Eligibility traces

1Averaging n-step returns

The n-step return keeps n rewards and then trusts the estimate of the state or pair it reaches:

This is the general form, for any way of estimating values: v(s, w) is the estimated value of state s given a vector of weights w.

• A table is the simplest case, with one weight per state, so that v(s, w) is just the table's entry V(s).
• With action values, the last term is the estimate of the pair (S_t+n, A_t+n) instead, as in n-step Sarsa.

Any n-step return is a valid target, and so is any average of them, as long as the weights are positive and add up to 1. Such an average keeps the error reduction property of the n-step returns, so it leads to sound learning too.

For example, an update toward half of a two-step return and half of a four-step return must wait four steps:

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, which sets the true values. The robot's table is still poor:

From the kitchen, the one-step return is 0 + 0.9 · 4 = 3.6, the two-step return 0.81 · 6 = 4.86, and the three-step return reaches the charger, 0.81 · 10 = 8.1. Half of the first and half of the last is 5.85.

2The λ-return

The λ-return averages every n-step return, with a weight that shrinks by λ at each extra step:

λ is between 0 and 1. The weights are 1 − λ for the one-step return, (1 − λ)λ for the two-step return, (1 − λ)λ² for the three-step return, and so on. They add up to 1, since 1 + λ + λ² + ⋯ = 1/(1 − λ); the factor 1 − λ is there to make them.

Once an n-step return reaches the end of the episode, it is the full return G_t, and so is every longer one. Gathering all their weights gives the form used for episodes:

The two ends of the range are the methods we already know. With λ = 1, the sum vanishes and Gλt = G_t: learning from it is Monte Carlo. With λ = 0, only the one-step return is left, Gλt = G_t:t+1: learning from it is one-step TD.

From the kitchen, two steps before the last, the λ-return has three terms. With λ = 0.5 their weights are 0.5, 0.25 and 0.25:

From 3.6 at λ = 0 to the full return, 8.1, at λ = 1, the target climbs with λ: the larger λ, the more the target relies on real rewards and the less on the poor estimates.

3Learning from the λ-return

The λ-return can replace the target of any update. Sarsa moved toward it becomes

and the same holds for state values. Gλt needs every reward until the end, so the simplest algorithm waits. The off-line λ-return algorithm changes nothing during the episode; when it ends, it makes one update per step, toward that step's λ-return:

The gradient ∇v says which weights produced the estimate of S_t, and how much. In a table it is 1 for the entry of S_t and 0 for every other, so the update is the familiar V(S_t) ← V(S_t) + α[Gλt − V(S_t)].

In the example with λ = 0.5 and α = 0.5, the table moves at the end of the episode:

How well does it learn? About as well as n-step TD at its best n, and slightly better at their best settings. As with n, an intermediate λ usually works best, and averaging over all horizons tends to be more robust than betting on a single n.

Forward and backward views

The λ-return is a forward view: each state's update looks forward in time. A backward view turns this around:

• Forward view: uses all the rewards and states that follow the state, so it updates only after the end, like Monte Carlo, and never in tasks without an end.
• Backward view: sends the current TD error back to the states or pairs visited recently, so every estimate is updated a little at every step, from information that already exists.

The next section shows why the two views can agree.

4The λ-return as a sum of TD errors

Take the TD error of Sarsa, with the table held fixed during the episode:

Write the λ-return out term by term, collect the rewards and the estimates step by step, and the estimates cancel in pairs. What is left is a discounted sum of the TD errors from time t on:

For the kitchen, the TD errors are δ₀ = 0 + 0.9 · 4 − 2 = 1.6, δ₁ = 0.9 · 6 − 4 = 1.4 and δ₂ = 10 − 6 = 4, and with γλ = 0.45 the sum is 1.6 + 0.45 · 1.4 + 0.2025 · 4 = 3.04, which is 5.04 − 2.

Now read the sum the other way. The TD error δ_k appears in the update of every pair visited before or at time k, with weight (γλ)^k−t, where k − t is how many steps ago that pair was visited. So there is no need to wait: as soon as δ_k is known, it can be passed back to every earlier pair.

5Sarsa(λ)

Sarsa(λ) keeps a trace z(s, a) for every pair, a short-term memory next to the long-term table Q. When a pair is visited its trace goes up by 1, and after every step all traces shrink by the factor γλ. Each step then moves every pair by its share of the current TD error:

A pair that was never visited, or visited long ago, has a trace near 0 and barely moves. With λ = 0 only the current pair has a trace, and Sarsa(λ) is one-step Sarsa. With λ = 1 the traces fade only by γ, and every pair of the episode shares each TD error as in Monte Carlo. The trace is also written e(s, a).

The algorithm

For a step size α, a discount γ, a trace decay λ and a small ε > 0, with Q(s, a) initialized arbitrarily except Q(terminal, ·) = 0, and for each episode:

1. Set every trace to 0: z(s, a) ← 0. Observe the first state S and choose A ε-greedily with respect to Q.
2. Take A, and observe R and S′. Choose A′ in S′ ε-greedily.
3. Compute the TD error δ ← R + γQ(S′, A′) − Q(S, A), and mark the pair just visited: z(S, A) ← z(S, A) + 1.
4. For every pair: Q(s, a) ← Q(s, a) + αδz(s, a), then z(s, a) ← γλz(s, a).
5. Set S ← S′ and A ← A′, and go back to step 2 until S is terminal.

Here is the hallway episode, with one action per room, go on, so that each Q plays the role of the room's value. λ = 0.5 and α = 0.5, so γλ = 0.45, and the table starts at 2, 4 and 6:

At t = 2, for example, the kitchen moves by 0.5 · 4 · 0.2025 = 0.405. The final table, 3.52, 5.6 and 8, is exactly what the off-line λ-return algorithm gives, because every TD error was computed from values that had not changed yet. In general they do change during the episode, since Sarsa(λ) updates as it goes, so a later TD error already reflects earlier updates. Sarsa(λ) is then not equivalent to the λ-return, but it is a close approximation, and it learns at every step instead of at the end.

Credit for a whole path

The traces spread each TD error over the whole recent path. Take a robot crossing an open room to its charger, with reward 0 on every move except +1 on arrival, all values 0 at first, γ = 1 and α = 0.5, and λ = 0.9. Its first episode wanders for nine moves. Every TD error is 0 until the last move, whose TD error is 1, and at that moment the trace of the move k steps before the end is 0.9^k.

The traces do not remember which moves were useful, only which were recent, so the detour in the middle of the path gets credit too. Later episodes sort this out, as paths that go straight collect their reward sooner.

The figure runs Sarsa(λ) on the cliff of the TD note, with λ = 0.9 as in the room, γ = 1, ε = 0.1 and a smaller step size, α = 0.1: a move visited again and again adds 1 to its trace each time, so its trace can grow well above 1, and a large α would overshoot.

• Each press is one line of the algorithm above.
• Every move with a trace is outlined in green, as strongly as its trace.
• The value the TD error uses is outlined in red.

The same mechanism works with any way of estimating values. The trace is then a vector z_t, the size of the weight vector: when a weight takes part in an estimate, its trace is bumped up, and then it fades. In a table, the weight that takes part is the entry of the pair just visited, which is the +1 of the algorithm above.

6Summary

The key ideas next to their NumPy equivalents. g_n holds the returns G_t:t+1 to G_t:T−1, g the full return, and q and z the table and the traces; λ is lam, since lambda is a Python keyword.