最難問ゲーム「Montezuma逆襲」でぶちぎりの得点を出したUberの論文を読む
下図の様にDeepMindのDQN[1]でAtariゲームで最難問と云われる「Montezuma逆襲」でぶちぎりの得点を弾き出したUberの論文を読んでみる。(Uberはネットでのタクシー手配提供会社)
この論文は下図の様に隔絶した得点を出したことが2018年末報告されており、その論文がやっと年初に出たので読んでみる。但し論文にはゲーム[Pitfall]の実験成果も報告されているが省略する。
[1901.10995] Go-Explore: a New Approach for Hard-Exploration Problems
このUberのモデル(以下Go-exp)は人間のゲーム知識を入れた得点(67万点)が赤枠で囲ったもので、青は人間のゲーム知識を入れない得点(4万4千点)である。
上図の下辺を拡大した下図(スケールに注意)に示す様にゲームの知識を入れないモデルの比較でも隔絶した得点をたたき出していることがわかる。緑丸のRNDは2018年に出された好奇心で探索する画期的な「Random Network Distillation」[2]モデルで、これも相当凌駕している。
この様にどうして隔絶した得点を出せたかについて論文を読んでみる。
・モデル
上述した様にRNDは内発的動機IM(intrinsic motivation)をモチーフにして探索するが、Go-expでも前方探索に[detachment]としてIM使い、後方探索として容易な戻り[derailment]が出来る方式を採用している。
Go-expはよく練られた２つのパイプライン(phase1 phase2)で構成されている。
phase1は要点(cell)の設定と要点間ルートの探索と保存を行い、phase2は保存された最適なルートを逆に辿って最大報酬が得られる様に強化学習[3](PPOモデル[4])をしている。
phase2とphase1に分て次の様なアイデアで高得点を実現している。
<phase2 >
①以前から複雑なミッション(例えば鍵のある部屋の探索等)ではゴールから逆向きに
学習すればよいと云われていたが、phase2はゴールに達した保存されたルートから逆に辿って実現している。
<phase1>
①phase1では探索がし易い様に、画像の次元を落として灰色の粗い画像上で行っている。 
②phase1の要点(cell)とは画像の各点の重要度が高い所を意味し、
この設定は次の新規の重要な要点が発見しやすい所に高い要点の重みを設定している。
即ち全く訪れていない場所の近くや重要な要点の近くに高い重みを設定している。
(これについてはAppendex5を参照 論文中で唯一式が出てくる所)
③要点から別の要点を探索しており、要点間では複数のルートが生成されるが、
ルート長やその間の報酬を評価して、優良なルートに入替えている。
当然Goalに達すると探索は終了する。
驚くべき事に要点設定とルート探索では全く深層学習を使っていないと言っている。
④phase1での要点間ルートの保存によって、エージェントが簡単に前の要点に戻れる
工夫がなされている。即ち無駄な後戻り探索を抑止している。
⑤phase1の要点設定では、人間の知識を入れた要点の重みを設定することができる。
（例えばエージェントが鍵のある部屋に入った場所の要点の価値を高くする）
この効果で66万点を実現しているが、この設定をしなくても隔絶した得点を実現している。
・感想
論文ではphase1はルート生成で、phase2はこのルートを逆向きに強化学習により統計的なイベントに対して頑健(robust)なモデルにしていると述べている。例えば「Montezumaの逆襲」ではランダムに現れる敵の攻撃を回避する必要がある。
Go-expの最大の成果は以下と考えられる。
①phase2でGoalからの逆向きの探査で無駄な探索を排除したこと
②phase1で場所の価値を要点として設定でき、要点間を最適なルートで繋いだこと
③要点間は簡単に戻れることにより無駄な探索を省いたこと
これは木構造探索で末端で失敗すれば、元に戻って別の枝に移れるイメージであろう。
しかしGo-expの様に要点間連結と逆向きの強化学習は、ゴールが見えている２次元迷路探索には効率的だが、RNDの様な内発的動機の方が人間の志向に近いと思われ、ゴールが定かでない課題が一般的なので、内発動機の方が様々な分野に応用できそうな気がする。
[1] [1312.5602] Playing Atari with Deep Reinforcement Learning
[2][1810.12894] Exploration by Random Network Distillation
[3][1812.03381] Learning Montezuma's Revenge from a Single Demonstration
