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

arXiv: https://arxiv.org/abs/1911.04225 · HTML: https://mlsanity.com/paper/1911.04225/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Nov 2019.

## Built on by (most cited first, 2 of 2)

- [Learning to Infer Structures of Network Games](https://mlsanity.com/paper/2206.08119/) (2022)
- [A Theoretical Study of The Effects of Adversarial Attacks on Sparse Regression](https://mlsanity.com/paper/2212.11209/) (2022)

## Abstract (arXiv)

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 ℓ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.