Coarse Coding with Multiple Tilings

A state does not activate several tiles within one partition. It activates one tile in each separate tiling.

Programming

From One Tile to a Coarse Representation

Suppose a state lies in a two-dimensional space divided into tiles. With only one tiling, the state activates the single tile that contains it. That representation is useful for locating the state, but two different states in different tiles appear completely unrelated. Multiple tilings change this situation: each copy of the partition is shifted, so one state can share some tiles with nearby states while differing on others. This overlap is the basis of coarse coding.

Key point

A state does not activate several tiles within one partition. It activates one tile in each separate tiling.

Tracing One State Across Tilings

Worked example

One State, Several Active Features

Consider a state presented to several shifted tilings. Trace which features become active.

1
Tiling 1
The state selects one tile in the first partition, so the feature for that tile becomes active.
2
Tiling 2
Because the second partition is shifted, the same state may lie in a different tile. One feature from this tiling becomes active as well.
3
Tiling 3
The third shifted partition supplies one more selected tile and therefore one more active feature.
4
Combined representation
The complete feature representation contains all selected tiles, with one active feature contributed by each tiling.

Result

The state is represented by a combination of active features rather than by one tile from one partition.

Which tile is activated in each tiling, and how do those activations combine into one feature representation?

Why Shared Tiles Generalize

Training on one state can affect another state when both states select some of the same tiles. The more selected tiles two states have in common, the stronger their connection through the representation. In this way, multiple tilings create graded generalization: states are not simply classified as identical or completely unrelated.

Worked example

Comparing Two Nearby States

Two states are represented across several tilings. State p and state q select some of the same tiles but not all of them. What does this overlap imply?

1
Compare selected tiles
List the tile selected by each state in every tiling and identify the matches.
2
Interpret the matches
Each shared selected tile gives the two states a connection through the representation.
3
Relate overlap to learning
Learning associated with one state can influence the other through their shared tiles.

Result

The states generalize to one another, with the strength of the connection determined by how many selected tiles they share.

Which tiles are shared by two states, and how does that overlap support generalization?

Offsets and Displacement Vectors

Definition

A displacement vector describes how one tiling is shifted relative to the previous tiling. If w is the tile width and k is the number of tilings, the basic displacement unit is w divided by k.

In two dimensions, the vector (1, 1) means that the next tiling shifts by one displacement unit in both dimensions. The vector (1, 3) shifts by one unit in the first dimension and three units in the second. The second vector is asymmetric because its shifts differ across dimensions.

How do different displacement vectors shift each tiling, and why can asymmetric offsets reduce diagonal artifacts?

Offsets determine which nearby states share tiles. Uniform offsets in every dimension can produce noticeable diagonal patterns in the generalization behavior. Asymmetric offsets vary the shifts between dimensions, producing patterns that are better centered on the trained state and avoiding the obvious asymmetries associated with uniform offsets.

Recommended Pattern in d Dimensions

For a space with dimension d, the recommended displacement pattern uses the first odd integers for the dimensions: 1, 3, 5, and so on, ending with 2d minus 1. This pattern is intended to distribute generalization more evenly and reduce the diagonal artifacts associated with uniform offsets.

Dimension	Recommended displacement entries
1	1
2	1, 3
3	1, 3, 5
d	1, 3, 5, ..., 2d minus 1

The recommended displacement vector uses successive odd integers across the dimensions.

The number of tilings k should be an integer power of 2 that is at least 4d. The displacement unit is then determined from the tile width and this number of tilings.

For a d-dimensional space, which odd displacement entries are assigned across the dimensions?

Mistakes Beginners Make

Common mistake
Assuming a state activates several tiles within one tiling
What it looks like
A state is described as belonging to multiple tiles in the same partition.
Why it fails
Each tiling is a separate partition, and a state selects one tile per tiling.
Do this instead
Count one selected tile from each tiling, then combine those selections into the feature representation.
Common mistake
Treating all different states as completely unrelated
What it looks like
Two states select different tiles in at least one tiling, so they are assumed to have no connection.
Why it fails
States can share some selected tiles even when their full representations differ.
Do this instead
Count shared selected tiles. More shared tiles mean stronger generalization through the representation.
Common mistake
Assuming uniform offsets are always neutral
What it looks like
The same displacement amount is used in every dimension without considering the resulting pattern.
Why it fails
Uniform offsets can create noticeable diagonal artifacts.
Do this instead
Use asymmetric displacement entries, with the recommended pattern based on successive odd integers.
Common mistake
Choosing arbitrary displacement entries for a d-dimensional space
What it looks like
A two-dimensional space is assigned the same displacement entry in both dimensions.
Why it fails
The recommended pattern assigns 1, 3, 5, and so on across the dimensions.
Do this instead
Use the first odd integers, ending with 2d minus 1.

Apply the Representation

MEDIUM

A state space has dimension d. Describe the recommended displacement vector pattern, explain how many tiles the state selects from each tiling, and state what shared tiles between two states imply about generalization.

Hints

Start the displacement entries with the first odd integers.
Remember that each state selects one tile per tiling, not several tiles from one tiling.
Relate the number of shared selected tiles to the strength of the connection between the states.

Your attempt (not saved)

What do you think happens?

Two states share three selected tiles across their tilings, while another pair shares only one selected tile. Which pair has the stronger connection through the representation?

The pair sharing three selected tiles
The pair sharing one selected tile
Both pairs have the same connection

Reveal answer

Answer:

The pair sharing three selected tiles

Generalization is proportional to the number of shared tiles, so the pair with more shared selected tiles has the stronger connection.

Summary

1
Multiple shifted tilings create overlapping receptive fields, which provide coarse coding.
2
A state selects one tile and activates one feature in each tiling.
3
States that share more selected tiles generalize more strongly to one another.
4
Displacement vectors control how tilings shift and therefore influence the boundaries of generalization.
5
Asymmetric offsets can reduce diagonal artifacts; the recommended entries for dimension d are 1, 3, 5, and so on through 2d minus 1.

At a glance

Multiple offset tilings turn non-overlapping partitions into overlapping receptive fields.
Each state activates exactly one selected tile per tiling, producing a combined feature representation.
Shared selected tiles allow learning about one state to generalize to another, with more overlap producing stronger generalization.
Asymmetric displacement vectors can reduce diagonal artifacts.
For dimension d, use the odd-integer pattern 1, 3, 5, ..., 2d minus 1, with a number of tilings that is an integer power of 2 and at least 4d.

Related concepts

More concepts starting with C