上一節我們說了馬爾可夫決策過程，它是對完全可觀測的環境進行描述的，也就是觀測到的內容完整決定了決策所需要的特徵。馬爾可夫決策過程可以用方程組求解簡單問題，但是對於複雜一點的問題，一般通過迭代的思想對其進行求解。動態規劃是非常有效的求解馬爾可夫決策過程的方法。

動態規劃初步理解

動態規劃求解的大體思想可分爲兩種：1. 在 已知模型 的基礎之上判斷策略的價值函數，並在此基礎上尋找最優的策略和最優的價值函數。這種方法我們通常稱其爲 值迭代 ；2. 或者直接尋找最優策略和最優價值函數，這種方法稱爲 策略迭代 。

什麼是動態規劃

• 動態規劃算法，是解決複雜問題的一個方法，將複雜問題分解爲子問題，通過求解子問題來得到整個問題的解。

• 在解決子問題的時候，其結果通常需要存儲起來，用來解決後續複雜的問題。

什麼樣的問題，可以考慮使用動態規劃來求解

• 一個複雜問題的最優解由數個小問題的最優解構成，可以通過尋找子問題的最優解來得到複雜問題的最優解；

• 子問題在複雜問題內重複出現，使得子問題的解可以被存儲起來重複利用。

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

貝爾曼方程把問題遞歸爲求解子問題， 價值函數就相當於存儲了一些子問題的解 ，可以複用，因此可以使用動態規劃來求解 MDP 。

這一節是整個強化學習內容的 核心入門知識點 。

如何使用動態規劃求解

動態規劃算法是用來求解一類被稱爲規劃的問題。規劃指的是，在瞭解整個馬爾可夫決策模型的基礎上來，求解最優策略。也就是在已知模型結構的基礎上(包括狀態-動作空間轉移概率和獎勵函數)，求解最優策略。

主要是預測( prediction )和控制( control )：

• Prediction：

預測是指：給定一個 MDP 和策略，要求輸出基於當前策略的價值函數。具體的數學描述爲：給定一個 MDP 和一個策略，或者給定一個 MRP ，要求輸出基於當前策略的 value function 。

• Control：

控制是指：給定一個 MDP ，要求確定最優價值函數和最優策略。給定一個 MDP ，要求確定最優價值函數和最優策略。具體的數學描述爲：輸入一個 MDP ，輸出 optimal value function 和 optimal policy 。

策略評估

那迭代法策略評估如何求解呢？策略評估( Policy Evaluation )指的是求解給定的策略下的值函數，也就 是預測當前策略下所能拿到的值函數問題 。把這個計算當前的狀態值函數的過程，稱爲--策略評估( Policy Evaluation )。 解決方案 是應用 Bellman 期望方程進行迭代。

具體方法：在次迭代中，使用更新計算，其中是的後繼狀態，此種方法通過反覆迭代最終將收斂。

其數學語言描述如下：

用直白一點的語言描述：基於一種策略，不斷地對 state value 迭代。比如：你當前在清華大學計算機系讀博士，你的 state-value 是什麼？是你對以後進入大廠、以後工資、生活條件有一個較好的預期。如上公式所述，當前的 state-value 是由對後繼狀態的 state-value 估計所構成。

或者用策略( Policy )直接與環境互動就可以得到它的值函數，數學表達形式如下：

策略評估步驟

那更具體策略評估( Policy Evaluation )的步驟是什麼樣子的呢？我們看一下算法僞代碼：

這裏就是拿着一個策略一直進行迭代，直到值函數收斂。

策略迭代

策略迭代法（ Policy Iteration method ）是動態規劃中求最優策略的基本方法之一。它藉助於動態規劃基本方程，交替使用“ 求值計算 ”和“ 策略改進 ”兩個步驟，求出逐次改進的、最終達到或收斂於最優策略的策略序列。

我們發現如果想知道最優的策略，就需要能夠準確估計值函數。然而想準確估計值函數，又需要知道最優策略，數字才能夠估計準確。所以實際上這是一個“雞生蛋還是蛋生雞”的問題。

一般的策略迭代法的思路可總結爲以下三個步驟：

1. 以某種策略開始，計算當前策略下的值函數。

2. 利用這個值函數，更新策略，得到。

3. 再用這個策略繼續前行，更新值函數，得到，一直到不在發生變化。

第一步就是上文說的策略評估( Policy Evaluation )

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

大體思想是在當前策略的基礎上，貪婪地選取行爲，使得後繼狀態價值增加最多。 Improve the policy by acting greedily with respect to 。

這個計算最優策略的過程，稱爲--策略提升( Policy Improvement )

策略迭代步驟

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

這裏是將策略評估( Policy Evaluation )和策略提升 ( Policy Improvement )結合起來，進行迭代，直到策略收斂。

策略迭代有點缺點， 策略迭代的主要時間都花費在策略評估上 ，對一個簡單的問題來說，在策略評估上花費的時間不算長；但對複雜的問題來說，這個步驟的時間實在有些長。一個最直接的想法就是，我們能不能縮短在策略評估上花的時間呢？有，就是價值迭代

值迭代

理解價值迭代原理的思路，可以從策略迭代的缺點出發。

1. 策略迭代的策略評估需要值函數完全收斂才進行策略提升的步驟，能不能 對策略評估的要求放低 ，這樣如果可以實現的話，速度會有所提升。

2. 我們在策略迭代中關注的是最優的策略，如果說我們找到一種方法，讓 最優值函數和最優策略同時收斂 ，那樣我們就可以只關注值函數的收斂過程，只要值函數達到最優，那策略也達到最優，值函數沒有最優，策略也還沒有最優。這樣能簡化了迭代步驟。

我們的問題是尋找最優策略，值迭代的解決方案是：使用貝爾曼最優方程， 將策略改進視爲值函數的改進 ，每一步都求取最大的值函數。具體的迭代公式如下所示：

上面這個公式與策略迭代相比，沒有等到狀態價值收斂纔去調整策略，而是隨着狀態價值的迭代，及時調整策略，這樣就大大減少了迭代的次數。

也就是說從初始狀態值函數開始同步迭代計算，最終收斂，整個過程中沒有遵循任何策略。

上述公式的理解可以參考下面這個推導：

由於策略的調整，我們現在的價值每次更新。傾向於貪婪法尋找到最優策略對應的後續的狀態價值。這樣收斂的速度會更快。

在值迭代過程中，算法不會給出明確的策略，迭代過程其間得到的價值函數不對應任何策略。

異步動態規劃

異步動態規劃有幾個研究的點：

• In-place dynamic programming

原位動態規劃，所謂的原位動態規劃指的是原地更新下一個狀態的狀態值，而不像同步迭代那樣存儲新的狀態值。在這種情況下，按何種次序更新狀態價值有時候會更有意義。

• Prioritised sweeping

重要狀態優先更新，對那些重要的狀態優先更新，一般使用 td-error (反映的是當前的狀態價值與更新後的狀態j價值差的絕對值)來確定哪些狀態是比較重要的。誤差越大越需要優先更新。

• Real-time dynamic programming

實時動態規劃，更新那些僅與個體關係密切的狀態。同時使用個體經驗來指導更新狀態的選擇，有些狀態理論上存在，但是在現實生活中基本上不會出現，利用已有的現實經驗，對於那些個體實際經歷過的狀態進行價值更新。這樣個體經常訪問過的狀態得到較高品質的更新。個體較少訪問的狀態，其價值更新的機會就比較少，收斂速度會相對慢一點。

動態規劃總結

• 預測問題：就是指在給定策略下，迭代計算價值函數。預測問題的求解主要是通過 Bellman Expectation Equation 進行 Iterative 或者 Policy Evaluation 。

• 控制問題-策略迭代：是指策略迭代，尋找最優策略問題。在先給定策略，或隨機策略下計算狀態價值函數，根據狀態函數，採用貪婪算法來更新策略，多次反覆找到最優策略。主要是通過 Bellman Expectation Equation 和 Greedy Policy Improvement 進行 Policy Iteration 。

• 控制問題-值迭代：單純的使用價值策略，全程沒有策略參與，也可以獲得最優策略。但是我們需要知道狀態的轉移矩陣。通過 Bellman Optimal Equation 進行 Value Iteration 。

基於 state-value function ()每一次 Iteration 的 Complexity 爲，其中表示 action space ，表示 state space 。

基於 state-action value function ()每一次 Iteration 的 Complexity 爲，其中表示 action space ，表示 state space 。