Direct Value-Approximation for Factored MDPs
- Dale Schuurmans, AICML
- Relu Patrascu, Department of Computer Science, University of Toronto
We present a simple approach for computing reasonable policies for factored Markov decision processes (MDPs), when the opti- mal value function can be approximated by a compact linear form. Our method is based on solving a single linear program that ap- proximates the best linear fit to the optimal value function. By applying an efficient constraint generation procedure we obtain an iterative solution method that tackles concise linear programs. This direct linear programming approach experimentally yields a signif- icant reduction in computation time over approximate value- and policy-iteration methods (sometimes reducing several hours to a few seconds). However, the quality of the solutions produced by linear programming is weaker|usually about twice the approxi- mation error for the same approximating class. Nevertheless, the speed advantage allows one to use larger approximation classes to achieve similar error in reasonable time.
Citation
D. Schuurmans, R. Patrascu. "Direct Value-Approximation for Factored MDPs". Neural Information Processing Systems (NIPS), Vancouver, British Columbia, Canada, December 2001.| Keywords: | direct, machine learning |
| Category: | In Conference |
BibTeX
@incollection{Schuurmans+Patrascu:NIPS01,
author = {Dale Schuurmans and Relu Patrascu},
title = {Direct Value-Approximation for Factored MDPs},
booktitle = {Neural Information Processing Systems (NIPS)},
year = 2001,
}Last Updated: August 14, 2007Submitted by Russ Greiner
