[RL] 8. PPO: Proximal Policy Optimization

Actor-Critic은 온-정책(on-policy) 알고리즘이기 때문에, 경험 데이터를 한 번만 사용할 수 있다. 다시 말해, 재사용이 불가하다.

 

PPO(Proximal Policy Optimization)는 이러한 한계점을 개선한 알고리즘이다. 

 

이전에 살펴본 Actor-Critic 수식을 advantage function으로 표현하면 다음과 같다.

$$\begin{matrix} \nabla_\theta J(\theta) &=& \mathbb E_{\tau \sim \pi_\theta} \left[ \sum_{t=0}^T (R_t + \gamma V_w(s_{t+1})-V_w(s_t)) \nabla_\theta \log \pi_\theta(a_t|s_t)\right] \\ &=& \mathbb E_{\tau \sim \pi_\theta} \left[ \sum_{t=0}^T (Q_w(s_t,a_t)-V_w(s_t)) \nabla_\theta \log \pi_\theta(a_t|s_t)\right] \\ &=& \mathbb E_{\tau \sim \pi_\theta} \left[ \sum_{t=0}^T A_w(s_t, a_t) \nabla_\theta \log \pi_\theta(a_t|s_t)\right] \end{matrix}$$

 

위 수식을 $\tau$의 평균에서 $s_t, a_t$의 평균으로 변형하면 다음과 같다.

$$\begin{matrix} \nabla_\theta J(\theta) &=& \mathbb E_{\tau \sim \pi_\theta} \left[ \sum_{t=0}^T A_w(s_t, a_t) \nabla_\theta \log \pi_\theta(a_t|s_t)\right] \\ &=& \int_{\tau} \left(\sum_{t=0}^T A_w(s_t, a_t) \nabla_\theta \log \pi_\theta(a_t|s_t)\right) p_{\pi_\theta}(\tau) d\tau \\ &=& \sum_{t=0}^T \int_{\tau} A_w(s_t, a_t) \nabla_\theta \log \pi_\theta(a_t|s_t) p_{\pi_\theta}(\tau) d\tau  \\ &=& \sum_{t=0}^T \int_{s_t, a_t} A_w(s_t, a_t) \nabla_\theta \log \pi_\theta(s_t|a_t) \int_{\tau-{s_t, a_t}} p_{\pi_\theta}(\tau) d(\tau - s_t, a_t) d(s_t, a_t) \\ &=& \sum_{t=0}^T \int_{s_t, a_t} A_w(s_t, a_t) \nabla_\theta \log \pi_\theta(s_t|a_t) p_{\pi_\theta}(s_t, a_t) d(s_t, a_t) \\ &=& \sum_{t=0}^T \mathbb E_{s_t, a_t \sim \pi_\theta} \left[A_w(s_t, a_t) \nabla_\theta \log \pi_\theta(s_t|a_t)\right] \end{matrix}$$

---

PPO 알고리즘은 importance sampling을 통해 경험 데이터 재사용을 가능케 해준다.

1. Importance Sampling

중요도 샘플링(importance sampling)은 특정 확률 분포(e.g., 현재 정책 $\pi$)의 기댓값을 다른 확률 분포(e.g., 과거 정책 $\pi_\text{old}$)에서 샘플링한 데이터를 사용하여 계산하는 기법이다.

 

수식으로 표현하면 다음과 같다.

$$\begin{matrix} \mathbb E_\pi[x] &=& \sum x\pi(x) \\ &=& \sum x\frac{\pi_\text{old}(x)}{\pi_\text{old}(x)}\pi(x) \\ &=& \sum x\frac{\pi(x)}{\pi_\text{old}(x)}\pi_\text{old}(x) \\ &=& \mathbb E_{\pi_\text{old}} \left[x\frac{\pi(x)}{\pi_\text{old}(x)}\right]\end{matrix}$$

 

여기서 $\rho(x) = \frac{\pi(x)}{\pi_\text{old}(x)}$라고 하면, 각 $x$에 "가중치" $\rho(x)$가 곱해진다고 볼 수 있다.

$$\mathbb E_\pi[x] \simeq {\rho(x^{(1)})x^{(1)} + \rho(x^{(2)})x^{(2)} + \cdots + \rho(x^{(n)})x^{(n)} \over n}, \quad (\text{sampling from } x^{(i)} \sim \pi_\text{old})$$

$\pi(x)$와 $\pi_\text{old}(x)$의 간극 즉, 확률 간극을 메우기 위해 가중치 $\rho(x)$ 곱하여 조정하는 것이다.

예를 들어 $\pi(x)=0.8$이고, $\pi_\text{old}(x)=0.3$일 때, 확률분포 $\pi$에서는 $x$가 많이 샘플링되는 반면 확률분포 $\pi_\text{old}$에서는 상대적으로 적게 샘플링 된다. 그렇기 때문에, 확률 간극을 메우기 위해 $b$에서 $x$가 샘플링된 경우 가중치 2.6를 곱해 값이 커지도록 한다. 즉, $x$를 $2.6x$로 취급하는 것이다.

 

이처럼 실제 값과 보정값 간의 차이가 클수록 다른 말로, $\rho$의 보정 효과가 클수록 분산이 커진다.

분산을 줄이기 위해선 두 확률 분포($\pi$, $\pi_\text{old}$)를 비슷하게 가깝게 만들어야 한다.

(참고로, 기댓값을 추정할 때 분산이 커질수록 더 많은 샘플 데이터를 사용해야 하기 때문에 줄이는게 좋다.)

---

중요도 샘플링 기법을 사용해 $\nabla_\theta J(\theta)$을 변형하면 다음과 같다.

$$\begin{matrix} \nabla_\theta J(\theta) &=& \sum_{t=0}^T \mathbb E_{s_t, a_t \sim \pi_\theta} \left[A_w(s_t, a_t) \nabla_\theta \log \pi_\theta(s_t|a_t)\right] \\ &=& \sum_{t=0}^T \int_{s_t, a_t} A_w(s_t, a_t) \nabla_\theta \log \pi_\theta(s_t|a_t) p_{\pi_\theta}(s_t, a_t) d(s_t, a_t) \\ &=& \sum_{t=0}^T \int_{s_t, a_t} A_w(s_t, a_t) \nabla_\theta \log \pi_\theta(s_t|a_t) {p_{\pi_\theta}(s_t, a_t) \over p_{\pi_{\theta_\text{old}}}(s_t, a_t)} \ p_{\pi_{\theta_\text{old}}}(s_t, a_t) d(s_t, a_t) \\&=& \sum_{t=0}^T \int_{s_t, a_t} A_w(s_t, a_t) \nabla_\theta \log \pi_\theta(s_t|a_t) {p_{\pi_\theta}(s_t) \pi_\theta(a_t|s_t) \over p_{\pi_{\theta_\text{old}}}(s_t) \pi_{\theta_\text{old}}(a_t|s_t)} \ \ p_{\pi_{\theta_\text{old}}}(s_t, a_t) d(s_t, a_t) \\ &=& \sum_{t=0}^T \int_{s_t, a_t} A_w(s_t, a_t) {\nabla_\theta \pi_\theta(s_t|a_t) \over \pi_\theta(s_t|a_t)} {p_{\pi_\theta}(s_t) \pi_\theta(a_t|s_t) \over p_{\pi_{\theta_\text{old}}}(s_t) \pi_{\theta_\text{old}}(a_t|s_t)} \ \ p_{\pi_{\theta_\text{old}}}(s_t, a_t) d(s_t, a_t) \\ &=& \sum_{t=0}^T \int_{s_t, a_t} A_w(s_t, a_t) {\nabla_\theta \pi_\theta(s_t|a_t) \over \pi_{\theta_\text{old}}(a_t|s_t)} p_{\pi_{\theta_\text{old}}}(s_t, a_t) d(s_t, a_t) \\ &=& \sum_{t=0}^T \mathbb E_{s_t, a_t \sim \pi_{\theta_\text{old}}} \left[A_w(s_t, a_t) {\nabla_\theta \pi_\theta(s_t|a_t) \over \pi_{\theta_\text{old}}(a_t|s_t)}\right] \end{matrix}$$

 

결론, 중요도 샘플링을 사용해 목표 함수가 $A_w(s_t, a_t) \log \pi_\theta(s_t|a_t)$에서 $A(s_t, a_t) {\pi_\theta(a_t|s_t) \over \pi_{\theta_\text{old}}(a_t|s_t)}$로 바꿨다. 다시 말해, 과거 정책에서 얻은 경험 데이터를 토대로 현재 정책을 업데이트 할 수 있게 되었다.

2. Clipping

이때, 위 수식의 성립하기 위해서는 $p_{\pi_\theta}(s_t)$와 $p_{\pi_{\theta_\text{old}}}(s_t)$가 같아야 한다.

더 나아가, 목표 함수의 분산을 줄이기 위해, 두 확률 분포 $\pi_\theta$와 $\pi_{\theta_\text{old}}$가 매우 비슷해야 한다.

 

그렇기 때문에 위 수식은 다음과 같은 제약 조건을 만족해야 한다.

$$\text{constraint}: D_\text{KL}[\pi_\theta, \pi_{\theta_\text{old}}] \le \delta$$

 

PPO는 위 제약 조건을 만족하기 위해 다음과 같은 clipping 기법을 사용한다.

$$r_t \triangleq {\pi_\theta(a_t|s_t) \over \pi_{\theta_\text{old}}(a_t|s_t)}$$

$$r_t A(s_t, a_t) \rightarrow J_t^\text{clip}$$

$$(J_t^\text{clip} = \min \{r_tA(s_t, a_t), \text{clip}(r_t, 1-\epsilon, 1+\epsilon)A(s_t, a_t)\})$$

 

즉, $r_t A(s_t, a_t)$ 대신 $J_t^\text{clip}$를 사용한다.

 

해석

$A(s_t,a_t) > 0$일 경우 $\pi(a_t|s_t)$가 커지도록 유도할 것이기 때문에 $r_t$는 커진다. 근데, $\pi_\theta$와 $\pi_{\theta_\text{old}}$가 비슷해야 하기 때문에 $r_t$가 일정 수준 이상 커지는 것을 방지해야 한다.

$A(s_t,a_t) > 0$일 때 $J_t^\text{clip}$와 $r_t$ 간의 관계는 다음과 같기 때문에, $r_t$가 일정 수준 이상 커지면 더 이상 커지지 않게  clipping 해주는 효과를 준다.

 

반대로 $A(s_t,a_t) < 0$일 경우 $\pi(a_t|s_t)$가 작아지도록 유도할 것이기 때문에 $r_t$는 작아진다. 근데, $\pi_\theta$와 $\pi_{\theta_\text{old}}$가 비슷해야 하기 때문에 $r_t$가 일정 수준 이상 작아지는 것을 방지해야 한다.

$A(s_t,a_t) > 0$일 때 $J_t^\text{clip}$와 $r_t$ 간의 관계는 다음과 같기 때문에, $r_t$가 일정 수준 이상 작아지면 더 이상 작아지지 않게 clipping 해주는 효과를 준다.

 

3. GAE(Generalized Advantage Estimated)

$V(s_t)$의 목표를 설정할 때 $R_t + \gamma V(s_{t+1})$ 즉, 1-step TD error만 사용하는 것보다 2-step TD error 더 나아가 n-step TD error까지 사용하는게 더 낫을거 같다는 생각해, 1-step TD error부터 n-step TD error까지 지수 이동 평균을 계산해 $V(s_t)$의 목표로 사용하자는 것이 바로 GAE의 개념이다.

 

다시 말해, PPO는 PPO는 $A_t$ 대신 $A_t^\text{GAE}$를 사용한다.

$$\begin{matrix}  A_t^\text{GAE} \triangleq \sum_{k=1}^\infty (1-\lambda)\lambda^{k-1} A_t^{(k)}, \quad (A_t^{(k)}: \text{k-step TD error})\\ \\ A_t^{(1)} = R_t + \gamma V(s_{t+1}) - V(s_t) \\  A_t^{(2)} = R_t + \gamma R_{t+1} + \gamma^2 V(s_{t+2}) - V(s_t) \\ \vdots \\ A_t^{(n)} = \sum_{k=1}^n \gamma^{k-1} R_{t+k-1} + \gamma^n V(s_{t+n}) - V(s_t) \end{matrix}$$

 

1-step TD error는 분산(variance)가 작고, 편향(bias)가 크다. 반면, n-step TD error는 분산이 크고 편향이 작다.

그렇기 때문에, GAE 기법은 목표의 분산을 높이는 대신 편향을 낮춰준다. 즉, 목표의 분산과 편향 간의 trade-off를 시켜준다.

 

PPO에서는 실제로 위 식을 약간 변형한 $A_t^\text{GAE}$를 사용한다.

그 전에 $A_t^{(n)}$를 다르게 표현해보자.

$$\begin{matrix} A_t^{(1)} = R_t + \gamma V(s_{t+1}) - V(s_t) \triangleq \delta_t \\ A_t^{(2)} = R_t + \gamma R_{t+1} \gamma^2 V(s_{t+2}) - V(s_t) = (R_t + \gamma V(s_{t+1}) - V(s_t)) + \gamma(R_{t+1}+\gamma V(s_{t+2}) - V(s_{t+1})) = \delta_t + \gamma \delta_{t+1} \\ \vdots \\ A_t^{(n)} = \sum_{k=t}^{t+n-1} \gamma^{k-t} \delta_k \end{matrix}$$

 

이를 $A_t^\text{GAE}$에 대입해보자.

$$\begin{matrix} A_t^\text{GAE} &=& \sum_{n=1}^\infty (1-\lambda)\lambda^{n-1} A_t^{(n)} \\ &=& (1-\lambda)(\delta_t + \lambda (\delta_t + \gamma \delta_{t+1}) + \lambda^2(\delta_t + \gamma \delta_{t+1} + \gamma^2 \delta_{t+2}) + \cdots) \\ &=& (1-\lambda)(\delta_t(1+\lambda+\lambda^2+\cdots) + \delta_{t+1}(\lambda+\lambda^2+\cdots) + \delta_{t+2}(\lambda^2+\lambda^3+\cdots) +\cdots ) \\&=& (1-\lambda)(\delta_t {1 \over 1-\lambda} + \gamma \delta_{t+1}{\lambda \over 1- \lambda} + \gamma^2 \delta_{t+2}{\lambda^2 \over 1- \lambda} + \cdots ) \\ &=& \delta_t + \gamma \delta_{t+1} \lambda+ \gamma^2 \delta_{t+2} \lambda^2 + \cdots \\ &=& \sum_{k=t}^\infty (\gamma \lambda)^{k-t} \delta_k \end{matrix}$$

 

근데, 지속적 과제에서는 $A_t^\text{GAE}$를 그대로 사용하지 못한다. 그래서 논문에서는 식을 다음과 같이 수정했다.

$$\hat A_t^\text{GAE} \triangleq \sum_{k=t}^T (\gamma \lambda)^{k-t} \delta_k$$