Timezone: »

 
Poster
No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium
Andrea Celli · Alberto Marchesi · Gabriele Farina · Nicola Gatti

Tue Dec 08 09:00 AM -- 11:00 AM (PST) @ Poster Session 1 #535
in Poster Session 2 »

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.

Author Information

Andrea Celli (Politecnico di Milano)
Alberto Marchesi (Politecnico di Milano)
Gabriele Farina (Carnegie Mellon University)
Nicola Gatti (Politecnico di Milano)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors