Bellman 期望方程 | Codeboy's Blog

形式陈述

在有限状态、有限非空动作集的折扣 MDP 中，对固定平稳马尔可夫策略 $\pi$ ，状态值函数满足

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

令 $r_\pi(s)=\sum_a\pi(a\mid s)r(s,a)$ 、 $P_\pi(s'\mid s)=\sum_a\pi(a\mid s)P(s'\mid s,a)$ ，可简写为

v_\pi=T^\pi v_\pi, \qquad (T^\pi v)(s)=r_\pi(s)+\gamma(P_\pi v)(s).

有限状态下因此有线性系统 $(I-\gamma P_\pi)v_\pi=r_\pi$ 。动作值版本则是

q_\pi(s,a)=r(s,a)+\gamma\sum_{s'}P(s'\mid s,a) \sum_{a'}\pi(a'\mid s')q_\pi(s',a').

若奖励有界且 $0\le\gamma<1$ ，Bellman 算子在有界函数的上确界范数下是 $\gamma$ -压缩：

\|T^\pi u-T^\pi v\|_\infty =\gamma\|P_\pi(u-v)\|_\infty \le\gamma\|u-v\|_\infty.

最后一步只用到 $P_\pi$ 每行是概率分布。有限状态上的实值函数空间在此范数下完备，且 $T^\pi$ 将它映入自身；Banach 不动点定理于是给出唯一不动点，并保证反复应用 $T^\pi$ 收敛。方程来自回报恒等式 $G_t=R_{t+1}+\gamma G_{t+1}$ 的条件期望和马尔可夫性质。

有限状态下还可把逆矩阵展开为 Neumann 级数：

v_\pi=(I-\gamma P_\pi)^{-1}r_\pi =\sum_{k=0}^{\infty}\gamma^kP_\pi^kr_\pi.

其中 $P_\pi^kr_\pi$ 是从当前状态出发的 $R_{k+1}$ 的期望，前面的 $\gamma^k$ 再施加时间折扣。有限部分和与 $I-\gamma P_\pi$ 相乘等于 $I-(\gamma P_\pi)^{N+1}$ ；余项范数至多为 $\gamma^{N+1}$ ，趋于零。这既证明逆矩阵存在，也把线性代数解、轨迹回报和迭代求值连接起来。

直觉

Bellman 方程是一条“价值账目守恒”：当前位置的长期价值，等于下一步拿到的平均奖励，加上折扣后的下一位置价值。它把无穷未来包进同一个未知函数，使每个状态只需查看一步转移。

压缩性质解释了为什么这个自指方程不会产生许多互相矛盾的解。两个候选价值即使一开始相差很大，做一次 Bellman 更新后差距最多保留 $\gamma$ 倍；反复更新便抹去初始化。随机转移不会扩大 sup norm，折扣负责严格缩小。

例子与边界

设固定策略诱导两状态链

P_\pi=\begin{pmatrix}4/5&1/5\\1/10&9/10\end{pmatrix}, \qquad r_\pi=\begin{pmatrix}1\\0\end{pmatrix}, \qquad \gamma=\tfrac12.

方程 $(I-\gamma P_\pi)v=r_\pi$ 展开为

\tfrac35v_1-\tfrac1{10}v_2=1, \qquad -\tfrac1{20}v_1+\tfrac{11}{20}v_2=0.

第二式给 $v_2=v_1/11$ ，代回得到 $v_1=22/13$ 、 $v_2=2/13$ 。直接检查第一状态：

1+\tfrac12\left(\tfrac45\cdot\tfrac{22}{13}+\tfrac15\cdot\tfrac2{13}\right)=\tfrac{22}{13}.

这项核验能发现转移矩阵左右乘、奖励时序或折扣位置的错误。

当 $\gamma=1$ 时， $P_\pi$ 在 sup norm 中通常只有非扩张性，严格压缩与唯一有界解都可能失效；平均奖励问题需要相对价值和遍历条件。奖励无界时还必须选择合适的加权函数空间。函数逼近下的投影 Bellman 算子也未必继承原算子的 sup-norm 压缩，不能直接沿用表格情形结论。

推论与应用

从任意有界 $v_0$ 迭代 $v_{k+1}=T^\pi v_k$ ，有

\|v_k-v_\pi\|_\infty\le\gamma^k\|v_0-v_\pi\|_\infty,

这就是迭代策略评估的基本保证。若只知道 Bellman 残差，则

\|v-v_\pi\|_\infty\le \frac{\|T^\pi v-v\|_\infty}{1-\gamma}.

该方程也定义了 TD 误差 $R_{t+1}+\gamma V(S_{t+1})-V(S_t)$ 的均值目标。模型已知时可解线性系统；模型未知时可采样近似算子。两者求的是同一个不动点，但数值误差、抽样噪声和函数逼近误差需要分开分析。

参考资料

Richard Bellman, Dynamic Programming, Princeton University Press, 1957, Ch. 3.
Martin L. Puterman, Markov Decision Processes, Wiley, 1994, Secs. 6.1–6.2.
Richard S. Sutton and Andrew G. Barto, Reinforcement Learning: An Introduction, 2nd ed., MIT Press, 2018, Sec. 3.5.

形式陈述 ​

反向链接

形式陈述