Alternating updates speed up regret matching convergence in game solving
On the Convergence of Alternating Regret Matching Algorithms
Computer Science and Game TheoryMachine Learning
Summary
In algorithms that help players learn the best moves in zero-sum games, updating one player at a time usually works better than updating both at once. The authors develop a new way to analyze these alternating updates, showing they get closer to a perfect strategy twice as fast on average compared to previous methods. They introduce a new predictive rule called half-prediction, which they prove is uniquely effective for these alternating methods. Their results also show these updates lead to stable final strategies, even when the best response isn't unique. Tests on various games show their approach performs as well as current top solvers.
What this means in practice
- •For game ai developers: Integrate alternating regret matching methods to improve convergence speed and stability in game-playing AI training.
- •For multiagent system engineers: Apply half-prediction alternating updates to stabilize learning processes in multiagent competitive scenarios.
Authors
Anh Duc Nguyen, Ioannis Anagnostides, Brian Hu Zhang, Tuomas Sandholm
Abstract
Alternating updates, that is, where each player is updated in turn, tend to typically perform better in regret matching algorithms than simultaneous updates. Alternation within the regret matching family has long been a central ingredient of practical solvers for zero-sum games. Yet our theoretical understanding is lagging behind. In this paper, we address this gap by developing a systematic way of analyzing such algorithms. Our framework centers on an alternating analog of the RVU property that we introduce, which we use to obtain the optimal $T^{-1}$ average-iterate convergence within this family. In particular, we establish this for two simple variants of predictive regret matching$^+$: i) increasing-regret predictive regret matching$^+$ and ii) half-prediction regret matching$^+$. Interestingly, we find that half prediction is the unique prediction multiplier that satisfies our alternating RVU property, giving it a strong theoretical justification. Going beyond average-iterate convergence, we refine our framework to obtain $T^{-1/2}$ best-iterate convergence and further establish convergence of their strategy profiles to a single Nash equilibrium, without assuming equilibrium uniqueness. We go on to establish separations between alternating and simultaneous updates, including a game in which half-prediction regret matching$^+$ converges under alternating updates but fails to converge in terms of the last iterate under simultaneous updates. This provides theoretical support for the empirical observation that alternation can stabilize learning dynamics. Finally, experiments on 15 game benchmarks demonstrate that the strong theoretical properties of the half-prediction mechanism translate to strong practical performance, being on par with state-of-the-art solvers.