作者：劉建平

編輯：黃俊嘉

在強化學習（二）馬爾科夫決策過程(MDP)中，我們討論了用馬爾科夫假設來簡化強化學習模型的復雜度，這一篇我們在馬爾科夫假設和貝爾曼方程的基礎上討論使用動態(tài)規(guī)劃(Dynamic Programming, DP)來求解強化學習的問題。

動態(tài)規(guī)劃這一篇對應Sutton書的第四章和UCL強化學習課程的第三講。

動態(tài)規(guī)劃和強化學習問題之間的聯系

對于動態(tài)規(guī)劃，相信大家都很熟悉，很多使用算法的地方都會用到。就算是機器學習相關的算法，使用動態(tài)規(guī)劃的也很多，比如之前講到的隱馬爾科夫模型HMM（二）前向后向算法評估觀察序列概率，隱馬爾科夫模型HMM（四）維特比算法解碼隱藏狀態(tài)序列， 都是動態(tài)規(guī)劃的典型例子。

動態(tài)規(guī)劃的關鍵點有兩個：

1. 第一是問題的最優(yōu)解可以由若干小問題的最優(yōu)解構成，即通過尋找子問題的最優(yōu)解來得到問題的最優(yōu)解。

2. 第二是可以找到子問題狀態(tài)之間的遞推關系，通過較小的子問題狀態(tài)遞推出較大的子問題的狀態(tài)。而強化學習的問題恰好是滿足這兩個條件的。

我們先看看強化學習的兩個基本問題。

1. 第一個問題是預測，即給定強化學習的6個要素：狀態(tài)集S，動作集A，模型狀態(tài)轉化概率矩陣P，即時獎勵R，衰減因子r，給定策略π，求解該策略的狀態(tài)價值函數

   
   。

2. 第二個問題是控制，也就是求解最優(yōu)的價值函數和策略。給定強化學習的5個要素：狀態(tài)集S，動作集A，模型狀態(tài)轉化概率矩陣P，即時獎勵R，衰減因子r，求解最優(yōu)的狀態(tài)價值函數

   
   和最優(yōu)策略
   
   。

那么如何找到動態(tài)規(guī)劃和強化學習這兩個問題的關系呢？

回憶一下上一篇強化學習（二）馬爾科夫決策過程(MDP)中狀態(tài)價值函數的貝爾曼方程：

從這個式子我們可以看出，我們可以定義出子問題求解每個狀態(tài)的狀態(tài)價值函數，同時這個式子又是一個遞推的式子, 意味著利用它，我們可以使用上一個迭代周期內的狀態(tài)價值來計算更新當前迭代周期某狀態(tài)s的狀態(tài)價值。可見，使用動態(tài)規(guī)劃來求解強化學習問題是比較自然的。

策略評估求解預測問題

首先，我們來看如何使用動態(tài)規(guī)劃來求解強化學習的預測問題，即求解給定策略的狀態(tài)價值函數的問題。這個問題的求解過程我們通常叫做策略評估(Policy Evaluation)。

策略評估的基本思路是從任意一個狀態(tài)價值函數開始，依據給定的策略，結合貝爾曼期望方程、狀態(tài)轉移概率和獎勵同步迭代更新狀態(tài)價值函數，直至其收斂，得到該策略下最終的狀態(tài)價值函數。

假設我們在第K輪迭代已經計算出了所有的狀態(tài)的狀態(tài)價值，那么在第K+1輪我們可以利用第K輪計算出的狀態(tài)價值計算出K+1輪的狀態(tài)價值。這是通過貝爾曼方程來完成的，即：

和上一節(jié)的式子唯一的區(qū)別是由于我們的策略π已經給定，我們不再寫出，對應加上了迭代輪數的下標。我們每一輪可以對計算得到的新的狀態(tài)價值函數再次進行迭代，直至狀態(tài)價值的值改變很小(收斂)，那么我們就得出了預測問題的解，即給定策略的狀態(tài)價值函數

下面我們用一個具體的例子來說明策略評估的過程。

策略評估求解實例

這是一個經典的Grid World的例子。我們有一個4x4的16宮格。只有左上和右下的格子是終止格子。該位置的價值固定為0，個體如果到達了該2個格子，則停止移動，此后每輪獎勵都是0。個體在16宮格其他格的每次移動，得到的即時獎勵R都是-1。注意個體每次只能移動一個格子，且只能上下左右4種移動選擇，不能斜著走, 如果在邊界格往外走，則會直接移動回到之前的邊界格。衰減因子我們定義為r=1。由于這里每次移動，下一格都是固定的，因此所有可行的的狀態(tài)轉化概率P=1。這里給定的策略是隨機策略，即每個格子里有25%的概率向周圍的4個格子移動。

首先我們初始化所有格子的狀態(tài)價值為0，如上圖k=0的時候。現在我們開始策略迭代了。由于終止格子的價值固定為0，我們可以不將其加入迭代過程。在k=1的時候，我們利用上面的貝爾曼方程先計算第二行第一個格子的價值：

第二行第二個格子的價值是：

其他的格子都是類似的，第一輪的狀態(tài)價值迭代的結果如上圖k=1的時候。現在我們第一輪迭代完了。開始動態(tài)規(guī)劃迭代第二輪了。還是看第二行第一個格子的價值：

第二行第二個格子的價值是：

最終得到的結果是上圖k=2的時候。第三輪的迭代如下：

最終得到的結果是上圖k=3的時候。就這樣一直迭代下去，直到每個格子的策略價值改變很小為止。這時我們就得到了所有格子的基于隨機策略的狀態(tài)價值。

可以看到，動態(tài)規(guī)劃的策略評估計算過程并不復雜，但是如果我們的問題是一個非常復雜的模型的話，這個計算量還是非常大的。

策略迭代求解控制問題

上面我們講了使用策略評估求解預測問題，現在我們再來看如何使用動態(tài)規(guī)劃求解強化學習的第二個問題控制問題。一種可行的方法就是根據我們之前基于任意一個給定策略評估得到的狀態(tài)價值來及時調整我們的動作策略，這個方法我們叫做策略迭代(Policy Iteration)。

如何調整呢？最簡單的方法就是貪婪法。考慮一種如下的貪婪策略：個體在某個狀態(tài)下選擇的行為是其能夠到達后續(xù)所有可能的狀態(tài)中狀態(tài)價值最大的那個狀態(tài)。還是以第三節(jié)的例子為例，如上面的圖右邊。當我們計算出最終的狀態(tài)價值后，我們發(fā)現，第二行第一個格子周圍的價值分別是0,-18,-20，此時我們用貪婪法，則我們調整行動策略為向狀態(tài)價值為0的方向移動，而不是隨機移動。也就是圖中箭頭向上。而此時第二行第二個格子周圍的價值分別是-14,-14,-20, -20。那么我們整行動策略為向狀態(tài)價值為-14的方向移動，也就是圖中的向左向上。

如果用一幅圖來表示策略迭代的過程的話，如下圖：

在策略迭代過程中，我們循環(huán)進行兩部分工作，第一步是使用當前策略π*評估計算當前策略的最終狀態(tài)價值v*，第二步是根據狀態(tài)價值v*根據一定的方法（比如貪婪法）更新策略π*，接著回到第一步，一直迭代下去，最終得到收斂的策略π*和狀態(tài)價值v*。

價值迭代求解控制問題

觀察第三節(jié)的圖發(fā)現，我們如果用貪婪法調整動作策略，那么當k=3的時候，我們就已經得到了最優(yōu)的動作策略。而不用一直迭代到狀態(tài)價值收斂才去調整策略。那么此時我們的策略迭代優(yōu)化為價值迭代。

還是以第三節(jié)的例子為例，如上面的圖右邊。比如當k=2的時候，第二行第一個格子周圍的價值分別是0,-2,-2，此時我們用貪婪法，則我們調整行動策略為向狀態(tài)價值為0的方向移動，而不是隨機移動。也就是圖中箭頭向上。而此時第二行第二個格子周圍的價值分別是-1.7,-1.7,-2, -2。那么我們整行動策略為向狀態(tài)價值為-1.7的方向移動，也就是圖中的向左向上。

和上一節(jié)相比，我們沒有等到狀態(tài)價值收斂才調整策略，而是隨著狀態(tài)價值的迭代及時調整策略, 這樣可以大大減少迭代次數。此時我們的狀態(tài)價值的更新方法也和策略迭代不同。現在的貝爾曼方程迭代式子如下：

可見由于策略調整，我們現在價值每次更新傾向于貪婪法選擇的最優(yōu)策略對應的后續(xù)狀態(tài)價值，這樣收斂更快。

異步動態(tài)規(guī)劃算法

在前幾節(jié)我們講的都是同步動態(tài)規(guī)劃算法，即每輪迭代我會計算出所有的狀態(tài)價值并保存起來，在下一輪中，我們使用這些保存起來的狀態(tài)價值來計算新一輪的狀態(tài)價值。

另一種動態(tài)規(guī)劃求解是異步動態(tài)規(guī)劃算法，在這些算法里，每一次迭代并不對所有狀態(tài)的價值進行更新，而是依據一定的原則有選擇性的更新部分狀態(tài)的價值，這類算法有自己的一些獨特優(yōu)勢，當然有額會有一些額外的代價。

常見的異步動態(tài)規(guī)劃算法有三種：

1. 第一種是原位動態(tài)規(guī)劃 (in-place dynamic programming)， 此時我們不會另外保存一份上一輪計算出的狀態(tài)價值。而是即時計算即時更新。這樣可以減少保存的狀態(tài)價值的數量，節(jié)約內存。代價是收斂速度可能稍慢。

2. 第二種是優(yōu)先級動態(tài)規(guī)劃 (prioritised sweeping)：該算法對每一個狀態(tài)進行優(yōu)先級分級，優(yōu)先級越高的狀態(tài)其狀態(tài)價值優(yōu)先得到更新。通常使用貝爾曼誤差來評估狀態(tài)的優(yōu)先級，貝爾曼誤差即新狀態(tài)價值與前次計算得到的狀態(tài)價值差的絕對值。這樣可以加快收斂速度，代價是需要維護一個優(yōu)先級隊列。

3. 第三種是實時動態(tài)規(guī)劃 (real-time dynamic programming)：實時動態(tài)規(guī)劃直接使用個體與環(huán)境交互產生的實際經歷來更新狀態(tài)價值，對于那些個體實際經歷過的狀態(tài)進行價值更新。這樣個體經常訪問過的狀態(tài)將得到較高頻次的價值更新，而與個體關系不密切、個體較少訪問到的狀態(tài)其價值得到更新的機會就較少。收斂速度可能稍慢。

動態(tài)規(guī)劃求解強化學習問題小結

 

END