Tile Coding (CMAC) in RL

Why Does This Exist?

When reinforcement learning agents operate in continuous state spaces—such as a robotic arm moving through 3D coordinates or a self-balancing cart-pole—tabular methods fail because no continuous state is ever visited twice.

A naive workaround is to discretize the state space into a single coarse grid. However, a single grid suffers from two critical flaws:

1. Severe quantization error: All continuous points within the same grid cell are treated as identical, producing stair-step, piecewise-constant value functions with harsh discontinuities at cell borders.
2. The curse of resolution vs. generalization: If cells are large, the agent cannot make fine-grained control distinctions; if cells are tiny, memory requirements explode exponentially ($K^d$) and learning generalizes virtually zero distance.

Introduced by James Albus in 1975 under the name CMAC (Cerebellar Model Articulation Controller) and popularized in reinforcement learning by Richard Sutton, tile coding elegantly resolves this trade-off. By superimposing multiple overlapping grid partitions (tilings) shifted by small asymmetric offsets, the intersection of active tiles achieves high spatial resolution while retaining the broad, smooth generalization of large tiles—all while producing sparse binary feature vectors that compute in $O(m)$ integer time.

Think of It Like This

How It Actually Works

Overlapping Tilings and Asymmetric Offsets

Let the continuous state space be $\mathcal{S} \subset \mathbb{R}^k$. A tiling is an exhaustive partitioning of the state space into non-overlapping geometric hyper-rectangles called tiles.

Tile coding uses $m$ distinct tilings. Each tiling has identical tile dimensions (width $w_j$ along dimension $j$), but each tiling is displaced relative to the others by an offset vector $\mathbf{o}_i$:

$\mathbf{o}_i = \left( o_{i, 1}, o_{i, 2}, \dots, o_{i, k} \right), \quad i \in \{0, 1, \dots, m-1\}$

For any continuous state $s = (s_1, s_2, \dots, s_k)$, the integer coordinate of the active tile in tiling $i$ along dimension $j$ is calculated via floor division:

$\text{coord}_{i, j}(s) = \left\lfloor \frac{s_j - o_{i, j}}{w_j} \right\rfloor$

To prevent unnatural diagonal alignment artifacts, offsets must be chosen asymmetrically. If tilings are shifted uniformly along diagonals ($o_i = (i \Delta, i \Delta)$), the intersections form diagonal elongated strips, causing the value function to generalize unnaturally along the 45-degree axis. Sutton and Barto recommend displacing tilings using odd-integer displacement vectors:

$\mathbf{o}_i = \frac{i}{m} \mathbf{w} \odot (1, 3, 5, \dots, 2k-1) \pmod{\mathbf{w}}$

This asymmetric spacing ensures that the overlapping intersection regions are nearly isotropic (square/circular), providing balanced generalization across all spatial directions.

Sparsity and O(m) Computational Efficiency

Because each tiling is an exhaustive partition, any continuous state $s$ falls into exactly one tile per tiling. For a system with $m$ tilings:

• The binary feature vector $\mathbf{x}(s) \in \{0, 1\}^d$ contains millions of possible tile dimensions.
• However, exactly $m$ features are non-zero ($\|\mathbf{x}(s)\|_1 = m$ and $x_j \in \{0, 1\}$).
• All remaining $d - m$ features are strictly $0$.

This extreme sparsity transforms linear value inference from an expensive vector multiplication into a fast integer lookup:

$\hat{v}(s, \mathbf{w}) = \mathbf{w}^\top \mathbf{x}(s) = \sum_{j=1}^d w_j x_j(s) = \sum_{i=0}^{m-1} w_{\text{tile}_i(s)}$

Rather than executing $d$ floating-point multiplications, computing $\hat{v}(s, \mathbf{w})$ requires only $m$ memory lookups and additions ($O(m)$ complexity), completely independent of total state-space resolution $d$.

Proportional Generalization and Tile Hashing

1. Controlled Generalization: Two continuous states $s$ and $s'$ generalize in direct proportion to their spatial proximity. If $s$ and $s'$ share $k$ active tiles across the $m$ tilings, their feature dot product is: $\mathbf{x}(s)^\top \mathbf{x}(s') = k$ Updating state $s$ shifts the value of state $s'$ by exactly the fraction $\frac{k}{m}$. Points separated by more than one tile width share zero tiles ($k=0$) and undergo zero cross-talk.

2. Consistent Tile Hashing: In multi-dimensional spaces, the total number of tiles across all tilings can easily reach billions. To cap memory usage, multi-dimensional tile coordinates $(i, c_1, c_2, \dots, c_k)$ are mapped to a fixed-size weight table of length $N$ using a uniform pseudo-random hash function: $\text{index} = \text{hash}(i, c_1, c_2, \dots, c_k) \pmod N$ Because tilings are offset and states are sparse, occasional hash collisions are spread uniformly throughout the state space, behaving as harmless pseudo-random noise that averages out during learning.

Worked numerical calculation

Consider a 2-dimensional continuous state $s = (x, y) = (3.6, 7.2)$.

• Number of tilings: $m = 4$.
• Tile width along both axes: $W = 2.0$.
• Fundamental offset step: $\Delta = W / m = 2.0 / 4 = 0.5$.
• Asymmetric offsets for the 4 tilings:
  • Tiling 0: $\mathbf{o}_0 = (0.0, 0.0)$
  • Tiling 1: $\mathbf{o}_1 = (0.5, 1.5)$
  • Tiling 2: $\mathbf{o}_2 = (1.0, 1.0)$
  • Tiling 3: $\mathbf{o}_3 = (1.5, 0.5)$

Compute active tile integer coordinates $c_x = \lfloor (x - o_x) / W \rfloor, \; c_y = \lfloor (y - o_y) / W \rfloor$:

1. Tiling 0: $c_x = \lfloor (3.6 - 0.0) / 2.0 \rfloor = \lfloor 1.80 \rfloor = \mathbf{1}$ $c_y = \lfloor (7.2 - 0.0) / 2.0 \rfloor = \lfloor 3.60 \rfloor = \mathbf{3}$ Active Tile: (Tiling 0, Tile [1, 3])

2. Tiling 1: $c_x = \lfloor (3.6 - 0.5) / 2.0 \rfloor = \lfloor 3.1 / 2.0 \rfloor = \lfloor 1.55 \rfloor = \mathbf{1}$ $c_y = \lfloor (7.2 - 1.5) / 2.0 \rfloor = \lfloor 5.7 / 2.0 \rfloor = \lfloor 2.85 \rfloor = \mathbf{2}$ Active Tile: (Tiling 1, Tile [1, 2])

3. Tiling 2: $c_x = \lfloor (3.6 - 1.0) / 2.0 \rfloor = \lfloor 2.6 / 2.0 \rfloor = \lfloor 1.30 \rfloor = \mathbf{1}$ $c_y = \lfloor (7.2 - 1.0) / 2.0 \rfloor = \lfloor 6.2 / 2.0 \rfloor = \lfloor 3.10 \rfloor = \mathbf{3}$ Active Tile: (Tiling 2, Tile [1, 3])

4. Tiling 3: $c_x = \lfloor (3.6 - 1.5) / 2.0 \rfloor = \lfloor 2.1 / 2.0 \rfloor = \lfloor 1.05 \rfloor = \mathbf{1}$ $c_y = \lfloor (7.2 - 0.5) / 2.0 \rfloor = \lfloor 6.7 / 2.0 \rfloor = \lfloor 3.35 \rfloor = \mathbf{3}$ Active Tile: (Tiling 3, Tile [1, 3])

Suppose the current learned weights associated with these four active tiles are:

• $w(0, 1, 3) = 1.20$
• $w(1, 1, 2) = 0.80$
• $w(2, 1, 3) = 1.50$
• $w(3, 1, 3) = 1.00$

The estimated linear state value is the direct sum of the $m=4$ active weights: $\hat{v}(s, \mathbf{w}) = 1.20 + 0.80 + 1.50 + 1.00 = \mathbf{4.50}$

Computing this prediction required exactly four additions, delivering high-acuity localization with minimal processor overhead.

Code

1import math2from typing import Dict, List, Set, Tuple3
4
5class TileCoder2D:6    """2D Tile Coder (CMAC) using asymmetric offsets and linear weight indexing."""7
8    def __init__(9        self,10        num_tilings: int = 4,11        tile_width: float = 2.0,12        offsets: List[Tuple[float, float]] = None,13    ):14        self.num_tilings = num_tilings15        self.tile_width = tile_width16
17        # Asymmetric offsets to prevent diagonal correlation artifacts18        if offsets is None:19            self.offsets = [20                (0.0, 0.0),21                (0.5, 1.5),22                (1.0, 1.0),23                (1.5, 0.5),24            ]25        else:26            assert len(offsets) == num_tilings27            self.offsets = offsets28
29    def get_active_tiles(self, x: float, y: float) -> List[Tuple[int, int, int]]:30        """Return the active (tiling_idx, coord_x, coord_y) for continuous point (x, y)."""31        active_tiles: List[Tuple[int, int, int]] = []32        for tiling_idx, (ox, oy) in enumerate(self.offsets):33            cx = math.floor((x - ox) / self.tile_width)34            cy = math.floor((y - oy) / self.tile_width)35            active_tiles.append((tiling_idx, cx, cy))36        return active_tiles37
38    def predict(39        self, x: float, y: float, weights: Dict[Tuple[int, int, int], float]40    ) -> float:41        """Compute linear prediction as sum of m active tile weights in O(m) time."""42        active_tiles = self.get_active_tiles(x, y)43        return sum(weights.get(tile, 0.0) for tile in active_tiles)44
45    def update(46        self,47        x: float,48        y: float,49        target: float,50        weights: Dict[Tuple[int, int, int], float],51        alpha: float = 0.1,52    ) -> float:53        """Perform linear semi-gradient update: w_i <- w_i + (alpha / m) * (target - v_hat)."""54        active_tiles = self.get_active_tiles(x, y)55        v_hat = sum(weights.get(tile, 0.0) for tile in active_tiles)56        error = target - v_hat57
58        # Step size normalized by number of active tilings m59        step_size = alpha / self.num_tilings60        for tile in active_tiles:61            weights[tile] = weights.get(tile, 0.0) + step_size * error62
63        return error64
65
66if __name__ == "__main__":67    tc = TileCoder2D(num_tilings=4, tile_width=2.0)68    query_x, query_y = 3.6, 7.269
70    # 1. Active Tile Indexing Verification71    active = tc.get_active_tiles(query_x, query_y)72    print("=== Tile Coding (CMAC) Numerical Verification ===")73    print(f"Continuous State Point: ({query_x}, {query_y})")74    print(f"Active Tile Indices across {tc.num_tilings} tilings:")75    for tile in active:76        print(f"  Tiling {tile[0]}: Tile Coordinate [{tile[1]}, {tile[2]}]")77
78    expected_active = [(0, 1, 3), (1, 1, 2), (2, 1, 3), (3, 1, 3)]79    assert (80        active == expected_active81    ), f"Expected {expected_active}, got {active}"82
83    # 2. Value Prediction Verification with Preset Weights84    preset_weights: Dict[Tuple[int, int, int], float] = {85        (0, 1, 3): 1.20,86        (1, 1, 2): 0.80,87        (2, 1, 3): 1.50,88        (3, 1, 3): 1.00,89    }90    v_val = tc.predict(query_x, query_y, preset_weights)91    print(f"\nCalculated Linear Value v_hat: {v_val:.2f}")92    assert math.isclose(v_val, 4.50), f"Expected 4.50, got {v_val}"93
94    # 3. Spatial Generalization Verification95    close_point = (3.7, 7.3)96    far_point = (6.5, 11.0)97
98    set_original: Set[Tuple[int, int, int]] = set(active)99    set_close: Set[Tuple[int, int, int]] = set(100        tc.get_active_tiles(*close_point)101    )102    set_far: Set[Tuple[int, int, int]] = set(tc.get_active_tiles(*far_point))103
104    overlap_close = len(set_original.intersection(set_close))105    overlap_far = len(set_original.intersection(set_far))106
107    print("\nGeneralization Analysis:")108    print(109        f"  Nearby point {close_point} shares: {overlap_close}/4 tiles ({overlap_close / 4:.0%} overlap)"110    )111    print(112        f"  Distant point {far_point} shares: {overlap_far}/4 tiles ({overlap_far / 4:.0%} overlap)"113    )114
115    assert (116        overlap_close >= 3117    ), "Close continuous points must share significant tile overlap!"118    assert (119        overlap_far == 0120    ), "Far continuous points must share zero tile overlap!"121
122    print("\nAll tile coding mathematical assertions passed successfully.")123
124# Expected Output:125# === Tile Coding (CMAC) Numerical Verification ===126# Continuous State Point: (3.6, 7.2)127# Active Tile Indices across 4 tilings:128#   Tiling 0: Tile Coordinate [1, 3]129#   Tiling 1: Tile Coordinate [1, 2]130#   Tiling 2: Tile Coordinate [1, 3]131#   Tiling 3: Tile Coordinate [1, 3]132#133# Calculated Linear Value v_hat: 4.50134#135# Generalization Analysis:136#   Nearby point (3.7, 7.3) shares: 4/4 tiles (100% overlap)137#   Distant point (6.5, 11.0) shares: 0/4 tiles (0% overlap)138#139# All tile coding mathematical assertions passed successfully.

Watch Out For

The Quick Version

• Multiple offset grids: Tile coding overlays $m$ complete partitionings (tilings) of continuous state space, displaced by asymmetric offsets.
• Sparse binary representation: Exactly $m$ tiles are active at any continuous point; the feature vector is purely binary with $\|\mathbf{x}(s)\|_1 = m$.
• Lightning-fast $O(m)$ inference: Value estimation evaluates as a simple sum of $m$ active weights, completely bypassing matrix multiplications.
• Isotropic generalization: Two states sharing $k$ active tiles generalize with exact weight fraction $\frac{k}{m}$, combining broad coverage with pinpoint spatial resolution.

What to Read Next

• Coarse Coding in RL
• Radial Basis Functions in RL
• Semi-Gradient SARSA in RL