Bellman 最优性方程 | Codeboy's Blog

形式陈述

有限折扣 MDP 的最优状态值满足

v_*(s)=\max_{a\in\mathcal A(s)} \left[r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)v_*(s')\right].

定义最优 Bellman 算子

(T_*v)(s)=\max_a\{r(s,a)+\gamma(P_av)(s)\},

则 $v_*=T_*v_*$ 。动作值形式为

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

任何在每个状态选取右侧最大动作的策略，都对该有限折扣问题最优。

对任意两个有界函数，利用 $|\max_a x_a-\max_a y_a|\le\max_a|x_a-y_a|$ ，有

\|T_*u-T_*v\|_\infty\le\gamma\|u-v\|_\infty.

有限状态函数空间完备， $T_*$ 又是自映射，所以Banach 不动点定理给出唯一不动点。它还保持偏序： $u\le v$ 蕴含 $T_*u\le T_*v$ 。与固定策略的线性 Bellman 方程不同，最大值让最优性方程成为分段线性的非线性方程。

这个不动点为何就是最优值，还需连接回策略。记不动点为 $u$ ，逐状态选一个使 $T_*u$ 达到最大值的确定性动作，得到平稳策略 $d$ 。此时 $T^d u=u$ ，由固定策略 Bellman 方程的唯一性， $u=v_d$ 。对任意可能依赖历史的策略，每步都有

u(S_t)\ge\mathbb E[R_{t+1}+\gamma u(S_{t+1})\mid H_t].

反复展开 $N$ 步，得到 $u(s)$ 不小于前 $N$ 项折扣奖励的期望加上 $\gamma^N\mathbb E u(S_N)$ ； $u$ 有界使尾项趋零。因此所有续程策略的价值都不超过 $u$ ，而 $d$ 达到它，故 $u=v_*$ 。

一般状态或动作空间中，公式里的最大值可能只能写作上确界；要从数值函数选出可测最优动作，还需紧性、连续性和可测选择等条件。有限情形自动避开了这些技术障碍。

直觉

最优性原理说：如果从当前起的整条计划最优，那么执行第一个动作后，余下计划也必须对实际到达的下一状态最优。于是一个全局策略搜索被拆成“枚举当前动作，再把未来交给同一个最优值函数”。

最大化只发生在当前动作，而转移后的状态仍要按概率求平均。把 $\max$ 错放进对下一状态的求和，会假设行动者能在转移发生前预知随机结果；这赋予了不存在的信息。Bellman 最优性方程把决策与自然随机性的先后次序完整保留下来。

例子与边界

有状态 $s_0,s_1$ 和终止态。 $s_0$ 可“收割”，立即得 $5$ 后终止；也可“培育”，立即得 $0$ 并确定转到 $s_1$ 。在 $s_1$ 只有“出售”，得 $8$ 后终止。取 $\gamma=4/5$ ，则

v_*(s_1)=8, \qquad v_*(s_0)=\max\{5,\tfrac45\cdot8\}=\tfrac{32}{5}.

最优动作是培育，尽管它即时奖励为零。若错把第二步奖励忘记折扣，会得到 $8$ ；若把到达 $s_1$ 后的出售动作也当作 $s_0$ 可直接选动作，则会破坏状态约束。

这个方程只刻画给定模型、期望折扣目标下的最优性。风险约束、部分可观测、鲁棒或平均奖励目标会改变状态或算子。连续动作的上确界未必达到；此时“对 $v_*$ 贪心的最优策略”需要额外存在性条件。函数逼近求得一个小训练残差，也不自动保证全状态的 sup-norm 误差小。

推论与应用

反复应用 $T_*$ 得到价值迭代；固定策略求值后对右侧逐状态贪心，则得到策略迭代。两者依靠同一个不动点，但一个连续更新数值函数，一个在有限策略集合中做改进。

若近似值 $v$ 的最优 Bellman 残差为 $\delta=\|T_*v-v\|_\infty$ ，压缩性给

\|v-v_*\|_\infty\le\frac{\delta}{1-\gamma}.

残差因而是模型已知时可计算的证书；它在 $\gamma$ 接近一时会被 $1/(1-\gamma)$ 放大。Q-learning 使用样本版最优性目标，但其收敛还依赖访问频率和步长，而非仅靠方程存在。

参考资料

Richard Bellman, Dynamic Programming, Princeton University Press, 1957, Ch. 3.
Martin L. Puterman, Markov Decision Processes, Wiley, 1994, Sec. 6.2.
Dimitri P. Bertsekas, Dynamic Programming and Optimal Control, Vol. I, 4th ed., Athena Scientific, 2017, Sec. 1.2.