12. 资格迹

资格迹"/>

12. 资格迹

文章目录

• 资格迹
• • 前言
  • 1. λ \lambda λ回报
  • 2. TD( λ \lambda λ)
  • 3. n-step截断 λ \lambda λ回报算法
  • 4. 重新更新：在线 λ \lambda λ回报算法
  • 5. 真正的在线TD( λ \lambda λ)
  • 6. MC学习中的dutch trace
  • 7. Sarsa( λ \lambda λ)
  • 8. 变量λ和γ
  • 9. 带有控制变量的off-policy traces
  • 10. Watkins's Q( λ \lambda λ) to Tree-Backup( λ \lambda λ)
  • 11. 带有traces的稳定的off-policy方法
  • 12. 实现中的问题
  • 总结

资格迹

前言

资格迹eligibility traces是强化学习中的一个基本机制，通常在算法中我们用 λ \lambda λ表示使用了资格迹的算法，比如TD( λ \lambda λ)等，几乎所有的基于TD原理的算法都有对应的资格迹的形式。
资格迹统一了TD和MC， λ = 1 \lambda=1 λ=1就变为了MC方法， λ = 0 \lambda=0 λ=0等价于单步TD方法。处于中间的方法被称作是中间算法，这类算法往往比两种极端方法的表现好。
之前第七章使用n-step TD方法组合使用TD和MC，但是资格迹的方式更加优雅，并且有一定的计算优势。该机制使用了一个短期记忆的向量，资格迹 z t ∈ R d z_t∈R^d zt​∈Rd,与权重w平行。大致的的思想就是，当w的某个分量参与了一个估计值的计算，那么z对应的部分就增大，之后慢慢减小。当对应的z分量减小为0之前有一个不为零的TD error，那么w对应的部分就会进行更新。资格迹消减的系数是 λ \lambda λ。
资格迹相比于n-step TD算法的计算优势在于只需要使用一个资格迹向量，不需要像n-step算法一样保存过去n个状态的特征向量。学习的过程也是连续均匀分布，而不是延迟到获得episode末尾的反馈值为止。另外，学习过程可以每一步都进行，从而立马影响下一状态的行为，不用等到n步之后更新。
有些算法需要等待之后的返回值来学习，比如MC算法和n-step TD算法，这种基于从被更新状态往前观察的机制叫做forward views 。一般这种机制实现起来比较复杂，因为需要考虑当前还未获得的之后的状态的反馈值。本章介绍的算法要能够使用当前的TD error并且通过资格迹使用先前访问过的状态来获得和forward views几乎一样的更新，这种形式叫做backward views。
先介绍状态值函数的估计，然后延伸到动作值函数和控制算法。主要关注线性函数近似，因为其使用资格迹之后的结果会变更好。

1. λ \lambda λ回报

带有近似拟合器的n-step状态回报定义如下：
G t : t + n ≐ R t + 1 + γ R t + 2 + ⋯ + γ n − 1 R t + n + γ n v ^ ( S t + n , w t + n − 1 ) , 0 ≤ t ≤ T − n G_{t : t+n} \doteq R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^{n-1} R_{t+n}+\gamma^{n} \hat{v}\left(S_{t+n}, \mathbf{w}_{t+n-1}\right), \quad 0 \leq t \leq T-n Gt:t+n​≐Rt+1​+γRt+2​+⋯+γn−1Rt+n​+γnv^(St+n​,wt+n−1​),0≤t≤T−n
复合更新
我们现在考虑，更新目标不仅仅是一个n-step反馈值，而是不同的n的n-step反馈的均值，比如一个两步反馈加上一个四步反馈的均值组合成为一个新的反馈值。任意的n步反馈的集合都可以通过这种形式进行平均，保证最终的系数和是1即可。合成的反馈值能够和单个的n-step反馈一样处理TD error，所以可以作为一个算法的收敛更新目标。这种均值的形式能够得到一系列的算法，比如可以将一步TD的反馈和无穷步反馈MC反馈进行平均得到一种新的组合TD算法和MC算法的方式。理论上可以将基于model得到的DP反馈和实际试验得到的反馈进行简单组合。
这种更新方式叫做复合更新 。其backup diagram对应如下：

注：复合更新只能等待其分量中最长的部分更新得到结果之后才可以进行计算。比如上图中，必须等到t+4（上图右侧）的那个更新结束之后，才可以计算平均的复合更新值。因此，使用的时候可以限制最长n步的n，防止每次更新都需要很长时间。

λ \lambda λ回报
下一节讲解TD( λ \lambda λ)算法，暂且只需要知道其采用了 λ \lambda λ回报作为更新目标，融合了资格迹来提升计算效率。其是混合更新的一种特殊形式，因为它融合了无限个n步回报，其次为了保证每个融合项的权重和为1，每一项的权重正比于 λ n − 1 \lambda^{n-1} λn−1，并且最后乘归一化因子 1 − λ 1-\lambda 1−λ，这种构造的复合更新叫做 λ \lambda λ回报。其定义如下：
G t λ ≐ ( 1 − λ ) ∑ n = 1 ∞ λ n − 1 G t : t + n G_{t}^{\lambda} \doteq(1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} G_{t : t+n} Gtλ​≐(1−λ)n=1∑∞​λn−1Gt:t+n​
其对应的backup diagram如下，反映了每一步反馈值的系数。

如何验证上面的权重和等于1？利用等比数列求和。或者关注每个n步回报的权重因子，如下图，
n为1时权重是 1 − λ 1-\lambda 1−λ,然后以 λ \lambda λ系数衰减，n为3时权重为 ( 1 − λ ) λ 2 (1-\lambda)\lambda^2 (1−λ)λ2.
对于有限长度T的episode来说，t+n≥T时，n步回报就等于MC回报，此时回报就相当于是 G t G_t Gt​，为了区分这两种形式，我们可以把 λ \lambda λ回报写成如下的形式：
G t λ = ( 1 − λ ) ∑ n = 1 T − t − 1 λ n − 1 G t + t + n + λ T − t − 1 G t G_{t}^{\lambda}=(1-\lambda) \sum_{n=1}^{T-t-1} \lambda^{n-1} G_{t+t+n}+\lambda^{T-t-1} G_{t} Gtλ​=(1−λ)n=1∑T−t−1​λn−1Gt+t+n​+λT−t−1Gt​
λ \lambda λ为1时，第一项为0，此时 λ \lambda λ回报就是MC回报，如果 λ \lambda λ为0，此时第二项为0，第一项只有在 0 0 = 1 0^0=1 00=1，所以此时 λ \lambda λ为0时 λ \lambda λ回报就等于 G t : t + 1 G_{t:t+1} Gt:t+1​，此时就等价于单步TD方法。再一次实现了TD方法和MC方法的混合。
offline λ \lambda λ回报算法
我们把更新目标换成 λ \lambda λ回报，然后利用SGD更新近似值函数的权重，这样就可以得到一个offline λ \lambda λ回报算法。
w t + 1 ≐ w t + α [ G t λ − v ^ ( S t , w t ) ] ∇ v ^ ( S t , w t ) , t = 0 , … , T − 1 \mathbf{w}_{t+1} \doteq \mathbf{w}_{t}+\alpha\left[G_{t}^{\lambda}-\hat{v}\left(S_{t}, \mathbf{w}_{t}\right)\right] \nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right), \quad t=0, \ldots, T-1 wt+1​≐wt​+α[Gtλ​−v^(St​,wt​)]∇v^(St​,wt​),t=0,…,T−1
之所以是offline的，是因为这个式子中的权重更新是在一个episode结束之后进行的。好比是我们先收集好数据然后再计算权重，因此是离线的。

offline λ \lambda λ回报算法和n-stepTD算法在19状态随机游走问题上的表现如下：

纵轴表示的是用offline λ \lambda λ回报算法和n-step TD算法估计的值函数与真实值函数之间的均方误差。不同线条表示不同参数 λ \lambda λ和n的表现。由此可以看到offline λ \lambda λ回报算法和n-stepTD算法可以获得相媲美的效果，两个算法都是在取中间值时会获得较好的算法效果。

前向视角
简单来说就是往前看，n-step回报就是前向的。可以假设我们当前在状态 S t S_t St​上，当我们向前看的时候，如果看到 S t + 1 S_{t+1} St+1​,那么我们就可以计算 G t : t + 1 G_{t:t+1} Gt:t+1​，如果看到 S t + 2 S_{t+2} St+2​，那么我们就可以计算 G t : t + 2 G_{t:t+2} Gt:t+2​.

2. TD( λ \lambda λ)

TD( λ \lambda λ)算法可以看作是offline λ \lambda λ算法的在线版本。与offline λ \lambda λ回报算法相比，TD( λ \lambda λ)的改进有以下三个方面：

• TD( λ \lambda λ)在每个step上都会更新权重向量，不必等到episode的结尾。
• 因为是每步更新，所以TD( λ \lambda λ)的计算会均匀分布在每一步上。
• TD( λ \lambda λ)可以应用于continuing task中。

本节内容讲解利用函数近似的方法求解TD( λ \lambda λ)，采用半梯度方法来更新权重参数。资格迹是一个d维向量，表示为 z t ∈ R d z_t∈R^d zt​∈Rd,向量的维度和权重向量w的维度是一样的。资格迹的每个维度可能会影响权重向量对应维度的值，权重向量是我们最终要求的值，它的估计值的好坏直接决定着近似函数的误差。我们希望不断更新这个权重，得到更加精确的近似。所以这个量是不断累积更新的。资格迹是一个短期的量，通常来说，其影响不会超过一个episode的长度。
资格迹
TD( λ \lambda λ)中，资格迹向量在episode的开始时刻会被初始化为0，然后每步再以梯度值增加，再以 γ λ \gamma\lambda γλ的速率衰减，所以资格迹的表达式就是：
z − 1 ≐ 0 z t ≐ γ λ z t − 1 + ∇ v ^ ( S t , w t ) , 0 ≤ t ≤ T \begin{array}{l} \mathbf{z}_{-1} \doteq \mathbf{0} \\ \mathbf{z}_{t} \doteq \gamma \lambda \mathbf{z}_{t-1}+\nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right), \quad 0 \leq t \leq T \end{array} z−1​≐0zt​≐γλzt−1​+∇v^(St​,wt​),0≤t≤T​
γ \gamma γ是折扣因子， λ \lambda λ是之前讲过的融合多个不同n-step回报的权重系数。这两个值通常来说都是小于1的，所以说会起到衰减作用。统称为迹衰减参数trace-decay parameter 。借助这个式子，资格迹就会不断记录权重向量的哪个维度对于最近的状态值函数产生了影响，这种影响是正面还是负面（由梯度项决定），这个最近主要是通过前面的迹衰减参数决定的。假设在第二步的时候梯度值为 ∇ v ^ ( S t + 2 , w t + 2 ) \nabla \hat{v}\left(S_{t+2}, \mathbf{w}_{t+2}\right) ∇v^(St+2​,wt+2​)，那么从这一步开始这个梯度信息就会一直被保存在这个资格迹向量z中，假设到了第10个状态，那么第2步梯度产生的影响就是 ( γ λ ) 8 ∇ v ^ ( S t + 2 , w t + 2 ) (\gamma\lambda)^8\nabla \hat{v}\left(S_{t+2}, \mathbf{w}_{t+2}\right) (γλ)8∇v^(St+2​,wt+2​)。

如果近似函数是线性函数，那么值函数的导数就等于特征向量，在这种情况下，资格迹向量其实就等于输入特征向量和和其衰减值的和。因此这个资格迹反映了权重向量每个维度对于当前事件的效用 ，因此资格迹也称作效用迹。
对于常规的one-step TD半梯度方法，权重更新的表达式可以表示为：
w t + 1 ≐ w t + α δ t ∇ v ^ ( S t , w t ) \mathbf{w}_{t+1} \doteq \mathbf{w}_{t}+\alpha\delta_t\nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right) wt+1​≐wt​+αδt​∇v^(St​,wt​)
其中：
δ t ≐ R t + 1 + γ v ^ ( S t + 1 , w t ) − v ^ ( S t , w t ) \mathbf{\delta}_{t} \doteq \mathbf{R}_{t+1}+\gamma \hat{v}\left(S_{t+1}, \mathbf{w}_{t}\right)- \hat{v}\left(S_{t}, \mathbf{w}_{t}\right) δt​≐Rt+1​+γv^(St+1​,wt​)−v^(St​,wt​)
在TD( λ \lambda λ)中我们使用TD error和资格迹的乘积来更新权重向量：
w t + 1 ≐ w t + α δ t z t \mathbf{w}_{t+1} \doteq \mathbf{w}_{t}+\alpha\delta_t\mathbf{z}_{t} wt+1​≐wt​+αδt​zt​
TD( λ \lambda λ)算法的伪代码如下：

主要步骤：更新资格迹向量；更新one-step TD error；更新TD error，并用资格迹更新近似值函数中的权重参数。
TD( λ \lambda λ)的反向视角
在更新权重参数w的算式中，把z展开，假设展开到 z t z_t zt​的前三步，这样我们就会发现td error会同时出现在t-3时间步以及当前时间步上。（因为td error是与z资格迹相乘的），同理，当前步的td error也会以相同的方式传递给之前的状态上。 如下示意图所示：

如果 λ \lambda λ为0，那么资格迹z就不会保存之前的信息，只保留当前的梯度信息，所以资格迹的更新就退化成了单步半梯度TD 更新，这也是为什么它叫做TD(0)。这里的0表示的是前0个状态受到TD误差的影响，当 λ \lambda λ处于0和1之间的时候，表示更多的历史状态会受到当前TD error的影响。但是距离当前时间越久远的状态影响越小。因为是衰减的。
当 λ \lambda λ为1时，此时表现得就很像带有折扣因子的MC方法，此时也叫做TD(1).
TD(1)可以看作是MC的一个推广，主要优势有以下几个方面：MC只能用于episodic任务，TD(1)可以用于折扣的continuing task；TD(1)可以在线更新，而MC必须等到一个episode结束之后才可以更新。这样有一个缺点：假设在中间某个step上选择了一个不好的动作，得到了一个低回报，但是这个动作并不会结束当前episode，所以agent还会继续执行这个不好的action，因为在一个episode的过程中是不会出现任何更新的操作的。对于TD(1)来说是可以在episode内任何的step执行更新的。因此这样的话agent就可以即时的根据当前action的好坏做出调整。
TD( λ \lambda λ)和offline λ \lambda λ算法在随机游走问题上的比较

由此可见，在步长参数较小的情况下，两者的效果是差不多的，在步长参数较大的情况下，TD( λ \lambda λ)算法的表现明显较差。这是因为TD( λ \lambda λ)算法是在线更新的，如果步长太大就会导致更新幅度很大，从而对整体的影响也很大。而offline λ \lambda λ算法是在一个episode结束之后才进行更新，所以对步长参数的敏感度比较低。
TD( λ \lambda λ)算法的收敛
对于采用线性近似函数的TD( λ \lambda λ)算法在在线策略的情况下被证明是收敛的，但是并不能收敛到具有最小误差的权重向量。而是收敛到最小权重误差的一个邻域内，这个邻域的大小取决于 λ \lambda λ值。continuing task的VE上界表达式如下：
V E ‾ ( w ∞ ) ≤ 1 − γ λ 1 − γ min ⁡ w V E ‾ ( w ) \overline{\mathrm{VE}}\left(\mathbf{w}_{\infty}\right) \leq \frac{1-\gamma \lambda}{1-\gamma} \min _{\mathbf{w}} \overline{\mathrm{VE}}(\mathbf{w}) VE(w∞​)≤1−γ1−γλ​wmin​VE(w)
λ \lambda λ为1时，线性TD( λ \lambda λ)等价于MC，这个边界值刚好是最小误差向量； λ \lambda λ为0时，边界值是最大的。实际情况中 λ \lambda λ为1表现反而最差。

3. n-step截断 λ \lambda λ回报算法

之前讲的 λ \lambda λ回报算法就是以 λ \lambda λ回报作为更新目标的半梯度方法， λ \lambda λ回报是n-step回报的加权和，对于episodic task，这个n要一直从开始直到终止状态，所以只有在一个episode结束之后才可以进行更新，这也是offline λ \lambda λ回报算法的劣势。本节的n-step 截断 λ \lambda λ回报算法可以解决这个问题。
思路很简单，既然n很大，更新需要等待很长时间，那么我们就截取其中的一段，因为越往后的回报由于受到衰减因子的作用，对当前回报的贡献也越小。截断 λ \lambda λ回报定义如下：
G t : h λ ≐ ( 1 − λ ) ∑ n = 1 h − t − 1 λ n − 1 G t : t + n + λ h − t − 1 G t : h , 0 ≤ t < h ≤ T G_{t: h}^{\lambda} \doteq(1-\lambda) \sum_{n=1}^{h-t-1} \lambda^{n-1} G_{t: t+n}+\lambda^{h-t-1} G_{t: h}, \quad 0 \leq t<h \leq T Gt:hλ​≐(1−λ)n=1∑h−t−1​λn−1Gt:t+n​+λh−t−1Gt:h​,0≤t<h≤T
与之前定义的 λ \lambda λ回报的区别在于就是把T换成了h，h是不大于T的。因为原来的offline λ \lambda λ算法是在整个episode结束之后才进行更新的，所以之前的算法中是T（结束态），当大于T时就等价与MC回报了。对于截断回报而言，h是不大于T的。

图片来自：

借助截断 λ \lambda λ回报的TD算法叫做TTD( λ \lambda λ)算法。对应的权重更新公式为：
w t + n ≐ w t + n − 1 + α [ G t : t + n λ − v ^ ( S t , w t + n − 1 ) ] ∇ v ^ ( S t , w t + n − 1 ) , 0 ≤ t < T \mathbf{w}_{t+n} \doteq \mathbf{w}_{t+n-1}+\alpha\left[G_{t: t+n}^{\lambda}-\hat{v}\left(S_{t}, \mathbf{w}_{t+n-1}\right)\right] \nabla \hat{v}\left(S_{t}, \mathbf{w}_{t+n-1}\right), \quad 0 \leq t<T wt+n​≐wt+n−1​+α[Gt:t+nλ​−v^(St​,wt+n−1​)]∇v^(St​,wt+n−1​),0≤t<T
对于截断 λ \lambda λ回报算法而言，在截断的位置就可以进行更新了，所以不需要等到episode结尾。
为了计算n-step回报，还可以增量式的计算：
G t : t + k λ = v ^ ( S t , w t − 1 ) + ∑ i = t t + k − 1 ( γ λ ) i − t δ i ′ G_{t: t+k}^{\lambda}=\hat{v}\left(S_{t}, \mathbf{w}_{t-1}\right)+\sum_{i=t}^{t+k-1}(\gamma \lambda)^{i-t} \delta_{i}^{\prime} Gt:t+kλ​=v^(St​,wt−1​)+i=t∑t+k−1​(γλ)i−tδi′​
δ t ′ ≐ R t + 1 + γ v ^ ( S t + 1 , w t ) − v ^ ( S t , w t − 1 ) \delta_{t}^{\prime} \doteq R_{t+1}+\gamma \hat{v}\left(S_{t+1}, \mathbf{w}_{t}\right)-\hat{v}\left(S_{t}, \mathbf{w}_{t-1}\right) δt′​≐Rt+1​+γv^(St+1​,wt​)−v^(St​,wt−1​)

4. 重新更新：在线 λ \lambda λ回报算法

在截断 λ \lambda λ回报中的n的选择是需要衡量的，大的n可以让算法接近offline λ \lambda λ回报的性能，小的n可以减小更新延迟，可以帮助我们尽快改变策略。那么如果想要同时获得两者的优点，我们需要以牺牲计算量为代价：在每个step中得到了新的数据之后，然后我们进行回溯更新，回溯episode中的每个step，直到该episode的起点。在此过程中我们需要保存 w 0 w_0 w0​，每次我们前进一个step，到达step j，就利用 G i : j λ , i = 0 , 1 , 2... j G_{i:j}^\lambda,i=0,1,2...j Gi:jλ​,i=0,1,2...j作为更新目标然后再次从 w 0 w_0 w0​出发更新参数，利用更新好的参数决定下一步动作。（怎么理解呢？其实就是在一个时间步中产生一个新的数据，然后就开始回溯更新，更新目标就是一个截断 λ \lambda λ回报，比如我走到了第三步，此时就从起始到第三步以截断 λ \lambda λ回报为目标更新一次，然后当我走到第四步的时候再从开始到第四步并以截断 λ \lambda λ回报为目标更新一次。）
为了区分不同step时的更新，在 w 0 h w_0^h w0h​中的上标表示的是当前进展到的step编号，下标表示的是实际执行该更新所处的时间步。对于一个episode来说，step1~3的更新表示为：
h = 1 : w 1 1 ≐ w 0 1 + α [ G 0 : 1 λ − v ^ ( S 0 , w 0 1 ) ] ∇ v ^ ( S 0 , w 0 1 ) h = 2 : w 1 2 ≐ w 0 2 + α [ G 0 : 2 λ − v ^ ( S 0 , w 0 2 ) ] ∇ v ^ ( S 0 , w 0 2 ) w 2 2 ≐ w 1 2 + α [ G 1 : 2 λ − v ^ ( S 1 , w 1 2 ) ] ∇ v ^ ( S 1 , w 1 2 ) h = 3 : w 1 3 ≐ w 0 3 + α [ G 0 : 3 λ − v ^ ( S 0 , w 0 3 ) ] ∇ v ^ ( S 0 , w 0 3 ) w 2 3 ≐ w 1 3 + α [ G 1 : 3 λ − v ^ ( S 1 , w 1 3 ) ] ∇ v ^ ( S 1 , w 1 3 ) w 3 3 ≐ w 2 3 + α [ G 2 : 3 λ − v ^ ( S 2 , w 2 3 ) ] ∇ v ^ ( S 2 , w 2 3 ) \begin{array}{c} h=1: \quad \mathbf{w}_{1}^{1} \doteq \mathbf{w}_{0}^{1}+\alpha\left[G_{0: 1}^{\lambda}-\hat{v}\left(S_{0}, \mathbf{w}_{0}^{1}\right)\right] \nabla \hat{v}\left(S_{0}, \mathbf{w}_{0}^{1}\right) \\ h=2: \quad \mathbf{w}_{1}^{2} \doteq \mathbf{w}_{0}^{2}+\alpha\left[G_{0: 2}^{\lambda}-\hat{v}\left(S_{0}, \mathbf{w}_{0}^{2}\right)\right] \nabla \hat{v}\left(S_{0}, \mathbf{w}_{0}^{2}\right) \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\mathbf{w}_{2}^{2} \doteq \mathbf{w}_{1}^{2}+\alpha\left[G_{1: 2}^{\lambda}-\hat{v}\left(S_{1}, \mathbf{w}_{1}^{2}\right)\right] \nabla \hat{v}\left(S_{1}, \mathbf{w}_{1}^{2}\right) \\ h=3: \mathbf{w}_{1}^{3} \doteq \mathbf{w}_{0}^{3}+\alpha\left[G_{0: 3}^{\lambda}-\hat{v}\left(S_{0}, \mathbf{w}_{0}^{3}\right)\right] \nabla \hat{v}\left(S_{0}, \mathbf{w}_{0}^{3}\right) \\ \;\;\;\;\;\;\;\;\;\;\;\; \mathbf{w}_{2}^{3} \doteq \mathbf{w}_{1}^{3}+\alpha\left[G_{1: 3}^{\lambda}-\hat{v}\left(S_{1}, \mathbf{w}_{1}^{3}\right)\right] \nabla \hat{v}\left(S_{1}, \mathbf{w}_{1}^{3}\right) \\\;\;\;\;\;\;\;\;\;\;\;\; \mathbf{w}_{3}^{3} \doteq \mathbf{w}_{2}^{3}+\alpha\left[G_{2: 3}^{\lambda}-\hat{v}\left(S_{2}, \mathbf{w}_{2}^{3}\right)\right] \nabla \hat{v}\left(S_{2}, \mathbf{w}_{2}^{3}\right) \end{array} h=1:w11​≐w01​+α[G0:1λ​−v^(S0​,w01​)]∇v^(S0​,w01​)h=2:w12​≐w02​+α[G0:2λ​−v^(S0​,w02​)]∇v^(S0​,w02​)w22​≐w12​+α[G1:2λ​−v^(S1​,w12​)]∇v^(S1​,w12​)h=3:w13​≐w03​+α[G0:3λ​−v^(S0​,w03​)]∇v^(S0​,w03​)w23​≐w13​+α[G1:3λ​−v^(S1​,w13​)]∇v^(S1​,w13​)w33​≐w23​+α[G2:3λ​−v^(S2​,w23​)]∇v^(S2​,w23​)​
权重更新公式为：
w t + 1 h ≐ w t h + α [ G t : h λ − v ^ ( S t , w t h ) ] ∇ v ^ ( S t , w t h ) , 0 ≤ t < h ≤ T \mathbf{w}_{t+1}^{h} \doteq \mathbf{w}_{t}^{h}+\alpha\left[G_{t: h}^{\lambda}-\hat{v}\left(S_{t}, \mathbf{w}_{t}^{h}\right)\right] \nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}^{h}\right), \quad 0 \leq t<h \leq T wt+1h​≐wth​+α[Gt:hλ​−v^(St​,wth​)]∇v^(St​,wth​),0≤t<h≤T
这个算法是完全在线的，每个step都要计算更新得到一个新的权重向量 w t w_t wt​，只利用到时间t为止的信息。该方法的计算复杂度很高，但是学习效率比离线方法好很多。

5. 真正的在线TD( λ \lambda λ)

在线方法是目前所有算法中效果最好的，但是因为计算量很大，所以可以考虑采用资格迹的方式来简化它，采用backward-view的视角，这种方法叫做真正在线TD( λ \lambda λ)算法。
推导比较复杂，可以将在线 λ \lambda λ回报算法计算权重向量列出来：
w 0 0 w 0 1 w 1 1 w 0 2 w 1 2 w 2 2 w 0 3 w 1 3 w 2 3 w 3 3 ⋮ ⋮ ⋮ ⋮ ⋱ w 0 T w 1 T w 2 T w 3 T … w T T \begin{array}{ccccc} \mathbf{w}_{0}^{0} & & & & \\ \mathbf{w}_{0}^{1} & \mathbf{w}_{1}^{1} & & & \\ \mathbf{w}_{0}^{2} & \mathbf{w}_{1}^{2} & \mathbf{w}_{2}^{2} & & \\ \mathbf{w}_{0}^{3} & \mathbf{w}_{1}^{3} & \mathbf{w}_{2}^{3} & \mathbf{w}_{3}^{3} & \\ \vdots & \vdots & \vdots & \vdots & \ddots \\ \mathbf{w}_{0}^{T} & \mathbf{w}_{1}^{T} & \mathbf{w}_{2}^{T} & \mathbf{w}_{3}^{T} & \ldots & \mathbf{w}_{T}^{T} \end{array} w00​w01​w02​w03​⋮w0T​​w11​w12​w13​⋮w1T​​w22​w23​⋮w2T​​w33​⋮w3T​​⋱…​wTT​​
上面三角形中的每列是一个时间步中算法计算得到的系数系列，实际上只需要每一行最后一个系数向量，如果我们可以根据上一行最后一个系数向量直接得到下一行最后一个系数向量（也就是当前系数向量），所以在线性情况下我们得到一个true online TD( λ \lambda λ)算法：
w t + 1 ≐ w t + α δ t z t + α ( w t ⊤ x t − w t − 1 ⊤ x t ) ( z t − x t ) \mathbf{w}_{t+1} \doteq \mathbf{w}_{t}+\alpha \delta_{t} \mathbf{z}_{t}+\alpha\left(\mathbf{w}_{t}^{\top} \mathbf{x}_{t}-\mathbf{w}_{t-1}^{\top} \mathbf{x}_{t}\right)\left(\mathbf{z}_{t}-\mathbf{x}_{t}\right) wt+1​≐wt​+αδt​zt​+α(wt⊤​xt​−wt−1⊤​xt​)(zt​−xt​)

z t ≐ γ λ z t − 1 + ( 1 − α γ λ z t − 1 ⊤ x t ) x t \mathbf{z}_{t} \doteq \gamma \lambda \mathbf{z}_{t-1}+\left(1-\alpha \gamma \lambda \mathbf{z}_{t-1}^{\top} \mathbf{x}_{t}\right) \mathbf{x}_{t} zt​≐γλzt−1​+(1−αγλzt−1⊤​xt​)xt​
算法已经被证明可以获得和online TD( λ \lambda λ)算法完全一样的权重向量序列，但是该算法需要的计算量更少，算法空间需求与传统的TD( λ \lambda λ)算法一样，但是每一步的计算量增大了大概50%，所以每一步的计算复杂度依然是O(d).

为了区分目前得到的两种资格迹，本节的方法叫做dutch trace，之前介绍的方法叫做accumulating trace。早期的工作常用一种叫做replacing trace的形式，这种形式只对表格形式/二进制编码形式tiling coding有效，定义如下：

第一个下标表示资格迹分量，第二个下标表示时间步。dutch trace比replacing trace表现好，理论依据明确。accumnulating trace则对非线性方法也适用，但是dutch trace不适用。

6. MC学习中的dutch trace

尽管资格迹在发展上与TD很密切，但实际上两者之间的联系并不是很密切，之前我们已经讲过，线性MC这种forward view算法，可以由与其等价的使用dutch trace的backward view算法代替，且计算量很低。这是本书唯一显式的说明forward view和backward view等价的例子。
具体的证明过程看书中内容即可。
主要是说明资格迹和TD没有关系，可以应用于任何想要高校学习长期的函数估计的情况。

7. Sarsa( λ \lambda λ)

本节考虑如何在动作值上应用资格迹。首先给出n-step 回报的动作值版本：
G t : t + n ≐ R t + 1 + ⋯ + γ n − 1 R t + n + γ n q ^ ( S t + n , A t + n , w t + n − 1 ) , t + n < T G_{t: t+n} \doteq R_{t+1}+\cdots+\gamma^{n-1} R_{t+n}+\gamma^{n} \hat{q}\left(S_{t+n}, A_{t+n}, \mathbf{w}_{t+n-1}\right), \quad t+n<T Gt:t+n​≐Rt+1​+⋯+γn−1Rt+n​+γnq^​(St+n​,At+n​,wt+n−1​),t+n<T
如果t+n≥T， G t : t + n ≐ G t G_{t: t+n} \doteq G_{t} Gt:t+n​≐Gt​ 。
动作值版本的offline λ回报算法更新公式：
w t + 1 ≐ w t + α [ G t λ − q ^ ( S t , A t , w t ) ] ∇ q ^ ( S t , A t , w t ) , t = 0 , … , T − 1 \mathbf{w}_{t+1} \doteq \mathbf{w}_{t}+\alpha\left[G_{t}^{\lambda}-\hat{q}\left(S_{t}, A_{t}, \mathbf{w}_{t}\right)\right] \nabla \hat{q}\left(S_{t}, A_{t}, \mathbf{w}_{t}\right), \quad t=0, \ldots, T-1 wt+1​≐wt​+α[Gtλ​−q^​(St​,At​,wt​)]∇q^​(St​,At​,wt​),t=0,…,T−1
其中 G t λ ≐ G t : ∞ λ G_{t}^{\lambda} \doteq G_{t: \infty}^{\lambda} Gtλ​≐Gt:∞λ​,下图为其对应的backdiagram，与 T D ( λ ) \mathrm{TD}(\lambda) TD(λ) 算法差不多。

动作值函数形式带有资格迹的TD算法叫做Sarsa(λ)使用forward view的形式逼近上述形式的算法。其更新形式与TD(λ)算法相同：

w t + 1 ≐ w t + α δ t z t \mathbf{w}_{t+1} \doteq \mathbf{w}_{t}+\alpha \delta_{t} \mathbf{z}_{t} wt+1​≐wt​+αδt​zt​
δ t ≐ R t + 1 + γ q ^ ( S t + 1 , A t + 1 , w t ) − q ^ ( S t , A t , w t ) \delta_{t} \doteq R_{t+1}+\gamma \hat{q}\left(S_{t+1}, A_{t+1}, \mathbf{w}_{t}\right)-\hat{q}\left(S_{t}, A_{t}, \mathbf{w}_{t}\right) δt​≐Rt+1​+γq^​(St+1​,At+1​,wt​)−q^​(St​,At​,wt​)
z − 1 ≐ 0 z t ≐ γ λ z t − 1 + ∇ q ^ ( S t , A t , w t ) , 0 ≤ t ≤ T \begin{array}{l} \mathbf{z}_{-1} \doteq \mathbf{0} \\ \mathbf{z}_{t} \doteq \gamma \lambda \mathbf{z}_{t-1}+\nabla \hat{q}\left(S_{t}, A_{t}, \mathbf{w}_{t}\right), \quad 0 \leq t \leq T \end{array} z−1​≐0zt​≐γλzt−1​+∇q^​(St​,At​,wt​),0≤t≤T​
线性函数近似形式，使用二进制特征，带有accumulating trace或replacing trace的Sarsa(λ)算法如下：

同样，也有动作值函数形式对应的online λ-return算法，以及对应的true online λ-return算法。

example:Sarsa(λ)在mountain car上的应用

不同版本的Sarsa(λ)算法在mountain car上的表现：

8. 变量λ和γ

到此为止，基本的TD learning的全部进展已经完成了。我们还可以把bootstrapping和discounting的程度改写成状态和动作的函数，并不是固定的参数，这样一来每步都有不同的λ和γ ，即 λ t \lambda_t λt​和 γ t \gamma_t γt​,定义 λ : S ∗ A → [ 0 , 1 ] \lambda:S*A \rightarrow [0,1] λ:S∗A→[0,1]是[0,1]值域的状态和动作的函数，记作 λ t ≐ λ ( S t , A t ) \lambda_t \doteq \lambda(S_t,A_t) λt​≐λ(St​,At​),定义 γ : S → [ 0 , 1 ] \gamma:S\rightarrow [0,1] γ:S→[0,1]是[0,1]值域的状态的函数，记作 γ t ≐ γ ( S t ) \gamma_t \doteq\gamma(S_t) γt​≐γ(St​),这也叫做termination function。

因此可以写出更一般的回报的定义
G t ≐ R t + 1 + γ t + 1 G t + 1 = R t + 1 + γ t + 1 R t + 2 + γ t + 1 γ t + 2 R t + 3 + γ t + 1 γ t + 2 γ t + 3 R t + 4 + ⋯ = ∑ k = t ∞ ( ∏ i = t + 1 k γ i ) R k + 1 \begin{aligned} G_{t} & \doteq R_{t+1}+\gamma_{t+1} G_{t+1} \\ &=R_{t+1}+\gamma_{t+1} R_{t+2}+\gamma_{t+1} \gamma_{t+2} R_{t+3}+\gamma_{t+1} \gamma_{t+2} \gamma_{t+3} R_{t+4}+\cdots \\ &=\sum_{k=t}^{\infty}\left(\prod_{i=t+1}^{k} \gamma_{i}\right) R_{k+1} \end{aligned} Gt​​≐Rt+1​+γt+1​Gt+1​=Rt+1​+γt+1​Rt+2​+γt+1​γt+2​Rt+3​+γt+1​γt+2​γt+3​Rt+4​+⋯=k=t∑∞​(i=t+1∏k​γi​)Rk+1​​
为了保证算法收敛，要求 ( ∏ k = t ∞ γ k = 0 ) \left(\prod_{k=t}^{\infty} \gamma_{k}=0\right) (∏k=t∞​γk​=0)对所有的t保证其成立。这种形式的好处就是对于episodic task来说不需要单独的提出起始状态和结束状态，结束状态变为了 γ ( s ) = 0 \gamma(s)=0 γ(s)=0并且转移到起始状态的状态。所以这种形式统一了episodic task和discounted-continuing。
对于自举的变量的泛化并不像discounting一样是对于问题的改变，而是对于解决策略的改变，这个泛化影响了 λ − r e t u r n \lambda-return λ−return，新的基于状态的 λ − r e t u r n \lambda-return λ−return可以写作：
G t λ s ≐ R t + 1 + γ t + 1 ( ( 1 − λ t + 1 ) v ^ ( S t + 1 , w t ) + λ t + 1 G t + 1 λ s ) G_{t}^{\lambda s} \doteq R_{t+1}+\gamma_{t+1}\left(\left(1-\lambda_{t+1}\right) \hat{v}\left(S_{t+1}, \mathbf{w}_{t}\right)+\lambda_{t+1} G_{t+1}^{\lambda_{s}}\right) Gtλs​≐Rt+1​+γt+1​((1−λt+1​)v^(St+1​,wt​)+λt+1​Gt+1λs​​)
这里的每个 λ \lambda λ都有一个状态s作为下标，这个等式表明 λ − r e t u r n \lambda-return λ−return可以有下一刻的奖励值加上第二项，第二项可能为0，第二项中有两个部分，每部分的值由其自举的程度决定，基于动作的 λ − r e t u r n \lambda-return λ−return可以写成Sarsa的形式：
G t λ a ≐ R t + 1 + γ t + 1 ( ( 1 − λ t + 1 ) q ^ ( S t + 1 , A t + 1 , w t ) + λ t + 1 G t + 1 λ a ) G_{t}^{\lambda a} \doteq R_{t+1}+\gamma_{t+1}\left(\left(1-\lambda_{t+1}\right) \hat{q}\left(S_{t+1}, A_{t+1}, \mathbf{w}_{t}\right)+\lambda_{t+1} G_{t+1}^{\lambda a}\right) Gtλa​≐Rt+1​+γt+1​((1−λt+1​)q^​(St+1​,At+1​,wt​)+λt+1​Gt+1λa​)
或者是期望Sarsa的形式：
G t λ a ≐ R t + 1 + γ t + 1 ( ( 1 − λ t + 1 ) V ˉ t ( S t + 1 ) + λ t + 1 G t + 1 λ a ) G_{t}^{\lambda a} \doteq R_{t+1}+\gamma_{t+1}\left(\left(1-\lambda_{t+1}\right) \bar{V}_{t}\left(S_{t+1}\right)+\lambda_{t+1} G_{t+1}^{\lambda a}\right) Gtλa​≐Rt+1​+γt+1​((1−λt+1​)Vˉt​(St+1​)+λt+1​Gt+1λa​)
其中
V ˉ t ( s ) ≐ ∑ a π ( a ∣ s ) q ^ ( s , a , w t ) \bar{V}_{t}(s) \doteq \sum_{a} \pi(a \mid s) \hat{q}\left(s, a, \mathbf{w}_{t}\right) Vˉt​(s)≐a∑​π(a∣s)q^​(s,a,wt​)

9. 带有控制变量的off-policy traces

这部分内容参考：

10. Watkins’s Q( λ \lambda λ) to Tree-Backup( λ \lambda λ)

有些方法尝试把Q-learning和资格迹结合起来，最初的就像Watkin’s Q( λ \lambda λ)，

该算法对于只要选择的式greedy动作就正常的衰减资格迹，否则的话就把第一个非greedy动作之后的资格迹置为0。第六章中把期望Sarsa和Q learning统一起来，第七章介绍了n-step Sarsa和n-step tree backup。本节展示的是资格迹版本的tree backup，叫做Tree-Backup( λ \lambda λ) ，简称TB( λ \lambda λ) 。

TB( λ \lambda λ)算法思想很直接，将每个长度的treebackup组合起来：
G t λ a ≐ R t + 1 + γ t + 1 ( ( 1 − λ t + 1 V ˉ t ( S t + 1 ) + λ t + 1 [ ∑ a ≠ A t + 1 π ( a ∣ S t + 1 ) q ^ ( S t + 1 , a , w t ) + π ( A t + 1 ∣ S t + 1 ) G t + 1 λ a ] ) = R t + 1 + γ t + 1 ( V ˉ t ( S t + 1 ) + λ t + 1 π ( A t + 1 ∣ S t + 1 ) ( G t + 1 λ a − q ^ ( S t + 1 , A t + 1 , w t ) ) ) \begin{aligned} G_{t}^{\lambda a} & \doteq R_{t+1}+\gamma_{t+1}\left(\left(1-\lambda_{t+1} \bar{V}_{t}\left(S_{t+1}\right)+\lambda_{t+1}\left[\sum_{a \neq A_{t+1}} \pi\left(a \mid S_{t+1}\right) \hat{q}\left(S_{t+1}, a, \mathbf{w}_{t}\right)+\pi\left(A_{t+1} \mid S_{t+1}\right) G_{t+1}^{\lambda a}\right]\right)\right.\\ &=R_{t+1}+\gamma_{t+1}\left(\bar{V}_{t}\left(S_{t+1}\right)+\lambda_{t+1} \pi\left(A_{t+1} \mid S_{t+1}\right)\left(G_{t+1}^{\lambda a}-\hat{q}\left(S_{t+1}, A_{t+1}, \mathbf{w}_{t}\right)\right)\right) \end{aligned} Gtλa​​≐Rt+1​+γt+1​⎝⎛​⎝⎛​1−λt+1​Vˉt​(St+1​)+λt+1​⎣⎡​a​=At+1​∑​π(a∣St+1​)q^​(St+1​,a,wt​)+π(At+1​∣St+1​)Gt+1λa​⎦⎤​⎠⎞​=Rt+1​+γt+1​(Vˉt​(St+1​)+λt+1​π(At+1​∣St+1​)(Gt+1λa​−q^​(St+1​,At+1​,wt​)))​
可以近似的写作TD error和的形式：
G t λ a ≈ q ^ ( S t , A t , w t ) + ∑ k = t ∞ δ k a ∏ i = t + 1 k γ i λ i π ( A i ∣ S i ) G_{t}^{\lambda a} \approx \hat{q}\left(S_{t}, A_{t}, \mathbf{w}_{t}\right)+\sum_{k=t}^{\infty} \delta_{k}^{a} \prod_{i=t+1}^{k} \gamma_{i} \lambda_{i} \pi\left(A_{i} \mid S_{i}\right) Gtλa​≈q^​(St​,At​,wt​)+k=t∑∞​δka​i=t+1∏k​γi​λi​π(Ai​∣Si​)
同样的需要更新资格迹，只不过增加了一个动作概率：
z t ≐ γ t λ t π ( A t ∣ S t ) z t − 1 + ∇ q ^ ( S t , A t , w t ) \mathbf{z}_{t} \doteq \gamma_{t} \lambda_{t} \pi\left(A_{t} \mid S_{t}\right) \mathbf{z}_{t-1}+\nabla \hat{q}\left(S_{t}, A_{t}, \mathbf{w}_{t}\right) zt​≐γt​λt​π(At​∣St​)zt−1​+∇q^​(St​,At​,wt​)

与所有的半梯度算法一样，这个算法无法保证在使用函数近似的off-policy的情形下保持稳定，下一节会给出一些保持稳定的算法。

11. 带有traces的稳定的off-policy方法

目前已经有提出了几种off-policy训练下保证稳定的资格迹方法，这些方法要么基于TD要么基于emphatic TD，所有算法假设使用线性拟合器，也有将其扩充到非线性的情形。

1.GTD( λ \lambda λ)，是TDC算法的资格迹形式。TDC算法是双状态值的Gradient-TD算法的改进版。
2.GQ算法，是Gradient-TD算法的带资格迹的动作值函数版本。
3.HTD(\lambda)算法是GTD( λ \lambda λ)和TD( λ \lambda λ)算法的状态值函数形式的混合。
4.Emphatic TD( λ \lambda λ)算法，是一步Emphatic-TD算法到资格迹的延伸。

具体内容看书或参考：

12. 实现中的问题

对于表格化方法而言，使用资格迹的方法要比one-step的算法计算上复杂的多。要求在每个step上更新估计值和资格迹，这对于单指令、多数据并行计算机或神经网络来说都不是问题，但是对于串行计算机来说问题较大。幸运的是，几乎所有状态的资格迹经常是0，只有那些最近被访问的状态才是明显大于0的迹，且只有很少状态需要更新。
实际中，只有明显大于0的迹才会被跟踪和更新，利用这个trick，在表格方法中使用资格迹的计算代价只是one-step的数倍，具体取决于参数 λ \lambda λ和 γ \gamma γ的取值。表格情形是使用资格迹最差的情形，如果使用的是函数逼近的方法，那么不使用资格迹的计算优势就小很多。比如使用神经网络和反向传播时，资格迹只会导致存储和计算代价增加一倍。

总结

资格迹与TD error结合，提供了一种高效的增量式的融合TD和MC的方式。第七章的n-step方法也有这个作用，但是资格迹方法更通用，学习速度更快，且能够保证不同程度的计算复杂度权衡。本章提到了各种资格迹算法。
在第五章我们提到，MC方法在非马尔可夫性任务下有一定优势，因为不需要bootstrasp。而资格迹方法使TD方法接近于MC方法，从而可以在这种场景下保持很好的性能。如果既需要TD方法的优点，且任务本身也带有一定的非马尔可夫性，那么资格迹方法就是一个很好的选择。资格迹方法对于长期延迟回报任务以及非马尔可夫性任务有较好的效果。
虽然资格迹方法是使TD方法接近于MC方法，但是如果使用资格迹时使其过于接近MC的话，（λ接近1），那么性能就会快速下降，所以折中参数比较好。 如下图所示：

利用资格迹的方法比one-step方法需要更多的计算，但是大大加速了学习，尤其是在reward延迟了很多步的时候，所以当数据是稀疏的或者难以重复使用时（在线应用），使用资格迹很有价值。在离线应用中，由于数据已经大量产生，此时使用资格迹就得不偿失，因为此时需要的是尽快的处理数据。