MCTSnetの論文を読む - TadaoYamaokaの開発日記

DeepMindからarXivに投稿された論文「Learning to Search with MCTSnets」についてです。

Redditの投稿が簡潔に要約しています。
Learning to Search with MCTSnets : cbaduk

AlphaGo ZeroのPUCTアルゴリズムは、PolicyとValueと訪問回数を使って、固定の計算式で算出した値から手を選択していますが、埋め込み、シミュレーション、バックアップ、および読み出しという4つのニューラルネットワークを使用してアクションを選択します。

埋め込みネットワーク $\epsilon$ は、状態sからノードの訪問回数の統計情報 $h^m$ を埋め込みベクトルとして出力します。埋め込みベクトルとは、ある次元で構成される情報の各次元の成分を異なる次元のベクトルとして分散表現したものです。（Word2Vecで単語の埋め込みベクトルとか行うやつです。）

シミュレーションネットワークπは、MCTSのシミュレーションにおいて、統計情報 $h^m$ を入力として各ノードでアクションを選択する際の確率分布を出力します。

バックアップネットワーク $\beta$ は、葉ノードからルートノードに向けてシミュレーションを行ったノードを逆方向にたどって、各ノードで新しい統計情報 $h^{m+1}$ を出力します。入力は、自ノードの現在の統計情報hと、一つ下のノードの統計情報hと報酬rと、選択したアクションです。

M回シミュレーションを行い、各ノードで統計情報を更新します。

最終的に、ルートノードでは、読みだしネットワーク $\rho$ を使ってアクションを選択します。
読みだしネットワーク $\rho$ は、ルートのバックアップネットワークの出力を入力として、MLPでアクションを出力します。

この図がうまく表現しています。
f:id:TadaoYamaoka:20180301213834p:plain

学習方法

MCTSnetの学習方法は、MCTSで長時間思考した教師ありデータを使用して、MCTSnetの出力の対数尤度を最小化するように学習します。（論文の3.6の内容は理解できませんでした。）

結果

実験には、「倉庫番」というゲームが使われています。
MCTSnetを使うと25シミュレーションで、MCTSの500シミュレーションと同等の成功率になっています。
f:id:TadaoYamaoka:20180301223605p:plain

感想

PUCTの代わりにニューラルネットワークを使うことで少ないシミュレーションで高い精度を上げています。
計算コストはバックアップのフェーズでニューラルネットワークの計算が増えるのでPUCTよりも高くなります。
計算コストに見合う精度向上なのかは論文では特に触れられていませんでした。
学習方法については、正直難しくて理解できませんでした。。。