An Analysis of Laplacian Methods for Value Function Approximation in MDPs
Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 2574-2578.
Abstract
Recently, a method based on Laplacian eigenfunctions was proposed to automatically construct a basis for value function approximation in MDPs. We show that its success may be explained by drawing a connection between the spectrum of the Laplacian and the value function of the MDP. This explanation helps us to identify more precisely the conditions that this method requires to achieve good performance. Based on this, we propose a modification of the Laplacian method for which we derive an analytical bound on the approximation error. Further, we show that the method is related the augmented Krylov methods, commonly used to solve sparse linear systems. Finally, we empirically demonstrate that in basis construction the augmented Krylov methods may significantly outperform the Laplacian methods in terms of both speed and quality.
@inproceedings{ijcai2007p414,
title = {An Analysis of Laplacian Methods for Value Function Approximation in MDPs},
author = {Petrik, Marek},
booktitle = {Proceedings of the Twentieth International Joint Conference on
Artificial Intelligence, {IJCAI-07}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ramon López de Mántaras},
pages = {2574--2578},
year = {2007},
url = {https://ijcai.org/proceedings/2007/414},
}
TY - CPAPER TI - An Analysis of Laplacian Methods for Value Function Approximation in MDPs AU - Petrik, Marek T2 - Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07 PB - International Joint Conferences on Artificial Intelligence PY - 2007 SP - 2574 EP - 2578 UR - https://ijcai.org/proceedings/2007/414 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
