AI學習筆記——MDP(Markov Decision Processes馬可夫決策過程)簡介
前面好幾篇文章都在介紹強化學習（RL），以及強化學習的一些具體演算法，但是強化學習中用到的最重要的理論MDP卻還沒提到。這篇文章就來說說MDP。
講MDP的文章和資料非常多，理論和數學公式也能輕易找到，所以本文並不是要嚴謹地推導MDP，而是想讓讀者感性地認識MDP以及它對強化學習的重要性。本文主要的參考資料來自於David Silver 教授(DeepMind 的創始人) ofollow,noindex">在UCL的課程 以及Richard S. Sutton and Andrew G. Barto的經典書籍: Reinforcement Learning: An Introduction
1. MDP需要滿足的條件
RL是要通過對環境不停地試錯來學習的，MDP就是用來描述RL中的環境。
- 這個環境必須是完全可觀測的(Fully Observable)。幾乎所有的RL問題都可以轉換成MDP的環境。
- 未來只與當前的狀態有關，與之前的歷史沒有關係。換句話說就是當前的狀態一旦確定了，之前的歷史就可以拋棄了，因為未來只與當前有關。
2. MP(Markov Process 馬可夫過程)
注意，MDP除去決策"D"，就是MP。MP是一個隨機過程。從 現在狀態 S 到 下一個狀態 S' 通過 P ss' 狀態轉移概率矩陣(State transition probability matrix) 來完成這個過程, Pss'只是概率，所以MP還是隨機的。
舉個栗子：
如下圖，一個學生學習一門課程，有6個狀態：從Class1 到 Class 3 的學習，到Pass再到去Sleep。中間可能去刷Facebook, 去Sleep或者去酒吧(Pub)喝酒。
其中，那些數字(0.9,0.1)和箭頭就代表了P ss' 的數值和狀態轉移的方向。P ss' 實際上是一個矩陣，如下圖：
3. 馬可夫獎勵過程(Markov Reward Process)
獎勵R是環境的反饋，當然這個反饋是與行動A, 相關的。在還沒引入行動這個概念之前，暫且認為只與狀態S有關。下圖是加上了獎勵引數的樣子：
我們的目標 G t 是獲得獎勵，有了R，有了S，有了P ss' 矩陣，實際上我們就能夠 估算 出每一個S上的G t ：E(G t |S t = S)。
G t 是這樣定義的：
的物理意義就是之後狀態的所有R的總和。
γ為衰減值（0到1之間），我們在之前Q-Learning中已經介紹過了，就不多說了。
這個估算出來的Gt就叫做這個狀態S上的Sate Value function(狀態值函式): v(S)
4. Bellman 等式
v(S)很明顯是一個遞迴的過程，也就是說知道了最終狀態v(S 最終 )(上面那個例子是Sleep)就可以倒推到初始狀態的v(S 初始 )，這個關係就是用Bellman 等式表達出來的。
在任意一個狀態S如何求v(S)呢？需要用到下面這個公式
就是之前提到的State transition probability matrix。
這個公式的物理意義也很簡單，就是這個狀態的獎勵加上所有可能的下一個狀態的v(S')和對應的P ss' 的乘積之和，再乘以衰減值γ。
我們可以輕易驗證4.3這個v(s) 是否正確，如下圖(γ=1)
5. MDP(Markov Decision Processes馬可夫決策過程)
有了前面MP的鋪墊，加上D(Decision)就是MDP(馬可夫決策過程了)。這個決策是要決策什麼呢？就是要決策 行動(Action) 。
正如之前提到的，行動A的獎勵R不僅跟狀態S相關，而且與行動A也是相關的，還是之前學生學習課程的例子，加上行動和與行動相關的R，如圖：
（注意pub 那個黑點這裡變成了行動，而不是狀態，主要是為了後面區分sate-value function 和 action-value function）
6. 策略(Policy)
DP是一個隨機的過程，在有了策略 (policy)π之後才整個過程才有了規律，策略也是一個概率分佈，體現了在給定狀態下采取行動的概率。
策略是用來指導行動的，不要與描述狀態間的P ss' 混淆了。當然兩者是有聯絡的，後面將會提到。
7. Value Function(值函式)
這是MDP最 重要的 的概念。前面已經提到了 狀態值函式(State-Value Function)v(S) (後面簡稱V函式)，但是沒有機器人，沒有策略指導機器人的行動。
有了策略π之後v π (s)的物理意義就是，在該策略的指導下，在目前這個狀態下，之後能夠預期的到的的獎勵是多少。
當然我們更關心策略是如何指導行動的，我們引入 行動值函式(Action-Value Function) q π (s,a) 的概念。看起來是不是很眼熟，因為我們通常又叫他q函式，參見之前的文章Q-Learning。
因為加入了行動，所以q函式的物理意義就是，在當前策略的指導下，在當前狀態下，採取行動a之後所能預期得到的獎勵是多少。
8. V函式和Q函式的關係
V函式和Q函式都是遞迴關係，這個通過Bellman 等式也可以證明，這裡也不再贅述。
通過Q函式來求V函式：
上圖，空心代表狀態，實心代表行動。所有行動的策略π(a|s)與Q函式q π ()的乘積之和就能得到V函式。
同樣的，所有下一個狀態的V函式與對應的P ss' 乘積之和再加上採取該行動的獎勵就能求得Q函式。
再次注意，P ss' 反映的是狀態間的轉移概率，π(a|s)是狀態和行動間的策略概率
當然上面兩圖組合(公式的帶入)就能反映該狀態的V函式和下一個狀態的V函式的遞迴關係。
倒過來組合(公式帶入)就能反映該行動下的Q函式和下一個行動的Q函式的遞迴關係。
。
利用上面的公式我們可以輕易驗證例子中pass的V函式：
注意：π(a|study)= π(a|pub) =0.5
總結
本文介紹了MDP的基本概念，然而我們瞭解MDP的概率是為了指導我們的行動從而得到最優的結果。換句話說就是選擇最優的策略得到最多的獎勵。再換句話說就是求最大的V函式和Q函式，這些內容將放到下一篇文章再做介紹。
文章首發steemit.com 為了方便牆內閱讀，搬運至此，歡迎留言或者訪問我的Steemit主頁