Optimal Instance-Dependent Sample Complexity for finding Nash Equilibrium in Two Player Zero-Sum Matrix games

Let $A \in [-1,1]^{n \times m}$ be an unknown payoff matrix of a two-player zero-sum matrix game. The row player chooses $x \in \Delta_n := \{x \in \mathbb{R}^n_{\ge 0}: \sum_{i=1}^n x_i = 1\}$ and the column player chooses $y \in \Delta_m$; the expected payoff to the row player is $x^\top A y$. The (minimax) value is

The algorithm does not observe $A$ directly. On each round $t$, it adaptively selects an entry $(i_t,j_t) \in [n] \times [m]$ and receives a random sample $X_t$ such that $\mathbb{E}[X_t \mid i_t,j_t] = A_{i_t j_t}$ and the noise $X_t - A_{i_t j_t}$ is (say) conditionally 1-sub-Gaussian. For accuracy $\varepsilon>0$ and confidence $\delta \in (0,1)$, an output pair $(\hat x,\hat y) \in \Delta_n \times \Delta_m$ is an $\varepsilon$-approximate Nash equilibrium (equivalently, an $\varepsilon$-approximate saddle point) if its exploitability is at most $\varepsilon$:

Define the instance-dependent sample complexity $T^*(A,\varepsilon,\delta)$ as the smallest integer $T$ for which there exists an adaptive algorithm that, on instance $A$, makes at most $T$ noisy entry queries and outputs an $\varepsilon$-approximate Nash equilibrium with probability at least $1-\delta$.