【論文的な】Learning Montezuma’s Revenge from a Single Demonstration (2018)

[Learning Montezuma's Revenge from a Single Demonstration](https://blog.openai.com/learning-montezumas-revenge-from-a-single-demonstration/)
↑動画もある

<img width="707" alt="image.png" src="https://qiita-image-store.s3.amazonaws.com/0/62450/a3948e21-60cf-5a4b-5c89-e1f0a06c626b.png">


# メタ情報
- OpenAI
- ブログポストだが、そのうち論文にするのだろうか？

# 概要
- [Montezuma’s Revenge \(Atari 2600\)](https://www.retrogames.cz/play_124-Atari2600.php?language=EN)[^1] で 74,500 のハイスコア達成
    - 利用したデモンストレーションのスコアは 71,500 だった
- アプローチはシンプル：デモンストレーションから選んだ状態からゲームをプレイさせ、PPO で学習する

# 探索と学習
- 強化学習の課題は大きく2つ：
    - 探索：良い報酬となる行動系列を見つける
    - 学習：行動系列 (とその結果) を汎化する
- 提案法のようにデモンストレーションから開始することで探索課題は解決できそうだ。今回得られた結果から、難しかったのは探索のほうであったらしいことがわかる

# なぜ探索が難しいのか
- 方策勾配法やQ学習のようなモデルフリー型手法は、ランダム行動で探索をおこなう
    - これがうまくいくのは、ランダム行動でもなんらかの報酬が得られやすいとき、つまり報酬が密なときだ
- この前提は Montezuma's Revenge のような、ランダム行動による報酬がほぼ貰えない (疎である) ゲームには当てはまらない
    - ランダム行動では報酬を得るのに指数的な試行が必要となる

# デモンストレーションによる探索の単純化

<img width="707" alt="image.png" src="https://qiita-image-store.s3.amazonaws.com/0/62450/a3948e21-60cf-5a4b-5c89-e1f0a06c626b.png">

- モデルフリー型強化学習は長い行動系列に弱いが、短い行動系列ではうまくいく
    - よって短い行動系列のサブタスクを解くようにカリキュラム学習をおこなう
        - 具体的には、デモンストレーションの各状態からエピソードを開始する
- エピソードの開始状態は、デモンストレーションの最後から逆順にだんだんと伸ばしていく
    - 試行のうち20%で、クリアできるかまたはデモンストレーションのスコアと並んだら、開始状態をバックさせる
- この方法は、動的計画法の方式で強化学習を解いていると解釈できる
    - 指数的な課題を線形時間に落とす
- デモンストレーション状態から開始する方法は以前にも提唱されている ([\[1607\.05077v1\] Playing Atari Games with Deep Reinforcement Learning and Human Checkpoint Replay](https://arxiv.org/abs/1607.05077v1)) が、だんだん後ろにずらすようなカリキュラムを組むわけではなかった

# 模倣学習との比較
- 最近 DeepMind が Montezuma's Revenge をデモンストレーションからの模倣学習で解く手法を提案した
    - YouTube をデモンストレーションとして使う方法： [\[1805\.11592v1\] Playing hard exploration games by watching YouTube](https://arxiv.org/abs/1805.11592v1)
    - デモンストレーションの行動の尤度を最大化するQ学習の方法： [\[1805\.11593v1\] Observe and Look Further: Achieving Consistent Performance on Atari](https://arxiv.org/abs/1805.11593v1)
- これらの手法の良い点は、任意の状態へのリセットなどの環境の制御が不要であること
    - ただし提案法では模倣学習ではなく目標はあくまでスコアの最大化である
    - よって、提案法は局所解への過学習の回避や、自己対戦をおこなえるゲームでのマルチエージェントシステムに対して利点がある

# 将来の課題
- デモンストレーションとエージェントで環境側の設定が異なったりすると、全く同じ行動系列で同じ状態にたどり着けなくなったりする
    - Montezuma's Revenge では問題なかったが、Gravitar や Pitfall のような、微妙な状態の違いの影響が大きいゲームではあまりうまくいっていない
    - 実際に人間がダウンサンプリングした画面でプレイしてみたらうまくできない
    - 方策ネットワークを深くし、ダウンサンプリングせずに入力したらうまくいきそうだ
- 探索と活用のバランスが難しい
    - 例えば方策勾配法のような標準的な強化学習アルゴリズムは、探索が多すぎるとスコアを得ることが出来ないし、活用が多すぎると学習が止まってしまう
    - 今回も、PPO のエントロピー項の係数を始めとして、学習率や報酬のスケーリングといったハイパーパラメータの調整が大変だった
    - 学習の安定性も良くない。学習に失敗することも多かった
- 人間はもっとノイズに対して頑健である
    - 方策ネットワークに意地悪 ([\[1709.06009v2\] Revisiting the Arcade Learning Environment: Evaluation Protocols and Open Problems for General Agents](https://arxiv.org/abs/1709.06009v2 "[1709.06009v2] Revisiting the Arcade Learning Environment: Evaluation Protocols and Open Problems for General Agents")) すると、人間に同じことをするよりもスコアが下がってしまう

# 結論
- デモンストレーションを利用する方法は、これまでは模倣学習が多かったが、提案法では報酬を直接最適化できる
    - これによってデモンストレーションとは微妙に異なる状況にも対応できるようになる
- デモンストレーションの終端状態から徐々にカリキュラムを組むことで、長い行動系列のゲームでもうまくプレイできた

# 参考資料
- [Learning Montezuma's Revenge from a Single Demonstration](https://blog.openai.com/learning-montezumas-revenge-from-a-single-demonstration/)
    - 公式
- [\[1709.06009v2\] Revisiting the Arcade Learning Environment: Evaluation Protocols and Open Problems for General Agents](https://arxiv.org/abs/1709.06009v2 "[1709.06009v2] Revisiting the Arcade Learning Environment: Evaluation Protocols and Open Problems for General Agents")
    - human starts に代わる評価方法 (sticky starts)
- [Reverse Curriculum Generation for Reinforcement Learning · Issue #525 · arXivTimes/arXivTimes](https://github.com/arXivTimes/arXivTimes/issues/525#issuecomment-403757586 "Reverse Curriculum Generation for Reinforcement Learning · Issue #525 · arXivTimes/arXivTimes")
- [\[1607\.05077v1\] Playing Atari Games with Deep Reinforcement Learning and Human Checkpoint Replay](https://arxiv.org/abs/1607.05077v1)
- [\[1805\.11592v1\] Playing hard exploration games by watching YouTube](https://arxiv.org/abs/1805.11592v1)
- [\[1805\.11593v1\] Observe and Look Further: Achieving Consistent Performance on Atari](https://arxiv.org/abs/1805.11593v1)

# 感想
- [【論文】Reverse Curriculum Generation for Reinforcement Learning (2017) - Qiita](https://qiita.com/keisuke-nakata/items/e80cee61d3887e42932f "【論文】Reverse Curriculum Generation for Reinforcement Learning (2017) - Qiita") とは違って、デモンストレーションからカリキュラムを組むので、必ずしも「逆」の行動がなくとも良い
    - 一方で、デモンストレーションの任意状態から学習を始めるためには、特定の状態へのリセット、または、完全なシード固定のどちらかが必要になる


[^1]: 様々な仕掛けのあるステージを切り替えながらアイテムを拾い集めるゲーム。時間方向の依存性やステージ切り替え等の理由から、これまでの強化学習で解くのは非常に難しいことが知られている