MDP 的線性規劃解法（linear programming for MDPs）

動態規劃並不是求解已知 MDP 的唯一精確方法。貝爾曼最適方程其實定義了一個線性規劃（linear program）——一個有線性目標與線性限制式的最佳化問題——所以你可以把整個 MDP 交給標準的線性規劃求解器，直接從解裡讀出最佳價值。這是看同一個答案的另一個視角。

你最小化各狀態價值的總和，並要求每個價值對每個動作都至少等於「期望獎勵加折扣後繼價值」。在最佳解處，這些不等式恰好在最佳動作所在的地方收緊成等式，把最佳價值函數還原出來。對偶線性規劃有個漂亮的讀法：它的變數正是最佳策略在長期下對各「狀態–動作」的造訪頻率。線性規劃能在多項式時間內解 MDP，也是受限 MDP 等更豐富想法的基礎。