Metraipolis › archive › dc_dabc68f74f50

Constant Swap Regret in General-Sum Games via Two-Scale Higher-Order Optimism — arXiv:2609.16751

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.16751
License (as archived)
CC0-1.0
Archived
2026-10-15T19:31:06.077Z
SHA-256 of the archived text
ecaf6fb54c02f7c65636fe9250caf6bc5b3d64f76256b8fdbb88352a99369248
Stable URL of this page
https://metraipolis.com/documento/dc_dabc68f74f50

How to cite

Constant Swap Regret in General-Sum Games via Two-Scale Higher-Order Optimism — arXiv:2609.16751 — arXiv (en), https://arxiv.org/abs/2609.16751 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_dabc68f74f50 (Metraipolis archive dc_dabc68f74f50, sha256 ecaf6fb54c02f7c65636fe9250caf6bc5b3d64f76256b8fdbb88352a99369248)
BibTeX
@misc{dcdabc68f74f50,
  title = {Constant Swap Regret in General-Sum Games via Two-Scale Higher-Order Optimism — arXiv:2609.16751},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.16751},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_dabc68f74f50; sha256 ecaf6fb54c02f7c65636fe9250caf6bc5b3d64f76256b8fdbb88352a99369248},
  year = {2026}
}

Archived text

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

We give deterministic and uncoupled learning dynamics for finite multiplayer general-sum games under full-information feedback that achieve constant individual swap regret in self-play, independent of the horizon $T$. With $n$ players and at most $m$ actions each, every player's individual swap regret is $O(\sqrt n\,m\log m\log^{5/2}(nm))$ at every finite horizon. The dynamics use the classical Blum-Mansour framework with optimism. Each player predicts the deviation gains, uses these predictions to update a row-stochastic transition matrix, and plays its stationary distribution. Our new ingredients include a tailored row normalization map and a two-scale higher-order predictor. An adversarially robust variant, obtained through a generic common-prefix switching wrapper, preserves the self-play bound up to a universal constant and guarantees individual swap regret at most $7\sqrt{mT\log m}$ in the adversarial setting.

Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-16 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.16751 — 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-10-15T18:39:23.381Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-16?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).