📑

【強化学習】Experience Replay の研究の傾向とその考察

2021/12/11に公開

この記事は強化学習 Advent Calendar 2021の12/11の記事です。

0. はじめに

強化学習は（一般的には）学習に必要なデータをプログラム自身が能動的に探索する必要があります。そのため、深層学習のネットワークの大きさや形状だけでなく、探索・学習の方法などロジック全体が重要です。気をつけるべき点や工夫できる点が多岐に渡るため、非常に難しいと同時にとてもおもしろいろ感じています。

この記事では、私が興味を持ってライブラリを開発したり、定期的に（？）記事を書いたりしているExperience Replay (経験再生) について、個人的に感じている近年の研究のポイントについて書こうと思います。

1. Experience Replay研究の着目点

強化学習（のoff-policyな手法）では、遷移（一般には $(s_t, a_t, r_t, s_{t+1}, d_t)$ の組）をReplay Bufferに保存しておき、後から『ランダム』に取り出してニューラルネットワーク等のポリシーを学習させることで、サンプル効率を高めるExperience Replay (経験再生)^[1] が広く行われています。

2016年のT. Schaul等のPrioritized Exprerience Replay (PER)^[2]を始めとして、様々なExperience Replay拡張が提案されてきていますが、着目している課題及び改良点は大きく分けて2点存在していると私は考えています。

最適方策への収束性 (= 最終精度・バイアス)
収束速度 (= 学習ステップ数・バリアンス)

2. 最適方策への収束性

2.1 概要

深層強化学習では、最適方策への収束が保証されていないので、いくら学習しても最適方策に到達しない、更にひどい時には学習を続けると精度が降下して学習に失敗することが起こりえます。

特に、「関数近似」・「Bootstrap」・「Off Policy (=現在の方策と行動方策の乖離)」の3要素が揃うことをDeadly Triad^[3]と呼び、(深層)強化学習が失敗しやすくなる要因として挙げられています。

Deadly Triadの一言で片付けるのも味気ないので、もう少し深堀りしようと思います。

テーブル形式のQ学習においては、次の式のようにTD誤差を利用してQ値を更新できますが、すべての $(s, a)$ ペアにおいて十分にQ値が更新され (+ 適切に係数 $\alpha$ を減少させ) 続ける限り、行動方策に寄らず最適なQ値(=最適方策)に収束することが理論的に保証されています。

Q(s_i, a_i) \gets Q(s_i, a_i) + \alpha \left(r_i + \gamma \max _{a^{\prime}}Q(s_i^{\prime}, a^{\prime}) - Q(s_i, a_i)\right)

一方で、関数近似（特に2015年のDQN以降の深層Q学習）では次の式のとおりTD誤差を最小化するようにネットワークを学習させます。これは上のテーブル形式のアナロジーではありますが、根本的に異なるアルゴリズムであり最適方策への収束は理論的には保証されていません。

w \gets w - \alpha \frac{\partial}{\partial w} \sum_{i\in \mathcal{B}}\left( r_i + \gamma \max _{a^{\prime}} Q_{\bar{w}}(s_i^{\prime}, a^{\prime}) - Q_w(s_i, a_i)\right)^2

式を見てもらえばわかるように、これは学習に利用する遷移の（重み付き）データ分布によって収束先が変わってきます。何らかの策を講じないのであれば、Replay Bufferの中にある遷移の分布に対して最適な方策を目指すことになります。

2.2 関連研究

関連する研究をいくつかさらっと要点に絞って紹介します。
ここには書ききれないので、詳細は原論文を確認ください。
また「★」マークのついたアルゴリズムは別途もう少し詳しい紹介記事を書いています。

(1) Combined Experience Replay (CER)

S. Zhang and R. S. Sutton, "A Deeper Look at Experience Replay", NIPS 2017 Deep Reinforcement Learning Symposium (arXiv)

CERでは、Replay BufferからサンプルしたOff Policyな遷移に、今のOn Policyな遷移を1つ加えて、ミニバッチ全体を少しOn Policyに寄せます。

Replay Bufferからbatch_size -1個の遷移をサンプル
行動方策が最後に観測した遷移を1個加えてミニバッチを構成する

(2) Remember and Forget for Experience Replay (ReF-ER) ★

G. Novati and P. Koumoutsakos, “Remember and Forget for Experience Replay”, ICML (2019)(arXiv, code)

ReF-ERでは、現在の方策とあまりに離れている行動方策から取得された遷移の利用を制限することで、サンプル効率を向上させます。

重要度(importance)を次のように定義: $\rho _t = \frac{\pi (a_t\mid s_t)}{\mu_t(a_t\mid s_t)}$ ただし、 $\pi$ : 現在の方策、 $\mu _t$ : 行動方策
$\frac{1}{c_{\text{max}}} < \rho _t < c_{\text{max}}$ なら "near-policy"、それ以外なら "far-policy"
ルール1: far-policy の時、損失のgradientを0にする。 $\hat{g}(w) \to 0$
ルール2: KLダイバージェンスによる正規化項を加える。
$\hat{g}^D (w) = \mathbb{E}[\nabla D_{\text{KL}}(\mu _k (\cdot \mid s_k) \| \pi ^w(\cdot \mid s_k))]$
$\hat{g}^{\text{ReF-ER}}(w) = \beta \hat{g}(w) + (1-\beta)\hat{g}^D(w)$
- $\beta$ は焼きなまし項
- $\beta \gets \begin{cases}(1-\eta)\beta & \text{if}~\frac{n_{\text{far}}}{N} > D \cr (1-\eta)\beta + \eta & \text{otherwise}\end{cases}$
- $\eta$ : 学習率、 $n_{\text{far}}$ : far-policyの遷移の数、 $N$ : 全遷移の数、 $D$ : ハイパーパラメータ

(3) Attentive Experience Replay (AER) ★

P. Sun et al., “Attentive Experience Replay”, AAAI (2020) 34, 5900-5907

AERでは、Replay Bufferから学習に利用するミニバッチの $\lambda$ 倍の遷移を抽出してから、On Policyな今の遷移との「状態 (Observation)」の類似度を計算し、類似度が高いものでミニバッチを構成して学習に利用します。

ミニバッチのサイズ $k$ の $\lambda$ 倍の $k\times\lambda$ 個の遷移を一様にサンプルする
(タスク依存の)類似度関数 $\mathcal{F}$ を用いて、今の状態 $s_i$ とサンプルした $s_k$ の類似度を計算し、
類似度の高い $k$ 個をミニバッチに採用する
- MuJoCoには、コサイン類似度: $\mathcal{F}(s_i,s_k) = \frac{s_i \cdot s_k}{|s_i||s_k|}$
- Atari 2600には、512次元の埋め込み特徴量の差: $\mathcal{F}(s_i,s_k) = - |\phi (s_i) - \phi (s_k)|_2$
$\lambda$ は焼きなましパラメータで、 $\lambda _0 \to 1$ と $\alpha \cdot T$ ステップを利用して徐々に変化
- $\alpha < 1$ : ハイパーパラメータ、 $T$ : トータルステップ数

(4) Experience Replay with Likelihood-free Importance Weights (LFIW)

S. Sinha et al., "Experience Replay with Likelihood-free Importance Weights", (2021)^[5] (arXiv)

LFIWでは、追加のネットワークを利用してReplay Bufferの中の遷移と現在方策との分布の変化を推定することでOff Policyの補正を行う手法です。

On Policyの遷移分布を近似するために、補助的な2個目の小さなReplay Bufferを用意する。(Fast Replay Bufferと呼ぶ)
定理 $D(P\|Q) \geq \mathbb{E}_{P}[f^{\prime}(w(x))]-\mathbb{E}_Q[f^{\ast}(f^{\prime}(w(x)))]$ を利用する。
- $D(\cdot\|\cdot)$ は $f$ -ダイバージェンス、 $f$ はconvex lower-semicontinuous function (日本語訳なんだっけ？)、 $f^{\prime}$ は導関数、 $f^{\ast}$ は複素共役
- 等号は $w = dP/dQ$ のときに成立。
ネットワーク $w_{\psi}(s,a)$ を損失関数 $L_{w}(\psi)=\mathbb{E}_{\mathcal{D}}[f^{\ast}(f^{\prime}(w_{\psi}(s, a)))]-\mathbb{E}_{\mathcal{D}_f}[f^{\prime}(w_{\psi}(s,a))]$ を最小化させるように学習させる。
- $\mathcal{D}$ はReplay Bufferの遷移分布。 $\mathcal{D}_f$ はFast Replay Bufferの遷移分布
- $w(s,a) \to d^{\mathcal{D}_f}/d^{\mathcal{D}} \sim d^{\pi}/d^{\mathcal{D}}$ となるので、Off Policyの補正として用いる

(5) Batch Prioritizing Experience Replay via KL Divergence (KLPER)

D. C. Cicek et al., "Off-Policy Correction for Deep Deterministic Policy Gradient Algorithms via Batch Prioritized Experience Replay", ICTAI (2021) (arXiv)

KLPERは、DDPG や TD3 などの Continuous Action において行動にガウス・ノイズを付加して探索を行う際に利用できる手法です。Replay Bufferからサンプルした遷移の状態(= Observation) に対して現在の方策で行動(= Action) を再計算すると、もしその遷移を生成した方策と今の方策が変化していなければ、サンプルした行動と再計算した行動の差がノイズとして採用したガウス分布に従うことを利用しています。逆に言えば、行動の差が従う分布が元のガウス分布から離れれば離れるほど、方策が変化しているとみなせます。分布を計算するので、遷移単位ではなくミニバッチ単位で取り扱います。

N個のミニバッチをReplay Bufferから一様分布に従って取り出す
ミニバッチごとにKLダイバージェンスを計算する
1. ミニバッチの行動と最新の方策から計算し直した行動の差分を $\dot{a}_t = \pi_{\text{latest}}(s_t) - a_t$ とする。
2. ミニバッチ内で、 $\dot{a}_t$ の平均・共分散から、仮想的なガウス分布 $\mathcal{N}(\mu_{\omega}, \Sigma_{\omega})$ を定義する
3. KLダイバージェンス $\kappa = D_{\text{KL}}\left( \mathcal{N}(\mu_{\omega}, \Sigma _{\omega})~\middle |~ \mathcal{N}(0, \sigma I)\right)$ により、ミニバッチと現在の方策との差を定義する。
KL ダイバージェンスが最も小さいミニバッチを選び方策を学習する。

著者等は実験の中で比較のために、普通のER (= Vanilla ER) およびPERで取得したミニバッチに対しても、同様にKLダイバージェンスを計算しています。「PERが学習に失敗かつKLPERが学習に成功」したときでも、PERのミニバッチの方がKLPERのミニバッチよりもKLダイバージェンスが小さくなることがありました。著者等はKLPERの方がより目立った方策の更新 (more prominent policy changes) を誘引しているからだと説明していますが、私には少し疑問が残りました。（それならどちらか片方の手法で方策を更新しつつ、両方の手法でミニバッチを取り出してみてKLダイバージェンスがどうなるのか同じ条件で比較してくれませんかね。）

(6) Prioritized Experience Replay with Deep Successor Representation (PER-SR)

Y. Yuan and M. Mattar , "Improving Experience Replay with Successor Representation" (2021), (arXiv)

将来その状態にどのくらい訪れるかを表す $Need(s_i, t) = \mathbb{E}\left[ \sum ^{\infty}_{t=0}\gamma ^t 1[s_t=s_j]~| ~s_0=s_i\right]$ を定義し、Successor Representationで学習する。
PERでサンプルした遷移に対して、Successor RepresentationでNeedを計算し、重みに掛け合わせて学習する

PER-SRのデータの流れ概要図 (原論文より引用)

3. 収束速度

3.1 概要

計算コストと時間に直結するので、少ないステップ数で高い精度に到達できることは重要です。

また、近年のAtariの研究では $10^6$ サイズのReplay Bufferで、 $10^6$ ステップ学習させるReplay Bufferが（ほとんど）溢れない構成で実験を行うことも多く、少ないステップ数で終了させることで、Replay Bufferのサイズを小さくすることもできるかもしれません。

3.2 関連研究

(1) Compact Experience Replay (COMPER)

D. E. Neves et al. "Improving Experience Replay through Modeling of Similar Transitions' Sets" (2021)^[6] (arXiv, code)

Transition Memory (TM) と Reduced Transition Memory (RTM)と2つの遷移保存領域を用意する
TD学習におけるターゲットQ値は、そもそも構造の異なるLSTMネットワークを採用する（COMPERではQLSTMと呼ぶ）
類似遷移毎にインデックスを割り当て、TMにインデックス・代表遷移・Q値を保存し、対応する遷移がはいって来るたびにQ値を更新
TMから取り出した遷移でQLSTMを学習させRTMに保存する
RTMから遷移を取り出して、メインのネットワークを学習させる。

COMPERのデータの流れ概要図 (原論文より引用)

学習ステップを重ねるごとに性能がどう移り変わっていったのかのグラフがなく最終性能のテーブルだけが示されていますが、ALEを $10^5$ ステップで報告しているので、多分速いんだと思います。^[7]

(2) Large Batch Experience Replay (LaBER)

T. Lahire et al., "Large Batch Experience Replay", CoRR (2021)(arXiv, code)

ミニバッチの $m$ 倍の遷移を一様にReplay Bufferから取り出す。
取り出した遷移に対して、Surrogate Priorityを計算する
Surrogate Priorityに比例した確率でミニバッチをその中からサンプルする

4. その他

4.1 関連研究

上記の2つのポイントに分類しづらかったのですが、Experience Replayの研究として触れておきたかった研究をその他枠として挙げます。

内容としては以下の記事に書いた内容の転載です。（転載元には原論文から引用した図も少しあります。）

(1) Experience Replay Optimzation (ERO) ★

D. Zha et al., “Experience Replay Optimization”, IJCAI (2019) (arXiv)

Replay Bufferをマスクする確率を別のネットワークのReplay Policy ( $\phi$ )で学習させる手法
(エージェントのPolicyとReplay Policyの両方をそれぞれ学習させる)
遷移に対してスコア( $\boldsymbol{\lambda}$ )を定義: $\boldsymbol{\lambda} = \lbrace \phi(f_{B_i}\mid \theta ^{\phi}) \mid \mathcal{B}_i \in \mathcal{B} \rbrace \in \mathbb{R}^N$
ただし、 $f_{B_i}$ : $i$ 番目の遷移の特徴量
マスク( $\boldsymbol{I}$ )はベルヌーイ分布で作成 $\boldsymbol{I}\sim \text{Bernoulli}(\boldsymbol{\lambda})$
マスクが、1となる遷移の中から一様にエージェントの学習用ミニバッチをサンプルする
サンプルした遷移に対して、新しいスコアを再計算して保存する
Replay Policyは、replay reward ( $r^r = r^c _{\pi} - r^c_{\pi ^{\prime}}$ : エピソードの累計報酬の増加量)を最大化するように学習させる
- $\nabla _{\theta ^{\phi}}\mathcal{J} \sim \sum _{j:\mathcal{B}_j\in\mathcal{B}}~r^r \nabla _{\theta ^{\phi}} [I_j\log \phi + (1-I_j)\log (1-\phi)]$

(2) Neural Experience Replay Sampler (NERS) ★

Y. Oh et. al., “Learning to Sample with Local and Global Contexts in Experience Replay Buffer”, ICLR (2021) (arXiv)

Replay Bufferからサンプルする確率を別のネットワークNERSで学習する手法
- EROと異なり、PERのpriority (=TD誤差の大きさ)にあたるスコア( $\sigma_i$ )を予測する
Actor/Criticの学習に利用したミニバッチの遷移に対して
- スコア( $\sigma _i$ )をNERSで更新する
- インデックス( $I$ )を保存しておく ( $\mathcal{I} = \mathcal{I} \cup I$ )
エピソード終端で、 $\mathcal{I}$ から一様にサンプルし( $I_{\text{train}} \sim \mathcal{I}$ )、replay reward $r^{\text{re}}$ を最大化するようにNERSを学習させる (その後 $\mathcal{I} = \empty$ に戻す)
- 入力は、 $D(I_{\text{train}}) = \lbrace s_{\kappa(i)}, a_{\kappa(i)}, r_{\kappa(i)}, s_{\kappa(i)+1},\kappa(i), \delta _{\kappa(i)}, r_{\kappa(i)} +\gamma \max _a Q_{\hat{\theta}}(s_{\kappa(i)},a) \rbrace _{i\in I_{\text{train}}}$
- $\kappa(i)$ : $i$ 番目の時刻、 $\delta _{\kappa(i)}$ : TD誤差、 $\gamma$ : 割引率、 $\hat{\theta}$ : ターゲットネットワークのパラメータ
- $\nabla _{\phi}\mathbb{E}_{\text{train}}[r^{\text{re}}] = \mathbb{E}_{I_{\text{train}}}\left [ r^{\text{re}}\sum _{i\in I_{\text{train}}} \nabla _{\phi}\log \sigma _i (D(I_{\text{train}})) \right ]$
NERSは3種類のネットワーク( $f_l, f_g, f_s$ )の組合せ
- $f_l$ : ローカルネットワーク。遷移ごとに計算
- $f_g$ : グローバルネットワーク。遷移ごとに計算し、ミニバッチで平均する
- $f_s$ : スコアネットワーク。 $f_l$ の出力と $f_g$ の出力を結合したものを入力に各遷移のスコア ( $\sigma _i$ ) を計算

(3) Loss-Adjusted Prioritized Experience Replay (LAP) ★

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

そもそも論として、PERでL2ノルムを損失関数に利用すること自体が、ERにおけるL2ノルムと比較してバイアスが乗るとして、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}

5. 今回触れなかった研究たち

（他にもあるとは思いますが、ぱっと思いついたものや手元のメモを参考に）

5.1 適格度トレース

Off Policy補正や最適方策への収束性の観点では触れておきたい気もするのですが、私の理解があまり及んでいない事もあって見送りました。

(ある程度の事前知識が必要ですが、) ざっとのイメージや手法の特性比較としてはRetraceの筆頭著者のスライドが分かりやすいのではないでしょうか。

5.2 Offline RL

同じく、分布補正の観点としては本当は抑えておきたい完全にOfflineの場合の強化学習。
私自身は論文調査すらもなかなかできていないので、有志の方がまとめていらっしゃるレポジトリを紹介しておきます。

5.3 その他

ちょっとおもしろいかもと思いつつも、理解が及ばなかったり納得がいっていなかったりする研究たち

F. Sovrano et al., "Explanation-Aware Experience Replay in Rule-Dense Environments" (arXiv)
- XAER
- 明確なルールがあるのであれば、複数Replay Bufferを持ってうまく使い分けようの精神 (はず)
B. Daley et al., "Stratified Experience Replay: Correcting Multiplicity Bias in Off-Policy Reinforcement Learning", AAMAS (2021) Page 1486 (arXiv)
- $(s_t,a_t)$ ハッシュ値毎に可変長個の遷移を保存し、 $(s_t,a_t)$ で一様サンプル
- 分布形状が全く変わるので、あんまり良くないのでは？
S. Kong et al., "Enhanced Off-Policy Reinforcement Learning With Focused Experience Replay", IEEE Access, vol. 9, pp. 93152--93164 (2021) doi: 10.1109/ACCESS.2021.3085142
- 学習全体で見れば、古い遷移の方が何度もサンプル対象になるため、取り出される確率が高くなるので、新しい遷移を優先度高くサンプルする手法
- 実験結果が誤差にしか見えない

6. おわりに

強化学習におけるExperience Replayのポイントについて、近年の研究を簡単に紹介しながら、個人的に感じていることをまとめました。「ここは違う」とか「ここはもっとこう解釈すべきだ」とかあれば、コメント欄やアンサー記事(？)でレスポンスもらえると嬉しいです。また、趣味でやってるせいか自分で手を動かして実験・検証というところまでなかなか到達せず知識偏重になってしまっているので、実際にやってみた感想なども知りたいなぁと思っています。

強化学習とExperience Replayに興味を持つ人が少しでも増えてくれるといいなと思います。

脚注

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 ↩︎
T. Schaul et al., “Prioritized Experience Replay”, ICLR (2016) (arXiv) ↩︎
H. Hasselt et al., "Deep Reinforcement Learning and the Deadly Triad", arXiv:1812.02648 (2018) ↩︎
H. Hasselt et al., "Deep Reinforcement Learning with Double Q-learning", AAAI (2016) 30(1) (arXiv) ↩︎
ICLR 2021で不採択 ↩︎
ブラジルの教皇庁立ミナスジェライス州・カトリック大学(?) (= PUC Minas) の大学院課程での成果とのことですが、査読付き論文やカンファレンスへの投稿は今の所見つけられませんでした。arXivのprepirntが41ページもあるので、学位論文にでもなるのでしょうか。 ↩︎
実験結果を公開しているのでよく見ればわかるのかもしれません。 ↩︎