【論文】Proximal Policy Optimization Algorithms (PPO, 2017)

[Proximal Policy Optimization](https://blog.openai.com/openai-baselines-ppo/ "Proximal Policy Optimization")

<blockquote class="twitter-tweet" data-lang="ja"><p lang="en" dir="ltr">Releasing PPO, a new class of reinforcement learning algorithms that excel at simulated robotics tasks: <a href="https://t.co/MsGrJDCfxK">https://t.co/MsGrJDCfxK</a> <a href="https://t.co/MC8rL3lB0c">pic.twitter.com/MC8rL3lB0c</a></p>&mdash; OpenAI (@OpenAI) <a href="https://twitter.com/OpenAI/status/888068607804022785?ref_src=twsrc%5Etfw">2017年7月20日</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

# 概要
- 環境とのやり取りによるデータの取得と、「代理」目的関数の最適化を交互に繰り返す、方策勾配法ベースの手法を提案する
- 提案法は PPO と名付けた。TRPO のいいところを受け継ぎつつ、実装は容易で、より一般的で、(実験的に)サンプル効率が良い
- PPO はロボット制御のシミュレーションでも、Atari でも従来手法よりも良い結果を出すことができた

# 導入
- 深層強化学習では、DQN／(生の) 方策勾配法／TRPO／自然方策勾配法 が先行しているが、大きなモデルや並列実装に対してスケールしたり、データ効率が良かったり、ロバスト (＝ハイパーパラメータ調整なしで色々な問題が解ける) な手法を開発する余地がある
    - (関数近似の) Q学習は連続状態に弱かったり理論解析が進んでいない
    - 生の方策勾配法はデータ効率性とロバスト性が悪い
    - TRPO は複雑でドロップアウトやパラメータ共有といったアーキテクチャに対応できない
- 比をクリッピングすることで、方策を悲観的に評価するような新しい目的関数を作り、TRPO を改善した新しい手法を提案する
- 方策の最適化は、方策からのデータサンプリングと数エポックぶんの最適化を繰り返すことでおこなう
- 提案法 (以後 PPO と呼ぶ) は連続制御タスクの性能もAtariの性能も良かった

# 背景：方策最適化

## 方策勾配法
<img width="944" alt="image.png" src="https://qiita-image-store.s3.amazonaws.com/0/62450/73ba37c4-2a06-0660-5448-8a8dfdbd9077.png">

という勾配に従って勾配法をおこなう。ただし、

- $\pi_\theta$ は確率的方策
- $\hat{A_t}$ は時刻tでのアドバンテージの推定量
- $\hat{\mathbb{E}}_t$ は期待値のサンプル平均近似

自動微分のために目的関数を陽に定めたいなら次を用いれば良い：

<img width="946" alt="image.png" src="https://qiita-image-store.s3.amazonaws.com/0/62450/5a332836-8bdf-256d-afb3-08d71beee15e.png">

## Trust Region Methods

TRPO では、目的関数 (「代理 (surrogate)」目的関数) は更新量に制約がかかっている：

<img width="943" alt="image.png" src="https://qiita-image-store.s3.amazonaws.com/0/62450/038f37b3-7e86-20c0-598a-b5196ba64e38.png">

これは、目的関数に線形の近似を、制約に2次の近似を置くと、共役勾配法で効率的に解くことができる。

TRPO を正当化する理論は、実際には制約ではなく正則化による方法を提示する：

<img width="950" alt="image.png" src="https://qiita-image-store.s3.amazonaws.com/0/62450/2dfe0e9f-3256-88c6-6d26-f468915a2a4f.png">

上式の目的関数,は、KLダイバージェンスの期待値ではなく最大値を取るため、方策 $\pi$ の悲観的評価 (下限) をなしている。[^1]

## Clipped Surrogate Objective

<img width="170" alt="image.png" src="https://qiita-image-store.s3.amazonaws.com/0/62450/32e8005f-5336-b91a-85bb-93e95290767f.png"> と書くことにすると、TRPO の代理目的関数は：

<img width="863" alt="image.png" src="https://qiita-image-store.s3.amazonaws.com/0/62450/5ff7cffc-4185-a85d-8f77-a2d44a86d45c.png">

"CPI" は "conservative policy iteration" (保守的方策反復) のこと。
これだけだと更新量が大きくなりすぎるので、 $r_t(\theta)$ に制約をかける。

提案法 PPO の主な目的関数は次式：

<img width="874" alt="image.png" src="https://qiita-image-store.s3.amazonaws.com/0/62450/ab55ff51-c3cb-48b8-e33e-6e7d4f0e64bf.png">

![image.png](https://qiita-image-store.s3.amazonaws.com/0/62450/13296051-5077-7740-45dc-beaaebde3983.png)

$\epsilon = 0.2$ はハイパーパラメータ。
(7) 式の min は悲観的評価を表している。

# 適応的 KL 罰則係数 (Adaptive KL Penalty Coefficient)

$L^{\text{CLIP}}$ の代わりに、もしくはそれに加えて、次のような手法も考えた[^2] (が、CLIP のほうが精度が良かった)：

<img width="863" alt="image.png" src="https://qiita-image-store.s3.amazonaws.com/0/62450/9195ce46-9c04-37e8-4803-b2a981aea380.png">

1.5 とか 2 みたいな数字はヒューリスティックに決めた。

# アルゴリズム

分散を軽減するために $L_t^{\text{VF}} = (V_\theta(s_t) - V_t^{\text{targ}})^2$ を[^3]、
探索を促すためにエントロピー[^4] $S[\pi_\theta]\(s_t\)$ を導入して、
次の式を最大化する：

<img width="853" alt="image.png" src="https://qiita-image-store.s3.amazonaws.com/0/62450/c251ef42-06ba-41cd-db5c-bc8a5dd2c2c7.png">

さらにアドバンテージ関数は T ステップ分を考える：

<img width="862" alt="image.png" src="https://qiita-image-store.s3.amazonaws.com/0/62450/63cc9e6a-06f1-26df-ee48-0aaa3ebce06a.png">

さらにさらに、(10)式は次のように一般化できる ($\lambda=1$ で一致する)：

<img width="858" alt="image.png" src="https://qiita-image-store.s3.amazonaws.com/0/62450/1f5acaf7-af6f-eb8c-3308-29b9c0b4b57f.png">

PPO では、N 個の actor を並列に T ステップ走らせてデータを集めて勾配法を実行している。

# 実験

## 代理目的関数の比較

<img width="879" alt="image.png" src="https://qiita-image-store.s3.amazonaws.com/0/62450/557e95ff-1a7d-871a-8205-25c133c33763.png">

比較する各手法でそれぞれハイパーパラメータを探したため、実験対象の環境は軽いものを利用した。
つまり、OpenAI Gym の MuJoCo を利用した7種類のロボット制御タスク。
各ハイパーパラメータはそれぞれ100万タイムステップぶんの更新をおこなっている。
各タスクのスコアは、ランダム方策によるスコアが0で最高スコアが1になるように調整している。

方策の近似は、64ユニットの全結合層を2層積み、tanh 活性化でガウス分布の平均と標準偏差を出力するようなニューラルネットを用いた。[^5]
方策と価値のネットワークのパラメータは共有せず、エントロピー項は利用していない。

## 連続制御タスクを扱える他の手法との比較

<img width="880" alt="image.png" src="https://qiita-image-store.s3.amazonaws.com/0/62450/459e9f50-9a8c-bb1f-ef15-7b1379748c16.png">

PPO はさっきの実験で一番良かったハイパーパラメータを利用した。[^6]

## ヒューマノイドの走行と操舵

PPO が高次元の連続制御タスクにも強いことを示すために、ヒューマノイドに石を投げつけながら、走行・操舵・起き上がりを学習させた。

動画は [公式](https://blog.openai.com/openai-baselines-ppo/) にある。石をたくさん投げつけられてかわいそう。

## Atari での比較

<img width="823" alt="image.png" src="https://qiita-image-store.s3.amazonaws.com/0/62450/285c734b-2a77-acb0-e0f9-351eda60eb81.png">

PPO は、離散行動である Atari でも良い結果が得られている。

# 参考資料
- [Proximal Policy Optimization](https://blog.openai.com/openai-baselines-ppo/ "Proximal Policy Optimization")
- [\[1707.06347\] Proximal Policy Optimization Algorithms](https://arxiv.org/abs/1707.06347 "[1707.06347] Proximal Policy Optimization Algorithms")
- [【強化学習】実装しながら学ぶPPO【CartPoleで棒立て：1ファイルで完結】 - Qiita](https://qiita.com/sugulu/items/8925d170f030878d6582 "【強化学習】実装しながら学ぶPPO【CartPoleで棒立て：1ファイルで完結】 - Qiita")

[^1]: ここらへんが言っていることは、たぶん「期待値よりも最大値のほうが大きいのだから、最大値で評価する式のほうが下限が落ちるはずだ。つまり悲観的評価だ」くらいの意味だと思うが、ちょっと自信がない
[^2]: 目的関数に KL が追加されて、その係数が $\beta$ であるが、それがアルゴリズムの第2ステップで適応的に修正されていく。だから「適応的 KL 罰則係数」と言っている
[^3]: $V_t^{\text{targ}}$ はDQNとかで使われている target value、つまりちょっと前のパラメータによる推定値のことだろうか？
[^4]: 方策に関するエントロピーの意だと思われる
[^5]: TRPO の論文と同じようにやっているらしい。つまり、最終的に出力したいベクトルと同じ次元の平均と標準偏差を出力する (つまり次元数は2倍となる) ようなネットワークを作り、その平均と標準偏差のガウシアンから値をサンプリングするということだと思われる。が、TRPO をちゃんと読んでいないので自信がない
[^6]: さらっと「A2C が A3C より同じかまたは良かった」とか書いてあって、強化学習がいよいよもって何もわからん