擴展動態規劃：非同步更新與維度詛咒

完整掃描的代價

經典 DP 在每一次迭代都掃過每一個狀態。這很浪費：在任一次掃描中，大多數狀態幾乎不變，而狀態空間某個偏遠角落或許正拖住收斂，你卻還在反覆回溯那些早已正確的狀態。如果狀態集很大，連一次掃描都可能負擔不起。

V(s) \leftarrow \max_a \sum_{s'} p(s' \mid s,a)\,\bigl[\,r(s,a,s') + \gamma\,V(s')\,\bigr]

每次完整備份都要對所有後繼狀態 s' 求和，而一次掃描要對所有狀態都做一遍——這正是開銷大的原因。

非同步 DP

非同步動態規劃（asynchronous dynamic programming）拋棄了「一次掃描必須以同一步調觸及每個狀態」的要求。你一次回溯一個狀態，順序隨你，並重用任何當前的價值——這就是把原地更新推到其邏輯終點。只要每個狀態最終都會持續被選來回溯（沒有任何狀態被永久餓死），收斂依然成立。

回報是：你可以把計算花在重要的地方。把回溯集中在代理人實際造訪的軌跡上，或集中在價值仍然錯得離譜的狀態附近，其餘的就先擱著。這正是同樣的廣義策略迭代精神——進展來自任意組合的部分回溯，而非僵硬的完整遍歷。

優先掃描

如果你可以用任何順序更新，下一個顯而易見的問題就是：接下來該更新哪一個狀態？優先掃描（prioritized sweeping）回答了它。維護一個依「價值可能變動多少」排序的優先佇列——以最近一次自舉更新的幅度（貝爾曼誤差）來衡量。總是回溯優先度最高的狀態，然後提高其前驅狀態的優先度，因為這裡的一個大變動意味著它們的價值現在過時了。

p(s) = \Bigl|\, \max_a \sum_{s'} p(s' \mid s,a)\bigl[\,r + \gamma\,V(s')\,\bigr] - V(s) \,\Bigr|

優先掃描按貝爾曼誤差（一次回溯會使價值改變多少）對每個狀態排序，優先更新誤差最大的狀態。

從佇列中取出待處理貝爾曼誤差最大的狀態。
回溯它；它的價值朝一致性跳動。
對每個前驅狀態，計算該變動會使它移動多少；以該優先度將其插入。
重複——工作從變動的源頭往回傳播。

維度詛咒

更聰明的排程能幫你省下很多，但它無法逃離更深的那道牆。維度詛咒（curse of dimensionality）是指：狀態的數量會隨狀態變數的數量指數成長。一個有三十個二元特徵的問題，其狀態數已經多過你筆電記憶體裡的原子數——你連價值表都存不下，更別說掃描它。表格式 DP 根本無法擴展到高維或連續問題。

|\mathcal{S}| = k^{d}

維數災難：把 d 個變量各離散成 k 個等級，狀態數就以 k 的 d 次方爆炸式增長。

這道牆定義了強化學習的其餘部分。有兩扇門通往外面。一扇是採樣回溯——放棄掃描每一個後繼狀態，改為跟隨採樣到的轉移（蒙地卡羅與 TD 方法）。另一扇是函數逼近（function approximation）——放棄表格，改為學習一個緊湊的參數化價值函數。幾乎每一個現代方法都走過這兩扇門中的一扇或兩扇。

另一扇完全不同的門：線性規劃

值得知道的是：迭代並不是精確求解有限 MDP 的唯一方法。MDP 的線性規劃（linear programming for MDPs）把貝爾曼最佳性條件轉寫成一個線性規劃的約束：在「每個狀態的價值都不小於任何一步前瞻」的條件下，最小化所有狀態價值之和。其解就是最佳價值函數。線性規劃求解器提供最壞情況下的多項式時間保證，並支撐了一部分近似 DP 的理論；不過對於大型問題，實務上值迭代與策略迭代通常更快。