Summary
Some games used in computer science rely on strategies that can be hard to solve quickly using traditional methods. The researchers improved the understanding of two common algorithms, policy iteration and value iteration, showing they run efficiently on any type of game graph when randomness slightly perturbs the game. They introduced new mathematical tools and methods that guarantee fast performance in most cases, even when previous assumptions about the game's structure do not hold. Additionally, they developed three new algorithms to solve certain games faster and proved these algorithms work well on such perturbed games.
What this means in practice
- •For algorithm engineers: Use the new smoothed polynomial-time guarantees to optimize policy and value iteration in game-solving tools for deterministic games on any graph.
- •For game theoreticians: Incorporate the improved algorithms and analysis to handle a wider class of game graphs efficiently without relying on ergodicity assumptions.
Abstract
Our understanding of turn-based stochastic games is reminiscent of our understanding of linear programming in the 1970s. Instead of the simplex method, we have two families of algorithms - policy iteration and value iteration - which work well in practice but are known to run in exponential time on some input instances, and we still lack an algorithm that runs in polynomial time on all instances. A recent result by Loff and Skomra showed that, for deterministic discounted and mean-payoff games played on an ergodic graph, a variant of policy iteration runs in smoothed polynomial time. This offered an explanation of why policy iteration performs well in practice, analogous to Spielman and Teng's explanation for the simplex method. In this paper, we drop the ergodicity assumption: we show that their policy iteration algorithms run in smoothed polynomial time for any game graph. We do this by defining a condition number that naturally generalizes theirs, showing that sufficiently-perturbed games are well-conditioned with high probability, and showing that their algorithms are efficient on well-conditioned instances. Although the outline is similar, our proof requires a substantially new approach, based on log-Lipschitz distributions which recently appeared in work on the smoothed analysis of the simplex method. For our second contribution, we propose three new value iteration algorithms for solving deterministic mean-payoff games (also on any graph). All three are based on iterative methods for finding fixed points of non-expansive operators, which we show can be applied to the Shapley operator. The first two are simple applications of Krasnoselskii-Mann iteration and Halpern iteration. The third is quadratically faster but more complicated: it runs Zwick-Paterson and Halpern iterations in parallel. We prove that all three algorithms are correct and run in smoothed polynomial time.