📚 Paper
https://arxiv.org/pdf/1707.06347
📚 Reference
https://fse.studenttheses.ub.rug.nl/25709/1/mAI_2021_BickD.pdf
https://huggingface.co/learn/deep-rl-course/unit8/visualize
Visualize the Clipped Surrogate Objective Function - Hugging Face Deep RL Course
Unit 0. Welcome to the course Unit 1. Introduction to Deep Reinforcement Learning Bonus Unit 1. Introduction to Deep Reinforcement Learning with Huggy Live 1. How the course work, Q&A, and playing with Huggy Unit 2. Introduction to Q-Learning Unit 3. Deep
huggingface.co
https://yonghyuc.wordpress.com/2019/07/26/generalized-advantage-estimation-gae/
Generalized Advantage Estimation (GAE)
자.. 이전에 살펴본 것 처럼,더 좋은 학습 과정을 위해서 advantage function을 사용하기로 했다. 이때 Q function은 “a” action을 했을 때 얻을 수 있는 최대 reward이므로 이 된다 (s`은 state ‘s’ 에서 actio
yonghyuc.wordpress.com
Abstract
reinforcement learning을 이용하는 policy gradient method의 새로운 방법론인 Proximal Policy Optimization(PPO)를 소개한다. PPO의 직관은, 급진적인 policy parameter의 업데이트를 막아 안정적으로 학습하자는 것이다. (update policy conservatively) PPO는 agent와 environment의 interaction으로 얻은 samples(mini batch)를 이용해 surrogate objective function을 SGA(Stochastic Gradient Ascent) 최적화하고 다시 samples를 얻는 과정을 반복한다. 이때 surrogate function은 어떤 function을 근사하는 function을 말한다. 본 논문에선 objective function을 estimator E를 사용해 근사하고 있다. PPO는 TRPO(Trust Region Policy Optimization)의 성능을 보이면서도 이보다 훨씬 implementation이 용이하며 덜 복잡하다.
Introduction
RL과 neural network를 결합한 DQN(Deep Q-Learning)에도 scalability, data efficient, robustness 측면에서 개선의 여직 남아 있다. TRPO는 복잡하고 dropout이나 parameter sharing architecture에는 적용이 안된다는 한계를 가진다. 또한 DQN은 주어진 action space에서 이산적인 문제 해결에는 뛰어난 성능을 나타내지만 로봇의 움직임, 자율주행과 같은 연속적이고 정교한 행동을 해야 하는 continuous control benchmarks에서는 두각을 보이지 못했다.
따라서, 본 논문은 data efficiency를 높이면서도 TRPO의 reliable performance를 구현할 수 있는, first-order optimization(SGA)만을 이용한 알고리즘을 찾고자 했다. 본 논문은 clipped probability ratios를 이용한 새로운 objective function을 제안한다.
Background: Policy Optimization
Policy Gradient Methods
policy gradient는 policy gradient estimator g_hat을 SGA 알고리즘에 대입하는 것이다. policy gradient method에서의 목적은 Eqn. (3)를 최대화하는 것이고, Eqn. (3)를 미분하면 Eqn. (1)의 gradient estimator가 된다.
Eqn. (3)에 대해 더 구체적으로 설명하자면, 초록색 부분의 \(\pi_{\theta}\)는 정책으로, 상태 s일 때 행동 a를 할 확률을 의미한다. 노란색 부분의 A는 advantage function으로, Eqn. (4)처럼 상태 s에서 행동 a를 한 후 정책 \(\pi_{\theta}\)를 따라갔을 때 얻는 보상의 총합에서 상태 s에서 정책 \(\pi_{\theta}\)를 따라갔을 때 얻는 보상의 총합을 뺀 값과 같다. 즉, 상태 s에서 행동 a를 하는 것이 얼마나 좋냐 나쁘냐를 나타내는 값이다. E는 batch 내의 유한한 samples의 로그 정책 x advantage estimator의 기댓값을 계산한다.
그러나 Eqn. (3)을 이용하면 과도하게 큰 policy update로 이어질 수 있다는 한계가 있다.
Trust Region Methods
TRPO는 Eqn. (5)와 같이 policy 사이의 KL divergence에 constraint를 두면서 subject를 maximize하는 것을 목적으로 한다. 그러나 실제로 TRPO를 정당화하는 이론에서는 constraints를 주는 대신 penalty를 주는 개념을 제안한다. Eqn. (6)과 같이 계수 베타에 대해 unconstrained optimization problem을 푸는 것이다. 그러나, 다른 문제 사이는 물론 한 문제 사이에서도 learning의 특성이 계속 바뀌기 때문에 베타를 정하여 Eqn. (6)을 최적화하는 것은 쉽지 않다.
🌟 Clipped Surrogate Objective 🌟
probability ratio를 Eqn. (7)과 같이 정의하면 TRPO의 목적 함수는 Eqn. (8)과 같다. 만약 Eqn. (8)에 대한 constraint가 없다면 policy update는 과도하게 크게 일어날 것이므로, 본 논문에서는 Eqn. (9)와 같이 r이 1로부터 벗어나도록 하는 정책에 대해 penalize할 수 있는 목적 함수를 새롭게 설정했다. 이때 L^CLIP은 한 번의 에피소드의 t = 1, 2, ....T개의 타임 스텝의 training example에 대해 계산된다.
Eqn. (9)를 더 구체적으로 알아보자.
- epsilon은 hyperparameter로, 논문에서 제시하고 있는 값은 0.2이다.
- min function 안의 첫 번째 값은 Eqn. (8)과 같으며 두 번째는 clip된 r과 A를 곱한 값이다. 즉, r이 1-엡실론보다 작으면 1-엡실론이, 1+엡실론보다 크면 1+엡실론이 되어 A와 곱해진다. 이를 통해 r이 1로부터 크게 벗어나지 못하도록 했다.
- clipped and unclipped objective 사이에서 minimum 값을 사용하기 때문에 final objective는 lower bound (pessimistic bound)로 설정된다. 이를 통해 정책에 급격한 update가 일어나는 것을 방지할 수 있다.
Figure 1으로 어떻게 정책 업데이트에 규제가 이루어지는지 알아보자. 이때 r == p이다. 논문에서 말하길, objective improve되면 r을 무시하라고 하고 objective worse되면 r을 포함하라고 한다.
- case 1: p가 clip 범위 내에 있기 때문에 전자든 후자든 값이 같다. 이때 advantage function A가 양수이므로 현재 행동 a는 권장되어야 할 좋은 행동이다. 따라서 현재 정책(상태 s에서 행동 a를 할 확률)을 높여야 한다.
- case 2: p가 clip 범위 내에 있기 때문에 전자든 후자든 값이 같다. 이때 A가 음수이므로 현재 행동 a는 피해야 할 나쁜 행동이다. 따라서 현재 정책은 낮아져야 한다.
- case 3: p가1-엡실론보다 작다. 전자는 pA이고 후자는 (1-엡실론)A인데 A>0이므로 min 값은 전자다. 이때 A가 양수이므로 현재 행동 a는 권장되어야 할 좋은 행동이기 때문에 현재 정책이 더 높아져야 한다.
- case 4: p가 1-엡실론보다 작다. 전자는 pA이고 후자는 (1-엡실론)A인데 A<0이므로 min은 후자다. 이때 A가 음수이므로 현재 행동 a는 피해야 할 나쁜 행동이다. 그러나, 이미 현재 정책은 충분히 낮기 때문에 더 낮아지면 이전 정책과 현재 정책 사이에 큰 차이가 발생하게 되므로 업데이트가 이루어지면 안된다. 따라서 gradient = 0이다.
- case 5: p가 1+엡실론보다 크다. 전자는 pA이고 후자는 (1+엡실론)A인데 A>0이므로 min은 후자다. 이때 A가 양수이므로 현재 행동 a는 권장되어야 할 좋은 행동이다. 그러나, 이미 현재 정책은 충분히 높기 때문에 더 높아지면 이전 정책과 현재 정책 사이에 큰 차이가 발생하게 되므로 업데이트가 이루어지면 안된다. 따라서 gradient = 0이다.
- case 6: p가 1+엡실론보다 크다. 전자는 pA이고 후자는 (1+엡실론)A인데 A<0이므로 min은 전자다. 이때 A가 음수이므로 현재 행동 a는 피해야 할 나쁜 행동이기 때문에 현재 정책은 낮아져야 한다.
만약 case 4, case 5에서 clip 제한이 없었다면 정책은 그때의 행동 a를 좋은 쪽 혹은 나쁜 쪽으로 계속 업데이트하기 때문에 이전 정책과 현재 정책 사이의 차이는 발산했을 것이다.
Figure 1에서 Sign of Objective 열은 Return Value of min의 부호를 의미하고 Gradient는 L^CLIP을 이용한 역전파에서 계산된 gradient가 return value of L^CLIP(min)을 최대화하는 것을 목표로 하는지(v) 아닌지(0)를 나타낸다. 빨간점은 r = 1로, optimization의 시작점이다.
Figure 2를 보면 L^CLIP이 L^CPI의 lower bound임을 확인할 수 있다. 또한 L^CLIP의 최대점에서의 KL-divergence가 0.02임을 알 수 있다.
Adaptive KL Penalty Coefficient
KL divergence의 값이 목표로 하는 d_target이 될 수 있도록 penalty coefficient 베타를 업데이트하는 방법이다. 비록 clipped surrogate objective의 성능보다 낮았지만 중요한 baseline이기 때문에 짚고 넘어간다. Eqn. (10)을 보면 Eqn. (6)에서 설명했듯 TRPO의 목적 함수와 같다. 이때 d를 이전 정책과 현재 정책의 KL-divergence라고 한다면, 이 d의 크기를 이용해 베타를 적절하게 업데이트한다. 1.5와 2는 heuristic하게 얻어진 값이지만 알고리즘은 이 두 값에 크게 민감하지 않는다. 또한 알고리즘 자체가 베타에 대해 빠르게 적응하기 때문에 두 개의 hyperparameter setting은 그다지 중요한 이슈가 아니다.
Algorithm
본 논문에서 주장하는 clipped surrogate objective function은 기존의 policy gradient implementation에서 크게 벗어나지 않고, 몇 줄의 코드 수정으로 구현 가능하다. L^PG 대신 L^CLIP 또는 L^KLPEN을 사용하여 목적 함수를 구성하고 여러 에피소드를 거쳐 SGA를 이용해 목적 함수를 최대화한다.
대부분의 계산에서 advantage function으로 GAE(Generalized Advantage Estimation)을 사용한다. 만약 policy와 value function이 파라미터를 공유하는 nn architecture라면, objective function은 policy surrogate와 value function error term을 결합한 형태여야 한다. 이는 또한 충분한 탐험을 보장하기 위한 entropy bonus term을 추가하는 것으로 이어질 수 있다.
Eqn. (11)에서 c1, c2는 계수이고, S는 entropy bonus이고, L^VF은 (상태 s에서 정책을 따를 때 받을 수 있는 보상의 총합 - 목표하는 보상의 총합)^2으로, Eqn. (12)와 같다. 또한 Eqn. (11)의 계산에 A도 사용되는데, 일반화된 식은 Eqn. (14)이고 lambda = 1일 때 Eqn. (13)과 같다. 이때 감마는 discount factor로, 미래의 보상에 대한 할인율을 의미하고 lambda는 GAE의 하이퍼파라미터이다. Eqn. (13)은 한 에피소드에서 T 타임스텝까지 갔을 때, 상태 s에 대한 행동 a가 얼마나 좋은 행동인지를 알려준다. 이때 총 T개의 sample data가 생긴다.
PPO 알고리즘은 Algorithm 1과 같다.
- 반복횟수만큼 반복한다.
- N개의 actor들이 병렬적으로 자신이 처한 환경에서 주어진 정책을 따라 T번의 타임스텝까지 진행하여 t 타임스텝에서의 sample data를 얻는다.
- 각각의 타임스텝 t에서 advantage function을 계산한다.
- 한 번의 반복에서 최대 NT개의 sample data가 쌓일 것이고, 그보다 작은 M개의 sample data로 하나의 batch를 구성한다. K번 에폭만큼 반복하며 L을 최적화한다.
- 그 결과 얻은 파라미터 세타를 세타_old로 사용한다.
- 끝
Experiments
Comparison of Surrogate Objectives
첫째로, 아래와 같은 세 가지의 surrogate objective function에 대해 다양한 hyperparameter를 사용해 실험했다. training은 100만번의 타임 스텝을 거쳤고 구체적인 파라미터 세팅은 Table 1과 같다. 최적 정책 파라미터를 찾기 위해서 각각 64개의 unit을 가지는 2개의 hidden layer로 구성되고 tanh를 nonlinearity function으로 사용한 fully-connected neural network를 사용했다. 또한 policy와 value function은 다른 파라미터를 사용했고 entropy bonus term은 사용하지 않았다. 7개의 서로 다른 environment에 대해 3개의 다른 random seed를 사용해 총 21번의 세팅에서 실험했다. 각각의 세팅에서 마지막 100개의 reward average를 계산해 점수를 계산했고, 0과 1사이로 shift and scaling을 해줬다. (normalizing) 마지막으로 결과가 스칼라로 나올 수 있도록 21개의 세팅의 점수를 평균내어줬다. 그 결과는 Table 2를 통해 확인할 수 있다.
Comparison to Other Algorithms in the Continuous Domain
다음으로, PPO를 다른 방법론들과 비교하는 실험을 했고 성능 비교 결과는 아래와 같다. PPO(보라색 그래프)가 다른 방법론들에 비해 continuous control environments에서 outperform하는 것을 확인할 수 있다.
Showcase in the Continuous Domain: Humanoid Running and Steering
고차원의 continuous control problem에서의 PPO의 성능을 확인하기 위해 3D humanoid를 포함하는 테스크를 수행하도록 했다. 첫째, 앞으로 걸어나가는 테스크. 둘째, 200번째 타임스텝마다 또는 목적이 달성됐을 때 target의 위치가 바뀌는데 이때마다 target을 따라가도록 하는 테스크. 셋째, 로봇이 바닥에서 일어나는 테스크. 아래 그래프는 타임스텝에 따른 learning curve로, 상승하고 있는 것을 확인할 수 있다.
Conclusion
본 논문은 PPO라는 새로운 방법론을 소개했다. vanilla policy gradient에서 조금의 수정을 거쳐 실행하기 간단하며 더욱 일반적인 상황에 적용될 수 있으면서도 동시에 TRPO의 성능을 낼 수 있다.