AI科技評(píng)論按:本文根據(jù)俞揚(yáng)博士在中國(guó)人工智能學(xué)會(huì)AIDL第二期人工智能前沿講習(xí)班“機(jī)器學(xué)習(xí)前沿”所作報(bào)告《強(qiáng)化學(xué)習(xí)前沿》編輯整理而來(lái),AI科技評(píng)論在未改變?cè)獾幕A(chǔ)上略作了刪減,經(jīng)俞揚(yáng)博士指正確認(rèn),特此感謝。全文分為上下兩篇,本文為下篇。 俞揚(yáng)博士、副教授,主要研究領(lǐng)域?yàn)槿斯ぶ悄堋C(jī)器學(xué)習(xí)、演化計(jì)算。分別于2004年和2011年獲得南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系學(xué)士學(xué)位和博士學(xué)位。 2011年8月加入南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系、機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘研究所(LAMDA)從事教學(xué)與科研工作。曾獲2013年全國(guó)優(yōu)秀博士學(xué)位論文獎(jiǎng)、2011年中國(guó)計(jì)算機(jī)學(xué)會(huì)優(yōu)秀博士學(xué)位論文獎(jiǎng)。發(fā)表論文40余篇,包括多篇Artificial Intelligence、IJCAI、AAAI、NIPS、KDD等國(guó)際一流期刊和會(huì)議上,研究成果獲得IDEAL'16、GECCO'11、PAKDD'08最佳論文獎(jiǎng),以及PAKDD’06數(shù)據(jù)挖掘競(jìng)賽冠軍等。 任《Frontiers of Computer Science》青年副編輯,任人工智能領(lǐng)域國(guó)際頂級(jí)會(huì)議IJCAI’15/17高級(jí)程序委員、IJCAI'16/17 Publicity Chair、ICDM'16 Publicity Chair、ACML'16 Workshop Chair。指導(dǎo)的學(xué)生獲天貓“雙十一”推薦大賽百萬(wàn)大獎(jiǎng)、Google獎(jiǎng)學(xué)金等。 在此列出俞揚(yáng)老師講課目錄,以供讀者參考:
上篇介紹了前兩個(gè)小節(jié)的內(nèi)容,以下為下篇內(nèi)容: 三、從馬爾可夫決策過(guò)程到強(qiáng)化學(xué)習(xí)在強(qiáng)化學(xué)習(xí)任務(wù)中,獎(jiǎng)賞和轉(zhuǎn)移都是未知的,需要通過(guò)學(xué)習(xí)得出。具體解決辦法有兩個(gè): 一種是還原出獎(jiǎng)賞函數(shù)和轉(zhuǎn)移函數(shù)。首先把MDP還原出來(lái),然后再在MDP上解這個(gè)策略,這類(lèi)方法稱(chēng)為有模型(Model-Based)方法,這里的模型指的是MDP。 還有一類(lèi)和它相對(duì)應(yīng)的方法,免模型(Model-Free)法,即不還原獎(jiǎng)賞和轉(zhuǎn)移。 基于模型的方法在這類(lèi)方法中,智能體會(huì)維護(hù)Model(即MDP),然后從Model中求解策略。 從隨機(jī)策略開(kāi)始,把策略放到環(huán)境中運(yùn)行,從運(yùn)行的序列數(shù)據(jù)中把MDP恢復(fù)出來(lái)。因?yàn)樾蛄袛?shù)據(jù)可以提供環(huán)境轉(zhuǎn)移和獎(jiǎng)賞的監(jiān)督信息,簡(jiǎn)單的做一個(gè)回歸,就能知道一個(gè)狀態(tài)做了一個(gè)動(dòng)作下面會(huì)轉(zhuǎn)移到哪兒,以及能得到的獎(jiǎng)賞是多少。 這里有一個(gè)非常簡(jiǎn)單的環(huán)境探索方法——RMax,它用了計(jì)數(shù)這個(gè)非常簡(jiǎn)單的回歸模型。 雖然看起來(lái)很簡(jiǎn)單,但是還原MDP的樣本復(fù)雜度是狀態(tài)數(shù)的平方,遠(yuǎn)高于前面說(shuō)到的求解策略的復(fù)雜度。從這里可以看出學(xué)習(xí)MDP的復(fù)雜度極高,所以大量的研究工作都集中在免模型學(xué)習(xí)上。 免模型學(xué)習(xí)免模型學(xué)習(xí)簡(jiǎn)單介紹兩種方法。一種叫做蒙特卡羅采樣方法(Monte-Carlo method),一種是時(shí)序差分法(Temporal difference method)
免模型學(xué)習(xí)和之前講到的策略迭代的思路很像,首先,評(píng)估當(dāng)前策略怎么樣;第二,提高當(dāng)前策略。 第一步 評(píng)估策略 在MDP里評(píng)估策略的時(shí)候,由于獎(jiǎng)賞和轉(zhuǎn)移都是知道的,所以可以直接用這兩個(gè)函數(shù)算評(píng)估值?,F(xiàn)在這兩個(gè)函數(shù)都不知道,那怎么辦呢? 這個(gè)Q值函數(shù)實(shí)際上是個(gè)期望,所以直接用采樣來(lái)替代期望就可以了。換句話說(shuō),就是拿該策略在環(huán)境里面去跑,看跑出來(lái)什么結(jié)果。 比如跑了之后我得到一條軌跡:先是出太陽(yáng),接著是多云,最后是出太陽(yáng);再跑第二次得到一條軌跡,再跑第三次又得到一個(gè)軌跡。最后得到很多軌跡。我知道每條軌跡的獎(jiǎng)賞是多少,然后把這些軌跡的獎(jiǎng)賞平均起來(lái),作為這個(gè)策略的值函數(shù)的估計(jì),用頻率來(lái)逼近期望。 第二步 更新/提高策略 如此一來(lái),我們就可以去評(píng)價(jià)一個(gè)策略的好壞。評(píng)價(jià)完一個(gè)策略以后,就可以和剛才一樣,取Q值函數(shù)指示最好的動(dòng)作作為新的策略,更新過(guò)程是一樣的。 整個(gè)算法寫(xiě)出來(lái)比較簡(jiǎn)單。我們要做m次采樣,每一次都把當(dāng)前的策略拿到環(huán)境里面運(yùn)行,然后會(huì)得到一個(gè)序列,根據(jù)序列讓獎(jiǎng)賞求和,然后更新Q值,這個(gè)Q值就是歷史上采樣的均值,c是計(jì)數(shù)。 在一條軌跡下來(lái)以后,更新Q值后,做第二條軌跡,這樣就做到了不依賴(lài)MDP模型的強(qiáng)化學(xué)習(xí)方法。 然而該方法缺乏環(huán)境探索,難以更新策略 但是,這個(gè)有一個(gè)問(wèn)題——如果得到了確定性策略,那么有可能采100個(gè)樣本出來(lái)的軌跡都是一樣的,導(dǎo)致無(wú)法評(píng)估策略在所有狀態(tài)上的表現(xiàn),所以無(wú)法提高策略。這里的關(guān)鍵在于它缺乏對(duì)環(huán)境的探索。 如何探索環(huán)境,以獲得最大回報(bào)? 怎么探索?我們可以考慮一個(gè)最簡(jiǎn)單的強(qiáng)化學(xué)習(xí)問(wèn)題:一個(gè)狀態(tài),兩個(gè)動(dòng)作,一個(gè)動(dòng)作的回報(bào)高一點(diǎn),一個(gè)動(dòng)作回報(bào)低一點(diǎn),但是這兩個(gè)回報(bào)來(lái)自于兩個(gè)分布。這個(gè)時(shí)候你選哪個(gè)動(dòng)作,或者你怎么做能收到最大的回報(bào)?這其實(shí)就是bandit模型。
第一種情況是要有足夠多的探索(即exploration),第二種情況是不需要過(guò)多的探索而有更好的投資(即exploitation),我們要在這兩點(diǎn)之間找到平衡。 解決這個(gè)問(wèn)題有多種方法。第簡(jiǎn)單的方法是,以1-ε的概率,現(xiàn)在看好哪個(gè),就去投資它,剩下的ε概率就完全隨機(jī),每個(gè)動(dòng)作都去嘗試。這個(gè)方法稱(chēng)為ε-greedy。 該方法可以保證所有狀態(tài)都有一定的概率,哪怕是很小的概率,被訪問(wèn)到。所以當(dāng)運(yùn)行一段時(shí)間以后,它能夠找到最優(yōu)的策略。 但這個(gè)方法也有缺點(diǎn),就是必須要指定一個(gè)ε值。通常這個(gè)值應(yīng)當(dāng)不斷衰減,直到收斂到一個(gè)比較好的結(jié)果。還有一個(gè)效率問(wèn)題,比如A動(dòng)作嘗試了10次以后,平均回報(bào)是1萬(wàn),B動(dòng)作嘗試了10次以后是0.1,這個(gè)時(shí)候就已經(jīng)沒(méi)有必要嘗試下去了,因?yàn)榫嚯x非常遠(yuǎn)。但是ε-greedy的探索不會(huì)停下來(lái),所以有了其他的方法,比如softmax——它會(huì)考慮到Q值本身,如果兩個(gè)動(dòng)作的值差別很大,探索的概率就很小。另一個(gè)在理論上比較漂亮的方法是UCB(Upper Confidence Bound):
所以,按照Q值加上置信度的上界來(lái)選擇動(dòng)作,它就會(huì)自動(dòng)平衡。 不過(guò),最常用的還是第一種ε-greedy方法。給出一個(gè)策略π以后,把它變成探索的策略,即隨機(jī)挑選一個(gè)動(dòng)作,把這個(gè)帶探索的策略放到蒙特卡羅的算法里面。并且,這個(gè)軌跡并不是從π中產(chǎn)生的,而是從帶探索的πε中產(chǎn)生的,這就能保證策略可以不斷更新了。 下面介紹On/Off Policy:學(xué)習(xí)帶探索/不帶探索的策略。 大家可能常聽(tīng)On/Off Policy策略這個(gè)詞。 在蒙特卡洛采樣中使用了πε策略來(lái)采樣,學(xué)的并不是π,是帶探索的πε。因?yàn)橛脕?lái)評(píng)估的數(shù)據(jù),是從帶探索的策略產(chǎn)出來(lái)的,而不是從我們想要學(xué)的策略上產(chǎn)生出來(lái)的。這個(gè)區(qū)別會(huì)導(dǎo)致把探索也作為策略的一部。這種采樣與更新的策略是一樣的算法叫做On Policy。 但很多時(shí)候,我們想學(xué)的實(shí)際是不帶探索的策略,也就是說(shuō)要從帶探索的策略中采樣,但更新的只是策略本身,即Off Policy。這里面臨一個(gè)問(wèn)題就是,采樣并不來(lái)自于當(dāng)前的策略,常用的重要性采樣(Importance Sampling)技術(shù)通過(guò)修改采樣的分布,改成想要的樣子??梢酝ㄟ^(guò)加權(quán)重這個(gè)簡(jiǎn)單的方法,修改策略的分布,然把這個(gè)分布加到具體算法里面去。也就是把獎(jiǎng)賞加了一個(gè)權(quán)重,這樣的算法就變成一個(gè)Off Policy的算法,這樣它學(xué)習(xí)的就是π自己了。 蒙特卡洛算法總結(jié)總體來(lái)說(shuō),蒙特卡洛的算法不是一個(gè)效率很高的算法,但是能夠展現(xiàn)免模型類(lèi)算法的特性。 我們要做這個(gè)策略的評(píng)估,然后做完評(píng)估以后找到一個(gè)改進(jìn)的方向,就可以改進(jìn)這個(gè)算法了;這里,為了使策略能夠有效更新,需要引入對(duì)環(huán)境的探索;而對(duì)環(huán)境的探索里面,要注意On/Off Policy這么兩個(gè)概念。 另外,蒙特卡洛的算法有一個(gè)很顯然的缺陷:一定要拿到整個(gè)軌跡以后,才能更新模型。
那能不能每走一步都更新模型呢?蒙特卡洛算法里面有一個(gè)性質(zhì)——即更新Q值的時(shí)候,實(shí)際上是在更新均值。 更新均值還可以寫(xiě)成:μt = μt-1 + α(xt _ μt-1),意思是剛才我們更新的是Q值(算式如下圖顯示),其中R ? Q(st, at)叫做蒙特卡羅誤差。我們知道,Q是對(duì)獎(jiǎng)賞的一個(gè)估計(jì),R是是采完這個(gè)軌跡以后得到的真實(shí)的獎(jiǎng)賞。換句話說(shuō),Q值d餓更新就是加上就是真實(shí)值和估計(jì)值的差別,即蒙特卡羅誤差。 在TD算法里,我們走了一步得到了一步真實(shí)的獎(jiǎng)賞,再往后走還沒(méi)走,所以不知道后面真實(shí)的獎(jiǎng)賞是多少,但可以通過(guò)之前的Q值來(lái)估計(jì)之后的獎(jiǎng)賞,這兩個(gè)加起來(lái)就是當(dāng)前知道的信息,用它來(lái)替代這個(gè)R,來(lái)減去老的預(yù)估值,我們稱(chēng)這個(gè)過(guò)程為時(shí)序差分。 如果用蒙特卡羅的話,需要先走到底,知道總體的結(jié)果之后,每一步的差別就能算出來(lái);而對(duì)于TDL來(lái)說(shuō),只需要記錄一步的信息,所以可以在線更新自己。
動(dòng)態(tài)規(guī)劃記錄的是所有狀態(tài)上面的信息。而把剛才的蒙特卡羅的error換成了TD errpr,就可以得到新的TD方法的強(qiáng)化學(xué)習(xí)方法。這個(gè)方法就不是采集整個(gè)軌跡了,而是根據(jù)探索的策略,用TDL來(lái)更新Q值,每走一步就更新一下對(duì)當(dāng)前策略的評(píng)判,然后再更新策略。這個(gè)算法叫做SARSA,屬于On Policy,而變成Off Policy的策略,只修改一處,用非探索策略來(lái)計(jì)算TD error,就得到Q-Learning算法。
這是一個(gè)爬格子的問(wèn)題,是典型的經(jīng)典強(qiáng)化學(xué)習(xí)問(wèn)題。 動(dòng)作是上下左右的走,每走一步就會(huì)有一個(gè)-1的獎(jiǎng)賞。從初始狀態(tài)走到最終的狀態(tài),要走最短的路才能使獎(jiǎng)賞最大。圖中有一個(gè)懸崖,一旦走到懸崖獎(jiǎng)賞會(huì)極小,而且還要再退回這個(gè)初始狀態(tài)。 在這里用On Policy SARSA會(huì)有一定的概率去探索,也就有可能會(huì)掉到這個(gè)懸崖下面去,所以獎(jiǎng)賞就會(huì)比較??;而用Q Learning,因?yàn)樽詈蟮牟呗允遣粠魏翁剿鞯?,沒(méi)有任何的隨機(jī)性,所以路徑最短。 這就是兩類(lèi)強(qiáng)化學(xué)習(xí)算法的區(qū)別。你在學(xué)習(xí)過(guò)程中可以看到,Q Learning的值較低,這是因?yàn)閷W(xué)習(xí)的時(shí)候一定要帶探索的學(xué)習(xí),所以你訓(xùn)練的過(guò)程中一定是不斷的去訓(xùn)練。 另外,前面講的TD誤差更新是走一步后的更新,實(shí)際上還可以做兩步的更新、走N步的更新,都是可以的。所以有一種方法就是做很多步的,按照一個(gè)概率加權(quán)把它綜合起來(lái),綜合起來(lái)以后到一個(gè)叫做λ—return,就是走一步、走兩步和走多步的TD。 四、值函數(shù)估計(jì)(Value function approximation)剛才講的所有問(wèn)題,前提是都能用表格表示。但是很多真實(shí)環(huán)境是無(wú)法用表格表示的。所以在強(qiáng)化學(xué)習(xí)發(fā)展的早期,一直沒(méi)辦法用在大規(guī)模的真實(shí)問(wèn)題上去。后來(lái)大家就想,怎么把這個(gè)強(qiáng)化學(xué)習(xí)放在一個(gè)連續(xù)狀態(tài)空間去,甚至說(shuō)放在動(dòng)作也是連續(xù)的情景中,比如控制一架直升機(jī)的。 大家可能覺(jué)得強(qiáng)化學(xué)習(xí)的學(xué)習(xí)過(guò)程和監(jiān)督學(xué)習(xí)之間的差別比較大,算法、模型好像都完全不一樣。但進(jìn)入連續(xù)狀態(tài)空間以后,兩者就會(huì)出現(xiàn)很多相似的地方。 離散狀態(tài)下可以用表格來(lái)表示值函數(shù)或策略;但進(jìn)入連續(xù)狀態(tài)空間就要用一個(gè)函數(shù)的近似來(lái)表示,這個(gè)方法叫做值函數(shù)近似。 比如,我們可以用一個(gè)線性函數(shù)來(lái)表示,V值是表示狀態(tài)s下面的一個(gè)值,狀態(tài)s先有一個(gè)特征的向量φ(s),這個(gè)V值表達(dá)出來(lái)就是一個(gè)線性的參數(shù)乘以特征的內(nèi)積。Q值里面有一個(gè)動(dòng)作,假設(shè)這個(gè)動(dòng)作是離散的,一種方式是把這個(gè)動(dòng)作和狀態(tài)放在一起變成一個(gè)特征,另一種方法是給每一個(gè)動(dòng)作單獨(dú)做一個(gè)模型。 當(dāng)遇到連續(xù)空間的問(wèn)題時(shí),用近似來(lái)表示值函數(shù)V和Q,這個(gè)做法看起來(lái)很自然,但是近似以后會(huì)發(fā)現(xiàn),以往很多的理論結(jié)果就不成立了。 但我們現(xiàn)在先不管那些問(wèn)題,先看做了近似以后怎么來(lái)學(xué)?我們想知道的是,這里的Q值,是希望Q值近似以后,夠盡量逼近真實(shí)的Q值。如果已經(jīng)知道真實(shí)的Q值,怎么逼近呢?最簡(jiǎn)單的方法就是做一個(gè)最小二乘回歸。其中一種解法是求導(dǎo)。求導(dǎo)以后,導(dǎo)數(shù)表示為,真實(shí)的Q和估計(jì)的Q的差值,然后再乘對(duì)Q值模型的導(dǎo)??梢钥吹?,導(dǎo)數(shù)表達(dá)的含義與之前的模特卡羅誤差、TD誤差是一致的,只不過(guò)更新的是參數(shù)w。把這種更新方式套進(jìn)Q learning里,其他地方都沒(méi)有變,只得到了用值函數(shù)逼近的Q-Learning方法。 這個(gè)模型用什么函數(shù)呢?最簡(jiǎn)單就是用線性函數(shù)。但是線性函數(shù)有很多局限的,需要在特征的設(shè)計(jì)上下功夫,這需要很好的人工設(shè)計(jì)。 把它變成非線性函數(shù),一個(gè)常用方法是用神經(jīng)網(wǎng)絡(luò),直接用神經(jīng)網(wǎng)絡(luò)表示Q值。在更新的時(shí)候也很簡(jiǎn)單,只需要把梯度傳到神經(jīng)網(wǎng)絡(luò)中去就可以了,因?yàn)樯窠?jīng)網(wǎng)絡(luò)的BP算法本身也是求梯度。 用批量學(xué)習(xí)改進(jìn)還有一些改進(jìn)的方式。比如說(shuō)我們?cè)谟?xùn)練近似模型的時(shí)候,在一個(gè)樣本上訓(xùn)練可能會(huì)不穩(wěn)定,所以可以用Batch Models的方式,積累一批數(shù)據(jù)來(lái)訓(xùn)練這個(gè)模型。 剛才講的所有訓(xùn)練方法,都是先把V值或者Q值估計(jì)出來(lái),然后再?gòu)闹邪堰@個(gè)策略導(dǎo)出來(lái)。我們稱(chēng)這種方法為基于值函數(shù)的強(qiáng)化學(xué)習(xí)方法。 五、策略搜索(Policy Search)值函數(shù)估計(jì)法存在的問(wèn)題:策略退化但是用值函數(shù)估計(jì)會(huì)有一個(gè)問(wèn)題——這種方法可以收斂到最優(yōu)策略,但前提必須是用表格的表達(dá)方式;如果用的是函數(shù)近似,則會(huì)出現(xiàn)策略退化,即對(duì)Q值估計(jì)越大,策略越差。 舉一個(gè)簡(jiǎn)單的例子,現(xiàn)在有兩個(gè)狀態(tài),一個(gè)是狀態(tài)1,一個(gè)是狀態(tài)2,狀態(tài)1的特征為2,狀態(tài)2的特征為1。我們?cè)O(shè)定獎(jiǎng)賞,使得狀態(tài)2的最優(yōu)V值比狀態(tài)1的要大。這時(shí)如果用一個(gè)線性函數(shù)來(lái)表示這個(gè)V,也就是用W乘以特征,這個(gè)特征只有一維,最優(yōu)的這個(gè)V值2是比1大的,1的特征值要高一點(diǎn),2的特征值要小一點(diǎn),所以最優(yōu)的W就應(yīng)該是個(gè)負(fù)數(shù),這樣會(huì)使得V(2)比V(1)大,因而能導(dǎo)出最優(yōu)策略。 但是基于值函數(shù)的做法是要使得V值盡量靠近最優(yōu)的V值,最優(yōu)的V值又是正值,這樣會(huì)導(dǎo)致這個(gè)W一定是正的,無(wú)法得到最優(yōu)的策略。這樣值函數(shù)估計(jì)得越準(zhǔn),策略越差的現(xiàn)象被稱(chēng)為策略退化。 用策略搜索解決策略退化問(wèn)題為了避免策略退化,我們的方法是直接去找策略,這就是策略搜索。 先把策略參數(shù)化,對(duì)于離散動(dòng)作來(lái)說(shuō),參數(shù)可以做成像Gibbs Policy一樣,即每個(gè)動(dòng)作有一個(gè)參數(shù),然后把它歸一,變成每一個(gè)動(dòng)作有一個(gè)概率。如果是一個(gè)連續(xù)動(dòng)作的話,可以用高斯分布來(lái)描述。里面這個(gè)參數(shù),我在這里寫(xiě)的是一個(gè)線性的過(guò)程,但也可以用神經(jīng)網(wǎng)絡(luò)來(lái)替代。 直接優(yōu)化策略的參數(shù),使得收到的總回報(bào)達(dá)到最大的方法,就是策略搜索(Policy Search)。 策略搜索的優(yōu)勢(shì)策略搜索和基于值函數(shù)的方法相比,優(yōu)缺點(diǎn)各是什么?
第三點(diǎn)用處很大,比如說(shuō)玩“剪刀石頭布”,如果選擇確定性策略,那一定會(huì)輸;一定要做一個(gè)帶概率的輸出才會(huì)贏。 還有另外一個(gè)例子,跟大家講解一下為什么需要隨機(jī)性策略。 骷髏代表走到這就死掉了;最優(yōu)策略肯定是往中間走,但是這里有兩個(gè)灰色格子,它們代表的是不完全觀測(cè)的狀態(tài),即走到灰格子之后不知道該往左邊還是右邊;
這也體現(xiàn)了策略搜索的優(yōu)勢(shì)。 第四,策略搜索和監(jiān)督學(xué)習(xí)的兼容性比較好。 這個(gè)策略是用參數(shù)表達(dá)的,它的目標(biāo)是最大化的獎(jiǎng)賞。最大化獎(jiǎng)賞的意思就是說(shuō),把空間里所有的軌跡枚舉出來(lái)。因?yàn)椴呗援a(chǎn)生這些軌跡是有一定概率的,在某個(gè)狀態(tài)上,策略做出相應(yīng)動(dòng)作的概率是由策略決定的,把所有一條軌跡上所有動(dòng)作的概率相乘,就得出產(chǎn)生這條軌跡的概率。所以它總體的期望回報(bào),就是所有軌跡的期望,也就是每條軌跡的概率乘以每條概率能獲得的獎(jiǎng)賞,這也是總回報(bào)的另外一種寫(xiě)法。這種寫(xiě)法有的好處就在于,它和策略參數(shù)目標(biāo)有關(guān),所以我可以對(duì)獎(jiǎng)賞直接求導(dǎo),來(lái)求解策略。另外一種寫(xiě)法用的是穩(wěn)態(tài)分布(Stationary Distribution),用和上面寫(xiě)法完全等價(jià),意思是完全一樣的,在這里就跳過(guò)不講了。 策略搜索也有一個(gè)缺點(diǎn),其中一個(gè)缺點(diǎn)就是有很多局部最優(yōu)解,失去了全局最優(yōu)的收斂性保障,其次是訓(xùn)練過(guò)程方差非常高。
相信大家都會(huì)求導(dǎo),不過(guò)有一種方式大家可能沒(méi)有見(jiàn)過(guò)——有限差分(Finite Difference),這是早期用來(lái)做策略求導(dǎo)的方法。 那什么時(shí)候會(huì)用到有限差分呢?可能是這個(gè)系統(tǒng)可能太復(fù)雜了,不容易求導(dǎo),那就可以用一個(gè)簡(jiǎn)單的方式來(lái)逼近這個(gè)導(dǎo)數(shù)。拿到一個(gè)參數(shù)θ,θ的導(dǎo)數(shù)就是看一下周?chē)膫€(gè)方向走的比較快,這樣給θ加一個(gè)很小的擾動(dòng)的值,對(duì)θ周?chē)木植窟M(jìn)行采樣,對(duì)那個(gè)采樣增長(zhǎng)得最快,這個(gè)方向就當(dāng)成是一個(gè)導(dǎo)數(shù)方向。這是最簡(jiǎn)單的方法,當(dāng)然這個(gè)方法有很多缺陷,特別是在高維度的情況下,會(huì)需要很多采樣,所以更直接的方法還是直接求導(dǎo)。 最后得到的一個(gè)導(dǎo)數(shù),導(dǎo)數(shù)形式如下所示:
E是期望,1到T代表考慮的是T步的軌跡,每一步軌跡對(duì)策略輸出值的對(duì)數(shù)取導(dǎo)數(shù),然后乘以真實(shí)的獎(jiǎng)賞(獎(jiǎng)賞不取對(duì)數(shù))。獎(jiǎng)賞是個(gè)常數(shù),即軌跡得到的獎(jiǎng)賞值。 可以通過(guò)采樣可以來(lái)逼近期望,對(duì)一個(gè)策略以后,去跑一些軌跡,然后計(jì)算平均梯度,作為梯度期望的逼近。 我們剛剛說(shuō)到,這種方式有一個(gè)很大的缺陷,就是它的方差很大,直接用計(jì)算的梯度來(lái)更新策略(vallina policy gradient),基本上得不到好的策略,因?yàn)樗姆讲钐?,不穩(wěn)定。 控制方差的方法 1、Actor-Critic控制方差有多種方式,其中一種叫做Actor-Critic。用比如直接求導(dǎo)的方式把策略求出來(lái),叫做Actor;對(duì)值函數(shù)進(jìn)行估計(jì),并用于評(píng)估策略,是Critic,意為它是一個(gè)評(píng)價(jià)者。 我們要維護(hù)一個(gè)值函數(shù)Q的模型。另外,用導(dǎo)數(shù)的方法來(lái)求策略的梯度的時(shí)候,不做直接使用獎(jiǎng)賞,而是使用Criitic提供的Q值。所以Actor-Critic會(huì)維護(hù)兩個(gè)模型,第一個(gè)是策略的模型,第二個(gè)是Q函數(shù)的模型。 對(duì)Q函數(shù)求近似的時(shí)候,式子和上面的那個(gè)導(dǎo)數(shù)形式一樣,里面的經(jīng)驗(yàn)獎(jiǎng)賞換成了Q值。在求策略梯度時(shí),Q值是一個(gè)常數(shù),是不更新的,它有自己的更新方式,且通常是真實(shí)的Q值。 控制方差的方法2、引入偏差項(xiàng)(bias term)另一種控制方差的形式,是引入偏差項(xiàng),只要這個(gè)函數(shù)是一個(gè)只跟狀態(tài)有關(guān)、跟動(dòng)作無(wú)關(guān)的函數(shù),它的積分就是0,不影響梯度方向,而會(huì)影響梯度的方差。 對(duì)于簡(jiǎn)單的形式,我們可以直接求出來(lái)最優(yōu)的偏差是什么。更一般的形式,我們可以用V值來(lái)替代bias。因?yàn)閂值就是關(guān)于狀態(tài)的估計(jì)值,和動(dòng)作沒(méi)有關(guān)系,所以它帶到積分里面去的時(shí)候會(huì)是0。 把V值帶進(jìn)去,后面的Q就變成了Q-V,叫做Advantage Function,意思指:在這個(gè)狀態(tài)上,V值相當(dāng)于是一個(gè)平均值,Q值指某個(gè)動(dòng)作比平均值高出來(lái)多少。用Advantage Function會(huì)使得做策略梯度以后,方差控制得比較好,只有當(dāng)方差控制好了,這類(lèi)算法才能真正起作用。 其他改進(jìn)方法梯度的改進(jìn)方法還有Nature Policy Gradient。在監(jiān)督學(xué)習(xí)里面,隨機(jī)梯度是很容易并行的。最近有一些理論的工作,也探討了它的并行不會(huì)影響到它的理論性質(zhì)。在策略梯度里面,我們同樣可以把這個(gè)梯度并行來(lái)做,這樣可以使得它的速度下的很快。 還有對(duì)策略直接求導(dǎo)的方法,比如無(wú)梯度的優(yōu)化(Derivative-Free Optimization)。這類(lèi)方法不管強(qiáng)化學(xué)習(xí)是在做什么,而是直接優(yōu)化策略里面的參數(shù)。優(yōu)化完參數(shù)以后,試一下策略,得出這個(gè)值具體是多少。 這樣,優(yōu)化過(guò)的算法可以通過(guò)總體獎(jiǎng)賞值來(lái)調(diào)整模型里面的參數(shù)。通常來(lái)說(shuō)它比用Gradient Policy效率差,由于中間過(guò)程是忽略不計(jì)的,所以它對(duì)特別復(fù)雜的問(wèn)題,反而有比較好的效果,比如俄羅斯方塊游戲。 六、游戲中的強(qiáng)化學(xué)習(xí)(Reinforcement Learning in Games)最后一部分,講一下強(qiáng)化學(xué)習(xí)和游戲。 為什么講游戲?一方面,是因?yàn)樵谟螒蚶锩嫘枰朔囊恍﹩?wèn)題,在真實(shí)應(yīng)用中也常遇到;另外一方面,用游戲來(lái)做強(qiáng)化學(xué)習(xí)任務(wù)的成本比較低。
2015年,DeepMind在Atari游戲上使用深度網(wǎng)絡(luò)直接從屏幕圖像訓(xùn)練強(qiáng)化學(xué)習(xí),直接推動(dòng)了“深度強(qiáng)化學(xué)習(xí)”的發(fā)展。 用深度神經(jīng)網(wǎng)絡(luò),放在Policy Gradient里面,作為一個(gè)策略的模型;或者放在基于值函數(shù)的方法里面,作為值函數(shù)Q值的一個(gè)估計(jì)。這樣的方法就稱(chēng)為深度強(qiáng)化學(xué)習(xí)。 深度強(qiáng)化學(xué)習(xí)其實(shí),深度強(qiáng)化學(xué)習(xí)里很多工作是在研究怎么讓網(wǎng)絡(luò)更穩(wěn)定。特別是當(dāng)輸入數(shù)據(jù)比較少的時(shí)候,網(wǎng)絡(luò)方差的浮動(dòng)會(huì)比較大。這就可以用“延后更新”來(lái)解決——如果用深度神經(jīng)網(wǎng)絡(luò),那么每走一步都更新模型會(huì)導(dǎo)致模型抖動(dòng)非常大。而用“延后更新”,例如可以在100步里不更新策略,只是把神經(jīng)網(wǎng)絡(luò)更新一下,這個(gè)神經(jīng)網(wǎng)絡(luò)沒(méi)有放到新的策略里面來(lái),等神經(jīng)網(wǎng)絡(luò)有一個(gè)比較穩(wěn)定的上升以后,再更新策略。還有,積累的數(shù)據(jù)不要丟掉,也拿出來(lái),讓這個(gè)神經(jīng)網(wǎng)絡(luò)更穩(wěn)定一點(diǎn)。這兩個(gè)技巧合起來(lái)放在Q-Learning里面,就是DQN。
DQN可以說(shuō)是第一個(gè)聲稱(chēng)深度強(qiáng)化學(xué)習(xí)算法,可能也是最廣為人知的一個(gè)。基本上,它的整體結(jié)構(gòu)就是一個(gè)函數(shù)近似的Q Learning,只不過(guò)用CNN做了近似函數(shù)。 在玩這個(gè)游戲的時(shí)候,它已經(jīng)有了100萬(wàn)個(gè)記錄歷史。每次訓(xùn)練神經(jīng)網(wǎng)絡(luò)的時(shí)候,要抓32個(gè)出來(lái)訓(xùn)練一次,并且訓(xùn)練完以后不去更新策略,而是在走一定的步數(shù)以后,再更新這個(gè)策略。除此之外,并不是直接從屏幕上把一幀圖像拿進(jìn)來(lái),而是把歷史上好幾幀的屏幕拼起來(lái),得到一個(gè)當(dāng)前幀和前面好幾幀合起來(lái)的一個(gè)總體的圖作為CNN的輸入。不過(guò)在最新的一些工作中,這個(gè)過(guò)程已經(jīng)被被遞歸神經(jīng)網(wǎng)絡(luò)替代了,不再是把好幾層拼起來(lái),而是讓好幾幀分別輸入例如LSTM的網(wǎng)絡(luò)。 很多運(yùn)用強(qiáng)化學(xué)習(xí)尋找策略的游戲已經(jīng)比人玩得都好了,它玩的好的優(yōu)勢(shì)主要體現(xiàn)在反應(yīng)速度上。但是在需要深入思考邏輯關(guān)系的游戲中,強(qiáng)化學(xué)習(xí)沒(méi)有人做得好。 我們來(lái)看看它的游戲報(bào)告結(jié)果。 這里面,“with replay”和“without replay”的意思是有沒(méi)有用到歷史數(shù)據(jù),“with target Q”和“without target Q”就用了CNN還是線性網(wǎng)絡(luò)。我們可以看到,神經(jīng)網(wǎng)絡(luò)在這里貢獻(xiàn)并不是最大的。如果我們只用神經(jīng)網(wǎng)絡(luò)而不用replay的話,效果還不如用了replay,但只用線性模型而不用CNN。當(dāng)然,同時(shí)使用深度模型和強(qiáng)化學(xué)習(xí)是最好的,這可以完成一些過(guò)去完成不了的事情。 在AlphaGo中的應(yīng)用AlphaGo系統(tǒng)的基礎(chǔ)框架是蒙特卡洛樹(shù)搜索,這是經(jīng)典的樹(shù)搜索的方法。但是單憑蒙特卡洛樹(shù)搜索本身并不能取得很好的效果,只用樹(shù)搜索大概只能達(dá)到業(yè)余的五六段。AlphaGo里面的一個(gè)創(chuàng)新的點(diǎn)就是引入強(qiáng)化學(xué)習(xí)來(lái)改進(jìn)搜索樹(shù)的深度和寬度。 這里面用了三個(gè)神經(jīng)網(wǎng)絡(luò)。
由于大家對(duì)DQN比較熟悉,所以在嘗試深度學(xué)習(xí)的時(shí)候,首先想到的算法大多是DQN。但因?yàn)樗且粋€(gè)基于值函數(shù)估計(jì)的強(qiáng)化學(xué)習(xí)方法,所以這種方法在稍微復(fù)雜一點(diǎn)的應(yīng)用環(huán)境中可能運(yùn)行不了,大家會(huì)感覺(jué)用DQN做強(qiáng)化學(xué)習(xí)效果沒(méi)那么好。但同樣是DeepMin做的圍棋游戲,它的強(qiáng)化學(xué)習(xí)方法已經(jīng)改成了Policy Gradient,而且以后的很多算法也都是以Policy Gradient為主的,用這種方法處理復(fù)雜問(wèn)題效果更好。 在其他游戲上的應(yīng)用正是由于在計(jì)算機(jī)中模擬游戲的代價(jià)很低,所以不斷有研究者借助游戲來(lái)發(fā)展強(qiáng)化學(xué)習(xí)。比如,有用在3D第一人稱(chēng)射擊游戲中,可以在這個(gè)世界里面行走,并且尋找東西。去年有一個(gè)“DOOM”游戲比賽,參賽者要用計(jì)算機(jī)控制游戲角色,以第一視角進(jìn)行3D射擊。有了強(qiáng)化學(xué)習(xí),參賽者就能控制游戲角色,讓它做一些動(dòng)作。由于這個(gè)游戲額環(huán)境比較復(fù)雜,所以在玩游戲的過(guò)程中,也發(fā)展出了一些創(chuàng)新方法。 例如,在游戲里面,如果讓一個(gè)強(qiáng)化學(xué)習(xí)直接到游戲環(huán)境里面學(xué)習(xí),那它又要撿醫(yī)療箱,又要去撿武器等等,太復(fù)雜了。而其中一個(gè)團(tuán)隊(duì),就采取了這樣的做法:他們讓強(qiáng)化學(xué)習(xí)從簡(jiǎn)單到復(fù)雜,一步一步的去學(xué)習(xí)——首先學(xué)一個(gè)策略,比如撿起醫(yī)療箱,然后在這個(gè)策略的基礎(chǔ)上再來(lái)學(xué)怎么樣來(lái)開(kāi)槍、怎么樣來(lái)射擊敵人等等。 實(shí)際上游戲里面有很多很高難度的挑戰(zhàn),其中一個(gè)非常復(fù)雜游戲叫做StarCraft。這個(gè)游戲已經(jīng)有很多年的歷史了,現(xiàn)在有不少人,包括DeepMind,都希望在這么復(fù)雜的游戲上面能表現(xiàn)出一個(gè)比較好的性能,因?yàn)檫@個(gè)游戲的復(fù)雜度已經(jīng)大到和很多真實(shí)應(yīng)用的復(fù)雜度相當(dāng),即使人去學(xué)這個(gè)游戲,也要花很長(zhǎng)時(shí)間才能學(xué)會(huì)。以前用強(qiáng)化學(xué)習(xí),只是先取其中一個(gè)小問(wèn)題來(lái)解決。比如說(shuō)我和對(duì)方各派三個(gè)兵,想辦法看這六個(gè)兵怎么打。這是一個(gè)很局部的戰(zhàn)役,但能學(xué)到這樣的東西也已經(jīng)比較不錯(cuò)了。如果要學(xué)到整盤(pán)的打法,它里面涉及到很多問(wèn)題,第一,它的規(guī)模遠(yuǎn)大于圍棋的規(guī)模;第二,有很多對(duì)手的信息是觀測(cè)不到的,比如敵方的行動(dòng)。雖然在今年年初,德州撲克游戲上機(jī)器已經(jīng)打贏了人類(lèi)玩家,但德州撲克其實(shí)是一類(lèi)很簡(jiǎn)單的牌類(lèi)游戲,想讓強(qiáng)化學(xué)習(xí)在大規(guī)模游戲任務(wù)中,在無(wú)法觀測(cè)到對(duì)手信息的情況下,指揮200多個(gè)單位做連續(xù)的運(yùn)動(dòng),還要持續(xù)半個(gè)多小時(shí)走幾十萬(wàn)步,目前還做不好。 七、強(qiáng)化學(xué)習(xí)總結(jié) 之前介紹的只是強(qiáng)化學(xué)習(xí)的其中一小部分,強(qiáng)化學(xué)習(xí)還包括很多內(nèi)容: 比如在MDP中如果出現(xiàn)了不可觀測(cè)的情況,它就不屬于Markov了,有一個(gè)專(zhuān)門(mén)的方向如POMDP來(lái)解決這個(gè)問(wèn)題。 還有Learning from Demonstrations,意為人先做出示范,然后從示范數(shù)據(jù)中教智能體。例如AlphaGo,一開(kāi)始訓(xùn)練的時(shí)候并不是直接上強(qiáng)化學(xué)習(xí),而是首先搜集了很多人類(lèi)對(duì)打的數(shù)據(jù)。 而怎么去設(shè)計(jì)獎(jiǎng)賞函數(shù)也會(huì)有很多不同的方法。 下面總結(jié)一下兩個(gè)大家比較關(guān)心的問(wèn)題。
如果碰到比較簡(jiǎn)單的強(qiáng)化學(xué)習(xí)問(wèn)題,可以用基于值函數(shù)的方法,比如DQN,更復(fù)雜的問(wèn)題可以用Policy Gradient的方法做策略梯度。 但是從目前的發(fā)展現(xiàn)狀兩看,強(qiáng)化學(xué)習(xí)的成熟度遠(yuǎn)遠(yuǎn)不夠,也就是說(shuō)在強(qiáng)化學(xué)習(xí)領(lǐng)域,還有很大的提升的空間,有可能能做出一個(gè)性能更好的全新的算法。但大規(guī)模的問(wèn)題現(xiàn)在還是很難解決。這個(gè)大規(guī)模指是它的狀態(tài)空間大,并且步數(shù)特別多。
1、 強(qiáng)化學(xué)習(xí)需要探索,在很多場(chǎng)景帶來(lái)風(fēng)險(xiǎn)。 以推薦股票為例。我本來(lái)已經(jīng)有一個(gè)還可以的推薦策略,每天能給我?guī)?lái)100萬(wàn)的收入。但是現(xiàn)在為了訓(xùn)練強(qiáng)化學(xué)習(xí),要做探索,嘗試一些隨機(jī)的股票。假如告訴你這個(gè)探索會(huì)導(dǎo)致今天一下子要損失好幾百萬(wàn),而一個(gè)月以后可以賺回1個(gè)億,那你就要衡量一下這里看面的風(fēng)險(xiǎn)有多高,敢不敢用了。 2、 為什么強(qiáng)化學(xué)習(xí)在很多游戲上面用的比較多? 游戲在計(jì)算機(jī)中運(yùn)行,速度高、代價(jià)低。如果放到現(xiàn)實(shí)世界中來(lái)運(yùn)行,比如放在推薦系統(tǒng)線上運(yùn)行,那它就必須和真實(shí)的環(huán)境打交道。它的學(xué)習(xí)過(guò)程需要不斷探索,而部署在真實(shí)環(huán)境里可能會(huì)遇到很多麻煩,如果能有一個(gè)比較好的模擬器,就可以減少這些麻煩;另外,如果有比較好的監(jiān)督學(xué)習(xí)數(shù)據(jù)的話,也可以做一個(gè)初始的策略,不過(guò)這個(gè)策略可能一開(kāi)始起點(diǎn)要稍微高一點(diǎn)。做機(jī)器人一般也有一個(gè)機(jī)器人模擬器,所以一般先在模擬器里面做,做好策略再放到機(jī)器人身上來(lái)學(xué)。但是其他現(xiàn)實(shí)世界問(wèn)題,在模擬器里可能就沒(méi)有那么好做了。 八、強(qiáng)化學(xué)習(xí)資源推薦書(shū)籍強(qiáng)化學(xué)習(xí)的書(shū)不多,最經(jīng)典的書(shū)是Richard S. Sutton的教科書(shū);Masashi Sugiyama的書(shū)屬于專(zhuān)著;Reinforcement Learning: State-of-the-Art屬于文集,覆蓋面比較廣,但需要讀者有一定基礎(chǔ);還有一些講述MDP的書(shū);另外,在機(jī)器學(xué)習(xí)的書(shū)里面也會(huì)提到強(qiáng)化學(xué)習(xí)。 線上資源OpenAI Gym:一個(gè)基礎(chǔ)的強(qiáng)化學(xué)習(xí)平臺(tái),里面很多環(huán)境,研究人員可以在上面做實(shí)驗(yàn),它對(duì)這個(gè)領(lǐng)域有很大的促進(jìn)。還有AlphaGo技術(shù)負(fù)責(zé)人David Silver的線上教學(xué)視頻,講的非常好。 論文發(fā)表地強(qiáng)化學(xué)習(xí)論文主要發(fā)表在AI期刊和會(huì)議上,期刊有Artificial Intelligence, JAIR, JMLR, Machine Learning, JAAMAS等,會(huì)議有IJCAI, AAAI, NIPS, ICML, ICLR, AAMAS, IROS等等。 以上就是俞揚(yáng)博士的演講,更多內(nèi)容請(qǐng)繼續(xù)關(guān)注AI科技評(píng)論。 報(bào)名 |【2017 AI 最佳雇主】榜單 在人工智能爆發(fā)初期的時(shí)代背景下,雷鋒網(wǎng)聯(lián)合旗下人工智能頻道AI科技評(píng)論,攜手《環(huán)球科學(xué)》和 BOSS 直聘,重磅推出【2017 AI 最佳雇主】榜單。 從“公司概況”、“創(chuàng)新能力”、“員工福利”三個(gè)維度切入,依據(jù) 20 多項(xiàng)評(píng)分標(biāo)準(zhǔn),做到公平、公正、公開(kāi),全面評(píng)估和推動(dòng)中國(guó)人工智能企業(yè)發(fā)展。 本次【2017 AI 最佳雇主】榜單活動(dòng)主要經(jīng)歷三個(gè)重要時(shí)段:
最終榜單名單由雷鋒網(wǎng)、AI科技評(píng)論、《環(huán)球科學(xué)》、BOSS 直聘以及 AI 學(xué)術(shù)大咖組成的評(píng)審團(tuán)共同選出,并于7月份舉行的 CCF-GAIR 2017大會(huì)期間公布。報(bào)名期間歡迎大家踴躍自薦或推薦心目中的最佳 AI 企業(yè)公司。 報(bào)名方式 |
|