[RL] Lost Horizons

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

 이번 글은 cost와 state transition을 알지 못하는 상태에서의 optimal control을 위한 강화학습의 관점을 설명하는 것에서 시작해보고자 한다. 모두들 알다시피 Dynamic Programming을 통해서 optimal solution을 구할 수 있다. 하지만, 현재의 모델이나 cost를 모를 때나, 전체 dynamic program를 수정하기 어려운 상황이라면, RL 문제를 풀기 위해서는 approximation(근사) 기법에 의존해야 한다.

 물론, dynamic program을 근사하는 것은 매우 어려운 부분이다. Bertsekas는 최근 "dynamic programming and optimal control"의 개정판을 출간했으며, 해당 책 2권의 6장을 살펴보면 dynamic programming을 근사하기 위해서 필요한 데이터 기반의 방법론에 대해서 종합적으로 분석했다. Bertsekas가 해당 책에서 설명한 것을 모두 반복해서 언급하기를 원하지는 않지만, 내 생각에 문제에 관한 그의 관점을 설명하는 것이 Receding Horizon Control(RHC)을 명확하게 설명해주고, 전통적인 제어 측면과 강화학습 측면에서 서로 보완점이 될 수 있도록 가교 역할을 해줄 것이라 본다.

Approximate Dynamic Programming

 Dynamic Programming에 대해서 장황하게 설명하고 싶진 않지만, 기초를 복습하는 차원에서 짧게 설명해보겠다.

 우리가 이전에 다뤘던 전통적인 optimal control 문제로 되돌아가보자.

$$ \begin{array}{ll} \mbox{maximize}_{u_t} & \mathbb{E}_{e_t}[ \sum_{t=0}^N R[x_t,u_t] ]\\ \mbox{subject to} & x_{t+1} = f(x_t, u_t, e_t)\\ & \mbox{($x_0$ given).} \end{array} $$

 비록 알려져 있는 batch solver 같은 것을 사용해서 정해진 시간 범주 내의 문제를 풀수 있긴 하지만, Dynamic Programming과 Optimality의 원칙에 기반한 간단한 방법이 있다. 만약 정해진 시간 범주 N내의 optimal control policy를 \(\pi_{1},...,\pi_{N}\) 라고 찾았다고 가정해보고, 이 상태에서 정해진 시간 t에 state \(x\)에서 시작하는 optimal한 제어 동작을 하길 원한다고 해보자. 그러면, 이 말은 시간 \(t\)부터 시작하는 optimal policy인 \(\pi_{t},...,\pi_{N}\)을 찾아야 할 것이다. 그러면 Dynamic Programming은 종료 시간에서 부터 출발하여 recursive하게 control policy를 찾게 될 것이고, 점점 시간을 앞당기면서 문제를 recursive하게 해결할 것이다.

 이를 무한대 시간에 놓고 보기 위해서, \(N\)을 무한대로 보내면, 우리는 optimality의 원칙에 대한 명확한 정의를 찾을 수 있게 된다. 만약 초기 상태 \(x\)에서의 optimal control 문제를 풀기 위해 받은 값을 \(V(x)\)라고 정의하면, 수식은 다음과 같이 정의할 수 있다.

$$ V(x) = \max_u \mathbb{E}_{e}\left[R[x,u] + V(f(x,u,e))\right]\,$$

Bellman`s Equation이라 알려져 있는 있는 이 공식은 주어진 optimal control problem 구조내에선 거의 명백하다. 하지만 이를 통해서 \(V\)에 관한 강력한 recursive formula를 정의할 수 있고, dynamic programming에 포함되어 있는 수많은 알고리즘의 기반을 형성해준다. 추가로 유념할 부분은 만약 위의 공식의 우변항을 최적화할 수 있는 방법을 찾았다면, 결국 이를 통해서 우변항을 최소화할 수 있는 \(u\)를 찾아 optimal action을 취할 수 있게 된다.

 TD나 Q-learning과 같은 고전적인 강화학습 알고리즘은 Bellman equation을 시작점으로 삼고, 데이터를 사용해서 value function을 되풀이하며 풀려고 한다. 이런 아이디어는 DQN과 같이 유명한 방법의 기반을 형성해줬다. 여기서 다시한번 Bertsekas의 내용을 읽어볼 것을 권하는데, 여기엔 이 bellman equation을 근사해서 해결하기 위한 많은 다양한 방법들을 소개하고 있다. 이 내용들을 다루는 것보다 bellman equation을 푸는 방법들과 Receding Horizon Control을 비교하는 부분으로 넘어가보자 한다.

Receding Horizon Control

  이전 포스트에서 다룬 바와 같이, 컨트롤러의 95%는 PID로 구성되어 있다. 남은 5% 중, 95%는 receding horizon control(RHC)를 기반으로 한다. Model Predictive Control(MPC)라고도 알려져 있는 RHC는 시뮬레이션과 피드백에 결합되어 있는 제어에 놀라울만큼 강력한 방법이다.

 RHC에선, agent가 현재에서 미래까지의 짧은 시간동안 시뮬레이션을 돌려서, 해당 결과를 기반으로 plan을 만든다. 그런 다음 plan의 첫 동작을 수행하고, 동작 후의 관측한 내용을 바탕으로 다음 action을 plan하기 위한 짧은 시뮬레이션을 수행하는 방식으로 진행된다. 이런 feedback loop는 agent로 하여금 시뮬레이션된 결과에 대한 action의 선택의 영향을 고려할 수 있게 해주고, 더불어 현재 모델의 mismatch나 noise realization, 그리고 예상치 못한 다른 오류들을 보정해주기도 한다.

비록 LSTD나 Q-learning가 "현대강화학습"의 범주안에 있는 반면에, MPC는 "고전적인 제어"로 언급되는 것을 들어왔지만, 내 생각에는 위의 것들이 approximate dynamic programming의 서로 다른 종류라고 보는 것이 좋을거 같다. 

 유념할 것은 value function \(V(x_{0})\)는 다음과 같은 최적화 문제

$$ \begin{array}{ll} \max_{u_t} & \mathbb{E}_{e_t}[ \sum_{t=0}^N R[x_t,u_t]  + V(x_{N+1})]\\ \mbox{subject to} & x_{t+1} = f(x_t, u_t, e_t)\\ & \mbox{($x_0$ given).} \end{array}$$

에서 최대값을 나타낸다는 것이다. 여기서 한 step 너머의 cost를 풀어쓰긴 했지만, 여전히 미래의 N step에 대한 cost는 수집하고 있다. 이게 사소한 것일 수도 있지만, 다시한번 말하건데 정말 강력한 효과를 나타낸다: 우리가 시간 수평축을 좀더 길게 잡을수록, value function \(V\)가 꼭 정확해야 할 걱정이 덜어지게 되는 것이다. 물론 이렇게 되면, 이제 state-transition map의 정확성에 대해서 고민을 해봐야 한다. 하지만, 특히 연속된 변수와 관련된 문제라면, 빠른 학습률과 짧은 연산 속도를 가지는 알고리즘을 찾는데 있어 정확성은 더이상 절대적이지 않다는 것이다. 학습 모델과 학습 value function 간에 장단점이 존재하고, 우리가 좀더 이해가 필요한 장단점이 된다.

 비록 RHC 방법이 모델 부정확성에 대해서 약한 모습을 나타낼 수도 있지만, 해당 방법이 단순히 모델의 좋은 정도에 불과한 것이기 때문에 RHC내부에 반복적으로 피드백을 줌으로써 수많은 모델링 오차를 보정할 수 있다. 예를 들어 MuJoCo 프레임워크 안에 포함된 robot 운동 task를 다시 살펴보는 것이 도움이 된다. 이런 task들은 실제로 Tassa와 Erez, 그리고 Todorov에 의해서 개발된 비선형 RHC 알고리즘 성능을 확인하기 위해 설계된 것이기도 하다.

 2012년에 해당 controller에서의 action을 찍은 비디오이다.

MuJoCo

2:50으로 넘겨보면, 우리가 이전에 random search 포스트에서 이야기 했던 휴머노이드 모델을 볼 수 있다. 유념할 것은 아무리 모델이 나쁘게 정의되어 있어도, controller는 로봇이 계속 위로 향하게끔 동작한다는 것이다. 더불어 RHC loop 내의 피드백 값은 모델링시 발생한 오류에 대해서 상당할 정도의 강한 특성을 제공하고 있다. 또하나 살펴봐야 할 점은 이 데모가 value function을 전혀 평가하지 않았다는 것이다. 대신, 그들은 무한대의 시간상의 time-horizon 문제를 단순하게 줄였다. 제어를 하는 목적으로 놓고 봤을때 receding horizon approximation은 이미 잘 동작했다.

 게다가, 위에 링크된 영상은 2012년 당시에 실제 시간보다 7배 빠른 환경상의 controller에 맞췄다. 이것도 나쁘지 않은 결과이고, 만약 이것만 전문적으로 하는 엔지니어가 있었다면, 실시간 하드웨어를 사용해서 실시간으로 동작하게끔 맞췄을 것이다. 하지만 2013년에 언급된 내용중에, 같은 연구 그룹이 DARPA robotics challenge에 사용했던 controller의 원형을 공개했는데, 여기 있는 영상은 매우 인상적이다.

여기의 해동들은 실시간으로 MPC에 의해서 생성된 것이다. 걷는 동작은 많은 연산량이 필요한 long-horizon trajectory optimization으로부터 얻은것에 비할바는 아니지만, 적어도 지난번 포스트에서 다뤘던 direct policy search gait보다는 훨씬 좋아진 것처럼 보인다.

Learning in RHC

 연산량이 많은 offline trajectory optimization과 실시간으로 모델을 예측할 수 있는 제어(model-predictive control) 의 중간단계가 있을까? 내 생각에는 있는 것같고, 이와 동일하게 learning dynamical model과 learning value function 의 중간 단계도 있을 거 같다. receding control system에서의 성능은 terminal cost가 정의된 value function을 잘 모델링함으로써 성능을 향상시킬 수 있다. value function에 맞는 좋은 모델을 만들수록, 시뮬레이션시 필요한 time horizon은 짧아지게 되고, 그만큼 실시간 동작에 가깝게 된다. 물론 value function에 대한 완벽한 모델을 갖게 된다면, Bellman equation을 풀 수 있게 되고, optimal control policy를 가지게 된다. 하지만 value function에 대해 근사를 해도, 실시간으로 여전히 높은 성능을 얻을 수 있다.

 그러면 만약 RHC가 동작하는 동안 value function을 반복적으로 개선시키는 것을 학습하게 된다면 어떻게 될까? 이 아이디어는 내 Berkeley 동료들인 Rosolia, Carvalho, Borrelli의 프로젝트에서 나온 것이다. 그들이 수행하고 있는 "Learning MPC" 접근 방식에서는 terminal cost가 가장 가까운 이웃으로부터 학습되어진다. 현재 state의 terminal cost는 해당 state에서 마지막으로 얻었던 value가 된다. 만약 그 state를 방문하지 않았다면, cost는 무한대가 된다. 이런 정의는 terminal condition이 이전에 관찰한 state내에 들어가는 것을 억제한다. 그러면 이미 안전하다고 확인된 state에 도달하게 되는 한, 유한한 time horizon내에서 cost를 줄이는 새로운 방법을 구할 수 있게 된다.

 이런 제어에서의 nearest-neighbor 방식은 실제에서도 잘 동작한다. 여기 영상을 해당 방법을 RC카에 적용한 결과이다.

 몇바퀴 안돌아도, 학습된 controller는 사람이 제어하는 것보다 더 잘 동작한다. 간단한 nearest neighbor 방법은 복잡한 자율 행동을 학습하기에도 충분한 것이다. 그리고, 만약 이런 일을 하게 되면서, 제어 성능 관점에서 monotonic하게 증가하는 것을 보여줄 수 있다. 실제 학습률을 조절하는 문제가 남아있긴 하지만, RL 이론가들한테는 연구할 여지가 있는 훌륭한 문제가 될 것이다. 하지만 내 생각엔 이 예제는 RHC 방법과 Q-learning 방법간의 틈이 처음 등장했을 때보다는 훨씬 작아진 것을 명확하게 보여주는 것 같다.

Safety While Learning

 제어에서 학습하는데 있어 이런 잘 혼합된 RHC 방법을 선호하는 또다른 이유는 control이나 state에 대해서 자신이 직접 조절할 수 있고, 학습에 안좋은 영향을 끼치는 모델과 최적화 관점에서 잘 통합시킬 수 있기 때문이다. 제어 상에서의 가장 도전적인 문제 중 몇몇은 시스템 한계에 대해서 학습을 지속적으로 하면서 얼마나 안전하게 동작시킬 수 있느냐는 것인데, RHC 방법은 안전과 성능의 균형을 맞추는 직접적인 길을 제공해준다. 다음 포스트에서 직접적으로 평가하고, 도델링 오류를 잘 조합해서 제어 설계시 반영하는 최적화 기반의 방법에 대해서 언급해보고자 한다.