Metraipolis › archive › dc_d0fb944db1f2

On the Convergence of Alternating Regret Matching Algorithms — arXiv:2611.02521

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.02521
License (as archived)
CC0-1.0
Archived
2026-11-03T11:15:29.490Z
SHA-256 of the archived text
c2e1aca9113140474bbd89a114de0c07408b976619ba4635945f1e79179c01a2
Stable URL of this page
https://metraipolis.com/documento/dc_d0fb944db1f2

How to cite

On the Convergence of Alternating Regret Matching Algorithms — arXiv:2611.02521 — arXiv (en), https://arxiv.org/abs/2611.02521 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d0fb944db1f2 (Metraipolis archive dc_d0fb944db1f2, sha256 c2e1aca9113140474bbd89a114de0c07408b976619ba4635945f1e79179c01a2)
BibTeX
@misc{dcd0fb944db1f2,
  title = {On the Convergence of Alternating Regret Matching Algorithms — arXiv:2611.02521},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.02521},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d0fb944db1f2; sha256 c2e1aca9113140474bbd89a114de0c07408b976619ba4635945f1e79179c01a2},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.02521. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: economia dei servizi IA (elenco arXiv cs.GT, nuovi lavori del giorno).
Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2611.02521 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T11:01:07.155Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).