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

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

Paul Tseng

Publication date: 1990

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

Full work available at URL: https://doi.org/10.1016/0167-6377(90)90022-w

zbMATH Keywords

polynomial-time algorithm\(\epsilon \) -approximationH-horizon, stationary Markov decision

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Dynamic programming (90C39) Markov and semi-Markov decision processes (90C40) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

A complexity analysis of policy iteration through combinatorial matrices arising from unique sink orientations, Temporal concatenation for Markov decision processes, Reachability analysis of uncertain systems using bounded-parameter Markov decision processes, The value iteration algorithm is not strongly polynomial for discounted dynamic programming, Complexity bounds for approximately solving discounted MDPs by value iterations, Uniform Turnpike Theorems for Finite Markov Decision Processes, Value Iteration, Randomized Linear Programming Solves the Markov Decision Problem in Nearly Linear (Sometimes Sublinear) Time, PageRank optimization by edge selection, A survey of computational complexity results in systems and control, Planning and acting in partially observable stochastic domains, Modified policy iteration algorithms are not strongly polynomial for discounted dynamic programming, Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes, An active-set strategy to solve Markov decision processes with good-deal risk measure, On the undecidability of probabilistic planning and related stochastic optimization problems

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