https://antkillerfarm.github.io/

Temporal-Difference Learning（續）

TD vs. MC—3

再來看如下示例：

已現有兩個狀態(A和B)，MDP未知，衰減系數為1，有如下表所示8個完整Episode的經驗及對應的即時獎勵，其中除了第1個Episode有狀態轉移外，其余7個均只有一個狀態。

Episode狀態轉移及獎勵

1	A:0,B:0
2	B:1
3	B:1
4	B:1
5	B:1
6	B:1
7	B:1
8	B:0

問題：依據僅有的Episode，計算狀態A，B的價值分別是多少，即V(A)=？， V(B)=？

答案：V(B) = 6/8，V(A)根據不同算法結果不同，用MC算法結果為0，TD則得出6/8。

解釋：應用MC算法，由于需要完整的Episode,因此僅Episode1可以用來計算A的狀態價值，很明顯是0；同時B的價值是6/8。應用TD算法時，TD算法試圖利用現有的Episode經驗構建一個MDP（如下圖），由于存在一個Episode使得狀態A有后繼狀態B，因此狀態A的價值是通過狀態B的價值來計算的，同時經驗表明A到B的轉移概率是100%，且A狀態的即時獎勵是0，并且沒有衰減，因此A的狀態價值等于B的狀態價值。

MC算法試圖收斂至一個能夠最小化狀態價值與實際收獲的均方差的解決方案。TD算法則收斂至一個根據已有經驗構建的最大可能的Markov模型的狀態價值。

通過比較可以看出，TD算法使用了MDP問題的Markov屬性，在Markov環境下更有效；但是MC算法并不利用Markov屬性，通常在非Markov環境下更有效。

DP & MC & TD

Monte-Carlo, Temporal-Difference和Dynamic Programming都是計算狀態價值的一種方法，區別在于，前兩種是在不知道Model的情況下的常用方法，這其中又以MC方法需要一個完整的Episode來更新狀態價值，TD則不需要完整的Episode；DP方法則是基于Model（知道模型的運作方式）的計算狀態價值的方法，它通過計算一個狀態S所有可能的轉移狀態S’及其轉移概率以及對應的即時獎勵來計算這個狀態S的價值。

關于是否Bootstrap：MC沒有bootstrapping，只使用實際收獲；DP和TD都有bootstrapping。

關于是否用采樣來計算: MC和TD都是應用樣本來估計實際的價值函數；而DP則是利用模型直接計算得到實際價值函數，沒有采樣之說。

上圖從兩個維度解釋了四種算法的差別，多了一個窮舉法。這兩個維度分別是：采樣深度和廣度。當使用單個采樣，同時不走完整個Episode就是TD；當使用單個采樣但走完整個Episode就是MC；當考慮全部樣本可能性，但對每一個樣本并不走完整個Episode時，就是DP；當既考慮所有Episode又把Episode從開始到終止遍歷完，就變成了窮舉法。

需要提及的是：DP利用的是整個MDP問題的模型，也就是狀態轉移概率，雖然它并不實際利用樣本，但是它利用了整個模型的規律，因此認為是Full Width的。

bootstrapping

在前面的章節，我們一直提到bootstrapping這個名詞，然而卻沒有解釋它的含義，現在是時候了。

統計學中，bootstrapping可以指依賴于重置隨機抽樣的一切試驗。bootstrapping可以用于計算樣本估計的準確性。對于一個采樣，我們只能計算出某個統計量(例如均值)的一個取值，無法知道均值統計量的分布情況。但是通過自助法(自舉法)我們可以模擬出均值統計量的近似分布。有了分布很多事情就可以做了（比如說有你推出的結果來進而推測實際總體的情況）。

bootstrapping方法的實現很簡單，假設抽取的樣本大小為n:

在原樣本中有放回的抽樣，抽取n次。每抽一次形成一個新的樣本，重復操作，形成很多新樣本，通過這些樣本就可以計算出樣本的一個分布。新樣本的數量通常是1000-10000。如果計算成本很小，或者對精度要求比較高，就增加新樣本的數量。

優點：簡單易于操作。

缺點：bootstrapping的運用基于很多統計學假設，因此假設的成立與否會影響采樣的準確性。

但是，這不是bootstrapping在RL中的含義！

Finally, we note one last special property of DP methods. All of them update estimates of the values
of states based on estimates of the values of successor states. That is, they update estimates on the
basis of other estimates. We call this general idea bootstrapping.

上面這段是Sutton給bootstrapping的定義，其實也不是太好懂。那么bootstrapping到底是什么意思呢？

V(St)←V(St)+α(Rt+1+γV(St+1)?V(St))V(St)←V(St)+α(Rt+1+γV(St+1)?V(St))

上式是TD的更新公式，從中可以看出TD target：Rt+1+γV(St+1)Rt+1+γV(St+1)中已經包含了V(s)，也就是說它是用其它V(s)更新當前V(s)。這種特性就是bootstrapping。

V(St)←V(St)+α(Gt?V(St))V(St)←V(St)+α(Gt?V(St))

而MC的target：GtGt就和V(s)無關。

參考：

https://datascience.stackexchange.com/questions/26938/what-exactly-is-bootstrapping-in-reinforcement-learning

What exactly is bootstrapping in reinforcement learning?

TD(n)

先前所介紹的TD算法實際上都是TD(0)算法，括號內的數字0表示的是在當前狀態下往前多看1步，要是往前多看2步更新狀態價值會怎樣？這就引入了n-step的概念。

在當前狀態往前行動n步，計算n步的return，同樣TD target 也由2部分組成，已走的步數使用確定的即時reward，剩下的使用估計的狀態價值替代。這就是TD(n)算法。

顯然，MC實際上就是TD(n=∞n=∞)。

定義n-步收獲：

G(n)t=Rt+1+γRt+2+?+γn?1Rt+n+γnV(St+n)Gt(n)=Rt+1+γRt+2+?+γn?1Rt+n+γnV(St+n)

TD(n)的更新公式：

V(St)←V(St)+α(G(n)t?V(St))V(St)←V(St)+α(Gt(n)?V(St))

Large Random Walk

既然存在n-步預測，那么n=？時效果最好呢，下面的例子試圖回答這個問題：

這個示例研究了使用多個不同步數預測聯合不同步長(step-size，公式里的系數αα）時，分別在在線和離線狀態時狀態函數均方差的差別。所有研究使用了10個Episode。離線與在線的區別在于，離線是在經歷所有10個Episode后進行狀態價值更新；而在線則至多經歷一個Episode就更新依次狀態價值。

結果如圖表明，離線和在線之間曲線的形態差別不明顯；從步數上來看，步數越長，越接近MC算法，均方差越大。對于這個大規模隨機行走示例，在線計算比較好的步數是3-5步，離線計算比較好的是6-8步。但是不同的問題其對應的比較高效的步數不是一成不變的。因此選擇多少步數作為一個較優的計算參數也是一個問題。

TD(λλ)

一種簡單的方法是計算Averaging n-Step Returns，例如：

G=12G(2)+12G(4)G=12G(2)+12G(4)

有沒有更有效的方法呢？這里我們引入了一個新的參數：

λλ 。通過引入這個新的參數，可以做到在不增加計算復雜度的情況下綜合考慮所有步數的預測。

λλ收獲：

Gλt=(1?λ)∑n=1∞λn?1G(n)tGtλ=(1?λ)∑n=1∞λn?1Gt(n)

λλ預測：

V(St)←V(St)+α(Gλt?V(St))V(St)←V(St)+α(Gtλ?V(St))

這張圖還是比較好理解，例如對于n=3的3-步收獲，賦予其在收獲中的權重如左側陰影部分面積，對于終止狀態的T-步收獲，T以后的所有陰影部分面積。而所有節段面積之和為1。這種幾何級數的設計也考慮了算法實現的計算方便性。

TD(λλ)的設計使得Episode中，后一個狀態的狀態價值與之前所有狀態的狀態價值有關，同時也可以說成是一個狀態價值參與決定了后續所有狀態的狀態價值。但是每個狀態的價值對于后續狀態價值的影響權重是不同的。我們可以從兩個方向來理解TD(λλ)：

前向認識TD(λλ)

引入了λλ之后，會發現要更新一個狀態的狀態價值，必須要走完整個Episode獲得每一個狀態的即時獎勵以及最終狀態獲得的即時獎勵。這和MC算法的要求一樣，因此TD(λλ)算法有著和MC方法一樣的劣勢。λ取值區間為[0,1]，當λλ=1時對應的就是MC算法。這個實際計算帶來了不便。

反向認識TD(λλ)

TD(λλ)從另一方面提供了一個單步更新的機制，通過下面的示例來說明。

老鼠在連續接受了3次響鈴和1次亮燈信號后遭到了電擊，那么在分析遭電擊的原因時，到底是響鈴的因素較重要還是亮燈的因素更重要呢？

這里有兩種啟發方法：

頻率啟發 Frequency heuristic：將原因歸因于出現頻率最高的狀態。

就近啟發 Recency heuristic：將原因歸因于較近的幾次狀態。

給每一個狀態引入一個數值：效用追蹤（Eligibility Traces, ET），來結合上述兩種啟發：

E0(s)=0Et(s)=γλEt?1(s)+1(St=s)E0(s)=0Et(s)=γλEt?1(s)+1(St=s)

上圖是Et(s)Et(s)函數的一個可能的曲線圖。該圖橫坐標是時間，橫坐標下有豎線的位置代表當前進入了狀態s，縱坐標是效用追蹤值E 。可以看出當某一狀態連續出現，E值會在一定衰減的基礎上有一個單位數值的提高，此時將增加該狀態對于最終收獲貢獻的比重，因而在更新該狀態價值的時候可以較多地考慮最終收獲的影響。同時如果該狀態距離最終狀態較遠，則其對最終收獲的貢獻越小。

特別的，E值并不需要等到完整的Episode結束才能計算出來，它可以每經過一個時刻就得到更新。E值存在飽和現象，有一個瞬時最高上限：

Emax=1/(1?γλ)Emax=1/(1?γλ)

結合之前提到的TD error和ET，則更新公式可改為：

V(St)←V(St)+αδtEt(s)V(St)←V(St)+αδtEt(s)

如果λ=0λ=0，則只有當前狀態得到更新，即Et(s)=1(St=s)Et(s)=1(St=s)，這實際上就和之前提到TD(n=0)算法是一致的了。

David Silver的課件在這里存在表示混亂的問題，在之前的章節中，TD(X)表示的是n=X，而下文中TD(X)有的時候指的是λ=Xλ=X。這里借用python表示參數的語法，更準確的描述公式。

如果$$lambda=1$，TD($\lambda=1$)粗略看與每次訪問的MC算法等同；在線更新時，狀態價值差每一步都會有積累；離線更新時，TD($\lambda=1$)等同于MC算法(即遍歷整個Episode)。

總結

以上是生活随笔為你收集整理的机器学习（二十九）——Temporal-Difference Learning的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。