# Last-iterate Convergence in Extensive-Form Games

Chung-Wei Lee
University of Southern California
<EMAIL_ADDRESS>Christian Kroer
Columbia University
<EMAIL_ADDRESS>Haipeng Luo
University of Southern California
<EMAIL_ADDRESS>
###### Abstract

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.

##  1 Introduction

Extensive-form games (EFGs) are an important class of games in game theory and
artificial intelligence which can model imperfect information and sequential
interactions. EFGs are typically solved by finding or approximating a _Nash
equilibrium_. Regret-minimization algorithms are among the most popular
approaches to approximate Nash equilibria. The motivation comes from a
classical result which says that in two-player zero-sum games, when both
players use _no-regret_ algorithms, _the average strategy_ converges to Nash
equilibrium (Freund and Schapire, 1999; Hart and Mas-Colell, 2000; Zinkevich
et al., 2007). Counterfactual Regret Minimization (CFR) (Zinkevich et al.,
2007) and it variants such as CFR+ (Tammelin, 2014) are based on this
motivation.

However, due to their ergodic convergence guarantee, theoretical convergence
rates of regret-minimization algorithms are typically limited to
$\mathcal{O}(1/\sqrt{T})$ or $\mathcal{O}(1/T)$ for $T$ rounds, and this is
also the case in practice (Brown and Sandholm, 2019a; Burch et al., 2019). In
contrast, it is known that linear convergence rates are achievable for certain
other first-order algorithms (Tseng, 1995; Gilpin et al., 2008). Additionally,
the averaging procedure can create complications. It not only increases the
computational and memory overhead (Bowling et al., 2015), but also makes
things difficult when incorporating neural networks in the solution process,
where averaging is usually not possible. Indeed, to address this issue, Brown
et al. (2019) create a separate neural network to approximate the average
strategy in their Deep CFR model.

Therefore, a natural idea is to design regret-minimization algorithms whose
last strategy converges (we call this _last-iterate convergence_), ideally at
a faster rate than the average iterate. Unfortunately, many regret
minimization algorithms such as regret matching, regret matching+, and hedge,
are known not to satisfy this property empirically and theoretically even for
normal-form games. Although Bowling et al. (2015) find that in Heads-Up Limit
Hold’em poker the last strategy of CFR+ is better than the average strategy,
and Farina et al. (2019b) observe in some experiments the last-iterate of
optimistic OMD and FTRL converge fast, a theoretical understanding of this
phenomenon is still absent for EFGs.

In this work, inspired by recent results on last-iterate convergence in
normal-form games (Wei et al., 2021), we greatly extend the theoretical
understanding of last-iterate convergence of regret-minimization algorithms in
two-player zero-sum extensive-form games with perfect recall, and open up many
interesting directions both in theory and practice. First, we show that any
optimistic online mirror-descent algorithm instantiated with a strongly convex
regularizer that is continuously differentiable on the EFG strategy space
provably enjoys last-iterate convergence, while CFR with either regret
matching or regret matching+ fails to converge. Moreover, for some of the
optimistic algorithms, we further show explicit convergence rates. In
particular, we prove that optimistic mirror descent instantiated with the
1-strongly-convex dilated entropy regularizer (Kroer et al., 2020), which we
refer to as _Dilated Optimistic Multiplicative Weights Update_ (DOMWU), has a
_linear_ convergence rate under the assumption that there is a unique Nash
equilibrium; we note that this assumption was also made by Daskalakis and
Panageas (2019); Wei et al. (2021) in order to achieve similar results for
normal-form games.

##  2 Related Work

##### Extensive-form Games

Here we focus on work related to two-player zero-sum perfect-recall games.
Although there are many game-solving techniques such as abstraction (Kroer and
Sandholm, 2014; Ganzfried and Sandholm, 2014; Brown et al., 2015), endgame
solving (Burch et al., 2014; Ganzfried and Sandholm, 2015), and subgame
solving (Moravcik et al., 2016; Brown and Sandholm, 2019b), these methods all
rely on scalable methods for computing approximate Nash equilibria. There are
several classes of algorithms for computing approximate Nash equilibria, such
as double-oracle methods (McMahan et al., 2003), fictitious play (Brown, 1951;
Heinrich and Silver, 2016), first-order methods (Hoda et al., 2010; Kroer et
al., 2020), and CFR methods (Zinkevich et al., 2007; Lanctot et al., 2009;
Tammelin, 2014). Notably, variants of the CFR approach have achieved
significant success in poker games (Bowling et al., 2015; Moravčík et al.,
2017; Brown and Sandholm, 2018). Underlying the first-order and CFR approaches
is the sequence-form representation (von Stengel, 1996), which allows the
problem to be represented as a bilinear saddle-point problem. This leads to
algorithms based on smoothing techniques and other first-order methods (Gilpin
et al., 2008; Kroer et al., 2017; Gao et al., 2021), and enables CFR via the
theorem connecting no-regret guarantees to Nash equilibrium.

##### Online Convex Optimization and Optimistic Regret Minimization

Online convex optimization (Zinkevich, 2003) is a framework for repeated
decision making where the goal is to minimize regret. When applied to repeated
two-player zero-sum games, it is known that the average strategy converges to
Nash Equilibria at the rate of $\mathcal{O}(1/\sqrt{T})$ when both players
apply regret-minimization algorithms whose regret grows on the order of
$\mathcal{O}(\sqrt{T})$ (Freund and Schapire, 1999; Hart and Mas-Colell, 2000;
Zinkevich et al., 2007). Moreover, when the players use optimistic regret-
minimization algorithms, the convergence rate is improved to
$\mathcal{O}(1/T)$ (Rakhlin and Sridharan, 2013; Syrgkanis et al., 2015).
Recent works have applied optimism ideas to EFGs, such as optimistic
algorithms with dilated regularizers (Kroer et al., 2020; Farina et al.,
2019b), CFR-like local optimistic algorithms (Farina et al., 2019a), and
optimistic CFR algorithms (Burch, 2018; Brown and Sandholm, 2019a; Farina et
al., 2021a). However, the theoretical results in all these existing papers
consider the average strategy, while we are the first to consider last-iterate
convergence in EFGs.

##### Last-iterate Convergence in Saddle-point Optimization

As mentioned previously, two-player zero-sum games can be formulated as
saddle-point optimization problems. Saddle-point problems have recently gained
a lot of attention due to their applications in machine learning, for example
in generative adversarial networks (Goodfellow et al., 2014). Basic
algorithms, including gradient descent ascent and multiplicative weights
update, diverge even in simple instances (Mertikopoulos et al., 2018; Bailey
and Piliouras, 2018). In contrast, their optimistic versions, optimistic
gradient descent ascent (OGDA) (Daskalakis et al., 2018; Mertikopoulos et al.,
2019; Wei et al., 2021) and optimistic multiplicative weights update (OMWU)
(Daskalakis and Panageas, 2019; Lei et al., 2021; 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.

##  3 Problem Setup

We start with some basic notation. For a vector ${\bm{z}}$, we use $z_{i}$ to
denote its $i$-th coordinate and $\|{\bm{z}}\|_{p}$ to denote its $p$-norm
(with $\|{\bm{z}}\|$ being a shorthand for $\|{\bm{z}}\|_{2}$). For a convex
function $\psi$, the associated Bregman divergence is define as
$D_{\psi}(\bm{u},\bm{v})=\psi(\bm{u})-\psi(\bm{v})-\langle\nabla\psi(\bm{v}),\bm{u}-\bm{v}\rangle$,
and $\psi$ is called $\kappa$-strongly convex with respect to the $p$-norm if
$D_{\psi}(\bm{u},\bm{v})\geq\frac{\kappa}{2}\|\bm{u}-\bm{v}\|_{p}^{2}$ holds
for all $\bm{u}$ and $\bm{v}$ in the domain. The Kullback-Leibler divergence,
which is the Bregman divergence with respect to the entropy function, is
denoted by $\text{\rm KL}(\cdot,\cdot)$. Finally, we use $\Delta_{P}$ to
denote the $(P-1)$-dimensional simplex and $[N]$ to denote the set
$\\{1,2\dots,N\\}$ for some positive integer $N$.

##### Extensive-form Games as Bilinear Saddle-point Optimization

We consider the problem of finding a Nash equilibrium of a two-player zero-sum
extensive-form game (EFG) with perfect recall. Instead of formally introducing
the definition of an EFG (see Appendix A for an example), for the purpose of
this work, it suffices to consider an equivalent formulation, which casts the
problem as a simple bilinear saddle-point optimization (von Stengel, 1996):

$\displaystyle\min_{{\bm{x}}\in{\mathcal{X}}}\max_{y\in{\mathcal{Y}}}{\bm{x}}^{\top}\bm{G}{\bm{y}}=\max_{y\in{\mathcal{Y}}}\min_{{\bm{x}}\in{\mathcal{X}}}{\bm{x}}^{\top}\bm{G}{\bm{y}},$
(1)

where $\bm{G}\in[-1,+1]^{M\times N}$ is a known matrix, and
${\mathcal{X}}\subset\mathbb{R}^{M}$ and ${\mathcal{Y}}\subset\mathbb{R}^{N}$
are two polytopes called _treeplexes_ (to be defined soon). The set of Nash
equilibria is then defined as
$\mathcal{Z}^{*}={\mathcal{X}}^{*}\times{\mathcal{Y}}^{*}$, where
${\mathcal{X}}^{*}=\operatorname*{argmin}_{{\bm{x}}\in{\mathcal{X}}}\max_{y\in{\mathcal{Y}}}{\bm{x}}^{\top}\bm{G}{\bm{y}}$
and
${\mathcal{Y}}^{*}=\operatorname*{argmax}_{y\in{\mathcal{Y}}}\min_{{\bm{x}}\in{\mathcal{X}}}{\bm{x}}^{\top}\bm{G}{\bm{y}}$.
Our goal is to find a point $z\in\mathcal{Z}={\mathcal{X}}\times{\mathcal{Y}}$
that is close to the set of Nash equilibria $\mathcal{Z}^{*}$, and we use the
Bregman divergence (of some function $\psi$) between ${\bm{z}}$ and the
closest point in $\mathcal{Z}^{*}$ to measure the closeness, that is,
$\min_{{\bm{z}}^{*}\in\mathcal{Z}^{*}}D_{\psi}({\bm{z}}^{*},{\bm{z}})$.

For notational convenience, we let $P=M+N$ and
$F({\bm{z}})=(\bm{G}{\bm{y}},-\bm{G}^{\top}{\bm{x}})$ for any
${\bm{z}}=({\bm{x}},{\bm{y}})\in\mathcal{Z}\subset\mathbb{R}^{P}$. Without
loss of generality, we assume $\|F({\bm{z}})\|_{\infty}\leq 1$ for all
${\bm{z}}\in\mathcal{Z}$ (which can always be ensured by normalizing the
entries of $\bm{G}$ accordingly).

##### Treeplexes

The structure of the EFG is implicitly captured by the treeplexes
${\mathcal{X}}$ and ${\mathcal{Y}}$, which are generalizations of simplexes
that capture the sequential structure of an EFG. The formal definition is as
follows. (In Appendix A, we provide more details on the connection between
treeplexes and the structure of the EFG, as well as concrete examples of
treeplexes for better illustrations.)

######  Definition 1 (Hoda et al. (2010)).

A treeplex is recursively constructed via the following three operations:

  1. 1.

Every probability simplex is a treeplex.

  2. 2.

Given treeplexes $\mathcal{Z}_{1},\dots,\mathcal{Z}_{K}$, the Cartesian
product $\mathcal{Z}_{1}\times\cdots\times\mathcal{Z}_{K}$ is a treeplex.

  3. 3.

(Branching) Given treeplexes $\mathcal{Z}_{1}\subset\mathbb{R}^{M}$ and
$\mathcal{Z}_{2}\subset\mathbb{R}^{N}$, and any $i\in[M]$,

$\mathcal{Z}_{1}~{}\framebox{\text{$i$}}~{}\mathcal{Z}_{2}=\left\\{(\bm{u},u_{i}\cdot\bm{v})\in\mathbb{R}^{M+N}:\bm{u}\in\mathcal{Z}_{1},~{}\bm{v}\in\mathcal{Z}_{2}\right\\}$

is a treeplex.

By definition, a treeplex is a tree-like structure built with simplexes, which
intuitively represents the tree-like decision space of a single player, and an
element in the treeplex represents a strategy for the player. Let
$\mathcal{H}^{\mathcal{Z}}$ denote the collection of all the simplexes in
treeplex $\mathcal{Z}$, which following Definition 1 can be recursively
defined as: $\mathcal{H}^{\mathcal{Z}}=\\{\mathcal{Z}\\}$ if $\mathcal{Z}$ is
a simplex;
$\mathcal{H}^{\mathcal{Z}}=\bigcup_{k=1}^{K}\mathcal{H}^{\mathcal{Z}_{i}}$ if
$\mathcal{Z}$ is a Cartesian product
$\mathcal{Z}_{1}\times\cdots\times\mathcal{Z}_{K}$; and
$\mathcal{H}^{\mathcal{Z}}=\mathcal{H}^{\mathcal{Z}_{1}}\cup\mathcal{H}^{\mathcal{Z}_{2}}$
if $\mathcal{Z}=\mathcal{Z}_{1}~{}\framebox{\text{$i$}}~{}\mathcal{Z}_{2}$. In
EFG terminology, $\mathcal{H}^{{\mathcal{X}}}$ and
$\mathcal{H}^{{\mathcal{Y}}}$ are the collections of _information sets_ for
player ${\bm{x}}$ and player ${\bm{y}}$ respectively, which are the decision
points for the players, at which they select an action within the simplex. For
any $h\in\mathcal{H}^{\mathcal{Z}}$, we let $\Omega_{h}$ denote the set of
indices belonging to $h$, and for any ${\bm{z}}\in\mathcal{Z}$, we let
${\bm{z}}_{h}$ be the slice of ${\bm{z}}$ whose indices are in $\Omega_{h}$.
For each index $i$, we also let $h(i)$ be the simplex $i$ falls into, that is,
$i\in\Omega_{h(i)}$.

In Definition 1, the last branching operation naturally introduces the concept
of a _parent variable_ for each $h\in\mathcal{H}^{\mathcal{Z}}$, which can
again be recursively defined as: if $\mathcal{Z}$ is a simplex, then it has no
parent; if $\mathcal{Z}$ is a Cartesian product
$\mathcal{Z}_{1}\times\cdots\times\mathcal{Z}_{K}$, then the parent of
$h\in\mathcal{H}^{\mathcal{Z}}$ is the same as the parent of $h$ in the
treeplex $\mathcal{Z}_{k}$ that $h$ belongs to (that is,
$h\in\mathcal{H}^{\mathcal{Z}_{k}}$); finally, if
$\mathcal{Z}=\left\\{(\bm{u},u_{i}\cdot\bm{v}):\bm{u}\in\mathcal{Z}_{1},~{}\bm{v}\in\mathcal{Z}_{2}\right\\}$,
then for all $h\in\mathcal{H}^{\mathcal{Z}_{2}}$ without a parent, their
parent in $\mathcal{Z}$ is $u_{i}$, and for all other $h$, their parents
remain the same as in $\mathcal{Z}_{1}$ or $\mathcal{Z}_{2}$. We denote by
$\sigma(h)$ the index of the parent variable of $h$, and let it be $0$ if $h$
has no parent. For convenience, we let $z_{0}=1$ for all $z\in\mathcal{Z}$ (so
that $z_{\sigma(h)}$ is always well-defined). Also define
$\mathcal{H}_{i}=\\{h\in\mathcal{H}^{\mathcal{Z}}:\sigma(h)=i\\}$ to be the
collection of simplexes whose parent index is $i$.

Similarly, for an index $i$, its parent index is defined as
$p_{i}=\sigma(h(i))$, and $i$ is called a _terminal index_ if it is not a
parent index (that is, $i\neq p_{j}$ for all $j$). Finally, for an element
${\bm{z}}\in\mathcal{Z}$ and an index $i$, we define $q_{i}=z_{i}/z_{p_{i}}$.
In EFG terminology, $q_{i}$ specifies the probability of selecting action $i$
in the information set $h(i)$ according to strategy ${\bm{z}}$.

##  4 Optimistic Regret-minimization Algorithms

There are many different algorithms for solving bilinear saddle-point problems
over general constrained sets. We focus specifically on a family of regret-
minimization algorithms, called Optimistic Online Mirror Descent (OOMD)
(Rakhlin and Sridharan, 2013), which are known to be highly efficient. In
contrast to the CFR algorithm and its variants, which minimize a local regret
notion at each information set (which upper bounds global regret), the
algorithms we consider explicitly minimize global regret. As our main results
in the next section show, these global regret-minimization algorithms enjoy
last-iterate convergence, while CFR provably diverges.

Specifically, given a step size $\eta>0$ and a convex function $\psi$ (called
a _regularizer_), OOMD sequentially performs the following update for
$t=1,2,\dots$,

$\displaystyle{\bm{x}}_{t}$
$\displaystyle=\operatorname*{argmin}_{{\bm{x}}\in{\mathcal{X}}}\Big{\\{}\eta\langle{\bm{x}},\bm{G}{\bm{y}}_{t-1}\rangle+D_{\psi}({\bm{x}},\widehat{\bm{x}}_{t})\Big{\\}},$
$\displaystyle\widehat{\bm{x}}_{t+1}$
$\displaystyle=\operatorname*{argmin}_{{\bm{x}}\in{\mathcal{X}}}\Big{\\{}\eta\langle{\bm{x}},\bm{G}{\bm{y}}_{t}\rangle+D_{\psi}({\bm{x}},\widehat{\bm{x}}_{t})\Big{\\}},$
$\displaystyle{\bm{y}}_{t}$
$\displaystyle=\operatorname*{argmin}_{{\bm{y}}\in{\mathcal{Y}}}\Big{\\{}\eta\langle{\bm{y}},-\bm{G}^{\top}{\bm{x}}_{t-1}\rangle+D_{\psi}({\bm{y}},\widehat{\bm{y}}_{t})\Big{\\}},$
$\displaystyle\widehat{\bm{y}}_{t+1}$
$\displaystyle=\operatorname*{argmin}_{{\bm{y}}\in{\mathcal{Y}}}\Big{\\{}\eta\langle{\bm{y}},-\bm{G}^{\top}{\bm{x}}_{t}\rangle+D_{\psi}({\bm{y}},\widehat{\bm{y}}_{t})\Big{\\}},$

with
$(\widehat{\bm{x}}_{1},\widehat{\bm{y}}_{1})=({\bm{x}}_{0},{\bm{y}}_{0})\in\mathcal{Z}$
being arbitrary. Using shorthands ${\bm{z}}_{t}=({\bm{x}}_{t},{\bm{y}}_{t})$,
$\widehat{\bm{z}}_{t}=(\widehat{\bm{x}}_{t},\widehat{\bm{y}}_{t})$,
$\psi({\bm{z}})=\psi({\bm{x}})+\psi({\bm{y}})$ and recalling the notation
$F({\bm{z}})=(\bm{G}{\bm{y}},-\bm{G}^{\top}{\bm{x}})$, the updates above can
be compactly written as OOMD with regularizer $\psi$ over treeplex
$\mathcal{Z}$:

$\displaystyle{\bm{z}}_{t}=\operatorname*{argmin}_{{\bm{z}}\in\mathcal{Z}}\Big{\\{}\eta\langle{\bm{z}},F({\bm{z}}_{t-1})\rangle+D_{\psi}({\bm{z}},\widehat{\bm{z}}_{t})\Big{\\}},~{}\,\widehat{\bm{z}}_{t+1}=\operatorname*{argmin}_{{\bm{z}}\in\mathcal{Z}}\Big{\\{}\eta\langle{\bm{z}},F({\bm{z}}_{t})\rangle+D_{\psi}({\bm{z}},\widehat{\bm{z}}_{t})\Big{\\}}.~{}$
(2)

Below, we discuss four different regularizers and their resulting algorithms
(throughout, we use notations $\Phi$ for regularizers based on Euclidean norm
and $\Psi$ for regularizers based on entropy).

##### Vanilla Optimistic Gradient Descent Ascent (VOGDA)

Define the vanilla squared Euclidean norm regularizer as
$\Phi^{\text{van}}({\bm{z}})=\frac{1}{2}\sum_{i}z_{i}^{2}$. We call OOMD
instantiated with $\psi=\Phi^{\text{van}}$ Vanilla Optimistic Gradient Descent
Ascent (VOGDA). In this case, the Bregman divergence is
$D_{\Phi^{\text{van}}}({\bm{z}},{\bm{z}}^{\prime})=\frac{1}{2}\|{\bm{z}}-{\bm{z}}^{\prime}\|^{2}$
(by definition $\Phi^{\text{van}}$ is thus $1$-strongly convex with respect to
the $2$-norm), and the updates simply become projected gradient descent. For
VOGDA there is no closed-form for Eq. (2), since projection onto the treeplex
$\mathcal{Z}$ is required. Nevertheless, the solution can still be computed in
$\mathcal{O}(P^{2}\log P)$ time (recall that $P$ is the dimension of
$\mathcal{Z}$) (Gilpin et al., 2008).

##### Vanilla Optimistic Multiplicative Weight Update (VOMWU)

Define the vanilla entropy regularizer as
$\Psi^{\text{van}}({\bm{z}})=\sum_{i}z_{i}\ln z_{i}$. We call OOMD with
$\psi=\Psi^{\text{van}}$ Vanilla Optimistic Multiplicative Weights Update
(VOMWU). The Bregman divergence in this case is the generalized KL divergence:
$D_{\Psi^{\text{van}}}({\bm{z}},{\bm{z}}^{\prime})=\sum_{i}z_{i}\ln(z_{i}/z_{i}^{\prime})-z_{i}+z_{i}^{\prime}$.
Although it is well-known that $\Psi^{\text{van}}$ is $1$-strongly convex with
respect to the $1$-norm for the special case when $\mathcal{Z}$ is a simplex,
this is not true generally on a treeplex. Nevertheless, it can still be shown
that $\Psi^{\text{van}}$ is 1-strongly convex with respect to the $2$-norm;
see Appendix C.

The name “Multiplicative Weights Update” is inherited from case when
${\mathcal{X}}$ and ${\mathcal{Y}}$ are simplexes, in which case the updates
in Eq. (2) have a simple multiplicative form. We emphasize, however, that in
general VOMWU does not admit a closed-form update. Instead, to solve Eq. (2),
one can equivalently solve a simpler dual optimization problem; see (Zimin and
Neu, 2013, Proposition 1).

The two regularizers mentioned above ignore the structure of the treeplex.
_Dilated Regularizers_ (Hoda et al., 2010), on the other hand, take the
structure into account and allow one to decompose the update into simpler
updates at each information set. Specifically, given any convex function
$\psi$ defined over the simplex and a weight parameter
${\bm{\alpha}}\in\mathbb{R}_{+}^{\mathcal{H}^{\mathcal{Z}}}$, the dilated
version of $\psi$ defined over $\mathcal{Z}$ is:

$\displaystyle\psi^{\text{dil}}_{{\bm{\alpha}}}({\bm{z}})=\sum_{h\in\mathcal{H}^{\mathcal{Z}}}\alpha_{h}\cdot
z_{{\sigma(h)}}\cdot\psi\left(\frac{{\bm{z}}_{h}}{z_{\sigma(h)}}\right).$ (3)

This is well-defined since $\nicefrac{{{\bm{z}}_{h}}}{{z_{\sigma(h)}}}$ is
indeed a distribution within the simplex $h$ (with $q_{i}$ for
$i\in\Omega_{h}$ being its entries). It can also be shown that
$\psi^{\text{dil}}_{{\bm{\alpha}}}$ is always convex in ${\bm{z}}$ (Hoda et
al., 2010). Intuitively, $\psi^{\text{dil}}_{{\bm{\alpha}}}$ applies the base
regularizer $\psi$ to the action distribution in each information set and then
scales the value by its parent variable and the weight $\alpha_{h}$. By
picking different base regularizers, we obtain the following two algorithms.

##### Dilated Optimistic Gradient Descent Ascent (DOGDA) (Farina et al.,
2019b)

Define the dilated squared Euclidean norm regularizer
$\Phi^{\text{dil}}_{{\bm{\alpha}}}$ as Eq. (3) with $\psi$ being the vanilla
squared Euclidean norm $\psi({\bm{z}})=\frac{1}{2}\sum_{i}z_{i}^{2}$. Direct
calculation shows
$\Phi^{\text{dil}}_{{\bm{\alpha}}}({\bm{z}})=\frac{1}{2}\sum_{i}\alpha_{h(i)}z_{i}q_{i}$.
We call OOMD with regularizer $\Phi^{\text{dil}}_{{\bm{\alpha}}}$ the Dilated
Optimistic Gradient Descent Ascent algorithm (DOGDA). It is known that there
exists an ${\bm{\alpha}}$ such that $\Phi^{\text{dil}}_{{\bm{\alpha}}}$ is
$1$-strongly convex with respect to the $2$-norm (Farina et al., 2019b).
Importantly, DOGDA decomposes the update Eq. (2) into simpler gradient
descent-style updates at each information set, as shown below.

######  Lemma 1 (Hoda et al. (2010)).

If
${\bm{z}}^{\prime}=\operatorname*{argmin}_{{\bm{z}}\in\mathcal{Z}}\left\\{\eta\langle{\bm{z}},\bm{f}\rangle+{D_{\Phi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}},\widehat{\bm{z}})}\right\\}$,
then for every $h\in\mathcal{H}^{\mathcal{Z}}$, the corresponding vector
${\bm{q}}_{h}^{\prime}=\frac{{\bm{z}}_{h}^{\prime}}{z_{\sigma(h)}^{\prime}}$
can be computed by:

$\displaystyle{\bm{q}}_{h}^{\prime}=\operatorname*{argmin}_{{\bm{q}}_{h}\in\Delta_{|\Omega_{h}|}}\left\\{\eta\langle{\bm{q}}_{h},\bm{L}_{h}\rangle+\frac{\alpha_{h}}{2}\|{\bm{q}}_{h}-\widehat{\bm{q}}_{h}\|^{2}\right\\},$
(4)

where
$\widehat{\bm{q}}_{h}=\frac{\widehat{\bm{z}}_{h}}{\widehat{\bm{z}}_{\sigma(h)}}$,
$\bm{L}_{h}$ is the slice of $\bm{L}$ whose entries are in $\Omega_{h}$, and
$\bm{L}$ is defined through:

$\displaystyle
L_{i}=f_{i}+\sum_{h\in\mathcal{H}_{i}}\left(\langle{\bm{q}}_{h}^{\prime},\bm{L}_{h}\rangle+\frac{\alpha_{h}}{2\eta}\|{\bm{q}}_{h}^{\prime}-\widehat{\bm{q}}_{h}\|^{2}\right).$

While the definitions of ${\bm{q}}_{h}^{\prime}$ and $\bm{L}$ are seemingly
recursive, one can verify that they can in fact be computed in a “bottom-up”
manner, starting with the terminal indices. Although Eq. (4) still does not
admit closed-form solution, it only requires projection onto a simplex, which
can be solved efficiently, see e.g. (Condat, 2016). Finally, with
${\bm{q}}_{h}^{\prime}$ computed for all $h$, ${\bm{z}}^{\prime}$ can be
calculated in a “top-down” manner by definition.

##### Dilated Optimistic Multiplicative Weight Update (DOMWU) (Kroer et al.,
2020)

Finally, define the dilated entropy regularizer
$\Psi^{\text{dil}}_{{\bm{\alpha}}}$ as Eq. (3) with $\psi$ being the vanilla
entropy $\psi({\bm{z}})=\sum_{i}z_{i}\ln z_{i}$. Direct calculation shows
$\Psi^{\text{dil}}_{{\bm{\alpha}}}({\bm{z}})=\sum_{i}\alpha_{h(i)}z_{i}\ln
q_{i}$. We call OOMD with regularizer $\Psi^{\text{dil}}_{{\bm{\alpha}}}$ the
Dilated Optimistic Multiplicative Weights Update algorithm (DOMWU). Similar to
DOGDA, there exists an ${\bm{\alpha}}$ such that
$\Psi^{\text{dil}}_{{\bm{\alpha}}}$ is $1$-strongly convex with respect to the
$2$-norm (Kroer et al., 2020).111Kroer et al. (2020) also show a better strong
convexity result with respect to the $1$-norm. We focus on the $2$-norm here
for consistency with our other results, but our analysis can be applied to the
$1$-norm case as well. Moreover, in contrast to all the three algorithms
mentioned above, the update of DOMWU has a closed-form solution:

######  Lemma 2 (Hoda et al. (2010)).

Suppose
${\bm{z}}^{\prime}=\operatorname*{argmin}_{{\bm{z}}\in\mathcal{Z}}\left\\{\eta\langle{\bm{z}},\bm{f}\rangle+{D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}},\widehat{\bm{z}})}\right\\}$.
Similarly to the notation $q_{i}$, define
$q^{\prime}_{i}=z^{\prime}_{i}/z^{\prime}_{p_{i}}$ and
$\widehat{q}_{i}=\widehat{z}_{i}/\widehat{z}_{p_{i}}$. Then we have

$\displaystyle q_{i}^{\prime}\propto\widehat{q}_{i}\exp\left(-\eta
L_{i}/\alpha_{h(i)}\right),~{}\text{where}~{}L_{i}=f_{i}-\sum_{h\in\mathcal{H}_{i}}\frac{\alpha_{h}}{\eta}\ln\left(\sum_{j\in\Omega_{h}}\widehat{q}_{j}\exp\left(-\eta
L_{j}/\alpha_{h}\right)\right).$

This lemma again implies that we can compute $q_{i}^{\prime}$ bottom-up, and
then ${\bm{z}}^{\prime}$ can be computed top-down. This is similar to DOGDA,
except that all updates have a closed-form.

##  5 Last-iterate Convergence Results

In this section, we present our main last-iterate convergence results for the
global regret-minimization algorithms discussed in Section 4. Before doing so,
we point out again that the sequence produced by the well-known CFR algorithm
may diverge (even if the average converges to a Nash equilibrium). Indeed,
this can happen even for a simple normal-form game, as formally shown below.

######  Theorem 3.

In the rock-paper-scissors game, CFR (with some particular initialization)
produces a diverging sequence.

In fact, we empirically observe that all of CFR, CFR+ (Tammelin, 2014) (with
simultaneous updates), and their optimistic versions (Farina et al., 2021a)
may diverge in the rock-paper-scissors game. We introduce the algorithms and
show the results in Appendix D.

On the contrary, every algorithm from the OOMD family given by Eq. (2) ensures
last-iterate convergence, as long as the regularizer is strongly convex and
continuously differentiable.

######  Theorem 4.

Consider the update rules in Eq. (2). Suppose that $\psi$ is $1$-strongly
convex with respect to the $2$-norm and continuously differentiable on the
entire domain, and $\eta\leq\frac{1}{8P}$. Then ${\bm{z}}_{t}$ converges to a
Nash equilibrium as $t\rightarrow\infty$.

As mentioned, $\Phi^{\text{van}}$ and $\Psi^{\text{van}}$ are both
$1$-strongly convex with respect to $2$-norm, so are
$\Phi^{\text{dil}}_{{\bm{\alpha}}}$ and $\Psi^{\text{dil}}_{{\bm{\alpha}}}$
under some specific choice of ${\bm{\alpha}}$ (in the rest of the paper, we
fix this choice of ${\bm{\alpha}}$). However, only $\Phi^{\text{van}}$ and
$\Phi^{\text{dil}}_{{\bm{\alpha}}}$ are continuously differentiable in the
entire domain. Therefore, Theorem 4 provides an asymptotic convergence result
only for VOGDA and DOGDA, but not VOMWU and DOMWU. Nevertheless, below, we
resort to different analyses to show a concrete last-iterate convergence rate
for three of our algorithms, which is a much more challenging task.

First of all, note that (Wei et al., 2021, Theorem 5, Theorem 8) already
provide a general last-iterate convergence rate for VOGDA over polytopes.
Since treeplexes are polytopes, we can directly apply their results and obtain
the following corollary.

######  Corollary 5.

Define
$\mathrm{dist}^{2}({\bm{z}},\mathcal{Z}^{*})=\min_{{\bm{z}}^{*}\in\mathcal{Z}^{*}}\|{\bm{z}}-{\bm{z}}^{*}\|^{2}$.
For $\eta\leq\frac{1}{8P}$, VOGDA guarantees

$\displaystyle\mathrm{dist}^{2}({\bm{z}}_{t},\mathcal{Z}^{*})\leq
64\mathrm{dist}^{2}(\widehat{\bm{z}}_{1},\mathcal{Z}^{*})(1+C_{1})^{-t},$

where $C_{1}>0$ is some constant that depends on the game and $\eta$.

However, the results for VOMWU in (Wei et al., 2021, Theorem 3) is very
specific to normal-form game (that is, when ${\mathcal{X}}$ and
${\mathcal{Y}}$ are simplexes) and thus cannot be applied here. Nevertheless,
we are able to extend their analysis to get the following result.

######  Theorem 6.

If the EFG has a unique Nash equilibrium ${\bm{z}}^{*}$, then VOMWU with step
size $\eta\leq\frac{1}{8P}$ guarantees
$\frac{1}{2}\|\widehat{\bm{z}}_{t}-{\bm{z}}^{*}\|^{2}\leq
D_{\Psi^{\text{van}}}({\bm{z}}^{*},\widehat{\bm{z}}_{t})\leq\frac{C_{2}}{t},$
where $C_{2}>0$ is some constant depending on the game,
$\widehat{\bm{z}}_{1}$, and $\eta$.

We note that the uniqueness assumption is often required in the analysis of
OMWU even for normal-form games (Daskalakis and Panageas, 2019; Wei et al.,
2021) (although (Wei et al., 2021, Appendix A.5) provides empirical evidence
to show that this may be an artifact of the analysis). Also note that for
normal-form games, (Wei et al., 2021, Theorem 3) show a linear convergence
rate, whereas here we only show a slower sub-linear rate, due to additional
complications introduced by treeplexes (see more discussions in the next
section). Whether this can be improved is left as a future direction.

On the other hand, thanks to the closed-form updates of DOMWU, we are able to
show the following linear convergence rate for this algorithm.

######  Theorem 7.

If the EFG has a unique Nash equilibrium ${\bm{z}}^{*}$, then DOMWU with step
size $\eta\leq\frac{1}{8P}$ guarantees
$\frac{1}{2}\|{\bm{z}}_{t}-{\bm{z}}^{*}\|^{2}\leq
D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}}^{*},{\bm{z}}_{t})\leq
C_{3}(1+C_{4})^{-t},$ where $C_{3},C_{4}>0$ are constants that depend on the
game, $\widehat{\bm{z}}_{1}$, and $\eta$.

To the best of our knowledge, this is the first last-iterate convergence
result for algorithms with dilated regularizers. Unfortunately, due to
technical difficulties, we were unable to prove similar results for DOGDA (see
Appendix E for more discussion). We leave that as an important future
direction.

##  6 Analysis Overview

In this section, we provide an overview of our analysis. It starts from the
following standard one-step regret analysis of OOMD (see, for example, (Wei et
al., 2021, Lemma 1)):

######  Lemma 8.

Consider the update rules in Eq. (2). Suppose that $\psi$ is 1-strongly convex
with respect to the $2$-norm, $\|F({\bm{z}}_{1})-F({\bm{z}}_{2})\|\leq
L\|{\bm{z}}_{1}-{\bm{z}}_{2}\|$ for all
${\bm{z}}_{1},{\bm{z}}_{2}\in\mathcal{Z}$ and some $L>0$, and
$\eta\leq\frac{1}{8L}$. Then for any ${\bm{z}}\in\mathcal{Z}$ and any $t\geq
1$, we have

$\displaystyle\eta F({\bm{z}}_{t})^{\top}({\bm{z}}_{t}-{\bm{z}})\leq
D_{\psi}({\bm{z}},\widehat{\bm{z}}_{t})-D_{\psi}({\bm{z}},\widehat{\bm{z}}_{t+1})-D_{\psi}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t})-\tfrac{15}{16}D_{\psi}({\bm{z}}_{t},\widehat{\bm{z}}_{t})+\tfrac{1}{16}D_{\psi}(\widehat{\bm{z}}_{t},{\bm{z}}_{t-1}).$

Note that the Lipschitz condition on $F$ holds in our case with $L=P$ since

$\|F({\bm{z}}_{1})-F({\bm{z}}_{2})\|=\sqrt{\|\bm{G}({\bm{y}}_{1}-{\bm{y}}_{2})\|^{2}+\|\bm{G}^{\top}({\bm{x}}_{1}-{\bm{x}}_{2})\|^{2}}\leq\sqrt{P\|{\bm{z}}_{1}-{\bm{z}}_{2}\|_{1}^{2}}\leq
P\|{\bm{z}}_{1}-{\bm{z}}_{2}\|,$

which is also why the step size is chosen to be $\eta\leq\frac{1}{8P}$ in all
our results. In the following, we first prove Theorem 4. Then, we review the
convergence analysis of (Wei et al., 2021) for OMWU in normal-form games, and
finally demonstrate how to prove Theorem 6 and Theorem 7 by building upon this
previous work and addressing the additional complications from EFGs.

###  6.1 Proof of Theorem 4

For any ${\bm{z}}^{*}\in\mathcal{Z}^{*}$, by optimality of ${\bm{z}}^{*}$ we
have:

$F({\bm{z}}_{t})^{\top}({\bm{z}}_{t}-{\bm{z}}^{*})={\bm{x}}_{t}^{\top}\bm{G}{\bm{y}}_{t}-{\bm{x}}_{t}^{\top}\bm{G}{\bm{y}}_{t}+{\bm{x}}_{t}^{\top}\bm{G}{\bm{y}}^{*}-{{\bm{x}}^{*}}^{\top}\bm{G}{\bm{y}}_{t}\geq{{\bm{x}}^{*}}^{\top}\bm{G}{\bm{y}}^{*}-{{\bm{x}}^{*}}^{\top}\bm{G}{\bm{y}}^{*}=0.$

Thus, taking ${\bm{z}}={\bm{z}}^{*}$ in Lemma 8 and rearranging, we arrive at

$\displaystyle D_{\psi}({\bm{z}}^{*},\widehat{\bm{z}}_{t+1})\leq
D_{\psi}({\bm{z}}^{*},\widehat{\bm{z}}_{t})-D_{\psi}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t})-\tfrac{15}{16}D_{\psi}({\bm{z}}_{t},\widehat{\bm{z}}_{t})+\tfrac{1}{16}D_{\psi}(\widehat{\bm{z}}_{t},{\bm{z}}_{t-1}).$

Defining
$\Theta_{t}=D_{\psi}({\bm{z}}^{*},\widehat{\bm{z}}_{t})+\tfrac{1}{16}D_{\psi}(\widehat{\bm{z}}_{t},{\bm{z}}_{t-1})$
and
$\zeta_{t}=D_{\psi}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t})+D_{\psi}({\bm{z}}_{t},\widehat{\bm{z}}_{t})$,
we rewrite the inequality above as

$\displaystyle\Theta_{t+1}\leq\Theta_{t}-\tfrac{15}{16}\zeta_{t}.$ (5)

We remark that similar inequalities appear in (Wei et al., 2021, Eq. (3) and
Eq. (4)), but here we pick ${\bm{z}}^{*}\in\mathcal{Z}^{*}$ arbitrarily while
they have to pick a particular ${\bm{z}}^{*}\in\mathcal{Z}^{*}$ (such as the
projection of $\widehat{\bm{z}}_{t}$ onto $\mathcal{Z}^{*}$). Summing Eq. (5)
over $t$, telescoping, and applying the strong convexity of $\psi$, we have

$\displaystyle\Theta_{1}\geq\Theta_{1}-\Theta_{T}\geq\frac{15}{16}\sum^{T-1}_{t=1}\zeta_{t}\geq\frac{15}{32}\sum^{T-1}_{t=1}\|\widehat{\bm{z}}_{t+1}-{\bm{z}}_{t}\|^{2}+\|{\bm{z}}_{t}-\widehat{\bm{z}}_{t}\|^{2}\geq\frac{15}{64}\sum^{T-1}_{t=2}\|{\bm{z}}_{t}-{\bm{z}}_{t-1}\|^{2}.$

Similar to the last inequality, we also have
$\Theta_{1}\geq\frac{15}{64}\sum^{T-1}_{t=1}\|\widehat{\bm{z}}_{t+1}-\widehat{\bm{z}}_{t}\|^{2}$
since
$2\|\widehat{\bm{z}}_{t+1}-{\bm{z}}_{t}\|^{2}+2\|{\bm{z}}_{t}-\widehat{\bm{z}}_{t}\|^{2}\geq\|\widehat{\bm{z}}_{t+1}-\widehat{\bm{z}}_{t}\|^{2}$.
Therefore, we conclude that $\|{\bm{z}}_{t}-\widehat{\bm{z}}_{t}\|$,
$\|{\bm{z}}_{t+1}-{\bm{z}}_{t}\|$, and
$\|\widehat{\bm{z}}_{t+1}-\widehat{\bm{z}}_{t}\|$ all converge to $0$ as
$t\to\infty$. On the other hand, since the sequence
$\\{{\bm{z}}_{1},{\bm{z}}_{2},\ldots,\\}$ is bounded, by the Bolzano-
Weierstrass theorem, there exists a convergent subsequence, which we denote by
$\\{{\bm{z}}_{i_{1}},{\bm{z}}_{i_{2}},\ldots,\\}$. Let
${\bm{z}}_{\infty}=\lim_{\tau\to\infty}{\bm{z}}_{i_{\tau}}$. By
$\|\widehat{\bm{z}}_{t}-{\bm{z}}_{t}\|\to 0$ we also have
${\bm{z}}_{\infty}=\lim_{\tau\to\infty}\widehat{\bm{z}}_{i_{\tau}}$. Now,
using the first-order optimality condition of $\widehat{\bm{z}}_{t+1}$, we
have for every ${\bm{z}}^{\prime}\in\mathcal{Z}$,

$(\nabla\psi(\widehat{\bm{z}}_{t+1})-\nabla\psi(\widehat{\bm{z}}_{t})+\eta
F({\bm{z}}_{t}))^{\top}({\bm{z}}^{\prime}-\widehat{\bm{z}}_{t+1})\geq 0.$

Apply this with $t=i_{\tau}$ for every $\tau$ and let $\tau\to\infty$, we
obtain

$\displaystyle 0\leq$
$\displaystyle\lim_{\tau\to\infty}(\nabla\psi(\widehat{\bm{z}}_{i_{\tau}+1})-\nabla\psi(\widehat{\bm{z}}_{i_{\tau}})+\eta
F({\bm{z}}_{i_{\tau}}))^{\top}({\bm{z}}^{\prime}-\widehat{\bm{z}}_{i_{\tau}+1})$
(by the first-order optimality) $\displaystyle=$
$\displaystyle\lim_{\tau\to\infty}\eta
F({\bm{z}}_{i_{\tau}})^{\top}({\bm{z}}^{\prime}-\widehat{\bm{z}}_{i_{\tau}+1})$
(by $\|\widehat{\bm{z}}_{t+1}-\widehat{\bm{z}}_{t}\|\to 0$ and the continuity
of $\nabla\psi$) $\displaystyle=$ $\displaystyle~{}\eta
F({\bm{z}}_{\infty})^{\top}({\bm{z}}^{\prime}-{\bm{z}}_{\infty})$ (by
${\bm{z}}_{\infty}=\lim_{\tau\to\infty}{\bm{z}}_{i_{\tau}}=\lim_{\tau\to\infty}\widehat{\bm{z}}_{i_{\tau}}$)

This implies that ${\bm{z}}_{\infty}$ is a Nash equilibrium. Finally, choosing
${\bm{z}}^{*}={\bm{z}}_{\infty}$ in the definition of $\Theta_{t}$, we have
$\lim_{\tau\to\infty}\Theta_{i_{\tau}}=0$ because
$\lim_{\tau\to\infty}D_{\psi}({\bm{z}}_{\infty},\widehat{\bm{z}}_{{i_{\tau}}})=0$
and
$\lim_{\tau\to\infty}\|\widehat{\bm{z}}_{{i_{\tau}}}-{\bm{z}}_{{i_{\tau}}-1}\|=0$.
Additionally, by Eq. (5) we also have that $\lim_{t\to\infty}\Theta_{t}=0$ as
$\Theta_{t}$ is non-increasing. Therefore, we conclude that the entire
sequence $\\{{\bm{z}}_{1},{\bm{z}}_{2},\ldots\\}$ converges to
${\bm{z}}_{\infty}$. On the other hand, since OOMD is a regret-minimization
algorithm, it is well known that the average iterate converges to a Nash
equilibrium (Freund and Schapire, 1999). Consequently, combining the two facts
above implies that ${\bm{z}}_{t}$ has to converge to a Nash equilibrium, which
proves Theorem 4.

We remark that Lemma 8 holds for general closed convex domains as shown in
(Wei et al., 2021). Consequently, with the same argument, Theorem 4 holds more
generally as long as ${\mathcal{X}}$ and ${\mathcal{Y}}$ are closed convex
sets. While the argument is straightforward, we are not aware of similar
results in prior works. Also note that unlike Theorem 6 and Theorem 7, Theorem
4 holds without the uniqueness assumption for VOMWU and DOMWU.

###  6.2 Review for normal-form games

To better explain our analysis and highlight its novelty, we first review the
two-stage analysis of (Wei et al., 2021) for OMWU in normal-form games, a
special case of our setting when ${\mathcal{X}}$ and ${\mathcal{Y}}$ are
simplexes. Note that both VOMWU and DOMWU reduce to OMWU in this case. As with
Theorem 6 and Theorem 7, the normal-form OMWU results assume a unique Nash
equilibrium ${\bm{z}}^{*}$. With this uniqueness assumption and (Mertikopoulos
et al., 2018, Lemma C.4), Wei et al. (2021) show the following inequality

$\displaystyle\zeta_{t}=D_{\psi}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t})+D_{\psi}({\bm{z}}_{t},\widehat{\bm{z}}_{t})\geq
C_{5}\|{\bm{z}}^{*}-\widehat{\bm{z}}_{t+1}\|^{2}$ (6)

for some problem-dependent constant $C_{5}>0$, which, when combined with Eq.
(5), implies that if the algorithm’s current iterate is far from
${\bm{z}}^{*}$, then the decrease in $\Theta_{t}$ is more substantial, that
is, the algorithm makes more progress on approaching ${\bm{z}}^{*}$. To
establish a recursion, however, we need to connect the $2$-norm back to the
Bregman divergence (a reverse direction of strong convexity). To do so, Wei et
al. (2021) argue that $\widehat{\bm{z}}_{t+1,i}$ can be lower bounded by
another problem-dependent constant for $i\in\text{supp}({\bm{z}}^{*})$ (Wei et
al., 2021, Lemma 19), where $\text{supp}({\bm{z}}^{*})$ denotes the support of
${\bm{z}}^{*}$. This further allows them to lower bound
$\|{\bm{z}}^{*}-\widehat{\bm{z}}_{t+1}\|$ in terms of
$D_{\psi}({\bm{z}}^{*},\widehat{\bm{z}}_{t+1})$ (which is just $\text{\rm
KL}({\bm{z}}^{*},\widehat{\bm{z}}_{t+1})$), leading to

$\displaystyle\zeta_{t}=D_{\psi}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t})+D_{\psi}({\bm{z}}_{t},\widehat{\bm{z}}_{t})\geq
C_{6}D_{\psi}({\bm{z}}^{*},\widehat{\bm{z}}_{t+1})^{2},$ (7)

for some $C_{6}>0$. On the other hand, ignoring the nonnegative term
$D_{\psi}({\bm{z}}_{t},\widehat{\bm{z}}_{t})$, we also have:

$\displaystyle\zeta_{t}=D_{\psi}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t})+D_{\psi}({\bm{z}}_{t},\widehat{\bm{z}}_{t})\geq
D_{\psi}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t})\geq\frac{1}{4}D_{\psi}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t})^{2},$
(8)

where the last step uses the fact that $\widehat{\bm{z}}_{t+1}$ and
${\bm{z}}_{t}$ are close (Wei et al., 2021, Lemma 17 and Lemma 18). Now, Eq.
(7) and Eq. (8) together imply
$6\zeta_{t}\geq{2C_{6}D_{\psi}({\bm{z}}^{*},\widehat{\bm{z}}_{t+1})^{2}}+{D_{\psi}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t})^{2}}\geq\min\left\\{{C_{6}},\frac{1}{2}\right\\}\Theta_{t+1}^{2}.$
Plugging this back into Eq. (5), we obtain a recursion

$\displaystyle\Theta_{t+1}\leq\Theta_{t}-C_{7}\Theta_{t+1}^{2}$ (9)

for some $C_{7}>0$, which then implies $\Theta_{t}=O(1/t)$ (Wei et al., 2021,
Lemma 12). This can be seen as the first and slower stage of the convergence
behavior of the algorithm.

To further show a linear convergence rate, they argue that there exists a
constant $C_{8}>0$ such that when the algorithm’s iterate is reasonably close
to ${\bm{z}}^{*}$ in the following sense:

$\displaystyle\max\\{\|{\bm{z}}^{*}-\widehat{\bm{z}}_{t}\|_{1},\|{\bm{z}}^{*}-{\bm{z}}_{t}\|_{1}\\}\leq
C_{8},$ (10)

the following improved version of Eq. (7) holds (note the lack of square on
the right-hand side):

$\displaystyle\zeta_{t}=D_{\psi}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t})+D_{\psi}({\bm{z}}_{t},\widehat{\bm{z}}_{t})\geq
C_{9}D_{\psi}({\bm{z}}^{*},\widehat{\bm{z}}_{t+1})$ (11)

for some constant $0<C_{9}<1$. Therefore, using the $1/t$ convergence rate
derived in the first stage, there exists a $T_{0}$ such that when $t\geq
T_{0}$, Eq. (10) holds and the algorithm enters the second stage. In this
stage, combining Eq. (11) and the fact $\zeta_{t}\geq
D_{\psi}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t})$ gives
$\zeta_{t}\geq\frac{C_{9}}{2}\Theta_{t+1}$, which, together with Eq. (5)
again, implies an improved recursion
$\Theta_{t+1}\leq\Theta_{t}-\frac{15}{32}C_{9}\Theta_{t+1}$. This finally
shows a linear convergence rate $\Theta_{t}=O((1+\rho)^{-t})$ for some
problem-dependent constant $\rho>0$.

###  6.3 Analysis of Theorem 6 and Theorem 7

While we mainly follow the steps of the analysis of (Wei et al., 2021)
discussed above to prove Theorem 6 and Theorem 7, we remark that the
generalization is highly non-trivial. First of all, we have to prove Eq. (6)
for $\mathcal{Z}$ being a general treeplex, which does not follow
(Mertikopoulos et al., 2018, Lemma C.4) since its proof is very specific to
simplexes. Instead, we prove it by writing down the primal-dual linear program
of Eq. (1) and applying the strict complementary slackness; see Appendix E.1
for details.

Next, to connect the $2$-norm back to the Bregman divergence (which is not the
simple KL divergence anymore, especially for DOMWU), we prove the following
for VOMWU:

$\displaystyle D_{\psi}({\bm{z}}^{*},\widehat{\bm{z}}_{t+1})$
$\displaystyle\leq\sum_{i\in\text{supp}({\bm{z}}^{*})}\frac{(z^{*}_{i}-\widehat{z}_{t+1,i})^{2}}{\widehat{z}_{t+1,i}}+\sum_{i\notin\text{supp}({\bm{z}}^{*})}\widehat{z}_{t+1,i}\leq\frac{3P\|{\bm{z}}^{*}-\widehat{\bm{z}}_{t+1}\|}{\min_{i\in\text{supp}({\bm{z}}^{*})}\widehat{z}_{t+1,i}},$
(12)

and the following for DOMWU:

$\displaystyle\frac{D_{\psi}({\bm{z}}^{*},\widehat{\bm{z}}_{t+1})}{C^{\prime}}\leq\sum_{i\in\text{supp}({\bm{z}}^{*})}\frac{\left({z^{*}_{i}-\widehat{z}_{t+1,i}}\right)^{2}}{z_{i}^{*}\widehat{q}_{t+1,i}}+\sum_{i\notin\text{supp}({\bm{z}}^{*})}z_{p_{i}}^{*}\widehat{q}_{t+1,i}\leq\frac{\|{\bm{z}}^{*}-\widehat{\bm{z}}_{t+1}\|_{1}}{\min_{i\in\text{supp}({\bm{z}}^{*})}z_{i}^{*}\widehat{z}_{t+1,i}},$
(13)

where $C^{\prime}=4P\|{\bm{\alpha}}\|_{\infty}$ (see Appendix E.2). We then
show a lower bound on $z_{t+1,i}$ and $\widehat{z}_{t+1,i}$ for all
$i\in\text{supp}(z^{*})$, using similar arguments of (Wei et al., 2021) (see
Appendix E.3). Combining Eq. (12) and Eq. (13) with Eq. (6), we have the
counterpart of Eq. (7) for both VOMWU and DOMWU.

Showing Eq. (8) also involves extra complication if we follow their analysis,
especially for VOMWU which does not admit a closed-form update. Instead, we
find a simple workaround: by applying Eq. (5) repeatedly, we get
$D_{\psi}({\bm{z}}^{*},\widehat{\bm{z}}_{1})=\Theta_{1}\geq\cdots\geq\Theta_{t+1}\geq\frac{1}{16}D_{\psi}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t}),$
thus, $\zeta_{t}\geq D_{\psi}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t})\geq
C_{10}D_{\psi}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t})^{2}$ for some $C_{10}>0$
depending on $D_{\psi}({\bm{z}}^{*},\widehat{\bm{z}}_{1})$. Combining this
with Eq. (7), and applying them to Eq. (5), we obtain the recursion
$\Theta_{t+1}\leq\Theta_{t}-C_{11}\Theta_{t+1}^{2}$ for some $C_{11}>0$
similar to Eq. (9), which implies $\Theta_{t}=O(1/t)$ for both VOMWU and DOMWU
and proves Theorem 6.

Finally, to show a linear convergence rate, we need to show the counterpart of
Eq. (11), which is again more involved compared to the normal-form game case.
Indeed, we are only able to do so for DOMWU by making use of its closed-form
update described in Lemma 2. Specifically, observe that in Eq. (13), the term
$\sum_{i\notin\text{supp}({\bm{z}}^{*})}z_{p_{i}}^{*}\widehat{q}_{t+1,i}$ is
the one that prevents us from bounding
$D_{\psi}({\bm{z}}^{*},\widehat{\bm{z}}_{t+1})$ by
$\mathcal{O}(\|{\bm{z}}^{*}-\widehat{\bm{z}}_{t+1}\|^{2})$. Thus, our high-
level idea is to argue that
$\sum_{i\notin\text{supp}({\bm{z}}^{*})}z_{p_{i}}^{*}\widehat{q}_{t+1,i}$
decreases significantly as $\widehat{\bm{z}}_{t}$ gets close enough to
${\bm{z}}^{*}$. To do so, we use a bottom-up induction to prove that, for any
information set $h\in\mathcal{H}^{\mathcal{Z}}$, indices $i,j\in\Omega_{h}$
such that $i\notin\text{supp}({\bm{z}}^{*})$ and
$j\in\text{supp}({\bm{z}}^{*})$, $\widehat{L}_{t,i}$ is significantly larger
than $\widehat{L}_{t,j}$ when $\widehat{\bm{z}}_{t}$ is close to
${\bm{z}}^{*}$, where $\widehat{\bm{L}}_{t}$ is the counterpart of $\bm{L}$ in
Lemma 2 when computing of $\widehat{\bm{q}}_{t+1}$. This makes sure that the
term $\sum_{i\notin\text{supp}({\bm{z}}^{*})}z_{p_{i}}^{*}\widehat{q}_{t+1,i}$
is dominated by the other term involving $i\in\text{supp}({\bm{z}}^{*})$ in
Eq. (13), which eventually helps us show Eq. (11) and the final linear
convergence rate in Theorem 7. See Appendix E.5 for details.

##  7 Experiments

Figure 1: Experiments on Kuhn poker (left), Pursuit-evasion (middle), and
Leduc poker (right). A description of each game is given in Appendix B.
$\xi_{t}=\max_{{\bm{y}}}\overline{{\bm{x}}}_{t}^{\top}\bm{G}{\bm{y}}-\min_{{\bm{x}}}{\bm{x}}^{\top}\bm{G}\overline{{\bm{y}}}_{t}$
is the duality gap at time step $t$, where
$(\overline{{\bm{x}}}_{t},\overline{{\bm{y}}}_{t})$ is the approximate Nash
equilibrium computed by the algorithm at time $t$ (for the optimistic
algorithms, $(\overline{{\bm{x}}}_{t},\overline{{\bm{y}}}_{t})$ is
$({{\bm{x}}}_{t},{{\bm{y}}}_{t})$ while for the CFR-based algorithms,
$(\overline{{\bm{x}}}_{t},\overline{{\bm{y}}}_{t})$ is the linear average).
The legend order reflects the curve order at the right-most point. Due to much
higher computation overhead than all the other algorithms, we only run VOMWU
on Kuhn poker, the game with the smallest size among the three games. For each
optimistic algorithm, we fine-tune step size $\eta$ to get better convergence
results and show its value in the legends. There is no hyperparameter for the
CFR-based algorithms. All the experiments are run on CPU in a personal
computer and the total computation time is less than an hour. There is no
random seed and the results are all deterministic.

In this section, we experimentally evaluate the algorithms on three standard
EFG benchmarks: Kuhn poker (Kuhn, 1950), Pursuit-evasion (Kroer et al., 2018),
and Leduc poker (Southey et al., 2005). The results are shown in Figure 1.
Besides the optimistic algorithms, we also show two CFR-based algorithms as
reference points. “CFR+” refers to CFR with alternating updates, linear
averaging (Tammelin, 2014), and regret matching+ as the regret minimizer. “CFR
w/ RM+” is CFR with regret matching+ and linear averaging. We provide the
formal descriptions of these two algorithms in Appendix D for completeness.
For the optimistic algorithms, we plot the last iterate performance. For the
CFR-based algorithms, we plot the performance of the linear average of
iterates (recall that the last iterate of CFR-based algorithms is not
guaranteed to converge to a Nash equilibrium).

For Kuhn poker and Pursuit-evasion (on the left and in the middle of Figure
1), all of the optimistic algorithms perform much better than CFR+, and their
curves are nearly straight, showing their linear last-iterate convergence on
these games.

For Leduc poker, although CFR+ performs the best, we can still observe the
last-iterate convergence trends of the optimistic algorithms. We remark that
although VOGDA and DOMWU have linear convergence rate in theory, the
experiment on Leduc uses a step size $\eta$ which is much larger than
Corollary 5 and Theorem 7 suggest, which may void the linear convergence
guarantee. This is done because the theoretical step size takes too many
iterations before it starts to show improvement. It is worth noting that CFR+
improves significantly when changing simultaneous updates (that is, CFR w/
RM+) to alternating updates. Analyzing alternation and combining it with
optimistic algorithms is a promising direction. We provide a description of
each game, more discussions, and details of the experiments in Appendix B.

##  8 Conclusions

In this work, we developed the first general last-iterate convergence results
for solving EFGs. Our paper opens up many potential future directions. The
recent dilatable global entropy regularizer of Farina et al. (2021b) can
likely be analyzed using techniques similar to our analysis of VOMWU and
DOMWU, and it would likely lead to a linear rate as with DOMWU, due to its
closed-form DOMWU-style update. Other natural questions include whether it is
possible to obtain better convergence rates for VOMWU and DOGDA, whether one
can remove the uniqueness assumption for VOMWU and DOMWU, and finally whether
it is possible to obtain last-iterate convergence rates for CFR-like
optimistic algorithms such as those in (Farina et al., 2021a). On the
practical side, optimistic algorithms with last-iterate convergence guarantees
may allow more efficient computation and better incorporation with deep
learning-based game-solving approaches.

## Acknowledgments and Disclosure of Funding

CWL and HL are supported by NSF Award IIS-1943607.

## References

  * Bailey and Piliouras (2018) James P Bailey and Georgios Piliouras.  Multiplicative weights update in zero-sum games.  In _Proceedings of the 2018 ACM Conference on Economics and Computation_ , 2018.
  * Bowling et al. (2015) Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin.  Heads-up limit hold’em poker is solved.  _Science_ , 347(6218):145–149, 2015.
  * Brown (1951) George W Brown.  Iterative solution of games by fictitious play.  _Activity analysis of production and allocation_ , 13(1):374–376, 1951.
  * Brown and Sandholm (2018) Noam Brown and Tuomas Sandholm.  Superhuman AI for heads-up no-limit poker: Libratus beats top professionals.  _Science_ , 359(6374):418–424, 2018.
  * Brown and Sandholm (2019a) Noam Brown and Tuomas Sandholm.  Solving imperfect-information games via discounted regret minimization.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pages 1829–1836, 2019a.
  * Brown and Sandholm (2019b) Noam Brown and Tuomas Sandholm.  Superhuman AI for multiplayer poker.  _Science_ , 365(6456):885–890, 2019b.
  * Brown et al. (2015) Noam Brown, Sam Ganzfried, and Tuomas Sandholm.  Hierarchical abstraction, distributed equilibrium computation, and post-processing, with application to a champion no-limit texas hold’em agent.  In _AAAI Workshop: Computer Poker and Imperfect Information_ , 2015\.
  * Brown et al. (2019) Noam Brown, Adam Lerer, Sam Gross, and Tuomas Sandholm.  Deep counterfactual regret minimization.  In _International conference on machine learning_ , pages 793–802. PMLR, 2019.
  * Burch (2018) Neil Burch.  _Time and space: Why imperfect information games are hard_.  PhD thesis, University of Alberta, 2018.
  * Burch et al. (2014) Neil Burch, Michael Johanson, and Michael Bowling.  Solving imperfect information games using decomposition.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 28, 2014.
  * Burch et al. (2019) Neil Burch, Matej Moravcik, and Martin Schmid.  Revisiting CFR+ and alternating updates.  _Journal of Artificial Intelligence Research_ , 64:429–443, 2019.
  * Condat (2016) Laurent Condat.  Fast projection onto the simplex and the $\ell_{1}$ ball.  _Mathematical Programming_ , 158(1):575–585, 2016\.
  * Daskalakis and Panageas (2019) Constantinos Daskalakis and Ioannis Panageas.  Last-iterate convergence: Zero-sum games and constrained min-max optimization.  _Innovations in Theoretical Computer Science_ , 2019.
  * Daskalakis et al. (2018) Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng.  Training gans with optimism.  In _International Conference on Learning Representations_ , 2018.
  * Farina et al. (2019a) Gabriele Farina, Christian Kroer, Noam Brown, and Tuomas Sandholm.  Stable-predictive optimistic counterfactual regret minimization.  In _International conference on machine learning_ , pages 1853–1862. PMLR, 2019a.
  * Farina et al. (2019b) Gabriele Farina, Christian Kroer, and Tuomas Sandholm.  Optimistic regret minimization for extensive-form games via dilated distance-generating functions.  In _Advances in Neural Information Processing Systems_ , pages 5222–5232, 2019b.
  * Farina et al. (2021a) Gabriele Farina, Christian Kroer, and Tuomas Sandholm.  Faster game solving via predictive Blackwell approachability: Connecting regret matching and mirror descent.  In _Proceedings of the AAAI Conference on Artificial Intelligence_. AAAI, 2021a.
  * Farina et al. (2021b) Gabriele Farina, Christian Kroer, and Tuomas Sandholm.  Better regularization for sequential decision spaces: Fast convergence rates for nash, correlated, and team equilibria.  In _Proceedings of the 2021 ACM Conference on Economics and Computation_ , 2021b.
  * Freund and Schapire (1999) Yoav Freund and Robert E Schapire.  Adaptive game playing using multiplicative weights.  _Games and Economic Behavior_ , 29(1-2):79–103, 1999.
  * Ganzfried and Sandholm (2014) Sam Ganzfried and Tuomas Sandholm.  Potential-aware imperfect-recall abstraction with earth mover’s distance in imperfect-information games.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 28, 2014.
  * Ganzfried and Sandholm (2015) Sam Ganzfried and Tuomas Sandholm.  Endgame solving in large imperfect-information games.  In _Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems_ , pages 37–45. Citeseer, 2015.
  * Gao et al. (2021) Yuan Gao, Christian Kroer, and Donald Goldfarb.  Increasing iterate averaging for solving saddle-point problems.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , 2021.
  * Gilpin et al. (2008) Andrew Gilpin, Javier Peña, and Tuomas Sandholm.  First-order algorithm with $\mathcal{O}(\mathrm{ln}(1/\epsilon))$ convergence for $\epsilon$-equilibrium in two-person zero-sum games.  In _AAAI_ , 2008.
  * Goodfellow et al. (2014) Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  In _Advances in neural information processing systems_ , 2014.
  * Hart and Mas-Colell (2000) Sergiu Hart and Andreu Mas-Colell.  A simple adaptive procedure leading to correlated equilibrium.  _Econometrica_ , 68(5):1127–1150, 2000.
  * Heinrich and Silver (2016) Johannes Heinrich and David Silver.  Deep reinforcement learning from self-play in imperfect-information games.  _arXiv preprint arXiv:1603.01121_ , 2016.
  * Hoda et al. (2010) Samid Hoda, Andrew Gilpin, Javier Pena, and Tuomas Sandholm.  Smoothing techniques for computing nash equilibria of sequential games.  _Mathematics of Operations Research_ , 35(2):494–512, 2010.
  * Kroer and Sandholm (2014) Christian Kroer and Tuomas Sandholm.  Extensive-form game abstraction with bounds.  In _Proceedings of the fifteenth ACM conference on Economics and computation_ , pages 621–638, 2014.
  * Kroer et al. (2017) Christian Kroer, Gabriele Farina, and Tuomas Sandholm.  Smoothing method for approximate extensive-form perfect equilibrium.  In _Proceedings of the 26th International Joint Conference on Artificial Intelligence_ , pages 295–301, 2017.
  * Kroer et al. (2018) Christian Kroer, Gabriele Farina, and Tuomas Sandholm.  Robust stackelberg equilibria in extensive-form games and extension to limited lookahead.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32, 2018.
  * Kroer et al. (2020) Christian Kroer, Kevin Waugh, Fatma Kılınç-Karzan, and Tuomas Sandholm.  Faster algorithms for extensive-form game solving via improved smoothing functions.  _Mathematical Programming_ , 179(1):385–417, 2020\.
  * Kuhn (1950) HW Kuhn.  Simplified two-person poker.  _Contributions to the Theory of Games_ , pages 97–103, 1950.
  * Lanctot et al. (2009) Marc Lanctot, Kevin Waugh, Martin Zinkevich, and Michael H Bowling.  Monte carlo sampling for regret minimization in extensive games.  In _NIPS_ , pages 1078–1086, 2009.
  * Lei et al. (2021) Qi Lei, Sai Ganesh Nagarajan, Ioannis Panageas, and Xiao Wang.  Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes.  _The 24nd International Conference on Artificial Intelligence and Statistics_ , 2021.
  * McMahan et al. (2003) H Brendan McMahan, Geoffrey J Gordon, and Avrim Blum.  Planning in the presence of cost functions controlled by an adversary.  In _Proceedings of the 20th International Conference on Machine Learning (ICML-03)_ , pages 536–543, 2003.
  * Mertikopoulos et al. (2018) Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras.  Cycles in adversarial regularized learning.  In _Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms_ , 2018.
  * Mertikopoulos et al. (2019) Panayotis Mertikopoulos, Houssam Zenati, Bruno Lecouat, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras.  Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile.  In _International Conference on Learning Representations_ , 2019.
  * Moravcik et al. (2016) Matej Moravcik, Martin Schmid, Karel Ha, Milan Hladik, and Stephen Gaukrodger.  Refining subgames in large imperfect information games.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 30, 2016.
  * Moravčík et al. (2017) Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisỳ, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling.  Deepstack: Expert-level artificial intelligence in heads-up no-limit poker.  _Science_ , 356(6337):508–513, 2017.
  * Nisan et al. (2007) Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V Vazirani.  _Algorithmic Game Theory_.  Cambridge University Press, 2007.
  * Rakhlin and Sridharan (2013) Sasha Rakhlin and Karthik Sridharan.  Optimization, learning, and games with predictable sequences.  In _Advances in Neural Information Processing Systems_ , pages 3066–3074, 2013.
  * Southey et al. (2005) Finnegan Southey, Michael Bowling, Bryce Larson, Carmelo Piccione, Neil Burch, Darse Billings, and Chris Rayner.  Bayes’ bluff: opponent modelling in poker.  In _Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence_ , pages 550–558, 2005.
  * Syrgkanis et al. (2015) Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire.  Fast convergence of regularized learning in games.  In _Advances in Neural Information Processing Systems_ , 2015.
  * Tammelin (2014) Oskari Tammelin.  Solving large imperfect information games using CFR+.  _arXiv preprint arXiv:1407.5042_ , 2014.
  * Tseng (1995) Paul Tseng.  On linear convergence of iterative methods for the variational inequality problem.  In _Journal of Computational and Applied Mathematics_ , 1995.
  * Vanderbei et al. (2015) Robert J Vanderbei et al.  _Linear programming_ , volume 3.  Springer, 2015.
  * von Stengel (1996) Bernhard von Stengel.  Efficient computation of behavior strategies.  _Games and Economic Behavior_ , 14(2):220–246, 1996.
  * Wei et al. (2021) Chen-Yu Wei, Chung-Wei Lee, Mengxiao Zhang, and Haipeng Luo.  Linear last-iterate convergence in constrained saddle-point optimization.  In _International Conference on Learning Representations_ , 2021.
  * Zimin and Neu (2013) Alexander Zimin and Gergely Neu.  Online learning in episodic Markovian decision processes by relative entropy policy search.  In _Neural Information Processing Systems 26_ , 2013.
  * Zinkevich (2003) Martin Zinkevich.  Online convex programming and generalized infinitesimal gradient ascent.  In _Proceedings of the 20th international conference on machine learning (icml-03)_ , pages 928–936, 2003.
  * Zinkevich et al. (2007) Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione.  Regret minimization in games with incomplete information.  _Advances in neural information processing systems_ , 20:1729–1736, 2007.

##  Appendix A Examples of EFG and Treeplexes

In this section, we introduce Kuhn poker [Kuhn, 1950], a simple EFG as an
example to introduce treeplexes and the corresponding definitions. In this
game, there are three cards in the deck: King, Queen, and Jack. Both player
${\bm{x}}$ and player ${\bm{y}}$ are dealt one card, while the third card is
put aside unseen. In the first round, player ${\bm{x}}$ can bet or check.
Then, if player ${\bm{x}}$ bets player ${\bm{y}}$ can choose to call or fold.
If player ${\bm{x}}$ checks then player ${\bm{y}}$ can bet or check. Finally,
if player ${\bm{x}}$ checks and player ${\bm{y}}$ bets, then player ${\bm{x}}$
has a final round where they can call or fold. If neither player folded, then
the player with the higher card wins the pot. If a player folded then the
other player wins the pot.

We show a game tree of Kuhn poker in Figure 2. Players’ imperfect information
is modeled by information sets. In Figure 2, nodes with the same color belong
to the same information set. A player cannot distinguish among nodes in a
given information set (that belongs to this player). For example, player
${\bm{x}}$ cannot distinguish among the blue nodes, since in both nodes,
player ${\bm{x}}$ was dealt Queen but does not know whether player ${\bm{y}}$
was dealt Jack or King.

We can further separate the decision spaces and consider them individually on
a per-player basis, which is where the concept of a treeplex arises. We show
player ${\bm{x}}$’s decision space in Figure 3. Here each circular node is an
information set, which is a decision node for player ${\bm{x}}$ where they
choose an action. For example, the blue node $\bm{h}_{3}$ corresponds to the
initial state where player ${\bm{x}}$ is dealt Queen, and player ${\bm{x}}$
can choose to bet or check at this node. Each square node is an observation
node, where player ${\bm{x}}$ does not make a decision, but the environment or
player ${\bm{y}}$ makes decisions which determine the next decision node for
player ${\bm{x}}$. Each triangular node is a terminal node, where the game
ends.

Each index of treeplex ${\mathcal{X}}$ corresponds to a solid, directed, edge
in the figure. In other words, each index corresponds to an action in finite
action set $\Omega_{h}$ for every $h$ in ${\mathcal{H}}^{{\mathcal{X}}}$, the
set of information sets that belongs to player ${\bm{x}}$. Indices (solid
edges) are labeled from $x_{1}$ to $x_{12}$. More specifically,
${\bm{x}}\in{\mathcal{X}}$ if ${\bm{x}}$ satisfies $x_{i}\geq 0$ for every
index $i$ and for every $h\in{\mathcal{H}}^{{\mathcal{X}}}$,

$\displaystyle\sum_{i\in\Omega_{h}}x_{i}=x_{\sigma(h)},$

where index $\sigma(h)\in\Omega_{h^{\prime}}$ is the unique action such that
$h$ can be reached immediately by taking $\sigma(h)$ when player ${\bm{x}}$ is
in information set $h^{\prime}$. When no such action exists, that is, $h$ can
be reached immediately in the beginning, we set $\sigma(h)=0$ and $x_{0}=1$.
For example, we must have $x_{6}=x_{7}+x_{8}$ and $x_{5}+x_{6}=x_{0}=1$ if
${\bm{x}}\in{\mathcal{X}}$. Intuitively, $x_{i}$ is the probability taking
action $i$, given that the sequential decisions from the environment and
player ${\bm{y}}$ can lead to the information set where action $i$ is.
Similarly, we show player ${\bm{y}}$’s decision space in Figure 4, which
illustrates treeplex ${\mathcal{Y}}$.

Figure 2: A game tree for Kuhn poker. The edge labeled with JQ means that
player ${\bm{x}}$ is dealt Jack and player ${\bm{y}}$ is dealt Queen. The
cases are similar at other edges. We omit branches stemming from the green and
red nodes, which are similar to what we present for the blue nodes. Circular
nodes are player ${\bm{x}}$’s decision nodes, while square nodes are player
${\bm{y}}$’s decision nodes. Triangular nodes are terminal nodes, where the
values denote the utility for player ${\bm{x}}$ (and thus the loss for player
${\bm{y}}$). Nodes with the same color belong to the same information set, and
a player cannot distinguish among nodes within the same information set, that
is, they only know they are at one of these nodes but do not know which node
they are at exactly. Figure 3: The decision space for player ${\bm{x}}$ and
treeplex ${\mathcal{X}}$. Each circular node is an information set, each
square node is an observation node, and each triangular node is a termination
node, where the decision process ends. Each solid edge corresponds an action
and one of the indexes in treeplex ${\mathcal{X}}$. More specifically, we have
$M=13$, $\mathcal{H}^{{\mathcal{X}}}=\\{\bm{h}_{1},\dots,\bm{h}_{6}\\}$,
$\Omega_{\bm{h}_{i}}=\\{2i-1,2i\\}$ for $i=1,\dots,6$,
$\sigma(\bm{h}_{1})=\sigma(\bm{h}_{3})=\sigma(\bm{h}_{5})=0$,
$\sigma(\bm{h}_{2})=2$, $\sigma(\bm{h}_{4})=6$, $\sigma(\bm{h}_{6})=10$.

Figure 4: The decision space for player ${\bm{y}}$ and treeplex
${\mathcal{Y}}$. Each square node is an information set and each triangular
node is a termination node. More specifically, we have $N=13$,
$\mathcal{H}^{{\mathcal{Y}}}=\\{\bm{h}_{1}^{\prime},\dots,\bm{h}_{6}^{\prime}\\}$,
$\Omega_{\bm{h}_{i}^{\prime}}=\\{2i-1,2i\\}$ and
$\sigma(\bm{h}_{i}^{\prime})=0$ for $i=1,\dots,6$.

##  Appendix B Omitted Details of Section 7

In this section, we provide more details about the experiments.

###  B.1 Additional Experiments

As we mentioned in Section 7, although VOGDA and DOMWU have linear convergence
rate in theory, we use much larger step sizes $\eta$ in the Leduc poker
experiment than what Corollary 5 and Theorem 7 suggest, which explains why we
were not able to observe the linear convergence. Here, we rerun this
experiment with a smaller step size for VOGDA and DOMWU. With more iterations,
on the order of $10^{5}$, we observe again that they exhibit fast convergence,
as shown in Figure 5.

Figure 5: Experiments on Kuhn Leduc poker for DOMWU (left) and VOGDA (right)
with small step sizes and more time steps.

###  B.2 Description of the Games

We briefly introduce the games in the experiments. Beside the rules of the
games, we show the game size by providing $M,N$,
$|\mathcal{H}^{{\mathcal{Y}}}|$, and $|\mathcal{H}^{{\mathcal{Y}}}|$ (recall
$\bm{G}=\mathbb{R}^{M\times N}$).

##### Kuhn poker

Introduced in [Kuhn, 1950], the deck for Kuhn poker contains three playing
cards: King, Queen, and Jack. Each player is dealt one card, while the third
card is unseen. Then a betting process proceeds. Player ${\bm{x}}$ can check
or raise, and then player ${\bm{y}}$ can also check or raise. Player
${\bm{x}}$ has a final round to call or fold if player ${\bm{x}}$ checks but
player ${\bm{y}}$ raises in the previous round. The player with the higher
card wins the pot. In this game, $M=N=13$,
$|\mathcal{H}^{{\mathcal{X}}}|=|\mathcal{H}^{{\mathcal{Y}}}|=6$.

##### Pursuit-evasion

This is a search game considered in [Kroer et al., 2018]. Given a direct
graph, player ${\bm{x}}$ controls an attacker to move in the graph, while
player ${\bm{y}}$ controls two patrols, who are only allowed to move in their
patrol areas. The game has 4 rounds. In each round, the attacker and the
patrols act simultaneously. The attacker can move to any adjacent node or
choose to wait in each round, with the final goal of going across the patrol
areas and reach the goal nodes without being caught by the patrols. On the
other hand, player ${\bm{y}}$’s goal is to let one of the patrols to reach the
same node as the attacker in any round. A patrol who visits a node that was
previously visited by the attacker will know that the attacker was there if
the attacker did not wait at that node (in order to clean up their traces). In
this game, $M=52$, $N=2029$, $|\mathcal{H}^{{\mathcal{X}}}|=34$,
$|\mathcal{H}^{{\mathcal{Y}}}|=348$.

##### Leduc poker

Introduced in [Southey et al., 2005], the game is similar to Kuhn poker. There
are total 6 cards in the deck with two Kings, two Queens, and two Jacks. Each
player is dealt a private card while there is another unrevealed public card.
In the first round, player ${\bm{y}}$ bets after player ${\bm{x}}$ bets. After
that the public card will be revealed and there is another betting stage. In a
showdown stage, a player who has the same rank with the public card wins.
Otherwise, the player with the higher card wins. In this game, $M=N=337$,
$|\mathcal{H}^{{\mathcal{X}}}|=|\mathcal{H}^{{\mathcal{Y}}}|=144$.

###  B.3 Parameter Selection in the Dilated Regularizers

We note that for the dilated regularizers, we use the unweighted version in
the experiments. This is sufficient as Lemma 9 shows there always exists an
assignment ${\bm{\alpha}}$ such that $\psi^{\text{dil}}_{{\bm{\alpha}}}$ is
1-strongly convex and ${\bm{\alpha}}=\beta\cdot\mathbf{1}$ for some $\beta>0$,
where $\mathbf{1}$ is the all-one vector over ${\mathcal{H}^{\mathcal{Z}}}$.
In this way, the value of $\eta$ we refer to in Figure 1 is actually
$\eta/\beta$. However, as we mentioned, the final $\eta$ used in the
experiments may still be larger than what the theorems suggest. Showing
similar results while allowing larger $\eta$ is an interesting future
direction.

######  Lemma 9.

For an assignment ${\bm{\alpha}}$ such that
$\psi^{\text{dil}}_{{\bm{\alpha}}}$ is 1-strongly convex,
$\psi^{\text{dil}}_{{\bm{\alpha}}^{\prime}}$ is also 1-strongly convex where
${\bm{\alpha}}^{\prime}={\|{\bm{\alpha}}\|_{\infty}}\mathbf{1}$.

###### Proof.

Recall the definition of regularizer
$\psi^{\text{dil}}_{{\bm{\alpha}}}({\bm{z}})$ in Eq. (3). Since each term
$z_{{\sigma(h)}}\cdot\psi\left(\frac{{\bm{z}}_{h}}{z_{\sigma(h)}}\right)$ is
convex in ${\bm{z}}$ (thus with a non-negative Bregman divergence),
$D_{\psi^{\text{dil}}_{{\bm{\alpha}}}}$ is an increasing function in any
variable $\alpha_{h}$ ($h\in\mathcal{H}^{\mathcal{Z}}$). Therefore, we have

$\displaystyle\frac{\|{\bm{z}}-{\bm{z}}^{\prime}\|^{2}}{2}\leq
D_{\psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}},{\bm{z}}^{\prime})\leq
D_{\psi^{\text{dil}}_{{\bm{\alpha}}^{\prime}}}({\bm{z}},{\bm{z}}^{\prime}),$

which completes the proof. ∎

##  Appendix C Omitted Details of Section 4

When introducing VOMWU in Section 4, we mention that $\Psi^{\text{van}}$ is
1-strongly convex with respect to the 2-norm. In the following, we formally
show this result. Before that, we first show a technical lemma.

######  Lemma 10.

For $u,v\in[0,1]$, the following inequalities hold:

$\displaystyle\frac{(u-v)^{2}}{2}\leq
u\ln\left(\frac{u}{v}\right)-u+v\leq\frac{(u-v)^{2}}{v}.$ (14)

###### Proof.

Define $f(u,v)=u\ln\left(\frac{u}{v}\right)-u+v-\frac{(u-v)^{2}}{2}$ and
$g(u,v)=\frac{(u-v)^{2}}{v}-u\ln\left(\frac{u}{v}\right)+u-v$. To prove the
claim, it is sufficient to show that the minimum of each of the two functions
is zero. Since both functions have the only critical point $(0,0)$, there is
no extreme point in the interior. Also, it is straightforward to find a
$(u,v)$ such that $f(u,v),g(u,v)>0$ in the interior. Thus, it remains to check
if the boundary of the domain satisfies $f(u,v),g(u,v)\geq 0$. For $u=0$, we
have

$\displaystyle\frac{(0-v)^{2}}{2}=\frac{v^{2}}{2}\leq v=\frac{(0-v)^{2}}{v}.$

The case for $v=0$ is trivial. For $u=1$, note that

$\displaystyle\frac{(v-1)^{2}}{2}\leq v-1-\ln(v)\leq\frac{(v-1)^{2}}{v}$

when $0\leq v\leq 1$. For $v=1$, we have

$\displaystyle\frac{(u-1)^{2}}{2}\leq u\ln u-u+1\leq(u-1)^{2}$

when $0\leq u\leq 1$. Therefore, we conclude $f(u,v),g(u,v)\geq 0$ and this
finishes the proof. ∎

Now we are ready to give the result.

######  Lemma 11.

$\Psi^{\text{van}}$ is 1-strongly convex with respect to the 2-norm.

###### Proof.

The result follows by the first inequality of Eq. (14) and $0\leq z_{i}\leq 1$
for all ${\bm{z}}\in\mathcal{Z}$. ∎

##  Appendix D CFR-based Algorithms and Proof of Theorem 3

In this section, we first introduce CFR, CFR+, and their optimistic versions.
Then we show Theorem 3 in Appendix D.3 and their empirical last-iterate
divergence in Appendix D.4.

###  D.1 CFR and Its Optimistic Version

Given $P$-dimensional treeplex $\mathcal{Z}$, loss vector
$\bm{\ell}\in\mathbb{R}^{P}$, and ${\bm{z}}\in\mathcal{Z}$, we recursively
define the value vector $\bm{L}\in\mathbb{R}^{P}$, to be

$L_{i}=\ell_{i}+\sum_{g\in\mathcal{H}_{i}}\langle{\bm{q}}_{g},\bm{L}_{g}\rangle$

for every index $i$ (recall that $q_{i}=z_{i}/z_{p_{i}}$). At time $t$, given
${\bm{q}}_{t}$, loss vector $\ell_{t}$, and its value vector $\bm{L}_{t}$,
denote $\text{\rm reg}_{t,j}^{g}=\langle{\bm{q}}_{t,g},\bm{L}_{t,g}\rangle-
L_{t,j}$, $\text{\rm Reg}_{0,j}^{g}=0$, and $\text{\rm
Reg}_{t,j}^{g}=\text{\rm Reg}_{t-1,j}^{g}+\text{\rm reg}_{t,j}^{g}$ for every
simplex $g\in\mathcal{H}^{\mathcal{Z}}$ and index $j\in\Omega_{g}$. In the
literature, _Counterfactual Regret Minimization_ (CFR) Zinkevich et al. [2007]
refers to the algorithm running _regret matching_ on every simplex in a
treeplex. Specifically, on simplex $g$ at time $t+1$, regret matching plays
arbitrarily when $\sum_{j\in\Omega_{g}}\left[\text{\rm
Reg}_{t,j}^{g}\right]_{+}=0$, where $\left[x\right]_{+}=\max(0,x)$; otherwise,
it plays

$\displaystyle q_{t+1,i}=\frac{\left[\text{\rm
Reg}_{t,i}^{g}\right]_{+}}{\sum_{j\in\Omega_{g}}\left[\text{\rm
Reg}_{t,j}^{g}\right]_{+}},$

for all $i$ in $\Omega_{g}$. In the two-player zero-sum setting, player
${\bm{x}}$ runs CFR on every simplex in treeplex ${\mathcal{X}}$ along with
point ${\bm{x}}_{t}\in{\mathcal{X}}$ and loss vector
$\bm{L}_{t}^{\bm{x}}=\bm{G}{\bm{y}}_{t}$, and player ${\bm{y}}$ runs CFR on
every simplex in ${\mathcal{Y}}$ along with point
${\bm{y}}_{t}\in{\mathcal{Y}}$ and loss vector
$\bm{L}_{t}^{\bm{y}}=-\bm{G}^{\top}{\bm{x}}_{t}$ for every time $t$.

The optimistic version of CFR Farina et al. [2021a] is running the optimistic
version of regret matching on every simplex in a treeplex. Specifically, the
algorithm plays arbitrarily when $\sum_{j\in\Omega_{g}}\left[\text{\rm
Reg}_{t,j}^{g}+\text{\rm reg}_{t,j}^{g}\right]_{+}=0$; otherwise,

$\displaystyle q_{t+1,i}=\frac{\left[\text{\rm Reg}_{t,i}^{g}+\text{\rm
reg}_{t,i}^{g}\right]_{+}}{\sum_{j\in\Omega_{g}}\left[\text{\rm
Reg}_{t,j}^{g}+\text{\rm reg}_{t,j}^{g}\right]_{+}}.$

To get an approximate Nash equilibrium at time $t$, CFR and its optimistic
version consider the average iterate, that is, they return

$(\overline{{\bm{x}}}_{t},\overline{{\bm{y}}}_{t})=\left(\frac{1}{t}\sum_{\tau=1}^{t}{\bm{x}}_{\tau},\frac{1}{t}\sum_{\tau=1}^{t}{\bm{y}}_{\tau}\right).$

###  D.2 CFR+ and Its Optimistic Version

To introduce CFR+, we first introduce another regret-minimization algorithm on
simplex, _regret matching+_. Similar to $\text{\rm Reg}_{t,j}^{g}$, we define
$\widehat{\text{\rm Reg}}_{0,j}^{g}=0$ and

$\displaystyle\widehat{\text{\rm Reg}}_{t,j}^{g}=\left[\widehat{\text{\rm
Reg}}_{t-1,j}^{g}+\text{\rm reg}_{t,j}^{g}\right]_{+},$

for every simplex $g\in\mathcal{H}^{\mathcal{Z}}$ and index $j\in\Omega_{g}$.
On simplex $g$ at time $t+1$, regret matching+ plays arbitrarily when
$\sum_{j\in\Omega_{g}}\left[\widehat{\text{\rm Reg}}_{t,j}^{g}\right]_{+}=0$;
otherwise, it plays

$\displaystyle q_{t+1,i}=\frac{\left[\widehat{\text{\rm
Reg}}_{t,i}^{g}\right]_{+}}{\sum_{j\in\Omega_{g}}\left[\widehat{\text{\rm
Reg}}_{t,j}^{g}\right]_{+}}.$

CFR+ Tammelin [2014] refers to running _regret matching+_ on every simplex in
a treeplex. In the two-player zero-sum setting, CFR+ usually refers to the one
with _alternating updates_. Specifically, player ${\bm{x}}$ runs CFR+ on every
simplex in $\mathcal{H}^{\mathcal{X}}$ with loss vector
$\bm{L}_{t}^{\bm{x}}=\bm{G}{\bm{y}}_{t}$ and player ${\bm{y}}$ runs CFR on
every simplex in $\mathcal{H}^{\mathcal{Y}}$ with loss vector
$\bm{L}_{t}^{\bm{y}}=-\bm{G}^{\top}{\bm{x}}_{t+1}$ (note that in the case with
simultaneous updates, $\bm{L}_{t}^{\bm{y}}=-\bm{G}^{\top}{\bm{x}}_{t}$).

The optimistic version of CFR+ Farina et al. [2021a] is running the optimistic
version of regret matching+ on every simplex in a treeplex. Specifically, the
algorithm plays arbitrarily when
$\sum_{j\in\Omega_{g}}\left[\widehat{\text{\rm Reg}}_{t,j}^{g}+\text{\rm
reg}_{t,j}^{g}\right]_{+}=0$; otherwise, it plays

$\displaystyle q_{t+1,i}=\frac{\left[\widehat{\text{\rm
Reg}}_{t,i}^{g}+\text{\rm
reg}_{t,i}^{g}\right]_{+}}{\sum_{j\in\Omega_{g}}\left[\widehat{\text{\rm
Reg}}_{t,j}^{g}+\text{\rm reg}_{t,j}^{g}\right]_{+}}.$

Regarding the averaging scheme, CFR+ usually refers to the version with
_linear averaging_ to get an approximate Nash equilibrium at time $t$.
Specifically, it returns

$(\overline{{\bm{x}}}_{t},\overline{{\bm{y}}}_{t})=\left(\frac{2}{t(t+1)}\sum_{\tau=1}^{t}\tau\cdot{\bm{x}}_{\tau},\frac{2}{t(t+1)}\sum_{\tau=1}^{t}\tau\cdot{\bm{y}}_{\tau}\right).$

In summary, CFR+ and its optimistic version refer to running regret matching+
and optimistic regret matching+ on every simplex with alternating updates and
linear averaging.

###  D.3 Proof of Theorem 3

###### Proof of Theorem 3.

Note that in this instance, there is only one simplex $g^{\bm{x}}$ for player
${\bm{x}}$ and one simplex $g^{\bm{y}}$ for player ${\bm{y}}$. The game matrix
$\bm{G}$ of the rock-paper-scissors is

$\displaystyle\bm{G}=\begin{bmatrix}0&-1&1\\\ 1&0&-1\\\
-1&1&0\end{bmatrix}=-\bm{G}^{\top}.$

We consider the case when ${\bm{x}}_{1}={\bm{y}}_{1}$. Recall that we have
$\bm{L}_{t}^{\bm{x}}=\bm{G}{\bm{y}}_{t}$ and
$\bm{L}_{t}^{\bm{y}}=-\bm{G}^{\top}{\bm{x}}_{t}$. Therefore, we know that

$\displaystyle\bm{L}_{1}^{\bm{x}}=\bm{G}^{\top}{\bm{y}}_{1}=\bm{G}^{\top}{\bm{x}}_{1}=-\bm{G}^{\top}{\bm{x}}_{1}=\bm{L}_{1}^{\bm{y}},$

and

$\displaystyle\text{\rm
reg}_{1,j}^{g^{\bm{x}}}={\bm{x}}_{1}^{\top}\bm{L}_{1}^{\bm{x}}-L_{1,j}^{{\bm{x}}}={\bm{x}}_{1}^{\top}\bm{G}{\bm{x}}_{1}-L_{1,j}^{{\bm{x}}}=-L_{1,j}^{{\bm{x}}}=-L_{1,j}^{{\bm{y}}}=\text{\rm
reg}_{1,j}^{g^{\bm{y}}}$

for $j=1,2,3$. It is not hard to see that in this case, we have
${\bm{x}}_{2}={\bm{y}}_{2}$, and thus ${\bm{x}}_{t}={\bm{y}}_{t}$ for every
$t$. Consequently, it is sufficient to focus on the updates of ${\bm{x}}_{t}$.
For notional convenience, we write

$\displaystyle\text{\rm reg}_{t}=\text{\rm
reg}_{t}^{g^{\bm{x}}}=\bm{G}^{\top}{\bm{x}}_{t}=(x_{t,2}-x_{t,3},x_{t,3}-x_{t,1},x_{t,1}-x_{t,2})^{\top},$
(15) $\displaystyle\text{\rm Reg}_{t}=\text{\rm
Reg}_{t}^{g^{\bm{x}}}=\text{\rm Reg}_{t-1}^{g^{\bm{x}}}+\text{\rm
reg}_{t}=\sum_{\tau=1}^{t}\text{\rm reg}_{\tau},$ (16)

and thus

$\displaystyle x_{t+1,j}=\frac{\left[\text{\rm
Reg}_{t,j}\right]_{+}}{\left[\text{\rm Reg}_{t,1}\right]_{+}+\left[\text{\rm
reg}_{t,2}\right]_{+}+\left[\text{\rm Reg}_{t,3}\right]_{+}}$ (17)

for $j=1,2,3$. We call distribution ${\bm{x}}_{t}$ _imbalanced_ if there
exists a permutation $\lambda$ of $\\{1,2,3\\}$ such that

$\displaystyle x_{t,\lambda(1)}\geq x_{t,\lambda(2)}\geq 0=x_{t,\lambda(3)}.$

We prove that if ${\bm{x}}_{1}$ is imbalanced, then every ${\bm{x}}_{t}$ is
imbalanced. Suppose at some time $t$, ${\bm{x}}_{t}$ is imbalanced and the
corresponding $\lambda$ is the identity without loss of generality, that is,

$\displaystyle x_{t,1}\geq x_{t,2}\geq 0=x_{t,3}.$ (18)

In this case, we know that $\text{\rm Reg}_{t-1,1}>0$. By Eq. (18) and Eq.
(15), we also know that $\text{\rm reg}_{t,1}\geq 0$, $\text{\rm
reg}_{t,3}\geq 0$, $\text{\rm reg}_{t,2}<0$, and $\text{\rm Reg}_{t,1}>0$.
Moreover, by Eq. (15) and Eq. (16), we can get

$\displaystyle\text{\rm reg}_{t,1}+\text{\rm reg}_{t,2}+\text{\rm
reg}_{t,3}=0,~{}\text{\rm Reg}_{t,1}+\text{\rm Reg}_{t,2}+\text{\rm
Reg}_{t,3}=0.$

Therefore, we have $\text{\rm Reg}_{t,2}+\text{\rm Reg}_{t,3}<0$, which means
that at least one of $x_{t+1,2}$ and $x_{t+1,3}$ is zero. Moreover, we have

$\text{\rm Reg}_{t,1}=\text{\rm Reg}_{t-1,1}+\text{\rm reg}_{t,1}\geq\text{\rm
Reg}_{t-1,1}\geq\text{\rm Reg}_{t-1,2}>\text{\rm Reg}_{t-1,2}+\text{\rm
reg}_{t,2}=\text{\rm Reg}_{t,2},$

where the second inequality follows from $x_{t,1}\geq x_{t,2}$ and Eq. (17).
The inequalities above imply that $x_{t+1,1}>x_{t+1,2}$. Thus, we get one of
the following three situations continues to hold at time $t+1$:

$\displaystyle x_{t+1,1}$ $\displaystyle\geq x_{t+1,2}\geq 0=x_{t+1,3},$ (19)
$\displaystyle x_{t+1,1}$ $\displaystyle\geq x_{t+1,3}\geq 0=x_{t+1,2},$ (20)
$\displaystyle x_{t+1,3}$ $\displaystyle\geq x_{t+1,1}\geq 0=x_{t+1,2}.$ (21)

If Eq. (19) holds at time $t+1$, the same argument implies one of the three
arguments above continues to hold; otherwise, if at some time step $\tau>t$,
Eq. (20) holds, that is,

$\displaystyle x_{\tau,1}\geq x_{\tau,3}\geq 0=x_{\tau,2}.$ (22)

Similarly, we know that $\text{\rm reg}_{\tau,1}\leq 0,\text{\rm
reg}_{\tau,2}\leq 0$ and $\text{\rm reg}_{\tau,3}\geq 0$, and
$x_{\tau+1,2}=0$. Thus, we get either Eq. (22) continues to hold at time
$\tau+1$ or

$\displaystyle x_{\tau+1,3}\geq x_{\tau+1,1}\geq 0=x_{\tau+1,2}$

holds, which is exactly the same permutation in Eq. (21). With similar
arguments, we know that for every imbalanced distribution, either the same
permutation holds in the next round, or it transits to another imbalanced
distribution with another permutation. Note that the average iterate of the
sequence $\\{{\bm{x}}_{t}\\}_{t}$ converges to the uniform distribution as CFR
is a no-regret algorithm, so ${\bm{x}}_{t}$ never converges to any imbalanced
distribution. Therefore, we conclude that ${\bm{x}}_{t}$ diverges if the
algorithm starts from $x_{1}=y_{1}$ being an arbitrary imbalanced
distribution. ∎

###  D.4 Experiments

Besides Theorem 3, we empirically observe divergence of CFR, CFR+ with
simultaneous updates, and their optimistic versions in the rock-paper-scissors
game. The results are shown in Figure 6. We remark that in these experiments,
we consider CFR+ with simultaneous updates instead of the more commonly used
ones (alternating updates). In fact, we observe that with alternating updates,
the optimistic CFR+ empirically has last-iterate convergence in some matrix
games. As all of our theoretical results are for simultaneous updates, the
theoretical justification of this observation is beyond the scope of this
paper, but it is an interesting direction for future works.

Figure 6: Last-iterate divergence of CFR, CFR+ with simultaneous updates, and
their optimistic versions in the rock-paper-scissors game. The first row is
the CFR algorithms while the second row is the CFR+ algorithms. For both rows,
we put the vanilla version on the left and the optimistic version on the
right. All algorithms start with ${\bm{x}}_{1}={\bm{y}}_{1}=(1,0,0)^{\top}$.

##  Appendix E Proofs of Theorem 6 and Theorem 7

In this section, we show the proof of Theorem 6 in Appendix E.4 and the proof
of Theorem 7 in Appendix E.5. We generally follow the outline in Section 6.3.
We discuss the technical difficulty to get a convergence rate for DOGDA in
Appendix E.6. Throughout the section, we assume that $\bm{G}$ has a unique
Nash equilibrium ${\bm{z}}^{*}=({\bm{x}}^{*},{\bm{y}}^{*})$ (call it the
uniqueness assumption). For the sake of analysis, we equivalently define
$\Psi^{\text{dil}}_{{\bm{\alpha}}}$ as

$\Psi^{\text{dil}}_{{\bm{\alpha}}}({\bm{z}})=\sum_{i}\alpha_{h(i)}z_{i}\ln\frac{z_{i}}{\sum_{j\in\Omega_{h(i)}}z_{j}}.$

Note that under this definition, we have

$\displaystyle\frac{\partial\Psi^{\text{dil}}_{{\bm{\alpha}}}({\bm{z}})}{\partial
z_{i}}=\alpha_{h(i)}\left[\ln\left(\frac{z_{i}}{\sum_{j\in\Omega_{h(i)}}z_{j}}\right)+1-\sum_{k\in\Omega_{h(i)}}\frac{z_{k}}{\sum_{j\in\Omega_{h(i)}}z_{j}}\right]=\alpha_{h(i)}\ln
q_{i},$ (23)

and

$\displaystyle
D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}},{\bm{z}}^{\prime})=\sum_{i}\alpha_{h(i)}\left[z_{i}\ln(q_{i})-z_{i}^{\prime}\ln(q_{i}^{\prime})-(z_{i}-z_{i}^{\prime})\ln(q_{i}^{\prime})\right]=\sum_{i}\alpha_{h(i)}z_{i}\ln\frac{q_{i}}{q_{i}^{\prime}}.$
(24)

###  E.1 Strict Complementary Slackness and Proof of Eq. (6) in EFGs

In this subsection, we prove Eq. (6), which is restated in Lemma 12.

######  Lemma 12.

Under the uniqueness assumption, for both VOMWU and DOMWU, there exists some
constant $C_{12}>0$ that depends on the game, $\eta$, and
$\widehat{\bm{z}}_{1}$ such that for any $t$,

$\displaystyle\zeta_{t}=D_{\psi}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t})+D_{\psi}({\bm{z}}_{t},\widehat{\bm{z}}_{t})\geq
C_{12}\|{\bm{z}}^{*}-\widehat{\bm{z}}_{t+1}\|^{2}.$ (25)

Before proving this lemma, we show some useful properties of EFGs. The first
one is the strict complementary slackness.

####  E.1.1 Strict Complementary Slackness

We formulate the minimax problem in Eq. (1) as a linear program. This is a
standard procedure in the literature (see, for example, [Nisan et al., 2007,
Section 3.11]), but we show its derivation here for completeness. Based on
Definition 1, we have ${\bm{x}}\in{\mathcal{X}}$ if ${\bm{x}}$ satisfies
$x_{i}\geq 0$ for every $i$ and

$\displaystyle
x_{0}=1,\qquad\sum_{i\in\Omega_{h}}x_{i}=x_{\sigma(h)},~{}\forall
h\in{\mathcal{H}}^{{\mathcal{X}}}.$ (26)

We can write the constraints in Eq. (26) using a matrix
$\bm{A}\in\mathbb{R}^{\left(\left|{\mathcal{H}}^{{\mathcal{X}}}\right|+1\right)\times
M}$ such that ${\bm{x}}\in{\mathcal{X}}$ if and only if
$\bm{A}{\bm{x}}=\bm{e},~{}{\bm{x}}\geq\bm{0}$, where all entries in $\bm{e}$
are zero except for $e_{0}=1$, which corresponds to the constraint
$x_{0}=e_{0}=1$. Similarly, for player ${\bm{y}}$, we have the constraint
matrix $\bm{B}$ and vector $\bm{f}$. Consequently, we write the best response
of ${\bm{x}}$ to a fixed ${\bm{y}}$ to as the following linear program:

$\displaystyle\min_{{\bm{x}}}{\bm{x}}^{\top}(\bm{G}{\bm{y}}),~{}\text{subject
to}~{}\bm{A}{\bm{x}}=\bm{e},~{}{\bm{x}}\geq\bm{0}.$

The dual of this linear program is

$\displaystyle\max_{\bm{V}}\bm{e}^{\top}\bm{V},~{}\text{subject
to}~{}\bm{A}^{\top}\bm{V}\leq\bm{G}{\bm{y}},$

where $\bm{V}\in\mathbb{R}^{|{\mathcal{H}}^{{\mathcal{X}}}|+1}$. Recall that
all entries in $\bm{e}$ are zero except for $e_{0}=1$ so the objective
$\bm{e}^{\top}\bm{V}=V_{0}$. On the other hand, player ${\bm{y}}$ tries to
maximize ${\bm{x}}^{\top}\bm{G}{\bm{y}}$, that is, maximize $V_{0}$ by the
strong duality. Therefore, every ${\bm{y}}^{*}\in{\mathcal{Y}}^{*}$ is a
solution to the following maximin problem

$\displaystyle\max_{\bm{V},{\bm{y}}}V_{0},~{}\text{subject
to}~{}\bm{A}^{\top}\bm{V}\leq\bm{G}{\bm{y}},~{}\bm{B}{\bm{y}}=\bm{f},~{}{\bm{y}}\geq\bm{0},$
(27)

which is also a linear program. The dual of this linear problem is

$\displaystyle\min_{\bm{U},{\bm{x}}}U_{0},~{}\text{subject
to}~{}\bm{B}^{\top}\bm{U}\geq\bm{G}^{\top}{\bm{x}},~{}\bm{A}{\bm{x}}=\bm{e},~{}{\bm{x}}\geq\bm{0}.$
(28)

It is also not hard to see that every ${\bm{x}}^{*}\in{\mathcal{X}}$ is a
solution to this dual. We conclude that Eq. (27) and Eq. (28) are primal-dual
linear programs of the minmax problem in Eq. (1). Given an optimal solution
pair ${\bm{x}}^{*},{\bm{y}}^{*}$ along with $\bm{V}^{*},\bm{U}^{*}$, by the
complementary slackness, we have some slackness variables
${\bm{w}}^{*}\in\mathbb{R}^{M},\bm{s}^{*}\in\mathbb{R}^{N}$ such that
${\bm{x}}^{*}\odot{\bm{w}}^{*}=\bm{0}$, ${\bm{y}}^{*}\odot\bm{s}^{*}=\bm{0}$
($\odot$ denotes the element-wise product), and

$\displaystyle\bm{A}^{\top}\bm{V}^{*}-\bm{G}{\bm{y}}^{*}+{\bm{w}}^{*}=\bm{0},\quad\bm{B}^{\top}\bm{U}^{*}-\bm{G}^{\top}{\bm{x}}^{*}-\bm{s}^{*}=\bm{0},\quad{\bm{w}}^{*},\bm{s}^{*}\geq\bm{0}.$
(29)

Thus, Eq. (29) implies that for every index $i$ of player ${\bm{x}}$,

$\displaystyle
V^{*}_{h(i)}-\sum_{g\in\mathcal{H}_{i}}V^{*}_{g}-(\bm{G}{\bm{y}}^{*})_{i}=(\bm{A}^{\top}\bm{V}^{*})_{i}-(\bm{G}{\bm{y}}^{*})_{i}=(\bm{A}^{\top}\bm{V}^{*}-\bm{G}{\bm{y}}^{*})_{i}=-w^{*}_{i}.$
(30)

Additionally, the _strict complementary slackness_ (see, for example,
[Vanderbei et al., 2015, Theorem 10.7]) ensures that there exists an optimal
solution $({\bm{x}}^{*},{\bm{y}}^{*})$ such that

$\displaystyle{\bm{x}}^{*}+{\bm{w}}^{*}>\bm{0},\quad{\bm{y}}^{*}+\bm{s}^{*}>\bm{0}.$
(31)

Under the uniqueness assumption, the strict complementary slackness must hold
for the unique optimal solution $({\bm{x}}^{*},{\bm{y}}^{*})$. Therefore, when
$x^{*}_{i}>0$, we have $w^{*}_{i}=0$, which means that Eq. (30) implies

$\displaystyle
V^{*}_{h}=(\bm{G}{\bm{y}}^{*})_{i}+\sum_{g\in\mathcal{H}_{i}}V^{*}_{g},\quad\forall
h\in{\mathcal{H}}^{{\mathcal{X}}},~{}i\in\Omega_{h},~{}x^{*}_{i}>0;$ (32)

otherwise, if $x^{*}_{i}=0$ and $w^{*}_{i}>0$, by Eq. (30), we have

$\displaystyle
V^{*}_{h}<(\bm{G}{\bm{y}}^{*})_{i}+\sum_{g\in\mathcal{H}_{i}}V^{*}_{g},\quad\forall
h\in{\mathcal{H}}^{{\mathcal{X}}},~{}i\in\Omega_{h},~{}x^{*}_{i}=0.$ (33)

Note that for every terminal index $i$, ${\mathcal{H}_{i}}$ is empty and we
set the term $\sum_{g\in\mathcal{H}_{i}}V^{*}_{g}$ zero correspondingly. The
case is similar for $\bm{U}^{*}$ and $\bm{G}^{\top}{\bm{x}}^{*}$. We summarize
this result as the following lemma.

######  Lemma 13.

Under the uniqueness assumption, we have

$\displaystyle\sum_{g\in\mathcal{H}_{i}}V^{*}_{g}+(\bm{G}{\bm{y}}^{*})_{i}$
$\displaystyle=V^{*}_{h(i)}$ $\displaystyle\forall
i\in\text{supp}({\bm{x}}^{*}),$
$\displaystyle\sum_{g\in\mathcal{H}_{i}}V^{*}_{g}+(\bm{G}{\bm{y}}^{*})_{i}$
$\displaystyle>V^{*}_{h(i)}$ $\displaystyle\forall
i\notin\text{supp}({\bm{x}}^{*}),$
$\displaystyle\sum_{g\in\mathcal{H}_{j}}U^{*}_{g}+(\bm{G}^{\top}{\bm{x}}^{*})_{j}$
$\displaystyle=U^{*}_{h(j)}$ $\displaystyle\forall
j\in\text{supp}({\bm{y}}^{*}),$
$\displaystyle\sum_{g\in\mathcal{H}_{j}}U^{*}_{g}+(\bm{G}^{\top}{\bm{x}}^{*})_{j}$
$\displaystyle<U^{*}_{h(j)}$ $\displaystyle\forall
j\notin\text{supp}({\bm{y}}^{*}).$

####  E.1.2 Some Problem-dependent Constants

After introducing the strict complementary slackness, we are ready to
introduce some problem-dependent constants. Note that by Lemma 13, we have the
following constant $\xi>0$.

######  Definition 2.

Under the uniqueness assumption, we define

$\displaystyle\xi\triangleq\min\left\\{\min_{i\notin\text{supp}({\bm{x}}^{*})}\sum_{g\in\mathcal{H}_{i}}V^{*}_{g}+(\bm{G}{\bm{y}}^{*})_{i}-V^{*}_{h(i)},~{}\min_{j\notin\text{supp}({\bm{y}}^{*})}U^{*}_{h(j)}-(\bm{G}^{\top}{\bm{x}}^{*})_{j}-\sum_{g\in\mathcal{H}_{j}}U^{*}_{g}\right\\}\in(0,2].$

Note that $\xi\leq 2$ follows from the fact that for any information set
$h\in\mathcal{H}^{\mathcal{X}}$, indices $i,j\in\Omega_{h}$ such that
$i\notin\text{supp}({\bm{x}}^{*})$ and $j\in\text{supp}({\bm{x}}^{*})$, by
Lemma 13, we have

$\xi\leq\sum_{g\in\mathcal{H}_{i}}V^{*}_{g}+(\bm{G}{\bm{y}}^{*})_{i}-V^{*}_{h}=(\bm{G}{\bm{y}}^{*})_{i}-(\bm{G}{\bm{y}}^{*})_{j}\leq
2.$

Below, we define
$\mathcal{V}^{*}(\mathcal{Z})=\mathcal{V}^{*}(\mathcal{X})\times\mathcal{V}^{*}(\mathcal{Y})$,
where

$\mathcal{V}^{*}(\mathcal{X})\triangleq\\{{\bm{x}}:{\bm{x}}\in\mathcal{X},~{}\text{supp}({\bm{x}})\subseteq\text{supp}({\bm{x}}^{*})\\}$

and

$\mathcal{V}^{*}(\mathcal{Y})\triangleq\\{{\bm{y}}:{\bm{y}}\in\mathcal{Y},~{}\text{supp}({\bm{y}})\subseteq\text{supp}({\bm{y}}^{*})\\}.$

######  Definition 3.

$\displaystyle
c_{x}\triangleq\min_{{{\bm{x}}\in\mathcal{X}\backslash\\{{\bm{x}}^{*}\\}}}\max_{{\bm{y}}\in\mathcal{V}^{*}(\mathcal{Y})}\frac{({\bm{x}}-{\bm{x}}^{*})^{\top}\bm{G}{\bm{y}}}{\|{\bm{x}}-{\bm{x}}^{*}\|_{1}},\qquad
c_{y}\triangleq\min_{{{\bm{y}}\in\mathcal{Y}\backslash\\{{\bm{y}}^{*}\\}}}\max_{{\bm{x}}\in\mathcal{V}^{*}(\mathcal{X})}\frac{{\bm{x}}^{\top}\bm{G}({\bm{y}}^{*}-{\bm{y}})}{\|{\bm{y}}^{*}-{\bm{y}}\|_{1}}.$

The following lemma shows that $c_{x}$ and $c_{y}$ are well-defined even
though the outer minimization is over an open set. The proof generally follows
[Wei et al., 2021, Lemma 14] but requires the results derived in Appendix
E.1.1.

######  Lemma 14.

$c_{x}$ and $c_{y}$ are well-defined, and $0<c_{x},c_{y}\leq 1$.

###### Proof.

We first show $c_{x}$ and $c_{y}$ are well-defined. To simplify the notations,
we define
$x_{\min}^{*}\triangleq\min_{i\in\text{supp}({\bm{x}}^{*})}x_{i}^{*}$ and
$\mathcal{X}^{\prime}\triangleq\\{{\bm{x}}:{\bm{x}}\in\mathcal{X},~{}\|{\bm{x}}-{\bm{x}}^{*}\|_{1}\geq
x_{\min}^{*}\\}$, and define $y_{\min}^{*}$ and $\mathcal{Y}^{\prime}$
similarly. We will show that

$\displaystyle
c_{x}=\min_{{\bm{x}}\in\mathcal{X}^{\prime}}\max_{{\bm{y}}\in\mathcal{V}^{*}(\mathcal{Y})}\frac{({\bm{x}}-{\bm{x}}^{*})^{\top}\bm{G}{\bm{y}}}{\|{\bm{x}}-{\bm{x}}^{*}\|_{1}},\quad
c_{y}=\min_{{\bm{y}}\in\mathcal{Y}^{\prime}}\max_{{\bm{x}}\in\mathcal{V}^{*}(\mathcal{X})}\frac{{\bm{x}}^{\top}\bm{G}({\bm{y}}^{*}-{\bm{y}})}{\|{\bm{y}}^{*}-{\bm{y}}\|_{1}},$

which are well-defined as the outer minimization is now over a closed set. To
prove the equality for $c_{x}$, it suffices to show that for any
${\bm{x}}\in\mathcal{X}$ such that ${\bm{x}}\neq{\bm{x}}^{*}$ and
$\|{\bm{x}}-{\bm{x}}^{*}\|_{1}<x_{\min}^{*}$, there exists
${\bm{x}}^{\prime}\in\mathcal{X}$ such that
$\|{\bm{x}}^{\prime}-{\bm{x}}^{*}\|_{1}=x_{\min}^{*}$ and

$\displaystyle\frac{({\bm{x}}-{\bm{x}}^{*})^{\top}\bm{G}{\bm{y}}}{\|{\bm{x}}-{\bm{x}}^{*}\|_{1}}=\frac{({\bm{x}}^{\prime}-{\bm{x}}^{*})^{\top}\bm{G}{\bm{y}}}{\|{\bm{x}}^{\prime}-{\bm{x}}^{*}\|_{1}},\;\forall{\bm{y}}.$
(34)

In fact, we can simply choose
${\bm{x}}^{\prime}={\bm{x}}^{*}+({\bm{x}}-{\bm{x}}^{*})\cdot\frac{x_{\min}^{*}}{\|{\bm{x}}-{\bm{x}}^{*}\|_{1}}$.
We first argue that ${\bm{x}}^{\prime}$ is still in $\mathcal{X}$. For each
index $j$, if $x_{j}-x^{*}_{j}\geq 0$, we surely have $x^{\prime}_{j}\geq
x_{j}^{*}+0\geq 0$; otherwise, $x_{j}^{*}>x_{j}\geq 0$ and thus
$j\in\text{supp}({\bm{x}}^{*})$ and $x^{*}_{j}\geq x_{\min}^{*}$, which
implies $x^{\prime}_{j}\geq
x^{*}_{j}-|x_{j}-x^{*}_{j}|\cdot\frac{x_{\min}^{*}}{\|{\bm{x}}-{\bm{x}}^{*}\|_{1}}\geq
x^{*}_{j}-x_{\min}^{*}\geq 0$. In addition, for any
$h\in{\mathcal{H}}^{{\mathcal{X}}}$,

$\displaystyle\sum_{j\in\Omega_{h}}x^{\prime}_{j}$
$\displaystyle=\frac{x_{\min}^{*}}{\|{\bm{x}}-{\bm{x}}^{*}\|_{1}}\cdot\sum_{j\in\Omega_{h}}x_{j}+\left(1-\frac{x_{\min}^{*}}{\|{\bm{x}}-{\bm{x}}^{*}\|_{1}}\right)\sum_{j\in\Omega_{h}}x^{*}_{j}$
$\displaystyle=\frac{x_{\min}^{*}}{\|{\bm{x}}-{\bm{x}}^{*}\|_{1}}\cdot
x_{\sigma(h)}+\left(1-\frac{x_{\min}^{*}}{\|{\bm{x}}-{\bm{x}}^{*}\|_{1}}\right)x_{\sigma(h)}^{*}$
$\displaystyle=x^{\prime}_{\sigma(h)}.$

Therefore, we conclude ${\bm{x}}^{\prime}\in\mathcal{X}$. Moreover, according
to the definition of ${\bm{x}}^{\prime}$,
$\|{\bm{x}}^{\prime}-{\bm{x}}^{*}\|_{1}=x_{\min}^{*}$ holds. Also, since
${\bm{x}}^{*}-{\bm{x}}$ and ${\bm{x}}^{*}-{\bm{x}}^{\prime}$ are parallel
vectors, Eq. (34) is satisfied. The arguments above show that the $c_{x}$ in
Definition 3 is a well-defined real number. The case of $c_{y}$ is similar.

Now we show $0<c_{x},c_{y}\leq 1$. The fact that $c_{x},c_{y}\leq 1$ is a
direct consequence of the definitions. Below, we use contradiction to prove
that $c_{y}>0$. First, if $c_{y}<0$, then there exists
${\bm{y}}\neq{\bm{y}}^{*}$ such that
${\bm{x}}^{*\top}\bm{G}{\bm{y}}^{*}<{\bm{x}}^{*\top}\bm{G}{\bm{y}}$. This
contradicts with the fact that $({\bm{x}}^{*},{\bm{y}}^{*})$ is the
equilibrium.

On the other hand, if $c_{y}=0$, then there is some ${\bm{y}}\neq{\bm{y}}^{*}$
such that

$\max_{{\bm{x}}\in\mathcal{V}^{*}(\mathcal{X})}{\bm{x}}^{\top}\bm{G}({\bm{y}}^{*}-{\bm{y}})=0.$
(35)

Consider the point
${\bm{y}}^{\prime}={\bm{y}}^{*}+\frac{\xi}{2N}({\bm{y}}-{\bm{y}}^{*})$ (recall
the definition of $\xi$ in Definition 2 and that $0<\xi\leq 2$), which is a
convex combination of ${\bm{y}}^{*}$ and ${\bm{y}}$, and hence
${\bm{y}}^{\prime}\in{\mathcal{Y}}$. Then, for any ${{\bm{x}}\in\mathcal{X}}$,

$\displaystyle{\bm{x}}^{\top}\bm{G}{\bm{y}}^{\prime}$
$\displaystyle=\sum_{i\notin\text{supp}({\bm{x}}^{*})}x_{i}(\bm{G}{\bm{y}}^{\prime})_{i}+\sum_{i\in\text{supp}({\bm{x}}^{*})}x_{i}(\bm{G}{\bm{y}}^{\prime})_{i}$
$\displaystyle\geq\sum_{i\notin\text{supp}({\bm{x}}^{*})}\big{(}x_{i}(\bm{G}{\bm{y}}^{*})_{i}-x_{i}\|{\bm{y}}^{\prime}-{\bm{y}}^{*}\|_{1}\big{)}+\sum_{i\in\text{supp}({\bm{x}}^{*})}\left(\frac{\xi}{2}\cdot
x_{i}(\bm{G}({\bm{y}}-{\bm{y}}^{*}))_{i}+x_{i}(\bm{G}{\bm{y}}^{*})_{i}\right)$
(using $G_{ij}\in[-1,1]$ for the first part and
${\bm{y}}^{\prime}={\bm{y}}^{*}+\frac{\xi}{2N}({\bm{y}}-{\bm{y}}^{*})$ for the
second)
$\displaystyle\geq\sum_{i\notin\text{supp}({\bm{x}}^{*})}\big{(}x_{i}(\bm{G}{\bm{y}}^{*})_{i}-x_{i}\|{\bm{y}}^{\prime}-{\bm{y}}^{*}\|_{1}\big{)}+\sum_{i\in\text{supp}({\bm{x}}^{*})}x_{i}\left(V^{*}_{h(i)}-\sum_{g\in\mathcal{H}_{i}}V^{*}_{g}\right),$

where the last inequality is due to Eq. (35) and Lemma 13. We continue to
bound the terms above, which are bounded by

$\displaystyle\geq\sum_{i\notin\text{supp}({\bm{x}}^{*})}\big{(}x_{i}\left((\bm{G}{\bm{y}}^{*})_{i}-\xi\right)\big{)}+\sum_{i\in\text{supp}({\bm{x}}^{*})}x_{i}\left(V^{*}_{h(i)}-\sum_{g\in\mathcal{H}_{i}}V^{*}_{g}\right)$
(using ${\bm{y}}^{\prime}-{\bm{y}}^{*}=\frac{\xi}{2N}({\bm{y}}-{\bm{y}}^{*})$
and $\|{\bm{y}}-{\bm{y}}^{*}\|_{1}\leq 2N$)
$\displaystyle\geq\sum_{i\notin\text{supp}({\bm{x}}^{*})}x_{i}\left(V^{*}_{h(i)}-\sum_{g\in\mathcal{H}_{i}}V^{*}_{g}\right)+\sum_{i\in\text{supp}({\bm{x}}^{*})}x_{i}\left(V^{*}_{h(i)}-\sum_{g\in\mathcal{H}_{i}}V^{*}_{g}\right)$
(by the definition of $\xi$)
$\displaystyle=\sum_{i}x_{i}\left(V^{*}_{h(i)}-\sum_{g\in\mathcal{H}_{i}}V^{*}_{g}\right).$

The last term can be writen as the matrix form
${\bm{x}}^{\top}\bm{A}^{\top}\bm{V}^{*}=\mathbf{e}^{\top}\bm{V}^{*}=V_{0}^{*}$.
This shows that
$\min_{{\bm{x}}\in\mathcal{X}}{\bm{x}}^{\top}\bm{G}{\bm{y}}^{\prime}\geq
V_{0}^{*}$, that is, ${\bm{y}}^{\prime}\neq{\bm{y}}^{*}$ is also a maximin
point, contradicting the uniqueness assumption. Therefore, $c_{y}>0$ has to
hold, and so does $c_{x}>0$ by the same argument. ∎

We continue to define more constants in the following.

######  Definition 4.

Define constants $z_{\min}\triangleq\min_{i}{\widehat{z}_{1,i}}\in(0,1]$,

$\displaystyle\epsilon_{{\text{van}}}\triangleq\min_{j\in\text{supp}({{\bm{z}}^{*}})}\exp\left(-\frac{P(1+\ln(1/z_{\min}))}{z_{j}^{*}}\right)\in(0,1),$
$\displaystyle\epsilon_{\text{dil}}\triangleq\min_{j\in\text{supp}({{\bm{z}}^{*}})}\left\\{{z^{*}_{j}}\cdot\exp\left(-\frac{\|\alpha\|_{\infty}P^{2}\ln\left(1/z_{\min}\right)}{z_{j}^{*}}\right)\cdot\left(\frac{3}{4}\right)^{P}\right\\}\in(0,1).$

For all $i\in\text{supp}({\bm{z}}^{*})$, we will show that
$\epsilon_{{\text{van}}}$ is a lower bound of $\widehat{z}_{t,i}$ for VOMWU,
while $\epsilon_{\text{dil}}$ is a lower bound of $\widehat{z}_{t,i}$ and
$z_{t,i}$ for DOMWU. We show the results in Lemma 20 and defer the proof
there.

####  E.1.3 Proof of Lemma 12

We are almost ready to prove Lemma 12. Before that, we first show the
following auxiliary lemma.

######  Lemma 15.

For any ${\bm{z}}\in\mathcal{Z}$, we have

$\max_{{\bm{z}}^{\prime}\in\mathcal{V}^{*}(\mathcal{Z})}F({\bm{z}})^{\top}({\bm{z}}-{\bm{z}}^{\prime})\geq
C\|{\bm{z}}^{*}-{\bm{z}}\|_{1},$

for $C=\min\\{c_{x},c_{y}\\}\in(0,1]$.

###### Proof.

Recall that $V^{*}_{0}={{\bm{x}}^{*}}^{\top}\bm{G}{\bm{y}}^{*}$ is the game
value and note that

$\displaystyle\max_{{\bm{z}}^{\prime}\in\mathcal{V}^{*}(\mathcal{Z})}F({\bm{z}})^{\top}({\bm{z}}-{\bm{z}}^{\prime})$
$\displaystyle=\max_{{\bm{z}}^{\prime}\in\mathcal{V}^{*}(\mathcal{Z})}({\bm{x}}-{\bm{x}}^{\prime})^{\top}\bm{G}{\bm{y}}+{\bm{x}}^{\top}\bm{G}({\bm{y}}^{\prime}-{\bm{y}})=\max_{{\bm{z}}^{\prime}\in\mathcal{V}^{*}(\mathcal{Z})}-{\bm{x}}^{\prime\top}\bm{G}{\bm{y}}+{\bm{x}}^{\top}\bm{G}{\bm{y}}^{\prime}$
$\displaystyle=\max_{{\bm{x}}^{\prime}\in\mathcal{V}^{*}(\mathcal{X})}\left(V_{0}^{*}-{\bm{x}}^{\prime\top}\bm{G}{\bm{y}}\right)+\max_{{\bm{y}}^{\prime}\in\mathcal{V}^{*}(\mathcal{Y})}\left({\bm{x}}^{\top}\bm{G}{\bm{y}}^{\prime}-V_{0}^{*}\right)$
$\displaystyle=\max_{{\bm{x}}^{\prime}\in\mathcal{V}^{*}(\mathcal{X})}{\bm{x}}^{\prime\top}\bm{G}({\bm{y}}^{*}-{\bm{y}})+\max_{{\bm{y}}^{\prime}\in\mathcal{V}^{*}(\mathcal{Y})}({\bm{x}}-{\bm{x}}^{*})^{\top}\bm{G}{\bm{y}}^{\prime}$
$\displaystyle\geq
c_{y}\|{\bm{y}}^{*}-{\bm{y}}\|_{1}+c_{x}\|{\bm{x}}^{*}-{\bm{x}}\|_{1}$ (by
Definition 3)
$\displaystyle\geq\min\\{c_{x},c_{y}\\}\|{\bm{z}}^{*}-{\bm{z}}\|_{1},$

where the third equality is due to Eq. (29),
${\bm{x}}^{\prime}\in\mathcal{V}^{*}(\mathcal{X})$, and

$V^{*}_{0}=\bm{e}^{\top}\bm{V}^{*}=({\bm{x}}^{\prime\top}\bm{A}^{\top})\bm{V}^{*}={\bm{x}}^{\prime\top}(\bm{A}^{\top}\bm{V}^{*})={\bm{x}}^{\prime\top}(\bm{G}{\bm{y}}^{*});$

the case for ${\bm{y}}^{\prime}$ is similar. This completes the proof. ∎

Now we show the proof of Lemma 12.

###### Proof of Lemma 12.

Below we consider any ${\bm{z}}^{\prime}\in\mathcal{Z}$ such that
$\text{supp}({\bm{z}}^{\prime})\subseteq\text{supp}({\bm{z}}^{*})$, that is,
${\bm{z}}^{\prime}\in\mathcal{V}^{*}(\mathcal{Z})$. Considering Eq. (2) , and
using the first-order optimality condition of $\widehat{\bm{z}}_{t+1}$, we
have

$\displaystyle(\nabla\psi(\widehat{\bm{z}}_{t+1})-\nabla\psi(\widehat{\bm{z}}_{t})+\eta
F({\bm{z}}_{t}))^{\top}({\bm{z}}^{\prime}-\widehat{\bm{z}}_{t+1})\geq 0.$ (36)

Rearranging the terms and we get

$\displaystyle\eta
F\left({\bm{z}}_{t}\right)^{\top}\left(\widehat{\bm{z}}_{t+1}-{\bm{z}}^{\prime}\right)\leq\left(\nabla\psi(\widehat{\bm{z}}_{t+1})-\nabla\psi(\widehat{\bm{z}}_{t})\right)^{\top}\left({\bm{z}}^{\prime}-\widehat{\bm{z}}_{t+1}\right).$
(37)

The left hand side of Eq. (37) is lower bounded as

$\displaystyle\eta
F\left({\bm{z}}_{t}\right)^{\top}\left(\widehat{\bm{z}}_{t+1}-{\bm{z}}^{\prime}\right)$
$\displaystyle=\eta
F\left(\widehat{\bm{z}}_{t+1}\right)^{\top}\left(\widehat{\bm{z}}_{t+1}-{\bm{z}}^{\prime}\right)+\eta\left(F\left({\bm{z}}_{t}\right)-F\left(\widehat{\bm{z}}_{t+1}\right)\right)^{\top}\left(\widehat{\bm{z}}_{t+1}-{\bm{z}}^{\prime}\right)$
$\displaystyle\geq\eta
F\left(\widehat{\bm{z}}_{t+1}\right)^{\top}\left(\widehat{\bm{z}}_{t+1}-{\bm{z}}^{\prime}\right)-\eta\|F\left({\bm{z}}_{t}\right)-F\left(\widehat{\bm{z}}_{t+1}\right)\|_{\infty}\|\widehat{\bm{z}}_{t+1}-{\bm{z}}^{\prime}\|_{1}$
$\displaystyle\geq\eta
F\left(\widehat{\bm{z}}_{t+1}\right)^{\top}\left(\widehat{\bm{z}}_{t+1}-{\bm{z}}^{\prime}\right)-2P\eta\left\|{\bm{z}}_{t}-\widehat{\bm{z}}_{t+1}\right\|_{1}$
$\displaystyle\geq\eta
F\left(\widehat{\bm{z}}_{t+1}\right)^{\top}\left(\widehat{\bm{z}}_{t+1}-{\bm{z}}^{\prime}\right)-\frac{1}{4}\left\|{\bm{z}}_{t}-\widehat{\bm{z}}_{t+1}\right\|_{1};$
($\eta\leq 1/(8P)$)

When $\psi=\Psi^{\text{van}}$, we have

$\displaystyle(\nabla\Psi^{\text{van}}(\widehat{\bm{z}}_{t+1})-\nabla\Psi^{\text{van}}(\widehat{\bm{z}}_{t}))_{i}=(1+\ln\widehat{z}_{t+1,i})-(1+\ln\widehat{z}_{t,i})=\ln\frac{\widehat{z}_{t+1,i}}{\widehat{z}_{t,i}}.$
(38)

On the other hand, when $\psi=\Psi^{\text{dil}}_{{\bm{\alpha}}}$, by Eq. (23),
we have

$\displaystyle\left(\nabla\Psi^{\text{dil}}_{{\bm{\alpha}}}(\widehat{\bm{z}}_{t+1})-\nabla\Psi^{\text{dil}}_{{\bm{\alpha}}}(\widehat{\bm{z}}_{t})\right)_{i}=\alpha_{i}\ln\frac{\widehat{q}_{t+1,i}}{\widehat{q}_{t,i}}.$
(39)

Therefore, the right hand side of Eq. (37) for VOMWU is upper bounded by

$\displaystyle\left(\nabla\Psi^{\text{van}}(\widehat{\bm{z}}_{t+1})-\nabla\Psi^{\text{van}}(\widehat{\bm{z}}_{t})\right)^{\top}\left({\bm{z}}^{\prime}-\widehat{\bm{z}}_{t+1}\right)$
$\displaystyle=\sum_{i}\left(z^{\prime}_{i}-\widehat{z}_{t+1,i}\right)\ln\frac{\widehat{z}_{t+1,i}}{\widehat{z}_{t,i}}$
(Eq. (38))
$\displaystyle\leq\|\widehat{\bm{z}}_{t+1}-\widehat{\bm{z}}_{t}\|_{1}-D_{\Psi^{\text{van}}}(\widehat{\bm{z}}_{t+1},\widehat{\bm{z}}_{t})+\sum_{i\in\text{supp}({\bm{z}}^{*})}z^{\prime}_{i}\ln\frac{\widehat{z}_{t+1,i}}{\widehat{z}_{t,i}}$
($\text{supp}({\bm{z}}^{\prime})\subseteq\text{supp}({\bm{z}}^{*})$)
$\displaystyle\leq\|\widehat{\bm{z}}_{t+1}-\widehat{\bm{z}}_{t}\|_{1}+\sum_{i\in\text{supp}({\bm{z}}^{*})}\left|\ln\frac{\widehat{z}_{t+1,i}}{\widehat{z}_{t,i}}\right|$
$\displaystyle\leq\|\widehat{\bm{z}}_{t+1}-\widehat{\bm{z}}_{t}\|_{1}+\sum_{i\in\text{supp}({\bm{z}}^{*})}\ln\left(1+\frac{\left|{\widehat{z}_{t+1,i}}-{\widehat{z}_{t,i}}\right|}{\min\\{\widehat{z}_{t+1,i},\widehat{z}_{t,i}\\}}\right)$
$\displaystyle\leq\|\widehat{\bm{z}}_{t+1}-\widehat{\bm{z}}_{t}\|_{1}+\sum_{i\in\text{supp}({\bm{z}}^{*})}\frac{\left|{\widehat{z}_{t+1,i}}-{\widehat{z}_{t,i}}\right|}{\min\\{\widehat{z}_{t+1,i},\widehat{z}_{t,i}\\}}$
($\ln(1+a)\leq a$)
$\displaystyle\leq\frac{2}{\epsilon_{{\text{van}}}}\|\widehat{\bm{z}}_{t+1}-\widehat{\bm{z}}_{t}\|_{1};$
(Lemma 20 and $\epsilon_{{\text{van}}}\leq 1$)

on the other hand, the right hand side of Eq. (37) for DOMWU is upper bounded
by

$\displaystyle\left(\nabla\Psi^{\text{dil}}_{{\bm{\alpha}}}(\widehat{\bm{z}}_{t+1})-\nabla\Psi^{\text{dil}}_{{\bm{\alpha}}}(\widehat{\bm{z}}_{t})\right)^{\top}\left({\bm{z}}^{\prime}-\widehat{\bm{z}}_{t+1}\right)$
$\displaystyle=\sum_{i}\alpha_{i}\left(z^{\prime}_{i}-\widehat{z}_{t+1,i}\right)\ln\frac{\widehat{q}_{t+1,i}}{\widehat{q}_{t,i}}$
(Eq. (39))
$\displaystyle=\sum_{i}\alpha_{i}z^{\prime}_{i}\ln\frac{\widehat{q}_{t+1,i}}{\widehat{q}_{t,i}}-\sum_{i}\alpha_{i}\widehat{z}_{t+1,i}\ln\frac{\widehat{q}_{t+1,i}}{\widehat{q}_{t,i}}$
$\displaystyle=\sum_{i\in\text{supp}({\bm{z}}^{*})}\alpha_{i}z^{\prime}_{i}\ln\frac{\widehat{q}_{t+1,i}}{\widehat{q}_{t,i}}-\sum_{h\in\mathcal{H}^{\mathcal{Z}}}\alpha_{h}\widehat{z}_{t+1,\sigma(h)}\sum_{j\in\Omega_{h}}\widehat{q}_{t+1,j}\ln\frac{\widehat{q}_{t+1,j}}{\widehat{q}_{t,j}}$
$\displaystyle\leq\|{\bm{\alpha}}\|_{\infty}\sum_{i\in\text{supp}({\bm{z}}^{*})}\left|\ln\frac{\widehat{q}_{t+1,i}}{\widehat{q}_{t,i}}\right|$
($\sum_{j\in\Omega_{h}}\widehat{q}_{t+1,j}\ln\frac{\widehat{q}_{t+1,j}}{\widehat{q}_{t,j}}\geq
0$)
$\displaystyle\leq\|{\bm{\alpha}}\|_{\infty}\sum_{i\in\text{supp}({\bm{z}}^{*})}\ln\left(1+\frac{\left|{\widehat{q}_{t+1,i}}-{\widehat{q}_{t,i}}\right|}{\min\\{\widehat{q}_{t+1,i},\widehat{q}_{t,i}\\}}\right)$
$\displaystyle\leq\|{\bm{\alpha}}\|_{\infty}\sum_{i\in\text{supp}({\bm{z}}^{*})}\frac{\left|{\widehat{q}_{t+1,i}}-{\widehat{q}_{t,i}}\right|}{\min\\{\widehat{q}_{t+1,i},\widehat{q}_{t,i}\\}}$
($\ln(1+a)\leq a$)
$\displaystyle\leq\frac{\|{\bm{\alpha}}\|_{\infty}}{\epsilon_{\text{dil}}}\sum_{i\in\text{supp}({\bm{z}}^{*})}{\left|{\widehat{q}_{t+1,i}}-{\widehat{q}_{t,i}}\right|}.$
(Lemma 20)

Since ${\bm{z}}^{\prime}$ can be chosen as any point in
$\mathcal{V}^{*}(\mathcal{Z})$, we further lower bound the left-hand side of
Eq. (37) using Lemma 15 and get for VOMWU,

$\displaystyle\eta C\|{\bm{z}}^{*}-\widehat{\bm{z}}_{t+1}\|_{1}$
$\displaystyle\leq\frac{2}{\epsilon_{{\text{van}}}}\|\widehat{\bm{z}}_{t+1}-\widehat{\bm{z}}_{t}\|_{1}+\frac{\|{\bm{z}}_{t}-\widehat{\bm{z}}_{t+1}\|_{1}}{4}$
$\displaystyle\leq\frac{2}{\epsilon_{{\text{van}}}}\left(\|\widehat{\bm{z}}_{t+1}-\widehat{\bm{z}}_{t}\|_{1}+\|{\bm{z}}_{t}-\widehat{\bm{z}}_{t+1}\|_{1}\right),$
(40)

and for DOMWU,

$\displaystyle\eta C\|{\bm{z}}^{*}-\widehat{\bm{z}}_{t+1}\|_{1}$
$\displaystyle\leq\frac{1}{4}\|{\bm{z}}_{t}-\widehat{\bm{z}}_{t+1}\|_{1}+\frac{\|{\bm{\alpha}}\|_{\infty}}{\epsilon_{\text{dil}}}\sum_{i\in\text{supp}({\bm{z}}^{*})}{|\widehat{q}_{t+1,i}-\widehat{q}_{t,i}|},$
(Lemma 20)
$\displaystyle\leq\frac{1}{4}\|{\bm{z}}_{t}-\widehat{\bm{z}}_{t+1}\|_{1}+\frac{\|{\bm{\alpha}}\|_{\infty}}{\epsilon_{\text{dil}}}\sum_{i\in\text{supp}({\bm{z}}^{*})}\frac{|\widehat{z}_{t+1,i}-\widehat{z}_{t,i}|}{\widehat{z}_{t+1,p_{i}}}+\widehat{z}_{t,i}\frac{|\widehat{z}_{t+1,p_{i}}-\widehat{z}_{t,p_{i}}|}{\widehat{z}_{t+1,p_{i}}\widehat{z}_{t,p_{i}}}$
$\displaystyle\leq\frac{1}{4}\|{\bm{z}}_{t}-\widehat{\bm{z}}_{t+1}\|_{1}+\frac{\|{\bm{\alpha}}\|_{\infty}}{\epsilon_{\text{dil}}^{2}}\sum_{i\in\text{supp}({\bm{z}}^{*})}{|\widehat{z}_{t+1,i}-\widehat{z}_{t,i}|}+{|\widehat{z}_{t+1,p_{i}}-\widehat{z}_{t,p_{i}}|}$
(Lemma 20)
$\displaystyle\leq\frac{1}{4}\|{\bm{z}}_{t}-\widehat{\bm{z}}_{t+1}\|_{1}+\frac{P\|{\bm{\alpha}}\|_{\infty}}{\epsilon_{\text{dil}}^{2}}\|\widehat{\bm{z}}_{t+1}-\widehat{\bm{z}}_{t}\|_{1}$
$\displaystyle\leq\left(\frac{1}{4}+\frac{P\|{\bm{\alpha}}\|_{\infty}}{\epsilon_{\text{dil}}^{2}}\right)\left(\|\widehat{\bm{z}}_{t+1}-\widehat{\bm{z}}_{t}\|_{1}+\|{\bm{z}}_{t}-\widehat{\bm{z}}_{t+1}\|_{1}\right).$
(41)

Squaring both sides of Eq. (40), we get

$\displaystyle\eta^{2}C^{2}\|{\bm{z}}^{*}-\widehat{\bm{z}}_{t+1}\|_{1}^{2}$
$\displaystyle\leq\frac{4}{\epsilon_{{\text{van}}}^{2}}\left(\|\widehat{\bm{z}}_{t+1}-\widehat{\bm{z}}_{t}\|_{1}+\|{\bm{z}}_{t}-\widehat{\bm{z}}_{t+1}\|_{1}\right)^{2}$
$\displaystyle\leq\frac{8}{\epsilon_{{\text{van}}}^{2}}\left(\|\widehat{\bm{z}}_{t+1}-\widehat{\bm{z}}_{t}\|_{1}^{2}+\|{\bm{z}}_{t}-\widehat{\bm{z}}_{t+1}\|_{1}^{2}\right).$
(42)

Using the strong convexity of the regularizers, the left hand side of Eq. (25)
can be bounded by

$\displaystyle
D_{\psi}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t})+D_{\psi}({\bm{z}}_{t},\widehat{\bm{z}}_{t})$
$\displaystyle\geq\frac{1}{2}\|\widehat{\bm{z}}_{t+1}-{\bm{z}}_{t}\|_{1}^{2}+\frac{1}{2}\|{\bm{z}}_{t}-\widehat{\bm{z}}_{t}\|_{1}^{2}$
($a^{2}+b^{2}\geq\frac{1}{2}(a+b)^{2}$)
$\displaystyle\geq\frac{1}{8}\|\widehat{\bm{z}}_{t+1}-{\bm{z}}_{t}\|_{1}^{2}+\frac{1}{4}\left(\|\widehat{\bm{z}}_{t+1}-{\bm{z}}_{t}\|_{1}^{2}+\|{\bm{z}}_{t}-\widehat{\bm{z}}_{t}\|_{1}^{2}\right)$
$\displaystyle\geq\frac{1}{8}\left(\|\widehat{\bm{z}}_{t+1}-\widehat{\bm{z}}_{t}\|_{1}^{2}+\|\widehat{\bm{z}}_{t+1}-{\bm{z}}_{t}\|_{1}^{2}\right)$
($a^{2}+b^{2}\geq\frac{1}{2}(a+b)^{2}$ and triangle inequality)

Combining this with Eq. (41) finishes the proof for VOMWU. The similar
argument works for DOMWU by combining the inequality above with Eq. (42). ∎

###  E.2 Proofs of Eq. (12) and Eq. (13)

In this subsection, we prove Eq. (12) and Eq. (13). We first show Lemma 16 and
Lemma 17. Then we get Eq. (12) and Eq. (13) by substituting ${\bm{z}}$ with
$\widehat{\bm{z}}_{t+1}$ in these lemmas.

######  Lemma 16.

For any ${\bm{z}}\in\mathcal{Z}$, we have

$\displaystyle D_{\Psi^{\text{van}}}({\bm{z}}^{*},{\bm{z}})$
$\displaystyle\leq\sum_{i\in\text{supp}({\bm{z}}^{*})}\frac{(z^{*}_{i}-z_{i})^{2}}{\min_{i\in\text{supp}({\bm{z}}^{*})}z_{i}}+\sum_{i\notin\text{supp}({\bm{z}}^{*})}z_{i}\leq\frac{3P\|{\bm{z}}^{*}-{\bm{z}}\|}{\min_{i\in\text{supp}({\bm{z}}^{*})}z_{i}}.$

###### Proof.

By Eq. (14), we have

$\displaystyle D_{\Psi^{\text{van}}}({\bm{z}}^{*},{\bm{z}})$
$\displaystyle\leq\sum_{i}\frac{(z^{*}_{i}-z_{i})^{2}}{z_{i}}\leq\sum_{i\in\text{supp}({\bm{z}}^{*})}\frac{(z^{*}_{i}-z_{i})^{2}}{\min_{i\in\text{supp}({\bm{z}}^{*})}z_{i}}+\sum_{i\notin\text{supp}({\bm{z}}^{*})}z_{i}$
$\displaystyle\leq\frac{\|{\bm{z}}^{*}-{\bm{z}}\|^{2}}{\min_{i\in\text{supp}({\bm{z}}^{*})}z_{i}}+\|{\bm{z}}^{*}-{\bm{z}}\|_{1}\leq\frac{3P\|{\bm{z}}^{*}-{\bm{z}}\|}{\min_{i\in\text{supp}({\bm{z}}^{*})}z_{i}},$

where the last inequality is because $\|{\bm{z}}^{*}-{\bm{z}}\|\leq 2P$ and
$\|{\bm{z}}^{*}-{\bm{z}}\|_{1}\leq P\|{\bm{z}}^{*}-{\bm{z}}\|$. ∎

######  Lemma 17.

For any ${\bm{z}}\in\mathcal{Z}$, we have

$D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}}^{*},{\bm{z}})\leq\|{\bm{\alpha}}\|_{\infty}\left(\sum_{i\in\text{supp}({\bm{z}}^{*})}\frac{4P}{z_{i}^{*}}\frac{\left({z^{*}_{i}-z_{i}}\right)^{2}}{q_{i}}+\sum_{i\notin\text{supp}({\bm{z}}^{*})}z_{p_{i}}^{*}q_{i}\right)\leq\frac{4P\|{\bm{\alpha}}\|_{\infty}}{\min_{i\in\text{supp}({\bm{z}}^{*})}z_{i}^{*}z_{i}}\|{\bm{z}}^{*}-{\bm{z}}\|_{1}.$

###### Proof.

By direction calculation and [Wei et al., 2021, Lemma 16], we have

$\displaystyle D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}}^{*},{\bm{z}})$
$\displaystyle=\sum_{i}\alpha_{h(i)}z_{p_{i}}^{*}q^{*}_{i}\ln\left(\frac{q^{*}_{i}}{q_{i}}\right)$
(Eq. (24))
$\displaystyle\leq\|{\bm{\alpha}}\|_{\infty}\sum_{i}z_{p_{i}}^{*}\left(\mathbbm{1}\\{i\in\text{supp}({\bm{z}}^{*})\\}\frac{(q^{*}_{i}-q_{i})^{2}}{q_{i}}+\mathbbm{1}\\{i\notin\text{supp}({\bm{z}}^{*})\\}q_{i}\right)$
$\displaystyle\leq\|{\bm{\alpha}}\|_{\infty}\sum_{i\in\text{supp}({\bm{z}}^{*})}\frac{2z_{p_{i}}^{*}}{q_{i}}\left(\left(\frac{z^{*}_{i}-z_{i}}{z_{p_{i}}^{*}}\right)^{2}+\left(\frac{z_{i}}{z_{p_{i}}^{*}}-\frac{z_{i}}{z_{p_{i}}}\right)^{2}\right)+\|{\bm{\alpha}}\|_{\infty}\sum_{i\notin\text{supp}({\bm{z}}^{*})}z_{p_{i}}^{*}q_{i}$
$\displaystyle=\|{\bm{\alpha}}\|_{\infty}\sum_{i\in\text{supp}({\bm{z}}^{*})}\left(\frac{2}{q_{i}z_{p_{i}}^{*}}\left({z^{*}_{i}-z_{i}}\right)^{2}+\frac{2q_{i}}{z_{p_{i}}^{*}}\left({z_{p_{i}}^{*}}-{z_{p_{i}}}\right)^{2}\right)+\|{\bm{\alpha}}\|_{\infty}\sum_{i\notin\text{supp}({\bm{z}}^{*})}z_{p_{i}}^{*}q_{i}$
$\displaystyle\leq\|{\bm{\alpha}}\|_{\infty}\sum_{i\in\text{supp}({\bm{z}}^{*})}\left(\frac{2}{z_{p_{i}}^{*}}\frac{\left({z^{*}_{i}-z_{i}}\right)^{2}}{q_{i}}+\frac{2P}{z_{i}^{*}}{\left({z^{*}_{i}-z_{i}}\right)^{2}}\right)+\|{\bm{\alpha}}\|_{\infty}\sum_{i\notin\text{supp}({\bm{z}}^{*})}z_{p_{i}}^{*}q_{i}$
($p_{i}\in\text{supp}({\bm{z}}^{*})$ for all $i\in\text{supp}({\bm{z}}^{*})$)
$\displaystyle\leq\|{\bm{\alpha}}\|_{\infty}\sum_{i\in\text{supp}({\bm{z}}^{*})}\left(\frac{4P}{z_{i}^{*}}\frac{\left({z^{*}_{i}-z_{i}}\right)^{2}}{q_{i}}\right)+\|{\bm{\alpha}}\|_{\infty}\sum_{i\notin\text{supp}({\bm{z}}^{*})}z_{p_{i}}^{*}q_{i}.$

This proves the first inequality. The second equality in the lemma follows
from

$\displaystyle D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}}^{*},{\bm{z}})$
$\displaystyle\leq\|{\bm{\alpha}}\|_{\infty}\sum_{i\in\text{supp}({\bm{z}}^{*})}\left(\frac{4P}{z_{i}^{*}}\frac{\left({z^{*}_{i}-z_{i}}\right)^{2}}{q_{i}}\right)+\|{\bm{\alpha}}\|_{\infty}\sum_{i\notin\text{supp}({\bm{z}}^{*})}z_{p_{i}}^{*}q_{i}$
$\displaystyle\leq\|{\bm{\alpha}}\|_{\infty}\sum_{i\in\text{supp}({\bm{z}}^{*})}\left(\frac{4P}{z_{i}^{*}z_{i}}\right)\left|{z^{*}_{i}-z_{i}}\right|+\|{\bm{\alpha}}\|_{\infty}\sum_{i\notin\text{supp}({\bm{z}}^{*})}\frac{z_{p_{i}}^{*}z_{i}}{z_{p_{i}}}$
($|z^{*}_{i}-z_{i}|\leq 1$)
$\displaystyle\leq\|{\bm{\alpha}}\|_{\infty}\sum_{i\in\text{supp}({\bm{z}}^{*})}\left(\frac{4P}{z_{i}^{*}z_{i}}\right)\left|{z^{*}_{i}-z_{i}}\right|+\|{\bm{\alpha}}\|_{\infty}\sum_{i\notin\text{supp}({\bm{z}}^{*})}\frac{\mathbbm{1}\\{p_{i}\in\text{supp}({\bm{z}}^{*})\\}}{z_{p_{i}}}\cdot|z_{i}-0|$
$\displaystyle\leq\frac{4P\|{\bm{\alpha}}\|_{\infty}}{\min_{i\in\text{supp}({\bm{z}}^{*})}z_{i}^{*}z_{i}}\|{\bm{z}}^{*}-{\bm{z}}\|_{1}.$

∎

###  E.3 Lower Bounds on the Probability Masses

In this subsection, we show for all $i\in\text{supp}({\bm{z}}^{*})$ and $t$,
$\widehat{z}_{t,i}$ computed by VOMWU can be lower bounded by
$\epsilon_{{\text{van}}}$, while $\widehat{z}_{t,i}$ and $z_{t,i}$ computed by
DOMWU can be lower bounded by $\epsilon_{\text{dil}}$, where
$\epsilon_{{\text{van}}}$ and $\epsilon_{\text{dil}}$ are defined in
Definition 4. We state the results in Lemma 19 and Lemma 20, respectively. We
first state the stability of $\widehat{\bm{q}}_{t}$ and ${\bm{q}}_{t}$, which
directly follows from the stability of OMWU on simplex, for example, [Wei et
al., 2021, Lemma 17].

######  Lemma 18.

For $\eta\leq\frac{1}{8P}$, DOMWU guarantees $\frac{3}{4}\widehat{q}_{t,i}\leq
q_{t,i}\leq\frac{4}{3}\widehat{q}_{t,i}$ and
$\frac{3}{4}\widehat{q}_{t,i}\leq\widehat{q}_{t+1,i}\leq\frac{4}{3}\widehat{q}_{t,i}$.

######  Lemma 19.

For all $i\in\text{supp}({\bm{z}}^{*})$ and $t$, VOMWU guarantees that
$\widehat{z}_{t,i}\geq\epsilon_{{\text{van}}}$.

###### Proof.

Using Eq. (5), we have

$\displaystyle
D_{\psi}({\bm{z}}^{*},\widehat{\bm{z}}_{t})\leq\Theta_{t}\leq\cdots\leq\Theta_{1}=\tfrac{1}{16}D_{\psi}(\widehat{\bm{z}}_{1},{\bm{z}}_{0})+D_{\psi}({\bm{z}}^{*},\widehat{\bm{z}}_{1})=D_{\psi}({\bm{z}}^{*},\widehat{\bm{z}}_{1}),$
(43)

where the last equality is because $\widehat{\bm{z}}_{1}={\bm{z}}_{0}$. Thus,
$D_{\Psi^{\text{van}}}({\bm{z}}^{*},\widehat{\bm{z}}_{t})\leq
D_{\Psi^{\text{van}}}({\bm{z}}^{*},\widehat{\bm{z}}_{1})$. Then, for any
$i\in\text{supp}({\bm{z}}^{*})$, we have

$\displaystyle z_{i}^{*}\ln\frac{1}{\widehat{z}_{t,i}}$
$\displaystyle\leq\sum_{j}z_{j}^{*}\ln\frac{1}{\widehat{z}_{t,j}}=D_{\Psi^{\text{van}}}({\bm{z}}^{*},\widehat{\bm{z}}_{t})+\sum_{j}\left(z_{j}^{*}-\widehat{z}_{t,j}-z_{j}^{*}\ln{z_{j}^{*}}\right)$
$\displaystyle\leq
D_{\Psi^{\text{van}}}({\bm{z}}^{*},\widehat{\bm{z}}_{1})-\sum_{j}z_{j}^{*}\ln{z_{j}^{*}}+\sum_{j}(z_{j}^{*}-\widehat{z}_{t,j})$
$\displaystyle\leq\sum_{j}z_{j}^{*}\ln\frac{1}{\widehat{z}_{1,j}}+\sum_{j}(\widehat{z}_{1,j}-\widehat{z}_{t,j})$
$\displaystyle\leq
P+\sum_{j}z_{j}^{*}\ln\frac{1}{\widehat{z}_{1,j}}=P(1+\ln(1/z_{\min})).$

Therefore, we conclude for all $t$ and $i\in\text{supp}({\bm{z}}^{*})$,
$\widehat{z}_{t,i}$ satisfies

$\widehat{z}_{t,i}\geq\exp\left(-\frac{P(1+\ln(1/z_{\min}))}{z_{i}^{*}}\right)\geq\min_{j\in\text{supp}({{\bm{z}}^{*}})}\exp\left(-\frac{P(1+\ln(1/z_{\min}))}{z_{j}^{*}}\right)=\epsilon_{{\text{van}}}.$

∎

######  Lemma 20.

For all $i\in\text{supp}({\bm{z}}^{*})$ and $t$, DOMWU guarantees that
$\widehat{q}_{t,i}\geq\widehat{z}_{t,i}\geq\epsilon_{\text{dil}}$ and
$q_{t,i}\geq z_{t,i}\geq\epsilon_{\text{dil}}$.

###### Proof.

Similar to Lemma 19, applying Eq. (43) gives
$D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}}^{*},\widehat{\bm{z}}_{t})\leq
D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}}^{*},\widehat{\bm{z}}_{1})$.
Then, for any $i\in\text{supp}({\bm{z}}^{*})$, we have

$\displaystyle z_{i}^{*}\ln\frac{1}{\widehat{q}_{t,i}}$
$\displaystyle\leq\sum_{j}\alpha_{j}z_{j}^{*}\ln\frac{1}{\widehat{q}_{t,j}}=D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}}^{*},\widehat{\bm{z}}_{t})-\sum_{j}\alpha_{j}z_{j}^{*}\ln
q_{j}^{*}\leq
D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}}^{*},\widehat{\bm{z}}_{1})-\sum_{j}\alpha_{j}z_{j}^{*}\ln{q_{j}^{*}}$
$\displaystyle=\sum_{j}\alpha_{j}z_{j}^{*}\ln\frac{1}{\widehat{q}_{1,j}}\leq\|{\bm{\alpha}}\|_{\infty}P\ln(1/z_{\min}).$

Therefore, we conclude for all $t$ and $i\in\text{supp}({\bm{z}}^{*})$,
$\widehat{q}_{t,i}$ satisfies

$\widehat{q}_{t,i}\geq\exp\left(-\frac{\|{\bm{\alpha}}\|_{\infty}P\ln(1/z_{\min})}{z_{i}^{*}}\right)\geq\min_{j\in\text{supp}({{\bm{z}}^{*}})}\exp\left(-\frac{\|{\bm{\alpha}}\|_{\infty}P\ln(1/z_{\min})}{z_{j}^{*}}\right)$

and $\widehat{z}_{t,i}$ satisfies

$\widehat{z}_{t,i}=\widehat{z}_{t,p_{i}}\widehat{q}_{t,i}=\widehat{z}_{t,p_{p_{i}}}\widehat{q}_{t,p_{i}}\widehat{q}_{t,i}\geq\prod_{j\in\text{supp}({\bm{z}}^{*})}\widehat{q}_{t,j}\geq\min_{j\in\text{supp}({{\bm{z}}^{*}})}\exp\left(-\frac{\|\alpha\|_{\infty}P\ln(1/z_{\min})}{z_{j}^{*}}\right)^{P}.$

This finishes the first part of the proof. Finally, using Lemma 18, we have
for $i\in\text{supp}({\bm{z}}^{*})$,
$q_{t,i}\geq\frac{3}{4}\widehat{q}_{t,i}\geq\epsilon_{\text{dil}}$ and

$\displaystyle
z_{t,i}\geq\prod_{j\in\text{supp}({\bm{z}}^{*})}q_{t,j}\geq\min_{j\in\text{supp}({{\bm{z}}^{*}})}\exp\left(-\frac{\|\alpha\|_{\infty}P^{2}\ln(1/z_{\min})}{z_{j}^{*}}\right)\cdot\left(\frac{3}{4}\right)^{P}\geq\epsilon_{\text{dil}}.$

∎

###  E.4 Proof of Theorem 6

Based on the results in the previous subsections and the discussion in Section
6.3, we can get $\Theta_{t}=\mathcal{O}(1/t)$ for both VOMWU and DOMWU. In
this subsection, we formally state the results in Theorem 21 for both VOMWU
and DOMWU, and show the proof by combining all the components. In particular,
the result for VOMWU implies Theorem 6.

######  Theorem 21.

Under the uniqueness assumption, VOMWU and DOMWU with step size
$\eta\leq\frac{1}{8P}$ guarantee
$D_{\Psi^{\text{van}}}({\bm{z}}^{*},\widehat{\bm{z}}_{t})\leq\frac{C_{13}}{t}$
and
$D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}}^{*},\widehat{\bm{z}}_{t})\leq\frac{C_{13}^{\prime}}{t}$,
respectively, where $C_{13}^{\prime},C_{13}>0$ are some constants depending on
the game, $\widehat{\bm{z}}_{1}$, and $\eta$.

###### Proof.

We start from Lemma 12. Using Lemma 16 and Lemma 19, the right hand side of
Eq. (25) can be bounded by

$\displaystyle\zeta_{t}$ $\displaystyle\geq
C_{12}\|{\bm{z}}^{*}-\widehat{\bm{z}}_{t+1}\|^{2}\geq\frac{\epsilon_{{\text{van}}}^{2}C_{12}}{9P^{2}}D_{\Psi^{\text{van}}}({\bm{z}}^{*},\widehat{\bm{z}}_{t+1})^{2},$
(44)

for VOMWU. Similarly, using Lemma 17 and Lemma 20, we have for DOMWU,

$\displaystyle\zeta_{t}$ $\displaystyle\geq
C_{12}\|{\bm{z}}^{*}-\widehat{\bm{z}}_{t+1}\|^{2}\geq\frac{\epsilon_{{\text{van}}}^{4}C_{12}}{16P^{2}\|{\bm{\alpha}}\|_{\infty}^{2}}D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}}^{*},\widehat{\bm{z}}_{t+1})^{2}.$

On the other hand, applying Eq. (5) repeatedly, we get

$D_{\psi}({\bm{z}}^{*},\widehat{\bm{z}}_{1})=\Theta_{1}\geq\cdots\geq\Theta_{t+1}\geq\frac{1}{16}D_{\psi}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t}).$

Thus, $\zeta_{t}\geq D_{\psi}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t})\geq
C_{10}D_{\psi}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t})^{2}$ for some $C_{10}>0$
depending on $D_{\psi}({\bm{z}}^{*},\widehat{\bm{z}}_{1})$. Combining this
with Eq. (44) gives

$\displaystyle\zeta_{t}$
$\displaystyle=\frac{1}{2}\left(D_{\psi}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t})+D_{\psi}({\bm{z}}_{t},\widehat{\bm{z}}_{t})\right)+\frac{1}{2}\left(D_{\psi}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t})+D_{\psi}({\bm{z}}_{t},\widehat{\bm{z}}_{t})\right)$
$\displaystyle\geq\frac{1}{2}\cdot\frac{\epsilon_{{\text{van}}}^{2}C_{12}}{9P^{2}}D_{\Psi^{\text{van}}}({\bm{z}}^{*},\widehat{\bm{z}}_{t+1})^{2}+\frac{1}{2}\cdot
C_{10}D_{\Psi^{\text{van}}}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t})^{2}$ (Eq.
(44)) $\displaystyle\geq\frac{\epsilon_{{\text{van}}}^{2}C_{12}}{36P^{2}}\cdot
2D_{\Psi^{\text{van}}}({\bm{z}}^{*},\widehat{\bm{z}}_{t+1})^{2}+\frac{C_{10}}{4}\cdot
2D_{\Psi^{\text{van}}}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t})^{2}$
$\displaystyle\geq\min\left\\{\frac{\epsilon_{{\text{van}}}^{2}C_{12}}{36P^{2}},\frac{C_{10}}{4}\right\\}\Theta_{t+1}^{2}\geq
C_{11}\Theta_{t+1}^{2},$

for some $C_{11}>0$. Similarly, we have $\zeta_{t}\geq
C_{11}^{\prime}\Theta_{t+1}^{2}$ for DOMWU and constant $C_{11}^{\prime}>0$.
Applying this to Eq. (5), we obtain the recursion
$\Theta_{t+1}\leq\Theta_{t}-\frac{15}{16}C_{11}\Theta_{t+1}^{2}$. This implies
$\Theta_{t}\leq\frac{C_{13}}{t}$ for some constant $C_{13}$ by [Wei et al.,
2021, Lemma 12]. With the same argument, we can prove the case for DOMWU. ∎

###  E.5 Proof of Theorem 7

####  E.5.1 The Significant Difference Lemma

In this subsection, we explain how to get the linear convergence result of
DOMWU. As we discuss in the end of Section 6.3, this requires showing that
$\sum_{i\notin\text{supp}({\bm{z}}^{*})}z_{p_{i}}^{*}\widehat{q}_{t+1,i}$
decreases significantly as $\widehat{\bm{z}}_{t}$ gets close enough to
${\bm{z}}^{*}$. The argument is shown in Lemma 24. Before that, we first show
a lemma stating that for any information set $h\in\mathcal{H}^{\mathcal{Z}}$,
indices $i,j\in\Omega_{h}$ such that $i\notin\text{supp}({\bm{z}}^{*})$ and
$j\in\text{supp}({\bm{z}}^{*})$, $\widehat{L}_{t,i}$ is significantly larger
than $\widehat{L}_{t,j}$ when $\widehat{\bm{z}}_{t}$ is close to
${\bm{z}}^{*}$.

######  Lemma 22.

Suppose
$\|{\bm{z}}^{*}-{\bm{z}}\|\leq\frac{\eta^{2}\xi\epsilon_{\text{dil}}^{2}}{40P^{3}\|{\bm{\alpha}}\|_{\infty}}$.
Then for $i\in\Omega_{h}$, $h\in\mathcal{H}^{\mathcal{X}}$, we have

$\displaystyle\forall i\in\text{supp}({\bm{x}}^{*}),$ $\displaystyle L_{i}\leq
V^{*}_{h}+\frac{\eta\xi}{10};$ $\displaystyle\forall
i\notin\text{supp}({\bm{x}}^{*}),$ $\displaystyle L_{i}\geq
V^{*}_{h}+\frac{9\eta\xi}{10},$ (45)

where
$L_{i}=(\bm{G}{\bm{y}})_{i}+\sum_{g\in\mathcal{H}_{i}}-\frac{\alpha_{g}}{\eta}\ln\left(\sum_{j\in\Omega_{g}}q_{j}\exp(-\eta
L_{j}/\alpha_{g})\right)$, $q_{j}=z_{j}/z_{p_{j}}$.

###### Proof.

We first consider terminal index $i$. By the assumption
$\|{\bm{z}}^{*}-{\bm{z}}\|\leq\frac{\eta^{2}\xi\epsilon_{\text{dil}}^{2}}{40P^{3}\|{\bm{\alpha}}\|_{\infty}}$
and Lemma 13, we have $\|{\bm{y}}-{\bm{y}}^{*}\|_{1}\leq\frac{\eta\xi}{10P}$,
and

$\displaystyle
L_{i}=(\bm{G}{\bm{y}})_{i}\leq(\bm{G}{\bm{y}}^{*})_{i}+\frac{\eta\xi}{10P}=V^{*}_{h}+\frac{\eta\xi}{10P}$
(46)

for $i\in\text{supp}({\bm{x}}^{*})$ and

$\displaystyle
L_{i}=(\bm{G}{\bm{y}})_{i}\geq(\bm{G}{\bm{y}}^{*})_{i}-\frac{\eta\xi}{10P}\geq
V^{*}_{h}+\xi-\frac{\eta\xi}{10P}\geq V^{*}_{h}+\frac{9\eta\xi}{10}$

for $i\notin\text{supp}({\bm{x}}^{*})$ by the definition of $\xi$. Therefore,
this shows Eq. (45) for terminal indices. In the following, we complete the
proof by backward induction. Specifically, for nonterminal index
$i\notin\text{supp}({\bm{x}}^{*})$, we assume $L_{j}\geq
V^{*}_{h(j)}+\frac{9\eta\xi}{10}$ for every _descendant_ $j$ (we say that
index $j$ is a descendant of index $i$ if there exists a sequence of indexes
$s_{0},\dots,s_{K}$ for some $K>0$ such that $s_{0}=j$, $s_{K}=i$, and
$p_{s_{k-1}}=s_{k}$ for every $k\in[K]$). Note that we always have
$j\notin\text{supp}({\bm{x}}^{*})$. We will prove $L_{i}$ satisfies Eq. (45),
which completes the proof for $i\notin\text{supp}({\bm{x}}^{*})$ by induction.
By assumption, we have

$\displaystyle L_{i}$
$\displaystyle=(\bm{G}{\bm{y}})_{i}+\sum_{g\in\mathcal{H}_{i}}-\frac{\alpha_{g}}{\eta}\ln\left(\sum_{j\in\Omega_{g}}q_{j}\exp(-\eta
L_{j}/\alpha_{g})\right)$
$\displaystyle\geq(\bm{G}{\bm{y}})_{i}+\sum_{g\in\mathcal{H}_{i}}-\frac{\alpha_{g}}{\eta}\ln\left(\max_{j\in\Omega_{g}}\exp(-\eta
L_{j}/\alpha_{g})\right)$
$\displaystyle=(\bm{G}{\bm{y}})_{i}+\sum_{g\in\mathcal{H}_{i}}\min_{j\in\Omega_{g}}L_{j}$
$\displaystyle\geq(\bm{G}{\bm{y}})_{i}+\sum_{g\in\mathcal{H}_{i}}V^{*}_{g}+\frac{9\eta\xi}{10}$
(by the induction hypothesis)
$\displaystyle\geq(\bm{G}{\bm{y}}^{*})_{i}-\xi+\sum_{g\in\mathcal{H}_{i}}V^{*}_{g}+\frac{9\eta\xi}{10}$
($\|{\bm{y}}-{\bm{y}}^{*}\|\leq\xi$) $\displaystyle\geq
V^{*}_{h(i)}+\frac{9\eta\xi}{10}.$ (Lemma 13)

Similarly, for nonterminal index $i\in\text{supp}({\bm{x}}^{*})$, we show for
every descendant $j$,

$\displaystyle L_{j}\leq V^{*}_{h(j)}+\frac{\eta\xi}{10P}f(h(j)),$ (47)

where $f:\mathcal{H}^{\mathcal{X}}\to\mathbb{R}^{+}$ is defined recursively as
follows. For information set (simplex) $g$ such that $\Omega_{g}$ contains
terminal indices only, we let $f(g)=1$. Otherwise, we define

$\displaystyle
f(g)=\max_{k\in\Omega_{g}}\sum_{s\in\mathcal{H}_{k}}\left(f(s)+\frac{1}{P}\right).$
(48)

This shows Eq. (45) as Lemma 23 guarantees

$f(h)\leq(P-1)\cdot\left(1+\frac{1}{P}\right)<P,$

for every simplex $h$. It remains to prove Eq. (48) by induction. For the base
case that $i$ is a terminal index, Eq. (47) clearly holds by Eq. (46). For
nonterminal index $i$, we have

$\displaystyle L_{i}$
$\displaystyle=(\bm{G}{\bm{y}})_{i}+\sum_{g\in\mathcal{H}_{i}}-\frac{\alpha_{g}}{\eta}\ln\left(\sum_{j\in\Omega_{g}}q_{j}\exp(-\eta
L_{j}/\alpha_{g})\right)$
$\displaystyle\leq(\bm{G}{\bm{y}})_{i}+\sum_{g\in\mathcal{H}_{i}}-\frac{\alpha_{g}}{\eta}\ln\left(\sum_{j\in\Omega_{g}\cap\text{supp}({\bm{x}}^{*})}q_{j}\exp(-\eta
L_{j}/\alpha_{g})\right)$
$\displaystyle\leq(\bm{G}{\bm{y}})_{i}+\sum_{g\in\mathcal{H}_{i}}-\frac{\alpha_{g}}{\eta}\ln\left[\exp\left(-\eta\left(V^{*}_{g}+\frac{\eta\xi}{10P}f(g)\right)/\alpha_{g}\right)\sum_{j\in\Omega_{g}\cap\text{supp}({\bm{x}}^{*})}q_{j}\right]$
(by the assumption)
$\displaystyle=(\bm{G}{\bm{y}})_{i}+\sum_{g\in\mathcal{H}_{i}}\left[V^{*}_{g}+\frac{\eta\xi}{20P}f(g)-\frac{\alpha_{g}}{\eta}\ln\left(\sum_{j\in\Omega_{g}\cap\text{supp}({\bm{x}}^{*})}q_{j}\right)\right].$
(49)

We continue to bound the last term. Let
$c=\frac{\eta^{2}\xi\epsilon_{\text{dil}}^{2}}{40P^{3}\|{\bm{\alpha}}\|_{\infty}}$.
We have

$\displaystyle-\frac{\alpha_{g}}{\eta}\ln\left(\sum_{j\in\Omega_{g}\cap\text{supp}({\bm{x}}^{*})}q_{j}\right)$