Bellman 方程
把值函数写成一步转移后的自身:V=T(V);讨论 Bellman 算子、折扣压缩、单调性与不动点,以及值迭代。标签 数学 / Bellman 方程 / 动态规划 / 不动点 / MDP
方程
设 是状态集, 是状态 的动作集, 是即时代价, 是转移到 的概率。记 ,,值函数 满足
其中 取遍动作集 。这是 Bellman 方程的 MDP 形式。取最大值时把 换成 ;确定性转移把求和换成单个后继的值。
Bellman 方程把值函数写成“一步转移后的自身”。它不是一次递推,而是关于整个值函数的固定点方程。
Bellman 算子
定义算子 为上式右端:对动作取最小。于是 满足 Bellman 方程当且仅当
把值函数映射成值函数。若转移概率非负, 保持逐点序: 时 。这个单调性是后面讨论不动点的基础。
不动点
折扣情形把后继值乘以折扣因子 。此时 是上确界范数下的 -压缩,存在唯一不动点;从任意有界初值出发的值迭代都会收敛到它。
无折扣时, 不一定是压缩,Bellman 方程可能有多个不动点,也可能没有有限解。存在性和唯一性需要额外条件,例如随机最短路的 proper policy 条件。
在完备格上,单调算子由 Knaster-Tarski 定理保证最小不动点和最大不动点存在,但两者不一定都等于问题的值。选哪一个取决于问题的序和初值:
- 布尔可达性常用最小不动点。
- 在非负扩展实数上,非负权最短路常用最大不动点。例如 的所有 都是不动点,最短距离 是其中最大的;从 开始的值迭代收敛到它,最小不动点反而可能给出错误答案。
因此 Bellman 方程本身只给出“值必须满足的方程”,不自动指定唯一解。
求解
值迭代是
压缩情形下它按几何速度收敛;非压缩情形需要单调性、初值和其他收敛条件。MDP 还可以用策略迭代。
确定性最短路可以用松弛、Bellman-Ford 或 Dijkstra 求相应的不动点;无环时,Bellman 方程退化为按拓扑序求值,见 动态规划。
Bellman 方程是正确性刻画,不是算法本身;值迭代、策略迭代和拓扑求值都是求解它的不同方式。
常见误区
- 认为 Bellman 方程有解就一定有唯一解;无折扣时通常还需要额外条件。
- 认为任意不动点都是最优值;最小不动点和最大不动点可能对应不同的解。
- 把 Bellman 方程直接当成值迭代;方程是刻画,值迭代只是求解方法之一。
- 认为所有最短路都用最小不动点;非负权最短路通常对应最大不动点。
- 认为 Bellman 方程只适用于 MDP;确定性的最短路、博弈和递归分解也能写成这种形式。