A complexity analysis of policy iteration through combinatorial matrices arising from unique sink orientations
From MaRDI portal
(Redirected from Publication:2363352)
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20)
Abstract: Unique Sink Orientations (USOs) are an appealing abstraction of several major optimization problems of applied mathematics such as for instance Linear Programming (LP), Markov Decision Processes (MDPs) or 2-player Turn Based Stochastic Games (2TBSGs). A polynomial time algorithm to find the sink of a USO would translate into a strongly polynomial time algorithm to solve the aforementioned problems---a major quest for all three cases. In addition, we may translate MDPs and 2TBSGs into the problem of finding the sink of an acyclic USO of a cube, which can be done using the well-known Policy Iteration algorithm (PI). The study of its complexity is the object of this work. Despite its exponential worst case complexity, the principle of PI is a powerful source of inspiration for other methods. As our first contribution, we disprove Hansen and Zwick's conjecture claiming that the number of steps of PI should follow the Fibonacci sequence in the worst case. Our analysis relies on a new combinatorial formulation of the problem---the so-called Order-Regularity formulation (OR). Then, for our second contribution, we (exponentially) improve the lower bound on the number of steps of PI from Schurr and Szab'o in the case of the OR formulation and obtain an bound.
Recommendations
Cites work
- scientific article; zbMATH DE number 3148886 (Why is no real title available?)
- scientific article; zbMATH DE number 3614497 (Why is no real title available?)
- scientific article; zbMATH DE number 1775049 (Why is no real title available?)
- A new polynomial-time algorithm for linear programming
- A subexponential randomized algorithm for the simple stochastic game problem
- Algorithms for discounted stochastic games
- Digraph Models of Bard-Type Algorithms for the Linear Complementarity Problem
- Exponential lower bounds for policy iteration
- Improved bound on the worst case complexity of policy iteration
- Improved upper bounds for Random-Edge and Random-Jump on abstract cubes
- Jumping Doesn’t Help in Abstract Cubes
- Linear programming and unique sink orientations
- Lower bounds for a subexponential optimization algorithm
- Polynomial algorithms in linear programming
- Randomized pivot algorithms for \(P\)-matrix linear complementarity problems
- Randomized simplex algorithms on Klee-Minty cubes
- Solving H-horizon, stationary Markov decision problems in time proportional to log (H)
- Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor
- The Linear Complementarity Problem
- The Random‐Facet simplex algorithm on combinatorial cubes
- The complexity of stochastic games
- The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate
- The simplex method is strongly polynomial for deterministic Markov decision processes
- Unique Sink Orientations of Grids
This page was built for publication: A complexity analysis of policy iteration through combinatorial matrices arising from unique sink orientations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2363352)
