On-policy control with approximation

1Values of pushes

To choose a push, the agent compares the values of its two pushes in the state it is in. With too many states for a table, it estimates them from weights, q(s, a, w) ≈ q_π(s, a), the value of taking action a in state s and following π afterwards. The features now describe a state and an action together, x(s, a), and the linear estimate weighs them as before:

Which features? The six ranges of the pole's angle that the prediction note used are not enough to choose by, for a reason in the physics of the cart:

1. A push changes how fast the cart moves, and with it how fast the pole turns, at once.
2. The pole's angle changes only on the steps after.
3. An agent that sees only the angle would see the same next state whichever way it pushed, and an update that looks one step ahead could never tell its two pushes apart.

So this note's agent also sees which way the pole swings:

For each situation there is one feature per push, d = 24: x_i(s, a) is 1 for the situation of s and the push a, and 0 for the other 23, so q(s, a, w) is the weight of that pair. It is state aggregation again, now over pairs of a state and an action.

The weights learn as in the prediction note, from examples that now pair a state and an action with a target, S_t, A_t ↦ U_t:

The target can be the return G_t, or one of the n-step returns of the n-step bootstrapping note. Sarsa's target, the reward plus the value of the next state and of the action chosen in it, gives episodic semi-gradient one-step Sarsa:

It is a semi-gradient method for the reason semi-gradient TD(0) was: its target depends on the weights, and the update ignores that. For a fixed policy it converges as semi-gradient TD(0) does, to a fixed point of its own, with the same kind of bound on its error.

The figure shows the 24 weights for the random policy of the prediction note, at the average return after each push when the pushes after it are random, which is where gradient Monte Carlo settles:

• each pair of bars stands over its situation, drawn as a small cart and pole with a curved arrow for the way it swings;
• the left bar is a push to the left, the right bar a push to the right;
• a small blue arrow beside the cart points to the push worth more.

Drag the pole at the top: its lean picks the range, and the way you move it, the swing.

2Learning to keep the pole up

The values of the last section belong to the random policy. To do better, the agent acts on its own estimates, as the control methods of the earlier notes did: in the next state it computes the value of each action and takes the greedy one,

or, some of the time, a random one: ε-greedy. With two pushes this takes two lookups. With many actions, or a continuous range of them, finding the best one is a problem of its own, with no settled answer. The policy that acts is the one being learned, on-policy, so every update changes the policy a little.

The algorithm

Episodic semi-gradient Sarsa, for an estimate q differentiable in its weights, a step size α > 0 and a small ε > 0:

1. Start with any weights w, for example all 0.
2. At the start of each episode, observe the first state S, and choose A from q(S, ·, w), ε-greedy.
3. Take A, and observe the reward R and the next state S′.
4. If S′ is terminal, update w ← w + α[R − q(S, A, w)] ∇q(S, A, w), and go back to step 2 for the next episode.
5. Otherwise choose A′ from q(S′, ·, w), ε-greedy, and update w ← w + α[R + γq(S′, A′, w) − q(S, A, w)] ∇q(S, A, w).
6. Set S ← S′ and A ← A′, and go back to step 3.

The figure's agent explores without random pushes, with ε = 0. Instead it starts every weight at 300 steps, more than any of its episodes will last. Whatever push it tries falls short of 300 sooner or later, so the push it has not tried looks better, and it tries that one: optimism, the bandit note's optimistic start.

α stays at 0.1 throughout. The prediction note shrank α from one episode to the next so that its weights would settle; here they must first come down from 300, and their targets keep changing as the policy improves. Over 100 runs of 500 episodes:

The figure draws the cart and pole at the top, with the push just chosen as a yellow arrow, and below them the bars of the last section, with a dot on the angle axis of the row of the pole's swing. Each press is one line of the steps above, as in the Sarsa figure of the TD note: choose A, take it, choose A′, the target, outlined in red, and the update, outlined in green.

3Looking n steps ahead

The n-step return with weights, from the eligibility traces and prediction notes, works with action values too, the estimate at its end taken from the weights as they stand:

with G_t:t+n = G_t when t + n ≥ T. It takes the place of Sarsa's target in the general update, which, as in the n-step bootstrapping note, updates the pair of n steps back:

The algorithm

Episodic semi-gradient n-step Sarsa, with α > 0, a small ε > 0 and n ≥ 1. It keeps the last n + 1 states, actions and rewards:

1. Start with any weights w, for example all 0.
2. At the start of each episode, observe S₀, choose A₀ from q(S₀, ·, w), ε-greedy, and set T ← ∞.
3. For t = 0, 1, 2, …: if t < T, take A_t and observe R_t+1 and S_t+1; if S_t+1 is terminal, set T ← t + 1, and otherwise choose A_t+1 from q(S_t+1, ·, w), ε-greedy.
4. Set τ ← t − n + 1, the time whose estimate is updated. If τ ≥ 0: G ← Σmin(τ+n, T)i=τ+1γ^i−τ−1R_i; if τ + n < T, G ← G + γⁿq(S_τ+n, A_τ+n, w); and w ← w + α[G − q(S_τ, A_τ, w)] ∇q(S_τ, A_τ, w).
5. Repeat steps 3 and 4 until τ = T − 1, then start the next episode.

On the cart-pole, the number of real rewards in the target matters:

• a target that looks one step ahead learns little from most steps: the pole usually stays in the same situation, so the target borrows the very weight being updated, and the TD error is 1 whatever that weight is, as in the prediction note;
• a target with n real rewards sees more of what a push did;
• with too many, though, the target is a whole return, which varies more from one episode to the next.

The figure runs the agent of the last section with four values of n, 200 times each, and shows how long the pole stays up, episode by episode.

Here the n that does best is a large one, 16 steps, about a third of a second of the cart's motion: the twelve situations are too coarse for the estimate of the next one to stand in well for what follows it.

4A task that never ends

The cart-pole can also be posed without episodes. After every failure, the pole falling or the cart leaving the track, the cart and pole start afresh and the task goes on, with a reward of −1 at each failure and 0 at every other step. A return that adds up rewards forever would then be −∞ for every policy that ever fails. Instead of a total, a policy is judged by its average reward per step:

Here it is minus the rate of failures: a policy that loses the cart every 183 steps on average has r(π) = −1/183 ≈ −0.0055.

The definition assumes that this long-run average does not depend on where the agent starts. The values then measure each step against it:

On the cart-pole, the differential value of a push is how many failures fewer than average follow it, in the long run.

The figure shows why the average must come out first. It adds up R_t − R over 1,100 steps of an agent that has learned to keep the pole up, the one of the next section, for an estimate R of r(π) that you set by dragging the end of the sum.

Learning needs no new machinery. The TD error measures the reward against the estimate R_t, and adds the values of the next pair and of this one, with no discount:

The weights follow w_t+1 ≐ w_t + αδ_t∇q(S_t, A_t, w_t), and R learns from the same error with a step size of its own, R ← R + βδ_t: when rewards keep beating R, the TD errors are mostly positive and R rises, and the other way round.

5Differential semi-gradient n-step Sarsa

With n steps, the differential return subtracts the estimate of the average from each of its n rewards, and then borrows the estimate at its end:

and the n-step TD error, δ_t ≐ G_t:t+n − q(S_t, A_t, w), updates the weights and R as in the last section.

The algorithm

Differential semi-gradient n-step Sarsa, with step sizes α, β > 0, a small ε > 0 and n ≥ 1. It keeps the last n + 1 states, actions and rewards:

1. Start with any weights w and any R, for example all 0.
2. Observe S₀ and choose A₀ from q(S₀, ·, w), ε-greedy.
3. For t = 0, 1, 2, …: take A_t, observe R_t+1 and S_t+1, and choose A_t+1 from q(S_t+1, ·, w), ε-greedy.
4. Set τ ← t − n + 1. If τ ≥ 0: δ ← Στ+ni=τ+1(R_i − R) + q(S_τ+n, A_τ+n, w) − q(S_τ, A_τ, w), then R ← R + βδ and w ← w + αδ∇q(S_τ, A_τ, w).

There is no episode to end: the loop runs as long as the agent does. β must be small, so that R follows the long-run average rather than the last few rewards.

The figure's agent uses n = 4, α = 0.1, β = 0.0001 and ε = 0, and starts with every weight and R at 0, which is optimistic too: R = 0 expects no failures at all. As it runs:

• a failure puts −1 in the windows of four updates;
• between failures, rewards of 0 beat a negative R, which adds a little to every TD error.

The figure is drawn like the one of section 2, but its bars are differential values, which can be negative, and the dashed blue outlines mark the four pushes in the window of the update.

6Summary

The key ideas next to their NumPy equivalents, for a linear estimate:

• x is the feature vector of S_t and A_t, and x_next that of S_t+1 and A_t+1;
• xs_next holds the feature vectors of S_t+1 with each action, as rows;
• in the n-step rows, rs holds the n rewards after A_t, and x_n the feature vector of S_t+n and A_t+n;
• rewards holds the rewards of a long run.