The smoothed complexity of policy iteration for Markov decision processes
From MaRDI portal
Publication:6499347
Cites work
- scientific article; zbMATH DE number 3126094 (Why is no real title available?)
- scientific article; zbMATH DE number 3148886 (Why is no real title available?)
- scientific article; zbMATH DE number 700091 (Why is no real title available?)
- A friendly smoothed analysis of the simplex method
- An exponential lower bound for Cunningham's rule
- An exponential lower bound for Zadeh's pivot rule
- Exponential lower bounds for policy iteration
- Finite state Markovian decision processes
- Improved bound on the worst case complexity of policy iteration
- Improving the Smoothed Complexity of FLIP for Max Cut Problems
- Local max-cut in smoothed polynomial time
- Markov decision processes and regular events
- Model checking probabilistic systems
- On the Complexity of the Policy Improvement Algorithm for Markov Decision Processes
- Simple Local Search Problems that are Hard to Solve
- Smoothed analysis of algorithms
- Smoothed analysis of local search for the maximum-cut problem
- Smoothed analysis of the 2-Opt algorithm for the general TSP
- Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor
- Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
- The complexity of probabilistic verification
- The complexity of the simplex method
- The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate
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)
