[Reinforcement Learning] Proximal Policy Optimization (PPO) Algorithm

Sion Park·2022년 7월 12일

안녕하세요! 오늘은 최근에 공부해본 PPO알고리즘에 대한 내용을 포스팅하고자합니다! PPO 알고리즘은 On-Policy 강화학습 알고리즘입니다. 제가 아는바에 의하면 TRPO알고리즘의 조금 더 구현에 친화적인 버젼으로 알고있습니다. 이 포스팅을 읽기 전에 A2C알고리즘에 대한 지식이 있으시면 좋습니다.

또한 이포스팅은 PPO알고리즘의 이론적인 부분을 조금 더 면밀히 살펴보고 이를 수식으로 이해하는데에 초점이 맞추어져있습니다.

Introduction

A2C 알고리즘
- REINFORCE 알고리즘의 단점인 몬테카를로 업데이트 문제와 그레디언트의 분산이 커지는 것을 해결.
- On-Policy 방법으로 인한 표본에 대한 효율성이 떨어짐.

PPO 알고리즘 또한 마찬가지로 On-Policy알고리즘 이지만 이러한 단점을 개선하였는데요! 어떠한 방법으로 이를 해결하였는지 알아보겠습니다!

이 포스팅에서 $x$ 는 state 를 의미하며, $u$ 는 action을 의미합니다.

또한 $x_0:u_t = (x_0, u_0, x_1, u_1, ... ,x_t, u_t)$ 를 의미하며, $x_0:x_t = (x_0, u_0, x_1, u_1, ... ,x_t)$ 의미합니다. 마지막으로, $x_0:\infty = (x_0, u_0, x_1, u_1, ... )$ 으로 무한 구간 에피소드를 의미합니다.

즉, 위 시퀀스들은 강화학습의 순서를 나타냅니다. (state 와 action의 반복)

Gradient Reconstruction

우선 A2C의 목적함수의 그레디언트를 알아보겠습니다..

\nabla J(\theta) = \sum_{t=0}^{T} \left(E_{x_0:u_t\sim p_\theta(x_0:u_t)} [\gamma^t\nabla_\theta log \pi_\theta (u_t\mid x_t)A^{\pi_\theta}(x_t, u_t)]\right)

여기서, 마코프 가정을 통해

\nabla J(\theta) = \sum_{t=0}^{T} \left(E_{x_t \sim p_\theta, u_t\sim \pi_\theta(u_t\mid x_t)} [\gamma^t\nabla_\theta log \pi_\theta (u_t\mid x_t)A^{\pi_\theta}(x_t, u_t)]\right)

임을 얻을 수 있다.

이러한 형태의 그레디언트로 인해 On-Policy 방법을 이용하여야 합니다. 즉, 정책 $\pi_\theta$ 로 발생시킨 샘플을 이용해서 기댓값을 계산하여야 합니다.

여기서 꼭 현재 정책을 이용하여야 할까요? 이전의 정책인 $\pi_{OLD}$ 로 발생한 샘플을 이용하면 안될까요?

중요샘플링을 이용하면 확률밀도함수 $p(x)$ 에 기반한 함수 $f(x)$ 의 기댓값을 다른 확률 밀도함수 $q(x)$ 를 이용해 계산이 가능합니다.
$E_{x\sim p(x) } [f(x)] = E_{x\sim q(x)} \left[\frac{p(x)}{q(x)}f(x)\right]$

위에서 말했던 A2C의 그레디언트에 중요샘플링을 적용하여 보면 아래와 같습니다.

\nabla J(\theta) = \sum_{t=0}^{T} \left(E_{x_t \sim p_\theta}\left[\frac{p_\theta(x_t)}{p_{\theta_{OLD}}(x_t)}E_{u_t\sim \pi_\theta(u_t\mid x_t)} \left[\gamma^t\frac{\pi_\theta(u_t\mid x_t)}{\pi_{\theta_{OLD}}(u_t\mid x_t)}\nabla_\theta log \pi_\theta (u_t\mid x_t)A^{\pi_\theta}(x_t, u_t)\right]\right]\right)

위 식에서 $p_\theta(x_t) \approx p_{\theta_{OLD}}(x_t)$ 라면,

\nabla J(\theta) = \sum_{t=0}^{T} \left(E_{x_t \sim p_\theta}\left[E_{u_t\sim \pi_\theta(u_t\mid x_t)} \left[\gamma^t\frac{\pi_\theta(u_t\mid x_t)}{\pi_{\theta_{OLD}}(u_t\mid x_t)}\nabla_\theta log \pi_\theta (u_t\mid x_t)A^{\pi_\theta}(x_t, u_t)\right]\right]\right)

가 됩니다.

여기서 스케일 함수로 쓰이는 $\frac{\pi_\theta(u_t\mid x_t)}{\pi_{\theta_{OLD}}(u_t\mid x_t)}$ 는 현재 시간스텝 $t$ 만의 함수이므로 그레디언트 값을 유사하게 얻을 수 있습니다.

Policy Update

정책 그레디언트의 원래 목적은 아래의 목적함수를 통해 정책 함수의 파라미터 $\theta$ 를 목적함수의 그래디언트를 이용해 목적함수가 최대가 되는 정책 $\pi_\theta$ 를 찾는 것입니다.

J(\theta) = E_{x_0:u_T\sim p_{\theta}(x_0 : u_T)}\left(\sum_{t = 0 }^T \gamma^tr(x_t, u_t)\right)

이를 찾기 위해 그레디언트를 통한 업데이트로 정책 파리미터 $\theta$ 를 찾게 됩니다. 즉, 정책을 점진적으로 업데이트 해가는 그레디언트 어센트 (최대화) 방법 등을 적용합니다.

여기서 업데이트된 정책은 이전의 정책보다 더 큰 목적함수 값을 가져야 합니다. 즉, $J(\theta) - J(\theta_{OLD}) >0$ 가 되도록 하여야 합니다.

다시 목적함수를 보겠습니다. 위의 목적함수 $J(\theta)$ 는 상태가치함수 V를 이용해

\begin{aligned} J(\theta) &= E_{x_0\sim p(x_0 )}\left(V^{\pi_{\theta}}(x_0)\right)\\ &=E_{x_0:\infty\sim p_{\theta}(x_0:\infty)}\left(V^{\pi_{\theta}}(x_0)\right) \end{aligned}

으로 표현됩니다. (상태가치함수가 $x_0$ 만의 함수이기 때문입니다.)

또한 이전 정책의 상태가치 함수의 평균은 다음과 같이 나타납니다.
$\begin{aligned}E_{x_0\sim p(x_0 )}\left(V^{\pi_{\theta_{OLD}}}(x_0)\right) &= \int_{x_0}V^{\pi_{\theta_{OLD}}}(x_0) p(x_0)dx_0\\ &= \int_{x_0} \left[p_\theta (u0, x1, ...)du_0dx_1\cdots\right]V^{\pi_{\theta_{OLD}}}(x_0) p(x_0)dx_0\\ &= \int_{x_0:\infty}V^{\pi_{\theta_{OLD}}}(x_0) p_\theta(x_0:\infty)dx_0:\infty\\ &= E_{x_0:\infty\sim p_{\theta}(x_0:\infty)}\left(V^{\pi_{\theta_{OLD}}}(x_0)\right) \end{aligned}$

이를 통해,

\begin{aligned} J(\theta) - J(\theta_{OLD}) &= E_{x_0\sim p(x_0 )}\left(V^{\pi_{\theta}}(x_0)\right) - E_{x_0\sim p(x_0 )}\left(V^{\pi_{\theta_{OLD}}}(x_0)\right)\\&= E_{x_0:\infty\sim p_{\theta}(x_0:\infty)}\left[V^{\pi_{\theta}}(x_0)\right] - E_{x_0:\infty\sim p_{\theta}(x_0:\infty)}\left[V^{\pi_{\theta_{OLD}}} (x_0)\right]\\ &=E_{x_0:\infty\sim p_{\theta}(x_0:\infty)}\left[\sum_{t=0}^\infty \gamma^t r(x_t, u_t)\right] \\ &\qquad - E_{x_0:\infty\sim p_{\theta}(x_0:\infty)}\left[\sum_{t=0}^\infty \gamma^t V^{\pi_{\theta_{OLD}}} (x_t) - \sum_{t=1}^\infty \gamma^t V^{\pi_{\theta_{OLD}}} (x_t)\right] \\ &= E_{x_0:\infty\sim p_{\theta}(x_0:\infty)}\left[\sum_{t=0}^\infty \gamma^t\left( r(x_t, u_t) + \gamma V^{\pi_{\theta_{OLD}}} (x_{t+1}) - V^{\pi_{\theta_{OLD}}} (x_t)\right) \right] \end{aligned}

입니다.

여기서 어드밴티지 함수의 정의

\begin{aligned} A^{\pi_\theta}(x_t,u_t) &=Q^{\pi_\theta}(x_t,u_t) - V^{\pi_\theta}(x_t)\\ &= r(x_t, u_t) + E_{x_{t+1} \sim p(x_{t+1}\mid x_t, u_t)}[\gamma V^{\pi_{\theta_{OLD}}}(x_{t+1})] - V^{\pi_{\theta_{OLD}}} (x_t)\\ &= E_{x_{t+1} \sim p(x_{t+1}\mid x_t, u_t)}[r(x_t, u_t) + \gamma V^{\pi_{\theta_{OLD}}}(x_{t+1}) - V^{\pi_{\theta_{OLD}}} (x_t)]\\ \end{aligned}

로부터

\begin{aligned} J(\theta) - J(\theta_{OLD}) = E_{x_0:\infty\sim p_{\theta}(x_0:\infty)}\left[\sum_{t=0}^\infty \gamma^t A^{\pi_{\theta_{OLD}}}(x_t, u_t)\right]= \sum_{t=0}^\infty E_{x_0:\infty\sim p_{\theta}(x_0:\infty)}\left[\gamma^t A^{\pi_{\theta_{OLD}}}(x_t, u_t)\right] \end{aligned}

임을 알 수 있습니다.

또한, 어드밴티지 함수 $A^{\pi_{\theta}}(x_t, u_t)$ 는 $x_t, u_t$ 의 함수이므로

E_{x_0:\infty\sim p_{\theta}(x_0:\infty)}\left[A^{\pi_{\theta}}(x_t, u_t)\right] = E_{x_t \sim p_\theta(x_t)}\left[ E_{u_t \sim \pi_\theta(u_t\mid x_t)} \left[ A^{\pi_{\theta}}(x_t, u_t)\right]\right]

임이 성립합니다. 이를 바탕으로 중요샘플링을 여기 적용해보면

E_{x_t \sim p_\theta(x_t)}\left[ E_{u_t \sim \pi_\theta(u_t\mid x_t)} \left[ A^{\pi_{\theta}}(x_t, u_t)\right]\right] = E_{x_t \sim p_\theta(x_t)}\left[ E_{u_t \sim \pi_{\theta_{OLD}}(u_t\mid x_t)} \left[ \frac{\pi_{\theta}(u_t\mid x_t)}{\pi_{\theta_{OLD}}(u_t\mid x_t)} A^{\pi_{\theta}}(x_t, u_t)\right]\right]

이고, $p_\theta \approx p_{\theta_{OLD}}$ 를 가정하여 위의 목적함수 차이에 적용해보면,

\begin{aligned} J(\theta) - J(\theta_{OLD}) &= \sum_{t=0}^\infty E_{x_t \sim p_\theta(x_t)}\left[ E_{u_t \sim \pi_{\theta_{OLD}}(u_t\mid x_t)} \left[ \frac{\pi_{\theta}(u_t\mid x_t)}{\pi_{\theta_{OLD}}(u_t\mid x_t)} A^{\pi_{\theta}}(x_t, u_t)\right]\right]\\ &\approx \sum_{t=0}^\infty E_{x_t \sim p_{\theta_{OLD}}(x_t)}\left[ E_{u_t \sim \pi_{\theta_{OLD}}(u_t\mid x_t)} \left[ \frac{\pi_{\theta}(u_t\mid x_t)}{\pi_{\theta_{OLD}}(u_t\mid x_t)} A^{\pi_{\theta}}(x_t, u_t)\right]\right] \end{aligned}

입니다. 이 차이 값을 $L(\theta)$ 라고 하겠습니다.

그러면 $J(\theta) = J(\theta_{OLD}) + L(\theta)$ 입니다.

여기서 $L(\theta)$ 를 $\theta$ 로 미분하여 보면

\begin{aligned} \nabla_\theta L(\theta) &= \sum_{t=0}^\infty E_{x_t \sim p_{\theta_{OLD}}(x_t)}\left[ E_{u_t \sim \pi_{\theta_{OLD}}(u_t\mid x_t)} \left[ \frac{\nabla_\theta\pi_{\theta}(u_t\mid x_t)}{\pi_{\theta_{OLD}}(u_t\mid x_t)} A^{\pi_{\theta}}(x_t, u_t)\right]\right]\\&= \sum_{t=0}^\infty E_{x_t \sim p_{\theta_{OLD}}(x_t)}\left[ E_{u_t \sim \pi_{\theta_{OLD}}(u_t\mid x_t)} \left[ \frac{\pi_{\theta}(u_t\mid x_t)}{\pi_{\theta_{OLD}}(u_t\mid x_t)} \nabla_\theta log \pi_\theta(u_t\mid x_t)A^{\pi_{\theta}}(x_t, u_t)\right]\right] \end{aligned}

이고 여기서 $\theta_{OLD} = \theta$ 인 경우 위의 Policy Reconstruction의 가장 처음 식인 $\nabla_\theta J(\theta)$ 와 동일하게 됩니다. 즉 $\theta_{OLD}$ 가 $\theta$ 와 유사한 경우 이전의 정책으로 발생한 표본을 정책 업데이트에 사용 가능하게 됩니다.

자, 그럼 이것을 어떻게 적용할 까요? $L(\theta)$ 를 최대한 큰 값으로 만들면서 정책을 크게 변화시키지 않음으로써 정책을 개선시킬 수 있습니다. 다음과 같이 제약조건이 있는 최적화 문제를 해결함으로써요..!

\theta = \arg\max_\theta \sum_{t=0}^\infty E_{x_t \sim p_{\theta_{OLD}}(x_t),u_t \sim \pi_{\theta_{OLD}}(u_t \mid x_t)}\left[ \frac{\pi_{\theta}(u_t\mid x_t)}{\pi_{\theta_{OLD}}(u_t\mid x_t)} A^{\pi_{\theta_{OLD}}}(x_t, u_t)\right]\\ subject \; to \quad \pi_\theta(u_t\mid x_t) \approx \pi_{\theta_{OLD}}(u_t\mid x_t)

PPO (Proximal Policy Optimization) 알고리즘

PPO 알고리즘에서 현재의 정책과 이전의 정책이 유사하게 한정시키기 위해 Clipping 이라는 전략을 사용합니다.

이전의 정책과 현재의 정책의 비율을 다음과 같이 정의해봅시다.

r_i(\theta) = \frac{\pi_\theta(u_t\mid x_t)}{\pi_{\theta_{OLD}}(u_t\mid x_t)}

여기서 Clipping 이라는 것은 다음과 같이 $r_i(\theta)$ 값을 $1-\epsilon$ 과 $1+\epsilon$ 사이로 유지시켜 주는 것입니다.

clip(r_i(\theta), 1-\epsilon, 1+\epsilon) = \begin{cases} 1+\epsilon, \; if \; r_i(\theta) \geq 1+\epsilon\\ 1-\epsilon, \; if \; r_i(\theta) \leq 1-\epsilon\\ r_i(\theta), \; otherwise \end{cases}

이를 이용해 새로운 목적함수인 $L_t^{clip}(\theta)$ 와 $\theta$ 의 최적화 문제를 다음과 같이 나타낼 수 있습니다.

L_T^{clip}(\theta) = min\{r_i(\theta)A^{\pi_{OLD}}(x_t, u_t), clip(r_i(\theta), 1-\epsilon, 1+\epsilon)A^{\pi_{OLD}}(x_t, u_t)\}

\theta \leftarrow \arg\max_\theta\sum_{t = 0 }^{\infty}E_{x_0:u_t \sim p_{\theta_{OLD}}(x_0:u_t)}\left[L_T^{clip}(\theta)\right]

여기서 $L_T^{clip}(\theta)$ 값은 $A^{\pi_{OLD}}(x_t, u_t) >0$ 인 경우와 $A^{\pi_{OLD}}(x_t, u_t) <0$ 인 경우로 나누어 생각해 볼 수 있는데요.

$A^{\pi_{OLD}}(x_t, u_t) >0$ 인 경우 : 상태 $x_t$ 에서 선택된 행동 $u_t$ 가 평균에 비해 좋다는 뜻이기 때문에 새로운 정책은 그 행동을 선택한 정책보다 더욱 높은 확률 값을 갖기때문에 $r_i(\theta)$ 값이 커지고 이를 $1+\epsilon$ 까지 제한합니다.
$A^{\pi_{OLD}}(x_t, u_t) <0$ 인 경우 : 상태 $x_t$ 에서 선택된 행동 $u_t$ 가 평균에 비해 좋지 않다는 뜻이기 때문에 새로운 정책은 그 행동을 선택한 정책보다 더욱 낮은 확률 값을 갖으려 하기 때문에 $r_i(\theta)$ 값이 작아지고 이를 $1-\epsilon$ 까지 제한합니다.

PPO algorithm

크리틱 신경망 ( $\phi$ ) 과 액터 신경망 ( $\theta$ ) 을 초기화 합니다.
- 2.1 이전 정책을 이용해 확률적으로 행동을 선택합니다.
- 2.2 TD타겟값 $y_i$ 와 어드밴티지 $A_\phi(x_t,u_t)$ 를 계산합니다.
- 2.3 $(x_t, u_t, y_t, A_\phi(x_t,u_t), log\pi_{\theta_{OLD}}(u_t\mid x_t) )$ 를 배치에 저장합니다.
- 2.1 - 2.3 을 N 번 반복하여 크기 N인 배치를 수집합니다.
$\;$
- 3.1 설정된 미니배치 크기 $B$ 만큼의 데이터를 얻습니다.
- 3.2 크리틱 신경망의 손실함수를 계산합니다.
  $L = \frac{1}{2B}\sum_i(y_i - V_\phi(x_i))^2$
- 3.3 손실함수의 그래디언트 값을 이용해 크리틱 신경망 $\phi$ 을 업데이트하여 줍니다.
- 3.4 $L_i^{clip}$ 을 계산하고 그래디언트를 통해 액터 신경망 $\theta$ 를 업데이트 하여 줍니다.
- 3.1 - 3.4 까지 모든 배치를 사용할 때 까지 반복하여 줍니다.
2.과 3.을 지정된 횟수 만큼 반복하여 줍니다.

GAE (Generalized Advantage Estimation)

어드밴티지를 계산할때 대게 n-스텝의 값을 이용해 어드밴티지 추정값을 이용합니다. 하지만 여기서 n이 작은 경우 편향이 크고 분산이 낮지만, n이 큰 경우 편향이 작아지지만 분산이 커집니다. PPO 알고리즘에서는 다음과 같은 GAE방법을 이용해서 어드밴티지값을 추정합니다.

A^{GAE}_\phi(x_t, u_t) = \sum_{n=1}^{\infty}\omega_nA_\phi^{(n)}(x_t, u_t)

여기서 $A_\phi^{(n)}(x_t, u_t) = \sum_{k =t}^{t+n-1}\gamma^{k-t}(r(x_t,u_t) + \gamma V_\phi(x_{t+1})- V_\phi(x_{t}))$ 입니다. (이는 n스텝 어드밴티지 함수의 정의를 통해 쉽게 얻을 수 있습니다.)