Greedy Linear Value-Approximation for Factored Markov Decision Processes
- Relu Patrascu, Department of Computer Science, University of Toronto
- Pascal Poupart, University of Waterloo
- Dale Schuurmans, AICML
- Craig Boutilier, Department of Computer Science, University of Toronto
- Carlos Guestrin, Department of Computer Science, Stanford University
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
R. Patrascu, P. Poupart, D. Schuurmans, C. Boutilier, C. Guestrin. "Greedy Linear Value-Approximation for Factored Markov Decision Processes". National Conference on Artificial Intelligence (AAAI), Edmonton Alberta, July 2002.| Keywords: | Markov, value-approximation, machine learning |
| Category: | In Conference |
BibTeX
@incollection{Patrascu+al:AAAI02,
author = {Relu Patrascu and Pascal Poupart and Dale Schuurmans and Craig
Boutilier and Carlos Guestrin},
title = {Greedy Linear Value-Approximation for Factored Markov Decision
Processes},
booktitle = {National Conference on Artificial Intelligence (AAAI)},
year = 2002,
}Last Updated: June 01, 2007Submitted by Staurt H. Johnson
