n-step bootstrapping

1The n-step return

Start with prediction: estimating v_π(s), the expected return from each state s when following a fixed policy π, from episodes that follow π. V is the table of estimates. The target of a Monte Carlo update is the full return, every reward until the episode ends at time T:

The target of a one-step TD update keeps the first reward and replaces the rest by the discounted estimate of the next state. It is the one-step return, G_t:t+1 = R_t+1 + γV_t(S_t+1). Keeping n rewards instead of one gives the n-step return:

In this return:

• the subscript t:t+n says that it starts at time t and uses rewards up to time t + n;
• the last term is the estimate of the state reached after n steps, standing in for all the rewards after it, and V_t+n−1 is the table as it stands when that return can first be computed;
• if the episode ends before n steps, when t + n ≥ T, there is nothing left to estimate, and the n-step return is the full return G_t.

An example. A robot drives home to its charger from the kitchen, through the hallway and the study. Reaching the charger gives +10, every other step 0, and γ = 0.9, so the true values are 8.1 for the kitchen, 9 for the hallway and 10 for the study. The robot's table is still poor: V(kitchen) = 2, V(hallway) = 4 and V(study) = 6. The returns from the kitchen, at t = 0:

Each extra step replaces part of an estimate with a real reward. With three steps the robot reaches the charger, so no estimate is left, and the return is the full return, 8.1.

Why a longer return is a better target

In the n-step return, the rewards are real, and the only estimate is multiplied by γⁿ. So its expectation is closer to the truth than the table, in the worst case by a factor γⁿ. This is the error reduction property:

In the example, the table's worst error is 6.1, at the kitchen:

This property is why every n-step TD method converges to the right values under the appropriate technical conditions: the one-step methods and Monte Carlo are the two ends of one family.

2n-step TD

The update moves the estimate of S_t toward its n-step return, and leaves every other state as it was. The indices record timing:

1. G_t:t+n needs R_t+n and S_t+n, which arrive at time t + n, so the state visited at time t is updated n steps later.
2. Nothing is updated during the first n − 1 steps of an episode.
3. To make up for it, the last n − 1 states are updated after the episode ends, with returns cut short by the end.

Here is the hallway episode with n = 2 and α = 0.5. At each time t, the state updated is the one from time τ = t − n + 1:

One-step TD on the same episode moves the kitchen only from 2 to 2.8 and the hallway from 4 to 4.7, since their targets, 3.6 and 5.4, rest on the poor estimates of the next state. With two steps, the reward of +10 reaches two states back instead of one, so a single episode carries it twice as far.

The algorithm

For a policy π to evaluate, a step size α in (0, 1] and a positive integer n, and for each episode:

1. Observe the first state S₀, and set T ← ∞, since the end is not known yet.
2. At each time t = 0, 1, 2, …, while t < T: take an action from π, and store the reward R_t+1 and the next state S_t+1. If S_t+1 is terminal, set T ← t + 1.
3. Set τ ← t − n + 1, the time whose state is updated now. If τ ≥ 0, set G ← Σmin(τ+n, T)i=τ+1γ^i−τ−1R_i, the discounted rewards; if τ + n < T, add γⁿV(S_τ+n); then update V(S_τ) ← V(S_τ) + α[G − V(S_τ)].
4. Stop when τ = T − 1, once the last state of the episode has been updated.

Only the last n + 1 states and rewards are ever needed, so they can be kept in a buffer indexed modulo n + 1.

The n-step error as a sum of TD errors

The one-step TD error measures how much one step changes an estimate:

If the table does not change along the way, the error of the n-step update is the discounted sum of the one-step errors of its n steps, because the estimates in between cancel:

In the example, δ₀ = 0 + 0.9 · 4 − 2 = 1.6 and δ₁ = 0 + 0.9 · 6 − 4 = 1.4, and 1.6 + 0.9 · 1.4 = 2.86, which is 4.86 − 2. With the whole episode this becomes the Monte Carlo error, and eligibility traces are built on the same sum.

Choosing n

Which n learns fastest depends on the task. Short returns lean on estimates, which are poor early on; long ones add up many random rewards, which vary; an intermediate n often does better than either end. A larger n also separates two time scales that one-step methods tie together: an agent may need to choose an action every fraction of a second, while a meaningful change of state takes many such steps, and bootstrapping works best across a change that matters.

3n-step Sarsa

For control, the same idea works with action values: replace states by state–action pairs, and act ε-greedily with respect to Q. The n-step return ends in the estimate of the pair reached after n steps,

for n ≥ 1 and 0 ≤ t < T − n, and it is the full return G_t when t + n ≥ T. The update is the same as for states:

With n = 1 this is one-step Sarsa, also called Sarsa(0). The gain shows most when rewards are rare. Take a robot crossing an open room to its charger, with reward 0 on every move except +1 on arrival, all action values 0 at first, γ = 1 and α = 0.5. Its first episode wanders for nine moves.

During the episode every target is 0, since the rewards are 0 and the table is still all zeros, until the returns start to reach the charger. One-step Sarsa's only such return is that of the last move, so one value rises, to 0.5; with n = 4, the returns of the last four moves reach the charger, and four values rise to 0.5. When rewards are rare, one episode of n-step Sarsa leaves a trail of up to n moves behind a reward, instead of one. Here the next episode that passes through those cells finds a trail four moves long.

The figure runs 4-step Sarsa on the cliff of the TD note, with the same settings, α = 0.5, γ = 1 and ε = 0.1. Its marks:

• a target's window of four moves is outlined in blue, from S_τ on;
• the move picked after it, whose estimate the target relies on, is outlined in red.

The first moves show how the updates wait for four rewards.

n-step Expected Sarsa

Expected Sarsa ends its return, instead, in the average value of the actions in S_t+n under the target policy π:

for t + n < T, and the full return otherwise. V_t(s), the expected approximate value of s, is 0 for a terminal state. The actions along the way are the ones actually taken; only the last step averages over all of them.

4Off-policy n-step learning

Off-policy learning learns the values of a target policy π from experience that follows a behavior policy b: often π is greedy with respect to Q and b is ε-greedy. One-step Q-learning needs no correction for the difference, but an n-step return does. Its rewards depend on the actions taken along the way, and b chose them, not π.

The correction weights the update by it:

• If π would never take one of those actions, the ratio is 0 and the return is ignored.
• If π takes them more often than b does, the ratio is above 1 and the return counts more, which makes up for how rarely b produces what π would do.
• When the two policies are the same, every factor is 1, and the updates below become the ones of sections 2 and 3.

For state values, the update of S_t is weighted by the ratio of the n actions A_t to A_t+n−1:

For action values, the ratio starts and ends one step later:

The pair being updated already contains its action A_t, so how likely b was to choose it does not matter: the value of (S_t, A_t) is about what happens after taking A_t. The actions after it, A_t+1 to A_t+n, are weighted, the last one included, since the return ends in its value Q(S_t+n, A_t+n).

For example, let π be greedy and b ε-greedy with ε = 0.2 and two actions, so that b takes the greedy action with probability 0.9. Each action contributes a factor, and the ratio is their product. In 3-step Sarsa:

Only stretches of greedy behavior teach about the greedy policy. A product of many ratios can swing widely, so these updates are noisier than on-policy ones.

5Summary

The key ideas next to their NumPy equivalents. The arrays s, a and r hold one episode, with r[i] for R_i, and v and q are the tables.