浪浪的老唐
在介紹馬爾可夫決策過程之前，前介紹一下什麼是馬爾可夫過程。
馬爾可夫過程（Markov Process）指的一類具有馬爾可夫性的隨機過程。其中馬爾可夫性就是：在當前狀態下，其未來變化不依賴於過去，即未來和過去是相互獨立的，相互之間沒有關係。換句話說，未來的變化只取決於當前狀態。比如天氣變化過程，人口增長過程就可以看作是一個馬爾可夫過程。
我們可以用有限狀態集合S和狀態之間的轉移矩陣P（從一個狀態轉移到另一個狀態的概率）來描述一個馬爾可夫隨機過程。舉一個最簡單的例子就是天氣狀態之間的變化。這裡為了簡單起見就只有兩個狀態，那麼S={Sunny,Rainy}
狀態轉移矩陣P
那麼根據天氣的狀態集S和狀態轉移P，我們就知道了天氣之間是如何變化的。現在就介紹我們的主角馬爾可夫決策過程（Markov Decision Process），顧名思義，就是在馬爾可夫過程的基礎之上引入了決策這一影響因素。從完全隨機來決定狀態轉移，變為部分隨機和決策者共同控制狀態之間的轉移。
這就需要在原有基礎之上再引入描述決策者的信息，包括決策者執行的動作集合A、驅動決策的回報函數R以及隨著時間推移的獎勵折扣率。此外狀態轉移矩陣也加入了選擇動作的因素，在相同狀態下，選擇不同的動作就會有不同的狀態轉移概率。如下圍棋、股票投資都可以視為馬爾可夫決策過程。
馬爾可夫決策過程的核心問題是：如何進行連續的決策（找到一個策略）使得最終得到的回報最大。
比如下面就是學生一天中的狀態轉移圖，那麼該如何規劃使得收穫最大（這裡取獎勵的折扣率為0.9）。其中每個圓圈有表示狀態，方塊表示結束。動作集合A={Facebook, Quit, Study, Sleep, Pub}。
那麼假設目前在狀態2處，那麼為了獲得最大的獎勵，具體的決策過程就是Study，跳到狀態3,然後繼續Study，跳到狀態4，然後選擇繼續Study，跳到結束狀態5。那麼最終獲得的獎勵就是：
針對狀態轉移概率P和獎勵R已知的情況下，我們可以用動態規劃的方法來解決馬爾可夫決策過程的最優化問題。如果未知，那麼就需要用強化學習的方法來解決如Q-learning、Sarsa等。
