3. 动态规划

动态规划，说白了就是解决「多阶段决策」问题的利器。我刚开始接触强化学习时，觉得这玩意儿特别绕——明明叫「动态」，怎么算来算去都是静态的表格？后来在项目中做机器人路径规划，才真正体会到它的威力。

今天咱们就聊聊动态规划里最核心的两个算法：策略迭代和值迭代。它们就像一对双胞胎，长得像，但脾气秉性完全不同。

3.1 从贝尔曼方程说起

要理解策略迭代和值迭代，得先搞明白贝尔曼方程。你想想看，一个状态的价值，其实由两部分组成：当前能拿到的即时奖励，加上未来所有可能状态的折扣价值。

数学上写出来就是：

V(s) = R(s) + γ * Σ P(s'|s,a) * V(s')

嗯，这里要注意，这个方程是「自洽」的——V(s) 的定义里又用到了 V(s')。这就是动态规划能迭代求解的根本原因。

3.2 策略迭代：先评估，再改进

策略迭代的思路很直观：先固定一个策略，算出它的价值函数；然后根据这个价值函数，改进策略；再评估新策略的价值……如此循环，直到策略不再变化。

我在项目中遇到过一个问题：如果策略评估做得太精确，收敛会非常慢。后来我学乖了——评估到一定程度就停，反正策略改进只需要相对正确的价值排序。

3.2.1 策略评估

给定一个策略 π，我们要解出它的状态价值函数 V^π。怎么做？用贝尔曼方程反复迭代：

V_{k+1}(s) = Σ π(a|s) * [R(s,a) + γ * Σ P(s'|s,a) * V_k(s')]

说白了，就是拿旧的价值去算新的价值。迭代到 V_k 和 V_{k+1} 的差距足够小，我们就说评估完成了。

3.2.2 策略改进

有了价值函数，改进策略就简单了——在每个状态，选能让价值最大的动作：

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

我曾经犯过一个错：改进策略时只看了当前状态的价值，忽略了动作对后续状态的影响。结果策略越改越差。后来才意识到，策略改进必须基于完整的 Q 值，而不是 V 值。

3.2.3 完整流程

策略迭代的伪代码长这样：

1. 初始化策略 π（比如随机策略）
2. 重复直到收敛：
   a. 策略评估：用迭代法计算 V^π
   b. 策略改进：根据 V^π 更新 π
   c. 如果 π 不再变化，停止

3.3 值迭代：一步到位

值迭代的思路更直接：不显式维护策略，直接更新价值函数。每次迭代时，我们取所有动作中能带来最大价值的那个：

V_{k+1}(s) = max_a [R(s,a) + γ * Σ P(s'|s,a) * V_k(s')]

你想想看，这其实就是在做「一步策略改进 + 一步策略评估」的合并。值迭代收敛后，最优策略可以直接从最终的价值函数中提取出来。

3.3.1 为什么值迭代更快？

因为值迭代不需要在每次改进前都做完整的评估。它每步都在改进，每步都在评估，两条腿一起走。我个人的经验是：如果状态空间大，值迭代通常比策略迭代快 2-5 倍。

但要注意，值迭代的收敛速度取决于折扣因子 γ。γ 越接近 1，收敛越慢。我记得有一次做金融决策模型，γ 设成了 0.99，结果跑了 2000 轮还没稳定……后来改成 0.9，100 轮就搞定了。

3.4 策略迭代 vs 值迭代：一张表说清楚

对比维度	策略迭代	值迭代
核心操作	评估 → 改进 → 评估 → 改进	直接更新价值
收敛速度	迭代次数少，但每次迭代慢	迭代次数多，但每次迭代快
适用场景	状态空间小，或需要精确策略	状态空间大，或对时间敏感
数学保证	有限步内收敛到最优	渐近收敛到最优
实现难度	稍复杂，需要维护策略	简单，一行公式搞定

3.5 核心逻辑流程图

下面这张图展示了策略迭代和值迭代的核心差异。我特意用 SVG 手绘了，你一看就明白：

3.6 代码实现：用格子世界说话

理论说完了，咱们上代码。我用一个 4×4 的格子世界来演示。智能体从左上角出发，目标是右下角，每走一步得 -1 分，碰到边界就原地不动。

import numpy as np

# 环境参数
n_states = 16
actions = [0, 1, 2, 3]  # 上、下、左、右
gamma = 0.9
theta = 1e-4

# 构建转移矩阵和奖励
def build_env():
    P = np.zeros((n_states, len(actions), n_states))
    R = np.full((n_states, len(actions)), -1.0)
    
    for s in range(n_states):
        row, col = divmod(s, 4)
        for a, (dr, dc) in enumerate([(-1,0), (1,0), (0,-1), (0,1)]):
            nr, nc = row + dr, col + dc
            if 0 <= nr < 4 and 0 <= nc < 4:
                ns = nr * 4 + nc
            else:
                ns = s  # 撞墙不动
            P[s, a, ns] = 1.0
    
    # 终点状态（右下角）奖励为0，且不再转移
    P[15, :, :] = 0
    P[15, :, 15] = 1
    R[15, :] = 0
    return P, R

P, R = build_env()

# 策略迭代
def policy_iteration():
    policy = np.zeros(n_states, dtype=int)
    V = np.zeros(n_states)
    
    while True:
        # 策略评估
        while True:
            delta = 0
            for s in range(n_states):
                a = policy[s]
                v = V[s]
                V[s] = R[s, a] + gamma * np.dot(P[s, a], V)
                delta = max(delta, abs(v - V[s]))
            if delta < theta:
                break
        
        # 策略改进
        policy_stable = True
        for s in range(n_states):
            old_action = policy[s]
            q_values = [R[s, a] + gamma * np.dot(P[s, a], V) for a in actions]
            policy[s] = np.argmax(q_values)
            if old_action != policy[s]:
                policy_stable = False
        
        if policy_stable:
            break
    
    return policy, V

# 值迭代
def value_iteration():
    V = np.zeros(n_states)
    
    while True:
        delta = 0
        for s in range(n_states):
            v = V[s]
            q_values = [R[s, a] + gamma * np.dot(P[s, a], V) for a in actions]
            V[s] = max(q_values)
            delta = max(delta, abs(v - V[s]))
        if delta < theta:
            break
    
    # 提取最优策略
    policy = np.zeros(n_states, dtype=int)
    for s in range(n_states):
        q_values = [R[s, a] + gamma * np.dot(P[s, a], V) for a in actions]
        policy[s] = np.argmax(q_values)
    
    return policy, V

# 运行
pi_pi, V_pi = policy_iteration()
pi_vi, V_vi = value_iteration()

print("策略迭代结果：", pi_pi.reshape(4,4))
print("值迭代结果：", pi_vi.reshape(4,4))

3.7 避坑指南

做动态规划项目时，我踩过不少坑。分享几个典型的：

• 我曾经在策略评估时忘了处理终止状态，结果价值函数一直不收敛。记住：终止状态的 V 值固定为 0，不参与迭代。
• 我曾经在值迭代中直接用 V 值去更新 V 值，忘了用旧值做备份。结果价值函数震荡得像过山车。正确做法是：用 V_old 计算，更新 V_new，一轮结束后再替换。
• 我建议在实现时，先在小规模环境（比如 4×4）上调通，再扩展到大规模。否则 debug 会让人崩溃。

3.8 什么时候选哪个？

说到底，策略迭代和值迭代没有绝对的好坏。我个人的经验是：

• 状态空间小（几百个以内）：用策略迭代。它收敛轮数少，而且你能看到策略一步步变好，心里踏实。
• 状态空间大（几千到几万）：用值迭代。虽然轮数多，但每轮计算量小，总体更快。
• 需要精确最优策略：策略迭代更合适，因为它直接操作策略，不会因为价值函数的微小误差而跑偏。
• 快速原型验证：值迭代代码短，实现快，适合先跑通再优化。

嗯，动态规划这块就聊到这儿。记住一句话：策略迭代是「稳扎稳打」，值迭代是「一步到位」。两种思路，各有千秋，关键看你的场景。