Thompson Sampling for Learning in Zero-Sum Games

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(sqrt T). The rate improves to O(T) for pure equilibria. We then identify the exact coefficient of the sqrt 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.