马尔可夫链与贝尔曼收缩 Markov Chains & Bellman Contraction
从天气随机演化到值函数收缩漏斗 — 特征向量与 Banach 压缩映射如何保证强化学习必然收敛
11.1 状态转移的无后效性：什么是马尔可夫链？
在第 10 步中，我们学习了贝叶斯公式与静态概率推断。但现实世界中，事件往往是随时间序列连续演化的。如果一个随机过程未来的状态只取决于「当前处于什么状态」，而与「过去通过什么路径到达当前状态」完全无关，这种特性就称为马尔可夫性质（无后效性 / Memorylessness）：
11.2 平稳分布：为什么混乱流动终将归于平衡？
设系统有有限个离散状态，转移概率写为方阵 $P$，其中第 $i$ 行第 $j$ 列的元素 $P_{ij} = P(S_{t+1}=j \mid S_t=i)$ 表示从状态 $i$ 跳转到状态 $j$ 的概率。设某一时刻的概率分布为行向量 $\pi_t$，经过一步转移后，新的概率分布为：
无论初始分布是多么极端（例如全城 100% 暴雨），只要转移矩阵 $P$ 满足遍历性（不可约且非周期），持续迭代后概率向量必然收敛到一个恒定不变的平衡态，称为平稳分布（Stationary Distribution） $\pi^*$：
从线性代数的视角看：移项得 $\pi^{*T} (P - I) = 0$。这说明平稳分布正好是转移矩阵 $P$ 对应特征值 $\lambda = 1$ 的左特征向量！根据佩隆-弗罗贝尼乌斯定理（Perron-Frobenius Theorem），随机转移矩阵的最大特征值必为 1，且对应的非负特征向量经过归一化后即为唯一的平稳概率分布。
🔬 交互实验 1：天气三状态马尔可夫链与平稳分布流动
模拟晴天 (Sunny)、阴天 (Cloudy) 和雨天 (Rainy) 三个状态之间的概率转移。点击单步演化或连续播放，观察极端初始分布如何像水流注平一样，迅速汇聚并锁定到唯一的平稳分布。
11.3 Banach 不动点定理：压缩映射与一维蛛网图
不仅是概率向量会收敛到平稳平衡态，更广义的迭代方程 $x_{k+1} = g(x_k)$ 在什么条件下一定会收敛到满足 $x^* = g(x^*)$ 的唯一解（不动点）？数学大师巴拿赫（Stefan Banach）给出了震撼的压缩映射不动点定理（Banach Fixed-Point Theorem）。
如果在度量空间中，映射 $g$ 能够将任意两点间的距离按严格小于 1 的比例 $L$ 压缩：
那么：① 必定存在且仅存在唯一的固定不动点 $x^*$ 使得 $g(x^*) = x^*$；② 从任意初始点 $x_0$ 出发不断应用映射迭代，序列必然以几何级数速率收缩汇聚到该点！几何上，在一维平面中这对应于切线斜率绝对值 $|g'(x)| \le L < 1$。我们可以通过蛛网迭代图（Spiderweb Plot）直观看见这种向心吸入过程。
🔬 交互实验 2：一维不动点蛛网迭代图 (Spiderweb Plot)
调节直线斜率 $L$（压缩常数）。当 $|L| < 1$ 时，迭代折线在函数与对角线 $y=x$ 之间螺旋收缩吸入唯一交点；当 $|L| \ge 1$ 时，折线迅速被向外甩出发散！
11.4 贝尔曼最优算子：值迭代必然收敛的几何证明
强化学习的核心是动态规划。定义贝尔曼最优算子 $T^*$ 作用于状态价值函数 $V$：
很多初学者常问：「为什么反复套用贝尔曼方程，数值就一定会收敛到最优值？为什么不会陷入死循环或无限发散？」
答案正是 Banach 压缩映射定理！在控制所有状态中最大误差的无穷范数（$\ell_\infty$ 范数，$\|V - U\|_\infty = \max_{s} |V(s) - U(s)|$）下，我们考察两个不同值函数 $U$ 和 $V$ 经过一次贝尔曼算子后的距离：
证明的关键逻辑仅有两步：① $\max$ 算子是非扩张的：$|\max_a f(a) - \max_a g(a)| \le \max_a |f(a) - g(a)|$；② 概率求和 $\sum_{s'} P(s'|s, a) = 1$ 保留了上界，而前置的折扣因子 $\gamma \in (0, 1)$ 将距离严格缩短为原来的 $\gamma$ 倍！由于 $\gamma < 1$，贝尔曼算子是一个严格的 $\gamma$-压缩映射，直接保证了无论初始价值向量设得多么离谱，反复迭代 $V_{k+1} = T^* V_k$ 必定以每轮误差缩小 $\gamma$ 倍的速度，几何收缩至唯一的 $V^*$！
🔬 交互实验 3：贝尔曼值函数空间收缩沙盘 (Value Space Funnel)
在 2D 状态空间中，绿色标记为真实最优解 $V^*$。点击「应用贝尔曼算子 T*」，观察无论起点多分散，所有候选方案如何以折扣率 $\gamma$ 比例同心缩向 $V^*$。
11.5 避坑指南：不可约、周期性与 γ=1 发散陷阱
11.6 全景映射：从 PageRank 到强化学习动态规划
| 应用领域 | 数学核心结构 | 物理与算法角色 |
|---|---|---|
| Google PageRank | 马尔可夫平稳分布 $\pi^T (d P + ((1-d)/N) E) = \pi^T$ | 网民在互联网随机漫游的稳态概率，直接度量网页重要性。 |
| 强化学习 (RL/ch03) | 贝尔曼最优算子 $T^*$ 与无穷范数 $\gamma$-收缩 | 保障策略评估与值迭代必然收敛到最优策略 $\pi^*$ 与 $V^*$。 |
| 生成模型 (Diffusion) | 连续时间马尔可夫链稳态高斯分布 | 正向加噪将复杂数据分布转化为纯高斯白噪声平稳态。 |
📚 参考文献与延伸阅读
- Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.), MIT Press, Ch. 3.5 & Ch. 4 — 贝尔曼方程与动态规划值迭代的收敛性推导。
- Bertsekas, D. P. (2012). Dynamic Programming and Optimal Control, Athena Scientific, Vol. II — 贝尔曼收缩映射算子与巴拿赫不动点定理的完备数学证明。
- Brin, S., & Page, L. (1998). The anatomy of a large-scale hypertextual Web search engine, Computer Networks — 利用马尔可夫链平稳分布评估网页重要性的 PageRank 奠基论文。
- 对照阅读 → RL 第 2 步 · 简化 MDP、RL 第 3 步 · 贝尔曼方程、RL 第 5 步 · TD 学习与值迭代。
理解检测 · 5 道双语自测题
检验你对马尔可夫转移、平稳分布、巴拿赫不动点与贝尔曼收缩定理的理解深度：