On Monte Carlo Tree Search and Reinforcement Learningを読んだ

出典

 Tom Vodopivec, Spyridon Samothrakis and Branko Ster, "On Monte Carlo Tree Search and Reinforcement Learning," Journal of Artificial Intelligence Research, vol.60, pp.881-936, 2017

概要

 MCTS強化学習を統一的な観点から捉え直し、TD(\lambda)法に基づくMCTSの改良アルゴリズムSarsa-UCT(\lambda)の提案を行った。

新規性

統一的な観点の提示

 MCTSを、状態空間の一部分をテーブル形式で表現する(強化学習と同じ定式化による)プランニングアルゴリズムとして捉えた。MCTSにおけるルートノードからリーフノードまでを選んでいく選択ステップにおいて、そこの方策がどの状態をテーブルに加えるべきかを制御するものとし、それによってルートの状態に近い状態がテーブルに追加されているという見方を行う。AMAFやRAVEもある特徴に基づいて複数の状態を同一視する手法として、このような状態空間の表現という観点からまとめられるとした。

Sarsa-UCT(\lambda)

 MCTSにおけるバックアップ部分が強化学習におけるパラメータ更新部分と同じであるという観点から、TD(\lambda)のように遠くの影響を減衰させる手法を提案した。

 核心部分は論文中アルゴリズム1のバックアップ。通常MCTSではプレイアウトで得た報酬を平均していく手法を取るが、MCTSにおけるバックアップでもTD(\lambda)のような更新則を使うということ。

f:id:tokumini:20190315111321p:plain

実験

二人ゲーム

 5目並べやHexにより実験。特にシミュレーション回数が少ないときに既存UCTアルゴリズムより良い性能を示す。シミュレーション回数が多くなってもUCTに劣るということはなく、簡単なゲームではどちらも最適となって差が出なくなるが、難しいゲームであれば差が出やすい。

f:id:tokumini:20190315121748p:plain

 トイゲームとビデオゲームについては割愛。これらについても提案手法が良い結果を出している。

今後の課題等

 TD(\lambda)(適格度トレース)一般の問題として\lambdaの値は実験的に確かめるしかない。更新ステップ幅(ほぼ学習率と同等なもの)も含めて、パラメータチューニングは強化学習の知見を応用できるところもあるはず。

 また逆に探索の知見を強化学習の方に活かす方法として、環境モデルの学習もできれば強化学習中にこういった探索を組み込むことも可能であるはず。

読んでの所感

 強化学習とゲーム木探索がかなり近いところにあるというのは常々感じていて、それを見事に指摘してくれたと感じた。特に探索は状態空間の一部分だけ表形式の強化学習をやっているという主張はかなり興味深い見方だと思う。参考文献もかなり多く、この論文に載っているものを丹念に追えば近年のMCTS関係の様子はかなり把握できそう。

 4.7節のなぜ\lambda \lt 1が良いかという説明も面白かった。AlphaZeroの棋譜などからMCTSだと有利な終盤で緩い手を指しやすいなどと言われることがあるけれど、それは勝ちであれば遠さを考慮せず価値が同じように足されるからという面もあるのかもしれない。tanh関数を使うので1.0に近い値が区別しにくいという原因の方が大きいかもしれないが。

 Sarsa-UCT(\lambda)に関しては、いろいろと似たような手法は研究されているようなのでどこまではっきりと新規性と言えるのかは少し微妙なところなのかもしれない。しかしシンプルで納得感の強い記述がなされていると思う。特にAlphaZeroのようにプレイアウトを行わないMCTSにおいては特に有効なのではないかと感じる。

 コンピュータ将棋に応用することを考えると、やはりプレイアウトの有無が大きく関わってきそうだ。基本的に将棋においてプレイアウトは有効ではないと思われているようだし、自分も(特に確かめたわけではないが)そう思っている。提案された手法の実装自体は簡単であり、途中の報酬はなく、割引率を1、プレイアウトもなしとすると

void backup(const std::vector<int32_t>& nodes) {
    double delta_sum = 0.0;
    double V_next = 0.0;
    for (int32_t i = nodes.size() - 1; i >= 0; i--) {
        double V_curr = table[nodes[i]].V;
        double delta = V_next - V_curr;
        delta_sum = lambda * delta_sum + delta;
        table[nodes[i]].n++;
        table[nodes[i]].V += alpha * delta_sum;
        V_next = -V_curr;
    }
}

 くらいのものになるはず。しかし手元で少し改造してやってみたところ通常のMCTSに対して勝率10%ほどになってしまった。いくらなんでもここまで悪くなるとは思えず何かしらのバグが残っているのだと思う。今までの平均を用いる方法とは少し実装を変えるところがあるので検証し直したい。再現できたという人がいれば教えていただけるとありがたいです。