Tile Coding (CMAC) in RL

Why Does This Exist?

Continuous states break tables. A robot arm never visits the exact same joint angle twice, so a lookup table learns nothing twice. The naive fix is one coarse grid, but it fails both ways: big cells blur distinctions the controller needs, and tiny cells explode memory while generalizing zero distance. Every point becomes an island.

Tile coding, introduced by Albus (1975) as CMAC and brought into RL by Sutton, escapes the tradeoff with overlap. Lay $m$ full grids (tilings) over the space, each shifted by a small offset. A point activates exactly one tile per tiling, so its feature vector holds exactly $m$ ones out of thousands of entries. Neighbors share most of their active tiles and generalize strongly; distant points share none. Prediction becomes a sum of $m$ weights, learned with linear value function approximation. Neighbors of this idea are coarse coding and radial basis functions; the control loop that consumes tile features is typically semi-gradient SARSA.

The one idea you need first.

A linear value estimate is a weighted sum of features: $\hat{v}(s, \mathbf{w}) = \mathbf{w}^\top \mathbf{x}(s)$, where $\mathbf{x}(s)$ is the feature vector for state $s$ and $\mathbf{w}$ holds one weight per feature. Tile coding is a way of building $\mathbf{x}(s)$ so that it is binary (entries are 0 or 1) and sparse (almost all zeros), which makes the sum trivially cheap.

Think of It Like This

How It Actually Works

Tilings, tiles, and asymmetric offsets

Let the state be $s = (s_1, \dots, s_k)$ in $k$ continuous dimensions. One tiling partitions the whole space into boxes (tiles) of width $w_j$ along dimension $j$. Tile coding uses $m$ tilings, all with the same tile widths, each displaced by its own offset vector $\mathbf{o}_i$. The active tile index in tiling $i$ along dimension $j$ is a floor division:

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

Offsets must be asymmetric. Shifting every tiling by the same diagonal step stretches the overlap regions into diagonal slivers, so the agent generalizes along the diagonal and not across it. The standard fix displaces tilings by odd multiples per dimension, keeping overlap patches compact in every direction.

Why prediction costs O(m)

Each tiling covers everything, so every state activates exactly one tile per tiling: $\|\mathbf{x}(s)\|_1 = m$, with entries in $\{0, 1\}$. The value estimate collapses to a sum over the $m$ active weights:

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

No matrix multiply, no search: $m$ memory lookups and $m$ additions, regardless of how fine the effective resolution is. Learning splits the TD error evenly: each active weight moves by $(\alpha / m)$ times the error, where $\alpha$ is the step size. The division by $m$ matters, and the second pitfall below shows what breaks without it.

Two nearby states sharing $k$ of $m$ tiles have feature dot product $k$, so updating one moves the other by fraction $k/m$. Points further apart than a tile width share nothing. When the grid count runs into the billions, tile coordinates are hashed into a fixed weight table; rare collisions spread as uniform noise the averaging absorbs.

Worked example

State $s = (3.6, 7.2)$, tile width $W = 2.0$, $m = 4$ tilings with offsets $(0.0, 0.0)$, $(0.5, 1.5)$, $(1.0, 1.0)$, $(1.5, 0.5)$:

• Tiling 0: $\lfloor 3.6/2.0 \rfloor = 1$, $\lfloor 7.2/2.0 \rfloor = 3$, tile $[1, 3]$.
• Tiling 1: $\lfloor 3.1/2.0 \rfloor = 1$, $\lfloor 5.7/2.0 \rfloor = 2$, tile $[1, 2]$.
• Tiling 2: $\lfloor 2.6/2.0 \rfloor = 1$, $\lfloor 6.2/2.0 \rfloor = 3$, tile $[1, 3]$.
• Tiling 3: $\lfloor 2.1/2.0 \rfloor = 1$, $\lfloor 6.7/2.0 \rfloor = 3$, tile $[1, 3]$.

With learned weights $1.20$, $0.80$, $1.50$, $1.00$ on those four tiles, the estimate is $1.20 + 0.80 + 1.50 + 1.00 = \mathbf{4.50}$, computed in 4 additions. A neighbor at $(3.7, 7.3)$ lands in the same four tiles, so it inherits the same $4.50$ until learning separates them.

Code

The worked example as runnable code: tile indexing, the 4-addition prediction, and one divided-by-$m$ update.

1import math2from typing import Dict, List, Tuple3
4OFFSETS: List[Tuple[float, float]] = [(0.0, 0.0), (0.5, 1.5), (1.0, 1.0), (1.5, 0.5)]5WIDTH = 2.06
7
8def active_tiles(x: float, y: float) -> List[Tuple[int, int, int]]:9    """Active (tiling, col, row) triple for a continuous point."""10    return [11        (i, math.floor((x - ox) / WIDTH), math.floor((y - oy) / WIDTH))12        for i, (ox, oy) in enumerate(OFFSETS)13    ]14
15
16def predict(tiles: List[Tuple[int, int, int]], weights: Dict[Tuple[int, int, int], float]) -> float:17    """Value estimate: plain sum of the m active weights."""18    return sum(weights.get(t, 0.0) for t in tiles)19
20
21tiles = active_tiles(3.6, 7.2)22print(tiles)  # -> [(0, 1, 3), (1, 1, 2), (2, 1, 3), (3, 1, 3)]23weights = {(0, 1, 3): 1.20, (1, 1, 2): 0.80, (2, 1, 3): 1.50, (3, 1, 3): 1.00}24print(f"{predict(tiles, weights):.2f}")  # -> 4.50

The indexing and the $4.50$ prediction match the hand computation tile for tile.

Watch Out For

The Quick Version

• Tile coding overlays $m$ offset grids on continuous space, activating exactly one binary tile per grid for $m$ active features total.
• Asymmetric offsets keep overlap patches compact; symmetric shifts carve diagonal grooves that generalize along one axis only.
• Prediction is a sum of the $m$ active weights: the $(3.6, 7.2)$ example totals 4.50 in 4 additions.
• States sharing $k$ of $m$ tiles move each other by fraction $k/m$ per update, giving broad coverage with pinpoint resolution.
• Split every update across the active tiles with step $\alpha / m$, or the effective step runs $m$ times too hot.
• Hash coordinates into a fixed table when tile counts explode; the rare collisions average out as noise.

What to Read Next

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