TD(λ)とTDLeaf(λ)の統一された見方 - GA将？開発日記～王理のその先へ～

　「TD(λ)とTDLeaf(λ)の違いは、価値関数（＝評価関数）の実装方法の違いだけなんじゃないか」って話をダラダラと書きます。要はチラシの裏。個人的に考えをまとめるためだけのものです。

　まず、適格度トレースがあると話がややこしくなるので、ここではTD(0)とTDLeaf(0)に絞って扱います。

　TD(0)の価値関数の更新ルールは下記の通り。

　　 $Q\left(s_t,a_i\right) \leftarrow Q\left(s_t,a_i\right)+\alpha\left(r+\gamma Q\left(s_{t+1},a_j\right)-Q\left(s_t,a_i\right)\right)$

　 $Q\left(s_t,a_i\right)$ は「状態 $s_t$ での行動 $a_i$ の価値」、 $\alpha$ は学習率、rは「状態 $s_t$ で行動 $a_i$ を行った際に得られた報酬」、 $\gamma$ は割引率（0〜1）、 $s_{t+1}$ は状態 $s_t$ の2手*1後の状態、 $a_i$ と $a_j$ はそれぞれ $s_t$ と $s_{t+1}$ で選択した手です。

　式 $x \leftarrow x + \alpha \left( y - x \right)$ の意味は「xの値を $\alpha$ で示す割合だけyに近付ける」という事なので、この場合は $r+\gamma Q\left(s_{t+1},a_j\right)$ が $Q\left(s_t,a_i\right)$ の目標値となる。

　以下、将棋の場合に限定すると、状態＝局面、行動＝手となる。

＃　余談ですが、事後状態価値関数を導入すると $Q\left(s,a\right)=W\left(s',a\right)$ と書ける。 $W\left(s',a\right)$ は「状態s'で行動aを行った後の状態の価値」である。将棋の場合であれば、事後状態価値関数を評価関数として用いる事が出来るので、これらの関数は同一視しても構わない。

　次に、TDLeaf(λ)の更新ルール。

　　 $Q\left(leaf\left(s'_t\right),a_i\right) \leftarrow Q\left(leaf\left(s'_t\right),a_i\right)+\alpha\left(r+\gamma Q\left(leaf\left(s'_{t+1}\right),a_j\right)-Q\left(leaf\left(s'_t\right),a_i\right)\right)$

　なお、 $leaf\left(s'_t\right)$ は「状態 $s'_t$ から探索を行った、PV末端の状態」を、 $s'_t$ は「状態 $s_t$ で行動aを行った後の状態」を示すものとする。

　ここで、 $Q\left(leaf\left(s'_t\right),a_i\right)=X\left(s_t,a_i\right)$ とすると、上記の式は

　　 $X\left(s_t,a_i\right) \leftarrow X\left(s_t,a_i\right)+\alpha\left(r+\gamma X\left(s_{t+1},a_j\right)-Q\left(s_t,a_i\right)\right)$

となる。

　この式をTD(0)の更新ルールと見比べてみると、QとXが異なるだけで、他の部分は全く同一となる。

　つまり、 $X\left(s_t,a_i\right)$ を「内部で探索を行う、動的な価値関数」と見なせば、TD(0)とTDLeaf(λ)は同一のアルゴリズムと考えれる。

＃この部分ですが、別にTDLeaf(λ)にケチをつけようとかそういう意図ではなく、単に「そういう見方も出来る」と書きたいだけです。

　で、同一のアルゴリズムと考えると何が嬉しいかというと、一つはTD(λ)の派生アルゴリズム（例えばQ学習）とTDLeaf(λ)を混ぜ合わせた、「方策オフTDLeaf(λ)」等のアルゴリズムの設計が容易になるという事。

　もう一つ嬉しいのは、アルゴリズムの選択が容易になるという事。

　TD(0)とTDLeaf(λ)の選択を強化学習アルゴリズムの選択と考えるとどちらを選ぶべきかは難しいです。しかし、価値関数の実装が静的か動的かの違いだけと捉えれば、後は自分の扱いやすい価値関数の実装を選ぶだけなので、比較的簡単な問題です。

　という訳で、私はこの考え方を応用して方策勾配法とTDLeaf(λ)のいいとこ取りをしたアルゴリズムを実装してみようと考えています。

　…後は図書館でリクエストした本が届くのを待つだけなんですが、待つ間ってのは辛い時間ですね。もうちょっとの辛抱です。

*1:自分と相手の手