# 动态规划

> 来源：https://dqn.cn/basics/dynamic-programming ｜ 作者：DQN.CN 编辑部 ｜ 发布：2026-10-29 ｜ 更新：2026-10-30 ｜ 许可：CC BY-NC-SA 4.0（文字）/ MIT（代码）

> **要点速览**
>
> - 动态规划（DP）在环境模型已知时，通过反复应用贝尔曼方程来计算价值函数和最优策略。
> - 策略迭代交替进行“策略评估”（算出当前策略的价值）和“策略改进”（对价值取贪心），在有限 MDP 中有限步内收敛到最优策略。
> - 价值迭代把评估和改进合并为一步：V(s) ← max_a Σ p(s',r|s,a)[r + γV(s')]。
> - DP 的局限是需要完整的转移模型，且每次扫描所有状态，状态空间大时不可行；这引出了蒙特卡洛和 TD 等无模型方法。

动态规划（Dynamic Programming，DP）是在**已知环境模型**（转移概率与奖励函数）的前提下求解 MDP 的一类方法。它把 [贝尔曼方程](https://dqn.cn/basics/bellman) 变成迭代更新规则，通过**策略评估**与**策略改进**交替进行，最终收敛到最优策略。真实问题中模型往往未知、状态空间也太大，DP 很少直接使用；但它是理解后续所有方法的理论基础——蒙特卡洛、TD 学习乃至深度强化学习，都可以看作在“没有模型”或“状态太多”的条件下对 DP 的近似。

## 前提与思路

DP 需要两个条件：

1. **完整的环境模型** $p(s', r \mid s, a)$；
2. **状态和动作空间足够小**，可以逐个遍历。

核心思路：既然贝尔曼方程描述了价值函数的不动点，那就把它当作更新规则反复应用，直到收敛。

## 策略评估（Policy Evaluation）

### 迭代策略评估

给定策略 $\pi$，计算 $v_\pi$ 的问题称为**预测问题**。把贝尔曼期望方程改写成更新规则：

$$
v_{k+1}(s) \leftarrow \sum_a \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a)\left[r + \gamma v_k(s')\right], \quad \forall s \in \mathcal{S}
$$

从任意 $v_0$（通常全 0）开始，对所有状态反复做这个“期望更新”，直到最大变化量 $\Delta = \max_s |v_{k+1}(s) - v_k(s)|$ 小于阈值 $\theta$。

实践中常用**原地更新**（in-place）：只保留一个数组，更新 $v(s)$ 时立即使用其他状态的最新值。原地更新同样收敛，而且通常更快。

### 收敛性

由于贝尔曼期望算子是 $\gamma$-压缩映射，误差每轮至少缩小为原来的 $\gamma$ 倍：

$$
\|v_k - v_\pi\|_\infty \le \gamma^k \|v_0 - v_\pi\|_\infty
$$

因此 $\gamma$ 越接近 1，收敛越慢。

**扩展阅读：压缩映射与 DP 收敛性的证明**

**压缩映射。** 在完备度量空间 $(X, d)$ 上，若存在 $0 \le \gamma < 1$ 使得对任意 $x, y$ 有 $d(Tx, Ty) \le \gamma\, d(x, y)$，则称 $T$ 为 $\gamma$-压缩映射。**巴拿赫不动点定理**：压缩映射有唯一不动点 $x^*$，且从任意 $x_0$ 出发的迭代 $x_{k+1} = Tx_k$ 都满足 $d(x_k, x^*) \le \gamma^k d(x_0, x^*)$。价值函数所在的空间 $\mathbb{R}^{|\mathcal{S}|}$ 配上无穷范数 $\|v\|_\infty = \max_s |v(s)|$ 是完备的。

**贝尔曼期望算子是压缩映射。** 记 $(\mathcal{T}^\pi v)(s) = r_\pi(s) + \gamma \sum_{s'} P_\pi(s' \mid s)\, v(s')$。对任意 $u, v$：

$$
|(\mathcal{T}^\pi u)(s) - (\mathcal{T}^\pi v)(s)| = \gamma \left| \sum_{s'} P_\pi(s' \mid s)\,[u(s') - v(s')] \right| \le \gamma \sum_{s'} P_\pi(s' \mid s)\, \|u - v\|_\infty = \gamma \|u - v\|_\infty
$$

对 $s$ 取最大值即得 $\|\mathcal{T}^\pi u - \mathcal{T}^\pi v\|_\infty \le \gamma \|u - v\|_\infty$。由于 $v_\pi = \mathcal{T}^\pi v_\pi$ 是不动点，迭代策略评估满足 $\|v_k - v_\pi\|_\infty \le \gamma^k \|v_0 - v_\pi\|_\infty$。

**贝尔曼最优算子也是压缩映射。** 对 $(\mathcal{T}^* v)(s) = \max_a \left[r(s, a) + \gamma \sum_{s'} p(s' \mid s, a)\, v(s')\right]$，关键不等式是 $|\max_a f(a) - \max_a g(a)| \le \max_a |f(a) - g(a)|$，于是

$$
|(\mathcal{T}^* u)(s) - (\mathcal{T}^* v)(s)| \le \max_a \gamma \sum_{s'} p(s' \mid s, a)\, |u(s') - v(s')| \le \gamma \|u - v\|_\infty
$$

所以价值迭代以几何速度收敛到唯一的不动点 $v_*$。

**由此得到的实用结论。**

- 若要误差小于 $\epsilon$，大约需要 $k \ge \log(\|v_0 - v_*\|_\infty / \epsilon) / \log(1/\gamma)$ 轮，$\gamma = 0.99$ 时约是 $\gamma = 0.9$ 的 10 倍。
- 停止准则：若相邻两轮 $\|v_{k+1} - v_k\|_\infty < \delta$，由三角不等式可得 $\|v_{k+1} - v_*\|_\infty \le \dfrac{\gamma \delta}{1 - \gamma}$，可据此选择阈值。
- 策略迭代的收敛性：由策略改进定理，每轮策略单调不变差；有限 MDP 的确定性策略只有有限个，所以策略迭代在有限轮内终止于最优策略。

## 策略改进定理

有了 $v_\pi$，怎样得到一个更好的策略？对每个状态贪心地选择一步前瞻最好的动作：

$$
\pi'(s) = \arg\max_a q_\pi(s, a) = \arg\max_a \sum_{s', r} p(s', r \mid s, a)\left[r + \gamma v_\pi(s')\right]
$$

**策略改进定理**：若对所有 $s$ 都有 $q_\pi(s, \pi'(s)) \ge v_\pi(s)$，则 $v_{\pi'}(s) \ge v_\pi(s)$ 对所有 $s$ 成立。

证明思路是反复展开：

$$
\begin{aligned}
v_\pi(s) &\le q_\pi(s, \pi'(s)) = \mathbb{E}\left[R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t = s, A_t = \pi'(s)\right] \\
&\le \mathbb{E}_{\pi'}\left[R_{t+1} + \gamma q_\pi(S_{t+1}, \pi'(S_{t+1})) \mid S_t = s\right] \\
&\le \mathbb{E}_{\pi'}\left[R_{t+1} + \gamma R_{t+2} + \gamma^2 v_\pi(S_{t+2}) \mid S_t = s\right] \\
&\le \cdots \le v_{\pi'}(s)
\end{aligned}
$$

如果贪心改进后策略不再变化，即 $v_{\pi'} = v_\pi$，那么 $v_\pi$ 满足贝尔曼最优方程，$\pi$ 就是最优策略。

## 策略迭代（Policy Iteration）

交替进行“完整的策略评估”和“贪心策略改进”：

$$
\pi_0 \xrightarrow{\text{评估}} v_{\pi_0} \xrightarrow{\text{改进}} \pi_1 \xrightarrow{\text{评估}} v_{\pi_1} \xrightarrow{\text{改进}} \pi_2 \longrightarrow \cdots \longrightarrow \pi_*
$$

伪代码：

```text
初始化 π(s) 为任意动作，V(s) = 0
重复：
    # 1. 策略评估
    重复直到 Δ < θ：
        对每个 s：V(s) ← Σ_{s',r} p(s',r|s,π(s)) [r + γV(s')]
    # 2. 策略改进
    policy_stable ← True
    对每个 s：
        old ← π(s)
        π(s) ← argmax_a Σ_{s',r} p(s',r|s,a) [r + γV(s')]
        若 old ≠ π(s)：policy_stable ← False
直到 policy_stable
```

由于有限 MDP 的确定性策略数量有限（$|\mathcal{A}|^{|\mathcal{S}|}$ 个），且每次改进都严格变好（或不变即终止），策略迭代一定在有限步内收敛，实践中通常只需要很少几轮。

## 价值迭代（Value Iteration）

策略迭代每一轮都要把策略评估跑到收敛，代价较高。**价值迭代**把评估截断为只扫描一次，并把改进直接合并进更新式，相当于反复应用贝尔曼最优算子：

$$
v_{k+1}(s) \leftarrow \max_a \sum_{s', r} p(s', r \mid s, a)\left[r + \gamma v_k(s')\right]
$$

收敛后再一次性提取贪心策略：

$$
\pi_*(s) = \arg\max_a \sum_{s', r} p(s', r \mid s, a)\left[r + \gamma v_*(s')\right]
$$

## 广义策略迭代（GPI）

策略迭代和价值迭代都是**广义策略迭代**（Generalized Policy Iteration）的特例：价值函数不断向当前策略的真实价值靠拢（评估），策略不断相对当前价值函数变得贪心（改进）。两个过程既竞争又合作，最终同时收敛到最优。

```mermaid
flowchart LR
  P[策略 π] -- 评估：V → v_π --> V[价值 V]
  V -- 改进：π → greedy(V) --> P
```

后面要学的蒙特卡洛控制、SARSA、Q-learning、Actor-Critic，都遵循 GPI 的框架，只是评估和改进的方式不同。

## 代码：在 FrozenLake 上实现策略迭代与价值迭代

`FrozenLake-v1` 是一个 4×4 的冰面网格：从左上角 S 出发，到达右下角 G 得到奖励 1，掉进冰洞 H 则回合结束。地面打滑：执行某个方向后，只有 1/3 概率按预期移动，另外各有 1/3 概率滑向两侧的垂直方向。动作编号为 0 左、1 下、2 右、3 上。

```python
"""动态规划：在 FrozenLake-v1（4x4，打滑）上实现策略迭代与价值迭代。"""
import gymnasium as gym
import numpy as np

env = gym.make("FrozenLake-v1", is_slippery=True)
P = env.unwrapped.P
nS, nA = env.observation_space.n, env.action_space.n
gamma, theta = 0.99, 1e-8

def q_from_v(v, s):
    """一步前瞻：q(s,a) = Σ p(s',r|s,a)[r + γ v(s')]"""
    q = np.zeros(nA)
    for a in range(nA):
        for prob, s2, r, done in P[s][a]:
            q[a] += prob * (r + gamma * v[s2] * (not done))
    return q

def policy_evaluation(policy, v=None):
    v = np.zeros(nS) if v is None else v.copy()
    while True:
        delta = 0.0
        for s in range(nS):
            new = q_from_v(v, s)[policy[s]]       # 确定性策略
            delta = max(delta, abs(new - v[s]))
            v[s] = new                           # 原地更新（in-place）
        if delta < theta:
            return v

def policy_iteration():
    policy = np.zeros(nS, dtype=int)
    v = np.zeros(nS)
    for i in range(100):
        v = policy_evaluation(policy, v)
        new_policy = np.array([np.argmax(q_from_v(v, s)) for s in range(nS)])
        if np.array_equal(new_policy, policy):
            return policy, v, i + 1
        policy = new_policy

def value_iteration():
    v = np.zeros(nS)
    for i in range(10_000):
        delta = 0.0
        for s in range(nS):
            best = np.max(q_from_v(v, s))
            delta = max(delta, abs(best - v[s]))
            v[s] = best
        if delta < theta:
            break
    policy = np.array([np.argmax(q_from_v(v, s)) for s in range(nS)])
    return policy, v, i + 1

def evaluate(policy, episodes=10_000, seed=0):
    rng_env = gym.make("FrozenLake-v1", is_slippery=True)
    wins = 0
    for ep in range(episodes):
        s, _ = rng_env.reset(seed=seed + ep)
        done = False
        while not done:
            s, r, term, trunc, _ = rng_env.step(int(policy[s]))
            done = term or trunc
        wins += r
    return wins / episodes

pi_pi, v_pi, n_pi = policy_iteration()
pi_vi, v_vi, n_vi = value_iteration()
arrows = np.array(["←", "↓", "→", "↑"])
print(f"策略迭代：{n_pi} 轮收敛；价值迭代：{n_vi} 次扫描收敛")
print("两种方法得到的策略是否一致：", np.array_equal(pi_pi, pi_vi))
print("最优策略：\n", arrows[pi_vi].reshape(4, 4))
print("v*(起点) =", round(v_vi[0], 4))
print(f"实际成功率（10000 回合）：{evaluate(pi_vi):.3f}")
```
实际运行输出：

```text
策略迭代：7 轮收敛；价值迭代：324 次扫描收敛
两种方法得到的策略是否一致： True
最优策略：
 [['←' '↑' '↑' '↑']
 ['←' '←' '←' '←']
 ['↑' '↓' '←' '←']
 ['←' '→' '↓' '←']]
v*(起点) = 0.542
实际成功率（10000 回合）：0.737
```

几点观察：

- 策略迭代只需 7 轮就收敛（但每轮内部有完整的策略评估），价值迭代需要 324 次扫描（$\gamma = 0.99$ 时收敛较慢）。
- 最优策略看起来“很奇怪”：起点处选择向左。这是因为地面打滑，向左（撞墙）不会掉进洞里，同时有 1/3 的概率滑向下方——智能体利用了打滑机制来规避风险。
- 起点的最优价值 $v_*(s_0) = 0.542$ 是**折扣后**的期望回报；实际成功率约 73.7%（环境默认最多 100 步，DP 求解时忽略了这一时间限制）。

## DP 的局限

1. **需要完整模型**：现实中通常拿不到 $p(s', r \mid s, a)$。→ 蒙特卡洛与 TD 方法直接从经验中学习。
2. **维度灾难**：每次扫描都要遍历所有状态，复杂度随状态数线性增长，而状态数随状态变量个数指数增长。→ 函数近似（如 DQN）。
3. **全宽回溯代价高**：每次更新要对所有后继状态求期望。→ 采样回溯。

尽管如此，DP 在中小规模的规划问题（库存管理、路径规划等）中依然实用，**异步 DP**（按任意顺序、只更新部分状态）和**优先扫描**（prioritized sweeping）也能显著提升效率。

## 常见误区

- **忘记处理终止状态**：终止状态之后没有未来价值，计算时要把 $v(s')$ 乘以 $(1-\text{done})$。
- **以为策略迭代的评估必须精确收敛**：其实只做有限几次扫描（修改的策略迭代）也能收敛到最优，价值迭代就是只扫描一次的极端情况。
- **用价值迭代的中间 $v_k$ 当作某个策略的价值**：价值迭代过程中的 $v_k$ 一般不对应任何策略的真实价值。

## 小结

- 策略评估：反复应用贝尔曼期望算子，求 $v_\pi$。
- 策略改进：对 $v_\pi$ 贪心，得到不差于原策略的新策略。
- 策略迭代 = 完整评估 + 改进交替；价值迭代 = 反复应用贝尔曼最优算子。
- 广义策略迭代（GPI）是几乎所有强化学习控制算法的共同框架。

## 练习题

1. 把例题中的 `is_slippery` 改为 `False`，最优策略和成功率会如何变化？先预测再运行验证。
2. 把 $\gamma$ 从 0.99 改为 0.9，价值迭代需要的扫描次数和得到的策略有何变化？成功率呢？
3. 实现“修改的策略迭代”：每轮只做 $k$ 次评估扫描（$k = 1, 5, 20$），比较收敛所需的总扫描次数。
4. 证明：如果策略改进后 $\pi' = \pi$，则 $v_\pi = v_*$。
5. 用 `FrozenLake-v1` 的 `map_name="8x8"` 重新运行，记录两种方法的耗时。

**延伸阅读**

交互工具：[网格世界：价值迭代 / 策略迭代可视化](https://dqn.cn/tools/gridworld)——在浏览器中编辑地图、调节 $\gamma$，逐步观察两种算法的收敛过程

## 参考文献

- Bellman, R. (1957). *Dynamic Programming*. Princeton University Press.
- Howard, R. A. (1960). *Dynamic Programming and Markov Processes*. MIT Press.（策略迭代）
- Sutton, R. S., & Barto, A. G. (2018). *Reinforcement Learning: An Introduction* (2nd ed.), 第 4 章.

## 下一步

继续阅读：[蒙特卡洛方法](https://dqn.cn/basics/monte-carlo)——不需要环境模型，直接从完整回合的经验中估计价值。

## 常见问题速查（FAQ）

**问：策略迭代和价值迭代哪个更快？**

答：策略迭代需要的外层迭代次数通常很少，但每次策略评估要扫描很多遍；价值迭代每轮只扫描一遍，但需要更多轮。在本站 FrozenLake 实验中，策略迭代 7 轮收敛，价值迭代扫描了 324 遍。

**问：什么是广义策略迭代（GPI）？**

答：GPI 指策略评估和策略改进两个过程相互作用、交替推进的一般思想。几乎所有强化学习算法都可以看作 GPI 的某种形式。

**问：动态规划在实际中还有用吗？**

答：在模型已知且状态不多的问题（如库存管理、小规模规划）中仍然直接可用；更重要的是，它是理解所有强化学习算法的理论基础。

## 如何引用本文

DQN.CN 编辑部. 动态规划[EB/OL]. DQN.CN, 2026-10-29（更新于 2026-10-30）. https://dqn.cn/basics/dynamic-programming.