[강화학습 요약] Policy Gradient

Policy-Based RL

- No explicit value function

- 최적의 Policy를 바로 구함

 

특징

- state-action value function을 parameterization이 쉽지 않을 때 쓰기 좋다

- 차원이 많거나 continuous action space 일 때 쓰기 좋다

- stochastic policy를 배울 수 있다

- local optima에 도달하는 경우가 많다

- variance가 크다

 

Policy Gradient

$\tau = (s_0,a_0,r_0,...,s_{T-1},a_{T-1},r_{T-1},s_T)$

$R(\tau) = \sum_{t=0}^{T} R(s_t,a_t)$ (Monte-Carlo return)

$V(\theta) = \sum_\tau P(\tau;\theta)R(\tau)$

 

V(θ)는  π(θ)를 따랐을 때 가능한 모든 trajectory의 reward의 평균이다

V(θ)를 가장 크게 만드는 것이 optimal policy이다

 

Take gradient with respect to θ:

${\begin{align}
\nabla_\theta  V(\theta) &= \nabla_\theta \sum_\tau P(\tau;\theta)R(\tau) \\
          &=  \sum_\tau  \nabla_\theta  P(\tau;\theta)  R(\tau)\\
          &=  \sum_\tau P(\tau;\theta) \frac{\nabla_\theta P(\tau;\theta)}{P(\tau;\theta)} R(\tau) \\
          &=  \sum_\tau P(\tau;\theta) \nabla_\theta log    P(\tau;\theta) R(\tau)
\end{align}}$

 

m-개의 샘플로 approximation하면,

$\nabla_\theta V(\theta) \approx \hat g = (1/m) \sum_{i=1}^m \nabla_\theta log P(\tau^{(i)};\theta) R(\tau^{(i)})$

 

${\begin{align}
\nabla_\theta log P(\tau^{(i)};\theta) &= \nabla_\theta log \mu(s_0)\prod_{j=0}^{T-1}p(s_{j+1}^i|s_j^i,a_j^i)\pi_\theta(a_j^i|s_j^i) \\
&=\nabla_\theta log \mu(s_0) + \nabla_\theta\sum_{j=0}^{T-1}log p(s_{j+1}^i|s_j^i,a_j^i) + \nabla_\theta\sum_{j=0}^{T-1}log \pi_\theta(a_j^i|s_j^i) \\
&= 0+0+\sum_{j=0}^{T-1} \nabla_\theta log \pi_\theta(a_j^i|s_j^i)
\end{align}}$

Policy만 고려해주면 optimal V(θ)를 구할 수 있다

 

$\nabla_\theta log \pi_\theta(a|s)$를 score function 이라고 한다

 

$\nabla_\theta V(\theta) \approx (1/m) \sum_{i=1}^m R(\tau^i)\sum_{t=0}^{T-1} \nabla_\theta log \pi_\theta(a_t^i | s_t^i)$

각각의 sample이 gradient에 기여하고 trajectory의 reward와 length가 다양하므로 variance가 크다

Variance 줄이는 두 가지 방법 : Temporal Structure / Baseline

 

Temporal Structure

action과 state를 시간으로 정렬하는 것(?)

 

위의 식을 정리하자

 

trajectory(τ)에서의 expected reward의 gradient는

$\nabla_\theta \mathbb{E}_\tau [R] = \mathbb{E}_\tau [ \sum_{t=0}^{T-1}r_t \sum_{t=0}^{T-1}\nabla_\theta log \pi_\theta(a_t|s_t)]$

 

time step t'에서의 expected reward의 gradient는

$\nabla_\theta \mathbb{E}[r_{t'}] =\mathbb{E} [r_{t'} \sum_{t=0}^{t'}\nabla_\theta log \pi_\theta(a_t|s_t)]$

intuition : future actions do not change earlier rewards

(t' 이후의 미래의 확률까지 더하지 않아도 된다)

 

time step t'을 0부터 T-1까지 더해주면

${\begin{align}
\nabla_\theta \mathbb{E}_\tau [R] &= \mathbb{E}_\tau [ \sum_{t=0}^{T-1}r_t \sum_{t=0}^{T-1}\nabla_\theta log \pi_\theta(a_t|s_t)] \\
&=\mathbb{E}_\tau [\sum_{t'=0}^{T-1} r_{t'} \sum_{t=0}^{t'}\nabla_\theta log \pi_\theta(a_t|s_t)] \rightarrow  (1)\\
&=\mathbb{E}_\tau [\sum_{t=0}^{T-1}\nabla_\theta log \pi_\theta(a_t|s_t) \sum_{t'=t}^{T-1} r_{t'} ] \rightarrow  (2)
\end{align}}$

(1)에서 (2)로 넘어가는 것은

$log \pi_\theta(a_1|s_1)$는 $r_1$ ~ $r_{T-1}$에 모두 더해지고

$log \pi_\theta(a_{T-1}|s_{T-1})$는 $r_{T-1}$에만 더해지는 것을 생각하면 된다

 

$\sum_{t'=t}^{T-1} r_{t'}$ 는 return이다 ($G_{t'}$)

 

따라서,$\nabla_\theta V(\theta) \approx (1/m) \sum_{i=1}^m \sum_{t=0}^{T-1} \nabla_\theta log \pi_\theta(a_t^i | s_t^i)G_t^i$

 

REINFORCE (Monte-Carlo policy gradient algorithm)

Init(θ)

REPEAT:
    for traj in (s1,a1,r2,...T까지):
        for t in range(1, T):
            θ = θ + α·Gt∇θ log πθ(at|st)

 

Policy로 자주 쓰이는 함수

1. Softmax Policy

- action / space가 discrete 일 때

$\pi(s,a) = e^{\phi(s,a)^T\theta} / (\sum_ae^{\phi(s,a)^T\theta})$

$\phi(s,a)$ : features that can be observed

2. Gaussian Policy

- continuous action spaces 일때

평균은 state features의 linear combination이다

$\mu(s) = \phi(s)^T\theta$
$a \sim N(\mu(s), \sigma ^2)$

 

Monotonic improvement가 필요한 이유

- 자율주행자동차의 경우 V가 오르고 내리기를 반복하고 결론적으로 optima에 도달한다고 하더라도 V가 내려갔을 때 위험이 크다 (high-stakes)

 

Baseline

$\nabla_\theta \mathbb{E}_\tau[R] = \mathbb{E}_\tau [\sum_{t=0}^{T-1} \nabla_\theta log \pi_\theta(a_t | s_t)(G_t-b(s_t))]$

Baseline 보다 얼마나 좋아졌는 지 파악할 수 있다(?)

Baseline은 fixed function으로 input으로 trajectory와 time step을 넣으면 scalar 값이 출력된다

 

baseline이 있더라도 unbias 하다는걸 증명

${\begin{align}
& \mathbb{E}_\tau [ \nabla_\theta log \pi_\theta(a_t | s_t) b(s_t)] \\
&= \mathbb{E}_{s_{0:t},a_{0:(t-1)}}[ \mathbb{E}_{s_{t+1:T},a_{t:(T-1)}} [ \nabla_\theta log \pi_\theta(a_t | s_t) b(s_t)]] decompose - into- two- parts \\
&=\mathbb{E}_{s_{0:t},a_{0:(t-1)}}[b(s_t) \mathbb{E}_{s_{t+1:T},a_{t:(T-1)}} [ \nabla_\theta log \pi_\theta(a_t | s_t) ]] future-timestep-independent \\
&=\mathbb{E}_{s_{0:t},a_{0:(t-1)}}[b(s_t) \mathbb{E}_{a_t} [ \nabla_\theta log \pi_\theta(a_t | s_t) ]] a_t에만 의존한다?? \\
&=\mathbb{E}_{s_{0:t},a_{0:(t-1)}}[b(s_t) \sum_{a_t}\pi_\theta(a_t | s_t) \nabla_\theta log \pi_\theta(a_t | s_t) ]  ???머지 \\
&=\mathbb{E}_{s_{0:t},a_{0:(t-1)}}[b(s_t) \sum_{a_t}\pi_\theta(a_t | s_t) \frac{\nabla_\theta \pi_\theta(a_t | s_t) }{\pi_\theta(a_t | s_t) } ] \\
&=\mathbb{E}_{s_{0:t},a_{0:(t-1)}}[b(s_t)\nabla_\theta \sum_{a_t} \pi_\theta(a_t | s_t) ] \\
&=\mathbb{E}_{s_{0:t},a_{0:(t-1)}}[b(s_t)\nabla_\theta 1 ] \\ 
&=0
\end{align}}$

 

Vanilla Policy Gradient Algorithm

 

REPEAT:
    trajectories = collect_traj_using_policy(π)
    # π = [π_1,π_2,...,]
    for i in range(len(trajectories)):
        $G_t^i = \sum_{t'=t}^{T-1}r_{t'}^i$

        $A_t^i = G_t^i - b(s_t)$

        J = $\sum_i \sum_t || G_t^i - b(s_t) || $ 

        J를 최소화하는 방향으로 baseline 업데이트

        $ \hat g = (1/m) \sum_{i=1}^m \nabla_\theta log P(\tau^{(i)};\theta) A_t$

        g를 SGD 또는 ADAM 하여 update policy 

 

Baseline를 정의하는 방법 중 하나는 V(s)이다.

단, V의 true value를 구하는 것이 불가능하므로 V(s;w)로 정의한다

G를 계산하는 방법 중 하나는 MC나 TD learning나 두 개가 혼합된 형태의 N-step estimator 이다

N-step estimator

$\hat{G_t}^{(1)} = r_t + \gamma V(s_{t+1})$

$\hat{G_t}^{(2)} = r_t + r_{t+1} + \gamma V(s_{t+2})$

...

TD는 bias가 크고 variance가 작다. MC는 bias가 없고 variance가 크다.

N을 잘 선택해서 중간정도의 bias와 variance를 가진 방법을 활용할 수 있다.

위와 같이 V나 Q를 구하는 것을 critic이라고 한다.

actor는 policy improvement를 하고 critic은 policy evaluation이다

 

Update Policy using gradient g

step size를 잘 구하는 것이 중요하다

데이터를 현재의 policy를 통해 구하므로 policy가 너무 좋지 못하면 유용한 데이터를 수집할 수 없다.

 

goal : monotonic improvement

$\tilde{\theta}$ : new policy

${V(\theta) = \mathbb{E}_{\pi_{\theta}}[\sum_{t=0}^{\infty}\gamma^tR(s_t,a_t;\pi_{\theta})]}$

${V(\tilde{\theta}) = V(\theta) + \mathbb{E}_{\pi_{\tilde{\theta}}}[\sum_{t=0}^{\infty}\gamma^tA_{\pi}](s_t,a_t)]}$

(${A_{\pi}(s_t,a_t) = Q^\pi(s,\tilde{\pi}(s))-Q^\pi(s,\pi(s))}$, 새로운 policy가 얼마나 더 좋은 지 측정)

${V(\tilde{\theta}) = V(\theta) + \sum_{s}\mu_{\tilde{\pi}}(s)\sum_{a}\tilde\pi(a|s)A_\pi(s,a)}$

 

$\mu_{\tilde{\pi}}(s)$ : discounted weighted frequency of state

s가 등장하는 확률 계산

${\mu_{\pi}(s) = \sum_{t=0}\gamma^t\mathbb{P}(s_t=s|\pi)}$

 

하지만, off policy 이므로 새로운 policy에 대해서는 아직 sample을 얻지 못했다.

따라서, $\mu_{\tilde{\pi}}(s)$를 알 수 없다

$\mu_{\tilde{\pi}}(s)$ 대신 $\mu_{\pi}(s)$를 쓴다 (이전 policy에 대한 s 분포를 쓴다)

 

${L_\pi(\tilde{\pi}) = V(\theta) + \sum_{s}\mu_{\pi}(s)\sum_{a}\tilde\pi(a|s)A_\pi(s,a)}$

note that) $L_\pi(\pi) = V(\theta)$

 

Lower bound가 존재한다 (왜 그런지는 모르겠음)

V >= L - ??

 

PPO (Proximal Policy Optimization)

step간의 변동 비율이 클 때 패널티를 줘서 큰 변동을 주지 못하게 막는 방법들

 

PPO with Clipped Objective

surrogate ratio : $r_t(\theta) = \frac{\pi_\theta(a_t|s_t)}{\pi_{\theta,old}(a_t|s_t)}$

${L^{clip}(\theta) = \mathbb{E}[\sum_{t=0}^T[ min(r_t(\theta)A_t^{\pi_k},clip(r_t(\theta),1-\epsilon,1+\epsilon)A_t^{\pi_k})]]}$

Lclip에 대해 gradient ascent