贝尔曼方程及其数学性质

贝尔曼方程（Bellman equation）是动态规划的核心，本质是把一个多阶段的决策问题拆成当前决策 + 剩余子问题的递归关系。它由理查德·贝尔曼在 20 世纪 50 年代提出，是强化学习、最优控制、经济学等领域的基础工具。

贝尔曼方程（Bellman Equation）是动态规划（Dynamic Programming）和强化学习（Reinforcement Learning）中的核心数学方程，用于描述一个系统在当前状态下的最优价值，如何由当前收益和未来状态的价值共同决定。

简单来说：当前状态的价值 = 当前获得的收益 + 未来可能获得的折扣收益。它的核心思想是：一个复杂的长期决策问题，可以分解为一系列相互关联的短期决策问题。

它不是某一个孤立的等式，而是一族把值函数与自身联系起来的泛函方程。它的数学内容可以概括为三个层次。第一，折扣回报在时间上的递归分解。第二，一个定义在有界函数空间上的算子。第三，该算子的不动点。动态规划与强化学习中的许多结论，本质上都是这三个层次的不同推论。

一、形式化

1.1 折扣马尔可夫决策过程

定义 1.1（折扣马尔可夫决策过程） #

设 $S$ 为状态集， $A$ 为动作集， $P(s'\mid s,a)$ 为在状态 $s$ 执行动作 $a$ 后转移到状态 $s'$ 的概率， $r:S\times A\times S\to\mathbb{R}$ 为奖励函数， $\gamma\in[0,1)$ 为折扣因子。记 $\mathcal{F}_t$ 为截至时刻 $t$ 的历史信息。若对任意 $t$ ，

\begin{aligned} P(s_{t+1}=s'\mid s_t=s,a_t=a,\mathcal{F}_t) &=P(s_{t+1}=s'\mid s_t=s,a_t=a), \end{aligned}

则称该序贯决策问题为折扣马尔可夫决策过程（discounted Markov decision process，折扣 MDP），记作 $\mathcal{M}=(S,A,P,r,\gamma)$ 。

本文默认 $S$ 与 $A$ 均为有限集，且存在常数 $R_{\max}<\infty$ 使得 $|r(s,a,s')|\le R_{\max}$ 对一切 $(s,a,s')$ 成立。有限性假设保证最大值可以取到，后文会在第 7 节说明连续状态空间中的相应修改。

一个策略 $\pi$ 是映射 $S\to\Delta(A)$ ，其中 $\Delta(A)$ 是动作集上的概率单纯形。 $\pi(a\mid s)$ 表示在状态 $s$ 选择动作 $a$ 的概率。若对每个 $s$ ， $\pi(a\mid s)$ 只在某一个动作处取 $1$ ，则称 $\pi$ 为确定性策略，并可将其视为映射 $\pi:S\to A$ 。

1.2 回报与值函数

定义 1.2（折扣回报） #

设轨迹为 $s_0,a_0,s_1,a_1,\dots$ ，记

r_t=r(s_t,a_t,s_{t+1}).

从时刻 $t$ 开始的折扣回报定义为

G_t=\sum_{k=0}^{\infty}\gamma^k r_{t+k}.

这里采用「转移奖励」约定，即 $r_t$ 是在从 $s_t$ 转移到 $s_{t+1}$ 时获得的奖励。若奖励只依赖于 $(s_t,a_t)$ ，只需令 $r(s,a)=\sum_{s'}P(s'\mid s,a)r(s,a,s')$ ，以下所有结论不变。

定义 1.3（状态值函数与动作值函数） #

在策略 $\pi$ 下，状态值函数与动作值函数分别定义为

\begin{aligned} V^\pi(s)&=\mathbb{E}_\pi\left[G_t\mid s_t=s\right],\\ Q^\pi(s,a)&=\mathbb{E}_\pi\left[G_t\mid s_t=s,a_t=a\right]. \end{aligned}

其中期望同时对策略 $\pi$ 的随机动作与转移核 $P$ 取。

引理 1.4（折扣回报的有界性） #

若 $|r(s,a,s')|\le R_{\max}$ 对一切 $(s,a,s')$ 成立，则对任意轨迹与任意 $t$ ，

|G_t|\le\frac{R_{\max}}{1-\gamma}.

证明由三角不等式与几何级数求和，

\begin{aligned} |G_t| &\le\sum_{k=0}^{\infty}\gamma^k|r_{t+k}|\\ &\le R_{\max}\sum_{k=0}^{\infty}\gamma^k =\frac{R_{\max}}{1-\gamma}. \end{aligned}

因此 $V^\pi$ 与 $Q^\pi$ 均为有界函数。证毕。

有界性并不是一个无关紧要的技术条件。它保证值函数属于一个有界函数空间，而该空间在 sup 范数下是完备的。后文的压缩映射论证正是在这个空间上进行的。

1.3 两个基本恒等式

命题 1.5（值函数的基本恒等式） #

对任意策略 $\pi$ ，有

V^\pi(s)=\sum_{a}\pi(a\mid s)Q^\pi(s,a),

以及

\begin{aligned} Q^\pi(s,a) &=\sum_{s'}P(s'\mid s,a)\\ &\quad\times\left[r(s,a,s')+\gamma V^\pi(s')\right]. \end{aligned}

证明第一式由全期望公式直接得到。对于第二式，利用 $G_t=r_t+\gamma G_{t+1}$ ，有

\begin{aligned} Q^\pi(s,a) &=\mathbb{E}_\pi[r_t\mid s_t=s,a_t=a]\\ &\quad+\gamma\mathbb{E}_\pi[G_{t+1}\mid s_t=s,a_t=a]. \end{aligned}

第一项为 $\sum_{s'}P(s'\mid s,a)r(s,a,s')$ 。第二项先用全期望公式对 $s_{t+1}$ 分解，再利用马尔可夫性与策略的平稳性：

\begin{aligned} \mathbb{E}_\pi[G_{t+1}\mid s_t=s,a_t=a] &=\sum_{s'}P(s'\mid s,a)\\ &\quad\cdot\mathbb{E}_\pi[G_{t+1}\mid s_{t+1}=s']\\ &=\sum_{s'}P(s'\mid s,a)V^\pi(s'). \end{aligned}

代入即得。证毕。

这里的关键是策略的平稳性。若策略依赖于时间，值函数应写成 $V_t^\pi$ ，递归形式仍然成立，但函数会随 $t$ 变化。本文只讨论平稳策略，因此可以省略时间下标。

二、贝尔曼期望方程

2.1 方程的推导

将命题 1.5 的第二式代入第一式，立即得到策略评估的核心方程。

定理 2.1（贝尔曼期望方程） #

对任意平稳策略 $\pi$ ，状态值函数满足

\begin{aligned} V^\pi(s) &=\sum_{a}\pi(a\mid s)\sum_{s'}P(s'\mid s,a)\\ &\quad\times\left[r(s,a,s')+\gamma V^\pi(s')\right], \qquad \forall s\in S. \end{aligned}

证明由命题 1.5，

\begin{aligned} V^\pi(s) &=\sum_{a}\pi(a\mid s)Q^\pi(s,a)\\ &=\sum_{a}\pi(a\mid s)\sum_{s'}P(s'\mid s,a) \left[r(s,a,s')+\gamma V^\pi(s')\right]. \end{aligned}

证毕。

这个方程的意义在于，它把一个涉及无限期回报的期望，转化为一个只涉及当前奖励与下一状态值函数的方程。方程右端仍然含有未知函数 $V^\pi$ ，因此它不是普通的递推式，而是一个泛函方程。

2.2 算子形式

为了把上述方程写成更紧凑的形式，定义贝尔曼期望算子 $\mathcal{T}^\pi$ 为

\begin{aligned} (\mathcal{T}^\pi V)(s) &=\sum_{a}\pi(a\mid s)\sum_{s'}P(s'\mid s,a)\\ &\quad\times\left[r(s,a,s')+\gamma V(s')\right]. \end{aligned}

于是贝尔曼期望方程可以写成不动点形式

V^\pi=\mathcal{T}^\pi V^\pi.

这里的 $V^\pi$ 不是某个数，而是函数空间中的一个点。算子 $\mathcal{T}^\pi$ 把一个有界函数 $V$ 映射为另一个有界函数 $\mathcal{T}^\pi V$ 。因此，求解贝尔曼方程等价于寻找算子 $\mathcal{T}^\pi$ 的不动点。

2.3 有限状态下的矩阵解

当 $S=\{1,\dots,n\}$ 为有限集时，贝尔曼期望方程可以写成线性方程组。定义向量 $V\in\mathbb{R}^n$ 与 $r^\pi\in\mathbb{R}^n$ ，以及矩阵 $P^\pi\in\mathbb{R}^{n\times n}$ ：

\begin{aligned} V_i&=V(i),\\ r^\pi_i&=\sum_{a}\pi(a\mid i)\sum_{j}P(j\mid i,a)r(i,a,j),\\ P^\pi_{ij}&=\sum_{a}\pi(a\mid i)P(j\mid i,a). \end{aligned}

则 $\mathcal{T}^\pi V=r^\pi+\gamma P^\pi V$ ，贝尔曼方程变为

(I-\gamma P^\pi)V^\pi=r^\pi.

命题 2.2（矩阵解与 Neumann 级数） #

设 $0\le\gamma<1$ 。则 $I-\gamma P^\pi$ 可逆，且

V^\pi=(I-\gamma P^\pi)^{-1}r^\pi =\sum_{k=0}^{\infty}\gamma^k(P^\pi)^k r^\pi.

证明记 $Q=\gamma P^\pi$ 。由于 $P^\pi$ 的每一行之和为 $1$ ，有 $\|P^\pi\|_\infty=1$ ，从而 $\|Q^k\|_\infty\le\gamma^k$ 。因此 Neumann 级数 $\sum_{k=0}^{\infty}Q^k$ 在算子范数下绝对收敛。并且

(I-Q)\sum_{k=0}^{n}Q^k=I-Q^{n+1}\longrightarrow I,

故 $I-Q$ 可逆，且

(I-Q)^{-1}=\sum_{k=0}^{\infty}Q^k.

由定理 2.1， $V^\pi$ 满足 $(I-Q)V^\pi=r^\pi$ ，于是

\begin{aligned} V^\pi&=(I-Q)^{-1}r^\pi\\ &=\sum_{k=0}^{\infty}\gamma^k(P^\pi)^k r^\pi. \end{aligned}

证毕。

矩阵解给出了一个重要的结构性事实：在有限状态与固定策略下，贝尔曼方程是一个线性方程组，其系数矩阵为 $I-\gamma P^\pi$ 。折扣因子 $\gamma<1$ 保证该矩阵可逆，因此解存在且唯一。对于一般状态空间，矩阵不再有限，但同样的结论可以由第 3 节的压缩映射论证得到。

2.4 例：两状态马尔可夫链

考虑两个状态 $S=\{1,2\}$ ，只有一个动作。设转移关系为

P(2\mid 1)=1,\qquad P(1\mid 2)=1,

奖励为 $r(1)=1$ ， $r(2)=0$ ，折扣因子 $\gamma=0.9$ 。贝尔曼方程为

V(1)=1+0.9V(2),\qquad V(2)=0+0.9V(1).

将第二式代入第一式，得

V(1)=1+0.81V(1),

因此

V(1)=\frac{1}{1-0.81}=5.2632,\qquad V(2)=0.9V(1)=4.7368.

用矩阵形式验证，转移矩阵与奖励向量为

P=\begin{pmatrix}0&1\\1&0\end{pmatrix}, \qquad r=\begin{pmatrix}1\\0\end{pmatrix}.

于是

(I-0.9P)^{-1} =\frac{1}{1-0.81} \begin{pmatrix}1&0.9\\0.9&1\end{pmatrix},

从而

\begin{aligned} V&=(I-0.9P)^{-1}r\\ &=\frac{1}{0.19}\begin{pmatrix}1\\0.9\end{pmatrix} =\begin{pmatrix}5.2632\\4.7368\end{pmatrix}. \end{aligned}

这个例子说明，即使状态每两步就回到原处，只要 $\gamma^2<1$ ，折扣回报的期望仍然是有限的。值函数不是把无限多项直接相加，而是通过解线性方程组把无限和压缩成一个有限量。

2.5 方程与回报定义的等价性

贝尔曼方程不仅是值函数的必要条件，也是充分条件。下面的命题说明，任何有界解都必然等于由折扣回报定义的值函数。

命题 2.3（策略评估的验证定理） #

设 $V\in B(S)$ 满足 $V=\mathcal{T}^\pi V$ 。则 $V=V^\pi$ 。特别地， $\mathcal{T}^\pi$ 在有界函数空间中至多有一个不动点。

证明设 $V=\mathcal{T}^\pi V$ 。反复代入得

V=\sum_{k=0}^{n-1}\gamma^k(P^\pi)^k r^\pi +\gamma^n(P^\pi)^n V.

由于 $\|(P^\pi)^n V\|_\infty\le\|V\|_\infty$ ，最后一项在 sup 范数下趋于 $0$ 。另一方面，

\sum_{k=0}^{\infty}\gamma^k(P^\pi)^k r^\pi

正是折扣回报的期望，即 $V^\pi$ 。故 $V=V^\pi$ 。证毕。

这个证明不依赖矩阵的有限维结构，只用到 $P^\pi$ 是随机核这一事实。因此它可以直接推广到一般状态空间。命题 2.3 也说明了贝尔曼方程的一个常见误读：它并不是「用未来价值近似当前价值」，而是在精确地刻画值函数。只要 $\gamma<1$ 且奖励有界，满足方程的函数就是值函数本身。

三、贝尔曼算子与压缩映射

3.1 有界函数空间

记 $B(S)$ 为 $S$ 上全体有界实值函数构成的空间，并赋予 sup 范数

\|V\|_\infty=\sup_{s\in S}|V(s)|.

当 $S$ 为有限集时，上确界就是最大值。 $(B(S),\|\cdot\|_\infty)$ 是完备的 Banach 空间。这个完备性是 Banach 不动点定理能够使用的关键。

贝尔曼期望算子 $\mathcal{T}^\pi$ 与贝尔曼最优算子 $\mathcal{T}^*$ 都将 $B(S)$ 映射到自身。 $\mathcal{T}^\pi$ 的定义已在 2.2 节给出， $\mathcal{T}^*$ 定义为

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

以 $\mathcal{T}^\pi$ 为例，

\begin{aligned} |(\mathcal{T}^\pi V)(s)| &\le\sum_{a}\pi(a\mid s)\sum_{s'}P(s'\mid s,a) \left(R_{\max}+\gamma\|V\|_\infty\right)\\ &=R_{\max}+\gamma\|V\|_\infty, \end{aligned}

故 $\|\mathcal{T}^\pi V\|_\infty<\infty$ 。对 $\mathcal{T}^*$ 有同样的界。因此算子迭代不会离开这个空间。

3.2 单调性与常数平移

命题 3.1（单调性与常数平移） #

设 $V,W\in B(S)$ 且 $V\le W$ 逐点成立。则

\mathcal{T}^\pi V\le\mathcal{T}^\pi W, \qquad \mathcal{T}^* V\le\mathcal{T}^* W.

此外，对任意常数 $c\in\mathbb{R}$ ，

\begin{aligned} \mathcal{T}^\pi(V+c\mathbf{1}) &=\mathcal{T}^\pi V+\gamma c\mathbf{1},\\ \mathcal{T}^*(V+c\mathbf{1}) &=\mathcal{T}^* V+\gamma c\mathbf{1}, \end{aligned}

其中 $\mathbf{1}$ 表示恒等于 $1$ 的函数。

证明若 $V\le W$ ，则对每个 $(s,a,s')$ ，

r(s,a,s')+\gamma V(s')\le r(s,a,s')+\gamma W(s').

由于 $\pi(a\mid s)\ge0$ 且 $P(s'\mid s,a)\ge0$ ，加权求和保持不等号，故 $\mathcal{T}^\pi V\le\mathcal{T}^\pi W$ 。对 $\mathcal{T}^*$ ，逐点取最大值也保持逐点序，故 $\mathcal{T}^*V\le\mathcal{T}^*W$ 。

常数平移式由直接计算得到：

\begin{aligned} \mathcal{T}^\pi(V+c\mathbf{1}) &=\sum_{a}\pi(a\mid s)\sum_{s'}P(s'\mid s,a) \left[r(s,a,s')+\gamma V(s')+\gamma c\right]\\ &=\mathcal{T}^\pi V+\gamma c\mathbf{1}. \end{aligned}

对 $\mathcal{T}^*$ ，常数 $\gamma c$ 与动作 $a$ 无关，可以从最大值中提出。证毕。

这两个性质看起来简单，却足以推出压缩性。单调性说明算子保持函数之间的序关系，常数平移式说明算子对整体平移的响应恰好按 $\gamma$ 缩小。二者结合，就得到「两个函数经过算子作用后距离至多变为原来的 $\gamma$ 倍」这一结论。

3.3 压缩映射

定理 3.2（贝尔曼算子的压缩性） #

设 $0\le\gamma<1$ 。则 $\mathcal{T}^\pi$ 与 $\mathcal{T}^*$ 都是 $B(S)$ 上的 $\gamma$ -压缩映射，即对任意 $V_1,V_2\in B(S)$ ，

\|\mathcal{T}V_1-\mathcal{T}V_2\|_\infty \le\gamma\|V_1-V_2\|_\infty.

证明令 $c=\|V_1-V_2\|_\infty$ 。则

V_2-c\mathbf{1}\le V_1\le V_2+c\mathbf{1}.

由命题 3.1 的单调性与常数平移，

\mathcal{T}V_2-\gamma c\mathbf{1} \le\mathcal{T}V_1 \le\mathcal{T}V_2+\gamma c\mathbf{1}.

因此对一切 $s$ ，

\begin{aligned} &\left|(\mathcal{T}V_1)(s)-(\mathcal{T}V_2)(s)\right|\\ &\quad\le\gamma c. \end{aligned}

对 $s$ 取上确界即得结论。证毕。

压缩性的直观含义是：无论两个价值函数相差多大，经过一次贝尔曼更新后，它们的最大差异最多变成原来的 $\gamma$ 倍。若 $\gamma=0.9$ ，初始最大差异为 $100$ ，则一次更新后差异不超过 $90$ ，两次后不超过 $81$ ， $k$ 次后不超过 $0.9^k\cdot100$ 。这正是后文几何收敛性的来源。

需要强调的是，压缩性依赖于 $\gamma<1$ 。当 $\gamma=1$ 时，贝尔曼算子通常只是非扩张的，即只能得到 $\|\mathcal{T}V_1-\mathcal{T}V_2\|_\infty\le\|V_1-V_2\|_\infty$ ，不能保证距离严格缩小。第 5.4 节会给出反例。

3.4 Banach 不动点定理

定理 3.3（Banach 不动点定理） #

设 $(X,d)$ 是完备度量空间， $T:X\to X$ 满足：存在 $\gamma\in[0,1)$ ，使得对任意 $x,y\in X$ ，

d(Tx,Ty)\le\gamma d(x,y).

则 $T$ 在 $X$ 中存在唯一不动点 $x^*$ 。此外，对任意初始点 $x_0\in X$ ，迭代 $x_{k+1}=Tx_k$ 满足

d(x_k,x^*)\le\gamma^k d(x_0,x^*).

证明先证唯一性。若 $x^*$ 与 $y^*$ 都是不动点，则

d(x^*,y^*)=d(Tx^*,Ty^*)\le\gamma d(x^*,y^*).

由于 $\gamma<1$ ，必有 $d(x^*,y^*)=0$ ，即 $x^*=y^*$ 。

再证存在性。任取 $x_0\in X$ ，令 $x_{k+1}=Tx_k$ 。对 $m>n$ ，由三角不等式与压缩性，

\begin{aligned} d(x_n,x_m) &\le\sum_{k=n}^{m-1}d(x_k,x_{k+1})\\ &\le\sum_{k=n}^{m-1}\gamma^k d(x_0,x_1) \le\frac{\gamma^n}{1-\gamma}d(x_0,x_1). \end{aligned}

因此 $\{x_n\}$ 是 Cauchy 列。由 $X$ 完备，存在 $x^*\in X$ 使得 $x_n\to x^*$ 。算子 $T$ 是 Lipschitz 连续的，故

\begin{aligned} Tx^*&=T\left(\lim_{n\to\infty}x_n\right) =\lim_{n\to\infty}Tx_n\\ &=\lim_{n\to\infty}x_{n+1}=x^*. \end{aligned}

最后，由压缩性直接得到

d(x_k,x^*)=d(T^kx_0,T^kx^*)\le\gamma^k d(x_0,x^*).

证毕。

3.5 唯一性与上下界

推论 3.4（不动点的存在唯一性） #

设 $0\le\gamma<1$ 。则 $\mathcal{T}^\pi$ 与 $\mathcal{T}^*$ 在 $B(S)$ 中各自存在唯一不动点。

证明 $B(S)$ 在 sup 范数下完备， $\mathcal{T}^\pi$ 与 $\mathcal{T}^*$ 都是 $\gamma$ -压缩映射。由定理 3.3 即得。证毕。

对 $\mathcal{T}^\pi$ ，命题 2.3 已经指出这个唯一不动点就是 $V^\pi$ 。对 $\mathcal{T}^*$ ，第 4 节将证明它的唯一不动点就是最优值函数 $V^*$ 。因此，「贝尔曼方程有唯一解」并不是一个额外的假设，而是压缩性的直接推论。

单调性还给出了一个在理论上很有用的上下界判据。

推论 3.5（上下界判据） #

设 $\mathcal{T}$ 为 $\mathcal{T}^\pi$ 或 $\mathcal{T}^*$ ，其唯一不动点为 $V_\infty$ 。若 $V_{\mathrm{low}}\le\mathcal{T}V_{\mathrm{low}}$ ，则 $V_{\mathrm{low}}\le V_\infty$ 。若 $V_{\mathrm{up}}\ge\mathcal{T}V_{\mathrm{up}}$ ，则 $V_{\mathrm{up}}\ge V_\infty$ 。

证明若 $V_{\mathrm{low}}\le\mathcal{T}V_{\mathrm{low}}$ ，由单调性反复作用得

V_{\mathrm{low}}\le\mathcal{T}V_{\mathrm{low}} \le\mathcal{T}^2V_{\mathrm{low}}\le\cdots.

而 $\mathcal{T}^nV_{\mathrm{low}}\to V_\infty$ ，故 $V_{\mathrm{low}}\le V_\infty$ 。上界情形同理，只是迭代序列单调下降。证毕。

这个判据说明，只要能够构造一个满足 $V\le\mathcal{T}V$ 的下界函数，它就一直位于真实值函数之下。满足 $V\ge\mathcal{T}V$ 的上界函数则一直位于真实值函数之上。这为值函数的区间估计提供了严格的数学基础。

四、贝尔曼最优方程

4.1 最优值函数

定义 4.1（最优值函数） #

最优状态值函数与最优动作值函数分别定义为

V^*(s)=\sup_{\pi}V^\pi(s), \qquad Q^*(s,a)=\sup_{\pi}Q^\pi(s,a).

若策略 $\pi^*$ 满足 $V^{\pi^*}=V^*$ ，则称 $\pi^*$ 为最优策略。

在有限状态与有限动作的折扣 MDP 中，上确界实际上可以取到，而且存在一个平稳确定性最优策略。这一点将由定理 4.2 的证明一并给出。因此，本节的 $\sup$ 可以理解为 $\max$ 。本文的 $\pi$ 均指平稳策略。对于折扣有限 MDP，平稳策略类已经包含最优策略，因此这一限制不失一般性。

4.2 最优方程的证明

第 3.1 节已经定义了贝尔曼最优算子 $\mathcal{T}^*$ ：

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

与 $\mathcal{T}^\pi$ 不同， $\mathcal{T}^*$ 先对每个动作计算期望，再在动作上取最大值。这个顺序不能交换，原因见 4.3 节。

定理 4.2（贝尔曼最优方程） #

设 $\gamma\in[0,1)$ ， $S$ 与 $A$ 有限。则 $V^*$ 是 $B(S)$ 中满足

\begin{aligned} V(s)&=\max_{a}\sum_{s'}P(s'\mid s,a)\\ &\quad\times\left[r(s,a,s')+\gamma V(s')\right], \qquad \forall s\in S \end{aligned}

的唯一有界解。此外，确定性策略 $\pi^*$ 最优当且仅当对每个 $s$ ，

\pi^*(s)\in\arg\max_{a}\sum_{s'}P(s'\mid s,a) \left[r(s,a,s')+\gamma V^*(s')\right].

证明由推论 3.4， $\mathcal{T}^*$ 在 $B(S)$ 中存在唯一不动点，记作 $\bar V$ 。下面证明 $\bar V=V^*$ 。

先证 $V^*\le\bar V$ 。对任意策略 $\pi$ ，由于 $\mathcal{T}^\pi$ 是各动作值的加权平均，而 $\mathcal{T}^*$ 在动作上取最大值，故逐点有

\mathcal{T}^\pi\bar V\le\mathcal{T}^*\bar V=\bar V.

由单调性，对一切 $n$ 有 $(\mathcal{T}^\pi)^n\bar V\le\bar V$ 。令 $n\to\infty$ ，由 $\mathcal{T}^\pi$ 的压缩性与命题 2.3， $(\mathcal{T}^\pi)^n\bar V\to V^\pi$ ，故 $V^\pi\le\bar V$ 。对 $\pi$ 取上确界得 $V^*\le\bar V$ 。

再证 $\bar V\le V^*$ 。令 $\pi_g$ 为关于 $\bar V$ 的贪婪策略，即对每个 $s$ ，

\pi_g(s)\in\arg\max_{a}\sum_{s'}P(s'\mid s,a) \left[r(s,a,s')+\gamma\bar V(s')\right].

则 $\mathcal{T}^{\pi_g}\bar V=\mathcal{T}^*\bar V=\bar V$ 。由命题 2.3， $\bar V=V^{\pi_g}$ ，故 $\bar V\le V^*$ 。结合两个不等式得 $\bar V=V^*$ 。

最后证明策略的最优性判据。若确定性策略 $\pi$ 在每个状态都取到最大值，则 $\mathcal{T}^\pi V^*=\mathcal{T}^*V^*=V^*$ ，由命题 2.3 得 $V^\pi=V^*$ 。反之，若 $V^\pi=V^*$ ，则

\begin{aligned} \mathcal{T}^\pi V^* &=\mathcal{T}^\pi V^\pi=V^\pi\\ &=V^*=\mathcal{T}^*V^*. \end{aligned}

由于 $\mathcal{T}^\pi V^*(s)$ 是各动作值的加权平均，而 $\mathcal{T}^*V^*(s)$ 是这些动作值的最大值，等号成立当且仅当 $\pi$ 在该状态以概率 $1$ 选择取得最大值的动作。对确定性策略，这正是 $\pi(s)\in\arg\max_a\cdots$ 。证毕。

这个证明的结构值得注意。它没有直接对无穷期问题做「先选动作再假设后续最优」的循环论证，而是把最优性分解为两个方向。一方面，任何策略都不如 $\mathcal{T}^*$ 的不动点。另一方面，关于该不动点的贪婪策略恰好达到它。两个方向合起来，既证明了最优方程，也证明了最优策略的存在性。

由定理 4.2 与 $Q^*$ 的定义，还可以得到最优动作值函数的表达式。若在状态 $s$ 先固定动作 $a$ ，此后采用最优策略，则

\begin{aligned} Q^*(s,a)&=\sum_{s'}P(s'\mid s,a) \left[r(s,a,s')+\gamma V^*(s')\right],\\ V^*(s)&=\max_{a}Q^*(s,a). \end{aligned}

第一式的上界由 $V^\pi\le V^*$ 得到，下界由在后续状态选取最优续策略达到。第二式说明，最优动作正是使 $Q^*(s,a)$ 最大的动作。因此， $Q^*$ 与 $V^*$ 的差别只在于第一步是否已经固定动作。

4.3 max 与期望不可交换

最优贝尔曼方程中是 $\max_a\mathbb{E}$ ，而不是 $\mathbb{E}\max_a$ 。这两个量一般不相等，原因在于动作必须在观察到下一状态之前选定。

考虑一个状态 $s$ ，两个动作 $a_1,a_2$ 。下一状态以 $1/2$ 的概率为 $s_1$ ，以 $1/2$ 的概率为 $s_2$ ，并设未来价值为零。奖励为

r(s,a_1,s_1)=1,\quad r(s,a_1,s_2)=0, \qquad r(s,a_2,s_1)=0,\quad r(s,a_2,s_2)=1.

则

\begin{aligned} \max_{a}\mathbb{E}[r\mid s,a]&=\frac12,\\ \mathbb{E}\left[\max_{a}r(s,a,s')\mid s\right]&=1. \end{aligned}

后者相当于在观察到 $s'$ 之后才选动作，因此获得了更大的灵活性，但它不是原问题的可行决策顺序。贝尔曼最优方程采用前者，是对决策时序的正确编码。

4.4 验证定理与最优策略

推论 4.3（最优性的验证定理） #

设 $V\in B(S)$ 满足 $V=\mathcal{T}^*V$ 。则 $V=V^*$ 。若策略 $\pi$ 关于 $V$ 贪婪，即

\pi(s)\in\arg\max_{a}\sum_{s'}P(s'\mid s,a) \left[r(s,a,s')+\gamma V(s')\right],

则 $V^\pi=V$ ，从而 $\pi$ 是最优策略。

证明第一式由 $\mathcal{T}^*$ 的不动点唯一性立即得到。若 $\pi$ 关于 $V$ 贪婪，则 $\mathcal{T}^\pi V=\mathcal{T}^*V=V$ 。由命题 2.3， $V^\pi=V$ 。证毕。

这个推论是贝尔曼方程「充分性」的精确表述。它说明，只要能够找到一个有界函数满足最优方程，就不需要再与其他策略比较，因为它必然等于最优值函数。反过来，最优值函数也必然满足该方程。因此，在折扣有界 MDP 中，贝尔曼最优方程既必要又充分。

4.5 例：带决策的路径

考虑如下路径选择问题。状态为 $A,B,C,D,E$ ，其中 $C$ 为终止状态。转移关系为

\begin{aligned} &A\to B,\quad B\to C,\quad A\to D,\\ &D\to E,\quad E\to C. \end{aligned}

每次转移获得奖励 $-1$ ，进入终止状态 $C$ 时额外获得奖励 $10$ 。设 $\gamma=0.9$ ，并令 $V(C)=0$ 。

在 $B$ 与 $E$ ，只有一条通往 $C$ 的动作，因此

V(B)=-1+10+0.9V(C)=9, \qquad V(E)=9.

在 $D$ ，唯一动作通向 $E$ ，故

V(D)=-1+0.9V(E)=-1+0.9\times9=7.1.

在 $A$ ，有两条动作。记 $Q(A\to B)$ 与 $Q(A\to D)$ 分别为在 $A$ 选择这两条动作的动作值，则

Q(A\to B)=-1+0.9V(B)=-1+0.9\times9=7.1,

Q(A\to D)=-1+0.9V(D)=-1+0.9\times7.1=5.39.

因此

V(A)=\max\{7.1,5.39\}=7.1,

最优动作是走向 $B$ 。路线 $A\to B\to C$ 虽然与 $A\to D\to E\to C$ 具有相同的终止奖励，但后者多走一步，多承担一次 $-1$ 的即时奖励，并通过折扣因子进一步缩小了终止奖励的现值，因此其价值更低。

这个例子同时展示了最优子结构的两层含义。第一，从 $A$ 出发的最优路线选择了 $B$ ，而从 $B$ 出发的剩余路线 $B\to C$ 本身是 $B$ 处子问题的最优解。第二，从 $D$ 出发的剩余路线 $D\to E\to C$ 也是 $D$ 处子问题的最优解。整体最优并不是把各段的局部最优任意拼接，而是沿着实际到达的后继状态，取该后继状态的最优续策略。

若改用 $V(C)=10$ 的约定，即把终止奖励直接记在终止状态上，而不是记在进入终止状态的转移上，则上述数值会改变，但最优动作不变。两种约定的差别只在于奖励被记在转移上还是被记在状态上，贝尔曼方程的形式必须与所采用的约定保持一致。

五、收敛性与误差界

5.1 不动点迭代

压缩映射不仅证明了解的存在唯一性，还给出了构造解的方法。任取初始函数 $V_0\in B(S)$ ，定义迭代

V_{k+1}=\mathcal{T}V_k, \qquad k=0,1,2,\dots

其中 $\mathcal{T}$ 可以是 $\mathcal{T}^\pi$ 或 $\mathcal{T}^*$ 。在强化学习中，这一迭代称为值迭代。由 Banach 不动点定理，迭代序列必然收敛到相应的不动点。

定理 5.1（几何收敛） #

设 $0\le\gamma<1$ ， $\mathcal{T}$ 为 $\mathcal{T}^\pi$ 或 $\mathcal{T}^*$ ，其唯一不动点为 $V_\infty$ 。则对任意 $V_0\in B(S)$ ，

\|V_k-V_\infty\|_\infty \le\gamma^k\|V_0-V_\infty\|_\infty.

特别地， $V_k\to V_\infty$ 在 sup 范数下成立。

证明由压缩性，

\begin{aligned} \|V_{k+1}-V_\infty\|_\infty &=\|\mathcal{T}V_k-\mathcal{T}V_\infty\|_\infty\\ &\le\gamma\|V_k-V_\infty\|_\infty. \end{aligned}

对 $k$ 反复迭代即得。证毕。

这个定理说明，初始估计 $V_0$ 不需要很准确。无论从哪个有界函数出发，误差都会按 $\gamma^k$ 的速度衰减。 $\gamma$ 越接近 $1$ ，衰减越慢，所需的迭代次数越多。这也是折扣因子在数值上既影响问题定义、又影响求解难度的体现。

5.2 误差上界

定理 5.1 给出的误差界含有未知的 $V_\infty$ ，在实际计算中不能直接使用。下面的命题给出只依赖迭代差分与初始差分的界。

命题 5.2（先验与后验误差界） #

设 $\mathcal{T}$ 为 $\gamma$ -压缩映射， $V_{k+1}=\mathcal{T}V_k$ ， $V_\infty$ 为不动点。则对任意 $k\ge1$ ，

\|V_k-V_\infty\|_\infty \le\frac{\gamma^k}{1-\gamma}\|V_1-V_0\|_\infty,

以及

\|V_k-V_\infty\|_\infty \le\frac{\gamma}{1-\gamma}\|V_k-V_{k-1}\|_\infty.

证明先证第一式。由三角不等式与压缩性，

\begin{aligned} \|V_k-V_\infty\|_\infty &\le\sum_{j=k}^{\infty}\|V_{j+1}-V_j\|_\infty\\ &\le\sum_{j=k}^{\infty}\gamma^j\|V_1-V_0\|_\infty =\frac{\gamma^k}{1-\gamma}\|V_1-V_0\|_\infty. \end{aligned}

再证第二式。由压缩性，

\|V_k-V_\infty\|_\infty \le\gamma\|V_{k-1}-V_\infty\|_\infty.

再由三角不等式，

\|V_{k-1}-V_\infty\|_\infty \le\|V_{k-1}-V_k\|_\infty+\|V_k-V_\infty\|_\infty.

合并两式得

\|V_k-V_\infty\|_\infty \le\gamma\|V_{k-1}-V_k\|_\infty +\gamma\|V_k-V_\infty\|_\infty.

移项得

(1-\gamma)\|V_k-V_\infty\|_\infty \le\gamma\|V_{k-1}-V_k\|_\infty,

即第二式。证毕。

第一式称为先验界，因为它在迭代之前就可以用来估计所需步数。第二式称为后验界，因为它使用当前迭代的实际差分，可以在计算过程中判断是否已经足够接近不动点。由第二式，当 $\gamma>0$ 时，若

\begin{aligned} &\|V_k-V_{k-1}\|_\infty\\ &\quad\le\frac{\varepsilon(1-\gamma)}{\gamma}, \end{aligned}

则必有 $\|V_k-V_\infty\|_\infty\le\varepsilon$ 。

5.3 例：显式迭代

回到 2.4 节的两状态马尔可夫链。令 $V_0=(0,0)$ ，迭代为

V_{k+1}(1)=1+0.9V_k(2), \qquad V_{k+1}(2)=0.9V_k(1).

前几步为

\begin{aligned} V_1&=(1,0),\\ V_2&=(1,0.9),\\ V_3&=(1.81,0.9),\\ V_4&=(1.81,1.629),\\ V_5&=(2.4661,1.629). \end{aligned}

可以看到，奇数步与偶数步分别单调地逼近极限。事实上，对 $m\ge0$ ，

V_{2m+1}(1)=\sum_{j=0}^{m}0.9^{2j}, \qquad V_{2m+1}(2)=\sum_{j=0}^{m-1}0.9^{2j+1}.

令 $m\to\infty$ ，得到

V(1)=\frac{1}{1-0.9^2}=5.2632, \qquad V(2)=\frac{0.9}{1-0.9^2}=4.7368.

这个例子的结构值得注意。若只看奇数步或偶数步的子序列，误差按 $0.9^2=0.81$ 的比例衰减，因为状态每两步回到自身。但逐步的 sup 范数误差仍然按 $0.9$ 衰减，只是最大误差所在的分量在两步之间交替。一般理论给出的是逐步最坏情形下的统一上界，具体问题的子序列可能具有更快的收敛速度。

由定理 5.1，初始误差为 $\|V_0-V_\infty\|_\infty=5.2632$ ，故

\|V_k-V_\infty\|_\infty\le5.2632\times0.9^k.

当 $k=20$ 时，右端约为 $0.64$ 。当 $k=50$ 时，右端约为 $0.027$ 。这与几何收敛的预期一致。

5.4 折扣因子的必要性

压缩性依赖 $\gamma<1$ 。若 $\gamma=1$ ，贝尔曼算子一般不再是压缩映射，贝尔曼方程可能没有有限解，也可能有多个解。以下两个例子说明这两种失效方式。

第一个例子是零奖励的确定性循环。设两个状态 $1,2$ ，转移为 $1\to2\to1$ ，奖励恒为零， $\gamma=1$ 。贝尔曼方程为

V(1)=V(2),\qquad V(2)=V(1).

任意常数函数 $V(1)=V(2)=c$ 都是解，因此不动点不唯一。Banach 定理的唯一性结论失效。

第二个例子是每步奖励为 $1$ 的同一循环。此时

G_t=\sum_{k=0}^{\infty}1=\infty,

折扣回报不再是有限实数，值函数不属于 $B(S)$ 。对应的贝尔曼方程为

V(1)=1+V(2),\qquad V(2)=1+V(1),

它也没有有限解。这说明 $\gamma<1$ 不是技术上的方便假设，而是保证回报有界、算子压缩、解唯一的结构性条件。

六、最优子结构与最优性原理

6.1 有限期情形

最优子结构最清晰的表述出现在有限期问题中。设时间范围为 $0,1,\dots,T$ ，策略为一个序列 $\pi=(\pi_0,\dots,\pi_{T-1})$ ，其中 $\pi_t$ 是时刻 $t$ 的策略。定义

\begin{aligned} V_t^\pi(s) &=\mathbb{E}_\pi\Bigg[\sum_{k=t}^{T-1}\gamma^{k-t}r_k\\ &\qquad\mid s_t=s\Bigg],\\ V_T^\pi(s)&=0. \end{aligned}

类似地，令 $V_t^*(s)=\sup_\pi V_t^\pi(s)$ 。

定理 6.1（有限期最优性原理） #

对 $t=T-1,T-2,\dots,0$ ，有

V_t^\pi=\mathcal{T}^{\pi_t} V_{t+1}^\pi, \qquad V_t^*=\mathcal{T}^* V_{t+1}^*.

证明对 $t$ 从 $T-1$ 到 $0$ 反向归纳。 $t=T$ 时两端均为零。设结论对 $t+1$ 成立。对任意策略 $\pi$ ，在 $s_t=s$ 处分解回报：

\begin{aligned} V_t^\pi(s) &=\mathbb{E}_\pi\Big[r_t+\gamma V_{t+1}^\pi(s_{t+1})\\ &\qquad\mid s_t=s\Big]. \end{aligned}

由 $V_{t+1}^*$ 的定义， $V_{t+1}^\pi\le V_{t+1}^*$ ，故

\begin{aligned} V_t^\pi(s) &\le\sum_{a}\pi_t(a\mid s)\sum_{s'}P(s'\mid s,a) \left[r(s,a,s')+\gamma V_{t+1}^*(s')\right]\\ &\le\max_{a}\sum_{s'}P(s'\mid s,a) \left[r(s,a,s')+\gamma V_{t+1}^*(s')\right]. \end{aligned}

另一方面，由归纳假设， $V_{t+1}^*$ 是 $t+1$ 时刻可达的最优值。取 $a_t$ 为使上式右端最大的动作，并从 $t+1$ 开始采用达到 $V_{t+1}^*$ 的最优续策略，则等号可以达到。在有限状态与有限动作下，可以逐状态选取最优续策略，因此不需要额外的可测选择条件。故 $V_t^*=\mathcal{T}^*V_{t+1}^*$ 。策略评估式同理。证毕。

这个定理就是反向归纳的数学形式。它说明，在时刻 $t$ ，最优决策只需要知道当前状态与下一时刻的最优值函数 $V_{t+1}^*$ 。一旦后继状态 $s_{t+1}$ 确定，从 $s_{t+1}$ 开始的剩余决策必须构成该子问题的最优策略。否则，替换该续策略就可以严格改进原策略，与整体最优性矛盾。这就是贝尔曼最优性原理在最简单情形下的完整证明。

6.2 无限期情形

无限期问题不能直接使用反向归纳，因为不存在一个最后的时刻。但第 4 节的压缩映射论证给出了同样的结论。定理 4.2 表明，无限期最优贝尔曼方程就是 $\mathcal{T}^*$ 的不动点方程，而最优值函数正是该方程的唯一有界解。

因此，最优子结构在无限期情形下不是一条需要额外假设的公理，而是折扣、马尔可夫性与可加效用三者共同作用的结果。折扣保证了算子的压缩性，马尔可夫性保证后继状态足以概括历史，可加效用保证了回报可以分解为 $G_t=r_t+\gamma G_{t+1}$ 。缺少其中任何一个条件，贝尔曼方程的标准形式都可能失效。

6.3 成立条件

最优子结构的成立依赖以下三个条件。

第一，效用必须是可加且按常数折扣的。也就是说，回报必须能够写成 $\sum_{k=0}^{\infty}\gamma^k r_{t+k}$ 。这个形式保证了 $G_t=r_t+\gamma G_{t+1}$ 。若效用是历史整体的非线性函数，例如某些非可加偏好，那么未来就不能被压缩成一个标量值函数。双曲折扣是一个典型例子。在双曲折扣下，今天的偏好与明天的偏好可能不一致，因而不存在一个与时间无关的递归值函数。

第二，状态必须满足马尔可夫性。若未来的转移依赖于更早的历史，当前状态 $s_t$ 就不是充分的统计量。此时可以把状态扩充为包含必要历史信息的新状态，例如部分可观测问题中的信念状态。在扩充后的状态空间上，贝尔曼方程仍然可以保持相同的形式。

第三，回报必须有界，或者折扣必须足够强。有限期问题即使 $\gamma=1$ 也可以有有界回报，因为求和的项数是有限的。无限期问题则需要 $\gamma<1$ ，或者采用平均奖励、吸收态等替代准则。否则，值函数可能发散，或者贝尔曼方程的解不唯一。

这三个条件共同说明，最优子结构是一个有明确适用范围的定理，而不是一条无条件成立的哲学原则。

七、边界与常见误区

7.1 连续状态空间

在标准的可测性假设下，连续状态空间中的 $B(S)$ 仍然是 Banach 空间，压缩映射的论证也仍然成立。因此，贝尔曼期望方程的唯一有界解依然存在，贝尔曼最优算子也依然有唯一有界不动点，值迭代的几何收敛性同样成立。在适当的可测选择条件下，该不动点等于最优值函数。

变化主要发生在 $\mathcal{T}^*$ 的定义上。此时最大值未必取到，应将其写成

\begin{aligned} (\mathcal{T}^*V)(s) &=\sup_{a}\Bigg\{\int_S \Big[r(s,a,s')\\ &\qquad+\gamma V(s')\Big]P(\mathrm{d}s'\mid s,a)\Bigg\}. \end{aligned}

压缩性证明中的「最大值保持逐点序」可以替换为「上确界保持逐点序」，因此 $\mathcal{T}^*$ 仍然是 $\gamma$ -压缩映射。唯一不动点仍然存在。

但是，最优策略的存在性需要额外条件。即使 $\mathcal{T}^*$ 有唯一不动点，也不一定存在一个可测的映射 $s\mapsto\pi^*(s)$ 在每个状态都取到上确界。通常需要动作集紧、奖励与转移核连续，或者使用可测选择定理。本文的有限状态与有限动作假设避开了这些技术问题。这也是为什么在一般情形下，贝尔曼最优方程常写成上确界形式，而不是最大值形式。

7.2 平均奖励与无折扣

当 $\gamma=1$ 且时间范围为无限时，折扣回报可能发散，贝尔曼方程的标准形式不再适用。此时常用的替代准则是平均奖励准则。它引入增益 $\rho$ 与偏差函数 $h$ ，其最优方程形如

\begin{aligned} \rho+h(s)&=\max_{a}\Bigg\{\bar r(s,a)\\ &\qquad+\sum_{s'}P(s'\mid s,a)h(s')\Bigg\}, \end{aligned}

其中 $\bar r(s,a)=\sum_{s'}P(s'\mid s,a)r(s,a,s')$ 是期望即时奖励。这个方程与折扣贝尔曼方程在结构上相似，但数学性质不同。平均奖励问题通常只保证偏差函数在相差一个常数的意义下唯一，因为若 $h$ 是解，则 $h+c$ 也是解。折扣因子 $\gamma<1$ 消除了这种平移自由度，因此折扣情形的不动点是真正唯一的。

有限期问题是一个例外。即使 $\gamma=1$ ，只要时间范围有限，回报就是有限项之和，值函数仍然有界，反向归纳仍然成立。因此， $\gamma<1$ 的必要性主要针对无限期问题。

7.3 注意要点

把贝尔曼方程写成没有期望的形式。 在确定性转移的情形下， $V(s)=r(s,a)+\gamma V(s')$ 可以成立。但在随机转移下，必须对下一状态取期望。遗漏期望会把随机问题误写成确定性问题。

把最大值放进期望内部。 最优方程是 $\max_a\mathbb{E}$ ，不是 $\mathbb{E}\max_a$ 。4.3 节的例子说明，二者一般相差很大。动作必须在观察到下一状态之前选定，这个时序约束正是最大值位于期望之外的原因。

混淆 $V$ 与 $Q$ 。 $V^\pi(s)$ 已经对策略的动作分布取了平均，因此它不再区分同一状态下的不同动作。要选择动作，应使用 $Q^*(s,a)$ ，最优动作是 $\arg\max_a Q^*(s,a)$ 。把 $\arg\max_a V(s)$ 当作最优动作是没有意义的，因为 $V(s)$ 中已经没有动作变量。

混淆必要性、充分性与唯一性。 在折扣有界 MDP 中，贝尔曼方程既必要又充分，而且解唯一。但在 $\gamma=1$ 、奖励无界或状态空间不满足可测选择条件时，这些结论可能分别失效。讨论贝尔曼方程时，应明确所依赖的假设。

认为最优策略唯一。 最优值函数是唯一的，但最优策略不一定唯一。例如只有一个状态、两个动作，两个动作都使状态保持不变且都获得奖励 $1$ 。此时

V^*=\frac{1}{1-\gamma},

两个动作在每个状态都达到最大值，因此都是最优的。唯一性属于值函数，而不属于策略。

总结

贝尔曼方程的核心可以概括为三步。第一步，利用折扣回报的递归分解 $G_t=r_t+\gamma G_{t+1}$ 与马尔可夫性，把值函数写成当前奖励与后继值函数的期望。第二步，把该递归式视为有界函数空间上的算子方程 $V=\mathcal{T}V$ 。第三步，利用算子的单调性、常数平移性与压缩性，证明不动点存在唯一，并由 Banach 不动点定理得到几何收敛。

贝尔曼期望方程刻画固定策略的值函数，其有限状态形式是一个线性方程组，系数矩阵为 $I-\gamma P^\pi$ 。贝尔曼最优方程刻画最优值函数，其算子在动作上取最大值。两者的共同点是都把无限期问题转化为一个不动点问题。区别在于前者对策略取期望，因而在有限状态下是线性方程。后者对动作取最大值，因而含有非线性项。

最优子结构是这一整套理论的解释性核心。它说明，在可加折扣效用、马尔可夫转移与有界回报的条件下，整体最优决策可以沿着实际到达的后继状态分解为一系列子问题的最优决策。它不是一个无条件的哲学原则，而是一个由回报结构、状态表示与折扣条件共同保证的数学定理。