動(dòng)態(tài)規(guī)劃與策略迭代、值迭代

本文目錄

??上一節(jié)我們說(shuō)了馬爾可夫決策過(guò)程，它是對(duì)完全可觀測(cè)的環(huán)境進(jìn)行描述的，也就是觀測(cè)到的內(nèi)容完整決定了決策所需要的特征。馬爾可夫決策過(guò)程可以用方程組求解簡(jiǎn)單問(wèn)題，但是對(duì)于復(fù)雜一點(diǎn)的問(wèn)題，一般通過(guò)迭代的思想對(duì)其進(jìn)行求解。動(dòng)態(tài)規(guī)劃是非常有效的求解馬爾可夫決策過(guò)程的方法。

動(dòng)態(tài)規(guī)劃初步理解

??動(dòng)態(tài)規(guī)劃求解的大體思想可分為兩種：1. 在已知模型的基礎(chǔ)之上判斷策略的價(jià)值函數(shù)，并在此基礎(chǔ)上尋找最優(yōu)的策略和最優(yōu)的價(jià)值函數(shù)。這種方法我們通常稱其為值迭代；2. 或者直接尋找最優(yōu)策略和最優(yōu)價(jià)值函數(shù)，這種方法稱為策略迭代。

?? 什么是動(dòng)態(tài)規(guī)劃

  • 動(dòng)態(tài)規(guī)劃算法，是解決復(fù)雜問(wèn)題的一個(gè)方法，將復(fù)雜問(wèn)題分解為子問(wèn)題，通過(guò)求解子問(wèn)題來(lái)得到整個(gè)問(wèn)題的解。

  • 在解決子問(wèn)題的時(shí)候，其結(jié)果通常需要存儲(chǔ)起來(lái)，用來(lái)解決后續(xù)復(fù)雜的問(wèn)題。

?? 什么樣的問(wèn)題，可以考慮使用動(dòng)態(tài)規(guī)劃來(lái)求解

  • 一個(gè)復(fù)雜問(wèn)題的最優(yōu)解由數(shù)個(gè)小問(wèn)題的最優(yōu)解構(gòu)成，可以通過(guò)尋找子問(wèn)題的最優(yōu)解來(lái)得到復(fù)雜問(wèn)題的最優(yōu)解；

  • 子問(wèn)題在復(fù)雜問(wèn)題內(nèi)重復(fù)出現(xiàn)，使得子問(wèn)題的解可以被存儲(chǔ)起來(lái)重復(fù)利用。

??馬爾可夫決策過(guò)程(MDP)具有上述兩個(gè)屬性：

??貝爾曼方程把問(wèn)題遞歸為求解子問(wèn)題，價(jià)值函數(shù)就相當(dāng)于存儲(chǔ)了一些子問(wèn)題的解，可以復(fù)用，因此可以使用動(dòng)態(tài)規(guī)劃來(lái)求解MDP。

??這一節(jié)是整個(gè)強(qiáng)化學(xué)習(xí)內(nèi)容的核心入門知識(shí)點(diǎn)。

??如何使用動(dòng)態(tài)規(guī)劃求解

??動(dòng)態(tài)規(guī)劃算法是用來(lái)求解一類被稱為規(guī)劃的問(wèn)題。規(guī)劃指的是，在了解整個(gè)馬爾可夫決策模型的基礎(chǔ)上來(lái)，求解最優(yōu)策略。也就是在已知模型結(jié)構(gòu)的基礎(chǔ)上(包括狀態(tài)-動(dòng)作空間轉(zhuǎn)移概率和獎(jiǎng)勵(lì)函數(shù))，求解最優(yōu)策略。

??主要是預(yù)測(cè)(prediction)和控制(control)：

  • Prediction：

??預(yù)測(cè)是指：給定一個(gè)MDP和策略\pi，要求輸出基于當(dāng)前策略\pi的價(jià)值函數(shù)。具體的數(shù)學(xué)描述為：給定一個(gè)MDP \langle\mathcal{S}, \mathcal{A},\mathcal{P}, \mathcal{R}, \mathcal{\gamma}\rangle和一個(gè)策略\pi，或者給定一個(gè)MRP\langle\mathcal{S}, \mathcal{P}, \mathcal{R}, \mathcal{\gamma}\rangle，要求輸出基于當(dāng)前策略的value function v_{\pi}。

  • Control：

??控制是指：給定一個(gè)MDP，要求確定最優(yōu)價(jià)值函數(shù)和最優(yōu)策略。給定一個(gè)MDP，要求確定最優(yōu)價(jià)值函數(shù)和最優(yōu)策略。具體的數(shù)學(xué)描述為：輸入一個(gè)MDP \langle\mathcal{S}, \mathcal{A},\mathcal{P}, \mathcal{R}, \mathcal{\gamma}\rangle，輸出optimal value function v_{*} 和 optimal policy \pi_{*}。

策略評(píng)估

??那迭代法策略評(píng)估如何求解呢？策略評(píng)估(Policy Evaluation)指的是求解給定的策略下的值函數(shù)，也就是預(yù)測(cè)當(dāng)前策略下所能拿到的值函數(shù)問(wèn)題。把這個(gè)計(jì)算當(dāng)前的狀態(tài)值函數(shù)的過(guò)程，稱為--策略評(píng)估(Policy Evaluation)。解決方案是應(yīng)用Bellman期望方程進(jìn)行迭代。

??具體方法：在k+1次迭代中，使用v_{k}(s^{\prime})更新計(jì)算v_{k+1}(s)，其中s^{\prime}是s的后繼狀態(tài)，此種方法通過(guò)反復(fù)迭代最終將收斂v_{\pi}。

s-a-s'

??其數(shù)學(xué)語(yǔ)言描述如下：

\begin{aligned} v_{k+1}(s) &=\sum_{a \in \mathcal{A}} \pi(a | s)\left(\mathcal{R}_{s}^{a}+\gamma \sum_{s^{\prime} \in S} \mathcal{P}_{s s^{\prime}}^{a} v_{k}\left(s^{\prime}\right)\right) \end{aligned}

\begin{aligned} v^{k+1} &=\mathcal{R}^{\pi}+\gamma \mathcal{P}^{\pi} v^{k} \end{aligned}

??用直白一點(diǎn)的語(yǔ)言描述：基于一種策略\pi，不斷地對(duì)state value迭代。比如：你當(dāng)前在清華大學(xué)計(jì)算機(jī)系讀博士，你的state-value是什么？是你對(duì)以后進(jìn)入大廠、以后工資、生活條件有一個(gè)較好的預(yù)期。如上公式所述，當(dāng)前的state-value是由對(duì)后繼狀態(tài)的state-value估計(jì)所構(gòu)成。

??或者用策略(Policy)直接與環(huán)境互動(dòng)就可以得到它的值函數(shù)，數(shù)學(xué)表達(dá)形式如下：

E_{\pi}(s) = \mathbb{E}\left[ R_{t+1}+\gamma R_{t+2} + \cdots | S_{t}=s\right]

策略評(píng)估步驟

??那更具體策略評(píng)估(Policy Evaluation)的步驟是什么樣子的呢？我們看一下算法偽代碼：

Policy Evaluation

??這里就是拿著一個(gè)策略一直進(jìn)行迭代，直到值函數(shù)收斂。

策略迭代

??策略迭代法（Policy Iteration method）是動(dòng)態(tài)規(guī)劃中求最優(yōu)策略的基本方法之一。它借助于動(dòng)態(tài)規(guī)劃基本方程，交替使用“求值計(jì)算”和“策略改進(jìn)”兩個(gè)步驟，求出逐次改進(jìn)的、最終達(dá)到或收斂于最優(yōu)策略的策略序列。

??我們發(fā)現(xiàn)如果想知道最優(yōu)的策略，就需要能夠準(zhǔn)確估計(jì)值函數(shù)。然而想準(zhǔn)確估計(jì)值函數(shù)，又需要知道最優(yōu)策略，數(shù)字才能夠估計(jì)準(zhǔn)確。所以實(shí)際上這是一個(gè)“雞生蛋還是蛋生雞”的問(wèn)題。

??一般的策略迭代法的思路可總結(jié)為以下三個(gè)步驟：

  1. 以某種策略\pi開(kāi)始，計(jì)算當(dāng)前策略下的值函數(shù)v_{\pi}(s)。
  2. 利用這個(gè)值函數(shù)，更新策略，得到\pi^{*}。
  3. 再用這個(gè)策略\pi^{*}繼續(xù)前行，更新值函數(shù)，得到v_{\pi}^{\prime}(s)，一直到v_{\pi}(s)不在發(fā)生變化。

??第一步就是上文說(shuō)的策略評(píng)估(Policy Evaluation)

??第二步是如何更新策略的呢？

??大體思想是在當(dāng)前策略的基礎(chǔ)上，貪婪地選取行為，使得后繼狀態(tài)價(jià)值增加最多。Improve the policy by acting greedily with respect to v_{\pi}。

\pi^{\prime} = greedy(v_{\pi})

??這個(gè)計(jì)算最優(yōu)策略的過(guò)程，稱為--策略提升(Policy Improvement)

策略迭代步驟

??那更具體策略迭代法（Policy Iteration method）的步驟是什么樣子的呢？我們看一下算法偽代碼：

Policy Iteration method

??這里是將策略評(píng)估(Policy Evaluation)和策略提升 (Policy Improvement)結(jié)合起來(lái)，進(jìn)行迭代，直到策略收斂。

??策略迭代有點(diǎn)缺點(diǎn)，策略迭代的主要時(shí)間都花費(fèi)在策略評(píng)估上，對(duì)一個(gè)簡(jiǎn)單的問(wèn)題來(lái)說(shuō)，在策略評(píng)估上花費(fèi)的時(shí)間不算長(zhǎng)；但對(duì)復(fù)雜的問(wèn)題來(lái)說(shuō)，這個(gè)步驟的時(shí)間實(shí)在有些長(zhǎng)。一個(gè)最直接的想法就是，我們能不能縮短在策略評(píng)估上花的時(shí)間呢？有，就是價(jià)值迭代

值迭代

??理解價(jià)值迭代原理的思路，可以從策略迭代的缺點(diǎn)出發(fā)。

  1. 策略迭代的策略評(píng)估需要值函數(shù)完全收斂才進(jìn)行策略提升的步驟，能不能對(duì)策略評(píng)估的要求放低，這樣如果可以實(shí)現(xiàn)的話，速度會(huì)有所提升。

  2. 我們?cè)诓呗缘嘘P(guān)注的是最優(yōu)的策略，如果說(shuō)我們找到一種方法，讓最優(yōu)值函數(shù)和最優(yōu)策略同時(shí)收斂，那樣我們就可以只關(guān)注值函數(shù)的收斂過(guò)程，只要值函數(shù)達(dá)到最優(yōu)，那策略也達(dá)到最優(yōu)，值函數(shù)沒(méi)有最優(yōu)，策略也還沒(méi)有最優(yōu)。這樣能簡(jiǎn)化了迭代步驟。

??我們的問(wèn)題是尋找最優(yōu)策略\pi，值迭代的解決方案是：使用貝爾曼最優(yōu)方程，將策略改進(jìn)視為值函數(shù)的改進(jìn)，每一步都求取最大的值函數(shù)。具體的迭代公式如下所示：

v_{k+1}(s)=\max_{a \in \mathcal{A}}\left(R_{s}^{a}+\gamma \sum_{s^{\prime} \in S}\mathcal{P}_{ss^{\prime}}^{a}v_{k}(s^{\prime})\right)

??上面這個(gè)公式與策略迭代相比，沒(méi)有等到狀態(tài)價(jià)值收斂才去調(diào)整策略，而是隨著狀態(tài)價(jià)值的迭代，及時(shí)調(diào)整策略，這樣就大大減少了迭代的次數(shù)。

??也就是說(shuō)從初始狀態(tài)值函數(shù)開(kāi)始同步迭代計(jì)算，最終收斂，整個(gè)過(guò)程中沒(méi)有遵循任何策略。

??上述公式的理解可以參考下面這個(gè)推導(dǎo)：

值迭代

??由于策略的調(diào)整，我們現(xiàn)在的價(jià)值每次更新。傾向于貪婪法尋找到最優(yōu)策略對(duì)應(yīng)的后續(xù)的狀態(tài)價(jià)值。這樣收斂的速度會(huì)更快。

??在值迭代過(guò)程中，算法不會(huì)給出明確的策略，迭代過(guò)程其間得到的價(jià)值函數(shù)不對(duì)應(yīng)任何策略。

異步動(dòng)態(tài)規(guī)劃

??異步動(dòng)態(tài)規(guī)劃有幾個(gè)研究的點(diǎn)：

  • In-place dynamic programming

??原位動(dòng)態(tài)規(guī)劃，所謂的原位動(dòng)態(tài)規(guī)劃指的是原地更新下一個(gè)狀態(tài)的狀態(tài)值，而不像同步迭代那樣存儲(chǔ)新的狀態(tài)值。在這種情況下，按何種次序更新?tīng)顟B(tài)價(jià)值有時(shí)候會(huì)更有意義。

  • Prioritised sweeping

??重要狀態(tài)優(yōu)先更新，對(duì)那些重要的狀態(tài)優(yōu)先更新，一般使用td-error(反映的是當(dāng)前的狀態(tài)價(jià)值與更新后的狀態(tài)j價(jià)值差的絕對(duì)值)來(lái)確定哪些狀態(tài)是比較重要的。誤差越大越需要優(yōu)先更新。

  • Real-time dynamic programming

??實(shí)時(shí)動(dòng)態(tài)規(guī)劃，更新那些僅與個(gè)體關(guān)系密切的狀態(tài)。同時(shí)使用個(gè)體經(jīng)驗(yàn)來(lái)指導(dǎo)更新?tīng)顟B(tài)的選擇，有些狀態(tài)理論上存在，但是在現(xiàn)實(shí)生活中基本上不會(huì)出現(xiàn)，利用已有的現(xiàn)實(shí)經(jīng)驗(yàn)，對(duì)于那些個(gè)體實(shí)際經(jīng)歷過(guò)的狀態(tài)進(jìn)行價(jià)值更新。這樣個(gè)體經(jīng)常訪問(wèn)過(guò)的狀態(tài)得到較高品質(zhì)的更新。個(gè)體較少訪問(wèn)的狀態(tài)，其價(jià)值更新的機(jī)會(huì)就比較少，收斂速度會(huì)相對(duì)慢一點(diǎn)。

動(dòng)態(tài)規(guī)劃總結(jié)

  • 預(yù)測(cè)問(wèn)題：就是指在給定策略下，迭代計(jì)算價(jià)值函數(shù)。預(yù)測(cè)問(wèn)題的求解主要是通過(guò)Bellman Expectation Equation進(jìn)行Iterative或者Policy Evaluation。

  • 控制問(wèn)題-策略迭代：是指策略迭代，尋找最優(yōu)策略問(wèn)題。在先給定策略，或隨機(jī)策略下計(jì)算狀態(tài)價(jià)值函數(shù)，根據(jù)狀態(tài)函數(shù)，采用貪婪算法來(lái)更新策略，多次反復(fù)找到最優(yōu)策略。主要是通過(guò)Bellman Expectation Equation 和Greedy Policy Improvement進(jìn)行Policy Iteration。

  • 控制問(wèn)題-值迭代：?jiǎn)渭兊氖褂脙r(jià)值策略，全程沒(méi)有策略參與，也可以獲得最優(yōu)策略。但是我們需要知道狀態(tài)的轉(zhuǎn)移矩陣。通過(guò)Bellman Optimal Equation進(jìn)行Value Iteration。

??基于state-value function(v_{\pi}(s))每一次Iteration的 Complexity為O(mn^{2})，其中m表示action space，n表示state space。

??基于state-action value function (q_{\pi}(s,a))每一次Iteration的 Complexity為O(m^{2}n^{2})，其中m表示action space，n表示state space。

我的微信公眾號(hào)名稱：深度學(xué)習(xí)與先進(jìn)智能決策
微信公眾號(hào)ID：MultiAgent1024
公眾號(hào)介紹：主要研究強(qiáng)化學(xué)習(xí)、計(jì)算機(jī)視覺(jué)、深度學(xué)習(xí)、機(jī)器學(xué)習(xí)等相關(guān)內(nèi)容，分享學(xué)習(xí)過(guò)程中的學(xué)習(xí)筆記和心得！期待您的關(guān)注，歡迎一起學(xué)習(xí)交流進(jìn)步！

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容