  


A New Complexity Result on Solving the Markov Decision Problem
Yinyu Ye (yinyuyestanford.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 realnumber 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 interiorpoint method iterations and $O(n^{4}(\log\frac{1}{1\theta}+\log n))$ arithmetic operations. Our method is a {\em combinatorial} interiorpoint method related to the work of Ye \cite{Ye90} and Vavasis and Ye \cite{VavasisYe}. To our knowledge, this is the first {\em strongly polynomialtime} 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/2004 Modify/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  