# Towards Characterizing the First-order Query Complexity of Learning (Approximate) Nash Equilibria in Zero-sum Matrix Games

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 43 references that are in the map.
- First posted on arXiv 25 Apr 2023.

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

- [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)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [Scale-Free Online Learning](https://mlsanity.com/paper/1601.01974/) (2016)
- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [The Complexity of Constrained Min-Max Optimization](https://mlsanity.com/paper/2009.09623/) (2020)
- [Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems](https://mlsanity.com/paper/1808.02901/) (2018)
- [Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems](https://mlsanity.com/paper/2002.00057/) (2020)
- [Hedging in games: Faster convergence of external and swap regrets](https://mlsanity.com/paper/2006.04953/) (2020)
- [Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium](https://mlsanity.com/paper/2104.12761/) (2021)
- [The Computational Power of Optimization in Online Learning](https://mlsanity.com/paper/1504.02089/) (2015)
- [On Lower Iteration Complexity Bounds for the Saddle Point Problems](https://mlsanity.com/paper/1912.07481/) (2019)
- [Near-Optimal No-Regret Learning Dynamics for General Convex Games](https://mlsanity.com/paper/2206.08742/) (2022)
- [Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update](https://mlsanity.com/paper/2111.14737/) (2021)
- [Frank-Wolfe Algorithms for Saddle Point Problems](https://mlsanity.com/paper/1610.07797/) (2016)
- [Learning Equilibria of Games via Payoff Queries](https://mlsanity.com/paper/1302.3116/) (2013)
- [Query Complexity of Approximate Nash Equilibria](https://mlsanity.com/paper/1306.6686/) (2013)
- [The Query Complexity of Correlated Equilibria](https://mlsanity.com/paper/1305.4874/) (2013)

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

- [The Oracle Complexity of Simplex-based Matrix Games](https://mlsanity.com/paper/2412.06990/) (2024)
- [Computational Lower Bounds for Regret Minimization in Normal-Form Games](https://mlsanity.com/paper/2411.01721/) (2024)

## Abstract (arXiv)

In the first-order query model for zero-sum K× K matrix games, players observe the expected pay-offs for all their possible actions under the randomized action played by their opponent. This classical model has received renewed interest after the discovery by Rakhlin and Sridharan that ε-approximate Nash equilibria can be computed efficiently from O(fracln Kε) instead of O(fracln Kε2) queries. Surprisingly, the optimal number of such queries, as a function of both ε and K, is not known. We make progress on this question on two fronts. First, we fully characterise the query complexity of learning exact equilibria (ε=0), by showing that they require a number of queries that is linear in K, which means that it is essentially as hard as querying the whole matrix, which can also be done with K queries. Second, for ε > 0, the current query complexity upper bound stands at O(min(fracln(K)ε , K)). We argue that, unfortunately, obtaining a matching lower bound is not possible with existing techniques: we prove that no lower bound can be derived by constructing hard matrices whose entries take values in a known countable set, because such matrices can be fully identified by a single query. This rules out, for instance, reducing to an optimization problem over the hypercube by encoding it as a binary payoff matrix. We then introduce a new technique for lower bounds, which allows us to obtain lower bounds of order tildeOmega(log(frac1Kε) for any ε ≤ 1 / (cK4), where c is a constant independent of K. We further discuss possible future directions to improve on our techniques in order to close the gap with the upper bounds.