強化學習筆記7—多步自舉

05-09

本章將統一前面兩章展示的方法。無論MC或單步TD方法不可能總是最好，多步TD方法擴展了兩者，因此可以平滑地從一個到另一個轉換。它們張成了一個MC方法在一端單步TD另一端的光譜，通常中間的方法比兩端表現更優。多步TD的另一好處是它解放了時間步的嚴苛，使用單步方法同一步內確定行動改變的頻率和自舉完成的時間間隔。許多應用希望能快速更新以考慮所有的改變，但自舉在狀態發生顯著或可辨改變的時間長度才發揮最好。多步方法能使自舉在較長時間間隔發生。多步方法通常與合格追蹤(eligibility trace)有關。如往常一樣，先考慮預測問題然後是控制問題，即先考慮多步方法如何在幫助預測固定策略作為狀態函數的回報，然後擴展到行動價值和控制方法。

7.1 ??-步TD預測

在MC和TD之間的方法空間是什麼呢？考慮從 $pi$ 生成的樣本小節中評估 $v_pi$ ，MC方法為每個狀態基於此狀態到節末觀測到激勵的整個序列執行更新；而單步TD方法的更新則僅基於下一個激勵，引導(bootstrapping)下一步狀態的價值作為剩餘激勵的代表(proxy)。一種中間方法就是基於中間個數的激勵更新。圖7.1描繪出了 $v_pi$ 的 $n$ -步更新譜：

使用 $n$ -步備份的方法依然是TD方法，因為它依然是根據與後面估計的差異來改變前面的估計。這種將時間差分擴展到 $n$ 步的方法稱為 $n$ -步TD方法。更正式地，將應用到狀態 $S_t$ 更新視為狀態-激勵序列 $S_t,R_{t+1},S_{t+1},dots,R_T, S_T$ 的結果。MC方法中 $v_pi(S_t)$ 的估計在所有回報的方向上更新： $G_t dot= R_{t+1} + gamma R_{t+2} + gamma^2R_{t+3} + cdots + gamma^{T-t-1}R_T$ 。 $T$ 是節的最後一步。稱這個量為更新目標(the target of the backup)。一步更新的目標稱為一步回報(one-step return)： $G_{t:t+1} dot=R_{t+1} + gamma V_t(S_{t+1})$ 。 $G_{t:t+1}$ 的下標表示這是使用時間 $t$ 到 $t+1$ 的截斷回報。在兩步之後這樣做也有同樣的含義，兩步備份的目標就是兩步回報： $G_{t:t+2} dot= R_{t+1} + gamma R_{t+2} + gamma^2V_{t+1}(S_{t+2})$ 。同樣，任意 $n$ 步備份的目標就是 $n$ -步回報，定義為對滿足 $n ge 1$ 並且 $0 le t le T-n$ 所有的 $n,t$ ：

$G_{t:t+n} dot= R_{t+1} + gamma R_{t+2} + cdots + gamma^{n-1}R_{t+n} + gamma^nV_{t+n-1}(S_{t+n}) ag{7.1}$

所有的 $n$ 步回報可以認為是全回報的近似，在 $n$ 步後被截斷然後用 $V_{t+n-1}(S_{t+n})$ 修正剩餘項。若 $t+n ge T$ （即 $n$ 步回報到達或超出終止點），則 $n$ -步回報就是普通的全回報( $G_{t:t+n} dot= G_t$ 若 $t+nge T$ )。注意 $n$ -步回報涉及從 $t$ 到 $t+1$ 轉移時還不可得的未來激勵和狀態，能得到的最早時間是 $t+n$ ，因此使用 $n$ -步回報的狀態-價值學習演算法就是：

$V_{t+n}(S_t) dot= V_{t+n-1}(S_t) + alphaBig[ G_{t:t+n} - V_{t+n-1}(S_t) Big] ag{7.2}$

而所有其他狀態價值保持不變時， $V_{t+n}(s) = V_{t+n-1}(s),forall s eq S_t$ 。稱這個演算法為 $n$ 步TD( $n$ -step TD)。注意在每節前 $n-1$ 步沒有做任何變化，作為彌補等量更新會在節末，即終止後和下一節開始前完成。完整的偽代碼如下：

$n$ -步回報使用價值函數 $V_{t+n-1}$ 來修正 $R_{t+n}$ 後失去的激勵，它們的一個重要特性是在最壞-狀態情況下，它們的期望保證是比 $V_{t+n-1}$ 更優的估計。也即對所有 $n ge 1$ ，期待 $n$ -步回報最糟的誤差保證小於或等於 $V_{t+n-1}$ 下最壞誤差的 $gamma^n$ 倍：

$max_a Big| mathbb E_pi[G_{t:t+n}mid S_t=s] - v_pi(s) Big| le gamma^nmax_sBig| V_{t+n-1}(s) - v_pi(s) Big| ag{7.3}$

這被稱為 $n$ -步回報的誤差減小特性(error reduction property)，用這個特性就能展現在一些合適的技術條件下，所有 $n$ -步TD方法收斂到正確的預測。因此 $n$ -步TD方法就形成了一個可行方法族，其中一步TD和MC是兩端成員。

示例7.1 隨機遊走的 $n$ 步TD方法：考慮將 $n$ -步TD方法應用在示例6.2描述的隨機遊走任務上。假設第一個節從中心 $mathtt C$ 開始直接向右經 $mathtt{D,E}$ 到達右邊終止點，獲得1的回報。所有狀態的估計價值以中間值 $V(s)=0.5$ 開始，作為這個經驗的結果，單步方法會改變最後的狀態估計 $V(mathtt E)$ 為1；兩步方法會增加終結前兩個狀態 $V(mathtt D)$ 和 $V(mathtt E)$ 都為1；三步或任意 $n > 2$ 的n-步方法都會將三個訪問過的狀態的價值都增加到1。

那麼怎樣的 $n$ 值更好。圖7.2展示了在一個更大的19個狀態的隨機遊走任務上（左邊結果為-1，其餘0，本章作為運行示例）一個簡單經驗測試結果。每個參數設定的衡量是節末19個狀態的預測和它們真實價值間方根平方差，然後在整個試驗前10節和100次重複上求均值。注意n值在中間的方法表現最好。這展示了TD和MC方法擴展到的 $n$ -步方法是怎樣能潛在比兩個端點方法表現得更好的。

7.2 $n$ -步Sarsa

$n$ -步方法怎樣用於控制呢？本節以直接的方式結合 $n$ -步方法和Sarsa產生一個on-policy控制方法，稱為 $n$ -步Sarsa，上一章描述的初始版本此後稱為單步Sarsa或Srasa(0)。主要思想是先將狀態轉換為行動（狀態-行動對），再使用一個 $varepsilon$ -貪心演算法。 $n$ -步Sarsa的備份圖（圖7.3）與 $n$ -步TD（圖7.1）的十分相似，除了Sarsa都是以行動開始和結束。

定義估計行動價值的 $n$ -步回報：

$G_{t:t+n}dot=R_{t+1} + gamma R_{t+2} + cdots+gamma^{n-1}R_{t+n} + gamma^nQ_{t+n-1}(S_{t+n}, A_{t+n}), qquad nge 1, 0le t<T-n ag{7.4}$

若 $t+nge T$ ，則 $G_{t:t+n} dot= G_t$ 。因此自然的演算法就是：

$Q_{t+n}(S_t,A_t)dot=Q_{t+n-1}(S_t,A_t) + alphaBig[ G_{t:t+n} - Q_{t+n-1}(S_t,A_t) Big],qquad 0le t<T ag{7.5}$

而其他狀態的價值保持不變， $Q_{t+n}(s,a) = Q_{t+n-1}(s,a)$ ，對所有滿足 $s eq S_t$ 或 $a eq A_t$ 的 $s,a$ 。這就是被稱為 $n$ -步Sarsa的演算法。完整偽代碼如下：

而解釋相比單步方法它能加速學習的原因的示例在圖7.4給出：

關於期望Sarsa的 $n$ -步版本的備份圖在圖7.3的最右側；與 $n$ -步Sarsa的非常相似，除了最後一個元素的是一束策略 $pi$ 下由自身概率加權的所有行動。演算法能用像 $n$ -步Sarsa一樣的方程描述，除了 $n$ -步回報定義為：

$G_{t:t+n}dot=R_{t+1} + gamma R_{t+2} + cdots+gamma^{n-1}R_{t+n} + gamma^nsum_api(amid S_{t+n})Q_{t+n-1}(S_{t+n}, a) ag{7.6}$

對所有滿足 $n ge 1$ 和 $0 le t le T-n$ 的 $n$ 和 $t$ 。

7.3 基於重要性採樣的??-步off-policy學習

Off-policy學習就是通過遵循行為策略 $b$ 學習策略 $pi$ 的價值函數。通常 $pi$ 是當前行動-價值函數的貪心策略， $b$ 則更具探索性，可以是 $varepsilon$ -貪心。要使用 $b$ 的數據必須考慮兩個策略的差異，使用被採取行動它們採取的相對概率。在 $n$ 步方法中，回報在 $n$ 步上構建。比如，要構造簡單的 $n$ 步TD版本，時間 $t$ 的更新（實際在時間 $t+n$ 做）可以簡單地由 $ho_{t:t+n-1}$ 權衡：

$V_{t+n}(S_t) dot= V_{t+n-1}(S_t) + alpha ho_{t:t+n-1}[G_{t:t+n} - V_{t+n-1}(S_t)],qquad0le t <T ag{7.7}$

其中 $ho_{t:t+n-1}$ ，被稱為重要性採樣率，是兩個策略下採取從 $A_t$ 到 $A_{t+n-1}$ 的 $n$ 個行動的相對概率：

$ho_{t:h} = prod_{k=t}^{min(h,T-1)} frac{pi(A_kmid S_k)}{b(A_kmid S_k)} ag{7.8}$

若有行動在 $pi$ 中採用的概率遠大於 $b$ ，這會增大隨後給定回報的權重。它是 $pi$ 的典型因此合乎情理，但卻很少被 $pi$ 選擇因此很少出現在數據中，作為彌補在出現時必須給它過大權重。若事實上兩個策略相同（則變為on-policy）則重要性採樣率總是1。因此新的更新(7.7)可以推廣並完全取代先前的 $n$ 步TD更新。同樣，先前的 $n$ -步Sarsa更新也可以被一個簡單的off-policy形式，即對 $0 le t le T$ ：

$Q_{t+n}(S_t,A_t) dot= Q_{t+n-1}(S_t, A_t) + alpha ho_{t+1:t+_n-1}[G_{t:t+n} - Q_{t+n-1}(S_t, A_t)], ag{7.9}$

注意這裡重要性採樣的開始比 $n$ -步Sarsa晚一步。這是因為這裡更新的是狀態-行動對。不必關注會選擇行為的概率，既然已經選擇了它就要完全用隨後行為的重要性採樣從所發生的學習。完整演算法的偽代碼如下：

$n$ -步期望Sarsa的off-policy版本使用Sarsa像上面一樣的更新規則，除了重要性採樣率少一個因子。也即上面等式會用 $ho_{t+1:t+n-2}$ 來代替 $ho_{t+1:t+n-1}$ ，並且也會用期望Sarsa版的 $n$ -步回報(7.6)。因為在期望Sarsa中，所有可能的行動都會在最後一個狀態考慮，實際採取的沒有影響，也不必修正。

7.4 *每激勵off-policy方法

前一節展示的多步off-policy方法確實非常簡潔清晰，但可能不是效率最高的。一種更精巧的方法是使用像5.9節介紹的每一激勵(per-reward)重要性採樣的思想。先注意常規多步回報(7.1)，像所有回報一樣可以寫為遞歸形式： $G_{t:h} = R_{t+1} + gamma G_{t+1:h}$ 。所有結果的經驗，包括第一個激勵 $R_{t+1}$ 和下個狀態 $S_{t+1}$ 必須用時間 $t$ 的重要性採樣率 $ho_t=frac{pi(A_tmid S_t)}{b(A_tmid S_t)}$ 加權。假定時間 $t$ 的行動永遠不會被 $pi$ 選中，則 $ho_t=0$ ，則簡單加權會導致 $n$ -步回報也為0，這用作目標策略時會導致高方差。因此使用一個替代 $n$ -步回報的off-policy定義為：

$G_{t:h} dot= ho_t(R_{t+1}+gamma G_{t+1:h}) + (1- ho_t)V(S_t),qquad t<hle T ag{7.10}$

其中 $V(S_t)$ 是 $S_{t+1}$ 價值的某個估計，並且 $G_{t:t} dot= V(S_t)$ （對精確用於 $V(S_t)$ 的時間步估計是有點模糊的，因為選擇依賴於特定演算法的概率）。現若 $ho=0$ ，目標與估計一樣不發生變化。重要性採樣率為0表示要忽視這個樣本，因此使得估計不變似乎是適當的結果。注意第二個額外的項並不改變期待更新，第二項的期望期望0。同樣注意off-policy定義(7.10)是先前 $n$ -步回報的on-policy定義(7.1)的嚴格推廣，因這兩個在on-policy情形上是等價的。

對一個傳統 $n$ -步方法，與(7.10)結合使用的學習規則是 $n$ -步TD更新(7.2)，除了嵌入在 $G$ 中，沒有明確的重要性採樣率。這種情況下，近似價值函數在時間索引上有 $h-1=t+n-1$ 。

對行動價值， $n$ -步回報的定義對應於期望Sarsa，有一點不同是因為第一個行動在重要性採樣中不發揮作用。我們學習這個行動的價值並且在目標策略下不可能發生也沒關係。它已被採用，現在滿單元的權重必須給到激勵和跟隨它的狀態。重要性採樣僅會應用到它後面的行動。行動價值 $n$ -步回報的遞歸定義為，對滿足 $t < h le T$ 的 $t,h$ ：

$G_{t:h} dot= R_{t+1} + gamma( ho_{t+1}G_{t+1:h} + (1- ho_{t-1})ar Q_{t+1}) ag{7.11}$

其中 $G_{t:t} dot= ar Q_t dot= sum_a pi(amid S_t)Q_{t-1}(S_t, a)$ 。完整的 $n$ -步off-policy行為-價值函數預測方法可以使用時間 $h-1=t+n-1$ 的估計來結合(7.11)和(7.5)。

重要性採樣使得off-policy學習得以實現，但增加了更新的方差。高方差迫使使用小步長參數，導致學習很慢。off-policy的訓練慢於on-policy的訓練很可能是無法避免的，畢竟數據與正在嘗試學習的更不相關。但是也有一些方法改善，一種可能是快速調整步長到觀測到的方差，就像Autostep方法；另一個很有前途的方法是不變更新。

7.5 無重要性採樣的off-policy學習：??-步樹備份演算法

本節介紹一個不使用重要性採樣的學習方法。第6章的Q-學習和期望Sarsa是一步情形，本節展示 $n$ -步的方法，稱為樹備份演算法(tree-backup algorithm)。演算法的思想如下圖所顯示，中心線向下在圖上標出的是三個樣本狀態和激勵，以及兩個樣本行動，表示初始狀態-行動對 $S_t, A_t$ 後發生事件的隨機變數。每個狀態的兩側是未選擇的行動（認為最後一個狀態的所有行動都還未被選擇）。因為沒有未選中行動樣本數據，引導並使用它們值的估計來形成更新的目標。這略微擴展了備份圖的思想。目前為止我們總是結合沿途的激勵（適當折扣）和底部節點的估計價值向一個目標更新並評估圖表頂部節點的價值。在樹備份中，目標包含所有這些加上所有層次懸在側邊搖擺行動節點價值的估計。

更精確地說，這個備份從樹葉子節點估計的行動價值開始，對應採取行為的內部的行動節點則不參與。每個葉子節點用於以正比於目標策略 $pi$ 下發生概率的權值促成目標。因此第一層的一個行動 $a$ 以權值 $pi(amid S_{t+1})$ 貢獻，除實際採取的行為 $A_{t+1}$ 未做任何貢獻，它的概率 $pi(A_{t+1} mid S_{t+1})$ 用於加權第二層的行動。因此每個未選中第二層行動 $a$ 以權值 $pi(A_{t+1}mid S_{t+1})pi(a mid S_{t+2})$ 貢獻，每個第三層行動貢獻的權值是 $pi(A_{t+1} mid S_{t+1}) pi(A_{t+2} mid S_{t+2}) pi(a mid S_{t+3})$ ，等等。就好像圖中到行動的每個箭頭都由此行動在目標策略下被選中的概率加權，而權值不僅適用於此行動，還有它下面的整棵樹。

可以將樹備份是為樣本轉移（從每個行動到隨後狀態）和全備份（從每個狀態考慮所有可能的行動和它們發生的概率）的交替序列。樣本轉移也有多種發生的概率，但因為它們已經給定行為選擇因此獨立於策略，所以無需考慮這些；它們會引入方差而非偏差。

樹備份演算法的單步回報（目標）與期望Sarsa的相同，可以寫為：

$egin{aligned} G_{t:t+1} &dot= R_{t+1} + gammasum_api(amid S_{t+1})Q_t(S_{t+1}, a)\ &= delta_t + Q_{t-1}(S_t,A_t) end{aligned}$

其中 $delta_t$ 是期望Sarsa中TD誤差的修改形式：

$delta_t dot= R_{t+1} + gammasum_api(amid S_{t+1})Q_t(S_{t+1},a) - Q_{t-1}(S_t,A_t) ag{7.12}$

由這些，樹備份演算法的一般 $n$ -步回報可以定義為遞歸形式，然後就像TD誤差之和：

$egin{eqnarray*} G_{t:t+n} &dot=& R_{t+1} + gammasum_{a eq A_{t+1}} pi(amid S_{t+1})Q_t(S_{t+1},a) + gammapi(A_{t+1}mid S_{t+1})G_{t+1:t+n} ag{7.13}\ &=& delta_t + Q_{t-1}(S_t,A_t) - gammapi(A_{t+1}mid S_{t+1})Q_t(S_{t+1},A_{t+1}) + gammapi(A_{t+1}mid S_{t+1})G_{t+1:t+n}\ &=& Q_{t-1}(S_t,A_t) + delta_t + gammapi(A_{t+1}mid S_{t+1})left( G_{t+1:t+n} - Q_t(S_{t+1},A_{t+1}) ight)\ &=& Q_{t-1}(S_t,A_t) + delta_t + gammapi(A_{t+1}mid S_{t+1})delta_{t=1} + gamma^2pi(A_{t+1}mid S_{t+1})pi(A_{t+2}mid S_{t+2})delta_{t+2}+ cdots\ &=& Q_{t-1}(S_t,A_t) + sum_{k=t}^{min(t+n-1, T-1)} delta_k prod_{i=t+1}^k gammapi(A_imid S_i) end{eqnarray*}$

慣例下0個元素的累積為1。此目標然後與 $n$ -步Sarsa的行動-價值更新規則一起使用：

$Q_{t+n}(S_t, A_t) dot= Q_{t+n-1}(S_t, A_t) + alpha[G_{t:t+n} - Q_{t+n-1}(S_t,A_t)] ag{7.5}$

而所有其他狀態-行動的價值保持不變，對 $forall s,a$ 滿足 $s eq S_t$ 或 $a eq A_t$ ，有 $Q_{t+n}(s,a)=Q_{t+n-1}(s,a)$ 。演算法的偽代碼如下：

7.6 *統一演算法： $n$ -步 $Q(sigma)$

目前本章已經介紹了三種不同的行動-價值備份，分別對應於圖7.5展示的前3個備份圖。 $n$ -步Sarsa有所有採樣的轉移；樹備份演算法有所有狀態到行動全部分支而非採樣的轉移；而??-步期望備份有所有採樣轉移，除最後的狀態到行動轉移是在所有分支上的期望值。將它們統一起來的一個思修是圖7.5的第4個備份圖，就是在逐步基礎上決定是否要像Sarsa中那樣採取行動為樣本，或者考慮用樹備份中那樣的所有行動上的期望來替代。然後，如果選擇總是採樣，就獲得了Sarsa；而若選擇絕不採樣，則獲得了樹備份演算法。期望Sarsa就是除最後一個外都選擇採樣的情形。當然還有很多其他可能性，就像圖中最後的圖表所示。為進一步提高概率，可以可以考慮一個在採樣和期望中的連續變體。 $sigma_t in [0,1]$ 表示在時 $t$ 採樣的程度。其 $sigma = 1$ 表示完全採樣， $sigma=0$ 表示純期望。隨機變 $sigma_t$ 可以設置為狀態、行動、或狀態-行動對的函數。稱這個新提出的演算法 $n$ - $Q(sigma)$ 。

現在建立 $n$ -步 $Q(sigma)$ 的方程。首先留意到Sarsa(7.4)的 $n$ -步回報可以寫成依據其本身基於純樣本的TD誤差：

$G_{t:t+n} = Q_{t-1}(S_t,A_t) + sum_{k=t}^{min(t+n-1,T-1)}gamma^{k-t}[R_{k+1}+gamma Q_k(S_{k+1}, A_{k+1})-Q_{k-1}(S_k,A_k)]$

這表明如果將TD誤差推廣到從期望使用 $sigma_t$ 滑動到其採樣形式，我們就能包含這兩種情況：

$delta_t dot= R_{t+1} + gamma[sigma_{t+1}Q_t(S_{t+1}, A_{t=1})+(1-sigma_{t+1}ar Q_{t+1})] - Q_{t-1}(S_t, A_t) ag{7.14}$

照例

$ar Q_{t} dot= sum_api(amid S_t)Q_{t-1}(S_t,a) ag{7.15}$

使用這些可以將 $Q(sigma)$ 的回報定義為：

$egin{eqnarray*} G_{t:t+1} &=& R_{t+1} + gamma[sigma_{t+1}Q_t(S_{t+1}, A_{t+1}) + (1-sigma_{t+1})ar Q_{t+1}]\ &=& delta_t + Q_{t-1}(S_t, A_t)\ \ G_{t:t+2}&=& egin{aligned} & R_{t+1} + gamma[sigma_{t+1}Q_t(S_{t+1}, A_{t+1}) + (1-sigma_{t+1})ar Q_{t+1}]\ & -gamma(1-sigma_{t+1})pi(A_{t+1}mid S_{t+1})Q(S_{t+1}, A_{t+1})\ & +gamma(1-sigma_{t+1})pi(A_{t+1}mid S_{t+1})[R_{t+2}+gamma[sigma_{t+2}Q_t(S_{t+2}, A_{t+2})+(1-sigma_{t+2})ar Q_{t+2}]]\ & -gammasigma_{t+1}Q_t(S_{t+1}, A_{t+1})\ & +gammasigma_{t+1}[R_{t+2}+gamma[sigma_{t+2}Q_t(S_{t+2}, A_{t+2})+(1-sigma_{t+2})ar Q_{t+2}]] end{aligned}\ &=& egin{aligned} & Q_{t-1}(S_t,A_t) + delta_t\ & + gamma(1-sigma_{t+1})pi(A_{t+1}mid S_{t+1})delta_{t+1}\ & +gammasigma_{t+1}delta_{t+1} end{aligned}\ &=& Q_{t-1}(S_t,A_t) + delta_t + gamma[(1-sigma_{t+1})pi(A_{t+1}mid S_{t+1}) + sigma_{t+1}]delta_{t+1}\ \ G_{t:t+n} &=& Q_{t-1}(S_t,A_t) + sum_{k=t}^{min(t+n-1, T-1)} delta_kprod_{i=t+1}^k gamma[(1-sigma_i)pi(A_imid S_i)+sigma_i] ag{7.16} end{eqnarray*}$

在on-policy訓練中，此回報已經能像 $n$ -步Sarsa(7.5)中那樣在更新中使用；對於off-policy的情況，則需要將 $sigma$ 考慮進重要性採樣率，可以更普遍地定義為：

$ho_{t:h} dot= prod_{k=t}^{min(h,T-1)}left( sigma_kfrac{pi(A_kmid S_k)}{b(A_kmid S_k)} + 1 -sigma_k ight) ag{7.17}$

這之後就可以對 $n$ -步Sarsa(7.9)使用普遍的(off-policy)更新。完整的演算法如下：