ByungSunBae/PolicyGradient.markdown

## PolicyGradient.markdown

      
    Raw
  

              PolicyGradient.markdown
            
          
    DRL : Policy Gradient

Overview


Deep Q network(이하 DQN)와 그 Variants(DoubleDQN, DuelingDQN)를 구현해보았다.


그런데 DQN과 같은 계열의 방법은 RL에서 Value-Based Method라서 Policy에 대한 직접적인 학습이 아니다.


게다가 Value가 약간만 바뀌어도 Policy가 금방 변한다.

학습과정이 불안정하게되어 수렴자체가 불안정해진다. (Bias가 높다.)


Policy에 대해 직접적으로 학습하는 방법은 없을까?

그게 바로 Policy Gradient다!!


그렇다면 Policy Gradient라는 이름에서 Policy와 Gradient는 각각 어떤 의미로 합쳐졌을까?


Review DQN


DQN에 대해서 다시 한번 살펴보자


Q-learning은 Model Free한 학습이 가능하므로써, DQN은 Convolutional Neural Network을 이용하여 Q value를 근사시킨다.


물론 Q value를 근사시키고 난 후에 여러 과정들이 있지만 알고리즘 부분이기 때문에 굳이 설명하지 않겠다.


DQN이 어떤 method 계열인지를 살펴보자.


DQN은 Value Based method로 Temperal Difference learning에 Off-policy를 더하여 학습을 하였다.


Temperal Difference(이하 TD)는 Monte Carlo Method + Dynamic Programming 이라는데 솔직히 깊게는 이해하지 못했다.


다만 Monte Carlo Method(이하 MC)는 1개의 에피소드를 끝까지 시행 후 거기서 얻어진 state(S), action(A), reward(R)를 가지고, 다음과 같이 각 시점별로 미래의 rewards의 합을 구하여 학습에 이용한다.

random sample의 return값의 평균을 이용하여 예측하는 방법을 MC method라 한다.
random sample이기 때문에 variance가 높다.

  
$$G_{t} = R_{t+1} + \gamma R_{t+2} + ... + \gamma^{T-1} R_{T-1}$$


단, t는 각 시점 (1, 2, 3, ... ), T는 state가 종료되는 시점


그리고 Dynamic Programming(이하 DP)은 과거에 학습한 추정치를 사용하여 현재의 추정치를 구하는 방법(called "Boostrap")이다.

Policy Iteration, Value Iteration 등이 대표적인 방식이다. (Bellman Equation 이용)

  
기댓값을 계산할 때, 현재 state에서 다음 state로 넘어갈때에 대한 확률값이 필요하다.

즉, Environment(환경)을 Agent가 전부 다 알아야하는 Model Based 방법이다.


그렇다면, TD는 이 2개의 조합이니 V를 업데이트 할때 왼쪽 식이 약간 달라질거라고 예상할 수 있다.


MC에서 업데이트 할때 사용했던 Gt가 DP에서 사용된 reward + discounted_factor * V로 바뀌었다.
  

위에서 빨간색으로 칠해진 term을 TD target, delta를 TD error라 부른다.

이는 DQN에서 V를 Q로 바꾸어서 보면 다음과 같다.

  
즉, Deep Q Network는 TD learning을 이용하였으며 Q value는 CNN으로 근사시키고 MSE Loss의 미분값이 TD error에 대응된다.

그리고 위 그림에서 빨간색글씨로 Target이라고 지칭하는 것이 TD Target에 대응된다.
학습할때는 Gradient Descent 방법으로 Loss를 최소화하는 방향으로 CNN의 parameters를 업데이트한다.


TD, MC, DP 등에 좀더 자세히 알고 싶다면 http://courseprojects.souravsengupta.com/cds2016/reinforcement-learning/ 를 참조..


그리고 DQN에서 실제로 학습시킬 때 Replay Memory와 Target Network를 이용해서 안정적인 학습을 도모하였다.


DQN은 이쯤에서 그만 설명하고, 이제 Policy Gradient에 대해 살펴보겠다.


Policy Gradient


1) Value-Based RL vs Policy-Based RL


Value-Based RL은 value function의 근사값을 사용하여 그 값을 가장 크게하는 action을 선택하게끔한다.

그래서 거의 deterministic하게 행동한다.
예를 들어, "가위 바위 보"에서 계속 가위만 내게 될수 있다.


반면에 Policy-Based RL은 policy 자체를 예측한다. (Policy의 의미)

action을 정할 때, 각 action별로 확률값에 의해 stochastic하게 policy를 결정한다.

물론 높은 확률을 가진 action이 선택되는 경우가 많다.
하지만 그렇다고 다른 action들을 아예 선택하지 않는게 아니다!!


예를 들어, "가위 바위 보"에서 가위도 내고 가끔 바위와 보도 낼 수 있다.

가위를 낼 확률 : 0.5, 바위를 낼 확률 : 0.3, 보를 낼 확률 : 0.2
이런 경우 무조건적으로 가위를 내는게 아니라 가끔 바위와 보를 낼 수도 있다.


"가위 바위 보"와 같은 게임에서는 stochastic policy가 필요한데 Policy-Based RL은 최적의 stochastic policy를 학습할 수 있다.

DQN처럼 Policy를 parameterize하여 최적의 stochastic policy를 찾는 문제를 best parameters를 찾는 문제로 변형가능하다.


2) Policy Objective Functions


목표 : parameterized policy가 주어졌을때, 가장 좋은 parameters를 찾자!


그런데 한 policy의 quality를 어떻게 측정할 수 있을까?


episodic environments에서 우리는 다음과 같은 start value를 사용할 수 있다.


$$ J_{1}(\theta) = V^{\pi_{\theta}}(s_{1}) = E_{\pi_{\theta}}[v_{1}] $$

continuing environments에서 우리는 다음과 같은 average value를 사용할 수 있다.

$$ J_{avV}(\theta) = \Sigma_{s} d^{\pi_{\theta}}(s) V^{\pi_{\theta}}(s) $$

혹은 time-step마다 average reward를 사용할 수 있다.

$$ J_{avR}(\theta) = \Sigma_{s} d^{\pi_{\theta}}(s) \Sigma_{a} \pi_{\theta}(s,a)R_{s}^{a} $$

이때, $d^{\pi_{\theta}}(s)$ 는 $\pi_{\theta}$에 대한 Markov chain의 stationary distribution이다.


3) Policy Optimisation


Policy-Based RL은 최적화 문제이다.


즉, $J(\theta)$를 최대로하는 $\theta$를 찾아야한다.


gradient를 사용하지 않은 optimization

Hill climbing
Simplex / amoeba / Nelder Mead
Genetic algorithms


gradient를 사용한 optimization

Gradient descent (Gradient의 의미)
Conjugate gradient
Quasi-newton


여기까지 살펴보면서 Policy Gradient가 왜 Policy Gradient인지를 한번 이야기 해보면 다음과 같다.

Policy는 말그대로 어떻게 action을 취할지에 대한 확률을 직접적으로 예측하자는 의미
Gradient는 Policy를 Optimization하기 위해 Gradient를 이용하는 것을 의미
참 직관적이다...ㅎㅎㅎ


4) Policy Gradient


$J(\theta)$를 어떤 policy objective function이라 하자.


Policy gradient 알고리즘은 $J(\theta)$에서 $\theta$ 관점에서 policy의 미분값이 커지는 방향으로 local maximum을 찾는다.


$\Delta\theta = \alpha \nabla_{\theta} J(\theta)$
  
  
$\nabla_{\theta} J(\theta)$는 policy gradient의 미분값이다.


$$\nabla_{\theta} J(\theta) =
\begin{bmatrix} \frac{\partial J(\theta)}{\partial \theta_{1}}
\ .
\ .
\ .
\ \frac{\partial J(\theta)}{\partial \theta_{n}}
\end{bmatrix} $$

그리고 $\alpha$는 step-size parameter이다. (결국 learning rate ..)


5) Monte Carlo Policy Gradient(이하 MCPG)


지금까지 Policy Gradient에 대해서 어느정도 살펴봤다.


그런데 어떻게 Policy Gradient를 통해서 학습을 시키겠다는 것인지 많이 와닿지 않을 것이다.


예를 들어, $J(\theta)$가 objective function이라 했는데, 이 $J(\theta)$는 어떻게 생겼으며 그 미분값의 형태도 어떻게 생겨먹었는지를 모른다...


action space가 연속형일때와 이산형일때 어떤 차이가 있는지도 모른다.


그리고 위에서 얘기되는 $\pi_{\theta}(s,a)$와 $R_{s}^{a}$는 어떻게 처리해야 하는지조차 감이 안온다.


그래서 5번째 MCPG에서 이야기 할 것은 다음과 같다.


$J(\theta)$가 어떻게 생겼는가?
Action space가 연속형일때와 이산형일때 어떤 차이가 있을까?

$\pi_{\theta}(s,a)$와 $R_{s}^{a}$는 어떻게 처리해야 하는가?
결국 Monte Carlo Policy Gradient라는 것은 무엇인가?


$J(\theta)$를 알아보기 위해 먼저 Score Function부터 살펴보자.


Score Function

Policy $\pi_{\theta}$ 가 0이 아닌 값으로써 미분가능하며,
미분값인 $\nabla_{\theta} \pi_{\theta}(s,a)$을 알고있다고 하자.
우리는 Likelihood Ratios(LR)를 얻을 수 있다. (일종의 trick을 써서 LR을 만든것임..)


$$\nabla_{\theta} \pi_{\theta}(s,a) = \pi_{\theta}(s,a) \frac{\nabla_{\theta} \pi_{\theta}(s,a)}{\pi_{\theta}(s,a)} = \pi_{\theta}(s,a) \nabla_{\theta} log\pi_{\theta}(s,a)
$$


위식에서 Score function인 $\nabla_{\theta} log\pi_{\theta}(s,a)$를 얻을 수 있다.


Action Space


우리가 가지고 있는 state feature를 $\phi(s,a)$라하고,


linear combination 형태인 $\phi(s,a)^{\top} \theta$를 사용하여 action에 가중치를 준다.


이산형일때, Softmax를 이용해서 Policy를 계산할 수 있다.

각 action에 대한 확률로 일종의 가중치로 보면된다.
그 확률값을 기반으로 어떤 action을 취할지 선택(stochastic policy)
이에 대한 score function은 다음과 같다. (실제 구현할때는 softmax function에 log를 취한 후 미분한 값을 사용한다.)
$\nabla_{\theta} log\pi_{\theta}(s,a) = \phi(s,a) - E_{\pi_{\theta}}[\phi(s,.)]$


연속형일때, Gaussian(정규분포)를 이용해서 Policy를 계산한다.

평균은 linear combination 형태인 $\mu(s) = \phi(s,a)^{\top} \theta$ 이다.
분산은 $\sigma^{2}$로 고정되거나 parameterised 될수 있다.
Policy는 Gaussian, $a \sim N(\mu(s), \sigma^{2})$

이에 대한 score function은 다음과 같다.
$\nabla_{\theta} log\pi_{\theta}(s,a) = \frac{(a - \mu(s)) \phi(s)}{\sigma^{2}}$


One-Step MDPs

one-step MDPs를 고려하자.

state s에서 시작, $s \sim d(s)$

1 step이 지나면서 reward $r = R_{s,a}$를 받고 종료


Policy gradient를 계산하기 위해 Likelihood Ratios를 사용한다.


$$ \begin{aligned}
J(\theta)
& = E_{\pi_{\theta}}[r] \\
& = \Sigma_{s \in S} d(s) \Sigma_{a \in A} \pi_{\theta}(s,a) R_{s,a}
\end{aligned}$$
$$ \begin{aligned}
\nabla_{\theta} J(\theta)
& = \Sigma_{s \in S} d(s) \Sigma_{a \in A} \nabla_{\theta} log\pi_{\theta}(s,a) R_{s,a} \\
& = E_{\pi_{\theta}}[\nabla_{\theta} log\pi_{\theta}(s,a) r]
\end{aligned}$$


그런데 갑자기 One-Step MDPs가 왜 나왔을까?

1 step만 있기 때문에 위에서 Gradient를 구할 때 간단하게 표현가능
먼저 간단한 표현을 보고나서 어떤 정리를 보기 위함이다.
그게 바로 Policy Gradient Theorem인데 One-Step MDPs가 아닌 Multi-Step MDPs로 LR 접근법을 일반화한 것이다.(뭔말이여...)


Policy Gradient Theorem


One-Step MDPs에서 사용된 즉각적인 reward $r$을 long term value인 $Q^{\pi}(s,a)$로 대체한다.


그리고 여기서는 위에서 언급한 것처럼 Multi-Step MDPs에 대한 LR 접근법을 일반화하였다.


Policy Gradient Theorem은 시작 state objective, 평균 reward, 그리고 평균 value objective에 적용된다.


임의의 미분가능한 Policy $\pi_{\theta}(s,a)$와 임의의 Policy objective functions $J = J_{1}, J_{avR}$ 또는 $\frac{1}{1-\gamma} J_{avV}$에 대해서 policy gradient는 다음과 같다.


$$\nabla_{\theta} J(\theta) = E_{\pi_{\theta}}[\nabla_{\theta} log\pi_{\theta}(s,a) Q^{\pi_{\theta}}(s,a)]$$


Algorithm of MCPG


stochastic gradient ascent에 의해 parameters를 업데이트


Policy Gradient Theorem을 사용


$Q^{\pi_{\theta}}(s,a)$ 의 비편향된 sample로써 return $v_{t}$를 사용

$\Delta\theta_{t} = \alpha \nabla_{\theta} log\pi_{\theta}(s_{t},a_{t}) v_{t}$


실제 알고리즘은 아래와 같다.


$\theta$를 임의적으로 초기화


각각의 에피소드에서 {$s_{1}, a_{1}, r_{2}, ..., s_{T-1}, a_{T-1}, r_{T}$} ~ $\pi_{\theta}$ 를 시행


(1) $t = 1$ 부터 $T-1$ 까지 다음과 같이 $\theta$를 업데이트

$\theta \leftarrow \theta + \alpha \nabla_{\theta} log\pi_{\theta}(s,a) v_{t}$


이렇게 알고리즘을 써놓고 보면 이것만 보고 구현할때 엄청난 멘붕이 올 수 있다.


나름대로 첨언을 하자면,


$v_{t}$는 $r_{t+1} + \gamma r_{t+2} + ... + \gamma^{T-1} r_{T-1}$ 로써 $Q^{\pi_{\theta}}(s,a)$에 대한 비편향 추정치정도로 받아들이면 된다.

시점마다 미래에 대한 rewards의 합을 사용 ($\gamma$는 discounted factor)


action을 선택할 때, Epsilon-Greedy를 쓰면 안된다!!

각 action에 대한 확률값을 기반으로 하여 sampling 되게끔 구현해야한다.(python libraries 중 numpy의 random.choice 함수 참고)


Action이 discrete한 경우 One-Hot encoding으로 표현하고 Deep Learning 모델에 의해 추정된 확률값들에 Log를 취한뒤 $v_{t}$를 곱하여 Objective function을 만든다.
그런데 Objective function를 maximizing 해야한다고 되어있는데 구현시에는 -1을 곱해서 부호를 반대로 하여 minimizing하게끔 구현하면 된다.


다른 방법들

Monte Carlo method가 아닌 다른 방법이 2가지가 있다.

Finite Difference Policy Gradient
Actor-Critic Policy Gradient


아직 위 2가지에 대해서 이해를 잘 못했기 때문에 본 문서에서는 기재하지 않았다..ㅠㅠ


6) Policy Gradient의 장단점


장점

더 나은 Convergence 성질을 가지고 있다.
action이 많거나 연속적인 action space에 대해서 효과적이다.
stochastic policies를 학습할 수 있다.


단점


Global optimum보다 Local optimum에 수렴한다.


Policy를 evaluating하는 것이 비효율적이고 variance가 높다.

Monte Carlo method를 통해서 episodic하게 학습을 시킨다.
1개의 episode가 끝날때까지 action을 하고 끝난 후에 학습을 하기 때문에 학습속도가 늦을 수 밖에 없다.
variance가 높은 이유는 stochastic한 policy 때문에 원래 optimal한 action을 하지 않고 다른 action을 할 확률도 존재하기 때문이다.