Exponential lower bounds for policy iteration

DOI10.1007/978-3-642-14162-1_46zbMATH Open1288.68089OpenAlexW1928484725MaRDI QIDQ3587467FDOQ3587467

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

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

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

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
Title not available (Why is that?)
Towards solving 2-TBSG efficiently
A novel use of value iteration for deriving bounds for threshold and switching curve optimal policies
Title not available (Why is that?)
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
Universal algorithms for parity games and nested fixpoints
Symmetric strategy improvement
Improved bound on the worst case complexity of policy iteration

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)