Coarse Coding in RL

Coarse coding covers continuous states with overlapping shapes, and each state is named by the set of shapes that contain it. The shape of those regions decides how far each lesson spreads.

Overlapping receptive fields turn one state into a binary feature set, so a weight update at 2.5, 3.0 lifts the unvisited neighbour at 2.8, 3.6 by 0.2

Why Does This Exist?

Linear value functions are fast and stable, but they can only draw flat planes over raw coordinates:

\hat{v}(s, w) = w^T x(s)

Give the model raw $[x, y]$ and it cannot form peaks, valleys, or cliffs. Chop space into hard non-overlapping cells and the opposite problem appears: neighbouring cells share nothing, so every cell must be visited before it knows anything.

Coarse coding sits between those failures. Cover space with overlapping regions called receptive fields, and let each region own one binary feature that is 1 inside and 0 outside. One state lights up several features at once, and one weight update reaches every state that shares a field.

This page covers binary overlapping fields and how their geometry sets generalization. For the broader feature menu see feature construction. For guaranteed full coverage with offset grids see tile coding. For smooth graded fields instead of hard edges see radial basis functions.

You need one idea first: a linear model predicts by weighting its features, and gradient descent changes only the weights of features that are active.

Think of It Like This

Phone towers that locate you by overlap

Your phone sits somewhere in a city covered by broadcast circles from cell towers. At your corner it hears towers 3, 7, and 12. Your location code is the list of towers you hear, not your exact coordinates.

When tower 7 gets repaired, everyone who hears tower 7 benefits, even people standing blocks away on streets nobody measured. Two people who share two towers share more signal than two people who share one.

Map it point for point: the city is the state space, tower circles are receptive fields, the heard-tower list is the binary feature vector, and the repair spreading to strangers is value generalizing to unvisited states.

Where it stops: tower signal fades smoothly with distance, while classic coarse coding is binary, inside or outside. Smooth the edges and you get radial basis functions.

How It Actually Works

Let $R_1$ through $R_d$ be regions over continuous states. Feature $i$ is an indicator:

x_i(s) = 1 \text{ if } s \text{ is in } R_i, \text{ else } 0

Value is the sum of weights of covering fields:

\hat{v}(s, w) = \sum_{i \in \mathrm{active}(s)} w_i

With a target $U_t$ (a return or a TD target) and error $\delta_t = U_t - \hat{v}(S_t, w)$ , the linear update touches only active fields:

w_i \leftarrow w_i + \alpha \delta_t \quad \text{for } i \in \mathrm{active}(S_t)

Inactive weights do not move. That is the whole engine: shared fields carry the lesson elsewhere.

Why shape sets generalization

Large circles share members across long distances, so learning is fast but blurry. Small circles barely overlap, so detail is crisp but every patch must be visited. Ellipses stretched along one axis generalize far along that axis and stay sharp along the other, which suits tasks like mountain car where position changes slowly and velocity matters sharply.

Worked example with 5 circular fields

Fields: $F_1$ center $(2.0, 3.0)$ radius $1.0$ , $F_2$ center $(2.5, 3.2)$ radius $1.0$ , $F_3$ center $(2.8, 2.7)$ radius $0.8$ , $F_4$ center $(3.2, 3.5)$ radius $0.8$ , $F_5$ center $(1.0, 1.0)$ radius $0.5$ . Weights $w = [1.5, 2.0, -0.5, 0.8, -1.2]$ .

Query $s = (2.5, 3.0)$ . Squared distances to centers: $0.25$ to $F_1$ (inside, since $1.0^2 = 1.0$ ), $0.04$ to $F_2$ (inside), $0.18$ to $F_3$ (inside, since $0.8^2 = 0.64$ ), $0.74$ to $F_4$ (outside), $6.25$ to $F_5$ (outside). So $x(s) = [1, 1, 1, 0, 0]$ and:

\hat{v}(s, w) = 1.5 + 2.0 - 0.5 = 3.0

Target $U = 4.0$ gives error $\delta = 1.0$ . With step size $\alpha = 0.1$ , each active weight rises by $0.1$ : new weights $[1.6, 2.1, -0.4, 0.8, -1.2]$ , new prediction $1.6 + 2.1 - 0.4 = 3.3$ .

Now the unvisited neighbour $s' = (2.8, 3.6)$ . It sits in $F_1$ (distance squared exactly $1.00$ ), in $F_2$ ( $0.25$ ), outside $F_3$ ( $0.81$ ), and in $F_4$ ( $0.17$ ). So $x(s') = [1, 1, 0, 1, 0]$ . Before the update its value was $1.5 + 2.0 + 0.8 = 4.3$ ; after, it is $1.6 + 2.1 + 0.8 = 4.5$ . Nobody visited $s'$ , yet it gained $0.2$ through the shared fields $F_1$ and $F_2$ . The diagram draws this exact handoff.

Code

The snippet below builds the five fields, runs the update at $(2.5, 3.0)$ , and shows the neighbour inheriting $0.2$ .

1import math2from typing import List, Tuple3
4
5def inside(point: Tuple[float, float], center: Tuple[float, float], r: float) -> bool:6    """Binary receptive field: 1 when the point is within radius r."""7    return (point[0] - center[0]) ** 2 + (point[1] - center[1]) ** 2 <= r ** 28
9
10centers = [(2.0, 3.0), (2.5, 3.2), (2.8, 2.7), (3.2, 3.5), (1.0, 1.0)]11radii = [1.0, 1.0, 0.8, 0.8, 0.5]12w = [1.5, 2.0, -0.5, 0.8, -1.2]13
14s = (2.5, 3.0)15feat = [1 if inside(s, c, r) else 0 for c, r in zip(centers, radii)]16print(feat)17# -> [1, 1, 1, 0, 0]18pred = sum(wi * fi for wi, fi in zip(w, feat))19print(round(pred, 2))20# -> 3.021
22delta = 4.0 - pred23w = [wi + 0.1 * delta * fi for wi, fi in zip(w, feat)]24print([round(v, 2) for v in w])25# -> [1.6, 2.1, -0.4, 0.8, -1.2]26
27adj = (2.8, 3.6)28feat_adj = [1 if inside(adj, c, r) else 0 for c, r in zip(centers, radii)]29print(feat_adj)30# -> [1, 1, 0, 1, 0]31print(round(sum(wi * fi for wi, fi in zip(w, feat_adj)), 2))32# -> 4.5

Watch Out For

Dead zones where no field fires

Scatter fields by hand and gaps appear where nothing covers the state. There the feature vector is all zeros, the prediction is 0, and the gradient is 0, so even a huge error updates nothing.

Symptom: the agent visits a region repeatedly and never improves there. Fix: check coverage on a grid of probe states before training, and prefer structured layouts such as offset tilings that guarantee every state activates the same number of fields.

Circles on axes with different scales

A circle treats $0.1$ along every axis as equal. Physical states rarely agree: mountain-car position spans $1.8$ while velocity spans $0.14$ . A circle sized for position swallows the whole velocity range, and the agent stops telling speeds apart.

Symptom: values look flat along one axis no matter how long you train. Fix: normalize each state variable first, or stretch fields into ellipses whose radii match each axis scale.

The Quick Version

Coarse coding turns a continuous state into a sparse binary vector, one bit per overlapping receptive field.
Value is the sum of weights of the active fields, and each update moves only those weights.
Field geometry picks the tradeoff: large fields blur and learn fast, small fields sharpen slowly, ellipses split the difference by axis.
In the worked case, $(2.5, 3.0)$ activates fields 1, 2, and 3, predicts 3.0, and moves to 3.3 after one update.
The unvisited neighbour $(2.8, 3.6)$ shares fields 1 and 2, so it inherits a 0.2 gain with zero visits.