【強化学習】Experience Replayの理論

0. はじめに

開発している強化学習向けExperience Replayライブラリcpprbのサイトに書いたExperience Replayの理論に関する調査の日本語焼き直し記事です。

前回の論文調査記事はこちら

https://zenn.dev/ymd_h/articles/35d88f7d739651

1. Experience Replayとは

L. Lin^[1]によって1992年に提案（少なくとも命名^[2]）された手法のExperience Replay（経験再生）は、遷移（一般的には$\lbrace s_t,a_t,r_t,s_{t+1},d_t\rbrace$の組）を一時的に Replay Buffer（またはReplay Memory）と呼ばれる領域に保存しておき、後からその遷移をランダムに取り出して学習に用いる手法です。

Experience Replayを利用する主たる目的の１つにサンプル効率の向上があります。強化学習に用いる環境のトライ&エラーはコストが高いことが多く（例えば、高精度なシミュレーションは計算コストが高いですし、実世界でロボットを下手に動かすと壊れたり、周囲の人に危険がおよんだりします）、可能な限り一度収集した遷移を再利用することが望まれています。

L. Linは同じ論文の中で、現在の方策と異なる方策から取得した遷移を再利用すると学習の結果を歪めうるとも既に言及しています。これ以後、Experience Replayの性質に関する研究や、サンプル効率の向上のための様々な拡張が提案されてきました。

2. Experience ReplayにおけるOn-Policynessの影響

W. Fedus等^[3]は2020年にExperience Replayにおける on-policyness（今の方策と行動方策の近さ）の影響について実験を行いました。この論文の鍵となるメトリクスは遷移の歳 (age of transition) で、その遷移が生成されてから方策が何回更新されたかで定義されています。

通常、Replay Bufferはサイズが一定のリング・バッファ(Wikipedia)によって実装されているため、限界まで遷移が保存されている際には一番古い遷移が新しく入ってきた遷移によって上書きされます。そのためreplay ratio $\left (=\frac{\text{方策更新回数}}{\text{遷移生成回数}}\right )$ がReplay Buffer内に保存される最も古い遷移の歳を調整するのに良い指標となります。^[4]

実際、著者等の実験の結果はreplay ratioに依存しています。

• replay ratioを小さくすると性能が向上する
  • Replay Buffer内の最も古い遷移の歳を変化させず、Replay Bufferのサイズを大きくする
  • Replay Bufferのサイズを変化させず、Replay Buffer内の最も古い遷移の歳を若くする
• replay ratioを変化させず、Replay Bufferのサイズを大きくすると、性能は上がったり下がったり
  • 相反する2つの影響（Replay Bufferのサイズの増大による向上＋遷移の歳が古くなることによる劣化）によるもの

更に $n$-step 報酬を利用することで Replay Buffer のサイズ拡大時の性能向上幅を大きくすることができたとも報告しています。

3. Prioritized Experience Replay (PER)

最も有名なExperience Replay拡張の１つが、T. Schaul等^[6]によって2016年に提案されたPrioritized Experience Replay (PER)です。PERのポイントはTD誤差 $\delta _i$ の大きさを遷移の重要度 $p_i$ として利用することです。

この論文では重要度の定義方法として2つ提案されています。比例方式 $p_i=|\delta_t|+\epsilon$ と順位方式 $p_i=\frac{1}{\text{rank(i)}}$ で、$\epsilon$ は重要度0を避けるための正の小さな値で、$\text{rank}(i)$ は $|\delta_i|$ でソートした際の順位です。理論的には順位方式の方が外れ値に強く頑健であると考えられています。一方、実験の結果では両者に大きな差はなくcpprbを含む多くのライブラリが比例方式を採用しています。^[7][8][5:1]

遷移 $i$ を実際にサンプルする確率は次の式で表されます

$$P(i) = \frac{(p_i)^{\alpha}}{\sum _k (p_k)^{\alpha}}$$

$\alpha$ はどれだけ重要度を考慮するかのハイパーパラメータで $\alpha=0$ だと一様サンプリングになります。
非一様な確率で遷移をサンプルすることによって生じる確率の歪みは重点サンプリングに則って重みを調整することで補正されます。

$$w _i = \left ( \frac{1}{N} \frac{1}{P(i)} \right )^{\beta}$$

$N$ は保存されている遷移の数で、$\beta$ は補正度合いを表すハイパーパラメータです。

4. PERの理論的背景

A. Ang等^[9]は2021年に理論面から PER がなぜうまくいくのかについての説明を試みています。彼らはExpected Value of Backup (EVB) という指標に着目しました。EVBはある経験（遷移と同義） $e_k$ を学習した際の累積割引報酬和の増加量によって定義されます。

$$\begin{aligned} \text{EVB}(e_k) &= v_{\pi _{\text{new}}}(s_k) - v_{\pi _{\text{old}}}(s_k) \cr &= \sum _ a \pi _{\text{new}}(a\mid s_k)q_{\pi_{\text{new}}}(s_k,a) - \sum _ a \pi _{\text{old}}(a\mid s_k)q_{\pi_{\text{old}}}(s_k,a) \end{aligned}$$

ただし、$\pi _{\text{old}}$, $v_{\text{old}}$, $q_{\pi_{\text{old}}}$ はそれぞれ更新前の方策、価値関数、Q関数で、$\pi _{\text{new}}$, $v_{\text{new}}$, $q_{\pi_{\text{new}}}$ は更新後のものです。

この論文のポイントは、方策の更新が貪欲であるかぎりEVBの大きさの上限は定数倍したTD誤差の大きさによって抑えられるという点です。

$$|\text{EVB}(e_k)| \leq \alpha |\text{TD}(s_k,a_k,r_k,s_{t+1})|$$

ここで $\alpha$ は学習のステップ幅のパラメータです。
この不等式だけでは完全な説明にはなりませんが、PERの成功を部分的には説明することができると思われます。（少なくともTD誤差が小さい遷移を用いてもEVBをそんなには向上することができないことはわかります。）

5. 損失関数と非一様なサンプリングの関係

S. Fujimoto等^[10]は2020年に Experience Replayにおける損失関数と非一様なサンプリングとの関係性を明らかにしました。著者等は非一様なサンプリングの場合と『期待値』が等しくなる一様サンプリング下の損失関数を定式化しています。

$$\mathbb{E} _{D_1}[\nabla _Q \mathcal{L}_1(\delta _i)] = \mathbb{E}_{D_2} \left [ \frac{p_{D_1}(i)}{p_{D_2}(i)}\nabla _Q \mathcal{L}_1 (\delta _i)\right ] = \mathbb{E} _{D_2}[\nabla _Q \mathcal{L}_2(\delta _i)]$$

ただし、 $\nabla _Q \mathcal{L}_2 (\delta _i) = \frac{p_{D_1}(i)}{p_{D_2}(i)}\nabla _Q \mathcal{L}_1(\delta_i)$ です。

一般化した $\tau$ 次のノルム $\frac{1}{\tau}|\delta_i|^{\tau}$ をPERで採用した際の等価な一様サンプリング下の損失関数は次のようになります。

$$\mathcal{L}^{\tau} _{\text{PER}} (\delta _i) = \frac{\eta N}{\tau + \alpha - \alpha\beta} |\delta_i|^{\tau+\alpha - \alpha\beta},~\eta = \frac{\min _j |\delta_i|^{\alpha\beta}}{\sum_j|\delta_i|^{\alpha}}$$

$|\delta_i|^2$ を最小化することはTDターゲット $y(i) = r_i + \gamma \mathbb{E}[Q(s,a)]$ の平均値(mean)に最適化することに等しく、 $|\delta_i|$ を最小化することは中央値(median)に最適化することに等しくなります。そしてその中間、つまり$|\delta_i|^{\tau}~(\tau\in(1,2))$ を最小化することは両者の混合のような働きをします。

再び $\mathcal{L}^{\tau}_{\text{PER}}$ の式を見直してみると、PERにおいて $|\delta_i|^2$ を最適化することは $\tau=2$ であり $\beta \neq 1$の時 $\tau + \alpha -\alpha\beta > 2$ となり歪んだ最適化を行いバイアスを生んでしまっています。また $\beta$ の補正項も結局は $|\delta _i|$ の次数に取り込まれているので、適切に損失を設計すれば $\beta = 0$ として重み計算をそもそもしなくて良いと著者等は提案しています。

著者等は上記のPERにおけるバイアスを排除したPER拡張を Loss-Adjusted Prioritized Experience Replay (LAP) として次のように定義しました。

$$P(i) = \frac{\max(|\delta_i|^{\alpha},1)}{\sum _j \max(|\delta_j|^{\alpha},1)},~\mathcal{L}_{\text{Huber}}(\delta_i) = \begin{cases} 0.5(\delta_i)^2 & \text{if}~|\delta_i|\leq 1 \cr |\delta_i| & \text{otherwise} \end{cases}$$

基本的には $\delta_i$ の1次ノルム（絶対値）を利用しますが、0近傍の滑らかな傾き変化のために2次ノルムを $\delta_i \leq 1$ で採用したHuber誤差を利用しています。$\delta _i \leq 1$ 領域でバイアスを生まないように、$p_i = \max(|\delta_i|^{\alpha},1)$ により重要度を一定として一様にサンプリングとなるようにしています。

さらに、著者等はこのLAPと一様サンプリング下で等価な損失関数として、Prioritized Approximation Loss (PAL) も提案しています。

$$\mathcal{L}_{\text{PAL}}(\delta_i) = \frac{1}{\lambda}\begin{cases} 0.5(\delta_i)^2 & \text{if}~|\delta_i|\leq 1 \cr \frac{|\delta_i|^{1+\alpha}}{1+\alpha} & \text{otherwise} \end{cases},~\lambda = \frac{\sum _j\max(|\delta_i|^{\alpha},1)}{N}$$

この章の初めにも書きましたが両者は『期待値』が等価であって分散は異なります。実際のところ分散はPERで（＝重要度に応じて）サンプルを行う方 (LAP) が小さくなります。一方、一様サンプリングを利用 (PAL) すればPERの計算コストを排除することができます。

まとめ

Experience Replay の原論文から始めて近年の理論的な論文までを整理しました。
PERがうまくいく理論的な背景の一因や、PERを適切に利用する方法についてわかりました。
一方、Replay Buffer から取り出す遷移の選び方を本質的にどうすれば良いかはまだ不明瞭の認識です。（前回の論文調査記事に挙げたEROやNERSのように選び方を学習する手法はその課題へのアプローチだと思っています。）

cpprbの今後の開発としては LAP や PAL の対応をしようかと検討中です。

2021/12/3更新

収束速度($\neq$ 最終精度)の観点で、Replay Bufferからの遷移抽出を最適化する抽出確率分布の理論的な導出と、一定の条件下でTD誤差がその確率分布の良い近似になることに言及した論文 Large Batch Experience Replay (LaBER)についての紹介+実装記事を書きました。

https://zenn.dev/ymd_h/articles/9006c1ee1eb487

2021/12/11更新

Experience Replayの研究の傾向と個人の考察をまとめた記事を書きました。
https://zenn.dev/ymd_h/articles/8261cb7b9fb925

脚注

1. L. Lin, “Self-improving reactive agents based on reinforcement learning, planning and teaching”, Mach. Learn. 8, 293-321 (1992) https://doi.org/10.1007/BF00992699

2. （1992年と古いこともあり定かではありませんが、）Experience Replayを含む様々な手法を比較・議論した論文であり、Experience Replay（またはその原型）が初出ではない可能性があります。一方、論文中で「The most straightforward way of reusing experiences is what I call experience replay.」と記載しているとおりL. Linが初めてExperience Replayという名称を利用し、その性質を検証・議論し、その後定着したと認識しています。

3. W. Fedus et al., “Revisiting Fundamentals of Experience Replay”, ICML (2020) (arXiv)

4. Reverb^[5]にはreplay ratioを制限する仕組みがあります。拙著の紹介記事も参照

5. A. Cassirer et al., “Reverb: An efficient data storage and transport system for ML research”, (2020) https://github.com/deepmind/reverb (code)

6. T. Schaul et al., “Prioritized Experience Replay”, ICLR (2016) (arXiv)

7. D. Prafulla et al., “Open AI Baeslines”, (2017) https://github.com/openai/baselines

8. E. Liang et al., “RLlib: Abstractions for Distributed Reinforcement Learning”, ICML (2018) (arXiv, code)

9. A. Ang et al., “Revisiting Prioritized Experience Replay: A Value Perspective” (2021) arXiv:2102.03261 (残念ながらICLR2021で不採択になっています。)

10. S. Fujimoto et al., “An Equivalence between Loss Functions and Non-Uniform Sampling in Experience Replay” NeurIPS (2020)(arXiv)