A Cost-Shaping Linear Program for Average-Cost Approximate Dynamic Programming with Performance Guarantees
العنوان: | A Cost-Shaping Linear Program for Average-Cost Approximate Dynamic Programming with Performance Guarantees |
---|---|
المؤلفون: | Daniela Pucci de Farias, Benjamin Van Roy |
المصدر: | Mathematics of Operations Research. 31:597-620 |
بيانات النشر: | Institute for Operations Research and the Management Sciences (INFORMS), 2006. |
سنة النشر: | 2006 |
مصطلحات موضوعية: | Dynamic programming, Mathematical optimization, Linear programming, General Mathematics, Second-order cone programming, Basis function, Criss-cross algorithm, Markov decision process, Management Science and Operations Research, Linear combination, Computer Science Applications, Mathematics, Linear-fractional programming |
الوصف: | We introduce a new algorithm based on linear programming for optimization of average-cost Markov decision processes (MDPs). The algorithm approximates the differential cost function of a perturbed MDP via a linear combination of basis functions. We establish a bound on the performance of the resulting policy that scales gracefully with the number of states without imposing the strong Lyapunov condition required by its counterpart in de Farias and Van Roy [de Farias, D. P., B. Van Roy. 2003. The linear programming approach to approximate dynamic programming. Oper. Res. 51(6) 850–865]. We investigate implications of this result in the context of a queueing control problem. |
تدمد: | 1526-5471 0364-765X |
URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_________::dbbc89fb2bb9f6223780b3fd1600b15e https://doi.org/10.1287/moor.1060.0208 |
رقم الأكسشن: | edsair.doi...........dbbc89fb2bb9f6223780b3fd1600b15e |
قاعدة البيانات: | OpenAIRE |
تدمد: | 15265471 0364765X |
---|