Instance-dependent sample complexity for zero-sum matrix games

To find a near-equilibrium of a two-player zero-sum game whose payoffs can only be sampled with noise, a generic method needs about $n/\varepsilon^2$ samples, whatever the game. For bandits we know, up to small factors, which instances are easy and how many samples each one needs. What is the analogous instance-by-instance answer for matrix games?

Problem

A payoff matrix $A \in \mathbb{R}^{n \times m}$ defines a zero-sum game: the row player picks a row $i$, the column player a column $j$, and the row player receives $A_{ij}$ while the column player receives $-A_{ij}$. Let $\mathcal{P}_k$ be the set of probability vectors in $\mathbb{R}^k$. A pair $(x^\star, y^\star) \in \mathcal{P}_n \times \mathcal{P}_m$ is an $\varepsilon$-approximate Nash equilibrium if, for all $x \in \mathcal{P}_n$ and $y \in \mathcal{P}_m$,

$$\langle x, A y^\star \rangle \le \langle x^\star, A y^\star \rangle + \varepsilon \quad\text{and}\quad \langle x^\star, A y \rangle \ge \langle x^\star, A y^\star \rangle - \varepsilon .$$

The matrix is unknown. Each sample picks an entry $(i, j)$ and returns $A_{ij} + \eta$, where $\eta$ is fresh zero-mean 1-subgaussian noise. The goal is to output an $\varepsilon$-approximate Nash equilibrium with probability at least $1 - \delta$ from as few samples as possible.

Question. Find functions $H_1(A, \varepsilon)$ and $H_2(A, \varepsilon)$ of the instance such that the optimal number of samples is $\Theta\big(H_1 \log(1/\delta) + H_2\big)$, possibly up to logarithmic factors, with an algorithm achieving it and a matching lower bound. Which parameters of $A$ make a game easy?

Background

Letting both players run a no-regret bandit algorithm such as EXP3-IX finds an $\varepsilon$-approximate equilibrium with $O(n \log(n/\delta)/\varepsilon^2)$ samples. This is nearly minimax optimal even for the special case of a multi-armed bandit, but in bandits instance-dependent bounds do much better: an $\varepsilon$-best of $K$ arms with means $\mu_1 \ge \dots \ge \mu_K$ can be found with $O\big(\sum_{i \ge 2} \Delta_i^{-2} \log(1/\delta)\big) + \widetilde O\big(\sum_{i \ge 2} \Delta_i^{-2}\big)$ samples, where $\Delta_i = \max\{\varepsilon, \mu_1 - \mu_i\}$. Maiti posed the matrix-game version at COLT 2025 [1], as a step towards sample-efficient learning in multi-agent settings.

What is known

• Pure equilibria. If $A$ has a strict pure equilibrium, every algorithm needs $\Omega(H^\star \log(1/\delta))$ samples, where $H^\star$ sums the inverse squared gaps between the equilibrium entry and the other entries of its row and column (Zhou, Li and Zhu, 2017) [3]. Maiti, Boczar, Jamieson and Ratliff (2024) matched this up to logarithmic factors [4].
• Games with $n \times 2$ payoff matrices. For such games with a unique equilibrium, the gap $\Delta_g = \min_{i \notin \mathrm{supp}(x^\star)} \langle x^\star - e_i, A y^\star \rangle$, suitably rescaled, governs the difficulty. There is an upper bound of order $1/\varepsilon^2 + n/\Delta_g^2$ and, for $3 \times 2$ games, a lower bound $\Omega(1/\Delta_g^2)$ (Maiti, Jamieson and Ratliff, 2023) [2].
• Unique equilibria in general. With a unique equilibrium, the two supports have the same size $k$, and every action outside them is worse by a strictly positive margin (Bohnenblust, Karlin and Shapley, 1950). Without noise, $n \cdot \mathrm{poly}(k)$ queries identify the supports (Maiti et al., 2025); how many noisy samples this takes is open [1].
• General games. A 2026 algorithm that repeatedly solves linear programs finds an estimate of an equilibrium, within $\varepsilon$, from $O\big(\tfrac{m_1 m_2}{\varepsilon \gamma} \log \tfrac{m_1 m_2}{\varepsilon}\big)$ samples on $m_1 \times m_2$ games, where $\gamma > 0$ is an instance-dependent constant; no matching lower bound is known [5].

What would count as progress

• For games with a unique equilibrium, an algorithm whose sample complexity is governed by the margins of the actions outside the supports, with a proof, together with a lower bound of the same form.
• Instance-dependent lower bounds for $n \times m$ games beyond the $3 \times 2$ case, for example by change-of-measure arguments.
• For strict pure equilibria, uncoupled no-regret learners that reach the optimal $\widetilde O(H^\star \log(1/\delta))$ sample complexity, or a proof that they cannot.

References

1. A. Maiti, Open problem: Optimal instance-dependent sample complexity for finding Nash equilibrium in two player zero-sum matrix games, COLT 2025, PMLR 291 (2025), 6230–6234. PMLR
2. A. Maiti, K. Jamieson and L. Ratliff, Instance-dependent sample complexity bounds for zero-sum matrix games, AISTATS 2023, PMLR 206 (2023), 9429–9469. PMLR
3. Y. Zhou, J. Li and J. Zhu, Identify the Nash equilibrium in static games with random payoffs, ICML 2017, PMLR 70 (2017), 4160–4169. PMLR
4. A. Maiti, R. Boczar, K. Jamieson and L. Ratliff, Near-optimal pure exploration in matrix games: a generalization of stochastic bandits and dueling bandits, AISTATS 2024, PMLR 238 (2024), 2602–2610. PMLR
5. J. Jiang and M. Zhang, An LP-based approach for bilinear saddle point problem with instance-dependent guarantee and noisy feedback, preprint (2026). arXiv:2602.12513

Source

Imported from COLT open problems, COLT 2025, curated by the Conference on Learning Theory (COLT). Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.