---
title: On-Policy Prediction with Approximation
module: Approximate Solution Methods
moduleNumber: 3
lessonNumber: 1
order: 301
summary: >
  Every tabular method so far stored one number per state, which fails
  once the state space is large or continuous. We replace the
  table with a parameterized value function $\hat v(s,\mathbf{w})$, define the
  mean squared value error it should minimize under the on-policy distribution,
  and derive stochastic- and semi-gradient learning rules — the semi-gradient
  TD(0) update that bootstraps and so is not a true gradient. Linear methods
  make the analysis clean and give the TD fixed point; feature construction
  (polynomials, Fourier basis, coarse and tile coding, RBFs) supplies the vectors
  $\mathbf{x}(s)$, and neural networks are the nonlinear bridge to deep RL.
topics: [Approximation]
sources:
  - book: Sutton & Barto
    ref: "Ch. 9 — On-policy Prediction with Approximation; §9.1 Value-function Approximation; §9.2 The Prediction Objective (VE)"
  - book: Sutton & Barto
    ref: "§9.3 Stochastic-gradient and Semi-gradient Methods; §9.4 Linear Methods; §9.5 Feature Construction for Linear Methods; §9.7 Nonlinear Function Approximation"
---

Every method up to here has stored the value function as a **table**: one entry
per state for $v_\pi$, one per state–action pair for $q_\pi$. That representation
is exact, but it does not scale. A backgammon position is one of $10^{20}$; a robot's
state is a vector of real-valued joint angles and velocities, so there are
uncountably many. No table has that many rows, and even if it did, the agent
would have to visit each state to fill its entry — there is never enough
experience to learn them one at a time. This is the **curse of dimensionality**:
the number of states grows exponentially in the number of state variables, and
tabular learning grows right along with it.

The alternative is to stop treating states as independent. We represent the
approximate value not as a lookup but as a **parameterized functional form** with
a weight vector $\mathbf{w} \in \mathbb{R}^d$,[^sb-intro]

$$
\hat v(s, \mathbf{w}) \;\approx\; v_\pi(s),
$$

where $d \ll |\mathcal{S}|$ — far fewer weights than states. Changing one weight
now changes the estimated value of _many_ states at once. When the agent
updates $\hat v$ at one state, the change **generalizes** to
other states, and a value can be assigned to states never seen at all. The same
move that lets us cope with enormous state spaces also lets us handle **partial
observability**: if $\hat v$ simply cannot depend on some aspect of the state,
learning proceeds exactly as if that aspect were hidden.[^sb-intro]

Generalization cuts both ways. With genuine approximation, improving the estimate
at one state usually _worsens_ it at others, because they share weights. We can no
longer make every state's value exactly right, so we must say which states we care
about most, and by how much. Prediction becomes an optimization problem, and this
lesson sets it up: the objective, the gradient methods that descend it, the
special structure of the linear case, and the features that feed it.

## The prediction objective

Before we can descend toward a good $\mathbf{w}$, we must define the objective.
Since we can no longer make every state's value exactly right, we need a
weighting that says how much an error at each state costs. That weighting is the
prediction objective.

In the tabular setting we never needed an explicit objective. The values at
different states were decoupled — an update at one state left every other
untouched — so each could converge exactly to its target and there was nothing to
trade off. Approximation destroys that independence. Because updating one state
spills onto others, and because there are far more states than weights, no
$\mathbf{w}$ makes every state correct. We are forced to weigh the errors against
each other.[^sb-ve]

We do this with a **state distribution** $\mu(s) \ge 0$, $\sum_s \mu(s) = 1$,
representing how much we care about the error at each state $s$. Weighting the
squared error at each state by $\mu$ gives the **Mean Squared Value Error**:

$$
\overline{VE}(\mathbf{w}) \;\doteq\; \sum_{s \in \mathcal{S}} \mu(s)\,\big[\,v_\pi(s) - \hat v(s, \mathbf{w})\,\big]^2.
$$

Its square root, the root $\overline{VE}$, is a rough measure of how far the
approximate values stray from the true ones, and it is what appears on the plots
in this chapter. The choice of $\mu$ is not incidental — it decides which states
the approximation bends to fit and which it is allowed to get wrong.

> **Definition (Mean Squared Value Error).** The prediction objective
> $\overline{VE}(\mathbf{w}) = \sum_s \mu(s)[v_\pi(s) - \hat v(s,\mathbf{w})]^2$,
> the average squared gap between the true value $v_\pi(s)$ and the approximation
> $\hat v(s,\mathbf{w})$, weighted by a distribution $\mu$ over states. Because
> weights are shared, no $\mathbf{w}$ can drive it to zero; the best we can seek
> is a minimum.

### The on-policy distribution

Which $\mu$? Throughout this chapter it is the **on-policy distribution**: the
fraction of time the agent actually spends in each state while following $\pi$.
States the policy visits often matter proportionally more, as they should:
accuracy where you are is worth more than accuracy where you never go. In a
continuing task this is the stationary distribution under $\pi$; in an episodic
task it depends on how episodes start. Let $h(s)$ be the probability an episode
begins in $s$, and $\eta(s)$ the expected number of time steps spent in $s$ per
episode. Time is spent in $s$ if episodes start there, or if a transition enters
it from some predecessor $\bar s$:

$$
\eta(s) \;=\; h(s) + \sum_{\bar s} \eta(\bar s) \sum_a \pi(a \mid \bar s)\, p(s \mid \bar s, a), \qquad \text{for all } s \in \mathcal{S}.
$$

Solve this linear system for the visit counts $\eta(s)$, and the on-policy
distribution is that count normalized to sum to one:

$$
\mu(s) \;=\; \frac{\eta(s)}{\sum_{s'} \eta(s')}, \qquad \text{for all } s \in \mathcal{S}.
$$

Emphasizing the on-policy distribution is what makes the
central convergence result of this chapter hold. Update states in these
proportions and bootstrapping is stable; update them in some other proportion and
the same method can diverge, a failure we return to under the
[deadly triad](/reinforcement-learning/approximation/off-policy-and-the-deadly-triad).[^sb-ve]

One caveat: $\overline{VE}$ is not obviously the _right_
objective — our real aim is a better policy, and the value function best for
control is not necessarily the one minimizing $\overline{VE}$. But it is the best
we can currently formalize, and minimizing it is a well-posed goal. For simple
(linear) approximators we can even hope for a **global optimum** $\mathbf{w}^\ast$
with $\overline{VE}(\mathbf{w}^\ast) \le \overline{VE}(\mathbf{w})$ everywhere;
for complex ones (neural nets) we settle for a **local optimum**, and sometimes
for merely staying near one.

## Every update is a training example

Before deriving the learning rule, notice a reframing that connects reinforcement
learning to ordinary supervised learning. Every prediction method here
updates an estimated value at some state toward a **backed-up value**, an _update
target_. Write a single update as $s \mapsto u$: the estimate at $s$ should move
toward $u$. Reading off the targets from earlier lessons:

| Method | Update $s \mapsto u$ | Target $u$ |
| --- | --- | --- |
| Monte Carlo | $S_t \mapsto G_t$ | the actual return |
| TD(0) | $S_t \mapsto R_{t+1} + \gamma\,\hat v(S_{t+1}, \mathbf{w})$ | one reward + bootstrap |
| $n$-step TD | $S_t \mapsto G_{t:t+n}$ | truncated return |
| DP | $s \mapsto \mathbb{E}_\pi[R_{t+1} + \gamma\,\hat v(S_{t+1}, \mathbf{w}) \mid S_t = s]$ | expected backup |

Each pair $s \mapsto u$ is a labelled example: input $s$, desired output $u$. Any
supervised-learning method that takes $(s, u)$ examples and produces a function
can serve as the value approximator — we simply hand it the updates as training
data.[^sb-vfa] But not every such method fits. Reinforcement learning demands
methods that learn **online** from incrementally acquired data, and that tolerate
**nonstationary** targets, because in bootstrapping the target
$R_{t+1} + \gamma\,\hat v(S_{t+1}, \mathbf{w})$ shifts as $\mathbf{w}$ changes.
Batch methods that assume a fixed training set are poorly suited. This narrows us,
in practice, to gradient methods.

## Stochastic-gradient methods

Assume $\hat v(s, \mathbf{w})$ is a differentiable function of the weight vector
$\mathbf{w} = (w_1, \dots, w_d)^\top$, and suppose on each step we observe an
example $S_t \mapsto v_\pi(S_t)$ — a state and, for now, its _true_ value.
**Stochastic gradient descent** (SGD) adjusts $\mathbf{w}$ after each example by a
small step down the gradient of that example's squared error:[^sb-sgd]

$$
\begin{aligned}
\mathbf{w}_{t+1}
&\doteq \mathbf{w}_t - \tfrac12\,\alpha\,\nabla\big[\,v_\pi(S_t) - \hat v(S_t, \mathbf{w}_t)\,\big]^2 \\
&= \mathbf{w}_t + \alpha\big[\,v_\pi(S_t) - \hat v(S_t, \mathbf{w}_t)\,\big]\,\nabla \hat v(S_t, \mathbf{w}_t),
\end{aligned}
$$

where $\alpha$ is a positive step size and $\nabla f(\mathbf{w})$ is the column
vector of partial derivatives $(\partial f / \partial w_1, \dots, \partial f /
\partial w_d)^\top$. The step is proportional to the negative gradient, the
direction of steepest descent on the squared error, so many small steps reduce an
average error like $\overline{VE}$. It matters that the step is _small_: we do not
want to eliminate the error on any single example, because that would unbalance the
fit across the other states that share the weights. Correcting each example only a
fraction of the way is what finds a balance.

$$
% caption: Each example nudges the weight vector down the gradient of that
% example's squared error. From a start the SGD path steps toward the minimum of
% $\overline{VE}(\mathbf{w})$; the step size $\alpha$ scales each arrow, small
% enough to average many examples rather than overfit one.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \foreach \r in {0.55,1.1,1.65,2.2,2.75}
    \draw[black] (0,0) ellipse ({\r*1.3} and \r);
  \fill[red] (0,0) circle (2.6pt);
  \node[red, anchor=north, font=\scriptsize] at (0,-3.05) {min VE};
  \coordinate (p0) at (-3.2,2.2);
  \coordinate (p1) at (-2.1,1.35);
  \coordinate (p2) at (-1.15,0.85);
  \coordinate (p3) at (-0.5,0.4);
  \coordinate (p4) at (-0.15,0.15);
  \draw[acc, very thick, ->] (p0) -- (p1);
  \draw[acc, very thick, ->] (p1) -- (p2);
  \draw[acc, very thick, ->] (p2) -- (p3);
  \draw[acc, very thick, ->] (p3) -- (p4);
  \fill[acc] (p0) circle (2.4pt);
  \node[acc, anchor=south, font=\scriptsize] at (-3.2,2.35) {w start};
  \node[acc, anchor=west, font=\scriptsize] at (-1.75,1.75) {step alpha};
\end{tikzpicture}
$$

In reality we do not know $v_\pi(S_t)$; we have only a possibly-noisy target
$U_t$ standing in for it. Substituting $U_t$ gives the general SGD method for
state-value prediction:

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

If $U_t$ is an **unbiased** estimate — $\mathbb{E}[U_t \mid S_t = s] =
v_\pi(S_t)$ — then $\mathbf{w}_t$ is guaranteed to converge to a local optimum
under the usual decreasing-$\alpha$ conditions. The Monte Carlo return $U_t \doteq
G_t$ qualifies: it is by definition an unbiased sample of $v_\pi(S_t)$. So
**gradient Monte Carlo** is a genuine SGD method and inherits its convergence
guarantee.[^sb-sgd]

```algorithm
caption: $\textsc{Gradient-Monte-Carlo}$ — estimate $\hat v \approx v_\pi$
input: a policy $\pi$, a differentiable $\hat v : \mathcal{S} \times \mathbb{R}^d \to \mathbb{R}$, step size $\alpha > 0$
$\mathbf{w} \gets$ arbitrary (e.g. $\mathbf{0}$)
for each episode do
  generate an episode following $\pi$: $S_0, A_0, R_1, \ldots, R_T, S_T$
  for $t = 0, 1, \ldots, T-1$ do
    $\mathbf{w} \gets \mathbf{w} + \alpha\big[G_t - \hat v(S_t, \mathbf{w})\big]\,\nabla \hat v(S_t, \mathbf{w})$
```

## Semi-gradient methods

The SGD guarantee assumed the target was a fixed label. A bootstrapped target is
not fixed — it is _itself_ computed from the weights being
adjusted, so it moves as they move. This section covers what a true gradient
would require with such a target, and the practical shortcut we take instead.

The guarantee breaks the instant the target **bootstraps**. Consider using the
TD(0) target $U_t \doteq R_{t+1} + \gamma\,\hat v(S_{t+1}, \mathbf{w}_t)$. It
depends on the current weights $\mathbf{w}_t$ — the very quantity we are
differentiating. The clean step from the squared-error gradient to the update
above relied on the target being _independent_ of $\mathbf{w}$; here it is not.
A true gradient of $[U_t - \hat v(S_t, \mathbf{w})]^2$ would include a term
$-\gamma\,\nabla\hat v(S_{t+1}, \mathbf{w})$ from differentiating the target. We
**drop that term**, keeping only the gradient of the estimate at $S_t$:[^sb-sgd]

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

Because it accounts for the effect of changing $\mathbf{w}$ on the estimate but
_ignores_ its effect on the target, this is only half of a gradient. We call such
methods **semi-gradient** methods. The one above is **semi-gradient TD(0)**.

$$
% caption: Why bootstrapping is only half a gradient. The TD error depends on
% $\hat v$ at both $S_t$ and $S_{t+1}$; a true gradient would follow both (dashed),
% but semi-gradient TD(0) keeps only $\nabla\hat v(S_t)$ (solid blue) and discards
% the target's dependence on $\mathbf{w}$ (crossed-out red).
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={circle, draw, fill=white, minimum size=8mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[st] (s) at (0,0) {S(t)};
  \node[st] (sp) at (4.2,0) {S(t+1)};
  \draw[->, black] (s) -- (sp) node[midway, above, font=\scriptsize] {R(t+1)};
  % TD error bracket below
  \node[anchor=north, font=\scriptsize] at (2.1,-0.55) {target = R(t+1) + gamma v(S(t+1))};
  % kept gradient
  \draw[acc, very thick, ->] (s) to[bend left=55] (-1.7,0);
  \node[acc, anchor=east, font=\scriptsize] at (-1.75,0) {keep grad v(S(t))};
  % discarded gradient
  \draw[red, thick, ->] (sp) to[bend right=55] (5.9,0);
  \node[red, anchor=west, font=\scriptsize] at (5.95,0) {drop grad v(S(t+1))};
  \draw[red, very thick] (5.15,0.55) -- (5.75,-0.05);
  \draw[red, very thick] (5.15,-0.05) -- (5.75,0.55);
\end{tikzpicture}
$$

Semi-gradient methods do not converge as robustly as full-gradient ones, but in
the important **linear** case (next) they converge reliably, and they carry two
practical advantages that usually make them preferred. They typically learn
significantly faster, as bootstrapping did in the tabular
[TD](/reinforcement-learning/tabular-methods/temporal-difference-learning) and
[$n$-step](/reinforcement-learning/tabular-methods/n-step-bootstrapping) chapters.
And they are **continual and online**: no need to wait for the end of an episode,
so they apply to continuing tasks.[^sb-sgd]

```algorithm
caption: $\textsc{Semi-Gradient-TD}(0)$ — estimate $\hat v \approx v_\pi$
input: a policy $\pi$, a differentiable $\hat v$ with $\hat v(\text{terminal},\cdot) = 0$, step size $\alpha > 0$
$\mathbf{w} \gets$ arbitrary
for each episode do
  initialize $S$
  repeat
    choose $A \sim \pi(\cdot \mid S)$, take it, observe $R$, $S'$
    $\mathbf{w} \gets \mathbf{w} + \alpha\big[R + \gamma\,\hat v(S', \mathbf{w}) - \hat v(S, \mathbf{w})\big]\,\nabla\hat v(S, \mathbf{w})$
    $S \gets S'$
  until $S$ is terminal
```

**State aggregation** is the simplest such approximator: group states into blocks,
give each block one weight, and estimate a state's value as its block's weight.
It is a special case of SGD in which $\nabla\hat v(S_t, \mathbf{w})$ is $1$ for the
active block's component and $0$ elsewhere. Run gradient Monte Carlo with state
aggregation on a 1000-state random walk and it recovers a staircase approximation
to the true value function — piecewise constant within each block, close to the
$\overline{VE}$ minimum — visibly biased in the outer blocks toward the values of
the states within them that the on-policy distribution $\mu$ weights most.[^sb-sgd]

### Worked example: state aggregation on the 1000-state walk

Make the bias concrete. The task is a random walk on states $1, \dots, 1000$ laid
in a line, plus two terminal states off each end. From any state the agent jumps
to one of the $100$ neighbors on its left or the $100$ on its right, each with equal
probability (a jump that would cross an end lands in the terminal there, and jumps
are truncated so the probabilities on the short side pile up on the near terminal).
Reaching the left terminal pays $-1$, the right terminal $+1$, every other reward
is $0$, and $\gamma = 1$. By symmetry the true value $v_\pi(s)$ rises almost
linearly from about $-1$ near state $1$ to about $+1$ near state $1000$, passing
through $0$ at the center.

Aggregate the $1000$ states into $10$ blocks of $100$: states $1$–$100$ share
weight $w_1$, states $101$–$200$ share $w_2$, and so on. There are $d = 10$ weights
standing in for $1000$ values. What value does gradient Monte Carlo settle on for a
block? Each block's weight converges to the $\mu$-weighted average of the true
values of the states inside it, because that average is the constant that minimizes
$\sum_{s \in \text{block}} \mu(s)[v_\pi(s) - w]^2$. Setting the derivative to zero
gives $w^\ast = \sum_{s} \mu(s) v_\pi(s) / \sum_s \mu(s)$ over the block — a
$\mu$-weighted mean. In the interior blocks $\mu$ is nearly flat and $v_\pi$ nearly
linear, so the weight lands near the block's midpoint value: block $5$ (states
$401$–$500$) settles around $-0.09$, block $6$ (states $501$–$600$) around $+0.09$.
The staircase there hugs the true line.

The outer blocks are where the bias shows. Under this walk $\mu$ is not flat: the
agent starts at state $500$ and the near-terminal jumps make the states just inside
each end rarer to occupy but the states a little further in more heavily visited,
so within block $1$ (states $1$–$100$) $\mu$ leans toward the states nearer state
$100$, whose true values are higher (closer to $0$) than the states near state $1$
(closer to $-1$). The $\mu$-weighted mean is pulled up: block $1$ converges to about
$-0.56$ rather than the midpoint value near $-0.75$, and the estimated value
_flattens_ at the edges instead of continuing down to $\pm 1$. That upward flattening
in the leftmost block and the matching downward flattening in the rightmost is the
signature of state aggregation — the approximation bends toward the states the
on-policy distribution weights most, and the edges pay for it.

$$
% caption: Gradient Monte Carlo with 10-block state aggregation on the 1000-state
% random walk. The true value (thin black) is nearly linear from $-1$ to $+1$; the
% learned approximation (blue) is a staircase, one flat step per block. Interior
% steps sit on the line; the outermost steps flatten toward $\pm 0.56$ instead of
% $\pm 1$, biased toward the interior states that the on-policy distribution $\mu$
% visits more.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  % axes
  \draw[->, black] (0,0) -- (8.4,0);
  \node[anchor=north, font=\scriptsize] at (4.0,-0.25) {state (1 to 1000)};
  \draw[->, black] (0,-2.0) -- (0,2.2);
  \node[anchor=east, font=\scriptsize] at (-0.1,1.9) {value};
  \draw[black, dashed] (0,0) -- (8.0,0);
  \node[anchor=east, font=\scriptsize] at (-0.1,1.7) {+1};
  \node[anchor=east, font=\scriptsize] at (-0.1,-1.7) {-1};
  % true value line (slightly S but ~linear)
  \draw[black, thin] (0.2,-1.55) -- (7.8,1.55);
  \node[anchor=south east, font=\scriptsize] at (7.8,1.55) {true v};
  % staircase: 10 steps, interior on line, edges flattened
  \def\hw{0.78}
  \foreach \k/\v in {1/-1.42, 2/-1.15, 3/-0.87, 4/-0.55, 5/-0.19, 6/0.19, 7/0.55, 8/0.87, 9/1.15, 10/1.42} {
    \pgfmathsetmacro\xa{0.2 + (\k-1)*0.76}
    \pgfmathsetmacro\xb{0.2 + \k*0.76}
    \draw[acc, thick] (\xa,\v) -- (\xb,\v);
  }
  \node[acc, anchor=south west, font=\scriptsize] at (5.2,-1.7) {aggregated v};
\end{tikzpicture}
$$

## Linear methods

The most important special case is the one where $\hat v$ is **linear** in the
weights. To each state $s$ attach a real-valued **feature vector**

$$
\mathbf{x}(s) \;\doteq\; \big(x_1(s), x_2(s), \dots, x_d(s)\big)^\top,
$$

with the same number of components as $\mathbf{w}$. Each $x_i : \mathcal{S} \to
\mathbb{R}$ is a **feature**, and the approximate value is the inner product of
weights and features:[^sb-linear]

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

The features $\mathbf{x}(s)$ are **basis functions** — they span the set of value
functions the model can represent — and constructing good features is where a
designer injects prior knowledge about the task. In the linear case the gradient
is trivially the feature vector itself,

$$
\nabla \hat v(s, \mathbf{w}) \;=\; \mathbf{x}(s),
$$

so the general SGD update collapses to a clean form,

$$
\mathbf{w}_{t+1} \;\doteq\; \mathbf{w}_t + \alpha\big[\,U_t - \hat v(S_t, \mathbf{w}_t)\,\big]\,\mathbf{x}(S_t).
$$

$$
% caption: Linear value approximation. Each feature $x_i(s)$ multiplies a weight
% $w_i$; their inner product is the estimate $\hat v(s,\mathbf{w}) =
% \mathbf{w}^\top\mathbf{x}(s)$. The gradient is just $\mathbf{x}(s)$, so learning
% adjusts each weight in proportion to its feature's activity.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  fb/.style={draw, minimum width=11mm, minimum height=8mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[anchor=east, font=\footnotesize] at (-0.4,1.2) {state s};
  \node[fb] (x1) at (0,2.1) {x1(s)};
  \node[fb] (x2) at (0,1.2) {x2(s)};
  \node[fb] (x3) at (0,0.3) {x3(s)};
  \node[fb, draw=acc, text=acc, minimum width=13mm, minimum height=11mm] (out) at (5.0,1.2) {v(s,w)};
  \draw[->, acc] (x1) -- (out) node[pos=0.42, above, font=\scriptsize] {w1};
  \draw[->, acc] (x2) -- (out) node[pos=0.42, above, font=\scriptsize] {w2};
  \draw[->, acc] (x3) -- (out) node[pos=0.42, below, font=\scriptsize] {w3};
  \node[anchor=west, font=\scriptsize] at (5.75,1.2) {= sum of wi xi(s)};
\end{tikzpicture}
$$

The linear case is favored because it is the one we can analyze. There is a single
optimum (or a connected set of equally good optima), so any method that reaches a
local optimum reaches the global one — gradient Monte Carlo under linear features
converges to the global $\overline{VE}$ minimum.

### The TD fixed point

Gradient Monte Carlo converges to the best possible $\mathbf{w}$. Semi-gradient
TD(0) converges to a different point, stable but slightly biased.
The next few equations locate that point. At convergence
the average update must be zero, and solving that condition for
$\mathbf{w}$ gives one specific weight vector, the **TD fixed point**.

Semi-gradient TD(0) also converges under linear approximation, but not to the
global minimum, and the argument needs its own machinery. Write $\mathbf{x}_t =
\mathbf{x}(S_t)$. The linear semi-gradient TD(0) update is

$$
\mathbf{w}_{t+1} \;\doteq\; \mathbf{w}_t + \alpha\big(R_{t+1} + \gamma\,\mathbf{w}_t^\top\mathbf{x}_{t+1} - \mathbf{w}_t^\top\mathbf{x}_t\big)\,\mathbf{x}_t \;=\; \mathbf{w}_t + \alpha\big(R_{t+1}\mathbf{x}_t - \mathbf{x}_t(\mathbf{x}_t - \gamma\mathbf{x}_{t+1})^\top \mathbf{w}_t\big).
$$

Once the process reaches steady state, the expected next weight vector is

$$
\mathbb{E}[\mathbf{w}_{t+1} \mid \mathbf{w}_t] \;=\; \mathbf{w}_t + \alpha(\mathbf{b} - \mathbf{A}\mathbf{w}_t),
$$

with

$$
\mathbf{b} \doteq \mathbb{E}[R_{t+1}\mathbf{x}_t] \in \mathbb{R}^d,
\qquad
\mathbf{A} \doteq \mathbb{E}\big[\mathbf{x}_t(\mathbf{x}_t - \gamma\mathbf{x}_{t+1})^\top\big] \in \mathbb{R}^{d\times d}.
$$

If the iteration converges, it must converge to the weight vector where the
expected update is zero, $\mathbf{b} - \mathbf{A}\mathbf{w}_{\mathrm{TD}} = 0$,
that is,

$$
\mathbf{w}_{\mathrm{TD}} \;\doteq\; \mathbf{A}^{-1}\mathbf{b}.
$$

This is the **TD fixed point**, and linear semi-gradient TD(0) does converge to
it. Rewriting the expected update as $\mathbb{E}[\mathbf{w}_{t+1} \mid
\mathbf{w}_t] = (\mathbf{I} - \alpha\mathbf{A})\mathbf{w}_t + \alpha\mathbf{b}$
shows that only $\mathbf{A}$ governs stability: convergence needs $\mathbf{A}$ **positive definite**.
Under the on-policy distribution $\mathbf{A}$ factors as
$\mathbf{X}^\top \mathbf{D}(\mathbf{I} - \gamma\mathbf{P})\mathbf{X}$, where
$\mathbf{D}$ is the diagonal matrix of the $\mu(s)$ and $\mathbf{P}$ the transition
matrix; the key matrix $\mathbf{D}(\mathbf{I} - \gamma\mathbf{P})$ has all its
column sums equal to $(1-\gamma)\boldsymbol{\mu}^\top$, which is positive, and
that positivity secures positive definiteness — and the existence
of $\mathbf{A}^{-1}$.[^sb-linear] **This is why the on-policy distribution
matters.** Update states in some other proportion and the column-sum argument
collapses; $\mathbf{A}$ may cease to be positive definite, and the iteration can
diverge.

> **Definition (TD fixed point).** The weight vector $\mathbf{w}_{\mathrm{TD}} =
> \mathbf{A}^{-1}\mathbf{b}$ to which linear semi-gradient TD(0) converges under
> the on-policy distribution. It is not the global $\overline{VE}$ minimum;
> instead its error is bounded by an expansion of the smallest achievable error.

The TD fixed point's stability comes with a bias. At $\mathbf{w}_{\mathrm{TD}}$,

$$
\overline{VE}(\mathbf{w}_{\mathrm{TD}}) \;\le\; \frac{1}{1 - \gamma}\, \min_{\mathbf{w}} \overline{VE}(\mathbf{w}).
$$

The asymptotic TD error is at most $\tfrac{1}{1-\gamma}$ times the smallest error
any linear approximation can achieve — the error the Monte Carlo method reaches in
the limit. When $\gamma$ is near $1$ the factor $\tfrac{1}{1-\gamma}$ is large, so
TD can settle for a noticeably worse asymptote. In exchange it usually has far
lower variance and learns much faster, which is why it is so often preferred; the
winner depends on the problem and on how long learning runs.[^sb-linear]

### Worked example: solving for the TD fixed point by hand

For example, take a two-state
chain with a single feature per state, so $d = 1$ and $\mathbf{A}, \mathbf{b}$ are
scalars. State $A$ transitions to state $B$ with reward $0$; state $B$ transitions
back to $A$ with reward $1$; discount $\gamma = 0.9$. Give $A$ the scalar feature
$x(A) = 1$ and $B$ the feature $x(B) = 2$. The on-policy distribution is uniform,
$\mu(A) = \mu(B) = \tfrac12$, because the two states alternate.

Compute $\mathbf{A} = \mathbb{E}[x_t(x_t - \gamma x_{t+1})]$ by averaging over the
two transition types under $\mu$. From $A$: $x_t = 1$, next feature $x_{t+1} = 2$,
so the term is $1(1 - 0.9 \cdot 2) = 1(1 - 1.8) = -0.8$. From $B$: $x_t = 2$, next
feature $x_{t+1} = 1$, so the term is $2(2 - 0.9 \cdot 1) = 2(1.1) = 2.2$. Averaging,

$$
\mathbf{A} \;=\; \tfrac12(-0.8) + \tfrac12(2.2) \;=\; 0.7.
$$

Compute $\mathbf{b} = \mathbb{E}[R_{t+1} x_t]$ the same way. From $A$ the reward is
$0$, contributing $0 \cdot 1 = 0$; from $B$ the reward is $1$, contributing
$1 \cdot 2 = 2$. Averaging, $\mathbf{b} = \tfrac12(0) + \tfrac12(2) = 1$. The TD
fixed point is

$$
w_{\mathrm{TD}} \;=\; \mathbf{A}^{-1}\mathbf{b} \;=\; \frac{1}{0.7} \;\approx\; 1.43,
$$

giving $\hat v(A) = 1.43$ and $\hat v(B) = 2.86$. Note $\mathbf{A} = 0.7 > 0$ — it
is positive, which is what makes $w_{\mathrm{TD}}$ a stable attractor: the expected
update $w \gets w + \alpha(1 - 0.7\,w)$ pulls any $w$ toward $1/0.7$ for any
$0 < \alpha < 2/0.7$. Had the features been chosen so that $\mathbf{A}$ came out
negative, the same iteration would push $w$ to infinity. The positive $\mathbf{A}$
is the one-dimensional case of the positive-definiteness that the column-sum
argument guarantees under the on-policy distribution.


[^sb-intro]: **Sutton & Barto**, _Reinforcement Learning: An Introduction_ (2nd ed.), §9.1 — Value-function Approximation: the approximate value $\hat v(s,\mathbf{w}) \approx v_\pi(s)$ as a parameterized form with weight vector $\mathbf{w} \in \mathbb{R}^d$, $d \ll |\mathcal{S}|$; how a single update generalizes across states, and why this makes reinforcement learning applicable to partially observable problems.
[^sb-ve]: **Sutton & Barto**, §9.2 — The Prediction Objective ($\overline{VE}$): the Mean Squared Value Error (9.1) weighted by a state distribution $\mu$, the on-policy distribution and the episodic-task visit equations (9.2)–(9.3), and the distinction between global and local optima.
[^sb-vfa]: **Sutton & Barto**, §9.1 — the $s \mapsto u$ / $s \mapsto g$ framing of every update as a supervised-learning example, the Monte Carlo, TD(0), $n$-step, and DP update targets, and the online and nonstationarity requirements that rule out static batch methods.
[^sb-sgd]: **Sutton & Barto**, §9.3 — Stochastic-gradient and Semi-gradient Methods: the SGD update (9.4)–(9.7), the unbiasedness condition for convergence, the Gradient Monte Carlo box, the semi-gradient argument (dropping the target's gradient because it bootstraps), the Semi-gradient TD(0) box, and state aggregation (Example 9.1, 1000-state random walk).
[^sb-linear]: **Sutton & Barto**, §9.4 — Linear Methods: the feature vector $\mathbf{x}(s)$ and $\hat v = \mathbf{w}^\top\mathbf{x}(s)$ (9.8), the linear SGD update, the expected-update matrices $\mathbf{A}$ and $\mathbf{b}$ (9.9)–(9.11), the TD fixed point $\mathbf{w}_{\mathrm{TD}} = \mathbf{A}^{-1}\mathbf{b}$ (9.12), the positive-definiteness / column-sum proof of convergence, and the $\overline{VE}$ bound (9.14).