秒懂 | 南京大學俞揚博士獨家演講：強化學習前沿（下）

anyyss 2018-04-21

展開全文

AI科技評論按：本文根據(jù)俞揚博士在中國人工智能學會AIDL第二期人工智能前沿講習班“機器學習前沿”所作報告《強化學習前沿》編輯整理而來,，AI科技評論在未改變原意的基礎(chǔ)上略作了刪減，經(jīng)俞揚博士指正確認,，特此感謝,。全文分為上下兩篇，本文為下篇,。

俞揚博士,、副教授，主要研究領(lǐng)域為人工智能,、機器學習,、演化計算。分別于2004年和2011年獲得南京大學計算機科學與技術(shù)系學士學位和博士學位,。

2011年8月加入南京大學計算機科學與技術(shù)系,、機器學習與數(shù)據(jù)挖掘研究所（LAMDA）從事教學與科研工作。曾獲2013年全國優(yōu)秀博士學位論文獎,、2011年中國計算機學會優(yōu)秀博士學位論文獎,。發(fā)表論文40余篇，包括多篇Artificial Intelligence,、IJCAI,、AAAI、NIPS,、KDD等國際一流期刊和會議上,，研究成果獲得IDEAL'16、GECCO'11,、PAKDD'08最佳論文獎,，以及PAKDD’06數(shù)據(jù)挖掘競賽冠軍等,。

任《Frontiers of Computer Science》青年副編輯，任人工智能領(lǐng)域國際頂級會議IJCAI’15/17高級程序委員,、IJCAI'16/17 Publicity Chair,、ICDM'16 Publicity Chair、ACML'16 Workshop Chair,。指導的學生獲天貓“雙十一”推薦大賽百萬大獎,、Google獎學金等。

在此列出俞揚老師講課目錄,，以供讀者參考：

一,、介紹（Introduction）
二、馬爾可夫決策過程（Markov Decision Process）
三,、從馬爾可夫決策過程到強化學習（from Markov Decision Process to Reinforce Learning）
四,、值函數(shù)估計（Value function approximation）
五、策略搜索（Policy Search）
六,、游戲中的強化學習（Reinforcement Learning in Games）
七,、強化學習總結(jié)
八、強化學習資源推薦

上篇介紹了前兩個小節(jié)的內(nèi)容,，以下為下篇內(nèi)容：

三,、從馬爾可夫決策過程到強化學習

在強化學習任務(wù)中，獎賞和轉(zhuǎn)移都是未知的,，需要通過學習得出,。具體解決辦法有兩個：

一種是還原出獎賞函數(shù)和轉(zhuǎn)移函數(shù)。首先把MDP還原出來,，然后再在MDP上解這個策略,，這類方法稱為有模型（Model-Based）方法，這里的模型指的是MDP,。

還有一類和它相對應(yīng)的方法,，免模型（Model-Free）法，即不還原獎賞和轉(zhuǎn)移,。

基于模型的方法

在這類方法中,，智能體會維護Model（即MDP），然后從Model中求解策略,。

從隨機策略開始,，把策略放到環(huán)境中運行，從運行的序列數(shù)據(jù)中把MDP恢復出來,。因為序列數(shù)據(jù)可以提供環(huán)境轉(zhuǎn)移和獎賞的監(jiān)督信息,，簡單的做一個回歸，就能知道一個狀態(tài)做了一個動作下面會轉(zhuǎn)移到哪兒，以及能得到的獎賞是多少,。

這里有一個非常簡單的環(huán)境探索方法——RMax,，它用了計數(shù)這個非常簡單的回歸模型。

雖然看起來很簡單,，但是還原MDP的樣本復雜度是狀態(tài)數(shù)的平方,，遠高于前面說到的求解策略的復雜度。從這里可以看出學習MDP的復雜度極高,，所以大量的研究工作都集中在免模型學習上,。

免模型學習

免模型學習簡單介紹兩種方法。一種叫做蒙特卡羅采樣方法（Monte-Carlo method）,，一種是時序差分法（Temporal difference method）

蒙特卡羅采樣方法介紹（Monte-Carlo method）

免模型學習和之前講到的策略迭代的思路很像,，首先，評估當前策略怎么樣,；第二,，提高當前策略。

第一步評估策略

在MDP里評估策略的時候,，由于獎賞和轉(zhuǎn)移都是知道的,，所以可以直接用這兩個函數(shù)算評估值。現(xiàn)在這兩個函數(shù)都不知道,，那怎么辦呢,？

這個Q值函數(shù)實際上是個期望,，所以直接用采樣來替代期望就可以了,。換句話說，就是拿該策略在環(huán)境里面去跑,，看跑出來什么結(jié)果,。

比如跑了之后我得到一條軌跡：先是出太陽，接著是多云,，最后是出太陽,；再跑第二次得到一條軌跡，再跑第三次又得到一個軌跡,。最后得到很多軌跡,。我知道每條軌跡的獎賞是多少，然后把這些軌跡的獎賞平均起來,，作為這個策略的值函數(shù)的估計,，用頻率來逼近期望。

第二步更新/提高策略

如此一來,，我們就可以去評價一個策略的好壞,。評價完一個策略以后，就可以和剛才一樣,，取Q值函數(shù)指示最好的動作作為新的策略,，更新過程是一樣的,。

整個算法寫出來比較簡單。我們要做m次采樣,，每一次都把當前的策略拿到環(huán)境里面運行,，然后會得到一個序列，根據(jù)序列讓獎賞求和,，然后更新Q值,，這個Q值就是歷史上采樣的均值，c是計數(shù),。

在一條軌跡下來以后,，更新Q值后，做第二條軌跡,，這樣就做到了不依賴MDP模型的強化學習方法,。

然而該方法缺乏環(huán)境探索，難以更新策略

但是,，這個有一個問題——如果得到了確定性策略,，那么有可能采100個樣本出來的軌跡都是一樣的，導致無法評估策略在所有狀態(tài)上的表現(xiàn),，所以無法提高策略,。這里的關(guān)鍵在于它缺乏對環(huán)境的探索。

如何探索環(huán)境,，以獲得最大回報,？

怎么探索？我們可以考慮一個最簡單的強化學習問題：一個狀態(tài),，兩個動作,，一個動作的回報高一點，一個動作回報低一點,，但是這兩個回報來自于兩個分布,。這個時候你選哪個動作，或者你怎么做能收到最大的回報,？這其實就是bandit模型,。

一個極端是，嘗試100次,，每個動作做50次,，這個時候我可能知道哪個動作比較好，但是拿到的回報可能不是最高的,，因為可能做10次以后,，就已經(jīng)知道第一個動作的回報要高一點了，如果剩下的投資還是均勻分布的話，就得不到最大回報,。
另一個極端是,，兩個動作各試一次，看哪個回報高,，剩下的98次全部投到最高的回報去,。這個方法也不好，因為只試了1次,，估計的回報很不穩(wěn)定,。

第一種情況是要有足夠多的探索（即exploration），第二種情況是不需要過多的探索而有更好的投資（即exploitation）,，我們要在這兩點之間找到平衡,。

解決這個問題有多種方法。第簡單的方法是,，以1-ε的概率,，現(xiàn)在看好哪個，就去投資它,，剩下的ε概率就完全隨機,，每個動作都去嘗試。這個方法稱為ε-greedy,。

該方法可以保證所有狀態(tài)都有一定的概率,，哪怕是很小的概率，被訪問到,。所以當運行一段時間以后,，它能夠找到最優(yōu)的策略。

但這個方法也有缺點,，就是必須要指定一個ε值,。通常這個值應(yīng)當不斷衰減,，直到收斂到一個比較好的結(jié)果,。還有一個效率問題，比如A動作嘗試了10次以后,，平均回報是1萬,，B動作嘗試了10次以后是0.1，這個時候就已經(jīng)沒有必要嘗試下去了,，因為距離非常遠,。但是ε-greedy的探索不會停下來，所以有了其他的方法,，比如softmax——它會考慮到Q值本身,，如果兩個動作的值差別很大，探索的概率就很小。另一個在理論上比較漂亮的方法是UCB（Upper Confidence Bound）：

第一,，考慮了Q值,。如果Q值本身差距比較大，探索的可能性就很??；
第二，考慮了探索次數(shù),。如果探索次數(shù)很少,，可能它的置信度就比較低，如果探索的次數(shù)較多,，置信度就會比較高,。

所以，按照Q值加上置信度的上界來選擇動作,，它就會自動平衡,。

不過，最常用的還是第一種ε-greedy方法,。給出一個策略π以后,，把它變成探索的策略，即隨機挑選一個動作,，把這個帶探索的策略放到蒙特卡羅的算法里面,。并且，這個軌跡并不是從π中產(chǎn)生的,，而是從帶探索的πε中產(chǎn)生的,，這就能保證策略可以不斷更新了。

下面介紹On/Off Policy：學習帶探索/不帶探索的策略,。

大家可能常聽On/Off Policy策略這個詞,。

在蒙特卡洛采樣中使用了πε策略來采樣，學的并不是π,，是帶探索的πε,。因為用來評估的數(shù)據(jù)，是從帶探索的策略產(chǎn)出來的,，而不是從我們想要學的策略上產(chǎn)生出來的,。這個區(qū)別會導致把探索也作為策略的一部。這種采樣與更新的策略是一樣的算法叫做On Policy,。

但很多時候,，我們想學的實際是不帶探索的策略，也就是說要從帶探索的策略中采樣,，但更新的只是策略本身,，即Off Policy,。這里面臨一個問題就是，采樣并不來自于當前的策略,，常用的重要性采樣（Importance Sampling）技術(shù)通過修改采樣的分布,，改成想要的樣子?？梢酝ㄟ^加權(quán)重這個簡單的方法,，修改策略的分布，然把這個分布加到具體算法里面去,。也就是把獎賞加了一個權(quán)重,，這樣的算法就變成一個Off Policy的算法，這樣它學習的就是π自己了,。

蒙特卡洛算法總結(jié)

總體來說,，蒙特卡洛的算法不是一個效率很高的算法，但是能夠展現(xiàn)免模型類算法的特性,。

我們要做這個策略的評估,，然后做完評估以后找到一個改進的方向，就可以改進這個算法了,；這里,，為了使策略能夠有效更新，需要引入對環(huán)境的探索,；而對環(huán)境的探索里面,，要注意On/Off Policy這么兩個概念。

另外,，蒙特卡洛的算法有一個很顯然的缺陷：一定要拿到整個軌跡以后,，才能更新模型。

時序差分（Temporal difference method）

那能不能每走一步都更新模型呢,？蒙特卡洛算法里面有一個性質(zhì)——即更新Q值的時候,，實際上是在更新均值。

更新均值還可以寫成：μt = μt-1 + α(xt _ μt-1),，意思是剛才我們更新的是Q值（算式如下圖顯示）,，其中R ? Q(st, at)叫做蒙特卡羅誤差。我們知道,，Q是對獎賞的一個估計,，R是是采完這個軌跡以后得到的真實的獎賞。換句話說,，Q值d餓更新就是加上就是真實值和估計值的差別，即蒙特卡羅誤差,。

在TD算法里,，我們走了一步得到了一步真實的獎賞,，再往后走還沒走，所以不知道后面真實的獎賞是多少,，但可以通過之前的Q值來估計之后的獎賞,，這兩個加起來就是當前知道的信息，用它來替代這個R,，來減去老的預(yù)估值,，我們稱這個過程為時序差分。

如果用蒙特卡羅的話,，需要先走到底,，知道總體的結(jié)果之后，每一步的差別就能算出來,；而對于TDL來說,，只需要記錄一步的信息，所以可以在線更新自己,。

SARSA

動態(tài)規(guī)劃記錄的是所有狀態(tài)上面的信息,。而把剛才的蒙特卡羅的error換成了TD errpr，就可以得到新的TD方法的強化學習方法,。這個方法就不是采集整個軌跡了,，而是根據(jù)探索的策略，用TDL來更新Q值,，每走一步就更新一下對當前策略的評判,，然后再更新策略。這個算法叫做SARSA,，屬于On Policy,，而變成Off Policy的策略，只修改一處,，用非探索策略來計算TD error,，就得到Q-Learning算法。

SARSA v.s. Q-learning

這是一個爬格子的問題,，是典型的經(jīng)典強化學習問題,。

動作是上下左右的走，每走一步就會有一個-1的獎賞,。從初始狀態(tài)走到最終的狀態(tài),，要走最短的路才能使獎賞最大。圖中有一個懸崖,，一旦走到懸崖獎賞會極小,，而且還要再退回這個初始狀態(tài)。

在這里用On Policy SARSA會有一定的概率去探索,，也就有可能會掉到這個懸崖下面去,，所以獎賞就會比較?。欢肣 Learning,，因為最后的策略是不帶任何探索的,，沒有任何的隨機性，所以路徑最短,。

這就是兩類強化學習算法的區(qū)別,。你在學習過程中可以看到，Q Learning的值較低,，這是因為學習的時候一定要帶探索的學習,，所以你訓練的過程中一定是不斷的去訓練。

另外,，前面講的TD誤差更新是走一步后的更新,，實際上還可以做兩步的更新、走N步的更新,，都是可以的,。所以有一種方法就是做很多步的，按照一個概率加權(quán)把它綜合起來,，綜合起來以后到一個叫做λ—return,，就是走一步、走兩步和走多步的TD,。

四,、值函數(shù)估計（Value function approximation）

剛才講的所有問題，前提是都能用表格表示,。但是很多真實環(huán)境是無法用表格表示的,。所以在強化學習發(fā)展的早期，一直沒辦法用在大規(guī)模的真實問題上去,。后來大家就想,，怎么把這個強化學習放在一個連續(xù)狀態(tài)空間去，甚至說放在動作也是連續(xù)的情景中,，比如控制一架直升機的,。

大家可能覺得強化學習的學習過程和監(jiān)督學習之間的差別比較大，算法,、模型好像都完全不一樣,。但進入連續(xù)狀態(tài)空間以后，兩者就會出現(xiàn)很多相似的地方,。

離散狀態(tài)下可以用表格來表示值函數(shù)或策略,；但進入連續(xù)狀態(tài)空間就要用一個函數(shù)的近似來表示，這個方法叫做值函數(shù)近似,。

比如,，我們可以用一個線性函數(shù)來表示,，V值是表示狀態(tài)s下面的一個值,，狀態(tài)s先有一個特征的向量φ（s）,，這個V值表達出來就是一個線性的參數(shù)乘以特征的內(nèi)積。Q值里面有一個動作,，假設(shè)這個動作是離散的,，一種方式是把這個動作和狀態(tài)放在一起變成一個特征，另一種方法是給每一個動作單獨做一個模型,。

當遇到連續(xù)空間的問題時,，用近似來表示值函數(shù)V和Q，這個做法看起來很自然,，但是近似以后會發(fā)現(xiàn),，以往很多的理論結(jié)果就不成立了。

但我們現(xiàn)在先不管那些問題,，先看做了近似以后怎么來學,？我們想知道的是，這里的Q值,，是希望Q值近似以后,，夠盡量逼近真實的Q值。如果已經(jīng)知道真實的Q值,，怎么逼近呢,？最簡單的方法就是做一個最小二乘回歸。其中一種解法是求導,。求導以后,，導數(shù)表示為，真實的Q和估計的Q的差值,，然后再乘對Q值模型的導,。可以看到,，導數(shù)表達的含義與之前的模特卡羅誤差,、TD誤差是一致的，只不過更新的是參數(shù)w,。把這種更新方式套進Q learning里,，其他地方都沒有變，只得到了用值函數(shù)逼近的Q-Learning方法,。

這個模型用什么函數(shù)呢,？最簡單就是用線性函數(shù)。但是線性函數(shù)有很多局限的,，需要在特征的設(shè)計上下功夫,，這需要很好的人工設(shè)計,。

把它變成非線性函數(shù)，一個常用方法是用神經(jīng)網(wǎng)絡(luò),，直接用神經(jīng)網(wǎng)絡(luò)表示Q值,。在更新的時候也很簡單，只需要把梯度傳到神經(jīng)網(wǎng)絡(luò)中去就可以了,，因為神經(jīng)網(wǎng)絡(luò)的BP算法本身也是求梯度,。

用批量學習改進

還有一些改進的方式。比如說我們在訓練近似模型的時候,，在一個樣本上訓練可能會不穩(wěn)定,，所以可以用Batch Models的方式，積累一批數(shù)據(jù)來訓練這個模型,。

剛才講的所有訓練方法,，都是先把V值或者Q值估計出來，然后再從中把這個策略導出來,。我們稱這種方法為基于值函數(shù)的強化學習方法,。

五、策略搜索（Policy Search）

值函數(shù)估計法存在的問題：策略退化

但是用值函數(shù)估計會有一個問題——這種方法可以收斂到最優(yōu)策略,，但前提必須是用表格的表達方式,；如果用的是函數(shù)近似，則會出現(xiàn)策略退化,，即對Q值估計越大,，策略越差。

舉一個簡單的例子,，現(xiàn)在有兩個狀態(tài),，一個是狀態(tài)1，一個是狀態(tài)2,，狀態(tài)1的特征為2,，狀態(tài)2的特征為1。我們設(shè)定獎賞,，使得狀態(tài)2的最優(yōu)V值比狀態(tài)1的要大,。這時如果用一個線性函數(shù)來表示這個V，也就是用W乘以特征,，這個特征只有一維,，最優(yōu)的這個V值2是比1大的，1的特征值要高一點,，2的特征值要小一點,，所以最優(yōu)的W就應(yīng)該是個負數(shù)，這樣會使得V(2)比V(1)大，因而能導出最優(yōu)策略,。

但是基于值函數(shù)的做法是要使得V值盡量靠近最優(yōu)的V值,，最優(yōu)的V值又是正值，這樣會導致這個W一定是正的,，無法得到最優(yōu)的策略,。這樣值函數(shù)估計得越準，策略越差的現(xiàn)象被稱為策略退化,。

用策略搜索解決策略退化問題

為了避免策略退化,，我們的方法是直接去找策略,，這就是策略搜索。

先把策略參數(shù)化,，對于離散動作來說,，參數(shù)可以做成像Gibbs Policy一樣，即每個動作有一個參數(shù),，然后把它歸一,，變成每一個動作有一個概率。如果是一個連續(xù)動作的話,，可以用高斯分布來描述,。里面這個參數(shù)，我在這里寫的是一個線性的過程,，但也可以用神經(jīng)網(wǎng)絡(luò)來替代,。

直接優(yōu)化策略的參數(shù)，使得收到的總回報達到最大的方法,，就是策略搜索（Policy Search）,。

策略搜索的優(yōu)勢

策略搜索和基于值函數(shù)的方法相比,，優(yōu)缺點各是什么,？

第一，能處理連續(xù)狀態(tài)和動作,；
第二，對于高維的數(shù)據(jù)總的表現(xiàn)比較好,。
第三，可以直接學出隨機性策略
第四,，Policy Search和監(jiān)督學習的兼容性比較好。

第三點用處很大,，比如說玩“剪刀石頭布”,，如果選擇確定性策略，那一定會輸,；一定要做一個帶概率的輸出才會贏,。

還有另外一個例子，跟大家講解一下為什么需要隨機性策略,。

骷髏代表走到這就死掉了,；最優(yōu)策略肯定是往中間走，但是這里有兩個灰色格子,，它們代表的是不完全觀測的狀態(tài)，即走到灰格子之后不知道該往左邊還是右邊,；

如果這時又用了確定性策略,，那就只能向左或向右走，只能是確定的,，則有可能會遇到走不通的路徑,。
如果用隨機性策略，向左和向右的概率都為50%,，因此不管往哪邊走總能到達目標,。

這也體現(xiàn)了策略搜索的優(yōu)勢。

第四,，策略搜索和監(jiān)督學習的兼容性比較好,。

這個策略是用參數(shù)表達的，它的目標是最大化的獎賞,。最大化獎賞的意思就是說,，把空間里所有的軌跡枚舉出來。因為策略產(chǎn)生這些軌跡是有一定概率的,，在某個狀態(tài)上,，策略做出相應(yīng)動作的概率是由策略決定的，把所有一條軌跡上所有動作的概率相乘,，就得出產(chǎn)生這條軌跡的概率,。所以它總體的期望回報，就是所有軌跡的期望,，也就是每條軌跡的概率乘以每條概率能獲得的獎賞,，這也是總回報的另外一種寫法。這種寫法有的好處就在于,，它和策略參數(shù)目標有關(guān),，所以我可以對獎賞直接求導,，來求解策略。另外一種寫法用的是穩(wěn)態(tài)分布（Stationary Distribution）,，用和上面寫法完全等價,，意思是完全一樣的，在這里就跳過不講了,。

策略搜索也有一個缺點,，其中一個缺點就是有很多局部最優(yōu)解，失去了全局最優(yōu)的收斂性保障,，其次是訓練過程方差非常高,。

早期策略求導的方法：Finite Difference

相信大家都會求導，不過有一種方式大家可能沒有見過——有限差分（Finite Difference）,，這是早期用來做策略求導的方法,。

那什么時候會用到有限差分呢？可能是這個系統(tǒng)可能太復雜了,，不容易求導,，那就可以用一個簡單的方式來逼近這個導數(shù)。拿到一個參數(shù)θ,，θ的導數(shù)就是看一下周圍哪個方向走的比較快，這樣給θ加一個很小的擾動的值,，對θ周圍的局部進行采樣,，對那個采樣增長得最快，這個方向就當成是一個導數(shù)方向,。這是最簡單的方法,，當然這個方法有很多缺陷，特別是在高維度的情況下,，會需要很多采樣,，所以更直接的方法還是直接求導。

最后得到的一個導數(shù),，導數(shù)形式如下所示：

E是期望,，1到T代表考慮的是T步的軌跡，每一步軌跡對策略輸出值的對數(shù)取導數(shù),，然后乘以真實的獎賞（獎賞不取對數(shù)）,。獎賞是個常數(shù)，即軌跡得到的獎賞值,。

可以通過采樣可以來逼近期望,，對一個策略以后，去跑一些軌跡,，然后計算平均梯度,，作為梯度期望的逼近。

我們剛剛說到，這種方式有一個很大的缺陷,，就是它的方差很大,，直接用計算的梯度來更新策略（vallina policy gradient），基本上得不到好的策略,，因為它的方差太大,，不穩(wěn)定。

控制方差的方法 1,、Actor-Critic

控制方差有多種方式,，其中一種叫做Actor-Critic。用比如直接求導的方式把策略求出來,，叫做Actor,；對值函數(shù)進行估計，并用于評估策略,，是Critic,，意為它是一個評價者。

我們要維護一個值函數(shù)Q的模型,。另外,，用導數(shù)的方法來求策略的梯度的時候，不做直接使用獎賞,，而是使用Criitic提供的Q值,。所以Actor-Critic會維護兩個模型，第一個是策略的模型,，第二個是Q函數(shù)的模型,。

對Q函數(shù)求近似的時候，式子和上面的那個導數(shù)形式一樣,，里面的經(jīng)驗獎賞換成了Q值,。在求策略梯度時，Q值是一個常數(shù),，是不更新的,，它有自己的更新方式，且通常是真實的Q值,。

控制方差的方法2,、引入偏差項（bias term）

另一種控制方差的形式，是引入偏差項,，只要這個函數(shù)是一個只跟狀態(tài)有關(guān),、跟動作無關(guān)的函數(shù)，它的積分就是0,，不影響梯度方向,，而會影響梯度的方差,。

對于簡單的形式，我們可以直接求出來最優(yōu)的偏差是什么,。更一般的形式,，我們可以用V值來替代bias。因為V值就是關(guān)于狀態(tài)的估計值,，和動作沒有關(guān)系,，所以它帶到積分里面去的時候會是0。

把V值帶進去,，后面的Q就變成了Q-V,，叫做Advantage Function，意思指：在這個狀態(tài)上,，V值相當于是一個平均值,，Q值指某個動作比平均值高出來多少。用Advantage Function會使得做策略梯度以后,，方差控制得比較好,，只有當方差控制好了，這類算法才能真正起作用,。

其他改進方法

梯度的改進方法還有Nature Policy Gradient,。在監(jiān)督學習里面，隨機梯度是很容易并行的,。最近有一些理論的工作,，也探討了它的并行不會影響到它的理論性質(zhì)。在策略梯度里面,，我們同樣可以把這個梯度并行來做，這樣可以使得它的速度下的很快,。

還有對策略直接求導的方法,，比如無梯度的優(yōu)化（Derivative-Free Optimization）。這類方法不管強化學習是在做什么,，而是直接優(yōu)化策略里面的參數(shù),。優(yōu)化完參數(shù)以后，試一下策略,，得出這個值具體是多少,。

這樣，優(yōu)化過的算法可以通過總體獎賞值來調(diào)整模型里面的參數(shù),。通常來說它比用Gradient Policy效率差,，由于中間過程是忽略不計的，所以它對特別復雜的問題,，反而有比較好的效果,，比如俄羅斯方塊游戲,。

六、游戲中的強化學習（Reinforcement Learning in Games）

最后一部分,，講一下強化學習和游戲,。

為什么講游戲？一方面,，是因為在游戲里面需要克服的一些問題,，在真實應(yīng)用中也常遇到；另外一方面,，用游戲來做強化學習任務(wù)的成本比較低,。

游戲推動深度強化學習（Deep Reinforcement Learning）的發(fā)展

2015年，DeepMind在Atari游戲上使用深度網(wǎng)絡(luò)直接從屏幕圖像訓練強化學習,，直接推動了“深度強化學習”的發(fā)展,。

用深度神經(jīng)網(wǎng)絡(luò)，放在Policy Gradient里面,，作為一個策略的模型,；或者放在基于值函數(shù)的方法里面，作為值函數(shù)Q值的一個估計,。這樣的方法就稱為深度強化學習,。

深度強化學習

其實，深度強化學習里很多工作是在研究怎么讓網(wǎng)絡(luò)更穩(wěn)定,。特別是當輸入數(shù)據(jù)比較少的時候,，網(wǎng)絡(luò)方差的浮動會比較大。這就可以用“延后更新”來解決——如果用深度神經(jīng)網(wǎng)絡(luò),，那么每走一步都更新模型會導致模型抖動非常大,。而用“延后更新”，例如可以在100步里不更新策略,，只是把神經(jīng)網(wǎng)絡(luò)更新一下,，這個神經(jīng)網(wǎng)絡(luò)沒有放到新的策略里面來，等神經(jīng)網(wǎng)絡(luò)有一個比較穩(wěn)定的上升以后,，再更新策略,。還有，積累的數(shù)據(jù)不要丟掉,，也拿出來,，讓這個神經(jīng)網(wǎng)絡(luò)更穩(wěn)定一點。這兩個技巧合起來放在Q-Learning里面,，就是DQN,。

Deep Q-Network（DQN）

DQN可以說是第一個聲稱深度強化學習算法，可能也是最廣為人知的一個,?；旧?，它的整體結(jié)構(gòu)就是一個函數(shù)近似的Q Learning，只不過用CNN做了近似函數(shù),。

在玩這個游戲的時候,，它已經(jīng)有了100萬個記錄歷史。每次訓練神經(jīng)網(wǎng)絡(luò)的時候,，要抓32個出來訓練一次,，并且訓練完以后不去更新策略，而是在走一定的步數(shù)以后,，再更新這個策略,。除此之外，并不是直接從屏幕上把一幀圖像拿進來,，而是把歷史上好幾幀的屏幕拼起來,，得到一個當前幀和前面好幾幀合起來的一個總體的圖作為CNN的輸入。不過在最新的一些工作中,，這個過程已經(jīng)被被遞歸神經(jīng)網(wǎng)絡(luò)替代了,，不再是把好幾層拼起來，而是讓好幾幀分別輸入例如LSTM的網(wǎng)絡(luò),。

很多運用強化學習尋找策略的游戲已經(jīng)比人玩得都好了,，它玩的好的優(yōu)勢主要體現(xiàn)在反應(yīng)速度上。但是在需要深入思考邏輯關(guān)系的游戲中,，強化學習沒有人做得好,。

我們來看看它的游戲報告結(jié)果。

這里面,，“with replay”和“without replay”的意思是有沒有用到歷史數(shù)據(jù),，“with target Q”和“without target Q”就用了CNN還是線性網(wǎng)絡(luò)。我們可以看到,，神經(jīng)網(wǎng)絡(luò)在這里貢獻并不是最大的,。如果我們只用神經(jīng)網(wǎng)絡(luò)而不用replay的話，效果還不如用了replay,，但只用線性模型而不用CNN。當然,，同時使用深度模型和強化學習是最好的,，這可以完成一些過去完成不了的事情。

在AlphaGo中的應(yīng)用

AlphaGo系統(tǒng)的基礎(chǔ)框架是蒙特卡洛樹搜索,，這是經(jīng)典的樹搜索的方法,。但是單憑蒙特卡洛樹搜索本身并不能取得很好的效果，只用樹搜索大概只能達到業(yè)余的五六段,。AlphaGo里面的一個創(chuàng)新的點就是引入強化學習來改進搜索樹的深度和寬度,。

這里面用了三個神經(jīng)網(wǎng)絡(luò),。

第一個policy network，在展開蒙特卡羅樹搜索節(jié)點的時候起作用,。這個網(wǎng)絡(luò)是用策略梯度方法訓練出來的,。
第二個是一個很小的神經(jīng)網(wǎng)絡(luò)，蒙特卡羅樹搜索里再往下做很深的搜索時會用到,，這樣它可以算得很快,。這個小的網(wǎng)絡(luò)是通過監(jiān)督學習學出來的。
第三個網(wǎng)絡(luò)是用來修正值的,。它是通過強化學習中間產(chǎn)生的數(shù)據(jù)來學習,。

由于大家對DQN比較熟悉，所以在嘗試深度學習的時候,，首先想到的算法大多是DQN,。但因為它是一個基于值函數(shù)估計的強化學習方法，所以這種方法在稍微復雜一點的應(yīng)用環(huán)境中可能運行不了,，大家會感覺用DQN做強化學習效果沒那么好,。但同樣是DeepMin做的圍棋游戲，它的強化學習方法已經(jīng)改成了Policy Gradient,，而且以后的很多算法也都是以Policy Gradient為主的,，用這種方法處理復雜問題效果更好。

在其他游戲上的應(yīng)用

正是由于在計算機中模擬游戲的代價很低,，所以不斷有研究者借助游戲來發(fā)展強化學習,。比如，有用在3D第一人稱射擊游戲中,，可以在這個世界里面行走,，并且尋找東西。去年有一個“DOOM”游戲比賽,，參賽者要用計算機控制游戲角色,，以第一視角進行3D射擊。有了強化學習,，參賽者就能控制游戲角色,，讓它做一些動作。由于這個游戲額環(huán)境比較復雜,，所以在玩游戲的過程中,，也發(fā)展出了一些創(chuàng)新方法。

例如,，在游戲里面,，如果讓一個強化學習直接到游戲環(huán)境里面學習，那它又要撿醫(yī)療箱,，又要去撿武器等等,，太復雜了,。而其中一個團隊，就采取了這樣的做法：他們讓強化學習從簡單到復雜,，一步一步的去學習——首先學一個策略,，比如撿起醫(yī)療箱，然后在這個策略的基礎(chǔ)上再來學怎么樣來開槍,、怎么樣來射擊敵人等等,。

實際上游戲里面有很多很高難度的挑戰(zhàn)，其中一個非常復雜游戲叫做StarCraft,。這個游戲已經(jīng)有很多年的歷史了,，現(xiàn)在有不少人，包括DeepMind,，都希望在這么復雜的游戲上面能表現(xiàn)出一個比較好的性能,，因為這個游戲的復雜度已經(jīng)大到和很多真實應(yīng)用的復雜度相當，即使人去學這個游戲,，也要花很長時間才能學會,。以前用強化學習，只是先取其中一個小問題來解決,。比如說我和對方各派三個兵,，想辦法看這六個兵怎么打。這是一個很局部的戰(zhàn)役,，但能學到這樣的東西也已經(jīng)比較不錯了,。如果要學到整盤的打法，它里面涉及到很多問題,，第一,，它的規(guī)模遠大于圍棋的規(guī)模；第二,，有很多對手的信息是觀測不到的,，比如敵方的行動。雖然在今年年初,，德州撲克游戲上機器已經(jīng)打贏了人類玩家,，但德州撲克其實是一類很簡單的牌類游戲，想讓強化學習在大規(guī)模游戲任務(wù)中,，在無法觀測到對手信息的情況下,，指揮200多個單位做連續(xù)的運動，還要持續(xù)半個多小時走幾十萬步,，目前還做不好。

七,、強化學習總結(jié)

之前介紹的只是強化學習的其中一小部分,，強化學習還包括很多內(nèi)容：

比如在MDP中如果出現(xiàn)了不可觀測的情況,，它就不屬于Markov了，有一個專門的方向如POMDP來解決這個問題,。

還有Learning from Demonstrations,，意為人先做出示范，然后從示范數(shù)據(jù)中教智能體,。例如AlphaGo,，一開始訓練的時候并不是直接上強化學習，而是首先搜集了很多人類對打的數(shù)據(jù),。

而怎么去設(shè)計獎賞函數(shù)也會有很多不同的方法,。

下面總結(jié)一下兩個大家比較關(guān)心的問題。

第一個問題：強化學習是否已經(jīng)發(fā)展成熟,？如何選擇強化學習問題中的算法,？

如果碰到比較簡單的強化學習問題，可以用基于值函數(shù)的方法,，比如DQN,，更復雜的問題可以用Policy Gradient的方法做策略梯度。

但是從目前的發(fā)展現(xiàn)狀兩看,，強化學習的成熟度遠遠不夠,，也就是說在強化學習領(lǐng)域，還有很大的提升的空間,，有可能能做出一個性能更好的全新的算法,。但大規(guī)模的問題現(xiàn)在還是很難解決。這個大規(guī)模指是它的狀態(tài)空間大,，并且步數(shù)特別多,。

第二個問題：在實際領(lǐng)域應(yīng)用強化學習，會遇到什么瓶頸,？

1,、強化學習需要探索，在很多場景帶來風險,。

以推薦股票為例,。我本來已經(jīng)有一個還可以的推薦策略，每天能給我?guī)?00萬的收入,。但是現(xiàn)在為了訓練強化學習,，要做探索，嘗試一些隨機的股票,。假如告訴你這個探索會導致今天一下子要損失好幾百萬,，而一個月以后可以賺回1個億，那你就要衡量一下這里看面的風險有多高，敢不敢用了,。

2,、為什么強化學習在很多游戲上面用的比較多？

游戲在計算機中運行,，速度高,、代價低。如果放到現(xiàn)實世界中來運行,，比如放在推薦系統(tǒng)線上運行,，那它就必須和真實的環(huán)境打交道。它的學習過程需要不斷探索,，而部署在真實環(huán)境里可能會遇到很多麻煩,，如果能有一個比較好的模擬器，就可以減少這些麻煩,；另外,，如果有比較好的監(jiān)督學習數(shù)據(jù)的話，也可以做一個初始的策略,，不過這個策略可能一開始起點要稍微高一點,。做機器人一般也有一個機器人模擬器，所以一般先在模擬器里面做,，做好策略再放到機器人身上來學,。但是其他現(xiàn)實世界問題，在模擬器里可能就沒有那么好做了,。

八,、強化學習資源推薦書籍

強化學習的書不多，最經(jīng)典的書是Richard S. Sutton的教科書,；Masashi Sugiyama的書屬于專著,；Reinforcement Learning: State-of-the-Art屬于文集，覆蓋面比較廣,，但需要讀者有一定基礎(chǔ),；還有一些講述MDP的書；另外,，在機器學習的書里面也會提到強化學習,。