TY - CONF
T1 - Towards characterizing the first-order query complexity of learning (approximate) Nash equilibria in zero-sum matrix games
AU - Hédi Hadiji
AU - Sarah Sachs
AU - Tim van Erven
AU - Koolen, Wouter
PY - 2023/12/1
Y1 - 2023/12/1
N2 - In the first-order query model for zero-sum K × 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 ε-approximate Nash equilibria can be computed efficiently from O(ln K/ε) instead of O(ln K/ε2 ) queries. Surprisingly, the optimal number of such queries, as a function of both ε 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 (ε = 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 ε > 0, the current query complexity upper bound stands at O(min(ln(K)/ε, 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 Ω(log( ˜ 1 Kε )) for any ε ⩽ 1/(cK4 ), 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.
AB - In the first-order query model for zero-sum K × 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 ε-approximate Nash equilibria can be computed efficiently from O(ln K/ε) instead of O(ln K/ε2 ) queries. Surprisingly, the optimal number of such queries, as a function of both ε 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 (ε = 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 ε > 0, the current query complexity upper bound stands at O(min(ln(K)/ε, 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 Ω(log( ˜ 1 Kε )) for any ε ⩽ 1/(cK4 ), 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.
M3 - Paper
T2 - Neural Information Processing Systems 2023
Y2 - 11 December 2023 through 16 December 2023
ER -