[RL] The Linear Quadratic Regulator

 <본 포스트는 UC Berkeley 교수인 Benjamin Recht 의 블로그에 올라온 글을 번역한 것입니다. 원본>

 dynamic를 모르는 상태에서의 optimal control을 이해하고, 강화학습을 전개하는 입장에서 관점을 제공해주는 엄청 심플한 baseline이 있을까?

 일단 매우 일반화가 된 예에서 시작해보자. 일반적으로 알려진 optimal한 제어 문제는 다음 형태를 띈다:

\( \text{maximize}_{u_{t}}  \;\;   \mathbb E_{e_{t}}[\sum_{t=0}^{N}R_{t}[x_{t}, u_{t}]] \)
\( \text{subject to} \;\; x_{t+1} = f(x_{t}, u_{t}, e_{t}) \)
\( (x_{0} \; \text{given}) \)

 여기서 \(x_{t}\)는 system의 state이고, \(u_{t}\)는 제어 action이고, \(e_{t}\)는 랜덤한 에러를 나타낸다. f는 현재 state와 제어 action, 그리고 새로운 state의 에러에 대해 관계를 표현한 정의라고 보면 된다. 여기서 평균 값은 에러보다 큰 값을 나타내고, \(u_{t}\)는 \(x_{1}\)부터 \(x_{t}\)까지 본상태에서 선택된다. 이때 \(R_{t}\)는 주어진 state와 그때 취한 제어 action에 대해 매 시간별로 얻어지는 reward가 되겠다. 여기서 유념할 것은 \(x_{t}\)라는 것이 진짜 변수가 아니라는 것이다. \(x_{t}\)란 완전히 이전 state와 그때의 제어 action, 그리고 에러에 의해서 결정되는 값이다. 이처럼 수많은 정의들이 설명되어 있긴 하지만, 이걸 통해서 하나의 meta-optimization problem에서 매우 큰 단위의 decision-making problem을 도출할 수 있게 해준다.

 이를 설명하기 위한 첫번째 단계는 아마 언제 해당 문제가 convex이냐에 대해 다뤄보는 것이 되겠다. 예외들이 있긴 하지만, 일반적으로 convexity를 보장하는 하나의 조건은 그것이 선형 모델이라는 것이다. 해당 문제를 선형적으로 보기 위해서 dynamic 시스템은 다음의 수식을 띄어야 한다.

$$ x_{t+1} = A_{t}x_{t} + B_{t}u_{t} + e_{t} $$

이런 dynamical system이 제어이론에서는 핵심적인 역할을 하는데, 보통 이것을 linear dynamical system이라고 부른다. (이런 용어가 딱 창의적인 것은 아니지만, 일단 넘어가고자 한다.)

 선형 조건이 어떤면에서는 제한적일 수도 있지만, 대다수의 시스템은 동작시 선형성을 띈다. 실제로 기술 연구의 노력이 실제 시스템에 많이 녹아 들어가면서, 그 반응이 가능한 한 선형성을 띄게 되었다.

 우선 우리가 1장에서 다뤘던 Newton`s law를 따르는 quadrotor dynamics는 선형성을 띈다. quadrotor의 state는 그게 떠 있는 높이와 속도 \(x_{t} = [z_{t};v_{t}]\) 이다. 이때 입력 \(u_{t}\)는 프로펠러로 가하는 힘이 되겠다. 여기에 정의된 Newton`s law를 행렬로 표현하면 아래와 같다.

$$ x_{t} =  \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}x_{t} + \begin{bmatrix}0 \\ 1/m \end{bmatrix} (u_{t} - g) $$

 그러면 cost function은 어떻게 정의할까? cost function이란 강화학습에서 다뤄지는 주제로, 완전히 만들어져 있는 형태로 존재한다. 우리가 제어를 할때 그 목적을 달성하기 위해서 정의할 수 있는 cost가 다양하게 존재한다. 만약 우리가 quadrotor를 \(z_{f}\) 위치 만큼 날게 하고 싶으면, 아래와 같이 

$$ R_{t}[x_{t}, u_{t}] = |z_{t} - z_{f}| $$

나

$$ R_{t}[x_{t}, u_{t}] = (z_{t} - z_{f})^2 $$

나

$$ R_{t}[x_{t}, u_{t}] = \begin{cases} 1 & z_{t} = z_{f} \\ 0 & \text{otherwise}  \end{cases} $$

로 정의할 수 있다. 이 중 어떤 것이 최선일까? 컨트롤러 출력의 특성과 컨트롤러 연산 난이도에 따른 장단점이 있다. 여기서는 cost function을 설계하고 있기 때문에 쉽게 풀 수 있는 방향으로 cost에 초정을 맞춰야 한다.

 자유도(degree of freedom)의 관점에서, 다시 내가 만든 optimizer가 있고, convex quadratic cost가 바로 최적화 알고리즘을 검증할때 내가 찾고자 하는 1순위의 것이라고 지정해본다.. 더불어 \(R[x_{t}, u_{t}\)가 convex이며, quadratic funciton이라는 것을 가정해보자. 문제를 조금더 단순하게 만들기 위해서 \(x_{t}\)와 \(u_{t}\) 사이의 외적 항(cross term)은 0이라고 가정해보자.

 이런 관점에서, 내가 생각하기에는 optimal한 제어와 강화학습 공부에 가장 간단한 baseline이 바로 Linear Quadratic Regulator(LQR) 인거 같다.

$$ \text{minimize}_{u_{t}, x_{t}} \;\; \frac{1}{2} \sum_{t=0}^{N} \{ x_{t}^{T}Qx_{t} + u_{t}^{T}Ru_{t} \}  + \frac{1}{2}x_{N+1}^{T}Sx_{N+1},$$

$$ \text{subject on} \;\; x_{t+1} = Ax_{t} + Bu_{t}, \;\; \text{for t = 0, 1, ..., N,} ( x_{0} \; \text{given} )$$

 이때 \(e_{t} \)는 평균값을 0으로 가지고, 이전에 취했던 action과는 독립적으로 나타난다. 그러면 한가지 증명할 수 있는 것은 확률적으로 나오는 cost는 노이즈가 없는 LQR 문제에 \(u_{t}\)과는 독립적으로 나오는 상수를 더한 값과 같다는 것이다. 이때 노이즈는 실험후 나오는 cost에 의해 절감이 되겠지만, 어떤 제어 action를 선택하는지에 대해서는 영향을 미치지 않을 것이다. 이런 사실을 증명하기 위해서는 \(z_{0} = x_{0} \)을 만족하는 보조적인 시퀀스인 \(z_{t} \)를 정의하면 된다. 그게 다음과 같이 된다.

$$ z_{t+1} = Az_{t} + Bu_{t} $$

이렇게 하면 \(x_{t} = z_{t} + e_{t+1} \)와 같이 선형성을 띤 아름다운 시퀀스가 나오게 된다. 이때의 state는 노이즈가 없는 상태에서 노이즈가 가해진 state의 합으로 단순화시킬 수 있다. 이런 사실을 활용해서 \( \mathbb{E}[x_{t}^{T}Qx_{t} = z_{t}^{T}Qz_{t} + \mathbb{E}[e_{t}^{T}Qe_{t-1}] \) 를 계산할 수 있다. quadratic cost를 선택함으로써 이제 분석을 엄청 간단하게 할 수 있고, 이를 통해 확률적인 제어 문제를 설계할 수 있게 된다. 이때의 cost function은 적분의 형태를 띠고, 이게 곧 optimal한 제어를 설계하는데 중요한 부분을 차지하게 된다. 강화학습 연구자는 이렇게 cost를 설계하는 것을 "reward shaping"라고 표현한다. 이게 속임수를 쓰는게 아니고, 강화학습을 처리하는데 있어 필요한 적분 부분이 되는 것이다.

 이게 다시 앞에서 다뤘던 quadrotor 문제로 돌아가 이걸 LQR 형태로 맞춰보자, 우선 가지고 있는 변수를 정렬해서 \(u_{t} \leftarrow u_{t} - g \) 와 \(z_{t} \leftarrow z_{t} - z_{f} \)라고 정의해보자. 그 후에 가지고 있는 스칼라값인 \(r_{0} \)에 대해 0점을 맞추는 것을 다음과 같이 써볼 수 있다.

$$ Q = \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix} \;\,\; R = r_{0} $$

여기서 R 항목은 프로펠러 힘이 너무 많이 가해지는 것에 패널티를 준다.(이 행동이 배터리를 소모하기 때문이다.) 여기서 어떠한 LQR을 적용하더라도, 설계의 기본이 있는데, \(r_{0}\)를 변경할 경우, 배터리 수명과 quadrotor의 속도나 목적지에 도달하는 것과 균형을 맞추기 위해 제어의 특성이 변경될 것이라는 점이다.

(일종의) backpropagation에서 LQR을 푸는 방법 

LQR에서 optimal한 제어 법칙을 도출하기 위해서 내가 선호하는 방식은 최근에 몇몇 천재들에 의해서 backpropagation이라고 알려진, adjoints을 활용한 방법을 사용하는 것이다. 사실 몇 년전에도 backprop에 대한 포스트를 통해 LQR 예제를 풀었었다. 그리고 여기서 소개한 adjoints를 활용한 방법이 optimal한 제어를 위한 핵심 근간이 된다.

 우선 제어 정책을 구하기 위한 첫번째 단계는 lagrangian 방정식을 세우는 것이다. 그리고 변수인 u, x에 맞는 값과 모든 변수에 대해 소멸되는 미분값인 Lagrange multiplier p 값을 찾을 것이다. LQR 문제에 대한 Lagrangian 방식은 다음과 같은 형태를 띤다.

$$ \mathcal{L}(x, u, p) := \sum_{t=0}^{N} [\frac{1}{2}x_{t}^{T}Qx_{t} + \frac{1}{2}u_{t}^{T}Ru_{t} - p_{t+1}^{T}(x_{t+1} - Ax_{t} - Bu_{t})] + \frac{1}{2}x_{N+1}^{T}Sx_{N+1}$$

여기서 Lagrangian의 gradient term은 다음과 같이 표현할 수 있다.

\(\nabla_{x_{t}}\mathcal{L} = Qx_{t} - p_{t}+ A^{T}p_{t+1}, \)
\(\nabla_{x_{N+1}}\mathcal{L} = -p_{N+1} + Sx_{N+1}, \)
\(\nabla_{u_{t}}\mathcal{L} = Ru_{t} + B^{T}p_{t+1}, \)
\(\nabla_{p_{t}}\mathcal{L} = -x_{t} - Ax_{t-1}+ Bu_{t-1} \)

이제 각 gradient 항을 제거할 수 있는 모든 변수의 설정값을 찾아야 한다. \( \nabla_{p_{t}}\mathcal{L} = 0 \)을 만족시키기 위해서는, dynamical system model을 만족시킬 수 있는 state와 입력을 간단하게 정의해야 한다. co-states(앞에서 말한 adjoints) \(p_{t} \)와 이때의 제어 action인 \(u_{t}\)를 구하기 위한 가장 간단한 방법은 backward(뒤먹임)을 하는 것이다. 참고로 마지막 co-state는 다음 항목을 만족한다.

$$ p_{N+1} = Sx_{N+1}$$ 

\( Ru_{N} = -B^{T}p_{N+1} \) (3번째 식 참조) 과 \(x_{N+1} = Ax_{N} + Bu_{N} \) (4번째 식 참조) 이란 항등항을 사용해서 다음의 최종식을 구할 수 있다.

\(K_{N} = (R + B^{T}SB)^{-1}(B^{T}SA) \) 인
\(u_{N} = -K_{N}x_{N} \)

 마지막 제어 action은 마지막 state에 대한 선형 방정식이 된다. 이는 모든 시간상에서 적용이 될텐데, 이때 이를 만족하는 행렬 \( K_{t} \)가 존재한다.

\( u_{t} = -K_{t}x_{t} \)

이를 증명하기 위해서는 위의 수식을 반대로 풀어보면 된다. (t+1) 단계에서 co-state가 어떤 행렬 \( M_{t+1} \)을 만족한다고 가정해보자.

\( p_{t+1} = M_{t+1}x_{t+1} \)

이를 통해 다음과 같은 방정식을 도출해낼 수 있다.

\( u_{t} = -(R+ B^{T}M_{t+1}B)^{-1}B^{T}M_{t+1}Ax_{t} \)

이제 \(M_{t}\)에 관해서 어떻게 도출하면 될까? 위에서 소개했던 \(u_{t}\)를 \(x_{t}\)에 관한 식으로 표현해서 \(p_{t} = Qx_{t} + A^{T}p_{t+1} \)과 \(x_{t+1} = Ax_{t} + Bu_{t}\)이란 항등식을 조합해보면 다음과 같은 방정식을 얻을 수 있다.

\(M_{t} = Q + A^{T}M_{t+1}A - (A^{T}M_{t+1}B)(R+B^{T}M_{t+1}B)^{-1}(B^{T}M_{t+1}A)\)

여기에다 제어값인 \(u_{t}\)를 계산하기 위해서, \(M_{N+1} = S\)란 식에서 출발해 \(M_{t}\)를 계산할 수 있는 reverse recursion 방법을 돌려보면 된다. 이렇게 하면 \(M_{t}\)에서 계산되었던 값을 활용하여 \(u_{t}\)를 계산할 수 있게 된다.

 만약 N을 \( \infty\)까지 보내서, 조금더 긴 시간 범위상에서의 LQR 제어를 계산하고 싶으면, M에 대한 fixed point 방정식을 도출할 수 있다.

\( M = Q + A^{T}MA - (A^{T}MB)(R + B^{T}MB)^{-1}(B^{T}MA) \)

 위의 방정식을 Discrete Algebraic Riccati Equation이라고 부른다. 이를 통해, 우리는 optimal한 제어 policy가 다음의 

\(u_{t} = -Kx_{t}\)

의 상태를 가지는 선형 방정식이라는 것을 알게 되었고, 이때 K는 

\(K = (R+B^{T}MB)^{-1}B^{T}MA\)

라고 정의된 행렬이 된다.

 다시 말해, 무한 시간대에서의 LQR 상에서, optimal한 제어 policy는 static하고, 선형적이며, 상태를 feedback하는(state feedback)하는 형태를 가지게 된다. 결국 제어 policy는 한번 offline상에서 계산되게 되면, 무한 시간대까지 계속 동작시킬 수 있게 된다. 하지만 N이 그렇게 크지 않은 유한 시간대에서는 policy가 suboptimal한 제어를 띄게 될 것이다.

 한가지 Dynamic Programming을 좋아하는 사람에게 흥미있는 주제라면, 더 직관적인 Dynamic Programming 접근 방식을 통해서도 LQR 방정식을 풀 수 있다는 것이다. 아래와 같이 함축된 문제를 풀 수 있는 행렬 \(V_{k}\)가 있다고 가정해보자.

\( \text{maximize}_{u_{t}}  \;\;   \frac{1}{2}\sum_{t=0}^{k-1}\{x_{t}^{T}Qx_{t} + u_{t}^{T}Ru_{t}\} + x_{k}^{T}V_{k}x_{k} \)
\( \text{subject to} \;\; x_{t+1} = Ax_{t} + Bu_{t} \;\; \text{for t=0,1,...,N}\)
\( (x_{0} \; \text{given}) \)

이러면 시간 k-1번째까지의 \((x_{t}, u_{t})\)는 우리가 완전한 LQR 문제를 푸는 것과 동일할 것이다. 이렇게 함으로써 우리는 \(V_{k}\)가 존재함 뿐만 아니라 다음과 같은 형태를 지니고 있다는 것도 알 수 있게 된다.

\(V_{k}(x) = min_{u}x^{T}Qx + u^{T}Ru + (Ax + Bu)^{T}M_{k+1}(Ax + Bu)\)

이때 \(M_{k}\)는 우리가 위에서 도출했던 값과 동일하다. 결국 이를 통해 LQR 문제를 위한 cost-to-go, 또는 value function이 quadratic 이라는 것을 알게 되었고, 위에서 표현한 \(M_{k}\)로 정의할 수 있다는 것도 알게 되었다.

위치 문제에서의 LQR 적용 

 LQR을 구성하는 방정식들이 거의다 지저분한 행렬이나 역행렬등으로 구성되어 있지만, 이를 푸는 해는 매우 명확하다. 또한 이를 계산하고, 구현하기도 쉽다. 실제로 몇줄의 python코드를 통해서도 LQR controller를 설계할 수 있다.

 내가 예로 들었던 간단한 quadrotor 문제처럼 LQR이란 어떤 형태를 띄고 있을까? 이상적인 LQR 제어란 현재의 위치와 현재의 속도의 결합에 가중치가 가해진 형태로 되어 있을 것이다. 사실 속도란 위치의 미분된 형태이므로, 이 제어는 proportional derivative (PD) controller라고 할 수 있다. 놀랍지 않게도, 만약 quadrotor가 원하는 위치보다 위에 있게 되면, 제어 action은 줄어들게 될 것이고, 만약 아래에 있으면, 제어 action은 커질 것이다. 이와 유사하게 속도가 윗방향으로 너무 빠르게 움직인다면, controller는 이전보다 적은 힘을 가하게 될 것이다. 반대로 quadrotor가 떨어지는 상태라면 controller는 프로펠러 속도를 증가실 것이다.

 여기서 유념해야 할 것은 cost function에서 "R" 항목에 대해서 다른 설정을 줌으로써, 실제에서도 다른 행동을 취할 수 있다는 것이다. 만약 R이 작다면, equilibrium에 돌어오기 전까지는 0을 거의 초과하지 않을 것이다. 반대로 R값이 크다면, quadrotor는 원하는 위치까지 도달하기에는 조금 오래 걸릴수는 있겠지만, 입력으로 가해지는 힘의 총량은 작을 것이다.

어떤 경로 선정이 더 좋냐의 문제는 결국 제어 엔지니어가 결정하는 스펙의 문제가 될 것이고, 걸국 상황에 따라 다를 것이다.

결론 

 다시 말해서, 나는 LQR을 통해서 모든 optimal control 문제를 해결할 수 없을 거라고 했고, 해당 dynamics가 선형성을 띄더라도 그렇게 될거라고 했다. 예를 들어 rotor는 무한한 힘을 가할 수 없고, 제어 action을 취하는 데 있어서 약간의 제한이 적용되어야 한다.

 이와 반대로, 많이 눈에 띄는 특징들도 존재한다. Dynamic programming recursion을 통해서 제어 action을 효율적으로 계산할 수 있다. 긴 시간 영역에서, static policy는 거의 optimal하게 된다. 그리고 optimal한 제어 action은 미래에 얻을 수 있는 reward를 표현할 수 있는 특정함수를 간략하게 함으로써 찾을 수 있다. 이런 아이디어들이 LQR baseline을 넘어서서 일반화될 것이다. 게다가 미분계수를 계산하기 위해 Lagrangian을 사용하는 것도 즉각적으로 일반화될 것이고, optimal한 제어에 필요한 수많은 아이디어들의 기반을 형성할 것이다. 더불어 이런 아이디어들이 optimal control problem에서 Taylor approximation을 풀 수 있는 Iterative LQR의 근간이 되게 된다.

 이게 강화학습 관점에서 다뤄져야 할 주요 질문은 "만약 A와 B에 대해서 모르는 상태에서는 어떤일이 일어날까?" 하는 것이다. 제어를 해야되는 입장에서 optimal control action을 효율적이고 빠르게 찾기 위해서는 dynamical system과 어떤 방식으로 interact되어야 할까? 다음 포스트들에서 강화학습에 찾은 아이디어들과 이걸 간단하고 선형화된 baseline에 적용하는 것이 얼마나 적절한지에 대해서 다뤄보고자 한다. 우선 현재의 강화학습에서 통용되고 있는 규칙들에 대해서 다뤄보자 한다.