![exploration bonus with pseudo-count
以下の式(6)によるexploration bonusを与える
係数は0.05を使用
+0.01は安定化のため
この値は、今回のDQNでは報酬を[-1, +1]に限定しているため
正規化の必要はなし](https://image.slidesharecdn.com/unifyingcount-basedexplorationandintrinsicmotivation-160925153844/85/Unifying-count-based-exploration-and-intrinsic-motivation-22-320.jpg)
論文紹介 : Unifying count based exploration and intrinsic motivation
- 1. Unifying Count-Based Exploration and Intrinsic Motivation 第34回 強化学習勉強会 in RECRUIT Katsuki Ohto @ YuriCat (github)
- 2. 論文概要 Unifying Count-Based Exploration and Intrinsic Motivation (Bellemare et al. 2016) NIPS2016採択論文 Atari2600のゲームで最難関とされていたMONTEZUNA’S REVENGEにおいて 飛躍的な向上 （MONTEZUNA’S REVENGEのプレイ動画） https://www.youtube.com/watch?v=0yI2wJ6F8r0 以降式や図は特に注釈がない限りこの論文からの引用
- 3. DQN (Mnih et el., 2013), (Mnih et al., 2015) deep Q-network 画面の画素情報からconvolutional neural network により離散的行動の価値を予測 (Mnih et al., 2015)
- 4. DQN (Mnih et el., 2013), (Mnih et al., 2015) Atari2600の多くのゲームにおいて 「プレイ画面の画像」と「報酬」だけからの強化学習に成功し人間より上達した 例) ブロック崩し (Mnih et al., 2015)
- 5. DQNの進歩 Gorila DQN (Nair et al., 2015) … DQNを並列環境で学習 Double DQN (van Hasselt et al., 2015) … 2つのQ関数を学習するDouble Q-learning を適用（後ほど詳しく） hierarchical-DQN (Kulkarni et al., 2016) … 低レベルの行動方策とメタ行動方針の階 層的な構造のDQN （詳細は小山田創哲さんのスライド http://www.slideshare.net/sotetsukoyamada/kulkarni-et-al-2016）
- 7. MONTEZUNA’S REVENGE Atari2600のゲームのうち、 DQNにとって最も難しいと 言われていた内の1つ ?多くの敵や罠 ?多数の部屋による迷路的な構成 ?報酬を得ることが少なく、即時性がない (Kulkarni et al., 2016)
- 8. 本論文の動機 ?報酬が疎 (sparse) で、遅れて得られる (delayed) 場合 →探索的行動 (exploration) が重要。 そのため観測した状態が新奇かどうか知りたい ?状態が高次元 →状態や（状態, 行動）、（状態, 報酬）などの経験回数を実際に数えても 役に立たない（完全に同じ状態に到達することが少ない） よって、（厳密には）新奇の状態に対しても擬似的な経験回数を算出し、 探索的行動を促進したい
- 14. information gain sequential density modelのクラス 上の混合モデル を 以下の確率分布関数とする この重みwの観測xによる更新式は以下 この重みの確率分布間のKulback-Leibler divergenceがinformation gain
- 15. prediction gain information gainの計算は難しかったり決定不可能であったりする prediction gainがよい近似になる xを一回観測したことによる情報量の差
- 16. pseudo-countとinformation gainとの関係 (Theorem 2) information gain prediction gain pseudo-count は以下の関係を満たす Information gainは混合モデル上で計算される値だが、 prediction gainとpseudo-countはそれを必要としない
- 18. pseudo-countの性能実験 (Figure 1) 確率分布モデルとして CTSモデル(Bellemare et al., 2014)を使用 Atari2600のFREEWAYとPITFALLにて baseline eventとsalient eventの pseudo-countを計算 ?baseline eventのpseudo-countがフレーム数に 対して線形増加 ?salient eventを観測しうる区間（背景が緑色） においてsalient eventのpseudo-countが増加
- 19. CTS density model 確率分布モデルとして CTSモデル(Bellemare et al., 2014)を使用 状態x（画面全体）中の各ピクセルの値をfactorと考え、 (i, j)ピクセルが (i - 1, j), (i, j - 1), (i - 1, j - 1), (i + 1, j - 1) ピクセルをparentとするグラフィカルモデル フレームの各画素の値を予測するする確率モデル
- 20. Double DQN (van Hasselt et al., 2015) Q関数を2つ用意し、互いの値を利用して値を更新する Double Q-Learning (van Hasselt, 2010)をDQNに適用 Q学習の際に現在の推定価値のargmaxを取ることによる過大評価を防ぐ
- 21. Double Q-learning (van Hasselt, 2010) 一般的なQ-learingの更新式 Double Q-learningにおける更新式 または
- 22. exploration bonus with pseudo-count 以下の式(6)によるexploration bonusを与える 係数は0.05を使用 +0.01は安定化のため この値は、今回のDQNでは報酬を[-1, +1]に限定しているため 正規化の必要はなし
- 23. Double DQN with exploration bonus + MC return 更新式にさらにモンテカルロ法による「報酬」和を加える ここにもexploration bonusを加える モンテカルロ項は計算時間短縮のために追加、 ほぼ全てのゲームで性能向上に寄与 experience replayなのでモンテカルロ項計算の遅延は問題ない
- 24. Experiment: 5つのゲームでの学習の進行比較 Atati2600の5つのゲーム （難しいもののうち、CNNの価値関数とCTS density modelが使えるもの）にて ?exprolation bonusなしDQN ?1フレームごととエピソード終了時に負の報酬を得るDQN (optimistic initialization) (Machado et al., 2014) ?exploration bonusを加えたDQN を比較
- 25. Result: 5つのゲームでの学習の進行 (Figure 2) 各ゲームでの平均得点推移（?1億フレーム）DQN optimistic bonus ?MONTEZUNA’S REVENGE, VENTUREにてbonusありが圧倒 ?FREEWAYではoptimisticでも良い成績(no bonusはおそらく2回失敗) ?PRIVATE EYEはexploration bonusを入れても出来ない
- 26. Result : “known worlds” for agent (Figure 4) 上：no exploration bonus 下：with exploration bonus bonusを加えることでより多くの部屋に到達 (学習開始から5000万フレーム)
- 27. A3C (Mnih et al., 2016) Asynchronous Advantage Actor-Critic の略 ①asynchronousに複数のエージェントで学習を走らせる → experience replayをしなくても学習が上手くいく ②actor-criticにする（方策と価値推定の両方を学習する） ③価値関数はadvantage（R - V(s)）2乗を最小化、方策はadvantageを最大化 詳しくは藤田康博さんのスライドにて http://pt.slideshare.net/mooopan/a3c-62170605
- 28. Result : A3CとA3C+の比較 A3Cのパラメータ更新の際の報酬にexploration bonusを加えたものをA3C+とする Atari2600の60のゲームでA3CとA3C+を比較 ベースのA3Cは15のゲームで学習に失敗（ランダムより50%以上伸びない） 一方A3C+は10のゲームでのみ学習に失敗 （DQNは8）
- 29. Result : A3CとA3C+の比較 (Figure 5) A3Cの2億フレームでの得点に対する 各段階の得点の割合（p.15の式） ?中央値（太線）は2億フレーム付近 では大きな差はない ?A3C+（exploration bonusあり）は 1/4程度のゲームで、 半数の1億フレームでA3Cと同程度
- 30. Experiment: exploration bonusの与え方の検討 式(6)ではexploration bonusを以下の式で与えた これは Model-based interval estimation with exploratory bonus (MBIE-EB) (Sterl and Littman, 2008)のexploration bonusと同じ形状であった
- 31. Experiment: exploration bonusの与え方の検討 ここではexploration bonusの式を以下の形式に書き換えてみる Bayesian Exploration Bonus (Kolter and Ng, 2009) もしくは compression progress (Shumidhuber, 2008)に近い手法で prediction gainに係数を掛けてbonus項にする
- 32. Result : exploration bonus の与え方 (Figure 6) Atari2600の60のゲームにて各条件で学習 inter-algorithm score distribution (Bellmare et al., 2013) を指標に 全てのゲームでの総合成績を検討 （グラフの見方） 高いスコアを出したゲーム割合 ←→ 低くないスコアを出した ゲーム割合
- 33. Result : exploration bonus の与え方 (Figure 6) ?no bonusは一部（おそらく、探索重要度 が低い）ゲームでは高い得点 ? は学習の立ち上がりが早い ? は1000万フレームでは特に高 い得点は出にくい（探索を重視する）が 2億フレームやると良い成績に ? の得点は低い
- 34. Future Work ?sequential density model の選択によって状態空間上の距離が定義出来るか ?Solomonoff induction (Hutter, 2005) のような全域な確率密度モデルの解析 ?sequential density modelとDQNにおけるQ-learningの学習速度があっていないの で、密度モデルに忘却を導入するか、密度モデルとQ関数を対応が取れたものにす る ?連続空間においてもpseusdo-count が回数の概念に合うかどうかの検証
- 35. 引用文献 Bellemare et al. (2016). Unifying Count-Based Exploration and Intrinsic Motivation. NIPS2016 Mnih et al. (2013). Playing Atari with Deep Reinforcement Learning. Mnih et al. (2015). Human-level control through deep reinforcement learning. Nair et al. (2015). Massively Parallel Methods for Deep Reinforcement Learning. van Hasselt et al. (2015). Deep Reinforcement Learning with Double Q-learning. Kulkarni et al. (2016). Hierarchical Deep Reinforcement Learning: Integrating Temporal Abstraction and Intrinsic Motivation. NIPS2016 Bellemare et al. (2014). Skip Context Tree Switching. 31st ICML
- 36. 引用文献 van Hasselt et al. (2015). Double Q-learning. NIPS2010 Machado et al. (2014). Domain-independent optimistic initialization for reinforcement learning. arxiv:1410.4604 Mnih et al. (2016). Asynchronous methods for deep reinforcement learning. arXiv:1602.01783 Strehl and Littman. (2008). An analysis of model-based interval estimation for Markov desicion process. Journal of Computer Science, 74(8):1309 - 1331. Kolter and Ng. (2009). Near-bayesian exploration in polynominal time. 26th ICML Shumidhuber. (2008). Driven by compression progress.
- 37. 引用文献 Bellemare et al. (2013). The Arcade Learning Environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47: 253-279 Hutter (2005). Universal artificial intelligence: Sequential decisions based on algorithmic probability. Springer
- 38. pseudo-countを用いたexplorationの目的 explorationの度合いについては以下の4段階に分けて考えられる（大渡考察） 0. 常に最適と推測した行動を選択（SARSA等） 1. 最適と推測していない行動もたまに選択（epsilon-greedy等）←DQN 2. 新奇な状態に遷移しそうな行動を選択 3. 新奇な状態を探索できそうな行動を選択（理想） Q学習により3まで到達可能だが 特にモンテカルロ項を加えたことで3に対する学習が促進されたのでは