跳到主要内容

时序差分 — 等一秒就学,拿猜测校准猜测

这一章讲四件事: TD 误差这个量怎么把「学习时机」从局末提前到下一步; 为什么「目标里含自己的估计」不碍事(batch 之下 TD 与 MC 各自收敛到什么); 三个控制算法的分工与性格差异(悬崖行走实验); 以及「挑最大值」这个动作自带的系统性偏差与解药。 原书前言明说:第 6 章是全书对主题、对其余各章都最重要的一章1。

1. 开篇定调​

作者的定位原话:若要挑一个核心且新颖的想法作为强化学习的代表,非时序差分(TD)莫属2。它的身世一句话说完:MC 的采样 + DP 的 bootstrapping——像 MC 一样直接从原始经验学、不要模型;像 DP 一样拿别的估计来更新当前估计,不等最终结果3。

2. 核心原理一:TD(0) 与 TD 误差(主走查的机制)​

MC 的更新模板(第 02 章那个形状)里,「目标」是完整回报 G(t)——必须等局终才知道。TD 只把目标换掉:用「下一步的奖励 + 下一步状态的当前估计值」当目标。这一换,学习时机从局末提前到下一步:

  V(S(t)) ← V(S(t)) + α·[ R(t+1) + V(S(t+1)) − V(S(t)) ]
                              └────── 这就是 TD 误差 δ ──────┘

  δ(t) = R(t+1) + γ·V(S(t+1)) − V(S(t))

主走查:开车回家(书里的例 6.1,表格里的时间与预测值全部取自书)4。每天下班你预测「到家还要多久」,沿途随路况一路修正。周五那次:

时刻状态预测的总时长
离开办公室周五 6 点30 分钟
到车库,开始下雨40
下高速,一路顺畅35
次干道,被卡车堵住40
转进家门那条街43
到家43(真值)

MC 怎么处理: 必须到家后才知道真值 43,才回头把每格预测往 43 挪——比如「下高速」那格按 α=0.5 修正 (43−35)/2=+4 分钟。缺点:堵在高速上的时候,你明明已经知道「30 分钟」太乐观了,MC 也按住不表,因为「真回报」还没出来5。

TD 怎么处理: 每往前走一段,立刻把上一格的预测朝这一格的预测挪。刚上高速发现下雨、预测改成 40,就把出发时那格的 30 立刻往 40 方向拉——哪怕还没到家。每次修正量正比于预测随时间的变化量,「时序差分」由此得名6。

把 δ 的身世看清楚:MC 的目标 G(t) 是「真回报的一个样本」;TD 的目标 R(t+1)+γV(S(t+1)) 是「期望回报的一个样本」——两头都带估计,因为 V 那一项本来就是猜的。作者总结:TD=MC 的采样 + DP 的 bootstrapping3;DP 的更新叫期望更新,TD 与 MC 的都叫样本更新(只看一个抽样的后继)7。

一条值得记住的恒等式:当 V 不变时,MC 的误差恰好等于一局 TD 误差之和(带折扣权重)8——两个方法看的其实是同一份信息的两种读法。

3. 核心原理二:拿猜测校准猜测,行吗?​

TD 的「目标里有自己的估计」听着像循环论证,书里用「成堆重刷」——把攒下的全部经验反复喂给算法,直到结果稳定——把它钉死:

  • 成堆重刷的 MC 收敛到「在这堆经验上均方误差最小」的估计;
  • 成堆重刷的 TD(0) 收敛到确定性等价(certainty-equivalence)估计——先从数据建一个最大似然(让观测数据出现概率最大)的环境模型,再假设模型绝对可靠去算值9。

书里给了个五分钟能做完的思想实验(数字全部来自书)10:你观测到 8 条经验,其中 1 条是「A→B→(0) 结束」,7 条是「B→(结束)」——6 次得 1、1 次得 0(合计见书:六次 1、两次 0)。问 V(A)、V(B)?

  V(B):8 次经过 B,6 次回报 1、2 次回报 0 → 6/8 = 3/4。两家答案一致。

  V(A):只被访问过 1 次,其后回报 0。
    MC 的答案:V(A) = 0(训练集上误差恰为 0,完美拟合已知数据)
    TD 的答案:V(A) = 3/4 —— 因为 A 百分之百通向 B,
               而 B 值 3/4;「A 之后的世界」就该照 B 算。

哪个对?书里的回答:若过程真是 Markov 的,TD 的答案在未来数据上误差更小——尽管 MC 的答案在已有数据上更完美10。这正是 TD 通常学得更快的深层原因;而确定性等价解直接算是 O(n²) 内存、O(n³) 计算,TD 用 O(n) 的内存就把同一个解「流式」逼近出来——作者说这在大状态空间里可能是唯一的可行之路11。

在线情形谁更快?书里如实写:没有人在数学上证明过谁更快,连「怎么问才算问得对」都还没有定论;只是实验上(5 状态随机游走,真值 1/6…5/6)TD 一致占优12。

4. 核心原理三:三个控制算法​

把「状态→状态」的 TD 换成「状态-动作→状态-动作」,就得到控制算法。三个主角,一张表看清分工:

SarsaQ-learningExpected Sarsa
更新目标R + γ·Q(S′,实际选的A′)R + γ·maxQ(S′,·)R + γ·**Σπ·**Q(S′,·)
类型on-policyoff-policy都可
学习的是什么自己正在走的(含探索)策略的值直接逼近 q*,与所走策略无关目标策略的期望
  • Sarsa 的名字来自一次转移的五元组 (S(t), A(t), R(t+1), S(t+1), A(t+1))——五个字母连读13。它学的是「包括探索在内、我真实走法」的值。书里另给风中网格:ε=0.1、α=0.5 下 8000 步后贪心策略已最优,带探索平均约 17 步(最短 15)14。
  • Q-learning 是这个领域的早期突破(Watkins 1989):学到的 Q 直接近似最优动作值 q*,不管你实际怎么乱走——条件只有一条:每个状态-动作对持续被访问15。
  • Expected Sarsa 用「下一动作按策略的期望」替代 max 或实际抽样;它消除了抽样 A′ 带来的方差,书里的结论相当直白:它涵盖并推广了 Q-learning,同时稳定地胜过 Sarsa;除了一点额外计算,它可能全面压制另外两个16。

三种性格,悬崖见分晓(书里的悬崖行走实验:起点到终点之间是惩罚 −100 的悬崖,其余每步 −1;ε=0.1)17:

  好走的路(贴着悬崖边,最短)          安全的路(绕上面一格,更长)
  S →→→→→→→→→→→ G                    S ─┐
      ↑ 摔下去 = −100 并回起点          └──────→ G
                                        (多走几步,但 ε 乱动也不致命)

  Q-learning:学到的是贴崖最优路径的值 → 在线表现差:ε 乱动时不时摔下去
  Sarsa:     学到的是「连探索一起算」的值 → 绕远但安全的路,在线累计奖励更高

书里的解读一锤定音:Q-learning 学的是最优策略的值,在线表现却更差;若把 ε 逐渐降到零,两者最终都收敛到最优——区别全在「带着探索生活」的阶段17。

5. 核心原理四:max 自带正偏,备份解药​

只要更新目标里有 max,Q-learning 这类算法就有一个系统性的毛病:估计值的最大值,系统性地高于真值的最大值(估计有噪声,有高有低,挑最大专挑高的)。书里称之为最大化偏差18。

实验(数字来自书):状态 A 有左右两选,右边直接结束、回报 0;左边进 B,B 里一堆动作的回报都服从均值 0.1、方差 1 的噪声分布——左边真实期望 0.1,严格更好。但 Q-learning 初期强烈偏爱左:因为 B 的若干估计里总有被噪声抬高的,max 一挑就虚高。哪怕到收敛,Q-learning 选左的比例仍比最优多出约 5%(ε=0.1、α=0.1 时)19。

解法朴素到可爱:两套估计互相检查。Q1 负责挑动作,Q2 负责给挑中的动作估值——「由 Q1 挑出的动作,在 Q2 眼里值多少」是无偏的;每步掷硬币决定更新哪一套。这就是 Double Q-learning:内存翻倍,每步计算不变20。

6. 作者的判断与证据​

实验支撑的: 随机游走上 TD 一致优于 MC、悬崖行走的行为差异、Double Q-learning 几乎不受最大化偏差影响(1 万次平均)——全是书里的实验数据121719。

作者的立场: 「本章的方法是当今使用最广的强化学习方法」,并解释原因——能在线、计算极少、几行代码;但随后的扩展会稍复杂也更强21。另一个容易被放过的立场:TD 不只是 RL 的算法,它是对动态系统做长程预测的一般方法(金融、天气、选举……),作者明说这些应用「尚未被充分探索」22。

书里坦白的: 哪个学得快没有证明(见第 3 节);TD(0) 的收敛保证只对表格(及部分线性——最简单的一类函数逼近)情形成立——后文(第 10 章)会看到超出这些条件的代价。

7. 边界与局限​

  • 策略依存:Sarsa 学的是「当前含探索的策略」的值;想要最优策略的值,得靠 Q-learning——而它又自带最大化偏差(第 5 节)。
  • 收敛条件:三个算法都要求每对状态-动作被无限次访问、步长满足随机逼近条件;表格之外没有一般保证。
  • one-step 的短视:单步更新的信息传播速度受限于时间步本身(「时间步的暴政」,下一章的议题)。
  • afterstates 等特殊情形:某些任务(棋类走完后的局面)天然的评估对象既非状态值也非动作值,本书用「afterstate 值函数」变通处理——框架不是万能模板23。

8. 可带走的​

  1. TD=更早的学习时机:目标从「整局回报」换成「一步奖励+下一步估计」,等一秒就能学。
  2. δ(TD 误差)是全书的主角:第 12 章的资格迹、第 15 章的多巴胺,都是围绕这一个数做文章。
  3. 开车回家的表:预测随路段滚动修正;MC 等到家、TD 当场改口——「时序差分」=预测的变化量。
  4. A→B 之争:TD 信任「A 之后照 B 算」(模型式外推),MC 只认手里那批经验;Markov 世界里 TD 的答案更准。
  5. Sarsa/Q-learning/Expected Sarsa 的分工:学自己走的 / 学最优的 / 都学且更稳;悬崖上,Sarsa 在线更抗摔。
  6. max 有正偏:挑过的估计总偏高;两套估计交叉验证(Double Q)即解,内存翻倍计算不翻。
  7. 「拿猜测校准猜测」是被证明站得住的(表格情形)——但它的证明边界之外,就是第 10 章「致命三件套」的地雷区。
  8. 今天最常用的 RL 算法就诞生于本章;读懂 TD(0) 的那行更新式,后面每一章都是它的变奏。

9. 原文地图​

主题原书章原文位置
核心且新颖;MC+DP 合体Temporal-Difference Learningtext/09-fm-temporal-difference-learning.txt:3(搜「central and novel」) · text/09-fm-temporal-difference-learning.txt:8(搜「they bootstrap」)
TD(0) 更新式、目标对比Temporal-Difference Learningtext/09-fm-temporal-difference-learning.txt:41(搜「one-step TD」) · text/09-fm-temporal-difference-learning.txt:40(搜「target for the TD update」)
采样+bootstrapping;样本更新Temporal-Difference Learningtext/09-fm-temporal-difference-learning.txt:74(搜「combine the sampling」) · text/09-fm-temporal-difference-learning.txt:83(搜「Sample updates」)
TD 误差Temporal-Difference Learningtext/09-fm-temporal-difference-learning.txt:92(搜「TD error」)
开车回家Temporal-Difference Learningtext/09-fm-temporal-difference-learning.txt:124(搜「Driving Home」) · text/09-fm-temporal-difference-learning.txt:136(搜「Predicted」) · text/09-fm-temporal-difference-learning.txt:195(搜「learn immediately」)
MC 误差=TD 误差之和Temporal-Difference Learningtext/09-fm-temporal-difference-learning.txt:101(搜「sum of TD errors」)
优势、在线增量Temporal-Difference Learningtext/09-fm-temporal-difference-learning.txt:226(搜「online, fully incremental」)
谁更快无定论;随机游走Temporal-Difference Learningtext/09-fm-temporal-difference-learning.txt:248(搜「open question」) · text/09-fm-temporal-difference-learning.txt:255(搜「Random Walk」) · text/09-fm-temporal-difference-learning.txt:306(搜「consistently better」)
批量更新、certainty-equivalenceTemporal-Difference Learningtext/09-fm-temporal-difference-learning.txt:333(搜「batch updating」) · text/09-fm-temporal-difference-learning.txt:418(搜「certainty-equivalence」)
A→B 思想实验Temporal-Difference Learningtext/09-fm-temporal-difference-learning.txt:372(搜「You are the Predictor」) · text/09-fm-temporal-difference-learning.txt:405(搜「future data」)
O(n²)/O(n³) 对照Temporal-Difference Learningtext/09-fm-temporal-difference-learning.txt:437(搜「striking」)
Sarsa 五元组Temporal-Difference Learningtext/09-fm-temporal-difference-learning.txt:471(搜「quintuple」)
风中网格Temporal-Difference Learningtext/09-fm-temporal-difference-learning.txt:504(搜「Windy Gridworld」) · text/09-fm-temporal-difference-learning.txt:529(搜「17 steps」)
Q-learningTemporal-Difference Learningtext/09-fm-temporal-difference-learning.txt:552(搜「early breakthroughs」) · text/09-fm-temporal-difference-learning.txt:559(搜「independent of the policy being followed」)
悬崖行走Temporal-Difference Learningtext/09-fm-temporal-difference-learning.txt:588(搜「Cliff Walking」) · text/09-fm-temporal-difference-learning.txt:626(搜「safer path」) · text/09-fm-temporal-difference-learning.txt:633(搜「asymptotically converge」)
Expected SarsaTemporal-Difference Learningtext/09-fm-temporal-difference-learning.txt:786(搜「dominate both」) · text/09-fm-temporal-difference-learning.txt:776(搜「safely set」)
最大化偏差Temporal-Difference Learningtext/09-fm-temporal-difference-learning.txt:798(搜「maximization bias」) · text/09-fm-temporal-difference-learning.txt:834(搜「favor left」)
double learningTemporal-Difference Learningtext/09-fm-temporal-difference-learning.txt:852(搜「double learning」) · text/09-fm-temporal-difference-learning.txt:853(搜「doubles the memory」)
最常用;一般预测方法Temporal-Difference Learningtext/09-fm-temporal-difference-learning.txt:958(搜「most widely used」) · text/09-fm-temporal-difference-learning.txt:974(搜「long-term predictions」)

Footnotes​

  1. 出处:「Preface to the Second Edition」第 75 段(text/01-fm-preface-to-the-second-edition.txt:75,搜「Chapter 6 is the most」)。原文:「Chapter 6 is the most important for the subject and for the rest of the book」。 ↩

  2. 出处:「Temporal-Difference Learning」第 3 段(text/09-fm-temporal-difference-learning.txt:3,搜「central and novel」)。 ↩

  3. 出处:「Temporal-Difference Learning」第 8 段(text/09-fm-temporal-difference-learning.txt:8,搜「they bootstrap」)与第 77 段(搜「combine the sampling」)。 ↩ ↩2

  4. 出处:「Temporal-Difference Learning」第 124 段(text/09-fm-temporal-difference-learning.txt:124,搜「Driving Home」);时刻与预测表在第 136-143 段(搜「Predicted」)。 ↩

  5. 出处:「Temporal-Difference Learning」第 192 段(text/09-fm-temporal-difference-learning.txt:192,搜「must you wait」)与第 195 段(搜「learn immediately」);α=1/2 的四分钟例子在第 156 段(搜「four minutes」)。 ↩

  6. 出处:「Temporal-Difference Learning」第 200 段(text/09-fm-temporal-difference-learning.txt:200,搜「temporal differences in predictions」)。 ↩

  7. 出处:「Temporal-Difference Learning」第 83 段(text/09-fm-temporal-difference-learning.txt:83,搜「Sample updates」)。 ↩

  8. 出处:「Temporal-Difference Learning」第 101 段(text/09-fm-temporal-difference-learning.txt:101,搜「sum of TD errors」)。 ↩

  9. 出处:「Temporal-Difference Learning」第 333 段(text/09-fm-temporal-difference-learning.txt:333,搜「batch updating」)与第 418 段(搜「certainty-equivalence」)。 ↩

  10. 出处:「Temporal-Difference Learning」第 372 段(text/09-fm-temporal-difference-learning.txt:372,搜「You are the Predictor」);八条经验的列表在第 376-379 段;「V(B)=3/4」在第 385 段(搜「3」);TD 答案 3/4 与 MC 答案 0 的对比在第 399-403 段(搜「batch Monte Carlo」);「未来数据上误差更小」在第 405 段(text/09-fm-temporal-difference-learning.txt:405,搜「future data」)。 ↩ ↩2

  11. 出处:「Temporal-Difference Learning」第 437 段(text/09-fm-temporal-difference-learning.txt:437,搜「striking」);O(n²)/O(n³) 的原文在第 434-436 段(搜「n2 memory」)。 ↩

  12. 出处:「Temporal-Difference Learning」第 248 段(text/09-fm-temporal-difference-learning.txt:248,搜「open question」)与第 255 段(搜「Random Walk」);真值 1/6…5/6 在第 273 段(搜「true values」);「TD consistently better」在第 305 段(搜「consistently better」)。 ↩ ↩2

  13. 出处:「Temporal-Difference Learning」第 471 段(text/09-fm-temporal-difference-learning.txt:471,搜「quintuple」)。 ↩

  14. 出处:「Temporal-Difference Learning」第 529 段(text/09-fm-temporal-difference-learning.txt:529,搜「17 steps」);「8000 步后贪心已最优」在第 528 段(搜「8000 time steps」);参数 ε=0.1、α=0.5 与风力各列 0 0 0 1 1 1 2 2 1 0 见第 517-524 段。 ↩

  15. 出处:「Temporal-Difference Learning」第 552 段(text/09-fm-temporal-difference-learning.txt:552,搜「early breakthroughs」)与第 558 段(搜「independent of the policy being followed」);持续访问的条件在第 562 段(搜「continue to be updated」)。 ↩

  16. 出处:「Temporal-Difference Learning」第 786 段(text/09-fm-temporal-difference-learning.txt:786,搜「dominate both」);确定性环境下 α 可取 1 在第 776 段(搜「safely set」)。 ↩

  17. 出处:「Temporal-Difference Learning」第 588 段(text/09-fm-temporal-difference-learning.txt:588,搜「Cliff Walking」);惩罚 −100 在第 600 段(搜「100」);Sarsa 走安全路、Q-learning 在线更差在第 624-631 段(搜「worse than that of Sarsa」);ε 降为零则同归最优在第 632 段(搜「asymptotically converge」)。 ↩ ↩2 ↩3

  18. 出处:「Temporal-Difference Learning」第 798 段(text/09-fm-temporal-difference-learning.txt:798,搜「maximization bias」)。 ↩

  19. 出处:「Temporal-Difference Learning」第 799 段(text/09-fm-temporal-difference-learning.txt:799,搜「Maximization Bias Example」);「左边是错误但被偏爱」在第 834 段(搜「favor left」);渐近仍多约 5% 在第 837 段(搜「5%」)。 ↩ ↩2

  20. 出处:「Temporal-Difference Learning」第 852 段(text/09-fm-temporal-difference-learning.txt:852,搜「double learning」)与第 853 段(搜「doubles the memory」)。 ↩

  21. 出处:「Temporal-Difference Learning」第 958 段(text/09-fm-temporal-difference-learning.txt:958,搜「most widely used」)。 ↩

  22. 出处:「Temporal-Difference Learning」第 974 段(text/09-fm-temporal-difference-learning.txt:974,搜「long-term predictions」)。 ↩

  23. 出处:「Temporal-Difference Learning」第 892 段(text/09-fm-temporal-difference-learning.txt:892,搜「afterstates」)。 ↩