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(n1.5(log 1/(1 − λ)+log n)) classical interior-point method iterations and O(n4(log 1/(1 − λ)+log n)) arithmetic operations. Our method is a combinatorial interior-point method related to the work of Ye and Vavasis and Ye. 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.
