[RL] The Policy of Truth

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

우리가 처음으로 다뤄볼 강화학습 알고리즘은 Policy Gradient 이다. 사실 1993년에 Policy Gradient가 나쁜 아이디어로 찍혀서 나오지 못했다는 사실이 놀랍긴 하다. Policy Gradient는 어떠한 domain knowledge없이도 어떤 문제도 풀수 있게끔 프로그램을 좋게 튜닝하는데 도움을 주기 때문에 매력적인 알고리즘이다. 물론 어떤 알고리즘이든 이렇게 주장하려면 이렇게 주장하려면, 그 좋은 부분에 대해서 매우 일반적인 성향을 띄어야 한다. 실제로 살펴보면 알겠지만 policy gradient란 수학적 심볼과 공식으로 이뤄진 랜덤 탐색에 불과하다.

 사실 이 내용은 많은 포스트를 할애해야 하기 때문에 미리 사과하고자 한다. Policy Gradient란 어떤 것에 대해서 깊게 파고 들때 우리를 혼란스럽게 하는 표현들이 과도하게 많이 쓰인다. 내 생각에 Policy Gradient가 아직까지 연구 주제로 남아있는 이유 중 하나는 사람들이 이걸 구현하지 못하고, 수식 자체도 매우 매력적이기 때문인 것 같다. 이것때문에 Policy Gradient가 실제로 구현되었을 때 어떤 동작을 할지 관점을 잃기 쉽게끔 만드는 것 같다. 제대로 동작할 때 잘 이해할 수 있는지 한번 살펴보자.

해가 구해질 때까지 감산을 수행하기

 Policy Gradient로 풀수 있는 아주 일반적인 문제에서 시작해보자. 이전 포스트에서 언급했다시피 trajectory란 dynamic system에 의해서 생성되는 state \(x_{k}\)와 제어 action \(u_{k}\)의 sequence 형태라고 했었다.

\( \tau_{t} = (u_{1},...,u_{t-1},x_{0},...,x_{t}) \)

 그리고 policy는 \(\pi\)로 정의되는 함수로, trajectory를 입력으로 받고 새로운 제어 action을 출력으로 내뱉는 역할을 한다. 우리의 목표는 정해진 time step L동안 얻을 수 있는 총 reward를 최대화할 수 있는 policy를 찾는 것이다.

 Policy Gradient에서, 우리의 초점을 수치화시킬 수 있고(parametric), 랜덤화시킬 수 있는 policy에 맞춘다. 이때 policy \(\pi\)는 튜닝 할 수 있는 계수들의 집합으로 구성되어 있고, 보통 \(\vartheta\)라고 표현을 한다. 그리고 우리가 특정 제어 action을 반환하기 보다는 \(\pi\) 자체가 action에 대한 확률 분포를 표현하는 것이라고 가정해보자. 이때 action은 매순간 해당 확률 분포 \(\pi\)에서 샘플링함으로써 해당 값을 선택한다. 여기서 질문을 던질 수 있을텐데, 왜 그럼 샘플링을 할까?  이 질문은 굉장히 좋은건데, 일단 질문에 대한 답을 하지 말고 계속 가보자.

 우선 계수 \(\vartheta\)를 따라 변화를 줄 수 있도록 \(\pi_{\vartheta}\)를 만들어보자. \(\pi_{\vartheta}\) 가 확률분포이기 때문에, \(\pi_{\vartheta}\)를 사용했을 때의 trajectory에 대한 확률 분포는 다음과 같이 도출이 된다.

\( p(\tau, \vartheta) = \prod_{t=0}^{L-1} p(x_{t+1} \vert x_{t},u_{t}) \pi_\vartheta(u_t\vert \tau_t)  \)

 추가로 표현을 더해서, trajectory에 대한 reward를 다음과 같이 정의할 수 있다.

\( R(\tau) = \sum_{t=0}^N R_t(x_t,u_t) \)

이러면 강화학습으로 해결하기 위한 최적화 문제는 다음과 같이 된다.

\( \begin{array}{ll}\mbox{maximize}_{\vartheta} & \mathbb{E}_{p(\tau \vert \vartheta)}[ R(\tau)]\end{array} \)

여기서 조금더 정렬을 하면 다음과 같이 정의할 수 있고,

\( J(\vartheta) := \mathbb{E}_{p(\tau \vert \vartheta)}[ R(\tau) ] \)

이제 강화학습으로 풀 문제의 목표는 조금 더 간단하게 정의할 수 있다.

\(\begin{array}{ll} \mbox{maximize}_{\vartheta} & J(\vartheta) \end{array} \)

Policy Gradient

이제 문제를 깨끗하게 정리했으니 다음과 같은 공식을 통해 Policy Gradient를 유도할 수 있다.

$$ \begin{align*} \nabla_{\vartheta} J(\vartheta) &= \int R(\tau) \nabla_{\vartheta} p(\tau;\vartheta) d\tau\\
&= \int R(\tau) \left(\frac{\nabla_{\vartheta} p(\tau;\vartheta)}{p(\tau;\vartheta)}\right) p(\tau;\vartheta) d\tau\\ &= \int \left( R(\tau) \nabla_{\vartheta} \log p(\tau;\vartheta) \right) p(\tau;\vartheta)d\tau \\
&= \mathbb{E}_{p(\tau;\vartheta)}\left[ R(\tau) \nabla_{\vartheta} \log p(\tau;\vartheta) \right] \end{align*} $$

이 계산을 통해서 \(\vartheta\)에 관한 J의 Gradient는 다음 함수의 기대치라는 것을 알 수 있다.

\(G(\tau, \vartheta) = R(\tau)\nabla_{\vartheta} \log p(\tau;\vartheta)\)

 추가로 \(\pi_{\vartheta}\) policy를 수행해서 trajectory \(\tau\)를 샘플링했을 때, \(G(\tau, \vartheta)\)를 계산할 수 있고, J에 대한 gradient의 unbiased estimate를 구할 수 있게 된다. 이 방향을 따라서 J에 대한 stochastic Gradient Descent를 돌려볼 것이다.

 더 마법같은 것은 \(G(\tau, \vartheta)\)가 dynamical system을 구성하는 어떠한 방정식에 대해서 알 필요 없이 계산할 수 있다는 것이다. 이는 아래 함수

\(p(x_{t+1}|x_{t}, u_{t})\)

가 \(\vartheta\)에 관한 함수가 아니라는 것으로부터 알 수 있다. 더불어

\( \nabla_\vartheta \log p(\tau;\vartheta) = \sum_{t=0}^{L-1} \nabla_\vartheta \log \pi_\vartheta(u_t|\tau_t)\)

에서 나오는 미분 계수들은 \(\pi_{\vartheta}\)가 미분가능하고, 최신 버전의 autograd 가 설치되어 있다면 계산할 수 있다.

 요약하자면, 우리는 system의 dynamics에 대해 알 필요없이 optimal control problem을 최적화시킬 수 있는 기적적인 방법을 찾은 것이다.

    1. 초기 control parameter인 \(\vartheta_{0}\)와 stepsize sequence인 \(\alpha_{k}\)를 지정한다. 그리고 k=0으로 설정한다.
    2. 시뮬레이터 상에서 policy \(\pi_{\vartheta_{k}}\)를 돌려서 \(\tau_{k}\)를 샘플링한다.
    3. \( \vartheta_{k+1} = \vartheta_k + \alpha_k R(\tau_k) \sum_{t=0}^{L-1} \nabla_\vartheta \log \pi_\vartheta(u_{tk}\vert \tau_t)\) 를 설정한다.
    4. k = k+1로 증가시키고 step 2를 다시 수행한다.

 Policy Gradient가 매력있는 이유는 이렇게 쉽기 때문이다. 만약 \(\pi_{\vartheta}\)만 효율적으로 샘플링될 수 있다면, 어떤 문제든 이 알고리즘을 돌릴 수 있다. quadcopter를 날릴 수도 있고, data center를 냉각 시킬 수 있고, 로봇이 문을 열게끔 할수도 있다. 이제 질문은 당연히, 이걸 잘 할 수 있겠냐는 것이다. 내 생각에는 Linear Principle에서 얻었던 매력으로부터 얻을 수 있는 결론은 Policy Gradient가 당신이 사용하길 원하는 알고리즘은 절대 아니었을 것이란 사실이다.

왜 우리가 다시 확률론(Probabilistic) 기반의 policy를 사용해야 할까?

 선형 모델에 대해서 이야기 하기에 앞서서, 다시 돌아가 순수 최적화 과정에 대해서 다뤄보자. 이전 포스트를 통해 강화학습에서 사용되는 여러 정의들이 추가되었고, 결론적으로 우리는 어떤 제한이 가해지지 않은 함수를 최대화하는데 목적을 두고 있었다. 이제 모든 dynamics들을 배제시키고 optimal control problem에서 한 step만 간 상태에서 고려해보자. 주어진 함수 \(R(\tau)\) 에서, 나는 해당 값을 최대화시킬 수 있는 u를 찾길 원한다. 결국 나는 다음의 

\(\begin{array}{ll} \mbox{maximize}_{u} & R(u) \end{array} \)

최적화 문제를 풀고 싶은게 된다. 이제 두번째로 약간 논점에서 어긋난 내용을 다뤄보겠다. 위와 같은 최적화 문제는 u에 대해서 확률 분포에 대한 최적화를 다루는 것과 동일하다.

\(\begin{array}{ll} \mbox{maximize}_{p(u)} & \mathbb E_{p}[R(u)] \end{array} \)

 이제 동등성은 다음과 같이 정의된다. 만약 \(u_{*}\)가 optimal한 해라면, \(u_{*}\)를 Delta-function에 넣었을 때도 동일한 reward를 얻을 것이다. 게다가 만약 p가 확률 분포를 나타낸다면, 기대 reward는 절대로 고정된 u에 의해서 얻을 수 있는 최대 reward보다 클 수 없다는게 명확하다. 그래서 u에 관해서 최적화를 시키거나, u에 대한 분포 상에서 최적화를 시킬 수 있다는 것이다.

 이제 Policy Gradient에 대한 첫번째 논리를 언급해보자. 모든 확률 분포상에서 전체 공간에 대해 최적화하기 보다는, 계수가 정해진 \(p(u;\vartheta)\) 상에서 최적화하는 것이다. 만약 해당 확률 분포가 Delta function의 모든 것을 포함하고 있다면, 최적화된 해는 랜덤하지 않은 최적화 문제의 해와 일치할 것이다. 반대로 해당 확률 분포가 Delta function을 포함하지 않는다면, 우리가 찾는 확률 분포가 얼마나 좋은지 상관없이 optimal reward의 최소값만 찾을 수 있게 될 것이다. 이 경우, policy로부터 u를 샘플링한다면, 샘플링한 값의 기대 reward는 반드시 suboptimal할 것이다.

 이렇게 확률 분포상에서 최적화하는 접근 방식의 문제는 확률 분포들간의 여러 요구 조건들이 어느정도 균형이 이뤄져야 한다는 것이다. 그래서 다음과 같은 확률 분포가 필요하다.

    1. Delta function을 근사할 만큼 충분히 많은 정보가 담겨 있어야 한다.
    2. gradient 방법을 통해서 쉽게 탐색이 가능해야 한다.
    3. 해당 확률 분포로부터 쉽게 샘플링이 되어야 한다.

특히 연속된 값을 가지는 제어 action을 찾아야 할 경우에는 확률 분포상에 필요한 사항들이 많긴 하다. 연속된 action의 경우에는 다음과 같은 Gaussian Distribution의 형태를 취해야 할 것이다.

\(u_{t} = f(\tau_{t}) + g_{t}\)

여기서 f는 어떤 비선형 방정식이고, \(g_{t}\)는 Gaussian random vector를 나타낸다. 이런 식의 계수들로 구성된 모델은 Delta function을 포함하지 않는다. 그리고, 강화학습에서는 모델링을 하는 것 자체가 허용되지 않기 때문에 이렇게 계수화를 통해서 얼마나 값을 잃게 되는지도 명확하지가 않다.

 중요한 것은 우리가 지금까지 연구하고 있는 기본적인 optimal control problem에서는 랜덤화된 policy가 필요없다는 것이다. 그리고 동일하게 단순한 LQR 문제에서도 마찬가지다. 확률기반의 policy가 필요한 상황이지만, 이건 deterministic한 policy보다 절대 좋지 않다.

엄청 일반적인 REINFORCE 알고리즘

 위의 내용을 통해, Policy Gradient가 아래와 같은

\(J(\vartheta) := \mathbb E_{p(u;\vartheta)}[R(u)] \)

함수에서 reward의 stochastic gradient를 찾을 수 있는 일반적인 방법이라는 것을 알게 되었다. 이걸 푸는 log-likelihood 기법은 다음과 같다.

\begin{align*}
 \nabla_{\vartheta} J(\vartheta) &= \int R(u) \nabla_{\vartheta} p(u;\vartheta) du\\ &= \int R(u) \left(\frac{\nabla_{\vartheta} p(u;\vartheta)}{p(u;\vartheta)}\right) p(u;\vartheta) du\\ &= \int \left( R(u) \nabla_{\vartheta} \log p(u;\vartheta) \right) p(u;\vartheta)du\\ &= \mathbb {E}_{p(u;\vartheta)}\left[ R(u) \nabla_{\vartheta} \log p(u;\vartheta) \right] \end{align*} 

더불어 계수화 분포에 관하여 reward는 최대화시킬 수 있는 일반적인 알고리즘은 다음과 같다.

    1. 초기 선택값 \(\vartheta_{0}\)과 stepsize sequence \(\alpha_{k}\)를 정하고, k = 0으로 지정한다.
    2. \(p(u;\vartheta_{k})\)에서 i.i.d를 따르는 \(u_{k}\)를 샘플링한다.
    3. \(\vartheta_{k+1} = \vartheta_{k} + \alpha_{k}R(u_{k}\nabla_{\vartheta} \log p(u_{k};\vartheta_{k}) \) 를 설정한다.
    4. k = k+1로 증가시키도 step 2를 다시 수행한다.

이런 형태의 알고리즘을 REINFORCE 라고 부른다. 약간 이상해 보일 수 있다. 우리가 얻은 것은 stochastic gradient이지만 우리가 최적화하고자 하는 함수 R은 function evaluation을 통해서만 값을 다룰 수 있다. R 자체로는 R에 대한 gradient를 계산할 수  없다. 이 알고리즘이 좋은 것일까?

 그건 너가 뭘 찾기 원하는지에 따라 다르다. 만약 gradient간의 어떤 관계를 찾는다면, 이 알고리즘은 안 좋다. 만약 R에 대해서 여타 다른 finite difference를 근사하는 기법에 대한 알고리즘을 찾아도 여전히 안 좋은 알고리즘이다. 그래도 여기에 들어가는 수학 자체는 괜찮다.

 핵심은 Linear Principle이 해당 알고리즘이 당장 버려야 할 알고리즘이라고 말하고 있는 것이다. LQR에서 가장 평범한 예제를 한번 살펴보자. 이때 \(R(u) = -||u-z||^2\)이고, \(p(u;\vartheta)\)는 평균 \(\vartheta\)와 분산 \(\sigma^{2}I\) 를 가지는 multivariate Gaussian이라고 가정해보자. Policy Gradient는 어떻게 동작할까? 우선 다음 수식을 살펴보자.

\( \mathbb{E}_{p(u;\vartheta)}[R(u)] = -||\vartheta - z||^{2}-\sigma^{2}d \)

 이때 우리가 취할 수 있는 최고의 방법은 \( \vartheta = z\)라고 지정하는 것이다. 이때 해당 지점에서의 기대 reward는 \(\sigma^{2}d \)이지만, 이 값은 u에 대해서 좋은 값을 찾기에는 적어도 도움이 될 것이다. 또한 \(\vartheta\) 함수와 마찬가지로, J 함수도 완전히 convex를 띄고, 가장 중요한 부분은 해당 지점에서의 gradient에 대한 기대 norm 값에 따라 반복 횟수가 결정된다는 것이다. 이제, \(\vartheta = 0\)에서 시작해보면 gradient는 

\( g =\frac{||\omega-z||^2 \omega}{\sigma^2} \)

가 될 것이고, 이때 \(\omega\)는 0의 평균값과 covariance \(\sigma^{2}I\)를 가지는 normally distributed random vector가 된다. 해당 stochastic gradient의 기대 norm은.. 많이 크다. 아마 6차 계수 항목까지 계산해야 할 것이고, 이건 결코 재미가 없을 것이다. 이걸 통과하더라도, 아마 기대 norm이 다음과 같이

\(O(\sigma d^{1.5} + \sigma^{-1}d^{0.5}||z||) \)

의 형식을 갖추게 되는데, 이 값은 매우 크다. 차원에 대해서 scaling을 해도 문제가 될 것이다.

 많은 사람들이 이런 접근 방식의 복잡성에 대해서 분석해봤는데, 사실 이 방법은 좋지 않고, 탐색 space 의 차원에 따라 값이 크게 변하는 것을 알게 되었다. 또한 가장 큰 reward B의 배수에 따라 달라지는 것도 알게 되었다. 만약 함수의 output에 노이즈가 있고, convex function이라 할지라도, 해당 함수의 수렴률은 \(O((d^{2}B^{2}/T)^{-1/3})\)가 될텐데, 이 값은 알고리즘의 계수들이 완벽하게 딱 맞는 것을 가정한 케이스이다. 완전히 convex function을 띄는 케이스에서는, \(O((d^{2}B^{2}/T)^{-1/2})\) function evaluation에 맞는 해를 억지로 찾을 수 있겠지만, 이 해 또한 계수를 어떻게 선정하느냐에 따라서 크게 달라지기 쉽다. 결국 reward에 단순히 상수값을 더하는 것만으로도 알고리즘의 처리 속도를 급격하게 줄일 수 있다. 만약 [0,1] 사이 값을 가지는 reward 함수에서 시작하고, 각 reward별로 1씩 백만번 빼야한다고 치면, 계수 내의 보상의 순서가 같다 할지라도 알고리즘의 동작시간이 기존보다 백만배만큼 늘어날 것이다.

 유념할 것은 이 문제를 dynamics에 가져다 놓으면 더 심각해진다는 것이다. LQR에 대한 Policy Gradient를 update하는 것이 노이즈가 매우 많고, 시뮬레이션 동작범위 L에 대해 그 분산도 커지게 될 것이다. 게다가 \(\vartheta\) 를 찾는 것도 단순한 static policy를 찾는 경우라면 non-convex를 띄게 된다. 물론 이렇게 현업에 적용할 수 있겠지만, 이미 위 사례에서도 수많은 허들이 나왔고, 다른 대안을 찾는 것이 더 좋을 수 있다는 걸 알 수 있다.

그럼 사람들이 어떻게 강화학습에서 성공하는 것일까?

  수많은 논문들이 다양한 설정값을 가지고 policy gradient를 적용해보았고, 미친 결과도 얻어냈지만, 이런 결과들이 이제는 현명한 방법을 가지고도 단순히 랜덤하게 찾는 방식을 적용했다는게 명확해졌으리라 생각한다. 아마 유전 알고리즘이 강화학습 알고리즘와 대적할 만 하다는 것을 보여주는 논문들을 읽다보면, 이게 유전 알고리즘이 좋아서 그런게 아니라는 것을 알게 될 것이다. 어떻게 보면 지금 적용하고 있는 방법이 랜덤하게 찾는 방식을 약간 티나게 구현한 것과 같다고 보면 된다.

 그럼에도 유전 알고리즘이나 policy gradient 방법은 합리적이지 않을 만큼의 샘플들이 필요하다. 만약 당신이 AWS를 사용하는데 수백만불을 기꺼이 쓸 수 있다면 좋겠지만, 이게 실제 시스템을 튜닝해주지는 않을 것이다. 그리고 더 좋은 방법이 있다.

 나는 policy gradient나 강화학습이 마법이 아니라는 것을 크게 강조한다고 생각하지 않는다. 다르게 말해 policy gradient나 이의 미분계수를 구하는 것은 어쩌면 나쁜 알고리즘일 수도 있다. 이런 알고리즘을 잘 동작하게 하기 위해서는 수많은 트릭들이 필요하다. 튜닝하기 어렵거나 결과를 재생산하기 어려운 알고리즘이나 high level의 유전 알고리즘을 넘어서지 못하는 것들은 좋은 알고리즘이 아니다.

 아마 시리즈를 다루면서 다시 해당 내용을 다루게 될 것이다. policy gradient가 잘 적용되는 케이스에 대해서 또다른 엄청 간단하고, 단단한 알고리즘이 존재할 것이고, 어쩌면 잘 동작할 수도 있다. 이런 건 좋은 아이디어도 아니고, 왜 이게 이렇게 유명한건지 규명할 수도 없다.

 사실 다음 포스트에서 LQR를 다시 살펴보고 policy gradient보다 더 성능이 잘 나오는 방법들을 찾아볼 것이다.