貝爾曼方程

「貝爾曼方程（Bellman Equation）」也被稱作「動態規劃方程（Dynamic Programming Equation）」，由理查·貝爾曼（Richard Bellman）發現。貝爾曼方程是動態規劃（Dynamic Programming）這種數學最佳化方法能夠達到最佳化的必要條件。此方程將「決策問題在特定時間點的值」以「來自初始選擇的報酬 及 由初始選擇衍生的決策問題的值」的形式表示。藉這個方式將動態最佳化問題變成較簡單的子問題，而這些子問題遵守由貝爾曼所提出的「最佳化原理」。

貝爾曼方程最早應用在工程領域的控制理論及其他應用數學領域，而後成為經濟學上的重要工具。

幾乎所有可以用最佳控制理論（Optimal Control Theory）解決的問題也可以透過分析合適的貝爾曼方程得到解決。然而，「貝爾曼方程」通常指離散時間（discrete-time）最佳化問題的動態規劃方程。處理連續時間（continuous-time）最佳化問題上，也有類似的偏微分方程，稱作漢彌爾頓-雅各比-貝爾曼方程（Hamilton–Jacobi–Bellman Equation, HJB Equation）。

動態規劃中的解析概念

想了解貝爾曼方程，要先了解許多相關概念。首先，任何最佳化問題都有目標：旅行時間最小化、成本最小化、利潤最大化、效用最大化等。用來描述目標的數學函數就稱為目標函數。

動態規劃將多期規劃問題轉為不同時間點上較簡單的步驟，因此，它需要追蹤決策背景情況隨時間的變化。作正確決策所需要當前情況的資訊被稱作是「狀態（State）」（貝爾曼，1957，Ch. III.2）。例如，為了決定每個時間要花多少錢，人們必須要知道他們初始財富的量，此例中財富就是一種「狀態變數（State Variables）」，或簡稱「狀態（State）」，當然也可能還有其他的種類。

從任意時點上所挑選以操作的變數通常稱為「控制變數」（Control Variables），或簡稱「控制」（Control）（控制理論中描述輸入的變數）。例如給定現在所具有的財富（狀態），人們便可以用以決定當下的消費（控制變數）。挑選當下的控制變數可被視為挑選下個狀態，廣義而言，下個狀態受到當下控制變數及其他因子的影響。舉個簡單的例子：今天的財富（狀態）及消費（控制變數）會決定明天的財富（新的狀態），雖然通常也還有其他的因素可以影響明天的財富（例如獲得意外之財）。

動態規劃方法中利用「找尋某種規則來求得各可能狀態下的（最佳）控制為何」來達成目標函數最佳化。例如：假設消費（c）只與財富（W）相關，想要找到一套規則$c(W)$來以財富描述消費。這些「將控制（Controls）表示成狀態（States）的函數」的規則被稱為策略函數（Policy Function）。

從定義可知，最佳化目標函數的策略乃是所有可能的策略函數中，其對應到目標函數值最佳者。沿用上述的例子，若某人利用給定的財富來消費以最大化快樂的感覺（這裡假定「快樂的感覺」可以被數學函數描述，像是效用函數等），那麼各種初始的財富便會對應到一個可能的最大快樂，表示成$H(W)$。這個最大的可能目標函數值（快樂的感覺），即是價值函數（Value Function）。

貝爾曼方程的推導

动态决策问题

令 $t$ 时刻的状态为 $x_{t}$。对于一个从时刻 0 开始的决策，令$x_{0}$为初始状态。在任意时刻，可能的行动集合都取决于当前状态。可以将其写作 $a_{t}\in \Gamma (x_{t})$，其中，$a_{t}$代表了一个或者多个控制变量。还可以假定，当采取行动 $a$时，状态由$x$变为新状态 $T(x,a)$，当前收益为$F(x,a)$。最后使用 $0<\beta <1$代表折扣因子（discount factor），折扣因子平衡了当前时刻的收益与较远时刻的收益间的影响。

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

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

服从以下约束：

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

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

贝尔曼最优化原理

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

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

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

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

$\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\}$

服从以下约束：

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

此处选择 $a_{0}$, 已知选择会导致时刻1的状态成为 $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