Open69

強化学習情報収集(論文など)

ピン留めされたアイテム

cpprb 開発用に、強化学習の(主に)Experience Replayに関する情報(論文など)を収集してメモしておくためのスクラップ。

以前に書いた記事は以下。ここのスクラップも、ある程度読み込んで整理したら記事化したい。

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

https://zenn.dev/ymd_h/articles/c3ba23033a6442

Stratified Experience Replay: Correcting Multiplicity Bias in Off-Policy Reinforcement Learning

B. Daley et al.
(2021/2/27時点では Extended Abstractのみ)

https://arxiv.org/abs/2102.11319

Experience Replay 用のバッファは通常リングバッファで構築されるが、
Hash と可変リストの組合せで構築することで、 (s_t, a_t) の組を一様にサンプリングする手法

バッファの構造を変えて、サンプリング空間を変えるアイディアは面白い

Hashのキーとするので、 (s_t, a_t) は離散かつ現実的な個数しか許容されないという実装上の制約があると思われる

また、 (s_t, a_t) 上で一様にサンプリングすることは、off-policyness の課題を解決していないと個人的には感じる。
Sutton先生等の教科書にかかれているシンプルだけどoff-policyで問題になるケースを解決できていないと感じる

Beyond Prioritized Replay: Sampling States in Model-Based Reinforcement Learning via Simulated Priorities

J. Mei et al.

https://arxiv.org/abs/2007.09569

前半(およびAppendix)でPERの理論的な考察を行い、後半ではモデルベースRLにおけるoff-policynessの(?)解決策を提案している。

ざっくりとしか目を通していないが、行動方策で獲得した遷移と、モデルベースのシミュレーションによって作成した遷移を混ぜてネットワークを学習させていると理解した。

Safe and Efficient Off-Policy Reinforcement Learning

R. Munos et al.

https://arxiv.org/abs/1606.02647

名前は聞いたことがあったけど、読まないままになっていた Retrace の論文 (多分)

最近 off-policy RL の off-policyness の影響について調査しているので、以下の記述の部分が特に気になる。

(2) it safely uses samples collected from any behaviour policy, whatever its degree of "off-policyness";

(論文がかなり難しい・・・)

ポイントは、 \prod _{t} \left (\lambda \min\left(1,\frac{\pi (a_t\mid s_t)}{\mu (a_t\mid s_t)} \right) \right ) を重みとして使うこと。

ということは、遷移ではなくエピソードごとに取り扱う必要があるかな?
(cpprb ではエピソードごとの取り扱いは現状考慮されていない。リングバッファに可変長のエピソードを保存するのが面倒なため)

IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures

L. Espeholt et al.

https://arxiv.org/abs/1802.01561

読まないままになっていた IMPALA および V-trace

learning with a novel off-policy correction method called V-trace

Retrace が Q-learning だったのに対して、IMPALA (V-trace) は、actor-critic で方策 \pi と 状態価値 V^{\pi} を学習させる

IMPALAの実装に取り組んでいますが、論文だけ読んでも(私には)わからない点がちらほら

  • n-ステップの遷移をセットで取り扱うが、途中でエピソードが終了 (d_t = 1) の場合はどうする?
  • 0\sim n-1n-ステップの遷移を送った次は、1\sim n ?それとも n \sim 2n-1
  • 方策の更新式に出てくる v_{s+1} は、s\sim s+n-1n-ステップでは計算できないような?
  • 文中にポロッと出てくるLSTMの状態を送るとはどういうことか?

途中でエピソードが終了 (d_t =1) の場合

割引率 (\gamma) に done を反転させて掛けている。

https://github.com/deepmind/scalable_agent/blob/6c0c8a701990fab9053fb338ede9c915c18fa2b1/experiment.py#L372
  • v_s の計算時には、累積積 cumprod を使うので、エピソードをまたいで計算をすることを防げる

0\sim n-1 ステップの次

最後の状態を保存して、そこから次の回を再開する。

https://github.com/deepmind/scalable_agent/blob/6c0c8a701990fab9053fb338ede9c915c18fa2b1/experiment.py#L288

off-policy deep RL

R. Munos (Retraceの筆頭著者かつ、IMPALAの著者のひとり。)

https://project.inria.fr/paiss/files/2018/07/munos-off-policy-dRL.pdf

off-policy の補正項についての変遷がまとめられている。

1. Importance Sampling

\gamma ^t \left( \prod_s \frac{\pi (a_s \mid s_s)}{\mu (a_s \mid s_s)}\right ) \delta _t
  • バイアスはない
  • バリアンスが大きい

2. Q^{\pi}(\lambda)

(\gamma \lambda)^t \delta _t
  • \| \pi - \mu \| _1 \leq \frac{1-\gamma}{\lambda \gamma} ならうまくいく
  • その他はだめな可能性がある

3. Tree Backup TB(\lambda)

\lambda ^t \prod _s (\pi (a_s\mid s_s)) \delta _t
  • 任意の \pi\mu でうまくいく
  • on-policy の時に不必要にトレースをカットしてしまい(?) 非効率的

4. Retrace(\lambda)

\lambda ^t \prod _s \min \left(1, \frac{\pi (a_s\mid s_s)}{\mu (a_s \mid s_s)} \right ) \delta _t
  • バリアンスは小さい
  • off-policy の時にはトレースをカットするので安全
  • on-policy の時には効率的

Revisiting Peng's Q(\lambda) for Modern Reinforcement Learning

T. Kozuno et al.

https://arxiv.org/abs/2103.00107

multi-step 報酬を off-policy RL でどうして使っていいかの理論的な考察の論文 (だと教えてもらった。未読)

multi-step 報酬は原理的に、行動方策での報酬なのでその理論的な合理性はこれまで未解決だった。

適切に行動方策を更新しつづければ、 TD(\lambda) 誤差で学習する Peng's Q(\lambda) は最適方策に収束する。

  • \mu \gets \alpha \pi + (1-\alpha)\mu、ただし \alpha \in [1-\lambda, 1]

収束の条件は『行動方策 (\mu)』を適切に更新となっているが、証明の中ではその更新した行動方策で集めたデータを利用して、方策 \pi のパラメータを更新している

ということは、行動方策そのものではなく、Replay Bufferの中に保存されているデータ分布 \mathcal{B} を意味していると解釈すべきなのではなかろうか?

つまり、Replay Buffer内の一定の割合 \alpha を最新の方策のデータにするということか。

Reconciling \lambda-Returns with Experience Replay

B. Daley and C. Amato

https://arxiv.org/abs/1810.09967

\lambda-報酬を Experience Replayと組合せて使う方法 (DQN(\lambda)など)

Replay Bufferにキャッシュ領域を設けて、Replay Bufferの連続した一部の領域をキャッシュに保存し、\lambda-報酬を計算しておく。更に \max_a Q(s_{t+1},a) の値も計算して保存しておくことでターゲットネットワークを置き換える

Sparse Graphical Memory for Robust Planning

S. Emmons et al.

https://arxiv.org/abs/2003.06417

疎なグラフ構造としてデータを保存しておく手法

SGM論文が、引用している関連手法 (一部)

Search on the Replay Buffer: Bridging Planning and Reinforcement Learning

B. Eysenbach et al.

https://arxiv.org/abs/1906.05253

Semi-parametric Topological Memory for Navigation

N. Savinov et al.

https://arxiv.org/abs/1803.00653

Mapping State Space using Landmarks for Universal Goal Reaching

Z. Huang et al.

https://arxiv.org/abs/1908.05451

Hallucinative Topological Memory for Zero-Shot Visual Planning

K. Liu et al.

https://arxiv.org/abs/2002.12336

原論文の疑似コードが混乱を招きうる(かつおそらく間違っている)のが原因だけど、上のNotionの疑似コード多分違う

ノードの追加のみ切り出すと

V = set()

for s in ReplayBuffer:
    for s_prime in V:
        if not ((C_in(s, s_prime) < tau) and (C_out(s, s_prime) < tau)): 
            V.add(s)

Offline-to-Online Reinforcement Learning via Balanced Replay and Pessimistic Q-Ensemble

S. Lee et al.

https://arxiv.org/abs/2107.00591

Offline RLで学習したモデルをOnlineのデータで fine tune しようとすると、データのドメインシフトの影響でせっかく学習した初期モデルの良さが失われうるという課題に対する提案論文。

内容は未読。後で読む。

Enhanced Off-Policy Reinforcement Learning With Focused Experience Replay

S. Kong et al.

https://ieeexplore.ieee.org/document/9444458

学習と探索を並行してすすめると、学習全体で考えたときに、古い遷移程たくさん学習に使われやすい事が課題

提案している Focused Experience Replay (FER) では、片側正規分布を用いて新しいサンプルのサンプル確率を上げることで、学習全体における遷移の利用確率の分布をよりなだらかにしている。
(尚、極端な例として常に最新の遷移のみを取り出すと、学習全体での遷移の利用率は完全に一様になるが、逆にExperience Replayのメリットを失うとのこと)

着眼点は面白いけど、実験結果は誤差の範囲内にしか見えない。

A Deeper Look at Experience Replay

S. Zhang and R. S. Sutton

https://arxiv.org/abs/1712.01275

2015年のDQN以降、ほとんどみんな Replay Buffer のサイズを 10^6 に固定してしまっている。

実験してみるとサイズが大きいほど学習がゆっくりになっている

提案の Combined Experience Replay (CER) は、 Replay Bufferからサンプルした batch_size - 1 の遷移に、最新の遷移を1つ加えてバッチを構成してネットワークを学習させることで、Replay Buffer のサイズが大きすぎる際の負の影響を打ち消す。

Experience Replay with Likelihood-free Importance Weights

S. Sinha et al.

https://arxiv.org/abs/2006.13169

未読: TD誤差による重み付けが heuristic であり、Actor-Critic系手法では sub-optimal になりがちであることを課題に挙げている。

サイズの異なる2つのReplay Buffer (例えば、10^610^4) を用いることで、
current policy における分布確率 d^{\pi}(s, a) と、Replay Buffer の分布確率 d^{\mathcal{D}}(s, a) の比率である
確率密度比: w(s, a) = d ^{\pi} (s, a)/ d ^ {\mathcal{D}} (s, a) を推定しようとしている。

確率密度比をネットワーク w_{\psi} (s, a) で推定するとして、f-divergence (論文では、Jenson-Shannon divergenceを利用) を用いた損失関数 L_{w}(\psi) を最小化している。

L_{w} (\psi) = \mathbb{E}_{\mathcal{D}_s}[f^{\ast}(f^{\prime}(w_{\psi}(s, a)))] - \mathbb{E}_{\mathcal{D_{f}}}[f^{\prime}(w_{\psi}(s, a))]

f^{\prime} は、f-divergence の1階微分
f^{\ast} は、f-divergenceの(?)複素共役
D_{s} は、大きい方 (slow) の Replay Bufferの分布
D_{f} は、小さい方 (fast) の Replay Bufferの分布 (≒ current policy の分布)

損失関数 L_{w}(\psi) の導出は、次の定理に基づいている

D_f(P\| Q) \geq \mathbb{E}_{P}[f^{\prime}(w(x))] - \mathbb{E}_{Q}[f^{\ast}(f^{\prime}(w(x)))]

損失関数は右辺の式の正負を入れ替えた形になっている。
つまり、損失関数を最小化するとは、f-divergence (の下界)を最大化していると考えられる。

あれ・・・?混乱してきました。
divergence を大きくするということは、2つの分布の差を大きくするのでは?

後で、読み直します。

勘違いしていました。

w(x) を変更したところで、D_f(P\| Q) は変化しませんね。
損失関数 L_{w}(\psi) を最小化するように、 w_{\psi} を学習させると、定理の等号が成り立つ値に向かって近づいていくのですね。

で、定理の等号は、 w = dP/dQ のときに成立することが知られているので、
損失関数の最小化時には、w_{\psi}(s, a) \to d\mathcal{D}_f/d\mathcal{D}_s

PERとの比較として著者は論理を展開しているが、ポイントは異なるように感じる。

PERは、重点サンプリングで学習の速度を向上させることを目指している。
一方、著者らの手法 LFIW (?) は、分布の違いに起因して、最適ポリシーに到達できないことを防ぐことにメリットがあると感じる。

[疑問]

上の方に書いたが、重点サンプリングの重みでポリシーの分布を補正する手法は、
分散が大きく使いにくいというのが、Retrace / V-trace の発明につながっているはずですが、
この LFIW では影響は無いのだろうか??

https://zenn.dev/link/comments/8d835c996a62b2

また、PERと併用すれば、収束速度の面でさらに向上が見られるのだろうか?

Large Batch Experience Replay

T. Lahire et al.

https://arxiv.org/abs/2110.01528

https://github.com/SuReLI/laber

Replay Bufferから、gradient の2乗ノルムの重要度でサンプルすることで
理論的には最速に収束することを示している。
PERで利用されている TD誤差はこの gradient を(ある条件下で)近似したものであることを示している。

TD誤差ではなく、 gradient を利用したバージョンを GER (Gradient Experience Replay)と定義している。

PER・GERともに、サンプルしたミニバッチのみ重要度を更新するため、ネットワークの更新のたびに古くなってしまうことが課題である。(もちろんReplay Buffer内の全ての遷移に対して、逐一重要度を更新するのは計算負荷が高すぎる。)

そこで更に、提案する LaBER (Large Batch Experience Replay) では、バッチサイズのm倍の遷移を抽出して、gradient を計算し、その gradient を重要度として、その中からミニバッチを抽出する2段階のサンプルを採用している。
この事によって、(部分的にではあるが)outdatedではない最新の重要度を利用してミニバッチを構築することができる。

Explanation-Aware Experience Replay in Rule-Dense Environments

F. Sovrano et al.

https://arxiv.org/abs/2109.14711

Abstのみ読了。後で読む。

明確なルールが有る時に、Replay Bufferを複数持つことで、説明可能な経験再生をする(?)
Explanation-Aware Experience Replay (XAER)

Improving Experience Replay through Modeling of Similar Transitions' Sets

D. E. Neves et al.

https://arxiv.org/abs/2111.06907
https://github.com/DanielEugenioNeves/COMPER-RELEASE-CODE

遷移の類似排除を行うことで、効率よく少ない遷移で学習を行う手法: Compact Experience Replay (COMPER)

Atari を 10^5 stepで実験している

ざっと読んでみた特徴

  • Targetネットワークが、主たるネットワークのコピーではなく、別のLSTM。
  • Transaction Memory (TM) と Reduced Transaction Memory (RTM) と2つのBufferを利用
    • TM: 遷移と推定Q値を保存する。類似度を(Faissで)判定して閾値以下を同一視して重複排除
    • RTM: Targetネットワーク (LSTM) によって、TMを更に削減してコンパクトな遷移を保存 (ここがよくわかっていない。)

Improving Experience Replay with Successor Representation

Y. Yuan and M. Mattar

https://arxiv.org/abs/2111.14331v1

神経学での海馬再生 (hippocampal replay) における need (= 将来到達する回数期待値) 項をPERに取り入れて、TD誤差と併せて、Replay Bufferからの抽出確率を構築する手法

M(s, s^{\prime}, a) = \mathbb{E}\left[ \sum _{t=0}^{\infty}\gamma ^t \mathbb{1}\left[ s_t = s^{\prime} \right] ~ \middle | ~ s_0=s, a_0 =a \right]
m_{s, a} =\sum _{s^{\prime}\in S}M(s, s^{\prime}, a)\phi(s^{\prime})
Need(s^{\prime})=M(s, s^{\prime}, a) - \min (0, \min _i M(s, s_i, a)),~i\in [i, k]

ん? Need をReplay Bufferからの抽出確率にも考慮するのかと思ったけど、Needはミニバッチを抽出後の重み付けだけなのか?

Off-Policy Correction for Deep Deterministic Policy Gradient Algorithms via Batch Prioritized Experience Replay

D. C. Cicek et al.

https://arxiv.org/abs/2111.01865

Batch Prioritized Experience Replay via KL Divergence (KLPER)

DDPG や TD3 などのContinuous Action 用。

  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) により、ミニバッチと現在の方策との差を定義する。
  4. N個のミニバッチを取り出し、KL divergenceが最も小さいミニバッチを選び方策を学習する。

Convergence Results For Q-Learning With Experience Replay

L. Szlak and O. Shamir

https://arxiv.org/abs/2112.04213

理論的に、テーブル形式のQ学習において、Experience Replay が収束速度に与える影響を考察している。

Replay For Safety

L. Szlak and O. Shamir

https://arxiv.org/abs/2112.04229v1

性能向上ではなくて、安全性(?)の向上のためにExperience Replayを活用する方法

= 最小のエピソード報酬を最大化することを目的としている。

Experiment 節に、テーブルもグラフも1つもない・・?

Variance Prioritized Replay

遷移がサンプルされる確率 w_t(s,a,s^{\prime}) を以下のように定義する

w_t(s,a,s^{\prime}, r) = \frac{Var(r(s,a))}{\sum _{\bar{s}\in \mathcal{S}}\sum _{\bar{a}\in \mathcal{A}} Var(r(\bar{s}, \bar{a}))} \frac{\exp (-\beta r)}{\sum _{r^{\prime} \in M_t(r (s,a))} \exp (-\beta r^{\prime})} \frac{1}{|L_t(s, a, r)|}

Var(r(s,a)) は 即時報酬の empirical な分散
M_t(r(s,a))(s, a) から生じる r (即時報酬) のユニークな集合
L_t(s,a,r)(s,a,r) から生じる s^{\prime} のユニークな集合

分散が大きい遷移をたくさん活用するという考え方自体は理解できる。
テーブル形式なら empirical な分散を求められるが、関数近似 (深層学習) においては難しいか?

また、このアルゴリズムが安全に収束するよねという証明はテーブル形式のTD学習を前提としているので、DQN-likeなアルゴリズムでは妥当性は不明。

Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs

N. Agarwal et al.

https://arxiv.org/abs/2110.08440v2

テーブル形式ではない、線形関数近似における最適Q関数への収束性を議論

Online Target Learning (OTL) + Reverse Experience Replay (RER) により、以下の2つのアルゴリズムを提案

  • Q-Rex
  • Q-RexDaRe: こっちがSample Efficient Variant

Q-Rex finds the optimal policy for linear MDPs
(or more generally for MDPs with zero inherent Bellman error with linear function approximation
(ZIBEL)) and allows us to derive non-asymptotic sample complexity bounds.

Parallel Actors and Learners: A Framework for Generating Scalable RL Implementations

C. Zhang et al.

https://arxiv.org/abs/2110.01101

並列化した学習におけるPERの効率的な実装の提案。

  • K-ary sum tree (K分木によるsum treeの実装)
  • 遅延書き込み + 効率的なロックによる実装

後者は cpprb.MPPrioritizedReplayBuffer で実装しているロックと近いんじゃないだろうか?

前者は、2分木よりもK分木の方が速度向上するというのであれば、検討・実装の余地ありかな?

ここに書いた。
https://ymd_h.gitlab.io/cpprb/survey/parallel/

ログインするとコメントできます