モンテカルロ木探索 - yuuk1's Digital Garden

# モンテカルロ木探索 ## 定義モンテカルロ木探索(Monte Carlo tree search、MCTS)は、候補手が多く先読みで全ての手を展開しきれない問題(囲碁など)において、有望な手を優先的に探索しつつ未探索の手も効率的に展開していく探索手法である。現在の状態を「根」とし、行動をとって遷移した状態を「子」とする探索木を展開しながら、各枝(状態 $s$・行動 $a$ の組)に行動価値 $Q(s,a)$・訪問回数 $N(s,a)$・事前確率 $P(s,a)$ を保持し、オンラインで状態価値・行動価値を再評価することで手の有望さを判定する。学習だけで得られる価値推定は不正確であるため、実行時に新しく与えられた盤面で再度先読みし価値を再評価することで、学習済みの価値・方策をそのまま使うよりも強いシステムを実現できる。(Source: [[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 4 深層強化学習]] §4.14) ## UCBによる探索と活用のバランス各節点では、行動価値(有望さ)$Q(s,a)$ と不確実性(まだ十分探索されていないか)$U(s,a)$ の和である UCB(Upper Confidence Bound)と呼ばれる尺度を計算し、UCBが最大の手を選択する: $UCB(s,a) = Q(s,a) + U(s,a), \qquad U(s,a) \propto \frac{P(s,a)}{1+N(s,a)}$ 事前確率 $P(s,a)$ には、次の手を予測するモデルの出力を用いる。探索が葉(子を持たない節点)$s_L$ に到達すると、その盤面を評価して事前確率を格納し(この評価は節点ごとに最初の1回だけでよい)、状態価値ネットワークの出力とロールアウトで得られた期待収益を線形結合して葉の状態価値とする。探索を終えると、訪問した枝の訪問回数 $N(s,a)$ と行動価値 $Q(s,a)$(訪問時に得た葉の状態価値の平均)を更新する。訪問回数が増えるほど事前確率の寄与($U$)の割合が下がり、実際に展開して得られた情報($Q$)が支配的になる。最終的には最も多く訪問された手を次の一手として選択する。(Source: [[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 4 深層強化学習]] §4.14) ## AlphaGoファミリーでの発展 [[AlphaGo]] は、次の手予測モデル $\pi(a|s;\sigma)$(教師あり学習で学習)を事前確率として使い、状態価値ネットワーク $V(s;\theta)$ とモンテカルロロールアウトを線形結合して葉を評価する。後継の AlphaGo Zero・AlphaZero では、事前確率と状態価値をともに単一のネットワーク $f(s;\theta)$ の出力 $(p,v)$ で置き換え、ロールアウトを行わずネットワークの状態価値をそのまま使うように単純化された。モンテカルロ木探索によって得られた方策 $\pi(s,a)\propto N(s,a)^{1/\tau}$ は、ネットワークの事前確率 $p$(今の盤面だけを見た瞬間的な評価)より強い手を選べる(先読みして評価し直した結果であるため)。この $\pi(s,a)$ を新たな学習目標として事前確率 $p$ をクロスエントロピー損失で近づけていく——という「深く読んだ手を今の自分より強い目標として使う」自己改善ループが、AlphaGo Zero以降の学習手法の核心である。(Source: [[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 4 深層強化学習]] §4.14) アルファ・ベータ法(alpha-beta pruning、既に求まっている価値の上下限を使って探索を打ち切る古典的なゲーム木探索)もAlphaGoでは検討されたが採用されなかった。ニューラルネットワークによる価値推定には時々大きな誤差が生じるため、平均で誤差を打ち消せるモンテカルロ木探索の方が、誤って探索を打ち切ってしまうリスクのあるアルファ・ベータ法より安定して有望な手を探索できるためである。(Source: [[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 4 深層強化学習]] §4.14) ## 横断的知見 1 ソース目のため、複数ソースの突き合わせによる横断的知見は今後の蓄積に委ねる。モンテカルロ木探索は本チャプターでは常に価値ネットワーク・方策ネットワークと組み合わせて使われており、単体のアルゴリズムというより「学習された価値・方策をオンラインで再評価する仕組み」として位置づけられている点は、[[AlphaGo]] エンティティページの学習パイプライン全体の記述と合わせて読む必要がある。 ## 未解決の問い - モンテカルロ木探索によるオンライン再評価が「学習済みの価値・方策をそのまま使うより強い」理由は、本文では「ニュートン法による更新に相当する」と参考文献(Bertsekas, arXiv:2108.10315)を引いて説明されるのみで、定量的な比較(再評価ありなしでの強さの差)は示されていない。 - UCBの不確実性項 $U(s,a)$ に事前確率 $P(s,a)$ ではなくネットワークの出力する不確実性推定(たとえばアンサンブルの分散)を使う設計は、囲碁以外のより不確実性の高い環境(実世界ロボティクスなど)でどう機能するか。 ## 関連 - source: [[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 4 深層強化学習]] - concept: [[強化学習]] - entity: [[AlphaGo]] ## 出典 - 岡野原大輔, 『ディープラーニングを支える技術〈2〉』, 技術評論社, 2022, 第4章, §4.14.