《強(qiáng)化學(xué)習(xí)理論與應(yīng)用》數(shù)學(xué)建模

目錄

馬爾可夫決策過(guò)程3.13.3求解強(qiáng)化學(xué)習(xí)任務(wù)3.2基于模型和無(wú)模型3.5

小結(jié)3.4探索和利用1馬爾可夫決策過(guò)程（MDP）：強(qiáng)化學(xué)習(xí)的數(shù)學(xué)理論基礎(chǔ)；以概率形式對(duì)強(qiáng)化學(xué)習(xí)任務(wù)進(jìn)行建模；對(duì)強(qiáng)化學(xué)習(xí)過(guò)程中出現(xiàn)的狀態(tài)、動(dòng)作、狀態(tài)轉(zhuǎn)移概率和獎(jiǎng)賞等概念進(jìn)行抽象表達(dá)。引言23.1馬爾可夫決策過(guò)程（1）馬爾可夫性質(zhì)：

在某一任務(wù)中，如果Agent從環(huán)境中得到的下一狀態(tài)僅依賴于當(dāng)前狀態(tài)，而不考慮歷史狀態(tài)，即：那么該任務(wù)就滿足馬爾可夫性質(zhì)。馬爾可夫過(guò)程（MarkovProcess，MP）：

由二元組

中的

組成的馬爾可夫鏈，該鏈中的所有狀態(tài)都滿足馬爾可夫性質(zhì)。33.1馬爾可夫決策過(guò)程（2）馬爾可夫獎(jiǎng)賞過(guò)程（MarkovRewardProcess，MRP）：

由三元組

組成的馬爾可夫過(guò)程。根據(jù)概率，狀態(tài)自發(fā)地進(jìn)行轉(zhuǎn)移，其狀態(tài)轉(zhuǎn)移概率P與動(dòng)作無(wú)關(guān)，記為:馬爾可夫決策過(guò)程（MarkovDecisionProcess，MDP）：

由四元組

組成的馬爾可夫過(guò)程，狀態(tài)依靠動(dòng)作進(jìn)行轉(zhuǎn)移。馬爾可夫決策過(guò)程分為：有窮馬爾可夫決策過(guò)程；無(wú)窮馬爾可夫決策過(guò)程。43.1馬爾可夫決策過(guò)程（3）馬爾可夫決策過(guò)程由四元組組成：用來(lái)表示不包含終止?fàn)顟B(tài)的狀態(tài)空間；用來(lái)表示包含終止?fàn)顟B(tài)的狀態(tài)空間；用來(lái)表示狀態(tài)空間中的某一狀態(tài)。通常用向量來(lái)表示，可分為離散狀態(tài)和連續(xù)狀態(tài)兩種類型。（1）狀態(tài)（state）或觀測(cè)值（observation）53.1馬爾可夫決策過(guò)程（4）表示動(dòng)作空間;表示狀態(tài)s的動(dòng)作空間；表示動(dòng)作空間中的某一個(gè)動(dòng)作。通常用向量來(lái)表示可分為：

離散動(dòng)作和連續(xù)動(dòng)作兩種類型。（2）動(dòng)態(tài)（action）6確定環(huán)境：隨機(jī)環(huán)境：3.1馬爾可夫決策過(guò)程（5）

（3）狀態(tài)轉(zhuǎn)移（statetransition）73.1馬爾可夫決策過(guò)程（6）表示獎(jiǎng)賞空間；

獎(jiǎng)賞公式可以表示為：或者：（4）獎(jiǎng)賞（reward）83.1馬爾可夫決策過(guò)程（7）

對(duì)于獎(jiǎng)賞，可以從兩個(gè)方面進(jìn)行理解：先獲得獎(jiǎng)賞再進(jìn)入下一狀態(tài)：獎(jiǎng)賞

與當(dāng)前狀態(tài)

和動(dòng)作

相關(guān)；先進(jìn)入下一狀態(tài)再獲得獎(jiǎng)賞：獎(jiǎng)賞

與當(dāng)前狀態(tài)

、動(dòng)作

和下一狀態(tài)

相關(guān)，這也是獎(jiǎng)賞用

表示的一個(gè)重要原因。93.1馬爾可夫決策過(guò)程（8）例3.1確定環(huán)境下掃地機(jī)器人任務(wù)的MDP數(shù)學(xué)建模

考慮圖中描述的確定環(huán)境MDP問(wèn)題：

一個(gè)掃地機(jī)器人，在躲避障礙物的同時(shí)，一方面需要到指定的位置收集垃圾，另一方面可以到指定位置給電池充電。10狀態(tài)空間：

離散化為24個(gè)不同的狀態(tài)（除去[3,3]），用集合表示為：動(dòng)作空間：

離散化為上、下、左、右4個(gè)不同的動(dòng)作，用集合表示為：3.1馬爾可夫決策過(guò)程（9）掃地機(jī)器人任務(wù)的MDP數(shù)學(xué)建模如下：11狀態(tài)轉(zhuǎn)移函數(shù)：映射為下一個(gè)狀態(tài)：映射為下一個(gè)狀態(tài)的概率：3.1馬爾可夫決策過(guò)程（10）12獎(jiǎng)賞函數(shù)：到達(dá)狀態(tài)，可以撿到垃圾，得到+3的獎(jiǎng)賞；到達(dá)狀態(tài)，充電，得到+1的獎(jiǎng)賞；機(jī)器人采取動(dòng)作向坐標(biāo)[3,3]處移動(dòng)時(shí)，會(huì)撞到障礙物，保持原地不動(dòng)，并得到-10的獎(jiǎng)賞；其他情況，獎(jiǎng)賞均為0。3.1馬爾可夫決策過(guò)程（11）133.1馬爾可夫決策過(guò)程（12）例3.2隨機(jī)環(huán)境下掃地機(jī)器人任務(wù)的MDP數(shù)學(xué)建模

重新考慮圖中描述的隨機(jī)環(huán)境MDP問(wèn)題：

假設(shè)由于地面的問(wèn)題，采取某一動(dòng)作后，狀態(tài)轉(zhuǎn)換不再確定。當(dāng)采取某一動(dòng)作試圖向某一方向移動(dòng)時(shí)，機(jī)器人成功移動(dòng)的概率為0.80，保持原地不動(dòng)的概率為0.15，移動(dòng)到相反方向的概率為0.05。143.1馬爾可夫決策過(guò)程（13）

在隨機(jī)環(huán)境下，狀態(tài)空間、動(dòng)作空間與確定環(huán)境是完全相同的，其隨機(jī)性主要體現(xiàn)在狀態(tài)轉(zhuǎn)移函數(shù)和獎(jiǎng)賞函數(shù)上。根據(jù)任務(wù)的隨機(jī)性，狀態(tài)轉(zhuǎn)移只能用概率來(lái)表示。狀態(tài)轉(zhuǎn)移函數(shù)

153.1馬爾可夫決策過(guò)程（14）獎(jiǎng)賞函數(shù)

在隨機(jī)環(huán)境下，獎(jiǎng)賞的獲取不單純受

的影響，還與下一狀態(tài)

相關(guān)。

16目錄

馬爾可夫決策過(guò)程3.13.3求解強(qiáng)化學(xué)習(xí)任務(wù)3.2基于模型和無(wú)模型3.5

小結(jié)3.4探索和利用173.2基于模型和無(wú)模型（1）

從狀態(tài)轉(zhuǎn)移概率p是否已知的角度，強(qiáng)化學(xué)習(xí)可以分為基于模型（model-based）強(qiáng)化學(xué)習(xí)和無(wú)模型（model-free）強(qiáng)化學(xué)習(xí)兩種：基于模型：狀態(tài)轉(zhuǎn)移概率p已知，能夠通過(guò)建立完備的環(huán)境模型來(lái)模擬真實(shí)反饋。相關(guān)算法如：動(dòng)態(tài)規(guī)劃法。無(wú)模型：狀態(tài)轉(zhuǎn)移概率p未知，Agent所處的環(huán)境模型是未知的。相關(guān)算法：蒙特卡洛法、時(shí)序差分法、值函數(shù)近似以及策略梯度法。

183.2基于模型和無(wú)模型（2）基于模型的優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：能夠基于模擬經(jīng)驗(yàn)數(shù)據(jù)直接模擬真實(shí)環(huán)境；具備推理能力，能夠直接評(píng)估策略的優(yōu)劣性；能夠與監(jiān)督學(xué)習(xí)算法相結(jié)合，來(lái)求解環(huán)境模型。

193.2基于模型和無(wú)模型（3）基于模型的優(yōu)缺點(diǎn)：缺點(diǎn)：存在二次誤差。兩次近似誤差具體體現(xiàn)在：第一次近似誤差：基于真實(shí)經(jīng)驗(yàn)對(duì)模型進(jìn)行學(xué)習(xí)，得到的模型僅僅是Agent對(duì)環(huán)境的近似描述。第二次近似誤差：基于模擬模型對(duì)值函數(shù)或策略進(jìn)行學(xué)習(xí)時(shí)，存在學(xué)習(xí)誤差。

20目錄

馬爾可夫決策過(guò)程3.13.3求解強(qiáng)化學(xué)習(xí)任務(wù)3.2基于模型和無(wú)模型3.5

小結(jié)3.4探索和利用213.3求解強(qiáng)化學(xué)習(xí)任務(wù)（1）

在t時(shí)刻，Agent從環(huán)境中得到當(dāng)前狀態(tài)

，根據(jù)策略

執(zhí)行動(dòng)作

，并返回獎(jiǎng)賞

和下一狀態(tài)

。Agent通過(guò)不斷地與環(huán)境交互進(jìn)行學(xué)習(xí)，并在學(xué)習(xí)過(guò)程中不斷更新策略，從而經(jīng)過(guò)多次學(xué)習(xí)后，得到解決問(wèn)題的最優(yōu)策略。?；贛DP的強(qiáng)化學(xué)習(xí)基本框架223.3.1策略

強(qiáng)化學(xué)習(xí)的目的就是：在MDP中搜索到最優(yōu)策略。策略表示狀態(tài)到動(dòng)作的映射，即在某一狀態(tài)下采取動(dòng)作的概率分布。

與狀態(tài)轉(zhuǎn)移概率不同，策略概率通常是人為設(shè)定的。根據(jù)概率分布形式，策略可以分為確定策略和隨機(jī)策略兩種。3.3求解強(qiáng)化學(xué)習(xí)任務(wù)（2）23在確定策略下，Agent在某一狀態(tài)下只會(huì)執(zhí)行固定一個(gè)動(dòng)作。可以表示為：在隨機(jī)策略下，Agent在一個(gè)狀態(tài)下可能會(huì)執(zhí)行多種動(dòng)作，隨機(jī)策略將狀態(tài)映射為執(zhí)行動(dòng)作的概率?？梢员硎緸椋?.3求解強(qiáng)化學(xué)習(xí)任務(wù)（3）24MDP應(yīng)用一個(gè)策略產(chǎn)生序列的方法：從初始狀態(tài)分布中產(chǎn)生一個(gè)初始狀態(tài)

；根據(jù)策略

，給出采取的動(dòng)作

，并執(zhí)行該動(dòng)作

；根據(jù)獎(jiǎng)賞函數(shù)和狀態(tài)轉(zhuǎn)移函數(shù)得到獎(jiǎng)賞

和下一個(gè)狀態(tài)

；不斷重復(fù)第（2）步到第（4）步的過(guò)程，產(chǎn)生一個(gè)序列：如果任務(wù)是情節(jié)式的，序列將終止于狀態(tài)

；如果任務(wù)是連續(xù)式的，序列將無(wú)窮延續(xù)。3.3求解強(qiáng)化學(xué)習(xí)任務(wù)（4）25強(qiáng)化學(xué)習(xí)任務(wù)的兩種隨機(jī)性：策略隨機(jī)性：人為設(shè)定的。

狀態(tài)轉(zhuǎn)移的隨機(jī)性：任務(wù)本身所固有的特性。3.3求解強(qiáng)化學(xué)習(xí)任務(wù)（5）263.3.2獎(jiǎng)賞與回報(bào)Agent會(huì)依據(jù)該策略得到一個(gè)狀態(tài)-動(dòng)作序列，其形式為：定義馬爾可夫決策過(guò)程的回報(bào)如下：

實(shí)際情況中，需要引入折扣率

，用于對(duì)未來(lái)獎(jiǎng)賞賦予折扣，則回報(bào)定義如下：3.3

求解強(qiáng)化學(xué)習(xí)任務(wù)（6）27例3.3設(shè)折扣率

，，獎(jiǎng)賞序列為：計(jì)算各時(shí)刻的回報(bào)：3.3求解強(qiáng)化學(xué)習(xí)任務(wù)（7）28例3.4掃地機(jī)器人任務(wù)

選取機(jī)器人的一段移動(dòng)軌跡，令折扣率為0.8，計(jì)算軌跡中每個(gè)狀態(tài)的折扣回報(bào)。3.3

求解強(qiáng)化學(xué)習(xí)任務(wù)（8）293.3.3值函數(shù)與貝爾曼方程狀態(tài)值函數(shù)（state-valuefunction）：

狀態(tài)值函數(shù)表示遵循策略，狀態(tài)s的價(jià)值?？杀硎緸椋簞?dòng)作值函數(shù)（action-valuefunction）動(dòng)作值函數(shù)表示遵循策略，狀態(tài)s采取動(dòng)作a的價(jià)值?？杀硎緸椋?.3

求解強(qiáng)化學(xué)習(xí)任務(wù)（9）30

動(dòng)作值函數(shù)是在狀態(tài)值函數(shù)的基礎(chǔ)上考慮了執(zhí)行動(dòng)作a所產(chǎn)生的影響。于是可以構(gòu)建值函數(shù)的遞歸關(guān)系：3.3

求解強(qiáng)化學(xué)習(xí)任務(wù)（10）狀態(tài)值函數(shù)的貝爾曼方程31

根據(jù)狀態(tài)值函數(shù)貝爾曼方程，可以構(gòu)建狀態(tài)值函數(shù)更新圖，空心圓表示狀態(tài)，實(shí)心圓表示動(dòng)作。由圖可知，狀態(tài)值函數(shù)與動(dòng)作值函數(shù)滿足如下關(guān)系式：3.3

求解強(qiáng)化學(xué)習(xí)任務(wù)（11）32

與狀態(tài)值函數(shù)的貝爾曼方程推導(dǎo)方式類似，同理可以得到動(dòng)作值函數(shù)的貝爾曼方程：3.3

求解強(qiáng)化學(xué)習(xí)任務(wù)（12）動(dòng)作值函數(shù)的貝爾曼方程33

根據(jù)動(dòng)作值函數(shù)的貝爾曼方程，可以構(gòu)建動(dòng)作值函數(shù)更新圖：

由左圖可知，動(dòng)作值函數(shù)與狀態(tài)值函數(shù)滿足如下關(guān)系式：3.3

求解強(qiáng)化學(xué)習(xí)任務(wù)（13）34例3.5已知、、、的狀態(tài)值，利用狀態(tài)值函數(shù)的貝爾曼方程，表示

的狀態(tài)值。3.3

求解強(qiáng)化學(xué)習(xí)任務(wù)（14）35確定情況下掃地機(jī)器人任務(wù)中，采用的隨機(jī)策略為:表示狀態(tài)可以采取的動(dòng)作數(shù)。

在折扣率的情況下，求掃地機(jī)器人任務(wù)中每個(gè)狀態(tài)的狀態(tài)值。例3.6確定環(huán)境掃地機(jī)器人任務(wù)3.3

求解強(qiáng)化學(xué)習(xí)任務(wù)（15）36首先，列出貝爾曼方程：根據(jù)貝爾曼方程，可以列出方程組：3.3

求解強(qiáng)化學(xué)習(xí)任務(wù)（16）37求解方程組，得到各個(gè)狀態(tài)的狀態(tài)值：3.3

求解強(qiáng)化學(xué)習(xí)任務(wù)（17）383.3.4最優(yōu)策略與最優(yōu)值函數(shù)

利用強(qiáng)化學(xué)習(xí)方法解決任務(wù)的關(guān)鍵在于：搜索出MDP中的最優(yōu)策略。最優(yōu)策略就是使得值函數(shù)最大的策略。在有窮MDP中，由于狀態(tài)空間和動(dòng)作空間都是有窮的，所以策略也是有窮的。更優(yōu)策略

，執(zhí)行該策略時(shí)，所有狀態(tài)的期望回報(bào)都大于或等于執(zhí)行

策略的期望回報(bào)。也就是說(shuō)，對(duì)于所有

，

都存在

。3.3

求解強(qiáng)化學(xué)習(xí)任務(wù)（18）39最優(yōu)狀態(tài)值函數(shù)定義為：最優(yōu)策略可能不止一個(gè)，它們共享相同的狀態(tài)值函數(shù)。最優(yōu)動(dòng)作值函數(shù)定義為：在狀態(tài)s處，執(zhí)行動(dòng)作a，并在隨后的過(guò)程中采取最優(yōu)策略

得到的期望回報(bào)，也就是在狀態(tài)-動(dòng)作對(duì)

處能夠獲得的最大價(jià)值。3.3

求解強(qiáng)化學(xué)習(xí)任務(wù)（19）40貝爾曼最優(yōu)方程基于狀態(tài)值的貝爾曼最優(yōu)方程：3.3

求解強(qiáng)化學(xué)習(xí)任務(wù)（20）413.3

求解強(qiáng)化學(xué)習(xí)任務(wù)（21）貝爾曼最優(yōu)方程基于動(dòng)作值的貝爾曼最優(yōu)方程：423.3

求解強(qiáng)化學(xué)習(xí)任務(wù)（22）貝爾曼最優(yōu)方程基于動(dòng)作值的貝爾曼最優(yōu)方程更新圖基于狀態(tài)值的貝爾曼最優(yōu)方程更新圖43

貝爾曼最優(yōu)方程3.3

求解強(qiáng)化學(xué)習(xí)任務(wù)（23）44例3.7

求解確定環(huán)境下掃地機(jī)器人任務(wù)的最優(yōu)狀態(tài)值函數(shù)，并給出最優(yōu)策略。設(shè)折扣率。

可以顯式地給出在該掃地機(jī)器人任務(wù)，最優(yōu)貝爾曼方程：3.3

求解強(qiáng)化學(xué)習(xí)任務(wù)（24）45

利用第4章的值迭代算法，可以求得最優(yōu)狀態(tài)值和最優(yōu)策略：3.3

求解強(qiáng)化學(xué)習(xí)任務(wù)（25）46目錄

馬爾可夫決策過(guò)程3.13.3求解強(qiáng)化學(xué)習(xí)任務(wù)3.2基于模型和無(wú)模型3.5

小結(jié)3.4探索和利用47強(qiáng)化學(xué)習(xí)的一大矛盾：探索與利用的平衡Agent秉持利用機(jī)制（exploitation），為了得到最大回報(bào)，需要始終采用最優(yōu)動(dòng)作，即根據(jù)當(dāng)前的值函數(shù)選擇最優(yōu)動(dòng)作，最大限度地提升回報(bào)。Agent需要探索機(jī)制（exploration），摒棄基于值函數(shù)的貪心策略，找到更多可能的動(dòng)作來(lái)獲得更好的策略，探索更多的可能性。3.4

探索與利用（1）48行為策略（behaviorpolicy）：用于產(chǎn)生采樣數(shù)據(jù)的策略，具備探索性，能夠覆蓋所有情況，通常采用-柔性策略；目標(biāo)策略（targetpolicy）：強(qiáng)化學(xué)習(xí)任務(wù)中待求解的策略，也就是待評(píng)估和改進(jìn)的策略，一般不具備探索性，通常采用確定性貪心策略。3.4

探索與利用（2）49同策略（on-policy）：行為策略和目標(biāo)策略相同。通過(guò)

貪心策略平衡探索和利用，在保證初始狀態(tài)-動(dòng)作對(duì)

不變的前提下，確保每一組(s,a)都有可能被遍歷到。常用算法為Sarsa和Sarsa(??)算法。異策略（off-policy）：行為策略和目標(biāo)策略不同。將探索與利用分開(kāi)，在行為策略中貫徹探索原則：采樣數(shù)據(jù)，得到狀態(tài)-動(dòng)作序列；在目標(biāo)策略中貫徹利用原則：更新值函數(shù)并改進(jìn)目標(biāo)策略，以得到最優(yōu)目標(biāo)策略。常用算法為Q-learning和DQN算法。3.4

探索與利用（3）50目錄

馬爾可夫決策過(guò)程3.13.3求解強(qiáng)化學(xué)習(xí)任務(wù)3.2基于模型和無(wú)模型3.5

小結(jié)3.4探索和利用51本章主要介紹了強(qiáng)化學(xué)習(xí)的基礎(chǔ)數(shù)學(xué)理論，以馬爾可夫決策過(guò)程描述了Agent與環(huán)境的交互。狀態(tài)是Agent選擇動(dòng)作的基礎(chǔ)，通過(guò)動(dòng)作的選擇，完成狀態(tài)的轉(zhuǎn)移，并以獎(jiǎng)賞評(píng)判Agent動(dòng)作選擇的優(yōu)劣。有限的狀態(tài)、動(dòng)作和收益共同構(gòu)成了有限馬爾可夫決策過(guò)程，回報(bào)刻畫(huà)了Agent