[RL] 강화학습 알고리즘: (5) PPO

---

PPO (Proximal Policy Optimization)는 2017년도 OpenAI에서 공개한 논문으로 이전 TRPO (Trust Region Policy Optimization) 알고리즘을 실용적으로 발전시킨 논문입니다. Policy gradient 계열의 알고리즘으로 성능이 우수하면서도 구현이 간단하여 performance와 complexity의 밸런스가 잘 잡힌 알고리즘으로 알려져 있습니다.

 

Motivation

PPO와 TRPO는 동일한 motivation을 가지고 있습니다. 주어진 데이터를 가지고 현재 policy를 최대한 큰 step만큼 빠르게 향상시키면서, 그렇다고 성능이 발산해버릴 정도로 너무 큰 step으로 업데이트 하는 것은 억제하고자 합니다. TRPO와 PPO의 최적화식을 비교해보면 다음과 같습니다.

 

$$ \begin{align} \small\text{TRPO:}~~~~ \normalsize\text{maximize}_{\theta}~~&\hat{\mathbb E}_t\left[\frac{\pi_\theta(a_t|s_t)}{\pi_\text{old}(a_t|s_t)}\hat{A}_t-\beta~KL[\pi_\text{old}(\cdot|s_t)~||~ \pi_\theta(\cdot|s_t)]\right] \\\\ \small\text{PPO:}~~~~ \normalsize\text{maximize}_{\theta}~~ &\hat{\mathbb E}_t\left[\min\!\left(\frac{\pi_\theta(a_t|s_t)}{\pi_\text{old}(a_t|s_t)}\hat{A}_t,~~\text{clip}\!\left(\frac{\pi_\theta(a_t|s_t)}{\pi_\text{old}(a_t|s_t)}, 1-\epsilon, 1+\epsilon\right)\!\hat{A}_t\right)\right] \end{align} $$

 

TRPO에서는 objective term $\frac{\pi_\theta(a|s)}{\pi_\text{old}(a|s)}\hat{A}_t$을 최대화하면서 penalty term $KL[\pi_\text{old}||\pi_\theta]$를 최소화 하는 것을 목표로 합니다. 즉 목적식을 통해 policy의 improvement step을 최대한 크게 가져갑니다. 동시에 penalty term은 old policy와 new policy의 차이가 너무 크게 변경되지 않도록 KL divergence를 통해 제한하는 역할을 합니다.

 

PPO에서 objective term $\frac{\pi_\theta(a|s)}{\pi_\text{old}(a|s)}\hat{A}_t$을 최대화 하는 부분은 TRPO와 동일하며, penalty term에서 KL divergence을 사용하는 대신 clipping 방식으로 변경하였습니다. 이를 통해 second-order method가 아닌 first-order method로 계산이 가능해져 구현적으로 실용적이게 되었습니다.

 

Figure 1. TRPO에 사용되는 Trust region method

 

1) Surrogate Objective

Policy gradient 알고리즘은 목적 함수 $J(\pi_\theta)$를 최대화하기 위해 policy gradient $\nabla J$ 방향으로 정책 $\pi_\theta$를 업데이트합니다. 목적 함수를 어떻게 정의했는지에 따라 policy gradient는 다양하게 표현할 수 있으며 advantage $A_{\pi_\theta}$를 이용한 목적 함수는 다음과 같습니다.

 

$$ J(\pi_\theta)=\mathbb E_{s\sim\rho_{\pi_\theta},~a\sim\pi_\theta}[A_{\pi_\theta}]=\sum_s \rho_{\pi_\theta}(s)\sum_a \pi_\theta(a|s)A_{\pi_\theta}(s,a) $$

 

$\rho_{\pi_\theta}(s)=P(s_0=s)+\gamma P(s_1=s)+\gamma^2 P(s_2=s)+\cdots$ 는 discounted visitation frequencies로 state가 $s$를 방문할 확률을 의미합니다. 여기서 $\pi_\text{old}\rightarrow\pi_\theta$로 policy가 충분히 작은 만큼만 업데이트 된다면, $\rho_{\pi_\theta}(s)$를 $\rho_{\pi_\text{old}}(s)$로 대체할 수 있고 이를 surrogate objective $L(\pi_\theta)$라고 하겠습니다.

 

$$ \begin{align} J(\pi_\theta)&=\sum_s \rho_{\pi_\theta}(s)\sum_a \pi_\theta(a|s)A_{\pi_\theta}(s,a) \\ L(\pi_\theta)&=\sum_s \rho_{\pi_\text{old}}(s)\sum_a \pi_\theta(a|s)A_{\pi_\theta}(s,a) \end{align} $$

 

따라서 policy가 충분히 작은 만큼만 변화하였을 때는 $J(\pi_\theta)$ 대신 $L(\pi_\theta)$을 이용하여 최적화를 수행해도 동일한 결과를 얻을 수 있습니다. 이를 위해 policy update에 대한 제약 조건이 추후 penalty term으로 추가되게 됩니다.

 

2) Importance Sampling

위 식에서 sample 기반 추정을 위해 surrogate objective를 expectation으로 표현하고, importance sampling을 활용하여 식을 변형하면 아래와 같이 나타낼 수 있습니다. (※ Importance sampling 포스팅 참고)

 

$$ \begin{align} L(\pi_\theta)&=\mathbb E_{s\sim\rho_{\pi_\text{old}},~a\sim\pi_\theta}\left[A_{\pi_\theta}(s,a)\right] \\ &=\mathbb E_{s\sim\rho_{\pi_\text{old}},~a\sim\pi_\text{old}}\left[\frac{\pi_\theta(a|s)}{\pi_\text{old}(a|s)}A_{\pi_\theta}(s,a)\right] \end{align} $$

 

Importance sampling을 통해 기존 policy $\pi_\text{old}$로부터 생성된 sample들을 이용하여 업데이트 된 policy $\pi_\theta$를 평가할 수 있습니다. 즉 새로 업데이트된 policy를 평가할 때마다, 새로운 sample을 생성할 필요 없이 old policy로부터 생성된 sample을 재사용할 수 있다는 의미입니다. $\hat{\mathbb E}_t[\cdots]$가 sample 기반 평균을 의미할 때 위 식은 아래처럼 표현할 수 있습니다.

 

$$ L(\theta)=\hat{\mathbb E}_t\left[\frac{\pi_\theta(a_t|s_t)}{\pi_\text{old}(a_t|s_t)}\hat{A}_t\right] $$

 

Importance sampling으로 인해 PPO는 한번의 episode에서 획득한 sample들을 여러번 재사용하여 policy를 업데이트할 수 있습니다.

 

3) Clipping

Policy의 과도한 업데이트를 막기위해 PPO 논문은 clipping과 adaptive KL penalty 두가지 방식을 제안하지만, 일반적으로 clipping 방식이 널리 알려져 있어 이를 정리해 보도록 하겠습니다. 

 

Surrogate objective에서 $r_t(\theta)=\frac{\pi_\theta(a_t|s_t)}{\pi_\text{old}(a_t|s_t)}$로 치환할 수 있고, 이는 특정 action을 취할 old policy와 new policy의 확률 비율을 의미합니다. 그렇기 때문에 policy가 업데이트 되지않아 $\pi_\theta=\pi_\text{old}$ 인 경우, $r_t(\theta)=1$이 성립하게 됩니다. 

 

Clipping은 $r_t(\theta)$를 $[1-\epsilon,1+\epsilon]$ 사이로 제한하여, policy가 업데이트되어도 특정 action을 수행할 확률이 너무 급격하게 증가하거나, 감소하는 것을 억제하고자 하며 수식적으로는 $\text{clip}(r_t(\theta),1-\epsilon, 1+\epsilon)$으로 표현됩니다.

 

$$ L^\text{CLIP}(\theta)=\min\!\left(r_t(\theta)\hat{A}_t,~~\text{clip}\!\left(r_t(\theta), 1-\epsilon, 1+\epsilon\right)\!\hat{A}_t\right) $$

 

Clipping은 최종적으로는 위 수식처럼 $\text{clip}(r_t(\theta),1-\epsilon, 1+\epsilon)$와 $r_t(\theta)\hat{A}_t$ 중 더 작은 값을 선택합니다. 그 결과로 advantage가 양수일때는 $1+\epsilon$, 음수일때는 $1-\epsilon$에 의해서만 clipping이 발생합니다. 아래의 [그림 1]은 advantage의 부호에 따른 clipping 효과를 나타낸 예시입니다.

 

Figure 2. Advantage 부호에 따른 ratio $r$과 surrogate objective $L^\text{CLIP}$의 관계

$L^\text{CLIP}$은 PPO가 최대화하고자 하는 목적 함수입니다. $A>0$일 때는 $r$를 증가시키는 것이 좋은 action을 선택할 확률을 강화시키는 것이므로 $L^\text{CLIP}$가 증가하며, $A<0$일 때는 $r$를 감소시키는 것이 나쁜 action을 선택할 확률을 약화시키는 것이므로 $L^\text{CLIP}$가 증가합니다. 여기에서 PPO는 $A>0$일 때는 $1+\epsilon$으로 $r$을 clipping, $A<0$일 때는 $1-\epsilon$으로 $r$을 clipping 해줌으로써, 한번에 너무 많은 $L^\text{CLIP}$이 증가하는 방향으로 policy가 업데이트되는 것을 피하고자 합니다.

 

4) GAE (Generalized Advantage Estimation)

Trajectory로부터 추정된 기존의 advantage는 high variance error를 가지고 있습니다. PPO에서는 기존 advantage의 variance를 낮추기 위해 GAE(Generalized Advantage Estimation)의 truncated 버전을 사용합니다.

 

$$ \begin{align} \small\text{Advantage function}~~~~ \normalsize &\hat{A_t}=-V(s_t)+r_t+\gamma r_{t+1}+\cdots+\gamma^{T-t+1}r_{T-1}+\gamma^{T-t}V(s_T) \\\\ \small\text{(Truncated) GAE}~~~~ \normalsize &\hat{A_t}=\delta_t+(\gamma\lambda)\delta_{t+1}+\cdots+(\gamma\lambda)^{T-t+1}\delta_{T-1} \\ &\text{where}~~~~ \delta_t=r_t+\gamma V(s_{t+1})-V(s_t) \end{align} $$

 

GAE는 파라미터 $\lambda$의 조절을 통해 bias-variance 사이의 trade-off를 조절할 수 있습니다 ($\lambda=0$일 때 high-bias/low-variance이며, $\lambda=1$일 때 low-bias/high-variance). GAE에 대한 구체적인 내용은 해당 논문 [3]을 참고 바랍니다.

 

PPO 알고리즘

위 설명을 바탕으로 논문의 PPO 알고리즘을 살펴보면 아래와 같습니다.

Figure 2. PPO 알고리즘

PPO는 environment와의 상호작용 시 한 번의 step만 진행해야만 할 필요가 없으며, 고정된 길이의 trajectory (또는 episode) 단위로 상호작용 할 수 있습니다. 또한 여러 actor를 병렬적으로 수행시켜 sample들을 획득할 수 있습니다. 따라서 첫번째 과정으로는 $N$개의 actor가 environment와 상호작용하여 $T$ timesteps 길이의 sample을 획득하게 됩니다.

 

결과적으로 $NT$개의 timesteps 데이터가 수집되며 이를 바탕으로 surrogate objective를 계산합니다. PPO는 importance sampling으로 인해 surrogate objective를 최적화하기 위한 파라미터 업데이트를 $K$ epochs 만큼 반복하여 수행할 수 있습니다. 한 번의 iteration이 끝나면 다시 environment와 상호작용을 수행하여 위의 과정을 반복하게 됩니다.

 

References

[1] J. Schulman et al., "Trust Region Policy Optimization," arXiv, 2015.

[2] J. Shculman et al., "Proximal Policy Optimization Algorithms," arXiv, 2017.

[3] J. Schulman et al., "High-Dimensional Continuous Control Using Generalized Advantage Estimation," arXiv, 2015.

 

---

강화학습 스터디의 다른 글 목록

• 강화학습 이론: On-policy & Off-policy
• 강화학습 알고리즘: (1) DQN (Deep Q-Network)
• 강화학습 알고리즘: (2) Double DQN
• 강화학습 알고리즘: (3) Dueling DQN
• 강화학습 알고리즘: (4) DDPG
• 강화학습 알고리즘: (5) PPO

 

---

오타나 잘못된 부분 있으면 댓글 부탁드립니다. 도움이 되셨다면 공감 눌러 주시면 감사하겠습니다 :)