Solving H-horizon, stationary Markov decision problems in time proportional to log (H)

DOI10.1016/0167-6377(90)90022-WzbMath0717.90090MaRDI QIDQ2638964

Paul Tseng

Publication date: 1990

Published in: Operations Research Letters (Search for Journal in Brave)

zbMATH Keywords

polynomial-time algorithm; \(\epsilon \) -approximation; H-horizon, stationary Markov decision

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90C39: Dynamic programming

90C40: Markov and semi-Markov decision processes

90-08: Computational methods for problems pertaining to operations research and mathematical programming

Related Items

A survey of computational complexity results in systems and control, Planning and acting in partially observable stochastic domains, On the undecidability of probabilistic planning and related stochastic optimization problems, Reachability analysis of uncertain systems using bounded-parameter Markov decision processes, Value Iteration

Cites Work

• A new polynomial-time algorithm for linear programming
• Games against nature
• Towards a complexity theory of synchronous parallel computation
• The Complexity of Markov Decision Processes
• Discrete Dynamic Programming with Sensitive Discount Optimality Criteria
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item