强化学习数学原理 - 第4章：值迭代与策略迭代 (Value & Policy Iteration)

1. 动态规划的登场

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

Value Iteration (VI, 值迭代)：粗暴直接，对着 BOE 猛算。
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 问题。

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 的思想更符合人类直觉：

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

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 就像是一场**“拔河比赛”**：

Evaluation ( $V \to V_\pi$ )：试图让 $V$ 贴合当前的 $\pi$ （说实话）。
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章 - 蒙特卡洛方法 >>