Sparse Approximate Policy Evaluation using Graph-based Basis Functions
Jeff Johns, Sridhar Mahadevan · 2009
Proto-value functions and diffusion wavelets are graph-based basis functions that capture topological structure of the MDP state space. A subset of these basis functions must be selected when approximating value functions in order to maintain computational efficiency and prevent overfitting. We evaluated four basis selection algorithms for performing this task. This is an enhancement over the previously used heuristic of always selecting the most global, or smoothest, subset of basis functions regardless of the policy being evaluated. We analyzed two schemes, one direct and one indirect, for combining basis selection and approximate policy evaluation. The indirect scheme requires more computation than the direct scheme, but gains flexibility in the manner in which basis functions are selected. The coefficients applied to the basis functions were set using least-squares methods. We also described how least-squares methods can be altered to include regularization. Laplacian-based regularization provides a bias toward smoother approximate value functions which can prevent overfitting and can be useful in stochastic domains. A thorough set of experiments was conducted on a simple chain MDP to understand how basis selection and the different least-squares policy evaluation algorithms impact one another. Although the experiments used graph-based basis functions, the algorithms described in this paper can be applied to any set of basis functions. 1