Optimal Instance-Dependent Sample Complexity for Two-Player Zero-Sum Games

Let $A\in\mathbb R^{n\times m}$ be unknown. A query $(i,j)$ returns $A_{ij}+\eta$, where $\eta$ is zero-mean and $1$-sub-Gaussian. Let $\Delta_n$ and $\Delta_m$ be the probability simplices. A pair $(\widehat x,\widehat y)\in\Delta_n\times\Delta_m$ is an $\varepsilon$-approximate Nash equilibrium if, for every $x\in\Delta_n$ and $y\in\Delta_m$,

$$x^\top A\widehat y\leq \widehat x^\top A\widehat y+\varepsilon, \qquad \widehat x^\top Ay\geq \widehat x^\top A\widehat y-\varepsilon.$$

What is the optimal instance-dependent sample complexity for identifying an $\varepsilon$-approximate Nash equilibrium, with probability at least $1-\delta$, in a two-player zero-sum game defined by $A$? More precisely, give a tight instance-dependent characterization of

$$\widetilde\Theta\bigl(H_1(A,\varepsilon)\log(1/\delta)+H_2(A,\varepsilon)\bigr),$$

where $H_1$ and $H_2$ are functions of the payoff matrix $A$ and the approximation parameter $\varepsilon$, capturing the instance's inherent difficulty. Identify which parameters of $A$ govern $H_1$ and $H_2$, and give matching algorithms and lower bounds.