AlphaZeroに対するTDLeaf(λ)の適用 ~準備編~

TDLeaf( $\lambda$ )の出典:Jonathan Baxter, Andrew Tridgell, Lex Weaver, "TDLeaf(lambda): Combining Temporal Difference Learning with Game-Tree Search," Proceedings of the Ninth Australian Conference on Neural Networks (ACNN'98), Brisbane QLD, February 1998, pages 168-172

　TDLeaf( $\lambda$ )とは1998年からある古い手法であり、簡単に言えばTD( $\lambda$ )を探索した値を使って行うものである。

TD( $\lambda$ )

　TD( $\lambda$ )とは、強化学習でよく用いられる時間差分学習の一種であり、後に続く状態の価値を $\lambda$ で重みづけながら教師情報として利用するものである。以下ではボードゲームのように報酬が最終状態でのみ与えられ、割引率が1であるような状況を前提とする。時刻 $t$ における状態 $s_t$ について、それに対する教師情報 $y_t$ は各状態の価値 $v_t$ を用いて次の図のように計算される。 $T$ は終端ステップ、 $z$ は最終結果に基づく報酬を示す。

　式として書くと

$\displaystyle y_t = \lambda^{(T-t-1)} z + (1 - \lambda) \sum_{\tau = t + 1}^{T-1} \lambda^{\tau - t - 1} v_{\tau} \tag{1}$

となる。これを目標に現在の状態価値を修正していけば良い。たとえば自乗誤差 $(y_t - v_t)^2$ を考えて勾配法で学習するなどの方法が考えられる。

　多くのボードゲームでは $T$ がそこまで大きくなることはないので影響はないかもしれないが、注意点として式(1)を愚直に計算すると各 $y_t$ を計算するのに $O(T)$ かかるので全 $y_t$ を求める計算量は $O(T^2)$ となってしまう。しかし式(1)はよく見ると

$\displaystyle y_t = \lambda y_{t + 1} + (1 - \lambda) v_{t +1} \tag{2}$

　と書けることがわかるので、後ろから計算していけば $y_{T - 1}, y_{T - 2}, \dots, y_{1}$ が $O(T)$ で求まる。式(2)を見てもわかるように、要するに $y_{t+1}$ と $v_{t + 1}$ の内分を取っていることになる。

TDLeaf( $\lambda$ )

　TDLeaf( $\lambda$ )ではTD( $\lambda$ )を探索を用いた手法へと拡張した。基本的には上のTD( $\lambda$ )での $v$ を探索した値で置き換えるということになる(GA将ブログなど参照)。

　論文ではαβ探索に対しての適用が議論されており、学習する状態も探索した葉にあたるノードを用いているが、必ずしもそのようにする必要はないと感じる。特にモンテカルロ木探索へ応用することを考えると、平均化しているので探索で得られた値に対応する葉のノードが一意に定まらない。学習する状態は探索を始めた根にあたるノードとしても良いと思われる。(余談ですがTDLeaf( $\lambda$ )をモンテカルロ木探索へ応用する論文を見つけられていません。ご存じの方がいましたら教えていただけるとありがたいです。)

　その場合ある局面 $s_t$ について探索した値 $v'_t$ もTD( $\lambda$ )で考慮する値としたい。つまり上の図が1ステップずつずれるような計算になる。式(2)で示した教師情報を $O(T)$ で求める工夫と合わせて、結局次の図のような計算をすれば良い。

　式として書くと

$\displaystyle y_t = \lambda y_{t + 1} + (1 - \lambda) v'_{t} \tag{3}$

であり、この $y_t$ を基に状態 $s_t$ における(探索をしない)価値 $v_t$ を更新する。

　ここでAlphaZeroの学習法はTDLeaf( $\lambda$ )において $\lambda = 1$ としたものだと捉えることができる。探索した値には全て $1-\lambda$ がかけられるので、 $\lambda = 1$ とすれば最終結果のみを考慮することになるためである。

　AlphaZeroのように最終結果だけを用いるのではなく、探索結果も使った方が学習が速いことはOracle Developersの記事で検証されている。ここでは最終結果と探索結果の平均や内分が取られている(elmoの学習方法とほぼ同じである)が、TDLeaf( $\lambda$ )の観点からすると $\lambda \lt 1$ とすることで探索結果を取り入れることができる。次回に続く。

TD()

TDLeaf()

TD( $\lambda$ )

TDLeaf( $\lambda$ )