帶你讀《強化學習：原理與Python實作》之二：Markov決策過程

點選檢視第一章 點選檢視第三章

第2章

Markov決策過程

本章介紹強化學習最經典、最重要的數學模型—Markov決策過程（Markov Decision Process，MDP）。首先我們從離散時間智能體/環境接口引入Markov決策過程的定義，然後介紹在求解Markov決策過程時會用到的重要性質，最後介紹一種求解Markov決策過程最優政策的方法。

2.1　Markov決策過程模型

在智能體/環境接口中，智能體可以向環境發送動作，并從環境得到狀态和獎勵資訊。本節将從離散時間的智能體/環境接口出發導出離散時間Markov決策過程模型，并介紹離散時間Markov決策過程模型的關鍵數學概念。

2.1.1　離散時間Markov決策過程

離散時間Markov決策過程模型可以在離散時間的智能體/環境接口的基礎上進一步引入具有Markov性的機率模型得到。首先我們來回顧上一章提到的離散時間智能體/環境接口。

在離散時間智能體/環境接口中，智能體和環境互動的時刻為{0,1,2,3，...}。在時刻t，依次發生以下事情。

• 智能體觀察狀态

  

  的環境，得到觀測

  

  ，其中是

  

  ,

  

  狀态空間（state space），表示狀态取值的綜合；

  

  是觀測空間（observation space），表示觀測取值的集合。
• 智能體根據觀測決定做出動作

  

  ，其中

  

  是動作集合。
• 環境根據智能體的動作，給予智能體獎勵

  

  ，并進入下一步的狀态

  

  。其中

  

  是獎勵空間（reward space），表示獎勵取值的集合，它是實數集R的子集。

在運作過程中，每一步的可能取值範圍不同。很多時候，這是由于在不同觀測下可選的動作集合可能不同造成的。為了分析友善，往往用一個包括所有可能動作的更大的集合來表示，使得每一步的動作集合在數學上可以用同樣的字母表示。

注意：

① 不同的文獻可能會用不同的數學記号。例如，有些文獻會将動作

後得到的獎賞記為

，而本書記為

。本書采用這樣的字母是考慮到

和

往往是同時确定的。

② 這裡的離散時間并不一定是間隔相同或是間隔預先設定好的時間。這裡的離散時間名額隻是表示決策和動作的名額。

一個時間離散化的智能體/環境接口可以用這樣的軌道（trajectory）表示：

對于回合制的任務，可能會有一個終止狀态。終止狀态和其他普通的狀态有着本質的不同：當達到終止狀态時，回合結束，不再有任何觀測或動作。是以，狀态空間裡的狀态不包括終止狀态。在回合制任務中，為了強調終止狀态的存在，會将含有終止狀态的狀态空間記為

。回合制任務的軌道形式是：

其中T是達到終止狀态的步數。

注意：回合制任務中一個回合的步數是一個随機變量。它在随機過程中可以視為一個停時（stop time）。

在時間離散化的智能體/環境中，如果智能體可以完全觀察到環境的狀态，則稱環境是完全可觀測的。這時，不失一般性地，可以令

，完全可觀測任務的軌道可以簡化為：

這樣就不需要再使用字母

了。

注意：智能體/環境接口沒有假設狀态是完全可觀測的。部分不完全可觀測的問題可以模組化為部分可觀測的Markov決策過程（Partially Observable Markov Decision Process，POMDP），并用相應方法求解。

在上述基礎上進一步引入機率和Markov性，就可以得到Markov決策過程模型。定義在時間t，從狀态

和動作

跳轉到下一狀态

和獎勵

的機率為：

引入這一概念，我們就得到了Markov決策過程模型。值得一提的是，這樣的機率假設認為獎勵

和下一狀态

僅僅依賴于目前的狀态

，而不依賴于更早的狀态和動作。這樣的性質稱為Markov性。Markov性是Markov決策過程模型對狀态的額外限制，它要求狀态必須含有可能對未來産生影響的所有過去資訊。

注意：智能體/環境接口沒有假設狀态滿足Markov性。Markov性是Markov決策過程的特點。另外，有時也能從不滿足Markov性的觀測中構造滿足Markov性的狀态，或者去學習Markov性。

如果狀态空間S、動作空間A、獎勵空間R都是元素個數有限的集合，這樣的Markov決策過程稱為有限Markov決策過程（Finite Markov Decision Process，Finite MDP）。

2.1.2　環境與動力

Markov決策過程的環境由動力刻畫。本節介紹動力的定義和導出量。

對于有限Markov決策過程，可以定義函數

為Markov決策過程的動力（dynamics）：

函數中間的豎線“|”取材于條件機率中間的豎線。

利用動力的定義，可以得到以下其他導出量。

• 狀态轉移機率：

  

• 給定“狀态–動作”的期望獎勵：

  

• 給定“狀态–動作–下一狀态”的期望獎勵：

  

對于不是有限Markov決策過程的Markov決策過程，可以用類似的方法定義動力函數與導出量，隻是定義時應當使用機率分布函數。動力的定義将離散空間的情況和連續空間的情況用統一的字母表示，簡化了書寫。

我們來看一個有限Markov決策過程的例子：某個任務的狀态空間為

，動作空間為

，獎勵空間為

，轉移機率由表2-1定義。

該Markov決策過程可以用狀态轉移圖（見圖2-1）表示。

2.1.3　智能體與政策

如前所述，智能體根據其觀測決定其行為。在Markov決策過程中，定義政策（policy）為從狀态到動作的轉移機率。對于有限Markov決策過程，其政策

可以定義為

對于動作集為連續的情況，可以用機率分布來定義政策。

如果某個政策

對于任意的

，均存在一個

，使得

則這樣的政策被稱為确定性政策。這個政策可以簡記為

，即

。

例如，對于表2-1的環境，某個智能體可以采用表2-2中的政策。

2.1.4　獎勵、回報與價值函數

在第1章中已經介紹過，強化學習的核心概念是獎勵，強化學習的目标是最大化長期的獎勵。本節就來定義這個長期的獎勵。

對于回合制任務，假設某一回合在第T步達到終止狀态，則從步驟t（t回報（return）

可以定義為未來獎勵的和：

注意：在上式中，是一個确定性的變量，而回合的步數是一個随機變量。是以，在的定義式中，不僅每一項是随機變量，而且含有的項數也是随機變量。

對于連續性任務，上述的定義會帶來一些麻煩。由于連續性的任務沒有終止時間，是以會包括時刻以後所有的獎勵資訊。但是，如果對未來的獎勵資訊簡單求和，那麼未來獎勵資訊的總和往往是無窮大。為了解決這一問題，引入了折扣（discount）這一概念，進而定義回報為：

其中折扣因子

。折扣因子決定了如何在最近的獎勵和未來的獎勵間進行折中：未來

步後得到的1機關獎勵相當于現在得到的

機關獎勵。若指定

，智能體會隻考慮眼前利益，完全無視遠期利益，就相當于貪心算法的效果；若指定

，智能體會認為目前的1機關獎勵和未來的1機關獎勵是一樣重要的。對于連續性任務，一般設定

。這時，如果未來每一步的獎勵有界，則回報也是有界的。

注意：有些文獻為連續性任務定義了平均獎勵（average reward）。平均獎勵的定義為

，是對除以步數的期望求極限的結果。還有文獻會進一步定義相對于平均獎勵的回報，即讓每一步的獎勵都減去平均獎勵後再求回報。

基于回報的定義，可以進一步定義價值函數（value function）。對于給定的政策

，可以定義以下價值函數。

• 狀态價值函數（state value function）：狀态價值函數

  

  表示從狀态

  

  開始采用政策

  

  的預期回報。如下式所示：

  

• 動作價值函數（action value function）：動作價值函數

  

  表示在狀态

  

  采取動作

  

  後，采用政策

  

  

終止狀态

不是一個一般的狀态，終止狀态後沒有動作。為了在數學上有統一的形式，一般定義，

例如，對于表2-1和表2-2的例子，有：

下一節将為給定的動力和政策計算價值函數。

2.2　Bellman期望方程

2.1節定義了政策和價值函數。政策評估（policy evaluation）則是試圖求解給定政策的價值函數。本節将介紹價值函數的性質—Bellman期望方程（Bellman Expectation Equations）。Bellman期望方程常用來進行政策評估。

Bellman期望方程刻畫了狀态價值函數和動作價值函數之間的關系。該方程由以下兩部分組成。

• 用t時刻的動作價值函數表示時刻的狀态價值函數：

  

（推導：對任一狀态

，有

這樣就得到了結果。）如果用空心圓圈代表狀态，實心圓圈表示狀态–動作對，則用動作價值函數表示狀态價值函數的過程可以用備份圖（backup diagram）表示，見圖2-2a。

• 用t+1時刻的狀态價值函數表示時刻的動作價值函數：

  

（推導：對任意的狀态

其中

用到了Markov性。利用上式，有

這樣就得到了結果。）用狀态價值函數表示動作價值函數可以用備份圖表示，見圖2-2b。

上述Bellman期望方程刻畫了狀态價值函數和動作價值函數之間的關系。在上式中，也可以用代入法消除其中一種價值函數，得到以下兩種結果。

• 用狀态價值函數表示狀态價值函數，備份圖見圖2-3a：

  

• 用動作價值函數表示動作價值函數，備份圖見圖2-3b：

  

例如，對于表2-1和表2-2的例子中，狀态價值函數和動作價值函數有以下關系：

用這個方程可以求得價值函數。

接下來示範如何通過sympy求解Bellman方程，尋找最優政策。不失一般性，假設

由于這個方程組是含有字母的線性方程組，我們用sympy的solve_linear_system() 函數來求解它。solve_linear_system() 函數可以接受整理成标準形式的線性方程組，它有以下參數：

• 矩陣參數system。對于有n個等式、m個待求變量的線性方程組，system是一個n*(m+1)的sympy.Matrix對象。
• 可變清單參數symbols。若有m個待求變量的線性方程組，則symbols是m個sympy.Symbol對象。
• 可變關鍵字參數flags。

該函數傳回一個dict，為每個待求變量給出結果。

我們把待求的Bellman期望方程整理成标準形式的線性方程組，得到：

用代碼清單2-1可以求解上述方程。

代碼清單2-1求得的狀态價值函數和動作價值函數為：

2.3　最優政策及其性質

前一節我們為政策定義了價值函數。價值函數實際上給出了政策的一個偏序關系：對于兩個政策

，如果對于任意

，都

，則稱政策

小于等于

，記作

。本節将基于這個偏序關系來定義最優政策，并考慮最優政策的性質和求解。

2.3.1　最優政策與最優價值函數

• 對于一個動力而言，總是存在着一個政策，使得所有的政策都小于等于這個政策。這時，政策

  

  就稱為最優政策（optimal policy）。最優政策的價值函數稱為最優價值函數。最優價值函數包括以下兩種形式。
• 最優狀态價值函數（optimal state value function），即

  

• 最優動作價值函數（optimal action value function），即

  

對于一個動力，可能存在多個最優政策。事實上，這些最優政策總是有相同的價值函數。是以，對于同時存在多個最優政策的情況，任取一個最優政策來考察不失一般性。其中一種選取方法是選擇這樣的确定性政策：

其中，如果有多個動作

使得

取得最大值，則任選一個動作即可。從這個角度看，隻要求得了最優價值函數，就可以直接得到一個最優政策。是以，求解最優價值函數是一個值得關注的重要問題。

2.3.2　Bellman最優方程

最優價值函數具有一個重要的性質—Bellman最優方程（Bellman optimal equation）。Bellman最優方程可以用于求解最優價值函數。

回顧2.2節，政策的價值函數滿足Bellman期望方程，最優價值函數也是如此。與此同時，将最優函數的性質：

代入Bellman期望方程，就可以得到Bellman最優方程。

Bellman最優方程有以下兩個部分。

• 用最優動作價值函數表示最優狀态價值函數，備份圖見圖2-4a：

  

• 用最優狀态價值函數表示最優動作價值函數，備份圖見圖2-4b：

  

基于最優狀态價值函數和最優動作價值函數互相表示的形式，可以進一步導出以下兩種形式。

• 用最優狀态價值函數表示最優狀态價值函數，備份圖見圖2-5a：

  

• 用最優動作價值函數表示最優動作價值函數，備份圖見圖2-5b：

  

例如，對于表2-1的動力系統，我們可以列出其Bellman最優方程為：

用這個方程可以求得最優價值函數。

接下來我們用sympy求解這個方程。Bellman最優方程含有max() 運算，可以通過分類讨論來化解這個max() 運算，将優化問題轉為普通線性規劃問題。如果用這種方法，可以将這個方程組分為以下4類情況讨論，用代碼清單2-2求解。

代碼清單2-2求得以下4種情況的解如下。

情況I：

且。這時

且

這種情況的求解結果為：

。此時，

可以化簡為：

情況II：

。這時

。這種情況的求解結果為：

情況III：

此時，

情況IV:

對于給定數值的情況，更常将

松弛為

，并消去

以減少決策變量，得到新的線性規劃：

是一組任意取值的正實數。Bellman最優方程的解顯然線上性規劃的可行域内。而由于

，是以線性規劃的最優解肯定會讓限制條件中的某些不等式取到等号，使得Bellman最優方程成立。可以證明，這個線性規劃的最優解滿足Bellman最優方程。

例如，在之前的例子中，如果限定

，我們用這個線性規劃求得最優狀态價值為

進而由最優狀态價值推算出最優動作價值為

2.3.3　用Bellman最優方程求解最優政策

在理論上，通過求解Bellman最優方程，就可以找到最優價值函數。一旦找到最優價值函數，就能很輕易地找到一個最優政策：對于每個狀态，總是選擇讓最大的動作。

例如，對于表2-1的動力系統，我們已經通過分類讨論求得了Bellman最優方程。那麼它的最優政策也可以通過分類讨論立即得到：

。這種情況的最優政策是

即一直不吃。

即餓了不吃，飽時吃。

即餓了吃，飽時不吃。

情況IV：

即一直吃。

對于一個特定的數值，求解則更加明顯。例如，當

，2.3.2節已經求得了最優動作價值，此時最優動作價值滿足

。是以，它對應的最優政策為

但是，實際使用Bellman最優方程求解最優政策可能會遇到下列困難。

• 難以列出Bellman最優方程。列出Bellman最優方程要求對動力系統完全了解，并且動力系統必須可以用有Markov性的Markov決策過程來模組化。在實際問題中，環境往往十分複雜，很難非常周全地用機率模型完全模組化。
• 難以求解Bellman最優方程。在實際問題中，狀态空間往往非常巨大，狀态空間和動作空間的組合更是巨大。這種情況下，沒有足夠的計算資源來求解Bellman最優方程。是以這時候會考慮采用間接的方法求解最優價值函數的值，甚至是近似值。

2.4　案例：懸崖尋路

本節考慮Gym庫中的懸崖尋路問題（CliffWalking-v0）。懸崖尋路問題是這樣一種回合制問題：在一個的網格中，智能體最開始在左下角的網格，希望移動到右下角的網格，見圖2-6。智能體每次可以在上、下、左、右這4個方向中移動一步，每移動一步會懲罰一個機關的獎勵。但是，移動有以下限制。

• 智能體不能移出網格。如果智能體想執行某個動作移出網格，那麼就讓本步智能體不移動。但是這個操作依然會懲罰一個機關的獎勵。
• 如果智能體将要到達最下一排網格（即開始網格和目标網格之間的10個網格），智能體會立即回到開始網格，并懲罰100個機關的獎勵。這10個網格可被視為“懸崖”。

當智能體移動到終點時，回合結束，回合總獎勵為各步獎勵之。

2.4.1　實驗環境使用

Gym庫中的環境'CliffWalking-v0'實作了懸崖尋路的環境。代碼清單2-3示範了如何導入這個環境并檢視這個環境的基本資訊。

這個環境是一個離散的Markov決策過程。在這個Markov決策過程中，每個狀态是取自

的int型數值（加上終止狀态則為

），表示目前智能體在圖2-6中對應的位置上。動作是取自

的int型數值：0表示向上，1表示向右，2表示向下，3表示向左。獎勵取自

，遇到懸崖為-100，否則為-1。

代碼清單2-4給出了用給出的政策運作一個回合的代碼。函數play_once() 有兩個參數，一個是環境對象，另外一個是政策policy，它是np.array類型的執行個體。

代碼清單2-5給出了一個最優政策optimal_policy。最優政策是在開始處向上，接着一路向右，然後到最右邊時向下。

下面的代碼用最優政策運作一個回合。采用最優政策，從開始網格到目标網格一共要移動13步，回合總獎勵為-13。

2.4.2　求解Bellman期望方程

接下來考慮政策評估。我們用Bellman期望方程求解給定政策的狀态價值和動作價值。首先來看狀态價值。用狀态價值表示狀态價值的Bellmn期望方程為：

這是一個線性方程組，其标準形式為：

得到标準形式後就可以調用相關函數直接求解。得到狀态價值函數後，可以用狀态價值表示動作價值的Bellan期望方程：

來求動作價值函數。

代碼清單2-6中的函數evaluate_bellman()實作了上述功能。狀态價值求解部分用np.linalg.solve()函數求解标準形式的線性方程組。得到狀态價值後，直接計算得到動作價值。

接下來我們用代碼清單2-6中的evaluate_bellman()函數評估給出的政策。代碼清單2-7和代碼清單2-8分别評估了一個随機政策和最優确定性政策，并輸出了狀态價值函數和動作價值函數。

2.4.3　求解Bellman最優方程

對于懸崖尋路這樣的數值環境，可以使用線性規劃求解。線性規劃問題的标準形式為：

其中目标函數中狀态價值的系數已經被固定為1。也可以選擇其他正實數作為系數。

代碼清單2-9使用scipy.optimize.linprog() 函數來計算這個動态規劃問題。這個函數的第0個參數是目标函數中各決策變量在目标函數中的系數，本例中都取1；第1個和第2個參數是形如“Ax<=b”這樣的不等式限制的A和b的值。函數optimal_bellman() 剛開始就計算得到這些值。scipy.optimize.linprog() 還有關鍵字參數bounds，指定決策變量是否為有界的。本例中，決策變量都是無界的。無界也要顯式指定，不可以忽略。還有關鍵字參數method确定優化方法。預設的優化方法不能處理不等式限制，這裡選擇了能夠處理不等式限制的内點法（interior-point method）。

求得最優動作價值後，可以用argmax計算出最優确定政策，代碼清單2-10給出了從最優動作價值函數計算最優确定政策的代碼。運作結果表明，計算得到的最優政策就是代碼清單2-5給出的政策。

2.5　本章小結

本章介紹了強化學習最重要的數學模型：Markov決策模型。Markov決策模型用動力系統來描述環境，用政策來描述智能體。本章還介紹了政策的價值函數和最優政策的最優價值函數。理論上，價值函數和最優價值函數可以通過Bellman期望方程和Bellman最優方程求解。但是在實際問題中，Bellman期望方程和Bellman最優方程往往難以獲得或難以求解。在後續的章節中，将給出解決這些問題的方法。

本章要點

在完全可觀測的離散時間智能體/環境接口中引入機率和Markov性，可以得到Markov決策過程。

在Markov決策過程中，

是狀态空間（包括終止狀态

的狀态空間為

），A是動作空間，R是獎勵空間，p是動力。

表示從狀态s和動作a到狀态

和獎勵r的轉移機率。

是政策。

表示在狀态s決定執行動作a的機率。

回報是未來獎勵的和，獎勵按折扣因子

進行折扣。

對于一個政策

，在某個狀态s下的期望回報稱為狀态價值

，在某個狀态動作對

下的期望回報稱為動作價值

狀态價值和動作價值滿足Bellman期望方程：

用狀态價值函數可以定義政策的偏序關系。對于一個環境，如果所有政策都小于等于某個政策

，則稱

是一個最優政策。

任何環境都存在最優政策。一個環境的所有最優政策有着相同的狀态價值和動作價值，分别稱為最優狀态價值（記為

）和最優動作價值（記為

）。

最優狀态價值和最優動作價值滿足Bellman最優方程：

可以應用下列線性規劃求解最優動作價值：

用Bellman最優方程求解出最優價值後，可以用

确定出一個确定性的最優政策。其中，對于某個

，如果有多個動作

值使得

取得最大值，則任選一個動作即可。