A Cost-Shaping Linear Program for Average-Cost Approximate Dynamic Programming with Performance Guarantees

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 resulti...

Full description

Saved in:
Bibliographic Details
Published in:Mathematics of operations research 2006-08, Vol.31 (3), p.597-620
Main Authors: de Farias, Daniela Pucci, Van Roy, Benjamin
Format: Article
Language:English
Subjects:
Algorithms
Analysis
approximate dynamic programming
Approximation
Average
Average cost
Cost accounting
Cost functions
Dynamic programming
Linear programming
Markov analysis
Mathematical functions
Mathematical theorems
Mathematics
Optimal solutions
Optimization algorithms
Process costing
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0364-765X
1526-5471
DOI:10.1287/moor.1060.0208