mlsanityData to 14 Oct 2026

Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback

arXiv 2502.17625 ↗First posted 24 Feb 2025cs.LG cs.GTcited by 10

Not on the map. Why?

Abstract (arXiv)

No-regret self-play learning dynamics have become one of the premier ways to solve large-scale games in practice. Accelerating their convergence via improving the regret of the players over the naive O(√T) bound after T rounds has been extensively studied in recent years, but almost all studies assume access to exact gradient feedback. We address the question of whether acceleration is possible under bandit feedback only and provide an affirmative answer for two-player zero-sum normal-form games. Specifically, we show that if both players apply the Tsallis-INF algorithm of Zimmert and Seldin (2018, arXiv:1807.07623), then their regret is at most O(c1 log T + √c2 T), where c1 and c2 are game-dependent constants that characterize the difficulty of learning -- c1 resembles the complexity of learning a stochastic multi-armed bandit instance and depends inversely on some gap measures, while c2 can be much smaller than the number of actions when the Nash equilibria have a small support or are close to the boundary. In particular, for the case when a pure strategy Nash equilibrium exists, c2 becomes zero, leading to an optimal instance-dependent regret bound as we show. We additionally prove that in this case, our algorithm also enjoys last-iterate convergence and can identify the pure strategy Nash equilibrium with near-optimal sample complexity.

Key facts. Cited by 10 papers in the map (data through 14 Oct 2026). Builds on 37 of its 67 references that are in the map. First posted on arXiv 24 Feb 2025.

Builds on

37 of 67 references.

References · 37

  1. 2017DeepStack: Expert-Level Artificial Intelligence in No-Limit Pokercited by 233
  2. 2023Nash Learning from Human Feedbackcited by 224
  3. 2013Optimization, Learning, and Games with Predictable Sequencescited by 188
  4. 2015Fast Convergence of Regularized Learning in Gamescited by 150
  5. 2022Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learningcited by 131
  6. 2018Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Banditscited by 124
  7. 2018More Adaptive Algorithms for Adversarial Banditscited by 114
  8. 2015Contextual Dueling Banditscited by 101
  9. 2018Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimizationcited by 98
  10. 2021Near-Optimal No-Regret Learning in General Gamescited by 85
  11. 2016Learning in games with continuous action sets and unknown payoff functionscited by 81
  12. 2014Reducing Dueling Bandits to Cardinal Banditscited by 62
25 more
  1. 2020Hedging in games: Faster convergence of external and swap regretscited by 57
  2. 2015Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problemcited by 52
  3. 2021Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibriumcited by 51
  4. 2020Tight last-iterate convergence rates for no-regret learning in multi-player gamescited by 49
  5. 2020Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transitioncited by 48
  6. 2021Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Gamescited by 43
  7. 2021The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitioncited by 40
  8. 2023The Consensus Game: Language Model Generation via Equilibrium Searchcited by 36
  9. 2022Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Gamescited by 35
  10. 2022Last-Iterate Convergence of Optimistic Gradient Method for Monotone Variational Inequalitiescited by 33
  11. 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 30
  12. 2022Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphscited by 26
  13. 2022Near-Optimal No-Regret Learning Dynamics for General Convex Gamescited by 25
  14. 2022A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedbackcited by 23
  15. 2022Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusioncited by 20
  16. 2021An Algorithm for Stochastic and Adversarial Bandits with Switching Costscited by 19
  17. 2022Best-of-Both-Worlds Algorithms for Partial Monitoringcited by 19
  18. 2023Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits: FTRL with General Regularizers and Multiple Optimal Armscited by 18
  19. 2020Matrix games with bandit feedbackcited by 16
  20. 2024Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithmscited by 14
  21. 2022Better Best of Both Worlds Bounds for Bandits with Switching Costscited by 13
  22. 2023No-Regret Online Reinforcement Learning with Adversarial Losses and Transitionscited by 13
  23. 2023On the Limitations and Possibilities of Nash Regret Minimization in Zero-Sum Matrix Games under Noisy Feedbackcited by 8
  24. 2023Instance-dependent Sample Complexity Bounds for Zero-sum Matrix Gamescited by 7
  25. 2023Near-Optimal Pure Exploration in Matrix Games: A Generalization of Stochastic Bandits & Dueling Banditscited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 3; 2026: 7.

10 papers.

  1. 2026Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferencescited by 5
  2. 2026Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regretcited by 4
  3. 2026Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actionscited by 4
  4. 2025Tight Regret Upper and Lower Bounds for Optimistic Hedge in Two-Player Zero-Sum Gamescited by 2
  5. 2025Two-Player Zero-Sum Games with Bandit Feedbackcited by 1
  6. 2025Last-Iterate Analyses of FTRL with the 1/2-Tsallis Entropy in Stochastic Banditscited by 1
  7. 2026Minimax Last-Iterate Convergence in Matrix Games with Observed Actionscited by 1
  8. 2026Fairness in two-player zero-sum games with bandit feedbackcited by 0
  9. 2026Polylogarithmic Nash Regret in Matrix Games with Bandit Feedbackcited by 0
  10. 2026Thompson Sampling for Learning in Zero-Sum Gamescited by 0