Bounding regret in empirical games

Bounding regret in empirical games

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

Full description

Saved in:
Bibliographic Details
Main Authors: JECMEN, Steven, SINHA, Arunesh, LI, Zun, TRAN-THANH, Long
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2020
Subjects:
Game theoretic analysis
Multi-armed bandit problem
Nash equilibria
Optimization goals
Sample complexity
Artificial Intelligence and Robotics
Theory and Algorithms
Online Access:https://ink.library.smu.edu.sg/sis_research/5075
https://ink.library.smu.edu.sg/context/sis_research/article/6078/viewcontent/AAAI_20_Bandit_Submission.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
Description
Summary: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

Similar Items