On the Complexity of Value Iteration

DOI10.4230/LIPICS.ICALP.2019.102MaRDI QIDQ5091264zbMATH OpenOpenAlexFDO

Authors Nikhil Balaji, Stefan Kiefer, Petr Novotný, G. A. Pérez, Mahsa Shirmohammadi

Publication date 21 July 2022

Full work available at URL https://arxiv.org/abs/1807.04920

zbMATH Keywords

formal verificationMarkov decision processesvalue iteration

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Recommendations

• Reachability in MDPs: refining convergence of value iteration
• Value Iteration
• The Complexity of Markov Decision Processes
• Complexity bounds for approximately solving discounted MDPs by value iterations
• The value iteration algorithm is not strongly polynomial for discounted dynamic programming

Cites work

• A note on succinct representations of graphs
• A survey of computational complexity results in systems and control
• Complexity of finite-horizon Markov decision process problems
• Dynamic programming and optimal control. Vol. 1.
• Handbook of model checking
• scientific article; zbMATH DE number 3126094 (Why is no real title available?)
• scientific article; zbMATH DE number 4061056 (Why is no real title available?)
• scientific article; zbMATH DE number 1216123 (Why is no real title available?)
• scientific article; zbMATH DE number 1335900 (Why is no real title available?)
• scientific article; zbMATH DE number 1786127 (Why is no real title available?)
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• scientific article; zbMATH DE number 5585443 (Why is no real title available?)
• Limit synchronization in Markov decision processes
• Low-depth uniform threshold circuits and the bit-complexity of straight line programs
• Markov decision processes with applications to finance.
• On the Complexity of Numerical Analysis
• Reinforcement learning. An introduction
• Sound value iteration
• The Complexity of Decentralized Control of Markov Decision Processes
• The Complexity of Markov Decision Processes
• The complexity of the simplex method
• Topological value iteration algorithms
• Uniform constant-depth threshold circuits for division and iterated multiplication.

Cited in

(9)

• The value iteration algorithm is not strongly polynomial for discounted dynamic programming
• Comparison of algorithms for simple stochastic games
• On the \(p\)-reinforcement and the complexity
• Complexity bounds for approximately solving discounted MDPs by value iterations
• Value iteration for simple stochastic games: stopping criterion and learning algorithm
• scientific article; zbMATH DE number 3637739 (Why is no real title available?)
• Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games
• A practitioner's guide to MDP model checking algorithms
• Stochastic processes with expected stopping time

This page was built for publication: On the Complexity of Value Iteration

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5091264)