The linear programming approach to approximate dynamic programming

The linear programming approach to approximate dynamic programming

0.00 Avg rating0 Votes
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: ,
Keywords: programming: linear
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.