- | ||||
|
![]()
|
A New Complexity Result on Solving the Markov Decision Problem
Yinyu Ye (yinyu-ye 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 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 | |
![]() |