资格迹
简介
- 资格迹将时序差分和蒙特卡洛算法统一结合起来并进行扩展，得到更有效一般的方法。
- 更优雅的算法机制：
- 引入短时记忆向量：$\textbf{z}_t \in \mathbb{R}^d$
- 长时权重向量：$\textbf{w}_t \in \mathbb{R}^d$
- 核心思想：参数$\textbf{w}_t$的一个分量参与计算并产生一个估计值时，对应的$\textbf{z}_t$分量会骤然升高，然后逐渐衰减。在资格迹归零之前若发现非零的时序差分误差，对应的长时权重向量的分量就可以得到学习，迹衰减参数$\lambda \in [0,1]$决定了迹的衰减率。
- 计算优势：只需追踪迹向量，不需要存储最近的n个特征向量；学习会持续并统一地在整个时间进行，可以在遇到一个状态后马上进行学习进行策略改进，不需要n步的延迟。
- 前向视图：更新依赖于还未发生的未来（n步时序差分算法基于n步的收益和之后的状态更新）。
- 资格迹的后向视图：往回看已访问过的状态，能得到与前向视图几乎一样的更新。
12.1 $\lambda$-回报
n步回报回顾
- n步回报为最初n步的折后收益加上n步后到达状态的折后预估价值组成：
$G_{t:t+n} \dot{=} R_{t+1} + \gamma R_{t+2}+…+ \gamma^{n-1}R_{t+n} + \gamma^{n}V_{t+n-1}(S_{t+n}, \textbf{w}_{t+n-1})$
- 复合型回报：可以使用不同n的平均n步回报作为更新目标（保证权值为1）：平均回报可以产生一系列新的算法。
${1 \over2} G_{t:t+2} + {1\over2}G_{t:t+4}$
- 复合更新：将简单的更新平均而组成的更新
- 回溯图：包括每个组成部分的单独的回溯图，上方画一道水平线，下方注明每个组成部分的权重。一个复合更新只能在它的组成部分最长的那个更新完成后完成（决定更新延迟）。
$\lambda$-回报
包括了所有可能的n步更新，每一个按比例$\lambda^{n-1}$加权，最后乘上正则项$(1-\lambda)$保证权值和为1，每多一步，权值按照$\lambda$衰减：
$G_t^\lambda \dot =(1-\lambda)\sum_{n=1}^\infin \lambda^{n-1}G_{t:t+n}$
到达终止状态后，所有的后续n步回报都为$G_t$，将终止状态之后的计算项从求和项中独立出来：
$G_t^\lambda \dot =(1-\lambda)\sum_{n=1}^{T-t-1} \lambda^{n-1}G_{t:t+n} + \lambda^{T-t-1}G_t$
- 极端情况：
- $\lambda =1$：求和项为0，剩余的为常规回报$G_t$，此时为蒙特卡洛算法。
- $\lambda =0$：回报为$G_{t:t+1}$,此时为单步时序差分算法。
离线$\lambda-$回报算法
基于$\lambda-$回报的学习算法，在回合序列的中间不会改变权值向量，在整回合结束后，才会进行整个序列的离线更新。根据半梯度准则，使用$\lambda-$回报作为更新目标：
$\mathbf{w}_{t+1}
= \mathbf w_t+\alpha[G_t^\lambda-\hat v(S_t,\mathbf w_t)]\nabla\hat v(S_t,\mathbf w_t),t=0,…,T-1$
- 本质：一种在蒙特卡洛算法与单步时序差分算法之间的平滑移动，类比第七章的n-步时序差分算法（参数由n->$\lambda$）。
- 比较：两种算法性能相当，都是在参数取中间值时取得最好的性能。
- 目前采取的所有算法理论上都是前向的：向未来的方向探索所有可能的未来的收益并决定如何最佳地结合它们。
- 在状态流中，从每一个状态往前看并决定如何更新这个状态，每次更新完一个状态，会移到下一个状态且再也不会更新之前的状态，而未来的状态会被重复地观测和处理。
练习
12.1 回报可以被递归地表示为首个收益与下一时刻回报的和（$G_t \dot= R_{t+1} +\gamma G_{t+1}$），$\lambda-$回报？
$G_{t:t+n} \dot{=} R_{t+1} + \gamma R_{t+2}+…+ \gamma^{n-1}R_{t+n} + \gamma^{n}V_{t+n-1}(S_{t+n}, \textbf{w}_{t+n-1})$
12.2 TD($\lambda$)
是第一个使用资格迹展示前向和后向视图之间关系的算法，可以看作对离线$\lambda-$回报算法的三个改进：
- 在一个回合序列的每一步更新权重向量，不是在回合结束时才更新。
- 计算平均在整个时间轴上，不仅仅是回合的结尾。
- 同时适用于持续性问题和分幕式问题。
权值向量：一个长期的记忆，整个系统的生命周期中进行积累，决定估计值。
资格迹：一个短期记忆，持续时间通常少于一个回合的长度，作用是影响权值向量。
$\textbf{z}_{-1} \dot = 0 \\ \textbf{z}_t \dot = \gamma\lambda\textbf{z}_{t-1}+\nabla\hat v(S_t,\mathbf w_t), 0 \le t \le T$
- 资格及向量被初始化为0，然后在每一步累加价值函数的梯度，并以$\gamma\lambda$衰减。
- 资格迹追踪了对最近的状态评估值作出了正或负贡献的权值向量的分量。资格迹向量可以看作是过去不断衰减的输入向量之和。本质是对之前时刻价值函数梯度的加权累加，展示了权值向量的对应分量有多少资格可以接受学习过程引起的变化。
半梯度TD($\lambda$)算法
TD($\lambda$)中，权值向量每一步的更新正比于时序差分的标量误差和资格迹：
$\delta_t\dot=R_{t+1}+\gamma\hat v(S_{t+1},\textbf{w}_t)-\hat v(S_t,\textbf{w}_t)\\
\textbf{w}_{t+1} \dot = \textbf{w}_t + \alpha \delta_t \textbf{z}_t$
- TD($\lambda$)从时间上往回看，每个时刻计算当前的时序差分误差，并根据之前状态对当前资格迹的贡献来分配它，时序差分误差和资格迹同时起作用。
分析与比较
- $\lambda =0$:t时刻的迹为该时刻状态对应的价值函数梯度，更新公式退化为：
$\textbf{w}_{t+1} \dot = \textbf{w}_t + \alpha \delta_t\nabla\hat v(S_t,\mathbf w_t)$（第九章）
表格型：TD(0)
- $\lambda =1$:资格迹的衰减与回报的衰减一样，与蒙特卡洛方法保持一致，TD(1)。
- 适用性：之前的MC局限于幕任务，TD(1)适用于带折扣的持续性任务。
- 增量式在线运行：运用到当前时刻为止的最近n步决策的信息，若在一幕中发生了特别好或特别差的事件，智能体能立刻调整智能体的行为，而MC控制只能在幕终止才能学习。
收敛性
如果更新步长随着时间的推移而减少，线性TD($\lambda$)被证明会在同轨策略情况下收敛。如9.4讨论的，根据$\lambda$收敛到最小误差附近的一个权值向量，对于一个带折扣的持续性任务：
$\overline{\mathbf{VE}}(\mathbf w_{\infin})\leq \frac{1-\gamma\lambda}{1-\gamma}\min_{\mathbf w}\overline{\mathbf{VE}}(\mathbf w)$
渐进误差不会超过$\frac{1-\gamma\lambda}{1-\gamma}$倍的最小误差，当$\lambda$接近1时，这个上界接近最小误差，但$\lambda$=1通常是个最差的选择。
练习
12.3 误差项$G_t^\lambda-\hat v(S_t,\mathbf w_t)$可以写为固定的单个$\textbf{w}$的时序差分误差$\delta_t\dot=R_{t+1}+\gamma\hat v(S_{t+1},\textbf{w}_t)-\hat v(S_t,\textbf{w}_t)$的和（类似第六章6.6式）
12.4 
12.3 n-步截断$\lambda-$回报方法
离线$\lambda-$回报需要使用到直到末尾才知道的$\lambda-$回报
推广：n-步截断$\lambda-$回报方法，对长期未来的收益依赖一定是越来越弱的，截断一定步数之后的序列，缺少的真实收益可以用估计值来代替。
- 假定数据最远只能达到未来的某个视界h，则我们可以定义当前时刻t的截断$\lambda-$回报为：
$G_{t:h}^\lambda \dot =(1-\lambda)\sum_{n=1}^{h-t-1} \lambda^{n-1}G_{t:t+n} + \lambda^{h-t-1}G_{t:h}$
截断TD($\lambda$)方法
以截断$\lambda-$回报为更新目标，将所有的k步回报（1～n）都考虑进来（之前说到的n步算法只使用了n步回报）：（没有使用到资格迹）
$\mathbf{w}_{t+n}
= \mathbf w_{t+n-1}+\alpha[G_{t:t+n}^\lambda-\hat v(S_t,\mathbf w_{t+n-1})]\nabla\hat v(S_t,\mathbf w_{t+n-1})$
练习
12.4 重做更新：在线$\lambda-$回报算法
以截断TD（$\lambda$）方法的推进：考虑截断参数n的取值？
- n应该尽量大：更接近离线$\lambda-$回报算法
- n应该比较小：更新更快，更迅速地影响后续行为
核心思想：每一步收集到新的数据增量时，回到回合的开始重做所有的更新。更新总是朝向一个n步截断$\lambda-$回报目标，但每次使用新的视界。
基础更新公式：$\mathbf{w}_{t+n}
= \mathbf w_{t+n-1}+\alpha[G_{t:t+n}^\lambda-\hat v(S_t,\mathbf w_{t+n-1})]\nabla\hat v(S_t,\mathbf w_{t+n-1})$
- 定义：$\textbf{w}_t^h$为视界为h的序列的时刻t所生成的权值，第一个权值向量$\textbf{w}_0^h$由上一幕继承而来，最后一个h=T获得的最终权值$\textbf{w}_T^T$会被传送给下一幕用作初始权值向量。
- 例子：三步更新
$h=1:\textbf{w}_1^1\dot=\textbf{w}_0^1+\alpha[G_{0:1}^\lambda-\hat v(S_0,\textbf{w}_0^1)]\nabla \hat v(S_0,\textbf{w}_0^1), \\$
$h=2:\textbf{w}_1^2\dot=\textbf{w}_0^2+\alpha[G_{0:2}^\lambda-\hat v(S_0,\textbf{w}_0^2)]\nabla \hat v(S_0,\textbf{w}_0^2), \\$
$\textbf{w}_2^2\dot=\textbf{w}_1^2+\alpha[G_{1:2}^\lambda-\hat v(S_1,\textbf{w}_1^2)]\nabla \hat v(S_1,\textbf{w}_1^2), \\$
$h=3:\textbf{w}_1^3\dot=\textbf{w}_0^3+\alpha[G_{0:3}^\lambda-\hat v(S_0,\textbf{w}_0^3)]\nabla \hat v(S_0,\textbf{w}_0^3), \\$
$\textbf{w}_2^3\dot=\textbf{w}_1^3+\alpha[G_{1:3}^\lambda-\hat v(S_1,\textbf{w}_1^3)]\nabla \hat v(S_1,\textbf{w}_1^3), \\$
$\textbf{w}_3^3\dot=\textbf{w}_2^3+\alpha[G_{2:3}^\lambda-\hat v(S_2,\textbf{w}_2^3)]\nabla \hat v(S_2,\textbf{w}_2^3), \\$
- 一般形式：在线$\lambda-$回报算法，仅仅使用时刻t获取的信息确定新的权值向量，缺点是计算非常复杂，在线算法会在回合中间进行更新，在回合结束时权值向量也获得了更多数量的有意义的更新。
$\textbf{w}_{t+1}^h\dot=\textbf{w}_{t}^h+\alpha[G_{t:h}^\lambda-\hat v(S_t,\textbf{w}_t^h)]\nabla \hat v(S_t,\textbf{w}_t^h) \\$
$\textbf{w}_t \dot=\textbf{w}_t^t$
12.5 真实的在线TD（$\lambda$）
在线$\lambda-$回报算法：计算非常复杂，能否将前向视图算法转换为利用资格迹的有效后向视图算法？
提出真实在线TD（$\lambda$）算法：一种更加“真实”的近似
计算用到的权重可以写为一个三角形，其中只有对角线上的$\textbf{w}_t^t$是真实需要的。
- 在线性逼近的情况下，$\hat v(s,\textbf{w})=\textbf{w}^{T}\textbf{x}(s)$，可以找到一种计算$\textbf{w}_t^t$的有效方式，得到真实的在线TD（$\lambda$）算法：
$\textbf{w}_{t+1}\dot=\textbf{w}_{t}+\alpha\delta_t\textbf{z}_{t}+\alpha(\textbf{w}_{t}^T\textbf{x}_{t}-\textbf{w}_{t-1}^T\textbf{x}_{t})(\textbf{z}_{t}-\textbf{x}_{t})$
- $\textbf{x}_{t}\dot=\textbf{x}(S_t)$
- $\textbf{z}_{t}\dot=\gamma\lambda\textbf{z}_{t-1}+(1-\alpha\gamma\lambda\textbf{z}_{t-1}^T\textbf{x}_{t})\textbf{x}_{t}$
这样得到的权值向量和在线$\lambda-$回报方法完全相同，但是其计算量更小，内存需求和计算复杂度都与TD（$\lambda$）相同。缺点：只针对线性函数近似情况。
这里的资格迹被称为荷兰迹，TD（$\lambda$）中的迹被称为积累迹。
12.7 Sarsa($\lambda$)
将资格迹从状态价值函数扩展到动作价值函数，只需将$\hat{v}(s, \mathbf{w})$变为$\hat{q}(s, a, \mathbf{w})$。
$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)$
$\Downarrow$
$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$
当$t+n\geq T$时，设$G_{t: t+n} \doteq G_{t}$
在离线$\lambda$回报算法的动作价值函数形式中用$\hat q$取代$\hat v$，得到
$\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)$
$\Downarrow$
$\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$
算法示意图如下：
$Sarsa(\lambda)$与$TD(\lambda)$相似，更新公式为：
$\begin{array}{l}
\mathbf{w}_{t+1} \doteq \mathbf{w}_{t}+\alpha \delta_{t} \mathbf{z}_{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) \\
\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)
\end{array}$
$TD(\lambda)$：
$\begin{array}{l}
\mathbf{w}_{t+1} \doteq \mathbf{w}_{t}+\alpha \delta_{t} \mathbf{z}_{t}\\
\delta_{t} \doteq R_{t+1}+\gamma \hat{v}\left(S_{t+1}, \mathbf{w}_{t}\right)-\hat{v}\left(S_{t}, \mathbf{w}_{t}\right)\\
\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}$
【例12.1】
展示了智能体在单幕中选择的道路，所有估计价值的初值都设为零，G目标位置的收益为正，其他所有的收益都是零。箭头分别展示了对于不同的算法，智能体到达目标后动作价值的增量。
单步法只会更新最后一个动作值，n步法会均等地更新最后的n个动作价值，资格迹法会从幕的开始不同程度地更新所有的动作价值，更新程度根据时间远近衰减。
$Sarsa(\lambda)$算法伪代码如下：
与传统的n-step Sarsa效果对比如下：
$Sarsa(\lambda)$的迹衰减自举策略在这个问题上表现出更高的学习效率。
真实在线$Sarsa(\lambda)$：采用动作价值函数特征向量$\mathbf{x}_{t}=\mathbf{x}\left(S_{t}, A_{t}\right)$代替状态价值函数特征向量$\mathbf{x}_{t}=\mathbf{x}(S_{t})$
算法比较：
12.8 变量$\lambda$和$\gamma$
将自举法和折扣的常数系数推广到依赖于状态和动作的函数。
每个时刻会有一个不同的$\lambda$和$\gamma$，用$\lambda_t$和$\gamma_t$来表示。
定义函数$\lambda: \mathcal{S} \times \mathcal{A} \rightarrow[0,1]$和$\gamma: \mathcal{S} \rightarrow[0,1]$，从而得到$\lambda_{t} \doteq \lambda\left(S_{t}, A_{t}\right), \gamma_{t} \doteq \gamma\left(S_{t}\right)$
函数$\gamma$称为终止函数，其改变了回报值：
$\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}$
为保证和是有限的，要求$\prod_{k=t}^{\infty} \gamma_{k}=0$对所有的$t$都成立。
这种形式的好处在于：幕无需制定起始状态和终止状态，只需使$\gamma(s)=0$即可。
对变量的自举法：
基于状态的$\lambda$-回报值可以被递归地写为：
$\begin{aligned}
G_{t}^{\lambda s} &=\left(1-\lambda_{t+1}\right) G_{t}+\gamma_{t+1} \lambda_{t+1} G_{t+1}^{\lambda s}+\lambda_{t+1} R_{t+1}\\
&=\left(1-\lambda_{t+1}\right)\left[R_{t+1}+\gamma_{t+1} \hat{v}\left(S_{t+1}, \mathbf{w}_{t}\right)\right]+\gamma_{t+1} \lambda_{t+1} G_{t+1}^{\lambda s}+\lambda_{t+1} R_{t+1} \\
&=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)
\end{aligned}$
$\lambda$-回报值是第一个收益值+第二项（根据$\gamma_{t+1}$来决定打多少折扣）。根据自举的程度可以分为两种情况。
有自举的情况下是状态的估计价值（$\lambda_{t+1}=0$），无自举的情况下是下一时刻的$\lambda$-回报值（$\lambda_{t+1}=1$）。
基于动作的$\lambda$-回报：
Sarsa形式：
$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)$
期望Sarsa形式：
$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)$
$\bar{V}_{t}(s) \doteq \sum_{a} \pi(a \mid s) \hat{q}\left(s, a, \mathbf{w}_{t}\right)$
12.9 带有控制变量的离轨策略资格迹
引入重要度采样，考虑带有控制变量的每次决策型重要度采样的自举法的推广。
$G_{t: h} \doteq \rho_{t}\left(R_{t+1}+\gamma G_{t+1: h}\right)+\left(1-\rho_{t}\right) V_{h-1}\left(S_{t}\right)$
$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)$
$\Downarrow$
$G_{t}^{\lambda s} \doteq \rho_{t}\left(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)\right)+\left(1-\rho_{t}\right) \hat{v}\left(S_{t}, \mathbf{w}_{t}\right)$
其中，$\rho_{t}=\frac{\pi\left(A_{t} \mid S_{t}\right)}{b\left(A_{t} \mid S_{t}\right)}$是普通的单步重要度采样率。
截断版本：
$\delta_{t}^{s}=R_{t+1}+\gamma_{t+1} \hat{v}\left(S_{t+1}, \mathbf{w}_{t}\right)-\hat{v}\left(S_{t}, \mathbf{w}_{t}\right)$
$\begin{aligned}
G_{t}^{\lambda s} & \doteq \rho_{t}\left(R_{t+1}+\gamma_{t+1}\left(\left(1-\lambda_{t+1}\right) V_{t+1}+\lambda_{t+1} G_{t+1}^{\lambda s}\right)\right)+\left(1-\rho_{t}\right) V_{t} \\
&=\rho_{t}\left(R_{t+1}+\gamma_{t+1} V_{t+1}-V_{t}+\gamma_{t+1}\left(-\lambda_{t+1} V_{t+1}+\lambda_{t+1} G_{t+1}^{\lambda s}\right)\right)+V_{t} \\
&=\rho_{t}\left(\delta_{t}^{s}+\gamma_{t+1}\left(\lambda_{t+1}\left(G_{t+1}^{\lambda s}-V_{t+1}\right)\right)\right)+V_{t} \\
&=\rho_{t}\left(\delta_{t}^{s}+\gamma_{t+1}\left(\lambda_{t+1}\left(\rho_{t+1}\left(R_{t+2}+\gamma_{t+2}\left(\left(1-\lambda_{t+2}\right) V_{t+2}+\lambda_{t+2} G_{t+2}^{\lambda s}\right)\right)+\left(1-\rho_{t+1}\right) V_{t+1}-V_{t+1}\right)\right)\right)+V_{t} \\
&=\rho_{t}\left(\delta_{t}^{s}+\gamma_{t+1}\left(\lambda_{t+1}\left(\rho_{t+1}\left(R_{t+2}+\gamma_{t+2} V_{t+2}-V_{t+1} \gamma_{t+2}\left(\lambda_{t+2}\left(G_{t+2}^{\lambda s}-V_{t+2}\right)\right)\right)\right)\right)\right)+V_{t} \\
&=\rho_{t}\left(\delta_{t}^{s}+\gamma_{t+1}\left(\lambda_{t+1}\left(\rho_{t+1}\left(\delta_{t+1}^{s}+\gamma_{t+2}\left(\lambda_{t+2}\left(G_{t+2}^{\lambda s}-V_{t+2}\right)\right)\right)\right)\right)+V_{t}\right.
\end{aligned}$
$G_{t}^{\lambda s} \approx \hat{v}\left(S_{t}, \mathbf{w}_{t}\right)+\rho_{t} \sum_{k=t}^{\infty} \delta_{k}^{s} \prod_{i=t+1}^{k} \gamma_{i} \lambda_{i} \rho_{i}$
使用前向视图更新：
$\begin{aligned}
\mathbf{w}_{t+1} &=\mathbf{w}_{t}+\alpha\left(G_{t}^{\lambda s}-\hat{v}\left(S_{t}, \mathbf{w}_{t}\right)\right) \nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right) \\
& \approx \mathbf{w}_{t}+\alpha \rho_{t}\left(\sum_{k=t}^{\infty} \delta_{k}^{s} \prod_{i=t+1}^{k} \gamma_{i} \lambda_{i} \rho_{i}\right) \nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right)
\end{aligned}$
沿着各个时刻求和的前向视图更新与沿时刻累加的后向视图更新是近似等价的。
前向视图更新：
$\begin{aligned}
\sum_{t=1}^{\infty}\left(\mathbf{w}_{t+1}-\mathbf{w}_{t}\right) & \approx \sum_{t=1}^{\infty} \sum_{k=t}^{\infty} \alpha \rho_{t} \delta_{k}^{s} \nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right) \prod_{i=t+1}^{k} \gamma_{i} \lambda_{i} \rho_{i} \\
&=\sum_{k=1}^{\infty} \sum_{t=1}^{k} \alpha \rho_{t} \nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right) \delta_{k}^{s} \prod_{i=t+1}^{k} \gamma_{i} \lambda_{i} \rho_{i} \\
&=\sum_{k=1}^{\infty} \alpha \delta_{k}^{s} \sum_{t=1}^{k} \rho_{t} \nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right) \prod_{i=t+1}^{k} \gamma_{i} \lambda_{i} \rho_{i}
\end{aligned}$
若第二个求和项写作资格迹的形式并进行增量更新，则更新式变为后向视图时序差分更新的总和形式。
即，若表达式为$k$时刻的迹，则其可由$k-1$时刻的值更新而得：
$\begin{aligned}
\mathbf{z}_{k} &=\sum_{t=1}^{k} \rho_{t} \nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right) \prod_{i=t+1}^{k} \gamma_{i} \lambda_{i} \rho_{i} \\
&=\sum_{t=1}^{k-1} \rho_{t} \nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right) \prod_{i=t+1}^{k} \gamma_{i} \lambda_{i} \rho_{i}+\rho_{k} \nabla \hat{v}\left(S_{k}, \mathbf{w}_{k}\right) \\
&=\gamma_{k} \lambda_{k} \rho_{k} \underbrace{\sum_{t=1}^{k-1} \rho_{t} \nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right) \prod_{i=t+1}^{k-1} \gamma_{i} \lambda_{i} \rho_{i}}_{\mathbf{z}_{k-1}}+\rho_{k} \nabla \hat{v}\left(S_{k}, \mathbf{w}_{k}\right) \\
&=\rho_{k}\left(\gamma_{k} \lambda_{k} \mathbf{z}_{k-1}+\nabla \hat{v}\left(S_{k}, \mathbf{w}_{k}\right)\right)
\end{aligned}$
$\mathbf{z}_{t} \doteq \rho_{t}\left(\gamma_{t} \lambda_{t} \mathbf{z}_{t-1}+\nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right)\right)$
这个资格迹和半梯度$TD(\lambda)$形成一个通用的$TD(\lambda)$算法，可以应用在同轨策略或离轨策略上。
同轨策略情况下，算法就是$TD(\lambda)$，$\rho_t$总为1。
离轨策略情况下，算法往往效果很好，但作为一种半梯度方法不能保证稳定性。
对于动作价值函数的情况与状态价值函数情况类似。
构造基于动作的$\lambda$-回报值：
$\begin{aligned}
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}\left[\rho_{t+1} G_{t+1}^{\lambda a}+\bar{V}_{t}\left(S_{t+1}\right)-\rho_{t+1} \hat{q}\left(S_{t+1}, A_{t+1}, \mathbf{w}_{t}\right)\right]\right) \\
&=R_{t+1}+\gamma_{t+1}\left(\bar{V}_{t}\left(S_{t+1}\right)+\lambda_{t+1} \rho_{t+1}\left[G_{t+1}^{\lambda a}-\hat{q}\left(S_{t+1}, A_{t+1}, \mathbf{w}_{t}\right)\right]\right)
\end{aligned}$
其中，$\bar{V}_{t}(s) \doteq \sum_{a} \pi(a \mid s) \hat{q}\left(s, a, \mathbf{w}_{t}\right)$
同样，$\lambda$-回报可以近似写作时序差分误差的总和：
$G_{t}^{\lambda a} \approx \hat{q}\left(S_{t}, A_{t}, \mathbf{w}_{t}\right)+\sum_{k=t} \delta_{k}^{a} \prod_{i=t+1}^{n} \gamma_{i} \lambda_{i} \rho_{i}$
使用基于动作的时序差分误差的期望形式：
$\delta_{t}^{a}=R_{t+1}+\gamma_{t+1} \bar{V}_{t}\left(S_{t+1}\right)-\hat{q}\left(S_{t}, A_{t}, \mathbf{w}_{t}\right)$
最后得到动作价值函数的资格迹：
$\mathbf{z}_{t} \doteq \gamma_{t} \lambda_{t} \rho_{t} \mathbf{z}_{t-1}+\nabla \hat{q}\left(S_{t}, A_{t}, \mathbf{w}_{t}\right)$
12.10 从Watkins的Q($\lambda$)到树回溯TB($\lambda$)
$Q(\lambda)$：将Q学习扩展到资格迹。只要采取贪心动作，就会以正常的方式让其资格迹衰减，然后在第一次非贪心动作后把迹缩减为零。
回溯图：
一旦到达某幕的结尾或者非贪心动作被选取，整个序列的各个分量更新都将结束。
$TB(\lambda)$：不同长度的树回溯更新都以通常的方式根据自举法参数$\lambda$进行加权。
该算法的$\lambda$-回报使用动作价值函数的递归形式：
$\begin{aligned}
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}\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) \\
&=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}$
近似写为时序差分误差的总和：
$\begin{array}{l}
\delta_{t}^{a}=R_{t+1}+\gamma_{t+1} \bar{V}_{t}\left(S_{t+1}\right)-\hat{q}\left(S_{t}, A_{t}, \mathbf{w}_{t}\right) \\
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)
\end{array}$
最后得到资格迹：
$\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)$
12.11 采用资格迹保障离轨策略方法的稳定性
$GTD(\lambda)$：TDC算法的资格迹形式
目的：学习一个参数$\mathbf{w}_{t}$，使得$\hat{v}(s, \mathbf{w}) \doteq \mathbf{w}_{t}^{\top} \mathbf{x}(s) \approx v_{\pi}(s)$
更新式：
$\begin{array}{l}
\mathbf{w}_{t+1} \doteq \mathbf{w}_{t}+\alpha \delta_{t}^{s} \mathbf{z}_{t}-\alpha \gamma_{t+1}\left(1-\lambda_{t+1}\right)\left(\mathbf{z}_{t}^{\top} \mathbf{v}_{t}\right) \mathbf{x}_{t+1} \\
\mathbf{v}_{t+1} \doteq \mathbf{v}_{t}+\beta \delta_{t}^{s} \mathbf{z}_{t}-\beta\left(\mathbf{v}_{t}^{\top} \mathbf{x}_{t}\right) \mathbf{x}_{t}
\end{array}$
$GQ(\lambda)$：梯度时序差分算法的资格迹形式
目的：学习一个参数$\mathbf{w}_{t}$，使得离轨策略数据满足$\hat{q}\left(s, a, \mathbf{w}_{t}\right) \doteq \mathbf{w}_{t}^{\top} \mathbf{x}(s, a) \approx q_{\pi}(s, a)$
更新式：
$\begin{array}{l}
\mathbf{w}_{t+1} \doteq \mathbf{w}_{t}+\alpha \delta_{t}^{a} \mathbf{z}_{t}-\alpha \gamma_{t+1}\left(1-\lambda_{t+1}\right)\left(\mathbf{z}_{t}^{\top} \mathbf{v}_{t}\right) \overline{\mathbf{x}}_{t+1} \\
\mathbf{x}_{t} \doteq \sum_{a} \pi\left(a \mid S_{t}\right) \mathbf{x}\left(S_{t}, a\right) \\
\delta_{t}^{a} \doteq R_{t+1}+\gamma_{t+1} \mathbf{w}_{t}^{\top} \overline{\mathbf{x}}_{t+1}-\mathbf{w}_{t}^{\top} \mathbf{x}_{t}
\end{array}$
$HTD(\lambda)$：$GTD(\lambda)$和$TD(\lambda)$结合
目的：$\hat{v}(s, \mathbf{w}) \doteq \mathbf{w}_{t}^{\top} \mathbf{x}(s) \approx v_{\pi}(s)$
更新式：
$\begin{aligned}
\mathbf{w}_{t+1} & \doteq \mathbf{w}_{t}+\alpha \delta_{t}^{s} \mathbf{z}_{t}+\alpha\left(\left(\mathbf{z}_{t}-\mathbf{z}_{t}^{b}\right)^{\top} \mathbf{v}_{t}\right)\left(\mathbf{x}_{t}-\gamma_{t+1} \mathbf{x}_{t+1}\right) \\
\mathbf{v}_{t+1} & \doteq \mathbf{v}_{t}+\beta \delta_{t}^{s} \mathbf{z}_{t}-\beta\left(\mathbf{z}_{t}^{b^{\top}} \mathbf{v}_{t}\right)\left(\mathbf{x}_{t}-\gamma_{t+1} \mathbf{x}_{t+1}\right), \quad \text { with } \mathbf{v}_{0} \doteq \mathbf{0} \\
\mathbf{z}_{t} & \doteq \rho_{t}\left(\gamma_{t} \lambda_{t} \mathbf{z}_{t-1}+\mathbf{x}_{t}\right), \quad \text { with } \mathbf{z}_{-1} \doteq \mathbf{0} \\
\mathbf{z}_{t}^{b} & \doteq \gamma_{t} \lambda_{t} \mathbf{z}_{t-1}^{b}+\mathbf{x}_{t}, \quad \text { with } \mathbf{z}_{-1}^{b} \doteq \mathbf{0}
\end{aligned}$
特征：是$TD(\lambda)$算法针对离轨策略学习的严格的一般化形式。如果行动策略与目标策略相同，会变得和$TD(\lambda)$一样。
强调$TD(\lambda)$：单步强调TD算法的资格迹形式
目的：$\hat{v}(s, \mathbf{w}) \doteq \mathbf{w}_{t}^{\top} \mathbf{x}(s) \approx v_{\pi}(s)$
更新式：
$\begin{array}{l}
\mathbf{w}_{t+1} \doteq \mathbf{w}_{t}+\alpha \delta_{t} \mathbf{z}_{t} \\
\delta_{t} \doteq R_{t+1}+\gamma_{t+1} \mathbf{w}_{t}^{\top} \mathbf{x}_{t+1}-\mathbf{w}_{t}^{\top} \mathbf{x}_{t} \\
\mathbf{z}_{t} \doteq \rho_{t}\left(\gamma_{t} \lambda_{t} \mathbf{z}_{t-1}+M_{t} \mathbf{x}_{t}\right), \text { with } \mathbf{z}_{-1} \doteq \mathbf{0} \\
M_{t} \doteq \lambda_{t} I_{t}+\left(1-\lambda_{t}\right) F_{t} \\
F_{t} \doteq \rho_{t-1} \gamma_{t} F_{t-1}+I_{t}, \quad \text { with } F_{0} \doteq i\left(S_{0}\right)
\end{array}$
其中， $M_t\geq0$是强调的一般形式，$F_t\geq0$被称为追随迹，$I_t\geq0$是兴趣。
12.12 实现中的问题
看起来资格迹的表格型方法比单步法复杂很多：需要在每个时间点对所有状态做更新。
实际上，绝大多数状态的资格迹都为0，只有少量最近经历过的状态的资格迹大于0，只需要做少量更新。
使用函数逼近时，不使用资格迹的计算优势会减小。