概述
時(shí)序差分算法是一種無模型的強(qiáng)化學(xué)習(xí)算法。它繼承了動(dòng)態(tài)規(guī)劃(Dynamic Programming)和蒙特卡羅方法(Monte Carlo Methods)的優(yōu)點(diǎn)，從而對(duì)狀態(tài)值(state value)和策略(optimal policy)進(jìn)行預(yù)測(cè)。從本質(zhì)上來說，時(shí)序差分算法和動(dòng)態(tài)規(guī)劃一樣，是一種bootstrapping的算法。同時(shí)，也和蒙特卡羅方法一樣，是一種無模型的強(qiáng)化學(xué)習(xí)算法，其原理也是基于了試驗(yàn)。雖然，時(shí)序差分算法擁有動(dòng)態(tài)規(guī)劃和蒙特卡羅方法的一部分特點(diǎn)，但它們也有不同之處。以下是它們各自的backup圖：
根據(jù)它們的backup圖可以知道，動(dòng)態(tài)規(guī)劃的backup操作是基于當(dāng)前狀態(tài)和下一個(gè)狀態(tài)的reward，蒙特卡羅方法的backup是基于一個(gè)完整的episode的reward，而時(shí)序差分算法的backup是基于當(dāng)前狀態(tài)和下一個(gè)狀態(tài)的reward。其中，最基礎(chǔ)的時(shí)序差分算法被稱為TD(0)。它也有許多拓展，如n-step TD算法和TD(lambda)算法。
Stationary Environment和Nonstationary Environment的區(qū)別
Stationary Environment即為固定的環(huán)境，也就是說采取相同的動(dòng)作時(shí)，狀態(tài)和環(huán)境是固定不變的。如：垃圾回收機(jī)器人每次充完電之后電都是滿的。而Nonstationary Environment與此相反，在采取相同的動(dòng)作時(shí)，狀態(tài)和環(huán)境是不確定的。如：轉(zhuǎn)一下抽獎(jiǎng)轉(zhuǎn)盤，它每次停止的位置都是不一樣的。
TD(0)時(shí)序差分算法
時(shí)序差分算法和蒙特卡羅方法一樣，仍然有兩部分計(jì)算。第一部分是時(shí)序差分的預(yù)測(cè)(即計(jì)算state value)，第二部分是時(shí)序差分的控制(TD control)，其目的是為了得到最優(yōu)的策略(optimal policy)。
時(shí)序差分預(yù)測(cè)(TD Prediction)
預(yù)測(cè)是為了計(jì)算狀態(tài)值(state value)。在計(jì)算的時(shí)間上，時(shí)序差分比蒙特卡羅方法更快一些。其計(jì)算公式分別如下所示：
根據(jù)公式，TD只需要等到跳轉(zhuǎn)到下一個(gè)狀態(tài)時(shí)，便可得知當(dāng)前狀態(tài)的state value。但是，蒙特卡羅方法則需要等到整個(gè)試驗(yàn)結(jié)束之后才可以得到當(dāng)前狀態(tài)的state value值。因?yàn)椋瑫r(shí)序差分算法計(jì)算value值時(shí)，是根據(jù)當(dāng)前狀態(tài)和接下來的狀態(tài)來計(jì)算，因此是有偏差的，但方差很小。相反，蒙特卡羅方法是無偏差的，但是方差卻很大。
時(shí)序差分和蒙特卡羅方法的學(xué)習(xí)都是通過試驗(yàn)采樣來計(jì)算value值的，采樣致使我們無法得到完整的在當(dāng)前狀態(tài)跳到下一個(gè)狀態(tài)的分布?？梢郧逦膹纳厦娴腷ackup 圖了解到，只有DP是基于所有的下一個(gè)狀態(tài)的分布。
TD算法和MC算法更新的那一部分被我們成為error(即真實(shí)value和評(píng)估的value的差值)，如下所示：
因?yàn)槭歉逻^程，所以其目的就是為了使最終預(yù)測(cè)的value值與真實(shí)的value值的誤差盡量小，也就是使其error最小化。在預(yù)測(cè)的計(jì)算公式中，alpa代表的是步長，類似于梯度下降里面的步長。為什么不讓error直接變到最小(為零)呢？其原因和我們平常所學(xué)的Gradient Descent概念是一樣的。因?yàn)?，我們使用的是抽樣的方法，并沒有得到真正的數(shù)據(jù)分布，而如果步長很大的話反倒會(huì)使計(jì)算value的收斂速度下降。其TD Prediction的偽代碼如下：
Batch TD(0)
在對(duì)state value進(jìn)行預(yù)測(cè)時(shí)，我們不僅可以一個(gè)試驗(yàn)一個(gè)試驗(yàn)的更新，同時(shí)，也可以一批一批的進(jìn)行更新。這就是我們所說的batch TD(0)。
例1: 假如我們對(duì)一個(gè)隨機(jī)游走(Random Walk)的游戲進(jìn)行state value的預(yù)測(cè)。我們通過一批(8個(gè))試驗(yàn)得到了狀態(tài)和相應(yīng)的reward，如下所示：
????????????????????????????????A:0, B:0 ? ? ? ?B:1 ? ? ? ? B:1 ? ? ? ?B:1 ? ? ? ?B:1 ? ? ? ?B:1 ? ? ? ?B:0 ? ? ? ?B:1????
我們很容易計(jì)算出B的value值應(yīng)該為四分之三。因?yàn)樵谶@8個(gè)試驗(yàn)中，B為1的總共有六個(gè)。而A的value值是多少呢？可能有人會(huì)說是0，因?yàn)橹挥幸淮卧囼?yàn)，而且A的reward還為零。但其實(shí)答案也是四分之三。要知道TD計(jì)算A的value值會(huì)根據(jù)下一個(gè)狀態(tài)的reward計(jì)算的，因?yàn)橹挥幸粋€(gè)A試驗(yàn)，且狀態(tài)被轉(zhuǎn)換到了B狀態(tài)。因此，TD會(huì)推斷從A到B的概率應(yīng)該是100%，所以通過計(jì)算，A的value值即為0 + 3 / 4 = 3 / 4。
Sarsa: On-policy TD Control
前面在講蒙特卡羅方法時(shí)，我們已經(jīng)說明了on-policy和off-policy的區(qū)別了，這里就不再重復(fù)。我們知道一個(gè)episode是由多個(gè)state-action對(duì)所組成的，如圖所示：
Sarsa則是State->action->reward->State->action(St, At, Rt+1, St+1, At+1)的簡稱。所以，其action value的計(jì)算公式為：
其偽代碼如下所示：
Q-learning: Off-policy Control
Q-learning是一種off-policy的算法，也就是里面有兩個(gè)policy。其中，behavior policy是用來去盡可能的探索。其偽代碼如下所示：
Expected Sarsa
Expected Sarsa和Q-learning很像， 其區(qū)別在于Q-learning中behavior policy計(jì)算的是最大值，而Expected Sarsa計(jì)算的則是期望，如圖所示：
其公式如下所示：
Reference
1. Reinforcement Learning An Introduction
2.強(qiáng)化學(xué)習(xí)入門 第四講 時(shí)間差分法（TD方法）?https://zhuanlan.zhihu.com/p/25913410
