TD(lambda)

在前面的章节中，我们学过了TD(0)：只往前看一步就进行更新。我们也学过MC：等到整个episode结束后才更新。这两种方法分别代表了两个极端。本章的核心问题是：有没有一种方法，能够在这两个极端之间平滑地过渡？ 答案就是TD(lambda)，它通过资格迹（Eligibility Traces）这一机制，将TD(0)和MC统一在一个框架下。

从n-step到lambda-return

n-step Return回顾

在TD(0)中，我们用一步的bootstrapping来构造目标值：

\[ G_t^{(1)} = R_{t+1} + \gamma \hat{v}(S_{t+1}, \mathbf{w}) \]

自然地，我们可以推广到\(n\)步：

\[ G_t^{(n)} = R_{t+1} + \gamma R_{t+2} + \dots + \gamma^{n-1} R_{t+n} + \gamma^n \hat{v}(S_{t+n}, \mathbf{w}) \]

即：前\(n\)步用真实奖励，第\(n+1\)步开始用估计值。当\(n \to \infty\)（一直到episode结束），\(G_t^{(\infty)} = G_t\)，这就退化成了MC。

不同的\(n\)值在不同的任务上表现各异。有时候\(n=1\)（TD(0)）最好，有时候\(n=4\)或\(n=8\)更好。那么，能不能同时利用所有的\(n\)-step return呢？

lambda-return的定义

lambda-return的核心思想是：对所有\(n\)-step return进行加权平均，权重按照几何级数递减：

\[ G_t^\lambda = (1 - \lambda) \sum_{n=1}^{\infty} \lambda^{n-1} G_t^{(n)} \]

其中\(\lambda \in [0, 1]\)。系数\((1-\lambda)\)是一个归一化常数，保证所有权重之和为1：

\[ (1-\lambda)(1 + \lambda + \lambda^2 + \dots) = (1-\lambda) \cdot \frac{1}{1-\lambda} = 1 \]

直观理解：

\(G_t^{(1)}\)（1-step return）的权重是\((1-\lambda)\)
\(G_t^{(2)}\)（2-step return）的权重是\((1-\lambda)\lambda\)
\(G_t^{(3)}\)（3-step return）的权重是\((1-\lambda)\lambda^2\)
...以此类推，权重指数衰减

lambda的含义

\(\lambda\)是一个控制"看多远"的旋钮：

\(\lambda = 0\)：所有权重集中在\(G_t^{(1)}\)上，\(G_t^0 = G_t^{(1)} = R_{t+1} + \gamma \hat{v}(S_{t+1})\)。这就是TD(0)。
\(\lambda = 1\)：权重均匀扩散到无穷远，\(G_t^1 = G_t\)（完整的MC回报）。这就是蒙特卡洛。
\(0 < \lambda < 1\)：介于TD(0)和MC之间，是两者的折中。短期的\(n\)-step return权重大，长期的权重小。

实践中常用的\(\lambda\)值在0.8到0.95之间。较大的\(\lambda\)意味着更依赖真实回报（低偏差、高方差），较小的\(\lambda\)意味着更依赖bootstrapping（高偏差、低方差）。

资格迹 (Eligibility Traces)

lambda-return在概念上非常优美，但直接计算\(G_t^\lambda\)需要知道未来所有的奖励，这和MC一样需要等到episode结束。资格迹提供了一种在线、逐步更新的方式来实现等价的效果。

资格迹的核心思想是：为每个状态（或每个参数分量）维护一个额外的变量\(\mathbf{e}_t\)，用来记录"该状态最近被访问过的频率和时间"。一个状态如果刚被访问过，它的资格迹就很高，说明它对当前的TD Error有很大的"责任"；随着时间推移，资格迹会逐渐衰减。

累积迹 (Accumulating Traces)

最基本的资格迹形式。每一步更新规则为：

\[ \mathbf{e}_t = \gamma \lambda \mathbf{e}_{t-1} + \nabla_\mathbf{w} \hat{v}(S_t, \mathbf{w}_t) \]

初始值\(\mathbf{e}_0 = \mathbf{0}\)。

这个公式的含义：

\(\gamma \lambda \mathbf{e}_{t-1}\)：旧的资格迹按\(\gamma\lambda\)的比率衰减。\(\gamma\)来自折扣因子，\(\lambda\)来自lambda-return的权重衰减。两者相乘意味着：越久远的访问，影响越小。
\(\nabla_\mathbf{w} \hat{v}(S_t, \mathbf{w}_t)\)：当前状态的梯度被"累加"到资格迹上。如果同一个状态被反复访问，它的资格迹会越来越大。

在表格情况下（每个状态一个独立参数），累积迹简化为：

\[ e_t(s) = \begin{cases} \gamma \lambda \, e_{t-1}(s) + 1 & \text{if } s = S_t \\ \gamma \lambda \, e_{t-1}(s) & \text{if } s \neq S_t \end{cases} \]

替换迹 (Replacing Traces)

替换迹的思路是：当一个状态被再次访问时，不累加，而是直接将资格迹重置为1：

\[ e_t(s) = \begin{cases} 1 & \text{if } s = S_t \\ \gamma \lambda \, e_{t-1}(s) & \text{if } s \neq S_t \end{cases} \]

替换迹在某些问题上比累积迹表现更好，因为它避免了资格迹因多次访问而变得过大。直觉上，当你反复访问同一个状态时，更合理的做法是"重新开始计时"，而不是"叠加信用"。

荷兰迹 (Dutch Traces)

荷兰迹是一种更高效的资格迹实现方式，由Hado van Hasselt和Marco Wiering提出。它的更新规则为：

\[ \mathbf{e}_t = \gamma \lambda \mathbf{e}_{t-1} + (1 - \alpha \gamma \lambda \, \mathbf{e}_{t-1}^\top \mathbf{x}_t) \mathbf{x}_t \]

其中\(\mathbf{x}_t = \mathbf{x}(S_t)\)是当前状态的特征向量，\(\alpha\)是学习率。

荷兰迹的主要优势在于计算效率：在线性函数近似下，使用荷兰迹的TD(lambda)算法可以做到与离线lambda-return算法精确等价（而不仅仅是近似等价），同时保持在线更新的计算效率。

TD(lambda)算法

前向视角 (Forward View) - lambda-return

前向视角直接使用lambda-return作为更新目标：

\[ \mathbf{w}_{t+1} = \mathbf{w}_t + \alpha [G_t^\lambda - \hat{v}(S_t, \mathbf{w}_t)] \nabla_\mathbf{w} \hat{v}(S_t, \mathbf{w}_t) \]

"前向"的含义是：站在时刻\(t\)，向前看（看未来），把未来所有的奖励信息汇总成\(G_t^\lambda\)，然后用它来更新当前状态的价值。

前向视角的问题在于：计算\(G_t^\lambda\)需要知道从\(t\)开始到episode结束的所有奖励，所以它本质上是一个离线算法——必须等episode结束才能计算。

后向视角 (Backward View) - Eligibility Traces

后向视角使用资格迹来实现等价的更新：

\[ \delta_t = R_{t+1} + \gamma \hat{v}(S_{t+1}, \mathbf{w}_t) - \hat{v}(S_t, \mathbf{w}_t) \]

\[ \mathbf{e}_t = \gamma \lambda \mathbf{e}_{t-1} + \nabla_\mathbf{w} \hat{v}(S_t, \mathbf{w}_t) \]

\[ \mathbf{w}_{t+1} = \mathbf{w}_t + \alpha \delta_t \mathbf{e}_t \]

"后向"的含义是：当产生一个TD Error \(\delta_t\)时，向后看（看过去），根据资格迹把这个误差分配给所有最近访问过的状态。资格迹高的状态分到的误差多，资格迹低的状态分到的误差少。

后向视角的巨大优势在于：它是一个在线算法，每走一步就可以立即更新，不需要等episode结束。

前向与后向的等价性

这是TD(lambda)理论中最核心的结论之一：

在线性函数近似下，前向视角（lambda-return算法）和后向视角（TD(lambda)算法）在整个episode结束时产生的参数更新总量是完全相等的。

即：如果我们把后向视角每一步的增量更新全部加起来，结果等于前向视角在episode结束时的批量更新。

这个等价性的意义在于：我们用前向视角来理解算法的目标（我们在优化lambda-return），用后向视角来实现算法的计算（在线、高效、逐步更新）。

Sarsa(lambda)

将TD(lambda)从预测问题推广到控制问题，就得到了Sarsa(lambda)。

算法伪代码

初始化参数向量 w, 资格迹向量 e = 0
对每个episode:
    初始化状态 S, 选择动作 A (epsilon-greedy)
    对每一步:
        执行动作 A, 观察 R, S'
        选择动作 A' (epsilon-greedy based on q_hat(S', ., w))

        计算TD Error:
            delta = R + gamma * q_hat(S', A', w) - q_hat(S, A, w)
            (若S'是终止状态, 则 delta = R - q_hat(S, A, w))

        更新资格迹:
            e = gamma * lambda * e + grad_w q_hat(S, A, w)

        更新参数:
            w = w + alpha * delta * e

        S <- S', A <- A'

        若S'是终止状态, 退出循环

    重置资格迹 e = 0

与普通SARSA的区别在于：每一步的TD Error不仅仅更新当前的\((S, A)\)对应的参数，而是通过资格迹\(\mathbf{e}\)把误差"广播"给所有最近访问过的状态-动作对。

类似地，可以将Q-learning与资格迹结合，得到Watkins's Q(lambda)。但由于Q-learning是off-policy方法，与资格迹的结合在理论上更加复杂（涉及Deadly Triad的问题）。

实践建议

lambda的选择

\(\lambda\)的最优值取决于具体任务，但有一些经验法则：

\(\lambda = 0\)（TD(0)）：偏差最高、方差最低。适合奖励密集、状态表示精确的任务。
\(\lambda = 1\)（MC）：偏差最低、方差最高。适合奖励稀疏、episode较短的任务。
\(\lambda \in [0.8, 0.95]\)：实践中往往是最好的选择。比如Sutton的Mountain Car实验中，\(\lambda = 0.9\)左右通常优于两个极端。

一个实用的调参策略是从\(\lambda = 0.9\)开始，如果方差太大就降低，如果学习太慢就提高。

与n-step TD的对比

特性	n-step TD	TD(lambda)
超参数	\(n\)（离散整数）	\(\lambda\)（连续实数）
多步信息	只使用\(n\)步的return	加权平均所有\(n\)-step return
实现方式	需要存储\(n\)步的转移	资格迹，只需额外一个向量
计算效率	每步更新一个状态	每步更新所有"有资格"的状态
理论性质	是lambda-return的特例	更一般的框架

TD(lambda)可以被看作n-step TD的"软"版本：n-step TD在某一个\(n\)值上集中所有权重，而TD(lambda)则把权重平滑地分散到所有可能的\(n\)值上。这种平滑化往往能带来更稳定的学习。

资格迹的直觉

资格迹可以用一个生活中的比喻来理解：

假设你训练一只猫，猫做了一连串动作（跳上桌子、打翻杯子、跑到厨房），然后你发现地上的水渍后给了猫一个惩罚。猫应该把这个惩罚归咎于哪个动作？

TD(0)只惩罚最近的动作（跑到厨房）——这显然不合理
MC平均分配到所有动作——但跳上桌子可能是无辜的
TD(lambda)按照时间远近分配：打翻杯子（最近相关动作）受到最大惩罚，其他动作按时间远近依次递减

这就是资格迹的精髓：它是一种信用分配（Credit Assignment） 的机制，根据时间距离来分配"功过"。

数学直觉：为什么gamma*lambda是衰减因子

在资格迹的更新公式中，衰减因子是\(\gamma \lambda\)而非单独的\(\gamma\)或\(\lambda\)。这两个因素各自承担了不同的职责：

\(\gamma\)来自价值函数的折扣：未来的奖励本身就应该被打折，距离越远折扣越多
\(\lambda\)来自lambda-return的几何权重：我们选择给短期n-step return更大的权重

两者相乘意味着：一个状态的"资格"会以\(\gamma\lambda\)的速度指数衰减。如果\(\gamma = 0.99\)，\(\lambda = 0.9\)，那么每一步的衰减率就是\(0.891\)。10步之前访问过的状态，其资格迹衰减到约\(0.891^{10} \approx 0.32\)，即只保留了约三分之一的"信用"。

这也解释了为什么TD(lambda)在两个极端下退化：

\(\lambda = 0\)时，\(\gamma \lambda = 0\)，资格迹在每一步都完全清零，只有当前状态的资格迹不为零。效果等价于TD(0)——只更新刚刚访问的状态。
\(\lambda = 1\)时，\(\gamma \lambda = \gamma\)，资格迹的衰减速度等于折扣因子的衰减速度。在episode结束时回头看，每个状态分到的信用恰好与MC方法中该状态对\(G_t\)的贡献成正比。

总结

TD(lambda)是连接TD(0)和MC的桥梁，提供了在偏差-方差谱上平滑移动的能力：

\[ \text{TD(0)} \xleftarrow{\lambda = 0} \text{TD}(\lambda) \xrightarrow{\lambda = 1} \text{MC} \]

核心要点：

lambda-return是所有n-step return的几何加权平均，提供了比单一n-step更稳健的目标值
资格迹是lambda-return的在线实现机制，通过维护一个衰减的"记忆向量"来追踪每个状态的信用
前向视角和后向视角在数学上是等价的，前者用于理解目标，后者用于高效实现
\(\lambda\)的选择本质上是偏差-方差权衡：小\(\lambda\)偏向bootstrapping（低方差、高偏差），大\(\lambda\)偏向MC采样（高方差、低偏差）