No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium
  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.
