3. Bellman Optimality Equation

发布于 2026 年 8 月 17 日

上一篇讨论了固定策略 $\pi$ 的 Bellman 期望方程：给定策略后，可以计算它的状态价值 $v_\pi$。这一篇要解决更进一步的问题：在所有策略中，哪个策略最好，以及怎样计算它？

本文考虑有限状态、有限动作的折扣 MDP，并假设：

$$0 \leq \gamma < 1$$

1. 最优策略与最优价值

如果两个策略 $\pi_1$ 和 $\pi_2$ 满足：

$$v_{\pi_1}(s) \geq v_{\pi_2}(s), \qquad \forall s \in \mathcal S$$

那么称 $\pi_1$ 不劣于 $\pi_2$。如果一个策略 $\pi^*$ 不劣于任意其他策略，即：

$$v_{\pi^*}(s) \geq v_\pi(s), \qquad \forall \pi,\ \forall s \in \mathcal S$$

则称 $\pi^*$ 为最优策略（optimal policy）。最优状态价值函数定义为：

$$\boxed{ v^*(s)=\max_\pi v_\pi(s) }$$

最优动作价值函数定义为：

$$\boxed{ q^*(s,a) =\mathbb E\left[R_{t+1}+\gamma v^*(S_{t+1}) \mid S_t=s,A_t=a\right] }$$

展开环境中的奖励和状态转移后：

$$q^*(s,a) =\sum_r p(r\mid s,a)r +\gamma\sum_{s'}p(s'\mid s,a)v^*(s')$$

它表示：在状态 $s$ 先执行动作 $a$，之后始终采用最优策略时能够获得的期望回报。

2. 从 Bellman 期望方程到最优方程

固定策略 $\pi$ 时，Bellman 期望方程为：

$$v_\pi(s) =\sum_a\pi(a\mid s) \left[ \sum_r p(r\mid s,a)r +\gamma\sum_{s'}p(s'\mid s,a)v_\pi(s') \right]$$

为了寻找最优价值，需要同时对所有策略进行最大化。先把括号中的部分记作动作价值：

$$q(s,a) =\sum_r p(r\mid s,a)r +\gamma\sum_{s'}p(s'\mid s,a)v(s')$$

于是，在单个状态 $s$ 上需要求解：

$$\max_\pi \sum_a \pi(a\mid s)q(s,a)$$

注意 $\pi(a\mid s)$ 是一组概率，所以这个式子只是各动作价值的加权平均。任何加权平均都不会超过其中的最大值：

$$\sum_a\pi(a\mid s)q(s,a) \leq \max_a q(s,a)$$

只要把全部概率分配给价值最大的动作 $a^*$，等号就能成立：

$$a^*(s)\in\arg\max_a q(s,a)$$ $$\pi^*(a\mid s) = \begin{cases} 1, & a=a^*(s) \\ 0, & a\neq a^*(s) \end{cases}$$

因此：

$$\boxed{ \max_\pi\sum_a\pi(a\mid s)q(s,a) =\max_a q(s,a) }$$

这也说明：对于有限 MDP，至少存在一个确定性的最优策略。若多个动作同时达到最大值，可以任选一个，也可以在这些动作之间随机化。

把 $q^*$ 的展开式代入，得到 Bellman 最优方程（Bellman Optimality Equation，BOE）：

$$\boxed{ v^*(s) =\max_a \left[ \sum_r p(r\mid s,a)r +\gamma\sum_{s'}p(s'\mid s,a)v^*(s') \right], \qquad \forall s\in\mathcal S }$$

等价地：

$$\boxed{ v^*(s)=\max_a q^*(s,a) }$$

Bellman 期望方程和 Bellman 最优方程的区别是：

• Bellman 期望方程使用 $\sum_a\pi(a\mid s)$，计算一个给定策略的价值；
• Bellman 最优方程使用 $\max_a$，直接选择当前价值最大的动作，计算最优价值。

3. 矩阵形式与 Bellman 最优算子

对于固定策略 $\pi$，定义：

$$[\mathbf r_\pi]_s =\sum_a\pi(a\mid s)\sum_r p(r\mid s,a)r$$ $$[P_\pi]_{s,s'} =\sum_a\pi(a\mid s)p(s'\mid s,a)$$

它的 Bellman 方程可以写成：

$$\mathbf v_\pi =\mathbf r_\pi+\gamma P_\pi\mathbf v_\pi$$

最优方程常简写为：

$$\mathbf v^* =\max_\pi \left(\mathbf r_\pi+\gamma P_\pi\mathbf v^*\right)$$

这里的 $\max$ 是逐状态取最大值：每个状态都可以选择自己的最优动作，而这些选择合在一起就构成一个策略。定义 Bellman 最优算子 $T$：

$$[T(\mathbf v)]_s =\max_a \left[ \sum_r p(r\mid s,a)r +\gamma\sum_{s'}p(s'\mid s,a)v(s') \right]$$

于是 Bellman 最优方程就是一个不动点方程：

$$\boxed{ \mathbf v^*=T(\mathbf v^*) }$$

接下来需要回答三个问题：

1. 这个不动点是否存在？
2. 这个不动点是否唯一？
3. 能否通过不断应用 $T$ 找到它？

4. 压缩映射

如果映射 $f:X\to X$ 满足：

$$\|f(x)-f(y)\|\leq c\|x-y\|, \qquad 0\leq c<1$$

那么称 $f$ 为压缩映射（contraction mapping）。压缩映射定理告诉我们：

• $f$ 存在不动点 $x^*$，使得 $f(x^*)=x^*$；
• 这个不动点唯一；
• 从任意 $x_0$ 出发，迭代 $x_{k+1}=f(x_k)$ 都会收敛到 $x^*$。

下面证明 Bellman 最优算子 $T$ 在无穷范数下是一个压缩映射。

4.1 一个关于最大值的不等式

对任意两组实数 $\{x_a\}$ 和 $\{y_a\}$：

$$\left|\max_a x_a-\max_a y_a\right| \leq \max_a|x_a-y_a|$$

原因是，设 $a_x\in\arg\max_a x_a$，则：

$$\max_a x_a-\max_a y_a =x_{a_x}-\max_a y_a \leq x_{a_x}-y_{a_x} \leq\max_a|x_a-y_a|$$

交换 $x$ 和 $y$ 后可得到反方向的不等式，因此绝对值形式成立。

4.2 Bellman 最优算子的压缩性

在这个证明中，$\mathbf v$ 和 $\mathbf u$ 已经被当作两个固定的输入向量。动作 $a$ 只是下面这个最大化中的临时变量

对任意两个价值向量 $\mathbf v$ 和 $\mathbf u$，在状态 $s$ 上有：

$$\begin{aligned} |[T(\mathbf v)]_s-[T(\mathbf u)]_s| &= \max_a \left[ \sum_r p(r\mid s,a)r +\gamma\sum_{s'}p(s'\mid s,a)v(s') \right]- \max_a \left[ \sum_r p(r\mid s,a)r +\gamma\sum_{s'}p(s'\mid s,a)u(s') \right] \\ &\leq \max_a\left| \gamma\sum_{s'}p(s'\mid s,a) \bigl(v(s')-u(s')\bigr) \right| \\ &\leq \gamma\max_a\sum_{s'}p(s'\mid s,a) |v(s')-u(s')| \\ &\leq \gamma\max_a\sum_{s'}p(s'\mid s,a) \|\mathbf v-\mathbf u\|_\infty \\ &= \gamma\max_a \|\mathbf v-\mathbf u\|_\infty \sum_{s'}p(s'\mid s,a) \\ &= \gamma\max_a \|\mathbf v-\mathbf u\|_\infty \\ &= \gamma\|\mathbf v-\mathbf u\|_\infty \end{aligned}$$

再对所有状态取最大值：

$$\boxed{ \|T(\mathbf v)-T(\mathbf u)\|_\infty \leq\gamma\|\mathbf v-\mathbf u\|_\infty }$$

因为 $0\leq\gamma<1$，所以 $T$ 是压缩系数为 $\gamma$ 的压缩映射。由压缩映射定理可知：

$$\boxed{ \text{Bellman 最优方程存在唯一解 }\mathbf v^* }$$

同时，不论初始价值如何选择，反复应用 $T$ 都会收敛到 $\mathbf v^*$。

5. Value Iteration

压缩映射定理直接给出求解 Bellman 最优方程的方法——价值迭代（value iteration）：

$$\boxed{ v_{k+1}(s) =\max_a \left[ \sum_r p(r\mid s,a)r +\gamma\sum_{s'}p(s'\mid s,a)v_k(s') \right] }$$

算法步骤如下：

1. 任意初始化 $v_0(s)$，例如全部设为 $0$；
2. 对每个状态和动作计算一步前瞻价值；
3. 对动作取最大值，得到 $v_{k+1}(s)$；
4. 当相邻两次结果足够接近时停止。

伪代码：

value = {state: 0.0 for state in states}

while True:
    delta = 0
    next_value = {}
    for state in states:
        action_values = [
            expected_return(state, action, value)
            for action in actions(state)
        ]
        next_value[state] = max(action_values)
        delta = max(delta, abs(next_value[state] - value[state]))

    value = next_value
    if delta < epsilon:
        break

由压缩性可以得到误差界：

$$\|\mathbf v_k-\mathbf v^*\|_\infty \leq \gamma^k\|\mathbf v_0-\mathbf v^*\|_\infty$$

误差至多按 $\gamma^k$ 的速度衰减。因此 $\gamma$ 越接近 $1$，未来奖励的影响越大，但通常也需要更多次迭代才能收敛。

6*. 从最优价值恢复最优策略

Bellman 最优方程输出的是最大值，而真正执行策略需要取得最大值的动作。当然，这个策略在迭代过程中可以由代码顺便记录下来，这部分是为了说明：

每个状态都选择 argmax 得到的动作后，这些动作组合成的策略确实能够达到 $v^*$

求出 $v^*$ 后，对每个状态进行一次贪心选择：

$$a^*(s) \in\arg\max_a \left[ \sum_r p(r\mid s,a)r +\gamma\sum_{s'}p(s'\mid s,a)v^*(s') \right]$$

等价地：

$$a^*(s)\in\arg\max_a q^*(s,a)$$

定义确定性贪心策略：

$$\boxed{ \pi^*(a\mid s) = \begin{cases} 1, & a=a^*(s) \\ 0, & a\neq a^*(s) \end{cases} }$$

由于 $a^*(s)$ 在每个状态都实现了 Bellman 最优算子的最大值：

$$\mathbf v^* =\mathbf r_{\pi^*}+\gamma P_{\pi^*}\mathbf v^*$$

右边正是策略 $\pi^*$ 的 Bellman 算子。固定策略的 Bellman 方程也有唯一解，因此：

$$\mathbf v^*=\mathbf v_{\pi^*}$$

所以该贪心策略确实是最优策略。注意，价值迭代中的中间结果 $v_k$ 只是对 $v^*$ 的近似；只有在收敛后，或者误差已经足够小时，基于它提取的贪心策略才有最优性保证。

7*. 奖励的仿射变换

奖励变换：

$$r'=ar+b$$

在无限时域折扣任务中，如果 $a>0$，并且常数 $b$ 被加到每一步奖励上，那么任意策略的回报变为：

$$\begin{aligned} G'_t &=\sum_{k=0}^{\infty}\gamma^k(aR_{t+k+1}+b) \\ &=aG_t+\frac{b}{1-\gamma} \end{aligned}$$

因此：

$$v'_\pi(s) =a v_\pi(s)+\frac{b}{1-\gamma}$$

正数缩放和统一平移不会改变各策略之间的大小关系，所以最优策略不变。换句话说，在这些条件下，重要的是奖励的相对关系，而不是绝对数值。

这个结论有适用范围：如果 $a<0$，最大化问题会反转；如果不同策略经历的步数不同，或者常数没有加到终止后的所有时间步上，那么平移奖励也可能改变最优策略

终止后仍把 terminal state 当作吸收状态，才是统一平移，不会改变策略的优劣关系

Summary

Bellman 最优方程把“搜索所有策略”转化成了“在每个状态选择价值最大的动作”：

$$v^*(s) =\max_a \left[ \sum_r p(r\mid s,a)r +\gamma\sum_{s'}p(s'\mid s,a)v^*(s') \right]$$

围绕它可以得到一条完整的求解链路：

$$\text{Bellman 最优算子是压缩映射} \Longrightarrow \text{唯一不动点 }v^* \Longrightarrow \text{价值迭代收敛} \Longrightarrow \text{对 }q^*\text{ 贪心得到 }\pi^*$$

与上一篇的策略评估相比，核心变化是从固定策略下的加权平均 $\sum_a\pi(a\mid s)$，变成了寻找最优动作的 $\max_a$。