Instance-dependent Sample Complexity Bounds for Zero-sum Matrix Games

Arnab Maiti, Kevin Jamieson, Lillian J. Ratliff

We study the sample complexity of identifying an approximate equilibrium for two-player zero-sum $n\times 2$ matrix games. That is, in a sequence of repeated game plays, how many r…