n-step — 在「等一秒」与「等一局」之间自由滑动
这一 章讲四件事: n-step return 怎么把 TD 与 MC 接成一条光谱; 为什么这条谱上每一点都站得住(误差缩减性质); 离策学习的两条 n-step 路线:重要性采样(方差大)与 tree-backup(不用采样); 以及按步选择「采样还是期望」的统一算法 Q(σ)。 读完你会理解,「学多快、信多深」是一个可以连续调节的旋钮,不是非此即彼。
1. 定位:填满 MC 与 TD 之间的空档
MC 与 one-step TD 各有失手的时候。n-step 方法把两者泛化成一条光谱:一端是 one-step TD,另一端是 MC,中间可以平滑滑动,按任务需要取位;最好的方法往往在中间1。
作者还给了个很工程的动机,叫时间步的暴政(the tyranny of the time step):one-step 方法里,「多快能改动作」和「bootstrap 跨多远」被同一个时间步绑死——改动作要快,bootstrap 却想在「发生了一次可辨认的状态变化」那么长的时间尺度上进行;one-step 里两者只能互相将就。n-step 把 bootstrap 的时长解放出来2。
2. 核心原理一:n-step return 的构造(主走查)
n-step return 就是:前 n 步的真实奖励,加上第 n 步到达状态的当前估计值(估计值替我们补上没看到的部分):
G(t:t+n) = R(t+1) + γR(t+2) + … + γ^(n−1)·R(t+n) + γ^n·V(S(t+n))
└──── n 步真金白银 ────┘ └── 一个 guess 兜底 ──┘
n=1:就是 TD(0) 的目标; n=∞(到局终):就是 MC 的目标。
主走查:同一局经验,三种 n 各学到什么(书里例 7.1 的开场景设定,状态与更新行为为书中给出)3:
5 状态随机游走(A B C D E,起点 C,到达右端 E 外终止得 +1,其余奖励 0),
所有估计初始化 0.5。假设第一局恰好一路向右:C → D → E → 终止(回报 1)。
one-step(n=1):只有 E 被更新——V(E) 从 0.5 朝 1 挪。
A、B、C、D 什么都没学到:它们离「出结果」隔了不止一步。
two-step(n=2):D 和 E 都被更新,都朝 1 挪。C 仍然没份。
n≥3: C、D、E 全部朝 1 挪,幅度相同。
同一局经验,一条路径上每个环节都记了功。
一眼可见的权衡:n 越大,单局经验传播得越远,但每条更新要等得越久。哪端更好不是定理说了算——书里在 19 状态随机游走上做了 n 与 α 的参数扫描(19 态、左端 −1、右端 +1),中间的 n 成绩最好:泛化到 n-step 确实能胜过两个极端4。
3. 核心原理二:整条光谱都收敛——误差缩减性质
n 越大目标里「猜测」的成分越少,这件事可以证成定理:误差缩减性质(error reduction property)——n-step return 的期望,其最坏情况的误差,不超过 V 当前最坏误差的 γ^(n/2) 倍。n 越大,保证越强;推论是所有 n-step TD 方法在适当条件下都收敛到正确的预测——这是一族「血统纯正」的方法,one-step TD 与 MC 是它的两个极端成员5。
4. 核心原理三:控制版 n-step Sarsa
把状态换成状态-动作对、末端接 Q(S(t+n), A(t+n)),就是 n-step Sarsa;one-step 版改叫 Sarsa(0)6。它为什么值得存在?书里画了一个一目了然的网格对比:一条通往高奖励格 G 的路径,one-step Sarsa 只强化最后一个动作,n-step Sarsa 强化最后 n 个——同样一局,学到的多得多7。
5. 核心原理四:离策的两条路线
数据来自行为策略 b、学的是目标策略 π 时(第 05 章的老问题),n-step 有两条路:
路线一:重要性采样。 给 n-step return 乘上轨迹概率比 ρ。可行,但 n 越长、乘的因子越多、方差越炸——书里在 5.8-5.9 节已经预告过这类「外无关因子白加方差」的病灶(折扣感知与 per-decision 两个减震器)。这一路在 n-step 里只是过渡。
路线二:tree-backup,完全不用重要性采样。 关键洞察:离策缺的不是数据,是「没发生的动作」的回报。那就不去猜它,用它的当前估计值:把每个状态旁「没被选中的动作」的估计值,按目标策略给它们的概率加权,编进更新目标——更新的来源从「一条采样的轨迹」变成「以实际轨迹为主干、两侧挂满估计值的一棵树」8。书里的说法:这是从整棵动作值估计之树上做的更新;特例检查:n=1 时它恰好就是 Expected Sarsa,目标策略为贪心时与 Q-learning 一脉相承9。
统一:Q(σ)。 Sarsa(全采样)、Expected Sarsa(除末步全期望)、tree-backup(全期望)其实是同一个算法在三档「采样程度」上的三个切面。引入每步一个采样度 σ ∈[0,1]——σ=1 退化为 Sarsa,σ=0 退化为 tree-backup,还可以逐状态、逐动作、甚至随机地取值。这就是 n-step Q(σ),二版新增算法10。
6. 作者的判断与证据
实验支撑的: 19 状态随机游走上「中间 n 最佳」的参数扫描4;网格图上 one-step 与 10-step 的学习广度对比7。
作者的立场: n-step 的框架价值大于它的直接使用价值——书里明说 n-step 想法「通常被当作资格 traces 的引子」,本书刻意把两者拆开,先在简单的 n-step 情形里把问题处理干净11;「从时间步的暴政下解放」的表述本身就是一个方法论主张:更新粒度应当与决策粒度解耦2。
坦白: 重要性采样路线的方差问题在本章只被「绕开」(tree-backup)而非解决;它真正的正面强攻要等到第 11 章(Gradient-TD),那里还会发现连「优化什么」 都曾搞错。
7. 边界与局限
- 前 n−1 步没有更新:一局的前几步学不到东西,靠局末补齐;实时性不如资格迹(第 12 章的动机之一)12。
- 要存最近 n 步的完整轨迹:内存与 n 成正比——资格迹用一个迹向量(一排随时间衰减的数)换掉这整段存储。
- tree-backup 的目标策略必须是可算的概率(要按 π 给每个未选动作加权);π 本身复杂时这个「期望」也不便宜。
- Q(σ) 的 σ 怎么取,书里给了机制没给答案——它是新增的自由度,也是新的调参负担10。
8. 可带走的
- n-step return = n 步真实 + 一个估计兜底;n 是「信数据」与「信模型(自己的估计)」之间的滑杆。
- 中间往往最好:既不全信长报告(太慢、方差大),也不全信一步猜测(太近视)。
- 误差缩减性质给整条光谱上了保险:多等一步,保证严格变强。
- 同一局经验,n 越大学得越多:路径上每个环节都记功,而不是只记最后一 步(主走查的 C、D、E)。
- 离策 n-step 优先想 tree-backup:没发生的动作用估计值+目标策略概率补齐,绕开重要性采样的方差账单。
- Sarsa / Expected Sarsa / tree-backup 是一个算法的三档采样度——Q(σ) 把这层窗户纸捅破。
- 决策粒度与学习粒度应当解耦(时间步的暴政);工程上这就是「更新窗口长度」独立可调的正当性。
9. 原文地图
| 主题 | 原书章 | 原文位置 |
|---|---|---|
| 光谱定位、中间最好 | n-step Bootstrapping | text/10-fm-n-step-bootstrapping.txt:6(搜「spectrum」) |
| 时间步的暴政 | n-step Bootstrapping | text/10-fm-n-step-bootstrapping.txt:10(搜「tyranny」) |
| 与资格迹的分工 | n-step Bootstrapping | text/10-fm-n-step-bootstrapping.txt:19(搜「eligibility traces」) |
| n-step return、更新式 | n-step Bootstrapping | text/10-fm-n-step-bootstrapping.txt:83(搜「n-step return」) · text/10-fm-n-step-bootstrapping.txt:100(搜「n-step TD」) |
| 误差缩减性质 | n-step Bootstrapping | text/10-fm-n-step-bootstrapping.txt:144(搜「error reduction property」) |
| 例 7.1 开场景 | n-step Bootstrapping | text/10-fm-n-step-bootstrapping.txt:149(搜「Random walk」) · text/10-fm-n-step-bootstrapping.txt:154(搜「one-step method」) |
| 19 状态扫描 | n-step Bootstrapping | text/10-fm-n-step-bootstrapping.txt:163(搜「19 states」) · text/10-fm-n-step-bootstrapping.txt:170(搜「intermediate value of n」) |
| n-step Sarsa | n-step Bootstrapping | text/10-fm-n-step-bootstrapping.txt:201(搜「n-step Sarsa」) |
| 网格对比图 | n-step Bootstrapping | text/10-fm-n-step-bootstrapping.txt:267(搜「speedup」) |
| tree-backup | n-step Bootstrapping | text/10-fm-n-step-bootstrapping.txt:469(搜「Without Importance Sampling」) · text/10-fm-n-step-bootstrapping.txt:492(搜「treebackup」) |
| Q(σ) 统一 | n-step Bootstrapping | text/10-fm-n-step-bootstrapping.txt:581(搜「Unifying」) · text/10-fm-n-step-bootstrapping.txt:587(搜「unified」) |
| Q(σ) 为二版新算法 | n-step Bootstrapping | text/10-fm-n-step-bootstrapping.txt:738(搜「new to this text」) |