![[CH03]贝尔曼方程](https://d-sketon.top/img/_backwebp/bg7.webp)
零、写在前面
对于两格世界而言，一共就四种确定性策略。但一旦策略或环境带有随机性，未来会像树一样不断分支，无法沿一条轨迹手算到底。
本章的核心思想是：
$$ \text{从当前状态开始的无限未来} \quad\Longleftrightarrow\quad \text{一步奖励}+\text{折现后的下一状态价值期望}. $$这个自洽关系就是贝尔曼方程（Bellman equation）。
一、贝尔曼方程
1.1 贝尔曼方程的推导
先通过一个简单的例子来回顾概率和期望值。
1.1.1 概率和期望值(复习概率基础知识)
单层随机性：骰子
令随机变量 $X$ 表示公平六面骰子的点数。每个点数概率均为 $1/6$，于是：
$$ \mathbb E[X] =\sum_x x\,p(x) =\frac{1+2+3+4+5+6}{6} =3.5. $$期望不是“某一次一定出现的数”，而是把每种结果按其概率加权后的平均。
两层随机性：骰子决定硬币
我们构造两步试验：
- 先掷骰子，结果记作 $X$；
- 若 $X$ 为奇数，使用正面概率 0.5 的普通硬币；若为偶数，使用正面概率 0.8 的偏置硬币；
- 再抛硬币，结果记作 $Y$。正面时奖励为骰子点数 $X$，反面时奖励为 0。
奖励可写成：
$$ r(x,y)= \begin{cases} x, & y=\text{正面},\\ 0, & y=\text{反面}. \end{cases} $$硬币结果依赖骰子结果，因此用条件概率 $p(y\mid x)$ 表示。两个结果同时出现的概率是：
$$ p(x,y)=p(x)\,p(y\mid x). $$于是奖励期望为：
$$ \mathbb E[r(X,Y)] =\sum_x\sum_y p(x)\,p(y\mid x)\,r(x,y) =2.35. $$也可快速核算：
$$ \frac{(1+3+5)\times0.5+(2+4+6)\times0.8}{6} =2.35. $$其实可以联系下强化学习：
骰子结果 $x$ 可以类比为代理本步选择的行动 $a$，硬币结果 $y$ 可以类比为环境迁移到的下一状态 $s'$。在 MDP 中，一条一步分支的概率正是：
$$ \pi(a\mid s)\,p(s'\mid s,a). $$在该分支上，环境给出奖励 $r(s,a,s')$。对所有 $a,s'$ 的“分支概率 × 分支结果”求和，就是稍后出现的贝尔曼方程。
1.1.2 从收益递推到贝尔曼方程
我们之前定义了收益：
$$ G_t=R_t+\gamma R_{t+1}+\gamma^2R_{t+2}+\cdots. $$把从下一时刻开始的收益单独提出：
$$ G_{t+1}=R_{t+1}+\gamma R_{t+2}+\cdots, $$便得到最重要的递推重写：
$$ G_t=R_t+\gamma G_{t+1}. $$它没有丢弃未来，也不是只看一步；恰恰相反，$G_{t+1}$ 压缩了 $t+1$ 以后全部的无限未来。
状态价值函数的定义为：
$$ v_\pi(s)=\mathbb E_\pi[G_t\mid S_t=s]. $$这里的 $R_t$ 是实际轨迹中观察到的随机奖励；而 $r(s,a,s')$ 表示给定三元组后的环境奖励。在本章的确定奖励设定下，二者相等；若奖励本身随机，则把 $r(s,a,s')$ 理解为其条件期望，因此无须在贝尔曼方程中额外对奖励变量求和。
把收益递推式代入，并利用期望的线性性：
$$ \begin{aligned} v_\pi(s) &=\mathbb E_\pi[R_t+\gamma G_{t+1}\mid S_t=s]\\ &=\mathbb E_\pi[R_t\mid S_t=s] +\gamma\mathbb E_\pi[G_{t+1}\mid S_t=s]. \end{aligned} $$接着逐项展开。当前为 $s$ 时，代理先以 $\pi(a\mid s)$ 选择行动，再以 $p(s'\mid s,a)$ 迁移到 $s'$。因此：
$$ \mathbb E_\pi[R_t\mid S_t=s] =\sum_{a,s'}\pi(a\mid s)p(s'\mid s,a)r(s,a,s'), $$$$ \mathbb E_\pi[G_{t+1}\mid S_t=s] =\sum_{a,s'}\pi(a\mid s)p(s'\mid s,a)v_\pi(s'). $$合并两项，得到：
$$ \boxed{ v_\pi(s) =\sum_{a,s'}\pi(a\mid s)p(s'\mid s,a) \left[r(s,a,s')+\gamma v_\pi(s')\right] }. $$这就是状态价值函数的贝尔曼方程。它对任意固定策略 $\pi$ 成立。
1.2 贝尔曼方程的例子
1.2.1 有两个方格的网格世界
我们回到两格世界。迁移仍然确定，但这次策略是随机的：在 L1、L2 中都以 0.5 的概率选择 Left，以 0.5 的概率选择 Right。
| 当前状态 | 行动 | 下一个状态 | 奖励 |
|---|---|---|---|
| L1 | Left | L1 | -1 |
| L1 | Right | L2 | +1 |
| L2 | Left | L1 | 0 |
| L2 | Right | L2 | -1 |
因为迁移由 $s'=f(s,a)$ 唯一决定，正确后继状态的 $p(s'\mid s,a)=1$，其余候选状态的概率为 0。贝尔曼方程可简化为：
$$ v_\pi(s) =\sum_a\pi(a\mid s) \left[r(s,a,f(s,a))+\gamma v_\pi(f(s,a))\right] $$
令 $\gamma=0.9$。对 L1 展开：
| L1 的分支 | 概率 | 即时奖励 | 后继状态 | 分支贡献 |
|---|---|---|---|---|
| Left | 0.5 | -1 | L1 | $0.5[-1+0.9v_\pi(L1)]$ |
| Right | 0.5 | +1 | L2 | $0.5[1+0.9v_\pi(L2)]$ |
将这两个分支贡献相加：
$$ v_\pi(L1) =0.5\left[-1+0.9v_\pi(L1)\right] +0.5\left[1+0.9v_\pi(L2)\right]. $$对 L2 展开：
$$ v_\pi(L2) =0.5\left[0+0.9v_\pi(L1)\right] +0.5\left[-1+0.9v_\pi(L2)\right]. $$整理为联立一次方程：
$$ \begin{cases} 0.55v_\pi(L1)-0.45v_\pi(L2)=0,\\ -0.45v_\pi(L1)+0.55v_\pi(L2)=-0.5. \end{cases} $$解为：
$$ v_\pi(L1)=-2.25,\qquad v_\pi(L2)=-2.75. $$1.2.2 贝尔曼方程的意义
随机策略对应的回溯图会无限分支，收益也包含无限多个奖励。直接枚举所有未来分支不可行；贝尔曼方程却把问题变成每个状态一个未知数、每个状态一条约束。
在当前例子中：
$$ \text{无限分支的未来} \quad\Longrightarrow\quad \text{两个未知量、两条联立方程}. $$对固定策略而言，贝尔曼方程是线性的，因而可以用线性方程思想或后续的迭代方法求解。最优方程会在后面出现 max 运算，届时不再是普通线性方程。
1.3 行动价值函数与贝尔曼方程
进入 MDP 后，行动的好坏还取决于所在状态，因此行动价值函数写作：
$$ q_\pi(s,a) =\mathbb E_\pi[G_t\mid S_t=s,A_t=a] $$它表示：当前处于 $s$ 时，先强制采取行动 $a$，从下一步开始再按策略 $\pi$ 行动，所得到的期望折现收益。
1.3.1 行动价值函数
状态价值与行动价值只有一个关键差别：
| 函数 | 本步行动由谁决定 | 条件 |
|---|---|---|
| $v_\pi(s)$ | 由策略 $\pi$ 随机选择 | 当前状态 $s$ |
| $q_\pi(s,a)$ | 本步行动固定为 $a$ | 当前状态 $s$ 与当前行动 $a$ |
所以，若要从 $q_\pi$ 恢复 $v_\pi$，只需按策略对当前行动加权平均：
$$ \boxed{ v_\pi(s)=\sum_a\pi(a\mid s)q_\pi(s,a) } $$请特别注意：$q_\pi(s,a)$ 中的 $a$ 不必是策略 $\pi$ 在状态 $s$ 下最可能选的行动。它可以是任何候选行动；固定它之后，才从下一时刻开始遵循 $\pi$。
这正是 Q 函数有用的原因：它让我们能并排比较“当前状态下，如果先做不同动作，长期后果分别如何”。
1.3.2 使用行动价值函数的贝尔曼方程
当前 $s,a$ 已经固定，因此本步不再对 $\pi(a\mid s)$ 求平均；我们只需对环境可能的下一状态 $s'$ 求平均：
$$ \boxed{ q_\pi(s,a) =\sum_{s'}p(s'\mid s,a) \left[r(s,a,s')+\gamma v_\pi(s')\right] } $$再将上一小节的关系
$$ v_\pi(s')=\sum_{a'}\pi(a'\mid s')q_\pi(s',a') $$代入，就得到：
$$ \boxed{ q_\pi(s,a) =\sum_{s'}p(s'\mid s,a) \left[ r(s,a,s') +\gamma\sum_{a'}\pi(a'\mid s')q_\pi(s',a') \right] } $$这里的 $a'$ 是下一时刻的行动，不能和已经固定的当前行动 $a$ 混淆。
1.4 贝尔曼最优方程
普通贝尔曼方程回答的问题是：“若以后固定遵循策略 $\pi$，价值是多少？”
强化学习最终的问题却是：“在每个状态怎样行动才能最好？”
这就把“按策略取期望”替换为“选择最好的行动”。
1.4.1 状态价值函数的贝尔曼最优方程
最优状态价值函数定义为：
$$ v^*(s)=\max_\pi v_\pi(s). $$从 $\max_\pi$ 过渡到 $\max_a$ 的原因是：先假定当前选择了某个候选行动 $a$，环境到达 $s'$ 后的 $v^*(s')$ 已经代表“此后始终按最优方式继续”的价值。因此，只需比较当前每个候选行动带来的长期价值。
在有限、折现 MDP 中，存在可取为确定性策略的最优策略。
比如二格世界，已经有确定性策略了，那么只需要关注action即可。
因此，在状态 $s$ 下应选择令“一步奖励 + 最优未来价值”最大的行动：
$$ \boxed{ v^*(s) =\max_a\sum_{s'}p(s'\mid s,a) \left[r(s,a,s')+\gamma v^*(s')\right] }. $$这就是状态价值函数的贝尔曼最优方程。
普通方程与最优方程最关键的区别如下：
| 固定策略 | 最优策略 |
|---|---|
| $\sum_a\pi(a\mid s)$ | $\max_a$ |
| 评价已经给定的策略 | 寻找可达到最高价值的策略 |
| 对固定策略通常是线性关系 | 含最大化，通常是非线性关系 |
max 会返回最大数值。例如候选值为 $-2,0,4$ 时，max 的结果是 $4$；最优策略以概率 1 选择产生 4 的行动。
1.4.2 Q 函数的贝尔曼最优方程
最优行动价值函数为：
$$ q^*(s,a) =\sum_{s'}p(s'\mid s,a) \left[ r(s,a,s') +\gamma\max_{a'}q^*(s',a') \right]. $$它的时间顺序十分重要：
- 当前行动 $a$ 已给定；
- 环境随机迁移到 $s'$；
- 从 $s'$ 开始，未来选择使 $q^*(s',a')$ 最大的行动 $a'$。
这解释了为什么公式中的最大化是 $\max_{a'}$，而不是 $\max_a$：当前的 $a$ 已经在 $q^*(s,a)$ 的条件中固定。
1.5 应用贝尔曼最优方程
我们再次使用两格世界，不过这次不再固定随机策略，而是直接求最优价值。
1.5.1 应用贝尔曼最优方程
两格世界的迁移是确定性的，因此：
$$ p(s'\mid s,a)= \begin{cases} 1, & s'=f(s,a),\\ 0, & s'\ne f(s,a). \end{cases} $$最优方程可简化为：
$$ v^*(s) =\max_a \left[r(s,a,f(s,a))+\gamma v^*(f(s,a))\right]. $$令 $\gamma=0.9$，对两个状态分别写出方程：
$$ v^*(L1) =\max \left\{ -1+0.9v^*(L1), \quad 1+0.9v^*(L2) \right\}, $$$$ v^*(L2) =\max \left\{ 0+0.9v^*(L1), \quad -1+0.9v^*(L2) \right\}. $$这是一组包含最大化的非线性联立方程。小问题可手算；一般问题将在后面用价值迭代等方法处理。
不难求出：
$$ v^*(L1)\approx5.26,\qquad v^*(L2)\approx4.73. $$与 3.2 的随机策略的 \(-2.25,-2.75\) 对比：
| 评估对象 | L1 价值 | L2 价值 | 原因 |
|---|---|---|---|
| 随机策略 $\pi$ | -2.25 | -2.75 | 经常撞墙 |
| 最优策略 $\pi^*$ | 5.26 | 4.73 | 在两格间往返拿苹果 |
这两组结果来自同一个环境和同一个折现率，但策略不同。
1.5.2 得到最优策略
已知最优 Q 函数时，最优策略通过以下式子得到：
$$ \boxed{ \mu^*(s)=\operatorname*{argmax}_a q^*(s,a) }. $$max 和 argmax 的区别必须彻底分清：
| 运算 | 返回什么 | 两格世界 L1 的例子 |
|---|---|---|
| $\max_a q^*(L1,a)$ | 最大的价值数值 | 精确值 $100/19\approx5.263$ |
| $\operatorname*{argmax}_a q^*(L1,a)$ | 取得最大值的行动 | Right |
若只有最优状态价值 $v^*$，也能选择最优行动：
$$ \boxed{ \mu^*(s) =\operatorname*{argmax}_a \sum_{s'}p(s'\mid s,a) \left[r(s,a,s')+\gamma v^*(s')\right] }. $$
我们使用前面已经计算出的最优状态价值函数 $v^*(L1)=5.26$、$v^*(L2)=4.73$ 作比较：
$$ \begin{aligned} \text{Left}:&\quad -1+0.9\times5.26=3.734,\\ \text{Right}:&\quad 1+0.9\times4.73=5.257. \end{aligned} $$因此 L1 应选 Right。类似地，在 L2 中：
$$ \begin{aligned} \text{Left}:&\quad 0+0.9\times5.26=4.734,\\ \text{Right}:&\quad -1+0.9\times4.73=3.257. \end{aligned} $$所以 L2 应选 Left。最终策略是在两格之间往返：
如上所述，一旦知道了最优状态价值函数，就可以得到最优策略。
1.6 小结
我们建立了强化学习最重要的递归语言：价值等于一步奖励加上折现后的未来价值，并对所有不确定性正确求平均。
说些什么吧！