Last-iterate Convergence in Extensive-Form Games

Regret-based algorithms are highly efficient at finding approximate Nash equilibria in sequential games such as poker games. However, most regret-based algorithms, including counterfactual regret minimization (CFR) and its variants, rely on iterate averaging to achieve convergence. Inspired by recent advances on last-iterate convergence of optimistic algorithms in zero-sum normal-form games, we study this phenomenon in sequential games, and provide a comprehensive study of last-iterate convergence for zero-sum extensive-form games with perfect recall (EFGs), using various optimistic regret-minimization algorithms over treeplexes. This includes algorithms using the vanilla entropy or squared Euclidean norm regularizers, as well as their dilated versions which admit more efficient implementation. In contrast to CFR, we show that all of these algorithms enjoy last-iterate convergence, with some of them even converging exponentially fast. We also provide experiments to further support our theoretical results. Wei et al., 2021] have been shown to enjoy attractive last-iterate convergence guarantees. However, almost none of these results apply to the case of EFGs: Wei et al. [2021] show a result that implies linear convergence of vanilla OGDA in EFGs (see Corollary 5), but no results are known for vanilla OMWU or more importantly for algorithms instantiated with dilated regularizers which lead to fast iterate updates in EFGs. In this work we extend the existing results on normal-form games to EFGs, including the practically-important dilated regularizers. Problem Setup We start with some basic notation. For a vector z, we use z i to denote its i-th coordinate and z p to denote its p-norm (with z being a shorthand for z 2 ). For a convex function ψ, the associated Bregman divergence is define as p holds for all u and v in the domain. The Kullback-Leibler divergence, which is the Bregman divergence with respect to the entropy function, is denoted by KL(•, •). Finally, we use ∆ P to denote the (P -1)-dimensional simplex and [N ] to denote the set 1, 2 . . . , N for some positive integer N .