贝尔曼最优性原理

贝尔曼最优性原理（Bellman principle of optimality）指出：在状态完整地概括后续决策所需信息、目标可按阶段分解的条件下，一条最优策略从任意已到达状态继续执行的部分，也应当是该状态下相应剩余问题的最优策略。它是动态规划的依据，核心在于“后续问题是同一个问题的剩余部分”。

一条最短路线的后半段

考虑有向无环路线：$S\to A$ 成本二，$S\to B$ 成本五，$A\to B$ 成本一，$A\to G$ 成本五，$B\to G$ 成本一。到达终点 $G$ 的剩余代价为零。反向计算：$V(B)=1$，$V(A)=min(5,1+1)=2$，$V(S)=min(2+2,5+1)=4$。最优路线为 $S,A,B,G$。

在A比较直达G的五与经B的二，再把A的最优剩余代价带回S。箭头旁数字是边成本。

假如这条最优路线从 $A$ 开始的部分不是最优，就存在更便宜的 $A\to G$ 路线。保留前段 $S\to A$，只替换后段，就得到总成本更低的完整路线，与原路线最优矛盾。这种拼接论证就是原理的基本证明；前提是替换后段仍然满足原问题所有限制。

有限时域的递推与归纳证明

设时刻 $k=0,\dots ,N-1$，状态按 $x_{k+1}=f_k(x_k,u_k)$ 更新，允许输入为 $u_k\in U_k(x_k)$。总代价为 $\sum _{k=0}^{N-1}{\ell }_k(x_k,u_k)+g(x_N)$，则 $$V_N(x)=g(x),V_k(x)=\underset{u\in U_k(x)}{inf}\{{\ell }_k(x,u)+V_{k+1}(f_k(x,u))\}.$$ 证明可向后归纳：终点等式来自定义；假定 $V_{k+1}$ 已给出所有剩余策略的最小代价，固定第一输入后，任何后续方案的成本都不小于它，因此完整成本不小于右边下确界。反过来，选择接近这个下确界的第一输入和接近后续下确界的策略，可任意逼近右边，得到反向不等式。若各步最小值实际达到，就可取达到者组成最优策略。

随机模型中，把下一步值函数改成给定当前状态和输入的条件期望。后续策略必须遵守相同的信息约束，不能在拼接时偷偷使用尚未观察到的随机结果。

状态不完整时的失败

若途中至多使用一次收费减免券，只用“当前位置”作状态就不完整：到达同一个节点时，有券和无券的后续成本不同。应把状态扩充为 $(\text{位置},\text{券是否仍可用})$，才能正确比较后半段。类似地，剩余预算、已使用资源或累计约束，都可能需要进入状态。

变式。 将 $A\to B$ 的成本从一改为六，保持其他边不变。此时 $V(A)=min(5,6+1)=5$，$V(S)=min(2+5,5+1)=6$，最优路线变为 $S,B,G$。最优前一步会随后续成本变化，不能把每条边的局部最小选择当作动态规划。

该原理导出策略迭代、值迭代和哈密顿－雅可比－贝尔曼方程，但不是这些算法在任意条件下都收敛的保证；时域、折扣、可行性和信息结构需要分别说明。