On-policy prediction with approximation

1Values from weights

The eligibility traces note wrote its updates for any estimate v(s, w), the value of state s given a vector of weights w, with a table as the simplest case, one weight per state. From here on, the weights are far fewer than the states. Each state is described by a feature vector, d numbers computed from the state:

and the simplest estimate, the one this note uses, is linear in the weights: each feature times its weight, added up.

For the cart-pole, the features could be the four numbers of the state, or anything computed from them. This note's agent keeps just one thing: the pole's angle, cut into six ranges of 4° from −12° to 12°. Each range is a feature, 1 when the pole leans within it and 0 otherwise, so d = 6, and v(s, w) is simply the weight of the range the pole is in.

A table is linear too, with one feature per state, 1 in its own state and 0 in every other. Choosing features is choosing what the agent can tell apart. This agent cannot tell a pole swinging back toward upright from one falling over, if they lean the same. Every state still gets a value, even one never seen, as long as its features can be computed. The price is that an update no longer stays where it is made: changing a weight to correct one state's estimate changes the estimate of every state with that feature, here every state in its range.

Each update of the earlier notes moved the estimate of a state S_t toward a target:

Each such pair, the state's features and its target, is now an example for supervised learning, which fits a function to examples of inputs and the outputs wanted for them. Any supervised method could adjust the weights, as long as it:

• learns from examples that arrive one at a time, as the agent moves;
• copes with targets that change as the estimates improve.

This note uses the simplest, gradient descent.

2Which errors matter

With fewer weights than states, the estimates cannot all be right, and making one better can make others worse. To choose among them, weigh each state's squared error by how much that state matters, with a distribution μ(s) ≥ 0, Σ_s μ(s) = 1. The result is the mean squared value error:

Its square root gives a rough idea of how far the estimates are from the true values.

In an episodic task it follows from two quantities: h(s), the probability that an episode starts in s, and η(s), the number of steps an episode spends in s on average. Time is spent in s when an episode starts there, or when a step leads there from a state where time is spent:

With discounting, a factor γ in the second term treats it as a chance that the episode ends. Pushed at random, the pole spends this share of its time in each range:

Inside a range the true values differ: a pole between 4° and 8° that is swinging back toward upright can stay up 20 more steps or more, and one falling away only 2 or 3. One weight cannot match them all, and VE weighs each miss by how often its state comes.

In the figure, each dot is a state the policy visited, at its angle and its true value, the steps it had left on average; there are more dots where the pole spends more time. Drag the six bars.

VE is least with each bar at the average of its range's states, weighed by how often they come: about 19 steps in the middle ranges, 12 from 4° to 8°, and 5 past 8°. What remains, 22.8, a typical miss of 4.8 steps, is the spread inside the ranges, which only better features could reduce. In practice nobody computes μ: following π brings each state at these rates, so learning from the states as they come weighs their errors by μ.

VE is the goal this note uses, with two cautions:

• A linear estimate has a single minimum of VE; an estimate that is not linear in its weights, such as a neural network, can have many, and the methods below may then find only one near where they start.
• VE is not certain to be the right goal: values are wanted for choosing actions, and the values with the least VE are not necessarily the best for that.

3Learning from returns

Suppose for a moment that each visit to a state S_t came with its true value. The weights could then take a small step in the direction that reduces that state's squared error fastest, against its gradient:

The gradient ∇v is the vector of the estimate's partial derivatives with respect to the weights. It says which weights produced the estimate of S_t, and how much, and for a linear estimate it is the feature vector, ∇v(s, w) = x(s).

States come at the rates μ sets, so over many small steps the weights go down VE. The steps must stay small, since steps that removed each state's error completely would just chase the last state visited. With a step size that shrinks over time at the right rate, the weights converge to a minimum of VE, or to one of its minima if it has several.

The true value is unknown, so the update uses a target U_t in its place:

If the target is right on average, E[U_t | S_t = s] = v_π(s), the guarantee stays the same. The return is right on average by definition, since v_π(s) is the return to expect from s. With U_t = G_t, the update is gradient Monte Carlo.

The algorithm

Gradient Monte Carlo, for a policy π, an estimate v differentiable in its weights, and a step size α > 0:

1. Start with any weights w, for example all 0.
2. Generate an episode S₀, A₀, R₁, …, S_T−1, A_T−1, R_T following π.
3. For each step, t = 0, 1, …, T − 1, update w ← w + α[G_t − v(S_t, w)] ∇v(S_t, w).
4. Go back to step 2 for the next episode.

With state aggregation, ∇v is 1 for the weight of S_t's range and 0 for the others, so each update moves one weight, the shared estimate of a whole range, toward the return of one of its states.

The figure runs gradient Monte Carlo on the cart-pole for 2,000 episodes:

• Above, the cart and pole show the current state, and a yellow arrow the push just chosen.
• Below, each range's weight is a bar, the steps the pole is expected to stay up, and a dot on the axis marks the pole's current angle.
• α starts at 0.1 and shrinks after every episode, α = 0.1 · 20/(k + 19) in episode k, so that the weights settle: these methods converge when α shrinks, and with α constant a single long episode would keep moving the bars by several steps.

4Learning from the next estimate

TD(0) uses the target U_t = R_t+1 + γv(S_t+1, w_t), built from the weights themselves, and that has two consequences:

1. The target is right on average only if the next state's estimate is, so it is biased, and the guarantee of the last section no longer applies.
2. The step of the last section is the gradient of the squared error only for a target that does not depend on the weights. This one does: changing the weights changes the next state's estimate, and with it the target.

The update takes into account how the weights move the estimate of S_t, and ignores how they move the target. It follows only part of the gradient, so it is called a semi-gradient method:

In the cart-pole, 85% of the steps leave the pole in the range it was in. The target of such a step is the reward, 1, plus the very weight being updated, so the TD error is 1 whatever that weight is, and the update raises the estimate and the target together: it chases a target that moves with it.

Why use it, then? For the reasons of the TD note: it learns from every step without waiting for the end of an episode, it works in tasks that never end, and its targets vary less than returns, so it usually learns faster. And with a linear estimate it converges reliably, to a point that the next section finds.

The algorithm

Semi-gradient TD(0), for a policy π, an estimate v differentiable in its weights with v(terminal, ·) = 0, and a step size α > 0:

1. Start with any weights w, for example all 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 w ← w + α[R + γv(S′, w) − v(S, w)] ∇v(S, w).
5. Set S ← S′, and go back to step 3 until S is terminal.

The figure runs semi-gradient TD(0) on the same episodes, with the same ranges and the same α. Each step's target borrows the weight of the next state's range, outlined in red, which is usually the range being updated.

5Where each method settles

With a linear estimate the gradient is the feature vector, so the general update becomes

and each weight moves in proportion to its own feature. A linear VE has a single minimum, or, when some features merely repeat others, a set of equally good ones. So gradient Monte Carlo, with a step size that shrinks appropriately, converges to the weights with the least VE: in the cart-pole, each range's average.

Semi-gradient TD(0) converges too, though not by the same argument, and not to the same weights. Writing x_t for x(S_t), its update is

Averaged over the states the policy visits and the steps it takes from them, the next weights are

so on average the weights stop moving where b − Aw = 0:

This is the TD fixed point, and linear semi-gradient TD(0) converges to it. With state aggregation it has a plain meaning: each range's weight equals the average, over the steps taken from that range, of the reward plus the weight of the range the step lands in (0 after a fall). TD treats the ranges as if they were the states. They are not: between 4° and 8°, some poles are swinging back toward upright and some are falling, and the range of the next step depends on which. TD borrows the same average for both, and settles 3.4 steps above the averages in the middle ranges and about 1 below them farther out:

How far off can TD's fixed point be? For continuing tasks with γ < 1, it has been proved that

With γ = 0.9, TD's error is at most ten times the least, and the bound loosens as γ nears 1; for episodic tasks, such as the cart-pole, a different but related bound holds. What TD gives up in the limit, it often makes up in speed. Which method is better depends on the problem, the features, and how long learning runs.

Between the two lies n-step TD, whose semi-gradient form updates the estimate of the state n steps back toward the n-step return:

The more real rewards a target holds, the less it leans on the estimates, and the closer its fixed point comes to the averages: in the cart-pole, 19.6 steps in the middle ranges for n = 8. Pick a method in the figure to see where it settles.

6Summary

The key ideas next to their NumPy equivalents, for a linear estimate. x and x_next are the feature vectors of S_t and S_t+1 (all 0 for a terminal state), xs holds the feature vectors of all the states as rows, p_pi[s, s2] is the probability of a step from s to s2 under π, and v_pi, h and mu are indexed by state. In n-step TD, rs holds the n rewards after S_t, and x_n the feature vector of S_t+n.