Directional Stripe Tilings
Representation Learning, Advanced Theory & Miscellaneous DS practice problem on Onlearn.
Difficulty: medium.
Topics: Directional Stripe Tilings, Wang Tiles, Directional Adjacency Constraints, Local Matching Rules, Entropy of Tiling Spaces, Non-Periodic Substitution Systems, Combinatorial Geometry, Discrete Mathematics, Computational Complexity, Tiling Theory, Algorithmic Information Theory, Aperiodic Tilings, Constraint Satisfaction Problems, Graph Coloring Algorithms, Recursive Pattern Generation, Boundary Condition Analysis.
Implement directional stripe tilings for constructing binary feature vectors from continuous 2D state spaces, a technique commonly used in reinforcement learning for value function approximation. Unlike full tile coding that partitions the entire 2D space into rectangular tiles, stripe tilings use 1D partitions (stripes) along each dimension independently. A horizontal stripe spans the full range of one dimension while discriminating along the other. This provides efficient generalization along each axis separately. Your task is to implement a function that generates stripe tiling feature representations for a list of 2D states. The function should: Accept a list of 2D states (each a tuple of two floats), the bounds of the state space, the number of stripes per dimension per tiling, and the number of overlapping tilings. For each tiling, create stripes along each of the 2 dimensions. Multiple tilings are offset from each other to provide finer resolution. The offset for tiling t along a given dimension is computed as t times the stripe width divided by the total number of tilings. Each stripe index is determined by how the state coordinate (shifted by the offset relative to the dimension's lower bound) falls into the equal width intervals. Indices should be clipped to valid range. Features are indexed sequentially: for tiling t and dimension d, the base index is t (2 num stripes) + d num stripes, plus the computed stripe index. Return a tuple containing: (1) a binary numpy feature matrix of shape (num states, total features) where total features = num tilings 2 num stripes, and (2) a list of lists containing the sorted active feature indices for each state. Each state activates exactly num tilings 2 features (one per dimension per tiling).