Coarse Coding in RL

Why Does This Exist?

In reinforcement learning with continuous state spaces, linear function approximation $\hat{v}(s, \mathbf{w}) = \mathbf{w}^T \mathbf{x}(s)$ is widely favored for its theoretical stability, rapid computation, and absence of local optima. However, a linear model can only represent complex, non-linear value surfaces if the feature vector $\mathbf{x}(s)$ captures non-linear properties of the underlying state space.

If an agent simply passes raw state coordinates (such as $\mathbf{x}(s) = [x, y]^T$), the linear model can only represent a flat, tilted plane. It cannot represent peaks, valleys, boundaries, or sharp cliffs. Conversely, if the state space is discretized into rigid, non-overlapping grid cells (a tabular histogram), the agent loses all ability to generalize between adjacent cells.

Coarse coding solves this feature engineering challenge by covering the continuous state space with an ensemble of overlapping geometric regions, known as receptive fields.

Each receptive field corresponds to a single binary feature in the representation:

$x_i(s) = \begin{cases} 1 & \text{if } s \in \text{Region}_i \\ 0 & \text{otherwise} \end{cases}$

Because the regions overlap, any continuous state activates a whole subset of receptive fields. Updating the weight of an active feature following a transition at state $s$ transfers value to every other state that shares that receptive field. Crucially, coarse coding reveals a foundational machine learning insight: the geometric shape, size, and orientation of the receptive fields directly determine how value knowledge generalizes across the state space.

Think of It Like This

How It Actually Works

Binary Receptive Fields and Generalization Geometry

Coarse coding transforms a continuous state vector $s \in \mathcal{S} \subseteq \mathbb{R}^k$ into a high-dimensional, sparse binary feature vector $\mathbf{x}(s) \in \{0, 1\}^d$.

1. Mathematical Formulation

Let $\{R_1, R_2, \dots, R_d\}$ denote a collection of $d$ receptive fields defined over the continuous state space $\mathcal{S}$. The $i$-th feature is defined as:

$x_i(s) \doteq \mathbb{I}(s \in R_i) = \begin{cases} 1 & \text{if } s \in R_i \\ 0 & \text{otherwise} \end{cases}$

The approximate value function $\hat{v}(s, \mathbf{w})$ is the inner product of the weight vector $\mathbf{w} \in \mathbb{R}^d$ and feature vector $\mathbf{x}(s)$:

$\hat{v}(s, \mathbf{w}) \doteq \mathbf{w}^T \mathbf{x}(s) = \sum_{i=1}^d w_i x_i(s) = \sum_{i \in \text{active}(s)} w_i$

where $\text{active}(s) \doteq \{i \in \{1, \dots, d\} \mid s \in R_i\}$ is the set of indices of all receptive fields containing state $s$. The value of state $s$ is simply the sum of weights of all receptive fields covering that state.

2. The Linear Semi-Gradient Update

When an agent observes an experience target $U_t$ (such as a Monte Carlo return $G_t$ or a one-step TD target $R_{t+1} + \gamma \hat{v}(S_{t+1}, \mathbf{w})$), the semi-gradient stochastic gradient descent update is:

$\mathbf{w} \leftarrow \mathbf{w} + \alpha \left[ U_t - \hat{v}(S_t, \mathbf{w}) \right] \nabla_{\mathbf{w}} \hat{v}(S_t, \mathbf{w})$

Because $\hat{v}$ is linear, the gradient with respect to $\mathbf{w}$ is simply the binary feature vector itself: $\nabla_{\mathbf{w}} \hat{v}(S_t, \mathbf{w}) = \mathbf{x}(S_t)$.

Denoting the TD error as $\delta_t \doteq U_t - \hat{v}(S_t, \mathbf{w})$:

• For inactive features ($i \notin \text{active}(S_t)$, where $x_i = 0$): $w_i \leftarrow w_i + 0$ (no update).
• For active features ($i \in \text{active}(S_t)$, where $x_i = 1$): $w_i \leftarrow w_i + \alpha \delta_t$

(Optionally, the step size can be normalized by the number of active features: $w_i \leftarrow w_i + \frac{\alpha}{|\text{active}(S_t)|} \delta_t$, ensuring that total value adjustments remain invariant to feature count).

3. How Receptive Field Geometry Dictates Generalization

The geometric characteristics of the receptive fields determine how the learning update at $S_t$ spreads to other states $s'$:

1LARGE CIRCLES                  SMALL CIRCLES                 ELONGATED ELLIPSES2    ╭─────╮                       ╭─╮   ╭─╮                    ╭───────────╮3  ╭─┤     ├─╮                    ╭┤ ├─╮╭┤ ├─╮                 ╭┤           ├─╮4  │ │  s  │ │                    │╰─╯ ││╰─╯ │                 ││     s     ││5  ╰─┤     ├─╯                    ╰─┬──╯╰──┬─╯                 ╰┤           ├─╯6    ╰─────╯                        ╰─╮   ╭─╯                   ╰───────────╯7Broad Isotropic                Sharp Spatial                  Directional Bias8Generalization                 Discrimination                 (e.g., Position vs Velocity)

1. Large Receptive Fields (Broad Generalization): When fields have a large radius $r$, states that are far apart still share many common receptive fields. An update at $s$ significantly alters the value of distant neighbors. This delivers rapid early learning of broad value trends, but limits the agent's ability to discriminate fine, sharp spatial details.
2. Small Receptive Fields (Fine Discrimination): When fields have a small radius, neighboring states quickly cease to share active fields. Updates remain tightly localized. This allows the agent to represent sharp cliffs and narrow value peaks, but requires substantially more samples because value information diffuses slowly across space.
3. Elongated / Elliptical Fields (Directional Generalization): If the receptive fields are elongated ellipses where the radius along feature 1 is much larger than along feature 2 ($r_1 \gg r_2$), the representation generalizes broadly along feature 1 while discriminating sharply along feature 2. In physical control tasks like the Mountain Car problem (position vs. velocity), value functions typically vary smoothly along position but change rapidly with velocity; elliptical fields aligned with these dynamics dramatically accelerate convergence.

Worked numerical example

Consider a 2D continuous state space covered by 5 receptive fields:

• $F_1$: Circle centered at $(2.0, 3.0)$ with radius $r = 1.0$
• $F_2$: Circle centered at $(2.5, 3.2)$ with radius $r = 1.0$
• $F_3$: Circle centered at $(2.8, 2.7)$ with radius $r = 0.8$
• $F_4$: Circle centered at $(3.2, 3.5)$ with radius $r = 0.8$
• $F_5$: Circle centered at $(1.0, 1.0)$ with radius $r = 0.5$

Let current parameter weights be: $\mathbf{w} = [w_1 = 1.5, \; w_2 = 2.0, \; w_3 = -0.5, \; w_4 = 0.8, \; w_5 = -1.2]^T$

Step 1: Feature Extraction at Query State $s = (2.5, 3.0)$

We check the Euclidean distance from $s$ to each field center:

• For $F_1$: $d^2 = (2.5 - 2.0)^2 + (3.0 - 3.0)^2 = 0.25 + 0.00 = 0.25 \le 1.0^2 \implies \mathbf{Active}$ ($x_1 = 1$)
• For $F_2$: $d^2 = (2.5 - 2.5)^2 + (3.0 - 3.2)^2 = 0.00 + 0.04 = 0.04 \le 1.0^2 \implies \mathbf{Active}$ ($x_2 = 1$)
• For $F_3$: $d^2 = (2.5 - 2.8)^2 + (3.0 - 2.7)^2 = 0.09 + 0.09 = 0.18 \le 0.8^2 = 0.64 \implies \mathbf{Active}$ ($x_3 = 1$)
• For $F_4$: $d^2 = (2.5 - 3.2)^2 + (3.0 - 3.5)^2 = 0.49 + 0.25 = 0.74 > 0.64 \implies \text{Inactive}$ ($x_4 = 0$)
• For $F_5$: $d^2 = (2.5 - 1.0)^2 + (3.0 - 1.0)^2 = 2.25 + 4.00 = 6.25 > 0.25 \implies \text{Inactive}$ ($x_5 = 0$)

The binary feature vector for state $s$ is: $\mathbf{x}(s) = [1, 1, 1, 0, 0]^T$

Step 2: Compute Initial Value Prediction

$\hat{v}(s, \mathbf{w}) = \sum_{i \in \{1, 2, 3\}} w_i = 1.5000 + 2.0000 + (-0.5000) = 3.0000$

Step 3: Weight Update Following Experience Target

The agent experiences target return $U = 4.0$. The TD error is: $\delta = U - \hat{v}(s, \mathbf{w}) = 4.0 - 3.0 = +1.0000$

Using learning rate $\alpha = 0.1$, we update the active weights: $\Delta w_i = \alpha \delta = 0.1 \times 1.0 = +0.1000 \quad (\text{for } i \in \{1, 2, 3\})$

Updated weight vector: $w_1 \leftarrow 1.5 + 0.1 = 1.6000$ $w_2 \leftarrow 2.0 + 0.1 = 2.1000$ $w_3 \leftarrow -0.5 + 0.1 = -0.4000$ $w_4 \leftarrow 0.8000 \quad (\text{unchanged})$ $w_5 \leftarrow -1.2000 \quad (\text{unchanged})$

The new prediction at $s$ is: $\hat{v}(s, \mathbf{w}_{\text{new}}) = 1.6000 + 2.1000 - 0.4000 = 3.3000$

Step 4: Generalization to an Unvisited Adjacent State

Now consider an adjacent, unvisited state $s_{\text{adj}} = (2.8, 3.6)$. Checking field containment:

• In $F_1$: $(2.8-2.0)^2 + (3.6-3.0)^2 = 0.64 + 0.36 = 1.00 \le 1.00 \implies \mathbf{Active}$ ($x_1 = 1$)
• In $F_2$: $(2.8-2.5)^2 + (3.6-3.2)^2 = 0.09 + 0.16 = 0.25 \le 1.00 \implies \mathbf{Active}$ ($x_2 = 1$)
• In $F_3$: $(2.8-2.8)^2 + (3.6-2.7)^2 = 0.00 + 0.81 = 0.81 > 0.64 \implies \text{Inactive}$ ($x_3 = 0$)
• In $F_4$: $(2.8-3.2)^2 + (3.6-3.5)^2 = 0.16 + 0.01 = 0.17 \le 0.64 \implies \mathbf{Active}$ ($x_4 = 1$)
• In $F_5$: Inactive ($x_5 = 0$)

The feature vector for $s_{\text{adj}}$ is $\mathbf{x}(s_{\text{adj}}) = [1, 1, 0, 1, 0]^T$.

Compare its value prediction before and after the update at $s$:

• Before update to $s$: $\hat{v}(s_{\text{adj}}, \mathbf{w}_{\text{old}}) = w_1 + w_2 + w_4 = 1.5000 + 2.0000 + 0.8000 = 4.3000$
• After update to $s$: $\hat{v}(s_{\text{adj}}, \mathbf{w}_{\text{new}}) = 1.6000 + 2.1000 + 0.8000 = 4.5000$

Even though $s_{\text{adj}}$ was never visited, its value prediction increased by $+0.2000$ purely because it shares receptive fields $F_1$ and $F_2$ with $s$!

Code

Below is a self-contained, type-hinted Python script implementing 2D coarse coding with both circular and elliptical receptive fields, binary feature extraction, and automated assertions confirming inductive generalization:

1import math2from typing import List, Tuple, Union3
4
5class CircleReceptiveField:6    """Circular binary receptive field: (x - cx)^2 + (y - cy)^2 <= r^2."""7
8    def __init__(self, name: str, center: Tuple[float, float], radius: float) -> None:9        self.name = name10        self.cx, self.cy = center11        self.radius = radius12
13    def contains(self, point: Tuple[float, float]) -> bool:14        x, y = point15        return (x - self.cx) ** 2 + (y - self.cy) ** 2 <= self.radius ** 216
17
18class EllipseReceptiveField:19    """Elliptical binary receptive field: ((x - cx)/rx)^2 + ((y - cy)/ry)^2 <= 1."""20
21    def __init__(22        self,23        name: str,24        center: Tuple[float, float],25        radius_x: float,26        radius_y: float,27    ) -> None:28        self.name = name29        self.cx, self.cy = center30        self.rx = radius_x31        self.ry = radius_y32
33    def contains(self, point: Tuple[float, float]) -> bool:34        x, y = point35        return ((x - self.cx) / self.rx) ** 2 + ((y - self.cy) / self.ry) ** 2 <= 1.036
37
38ReceptiveField = Union[CircleReceptiveField, EllipseReceptiveField]39
40
41class CoarseCoding2D:42    """Coarse coding linear value function approximator in 2D space."""43
44    def __init__(self, receptive_fields: List[ReceptiveField]) -> None:45        self.fields = receptive_fields46        self.weights: List[float] = [0.0] * len(receptive_fields)47
48    def extract_features(self, point: Tuple[float, float]) -> List[int]:49        """Convert a continuous 2D coordinate into a binary feature vector."""50        return [1 if field.contains(point) else 0 for field in self.fields]51
52    def predict(self, point: Tuple[float, float]) -> float:53        """Compute v_hat(point, w) = sum of weights for active fields."""54        features = self.extract_features(point)55        return sum(w * f for w, f in zip(self.weights, features))56
57    def update(58        self, point: Tuple[float, float], target: float, alpha: float59    ) -> Tuple[float, List[int]]:60        """Perform semi-gradient SGD update on active binary features."""61        features = self.extract_features(point)62        pred = sum(w * f for w, f in zip(self.weights, features))63        delta = target - pred64
65        # Each active feature updates by alpha * delta66        for i in range(len(self.weights)):67            if features[i] == 1:68                self.weights[i] += alpha * delta69
70        return delta, features71
72
73def demonstrate_coarse_coding() -> None:74    # 5 receptive fields matching the worked numerical example75    fields: List[ReceptiveField] = [76        CircleReceptiveField("F1", (2.0, 3.0), 1.0),77        CircleReceptiveField("F2", (2.5, 3.2), 1.0),78        CircleReceptiveField("F3", (2.8, 2.7), 0.8),79        CircleReceptiveField("F4", (3.2, 3.5), 0.8),80        CircleReceptiveField("F5", (1.0, 1.0), 0.5),81    ]82
83    model = CoarseCoding2D(fields)84    # Initialize weights: [1.5, 2.0, -0.5, 0.8, -1.2]85    model.weights = [1.5, 2.0, -0.5, 0.8, -1.2]86
87    # Target training point s: (2.5, 3.0)88    point_s = (2.5, 3.0)89    feat_s = model.extract_features(point_s)90    print(f"Features for s={point_s}: {feat_s}")91    assert feat_s == [1, 1, 1, 0, 0]92
93    v_init_s = model.predict(point_s)94    print(f"Initial v(s): {v_init_s:.4f}")95    assert abs(v_init_s - 3.0) < 1e-696
97    # Update with target=4.0, alpha=0.1 -> delta = +1.098    delta, _ = model.update(point_s, target=4.0, alpha=0.1)99    print(f"Update TD error delta: {delta:.4f}")100    print(f"Updated weights: {[round(w, 4) for w in model.weights]}")101    assert abs(model.weights[0] - 1.6) < 1e-6102    assert abs(model.weights[1] - 2.1) < 1e-6103    assert abs(model.weights[2] - (-0.4)) < 1e-6104    assert abs(model.weights[3] - 0.8) < 1e-6105    assert abs(model.weights[4] - (-1.2)) < 1e-6106
107    v_new_s = model.predict(point_s)108    print(f"Updated v(s): {v_new_s:.4f}")109    assert abs(v_new_s - 3.3) < 1e-6110
111    # Evaluate unvisited adjacent point s_adj = (2.8, 3.6)112    point_adj = (2.8, 3.6)113    feat_adj = model.extract_features(point_adj)114    print(f"\nFeatures for unvisited s_adj={point_adj}: {feat_adj}")115    assert feat_adj == [1, 1, 0, 1, 0]116
117    v_adj = model.predict(point_adj)118    print(f"Value for unvisited s_adj: {v_adj:.4f} (inherited +0.2 from shared fields F1, F2!)")119    assert abs(v_adj - 4.5) < 1e-6120
121
122if __name__ == "__main__":123    demonstrate_coarse_coding()124
125# -> Expected output:126# -> Features for s=(2.5, 3.0): [1, 1, 1, 0, 0]127# -> Initial v(s): 3.0000128# -> Update TD error delta: 1.0000129# -> Updated weights: [1.6, 2.1, -0.4, 0.8, -1.2]130# -> Updated v(s): 3.3000131# -> 132# -> Features for unvisited s_adj=(2.8, 3.6): [1, 1, 0, 1, 0]133# -> Value for unvisited s_adj: 4.5000 (inherited +0.2 from shared fields F1, F2!)

Watch Out For

The Quick Version

• Binary Receptive Fields: Coarse coding covers continuous state spaces with overlapping geometric regions, mapping any continuous coordinate into a sparse binary feature vector $\mathbf{x}(s) \in \{0, 1\}^d$.
• Sum-of-Weights Value Surface: The approximate state value $\hat{v}(s, \mathbf{w}) = \sum_{i \in \text{active}(s)} w_i$ is simply the sum of weights associated with all receptive fields covering state $s$.
• Geometry Dictates Generalization: Large fields generate broad isotropic generalization with fast learning; small fields provide fine spatial discrimination; elongated ellipses produce directional generalization along primary physical axes.
• Overlap-Proportional Knowledge Transfer: Generalization between two states is strictly proportional to the intersection volume of their active receptive fields, enabling zero-shot value estimation on unvisited coordinates.

What to Read Next

• Feature Construction in RL
• Tile Coding (CMAC) in RL
• Radial Basis Functions in RL