[論文解説] DisCor: Corrective Feedback in Reinforcement Learning via Distribution Correction

この記事は，以下の論文の解説です．

DisCor: Corrective Feedback in Reinforcement Learning via Distribution Correction (ICLR 2020)

記事内容では，強化学習の基礎的な知識を前提としています．
また，記事中の図は全て論文からの引用です．
不備がございましたら，ご指摘頂けると幸いです．

また，この論文で提案する手法(DisCor)の再現実装をGithubで公開しています．アルゴリズムがわかりやすいように工夫して，コメントも詳しく書いていますので，理解の助けになればと思います．ぜひ参照してみてください．

概要

この論文では，「過去・現在の方策に基づいて収集したデータ分布で学習を行うことで，状態行動価値の近似誤差が小さくなるようなデータ収集と状態行動価値の学習の関係性 = corrective feedback 」 を享受できないことが，深層強化学習において学習が不安定になる要因であると考察しています．

そして，リプレイメモリのデータを重み付けすることで，収集したデータの分布を，corrective feedback を享受できるようなデータ分布に修正する手法 DisCor を提案しています．

Corrective Feedbackとは

ここでは，真の最適状態行動価値 $Q^*(s,a)$ を用いて教師あり学習で強化学習を行う場合と，Q学習やActor-Criticなどの関数近似により状態行動価値を推定して強化学習を行う場合(ADP; Approximation Dynamic Programming )を考えます．このとき，ADPにおいて探索の問題を切り分けて考えるために，すべての状態遷移をアルゴリズムに与えています．その後，ADPにおいて corrective feedback を享受できない例をみていきます．

直感的解釈

バンディット問題(教師あり学習)

まず，真の最適状態行動価値 $Q^{*}(s,a)$ にアクセス可能なバンディット問題を考えます．バンディット問題では，最適状態行動価値 $Q^{*}(s,a)$ は即時報酬 $r(s,a)$ に一致します．このとき，教師あり学習を用いて以下の誤差を最小化することを考えます．

\mathbb E_{s,a}[|Q_k(s,a)-Q^{*}(s,a)|]

Epsilon-greedy などのデータを収集するための方策 $\pi_k(a|s)$ は，$Q_k(s,a)$ において過大評価された行動 $a$ を選択しやすく，結果として $Q^{*}(s,a) = r(s,a)$ を観測します．それに伴い，この過大評価は学習により修正されていき，過大評価されたすべての行動 $a$ について，$Q_k(s,a)$ は $Q^{*}(s,a)$ に収束していきます．この論文では，このように データ収集と誤差の修正が相互に関連している ことを corrective feedback と呼んでいます．

ADP

一方，ADPでは，状態行動価値のターゲットは真の値 $Q^{*}$ ではなく，近似した他の状態行動価値にベルマンオペレータを適用することで推定される値なので，他の状態行動価値の近似誤差が伝播しています．よって，どんなにその状態行動について学習を行っても，ターゲットが誤差を持つ場合，その状態行動の近似誤差が修正されないという問題が生じます．すなわち，近似した状態行動価値において，過大評価された行動に関するデータを収集したとしてもこの過大評価が修正されない 可能性があります．

この例では，データ収集が誤差の修正に貢献していない，すなわち corrective feedback が存在していないと解釈することができます．一般に，ベルマン方程式に基づくアルゴリズムは ターゲットに用いる状態行動価値の正確さ に依存しているため，このような問題が生じてしまいます．

定義

定義1

現在の方策に基づくデータ分布 $d^{\pi_k}$ における，最適状態行動価値 $Q^*$ と現在の状態行動価値 $Q_k$ の近似誤差 $\mathcal E_{k}$ を以下のように定義する．

\mathcal E_k = \mathbb E_{d^\pi_k}[|Q_k - Q^*|]

このとき，$\mathcal E_k$ が学習に伴い $0$ に向かって滑らかに減少することは，corrective feedback が存在していることを示します．もし $\mathcal E_k$ が振動したり増加していれば，アルゴリズムがうまく学習していないことを示します．また十分な近似能力を持ったニューラルネットワークを用いているのにも関わらず $\mathcal E_k$ が $0$ ではない値に収束している場合には，準最適な解に収束していることを示します．

トイプロブレム

ここでは，木構造を持ったMDPを考えます． このMDPは7つの状態を持ち，終端状態(葉ノード)以外は左右の子に進むという2つの決定的な遷移を持ちます．エージェントは，終端状態においてのみ報酬を受け取ります．

上図は，Q学習における学習の過程(赤色が誤差が大きく，緑色が誤差が小さい)を表しています．報酬を受け取ることのできる終端状態は最も訪問確率が低く，終端状態の学習の進行はとても遅くなっています．また終端状態が大きな誤差を持った状態では，中間状態のターゲットにもその誤差が伝播しているので，中間状態の状態行動価値は corrective feedback を享受できず，学習が進みにくくなっています．

上図のように，終端状態から順に状態行動価値を学習していくことができれば，近似誤差は安定して小さくなっていくと考えられます．このとき，自分より終端側の状態行動価値の近似誤差が小さければ，ターゲットの誤差が小さいため corrective feedback を享受できると考えられます．

論文では，このトイプロブレムにおける理論的な考察として，以下の定理2を示しています(証明は論文付録参照)．

定理2

状態数 $|\mathcal S| = 2^H$ ，行動数 $|\mathcal A| = 2$ のMDPを考え，特徴量 $\Phi$ はほぼ正確に最適状態行動価値を近似できるとします．すなわち，$||Q^{*} - \Phi w||_{\infty} \le \epsilon$ であると仮定します．データ分布は，過去の状態訪問分布の線形結合 $D_k = \sum_i d^{\pi_i}$ とすると，最適状態行動価値 $Q^*$ に収束するには $\Omega(\gamma^{-H})$ 回の学習が必要である．

すなわち，たとえすべての状態遷移がリプレイバッファに含まれていたとしても，必要となる学習回数は状態数について指数関数的に増加します．このことは，関数近似を用いた際には訪問回数が小さいほど誤差が修正されにくい ことに起因しています．

影響

この論文では，さらに複数のRLタスクにおいて corrective feedback を享受できないことによる影響を検証しています．上図は，近似誤差(実線)と収益(点線)を表しており，on-policy での学習曲線(左)，リプレイバッファを用いた場合の学習曲線(中央)，スパース・ノイズを持った報酬のタスクにおいてリプレイバッファを用いた場合の学習曲線(右)を示しています．ここで，アルゴリズムはすべての遷移にアクセスできるものとしているので，探索は問題ではないことに注意します．

これら結果から，corrective feedback を享受できないことで以下のような問題が生じていることがわかります．

1. 準最適な状態行動価値への収束
   上図左では，on-policy で学習した際，近似誤差 $\mathcal E_k$ は初めは滑らかに減少しているものの，$0$ より大きい値に収束していることがわかります．

2. 学習の不安定さ
   上図中央では，ADPはリプレイバッファを用いた場合にさえ，学習が不安定になっていることがわかります．例えば，方策が最適に近い収益を獲得しているときでさえ，その後すぐに学習に失敗しています．

3. ノイズが大きい場合の学習の失敗
   上図右では，ADPはスパース・ノイズを持った報酬のタスクにおいて，学習に失敗していることがわかります．

最適なデータ分布

ここまで，on-policy やリプレイバッファを用いてナイーブに学習した際に，ADPが corrective feedback を享受できない例を見てきました．しかし，真の最適状態行動価値 $Q^{*}$ にアクセスできると仮定し，それをもとに corrective feedback を享受するのに最適なデータ分布を計算することができれば，ADPも corrective feedback を享受できる と考えられます．ここでは，そのような最適なデータ分布を導出していきます．

最適解の導出

最適なデータ分布を求める問題を，以下のように定義します．この問題は，データ分布 $p_k$ を用いて状態行動価値 $Q_{k-1}$ を $Q_k$ に更新するときに，近似誤差 $\mathcal E_k$ が最も小さくなるような $p_k$ を求めることを意味します．

\begin{align}
\min_{p_k} \:\:&\mathbb E_{d^{\pi_k}} [|Q_k - Q^*|] \\
{\rm s.t.} \:\: &Q_k = arg\min_Q \mathbb E_{p_k} [(Q-\mathcal B^* Q_{k-1})^2]
\end{align}

この問題の最適解は，以下の定理3を満たします(証明は論文付録参照)．

定理3

上記の最適化問題の最適解 $p_k$ は，以下の関係を満たす．

p_k(s,a) \propto \exp(-|Q_k-Q^*|(s,a))\frac{|Q_k-\mathcal B^*Q_{k-1}|(s,a)}{\lambda^*}

ここで，$\lambda^* \in \mathbb R^+$ はラグランジュの双対変数であり，$p_k$ が確率分布となることを保証する．

したがって，最適解 $p_k$ はベルマン誤差 $|Q_k -\mathcal B^{*} Q_{k-1}|$ が大きく，近似誤差 $|Q_k-Q^{*}|$ が小さい状態行動に，高い確率を割り当てます．ただし，本来は観測できない( $p_k$ が定まって初めて観測できる) $Q^{*}$ と $Q_k$ に依存しているので，これらの値を代替量で推定する必要があります．

代替量による近似

ここでは，$Q^{*}$ や $Q_k$，もしくはそれらが出てくる項 $|Q_k - Q^{*}|$ や $|Q_k - \mathcal B^{*} Q_{k-1}|$ の代替量を考えていきます．

近似誤差の代替量

まず，過去のベルマン誤差の割引累積和 $\Delta_k$ を以下のように定義します．

\begin{align}
\Delta_k &= \sum_{i=1}^{k} \gamma^{k-i}(\prod_{j=i}^{k-1}P^{\pi_j})|Q_i-\mathcal B^* _{i-1}|\\
&= |Q_k-\mathcal B^*Q_{k-1}| + \gamma P^{\pi_{k-1}}\Delta_{k-1}
\end{align}

この $\Delta_k$ は以下の定理4を満たします(証明は論文付録参照)．

定理4

任意の $k$ に対して $k \ge k_0$ となるような $k_0\in\mathbb N$ と $\Delta_k$ が存在し，$\Delta_k$ は状態行動について，以下の式を満たす．

\Delta_k + \sum_{i=1}^{k}\gamma^{k-i}\alpha_i \ge |Q_k-Q^*|, \:\: \alpha_i = \frac{2R_{max}}{1-\gamma} D_{TV}(\pi_i, \pi^{*})

この定理4は，$\Delta_k$ が $|Q_k - Q^*|$ の上界になっているとこを示しています．論文では，この上界を代替量として用いることを提案しています．

ベルマン誤差の代替量

論文では，ベルマン誤差 $|Q_k-\mathcal B^* Q_{k-1}|$ のシンプルな代替量として，1つ前のベルマン誤差の下界 $c_1 = \min_{s,a}|Q_{k-1} - \mathcal B^* Q_{k-2}|$ と上界 $c_2 = \max_{s,a}|Q_{k-1} - \mathcal B^* Q_{k-2}|$ を用いることを提案しています．

重点サンプリングによる分布の射影

最適なデータ分布を近似により計算できたとしても，そのようなデータ分布を探索によって実現することは難しいです．そこで，データ分布 $\mu(s,a)$ を持つリプレイバッファ内のデータを，重み $w_k = \frac{p_k(s,a)}{\mu(s,a)}$ で重点サンプリングする ことが考えられます．しかし一般に，ナイーブな重点サンプリングでは推定値の分散が大きくなってしまい，学習が不安定になってしまうことが知られています．

そこで，そのまま重点サンプリングを行う代わりに，データ分布 $\mu$ を $q_k$ に射影するように重点サンプリングを行うことが考えられます．ただし，$\tau>1$ として，$q_k$ は以下の式で表されます．

q_k = arg\min_q (D_{KL}(q||p) + (\tau - 1)D_{KL}(q||\mu))

$q_k$ はKLダイバージェンスにおいて $\mu$ に近いままであるように射影されます．この重点サンプリングの重み $w_k$ は，以下の式で表されます(導出は論文付録参照)．

w_k(s,a) \propto \exp(\frac{-|Q_k-Q^*|(s,a)}{\tau})\frac{|Q_k-\mathcal B^* Q_{k-1}|}{\lambda^*}

計算全体

これまでの議論で，最適なデータ分布 $p_k$ を導出し，それを推定するための代替量を定義し，そのデータ分布を獲得するための重点サンプリングを考えました．以下では，これらをすべてまとめていきます．

まず，定理4に $\Delta_k$ の再帰式を代入し，$|Q_-\mathcal B^{*} Q_{k-1}|$ の上界の代替量 $c_2$ で挟み込むことで，以下の $|Q_k - Q^{*}|$ の上界を得ます．

|Q_k - Q^*| \le \gamma P^{\pi_{k-1}} \Delta_{k-1} + c_2 + \sum_i \gamma^i \alpha_i

この上界と，ベルマン誤差の下界の代替量 $c_1 \le|Q_k-\mathcal B^{*}Q_{k-1}|$ を用い，定数項 $c_1$，$c_2$，$\lambda^{*}$ を省略することで，前述の重点サンプリングの重み $w_k$ は以下のように表すことができます(簡単な式変形で導出できます)．この重みでは，負の指数部分に上界，比例係数部分に下界を用いており，常に重みが小さくなるように"保守的な"近似を行っていることがわかります．

w_k \propto \exp(-\frac{\gamma[P^{\pi_{k-1}}\Delta_{k-1}](s,a)}{\tau})

直感的には，指数部の $P^{\pi_{k-1}}\Delta_{k-1}$ は，過去のベルマン誤差の蓄積が伝播することにより生じる現在のターゲットの誤差の上界の推定値であると考えることができます．したがって，ターゲットと真の状態行動価値 $Q^*$ の誤差が大きい状態行動に関して，データの重みを小さくしていると解釈できます．これにより，ターゲットが正確な状態行動から順に学習係数が大きくなるように重み付けをすることで，corrective feedback が生じるような順番で学習していると解釈できます．

アルゴリズム(DisCor)

DisCorの具体的なアルゴリズムは，上の疑似コードのようになります．

通常のADPとの違いは赤色で示されています．まず，通常の状態行動価値に加えて，$\Delta_k(s,a)$ を推定するためのエラーモデル $\Delta_\phi$ を学習します．このエラーモデルは，$\Delta_k$ の再帰式に基づいて学習を行います(8行目)．また，この $\Delta_\phi$ を用いて計算された重み $w_k$ で，リプレイバッファのデータの重み付けを行っています(6行目)．

検証

連続行動RL

連続行動RLとして，上図のMeta-Worldの6つのマニピュレーションタスクで検証しています．比較対象として，Soft Actor-Critic(SAC)，SAC + Prioritized Experience Replay(PER)を用い，DisCorもSACをベースに実装しています．

上図からは，DisCorは他の手法に比べて効率的に学習できていて，いくつかのタスクでは他の手法を上回る最終性能を示していることが分かります．一方で，PERは逆に性能悪化に繋がっていることが分かります．これは，ターゲットが大きな誤差を持つ状態行動については，優先度重みも大きくなり頻繁に学習に用いられるようになる一方，corrective feedback を享受しないために学習が進まないことが原因であると推測されます．

離散行動RL

離散行動RLとして，AtariのPong，Breakout，Asterixで検証しています．比較対象として，DQNを用い，DisCorもDQNをベースに実装しています．

上図から，DisCorはDQNに比べて高い性能を示していることが分かります．

まとめ

この論文では，多くの強化学習アルゴリズムが corrective feedback を享受できていないこと，それにより学習の不安定性などの問題を引き起こしていることを示しました．さらに，corrective feedback を享受するための最適なデータ分布の計算方法を導出し，データの重み付けによりデータ分布の修正を行うアルゴリズム DisCor を提案しました．