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.