控制与致命三件套 — 函数逼近下,什么会炸
这一章讲三件事: semi-gradient Sarsa 怎么把控制做起来(Mountain Car 走查); 持续任务里折扣为什么站不住,以及作者那个惊人的替代方案; w→2w 与 Baird 反例怎么把「致命三件套」炸给你看。 读完你会拿到第二部分最关键的安全地图:哪些组合有保证,哪个组合没有。
1. 控制端:半梯度 Sarsa
把第 09 章的套路从 v 搬到 q,评估对象变成「状态-动作 ↦ 目标」,更新目标还是那个熟悉的形状——R + γ·q̂(S′,A′),A′ 照 ε-greedy 选。这就是 episodic semi-gradient Sarsa,一切照旧、只是查表换成了函数1。
主走查:Mountain Car(书里的例 10.1,任务设定为书中给出)2:
任务:一辆动力不足的车卡在山谷,油门全开也爬不上坡;
唯一出路是先倒退、借对面坡攒动量,再冲上去。
状态 = (位置, 速度) 连续;动作 = {全油门前进, 全油门倒车, 不踩};
每步奖励 −1,冲过山顶结束。
为什么难:「必须先变得更远(离目标更远),才能变得更好」——
书里明说很多控制方法没人工帮助就搞不定这类任务。
做法:位置×速度铺上 8 层错位网格(tile coding,第 09 章),跑线性 semi-gradient Sarsa。
学到的 cost-to-go 图随训练展开:约 9000 步后,价值面显出完整的「先绕远、再冲刺」结构。
这个例子选得刁:奖励全负、目标只隐含在「尽快结束」里,没有任何一步有局部线索告诉你该倒车——值函数必须把长程后果全部学出来。
2. 一颗雷:折扣在持续任务里站不住
情节任务里折扣无所谓(反正有终点)。持续任务+函数逼近,书里掀了桌子,论证分两步3:
第一步(概念): 状态只剩特征向量、时间无始无终时,你手里其实只有一条不断流过的奖励序列。想评估它,唯一自然的就是长期平均奖励 r(π)。折扣呢?也可以算「折扣回报的平均」——但一算吓一跳:每个奖励在所有位置的回报里各出现一次,权重恰好凑成 1/(1−γ),平均折扣回报 = 平均奖励 × 常数;γ 取多少,策略排序一模一样;γ 取 0 都不改变排序。书里用「每个时间步完全对称」的论证把这个结论做成了带框的定理4。
第二步(定理失效): 那能不能照旧用折扣当目标?不能——函数逼近下,折扣算法并不优化「on-policy 分布上的折扣值」,于是也不保证优化平均奖励。作者归结出病根:函数逼近之下,策略改进定理没了。原文的重话:「With function approximation we have lost it!」5。
于是本章改用平均奖励设定:目标=最大化 r(π),值函数改成「差分值函数」(衡量比平均好多少),TD 误差改成 δ = R − R̄ + v̂(S′) − v̂(S),R̄ 是对平均奖励的在线估计6。作者的判词是本书最激进的主张之一:在函数逼近的控制问题定义里,折扣没有立足之地;它从「问题参数」降格为「 算法参数」7。别忘了补一刀:换了设定,ε-greedification 也可能来回震荡,不收敛——改进保证的缺口是整个动作值方法家族的,不是某个算法的8。
3. 另一颗雷:致命三件套
3.1 w→2w:十行就能演的爆炸
把最小的一块误差放大看(书里 11.2 节的开场例,数字全部来自书)9:
两个状态,值函数被参数化成 v(s₁)=w,v(s₂)=2w(特征分别是 1 和 2,w 是一个数)。
s₁ 唯一的动作必然转移到 s₂,奖励 0。真实值全 0,即 w=0 是正确解。
离策训练:行为策略反复经历 s₁→s₂(其他转移的权重 ρ=0,不更新)。
TD 误差 δ = 0 + γ·2w − w = (2γ−1)·w
更新 w ← w + α·ρ·(2γ−1)·w = w·(1 + α(2γ−1))
γ=1,α=0.1,初值 w=1:每次更新乘以 1.1 → 1, 1.1, 1.21, 1.33, … 指数奔向无穷。
只要 γ>0.5,系数就大于 1 —— 与步长大小无关,α 只改爆炸速度,不改变炸不炸。
机理一句话:提升 w 让 s₁ 的估计追上 s₂,但 s₂ 的估计也同步被抬高——追者永远追不上被追者。on-policy 时这个游戏玩不下去(每条「期望」后面必须接上兑现,「toll 要还」,书里说「the piper must be paid」);off-policy 时,一条「目标策略绝不会走的转移」可以把账一笔勾销——书里的措辞:许下的诺可以「随后被遗忘和原谅」10。
3.2 Baird 反例:正经 MDP 也炸
怕人说「那是残缺的碎片,不是真 MDP」,书里给了完整反例(设定为书中给出)11:七个状态、两个动作、八个线性特征、奖励恒 0(真值全 0,w=0 即完美解)。行为策略让下一状态均匀分布,目标策略固定选实线动作。半梯度 TD(0) 从任意正步长都发散——连换成 DP 的期望更新也发散;把更新分布从均匀改回 on-policy 分布,收敛恢复。作者的结语值得背下来:哪怕是 bootstrap 与函数逼近最简单的组合,只要更新分布不按 on-policy 分布来,就可能不稳定11。Q-learning 也有类似的发散反例;行为策略取 ε-greedy 时「据我们所知从未见过发散,但也没有理论分析」12。
3.3 三件套清单
书里把危险归纳成一个名字——致命三件套(deadly triad),三者同时在场就可能发散13:
- 函数逼近(要扩展性,丢不起);
- bootstrapping(丢了的代价是计算与数据效率,书里盘点下来「极有价值,非常想留」)14;
- 离策训练(更新分布≠目标策略的分布)。
两两组合都安全(线性+on-policy bootstrap 有定理;off-policy+表格有收敛;MC+任何逼近不 bootstrap 所以不炸);三个一起,没有一般保证。注意书里特意澄清:危险不在控制、不在 GPI、也不在学习本身——环境完全已知的 DP 规划照样炸;病根在「更新分布」与「谁的目标」脱钩15。
4. 作者的判断与证据
实验/反例支撑的: Mountain Car 的 cost-to-go 演化、w→2w 的逐项更新、Baird 的发散曲线(α=0.01,初值里 w₇=10)都是书中给定的实验2911;「γ 对策略排序无影响」有带框证明4。
作者的立场(本章两条重炮): ①折扣应当被逐出持续任务控制问题的定义(可留作算法技巧);②「致命三件套」这个命名本身就是判断——它把一个散落的工程 folklore 提升为领域级的结构性事实(书里注明三件套的提法出自 Sutton 1995b,系统分析靠后来者)16。
坦白: 「我们目前没有一个局部的改进保证可用于动作值方法」——作者把这一页写得很诚实;可能的出路(Perkins & Precup 等)只被点名8。
5. 边界与局限
- 发散是「可能」,不是「必然」:大量离策+逼近的实际系统跑得好好的;理论给的是「无保证」,不是「必炸」。
- 救法在本章只有两条消极路线:丢掉 bootstrapping(用 MC 式目标)或丢掉函数逼近的发挥(averagers 这类不做外推的逼近器);正面解法在下一章。
- 平均奖励设定自身也有代价:差分值函数的估计多一个要在线学的 R̄;episodic 任务里折扣照旧好用。
- Baird 反例是构造出来的极端;它证明「最简单的组合都可能炸」,不预测你的具体任务炸不炸。
6. 可带走的
- 半梯度 Sarsa 是函数逼近时代控制的默认起点;Mountain Car 说明值函数要学的正是「先绕远」这类无局部线索的长程结构。
- 持续任务里,折扣的目标没有立足之地(γ 不影响策略排序),平均奖励才是自然目标;γ 降格为算法参数。
- 函数逼近杀死了策略改进定理——这是第二部分几乎所有理论不安的总根源。
- w→2w 一例记住爆炸的机理:bootstrap 把「追估」变成自我抬升,离策把兑现的义务一笔勾销。
- 致命三件套 = 函数逼近 + bootstrapping + 离策训练;两两可以,三个同台无保证——选型时先数这三样。
- 危险与「学习/规划」「控制/预测」无关,DP 规划照样炸;关键变量是更新分布与目标策略是否一致。
- ε-greedy 行为策略下未见发散但没有理论——「实践中没炸」不等于「安全」。
7. 原文地图
| 主题 | 原书章 | 原文位置 |
|---|---|---|
| 半梯度 Sarsa | On-policy Control with Approximation | text/13-fm-on-policy-control-with-approximation.txt:39(搜「episodic semi-gradient」) |
| Mountain Car | On-policy Control with Approximation | text/13-fm-on-policy-control-with-approximation.txt:72(搜「Mountain Car」) · text/13-fm-on-policy-control-with-approximation.txt:112(搜「get worse」) |
| 平均奖励转向 | On-policy Control with Approximation | text/13-fm-on-policy-control-with-approximation.txt:12(搜「average-reward」) |
| 废弃折扣 | On-policy Control with Approximation | text/13-fm-on-policy-control-with-approximation.txt:479(搜「questionable whether」) |
| γ 不影响排序 | On-policy Control with Approximation | text/13-fm-on-policy-control-with-approximation.txt:542(搜「does not influence the ordering」) |
| 没有立足之地 | On-policy Control with Approximation | text/13-fm-on-policy-control-with-approximation.txt:508(搜「no role to play」) |
| 丢了改进定理 | On-policy Control with Approximation | text/13-fm-on-policy-control-with-approximation.txt:277(搜「With function approximation」) |
| 抖动 | On-policy Control with Approximation | text/13-fm-on-policy-control-with-approximation.txt:554(搜「chatter」) |
| w→2w | Off-policy Methods with Approximation | text/14-fm-off-policy-methods-with-approximation.txt:130(搜「2w」) · text/14-fm-off-policy-methods-with-approximation.txt:159(搜「specific step size」) |
| 诺被原谅 | Off-policy Methods with Approximation | text/14-fm-off-policy-methods-with-approximation.txt:176(搜「forgotten and forgiven」) |
| Baird 反例 | Off-policy Methods with Approximation | text/14-fm-off-policy-methods-with-approximation.txt:180(搜「Baird」) · text/14-fm-off-policy-methods-with-approximation.txt:215(搜「no matter how small」) · text/14-fm-off-policy-methods-with-approximation.txt:250(搜「simplest combination」) |
| Q-learning 未见发散 | Off-policy Methods with Approximation | text/14-fm-off-policy-methods-with-approximation.txt:258(搜「never been found」) |
| 致命三件套 | Off-policy Methods with Approximation | text/14-fm-off-policy-methods-with-approximation.txt:299(搜「deadly triad」) |
| 三选一的取舍 | Off-policy Methods with Approximation | text/14-fm-off-policy-methods-with-approximation.txt:326(搜「cannot be given up」) · text/14-fm-off-policy-methods-with-approximation.txt:354(搜「extremely valuable」) |
| 不在学习也不在规划 | Off-policy Methods with Approximation | text/14-fm-off-policy-methods-with-approximation.txt:317(搜「not due to」) |
| 三件套命名出处 | Off-policy Methods with Approximation | text/14-fm-off-policy-methods-with-approximation.txt:2052(搜「1995b」) |