原理层 T17 / 27 · 收敛与不动点
范数与不动点:「一定收敛」的出处
「值迭代一定收敛」不是经验事实,是 Banach 不动点定理的推论。贝尔曼最优算子在 sup 范数下是 γ-压缩——γ<1 是全部前提,γ=1 时一切保证消失。
一句话结论
压缩映射原理一句话:完备空间上,把点与点之间距离压缩到 γ<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₀‖。三角不等式求和:
γ^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),逐点比较即得)。
第二个不等号用了 |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)
- 定理 5.1 误差界:‖V_k − V*‖_∞ ≤ γ^k/(1−γ)·‖V₁−V₀‖ = 0.9^k/0.1 × 1。
- 要求 0.9^k/0.1 ≤ 0.01,即 0.9^k ≤ 0.001。
- [object Object]
- 对照另一条界(定理 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* 不存在。这不是数值问题,是问题本身没有有限答案——必须加折扣、终止、或改为平均奖励准则。