Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium

Understand

The existence of simple uncoupled no-regret learning 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 games generalize normal-form games by modeling both sequential and simultaneous moves, as well as imperfect information.
• Because of the sequential nature and presence of private information in the game, correlation in extensive-form games possesses significantly different properties than its counterpart in normal-form games, many of which are still open research directions.