Coarse Coding with Multiple Tilings
Multiple tilings provide the overlapping receptive fields needed for coarse coding.
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.
A state does not activate several tiles within one partition. It activates one tile in each separate tiling.
Tracing One State Across Tilings
One State, Several Active Features
Consider a state presented to several shifted tilings. Trace which features become active.
Tiling 1: The state selects one tile in the first partition, so the feature for that tile becomes active.
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.
Tiling 3: The third shifted partition supplies one more selected tile and therefore one more active feature.
Combined representation: The complete feature representation contains all selected tiles, with one active feature contributed by each tiling.
The state is represented by a combination of active features rather than by one tile from one partition.
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.
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?
Compare selected tiles: List the tile selected by each state in every tiling and identify the matches.
Interpret the matches: Each shared selected tile gives the two states a connection through the representation.
Relate overlap to learning: Learning associated with one state can influence the other through their shared tiles.
The states generalize to one another, with the strength of the connection determined by how many selected tiles they share.
Offsets and Displacement Vectors
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.
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.
Mistakes Beginners Make
Assuming a state activates several tiles within one tiling
Each tiling is a separate partition, and a state selects one tile per tiling.
Fix:
Count one selected tile from each tiling, then combine those selections into the feature representation.Treating all different states as completely unrelated
States can share some selected tiles even when their full representations differ.
Fix:
Count shared selected tiles. More shared tiles mean stronger generalization through the representation.Assuming uniform offsets are always neutral
Uniform offsets can create noticeable diagonal artifacts.
Fix:
Use asymmetric displacement entries, with the recommended pattern based on successive odd integers.Choosing arbitrary displacement entries for a d-dimensional space
The recommended pattern assigns 1, 3, 5, and so on across the dimensions.
Fix:
Use the first odd integers, ending with 2d minus 1.
Apply the Representation
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.
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?
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
- Multiple shifted tilings create overlapping receptive fields, which provide coarse coding.
- A state selects one tile and activates one feature in each tiling.
- States that share more selected tiles generalize more strongly to one another.
- Displacement vectors control how tilings shift and therefore influence the boundaries of generalization.
- Asymmetric offsets can reduce diagonal artifacts; the recommended entries for dimension d are 1, 3, 5, and so on through 2d minus 1.
Key Takeaways
- 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.