An Exponential Lower Bound for the Latest Deterministic Strategy Iteration Algorithms

DOI10.2168/LMCS-7(3:23)2011zbMath1237.68087MaRDI QIDQ3224689

Oliver Friedmann

Publication date: 2 April 2012

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

zbMATH Keywords

\(\mu\)-calculusparity gamespolicy iterationexponential lower boundstrategy improvementpayoff games

Mathematics Subject Classification ID

Games involving graphs (91A43) Stochastic games, stochastic differential games (91A15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (10)

Symmetric Strategy Improvement ⋮ The mu-calculus and Model Checking ⋮ Generic uniqueness of the bias vector of finite zero-sum stochastic games with perfect information ⋮ An exponential lower bound for Zadeh's pivot rule ⋮ Parity Games and Propositional Proofs ⋮ Recursive stochastic games with positive rewards ⋮ Unnamed Item ⋮ A superpolynomial lower bound for strategy iteration based on snare memorization ⋮ An exponential lower bound for Cunningham's rule ⋮ Unnamed Item

Uses Software

• PGSolver

This page was built for publication: An Exponential Lower Bound for the Latest Deterministic Strategy Iteration Algorithms