Duan, Z;
Huang, W;
Zhang, D;
Du, Y;
Wang, J;
Yang, Y;
Deng, X;
(2023)
Is Nash Equilibrium Approximator Learnable?
In:
Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems.
(pp. pp. 233-241).
International Foundation for Autonomous Agents and Multiagent Systems
Preview |
Text
2108.07472.pdf - Accepted Version Download (1MB) | Preview |
Abstract
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 warm-start and accelerate classical NE solvers. Together, our results show the practicability of approximating NE through function approximation.
| Type: | Proceedings paper |
|---|---|
| Title: | Is Nash Equilibrium Approximator Learnable? |
| Event: | AAMAS '23: 2023 International Conference on Autonomous Agents and Multiagent Systems |
| ISBN-13: | 9781450394321 |
| Open access status: | An open access version is available from UCL Discovery |
| Publisher version: | https://dl.acm.org/doi/10.5555/3545946.3598642 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10178132 |
Archive Staff Only
 |
View Item |
