Policy Gradient Methods

이번 포스팅은 RL분야에서 최근 대두되는 알고리즘을 소개하고자 한다. 이전 포스팅들은 action-value function을 기반으로 하여 학습을 하는 알고리즘이었다. 즉, action-value를 통해 간접적으로 policy가 결정되는 형태이다. 이번에 소개할 알고리즘은 value function을 구하지 않고도 action을 선택할 수 있는 parameterized policy에 관한 것이다. Value function이 policy weights를 학습하기 위해 여전히 사용될 수도 있지만 action을 선택하는데는 필요하지 않다. 우리는 policy를 구하는데 관심을 둘것이므로 weight parameter는 아래 수식과 같이 policy function용으로 사용될 것이다.

 \pi(a|s, \boldsymbol{\theta}) \doteq Pr\{A_t =a | S_t = s,\boldsymbol{\theta_t} =\boldsymbol{\theta}\}

Value function을 추가로 학습하는지에 대한 여부와는 상관없이 이러한 방식을 따르는 모든 methods를 policy gradient methods라고 한다. Policy와 value function을 모두 학습하는 methods를 actor-critic methods라고 하며, 여기서 actor는 학습한 policy를 의미하고, critic은 학습한 value function(일반적으로 state-value function)을 지칭한다. 먼저 episodic case의 경우 performance는 parameterized policy하에 start state의 value라고 정의할 수 있다:

\eta(\boldsymbol{\theta}) = v_{\pi_{\boldsymbol{\theta}}} (S_0)

Continuing task의 경우는 average value를 사용하여 다음과 같이 정의 할 수 있을 것이다.

\eta(\boldsymbol{\theta}) = \displaystyle\sum_{s} d_{\pi_{\boldsymbol{\theta}}} (s) v_{\pi_{\boldsymbol{\theta}}} (s)

위와 같이 performance function이 주어지면, 우리가 할일은 이러한 performance를 최대화 시키는 policy parameter \boldsymbol{\theta}를 찾아내는 것이다. 그러므로 policy based reinforcement learning은 optimization 문제와 동일하다. 이러한 optimization 문제를 해결하는 알고리즘은 이미 많이 연구되었고, 다른 기술/공학분야에서 많이 사용되고 있다. RL에서는 물론 gradient descent방법을 사용하는 것을 기본으로 한다. Policy gradient algorithm은 performance function의 maximum을 만족시키는 다음과 같은 조건을 찾으려고 한다.

\boldsymbol{\theta} \doteq \boldsymbol{\theta} + \alpha \nabla_{\boldsymbol{\theta}} \eta (\boldsymbol{\theta})

여기서, \nabla_{\boldsymbol{\theta}} \eta (\boldsymbol{\theta})는 policy gradient vector이다.

Policy Approximation and its Advantages

Policy gradient methods에서, \pi (a|s,\boldsymbol{\theta})가 미분가능하다면, 즉 \nabla_{\boldsymbol{\theta}} \pi (a|s,\boldsymbol{\theta})가 존재한다면, policy는 어떤 형태의 parameter 함수도 가능하다. Policy-based methods는 discrete action-space뿐만 아니라 continuous action-space에서도 유용하다.

만약 action space가 discrete(이산)이며 크지 않다면, 자연스러운 방식의 parameterization은 각 state-action pair에 해당하는 parameterized numerical preferences h(s, a, \boldsymbol{\theta}) \in \mathbb{R} 를 도입하는 것이다. 각 state에서 가장 선호되는 action은, 예를 들어 아래와 같은 exponential softmax distribution에 따라, 선택될 확률이 가장 높은 것이 될것이다.

rl-eq13-2

정의된 preference는 어떤 형태로든 parameterize 가능하다. 예를 들면, Deep-Q-network system에서와 같이 \boldsymbol{\theta}를 weights로 가지는 deep neural network형태일 수도 있다. 아니면, preference 함수는 간단히 아래아 같이 feature vector  \phi(s,a) \in \mathbb{R}^n 를 가진 선형형태일 수도 있다.

rl-eq13-3

action preference에 softmax함수를 사용하여 action을 선택하는 것의 장점은 approximate policy가 determinism에 접근한다는 점이다. 반면에 action value을 기반으로한 \epsilon-greedy action선택은 \epsilon 확률만큼 무작위로 action을 선택하게 된다. policy parameterization방법이 action-value parameterization방법에 비해 가장 단순한 장점이라면, policy가 추정하기 더 간단한 함수형태라는 점이다. 문제에 따라 두 parameterization방법의 complexity가 다를 수 있으나, policy가 더 간단한 경우, 학습속도가 더 빠르고 뛰어난 수렴성능을 보인다. 또한 문제가 매우 중대한 결정이 필요하다면, 가장 적절한 approximate policy는 stochastics형태일 것이다. Action-value methods는 stochastic policy를 구해낼 직접적인 방법이 없는 반면, policy approximation methods는 가능하다.

Policy Gradient Theorem

앞에서 policy parameterization 방법을 위한 performance를 정의하면서 true value function v_{\pi_{\boldsymbol{\theta}}}이 사용되었다. 문제는 performance가 action과 states 모두의 함수라는 점이며, 이 둘은 policy weight의 영향을 받는다. state가 주어지면, policy parameterization정보로 부터 action(결국, reward)에 미치는 policy weights의 영향을 비교적 명확하게 계산될 수 있다. 그러나, policy가 state distribution에 미치는 영향은 온전히 environment의 함수이며, 알 수 없는 것이다. 그렇다면, 우리는 어떻게 policy가 영향받는 state distribution을 모른 상태에서 이 모르는 정보에 영향받는 policy weights의 performance gradient를 추정할 수 있을까? (글이 너무 복잡하다. 요점은 performance는 policy weights에 영향을 받는 state와 action의 함수이지만, 알 수 없는 state에 대한 정보가 없으면 gradient를 구할 수 없다는 얘기다.)

이점을 보다 명확히 정의하기 위해 policy gradient theorem이 도입되었는데, 이 theorem은 이론적 수식으로 performance gradient와 policy weights, value function과의 관계를 규정해 놓은것이며, 아래와 같다.

rl-eq13-5

여기서, gradients는  policy weights 성분에 대한 편미분항으로 이루어진 column vector이다. Episodic case에서 d_{\pi}(s)는 state s_0에서 시작하고 policy \pi를 따르는 MDP dynamics에서 state S_t =s가 되는 time step 수의 기대값이다.

이제 policy gradient를 보다 실제적인 응용을 위해 더 깊게 생각해 보자. Policy gradient theorem은 gradient ascent algorithm에서 필요한 performance gradient를 정확히 수식으로 표현해주고 있다. 이제 우리가 필요한 것은 sampling을 통해 얻은 기대치가 이 수식과 같거나 또는 근사치를 주는 어떤 방법을 찾아내는 것이다. Policy gradient theorem의 오른편은 policy \pi를 따르면서 얼마나 자주 어떤 state가 나타나는지를 가중치로 두고 있으며, 이것을 다시 몇번의 time step을 거쳐 그 state에 도달했는지를 나타내는 가중치  \gamma^t가 요구된다. \pi 를 따른다면 우리는 이것과 비례해서 state를 방문하게 될것이고 \gamma^t를 가중치로 사용하는 expected value를 아래와 같이 생각해 볼 수 있다.

rl-eq13-5

이와 같은 과정을 action에 대해서도 시도해 보자. 위 식의 나머지 부분은 action에 대한 합이며, action 선택확률을 가중치로 사용될것이다. 그러므로 이 확률을 곱하고 나누는 작업을 수행하여 다음과 같이 위 식을 변경시킨다.

rl-eq13-6a

위식에서 value로는 어떤 것이든 사용 가능하다. one-step reward (r)이 사용될 수도 있고, long-term reward 또는 accumulated reward등이 사용될 수 있다. 위의 식 유도에서  vector \frac{\nabla_{\boldsymbol{\theta}} \pi (A_t|S_t , \boldsymbol{\theta})}{\pi (A_t|S_t , \boldsymbol{\theta})} 는 policy parameterization이 나타나는 유일한 항이다. 이 벡터는 여러 이름으로 불리지만, eligibility vector라고 하자. 이 벡터를 likelihood ratio를 이용하면 다음과 같이 수학적으로 동일한 \nabla_{\boldsymbol{\theta}} log \pi (A_t|S_t , \boldsymbol{\theta})로 표현할 수 있으며, 이것을 score function이라고 부르기도 한다.(이 score function은 policy gradient를 구하면서 나온 term이기 때문에 자주 사용된다.) 위에서 언급한 바와 같이 linear action preference를 사용하여 softmax function를 적용하게 되면, eligibility vector는 다음과 같으며, softmax policy를 따른다고 말한다.

rl-eq13-7

Softmax policy는 deterministic action space에 알맞는 policy이다. Action space가 continuous인 경우에는 Gaussian policy가 더 자연스러운 선택이 될것이다.

REINFORCE : Monte Carlo Policy Gradient

위의 performance gradient를 policy gradient의 함수로 정의하는 것은 정확히 우리가 원하는 형태이다. 각 time step에서 sample를 통해 얻은 quantity의 기대치는 gradient와 비례한다. 이것을 gradient ascent algorithm에 적용하면 다음과 같은 update를 얻을 수 있다.

RL eq13.6.png

이 알고리즘을 REINFORCE algorithm이라고 한다. 이 update rule을 살펴보면, 변화량은 return G_t와 vector(action을 선택할 확률의 gradient를 그 확률자체로 나눈 항)와의 곱과 비례한다. 이 vector는  미래에 state S_t에서 다시 action A_t를 선택할 확률을 증가시키도록 weight space의 변화 방향을 결정한다. update는 return과 비례해서 weight를 증가시키는 반면, action probability와는 반비례한다.

주목해야 할 점은 REINFORCE algorithm은 episode가 끝나는 최종 return값을 사용한다는 점이다. 이런 의미에서 REINFORCE는 Monte Carlo algorithm이라고 할 수 있다. 아래는 REINFORCE algorithm의 pseudocode이다.

rl-reinforce-algorithm

하나의 episode를 이용한REINFORCE update는 performance gradient와 같은 방향이다. 그러므로, 충분히 작은 α를 사용하면 진전이 확실히 일어나면서 local optimum에 수렴한다. 그러나, Monte Carlo method로서의 REINFORCE는  큰 variance를 가질 수 있고, 학습속도 저하가 일어날 수 있다.

REINFORCE with Baseline

Policy gradient theorem은 임의의 baselineb(s)와 action value를 비교하는 형태를 사용하여 아래와 같이 일반화 할 수 있다.

rl-eq13-8

Baseline은 이것이 action a에 따라 변하지 않는다면, 어떤 형태의 함수도 될 수 있고, 위의 식은 아래식에서 보인바와 같이 빼주는 항이 제로가 되기 때문에 항상 성립한다.

rl-eq13-8a

그러나, 우리가 policy gradient theorem을 expectation과 update rule로 전환하다보면, baseline은 update rule의 variance에 지대한 영향을 미치게 된다. Baseline을 포함한  새로운 버전의 REINFORCE update rule은 다음과 같다.

rl-eq13-9

일반적으로 baseline은 update의 예상 value를 변화시키지 않지만, variance에는 큰 영향을 미치게 된다. 어떤 states에서 모든 action이 모두 큰 value를 가지게되면 작은 value를 가진 state와 차별화하기 위해 큰 baseline이 필요하다. 모든 action이 작은 값을 가지는 state에서는 작은 baseline이 필요하다. Baseline을 정하는 자연스러운 방법은 state value \hat{v}(S_t , \boldsymbol{w})를 사용하는 것이며, \boldsymbol{w}는 value function의 weight vector이다. REINFORCE는 policy weights를 학습하는 Monte Carlo method이기 때문에, state-value weight \boldsymbol{w}를 학습하기 위해서도 Monte Carlo method를 사용하는 것이 자연스러울것 같다. baseline을 사용하는 REINFORCE algorithm의 pseudocode는 아래와 같다.

rl-reinforce-with-baseline-algorithm


policy 및 value update에는 step size parameter가 포함된다. policy의 step size parameter는 어떤 의미를 가질까 의문이 들것이다. 이 값이 크면 policy가 더 적극적으로 action probability를 바꾼다는 의미이므로 greedy policy와 같이 움직일것이다.


REINFORCE with baseline for Cliff-walking task

이 Cliff-walking task는 이미 TD methods 포스팅에서 다룬바 있다. 같은 task에 REINFORCE algorithm을 적용하여 얻은 결과를 아래 나타내었다. 앞서 언급한 바와 같이 Monte Carlo based policy gradient method는 variance가 크다.

rl-reinforce-with-baseline-for-cliff-walk

Note) 본 포스팅은 Sutton과 Barto가 공저한 Reinforcement Learning : An Introduction을 기초로 작성된것이다.

Advertisements

Policy Gradient Methods”에 대한 답글 1개

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중