The smoothed complexity of policy iteration for Markov decision processes

DOI10.1145/3564246.3585220MaRDI QIDQ6499347

Miranda Christ, Mihalis Yannakakis

Publication date: 8 May 2024

zbMATH Keywords

policy iterationsmoothed analysis

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An exponential lower bound for Cunningham's rule
• Improved bound on the worst case complexity of policy iteration
• Finite state Markovian decision processes
• The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate
• The Complexity of the Simplex Method
• Model Checking Probabilistic Systems
• Simple Local Search Problems that are Hard to Solve
• Smoothed analysis of algorithms
• Exponential Lower Bounds for Policy Iteration
• On the Complexity of the Policy Improvement Algorithm for Markov Decision Processes
• The complexity of probabilistic verification
• Markov decision processes and regular events
• Smoothed Analysis of the 2-Opt Algorithm for the General TSP
• Smoothed Analysis of Local Search for the Maximum-Cut Problem
• Local max-cut in smoothed polynomial time
• Improving the Smoothed Complexity of FLIP for Max Cut Problems
• A Friendly Smoothed Analysis of the Simplex Method
• 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
• 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