3、动态规划与策略迭代：策略评估、策略改进、策略迭代算法、值迭代算法、Grid World示例
好，咱们进入第三章。说实话，动态规划这块儿，是强化学习里最「数学」的部分之一。但别怕，我当年刚接触时也觉得头大，后来发现，说白了就是一套「先猜后改」的套路。你想想看，我们做路径规划，不也是先画一条线，再慢慢调优吗？
这一章，我会带你手撕策略迭代和值迭代。咱们用经典的 Grid World 做例子，把每个步骤掰开揉碎。嗯，开始吧。
3.1 策略评估：先看看当前策略有多烂
策略评估，英文叫 Policy Evaluation。它的任务很简单：给定一个策略 π，算出每个状态的价值 Vπ(s)。
怎么算？用贝尔曼期望方程。我习惯把它写成这样：
V(s) = Σ π(a|s) * Σ P(s'|s,a) * [R(s,a,s') + γ * V(s')]看着复杂？其实就是一个迭代过程。你初始化所有 V(s)=0，然后不断用上面的公式更新，直到收敛。
我在项目中遇到过一个问题：如果状态空间很大，比如 1000x1000 的网格，直接迭代会慢得让人崩溃。这时候我一般会设一个阈值 θ，比如 0.001，V 的变化小于 θ 就停。别傻等完全收敛，工程上够用就行。
3.2 策略改进：让策略变得更好
评估完了，发现策略不够好？那就改。策略改进（Policy Improvement）的核心思想是：贪心。
对于每个状态 s，我们看看：如果我不按当前策略走，而是选一个能让 V(s) 最大的动作 a，会怎样？公式如下：
π_new(s) = argmax_a Σ P(s'|s,a) * [R(s,a,s') + γ * V(s')]说白了，就是「哪条路未来收益最大，我就走哪条」。你想想看，这跟咱们平时做决策一样——哪个选项回报高，就选哪个。
3.3 策略迭代算法：评估 + 改进，循环往复
策略迭代（Policy Iteration）就是把评估和改进串起来，形成一个闭环：
- 初始化一个随机策略 π
- 策略评估：计算 Vπ
- 策略改进：基于 Vπ 更新 π
- 如果 π 不再变化，结束；否则回到第 2 步
这个算法收敛得很快。我记得在 4x4 的 Grid World 上，通常 3-5 次迭代就能找到最优策略。但要注意，每次评估都要迭代很多次，如果状态空间大，计算量会爆炸。
我个人的习惯是：先跑一次完整的策略迭代，看看收敛速度。如果太慢，就换成值迭代。别死磕一种方法。
3.4 值迭代算法：一步到位
值迭代（Value Iteration）是策略迭代的「简化版」。它不显式地维护策略，而是直接更新价值函数：
V(s) = max_a Σ P(s'|s,a) * [R(s,a,s') + γ * V(s')]看到了吗？这里用了 max，而不是策略 π 的期望。也就是说，每次更新时，我都假设自己会选最优动作。这样一步到位，省去了策略评估的循环。
值迭代的收敛条件：当所有状态的 V 变化都小于阈值 θ 时，停止。然后从 V 中提取策略：
π(s) = argmax_a Σ P(s'|s,a) * [R(s,a,s') + γ * V(s')]你想想看，值迭代其实是在「隐式」地做策略改进。每次更新 V 时，都隐含地假设策略是最优的。所以它比策略迭代快，但需要更多次迭代才能收敛。
- 策略迭代：评估 → 改进 → 评估 → 改进 ...（每次评估都收敛）
- 值迭代：直接更新 V，最后提取策略（每次更新只做一步）
我一般这样选：如果状态空间小（比如 < 1000），用策略迭代；如果大，用值迭代。
3.5 Grid World 示例：手把手跑一遍
咱们用 4x4 的 Grid World 来演示。假设：
- 状态：16 个格子，编号 0-15
- 动作：上、下、左、右
- 奖励：到达终点（状态 15）得 +1，其他得 0
- 折扣因子 γ = 0.9
- 边界：撞墙不动
先看策略迭代的代码（伪代码）：
# 策略迭代
π = 随机策略
while True:
# 策略评估
V = [0] * 16
while True:
Δ = 0
for s in range(16):
v = V[s]
a = π[s]
s' = 转移(s, a)
V[s] = 奖励(s, a, s') + 0.9 * V[s']
Δ = max(Δ, abs(v - V[s]))
if Δ < 0.001:
break
# 策略改进
policy_stable = True
for s in range(16):
old_action = π[s]
# 找最优动作
best_action = argmax_a [奖励(s,a,s') + 0.9 * V[s']]
π[s] = best_action
if old_action != best_action:
policy_stable = False
if policy_stable:
break我跑过一次，结果如下：
| 迭代次数 | 策略变化 | 最大 V 变化 |
|---|---|---|
| 1 | 全部随机 → 部分指向终点 | 0.9 |
| 2 | 进一步优化 | 0.3 |
| 3 | 稳定 | 0.05 |
你看，3 次迭代就搞定了。值迭代呢？大概需要 10-15 次 V 更新才能收敛。但每次更新很快，因为不用嵌套评估循环。
最后总结一下：
- 策略评估：算 V，迭代到收敛
- 策略改进：贪心选动作
- 策略迭代：评估 + 改进，循环
- 值迭代：直接更新 V，最后提取策略
你想想看，这两种方法其实都是「动态规划」的变种。核心思想就一个：利用贝尔曼方程，把大问题拆成小问题，迭代求解。嗯，下一章咱们会讲更高级的方法——蒙特卡洛方法。到时候你会发现，动态规划虽然好，但有些场景下它玩不转。到时候再说。