Policy Gradient Methods - Newversion

2018-08-05

Policy Gradient Methods

Wonseok Jung

1. Two methods of choosing action

Action을 선택하는 방법에는 Action-value를 기준으로 하는 것과 Parameterized policy를 기준으로 하는것으로 두 가지 방법이 있다.

  • Action-value :
    • Learning the action value
    • Estimate action value을 바탕으로 action을 선택한다.
    • Policies would not even exist without the action-value estimates

  • Parameterized policy :
    • select actions without consulting value function
    • Value function still be used to learn policy parameter
    • Value function이 action을 선택하는 기준으로 사용되지 않는다
    • 여기서 policy $\pi$ 는 neural network가 될 수 있다.
    • pixel 또는 state information등 input이 neural network를 통과해 possible action을 output으로 return 한다.

2.Policy Objective Functions

  1. Policy Objective Functions에 대하여 알아보도록 하겠다.

    Policy Objective Function의 목적은 Parameter $\theta$를 가진 주어진 Policy를 $\pi_{\theta}(s,a)$ 의 가장 좋은 Parameter $\theta$ 를 찾는 것이다.

    Policy $\pi_{theta}$ 를 측정하려면 어떠한 방법이 필요할까?

    2.1 Episodic한 환경 : Episodic한 환경에서는 start value를 사용할 수 있다.

    $J_1 (\theta) = V^{\pi_{\theta}} (S_1) = E_{\pi_\theta} [v1]$

    2.2 Continuing 환경: Average value를 사용할 수 있다.

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

    2.3 Time-step마다의 reward를 average하는 방법

$J_{avR}(\theta) = \sum_s d^{\pi_\theta}(s) V^{\pi_\theta}(s)$

Note 1:

$d^\pi_{\theta}$ : $\pi(\theta)$에 의한 Markov Chain의 stationary distribution

Note 2
Markov chain:

A Markov chain is “a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event”.[[1]

Note 3

Stationary distribution : A stationary distribution of a Markov chain is a probability distribution that remains unchanged in the Markov chain as time progresses (reference :https://brilliant.org/wiki/stationary-distributions/)

3. Polciy Optimization

지금부터 위의 Obejectives를 Optimization 하는 방법에 대해 알아보도록 하겠다. 정확히 말하면 Objective function을 maximize하는 parameter을 찾는 것이다.

$Max {\theta} E [\sum{t=0}^H R(S_t) \mid \pi_{\theta}]$

Optimization을 하는 방법으로는 Gradient based method와 Gradient free method 두 가지로 구분할 수 있다.

Gradient free method :

  • Hill climbing
  • Simplex, Amoeba, nelder Mead
  • Genetic Algorithms

Gradient based method

  • Gradient descent
  • Conjugate gradient
  • Quasi-newton

여기서는 Gradient descent 방법에 대하여 자세히 알아보도록 하겠다.

4. Policy Optimization

$J(\theta)$를 policy의 objective function이라고 해보자.

우리는 이 Object function $J(\theta)$ 을 통하여 받는 reward를 maximize하는 parameter를 찾으려는게 목적이며,

그렇기 떄문에 parameter의 Gradient descent가 아닌 Gradient ascent를 구해야하 한다.

$\triangle \theta = \alpha \triangledown_{\theta}J(\theta)$

위의 식에서 $\alpha$는 step size이며, $\triangledown_{\theta} J(\theta)$는 Policy gradient 이다.

Policy gradient는 partial derivative 이다.

Note 1

Gradient descent : Gradient descent is a first-order iterative optimization algorithm for finding the minimum of a function. To find a local minimum of a function using gradient descent, one takes steps proportional to the negative of the gradient (or approximate gradient) of the function at the current point. If instead one takes steps proportional to the positive of the gradient, one approaches a local maximum of that function; the procedure is then known as gradient ascent.

Note2

Gradient ascent : If instead one takes steps proportional to the positive of the gradient, one approaches a local maximum of that function; the procedure is then known as gradient ascent.

Note 3

  • gradient descent aims at minimizing some objective function: $\theta_j \leftarrow \theta_j - \alpha \triangledown J(\theta) $
  • gradient ascent aims at maximizing some objective function: $\theta_j \leftarrow \theta_j + \alpha \triangledown J(\theta) $

5. Likelihood Ratio Policy Gradient

$\tau$는 state-action 의 sequence로 정의한다. ${s_0, a_0, s_1,a_1 …… s_T, u_T}$ 위와같이 state 에서 action을 선택하며 받은 reward의 총 합을 다음과 같이 정의할 수 있다.

$R(\tau) = \sum_{t=0}^H R(s_t, a_t)$

Parameter $\theta$ 를 따른 Policy $\pi$ 에 의해 선택된 sequence $\tau$ 는 다음과 같이 정의한다.

$J(\theta) = E [ \sum_{t=0}^H R(s_t, a_t) ; \pi_{\theta}] = \sum_{\tau} P(\tau ; \theta) R(\tau)$

Reinforcement Learning에서는 episode동안 받을수 있는 총 reward를 최대화 시키는 것이 목표이기 때문에,

Parameter $\theta$ 를 따른 Policy $\pi​$ 에 의해 선택된 sequence $\tau​$ 를 최대화 하는 Parameter $\theta​$ 를 찾는것이 목표이다!

$max_{\theta} J(\theta) =max_{\theta} \sum_{\tau} P(\tau ; \theta) R(\tau)$

$J(\theta) = E [ \sum_{t=0}^H R(s_t, a_t) ; \pi_{\theta}] = \sum_{\tau} P(\tau ; \theta) R(\tau)$ 식의 parameter $\theta$ 에 의해 gradient를 전개해보면 다음과 같다.

$\bigtriangledown J(\theta) = \bigtriangledown_{\theta} \sum_{\tau} P(\tau ; \theta)R(\tau)$

$= \sum_{\tau} \bigtriangledown_\theta P(\tau ; \theta)R(\tau)$

Probability of Trajectory under theta를 $\frac{P(\tau ; \theta)}{P(\tau ; \theta)} $ 형태로 추가

$= \sum_{\tau} \frac{P(\tau ; \theta)}{P(\tau ; \theta)} \bigtriangledown_\theta P(\tau ; \theta)R(\tau)$

$= \sum_{\tau} P(\tau ; \theta) \frac{\bigtriangledown_\theta P(\tau ; \theta)}{P(\tau ; \theta)}R(\tau)$

$= \sum_{\tau} P(\tau ; \theta) \bigtriangledown _{\theta} log P(\tau ; \theta) R(\tau)$

이렇게 변환된 식을 통하여 polcy $\pi_{\theta}$ 를 따른 Sample path m 개 만큼의 estimate of the policy gradient는 다음과 같이 정의할 수 있다.

$\bigtriangledown_{\theta} J(\theta) \approx \hat{g} = \frac{1}{m} \sum_{i=1}^m \bigtriangledown_{\theta} log P(\tau^{(i)} ; \theta)R(\tau^{(i)})$

위와같은 Likelihood Ratio Gradient는 Roll out을 통해 경험을 하며 postive reward 의 pat의 확률을 increase 시키며 negative Reward path의 확률을 감소 시킨다.

$\bigtriangledown_{\theta} log P \left [ (\tau^{(i)} ; \theta) = \bigtriangledown_{\theta} log \prod_{t=0}^{H} P(s^{(i)}{t+1} \mid s{t}^{(i)}a_t^{(i)})\times \pi_{\theta} (a_t^ \mid s_t^{(i)}) \right ]$

Parameter $\theta$에 는 Gradient를 하지 않으므로 Dynamics model 부분을 없앨수 있고, 그러므로 우리는 Likelyhoold Ratio Graident에서 Dynamics model을 알지 못하여도 사용할 수 있다.

Note 1

Score function

Intuitively it can be thought of as describing the direction in which we should change θ in order to maximize the likelihood. So if we for example have θ = {μ, Σ}, then the score function will tell us how to change μ and Σ in order to maximize the likelihood.In the case of a NN, we would instead get a measure of how we should change each weight w.

(reference : https://aboveintelligent.com/deep-learning-basics-the-score-function-cross-entropy-d6cc20c9f972)

  1. 6. Likelihood Ratio Gradient Estimate

위의 Likelihood Ratio Gradient Estimate는 unbiased하지만 noisy가 많다.

$\bigtriangledown_{\theta} J(\theta) \approx \hat{g} = \frac{1}{m} \sum_{i=1}^m \bigtriangledown_{\theta} log P(\tau^{(i)} ; \theta)R(\tau^{(i)})$

이것을 해결하기 위해서 실제로는 다음의 방법을 사용한다.

  1. Baseline
  2. Temporal structure
  3. KL-divergence trust region/ natural gradient

위의 방법을 어떻게 사용하는지 하나씩 알아보도록 하자. (3번은 다음 글에)

먼저 위의 예제에서 세번의 path를 roll out한 예제를 보았다.

이 예제에서 세개의 roll out path가 모두 positive하다면?

Positive reward를 받은 path의 확률을 높이고, Negative reward를 받은 path의 확률을 낮추려는 gradient의 특징으로 인해

likelyhood RatioGradient는 세개의 roll out path 모두의 probability를 높이려고 할것이다.

하지만 이 path 중에서는 더 좋은것도 있고 덜 좋은것도 잇을 것이다.

이것을 어떻게 알수 있을까?

  • BaseLine

단순히 postive 할때 높여주고, negative면 낮춰주는 방법을 사용하지 않고 어떠한 baseline(기준점)을 설정하여서 rollout 했을때의 path가 기준점보다 높으면 그 확률을 높여주고 그 path보다 낮다면 확률을 낮춰주는 방법을 사용하기도 한다.

정의는 아래와같이 할 수 있다.

Original equation : $\bigtriangledown_{\theta} J(\theta) \approx \hat{g} = \frac{1}{m} \sum_{i=1}^m \bigtriangledown_{\theta} log P(\tau^{(i)} ; \theta)R(\tau^{(i)})$

Consider base line b : $\bigtriangledown_{\theta} J(\theta) \approx \hat{g} = \frac{1}{m} \sum_{i=1}^m \bigtriangledown_{\theta} log P(\tau^{(i)} ; \theta)R(\tau^{(i)}- b)$

위의 방법은 williams가 1992년에 수학적으로 이 방법을 통하여 variance를 줄일 수 있다는 것을 증명하였다.

Temporal Structure

조금 더 나아가서 baselin을 적용한 식에 current time step $t$

Baseline은 average를 하는 방법뿐만 아닌 다음과 같이 여러가지 방법이 있다.

  • 여기서 notation $u_t$는 $a_t$와 같다.

마지막 방법인 state-dependen expected return을 baseline으로 했을때 State $s_t$에서 policy $\pi$에 따라 받을수 있는 expected return과 비교를 하는것이 가능해진다.

이 방법에 대해 조금 더 자세히 알아보도록 하자.

7. Estimation of $V_\pi$

$\frac{1}{m} \sum_{i=1}^m \bigtriangledown_{\theta} log P(\tau^{(i)} ; \theta)R(\tau^{(i)}- b)$

위의 LikelihoodRatio Gradient 식을 다음과 같이 정의할 수 있다.

여기서 $V_\pi (s_k^i )$를 어떻게 정의할 수 있을까?

Policy $\pi$를 따른 state value $V$를 생성하는 neural network를 만들어서 supervised learning에서와 같이 이 network를 다음의 식으로 parameter를 optimize 해준다.

위와같이 $V_\pi$와 time step $t$ 부터 Terminal state까지의 총 Reward의 합의 차이를 mimize하는 parameter $\phi$ 를 찾아 update 해준다.

위와같이 Value of $V$를 Monte calro estimation 으로 측정하는 것이 아닌 Bellman equation 을 사용하여 State value $V$를 구하는 방법도 있다.

위와 마찬가지로 parameter를 optimize하지만 $V_\theta^\pi(s)$ 가 아닌 $r+V_\theta^\pi(s’)$를 target 으로 parameter 를 update한다.

위의 방법을 사용한 poilcy gradient 방법을 Vanilla Policy Gradient 라고 하며 pseudo code는 다음과 같다.