Complexity bounds for approximately solving discounted MDPs by value iterations

DOI10.1016/j.orl.2020.07.001zbMath1479.90212OpenAlexW3039679414MaRDI QIDQ2661516

Gaojin He, Eugene A. Feinberg

Publication date: 7 April 2021

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

Full work available at URL: https://doi.org/10.1016/j.orl.2020.07.001

zbMATH Keywords

complexityalgorithmMarkov decision processdiscountingoptimal policy

Mathematics Subject Classification ID

Markov and semi-Markov decision processes (90C40)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The value iteration algorithm is not strongly polynomial for discounted dynamic programming
• Modified policy iteration algorithms are not strongly polynomial for discounted dynamic programming
• A bound for the number of different basic solutions generated by the simplex method
• Gaussian elimination is not optimal
• Solving H-horizon, stationary Markov decision problems in time proportional to log (H)
• The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate
• Improved and Generalized Upper Bounds on the Complexity of Policy Iteration
• Powers of tensors and fast matrix multiplication
• The Simplex Method is Strongly Polynomial for Deterministic Markov Decision Processes
• Modified Policy Iteration Algorithms for Discounted Markov Decision Problems
• Uniform Turnpike Theorems for Finite Markov Decision Processes

This page was built for publication: Complexity bounds for approximately solving discounted MDPs by value iterations