强化学习 03：Bellman Optimality Equation

最优值函数

在上一章中，我们讨论的是“给定一个策略 $\pi$ ，这个策略平均能得到多少回报”。这一章的问题换成了：

如果智能体可以自由选择动作，那么从状态 $s$ 出发最多能得到多少回报？

最优状态值函数（optimal state-value function）就是这个问题的答案。它是在所有可能策略中能够取得的最大期望回报：

V^*(s)=\max_\pi V^\pi(s)

这里的上标 $*$ 表示“最优”，而不是某一个特定的策略。换句话说， $V^*(s)$ 只关心最好的结果，不关心达到这个结果具体使用了哪一个策略。

类似地，最优动作值函数回答的是：先在状态 $s$ 执行动作 $a$ ，之后再做最优决策，最多能获得多少期望回报：

Q^*(s,a)=\max_\pi Q^\pi(s,a)

如果已经知道 $Q^*$ ，选取最优动作就很直接：

\pi^*(s)\in\arg\max_a Q^*(s,a)

其中 $\arg\max$ 表示“使目标取得最大值的动作集合”。如果只有一个动作最大，策略就选择它；如果多个动作并列最大，任选一个都可以，这也是最优策略可能不唯一的原因。

Bellman 最优方程

先回顾回报的一步展开

折扣回报可以拆成当前一步奖励和从下一时刻开始的回报：

G_t=R_{t+1}+\gamma G_{t+1}

这条等式非常重要。它告诉我们，长期回报并不是一个必须一次性计算到底的巨大数字，而可以先看眼前得到的奖励，再把未来回报折扣后加回来。

对于固定策略 $\pi$ ，我们已经知道：

V^\pi(s) =\mathbb{E}_\pi \left[ R_{t+1}+\gamma V^\pi(S_{t+1}) \mid S_t=s \right]

最优方程与它的区别只有一个核心问题：当前动作应该按照某个固定策略随机选择，还是应该直接选择最好的动作？最优控制当然要选择后者，因此会出现 $\max$ 。

从最优状态值定义开始推导

下面逐步推导 $V^*$ 的 Bellman 最优方程。为避免跳步，先把“策略”拆成两部分：

当前在状态 $s$ 要执行哪个动作 $a$ ；
执行动作后到达下一状态，之后继续采用什么策略。

从定义出发：

V^*(s)=\max_\pi V^\pi(s)

将 $V^\pi(s)$ 写成回报的期望：

V^*(s) =\max_\pi \mathbb{E}_\pi \left[G_t\mid S_t=s\right]

使用 $G_t=R_{t+1}+\gamma G_{t+1}$ ：

V^*(s) =\max_\pi \mathbb{E}_\pi \left[ R_{t+1}+\gamma G_{t+1} \mid S_t=s \right]

现在观察第一步。策略在状态 $s$ 下首先要决定动作。假设第一步选择了动作 $a$ ，环境随后产生奖励 $R_{t+1}$ ，并转移到状态 $S_{t+1}$ 。因此，“选择最优策略”可以先写成“选择最好的第一步动作”：

V^*(s) =\max_a\max_{\text{后续策略}} \mathbb{E} \left[ R_{t+1}+\gamma G_{t+1} \mid S_t=s,A_t=a \right]

这一步的直观含义是：我们先比较所有当前动作；对于每个当前动作，再假设从下一状态开始也会采用最好的后续策略。

固定第一步动作 $a$ 后，当前奖励的期望由环境决定，而未来部分可以从下一状态开始重新做最优决策：

\max_{\text{后续策略}} \mathbb{E} \left[ G_{t+1}\mid S_{t+1}=s' \right] =V^*(s')

所以有：

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

这就是 Bellman 最优方程的紧凑形式：

当前状态的最优价值 = 当前动作中最好的“即时奖励 + 折扣后的下一状态最优价值”。

这里最容易误解的一点是： $\max$ 不是只挑即时奖励最大的动作。它比较的是整个目标：

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

因此，一个动作即使眼前奖励较小，只要它能把智能体带到更有价值的未来状态，仍然可能是最优动作。

展开环境的随机性

上面的期望形式已经足够表达 Bellman 最优方程，但在有限离散 MDP 中，通常还会把环境的随机性展开。执行 $(s,a)$ 后，环境可能转移到不同的 $s'$ ，并产生不同的奖励 $r$ 。定义联合转移概率：

p(s',r\mid s,a) =P(S_{t+1}=s',R_{t+1}=r\mid S_t=s,A_t=a)

对所有可能的 $(s',r)$ 求加权平均：

\begin{aligned} V^*(s) &=\max_a \mathbb{E} \left[ R_{t+1}+\gamma V^*(S_{t+1}) \mid S_t=s,A_t=a \right]\\ &=\boxed{ \max_a\sum_{s',r}p(s',r\mid s,a) \left[r+\gamma V^*(s')\right]} \end{aligned}

这一行可以按下面的顺序阅读：

固定一个动作 $a$ 。
枚举这个动作可能带来的每个结果 $(s',r)$ 。
对每个结果计算“一步奖励 $r$ 加上未来价值 $\gamma V^*(s')$ ”。
按结果发生的概率 $p(s',r\mid s,a)$ 加权求和。
比较所有动作，取其中最大的值。

如果状态或奖励是连续变量，求和相应替换为积分；推导逻辑完全相同。

一个简单的数字例子

假设当前处于状态 $s$ ，折扣因子为 $\gamma=0.9$ 。有两个动作：左和右。根据当前对未来价值的估计，一步备份得到：

动作	即时奖励	下一状态的期望最优价值	动作总价值
左	$1$	$5$	$1+0.9\times5=5.5$
右	$3$	$2$	$3+0.9\times2=4.8$

虽然“右”的即时奖励更高，但完整目标比较的是 $r+\gamma V^*(s')$ ，所以应该选择“左”：

V^*(s)=\max(5.5,4.8)=5.5

这就是 Bellman 最优方程在做的事情：它不会被眼前的一步奖励牵着走，而是把未来也纳入比较。

最优动作价值方程

状态值函数在当前状态还没有指定动作，所以需要对动作取最大值。动作值函数则固定了当前动作，因此推导会更简单。

从定义出发：

Q^*(s,a)=\max_\pi Q^\pi(s,a)

展开回报：

\begin{aligned} Q^*(s,a) &=\max_\pi\mathbb{E}_\pi \left[G_t\mid S_t=s,A_t=a\right]\\ &=\max_\pi\mathbb{E} \left[ R_{t+1}+\gamma G_{t+1} \mid S_t=s,A_t=a \right] \end{aligned}

第一步动作已经固定为 $a$ ，所以这里不需要再对当前动作求最大值。只有到达下一状态 $S_{t+1}$ 后，才重新选择最好的下一动作。下一状态的最优价值是：

V^*(s')=\max_{a'}Q^*(s',a')

代回上式：

Q^*(s,a) =\mathbb{E} \left[ R_{t+1}+\gamma\max_{a'}Q^*(S_{t+1},a') \mid S_t=s,A_t=a \right]

展开环境转移后得到：

\boxed{ Q^*(s,a) =\sum_{s',r}p(s',r\mid s,a) \left[r+\gamma\max_{a'}Q^*(s',a')\right]}

这条公式和上一条 $V^*$ 方程表达的是同一个最优决策过程，只是观察角度不同：

$V^*(s)$ ：还没有决定当前动作，所以先对动作取 $\max$ 。
$Q^*(s,a)$ ：当前动作已经固定，只需要计算执行它之后的结果。
到达 $s'$ 后，再通过 $\max_{a'}Q^*(s',a')$ 选择下一步最好的动作。

二者的关系为：

\boxed{V^*(s)=\max_a Q^*(s,a)}

为什么是“取最大值”而不是“求平均”

这是 Bellman 期望方程和 Bellman 最优方程最关键的区别。

在固定策略 $\pi$ 下，策略可能以不同概率选择动作，所以状态价值是动作价值的加权平均：

V^\pi(s)=\sum_a\pi(a\mid s)Q^\pi(s,a)

例如，一个策略以 $0.5$ 的概率向左、以 $0.5$ 的概率向右，那么它得到的是两种动作价值的平均，而不是每次都选择更好的那个。

在求最优价值时，我们不是在评价一个已经给定的随机行为，而是在回答“能做到的最好结果是多少”。因此直接选择价值最大的动作：

V^*(s)=\max_a Q^*(s,a)

可以把两种情况简单记成：

问题	动作如何处理	对应方程
这个策略表现如何？	按 $\pi(a\mid s)$ 加权平均	Bellman 期望方程
最好的策略能表现如何？	对动作取最大值	Bellman 最优方程

注意，“取最大值”发生在动作选择上；环境的随机转移仍然要按概率求期望。智能体不能控制环境下一定转移到哪个状态，但可以控制自己当前选择哪个动作。

Bellman 最优算子

定义 Bellman 最优算子：

(\mathcal{T}^*V)(s) =\max_a\mathbb{E} \left[ R_{t+1}+\gamma V(S_{t+1}) \mid S_t=s,A_t=a \right]

它的输入是一个任意的价值函数 $V$ ，输出是在这个价值估计下做一次“最优备份”之后的新价值函数。把 $V$ 换成真正的最优价值 $V^*$ 时，备份前后不会再变化：

V^*=\mathcal{T}^*V^*

这说明 $V^*$ 是 Bellman 最优算子的一个不动点。

当 $\gamma<1$ 时， $\mathcal{T}^*$ 是压缩映射。直观地说，如果两个价值函数一开始相差很大，经过一次最优备份后，它们的差异至多缩小为原来的 $\gamma$ 倍：

\|\mathcal{T}^*V-\mathcal{T}^*U\|_\infty \leq\gamma\|V-U\|_\infty

因此，在满足常见条件的折扣有限 MDP 中， $V^*$ 是唯一的不动点。不断应用 Bellman 最优算子，就得到值迭代：

V_{k+1}(s) \leftarrow \max_a\sum_{s',r}p(s',r\mid s,a) \left[r+\gamma V_k(s')\right]

非线性来自哪里

固定策略的 Bellman 方程中，动作概率 $\pi(a\mid s)$ 已经确定，因此对价值函数只是加权求和，可以写成线性方程组：

V^\pi=r^\pi+\gamma P^\pi V^\pi

Bellman 最优方程则需要在每个状态比较动作并选择最大值：

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

动作究竟哪个最大，取决于未知的 $V^*$ 本身，所以这是一个非线性方程。也正因为如此，通常不能像固定策略评价那样通过一次矩阵求逆直接得到答案，而是使用值迭代、策略迭代或采样方法逐步逼近。

最优价值与最优策略的关系

需要区分两个事实：

在折扣有限 MDP 中，最优值函数通常是唯一的。
最优策略不一定唯一，多个动作可能拥有相同的最优动作价值。

如果策略在每个状态都选择 $Q^*$ 最大的动作，那么它就是最优策略：

\pi^*(s)\in\arg\max_a Q^*(s,a)

也可以把它写成只使用状态最优价值的形式：

\pi^*(s)\in\arg\max_a \mathbb{E} \left[ R_{t+1}+\gamma V^*(S_{t+1}) \mid S_t=s,A_t=a \right]

这就是“对 $V^*$ 做贪心选择”。需要注意，贪心是相对于完整的一步目标而言的：它比较的是即时奖励和下一状态价值之和，而不是只比较即时奖励。

从规划到学习

Bellman 最优方程假设我们能够计算环境期望，也就是知道 $p(s',r\mid s,a)$ 。当环境模型已知时，可以使用动态规划计算上面的求和；当模型未知时，可以用实际采样到的结果近似这个期望。

例如，Q-learning 使用的目标为：

R_{t+1}+\gamma\max_{a'}Q(S_{t+1},a')

它对应 Bellman 最优方程中一次具体样本：

$R_{t+1}$ 是这次真实观察到的即时奖励；
$S_{t+1}$ 是这次真实到达的下一状态；
$\max_{a'}Q(S_{t+1},a')$ 是对下一状态采取最佳动作的当前估计。

因此，动态规划是在知道模型时计算期望，Q-learning 则是在不知道模型时用样本逐渐逼近同一个最优递推关系。

本章小结

Bellman 期望方程评估一个给定策略，Bellman 最优方程则直接描述“从每个状态出发能够做到的最好价值”。它的推导可以记成四步：

把长期回报拆成当前奖励和未来回报。
固定当前动作，计算它带来的即时奖励与下一状态。
假设从下一状态开始继续采取最优决策，用 $V^*$ 表示未来价值。
在所有当前动作中取最大值。

最终得到：

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

以及等价的动作价值形式：

Q^*(s,a) =\sum_{s',r}p(s',r\mid s,a) \left[r+\gamma\max_{a'}Q^*(s',a')\right]

前者强调“当前状态选哪个动作”，后者强调“固定当前动作后，未来如何继续选择”。值迭代、Q-learning 等方法，都是在不同信息条件下求解或近似这两个方程。