まず戻ってから探索せよ
Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O. Stanley & Jeff Clune
Uber社からのNature論文．新しい種類の強化学習アルゴリズムGo-exploreを提案し，Atariで最難とされる「Montezuma逆襲」や「Pitfall」を人間のプロレベルより桁違いのスコアをたたき出す性能が得られた．これらのタスクのように報酬がスパースなタスクは一般に学習が難しく，網羅的な探索が重要となる．このモデルは盤面の要点間をつなぐ効率的なパスを明示的に記憶したうえで探索を行うため，効率よく探索が可能となる．2018年の時点でpreprintは出ていて話題になっていたが，ようやくNatureにてpublish．
https://arxiv.org/abs/1901.10995
手法
探索phase
入力画像を低次元化し要点（cell）を設定．要点は盤面の重要さ（ゴールに近いなど）に加え，新規性の高い場所を重みづけて設定される（前方探索）．要点間をつなぐ経路を探索し，最も効率の良いものは明示的に保存される．そして次の探索では有望な状態に戻ってから探索が行われるので，無駄な探索が少ない（後方探索）．前方探索は内発的動機/好奇心と呼ばれる分野でよく研究されているので（https://arxiv.org/abs/1810.12894）後方探索の部分が新規性となる．
ロバスト化phase
ゴールから逆算して近い要点への経路をPPOを用いて学習する．PPOもゴールからの逆算も実は過去に研究されている．
逆算（正確にはゴールによる条件付け）：https://papers.nips.cc/paper/2019/hash/5c48ff18e0a47baaf81d8b8ea51eec92-Abstract.html
PPO：https://arxiv.org/abs/1707.06347
結果
横軸に各種アルゴリズムが開発された年，縦軸に「Montezumaの逆襲」スコアを示す．
https://gyazo.com/6930ccfc28c6b8fe819f2a1186d54694
これまでの主要なアルゴリズムでは人間の平均に到達するのも難しく，RNDなど好奇心を加え始めたあたりからようやく人間レベルに到達．一方今回のGo-Ecplore（赤枠）の登場で他のアルゴリズムを圧倒し人間プレイヤーのプロを超えるレベルに到達し，ドメイン知識（オレンジ色の点．例えば鍵のある部屋という場所の要点に対して高い価値を設定する）を加えると人間の世界記録よりも桁違いに高いスコアを達成．
感想
「有望な状態に戻る」という点を加えただけで，探索効率が上がり，桁違いに性能が上がっていて驚いた．しかもこの点には深層学習は使われていない．発想次第でアルゴリズムの性能が桁違いに変わる可能性があるというのは夢があると思った．
また，ゴールから遡ってサブゴール（要点）までの経路を計算するという点，新奇な箇所に訪れようとする点は脳にも備わっているかもしれないとも思うので，生物の戦略とも比較して考えていきたい．