Towards Characterizing the First-order Query Complexity of Learning (Approximate) Nash Equilibria in Zero-sum Matrix Games. (arXiv:2304.12768v2 [cs.GT] UPDATED)

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 …

arxiv complexity discovery equilibria games matrix observe query