A complexity analysis of Policy Iteration through combinatorial matrices arising from Unique Sink Orientations
  • Metaadatok
Tartalom: http://real.mtak.hu/73744/
Archívum: MTA Könyvtár
Gyűjtemény: Status = Published

Type = Article
Cím:
A complexity analysis of Policy Iteration through combinatorial matrices arising from Unique Sink Orientations
Létrehozó:
Gerencsér, Balázs
Hollanders, R.
Delvenne, J-C.
Jungers, Raphaël M.
Dátum:
2017
Téma:
QA Mathematics / matematika
Tartalmi leírás:
Unique Sink Orientations (USOs) are an appealing abstraction of several major optimization problems of applied mathematics such as 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 the case of an acyclic USO of a cube, a situation that captures both MDPs and 2TBSGs, one can apply the well-known Policy Iteration (PI) algorithm. 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. In 2012, Hansen and Zwick introduced a new combinatorial relaxation of the complexity problem for PI resulting in what we call Order-Regular (OR) matrices. They conjectured that the maximum number of rows of such matrices—an upper bound on the number of steps of PI—should follow the Fibonacci sequence. As our first contribution, we disprove the lower bound part of Hansen and Zwick's conjecture. Then, for our second contribution, we (exponentially) improve the Ω(1.4142n) lower bound on the number of steps of PI from Schurr and Szabó in the case of OR matrices and obtain an Ω(1.4269n) bound. © 2017 Elsevier B.V.
Nyelv:
angol
Típus:
Article
PeerReviewed
info:eu-repo/semantics/article
Formátum:
text
Azonosító:
Gerencsér, Balázs and Hollanders, R. and Delvenne, J-C. and Jungers, Raphaël M. (2017) A complexity analysis of Policy Iteration through combinatorial matrices arising from Unique Sink Orientations. JOURNAL OF DISCRETE ALGORITHMS, 44. pp. 21-38. ISSN 1570-8667
Kapcsolat:
https://doi.org/10.1016/j.jda.2017.04.004
MTMT:3251093; doi:10.1016/j.jda.2017.04.004