馬可夫決策過程

在數學中，馬可夫決策過程（英語：Markov decision process，MDP）是離散時間隨機控制過程。 它提供了一個數學框架，用於在結果部分隨機且部分受決策者控制的情況下對決策建模。 MDP對於研究通過動態規劃解決的最佳化問題很有用。 MDP至少早在1950年代就已為人所知；^[1] 一個對馬可夫決策過程的核心研究是 羅納德·霍華德（英語：Ronald A. Howard）於1960年出版的《動態規劃和馬可夫過程》^[2]。 它們被用於許多領域，包括機械人學，自動化，經濟學和製造業。 MDP的名稱來自俄羅斯數學家安德雷·馬可夫，因為它們是馬可夫鏈的推廣。

在每個時間步驟中，隨機過程都處於某種狀態${\displaystyle s}$，決策者可以選擇在狀態${\displaystyle s}$下可用的動作${\displaystyle a}$。 該隨機過程在下一時間步驟會隨機進入新狀態${\displaystyle s'}$，並給予決策者相應的回饋${\displaystyle R_{a}(s,s')}$。

隨機過程進入新狀態${\displaystyle s'}$的概率受所選操作影響。 具體來說，它是由狀態轉換函數${\displaystyle P_{a}(s,s')}$給出的。 因此，下一個狀態${\displaystyle s'}$取決於當前狀態${\displaystyle s}$和決策者的動作${\displaystyle a}$。 但是給定${\displaystyle s}$和${\displaystyle a}$，它條件獨立於所有先前的狀態和動作； 換句話說，MDP的狀態轉換滿足馬可夫性質。

馬可夫決策過程是馬可夫鏈的推廣，不同之處在於添加了行動（允許選擇）和獎勵（給予動機）。反過來說，如果每個狀態只存在一個操作和所有的獎勵都是一樣的，一個馬可夫決策過程可以歸結為一個馬可夫鏈。

定義

一個簡單的MDP示例，包含三個狀態（綠色圓圈）和兩個動作（橙色圓圈），以及兩個獎勵（橙色箭頭）

馬可夫決策過程是一個4元組${\displaystyle (S,A,P_{a},R_{a})}$，其中:

• ${\displaystyle S}$是狀態空間的集合，
• ${\displaystyle A}$是動作的集合，也被稱為動作空間（比如說${\displaystyle A_{s}}$是狀態${\displaystyle s}$中可用的動作集合），
• ${\displaystyle P_{a}(s,s')=\Pr(s_{t+1}=s'\mid s_{t}=s,a_{t}=a)}$是${\displaystyle t}$時刻${\displaystyle s}$狀態下的動作${\displaystyle a}$導致${\displaystyle t+1}$時刻進入狀態${\displaystyle s'}$的概率，
• ${\displaystyle R_{a}(s,s')}$狀態${\displaystyle s}$經過動作${\displaystyle a}$轉換到狀態${\displaystyle s'}$後收到的即時獎勵（或預期的即時獎勵）。

狀態和行動空間可能是有限的，也可能是無限的。一些具有可數無限狀態和行動空間的過程可以簡化為具有有限狀態和行動空間的過程。^[3]

策略函數${\displaystyle \pi }$是從狀態空間（${\displaystyle S}$）到動作空間（${\displaystyle A}$）的（潛在概率）映射。

優化目標

馬可夫決策過程的目標是為決策者找到一個好的「策略」：一個函數${\displaystyle \pi }$，它指定決策者在狀態${\displaystyle s}$時將選擇的動作${\displaystyle \pi (s)}$。一旦以這種方式將馬可夫決策過程與策略組合在一起，就可以確定在每個狀態的動作，並且生成的組合行為類似於馬可夫鏈（因為在狀態${\displaystyle s}$的動作都由${\displaystyle \pi (s)}$決定，${\displaystyle \Pr(s_{t+1}=s'\mid s_{t}=s,a_{t}=a)}$簡化為${\displaystyle \Pr(s_{t+1}=s'\mid s_{t}=s)}$，成為一個馬可夫轉移矩陣）。

目標是選擇一個策略${\displaystyle \pi }$，使隨機獎勵的累積函數最大化，通常是在潛在的無限範圍內的預期貼現總和:

${\displaystyle E\left[\sum _{t=0}^{\infty }{\gamma ^{t}R_{a_{t}}(s_{t},s_{t+1})}\right]}$（我們選擇${\displaystyle a_{t}=\pi (s_{t})}$也就是策略給出的動作）。並且期望值為${\displaystyle s_{t+1}\sim P_{a_{t}}(s_{t},s_{t+1})}$。

其中${\displaystyle \ \gamma \ }$是折現因子，滿足${\displaystyle 0\leq \ \gamma \ \leq \ 1}$，通常接近於1（例如，對於貼現率r，存在${\displaystyle \gamma =1/(1+r)}$）。較低的折扣率促使決策者傾向於儘早採取行動，而不是無限期地推遲行動。

使上述函數最大化的策略稱為最優策略，通常用${\displaystyle \pi ^{*}}$表示。一個特定的MDP可能有多個不同的最佳策略。由於馬可夫決策過程的性質，可以證明最優策略是當前狀態的函數，就像上面所敘述的那樣。

模擬模型

在許多情況下，很難明確地表示轉移概率分佈${\displaystyle P_{a}(s,s')}$。在這種情況下，可以使用模擬器通過提供來自轉換發行版的示例來隱式地對MDP建模。隱式MDP模型的一種常見形式是情景環境模擬器，它可以從初始狀態啟動，生成後續狀態，並在每次接收到操作輸入時給予獎勵。通過這種方式，我們可以模擬出目標經過的狀態、採取的行動以及獲得的獎勵（統稱「軌跡」）。

另一種形式的模擬器是生成模型，即能夠生成下一個狀態的樣本並提供所有狀態和行動獎勵的單步驟模擬器。^[4]在用偽代碼表示的算法中，${\displaystyle G}$通常用來表示生成模型。例如，表達式${\displaystyle s',r\gets G(s,a)}$可以表示從生成模型中取樣的動作，其中${\displaystyle s}$和${\displaystyle a}$是當前狀態和動作，${\displaystyle s'}$和${\displaystyle r}$是下一步的狀態和獎勵。與情景模擬器相比，生成模型的優勢在於它可以從任何狀態獲取數據，而不僅僅是在軌跡中遇到的狀態。

這些模型類形成了資訊內容的層次結構：顯式模型通過從分佈中採樣簡單地生成生成模型，並且生成模型的重複應用生成軌跡模擬器。在相反的方向上，只能通過迴歸分析研究近似模型。可用於特定MDP的模型類型在確定哪種解決方案算法合適方面起着重要作用。例如，下一節中描述的動態規劃算法需要一個顯式模型，而蒙地卡羅樹搜尋需要一個生成模型（或可以在任何狀態下複製的情景模擬器），而大多數強化學習算法只需要一個軌跡模擬器 。

算法

可以通過各種方法（例如動態規劃）找到具有有限狀態和動作空間的MDP的解決方案。本節中的算法適用於具有有限狀態和動作空間並明確給出轉移概率和獎勵函數的MDP，但基本概念可以擴展到處理其他問題類別，例如使用函數趨近。

為有限狀態和動作MDP計算最優策略的標準算法系列需要存儲兩個按狀態索引的數列：第一個數列是${\displaystyle V}$，用來儲存實數，以及策略${\displaystyle \pi }$，用來存動作。在算法結束時，${\displaystyle \pi }$將存儲每一個狀態時的解決方案，而${\displaystyle V(s)}$將存儲從狀態${\displaystyle s}$遵循該解決方案獲得的獎勵的折扣總和（平均）。

${\displaystyle V(s):=\sum _{s'}P_{\pi (s)}(s,s')\left(R_{\pi (s)}(s,s')+\gamma V(s')\right)}$

${\displaystyle \pi (s):={\underset {a}{\operatorname {arg\,min} }}\left\{\sum _{s'}P(s'\mid s,a)\left(R(s'\mid s,a)+\gamma V(s')\right)\right\}}$

它們的順序取決於你所採用的算法的變體，可以一次或逐個狀態地對所有狀態執行它們，並且對某些狀態比其他狀態更頻繁。 只要沒有狀態被永久排除在任何一個步驟之外，算法最終將得出正確的解決方案。^[5]

著名的變體

數值迭代

數值迭代也稱為反向歸納，不使用${\displaystyle \pi }$函數.相反，${\displaystyle \pi (s)}$的值在需要時在${\displaystyle V(s)}$內計算。 將${\displaystyle \pi (s)}$的計算代入${\displaystyle V(s)}$的計算得出組合步驟：

${\displaystyle V_{i+1}(s):=\max _{a}\left\{\sum _{s'}P_{a}(s'|s)\left(R_{a}(s,s')+\gamma V_{i}(s')\right)\right\},}$

其中${\displaystyle i}$是迭代數，值迭代從${\displaystyle i=0}$和${\displaystyle V_{0}}$開始，作為價值函數的猜測。

參見

• 馬可夫鏈
• 半馬可夫過程
• 隨機漫步
• 布朗運動
• 馬可夫模型
• 隱馬爾可夫模型
• 學習自動機
• 部分可觀察馬可夫決策過程

參考文獻

1. Bellman, R. A Markovian Decision Process. Journal of Mathematics and Mechanics. 1957, 6 (5): 679–684 [2021-04-30]. JSTOR 24900506. （原始內容存檔於2021-04-30）. （頁面存檔備份，存於互聯網檔案館）
2. Howard, Ronald A. Dynamic Programming and Markov Processes (PDF). The M.I.T. Press. 1960 [2021-04-30]. （原始內容存檔 (PDF)於2011-10-09）. （頁面存檔備份，存於互聯網檔案館）
3. Wrobel, A. On Markovian Decision Models with a Finite Skeleton. Mathematical Methods of Operations Research (ZOR). 1984, 28 (February): 17–27. S2CID 2545336. doi:10.1007/bf01919083.
4. Kearns, Michael; Mansour, Yishay; Ng, Andrew. A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes. Machine Learning. 2002, 49 (193–208): 193–208. doi:10.1023/A:1017932429737 .
5. Reinforcement Learning: Theory and Python Implementation. Beijing: China Machine Press. 2019: 44. ISBN 9787111631774.

• Yosida, K. 「Functional Analysis」, Ch XIII, § 3, Springer-Verlag, 1968. ISBN 3-540-58654-7
• Ribarič.M. and I.Vidav, 「An inequality for concave functions.」 Glasnik Matematički 8 (28), 183–186 (1973).

外部連結

• 埃里克·韋斯坦因. Markov process. MathWorld.