《強(qiáng)化學(xué)習(xí)理論與應(yīng)用》動態(tài)規(guī)劃法

目錄1前言44.2值迭代4.1策略迭代4.3廣義策略迭代4.4小結(jié)2023/11/523:45

在強(qiáng)化學(xué)習(xí)中，動態(tài)規(guī)劃法（dynamicprogramming，DP）主要用于求解有模型的MDP問題。

盡管在現(xiàn)實任務(wù)中難以獲得完備的環(huán)境模型，且動態(tài)規(guī)劃需要消耗大量的計算資源，但是作為強(qiáng)化學(xué)習(xí)的基礎(chǔ)，動態(tài)規(guī)劃法仍然具有非常重要的理論意義。

4.前言（1）2023/11/523:452

事實上，所有其他強(qiáng)化學(xué)習(xí)方法，如蒙特卡洛法（MonteCarlo，MC）、時序差分法（TemporalDifference，TD）等，都是對動態(tài)規(guī)劃法的一種近似，只是在學(xué)習(xí)過程中不再需要完整的環(huán)境模型，而且在計算資源的消耗方面也可以大幅度減少。

前言（2）2023/11/523:453

動態(tài)規(guī)劃法：利用值函數(shù)來評價策略。基于模型的策略迭代基于模型的值迭代

前言（3）2023/11/523:454目錄5前言44.2值迭代4.1策略迭代4.3廣義策略迭代4.4小結(jié)2023/11/523:45策略迭代通過構(gòu)建策略的值函數(shù)（狀態(tài)值函數(shù)或動作值函數(shù)）來評估當(dāng)前策略，并利用這些值函數(shù)給出改進(jìn)的新策略。策略迭代由策略評估（PE）和策略改進(jìn)（PI）兩部分組成。

4.1策略迭代（1）62023/11/523:454.1策略迭代（2）7策略評估：

每一次策略評估都是一個迭代過程，對于一個給定的策略

，評估在該策略下，所有狀態(tài)

（或狀態(tài)-動作對）的值函數(shù)或。策略改進(jìn)：

在策略評估的基礎(chǔ)上，直接利用策略

的動作值函數(shù)，然后通過貪心策略（或-貪心策略）對策略進(jìn)行改進(jìn)。2023/11/523:45根據(jù)策略的值函數(shù)（或）產(chǎn)生一個更優(yōu)策略，再根據(jù)策略的值函數(shù)（或）得到一個更優(yōu)策略,以此類推，通過這樣的鏈?zhǔn)椒椒梢缘玫揭粋€關(guān)于策略和值函數(shù)的更新序列，并且能夠保證每一個新策略都比前一個策略更優(yōu)（除非前一個策略已是最優(yōu)策略）。

4.1策略迭代（3）8鏈?zhǔn)疥P(guān)系2023/11/523:45

4.1策略迭代（4）9在有限MDP中，策略有限，所以在多次迭代后，一定能收斂到最優(yōu)策略和最優(yōu)值函數(shù)。鏈?zhǔn)疥P(guān)系注：策略的下標(biāo)表示迭代更新的次序。2023/11/523:454.1.1策略評估1.基于狀態(tài)值函數(shù)的策略評估(v值)

4.1策略迭代（5）10

每一次策略評估都是一個迭代過程，對于一個給定的策略，評估在該策略下，所有狀態(tài)s的狀態(tài)值函數(shù)或動作值函數(shù)。2023/11/523:45基于狀態(tài)值函數(shù)的策略評估迭代式

可以將狀態(tài)值函數(shù)的貝爾曼方程轉(zhuǎn)化為迭代式：

4.1策略迭代（6）11

初始值可以為任意值（通常設(shè)為0）。在使用這樣的迭代式時，默認(rèn)采用同一策略，為了突出迭代關(guān)系，可以省略的下標(biāo)。2023/11/523:45提前結(jié)束迭代的兩種方法

4.1策略迭代（7）12直接設(shè)置迭代次數(shù)。只要達(dá)到預(yù)期的迭代次數(shù)，即可停止迭代；設(shè)定較小的閾值（次優(yōu)界限）。當(dāng)時，停止迭代。比較兩次迭代的狀態(tài)值函數(shù)差的絕對值（或差的平方），當(dāng)最大值小于閾值時，終止迭代。2023/11/523:45期望更新法（expectedupdate）

4.1策略迭代（8）13

根據(jù)給定的策略（動作分布），采取可能的動作，得到單步轉(zhuǎn)移后的所有狀態(tài)和獎勵，并利用下一狀態(tài)的值函數(shù)

。通過分布的期望值，更新狀態(tài)s的值函數(shù)。2023/11/523:454.1策略迭代（9）2023/11/523:4514異步計算方式：

在相鄰的兩個迭代輪次

和

，保存同一組狀態(tài)值函數(shù)

。在中，存儲兩輪混合的函數(shù)值。因此在每次計算中，如果狀態(tài)

s

的值函數(shù)已被更新，那么當(dāng)用到

時，就使用已經(jīng)更新過的數(shù)據(jù)。

評估過程中，中間結(jié)果與狀態(tài)評估的先后次序密切相關(guān)。

4.1策略迭代（10）152023/11/523:45在相同情況下，利用兩種迭代方式評估，收斂后結(jié)果是相同的。但收斂速度方面相比較，通常異步計算方式收斂速度會更快。同步計算方式：

在每一迭代輪次

，都保存相鄰兩輪的狀態(tài)值函數(shù)：和

。在計算

過程中，使用的全部是上一輪的

值。

評估過程中，中間結(jié)果與狀態(tài)評估的先后次序無關(guān)。

4.1策略迭代（11）162023/11/523:45算法4.1可用于有窮狀態(tài)空間的確定MDP問題和隨機(jī)MDP問題，這具體體現(xiàn)在MDP的狀態(tài)轉(zhuǎn)移動態(tài)：對于確定MDP問題，在當(dāng)前狀態(tài)s下采取動作a，到達(dá)下一狀態(tài)

的概率為1，而到達(dá)其他狀態(tài)的概率均為0。對于隨機(jī)MDP問題，在當(dāng)前狀態(tài)s下采取動作a，到達(dá)下一狀態(tài)

是隨機(jī)的。

4.1策略迭代（12）172023/11/523:45

4.1策略迭代（13）18因此利用算法4.1解決確定MDP問題和隨機(jī)MDP時，只是狀態(tài)轉(zhuǎn)移動態(tài)的變化，而算法本身不需要改變。這也體現(xiàn)出確定MDP是隨機(jī)MDP的特例。2023/11/523:45例4.1對確定環(huán)境掃地機(jī)器人任務(wù)進(jìn)行策略評估。

4.1策略迭代（14）19機(jī)器人在非終止?fàn)顟B(tài)（除位置0、12、19）均采取等概率策略：

掃地機(jī)器人最多可以采取4個動作。獎賞：2023/11/523:45評估過程（1）4.1策略迭代（15）202023/11/523:45評估過程4.1策略迭代（16）212023/11/523:45評估過程4.1策略迭代（17）22當(dāng)時，，認(rèn)為已經(jīng)收斂于，計算得到的就是在策略下的有效評估。2023/11/523:45每輪狀態(tài)值函數(shù)的更新過程4.1

策略迭代（18）232023/11/523:45異步動態(tài)規(guī)劃法（AsynchronousDynamicProgarmming，ADP）

4.1策略迭代（19）24

采用異步計算方式時，每一輪迭代都直接用新產(chǎn)生的值函數(shù)來替換舊的值函數(shù)，不需要對上一輪迭代的狀態(tài)值函數(shù)進(jìn)行備份，既減少了迭代次數(shù)，又節(jié)省了存儲空間。對于上述掃地機(jī)器人任務(wù)，采用異步計算方式進(jìn)行評估，30輪迭代后既可以收斂到，而采用同步計算方式，收斂到則需要51輪迭代。另外，使用異步計算方式時，每次遍歷并不需要對所有的狀態(tài)值函數(shù)都做一次更新，而可以任意順序更新狀態(tài)值，這樣其中的某些狀態(tài)值可能會在其他狀態(tài)值更新一次之前已經(jīng)更新過多次。2023/11/523:45ADP的特點歸納

4.1策略迭代（20）25ADP可以對更新順序進(jìn)行調(diào)整，通常重要的狀態(tài)優(yōu)先更新；實際情況中，ADP必須保證完成所有狀態(tài)的價值更新；ADP并不一定能減少計算量。但該方法的作用在于：算法在改進(jìn)策略之前不需要陷入無望的長時間掃描。2023/11/523:454.1策略迭代（21）例4.2對隨機(jī)環(huán)境掃地機(jī)器人任務(wù)進(jìn)行策略評估。

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

假設(shè)由于地面的問題，采取某一動作后，狀態(tài)轉(zhuǎn)換不再確定。當(dāng)采取某一動作試圖向某一方向移動時，機(jī)器人成功移動的概率為0.80，保持原地不動的概率為0.15，移動到相反方向的概率為0.05。262023/11/523:454.1策略迭代（22）

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

272023/11/523:454.1策略迭代（23）獎賞函數(shù)

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

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

相關(guān)。

282023/11/523:45評估過程4.1策略迭代（24）292023/11/523:45評估過程4.1策略迭代（25）302023/11/523:45評估過程4.1策略迭代（26）31當(dāng)時，，認(rèn)為已經(jīng)收斂于，計算得到的就是在策略下的有效評估。2023/11/523:45每輪狀態(tài)值函數(shù)更新過程4.1

策略迭代（27）322023/11/523:45基于動作值函數(shù)的策略評估4.1策略迭代（28）33基于動作值函數(shù)的策略評估迭代式為：2023/11/523:454.1策略迭代（29）342023/11/523:454.1策略迭代（30）例4.3基于Q值函數(shù)對確定環(huán)境掃地機(jī)器人任務(wù)進(jìn)行策略評估35整體狀態(tài)與動作條件與例4.1保持一致。動作順序：折扣系數(shù)：2023/11/523:457-10.0

狀態(tài)0.0000.000;0.000*.***0.0000.000;0.000*.***0.0000.000;0.000*.***0.0000.000;0.000*.***0.0000.267;0.000*.***0.0000.267;0.0000.267-10.0

0.107;0.0000.0710.000-1.964;0.0000.01890.0000.0710.1074.1策略迭代（31）

狀態(tài)0.0000.000;0.000*.***0.0000.000;0.000*.***0.0000.000;0.000*.***0.0000.000;0.000*.***0.0000.267;0.000*.***0.0000.267;0.0000.267-10.0

0.107;0.0000.0710.000-1.964;0.0000.0189-1.9640.314;0.189*.***-1.9570.314;-1.9640.314-11.964

-0.659;-0.389-0.435-2.093-2.689;-0.102-0.218-3.719-0.573;-0.102*.***-3.773-0.585;-3.719-0.573-13.719

-1.729;-1.729-1.417-3.189-3.719;-0.709-1.024-3.719-0.573;-0.102*.***-3.773-0.585;-3.719-0.573-13.719

-1.729;-1.729-1.417-3.189-3.719;-0.709-1.024-3.719-0.573;-0.102*.***-3.773-0.585;-3.719-0.573-13.719

-1.729;-1.729-1.417-3.189-3.719;-0.709-1.024面向確定環(huán)境掃地機(jī)器人任務(wù)的動作值函數(shù)

評估過程當(dāng)時，，認(rèn)為已經(jīng)收斂于，計算得到的就是在策略下的有效評估。結(jié)論4.1策略迭代（32）4.1策略迭代（33）例4.4基于Q值函數(shù)對隨機(jī)環(huán)境掃地機(jī)器人任務(wù)進(jìn)行策略評估38整體狀態(tài)與動作條件與例4.1保持一致。動作順序：折扣系數(shù)：狀態(tài)轉(zhuǎn)移情況如圖所示。2023/11/523:457-7.997

狀態(tài)0.0000.000;0.000*.***0.0000.000;0.000*.***0.0000.000;0.000*.***0.0000.000;0.000*.***0.0000.188;0.019*.***0.0120.197;0.0240.189-7.997

-0.193;-0.2620.6960.001-1.463;0.1350.010-0.2620.696-0.1934.1策略迭代（34）評估過程4.1策略迭代（44）40同理可以計算動作值函數(shù)，

，。按順序計算完一輪后，得到動作值函數(shù)。當(dāng)時，，認(rèn)為已經(jīng)收斂于，計算得到的就是在策略下的有效評估。2023/11/523:454.1策略迭代（45）41面向隨機(jī)環(huán)境掃地機(jī)器人任務(wù)的動作值函數(shù)

評估過程2023/11/523:45策略改進(jìn)4.1策略迭代（46）42

策略的優(yōu)劣性可以由值函數(shù)來評價。通過策略評估迭代得到值函數(shù)，再利用動作值函數(shù)來尋找更好的策略。

假設(shè)已知某一策略的值函數(shù)或，目的是尋找一個更優(yōu)策略。2023/11/523:45特殊情況到一般情況對策略改進(jìn)方法4.1策略迭代（47）43特殊情況針對單一狀態(tài)s和特定動作a，制定如下約定以獲得新策略：在狀態(tài)s下選擇一個新動作

；保持后續(xù)（其他）狀態(tài)所執(zhí)行的動作與原策略給出的動作相同。2023/11/523:45根據(jù)動作值函數(shù)貝爾曼方程，得到的價值為：若成立，則說明滿足以上約定的策略

優(yōu)于或等價于。特殊情況到一般情況對策略改進(jìn)方法4.1策略迭代（48）442023/11/523:45特殊情況到一般情況對策略改進(jìn)方法4.1策略迭代（49）45一般情況將單一狀態(tài)和特定動作的情況進(jìn)行拓展。對任意狀態(tài)，若存在任意的兩個確定策略和滿足策略改進(jìn)定理，則說明在狀態(tài)s處采取策略時，能得到更大的值函數(shù)，即優(yōu)于或等價于。

策略改進(jìn)定理為：即：2023/11/523:45特殊情況到一般情況對策略改進(jìn)方法4.1策略迭代（50）462023/11/523:45確定貪心策略4.1策略迭代（51）47隨機(jī)貪心策略2023/11/523:454.1.2策略迭代4.1策略迭代（52）48

策略迭代的關(guān)鍵部分是策略評估，首先評估狀態(tài)的價值，然后根據(jù)狀態(tài)的動作值進(jìn)行相應(yīng)的策略改進(jìn)，并進(jìn)行下一輪評估和改進(jìn)，直到策略穩(wěn)定。策略改進(jìn)可以通過求解靜態(tài)最優(yōu)化問題來實現(xiàn)，通過狀態(tài)動作值來選擇動作，通常比策略評估容易。2023/11/523:454.1.2.1基于狀態(tài)值函數(shù)的策略迭代4.1策略迭代（53）49基于狀態(tài)值函數(shù)的策略迭代算法主要包括以下3個階段：（1）初始化策略函數(shù)和狀態(tài)值函數(shù)；（2）策略評估：在當(dāng)前策略下，使用貝爾曼方程更新狀態(tài)值函數(shù)

，直到收斂于，再計算出。（3）策略改進(jìn)：基于，通過貪心策略得到更優(yōu)策略。2023/11/523:454.1策略迭代（54）502023/11/523:454.1策略迭代（55）512023/11/523:454.1策略迭代（56）例4.5將基于狀態(tài)值函數(shù)的策略迭代算法4.3應(yīng)用于例4.1的確定環(huán)境掃地機(jī)器人任務(wù)52經(jīng)過多輪迭代后，得到下表所示的值函數(shù)和策略迭代更新過程。2023/11/523:454.1策略迭代（57）53表4.3面向確定環(huán)境掃地機(jī)器人任務(wù)的狀態(tài)值函數(shù)策略迭代更新過程2023/11/523:454.1策略迭代（58）54表4.3面向確定環(huán)境掃地機(jī)器人任務(wù)的狀態(tài)值函數(shù)策略迭代更新過程（續(xù)）2023/11/523:454.1策略迭代（59）55面向確定環(huán)境掃地機(jī)器人任務(wù)的狀態(tài)值函數(shù)及策略迭代更新過程圖2023/11/523:454.1策略迭代（60）56面向確定環(huán)境掃地機(jī)器人任務(wù)的狀態(tài)值函數(shù)及策略迭代更新過程圖（續(xù)）2023/11/523:454.1策略迭代（61）例4.6

汽車租賃問題。57汽車租賃場（A，B租賃場）：每租出一輛車，獲得10美元的租金；兩租賃場移動車輛費用2美元；假設(shè)每個租賃場租車和還車的數(shù)量是一個泊松隨機(jī)量：

即：期望數(shù)量n的概率為：

任何一個租賃場車輛總數(shù)不超過20輛車；當(dāng)天還回的車輛第2天才能出租。兩個租車場之間每天最多可移車數(shù)量為5輛。2023/11/523:45狀態(tài)空間：

動作空間：

可移動車輛數(shù)目不超過5輛。設(shè)A租賃場向B租賃場移車為“-”，B租賃場向A租賃場移車為“+”。離散化為11個不同的動作。即：4.策略迭代（62）汽車租賃任務(wù)的MDP數(shù)學(xué)建模如下：58狀態(tài)共個，即：2023/11/523:45狀態(tài)轉(zhuǎn)移函數(shù)狀態(tài)轉(zhuǎn)移函數(shù)計算為：4.1策略迭代（63）592023/11/523:45狀態(tài)轉(zhuǎn)移函數(shù)如果且，則有：4.1策略迭代（64）602023/11/523:45獎賞函數(shù)

該問題的立即獎賞函數(shù)為：，即在當(dāng)前狀態(tài)下，采取動作a，到達(dá)下一狀態(tài)得到的立即獎賞。

61兩個租賃場的租車收益：4.1策略迭代（65）2023/11/523:45獎賞函數(shù)兩個租賃場之間的移車費用：；

62獲得的立即獎為：。4.1策略迭代（66）2023/11/523:45

634.1策略迭代（67）關(guān)于汽車租賃問題的策略迭代過程2023/11/523:454.1.2.2基于動作值函數(shù)的策略迭代

644.1策略迭代（68）2023/11/523:45

654.1策略迭代（69）2023/11/523:454.1策略迭代（70）例4.7將基于動作值函數(shù)的策略迭代算法4.4應(yīng)用于例4.1的確定環(huán)境掃地機(jī)器人任務(wù)。表4.4面向確定環(huán)境掃地機(jī)器人任務(wù)的基于動作值函數(shù)的策略迭代更新過程662023/11/523:454.1策略迭代（71）67表4.4面向確定環(huán)境掃地機(jī)器人任務(wù)的基于動作值函數(shù)的策略迭代更新過程（續(xù)）2023/11/523:45目錄68前言44.2值迭代4.1策略迭代4.3廣義策略迭代4.4小結(jié)2023/11/523:45

4.2值迭代（1）在策略迭代中，每輪策略改進(jìn)之前都涉及策略評估，每次策略評估都需要多次遍歷才能保證狀態(tài)值函數(shù)在一定程度上得到收斂，這將消耗大量的時間和計算資源。

值迭代公式2023/11/523:4569

4.2值迭代（2）根據(jù)迭代次數(shù)與策略穩(wěn)定的相互關(guān)系，考慮在單步評估之后就進(jìn)入改進(jìn)過程，即采取截斷式策略評估，在一次遍歷完所有的狀態(tài)后立即停止策略評估，進(jìn)行策略改進(jìn)，這種方法稱為值迭代。

2023/11/523:4570

4.1值迭代（3）在有窮狀態(tài)空間MDP中，基于狀態(tài)值函數(shù)的值迭代算法。2023/11/523:4571

4.2值迭代（4）在有窮狀態(tài)空間MDP中，基于狀態(tài)值函數(shù)的值迭代算法（續(xù)）2023/11/523:4572

4.2值迭代（5）在有窮狀態(tài)空間MDP中，基于動作值函數(shù)的值迭代算法。2023/11/523:4573

4.2值迭代（6）在有窮狀態(tài)空間MDP中，基于動作值函數(shù)的值迭代算法（續(xù)）2023/11/523:45744.2值迭代（7）例4.8將基于狀態(tài)值函數(shù)的值迭代算法4.5應(yīng)用于確定環(huán)境掃地機(jī)器人任務(wù)。75當(dāng)時（為值迭代次數(shù)），對于所有的初始化為；當(dāng)時，以狀態(tài)為例。在策略下，只能采取向下和向左2個動作，概率各為0.5。采取向下的動作時，到達(dá)狀態(tài)，并可以撿到垃圾，獲得的獎賞；采取向左的動作時，到達(dá)狀態(tài)，獲得的獎賞。2023/11/523:454.2值迭代（8）762023/11/523:454.2值迭代（9）77當(dāng)時，以狀態(tài)為例，計算狀態(tài)值函數(shù)。異步計算方式，通常與迭代的計算順序有關(guān)，根據(jù)例4.1規(guī)定，在每一輪次中，這3個狀態(tài)的計算順序為

。2023/11/523:454.3.值迭代（10）782023/11/523:454.2值迭代（11）79當(dāng)時，，認(rèn)為已經(jīng)收斂于，計算得到的就是最優(yōu)狀態(tài)值函數(shù)。2023/11/523:454.2值迭代（12）80表4.5確定環(huán)境掃地機(jī)器人任務(wù)的基于狀態(tài)值函數(shù)的值迭代更新過程2023/11/523:454.2值迭代（13）81表4.6確定掃地機(jī)器人任務(wù)的基于動作值函數(shù)的值迭代更新過程2023/11/523:454.2值迭代（14）例4.9賭徒問題游戲通過投擲骰子累加骰子點數(shù)之和來決定賭徒的輸贏。賭徒可以自己選擇重新投擲骰子或者結(jié)束整局游戲。如果選擇結(jié)束整局游戲，骰子總和數(shù)剛好18點，則賭徒贏得10元；骰子點數(shù)總和超過了18，則輸?shù)簦蛔狱c數(shù)總數(shù)-18）的資金；少于18，則輸?shù)簦ǎ┑馁Y金。當(dāng)點數(shù)超過或者等于18時，會自動結(jié)束整局游戲。2023/11/523:4582狀態(tài)空間：

當(dāng)前賭徒骰子點數(shù)的總和，即共24個狀態(tài)。動作空間：

賭徒可以選擇重新投擲骰子或是結(jié)束整局比賽，即兩個動作0代表結(jié)束游戲，1代表擲骰子。4.2值迭代（15）賭徒問題的MDP數(shù)學(xué)建模如下：832023/11/523:45狀態(tài)轉(zhuǎn)移函數(shù)：4.3.值迭代（17）84在當(dāng)前狀態(tài)下，采取動作a，到達(dá)下一狀態(tài)的概率。假設(shè)時執(zhí)行了動作1。那么有可能的狀態(tài)是共6種狀態(tài)，每個狀態(tài)的概率為。但當(dāng)，會自動執(zhí)行動作0來結(jié)束整個回合，并獲得回報。2023/11/523:45獎賞函數(shù)：4.2值迭代（17）85立即獎賞：賭徒重新投擲骰子會獲得0的立即獎賞。當(dāng)整局比賽結(jié)束，立即獎賞為：2023/11/523:45目錄86前言44.2值迭代4.1策略迭代4.3廣義策略迭代4.4小結(jié)2023/11/523:45廣義策略迭代（GeneralizedPolicyIteration，GPI）4.3廣義策略迭代（1）87

體現(xiàn)了策略評估與策略改進(jìn)交替進(jìn)行的一般性，強(qiáng)調(diào)策略評估和策略改進(jìn)的交互關(guān)系，而不關(guān)心策略評估到底迭代了多少次，或具體的策略評估和策略改進(jìn)的細(xì)節(jié)。

在GPI中，策略評估沒結(jié)束，就可以進(jìn)行策略改進(jìn)，只要這兩個過程都能不斷地更新，就能收斂到最優(yōu)值函數(shù)和最優(yōu)策略。從這一角度看，值迭代也屬于GPI，而實際上幾乎所有的強(qiáng)化學(xué)習(xí)方法都可以被描述為GPI2023/11/523:45廣義策略迭代（GeneralizedPolicyIteration，GPI）4.3廣義策略迭代（2）88

GPI體現(xiàn)了評估和改進(jìn)之間相互競爭與合作的關(guān)系：基于貪心策略，使得值函數(shù)與當(dāng)前策略不匹配，而保持值函數(shù)與策略一致就無法更新策略。在長期的博弈后，兩個流程會趨于一個目標(biāo)，即最優(yōu)值函數(shù)和最優(yōu)策略。2023/11/523:45廣義策略迭代（GeneralizedPolicyIteration，GPI）4.3廣義策略迭代（3）89

策略總是基于特定的值函數(shù)進(jìn)行改進(jìn)的，值函數(shù)始終會收斂于對應(yīng)的特定策略的真實值函數(shù)，當(dāng)評估和改進(jìn)都穩(wěn)定時，貝爾曼最優(yōu)方程便可成立，此時得到最優(yōu)值函數(shù)和最優(yōu)策略。換句話說，值函數(shù)只有與當(dāng)前策略一致時才穩(wěn)定，且策略只有是當(dāng)前值函數(shù)的貪心策略時才穩(wěn)定。2023/11/523:45動態(tài)規(guī)劃一些缺點4.3廣義策略迭代（4）

90在進(jìn)行最優(yōu)策略計算時，必須知道狀態(tài)轉(zhuǎn)移概率p；DP的推演是整個樹狀展開的，計算量大，存儲消耗資源多；每次回溯，所有可能的下一狀態(tài)和相應(yīng)動作都要被考慮在內(nèi)，存在維度災(zāi)難問題；由于策略初始化的隨機(jī)性，不合理的策略可能會導(dǎo)致算法無法收斂。2023/11/523:45目錄91前言44.2值迭代4.1策略迭代4.3廣義策略迭代4.4小結(jié)