# Thompson Sampling for Learning in Zero-Sum Games

arXiv: https://arxiv.org/abs/2610.18899 · HTML: https://mlsanity.com/paper/2610.18899/

## 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 (most cited first, 24 of 24)

- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Parallelizing the dual revised simplex method](https://mlsanity.com/paper/1503.01889/) (2015)
- [Thompson Sampling for 1-Dimensional Exponential Family Bandits](https://mlsanity.com/paper/1307.3400/) (2013)
- [Matrix games with bandit feedback](https://mlsanity.com/paper/2006.05145/) (2020)
- [A Self-Play Posterior Sampling Algorithm for Zero-Sum Markov Games](https://mlsanity.com/paper/2210.01907/) (2022)
- [Achieving Logarithmic Regret in KL-Regularized Zero-Sum Markov Games](https://mlsanity.com/paper/2510.13060/) (2025)
- [Doubly Optimal No-Regret Learning in Monotone Games](https://mlsanity.com/paper/2301.13120/) (2023)
- [Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback](https://mlsanity.com/paper/2502.17625/) (2025)
- [On the Limitations and Possibilities of Nash Regret Minimization in Zero-Sum Matrix Games under Noisy Feedback](https://mlsanity.com/paper/2306.13233/) (2023)
- [Variational Bayesian Optimistic Sampling](https://mlsanity.com/paper/2110.15688/) (2021)
- [Instance-dependent Sample Complexity Bounds for Zero-sum Matrix Games](https://mlsanity.com/paper/2303.10565/) (2023)
- [Near-Optimal Pure Exploration in Matrix Games: A Generalization of Stochastic Bandits & Dueling Bandits](https://mlsanity.com/paper/2310.16252/) (2023)
- [Optimal last-iterate convergence in matrix games with bandit feedback using the log-barrier](https://mlsanity.com/paper/2604.15242/) (2026)
- [The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback](https://mlsanity.com/paper/2604.16087/) (2026)
- [A Bayesian Learning Algorithm for Unknown Zero-sum Stochastic Games with an Arbitrary Opponent](https://mlsanity.com/paper/2109.03396/) (2021)
- [Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regret](https://mlsanity.com/paper/2602.06348/) (2026)
- [Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions](https://mlsanity.com/paper/2605.09363/) (2026)
- [Posterior Sampling for Competitive RL: Function Approximation and Partial Observation](https://mlsanity.com/paper/2310.19861/) (2023)
- [Minimally Modifying a Markov Game to Achieve Any Nash Equilibrium and Value](https://mlsanity.com/paper/2311.00582/) (2023)
- [Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games](https://mlsanity.com/paper/2502.09780/) (2025)
- [Bayesian Learning in Episodic Zero-Sum Games](https://mlsanity.com/paper/2603.20604/) (2026)
- [Policy Optimization and Statistical Inference for Online Contextual Matrix Games](https://mlsanity.com/paper/2608.17173/) (2026)

## 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.