mlsanityData to 14 Oct 2026

Polylogarithmic Nash Regret in Matrix Games with Bandit Feedback

arXiv 2609.34812 ↗First posted 28 Sep 2026cs.LG cs.GTcited by 0

Not on the map. Why?

Abstract (arXiv)

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 O(log2 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×2 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.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 15 of its 28 references that are in the map. First posted on arXiv 28 Sep 2026.

Builds on

15 of 28 references.

References · 15

  1. 2018Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Banditscited by 124
  2. 2015Explore no more: Improved high-probability regret bounds for non-stochastic banditscited by 120
  3. 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 30
  4. 2020Matrix games with bandit feedbackcited by 16
  5. 2025Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedbackcited by 10
  6. 2023On the Limitations and Possibilities of Nash Regret Minimization in Zero-Sum Matrix Games under Noisy Feedbackcited by 8
  7. 2025From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applicationscited by 8
  8. 2024Uncoupled and Convergent Learning in Monotone Games under Bandit Feedbackcited by 6
  9. 2024Decentralized Best-Response-Based Learning in Two-Player Zero-Sum Stochastic Games: A Finite-Sample Analysiscited by 6
  10. 2026Optimal last-iterate convergence in matrix games with bandit feedback using the log-barriercited by 5
  11. 2026The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedbackcited by 5
  12. 2026Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regretcited by 4
3 more
  1. 2026Efficient Uncoupled Learning Dynamics with tildeO!left(T-1/4right) Last-Iterate Convergence in Bilinear Saddle-Point Problems over Convex Sets under Bandit Feedbackcited by 4
  2. 2026Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actionscited by 4
  3. 2024Finite-Sample Guarantees for Learning Dynamics in Zero-Sum Polymatrix Gamescited by 2

Built on by

Not cited yet.