Value Function Approximation with Diffusion Wavelets and Laplacian Eigenfunctions

Part of Advances in Neural Information Processing Systems 18 (NIPS 2005)

Bibtex Metadata Paper


Sridhar Mahadevan, Mauro Maggioni


We investigate the problem of automatically constructing ef´Čücient rep- resentations or basis functions for approximating value functions based on analyzing the structure and topology of the state space. In particu- lar, two novel approaches to value function approximation are explored based on automatically constructing basis functions on state spaces that can be represented as graphs or manifolds: one approach uses the eigen- functions of the Laplacian, in effect performing a global Fourier analysis on the graph; the second approach is based on diffusion wavelets, which generalize classical wavelets to graphs using multiscale dilations induced by powers of a diffusion operator or random walk on the graph. Together, these approaches form the foundation of a new generation of methods for solving large Markov decision processes, in which the underlying repre- sentation and policies are simultaneously learned.