Exponential Lower Bounds for Policy Iteration

DOI10.1007/978-3-642-14162-1_46zbMath1288.68089OpenAlexW1928484725MaRDI QIDQ3587467

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)

Related Items (20)

A complexity analysis of policy iteration through combinatorial matrices arising from unique sink orientations ⋮ Symmetric Strategy Improvement ⋮ The Simplex Method is Strongly Polynomial for Deterministic Markov Decision Processes ⋮ The stochastic shortest path problem: a polyhedral combinatorics perspective ⋮ An exponential lower bound for Zadeh's pivot rule ⋮ Recursive stochastic games with positive rewards ⋮ Universal algorithms for parity games and nested fixpoints ⋮ Continuous Positional Payoffs ⋮ Improved complexity analysis of quasi-polynomial algorithms solving parity games ⋮ Towards solving 2-TBSG efficiently ⋮ Unnamed Item ⋮ 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 ⋮ A Subexponential Lower Bound for Zadeh’s Pivoting Rule for Solving Linear Programs and Games ⋮ Numerical invariants through convex relaxation and max-strategy iteration ⋮ Multigrid methods for two‐player zero‐sum stochastic games ⋮ Unnamed Item ⋮ Improved bound on the worst case complexity of policy iteration ⋮ Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes ⋮ Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time

This page was built for publication: Exponential Lower Bounds for Policy Iteration