Approximate Dynamic Programming via a Smoothed Linear Program

Vijay V. Desai (), Vivek F. Farias () and Ciamac C. Moallemi ()
Additional contact information
Vijay V. Desai: Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027
Vivek F. Farias: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Ciamac C. Moallemi: Graduate School of Business, Columbia University, New York, New York 10027

Operations Research, 2012, vol. 60, issue 3, 655-674

Abstract: We present a novel linear program for the approximation of the dynamic programming cost-to-go function in high-dimensional stochastic control problems. LP approaches to approximate DP have typically relied on a natural “projection” of a well-studied linear program for exact dynamic programming. Such programs restrict attention to approximations that are lower bounds to the optimal cost-to-go function. Our program---the “smoothed approximate linear program”---is distinct from such approaches and relaxes the restriction to lower bounding approximations in an appropriate fashion while remaining computationally tractable. Doing so appears to have several advantages: First, we demonstrate bounds on the quality of approximation to the optimal cost-to-go function afforded by our approach. These bounds are, in general, no worse than those available for extant LP approaches and for specific problem instances can be shown to be arbitrarily stronger. Second, experiments with our approach on a pair of challenging problems (the game of Tetris and a queueing network control problem) show that the approach outperforms the existing LP approach (which has previously been shown to be competitive with several ADP algorithms) by a substantial margin.

Keywords: optimization; linear programming; stochastic control; Markov decision processes; approximate dynamic programming (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1120.1044 (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:60:y:2012:i:3:p:655-674

Access Statistics for this article

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