← Search

The Linear Programming Approach to Approximate Dynamic Programming

D. P. de Farias¹; B. Van Roy²

¹ Department of Mechanical Engineering, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139 · ² Department of Management Science and Engineering, Stanford University, Stanford, California 94306

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.

DOI

10.1287/opre.51.6.850.24925

Volume

51 (6)

Pages

850-865

Language

en

Export

BibTeX

Sources

crossref