跳到主要内容

函数逼近 — 从查表到学规律

这一章讲四件事: 表格为什么必须被换掉,换成的参数化函数怎么接上监督学习; 「往哪个状态学」变成一个必须显式回答的问题(on-policy 分布); 半梯度这个词「半」在哪,线性情形的收敛定理与代价; 特征构造与神经网络各扮演什么角色。 读完你会理解全书最大的转轨:从「存得下」的世界进入「要泛化」的世界。

1. 转轨:表格的死亡​

第一部分的所有方法都默认一件事:每个状态(或状态-动作对)有自己专属的一个数。双陆棋 10^20 个状态已经宣告这条路走不通。本章把值函数换成参数化的函数形式 v̂(s,w)≈vπ(s):线性函数也好、多层神经网络也好、决策树(像流程图一样层层提问的模型)也好,权重向量的维数 d 远小于状态数1。

这一换带来一个质变:改一个权重,许多状态的估计值一起变——在某个状态学到的经验,自动泛化到相似状态。书里的评价一分为二:泛化让学习潜在的更强大,但也更难驾驭和理解1。

意外的红利:函数逼近顺带让 RL 能处理部分可观测问题——只要函数形式上不让值依赖状态的某些侧面,那些侧面就等价于看不见2。

2. 核心原理一:每次更新 = 一条监督学习样例​

把 TD(0) 的更新拆开看:它说「状态 S(t) 的值,该更像 R(t+1)+v̂(S(t+1))」。这就是一条输入-输出样例:S(t) ↦ 目标值。于是任何监督学习方法(神经网络、决策树、回归)都能拿来当值函数的学习器——把每次更新当一条样例喂给它即可3。

但不是什么监督学习法都行。RL 有两条硬约束,直接淘汰了一批漂亮方法4:

  • 在线增量:数据一条条来,不允许「先攒一大堆旧数据再整批刷」;
  • 非平稳目标:控制里策略在变,bootstrap 的目标本身也在漂——静态数据集上研发的精巧方法,遇到会动的靶子就失灵。

3. 核心原理二:「在乎哪些状态」必须说清​

表格时代每个状态各管各的,可以处处精确;现在参数不够用,把这个状态调准必然把别的状态挤歪——于是「更在乎哪些状态的误差」必须显式建模。这就是状态分布 μ(s) 与目标函数 VE(均方值误差)。最自然的 μ 是on-policy 分布:按策略走,停留在各状态的时间占比5。

作者在这里留了句诚实的话:连 VE 是不是对的优化目标都不完全清楚——我们学值函数是为了找好策略,对策略最有用的值函数未必是 VE 最小的那个;只是眼下没有更好的共识答案6。还要记一个坏消息:函数逼近之下,有的方法干脆发散,VE 冲向无穷——这不是危言耸听,第 10 章会给反例7。

4. 核心原理三:梯度下降,和「半」个梯度​

SGD(随机梯度下降):每来一个样例,把权重朝「这条样例的误差下降最快的方向」挪一小步8。直观版:误差像山谷的高度,梯度是上坡方向,每次朝下坡踩一小步,换一条样例踩一步,最后停在谷底。

而 TD 类方法的麻烦在:目标 R+v̂(S′) 里含有 w 自己。严格求梯度就该把这一项也算进去;实际上大家都把它当常数不管——只对 v̂(S(t)) 这一半求梯度,所以叫 semi-gradient(半梯度)9。省事、常用、有效,但经典 SGD 的收敛定理不能直接搬过来——需要单独证。

5. 线性情形:唯一能全证的世界​

线性方法把每个状态表示成一个特征向量 x(s),值=权重的加权和 wᵀx(s)。它是最受理论青睐的情形——书里直言:几乎所有学习系统的有用收敛结果,都是线性(或更简单)情形的10。

主走查看线性 TD(0) 的落点(数是推演用的演示值,机制为书中定理):

  设两个特征 x₁=「是否靠近出口」(0 或 1)、x₂=「走廊长度」(1–5),权重 w₁=4、w₂=−0.5。
  状态 s:x(s)=[1,3] → v̂ = 4×1 + (−0.5)×3 = 2.5
  一步后拿到奖励 R=1,后继 v̂(S′)=3.0,α=0.1,γ=0.9:
    δ = 1 + 0.9×3.0 − 2.5 = 1.2
    w ← w + α·δ·x(s) = [4, −0.5] + 0.1×1.2×[1,3] = [4.12, −0.14]

  注意:只访问了 s,但两个权重都动了 → 所有含这些特征的状态的估计都变了。
  这就是「改一处、动一片」的具体样子。

线性 semi-gradient TD(0) 收敛到的点有名字:TD fixed point(w_TD=A⁻¹b)11。它的代价也有定量刻画:fixed point 处的 VE 不超过理论最优误差的 1/(1−γ) 倍——γ=0.9 时是最优的 10 倍以内,γ 越大放大越狠。作者如实两边记账:TD 的渐近误差可能明显更差,但方差小、学得快;孰优取决于问题和学习时长12。n-step 推广后,界随 n 增大而变紧、n→∞ 时退回 MC 的最优界——但实践中太高的 n 学得太慢,还是小 bootstrap 划算13。

6. 特征怎么造,网络何时进场​

特征选择是往系统里注入领域知识的最主要通道14。书里的工具箱一句话带过:多项式基(在线情形泛化差)、tile coding(把状态空间铺多层错位的网格,每格一个开关;计算便宜、灵活,线性方法的主力)、径向基函数(低维平滑响应)、Fourier 基15。

再往上是非线性方法:多层神经网络+反向传播(把误差从输出逐层传回、算出每个权重该怎么改的算法)。书里对它的定位值得原样记住:这些方法近年大红大紫,名字就叫深度强化学习16——全书 2018 年成书时,已经给 DQN(第 15 章)预留好了理论位置。

7. 作者的判断与证据​

书里给了定理/推导的: 线性 TD(0) 收敛(证明核心:矩阵(数字排成的表)D(I−γP) 的列和为 (1−γ)μ>0,故正定)——这个证明依赖 on-policy 分布:μ 恰是策略自己的平稳分布,列和才恰好非负17。请记住这个依赖,它是下一章所有故事的引线:分布一换(离策),证明的地基就没了。

作者的立场: 在函数逼近下,「挑哪些状态学」从技术细节升格为目标定义的一部分;本书选定 on-policy 分布作为本章的立足点,off-policy 推到第 11 章。

8. 边界与局限​

  • half 的代价:semi-gradient 不是真梯度,只有线性(及部分特殊)情形有收敛保证;非线性情形连局部最优(在小邻域内最好的解)都保证不了。
  • 1/(1−γ) 的界只在 on-policy + 线性 + γ<1 下成立;三个条件缺一个都作废。
  • 特征构造仍是手工艺术,书里直言「更多的表示选择目前 more art than science」(第 03 章已见),本章的工具箱也只是菜单不是答案。
  • 神经网络部分本章只开窗口;它与本框架组合时的稳定性问题,要到第 10 章才见分晓。

9. 可带走的​

  1. 参数少于状态=必须泛化:改一个权重、动一片状态——这是力量也是失控的来源。
  2. 每次更新就是一条监督学习样例;但你的监督学习器必须吃得了「源源涌来的经验+会漂的靶子」。
  3. on-policy 分布是表格时代没有的新问题:误差必须在某个状态分布下加权,本书默认「按策略呆得久的状态」。
  4. semi-gradient 的「半」:目标里的 w 不进梯度;省了事,也丢了现成定理。
  5. 线性世界的两个数字:TD fixed point 存在且收敛;误差至多 1/(1−γ) 倍于最优——γ=0.9 时付的「近视税」可到 10 倍。
  6. tile coding 是线性时代的王牌特征;神经网络是下一个时代的——它在本书里的名字就是「深度强化学习」。
  7. 收敛证明押在 on-policy 分布上——记住这句,下一章它就是案发现场。

10. 原文地图​

主题原书章原文位置
参数化、泛化的双刃On-policy Prediction with Approximationtext/12-fm-on-policy-prediction-with-approximation.txt:16(搜「number of states (d ⌧
部分可观测红利On-policy Prediction with Approximationtext/12-fm-on-policy-prediction-with-approximation.txt:22(搜「partially observable」)
更新即样例On-policy Prediction with Approximationtext/12-fm-on-policy-prediction-with-approximation.txt:48(搜「input–output」)
RL 的两条硬约束On-policy Prediction with Approximationtext/12-fm-on-policy-prediction-with-approximation.txt:63(搜「incrementally acquired」) · text/12-fm-on-policy-prediction-with-approximation.txt:65(搜「nonstationary」)
μ 与 VE、on-policy 分布On-policy Prediction with Approximationtext/12-fm-on-policy-prediction-with-approximation.txt:82(搜「state distribution」) · text/12-fm-on-policy-prediction-with-approximation.txt:95(搜「on-policy distribution」)
VE 是否正确目标On-policy Prediction with Approximationtext/12-fm-on-policy-prediction-with-approximation.txt:123(搜「right performance objective」)
可能发散On-policy Prediction with Approximationtext/12-fm-on-policy-prediction-with-approximation.txt:136(搜「diverge」)
SGDOn-policy Prediction with Approximationtext/12-fm-on-policy-prediction-with-approximation.txt:152(搜「stochastic gradient descent」)
线性方法、特征On-policy Prediction with Approximationtext/12-fm-on-policy-prediction-with-approximation.txt:357(搜「feature vector」)
线性世界几乎全部定理On-policy Prediction with Approximationtext/12-fm-on-policy-prediction-with-approximation.txt:374(搜「Almost all useful」)
TD fixed pointOn-policy Prediction with Approximationtext/12-fm-on-policy-prediction-with-approximation.txt:409(搜「TD fixed point」)
1/(1−γ) 界On-policy Prediction with Approximationtext/12-fm-on-policy-prediction-with-approximation.txt:486(搜「substantial potential loss」)
收敛证明的列和On-policy Prediction with Approximationtext/12-fm-on-policy-prediction-with-approximation.txt:96(搜「stationary distribution」)
n-step 界与实用On-policy Prediction with Approximationtext/12-fm-on-policy-prediction-with-approximation.txt:1736(搜「bound」)
tile coding 等、深度 RLOn-policy Prediction with Approximationtext/12-fm-on-policy-prediction-with-approximation.txt:1727(搜「Tile coding」) · text/12-fm-on-policy-prediction-with-approximation.txt:1734(搜「deep reinforcement learning」)
semi-gradient 的定义On-policy Prediction with Approximationtext/12-fm-on-policy-prediction-with-approximation.txt:150(搜「semi-gradient」)

Footnotes​

  1. 出处:「On-policy Prediction with Approximation」第 16 段(text/12-fm-on-policy-prediction-with-approximation.txt:16,搜「number of states (d ⌧ |S|)」)与第 18 段(text/12-fm-on-policy-prediction-with-approximation.txt:18,搜「generalization」)。 ↩ ↩2

  2. 出处:「On-policy Prediction with Approximation」第 22 段(text/12-fm-on-policy-prediction-with-approximation.txt:22,搜「partially observable」)。 ↩

  3. 出处:「On-policy Prediction with Approximation」第 48 段(text/12-fm-on-policy-prediction-with-approximation.txt:48,搜「input–output」)与第 52 段(搜「training example」)。 ↩

  4. 出处:「On-policy Prediction with Approximation」第 63 段(text/12-fm-on-policy-prediction-with-approximation.txt:63,搜「incrementally acquired」)与第 65 段(搜「nonstationary」)。 ↩

  5. 出处:「On-policy Prediction with Approximation」第 82 段(text/12-fm-on-policy-prediction-with-approximation.txt:82,搜「state distribution」)与第 94 段(搜「on-policy distribution」)。 ↩

  6. 出处:「On-policy Prediction with Approximation」第 123 段(text/12-fm-on-policy-prediction-with-approximation.txt:123,搜「right performance objective」)。 ↩

  7. 出处:「On-policy Prediction with Approximation」第 136 段(text/12-fm-on-policy-prediction-with-approximation.txt:136,搜「diverge」)。 ↩

  8. 出处:「On-policy Prediction with Approximation」第 152 段(text/12-fm-on-policy-prediction-with-approximation.txt:152,搜「stochastic gradient descent」)与第 177 段(搜「observed examples」)。 ↩

  9. 出处:「On-policy Prediction with Approximation」第 150 段(text/12-fm-on-policy-prediction-with-approximation.txt:150,搜「semi-gradient」)。原文:「the weight vector appears in the update target, yet this is not taken into account in computing the gradient—thus they are semi-gradient methods」。 ↩

  10. 出处:「On-policy Prediction with Approximation」第 374 段(text/12-fm-on-policy-prediction-with-approximation.txt:374,搜「Almost all useful」);特征向量定义在第 357 段(搜「feature vector」)。 ↩

  11. 出处:「On-policy Prediction with Approximation」第 409 段(text/12-fm-on-policy-prediction-with-approximation.txt:409,搜「TD fixed point」)。主走查的特征与更新数值是我们按书中式 (9.9) 编排的演示值。 ↩

  12. 出处:「On-policy Prediction with Approximation」第 486 段(text/12-fm-on-policy-prediction-with-approximation.txt:486,搜「substantial potential loss」);「方差小、更快」的对照在第 488-490 段(搜「vastly reduced variance」)。 ↩

  13. 出处:「On-policy Prediction with Approximation」第 136 段(text/12-fm-on-policy-prediction-with-approximation.txt:136,搜「bound」);「小 bootstrap 划算」在第 1739 段(搜「usually preferable」)。 ↩

  14. 出处:「On-policy Prediction with Approximation」第 596 段(text/12-fm-on-policy-prediction-with-approximation.txt:596,搜「prior domain knowledge」)。 ↩

  15. 出处:「On-policy Prediction with Approximation」第 1727 段(text/12-fm-on-policy-prediction-with-approximation.txt:1727,搜「Tile coding」)。 ↩

  16. 出处:「On-policy Prediction with Approximation」第 1734 段(text/12-fm-on-policy-prediction-with-approximation.txt:1734,搜「deep reinforcement learning」)。 ↩

  17. 出处:「On-policy Prediction with Approximation」第 96 段(text/12-fm-on-policy-prediction-with-approximation.txt:96,搜「stationary distribution」)与第 475 段(搜「positive definite」)。 ↩