在上一篇文章 強化學習（二）：馬爾可夫決策過程 中, 我們介紹用來對強化學習問題進行建模的馬爾可夫決策過程(Markov Decision Processes, MDPs).

由於MDPs的貝爾曼最優方程沒有封閉解, 因此一般採用迭代的方法對其進行求解.

本文將介紹使用動態規劃(Dynamic Programming)演算法來求解MDPs.

文章目錄

1. 動態規劃
1.1. 動態規劃的性質
1.2. 用動態規劃進行預測和控制
2. 策略評估
2.1. 策略評估問題
2.2. 迭代策略評估演算法
3. 策略改進
4. 策略迭代
4.1. 策略迭代
4.2. 策略迭代演算法
4.3. 策略迭代的擴展
4.3.1. 改良策略迭代
4.3.2. 廣義策略迭代
5. 值迭代
5.1. 最優性原則
5.2. 確定性值迭代
6. 同步動態規劃演算法總結
7. 動態規劃的擴展
7.1. 非同步動態規劃
7.1.1. 就地動態規劃
7.1.2. 優先掃描
7.1.3. 實時動態規劃
7.2. 全寬和採樣備份
7.2.1. 全寬備份
7.2.2. 採樣備份
8. 壓縮映射

1. 動態規劃

  • 動態(Dynamic): 問題中的時序部分
  • 規劃(Planning): 對問題進行優化

動態規劃將問題分解為子問題, 從子問題的解中得到原始問題的解.

1.1 動態規劃的性質

最優子結構(Optimal substructure)

  • 應用最優性原則(Principle of optimality)
  • 最優解可以從子問題的最優解中得到

重疊子問題(Overlapping subproblems)

  • 相同的子問題出現多次
  • 問題的解可以被緩存和復用

馬爾可夫決策過程滿足上面兩種性質:

貝爾曼方程 給出了問題的遞歸分解表示, 值函數 存儲和復用了問題的解.

v_{pi}(s) = sum limits_{a in mathcal{A}} pi(a|s) (mathcal{R}_s^a + gamma sum limits_{s in mathcal{S}} mathcal{P}_{ss}^{a}v_{pi}(s))

1.2 用動態規劃進行預測和控制

前提:

動態規劃假設我們知道MDP的所有知識, 包括狀態、行為、轉移矩陣、獎勵甚至策略等.

對於預測(Prediction)問題:

輸入:

  • MDP <mathcal{S}, mathcal{A}, mathcal{P}, mathcal{R}, gamma> 和 策略 pi
  • MRP <mathcal{S}, mathcal{P}^{pi}, mathcal{R}^{pi}, gamma>

輸出:

  • 值函數 v_{pi}

對於控制(Control)問題:

輸入:

MDP <mathcal{S}, mathcal{A}, mathcal{P}, mathcal{R}, gamma>

輸出:

  • 最優值函數 v_{*}
  • 最優策略 pi_{*}

2. 策略評估(Policy Evaluation)

2.1 策略評估問題

問題: 評估一個給定的策略 pi

求解: 對貝爾曼期望方程進行迭代, v_1 o v_2 o dots o v_{pi}

通常使用同步備份(synchronous backups)方法:

對於第 k+1 次迭代, 所有狀態 s 在第 k+1 時刻的價值 v_{k+1}(s) 用 v_k(s) 進行更新, 其中 s 是 s 的後繼狀態.

迭代策略評估

egin{aligned} v _ { k + 1 } ( s ) & = sum _ { a in mathcal { A } } pi ( a | s ) left( mathcal { R } _ { s } ^ { a } + gamma sum _ { s ^ { prime } in mathcal { S } } mathcal { P } _ { s s ^ { prime } } ^ { a } v _ { k } left( s ^ { prime } ight) ight) \ mathbf { v } ^ { k + 1 } & = mathcal { R } ^ { pi } + gamma mathcal { P } ^ { pi } mathbf { v } ^ { k } end{aligned}

2.2 迭代策略評估演算法

迭代策略評估演算法用來估計 V approx v_{pi} .

這裡使用in-place版本, 即只保留一份 v 數組, 沒有新舊之分.

通常來說, 該方法也能收斂到 v_{pi} , 而且收斂速度可能更快.

終止條件: max limits_ { s in mathcal{S} } left| v _ { k + 1 } ( s ) - v _ { k } ( s ) ight| 小於給定的誤差 heta .

迭代策略評估偽代碼

例子: Small Gridworld [代碼]

Small Gridworld

Small Gridworld Solution

3. 策略改進(Policy Improvement)

讓我們考慮一個確定性策略(即對於一個狀態來說, 其採取的動作是確定的, 而不是考慮每個動作的概率) a = pi(s) .

我們可以通過貪心選擇來改進策略 pi :

pi ^ { prime } ( s ) = underset { a in mathcal { A } } { operatorname { argmax } } q _ { pi } ( s , a )

即狀態 s 的新策略為令動作值函數 q_{pi}(s, a) 取得最大值的動作.

相應地, 動作值函數 q _ { pi } left( s , pi ^ { prime } ( s ) ight) 得到了改進:

q _ { pi } left( s , pi ^ { prime } ( s ) ight) = max _ { a in mathcal { A } } q _ { pi } ( s , a ) geq q _ { pi } ( s , pi ( s ) ) = v _ { pi } ( s ) \ {scriptsize 由於是確定性策略, 才會有 v_{pi}(s) = q_{pi}(s, pi(s))} ag{1}

注: 確定性策略下的動作值函數q_{pi}(s, a)為:

egin{aligned} q _ { pi } ( s , a ) & = mathbb { E } left[ R _ { t + 1 } + gamma v _ { pi } left( S _ { t + 1 } ight) | S _ { t } = s , A _ { t } = a ight] \ & = sum _ { s ^ { prime } , r } p left( s ^ { prime } , r | s , a ight) left[ r + gamma v _ { pi } left( s ^ { prime } ight) ight] end{aligned} ag{2}

從而, 值函數 v _ { pi ^ { prime } } ( s ) 也得到了改進:

egin{aligned} v_pi(s) & le q_pi(s,pi^{}(s)) {scriptsize //公式(1)} \ &={Bbb E}[R_{t+1} + gamma v_pi(S_{t+1})|S_t=s, A_t=pi^{}(s)] {scriptsize //公式(2)} \ &={Bbb E}_{pi}[R_{t+1}+gamma v_pi(S_{t+1})|S_t=s] {scriptsize //注意外層是在新策略 pi^{} 下求期望} \ & le {Bbb E}_{pi}[R_{t+1}+gamma q_pi(S_{t+1},pi(S_{t+1}))|S_t=s] {scriptsize //對狀態S_{t+1}使用公式(1)} \ &= {Bbb E}_{pi}[R_{t+1}+gamma {Bbb E}_{pi}left[ R_{t+2}+gamma v_{pi}left( S_{t+2} ight) | S_{t+1}, A_{t+1}=pi^{}(S_{t+1}) ight] | S_t=s]\ &= {Bbb E}_{pi}[R_{t+1}+gamma R_{t+2}+gamma^2 v_{pi}left( S_{t+2} ight)|S_t=s] {scriptsize //去掉括弧內的期望} \ & le {Bbb E}_{pi}[R_{t+1}+gamma R_{t+2}+gamma ^2 q_pi(S_{t+2},pi(S_{t+2}))|S_t=s] {scriptsize //對狀態S_{t+2}使用公式(1)} \ &= {Bbb E}_{pi}[R_{t+1}+gamma R_{t+2}+gamma^2 {Bbb E}_{pi}left( R_{t+3}+gamma v_{pi}left( S_{t+3} ight) ight)|S_t=s]\ &= {Bbb E}_{pi}[R_{t+1}+gamma R_{t+2}+gamma^2 R_{t+3}+gamma^3 v_{pi}left( S_{t+3} ight)|S_t=s]\ & vdots \ & le {Bbb E}_{pi}[R_{t+1}+gamma R_{t+2}+gamma^2 R_{t+3}+gamma^3 R_{t+4} + dots |S_t=s]\ &=v_{pi^{}}(s) \ end{aligned}

當改進停止時, 有如下等式:

q _ { pi } left( s , pi ^ { prime } ( s ) ight) = max _ { a in mathcal { A } } q _ { pi } ( s , a ) = q _ { pi } ( s , pi ( s ) ) = v _ { pi } ( s ) ag{3}

可以說, 此時公式(3)滿足了貝爾曼最優方程:

v _ { pi } ( s ) = max _ { a in mathcal { A } } q _ { pi } ( s , a )

從而, 對所有狀態 s 來說, 有 v_{pi}(s) = v_{*}(s) , 即策略 pi 改進到了最優策略.

4. 策略迭代(Policy Iteration)

4.1 策略迭代

給定一個策略 pi , 我們可以首先對策略進行評估, 然後根據值函數 v_{pi} 進行貪心地改進策略.

pi _ { 0 } stackrel { mathrm { E } } { longrightarrow } v _ { pi _ { 0 } } stackrel { mathrm { I } } { longrightarrow } pi _ { 1 } stackrel { mathrm { E } } { longrightarrow } v _ { pi _ { 1 } } stackrel { mathrm { I } } { longrightarrow } pi _ { 2 } stackrel { mathrm { E } } { longrightarrow } cdots stackrel { mathrm { I } } { longrightarrow } pi _ { * } stackrel { mathrm { E } } { longrightarrow } v _ { * }

其中, stackrel { mathrm { E } } { longrightarrow } 表示策略評估, stackrel { mathrm { I } } { longrightarrow } 表示策略改進.

  • 評估(Evaluate):

v _ { pi } ( s ) = mathbb { E } left[ R _ { t + 1 } + gamma R _ { t + 2 } + ldots | S _ { t } = s ight]

  • 改進(Improve):

    pi^{} = ext{greedy}(v_{pi})

由於每個策略都比前一個策略更優, 同時一個有限狀態的馬爾可夫決策過程(finite MDP)僅有有限個策略, 因此該過程一定能夠在有限次的迭代中收斂到最優策略 pi_{*}和最優值函數v_{*} .

策略迭代

4.2 策略迭代演算法

策略迭代演算法分為: 初始化, 策略評估 以及 策略改進 三部分.

其中, 策略改進部分的終止條件為: 是否所有狀態的策略不再發生變化.

策略迭代偽代碼

例子: Jack』s Car Rental [代碼] (先佔個坑 , 等有時間把這個例子詳細寫下)

Jack&amp;amp;amp;#39;s Car Rental

策略迭代求解結果:

Jack&amp;amp;amp;#39;s Car Rental Solution

圖中縱坐標是位置 1 的汽車數量, 橫坐標是位置 2 的汽車數量, 該問題共有 21 imes 21 個狀態.

圖中的等高線將狀態劃分為不同的區域, 區域內的數值代表相應的策略(正數代表從位置 1 移往位置 2 的汽車數量, 負數則往反方向移動).

4.3 策略迭代的擴展

4.3.1 改良策略迭代(Modified Policy Iteration)

策略評估並不需要真正的收斂到 v_{pi} . (比如在 Small Gridworld例子中, 迭代 k=3 次 即可以得到最優策略.)

為此我們可以引進終止條件, 如:

  • 值函數的 epsilon -收斂
  • 簡單地迭代 k 次便停止策略評估

或者每次迭代(即 k=1 )都對策略進行更新改進, 這種情況等價於值迭代(value iteration).

4.3.2 廣義策略迭代(Generalized Policy iteration)

廣義策略迭代(Generalized Policy iteration，GPI)指代讓策略評估(policy-evaluation)和策略改進(policyimprovement)過程進行交互的一般概念, 其不依賴於兩個過程的粒度(granularity)和其他細節.

幾乎所有強化學習方法都可以很好地被描述為GPI. 也就是說, 它們都具有可辨識的策略與值函數. 其中, 策略 pi 通過相應的值函數 v 進行改進, 而值函數 V 總是趨向策略 pi 的值函數 v^{pi} . 如下圖所示,

廣義策略迭代

5. 值迭代(Value Iteration)

策略迭代的一個缺點是它的每次迭代都涉及策略評估, 這本身就是一個需要對狀態集進行多次掃描的耗時迭代計算.

而在值迭代的過程中, 並沒有出現顯式的策略, 並且中間過程的值函數可能也不和任何策略對應.

5.1 最優性原則(Principle of Optimality)

一個最優策略可以被分解為兩部分:

  • 當前狀態的最優動作 A_{*}
  • 後繼狀態 S^{prime} 的最優策略
最優性原則

該原則的意思是說, 一個策略 pi(a|s) 在狀態 s 取到最優值函數 v_{pi}(s) = v_{*}(s) 當且僅當 對於所有從狀態 s 出發可到達的狀態 s^{prime} , 策略 pi 也能夠在狀態 s^{prime} 取到最優值函數.

5.2 確定性值迭代(Deterministic Value Iteration)

如果我們已經知道子問題的最優解 v_{*}(s^{prime}) , 那麼狀態 s 的最優解可以通過向前看(lookahead)一步得到, 這稱為值迭代(Value Iteration):

v_{*}(s) gets max limits_{a in mathcal{A}} left( mathcal{R}_{s}^{a} + gamma sum limits_{s in mathcal{S}} mathcal{P}_{ss}^{a} v_{*}(s) ight)

值迭代演算法:

值迭代演算法和策略迭代演算法一樣, 是用來估計最優策略 pi_{*} 的, 它將策略評估和策略改進有效地結合在了一起.

值迭代演算法

6. 同步動態規劃演算法總結

egin{array}{ccc} extbf{問題} & extbf{貝爾曼方程} & extbf{演算法} \ 預測(Prediction) & 貝爾曼期望方程 &迭代策略評估 \ 控制(Control) & 貝爾曼期望方程 + 貪心策略改進 & 策略迭代 \ 控制(Control) & 貝爾曼最優方程 & 值迭代 \ end{array}

對於有 m 個動作和 n 個狀態 的MDP來說, 每次迭代的時間複雜度如下:

egin{array}{cc} extbf{函數} & extbf{時間複雜度} \ v_{pi}(s) / v_{*}(s) & mathcal{O}(mn^2) \ q_{pi}(s, a) / q_{*}(s, a) & mathcal{O}(m^2n^2) \ end{array}

7. 動態規劃的擴展

7.1 非同步動態規劃(Asynchronous Dynamic Programming)

同步DP演算法的主要缺點是每次迭代都需要對整個狀態集進行掃描, 這對於狀態數非常多的MDP來說耗費巨大. 而非同步DP演算法則將所有的狀態獨立地,以任意順序進行備份, 並且每個狀態的更新次數不一, 這可以顯著地減少計算量.

為了保證演算法的正確收斂, 非同步動態規劃演算法必須保證所有狀態都能夠持續地被更新(continue to update the values of all the states), 也就是說在任何時刻任何狀態都有可能被更新, 而不能忽略某個狀態.

非同步DP演算法主要有三種簡單的思想:

  • 就地動態規劃(In-place dynamic programming)
  • 優先掃描(Prioritised sweeping)
  • 實時動態規劃(Real-time dynamic programming)

7.1.1 就地動態規劃

同步DP保留值函數的兩個備份, v_{new} 和 v_{old}

{color{red} {v_{new}(s)}} gets max limits_{a in mathcal{A}} left( mathcal{R}_{s}^{a} + gamma sum limits_{s in mathcal{S}} mathcal{P}_{ss}^{a} {color{red} {v_{old}(s)}} ight)

就地值迭代只保留值函數的一個備份.

{color{red} {v(s)}} gets max limits_{a in mathcal{A}} left( mathcal{R}_{s}^{a} + gamma sum limits_{s in mathcal{S}} mathcal{P}_{ss}^{a} {color{red} {v(s)}} ight)

7.1.2 優先掃描

使用貝爾曼誤差的大小來進行狀態的選擇:

left| max _ { a in mathcal { A } } left( mathcal { R } _ { s } ^ { a } + gamma sum _ { s ^ { prime } in mathcal { S } } mathcal { P } _ { s s ^ { prime } } ^ { a } v left( s ^ { prime } ight) ight) - v ( s ) ight|

  • 僅備份有最大貝爾曼誤差的狀態
  • 在每次備份後, 需要更新受到影響的狀態(即備份狀態的前驅狀態)的貝爾曼誤差
  • 可以使用優先隊列進行實現

7.1.3 實時動態規劃

  • 思想: 只使用和Agent相關的狀態
  • 使用Agent的經驗來進行狀態的選擇
  • 在每個時間步 S_t, A_t, R_{t+1} 對狀態 S_t 進行備份

{color{red} {v left( S _ { t } ight)}} gets max _ { a in mathcal { A } } left( mathcal { R } _ { {color{red}{S _ { t }}} } ^ { a } + gamma sum _ { s ^ { prime } in mathcal { S } } mathcal { P } _ { {color{red} {S _ { t }}} s ^ { prime }} ^ { a } {color{red} {v left( s ^ { prime } ight)}} ight)

7.2 全寬和採樣備份(Full-width and sample backups)

7.2.1 全寬備份

  1. DP使用全寬備份(full-width backups)
  2. 對於每次備份(不管同步還是非同步)
  • 每個後繼狀態和動作都會被考慮進去
  • 需要知道MDP轉移矩陣和獎勵函數

3. 對於大規模DP問題會遇到維數災難

4. 進行一次備份都太奢侈了

7.2.2 採樣備份

採樣備份(Sample Backups)使用採樣的獎勵和採樣的轉移 < S , A , R , S ^ { prime } > 來替代獎勵函數 mathcal{R} 和 轉移矩陣 mathcal{P} .

採樣備份的優點:

  • Model-free: 不需要知道MDP的先驗知識
  • 通過採樣緩解維數災難
  • 備份代價成為常量, 獨立於狀態數 n = |mathcal{S}|

8. 壓縮映射(Contraction Mapping)

關於上面的種種演算法, 我們可能會有如下疑問:

  • 值迭代是否會收斂到 v_{*} ?
  • 迭代策略評估是否會收斂到 v_{pi} ?
  • 策略迭代是否會收斂到 v_{*} ?
  • 解唯一嗎 ?
  • 演算法收斂速度有多快 ?

為瞭解決這些問題, 需要引入壓縮映射(contraction mapping)理論.

可以參考: 如何證明迭代式策略評價、值迭代和策略迭代的收斂性？

參考資料

  1. Reinforcement learning: An introduction (second edition) 第四章
  2. UCL Course on RL Lecture3: Planning by Dynamic Programming
  3. David Silver 增強學習——Lecture 3 動態規劃
  4. 強化學習（三）用動態規劃（DP）求解

推薦閱讀：

相關文章