Article ID: | iaor20073404 |
Country: | United States |
Volume: | 51 |
Issue: | 6 |
Start Page Number: | 850 |
End Page Number: | 865 |
Publication Date: | Nov 2003 |
Journal: | Operations Research |
Authors: | Farias D.P. de, Roy B. Van |
Keywords: | programming: linear |
The curse of dimensionality gives rise to prohibitive computational requirements that render infeasible the exact solution of large-scale stochastic control 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 the domain of queueing network control provide empirical support for the methodology.