机器人入行指南
原理层/范数与不动点:「一定收敛」的出处

原理层 T17 / 27 · 收敛与不动点

范数与不动点:「一定收敛」的出处

「值迭代一定收敛」不是经验事实,是 Banach 不动点定理的推论。贝尔曼最优算子在 sup 范数下是 γ-压缩——γ<1 是全部前提,γ=1 时一切保证消失。

x当前估计映射 f贝尔曼算子 / 梯度步f(x)新估计收敛判据压缩映射 → 唯一不动点不动点f(x*)=x*值迭代收敛的全部理由就是「贝尔曼算子是 γ-压缩」——γ 越小收得越快
约 55 分钟2 定理10 步证明4 题自测

一句话结论

压缩映射原理一句话:完备空间上,把点与点之间距离压缩到 γ<1 倍的映射有且只有一个不动点,且从任何起点迭代都能以 γ^k 的速度到达它。值迭代的收敛速度、误差界、停止条件,全部是这条定理的机械应用。

TD 收敛吗?值迭代收敛吗?Q-learning 呢?这些问题的第一个共同源头在这里。看完本篇你会知道:「收敛」的证明结构长什么样、γ 扮演什么角色、以及 γ=1 时缺口在哪里——后面 T10 会补上随机版本的最后一块。

为什么需要它

先立靶子:给定贝尔曼最优算子 (TV)(s) = max_a Σs' p(s'|s,a)[r + γV(s')],「值迭代收敛」的意思是 V, TV, T²V, … 趋向唯一解 V*,满足 TV* = V*。

为什么 T²V 会稳定下来而不是来回震荡甚至发散?迭代法的收敛性分析有一条通用路径:找空间上的距离度量,证明映射把任意两点的距离至少压缩 γ<1 倍。这时迭代序列是柯西列,极限存在,极限必然是不动点。

需要的工具一个一个来:什么叫两点距离(范数)、什么叫距离意义下的完备(柯西列都收敛)、什么叫压缩(Lipschitz 常数 <1)。

定义

定义 5.1 范数与完备性

范数 ‖·‖ 是向量空间上满足正定性、齐次性、三角不等式的函数。度量空间完备:任何柯西列(元素两两距离趋于 0)都在空间内收敛。ℝⁿ 配任何范数都完备。

为什么这样定完备性是「极限存在」的保证。没有它,柯西列可能「收敛到空间外」——迭代法白跑。值函数空间 ℝ|S| 配 sup 范数完备,这一条在有限状态时免费。

定义 5.2 压缩映射

(X, ‖·‖) 上的映射 T 是 γ-压缩(γ<1),若对一切 x, y∈X:‖Tx − Ty‖ ≤ γ‖x−y‖。γ 叫压缩系数。

为什么这样定注意 ≤ γ‖x−y‖ 对一切点对一致成立——不是平均意义、不是局部意义。贝尔曼算子恰好满足这个强条件(系数恰为 γ),这是强化学习最幸运的一件事。

定理与证明

定理 5.1 Banach 不动点定理(完整证明)

完备空间 X 上的 γ-压缩映射 T 有唯一不动点 x*,且从任意 x₀ 出发,‖x_k − x*‖ ≤ γ^k/(1−γ)·‖x₁−x₀‖。

证

第一步(迭代序列是柯西列)。对 m>n,反复用压缩性:‖xn+1−x_n‖ ≤ γ‖x_n−xn−1‖ ≤ … ≤ γ^n‖x₁−x₀‖。三角不等式求和:

‖x_m − x_n‖ ≤ Σk=nm−1 ‖xk+1−x_k‖ ≤ ‖x₁−x₀‖·Σk=nm−1 γ^k ≤ ‖x₁−x₀‖·γ^n/(1−γ)

γ^n → 0,所以 m,n 充分大时右端任意小——柯西列。由完备性,x_n → x* ∈ X。

第二步(极限是不动点)。T 是压缩故连续(‖Tx−Ty‖≤γ‖x−y‖ 里令 y→x)。于是 Tx* = T(lim x_n) = lim T x_n = lim xn+1 = x*。

第三步(唯一性)。若 Tx*=x* 且 Ty*=y*:‖x*−y*‖ = ‖Tx*−Ty*‖ ≤ γ‖x*−y*‖。γ<1 时唯一可能是 ‖x*−y*‖=0,即 x*=y*。

第四步(速率)。‖xn+1−x*‖ = ‖Tx_n − Tx*‖ ≤ γ‖x_n−x*‖,归纳得 ‖x_n−x*‖ ≤ γ^n‖x₀−x*‖。再把这个界与第一步的柯西控制结合(x_m → x* 代入 ‖x_m−x_n‖ ≤ γ^n/(1−γ)·‖x₁−x₀‖ 取 m→∞),得误差界 ‖x_n−x*‖ ≤ γ^n/(1−γ)·‖x₁−x₀‖。∎

注证明结构是迭代法分析的标准模板:柯西 → 极限存在 → 极限是不动点 → 唯一 → 速率。任何「某某迭代收敛」的证明都是这个模板的变体,包括 T10 的随机逼近(那里多了噪声,需要额外的手段)。

定理 5.2 贝尔曼最优算子是 γ-压缩

在 (ℝ|S|, ‖·‖_∞) 上,贝尔曼最优算子 T(以及任意固定策略的贝尔曼期望算子 T^π)满足 ‖TV − TW‖_∞ ≤ γ‖V−W‖_∞。

证

逐状态展开。对每个 s,max 的压缩性:|max_a f(a) − max_a g(a)| ≤ max_a |f(a)−g(a)|(max 是 1-Lipschitz 的:max_a f ≥ max_a g 的某项 = f(a) ≥ g(a),逐点比较即得)。

|(TV)(s)−(TW)(s)| = |max_a Σs' p(s'|s,a)[r+γV(s')] − max_a Σs' p(s'|s,a)[r+γW(s')]|
≤ max_a |γ Σs' p(s'|s,a)(V(s')−W(s'))| ≤ γ max_a Σs' p(s'|s,a)·‖V−W‖_∞ = γ‖V−W‖_∞

第二个不等号用了 |V(s')−W(s')| ≤ ‖V−W‖_∞ 逐点代入,第三个用了概率和为 1。对 s 取 max 即得算子范数意义的不等式。∎

注γ 从哪里进来:折扣项 γV(s') 让「下一层的值」打 γ 折,max 和期望都是 1-Lipschitz 的,所以 γ 一路穿过所有运算直达结论。γ=1 时链条断裂——T7 的实验会看到那时连 V* 都可能不存在。

手算一遍

γ=0.9,初值 V₀=0,要求最终值函数误差 ≤0.01。用定理 5.1 的界估计值迭代需要多少次迭代?(该问题实测 ‖V₁−V₀‖_∞ = 1)

  1. 定理 5.1 误差界:‖V_k − V*‖_∞ ≤ γ^k/(1−γ)·‖V₁−V₀‖ = 0.9^k/0.1 × 1。
  2. 要求 0.9^k/0.1 ≤ 0.01,即 0.9^k ≤ 0.001。
  3. [object Object]
  4. 对照另一条界(定理 5.1 第四步的 γ^n 形式需要知道 ‖x₀−x*‖,而 x* 未知时用不了)——工程上用柯西停机:‖V_k − Vk−1‖ ≤ (1−γ)/γ · 精度 时可停。
答

k = 66 步保证误差 ≤0.01。注意这是「保证」,实测(见下)误差下降速度比界快——界必须覆盖最坏情况。停止条件的换算 (1−γ)/γ·精度 出自 ‖V_k−Vk−1‖ ≤ γ^k/(1−γ)‖V₁−V₀‖ 与 ‖V_k−V*‖ ≤ γ/(1−γ)·‖V_k−Vk−1‖ 两式的组合。

实跑一遍

数字出处

4 状态链(状态 3 吸收、每步奖励 1),γ=0.9,从 V₀=0 值迭代。实测相邻迭代差与理论界:

  • k=2: ‖ΔV‖=0.900,收缩比 0.9000(理论界 9.000)
  • k=5: ‖ΔV‖=0.656,收缩比 0.9000(理论界 6.561)
  • k=10: ‖ΔV‖=0.387,收缩比 0.9000(理论界 3.874)
  • k=20: ‖ΔV‖=0.135,收缩比 0.9000(理论界 1.351)
  • k=39: ‖ΔV‖=0.018 —— 收缩比每一步都恰好等于 γ=0.9000,而理论界松约 10 倍

映射回强化学习

这里的对象RL 里的对应物站内用法
压缩系数 γ折扣因子:既定义问题(远期奖励权重)又保证算法收敛用法 →
不动点唯一性V* 唯一存在——「最优值函数」这个词合法的前提用法 →
误差界值迭代的停止条件:‖V_k−Vk−1‖ ≤ (1−γ)/γ · 精度用法 →
γ=1 断裂无折扣时 T 可能不是压缩,V* 可能不存在——发散的数学根源用法 →

边界:这一篇停在哪里

本篇停在哪里:非完备空间上的不动点定理、加权范数压缩(能加速收敛的技巧)、异步值迭代的收敛条件,都不讲。够用判据:有限状态 + γ<1,本篇定理直接适用。

自测 4 题

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

01Banach 定理的四个证明步骤分别解决什么问题?

① 柯西列:保证序列「有资格收敛」;② 极限是不动点:迭代有意义;③ 唯一性:不动点这个词能用单数;④ 速率:给出停机条件和迭代次数预算。四步缺一不可,缺②③的「数值稳定」不等于收敛。

02为什么贝尔曼算子的压缩系数恰好是 γ?max 和期望不会放大误差吗?

max 是 1-Lipschitz(不会放大),期望对概率凸组合也是 1-Lipschitz(不会放大)。唯一引入系数的是折扣 γ 乘在下一层值上。γ<1 时整条链压缩,γ=1 时链是 1-Lipschitz 的——不放大但也不收缩,可能不收敛。

03值迭代停机条件为什么是 ‖V_k−Vk−1‖ ≤ (1−γ)/γ·精度,而不是直接 ≤ 精度?

因为 ‖V_k−Vk−1‖ 小不直接等于 ‖V_k−V*‖ 小:‖V_k−V*‖ ≤ γ/(1−γ)·‖V_k−Vk−1‖。γ=0.9 时迭代差被放大约 9 倍才是真实误差,所以迭代差要先乘 (1−γ)/γ 压回去。直接拿迭代差当误差会提前停机 9 倍的精度。

04如果 γ=1 且存在每步奖励 1 的自环状态,值迭代会怎样?

V 在该状态的值每步加 1,发散到无穷(T7 的实测:30 步迭代 V=30)。压缩性失效(γ=1 不是压缩),V* 不存在。这不是数值问题,是问题本身没有有限答案——必须加折扣、终止、或改为平均奖励准则。

接着看

全系列 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 分钟