mlsanityData to 14 Oct 2026

Thompson Sampling for Learning in Zero-Sum Games

arXiv 2610.18899 ↗First posted 11 Oct 2026cs.GT stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

Thompson sampling (TS) achieves logarithmic and asymptotically optimal regret in classical stochastic bandits, but its behavior in multi-agent learning remains less understood. We study TS in an unknown finite two-player zero-sum matrix game with Gaussian bandit feedback. Under centralized self-play, TS samples a single payoff matrix from the posterior and plays a Nash equilibrium of the sampled game. For every fixed zero-sum game with a unique Nash equilibrium, we show that the expected cumulative duality gap is O(√ T). The rate improves to O(log T) for pure equilibria. We then identify the exact coefficient of the √ T term, which depends only on the equilibrium strategies and the noise level. We also establish a minimax lower bound matching the square-root dependence on T and an instance-dependent lower bound matching the logarithmic dependence on T for a class of games with a unique pure equilibrium. Experiments support the predicted rates and coefficient.

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

Builds on

24 of 32 references.

References · 24

  1. 2017A Tutorial on Thompson Samplingcited by 433
  2. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 286
  3. 2013Learning to Optimize Via Posterior Samplingcited by 256
  4. 2015Parallelizing the dual revised simplex methodcited by 89
  5. 2013Thompson Sampling for 1-Dimensional Exponential Family Banditscited by 42
  6. 2020Matrix games with bandit feedbackcited by 16
  7. 2022A Self-Play Posterior Sampling Algorithm for Zero-Sum Markov Gamescited by 16
  8. 2025Achieving Logarithmic Regret in KL-Regularized Zero-Sum Markov Gamescited by 15
  9. 2023Doubly Optimal No-Regret Learning in Monotone Gamescited by 14
  10. 2025Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedbackcited by 10
  11. 2023On the Limitations and Possibilities of Nash Regret Minimization in Zero-Sum Matrix Games under Noisy Feedbackcited by 8
  12. 2021Variational Bayesian Optimistic Samplingcited by 7
12 more
  1. 2023Instance-dependent Sample Complexity Bounds for Zero-sum Matrix Gamescited by 7
  2. 2023Near-Optimal Pure Exploration in Matrix Games: A Generalization of Stochastic Bandits & Dueling Banditscited by 7
  3. 2026Optimal last-iterate convergence in matrix games with bandit feedback using the log-barriercited by 5
  4. 2026The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedbackcited by 5
  5. 2021A Bayesian Learning Algorithm for Unknown Zero-sum Stochastic Games with an Arbitrary Opponentcited by 4
  6. 2026Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regretcited by 4
  7. 2026Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actionscited by 4
  8. 2023Posterior Sampling for Competitive RL: Function Approximation and Partial Observationcited by 3
  9. 2023Minimally Modifying a Markov Game to Achieve Any Nash Equilibrium and Valuecited by 3
  10. 2025Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Gamescited by 3
  11. 2026Bayesian Learning in Episodic Zero-Sum Gamescited by 1
  12. 2026Policy Optimization and Statistical Inference for Online Contextual Matrix Gamescited by 1

Built on by

Not cited yet.