On-Policy Control with Approximation

The previous lesson learned a value function from features: replace the table $V(s)$ with a parameterized $\hat{v}(s,\mathbf{w})$, and update the weight vector $\mathbf{w}$ by semi-gradient descent on the prediction error. That solves evaluation — how good is a fixed policy — but not control, where the policy itself is what we are trying to improve. Control needs action values, because a greedy step compares actions, and to compare actions from a value function you must be able to evaluate each one.

So the move is the same one that took tabular TD to Sarsa: approximate the action-value function instead of the state-value function. Write $\hat{q}(s,a,\mathbf{w})\approx q_{\pi }(s,a)$ for a differentiable function of the weights, generalize the semi-gradient update to it, and interleave policy improvement by acting greedily (or $\epsilon$-greedily) with respect to the current $\hat{q}$.¹ Everything from prediction carries over; what is new is that once the state space is too large to enumerate, the whole idea of discounting the future starts to come apart — and the second half of this lesson replaces it.

Episodic semi-gradient Sarsa

In prediction the target for $\hat{v}$ was some return $U_t$, and the semi-gradient update nudged $\mathbf{w}$ toward reducing the squared error between $\hat{v}(S_t,\mathbf{w})$ and $U_t$:

The action-value form is the identical statement with $\hat{q}$ in place of $\hat{v}$ and a state–action argument in place of a state. For a general target $U_t$ estimating $q_{\pi }(S_t,A_t)$,

Take $U_t$ to be the one-step Sarsa return, one real reward plus the discounted estimate of the next state–action pair actually taken, and this becomes episodic semi-gradient one-step Sarsa:

It is called semi-gradient for the same reason as in prediction: the target $R_{t+1}+\gamma \hat{q}(S_{t+1},A_{t+1},{\mathbf{w}}_t)$ itself depends on ${\mathbf{w}}_t$, but we treat it as a fixed number and differentiate only the estimate $\hat{q}(S_t,A_t,{\mathbf{w}}_t)$ that we are correcting. The gradient of the target is dropped. For a constant policy this method converges the same way TD(0) does, with the same kind of error bound.

To turn evaluation into control we need action selection and improvement on top of it. If the action set is discrete and not too large, both are immediate: in state $S_t$ compute $\hat{q}(S_t,a,{\mathbf{w}}_t)$ for every action $a$, then take the greedy action $A_t^{\ast }=\arg {\max }_a\hat{q}(S_t,a,{\mathbf{w}}_t)$. Policy improvement is done by making the estimation policy a soft — say $\epsilon$-greedy — approximation of that greedy policy, and actions are selected according to the same policy. (Continuous or very large action sets are a research topic; here the action set is small.)

The terminal step drops the bootstrap: with $\hat{q}$ of a terminal state defined to be zero, the target is just the final reward $R$. Otherwise every step is a single semi-gradient correction toward a Sarsa return computed from the action the policy actually selected next — which is what makes it on-policy.

Mountain Car

The running example for the rest of this lesson is Mountain Car: drive an underpowered car up a steep one-dimensional hill. The engine is weaker than gravity, so from the bottom of the valley full throttle is not enough to climb the goal slope directly. The only solution is counterintuitive — reverse up the opposite hill first, then use the accumulated momentum to carry past the goal. It is a clean example of a continuous control task where things must get worse (farther from the goal) before they can get better, and undirected methods struggle with it.

The physics is a simplified two-variable system. Position $x_t$ and velocity ${\dot{x}}_t$ update by

where $\mathrm{bound}$ enforces $-1.2\le x_{t+1}\le 0.5$ and $-0.07\le {\dot{x}}_{t+1}\le 0.07$. The action $A_t\in \{-1,0,+1\}$ is full-reverse, zero, or full-forward throttle; the $\cos (3x_t)$ term is gravity along the slope. The reward is $-1$ on every step until the car passes the goal at $x=0.5$, which ends the episode. Minimizing total penalty therefore means reaching the goal in as few steps as possible. Each episode starts from a random position in $[-0.6,-0.4]$ with zero velocity.

Trace two steps by hand to see the dynamics. Start at the valley near $x_0=-0.52$, ${\dot{x}}_0=0$, and apply full forward throttle $A_0=+1$. The gravity term is $-0.0025\cos (3\cdot (-0.52))=-0.0025\cos (-1.56)$; with the cosine argument in radians, $\cos (-1.56)\approx 0.011$, so gravity contributes about $-0.000027$. The velocity update is ${\dot{x}}_1=0+0.001(+1)-0.000027\approx +0.00097$, and the position becomes $x_1=-0.52+0.00097\approx -0.519$. The engine's $0.001$ barely outpaces gravity here because the car sits near the flat valley bottom, where the slope is shallow. Push forward again from $x_1=-0.519$: gravity is still small, ${\dot{x}}_2\approx 0.00097+0.001-0.000024\approx 0.00194$, so $x_2\approx -0.517$. Velocity accumulates, but slowly — and once the car climbs the right slope, where $\cos (3x)$ turns strongly negative, gravity's pull grows until full throttle alone stalls the climb. That stall forces the policy to reverse first: driving left up the opposite hill lets gravity there add to the engine, and the car returns through the valley with enough speed to clear the right slope on the next pass.

The two continuous state variables are turned into binary features by tile coding: eight overlapping grid-tilings, each partitioning the (position, velocity) plane, with a feature set to $1$ when the state falls in that tile and $0$ otherwise. Because the features are binary indicators, the action-value function is linear in the weights,

so $\nabla \hat{q}(s,a,\mathbf{w})=\mathbf{x}(s,a)$ and the semi-gradient update simply adds a scaled feature vector to the weights. The feature vector $\mathbf{x}(s,a)$ depends on the action as well as the state — one block of tile features per action — so the same tilings give a separate value surface for each of the three throttle settings.

The cost-to-go surface

A useful way to visualize learning is to plot the cost-to-go function, $-{\max }_a\hat{q}(s,a,\mathbf{w})$, over the (position, velocity) plane. Since every reward is $-1$, ${\max }_a\hat{q}$ is negative and roughly counts the steps still needed to reach the goal; negating it gives a positive surface whose height approximates the number of steps remaining from each state. Learning is the process of this surface settling into the true cost-to-go.

Sutton and Barto's figure shows exactly this. The action values were initialized to zero, which is optimistic (all true values are strongly negative), so even with $\epsilon =0$ the agent explores widely: every state it visits turns out worse than the unrealistically high zero it started at, which continually drives it away from wherever it has been toward unexplored states. The step-428 panel, before even one episode has finished, shows the car oscillating in the valley, building the momentum it needs; by episode 9000 the surface is a clean bowl. This optimistic initialization substitutes for explicit exploration on this task.

Semi-gradient n-step Sarsa

One-step Sarsa bootstraps immediately; as in the tabular case, an intermediate level of bootstrapping usually learns faster. The n-step return generalizes to the function-approximation setting exactly as it did to state values — string $n$ real rewards, then bootstrap from $\hat{q}$ at the state–action pair reached $n$ steps out:

with $G_{t:t+n}\doteq G_t$ when $t+n\ge T$, as usual. The $n$-step update is the same semi-gradient step with this return as its target:

The same lag as tabular $n$-step Sarsa applies — the return for step $t$ is not computable until wall-clock time $t+n$ — so the pseudocode updates the state $\tau =t-n+1$ steps in the past.

On Mountain Car the effect is the one bootstrapping always has: an intermediate $n$ learns faster and reaches a lower steps-per-episode floor than $n=1$. With well-chosen step sizes, $n=8$ clearly beats $n=1$; sweeping both $\alpha$ and $n$ shows the familiar tradeoff, with a moderate $n$ (around $n=4$) sitting at the bottom of the family of U-shaped curves.

Control at scale

Episodic semi-gradient Sarsa is the on-policy, value-based core that modern control methods extend. The most important extension past Sutton & Barto addresses a limitation of this lesson: the greedy step $\arg {\max }_a\hat{q}$ is only tractable when the actions can be enumerated.

On-policy actor-critic and the continuous-action gap. A large or continuous action set makes $\arg {\max }_a\hat{q}$ intractable — the actions cannot be enumerated to pick the greedy one. The standard solution is to parameterize the policy directly and learn it alongside a value estimate, the actor-critic idea that the policy-gradient lesson develops. Its deep, on-policy instances are A3C (Mnih et al., 2016, Asynchronous methods for deep reinforcement learning, ICML), which runs many actor-learners in parallel to decorrelate on-policy data without a replay buffer, and PPO (Schulman et al., 2017, Proximal policy optimization algorithms, arXiv:1707.06347), which constrains each policy update with a clipped surrogate objective so the on-policy step never moves the policy too far.² Both keep the semi-gradient value critic of this lesson and add a policy that handles continuous throttle directly, rather than three discrete settings.

What carried over, and what comes next

The mechanical part of the jump from prediction to control is small. Swap $\hat{v}$ for $\hat{q}$, add $\epsilon$-greedy action selection, and the semi-gradient update is unchanged — episodic semi-gradient Sarsa and its $n$-step form are the prediction methods with an action argument added, and Mountain Car shows them descending a cost-to-go surface into a working policy.

The subtle part is the setting, and it is large enough to need its own lesson. Once the state space is too big to enumerate, function approximation undermines discounting, and the replacement is the average-reward formulation. That continues in average-reward control for continuing tasks. Further out, relaxing the on-policy assumption exposes the sharpest instability in approximate RL — the deadly triad.