1. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
DeNA Co., Ltd.
システム本部
AI システム部 AI 研究開発第三グループ
甲野 佑
Reinforcement Learning @ NeurIPS2018
2. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
甲野 佑
所属 : 株式会社ディー?エヌ?エー AI システム部 AI 研究開発第三グループ
??? 東京電機?学 理?学部 講師 (兼業)
研究 : 強化学習,”逆転転オセロニア” への応?
興味:神経科学,認知科学に基づいた階層型 RL アーキテクチャ
?2017年3?: ?学で強化学習の研究してきました
2017年4??: 強化学習を応?したゲーム AI の研究開発をしています
2018年4??: 東京電機?学にて??知能についての授業をしています
??紹介
2
3. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
3
RL at NIPS
サンプル効率性や探索などの基礎寄り研究が相変わらず多い
??でマルチエージェントやメタ学習など応?寄りの研究も同じくらい
Zhang, J. A Comprehensive Summary and Categorization on Reinforcement Learning Papers from NeurIPS 2018.
参照 URL : https://medium.com/@jianzhang_23841/neurips-2018-paper-summary-and-categorization-on-
reinforcement-learning-ae266bed7ca5
4. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
4
RL の問題分類
サンプル効率性
過去のサンプルの再利?
探索促進
最適経路の発?可能性の担保
環境の制約
環境が MDP を満たす必要
近似関数の保証
価値関数の関数近似の問題
実?上はリアリティーギャップやマルチエージェントが
問題にされるが,それらも上記の問題の複合と捉えられる
5. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
5
RL 研究の傾向
サンプル効率化
重要度サンプリング(IS)やソフト最適化による on-policy に対する経験再?の応?
O?-policy 補正の適?による学習の安定性の向上,基礎研究寄り
2017 年
探索促進
?いサンプル効率に基づいた強化学習の本丸の問題へのアプローチ
過去の?度なアルゴリズムへの o?-policy 技術の応?
2018 年
?貫するのは強化学習の反復回数の減少が?的
8. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
8
気になった RL の研究 at NIPS
■ 新しい形式での探索の効率化
- Go-Explore - A new type of algorithm for hard-exploration problems - [presentation]
? リスタートを重視した新しい環境の探索?法
- Data-E?cient Hierarchical Reinforcement Learning
? サンプル効率化して階層化した意思決定で探索を効率化
■ さらなるサンプル効率化
- Policy Optimization via Importance Sampling (割愛)
? Action level, (複数の) policy level で IS を使?して補正して最適化
- Breaking the Curse of Horizon: In?nite-Horizon O?-Policy Estimation?(割愛)
? 超?期な軌跡にIS を適?すると?分散になるため定常状態訪問分布を推定してに直接 IS 適?
■ モデルベース RL の究極の夢
- Recurrent World Models Facilitate Policy Evolution (割愛)
? 教師なし学習による環境表現(モデル)の獲得とその上での RL
■ ドメイン知識なし部分観測下 (マルチエージェント) の学習
- Actor-Critic Policy Optimization in Partially Observable Multiagent Environments (割愛)
? ゼロサムゲームに対するモデルフリーでの強化学習
■ DRL の根本的な問題
- Non-delusional Q-learning and value iteration [Best paper]
? 価値関数の近似で最適化を阻害する delusional bias (妄想バイアス) の補正
9. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
9
気になった RL の研究 at NIPS
■ 新しい形式での探索の効率化
- Go-Explore - A new type of algorithm for hard-exploration problems - [presentation]
? リスタートを重視した新しい環境の探索?法
- Data-E?cient Hierarchical Reinforcement Learning
? サンプル効率化して階層化した意思決定で探索を効率化
■ さらなるサンプル効率化
- Policy Optimization via Importance Sampling (割愛)
? Action level, (複数の) policy level で IS を使?して補正して最適化
- Breaking the Curse of Horizon: In?nite-Horizon O?-Policy Estimation?(割愛)
? 超?期な軌跡にIS を適?すると?分散になるため定常状態訪問分布を推定してに直接 IS 適?
■ モデルベース RL の究極の夢
- Recurrent World Models Facilitate Policy Evolution (割愛)
? 教師なし学習による環境表現(モデル)の獲得とその上での RL
■ ドメイン知識なし部分観測下 (マルチエージェント) の学習
- Actor-Critic Policy Optimization in Partially Observable Multiagent Environments (割愛)
? ゼロサムゲームに対するモデルフリーでの強化学習
■ DRL の根本的な問題
- Non-delusional Q-learning and value iteration [Best paper]
? 価値関数の近似で最適化を阻害する delusional bias (妄想バイアス) の補正
10. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
10
Go-Explore
- A new type of algorithm for hard-exploration problems -
Ecoffet, A., Huizinga, J., Lehman, J., Stanley, K. O., Clune, J. Go-Explore A new type of algorithm for hard-exploration problems.
Proceedings of the 32st Conference on Neural Information Processing Systems (NeurIPS 2018) Deep Reinforcement Learning Workshop,
2018.
参照 URL : http://www.cs.uwyo.edu/~je?clune/share/2018_12_07_NeurIPS_DeepRLWorkshop_Go_Explore.pdf
11. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
11
新しい探索?法:Go Explore
悪名?い “モンテズマの復讐” に圧倒的な成績
12. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
12
新しい探索?法:Go Explore
?間の知識(抽象化の?法)を使?しないフェアな評価はこちら
13. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
13
探索の罠:?つの迷宮問題
報酬源まで「遠い」「到達可能性が低く」場合,?前で飽きる=好奇?の枯渇
14. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
14
前?ボーナス?後?報酬
探索が必要な意思決定課題,?動時に報酬期待値を参照して?動する
UCB 系:Q 値+探索ボーナス
好奇?系:Q 値そのものを歪める(探索報酬を含めた価値関数を ”学習”)
?- Deep RL はたいてい探索報酬として与えられるが使われる
未知度合いを上乗せ
真の Q 値は不変
A B< A B>
UCB系:時間変異
探索報酬ごと学習
真の Q 値が?定常
A B< A B>
好奇?系:時間変異
15. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
15
前?ボーナス?後?報酬
A B< A B>
UCB系:初回訪問?
A B< A B>
好奇?系:初回訪問?
初期訪問時から有効
初期訪問時は無影響
影響は次の訪問から
?動ごとに訪問が必要
好奇?系による探索報酬は「初回訪問」時に与えられる
報酬に対する価値の学習がバックアップである以上
探索意欲は探索したい状態??動に「再訪問」時に発揮する
そのタイムラグが「?つの迷宮」問題をもたらす原因の?つ
迷路の奥になるほど広がっていくなら前?ボーナスでも解決できない
16. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
16
とにかくすごく探索する:Go Explore
すごくシンプルに?うと???
- (有望そうな) 過去訪れた好きな場所からリスタート
- そこから?定回数ランダム探索して?んな場所を覚えていく!
? いつでも好きな場所からリスタートできたら流?にチート
? リスタート位置までの経路を覚えてフェアなリスタートを
失敗成功
ワープ
やり直し
20. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
20
Go Explore の問題
POMDP の本質的な解決にはなっていない:
より困難な POMDP (セル単位などで
は正しく分別できない状態) には
対処できない
状態の抽象化:
複数のセーブポイントへの?策を覚えて
おける分,課題によっては?策数が膨?
になってしまう
また,セル単位の抽象化が正しいか不明
状態 b ?動2状態 a?動 1
観測状態?
良い軌跡の評価:
頑健な経路を学習するフェーズにおいて,環境や?策,収益の確率性へ
の対策 (モンテズマの逆襲は環境,収益は決定論的)
状態の同?視を防ぐため正しく状態分割
21. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
21
Go Explore の今後の発展
リスタートからのランダム探索の部分に既存 RNN + 探索促進アルゴリ
ズムを導?
- 探索の仕?をランダムよりは賢くする (より複雑な環境を?据えて)
- RNN で時系列を圧縮して POMDP に対処
リスタート?策に確率的な?策の学習を採?
- sticky actions による対処では現実のランダム性には不?分
HER などのゴール志向な?策の保存の仕?
- 保存?策数の爆発の抑制
状態の近似にセル区分ではなく VAE などの潜在空間を利?したい
- どちらにせよ潜在空間を離散化しなければならないと思われる
が????
- あとで軽く触れる world model なんかが正に
22. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
22
通常 RL の拡張アルゴリズム
Universal Value Function Approximators (UVFA)
後知恵 (Hindsight, ある種の記憶改竄) による効率改善
→ HER (価値関数), HPG (?策関数として)
最初からゴール状態を定義して学習 ↓
?休?:ゴール志向型の価値関数??策
23. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
23
Go Explore まとめ
反復回数をメモリに押し付けている
- ?並列的な多点観測
- ある意味アルゴリズムの基本
枠組みレベルの新規な探索法が??い
- 状態ごとに保存というとテーブル型強化学習っぽさがある
- 現時点では正確には純粋な強化学習アルゴリズムとは?いにくい
適?範囲はまだまだ狭い
- 確率的なダイナミクスのタスク,状態分割が難しいタスク
状態の近似にセル区分ではなく VAE などの潜在空間を利?したい
- どちらにせよ離散化しなければならないと思われるが????
Go Explore は枠組みそのものの新規性なので
他の最新アルゴリズムとの融合でもっと拡張されうる
24. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
24
Data-E?cient Hierarchical Reinforcement Learning
Nachum, O., Gu, S., Lee, H., Levine, S. Data-efficient hierarchical reinforcement learning. Proceedings of the 32st Conference on Neural
Information Processing Systems (NeurIPS 2018), 2018.
参照 URL : https://papers.nips.cc/paper/7591-data-e?cient-hierarchical-reinforcement-learning.pdf
26. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
26
HRL の利点
?転移学習がしやすい
- 他の課題に共通する下位?策を転移できる
?構造化(?順)された探索
- Go Explore のようにリスタート後の再探索ができる
- 取り返しのつかない?順 (?度?順に失敗すると戻れない) などに強い
崖
← エージェント 報酬 →
崖
← エージェント 報酬 →
↑橋の上で探索せず対岸に着くのは?難
↓対岸についてから再探索が可能
27. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
27
課題
おなじみの Ant (4つ?エージェント) を使った課題
Ant Gather
- 爆弾を避けながら報酬を取得
Ant Maze
- 迷路
Ant Push
- ブロックを正しい?向に押してゴールまでの経路を開く
- 間違った?向に押したらゴールできない
Ant Fall
- ブロックを溝に落としてその上を通ることでゴールに到達
28. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
28
上位?策から下位?策を全て微分可能な
End-to-End ネットワークで学習
状態間の ”相対的なゴール” を上位?策が選択
抽象状態空間に埋め込み
学習が安定しない
類似アーキテクチャ:FeUdal Networks (FuN)
※
※
※ 画像は https://en.wikipedia.org/wiki/Von_Mises-Fisher_distribution
Vezhnevets, A. S., Osindero, S., Schaul, T., Heess, N., Jaderberg, M., Silver, D., and Kavukcuoglu, K. FeUdal Networks for Hierarchical Reinforcement
Learning. ArXiv. Retrieved from http://arxiv.org/abs/1703.01161 , 2017.
29. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
29
HIRO: HIerarchical Reinforcement learning with O?-policy correction
現状態+相対的なゴール=絶対的なゴール座標に対する下位?策の学習
- 近づいたら正の擬似報酬,離れたら負の擬似報酬
? 報酬が常に与えられるため密報酬環境での学習になる
- 動くごとに現状態と絶対ゴールとの相対ゴール距離は再計算
? その場所ごとに相対ゴールが変わるため多様な下位?策を学習
上位?策は課題の?的(環境からの報酬)で学習
- ?定時間ごとに再度ゴールを選択する
学習は TD3 (DDPG の亜種) を使?
30. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
30
効率的な階層型?策の学習:HIRO
1. ゴール状態を埋め込まず,直接的な状態の差分として表現
- End-to-End にゴールを埋め込むと意味のない擬似報酬を下位?策
に与えてしまう (スキルが得られない)
- HIRO はゴールは?つの状態の差分として定義 (相対的なゴール)
? 最終?的にそぐわなくても様々な下位?策が学習される
? 状態に関しては?夫をしている(Ant の位置や四肢の向きに限定)?
31. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
31
効率的な階層型?策の学習:HIRO
O?-policy 補正によるサンプル効率性の向上
- 近年の重要度サンプリングの補正によるサンプル効率化
? 上位,下位?策?にそれぞれ別に Replay bu?er を持つ
? 下位?策は単純に学習されやすくなる
- [問題] 下位?策の変化により上位?策の前提が崩れる
? End-to-End であるがゆえに下位?策が変わってしまう
? 上位?策を学習し直すためやはりサンプル数が多く必要
32. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
32
?休?:On-policy と O?-policy
推定?策
価値を評価したい?策
挙動?策
探索込みの?策
Replay Bu?er
過去の軌跡データ
?致
=
On-policy
学習
推定?策
価値を評価したい?策
挙動?策
探索込みの?策
Replay Bu?er
過去の軌跡データ
不?致
≠
O?-policy
学習
過去の軌跡と現軌跡が不?致に
Max オペレータなので常に?致
34. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
34
効率的な階層型?策の学習:HIRO
上位?策の RB 内のサンプルの中のゴールを書き換える事で安定化
- 格納された下位?策の軌跡を再現しやすいゴールに記憶を書き換え
? 相対的なゴールを中?としたガウス分布からサンプリング
? 過去のゴール,今のゴールとそのサンプルから選択
- 上書きするゴールは以下の指標を最?化するものを選択
? 意味:ゴールを変えた時,どれだけ過去軌跡と?致しているか?
35. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
35
他 HRL アルゴリズムとの?較
まともに学習できたのは HIRO のみ
- 10 M step, 10回の無作為のシードがまずい?
? FuN あたりはシード依存なとこがある
- FuN とちがい埋め込まず?の状態信号を使う利点
? 埋め込みに意味が与えられる前に意味のある?動を学習できる
37. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
37
HIRO まとめ
?較的現実的な階層型強化学習アルゴリズムの登場
- 今まではアイディア?コンセプトレベル
- O?-policy 関係の技術発展の賜物
- RB 内のゴールの再選択という概念が新規的
ゴールの定義はこれで良いか?
- 環境ダイナミクス内の距離に意味があるなら良いが,他の状態観測
の場合は?(主観迷路とか)
- 完全な状態差分を出?するのは不可能だと考えられる
安全性?安定性としてはまだまだ
- RND や post Go-Explore などの極?探索の?が有効かも
時間的なゴールの再選択で良いのか?
- ゴール志向型の?策単位の区切りではない
探索促進とゴールの打ち切り分布の学習に期待
38. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
38
モデルベース DRL の究極の夢:World model
すごくシンプルに?うと???
- 環境のシミュレータをエージェント内部に作成
? VAE と MDN-RNN を使ったのがポイントらしい
- Rollout (未来予測) による探索の促進
- 潜在空間ゆえの?の??特徴の複雑性と付き合わなくて良い
- 次状態予測可能なシミュレータなので POMDP → MDP に補完した潜在空間?
Ha. D., Schmidhuber, J. Recurrent world models facilitate policy evolution. Proceedings of the 32st Conference on Neural Information
Processing Systems (NeurIPS 2018), 2018.
参照 URL : https://papers.nips.cc/paper/7512-recurrent-world-models-facilitate-policy-evolution.pdf
39. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
39
Non-delusional Q-learning and value iteration
Lu, T., Boutilier, C., Schuurmans, D. Non-delusional Q-learning and value-iteration. Proceedings of the 32st Conference on Neural
Information Processing Systems (NeurIPS 2018), 2018.
参照 URL : https://papers.nips.cc/paper/8200-non-delusional-q-learning-and-value-iteration.pdf
41. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
41
?休?:価値関数と類似度
RL における価値関数の関数近似では
似てるものを「似てる」と判定するより
似てそうだけど似て欲しくないものを「似ていない」と
即座に学習する能?が必要
既存の機械学習は「似てる」の「否定」に対する学習感度が低い?
妄想バイアスと関連
Xu, Z., Modayil, J., Hasselt, H., P., Barreto, A., Silver, D., Schaul, T. Natural Value Approximators: Learning when to Trust Past Estimates. Proceedings of
the 31st Conference on Neural Information Processing Systems (NIPS 2017), 2017.
42. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
42
追加概念:Policy-Class
その選択を実現するパラメータ空間の分割
- 複数のパラメータを保存する
- 到達 Q 値ランクで分離
- 実?上は単純なパラメータじゃないと
?い
- 本論?はシンプルな線形関数を想定
43. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
43
Policy-Class Value Iteration
更新対象となる状態にとって?妄想的な情報セットから TD 更新
- 情報セット:制限された?動,Q 値
? 選択された状態?動対(s, a)を含んでいるかを確認して更新
- 制限 (?妄想的な?動) の中で通常通り Value Iteration
44. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
44
Policy-Class Value Iteration
Policy class を更新
更新対象となる状態にとって?妄想的な情報セットから TD 更新
- 情報セット:制限された?動,Q 値
? 選択された状態?動対(s, a)を含んでいるかを確認して更新
- 制限 (?妄想的な?動) の中で通常通り Value Iteration
47. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
47
課題
Start r = 1
r = 2 r = 10
Start r = 1
r = 2 r = 10
状態?動対の特徴量はランダムに初期化
- 最適?動が妄想バイアスによって獲得不可能
- そのような劣悪な特徴量下での最良の?策を獲得可能か?
48. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
48
?較
関数近似を使うと最適解にはどちらにせよ到達しない
- 代わりに妄想バイアスにより実?不能な?動を除去して妥協解にた
どり着く
- Policy class を使わないと妥協解にすら辿りつかない
- Estimate は Oracle が存在する過程で初期状態から検索した数値?
? まだ論?を解釈しきれていない
4×4 5×5
50. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
50
まとめ
?O? policy な補正により Replay Bu?er が使える事で幅が広く
- 旧来のアルゴリズムの修正も?われている
- ?期的な軌跡にも使いたいので定常訪問分布を推定して IS をするほど
?複数の?策を保持することが?般的に
- アンサンブルという意味ではなく,より構造化された形で
? Go Explore も HIRO もゴール志向型?策を学習 (e.g. HER 形式)
- その概念?体は新しくないがテーブル型 RL の良い点を利?している
? 価値関数の関数近似問題(妄想バイアス他)への対処に必要
? 問題点もテーブル型と同じ(メモリが?りない)
?2019 年はより?度なかたちで?盾する探索概念の融合が到来しそう
- 「広い範囲を探索」しつつ「無意味な?動」はしない
- すると MDP 化の DRL では基本やることがなくなる
- いよいよ POMDP (world model 的な補完,マルチエージェント)に?
51. Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
引??献
51
[1] Sutton, R. S. and Barto, A. G. Reinforcement Learning: An Introduction. MIT Press, Cambridge, 1998.
[2] Zhang, J. A Comprehensive Summary and Categorization on Reinforcement Learning Papers from NeurIPS 2018. https://
medium.com/@jianzhang_23841/neurips-2018-paper-summary-and-categorization-on-reinforcement-learning-ae266bed7ca5
[3] Ecoffet, A., Huizinga, J., Lehman, J., Stanley, K. O., Clune, J. Go-Explore A new type of algorithm for hard-exploration
problems. Proceedings of the 32st Conference on Neural Information Processing Systems (NeurIPS 2018) Deep
Reinforcement Learning Workshop, 2018. http://www.cs.uwyo.edu/~jeffclune/share/
2018_12_07_NeurIPS_DeepRLWorkshop_Go_Explore.pdf
[4] Nachum, O., Gu, S., Lee, H., Levine, S. Data-efficient hierarchical reinforcement learning. Proceedings of the 32st
Conference on Neural Information Processing Systems (NeurIPS 2018), 2018.
[5] Vezhnevets, A. S., Osindero, S., Schaul, T., Heess, N., Jaderberg, M., Silver, D., Kavukcuoglu, K. FeUdal Networks for
Hierarchical Reinforcement Learning. ArXiv. Retrieved from http://arxiv.org/abs/1703.01161 , 2017.
[1] Metelli, A. M., Papini, M., Faccio, F., Restelli, M. Policy Optimization via Importance Sampling. Proceedings of the 32st
Conference on Neural Information Processing Systems (NeurIPS 2018), 2018.
[1] Liu, Q., Li, L., Tang, Z., Zhou, D.. Breaking the curse of horizon: Infinite-horizon off-policy estimation. Proceedings of the
32st Conference on Neural Information Processing Systems (NeurIPS 2018), 2018.
[1] Ha. D., Schmidhuber, J. Recurrent world models facilitate policy evolution. Proceedings of the 32st Conference on Neural
Information Processing Systems (NeurIPS 2018), 2018.
[1] Lanctot, M., Srinivasan, S., Zambaldi, V., Perolat, J., Tuyls, K., Munos, R., Bowling, M.. Actor-critic policy optimization in
partially observable multiagent environments. Proceedings of the 32st Conference on Neural Information Processing Systems
(NeurIPS 2018), 2018.
[1] Lu, T., Boutilier, C., Schuurmans, D. Non-delusional Q-learning and value-iteration. Proceedings of the 32st Conference on
Neural Information Processing Systems (NeurIPS 2018), 2018.
[1] Xu, Z., Modayil, J., Hasselt, H., P., Barreto, A., Silver, D., Schaul, T. Natural Value Approximators: Learning when to Trust
Past Estimates. Proceedings of the 31st Conference on Neural Information Processing Systems (NIPS 2017), 2017.