跳到主要内容

资格迹 — 一份短期记忆,把 TD 与 MC 焊成连续谱

这一章讲四件事: λ-return 怎么把所有 n-step return 加权平均; 资格迹这个短期记忆怎么用「往回喊」实现同一件事; TD(λ) 的三个实际优点;控制与离策情形的几个变体。 读完你会拿到全书机制上最优雅的一件工具——以及「λ 该调多大」的实感。

1. 定位:机制,不是参数​

书的开篇给足了地位:资格迹是强化学习的基本机制之一;几乎所有 TD 类方法(Q-learning、Sarsa)都能接上它,变得可能更高效1。它与第 07 章 n-step 的关系要说准:两者都统一 TD 与 MC,但资格迹额外给的是一个优雅的算法机制,带实打实的计算优势2。

机制本身一句话:给每个权重配一份短期记忆(资格迹 z):某权重参与生成了当前估计,它的资格就抬高一点,然后随时间衰减;衰减到零之前若发生 TD 误差,这份资格决定它分到多少更新。衰减率就是 λ∈[0,1]3。

2. 核心原理一:λ-return——先讲「想算什么」​

从「前向视角」讲起(目标是什么):n-step return 有了一整族(第 07 章),那为什么只挑一个 n?把所有 n-step return 按指数权重平均:n=1 权重最大,随 n 按 λ 的幂衰减。这个平均目标叫 λ-return4。

两个端点核对:λ=0 时全部权重压在 n=1 上——就是 TD(0) 的目标;λ=1 时全部权重压在「完整回报」上——就是蒙特卡洛5。中间值=「近处的多信、远处的少信」,和 n-step 的「中间最好」呼应(19 态随机游走上,λ 与 n 的参数扫描成绩相当,中间值同样占优)6。

3. 核心原理二:TD(λ)——「往回喊」的实现(主走查)​

前向视角有个实现障碍:n-step 的更新要等 n 步之后的数据齐(第 07 章的老问题)。资格迹给出后向视角:每步只做两件事(线性情形,更新式为书中式 12.5/12.7)7:

  ① 资格累积:z ← γλ·z + x(S)          (特征的迹抬升,旧的按 γλ 衰减)
  ② 误差广播:w ← w + α·δ·z            (δ 是本步 TD 误差,整份迹一起结算)

  主走查:三状态走廊,S1→S2→S3→终点(+10),线性特征 x=one-hot,
  γ=1,λ=0.5,α=0.1,全部 V 初始 0(演示值为演示编的,机制为书中定义)。

  走完 S1(得 R=0,到 S2):
    z = 0.5×[0,0,0] + [1,0,0] = [1,0,0]
    δ = 0 + V(S2) − V(S1) = 0 − 0 = 0          → 无更新
  走完 S2(得 R=0,到 S3):
    z = 0.5×[1,0,0] + [0,1,0] = [0.5,1,0]
    δ = 0 + 0 − 0 = 0                           → 仍无更新
  走完 S3(得 R=10,终止):
    z = 0.5×[0.5,1,0] + [0,0,1] = [0.25,0.5,1]
    δ = 10 + 0 − 0 = 10
    w ← w + 0.1×10×[0.25,0.5,1] = [ +0.25, +0.5, +1.0 ]

  一条 TD 误差,瞬间分给沿途三个状态——离终点越近分得越多(资格越高)。
  前向视角要等局终才能算的 λ-return,后向视角每一步都在实时结算。

两个视角是同一更新的两种读法:前向=「从每个状态向前看,决定它的更新」;后向=「TD 误差一来,朝所有带资格的过去状态喊回去」8。书里的比喻值得借用一次:想象自己乘着状态之流顺流而下,算出 TD 误差就朝上游喊回去,谁资格高谁听得清8。

λ 的取值手感:λ=0 时 z 就是当前特征,算法精确退回 TD(0)(这解释了 TD(0) 名字的来历);λ=1 时迹只按 γ 衰减,恰好给出蒙特卡洛式的归因9。

4. 核心原理三:相比 n-step 的三个实际优点​

书里列得很干脆10:

  1. 每步都在学,不用憋到局末——估计更早变好;
  2. 计算在时间上均匀分布,不会在局末堆积;
  3. 能用于没有回合的持续问题——MC 的地盘它也进得去。

工程上更硬的一条:一个迹向量替掉「最近 n 步的全部特征向量」;对 n-step,你要把历史存起来、局末补课;对资格迹,经验随到随算、用完即可丢弃11。

5. 变体地图(点到为止)​

  • true online TD(λ):上述「向后近似前向」其实只是近似;van Seijen 的 true online 版把迹的更新式改两行,做到与离线 λ-return 精确等价,实践也更稳——二版新收12。
  • Sarsa(λ):动作值版,迹按状态-动作特征累积;是控制问题上的主力13。
  • 离策情形:Watkins 的 Q(λ)(遇非贪心动作截断迹)到 Tree-Backup(λ)(第 07 章 tree-backup 的迹化),再到与第 11 章 Gradient-TD 结合的 GTD(λ)/GQ(λ)——离策的方差与稳定性问题在迹的世界里原样重现,解法也一样不少14。

6. 作者的判断与证据​

实验支撑的: 19 态随机游走上离线 λ-return 与 n-step 成绩相当、中间参数占优6;true online 的等价性有证明。

作者的立场: 资格迹的位置被排得极高——它能用完全不同的实现方式达到同样的更新,「说明一个学习算法有时可以换个实现方式来换计算优势」;这句方法论的话是本章真正的题眼15。二版还刻意把 n-step(前向)与资格迹(后向)拆成两章,作者在前言里说明这是为了让两套思想各自讲清——「前后向等价」这件事在 2014 年后被做得远比一版成熟16。

7. 边界与局限​

  • 「后向=前向」在线性+特定迹规则下成立(或 true online 下精确成立);非线性函数逼近下的等价性没有同样干净的结论。
  • λ 是新的超参数:它同时改偏差(bootstrap 深度)与方差(归因宽度),与 α、γ 耦合,调起来不独立。
  • 迹对「状态重复访问」敏感:同一状态反复出现,迹会叠高——折扣与衰减压得住,但机制上要知道。
  • 离策+迹的稳定性(第 10-11 章的问题)不因加迹而消失,只是多了一层实现要操心。

8. 可带走的​

  1. 资格迹=权重的短期记忆:出过力→资格抬升→随 γλ 衰减;TD 误差按资格结算。
  2. λ-return=所有 n-step 目标的指数加权平均;λ=0 即 TD(0),λ=1 即 MC——一个参数滑完整个光谱。
  3. 两个视角一个更新:前向定义「学什么」,后向定义「怎么算」;主走查里 δ=10 一瞬把 +0.25/+0.5/+1.0 沿途分账,就是全部机制。
  4. 三个实际优点:更早学、计算均匀、可上持续问题;外加内存优势(一个向量 vs 一段历史)。
  5. true online:多改两行,近似变精确等价——「同样的更新,更好的实现」的范本。
  6. 别把 λ 当玄学:它是「近因偏好」的旋钮;中间值通常最好,和 n-step 的结论互为印证。
  7. 离策的老问题(方差、致命三件套)在迹的世界原样存在,GTD(λ)/GQ(λ) 是接力点。

9. 原文地图​

主题原书章原文位置
基本机制、统一 TD/MCEligibility Tracestext/15-fm-eligibility-traces.txt:3(搜「basic mechanisms」) · text/15-fm-eligibility-traces.txt:9(搜「spectrum」)
迹的机制、λEligibility Tracestext/15-fm-eligibility-traces.txt:18(搜「bumped up」)
对 n-step 的优势Eligibility Tracestext/15-fm-eligibility-traces.txt:23(搜「single trace vector」)
前向/后向视角Eligibility Tracestext/15-fm-eligibility-traces.txt:33(搜「forward views」)
复合更新、λ-returnEligibility Tracestext/15-fm-eligibility-traces.txt:73(搜「compound update」) · text/15-fm-eligibility-traces.txt:50(搜「-return」)
λ=0/λ=1 端点Eligibility Tracestext/15-fm-eligibility-traces.txt:9(搜「one-step TD method」)
TD(λ) 地位与三优点Eligibility Tracestext/15-fm-eligibility-traces.txt:233(搜「oldest and most widely」) · text/15-fm-eligibility-traces.txt:238(搜「improves over」)
迹更新式、长短期记忆Eligibility Tracestext/15-fm-eligibility-traces.txt:254(搜「z 1 = 0」) · text/15-fm-eligibility-traces.txt:16(搜「short-term memory」)
后向视角、喊回Eligibility Tracestext/15-fm-eligibility-traces.txt:310(搜「shouting」)
λ=0 退化、λ=1 归因Eligibility Tracestext/15-fm-eligibility-traces.txt:318(搜「called TD(0)」→ 若无则搜「reduces to the one-step」) · text/15-fm-eligibility-traces.txt:326(搜「Monte Carlo behavior」)
true onlineEligibility Tracestext/15-fm-eligibility-traces.txt:581(搜「True Online」)
Sarsa(λ)Eligibility Tracestext/15-fm-eligibility-traces.txt:763(搜「Sarsa(」)
Watkins→Tree-BackupEligibility Tracestext/15-fm-eligibility-traces.txt:1296(搜「Watkins」)
GTD(λ)/GQ(λ)Eligibility Tracestext/15-fm-eligibility-traces.txt:1660(搜「GQ」)

Footnotes​

  1. 出处:「Eligibility Traces」第 3 段(text/15-fm-eligibility-traces.txt:3,搜「basic mechanisms」)。 ↩

  2. 出处:「Eligibility Traces」第 9 段(text/15-fm-eligibility-traces.txt:9,搜「spectrum」)与第 14 段(搜「algorithmic mechanism」)。 ↩

  3. 出处:「Eligibility Traces」第 18 段(text/15-fm-eligibility-traces.txt:18,搜「bumped up」)与第 21 段(搜「trace-decay parameter」)。 ↩

  4. 出处:「Eligibility Traces」第 73 段(text/15-fm-eligibility-traces.txt:73,搜「compound update」)与第 92 段(搜「-return」);权重形状(n=1 最大、按 λ 幂衰减)在第 96-98 段(搜「weight fades」)。 ↩

  5. 出处:「Eligibility Traces」第 9 段(text/15-fm-eligibility-traces.txt:9,搜「one-step TD method」)。 ↩

  6. 出处:「Eligibility Traces」第 168 段(text/15-fm-eligibility-traces.txt:168,搜「19-state random walk」)与第 176 段(搜「intermediate value」);图 12.3 的对比在第 179-206 段。 ↩ ↩2

  7. 出处:「Eligibility Traces」第 254 段(text/15-fm-eligibility-traces.txt:254,搜「z 1 = 0」)(式 12.5)与第 273 段(搜「eligibility trace」)(式 12.7);长短期记忆对照在第 247-249 段(搜「long-term memory」)。主走查的走廊与数值为演示编排。 ↩

  8. 出处:「Eligibility Traces」第 310 段(text/15-fm-eligibility-traces.txt:310,搜「shouting」)与前向视角的定义在第 208-215 段(搜「forward」)。 ↩ ↩2

  9. 出处:「Eligibility Traces」第 318 段(text/15-fm-eligibility-traces.txt:318,搜「TD(0)」)与第 337 段(搜「Monte Carlo behavior」)。 ↩

  10. 出处:「Eligibility Traces」第 238 段(text/15-fm-eligibility-traces.txt:238,搜「improves over」)。 ↩

  11. 出处:「Eligibility Traces」第 23 段(text/15-fm-eligibility-traces.txt:23,搜「single trace vector」)。 ↩

  12. 出处:「Eligibility Traces」第 581 段(text/15-fm-eligibility-traces.txt:581,搜「True Online」);出处注第 1619 段(搜「van Seijen」)。 ↩

  13. 出处:「Eligibility Traces」第 763 段(text/15-fm-eligibility-traces.txt:763,搜「Sarsa(」)。 ↩

  14. 出处:「Eligibility Traces」第 1296 段(text/15-fm-eligibility-traces.txt:1296,搜「Watkins」)与第 1660 段(搜「GQ」)。 ↩

  15. 出处:「Eligibility Traces」第 28 段(text/15-fm-eligibility-traces.txt:28,搜「different way」)。 ↩

  16. 出处:「Preface to the Second Edition」第 53 段(text/01-fm-preface-to-the-second-edition.txt:53,搜「forward-view」)。 ↩