基于動(dòng)態(tài)規(guī)劃的強(qiáng)化學(xué)習(xí)算法

學(xué)習(xí)「強(qiáng)化學(xué)習(xí)」（基于這本教材，強(qiáng)烈推薦）時(shí)的一些總結(jié)，在此記錄一下。

在馬爾可夫決策過(guò)程 環(huán)境模型已知（也就是狀態(tài)轉(zhuǎn)移函數(shù)P、獎(jiǎng)勵(lì)函數(shù)r已知）的情況下，我們可以通過(guò) 「動(dòng)態(tài)規(guī)劃」 求得馬爾可夫決策過(guò)程的最優(yōu)策略 \(\pi^*\) 。

1. 動(dòng)態(tài)規(guī)劃

對(duì)于做過(guò)算法題目的同學(xué)而言，這個(gè)詞應(yīng)該并不陌生，比較經(jīng)典的「背包問(wèn)題」就是需要利用「動(dòng)態(tài)規(guī)劃」。動(dòng)態(tài)規(guī)劃的思想是：將當(dāng)前問(wèn)題分解為子問(wèn)題，求解并記錄子問(wèn)題的答案，最后從中獲得目標(biāo)解。它通常用于求解「最優(yōu)」性質(zhì)的問(wèn)題。

而求解馬爾可夫決策過(guò)程最優(yōu)策略的動(dòng)態(tài)規(guī)劃算法主要有兩種：

1. 策略迭代
2. 價(jià)值迭代

2. 策略迭代

「策略迭代」 分為「策略評(píng)估」和「策略提升」兩部分。

策略評(píng)估

策略評(píng)估會(huì)先設(shè)定一個(gè)初始狀態(tài)價(jià)值函數(shù) \(V^0\)，再通過(guò)「動(dòng)態(tài)規(guī)劃」不斷更新策略的狀態(tài)價(jià)值函數(shù) \(V^{k+1} \leftarrow V^k\)，當(dāng)最大的「 \(V^{k+1}(s)\) 與上次的 \(V^k(s)\) 的差距」非常?。?\(<\theta\)）時(shí)，就結(jié)束迭代。

策略評(píng)估的迭代公式可以看作是「貝爾曼期望方程」+「動(dòng)態(tài)規(guī)劃」。我們可以看看兩者的不同：

光說(shuō)這些還是不容易理解的，我們用實(shí)例演示一遍吧。同樣以教材中的「懸崖環(huán)境」為例：

假設(shè)現(xiàn)在有這么一個(gè) \(5 \times 4\) 區(qū)域的懸崖，我們的目標(biāo)是要找出從起點(diǎn)到終點(diǎn)的最優(yōu)策略。我們把每個(gè)格子都當(dāng)成一個(gè)狀態(tài)，也就是說(shuō)，只要智能體移動(dòng)了一個(gè)格子，就轉(zhuǎn)換了一次狀態(tài)；并且智能體只能「上下左右」地走（如果將走出范圍，就當(dāng)作原地踏步，即「走到自身格子」），每走一步都是一個(gè)動(dòng)作且往不同方向走的概率是相同的。走到懸崖的獎(jiǎng)勵(lì)我們?cè)O(shè)為-100，走到正常位置的獎(jiǎng)勵(lì)設(shè)為-1，走到終點(diǎn)就直接結(jié)束（相當(dāng)于獎(jiǎng)勵(lì)是0），那么我們可以整理出獎(jiǎng)勵(lì)函數(shù) \(r(s, a)\)：

• 可能會(huì)有的疑惑：\(r(s, a)\) 不是 由狀態(tài)與動(dòng)作一起決定 的嗎，這里怎么把 \(r(s, a)\) 直接放在狀態(tài)上了？
  答：這其實(shí)是種簡(jiǎn)化的表達(dá)方式，我們應(yīng)該這么看：這里的 \(r(s, a)\) 指 從其它狀態(tài)（格子）以任意方向走到當(dāng)前狀態(tài)（格子）的 \(r(s, a)\)，只不過(guò)因?yàn)樗鼈兌枷嗤ㄒ驗(yàn)樵O(shè)置的這個(gè)環(huán)境比較特殊），所以寫(xiě)在了一起。比如下面這個(gè)紅色小旗所在格子位置上的 \(r(s, a)\) 其實(shí)是它周?chē)褡幼叩皆摳褡拥?\(r(s, a)\)：

  

1. 我們先讓初始 \(V^0\) 全為0，判定迭代結(jié)束的小閾值 \(\theta = 0.01\)，為了方便，讓折扣因子 \(\gamma = 1\)，而且由于走一步僅能到達(dá)一個(gè)狀態(tài)，所以讓所有的狀態(tài)轉(zhuǎn)移概率都為1 ：

2. 根據(jù)迭代公式，開(kāi)始迭代 \(V^1\)，先以起點(diǎn)的 \(V\) 開(kāi)始：

   
   \[ \begin{aligned} V^1(起) &= \frac{1}{4} \times ((-1) + 1 \times 1 \times(V^0(起上))) + \frac{1}{4} \times ((-1) + 1 \times 1 \times(V^0(起下))) \\ &+ \frac{1}{4} \times ((-1) + 1 \times 1 \times(V^0(起左))) + \frac{1}{4} \times ((-100) + 1 \times 1 \times(V^0(起右))) \\ &= \frac{1}{4} \times ((-1) + 1 \times 1 \times(0)) + \frac{1}{4} \times ((-1) + 1 \times 1 \times(0)) \\ &+ \frac{1}{4} \times ((-1) + 1 \times 1 \times(0)) + \frac{1}{4} \times ((-100) + 1 \times 1 \times(0)) \\ & = -25.75\\ \end{aligned} \]

   每個(gè)狀態(tài)（格子）都計(jì)算完后，就得到了完整的新的 \(V^1\):

   

3. 然后進(jìn)行評(píng)估，發(fā)現(xiàn) \(max\{|V^1(s) - V^0(s)|\} = 25.75 > \theta\)，還得繼續(xù)迭代

4. 重復(fù)與2相同的步驟，根據(jù) \(V^1\) 求出 \(V^2\)，又可以得到：

   

5. ……

總之，在經(jīng)過(guò)多輪的重復(fù)迭代后，我們?nèi)〉昧耸諗康?\(V\)，這時(shí)就進(jìn)入到了 「策略提升」 環(huán)節(jié)。

策略提升

接下來(lái)就是調(diào)整策略 \(\pi\) 了，我們可以直接貪心地在每一個(gè)狀態(tài)選擇動(dòng)作價(jià)值最大的動(dòng)作，也就是：

根據(jù)這個(gè)調(diào)整方式，來(lái)看看最終策略提升得到的新的 \(\pi^1\):

然而，這還沒(méi)有結(jié)束，如果不滿足 \(\pi^{k-1} = \pi^k\)，那么還需要繼續(xù)進(jìn)行策略迭代。如果滿足了，那么此時(shí)的 \(\pi^k\) 就是最優(yōu)策略、 \(V^k\) 就是最優(yōu)價(jià)值。在這里顯然 $ \pi^0 \neq \pi^1$，所以要繼續(xù)。

總結(jié)

最后，綜合「策略評(píng)估」和「策略提升」，得到策略迭代算法（教材中的）：

3. 價(jià)值迭代

「策略迭代算法」似乎計(jì)算量大了些，既要進(jìn)行不斷迭代 \(V\) ，還要迭代 \(\pi\)，有計(jì)算量比較小的算法嗎？ 「價(jià)值迭代算法」 可能可以滿足你的需求，它雖說(shuō)也要進(jìn)行 \(V\) 迭代，但卻只用一輪，而后就直接「蓋棺定論」將更改后得到的 \(\pi\) 作為「最優(yōu)策略」了。

它可以看作是：「貝爾曼最優(yōu)方程」+ 「動(dòng)態(tài)規(guī)劃」。

可以直接來(lái)對(duì)比下「策略迭代」與「價(jià)值迭代」：

紅色框表示的是「\(V\)迭代」，在這部分不同的是，「價(jià)值迭代」直接選取最大狀態(tài)價(jià)值而不是「策略迭代」的期望狀態(tài)價(jià)值；藍(lán)色框表示的是「\(\pi\)迭代」，「價(jià)值迭代」沒(méi)有對(duì)「策略」進(jìn)一步進(jìn)行迭代 （所以才叫「價(jià)值迭代」嘛

雖然很簡(jiǎn)單，但同樣我們也來(lái)實(shí)操一遍「價(jià)值迭代」，同樣用到剛剛的「懸崖」環(huán)境：

1. 初始化就不提了，直接根據(jù)迭代公式，開(kāi)始迭代 \(V^1\)，先以起點(diǎn)的 \(V\) 開(kāi)始：

   
   \[ \begin{aligned} V^1(起) &= max\{((-1) + 1 \times 1 \times(V^0(起上)))，((-1) + 1 \times 1 \times(V^0(起下)))， \\ & ((-1) + 1 \times 1 \times(V^0(起左)))，((-100) + 1 \times 1 \times(V^0(起右)))\}\\ &= max\{((-1) + 1 \times 1 \times(0))，((-1) + 1 \times 1 \times(0))， \\ & ((-1) + 1 \times 1 \times(0))，((-100) + 1 \times 1 \times(0))\} \\ & = max\{-1, -1, -1, -100\}\\ & = -1\\ \end{aligned} \]

   每個(gè)狀態(tài)（格子）都計(jì)算完后，就得到了完整的新的 \(V^1\):

   

2. 同樣評(píng)估一下是否 \(max\{|V^1(s) - V^0(s)|\} > \theta\) ，如有則繼續(xù)迭代。這里經(jīng)過(guò)7次迭代就達(dá)到判定閾值了：

   

3. 最后同樣選取最大動(dòng)作價(jià)值，來(lái)更新策略即可。如果動(dòng)作中有多個(gè)「最大動(dòng)作價(jià)值」的動(dòng)作，則給予等概率。

   

4. 總結(jié)

策略迭代在理論上能更好地收斂到最優(yōu)策略，但有著比較大的計(jì)算量；價(jià)值迭代可以通過(guò)較少的計(jì)算就收斂，但不像策略迭代那樣有嚴(yán)格的收斂性保證（可以看看這個(gè)數(shù)學(xué)證明）。只能說(shuō)各有優(yōu)劣，具體用哪個(gè)還得看實(shí)際情況。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-837696.html

到了這里，關(guān)于基于動(dòng)態(tài)規(guī)劃的強(qiáng)化學(xué)習(xí)算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！