机器人入行指南
原理层/随机逼近:学习率公式里的每一条

原理层 T22 / 27 · 随机逼近

随机逼近:学习率公式里的每一条

xn+1 = x_n + a_n(观测 − x_n) 收敛的每个条件都对应一类爆炸:步长不归零就永远抖,归零太慢带噪声尾巴。Robbins-Monro 两条是对 TD、Q-learning 学习率的最终解释。

高温几乎全接受 · 全局乱走接受准则变差也以 e^{−Δ/T} 接受降温调度T 按几何衰减冻结T→0 退化为贪心模拟退火 = 在「贪心的收敛」与「随机的覆盖」之间做调度——全局保证要慢降温换
约 55 分钟2 定理4 步证明4 题自测

一句话结论

带噪声的迭代想收敛到真值,步长必须满足 Σa_n=∞(走得够远)且 Σa_n²<∞(噪声积累有限)。固定步长不满足第二条——它收敛到真值的一个邻域然后永远抖动,稳态方差 a σ²/2 可精确算出。这就是「训练后期 loss 不再下降只抖动」的数学身份。

TD(0)、Q-learning、actor-critic 的每一个更新式都是本篇模板的填空题。看完本篇,学习率调度不再是玄学:哪类调度真收敛、哪类永远抖、抖多大——都可算。

为什么需要它

从最简单的情形切入:估计一个未知常数 θ,观测是 θ 加噪声(θ + 噪声)。朴素平均(样本均值)当然可行,但它要存全部历史。能否流式更新、每来一个样本只改一个数?xn+1 = x_n + a_n(x_n 的观测 − x_n)。

这个形式值得盯住:它就是 TD(0) 的更新式(把 θ 换成 V(s),观测换成 r+γV(s'))、是 SGD 的更新式(把观测换成梯度)、是 Q-learning 的骨架。所以「它什么时候收敛」的答案会原样迁移到所有这些算法。

直觉预演:步长固定 a 时,更新在真值附近做随机游走——新观测的噪声被乘 a 注入,旧误差被乘 (1−a) 衰减。稳态是两者的平衡:注入 a²σ²,衰减掉的约 2a×方差,平衡点方差 ≈ aσ²/2。步长不归零 ⇒ 噪声持续注入 ⇒ 永远抖。这可以严格化,但先让数字说话(见实测)。

定义

定义 10.1 Robbins-Monro 问题

求方程的根/目标的最优值,但只能拿到带噪声的观测:xn+1 = x_n − a_n·(观测噪声版的梯度信息)。估计均值是最简特例:观测 = θ + ε_n。

为什么这样定RL 的所有「用样本更新值/策略」的问题都能写成这个形状。它是 SGD 的 1951 年原型。

定义 10.2 步长条件(Robbins-Monro 1951)

步长序列 {a_n} 满足:(C1) Σ a_n = ∞;(C2) Σ a_n² < ∞。经典例子 a_n = 1/n:C1 调和级数发散 ✓,C2 Σ1/n² = π²/6 收敛 ✓。

为什么这样定C1 管「能不能到达」:步长总和有限则可能停在中途。C2 管「到了能不能安顿」:噪声注入的方差与 a_n² 成正比,二阶和有限才能积累有限。两条缺一不可,方向正好相反——这就是为什么最优调度要在两者之间走钢丝。

定理与证明

定理 10.1 Robbins-Monro 收敛定理(陈述+直观论证)

噪声零均值、方差有限、步长满足 C1+C2 时,x_n 几乎必然收敛到真值 θ*。固定步长 a 时收敛到邻域:limsup |x_n−θ*| 的稳态标准差 ≈ √(aσ²/2)。

证

完整证明(Dvoretzky 1956 版)超出边界。给出分解论证的骨架:误差 e_n = x_n − θ* 满足递推 en+1 = (1−a_n)e_n − a_n εn+1,即「确定性衰减 × (1−a_n)」加「噪声注入 −a_n ε」。

E[en+1²] = (1−a_n)² E[e_n²] + a_n² σ²

确定性部分:若 Σa_n=∞,衰减因子连乘 Π(1−a_n)=0——任何初始误差被磨光。噪声部分:稳态解方程 v = (1−a)²v + a²σ² 给出 v = a²σ²/(2a−a²) ≈ aσ²/2(a 小时)。步长递减且 Σa_n²<∞ 时,噪声注入的总方差有限——尾项任意小,误差趋于 0。∎(骨架级论证)

注诚实标注:这是「让数字可解释」级别的论证,不是完整证明。完整版需要超滤/ODE 方法(Borkar 的书)。但注意这个论证已经给出了固定步长稳态方差的精确公式——它是对的,且下面实测。

定理 10.2 两时间尺度(陈述)

两个耦合的随机逼近同时跑:快变量用步长 a_n、慢变量用 b_n,若 b_n/a_n → 0(慢的相对更快地「冻结」),则分析时可把慢变量视为常数处理——快变量先收敛到「以慢变量为参数」的平衡点,慢变量再沿着平衡点流移动。

证

证明(Borkar 的 ODE 方法)超出边界,只陈述与使用。

注actor-critic 的理论形式:critic 用较大步长(快速追踪 V^π),actor 用小得多的步长(把 critic 当准精确)。若两者步长同量级,actor 在「还没评估完的策略」上改进——改进定理(T8)前提失效。这也解释了为什么 target network 要慢更新:它扮演「慢时间尺度」的角色。

手算一遍

估计均值 θ=3.7,观测噪声 σ=1。固定步长 a=0.05 时稳态标准差是多少?要把它减半需要怎么改?再用级数判断 a_n=1/√n 为什么不合格。

  1. 稳态方差公式(定理 10.1):v = aσ²/(2−a) ≈ aσ²/2 = 0.05×1/2 = 0.025 → 稳态标准差 ≈ 0.158。
  2. 减半方差需要 a 减半(0.025)——固定步长的困境:降噪和提速矛盾(a 大收敛快但抖,a 小抖得轻但走不动)。
  3. [object Object]
  4. C2 破的后果:噪声方差注入 Σa_n²σ² = ∞,不收敛——尽管步长确实在变小。1/n^0.4 同罪(Σ1/n^0.8 发散)。
答

稳态标准差 0.158;减半需步长减半(牺牲速度);1/√n 不合格因为 Σa_n²=Σ1/n=∞。这条级数判据是写学习率调度时唯一需要背的公式:指数衰减和 1/n^p (p>1/2) 合格,1/n^p (p≤1/2) 不合格。

实跑一遍

数字出处

估计 θ=3.7(噪声 σ=1),6 万步,四种步长调度(各报告 x@100 / x@1k / x@10k / x@60k):

  • 固定 a=0.05:3.484 / 3.559 / 3.883 / 3.823 —— 在真值附近永久抖动(理论稳态 sd 0.158)
  • 固定 a=0.3:4.075 / 3.939 / 4.241 / 3.808 —— 抖得更凶(稳态 sd √(0.15)≈0.39)
  • a_n=1/n:3.805 / 3.728 / 3.690 / 3.701 —— 真收敛(60k 步时与真值差 0.001)
  • a_n=1/n^0.4:2.872 / 3.633 / 3.746 / 3.803 —— 早期快但后期残留噪声(Σa_n² 发散,C2 破)

映射回强化学习

这里的对象RL 里的对应物站内用法
Robbins-Monro 条件TD/Q-learning 的学习率调度合法性(1/n 型合格,常数型只到邻域)用法 →
固定步长的邻域「loss 降不下去只抖动」的数学身份:稳态方差 aσ²/2用法 →
两时间尺度critic 快 actor 慢、target network 慢更新用法 →
收敛前提Q-learning 全收敛还要求每对 (s,a) 无穷次访问——探索的定理化用法 →

边界:这一篇停在哪里

本篇停在哪里:Dvoretzky 定理的完整证明、ODE 方法、Markov 噪声下的随机逼近(转移核自己也在变——这正是 TD 的实际情形,Borkar 有结论但证明重),都不讲。诚实声明:TD/Q-learning 的完整收敛证明(Jaakkola-Tsitsiklis 1994、Tsitsiklis-Van Roy 1997)= 本篇 + Markov 链理论(T6)的叠加,深度 RL 的函数逼近版至今没有一般收敛保证(致命三要素,/fund/approx/)。

自测 4 题

全是手算和「找证明错在哪」类题目,不出背诵题。答不上来回到对应小节。

01Robbins-Monro 两条各管什么?举一个违反 C2 的调度。

C1(Σa_n=∞)管「走得到」——总步长有限则可能停在中途;C2(Σa_n²<∞)管「噪声不积累」——方差注入与 a_n² 成正比。违反 C2 的例子:a_n=1/√n(Σ1/n=∞)或 1/n^0.4。实测后者 6 万步后仍带 0.1 量级噪声。

02固定步长训练后期「loss 不降只抖」是什么现象?抖多大?

固定步长随机逼近的稳态:收敛到真值邻域后永久抖动,稳态方差 ≈ aσ²/2。a=0.05、σ=1 时 sd≈0.158。这不是 bug 也不是学习率太大「过了」——是固定步长的数学本性。要真收敛必须用递减调度。

03为什么 target network 要慢更新?用两时间尺度回答。

两时间尺度定理:慢变量(target/actor)相对快变量(online net/critic)冻结时,快变量的收敛分析才成立。target 同速更新时,回归目标本身在漂移——等于在追一个移动的靶子,chasing 会导致震荡(致命三要素的第三要素与此相关)。

04TD(0) 用常数学习率 0.01,理论上它收敛到 V^π 吗?

不收敛到精确值,收敛到 V^π 的一个邻域(稳态方差 aσ²/2 量级,σ² 是 TD 误差的方差)。表格情形想要精确收敛用 1/n 型调度(每个状态-对各自的访问计数),深度 RL 里大家接受邻域解——这就是「训练后期曲线抖动正常」的理论出处。

接着看

全系列 27 篇

T1矩阵就是旋转的记账本约 25 分钟T2从斜率到梯度:机器人学习算法的第一行约 25 分钟T3向量与受力:点积的物理读法约 20 分钟T4两把尺子和一把更好的尺子约 25 分钟T5电机转一圈的账:弧度、转速与功率约 20 分钟T6复数乘法就是旋转:四元数的一维版约 20 分钟T7基与坐标:为什么机器人什么都用矩阵约 45 分钟T8矩阵乘法:变换的串联,不是表格运算约 40 分钟T9雅可比:关节转一度,末端动多少约 45 分钟T10特征向量:矩阵不敢动的方向约 45 分钟T11SVD 与伪逆:没有精确解时,找最近的解约 50 分钟T12泰勒展开:用直线替曲线打工约 40 分钟T13概率空间:为什么「随机」需要公理约 50 分钟T14期望:「平均」的严格构造约 55 分钟T15条件期望:竖线的真正含义约 60 分钟T16四个不等式:「多少样本才够」的定量答案约 45 分钟T17范数与不动点:「一定收敛」的出处约 55 分钟T18马尔可夫链:时间平均何时等于集合平均约 55 分钟T19MDP 的数学构造:一条公理值多少钱约 50 分钟T20动态规划:两种迭代的账约 50 分钟T21优化:约束为什么不能只靠罚约 55 分钟T22随机逼近:学习率公式里的每一条约 55 分钟T23接触的数学:Hertz 理论约 45 分钟T24摩擦与摩擦锥:约束的几何形状约 40 分钟T25力封闭与抓取度量:ε 是一个线性规划约 50 分钟T26接触运动学:滚动为什么不是「贴着滑」约 45 分钟T27滑移检测:从「感觉到了」到「算出来了」约 50 分钟