Abstract: In this work, we study the sample complexity of finding a Nash Equilibrium (NE) of two-player zero-sum matrix games with noisy feedback. We propose a novel algorithm based on resolving linear programs (LP), achieving an $\veps$-approximate NE with sample complexity $O(\min\{\frac{m_1m_2}{\epsilon^2}\log\frac{m_1m_2}{\epsilon}, \frac{m_1m_2}{\epsilon\delta^2}\log(\frac{m_1m_2}{\epsilon\delta})\})$ for general $m_1\times m_2$ game matrices, where $\delta$ is certain instance-dependent value related to the LP. To our knowledge, this result provides the first instance-dependent sample complexity for general-dimension matrix games under noisy feedback and non-unique NE. Our algorithm is inspired by recent advances in online resource allocation and includes two key components: first, identifying a support set of the NE, and second, determining the unique NE within this support. Both steps rely on a careful analysis of the performance of solving the LP constructed by noisy samples.

Bio: Jiashuo Jiang is currently an assistant professor at Hong Kong University of Science and Technology. He works at the intersection of machine learning, optimization, and operations management, focusing particularly on online decision making. He obtained his PhD degree in Operations Research from NYU Stern School of Business in 2022.

组织者：周源