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

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