文章目錄

• • 1 簡介
  • 2 馬爾可夫屬性
  • 3 State Transition Matrix
  • 4 MP
  • 5 示例：Student Markov Chain
  • 6 Markov Reward Process
  • 7 Return
  • 8 為什么需要衰減？
  • 9 MRP的值函數
  • 10 貝爾曼方程
  • 11 貝爾曼方程的數學表示
  • 12 MDP
  • 13 Policy
  • 14 MDP的值函數
  • 15 最優值函數
  • 16 最優策略
  • 17 尋找最優策略
  • 18 貝爾曼最優等式
  • 19 MDP的拓展
  • • 19.1 Infinite MDPs
    • 19.2 POMDPs

1 簡介

馬爾可夫決策過程(Markov Decision Processes, MDP) 是RL中的一個基本理論，它為RL較為公式化地描述了一個environment(以下簡稱env)，這個env比較理想化，是fully observable(即環境的所有變化對智能體agent可見)。
值得一提的是，所有RL問題都可以是MDP問題：

• Optimal control primarily deals with continuous MDPs
• Partially observable problems can be converted into MDPs
• Bandits(老虎機問題) are MDPs with one state

2 馬爾可夫屬性

MDP形式上類似數字電路中的狀態機，即狀態的轉換過程，能夠構成MDP的狀態稱之為具有馬爾可夫屬性，以下簡稱M屬性。定義如下：

上述的數學含義是$S_{t+1}$在$S_t$下的條件概率與在$S_1,S_2,...,S_t$并集下的概率相等，即The future is independent of the past given the present(未來的狀態只與當前狀態有關)。

3 State Transition Matrix

在MDP中，當前狀態可以在下一步轉換到自身狀態，也可能轉換到其他狀態，例如總共3個狀態，處于狀態1即$s_1$時，轉到自身或其他狀態$s_2$和$s_3$的概率分別是0.2，0.4，0.4，注意這里的概率和自然等于1。這種轉換過程需要用state transition probability來描述：

即狀態為$s$條件下，下一步狀態為$s^{\prime }$的概率。
對于n個狀態的情況下，把每個state transition probability湊到一起就成了State Transition Matrix：

忽略圖中的from和to(懶得改了)，其中根據上面轉換到所有狀態的概率和為1，矩陣每行的元素之和也等于1。

4 MP

馬爾可夫過程(MP)是一個無記憶的隨機過程：

5 示例：Student Markov Chain

如圖是一個學生狀態的馬爾可夫過程或者說馬爾可夫鏈，圖中的意思是，假如學生在上class 1，那么結束class 1后有0.5的概率繼續上class 2，也有0.5的概率會去刷facebook，注意這里有一個終止狀態，即sleep，進入sleep之后不再跳轉，也如定義中所說的$S$是一個(finite) set of states。
假設我們的初始狀態是class 1(C1)，它最終是會進入終止狀態sleep(當前也可能不會而變成一個循環狀態)的，可能的情況有很多種：

• C1 C2 C3 Pass Sleep
• C1 FB FB C1 C2 Sleep
• C1 FB FB C1 C2 C3 Pub C1 FB FB FB C1 C2 C3 Pub C2 Sleep
  這里的每一種情況一般稱為一個回合(episode)。那么這里我們就可以描述它的 State Transition Matrix了，如下：
  

6 Markov Reward Process

僅僅有上面的過程還不足以做出決策，RL本質上是一個基于reward的過程，我們需要引入reward，定義如下：

在Student Markov Chain示例中，則可以表示為：

即比如當我們進入狀態class 1時，就給一個-2的獎勵，這個獎勵可以是人為規定的。

7 Return

在一個**回合(episode)**中，我們每完成一個狀態就給一個獎勵，回合結束時將獎勵累積起來就是最終的回報(return)，如下：

這里引入了一個衰減因子$\gamma$，它在0-1范圍之間，它的基本意義如下：

8 為什么需要衰減？

大多數MDP都會有這個衰減因子，原因如下：

• 便于數學計算
• 避免循環馬爾可夫過程中的return成無限大的值
• 沒有衰減，未來的不確定性可能不能很好地表示出來
• If the reward is financial, immediate rewards may earn more interest than delayed rewards
• Animal/human behaviour shows preference for immediate reward

9 MRP的值函數

value function(值函數)是用來表示某個狀態的長期價值的。

如下：

上面可以看出不同情況下或者說不同的episode，每個狀態的value不同的，我們value function計算的是期望值，但是由于每個狀態的episode很多，顯然不方便直接列舉計算，而貝爾曼方程給出了答案。

10 貝爾曼方程

貝爾曼方程給出了值函數的求解，

即當前狀態的值$v(s)$等于完成當前狀態的獎勵$R_{t+1}$以及下一步各狀態的值的衰減和的期望。

示例如下：

如圖這里$R_{t+1}=?2$，下一個狀態有兩個，對應的概率分別為0.6和0.4，值分別為10和8，注意這里的衰減因子$\gamma =1$。
此時會產生一個問題，這里的10和8又是怎么來的呢？我們需要從終止狀態算起，首先看終止狀態即$R=0$的狀態，因為沒有下一個狀態，且$R_{t+1}=0$，所以對應的value也等于0，然后再找與終止狀態相鄰并且簡單的狀態，即$R=10$的那個，因為它的下一個狀態只有終止狀態，所以也容易得出它的value=10，計算其他的可能就需要設未知數求解了，這是筆者想到的第一個比較自然的高中數學思路，其實用矩陣表示的話計算會更加簡單，也能適用于更為復雜的情況，見下一節。

11 貝爾曼方程的數學表示

根據上面一節，不難寫出貝爾曼方程的矩陣表示形式，可以看到包含了所有狀態之后，這里不再有$v(s)$和$v(S_{t+1})$的區分，而都變成了$v$，這就是所謂的數學之美！，有了這個計算value就簡單多了，如下：

當然說簡單也不簡單，這里涉及到逆矩陣，對于簡單的MDP可以計算得出，對于復雜的就需要用到其他各種各樣的方法，比如：

• Dynamic programming
• Monte-Carlo evaluation
• Temporal-Difference learning

12 MDP

上面描述了Markov Process和Markov Reward Process，這次我們再引入一個action，就成了一個完備的MDP了，如下：

還是以學生作為示例，圖中的紅字就是action，注意跟狀態state有區別：

13 Policy

policy即策略，RL最終就是要找到一個最優策略來達到比如回報最大的目標，數學定義如下：

即它是狀態為s條件下的a的概率分布，注意policy是描述智能體agent的行為的，它只依賴于當前的狀態。
總結一下就是對于一個MDP即$\mathcal{M}=?\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},\gamma ?$和策略$\pi$，一個狀態序列(state sequence)$S_1,S_2,...$或者說一個回合(episode)就是一個馬爾可夫過程$?\mathcal{S},{\mathcal{P}}^{\pi }?$，一個狀態獎勵序列$S_1,R_2,S_2,...$就是Markov Reward Process$?\mathcal{S},{\mathcal{P}}^{\pi },{\mathcal{R}}^{\pi },\gamma ?$，并且：

14 MDP的值函數

MDP的值函數分為狀態-值函數和動作-值函數，如下：

注意v跟q的關系如下：

與上面MRP的值函數類似，我們依然需要用到貝爾曼方程計算每個狀態的期望價值，這里使用q表示value，經典算法q-learning的q也是這個q：


注意這里的$\gamma$和$\pi \left(a^{\prime }|s^{\prime }\right)$一般是常量，這里取$\gamma =1$和7.4狀態下的$\pi \left(a^{\prime }|s^{\prime }\right)=0.5(即此狀態下對study和pub動作雨露均沾，概率各為0.5)$，以學生為例：

以7.4(這個是v值而不是q)這個狀態為例，對于這個狀態它有兩種可能的行為即study和pub，study之后對應的只有0的那個狀態，pub之后可能有三種狀態，先計算study這個動作對應的q值，首先完成study之后對應的獎勵為10，因為下一步的v值即這里的${\sum }_{a^{\prime }\in \mathcal{A}}\pi \left(a^{\prime }|s^{\prime }\right)q_{\pi }\left(s^{\prime },a^{\prime }\right)$等于0，所以study對應的$q_{\pi }(s,a)$等于10，再計算pub對應的q值，易知獎勵為1，第二項$\gamma {\sum }_{s^{\prime }\in \mathcal{S}}{\mathcal{P}}_{s{s}^{\prime }}^a{\sum }_{a^{\prime }\in \mathcal{A}}\pi \left(a^{\prime }|s^{\prime }\right)q_{\pi }\left(s^{\prime },a^{\prime }\right)=1?0.2??1.3+1?0.4?2.7+1?0.4?7.4$，兩個q值相加再乘以$\pi (a|s)=0.5$即可。
前面也提到這種計算方法不適用于復雜情況，因此同樣的對應的貝爾曼方程的矩陣表示如下：

15 最優值函數

我們定義最優值函數即對應的value達到最大，也是MDP的最優解。

16 最優策略

對于智能體agent我們則需要知道最優策略，最優策略即最優值函數下對應的策略，如下：

對于任意MDP，定論如下：

• 必然存在最優策略，可能不止一個
• 最優策略對應的state-value function值(簡稱v值)最大
• 最優策略對應的action-value function(q值)最大

17 尋找最優策略

一個簡單的最優策略可以通過找到每步最大的q值得出，如下：

如下：

注意這里圓圈里面的值不是之前的v值而是q值，這里設facebook那里為起始狀態，那么最優化策略就是圖中的紅線，即每次選擇使q值最大的狀態和動作。

18 貝爾曼最優等式

對應的貝爾曼最優等式(Bellman Optimality Equation)表示如下：


如下：

假如我們處于紅色數字6的狀態，對應的下一步動作有兩個，每個動作對應的q值分別為-2+8=6，和-1+6=5，此時我們就應該選擇q值最大的study動作。
需要注意的是貝爾曼最優等式是非線性的，因此沒有一個通解，常用的解決方法如下：

• Value Iteration
• Policy Iteration
• Q-learning
• Sarsa

19 MDP的拓展

前面簡介那一節說了，原始的MDP是有限個狀態的，并且fully observable，而相應地MDP的拓展形式有：

• Infinite and continuous MDPs
• Partially observable MDPs
• Undiscounted, average reward MDPs

19.1 Infinite MDPs

即無限狀態的MDP，可能情況以及對應的解決方法如下：

• 離散的無限狀態-動作空間
  比較簡單
• 連續的狀態-動作空間
  Closed form for linear quadratic model (LQR)，即轉換為線性二次模型
• 連續時間
  1)Requires partial differential equations，需要偏微分方程
  2)Hamilton-Jacobi-Bellman (HJB) equation
  3)Limiting case of Bellman equation as time-step → 0

19.2 POMDPs

即Partially observable MDPs，如下：

這里引入了一個觀測值，即observation。
后面的暫時不展開，有興趣可以看一下Ergodic Markov Process。

總結

以上是生活随笔為你收集整理的深度强化学习第2课｜马尔可夫决策过程的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。