# Instance-dependent Sample Complexity Bounds for Zero-sum Matrix Games

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 26 references that are in the map.
- First posted on arXiv 19 Mar 2023.

## Builds on (most cited first, 7 of 7)

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Bandit learning in concave N-person games](https://mlsanity.com/paper/1810.01925/) (2018)
- [Matrix games with bandit feedback](https://mlsanity.com/paper/2006.05145/) (2020)
- [Learning in Congestion Games with Bandit Feedback](https://mlsanity.com/paper/2206.01880/) (2022)
- [Gap-Dependent Bounds for Two-Player Markov Games](https://mlsanity.com/paper/2107.00685/) (2021)

## Built on by (most cited first, 7 of 7)

- [Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback](https://mlsanity.com/paper/2502.17625/) (2025)
- [Near-Optimal Pure Exploration in Matrix Games: A Generalization of Stochastic Bandits & Dueling Bandits](https://mlsanity.com/paper/2310.16252/) (2023)
- [Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regret](https://mlsanity.com/paper/2602.06348/) (2026)
- [Pure Exploration with Infinite Answers](https://mlsanity.com/paper/2505.22473/) (2025)
- [Two-Player Zero-Sum Games with Bandit Feedback](https://mlsanity.com/paper/2506.14518/) (2025)
- [Fairness in two-player zero-sum games with bandit feedback](https://mlsanity.com/paper/2606.01159/) (2026)
- [Thompson Sampling for Learning in Zero-Sum Games](https://mlsanity.com/paper/2610.18899/) (2026)

## Abstract (arXiv)

We study the sample complexity of identifying an approximate equilibrium for two-player zero-sum n× 2 matrix games. That is, in a sequence of repeated game plays, how many rounds must the two players play before reaching an approximate equilibrium (e.g., Nash)? We derive instance-dependent bounds that define an ordering over game matrices that captures the intuition that the dynamics of some games converge faster than others. Specifically, we consider a stochastic observation model such that when the two players choose actions i and j, respectively, they both observe each other's played actions and a stochastic observation Xij such that mathbb E[ Xij] = Aij. To our knowledge, our work is the first case of instance-dependent lower bounds on the number of rounds the players must play before reaching an approximate equilibrium in the sense that the number of rounds depends on the specific properties of the game matrix A as well as the desired accuracy. We also prove a converse statement: there exist player strategies that achieve this lower bound.