【機器學習】馬爾科夫決策過程
- 2020 年 2 月 13 日
- 筆記
本文介紹了馬爾可夫決策過程，首先給出了馬爾可夫決策過程的定義形式，其核心是在時序上的各種狀態下如何選擇最優決策得到最大回報的決策序列，通過貝爾曼方程得到累積回報函數；然後介紹兩種基本的求解最優決策的方法，值迭代和策略迭代，同時分析了兩種方法的適用場景；最後回過頭來介紹了馬爾科夫決策過程中的參數估計問題：求解-即在該狀態下採取該決策到底下一狀態的概率。
作者 | 文傑
編輯 | yuquanle
馬爾科夫決策過程
A、馬爾科夫決策過程
機器學習演算法（有監督，無監督，弱監督）中，馬爾科夫決策過程是弱監督中的一類叫增強學習。增加學習與傳統的有監督和無監督不同的地方是，這些方法都是一次性決定最終結果的，而無法刻畫一個決策過程，無法直接定義每一次決策的優劣，也就是說每一次的決策資訊都是弱資訊，所以某種程度上講，強化學習也屬於弱監督學習。從模型角度來看，也屬於馬爾科夫模型，其與隱馬爾科夫模型有非常強的可比性。
下面是一個常用的馬爾科夫模型的劃分關係
不考慮動作 | 考慮動作 | |
|---|---|---|
狀態完全可見 | 馬爾科夫鏈(MC) | 馬爾科夫決策過程(MDP) |
狀態不完全可見 | 隱馬爾科夫模型(HMM) | 不完全可觀察馬爾科夫決策過程(POMDP) |
馬爾科夫決策過程：
馬爾科夫決策過程由五元組組成
：表示狀態集合
：表示一組動作
：表示在某一狀態下，採取動作，轉移到轉態的概率，也就是說在確定的狀態下採取相應的動作之後不能完全確定下一狀態，而是以一定的概率確定下一狀態。
：表示決策過程的一個阻尼係數，用戶定義回報在決策過程中隨時間打折扣，加快決策國產的收斂
：表示在該狀態下的一個回報，有時由動作和狀態共同決定回報該時刻的回報。
有了上面的定義之後，一個完整的馬爾科夫決策過程狀態轉移圖如下：
該過程表示從出發，有決策函數來選擇相應的動作，然後以概率到達下一狀態，這裡的只是表示第時刻的狀態，而的值屬於狀態集。
回報函數定義之後，整個決策過程的累積回報如下：
當回報函數與狀態無關累積回報如下：
其中為折扣因子，隨著決策不斷進行，回報不斷打折扣。
當定義不同決策函數時，我們會得到不同的回報，因此就定義了一個決策到回報的函數。在整個決策過程中，給定決策函數—在狀態下採取動作。因此，從狀態出發，採用決策函數，有累積回報函數如下：
直接最大化累積回報函數不易，從遞推角度來看，由貝爾曼方程有：
其中為立即回報，表示由採取動作之後轉移到下一個狀態集中，具體到哪個狀態的概率為。其解釋性可以理解為下象棋最終的累積回報為輸贏，在第狀態下的累積回報則是當前狀態下的立即回報以及未來的回報。第一項為立即回報，第二項就是未來的回報。
有了上面的貝爾曼方程，我們的目標就是最大化任意狀態下出發的累積回報函數，其中也是一個決策函數，但是在累積回報函數中它是我們需要優化的變數。目標函數如下：
由目標函數可以看出，最優回報和最優決策一一對應。最大化累積回報對應的決策函數就是最有決策，最有決策對應的累積回報也是最大累積回報，所以最有決策如下：
有了最優決策和最大累積回報，那麼必定有下式：
也就是說最優決策下對應的累積回報一定不小於一般的決策下的累積回報。
值得注意是，最優決策是出於全局考慮的，是從所有狀態下出發到得到的累積回報的加和最大，這就意味著決策函數不保證其中每一個狀態出髮根據決策函數得到的累積回報都是最大的。
最優決策：
也許上面的目標函數還不清晰，如何求解最有決策，如何最大化累積回報
下面結合例子來介紹如何求解上面的目標函數。且說明累積回報函數本身就是一個過程的累積回報，回報函數才是每一步的回報。
下面再來看求解上述最優問題，其中 就是以s為初始狀態沿著決策函數走到結束狀態的累積回報。
值迭代：
- 將每一個初始狀態為s的初始化為0,目標狀態累積回報為1
- 循環直到收斂{
對於每一個初始狀態，對進行更新：
}
可以看出，更新第一次所有的，也就是說都只看眼下的立即回報，然後由於獎勵狀態和懲罰狀態的分布不同，由靠近獎勵狀態和懲罰狀態的狀態決策逐漸導向到初始狀態的決策，這也就是累積回報不斷更新的原因（動力）。但是值得思考的還是最終會不會收斂到最優累積回報（暫時不作討論）。
內循環迭代的的處理方法有兩種：
- 同步迭代：即在一次循環過程中，累積回報不更新，而是計算完所有的累積回報之後，再統一更新。
- 非同步迭代，即在一次循環過程中，每計算完一個初始狀態下累積回報就立即更新，不需要等到所有的累積回報都計算出來之後再更新。
可以看出兩種迭代方式造成不同的原因是第二項，因為立即更新之後，再計算下一個初始狀態下的累積回報與暫時不更新得到的累積回報肯定不一樣，拿第一次更新為例，同步更新第一次 ，而非同步更新則第一次內循環中，除了第一次更新的s會出現 ，剩下的都有 ，值得肯定的是非同步迭代的收斂速度肯定是快於同步迭代。
策略迭代：
值迭代是使累積回報值最優為目標進行迭代，而策略迭代是藉助累積回報最優即策略最優的等價性，進行策略迭代。
- 隨機指定一個策略 。
- 循環直到收斂{ a:令 b:對於每一個狀態s，對做更新
}
這裡要說明的是a步是通過前面的貝爾曼方程，以解方程的形式求解出每一個狀態下的累積回報：
在b步則是根據累積回報值，重新更新決策 。
同樣，收斂性也是值得探討的，這裡簡單的思考一下，由於獎勵狀態和懲罰狀態的分布，以及累積回報唯一確定決策函數，那麼未達到最優決策，必然累積回報和決策函數處於不穩定的狀態，而只有當到達最優決策時，才有：
所以該過程就是在a步由決策函數確定累積回報，然後最大化累積回報來更新決策，如此反覆，則有最優決策。值迭代和策略迭代比較：可以看出策略迭代涉及從決策函數到累積回報的解線性方程組的步驟，值迭代則是反覆的，所以策略迭代更適合處理少量狀態的情況，一般10000以內還是可以接受的。
MDP中的參數估計：
回過頭來再來看前面的馬爾科夫決策過程的定義是一個五元組，一般情況下，五元組應該是我們更加特定的問題建立馬爾科夫決策模型時該確定的，並在此基礎上來求解最優決策。所以在求解最優決策之前，我們還需更加實際問題建立馬爾科夫模型，建模過程就是確定五元組的過程，其中我們僅考慮狀態轉移概率，那麼也就是一個參數估計過程。（其他參數一般都好確定，或設定）。
假設，在時間過程中，我們有下面的狀態轉移路徑：
其中表示步，第條轉移路徑對應的狀態，是狀態下執行的動作，每一條轉移路徑中狀態數都是有限的，在實際過程中，每一個狀態轉移路徑都要進入終結狀態。如果我們獲得了很多上面的轉移路徑，那麼我們就可以來估計參數。
分子是在狀態下採取動作都轉移到的次數，分母是在狀態下採取動作的次數。為了避免的情況，同樣採用拉普拉斯平滑。也就是說當到達的狀態是樣本中為為到達過的狀態，那麼在該狀態下的執行的動作達到下一狀態的概率均分。上面的這種估計方法是從歷史數據中進行統計的，同樣該方法適合於在線更新。對於立即回報函數的估計，一般根據實際情況學習或者設定。
所以整個馬爾科夫決策過程流程如下（以策略迭代為例）：
- 隨機初始化策略 。
- 循環直到收斂{ a 在樣本上統計該策略下每個狀態轉移的次數，來估計和 b 使用估計到參數來更新對應決策函數下的累積回報 c 根據更新的累積回報重新進行決策，即更新
}
整個流程就是在策略迭代的基礎上，同時進行了參數估計。
程式碼實戰
A、馬爾可夫決策過程值迭代
/*** 馬爾科夫決策過程值迭代，關鍵在於第一次迭代要例外， 因為目標狀態是一個終止狀態，放到迭代循環裡面會出現 臨近的狀態回報函數無限的，發散。 迭代過程採用的是非同步迭代，即每一次內層循環找到更優的 回報就立即更新最大回報，以便與之相鄰的狀態能立即更新到最優 */ /**** 值迭代 同步更新 12*12*7 */ while(!flag) { flag=1; for(i=0; i<size; i++) { if(action[i]>0||action[i]==0) maxreward[i]=reward[i]+maxreward[action[i]]; else maxreward[i]=reward[i]; }//放到這意味著同步更新，count=1008是12*12的7倍，即掃了7遍 for(i=0; i<size; i++)//對每一個狀態求最大的V(s) { for(j=0; j<size; j++)//策略迭代的話這裡其實可以換做掃一遍策略集，這也就是和值迭代不同的地方 { //cout<<"i="<<i<<" "<<maxreward[i]<<" "<<endl; if(matrix[i][j]==1&&maxreward[j]>maxreward[i]-reward[i]+0.0001)//更新累積回報 { action[i]=j; //if(action[i]>0||action[i]==0) //maxreward[i]=reward[i]+maxreward[action[i]];//放到這是非同步更新， //else // maxreward[i]=reward[i]; flag=0;//當累積回報不再更新，即不進入該if，那麼就結束迭代 } count++; } } }B、馬爾可夫決策過程策略迭代
while(!flag) { flag=1; for(i=0; i<size; i++)//對每一個狀態求最大的V(s) { for(j=0; j<ACTION; j++)//策略迭代的話這裡其實可以換做掃一遍策略集，這也就是和值迭代不同的地方 { //cout<<"i="<<i<<" "<<maxreward[i]<<" "<<endl; if(matrix[i][ac[j]+i]==1&&maxreward[ac[j]+i]>maxreward[i]-reward[i]+0.0001) { action[i]=j; //if(reward[i]!=1&&reward[i]!=-1) maxreward[i]=reward[i]+maxreward[ac[j]+i]; //else // maxreward[i]=reward[i]; flag=0; } count++; } } }C、馬爾可夫決策過程動態規劃版
/** 4 非遞歸動態規劃 從最終狀態出發，採用廣度遍歷不斷的更新其上一狀態的累積回報 */ /* while(q!=NULL)//這裡圖的廣度遍歷沒有用到隊列，但也用到了隊列的思想 //對於當前步能到達的節點用鏈表連接起來，然後逐漸進行下一步的能到達的節點進行入鏈（入隊列），同樣是一種先進先出思想 { for(i=0; i<size; i++) //由於不是策略迭代，只能遍歷所有的狀態，找出能到的，且更優的 { if(matrix[i][q->data]==1&&maxreward[i]<0)//double類型比較大小的偏差，加上一個小數作為精度 { maxreward[i]=reward[i]+maxreward[q->data]; p=(subset *)malloc(sizeof(subset)*1); p->data=i; p->next=NULL; q=maxsubset; while((q->next)!=NULL) q=q->next; q->next=p; } count++; } maxsubset->next=maxsubset->next->next;//刪除當前節點，即當前步下能到達的節點都已經走完了，可出隊列了 q=maxsubset->next;// }