  Using function approximation to represent a value function is necessary for
continuous and high-dimensional state spaces. Linear function approximation has
desirable theoretical guarantees and often requires less compute and samples
than neural networks, but most approaches suffer from an exponential growth in
the number of functions as the dimensionality of the state space increases. In
this work, we introduce the wavelet basis for reinforcement learning. Wavelets
can effectively be used as a fixed basis and additionally provide the ability
to adaptively refine the basis set as learning progresses, making it feasible
to start with a minimal basis set. This adaptive method can either increase the
granularity of the approximation at a point in state space, or add in
interactions between different dimensions as necessary. We prove that wavelets
are both necessary and sufficient if we wish to construct a function
approximator that can be adaptively refined without loss of precision. We
further demonstrate that a fixed wavelet basis set performs comparably against
the high-performing Fourier basis on Mountain Car and Acrobot, and that the
adaptive methods provide a convenient approach to addressing an oversized
initial basis set, while demonstrating performance comparable to, or greater
than, the fixed wavelet basis.
