On-Policy Prediction with 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$,¹

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.¹

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.²

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:

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.

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}$:

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

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.²

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:

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.³ 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:⁴

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.

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:

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.⁴

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$:⁴

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

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 and $n$-step chapters. And they are continual and online: no need to wait for the end of an episode, so they apply to continuing tasks.⁴

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.⁴

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.

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

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:⁵

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,

so the general SGD update collapses to a clean form,

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

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

with

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,

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 ){\mathbf{\mu }}^{\top }$, which is positive, and that positivity secures positive definiteness — and the existence of ${\mathbf{A}}^{-1}$.⁵ 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.

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

The asymptotic TD error is at most $\frac{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 $\frac{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.⁵

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)=\frac{1}{2}$, 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,

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}=\frac{1}{2}(0)+\frac{1}{2}(2)=1$. The TD fixed point is

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\leftarrow w+\alpha (1-0.7w)$ 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.