Linear in the weights
Linear function approximation writes the value as a dot product: v̂(s, w) = wᵀx(s), where x(s) is a feature vector describing the state and w is the learnable weight on each feature. 'Linear' refers to the weights, not the state — the features themselves can be wildly nonlinear functions of the raw state. This is the same trick as linear regression with engineered features.
The linear value estimate is just the dot product of the weight vector and the state's feature vector.
Why start linear when neural networks exist? Because linear methods have a single, well-understood optimum, converge under clear conditions, are cheap to update, and — as later guides show — are the safe corner of the deadly triad. They remain the right tool whenever good features are available, and they are the cleanest place to understand everything that can go wrong.
The art of feature construction
With linear methods, all the modelling power lives in the features. Feature construction asks: what numbers about the state let a weighted sum express the value well? Good features make nearby-in-value states nearby-in-feature-space, so that learning at one point spills helpfully onto its neighbours — that controlled spillover is generalization.
Diagram of a dot product as similarity: a dot b equals the product of the magnitudes times the cosine of the angle between the vectors.
Three classic families dominate practical linear RL, all variations on one idea: cover the state space with overlapping receptive fields, and let a state's features record which fields it falls inside. We will take them in order of increasing smoothness.
Coarse coding: overlapping blobs
Coarse coding scatters overlapping regions — think circles — across the state space. A feature is 1 if the state lies inside that region and 0 otherwise. Because the circles overlap, each state activates several features, and two nearby states share most of theirs. Update one state and every state sharing a circle moves with it. The size of the circles sets the generalization width: big circles spread learning far but blur detail; small circles stay sharp but generalize little — the same dial as state aggregation, now smooth.
Tile coding: the workhorse
Tile coding is coarse coding made fast and tidy. Lay several grids ('tilings') over the state space, each offset slightly from the others. A state lands in exactly one tile per tiling, so its feature vector is binary with exactly one '1' per tiling — cheap to compute and cheap to update. The offsets between tilings give the smooth generalization; the number of tilings sets the resolution. Because only a handful of features are active, the dot product is a fast sum of a few weights.
Radial basis functions: soft membership
Tile features are 0/1 — a state is in a tile or it isn't. Radial basis functions (RBFs) soften that to a graded membership: each feature is a Gaussian bump centred somewhere, returning a value near 1 when the state is close to the centre and fading smoothly to 0 farther away. The result is a continuous, differentiable feature vector, which can represent smoothly varying values with fewer features — at the cost of tuning each bump's width and choosing where to place the centres.
A radial basis feature is a Gaussian bump centred at c_i, giving graded membership that fades with distance.
Notice the progression: aggregation (one hard bucket) → coarse coding (overlapping hard blobs) → tile coding (structured hard tiles) → RBFs (soft Gaussian blobs). Each step trades a little speed and simplicity for smoother generalization. Whatever you pick, the learning rule for the weights is identical — and that rule is the next guide.