3. 动态规划与策略迭代：策略评估、策略改进、策略迭代算法、值迭代算法、Gymnasium环境下的DP实现

各位好，欢迎来到第三章。这一章我们聊聊动态规划（DP）在强化学习里的应用。说实话，DP 是 RL 理论的基石，虽然现在大家一上来就搞深度网络，但 DP 的思想——利用环境模型来迭代优化策略——是理解后续所有算法的关键。

我个人习惯把 DP 看作「有模型」的 RL 核心。什么意思？就是你知道环境的状态转移概率和奖励函数。有了这个模型，你就能像下棋一样，提前推演每一步的后果。嗯，咱们先看最基础的两个操作：策略评估和策略改进。

3.1 策略评估：算清楚当前策略到底有多好

策略评估，说白了就是给定一个策略 π，算出每个状态的价值 V^π(s)。怎么算？用贝尔曼期望方程迭代。

公式很简单：

V_{k+1}(s) = Σ_a π(a|s) Σ_{s',r} p(s',r|s,a) [r + γ V_k(s')]

你可能会问：这不就是反复套公式吗？对，就是反复套。直到 V 的变化小于某个阈值 ε。我在项目中遇到过这种情况：一开始迭代 100 轮还不收敛，后来发现是 γ 设得太接近 1，导致收敛速度极慢。所以，γ 越大，需要的迭代次数越多。

3.2 策略改进：让策略变得更好

评估完策略，下一步就是改进。怎么改进？贪心！对每个状态 s，我们选择能最大化 Q 值的动作：

π'(s) = argmax_a Σ_{s',r} p(s',r|s,a) [r + γ V(s')]

这里有个关键点：策略改进定理保证新策略 π' 一定不比 π 差。为什么？因为贪心选择至少不会让 Q 值下降。你想想看，如果所有状态都选最优动作，整体价值怎么可能变差？

我在实际调参时发现，有时候策略改进一步就收敛了，有时候需要好几轮。这取决于初始策略有多差。比如随机策略，通常 2-3 轮改进就能达到最优。

3.3 策略迭代算法：评估 + 改进，循环直到收敛

策略迭代就是把评估和改进串起来：

1. 初始化策略 π（比如随机）
2. 策略评估：计算 V^π
3. 策略改进：基于 V^π 得到 π'
4. 如果 π' == π，停止；否则回到步骤 2

这个算法在有限 MDP 下保证收敛到最优策略。我记得第一次实现时，评估阶段我迭代了 1000 轮，结果发现其实 50 轮就够了。后来我加了个动态停止条件：当 V 的变化小于 1e-6 就提前退出。效率提升很明显。

3.4 值迭代算法：把评估和改进合并成一步

值迭代是策略迭代的变种。它不显式维护策略，而是直接更新价值函数：

V_{k+1}(s) = max_a Σ_{s',r} p(s',r|s,a) [r + γ V_k(s')]

你看，这里直接用了 max，而不是先算期望再改进。说白了，值迭代把策略改进融进了每一次价值更新中。这样做的好处是：不需要等到评估完全收敛再改进，而是边评估边改进。

我个人习惯在状态空间连续或离散但很大的场景下用值迭代。因为它每次迭代只做一次 max 操作，比策略迭代的「评估+改进」两阶段要轻量。但要注意：值迭代的收敛条件不是策略不变，而是价值函数变化小于 ε。

算法	每次迭代复杂度	收敛轮数	适用场景
策略迭代	O(|S|²|A|) 评估 + O(|S||A|) 改进	少（通常 < 20）	状态空间中等，需要精确策略
值迭代	O(|S|²|A|)	多（通常 50-200）	状态空间大，快速原型

3.5 Gymnasium 环境下的 DP 实现

理论说完了，咱们动手。Gymnasium 里有个经典环境叫 FrozenLake-v1，4x4 网格，有冰面（安全）和洞（掉下去就结束）。状态转移是确定的？不，其实是随机的——你朝前走，有 1/3 概率滑到左边或右边。这正好适合 DP。

下面是我写的一个策略迭代实现片段：

import gymnasium as gym
import numpy as np

env = gym.make('FrozenLake-v1', is_slippery=True)
nS = env.observation_space.n  # 16
nA = env.action_space.n       # 4
gamma = 0.99
theta = 1e-6

# 初始化随机策略
policy = np.ones([nS, nA]) / nA

def policy_evaluation(policy, V):
    while True:
        delta = 0
        for s in range(nS):
            v = 0
            for a, prob in enumerate(policy[s]):
                for prob_next, next_s, reward, done in env.P[s][a]:
                    v += prob * prob_next * (reward + gamma * V[next_s] * (not done))
            delta = max(delta, abs(v - V[s]))
            V[s] = v
        if delta < theta:
            break
    return V

def policy_improvement(policy, V):
    policy_stable = True
    for s in range(nS):
        old_action = np.argmax(policy[s])
        action_values = np.zeros(nA)
        for a in range(nA):
            for prob_next, next_s, reward, done in env.P[s][a]:
                action_values[a] += prob_next * (reward + gamma * V[next_s] * (not done))
        best_action = np.argmax(action_values)
        if old_action != best_action:
            policy_stable = False
        policy[s] = np.eye(nA)[best_action]
    return policy, policy_stable

V = np.zeros(nS)
while True:
    V = policy_evaluation(policy, V)
    policy, stable = policy_improvement(policy, V)
    if stable:
        break

print("最优策略:", np.argmax(policy, axis=1).reshape(4,4))

值迭代的实现更简洁：

V = np.zeros(nS)
while True:
    delta = 0
    for s in range(nS):
        v = V[s]
        action_values = np.zeros(nA)
        for a in range(nA):
            for prob_next, next_s, reward, done in env.P[s][a]:
                action_values[a] += prob_next * (reward + gamma * V[next_s] * (not done))
        V[s] = np.max(action_values)
        delta = max(delta, abs(v - V[s]))
    if delta < theta:
        break

# 从 V 提取策略
policy = np.zeros([nS, nA])
for s in range(nS):
    action_values = np.zeros(nA)
    for a in range(nA):
        for prob_next, next_s, reward, done in env.P[s][a]:
            action_values[a] += prob_next * (reward + gamma * V[next_s] * (not done))
    policy[s, np.argmax(action_values)] = 1

你运行一下会发现，两种算法得到的最优策略基本一致。但值迭代收敛需要的轮数更多（比如 100 轮 vs 策略迭代的 5 轮）。不过值迭代每轮的计算量小，所以总时间可能差不多。

3.6 本章知识体系图

下面这张 SVG 图总结了 DP 在 RL 中的核心逻辑：

从图中你能看到：策略迭代是「评估→改进→再评估→再改进」的循环，而值迭代直接一步到位更新 V。两者最终都输出最优策略和最优价值函数。

好了，这一章的内容就到这里。DP 虽然古老，但它的思想贯穿整个 RL。后面讲到无模型方法时，你会发现很多算法都是在 DP 的基础上，用采样代替了环境模型。嗯，先消化一下，动手跑跑代码，有问题随时翻回来看看。

---