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 queueing problems and an application to web server farms provide empirical support for the methodology.
