最近木探索について考えていること

 最近、「探索の仕方自体を学習する」手法について興味が出ている。AlphaZeroの手法をニューラルネットワーク + モンテカルロ木探索として分けて見た場合、前者は学習されるが後者は固定的なアルゴリズムとなっているため、ここを学習にすることができればより性能が高まる可能性があるのではないかと感じたためだ。特に静止探索的な概念を踏まえて、「ある局面で探索を打ち切ってよいか」という判断を行うことで、評価が安定しにくい局面などで改善ができるのではないかと思っている。

 探索というものは次の3モジュールによってモデル化できるのではないかと考えている。

f:id:tokumini:20200619133856p:plain
探索のモデル

 たとえばAlphaZeroでは

というように解釈できるのではないかということだ。

 自分の研究を振り返ってみると、B4のときはAlphaZeroにCategorical DQNを混ぜるということをやっていて、これは上の図で言えば評価器の改善を目指したものだった。M1では先週JSAIで発表したように遷移モデルの学習について研究をしていて、これは図の中央にそのまま相当する。というわけでM2で一番上の部分を扱うとすれば統一的に解釈できるのかもしれない。まぁそのために無理やり捻り出した感もあるモデルなのだが。

 探索マネージャの学習について、知っている限りで一番近そうだと思っている論文は以下の「Learning model-based planning from scratch」というDeepMindが2017年に出したもの。(僕DeepMindの論文を後追いしているだけの人間では?)

 上の論文で記憶モジュール(LSTM)が使われているように、探索マネージャには記憶(特にワーキングメモリ)が必要であるように思われる。たとえばモンテカルロ木探索では置換表がそれまでの探索結果を記録しており、それを参照することで次に探索するべき局面を決定している。(αβ探索では置換表は絶対に必要なものではないが、再帰関数を使っているループそのものが他の行動の価値を記憶している部分と見なすことができる……?)

 ワーキングメモリとしてLSTMで十分なのか、もっとリッチなもの(Neural Turing Machineとか、それをさらに発展させたらしいDifferentiable Neural Computersとか? ちなみにこのDNCもDeepMindの論文)を使う必要があるのかはよくわからないが、木探索では感覚的には明瞭な記憶が必要な気がするのでLSTMよりは外部メモリを明示的に使う手法の方が良さそうかなと思っている。

 全体として探索自体の学習というのはかなりロマン寄りの研究テーマっぽいのでまともな形(実際にプログラムに組み込んでSOTAが達成できるということ)にはならなさそう。「次に評価するべき局面と行動」をどう指定するのかとか、評価結果をどういう形で取り込むかとか、そもそも木という制約を上手く入れないとまともな学習はできなさそうだとか、課題は多い。

 なにか似た論文の情報や質問等あればコメント欄なり@tokumini_ssなりに教えてもらえるとありがたいです。