压缩映射定理

压缩映射定理的形式化定义（巴拿赫不动点定理）

压缩映射定理，也称为巴拿赫不动点定理 (Banach Fixed-Point Theorem)，是泛函分析中的一个核心结果。

1. 概念定义：度量空间 (Metric Space)

该定理的前提是必须在一个完备度量空间 (Complete Metric Space) 上进行讨论。

• 度量空间 $(\mathcal{X},d)$： $\mathcal{X}$ 是一个集合， $d:\mathcal{X}\times \mathcal{X}\to \mathbb{R}$ 是一个度量（距离函数），满足非负性、同一性、对称性和三角不等式。
• 完备性 (Completeness)： 空间中的所有柯西序列 (Cauchy sequence) 都收敛于空间内的一个点。 (例如，实数空间 $\mathbb{R}$ 在标准度量下是完备的)。

在强化学习中，值函数空间（如 $v_{\pi }$ 向量或 $Q_{\pi }$ 矩阵）通常是一个完备度量空间，度量可以是无穷范数 $d(\mathbf{x},\mathbf{y})=\Vert \mathbf{x}-\mathbf{y}{\Vert }_{\infty }$。

2. 核心定义：压缩映射 (Contraction Mapping)

设 $f:\mathcal{X}\to \mathcal{X}$ 是一个从度量空间 $\mathcal{X}$ 到自身的映射。如果存在一个常数 $\gamma \in [0,1)$，使得对于空间中任意两点 $x_1,x_2\in \mathcal{X}$，都有：

$$d(f(x_1),f(x_2))\le \gamma \cdot d(x_1,x_2)$$

则称 $f$ 是一个压缩映射，$\gamma$ 称为压缩系数 (Contraction Factor)。

物理意义： 压缩映射 $f$ 会将空间中任意两点之间的距离至少压缩 $\gamma$ 倍。

阶段二：压缩映射定理的内容解析

压缩映射定理给出了关于方程 $x=f(x)$ 的解（不动点 $x^{\ast }$）的三个关键结论：

1. 存在性 (Existence)

结论： 存在一个唯一的点 $x^{\ast }\in \mathcal{X}$ 满足 $x^{\ast }=f(x^{\ast })$。

意义： 在 RL 中，这意味着策略评估的贝尔曼期望方程 $\mathbf{v}={\mathcal{T}}_{\pi }(\mathbf{v})$ 和寻找最优值函数的贝尔曼最优方程 ${\mathbf{v}}^{\ast }={\mathcal{T}}^{\ast }({\mathbf{v}}^{\ast })$ 必定有解。

2. 唯一性 (Uniqueness)

结论： 这个不动点 $x^{\ast }$ 是唯一的。

意义： 策略 $\pi$ 对应的状态值函数 $v_{\pi }$ 是唯一的；最优策略对应的最优值函数 $v^{\ast }$ 也是唯一的。这保证了我们的目标是明确的。

3. 算法与收敛性 (Algorithm & Convergence)

结论： 对于任意初始点 $x_0\in \mathcal{X}$，通过迭代序列 $x_{k+1}=f(x_k)$ 产生的序列 $\{x_k\}$ 必然收敛到不动点 $x^{\ast }$。

$$\underset{k\to \infty }{\lim }{x}_k=x^{\ast }$$

更进一步，收敛速度是指数级 (exponentially fast) 的，由以下误差界限给出：

$$d(x_k,x^{\ast })\le \frac{{\gamma }^k}{1-\gamma }d(x_0,x_1)$$

或

$$d(x_k,x^{\ast })\le {\gamma }^{k}d(x_0,x^{\ast })$$

意义： 这是值迭代（Value Iteration）和策略评估（Policy Evaluation）算法收敛性的根本保障。它不仅保证了收敛，还量化了收敛速度，这个速度由压缩系数 $\gamma$ 决定。

---

阶段三：压缩映射定理在强化学习中的应用（贝尔曼操作符）

在 RL 中，贝尔曼方程被视为一个映射关系 $x=f(x)$，这里的 $x$ 就是值函数 $\mathbf{v}$。

我们定义贝尔曼期望操作符 (Bellman Expectation Operator) ${\mathcal{T}}_{\pi }$：

$${\mathcal{T}}_{\pi }(\mathbf{v})={\mathbf{r}}_{\pi }+\gamma {\mathbf{P}}_{\pi }\mathbf{v}$$

我们前面讨论的策略评估迭代 ${\mathbf{v}}_{k+1}={\mathbf{r}}_{\pi }+\gamma {\mathbf{P}}_{\pi }{\mathbf{v}}_k$ 就是 ${\mathbf{v}}_{k+1}={\mathcal{T}}_{\pi }({\mathbf{v}}_k)$。

证明 ${\mathcal{T}}_{\pi }$ 是一个压缩映射

我们需要证明 ${\mathcal{T}}_{\pi }$ 在无穷范数 $\Vert \cdot {\Vert }_{\infty }$ 下是一个压缩映射，且压缩系数为 $\gamma$。

设 ${\mathbf{v}}_1$ 和 ${\mathbf{v}}_2$ 是值函数空间中的任意两个向量。

我们计算 ${\mathcal{T}}_{\pi }({\mathbf{v}}_1)$ 和 ${\mathcal{T}}_{\pi }({\mathbf{v}}_2)$ 之间的距离：

$$\Vert {\mathcal{T}}_{\pi }({\mathbf{v}}_1)-{\mathcal{T}}_{\pi }({\mathbf{v}}_2){\Vert }_{\infty }$$

代入 ${\mathcal{T}}_{\pi }$ 的定义：

$$=\Vert ({\mathbf{r}}_{\pi }+\gamma {\mathbf{P}}_{\pi }{\mathbf{v}}_1)-({\mathbf{r}}_{\pi }+\gamma {\mathbf{P}}_{\pi }{\mathbf{v}}_2){\Vert }_{\infty }$$

${\mathbf{r}}_{\pi }$ 项抵消：

$$=\Vert \gamma {\mathbf{P}}_{\pi }{\mathbf{v}}_1-\gamma {\mathbf{P}}_{\pi }{\mathbf{v}}_2{\Vert }_{\infty }$$

提取常数 $\gamma$：

$$=\gamma \Vert {\mathbf{P}}_{\pi }({\mathbf{v}}_1-{\mathbf{v}}_2){\Vert }_{\infty }$$

利用矩阵范数与向量范数的关系 $\Vert \mathbf{Ax}{\Vert }_{\infty }\le \Vert \mathbf{A}{\Vert }_{\infty }\Vert \mathbf{x}{\Vert }_{\infty }$：

$$\le \gamma \Vert {\mathbf{P}}_{\pi }{\Vert }_{\infty }\Vert {\mathbf{v}}_1-{\mathbf{v}}_2{\Vert }_{\infty }$$

由于 ${\mathbf{P}}_{\pi }$ 是一个随机矩阵，其无穷范数 $\Vert {\mathbf{P}}_{\pi }{\Vert }_{\infty }=1$：

$$\le \gamma \cdot 1\cdot \Vert {\mathbf{v}}_1-{\mathbf{v}}_2{\Vert }_{\infty }$$

最终，我们得到：

$$\Vert {\mathcal{T}}_{\pi }({\mathbf{v}}_1)-{\mathcal{T}}_{\pi }({\mathbf{v}}_2){\Vert }_{\infty }\le \gamma \Vert {\mathbf{v}}_1-{\mathbf{v}}_2{\Vert }_{\infty }$$

因为 $\gamma <1$，所以 ${\mathcal{T}}_{\pi }$ 是一个压缩系数为 $\gamma$ 的压缩映射。

结论： 压缩映射定理的所有三个结论（存在性、唯一性、迭代收敛性）都适用于策略评估问题，严格证明了值迭代方法在折扣化 MDPs 中一定能找到唯一的 $v_{\pi }$ 解。