3. 动态规划与策略迭代：从理论到网格世界

动态规划，说白了就是「拆解问题」的数学艺术。我刚开始接触时也觉得这名字挺唬人，但后来发现，它其实就是把一个大问题拆成小问题，然后逐个击破。在强化学习里，我们用它来求解最优策略——前提是你得有一个完整的模型。

嗯，这里要注意：动态规划要求环境模型完全已知。什么意思？就是你知道状态怎么转移，奖励怎么给。如果不知道，那动态规划就用不了。但在网格世界里，我们刚好有这个条件。

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

策略评估，就是给定一个策略 π，算出每个状态的价值 Vπ(s)。

公式其实不复杂：

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

说白了，就是不断迭代更新价值函数，直到收敛。我习惯把这个过程叫做「扫表」——就像扫地一样，一遍不行就两遍，直到干净为止。

核心要点：策略评估是一个迭代过程。每次迭代都用当前的价值估计去更新下一个价值估计。收敛条件通常是价值变化小于某个阈值 ε。

我在项目中遇到过一个问题：如果 γ 接近 1，收敛会非常慢。你想想看，未来的奖励几乎和现在一样重要，那价值传播就需要很多步。这时候我一般会把 ε 设大一点，或者直接用后面要讲的值迭代。

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

评估完了，下一步就是改进。策略改进的核心思想很简单：

对于每个状态 s，看看有没有比当前策略 π(s) 更好的动作 a'。

判断标准是什么？就是看 Q 值：

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

如果 Q_π(s,a') > V_π(s)，那就把策略改成 a'。这就是贪心策略改进。

我的经验：贪心改进不一定每次都选最优动作。有时候你选了一个看起来不错的动作，但后续状态的价值还没算准，结果反而变差了。所以策略评估一定要做充分，否则改进就是「盲人摸象」。

我曾经踩过一个坑：在某个网格世界里，我贪心地选了局部最优动作，结果策略直接卡死在一个角落里。后来我加了一个 ε-贪心的探索机制，才绕出来。

3.3 策略迭代算法：评估 + 改进，循环往复

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

  1. 初始化一个随机策略 π
  2. 策略评估：计算 Vπ
  3. 策略改进：基于 Vπ 生成新策略 π'
  4. 如果 π' ≠ π，回到第 2 步；否则结束

这个算法保证收敛到最优策略。为什么？因为每次改进都让策略变好，而策略空间是有限的，所以最终会停在最优解上。

注意：策略评估如果做太多轮，会浪费计算资源。我建议每轮评估只做有限次迭代（比如 10 次），然后直接改进。这叫「截断策略迭代」，效果往往更好。

下面是我画的一张流程图，帮你理清策略迭代的脉络：

初始化策略 π 策略评估 策略改进 π' = π? 否 输出 π* 是

3.4 值迭代算法：一步到位

策略迭代需要反复评估和改进，有点啰嗦。值迭代则更直接：它把评估和改进合并成一步。

值迭代的更新公式：

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

看到了吗？这里直接取 max，不再依赖当前策略。每次更新都在做「隐式的策略改进」。

对比：策略迭代是「评估→改进→评估→改进...」，值迭代是「评估+改进→评估+改进...」。值迭代收敛更快，但每次迭代的计算量稍大（因为要算 max）。

我个人习惯：如果状态空间小（比如几百个），用策略迭代；如果状态空间大（几千上万个），用值迭代。为什么？因为策略迭代的评估阶段需要多次扫表，而值迭代一次扫表就完成了评估和改进。

3.5 网格世界中的实现

来，我们看一个具体的例子。假设有一个 4×4 的网格世界：

S
G

S 是起点，G 是终点（奖励 +1）。其他格子奖励为 0。动作有上下左右，碰到边界就留在原地。折扣因子 γ = 0.9。

下面是用值迭代求解的代码：

import numpy as np

# 网格参数
n_rows, n_cols = 4, 4
gamma = 0.9
theta = 1e-4  # 收敛阈值

# 动作定义：上、下、左、右
actions = [(-1,0), (1,0), (0,-1), (0,1)]

# 初始化价值函数
V = np.zeros((n_rows, n_cols))

# 值迭代
while True:
    delta = 0
    for i in range(n_rows):
        for j in range(n_cols):
            # 终点价值为0
            if (i == n_rows-1 and j == n_cols-1):
                continue
            
            v = V[i, j]
            max_q = -np.inf
            
            for a in actions:
                # 计算下一个状态
                ni = max(0, min(n_rows-1, i + a[0]))
                nj = max(0, min(n_cols-1, j + a[1]))
                
                # 奖励：到达终点为1，否则为0
                reward = 1.0 if (ni == n_rows-1 and nj == n_cols-1) else 0.0
                
                # Q值
                q = reward + gamma * V[ni, nj]
                max_q = max(max_q, q)
            
            V[i, j] = max_q
            delta = max(delta, abs(v - V[i, j]))
    
    if delta < theta:
        break

print("最优价值函数：")
print(np.round(V, 2))

运行结果：终点附近的状态价值最高，远离终点的状态价值逐渐降低。这就是「距离越远，未来奖励折扣越大」的直观体现。

我曾经用这个网格世界给团队做培训。有个同事问：「为什么左上角的价值不是 0？」我说：「因为虽然它离终点远，但通过一系列动作还是能到达终点，所以价值是正的。只不过折扣因子让它的价值变小了。」

嗯，这里要注意：如果 γ = 0，那所有非终点状态的价值都是 0。因为未来奖励完全被忽略，只有即时奖励算数。所以 γ 的选择很关键，它决定了你的智能体是「短视」还是「远视」。

避坑指南：我曾经在实现策略迭代时，忘了给终点状态设价值为 0。结果策略评估时，终点的价值被不断更新，导致整个价值函数发散。记住：终点的价值是固定的，不需要更新。

最后总结一下：动态规划是强化学习的基石。策略迭代和值迭代是两种经典解法。策略迭代适合小规模问题，值迭代适合大规模问题。网格世界是一个绝佳的测试平台，因为它直观、可控，而且能让你亲眼看到算法是如何一步步收敛的。

可可精品资料库

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