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/2004
Entry Accepted: 10/05/2004
Entry Last Modified: 10/05/2004

Modify/Update this entry