TD prediction and Sarsa

1Learning from the next step

Constant-α Monte Carlo moves the estimate of each visited state toward the return that followed it:

but G_t is known only when the episode ends. The simplest TD method, TD(0) or one-step TD, uses instead the reward R_t+1 and the estimate of the next state, both available at time t + 1:

Why is that a sensible target? The return of one step is the next reward plus the discounted return of the next step, G_t = R_t+1 + γG_t+1, so the value of a state can be written in two ways:

The three methods use the two forms differently:

TD does both at once: like dynamic programming, it bootstraps, and like Monte Carlo, it needs no model.

The algorithm

Tabular TD(0), for a policy π and a step size α in (0, 1]:

1. Start with any V(s), except V(terminal) = 0.
2. At the start of each episode, observe the first state S.
3. Take the action π gives for S, and observe the reward R and the next state S′.
4. Update V(S) ← V(S) + α[R + γV(S′) − V(S)].
5. Set S ← S′, and go back to step 3 until S is terminal.

The figure runs TD(0) on the same 30 episodes as the first figure of the previous note: the random moves are the same, and only the learning differs. γ = 0.9 again, α = 0.5, and every estimate starts at 0. Every move is now followed by its TD error, whose target uses the estimate outlined in red, and by the update.

2One trip, step by step

Say the robot's estimates are V(kitchen) = −5, V(hallway) = −4 and V(study) = −2, averages of two lucky trips; the true values of its wandering are −9, −8 and −5. Its next trip goes kitchen, hallway, kitchen, hallway, study, charger. With γ = 1 and α = 0.5, TD(0) makes one update per move:

At t = 1, stepping back into the kitchen tells the robot that the hallway was worse than it thought, and TD lowers the hallway's estimate on the spot. At t = 3 the robot reaches the study from the hallway, which is better news, and the estimate goes back up. Constant-α Monte Carlo waits until the charger, then moves each visit's estimate toward its return:

The Monte Carlo error as a sum of TD errors

If the table does not change during the episode, the error of the Monte Carlo update is the discounted sum of the TD errors along the rest of the episode, because the estimates in between cancel in pairs:

With the table held at −5, −4 and −2, the TD errors of this trip are 0, −2, 0, 1 and 1, which add up to 0: exactly G₀ − V(kitchen) = −5 − (−5). TD(0) changes the table as it goes, so the identity then holds only approximately; the third TD error above is −1 instead of 0 because the hallway had already been updated.

3Why learn from a guess?

Compared with dynamic programming, TD needs no model: no probabilities of rewards and next states, only experience. Compared with Monte Carlo, it learns online, one step at a time. That matters:

• when episodes are long;
• when the task never ends;
• when some policies would make an episode last forever: Monte Carlo can learn nothing from an episode that never ends, while TD notices during the episode that things are going badly.

It is also sound. For a fixed policy π, TD(0) converges to v_π. It does so in the mean for a small enough constant α, and with probability 1 if α shrinks in the usual way, with a sum that grows without limit and a sum of squares that stays finite. Which method learns faster has not been proved in general, but in practice TD usually beats constant-α Monte Carlo on tasks with randomness.

4Batch updating: what each method converges to

With a fixed amount of experience, say a few episodes, one can replay it until the estimates stop changing. In batch updating, the increments of every step of every episode are computed and added up, the table changes once by their sum, and the whole batch is processed again, until it converges.

With a small enough α, batch TD(0) converges to a single answer that does not depend on α, and so does batch Monte Carlo, but the two answers differ.

An example. The charger is sometimes taken by another robot. Reaching it from the study gives +1 if it is free and 0 if it is taken, and moving from the hallway to the study gives −1; γ = 1. Five episodes were recorded:

Both methods give the study the average of its five returns, 0, 1, 1, 1 and 0: V(study) = 0.6. They disagree about the hallway:

If the process is Markov, the TD answer should predict future returns better. The one bad outcome after the hallway was the charger's doing, and five visits to the study say more about the charger than one.

This helps explain why TD tends to learn faster. Computing the certainty-equivalence estimate directly is rarely practical: with n states, the model alone can need memory of order n², and solving it about n³ steps. TD approaches the same answer with memory of order n, and online TD, which does not replay, still moves roughly toward it.

The algorithm

Batch TD(0), for a batch of episodes and a small step size α:

1. Start with any V(s), except V(terminal) = 0.
2. With V held fixed, go through every step of every episode in the batch and compute its TD error, δ_t = R_t+1 + γV(S_t+1) − V(S_t).
3. Change each estimate once, by α times the sum of the TD errors of the steps that start in its state: V(s) ← V(s) + α Σ δ_t, over the steps with S_t = s.
4. Go back to step 2 until V stops changing.

Batch Monte Carlo is the same with G_t − V(S_t) in place of δ_t, at every step, as in constant-α Monte Carlo.

The figure runs both on the 702 moves of the first figure's 30 episodes, with every estimate at 0 and α = 0.005, small because each estimate moves by α times a sum: 176 of the moves start in A1.

• The agent stays in A1, since the batch is only replayed.
• Each press is one line of the steps above; the estimates a pass changes are outlined in green, and those that targets borrow in red, as in the first figure.
• The buttons above the grid switch between batch TD(0) and batch Monte Carlo.

5Sarsa: TD for control

To learn to act without a model, TD learns action values, and the policy improves along the way: evaluate with TD, act ε-greedily with respect to the current estimates, and repeat, as in generalized policy iteration. The update is the same as TD(0), from one state–action pair to the next:

It is made after every transition from a nonterminal state, with Q(terminal, ·) = 0. It uses the five quantities S_t, A_t, R_t+1, S_t+1 and A_t+1, which give the method its name. Sarsa is on-policy: A_t+1 is the action the policy actually takes next, so Sarsa learns the values of the policy it follows, exploration included.

Sarsa converges with probability 1 to an optimal policy and its action values if every pair keeps being visited, the step sizes shrink in the usual way, and the policy becomes greedy in the limit, for example ε-greedy with ε = 1/t.

The algorithm

For a step size α in (0, 1] and a small ε > 0, with Q(s, a) arbitrary except Q(terminal, ·) = 0:

1. At the start of each episode, observe S, and choose A ε-greedily with respect to Q.
2. Take A, and observe R and S′. Choose A′ in S′ ε-greedily with respect to Q.
3. Update Q(S, A) ← Q(S, A) + α[R + γQ(S′, A′) − Q(S, A)].
4. Set S ← S′ and A ← A′, and go back to step 2 until S is terminal.

Learning within the episode is what lets Sarsa escape a policy that would never finish. Suppose all of the robot's action values start at 0 and, breaking the tie, its policy sends it from the hallway back to the kitchen, from where the only move is back to the hallway. Followed greedily, that policy shuttles forever, and a Monte Carlo method would wait forever for a return. With Sarsa, α = 0.5 and γ = 1:

1. The first time the robot goes back to the kitchen, Q(hallway, kitchen) drops to 0.5(−1 + 0 − 0) = −0.5.
2. That is below the 0 of the untried move to the study.
3. So the next time it is in the hallway, it heads for the study.

To watch Sarsa learn, take a larger grid than the cookie grid:

• 6 cells wide and 4 tall, from A1 at the bottom left to F4 at the top right;
• the agent starts in A1, and an episode ends when it reaches the goal, F1, at the bottom right;
• every move gives −1, and between start and goal, along the bottom edge, runs a cliff: a step into it gives −100 and sends the agent back to the start;
• the shortest route runs right along the edge, in 7 moves.

The figure runs Sarsa there with α = 0.5, γ = 1 and ε = 0.1, so that in each cell the greedy move has probability 0.925 and each other move 0.025. Each cell holds the values of its four moves again, as in the Monte Carlo control figure. Here every move costs, so the values are negative, and the heatmap shades them a faint coral, deeper the more negative they are. Before each update, the agent chooses its next move, in yellow, and the target uses that move's value, outlined in red.

Sarsa's target uses the move the agent actually makes next, exploring moves included, so its values count what exploring costs. Next to the edge, every step has a 0.025 chance of a random move down into the cliff; one row up, a random move down only lands on the edge. That makes the edge worth less to Sarsa.

In the figure the values still jump with every fall, since α = 0.5 moves an estimate halfway to each target. With a small step size and many episodes, they settle at the values of the ε-greedy policy the agent follows, which average in every fall:

The route one row up, 9 moves, is the best an agent can do while it keeps exploring. It is not the best route: once the exploring stops, the edge is two moves shorter and never falls.

6Summary

The key ideas next to their NumPy equivalents, with the tables v and q indexed by state, and by state and action.