The Linear Programming Approach to Approximate Dynamic Programming

D. P. de Farias () and B. Van Roy ()
Additional contact information
D. P. de Farias: Department of Mechanical Engineering, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
B. Van Roy: Department of Management Science and Engineering, Stanford University, Stanford, California 94306

Operations Research, 2003, vol. 51, issue 6, 850-865

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.

Keywords: Dynamic programming/optimal control: approximations/large-scale problems; Queues; algorithms: control of queueing networks (search for similar items in EconPapers)
Date: 2003
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (89)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.51.6.850.24925 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:51:y:2003:i:6:p:850-865

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().