Provable Computational and Statistical Guarantees for Efficient Learning of Continuous-Action Graphical Games

In this paper, we study the problem of learning the set of pure strategy Nash equilibria and the exact structure of a continuous-action graphical game with parametric payoffs by observing a small set of perturbed equilibria. A continuous-action graphical game can possibly have an uncountable set of Nash equilibria. We propose an ℓ12 block regularized method which recovers a graphical game, whose Nash equilibria are contained in the -Nash equilibria of the game from which the data was generated (true game). Under a slightly stringent condition on the parameters of the true game, our method recovers the exact structure of the graphical game. Our method has a logarithmic sample complexity with respect to the number of players. It also runs in polynomial time. A full version of this paper is accessible at: https://www.cs.purdue.edu/homes/abarik/icassp_para_games.pdf