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