現(xiàn)代機(jī)器學(xué)習(xí) 課件 第12章 深度強(qiáng)化學(xué)習(xí)

第12章深度強(qiáng)化學(xué)習(xí)12.1任務(wù)與獎(jiǎng)賞12.2多臂老虎機(jī)12.3馬爾可夫決策過程(MDP)12.4動(dòng)態(tài)規(guī)劃12.5蒙特卡羅法本章小結(jié)

強(qiáng)化學(xué)習(xí)(ReinforcementLearning)基本上是對(duì)上述原則的數(shù)學(xué)化描述。強(qiáng)化學(xué)習(xí)是機(jī)器學(xué)習(xí)的一個(gè)重要分支。前幾年人機(jī)大戰(zhàn)的主角AlphaGo正是以強(qiáng)化學(xué)習(xí)為核心所構(gòu)造

的。強(qiáng)化學(xué)習(xí)中,包含兩種基本的元素:狀態(tài)(States)與動(dòng)作(Actions),在某個(gè)狀態(tài)下執(zhí)行某種動(dòng)作,這便是一種策略(Policy),學(xué)習(xí)器要做的就是通過不斷的探索學(xué)習(xí),從而獲得一

個(gè)好的策略。

強(qiáng)化學(xué)習(xí)是和監(jiān)督學(xué)習(xí)、無監(jiān)督學(xué)習(xí)并列的第三種機(jī)器學(xué)習(xí)方法。

12.1任務(wù)與獎(jiǎng)賞強(qiáng)化學(xué)習(xí)任務(wù)通常使用馬爾可夫決策過程(MarkovDecisionProcess,MDP)來描述。具體而言:機(jī)器處在一個(gè)環(huán)境E中,狀態(tài)空間為X,每個(gè)狀態(tài)x∈X為機(jī)器對(duì)當(dāng)前環(huán)境的感知;機(jī)器的動(dòng)作空間為A,機(jī)器只能通過動(dòng)作a∈ｉ來影響環(huán)境;當(dāng)機(jī)器執(zhí)行一個(gè)動(dòng)作后,會(huì)使得環(huán)境按某種轉(zhuǎn)移函數(shù)P轉(zhuǎn)移到另一個(gè)狀態(tài);同時(shí),環(huán)境會(huì)根據(jù)潛在的獎(jiǎng)賞函數(shù)R反饋給機(jī)器一個(gè)獎(jiǎng)賞r?？偟膩碚f,強(qiáng)化學(xué)習(xí)主要包含四個(gè)要素:狀態(tài)、動(dòng)作、轉(zhuǎn)移函數(shù)和獎(jiǎng)賞函數(shù)(E=<X,A,ｉ,R>),其示意圖如圖12.1所示。圖12.1強(qiáng)化學(xué)習(xí)示意圖

機(jī)器要做的就是通過在環(huán)境中不斷的嘗試而學(xué)得一個(gè)策略π,常見的策略表示方法有以下兩種:

①確定性策略a=π(x),即在狀態(tài)x下執(zhí)行動(dòng)作a;

②隨機(jī)性策略P=π(x,a),即在狀態(tài)x下執(zhí)行動(dòng)作a的概率,且有

一個(gè)策略的優(yōu)劣取決于長(zhǎng)期執(zhí)行這一策略后的累積獎(jiǎng)賞,換句話說,可以使用累積獎(jiǎng)賞來評(píng)估策略的好壞。最優(yōu)策略是指在初始狀態(tài)下一直執(zhí)行這個(gè)策略,最后的累積獎(jiǎng)賞值最高。長(zhǎng)期累積獎(jiǎng)賞通常使用下述兩種計(jì)算方法:

現(xiàn)在,我們來重新定義一些強(qiáng)化學(xué)習(xí)模型的要素:

(1)環(huán)境狀態(tài)S:t時(shí)刻下環(huán)境的狀態(tài)St

是環(huán)境狀態(tài)集中的某一個(gè)狀態(tài)。

(2)個(gè)體動(dòng)作A:t時(shí)刻個(gè)體采取的動(dòng)作At是動(dòng)作集中的某一個(gè)動(dòng)作。

(3)環(huán)境的獎(jiǎng)賞R:t時(shí)刻個(gè)體在狀態(tài)St采取的動(dòng)作At對(duì)應(yīng)的獎(jiǎng)賞Rt+1會(huì)在t+1時(shí)刻得到。

(4)個(gè)體的策略π:代表個(gè)體采取動(dòng)作的依據(jù)。常見的是一個(gè)條件概率分布π(At|St),即在狀態(tài)St

時(shí)采取動(dòng)作At

的概率。

(5)價(jià)值函數(shù)vπ(s):表示在策略π和狀態(tài)s時(shí)采取行動(dòng)后的價(jià)值。這個(gè)價(jià)值一般是期望函數(shù)。雖然當(dāng)前動(dòng)作會(huì)給一個(gè)延時(shí)獎(jiǎng)賞Rt+1,但是僅看這個(gè)延時(shí)獎(jiǎng)賞是不行的,因?yàn)楫?dāng)前的延時(shí)獎(jiǎng)賞高,不代表t+1,t+2,…時(shí)刻的后續(xù)獎(jiǎng)賞也高。比如下象棋,雖然某個(gè)動(dòng)作可以吃掉對(duì)方的車,但是后面輸棋了,此時(shí)吃車的動(dòng)作獎(jiǎng)賞值高但是價(jià)值并不高。因此價(jià)值要綜合考慮當(dāng)前的延時(shí)獎(jiǎng)賞和后續(xù)的延時(shí)獎(jiǎng)賞。價(jià)值函數(shù)vπ(s)一般可以表示為

(6)環(huán)境的狀態(tài)轉(zhuǎn)移模型Pas,s':可以理解為一個(gè)概率狀態(tài)機(jī),它表示一個(gè)概率模型,即在狀態(tài)s下采取動(dòng)作a后轉(zhuǎn)到下一個(gè)狀態(tài)s'的概率。

(7)探索率ｉ:主要用在強(qiáng)化學(xué)習(xí)訓(xùn)練迭代過程中。由于一般會(huì)選擇使當(dāng)前迭代價(jià)值最大的動(dòng)作,但這會(huì)導(dǎo)致一些較好的且沒有執(zhí)行過的動(dòng)作被錯(cuò)過,因此在訓(xùn)練選擇最優(yōu)動(dòng)作時(shí),會(huì)有一定的概率(即探索率ε)不選擇使當(dāng)前迭代價(jià)值最大的動(dòng)作,而等概率地選擇其他的動(dòng)作。

12.2多臂老虎機(jī)12.2.1守成與探索多臂老虎機(jī)問題是一個(gè)經(jīng)典的單步?jīng)Q策概率論問題。老虎機(jī)有多個(gè)拉桿,拉動(dòng)不同的拉桿會(huì)得到不同程度的獎(jiǎng)賞。玩家的目的是通過拉動(dòng)特定的桿來取得最多的獎(jiǎng)賞。我們?nèi)糁烂恳粋€(gè)動(dòng)作a的獎(jiǎng)賞,那么解決這一問題將會(huì)變得十分簡(jiǎn)單。但實(shí)際上我們一開始并不知道每一個(gè)動(dòng)作a所對(duì)應(yīng)的獎(jiǎng)賞,這時(shí)我們只能通過“學(xué)習(xí)”來找到對(duì)應(yīng)的規(guī)律,從而找到最優(yōu)的動(dòng)作a:

12.2.2多臂老虎機(jī)問題建模及ε貪婪法

多臂老虎機(jī)問題中,每一個(gè)選項(xiàng)對(duì)應(yīng)的都是一個(gè)不同的動(dòng)作a。我們需要比較各個(gè)動(dòng)作a之間的優(yōu)劣,才能做出最優(yōu)的選擇。要評(píng)價(jià)各個(gè)動(dòng)作a的優(yōu)劣,首先需要建立一個(gè)合

適的動(dòng)作獎(jiǎng)賞評(píng)價(jià)體系。一個(gè)簡(jiǎn)單直觀的方法是采樣平均(sample-average),即

這種方式在計(jì)算時(shí)仍然會(huì)占用大量的存儲(chǔ)空間,所以我們繼續(xù)采用一種小的技巧來降低算法所需要占用的存儲(chǔ)空間:

在確定以上這些以后,我們將多臂老虎機(jī)問題的算法總結(jié)如下:

12.3馬爾可夫決策過程(MDP)

12.3.1引入MDP的原因現(xiàn)實(shí)生活中不光有單步?jīng)Q策過程,更多的是相互影響的多步?jīng)Q策過程。環(huán)境的狀態(tài)轉(zhuǎn)移模型Pas,s',轉(zhuǎn)移到下一個(gè)狀態(tài)s'既與上一個(gè)狀態(tài)s有關(guān),也與上上個(gè)狀態(tài)以及很久之前的狀態(tài)有關(guān)。這一關(guān)系會(huì)導(dǎo)致環(huán)境的轉(zhuǎn)移模型非常復(fù)雜,復(fù)雜到難以建模。因此需要對(duì)強(qiáng)化學(xué)習(xí)的環(huán)境轉(zhuǎn)移模型進(jìn)行簡(jiǎn)化。

簡(jiǎn)化的方法就是假設(shè)狀態(tài)轉(zhuǎn)移具有馬爾可夫性,也就是

假設(shè)轉(zhuǎn)移到下一個(gè)狀態(tài)s'的概率僅與上一個(gè)狀態(tài)s和動(dòng)作a有關(guān),與之前的狀態(tài)和動(dòng)作無關(guān),用公式表示為

除了對(duì)環(huán)境的狀態(tài)轉(zhuǎn)移模型做馬爾可夫假設(shè)外,這里還對(duì)強(qiáng)化學(xué)習(xí)第四個(gè)要素個(gè)體的策略π也做了馬爾可夫假設(shè)。即在狀態(tài)s時(shí)采取動(dòng)作a的概率僅與當(dāng)前狀態(tài)s有關(guān),與其他的要素?zé)o關(guān),用公式表示為

對(duì)于第五個(gè)要素價(jià)值函數(shù)vπ(s)也是一樣,vπ(s)現(xiàn)在僅依賴于當(dāng)前狀態(tài),用公式表示為

其中,Gt代表收獲,是一個(gè)MDP中從某一狀態(tài)St開始采樣直到終止?fàn)顟B(tài)時(shí)所有獎(jiǎng)賞的衰減值之和。我們稱函數(shù)vπ(s)是策略π的狀態(tài)價(jià)值函數(shù)。

12.3.2MDP的價(jià)值函數(shù)

12.3.1節(jié)中介紹的價(jià)值函數(shù)vπ(s)并沒有考慮到所采用的動(dòng)作a帶來的價(jià)值影響,因此,除了vπ(s)這個(gè)狀態(tài)價(jià)值函數(shù)外,還有一個(gè)動(dòng)作價(jià)值函數(shù)qπ(s,a):

根據(jù)價(jià)值函數(shù)表達(dá)式,可以推導(dǎo)出價(jià)值函數(shù)基于狀態(tài)的遞推關(guān)系。比如,對(duì)于狀態(tài)價(jià)值函數(shù)vπ(s),可以發(fā)現(xiàn):

也就是說,t時(shí)刻的狀態(tài)St和t+1時(shí)刻的狀態(tài)St+1是滿足遞推關(guān)系的。式(12-11)一般叫作貝爾曼方程。通過式(12-11)可以知道,一個(gè)狀態(tài)的價(jià)值由該狀態(tài)的獎(jiǎng)賞以及后續(xù)狀態(tài)價(jià)值按一定的衰減比例聯(lián)合組成。同理,可以得到動(dòng)作價(jià)值函數(shù)qπ(s,a)的貝爾曼方程:

12.3.3狀態(tài)價(jià)值函數(shù)與動(dòng)作價(jià)值函數(shù)的關(guān)系

根據(jù)動(dòng)作價(jià)值函數(shù)qπ(s,a)和狀態(tài)價(jià)值函數(shù)vπ(s)的定義,很容易得到它們之間的轉(zhuǎn)化關(guān)系公式:

也就是說,狀態(tài)價(jià)值函數(shù)是所有動(dòng)作價(jià)值函數(shù)基于策略π的期望。通俗地說,就是某狀態(tài)下所有動(dòng)作價(jià)值函數(shù)乘該動(dòng)作出現(xiàn)的概率后求和,就得到了對(duì)應(yīng)的狀態(tài)價(jià)值。

同樣,也可利用狀態(tài)價(jià)值函數(shù)vπ(s)來表示動(dòng)作價(jià)值函數(shù)qπ(s,a):

即動(dòng)作價(jià)值函數(shù)由兩部分相加組成:第一部分是即時(shí)獎(jiǎng)賞;第二部分是環(huán)境所有可能出現(xiàn)的下一個(gè)狀態(tài)的概率乘下一個(gè)狀態(tài)的狀態(tài)價(jià)值后求和,并乘上衰減因子γ。將式(12-13)和式(12-14)結(jié)合起來,有

12.3.4最優(yōu)價(jià)值函數(shù)

解決強(qiáng)化學(xué)習(xí)問題意味著要尋找一個(gè)最優(yōu)的策略讓個(gè)體在與環(huán)境交互過程中獲得始終比其他策略都要多的收獲,這個(gè)最優(yōu)策略可以用π*表示。一旦找到最優(yōu)策略π*,這個(gè)強(qiáng)

化學(xué)習(xí)問題就解決了。一般來說,比較難找到一個(gè)最優(yōu)策略,但是可以通過比較若干不同策略的優(yōu)劣來確定一個(gè)較好的策略,也就是局部最優(yōu)解。

如何比較策略的優(yōu)劣呢?一般是通過對(duì)應(yīng)的價(jià)值函數(shù)來比較的。也就是說,尋找較優(yōu)策略可以通過尋找較優(yōu)的價(jià)值函數(shù)來完成。可以定義最優(yōu)狀態(tài)價(jià)值函數(shù)是所有策略下產(chǎn)生

的眾多狀態(tài)價(jià)值函數(shù)中的最大者,即

同理,也可以定義最優(yōu)動(dòng)作價(jià)值函數(shù)是所有策略下產(chǎn)生的眾多動(dòng)作狀態(tài)價(jià)值函數(shù)中的最大者:

對(duì)于最優(yōu)的策略,基于動(dòng)作價(jià)值函數(shù)定義為

只要找到了最大的狀態(tài)價(jià)值函數(shù)或者動(dòng)作價(jià)值函數(shù),對(duì)應(yīng)的策略π*就是強(qiáng)化學(xué)習(xí)問題的解。同時(shí),利用狀態(tài)價(jià)值函數(shù)和動(dòng)作價(jià)值函數(shù)之間的關(guān)系也可以得到:

12.4動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃(DynamicProgramming,DP)是指在給定理想MDP模型的情況下用于計(jì)算最優(yōu)策略的算法集合。動(dòng)態(tài)規(guī)劃的關(guān)鍵點(diǎn)有兩個(gè):一是問題的最優(yōu)解可以由若干小問題的最優(yōu)解構(gòu)成,即通過尋找子問題的最優(yōu)解來得到問題的最優(yōu)解;二是可以找到子問題狀態(tài)之間的遞推關(guān)系,通過較小的子問題狀態(tài)遞推出較大的子問題狀態(tài)。而強(qiáng)化學(xué)習(xí)的問題恰好是滿足這兩個(gè)條件的。

下面討論如何使用動(dòng)態(tài)規(guī)劃來求解強(qiáng)化學(xué)習(xí)的預(yù)測(cè)問題,即求解給定策略的狀態(tài)價(jià)值函數(shù)的問題。這個(gè)問題的求解過程通常叫作策略評(píng)估(PolicyEvaluation)。策略評(píng)估的基本

思路是從任意一個(gè)狀態(tài)價(jià)值函數(shù)開始,依據(jù)給定的策略,結(jié)合貝爾曼方程、狀態(tài)轉(zhuǎn)移概率和獎(jiǎng)賞同步迭代更新狀態(tài)價(jià)值函數(shù),直至其收斂,得到該策略下最終的狀態(tài)價(jià)值函數(shù)。假設(shè)在第k輪迭代已經(jīng)計(jì)算出了所有狀態(tài)的狀態(tài)價(jià)值,那么在第k+1輪可以利用第k輪計(jì)算出的狀態(tài)價(jià)值來計(jì)算第k+1輪的狀態(tài)價(jià)值。這是通過貝爾曼方程來完成的:

每一輪可以對(duì)計(jì)算得到的新的狀態(tài)價(jià)值函數(shù)再次進(jìn)行迭代,直至狀態(tài)價(jià)值的值改變很小(收斂),這樣就得到了預(yù)測(cè)問題的解,即給定策略的狀態(tài)價(jià)值函數(shù)v(π)。這種算法被稱為

迭代策略評(píng)估。

動(dòng)態(tài)規(guī)劃算法的思路比較簡(jiǎn)單,主要是利用貝爾曼方程來迭代更新狀態(tài)價(jià)值,用貪婪法之類的方法來迭代更新最優(yōu)策略。動(dòng)態(tài)規(guī)劃算法使用全寬度(full-width)的回溯機(jī)制來進(jìn)

行狀態(tài)價(jià)值的更新,也就是說,在每一次回溯更新某一個(gè)狀態(tài)的價(jià)值時(shí),都要回溯到該狀態(tài)的所有可能的后續(xù)狀態(tài),并利用貝爾曼方程更新該狀態(tài)的價(jià)值。這種全寬度的價(jià)值更新方式對(duì)于狀態(tài)數(shù)較少的強(qiáng)化學(xué)習(xí)問題還是比較有效的,但是當(dāng)問題規(guī)模很大時(shí),動(dòng)態(tài)規(guī)劃算法將會(huì)因貝爾曼維度災(zāi)難而無法使用,因此還需要尋找其他的針對(duì)復(fù)雜問題的強(qiáng)化學(xué)習(xí)問題求解方法。

12.5蒙特卡羅法

2.5.1不基于模型的強(qiáng)化學(xué)習(xí)動(dòng)態(tài)規(guī)劃法需要在每一次回溯更新某一個(gè)狀態(tài)的價(jià)值時(shí),回溯到該狀態(tài)的所有可能的后續(xù)狀態(tài),這會(huì)導(dǎo)致求解復(fù)雜問題時(shí)計(jì)算量很大。同時(shí)很多時(shí)候,環(huán)境的狀態(tài)轉(zhuǎn)移模型無法獲取,這時(shí)動(dòng)態(tài)規(guī)劃法無法使用。在動(dòng)態(tài)規(guī)劃法中,強(qiáng)化學(xué)習(xí)的兩個(gè)問題是這樣定義的:

(1)預(yù)測(cè)問題,即給定強(qiáng)化學(xué)習(xí)的6個(gè)要素———狀態(tài)集S、動(dòng)作集A、模型狀態(tài)轉(zhuǎn)移概率矩陣P、即時(shí)獎(jiǎng)賞R、衰減因子γ、給定策略π,求解該策略的狀態(tài)價(jià)值函數(shù)v(π)。

(2)控制問題,也就是求解最優(yōu)的價(jià)值函數(shù)和策略,即給定強(qiáng)化學(xué)習(xí)的5個(gè)要素——狀態(tài)集S、動(dòng)作集A、模型狀態(tài)轉(zhuǎn)移概率矩陣P、即時(shí)獎(jiǎng)賞R、衰減因子γ,求解最優(yōu)的狀態(tài)價(jià)值函數(shù)v*和最優(yōu)策略π*。

可見,模型狀態(tài)轉(zhuǎn)移概率矩陣P始終是已知的,即MDP已知,這樣的強(qiáng)化學(xué)習(xí)問題一般稱為基于模型的強(qiáng)化學(xué)習(xí)問題。

不過有很多強(qiáng)化學(xué)習(xí)問題無法事先得到模型狀態(tài)轉(zhuǎn)移概率矩陣P,這時(shí)如果仍然需要求解強(qiáng)化學(xué)習(xí)問題,那么這就成為了不基于模型的強(qiáng)化學(xué)習(xí)問題。它的兩個(gè)問題一般的定義是:

(1)預(yù)測(cè)問題,即給定強(qiáng)化學(xué)習(xí)的5個(gè)要素——狀態(tài)集S、動(dòng)作集A、即時(shí)獎(jiǎng)賞R、衰減因子γ、給定策略π,求解該策略的狀態(tài)價(jià)值函數(shù)v(π)。

(2)控制問題,也就是求解最優(yōu)的價(jià)值函數(shù)和策略,即給定強(qiáng)化學(xué)習(xí)的5個(gè)要素——狀態(tài)集S、動(dòng)作集A、即時(shí)獎(jiǎng)賞R、衰減因子γ、探索率ε,求解最優(yōu)的動(dòng)作價(jià)值函數(shù)q*和最優(yōu)策略π*。

蒙特卡羅法是一種不基于模型的強(qiáng)化學(xué)習(xí)問題求解方法。它通過采樣近似求解問題。蒙特卡羅法通過采樣若干經(jīng)歷完整的狀態(tài)序列來估計(jì)狀態(tài)的真實(shí)價(jià)值。所謂的經(jīng)歷完整,就是這個(gè)序列必須是達(dá)到終點(diǎn)的。比如下棋問題分出輸贏,駕車問題成功到達(dá)終點(diǎn)或者失敗。有了很多組這樣經(jīng)歷完整的狀態(tài)序列,就可以近似地估計(jì)狀態(tài)價(jià)值,進(jìn)而求解預(yù)測(cè)和控制問題了。蒙特卡羅法的優(yōu)點(diǎn)是:與動(dòng)態(tài)規(guī)劃比,它不需要依賴于模型狀態(tài)轉(zhuǎn)移概率;它從經(jīng)歷過的完整序列學(xué)習(xí),完整的經(jīng)歷越多,學(xué)習(xí)效果越好。

12.5.2預(yù)測(cè)問題

蒙特卡羅法求解強(qiáng)化學(xué)習(xí)預(yù)測(cè)問題的方法,即策略評(píng)估。一個(gè)給定策略π的完整T個(gè)狀態(tài)的狀態(tài)序列如下:

根據(jù)式(12-9)對(duì)價(jià)值函數(shù)vπ(s)的定義,可以看出每個(gè)狀態(tài)的價(jià)值函數(shù)等于所有該狀態(tài)收獲的期望,同時(shí)這個(gè)收獲是通過后續(xù)的獎(jiǎng)賞與對(duì)應(yīng)的衰減乘積求和得到的。對(duì)于蒙特卡羅法來說,如果要求某一個(gè)狀態(tài)的狀態(tài)價(jià)值,只需要求出所有的完整序列中該狀態(tài)出現(xiàn)時(shí)候的收獲再取平均值即可近似求解:

12.5.3控制問題

蒙特卡羅法求解控制問題的思路和動(dòng)態(tài)規(guī)劃中價(jià)值迭代的思路類似,每輪迭代先做策略評(píng)估,計(jì)算出價(jià)值vk(s),然后基于一定的方法(比如貪婪法)更新當(dāng)前策略π,最后得到最優(yōu)價(jià)值函數(shù)v*和最優(yōu)策略π*。動(dòng)態(tài)規(guī)劃和蒙特卡羅法的不同之處體現(xiàn)在三點(diǎn):

(1)預(yù)測(cè)問題中策略評(píng)估的方法不同。

(2)蒙特卡羅法一般是優(yōu)化最優(yōu)動(dòng)作價(jià)值函數(shù)q*,而不是狀態(tài)價(jià)值函數(shù)v*。

(3)動(dòng)態(tài)規(guī)劃一般基于貪婪法更新策略,而蒙特卡羅法一般采用ε貪婪法更新策略。

純貪心行動(dòng)很有可能陷入局部最優(yōu)解(最壞情況下,貪心行動(dòng)可能導(dǎo)致玩家從頭到尾都在選擇一個(gè)固定的非最優(yōu)的行為),這時(shí)就需要去“探索(Exploring)”,犧牲一點(diǎn)眼前的利益,換來能帶來長(zhǎng)遠(yuǎn)價(jià)值的信息。只需對(duì)貪心策略稍做修改,我們就能做到這一點(diǎn)。ε貪婪法通過設(shè)置一個(gè)較小的ε值,使用1ε的概率貪婪地選擇目前認(rèn)為是最大行為價(jià)值的行為,而用ε的概率隨機(jī)地從所有m個(gè)可選行為中選擇行為,用公式可以表示為

蒙特卡羅法可以避免動(dòng)態(tài)規(guī)劃求解過于復(fù)雜的問題,同時(shí)還可以不事先知道環(huán)境的狀態(tài)轉(zhuǎn)移模型,直接在與環(huán)境的交互中學(xué)習(xí)到最優(yōu)的行為,因此其可以用于海量數(shù)據(jù)和復(fù)雜

模型。但是它也有自己的缺點(diǎn),這就是它每次采樣都需