Feature Construction in RL

Linear methods can only draw flat planes over their inputs. Feature construction rebuilds raw state numbers into richer inputs first, so the same flat learner can fit curved value surfaces.

A quadratic feature map turns state (1.4, 2.3) into six inputs whose weighted parts sum to 8.85, with the cross product term contributing 2.58

Why Does This Exist?

Linear value methods are attractive for three hard reasons: each update costs $O(d)$ for $d$ features, the error surface has a single bowl with no false bottoms, and on-policy temporal-difference learning converges with proofs rather than hopes. The dedicated treatment is linear methods.

The price is geometric. A linear model over raw state variables can only fit a flat hyperplane. Hand a robot learner its joint angle $\theta$ and angular velocity $\dot{\theta}$ directly, and the value estimate is stuck at $\hat{v} = w_1\theta + w_2\dot{\theta} + w_0$ . Real value surfaces curve, fold, and drop off cliffs, as in Mountain Car or CartPole. A plane cannot follow any of that, so the agent fails no matter how long it trains.

Feature construction breaks the bottleneck without giving up the proofs. All the nonlinearity is pushed into a fixed mapping $\mathbf{x}(s)$ from state to features, built once by the designer. Learning stays strictly linear in the weights $\mathbf{w}$ , but the composite $\mathbf{w}^\top\mathbf{x}(s)$ bends, peaks, and cliffs wherever the features do.

This page covers the what and why of the whole menu: bins, polynomials, sinusoids, and bells. The deep treatments live on their own pages: tile coding for offset grids, coarse coding for overlapping binary fields, polynomial and Fourier bases for global smooth maps, and radial basis functions for local graded fields.

The one idea you need first.

A linear value estimate is a weighted sum $\hat{v}(s, \mathbf{w}) = \mathbf{w}^\top\mathbf{x}(s)$ : each feature $x_i(s)$ is one input number describing the state, each weight $w_i$ is learned, and the estimate is features times weights added up. Everything below is a choice of what those input numbers should be. The broader approximation story is value function approximation.

Think of It Like This

Whole spices versus a ground spice blend

A seasoning machine has one dial per hopper and can only change how much powder falls out. It cannot roast, grind, or blend during cooking. Fill its hoppers with whole cumin seeds and peppercorns and the dish comes out uneven and bitter: the machine can adjust volumes but cannot unlock the flavors inside whole seeds.

A cook fixes this before the machine runs. Toast the cumin, crack the pepper, grind both with paprika into one blend, then load the blend. The machine is exactly as linear as before, turning one dial, but the prepared input lets it produce layered flavor.

Point for point: the machine is the linear learner, the whole spices are raw state variables, grinding and blending is the feature map $\mathbf{x}(s)$ , and the dial is the weight vector $\mathbf{w}$ . Where it stops: ground spices go stale, while a feature map is a fixed mathematical function that returns identical numbers on episode one and episode one million.

How It Actually Works

Why the linear update loves good features

The gradient of a linear estimate with respect to its weights is the feature vector itself, $\nabla_\mathbf{w} \hat{v}(s, \mathbf{w}) = \mathbf{x}(s)$ . Here $\mathbf{w}$ is the weight vector, $\alpha$ in $(0, 1]$ is the step size, $\gamma$ in $[0, 1]$ is the discount factor, $R_{t+1}$ is the reward just seen, and $\hat{v}$ is the current estimate. That identity makes the semi-gradient TD update a clean push along the active features:

$\mathbf{w}_{t+1} = \mathbf{w}_t + \alpha \left[ R_{t+1} + \gamma \hat{v}(S_{t+1}, \mathbf{w}_t) - \hat{v}(S_t, \mathbf{w}_t) \right] \mathbf{x}(S_t)$

Because each update moves $\mathbf{w}$ along $\mathbf{x}(S_t)$ , the features decide how learning at one state spills over to its neighbors. That spillover is the entire design game.

Five constructions cover nearly every linear RL design, ordered from least to most generalization:

One-hot tabular. Each discrete state gets its own basis vector, so updating one state touches nothing else. Zero spillover, zero generalization.
State aggregation. Chop each continuous dimension into bins and light one binary feature per box: $x_i(s) = 1$ inside bin $i$ , else $0$ . Every state in a box shares one value, giving a staircase surface.
Polynomials with cross terms. Expand coordinates into powers and products, for example $\mathbf{x}(s) = [1, s_1, s_2, s_1^2, s_2^2, s_1 s_2]^\top$ . The product $s_1 s_2$ is the crucial piece: it lets the effect of one variable depend on the other.
Fourier basis. Use cosine waves $x_i(s) = \cos(\pi \mathbf{c}_i^\top s)$ with integer frequency vectors $\mathbf{c}_i$ . Global and smooth, strong on continuous control.
Radial basis functions. Hang bell curves $x_i(s) = \exp(-\|s - \mathbf{c}_i\|^2 / 2\sigma_i^2)$ on prototype points $\mathbf{c}_i$ with width $\sigma_i$ . Smooth local spillover that fades with distance.

The width tradeoff

Broad features, meaning wide bells or chunky bins, generalize fast: one update fixes a whole neighborhood, so early learning flies. The cost is blur: sharp cliffs and narrow ridges get smeared. Narrow features resolve fine detail but must each be visited to learn, degrading toward tabular sample hunger. There is no setting that wins both; match the width to the sharpest structure the task actually has.

Worked example

State $s = (1.40, 2.30)$ in a square from $0.0$ to $3.0$ on each axis, judged two ways.

First, a $3 \times 3$ aggregation grid with bin width $1.0$ . Coordinate $1.40$ falls in bin $1$ and $2.30$ in bin $2$ , so the flat index is $1 \times 3 + 2 = 5$ and the feature vector is all zeros except a $1$ at position $5$ . With weights $[1.2, 2.5, 4.0, 2.0, 5.5, 8.0, 3.5, 7.0, 10.0]$ , the estimate reads off weight $5$ directly: $\hat{v} = 8.00$ . Every state in the box $[1.0, 2.0) \times [2.0, 3.0]$ scores exactly $8.00$ .

Second, the quadratic map $[1.0, x_1, x_2, x_1^2, x_2^2, x_1 x_2]^\top$ . At this state that is $[1.0, 1.40, 2.30, 1.96, 5.29, 3.22]$ , since $1.4^2 = 1.96$ , $2.3^2 = 5.29$ , and $1.4 \times 2.3 = 3.22$ . With weights $[0.5, 1.0, 1.5, 0.2, 0.1, 0.8]$ the parts are $0.50$ , $1.40$ , $3.45$ , $0.39$ , $0.53$ , and $2.58$ , summing to $\hat{v} = 8.8470$ . The cross term alone contributes $2.58$ , nearly a third of the total: interaction the grid staircase cannot express without far more bins.

Code

Both regimes from the worked example, using only the standard library. Rounding keeps the printed features exact.

1from typing import List2
3
4def aggregation_index(x1: float, x2: float, bins: int = 3, lo: float = 0.0, hi: float = 3.0) -> int:5    """Flat bin index of a 2D state in a uniform grid."""6    i = min(bins - 1, int((x1 - lo) / (hi - lo) * bins))7    j = min(bins - 1, int((x2 - lo) / (hi - lo) * bins))8    return i * bins + j9
10
11def polynomial_features(x1: float, x2: float) -> List[float]:12    """Quadratic expansion [1, x1, x2, x1^2, x2^2, x1*x2]."""13    return [1.0, x1, x2, round(x1 ** 2, 4), round(x2 ** 2, 4), round(x1 * x2, 4)]14
15
16def dot(a: List[float], b: List[float]) -> float:17    """Weighted sum of features under weights."""18    return sum(x * y for x, y in zip(a, b))19
20
21state = (1.4, 2.3)22grid_w = [1.2, 2.5, 4.0, 2.0, 5.5, 8.0, 3.5, 7.0, 10.0]23poly_w = [0.5, 1.0, 1.5, 0.2, 0.1, 0.8]24print(aggregation_index(*state))  # -> 525print(f"{grid_w[aggregation_index(*state)]:.2f}")  # -> 8.0026print(polynomial_features(*state))  # -> [1.0, 1.4, 2.3, 1.96, 5.29, 3.22]27print(f"{dot(polynomial_features(*state), poly_w):.4f}")  # -> 8.8470

The script prints the same $5$ , $8.00$ , feature list, and $8.8470$ the hand computation gives.

Watch Out For

Binning every dimension until the features explode

Slicing each of $D$ dimensions into $B$ bins needs $B^D$ weights. A 12 dimensional arm state with 10 bins per variable asks for $10^{12}$ weights: terabytes of memory where each bin still needs its own visits to learn anything.

The symptom is a weight table that does not fit and a visit histogram where nearly every bin sits at zero after days of training. The fix is a sparse scheme whose size grows with resolution linearly, not exponentially: tile coding with a handful of offset tilings, or a smooth global basis. Finer bins are the last resort, never the first.

Independent per-variable features that cannot see diagonals

Encoding each variable on its own, such as separate 1D tilings concatenated together, keeps the count at $O(D \cdot B)$ but builds a purely additive model. If success needs $s_1$ and $s_2$ high together, a diagonal boundary, additive features cannot draw it: no sum of separate curves makes a corner.

The symptom is a plateau where each variable looks right alone yet combined states fail, and adding more 1D resolution changes nothing. The fix is interaction terms: cross products like $s_1 s_2$ in a polynomial map, or conjunctive tiles that fire only on the combination. Whenever two physical variables push on each other, their product belongs in the features.

The Quick Version

Linear estimates $\hat{v}(s, \mathbf{w}) = \mathbf{w}^\top\mathbf{x}(s)$ draw flat planes over whatever inputs they get, so curved values need prepared inputs.
Aggregation bins share one value per box and give staircases; polynomials add curves and cross terms; Fourier gives global waves; bells give local graded spillover.
Feature width sets the generalization tradeoff: broad learns fast but blurs cliffs, narrow resolves detail but starves for visits.
Cross terms such as $x_1 x_2$ carry interactions additive features cannot express; at state $(1.4, 2.3)$ the $3.22$ term supplies $2.58$ of the $8.85$ estimate.
Naive $B^D$ grids explode in higher dimensions, so scale with tilings or smooth bases instead of finer bins.