モデルベース強化学習の復習とMuZeroの解説

モデルベース強化学習の復習とMuZeroの解説

強化学習コロキウム
2020-03-18
太⽥ 晋

Transcript

1. モデルベース強化学習の復習と MuZeroの解説 2020/3/18 太⽥ 晋
2. ⽬次 • MuZeroの特徴 • 強化学習 • バンディット問題 • nステップTD学習 • モデルベース強化学習 • MuZero • 全体像 • ⽅法 • 結果 • 今後の課題 • まとめ
3. MuZeroの特徴 • モデルベース強化学習 • 従来: 囲碁, 将棋, チェス(ゼロサムゲーム)に おいてSOTA • 今回: ビデオゲーム(Atari)においてもSOTA • ⽐較的シンプル • 教科書に書かれている⼿法の組み合わせ • スケーラブル • 探索と学習は別スレッドで実⾏可能 • 探索は⼤量に並列実⾏可能 https://storage.googleapis.com/deepmind-media/research/muzero_poster_neurips_2019.pdf
4. 強化学習 • 強化学習 • 環境との直接的な相互作⽤から学習 • 4要素: ⽅策・報酬・価値関数・(環境のモデル) • マルコフ決定過程によって定式化 • エージェント・環境との相互作⽤を状態・⾏動・報酬によって記述 • 価値関数 • 状態の価値とは、将来得られると予想される報酬の合計 • ⽅策空間の効率的な探索において重要 • 探索と利⽤のジレンマ • 探索を重視すると計算時間増⼤ or 収束しない • 利⽤を重視すると局所最適解
5. バンディット問題 • 例: 10個のスロットマシン • 報酬の分布が不明 • 状態は⾏動によって変化しない • 最適解 • ⾏動3を取り続けると報酬期待値 1.55に収束 • ⽅策 • 序盤は満遍なく • ある程度分布がわかれば集中 • 探索と利⽤のバランスをどうと るか？
6. UCB1 (Upper Confidence Bound 1) • バンディット問題の解法 の1つ • 平均報酬1.55が最適解 • 序盤は探索(第2項)が⼤ • 次第に探索が減っていく • MuZeroでは • ある局⾯において、次の⼀ ⼿を決める際にUCBの改良 版(pUCT)を利⽤ 利⽤ 探索
7. nステップTD学習 • temporal-difference(TD)学習 • 連続する時間(例えばtとt+1)の違 いに基づいて学習 • 価値VをターゲットG (⾚線部分)に 近づける • nステップTD学習 • nステップリターンをターゲット としてTD学習
8. モデルベースとモデルフリー • モデルベース強化学習 • ⼆⼈零和有限確定完全情報ゲーム(ゼロサムゲーム)で成功 • 囲碁・将棋・チェス等 • 例えばポーカーは含まれない(完全情報ではない) • AlphaZero, MuZero等 • モデルフリー強化学習 • Atari等のビデオゲームで成功 • DQN, Ape-X, R2D2等 • 今回MuZeroがビデオゲーム(Atari)でもSOTA
9. ゼロサムゲームとビデオゲームの違い • ⼆⼈零和有限確定完全情報ゲーム • ビデオゲーム • ⼆⼈ではない・零和ではない • Atariのすべてのゲームは1⼈⽤ • 有限ではない • エピソード終端が存在するとは限らない • 報酬がエピソード末だけに得られるとは限らない • 確定ではない • ランダム性がある • 完全情報ではない • 全ての情報が観測できるわけではない • 観測が部分的→POMDP?
10. モデルとプランニング • モデル • 状態と⾏動が与えられた時に、次の状態と報酬を予測 • S, A → S’, R • プランニング • モデルを⼊⼒ • シミュレートされた経験を出⼒ • 価値関数を更新 • ⽅策を出⼒
11. モデルベース強化学習 • 価値関数/⽅策の改善 • 直接強化学習 • シンプル • モデル設計のバイアスを受けない • 間接強化学習(モデル経由) • 限られた経験を最⼤限利⽤ • 少数の環境との相互作⽤から、より 良い⽅策を⾒つけることが出来る
12. モンテカルロ⽊探索(MCTS) • 選択(Selection) • ツリー⽅策(εグリー ディ等)に従ってリーフ ノードを選択 • 拡張(Expansion) • リーフノードから辿れる 未探索の⾏動を⼦ノード として追加 • シミュレーション (Simulation) • 選択されたノードから、 ロールアウト⽅策に従っ て完全なエピソードをシ ミュレーション • バックアップ(Backup) • ツリー⽅策でトラバース されたエッジの⾏動価値 を更新 • ロールアウト⽅策で訪問 された部分は⾏動価値を 保存しない
13. AlphaGoからMuZeroへの発展 • AlphaGo (2016年) • 囲碁 • MCTS • セルフプレイ • プロ棋⼠の棋譜データベース • AlphaGo Zero (2017年10⽉) • 囲碁 • MCTS • セルフプレイ • ⼈間の知識なし • プロ棋⼠の棋譜データベースを使わない • AlphaZero (2017年12⽉) • チェス, 将棋, 囲碁 • MCTS • セルフプレイ • 囲碁特有の学習⽅法を除外 • 盤⾯の回転による学習データ⽔増し • 引き分けの追加 • MuZero (2019年) • チェス, 将棋, 囲碁, ビデオゲーム(Atari) • MCTS • セルフプレイ • ゲームのルールの知識なし • 報酬のみで学習 • 報酬・価値のスケーリング • エピソード途中の報酬
14. MuZero全体像 • リプレイバッファと シェアドストレージ • セルフプレイと学習 器は別スレッド • セルフプレイ • プランニング • ⾏動選択 • 学習器 • NNをnステップTDで 学習 https://github.com/werner-duvaud/muzero-general/wiki/How-MuZero-works
15. ⽅法 • データベース • リプレイバッファ(エピソード毎の観測・⾏動・報酬・⽅策・価値のシーケンス) • シェアドストレージ(表現・ダイナミクス・予測の3つのニューラルネットワークの重 み)を世代毎に保存 • プランニング • シェアドストレージからNNの重みを読み込み • MCTSで探索(シミュレーション) • ある局⾯から始まるツリーの各ノードの価値を計算 • 次の1⼿を決めるバンディット問題(UCBの改良版pUCTで解く) • ⾏動選択 • プランニングで得られた⽅策をもとにボルツマン分布でサンプリングして⾏動を決 定 • ⾏動を実環境に作⽤させ観測と報酬を得る • エピソード末で軌跡をリプレイバッファに保存 • 学習 • リプレイバッファからをエピソードを1つ読み込み • n-ステップTDで学習 • NNの重みをシェアドストレージに保存
16. プランニング(MCTS) • 3つのニューラルネットワーク • 表現学習・環境モデル・Actor-Criticの 組み合わせ https://storage.googleapis.com/deepmind-media/research/muzero_poster_neurips_2019.pdf
17. ⾏動選択 • プランニングで得られた⽅策をもとにボルツマン分布でサンプリン グして⾏動を決定 • ボルツマン分布でランダム性を加え探索を⾏う • 徐々に温度パラメータを減らしてランダム性を減らす • ⾏動を実環境に作⽤させ観測と報酬を得る • エピソード末で軌跡をリプレイバッファに保存
18. 学習 • リプレイバッファか らをエピソードを1つ 読み込み • n-ステップTDで学習 (次ページ) • NNの重みをシェアド ストレージに保存 ⽅策 価値 報酬
19. MuZeroにおけるnステップTD学習 • 学習⼿順 • リプレイバッファから優先順位に基づいて1つのエピ ソードを取り出す • そのエピソード中の任意の位置を決める • その位置から5ステップ(unrollステップ)分以下を実⾏ • nステップリターンを計算(unrollステップとは違うことに注 意) • nステップリターンをターゲットとしてTD学習 • ゼロサムゲームの場合 • エピソード終端が存在 • 例えば囲碁は最⼤722ステップでそれを超えたら引き分け • 報酬はエピソード末のみ(勝ち1・負け-1・引き分け0) • n=∞ (つまりモンテカルロリターン) • γ=1 • ビデオゲームの場合 • エピソード⻑は任意だが最⼤27000ステップ(30分に相 当)に制限 • 報酬がエピソード途中に得られる可能性がある • n=10 • γ=0.997
20. 結果 • 2つ評価においてSOTA を達成 • ⼤量のデータ • モデルフリー強化学習 ⼿法より良い • 少量のデータ • サンプル効率がよい
21. 結果の詳細 • モデルフリーより⼤幅に劣るゲーム(⾚) • montezuma revenge • qbert • solaris • venture • ⼈間より⼤幅に劣るゲーム(⻘) • pitfall • skiing
22. 今後の課題 • 環境のモデル(ダイナミクスのNN)が決定論的 • 確率的な環境(例えばポーカー)に対する拡張が必要 • ⾏動が離散的 • MCTSを連続⾏動空間に適⽤するいくつかの⼿法がある • マルチエージェントへの対応 • 例えば複数⼈対戦のビデオゲーム
23. まとめ • モデルベース強化学習がビデオゲームにおいてSOTAを達成 • サンプル効率がよい • ⼆⼈零和有限確定完全情報ゲームとビデオゲームを同⼀⼿法で 解くことが可能 • 表現・環境のモデル・予測を同時に学習可能
24. 参考⽂献 • MuZero • Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model • https://deepmind.com/research/publications/Mastering-Atari-Go-Chess- and-Shogi-by-Planning-with-a-Learned-Model • muzero-general • https://github.com/werner-duvaud/muzero-general • Reinforcement Learning: An Introduction • http://incompleteideas.net/book/the-book.html