Timezone: »

 
Poster
Last-iterate Convergence in Extensive-Form Games
Chung-Wei Lee · Christian Kroer · Haipeng Luo

Thu Dec 09 08:30 AM -- 10:00 AM (PST) @
in Poster Session 6 »

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.

Keywords: Online Learning

Author Information

Chung-Wei Lee (University of Southern California)
Christian Kroer (Columbia University)
Haipeng Luo (University of Southern California)

More from the Same Authors