Publication Type
Conference Proceeding Article
Version
publishedVersion
Publication Date
2-2020
Abstract
Empirical game-theoretic analysis refers to a set of models and techniques for solving large-scale games. However, there is a lack of a quantitative guarantee about the quality of output approximate Nash equilibria (NE). A natural quantitative guarantee for such an approximate NE is the regret in the game (i.e. the best deviation gain). We formulate this deviation gain computation as a multi-armed bandit problem, with a new optimization goal unlike those studied in prior work. We propose an efficient algorithm Super-Arm UCB (SAUCB) for the problem and a number of variants. We present sample complexity results as well as extensive experiments that show the better performance of SAUCB compared to several baselines
Keywords
Game theoretic analysis, Multi-armed bandit problem, Nash equilibria, Optimization goals, Sample complexity
Discipline
Artificial Intelligence and Robotics | Theory and Algorithms
Research Areas
Data Science and Engineering
Publication
Proceedings of 34rd AAAI Conference on Artificial Intelligence (AAAI), New York, 2020 February 7-12
First Page
1
Last Page
8
ISBN
9781577358350
Identifier
10.1609/aaai.v34i04.5851
Publisher
AAAI Press
City or Country
Menlo Park, CA
Citation
JECMEN, Steven; SINHA, Arunesh; LI, Zun; and TRAN-THANH, Long.
Bounding regret in empirical games. (2020). Proceedings of 34rd AAAI Conference on Artificial Intelligence (AAAI), New York, 2020 February 7-12. 1-8.
Available at: https://ink.library.smu.edu.sg/sis_research/5075
Copyright Owner and License
Publisher
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1609/aaai.v34i04.5851