贝尔曼方程

想了解贝尔曼方程，要先了解许多相关概念。首先，任何最佳化问题都有目标：旅行时间最小化、成本最小化、利润最大化、效用最大化等。用来描述目标的数学函数就称为目标函数。

动态规划将多期规划问题转为不同时间点上较简单的步骤，因此，它需要追踪决策背景情况随时间的变化。作正确决策所需要当前情况的资讯被称作是“状态（State）”（贝尔曼，1957，Ch. III.2）。^[1][2]例如，为了决定每个时间要花多少钱，人们必须要知道他们初始财富的量，此例中财富就是一种“状态变数（State Variables）”，或简称“状态（State）”，当然也可能还有其他的种类。

从任意时点上所挑选以操作的变数通常称为“控制变数”（Control Variables），或简称“控制”（Control）（控制理论中描述输入的变数）。例如给定现在所具有的财富（状态），人们便可以用以决定当下的消费（控制变数）。挑选当下的控制变数可被视为挑选下个状态，广义而言，下个状态受到当下控制变数及其他因子的影响。举个简单的例子：今天的财富（状态）及消费（控制变数）会决定明天的财富（新的状态），虽然通常也还有其他的因素可以影响明天的财富（例如获得意外之财）。

动态规划方法中利用“找寻某种规则来求得各可能状态下的（最佳）控制为何”来达成目标函数最佳化。例如：假设消费（c）只与财富（W）相关，想要找到一套规则${\displaystyle c(W)}$ 来以财富描述消费。这些“将控制（Controls）表示成状态（States）的函数”的规则被称为策略函数（Policy Function）。^[1]

从定义可知，最佳化目标函数的策略乃是所有可能的策略函数中，其对应到目标函数值最佳者。沿用上述的例子，若某人利用给定的财富来消费以最大化快乐的感觉（这里假定“快乐的感觉”可以被数学函数描述，像是效用函数等），那么各种初始的财富便会对应到一个可能的最大快乐，表示成${\displaystyle H(W)}$ 。这个最大的可能目标函数值（快乐的感觉），即是价值函数（Value Function）。

动态决策问题

令 ${\displaystyle t}$  时刻的状态为 ${\displaystyle x_{t}}$ 。对于一个从时刻 0 开始的决策，令${\displaystyle x_{0}}$ 为初始状态。在任意时刻，可能的行动集合都取决于当前状态。可以将其写作 ${\displaystyle a_{t}\in \Gamma (x_{t})}$ ，其中，${\displaystyle a_{t}}$ 代表了一个或者多个控制变量。还可以假定，当采取行动 ${\displaystyle a}$ 时，状态由${\displaystyle x}$ 变为新状态 ${\displaystyle T(x,a)}$ ，当前收益为${\displaystyle F(x,a)}$ 。最后假设一个由 ${\displaystyle 0<\beta <1}$ 表示的impatience。

在这些假设下，一个无限范围决策问题有以下形式：

${\displaystyle V(x_{0})\;=\;\max _{\left\{a_{t}\right\}_{t=0}^{\infty }}\sum _{t=0}^{\infty }\beta ^{t}F(x_{t},a_{t}),}$ 

服从以下约束：

${\displaystyle a_{t}\in \Gamma (x_{t}),\;x_{t+1}=T(x_{t},a_{t}),\;\forall t=0,1,2,\dots }$ 

注意已经使用了 ${\displaystyle V(x_{0})}$  来表示可以通过最大化符合约束假设的目标函数得到的最优值。这个函数就是 价值函数。由于最优值取决于初始状态，因此，它是初始状态变量 ${\displaystyle x_{0}}$ 的函数。

贝尔曼最优化原理

动态规划方法将决策问题分解为更小的子问题。贝尔曼最优化原理描述了如何做到这点：

最优化原理：最优化策略有这样的性质，即无论初始状态和初始决策是什么，余下的决策必定构成一个与由初始决策导致的状态有关的最优化策略。 (See Bellman, 1957, Chap. III.3.)

在计算机科学领域，一个可以如此分解的问题称作有最优子结构（英语：Optimal substructure）。在博弈论中，这个原理与subgame perfect equilibrium（英语：subgame perfect equilibrium）的概念类似，尽管在这种情况下，构成最优策略的条件取决于决策者的对手从他们的立场选择类似的最优策略。

正如最优化原理所说，会单独考虑初始决策，将所有将来决策暂放一边。收集右侧括号的将来决策，上述无限尺度决策问题等价于：^{[需要解释]}

${\displaystyle \max _{a_{0}}\left\{F(x_{0},a_{0})+\beta \left[\max _{\left\{a_{t}\right\}_{t=1}^{\infty }}\sum _{t=1}^{\infty }\beta ^{t-1}F(x_{t},a_{t}):a_{t}\in \Gamma (x_{t}),\;x_{t+1}=T(x_{t},a_{t}),\;\forall t\geq 1\right]\right\}}$ 

服从以下约束：

${\displaystyle a_{0}\in \Gamma (x_{0}),\;x_{1}=T(x_{0},a_{0}).}$ 

此处选择 ${\displaystyle a_{0}}$ , 已知选择会导致时刻1的状态成为 ${\displaystyle x_{1}=T(x_{0},a_{0})}$ . 自时刻1起，该新状态会影响随后决策问题。整个未来的决策问题出现在右边的方括号内。^{[需要解释]}

贝尔曼方程

子问题和贝尔曼方程 对于每个t = 0, . . . , T, 子问题对应的子方程: 已知 st = s,

最大化 rt(st, at) + βrt+1(st+1, at+1)+ · · · + β^T −t−1*rT−1(sT−1, aT−1) + β^T−t*rT (sT )

服从于: 对于 k = t, . . . , T − 1, ak ∈ Ak(sk) sk+1 − gk(sk, ak) = 0

• 最优值函数, v∗t(s): 子问题（第t行）的最大值

• 由此可得贝尔曼方程的公式: (未知数: v∗t(s))

v∗t(s) = max 【a∈At(s)】 rt(s, a) + βv∗t+1(gt(s, a)), s ∈ S, t = 0, . . . , T − 1

v∗T(s) = rT (s), s ∈ S

贝尔曼方程在随机问题的应用