Exponential lower bounds for policy iteration

DOI10.1007/978-3-642-14162-1_46MaRDI QIDQ3587467zbMATH OpenOpenAlexFDO

Authors John Fearnley

Publication date 7 September 2010

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-14162-1_46

Mathematics Subject Classification ID

Search theory (90B40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Improved bound on the worst case complexity of policy iteration
• Improved and generalized upper bounds on the complexity of policy iteration
• scientific article; zbMATH DE number 3961380
• An exponential lower bound for the latest deterministic strategy iteration algorithms
• A polynomial time bound for Howard's policy improvement algorithm

Cited in

(25)

• Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time
• An exponential lower bound for the latest deterministic strategy iteration algorithms
• Improved complexity analysis of quasi-polynomial algorithms solving parity games
• Multigrid methods for two-player zero-sum stochastic games.
• The complexity of all-switches strategy improvement
• Optimal schedulers vs optimal bases: an approach for efficient exact solving of Markov decision processes
• Simple stochastic games with almost-sure energy-parity objectives are in NP and conp
• Numerical invariants through convex relaxation and max-strategy iteration
• A subexponential lower bound for Zadeh's pivoting rule for solving linear programs and games
• Towards solving 2-TBSG efficiently
• scientific article; zbMATH DE number 2243354 (Why is no real title available?)
• A novel use of value iteration for deriving bounds for threshold and switching curve optimal policies
• scientific article; zbMATH DE number 7471697 (Why is no real title available?)
• Recursive stochastic games with positive rewards
• The stochastic shortest path problem: a polyhedral combinatorics perspective
• An exponential lower bound for Zadeh's pivot rule
• A complexity analysis of policy iteration through combinatorial matrices arising from unique sink orientations
• The simplex method is strongly polynomial for deterministic Markov decision processes
• The smoothed complexity of policy iteration for Markov decision processes
• An exponential lower bound for Cunningham's rule
• Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• A practitioner's guide to MDP model checking algorithms
• Improved bound on the worst case complexity of policy iteration
• Symmetric strategy improvement
• Universal algorithms for parity games and nested fixpoints

This page was built for publication: Exponential lower bounds for policy iteration

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