- A New Complexity Result on Solving the Markov Decision Problem Yinyu Ye (yinyu-yestanford.edu) Abstract: 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(n^{1.5}(\log\frac{1}{1-\theta}+\log n))$ classical interior-point method iterations and $O(n^{4}(\log\frac{1}{1-\theta}+\log n))$ arithmetic operations. Our method is a {\em combinatorial} interior-point method related to the work of Ye \cite{Ye90} and Vavasis and Ye \cite{VavasisYe}. To our knowledge, this is the first {\em strongly polynomial-time} algorithm for solving the MDP with fixed discount factor or interest rate. Keywords: Markov Decision, Linear Programming, Dynamic Programming Category 1: Linear, Cone and Semidefinite Programming (Linear Programming ) Citation: Working Paper, Department of Management Science and Engineering, Stanford University, Stanford, CA 94305; September 2002 (revised October 2004). Download: [PDF]Entry Submitted: 10/05/2004Entry Accepted: 10/05/2004Entry Last Modified: 10/05/2004Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.