No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium

Andrea Celli*, Alberto Marchesi*, Gabriele Farina*, Nicola Gatti

Abstract

The existence of simple, uncoupled no-regret dynamics that converge to correlated equilibria in normal-form games is a celebrated result in the theory of multi-agent systems. Specifically, it has been known for more than 20 years that when all players seek to minimize their internal regret in a repeated normal-form game, the empirical frequency of play converges to a normal-form correlated equilibrium. Extensive-form (that is, tree-form) games generalize normal-form games by modeling both sequential and simultaneous moves, as well as private information. Because of the sequential nature and presence of partial information in the game, extensive-form correlation has significantly different properties than the normal-form counterpart, many of which are still open research directions. Extensive-form correlated equilibrium (EFCE) has been proposed as the natural extensive-form counterpart to normal-form correlated equilibrium. However, it was currently unknown whether EFCE emerges as the result of uncoupled agent dynamics. In this paper, we give the first uncoupled no-regret dynamics that converge to the set of EFCEs in n-player general-sum extensive-form games with perfect recall. First, we introduce a notion of trigger regret in extensive-form games, which extends that of internal regret in normal-form games. When each player has low trigger regret, the empirical frequency of play is a close to an EFCE. Then, we give an efficient no-trigger-regret algorithm. Our algorithm decomposes trigger regret into local subproblems at each decision point for the player, and constructs a global strategy of the player from the local solutions at each decision point.

Bibtex entry

@inproceedings{Celli20:NoRegret, title={No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium}, author={Celli, Andrea and Marchesi, Alberto and Farina, Gabriele and Gatti, Nicola}, booktitle={Conference on Neural Information Processing Systems (NeurIPS)}, year={2020} }

Download

Paper PDF

Bibtex entry

@inproceedings{Celli20:NoRegret, title={No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium}, author={Celli, Andrea and Marchesi, Alberto and Farina, Gabriele and Gatti, Nicola}, booktitle={Conference on Neural Information Processing Systems (NeurIPS)}, year={2020} }

Typo or question?

Get in touch!
gfarina AT mit.edu

Metadata

Venue: NeurIPS 2020
Topic: Decision Making, Optimization, and Computational Game Theory