A complexity analysis of Policy Iteration through combinatorial matrices arising from Unique Sink Orientations

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.