# Reinforcement Learning: An Introduction_Chapter 6 Temporal-Difference Learning
###### tags: `Reinforcement Learning` `Second Edition`

[相關連結_Sutton_2nd](http://incompleteideas.net/book/the-book-2nd.html)
[David Silver_bilibili_簡中字幕](https://www.bilibili.com/video/BV1kb411i7KG/)
[程式碼參考_ShangtongZhang](https://github.com/ShangtongZhang/reinforcement-learning-an-introduction)
[程式碼參考_dennybritz](https://github.com/dennybritz/reinforcement-learning)
[程式碼參考_弱弱的我](https://github.com/shaoeChen/Reinforcement-Learning-An-Introduction-Record)

如果你問我，當今世上最新潮的強化學習是什麼，那我就跟你說，就是temporal-difference(TD) learning(後續皆簡寫為TD-learning)。TD-learning結合MC與DP的概念，它可以像MC一樣，直接從經驗學習，不需要環境動態性的模型，也可DP一樣，不需要最終的結果(TD使用自舉(bootstrap))，而是基於其它部份的學習測估來更新當前的估測值。這一章裡面我們會看到這三種方法以各種方式結合在一起。Chapter 7中，我們會說明$n$-step algorithms，這能夠將MC與TD之間有個關聯，然後Chapter 12的時候，我們會介紹TD($\lambda$) algorithm，這可以將MC與TD無縫接軌。

一樣的，我們會先關注policy evaluation或prediction problem，也就是給定$\pi$的情況下來估測value function $v_\pi$。然後對於控制問題(control problem，也就是找出一個optimal policy)，DP、TD、MC都是使用GPI(generalized polciy iteration)的概念。這些方法之間的差異在於它們解決預測問題的方式不同。

## 6.1 TD Prediction
TD與MC都是用經驗來解預測問題，也就是給定一些依著policy $\pi$得到的經驗，兩個方法都是從這些經驗中的nonterminal state $S_t$來更新它們的$v_\pi$。不過它們之間還是有一點點差異，MC要有一個return才能用這個return來做為$V(S_t)$的目標。我們可以把一個非穩定環境(nonstationary environments)的every-visit MC寫成下面這樣：
$$V(S_t) \leftarrow V(S_t) + \alpha [G_t - V(S_t)] \tag{6.1}$$

其中$G_t$是在時間$t$的實際的return，而$\alpha$是定義step-size的常數參數，可見方程式2.4。這方樣稱為constant-$\alpha$ MC。

:::warning
$$\text{NewEstimate} \leftarrow \text{OldEstimate + StepSize [ Target - OldEstimate ]} \tag{2.4}$$
:::

MC必需要一直等到episode終止才能做$V(S_t)$的增量，因為只有這個時候才知道$G_t$是多少，但是TD只需要下一個time step就可以知道。在時間$t+1$就能立即形成目標，然後用觀察到的reward $R_{t+1}$與估測值$V(S_{t+1})$來做一個有效的更新。最簡單的TD更新如下(轉移至$S_{t+1}$與得到reward $R_{t+1}$立即性的更新)：
$$V(S_t) \leftarrow V(S_t) + \alpha[R_{t+1} + \gamma V(S_{t+1}) - V(S_t)] \tag{6.2}$$

事實上，MC的目標是更新$G_t$，而TD的目標則是更新$R_{t+1} + \gamma V(S_{t+1})$，這樣的方法稱為TD(0)，或是one-step TD，後續還會談到TD($\lambda$)、$n$-step TD，下面先給出TD(0)的完整程序：

TD(0)的更新是部份基於已存在的估測，所以我們說，這是一種bootstrapping method(自舉法？)，就好比是DP。我們從Chapter 3已經知道：
$$
\begin{align}
v_\pi(s) & \dot{=} \mathbb{E}_\pi[G_t \vert S_t=s] \tag{6.3} \\
&= \mathbb{E}_\pi[R_{t+1} + \gamma G_{t+1} \vert S_t=s] \tag{3.9} \\
&= \mathbb{E}_\pi[R_{t+1} + \gamma v_\pi(S_{t+1}) \vert S_t=s] \tag{6.4}
\end{align}
$$

大致上來說是這樣的：
* MC
* 用6.3的估測值做為目標
* 為估測值，因為6.3的期望值是未知的，我們的做法是用樣本回報(sample return)做為部份的實際的期望回報(real expected return)
* DP
* 用6.4的估測值做為目標
* 雖然是一個估測，但並不是因為期望值，而是因為我們假設我們有完整的關於環境模型的資訊，但是因為$v_\pi(S_{t+1})$是未知的，因此用$V(S_{t+1})$來替代
* TD
* TD的目標也是一種估測值，這有兩個理由：(1)它從6.4得到樣本期望值，(2)它使用當前的估測值$V$來取代實際的估測值$v_\pi$

基於上面兩個條件我們可以看的到，TD結合的MC的採樣與DP的自舉(bootstrapping)。後面我們會看到TD是如何結合MC、DP兩個方法的優點。

下圖看到的是屬於tabular TD(0)的backup diagram：

上圖可以看的到，backup diagram的最上面的那個state節點的估測值是依據它後面那個state一次樣本轉移之後來做更新的。我們談到MC、TD的更新是屬於一種樣本更新(sample updates)，因為它們涉及了樣本後續的狀態(state)(或state-action pair)，使用後續的state的value與沿途計算而得的back-up value來更新original state的value(或是original state-action pair)。而sample updates與DP所用的expected updates的不同在於，sample update是基於單一個後續狀態的採樣(這可以看上面那一張TD(0)的backup diagram)，而不是所有可能的後續狀態的完整分佈。

:::warning
理解上，sample update是只跟後續有遇到的state有關，因此MC、TD就屬於這類型的。而expected update是跟後續所有的state有關，因此DP就屬於類型的。以gridworld為例，我們就會是計算上、下、左、右四個action的next state的value，這就是計算所有可能的state的value。
:::

最後，我們注意到TD(0)更新中，那個括號內的數值所代表的是一種誤差，這稱為TD error，這邊衡量的是估測值$S_t$與較好的估測值$R_{t+1} + \gamma V(S_{t+1})$之間的差異，這會在強化學習中以各種形式出現，如下：
$$\delta_t \dot{=} R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \tag{6.5}$$

下面這張圖是個人在學校報告的時候弄的，應該可以比直觀理解：

上圖左的time $t$可以看的到，有14隻怪，這時候的$V(s)=14$，選擇的action是fire，然後就進入time $t+1$，擊中一隻，得到reward=1，這時候的$V(s')=13$，如果估出來的是12，那中間的誤差就稱為TD error。

注意到兩件事：
1. 是TD error每次的估測的都是當下這個time誤差。因為TD error是取決於下一個state與下一個reward，所以你要在下一個time step之後才能得到相關資訊。這意思是說，$\delta_t$是$V(S_t)$的error，不過你在$t+1$的時候才算的出來
2. 如果array $V$在一個episode期間沒有任何的改變(MC就是這樣，它是在結束的時候才會改變)，那MC error就可以寫成TD error

下面給出MC error寫成TD error的推導：
$$
\begin{align}
G_t-V(S_t)&=R_{t+1} + \gamma G_{t+1} - V(S_t) + \gamma V(S_{t+1}) - \gamma V(S_{t+1}) \tag{3.9} \\
&= \delta_t + \gamma(G_{t+1} - V(S_{t+1})) \\
&= \delta_t + \gamma \delta_{t+1} + \gamma^2(G_{t+2}-V(S_{t+2})) \\
&= \delta_t + \gamma \delta_{t+1} + \gamma^2 \delta_{t+2} + \cdots + \gamma^{T-t-1}\delta_{T-1} + \gamma^{T-t}(G_T - V(S_T))\\
&= \delta_t + \gamma \delta_{t+1} + \gamma^2 \delta_{t+2} + \cdots + \gamma^{T-t-1}\delta_{T-1} + \gamma^{T-t}(0-0) \\
&= \sum_{k=t}^{T-1}\gamma^{k-t}\delta_k \tag{6.6}
\end{align}
$$

:::warning
下面給出公式3.9，
1. 第一行只是單純的把$G_t$展開3.9，然後一加一減$\gamma V(S_{t+1})$
2. 第二行把公式6.5帶入得到$\delta_t$，剩下的取出$\gamma$做整理
3. 第三行你發現，整理之後的$\gamma(G_{t+1} - V(S_{t+1}))$可以讓你再做一次第二行的事情
:::

:::warning
$$
\begin{align}
G_t &= R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots \\
&= R_{t+1} + \gamma(R_{t+2} + \gamma R_{t+3} + \gamma^2 R_{t+4} + \cdots)\\
&= R_{t+1} + \gamma G_{t+1}
\end{align} \tag{3.9}
$$
:::

如果$V$在episode期間更動了，那這個恆等式就是不精確的(例如TD(0))，不過如果這個step size不是那麼大，是小小的，那可能還是可以近似成立。這恆等式的泛化性在TD learning的理論與演算法中扮演著重要的角色。

:::info
Example 6.1: Driving Home

每天你開車回家都會試著預估一下你要多久的時間可以回到家。當你離開辦公室，你會注意到時間，然後星期幾、天氣跟其它也許相關的任何事情。假設，這星期五，你離開的時候正好6點，你估計可能30分鐘可以回到家。6點5分的時候到車子，然後你發現下雨了。下雨的時候通常大家開的比較慢，所以你重新估計也許還要開35分鐘才能到家，也就是總共要40分鐘。不賴的是，你15分鐘就下交流道了，所以你覺得應該只要35分鐘就可以到家。只是很倒楣的是，你堵在一台大卡車的屁股後面，這路又很窄，你沒有辦法隨便亂超車。你只能一路塞到你住家附近的街道，這時候已經6點40分了。3分鐘後你到家了。上面這個故事的states、times、predictions如下表所示：

這個範例的reward就是這個行程車每一段經過的時間^註1^，然後沒有計算discount，也就是$\gamma=1$，因此，每一個state的return就是離開該state的實際時間，你可以看的到上面表格的Elapsed Time就是該state的return。每個state的value就是你預期到家的時間。上面表格的Predicted Time to Go給出你遇到每一個state的當前估測值。

* 註1：如果把這個問題視為求最短行程時間的控制問題，那我們當然是把經過的時間取負值來做為reward。但我們這邊只關心預測問題(prediction，即policy evaluation)，所以就簡單來看，維持正數，不取負數。

下面先給出MC與TD對於開車回家的這個範例的不同：
Figure 6.1：Changes recommended in the driving home example by Monte Carlo methods (left) and TD methods (right).

上圖左就是用MC去繪出預測的總時間(總時間見上面表格最後一欄)，紅色箭頭所表示的就是利用constant-$\alpha$ MC method所給出的建議預測，$\alpha = 1$。這正是每個state的估測值(predicted time to go)與實際的return(actual time to go)之間的誤差。舉例來說，當你下交流道之後你以為你只要再15分鐘就可以回到家，但實際上你下交流道之後還花了23分鐘。這時候你完全可以用方程式6.1來計算下交流道之後的剩餘時間的增量。(如下所示)

$$V(S_t) \leftarrow V(S_t) + \alpha [G_t - V(S_t)] \tag{6.1}$$

誤差值，$G_t-V(S_t)$，在這時候是8分鐘。假設step-size $\alpha=1/2$，那根據這個經驗你下交流道之後的誤差就會是4分鐘。這個範例中，這改變可能有點大；因為可能只是剛好倒楣去卡在大貨車屁股後面。無論如何，這種改變只有發生在[off-line](http://terms.naer.edu.tw/detail/13833706/)的情況，也就是說你到家之後再來改變，也只有你到家了才能知道實際的returns。
:::

我們說，有沒有一定要有最終結果之後才能開始學習呢？我們來想另一種情況。某一天你又下班無聊在想你離開辦公室回家需要多少時間，一樣的，離開辦公室回到家要30分鐘，但這次你真的卡到了，離開辦公室25分鐘了，你還是一樣在高速公路上，還沒有辦法可以下交流道。這時候你估計還需要再25分鐘才有辦法回到家，這樣回家就總共花了50分鐘。現在你已經知道你估30分鐘是太樂觀了。現在你覺得你還需要等回到家才能知道一開始估30分鐘太樂觀了嗎？

如果你用MC methods，那答案當然就是肯定的，因為你還不知道那個true return。但是如果是TD，你可以立即的學習，直接把你的初始預估從30分鐘調整為50分鐘。事實上，每個估測值都會轉移為緊接在後的那個估測值，這你可以從Figure 6.1右邊看的出來。

回到Example 6.1的情境，Figure 6.1右邊圖給出的就是利用TD(公式6.2)會得到的預測建議，而這些改變是假設$\alpha=1$而得。每一個誤差(error_都與預測隨時間變化成正比，也就是我們說的temporal differences(時序差異？)

直接根據當前預測來學習而不等到有實際結果之後再來學習是有幾個計算方面的優點的，這在後面會說明。
## 6.2 Advantages of TD Prediction Methods
TD更新估測值會基於部份其它估測值。它們從猜測中學習猜測，也就是它們自舉(bootstrap)。這麼做到底好不好，TD到底比MC好了那些，這些問題可能這書還說明不完，不過這章節會有簡單的說明。

很明顯的，TD比之DP有個優點，那就是TD並不需要環境模型，也就是reward與next state的機率分佈。而比之MC的話，TD可以很自然地用著on-line、完全增益的方式來實現。MC必需要一直等到episode結束才能學習，因為這時候你才知道這個episode的return，但TD只需要等待一個time step。這很重要，因為有一些應用它們的episodes太長，所以如果你將所有的學習都推遲到episode結束那就太慢了。而有些應用則是continuing tasks，根本沒有episodes。最後就是，上一章有提到，有些MC必需要忽略或對採取的experimental actions的episodes計算discount，這也大大減緩學習的速度。TD不大受這些問題影響，因為它們從每次轉移中學習，而不會去考慮後續採取怎麼樣的actions。

不過TD這麼樣的計算真的合理嗎？當然啦，從下一個猜測去學習一個猜測那是非常方便的，你也不用真的去等那個實際的最終結果，但我們是否仍然可以保證其收斂性？答案是，YES，這是可以預期的答案，不然幹嘛談。對於任意的fixed policy $\pi$，TD(0)已經被證明可以收斂至$v_\pi$，前提是那個step-size夠小，那它的平均值就可以收斂至$v_\pi$，而如果step-size依著隨機近似條件(2.7)來減少，那它能夠成功收斂的機率就是1。

:::warning
$$\sum_{n=1}^\infty \alpha_n(a) = \infty \text{ and } \sum_{n=1}^\infty \alpha^2_n(a) < \infty \tag{2.7}$$
:::

如果TD、MC都能夠漸近地收斂到正確的預測，那很自然的下一個問題就是，誰會先到達那個聖域？換言之，就是那一個方法比較快？那一個方法比較能夠有效的利用有限的資料？這是一個沒有答案的問題，不過實作上，可以從Example 6.2看的到，TD隨機任務上的收斂通常比constant-$\alpha$ MC還要來的快。

:::info
Example 6.2 Random Walk

這個範例中，我們會憑經驗來比較TD(0)與constant-$\alpha$ MC的預測能力，用下面這個Markov reward process：

Markov reward process，或稱MRP，它是一種Markov decision process沒有action的變體。當我們關注的是預測問題(prediction problem)的時候，我們通常會使用MRPs，這樣我們就不需要去區分這個變動是因為環境，還是來自agent。這個MRP的範例中，所有的episodes都是從中間這個state，也就是$C$開始，然後每個step就是等機率的往左、往右跳一個state。只要到達最左邊或是最右邊的時候，當下的episode就算結束。如果是到最左邊，那reward +0，如果是最右邊，那reward +1。這邊給出一個可能的例子：$C,0,B,0,C,0,D,0,E,1$。因為這個task是undiscounted，所以每個state的實際值(true value)就會是從該state開始會結束於最右邊的機率。所以啊，我們就可以知道中間那一個state的true value就是$v_\pi(C)=0.5$。這樣就不難明白，$A\sim E$的true value則是$\dfrac{1}{6},\dfrac{2}{6},\dfrac{3}{6},\dfrac{4}{6},\dfrac{5}{6}$


上圖左說明了不同episodes各state在做TD(0)後的學習結果。可以看的到在100個episodes之後得到的值已經非常接近實際值，這邊的constant step-size，$\alpha$設置為0.1，因此估測值的波動所反應的是比較接近的episodes。右圖所顯示的則是兩個方法在不同的$\alpha$下的學習曲線。效能的量測是採取學習到的value function與實際的value function之間的RMS(root mean square)，每5個state計算平均，然後在這100次執行中計算平均。然後對於所有的$s$，其approximate value function都被初始化為中間值，$V(s)=0.5$。這個任務來看，TD的表現比MC還要來的好。
:::

:::warning
root mean square，RMS，均方根，也就是平方平均數，$M=\sqrt{\dfrac{\sum^n_{i=1} x^2_i}{n}}$
:::

## 6.3 Optimality of TD(0)
假設，我們的經驗是有限的，也許只有10個episodes或是100個time steps。這種情況下常見的作法就是使用[增量學習](https://terms.naer.edu.tw/detail/13806376/?index=1)反覆的應用這些經驗一直到收斂出一個結果。給定一個approximatate value function ，$V$，然後我們在每一個time step $t$，只要是nontermainal state都利用6.1或6.2所規定來計算其增量，但是value function只會更新一次，也就是所有增量的總和。然後新的value function再拿所有可以用的經驗來處理，以此產生新的總體增量(overall increment)，以此類推，一直到value function收斂。我們稱這作法為batch updating，因為只有在處理完每批完整的訓練資料後才會進行更新。

使用這個batch updating，只要你的$\alpha$(step-size)夠小，TD(0)就確定可以收斂到與step-size無關的唯一答案。constant-$\alpha$ MC method在相同條件下也可以確定收斂，只是收斂到的結果不一樣。這有助於我們瞭解這兩個方法之間的差異。下面我們用幾個範例來說明。

:::info
Example 6.3: Random walk under batch updating

Example 6.2的那個[隨機漫步](http://terms.naer.edu.tw/detail/576952/)預測問題如果用batch-updating version的TD(0)、constant-$\alpha$ MC的話，會是這樣的：在每一個新的episode之後，所有已經過看的episodes都會被視為一個batch。它們會反覆的被用到演算法裡面，TD(0)跟constant-$\alpha$ MC都一樣，然後$\alpha$是小到能夠讓value function收斂的那種。最終得到的value function再來跟$v_\pi$比較，然後每5個states計算其平均平方根誤差(整個實驗是100次獨立的反覆計算)，得到的學習曲線結果如Figure 6.2所示。

Figure 6.2：隨機漫步任務上使用批次訓練(batch training)的TD(0)與constant-$\alpha$ MC的比較

上圖也可以看的出來，TD(0)的結果還是比MC來的好。

使用batch training，constant-$\alpha$ MC收斂至$V(s)$，這是在看過(visiting)每一個state $s$之後的實際回報(actual returns)的樣本平均。某種程度上這算是最佳估測(optimal estimates)，它們最小化來自訓練集內的實際回報(actual returns)的均方誤差(mean square error)。但是你從Figure 6.2來看卻發現，batch TD method的表現竟然比MC還要來的好。它老兄怎麼有辦法比這個optimal method還要來的好？答案是這樣的，MC只在某些有限方面上是最佳的，而TD則是與預測回報(prediction returns)相關方面是最佳的。
:::

:::info
Example 6.4: You are the Predictor
現在，你就是一個預言家，你要預測那個未知的Markov reward process的returns。你從水晶球中看到八個episodes：

第一個episode來看，從$A$開始，轉移至$B$，這個轉移沒有reward，然後在B這地方結束，也沒有reward。其它的更厲害，一個$B$開始，然後就結束。給你這批資料，你覺得最佳的預測是什麼？$V(A)$、$V(B)$最佳估測值又是多少？有人可能會說，$V(B)$的optimal value是$\dfrac{3}{4}$，因為八個episodes裡面它出現六次是有reward。

那$V(A)$呢？這邊給出兩個合理的答案：
1. 我們知道，$A$雖然只出現一次，但是它100%是直接將狀態轉至$B$，雖然reward=0，但我們剛剛已經定義$V(B)$是$\dfrac{3}{4}$，因此$A$就是$\dfrac{3}{4}$。把這個範例用Markov process來看，如下圖所示，很直觀的，$A$有100%的機率會往$B$，然後$B$有75%(6/8)的機率reward=1，25%(2/8)的機率reward=0。這也是TD(0)會給出的答案
* 
2. $A$只出現一次，而且其episode得到的return=0，因此$V(A)=0$，這是MC會給出的答案。值得注意的是，它也是給出訓練資料最小平方誤差的答案。事實上，這答案在這資料集上是沒有誤差的。

實際上來看，我們會覺得第一個答案是比較好的，也就是$3/4$。如果這是一個馬可夫過程，我們會預期第一個答案在未來的資料可以產生較低的誤差，即使MC在已知的資料上有著較好的答案。
:::

Example 6.4給出batch TD(0)與batch MC之間的估測差異：
* batch MC通常可以在訓練集上估測出最小均方誤差
* batch TD(0)通常可以找到完全正確的馬可夫過程最大似然模型的估測

通常，參數的最大似然估計(maximum-likelihood estimate)是生成資料的機率最大的參數值。這種情況下，最大似然估計很明顯的就會是從觀察到的episodes中所形成的馬可夫過程的模型：從$i$到$j$估計的轉移機率會是從$i$到$j$所觀察到轉移的[分數](http://terms.naer.edu.tw/detail/2116426/)，而相關的預期的報酬(expected reward)就會是這些轉移中所觀察到的rewards的平均。給定這個模型，如果這個模型是完全正確的，那我們就可以精確的計算這個value function的估測值。這樣的方法稱為[確定等值](http://terms.naer.edu.tw/detail/2915740/)估計法(certainty-equivalence estimate)，因為這等價於假設潛在過程(underlying process)的估測確定是已知的，而非近似。通常，TD(0)會收斂到確定等值估計。

:::warning
underlying好像也可以翻成基本，所以不確定是潛在過程還是基本過程，反正就是underlying process
:::

這說明了為什麼TD可以收斂的比MC還要來的快。在批次的形式中，TD(0)比MC快是因為它計算的就是真正的確定等值估計。這就說明Figure 6.2那個隨機漫步任務中，TD(0)所呈現出來的優勢。跟確定等值估計的關聯也許也可以說明nonbatch TD(0)的速度優勢。這可以回頭看Example 6.2的右邊那張圖。雖然nonbatch methods無法達到確定等值估計跟最小平方誤差估計，但是它們可以理解為大致還是朝著這些方向在前進。nonbatch TD(0)也許會比constant-$\alpha$ MC還要來的快，因為它就是會往更好的估測的那個方向去發展，即使沒有完全的到達那裡。另外就是，目前對於online的TD、MC誰比較快並沒有一個明確的說法。

最後，值得注意的是，雖然確定等值估計某種程度來看是一個最佳解，但直接去計算它是不可能的。如果$n=\vert \mathcal{S} \vert$是state的數量：
* 計算最大似然估計記憶體需求是$n^2$
* 計算相對應的value function的記憶體需求為$n^3$

如果是TD的話，記憶體需求不超過$n$，就可以在訓練集上反覆的計算，以此得到近似解。所以，如果你的state space非常大，那TD應該是唯一能夠求近似確定等估計的作法。
## 6.4 Sarsa: On-policy TD Control
Sarsa，state-action-reward-state'-action'。

現在我們要用TD prediction methods來處理控制問題(control problem)。按慣例，我們會按著generalized policy iteration(GPI)的模式，不過這次會用TD來處理評估(evaluation)或預測(prediction)的部份。就像先前談過的MC一樣，我們仍然面對exploration(探索)與exploitation(開發)之間的權衡，然後一樣會分成兩種主要類型：on-policy與off-policy。這邊會先說明的是on-policy。

首先要學習的是action-value function，而不是state-value function。特別是，對於on-policy method，我們必需要為當前行為策略$\pi$與所有的states $s$、actions $a$估測其$q_\pi(s, a)$。這本質上跟上面提到學習$v_\pi$是一樣的。回想一下，一個episode的組成，states與state-action pairs的交替序列：

前面我們考慮了state之轉移並且學到states的values。現在我們考慮的是state-action pair之間的轉移，並且要學習到的是state-action pairs的value。形式上來看，這兩件事是一樣的：它們都是有著reward process的Markov chains(有著報酬過程的馬可夫鏈)。使用TD(0)的state value的收斂性也同樣適用於action value：
$$Q(S_t,A_t)\leftarrow Q(S_t,A_t) + \alpha[R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)] \tag{6.7}$$

只要不是terminal state $S_t$，那每次的狀態轉移之後就會做一次上面的更新。如果$S_{t+1}$是terminal state，那$Q(S_{t+1}, A_{t+1})=0$。這個規則用了quintuple(五元組)的每個元素，也就是構成state-action apir轉換的quintuple，$(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$。每個元素的第一個字拿出來，就是Sarsa。其backup diagram如下：

基於Sarsa prediction method來設計出一個on-policy control algorithm是非常簡單的。如同所有on-policy methods，我們連續的針對behavior policy $\pi$估測其$q_\pi$，然後同一時間讓$\pi$變的對$q_\pi$貪婪(greediness)。下面給出Sarsa control algorithm(一般形式)：

Sarsa algoritm的收斂特性取決於policy對$Q$的依賴性。舉例來說，我們可以用$\epsilon-$greedy或$\epsilon-$soft policies。只要所有的state-action pairs都出現過無限次，然後policy也收斂到greedy policy的極限，那Sarsa就會以1的機率收斂到optimal policy與action-value function(舉例來說，$\epsilon-$greedy policies設置$\epsilon=1/t$就可以達成)。

:::info
Example 6.5: Windy Gridworld

如上圖的小插圖所示，那是一個標準的gridworld，有開始(S)與目標(G)狀態，有一點不同：有一個側風在中間由下往上吹。那actions一樣是標準的那四個，上、下、右、左，但是到中間之後你的next state會被風往上吹而導致偏移，造成偏移的強度會依不同的column而有所不同。風吹的強度也在每個column上給出，一看你就知道會被吹幾格。舉例來說，如果你在目標(G)右邊的格子，然後你執行action是向左，那你就會被帶到目標(G)的上面一格。這是undiscounted episodic task，在你到達目標之前，你每次都會得到reward=-1。

那個趨勢線則是你用$\epsilon-$greedy Sarsa來處理這個任務的結果，其$\epsilon=0.1, \alpha=0.5$，然後所有的$s, a$的初始$Q(s,a)=0$。上圖可以看的到，斜率增加說明的是，隨著時間的推移，我們可以更快的到達目標(G)。在經過8000個time steps之後，greedy policy早就是optimal(插圖說明的就是它的trajectory)；一直是$\epsilon-$greedy exploration的話，大概每個episodes都是平均17個steps可以完成，比最小15個steps還要多2個steps。注意到，這個任務用MC可能不是那麼輕鬆，因為不是所有的policies都能夠保證終止。如果曾經有policy被發現會導致agent停留在同一個state，那下一個episode它就永遠不會終止。像是Sarsa這種online learning methods不會有這樣的問題，因為它們會很快的在episode的期間學習，如果policies不夠好，那就換一個。
:::
## 6.5 Q-learning: Off-policy TD Control
早期強化學習一個重大的突破就是off-policy TD control algorithm的發展，也就是傳說中的Q-learning(Watkins, 1989)，定義如下：
$$Q(S_t, A_t) \leftarrow Q(S_t,A_t) + \alpha[R_{t+1}+\gamma \max_a Q(S_{t+1}, a) - Q(S_t, A_t)] \tag{6.8}$$

:::warning
下面給出Sarsa，方便比較
$$Q(S_t,A_t)\leftarrow Q(S_t,A_t) + \alpha[R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)] \tag{6.7}$$
:::

這種情況下，我們學習到的action-value function，$Q$，會直接近似$q_*$，也就是option action-value function，跟所依循的policy無關。這大大的簡化演算法的分析，也讓早期的收斂性得以證明。policy對於那些已經看過、更新完的確定性的state-action pairs仍然有影響力。然後，你要能夠正確的收斂就是要所有全部的state-action pairs能夠持續的被更新。就像我們在Chapter 5看到那樣，這是一般情況下任一個方法要保證能夠找到optimal behavior的最底要求。在這個假設之下，加上step-size parameters的序列上類似於常用的隨機近似條件，$Q$已經被證明可以以1的機率收斂至$q_*$。$Q$-learning algorithm程式如下：

那$Q$-learning的backup diagram是長什麼樣子？規則6.8更新了state-action pair，因此，那個top node，也就做為更新的那個root，就必需是一個小小的，填滿的action node。

:::warning
真的不是很明白這個意思，The rule (6.8) updates a state–action pair, so the top node, the root of the update, must be a small, filled action node。不過能確定的是描述的應該就是backup diagram就是了。
:::

而更新也是來自於action nodes，也就是next state裡面所有可能的actions中能夠最大化value的那一個。因此，這個backup diagram的bottom nodes就會是所有的這些action nodes。最後，記得，我們採取的是那些"next action" nodes中最大的那一個，就是Figure 3.4右邊圖的那個有弧線穿過的那一個。現在你能猜到它的diagram了嗎？我不行，所以我直接看答案：

Figure 6.4: The backup diagrams for Q-learning and Expected Sarsa

:::warning
Figure 3.4的backup diagrams以圖形化來說明$v_*, q_*$的Bellman optimality equations中所考慮的未來的state與action。
:::

:::info
Example 6.6: Cliff Walking
這個gridworld的範例要比較的是Sarsa on-policy與Q-learnin off-policy之間的差異，差異的部份就特別把它highlight出來。這個gridworld長的就像下面這樣：

這個gridworld的性質如下：
1. undiscount
2. episodic task
3. 有start state與goal state
4. actions有上、下、左、右
5. 每個狀態的轉移reward都-1，除非你進入"The Cliff"的區域，那reward就變-100，然後把你送回起點(綠色線)

上圖呈現的是兩個方法(Sarsa、Q-learnin)使用$\epsilon-$greedy($\epsilon=0.1$)的結果：
* 在[起始瞬變](http://terms.naer.edu.tw/detail/3112801/)之後，Q-learnin就學到optimal policy的value，也就是延著cliff(懸崖)的邊緣在走。不過厚，因為是用$\epsilon-$greedy的方式，所以三不五時還是會掉下去
* Sarsa的話則是將action的選擇列入考慮，走了一條比較長，但是更安全的路

雖然Q-learning確實的學到optimal pylicy的values，但它的online版本的效能真的是比Sarsa的迂迴策略還要來的糟。當然，如果$\epsilon$逐步的調降，那兩個方法都會漸近的收斂到optimal policy。
:::
## 6.6 Expected Sarsa
我們想像有一種學習演算法，它長的就像是Q-learning一樣，不過它不是取next state-action pairs的作法，而是用expected value(期望值)，以此計算以當前的policy，每一個action的機會有多大。演算法更新規則如下：
$$
\begin{align}
Q(S_t, A_t) & \leftarrow Q(S_t, A_t) + \alpha [R_{t+1} + \gamma \mathbb{E}_\pi[Q(S_{t+1}, A_{t+1}) \vert S_{t+1}] - Q(S_t, A_t)] \\
& \leftarrow Q(S_t, A_t) + \alpha [R_{t+1} + \gamma \sum_a \pi(a\vert S_{t+1})Q(S_{t+1}, a)-Q(S_t, A_t)] \tag{6.9}
\end{align}
$$

其它的部份還是跟Q-learning是一樣的。給定next state，$S_{t+1}$，這演算法跟Sarsa預期的方向一致，因此稱為Expected Sarsa。其backup diagram如下圖所示：

Expected Sarsa的計算複雜度比Sarsa來的高，好處就是，它消除掉因隨機選擇action $A_{t+1}$所產生的方差。給定相同經驗數量的情況下，Expected Sarsa的效果也確實是比Sarsa來的好。Figure 6.3給出上面那個cliff-walking用Expected Sarsa與Sarsa、Q-learning的比較。

Figure 6.3：TD control methods在cliff-walking task上作為$\alpha$的函數的效能(interim與asymptotic)。所有的演算法都使用$\epsilon-$greedy，且$\epsilon=0.1$。asympotoic performance(漸近效能)是100,000個episodes的平均值，然後interim performance則是前100個episodes的平均。這些資料是interim與asymptotic各別執行500,000個episodes與10runs的平均。實心圓的標記則是每一種方法的最佳interim performancec。改編自van Seijen et al. (2009)。

在這個問題上，Expected Sarsa維持著Sarsa比Q-learning好的優點。除此之外，在區間比較大的step-size parameter $\alpha$情況下，Expected Sarsa也較Sarsa有顯著改善。在cliff walking這個範例中，state的轉移都是確定性的，所有的隨機性都是來自於policy。這種情況下，Expected Sarsa可以很放心的設定$\alpha=1$，不需要擔心漸近效能(asymptotic performance)的退化，可是如果是Sarsa的話就只能夠用很小的$\alpha$才能夠在長時間執行有好的表現，如果是短時間的話那效能就會很不好。總之，Expected Sarsa的效能是比較好的。

在cliff walking這個範例中，Expected Sarsa是採用on-policy，不過一般來說，它也可以用一個不同於target policy $\pi$的方式來生成行為(behavior)，只是這種情況下就變成是off-policy。舉例來說，我們假設$\pi$是greedy policy，而behavior是更具有探索性的；這樣的話，Expected Sarsa就完全是Q-learing。在這個意義上，Expected Sarsa包含並概括Q-learning，同時可靠度也較Sarsa來的好。總之，除了計算成本增加的問題之外，Expected Sarsa應該是比這兩種TD control algorithms來的好。

## 6.7 Maximization Bias and Double Learning
目前為止我們談到的控制演算法都涉及到在構建target policies中的最大化。舉例來說，在Q-learning中，target policy就是根據你給定的action values中最大的那一個來做greedy policy的操作，而在Sarsa的話，其policy通常是$\epsilon-$greedy，這也涉及最大化的運算。而這些演算法中，估測值的最大化也是內含著對最大值的估測，這會導致明顯的正偏差(positive bias)。我們來喵喵看為什麼，考慮一個單一的state $s$，然後它有很多的actions $a$，其真實的值(true value)，$q(s,a)$，都是0，但它們的估測值，$Q(s,a)$都是不確定的，因此會有一些是大於0，有一些就小於0。它最大的真實值就是0，但是估測的最大值卻是正值，這就是一個正偏差(positive bias)。我們稱為maximization bias。

:::info
Example 6.7: Maximization Bias Example

Figure 6.5：在一個簡單的episodic MDP上比較Q-learning與Double Q-learning(如插圖所示)。Q-learning一開始學習到採用left的頻率比right還要來的多次， 而且機率明顯高過於$\epsilon=0.1$所強制的最小5%的機率。相比之下，Double Q-learning就不受maximization bias的影響。這些資料是執行10,000次的平均。初始的action-value為0。Any ties in $\epsilon$-greedy action selection were broken randomly. (這句真的不會翻，不過意思大致就是，當你遇到兩個action的機率一致的時候就隨機選一個吧。)

Figure 6.5那個小小的MDP插圖提供簡單的範例，說明maximization bias如何對TD control algorithms造成傷害：
1. 有一個MPD，它有兩個non-terminal states $A$、$B$
2. episode都是從$A$開始
3. 兩個actions，左、右
4. 如果選擇右，那就會馬上進入終止狀態(terminal state)，然後reward、return都是0
5. 如果選擇左，那就轉移至$B$，然後reward也是0，然後接續會有很多actions都會導致立即終止，然後會從一個均值為-0.1、方差為1.0的常態分佈(normal distribution)中得到一個reward

好，現在我們知道，對於任意一個trajectory是從左這個action開始的expected return都是-0.1，這樣子，你在$A$選擇左這個action就是錯的。

儘管如此，我們的control methods也許會喜歡"左"這個action，因為maximization bias讓$B$明顯的有positive value。所以你看一下上面的圖也不難發現，用著$\epsilon-$greedy的Q-learning一開始的學習是非常愛好"左"這個action。即使在漸近線處，選擇"左"的機率也還是比我們參數設置($\epsilon=0.1, \alpha=0.1, \gamma=1$)的最佳值高了大約5%。

實作上你可以利用`np.random.normal(-0.1, 1)`從均值為-0.1、方差為1.0的常態分佈(normal distribution)中得到一個reward。
:::

看完範例，那我們想問的是，有沒有演算法可以避免掉maximization bias的問題？我們先來看賭博機問題，我們對許多actions的每一個value做噪點的估測(noisy estimates)，這是遊戲中每個action所得到的rewards的樣本平均。如我們上面所討論，如果我們使用估測的最大值來做為實際值的最大值的估測，那就會存在一個positive maximization bias。有一種看法是說，這是因為確定價值最大化的action與估測其值(value)的這兩件事都是使用相同的樣本所造成。假如我們把樣本分為兩個部份，以此學習兩個獨立的true value $q(a) \forall a\in\mathcal{A}$的估測，稱為$Q_1(a), Q_2(a)$。這樣我們就可以其中一個估測，假設$Q_1$就是定義maximizing action $A^*=\arg\max_aQ_1(a)$，另一個$Q_2$用來估測它的value，也就是$Q_2(A^*) = Q_2(\arg\max_aQ_1(a))$。某種意義上，$\mathbb{E}[Q_2(A^*)]=q(A^*)$，因此，這個估測會是無偏的(unbiased)。我們可以兩個對調，然後重覆這兩個估測的過程，那就產生第二個無偏估測$Q_1(\arg\max_aQ_2(a))$。這個想法就是double learning。注意到，雖然我們學習兩個估測，但只會有一個估測會在每個樣本上更新；double learning同時也會有兩倍的記憶體需求，但並不會有額外的計算量。

double learning可以很自然的擴展到full MPDs。舉例來說，類似於Q-learning的double learning algorithm就稱為Double Q-learning，那Double Q-learning會把time step分割為2，每一個step都用擲硬幣來決定。那就會有兩種結果：
1. 正面，那就依下面公式更新
$$Q_1(S_t, A_t) \leftarrow Q_1(S_t, A_t) + \alpha[R_{t+1} + \gamma Q_2(S_{t+1}, \arg\max_a Q_1(S_{t+1}, a)) - Q_1(S_t, A_t)] \tag{6.10}$$
2. 反面，那就依上面的公式更新，只是把$Q_1$、$Q_2$角色對調，就換更新$Q_2$

這兩個approximate value functions是完全被對稱處理。behavior policy可以使用這兩個value function來做action-value的估測。舉例來說，Double Q-learning使用$\epsilon-$greedy policy可以基於這兩個action-value估測出來的值的平均(或加總)。

下面給出完整的Double Q-learning algorithm：

這也是Figure 6.5所用的演算法。在該範例中，double learning看起來是可以消除掉maxinmization bias帶來的危害。當然啦，還是有Sarsa、Expected Sarsa這兩個版本的double learning。
## 6.8 Games, Afterstates, and Other Special Cases
這本書試著找幾個比較通用的解決方案，不過還是會有一些特殊的情況只能用一些特定的演算法來處理。舉例來說，我們用比較通用的方法來學習action-value function，但是在Chapter 1中，我們演示一種TD method來玩井字遊戲(tic-tac-toe)，這學到的比較像是state-value function。不過如果你仔細看看會發現，它學到的既不是action-value function，也不是state-value function。傳統的state-value function是評估一個state在選擇一個action之後，這個state的value有多少，但是這個井字遊戲中的state-value function所評估的可能是agent選擇一步之後的局面。我們把這稱為afterstates，其value function稱為afterstate value functions。這種afterstates在一些我們知道環境動態性的初始的部份信息的情況下是非常有用的。像是在一些遊戲中，我們通常可以知道一個動作之後的影響。我們知道每個可能的棋步會產生什麼結果，但不知道我們的對手會如何回應。afterstate value functions可以很自然的利用這類知識來產生更有效的學習方法。

我們用井字遊戲來說說為什麼根據afterstate所設計的演算法會更有效的原因。傳統的action-value function會把位置(position)(當下的局面)跟動作(move)(你要下那一個地方)映射到一個估測值。但是有很多position-move pair都會產生相同的結果，如下範例：

上圖兩個狀況我們看的出來，左右各有不同的position-move pair，但是最終得到相同的afterposition，因此它們得到的value都會是一樣的。傳統的action-value function必需要分別的評估這兩個pair，但是afterstate value function可以立即評估這兩個pair是一樣的。任何關於上圖左的那個position-move pair學到的東西都可以立即的轉移(transfer)到右邊那個pair。

afterstates可以用在很多地方，不單單是遊戲。舉例來說，queuing tasks(排隊任務)，你的actions就是把客戶分配給servers，或是拒絕客戶、丟棄信息。這種情況下，事實上，actions是根據他們的立即影響來定義的，這完全是已知的。

還是那句話，這本書提出的都是比較通用的演算法與狀況。許多情況下，我們面臨的還是on-policy、off-policy之間的選擇。
## 6.9 Summary
這一章我們談了temporal-difference(TD) learning，也說了怎麼把它應用到強化學習上。一般來說，我們把會把問題切分為(1)預測問題(prediction problem)與(2)控制問題(control problem)。TD可以取代MC來解決預測問題。這兩種方法都可以利用Chapter 4提過的GPI(generalized policy iteration)來擴展至控制問題。想法上就是利用近似策略(approximate policy)與價值函數(value function)的交互讓雙方都往自己的最佳值(optimal value)去優化。

組成GPI的兩個過程之一驗動value function精確的為當下的策略(current policy)預測returns；這就是預測問題。另一個則驅動著策略(policy)依當下的價值函數(current value function)來做局部改進(如$\epsilon-$greedy)；這就是控制問題。當第一個過程依著經驗進行的時候，一個複雜的問題就產生了，那就是，到底還要要不要持續的探索下去。我們可以把TD的控制方法根據使用on-policy(Sarsa)還是off-policy(Q-learning)來做分類。Expected Sarsa則是屬於off-policy。另外還有第三種方法，不過這在Chapter 13才會談到，也就是actor-critic methods。

本章介紹的都是目前比較廣泛使用的強化學習方法。這可能是因為它們真的很簡單：它們可以以最小的計算資源來做online的應用，就可以得到與環境(Env)互動產生的經驗；它們幾乎可以用一個方程式就可以表示，而且你還只需要寫個小程式就可以實作它。接下來幾個章節，我們會擴展這些演算法，讓它們稍微複雜一些，但是會更強大。所有新的演算法都會原汁原味的保留這邊介紹過的本質：它們將能夠用相對較少的計算量在線(online)的處理經驗，而且它們將由TD error來驅動。這一章介紹的TD正確來說應該是one-step、tabular、model-free TD methods。後面我們會把它擴展到$n$-step的形式(與MC連結)，以及包含環境模式的形式(與planning、DP連結)。然後這本書的第二部份會把這一切擴展到函數近似(function approximation)，而不是表格式(連結深度學習與人工智慧)。

最後，雖然我們是在強化學習背景下討論TD，不過實際上TD是非常通用的。它們可以用來學習如何在動態系統中做出長期預測(long-term predictions)的方法。舉例來說，TD也許可以用於預測金融資料、壽命、選舉結果、天氣模式、動物行為、電力需求或客戶購買行為。只有在把TD單純的作為預測方法，脫離強化學習這個框架，人們才開始真正的瞭解它的理論特性。儘管如此，TD還是有很多潛在應用尚未被深入的研究。