English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In the first-order query model for zero-sum $K\times K$ matrix games, playersobserve the expected pay-offs for all their possible actions under therandomized action played by their opponent. This classical model has receivedrenewed 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 twofronts. First, we fully characterise the query complexity of learning exactequilibria ($\epsilon=0$), by showing that they require a number of queriesthat is linear in $K$, which means that it is essentially as hard as queryingthe 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, obtaininga matching lower bound is not possible with existing techniques: we prove thatno lower bound can be derived by constructing hard matrices whose entries takevalues in a known countable set, because such matrices can be fully identifiedby a single query. This rules out, for instance, reducing to an optimizationproblem over the hypercube by encoding it as a binary payoff matrix. We thenintroduce a new technique for lower bounds, which allows us to obtain lowerbounds of order $\tilde\Omega(\log(\frac{1}{K\epsilon})$ for any $\epsilon \leq1 / (cK^4)$, where $c$ is a constant independent of $K$. We further discusspossible future directions to improve on our techniques in order to close thegap with the upper bounds.

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