Open Problem: Optimal Instance-Dependent Sample Complexity for Finding Nash Equilibrium in Two Player Zero-Sum Matrix Games
Abstract
Optimal instance-dependent sample complexity is a well-studied topic in the multi-armed bandit literature. However, the analogous question in the setting of two-player zero-sum matrix games, where the payoff matrix can only be accessed through noisy samples, remains largely unexplored despite being a natural generalization of the multi-armed bandit problem. In this write-up, we pose a simple open question: What is the optimal instance-dependent sample complexity to find an approximate Nash equilibrium in two-player zero-sum matrix games?
Cite
Text
Maiti. "Open Problem: Optimal Instance-Dependent Sample Complexity for Finding Nash Equilibrium in Two Player Zero-Sum Matrix Games." Proceedings of Thirty Eighth Conference on Learning Theory, 2025.Markdown
[Maiti. "Open Problem: Optimal Instance-Dependent Sample Complexity for Finding Nash Equilibrium in Two Player Zero-Sum Matrix Games." Proceedings of Thirty Eighth Conference on Learning Theory, 2025.](https://mlanthology.org/colt/2025/maiti2025colt-open/)BibTeX
@inproceedings{maiti2025colt-open,
title = {{Open Problem: Optimal Instance-Dependent Sample Complexity for Finding Nash Equilibrium in Two Player Zero-Sum Matrix Games}},
author = {Maiti, Arnab},
booktitle = {Proceedings of Thirty Eighth Conference on Learning Theory},
year = {2025},
pages = {6230-6234},
volume = {291},
url = {https://mlanthology.org/colt/2025/maiti2025colt-open/}
}