PPO(Proximal Policy Optimization Algorithms)

Main Paper https://arxiv.org/pdf/1707.06347.pdf

 

Proximal Policy Optimization Algorithms

Abstract

env와의 interaction을 통한 data sampling과 policy gradient ascent 사용한 surrogate objective function optimization를 교대하는 Policy Gradient 방식을 제안한다. 기존의 PG가 data sample당 하나의 gradient update를 수행하는 반면, 우리는 mini batch update의 여러 epoch를 가능하게 하는 새로운 objective function을 제안한다.

 

제안하는 PPO는 TRPO의 일부 이점이 있지만 구현이 훨씬 간단하고 sample complexity가 empirically하게 더 좋다. 결과적으로 PPO가 다른 online PG 방식보다 성능이 우수하고, 전반적으로 sample complexity, simplicity, wall-time에서 유리한 balance를 유지한다는 것을 보여준다.

 

 

---

Introduction

최근 몇년간 RL를 위해 neural network function approximators 방식들이 제안되었다. 그러나 scalable(to large model and parallel implementations), data efficient, hyperparameter 조정 없이 다양한 문제에 적용가능한 robust에 대한 문제점들이 존재한다. 

 

1. deep Q-learning

: 많은 간단한 문제에서 실패하고, 잘 이해되지 않는다. 

2. 'vanilla' policy gradient

: data efficient와 robustness가 좋지 않다. 

3. TRPO

: 상대적으로 복잡하며 noise(such as dropout) 또는 parameter sharing(between policy & value fucntion or auxiliary tasks)를 포함하는 구조와 호환되지 않는다. 

 

본 논문에서는 위 문제점들을 해결 하기 위해 first-order optimization를 사용해 TRPO의 data efficiency와 reliable performance를 얻을 수 있는 알고리즘을 제안한다. 또한 policy의 성능에 대한 pessimistic estimate(비관적 추정 i.e. lower bound)을 형성하는 clipped probability ratios로 새로운 objective를 제안한다. policy를 최적화하기 위해, policy에서 data sampling하고, sampled data에 대해 여러 epoch optimization을 수행한다. 

 

 

---

Background: Policy Optimization

Policy Gradient Methods

: policy gradient estimator를 계산하고, 이를 stochastic gradient ascent algorithm에 연결하여 작동한다. 가장 일반적으로 사용되는 gradient(estimator)는 다음과 같다. 

 

equation(1)

: stochastic policy

 

: estimator of the advantage function at timestep t

 

: sampling과 optimization를 번갈아 가며 사용하는 finite batch of samples에 대한 empirical average(경험적 평균)

 

automatic dierentiation software를 사용하는 구현은 objective function의 gradient가 policy gradient estimator인 구성을 가지며 작동한다. equation(1)은 다음의 objective function(loss) equation(2)를 미분하여 만들어진다. 

 

equation(2)

 

same trajectory를 사용하여 loss L에 대해 여러 최적화 단계를 수행하는 것이 좋지만, 그렇게 하는 것은 well-justified하지 않으며 경험적으로 종종 파괴적인 large policy update로 이어진다. 

=> 여러 trajectory sample에 대한 optimization으로 

 

Trust Region Methods

: TRPO에서는 policy update size에 대한 constraint에 따라 objective function("surrogate" objective)가 최대화되는 policy로 update를 진행한다. 

 

equation(3)

: 업데이트 전 policy parameter의 vector

 

Trust Region Method는 objective에 대한 linear approximation & constraint에 대한 quadratic approximation을 수행한 후, conjugate gradient algorithm을 사용하여 대략적으로 해결할 수 있다.

=> 계산이 매우 많고, 복잡하므로 근사적으로 문제는 해결하였지만 개선 및 분석이 힘들다. TRPO의 고질적 문제점.

 

TRPO는 실제로 surrogate objective가 policy의 성능을 보장하기 위한 lower bound를 형성한다는 개념을 따라 constraint 대신 아래와 같이 penalty를 사용하는 것을 제안한다. coefficient β에 대해, unconstrained optimization problem을 해결하는 것이다.

 

equation(4)

 

그럼에도 TRPO에서 hard constraint 방식을 사용한 이유는 학습 도중에 특성의 변화가 많아 fixed β를 결정하기 어렵기 때문이다. 따라서 TRPO의 monotonic improvement를 유지하기 위한 first-order algorithm의 목표를 달성하기 위해, 실험에 따르면 단순히 a fixed penalty coefficient β를 선택하고 SGD를 사용하여 penalized objective equation(4)를 최적화하는 것만으로는 충분하지 않다고 보여 추가적인 수정이 필요하다.

=> 기존의 penalty coefficient β 값 선택과 equation(4) optimize(objective & constraint approximation)가 상당히 어렵다는 이유로, TRPO의 monotonic improvement가 가능한 policy optimization을 first-order algoritm로 계산하는 방식에서 추가적인 개선이 필요하다. 

 

 

---

Clipped Surrogate Objective

 

: probability ratio, so

 

 

 

 

TRPO는 아래의 'surrogate' objective를 최대화하고, 이를 위에서 정의한 probability ratio를 적용해보면 다음과 같이 표현이 가능하다. (CPI: conservative policy iteration;)

 

equation(5)

 

constraint 없이 위 objective를 maximization하게되면 large policy update가 진행될 가능성이 있으므로,  monotonuous improvement를 보장할 수 없다. 따라서 probability ratio를 숫자 1에서부터 멀리 떨어져있는(기존 policy와 많이 다른) policy에 penalty를 준다. 결과적으로 아래의 modified surrogate objective function이 등장한다. 

 

equation(6)

ε: hyperparameter, default=0.2

 

위 surrogate objective function에서 min( , ) 내부 값의 의미는 다음과 같다.

(1) first term: 기존 L^CPI의 surrogate objective(equation(5))이며,

(2) second term: surrogate objective에 clipping probability ratio를 적용한 것이다. 

 

clipping은 [1-ε, 1+ε] 간격의 외부로 r_t가 이동하려는 incentive를 제거하는 역할을 한다. 결과적으로 얻게 된 clipped & unclipped surrogate objective를 비교해 최소값을 취함으로써 final objective는 lower bound를 형성하는 데에 의미가 있다. 이 방식은 어떻게 보면 probability ratio change가 objective를 향상시킬 때는 무시하고 objective를 악화시킬 때는 포함한다.

=> 요약하자면, lower bound를 취해 old policy와 new policy 사이 너무 큰 distance가 생기지 않도록 Loss에 대한 한계폭을 지정해준다. 

 

 

 

---

Adaptive KL Penalty Coefficient

clipped surrogate objective 대신 혹은 추가로 사용가능한 접근으로는, KL divergence에 대한 penalty를 사용할 수 있다. policy update마다 KL divergence의 target value를 달성하도록 penalty coefficient를 조정한다. 실제로 실험에서는 KL penalty가 clipped surrogate objective 보다 낮은 성능을 보였다고 한다. 

=> 기존 penalty method에서 penalty coefficient를 조정해주는 방식으로, clipping method에 비해 좋은 성능을 나타내지는 못했다. 

 

KL penalty 사용 경우, policy update마다 다음 과정을 거친다.

(1) mini batch SGD의 여러 epochs를 사용하여 KL-penalized objective를 최적화한다.

 

 

(2) 아래의 d를 계산하여 penalty coefficient을 조정한다.

 

 

β는 next policy update에 사용된다. 드물게 KL divergence와 d target의 차이가 현저하게 큰 경우가 존재하는데, 이는 β가 빠르게 조정되므로 크게 문제가 되지 않는다. 또한 알고리즘은 빠르게 조정되는 특성 때문에 위 식에서 heuristically하게 정한 1.5, 2 혹은 β hyperparameter initial value에 sensitive하지 않다. 

 

 

---

Algorithm

이전 섹션에서 언급되었던 surrogate loss function들은 typical policy gradient 실행에서 조금의 변경을 통해 계산 혹은 미분 가능하다. automatic differentation를 사용하는 실행을 위해서는 loss에 L^PG대신 L^CLIP or L^KLPEN를 사용하여 objective에 대해 stochastic gradient ascent를 수행시키면 된다. 

 

variance-reduced advantage-function estimator를 계산하기 위해 보통 state-value function V(s)를 사용한다. 이 때 policy와 value-function의 parameters를 공유하는 neural network architecture를 사용할 경우, 우리는 policy surrogate와 value-function error term를 섞는 loss function을 사용해야 한다. 또한 sufficient exploration을 보장하기 위해 entropy bonus를 추가하였다. 이러한 terms를 혼합하여, each iteration에서  approximtely maximized되는 다음의 objective를 얻을 수 있다. 

=> loss function L^CLIP이 policy surrogate + value function error + entropy bonus로 혼합된다.

 

c1, c2: coefficient

S: entropy bonus

: squared-error loss, equal to 

 

 

 

policy gradient 실행의 한 방식으로, recurrent neural network에 적합하게 사용되고있는 방법으로, policy를 T timestep(where T < episode length)만큼 sample을 모아 update하는 방식이다. 이 때, T timestep 만큼 보지 못하는 advantage estimaor가 요구된다. 

 

 

일반화하면, 아래의 truncated version of generalized advantage estimation을 사용할 수 있다. (when λ=1)

 

 

PPO algorithm은 fixed-length trajectory segment를 이용한다.

1. 각 iteration에서, N actors는 policy로 T timesteps의 data(T-length trajectory)를 수집한다.

2. T-timestep 만큼의 advantage estimate A_t를 계산한다. 

3. NT timestep data에 대해 surrogate loss L^CLIP+VF를 생성한다.

4. surrogate loss를 minibatch SGD로 K epochs만큼 optimize한다. 

 

 

 

---

Code