在以往的强化学习方法中我们看到，不管是使用纯粹采样的MC方法，还是基于Bellman equation的DP方法以及bootstrape方法，每个value(state or action)都依赖于其后发生的动作，即属于forward view的算法思想：
通过引入Eligibility trace，我们便能够将forward view的算法转变为backward view的算法。
The λ-return
这个算法比较像MC method with approximation，后面的section会看到使用Eligibility trace的MC方法，这两者完全是不同的，所以我认为λ-return方法和TD(λ)不完全一致，两者结合可以得到true on-line算法，但是λ-return仍然是forward view的，而TD(λ)则是将backward view融入了bootstrape方法中的。
回忆一下在n step-TD中使用的G：
如果使用不同的n，并将不同的n对应的G进行加权，就可以得到如下的混合的return，我们称之为λ-return：
可以看到每个G赋给的weight总和=1。
上面的λ-return通式对应于continuing task，对于episodic task，λ-return可以改写为如下公式，仍然保证了weight的总和为1：
如果使用λ-return完成function approximation的weight更新，则使用如下的更新公式，对应的算法称之为off-line λ-return算法：
这个更新公式通过λ将MC方法和n-step的TD方法联系在一起，如果λ趋于1，那么更新公式趋于MC方法，如果λ趋于0，那么更新公式趋于n-step TD方法，准确来说是one-step TD方法，因为受到λ的幂指数影响。
通过random walk例子比较off-line λ-return和n-step TD的性能，例子可以参考19-state Random walk。
目前为止算法仍然是forward view更新的，下一个section将会讨论第一个引入backward view更新的算法TD(λ)。
TD(λ)
理解TD(λ)方法，主要要理解Eligibility trace z。z是和w维度相同的向量。w是一个long-memory的变量，也是我们在多个episode中训练的变量，z却是一个short-memory的变量，在每个episode开头将它初始化为0。一开始可能不理解z的作用，可以先看一下z是如何在w的更新中使用的：
首先是z的更新：
然后是z在w更新中的使用：
( _ゝ`)
其中的δ_t是one-step TD error，可以看到z替代了∇v̂(S_t,w_t)的位置，而且z和后者是同维度的，再结合z的更新公式，我们可以分析得到：z用来调整w各个分量更新的权重，如果令z更新公式里的λ=0，那么TD(λ)就和TD(0)方法一致了，但是z引入了“之前”的state的影响，使得更新算法具有了backward的视角：
使用Eligibility trace z更新的伪代码如下：
通过random-walk的例子可以比较TD(λ)和off-line λ-return算法的性能，例子参考19-state Random walk。
关于TD(λ)的收敛性，可以证明在使用linear approximation function的on-policy训练算法的条件下，w收敛到最小VE的理想w的比例范围内：
n-step Truncated λ-return Methods
在之前提到的λ-return中，因为越往后的state系数很小对应的影响很小，所以可以忽略其影响得到truncated λ-return：
使用1truncated λ-return进行w更新的算法称为TTD(λ)，更新公式如下：
TTD(λ)关于truncated λ-return可以使用下面的优化公式计算：
注意δ’的w的下标：
给出backup diagram of truncated TD(λ)：
Redoing Updates: The Online λ-return Algorithm
上一个section提到的truncated TD(λ)方法可以改进为on-line算法，具体思路如下：
即将h遍历1,2,3，…分别完成不同h的更新，每次更新的结束作为下一次更新的开始，比如h=1更新结果作为h=2的w初始值，这种算法称为on-line λ-return algorithm。
关于on-line和off-line λ-return算法的性能比较，可以参考19-state random-walk
True Online TD(λ)
通过上一个section，我们可以看到on-line算法表现的更好，但是给出的on-line λ-return算法计算复杂度很高，每次h的迭代量很大。我们发现，如果把更新结果写在一个下三角矩阵中，那么只有对角线上的值是有用的：
使用下面的更新规则直接更新对角线上的w，得到true online TD(λ)算法：
其中的z为dutch trace，使用如下公式更新：
true online TD(λ)算法的伪代码如下：
关于Eligibility trace有如下三种：
1、TD(λ)使用的，称为accumulating trace
2、早期的算法中经常使用的，称为replacing trace，仅适用于0-1(binary)的feature vector，如Tile Coding产生的feature，公式如下：
3、true on-line TD(λ)使用的dutch trace，这种Eligibility trace也是目前最常用的。
Dutch Traces in Monte Carlo Learning
dutch trace一般在TD learning算法中使用，但是事实上它也可以在MC方法中使用，并带来计算上的优化。
首先看一下基本的MC方法with approximation：
这里关于return G做如下假设：中间过程的reward都是0，只有到达terminal state的action才产生reward，所以G可以视为常数。
一般的MC方法会在0-T之间更新T次上式，但是可以将公式展开得到如下一步更新公式：
其中a_T和z_T可以不依赖G独立的进行增量更新：
这种方法可以获得更好的计算性能，因为可以不用使用额外的空间来存储episode中所有的feature vector，只用维护两个增量更新的变量即可；计算将分布到每一步中去，而不是在episode结束之后才开始。
Sarsa(λ)
将上面使用的state value改为action value，即可从TD(λ)算法推广得到Sarsa(λ)算法，直接给出伪代码如下:
Sarsa(λ)和n-step Sarsa算法的性能对比可以参考例子Example 12.2: Sarsa(λ) on Mountain Car
同理从true on-line TD(λ)算法推广可以得到on-line Sarsa(λ)算法，伪代码如下：
例子同上。
Stable Off-policy Methods with Traces
GTD(λ)
GTD算法的Eligibility trace版本，w更新规则：
δ：
z_t使用accumulating trace：
v_t更新公式：
GQ(λ)
Gradient-TD algorithm for action values with eligibility traces:
z_t：
v_t的更新和GTD(λ)一致。
HTD(λ)
a hybrid state-value algorithm combining aspects of GTD(λ) and TD(λ),it is a strict generalization of TD(λ) to off-policy learning, meaning that if the
behavior policy happens to be the same as the target policy, then HTD(λ) becomes the same as TD(λ), which is not true for GTD(λ).
update rule:
可以看到维护了两个Eligibility trace。
Emphatic TD(λ)
extension of the one-step Emphatic-TD algorithm from Section 11.8 to eligibility traces(param is Θ):
