1. 终极目标：寻找最优策略

在第2章中，我们学会了“给定一个策略，评估它好不好（Policy Evaluation）”。但这只是第一步，RL 的终极目标是找到最好的那个策略（Optimal Policy, $\pi^*$）。

什么叫“最好”？
数学定义：如果策略 $\pi^$ 的状态价值 $v_{\pi^}(s)$ 在每一个状态 $s$ 上都不低于其他任何策略 $\pi$ 的价值 $v_\pi(s)$，那么 $\pi^$ 就是最优策略。
$$ v_{\pi^}(s) \ge v_\pi(s), \quad \forall s \in \mathcal{S}, \forall \pi $$

直观理解：
最优策略就像一个完美的导航仪，无论你现在身处何地（哪怕是被风吹到了错误的格子），它都能告诉你接下来该怎么走才能获得最大的未来回报。

2. 贝尔曼最优方程 (Bellman Optimality Equation, BOE)

2.1 从 Bellman Equation 到 BOE

回忆普通贝尔曼方程：
$$ v_\pi(s) = \sum_{a} \pi(a|s) \underbrace{\left( \sum_{s’} p(s’|s,a) [ r + \gamma v_\pi(s’) ] \right)}{q\pi(s,a)} $$

如果我们想要 $v(s)$ 最大，那么在选择动作 $a$ 时，就不应该犹豫，而应该只选 Q 值最大的那个动作。
于是，求和号 $\sum_a \pi(a|s)$ 变成了取最大值 $\max_a$：

$$ v^(s) = \max_{a \in \mathcal{A}} \underbrace{\sum_{s’} p(s’|s,a) [ r(s,a,s’) + \gamma v^(s’) ]}_{q^*(s,a)} $$

这就是 Bellman Optimality Equation (BOE)。它描述了最优状态价值 $v^*$ 必须满足的递归关系。

2.2 为什么 BOE 很难解？

对比一下：

  • Bellman Equation (BE): $v = R_\pi + \gamma P_\pi v$。这是线性方程，可以直接 $v = (I - \gamma P)^{-1} R$。
  • Bellman Optimality Equation (BOE): $v = \max (R + \gamma P v)$。这里有个 $\max$ 操作。
    • $\max(a+b) \ne \max(a) + \max(b)$。
    • $\max$ 是非线性的。
    • 结论：我们不能用矩阵求逆来解 BOE！必须使用迭代算法（Value Iteration）。

3. 压缩映射定理 (Contraction Mapping Theorem)

这是 RL 中最硬核的数学理论之一，它保证了 Value Iteration 算法一定会收敛。

3.1 什么是压缩映射？

把 BOE 的右边看作一个算子（Operator）$f$：
$$ f(v) = \max_a (R_a + \gamma P_a v) $$
如果能证明对于任意两个向量 $v_1, v_2$，经过 $f$ 变换后，它们的距离变小了：
$$ | f(v_1) - f(v_2) |\infty \le \gamma | v_1 - v_2 |\infty $$
因为 $\gamma < 1$，所以 $f$ 是一个压缩映射。

3.2 不动点 (Fixed Point)

根据 Banach Fixed Point Theorem：

  1. 存在性：$v^* = f(v^*)$ 一定存在。
  2. 唯一性：$v^*$ 是唯一的。
  3. 收敛性：任意初始化 $v_0$，只要不断算 $v_{k+1} = f(v_k)$，最终一定收敛到 $v^*$。

简单人话：你随便猜一个 Value Table，只要不断用“贪心”的方式更新它，最后它一定会变成真正的最优 Value Table。

3.3 深度思考：压缩映射的物理意义

为什么 $\gamma < 1$ 就能保证压缩？
$$ | v_{k+1} - v^* | \le \gamma | v_k - v^* | $$
这表示每次迭代，我们离真理的距离都会缩小 $\gamma$ 倍。
物理意义：
$\gamma$ 是折扣因子，它代表了我们对未来的**“遗忘速度”**。

  • 如果 $\gamma \approx 0$，Agent 是超级近视眼，只看眼前。任何遥远的误差都影响不到现在，所以收敛极快。
  • 如果 $\gamma \approx 1$，Agent 是远视眼，千秋万代都要考虑。远处的微小误差都会传递到现在，所以收敛很慢。
    结论：压缩映射的本质是**“用时间的衰减来消除初始猜测的错误”**。

4. 最优策略的确定性

一个有趣且重要的结论：对于有限 MDP，总是存在一个确定性的最优策略（Deterministic Optimal Policy）。

这意味着最优策略不需要随机扔骰子（不需要 $\pi(a|s) = 0.5$）。
$$ \pi^(s) = \arg\max_{a} q^(s, a) $$
在每个路口，只要坚定地走 Q 值最大的那条路就行了。如果有多个动作 Q 值一样大，随便选一个确定的即可。

5. Python 代码实战：验证最优性

在第2章的代码中，我们计算了一个随机策略的 Value。现在我们来“手动”算一下最优策略。

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
import numpy as np

# 假设环境参数 (同 Chapter 2)
# s1, s2, s3, s4
# 只有 s1 面临选择：
# Action 1 (去 s1/s2): r=-1
# Action 2 (去 s3): r=0 (假设有一条捷径)

# ... (定义 P 和 R) ...

def calculate_optimal_value(max_iter=1000, gamma=0.9):
    # 初始化 v
    v = np.zeros(4)
    
    for k in range(max_iter):
        v_old = v.copy()
        
        # 对 s1: max( q(s1, a1), q(s1, a2) )
        # q(s1, a1) = -1 + gamma * (0.5*v[0] + 0.5*v[1])
        # q(s1, a2) = 0 + gamma * v[2]
        
        q_s1_a1 = -1.0 + gamma * (0.5 * v[0] + 0.5 * v[1])
        q_s1_a2 = 0.0 + gamma * v[2] # 假设 a2 直接到 s3
        
        v[0] = max(q_s1_a1, q_s1_a2) # BOE 的核心 max
        
        # 其他状态假设不动
        v[1] = 0 + gamma * v[3]
        v[2] = 1 + gamma * v[3]
        v[3] = 0 # 终点
        
        if np.max(np.abs(v - v_old)) < 1e-6:
            print(f"Converged at step {k}")
            break
            
    return v

v_star = calculate_optimal_value()
print("Optimal State Values:", v_star)

通过这段代码逻辑，我们可以看到 Value Iteration 的雏形：算 Q 值 -> 取 Max -> 更新 V。

6. 总结

本章解决了 RL 的核心目标问题：

  1. 定义最优：$v^*(s) \ge v_\pi(s)$。
  2. 方程描述：$v^* = \max (R + \gamma P v^*)$。
  3. 求解难点：非线性，无法矩阵求逆。
  4. 理论保障：压缩映射定理保证了迭代法的收敛性。

这为下一章正式介绍 Value Iteration (VI) 和 Policy Iteration (PI) 算法铺平了道路。

上一章：第2章 - 贝尔曼方程 | 下一章：第4章 - 值迭代与策略迭代 >>