Francisco Ruiz, Jennifer Dy
(Ed.)

We study the sample complexity of identifying an approximate equilibrium for two-player
zero-sum n × 2 matrix games. That is, in a sequence of repeated game plays, how many
rounds must the two players play before reaching an approximate equilibrium (e.g., Nash)? We
derive instance-dependent bounds that define an ordering over game matrices that captures
the intuition that the dynamics of some games converge faster than others. Specifically, we
consider a stochastic observation model such that when the two players choose actions i and
j, respectively, they both observe each other’s played actions and a stochastic observation Xij
such that E [Xij ] = Aij . To our knowledge, our work is the first case of instance-dependent
lower bounds on the number of rounds the players must play before reaching an approximate
equilibrium in the sense that the number of rounds depends on the specific properties of the
game matrix A as well as the desired accuracy. We also prove a converse statement: there exist
player strategies that achieve this lower bound.

more »
« less