Faster No-Regret Learning Dynamics for Extensive-Form Correlated and Coarse Correlated Equilibrium
Ioannis Anagnostides*, Gabriele Farina*, Christian Kroer, Andrea Celli, Tuomas Sandholm
Abstract
A recent emerging trend in the literature on learning in games has been concerned with providing faster learning dynamics for Correlation and Mediated Equilibria in normal-form games. Much less is known about the significantly more challenging setting of extensive-form games, which can capture both sequential and simultaneous moves, as well as imperfect information. In this paper we establish faster no-regret learning dynamics for
extensive-form correlated equilibria (EFCE) in multiplayer general-sum imperfect-information extensive-form games. When all players follow our accelerated dynamics, the correlated distribution of play is an $O(T^{-3/4})$-approximate EFCE, where the $O(\cdot)$ notation suppresses parameters polynomial in the description of the game. This significantly improves over the best prior rate of $O(T^{-1/2})$. To achieve this, we develop a framework for performing accelerated
Phi-regret minimization via predictions. One of our key technical contributions---that enables us to employ our generic template---is to characterize the stability of fixed points associated with
trigger deviation functions through a refined perturbation analysis of a structured Markov chain. Furthermore, for the simpler solution concept of extensive-form
coarse correlated equilibrium (EFCCE) we give a new succinct closed-form characterization of the associated fixed points, bypassing the expensive computation of stationary distributions required for EFCE. Our results place EFCCE closer to
normal-form coarse correlated equilibria in terms of the per-iteration complexity, although the former prescribes a much more compelling notion of correlation. Finally, experiments conducted on standard benchmarks corroborate our theoretical findings.
Bibtex entry
@inproceedings{Anagnostides22:Faster,
title={Faster No-Regret Learning Dynamics for Extensive-Form Correlated and Coarse Correlated Equilibrium},
author={Ioannis Anagnostides and Gabriele Farina
and Christian Kroer and Andrea Celli and Tuomas Sandholm},
booktitle={Economics and Computation},
year={2022}
}