增強(qiáng)學(xué)習(xí)Reinforcement Learning經(jīng)典算法梳理.doc

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