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 correlated and coarse correlated 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} }

Download

Paper PDF

Typo or question?

Get in touch!
gfarina AT cs.cmu.edu

Metadata

Venue: EC 2022
Topic: Decision Making, Optimization, and Computational Game Theory