---

layout: post
title: Review of TD-Leaf(lambda)

date: 2017-02-26 22:48

昨天报seminar的时候把TD-Leaf$(\lambda)$ 搞错了，23333.

本篇文章重新回顾一下Temporal Difference Learning，
主要包括TD$(0)$,TD$(1)$,TD$(\lambda)$，
最后再回顾一下TD-Leaf$(\lambda)$.

Paper的话大致是如下两篇：

KnightCap: A chess program that learns by combining TD(lambda) with game-tree search
TDLeaf(lambda): Combining Temporal Difference Learning with Game-Tree Search

0x01 TD$(\lambda)$

设$S$ 表示所有可能的Position的集合
在 $t$ 时刻，agent的状态表示为 $x_t$ ,且$x_t \in S$
$A_{x_t}$ 表示在position $x_t$时的合法步的集合

当agent选择一个action $a \in A_{x_t}$,
从状态$x_t$转化为$x_{t+1}$，
我们把选择action $a$的概率记为$p(x_t,x_{t+1},a)$
这里的状态$x_{t+1}$，表示在我方做出一个action，对方也做action后得到的状态。
比如2048，当前状态我们称为$x_t$,此时，我们向上移动后，系统再随机产生一个方块，这时才算从状态$x_t$转移到了$x_{t+1}$。

当游戏结束时，agent会得到一个(scalar)reward，
通常获胜得到 $"1"$分，平局得到 $"0"$分，失败得到 $"-1"$分。
当然，如果是2048的话，就是最后玩完游戏的总得分。

假设我们的游戏玩到结束用了$N$步,即游戏的 $length=N$.
令$r(x_N)$ 表示游戏结束时的reward.

假设agent从当前状态$x$选择某个action进行转移，则我们期望得到的reward可以表示为

$$\begin{equation} J^{*}(x):=E_{x_N|x}r(x_N) \end{equation}$$

$J^{*}(x)$表示从当前点往下走我们能得到的分数的期望。

当状态空间$S$很大时，我们无法将每一个状态$x$的$J^{*}(x)$值存起来

所以我们尝试用一些带参数的函数$\widetilde{J}(.,w)$来表示这个理想的函数$J^{*}(x)$.

$\widetilde{J}:S \times \mathbb{R}^{k}\rightarrow \mathbb{R}$

$\widetilde{J}(.,w)$是一个可微函数，比如线性函数（linear function）, 样条函数（splines）, 神经网络（neural
networks）,等等。
$w=(w_1,...,w_k)$是一个Vetcor。

很显然，在每一个状态，$J^{*}(x)$和$\widetilde{J}(.,w)$会有一个差值error，
我们的目标就是，找到vector $w \in \mathbb{R}$ 的参数，使得error最小，突然在这里想起了machine learning的gradient descent.

那么，TD$(\lambda)$就是干这个事情的。

假设 $x_1,...,x_{N-1},x_N$ 代表整个游戏的状态序列。
对于给定的向量$w$，我们定义从$x_t \rightarrow x_{t+1}$的差值为temporal
difference：

$$\begin{equation} d_t:=\widetilde{J}(x_{t+1},w)-\widetilde{J}(x_t,w) \end{equation}$$

对于

$$J^{*}(x_t)$$ 和 $$J^{*}(x_{t+1})$$ 来说：

$$E_{x_{t+1|x_t}}[J^{*}(x_{t+1})-J^{*}(x_{t})]=0$$

所以如果$\widetilde{J}(.,w)$足够接近$J^{*}$,$E_{x_{t+1|x_t}}d_t=0$应该非常接近0.
前面我们有提到,游戏最后的reward是$r(x_N)$，所以最后一个状态的temporal difference $d_{N-1}$满足:

$$d_{N-1}=\widetilde{J}(x_N,w)-\widetilde{J}(x_{N-1},w)=r(x_N)-\widetilde{J}(x_{N-1},w)$$

也就是说$d_{N-1}$是 游戏最后的正确输出和倒数第二步的预测值的差值。

最后我们会得到下面的formula:

$$\begin{equation} w:=w+\alpha \sum^{N-1}_{t=1} \nabla \widetilde{J}(x_t,w)[\sum^{N-1}_{j=t} \lambda^{j-t} d_t] \end{equation}$$

$\nabla \widetilde{J}(.,w)$是向量$w$在每个方向上的偏导，$\alpha$是learning rate， $\lambda \in [0,1]$, 它根据时间来控$d_t$的反向传播，其实也很好理解，离要更新的状态越远，对它的影响就越小，所以$\lambda^{m}$的m就越大，值当热越小。

TD$(0)$

如果 $\lambda=0$,因为只有 $0^0=1$，所以原来的公式就变为

$$\begin{equation} w:=w+\alpha \sum^{N-1}_{t=1} \nabla \widetilde{J}(x_t,w)d_t \\ = w+\alpha \sum^{N-1}_{t=1} \nabla \widetilde{J}(x_t,w)[\widetilde{J}(x_{t+1},w)-\widetilde{J}(x_{t},w)] \end{equation}$$

TD$(1)$

那就是，，全部都用最后一个状态更新 :

$$\begin{equation} w:= w+\alpha \sum^{N-1}_{t=1} \nabla \widetilde{J}(x_t,w)[r(x_N)-\widetilde{J}(x_{t},w)] \end{equation}$$

从一个状态转移到另一个状态，我们希望转移之后的

$$\widetilde{J}({x_{a}}',w)$$ 最小。也就是：

$$\begin{equation} a^{*}(x):=\underset{c\in A_x}{\operatorname{argmax}} \end{equation}\widetilde{J}({x_{a}}',w)$$

对于2048，Backgammon这样的游戏，我们可以通过搜寻一步或者一层来评估盘面前后的差距，但是对于西洋棋，象棋这样的游戏，仅仅搜寻一步，是很难进行精确预估的。

对于这些游戏，我们往往会使用min-max search，或者是用alpha-beta进行剪枝。

0x02 TD-Leaf$(\lambda)$

那如果想把TD用到西洋棋上呢？这里我们把TD和Search结合起来使用。

对于TD$(\lambda)$，我们在计算每个状态的值时，仅仅使用

$$\widetilde{J}(.,w)$$ 来计算， 而在这里，我们通过search d层，找到search之后叶节点中的最优值作为root节点的值，也就是当前状态的估计值。

如上图所示：

TD$(0)$，$d_t$的算法是前后两个状态的预估值相减
TD$(\lambda)$则是从状态$s_t$到结束每两个状态的预估值都对其有贡献
TDLeaf$(\lambda)$的特点在于，在计算每个状态

$$x_i$$ 的预估值时，会向下search $d$ 层，并用叶节点的值表示 $$x_i$$ 的预估值。