1. 动态规划的登场

在第3章中，我们推出了 Bellman Optimality Equation (BOE)：
$$ v^(s) = \max_{a} \sum_{s’} p(s’|s,a) [ r + \gamma v^(s’) ] $$
因为 $\max$ 的非线性，我们无法直接解方程。本章我们将介绍求解 BOE 的两把“倚天屠龙剑”：

  1. Value Iteration (VI, 值迭代)：粗暴直接，对着 BOE 猛算。
  2. Policy Iteration (PI, 策略迭代)：优雅从容，交替进行评估和改进。

这两类算法统称为 动态规划 (Dynamic Programming, DP) 方法。它们要求我们完全已知环境模型（$P$ 和 $R$）。

2. 值迭代 (Value Iteration)

2.1 算法逻辑

VI 的思想非常简单：既然 $v^*$ 是 BOE 的不动点，那我就把 BOE 当作更新规则，一直迭代直到收敛。

$$ v_{k+1}(s) = \max_{a} \underbrace{\sum_{s’} p(s’|s,a) [ r(s,a,s’) + \gamma v_k(s’) ]}_{q_k(s,a)} $$

2.2 Python 实现 (Standard VI)

这是一个标准的 VI 算法模板，可以直接用于解 GridWorld 问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import numpy as np

def value_iteration(P, R, gamma=0.9, theta=1e-4):
    """
    :param P: 状态转移概率 [num_states, num_actions, num_states]
              注意：这里为了通用，假设 P 是三维张量
    :param R: 奖励矩阵 [num_states, num_actions, num_states]
    """
    num_states, num_actions, _ = P.shape
    V = np.zeros(num_states) # 初始化 V
    
    while True:
        delta = 0
        # 1. 对每个状态进行更新
        for s in range(num_states):
            v_old = V[s]
            
            # 2. 计算所有动作的 Q 值
            # Q[a] = sum(P[s,a,s'] * (R[s,a,s'] + gamma * V[s']))
            q_values = np.zeros(num_actions)
            for a in range(num_actions):
                for s_prime in range(num_states):
                    prob = P[s, a, s_prime]
                    if prob > 0:
                        reward = R[s, a, s_prime]
                        q_values[a] += prob * (reward + gamma * V[s_prime])
            
            # 3. 贪心更新 (Bellman Optimality Backup)
            V[s] = np.max(q_values)
            
            # 4. 记录最大变化量
            delta = max(delta, abs(v_old - V[s]))
            
        # 5. 收敛检查
        if delta < theta:
            break
            
    # 6. 提取最优策略
    policy = np.zeros(num_states, dtype=int)
    for s in range(num_states):
        q_values = np.zeros(num_actions)
        for a in range(num_actions):
            for s_prime in range(num_states):
                 q_values[a] += P[s, a, s_prime] * (R[s, a, s_prime] + gamma * V[s_prime])
        policy[s] = np.argmax(q_values)
        
    return policy, V

3. 策略迭代 (Policy Iteration)

3.1 算法逻辑

PI 的思想更符合人类直觉：

  1. 先随便定个策略（比如全往左走）。
  2. Policy Evaluation (PE): 算算这个策略到底能得多少分 ($v_\pi$)。
    • 这里解的是线性方程 $v = r_\pi + \gamma P_\pi v$，比 VI 的 $\max$ 容易。
  3. Policy Improvement (PI): 既然知道各状态的分数了，看看有没有哪个路口换个动作能得分更高？($\pi_{new}(s) = \arg\max q_\pi(s,a)$)。
  4. 重复 2-3，直到策略不再变化。

3.2 为什么 PI 会收敛？

书中给出了严格证明：策略改进定理 (Policy Improvement Theorem) 保证了每次改进后的策略 $v_{\pi_{new}}(s) \ge v_{\pi_{old}}(s)$。因为有限 MDP 的策略总数是有限的（$|\mathcal{A}|^{|\mathcal{S}|}$），所以一定会在有限步内收敛到最优。

3.3 Python 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
def policy_iteration(P, R, gamma=0.9):
    num_states, num_actions, _ = P.shape
    # 1. 初始化随机策略
    policy = np.random.randint(0, num_actions, num_states)
    V = np.zeros(num_states)
    
    while True:
        # --- Step 2: Policy Evaluation ---
        while True:
            delta = 0
            for s in range(num_states):
                v_old = V[s]
                a = policy[s]
                # 只计算当前策略选的动作 a 的价值
                v_new = 0
                for s_prime in range(num_states):
                    v_new += P[s, a, s_prime] * (R[s, a, s_prime] + gamma * V[s_prime])
                V[s] = v_new
                delta = max(delta, abs(v_old - V[s]))
            if delta < 1e-4: break
        
        # --- Step 3: Policy Improvement ---
        policy_stable = True
        for s in range(num_states):
            old_action = policy[s]
            
            # 寻找当前 V 下最好的动作
            q_values = np.zeros(num_actions)
            for a in range(num_actions):
                for s_prime in range(num_states):
                    q_values[a] += P[s, a, s_prime] * (R[s, a, s_prime] + gamma * V[s_prime])
            
            best_action = np.argmax(q_values)
            policy[s] = best_action
            
            if old_action != best_action:
                policy_stable = False
                
        if policy_stable:
            break
            
    return policy, V

4. 截断策略迭代 (Truncated Policy Iteration)

4.1 VI 和 PI 的统一视角

  • PI: Policy Evaluation 步骤要求精确求解 $v_\pi$（比如迭代直到 $\delta < 10^{-4}$，或者解矩阵方程）。这非常耗时。
  • VI: 其实可以看作 Policy Evaluation 只做了一步（更新一次 $V$），就立刻进行 Policy Improvement（取 $\max$）。

Truncated PI: 我们可以折中一下。在 Evaluation 阶段，我不求精确解，只迭代 $k$ 次（比如 5 次），然后就去改进策略。

  • 当 $k=1$ 时，它就是 VI。
  • 当 $k=\infty$ 时，它就是 PI。

这个视角非常重要，它告诉我们：不用追求完美的 Evaluation，差不多的 Value 就能指导出更好的 Policy。

4.2 深度思考：广义策略迭代 (Generalized Policy Iteration, GPI)

Sutton 在其经典教材中提出了 GPI 的概念，它不仅仅是 VI 和 PI 的统称，更揭示了 RL 的核心动力学。
RL 就像是一场**“拔河比赛”**：

  1. Evaluation ($V \to V_\pi$)：试图让 $V$ 贴合当前的 $\pi$（说实话）。
  2. Improvement ($\pi \to \text{greedy}(V)$)：试图让 $\pi$ 变得更贪心（想耍赖）。

这两个过程往往是冲突的：一旦 $\pi$ 变贪心了，$V$ 就不准了；一旦 $V$ 算准了，$\pi$ 又不够贪心了。
GPI 的美妙之处：只要我们持续不断地交替进行这两个过程（哪怕 Evaluation 不准，哪怕 Improvement 不完全），最终它们会在最优解处达成和解（Nash 均衡点）。
$$ v^* = \text{greedy}(v^*) $$
这就是所有 RL 算法（包括 DQN, PPO）能够收敛的底层逻辑。

5. 总结与对比

特性Value Iteration (VI)Policy Iteration (PI)
核心操作一直取 $\max$ (BOE)交替 Eval (解方程) 和 Improve (取 $\max$)
单步计算量小 (只算一遍 Q)大 (PE 阶段要解方程或多次迭代)
收敛步数多 (线性收敛)少 (通常几步就收敛)
适用场景状态空间大，不要求极高精度状态空间小，追求精确解

到此为止，我们已经掌握了有模型 (Model-based) 的所有核心武功。
但在现实中，我们往往不知道 $P$ 和 $R$（比如你不知道股票涨跌的概率公式）。这时候该怎么办？

下一章，我们将进入 Model-free (无模型) 的世界，第一站：蒙特卡洛方法 (Monte Carlo Methods)。

上一章：第3章 - 贝尔曼最优方程 | 下一章：第5章 - 蒙特卡洛方法 >>