This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by de Farias, D. P. Articles by Van Roy, B. Search for Related Content

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

Department of Mechanical Engineering, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Departments of Management Science and Engineering and Electrical Engineering, Stanford University, Stanford, California 94305
pucci{at}mit.edu
bvr{at}stanford.edu

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.

Key Words: approximate dynamic programming; linear programming; average cost
History: Received: September 12, 2004; revision received: December 6, 2005;