On constraint sampling in the linear programming approach to approximate dynamic programming

• 成果类型: Article
• 署名作者: de Farias, DP; Van Roy, B
• 署名单位: Massachusetts Institute of Technology (MIT); Stanford University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1040.0094
• 发表日期: 2004
• 页码: 462-478
• 关键词: algorithms

摘要

In the linear programming approach to approximate dynamic programming, one tries to solve a certain linear program-the ALP-that has a relatively small number K of variables but an intractable number M of constraints. In this paper, we study a scheme that samples and imposes a subset of m much less than M constraints. A natural question that arises in this context is: How must m scale with respect to K and M in order to ensure that the resulting approximation is almost as good as one given by exact solution of the ALP? We show that, given an idealized sampling distribution and appropriate constraints on the K variables, m can be chosen independently of M and need grow only as a polynomial in K. We interpret this result in a context involving controlled queueing networks.