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 $\ell_{12}$ block regularized method which recovers a graphical game, whose Nash equilibria are contained in the $\epsilon$-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. \textit{A full version of this paper is accessible at:} \url{https://www.cs.purdue.edu/homes/abarik/icassp_para_games.pdf}