Metraipolis › archive › dc_f39bcd30a1eb
Polylogarithmic Nash Regret in Matrix Games with Bandit Feedback — arXiv:2609.34812
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.34812
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T22:14:12.387Z
- SHA-256 of the archived text
1d6b0c058af909b25d6143e93f563a98aaf999eafae22ccc0fdef02427db8526- Stable URL of this page
https://metraipolis.com/documento/dc_f39bcd30a1eb
How to cite
Polylogarithmic Nash Regret in Matrix Games with Bandit Feedback — arXiv:2609.34812 — arXiv (en), https://arxiv.org/abs/2609.34812 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f39bcd30a1eb (Metraipolis archive dc_f39bcd30a1eb, sha256 1d6b0c058af909b25d6143e93f563a98aaf999eafae22ccc0fdef02427db8526)
BibTeX
@misc{dcf39bcd30a1eb,
title = {Polylogarithmic Nash Regret in Matrix Games with Bandit Feedback — arXiv:2609.34812},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.34812},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f39bcd30a1eb; sha256 1d6b0c058af909b25d6143e93f563a98aaf999eafae22ccc0fdef02427db8526},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.34812. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study Nash regret minimization in unknown finite matrix games with bandit payoff feedback and observed opponent actions. We develop Optimistic Payoff Balancing (OPB), which achieves instance-dependent $\mathcal{O}(\log^2 T)$ Nash regret against arbitrary adaptive opponents, including games with nonunique equilibria. This resolves the open problem posed by Maiti et al. (2025), extending their polylogarithmic guarantee under bandit feedback from $2\times2$ games to arbitrary finite dimensions. To handle nonunique equilibria, we construct a reference strategy that leaves room for local adjustments. We order independent payoff differences by estimation accuracy and scale these adjustments by uncertainty, allowing the learner to exploit the opponent's imbalance to offset estimation costs. Our result thus shows that observing opponent actions suffices for polylogarithmic Nash regret in general finite matrix games.
Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-29 in cs.GT).
Categorie arXiv: Machine Learning (cs.LG) ; Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2609.34812 — 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-07T21:55:21.874Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).