03 - 贝尔曼方程：理论基础与数学推导¶

学习时间: 6-8小时 重要性: ⭐⭐⭐⭐⭐ 强化学习最核心的数学基础 前置知识: 线性代数、概率论基础、泛函分析（可选）

🎯 学习目标¶

完成本章后，你将能够： - 从数学上严格推导贝尔曼方程 - 理解贝尔曼算子的压缩映射性质 - 掌握值函数迭代的收敛性证明 - 理解最优性原理的数学基础 - 能够应用贝尔曼方程分析复杂问题

1. 贝尔曼方程的数学基础¶

1.1 值函数空间与范数¶

定义（值函数空间）：设 $\mathcal{V}$ 为所有有界实值函数 $V: \mathcal{S} \to \mathbb{R}$ 构成的空间。

定义（上确界范数）： $$\|V\|_\infty = \sup_{s \in \mathcal{S}} |V(s)|$$

$(\mathcal{V}, \|\cdot\|_\infty)$ 构成一个巴拿赫空间（Banach Space），即完备的赋范线性空间。

为什么重要？ - 为定义算子和研究收敛性提供数学框架 - 保证迭代方法的收敛性 - 允许我们使用泛函分析的工具

1.2 贝尔曼期望算子¶

定义（贝尔曼期望算子）：对于给定策略 $\pi$，定义算子 $T^\pi: \mathcal{V} \to \mathcal{V}$ 为：

\[(T^\pi V)(s) = \sum_a \pi(a|s) \sum_{s', r} p(s', r|s, a) [r + \gamma V(s')]\]

算子表示的优势：

Text Only

贝尔曼方程可以简洁地表示为：
V^π = T^π V^π

即：V^π 是算子 T^π 的不动点

1.3 压缩映射定理¶

定义（压缩映射）：设 $(X, d)$ 是度量空间，映射 $T: X \to X$ 称为压缩映射，如果存在 $\gamma \in [0, 1)$ 使得：

\[d(Tx, Ty) \leq \gamma \cdot d(x, y), \quad \forall x, y \in X\]

定理（Banach不动点定理）：

设 $(X, d)$ 是完备度量空间，$T: X \to X$ 是压缩映射，则： 1. $T$ 存在唯一不动点 $x^*$ 2. 对任意 $x_0 \in X$，迭代序列 $x_{n+1} = T x_n$ 收敛到 $x^*$ 3. 收敛速率：$d(x_n, x^*) \leq \frac{\gamma^n}{1-\gamma} d(x_1, x_0)$

这个定理是值迭代收敛性的理论基础！

2. 贝尔曼算子的压缩性证明¶

2.1 定理陈述¶

定理：贝尔曼期望算子 $T^\pi$ 是 $\mathcal{V}$ 上的压缩映射，压缩系数为 $\gamma$。

2.2 完整证明¶

证明：

设 $V_1, V_2 \in \mathcal{V}$，我们需要证明： $$\|T^\pi V_1 - T^\pi V_2\|_\infty \leq \gamma \|V_1 - V_2\|_\infty$$

步骤1：展开定义

对于任意状态 $s$： \begin{align} (T^\pi V_1)(s) - (T^\pi V_2)(s) &= \sum_a \pi(a|s) \sum_{s', r} p(s', r|s, a) [r + \gamma V_1(s')] \ &\quad - \sum_a \pi(a|s) \sum_{s', r} p(s', r|s, a) [r + \gamma V_2(s')] \ &= \gamma \sum_a \pi(a|s) \sum_{s', r} p(s', r|s, a) [V_1(s') - V_2(s')] \end{align}

步骤2：取绝对值并放缩

\[\begin{align} |(T^\pi V_1)(s) - (T^\pi V_2)(s)| &\leq \gamma \sum_a \pi(a|s) \sum_{s', r} p(s', r|s, a) |V_1(s') - V_2(s')| \\ &\leq \gamma \sum_a \pi(a|s) \sum_{s', r} p(s', r|s, a) \|V_1 - V_2\|_\infty \\ &= \gamma \|V_1 - V_2\|_\infty \sum_a \pi(a|s) \sum_{s', r} p(s', r|s, a) \end{align}\]

步骤3：利用概率归一性

由于 $\sum_a \pi(a|s) = 1$ 且 $\sum_{s', r} p(s', r|s, a) = 1$：

\[|(T^\pi V_1)(s) - (T^\pi V_2)(s)| \leq \gamma \|V_1 - V_2\|_\infty\]

步骤4：取上确界

对上式关于 $s$ 取上确界：

\[\|T^\pi V_1 - T^\pi V_2\|_\infty \leq \gamma \|V_1 - V_2\|_\infty\]

证毕。

2.3 重要推论¶

推论1（存在唯一性）：对于任意策略 $\pi$，贝尔曼方程 $V = T^\pi V$ 存在唯一解 $V^\pi$。

推论2（收敛性）：值迭代 $V_{k+1} = T^\pi V_k$ 收敛到 $V^\pi$，且： $$\|V_k - V^\pi\|_\infty \leq \frac{\gamma^k}{1-\gamma} \|V_1 - V_0\|_\infty$$

推论3（收敛速率）： - 指数收敛，速率由 $\gamma$ 决定 - $\gamma$ 越小，收敛越快 - 当 $\gamma \approx 1$ 时，收敛很慢

3. 贝尔曼最优算子¶

3.1 定义与性质¶

定义（贝尔曼最优算子）：定义算子 $T^*: \mathcal{V} \to \mathcal{V}$ 为：

\[(T^* V)(s) = \max_a \sum_{s', r} p(s', r|s, a) [r + \gamma V(s')]\]

定理：$T^*$ 也是压缩映射，压缩系数为 $\gamma$。

证明概要：利用不等式 $|\max_x f(x) - \max_x g(x)| \leq \max_x |f(x) - g(x)|$，其余证明与 $T^\pi$ 类似。

3.2 最优值函数的不动点¶

定理：$V^*$ 是 $T^*$ 的唯一不动点，即 $V^* = T^* V^*$。

证明：

存在性：由Banach不动点定理直接得到。

最优性证明：

设 $V$ 是任意不动点，我们需要证明 $V = V^*$。

对于任意策略 $\pi$： $$T^\pi V \leq T^* V = V$$

由单调性（后面证明），对任意 $k$： $$(T^\pi)^k V \leq V$$

取极限 $k \to \infty$： $$V^\pi \leq V$$

由于这对任意 $\pi$ 成立，故 $V^* \leq V$。

另一方面，设 $\pi^*$ 是贪心策略（关于 $V$），则： $$T^{\pi^*} V = T^* V = V$$

因此 $V = V^{\pi^*} \leq V^*$。

综上，$V = V^*$。

证毕。

4. 贝尔曼算子的其他重要性质¶

4.1 单调性¶

定理（单调性）：如果 $V_1 \leq V_2$（逐点），则 $T^\pi V_1 \leq T^\pi V_2$ 且 $T^* V_1 \leq T^* V_2$。

证明：直接由定义可得，因为所有操作（期望、最大化）都保持序关系。

应用： - 策略改进的数学基础 - 证明值迭代的单调收敛

4.2 次优界¶

定理（次优界）：对于任意 $V \in \mathcal{V}$： $$\|V^* - V^{\pi_V}\|_\infty \leq \frac{2\gamma}{1-\gamma} \|V^* - V\|_\infty$$

其中 $\pi_V$ 是关于 $V$ 的贪心策略。

意义：值函数的误差与策略性能的关系。

4.3 收缩性质的应用¶

误差传播分析：

假设我们用近似值函数 $\hat{V}$ 代替真实 $V^\pi$，则：

\[\|V^\pi - \hat{V}\|_\infty \leq \frac{1}{1-\gamma} \|T^\pi \hat{V} - \hat{V}\|_\infty\]

这称为贝尔曼残差界。

5. 值迭代的收敛性分析¶

5.1 线性收敛速率¶

定理：值迭代 $V_{k+1} = T^* V_k$ 以线性速率收敛：

\[\|V_k - V^*\|_\infty \leq \gamma^k \|V_0 - V^*\|_\infty\]

证明：

\[\begin{align} \|V_{k+1} - V^*\|_\infty &= \|T^* V_k - T^* V^*\|_\infty \\ &\leq \gamma \|V_k - V^*\|_\infty \\ &\leq \gamma^{k+1} \|V_0 - V^*\|_\infty \end{align}\]

5.2 有限迭代后的策略质量¶

定理：设 $\pi_k$ 是关于 $V_k$ 的贪心策略，则：

\[\|V^* - V^{\pi_k}\|_\infty \leq \frac{2\gamma^{k+1}}{1-\gamma} \|V_0 - V^*\|_\infty\]

意义：经过 $k$ 次迭代后，得到的策略与最优策略的性能差距。

5.3 迭代复杂度¶

要达到 $\epsilon$-最优策略，需要迭代次数：

\[k \geq \frac{\log(\frac{2\|V_0 - V^*\|_\infty}{(1-\gamma)\epsilon})}{\log(1/\gamma)}\]

当 $\gamma \approx 1$ 时，$\log(1/\gamma) \approx 1-\gamma$，故：

\[k = O\left(\frac{1}{1-\gamma} \log\frac{1}{\epsilon}\right)\]

关键洞察：折扣因子越接近1，收敛越慢！

6. 策略迭代的收敛性¶

6.1 策略改进的严格性¶

定理（策略改进定理）：设 $\pi'$ 是关于 $V^\pi$ 的贪心策略，则：

\[V^{\pi'} \geq V^\pi\]

且如果 $\pi'$ 在某状态严格改进，则 $V^{\pi'} > V^\pi$（至少在一个状态）。

证明：

由贪心定义：$T^{\pi'} V^\pi = T^* V^\pi \geq T^\pi V^\pi = V^\pi$

由单调性：$(T^{\pi'})^k V^\pi \geq V^\pi$

取极限：$V^{\pi'} \geq V^\pi$

6.2 有限收敛性¶

定理：对于有限MDP，策略迭代在有限步内收敛到最优策略。

证明： - 策略空间是有限的（$|A|^{|S|}$ 个确定性策略） - 每次迭代严格改进（或已最优） - 因此最多有限步收敛

6.3 策略迭代 vs 值迭代¶

特性	策略迭代	值迭代
每次迭代代价	高（策略评估）	低（单步更新）
迭代次数	少（通常<100）	多（可能数千）
总计算量	可能更少	可能更多
实现	复杂	简单

7. 贝尔曼方程的变体与扩展¶

7.1 平均奖励情形¶

当 $\gamma = 1$ 且考虑平均奖励时：

\[\rho^\pi + h^\pi(s) = \sum_a \pi(a|s) \sum_{s', r} p(s', r|s, a) [r + h^\pi(s')]\]

其中 $\rho^\pi$ 是平均奖励，$h^\pi$ 是微分值函数。

特点： - 解不唯一（$h$ 可加减常数） - 需要额外的遍历性假设 - 收敛性分析更复杂

7.2 连续时间情形（HJB方程）¶

连续时间最优控制中，贝尔曼方程变为Hamilton-Jacobi-Bellman方程：

\[\rho = \max_a \left\{ r(s, a) + \sum_{s'} \frac{\partial V}{\partial s'} f(s, a, s') \right\}\]

这是偏微分方程，需要数值方法求解。

7.3 分布鲁棒优化¶

考虑模型不确定性时：

\[V(s) = \max_a \min_{p \in \mathcal{P}} \mathbb{E}_p [r + \gamma V(s')]\]

其中 $\mathcal{P}$ 是可能的转移概率集合。

8. 数值计算与实现细节¶

8.1 迭代停止准则¶

常用准则： 1. 绝对误差：$\|V_{k+1} - V_k\|_\infty < \epsilon$ 2. 相对误差：$\|V_{k+1} - V_k\|_\infty / \|V_k\|_\infty < \epsilon$ 3. 策略稳定：连续多轮策略不变

8.2 收敛诊断¶

问题：如何判断是否收敛？

方法： - 监控贝尔曼残差 $\|T^* V_k - V_k\|$ - 次优界估计 - 策略变化频率

8.3 高效实现技巧¶

Python

import numpy as np

def value_iteration_efficient(P, R, gamma, theta=1e-8, max_iter=10000):
    """
    高效的值迭代实现

    优化点：
    1. 原地更新减少内存
    2. 提前终止
    3. 收敛监控
    """
    n_states, n_actions = R.shape
    V = np.zeros(n_states)

    for iteration in range(max_iter):
        delta = 0

        # 原地更新
        for s in range(n_states):
            v = V[s]

            # 计算所有动作的Q值
            Q_s = np.zeros(n_actions)
            for a in range(n_actions):
                Q_s[a] = R[s, a] + gamma * np.dot(P[s, a], V)  # np.dot矩阵/向量点乘

            V[s] = np.max(Q_s)
            delta = max(delta, abs(v - V[s]))

        # 监控收敛
        if iteration % 100 == 0:
            residual = compute_bellman_residual(V, P, R, gamma)
            print(f"Iter {iteration}: delta={delta:.6f}, residual={residual:.6f}")

        # 提前终止
        if delta < theta:
            print(f"收敛于迭代 {iteration}")
            break

    # 提取最优策略
    policy = extract_greedy_policy(V, P, R, gamma)

    return V, policy

def compute_bellman_residual(V, P, R, gamma):
    """计算贝尔曼残差"""
    n_states, n_actions = R.shape
    residual = 0

    for s in range(n_states):
        Q_s = np.array([R[s, a] + gamma * np.dot(P[s, a], V)  # np.array创建NumPy数组
                        for a in range(n_actions)])
        residual = max(residual, abs(V[s] - np.max(Q_s)))

    return residual

9. 本章总结¶

核心理论框架¶

Text Only

贝尔曼方程的数学理论

├── 算子理论框架
│   ├── 贝尔曼期望算子 T^π
│   ├── 贝尔曼最优算子 T*
│   └── 压缩映射性质（压缩系数γ）
│
├── 收敛性理论
│   ├── Banach不动点定理
│   ├── 值迭代的线性收敛
│   ├── 策略迭代的有限收敛
│   └── 收敛速率分析
│
├── 误差分析
│   ├── 次优界
│   ├── 贝尔曼残差
│   └── 误差传播
│
└── 扩展
    ├── 平均奖励
    ├── 连续时间（HJB）
    └── 鲁棒优化

关键公式回顾¶

贝尔曼期望方程： $$V^\pi = T^\pi V^\pi$$

贝尔曼最优方程： $$V^* = T^* V^*$$

压缩性质： $$\|TV_1 - TV_2\| \leq \gamma \|V_1 - V_2\|$$

收敛速率： $$\|V_k - V^*\| \leq \gamma^k \|V_0 - V^*\|$$

✅ 自测问题¶

证明贝尔曼期望算子是压缩映射，并确定压缩系数。
如果折扣因子 $\gamma = 0.9$，要达到 $10^{-6}$ 精度，值迭代大约需要多少次迭代？
解释为什么策略迭代在有限MDP中一定收敛。
贝尔曼残差与实际值函数误差的关系是什么？
当 $\gamma \to 1$ 时，收敛速率如何变化？这对长程规划有什么启示？

📚 延伸阅读¶

经典文献¶

Bellman, R. (1957). Dynamic Programming. Princeton University Press.
动态规划的奠基之作
Puterman, M. L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming.
MDP理论的权威参考书
Bertsekas, D. P. (2017). Dynamic Programming and Optimal Control.
深入的理论分析和算法

数学基础¶

泛函分析：Kreyszig, Introductory Functional Analysis with Applications
不动点理论：Granas & Dugundji, Fixed Point Theory
随机逼近：Kushner & Yin, Stochastic Approximation Algorithms

掌握本章后，你已经具备了理解强化学习算法收敛性的数学基础。

→ 下一步：04-动态规划.md