[論文解説] BCQ: Off-Policy Deep Reinforcement Learning without Exploration

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

[Off-Policy Deep Reinforcement Learning without Exploration](https://arxiv.org/abs/1812.02900) (ICLR 2018)



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

**UPDATE**

- 2020/08/20
    - BCQの"Perturbation Model"の訳をノイズモデルとしていましたが，誤解を招きやすい不適切な訳でした．
    - このモデルでは"決定論的な"摂動を学習することから，**摂動モデル**と訳を修正しました．



## 概要

この論文は，主に

- 過去に収集したデータからのみ強化学習を行う**バッチ強化学習**で，既存のoff-policyの手法が学習に失敗する原因は，観測されていない状態-行動ペアの推定行動価値が誤差を持つこと = **extrapolation error**であることを指摘した
- **Batch-Constrained deep Q-learning(BCQ)**を提案し，連続行動タスクでのバッチ強化学習で**extrapolation error**を回避し，効率的に学習できることを示した

論文になります．

この記事では，まずバッチの分布と現在の方策におけるデータ分布の相関が低い場合(i.e. バッチ強化学習)に学習に失敗する原因として，**extrapolation error**に関して検証していきます．

次に，**extrapolation error**を解決する手法として，生成モデルを用いて行動の候補をサンプルすることで，**バッチと似たような状態-行動ペアを遷移していく**ように方策を制約しつつQ学習を行う手法，BCQを説明していきます．



## extrapolation error

近年の強化学習では，off-policyと呼ばれる，すでに収集されたデータから学習を行うことができる手法，すなわち**データを収集する方策と学習する方策が一致することを仮定しない手法**が存在しています．しかし，学習に用いるデータの分布と現在の方策に対応するデータ分布の相関が低くなるにつれ，off-policyの手法が学習に失敗することが知られています．この論文では，このように学習に失敗する原因は，**extrapolation error**によるものだと指摘しています．

**extrapolation error**とは，「観測されていない状態-行動ペアの推定行動価値が誤差を持つこと」です．そもそも，データのない状態-行動ペアの行動価値を正確に推定することは不可能なのかもしれませんが，バッチ強化学習(特に連続行動タスク)ではデータが十分にあるとは限りません．

ある状態-行動ペア$(s',a')$での推定行動価値が誤差を持ってしまうと，Q学習の場合にはベルマンオペレータによって他の状態-行動ペア$(s,a)$の推定行動価値にもバイアスが生じてしまいます．

<div align="center">
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/248552/db2f66e0-bec5-518b-66a2-6f329be17e8a.png" width=600>
</div>



既存のoff-policyの手法(DDPG)では，通常は学習時には$\epsilon$-greedyなどでリプレイバッファにデータを集めていくので，バッチの分布と現在の方策に対応するデータ分布は大きな相関を持っていると考えられます．

以下では，3つの設定でDDPGを学習させ，データ間の相関が小さい時にDDPGの学習が不安定になり，推定価値が発散していくことを検証していきます．ここでは，MuJoCoのHopper-v1の環境を用い，off-policyで学習している方策だけでなく，データ収集方策の平均収益と推定価値も評価します．

- 設定1: **Final buffer**
  - DDPGを通常通り学習させるが，行動に$N(0, 0.5)$のノイズを入れる
  - ノイズが大きいため，現在の方策との相関が小さい，かつ多様なデータが収集されると期待できる
- 設定2: **Concurrent**
  - off-policyでの学習方策だけでなく，収集方策も同時に学習させる
  - 2つの方策は全く同じデータから学習され，初期値のみが異なる

- 設定3: **Imitation**
  - 学習済みのDDPGを収集方策とする
  - 価値の高い(質のいい)データのみが収集されると期待できる

結果は上図に示してあります．どの設定においても，**off-policyで学習した方策は，データ収集方策に比べてパフォーマンスが著しく悪い**という結果になりました(図上段)．価値の推定も，データ収集方策では安定しているのに対し，off-policyでの学習方策では非常に不安定になっていることが分かります(図下段)．

**Concurrent**では，2つの方策は全く同じデータから学習しており，重みの初期値が違うだけなのに大きなパフォーマンス差が生じています．このことから，重みの初期値が違うだけでも，**extrapolation error**が生じるくらい2つの方策の対応するデータ分布が異なってしまうことが分かります．

**Final buffer**では，十分に多様なデータを収集しているので，推定価値が収束することが期待されていたのですが，この場合でも価値が不安定であることが読み取れます．

**Imitation**では，データは全て**Expert**であるにも関わらず，off-policyでの学習方策はすぐにnon-Expertな行動の価値を過大評価してしまい，パフォーマンスは収束してしまっています．

**extrapolation error**では，観測されていない状態-行動ペアの価値を必ずしも過大評価するとは限りませんが，Q学習のmax操作と組み合わさることで価値の過大評価を生じます(詳しくは，[TD3の論文](https://arxiv.org/abs/1802.09477)や[解説](https://qiita.com/ku2482/items/a33fc20490891ddc2a59)を参照してください)．学習途中でのシミュレーションが可能な場合であれば，過大評価した行動は選択されやすくなるため，その行動に関するデータ収集が促進され，過大評価が修正されていきます．しかし，バッチ強化学習では新たにデータを収集することができないため，この過大評価は修正されず，**Imitation**のようにすぐにsub-optimalな方策に収束してしまいます．



## Batch-Constrained deep Q-learning(BCQ)

上述のように，観測されていない状態-行動ペアの価値は一貫して過大評価されてしまいます．一方で，データの存在する領域の行動価値は正確に推定できると考えられます．

この論文では，**バッチと似たような状態-行動ペアを遷移していくように方策を制約することで、extrapolation errorを避けよう**というシンプルなアイデアをもとで，**Batch-Constrained deep Q-learning(BCQ)**を提案しています．

**BCQ**では，以下の3つの目的で最適化を行います．

1. 方策が選択する行動とバッチ内の行動が近くなるようにする

2. 遷移先の状態もバッチに含まれるようにする

3. 価値を最大化する(通常の強化学習)

論文では，データがない行動は価値を正確に推定できないため，1が最も重要であると指摘しています．**BCQ**では，生成モデルを用いることで1の条件を実現しています．

**BCQ**では，以下の3つのモジュールにより方策を構成します．

- 生成モデル: $G_\omega(s)$
    - 状態が与えられた際，バッチ内の行動と似た行動の候補を生成
        - $a \sim G_\omega(s)$
    - Conditional VAE([論文](https://arxiv.org/abs/1406.5298)，[解説](https://qiita.com/ku2482/items/da5ecd0c1cfce99f7a66))を学習させることで，条件付き分布からのサンプル $arg\max_a p_{\mathcal B}(a|s)$ を近似
- 摂動モデル: $\zeta_\phi(s, a, \Phi)$
    - 行動の多様性を上げるため，行動に"決定論的な"摂動を加える
    - $\Phi$によって摂動の大きさを制限
    - 価値の最大化を目的に学習される
        - $\phi \leftarrow arg \max_\phi \sum_{(s,a)} Q_\theta(s, a+\zeta_\phi(s,a,\Phi))$
    - バッチ内には少ししかないけど価値が高い行動はバッチ内の行動の分布において確率密度が小さく，CVAEからはサンプリングされにくい．摂動モデルでは，**Extrapolation Errorを生じないようバッチ内の行動の分布から離れすぎず，しかし価値の高い行動を選択しやすくなるようにCVAEからサンプリングされた行動に加える摂動**を学習している
    - (CVAEはあくまでもバッチ内の行動分布を近似するように生成分布を学習するので，摂動モデルで価値が高い行動を選択しやすいように生成分布を微調整していると考えることができる)

- 価値関数: $Q_{\theta_1}, Q_{\theta_2}$
    - 生成モデルから$n$個の行動をサンプルした後，最も価値の高い行動を選択
    - 将来の不確実性に伴う価値の過大評価を抑制するため，**Clipped Double Q**に修正を加えたターゲットを利用
        - $r + \gamma \max\_{a_i} [\lambda \min\_{j=1,2}Q\_{\theta'\_j}(s', a_i) + (1-\lambda) \max\_{j=1,2}Q\_{\theta'\_j}(s', a\_i)]$
    - $\lambda$ によって，どのくらい将来の不確実性にペナルティを与えるかを調整

まとめると，**BCQ**の方策では，生成モデル$G_\omega(s)$を用いて$n$個の行動候補$a_i$をサンプルし，それぞれの行動候補に摂動 $\zeta_\phi(s, a_i, \Phi)$を加えます．その後，最も価値の高い行動 $a = arg \max_{a_i} Q(s, a_i + \zeta_\phi(s, a_i, \Phi))$を選択します．

学習は，生成モデルはConditional VAEのELBO最大化，摂動モデルは価値の最大化，Q関数はClipped Double Qに修正を加えたターゲットとのTD誤差の最小化，を目的として行います．

## 検証

<div align="center">
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/248552/c179e331-7fd8-fb32-241f-6e8d54436d12.png" width=500>
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/248552/414b41c4-cbf8-688d-75e9-5187e91e52f2.png" width=500>
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/248552/7213e0aa-576b-5d5c-04fe-59d631373303.png" width=500>
</div>

MuJoCoベンチマークタスクにおいて，DDPGや**Behaviour Cloning(BC)**らの手法と比較検証しています．また，前の章での検証に加えて，以下の設定を加えています．

- 設定4: **Imperfect demonstration**
  - 0.3の確率でランダム行動
  - 0.7の確率でExpertで行動．ただし，行動に$N(0, 0.3)$のノイズを加える
  - ノイズを伴ったExpertのデモンストレーションに対応

結果として，**BCQ**は全ての設定で学習でき，収集方策よりも優れたパフォーマンスを示した唯一の手法ととなりました(図上4段)．また，推定行動価値も非常に安定していることが読み取れます(図最下段)．

**Imitation**では**Behavior Cloning(BC)**のパフォーマンスが最も高くなっていますが，その他の設定では最も高いパフォーマンスを示しています．**Imperfect demonstration**では，強化学習(DDPG)・模倣学習(BC)の手法が学習に失敗している中，唯一不完全なデモンストレーションから学習に成功しています．さらに，**BCQ**は非常に少ないデータ数$O(10^5)$で学習できており，サンプル効率が非常に良いことが分かります，これらのことから，**BCQ**はノイズの存在下でも，Expertデータを効率的に活用できていると言えます．



## まとめ

この論文では，**BCQ**と呼ばれる，過去データのみから効率的に強化学習を行える手法を提案しました．

今回は紹介していませんが，表形式タスクにおいて **extrapolation error** が生じる条件や，バッチ強化学習において最適方策に収束する手法を提案しています．証明もついていますので，ぜひ論文を参照してみてください．