モンテカルロ木探索について

“Decision Making under Uncertainty"を参考にしている．Monte Carlo Tree Search(MCTS)はアルファ碁にも用いられたことで有名である．

木の上の再帰関数だから競プロ的な雰囲気で理解したほうが良いのかも．

逐次的意思決定問題

状態 $s$ における最適な方策を返す写像を $\pi(s)$ ，状態 $s$ における効用関数を $U(s)$ とする．

反復方策評価

期待効用の計算は方策評価と呼ばれる．反復方策評価では $\pi_0(s)$ を初期値(初期関数)で初期化して，これを使って効用関数のアップデートを繰り返す．

$$\begin{align*} U^{\pi}_0 (s) = R(s, \pi(s)) + \gamma \sum_{s{\prime}} T(s^{\prime} \mid s, \pi(s)) U_{t-1}^{\pi}(s^{\prime}) \end{align*}$$

$T(s^{\prime} \mid s, \pi(s))$ は状態から行動 $\pi(s)$ を使って遷移する確率である．

$U^{\prime}_0(s) \leftarrow 0$
for $t \leftarrow 1$ to $n$ do:
すべての $s$ について
$U^{\pi}_0 (s) = R(s, \pi(s)) + \gamma \sum_{s{\prime}} T(s^{\prime} \mid s, \pi(s)) U_{t-1}^{\pi}(s^{\prime})$
return $U_{n}^{\pi}$

方策反復

最適行動 $\pi(s)$ を求める方法は方策反復と価値反復の二つがある．方策反復では $\pi_0$ の初期値を設定して以下のように $\pi_k$ を更新する．

$$\begin{align*} \pi_{k+1} = \underset{a}{\mathrm{argmax}} \left( R(s, a) + \gamma \sum_{s^{\prime}} T(s^{\prime} \mid s, a) U^{\pi_k} (s^{\prime}) \right) \end{align*}$$

$\pi_{k+1}$ との差が縮まるまで繰り返す．

価値反復

価値反復は $U_k (s)$ 自体を更新していき，最後に $\pi^{*}(s)$ を求める．

$U_{0}(s)$ を初期化する
$U_{k+1}(s) \leftarrow \underset{a}{\max} \left( R(s, a) + \gamma \sum_{s^{\prime}} T(s^{\prime} \mid s, a) U_{k}(s^{\prime}) \right)$ で更新

効用関数が収束したら

$$\begin{align*} \pi(s) \leftarrow \underset{a}{\mathrm{argmax}} \left( R(s, a) + \gamma \sum_{s^{\prime}} T(s^{\prime} \mid s, a) U^{*} (s^{\prime}) \right) \end{align*}$$

で最適方策を求める．

オンライン手法

方策反復と価値反復では．全状態空間を対象に効用関数や方策が収束するまで繰り返しを行う必要がある．一方で最適ではないものの与えらえた状態 $s$ に対して準最適な解を求める任意時間のアルゴリズムがMCTSを含む以下の手法である．

前向き探索

シンプルに深さ優先探索を行う．

function $\mathrm{SelectAction}(s, d)$
　　if $d == 0$
　　　　return $(\mathrm{NIL}, 0)$
　　$(a^{*}, v^{*}) \leftarrow (\mathrm{NIL}, -\infty)$
　　for $a \in A(s)$
　　　　$v \leftarrow R(s, a)$
　　　　for $s^{\prime} \in S(s, a)$
　　　　　　$(a^{\prime}, v^{\prime}) \leftarrow \mathrm{SelectAction}(s^{\prime}, d-1)$
　　　　　　$v \leftarrow v + \gamma T(s^{\prime} \mid s, a) v^{\prime}$
　　　　if $v > v^{*}$
　　　　　　$(a^{*}, v^{*}) \leftarrow (a, v)$
return $(a^{*}, v^{*})$

分岐限定法

価値関数の下限 $\underline{U}(s)$ と状態ー行動の価値関数の上限 $\overline{U}(s)$ が分かっている場合，ノードの効用値 $v$ が $\underline{U}(s) \leq v \leq \overline{U}(s, a)$ の場合それ以上の深さに対しては再帰をcallしない．

function $\mathrm{SelectAction}(s, d)$
　　if $d == 0$
　　　　return $(\mathrm{NIL}, \underline{U}(s))$
　　$(a^{*}, v^{*}) \leftarrow (\mathrm{NIL}, -\infty)$
　　for $a \in A(s)$
　　　　if $v^{*} > \overline{U}(s, a)$
　　　　　　return $(a^{*}, v^{*})$
　　　　$v \leftarrow R(s, a)$
　　　　for $s^{\prime} \in S(s, a)$
　　　　　　$(a^{\prime}, v^{\prime}) \leftarrow \mathrm{SelectAction}(s^{\prime}, d-1)$
　　　　　　$v \leftarrow v + \gamma T(s^{\prime} \mid s, a) v^{\prime}$
　　　　if $v > v^{*}$
　　　　　　$(a^{*}, v^{*}) \leftarrow (a, v)$
return $(a^{*}, v^{*})$