---
title: "Feature Construction and Nonlinear Approximation"
module: Approximate Solution Methods
moduleNumber: 3
lessonNumber: 2
order: 302
summary: >
  Linear methods are only as good as the feature vectors $\mathbf{x}(s)$ fed to
  them, and this lesson builds those vectors. Polynomials and the Fourier basis
  turn a state's coordinates into smooth global features; coarse coding, tile
  coding, and radial basis functions cover a continuous space with overlapping
  local receptive fields whose size sets the reach of generalization. Then we
  stop designing features by hand: a neural network learns the representation
  itself by gradient descent, trading the convergence guarantees of the linear
  case for expressiveness — the bridge to deep reinforcement learning.
topics: [Approximation]
sources:
  - book: Sutton & Barto
    ref: "Ch. 9 — On-policy Prediction with Approximation; §9.5 Feature Construction for Linear Methods"
  - book: Sutton & Barto
    ref: "§9.7 Nonlinear Function Approximation: Artificial Neural Networks"
---

This builds on
[on-policy prediction with approximation](/reinforcement-learning/approximation/on-policy-prediction),
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_.[^sb-features] 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,

$$
x_i(s) \;=\; \prod_{j=1}^k s_j^{\,c_{i,j}}, \qquad c_{i,j} \in \{0, 1, \dots, n\},
$$

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^i_1, \dots, c^i_k)^\top$ with $c^i_j \in \{0, \dots, n\}$:

$$
x_i(s) \;=\; \cos\!\big(\pi\, \mathbf{s}^\top \mathbf{c}^i\big).
$$

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.[^sb-features]

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\, i\, s)$ for $i = 0, 1, 2, 3, 4$ — five features. At
the midpoint $s = 0.5$ the feature vector is

$$
\mathbf{x}(0.5) = \big(\cos 0,\ \cos \tfrac{\pi}{2},\ \cos \pi,\ \cos \tfrac{3\pi}{2},\ \cos 2\pi\big) = (1,\ 0,\ -1,\ 0,\ 1),
$$

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/\lVert
\mathbf{c}^i \rVert$ so high-frequency features, which change fastest, learn slower
and do not dominate.

$$
% caption: Two-dimensional Fourier cosine features $\cos(\pi\,\mathbf{s}^\top
% \mathbf{c})$ for a few frequency vectors $\mathbf{c}$. A zero in a slot makes the
% feature flat along that axis; nonzero entries in both slots give a diagonal
% ripple whose orientation is the ratio of frequencies.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  % three little unit squares with sketched wave stripes
  \begin{scope}
    \draw[black] (0,0) rectangle (2,2);
    \node[anchor=south, font=\scriptsize] at (1,2.05) {c = (1,0)};
    \foreach \x in {0.4,0.8,1.2,1.6} \draw[acc] (\x,0) -- (\x,2);
    \node[anchor=north, font=\scriptsize] at (1,-0.1) {f\/lat vertically};
  \end{scope}
  \begin{scope}[xshift=3.2cm]
    \draw[black] (0,0) rectangle (2,2);
    \node[anchor=south, font=\scriptsize] at (1,2.05) {c = (0,1)};
    \foreach \y in {0.4,0.8,1.2,1.6} \draw[acc] (0,\y) -- (2,\y);
    \node[anchor=north, font=\scriptsize] at (1,-0.1) {f\/lat horizontally};
  \end{scope}
  \begin{scope}[xshift=6.4cm]
    \node[anchor=south, font=\scriptsize] at (1,2.05) {c = (1,1)};
    \begin{scope}
      \clip (0,0) rectangle (2,2);
      \foreach \d in {-2.0,-1.4,-0.8,-0.2,0.4,1.0,1.6} \draw[acc] (\d,0) -- (\d+2,2);
    \end{scope}
    \draw[black] (0,0) rectangle (2,2);
    \node[anchor=north, font=\scriptsize] at (1,-0.1) {diagonal};
  \end{scope}
\end{tikzpicture}
$$

### 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.[^sb-features]

$$
% caption: Coarse coding. State $s$ activates the features whose receptive fields
% (circles) contain it; training at $s$ moves those weights, so a nearby state
% $s'$ sharing one field generalizes slightly, while a distant state sharing none
% does not.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  % overlapping circles
  \foreach \cx/\cy in {0/0, 1.1/0.4, 0.5/1.1, -0.6/0.6, 0.3/-0.9, 1.4/-0.5, -0.4/-0.5} {
    \draw[black] (\cx,\cy) circle (0.95);
  }
  % state s inside several
  \fill[acc] (0.35,0.35) circle (2.4pt);
  \node[acc, anchor=south west, font=\scriptsize] at (0.45,0.45) {s};
  % state s' sharing one field
  \fill[black] (1.75,0.55) circle (2.4pt);
  \node[anchor=west, font=\scriptsize] at (1.9,0.55) {s' (one f\/ield shared)};
\end{tikzpicture}
$$

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.

$$
% caption: Field width sets early generalization, not final acuity. Broad fields
% (right) spread each update widely and learn a smooth approximation fast; narrow
% fields (left) change only close neighbors and stay bumpy longer; with enough
% examples all three converge to nearly the same target function.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  % target square wave (shared shape, drawn faint at top)
  \foreach \col/\lab/\shift in {0/{narrow}/0, 3.6/{medium}/3.6, 7.2/{broad}/7.2} {
    \begin{scope}[xshift=\col cm]
      % early (bumpy vs smooth)
      \draw[black] (0,2.6) -- (0.8,2.6) -- (0.8,3.2) -- (1.8,3.2) -- (1.8,2.6) -- (2.6,2.6);
      \node[anchor=south, font=\scriptsize] at (1.3,3.25) {\lab};
    \end{scope}
  }
  % early approximations row
  \node[anchor=east, font=\scriptsize] at (-0.15,1.6) {early};
  \draw[acc] (0,1.4) sin (0.4,1.9) cos (0.8,1.5) sin (1.2,2.0) cos (1.6,1.4) sin (2.0,1.9) cos (2.6,1.5);
  \draw[acc] (3.6,1.5) .. controls (4.2,1.5) and (4.5,2.0) .. (5.0,1.95) .. controls (5.5,2.0) and (5.8,1.5) .. (6.2,1.5);
  \draw[acc] (7.2,1.6) .. controls (8.0,1.65) and (8.4,1.9) .. (8.8,1.9) .. controls (9.2,1.9) and (9.6,1.65) .. (9.8,1.6);
  % late approximations row (all near the square wave)
  \node[anchor=east, font=\scriptsize] at (-0.15,0.4) {late};
  \foreach \col in {0,3.6,7.2} {
    \draw[acc] (\col,0.2) -- (\col+0.8,0.2) -- (\col+0.8,0.8) -- (\col+1.8,0.8) -- (\col+1.8,0.2) -- (\col+2.6,0.2);
  }
\end{tikzpicture}
$$

### 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.[^sb-features]

$$
% caption: Tile coding. Four grid tilings, each offset by a fraction of a tile
% width, cover the state space; the query point falls in exactly one tile per
% tiling, so it activates four features. The number active is always the number
% of tilings.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % four offset grids
  \draw[black] (0,0) grid[step=1] (3,3);
  \draw[acc!70, xshift=6, yshift=6] (0,0) grid[step=1] (3,3);
  \draw[red!60, xshift=12, yshift=-6] (0,0) grid[step=1] (3,3);
  \draw[black, xshift=-6, yshift=12] (0,0) grid[step=1] (3,3);
  % the four active tiles highlighted (approx overlapping around the point)
  \draw[black, very thick] (1,1) rectangle (2,2);
  \draw[acc, very thick, xshift=6, yshift=6] (1,1) rectangle (2,2);
  \draw[red, very thick, xshift=12, yshift=-6] (1,1) rectangle (2,2);
  \draw[black, very thick, xshift=-6, yshift=12] (1,1) rectangle (2,2);
  % the query point (drawn last, on top) with a leader to a clear label
  \fill[black] (1.55,1.45) circle (2.8pt);
  \draw[black] (1.55,1.45) -- (1.9,-0.65);
  \node[anchor=north, font=\scriptsize] at (1.9,-0.7) {query point};
  \node[anchor=west, font=\scriptsize] at (3.7,1.9) {4 active tiles};
  \node[anchor=west, font=\scriptsize] at (3.7,1.4) {= 4 features on};
\end{tikzpicture}
$$

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$:[^sb-features]

$$
x_i(s) \;\doteq\; \exp\!\left(-\frac{\lVert s - c_i \rVert^2}{2\sigma_i^2}\right).
$$

$$
% caption: One-dimensional radial basis functions. Each feature $x_i(s) =
% \exp(-\lVert s - c_i\rVert^2 / 2\sigma_i^2)$ is a Gaussian bump centered at
% $c_i$ with width $\sigma_i$; a state's feature vector reads off each bump's
% height at that point.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \draw[black] (-0.3,0) -- (7.3,0);
  % three gaussian bumps
  \draw[acc, thick] plot[domain=-0.2:3.0, samples=40] (\x, {2.0*exp(-((\x-1.4)^2)/0.35)});
  \draw[acc, thick] plot[domain=1.0:5.2, samples=40] (\x, {2.0*exp(-((\x-3.5)^2)/0.35)});
  \draw[acc, thick] plot[domain=3.2:7.2, samples=40] (\x, {2.0*exp(-((\x-5.6)^2)/0.35)});
  \foreach \cx/\lab in {1.4/c(i-1), 3.5/c(i), 5.6/c(i+1)} {
    \fill[black] (\cx,0) circle (1.6pt);
    \node[anchor=north, font=\scriptsize] at (\cx,-0.08) {\lab};
  }
  % width marker on the middle bump
  \draw[black, <->] (3.5,1.0) -- (4.1,1.0);
  \node[anchor=west, font=\scriptsize] at (4.15,1.0) {width sigma(i)};
\end{tikzpicture}
$$

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](/deep-learning/neural-networks/backpropagation).[^sb-nonlinear]

$$
% caption: A feedforward network as a nonlinear value approximator. The state
% enters as inputs, hidden layers compute learned features, and the output unit
% reads off $\hat v(s,\mathbf{w})$; unlike tile coding the features here are
% learned, not designed.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  u/.style={circle, draw, minimum size=5mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  % input layer (3 units)
  \foreach \i/\y in {1/0, 2/0.9, 3/1.8} \node[u] (i\i) at (0,\y) {};
  % hidden layer 1 (4 units)
  \foreach \i/\y in {1/-0.4, 2/0.5, 3/1.4, 4/2.3} \node[u] (a\i) at (1.8,\y) {};
  % hidden layer 2 (4 units)
  \foreach \i/\y in {1/-0.4, 2/0.5, 3/1.4, 4/2.3} \node[u] (b\i) at (3.6,\y) {};
  % output
  \node[u, draw=acc, text=acc] (o) at (5.4,0.9) {};
  \foreach \p in {1,2,3} \foreach \q in {1,2,3,4} \draw[black] (i\p) -- (a\q);
  \foreach \p in {1,2,3,4} \foreach \q in {1,2,3,4} \draw[black] (a\p) -- (b\q);
  \foreach \p in {1,2,3,4} \draw[acc] (b\p) -- (o);
  \node[anchor=north, font=\scriptsize] at (0,-0.75) {state s};
  \node[anchor=north, font=\scriptsize] at (2.7,-0.9) {learned features};
  \node[acc, anchor=west, font=\scriptsize] at (5.75,0.9) {v(s,w)};
\end{tikzpicture}
$$

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](/reinforcement-learning/deep-rl/deep-q-networks):
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_.[^tile] 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.[^dqn] 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 $\tfrac{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](/reinforcement-learning/approximation/off-policy-and-the-deadly-triad) —
once off-policy training is added on top.

[^sb-features]: **Sutton & Barto**, _Reinforcement Learning: An Introduction_ (2nd ed.), §9.5 — Feature Construction for Linear Methods: polynomials (9.17), the Fourier cosine basis (9.18) with Figures 9.3–9.5, coarse coding (Figures 9.6–9.8), tile coding (Figures 9.9–9.12, asymmetric offsets and hashing), and radial basis functions (9.13) with the RBF-network remark.
[^sb-nonlinear]: **Sutton & Barto**, §9.7 — Nonlinear Function Approximation: Artificial Neural Networks: feedforward ANNs (Figure 9.14), semi-linear units with sigmoid or rectifier activations, the universal-approximation property of one hidden layer, and why deep, hierarchical representations are learned more efficiently by many layers.
[^tile]: **Albus, J. S.** (1975), "A new approach to manipulator control: The cerebellar model articulation controller (CMAC)", _Journal of Dynamic Systems, Measurement, and Control_, 97(3), 220–227 — the tiling/CMAC representation. **Sutton, R. S.** (1996), "Generalization in reinforcement learning: Successful examples using sparse coarse coding", _Advances in Neural Information Processing Systems_ 8 — sparse coarse (tile) coding as a value-function representation, with tiling hashing.
[^dqn]: **Mnih, V. et al.** (2015), "Human-level control through deep reinforcement learning", _Nature_ 518, 529–533 — the deep Q-network: a convolutional value function trained by semi-gradient Q-learning from raw pixels, stabilized by an experience-replay buffer and a periodically updated target network.