A new complexity result on solving the Markov decision problem

• 成果类型: Article
• 署名作者: Ye, YY
• 署名单位: Stanford University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1050.0149
• 发表日期: 2005
• 页码: 733-749
• 关键词: polynomial-time algorithm; interior-point algorithms

摘要

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)(log1/(1 - theta) + log n)) classical interior-point method iterations and O(n(4)(log 1/(1 - theta) + log n)) arithmetic operations. Our method is a combinatorial interior-point method related to the work of Ye (1990. A build-down scheme for linear programming. Math. Programming 46 61-72) and Vavasis and Ye (1996. A primal-dual interior-point method whose running time depends only on the constraint matrix. Math. Programming 74 79-120). 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.