Thompson Sampling for Learning in Zero-Sum Games
Abstract
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.
Related
- When May a Bandit Leave Its Anchor? E-Process-Authorized Thompson Sampling under Non-stationarity
- High-Probability Regret Bounds for Feel-Good Thompson Sampling
- Convergence Rates of Gaussian Process Thompson Sampling for Efficient Global Optimization
- Posterior Tempering Explains Variance Inflation in Linear and Generalized Linear Thompson Sampling
- Structure, Not Belief: Correlated Thompson Sampling from LLM-Derived Covariance in Combinatorial Semi-Bandits
BibTeX
@misc{abe2026thompson,
title = {{Thompson Sampling for Learning in Zero-Sum Games}},
author = {Kenshi Abe and Kaito Ariu and Po-An Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.18899},
eprint = {2610.18899},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.18899},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Thompson Sampling for Learning in Zero-Sum Games
AU - Kenshi Abe
AU - Kaito Ariu
AU - Po-An Wang
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2610.18899
UR - https://arxiv.org/abs/2610.18899
AB - 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.
ER -