Statistical learning theory / Open question
How Hard Is Learning an Equilibrium?
Learning from interaction involves several competing decision makers. The intrinsic difficulty should reflect the game's structure, not just the number of possible action pairs.
Seed catalog · Showing the bundled record.
Problem statement
Characterize the optimal instance-dependent sample complexity of finding an -Nash equilibrium in a finite two-player zero-sum matrix game from noisy entry queries, with success probability at least . Seek a quantity determined by the payoff matrix and accuracy that admits matching achievable and necessary sample bounds, including mixed and nonunique equilibria.
Assumptions and scope
- A centralized learner chooses matrix entries adaptively and receives independent zero-mean 1-sub-Gaussian noise; fix a bounded payoff range and both matrix dimensions.
- Specify approximate Nash through each player's unilateral gain, rather than replacing it by expected estimator bias or cumulative Nash regret.
- Allow nonunique equilibria and charge support identification. A characterization that assumes the equilibrium support is known is a restricted baseline.
What would settle it?
An instance-dependent fixed-confidence lower bound and an adaptive algorithm matching it up to stated factors, or a sharp characterization for a new mixed-equilibrium family.
Selected for a theoretical or computational target. A fitted scaling curve or improved benchmark score alone does not establish the stated learning-theoretic guarantee.
Status and evidence
Strict pure equilibria and n-by-2 cases already have instance-dependent results. General-dimensional epsilon-bias LP bounds and polylogarithmic Nash-regret claims appeared in 2026. These objectives do not automatically settle the COLT fixed-confidence approximate-equilibrium question. This is an editorial reformulation of a published open problem. The preliminary review through 2026-11-19 does not certify novelty or exclude an unlocated resolution.
Preliminary source check; not an expert-verified open status or an independent audit of proposed proofs. The compilation date is not a literature-review cutoff.
Sources and further reading
- Maiti — Optimal Instance-Dependent Sample Complexity for Finding Nash Equilibrium in Two Player Zero-Sum Matrix Games ↗problem statement · source checked 2026-11-19
PDF Sections 2–3 checked: adaptive entry sampling with zero-mean 1-sub-Gaussian noise and high-probability approximate Nash identification; strict-pure and n-by-2 cases already have bounds.
- Maiti et al. — Near-Optimal Pure Exploration in Matrix Games ↗partial theory · source checked 2026-11-19
Primary search abstract checked: pure-strategy Nash identification matches instance-dependent lower bounds up to logarithmic factors. Mixed or nonunique equilibria require separate analysis.
- Jiang and Zhang — An LP-Based Approach for Bilinear Saddle Point Problem with Instance-Dependent Guarantee and Noisy Feedback ↗partial theory · source checked 2026-11-19
Primary search abstract checked: instance-dependent general-dimension, potentially nonunique-equilibrium bounds for epsilon bias. Expected bias is not interchangeable with fixed-confidence equilibrium error.
- Zhang — Polylogarithmic Nash Regret in Matrix Games with Bandit Feedback ↗partial theory · source checked 2026-11-19
Primary search abstract checked: a claimed resolution for polylogarithmic Nash regret against adaptive opponents with observed actions. The catalogue target is sharp fixed-confidence sample complexity, a distinct objective.