Tile Coding Implementation
Representation Learning, Advanced Theory & Miscellaneous DS practice problem on Onlearn.
Difficulty: medium.
Topics: Tile Coding Implementation, Hashing Functions, Overlapping Tilings, Active Feature Indices, Resolution Scaling, Offset Vector Perturbation, Reinforcement Learning, Function Approximation, Feature Engineering, Computational Geometry, Numerical Analysis, Linear Function Approximation, State Space Discretization, Sparse Vector Representations, Generalization Methods, Grid-based Encoding.
Implement tile coding, a key feature construction method for reinforcement learning with continuous state spaces. Tile coding converts continuous state variables into a sparse binary feature representation by overlaying multiple offset grids (tilings) across the state space. Each tiling partitions the space into tiles, and a given state activates exactly one tile per tiling. The offsets between tilings ensure that nearby states share some (but not all) active tiles, providing smooth generalization. Given: state: a list of floats representing the continuous state (one value per dimension) num tilings: the number of tilings to overlay tiles per dim: a list of integers specifying how many tiles each dimension is divided into (per tiling) state low: a list of floats for the lower bound of each dimension state high: a list of floats for the upper bound of each dimension For each tiling, the grid is uniformly offset. The tile width for dimension d is (state high[d] state low[d]) / tiles per dim[d]. Each tiling t (0 indexed) has its grid shifted by t tile width d / num tilings in dimension d. The tile index for a dimension is obtained by flooring the adjusted position, then clipping to valid bounds [0, tiles per dim[d] 1]. Tile indices within a tiling are flattened using row major (C style) ordering. Global tile indices are computed by offsetting each tiling's local index by t tiles per tiling, where tiles per tiling is the product of all tiles per dim values. Return a tuple of: 1. A list of active global tile indices (one per tiling) 2. The total number of tiles across all tilings