2019/11/08 by Adarsh Barik, Barik, Adarsh, Jean Honorio +1
Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Advanced Causal Inference Techniques #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Applications #Machine Learning (cs.LG) #Machine Learning (stat.ML)
paper · pdf · doi:10.48550/arxiv.1911.04225
openalex publication_date 2019/11/08 · openalex created_date 2023/05/07 · openalex updated_date 2026/07/28
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.