馬可夫決策過程（Markov Decision Process, MDP）

馬可夫決策過程（Markov Decision Process, MDP）是在結果具有不確定性時，用於序列決策的模型。MDP 起源於 1950 年代的作業研究領域，此後在多個領域獲得重視。其名稱源於與馬可夫鏈（Markov chains）之間的關聯，而 Markov chains 是由俄國數學家 Andrey Markov 所提出。

MDP 是強化學習（Reinforcement Learning, RL）的正式數學模型。它是從交互作用中學習以實現目標的一個簡單框架。這個交互作用（interactions）是指代理人（agent）與環境（environment）之間的交互作用，如下圖。

Agent 和 environment 在一系列的時步（time steps）， $t=0,1,2,3,\cdots$ ，進行 interaction。在每個 time step $t$ ，agent 會接收到來自環境的狀態（state）， $S_t \in \mathcal{S}$ ，的一些表徵（representation）。在這基礎上，agent 會選擇一個動作（action）， $A_t \in \mathcal{A}(s)$ 。在下一個 time step $t+1$ ，agent 會從 environment 收到一個獎勵（reward）， $R_{t+1} \in \mathcal{R} \subset \mathbb{R}$ ，並同時發現自己處在一個新的狀態 $S_{t+1}$ 。

The agent–environment interaction in a Markov decision process. (source: Reinforcement Learning: An Introduction, 2nd)

因此，MDP 和 agent 會一起產生一個軌跡（trajectory），如下。

$S_0, A_0,R_1,S_1, A_1,R_2,S_2, A_2,R_3,\cdots$

完整的 MDP 由五個元素構成：

$(\mathcal{S}, \mathcal{A}, p, r, \gamma)$

狀態空間（State Space）

狀態空間（State space）記作 $\mathcal{S}$ 。在每個 time step $t$ ，agent 位於某個state $S_t \in \mathcal{S}$ 。當下的 state $S_t$ 是 agent 在 time step $t$ 所能觀察的資訊，用來決定下一個 action $A_t$ 。因此，state $S_t$ 必須包括有關過去 agent 與 environment 互動的所有可能對未來有影響的資訊。若符合此條件，則表示該 state 具有馬可夫性質（Markov Property）：

$\Pr(S_{t+1} \mid S_t, A_t) = \Pr(S_{t+1} \mid S_1, A_1, \cdots, S_t, A_t)$

這也就是說，當 agent 在 state $S_t$ 時，它可以丟棄以前的 states 和 actions，（ $S_1, A_1, \cdots, S_{t-1}, A_{t-1}$ ）。未來只取決於現在，不取決於過去。

動作空間（Action Space）

動作空間（Action space）記作 $\mathcal{A}$ 。每個 state $s$ 可選的動作集合記作 $\mathcal{A}(s)$ 。

狀態轉移機率（State-Transition Probabilities）

在 state $s$ 下選擇 action $a$ 後，會有數個可轉移的 states，這會由狀態轉移機率（State-Transition Probabilities） $p$ 來決定下一個 state $s^\prime$ 。

$\displaystyle p(s^\prime, r \mid s, a) \doteq \Pr\{S_t=s^\prime, R_t=r \mid S_{t-1}=s, A_{t-1}=a\} \\\\ \sum_{s^\prime \in \mathcal{S}} \sum_{r \in \mathcal{R}} p(s^\prime, r \mid s, a) = 1, \forall s \in \mathcal{S}, a \in \mathcal{A}(s) \\\\ p(s^\prime \mid s, a) \doteq \mathbb{E} \left[ R_t \mid S_{t-1}=s, A_{t-1}=a \right] = \sum_{r \in \mathcal{R}} p(s^\prime, r \mid s, a)$

獎勵（Reward）

獎勵（Reward）記作 $\mathcal{R}$ 。Reward 是即時回饋的。Reward $r$ 發生在從 state $s$ 選擇 action $a$ 後，轉移至 state $s^\prime$ 的過程中。

$\displaystyle r(s, a, s^\prime) \doteq \mathbb{E} \left[ R_t \mid S_{t-1}=s, A_{t-1}=a, S_t=s^\prime \right] = \sum_{r \in \mathcal{R}} r \frac{p(s^\prime, r \mid s, a)}{p(s^\prime \mid s, a)} \\\\ r(s, a) \doteq \mathbb{E} \left[ R_t \mid S_{t-1}=s, A_{t-1}=a \right] = \sum_{r \in \mathcal{R}} r \sum_{s^\prime \in \mathcal{S}} p(s^\prime, r \mid s, a)$

折扣因子（Discount Factor）

折扣因子（Discount factor）記作 $\gamma \in \left[ 0,1 \right]$ 。它是用來衡量未來 reward 的價值。當 $\gamma=0$ 時，表示只重視當下的 reward；當 $\gamma=1$ 時，表示未來的 reward 與現在的 reward 同等重要。

回報（Returns）和分節（Episodes）

Agent 的目標，從長遠來看是最大化累積的 reward，也就是最大化在 time step $t$ 之後能接受到的 reward。我們稱為最大化預期回報（expected return）。在 time step $t$ 的 return 記作 $G_t$ 。在最簡單的情況下，return 是 reward 的總和：

$\displaystyle G_t \doteq R_{t+1} + R_{t+2} + R_{t+3} + \cdots + R_T = \sum_{k=t+1}^{T} \gamma^{k-t-1} R_k$

其中 $T$ 為最後一個 time step。

當 agent 和 environment 的 interaction 可以自然地被劃分為子序列時，我們將這樣的子序列稱為分節（episodes）。每個 episode 以一個稱為終端狀態（terminal state）的特殊狀態結束。每個 episode 與上一個 episode 是無關的。這種任務被稱為分節式任務（episodic tasks），如一局遊戲。

當 agent 和 environment 的 interaction 無法被自然地劃分為 episodes，而是不斷地持續進行時，這種任務被稱為連續性任務（continuing tasks），如生命週期相當長的機器人應用。因此，在 $G_t$ 的公式裡，最後的 time step 將是 $T=\infty$ 。當我們試圖最大化 return 時， $G_t$ 很輕易地成為無窮大。

我們可以使用折扣（discounting）來解決這個問題。Agent 將最大化預期折扣回報（expected discounted return）：

$\displaystyle G_t \doteq R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \gamma^3 R_{t+4} + \cdots = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$

其中 $\gamma \in \left[ 0,1 \right]$ 為折扣因子（discounting factor）。

連續時步（Successive time steps）的 return 是相互關聯，這對 RL 的理論和演算法很重要：

$G_t \doteq R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \gamma^3 R_{t+4} + \cdots \\\\ \hphantom{G_t \doteq \space} R_{t+1} + \gamma (R_{t+2} + \gamma^1 R_{t+3} + \gamma^2 R_{t+4} + \cdots) \\\\ \hphantom{G_t \doteq \space} R_{t+1} + \gamma G_{t+1}$

雖然 discounted return 是由無窮多項組成，但如果 reward 是非零常數，且 $\gamma < 1$ ，則 return 仍是有限的值。例如，如果 reward 是 $+1$ ，則 return 為：

$\displaystyle G_t = \sum_{k=0}^\infty \gamma^k = \frac{1}{1 - \gamma}$

策略（Policy）

每個 state $s$ 是使用策略（policy）來從動作集合 $\mathcal{A}(s)$ 中，選擇 action $a \in \mathcal{A}(s)$ 。Policy 記作 $\pi$ 。正式地說，policy 是一個從 state 對可選的 actions 的機率分佈。

在 time step $t$ 時，當 agent 處於 state $s$ ，依據 policy $\pi$ 選擇 action $a$ 的機率為：

$\pi(a \mid s) = \Pr(A_t = a \mid S_t = s)$

Policy 可以是決定性策略（deterministic policy）。也就是 policy $\pi$ 永遠只會選擇某一個 action。

$\pi(a \mid s) = \left \{ \begin{matrix} 1 & a = \pi(s) \\ 0 & \text{otherwise} \end{matrix} \right.$

Policy 也可以是隨機性策略（stochastic policy），則每個 action 都有被選中的機率。

價值函數（Value Function）

價值函數（Value function）是一個對 policy 的評估。評估，在 policy $\pi$ 下，評估未來能獲得的 expected return 是多少。

狀態價值函數（State-Value Function）

在 policy $\pi$ 下，從 state $s$ 開始，評估未來能獲得的 expected return 是多少？這個稱為 policy $\pi$ 的狀態價值函數（state-value function），記作 $v_\pi(s)$ 。

$\displaystyle v_\pi(s) \doteq \mathbb{E}_\pi \left[ G_t \mid S_t=s \right] = \mathbb{E}_\pi \left[ \sum_{k=0}^\infty \gamma^k R_{t+k+1} \mid S_t=s \right], \forall s \in \mathcal{S}$

動作價值函數（Action-Value Function）

在 policy $\pi$ 下，在 state $s$ 下並選擇 action $a$ 開始，評估未來能獲得的 expected return 是多少？這個稱為 policy $\pi$ 的動作價值函數（action-value function），記作 $q_\pi(s,a)$ ，也因此又被稱為 q-function。

$\displaystyle q_\pi(s,a) \doteq \mathbb{E}_\pi \left[ G_t \mid S_t=s, A_t=a \right] = \mathbb{E}_\pi \left[ \sum_{k=0}^\infty \gamma^k R_{t+k+1} \mid S_t=s, A_t=a \right]$

狀態價值函數（State-Value Function）和動作價值函數（Action-Value Function）之間的關係

State-value function $v$ 和 action-value function $q$ 之間的關係貫穿了整個 RL。因此，這小節中的公式將會在 RL 中一直被提及。

以下是 $v_\pi$ 的 backup diagram，其中空心圓是 states，而實心圓是 actions。這張圖總括我們至目前為止談論到的元素。在 state $s$ 下，依據 policy $\pi$ 來選擇 action $a$ 。然後，依據 state-transition dynamics $p$ 決定下一個 state $s^\prime$ 並且產生一個 reward $r$ 給 state $s^\prime$ 。

Backup diagram (source: Reinforcement Learning: An Introduction, 2nd).

首先，我們來看 state-value function 對 action-value function 的關係。在一個給定的 state $s$ 下， $v_\pi(s)$ 是對所有可能 action $a$ 的加權期望，而其加權的權重由 policy $\pi(a \mid s)$ 所決定。換言之，state-value function 可以視為 action-value function 的期望值。

$\displaystyle v_\pi(s) = \sum_a \pi(a \mid s) q_\pi(s, a)$

接下來，我們來看 action-value function 對 state-value function 的遞迴關係。在 state $s$ 下選擇 action $a$ 後， $q_\pi(s, a)$ 是對所有可能的下一個 state $s^\prime$ 與對應即時 reward $r$ 的加權期望，而其加權的權重由 state-transition probabilities $p(s^\prime, r \mid s, a)$ 所決定。對每一個可能的 $(s,r)$ ，我們累加即時 reward $r$ 與折扣後的未來價值 $\gamma v_\pi(s)$ 。因此，action-value function 等於即時 reward 加上折扣後的 state-value function 的期望值。

$\displaystyle q_\pi(s, a) = \sum_{s^\prime, r} p(s^\prime, r \mid s, a) \left[ r + \gamma v_\pi(s^\prime) \right]$

貝爾曼期望方程（Bellman Expectation Equation）

貝爾曼方程（Bellman Equation），以 Richard E. Bellman 之名命名，是動態規劃（Dynamic Programming）中的一項技術。Bellman 所提出的最適性原則（principle of optimality）是指，一個最佳化問題可以被拆解為一個由子問題組成的遞迴結構。任何一個狀態的價值，都可以表達為某些初始選擇所帶來的即時報酬，加上因這些選擇所導致的後續子問題的價值。

因此，Bellman equation 的基本思想是，一個 state 的 value 可以表達為下一步的 reward 加上下一個 state 的 value 的期望值。

狀態價值函數（State-Value Function）的貝爾曼期望方程（Bellman Expectation Equation）

在 policy $\pi$ 下，state-value function $v_\pi$ 可以寫成如下的遞迴形式：

$\displaystyle v_\pi(s) \doteq \mathbb{E}_\pi \left[ G_t \mid S_t=s \right] \\\\ \hphantom{v_\pi(s)} = \mathbb{E}_\pi \left[ R_{t+1} + \gamma G_{t+1} \mid S_t=s \right] \\\\ \hphantom{v_\pi(s)} = \sum_a \pi(a \mid s) \sum_{s^\prime} \sum_r p(s^\prime, r \mid s, a) \Big[ r + \gamma \mathbb{E}_\pi \left[ G_{t+1} \mid S_{t+1} = s^\prime \right] \Big] \\\\ \hphantom{v_\pi(s)} = \sum_a \pi(a \mid s) \sum_{s^\prime} \sum_r p(s^\prime, r \mid s, a) \Big[ r + \gamma v_\pi(s^\prime) \Big], \forall s \in \mathcal{S}$

這個方程描述，在 state $s$ 下， $v_\pi(s)$ 是對所有可能 action $a$ 的加權期望，而加權方式由 $policy \pi(a \mid s)$ 所決定。每個 action $a$ 的價值又是其可能的下一個 state $s^\prime$ 與 reward $r$ 所帶來的即時報酬，以及折扣後的未來價值的期望。因此，我們稱此為貝爾曼期望方程（Bellman Expectation Equation）。

動作價值函數（Action-Value Function）的貝爾曼期望方程（Bellman Expectation Equation）

對 action-value function $q_\pi(s,a)$ 進行同樣的遞迴推導，可以得到：

$\displaystyle q_\pi(s, a) \doteq \mathbb{E}_\pi \left[ G_t \mid S_t=s, A_t=a \right] \\\\ \hphantom{v_\pi(s, a)} = \mathbb{E}_\pi \left[ R_{t+1} + \gamma G_{t+1} \mid S_t=s, A_t=a \right] \\\\ \hphantom{v_\pi(s, a)} = \sum_{s^\prime} \sum_r p(s^\prime, r \mid s, a) \Big[ r + \gamma \mathbb{E}_\pi \left[ G_{t+1} \mid S_{t+1} = s^\prime \right] \Big] \\\\ \hphantom{v_\pi(s, a)} = \sum_{s^\prime} \sum_r p(s^\prime, r \mid s, a) \Big[ r + \gamma v_\pi(s^\prime) \Big], \forall s \in \mathcal{S}, a \in \mathcal{A}(s)$

這的方程描述，在 state $s$ 下採取 action $a$ 的價值，是即時 reward $r$ 與折扣後未來 state-value 的加權期望，而加權方式由 environment 的 transition probabilities $p(s^\prime, r \mid s, a)$ 所決定。

最佳策略（Optimal Policy）

解決 RL 任務是指，發現一個能長期獲得大量 reward 的 policy。對於 finite MDP，我們可以精確地定義一個最佳策略（optimal policy）。Value functions 對策略定義一個部分排序。若在所有的 states 下，一個 policy $\pi$ 的 expected return 都大於或等於另一個 policy $\pi^\prime$ ，則policy $\pi$ 被定義為比 policy $\pi^\prime$ 較好或一樣好。

$\pi \ge \pi^\prime \text{ if and only if } v_\pi(s) \ge v_{\pi^\prime}(s), \forall s \in \mathcal{S}$

總是至少有一個 policy 優於或等於所有其他 policies。這就是一個 optimal policy。雖然有可以多於一個 optimal policy，我們還是將所有的 optimal policies 記作 $\pi_*$ 。

這些 optimal policies 有相同的 state-value function，稱為最佳狀態價值函數（optimal state-value function），記作 $v_*$ 。

$\displaystyle v_*(s) \doteq \max_{\pi} v_\pi(s), \forall s \in \mathcal{S}$

它們也有相同的 action-value function，稱為最佳動作價值函數（optimal action-value function），記作 $q_*$ 。

$\displaystyle q_*(s, a) \doteq \max_{\pi} q_\pi (s, a), \forall s \in \mathcal{S}, a \in \mathcal{A}(s)$

貝爾曼最佳方程（Bellman Optimality Equation）

最佳狀態價值函數（Optimal State-Value Function）的貝爾曼最佳方程（Bellman Optimality Equation）

在 optimal policy $\pi_*$ 下，optimal state-value function $v_*$ 可以寫成如下的遞迴形式：

$\displaystyle v_*(s)=\max_{a \in \mathcal{A}(s)} q_* (s, a) \\\\ \hphantom{v_*(s)} = \max_a \mathbb{E}_{\pi_*} \left[ G_t \mid S_t=s, A_t=a \right] \\\\ \hphantom{v_*(s)} = \max_a \mathbb{E}_{\pi_*} \left[ R_{t+1} + \gamma G_{t+1} \mid S_t=s, A_t=a \right] \\\\ \hphantom{v_*(s)} = \max_a \mathbb{E} \left[ R_{t+1} + \gamma v_*(S_{t+1}) \mid S_t=s, A_t=a \right] \\\\ \hphantom{v_*(s)} = \max_a \sum_{s^\prime, r} p(s^\prime, r \mid s, a) \left[ r + \gamma v_*(s^\prime) \right]$

其中 $\displaystyle \max_a$ 表示，在每個 state 中，都挑選能使價值最大化的 action，這反映 optimal policy 的本質。這就是 $v_*$ 的貝爾曼最佳方程（Bellman Optimality Equation）。

最佳動作價值函數（Optimal Action-Value Function）的貝爾曼最佳方程（Bellman Optimality Equation）

在 optimal policy $\pi_*$ 下，optimal action-value function $q_*$ 可以寫成如下的遞迴形式

$\displaystyle q_*(s, a) = \mathbb{E} \left[ R_{t+1} + \gamma \max_{a^\prime} q_*(S_{t+1}, a^\prime) \mid S_t=s, A_t=a \right] \\\\ \hphantom{q_*(s, a)} = \sum_{s^\prime, r} p(s^\prime, r \mid s, a) \left[ r + \gamma \max_{a^\prime} q_*(s^\prime, a^\prime) \right]$

這就是 $q_*$ 的 Bellman optimality equation。

結論

MDP 為 RL 中的決策問題提供了一套精確、可操作的數學描述，使我們得以定義 policies、衡量 policies 的長期表現，並進一步比較不同 policies 的優劣。後續的控制問題與最佳策略搜尋，所有方法最終都可追溯至 MDP 中的這一組核心定義。

參考

Adam White and Martha White. Reinforcement Learning Specialization. University of Alberta and Coursera.
Richard S. Sutton and Andrew G. Barto. 2020. Reinforcement Learning: An Introduction, 2^nd. The MIT Press.

馬可夫決策過程（Markov Decision Process, MDP）

Share

Table of Contents