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 Ye, Y. Search for Related Content

A New Complexity Result on Solving the Markov Decision Problem

Department of Management Science and Engineering, Terman 316, Stanford University, Stanford, California 94305
yinyu-ye{at}stanford.edu, www.stanford.edu/~yyye

We present a new complexity result on solving the Markov decision problem (MDP) with n states and a number of actions for each state, a special class of real-number linear programs with the Leontief matrix structure. We prove that when the discount factor is strictly less than 1, the problem can be solved in at most O(n^1.5(log 1/(1 – ) + log n)) classical interior-point method iterations and O(n⁴(log 1/(1 – ) + log n)) arithmetic operations. Our method is a combinatorial interior-point method related to the work of Ye (1990. A "build-down" scheme for linear programming. Math. Programming 46 61–72) and Vavasis and Ye (1996. A primal-dual interior-point method whose running time depends only on the constraint matrix. Math. Programming 74 79–120). To our knowledge, this is the first strongly polynomial-time algorithm for solving the MDP when the discount factor is a constant less than 1.

Key Words: Markov decision problem; linear programming; complexity
History: Received: November 4, 2003; revision received: October 3, 2004;revision received: December 27, 2004;