[작성중] PPO - Proximal Policy Optimization Algorithms 논문 리뷰 및 요약

요약

 

2. Background

Policy Optimization

Policy gradient method는 policy gradient 추정기를 계산하는 방법으로 작동한다. 아래의 경사 추정기 $\hat{g}$는 목적 함수 $L^{PG}$를 미분함으로써 얻는다.

$$\hat{g} = \hat{\mathbb{E}}_t \left[ \nabla_\theta \text{log} \pi _\theta (a_t | s_t ) \hat{A}_t \right] $$

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

 $\pi_\theta$는 stochastic policy, $\hat{A}_t$는 advantage function estimator 이다. 그리고 기댓값은 유한한 샘플 배치에 대한 실험적 평균이다.

 목적 함수 $L^{PG}$에 대해 여러 단계를 거쳐서 최적화하는게 좋을 순 있으나, 그렇게 당연하진 않고, 실험적으로 이러한 방법은 파괴적으로 과도한 정책 갱신을 유발한다.

Trust Region Method

 TRPO에서는, 목적 함수(Objective function, surrogate objective)는 정책 갱신의 크기에 제약조건을 두고 최대화된다.

$$\text{maximize}_\theta \hspace{5mm} \hat{\mathbb{E}} \left[ \frac{\pi_\theta (a_t | s_t) }{\pi_{\theta_{\text{old}}}(a_t | s_t) } \hat{A}_t \right] $$

$$\text{subject to} \hspace{5mm} \hat{\mathbb{E}}_t \left[ \text{KL} [ \pi_{\theta_{\text{old}}} (\cdot |s_t), \pi_\theta(\cdot |s_t) ] \right] < \delta$$

 이 문제는 objective를 선형 근사하고 constraint를 이차식으로 근사함으로써, conjugate gradient algorithm을 이용하여 근사적으로 효율적이게 풀릴 수 있다. 

 TRPO를 정당화하는 이론은 constraint보다는 penalty를 이용하는 방법을 제안한다. 다시 말해, 비구속 최적화 문제를 푸는 방법의 제안이다.

$$\text{maximize}_\theta \hspace{5mm} \hat{\mathbb{E}} \left[ \frac{\pi_\theta (a_t | s_t) }{\pi_{\theta_{\text{old}}}(a_t | s_t) } \hat{A}_t -\beta \text{KL} [ \pi_{\theta_{\text{old}}} (\cdot |s_t), \pi_\theta(\cdot |s_t) ] \right] $$

 이는 mean KL이 아닌 max KL을 계산하는 특정 surrogate objective가 정책의 성능의 하한선(lower bound)를 형성한다는 점을 따른다. TRPO는 다른 문제에서도 잘 통할만한 단일 값인 체벌 계수 $\beta$를 선택하기가 어렵기 때문에 penalty보다 어려운 contraint를 사용한다. 그러므로 TRPO의 단조 향상을 따라하는 1차 알고리즘의 목적을 달성하기에는, 실험들은 고정된 체벌 변수 $\beta$를 간단하게 선택하고, 위의 체벌을 적용한 목적함수를 최적화하기에는 불충분하다. 약간의 변형이 필요하다.

3. Clipped Surrogate Objective

 $r_t(\theta)$는 확률 비율로 $r_t (\theta) = \pi_\theta (a_t | s_t) /\pi_{\theta_{\text{old}}}(a_t | s_t) $으로 $r_t (\theta_{old})=1$이다. TRPO는 surrogate objective를 최대화한다.

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

위첨자 CPI는 Conservative policy iteration으로, 이러한 목적함수가 제안되었다. 구속 조건 없이 목적 함수의 최대화는 과도한 정책 갱신을 유도한다. 따라서 목적 함수를 어떻게 변형할 것인가, $r_t (\theta)$를 1에서 멀어지게하는 정책의 변화를 얼마나 체벌할 것인가를 상정해보자.

 위 논문에서 제안하는 목적 함수는 다음과 같다.

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

$\epsilon$은 초-매개변수로, $\epsilon=0.2$이다. 첫째 항은 $L^{CPI}$의 최소화이고, 두 번째 항은 확률 비율 $r_t$를 clipping(잘라낸) surrogate objective를 변형한다. 결국 clipped 또는 unclipped 목적함수의 최소화를 취하게 된다. 최종 목적 함수는 unclipped 목적 함수의 lower bound가 된다. 

 확률 비율 $r_t$ 은 advantage의 부호에 따라 clipping 된다.

-

4. Adaptive KL Penalty Coefficient

 앞서 설명한 clipped surrogate objective 를 사용하는 대신, 다른 접근 방법으로 KL 발산 값을 penalty 상수 $\beta$로 조절하면서 추가적인 penalty로 사용하는 방법이 있다. 

KL-penalized objective는 다음과 같다.

$$L^{KP-pen}(\theta) = \hat{\mathbb{E}}_t \left[\frac{\pi_\theta (a_t | s_t)}{\pi_{\theta_{old}}(a_t | s_t)} \hat{A}_t - \beta \text{KL} \left[ \pi_{\theta_{old}} (\cdot | s_t ) , \pi _\theta (\cdot | s_t ) \right]  \right]$$

정책 간 KL divergence의 기댓값 $d=\hat{\mathbb{E}}_t \left[ \text{KL} \pi_{\theta_{old}}(\cdot | s_t ) , \pi_\theta(\cdot | s_t ) \right]$$은 다음과 같이 계산한다.

$$\cases{ \beta\leftarrow \beta/2 \hspace{5mm} d < d_{targ} /1.5\\ \beta \leftarrow \beta \times 2 \hspace{5mm} d>d_{targ} \times 1.5 }$$

 갱신한 $\beta$ 는 다음 정책 갱신에 사용된다. 위 전략을 사용하면 $d_{targ}$이 유효하게 커질 때 가끔 정책 갱신이 발생한다는 것을 볼 수 있다. 위에 곱하는 1.5나 2는 경험적으로 선택하는 값인데, 이 값에 알고리즘이 많이 민감하진 않다. 그리고 $\beta$의 초깃값도 초-매개변수인데, 알고리즘이 $\beta$를 매우 빠르게 조정하기 때문에 실제는 그리 중요하지 않다.

 

5. Algorithm

 앞서 설명한 Surrogate loss들은 계산 가능하며 통상적인 정책 경사 구현에 약간의 변화를 주어 미분된다. 자동 미분을 이용한 구현에서, surrogate loss는 $L^{PG}$ 대신 쉽게 $L^{CLIP}$ 혹은 $L^{KP-pen}$을 구할 수 있다. 그리고 이 loss는 이 objective에 대해서 stochastic gradient ascent의 여러 스텝을 수행할 수 있다.

 분산을 줄이는 advantage-function estimator를 계산하는 대부분의 기술은 학습된 state-value function $V(s)$를 사용한다. 예를 들면 generalized advantage estimation [Sch+15a], finite-horizon estimators [Mni+16} 가 있다. 만약 policy/value network가 매개변수를 공유한다면 policy surrogate와 value function error term을 합친 loss function을 사용해야 한다. 이러한 objective는 충분한 탐험을 보장하기 위해 entropy bonus를 추가하는 식으로 보완된다.

$$L_t^{CLIP+VF+S}(\theta) = \hat{\mathbb{E}}_t \left[ L_t^{CLIP}(\theta) - c_1 L_t^{VF}(\theta)+c_2 S[\pi_\theta](s_t) \right]$$

 $c_1$, $c_2$는 상수, $S$는 entropy bonus, $L_t^{VF}$는 squared-error loss $\left(V_\theta (s_t) - V_t^{targ} \right)^2 $이다.

 [Mni+16]으로 유명해졌으며, 순환신경망 RNN에 사용하면 아주 적합한, 정책 경사 구현 방법은 에피소드 길이보다는 매우 작은 시간 스텝 $T$만큼 정책을 적용한다. 그리고 정책 갱신을 위해서 sample을 모은다. 이 방법은 시간 $T$ 너머로 보진 않은 advantage estimator를 필요로 한다. [Mni+16]에서 사용한 estimator는 다음과 같다.

$$\hat{A}_t = -V(s_t) + r_t + \gamma r_{t+1} + \cdots + \gamma ^{T-t+1} + \gamma^{T-t} V(s_T)$$

시간 t는 주어진 T 길이의 궤적 부분인 [0,T]으로 특정된다. 이 선택을 일반화하려면, generalized advantage estimation의 절단된 버전 (위 식이 $\lambda=1$인)이 필요하다. 

$$\hat{A}_t = -V(s_t) + r_t + (\gamma\lambda)  r_{t+1} + \cdots + (\gamma \lambda) ^{T-t+1} + (\gamma \lambda )^{T-t} V(s_T)$$

$$\delta_t = r_t + \gamma V(s_{t+1}) - V(s_t) $$

 고정된 길이의 궤적을 사용하는 PPO 알고리즘은 다음 박스와 같다. 각 반복마다 평행한 $N$개의 actor는 시간스텝 $T$ 만큼의 데이터를 모은다. 그리고 $NT$ 만큼의 데이터를 가지고 surrogate loss를 만든다.

6. 실험

 총 3개의 objective를 정의하였으므로 이에 대한 성능 비교는 다음과 같다. 이는 OpenAI Gym 환경에서 MuJoCo 물리엔진을 사용했다고 한다.

 

구현을 위한 정리

Recommended coefficients

KL-penalty coefficient $\beta_0 = 1$

clipping coefficient $\epsilon=1$

Discount factor $\gamma=0.99$

GAE parameter $\lambda=0.5$

 

Advantage function estimator $\hat{A}$

에피소드 길이보다 짧은 시간 길이 $T$에 대해서 Advantage를 추정한다. [0,T] 상의 t 에 대해서,

1) Generalized Advantage estimator(GAE) [Mni+16]

$$\hat{A}_t = -V(s_t) + r_t + \gamma r_{t+1} + \cdots + \gamma ^{T-t+1} + \gamma^{T-t} V(s_T)$$

2) Truncated version of Generalized advantage estimator

$$\hat{A}_t = -V(s_t) + r_t + (\gamma\lambda)  r_{t+1} + \cdots + (\gamma \lambda) ^{T-t+1} + (\gamma \lambda )^{T-t} V(s_T)$$

Surrogate Objective Family $L$

1) Surrogate Objective - Conservative policy iteration [KL02]

$$L^{CPI} =r_t(\theta) \hat{A}_t, \hspace{5mm} r_t (\theta) = \pi_\theta (a_t | s_t) /\pi_{\theta_{\text{old}}}(a_t | s_t) $$

2) Clipped Surrogate Objective

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

3) KL-penalized Objective

$$L^{KL} = \frac{\pi_\theta (a_t | s_t)}{\pi_{\theta_{old}}(a_t | s_t)} \hat{A}_t - \beta \text{KL} \left[ \pi_{\theta_{old}} (\cdot | s_t ) , \pi _\theta (\cdot | s_t )   \right]$$

$$d=\hat{\mathbb{E}} \left[ \text{KL} \left[ \pi_{\theta_{old}} (\cdot | s_t ) , \pi _\theta (\cdot | s_t )   \right]\right]$$

$$\cases{ \beta\leftarrow \beta/2 \hspace{5mm} d < d_{targ} /1.5\\ \beta \leftarrow \beta \times 2 \hspace{5mm} d>d_{targ} \times 1.5 }$$

4) Clipped Surrogate Objective for the network sharing parameters [Wil92, Mni+16]

$$L_t^{Clip+VF+S}(\theta) = \hat{\mathbb{E}}_t \left[ L_t^{CLIP}(\theta) - c_1 L_t^{VF}(\theta)+c_2 S[\pi_\theta](s_t) \right]$$

$$L_t^{VF}(\theta)=\left(V_\theta (s_t) - V_t^{targ} \right)^2 $$