Department of Computer Science Colloquium
Thursday
January 24th, 2002
4:15pm
Upson Hall B17
The Linear Programming Approach to
Approximate Dynamic Programming
Daniela Pucci de Farias
PhD Candidate Management Science and Engineering Stanford University
Dynamic programming offers an elegant, unified treatment of a wide range of stochastic control problems. However, the curse of dimensionality gives rise to prohibitive computational requirements that render infeasible the exact solution of large-scale problems. We study an efficient method based on linear programming for approximating solutions to such problems. The approach ``fits'' a linear combination of pre-selected basis functions to the dynamic programming cost-to-go function. We develop error bounds that offer performance guarantees and also guide the selection of both basis functions and ``state-relevance weights'' that influence quality of the approximation. Experimental results in queuing problems and an application to web-server farms provide empirical support for the methodology.