A complexity analysis of policy iteration through combinatorial matrices arising from unique sink orientations

DOI10.1016/J.JDA.2017.04.004zbMATH Open1370.68126arXiv1407.4293OpenAlexW2962676361WikidataQ115041711 ScholiaQ115041711MaRDI QIDQ2363352FDOQ2363352

Authors: Balázs Gerencsér, Romain Hollanders, Jean-Charles Delvenne, Raphaël M. Jungers 

Publication date: 13 July 2017

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

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 $Omega(1.4142^n)$ lower bound on the number of steps of PI from Schurr and Szab'o in the case of the OR formulation and obtain an $Omega(1.4269^n)$ bound.

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

Recommendations

• Improved and generalized upper bounds on the complexity of policy iteration
• Improved bound on the worst case complexity of policy iteration
• Counting unique-sink orientations
• Unique sink orientations of grids
• Mathematical Foundations of Computer Science 2004

zbMATH Keywords

policy iterationcomplexity boundscombinatorial matricesunique sink orientations

Mathematics Subject Classification ID

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)

Cites Work

• The complexity of stochastic games
• Solving H-horizon, stationary Markov decision problems in time proportional to log (H)
• Title not available (Why is that?)
• A new polynomial-time algorithm for linear programming
• The Linear Complementarity Problem
• Polynomial algorithms in linear programming
• Digraph Models of Bard-Type Algorithms for the Linear Complementarity Problem
• A subexponential randomized algorithm for the simple stochastic game problem
• The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate
• Algorithms for discounted stochastic games
• Lower bounds for a subexponential optimization algorithm
• Randomized pivot algorithms for \(P\)-matrix linear complementarity problems
• Linear programming and unique sink orientations
• The Random‐Facet simplex algorithm on combinatorial cubes
• Title not available (Why is that?)
• Randomized simplex algorithms on Klee-Minty cubes
• Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor
• Jumping Doesn’t Help in Abstract Cubes
• Unique Sink Orientations of Grids
• Improved bound on the worst case complexity of policy iteration
• Exponential lower bounds for policy iteration
• Improved upper bounds for Random-Edge and Random-Jump on abstract cubes
• Title not available (Why is that?)
• The simplex method is strongly polynomial for deterministic Markov decision processes

Cited In (1)

• Improved bound on the worst case complexity of policy iteration

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)