Improved Bounds for Strategy Improvement Algorithms for Energy Games

Strategy improvement is a natural and well-studied family of algorithms for solving various classes of stochastic and deterministic graph games. We present an improved upper bound of O(n 2ⁿ) on the number of iterations performed by the most natural, and most greedy, variant of the algorithm when applied to n-vertex Energy Games. We also obtain a similar upper bound of O(poly(n)⋅ 2ⁿ) on the expected number of iterations performed by Random-Edge, one of the most natural randomized variants of the algorithm. To the best of our knowledge, these are the first bounds for natural strategy-improvement algorithms on non-binary energy games that beat the trivial nⁿ = 2^{n log n} bound obtained by enumerating all strategies. The proof is based on a new adaptation of the layering technique of [Dorfman, Kaplan, Zwick, ICALP 2019].