這一節(jié)，我們先介紹強化學(xué)習(xí)中，當(dāng)馬爾科夫決策過程可以利用元組 (S,A,P,r,γ) 來描述，且轉(zhuǎn)移概率 P 已知(稱為基于模型強化學(xué)習(xí)），該類強化學(xué)習(xí)的優(yōu)化問題可以通過動態(tài)規(guī)劃算法進(jìn)行解決。

? ?

4.1. 什么是動態(tài)規(guī)劃

Richard Bellman在20世紀(jì)50年代提出的動態(tài)規(guī)劃（dynamic programming）概念，這是一種強大的算法設(shè)計技術(shù)——將問題分解成多個小問題，存儲它們的解，通過將其結(jié)合在一起，最終得到原始問題的解決方案。

了解更多相關(guān)知識請參考動態(tài)規(guī)劃_百度百科 (baidu.com)

4.2.動態(tài)規(guī)劃為什么可以求解基于模型強化學(xué)習(xí)

根據(jù)第二節(jié)(2.強化學(xué)習(xí)如何建模序貫決策問題 - 知乎 (zhihu.com))部分，介紹的狀態(tài)值函數(shù)與狀態(tài)-行為值函數(shù)的貝爾曼?程，最優(yōu)值函數(shù)和狀態(tài)行為值函數(shù)滿足下述方程：

? ? ? 從4.1部分介紹的動態(tài)規(guī)劃基礎(chǔ)知識可以知道，如果想利?動態(tài)規(guī)劃解決的問題需要滿?兩個條件：?是整個優(yōu)化問題可以分解為多個?優(yōu)化問題；?是?優(yōu)化問題的解可以被存儲和重復(fù)利?。

? ? ?從第二節(jié)(2.強化學(xué)習(xí)如何建模序貫決策問題 - 知乎 (zhihu.com))回憶下述圖和值函數(shù)的迭代計算公式，狀態(tài) s 處的值函數(shù) υπ(s) ，可以看成后繼狀態(tài)的值函數(shù) υπ(s′) 的表示。另外，動態(tài)規(guī)劃的第二個條件較容易滿足。因此，該類強化學(xué)習(xí)，可以通過動態(tài)規(guī)劃求解。

4.3.如何利用動態(tài)規(guī)劃求解基于模型強化學(xué)習(xí)

? ? ?對于求解上式(4.2)方程， ，Pssa，γ 和 Rsa 都是已知數(shù)， π(a|s) 為要評估的策略是指定的，也是已知值。方程中唯一的未知數(shù)是值函數(shù)，該方程，變成求解值函數(shù)的線性方程組，如何求解呢？

4.3.1. 線性方程組的迭代求解法

? ? ? 用方程表示一般的線性方程組： AX=b ? ?（4.3）

? ? ? 線性方程組的數(shù)值求解包括直接法（如高斯消元法、矩陣三角分解法、平方根法、追趕法等）和迭代解法。策略評估中采用線性方程組的迭代解法。

? ? ? ?所謂迭代解法是根據(jù)(4.3)式設(shè)計一個迭代公式，任取初始值 X(0) ，將其導(dǎo)入到設(shè)計的迭代公式中，得到 X(1) ，再將代入迭代公式中得到 X(2) ，如此循環(huán)最終得到收斂的 X 。常用的迭代方法有：

方法一：雅可比(Jacobi)迭代法

? ? ? ?方法二：高斯-賽德爾迭代法

4.3.2. 基于動態(tài)規(guī)劃的基于模型強化學(xué)習(xí)迭代算法設(shè)計思路

? ? ? 此處，我們使用高斯-賽德爾迭代算法進(jìn)行求解(4.2)。

思考題：上述迭代公式，能夠獲得線性方程組(4.2)的解嗎？答案請參考4.3.5解內(nèi)容

基本問題1：策略評估算法。給定?個策略π，如何計算在策略π下的值函數(shù)？

基本問題2：策略改善算法。如何利?值函數(shù)進(jìn)?策略改善，從?得到最優(yōu)策略？

? ? ?個很?然的?法是當(dāng)已知當(dāng)前策略的值函數(shù)時，在每個狀態(tài)采?貪婪策略對當(dāng)前策略進(jìn)?改善

4.3.3.基于模型強化學(xué)習(xí)迭代算法——策略迭代算法

? ? ? 策略迭代算法包括策略評估和策略改善兩個步驟。在策略評估中，給定策略，通過數(shù)值迭代算法不斷計算該策略下每個狀態(tài)的值函數(shù)。利用該值函數(shù)和貪婪策略得到新的策略。

? ? ? 從策略迭代的偽代碼我們看到，進(jìn)?策略改善之前需要得到收斂的值函數(shù)。值函數(shù)的收斂往往需要很多次迭代(如下圖所示)，現(xiàn)在問題是進(jìn)?策略改善之前?定要等到策略值函數(shù)收斂嗎？

答案:不?定要等到策略評估算法完全收斂。

如果我們在評估一次之后就進(jìn)行策略改善，則稱為值函數(shù)迭代算法(接下來要介紹的算法)。

4.3.4.基于模型強化學(xué)習(xí)迭代算法——值迭代算法

? ? ? 值函數(shù)迭代算法的偽代碼如下：

4.3.5.高斯-賽德爾迭代的策略評估算法會收斂嗎？

? ?首先介紹一個數(shù)學(xué)概念：壓縮映射(contraction mapping)。

? ?定義：設(shè) X 是度量空間，其度量用 ρ 表示。映射 T:X→X ,若存在a, 0≤a<1 使得 ρ(Tx,Ty)≤aρ(x,y),?x,y∈X , 則稱 T 是 X 上的一個壓縮映射。

? ?定理1：完備度量空間上的壓縮映射具有唯一的不動點。

? ?定理1，也可以解釋為，從度量空間任何一點出發(fā)，只要滿足壓縮映射，壓縮映射的序列必定會收斂到唯一的不動點。因此，證明一個迭代序列是不是收斂，只需證明該序列所對應(yīng)的映射是不是壓縮映射。

在回答策略評估算法是否收斂的證明中

4.4.思考

思考1：基于模型的策略迭代算法，優(yōu)化變量(迭代策略)收斂性嗎？

思考2：基于模型的值函數(shù)迭代算法，優(yōu)化變量(迭代策略)收斂性嗎？