The linear programming approach to approximate dynamic programming

• 成果类型: Article
• 署名作者: De Farias, DP; Van Roy, B
• 署名单位: Massachusetts Institute of Technology (MIT); Stanford University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.51.6.850.24925
• 发表日期: 2003
• 页码: 850-865
• 关键词: dynamic programming/optimal control : approximations/large-scale problems; queues; algorithms : control of queueing networks

摘要

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.