狠狠撸

狠狠撸Share a Scribd company logo
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
DeNA	Co.,	Ltd.	
システム本部	
AI	システム部	AI	研究開発第三グループ	
甲野	佑
Reinforcement	Learning	@	NeurIPS2018
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
甲野	佑	
所属	:	株式会社ディー?エヌ?エー	AI	システム部	AI	研究開発第三グループ	
???	東京電機?学	理?学部	講師	(兼業)	
研究	:	強化学習,”逆転転オセロニア”	への応?	
興味:神経科学,認知科学に基づいた階層型	RL	アーキテクチャ	
?2017年3?:	?学で強化学習の研究してきました	
2017年4??:	強化学習を応?したゲーム	AI	の研究開発をしています	
2018年4??:	東京電機?学にて??知能についての授業をしています	
??紹介
2
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
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
4
RL	の問題分類
サンプル効率性	
過去のサンプルの再利?
探索促進	
最適経路の発?可能性の担保
環境の制約	
環境が	MDP	を満たす必要
近似関数の保証	
価値関数の関数近似の問題
実?上はリアリティーギャップやマルチエージェントが	
問題にされるが,それらも上記の問題の複合と捉えられる
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
5
RL	研究の傾向
サンプル効率化	
重要度サンプリング(IS)やソフト最適化による	on-policy	に対する経験再?の応?	
O?-policy	補正の適?による学習の安定性の向上,基礎研究寄り
2017	年
探索促進	
?いサンプル効率に基づいた強化学習の本丸の問題へのアプローチ	
過去の?度なアルゴリズムへの	o?-policy	技術の応?
2018	年
?貫するのは強化学習の反復回数の減少が?的
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
6
RL	と反復
π Rπ?策 ?策の評価	(収益)
?策(?動の選択分布)の評価に基づいて良い?策を探索/最適化する
?策(?動の選択分布)の良さを実際の?動結果から評価する
π’ Rπ?策 ?策の評価	(収益)
全ての	RL	アルゴリズムはこの反復で成り?っている	
実際は反復の役割は複合的で?的は単?ではない
?策の評価をサンプリング
?策の修正
膨?な反復回数
期待値の収束反復 価値の更新 環境の探索× ×=
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
7
探索の?盾
無意味な?動の枝切り探索の促進
?必要性	
- 最適な経路を?つけるためにはあらゆ
る状態に到達できなければならない	
?対抗策	
- 好奇?	
- 未知の状態訪問にボーナス報酬を付与	
- 擬似カウント	
- 試?回数が低い?動,状態を優先する	
- ロールアウト	
- シミュレーションベースで数ステップ
先まで探索して良い経路(の短期的な
?動まで)を実?
?必要性	
- 状態?動空間が広?だと,明らかに無
意味な?動が存在するため,それを抑
制する必要がある	
?対抗策	
- 事前学習と転移	
- 簡単なタスク,要素的なタスクで基礎
的なスキルを獲得	
- 逆強化学習	
- エキスパートの?動?策に寄せる	
- ?動?順の(スキル)構造化	
- ?動表現をコントローラに埋め込む	
- 意思決定の階層化
複雑なタスクであるほど相反する両者を成?させる必要がある	
?動表現の埋め込みは相変わらず?気
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	(妄想バイアス)	の補正
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	(妄想バイアス)	の補正
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
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
11
新しい探索?法:Go	Explore
悪名?い	“モンテズマの復讐”	に圧倒的な成績
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
12
新しい探索?法:Go	Explore
?間の知識(抽象化の?法)を使?しないフェアな評価はこちら
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
13
探索の罠:?つの迷宮問題
報酬源まで「遠い」「到達可能性が低く」場合,?前で飽きる=好奇?の枯渇
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>
好奇?系:時間変異
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
15
前?ボーナス?後?報酬
A B< A B>
UCB系:初回訪問?
A B< A B>
好奇?系:初回訪問?
初期訪問時から有効
初期訪問時は無影響	
影響は次の訪問から	
?動ごとに訪問が必要
好奇?系による探索報酬は「初回訪問」時に与えられる	
報酬に対する価値の学習がバックアップである以上	
探索意欲は探索したい状態??動に「再訪問」時に発揮する	
そのタイムラグが「?つの迷宮」問題をもたらす原因の?つ	
迷路の奥になるほど広がっていくなら前?ボーナスでも解決できない
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
16
とにかくすごく探索する:Go	Explore
すごくシンプルに?うと???	
- (有望そうな)	過去訪れた好きな場所からリスタート	
- そこから?定回数ランダム探索して?んな場所を覚えていく!	
? いつでも好きな場所からリスタートできたら流?にチート	
? リスタート位置までの経路を覚えてフェアなリスタートを
失敗成功
ワープ	
やり直し
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
17
リスタートを重視して様々な経路を覚える
Phase	1	(リスタートとランダム探索):	
1. アーカイブからセーブポイントを選択	(稀なほど優先)	
2. セーブポイントまでのリスタートまでの経路を再?	
3. セーブポイントからランダム探索を?って良い軌跡を格納	(NN	不使?!)	
Phase	2	(模倣学習によるリスタート経路のロバスト化):	
4. 新たなセーブポイントをその到達軌跡で模倣学習	→	?策をアーカイブ化	
更に経路そのものも到達確率の?いもの(再スタートが安定するもの)に寄せる	
セーブポイントの数だけ?策を覚えておく	(多数の?策の可能性を保存)
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
18
セーブポイントの抽象化
エージェントの存在するセル(の実績)で状態を区分	
- セルごとに到達可能なリスタート経路を保存する	
- ?応,この状態の抽象化で酷い	POMDP	は発?しないらしい		
ゲームドメインごとの知識を使うこともある	(微チート)	
- 特徴量:エージェントの座標や鍵の取得数,部屋番号など	
? スコア	約35,000	→	400,000	超
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
19
リスタート経路の模倣学習
Backwards	Imitation	Learning	
- デモで到達箇所から少しずつ時間
的に後ろ倒しにスタートしていく	
? より優れた報酬の?動を?策
として採択していく	
- ?分の到達経路をデモとして利?	
- 特に模倣学習に拘りはないらしい	
“sticky	actions”	
- 実?時のみランダム性を与える	
- ?定確率で?つ前の?動を続ける	
- 環境のランダム性への場当たり的
な対処	
? 模倣学習も完全ではないため	
? ロバスト性への保険
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
20
Go	Explore	の問題
POMDP	の本質的な解決にはなっていない:	
より困難な	POMDP	(セル単位などで	
は正しく分別できない状態)	には	
対処できない
状態の抽象化:	
複数のセーブポイントへの?策を覚えて
おける分,課題によっては?策数が膨?
になってしまう	
また,セル単位の抽象化が正しいか不明
状態	b ?動2状態	a?動	1
観測状態?
良い軌跡の評価:	
頑健な経路を学習するフェーズにおいて,環境や?策,収益の確率性へ
の対策	(モンテズマの逆襲は環境,収益は決定論的)
状態の同?視を防ぐため正しく状態分割
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
21
Go	Explore	の今後の発展
リスタートからのランダム探索の部分に既存	RNN	+	探索促進アルゴリ
ズムを導?	
- 探索の仕?をランダムよりは賢くする	(より複雑な環境を?据えて)	
- RNN	で時系列を圧縮して	POMDP	に対処	
リスタート?策に確率的な?策の学習を採?	
- sticky	actions	による対処では現実のランダム性には不?分	
HER	などのゴール志向な?策の保存の仕?	
- 保存?策数の爆発の抑制	
状態の近似にセル区分ではなく	VAE	などの潜在空間を利?したい	
- どちらにせよ潜在空間を離散化しなければならないと思われる
が????	
- あとで軽く触れる	world	model	なんかが正に
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
22
通常	RL	の拡張アルゴリズム	
Universal	Value	Function	Approximators	(UVFA)	
後知恵	(Hindsight,	ある種の記憶改竄)	による効率改善	
→	HER	(価値関数),	HPG	(?策関数として)
最初からゴール状態を定義して学習	↓
?休?:ゴール志向型の価値関数??策
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
23
Go	Explore	まとめ
反復回数をメモリに押し付けている	
- ?並列的な多点観測	
- ある意味アルゴリズムの基本	
枠組みレベルの新規な探索法が??い	
- 状態ごとに保存というとテーブル型強化学習っぽさがある	
- 現時点では正確には純粋な強化学習アルゴリズムとは?いにくい	
適?範囲はまだまだ狭い	
- 確率的なダイナミクスのタスク,状態分割が難しいタスク	
状態の近似にセル区分ではなく	VAE	などの潜在空間を利?したい	
- どちらにせよ離散化しなければならないと思われるが????	
Go	Explore	は枠組みそのものの新規性なので	
他の最新アルゴリズムとの融合でもっと拡張されうる
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
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
25
HRL	の問題
複数の下位?策を学習するため通常の	RL	よりサンプル数が必要	
- 別課題として事前学習することもあるが	End-to-End	を想定	
下位?策が変わると上位?策の意図する?動が変わり安定しない	
- End-to-End	であるがゆえに下位?策が変わってしまう	
- 上位?策を学習し直すためやはりサンプル数が多く必要	
従来の	HRL	は	on-policy	なので更新ごとに軌跡をサンプリングし直し	
サンプル効率性が?常に悪い
下位?策
物を掴む 移動する物を置く
上位?策	
(物を?的地まで運ぶ)
選択
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
26
HRL	の利点
?転移学習がしやすい	
- 他の課題に共通する下位?策を転移できる	
?構造化(?順)された探索	
- Go	Explore	のようにリスタート後の再探索ができる	
- 取り返しのつかない?順	(?度?順に失敗すると戻れない)	などに強い
崖
←	エージェント 報酬	→
崖
←	エージェント 報酬	→
↑橋の上で探索せず対岸に着くのは?難	
↓対岸についてから再探索が可能
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
27
課題
おなじみの	Ant	(4つ?エージェント)	を使った課題	
Ant	Gather	
- 爆弾を避けながら報酬を取得	
Ant	Maze	
- 迷路	
Ant	Push	
- ブロックを正しい?向に押してゴールまでの経路を開く	
- 間違った?向に押したらゴールできない	
Ant	Fall	
- ブロックを溝に落としてその上を通ることでゴールに到達
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.
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
29
HIRO:	HIerarchical	Reinforcement	learning	with	O?-policy	correction
現状態+相対的なゴール=絶対的なゴール座標に対する下位?策の学習	
- 近づいたら正の擬似報酬,離れたら負の擬似報酬	
? 報酬が常に与えられるため密報酬環境での学習になる	
- 動くごとに現状態と絶対ゴールとの相対ゴール距離は再計算	
? その場所ごとに相対ゴールが変わるため多様な下位?策を学習	
上位?策は課題の?的(環境からの報酬)で学習	
- ?定時間ごとに再度ゴールを選択する	
学習は	TD3	(DDPG	の亜種)	を使?
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
30
効率的な階層型?策の学習:HIRO
1.	ゴール状態を埋め込まず,直接的な状態の差分として表現	
- End-to-End	にゴールを埋め込むと意味のない擬似報酬を下位?策
に与えてしまう	(スキルが得られない)	
- HIRO	はゴールは?つの状態の差分として定義	(相対的なゴール)	
? 最終?的にそぐわなくても様々な下位?策が学習される	
? 状態に関しては?夫をしている(Ant	の位置や四肢の向きに限定)?
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
31
効率的な階層型?策の学習:HIRO
O?-policy	補正によるサンプル効率性の向上	
- 近年の重要度サンプリングの補正によるサンプル効率化	
? 上位,下位?策?にそれぞれ別に	Replay	bu?er	を持つ	
? 下位?策は単純に学習されやすくなる	
- [問題]	下位?策の変化により上位?策の前提が崩れる	
? End-to-End	であるがゆえに下位?策が変わってしまう	
? 上位?策を学習し直すためやはりサンプル数が多く必要
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
32
?休?:On-policy	と	O?-policy
推定?策	
価値を評価したい?策
挙動?策	
探索込みの?策
Replay	Bu?er	
過去の軌跡データ
?致	
=
On-policy
学習
推定?策	
価値を評価したい?策
挙動?策	
探索込みの?策
Replay	Bu?er	
過去の軌跡データ
不?致	
≠
O?-policy
学習
過去の軌跡と現軌跡が不?致に
Max	オペレータなので常に?致
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
33
?休?:On-policy	と	O?-policy
推定?策	
価値を評価したい?策
挙動?策	
探索込みの?策
Replay	Bu?er	
過去の軌跡データ
?致	
=
On-policy
学習
推定?策	
価値を評価したい?策
挙動?策	
探索込みの?策
Replay	Bu?er	
過去の軌跡データ
不?致	
≠
O?-policy
学習
過去の軌跡と現軌跡が不?致に
Max	オペレータなので常に?致
要するに軌跡の?成時点と	
現?策が?致すれば良い	
(確率的に)	
(やや暴論なので鵜呑みは厳禁)
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
34
効率的な階層型?策の学習:HIRO
上位?策の	RB	内のサンプルの中のゴールを書き換える事で安定化	
- 格納された下位?策の軌跡を再現しやすいゴールに記憶を書き換え	
? 相対的なゴールを中?としたガウス分布からサンプリング	
? 過去のゴール,今のゴールとそのサンプルから選択	
- 上書きするゴールは以下の指標を最?化するものを選択	
? 意味:ゴールを変えた時,どれだけ過去軌跡と?致しているか?
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
35
他	HRL	アルゴリズムとの?較
まともに学習できたのは	HIRO	のみ	
- 10	M	step,	10回の無作為のシードがまずい?	
? FuN	あたりはシード依存なとこがある	
- FuN	とちがい埋め込まず?の状態信号を使う利点	
? 埋め込みに意味が与えられる前に意味のある?動を学習できる
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
36
HIRO	のバリエーションとの?較
HIRO	のバリエーション?較	
? ?	End-to-End	に事前に?動学習	
? 下位?策の経験再?時にもゴール再計算をする	
? O?-policy	補正をしない	
? 階層化しない	
- 概ねオリジナル	HIRO	が良い	
? Maze	は	O?-policy	必要ない	
? 事前学習は基本的に	End-to-End	の妨げになる
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
37
HIRO	まとめ
?較的現実的な階層型強化学習アルゴリズムの登場	
- 今まではアイディア?コンセプトレベル	
- O?-policy	関係の技術発展の賜物	
- RB	内のゴールの再選択という概念が新規的	
ゴールの定義はこれで良いか?	
- 環境ダイナミクス内の距離に意味があるなら良いが,他の状態観測
の場合は?(主観迷路とか)	
- 完全な状態差分を出?するのは不可能だと考えられる	
安全性?安定性としてはまだまだ	
- RND	や	post	Go-Explore	などの極?探索の?が有効かも	
時間的なゴールの再選択で良いのか?	
- ゴール志向型の?策単位の区切りではない	
探索促進とゴールの打ち切り分布の学習に期待
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
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
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
40
DRLの根本的な問題:Delusional	bias
最適解
φ(s1, a1) = (0, 1)
φ(s1, a2) = (0.8, 0) φ(s2, a2) = (0.8, 0)
φ(s2, a1) = (0, 0) φ(s4, a1) = (0, 1)
φ(s3, a2) = (?1, 0) φ(s4, a2) = (?1, 0)
φ(s3, a1) = (0, 0)
妥協解???すら取れなくなることも
価値関数を関数近似する	(e.g.	DRL)	する際に発?	
- 特徴量の都合により最適?動内にどんなパラメータでも両?不可能	
? 価値関数的に実?不可能な?動の	buckup	してしまう故に	
? Delusional	bias	(妄想バイアス)	と呼ぶ	
- 多数ニューラルネットネットなら回避できるのでは?	
- (multi	step	でも)	TD	学習だと??依存的な反復が起こり不可避
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.
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
42
追加概念:Policy-Class	
その選択を実現するパラメータ空間の分割	
- 複数のパラメータを保存する	
- 到達	Q	値ランクで分離	
- 実?上は単純なパラメータじゃないと
?い	
- 本論?はシンプルな線形関数を想定
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
43
Policy-Class	Value	Iteration
更新対象となる状態にとって?妄想的な情報セットから	TD	更新	
- 情報セット:制限された?動,Q	値	
? 選択された状態?動対(s, a)を含んでいるかを確認して更新	
- 制限	(?妄想的な?動)	の中で通常通り	Value	Iteration
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
44
Policy-Class	Value	Iteration
Policy	class	を更新
更新対象となる状態にとって?妄想的な情報セットから	TD	更新	
- 情報セット:制限された?動,Q	値	
? 選択された状態?動対(s, a)を含んでいるかを確認して更新	
- 制限	(?妄想的な?動)	の中で通常通り	Value	Iteration
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
45
Policy-Class	Q	Learning
基本的には	PCVI	と同じ	
- 環境モデルがないのでサンプルを使った	TD	更新	
- 情報セット	ConQ	の回帰を?なって近似的に取得する		
? 付録	8	にアルゴリズム記載	
? Q	値が低い分割領域は削除してテーブル数を削減	
推定?策が	Greedy	policy,VC	次元が有限だと多項式次元で解ける	
- どちらにせよ	DNN	での近似には現実的ではない
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
46
Policy-Class	Q	Learning
Policy	class	を更新
基本的には	PCVI	と同じ	
- 環境モデルがないのでサンプルを使った	TD	更新	
- 情報セット	ConQ	の回帰を?なって近似的に取得する		
? 付録	8	にアルゴリズム記載	
? Q	値が低い分割領域は削除してテーブル数を削減	
推定?策が	Greedy	policy,VC	次元が有限だと多項式次元で解ける	
- どちらにせよ	DNN	での近似には現実的ではない
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
47
課題
Start r = 1
r = 2 r = 10
Start r = 1
r = 2 r = 10
状態?動対の特徴量はランダムに初期化	
- 最適?動が妄想バイアスによって獲得不可能	
- そのような劣悪な特徴量下での最良の?策を獲得可能か?
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
48
?較
関数近似を使うと最適解にはどちらにせよ到達しない	
- 代わりに妄想バイアスにより実?不能な?動を除去して妥協解にた
どり着く	
- Policy	class	を使わないと妥協解にすら辿りつかない	
- Estimate	は	Oracle	が存在する過程で初期状態から検索した数値?		
? まだ論?を解釈しきれていない
4×4 5×5
Copyright (C) DeNA Co.,Ltd. All Rights Reserved.
49
PCVI	&	PCQL	まとめ
相互参照的に更新されることによる妥協解にすら?れない問題	
- 価値関数が??参照的な回帰であるがゆえの問題	
- DRL	でも回避不可能(表現次元が広いので直接的には?つけにくい)	
- 綺麗に(致命的に)	ハマったら	DeepRL	でも抜け出せない	
- 従来はハイパラチューニングで回避している?	
?策空間を分割?観測による追加によって参照禁?の?動を内包	
- ?かけ上(特徴量レベルで)起こる更新ループを回避	
DRL	膨?なメモリ必要?計算も?	
- 多項式時間ではとけると書いてある	
- 理論的な問題点の指摘	
Policy	class	の適?範囲は	greedy	な推定?策に限定する	
	DRL	での学習の根幹に関わる議論なので今後の発展に期待
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	的な補完,マルチエージェント)に?
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.

More Related Content

Reinforcement Learning @ NeurIPS2018

  • 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 年 ?貫するのは強化学習の反復回数の減少が?的
  • 6. Copyright (C) DeNA Co.,Ltd. All Rights Reserved. 6 RL と反復 π Rπ?策 ?策の評価 (収益) ?策(?動の選択分布)の評価に基づいて良い?策を探索/最適化する ?策(?動の選択分布)の良さを実際の?動結果から評価する π’ Rπ?策 ?策の評価 (収益) 全ての RL アルゴリズムはこの反復で成り?っている 実際は反復の役割は複合的で?的は単?ではない ?策の評価をサンプリング ?策の修正 膨?な反復回数 期待値の収束反復 価値の更新 環境の探索× ×=
  • 7. Copyright (C) DeNA Co.,Ltd. All Rights Reserved. 7 探索の?盾 無意味な?動の枝切り探索の促進 ?必要性 - 最適な経路を?つけるためにはあらゆ る状態に到達できなければならない ?対抗策 - 好奇? - 未知の状態訪問にボーナス報酬を付与 - 擬似カウント - 試?回数が低い?動,状態を優先する - ロールアウト - シミュレーションベースで数ステップ 先まで探索して良い経路(の短期的な ?動まで)を実? ?必要性 - 状態?動空間が広?だと,明らかに無 意味な?動が存在するため,それを抑 制する必要がある ?対抗策 - 事前学習と転移 - 簡単なタスク,要素的なタスクで基礎 的なスキルを獲得 - 逆強化学習 - エキスパートの?動?策に寄せる - ?動?順の(スキル)構造化 - ?動表現をコントローラに埋め込む - 意思決定の階層化 複雑なタスクであるほど相反する両者を成?させる必要がある ?動表現の埋め込みは相変わらず?気
  • 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 すごくシンプルに?うと??? - (有望そうな) 過去訪れた好きな場所からリスタート - そこから?定回数ランダム探索して?んな場所を覚えていく! ? いつでも好きな場所からリスタートできたら流?にチート ? リスタート位置までの経路を覚えてフェアなリスタートを 失敗成功 ワープ やり直し
  • 17. Copyright (C) DeNA Co.,Ltd. All Rights Reserved. 17 リスタートを重視して様々な経路を覚える Phase 1 (リスタートとランダム探索): 1. アーカイブからセーブポイントを選択 (稀なほど優先) 2. セーブポイントまでのリスタートまでの経路を再? 3. セーブポイントからランダム探索を?って良い軌跡を格納 (NN 不使?!) Phase 2 (模倣学習によるリスタート経路のロバスト化): 4. 新たなセーブポイントをその到達軌跡で模倣学習 → ?策をアーカイブ化 更に経路そのものも到達確率の?いもの(再スタートが安定するもの)に寄せる セーブポイントの数だけ?策を覚えておく (多数の?策の可能性を保存)
  • 18. Copyright (C) DeNA Co.,Ltd. All Rights Reserved. 18 セーブポイントの抽象化 エージェントの存在するセル(の実績)で状態を区分 - セルごとに到達可能なリスタート経路を保存する - ?応,この状態の抽象化で酷い POMDP は発?しないらしい ゲームドメインごとの知識を使うこともある (微チート) - 特徴量:エージェントの座標や鍵の取得数,部屋番号など ? スコア 約35,000 → 400,000 超
  • 19. Copyright (C) DeNA Co.,Ltd. All Rights Reserved. 19 リスタート経路の模倣学習 Backwards Imitation Learning - デモで到達箇所から少しずつ時間 的に後ろ倒しにスタートしていく ? より優れた報酬の?動を?策 として採択していく - ?分の到達経路をデモとして利? - 特に模倣学習に拘りはないらしい “sticky actions” - 実?時のみランダム性を与える - ?定確率で?つ前の?動を続ける - 環境のランダム性への場当たり的 な対処 ? 模倣学習も完全ではないため ? ロバスト性への保険
  • 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
  • 25. Copyright (C) DeNA Co.,Ltd. All Rights Reserved. 25 HRL の問題 複数の下位?策を学習するため通常の RL よりサンプル数が必要 - 別課題として事前学習することもあるが End-to-End を想定 下位?策が変わると上位?策の意図する?動が変わり安定しない - End-to-End であるがゆえに下位?策が変わってしまう - 上位?策を学習し直すためやはりサンプル数が多く必要 従来の HRL は on-policy なので更新ごとに軌跡をサンプリングし直し サンプル効率性が?常に悪い 下位?策 物を掴む 移動する物を置く 上位?策 (物を?的地まで運ぶ) 選択
  • 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 オペレータなので常に?致
  • 33. Copyright (C) DeNA Co.,Ltd. All Rights Reserved. 33 ?休?: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 とちがい埋め込まず?の状態信号を使う利点 ? 埋め込みに意味が与えられる前に意味のある?動を学習できる
  • 36. Copyright (C) DeNA Co.,Ltd. All Rights Reserved. 36 HIRO のバリエーションとの?較 HIRO のバリエーション?較 ? ? End-to-End に事前に?動学習 ? 下位?策の経験再?時にもゴール再計算をする ? O?-policy 補正をしない ? 階層化しない - 概ねオリジナル HIRO が良い ? Maze は O?-policy 必要ない ? 事前学習は基本的に End-to-End の妨げになる
  • 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
  • 40. Copyright (C) DeNA Co.,Ltd. All Rights Reserved. 40 DRLの根本的な問題:Delusional bias 最適解 φ(s1, a1) = (0, 1) φ(s1, a2) = (0.8, 0) φ(s2, a2) = (0.8, 0) φ(s2, a1) = (0, 0) φ(s4, a1) = (0, 1) φ(s3, a2) = (?1, 0) φ(s4, a2) = (?1, 0) φ(s3, a1) = (0, 0) 妥協解???すら取れなくなることも 価値関数を関数近似する (e.g. DRL) する際に発? - 特徴量の都合により最適?動内にどんなパラメータでも両?不可能 ? 価値関数的に実?不可能な?動の buckup してしまう故に ? Delusional bias (妄想バイアス) と呼ぶ - 多数ニューラルネットネットなら回避できるのでは? - (multi step でも) TD 学習だと??依存的な反復が起こり不可避
  • 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
  • 45. Copyright (C) DeNA Co.,Ltd. All Rights Reserved. 45 Policy-Class Q Learning 基本的には PCVI と同じ - 環境モデルがないのでサンプルを使った TD 更新 - 情報セット ConQ の回帰を?なって近似的に取得する ? 付録 8 にアルゴリズム記載 ? Q 値が低い分割領域は削除してテーブル数を削減 推定?策が Greedy policy,VC 次元が有限だと多項式次元で解ける - どちらにせよ DNN での近似には現実的ではない
  • 46. Copyright (C) DeNA Co.,Ltd. All Rights Reserved. 46 Policy-Class Q Learning Policy class を更新 基本的には PCVI と同じ - 環境モデルがないのでサンプルを使った TD 更新 - 情報セット ConQ の回帰を?なって近似的に取得する ? 付録 8 にアルゴリズム記載 ? Q 値が低い分割領域は削除してテーブル数を削減 推定?策が Greedy policy,VC 次元が有限だと多項式次元で解ける - どちらにせよ DNN での近似には現実的ではない
  • 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
  • 49. Copyright (C) DeNA Co.,Ltd. All Rights Reserved. 49 PCVI & PCQL まとめ 相互参照的に更新されることによる妥協解にすら?れない問題 - 価値関数が??参照的な回帰であるがゆえの問題 - DRL でも回避不可能(表現次元が広いので直接的には?つけにくい) - 綺麗に(致命的に) ハマったら DeepRL でも抜け出せない - 従来はハイパラチューニングで回避している? ?策空間を分割?観測による追加によって参照禁?の?動を内包 - ?かけ上(特徴量レベルで)起こる更新ループを回避 DRL 膨?なメモリ必要?計算も? - 多項式時間ではとけると書いてある - 理論的な問題点の指摘 Policy class の適?範囲は greedy な推定?策に限定する DRL での学習の根幹に関わる議論なので今後の発展に期待
  • 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.