The smoothed complexity of policy iteration for Markov decision processes
From MaRDI portal
Publication:6499347
DOI10.1145/3564246.3585220MaRDI QIDQ6499347FDOQ6499347
Authors: Miranda Christ, Mihalis Yannakakis 
Publication date: 8 May 2024
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- The complexity of probabilistic verification
- Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
- Finite state Markovian decision processes
- Smoothed analysis of algorithms
- Simple Local Search Problems that are Hard to Solve
- Markov decision processes and regular events
- The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate
- An exponential lower bound for Cunningham's rule
- On the Complexity of the Policy Improvement Algorithm for Markov Decision Processes
- The complexity of the simplex method
- Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor
- Model checking probabilistic systems
- Smoothed analysis of local search for the maximum-cut problem
- Improved bound on the worst case complexity of policy iteration
- Local max-cut in smoothed polynomial time
- Exponential lower bounds for policy iteration
- Smoothed analysis of the 2-Opt algorithm for the general TSP
- A friendly smoothed analysis of the simplex method
- Improving the Smoothed Complexity of FLIP for Max Cut Problems
- An exponential lower bound for Zadeh's pivot rule
This page was built for publication: The smoothed complexity of policy iteration for Markov decision processes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6499347)
