強化學習筆記4—動態規劃

05-09

術語動態規劃(Dynamic Programming, or DP)指一系列給定環境模型為馬爾科夫決策過程，用於計算最優策略的演算法。因為要求環境模型的完美假設和巨大的計算消耗，經典DP演算法在RL中作用有限，但理論上依然重要，因其是理解本書後面演算法的必要基礎。實際上，所有這些方法都可以認為是在消耗更少計算資源和沒有完美環境模型的條件下獲得與DP相同效果的努力。

從本章開始，我們通常假設環境是一個有限MDP，即假定其狀態、行為、和激勵集合， $mathcal S, mathcal A(s)$ ，和 $mathcal R$ ，對 $s inmathcal S$ ，是有限的；環境的動態由概率集合 $p(s,rmid s,a)$ ，對所有 $s in mathcal S, a in mathcal A(s), r in mathcal R$ 和 $s in mathcal S^+$ （ $mathcal S$ 加上終止狀態若任務是分節的）。儘管DP思想可應用於連續狀態和行為空間，但僅在特殊情況中才可能有精確解。DP和一般強化學習的關鍵思想，就是使用價值函數來組織和安排良好的策略搜索。回憶貝爾曼最優性方程：

$egin{eqnarray*} v_*(s) &=& max_a mathbb Eleft[ R_{t+1} + gamma v_*(S_{t+1}) middle | S_t=s, A_t=a ight] \ &=& max_a sum_{s,r} p(s,rmid s,a)left[ r + gamma v_*(s) ight] ag{4.1} end{eqnarray*}$

或

$egin{eqnarray*} q_*(s,a) &=& mathbb E left[ R_{t+1} +gammamax_a q_*(S_{t+1}, a) middle | S_t=s, A_t=a ight] \ &=& sum_{s,r} p(s,rmid s,a)left[ r+gammamax_{a} q_*(s,a) ight] ag{4.2} end{eqnarray*}$

對任意 $s in mathcal S, a in mathcal A(s)$ 和 $s in S^+$ 。DP演算法通過將貝爾曼方程轉化為賦值，也就是改善期望價值函數近似量的更新規則來獲得。

4.1 策略評估（預測）

首先考慮如何計算任意策略 $pi$ 的狀態-價值函數 $v_pi$ ，這在DP中稱為策略評估(policy evaluation)。這裡也稱為預測問題。對任意 $s in mathcal S$ ：

$egin{eqnarray*} v_pi(s) &=& mathbb E_pi[G_t mid S_t=s] \ &=& mathbb E_pi[R_{t+1} + gamma G_{t+1}mid S_t=s] \ &=& mathbb E_pi[R_{t+1} + gamma v_pi(S_{t+1})mid S_t=s] ag{4.3} \ &=& sum_a pi(amid s) sum_{s,r}p(s,rmid s,a)left[ r+gamma v_pi(s) ight] ag{4.4} end{eqnarray*}$

其中 $pi(amid s)$ 是策略 $pi$ 下狀態 $s$ 時採取行動 $a$ 的概率。只要 $gamma<1$ 或 $pi$ 下從所有狀態開始都能終止，就能保證 $v_pi$ 的存在和唯一。若環境動態完全已知，則(4.4)就是 $leftvertmathcal S ightvert$ 個 $leftvertmathcal S ightvert$ 元線性方程組。這裡更適合用迭代方法，考慮一個近似價值函數序列 $v_0, v_1, v_2,cdots$ ，每個都映射 $mathcal S^+$ 到 $mathbb R$ （這裡的每個 $v_k$ 都是狀態的一種價值函數），初始估計 $v_0$ 可任意選擇（除終止狀態必須為0），每個後繼近似都通過使用(3.14)作為更新規則獲得，對任意 $s in mathcal S$ ：

$egin{eqnarray*} v_{k+1}(s) &=& mathbb E_pi[R_{t+1}+gamma v_k(S_{t+1}) mid S_t=s] \ &=& sum_a pi(amid s)sum_{s,r} p(s,rmid s,a) left[ r+gamma v_k(s) ight] ag{4.5} end{eqnarray*}$

顯然 $v_k=v_pi$ 是這個更新規則的固定點，因 $v_pi$ 的貝爾曼方程保證了這種情況的等價性。實際上，在與確保 $v_pi$ 存在相同的條件下，序列 ${v_k}$ 通常會隨 $k o infty$ 收斂於 $v_pi$ 。這種演算法稱為迭代策略評估。

為從 $v_k$ 得到每個後繼近似 $v_{k+1}$ ，迭代策略評估對每個狀態 $s$ 應用同樣的操作：將 $s$ 的舊價值替換為從 $s$ 後繼狀態舊價值得到的新值、即時激勵的期望，伴隨著被評估策略下所有一步轉移的可能性。稱這種操作為全備份，每一步迭代備份一次每個狀態的價值以產生新的近似價值函數 $v_{k+1}$ 。有幾種不同的全備份，取決於備份的是狀態還是狀態-行動，也取決於後繼狀態評估的值組合的精確方式。DP演算法中所做的所有備份都是全備份，因其基於所有可能的下個狀態而非一個樣本。

要實現迭代策略評估的計算機程序，可以使用兩個數組分別存儲 $v_k(s)$ 和 $v_{k+1}(s)$ 。但更簡單的是用一個數組並「就地」更新舊值，也就是每個新的備份值立即覆蓋舊值，然後依賴於狀態備份的順序，有時新值會代替舊值在(4.5)右側使用。這種演算法也收斂到 $v_pi$ ，事實上速度更快，因其獲得新值後便立即使用。我們認為備份是在狀態空間的掃描中完成的，對就地演算法而言，掃描期間狀態備份的順序對收斂速度影響顯著，在提到DP演算法時記住通常是就地演算法。

另一個實現點與演算法的終止有關。正式情況下，迭代策略評估演算法僅在極限情況下(in the limit)收斂，但實際中必須短於此停止。通常的停機條件是在每步迭代後測試 $max_{sinmathcal S}leftvert v_{k+1}(s)-v_k(s) ightvert$ ，當充分小的時候停止。下面展示了帶停機標準的完整演算法：

示例4.1：考慮下面展示的 $4 imes 4$ 網格世界，

非終止狀態是 $mathcal S={1,2,dots,14}$ ，每個狀態有4種行動 $mathcal A={mathtt{up, down, right, left}}$ ，也確定了相應的狀態轉移，除了使代理離開網格實際保持不變的行動。這是一個無折扣分節任務，所有轉移的激勵是-1直到到達終止狀態。終止狀態是圖中陰影部分（儘管展示了兩個地方但形式上是一個狀態）。圖4.1左側展示了由迭代策略評估計算的價值函數序列 ${v_k}$ 。最終評估實際是 $v_pi$ ，這種情況下給每個狀態從次開始到終結的期望步數的負數。

4.2 策略改善

計算一個策略的價值函數的原因之一是幫助找到更好的策略。假定已確定任一策略 $pi$ 的價值函數 $v_pi$ ，對某個狀態 $s$ 要知道是否需改變策略選擇一個行動 $a eq pi(s)$ 。已經知道從狀態 $s$ 開始遵循當前策略的好壞——就是 $pi(s)$ ，但轉到新策略會變得如何呢？一種方法是考慮在 $s$ 選擇 $a$ ，此後遵循已有的策略 $pi$ 。這種方法的價值是：

$egin{eqnarray*} q_pi(s,a) &=& mathbb E_pi left[ R_{t+1} + gamma v_pi(S_{t+1}) middle | S_t=s, A_t=a ight] \ &=& sum_{s,r} p(s,r mid s,a) left[ r + gamma v_pi(s) ight] ag{4.6} end{eqnarray*}$

關鍵標準是看這個值與 $pi(s)$ 的大小。若在 $s$ 選擇 $a$ 然後遵循 $pi$ 比始終遵循 $pi$ 更好，則能夠期待每次遇到 $s$ 時選擇 $a$ 會更好，因此這個新的策略事實上就是一個更好的策略。這是更一般的稱為策略改善定理的一種特殊情況。令 $pi$ 和 $pi$ 為任意策略對，若 $forall s in mathcal S$ ：

$q_pi(s, pi(s)) ge v_pi(s) ag{4.7}$

則策略 $pi$ 必然與策略 $pi$ 同樣或更好，也就是說 $pi$ 必然從 $forall s in mathcal S$ 獲得更多或相等的期望回報：

$v_pi(s) ge v_pi(s) ag{4.8}$

若對任意狀態(4.7)都是嚴格不等式，則(4.8)中至少有一個狀態是嚴格的。這個結果尤其適用於考慮一個改變的策略 $pi$ 與一個原始策略 $pi$ 除 $pi(s)=a eqpi(s)$ 都是等價的，則(4.7)在除 $s$ 外的所有狀態都成立，因此若 $q_pi(s,a)>pi(s)$ ，則改變的策略是比 $pi$ 更好的策略。證明策略改善理論背後的思想很簡單，從(4.7)開始持續展開 $q_pi$ 側並反覆應用(4.7)直到獲得 $v_{pi}(s)$ ：

$egin{eqnarray*} v_pi(s) &le& q_{pi}(s, pi(s)) \ &=& mathbb E_{pi} left[ R_{t+1} +gamma v_pi(S_{t+1}) middle | S_t=s ight] \ &le& mathbb E_{pi} left[ R_{t+1} +gamma q_pi(S_{t+1}, pi(S_{t+1})) middle | S_t=s ight] \ &=& mathbb E_{pi} left[ R_{t+1} +gamma mathbb E_{pi}(R_{t+2}+gamma v_pi(S_{t+2})) middle | S_t=s ight] \ &=& mathbb E_{pi} left[ R_{t+1} + gamma R_{t+2}+gamma^2 v_pi(S_{t+2}) middle | S_t=s ight] \ &le& mathbb E_{pi} left[ R_{t+1} + gamma R_{t+2} + gamma^2 R_{t+3} + gamma^3v_pi(S_{t+3}) middle | S_t=s ight] \ &vdots& \ &le& mathbb E_{pi} left[ R_{t+1} + gamma R_{t+2} + gamma^2 R_{t+3} + gamma^3R_{t+4} + cdots middle | S_t=s ight] \ &=& v_{pi}(s) end{eqnarray*}$

目前已看到給定策略及其價值函數，如何評估此策略下在單個狀態到一個特定行動的改變。很自然地考慮在所有狀態到所有可能行動的改變，在每個狀態選擇表現出最好 $q_pi(s,a)$ 的行動。換句話說，考慮如下貪心策略：

$egin{eqnarray*} pi(s) &dot=& argmax_a q_pi(s,a)\ &=& argmax_a mathbb Eleft[ R_{t+1} + gamma v_pi(S_{t+1}) middle | S_t=s, A_t=a ight] ag{4.9}\ &=& argmax_a sum_{s,r} p(s,rmid s,a)left[ r+gamma v_pi(s) ight] end{eqnarray*}$

貪心策略選擇基於 $v_pi$ 短期的最優行動。由其構造，貪心策略滿足策略改善定理的條件，因此與原策略相比也等優或者更優。這種通過貪心選擇原策略價值函數來產生新策略以改善原策略過程稱為策略改善。假定新的貪心策略 $pi$ ，等優、但不優於舊策略 $pi$ ，則 $v_pi = v_{pi}$ 。由(4.9)，它滿足 $forall s in mathcal S$ ：

$egin{eqnarray*} v_{pi}(s) &=& max_a mathbb Eleft[ R_{t+1} + gamma v_{pi}(S_{t+1}) middle | S_t=s, A_t=a ight]\ &=& max_a sum_{s,r} p(s,rmid s,a) left[ r+gamma v_{pi}(s) ight] end{eqnarray*}$

這與貝爾曼最優性方程相同，因此 $v_{pi}$ 必然是 $v_*$ ，而 $pi$ 和 $pi$ 都是最優策略。策略改善必然給出嚴格更優的策略除非原策略已是最優。

目前這節內容已經考慮了確定性策略的特殊情況，在更一般的情況中，一個隨機策略 $pi$ 確定在每種狀態下採取每種行動的概率 $pi(amid s)$ ，這一節所有的內容都能很方便地擴展到隨機策略。尤其是策略改善定理在隨機情況中像陳述的那樣成立。另外，如果在策略改善中有平局——也就是有多個行為取得了最大值——則在隨機過程中不必從中挑選一個，而是每個最大的行為都賦予被新貪心策略選中的概率的一部分。任何分配計劃都可以，只要所有次優行為都賦予0概率。

圖4.1的最後一行展示了改善隨機策略的一個示例。原策略是等概率隨機的，新策略 $pi$ ，則是關於 $v_pi$ 貪心的，價值函數 $v_pi$ 展示在底部左側圖表中，可能的策略 $pi$ 集在底部右側圖表。任何這樣策略 $v_{pi}(s)$ 的價值函數通過檢查可看到所有狀態 $s in mathcal S$ 可能是-1，-2或-3，而最大是-14。因此 $v_{pi}(s) ge v_pi(s),quadforall sinmathcal S$ ，展示了策略改善。儘管在這個示例中新的策略 $pi$ 是最優，但通常僅能保證一步改進。

4.3 策略迭代

一旦某個策略 $pi$ 用 $v_pi$ 改善產生更好的策略 $pi$ 後，則能計算 $v_{pi}$ 然後又產生更好的 $pi$ ，因此就能獲得一序列單調遞增改進的策略和價值函數。

$egin{CD} pi_0 @>E>> v_{pi_0} @>I>> pi_1 @>E>> v_{pi_1} @>I>> pi_2 @>E>> cdots @>I>> pi_* @>E>> v_* end{CD}$

其中 $egin{CD} @>E>> end{CD}$ 表示策略評估， $egin{CD} @>I>> end{CD}$ 表示策略改善。每個策略都保證為前一個的嚴格改善（除非已是最優）。因有限MDP僅有有限的策略，這個過程必然會在有限次迭代後收斂到最優策略和最優價值函數。這種尋找最優策略的方法稱為策略迭代，完整的演算法在如下面所示（注意它有一個細小的缺陷，就是可能會在兩個或多個同樣好的策略中切換而永不終止，可通過增加額外的flag修正）。注意每個策略評估本身也是迭代計算，從前一個策略的價值函數開始。這通常能帶來策略評估收斂速度的巨大提升（大概是因為價值函數從一個策略到下一個改變很小）。

策略迭代通常以令人驚異的速度收斂，如圖4.1的例子展示的那樣。策略改善了理論保證了這些策略優於原始的隨機策略。在這種情形中，這些策略不僅是更優，而是最優，以最小的步數進展到了終止狀態。在這個示例中，策略迭代僅在一步之後就找到了最優策略。

示例4.2 Jack的汽車租賃：Jack管理一家全國範圍汽車租賃公司的兩個地點。每天一些顧客到這兩個地點租車。如果Jack有車則租出去然後通過全國公司記入$10的貸方。若在那個地點沒車，則錯失這筆生意。車在被歸還的後一天才能被出租。為確保車在需要的時候能獲得，Jack可以在一個晚上的時間將車在兩個地點間移動，每輛車移動的代價為$2。假定每個地點車輛的需求和歸還數是泊松隨機變數(Poisson random variables)，也就是數目為 $n$ 的概率為 $frac{lambda^n}{n!}e^{-lambda}$ ，其中 $lambda$ 為期望數目。假定第一個地點租賃和歸還的 $lambda$ 都是3，第二個地點租賃的 $lambda$ 為4，歸還為2。假定每個地點不超過20輛車，一個晚上能從一個地點移動的車不超過5輛。取折扣率為 $gamma=0.9$ 並將此問題建立為連續有限MDP，時間步是天，狀態是每個地點當天結束時的車輛數，行為是一晚在兩地點間移動車輛的凈數目。圖4.2展示了策略迭代從一輛車都不移動的策略開始找到的策略序列。

4.4 價值迭代

策略迭代的一個缺陷是它包含的策略評估本身也可能是一個耗時的迭代計算。若迭代地完成策略評估，則僅在極限時才會精確收斂到 $v_pi$ 。實際上策略迭代中的策略評估可以在不失去收斂保證的條件下用一些方法來截短。其中一種重要的特例是策略評估在一次掃描（每個狀態備份一次）後就停止。這種演算法稱為價值迭代，能夠寫成一個特別簡單的結合策略改善和截短的策略評估的備份操作，即對 $forall s in mathcal S$ ：

$egin{eqnarray*} v_{k+1}(s) &=& max_a mathbb Eleft[ R_{t+1} + gamma v_k(S_{t+1}) mid S_t=s, A_t=a ight]\ &=& max_a sum_{s, r} p(s,rmid s,a)left[ r+gamma v_k(s) ight] end{eqnarray*}$

對任意 $v_0$ ，序列 ${v_k}$ 能在保證 $v_*$ 存在同樣的條件下收斂到 $v_*$ 。另一種理解價值迭代的方法是參考貝爾曼最優性方程(4.1)。注意價值迭代策略僅是將貝爾曼最優性方程轉換為更新規則而得，同樣注意除了需從所有行動中採取最大值，價值迭代備份是如何與策略評估備份(4.5)等價的。也可以通過比較這些演算法的備份圖來理解這種緊密關係：圖3.7左邊展示了策略評估的備份圖，而圖3.7左側展示了價值迭代的備份圖。這兩個是計算 $v_pi$ 和 $v_*$ 的自然備份操作。

最後考慮價值迭代如何終止。與策略評估類似，價值迭代形式上要求無限次的迭代來恰好收斂到 $v_*$ 。實際上一旦價值函數在一次清掃中僅改變很小的量時就停機。價值迭代有效地結合了策略評估的一次清掃和策略改善的每一次清掃。通常，整個縮短的策略迭代演算法類可以認為是一系列清掃。其中一些使用策略評估備份，一些則使用價值迭代備份。因為(4.10)中的最大化操作是這些備份間僅有的差異，這就意味著最大操作附加到了策略評估的的清掃。所有這些演算法收斂到折扣有限MDP的最優策略。

示例4.3 賭徒難題：一個賭徒有機會為一系列拋擲硬幣的結果下注。若硬幣頭朝上，他贏得與下注數相等的美元；若尾朝上，則輸掉所下賭注。當賭徒贏得其目標100刀、或輸掉所有錢後，遊戲結束。每次拋擲，他都要決定用哪部分資本下注，以整數刀計。這個問題能表述為無折扣、分節、有限MDP。狀態為賭徒的資本 $sin{1,2,dots,99}$ ，行動為賭注 $ain{0,1,dots,min(s,100-s)}$ 。所有狀態轉移的激勵都為0，除了賭徒達到自己目標時激勵為+1。狀態-價值函數給出從每個狀態獲勝的概率，策略為從資本水平到賭注的映射，最優策略最大化達到目標的概率。令 $p_h$ 表示硬幣頭朝上的概率。若 $p_h$ 已知，則整個問題就已知並能被例如價值迭代的方法解決。圖4.3展示了 $p_h=0.4$ 時，在價值迭代連續的清掃中價值函數的變化，和找到的最終策略，策略最優但不唯一。實際上，存在一個最優策略族，對應為關於最優價值函數參數最大選擇的平局。試猜測整個族的樣子。

4.5 非同步動態規劃

目前為止所討論的DP方法都涉及MDP整個狀態集的操作，若狀態集非常大，則即便單步掃描的代價也會非常驚人。非同步DP演算法是不按照狀態集系統清理組織的就地迭代演算法，他們以任意順序備份狀態的價值，使用恰有的其他狀態的任意價值。一些狀態的價值可能在其他狀態備份前已備份數次，然而為正確地收斂，非同步演算法必須繼續備份所有狀態的價值：在計算的一些點以後不能忽視任何狀態。非同步DP演算法在選擇備份操作應用到的狀態中具有巨大的靈活性。

例如，一種非同步價值迭代在每一步 $k$ ，僅用(4.10)就地備份一個狀態 $s_k$ 。若 $0 le gamma < 1$ ，則僅給定所有在序列 ${s_k}$ 的狀態僅發生有限次（序列甚至可以是隨機的），就能保證漸進收斂到 $v_*$ （在無折扣分節情形中，可能存在一些備份順序不導致收斂，但可以相對簡單地避免）。同樣，也可能混合策略評估和策略迭代備份來產生一種非同步縮減策略迭代。顯然一些不同的備份形成能靈活地用在多種無清理DP演算法的模塊。

當然避免清理並不一定意味著計算量更少，僅意味著演算法在使用進展改善策略前無需被極度冗長的清理所束縛。可以嘗試通過選擇應用更新狀態的這種靈活性的優勢來改善演算法進展的速度。可以嘗試整理更新以使價值信息在狀態間高效地傳遞。一些狀態的價值可能無需像其他狀態一樣頻繁更新，甚至可以嘗試整個跳過某些狀態的更新，若其與最優行為無關。

非同步演算法也使得計算與實時交互更簡單。要解決給定的MDP，可以在代理真實經歷MDP的同時運行迭代DP演算法。代理的經驗能用於確定DP演算法將更新應用到哪個狀態。同時，來自DP演算法的最新價值和策略信息能夠指導代理的決策。例如，可以在代理訪問狀態時更新它們，這使得DP演算法的更新聚焦在狀態集中與代理最相關的部分。這種聚焦是強化學習中反覆的主題。

4.6 廣義策略迭代

策略迭代由兩個同時、交互的進程組成，其中一個使價值函數與當前策略一貫（策略評估），另一個使策略對當前價值函數貪婪（策略改善）。在策略迭代中，這兩個進程交替輪換，每個都在另一個開始前結束，但這並不是必須的。例如在價值迭代中，在每個策略改善之間僅進行單步策略迭代。在非同步DP方法中，評估和改善過程則更細粒度地互相交錯。某些情況中，在回到另一個之前單個進程僅更新單個狀態。只要兩個過程持續更新所有狀態，最終通常都會收斂到最優價值函數和最優策略。

使用術語廣義策略迭代(GPI)來表示與粒度和其他細節無關的策略評估和策略改善進程交互的一般思想。幾乎所有的強化學習演算法能用GPI很好地描述，即都有可識別的策略和價值函數，其中策略總是就價值函數改善，而價值函數則總被驅向策略的價值函數，如下圖所示。顯然若評估進程和改善進程都穩定，即不再產生變化時，則價值函數和策略就是最優的。僅當與當前策略一致時價值函數才穩定；而僅當關於當前價值函數貪心時策略才穩定。因此僅當策略關於其自身的評估函數貪心時兩者才豆穩定。這就意味著貝爾曼最優性方程(4.1)成立，此時的策略和價值函數是最優的。

GPI中的評估和改善過程競爭與合作。就往相反的方向拉拽它們是競爭的，策略關於價值函數貪心通常會使價值函數對改變後的策略錯誤，而價值函數與策略一致通常導致策略不再貪心。然而就長期而言，這兩個進程交互找到單個聯合解決方法：最優價值函數和最優策略。也可以依照兩個限制或目標來GPI中評估和改善進程的交互——比如下面圖中二維空間中的兩條直線。雖然實際的幾何會複雜得多，但圖表顯示了實際案例中所發生的事。每個過程驅使價值函數或策略到其中一條直線，表示其中一個目標的解法。兩個目標相交因兩者並非正交，往一個目標的驅動會導致到另一個目標的遠離。然後這個聯合進程必然被帶得離總體最優目標更近。在GPI中也可以向每個目標採用更小、非完整的步驟。在每種情況中，兩個進程一起到達總體最優目標，儘管都沒有嘗試直接去實現。