Sutton & Barto Chapter 9 — On-policy Prediction with Approximation Explained

// the one-minute version

A value table remembers; a function approximator generalizes. We replace one number per state with v̂(s,w), choose an objective that says which prediction errors matter, and update a shared parameter vector from experience generated by the policy being evaluated. Monte Carlo supplies an unbiased supervised target. TD supplies a cheaper, bootstrapped target and therefore uses a semi-gradient. With linear functions, feature design determines what “similar states” means; tile coding, Fourier bases, radial basis functions, and neural networks express different assumptions. The central lesson is not merely how to fit a curve. It is how to control the compromises forced by sharing parameters across states.

Asha’s warehouse robot has outgrown its lookup table. Its state includes position measured in millimetres, velocity, battery temperature, payload weight, and dozens of sensor readings. Even if each variable is coarsely discretized, the Cartesian product is astronomical. Worse, most exact combinations will never repeat. A table would treat “battery 61.0%” and “battery 61.1%” as strangers. Asha needs learning from one state to improve predictions in related states. That useful sharing—and the mistakes it can spread—is the subject of Chapter 9.

01 From drawers to a prediction machine

In the tabular case, v(s) is a drawer labelled by state s. Updating one drawer leaves every other drawer untouched. Approximation replaces the drawers with a machine:

predictionv̂(s,w) ≈ v_π(s), where w ∈ ℝ^d is one shared parameter vector.

The hat means “approximation.” Feed the machine a state and it returns a value. Learning changes w, so one update can alter predictions for many states. This is generalization. It is necessary when the state set is huge, continuous, or partially observed, but it creates interference: making one prediction better can make another worse.

Chapter 9 is on-policy prediction. The policy π is fixed, and the same policy generates the training trajectory. We are not yet choosing actions; we are estimating the return that will follow from states visited under π.

02 Approximation forces us to say what “best” means

If the function class cannot represent every true value exactly, there is no universally perfect w. We need a loss. Sutton and Barto use the mean-squared value error

objectiveVE(w) = Σ_s μ(s)[v_π(s) − v̂(s,w)]²,

where μ(s) is the fraction of time the on-policy process spends in s. This weighting is not decoration: it decides whose errors count. Frequently visited states dominate; unreachable states receive no weight. Under continuing ergodic tasks μ is the stationary distribution induced by π. In episodic tasks it is proportional to expected visits per episode.

This explains an apparent puzzle. An algorithm may reduce prediction accuracy in a rare state while improving VE overall. Approximation is a negotiated compromise over a distribution, not a promise of uniform accuracy.

03 Stochastic gradient descent from first principles

Suppose experience provides a target U_t for v_π(S_t). For the instantaneous squared error [U_t−v̂(S_t,w)]², calculus says move w opposite the loss gradient. Constants can be absorbed into the step size:

general SGDw_t+1 = w_t + α[U_t − v̂(S_t,w_t)]∇v̂(S_t,w_t).

The bracket is the prediction error. The gradient tells which parameters caused the current output. Their product assigns credit. If U_t is an unbiased sample of v_π(S_t), the expected update follows the gradient of VE. The step-size schedule must balance rapid learning against persistent noise; classical convergence uses diminishing steps whose sum is infinite but whose squared sum is finite.

04 Monte Carlo is ordinary supervised learning; TD is not

For episodic Monte Carlo, choose U_t=G_t. Because the return is an unbiased sample of the true value, gradient Monte Carlo is genuine stochastic gradient descent. It waits until the episode ends and can have high variance, but its target does not depend on w.

One-step TD instead chooses U_t=R_t+1+γv̂(S_t+1,w_t). Now the target contains the same parameters being changed. Semi-gradient TD deliberately differentiates the current prediction but treats the target as fixed:

semi-gradient TD(0)δ_t=R_t+1+γv̂(S_t+1,w_t)−v̂(S_t,w_t); w←w+αδ_t∇v̂(S_t,w).

“Semi” is a precise warning, not an insult. The update is not the full gradient of the squared TD error. In the on-policy linear setting it nevertheless converges under standard conditions to a well-defined approximation near the best representable value.

05 Linear approximation makes representation visible

Let x(s) be a feature vector. A linear value function is v̂(s,w)=wᵀx(s). Its gradient is simply x(s), so TD becomes w←w+αδx(S_t). Only active features change.

Feature design is an inductive bias: it decides which states share each update.

If every state has a one-hot feature, linear approximation reproduces a table. The power comes from overlapping features. Asha can encode “high payload,” “turning quickly,” and “warm battery” separately, letting experience transfer across many exact sensor combinations.

06 Bases and receptive fields: different meanings of similarity

Polynomial bases use powers and interactions of normalized state variables. They can represent smooth global trends, but high orders are poorly scaled and one coefficient affects the whole space. Fourier bases use cosines at different frequencies; low frequencies express broad trends and higher ones add detail.

Coarse coding covers the state space with overlapping receptive fields. A state activates every field containing it. Broad fields generalize widely; narrow fields preserve local detail. Tile coding overlays several offset grids. Each state activates one tile per tiling, producing sparse binary features. The offsets make the combined representation much finer than any single grid. A useful default is to divide α by the number of simultaneously active tiles because one observation updates all of them.

Radial basis functions replace hard membership with graded activation, often exp(−‖s−c_i‖²/2σ²). The width σ controls smoothness. All these constructions answer the same scientific question: which distinctions in the state are relevant to predicting return?

07 Choosing step sizes and building features in practice

Scale inputs before using global bases; otherwise one large-magnitude dimension dominates. For sparse binary features, normalize the step size by the number of active features. For general features, a safe bound relates α to the expected squared feature norm, although tuning still matters.

The book’s random-walk experiments reveal the trade-off. Coarse features learn quickly because each sample influences a region, but their asymptotic shape may be biased. Finer representations can approach the truth more closely but require more data. This is the approximation version of bias versus variance.

Asha’s implementationShe begins with eight offset tilings over position and battery temperature. One transition activates eight features. A positive TD error raises all eight weights, improving the current state and nearby states that share some tiles. She plots predictions against held-out Monte Carlo returns—not merely training reward—to see both generalization and interference.

08 Beyond basic SGD: networks, least squares, and memory

A multilayer neural network can learn features rather than fixing them. Backpropagation supplies ∇v̂, so the same semi-gradient TD template applies. But nonlinear approximation makes the optimization landscape and moving bootstrap targets harder; input normalization, initialization, replay distribution, and step size become part of the algorithm.

Least-squares TD (LSTD) collects linear equations implied by TD’s fixed point and solves for w, usually with regularization. It is data-efficient but costs more memory and computation than incremental TD. Kernel and memory-based methods keep representative examples and predict through similarity to them. They can adapt their resolution to data, but an unrestricted memory grows without bound, so sparsification or prototype selection is required.

The chapter also introduces state aggregation—a special linear representation where many states share one component—as a clean way to reason about approximation error.

09 Interest and emphasis: learning is also an allocation problem

The visitation distribution μ determines the default objective, but a designer may care about states differently. An interest function can express this preference. Later chapters turn interest into emphatic weighting for stable off-policy learning. The important first-principles point is that data frequency, scientific importance, and update weight are different quantities. A safety-critical rare state may deserve deliberate sampling or extra emphasis even when π seldom visits it.

gotchasApproximation is not just compression. It asserts a geometry of similarity. Do not report one seed, test only visited states, or assume a smaller training TD error means a better value estimate. A bootstrapped target can agree with itself while being wrong. Inspect coverage, compare against independent returns where possible, and vary the representation as well as the optimizer.

10 Questions a master’s student should be able to answer

Why is on-policy linear TD comparatively well behaved?

The update’s expected dynamics have a stable fixed point under standard coverage and step-size assumptions. It converges to the projection of the Bellman solution into the representable feature space—not generally the exact value, but a bounded approximation. Off-policy sampling breaks this favorable geometry, which motivates Chapter 11.

Why does Monte Carlo minimize VE while TD generally does not?

Monte Carlo returns are unbiased targets for the true values, so expected SGD follows the gradient of VE. TD targets bootstrap from the current approximation; its fixed point is a projected Bellman equation. TD can learn faster despite settling at a different point.

How is tile coding different from discretizing into one grid?

A single grid creates arbitrary discontinuities at bin borders. Multiple offset tilings make nearby points share most, but not necessarily all, active features. This provides local generalization with controllable resolution and avoids relying on one boundary placement.

When should I prefer linear features to a neural network?

Prefer them when data is limited, the state variables already have meaningful structure, fast online updates and reproducibility matter, or you need theoretical clarity. Neural networks become attractive when useful features must be learned from high-dimensional raw observations.

What is the minimum convincing experiment?

Define the evaluation distribution, compare predicted values with independent return estimates or known truth, run multiple seeds, plot learning curves and final error, sweep meaningful step sizes, and inspect which regions lack data. Reward alone cannot validate a prediction method.

11 Chapter summary and exam-ready map

Why approximation: large or continuous state spaces require generalization from visited states to related ones.
Objective: VE is a state-distribution-weighted squared error; the weighting determines the compromise.
Gradient MC: uses complete unbiased returns and is true SGD.
Semi-gradient TD: bootstraps, treats the target as fixed, and usually learns more efficiently on-policy.
Linear methods: v̂=wᵀx makes the gradient equal to the features and exposes the role of representation.
Feature families: polynomial and Fourier bases are global; coarse coding, tile coding, and RBFs are local in different ways.
Beyond linearity: neural networks learn features; LSTD solves a batch fixed point; kernel methods remember similar examples.
Scientific habit: state the evaluation distribution and inspect generalization, coverage, stability, and seed variation.

// master’s study sheetchapter 9

derive

loss → updateDifferentiate ½[U−v̂(s,w)]² to recover w←w+α[U−v̂]∇v̂.

linear TDSubstitute v̂=wᵀx and ∇v̂=x into the semi-gradient TD update.

distinguish

MC vs TDUnbiased completed-return target versus lower-variance bootstrapped target; true gradient versus semi-gradient.

feature choicesGlobal basis, hard local overlap, soft local overlap, or learned nonlinear representation.

implement

experimentUse a continuous random walk or mountain-car state, tile code it, sweep α/number of tilings/width, and measure value RMS error across seeds.

diagnosePlot visitation, independent return targets, prediction residuals by region, and weight or gradient norms.

12 Source trail and scope

These are independent companion notes, not a replacement for the textbook. The chapter organization follows Sutton and Barto's second edition; explanations and examples here are original. Use the authors' book page, the MIT Press edition page, and the official table of contents for the primary source and exact section sequence.

Chapter 9 — On-policy Prediction with Approximation, explained.