David Silver强化学习课程笔记（二）
第二課：馬爾科夫決策過程
??????? 為什么要講馬爾科夫決策過程？因為幾乎所有的強化學習問題都可以表述成馬爾科夫決策過程（MDP）的形式，比如說：最優控制主要是處理連續MDP問題、任何部分可觀測的問題都可以轉化為MDP問題、bandits都是僅有一個狀態的MDP問題。這里的bandit是一種最為簡單的馬爾科夫問題：給你一組actions，然后你選擇一個action，從而得到reward，僅此而已。
?????? 1.馬爾科夫性
??????? "The future is independent of the past given the present."
??????? 準確的數學定義如下：
???????
??????? 值得注意的是，定義中給出的是某個狀態的Markov性，如果某個過程中的狀態均滿足Markov性，那么我們就說該過程為Markov過程。
??????? 從上面的定義中我們可以看出，某個狀態是Markov的也即該狀態從history中捕獲了所有的信息。因此，一旦我們得知了該狀態，我們就可以扔掉history了。換句話說，該狀態是future的充分統計量。在強化學習中，狀態s是future的充分統計量指的是s包含了足夠的信息來描述future所有的rewards。
?????? 2.馬爾科夫過程
???????
???????? 如上所說，馬爾科夫過程也即該過程中所有的狀態均滿足馬爾科夫性，它可以表示為一個二元組，包含了狀態集和狀態轉移矩陣。
?????? 3.馬爾科夫獎勵過程
???????
??????? 與上面的馬爾科夫過程對比，馬爾科夫獎勵過程（MRP）多了一個獎勵函數以及一個折扣因子，獎勵函數可以通過字面意思理解，而折扣因子則表示未來的獎勵對于現在的影響大小的度量。
?????? 4.馬爾科夫決策過程
??????
??????? 與MRP相比，馬爾科夫決策過程（MDP）加入了動作集，該過程中的狀態并不是自發地按照某個概率進行轉移了，而是通過選擇某個動作來進行轉移的，并且MDP過程中的獎勵不僅僅與所處狀態s相關了，而且還與在狀態s下選擇的動作a有關，該動作是按照某一指定策略來進行選取的。
?????? 5.回報
?????
??????? 所謂回報，也就是從時間步t開始，一直到terminal的總的折扣獎勵。值得注意的是，獎勵是從t+1開始的，具體分析見David Silver強化學習課程筆記（一）。
??????? 從回報的計算公式中可以看出，我們更加看重當前的獎勵。如果折扣因子接近0，就說這個回報是鼠目寸光的（myopic），如果折扣因子接近1，則說這個回報計算是有長遠打算的（far-sighted）。
?????? 6.MRP與值函數
??????? 我們首先看一下MRP中的值函數定義：
??????
??????? 如果我們稍加推導就會導出MRP的貝爾曼方程：
??????? 由于對于MRP過程而言，獎勵僅僅與狀態相關，因此，貝爾曼方程可以如下進行分解表示：
??????? 在貝爾曼方程中，值函數被分解為兩部分，一部分是對于t+1時間步的獎勵的期望，另一部分是對于有折扣的下一狀態值函數的期望。第一部分中由于t+1時間步的獎勵其實就是t時刻的狀態所換得的獎勵，因此期望可以直接略去；第二部分則是利用狀態轉移矩陣對狀態值函數求的期望。
??????? 當然，為了編程需要，我們也可以導出貝爾曼方程的矩陣形式：
??????
??????? 從矩陣形式的貝爾曼方程中我們可以看出，貝爾曼方程是一個線性方程，如果對于一些比較小的MRP，我們可以直接求解：
??????
??????? 其中計算時間復雜度最高的操作是求矩陣的逆，其時間復雜度是O(n^3)，n表示狀態數。可見，這種方法是不適用于求解大型MRP問題的，因此我們可以使用一些迭代方法進行求解：
??????? 1）動態規劃（DP）；
??????? 2）蒙特卡洛估計（MC evaluation）；
??????? 3）時間差分學習（TD learning）。
?????? 7.MDP與值函數
??????? 我們知道與MRP相比，MDP的元組表示中多了動作集這一項，動作的選取是按照某一指定策略進行選取的，因此，我們先對策略進行定義：
??????
??????? 從定義上來分析，這里的策略表示在給定的狀態下，各個動作選擇的概率分布，既可以表示確定性策略，也可以表示隨機性策略。所謂確定性策略即給定某個狀態，該策略的輸出就是某個動作，而不是一個概率分布；隨機性策略則輸出各個動作選擇的概率分布。
??????? 此外，課程還講到了我們可以從一個MDP模型中恢復MP與MRP：
??????
??????? 對于MDP而言，它就不僅僅只有狀態值函數V了，而且還有動作值函數Q，兩個值函數定義如下：
??????
?????? 與MRP的貝爾曼方程一樣，我們對上面兩個值函數稍加推導就可以得到兩個貝爾曼期望方程：
??????
??????? 將兩個值函數進行一步推演，即有：
? ? ? ?? ?????
??????? 如果我們將二者互相代入，或者說，進行二步推演，則得到：
? ? ? ? ? ? ?????
?????? 8.最優值函數與最優策略
??????? 強化學習的主要目的就是使智能體學會在環境中自行決策與動作，且累積獎勵要盡可能大。換句話說，我們想要智能體學到一個好的策略，那么如何比較兩個策略的好壞呢？首先我們定義最優值函數如下：
??????
??????? 即不論是對狀態值函數還是對于動作值函數而言，最優也就意味著通過改進策略來最大化值函數。
??????? 下面，我們利用值函數定義偏序關系：
??????
??????? 此外，我們有如下定理：
??????
??????? 也就是說對于任意的MDP而言，總存在一個最優策略，且最優策略的值函數是最優值函數。由此可見，我們只需要找到使值函數最大化的策略即可：
??????
??????? 上面通過greedy得到的策略是一個確定性策略。值得注意的是，對于任意MDP而言，總是存在一個最優的確定性策略的。
? ? ? ?9.貝爾曼最優方程
? ? ? ? 與前面關于貝爾曼期望方程的推演類似，我們可以對貝爾曼最優方程進行推演，首先是一步推演：
? ? ? ??
? ? ? ? 進行第二步推演：
? ? ? ??
? ? ? ? 將貝爾曼期望方程與貝爾曼最優方程進行對比，可以發現，貝爾曼期望方程是對于某一個給定的策略，求其狀態值函數和動作值函數，也即對某一策略進行估計；而貝爾曼最優方程則是要去尋找最優策略，也即通過對動作值函數進行greedy得到。
? ? ? ? 觀察貝爾曼最優方程可以發現，這并不是線性方程，其中引入了max函數，這是一個非線性函數，因此通常來說我們并不能像貝爾曼期望方程一樣直接求解得到一個閉式解，只能通過迭代進行求解，求解的方法有：
? ? ? ? 1）值迭代；
? ? ? ? 2）策略迭代；
? ? ? ? 3）Q-learning；
? ? ? ? 4）Sarsa。
? ? ? ?10.MDP擴展
? ? ? ? 上面的討論中，我們僅僅討論了周期性的離散的MDP，下面我們將簡要地討論一些復雜的情形：
? ? ? ? 1）無限的連續的MDP；
? ? ? ? 2）部分觀察的MDP（POMDP）；
? ? ? ? 3）無折扣因子的平均獎勵MDP。
? ? ? ? 首先，我們來看看Infinite MDPs：
? ? ? ?
? ? ? ??
? ? ? ? 對于無限但可數的狀態空間與動作空間而言，按照上面的方法進行求解即可；對于連續狀態與動作空間（時間仍然為離散化的）而言，使用LQR的閉式解；對于連續時間情形而言，我們需要引入偏微分方程，使用HJB方程進行求解。
? ? ? ? 其次，對于部分可觀察的MDP而言，其定義如下：
? ? ? ?
? ? ? ? 通俗地來講，POMDP也就是一個有著隱狀態（hidden states）的MDP，或者說，是一個引入了動作的隱馬爾科夫過程。從上面的定義中可以看出，狀態轉移矩陣P定義的狀態轉移是不可見的，即S'是隱狀態，我們所能觀測的狀態是o。
? ? ? ? 那如果我們得到了某個history如下：
? ? ? ?
? ? ? ? 此時隱狀態的分布是怎么樣的呢？我們引入信念狀態的概念：
? ? ? ?
? ? ? ? 信念狀態就是在給定某一個history的情況下，隱狀態的概率分布。
? ? ? ? 我們可以對POMDP進行簡化的表示：
? ? ? ?
? ? ? ? 左邊是馬爾科夫history樹，而右邊是belief state樹，對這兩個圖的理解是按照某一個分支進行，逐步模擬馬爾科夫過程的進行。
? ? ? ? 最后是平均獎勵MDP（Average Reward MDPs），首先，對各態歷經馬爾科夫過程進行定義：
? ? ? ?
? ? ? ? 緊接著，對各態歷經MDP進行定義：
? ? ? ?
? ? ? ? 最后引出平均獎勵值函數：
? ? ? ?
? ? ? ??
? ? ? ? 有一個重要概念需要理解，“什么是各態歷經過程？”各態歷經過程需要滿足三個條件，首先得是一個平穩過程，其次，該過程的均值具有各態歷經性，最后，該過程的相關函數具有各態歷經性。那什么是各態歷經性？所謂的“各態歷經性”指的是，只要觀察時間足夠長，它的每個樣本都歷經過程的各個可能狀態，或者說是“遍歷”各種可能狀態，所以一個樣本按時間的平均就可以近似地替代它在固定取值時的統計平均。具體來講，我們的隨機過程指的是從某一個時間點來看，是一個隨機變量，我們可以想象為，在某一個時間點處，有一個隨機分布。我們為了求這個隨機分布的統計特征，就需要在這個時間點做很多次實驗，然后用經驗值估計實際值，但是我們并不能控制時間的流逝，所以我們只能在不同時間點上去做實驗，然后求取統計特征。那各態歷經性對此有什么保證呢？它可以當做是保證了在每一個時刻，我們的任意一個狀態都有機會到達，并且還維持了整個過程的統計特征，這樣，我們就可以通過時間的平均來近似替代固定時刻取值的統計平均了。
?
? ? ? ? 謝謝閱讀，如有不當之處，請指出。
?
?
總結
以上是生活随笔為你收集整理的David Silver强化学习课程笔记（二）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 军用装备机车车辆设备冲击和振动试验测试机
- 下一篇： 深度学习方法求解平均场博弈论问题