  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 possesses
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, though it was currently unknown whether
EFCE emerges as the result of uncoupled agent dynamics. In this article, we
give the first uncoupled no-regret dynamics that converge with high probability
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-regret algorithm which guarantees with high
probability that trigger regrets grow sublinearly in the number of iterations.
