TRPO와 PPO 알고리즘의 개념

 앞선 글들에서 소개했듯이, 강화학습은 주어진 Environment에서 State을 기준으로, 최고의 Action을 학습해나가는 과정이다. State에서의 Action을 통한 결과를 반영하여 (State, Action) = (s,a)의 관계 Q function을 점수화하는 Value-Based 학습, Action을 결정하는 Policy 자체를 학습시켜 나가는 Policy-Based 학습이 있다. 각각의 장단점을 갖고 있으며, 그 카테고리 안에도 State와 Action이 Discrete or Continuous 여부 등에 따라 여러 모델들이 파생된다. 그 중, 이번 글에서 소개할 Proximal Policy Optimization Algorithm (PPO) [1]은 이름에서 알 수 있듯이 Policy-Based Algorithm이다.

 PPO가 중요한 이유는, State of the Art (SOTA) 알고리즘인 동시에 대부분의 환경에서 어지간한 알고리즘은 다 이겨버린다는 특성 때문이다. 2017년에 등장한 만큼, SOTA라고 부르기는 살짝 민망하지만, 2021년 9월 현재, 5 천회 넘게 인용이 되었고, 이후에 나오는 RL 알고리즘을 상회하는 결과들도 많이 보여준다.

 

Trust Region Policy Optimization (TRPO)

 PPO를 설명하기에 앞서, Trust Region Policy Optimization (TRPO) [2]을 간단하게 소개한다. PPO를 설명하다 말고 왜 TRPO를 설명하는지는 Concept과 유도과정이 비슷하지만, 몇 가지 차이를 보이는 알고리즘이기 때문이다. TRPO의 Concept은 'Trust Region (믿을만한 구역)'에서만 Update하겠다는 뜻이다. 대부분 RL은 아래 식처럼 보상의 Expectation을 최대화하는 방향으로 학습이 되는데, 이 때 policy 파이를 직접 찾아나가는 과정이 Policy-based Algorithm이다.

Expectation of original policy

 이 때, Kakade & Langford (2002)의 이론과 TRPO의 Appendix에 따르면, new policy 파이'를 다음과 같이 나타낼 수 있다. 이 때, new policy 파이'에서 Sampling을 해야 하는데, 모르는 New Policy에서 Sampling한다는 것이 쉽지 않다.

Expectation of new policy

 New Policy 파이'에서 Sampling한 위의 eta 식을 조금 간단하게 만들기 위해 Local point에서의 최적화 문제로 바꾸는  Conservative Policy Iteration을 통해 아래와 같은 식을 유도할 수 있다. 이 과정에 복잡한 수학적인 증명이 되어있으니 [2]에서 하나씩 따라가보면 된다. 이렇게 구한 L을 Maximize하는 new policy 파이'를 찾아나가는 과정으로 policy 최적화가 이루어진다.

Local appoximation of new policy

 여기서 Trust region이라 함은 eta를 안정적으로 증가시키기면서, Train에 적합한 적당히 큰 step size를 만족하는 영역으로 constraint로 반영했고, TRPO는 이 영역에서만 Train을 하기 때문에 안정적인 RL 학습이 가능하다는 Concept이다.

Objective Function

 여기서 문제는 이 Penalty로 사용할 constraint가 모든 state에 대해서 다 만족을 해야하는데, 현실적으로 모든 state에 대한 KL Divergence계산을 하는 것은 현실적이지 않기 때문에, 이를 practical하게 바꾸기 위해, Sampling-based Estimation인 몬테카를로 기법을 사용하여 다음과 같은 surrogate objective function을 최적화한다.

Surrogate Objective Function with Monte-Carlo

 위의 Objective Function을 Maximize하기 위한 Policy의 paramater인 세타 값을 찾기 위해, KL divergence의 Hessian을 구하고, 이를 기반으로 Fisher Information Matrix를 구하여, optimize를 한다. 상당히 어려운 내용이 나왔지만, 여기서 주목할 점은 Hessian을 구한다는 점이다. Hessian을 구한다는 것은 2차 미분 값들을 구한다는 뜻인데, 이 부분이 TRPO와 PPO의 차이점 중 하나다. TRPO는 2차 미분을 구해야하지만, PPO는 1차 미분만으로도 approx.가 가능하도록 만들어져있다.

 

Proximal Policy Optimization Algorithm (PPO)

 PPO는 논문의 Intro.부터 TRPO의 복잡한 계산을 단순화시키기 위한 목적을 드러낸다. TRPO의 Surrogate Objective Function을 푸는 과정이 복잡하니, Clipping 등의 방법으로 단순화 시켜, First-order (1차 미분)으로 aprroximate하자는 내용이다. TRPO에서는 Trust Region을 만족하기 위한 Constraint를 정의하고, Surrogate Objective Funtion을 구했는데, PPO에서는 constraint를 단순하게 Clipping 해버린다. 입실론 값은 hyper-parameter로 0.1 이나 0.2 정도를 사용한다고 한다.

Clipping은 일정 영역을 벗어나는 부분은 constant 값으로 잘라주겠다는 의미인데, A<0 일때는 안 좋은 행동이니까 그 행동을 적게 해야되기 때문에 r을 줄여야 한다. 그런데 무한정 줄이는게 아니라 Clipping 된 경계까지만 줄인다. 이런 원리로, State-Value과 Exploration을 위한 Action Entropy를 반영한 최종적인 Objective Function을 최적화시키게 된다.

PPO의 Objective Function

 PPO는 Advantage Actor-critic의 변형으로, N개의 Actor가 각자가 T Time-Step만큼 Action을 하면서 Data를 쌓고, 각 Time-Step에 대해서 Advantage를 계산한다. 몇 번의 Epoch동안 L-Clip (theta)로 계속 Update를 한다. 이 과정에서 Clipping으로 믿을 수 있는 부분에서만 update를 하기 떄문에, 안정적으로, 쌓은 데이터를 여러 번 사용할 수 있다. 

 

Conclusion

 PPO 논문에서는 Trust Region에서의 Training을 통해 Stability를 가지면서, TRPO 대비 적은 Complexity를 가지고, 다른 모델 대비 좋은 성능을 보여준다. Continuous Action, Discrete Action에 모두 사용할 수 있다는 점, 그리고 대부분의 환경에서 좋은 성능을 보인다는 측면에서 가장 먼저 고려해야할 RL 모델로 손꼽히고 있다. RL의 대표적인 라이브러리인 Stable baseline2 [3]에 사용하기 쉬운 PPO 알고리즘도 있기 때문에, 자신한테 어떤 RL 모델이 맞는지 헷갈리는 사람에게 가장 먼저 사용해볼 알고리즘으로 PPO를 추천한다.

 

Reference

[1] J. Schulman, S. Levine, P. Abbeel, M. Jordan, and P. Moritz. Trust region policy optimization. In Proceedings of The 32nd International Conference on Machine Learning, pages 1889–1897, 2015.

[2] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.

[3] https://stable-baselines.readthedocs.io/en/master/modules/ppo2.html

PPO2 — Stable Baselines 2.10.2 documentation