Piecewise Linear Value Function Approximation for Factored MDPs
- Pascal Poupart, University of Waterloo
- Craig Boutilier, Department of Computer Science, University of Toronto
- Relu Patrascu, Department of Computer Science, University of Toronto
- Dale Schuurmans, AICML
Significant recent work has focused on using linear represen tations to approximate value functions for factored Markov decision processes (MDPs). Current research has adopted lin ear programming as an effective means to calculate approxi mations for a given set of basis functions, tackling very large MDPs as a result. However, a number of issues remain un resolved: How accurate are the approximations produced by linear programs? How hard is it to produce better approxi mations? and Where do the basis functions come from? To address these questions, we first investigate the complexity of minimizing the Bellman error of a linear value function approximation---showing that this is an inherently hard prob lem. Nevertheless, we provide a branch and bound method for calculating Bellman error and performing approximate policy iteration for general factored MDPs. These methods are more accurate than linear programming, but more expen sive. We then consider linear programming itself and inves tigate methods for automatically constructing sets of basis functions that allow this approach to produce good approxi mations. The techniques we develop are guaranteed to reduce L1 error, but can also empirically reduce Bellman error.
Citation
P. Poupart, C. Boutilier, R. Patrascu, D. Schuurmans. "Piecewise Linear Value Function Approximation for Factored MDPs". National Conference on Artificial Intelligence (AAAI), Edmonton Alberta, July 2002.Keywords: | factored, machine learning |
Category: | In Conference |
BibTeX
@incollection{Poupart+al:AAAI02, author = {Pascal Poupart and Craig Boutilier and Relu Patrascu and Dale Schuurmans}, title = {Piecewise Linear Value Function Approximation for Factored MDPs}, booktitle = {National Conference on Artificial Intelligence (AAAI)}, year = 2002, }Last Updated: June 01, 2007
Submitted by Staurt H. Johnson