Hash Function for Tile Coding

Representation Learning, Advanced Theory & Miscellaneous DS practice problem on Onlearn.

Difficulty: medium.

Topics: Hash Function for Tile Coding, Collision Resolution, Feature Vector Sparsity, Tiling Overlap, Bitwise XOR Folding, Memory Index Mapping, Reinforcement Learning, Feature Engineering, Computational Geometry, Information Theory, Data Structures, Function Approximation, Sparse Representation, Locality Sensitive Hashing, State Space Discretization, Memory Management.

Implement a tile coding function that maps continuous state variables to a set of active tile indices using a hash function. Tile coding is a method for discretizing continuous spaces used in reinforcement learning function approximation. Your function should: 1. For each tiling (0 to num tilings 1), apply a displacement offset to the state before discretization. The offset for tiling t is t / num tilings (in tile width units). 2. Normalize each state dimension to [0, tiles per dim] using the provided bounds, then add the tiling offset. 3. Discretize each shifted dimension using floor to get integer tile coordinates. 4. Construct a coordinate tuple: (tiling index, tile coord dim0, tile coord dim1, ...). 5. Hash this coordinate tuple into an index in the range [0, memory size) using a djb2 style hash function. 6. Return a list of active tile indices, one per tiling. The djb2 hash works as follows: initialize h = 5381, then for each integer c in the coordinate tuple compute h = ((h 33) + c) masked to 32 bits. The final index is h modulo memory size. Args: state: list of floats, continuous state variables num tilings: int, number of overlapping tilings tiles per dim: int, number of tiles per dimension per tiling memory size: int, size of the hash table (weight vector length) state bounds: optional list of (low, high) tuples per dimension; defaults to (0.0, 1.0) for each dimension Return a list of integers representing the active tile indices.