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)

山田(ymd)2021/04/04

公式実装

https://github.com/scottemmons/sgm

(非常に読みにくい)

山田(ymd)2021/09/06

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 しようとすると、データのドメインシフトの影響でせっかく学習した初期モデルの良さが失われうるという課題に対する提案論文。

内容は未読。後で読む。

山田(ymd)2021/09/16

Enhanced Off-Policy Reinforcement Learning With Focused Experience Replay

S. Kong et al.

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

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

山田(ymd)2021/09/16

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

山田(ymd)2021/09/17

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 のサイズが大きすぎる際の負の影響を打ち消す。

山田(ymd)2021/12/11

ここに掲載

山田(ymd)2021/09/17

Experience Replay with Likelihood-free Importance Weights

S. Sinha et al.

https://arxiv.org/abs/2006.13169

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

山田(ymd)2021/09/21

サイズの異なる２つのReplay Buffer (例えば、 $10^6$ と $10^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 の分布)

山田(ymd)2021/09/21に更新

損失関数 $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 を大きくするということは、２つの分布の差を大きくするのでは？

後で、読み直します。

山田(ymd)2021/09/21

勘違いしていました。

$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$

山田(ymd)2021/09/21

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

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

山田(ymd)2021/09/21

[疑問]

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

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

山田(ymd)2021/12/11

ここに掲載

山田(ymd)2021/10/11

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)

山田(ymd)2021/11/29

Improving Experience Replay through Modeling of Similar Transitions' Sets

D. E. Neves et al.

https://arxiv.org/abs/2111.06907

遷移の類似排除を行うことで、効率よく少ない遷移で学習を行う手法: 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を更に削減してコンパクトな遷移を保存 (ここがよくわかっていない。)

山田(ymd)2021/12/11

ここに掲載

山田(ymd)2021/12/03

Improving Experience Replay with Successor Representation

Y. Yuan and M. Mattar

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

山田(ymd)2021/12/04

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

山田(ymd)2021/12/05

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]

山田(ymd)2021/12/05

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

山田(ymd)2021/12/11

ここに掲載

山田(ymd)2021/12/05

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)

山田(ymd)2021/12/05

DDPG や TD3 などのContinuous Action 用。

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

山田(ymd)2021/12/11

ここに掲載

山田(ymd)2021/12/12

Convergence Results For Q-Learning With Experience Replay

L. Szlak and O. Shamir

https://arxiv.org/abs/2112.04213

山田(ymd)2021/12/12

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

山田(ymd)2021/12/13

Replay For Safety

L. Szlak and O. Shamir

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

山田(ymd)2021/12/13

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

山田(ymd)2021/12/13

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

山田(ymd)2021/12/15

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

山田(ymd)2021/12/15に更新

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}$ のユニークな集合

山田(ymd)2021/12/15

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

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

山田(ymd)2021/12/16

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

山田(ymd)2021/12/17

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

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

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

山田(ymd)2021/12/17

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.

山田(ymd)2021/12/18

Lucid Dreaming for Experience Replay: Refreshing Past States with the Current Policy

Y. Du et al.

Lucid Dreaming for Experience Replay (LiDER)

山田(ymd)2021/12/18

山田(ymd)2022/01/18に更新

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

C. Zhang et al.

https://arxiv.org/abs/2110.01101

山田(ymd)2021/12/27

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

山田(ymd)2021/12/27

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

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

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

山田(ymd)2021/12/31

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

山田(ymd)2022/01/18に更新

Improving the Efficiency of Off-Policy Reinforcement Learning by Accounting for Past Decisions

B. Daley and C. Amato

https://arxiv.org/abs/2112.12281

山田(ymd)2022/01/18

山田(ymd)2022/02/04

Double Prioritized State Recycled Experience Replay

F. Bu et al.

https://arxiv.org/abs/2007.03961

バッファがいっぱいになったあとにFIFOではなく、重要度を考慮して削除する要素を選択する手法

山田(ymd)2022/02/06

Model-augmented Prioritized Experience Replay

Y. Oh et al

(ToDo: arXiv等にアップロードされたらURLを差し替える)

MaPER

Q値を推定する critic network で、reward / next state も推定する。
TD誤差だけではなく、reward推定誤差、next state 推定誤差も加味して、遷移の重要度を算出する。

効果

TD誤差が速く減少する。
推定Q値がReturnとより良く一致する。 (overestimation/underestimationしづらい)

不明点

なぜ reward/next stateの推定誤差を加えると上手くいくのかが理論的に不明瞭
実験結果の信頼区間が被っている。統計的に本当に優位な誤差がある？

山田(ymd)2022/02/10

Loss ( $\mathcal{L}$ ) や遷移の重要度 ( $\sigma _i$ ) は、TD誤差・報酬予測誤差・状態予測誤差の混合とする

\mathcal{L} = \xi_Q \mathcal{L}_{Q} + \xi_R \mathcal{L}_{R} + \xi_S\mathcal{L}_{S}

\sigma_i = \xi_Q |\delta Q_i|_{MSE} + \xi_R |\delta R_i|_{MSE} + \xi_S|\delta S_i|_{MSE}

係数 $\xi_Q,\xi_R,\xi_S$ は各損失の変化量に応じて動的に決める

\xi _j = \frac{1}{Z} \exp \left ( \frac{\mathcal{L}_{j}^{t-1}}{\mathcal{L}_{j}^{t-2} T} \right )~\text{where}~j=Q,R,S

https://arxiv.org/abs/1803.10704
https://arxiv.org/abs/2002.04792

山田(ymd)2022/02/08

Why Should I Trust You, Bellman? The Bellman Error is a Poor Replacement for Value Error

S. Fujimoto et al.

https://arxiv.org/abs/2201.12417

[定義]

Bellman Error: $\varepsilon _Q(s,a) = Q(s,a) - \mathbb{E}_{r, s^{\prime}\sim p,a^{\prime}\sim \pi}[r+\gamma Q(s^{\prime}, a^{\prime})]$
Value Error: $\Delta _Q(s,a) = Q(s,a) - Q^{\pi}(s,a)$
Bellman Residual Minimization (BRM): $\mathcal{L}_{BRM}=\frac{1}{|D|}\sum (Q(s,a) - (r + \gamma Q(s^{\prime}, a^{\prime})))^2$
Fitted-Q Evaluation (FQE): $\mathcal{L}_{FQE}=\frac{1}{|D|}\sum (Q(s,a) - (r + \gamma \bar{Q}(s^{\prime}, a^{\prime})))^2$
- $\bar{Q}(s^{\prime}, a^{\prime})$ は固定しておいて定期的に更新。(Target Network等)

[理論]

本来やりたいことはValue Errorの最小化だが、Q学習ではBellman Errorの最小化を行っている。
あらゆる $(s,a)$ で $\varepsilon _Q(s,a)=0$ となるときのみ、Bellman ErrorとValue Errorは一致する。
- 特に不完全な $(s, a)$ の組しかない場合、条件を満たすValue Errorは無限に存在する。
Bellman Errorは差分なため、Q関数にバイアスがあってもBellman Errorには影響がない
Value Errorの大きさよりも、ずれの方向 (符号) のほうが、Bellman Errorに与える影響は大きい

[実験]

Bellman Errorを最小化する手法 (BRM, FQE) では、Bellman Errorは小さくなるが、Value Errorが小さくなるとは限らない
- on-policyでは連続する遷移においてValue Errorのズレが同じ方向になりやすいこともあり、BRM、FQEともにまし
- off-policyではBRMはひどいが、FQEはまだまし

[FQEの追加の考察]

FQEは間接的にはBellman Errorを最小化する手法だが、厳密にはBellman OperatorによるBellman更新とみなせる
$Q_2 = \mathcal{T} Q_1$ とすると
- $\gamma \max _{(s,a)\in D}|\mathbb{E}_{(s^{\prime},a^{\prime})\sim p(\cdot |s,a),\pi}[\Delta _{Q_2}(s^{\prime},a^{\prime})]| < \max _{(s, a)\in D}|\Delta _{Q_1}(s,a)|$ であれば
- $\max _{(s,a) \in D}|\Delta _{Q_2}(s,a)| < \max _{(s,a) \in D}|\Delta _{Q_1}(s,a)|$ となる
- つまり、この条件下であれば、データが不完全であってもValue Errorの減少が保証される

山田(ymd)2022/02/08

[所感]

Q学習がQ値の過大評価 (過小評価) に陥ってしまう理由を明らかにした
- (誘発するダイナミクスではなく、結果の解釈の観点として)
Target Networkの利用で学習がより安定することを理論的・実験的に明らかにした
Target Networkを利用する学習でQ値の推定誤差が減少していく条件を明らかにした
- 但し、その条件を満たすために、どのようにセットアップすればよいのかは未解明

山田(ymd)2022/03/03

GA-DRL: Genetic Algorithm-Based Function Optimizer in Deep Reinforcement Learning for Robotic Manipulation Tasks

A. Sehgal et al.

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

DDPG-HER のハイパーパラメータを Genetic Algorithm で最適化。

30体 $\times$ 30世代
順位を元に確率的に親を決める
子は一様交叉 (uniform crossover) で生成
パラメータをbit列で表現して、0.1の確率で反転突然変異 (flip mutation)

山田(ymd)2022/03/03

A DPDK-Based Acceleration Method for Experience Sampling of Distributed Reinforcement Learning

M. Furukawa and H. Matsutani

https://arxiv.org/abs/2110.13506

Data Plane Development Kit (DPDK) を使い Ape-X を高速化 (Low-Latency)

山田(ymd)2022/03/05

Learning to Reach Goals via Iterated Supervised Learning

D. Ghosh et al.

https://arxiv.org/abs/1912.06088

[提案手法] Goal-conditioned supervised learning (GCSL)

Hindsight Experience Replay (HER) で用いられるゴールの付け替えで生成した疑似成功エピソードを使って Behavior Cloning (BC) で方策を更新する。

[効果]

Behavior Cloning で方策の尤度を直接最大化するので、Value Functionを学習する必要がない
ゴール付替をした過去の全 off-policy なデータを利用できる。

山田(ymd)2022/03/29

Remember and Forget Experience Replay for Multi-Agent Reinforcement Learning

P. Weber et al.

https://arxiv.org/abs/2203.13319

ReF-ER のマルチエージェント拡張

山田(ymd)2022/03/31

Topological Experience Replay

Z. Hong et al.

https://arxiv.org/abs/2203.15845

山田(ymd)2022/03/31

エージェントの遷移から、状態遷移のグラフを構築しグラフのつながりに応じてQ値の更新順序を決めることで、疎な報酬の環境を効率よく学習させる。

Hidden comment

山田(ymd)2022/04/02

論文をもう少し読むと、E (Edge)は、読み出し速度向上のために二重のハッシュテーブルとして実装

不明点: V (vertex) は何に使っている？

山田(ymd)2022/04/02

更新版

from queue import Queue
import numpy as np

class Hash:
    """
    Random Projection
    """
    def __init__(self, obs_shape, hash_dim):
        obs_dim = np.prod(obs_shape)
        self.M = np.random.normal(0, 1.0/hash_dim, (hash_dim, obs_dim))

    def __call__(obs):
        return self.M @ np.ravel(obs)

hash = Hash(obs_dim, hash_dim)

Twarm = 100
N = 1000
B = 32

# G
G = {}

Ve = []

sQueue = Queue()
bQueue = Queue()

visited = []

for t in range(N):
    act = policy(obs)
    next_obs, rew, done, _ = env.step(act)

    h_obs = hash(obs)
    h_next_obs = hash(next_obs)
    if h_next_obs not in G:
        G[h_next_obs] = {h_obs: {[(obs, act, rew, next_obs)]}}
    elif h_obs not in G[h_next_obs]:
        G[h_next_obs][h_obs] = [(obs, act, rew, next_obs)]
    else:
        G[h_next_obs][hobs].append((obs, act, rew, next_obs))

    if done:
        Ve.append(h_next_obs)

    while t > Twarm and bQueue.qsize() < B:
        if sQueue.empty():
            sQueue.push(np.random.choice(Ve))
            visited = []

        while True:
            vp = sQueue.pop()
            if vp not in visited:
                break
        
        Ep = G[vp]

        for v, trans in Ep.items():
            sQueue.push(v)
            for _trans in trans:
                bQueue.push(_trans)

        visited.append(vp)

    if t > Twarm:
        b = [bQueue.pop() for _ in range(B)]
        model.train(b)

山田(ymd)2022/04/07

Appendix A の実装詳細から

終端状態を8個ランダムサンプル
- 幅優先探索で、各ノードから最大3つ (全部は多すぎるらしい) の前状態を探索
論文では、2次元画像を（たった）3次元に射影 (ランダムに初期化) した
サンプル時に古い遷移は取り除く、遷移が 0 になったら、エッジも取り除く
環境に応じて、0.1 - 0.5 の割合で、PERのサンプルと混ぜてモデルを学習させた

山田(ymd)2022/04/11

実際には、ハッシュテーブル (Python なら dict かな) を用いた実装

float や tuple をキーにすることができそう。

また、NumPy の ndarray をハッシュにするなら、hash(a.tostring())

注意事項として、Pythonのハッシュ自体に乱数が使われていてプロセスごとにシードが異なるらしい。

気になるのは、射影先がたった3次元とはいえ、浮動小数点の微妙な揺らぎをすべて異なる値だとして、ハッシュのキーにしてもよいのかどうか。

山田(ymd)2022/05/18

Variance Reduction based Partial Trajectory Reuse to Accelerate Policy Gradient Optimization

H. Zheng and W. Xie

https://arxiv.org/abs/2205.02976

山田(ymd)2022/05/18

著者による公式コード

山田(ymd)2022/05/18

同著者による先行研究

Green Simulation Assisted Policy Gradient to Accelerate Stochastic Process Control

H. Zheng at al.

https://arxiv.org/abs/2110.08902

山田(ymd)2022/05/24

Neighborhood Mixup Experience Replay: Local Convex Interpolation for Improved Sample Efficiency in Continuous Control Tasks

R. Sander et al.

https://arxiv.org/abs/2205.09117

山田(ymd)2022/05/24

Neighborhood Mixup Experience Replay (NMER)

線型補完による一般化で、連続空間におけるサンプル効率化

Replay Buffer から一様にミニバッチをサンプル
state-action (を Z score変換した) 空間で、各サンプル ( $x_s$ ) の最近傍サンプル ( $x_{\text{NN}}$ ) を探す
$\lambda \sim \beta (\alpha, \alpha)$ (ベータ分布) で係数 $\lambda$ を決める
線型補完点 $x_i = \lambda x_s + (1-\lambda) x_{\text{NN}}$ を学習に加える

山田(ymd)2022/06/24に更新

Look Back When Surprised: Stabilizing Reverse Experience Replay for Neural Approximation

R. Kumar and D. Nagaraj

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

RER++ = Reverse Experience Replay (RER) + Optimistic Experience Replay (OER)

山田(ymd)2022/06/12

探索 1step毎に
buffer 内の遷移の重要度を計算
重要度上位 $G$ 個の遷移のインデックス ( $I_1, ..., I_G$ ) を抽出
$G$ 個のインデックス毎に
1. 抽出したインデックスから前方向に $B$ 個の連続した遷移 ( $T_{I_i -B +1}, ..., T_{I_i}$ ) をミニバッチとしてモデル学習

山田(ymd)2022/06/12

RERはミニバッチ毎に1stepずつ過去へ遡って学習するが、
RER++では連続した $B$ step が同じミニバッチで一度に学習される。

RERは、疎な報酬の環境の状態価値を効率よく伝搬することが感覚的に理解できた (明確な証明があるのかは不明) が、RER++ではどうなのだろうか？

重要度上位の遷移をミニバッチとして学習して、RERのように順番に過去方向にずらして学習したらどうなるのだろうか？？

山田(ymd)2022/06/24

MASER: Multi-Agent Reinforcement Learning with Subgoals Generated from Experience Replay Buffer

J. Jeon et al.

https://arxiv.org/abs/2206.10607

山田(ymd)2022/08/24

Reinforcement learning with experience replay and adaptation of action dispersion

P. Wawrzyński et al.

https://arxiv.org/abs/2208.00156

山田(ymd)2022/09/14

Actor Prioritized Experience Replay

B. Saglam et al.

https://arxiv.org/abs/2209.00532

山田(ymd)2022/09/19

著者らの研究による発見（主張）

Actor ネットワークはTD誤差の小さい遷移で学習させなければならない
- TD誤差が大きい（≒ Critic推定が悪い）遷移は、policy gradientを真の値から逸らしてしまうので、効率の良いActorの学習ができない。
Actor / Critic ネットワークは一様分布で学習させなければならない
- ActorとCriticを低TD誤差や高TD誤差など、全く異なる遷移で学習させることはActor-Critic理論に反している
- 実験的にも一様分布で学習させることが学習の安定性に影響することを示した
Prioritized Samplingでは、outlier bias leakage (外れ値バイアス？) を防ぐために損失関数を修正すべき

→ Loss-Adjusted Approximate Actor Prioritized Experience Replay (LA3P) 法の提案

山田(ymd)2022/09/19

公式ソースコード

https://github.com/baturaysaglam/LA3P

山田(ymd)2022/09/29

1 探索 step 毎の学習 mini-batch サイズを $N$ 、分割ハイパーパラメータ $\lambda \in [0, 1]$ として、

$\lambda N$ 遷移を一様にサンプルする
Critic $\to$ Actor の順に、損失 $\mathcal{L}_{\text{PAL}}$ でパラメータ更新
$(1-\lambda) N$ 遷移を、 $p_i \sim \max (|\delta_i|^{\alpha}, 1)$ で重点サンプリングして、Critic を更新する
$(1-\lambda)N$ 遷移を、 $1/p_i$ で重点サンプリングして、Actor を更新する

著者らの実験によると $\lambda = 0.5$ が最も良い結果

山田(ymd)2022/09/14

Prioritizing Samples in Reinforcement Learning with Reducible Loss

T. Kim and D. Har

https://arxiv.org/abs/2208.10483

山田(ymd)2022/10/02

公式実装

山田(ymd)2022/10/02に更新

一部学習データをHold outすることで、そのデータによる損失減少を見積もる Reducible Loss (ReLo) を強化学習に採用する手法

Target ネットワークは、一定の間隔でパラメータを同期させるため、直近のデータを学習していない擬似的なHold outモデルとみなすことができる

\text{ReLo} = \mathcal{L}(\theta) - \mathcal{L}(\theta _ {\text{target}})

この ReLo を PER の TD誤差の代わりに遷移の重要度して利用する。

p_i = \max (\text{ReLo}, 0) + \epsilon

Hidden comment

山田(ymd)2022/10/30

MEET: A Monte Carlo Exploration-Exploitation Trade-off for Buffer Sampling

J. Ott et al.

https://arxiv.org/abs/2210.13545#

山田(ymd)2022/10/30

However, to the best of our knowledge, the uncertainty of the Q-Value estimation has not yet been used to leverage exploration and exploitation for buffer sampling. In that way, the proposed method samples more useful transitions in continuous action space problems, without any further assumptions on the RL model.

Q値推定の uncertainty を利用して、探索とバッファ・サンプリングを効率化する手法

山田(ymd)2022/10/30

multihead の DQN で Q値の不確かさを推定し、

p = \sigma ^2 (Q) \left ( \mu (Q) + \frac{1- \mu(Q)}{N(v)} \right )

の重要度で、Replay Buffer からサンプルする。

山田(ymd)2022/10/30

$N(v)$ は回数で、遷移と一緒に Replay Buffer に保存しておき、サンプルする毎に +1 増加する。

山田(ymd)2022/10/30

公式実装

山田(ymd)2022/10/30

uncertainty に着目する着想はおもしろい。
実験結果はあんまり有意な差があるようには見えなかった。

$10^6$ 程度の大きな buffer を使うことが多いと思うが、遷移毎に定義したサンプル回数 $N(v)$ がそんなに大きくなるほど何度もサンプリングされるのだろうか？

後継研究の発展に期待

山田(ymd)2022/10/30

Memory-efficient Reinforcement Learning with Knowledge Consolidation

Q. Lan et al.

https://arxiv.org/abs/2205.10868

山田(ymd)2022/10/30

(著者らは蒸留と位置づけているが、) target network との L2 正則化項を追加することで、Replay Buffer のサイズを 10% に縮小しても、DQNと同等の性能を出したとの主張

また、L2項は、サンプルした遷移ではなく、state 空間から一様ランダム抽出した仮想 state で、action は総和をとっている。

L_{\text{consolid}} \equiv \mathbb {E}_{\pi} \left [ \sum _{a \in \mathcal{A}} \left( Q_{\theta}(s, a) - Q_{\theta ^{\prime}}(s,a) \right)^2 \right ]

山田(ymd)2022/11/02

Event Tables for Efficient Experience Replay

V. Kompella et al.

https://arxiv.org/abs/2211.00576

山田(ymd)2022/11/05

$n$ 個の buffer $B_1,\dots, B_n$ を別途用意し、
条件 $\omega _i (s_{t+1}) == 1$ となる際に、
直近 $\tau _i$ 遷移をbuffer $B _i$ にも保管する

山田(ymd)2023/02/26

Offline Q-learning on Diverse Multi-Task Data Both Scales And Generalizes

A. Kumar et al.

https://arxiv.org/abs/2211.15144

提案手法: Scaled QL: Multi-task pre-training with conservative Q-learning

Multi-task Pretraining + Offline RL
従来手法よりも大きな ResNet 101 を採用
cross-entropy ベースの distributional backup
特徴量正規化
Conservative Q-Learning (CQL) ベースの学習
- TD誤差 + 正則化: 未知の行動のQ値を最小化 & データセットのQ値を最大化

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

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

Offline RL の情報をまとめた awesome-offline-rl

Safe and Efficient Off-Policy Reinforcement Learning

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

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

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

off-policy deep RL

1. Importance Sampling

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

3. Tree Backup TB(\lambda)

4. Retrace(\lambda)

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

Reconciling \lambda-Returns with Experience Replay

Sparse Graphical Memory for Robust Planning

Search on the Replay Buffer: Bridging Planning and Reinforcement Learning

Semi-parametric Topological Memory for Navigation

Mapping State Space using Landmarks for Universal Goal Reaching

Hallucinative Topological Memory for Zero-Shot Visual Planning

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

Enhanced Off-Policy Reinforcement Learning With Focused Experience Replay

A Deeper Look at Experience Replay

Experience Replay with Likelihood-free Importance Weights

Large Batch Experience Replay

Explanation-Aware Experience Replay in Rule-Dense Environments

Improving Experience Replay through Modeling of Similar Transitions' Sets

Improving Experience Replay with Successor Representation

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

Convergence Results For Q-Learning With Experience Replay

Replay For Safety

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

Lucid Dreaming for Experience Replay: Refreshing Past States with the Current Policy

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

Improving the Efficiency of Off-Policy Reinforcement Learning by Accounting for Past Decisions

Double Prioritized State Recycled Experience Replay

Model-augmented Prioritized Experience Replay

MaPER

効果

不明点

Why Should I Trust You, Bellman? The Bellman Error is a Poor Replacement for Value Error

GA-DRL: Genetic Algorithm-Based Function Optimizer in Deep Reinforcement Learning for Robotic Manipulation Tasks

A DPDK-Based Acceleration Method for Experience Sampling of Distributed Reinforcement Learning

Learning to Reach Goals via Iterated Supervised Learning

[提案手法] Goal-conditioned supervised learning (GCSL)

[効果]

Remember and Forget Experience Replay for Multi-Agent Reinforcement Learning

Topological Experience Replay

Variance Reduction based Partial Trajectory Reuse to Accelerate Policy Gradient Optimization

Green Simulation Assisted Policy Gradient to Accelerate Stochastic Process Control

Neighborhood Mixup Experience Replay: Local Convex Interpolation for Improved Sample Efficiency in Continuous Control Tasks

Look Back When Surprised: Stabilizing Reverse Experience Replay for Neural Approximation

MASER: Multi-Agent Reinforcement Learning with Subgoals Generated from Experience Replay Buffer

Reinforcement learning with experience replay and adaptation of action dispersion

Actor Prioritized Experience Replay

Prioritizing Samples in Reinforcement Learning with Reducible Loss

MEET: A Monte Carlo Exploration-Exploitation Trade-off for Buffer Sampling

Memory-efficient Reinforcement Learning with Knowledge Consolidation

Event Tables for Efficient Experience Replay

Offline Q-learning on Diverse Multi-Task Data Both Scales And Generalizes

提案手法: Scaled QL: Multi-task pre-training with conservative Q-learning

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

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

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

3. Tree Backup TB $(\lambda)$

4. Retrace $(\lambda)$

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

Reconciling $\lambda$ -Returns with Experience Replay