动态规划

动态规划

本节摘要:动态规划(Dynamic Programming, DP)是「会作弊的强化学习」——你已经知道转移函数和奖励函数,只需反复套用贝尔曼方程,直到 V 或 π 不再变化。Bellman 在 1957 年设计了它,至今仍定义着「最优」:当人们说「这个 MDP 的最优策略」时,他们指的就是 DP 会返回的那个策略。本节讲透两大算法——策略迭代(Policy Iteration,评估 + 改进交替)与价值迭代(Value Iteration,一把扫把式合并二者)——以及它们的统一框架广义策略迭代(GPI)。你会在带「打滑」的 GridWorld 上看到两者各 4~6 次外循环就收敛,产出 V*(0,0) ≈ -6。最后解释为什么 γ < 1 是收敛保证的关键(γ-压缩映射)。

对应原课程:Phase 9 · Lesson 02 · dynamic-programming(原英文 phases/09-reinforcement-learning/02-dynamic-programming/docs/en.md)。

学习目标

阅读完本节,你应当能够:

1. 区分策略迭代与价值迭代的迭代结构,并说明各自的代价与适用场景。
2. 用贝尔曼最优算子写出价值迭代,并解释它为何几何收敛。
3. 论证 γ < 1 带来的压缩映射(Contraction)保证——唯一不动点 + 几何收敛。
4. 把 DP 当作金标准,用 V* 校验采样方法(Q 学习、PPO)的实现是否正确。
5. 识别 DP 的状态空间上限(~10⁷),并知道何时该转向函数逼近(第 05 节起)。

一、问题与直觉

你有一个模型已知的 MDP:对任意「状态-动作」对,都能查询 P(s' | s, a) 和 R(s, a, s')。库存经理知道需求分布;棋类游戏有确定性转移;GridWorld 是四行 Python——你拥有一个模型。

无模型的 RL(Q 学习、PPO、REINFORCE)是为「没有模型、只能采样」的情形发明的。但当你有模型时,有更快、更精确的方法:动态规划。

2026 年你仍然需要 DP,有三个理由。第一,RL 研究里每一个表格型环境(GridWorld、FrozenLake、CliffWalking)都用 DP 求出金标准策略。第二,精确值能用来 debug 采样方法:如果 Q 学习对 V*(s_0) 的估计与 DP 答案差 30%,你的 Q 学习有 bug。第三,现代离线 RL 与规划方法(MCTS、AlphaZero 的搜索、第 10 节的基于模型的 RL)本质上都是在学到的或给定的模型上迭代一次贝尔曼回溯。

两种算法,都是贝尔曼不动点迭代

策略迭代:交替两个步骤,直到策略不再变化。

1. 评估:给定策略 π,反复套用 V(s) ← Σ_a π(a|s) Σ_{s',r} P(s',r|s,a) [r + γ V(s')] 直到收敛。
2. 改进:给定 V^π,把 π 改成对 V^π 的贪心策略:π(s) ← argmax_a Σ_{s',r} P(s',r|s,a) [r + γ V(s')]。

收敛是有保证的:每次改进要么保持 π 不变,要么严格提升某些状态的 V^π,且确定性策略空间有限。即便大状态空间,通常 5~20 次外循环就收敛。

价值迭代:把评估与改进压成一次扫掠,直接套贝尔曼最优性方程:

V(s) ← max_a Σ_{s',r} P(s',r|s,a) [r + γ V(s')]
​

反复迭代到 max_s |V_new(s) - V(s)| < ε,最后取贪心动作即得策略。每次迭代严格更快(无内层评估循环),但通常需要更多次迭代才能收敛。

γ < 1 为何关键:压缩映射

贝尔曼算子在上确界范数下是 γ-压缩:||T V - T V'||_∞ ≤ γ ||V - V'||_∞。压缩意味着唯一不动点 + 几何收敛。丢掉 γ < 1 就丢掉了这个保证——你需要有限视野或吸收型终点。

广义策略迭代(GPI)

统一框架。价值函数与策略锁在一个双向改进循环里;任何把两者推向相互一致的方法——异步价值迭代、修正策略迭代、Q 学习、Actor-Critic、PPO——都是 GPI 的实例。

💡 GPI 是本章后半所有深度 RL 算法的「心智模型」。看到 Actor-Critic、PPO,你就该想到「评估 + 改进」这对舞步,只是采样代替了枚举。

二、从零实现

沿用第 01 节的 4×4 GridWorld,并加一个随机变体:动作以概率 0.1 滑到垂直方向。

Step 1:构建 GridWorld MDP 模型

SLIP = 0.1

def transitions(state, action):
    if state == TERMINAL:
        return [(state, 0.0, 1.0)]
    outcomes = []
    for direction, prob in action_probs(action):
        outcomes.append((apply_move(state, direction), -1.0, prob))
    return outcomes
​

transitions(s, a) 返回一个 (s', r, p) 列表。这就是整个模型。

Step 2:策略评估

给定策略 π(s) = {动作: 概率},反复套贝尔曼方程直到 V 不再动:

def policy_evaluation(policy, gamma=0.99, tol=1e-6):
    V = {s: 0.0 for s in states()}
    while True:
        delta = 0.0
        for s in states():
            v = sum(pi_a * sum(p * (r + gamma * V[s_prime])
                              for s_prime, r, p in transitions(s, a))
                   for a, pi_a in policy(s).items())
            delta = max(delta, abs(v - V[s]))
            V[s] = v
        if delta < tol:
            return V
​

Step 3:策略改进

把 π 替换成对 V 的贪心策略。若 π 没变,就到了最优:

def policy_improvement(V, gamma=0.99):
    new_policy = {}
    for s in states():
        best_a = max(
            ACTIONS,
            key=lambda a: sum(p * (r + gamma * V[s_prime])
                              for s_prime, r, p in transitions(s, a)),
        )
        new_policy[s] = best_a
    return new_policy
​

Step 4:拼成策略迭代

def policy_iteration(gamma=0.99):
    policy = {s: "up" for s in states()}   # 任意起点
    for _ in range(100):
        V = policy_evaluation(lambda s: {policy[s]: 1.0}, gamma)
        new_policy = policy_improvement(V, gamma)
        if new_policy == policy:
            return V, policy
        policy = new_policy
​

在 4×4 上典型收敛:4~6 次外迭代。输出 V*(0,0) ≈ -6,以及一个严格递减步数的策略。

Step 5:价值迭代(单循环版本)

def value_iteration(gamma=0.99, tol=1e-6):
    V = {s: 0.0 for s in states()}
    while True:
        delta = 0.0
        for s in states():
            v = max(sum(p * (r + gamma * V[s_prime])
                       for s_prime, r, p in transitions(s, a))
                   for a in ACTIONS)
            delta = max(delta, abs(v - V[s]))
            V[s] = v
        if delta < tol:
            break
    policy = policy_improvement(V, gamma)
    return V, policy
​

同一个不动点,代码更少。

💡 两种算法都收敛到 V*。规则:小状态空间用价值迭代(代码少、易实现),大状态空间、外循环代价高时用策略迭代(外迭代次数少)。

三、框架对比

在 2026 年,DP 是正确性基线与各种规划器的内循环:

每次有人提到「最优价值函数」,他们指的就是「DP 不动点」。在论文里看到 V* 或 Q*,脑海里就该浮现这个循环。

与 stable-baselines3 / 教学库的对照

stable-baselines3 不直接提供 DP(它是深度 RL 库),但科研里常用的 gymnasium + 自写 DP 是验证手段——frozenlake 这种小型 MDP 几十行 Python 就能跑出精确 V*,再去和 SB3 训出来的 DQN 对比。这种「先求精确解、再校验采样解」的工作流,是 RL 工程师的基本素养。

四、可复用产物

本节产出一个可复用 skill(位于原课程 outputs/skill-dp-solver.md)。骨架:

---
name: dp-solver
description: 用策略迭代或价值迭代精确求解小型表格 MDP,并报告收敛行为。
version: 1.0.0
phase: 9
lesson: 2
tags: [rl, dynamic-programming, bellman]
---

给定一个模型已知的 MDP,输出:

1. 选择。策略迭代 vs 价值迭代。理由要挂到 |S|、|A|、γ。
2. 初始化。V_0、起始策略。对收敛的敏感度。
3. 停止。上确界范数容差 ε。预期扫把数。
4. 验证。精确算出 V*(s_0)。提取贪心策略。
5. 用途。这个基线将如何用于 debug/评估采样方法。

拒绝在状态空间 > 10⁷ 上跑 DP。
拒绝在没有上确界范数检查时声称收敛。
标记任何无限视野任务上 γ ≥ 1 为保证失效。
​

五、练习

1. 基础。 在 4×4 GridWorld 上跑价值迭代,γ ∈ {0.9, 0.99}。多少次扫把能让 max |ΔV| < 1e-6?把 V* 打印成 4×4 网格。
2. 进阶。 在随机 GridWorld(打滑概率 0.1)上对比策略迭代与价值迭代。统计:扫把数、墙钟时间、最终 V*(0,0)。哪个在迭代数上更快?在墙钟上呢?
3. 挑战。 实现修正策略迭代:评估阶段只跑 k 次扫把而非到收敛。对 k ∈ {1, 2, 5, 10, 50},画出 V*(0,0) 误差曲线。这条曲线告诉你评估 / 改进的取舍是什么?

六、常见陷阱

• 忘处理终点。 对吸收态套贝尔曼,它仍会挑一个什么都不改的「最优动作」。用 if s == terminal: V[s] = 0 守住。
• 范数选错。 用 max |V_new - V|,不要用平均。理论保证是在上确界范数上。
• 就地 vs 同步更新。 就地更新 V[s](高斯-赛德尔)比另开 V_new 字典(雅可比)收敛更快。生产代码用就地。
• 策略平局。 两个动作 Q 值相等时,argmax 每次可能不同地破平局,导致「策略稳定」检查震荡。用稳定的破平局(固定顺序中的第一个)。
• 状态空间爆炸。 DP 每次扫把是 O(|S| · |A|)。到 ~10⁷ 状态还行,再大就要函数逼近(第 05 节起)。

本节要点回顾

1. DP 是「模型已知的 RL」:能查询 P 与 R 时,迭代贝尔曼方程到收敛即可得到最优。
2. 策略迭代 = 评估 + 改进交替;价值迭代把两者合并成一把带 max 的扫把;两者收敛到同一个 V*。
3. GPI 是统一框架:任何把 V 与 π 推向相互一致的方法(Q 学习、Actor-Critic、PPO)都是它的实例。
4. γ < 1 是压缩映射:||T V - T V'||_∞ ≤ γ ||V - V'||_∞,保证唯一不动点 + 几何收敛。
5. DP 是正确性基线:论文里的 V*、Q* 就是指 DP 不动点;用来 debug 采样方法。
6. 就地更新比同步快,用上确界范数而非平均判收敛,固定破平局避免策略震荡。
7. 状态空间上限 ~10⁷,超过就要函数逼近——这是下一阶段(DQN 起步)的动机。

下一节,我们丢掉模型假设——只从完整回合中采样,用蒙特卡洛方法估计价值。这是从「精确」走向「可扩展」的第一步。