《强化学习的数学原理》【学习笔记13】附录 C：序列的收敛性——算法收敛的理论基础

《强化学习的数学原理》赵世钰 著 · 附录 C

RL 算法都是迭代过程：$v_{k+1} = f(v_k)$、$\theta_{t+1} = \theta_t + \alpha_t g_t$。这些迭代"收敛"是什么意思？附录 C 给出了严格的收敛定义和判据。

一、确定性序列的收敛性

各种收敛定义

逐点收敛：$x_n \to x$，如果对任意 $\epsilon > 0$，存在 $N$ 使得 $n > N \implies |x_n - x| < \epsilon$。

线性收敛（Q-线性）：$|x_{n+1} - x^*| \leq c |x_n - x^*|$，$0 < c < 1$。

超线性收敛：$\frac{|x_{n+1} - x^*|}{|x_n - x^*|} \to 0$。

二次收敛：$|x_{n+1} - x^*| \leq c |x_n - x^*|^2$。

在 RL 中的对应：

• 值迭代是线性收敛（压缩映射，收敛率 $\gamma$）
• 策略迭代是有限步收敛（比任何收敛率都快）
• 牛顿法是二次收敛（但 RL 中很少用）

二、向量序列的收敛性

范数

$\|x\|$ 满足：非负性、齐次性、三角不等式。

常用范数：

• $\|x\|_\infty = \max_i |x_i|$（无穷范数，RL 中最常用）
• $\|x\|_1 = \sum_i |x_i|$
• $\|x\|_2 = \sqrt{\sum_i x_i^2}$

范数等价性

有限维空间中所有范数等价——在一个范数下收敛，在所有范数下都收敛。

为什么 RL 偏爱无穷范数？ 因为压缩映射定理在无穷范数下最自然：$\|Pv\|_\infty \leq \|v\|_\infty$（概率矩阵的范数性质）。

三、矩阵序列的收敛性

矩阵范数

$$\|A\| = \sup_{x \neq 0} \frac{\|Ax\|}{\|x\|}$$

谱半径

$$\rho(A) = \max_i |\lambda_i(A)|$$

收敛判据

$A^k \to 0 \iff \rho(A) < 1$

在 RL 中的应用：值迭代的收敛性等价于 $\rho(\gamma P_\pi) < 1$。因为 $P_\pi$ 是概率矩阵（谱半径为 1），$\gamma < 1$，所以 $\rho(\gamma P_\pi) = \gamma < 1$，保证收敛。

四、随机序列的收敛性

这是附录 C 的重点——RL 算法产生的是随机序列（因为样本是随机的）。

四种收敛模式

1. 依概率收敛（Convergence in Probability）

$$X_n \xrightarrow{P} X \iff \forall \epsilon > 0: P(|X_n - X| > \epsilon) \to 0$$

“偏离任意小的概率趋于零”。

2. 几乎必然收敛（Almost Sure Convergence）

$$X_n \xrightarrow{a.s.} X \iff P\left(\lim_{n \to \infty} X_n = X\right) = 1$$

“以概率 1 收敛”。比依概率收敛更强。

3. Lp 收敛

$$X_n \xrightarrow{L^p} X \iff \mathbb{E}[|X_n - X|^p] \to 0$$

$p = 2$ 时叫均方收敛。

4. 依分布收敛（Convergence in Distribution）

$$X_n \xrightarrow{d} X \iff F_n(x) \to F(x) \text{ 在 } F \text{ 连续点处}$$

最弱的收敛模式。

强弱关系

Lp 收敛 ⟹ 几乎必然收敛 ⟹ 依概率收敛 ⟹ 依分布收敛

（注意：$L^p$ 和几乎必然之间没有一般性的蕴含关系，但在某些条件下有。）

在 RL 中的对应：

• TD(0) 的收敛是几乎必然收敛（在 RM 条件下）
• Q-learning 的收敛也是几乎必然收敛
• 大数定律是几乎必然收敛（强大数定律）或依概率收敛（弱大数定律）

五、随机近似算法的收敛

Robbins-Monro 的收敛

$$w_{t+1} = w_t - \alpha_t g(w_t, X_t) \xrightarrow{a.s.} w^*$$

条件：

1. $\sum \alpha_t = \infty$, $\sum \alpha_t^2 < \infty$（步长条件）
2. $g$ 满足 Lipschitz 条件
3. 某些有界性条件

在 RL 中的应用

六、总结