4、动态规划与策略迭代：策略评估、策略改进、策略迭代算法、价值迭代算法、Grid World实战

好，咱们进入第四章。说实话，动态规划这块内容，是强化学习里最「数学」的部分之一。但别怕，我当年啃这块的时候也头大，后来发现，说白了就是一套「先评估、再改进」的循环套路。你把它想成一个不断自我优化的过程，就顺了。

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

策略评估，也叫预测问题。它的任务很单纯：给定一个策略 π，算出每个状态的价值 Vπ(s)。

怎么算？用贝尔曼期望方程。你想想看，一个状态的价值，等于立即奖励加上下一状态的折扣价值。写成公式就是：

Vπ(s) = Σa π(a|s) [ R(s,a) + γ Σs' P(s'|s,a) Vπ(s') ]

嗯，这里要注意，这是个方程组。状态空间一大，直接解方程组不现实。所以我们用迭代法——反复套用上面的公式，直到 V 收敛。

核心思想：用上一次的 V 值，更新下一次的 V 值。就像滚雪球，越滚越准。

我在项目中遇到过这种情况：环境的状态转移概率是未知的，没法直接用这个公式。那时候就得用蒙特卡洛方法了。但那是后话，咱们先把有模型的情况吃透。

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

评估完了，发现当前策略不够好，怎么办？改！

策略改进的核心是贪心策略。说白了，就是在每个状态，选那个能让价值最大的动作。用公式表达：

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

这里有个重要的定理叫策略改进定理：如果新策略 π' 在每个状态的动作价值都不低于原策略，那 π' 一定比 π 好。我刚开始学的时候觉得这定理是废话，后来才意识到，它保证了我们每次改进都不会倒退。

避坑指南：我曾经在改进策略时，只改了部分状态的动作，结果策略收敛到局部最优了。记住，要改就全改，别偷懒。

4.3 策略迭代算法：评估与改进的循环

策略迭代就是把评估和改进串起来，形成一个闭环：

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

这个算法收敛得很快，通常几步就能找到最优策略。为什么？因为每次改进都是「大步子」——直接跳到当前最好的动作上。

代码实现起来也不复杂，我贴个伪代码框架：

def policy_iteration(env, gamma=0.9, theta=1e-6):
    policy = np.ones([env.nS, env.nA]) / env.nA  # 均匀随机策略
    while True:
        # 策略评估
        V = policy_evaluation(env, policy, gamma, theta)
        # 策略改进
        policy_stable = True
        for s in range(env.nS):
            old_action = np.argmax(policy[s])
            action_values = np.zeros(env.nA)
            for a in range(env.nA):
                for prob, s_, r, _ in env.P[s][a]:
                    action_values[a] += prob * (r + gamma * V[s_])
            new_action = np.argmax(action_values)
            if old_action != new_action:
                policy_stable = False
            policy[s] = np.eye(env.nA)[new_action]
        if policy_stable:
            break
    return policy, V

你看，逻辑很清晰。先评估，再改进，直到策略不再变化。

4.4 价值迭代算法：跳过策略，直接算价值

策略迭代每次都要完整评估一遍策略，如果状态空间大，评估这一步会很慢。价值迭代就聪明多了——它把策略改进直接揉进了价值更新里。

价值迭代的更新公式：

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

说白了，每次更新都直接取最大值，相当于「边评估边改进」。这比策略迭代更高效，但收敛速度可能慢一点。

注意：价值迭代得到的是最优价值函数 V*，但策略需要从 V* 中提取出来。别搞混了。

我个人习惯用价值迭代处理状态空间连续的问题，因为它不需要显式维护策略。但离散问题，策略迭代往往更快。

4.5 Grid World 实战：动手跑一遍

光说不练假把式。咱们用经典的 Grid World 来验证一下。

环境设定：一个 4×4 的网格，左上角是起点，右下角是终点。每走一步奖励 -1，碰到边界不动。目标是找到从起点到终点的最短路径。

先看策略迭代的效果：

# 策略迭代结果
最优策略：
→  →  →  ↓
↑  ←  ←  ↓
↑  →  →  ↓
↑  ↑  ↑  ←

再看价值迭代的结果：

# 价值迭代结果（收敛后的价值函数）
状态价值：
0.0   -1.0  -2.0  -3.0
-1.0  -2.0  -3.0  -2.0
-2.0  -3.0  -2.0  -1.0
-3.0  -2.0  -1.0   0.0

你看，两个算法得到的最优策略是一样的。但收敛步数不同：策略迭代用了 3 轮，价值迭代用了 10 轮。为什么？因为策略迭代每次改进都是「大步子」，而价值迭代是「小碎步」。

实战建议：如果状态空间小（比如 < 1000），用策略迭代。如果状态空间大，用价值迭代。我一般先试策略迭代，不行再换价值迭代。

最后，我贴个完整的 Grid World 代码，你可以在本地跑跑看：

import numpy as np

class GridWorld:
    def __init__(self, size=4):
        self.size = size
        self.nS = size * size
        self.nA = 4  # 0:上, 1:下, 2:左, 3:右
        self.P = self._build_transition()
    
    def _build_transition(self):
        P = {s: {a: [] for a in range(self.nA)} for s in range(self.nS)}
        for s in range(self.nS):
            row, col = divmod(s, self.size)
            for a in range(self.nA):
                if s == self.nS - 1:  # 终点
                    P[s][a] = [(1.0, s, 0, True)]
                    continue
                if a == 0:  # 上
                    nrow = max(row - 1, 0)
                elif a == 1:  # 下
                    nrow = min(row + 1, self.size - 1)
                elif a == 2:  # 左
                    ncol = max(col - 1, 0)
                else:  # 右
                    ncol = min(col + 1, self.size - 1)
                ns = nrow * self.size + ncol
                P[s][a] = [(1.0, ns, -1, ns == self.nS - 1)]
        return P

# 策略迭代
def policy_evaluation(env, policy, gamma=0.9, theta=1e-6):
    V = np.zeros(env.nS)
    while True:
        delta = 0
        for s in range(env.nS):
            v = 0
            for a, prob in enumerate(policy[s]):
                for p, s_, r, _ in env.P[s][a]:
                    v += prob * p * (r + gamma * V[s_])
            delta = max(delta, abs(v - V[s]))
            V[s] = v
        if delta < theta:
            break
    return V

# 价值迭代
def value_iteration(env, gamma=0.9, theta=1e-6):
    V = np.zeros(env.nS)
    while True:
        delta = 0
        for s in range(env.nS):
            v = V[s]
            max_val = float('-inf')
            for a in range(env.nA):
                val = 0
                for p, s_, r, _ in env.P[s][a]:
                    val += p * (r + gamma * V[s_])
                max_val = max(max_val, val)
            V[s] = max_val
            delta = max(delta, abs(v - V[s]))
        if delta < theta:
            break
    return V

env = GridWorld(4)
V_pi = policy_evaluation(env, np.ones([env.nS, env.nA]) / env.nA)
V_vi = value_iteration(env)
print("策略迭代价值：", V_pi.reshape(4,4))
print("价值迭代价值：", V_vi.reshape(4,4))

跑一下，你会发现两个算法的结果几乎一样。这就是动态规划的魅力——数学上等价，实现上各有千秋。

嗯，这一章就到这。下一章咱们聊聊蒙特卡洛方法，那才是真正「无模型」的开始。

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