# Reinforcement Learning: An Introduction_Chapter 7 $n$-step Bootstrapping
###### 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)
[LyWangPX/Reinforcement-Learning-2nd-Edition-by-Sutton-Exercise-Solutions](https://github.com/LyWangPX/Reinforcement-Learning-2nd-Edition-by-Sutton-Exercise-Solutions)

這一章裡面，我們會統一前兩章提到的Monte Carlo(MC) methods與one-step temporal-difference(TD) methods。這邊開始要介紹的是$n-$step TD methods，這方法概括MC與one-step TD，這讓你可以依據需求從一種方法漂亮的轉身到另一個方法，以滿足特定任務的需求。$n-$step跨越MC與one-step TD，而通常最好的方法都是藏身在兩極端之間。

$n-$step TD methods的一個好處就是，它讓你從time step的無底深淵中爬出來。當你用one-step TD methods，相同的time step(都是one-step)決定了action變更的頻率，以及完成自舉(bootstrapping)的時間間隔。在許多應用程式中，我們會希望可以非常快速的更新action，這樣你才能夠把很多已經改變的事情列入考量，但是bootstrapping要做的好，除非是經過一段很長的時間，而且還要有明顯而且可識別的狀態變化。所以，當你用的是one-step TD的時候，這些時間間隔是相同的，你就必需要有所選擇(折衷)。$n-$step methods可以在多個steps上自舉(bootstrapping)，藉此讓我們擺脫single time step的困境。

這跟後面Chapter 12的eligibility traces也會有關，eligibility traces讓自舉(bootstrapping)這件事可以在多個時間間隔中同時發生。不過這邊先介紹$n-$step bootstrapping的概念，剩下的後面再說。

一樣的，我們先來談談prediction problem與control problem。也就是說我們要先來說說$n-$step對於一個fixed policy估測$v_\pi$有什麼幫助，然後再把它擴展到action values與control methods。
## 7.1 $n$-step TD Prediction
在MC、TD這兩個方法之間有什麼？我們來想像一個情況，用policy $\pi$採樣生成很多的episodes，然後估測$v_\pi$。MC更新每一個state的value是基於該state在整個被觀測到的reward sequence(這是一個序列，忘了可以回頭看first-visit、every-visit)從開始到該episode的結束。如果是one-step TD的話，那就是只基於下一個reward，將下一個state的value做為剩餘的rewards來做自舉更新。有那麼一種介於兩者之間的方法，它就基於中間數量的rewards來更新：比一個多，但又不拿全部。舉例來說，two-step就是基於前兩個rewards，估測的就是two steps之後的state的value。相同道理，你就可以有three-steps、fous-steps，以此類推。看下面Figure 7.1就給出相關$v_\pi$的$n-$step backup-diagrams，很明顯的one-step TD就是最左邊那個，最右邊的就是MC。

Figure 7.1：$n-$step的backup diagrams。從最左邊的one-step TD到最右邊的MC。

使用$n-$step updates仍然是TD methods，因為前面的估測仍然是基於後面估測的差值。只是現在後面的估測不是one step，而是$n$ steps，因此稱為$n-step$ TD methods。

嚴謹一點來看的話，我們把state $S_t$估測值的更新看成是state-reward sequence $S_t, R_{t+1}, S_{t+1}, R_{t+2}, ... , R_T, S_T$(這邊省略掉actions)的結果。如果是MC要做$v_\pi(S_t)$的更新，它會依著整個完整的return的方向來做更新：
$$G_t \dot{=} R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t_3} + \cdots + \gamma^{T-t-1}R_T$$

，其中$T$就是這個episode的最後一個time step。我們把$G_t$稱做是更新的目標(target)。在MC中更新的目標是return(就是$G_t$)，而在one-step的更新中，目標就第一個reward加上下一個state的折扣估測值，我們稱為one-step return：
$$G_{t:t+1} \dot{=} R_{t+1} + \gamma V_t(S_{t+1})$$

其中$V_t:\mathcal{S} \to \mathbb{R}$在這邊指的是在時間$t$其$v_\pi$的估測值。而在$G_{t:t+1}$的下標則是指出這是一種truncated return(截斷回報?)，這是從時間$t$一直到$t+1$的reward，然後用折扣估測值$\gamma V_t(S_{t+1})$來取代完整的return，$\gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots + \gamma^{T-t-1} R_{T}$。我們的重點就在這邊，如果是two-step，那它的想法跟one-step是類似的：
$$G_{t:t+2} \dot{=} R_{t+1} + \gamma R_{t+2} + \gamma^2 V_{t+1}(S_{t+2})$$

很明顯的，discounted estimate $\gamma^2 V_{t+1}(S_{t+2})$就是取代掉$\gamma^2 R_{t+3} + \gamma^3 R_{t+4} + \cdots + \gamma^{T-t-1}R_T$。同樣的，如果是$n-$step的話，其return $\forall n, t \text{ and } n\geq 1, 0\leq t < T-n$：
$$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}) \tag{7.1}$$

所有的$n-$step returns都可以被視為近似完整的回報(full return)，在$n$個steps之後截斷，然後其它遺失的部份則用估測值$V_{t+n-1}(S_{t+n})$來代替。如果$t+n \geq T$(就是time step超出這個eipsode的terminal time $T$)，那所有遺失的部份就通通視為0($V_{t+n-1}(S_{t+n})=0$)，也就是這種情況下$n-$step的return就會是$G_{t:t+n}\dot{=}G_t$。

要注意到，在$n>1$的$n-$step returns中，那涉及未來的rewards與states，你單純的從時間$t$到$t+1$的轉移是無法取得這些資訊的。在你看到$R_{t+n}$，並且計算$V_{t+n-1}$之前，沒有演算法可以使用$n-$state return，因此要到$t+n$你才能真正的計算。所以一個很自然的state-value learning algorithm來使用$n-$step returns的方法就是：
$$V_{t+n}(S_t)\dot{=}V_{t+n-1}(S_t) + \alpha[G_{t:t+n} - V_{t+n-1}(S_t)], 0 \leq t < T \tag{7.2}$$

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

而對其它狀態(state)的估測值是沒有改變的：$V_{t+n}(s) = V_{t+n-1}(s), \forall s \neq S_t$。這演算法就稱為$n-step$ TD。值得注意的是，在每個episode的第一個$n-1$ steps是沒有任何變動的。為了彌補這一點，會在episode的最後，也就是這個episode結束之後，在下一個episode開始之前，做相同數量的額外更新。下面給出完整的pseudocode：

$n-$step return用value function $V_{t+n-1}$來修正$R_{t+n}$之後所遺失的reward。那$n-$step returns有一個很重要的特性，在最壞的情況(in worst-state case)下，它們的期望值能夠保證$v_\pi$的估測會比$V_{t+n-1}$還要來的好。也就是說，預期的$n-$step returns的最糟的誤差會保證小於等於$\gamma^n$乘上$V_{t+n-1}$最糟的誤差，即$\forall{n \geq 1}$：
$$\max_s\vert \mathbb{E}_\pi[G_{t:t+n}\vert S_t=s] - v_\pi(s) \vert \leq \gamma^n \max_s \vert V_{t+n-1}(s)-v_\pi(s) \vert \tag{7.3}$$

:::warning
上面的部份，個人所理解應該還是跟Chapter 4提到的一樣，只是在DP說的是這次的迭代一定是比上一次還要好，而在TD談到的是time step。
:::

這稱為$n-$step returns的error reduction property(誤差降低特性?)。因為這個特性，我們可以證明，所有的$n-$step TD methods都可以在合適的技術條件下收斂到正確的預測。

:::info
Example 7.1: n-step TD Methods on the Random Walk

這邊把之前Example 6.2的範例改用$n-$step TD來處理。

假設，第一個episode就從$C$開始，然後往右經過$D, E$，成功的進到終止狀態，得到1的reward。現在讓我們回想一下，所有狀態的起始估測值皆為0.5，即$v(s)=0.5$。以這個經驗的結果來看，如果是one-step，那只有最後一個state估測值會變更，也就是$V(E)$，會往1的方向去增加。如果是two-step的話，那變更的就會是$V(D), V(E)$同時往1的方向增加。在$n>2$的情況下，所有經過的state都會以相同的大小來更新其value。

這樣子，我們應該怎麼選擇這個$n$呢？Figure 7.2給出這個簡單實際測試的結果，不過這邊實驗的是19個states，而不是Example 6.2中的5個states，左邊的reward是-1，然後所有的value的初始值皆為0，這章後續的範例也都是這樣的。呈現出的是$n-$step TD methods用區間值內不同的$n, \alpha$的測試結果。橫軸是$\alpha$，不同的線代表不同的$n$，然後縱軸是這19個states前10個episodes完整實驗100次取平均得到的預測值與真實值之間的均方誤差的平方根。可以明顯看的出來，$n$取中間值($n=4$)的效果最好，相對的說明$n-$step的效果會比TD還有MC還要來的好。

Figure 7.2: Performance of $n$-step TD methods as a function of $\alpha$, for various values of $n$, on a 19-state random walk task (Example 7.1).
:::

:::warning
The performance measure for each parameter setting, shown on the vertical axis, is the square-root of the average squared error between the predictions at the end of the episode for the 19 states and their true values, then averaged over the first 10 episodes and 100 repetitions of the whole experiment.
:::

## 7.2 $n$-step Sarsa
我們要怎麼讓$n$-step不止是用在預測(prediction)，還要可以用在控制(control)？這個Chapter就要來說說怎麼讓Sarsa結合$n$-step然後直接的產生一個on-policy TD control method，這樣的方法稱為$n$-step Sarsa，至於Chapter 6提到的自然的就是one-step Sarsa或是Sarsa(0)。

很簡單，就是把state改成state-action pair，然後用$\epsilon-$greedy policy。其backup diagrams如下：
Figure 7.3: state-action values的$n-$step methods系列的backup diagrams。這區間從Sarsa(0)的one-step update一路到Monte Carlo的up-until-termination update。這中間就是$n-$step updates，基於$n$ steps的real rewards以及第$n$個next state-action pair的估測值，這些都有適當的折扣。最右邊那個就是$n-$step Expected Sarsa的backup diagram。

我們來重新定義一下它的更新目標：
$$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}), n \geq 1, 0 \leq t < T-n, \tag{7.4}$$

一樣的，如果$t+n \geq T$，那$G_{t:t+n}=G_t$。很自然的，就會變成：
$$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)], 0\leq t < T \tag{7.5}$$

所有其它states的values都維持不變：$Q_{t+n}(s, a) = Q_{t+n-1}(s, a)$，對所有$s \neq S_t \text{ or } a \neq A_t$的$s, a$都是如此 ，這就是$n-step$ Sarsa，相關pseudocode如下圖所示：

相關比較說明為什麼它可以學習的比one-step還要快可見下圖：
Figure 7.4: 這個gridworld範例說明著為什麼$n-$step可以加速學習policy的原因。第一個圖說明著在單一個episode中agent選擇的路徑，最終結束在一個較高報酬(reward)的地方，也就是標記$G$的那個點。這個範例中，所有的values都初始化為0，所有的過程中的reward都是0，只要最後停在$G$的時候才會得到一個正值。 另外兩張圖則是分別說明利用one-step Sarsa與$n-$step Sarsa的action value所增強的結果。看的出來，one-step只有對最後一個action有增強的效果，但是$n-$step則是對最後$n$個action都有效果，這讓你可以從一個episode中學習到較多的東西。

那Expected Sarsa呢？Expected Sarsa的$n-$step就如Figure 7.3的最右邊那張圖所示。它包含sample actions與states的linear string，就像$n-$step Sarsa一樣，除了最後一個元素是所有可能的action的分支(branch)，依著$\pi$的機率來做加權。我們可以把它寫成跟$n-$step Sarsa一樣的方程式，除了$n-$step的return要重新定義：
$$G_{t:t+n} \dot{=} R_{t+1} + \cdots + \gamma^{n-1}R_{t+n} + \gamma^n\bar{V}_{t+n-1}(S_{t+n}), t+n<T \tag{7.7}$$

，一樣的，如果$t+n\geq T$，那$G_{t:t+n}=G_t$，其中$\bar{V}_t(s)$指的就是state $s$的expected approximate value(期望近似值?)，按著target policy在時間$t$的時候估測的action values：
$$\bar{V}_t(s) \dot{=} \sum_a\pi(a\vert s)Q_t(s, a), \forall s \in \mathcal{S} \tag{7.8}$$

這(expected approximate value)在後面很常用到，如果$s$是終止狀態，那得到的就是0。
## 7.3 $n$-step Off-policy Learning
先回想一下，off-policy learning就是從$\pi$學value function，但是你是依著另一個policy $b$在做事的。通常，$\pi$是greedy policy(對當下的action-value function的估測值greedy)，然後$b$是一個充滿探索性的policy，像是$\epsilon-$greedy。為了能夠從$b$得到的資料，我們必需要將兩個policy的不同處列入考量，使用它們對應的action的相對機率(詳細可以參考[Section 5.5](https://hackmd.io/@shaoeChen/rJ46Bsqu_#55-Off-policy-Prediction-via-Importance-Sampling))。在$n-$step methods中，returns是由$n$個steps所構建而成，因此我們感興趣的就是這$n$個actions的相對機率。舉例來說，弄一個off-policy的$n-step$TD，在時間$t$的更新(時間上是$t+n$)，可以用$\rho_{t:t+n-1}$來加權：
$$V_{t+n}(S_t) \dot{=} V_{t+n-1}(S_t) + \alpha \rho_{t:t+n-1}[G_{t:t+n} - V_{t+n-1}(S_t)], 0 \leq t < T \tag{7.9}$$

其中$\rho_{t:t+n-1}$就稱為[重要性抽樣比率](http://terms.naer.edu.tw/detail/2117615/)，也就是兩個policy從$A_t$到$A_{t+n-1}$所採取的actions的相對機率(方程式5.3)：
$$\rho_{t:h} \dot{=} \prod_{k=t}^{\min(h,T-1)} \dfrac{\pi(A_k\vert S_k)}{b(A_k \vert S_k)} \tag{7.10}$$

:::warning
$$\rho_{t:T-1}\dot{=}\dfrac{\prod^{T-1}_{k=t}\pi(A_k\vert S_k)p(S_{k+1}\vert S_k, A_k)}{\prod^{T-1}_{k=t}b(A_k\vert S_k)p(S_{k+1}\vert S_k,A_k)}=\prod_{T-1}^{k=t}\dfrac{\pi(A_k\vert S_k)}{b(A_k\vert S_k)}\tag{5.3}$$
:::

舉例來說，如果有任一個action從來沒有被$\pi$選中($\pi(A_k\vert S_k)=0$)，那麼$n-$step的return的權重就會是0，而且被完全的忽略。另一方面，好死不死的有一個action被$\pi$選中的機率比被$b$選中還要來高很多，這樣就會增加對應的return的權重。這是有意義的，因為這個action是$\pi$的特性(這也是我們要學習的部份)，只是剛好很少被$b$選中，因此很少出現在資料中。為了彌補這一點，我們就必需在這個action發生的時候拉高它的權重。要注意到的是，如果兩個policies真的是完全一樣的(on-policy的情況)，那重要性抽樣比率就永遠都會是1。下面我們直接寫出把$n-$step Sarsa用off-policy呈現的方式，$\forall 0 \leq t < T$：
$$Q_{t+n}(S_t, A_t) \dot{=} Q_{t+n-1}(S_t, A_t) + \alpha\rho_{t+1:t+n}[G_{t:t+n} - Q_{t+n-1}(S_t, A_t)] \tag{7.11}$$

很明顯的，這邊的重要性抽樣比率比起公式7.9的$n-$step TD，在開始跟結束都晚了一步(one step)，這是因為這邊我們更新的是state-action pair。我們並不在意這些action被選中的機率有多少；既然選中這個action了，我們希望可以從已發生的事情中充份學習，而這個學習也只會針對後續的actions計算出的重要性抽樣。下面給出pseudocode：

off-policy的$n$-step Expected Sarsa用的更新規則跟上面給出的$n-$step Sarsa是一樣的，唯一的差別就是重要性抽樣比率少一個因子。也就是用$\rho_{t+1:t+n-1}$而不是$\rho_{t+1:t+n}$，當然啦，它用就會是Expected Sarsa的$n-$step return，也就是公式7.7。這是因為Expected Sarsa會在最後一個state把所有可能的actions都列入考量；實際採用的是那一個action在這邊(Expected Sarsa)就完全沒有影響，也不需要去修正它。

:::warning
$$G_{t:t+n} \dot{=} R_{t+1} + \cdots + \gamma^{n-1}R_{t+n} + \gamma^n\bar{V}_{t+n-1}(S_{t+n}), t+n<T \tag{7.7}$$
:::

## 7.4 \*Per-decision Methods with Control Variates
前面討論的multi-step off-policy methods雖然簡潔有力，但可能，，，不是最有效率的。有一種更高端的方法，用著per-decision importance sampling的概念(如[Section 5.9](https://hackmd.io/@shaoeChen/rJ46Bsqu_#59-Per-decision-Importance-Sampling))。為了瞭解這個方法，我們先來看一下最原始的$n-$step return，也就是公式7.1的部份，

:::warning
$$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}) \tag{7.1}$$
:::

我們可以把所有的returns都寫成遞迴模式。對所有結束於$h$的$n$ steps，它的$n-$step return可以寫成下面這樣：
$$G_{t:h}=R_{t+1} + \gamma G_{t+1:h}, t<h<T, \tag{7.12}$$

其中$G_{h:h}=V_{h-1}(S_h)$，這個return是在時間$t$的時候用的，先前定義為$t+n$。我們現在來考慮一個behavior policy $b$跟target policy $\pi$不同所造成的影響。所有產生的經驗，都包含第一個reward $R_{t+1}$以及下一個state $S_{t+1}$，都必需要用時間$t$的重要性抽樣比例，$\rho_t\dfrac{\pi(A_t\vert S_t)}{b(A_t\vert S_t)}$，來做加權。也許有人會覺得，就把上面方程式的右邊做個簡單加權不就好了，但我們可以有更好的作法。假設有個action從來沒有在時間$t$被$\pi$選中過，那$\rho_t=0$。那這個所謂的簡單加權就會造成這個$n-$step的return為0，如果它被當做是target的時候就可能會造成很高的variance。所以厚，在這種更高端的方法中，$n-$step結束於horizon $h$的return，其off-policy的定義為：
$$G_{t:h}\dot{=}\rho_t(R_{t+1}+\gamma G_{t+1:h}) + (1 - \rho_t)V_{h-1}(S_t), t<h<T, \tag{7.13}$$

一樣，$G_{h:h}\dot{=}V_{h-1}(S_h)$。

這個高端的方法阿，如果$\rho_t=0$，target並不會變成0，也不會導致估測值收縮(shrink)，NO，並不會，target只會跟估測值一樣，不會引起變化。然後，公式7.13額外的項目稱為control variate([控制變量](http://terms.naer.edu.tw/detail/2113684/))。值得注意的是，這個控制變量並不會改變預期的更新；重要性抽樣比例的期望值是1([Section 5.9](https://hackmd.io/@shaoeChen/rJ46Bsqu_#59-Per-decision-Importance-Sampling))，而且它跟估測值是不相關的，因此，控制變量的期望值為0。還要注意一下那個off-policy的定義(7.13)，這個定義是上面公式7.1的一種嚴格範化(strict generalization)，所以如果你的$\rho_t=1$，7.1跟7.13就是相同的。

:::warning
$$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}) \tag{7.1}$$
:::

對於一般比較常見的$n-$step methods，通常是拿$n-$step TD update(7.2)來結合7.13，這除了崁入在return當中的部份之外，並沒有明顯的重要性抽樣比例。

:::warning
$$V_{t+n}(S_t)\dot{=}V_{t+n-1}(S_t) + \alpha[G_{t:t+n} - V_{t+n-1}(S_t)], 0 \leq t < T \tag{7.2}$$
:::

對於action values，$n-$step return的off-policy定義有一些些的不同，因為第一個action在重要性抽樣中是不起作用的。第一個action它是一個學習中的action；在target policy下，第一個action有沒有可能或者甚至不可能被選中都無所謂，因為它已經被選中了，現在對於後續的reward與state要給全單位權重(full unit weight)。重要性抽樣僅適用於後續的操作。

對action values來說，$n-$step on-policy return是結束在horizon $h$，它的期望值(7.7)也可以寫成像(7.12)的那種遞迴形式，除了action values的這個遞迴式是結束在$G_{h:h}\dot{=}\bar{V}_{h-1}(S_h)$(如7.8)。off-policy的控制變量形式如下：
$$
\begin{align}
G_{t:h} &\dot{=} R_{t+1} + \gamma(\rho_{t+1} G_{t+1:h} + \bar{V}_{h-1}(S_{t+1}) - \rho_{t+1}Q_{h-1}(S_{t+1}, A_{t+1})), \\
&= R_{t+1} + \gamma \rho_{t+1}(G_{t+1:h} - Q_{h-1}(S_{t+1}, A_{t+1})) + \gamma\bar{V}_{h-1}(S_{t+1}), t<h\leq T\tag{7.14}
\end{align}
$$

這會有兩種情況：
1. $h<T$，那遞迴會結束於$G_{h:h}\dot{=}Q_{h-1}(S_h, A_h)$
2. $h \geq T$，那遞迴會結束於$G_{T-1:h}\dot{=}R_T$

結合7.5之後得到的這個演算法就類似Expected Sarsa。

這陣子(含Chapter 5)所用的重要性抽樣雖然讓我們能夠使用off-policy learning，但也為更新過程中帶來比較高的方差，這迫使我們使用較小的step-size，但也因此讓學習變慢了。off-policy訓練的會比on-policy來的慢，這可能是必然的，畢竟資料跟學習的部份相關性較小。不過厚，這是有可能改進的。控制變量(control variates)是一種減少方差(variance)的方法。另外還有一種稱為Autostep method(Mahmood, Sutton, Degris and Pilarski, 2012)可以根據觀察到的方差快速的調整step-size。還有一種invariant updates(Karampatziakis and Langford, 2010)，這方法也被Tian應用到TD上。Mahmood (2017; Mahmood and Sutton, 2015)嘛妹賣。下一章就來談談沒有用重要性抽樣的off-policy learning method。

## 7.5 Off-policy Learning Without Importance Sampling: The $n$-step Tree Backup Algorithm

這一章我們要來談談tree-backup algorithm，它的一個概念如下3-step tree-backup backup diagram所示：

沿著中心向下，你看到的是三個sample states與rewards，以及兩個sample actions。這代表的是在初始的state-action pair，$S_t, A_t$之後發生的事件，它們是隨機變量。掛在每一個state的左右兩邊的是沒有選擇到的actions，不過對於最後一個state，我們會把所有的actions都視為還沒有被選擇。因為我們並沒有關於未選擇到的actions的樣本資料，所以我們會自舉(bootstrap)，然後用它們的估測值來做為它們的更新目標。這有一咪咪的擴展了backup diagram的概念。

目前為止，我們一直把這個diagram最上面那個節點(node)的估測值的更新往著一個目標去走，這個目標(target)就是結合沿途的rewards(適當地折扣)與底部結節的估測值。在tree-backup update中，target包含所有這些東西"加上"每一層掛兩測的action nodes的估測值。這就是為什麼被稱為tree-backup update原因；它的更新是來自於整個tree的action values的估測值。

更精確的說，這更新(update)是來自於tree的leaf nodes(葉節點)的action values的估測值。內部的action nodes就相對於實際被選中的action，所以不參與這個update。每一個leaf node對target的貢獻，其權重跟它在$\pi$這個target policy下的發生機率是成正比的。因此，每一個first-level的action $a$貢獻的權重為$\pi(a\vert S_{t+1})$，但如果是真的被選中的那個action，也就是$A_{t+1}$的話，那它是完全沒有任何貢獻的。它的機率$\pi(A_{t+1}\vert S_{t+1})$，是用來給所有second-level action values做加權的。因此，每一個沒有被選中的second-level action的貢獻權重就會是$\pi(A_{t+1}\vert S_{t+1})\pi(a' \vert S_{t+2})$。很明顯的third-level action的貢獻權重就會是$\pi(A_{t+1} \vert S_{t+1}) \pi(A_{t+2} \vert S_{t+2}) \pi(a''\vert S_{t+s})$，以此類推。這就好比是每一個指向action node的箭頭都是由該target policy下被選中的機率來做加權，如果action下面長tree，那這個權重就會用到這個tree內的所有leaf nodes。

我們可以把一個3-step tree-backup update想成是6個half-steps的組成，從一個action到後續的state的sample half-steps之間的交替，以及expected half-steps考慮了來自該state在使用該policy下的所有可能的action發生的機率。

進入重頭戲，我們來寫下$n-$step tree-backup algorithm的方程式。one-step return(target)跟Expected Sarsa是一樣的，對於$t<T-1$的情況：
$$G_{t:t+1}\dot{=}R_{t+1} + \gamma \sum_a \pi(a\vert S_{t+1})Q_t(S_{t+1}, a) \tag{7.15}$$

，然後，two-step tree-backup return，對於$t<T-2$就是：
$$
\begin{align}
G_{t:t+2} & \dot{=} R_{t+1} + \gamma \sum_{a\neq A_{t+1}} \pi(a\vert S_{t+1})Q_{t+1}(S_{t+1}, a) + \gamma \pi(A_{t+1 }\vert S_{t+1})(R_{t+2} + \gamma \sum_a \pi(a\vert S_{t+2})Q_{t+1}(S_{t+2}, a)) \\
&= R_{t+1}+\gamma\sum_{a\neq A_{t+1}}\pi(a\vert S_{t+1})Q_{t+1}(S_{t+1}, a) + \gamma\pi(A_{t+1}\vert S_{t+1})G_{t+1:t+2}
\end{align}
$$

上面公式的第二段說明了tree-backup $n-$step return的遞迴定義，對於
$t<T-1, n\geq 2$，其
$$G_{t:t+n}\dot{=} R_{t+1} + \gamma \sum_{a\neq A_{t+1}}\pi(a\vert S_{t+1})Q_{t+n-1}(S_{t+1}, a) + \gamma \pi(A_{t+1} \vert S_{t+1})G_{t+1:t+n} \tag{7.16}$$

除了$G_{T-1:t+n}\dot{=}R_T$，剩下的只要$n=1$都可以用7.15來處理。

這個target你就可以拿來做$n-$step Sarsa action value的更新，對於$0 \leq t < T$：
$$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)]$$

所有其它的state-action pairs的value則是維持不變：對所有$s\neq S_t$或是$a\neq A_t$的$s, a$，其$Q_{t+n}(s, a)=Q_{t+n-1}(s, a)$。相關的pseudocode如下：

## 7.6 \*A Unifying Algorithm: $n$-step $Q(\sigma)$
目前為止我們已經看了三種不同的action-value algorithms，分別與Figure 7.5中所給出的前三個backup diagram相對應：
1. $n-$step Sarsa有著所有的樣本轉移
2. tree-back有著所有state-to-action轉移的完整分枝資訊，不需要採樣
3. $n-$step Expected Sarsa有所有樣本轉移，除了最後一個state-to-action，這是有期望值的完整分枝

這些演算法能有多大程度上的統一?看看下面的Figure 7.5：

Figure 7.5: The backup diagrams of the three kinds of $n$-step action-value updates considered so far in this chapter (4-step case) plus the backup diagram of a fourth kind of update that unifies them all. The label ‘$\rho$’ indicates half transitions on which importance sampling is required in the o↵-policy case. The fourth kind of update unifies all the others by choosing on a state-by-state basis whether to sample ($\sigma_t=1$) or not ($\sigma_t=0$).

我們的想法是像Figure 7.5中的第二個backup diagram。這個想法就是，我們可以決定是要像Sarsa一樣的把採取的action做為樣本，還是像tree-backup update一樣考慮所有action的期望。然後，我們選擇永遠採樣，那得到的當然就是Sarsa，反之，如果這輩子我就是不採樣，那得到的就是tree-back algorithm。Expected Sarsa則是最後一個step除外的所有steps都做採樣。
想當然，還是會有其它的可能，就像Figure 7.5最後一個圖那樣子，這也是一種可能。為了進一步的增加可能性，我們可以考慮在採樣跟期望之間的連續變化。假設$\sigma_t \in [0, 1]$表示在step $t$的採樣程度(degree)，當$\sigma=1$則表示完全採樣，而當$\sigma=0$則表示單純的期望(expectation)而不採樣。我們可以把隨機變數$\sigma_t$設置成一個state、action，或是state-action pair在時間$t$時候的函數。這樣的作法，我們把它稱為$n-$step $Q(\sigma)$。

現在讓我們來弄一下$n-$step $Q(\sigma)$的方程式。首先我們寫下tree-backup $n-$step return在horizon $h=t+n$的方程式(7.16)還有方程式(7.8)的expected approximate value $\bar{V}$：
$$
\begin{align}
G_{t:h} &= R_{t+1} + \gamma \sum_{a\neq A_{t+1}} \pi(a\vert S_{t+1})Q_{h-1}(S_{t+1}, a) + \gamma \pi(A_{t+1} \vert S_{t+1}) G_{t+1:h} \\
&= R_{t+1} + \gamma \bar{V}_{h-1}(S_{t+1}) - \gamma\pi(A_{t+1}\vert S_{t+1})Q_{h-1}(S_{t+1}, A_{t+1}) + \gamma\pi(A_{t+1} \vert S_{t+1})G_{t+1:h} \\
&= R_{t+1} + \gamma\pi(A_{t+1} \vert S_{t+1})\left(G_{t+1:h} - Q_{h-1}\left(S_{t+1}, A_{t+1}\right)\right) + \gamma\bar{V}_{h-1}(S_{t+1})
\end{align}
$$

經過上面這樣一寫之後會發現，真的長的很像帶控制變量(7.14)的Sarsa的$n-$step return，除了用action probability $\pi(A_{t+1}\vert S_{t+1})$來代替重要性抽樣比例$\rho_{t+1}$。對於$Q(\sigma)$，我們在兩種情況做一些線性划動(slide linearly)，對$t<h\leq T$的情況：
$$G_{t:h}\dot{=}R_{t+1} + \gamma(\sigma_{t+1}\rho_{t+1}+ (1-\sigma_{t+1})\pi(A_{t+1}\vert S_{t+1}))(G_{t+1:h}-Q_{h-1}(S_{t+1}, A_{t+1})) + \gamma \bar{V}_{h-1}(S_{t+1}) \tag{7.17}$$。

這個遞迴式會在兩種情況停止：
1. $h<T$，那這個遞迴式就會在$G_{h:h}\dot{=}Q_{h-1}(S_h,A_h)$停止，
2. $h=T$，那這個遞迴式就會在$G_{T-1:T}\dot{=}R_T$

然後我們就可以用方程式(7.5)這個沒有重要性抽樣的$n-$step Sarsa來取代(7.11)。完整的演算法如下：

## 7.7 Summary
這一章我們詳細的介紹了一系列的TD learning methods，這介於one-step TD跟MC這兩個方法。這方法涉及兩個極端中間的自舉(bootstrapping)，也就是$n-$steps。

我們關注$n-$step，這方法往前看了$n$個reweards、states、actions。下圖兩個4-step backup diagrams總結了大部份的說明：

:::warning
往前指的就是往下$n$個time step去看
:::

圖中state-value的更新是用於使用重要性抽樣的$n-$step TD，而action-value的更新則是用於$n-$step $Q(\sigma)$，這概括了Expected Sarsa與Q-learning。所有的$n-$step methods都涉及了在更新之前的$n$個time steps的延遲，也只有這樣才能知道未來所應該知道的事情。另一個缺點就是說，跟之前的方法(one_step)相比，$n-$step在每一個time step都涉及更多的計算，而且需要更多的記憶體去記下states、actions、rewards，有時候還有其它的變數要記錄。不過最終我們會在Chapter 12看到multi-step TD methods怎麼樣用eligibility traces來實現最小化記憶體與計算複雜度。不過不管如何對比於one-step，總是會有一些額外的計算就是。但這樣的付出是值得的，這讓我們可以避開one-step帶來的問題。

雖然$n$-step methods相較於eligibility traces是較為複雜，但是概念上卻是比較清晰的。我們試著在$n-$step情況下開發兩種off-policy learning的方法來利用這一個優點。一種是基於重要性抽樣，概念簡單，但是會導致很高的方差(high variance)。如果target與behavior policies非常的不同，那它可能需要一些新的演算法才有辦法真的拿來用。另一種是基於tree-backup updates，這是一種從Q-learning到具有隨機目標策略(stochastic target policies)的multi-step情境的延申應用(原文是說natural extension)。它並不涉及重要性抽樣，還是要再說一次，如果target與behavior policies真的是實質上的不同，那即使你設置的$n$再大，它的自舉(bootstrapping)最多還是只少跨過少少的幾個steps。