AI Planning 學習筆記（5）：認識 Markov Decision Process（MDP）

在上一篇文章中，我們介紹了 Decision Theory，並了解到理性的 Agent 應遵循 Maximum Expected Utility（MEU） 原則，也就是選擇 Expected Utility 最大的 Action。

不過，Decision Theory 其實隱含了一個限制，那就是它通常只考慮一次決策。

然而，現實世界中的 AI 幾乎都不是如此。

例如：

自駕車需要每秒重新決定加速、煞車或轉彎。
機器人需要持續規劃下一步該往哪裡移動。
AlphaGo 必須考慮數十步甚至數百步之後的局勢。

這些問題都有一個共同點：現在的決策，會影響未來能做出的決策。

因此，我們需要一個能夠描述序列決策（Sequential Decision Making）的數學模型。

這就是 Markov Decision Process（MDP）。

什麼是 Markov Decision Process？

MDP 是描述 完全可觀測（Fully Observable）、具有隨機性（Stochastic） 環境中序列決策問題的標準模型。

一個 MDP 可以表示成：

M=(S,A,T,R,\gamma)

其中包含五個元素：

元件	說明
$S$	所有可能的狀態 State。
$A$	Agent 可以採取的 Action。
$T$	Transition Function，描述執行 Action 後轉移到下一個 State 的機率。
$R$	Reward Function，描述每次 State Transition 所得到的 Reward。
$\gamma$	Discount Factor，用來衡量未來 Reward 的重要程度。

可以發現，MDP 與上一篇介紹的 Decision Model 非常相似。

最大的不同在於：

MDP 關心的是長期累積 Reward，而不是單一步驟的 Utility。

因此，我們想要找到的，也不再是一個 Action，而是一個最佳 Policy。

Markov Property

MDP 建立在一個重要假設之上：

未來只與現在有關，而與過去無關。

這稱為 Markov Property。

數學上表示為：

P(s_{t+1}|s_t,a_t,s_{t-1},\ldots)=P(s_{t+1}|s_t,a_t)

也就是說，只要知道目前 State和當下採取的 Action，就足以預測下一個 State。

不需要知道更早之前發生了什麼。

例如，一台掃地機器人只需要知道自己目前的位置和是否偵測到障礙物，

就可以決定下一步如何移動，而不需要記住昨天走過哪些路。

Markov Property 正是 MDP 能夠有效建模的關鍵假設。

我們真正想找到的答案：Policy

上一篇提到，Policy 是：每個 State 應該採取哪個 Action 的完整策略。

在 MDP 中，我們通常寫成：

\pi:S\rightarrow A

代表每個 State 都會對應到一個 Action。

而我們真正想求的是：

\pi^*

也就是 Optimal Policy。

它能讓 Agent 長期獲得最大的 Expected Return。

Finite Horizon 與 Infinite Horizon

並不是所有 Decision Problem 都會一直持續下去。

因此，MDP 通常分成兩種類型。

	Finite Horizon	Infinite Horizon
決策長度	固定步數	沒有固定終點
Policy	Nonstationary	Stationary
Utility	有限	可能無限

如果是一場棋局，可能最多只有數百步，這就是 Finite Horizon。

但像是：

自駕車
工廠機器人
網頁推薦系統

理論上都可能持續運作，因此屬於 Infinite Horizon。

這時就會遇到一個問題：

如果 Reward 一直累積，

Utility 不是會變成無限大嗎？

因此，我們引入 Discount Factor。

Discount Factor

Discount Factor 記作：

0\le\gamma\le1

它表示未來 Reward 的重要程度。

如果 $\gamma=0$ ，代表 Agent 只在乎眼前 Reward。

如果 $\gamma\approx1$ ，則代表 Agent 也十分重視長期回報。

Discount Factor 不僅可以用來表達 Agent 對未來的重視程度，也保證 Infinite Horizon 下的累積 Utility 有上界：

U \le \frac{R_{\max}}{1-\gamma}

因此，即使 Agent 持續運作，也能得到有限的 Value。

MDP 的核心：Bellman Equation

Bellman Equation 描述：

一個 State 的價值，等於目前 Reward，加上未來最佳 Reward。

表示為：

V(s)= \max_a \sum_{s’} P(s’|s,a) \left[ R(s,a,s’) +\gamma V(s’) \right]

這是一個非常重要的遞迴關係。

可以發現 State 的 Value，

取決於現在得到多少 Reward，以及下一個 State 的 Value。

因此，只要知道未來每個 State 的 Value，就能反推出現在 State 的最佳選擇。

根據 Bellman Equation，也可以得到 Optimal Policy：

\pi^*(s) \arg\max_a \sum_{s’} P(s’|s,a) \left[ R+\gamma V(s’) \right]

此外，我們也常定義 Q-Function：

Q(s,a) \sum_{s’} P(s’|s,a) \left[ R+\gamma V(s’) \right]

它代表：

在 State (s) 執行 Action (a) 所能得到的 Expected Return。

因此 $V(s)=\max_aQ(s,a)$

未來介紹 Q-Learning 時，這個概念會再次出現。

Value Iteration

既然 Bellman Equation 是遞迴的，

要如何真正求出每個 State 的 Value？

其中一種方法就是 Value Iteration。

它的想法是先假設所有 State 的 Value 都是 0，

然後反覆利用 Bellman Equation 更新。

每一次更新 $V_{k+1}(s) \max_a \sum_{s’} P(s’|s,a) \left[ R+\gamma V_k(s’) \right]$

隨著更新次數增加，Value 會逐漸收斂到真正的 Optimal Value Function。

Policy Iteration

另一種經典方法則是 Policy Iteration。

與其一直更新 Value，它反覆更新 Policy。

整個流程只有兩個步驟：

Policy Evaluation
- 固定目前的 Policy，計算每個 State 的 Value。
Policy Improvement
- 利用剛算出的 Value，重新選擇更好的 Action。

重複上述兩步，直到 Policy 不再改變。

雖然每一次 Evaluation 都需要解聯立方程式，因此計算成本較高，但在許多問題中，Policy Iteration 往往比 Value Iteration 更快收斂。

當 State Space 太大怎麼辦？

前面的方法都有一個共同前提，那就是必須先計算整個 MDP。

但是在許多實際問題中，

State Space 可能大到根本無法全部列舉。

例如西洋棋、圍棋等。

因此，我們改成只有真正需要做決策時，才開始搜尋。

這就是 Online Planning。

Monte Carlo Tree Search（MCTS）

目前最成功的 Online Planning 方法之一，就是 Monte Carlo Tree Search（MCTS）。

MCTS 並不需要完整展開整棵搜尋樹，而是不斷重複四個步驟：

Selection：根據目前資訊，選擇最值得探索的節點。
Expansion：擴展新的節點。
Simulation（Rollout）：從新節點模擬到終局，估計 Reward。
Backup：將 Simulation 的結果回傳，更新整條路徑上的 Value。

透過大量模擬，MCTS 能逐漸找到值得探索的方向，而不需要遍歷整個 State Space。

UCT：探索與利用的平衡

Selection 步驟時，MCTS 最常使用 UCT（Upper Confidence Bound applied to Trees）。

其公式為 $\pi_{UCT} \arg\max_a \left( \hat Q(s,a) + c \sqrt{\frac{\ln N(s)}{N(s,a)}} \right)$

其中：

第一項 Exploitation：選擇目前看起來最好的 Action。
第二項 Exploration Bonus：鼓勵嘗試還沒探索過的 Action。

這兩者之間形成了著名的 Exploration–Exploitation Trade-off。

如果只利用（Exploit），可能永遠找不到更好的策略；如果只探索（Explore），又無法充分利用已知資訊。

UCT 正是在兩者之間取得平衡，因此成為 MCTS 的核心。

小結

上一篇介紹了 Decision Theory，說明 AI 如何在一次決策中最大化 Expected Utility。

而這一篇則更進一步，回答了

如果決策是連續進行的，AI 該如何思考？

本文介紹了 MDP 的核心概念：

MDP 使用 $(S,A,T,R,\gamma)$ 建立序列決策模型。
Markov Property 假設未來只與目前 State 有關。
Bellman Equation 提供求解最佳 Policy 的遞迴關係。
Value Iteration 與 Policy Iteration 是兩種經典的離線演算法。
Monte Carlo Tree Search（MCTS） 則適合處理龐大的狀態空間，透過模擬逐步找到最佳決策。

下一篇文章，我們將進一步討論 Reinforcement Learning。與 MDP 不同的是，Agent 不再事先知道 Transition Function 和 Reward，而是必須透過與環境互動，一步步學會最佳策略。

AI Planning 學習筆記（5）：認識 Markov Decision Process（MDP）