动态规划

一句话总结 · 要点速览

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

术语不熟悉？查看 强化学习术语表。

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

前提与思路

DP 需要两个条件：

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

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

策略评估（Policy Evaluation）

迭代策略评估

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

$$v_{k+1}(s)\leftarrow \sum _a\pi (a\mid s)\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)[r+\gamma v_k(s^{\prime })],\mathrm{\forall }s\in \mathcal{S}$$

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

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

收敛性

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

$$\parallel v_k-v_{\pi }{\parallel }_{\mathrm{\infty }}\le {\gamma }^k\parallel v_0-v_{\pi }{\parallel }_{\mathrm{\infty }}$$

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

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

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

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

$$|({\mathcal{T}}^{\pi }u)(s)-({\mathcal{T}}^{\pi }v)(s)|=\gamma |\sum _{s^{\prime }}{P}_{\pi }(s^{\prime }\mid s)[u(s^{\prime })-v(s^{\prime })]|\le \gamma \sum _{s^{\prime }}{P}_{\pi }(s^{\prime }\mid s)\parallel u-v{\parallel }_{\mathrm{\infty }}=\gamma \parallel u-v{\parallel }_{\mathrm{\infty }}$$

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

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

$$|({\mathcal{T}}^{\ast }u)(s)-({\mathcal{T}}^{\ast }v)(s)|\le \underset{a}{max}\gamma \sum _{s^{\prime }}p(s^{\prime }\mid s,a)|u(s^{\prime })-v(s^{\prime })|\le \gamma \parallel u-v{\parallel }_{\mathrm{\infty }}$$

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

由此得到的实用结论。

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

策略改进定理

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

$${\pi }^{\prime }(s)=\arg \underset{a}{max}{q}_{\pi }(s,a)=\arg \underset{a}{max}\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)[r+\gamma v_{\pi }(s^{\prime })]$$

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

证明思路是反复展开：

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

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

策略迭代（Policy Iteration）

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

$${\pi }_0\stackrel{\text{评估}}{\to }{v}_{{\pi }_0}\stackrel{\text{改进}}{\to }{\pi }_1\stackrel{\text{评估}}{\to }{v}_{{\pi }_1}\stackrel{\text{改进}}{\to }{\pi }_2⟶\cdots ⟶{\pi }_{\ast }$$

伪代码：

初始化 π(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 \underset{a}{max}\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)[r+\gamma v_k(s^{\prime })]$$

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

$${\pi }_{\ast }(s)=\arg \underset{a}{max}\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)[r+\gamma v_{\ast }(s^{\prime })]$$

广义策略迭代（GPI）

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

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 上。

"""动态规划：在 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}")

实际运行输出：

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

几点观察：

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

DP 的局限

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

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

常见误区

• 忘记处理终止状态：终止状态之后没有未来价值，计算时要把 $v(s^{\prime })$ 乘以 $(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 }^{\prime }=\pi$，则 $v_{\pi }=v_{\ast }$。
5. 用 FrozenLake-v1 的 map_name="8x8" 重新运行，记录两种方法的耗时。

延伸阅读

交互工具：网格世界：价值迭代 / 策略迭代可视化——在浏览器中编辑地图、调节 $\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 章.

下一步

继续阅读：蒙特卡洛方法——不需要环境模型，直接从完整回合的经验中估计价值。