本章是整個(gè)課程中，算法與方法的第一章，應(yīng)該是最簡(jiǎn)單的入門(mén)方法。

上一章講到了貝爾曼最優(yōu)方程，其目的是計(jì)算出最優(yōu)狀態(tài)值，從而確定對(duì)應(yīng)的最優(yōu)策略。

而壓縮映射理論推出了迭代算法

對(duì)初始值V0賦一個(gè)隨機(jī)的初始值，算法最終總會(huì)找到這個(gè)最優(yōu)狀態(tài)值與最優(yōu)策略，就是上一章講到的穩(wěn)定點(diǎn)，這個(gè)方法就叫做值迭代法（value? iteration）。

那么如何實(shí)現(xiàn)這個(gè)值迭代算法呢？首先選擇貝爾曼最優(yōu)方程的矩陣-向量形式。

接著算法進(jìn)行迭代，每個(gè)迭代周期內(nèi)進(jìn)行兩步操作。第一步叫做策略升級(jí)，利用現(xiàn)有策略對(duì)應(yīng)參數(shù)，計(jì)算出其中的最優(yōu)策略記作下個(gè)時(shí)間點(diǎn)的策略Pi_k+1。

第二步叫做值的升級(jí)，利用第一步新得到的最優(yōu)策略，對(duì)現(xiàn)有的值進(jìn)行升級(jí)。

這里的Vk不是狀態(tài)值，因?yàn)樗灰欢M(mǎn)足貝爾曼方程（原文這樣寫(xiě)，我也沒(méi)明白為啥不一定滿(mǎn)足）

這里是采用矩陣-向量的形式進(jìn)行值迭代的理論分析，具體的算法實(shí)現(xiàn)，還是用基于元素的方式來(lái)完成。在基于元素的方式下，第一步策略升級(jí)的公式，可以寫(xiě)成如下這樣，向下的大括號(hào)整體上是行為值（Action?Value，第二章的內(nèi)容）

策略更新的本質(zhì)就是將每個(gè)狀態(tài)下的行為，都修改成行為值最大的那個(gè)，可以看出這是個(gè)基于貪心思路的策略。

第二步的值升級(jí)公式，在基于元素的形式下，可以寫(xiě)成如下形式

因?yàn)椴捎秘澬牡乃悸?#xff0c;這個(gè)新的值V_k+1等價(jià)于最優(yōu)的行為值（行為值最大的行為，采用的概率為100%，其余的為0%，就能得到最大值）。

整個(gè)計(jì)算的流程如下所示，依次計(jì)算各對(duì)應(yīng)的變量

值迭代算法的偽代碼（沒(méi)仔細(xì)看）

第二種算法叫做策略迭代法（Policy iteration algorithm），該算法也是分為兩步。初始情況下，給一個(gè)隨機(jī)的策略Pi_0。第一步是對(duì)這個(gè)策略進(jìn)行性能的量化，計(jì)算出狀態(tài)值。

第二步叫做策略改進(jìn)，逐狀態(tài)更新對(duì)應(yīng)的行為。

整個(gè)策略迭代法的計(jì)算順序如下所示，其中PE為策略估計(jì)，PI是策略提升。策略迭代算法本質(zhì)上是在策略估計(jì)中，嵌入了另一個(gè)迭代算法。

策略迭代算法的實(shí)現(xiàn)與值迭代算法類(lèi)似，都是采用基于元素的方式。策略迭代算法的策略評(píng)估，其基于元素的方法如下所示：

迭代的終止條件為j的值足夠大（即迭代足夠多的次數(shù)），或者迭代的過(guò)程中，前后兩次計(jì)算得到的狀態(tài)值差異足夠小。

第二步策略改進(jìn)的基于元素的方法如下所示

當(dāng)然需要的操作跟矩陣-向量形式一樣，都是先找尋最大行為值，再更新策略里的相關(guān)行為。

策略迭代的偽代碼如下（也沒(méi)仔細(xì)看）

下面討論的是值迭代法和策略迭代法之間的關(guān)系。下面是兩個(gè)算法的整體情況，都是分兩步進(jìn)行。策略迭代的初始是一個(gè)隨機(jī)的策略，值迭代的初始是一個(gè)隨機(jī)的狀態(tài)值。

兩個(gè)算法本質(zhì)上很相似，用；流水線的形式表示可以看出，兩個(gè)算法的開(kāi)頭相差一步，后面都是一樣的。

用表格的形式展示，可以看到算法的細(xì)節(jié)，后面的每一步雖然名字不同，但是計(jì)算的內(nèi)容大部分是一樣的。

第四步的計(jì)算是有差異的，策略迭代這里是要用一個(gè)無(wú)窮步迭代算法計(jì)算這個(gè)策略值，而值迭代這里只是一個(gè)一步的迭代運(yùn)算。

所以在做策略迭代的時(shí)候，這里要設(shè)置一個(gè)閾值j，迭代次數(shù)大于J的迭代操作予以舍棄，這叫做截?cái)嗟牟呗缘惴?#xff08;truncated policy iteration algorithm）。

這個(gè)是截?cái)嗟牟呗缘惴ǖ膫未a

下面是幾個(gè)算法測(cè)試的性能

既然有三種算法，那么在使用中又是如何取舍的？我問(wèn)了豆包，結(jié)果貼在了下面?？偟膩?lái)說(shuō)就是，簡(jiǎn)單問(wèn)題選值迭代，復(fù)雜問(wèn)題下資源（時(shí)間資源、計(jì)算資源）充足選策略迭代，資源不充足選基于截?cái)嗟牟呗缘?