Feature Construction and Nonlinear Approximation

This builds on on-policy prediction with approximation, which set up the linear value function $\hat{v}(s,\mathbf{w})={\mathbf{w}}^{\top }\mathbf{x}(s)$ and showed that semi-gradient TD(0) converges to a clean fixed point in that setting. That lesson left one thing unspecified: where the feature vector $\mathbf{x}(s)$ comes from. A linear model is only a readout on top of its features, so the features decide everything the model can represent. This lesson is about building them — first by hand, in several standard families, and then by letting a neural network learn them for us.

Feature construction

Linear methods are only as good as their features. Because $\hat{v}$ is a linear combination of the $x_i(s)$, it cannot represent interactions between features unless a feature encodes the interaction directly. In pole-balancing, high angular velocity is dangerous at a large pole angle but stabilizing at a small one; a linear model with separate features for angle and velocity can never express that — it needs a feature for the combination.¹ The families below are different answers to the question of which features to build.

The families split along one intuitive line. Polynomials and the Fourier basis are global: each feature is a smooth function spanning the whole state space, good for capturing broad trends. Coarse coding, tile coding, and radial basis functions are local: each feature responds only near one region, good for carving a continuous space into pieces that generalize to their neighbors and nowhere else.

Polynomials and the Fourier basis

The oldest answer borrows from interpolation and regression. If a state is $k$ numbers $s_1,\dots ,s_k$, an order-$n$ polynomial feature is a product of their powers,

which gives $(n+1{)}^k$ features. The constant $1$ among them lets the model fit affine functions, and cross terms like $s_1{s}_2$ let it fit interactions. Polynomials are simple and familiar, but the feature count explodes with dimension and they extrapolate badly, so they are rarely the best choice for online RL.

The Fourier basis usually works better. It represents a function as a weighted sum of cosines of different frequencies. For a $k$-dimensional state $\mathbf{s}\in [0,1{]}^k$, the order-$n$ Fourier cosine basis has one feature per integer vector ${\mathbf{c}}^i=(c_1^i,\dots ,c_k^i{)}^{\top }$ with $c_j^i\in \{0,\dots ,n\}$:

The vector ${\mathbf{c}}^i$ sets each dimension's frequency: a zero in a slot means the feature is constant along that state dimension, and a nonzero pair $(c_1,c_2)$ produces a feature that varies along both — an interaction whose orientation is set by their ratio. Fourier features are easy to select (limit the $\mathbf{c}$ entries to cap frequency) and perform well across a range of problems; on the 1000-state random walk they beat polynomials cleanly.¹

Work the one-dimensional case to see the feature vector. Scale the state to $s\in [0,1]$ and take the order-$n=4$ Fourier cosine basis, which for a scalar state is $x_i(s)=\cos (\pi is)$ for $i=0,1,2,3,4$ — five features. At the midpoint $s=0.5$ the feature vector is

the alternating pattern that any half-integer argument produces. At $s=0.25$ it is $(1,0.707,0,-0.707,-1)$. The constant feature $x_0\equiv 1$ carries the average value; the higher-frequency features let the model bend to finer structure. An order-$n$ polynomial basis over the same scalar state is instead $x_i(s)=s^i$, so at $s=0.5$ it is $(1,0.5,0.25,0.125,0.0625)$ — powers that shrink fast and are all positive. That uniform sign is why polynomials struggle to represent the sign changes of a value function, and why they extrapolate poorly past the range they were fit on. The Fourier features, bounded in $[-1,1]$ and oscillating, do not have that defect. A practical detail: because Fourier feature $i$ carries frequency proportional to $i$, a good rule of thumb scales its step size by $1/\Vert {\mathbf{c}}^i\Vert$ so high-frequency features, which change fastest, learn slower and do not dominate.

Coarse coding

For continuous state spaces a different idea works: cover the space with overlapping regions (receptive fields) and let each be a binary feature — $1$ if the state lies inside, $0$ otherwise. Which fields a state is inside is a coarse code for its location. This is coarse coding, and its overlap is what produces generalization: training at one state adjusts the weights of every field containing it, so nearby states — those sharing fields — are pulled along, while distant states, sharing none, are untouched.¹

The size and shape of the fields decide the reach of generalization: small fields generalize over a short distance, large fields over a long one, and fields stretched along one axis generalize mainly along that axis. What they do not decide is the ultimate acuity. One might expect broad fields to blur fine detail permanently, but they do not: initial generalization is governed by field size, while the finest discrimination possible is governed by the sheer number of features. Broad fields learn fast and coarse early, yet with enough of them the final approximation is nearly as sharp as with narrow ones.

Tile coding

Tile coding is coarse coding made practical for multi-dimensional continuous spaces. Partition the state space into a grid — each partition is a tiling, each cell a tile — and use several tilings, each offset from the last by a fraction of a tile width. A state falls in exactly one tile per tiling, so the number of active (value-$1$) features always equals the number of tilings, no matter where the state is.¹

The fixed active count simplifies tuning. The step size can be set intuitively — choosing $\alpha =1/n$ for $n$ tilings gives exact one-trial learning, $\alpha =1/(10n)$ moves a trained state one-tenth of the way to its target. And because features are binary, computing $\hat{v}={\mathbf{w}}^{\top }\mathbf{x}(s)$ is nearly free: rather than $d$ multiplications, just sum the $n$ weights of the active tiles. How the tilings are offset shapes generalization. Uniform offsets — every tiling shifted the same way in each dimension — leave diagonal artifacts; asymmetric offsets (displacement vectors of the first odd integers, e.g. $(1,3)$ rather than $(1,1)$) center generalization more evenly on the trained state. Elongated tiles generalize along their long axis, and mixing stripe-shaped and rectangular tilings gives both broad generalization and the ability to learn specific conjunctions.

Radial basis functions

Radial basis functions (RBFs) generalize coarse coding to graded features. Instead of a binary $0$/$1$, an RBF feature responds with a value in $[0,1]$ depending on how close the state is to a center $c_i$, typically a Gaussian of width ${\sigma }_i$:¹

RBFs produce smooth, differentiable approximations, which is appealing, but the smoothness rarely helps enough to justify the extra computation over tile coding, and in high dimensions they tend to fall behind. Left as fixed centers and widths, an RBF network is an ordinary linear approximator; let learning adjust the centers and widths too and it becomes nonlinear, more expressive but harder to tune.

Nonlinear approximation and the bridge to deep RL

Every feature family so far builds a good $\mathbf{x}(s)$ by hand and then learns a linear readout on top. The remaining move is the one that defines modern RL: stop designing features and learn the representation itself.

An artificial neural network stacks layers of units, each computing a weighted sum of its inputs followed by a nonlinear activation $f$ — the logistic $f(x)=1/(1+e^{-x})$ or the rectifier $f(x)=\max (0,x)$ — and adjusts all the weights, in every layer, by gradient descent through backpropagation.²

A single hidden layer of enough units is already a universal approximator, but depth matters for the same reason it does elsewhere: hierarchical, compositional features are learned far more efficiently by many layers than by one. Nonlinear approximation gains precision and automates feature design, at the cost of convergence guarantees and more tuning. This leads to deep reinforcement learning: replace $\hat{v}(s,\mathbf{w})={\mathbf{w}}^{\top }\mathbf{x}(s)$ with a deep network, keep the semi-gradient update, and the same $\overline{VE}$ objective now drives a network that learns its own features from raw state.

From tile coding to deep value functions

The chapter's feature machinery remains in practical use, and the two endpoints — the oldest linear representation and the newest deep one — are worth naming precisely.

Tile coding as CMAC. Tile coding is not new to reinforcement learning; it is the cerebellar model articulation controller (CMAC) proposed by Albus (1975), A new approach to manipulator control: The cerebellar model articulation controller, Journal of Dynamic Systems, Measurement, and Control.³ Its use as a value-function representation, and the practice of hashing many tilings down to a manageable weight vector, was developed by Sutton (1996), Generalization in reinforcement learning: Successful examples using sparse coarse coding, NeurIPS, which showed sparse coarse coding solving continuous control tasks — the direct ancestor of the Mountain Car tile coding in a later lesson. The binary, sparse, fixed-active-count structure is what makes the $O(n)$-per-step arithmetic and the intuitive $\alpha =1/n$ step-size rule possible.

Deep value functions and where the guarantees stop. Swapping the linear readout for a deep network is what Mnih et al. (2015), Human-level control through deep reinforcement learning, Nature, did to reach human-level play on Atari from raw pixels.⁴ The move keeps the $\overline{VE}$ objective and the semi-gradient update but loses the convergence theory of the previous lesson: with a nonlinear $\hat{v}$, $\mathbf{A}$ is no longer a fixed positive-definite matrix, the fixed-point bound $\frac{1}{1-\gamma }\min \overline{VE}$ does not apply, and training can oscillate or diverge. Deep RL recovers stability with engineering rather than theory — a replay buffer that breaks the correlation between consecutive samples and a slowly updated target network that freezes the bootstrap target, so the shifting-target problem of semi-gradient learning is damped. The instability itself sharpens into a named failure — the deadly triad — once off-policy training is added on top.