增強學習Reinforcement Learning經典算法梳理1：policy and value iteration前言就目前來看，深度增強學習（Deep Reinforcement Learning)中的很多方法都是基于以前的增強學習算法，將其中的value function價值函數或者Policy function策略函數用深度神經網絡替代而實現。因此，本文嘗試總結增強學習中的經典算法。本文主要參考：1Reinforcement Learning: An Introduction；2Reinforcement Learning Course by David Silver1 預備知識對增強學習有所理解，知道MDP，Bellman方程詳細可見：Deep Reinforcement Learning 基礎知識（DQN方面）很多算法都是基于求解Bellman方程而形成：Value IterationPolicy IterationQ-LearningSARSA2 Policy Iteration 策略迭代Policy Iteration的目的是通過迭代計算value function 價值函數的方式來使policy收斂到最優。Policy Iteration本質上就是直接使用Bellman方程而得到的：那么Policy Iteration一般分成兩步：Policy Evaluation 策略評估。目的是 更新Value FunctionPolicy Improvement 策略改進。 使用 greedy policy 產生新的樣本用于第一步的策略評估。本質上就是使用當前策略產生新的樣本，然后使用新的樣本更新當前的策略，然后不斷反復。理論可以證明最終策略將收斂到最優。具體算法： 那么這里要注意的是policy evaluation部分。這里的迭代很重要的一點是需要知道state狀態轉移概率p。也就是說依賴于model模型。而且按照算法要反復迭代直到收斂為止。所以一般需要做限制。比如到某一個比率或者次數就停止迭代。3 Value Iteration 價值迭代Value Iteration則是使用Bellman 最優方程得到然后改變成迭代形式value iteration的算法如下： 那么問題來了：Policy Iteration和Value Iteration有什么本質區別？為什么一個叫policy iteration，一個叫value iteration呢？原因其實很好理解，policy iteration使用bellman方程來更新value，最后收斂的value 即v是當前policy下的value值（所以叫做對policy進行評估），目的是為了后面的policy improvement得到新的policy。而value iteration是使用bellman 最優方程來更新value，最后收斂得到的value即v就是當前state狀態下的最優的value值。因此，只要最后收斂，那么最優的policy也就得到的。因此這個方法是基于更新value的，所以叫value iteration。從上面的分析看，value iteration較之policy iteration更直接。不過問題也都是一樣，需要知道狀態轉移函數p才能計算。本質上依賴于模型，而且理想條件下需要遍歷所有的狀態，這在稍微復雜一點的問題上就基本不可能了。4 異步更新問題那么上面的算法的核心是更新每個狀態的value值。那么可以通過運行多個實例同時采集樣本來實現異步更新。而基于異步更新的思想，DeepMind出了一篇不錯的paper：Asynchronous Methods for Deep Reinforcement Learning。該文對于Atari游戲的效果得到大幅提升。5 小結Reinforcement Learning有很多經典算法，很多算法都基于以上衍生。鑒于篇幅問題，下一個blog再分析基于蒙特卡洛的算法。增強學習Reinforcement Learning經典算法梳理2：蒙特卡洛方法1 前言在上一篇文章中，我們介紹了基于Bellman方程而得到的Policy Iteration和Value Iteration兩種基本的算法，但是這兩種算法實際上很難直接應用，原因在于依然是偏于理想化的兩個算法，需要知道狀態轉移概率，也需要遍歷所有的狀態。對于遍歷狀態這個事，我們當然可以不用做到完全遍歷，而只需要盡可能的通過探索來遍及各種狀態即可。而對于狀態轉移概率，也就是依賴于模型Model，這是比較困難的事情。什么是狀態轉移？就比如一顆子彈，如果我知道它的運動速度，運動的當前位置，空氣阻力等等，我就可以用牛頓運動定律來描述它的運動，進而知道子彈下一個時刻會大概在哪個位置出現。那么這個基于牛頓運動定律來描述其運動就是一個模型Model，我們也就可以知道其狀態（空間位置，速度）的變化概率。那么基本上所以的增強學習問題都需要有一定的模型的先驗知識，至少根據先驗知識我們可以來確定需要多少輸入可以導致多少輸出。比如說玩Atari這個游戲，如果輸入只有屏幕的一半，那么我們知道不管算法多么好，也無法訓練出來。因為輸入被限制了，而且即使是人類也是做不到的。但是以此同時，人類是無需精確的知道具體的模型應該是怎樣的，人類可以完全根據觀察來推算出相應的結果。所以，對于增強學習的問題，或者說對于任意的決策與控制問題。輸入輸出是由基本的模型或者說先驗知識決定的，而具體的模型則可以不用考慮。所以，為了更好的求解增強學習問題，我們更關注Model Free的做法。簡單的講就是如果完全不知道狀態轉移概率（就像人類一樣），我們該如何求得最優的策略呢？本文介紹蒙特卡洛方法。2 蒙特卡洛方法蒙特卡洛方法只面向具有階段episode的問題。比如玩一局游戲，下一盤棋，是有步驟，會結束的。而有些問題則不一定有結束，比如開賽車，可以無限的開下去，或者說需要特別特別久才能結束。能不能結束是一個關鍵。因為只要能結束，那么每一步的reward都是可以確定的，也就是可以因此來計算value。比如說下棋，最后贏了就是贏了，輸了就是輸了。而對于結束不了的問題，我們只能對于value進行估計。那么蒙特卡洛方法只關心這種能夠較快結束的問題。蒙特卡洛的思想很簡單，就是反復測試求平均。如果大家知道在地上投球計算圓周率的事情就比較好理解了。不清楚的童鞋可以網上找找看。那么如何用在增強學習上呢？既然每一次的episode都可以到結束，那么意味著根據：每一步的reward都知道，也就意味著每一步的return Gt都可以計算出來。這就好了。我們反復做測試，這樣很多狀態會被遍歷到，而且不止一次，那么每次就可以把在狀態下的return求和取平均。當episode無限大時，得到的數據也就接近于真實的數據。蒙特卡洛方法就是使用統計學的方法來取代Bellman方法的計算方法。上面的算法叫first-visit MC。也就是每一次的episode中state只使用第一次到達的t來計算return。另一種方法就是every-visit，就是每一次的episode中state只要訪問到就計算return求平均。所以可以看到蒙特卡洛方法是極其簡單的。但是缺點也是很明顯的，需要盡可能多的反復測試，而且需要到每一次測試結束后才來計算，需要耗費大量時間。但是，大家知道嗎？AlphaGo就是使用蒙特卡洛的思想。不是蒙特卡洛樹搜索，而是說在增強學習中使用蒙特卡洛方法的思想。AlphaGo每次也是到下棋結束，而且只使用最后的輸贏作為return。所以這也是非常神奇的事，只使用最后的輸贏結果，竟然能夠優化每一步的走法。3 使用蒙特卡洛方法來控制上面說的蒙特卡洛方法只是能夠對當前的policy進行評估。那么大家記得上一個blog說的policy iteration方法嗎？我們可以在policy iteration中使用蒙特卡洛方法進行評估，然后使用greedy policy更新。那么依然是有兩種做法。一種就是在一個policy下測試多次，評估完全，然后更新policy，然后再做很多測試。另一種就是不完全評估，每次測試一次完就評估，評估完就更新：第一種做法：第二種做法：兩種做法都能夠收斂，那么顯然第二種做法的速度更快。那么再改進一點，就是改變greedy policy中的值，使得不斷變小趨于0，這個時候最后得到的policy就是完全的最優policy了。這個算法就叫做GLIE Monte-Carlo Control：其他變種：Monte Carlo with Exploring Starts,使用Q(s,a),然后使用上面說的第二種做法，一次episod就更新一次policy，而且policy直接使用Q值。policy的更新使用了greedy，目的就是能夠更好的探索整個狀態空間。4 Off Policy Learning那么上面的方法一直是基于當前的policy，為了探索狀態空間，采用一個次優的策略greedy policy來探索。那么是不是可以更直接的使用兩個policy。一個policy用來探索空間，也就是behavior policy，另一個policy就是為了達到最優policy，叫做target policy。那么這種方法就叫做off policy learning。On-policy的方法比較簡單，off-policy 方法需要更多的概念和標記，比較不好理解，而且，由于behaviour policy和target policy不相關，這種方法比較不容易收斂。但是off-policy更強大，更通用，實際上的on-policy方法就是off-policy方法的一個子集。比如，就可以使用off-policy從人類專家或者傳統的控制算法來學習一個增強學習模型。關鍵是要找到兩個policy之間的權重關系，從而更新Q值。關于off-policy learning的部分，之后結合TD方法再做分析。小結本次blog分析了一下蒙特卡洛方法。這種基于統計學的方法算法簡單，但是更多的只能用于虛擬環境能進行無限測試的情況。并且state 狀態比較有限，離散的最好。基于這個方法，比如簡單的五子棋（棋盤最好小一點），就可以用這個方法來玩玩了。增強學習Reinforcement Learning經典算法梳理3：TD方法1 前言在上一篇blog中，我們分析了蒙特卡洛方法，這個方法的一個特點就是需要運行完整個episode從而獲得準確的result。但是往往很多場景下要運行完整個episode是很費時間的，因此，能不能還是沿著bellman方程的路子，估計一下result呢？并且，注意這里，依然model free。那么什么方法可以做到呢？就是TD（temporal-difference時間差分）方法。有個名詞注意一下：boostraping。所謂boostraping就是有沒有通過估計的方法來引導計算。那么蒙特卡洛不使用boostraping，而TD使用boostraping。接下來具體分析一下TD方法2 TD與MC的不同MC使用準確的return來更新value，而TD則使用Bellman方程中對value的估計方法來估計value，然后將估計值作為value的目標值進行更新。也因此，估計的目標值的設定將衍生出各種TD下的算法。那么TD方法的優勢有什么呢？每一步都可以更新，這是顯然，也就是online learning，學習快；可以面對沒有結果的場景，應用范圍廣不足之處也是顯而易見的，就是因為TD target是估計值，估計是有誤差的，這就會導致更新得到value是有偏差的。很難做到無偏估計。但是以此同時，TD target是每一個step進行估計的，僅最近的動作對其有影響，而MC的result則受到整個時間片中動作的影響，因此TD target的方差variance會比較低，也就是波動性小。還是放一下David Silver的總結吧：那么David Silver的ppt中有三張圖，很清楚的對比了MC，TD以及DP的不同： 從上面可以很清楚的看到三者的不同。DP就是理想化的情況，遍歷所有。MC現實一點，TD最現實，但是TD也最不準確。但是沒關系，反復迭代之下，還是可以收斂的。整個增強學習算法也都在上面的范疇里：3 TD算法這只是TD（0）的估計方式，顯然可以拓展到n-step。就是講TD-target再根據bellman方程展開。再下來的思想，就是可以把TD（i）和TD（j）合在一起求個平均吧。再下來就是把能算的TD（i）都算一遍，每一個給個系數，總和為1，這就是TD()4 SARSA算法SARSA算法的思想很簡單，就是增加一個A，下一步的A，然后據此來估計Q(s,a)。之所以算法稱為SARSA，就是指一次更新需要用到這5個量。5 Q-Learning算法著名的Q-Learning。這里直接使用最大的Q來更新。為什么說SARSA是on-policy而Q-Learning是off-policy呢？因為SARSA只是對policy進行估計，而Q