Generalization in Tiling Strategies

Multiple tilings provide the overlapping receptive fields needed for coarse coding.

Programming

From One Partition to Coarse Coding

Imagine dividing a state space into a grid. A single grid can tell you which tile contains a state, but it gives every state in that tile the same representation and does not create overlapping receptive fields. Multiple tilings solve this limitation by placing several copies of the partition over the same space and shifting each copy by a fraction of a tile width. Each state then receives one selected tile from every tiling. Those selected tiles together form a coarse-coded representation.

How do several shifted grids divide the same state space, and why does their overlap create a coarse-coded representation?

Tracing One State

For a particular state, the selection process is performed independently in every tiling. The state belongs to one tile in the first tiling, one tile in the second tiling, and so on. It does not belong to several tiles within one partition. The feature vector has a component for every tile in every tiling, but only the components corresponding to the selected tiles become active.

What happens to a single state as it is mapped into each tiling, and which tile becomes active in every tiling?

A State with Four Tilings

Suppose a two-dimensional state is represented with four separate tilings. Trace the active features for one state.

Select from the first tiling: The state selects one tile in tiling 1. That tile contributes one active feature.

Repeat for the remaining tilings: The same state selects one tile in tiling 2, one in tiling 3, and one in tiling 4. The selected tiles may be different because the tilings are shifted.

Assemble the representation: The feature vector contains one active component for each selected tile, giving four active features in total, one from each tiling.

One state activates one feature per tiling, not several features within a single tiling.

Shared Tiles and Graded Generalization

Generalization occurs when two states select some of the same tiles. Training on one state can then affect another state because both states use shared features. The more selected tiles the two states have in common, the stronger their connection through the representation. This creates a graded pattern of generalization instead of treating every different state as completely unrelated.

Which features are shared by two nearby states, and how does a shared tile cause one learned value to generalize between them?

Comparing Shared Feature Counts

Consider three pairs of states. Pair A shares many selected tiles, Pair B shares fewer, and Pair C shares none. What does the representation imply about generalization?

Pair A: Because the states share many selected tiles, training on one has a stronger connection to the other.

Pair B: Because the states share fewer selected tiles, the connection between them is weaker.

Pair C: With no shared selected tiles, the representation provides no shared-feature connection between the states.

The number of shared selected tiles controls the strength of generalization between the states.

Displacement and Boundary Patterns

A displacement vector describes how one tiling is shifted relative to the previous tiling. If the tile width is w and there are k 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) means that the shift is one unit in the first dimension and three units in the second.

Offsets determine which nearby states share tiles. Within a small square whose side is the displacement unit, every state activates the same tiles and therefore receives the same feature representation and approximated value. Moving a state by one displacement unit in a Cartesian direction changes the feature representation by one component or tile. The displacement pattern therefore controls the boundaries of generalization.

How do symmetric and asymmetric offsets change grid-boundary placement, and why can asymmetric offsets reduce diagonal artifacts?

Choosing Offsets 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 asymmetric pattern is intended to distribute the tiling offsets effectively and reduce the diagonal artifacts associated with uniform offsets. The number of tilings k should be an integer power of 2 that is at least 4d.

How are displacement vectors arranged across d dimensions, and what pattern should be selected?

Selecting a Pattern for Three Dimensions

Choose the recommended displacement vector pattern for a three-dimensional space.

List the dimension positions: There are three dimensions, so the pattern needs three entries.

Use successive odd integers: The first three odd integers are 1, 3, and 5.

Check the final entry: For d equal to 3, the final recommended entry is 2d minus 1, which is 5.

The recommended displacement vector pattern is (1, 3, 5).

Common Reasoning Errors

Assuming that 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 active feature from each tiling.
Assuming that different states cannot share features.
States from different locations may select some of the same tiles across the tilings.
Fix: Compare their selected tiles. Shared tiles create the representation-level connection.
Treating all generalization as equally strong.
The strength of generalization is proportional to the number of shared tiles.
Fix: Use the shared-tile count as a graded measure of their connection.
Using identical offset components in every dimension without considering artifacts.
Uniform offsets can produce noticeable diagonal patterns.
Fix: Consider the recommended odd-integer pattern across dimensions.
Choosing displacement entries without regard to dimension.
The recommended pattern supplies one entry for each dimension.
Fix: For dimension d, use 1, 3, 5, and so on through 2d minus 1.

Practice Check

MEDIUM

A state is represented using five tilings. Another state shares three of the selected tiles with it. Explain how many active features each state receives and what the three shared tiles imply about generalization.

Hints

Start by applying the one-tile-per-tiling rule.
Then compare the selected tiles of the two states.
Use the number of shared tiles to describe the strength of their connection.

Your attempt (not saved)

MEDIUM

For a four-dimensional space, select the recommended displacement vector pattern. Then explain why this pattern is preferred over using the same offset in every dimension.

Hints

List the first four odd integers.
The final entry should equal 2d minus 1.
Relate different offsets across dimensions to diagonal artifacts.

Your attempt (not saved)

Key Takeaways

A single tiling partitions the space but does not provide the overlapping receptive fields needed for coarse coding.
Multiple shifted tilings give each state one selected tile, and therefore one active feature, per tiling.
Two states generalize to one another through the tiles they select in common; more shared tiles mean a stronger connection.
Displacement vectors determine how tiling boundaries are arranged and which nearby states share features.
For dimension d, the recommended displacement pattern uses 1, 3, 5, and so on through 2d minus 1, with a tiling count that is an integer power of 2 and at least 4d.

Key Takeaways

Multiple offset tilings turn separate partitions into overlapping receptive fields for coarse coding.
Every state activates exactly one feature in each tiling.
Shared active tiles allow learning at one state to generalize to another, with strength proportional to the number of shared tiles.
Asymmetric displacement vectors can reduce diagonal artifacts caused by uniform offsets.
The recommended displacement pattern in d dimensions is 1, 3, 5, through 2d minus 1.