04 - 动态规划：理论、算法与复杂度分析¶

⚠️ 时效性说明：本章涉及前沿模型/价格/榜单等信息，可能随版本快速变化；请以论文原文、官方发布页和 API 文档为准。

学习时间: 5-6小时 重要性: ⭐⭐⭐⭐⭐ 求解MDP的经典方法 前置知识: 贝尔曼方程、压缩映射定理

🎯 学习目标¶

完成本章后，你将能够： - 理解动态规划的数学基础与收敛性 - 掌握同步与异步动态规划算法 - 分析DP算法的计算复杂度与收敛速率 - 理解近似动态规划的基本思想 - 能够针对实际问题选择合适的DP方法

1. 动态规划的数学基础¶

1.1 DP与贝尔曼方程的关系¶

动态规划的本质是通过迭代求解贝尔曼方程。

回顾：贝尔曼最优方程可以写成算子形式： $$V = T^* V$$

其中 $T^*$ 是贝尔曼最优算子： $$(T^* V)(s) = \max_a \sum_{s', r} p(s', r|s, a)[r + \gamma V(s')]$$

关键性质：$T^*$ 是压缩系数为 $\gamma$ 的压缩映射。

1.2 值迭代作为不动点迭代¶

值迭代 $V_{k+1} = T^* V_k$ 是不动点迭代的特例。

收敛性定理：

设 $V^*$ 是 $T^*$ 的唯一不动点，则： $$\|V_k - V^*\|_\infty \leq \gamma^k \|V_0 - V^*\|_\infty$$

证明：直接由压缩映射性质得到。

1.3 收敛速率分析¶

线性收敛： - 误差以几何速率衰减 - 收敛因子为折扣因子 $\gamma$ - 当 $\gamma \approx 1$ 时，收敛很慢

达到精度 $\epsilon$ 所需的迭代次数：

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

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

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

关键洞察： - 折扣因子越接近1，收敛越慢 - 这与"长期规划更难"的直觉一致

2. 同步动态规划¶

2.1 同步值迭代（Synchronous VI）¶

算法：

Text Only

同步值迭代
─────────────────────────────────
输入：MDP模型，折扣因子γ，阈值θ
输出：最优值函数V*，最优策略π*

初始化：V(s) = 0 对所有s

重复直到收敛：
    对每个状态s（并行或顺序）：
        V_new(s) = max_a Σ_{s',r} p(s',r|s,a)[r + γV(s')]

    V ← V_new  （同步更新）

    如果 ||V - V_old|| < θ：停止

返回 V

特点： - 每次迭代更新所有状态 - 需要存储两个值函数数组 - 收敛速度稳定

2.2 同步策略迭代¶

算法结构：

Text Only

策略迭代 = 策略评估 + 策略改进（循环）

策略评估的内循环： - 需要多次迭代直到收敛 - 每次评估的计算复杂度：$O(|S|^2 |A|)$ - 评估收敛需要 $O(\frac{1}{1-\gamma})$ 次迭代

总复杂度分析： - 每次策略评估：$O(\frac{|S|^2 |A|}{1-\gamma})$ - 策略改进：$O(|S|^2 |A|)$ - 策略迭代次数：通常远小于值迭代

2.3 Gauss-Seidel值迭代¶

改进：使用最新更新的值，而不是上一轮的所有值。

Text Only

Gauss-Seidel值迭代
─────────────────────────────────
对每个状态s（按某种顺序）：
    V(s) = max_a Σ_{s',r} p(s',r|s,a)[r + γV(s')]
    （使用已经更新的V值）

优势： - 更快的收敛（经验上） - 只需要一个数组（原地更新） - 仍然保证收敛

收敛性：虽然收敛速率难以理论分析，但实践中通常比同步VI快2-3倍。

3. 异步动态规划¶

3.1 动机与问题¶

同步DP的问题：

Text Only

├── 每次迭代需要更新所有状态
├── 计算量大（|S|可能很大）
├── 很多状态的更新是不必要的
└── 无法利用问题的结构

异步DP的思想：

不需要每次更新所有状态，可以按任意顺序更新，只要每个状态被无限次更新。

3.2 异步值迭代¶

算法框架：

Text Only

异步值迭代
─────────────────────────────────
输入：MDP模型，折扣因子γ
输出：最优值函数V*

初始化：V(s) = 0 对所有s

重复：
    选择某个状态s（任意选择策略）
    V(s) = max_a Σ_{s',r} p(s',r|s,a)[r + γV(s')]

直到满足停止条件

状态选择策略： 1. 循环扫描：按固定顺序循环 2. 优先扫描：优先更新变化大的状态 3. 实时更新：根据实际访问更新

3.3 收敛性定理¶

定理（异步VI收敛性）：

如果每个状态被无限次更新，则异步值迭代收敛到最优值函数 $V^*$。

证明概要： 1. 证明算子 $T^*$ 是单调的 2. 证明值函数有界 3. 应用压缩映射的异步版本

3.4 实时动态规划（Real-Time DP）¶

思想：

只更新智能体实际访问的状态，模拟"学习"过程。

算法：

Text Only

实时动态规划（RTDP）
─────────────────────────────────
输入：MDP模型，初始状态s₀，折扣因子γ
输出：最优值函数V*

初始化：V(s) = 0 对所有s

重复多个episode：
    s ← s₀
    当s不是终止状态：
        # 更新当前状态
        V(s) = max_a Σ_{s',r} p(s',r|s,a)[r + γV(s')]

        # 选择动作（贪心或探索）
        a = argmax_a Σ_{s',r} p(s',r|s,a)[r + γV(s')]

        # 执行动作，转移到下一状态
        s ← 从P(·|s,a)采样

特点： - 只更新访问过的状态 - 聚焦于"重要"状态 - 与强化学习的思想一致

收敛条件： - 每个状态-动作对被执行无限次 - 或者使用探索性开始

4. 优先级扫描（Prioritized Sweeping）¶

4.1 动机¶

观察： - 不同状态的更新对整体收敛的贡献不同 - 贝尔曼残差大的状态更需要更新 - 优先更新"重要"状态可以加速收敛

4.2 优先级定义¶

贝尔曼残差（Bellman Residual）： $$\text{Priority}(s) = |V(s) - \max_a \sum_{s', r} p(s', r|s, a)[r + \gamma V(s')]|$$

意义： - 残差大 = 当前估计与贝尔曼方程差距大 - 优先更新残差大的状态

4.3 算法¶

Text Only

优先级扫描
─────────────────────────────────
输入：MDP模型，折扣因子γ
输出：最优值函数V*

初始化：
    V(s) = 0 对所有s
    优先级队列Q = 空

# 初始化优先级
对每个状态s：
    priority = |V(s) - max_a Q(s,a)|
    将s以优先级priority加入Q

当Q非空：
    s = Q.pop()  # 取出优先级最高的状态

    # 更新状态s
    V_old = V(s)
    V(s) = max_a Σ_{s',r} p(s',r|s,a)[r + γV(s')]

    # 更新前驱状态的优先级
    对每个可能转移到s的前驱状态s'：
        重新计算priority(s')
        更新Q中的优先级

4.4 性能分析¶

优势： - 通常比标准VI快数倍 - 特别适合稀疏转移的MDP - 可以聚焦于目标状态附近

复杂度： - 维护优先级队列：$O(\log |S|)$ 每次操作 - 但收敛所需的更新次数显著减少

5. 计算复杂度分析¶

5.1 时间复杂度¶

算法	每次迭代	收敛迭代次数	总时间复杂度
值迭代	$O(\lvert S\rvert^2 \lvert A\rvert)$	$O(\frac{1}{1-\gamma} \log \frac{1}{\epsilon})$	$O(\frac{\lvert S\rvert^2 \lvert A\rvert}{1-\gamma} \log \frac{1}{\epsilon})$
策略迭代	$O(\lvert S\rvert^2 \lvert A\rvert)$（评估）	通常 $O(\lvert S\rvert)$ 次策略改进	$O(\frac{\lvert S\rvert^3 \lvert A\rvert}{1-\gamma})$（最坏情况）
优先级扫描	$O(\lvert S\rvert \lvert A\rvert + \log \lvert S\rvert)$	通常比VI少10-100倍	实践中往往最快

5.2 空间复杂度¶

算法	空间复杂度	说明
同步VI	$O(\lvert S\rvert)$	需要两个值函数数组
Gauss-Seidel	$O(\lvert S\rvert)$	原地更新，一个数组
策略迭代	$O(\lvert S\rvert \lvert A\rvert)$	需要存储策略和值函数
优先级扫描	$O(\lvert S\rvert)$	需要优先级队列

5.3 复杂度下界¶

定理（VI下界）：对于某些MDP，值迭代需要 $\Omega(\frac{1}{1-\gamma})$ 次迭代才能收敛。

含义： - 值迭代的收敛速率在一般情况下是紧的 - 长期规划问题（$\gamma \approx 1$）本质上是困难的

6. 近似动态规划基础¶

6.1 动机¶

维度灾难： - 状态空间 $|S|$ 可能非常大或连续 - 无法存储所有状态的值 - 需要函数近似

6.2 近似值迭代¶

思想：用近似值函数 $\hat{V}$ 代替精确值函数。

算法：

Text Only

近似值迭代
─────────────────────────────────
输入：MDP模型，函数近似器，折扣因子γ
输出：近似最优值函数V̂

初始化：V̂₀（参数化函数）

对k = 0, 1, 2, ...：
    # 计算目标值
    对每个状态s（采样）：
        y(s) = max_a Σ_{s',r} p(s',r|s,a)[r + γV̂ₖ(s')]

    # 函数拟合
    V̂ₖ₊₁ = argmin_{V̂} ||V̂ - y||²

    （使用监督学习方法）

6.3 误差传播分析¶

定理（近似误差界）：设 $\epsilon$ 是每步的近似误差，则： $$\|\hat{V} - V^*\|_\infty \leq \frac{\epsilon}{1-\gamma}$$

意义： - 近似误差被放大 $1/(1-\gamma)$ 倍 - 长期规划对近似误差更敏感

6.4 与强化学习的联系¶

Text Only

精确DP → 近似DP → 强化学习

├── 精确DP：已知模型，精确值函数
├── 近似DP：已知模型，近似值函数
└── 强化学习：未知模型，近似值函数

7. 实际应用与实现技巧¶

7.1 稀疏矩阵优化¶

观察： - 很多MDP的转移矩阵是稀疏的 - 每个状态只转移到少数几个状态

优化：

Python

# 稀疏表示
# 不用：P[s][a][s_next]（稠密，O(|S|²|A|)）
# 而用：transitions[s][a] = [(s_next, prob, reward), ...]

def sparse_value_iteration(transitions, gamma, theta=1e-8):
    """
    稀疏值迭代
    transitions: {s: {a: [(s_next, prob, reward), ...]}}
    """
    states = list(transitions.keys())
    V = {s: 0.0 for s in states}

    while True:
        delta = 0
        for s in states:
            v = V[s]

            # 只遍历实际可能的转移
            max_q = float('-inf')
            for a, next_states in transitions[s].items():
                q = sum(prob * (reward + gamma * V[s_next])
                       for s_next, prob, reward in next_states)
                max_q = max(max_q, q)

            V[s] = max_q
            delta = max(delta, abs(v - V[s]))

        if delta < theta:
            break

    return V

7.2 并行化¶

并行策略评估： - 每个状态的更新是独立的 - 可以使用GPU并行计算 - 特别适合大规模MDP

7.3 检查点与恢复¶

长时间运行的DP： - 定期保存值函数 - 支持中断和恢复 - 监控收敛进度

8. 本章总结¶

动态规划算法谱系¶

Text Only

动态规划方法

├── 同步方法
│   ├── 值迭代（VI）
│   ├── 策略迭代（PI）
│   └── Gauss-Seidel VI
│
├── 异步方法
│   ├── 异步VI
│   ├── 实时DP（RTDP）
│   └── 优先级扫描
│
└── 近似方法
    ├── 近似VI
    ├── 近似PI
    └── 与RL的结合

复杂度对比¶

Text Only

时间复杂度：
├── VI: O(|S|²|A|/(1-γ) · log(1/ε))
├── PI: O(|S|³|A|/(1-γ))（最坏情况）
└── 优先级扫描: 实践中通常最快

空间复杂度：
└── 都是 O(|S|) 或 O(|S||A|)

选择指南¶

场景	推荐算法
小规模MDP	策略迭代
大规模稀疏MDP	优先级扫描
在线学习	实时DP
并行计算	同步VI（GPU）
连续状态空间	近似DP

✅ 自测问题¶

证明值迭代的收敛速率是 $O(\gamma^k)$。
异步DP与同步DP的主要区别是什么？异步DP的收敛条件是什么？
优先级扫描为什么能加速收敛？什么情况下效果最明显？
当 $\gamma = 0.99$ 时，要达到 $10^{-6}$ 精度，值迭代大约需要多少次迭代？
近似DP的误差如何传播？这对函数近似有什么启示？

📚 延伸阅读¶

经典文献¶

Bertsekas, D. P. (2017). Dynamic Programming and Optimal Control (Vol. 1 & 2).
动态规划的权威教材
Bertsekas, D. P., & Tsitsiklis, J. N. (1996). Neuro-Dynamic Programming.
近似动态规划与神经网络的结合
Moore, A. W., & Atkeson, C. G. (1993). Prioritized Sweeping.
优先级扫描的原始论文

前沿研究¶

异步随机逼近：Tsitsiklis, Asynchronous Stochastic Approximation
分布式DP：Parallel and Distributed Computation
连续状态空间ADP：Powell, Approximate Dynamic Programming

掌握本章后，你能够针对实际问题选择和实现合适的动态规划算法。

→ 下一步：05-蒙特卡洛方法.md

算法	每次迭代	收敛迭代次数	总时间复杂度
值迭代	\(O(\lvert S\rvert^2 \lvert A\rvert)\)	\(O(\frac{1}{1-\gamma} \log \frac{1}{\epsilon})\)	\(O(\frac{\lvert S\rvert^2 \lvert A\rvert}{1-\gamma} \log \frac{1}{\epsilon})\)
策略迭代	\(O(\lvert S\rvert^2 \lvert A\rvert)\)（评估）	通常 \(O(\lvert S\rvert)\) 次策略改进	\(O(\frac{\lvert S\rvert^3 \lvert A\rvert}{1-\gamma})\)（最坏情况）
优先级扫描	\(O(\lvert S\rvert \lvert A\rvert + \log \lvert S\rvert)\)	通常比VI少10-100倍	实践中往往最快

算法	空间复杂度	说明
同步VI	\(O(\lvert S\rvert)\)	需要两个值函数数组
Gauss-Seidel	\(O(\lvert S\rvert)\)	原地更新，一个数组
策略迭代	\(O(\lvert S\rvert \lvert A\rvert)\)	需要存储策略和值函数
优先级扫描	\(O(\lvert S\rvert)\)	需要优先级队列