強化學習 - 有限馬爾科夫模型

目錄

• • “智能體-環境”互動接口
  • 目标和收益
  • 回報和分幕
  • 分幕式和持續性任務的統一表示法
  • 政策和價值函數
  • 最優政策和最優價值函數
  • 最優性和近似算法
  • 例子，GridWorld問題

有限馬爾可夫決策過程（有限MDP問題）既涉及“評估性回報”，又涉及“發散聯想”，即在不同情境下選擇不同的動作。MDP是序列決策的經典形式化表達，其動作不僅影響目前的即時收益，還影響後續的情境（又稱狀态）以及未來的收益。是以，MDP涉及了延遲收益，由此也就有了在目前收益和延遲收益之間權衡的需求。

在賭博機問題中，我們估計了每個動作a的價值 q ∗ ( a ) q_*(a) q∗​(a)，而在MDP中，每個動作 a a a在每個狀态s中的價值 q ∗ ( s , a ) q_*(s,a) q∗​(s,a)，或者估計給定最有動作下的每個狀态的價值 v ∗ ( s ) v_*(s) v∗​(s)。

“智能體-環境”互動接口

MDP是一種通過互動式學習來實作目标的理論架構。進行學習及實施決策的機器被稱為智能體（agent）。與之互相作用的事物都被稱為環境（environment）。事物之間持續互動，智能體選擇動作，環境對這些動作做出響應，并向智能體呈現出新的狀态。而環境也會産生收益，通常是特定的數值，這就是智能體在動作選擇過程中想要最大化的目标。

在每個離散時刻t = 0,1,2,3,…,（會有連續的情況）， 智能體和環境都發生了互動。 S t ∈ S S_t∈S St​∈S，選擇一個動作， A t ∈ A ( s ) A_t∈A(s) At​∈A(s)。然後在下一時刻，作為其動作的結果，智能體接收到一個數值化， R t + 1 ∈ R R_{t+1}∈R Rt+1​∈R，然後進入一個新的狀态 S t + 1 S_{t+1} St+1​。最後MDP和智能體共同給出了序列或者說軌迹。 S 0 , A 0 , R 1 , S 1 , A 1 , R 2 , A 2 , R 3 , . . . S_0,A_0,R_1,S_1,A_1,R_2,A_2,R_3,... S0​,A0​,R1​,S1​,A1​,R2​,A2​,R3​,...

在有限MDP中，狀态、動作和收益的集合(S、A和R)都隻有有限個元素。在這種情況下，随機變量 R t R_t Rt​和 S t S_t St​具有定義明确的離散機率分布，并且隻依賴于前繼狀态和動作，換言之，給定前繼狀态和動作的值時， s ′ ∈ S s'∈S s′∈S和 r ∈ R r∈R r∈R，在t時刻出現的機率是

對于任意 s ′ , s ∈ S ， r ∈ R s',s∈S，r∈R s′,s∈S，r∈R，以及 a ∈ A ( s ) a∈A(s) a∈A(s)。函數p定義了MDP的動态特性。動态函數 p : S ∗ R ∗ S ∗ A − > [ 0 , 1 ] p:S*R*S*A->[0,1] p:S∗R∗S∗A−>[0,1]是有4個參數的普通的确定性函數。中間“|”表示條件機率的符号，函數 p p p為每個 s s s和 a a a的選擇都指定了一個機率分布，即：

在馬爾科夫決策過程中，由 p p p給出的機率完全刻畫了環境的動态特性。St和Rt的每個可能的值出現的機率隻取決于前一個狀态 S t − 1 S_{t-1} St−1​和前一個動作 A t − 1 A_{t-1} At−1​，并且與更早之前的狀态和動作完全無關。這個限制并不是針對決策過程，而是針對狀态的。狀态必須包括過去智能體和環境互動的方方面面的資訊，這些資訊會對未來産生一定影響。這樣，狀态就被認為具有馬爾科夫性。

從四參數動态函數 p p p中，我們可以計算出關于環境的任何資訊，例如狀态轉移機率（我們将其表示為一個三參數函數 p ： S ∗ S ∗ A − > [ 0 , 1 ] p：S*S*A->[0,1] p：S∗S∗A−>[0,1]）

我們還可以定義“狀态-動作”二進制組的期望收益，将其表示為一個雙參數函數 r ： S ∗ A − > R r：S*A->R r：S∗A−>R：

和“狀态-動作-後繼狀态”三元組的期望收益，并将其表示為一個三參數函數 r : S ∗ A ∗ S − > R r:S*A*S->R r:S∗A∗S−>R

MDP架構非常靈活，能以不同的方式應用到許多實際問題中。

例如，時間步長不需要真實時間的固定間隔，也可以是決策和行動的任意的連貫階段。動作可以是低級的控制，例如機器臂的發動機的電壓，也可以是進階的決策，例如是否吃午餐。同樣地，狀态可以采取多種表述形式，例如傳感器的直接讀數。狀态的一些組成成分可以是基于過去感覺的記憶，甚至可以是完全主觀的。例如，智能體可能不确定對象位置，也可能剛剛響應過某種特定的感覺。類似地，一些動作可能是完全主觀或完全可計算的。例如，一些動作可以控制智能體選擇考慮的内容，或者控制它把注意力集中在哪裡，一般而言，動作可以是我們想要做的決策，而狀态則可以使對決策有所幫助的事情。

MDP架構是目标導向的互動式學習問題的一個高度抽象。任何目标導向的行為的學習問題都可以概括為智能體及其環境之間來回傳遞的三個信号：

（1）用來表示智能體做出的選擇（行動）

（2）一個信号用來表示做出該選擇的基礎（狀态）

（3）定義智能體的目标（收益）

目标和收益

在強化學習中，智能體的目标呗形式化表征為一種特殊信号，稱為收益，它通過環境傳遞給智能體。在每個時刻，收益都是一個單一标量數值， R t ∈ R R_t∈R Rt​∈R。非正式地說，智能體的目标是最大化所收到的總收益。這意味着需要最大化的不是目前收益，而是長期的累計收益。使用收益信号來形式化目标是強化學習最顯著的特征之一。

智能體總是學習如何最大化收益。如果我們想要它為我們做某件事，我們提供收益的方式必須要使得智能體在最大化收益的同時，也實作我們的目标。此外，收益信号并不是傳授智能體如何實作目标的先驗知識。例如，國際象棋智能體隻有當最終獲勝時才能獲得收益，而非達到某個子目标，比如吃掉對方的子，或者控制中心區域。如果實作這些子目标也能得到收益，那麼智能體可能會避開最終目的，來實作子目标。比如為了吃對手的子，輸掉了比賽也沒關系。是以收益信号隻能用來傳達什麼是你想要實作的目标，而不是如何實作目标。

回報和分幕

智能體的目标是最大限度地提高長期收益。那應該怎樣正式定義？如果把時刻t後接收的收益序清單示為 R t + 1 ， R t + 2 ， R t + 3 ， . . . ， R_{t+1}，R_{t+2}，R_{t+3}，...， Rt+1​，Rt+2​，Rt+3​，...，那麼最大化這個序列的那一方面？一般來說，我們尋求的是最大化期望回報，記為 G t G_t Gt​，它被定義為收益序列的一些特定函數。在最簡單的情況下，回報是收益的總和：

其中T是最終時刻。在有“最終時刻”的應用中，智能體和環境的互動能被自然地分成一系列子序列（每個序列都存在最終時刻），我們稱每個子序列為幕（episodes，或者是試驗，trials），也可以感性地認識為一段情節，并且上一幕和下一幕并無關聯。在這些分幕式任務中，我們需要區分非終結狀态集合，記為S，和包含終結與非終結狀态的所有狀态集，記作S+。終結的時間T是一個随機變量，通常随着幕的不同而不同。

另一方面，在許多情況下，智能體-環境互動不一定能被自然地分為單獨的幕，而是持續不斷地發生。比如一個連續的過程控制任務或者長期運作機器人的應用。這些一般稱為持續性任務。

使用上面的回報公式描述持續性任務會出現問題，因為最終時刻T = ∞，因為最大化的回報容易趨于無窮。是以這裡引入一個額外概念，即折扣。根據這種方法，智能體嘗試選擇動作，使得它在未來收到的經過折扣系數權重後的收益總和是最大化的。它選擇 A t A_t At​來最大化期望折後回報。

其中 r r r是一個參數， 0 ≦ r ≦ 1 0≦r≦1 0≦r≦1，被稱為折扣率。

折扣率決定了未來收益的目前價值：未來時刻 k k k的收益值隻有它的目前值的 r k − 1 r^{k-1} rk−1倍。如果 r < 1 r<1 r<1，那麼隻要收益序列{ R k R_k Rk​}有界，那麼上式的無限序列總和就是一個有限值。如果r=0，那麼智能體是“目光短淺的”，即隻關心最大化目前收益（即，選擇 A t A_t At​來最大化 R t + 1 R_{t+1} Rt+1​）。如果每個智能體的行為都碰巧隻影響目前收益，而不是未來的回報，那麼目光短淺的智能體可以通過單獨最大化每個目前收益來最大化上面的式子。但一般來說，最大化目前收益會減少未來的收益，以至于實際上的收益變少了。随着r接近1，折後回報将更多地考慮未來的收益，也就是說智能體變得有遠見了。

鄰接時刻的回報可以用如下遞歸方式互相聯系起來，這對于強化學習的理論和算法來說至關重要。

盡管上面式子中定義的回報是對無限個收益子項求和，但隻要收益是一個非零常數且r<1，那這個回報仍是有限的。比如，如果收益是一個常數+1，那麼回報就是

分幕式和持續性任務的統一表示法

分幕式任務對比持續性任務，前一種情況更容易表示，因為在這一幕，每個動作隻能影響到之後收到的有限個收益。為了能夠同時精确地讨論兩種情況，我們需要建立一個統一的表示法。

我們需要使用另一個約定來獲得一個統一符号，它可以同時适用于分幕式和持續性任務。在一種情況下，我們彙報定義為有限項的總和；而在另一種情況中，我們将回報定義為無限項的總和。這兩者可以通過一個方法進行統一，即把幕的終止當做一個特殊的吸收狀态的入口，它隻會轉移到自己并且隻産生零收益。

這裡的方塊表示與幕結束對應的吸收狀态。從 S 0 S_0 S0​開始，我們就會得到收益序列： + 1 ， + 1 ， + 1 ， 0 ， 0 ， 0... +1，+1，+1，0，0，0... +1，+1，+1，0，0，0...。此時無論我們是計算前T個收益（這裡T=3）的綜合，還是計算無限序列的全部綜合，我們都能得到相同的回報。即使我們引入折扣，這也仍然成立。是以我們可以把回報表示為：

并允許上式包括T=∞或r=1（但是兩者不能同時）的可能性。這些慣例用來簡化符号，并表達分幕式和持續性任務之間的緊密聯系。

政策和價值函數

幾乎所有的強化學習算法都涉及價值函數的計算。價值函數是狀态（或狀态與動作二進制組）的函數，用來評估目前智能體的給定狀态（或外加動作）下有多好，也就是用未來預期的收益（回報）來定義的期望值。智能體期望未來能得到的收益取決于智能體所選擇的動作。是以，價值函數是與特定的行為方式相關的，稱為政策。

政策是從狀态到每個動作的選擇機率之間的映射。如果智能體在時刻t選擇了政策π，那麼π(a|s)就是當St=s時 At=a的機率。就像p一樣，π就是一個普通的函數， π ( a ∣ s ) π(a|s) π(a∣s)中間的“|”隻是提醒我們它為每個 s ∈ S s∈S s∈S都定義了一個在 a ∈ A a∈A a∈A上的機率分布。強化學習方法規定了智能體的政策如何随着經驗而發生變化。

把政策π下狀态s的價值函數記為 v π ( s ) v_π(s) vπ​(s)，即從狀态s開始，智能體按照政策π進行決策所獲得的回報的機率期望值。對于MDP，我們可以正式定義 v π v_π vπ​為

其中， E π [ ∗ ] E_π[*] Eπ​[∗]表示在給定政策π時一個随機變量的期望值，t可以是任意時刻。請注意，終止狀态的價值始終是零。我們把函數 v π v_π vπ​稱為政策 π π π的狀态價值函數。類似地，我們把政策 π π π下載下傳狀态s時采取動作 a a a的價值記為 q π ( s , a ) q_π(s,a) qπ​(s,a)。這就是根據政策π，從狀态s開始，執行動作a之後，所有可能的決策序列的期望回報。

價值函數 v π v_π vπ​和 q π q_π qπ​都能從經驗中估算得到。比如，一個智能體遵循政策π，并且對每個遇到的狀态都記錄該狀态後的實際回報的平均值，那麼，随着狀态出現的次數接近無窮大，這個平均值會收斂到狀态價值 v π ( s ) v_π(s) vπ​(s)。如果為每個狀态的每個動作都保留單獨的平均值，那麼，随着狀态出現的次數接近無窮大，這個平均值會收斂到狀态價值 v π ( s ) v_π(s) vπ​(s)。如果為每個狀态的每個動作都保留單獨的平均值，那麼類似地，這些平均值也會收斂到動作價值 q π ( s , a ) q_π(s,a) qπ​(s,a)。我們将這種估算方法稱作蒙特卡洛方法，因為該方法涉及從真實回報的多個随機樣本中求平均值。當環境中有很多狀态時，獨立地估算每個狀态的平均值是不切實際的。此時我們可以将價值函數 v π v_π vπ​和 q π q_π qπ​參數化（參數的數量要遠少于狀态的數量），然後通過調整價值函數的參數來更好地計算回報值。

在強化學習和動态規劃中，價值函數有一個基本特性，就是滿足某種遞歸關系。對于任何政策π和任何狀态s，s的價值與其可能的後繼狀态的價值之間存在以下關系

其中，動作a取自集合A(s)，下一時刻狀态s’取自集合S（在分幕式的問題中，取自集合S+），收集值r取自集合R。上式被稱作 v π v_π vπ​的貝爾曼方程。它用等式表達了狀态價值和後繼狀态價值之間的關系，從一個狀态向後觀察所有可能到達的後繼狀态。

如上圖所示，空心圓代表狀态，而實心圓表示一個“狀态-動作”二進制組。從狀态s開始，并将其作為根節點，智能體可以根據其政策π，采取動作集合中的任意一個動作（圖中顯示了三個動作）。對每一個動作，環境會根據其動态特性函數p，以一個後繼狀态s’，及其收益r作為響應。貝爾曼方程對所有可能性采用其出現機率進行了權重平均。說明起始狀态的價值一定等于後繼狀态的（折扣）期望值加上對應的收益期望值。

貝爾曼方程是一系列計算、近似和學習 v π v_π vπ​的基礎。上圖叫回溯圖，因為圖中的關系是回溯運算的基礎，這也是強化學習方法的核心内容。通俗地講，回溯操作就是将後繼狀态的價值資訊回傳給目前時刻的狀态（或 “狀态-動作”二進制組）。

最優政策和最優價值函數

強化學習任務意味着要找出一個政策，使其能夠在長期過程中獲得大量的收益。對于有限MDP，我們通過比較價值函數精确地定義一個最優政策。本質上，價值函數定義了政策上的偏序關系。若對于 s ∈ S s∈S s∈S， π ≥ π ′ π≥π' π≥π′，那麼應當 v π ( s ) ≥ v π ′ ( s ) v_π(s)≥v_{π'}(s) vπ​(s)≥vπ′​(s)，即總會存在一個政策不劣于其他所有的測錄，就是最優政策。可以用 π ∗ π_* π∗​來表示所有這些最優政策。他們共享相同的狀态價值函數，稱為最優狀态價值函數，記為 v ∗ v_* v∗​。

最優政策下各個狀态的價值一定等于這個狀态下最優動作的期望回報，這就是貝爾曼最優方程。

而 q ∗ q_* q∗​的貝爾曼最優方程如下：

最優性和近似算法

即使我們有一個關于環境動态變化特性的完備精确模型，貝爾曼最優方程仍然不能簡單地計算出一個最優政策，例如象棋之類的棋類遊戲隻是人類經驗的一小部分，對于大型定制的計算機來說，其仍然十分複雜，以至于無法計算出最優的走棋政策。現在智能體面臨的一個關鍵問題是能用多少計算力，特别是每一步能用的計算力。

存儲容量是一個很重要的限制，價值函數、政策和模型的估計通常需要大量的存儲空間，在狀态集合小而有限的任務中，用數組或者表格估計每個狀态是有可能的。我們稱之為表格型任務，對應的方法我們稱作表格型方法。但在很多實際情況下，很多狀态不能用表格的一行來表達。在這些情況下，價值函數必須采用近似算法，這時通常使用緊湊的參數化函數表示方法。

強化學習問題是我們不得不認真面對近似的問題。例如，在近似最優行為時，智能體可能會有大量的狀态，每個狀态出現的機率都很低，這使得選擇次優的動作對整個智能體所獲得的收益的影響很小。

例子，GridWorld問題

如上圖所示是一個包含5*5的網格，在每一個單元格中，agent都有四種行動可以執行，它們分别是“上”、“下”、“左”、“右”。假設agent在每個格子處采取四種行動的機率是相同的，也就是1/4=0.25，同時未來回報的折扣因子設為0.9，而agent的狀态轉移以及回報值分為以下四種情況：

（1）如果agent在邊緣處，那麼如果它此時執行的動作使它溢出網格的話，我們限制它的位置仍然固定不變，但是同時它會得到-1的回報值。

（2）如果agent處在A點，那麼它的任意行動都将得到10的回報值，同時下一步的狀态移至A’處；

（3）如果agent處在B點，那麼它的任意行動都将得到5的回報值，同時下一步的狀态移至B’處；

（4）其他情況則會得到0的回報值，狀态轉移遵從格子的位置變化；

根據以上提示，計算每個格子的狀态-價值函數以及最優狀态-價值函數。

一、初始化相關參數

grid_size = 5 #網格大小
posA=[0,1] #A的位置
posB=[0,3] #B的位置
primeA=[4,1] #A'的位置
primeB=[2,3] #B'的位置
discount=0.9 #折扣參數
actions=["U","D","L","R"] #動作清單
           

二、初始化每個格子（狀态）處的行動機率，即均勻随機決策

#初始化每個格子（狀态）處的行動機率，即均勻随機決策
actionProb = []
for i in range(0,grid_size):
    actionProb.append([])
    for j in range(0,grid_size):
        actionProb[i].append(dict({"L":0.25,"U":0.25,"R":0.25,"D":0.25}))
           

三、初始化每個格子（狀态）出的狀态轉移和收益

#定義好每個狀态處的狀态轉移，以及回報值
successorState=[]
actionReward=[]
for i in range(0,grid_size):
    successorState.append([])
    actionReward.append([])
    for j in range(0,grid_size):
        next = dict()
        reward = dict()
        #設定向上移動時的收益以及新的位置（狀态）
        if i== 0:
            next["U"]=[i,j]
            reward["U"]=-1.0
        else:
            next["U"]=[i-1,j]
            reward["U"]=0.0
        
        #設定向下移動時的收益以及新的位置（狀态）
        if i==grid_size - 1:
            next["D"]=[i,j]
            reward["D"]=-1.0
        else:
            next["D"]=[i+1,j]
            reward["D"]=0.0
            
        #設定向左移動時的收益以及新的位置（狀态）
        if j==0:
            next["L"]=[i,j]
            reward["L"]=-1.0
        else:
            next["L"]=[i,j-1]
            reward["L"]=0.0
            
        #設定向右移動時的收益以及新的位置（狀态）
        if j == grid_size-1:
            next["R"]=[i,j]
            reward["R"]=-1.0
        else:
            next["R"]=[i,j+1]
            reward["R"]=0.0
        
        #到達A的位置時，直接到A'，并且收益為10.0
        if [i,j] == posA:
            next["L"]=next["R"]=next["D"]=next["U"]=primeA
            reward["L"]=reward["R"]=reward["D"]=reward["U"]=10.0
        if [i,j]==posB:
            next["L"] = next["R"] = next["D"] = next["U"] = primeB
            reward["L"] = reward["R"] = reward["D"] = reward["U"] = 5.0
            
        successorState[i].append(next)
        actionReward[i].append(reward)
           

四、使用貝爾曼方程計算狀态-價值函數并可視化

stateValue = np.zeros((grid_size,grid_size))
while True:
    newStateValue=np.zeros((grid_size,grid_size))
    for i in range(0,grid_size):
        for j in range(0,grid_size):
            for action in actions:
                newPosition = successorState[i][j][action]
                #這裡計算對應公式上的p(s',r|s,a)時，值為1
                newStateValue[i,j]+=actionProb[i][j][action]*(actionReward[i][j][action]+discount*stateValue[newPosition[0],newPosition[1]])

    if np.sum(np.abs(stateValue-newStateValue))<1e-4:
        print("狀态-價值")
        print(newStateValue)
        break
    stateValue = newStateValue

plt.matshow(newStateValue,cmap=plt.cm.Greys)
plt.colorbar()
plt.show()
           

[[ 3.30902999  8.78932551  4.42765281  5.3224012   1.49221235]
 [ 1.52162172  2.9923515   2.25017358  1.90760531  0.5474363 ]
 [ 0.05085614  0.73820423  0.67314689  0.35821982 -0.40310755]
 [-0.97355865 -0.43546179 -0.35484864 -0.58557148 -1.18304148]
 [-1.8576669  -1.34519762 -1.22923364 -1.42288454 -1.97514545]]
           

五、計算最優狀态-價值函數

stateValue = np.zeros((grid_size,grid_size))
while True:
    newStateValue = np.zeros((grid_size,grid_size))
    a = ""
    for i in range(0,grid_size):
        for j in range(0,grid_size):
            values = []
            for action in actions:
                newPosition = successorState[i][j][action]
                #這裡計算對應公式上的p(s',r|s,a)時，值為1
                values.append(actionReward[i][j][action]+discount*stateValue[newPosition[0],newPosition[1]])

            newStateValue[i][j]=np.max(values)
            #找出所有最優狀态-價值的行動
            indexes = np.argwhere(values==np.max(values))
            indexes = indexes.flatten().tolist()
            policyOfState = "".join([actions[index] for index in indexes])
            a += policyOfState+" "

    if np.sum(np.abs(stateValue - newStateValue)) < 1e-4:
        a = a.strip().split(" ")
        policy = np.reshape(a,[grid_size,grid_size])
        print("最優狀态-價值")
        print(newStateValue)
        print("最優政策")
        print(policy)
        break

    stateValue = newStateValue
plt.matshow(newStateValue,cmap=plt.cm.Greys)
plt.colorbar()
plt.title("optimal state value")
plt.show()
           

最優狀态-價值
[[21.97744338 24.41938153 21.97744338 19.41938153 17.47744338]
 [19.77969904 21.97744338 19.77969904 17.80172914 16.02153504]
 [17.80172914 19.77969904 17.80172914 16.02153504 14.41938153]
 [16.02153504 17.80172914 16.02153504 14.41938153 12.97744338]
 [14.41938153 16.02153504 14.41938153 12.97744338 11.67969904]]
最優政策
[['R' 'UDLR' 'L' 'UDLR' 'L']
 ['UR' 'U' 'UL' 'L' 'L']
 ['UR' 'U' 'UL' 'UL' 'UL']
 ['UR' 'U' 'UL' 'UL' 'UL']
 ['UR' 'U' 'UL' 'UL' 'UL']]