CS 294: Deep Reinforcement Learning（5）

01-30

Berkeley深度強化學習的中文筆記（5）：MDP，值迭代，策略迭代

之前的四節講了優化控制，有模型的強化學習（model-based RL），在最後也看出了有模型的RL的一些弊端：動態模型可能很複雜，模型需要時間和數據進行學習，在建模時人為建立了很多額外假設。因此從這節開始，我們從另個角度出發，用無模型的強化學習（model-free RL）。不再關注對外部環境的建模，而僅關注值函數，策略函數，以此來做迭代優化。

這節開始，將部分與Sutton的Reinforcement Learning：An Introduction第二版聯合起來做筆記。（如果網上找不到資源可私信我）
這節的MDP在Sutton第二版書中的第3節，可以看到 $gamma$ 折扣反饋和 $T$ 步反饋的差別。
這節的值迭代，策略迭代也稱為動態規劃（dynamic programming）在書第四節，與蒙特卡洛方法和TD方法成為經典RL的三種基本方法。

在這一節中，我們先考慮一種比較簡單的情形：已知動態模型，而且狀態和動作都是離散有限的。而這個簡單的情形，為之後深入的model-free RL的求解過程和思想打下基礎。在求解之前，我們先重述一些MDP的術語：

馬爾科夫決策過程（Markov Decision Process，MDP）

$p(x_{t+1}|x_t,u_t)$ 表示狀態轉移函數： $x_{t+1}$ 僅與 $x_t,u_t$ 有關，而與條件 $x_{t-1},u_{t-1}$ 不相關。

MDP在第一節中就講過一些了，現在再定義一些記號：

$mathcal{S}$ ：狀態空間
$mathcal{A}$ ：動作空間
$P(r,s|s,a)$ ：狀態轉移概率，其中r是獎勵值，s是下一狀態。（也可以用 $P(s|s,a)$ ，以及 $R(s)$ 或 $R(a)$ 或 $R(s,a,s)$ 表示）
$a=pi(s)$ 確定性策略，或 $asim pi(a|s)$ 不確定性策略。

部分觀測的MDP（POMDP）：機器只能接收到觀測 $y$ ，而非完整的狀態s的信息，其中觀測與狀態關係： $ysim P(y|s)$ 。這種情況，觀測y不滿足Markov 性質。但POMDP可以轉化為MDP：通過重定義： $tilde s_0={y_0}$ ， $tilde s_1={y_0,y_1}…$ 但是這樣定義的狀態在步數比較多後，就太大了，可以對其窗口進行一些限制：比如只與前n個有關（n-gram）或者用LSTM。

MDP的例子：gym上的FrozenLake-v0，也是這次的作業題， $mathcal{S}$ 只有4個狀態：起始狀態，目標狀態，冰面，洞。當達到目標或洞時，回合結束。而達到目標狀態，r=1，未達到r=0。 $mathcal{A}$ 為上下左右四個動作，但是狀態轉移概率為：有50%概率朝錯誤方向前進。

與MDP相關的問題：

策略優化：選取一種策略使累積獎勵最大： $max_{pi} E[sum_{t=0}^{infty}r_t]$

策略評估：對於某個策略 $pi$ ，基於之後一段時間的獎勵來給出合理的評估反饋（return）：

反饋可以分兩種： $gamma$ 折扣反饋： $r_t+gamma r_{t+1}+gamma^2 r_{t+2}+…,gamma in (0,1)$ $qquadqquadqquadquad$ $T$ 步反饋： $r_t+r_{t+1}+…+r_{T-1}+V(s_T)$ ， $V(s_T)$ 是已知的對最終狀態作出評估的函數，可以是 $r_T$
基於上面的反饋，可以對策略的表現作出評估：

$qquadeta(pi)= E[sum_{t=0}^{infty}gamma^tr_t]$

但用的比較多的是，關於某一狀態的策略 $pi$ 的值函數，用於策略評估：

$qquad V^{pi}(s)=E[sum_{t=0}^{infty}gamma^tr_t|s_0=s]$

以及在該策略下的狀態—動作對的值函數，用在策略優化（選取greedy策略）時會很好用：

$qquad Q^{pi}(s,a)=E[sum_{t=0}^{infty}gamma^tr_t|s_0=s,a_0=a]$

值迭代（Value Iteration, VI）：

我們希望能夠通過對策略的評估，在T步反饋時是簡單的，然後取最優的策略/動作（貪心）；對於 $gamma$ 折扣反饋，我們需要在迭代中提升對策略的評估的正確性，同時取最優策略。

有限視野：

先考慮有限視野的情形，即採用T步反饋：那麼問題變為：

這裡策略 $pi_t$ 是隨時間t而變的， $V(s_T)$ 是已知的。在做出這樣假設後， $pi_t$ 與t之前的動作無關：

可依次求解得到單步最大的動作和值函數：

其中maximize的意思是得到argmax,max對，因此每一步可得到 $V_{t-1}(s)$ 用來做上一時間的求解。

用演算法表示：

如果仔細回憶一下，便發現這個過程其實和第二節筆記的優化控制的LQR一模一樣，只是LQR是線性的連續狀態空間，能得到 $pi_t(s)$ 為s的線性函數，是直接的解析表達式。而離散有限情況，往往不能有這麼好的顯式解析表達式。以上演算法，循環一次就可以得到分步最優的策略，以及對分步最優策略的正確的T步反饋評估。

無限視野有折扣：

現在我們希望能找到一個策略函數能對任一狀態出發最大化有折扣 $(gamma in[0,1))$ 的策略評估值 $V^{pi}(s)$ 。實際上有折扣的評估可以通過以下模型得到：原模型中每一步額外地會以 $1-gamma$ 的概率達到沉沒狀態（sink state）（終止，無獎勵）。直接先來看演算法：

可以任一選取初始值函數 $V^{(0)}(s)$ （選取的影響會隨著n增大而減小）。然後將更新步驟與有限視野的Algorithm 1對比，可以發現幾乎是一樣的更新步驟，因此Algorithm 2第n次循環其實就是n步評估下 $V_0$ 的值，而 $V_T(s_T)$ 為 $V^{(0)}(s)$ 。不同的是不同步驟的策略函數 $pi$ 是同一策略了，在每次迭代中更新；而且每次迭代值函數有折扣。

因此Algorithm 2可以理解為：在第n步循環時，拋棄掉 $r_n,r_{n+1},…$ ，只考慮前n步獎勵，這樣就變成了有限視野的問題。而且由於折扣 $gamma in[0,1)$ ，這樣拋棄的誤差為 $epsilon le r_{max}gamma^n/(1-gamma)$ ，隨著迭代步數n的增加而指數階減小。因此當 $ntoinfty$ 時，n步評估的 $pi_0,V_0$ 會收斂到最優的策略和值函數。

從運算元的視角看：

對於有限狀態空間，V是 $mathcal{S}$ 上的函數，其可以表示成 $|mathcal{S}|$ 維的向量，因此 $Vinmathbb R^{|mathcal{S}|}$ 。

那麼對於VI更新步驟，就可以看成 $R^{|mathcal{S}|}$ 到自身的映射： $mathcal{T}:mathbb R^{|mathcal{S}|}to mathbb R^{|mathcal{S}|}$ ，稱為backup運算元（backup operator），具體為：

$qquad[mathcal T V ](s) = max_a E_{s′ | s,a} [r + gamma V (s′)]$

因此更新步驟為： $V^{(n+1)} = mathcal T V^{(n)}$ 。

容易看出： $||mathcal T V ? mathcal T W||_{infty} le gamma||V ? W||_{infty}$ ，因此由壓縮映射定理， $V^{(n)}$ 最終會收斂到不動點：對最優策略的正確無限視野折扣評估。

策略迭代（Policy Iteration，PI）：

之前的值迭代的結果是得到了最優的策略，以及對該策略的正確評估。是因為在更新步驟中策略和值函數（評估正確性）是同時提升的。但現在我們想對一般的策略進行評估：

使用與之前一樣的方法，可以先考慮有限視野情形，發現迭代步驟為： $V_{t} = mathcal T^{pi} V_{t+1}$ ，其中：

與值迭代相比，只是每一步取最優動作改為了取評估對象 $pi$ 所給的動作。而且也 $mathcal T^{pi}$ 是滿足壓縮映射定理的，因此最終會收斂到正確評估。值得注意的是這個不動點 $V = mathcal T^{pi} V$ 是一個 $|mathcal{S}|$ 維線性方程，因此可以有顯式解：

從這一點出發，我們避免了對策略 $pi$ 評估時要做多次循環，而只需要解方程組即可。

這樣我們對任一策略 $pi$ 都能正確評估，那麼我們想得到最優策略，只需要在策略 $pi$ 的評估基礎上，每一狀態都取能讓 $V^{pi}$ 最大的動作（貪心）即可：

其中 $mathcal G V^{pi^{(n-1)}}$ 為 $pi^{(n)}(s)=argmax_a E_{s′ | s,a}V^{pi^{(n-1)}}(s)$ 。

容易證明 $V^{pi^{(0)}} le V^{pi^{(1)}}le V^{pi^{(2)}}le…$ ，因此策略是單調提升的，而且極限情況就是最優策略。

實際上策略迭代是比值迭代的收斂速度要快的（在這本書中有證明：M. L. Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.），但這點也會在這次的作業裡面很明顯地看出來（而且從作業中可以看出，冰面模型的隨機性導致了這種差異（擴大了感受野），策略迭代能很敏銳地發現值函數的變化，而值迭代只能一格一格地更新）。

策略迭代修改版：

有時候維數大時，或者更一般的無限情況，就無法解線性方程組了，為此我們結合值迭代和策略迭代，可以得到：

即在策略評估時，用迭代k步的方法進行評估。實際上，當 $k=1$ 時，這個就是值迭代；當 $k=infty$ 時，就是策略迭代。

這節動態規劃內容我也挺欣賞Sutton書上的條理：
他把RL的學習過程分為兩塊：策略估計（policy evaluation）和策略提升（policy improvement）。
對於第一塊策略估計，可以用Bellman等式得到Bellman backup（第7節也會說）： $V_{pi}(s) gets sum_api(a|s)sum_{s,r}p(s,r|s,a)[r+gamma V_{pi}(s)]=mathcal T^{pi} V_{pi}(s)$ （其中 $gets$ 表示更新步驟）我們之前證明了這個能收斂到正確的對 $pi$ 的值估計。
對於第二塊策略提升，可以證明策略提升定理：

如果 $Q_{pi}(s,pi(s)) ge V_{pi}(s)$ 對任意s成立，那麼 $pi$ 的值函數優於 $pi$ 的，因此根據提升定理，想要提升策略 $pi$ ，取貪心策略 $mathcal G V^{pi^{(n-1)}}$ 為 $pi^{(n)}(s)=argmax_a E_{s′ | s,a}V^{pi^{(n-1)}}(s)$ 。兩塊結合這就是我們的策略迭代啊！
然而策略迭代需要第一步策略估計比較準確，那麼需要做很多步的Bellman backup。
那麼考慮極端情況，只做一步策略估計，然後立馬做greedy策略提升，那麼就是我們的值迭代了啊！
因此Sutton通過一個general的學習過程策略估計+策略提升，把策略迭代和值迭代整合起來了，實際上這個general的學習過程將貫穿整個RL基本。

隨便說一句，這裡雖然策略迭代比值迭代的效果好，但是當環境模型未知時，值迭代（Q-learning）比策略迭代（Sarsa）有一個天然優勢，第七節將會講到。

總結

這一節為無模型的強化學習開了個頭，介紹了Markov決策過程（MDP）。引入值函數概念，以此出發來優化策略。對於策略有兩種評估方法： $gamma$ 折扣反饋，T步反饋。這節假設有限的狀態空間和已知模型。

對於有限視野的評估，我們引出了值迭代的思想和方法（根據對策略的評估：值函數，來選擇當前最優的策略，而經過迭代來提升值函數的正確性）。
並且推廣到無限的 $gamma$ 折扣評估，採用迭代更新值函數和策略的方法，最後收斂到最優策略和對其正確的評估。
同時我們從運算元的視角更清楚地來看這個過程 $V^{(n+1)} = mathcal T V^{(n)}$ 。

但我們並不滿足只對最優策略進行評估，或者不想策略和值函數同時提升。因此我們先對任一策略能做正確評估：相似的迭代的方法，或者解線性方程組 $V = mathcal T^{pi} V$ 。

基於對上一個策略的正確評估（解線性方程組），用貪心法來得到當前最好的策略。最後也能收斂到最優策略。
為了解決更一般的情況，在對當前策略評估時，用迭代的方法得到較優評估。

對於無限狀態空間和未知模型情形，下一節會講另一個無模型RL的方法：策略梯度方法。

這節的作業已經上傳到我的GitHub上了：https://github.com/futurebelongtoML/homework.git

是一個很簡單的MDP問題：FrozenLake-v0