The simplex method is strongly polynomial for deterministic Markov decision processes
From MaRDI portal
Abstract: We prove that the simplex method with the highest gain/most-negative-reduced cost pivoting rule converges in strongly polynomial time for deterministic Markov decision processes (MDPs) regardless of the discount factor. For a deterministic MDP with n states and m actions, we prove the simplex method runs in O(n^3m^2log^2 n) iterations if the discount factor is uniform and O(n^5m^3log^2 n) iterations if each action has a distinct discount factor. Previously the simplex method was known to run in polynomial time only for discounted MDPs where the discount was bounded away from 1 [Ye11]. Unlike in the discounted case, the algorithm does not greedily converge to the optimum, and we require a more complex measure of progress. We identify a set of layers in which the values of primal variables must lie and show that the simplex method always makes progress optimizing one layer, and when the upper layer is updated the algorithm makes a substantial amount of progress. In the case of nonuniform discounts, we define a polynomial number of "milestone" policies and we prove that, while the objective function may not improve substantially overall, the value of at least one dual variable is always making progress towards some milestone, and the algorithm will reach the next milestone in a polynomial number of steps.
Recommendations
- The simplex method is strongly polynomial for deterministic Markov decision processes
- The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate
- Strong polynomiality of the Gass-Saaty shadow-vertex pivoting rule for controlled random walks
- The complexity of the simplex method
- A New Complexity Result on Solving the Markov Decision Problem
Cites work
- scientific article; zbMATH DE number 3152615 (Why is no real title available?)
- A New Complexity Result on Solving the Markov Decision Problem
- A subexponential lower bound for Zadeh's pivoting rule for solving linear programs and games
- Discounted deterministic Markov decision processes and discounted all-pairs shortest paths
- Exponential lower bounds for policy iteration
- Linear programming and sequential decisions
- Lower bounds for Howard's algorithm for finding minimum mean-cost cycles
- 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
- The Complexity of Markov Decision Processes
- The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate
Cited in
(18)- Worst-case analysis of restarted primal-dual hybrid gradient on totally unimodular linear programs
- Maximal acyclic subgraphs and closest stable matrices
- Dantzig's pivoting rule for shortest paths, deterministic MDPs, and minimum cost to time ratio cycles
- The simplex method is strongly polynomial for deterministic Markov decision processes
- Complexity bounds for approximately solving discounted MDPs by value iterations
- A friendly smoothed analysis of the simplex method
- The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate
- The simplex method using Tardos' basic algorithm is strongly polynomial for totally unimodular LP under nondegeneracy assumption
- Reward machines: exploiting reward function structure in reinforcement learning
- The complexity of the simplex method
- Modified policy iteration algorithms are not strongly polynomial for discounted dynamic programming
- Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods
- Strong polynomiality of the Gass-Saaty shadow-vertex pivoting rule for controlled random walks
- Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor
- A New Complexity Result on Solving the Markov Decision Problem
- scientific article; zbMATH DE number 7626790 (Why is no real title available?)
- The greedy strategy for optimizing the Perron eigenvalue
- Improved bound on the worst case complexity of policy iteration
This page was built for publication: The simplex method is strongly polynomial for deterministic Markov decision processes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3465936)
