  In the first-order query model for zero-sum $K\times K$ matrix games, players
observe the expected pay-offs for all their possible actions under the
randomized action played by their opponent. This classical model has received
renewed interest after the discovery by Rakhlin and Sridharan that
$\epsilon$-approximate Nash equilibria can be computed efficiently from
$O(\frac{\ln K}{\epsilon})$ instead of $O(\frac{\ln K}{\epsilon^2})$ queries.
Surprisingly, the optimal number of such queries, as a function of both
$\epsilon$ and $K$, is not known. We make progress on this question on two
fronts. First, we fully characterise the query complexity of learning exact
equilibria ($\epsilon=0$), by showing that they require a number of queries
that is linear in $K$, which means that it is essentially as hard as querying
the whole matrix, which can also be done with $K$ queries. Second, for
$\epsilon > 0$, the current query complexity upper bound stands at
$O(\min(\frac{\ln(K)}{\epsilon} , K))$. We argue that, unfortunately, obtaining
a matching lower bound is not possible with existing techniques: we prove that
no lower bound can be derived by constructing hard matrices whose entries take
values in a known countable set, because such matrices can be fully identified
by a single query. This rules out, for instance, reducing to an optimization
problem over the hypercube by encoding it as a binary payoff matrix. We then
introduce a new technique for lower bounds, which allows us to obtain lower
bounds of order $\tilde\Omega(\log(\frac{1}{K\epsilon})$ for any $\epsilon \leq
1 / (cK^4)$, where $c$ is a constant independent of $K$. We further discuss
possible future directions to improve on our techniques in order to close the
gap with the upper bounds.
