No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium

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

References in corpus (6)

• DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker
• Bayes' Bluff: Opponent Modelling in Poker
• Learning to Correlate in Multi-Player General-Sum Sequential Games
• A Sampling-Based Approach to Computing Equilibria in Succinct Extensive-Form Games
• Correlation in Extensive-Form Games: Saddle-Point Formulation and Benchmarks
• Efficient Regret Minimization Algorithm for Extensive-Form Correlated Equilibrium

Cited by in corpus (6)

• DREAM: Deep Regret minimization with Advantage baselines and Model-free learning
• When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?
• The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces
• Multi-Agent Training beyond Zero-Sum with Correlated Equilibrium Meta-Solvers
• Efficient Decentralized Learning Dynamics for Extensive-Form Coarse Correlated Equilibrium: No Expensive Computation of Stationary Distributions Required
• Evolutionary Dynamics and $\Phi$-Regret Minimization in Games