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

Arnab Maiti, Kevin Jamieson, Lillian Ratliff
Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, PMLR 206:9429-9469, 2023.

Abstract

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 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 $X_{ij}$ such that $\mathbb{E}[X_{ij}] = A_{ij}$. 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.

Cite this Paper


BibTeX
@InProceedings{pmlr-v206-maiti23a, title = {Instance-dependent Sample Complexity Bounds for Zero-sum Matrix Games}, author = {Maiti, Arnab and Jamieson, Kevin and Ratliff, Lillian}, booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics}, pages = {9429--9469}, year = {2023}, editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem}, volume = {206}, series = {Proceedings of Machine Learning Research}, month = {25--27 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v206/maiti23a/maiti23a.pdf}, url = {https://proceedings.mlr.press/v206/maiti23a.html}, abstract = {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 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 $X_{ij}$ such that $\mathbb{E}[X_{ij}] = A_{ij}$. 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.} }
Endnote
%0 Conference Paper %T Instance-dependent Sample Complexity Bounds for Zero-sum Matrix Games %A Arnab Maiti %A Kevin Jamieson %A Lillian Ratliff %B Proceedings of The 26th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2023 %E Francisco Ruiz %E Jennifer Dy %E Jan-Willem van de Meent %F pmlr-v206-maiti23a %I PMLR %P 9429--9469 %U https://proceedings.mlr.press/v206/maiti23a.html %V 206 %X 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 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 $X_{ij}$ such that $\mathbb{E}[X_{ij}] = A_{ij}$. 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.
APA
Maiti, A., Jamieson, K. & Ratliff, L.. (2023). Instance-dependent Sample Complexity Bounds for Zero-sum Matrix Games. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 206:9429-9469 Available from https://proceedings.mlr.press/v206/maiti23a.html.

Related Material