Provable Computational and Statistical Guarantees for Efficient Learning of Continuous-Action Graphical Games
This provides efficient learning guarantees for graphical games, which is important for multi-agent systems and economics, though it appears incremental as it builds on existing game learning frameworks.
The paper tackles the problem of learning continuous-action graphical games with quadratic payoffs from a small set of perturbed equilibria, proposing an ℓ₁₂-block regularized method that recovers the game structure and its ε-Nash equilibria with logarithmic sample complexity in the number of players and polynomial runtime.
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 quadratic payoffs by observing a small set of perturbed equilibria. A continuous-action graphical game can possibly have an uncountable set of Nash euqilibria. We propose a $\ell_{12}-$ block regularized method which recovers a graphical game, whose Nash equilibria are 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.