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

www.stanford.edu/~pucci/

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.