Bellman 方程

把值函数写成一步转移后的自身:V=T(V);讨论 Bellman 算子、折扣压缩、单调性与不动点,以及值迭代。

标签 数学 / Bellman 方程 / 动态规划 / 不动点 / MDP

方程

设 𝑆 是状态集,𝐴(𝑠) 是状态 𝑠 的动作集,𝑐(𝑠,𝑎) 是即时代价,𝑃(𝑠′|𝑠,𝑎) 是转移到 𝑠′ 的概率。记 𝑐𝑎=𝑐(𝑠,𝑎),𝑃𝑎(𝑠′)=𝑃(𝑠′|𝑠,𝑎),值函数 𝑉:𝑆→ℝ 满足

𝑉(𝑠)=min𝑎{𝑐𝑎+∑𝑠′𝑃𝑎(𝑠′)𝑉(𝑠′)}.

其中 𝑎 取遍动作集 𝐴(𝑠)。这是 Bellman 方程的 MDP 形式。取最大值时把 min 换成 max;确定性转移把求和换成单个后继的值。

Bellman 方程把值函数写成“一步转移后的自身”。它不是一次递推,而是关于整个值函数的固定点方程。

Bellman 算子

定义算子 (𝒯︀𝑉)(𝑠) 为上式右端:对动作取最小。于是 𝑉 满足 Bellman 方程当且仅当

𝑉=𝒯︀𝑉.

𝒯︀ 把值函数映射成值函数。若转移概率非负,𝒯︀ 保持逐点序:𝑉≤𝑊 时 𝒯︀𝑉≤𝒯︀𝑊。这个单调性是后面讨论不动点的基础。

不动点

折扣情形把后继值乘以折扣因子 𝛾<1。此时 𝒯︀ 是上确界范数下的 𝛾-压缩,存在唯一不动点;从任意有界初值出发的值迭代都会收敛到它。

无折扣时,𝒯︀ 不一定是压缩,Bellman 方程可能有多个不动点,也可能没有有限解。存在性和唯一性需要额外条件,例如随机最短路的 proper policy 条件。

在完备格上,单调算子由 Knaster-Tarski 定理保证最小不动点和最大不动点存在,但两者不一定都等于问题的值。选哪一个取决于问题的序和初值:

  • 布尔可达性常用最小不动点。
  • 在非负扩展实数上,非负权最短路常用最大不动点。例如 𝑑=min(1,0+𝑑) 的所有 𝑑≤1 都是不动点,最短距离 1 是其中最大的;从 +∞ 开始的值迭代收敛到它,最小不动点反而可能给出错误答案。

因此 Bellman 方程本身只给出“值必须满足的方程”,不自动指定唯一解。

求解

值迭代是

𝑉𝑘+1=𝒯︀𝑉𝑘.

压缩情形下它按几何速度收敛;非压缩情形需要单调性、初值和其他收敛条件。MDP 还可以用策略迭代。

确定性最短路可以用松弛、Bellman-Ford 或 Dijkstra 求相应的不动点;无环时,Bellman 方程退化为按拓扑序求值,见 动态规划。

Bellman 方程是正确性刻画,不是算法本身;值迭代、策略迭代和拓扑求值都是求解它的不同方式。

常见误区

  • 认为 Bellman 方程有解就一定有唯一解;无折扣时通常还需要额外条件。
  • 认为任意不动点都是最优值;最小不动点和最大不动点可能对应不同的解。
  • 把 Bellman 方程直接当成值迭代;方程是刻画,值迭代只是求解方法之一。
  • 认为所有最短路都用最小不动点;非负权最短路通常对应最大不动点。
  • 认为 Bellman 方程只适用于 MDP;确定性的最短路、博弈和递归分解也能写成这种形式。
源码位置