贝尔曼方程

一句话总结 · 要点速览

• 贝尔曼方程把一个状态的价值写成“即时奖励 + 折扣后的下一状态价值”的期望，即 v_π(s) = E_π[R_{t+1} + γ v_π(S_{t+1}) | S_t = s]。
• 贝尔曼期望方程描述给定策略 π 的价值；贝尔曼最优方程用 max 代替按策略求平均，描述最优价值函数 v_* 和 q_*。
• 对已知模型的有限 MDP，贝尔曼期望方程是线性方程组，可以直接求解析解，也可以迭代求解。
• 几乎所有价值类强化学习算法（DP、TD、Q-learning、DQN）都是在用不同方式近似求解贝尔曼方程。

术语不熟悉？查看 强化学习术语表。

贝尔曼方程（Bellman equation）揭示了价值函数的递归结构：一个状态的价值，等于“走一步拿到的即时奖励”加上“下一个状态价值的折扣期望”。它分为描述给定策略价值的贝尔曼期望方程和描述最优价值的贝尔曼最优方程。几乎所有强化学习算法——动态规划、TD 学习、Q-learning、DQN、Actor-Critic——都可以看作在用不同方式近似求解这两个方程。

本节沿用 MDP 一节的记号：状态 $s$、动作 $a$、动力学 $p(s^{\prime },r\mid s,a)$、折扣因子 $\gamma$、策略 $\pi (a\mid s)$、价值函数 $v_{\pi }(s)$ 与 $q_{\pi }(s,a)$。

动机：为什么需要递归形式

按定义，$v_{\pi }(s)={\mathbb{E}}_{\pi }[G_t\mid S_t=s]$ 是对无穷长未来的期望，直接计算需要枚举所有可能的轨迹，这在任何有意义的问题上都不可行。

关键观察是回报本身满足递归关系：

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

于是“对整条未来求期望”可以拆成“对一步求期望 + 对下一个状态的价值求期望”。这样价值函数就满足一组只涉及相邻两个时刻的方程，可以迭代求解，也可以从单步样本中学习。

贝尔曼期望方程

状态价值函数的递归形式

从定义出发，利用 $G_t=R_{t+1}+\gamma G_{t+1}$ 和马尔可夫性：

$$\begin{array}{rl}{v}_{\pi }(s)& ={\mathbb{E}}_{\pi }[R_{t+1}+\gamma G_{t+1}\mid S_t=s]\\ & =\sum _a\pi (a\mid s)\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)[r+\gamma {\mathbb{E}}_{\pi }[G_{t+1}\mid S_{t+1}=s^{\prime }]]\\ & =\sum _a\pi (a\mid s)\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)[r+\gamma v_{\pi }(s^{\prime })]\end{array}$$

这就是 $v_{\pi }$ 的贝尔曼期望方程。读法是：先按策略对动作取平均，再按环境动力学对下一状态和奖励取平均，括号里是“即时奖励 + 折扣后的下一状态价值”。

动作价值函数的递归形式

同理可得：

$$q_{\pi }(s,a)=\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)[r+\gamma \sum _{a^{\prime }}\pi (a^{\prime }\mid s^{\prime })q_{\pi }(s^{\prime },a^{\prime })]$$

$v_{\pi }$ 与 $q_{\pi }$ 之间的两条桥梁是：

$$v_{\pi }(s)=\sum _a\pi (a\mid s)q_{\pi }(s,a),q_{\pi }(s,a)=\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)[r+\gamma v_{\pi }(s^{\prime })]$$

把其中一条代入另一条，就得到上面两个方程。

矩阵形式与解析解

对有限 MDP，记

• $r_{\pi }(s)=\sum _a\pi (a\mid s)\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)r$：策略 $\pi$ 下的期望即时奖励；
• $P_{\pi }(s,s^{\prime })=\sum _a\pi (a\mid s)p(s^{\prime }\mid s,a)$：策略 $\pi$ 下的状态转移矩阵。

则贝尔曼期望方程可以写成线性方程组：

$${\mathbf{v}}_{\pi }={\mathbf{r}}_{\pi }+\gamma P_{\pi }{\mathbf{v}}_{\pi }⟹{\mathbf{v}}_{\pi }=(I-\gamma P_{\pi }{)}^{-1}{\mathbf{r}}_{\pi }$$

当 $\gamma <1$ 时 $I-\gamma P_{\pi }$ 一定可逆（$P_{\pi }$ 的谱半径不超过 1）。直接求逆的复杂度是 $O(|\mathcal{S}{|}^3)$，只适合小规模问题；大规模问题需要用迭代法（动态规划）或采样法（蒙特卡洛、TD 学习）。

贝尔曼算子与压缩映射

定义贝尔曼期望算子 ${\mathcal{T}}^{\pi }$：

$$({\mathcal{T}}^{\pi }v)(s)=\sum _a\pi (a\mid s)\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)[r+\gamma v(s^{\prime })]$$

则 $v_{\pi }$ 是 ${\mathcal{T}}^{\pi }$ 的不动点：$v_{\pi }={\mathcal{T}}^{\pi }{v}_{\pi }$。可以证明 ${\mathcal{T}}^{\pi }$ 在无穷范数下是 $\gamma$-压缩映射：

$$\parallel {\mathcal{T}}^{\pi }u-{\mathcal{T}}^{\pi }v{\parallel }_{\mathrm{\infty }}\le \gamma \parallel u-v{\parallel }_{\mathrm{\infty }}$$

由巴拿赫不动点定理，从任意 $v_0$ 出发反复应用 ${\mathcal{T}}^{\pi }$，都会以几何速度收敛到唯一不动点 $v_{\pi }$。这正是迭代策略评估的理论基础。

贝尔曼最优方程

最优状态价值

最优价值函数 $v_{\ast }(s)=\underset{\pi }{max}{v}_{\pi }(s)$ 满足：最优策略在每个状态都会选择最好的动作，因此“对动作取平均”变成“对动作取最大”：

$$v_{\ast }(s)=\underset{a}{max}\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)[r+\gamma v_{\ast }(s^{\prime })]$$

最优动作价值

$$q_{\ast }(s,a)=\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)[r+\gamma \underset{a^{\prime }}{max}{q}_{\ast }(s^{\prime },a^{\prime })]$$

一旦得到 $q_{\ast }$，最优策略就是贪心策略 ${\pi }_{\ast }(s)=\arg \underset{a}{max}{q}_{\ast }(s,a)$，不需要知道环境模型——这正是 Q-learning 和 DQN 学习 $q_{\ast }$ 的原因。

相应的贝尔曼最优算子 $({\mathcal{T}}^{\ast }v)(s)=\underset{a}{max}\sum _{s^{\prime },r}p(s^{\prime },r\mid s,a)[r+\gamma v(s^{\prime })]$ 同样是 $\gamma$-压缩映射，反复应用它就是 价值迭代。

为什么没有闭式解

期望方程是线性的，可以直接解线性方程组；最优方程中含有 $max$ 运算，是非线性的，一般没有闭式解，只能迭代求解。此外，直接求解贝尔曼最优方程还需要：(1) 已知环境动力学；(2) 足够的计算资源遍历所有状态；(3) 马尔可夫性成立。现实中这三条往往不能同时满足，所以强化学习算法本质上都是在近似求解贝尔曼最优方程。

回溯图（Backup Diagram）

回溯图用图形表示一次更新“从哪里取信息”。空心圆表示状态，实心圆表示状态—动作对：

flowchart TD
  s((s)) -->|"π(a|s)"| a1((s,a₁))
  s -->|"π(a|s)"| a2((s,a₂))
  a1 -->|"p(s',r|s,a)"| s1((s'))
  a1 -->|"p(s',r|s,a)"| s2((s''))
  a2 -->|"p(s',r|s,a)"| s3((s'''))

• $v_{\pi }$ 的回溯：从 $s$ 出发，对动作按 $\pi$ 加权，再对后继状态按 $p$ 加权，把后继状态的价值“回传”给 $s$。
• $v_{\ast }$ 的回溯：结构相同，但在动作这一层取最大值而不是加权平均。

不同算法的区别可以概括为回溯的宽度（是否对所有可能的后继求期望）和深度（是只看一步还是一直看到回合结束）：

方法	宽度	深度
动态规划	全宽（对所有后继求期望）	一步
蒙特卡洛	采样（单条轨迹）	整个回合
TD(0)	采样	一步
穷举搜索	全宽	整个回合

例题：FrozenLake 上的价值计算

下面在 Gymnasium 的 FrozenLake-v1（4×4，地面打滑）上，计算均匀随机策略的状态价值，分别用矩阵解析解和反复应用贝尔曼期望算子两种方法，验证两者一致。env.unwrapped.P 给出了完整的环境模型 P[s][a] = [(概率, 下一状态, 奖励, 是否终止), ...]。

"""贝尔曼期望方程：用矩阵形式求解 FrozenLake 上均匀随机策略的状态价值，并与迭代法对比。"""
import gymnasium as gym
import numpy as np

env = gym.make("FrozenLake-v1", is_slippery=True)
P = env.unwrapped.P            # P[s][a] = [(prob, s_next, reward, terminated), ...]
nS, nA = env.observation_space.n, env.action_space.n
gamma = 0.9
pi = np.full((nS, nA), 1.0 / nA)   # 均匀随机策略 π(a|s)

# 构造 P_π（nS×nS）和 r_π（nS）
P_pi = np.zeros((nS, nS))
r_pi = np.zeros(nS)
for s in range(nS):
    for a in range(nA):
        for prob, s2, r, done in P[s][a]:
            P_pi[s, s2] += pi[s, a] * prob * (0.0 if done else 1.0)  # 终止后不再有未来价值
            r_pi[s] += pi[s, a] * prob * r

# 方法一：解析解 v = (I - γ P_π)^{-1} r_π
v_exact = np.linalg.solve(np.eye(nS) - gamma * P_pi, r_pi)

# 方法二：反复应用贝尔曼期望算子直到收敛
v = np.zeros(nS)
for it in range(1000):
    v_new = r_pi + gamma * P_pi @ v
    if np.max(np.abs(v_new - v)) < 1e-10:
        break
    v = v_new

print("解析解：\n", v_exact.reshape(4, 4).round(4))
print(f"迭代 {it} 次后与解析解的最大误差: {np.max(np.abs(v - v_exact)):.2e}")

在本站环境（Gymnasium 1.4.0）中实际运行的输出如下：

解析解：
 [[0.0045 0.0042 0.0101 0.0041]
 [0.0067 0.     0.0263 0.    ]
 [0.0187 0.0576 0.107  0.    ]
 [0.     0.1304 0.3915 0.    ]]
迭代 63 次后与解析解的最大误差: 3.30e-10

可以看到：(1) 随机策略下起点价值只有约 0.0045，说明随机乱走几乎到不了终点；(2) 越靠近右下角终点，价值越高；(3) 冰洞和终点是终止状态，价值为 0；(4) 迭代法 63 次后与解析解的误差已在 ${10}^{-10}$ 量级，印证了压缩映射的几何收敛。

常见误区

• 把终止状态的价值也算进去：到达终止状态后不再有未来奖励，计算目标时要乘以 $(1-\text{done})$。代码里 (0.0 if done else 1.0) 就是这个作用。
• 混淆期望方程和最优方程：前者评估“某个给定策略有多好”，后者刻画“最好能有多好”。
• 以为 $v_{\ast }$ 唯一意味着最优策略唯一：最优价值函数唯一，但可能有多个动作并列最优，因此最优策略可以不唯一。

小结

• 回报的递归关系 $G_t=R_{t+1}+\gamma G_{t+1}$ 导出了价值函数的贝尔曼方程。
• 贝尔曼期望方程是线性的，可直接求解；贝尔曼最优方程含 $max$，需要迭代求解。
• 两个贝尔曼算子都是 $\gamma$-压缩映射，保证了迭代算法的收敛。
• 后续所有算法都可以看作用不同的“宽度 × 深度”回溯来近似求解贝尔曼方程。

练习题

1. 从 $q_{\pi }$ 的定义出发，完整推导 $q_{\pi }$ 的贝尔曼期望方程。
2. 证明贝尔曼期望算子 ${\mathcal{T}}^{\pi }$ 在无穷范数下是 $\gamma$-压缩映射。（提示：$|\sum _i{w}_i{x}_i|\le \underset{i}{max}|x_i|$，其中 $w_i\ge 0,\sum _i{w}_i=1$。）
3. 在 MDP 一节的两状态例子中，写出贝尔曼最优方程并手算 $v_{\ast }(A)$、$v_{\ast }(B)$。
4. 修改例题代码，把 $\gamma$ 改为 0.99，起点价值如何变化？为什么？
5. 修改例题代码，计算“永远向右”的确定性策略的价值，并与随机策略比较。

延伸阅读

交互工具：网格世界：价值迭代 / 策略迭代可视化

参考文献

• Bellman, R. (1957). Dynamic Programming. Princeton University Press.
• Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.), 第 3 章. MIT Press.

下一步

继续阅读：动态规划——用迭代的方式求解贝尔曼方程，并找到最优策略。