Chapter 7: n-step Bootstrapping
n-step TD methods span a spectrum with MC methods at one end and one-step TD methods at the other.
n-step TD Prediction
The target estimation of value functions in n-step TD is a combination of the first n steps' sample rewards and bootstrapping the value estimation of the sampled state after n steps, i.e., .)
Correspondingly, the update rule is ![V_{t+n}(S_t) = V_{t+n-1}(S_t) + \alpha [G_{t:t+n} - V_{t+n-1}(S_t)].](https://math.jianshu.com/math?formula=V_%7Bt%2Bn%7D(S_t)%20%3D%20V_%7Bt%2Bn-1%7D(S_t)%20%2B%20%5Calpha%20%5BG_%7Bt%3At%2Bn%7D%20-%20V_%7Bt%2Bn-1%7D(S_t)%5D.)
Note that only the value of 
changes at step 
, while the values of all the other states remain unchanged, i.e., %20%3D%20V_%7Bt%2Bn-1%7D(s))
for 
. An issue here is that the value estimation of )
may be updated long ago and does not reflect the true value of 
under the current policy 
in expectation. This is not covered in the RL book and I'm not sure if this will cause any problem in RL.
One-step TD (as introduced in the last chapter) can be seen as a special case of n-step TD when 
, i.e., .)
MC can be seen as the extreme of n-step TD in the opposite direction when 
equals to the episode length, i.e., 
.
n-step Sarsa
n-step Sarsa is a natural generalization of 1-step Sarsa with the target estimation as %2C)
and the corresponding update rule is ![Q_{t+n}(S_t, A_t) = Q_{t+n-1}(S_t, A_t) + \alpha [G_{t:t+n} - Q_{t+n-1}(S_t, A_t)].](https://math.jianshu.com/math?formula=Q_%7Bt%2Bn%7D(S_t%2C%20A_t)%20%3D%20Q_%7Bt%2Bn-1%7D(S_t%2C%20A_t)%20%2B%20%5Calpha%20%5BG_%7Bt%3At%2Bn%7D%20-%20Q_%7Bt%2Bn-1%7D(S_t%2C%20A_t)%5D.)
The RL book gives a gridworld example as shown below to illustrate the advantage of n-step Sarsa compared to one-step Sarsa. When the reward is sparse, n-step Sarsa can help speed up the reward propagation the earlier states.
n-step Off-policy Control
For n-step off-policy control, we need to take importance sampling into consideration, which leads to the update rule as follows: ![Q_{t+n}(S_t, A_t) = 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)],](https://math.jianshu.com/math?formula=Q_%7Bt%2Bn%7D(S_t%2C%20A_t)%20%3D%20Q_%7Bt%2Bn-1%7D(S_t%2C%20A_t)%20%2B%20%5Calpha%20%5Crho_%7Bt%2B1%3At%2Bn%7D%20%5BG_%7Bt%3At%2Bn%7D%20-%20Q_%7Bt%2Bn-1%7D(S_t%2C%20A_t)%5D%2C)
where %7D%20%5Cfrac%7B%5Cpi(A_k%7CS_k)%7D%7Bb(A_k%7CS_k)%7D)
. Note that the ratio starts from step 
because we do not have to care how likely we were to select the action 
; now that we have selected it we want to learn fully from what happens, with importance sampling only for subsequent actions. This also explains why one-step Q-learning do not have the ratio term, as 
for .
Off-policy Learning Without Importance Sampling: The n-step Tree Backup Algorithm
Importance sampling is required in Q-learning because it is a sample update method. So we need to multiply with the importance sampling ratio to make the update's expectation unbiased w.r.t. the target policy. Thus a natural way to avoid importance sampling is to perform expected update w.r.t. the target policy 
, i.e., the n-step tree backup algorithm.
In its simplest case with , tree backup is exactly expected Sarsa, i.e., %20Q_t(S_%7Bt%2B1%7D%2C%20a).)
For 
, we can further expand the corresponding )
term in the equation above to get a two-step target. Recursively, we can get the tree backup target as follows: %20Q_%7Bt%2Bn-1%7D(S_%7Bt%2B1%7D%2Ca)%20%2B%20%5Cgamma%20%5Cpi(A_%7Bt%2B1%7D%7CS_%7Bt%2B1%7D)%20G_%7Bt%2B1%3At%2Bn%7D.)
And the update rule without importance sampling is
