馬爾可夫決策過程 (Markov Decision Process, MDP)

1. MDP 原理介紹

馬爾可夫決策過程 (MDP) 是強化學習 (Reinforcement Learning, RL) 中用于對序貫決策 (Sequential Decision Making) 問題進行數學建模的標準框架。它描述了一個智能體 (Agent) 與環境 (Environment) 交互的過程，其中智能體的目標是最大化其在一段時間內獲得的總獎勵。

MDP 假設環境具有馬爾可夫性質 (Markov Property)，即未來的狀態和獎勵只依賴于當前的狀態和智能體采取的動作，而與過去的狀態或動作歷史無關。

一個 MDP 通常由以下五個核心要素組成，表示為一個五元組 $(S,A,P,R,\gamma )$：

1. 狀態集合 (State Space, $S$):

   • 表示智能體可能處于的所有不同情況或配置的集合。狀態可以是離散的（例如棋盤格的位置）或連續的（例如機器人的關節角度）。這里我們主要關注離散狀態空間。
   • $S_t$ 表示智能體在時間步 $t$ 所處的狀態。

2. 動作集合 (Action Space, $A$):

   • 表示智能體在每個狀態下可以采取的所有可能行為的集合。動作也可以是離散的（例如游戲中按鍵）或連續的（例如控制油門）。有時動作集合依賴于狀態，記為 $A(s)$。
   • $A_t$ 表示智能體在時間步 $t$ 選擇的動作。

3. 狀態轉移概率 (Transition Probability Function, $P$):

   • $P(s^{\prime }|s,a)=Pr(S_{t+1}=s^{\prime }|S_t=s,A_t=a)$。
   • 它定義了在狀態 $s$ 下采取動作 $a$ 后，轉移到下一個狀態 $s^{\prime }$ 的概率。這體現了環境的動態性，可能包含隨機性。
   • 對于所有 $s\in S,a\in A(s)$，必須滿足 ${\sum }_{s^{\prime }\in S}P(s^{\prime }|s,a)=1$。

4. 獎勵函數 (Reward Function, $R$):

   • 定義了智能體在特定狀態下采取特定動作后獲得的即時獎勵。有幾種常見的定義方式：
     • $R(s,a,s^{\prime })$：在狀態 $s$ 采取動作 $a$ 并轉移到狀態 $s^{\prime }$ 時獲得的獎勵。
     • $R(s,a)=E[R_{t+1}|S_t=s,A_t=a]={\sum }_{s^{\prime }}P(s^{\prime }|s,a)R(s,a,s^{\prime })$：在狀態 $s$ 采取動作 $a$ 后期望獲得的即時獎勵。這是更常用的形式。
     • $R(s)$：僅與進入狀態 $s$ 相關聯的獎勵。
   • 獎勵函數 $R$ 定義了問題的目標。智能體的目的是最大化累積獎勵。$R_{t+1}$ 是在時間步 $t+1$ 獲得的獎勵。

5. 折扣因子 (Discount Factor, $\gamma$):

   • $\gamma \in [0,1]$。它是一個用于衡量未來獎勵相對于當前獎勵重要性的參數。
   • $\gamma$ 接近 0 時，智能體更關注即時獎勵（短視）。
   • $\gamma$ 接近 1 時，智能體更關注長期累積獎勵（遠視）。
   • $\gamma <1$ 通常也確保了無限時間范圍內的累積獎勵（回報）是有限的。

馬爾可夫性質 (Markov Property)
這是 MDP 的核心假設：$P(S_{t+1},R_{t+1}|S_t,A_t,S_{t?1},A_{t?1},...,S_0,A_0)=P(S_{t+1},R_{t+1}|S_t,A_t)$。這意味著，系統下一時刻的狀態和獲得的獎勵，僅取決于當前的狀態 $S_t$ 和當前采取的動作 $A_t$，與之前的歷史狀態和動作無關。

目標
智能體的目標是找到一個策略 (Policy) $\pi$，該策略定義了在每個狀態 $s$ 下選擇動作 $a$ 的方式（通常是概率分布 $\pi (a|s)=Pr(A_t=a|S_t=s)$），以最大化期望累積折扣獎勵 (Expected Cumulative Discounted Reward)，也稱為回報 (Return) 或 價值 (Value)。
從時間步 $t$ 開始的回報定義為：
$$G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+...=\sum _{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}$$

價值函數 (Value Functions)
為了評估策略的好壞，引入了價值函數：

• 狀態價值函數 (State-Value Function) $V^{\pi }(s)$: 從狀態 $s$ 開始，遵循策略 $\pi$ 所能獲得的期望回報。
  $$V^{\pi }(s)=E_{\pi }[G_t|S_t=s]=E_{\pi }\left[\sum _{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}|S_t=s\right]$$
• 動作價值函數 (Action-Value Function) $Q^{\pi }(s,a)$: 在狀態 $s$ 采取動作 $a$，然后遵循策略 $\pi$ 所能獲得的期望回報。
  $$Q^{\pi }(s,a)=E_{\pi }[G_t|S_t=s,A_t=a]=E_{\pi }\left[\sum _{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}|S_t=s,A_t=a\right]$$

貝爾曼方程 (Bellman Equations)
價值函數滿足遞歸關系，稱為貝爾曼方程，它們是大多數 RL 算法的基礎。

• 貝爾曼期望方程 (Bellman Expectation Equation for $V^{\pi }$):
  $$V^{\pi }(s)=\sum _a\pi (a|s)\sum _{s^{\prime }}P(s^{\prime }|s,a)[R(s,a,s^{\prime })+\gamma V^{\pi }(s^{\prime })]$$
  (若使用 $R(s,a)$，則為: $V^{\pi }(s)={\sum }_a\pi (a|s)(R(s,a)+\gamma {\sum }_{s^{\prime }}P(s^{\prime }|s,a)V^{\pi }(s^{\prime }))$)
• 貝爾曼期望方程 (Bellman Expectation Equation for $Q^{\pi }$):
  $$Q^{\pi }(s,a)=\sum _{s^{\prime }}P(s^{\prime }|s,a)[R(s,a,s^{\prime })+\gamma \sum _{a^{\prime }}\pi (a^{\prime }|s^{\prime })Q^{\pi }(s^{\prime },a^{\prime })]$$
  (若使用 $R(s,a)$，則為: $Q^{\pi }(s,a)=R(s,a)+\gamma {\sum }_{s^{\prime }}P(s^{\prime }|s,a)V^{\pi }(s^{\prime })=R(s,a)+\gamma {\sum }_{s^{\prime }}P(s^{\prime }|s,a){\sum }_{a^{\prime }}\pi (a^{\prime }|s^{\prime })Q^{\pi }(s^{\prime },a^{\prime }))$)

強化學習的目標是找到最優策略 ${\pi }_{?}$，使得所有狀態的價值 $V^{{\pi }_{?}}(s)$ 或所有狀態動作對的價值 $Q^{{\pi }_{?}}(s,a)$ 最大化。對應的價值函數稱為最優價值函數 $V_{?}(s)$ 和 $Q_{?}(s,a)$，它們滿足貝爾曼最優方程 (Bellman Optimality Equations)。

2. MDP 建模/實現步驟

將一個實際問題建模為 MDP，通常涉及以下步驟。這并不是一個具體的編程實現，而是定義問題的數學框架：

1. 定義狀態空間 $S$: 確定能夠充分描述問題狀態的所有變量和它們的可能取值。狀態需要滿足馬爾可夫性質。選擇合適的狀態表示至關重要。
2. 定義動作空間 $A$: 確定智能體在每個狀態下可以采取的所有動作。
3. 定義狀態轉移概率 $P(s^{\prime }|s,a)$: 描述環境的動態。對于每個狀態 $s$ 和動作 $a$，確定轉移到下一個狀態 $s^{\prime }$ 的概率。這通常是建模中最困難的部分，可能基于物理定律、規則或數據估計。
4. 定義獎勵函數 $R(s,a)$ 或 $R(s,a,s^{\prime })$: 設計獎勵信號以引導智能體實現目標。獎勵應該反映任務的即時成功或失敗。例如，目標達成給予正獎勵，危險狀態給予負獎勵，普通移動給予小的負獎勵（鼓勵效率）。
5. 選擇折扣因子 $\gamma$: 根據任務是有限期還是無限期，以及對未來獎勵的重視程度來選擇 $\gamma$。

完成建模后:

• 如果 MDP 的模型（$P$ 和 $R$）已知，可以使用動態規劃 (Dynamic Programming) 方法（如價值迭代 Value Iteration 或策略迭代 Policy Iteration）來精確計算最優價值函數和最優策略。
• 如果 MDP 的模型未知（這是更常見的情況），則需要使用強化學習算法（如 Q-Learning, SARSA, DQN, Actor-Critic 等），通過智能體與環境的交互（采樣）來學習最優策略。

3. MDP 示例：簡單網格世界 (Grid World)

假設有一個 3x3 的網格世界。

+---+---+---+
|   |   | G |  (0,0) (0,1) (0,2)
+---+---+---+
|   | W |   |  (1,0) (1,1) (1,2)
+---+---+---+
| S |   |   |  (2,0) (2,1) (2,2)
+---+---+---+

• S (Start): 智能體的起始位置 (2,0)。
• G (Goal): 目標位置 (0,2)，到達后獲得獎勵。
• W (Wall): 墻壁 (1,1)，無法進入。
• 空格: 可以移動的普通格子。

MDP 組件定義:

1. 狀態空間 $S$: 每個格子的坐標 $(r,c)$，其中 r ∈ { 0 , 1 , 2 } , c ∈ { 0 , 1 , 2 } r \in \{0, 1, 2\}, c \in \{0, 1, 2\} r∈{0,1,2},c∈{0,1,2}。共 9 個狀態。狀態 (1,1) 是障礙物。狀態 (0,2) 是目標狀態（可以設為終止狀態）。

2. 動作空間 $A$: 在每個非終止狀態，智能體可以嘗試向四個方向移動：{上 (Up), 下 (Down), 左 (Left), 右 (Right)}。

3. 狀態轉移概率 $P(s^{\prime }|s,a)$:

   • 確定性環境: 假設移動是確定的。
     • 如果從狀態 $s=(r,c)$ 嘗試動作 $a$，目標格子 $s^{\prime }=(r^{\prime },c^{\prime })$ 在網格內且不是墻壁 (1,1)，則 $P(s^{\prime }|s,a)=1$，其他 $P(s^{\prime \prime }|s,a)=0$。
     • 如果目標格子 $s^{\prime }$ 超出邊界或撞墻 (1,1)，則智能體停留在原地，即 $P(s|s,a)=1$。
     • 如果當前狀態 $s$ 是目標狀態 G (0,2)，可以設定 G 為終止狀態，任何動作都停留在 G (或轉移到一個特殊的終止狀態)。
   • 隨機性環境 (可選): 假設有 80% 的概率按預期方向移動，各有 10% 的概率向預定方向的左側或右側移動（撞墻或邊界則停留在原地）。例如，在 (1,0) 選擇 ‘Up’：
     • 80% 概率到達 (0,0)。
     • 10% 概率向左滑，撞邊界，停留在 (1,0)。
     • 10% 概率向右滑，撞墻 (1,1)，停留在 (1,0)。
     • 因此 $P((0,0)|(1,0),\text{’Up’})=0.8$, $P((1,0)|(1,0),\text{’Up’})=0.2$。

4. 獎勵函數 $R(s,a)$ 或 $R(s,a,s^{\prime })$:

   • 到達目標狀態 G (0,2)：$R=+10$。
   • 每次移動（到達非目標狀態）：$R=?0.1$ （鼓勵盡快到達目標）。
   • 撞墻或邊界（停留在原地）：$R=?1$ （輕微懲罰）。
   • (另一種設計：只有到達目標狀態 G 時獲得 $R=+1$，其他所有轉移獎勵為 0)。

5. 折扣因子 $\gamma$: 例如， $\gamma =0.9$。

目標: 找到一個策略 $\pi (a|s)$，使得從狀態 S (2,0) 出發，到達 G (0,2) 的期望累積折扣獎勵最大化。這通常意味著找到一條避開墻壁、最快到達目標的路徑。

通過動態規劃（如果 $P,R$ 已知）或強化學習算法（如果未知或需要通過交互學習），可以計算出每個狀態的最佳動作，形成最優策略。例如，在 (2,0) 最優動作可能是 ‘Up’，在 (1,0) 最優動作可能是 ‘Up’ 或 ‘Right’ (取決于隨機性和獎勵設計)，最終引導智能體走向 (0,2)。