Mathematics of Operations Research
HOME HELP FEEDBACK SUBSCRIPTIONS ARCHIVE SEARCH TABLE OF CONTENTS
 QUICK SEARCH:   [advanced]


     


MATHEMATICS OF OPERATIONS RESEARCH
Vol. 30, No. 3, August 2005, pp. 733-749
DOI: 10.1287/moor.1050.0149
This Article
Right arrow Full Text (PDF)
Right arrow References
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Download to citation manager
Right arrow reprints & permissions
Citing Articles
Right arrow Citing Articles via Google Scholar
Google Scholar
Right arrow Articles by Ye, Y.
Right arrow Search for Related Content

A New Complexity Result on Solving the Markov Decision Problem

Yinyu Ye

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 {theta} is strictly less than 1, the problem can be solved in at most O(n1.5(log 1/(1 – {theta}) + log n)) classical interior-point method iterations and O(n4(log 1/(1 – {theta}) + 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;





HOME HELP FEEDBACK SUBSCRIPTIONS ARCHIVE SEARCH TABLE OF CONTENTS
Copyright © 2005 by INFORMS.