Reinforcement Learning: An Introduction second edition, Chapter 8 Planning and Learning with Tabular Methods

Reinforcement Learning: An Introduction second edition
Chapter 8 Planning and Learning with Tabular Methods

Sutton輪読会
太⽥ 晋
2019-06-25

Transcript

1. Reinforcement Learning: An Introduction second edition Richard S. Sutton and Andrew G. Barto Sutton輪読会 第8章 Planning and Learning with Tabular Methods 2019/6/25 太⽥ 晋
2. ⽬次 • 8 Planning and Learning with Tabular Methods 159 • 8.1 Models and Planning 159 • 8.2 Dyna: Integrated Planning, Acting, and Learning 161 • 8.3 When the Model Is Wrong 166 • 8.4 Prioritized Sweeping 168 • 8.5 Expected vs. Sample Updates 172 • 8.6 Trajectory Sampling 174 • 8.7 Real-time Dynamic Programming 177 • 8.8 Planning at Decision Time 180 • 8.9 Heuristic Search 181 • 8.10 Rollout Algorithms 183 • 8.11 Monte Carlo Tree Search 185 • 8.12 Summary of the Chapter 188 • 8.13 Summary of Part I: Dimensions 189
3. 今回紹介する範囲 • 8 Planning and Learning with Tabular Methods 159 • 8.1 Models and Planning 159 • 8.2 Dyna: Integrated Planning, Acting, and Learning 161 • 8.3 When the Model Is Wrong 166 • 8.4 Prioritized Sweeping 168 • 8.5 Expected vs. Sample Updates 172 • 8.6 Trajectory Sampling 174 • 8.7 Real-time Dynamic Programming 177 • 8.8 Planning at Decision Time 180 • 8.9 Heuristic Search 181 • 8.10 Rollout Algorithms 183 • 8.11 Monte Carlo Tree Search 185 • 8.12 Summary of the Chapter 188 • 8.13 Summary of Part I: Dimensions 189
4. ⽬次 • 8 Planning and Learning with Tabular Methods 159 • 8.1 Models and Planning 159 • 8.2 Dyna: Integrated Planning, Acting, and Learning 161 • 8.3 When the Model Is Wrong 166 • 8.4 Prioritized Sweeping 168 • 8.5 Expected vs. Sample Updates 172 • 8.6 Trajectory Sampling 174 • 8.7 Real-time Dynamic Programming 177 • 8.8 Planning at Decision Time 180 • 8.9 Heuristic Search 181 • 8.10 Rollout Algorithms 183 • 8.11 Monte Carlo Tree Search 185 • 8.12 Summary of the Chapter 188 • 8.13 Summary of Part I: Dimensions 189
5. プランニングと学習 • 本章の⽬的 • モデルをより⼀般的に考える • プランニング(Planning)と学習(Learning)の統合 • 共通点は価値関数の計算 • モデルベース強化学習の紹介 • モデルベース強化学習 • 代表的な例: 動的計画法、ヒューリスティックサーチ • モデルフリー強化学習 • 代表的な例: モンテカルロ法、TD法
6. モデル • モデル • ⾏動に対して環境がどのように反応するかを予測できるもの • 状態と⾏動が与えられた時に、次の状態と報酬を予測 • S, A → S’, R • 分布モデル(distribution model) • 全ての可能性とその確率を⽣成 p(s’, r | s, a) • 例: 12個のサイコロ • 全ての可能な合計値とその確率をモデルから⽣成 • サンプルモデル(sample model) • 確率に基づいて⼀つのサンプルを⽣成 • 例: 12個のサイコロ • 確率に基づいて⼀つの合計値をモデルから⽣成
7. • プランニング: モデルを使って⽅策を作成・改善する計算過程 • モデルからシミュレートされた経験を⽣成して価値関数を更新 • バックグラウンドプランニング(background planning) • モデルからシミュレートされた経験を⽣成して徐々に価値関数と⽅策を改善 • 現在の状態の⾏動価値を⽐較して、⾏動を選択 • 意思決定時プランニング(decision-time planning) • 新たな状態に出会ってからモデルを使って⾏動を計算 • 現在の状態にフォーカスしてプランニングを⾏い、⾏動を選択 プランニング
8. プランニングと学習の⽐較 • 共通点 • 価値関数の推定 • バックアップ更新 • 違い • プランニング • モデルによって⽣成されたシミュレートされた経験を使う • 学習 • 環境によって⽣成された実際の経験を使う
9. 単純なプランニング⼿法の例 ランダムサンプル 1ステップ 表形式 Qプランニング • Dynaのプランニング⼿法として利⽤(後述)
10. ⽬次 • 8 Planning and Learning with Tabular Methods 159 • 8.1 Models and Planning 159 • 8.2 Dyna: Integrated Planning, Acting, and Learning 161 • 8.3 When the Model Is Wrong 166 • 8.4 Prioritized Sweeping 168 • 8.5 Expected vs. Sample Updates 172 • 8.6 Trajectory Sampling 174 • 8.7 Real-time Dynamic Programming 177 • 8.8 Planning at Decision Time 180 • 8.9 Heuristic Search 181 • 8.10 Rollout Algorithms 183 • 8.11 Monte Carlo Tree Search 185 • 8.12 Summary of the Chapter 188 • 8.13 Summary of Part I: Dimensions 189
11. モデルベース強化学習 • プランニングがオンラインの場合 • 環境との相互作⽤に基づいてモデル が変化→プランニングにも影響 • 価値関数/⽅策の改善 • 直接強化学習 • シンプル • モデル設計のバイアスを受けない • 間接強化学習(モデル経由) • 限られた経験を最⼤限利⽤ • 少数の環境との相互作⽤から、より良 い⽅策を⾒つけることが出来る
12. Dynaのアーキテクチャ • プランニング⼿法 • ランダムサンプル1ステップ表 形式Qプランニング(3ページ前) • 直接強化学習⼿法 • 1ステップ表形式Q学習 • モデル学習⼿法 • 表形式 • 決定論的環境を想定 • 学習とプランニングの違いは 経験の出処のみ
13. 表形式 Dyna-Qアルゴリズム • (e), (f) を除くと通常の1ステップ表形式Q学習 直接強化学習 モデル学習 プランニング
14. 迷路タスクへのDyna-Qの適⽤ • 状態47 (=6×9-7) • ⾏動4 (上下左右) • ゴールで報酬1 • 決定論的環境 • ⾏動価値の初期値0 • γ=0.95 • α=0.1 • ε=0.1 • 実験30回の平均
15. プランニングが速い理由 • 2番⽬のエピソード途中の⽅策の様⼦ • ⻘⽮印はグリーディ⾏動 • 空欄は全ての⽅向の⾏動価値が等しい • デモ • 16b Models and Planning-2.mov • 8:00-11:00 辺り • https://drive.google.com/open?id=15d2I8GLRutv805sGUH5jISol5IDIv7CP
16. ⽬次 • 8 Planning and Learning with Tabular Methods 159 • 8.1 Models and Planning 159 • 8.2 Dyna: Integrated Planning, Acting, and Learning 161 • 8.3 When the Model Is Wrong 166 • 8.4 Prioritized Sweeping 168 • 8.5 Expected vs. Sample Updates 172 • 8.6 Trajectory Sampling 174 • 8.7 Real-time Dynamic Programming 177 • 8.8 Planning at Decision Time 180 • 8.9 Heuristic Search 181 • 8.10 Rollout Algorithms 183 • 8.11 Monte Carlo Tree Search 185 • 8.12 Summary of the Chapter 188 • 8.13 Summary of Part I: Dimensions 189
17. モデルが間違っている場合 (環境が変化) • 環境が変化した時にモデルの誤りが検出される例(左)・されない例(右) • ε-グリーディだけではめったに最適経路を発⾒できない(右図Dyna-Q)
18. Dyna-Q+ • 探索(exploration)と利⽤(exploitation)の対⽴ • 探索: モデルを改善するために様々な⾏動を試す • 利⽤: 現在のモデルにおいて最適な⾏動を選ぶ • 完全かつ実践的な解決策はないが簡単なヒューリスティックがしばしば効果的 • Dyna-Q+におけるヒューリスティック • 経過ステップ数 τ • それぞれの状態-⾏動ペアについて、最後にそのペアを実環境で試してから何ステップ 経過したかを記録 • 経過時間が⻑いほどそのペアのダイナミクスが変わってるかもしれない • (つまり、モデルの誤りを検出できるかもしれない) • ボーナス報酬 • ⻑く試されていない⾏動を促すためにボーナス報酬をシミュレートされた経験に与える • モデルの報酬 r, ⼩さな係数 k, 経過ステップ数 τ とすると、ボーナス報酬は
19. ⽬次 • 8 Planning and Learning with Tabular Methods 159 • 8.1 Models and Planning 159 • 8.2 Dyna: Integrated Planning, Acting, and Learning 161 • 8.3 When the Model Is Wrong 166 • 8.4 Prioritized Sweeping 168 • 8.5 Expected vs. Sample Updates 172 • 8.6 Trajectory Sampling 174 • 8.7 Real-time Dynamic Programming 177 • 8.8 Planning at Decision Time 180 • 8.9 Heuristic Search 181 • 8.10 Rollout Algorithms 183 • 8.11 Monte Carlo Tree Search 185 • 8.12 Summary of the Chapter 188 • 8.13 Summary of Part I: Dimensions 189
20. 優先度付き⾛査(Prioritized Sweeping) • Dynaの問題点 • すべての以前経験した状態-⾏動ペアの中から⼀様にランダム (uniformly at random)にペアを選んで価値を更新 • 右図の例の場合 • ゴールにつながるペアだけが正の価値、それ以外はゼロ • 価値がゼロのペアを選んでも価値が更新されないので無駄 • →特定のペアに集中して選んだ⽅が効率的 • 優先度付き⾛査 (Prioritized Sweeping) • ペアの価値の変化量の⼤きさ順でキューに挿⼊ • 変化量の⼤きいペアから順に価値を更新 • 詳細は次ページ
21. 優先度付き⾛査 (決定論的環境)
22. 迷路タスクへの優先度付き⾛査の適⽤ • 1回の環境相互作⽤につき5回 のプランニング(n=5) • 優先度付き⾛査が5〜10倍程 度速い
23. ⽬次 • 8 Planning and Learning with Tabular Methods 159 • 8.1 Models and Planning 159 • 8.2 Dyna: Integrated Planning, Acting, and Learning 161 • 8.3 When the Model Is Wrong 166 • 8.4 Prioritized Sweeping 168 • 8.5 Expected vs. Sample Updates 172 • 8.6 Trajectory Sampling 174 • 8.7 Real-time Dynamic Programming 177 • 8.8 Planning at Decision Time 180 • 8.9 Heuristic Search 181 • 8.10 Rollout Algorithms 183 • 8.11 Monte Carlo Tree Search 185 • 8.12 Summary of the Chapter 188 • 8.13 Summary of Part I: Dimensions 189
24. ロールアウトアルゴリズム • 意思決定時プランニング • 新たな状態に出会ってからモデルを使って⾏動を計算 • 現在の状態にフォーカスしてプランニングを⾏い、⾏動を選択 • ロールアウトアルゴリズム • 意思決定時プランニングの⼀種 • モンテカルロ制御(control)(P. 97)を現在の状態から始まるシミュレートされた軌跡 に適⽤ • 与えられた⽅策(ロールアウト⽅策)において、多数のシミュレートされた軌跡を平均 することで⾏動価値を推定 • トレードオフ • より良いロールアウト⽅策はより計算時間が必要 • 解決アプローチ • モンテカルロ試⾏はそれぞれ独⽴なので別々のプロセッサで並⾏実⾏可能 • シミュレートされた軌跡を短く切り詰める • 最良になりえない⾏動を枝刈り
25. ⽬次 • 8 Planning and Learning with Tabular Methods 159 • 8.1 Models and Planning 159 • 8.2 Dyna: Integrated Planning, Acting, and Learning 161 • 8.3 When the Model Is Wrong 166 • 8.4 Prioritized Sweeping 168 • 8.5 Expected vs. Sample Updates 172 • 8.6 Trajectory Sampling 174 • 8.7 Real-time Dynamic Programming 177 • 8.8 Planning at Decision Time 180 • 8.9 Heuristic Search 181 • 8.10 Rollout Algorithms 183 • 8.11 Monte Carlo Tree Search 185 • 8.12 Summary of the Chapter 188 • 8.13 Summary of Part I: Dimensions 189
26. モンテカルロ⽊探索(MCTS) • 近年最も成功した意思決定時プランニングの例 • AlphaGo • ロールアウトアルゴリズムの⼀種 • モンテカルロシミュレーションから得られた価値推定を累積 • より⾼報酬の軌跡を⽬指してシミュレーションを連続して⾏う • 2つの⽅策 • ロールアウト⽅策(rollout policy) • ⼀番単純なものはランダム⽅策 • ツリー⽅策(tree policy) • ε-グリーディやUCB選択ルールなど
27. MCTSのアルゴリズム • 選択(Selection) • ツリー⽅策に従ってリー フノードを選択 • 拡張(Expansion) • リーフノードから辿れる 未探索の⾏動を⼦ノード として追加 • シミュレーション (Simulation) • 選択されたノードから、 ロールアウト⽅策に従っ て完全なエピソードをシ ミュレーション • バックアップ(Backup) • ツリー⽅策でトラバース されたエッジの⾏動価値 を更新 • ロールアウト⽅策で訪問 された部分は⾏動価値を 保存しない
28. ⽬次 • 8 Planning and Learning with Tabular Methods 159 • 8.1 Models and Planning 159 • 8.2 Dyna: Integrated Planning, Acting, and Learning 161 • 8.3 When the Model Is Wrong 166 • 8.4 Prioritized Sweeping 168 • 8.5 Expected vs. Sample Updates 172 • 8.6 Trajectory Sampling 174 • 8.7 Real-time Dynamic Programming 177 • 8.8 Planning at Decision Time 180 • 8.9 Heuristic Search 181 • 8.10 Rollout Algorithms 183 • 8.11 Monte Carlo Tree Search 185 • 8.12 Summary of the Chapter 188 • 8.13 Summary of Part I: Dimensions 189
29. 8章のまとめ • プランニングと学習の密接な関係 • シミュレートされた経験か実際の経験か • 分布モデルとサンプルモデルの違い • プランニングと学習の統合 • プランニング、⾏動、モデル学習 • バックアップの種類: 計算をどこにフォーカスするか • 優先度付き⾛査 • 少数バックアップ (Dyna) • サンプルバックアップ • 軌跡サンプリング: 軌跡に沿ってバックアップ • ヒューリスティックサーチ • モンテカルロ⽊探索: オンライン・逐次的・サンプルベース • バックアップのサイズ • 完全/サンプル • 深く/浅く
30. パートIのまとめ • 全ての⼿法に共通するアイデア • 価値関数の推定 • バックアップ更新 • バックアップ • 狭く/広く (右図横軸) • 浅く/深く (右図縦軸) • 問題の次元 • 予測(prediction) vs 制御(control) • ⾏動価値 vs 状態価値 • on-policy vs off-policy • エピソードタスク vs 連続タスク • その他の次元 • オンライン vs オフライン
31. 参考資料 • Suttonの授業スライド • https://drive.google.com/drive/folders/0B3w765rOKuKAeVZIWmFa ZW1FTW8 • Suttonの授業ビデオ • https://drive.google.com/drive/folders/0B- WvrETGtkesN29sV1g3aXZ1Z0U • Pythonコード • https://github.com/ShangtongZhang/reinforcement-learning-an- introduction/tree/master/chapter08 • 迷路タスクのコードがある