動態規劃原理(dynamic programming principle)
動態規劃原理(DPP)是讓「不確定下的序列決策」變得可處理的那一個核心想法。貝爾曼把它陳述為最佳性原理:最佳策略具有此性質——無論初始狀態與第一個決策為何,其餘決策對由此產生的狀態而言必須構成最佳策略。用白話說——最佳計畫的一個尾段本身也是最佳的。這讓你能把「對整個策略做的一個大得不可能的最佳化」換成「一連串只對下一步做的小最佳化」,每一步都信任價值函數已概括了其後的一切。
形式上,對價值函數為 V(t,x) 的受控擴散,DPP 說:對 [t, T] 中任一中間(停止)時刻 theta,有 V(t,x) = inf_u E[ integral_t^theta f(X_s, u_s) ds + V(theta, X_theta) given X_t = x ]。仔細讀它:你在短區間 [t, theta] 上最佳化所累積的成本,而在時刻 theta 你停止逐項記帳,僅向自己收取價值函數 V(theta, X_theta)——因為依假設自 theta 起你將最佳地行動,而 V 已把那個最佳續行編碼進去了。證明分兩半:「<=」(任何控制都不優於在尾段最佳地行動)與「>=」(你能可測地把近最佳的尾段控制黏接起來,這需要可測選擇論證)。DPP 對非常一般的(馬可夫)問題成立,是把 theta 送向 t 並用伊藤公式推導 HJB 方程的基底。
DPP 正是最佳控制何以可計算的原因:離散時間的倒向歸納、連續時間的 HJB、強化學習中的價值迭代與 Q-學習,全都是它的化身。一個誠實的提醒:抽象的 DPP 在直覺上顯然,但技術上微妙——「>=」方向要求你能以可測、適應的方式選取近最佳控制(可測選擇定理),而條件期望的操作需要可積性。它也預設問題確為馬可夫(價值依賴當前狀態而非全部歷史);對非馬可夫成本或部分觀測,必須先擴大狀態(例如擴到濾波器的條件分布)DPP 才適用。
在一格狀城市網中、旅行時間隨機的最短路徑問題:與其枚舉所有路線,定義 V(城市) = 到目的地的期望最小剩餘成本。則 V(c) = min over 鄰居 c' of [ E(成本 c -> c') + V(c') ]。從目的地倒向求解這條貝爾曼方程,便得每個城市的最佳下一步——DPP 把指數級搜尋化為線性掃描。
貝爾曼原理:最佳的下一步只需你將落腳處的價值函數,而不需整個未來計畫。
DPP 看似顯然,但其嚴格證明(「>=」那半)需要近最佳控制的可測選擇與可積性;且它要求馬可夫狀態——部分觀測迫使你先把狀態提升到條件分布(即濾波器)。