深層強化学習手法R2D2を解説する

#はじめに
はじめまして。今回は[Recurrent Experience Replay in Distributed Reinforcement Learning](https://openreview.net/forum?id=r1lyTjAqYX)というICLR2019査読中の論文(古いバージョンと2018/12/21に更新されたバージョン)を読んだのでご紹介したいと思います。
この論文ではR2D2という新しい深層強化学習手法を提案し、Recurrent Networkを用いる場合のExperience Replayのやり方を確立しました。結果的にAPE-X[^1]を大きく上回る学習結果となり、SOTA(State Of The Art)を達成しました。今回このR2D2という手法についてみなさんと共有したいと思います。

#R2D2
R2D2はAPE-Xを改良した手法になります。よって、Nature版DQN[^2]に対して以下のものを適用したものになります。

- Double DQN[^3]
- Dueling Network[^4]
- Prioritized Replay[^5]
- Multi-Step Learning[^6]
- 分散型強化学習

##APE-Xとの違い
基本構造はAPE-Xと同じですが、いくつか変更点があるので順に解説していきます。

###Recurrent Networkを用いる
R2D2ではRecurrent Networkの一種であるLSTM[^7]を用います。LSTMブロックを挿入する箇所はDueling Networkの畳み込み層の後ろです。よって、LSTMブロックの後ろにアドバンテージを出力する全結合層と状態価値を出力する全結合層がつながる形になります。

###リワードクリッピングとloss-of-life-as-episode-endをやめる
R2D2ではリワードクリッピングとloss-of-life-as-episode-end(ライフポイントを失った時をエピソードの終端にする)をやめます。これにより、大きな報酬もクリップされずに扱うことができるようになります。また、ライフポイントを失うとリスポーンしたりするので、その不連続性を回避するためにライフポイントを失った時をエピソードの終端にしていましたが、これは本来環境が定義しているエピソードの終端ではありません。従来手法ではいずれも学習を安定させるために行われてきましたが、より自然な学習をするためにはこれらの撤廃が望まれます。

###経験データのため方
Recurrent Networkを用いるため、経験データ(本記事では(状態,行動,報酬,次の状態,終端フラグ)のセットのことを言います)をシーケンシャルに一定数集めて一つの経験データとして扱います。本記事ではこれをシーケンシャル経験データと呼ぶことにします。つまり、シーケンス長が10であった場合、10個の経験データを時系列順に集め、それで一つのシーケンシャル経験データとし、これがミニバッチ個選択されて学習に使用されるということです。

###n-step target valueの計算にrescaling関数を用いる
rescaling関数$h(x)$が新たに提案され、これを用いてn-step target value($\hat{y_t}$)を計算します。
$$
\begin{align}
h(x) &= \mathrm{sgn} (x)\left(\sqrt{|x|+1}-1\right) + \epsilon x \\\
\hat{y_t} &= h\left(\sum_{k=0}^{n-1} \gamma ^kr_{t+k} + \gamma ^n h^{-1}\left(Q(s_{t+n},argmax_a Q(s_{t+n},a;\theta); \overline{\theta})\right)\right)
\end{align}
$$
ここで、$t$はタイムステップ、$n$はステップ数、$\theta$はその時のネットワークの重み、$\overline{\theta}$はターゲットネットワークの重みを表します。$\mathrm{sgn}$は符号関数です。$\epsilon$はおそらく定数だと思われますがが、この値については不明です。
論文ではrescaling関数についてほとんど言及されておらず謎が残りますが、リワードクリッピングの代わりにこれを用いたと書かれているので、リワードクリッピングのように報酬を[-1,1]にばっさりスケーリングするのではなく、target value自体が大きな値を取りえるが、ちゃんと学習できるようなスケーリングになっていると考えられます。

###Priorityの計算方法
APE-Xでは以下の式を用いて、**経験データ一つ一つに対して**Priority(p)を与えていました。
$$
\begin{align}
\delta &= \sum_{k=0}^{n-1} \gamma ^kr_{t+k} + \gamma ^n Q(s_{t+n},argmax_a Q(s_{t+n},a;\theta);\overline{\theta}) - Q(s,a;\theta)\\\
p &= |\delta|
\end{align}
$$
しかしR2D2ではシーケンシャル経験データをミニバッチ個選ぶので、**シーケンシャル経験データ一つ一つに対して**Priorityを与えなければなりません。よって、Priorityの計算方法を先ほどの$\hat{y_t}$を用いて次のように変更します。
$$
\begin{align}
\delta &= \hat{y_t} - Q(s_t,a_t;\theta) \\\
p &= \eta\ max_i |\delta_i| + (1-\eta)|\overline{\delta}|
\end{align}
$$
ここで、$\eta$は[0,1]の定数、iはReplay Memory中のシーケンシャル経験データのインデックスです。また、$|\overline{\delta}|$はデルタの絶対値の平均を表します。つまり、i番目のシーケンシャル経験データの中で最も大きい$|\delta|$とその平均を用いてPriorityを決定するということです。

##Experience Replayのやり方
R2D2の最も重要かつ斬新なポイントはExperience Replayのやり方にあります。このセクションでは従来から存在する問題点とR2D2で用いられる提案手法を解説していきます。

###従来から存在する問題点
Recurrent Networkを用いる場合、「シーケンシャル経験データをミニバッチ個選びました。で、始めの内部状態はどうするの？」という問題が生じます。これについては先行研究のDRQN[^8]という手法で以下の二つの方法が検証されていました。

1. 始めの内部状態をゼロで初期化する
これは非常にシンプルな方法です。しかし、本来の始めの内部状態からほぼ間違いなくずれているのは想像に難くないと思います。ですが検証の結果、内部状態をゼロで初期化し、しばらくネットワークにシーケンシャルにデータを流し続けると、次第に本来の内部状態に復帰してくることが分かりました。

2. シーケンス長を1エピソードにする
エピソードの始めはゼロで初期化するので、この方法であれば先の問題は解決することができます。しかし、環境にもよりますがシーケンス長がかなり長くなることが予想されるため、これでは一つのシーケンシャル経験データの学習を終えるまでにかなり時間がかかります。さらに、あるエピソードでは大量の正の報酬が得られたが、別のエピソードでは大量の負の報酬を得たという状況では、それぞれのエピソードでの勾配が全く違うものになります。つまり、勾配の分散が大きくなりやすいとこうことです。これは学習の安定性に悪影響を及ぼします。

###R2D2のExperience Replay
先の先行研究を踏まえ、R2D2では内部状態もReplay Memoryに保存しておきます。これであればシーケンシャル経験データをミニバッチ個選んだあと、始めの内部状態を正確に復元することができそうです。しかし、本当に**正確に復元する**ことができるのでしょうか？答えは否です。理由は**今**のネットワーク(の重み)にとっては本当の内部状態ではないからです。Replay Memoryに蓄えられたシーケンシャル経験データは昔のネットワークの重みの時に得られたものから最新のネットワークの重みの時に得られたものまで存在します。したがって古いシーケンシャル経験データに保存されていた内部状態は、今のネットワークでは本当の内部状態ではないのです。論文ではこのことを「recurrent state staleness」と呼んでいます。
しかし、先の先行研究の1番の手法で行ったような内部状態をゼロで初期化するというアプローチよりは、かなり正確な内部状態を復元できることが期待されます。

####Burn-in
先の先行研究の1番の手法を思い出してください。この手法では、しばらくネットワークにシーケンシャルにデータを流し続けると、次第に本来の内部状態に復帰してくることが分かりました。このようにして内部状態を本来の内部状態に復元することを論文では「Burn-in」と呼んでいます。そしてこれをrecurrent state stalenessの軽減に用います。したがって、最終的に以下のようにExperience Replayを行います。

1. Replay MemoryからPriorityに基づいてシーケンシャル経験データをミニバッチ個サンプリング
2. サンプリングしたシーケンシャル経験データから始めの内部状態を取り出し、ネットワークにセット
3. Burn-in期間を設け、シーケンス長の内始めのBurn-in期間は学習を行わずにデータを流すだけにし、より正確な内部状態の生成に使う
4. Burn-in期間が終了した後、シーケンスの残りの部分でのみ学習を行う

この新しいExperience Replayのやり方がR2D2の最も重要なポイントです。

##時系列的特徴量を抽出することの意義
Recurrent Networkを用いて時系列的特徴量を抽出することでQ値の推定材料が増えます。よって、より正確なQ値の推定ができることが期待できます。また、POMDP(部分観測マルコフ決定過程)ではQ値は信念状態を参考に決定され、信念状態は過去の状態遷移の履歴によって決定されます。つまり、Recurrent Networkを用いれば内部状態として過去の履歴を保持することができるので、POMDPに対応することができるということです。

##実験結果
![1.png](https://qiita-image-store.s3.amazonaws.com/0/347208/18f3b999-0a4d-3177-50d5-66e4f8150f74.png)
この図は論文より抜粋したものです。従来の手法と比べて非常に高いスコアを獲得できています。素晴らしいですね。
最後に論文で示されたハイパーパラメータをまとめておきます。ここに記載されていないハイパーパラメータは全てAPE-Xと同じです。

|ハイパーパラメータ|値|
|:--------------|:--:|
|アクターの数|$256$|
|アクターのパラメータを更新する間隔|$400$ environment steps|
|シーケンス長|$120$|
|Burn-in期間|$40$|
|Replay Memoryサイズ|$4\times10^6$|
|Priority exponent|$0.9$|
|割引率|$0.997$|
|ミニバッチサイズ|$64$|
|オプティマイザ|Adam(学習率=$10^{-4}$,$\epsilon=10^{-3}$)|
|ターゲットネットワークの更新間隔|$2500$ learner steps|
|LSTMのユニット数|$512$|
|Priorityの計算式の$\eta$|$0.9$|
|Multi-Stepのステップ数$n$|$5$|
|Importance sampling exponent|$0.6$|

ちなみに古いバージョンの論文ではImportance samplingは効果がなかったからやらないとのことでしたが、レビュワーの意見をもとにもう一度実験してみたら学習を安定させる効果があったのでやっぱりやるとのことです。

#おわりに
深層強化学習は非常に面白く、考えれば考えるほど新たな発見やひらめきがある分野です。
また何か面白い知見があれば積極的にみなさんと共有していこうと思います！
最後までご覧いただき、ありがとうございました。質問、感想、間違いの指摘等ありましたら遠慮なくコメントをください。

#参考文献
[1][【深層強化学習】Ape-X 実装・解説](https://qiita.com/omuram/items/bb7d463d8177cb395bb7)
APE-Xについて非常に詳しく解説されています。実装までされているので、とても分かりやすいと思います。

[2][深層強化学習アルゴリズムまとめ](https://qiita.com/shionhonda/items/ec05aade07b5bea78081)
深層強化学習全体の手法が非常にわかりやすくまとめられています。ぜひ読んでいただきたい記事です。

[3]これからの強化学習, 牧野貴樹 他著, 森北出版, 2016
僕が強化学習の基礎を学んだ本です。そこまで詳しくは書かれていませんが、DQNやPrioritized Replayも載っています。強化学習の基礎を学びたい方にぜひお勧めしたい一冊です。

[^1]: [Distributed Prioritized Experience Replay [DeepMind, 2018]](https://arxiv.org/abs/1803.00933)
[^2]: [Human-level control through deep reinforcement learning [DeepMind,2015]](https://www.nature.com/articles/nature14236)
[^3]: [Deep Reinforcement Learning with Double Q-learning [DeepMind, 2015]](https://arxiv.org/abs/1509.06461)
[^4]: [Dueling Network Architectures for Deep Reinforcement Learning [DeepMind, 2015]](https://arxiv.org/abs/1511.06581)
[^5]: [Prioritized Experience Replay [DeepMind, 2015]](https://arxiv.org/abs/1511.05952)
[^6]: [Reinforcement learning: An introduction [Sutton, 1998]](https://web.stanford.edu/class/psych209/Readings/SuttonBartoIPRLBook2ndEd.pdf)
[^7]: [Long short-term memory [Hochreiter, 1997]](https://www.bioinf.jku.at/publications/older/2604.pdf)
[^8]: [Deep Recurrent Q-Learning for Partially Observable MDPs [Hausknecht, 2015]](https://arxiv.org/abs/1507.06527)