貝爾曼方程

「貝爾曼方程（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