3. 动态规划与策略迭代：从理论到代码

动态规划（Dynamic Programming，DP）在强化学习里是个什么角色？说白了，它是解决「已知环境模型」问题的黄金标准。我刚开始学RL时，总觉得DP太数学、太理想化——谁会给你完美的状态转移概率啊？但后来我发现，不理解DP，后面那些更高级的算法（比如Q-learning、Actor-Critic）你根本吃不透。它就像练武的马步，枯燥但必须扎实。

这一章，我们聚焦四个核心概念：策略评估、策略改进、策略迭代和值迭代。我会结合代码和流程图，把每一步掰开揉碎了讲。

3.1 策略评估（Policy Evaluation）

策略评估要解决什么问题？给定一个策略π，我们想知道它到底好不好。好坏的衡量标准就是状态值函数Vπ(s)。

回忆一下贝尔曼期望方程：

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

这个方程是自洽的——左边的V依赖于右边的V。怎么解？迭代！

核心思想：从一个初始值函数开始（比如全0），反复应用贝尔曼算子，直到收敛。

具体步骤：

  1. 初始化V(s)=0，对所有状态s
  2. 对每个状态s，计算：Vk+1(s) = Σa π(a|s) Σs',r p(s',r|s,a) [r + γ Vk(s')]
  3. 如果maxs |Vk+1(s) - Vk(s)| < θ，停止；否则回到第2步

这里θ是一个很小的阈值，比如1e-6。我习惯用θ=1e-4做快速原型，等调通了再收紧。

我的经验：在实际项目中，策略评估的收敛速度取决于γ。γ越接近1，收敛越慢。我曾经在一个机器人导航任务里，γ=0.99，跑了200轮才稳定。后来我把γ降到0.9，20轮就差不多了——当然，代价是策略变得短视。这是个trade-off，你得自己权衡。

来看一段Python伪代码：

def policy_evaluation(policy, env, gamma=0.9, theta=1e-4):
    V = {s: 0.0 for s in env.states}
    while True:
        delta = 0.0
        for s in env.states:
            v = V[s]
            new_v = 0.0
            for a in env.actions:
                action_prob = policy[s][a]
                for s_next, reward, prob in env.transitions(s, a):
                    new_v += action_prob * prob * (reward + gamma * V[s_next])
            V[s] = new_v
            delta = max(delta, abs(v - new_v))
        if delta < theta:
            break
    return V

这段代码里，env.transitions(s, a)返回的是(s', r, p(s',r|s,a))的列表。注意，这里假设环境模型已知——这正是DP的前提。

3.2 策略改进（Policy Improvement）

评估完策略，下一步就是改进它。怎么改？贪心！

对于每个状态s，我们看看在当前值函数V下，哪个动作能带来最大的期望回报：

π'(s) = argmaxa Σs',r p(s',r|s,a) [r + γ V(s')]

这个新策略π'一定比π好吗？是的，策略改进定理保证了这一点。只要新策略在至少一个状态上严格更好，它就是严格改进的。

注意：策略改进依赖的是当前的值函数V。如果V评估得不准，改进方向可能偏掉。我曾经犯过一个错误：在策略评估还没收敛时就做改进，结果策略来回震荡，就是不收敛。后来我老老实实等评估收敛再做改进，问题就解决了。

代码实现很简单：

def policy_improvement(V, env, gamma=0.9):
    policy = {s: {} for s in env.states}
    for s in env.states:
        action_values = {}
        for a in env.actions:
            q_value = 0.0
            for s_next, reward, prob in env.transitions(s, a):
                q_value += prob * (reward + gamma * V[s_next])
            action_values[a] = q_value
        best_action = max(action_values, key=action_values.get)
        policy[s] = {a: 1.0 if a == best_action else 0.0 for a in env.actions}
    return policy

3.3 策略迭代算法（Policy Iteration）

把评估和改进串起来，就是策略迭代。流程如下：

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

这个算法保证在有限MDP中收敛到最优策略。为什么？因为每次迭代策略都严格改进，而策略数量是有限的（|A||S|），所以最多迭代|A||S|次就停了。

收敛性证明（直觉版）：策略改进定理保证Vπ'(s) ≥ Vπ(s)对所有s成立，且至少一个s严格大于。值函数有上界（因为回报有界），所以序列{Vπ}单调递增且有上界，必然收敛。收敛时，策略不再改变，此时满足贝尔曼最优方程。

下面这张图展示了策略迭代的完整流程：

策略迭代流程图 策略迭代流程图 初始化随机策略 π 策略评估：计算 Vπ 策略改进：得到 π' π' == π ? 是 输出最优策略 π* 否 令 π = π' 策略迭代保证在有限MDP中收敛到最优策略，每次迭代策略严格改进

3.4 值迭代算法（Value Iteration）

策略迭代有个缺点：每次策略评估都要内嵌一个迭代循环，计算量大。值迭代把评估和改进合并成一个步骤，效率更高。

值迭代的核心公式：

Vk+1(s) = maxa Σs',r p(s',r|s,a) [r + γ Vk(s')]

你看，这里直接取max，不再依赖当前策略。每次迭代都在做「一步策略改进+一步策略评估」的融合操作。

我的习惯：值迭代的收敛速度通常比策略迭代快，尤其是在状态空间大的时候。但要注意，值迭代收敛的是值函数，策略可能提前稳定。我一般会同时监控值函数变化和策略变化，哪个先稳定就用哪个。

代码实现：

def value_iteration(env, gamma=0.9, theta=1e-4):
    V = {s: 0.0 for s in env.states}
    while True:
        delta = 0.0
        for s in env.states:
            v = V[s]
            action_values = []
            for a in env.actions:
                q_value = 0.0
                for s_next, reward, prob in env.transitions(s, a):
                    q_value += prob * (reward + gamma * V[s_next])
                action_values.append(q_value)
            V[s] = max(action_values)
            delta = max(delta, abs(v - V[s]))
        if delta < theta:
            break
    # 从收敛的值函数中提取最优策略
    policy = {}
    for s in env.states:
        action_values = {}
        for a in env.actions:
            q_value = 0.0
            for s_next, reward, prob in env.transitions(s, a):
                q_value += prob * (reward + gamma * V[s_next])
            action_values[a] = q_value
        best_action = max(action_values, key=action_values.get)
        policy[s] = best_action
    return policy, V

3.5 策略迭代 vs 值迭代：对比

这两个算法到底选哪个？我整理了一张对比表：

维度 策略迭代 值迭代
核心操作 评估→改进→评估→改进... 直接更新值函数（取max）
收敛速度 迭代次数少（策略快速改进） 迭代次数多（但每次迭代快）
每次迭代计算量 大（内嵌评估循环） 小（一步到位）
适用场景 状态空间小，或需要精确策略 状态空间大，或需要快速原型
收敛保证 有限步内收敛到最优 渐近收敛到最优

避坑指南：我曾经在一个网格世界任务里用策略迭代，状态数只有100，但动作空间是4，策略迭代跑了15轮就收敛了。后来换到连续状态空间（离散化后10000个状态），策略迭代每轮评估都要跑50次内循环，总共花了半小时。换成值迭代后，虽然迭代了200轮，但每轮只要一次扫描，5分钟就出结果了。所以，选哪个取决于你的问题规模。

3.6 收敛性证明（简要）

这两个算法为什么能收敛？我简单说下思路。

策略迭代：

  • 策略改进定理保证Vπ' ≥ Vπ（逐点）
  • 值函数有上界（回报有界，γ<1）
  • 单调递增有上界序列必收敛
  • 收敛时满足贝尔曼最优方程

值迭代：

  • 贝尔曼最优算子T*是压缩映射（压缩因子γ）
  • 根据巴拿赫不动点定理，反复应用T*会收敛到唯一不动点
  • 这个不动点就是最优值函数V*

一句话总结：策略迭代靠「单调改进」收敛，值迭代靠「压缩映射」收敛。两种思路都漂亮，但值迭代的数学更优雅——你想想看，一个算子反复作用就能收敛到最优，多简洁。

嗯，到这里，动态规划的核心内容就讲完了。策略评估、策略改进、策略迭代、值迭代，这四个概念是强化学习的基石。后面的章节我们会看到，很多高级算法（比如DQN、A3C）都能追溯到这些基本思想。代码我已经给了，建议你找个简单环境（比如4x4网格世界）跑一跑，亲手感受一下收敛过程。

← 上一章 📖 返回目录 下一章 →