Faster No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium

Abstract

A recent emerging trend in the literature on learning in games has been concerned with providing accelerated 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 sequential and simultaneous moves, as well as imperfect information. In this paper, we develop faster no-regret learning dynamics for extensive-form correlated equilibrium (EFCE) in multiplayer general-sum imperfect-information extensive-form games. When all agents play T repetitions of the game according to the accelerated dynamics, the correlated distribution of play is an O(T^-3/4)-approximate EFCE. This significantly improves over the best prior rate of O(T^-1/2). One of our conceptual contributions is to connect predictive (that is, optimistic) regret minimization with the framework of -regret. One of our main technical contributions is to characterize the stability of certain fixed point strategies through a refined perturbation analysis of a structured Markov chain, which may be of independent interest. Finally, experiments on standard benchmarks corroborate our findings.

Tasks

Reproductions