---
title: On-Policy Control with Approximation
module: Approximate Solution Methods
moduleNumber: 3
lessonNumber: 3
order: 303
summary: >
  Prediction learned a value function from features; control learns to act. We
  carry semi-gradient methods over to action values $\hat q(s,a,\mathbf{w})$,
  giving episodic semi-gradient Sarsa and its n-step form, and solve
  Mountain Car by descending a cost-to-go surface. In the continuing case,
  function approximation makes discounting unable to affect which policy is
  best, so we replace it with the average-reward setting — the
  differential return, differential value functions, and differential
  semi-gradient Sarsa.
topics: [Approximation]
sources:
  - book: Sutton & Barto
    ref: "Ch. 10 — On-policy Control with Approximation; §10.1 Episodic Semi-gradient Control; §10.2 Semi-gradient n-step Sarsa"
  - book: Sutton & Barto
    ref: "§10.3 Average Reward: A New Problem Setting for Continuing Tasks; §10.4 Deprecating the Discounted Setting"
---

The [previous lesson](/reinforcement-learning/approximation/on-policy-prediction)
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 $\varepsilon$-greedily) with respect to the
current $\hat q$.[^sb-control] 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$:

$$
\mathbf{w}_{t+1} \;\doteq\; \mathbf{w}_t + \alpha\,\big[\, U_t - \hat v(S_t, \mathbf{w}_t) \,\big]\, \nabla \hat v(S_t, \mathbf{w}_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)$,

$$
\mathbf{w}_{t+1} \;\doteq\; \mathbf{w}_t + \alpha\,\big[\, U_t - \hat q(S_t, A_t, \mathbf{w}_t) \,\big]\, \nabla \hat q(S_t, A_t, \mathbf{w}_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**:

$$
\mathbf{w}_{t+1} \;\doteq\; \mathbf{w}_t + \alpha\,\big[\, R_{t+1} + \gamma\, \hat q(S_{t+1}, A_{t+1}, \mathbf{w}_t) - \hat q(S_t, A_t, \mathbf{w}_t) \,\big]\, \nabla \hat q(S_t, A_t, \mathbf{w}_t).
$$

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)](/reinforcement-learning/tabular-methods/temporal-difference-learning)
does, with the same kind of error bound.

> **Definition (Episodic semi-gradient one-step Sarsa).** The action-value
> semi-gradient update
> $\mathbf{w} \gets \mathbf{w} + \alpha\,[R + \gamma\, \hat q(S', A', \mathbf{w}) -
> \hat q(S, A, \mathbf{w})]\, \nabla \hat q(S, A, \mathbf{w})$,
> with $A'$ chosen $\varepsilon$-greedily from $\hat q(S', \cdot, \mathbf{w})$.
> Prediction (fixed target policy) plus $\varepsilon$-greedy policy improvement
> gives on-policy control.

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
$\varepsilon$-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.)

```algorithm
caption: $\textsc{Episodic-Semi-Gradient-Sarsa}$ — estimate $\hat q \approx q_\ast$
input: a differentiable action-value function $\hat q : \mathcal{S} \times \mathcal{A} \times \mathbb{R}^d \to \mathbb{R}$
parameters: step size $\alpha > 0$; small $\varepsilon > 0$
initialize $\mathbf{w} \in \mathbb{R}^d$ arbitrarily (e.g. $\mathbf{w} = \mathbf{0}$)
for each episode do
  $S, A \gets$ initial state and action of episode (e.g. $\varepsilon$-greedy)
  repeat
    take action $A$, observe $R, S'$
    if $S'$ is terminal then
      $\mathbf{w} \gets \mathbf{w} + \alpha\,[R - \hat q(S, A, \mathbf{w})]\, \nabla \hat q(S, A, \mathbf{w})$
      break // go to next episode
    choose $A'$ as a function of $\hat q(S', \cdot, \mathbf{w})$ (e.g. $\varepsilon$-greedy)
    $\mathbf{w} \gets \mathbf{w} + \alpha\,[R + \gamma\, \hat q(S', A', \mathbf{w}) - \hat q(S, A, \mathbf{w})]\, \nabla \hat q(S, A, \mathbf{w})$
    $S \gets S'$
    $A \gets A'$
  until $S$ is terminal
```

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.

$$
% caption: The Mountain Car task. From the valley floor the engine cannot climb
% the goal slope directly; the car must first reverse up the left hill to build
% momentum. State is (position $x$, velocity $\dot x$); the three actions are
% full-throttle forward, full-throttle reverse, and zero throttle.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{grn}{HTML}{1F9D4D}
  % the hill: a cosine-like valley
  \draw[black, thick] plot[smooth, domain=-3:3, samples=60]
    (\x, {0.5*cos(deg(1.05*\x)) + 0.7});
  % goal flag at the right crest
  \fill[grn] (2.99,1.13) rectangle (2.99,1.13);
  \draw[grn, thick] (2.6,1.06) -- (2.6,1.65);
  \fill[grn] (2.6,1.65) -- (2.9,1.55) -- (2.6,1.45) -- cycle;
  \node[grn, anchor=south west, font=\scriptsize] at (2.05,1.62) {goal};
  % the car near the valley floor
  \fill[acc] (-0.15,0.24) circle (2.6pt);
  \node[acc, anchor=north, font=\scriptsize] at (-0.15,0.14) {car};
  % momentum arrows: reverse first, then forward
  \draw[acc, thick, ->] (-0.4,0.5) to[bend left=25] (-1.5,0.95);
  \node[acc, anchor=east, font=\scriptsize] at (-1.55,0.98) {1. reverse};
  \draw[acc, thick, ->] (0.1,0.5) to[bend right=22] (2.3,1.15);
  \node[acc, anchor=north, font=\scriptsize] at (1.45,0.5) {2. build momentum};
\end{tikzpicture}
$$

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

$$
x_{t+1} \;\doteq\; \bound\big[\, x_t + \dot x_{t+1} \,\big], \qquad
\dot x_{t+1} \;\doteq\; \bound\big[\, \dot x_t + 0.001\,A_t - 0.0025 \cos(3 x_t) \,\big],
$$

where $\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,

$$
\hat q(s, a, \mathbf{w}) \;\doteq\; \mathbf{w}^\top \mathbf{x}(s, a) \;=\; \sum_{i=1}^{d} w_i\, x_i(s, a),
$$

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.

$$
% caption: The cost-to-go surface $-\max_a \hat q(s,a,\mathbf{w})$ over the
% (position, velocity) plane, sketched at three stages of one run. Early on
% (left) optimism drives exploration and the surface is spiky and low; after
% many episodes (right) it settles into a smooth bowl whose height is the number
% of steps still needed to reach the goal. The valley floor of the bowl is the
% momentum-building region.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  % --- three mini surface panels drawn as stacked profile curves ---
  \foreach \ox/\lab/\amp/\rough in {0/early (step 428)/0.35/1, 4.7/mid (episode 104)/0.9/0, 9.4/late (episode 9000)/1.25/0} {
    \begin{scope}[xshift=\ox cm]
      % baseplate
      \draw[black] (0,0) -- (2.6,0) -- (3.3,0.55) -- (0.7,0.55) -- cycle;
      % axis hint labels, kept clear of the baseplate edges
      \node[anchor=north east, font=\scriptsize, black] at (0.05,-0.06) {position};
      \node[anchor=north west, font=\scriptsize, black] at (3.25,0.5) {velocity};
      \node[anchor=north, font=\scriptsize] at (1.85,-0.42) {\lab};
      % front profile ridge (smooth bowl for later panels, jagged for early)
      \ifnum\rough=1
        \draw[acc, thick] (0.2,0.15) -- (0.55,0.55) -- (0.9,0.1) -- (1.25,0.62)
          -- (1.6,0.2) -- (1.95,0.5) -- (2.3,0.12) -- (2.55,0.35);
      \else
        \draw[acc, thick] plot[smooth, domain=0.2:2.55, samples=30]
          (\x, {\amp*sin(deg(3.1416*(\x-0.2)/2.35)) + 0.12});
      \fi
    \end{scope}
  }
\end{tikzpicture}
$$

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
$\varepsilon = 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](/reinforcement-learning/tabular-methods/n-step-bootstrapping)
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:

$$
G_{t:t+n} \;\doteq\; R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^{n}\, \hat q(S_{t+n}, A_{t+n}, \mathbf{w}_{t+n-1}),
\qquad t + n < T,
$$

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:

$$
\mathbf{w}_{t+n} \;\doteq\; \mathbf{w}_{t+n-1} + \alpha\,\big[\, G_{t:t+n} - \hat q(S_t, A_t, \mathbf{w}_{t+n-1}) \,\big]\, \nabla \hat q(S_t, A_t, \mathbf{w}_{t+n-1}),
\qquad 0 \le t < T.
$$

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.

```algorithm
caption: $\textsc{Episodic-Semi-Gradient-n-Step-Sarsa}$ — estimate $\hat q \approx q_\ast$
input: a differentiable $\hat q : \mathcal{S} \times \mathcal{A} \times \mathbb{R}^d \to \mathbb{R}$; a policy $\pi$ (if estimating $q_\pi$)
parameters: step size $\alpha > 0$; small $\varepsilon > 0$; a positive integer $n$
initialize $\mathbf{w} \in \mathbb{R}^d$ arbitrarily (e.g. $\mathbf{w} = \mathbf{0}$)
all store and access operations can take their index mod $n+1$
for each episode do
  initialize and store $S_0 \ne$ terminal
  select and store $A_0 \sim \pi(\cdot \mid S_0)$ or $\varepsilon$-greedy in $\hat q(S_0, \cdot, \mathbf{w})$
  $T \gets \infty$
  for $t = 0, 1, 2, \ldots$ do
    if $t < T$ then
      take action $A_t$, observe and store $R_{t+1}$ and $S_{t+1}$
      if $S_{t+1}$ is terminal then
        $T \gets t + 1$
      else
        select and store $A_{t+1} \sim \pi(\cdot \mid S_{t+1})$ or $\varepsilon$-greedy in $\hat q(S_{t+1}, \cdot, \mathbf{w})$
    $\tau \gets t - n + 1$ // $\tau$ = time whose estimate is updated now
    if $\tau \ge 0$ then
      $G \gets \sum_{i=\tau+1}^{\min(\tau+n,\,T)} \gamma^{\,i-\tau-1} R_i$
      if $\tau + n < T$ then
        $G \gets G + \gamma^{n}\, \hat q(S_{\tau+n}, A_{\tau+n}, \mathbf{w})$
      $\mathbf{w} \gets \mathbf{w} + \alpha\,[G - \hat q(S_\tau, A_\tau, \mathbf{w})]\, \nabla \hat q(S_\tau, A_\tau, \mathbf{w})$
  until $\tau = T - 1$
```

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.

$$
% caption: Mountain Car learning curves for semi-gradient $n$-step Sarsa with
% tile coding: steps per episode (log scale, averaged over many runs) against
% episode number. An intermediate $n$ ($n=8$, blue) learns faster and settles
% lower than one-step Sarsa ($n=1$, red); both fall steeply from an initial
% $\sim 1000$ steps. Curves labelled at their right ends.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % axes
  \draw[->, black] (0,0) -- (6.6,0);
  \node[anchor=north, font=\scriptsize] at (3.2,-0.5) {episode};
  \draw[->, black] (0,0) -- (0,4.3);
  \node[align=center, anchor=east, font=\scriptsize] at (-0.15,3.6)
    {steps per\\episode\\(log scale)};
  \foreach \x/\lab in {0/0, 6.0/500}
    \node[anchor=north, font=\scriptsize] at (\x,-0.05) {\lab};
  \foreach \y/\lab in {0.3/100, 1.7/200, 3.1/400, 4.1/1000}
    \node[anchor=east, font=\scriptsize] at (-0.08,\y) {\lab};
  % n=1 curve: falls, settles higher
  \draw[red, thick] (0.15,4.15) .. controls (0.7,1.9) and (1.6,1.35) .. (6.0,1.15);
  \node[red, anchor=west, font=\scriptsize] at (6.05,1.15) {n=1};
  % n=8 curve: falls faster, settles lower
  \draw[acc, thick] (0.15,4.05) .. controls (0.55,1.4) and (1.3,0.75) .. (6.0,0.6);
  \node[acc, anchor=west, font=\scriptsize] at (6.05,0.6) {n=8};
\end{tikzpicture}
$$

## 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](/reinforcement-learning/approximation/policy-gradient-methods)
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.[^actor-critic] 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 $\varepsilon$-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](/reinforcement-learning/approximation/average-reward-control).
Further out, relaxing the on-policy assumption exposes the sharpest instability in
approximate RL — the
[deadly triad](/reinforcement-learning/approximation/off-policy-and-the-deadly-triad).

[^sb-control]: **Sutton & Barto**, _Reinforcement Learning: An Introduction_ (2nd ed.), Ch. 10 — On-policy Control with Approximation. §10.1 — Episodic Semi-gradient Control: the action-value semi-gradient update (10.1), episodic semi-gradient one-step Sarsa (10.2), and Example 10.1, the Mountain Car task with tile-coded features (10.3) and its cost-to-go figure (Figure 10.1). §10.2 — Semi-gradient n-step Sarsa: the n-step return (10.4) and update (10.5).
[^actor-critic]: **Mnih, V. et al.** (2016), "Asynchronous methods for deep reinforcement learning", _ICML_ — A3C, parallel on-policy actor-learners. **Schulman, J. et al.** (2017), "Proximal policy optimization algorithms", arXiv:1707.06347 — PPO's clipped surrogate objective for stable on-policy updates.