Is Nash Equilibrium Approximator Learnable?

In this paper, we investigate the learnability of the function approximator that approximates Nash equilibrium (NE) for games generated from a distribution. First, we offer a generalization bound using the Probably Approximately Correct (PAC) learning model. The bound describes the gap between the expected loss and empirical loss of the NE approximator. Afterward, we prove the agnostic PAC learnability of the Nash approximator. In addition to theoretical analysis, we demonstrate an application of NE approximator in experiments. The trained NE approximator can be used to warmstart and accelerate classical NE solvers. Together, our results show the practicability of approximating NE through function approximation.

Authors

• Zhijian Duan CFCS, School of Computer Science, Peking University
• Wenhan Huang
• Dinghuai Zhang
• Yali Du King's College London
• Jun Wang University College London
• Yaodong Yang Institute for Artificial Intelligence, Peking University
• Xiaotie Deng CFCS, School of Computer Science & CMAR, Institute for AI, Peking University

Keywords

• Game Theory
• Normal-Form Games
• Nash Equilibrium
• Function
• Approximation
• Generalization Bound
• PAC Learnability