Towards Characterizing the First-order Query Complexity of Learning (Approximate) Nash Equilibria in Zero-sum Matrix Games

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. 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. 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.