The Simplex Method is Strongly Polynomial for Deterministic Markov Decision Processes

DOI10.1287/moor.2014.0699zbMath1329.90084arXiv1208.5083OpenAlexW2569788251MaRDI QIDQ3465936

Ian Post, Yinyu Ye

Publication date: 29 January 2016

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1208.5083

zbMATH Keywords

linear programmingMarkov decision processsimplex methodstrongly polynomial

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Markov and semi-Markov decision processes (90C40)

Related Items (9)

The greedy strategy for optimizing the Perron eigenvalue ⋮ Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods ⋮ Complexity bounds for approximately solving discounted MDPs by value iterations ⋮ A Friendly Smoothed Analysis of the Simplex Method ⋮ Maximal Acyclic Subgraphs and Closest Stable Matrices ⋮ Unnamed Item ⋮ Modified policy iteration algorithms are not strongly polynomial for discounted dynamic programming ⋮ Improved bound on the worst case complexity of policy iteration ⋮ Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning

Cites Work

• Unnamed Item
• Unnamed Item
• Linear Programming and Sequential Decisions
• The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate
• A Subexponential Lower Bound for Zadeh’s Pivoting Rule for Solving Linear Programs and Games
• Lower Bounds for Howard’s Algorithm for Finding Minimum Mean-Cost Cycles
• Exponential Lower Bounds for Policy Iteration
• The Complexity of Markov Decision Processes
• On the Complexity of the Policy Improvement Algorithm for Markov Decision Processes
• Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
• Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
• A New Complexity Result on Solving the Markov Decision Problem

This page was built for publication: The Simplex Method is Strongly Polynomial for Deterministic Markov Decision Processes