我们之前讲过的蒙特卡洛方法和时序差分算法有一点不同点，当更新当前状态的值函数的时候，蒙特卡洛方法是使用整个轨迹来预估，而TD算法则是使用一段轨迹来预估，而这个一段轨迹一般是小于整条轨迹的。而通过利用不同的举例来估计，我就称为多步时序差分法也叫做 资格迹法。

而资格迹法一般又分为两个角度来计算。

一种前项视角，估计当前状态的值函数的时候，使用当前时刻以后的几个时刻来估计。

另一种是后项的视角来更新，就是使用当前时刻之前的数据来更新，资格迹是进行资格分配的方法，它是强化学习的一种基本机制。$TD(\lambda)$算法中的$\lambda$就是对资格迹的运用。包括Q-learning，sarsa等算法都可以借用这种方法提升效率。

多步TD评估

蒙特卡洛的估计公式是

$$V(s_t) <- V(s_t)+\alpha(G_t-V(s_t)) \tag{6.1}$$

其中更新目标$G_t$为累计回报。

$$G_t=r_{t+1}+\gamma r_{t+2}+\gamma^{2} r_{t+3}...$$

很容易知道，对于一步的TD更新目标

$$G_{t}^{1}=r_{t+1}+\gamma V(s_{t+1})$$

很容易知道，对于两步的TD更新目标

$$G_{t}^{2}=r_{t+1}+\gamma V(s_{t+2}) +\gamma^{2}V(s_{t+2})$$

以此类推我们就能知道n步的回报是如何表达。由上面的过程我们知道，其实如果我们的n大于轨迹长度，那么就是蒙特卡洛的算法，

前向算法

既然存在n步时序差分，那么这个n取值就是一个值得讨论的问题。
一种简单的方法是通过平均多个不同的n步回报进行更新，最后他们的权重之和为1。
下面我们来举个例子。
假如我们使用2步TD和4步TD相结合。每次更新的时候，2步TD权重是1/2,4步TD也是1/2作为最终的更新量。
前向视角的$TD(\lambda)$算法最主要的特点是平均化的操作运用。唯一特别是$TD(\lambda)$直接平均化所有步的回报。每个回报的权重是$(1-\lambda)\lambda^{n-1}$，通过引用这个$\lambda$综合考虑步数的回报。
如果轨迹长度是T的时候，就有

$$G_{t}^{\lambda}=(1-\lambda) \sum_{n=1}^{T-t-1}\lambda^{n-1}G_{t}^{n}+\lambda^{T-t-1}G_{t} \tag{6.2}$$

值更新的公式如下

$$V_(s_t) <- V(s_t)+\alpha(G_{t}^{\lambda}-V(s_t)) \tag{6.3}$$

后向算法

刚刚讲的前向算法主要是需要当前时刻以后的几个时刻的状态，其实和蒙特卡洛的思想相近，当时无法直接实现。
我们需要一种无须等到实验结束就更新当前状态值函数的方法。这种增量式更新方法需要利用多步的时序差分的后向观点。它采用的明确的因果性递增机制来实现的。
后向视角，引入一个和每个状态都相关的额外变量（资格迹）。现在外面来讲个打死外星人的例子。外星人被连续的3次拳击和一次电击后死亡，那么我们在分析外星人死亡原因的时候，到底是拳击因素重要还是电击的因素重要呢？
实际进行资格迹分配的时候有两种方式，一种是频率启发式，将资格迹分配给最频繁的拳击方式，还有一种是最近启发式，也就是电击方式。
在t时刻状态s，对应的资格迹标记为$E_{t}(s)$

$$E_{s}=0$$

$$E_{t}^{s}=\gamma \lambda E_{t-1}(s)+I(S_t=s)$$

初始的资格迹，$E_{s}=0$，当下一个时刻，被访问到的状态，其资格迹为前一个时刻该状态资格迹$E_{t-1}(s)$乘以退化参数$\lambda$和衰减因子$\gamma$然后加1，表示当前该状态资格迹变大。其他未被访问的状态，其资格迹只是原有基础上乘以$\lambda \gamma$，不用加1.那么我们来看看上文那个例子的更新过程。
在上面的场景中我们分别有两个状态拳击和电击分别是s1和s2，然后$\lambda=0.9,\gamma=0.8$

当t=1的时候。

$$E_{1}^{s_1}=\gamma \lambda E_{0}(s_1)+1=1 \\ E_{1}^{s_2}=\gamma \lambda E_{0}(s_2)=0 \\$$

当t=4的时候

$$E_{4}^{s_1}=\gamma \lambda E_{3}(s_1)+1=1.61 \\ E_{4}^{s_2}=\gamma \lambda E_{3}(s_2)+1=1 \\$$

因此推测外星人的死是拳击的权重更大一些。

我们能够看出可以使用资格迹$E_{t}(s)$来分配各值函数的资格，也就是说使用资格迹来衡量TD误差发生时，各个状态值函数更新会有多大影响。

$$\delta_t=R_{t+1}+\gamma V_{t}(S_{t+1}) -V_{t}(S_t) \tag{6.4}$$

结合资格迹更新状态价值

$$V(s) <- V(s)+\alpha \delta E_{t}(s) \tag{6.5}$$

前向Sarsa方法

将资格迹与Sarsa方法结合就形成了一个新的算法就是前向的Sarsa方法，与原始的Sarsa方法不同，需要学习的不是$V_t(s)$,而是学习$Q(s,a)$,其主要思想同$TD(\lambda)$一致，通过每个回报赋予权重$(1-\lambda)\lambda^{n-1}$的平均多个Q回报进行更新。

这个时候的Q回报相对于累计回报$G$，指的是状态行为对$(s,a)$从t时刻开始往后所有回报的衰减的总和。

其中n步以后的Q回报就是

$$Q_{t}^{n}=r_{t+1} +\gamma r_{t+2}...+\gamma^{n} Q(s_{t+n}, a_{t+n})$$

对Q回报加权求和的$\lambda$回报$Q_{t}^{\lambda}$

$$Q_{t}^{\lambda}=(1-\lambda) \sum_{n=1}^{\inf} \lambda^{n-1}Q_{t}^{n} \tag{6.6}$$

那么最后的更新公式是

$$Q(S,A)=Q(S_t,A_t)+\alpha(Q_{t}^{\lambda}-Q(S_t,A_t))$$

后向Sarsa方法

后向的Sarsa方法引入资格迹，将当前的行为值函数误差按照比例抛给其他状态行为值函数，作为更新额依据。不同的是，资格迹不再是$E_t(s)$而是$E_t(s,a)$，就是针对每一个状态行为都有一个资格迹

$$E_{0}(s,a)=0 \\ E_t(s,a)=\gamma \lambda E_{t-1}(s,a)+I(S_t=s,A_t=a)$$

其他的部分后后向的TD一样

$$Q_{t+1}(s,a)=Q_{t}(s,a)+\alpha \delta_t E_{t}(s,a)$$

Sarsa是一个在线算法，也就是采样的策略和评估改进的同一个策略，对于在线算法，算法更新方式很多，很简单就是依据当前的行为值函数估计值采用$\sigma$贪心算法更新。

前向的Watkin’s $Q(\lambda)$方法

常用的Qlearning是一个离线算法，就是产生的策略和评估的策略不是同一个策略，也就是我说需要依据带有$\sigma$贪心行为的轨迹来学习一个贪心策略。

在进行值函数更新的时候，Q-learning采用的更新公式

$$Q(s,a)=Q(s,a)+\alpha(R+\gamma\ max Q(s',a')-Q(s,a)$$

而Q-learning是一步更新，如何来进行多步更行的？
假设我们正在进行贪心策略在状态(s,a)的行为值函数，前两个时间步选择的行为是贪心的，但是第三个时间步行为是探索策略，那么有效的轨迹长度，最长就是第二个时间步，从第三个时间步往后的策略都不会理会，也就是说使用最近的一个探索策略对应的时间步长，所以在进行数据探索的时候，一旦发现有探索行为就立刻结束了，
Q回报的加权求和公式同公式6.6

更新公式为

$$Q(s_t,a_t)=Q(s_t,a_t)+\alpha(Q_{t}^{\lambda}-Q(s_t,a_t))$$

后向的Watkin’s $Q(\lambda)$方法

后向的$Q(\lambda)$的资格迹如何更新呢？

对位状态行为(s,a)的资格迹，更新分为两部分，首先如果当前的行为选择$a_t$，是贪心行为，资格迹乘以系数$\lambda \gamma$否则资格迹就是0，其次，对于当前在访问的$(s_t,a_t)$其资格迹单独加1.资格迹的更新公式为。

\begin{equation} E_{t}(s,a)=I_{ss_{t}} I_{aa_{t}} + \left\{ \begin{aligned} \lambda \gamma E_{t-1}(s,a)\ \ 如果Q_{t-1}(s_t,a_t)=maxQ_{t-1}(s_t,a) \\ 0 \ \ \ \ \ \ \ \ 其他\\ \end{aligned} \right. \end{equation}

其中$I_{ss_{t}} I_{aa_{t}}$表示示例函数，$I_{ss_t}$表示当$s=s_{t}$其值为1.

假设当前正在访问的状态行为$(s,a_t)$，其中$a_t$表示探索行为，状态行为对$(s,a)$的资格迹为：$E_{t}(s,a)=0+0=0$，与此同时，当前正在访问的状态行为$(s,a_t)$的资格迹$E_{t}(s_{t},a)=1+0=1$.

$$Q_{t+1}(s,a)=Q_{t}(s,a)+\alpha \delta_t E_t(s,a)$$

其中

$$\delta_t=r_{t+1}+ \gamma max Q_t(s_{t+1},a')-Q_t(s,a_t)$$