強化學習經典入門書的讀書筆記系列--第七篇（下）

原文鏈接：強化學習經典入門書的讀書筆記系列--第七篇（下）

本書資料下載：http://pan.baidu.com/s/1hrFcDG4

本書的演算法代碼也在更新：lvlvlvlvlv/A-introduction-to-reinforcement-learning

歡迎關注我們的微信公眾號：神經網路與強化學習 或 加微信進入討論群：lllmya

文章原創，禁止轉載。

歡迎大家提出寶貴意見，多多交流~

------------------------------------------------------------------------------------------------------------------------

文章目錄

• 7.5 Sarsa(λ)演算法---Sarsa演算法的資格跡版本
• 7.6 Q(λ)演算法---Q-learning演算法的資格跡版本
• 7.7 替代型資格跡---資格跡不止一種喲
• 7.8 資格跡代碼實現的一些問題
• 7.9 變數λ---常量λ進化到變數λ
• 7.10 本章小結

7.5 Sarsa(λ)

前面幾節一直都在說prediction問題，那麼資格跡思想能不能用在control問題里呢？當然可以。解決方法和以前一樣，我們不再讓執行機構學習 ,而是去學習 。新方法的提出，大多都是把新的idea和傳統的成熟方法結合起來得到。這一節，我們就把資格跡思想和上一章講的Sarsa演算法結合，得到一種新的on-policy TD control method----Sarsa(λ) 。

首要的一點，資格跡不再是 ,而應該變成,即每一對state-action都有一個資格跡。其他的部分和TD(λ)一模一樣，只是把都換成,都換成,即可。的更新公式如下：

其中，

的更新公式如下：對於所有的s,a:

Sarsa(λ)的反向轉移圖如下：

這個圖和前文中TD(λ)的反向轉移圖非常像。注意這個圖其實是從前向視角看到的結果，而上述更新公式所描述的其實是後向視角的實現方式。這部分在前文中關於TD(λ)的前向、後向視角的討論是一致的。

Sarsa(λ)是on-policy演算法，也就是在的近似過程和policy的更新過程中，參與的policy一直是同一個。對於on-policy演算法，policy的更新方式有很多，最簡單的就是依據當前的action-value 估計值，採用 policy。

Sarsa(λ)偽代碼如下：

7.6 Q(λ)

當我們把資格跡和Sarsa演算法結合之後，自然會想到是否資格跡也能和Q-learning演算法結合。答案顯而易見，就是Q(λ)。

這裡我們介紹三種Q(λ)演算法：

• Watkins』s Q(λ)
• Peng』s Q(λ)
• naive Q(λ)

（1）在討論Watkins』s Q(λ)演算法之前，先回憶一下常規的Q-learning演算法。Q-learning屬於off-policy演算法，也就是說學到的policy（target policy）和用於選擇動作的policy（behavior

policy）可以不一樣。具體來說就是，behavior policy偶爾會引入non-greedy action，而Q-learning需要依據帶有non-greedy action的episode來學到最優policy。這時引入資格跡需要特別注意。

Watkins』s Q(λ)演算法的特點很顯著：假如我們有一個episode，第一個timestep的action是greedy的，第二個timestep的action也是greedy的，第三個timestep的action是non-greedy的，那麼Watkins』s Q(λ)使用的有效序列長度，最長就到第二個timestep，從第三個timestep往後的序列都不再理會。也就是說，Watkins』s Q(λ)使用的有效序列長度最遠到達第一個non-greedy action對應的timestep。

如何確定當前timestep選擇的action是否是greedy呢？很簡單，把當前選擇的action和當前的對比，如果一致就是greedy，不一致就是non-greedy。

Watkins』sQ(λ)演算法的資格跡如何更新呢？分兩部分：首先，所有(s,a)的資格跡要麼乘以decay係數γλ（當選擇的action是greedy的），要麼變成0（當選擇的action是non-greedy的）；其次，對於當前正在訪問的(s,a)，其資格跡單獨+1。

和上一節的Sarsa(λ) 演算法一樣，我們給出相關的更新公式。

資格跡的更新公式如下：

的更新方式如下:

其中：

Watkins』s Q(λ)演算法的偽代碼如下：

Watkins』s Q(λ)演算法有個很大的缺點：每次只考慮一段序列中non-greedy action之前的部分，這樣會浪費大量後面的序列信息。如果有很多non-greedy action發生在序列的早期，那麼每段序列的有效信息就只有一兩個timestep。

於是我們需要Peng』s Q(λ)演算法來解決上述問題。

（2）Peng』s Q(λ)演算法可以看作既有on-policy部分又有off-policy部分的混合型Q(λ)演算法。我們通過看它的反向轉移圖來分析一下其特點。

上圖也可以看做是Peng』s Q(λ)演算法的前向視角。可以看到，在每個backup過程中（除了最長的完整episode），前面的狀態轉移過程都是依據某個隨機的non-greedy policy，屬於actual experience；最後一個action 的選擇，則是依據greedy policy，即根據來選擇最優action。這麼看的話，每個backup過程都是既有on-policy成分（前面部分Q的更新基於當前的policy），又有off-policy成分（最終的action選擇基於greedy policy）。

下面我們給出Pengs Q(λ)的偽代碼，通過偽代碼也可以看出上述特點，並且也能知道為什麼Pengs Q(λ)可以解決Watkins』s Q(λ)存在的trace cut問題。

注意偽代碼中的表示，這裡的x就是我們之前說的狀態s。

偽代碼中，D、E兩行分別按照on-policy和off-policy方式求得了temporal error，然後通過F、G兩行分別更新 「非當前(s,a)的Q值」、「當前(s,a)的Q值」，而資格跡Tr的更新方式不再出現歸零的情況。

然而Pengs Q(λ)演算法也有其缺點：（1）代碼實現起來不容易（2）在理論上不能保證收斂到最優Q(s,a)。但是，如果我們將non-greedy policy逐漸變成近似greedy，那麼最後也許可以保證收斂到（未被證明）。

從實際效果來看，Pengs Q(λ)演算法明顯要比Watkins』s Q(λ)效果好，和Sarsa(λ)演算法的效果近乎相同。

（3）Pengs Q(λ)演算法實現起來很麻煩，於是我們可以基於Watkins』s Q(λ)演算法構造一個naive Q(λ)演算法。naive Q(λ)和Watkins』s Q(λ)幾乎相同，只是在遇到non-greedy action的時候，資格跡不歸零，而是歸於某個常數或函數。這樣也許可以既獲得部分Pengs Q(λ)的優點，又易於實現。

7.7 Replacing Traces

有些強化學習任務，可以通過改變資格跡的類型來獲得更好的效果。前面我們定義的資格跡都是「累計型」資格跡（accumulating traces），這一節我們會介紹另一種「替代型」資格跡（replacing traces）。這種新的資格跡在某些任務中的效果要優於「累計型」資格跡。

replacing traces定義如下：

下圖更直觀地表示了兩種類型資格跡的區別：

注意到：當某個狀態被頻繁訪問的時候，它的「累計型」資格跡會不斷爬升，數值上也不斷增加；而它的「替換型」資格跡則會一直保持在 1 不變。這種差別在什麼情況下會有優劣之分呢？我們考慮一個例子。

假如我們有個任務的狀態轉移圖如下：

在每個狀態下只有兩種動作可選：選擇wrong就保持在某狀態不變，選擇right就前進一步，到下一個狀態。我們規定無論選擇任何動作其reward都是0，除了最後一步reward是1（圖上已標明）。於是這個任務的目的是如何讓agent通過最少的步數由起點走到終點。

如果使用「累積型」資格跡，考慮這樣一種情況：在第一個episode中，agent在選擇right action之前先選擇了若干次wrong action。在這種情況下，Z(s,wrong)很可能比Z(s,right)大。當最終獲得reward之後，wrong action的Q值很可能比right action的Q值大。這樣的話，在下一個episode中，agent會傾向於在right action之前選擇更多次wrong action，於是就會導致Z(s,wrong)更大，以此類推。

當然，最終結果仍然可以收斂，但是agent的學習過程會因此被大幅延長。其原因就在於使用「累積型」資格跡，無法控制那些不理想action的資格跡增長。如果使用這一節說的「替代型」資格跡，無論wrong action在right action之前被選擇了多少次，都不會使其資格跡不斷累積變大，一旦right action被選中，則Z(s,right) > Z(s,wrong)。上一段所說的情形也就不會出現，agent的學習過程會依舊高效。

「替代型」資格跡還有一些變體，比如下面這種：

將這個「替代型」資格跡的變體應用於上面所說的例子，其效果甚至比原始「替代型」資格跡的效果還要好。因為一旦right action被選中，那麼wrong action的資格跡就立刻變成0，這樣可以最大限度消除Z(s,wrong)的影響。

7.8 Implementation Issues

這一節簡單討論一下具體實現過程中的tricks。之所以要說一下trick，是因為：當把原始TD(0)演算法用上資格跡之後，會帶來內存和運算時間的大量消耗---每一個timestep都必須更新當前state-action pair的value estimate和eligibilitytrace。

但事實證明，對於常用的和 ，只有那些最近被訪問過的state-action pair，它們的資格跡才顯著大於0；至於絕大多數state-action pair，其資格跡都幾乎為0。因此這裡的trick就是：始終保存最近訪問過的states or state action pair，更新的時候只更新它們的資格跡，而忽略大多數的states。這樣可以大幅提高運算效率。

最後還要提一句，到目前為止我們對於Q值和資格跡的存儲形式基本都採用的是tabular（表格形式），就是一個蘿蔔一個坑，每個state對應自己的value或者eligibility trace。這種形式的實現方式是最不利於使用資格跡的，因為運算開銷相對較大。當我們在第九章討論function approximation時，比如使用神經網路和反向傳播的方式，那麼資格跡僅僅會帶來多一倍的內存和時間消耗。

7.9 Variable λ

這一節我們把λ改造一下。之前的λ是常數，現在λ是隨時間t變化的函數。於是資格跡的定義如下：

雖然這種 函數很少在實際中應用，但在理論上似乎是行得通的。

比如我們可以把 定義為。在這種定義下，如果我們對某個狀態的估計值十分確信，那麼很顯然最好是充分使用這個估計值，而忽略之後的states和reward，因此就可以把這個狀態對應的λ設置的接近於0（極小）。

反過來說，如果我們對某個狀態的估計值很沒有把握，那麼最好把這個狀態的設置為1---這樣的話，該估計值對其他狀態的更新都不會有太大影響，相當於把當前這個不可信的狀態給跳過了。

如果對上面這部分不理解，可以回看一下下圖：當 = 0時，除了one-step reward的權重為1，其他的multi-step reward的權重都為0，即對狀態的某個估計值十分確信，最好是充分使用估計值，而忽略之後的states和reward；當 = 1時，該狀態的估計值所佔的權重為0，這樣當其他狀態採用λ-return方式更新Q時，就會跳過這個不可信的狀態估計值。

7.10 Conclusion

資格跡方法和傳統TD演算法的結合--TD(λ),使得傳統TD演算法也具備了蒙特卡洛演算法的一些優點：可以處理帶有非馬爾科夫性質的任務；同時避免了蒙特卡洛演算法的缺點：長延遲reward帶來的嚴重variation。可以這麼說：資格跡方法是應對「非馬爾科夫性任務」和「長延遲reward」問題的首要防線。

雖然資格跡方法的運用帶來一定量的計算負擔，但是它的確極大程度地提高了訓練速度，尤其是當reward的延遲性很高的時候。因此我們也能總結出來一個結論：對於數據比較稀疏或者不能重複處理的時候，用資格跡配合傳統TD是必要的；然而，對於數據量足夠的任務，優先需要考慮解決的問題則應該是如何儘可能快速地處理數據，這種情況下TD(0)演算法才是更合適的選擇。

（本章完）

推薦閱讀：