《強(qiáng)化學(xué)習(xí)理論與應(yīng)用》規(guī)劃與蒙特卡洛樹搜索

目錄

模型、學(xué)習(xí)與規(guī)劃8.18.3

決策時間規(guī)劃8.2

Dyna-Q結(jié)構(gòu)及其算法改進(jìn)8.5

習(xí)題8.4小結(jié)1

在強(qiáng)化學(xué)習(xí)領(lǐng)域，根據(jù)MDP環(huán)境中是否包含完備的遷移概率，分為有模型和無模型方法。前面章節(jié)中的DP方法屬于有模型方法，而MC、TD、n-步TD等方法屬于無模型的方法。有模型方法將規(guī)劃（planning）作為主要組成部分；在無模型方法將學(xué)習(xí)（learning）作為主要組成部分；

本章的重點(diǎn)并非是將兩種方法進(jìn)行區(qū)分，而是以一定的方法對它們進(jìn)行有效的結(jié)合。引言8.1.1模型Agent可以通過模型來預(yù)測環(huán)境并作出反應(yīng)，即在給定一個狀態(tài)和動作時，通過模型，可以對下一狀態(tài)和獎賞進(jìn)行預(yù)測。如果模型是隨機(jī)的，則存在多種可能的下一狀態(tài)和獎賞。8.1模型、學(xué)習(xí)與規(guī)劃（1）

模型通常可以分為分布模型和樣本模型兩種類型：分布模型（distributionmodel）

該模型可以生成所有可能的結(jié)果及其對應(yīng)的概率分布?？梢岳斫鉃椋瑺顟B(tài)轉(zhuǎn)移概率p已知，在狀態(tài)s下執(zhí)行動作a能夠給出所有可能的下一狀態(tài)和相應(yīng)的轉(zhuǎn)換概率，如DP算法。8.1模型、學(xué)習(xí)與規(guī)劃（2）樣本模型（samplemodel）

該模型能夠從所有可能的情況中產(chǎn)生一個確定的結(jié)果。可以理解為，狀態(tài)轉(zhuǎn)移概率p未知，通過采樣獲取軌跡，如MC和TD算法。

從功能上講，模型就是用于模擬環(huán)境和產(chǎn)生模擬經(jīng)驗的。與樣本模型相比，分布模型包含更多的信息，只是現(xiàn)實(shí)任務(wù)中難以獲得所有的狀態(tài)轉(zhuǎn)移概率。8.1模型、學(xué)習(xí)與規(guī)劃（3）8.1.2學(xué)習(xí)

學(xué)習(xí)過程是從環(huán)境產(chǎn)生的真實(shí)經(jīng)驗中進(jìn)行學(xué)習(xí)。根據(jù)經(jīng)驗的使用方法，學(xué)習(xí)過程可以分為直接強(qiáng)化學(xué)習(xí)和簡介強(qiáng)化學(xué)習(xí)兩種類型：直接強(qiáng)化學(xué)習(xí)（directRL）

在真實(shí)環(huán)境中采集真實(shí)經(jīng)驗，根據(jù)真實(shí)經(jīng)驗直接改進(jìn)值函數(shù)或策略，不受模型偏差的影響。8.1模型、學(xué)習(xí)與規(guī)劃（4）間接強(qiáng)化學(xué)習(xí)

在真實(shí)環(huán)境中采集真實(shí)經(jīng)驗，根據(jù)真實(shí)經(jīng)驗來構(gòu)建和改進(jìn)模擬模型（simulatedmodel），提高模擬模型精度，使其更接近真實(shí)環(huán)境。

間接強(qiáng)化學(xué)習(xí)包含模型學(xué)習(xí)和模型規(guī)劃兩個過程，通常能更充分地利用有限的經(jīng)驗。而直接強(qiáng)化學(xué)習(xí)是一種直接的學(xué)習(xí)，它更為簡單，容易實(shí)現(xiàn)，不受模型構(gòu)建帶來的偏差影響。8.1模型、學(xué)習(xí)與規(guī)劃（5）8.1.3規(guī)劃

規(guī)劃過程是基于模擬環(huán)境或經(jīng)驗?zāi)Ｐ?，從模擬經(jīng)驗中改進(jìn)值函數(shù)，實(shí)現(xiàn)改善策略的目的。學(xué)習(xí)和規(guī)劃的核心都是通過迭代更新來評估值函數(shù)。

不同之處在于：在規(guī)劃過程中，Agent并沒有與真實(shí)環(huán)境進(jìn)行交互。8.1模型、學(xué)習(xí)與規(guī)劃（6）規(guī)劃通?？煞譃椋籂顟B(tài)空間規(guī)劃（state-spaceplanning）方案空間規(guī)劃（plan-spaceplanning）

在強(qiáng)化學(xué)習(xí)領(lǐng)域，僅討論狀態(tài)空間規(guī)劃。狀態(tài)空間規(guī)劃（以下所有狀態(tài)空間規(guī)劃都簡稱為規(guī)劃）是在狀態(tài)空間中尋找最優(yōu)策略，值函數(shù)的計算都是基于狀態(tài)的，通常將該規(guī)劃方法視為“搜索”方法。8.1模型、學(xué)習(xí)與規(guī)劃（7）所有規(guī)劃算法都以計算值函數(shù)作為策略改進(jìn)的中間關(guān)鍵步驟；所有規(guī)劃算法都可以通過基于模型產(chǎn)生的模擬經(jīng)驗來計算值函數(shù)。規(guī)劃的基本鏈?zhǔn)浇Y(jié)構(gòu)如下所示：

真實(shí)經(jīng)驗既可用于改進(jìn)模擬模型，也可直接改進(jìn)值函數(shù)或策略。8.1模型、學(xué)習(xí)與規(guī)劃（8）8.1模型、學(xué)習(xí)與規(guī)劃（9）圖8.1規(guī)劃Agent的角色圖一種常用的規(guī)劃算法——隨機(jī)采樣單步表格式Q-planning算法。8.1模型、學(xué)習(xí)與規(guī)劃（10）目錄

模型、學(xué)習(xí)與規(guī)劃8.28.3

決策時間規(guī)劃8.1

Dyna-Q結(jié)構(gòu)及其算法改進(jìn)8.5

習(xí)題8.4小結(jié)138.2.1Dyna-Q架構(gòu)Dyna-Q架構(gòu)將學(xué)習(xí)和規(guī)劃有機(jī)結(jié)合在一起，是有模型和無模型方法的融合。在Dyna-Q架構(gòu)中，規(guī)劃方法為隨機(jī)采樣單步表格式Q-planning算法，直接強(qiáng)化學(xué)習(xí)方法為單步表格式Q-leaning算法，模型學(xué)習(xí)方法為確定環(huán)境下的表格式算法。

8.2Dyna-Q結(jié)構(gòu)及其算法改進(jìn)（1）

圖8.2Dyna架構(gòu)圖8.2Dyna-Q結(jié)構(gòu)及其算法改進(jìn)（2）8.2Dyna-Q結(jié)構(gòu)及其算法改進(jìn)（3）例8.1

將Dyna-Q架構(gòu)用于例4.1掃地機(jī)器人實(shí)例，比較算法中不同規(guī)劃步數(shù)對實(shí)驗效果的影響。掃地機(jī)器人在任何狀態(tài)下，動作空間都為

。機(jī)器人離開邊界或撞到障礙物時，保持原地不變，得到+10的獎賞；到達(dá)充電樁時，得到+1的獎賞；撿到垃圾時，得到+5的獎賞；其他遷移情況，獎賞均為0。這里參數(shù)

，

，

。8.2Dyna-Q結(jié)構(gòu)及其算法改進(jìn)（4）

若每次實(shí)驗都采用相同的初始種子來控制隨機(jī)過程，則對于任意n值，第1個情節(jié)的步數(shù)都是完全相同的。而從第2個情節(jié)開始，n越大，收斂到最優(yōu)策略的速度越快。當(dāng)n=0時，采用的是無規(guī)劃Agent，僅使用直接強(qiáng)化學(xué)習(xí)，即單步表格式Q-learning，學(xué)習(xí)速度最慢，大約需要25個情節(jié)才能得到最優(yōu)策略。而當(dāng)n=5時（5次規(guī)劃方法），僅需5個情節(jié)；n=30時，僅需2個情節(jié)，即可得到最優(yōu)策略。8.2Dyna-Q結(jié)構(gòu)及其算法改進(jìn)（5）例8.2將Dyna-Q架構(gòu)應(yīng)用于掃地機(jī)器人任務(wù)。在該任務(wù)中，Agent在不同的情節(jié)中采用n=0和n=50所獲得的策略不同。因為與無規(guī)劃Agent相比，規(guī)劃Agent能更快地找到有效路徑，所以當(dāng)

n=50時，Dyna-Q算法值函數(shù)更新更快。

n=0和n=50時，第2個情節(jié)每個狀態(tài)的策略8.2Dyna-Q結(jié)構(gòu)及其算法改進(jìn)（6）8.2.2優(yōu)先遍歷優(yōu)先遍歷是一種常用的提高規(guī)劃效率的分布計算方法。在一定程度上，該方法可以避免隨機(jī)選擇狀態(tài)和動作所導(dǎo)致的低效率問題。在使用優(yōu)先遍歷法時，用一個優(yōu)先隊列PQueue來存儲值函數(shù)變化較大的狀態(tài)-動作對

，并以動作值函數(shù)改變的大?。碩D誤差）作為優(yōu)先級P，來對其進(jìn)行排序，然后依據(jù)該優(yōu)先隊列依次產(chǎn)生模擬經(jīng)驗。8.2Dyna-Q結(jié)構(gòu)及其算法改進(jìn)（7）當(dāng)隊列頂端的

被更新時，它對其前序

的影響也會被計算。如果這些影響超過某個閾值，就將相應(yīng)的前序

也插入優(yōu)先隊列中（如果該

已經(jīng)存在于隊列中，則保留優(yōu)先級高的）。通過優(yōu)先遍歷法，值函數(shù)變化的影響被有效地反向傳播，直到消失。優(yōu)先級P定義為單步TD誤差（即Q-learning算法的TD誤差），其計算迭代式為：8.2Dyna-Q結(jié)構(gòu)及其算法改進(jìn)（8）8.2Dyna-Q結(jié)構(gòu)及其算法改進(jìn)（9）例8.3在掃地機(jī)器人環(huán)境中，分別用n=10、n=30的Dyna-Q算法和優(yōu)先遍歷算法進(jìn)行訓(xùn)練，將到達(dá)垃圾狀態(tài)[8,5]和充電狀態(tài)[1,6]的遷移獎賞均設(shè)置為+1，其他情況遷移獎賞均設(shè)置為-0.1，參數(shù)

，

，

。8.2Dyna-Q結(jié)構(gòu)及其算法改進(jìn)（10）

實(shí)驗結(jié)果表明：

在除了到達(dá)垃圾和充電狀態(tài)以外，其他獎賞都為負(fù)值的情況下，優(yōu)先遍歷算法運(yùn)行效果好于Dyna-Q算法，能更快地找到最優(yōu)路徑。8.2Dyna-Q結(jié)構(gòu)及其算法改進(jìn)（11）

現(xiàn)在將設(shè)置改成：除了到達(dá)垃圾和充電狀態(tài)以外，其他獎賞都為0。同樣采用用n=10、n=30的Dyna-Q算法和優(yōu)先遍歷算法進(jìn)行訓(xùn)練，運(yùn)行結(jié)果如圖所示：由圖可以看出：當(dāng)除了到達(dá)垃圾和充電狀態(tài)以外，其他獎賞都為0時，優(yōu)先遍歷算法運(yùn)行效果略低于Dyna-Q算法。8.2Dyna-Q結(jié)構(gòu)及其算法改進(jìn)（12）利用優(yōu)先遍歷算法的規(guī)劃過程，對隊列中的每個

值只進(jìn)行了1次更新。與n=30的Dyna-Q算法相比，更新次數(shù)太少。特別是在開始階段，第1個情節(jié)結(jié)束后，進(jìn)行規(guī)劃的次數(shù)僅為1次；在掃地機(jī)器人環(huán)境，涉及的狀態(tài)空間較?。?7個狀態(tài)）。優(yōu)先掃描算法在大狀態(tài)空間中才能表現(xiàn)出其優(yōu)勢；當(dāng)除了到達(dá)垃圾和充電狀態(tài)以外，其他獎賞都為負(fù)時，優(yōu)先遍歷算法每步都會進(jìn)行規(guī)劃；而其他轉(zhuǎn)移獎賞為0時，優(yōu)先遍歷算法只對靠近終止位置（垃圾和充電樁）的狀態(tài)進(jìn)行規(guī)劃更新。8.2Dyna-Q結(jié)構(gòu)及其算法改進(jìn)（13）將優(yōu)先遍歷思想推廣到隨機(jī)性環(huán)境時，由于其采用的是期望更新，所以模型保存的是每一組

出現(xiàn)的次數(shù)以及它們下一狀態(tài)

出現(xiàn)的次數(shù)（概率），可能需要耗費(fèi)大量的時間。尤其是在缺乏分布模型的情況下，期望更新更難以實(shí)現(xiàn)的。相比較而言，采樣更新能將整個回溯計算分解為更小的片段，每一部分對應(yīng)一個轉(zhuǎn)換，使計算能夠聚焦于產(chǎn)生最大影響的片段上。盡管采樣更新會引入方差，但通常在訓(xùn)練過程中，只需要耗費(fèi)較少的計