A Policy-Gradient Approach to Solving Imperfect-Information Games with Best-Iterate Convergence

## Abstract

Abstract Policy gradient methods have become a staple of any single-agent reinforcement learning toolbox, due to their combination of desirable properties: iterate convergence, efficient use of stochastic trajectory feedback, and theoretically-sound avoidance of importance sampling corrections. In multi-agent imperfect-information settings (extensive-form games), however, it is still unknown whether the same desiderata can be guaranteed while retaining theoretical guarantees. Instead, sound methods for extensive-form games rely on approximating counterfactual values (as opposed to Q values), which are incompatible with policy gradient methodologies.
In this paper, we investigate whether policy gradient
can be safely used
in two-player zero-sum imperfect-information extensive-form games (EFGs).
We establish positive results, showing for the first time that a policy gradient method leads to provable best-iterate convergence to a regularized Nash equilibrium in self-play.

## 1 Introduction

In recent years, deep reinforcement learning (DRL) has succeeded tremendously in many applications with large and complex environments, such as games (Mnih et al., ; Silver et al., ), autonomous driving (Kiran et al., ), robotics (Ibarz et al., ), and large language models (*e.g.* Ouyang et al. () and ChatGPT). Much of these successes are due to the applicability of scalable algorithms, such as proximal policy optimization (PPO) (Schulman et al., ) and soft actor-critic (SAC) (Haarnoja et al., ). The success of these algorithms hinges on a few critical properties—these algorithms
(I) only require value estimates obtained from repeated random rollouts which can be implemented efficiently;
(II) converge in iterates (as opposed to in averages), removing the need for either training an average policy approximator or storing snapshots of past policies; and
(III) soundly avoid importance sampling corrections, which can be detrimental in practice as they often lead to outsized reward estimates.

However, DRL is not applicable in multi-agent imperfect-information settings, such as Texas Hold’em poker, where they tend to end up trapped in cycles without making progress (Balduzzi et al., ).
Constructing policy gradient algorithms that enjoy the same wide applicability as their DRL counterparts and yet retain theoretical guarantees in tabular settings even in imperfect-information games is a challenging, open direction of research.
Current sound algorithms for competitive games typically see their scalability limited by
two major obstacles: their lack of last- (or even best-) iterate convergence, and their reliance on counterfactual values. In what follows we illustrate both of these issues separately.

Average vs iterate convergence.
In the last decade, most scalable techniques to solve Nash equilibrium strategies in two-player zero-sum imperfect-information extensive-form games (EFGs) have been based on Counterfactual Regret Minimization (CFR) (Zinkevich et al., ) and its modern variants (Tammelin et al., ; Farina et al., ; Brown and Sandholm, ; Farina et al., ). These algorithms guarantee that their *average* strategy converges to the set of Nash equilibrium (NE) strategies. However, average-iterate convergence is not desirable within the regime of deep learning, where strategies are stored indirectly as a vector of neural network weights. To represent and use the average strategy, some authors have resorted to storing in memory multiple snapshots of the network, sampling one at random; this can quickly become expensive in large games (Liu et al., )). Alternatively, some authors have included—as part of their pipeline—training a second network whose goal is approximating the average strategy (Brown et al., ; Steinberger et al., ). This approach is also undesirable, as it incurs an additional error in the approximation of the average strategy.

In light of the above discussion, a recent trend in the literature has focused on algorithms that do not require taking averages of strategies and instead converge to the set of Nash equilibrium strategies—in short, exhibit *iterate convergence*. A distinction between two forms of iterate convergence is often made: *best-iterate* convergence, meaning that at least one of the iterates produced by the algorithm is very close to equilibrium, and *last-iterate* convergence, meaning that the last iterate produced is. While this line of work has produced a wealth of algorithms with provable last-iterate convergence Daskalakis and Panageas (); Anagnostides et al. (); Wei et al. (); Lee et al. (); Cen et al. (); Liu et al. (), a major obstacle towards practical combination with function approximation has been the reliance of these algorithms on *counterfactual values*, which we discuss next.

Counterfactual values vs Q-values. Aside from the cycling effect, there is another reason that reinforcement learning, commonly based on Q-values in single-agent environments, is not applicable in EFGs, which is the fundamental *state* concept being replaced by the *information set*. Players’ expected payoffs of taking action $a$ at an information set $s$ need to consider the opponent’s reach probabilities to $s$, captured in the notion of *counterfactual values*. These are essentially Q-values multiplied by the probability of the opponent and environment reaching $s$ from the game’s root when the opponent follows their strategy.

The downsides of counterfactual values become apparent when turning the attention onto *estimation* of values. Q-values are extremely practical to estimate by performing random rollouts. For counterfactual values, several techniques have been proposed. A popular technique in this space is using importance sampling to estimate the counterfactual values (Lanctot et al., ; Farina et al., ). However, importance sampling is not suitable for DRL in large-scale environments due to the high dispersion (*i.e.*, range of values) of the produced estimator—for instance, the estimated Q-value can be as large as the game size (Bai et al., ; Fiegel et al., ).

Algorithms that sidestep the need for importance sampling, such as External Monte Carlo CFR (Lanctot et al., ), do that at the expense of exploring about square-root of the EFG size in every iteration to reduce the variance of the estimator. This is in stark contrast with DRL, which simply samples a batch of trajectories at every iteration, each with a size proportional to the height of the tree, which is typically logarithmic in the size of the game.
Techniques based on rollouts of individual trajectories (Kozuno et al., ; Bai et al., ; Fiegel et al., ) only sample a trajectory in every iteration (with size equal to the EFG height), they utilized importance sampling, potentially resulting in feedback with extremely high dispersion when the importance weight is very large, thus hindering the stable training of neural networks. Certain variance reduction techniques, such as those by Schmid et al. (), still suffer a large dispersion even though the variance is reduced.

Contributions. Given the above discussion, a question is natural:

*Is it possible to design a theoretically sound policy gradient method for solving two-player zero-sum extensive-form games that achieves the desiderata [(I)](#S1.I1.i1), [(II)](#S1.I1.i2), [(III)](#S1.I1.i3) listed in the introduction?*

Such an algorithm would enable estimating values via rollouts, without need of importance sampling, all while ensuring iterate convergence, bringing EFG technology more in line with modern DRL technology.
Our aim in this paper is to show that a positive answer to the question is possible.

In this work, we develop the first principled policy gradient approach for solving imperfect information EFGs. Our approach builds on a particular notion of Q-values for EFGs, called *trajectory Q-values*, which admits efficient estimation through random rollouts without importance sampling. Our algorithm also introduces a new regularizer for EFGs, which we coin *bidilated* regularizer. When paired with trajectory Q-values, the bidilated regularizer enables iterate convergence with both full-information and stochastic feedback obtained through the sampled trajectory. To obtain the results, we devised a novel learning rate schedule that increases with the depth of the game tree. It ensures that the strategies of ancestors are changing slower than those of the children, and are therefore stable when the children are updating their payoff estimates.

## 2 Related Work

This section compares our paper to prior literature on three aspects: convergence guarantees, notion of values used by the algorithm, and support of value estimation via rollouts. We provide a visual comparison of the most relevant algorithms in [Table 1](#S2.T1).

Convergence Guarantee. Most CFR-based algorithms (Zinkevich et al., ; Tammelin et al., ; Steinberger et al., ) only guarantee that the *average* strategy converges to a NE, though empirically some variants of CFR exhibit last-iterate convergence (Bowling et al., ; Tammelin et al., ). Motivated by the success of *Optimistic Mirror Descent* (OMD) achieving last-iterate convergence in normal-form games (NFGs) (Mertikopoulos et al., ; Wei et al., ; Cai et al., ), Farina et al. () first empirically showed that OMD also enjoys last-iterate convergence in EFGs. Then, Lee et al. () theoretically proved that *Optimistic Multiplicative Weights Update* (OMWU), an instance of OMD, converges in EFGs with unique NE assumption.

Use of Q-Values. To achieve last-iterate convergence in EFGs, additional regularization and optimism are widely used. Perolat et al. () used that approach in continuous time, using counterfactual values under full-information (*i.e.*, non-sampled) feedback. Lee et al. (); Liu et al. () achieved last-iterate convergence in EFGs using discrete-time updates, but both of their convergence results are based on counterfactual values in the non-sampled case. Sokota et al. ()’s MMD algorithm empirically observed convergence by using sampled (trajectory) Q-values in conjunction with entropic regularization, without theoretical guarantees.
In this paper, we combine regularization and optimism, and obtain a theoretically sound algorithm (QFR) for solving two-player zero-sum EFGs using sampled Q-values / trajectory Q-values.

Rollout-based estimation. Lanctot et al. () proposed Outcome-Sampling Monte-Carlo CFR (OS-MCCFR), a variant of CFR which uses random rollouts to estimate counterfactual values. Later, Farina and Sandholm (); Farina et al. (); Bai et al. (), and Fiegel et al. () proposed algorithms that converge in EFGs with trajectories at each iteration. However, those algorithms rely on importance sampling, which causes numerical instability due to the large range of feedback. ESCHER (McAleer et al., ) samples trajectories off-policy. This is usually undesirable as it favors exploring parts of the game tree according to uniform random probability, rather on focusing on those that are more likely given the policy. ARMAC (Gruslys et al., ) and ACH (Fu et al., ) support both Q-values and approximately-on-policy estimation, but like ESCHER it does not guarantee convergence of the iterates.

**Table 1: The table above compares the related work in three aspects: convergence guarantee, feedback type, and supporting sampling or not. (last) and (best) denote last-iterate convergence and best-iterate convergence, respectively.**
| Algorithm | Iterate convergence | Q-values | Stochastic feedback |
| --- | --- | --- | --- |
| Dream, Deep-CFR (Steinberger et al., ; Brown et al., ) | ✗ | ✗ | ✓ |
| OOMD, Reg-DOMD, MMD (Lee et al., ; Liu et al., ; Sokota et al., ) | ✓(last) | ✗ | ✗ |
| Adaptive FTRL (Fiegel et al., ) | ✗ | ✗ | ✓ |
| Escher (McAleer et al., ) | ✗ | ✓ | $\approx$ (off-policy) |
| Armac, ACH (Gruslys et al., ; Fu et al., ) | ✗ | ✓ | ✓ |
| QFR (this paper) | ✓(best) | ✓ | ✓ |

## 3 Preliminaries

For any vector $\bm{x}$,
we use $x_{i}$ as element $i$ of vector $\bm{x}$ and $\left\|\bm{x}\right\|_{p}$ as the $p$-norm. We let $\left\|\bm{x}\right\|$ denote the Euclidean norm $\left\|\bm{x}\right\|_{2}$. We use $\Delta^{n}$ to denote the $(n-1)$-dimensional probability simplex $\left\{\bm{x}\in[0,1]^{n}\colon\sum_{i=1}^{n}x_{i}=1\right\}$. We also define the Bregman divergence $D_{\psi}(\bm{x},\bm{y})\coloneqq\psi(\bm{x})-\psi(\bm{y})-\left\langle\nabla\psi(\bm{y}),\bm{x}-\bm{y}\right\rangle$ with respect to the $c$-strongly convex function $\psi$. The $c$-strong convexity of $\psi$ implies the bound $D_{\psi}(\bm{x},\bm{y})\geq\frac{c}{2}\left\|\bm{x}-\bm{y}\right\|^{2}$. For any integer $n\geq 0$, we use $[n]\coloneqq\left\{1,2,...,n-1,n\right\}$. For any set ${\mathcal{S}}$, we denote with $|{\mathcal{S}}|$ as its cardinality.

Extensive-Form Games.
EFGs are played on a rooted game tree, with the set of all histories (nodes) denoted as $\mathcal{H}$. In this paper we focus on two-player zero-sum EFGs; hence, each node belongs to exactly one player out of the set $\left\{1,2\right\}\cup\left\{c\right\}$. The special player $c$ is called the *chance player*, and models stochastic events (for example: a roll of the dice or dealing a card from a shuffled deck) sampled from a known distribution. We use $\mathcal{H}_{1},\mathcal{H}_{2},\mathcal{H}_{c}$ to denote the set of nodes belonging to each of the players. Terminal nodes (nodes without children) have an associated payoff for each player (the sum across player is 0 since the game is zero-sum).

To model imperfect information, the set of nodes $\mathcal{H}_{i}$ of each player $i\in[2]$ is partitioned into *information sets* (or *infosets* for short) $s_{1},s_{2},...,s_{m}$. Nodes in the same infoset are indistinguishable for the acting player of that infoset. For example, in poker player 1 cannot distinguish two nodes in the game tree that only differ on the private cards of player 2, since player 1 does not observe the hand of the opponent. We use ${\mathcal{S}}_{i}\coloneqq\left\{s_{1},s_{2},...,s_{m}\right\}$ to denote the collection of all infosets of player $i$. Let $\mathcal{H}\coloneqq\mathcal{H}_{1}\cup\mathcal{H}_{2}$ and ${\mathcal{S}}\coloneqq{\mathcal{S}}_{1}\cup{\mathcal{S}}_{2}$ be the joint set of nodes and infosets of player $1,2$ for convenience. Because nodes in the same infoset are indistinguishable from the acting player, they must all have the same action set, which we denote with $\mathcal{A}_{s}$ as the action set of infoset $s\in{\mathcal{S}}$. Furthermore, $p\colon{\mathcal{S}}\to\left\{1,2\right\}$ denotes the player that an infoset $s$ belongs to.

We make the assumption that each player remembers all their past observations and actions; this assumption is standard and goes under the name of *perfect recall*. A direct corollary of this assumption is that nodes in the same infoset $s\in{\mathcal{S}}_{i}$ have the same past observation along the path from the root to the node in the view of player $i$.
For any two nodes $h,h^{\prime}\in\mathcal{H}$, we write $h\sqsubseteq h^{\prime}$ if $h$ is on the path from the root of the game tree to $h^{\prime}$. Suppose $h\in s$ and for any $a\in\mathcal{A}_{s}$, we write $(h,a)\sqsubseteq h^{\prime}$ if the path from the root of the game tree to node $h^{\prime}$ includes the edge corresponding to taking action $a$ at $s$. For any two infosets $s,s^{\prime}\in{\mathcal{S}}_{i}$ that belong to the same player $i\in[2]$, whenever there exist two nodes $h\in s,h^{\prime}\in s^{\prime}$ such that $h\sqsubseteq h^{\prime}$, we write $s\sqsubseteq s^{\prime}$. Similarly, we write $(s,a)\sqsubseteq s^{\prime}$ where $a\in\mathcal{A}_{s}$ to mean that there exist nodes $h\in s,h^{\prime}\in s^{\prime}$ such that $(h,a)\sqsubseteq h^{\prime}$. Moreover, we can define $(s,a)\sqsubseteq(s^{\prime},a^{\prime})$ for $s,s^{\prime}\in{\mathcal{S}}_{i}$ for some $i\in[2]$ and $a\in\mathcal{A}_{s},a^{\prime}\in\mathcal{A}_{s^{\prime}}$ similarly.
Furthermore, for any player $i\in[2]$, we define the *parent sequence* $\sigma(s)$ of an infoset $s\in{\mathcal{S}}_{i}$ as the last infoset-action pair $(s^{\prime},a^{\prime})$, where $s^{\prime}\in{\mathcal{S}}_{i},a^{\prime}\in\mathcal{A}_{s^{\prime}}$, encountered along the path from root to any nodes in $s$ (the choice of node in $s$ is irrelevant and $\sigma(s)$ is either unique or non-existing due to the perfect-recall assumption
). If there does not exist such infoset-action pair, we let $\sigma(s)=\emptyset$. For any node $h\in\mathcal{H}$, we define $\sigma_{i}(h)$ as the last infoset-action pair $(s,a)$, where $s\in{\mathcal{S}}_{i}$, encountered along the path from root to $h$.
Finally, we define the *depth* $\mathcal{D}(h)$ of a node $h\in\mathcal{H}$ as the number of actions (of all players) on the path from the root of the game tree to $h$. The depth $\mathcal{D}(s)$ of an infoset $s\in{\mathcal{S}}_{i}$ is the maximum depth of any node $h\in s$.

Strategies in EFGs.
Since players cannot differentiate nodes in the same infoset, their strategies must be the same at all of them. For player $i$ and infoset $s\in{\mathcal{S}}_{i}$ (*i.e.* $p(s)=i$), we use $\pi_{i}(a{\,|\,}s)$ to denote the probability of taking action $a\in\mathcal{A}_{s}$ at any node in infoset $s$. We use $\bm{\pi}\coloneqq(\pi_{1},\pi_{2})$ to denote the strategy profile. For a player $i$, given an assignment of $\pi_{i}(a{\,|\,}s)$ for each $s\in{\mathcal{S}}_{i},a\in\mathcal{A}_{s}$, then we can represent strategies for the EFG via their *sequence-form* representation (Von Stengel, ). This is a mapping $\mu_{i}^{\pi_{i}}\colon\bigcup_{s\in{\mathcal{S}}_{i},a\in\mathcal{A}_{s}}\left\{(s,a)\right\}\to[0,1]$ associated with strategy $\pi_{i}$ for each player $i\in[2]$, where $\mu_{i}^{\pi_{i}}(s,a)\coloneqq\mu_{i}^{\pi_{i}}(\sigma(s))\cdot\pi_{i}(a{\,|\,}s)$ for any $s\in{\mathcal{S}}_{i},a\in\mathcal{A}_{s}$. Note that $\mu_{i}^{\pi_{i}}(\emptyset)=1$. For each $h\in\mathcal{H}$, according to the definition above, $\mu_{i}^{\pi_{i}}(\sigma_{1}(h))$ is equal to the product of the probability of all of Player $i$’s actions from the root of the tree down to node $h$. We use $\mu_{c}(h)$ to denote the probability of reaching $h\in\mathcal{H}$ contributed by the chance player. We assume $\mu_{c}(h)>0$ for any $h\in\mathcal{H}$, since otherwise $h$ will never be reached and thus can be removed from the game tree.

For simplicity, let $\mu_{1}^{\pi_{1}}$ to be a vector with index $(s,a)$, where $s\in{\mathcal{S}}_{i},a\in\mathcal{A}_{s}$, and $(\mu_{1}^{\pi_{1}})_{(s,a)}=\mu_{1}^{\pi_{1}}(s,a)$. In this representation, the expected utility for Player 1 is the bilinear function $(\mu_{1}^{\pi_{1}})^{\top}\bm{A}\mu_{2}^{\pi_{2}}$ (^1^11$\bm{A}\in[-1,1]^{\sum_{s\in{\mathcal{S}}_{1}}|\mathcal{A}_{s}|\times\sum_{s^{\prime}\in{\mathcal{S}}_{2}}|\mathcal{A}_{s^{\prime}}|}$ is the utility matrix of the game.) (the utility for Player 2 is $-(\mu_{1}^{\pi_{1}})^{\top}\bm{A}\mu_{2}^{\pi_{2}}$ since the game is zero-sum). We define the convex polytope of all valid sequence-form strategies as $\Pi_{1},\Pi_{2}$ for player $1,2$ respectively, and $\Pi\coloneqq\Pi_{1}\times\Pi_{2}$. For simplicity, let $\bm{\mu}^{\bm{\pi}}\coloneqq(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}})$ as the concatenation of the sequence-form strategy of both players. Sometimes, we will omit the subscript of $\mu$ when it is clear from the context, such as writing $\mu^{\pi_{p(s)}}_{p(s)}(s,\cdot)$ as $\mu^{\bm{\pi}}(s,\cdot)$.

Counterfactual and Q-Values.
In this section we recall some key notions of values for EFGs. Our exposition is mostly intuitive to avoid notational burden; all definitions can be found in [Appendix A](#A1). We start from introducing these values for *nodes* and for Player 1 (the definitions are symmetric for Player 2), and will later extend the definition to infosets.

- •
The *Q-value* $Q_{1}^{\bm{\pi}}(h,a)$ associated with strategies $\pi_{1},\pi_{2}$ for node-action pair $(h,a)$ is defined as Player 1’s expected utility in the subtree rooted at $h$, when Player 1 follows $\pi_{1}$ and Player 2 follows $\pi_{2}$ after first selecting $a$ as their first action.
- •
The *counterfactual value* $\mathsf{CF}_{1}^{\bm{\pi}}(h,a)$ is defined as the product of the corresponding Q-value with the probability that Player 2 and the chance player reach $h$; in symbols,
$\mathsf{CF}_{1}^{\bm{\pi}}(h,a)\coloneqq\mu_{2}^{\pi_{2}}(\sigma_{2}(h))\cdot\mu_{c}(h)\cdot Q_{1}^{\bm{\pi}}(h,a).$
- •
The *trajectory Q-value* $\mkern 1.5mu\overline{\mkern-1.5muQ\mkern-1.5mu}\mkern 1.5mu_{1}^{\bm{\pi}}(h,a)$ is defined as the product of the corresponding Q-value with the probability of the path of actions from the root of the game tree down to $h$. In symbols,
$\mkern 1.5mu\overline{\mkern-1.5muQ\mkern-1.5mu}\mkern 1.5mu_{1}^{\bm{\pi}}(h,a)\coloneqq\mu_{1}^{\pi_{1}}(\sigma_{1}(h))\cdot\mu_{2}^{\pi_{2}}(\sigma_{2}(h))\cdot\mu_{c}(h)\cdot Q_{1}^{\bm{\pi}}(h,a).$

We now extend these definitions from nodes to *infosets*. Consider infoset $s\in{\mathcal{S}}$ and action $a\in\mathcal{A}_{s}$. For trajectory Q-value and counterfactual value we simply have $\mkern 1.5mu\overline{\mkern-1.5muQ\mkern-1.5mu}\mkern 1.5mu_{1}^{\bm{\pi}}(s,a)\coloneqq\sum_{h\in s}\mkern 1.5mu\overline{\mkern-1.5muQ\mkern-1.5mu}\mkern 1.5mu_{1}^{\bm{\pi}}(h,a)$ and $\mathsf{CF}_{1}^{\bm{\pi}}(s,a)\coloneqq\sum_{h\in s}\mathsf{CF}_{1}^{\bm{\pi}}(h,a)$. For Q-value, $Q_{1}^{\bm{\pi}}(s,a)\coloneqq\mathbb{E}_{h\sim d(\cdot{\,|\,}s)}[Q_{1}^{\bm{\pi}}(h,a)]$, where $d(h{\,|\,}s)\propto\mu_{c}(h)\mu_{1}^{\pi_{1}}(\sigma_{1}(h))\mu_{2}^{\pi_{2}}(\sigma_{2}(h))\propto\mu_{c}(h)\mu_{2}^{\pi_{2}}(\sigma_{2}(h))$ (^2^22Because $\sigma_{1}(h)=\sigma(s)$ for any $s\in{\mathcal{S}}_{1}$ and $h\in s$ due to the perfect-recall assumption.) for any $h\in s$. All definitions are symmetric for Player 2.

#### Regret and Equilibrium.

When players $1$ and $2$ play according to strategies $\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}}$ respectively, the utility of Player $1$ is $(\mu_{1}^{\pi_{1}})^{\top}\bm{A}\mu_{2}^{\pi_{2}}$ and that of Player $2$ is $-(\mu_{1}^{\pi_{1}})^{\top}\bm{A}\mu_{2}^{\pi_{2}}$ since the game is zero-sum. An $\epsilon$-approximate Nash equilibrium (NE) of the game is then defined as follows.

###### Definition 3.1 ( $\epsilon$ -approximate Nash Equilibrium) .

For compact convex set $\mathcal{C}_{1},\mathcal{C}_{2}$, a strategy profile $(\mu_{1},\mu_{2})\in\mathcal{C}_{1}\times\mathcal{C}_{2}$ is an $\epsilon$-approximate NE if

$$ $\displaystyle\max_{\widehat{\mu}_{1}\in\mathcal{C}_{1}}\widehat{\mu}_{1}^{\top}\bm{A}\mu_{2}-\min_{\widehat{\mu}_{2}\in\mathcal{C}_{2}}\mu_{1}^{\top}\bm{A}\widehat{\mu}_{2}\leq\epsilon.$ (3.1) $$

When $\epsilon=0$, we also simply call the strategy profile a Nash equilibrium (NE).

Given a sequence of $T$ strategy pairs $(\mu_{1}^{(t)},\mu_{2}^{(t)})\in\mathcal{C}_{1}\times\mathcal{C}_{2}$, we can define the regret of Player $1$ as (Player $2$’s is analogous),

$$ $\displaystyle R^{(T)}_{1}\coloneqq\max_{\widehat{\mu}_{1}\in\mathcal{C}_{1}}\sum_{t=1}^{T}\left(\widehat{\mu}_{1}-\mu_{1}^{(t)}\right)^{\top}\bm{A}\mu_{2}^{(t)}.$ (3.2) $$

A folklore result establishes a direct connection between regret minimization and approximate Nash equilibrium. Specifically, when the players’ strategies incur regret $R^{(T)}_{1}$ and $R^{(T)}_{2}$ respectively, then the *average* strategies of the players form an $\epsilon$-NE, where

$$ $\epsilon\leq(R^{(T)}_{1}+R^{(T)}_{2})/T.$ (3.3) $$

###### Definition 3.1 ( ϵ italic-ϵ \epsilon -approximate Nash Equilibrium) .

## 4 Q-Function based Regret Minimization ( QFR )

In this section, we propose our policy gradient algorithm for EFGs, which we coin *Q-Function based Regret Minimization (QFR)*.
In QFR, for each player $i\in[2]$ and state $s\in{\mathcal{S}}_{i}$, we enforce the strategy $\pi_{i}^{(t)}(\cdot{\,|\,}s)$ ($\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu_{i}^{(t)}(\cdot{\,|\,}s)$) to explore with probability $\gamma_{s}$ using the exploration strategy $\bm{\nu}_{s}$, in order to ensure that each infoset will be reached with a positive probability $\gamma>0$.

Then, we show that QFR converges in best iterate to the *regularized Nash equilibrium*. Specifically, QFR will converge to the solution $\bm{\mu}^{(\tau,\gamma),*}=(\mu_{1}^{(\tau,\gamma),*},\mu_{2}^{(\tau,\gamma),*})$ of the original bilinear minimax objective plus ad ditional regularization term $\psi_{\rm bi}^{\Pi_{1}}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}})$ and $\psi_{\rm bi}^{\Pi_{2}}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}})$. $\psi_{\rm bi}^{\Pi_{1}}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}})$ is strongly convex with respect to $\mu_{1}^{\pi_{1}}$ and convex with respect to $\mu_{2}^{\pi_{2}}$. Conversely, $\psi_{\rm bi}^{\Pi_{2}}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}})$ is strongly convex with respect to $\mu_{2}^{\pi_{2}}$ and convex with respect to $\mu_{1}^{\pi_{1}}$. In contrast to the original bilinear objective, optimizing the regularized objective will stabilize the training process, and result in better convergence results. Formally, the *regularized and perturbed* (perturb refers to the exploration) game is,

$$ $\displaystyle\max_{\begin{subarray}{c}\mu_{1}^{\pi_{1}}\in\Pi_{1}\colon\\ \forall s\in{\mathcal{S}}_{1},~{}\pi_{1}(\cdot{\,|\,}s)\in\Delta^{|\mathcal{A}_{s}|}_{\gamma_{s},\bm{\nu}_{s}}\end{subarray}}\min_{\begin{subarray}{c}\mu_{2}^{\pi_{2}}\in\Pi_{2}\colon\\ \forall s\in{\mathcal{S}}_{2},~{}\pi_{2}(\cdot{\,|\,}s)\in\Delta^{|\mathcal{A}_{s}|}_{\gamma_{s},\bm{\nu}_{s}}\end{subarray}}\left(\mu_{1}^{\pi_{1}}\right)^{\top}\bm{A}\mu_{2}^{\pi_{2}}-\tau\psi_{\rm bi}^{\Pi_{1}}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}})+\tau\psi_{\rm bi}^{\Pi_{2}}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}})$ (4.1) $$

where $\Delta^{|\mathcal{A}_{s}|}_{\gamma_{s},\bm{\nu}_{s}}\coloneqq\left\{\bm{u}\in\Delta^{|\mathcal{A}_{s}|}\colon\forall a\in\mathcal{A}_{s},~{}~{}u_{a}\geq\gamma_{s}\nu_{s,a}\right\}$, and $\tau\geq 0$ controls the magnitude of the regularizer. Note that the NE of the non-regularized game can be computed by annealing the regularization coefficient $\tau$ by using a standard technique (Liu et al., ).

To decompose the regularizer $\mu_{\rm bi}^{\Pi_{i}}$ to each infoset for efficient update, we resort to the concept *dilated regularizer* (Hoda et al., ). Take Euclidean norm for example, unlike naively choosing $\frac{1}{2}\left\|\mu_{i}^{\pi_{i}}\right\|^{2}$ as the regularizer, dilated regularizer weights the regularizer $\frac{1}{2}\left\|\pi_{i}(\cdot{\,|\,}s)\right\|^{2}$ at each infoset $s\in{\mathcal{S}}_{i}$ by the reach probability of player $i$ to $s$, *i.e.* $\frac{1}{2}\sum_{s\in{\mathcal{S}}_{i}}\mu_{i}^{\pi_{i}}(\sigma(s))\left\|\pi_{i}(\cdot{\,|\,}s)\right\|^{2}$. It is shown in Hoda et al. () that the dilated regularizer is strongly convex with respect to $\mu_{i}^{\pi_{i}}$. However, dilated regularizer $\psi^{\Pi_{i}}$ only weights the reach probability of player $i$, neglecting that of the opponents, of which the asymmetry causes importance sampling when estimating the regularizer term in a rolling trajectory. Therefore, a natural solution is weighting the strongly convex regularizer $\psi_{s}^{\Delta}\colon\Delta^{|\mathcal{A}_{s}|}\to\mathbb{R}$ at each infoset $s\in{\mathcal{S}}$ (typically it is Euclidean norm or negative entropy) by the reach probability of all players. Formally, the *bidilated* regularizer $\psi^{\Pi_{1}}_{\rm bi}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}})$ of player 1 is defined as (that of player 2 can be defined similarly),

$$ $\displaystyle\psi^{\Pi_{1}}_{\rm bi}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}})\coloneqq\sum_{s\in{\mathcal{S}}_{1}}\mu_{1}^{\pi_{1}}(\sigma(s))\left(\sum_{h\in s}\mu_{c}(h)\mu_{2}^{\pi_{2}}(\sigma_{2}(h))\right)\psi_{s}^{\Delta}(\pi_{1}(\cdot{\,|\,}s)),$ ( Bidilated Regularizer ) $\displaystyle\psi^{\Pi_{1}}(\mu_{1}^{\pi_{1}})=\sum_{s\in{\mathcal{S}}_{1}}\mu_{1}^{\pi_{1}}(\sigma(s))\psi_{s}^{\Delta}(\pi_{1}(\cdot{\,|\,}s))$ ( Dilated Regularizer ) $$

The details can be referred to [Appendix C](#A3). For notational simplicity, let $\psi^{\Pi}(\bm{\mu}^{\bm{\pi}})\colon\Pi\to\mathbb{R}=\psi^{\Pi_{1}}(\mu_{1}^{\pi_{1}})+\psi^{\Pi_{2}}(\mu_{2}^{\pi_{2}})$. With all ingredients at hand, we can introduce the algorithm Q-Function based Regret minimization (QFR). At each timestep $t$, QFR will sample a trajectory according to the current strategy $\bm{\pi}^{(t-1)}$ (Line 3 of [Algorithm 1](#alg1)). Then, the *trajectory Q-value* will be estimated from the trajectory (Line 8-10). Lastly, all infosets along the trajectory will be updated with a variant of Regularized Optimistic Mirror Descent (Reg-OMD) proposed in Liu et al. () (Line 11). In Reg-OMD, at timestep $t$, the strategy $\bm{\pi}^{(t)}$ serves as the prediction of $\mkern 1.5mu\overline{\mkern-1.5mu\bm{\pi}\mkern-1.5mu}\mkern 1.5mu^{(t+1)}$. Then in the next timestep $t+1$, $\mkern 1.5mu\overline{\mkern-1.5mu\bm{\pi}\mkern-1.5mu}\mkern 1.5mu^{(t)}$ will be updated with the trajectory Q-value estimated at $\bm{\pi}^{(t)}$.
The pseudocode of QFR is proposed in [Algorithm 1](#alg1).

Figure: Algorithm 1 Q-Function based Regret minimization (QFR)

We define the largest learning rate among all ancestor infosets
of $s\in{\mathcal{S}}$ as $\eta_{s}^{\rm anc}\coloneqq\max_{i\in[2],h\in s}\max_{(s^{\prime},a^{\prime})\sqsubseteq\sigma_{i}(h)}\eta_{s^{\prime}}$ ($\eta_{s}$ is the learning of infoset $s$), and we have the following theorem that establishes the best-iterate convergence of [Algorithm 1](#alg1) to the NE $\bm{\mu}^{(\tau,\gamma),*}=(\mu_{1}^{(\tau,\gamma),*},\mu_{2}^{(\tau,\gamma),*})$ of [Equation 4.1](#S4.E1) with high-probability.

###### Theorem 4.1 (Informal) .

Consider [Algorithm 1](#alg1). When $\frac{\eta_{s}^{\rm anc}}{\eta_{s}}\leq\tau C_{s}^{\eta,T}$, where $C_{s}^{\eta}$ is a game-dependent constant, and $\eta_{s}$ is smaller than a game dependent constant (formally defined in [Appendix E](#A5)) for any $s\in{\mathcal{S}}$, we have the following guarantee with probability $1-2\delta$.

$$ $\displaystyle\sum_{t=2}^{T}D_{\psi^{\Pi}}(\bm{\mu}^{(\tau,\gamma),*},\bm{\mu}^{\mkern 1.5mu\overline{\mkern-1.5mu\bm{\pi}\mkern-1.5mu}\mkern 1.5mu^{(t)}})\leq\widetilde{O}\left(\max_{s\in{\mathcal{S}}}\eta_{s}T\right)+\widetilde{O}\left(\frac{1}{\min_{s\in{\mathcal{S}}}\eta_{s}}\right)+\widetilde{O}\left(\sqrt{T\log\frac{1}{\delta}}\right).$ (4.3) $$

The $\widetilde{O}$ notion hides the logarithm of $T$. The proof and the formal version are postponed to Appendix [E](#A5). [Theorem 4.1](#S4.Thmtheorem1) gives a high-probability upper-bound on the cumulative Bregman divergence. By letting $\eta_{s}=\Theta(1/\sqrt{T})$ for all infoset $s\in{\mathcal{S}}$, the right-hand-side of ([4.3](#S4.E3)) is bounded by $\widetilde{O}(\sqrt{T})$.
Therefore, it implies that $\sum_{t=2}^{T}D_{\psi^{\Pi}}(\bm{\mu}^{(\tau,\gamma),*},\bm{\mu}^{\mkern 1.5mu\overline{\mkern-1.5mu\bm{\pi}\mkern-1.5mu}\mkern 1.5mu^{(t)}})$ is upper-bounded by $\widetilde{O}(\sqrt{T})$ with probability $1-2\delta$. Then, there must exist some $t^{*}\in[T]$ so that $D_{\psi^{\Pi}}(\bm{\mu}^{(\tau,\gamma),*},\bm{\mu}^{\mkern 1.5mu\overline{\mkern-1.5mu\bm{\pi}\mkern-1.5mu}\mkern 1.5mu^{(t^{*})}})\leq\widetilde{O}(1/\sqrt{T})$, because the minimum over $\left\{D_{\psi^{\Pi}}(\bm{\mu}^{(\tau,\gamma),*},\bm{\mu}^{\mkern 1.5mu\overline{\mkern-1.5mu\bm{\pi}\mkern-1.5mu}\mkern 1.5mu^{(t)}})\colon t=2,3,...,T\right\}$ must be bounded by the average, which is $\widetilde{O}(1/\sqrt{T})$.

###### Theorem 4.1 (Informal) .

## 5 Analysis

In this section, we provide the proof sketch of [Theorem 4.1](#S4.Thmtheorem1). [Section 5.1](#S5.SS1) introduces some necessary notions and properties for the analysis. [Section 5.2](#S5.SS2) shows the convergence of QFR under full-information feedback (traversing all infosets at each iteration), and [Section 5.3](#S5.SS3) generalizes to the stochastic setting in [Section 4](#S4).

### 5.1 Preliminaries and Basic Properties

In order to keep the presentation modular between Q-values and trajectory Q-values, we will assume that, at each iteration $t$, the local strategy at each infoset will be updated by taking a step in the direction of some generalized *value vector* $q^{(t)}(s,\cdot)\in\mathbb{R}^{|\mathcal{A}_{s}|}$. For each $a\in\mathcal{A}_{s}$, (we will use $\mathsf{CF}^{(t)}_{1}(s,a)$ instead of $\mathsf{CF}_{1}^{\bm{\pi}^{(t)}}(s,a)$ and $\mu_{i}^{(t)}$ instead of $\mu_{i}^{\pi_{i}^{(t)}}$ as the shorthand notion), the relationship of counterfactual values and the feedback is,

$$ $\displaystyle\mathsf{CF}^{(t)}_{1}(s,a)=\begin{cases}\sum_{h\in s}\mu_{c}(h)\mu_{2}^{(t)}(\sigma_{2}(h))\cdot q^{(t)}(s,a)&q^{(t)}(s,\cdot)\text{ is Q-value}\[5.69054pt] \frac{q^{(t)}(s,a)}{\mu_{1}^{(t)}(\sigma(s))}&q^{(t)}(s,\cdot)\text{ is trajectory Q-value}\[8.53581pt] q^{(t)}(s,a)&q^{(t)}(s,\cdot)\text{ is counterfactual value}\end{cases}$ (5.1) $$

It is noteworthy that when sampling a trajectory from the root to a terminal node, the utility will be a good estimator of trajectory Q-value. Therefore, to estimate $\mathsf{CF}^{(t)}_{1}(s,a)$, we need to divide the reaching probability $\mu_{1}^{(t)}(\sigma(s))$ of $s$, which can be extremely small and thus induces a large variance. In the following, we will write $\mathsf{CF}^{(t)}_{1}(s,a)=m^{(t)}_{s}q^{(t)}(s,a)$ and $m^{(t)}_{s}$ is different for different types of $q^{(t)}(s,\cdot)$ according to [Equation 5.1](#S5.E1).

Note that the value of $m^{(t)}_{s}$ in most cases depends on the strategies that are produced by the algorithm; hence, there is some circularity in the dependence between the properties satisfied by $m^{(t)}_{s}$ and those satisfied by our algorithm. To break this circularity, at the heart of our correctness proof we will verify and leverage two key properties of the sequence of $m^{(t)}_{s}$ that arises from using our algorithm: *boundedness* and *stability*, as detailed next.

###### Property 1 (Boundedness) .

For any $t\in[T]$ and $s\in{\mathcal{S}}$, we have $m^{(t)}_{s}\in[M_{1},M_{2}]$ where $0<M_{1}\leq M_{2}<+\infty$.

###### Property 2 (Stability) .

For any $t\in[T-1]$ and $s\in{\mathcal{S}}$, we define the largest learning rate among all ancestor infosets of $s$ as $\eta_{s}^{\rm anc}\coloneqq\max_{i\in[2],h\in s}\max_{(s^{\prime},a^{\prime})\sqsubseteq\sigma_{i}(h)}\eta_{s^{\prime}}$, where $\eta_{s^{\prime}}$ is the learning rate of infoset $s^{\prime}$, then

$$ $\displaystyle\left|m^{(t+1)}_{s}-m^{(t)}_{s}\right|\leq C_{s}^{-}\eta_{s}^{\rm anc}$ (Additive Stability) $\displaystyle\left|\frac{m^{(t+1)}_{s}}{m^{(t)}_{s}}-1\right|\leq C_{s}^{/}\eta_{s}^{\rm anc}.$ (Multiplicative Stability) $$

Property [1](#Thmproperty1) will be satisfied by enforcing $\pi^{(t)}(\cdot{\,|\,}s)\succeq\gamma_{s}\bm{\nu}_{s}$ for every $s\in{\mathcal{S}}$, where $\gamma_{s}\in(0,1]$ and $\bm{\nu}_{s}\in\Delta^{|\mathcal{A}_{s}|}$ are specified in [Section F.2](#A6.SS2).
The proof that our algorithm produces iterates that satisfy Property [2](#Thmproperty2) can be found in [Appendix B](#A2).

###### Property 1 (Boundedness) .

###### Property 2 (Stability) .

### 5.2 Convergence with Full Information Feedback

QFR runs a variant of Regularized Optimistic Mirror Descent (Reg-OMD) (Liu et al., ) algorithm to update the strategy in each infoset. For notational simplicity, we define the reach probability of opponents to an infoset $s\in{\mathcal{S}}$ as $\mu_{-p(s)}^{(t)}(s)\coloneqq\sum_{h\in s}\mu_{c}(h)\mu_{3-p(s)}^{(t)}(\sigma_{3-p(s)}(h))$. The update rule is

$$ $\begin{split}\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)\!=\!\mathop{\mathrm{argmin}}_{\pi_{p(s)}(\cdot{\,|\,}s)\in\Delta^{|\mathcal{A}_{s}|}_{\gamma_{s},\bm{\nu}_{s}}}&\left\langle\pi_{p(s)}(\cdot{\,|\,}s),-q^{(t-1)}(s,\cdot)\right\rangle+\frac{\tau\mu_{-p(s)}^{(t-1)}(s)}{m^{(t-1)}_{s}}\psi_{s}^{\Delta}(\pi_{p(s)}(\cdot{\,|\,}s))\\ &+\frac{1}{\eta_{s}}D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s))\\ \mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s)\!=\!\mathop{\mathrm{argmin}}_{\pi_{p(s)}(\cdot{\,|\,}s)\in\Delta^{|\mathcal{A}_{s}|}_{\gamma_{s},\bm{\nu}_{s}}}&\left\langle\pi_{p(s)}(\cdot{\,|\,}s),-q^{(t)}(s,\cdot)\right\rangle+\frac{\tau\mu_{-p(s)}^{(t)}(s)}{m^{(t)}_{s}}\psi_{s}^{\Delta}(\pi_{p(s)}(\cdot{\,|\,}s))\\ &+\frac{1}{\eta_{s}}D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s))\\ \end{split}$ (5.2) $$

where $\Delta^{|\mathcal{A}_{s}|}_{\gamma_{s},\bm{\nu}_{s}}\coloneqq\left\{\bm{u}\in\Delta^{|\mathcal{A}_{s}|}\colon\forall a\in\mathcal{A}_{s},~{}~{}u_{a}\geq\gamma_{s}\nu_{s,a}\right\}$ and $\psi_{s}^{\Delta}$ is the regularizer chosen for infoset $s$. Here $q^{(t)}(s,\cdot)$ can be trajectory Q-value, Q-value, and counterfactual value associated with $\bm{\pi}^{(t)}$. When $q^{(t)}(s,\cdot)$ is the trajectory Q-value, ([5.2](#S5.E2)) is the full-information version of ([4.2](#S4.E2)).

By analyzing the update rule ([5.2](#S5.E2)), we can get the following inequality. For any $s\in{\mathcal{S}}$ and strategy $\pi_{p(s)}(\cdot{\,|\,}s)\in\Delta^{|\mathcal{A}_{s}|}_{\gamma_{s},\bm{\nu}_{s}}$, we have

$$ $\displaystyle\sum_{t=1}^{T}\left(\tau\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\tau\psi_{s}^{\Delta}(\pi_{p(s)}(\cdot{\,|\,}s))+m^{(t)}_{s}\langle-q^{(t)}(s,\cdot),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\pi_{p(s)}(\cdot{\,|\,}s)\rangle\right)$ $\displaystyle\leq$ $\displaystyle\sum_{t=2}^{T}\underbrace{\left(\frac{m^{(t)}_{s}-m^{(t-1)}_{s}}{\eta_{s}}-\tau\mu^{(t-1)}_{-p(s)}(s)\right)}_{\leavevmode\hbox to7.23pt{\vbox to7.23pt{\pgfpicture\makeatletter\hbox{\hskip 3.61601pt\lower-3.61601pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.41602pt}{0.0pt}\pgfsys@curveto{3.41602pt}{1.88663pt}{1.88663pt}{3.41602pt}{0.0pt}{3.41602pt}\pgfsys@curveto{-1.88663pt}{3.41602pt}{-3.41602pt}{1.88663pt}{-3.41602pt}{0.0pt}\pgfsys@curveto{-3.41602pt}{-1.88663pt}{-1.88663pt}{-3.41602pt}{0.0pt}{-3.41602pt}\pgfsys@curveto{1.88663pt}{-3.41602pt}{3.41602pt}{-1.88663pt}{3.41602pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s))+O(\eta_{s}T)+O(\frac{1}{\eta_{s}}).$ (5.3) $$

Then, since $\left|m^{(t)}_{s}-m^{(t-1)}_{s}\right|\leq O(\eta_{s}^{\rm anc})$, $\leavevmode\hbox to9.67pt{\vbox to9.67pt{\pgfpicture\makeatletter\hbox{\hskip 4.83623pt\lower-4.83623pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.63623pt}{0.0pt}\pgfsys@curveto{4.63623pt}{2.56055pt}{2.56055pt}{4.63623pt}{0.0pt}{4.63623pt}\pgfsys@curveto{-2.56055pt}{4.63623pt}{-4.63623pt}{2.56055pt}{-4.63623pt}{0.0pt}\pgfsys@curveto{-4.63623pt}{-2.56055pt}{-2.56055pt}{-4.63623pt}{0.0pt}{-4.63623pt}\pgfsys@curveto{2.56055pt}{-4.63623pt}{4.63623pt}{-2.56055pt}{4.63623pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\leq-\frac{\tau}{2}\mu^{(t-1)}_{-p(s)}(s)\leq-\frac{\tau\gamma}{2}\sum_{h\in s}\mu_{c}(h)$ when $\eta_{s}^{\rm anc}$ is smaller then $\eta_{s}$ by a small enough constant (please refer to Appendix [D](#A4) for details). Then, by applying the generalized regret decomposition lemma (Liu et al., ) (details can be found in [Lemma D.3](#A4.Thmtheorem3)) to [Equation 5.3](#S5.E3), the difference of $\pi_{p(s)}^{(t)}$ and $\pi_{p(s)}$ in an infoset $s$ can be extended to the difference of the whole game. Specifically, by letting

$$ $\text{diff}_{1}(\bm{\mu}^{\bm{\pi}},\bm{\mu}^{\bm{\pi}^{\prime}})\coloneqq\left(\mu_{1}^{\pi_{1}}-\mu_{1}^{\pi_{1}^{\prime}}\right)^{\top}\bm{A}\mu_{2}^{\pi_{2}}-\tau\left(\psi_{\rm bi}^{\Pi_{1}}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}})-\psi_{\rm bi}^{\Pi_{1}}(\mu_{1}^{\pi_{1}^{\prime}},\mu_{2}^{\pi_{2}})\right)+\tau\left(\psi_{\rm bi}^{\Pi_{2}}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}})-\psi_{\rm bi}^{\Pi_{2}}(\mu_{1}^{\pi_{1}^{\prime}},\mu_{2}^{\pi_{2}})\right)$ $$

and $\text{diff}_{2}$ similarly, then

$$ $\displaystyle\small\sum_{t=1}^{T}\sum_{s\in{\mathcal{S}}}\mu^{(\tau,\gamma),*}(\sigma(s))\left(\tau\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\tau\psi_{s}^{\Delta}(\pi_{p(s)}^{(\tau,\gamma),*}(\cdot{\,|\,}s))+m^{(t)}_{s}\langle-q^{(t)}(s,\cdot),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\pi^{(\tau,\gamma),*}_{p(s)}(\cdot{\,|\,}s)\rangle\right)$ $$

is equal to

$$ $\displaystyle\sum_{t=1}^{T}\text{diff}_{1}(\bm{\mu}^{(\tau,\gamma),*},\bm{\mu}^{(t)})+\text{diff}_{2}(\bm{\mu}^{(\tau,\gamma),*},\bm{\mu}^{(t)})\geq 0.$ (5.4) $$

The non-negativity is because $\bm{\mu}^{(\tau,\gamma),*}$ is the NE of [Equation 4.1](#S4.E1). By combining ([5.3](#S5.E3)) and ([5.4](#S5.E4)), we have

$$ $\displaystyle 0\leq$ $\displaystyle\sum_{s\in{\mathcal{S}}}\mu^{(\tau,\gamma),*}(\sigma(s))\left(-\frac{\tau\gamma}{2}\sum_{h\in s}\mu_{c}(h)\sum_{t=2}^{T}D_{\psi_{s}^{\Delta}}(\pi_{p(s)}^{(\tau,\gamma),*}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s))+O(\eta_{s}T)+O\left(\frac{1}{\eta_{s}}\right)\right)$ $\displaystyle\overset{(a)}{=}$ $\displaystyle-\frac{\tau\gamma}{2}\min_{s\in{\mathcal{S}}}\sum_{h\in s}\mu_{c}(h)\sum_{t=2}^{T}D_{\psi^{\Pi}}(\bm{\mu}^{(\tau,\gamma),*},\bm{\mu}^{\mkern 1.5mu\overline{\mkern-1.5mu\bm{\pi}\mkern-1.5mu}\mkern 1.5mu^{(t)}})+O(\max_{s\in{\mathcal{S}}}\eta_{s}T)+O\left(\frac{1}{\min_{s\in{\mathcal{S}}}\eta_{s}}\right).$ $$

$(a)$ is by Lemma [5.1](#S5.Thmtheorem1) in the following. By rearranging the terms, we can get an upperbound on $\sum_{t=2}^{T}D_{\psi^{\Pi}}(\bm{\mu}^{(\tau,\gamma),*},\bm{\mu}^{\mkern 1.5mu\overline{\mkern-1.5mu\bm{\pi}\mkern-1.5mu}\mkern 1.5mu^{(t)}})$.

###### Lemma 5.1 (Lemma D.2. in Liu et al. ( 2022 ) ) .

For any strategy $\bm{\mu}^{\bm{\pi}},\bm{\mu}^{\widetilde{\bm{\pi}}}\in\Pi$ and regularizer $\psi^{\Delta}_{s}\colon\Delta^{|\mathcal{A}_{s}|}\to\mathbb{R}$ for each infoset $s\in{\mathcal{S}}$, we have

$$ $\displaystyle D_{\psi^{\Pi}}(\bm{\mu}^{\bm{\pi}},\bm{\mu}^{\widetilde{\bm{\pi}}})=\sum_{s\in{\mathcal{S}}}\mu^{\bm{\pi}}(\sigma(s))D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\widetilde{\pi}_{p(s)}(\cdot{\,|\,}s)).$ (5.5) $$

For completeness, the proof of the lemma can be found in [Section D.1](#A4.SS1). Here is the full theorem.

###### Theorem 5.2 (Informal) .

Consider the update rule ([5.2](#S5.E2)) and $q^{(t)}(s,\cdot)$ is chosen to be counterfactual value, trajectory Q-value, or Q-value. When $\frac{\eta_{s}^{\rm anc}}{\eta_{s}}\leq\tau C_{s}^{\eta}$, where $C_{s}^{\eta}$ is a game-dependent constant, and $\eta_{s}$ is smaller than a game dependent constant (formally defined in [Appendix D](#A4)) for any $s\in{\mathcal{S}}$, we have the following guarantee.

$$ $\displaystyle\sum_{t=2}^{T}D_{\psi^{\Pi}}(\bm{\mu}^{(\tau,\gamma),*},\bm{\mu}^{\mkern 1.5mu\overline{\mkern-1.5mu\bm{\pi}\mkern-1.5mu}\mkern 1.5mu^{(t)}})\leq O\left(\max_{s\in{\mathcal{S}}}\eta_{s}T\right)+O\left(\frac{1}{\min_{s\in{\mathcal{S}}}\eta_{s}}\right).$ (5.6) $$

The proof and the formal version are postponed to Appendix [D](#A4). Therefore, by choosing $\eta_{s}=\Theta\left(\frac{1}{\sqrt{T}}\right)$ for any $s\in{\mathcal{S}}$ as in [Theorem 5.2](#S5.Thmtheorem2), QFR enjoys best-iterate convergence with under full-information feedback.

###### Lemma 5.1 (Lemma D.2. in Liu et al. ( 2022 ) ) .

###### Theorem 5.2 (Informal) .

### 5.3 Convergence with Stochastic Feedback

We complement the results of Section [5.2](#S5.SS2) by showing that the best-iterate convergence guaranteed by QFR is still guaranteed when only visiting a trajectory at each iteration. The proof utilizes standard concentration inequalities, incurring an additional sublinear cost caused by the noise incurred from sampling, as recalled in the following lemma.

###### Lemma 5.3 (Generalization of Proposition 1 in Farina et al. ( 2020 ) ) .

Let $M,\widetilde{M}$ be positive constants such that $\left|f^{(t)}(\bm{u})-f^{(t)}(\bm{u}^{\prime})\right|\leq M$ and $\left|\widetilde{f}^{(t)}(\bm{u})-\widetilde{f}^{(t)}(\bm{u}^{\prime})\right|\leq\widetilde{M}$ for any $\bm{u},\bm{u}^{\prime}\in\mathcal{C}$ for any $t\in[T]$, where $\mathcal{C}$ is a convex set. Then, if for any $\bm{u}$, $\mathbb{E}[\widetilde{f}^{(t)}(\bm{u}){\,|\,}\widetilde{f}^{(1)},\widetilde{f}^{(2)},...,\widetilde{f}^{(t-1)}]=f^{(t)}(\bm{u})$ and $\bm{u}^{(t)}$ is deterministically influenced by $\widetilde{f}^{(1)},\widetilde{f}^{(2)},...,\widetilde{f}^{(t-1)}$, then for any $\delta\in(0,1)$ and $\bm{u}\in\mathcal{C}$, we have

$$ $\displaystyle\Pr\Bigg{(}\sum_{t=1}^{T}\left(f^{(t)}(\bm{u})-f^{(t)}(\bm{u}^{(t)})\right)\leq\sum_{t=1}^{T}\left(\widetilde{f}^{(t)}(\bm{u})-\widetilde{f}^{(t)}(\bm{u}^{(t)})\right)+(M+\widetilde{M})\sqrt{2T\log\frac{1}{\delta}}\Bigg{)}\geq 1-\delta.$ $$

Next, we will substitute the following values into [Lemma 5.3](#S5.Thmtheorem3),

$$ $\displaystyle f^{(t)}_{s}(\bm{u})\coloneqq\frac{1}{\mu_{p(s)}^{(t)}(\sigma(s))}\langle q^{(t)}(s,\cdot),\bm{u}\rangle-\tau\mu_{-p(s)}^{(t)}(s)\psi_{s}^{\Delta}(\bm{u})$ $\displaystyle\widetilde{f}^{(t)}_{s}(\bm{u})\coloneqq\begin{cases}\frac{1}{\mu_{p(s)}^{(t)}(\sigma(s))}\langle\widetilde{q}^{(t)}(s,\cdot),\bm{u}\rangle-\frac{\tau}{\mu_{p(s)}^{(t)}(\sigma(s))}\psi_{s}^{\Delta}(\bm{u})&s{\text{ is visited at timestep }t}\\ 0&\text{Otherwise}\end{cases}$ $$

, where $\widetilde{q}^{(t)}$ is defined in [Algorithm 1](#alg1). The proof of $\widetilde{f}^{(t)}_{s}$ being an unbiased estimator of $f^{(t)}_{s}$ is postponed to [Appendix E](#A5). Then, [Equation 5.3](#S5.E3) can be bounded by $\sum_{t=1}^{T}\left(\widetilde{f}^{(t)}_{s}(\pi_{p(s)}(\cdot{\,|\,}s))-\widetilde{f}^{(t)}_{s}(\pi_{p(s)}^{(t)}(\cdot{\,|\,}s))\right)$, which can be further bounded by analyzing the update-rule [Equation 4.2](#S4.E2). The analysis is similar to the one in [Section 5.2](#S5.SS2) and can be found in [Appendix E](#A5). Finally, we have [Theorem 4.1](#S4.Thmtheorem1).

###### Lemma 5.3 (Generalization of Proposition 1 in Farina et al. ( 2020 ) ) .

## 6 Experiments

In the experiments, we apply QFR in 4-Sided Liar’s Dice, Leduc Poker (Southey et al., ), Kuhn Poker (Kuhn, ), and $2\times 2$ Abrupt Dark Hex. The learning rate is the *same* in all infosets, unlike what the theorem requires, which shows that QFR is easier to implement than what the theory suggests. Note that for MMD (Sokota et al., ), there is no theory for convergence when using trajectory Q-value and Q-value as feedback, while QFR has.

In order to pick hyperparameters, we performed a grid-search for QFR and MMD on learning rate $\eta$, regularization $\tau$, perturbation $\gamma$, and the regularizer is either negative entropy or Euclidean distance. For the outcome-sampling CFR / CFR+, we also applies grid-search on the exploration parameter. The details can be found in Appendix [G](#A7).

Figure: Figure 1: Exploitability of [Algorithm 1](#alg1) in 4 benchmark games. We can see that QFR outperforms CFR and CFR+ in all games except Liar’s Dice, and outperforms MMD in all games except dark hex. For each line, we repeat the experiments 100 times with different seeds.​​
Refer to caption: /html/2408.00751/assets/x1.png

The experimental result of [Algorithm 1](#alg1) is presented in [Figure 1](#S6.F1).
In the experiments, QFR and MMD are both using an unbiased estimator of the trajectory Q-value, while CFR and CFR+ use an unbiased estimator of the counterfactual value.

In Figure [1](#S6.F1), we can see that QFR outperforms outcome-sampling CFR and CFR+ in all games except Liar’s Dice. The reason may be the equilibrium of Liar’s Dice is too simple. As shown in [Figure 2](#A7.F2) in the Appendix, the equilibrium of Liar’s Dice can be computed in 50 iterations.

## Appendix A Formal Definition of Trajectory Q-Value, Q-Value, and Counterfactual Value

In the following, we will formally define trajectory Q-value, Q-value, and counterfactual value respectively.

For any $s\in{\mathcal{S}},a\in\mathcal{A}_{s}$, the *trajectory Q-value* $\mkern 1.5mu\overline{\mkern-1.5muQ\mkern-1.5mu}\mkern 1.5mu_{1}^{\bm{\pi}}(s,a)$ is formally defined as,

$$ $\displaystyle\mkern 1.5mu\overline{\mkern-1.5muQ\mkern-1.5mu}\mkern 1.5mu_{1}^{\bm{\pi}}(s,a)\coloneqq\frac{1}{\pi_{1}(a{\,|\,}s)}\sum_{h^{\prime}\colon\exists h\in s,(h,a)\sqsubseteq h^{\prime}}\mu_{c}(h^{\prime})\mu_{1}^{\pi_{1}}(\sigma_{1}(h^{\prime}))\mu_{2}^{\pi_{2}}(\sigma_{2}(h^{\prime}))\mathcal{U}_{1}(h^{\prime})$ (A.1) $$

In Eq ([A.1](#A1.E1)), $\mu_{c}(h)$ denotes the probability of reaching $h$ contributed by the chance player. We use $\left\{\mathcal{U}_{i}\colon\mathcal{H}\to[-1,1]\right\}_{i\in[2]}$ to denote the utility assigned to each player at each node of the game. We assume this is nonzero only at terminal nodes (nodes with an empty action set) without loss of generality.

At the same time, we can define the *Q-value*, defined as the expected utility *conditioned on* reaching infoset $s$,

$$ $\displaystyle Q_{1}^{\bm{\pi}}(s,a)\coloneqq\frac{\mkern 1.5mu\overline{\mkern-1.5muQ\mkern-1.5mu}\mkern 1.5mu_{1}^{\bm{\pi}}(s,a)}{\sum_{h\in s}\mu_{c}(h)\mu_{1}^{\pi_{1}}(\sigma_{1}(h))\mu_{2}^{\pi_{2}}(\sigma_{2}(h))}.$ (A.2) $$

Typically, algorithms like CFR and its variants (Tammelin et al., ; Brown and Sandholm, ) use counterfactual values as feedback to learn the equilibrium. The counterfactual value at infoset $s$ of player $i$ is the Q-value at $s$ times the reach probability of the opponent and the chance player to $s$. Formally, for any $s\in{\mathcal{S}},a\in\mathcal{A}_{s}$, we can define the *counterfactual value* $\mathsf{CF}_{1}^{\bm{\pi}}(s)$ as,

$$ $\displaystyle\mathsf{CF}_{1}^{\bm{\pi}}(s,a)\coloneqq\sum_{h^{\prime}\colon\exists h\in s,(h,a)\sqsubseteq h^{\prime}}\mu_{c}(h^{\prime})\frac{\mu_{1}^{\pi_{1}}(\sigma_{1}(h^{\prime}))}{\mu_{1}^{\pi_{1}}(s,a)}\mu_{3-1}^{\pi_{3-1}}(\sigma_{3-1}(h^{\prime}))\mathcal{U}_{1}(h^{\prime}).$ (A.3) $$

$\mathsf{CF}_{i}^{\bm{\pi}}$ is not compatible with rolling out trajectories as reinforcement learning usually does, since a rolling trajectory includes the probability of both players reaching infoset $s$, which hinders extending algorithms to large games.

Also, for any $s\in{\mathcal{S}}_{1}$ and $a\in\mathcal{A}_{s}$ (similar for player $2$), we have

$$ $\displaystyle\mathsf{CF}_{1}^{\bm{\pi}}(s,a)=$ $\displaystyle\frac{1}{\mu_{1}^{\pi_{1}}(\sigma(s))}\mkern 1.5mu\overline{\mkern-1.5muQ\mkern-1.5mu}\mkern 1.5mu_{1}^{\bm{\pi}}(s,a)$ (A.4) $\displaystyle\mathsf{CF}_{1}^{\bm{\pi}}(s,a)=$ $\displaystyle\frac{\sum_{h\in s}\mu_{c}(h)\mu_{1}^{\pi_{1}}(\sigma_{1}(h))\mu_{2}^{\pi_{2}}(\sigma_{2}(h))}{\mu_{1}^{\pi_{1}}(\sigma(s))}\cdot Q_{1}^{\bm{\pi}}(s,a)\overset{(i)}{=}$ $\displaystyle\sum_{h\in s}\mu_{c}(h)\mu_{2}^{\pi_{2}}(\sigma_{2}(h))Q_{1}^{\bm{\pi}}(s,a),$ (A.5) $$

where equality $(i)$ follows from $\sigma_{1}(h)=\sigma(s)$ for any $s\in{\mathcal{S}}_{1}$ and $h\in s$, which is a consequence to the perfect-recall assumption.

## Appendix B Stability of Trajectory Q-value and Q-Value

In this section, we will show the stability of trajectory Q-value and Q-value, *i.e.* proving Property [2](#Thmproperty2). Due to the symmetry between two players, we will only prove that for $s\in{\mathcal{S}}_{1}$. Moreover, to stabilize trajectory Q-value and Q-value, the learning rate need to satisfy the following conditions.

- (A)
$\max_{h\in s}\sum_{(s^{\prime},a^{\prime})\sqsubseteq\sigma_{i}(h)}\eta_{s^{\prime}}\leq\eta_{s}$ for any $s\in{\mathcal{S}},i\in[2]$
- (B)
$\allowbreak 6\eta_{s}^{\rm anc}\max_{s^{\prime}\in{\mathcal{S}}}\allowbreak\left(\frac{2\left\|\bm{q}\right\|_{\infty}}{\alpha_{s^{\prime}}}+\frac{\tau}{M_{1}}\log\frac{1}{\gamma}\right)\leq 1$ for any $s\in{\mathcal{S}}$, where $\left\|\bm{q}\right\|_{\infty}\coloneqq\max_{t\in[T],s\in{\mathcal{S}}}\left\|q^{(t)}(s,\cdot)\right\|_{\infty}$ and its upperbound is given in [Lemma F.1](#A6.Thmtheorem1)
- (C)
$\eta_{s}\left(2\left\|\bm{q}\right\|_{\infty}+\frac{\tau\alpha_{s}}{M_{1}}\log\frac{1}{\gamma}\right)\leq 1$ for any $s\in{\mathcal{S}}$

[A](#A2.I1.i1) ensures that $\sum_{(s^{\prime},a^{\prime})\sqsubseteq\sigma(s)}\eta_{s^{\prime}}\leq 2\eta_{s}^{\rm anc}$ for any $s\in{\mathcal{S}}$. [B](#A2.I1.i2), [C](#A2.I1.i3) ensure that the update at each iteration will not change the strategy too much.

### B.1 Stability of Trajectory Q-value

###### Lemma B.1 (Stability of $m^{(t)}_{s}$ under Euclidean regularizer) .

Consider when $\psi^{\Delta}_{s}(\bm{u})=\frac{\alpha_{s}}{2}\sum_{a\in\mathcal{A}_{s}}u_{a}^{2}$ for any $s\in{\mathcal{S}}$ and [A](#A2.I1.i1) is satisfied. For any $s\in{\mathcal{S}}$ and $t=1,2,...,T$, when $m^{(t)}_{s}$ is the trajectory Q-value feedback, we have

$$ $\displaystyle C_{s}^{-}=\frac{6}{\gamma^{2}}\max_{s^{\prime}\in{\mathcal{S}}}C_{s^{\prime}}^{\rm diff}$ $\displaystyle C_{s}^{/}=\frac{6}{\gamma^{2}M_{1}}\max_{s^{\prime}\in{\mathcal{S}}}C_{s^{\prime}}^{\rm diff}.$ (B.1) $$

###### Proof.

For trajectory Q-value feedback, for any $s\in{\mathcal{S}}_{1}$,

$$ $\displaystyle\left|m^{(t+1)}_{s}-m^{(t)}_{s}\right|=$ $\displaystyle\left|\frac{1}{\mu_{1}^{(t+1)}(\sigma(s))}-\frac{1}{\mu_{1}^{(t)}(\sigma(s))}\right|$ $\displaystyle=$ $\displaystyle\frac{\left|\mu_{1}^{(t+1)}(\sigma(s))-\mu_{1}^{(t)}(\sigma(s))\right|}{\mu_{1}^{(t+1)}(\sigma(s))\mu_{1}^{(t)}(\sigma(s))}$ $\displaystyle=$ $\displaystyle\frac{\left|\prod_{(s^{\prime},a^{\prime})\sqsubseteq\sigma(s)}\pi_{1}^{(t+1)}(a^{\prime}{\,|\,}s^{\prime})-\prod_{(s^{\prime},a^{\prime})\sqsubseteq\sigma(s)}\pi_{1}^{(t)}(a^{\prime}{\,|\,}s^{\prime})\right|}{\mu_{1}^{(t+1)}(\sigma(s))\mu_{1}^{(t)}(\sigma(s))}$ $\displaystyle\leq$ $\displaystyle\frac{1}{\gamma^{2}}\sum_{(s^{\prime},a^{\prime})\sqsubseteq\sigma(s)}\left|\pi_{1}^{(t+1)}(a^{\prime}{\,|\,}s^{\prime})-\pi_{1}^{(t)}(a^{\prime}{\,|\,}s^{\prime})\right|.$ $$

In the last line, we use the fact $\mu_{1}^{(t+1)}(\sigma(s)),\mu_{1}^{(t)}(\sigma(s))\geq\gamma$, and

$$ $\displaystyle\left|\prod_{(s^{\prime},a^{\prime})\sqsubseteq\sigma(s)}\pi_{1}^{(t+1)}(a^{\prime}{\,|\,}s^{\prime})-\prod_{(s^{\prime},a^{\prime})\sqsubseteq\sigma(s)}\pi_{1}^{(t)}(a^{\prime}{\,|\,}s^{\prime})\right|$ $\displaystyle\leq$ $\displaystyle\prod_{(s^{\prime},a^{\prime})\sqsubseteq\sigma_{1}(\sigma(s))}\pi_{1}^{(t+1)}(a^{\prime}{\,|\,}s^{\prime})\left|\pi_{1}^{(t+1)}(\sigma(s))-\pi_{1}^{(t)}(\sigma(s))\right|$ $\displaystyle+\pi_{1}^{(t)}(\sigma(s))\left|\prod_{(s^{\prime},a^{\prime})\sqsubseteq\sigma(\sigma(s))}\pi_{1}^{(t+1)}(a^{\prime}{\,|\,}s^{\prime})-\prod_{(s^{\prime},a^{\prime})\sqsubseteq\sigma(\sigma(s))}\pi_{1}^{(t)}(a^{\prime}{\,|\,}s^{\prime})\right|$ $\displaystyle\leq$ $\displaystyle\left|\pi_{1}^{(t+1)}(\sigma(s))-\pi_{1}^{(t)}(\sigma(s))\right|+\left|\prod_{(s^{\prime},a^{\prime})\sqsubseteq\sigma(\sigma(s))}\pi_{1}^{(t+1)}(a^{\prime}{\,|\,}s^{\prime})-\prod_{(s^{\prime},a^{\prime})\sqsubseteq\sigma(\sigma(s))}\pi_{1}^{(t)}(a^{\prime}{\,|\,}s^{\prime})\right|.$ $$

We abuse the notion of $\pi_{1}(\sigma(s))$ as $\pi_{1}(a^{\prime}{\,|\,}s^{\prime})$ and $\sigma(\sigma(s))=\sigma(s^{\prime})$, given $\sigma(s)=(s^{\prime},a^{\prime})$.

By recursively applying the process above, we will get

$$ $\displaystyle\left|\prod_{(s^{\prime},a^{\prime})\sqsubseteq\sigma(s)}\pi_{1}^{(t+1)}(a^{\prime}{\,|\,}s^{\prime})-\prod_{(s^{\prime},a^{\prime})\sqsubseteq\sigma(s)}\pi_{1}^{(t)}(a^{\prime}{\,|\,}s^{\prime})\right|\leq\sum_{(s^{\prime},a^{\prime})\sqsubseteq\sigma(s)}\left|\pi_{1}^{(t+1)}(a^{\prime}{\,|\,}s^{\prime})-\pi_{1}^{(t)}(a^{\prime}{\,|\,}s^{\prime})\right|.$ $$

###### Lemma B.2 .

Consider the update-rule Eq ([5.2](#S5.E2)). When we choose $\psi_{s}^{\Delta}$ to be negative entropy or Euclidean distance, we have

$$ $\displaystyle\left\|\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s)\right\|_{1},\left\|\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s)-\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s)\right\|_{1}\leq C_{s}^{\mathrm{diff}}\eta_{s}.$ (B.2) $$

where

$$ $\displaystyle C_{s}^{\mathrm{diff}}\coloneqq\begin{cases}\frac{2}{\alpha_{s}}\left(\left\|\bm{q}\right\|_{\infty}+\frac{\tau\alpha_{s}}{M_{1}}\log\frac{1}{\gamma}\right)&\text{Entropy}\\ \frac{|\mathcal{A}_{s}|}{\alpha_{s}}\left\|\bm{q}\right\|_{\infty}+\frac{2\sqrt{|\mathcal{A}_{s}|}\tau}{M_{1}}&\text{Euclidean Distance}\end{cases}$ (B.3) $$

The proof is postponed to Appendix [F.3](#A6.SS3).
By using [Lemma B.2](#A2.Thmtheorem2), we have

$$ $\displaystyle\left|m^{(t+1)}_{s}-m^{(t)}_{s}\right|$ $\displaystyle\leq$ $\displaystyle\frac{1}{\gamma^{2}}\sum_{(s^{\prime},a^{\prime})\sqsubseteq\sigma(s)}\left|\pi_{1}^{(t+1)}(a^{\prime}{\,|\,}s^{\prime})-\pi_{1}^{(t)}(a^{\prime}{\,|\,}s^{\prime})\right|$ $\displaystyle\leq$ $\displaystyle\frac{1}{\gamma^{2}}\sum_{(s^{\prime},a^{\prime})\sqsubseteq\sigma(s)}\left(\left|\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu_{1}^{(t+1)}(a^{\prime}{\,|\,}s^{\prime})-\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu_{1}^{(t)}(a^{\prime}{\,|\,}s^{\prime})\right|+\left|\pi_{1}^{(t+1)}(a^{\prime}{\,|\,}s^{\prime})-\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu_{1}^{(t+1)}(a^{\prime}{\,|\,}s^{\prime})\right|+\left|\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu_{1}^{(t)}(a^{\prime}{\,|\,}s^{\prime})-\pi_{1}^{(t)}(a^{\prime}{\,|\,}s^{\prime})\right|\right)$ $\displaystyle\leq$ $\displaystyle\frac{3}{\gamma^{2}}\sum_{(s^{\prime},a^{\prime})\sqsubseteq\sigma(s)}C_{s^{\prime}}^{\rm diff}\eta_{s^{\prime}}.$ $$

At the same time,

$$ $\left|\frac{m^{(t+1)}_{s}}{m^{(t)}_{s}}-1\right|=\frac{1}{m^{(t)}_{s}}\left|m^{(t+1)}_{s}-m^{(t)}_{s}\right|\leq\frac{3\sum_{(s^{\prime},a^{\prime})\sqsubseteq\sigma(s)}C_{s^{\prime}}^{\rm diff}\eta_{s^{\prime}}}{\gamma^{2}M_{1}}.$ $$

Therefore, $C_{s}^{-}=\frac{6}{\gamma^{2}}\max_{s^{\prime}\in{\mathcal{S}}}C_{s^{\prime}}^{\rm diff}$ and $C_{s}^{/}=\frac{6\max_{s^{\prime}\in{\mathcal{S}}}C_{s^{\prime}}^{\rm diff}}{\gamma^{2}M_{1}}$ by [A](#A2.I1.i1). ∎

###### Lemma B.3 (Stability of $m^{(t)}_{s}$ under entropy regularizer) .

Consider when $\psi^{\Delta}_{s}(\bm{u})=\alpha_{s}\left(\log|\mathcal{A}_{s}|+\sum_{a\in\mathcal{A}_{s}}u_{a}\log u_{a}\right)$ for any $s\in{\mathcal{S}}$, and [A](#A2.I1.i1), [B](#A2.I1.i2), [C](#A2.I1.i3) are satisfied. For any $s\in{\mathcal{S}}$ and $t=1,2,...,T$, when $m^{(t)}_{s}$ is the trajectory Q-value feedback, we have

$$ $\displaystyle C_{s}^{-}=\frac{12\max_{s^{\prime}\in{\mathcal{S}}}\left(\frac{2\left\|\bm{q}\right\|_{\infty}}{\alpha_{s^{\prime}}}+\frac{\tau}{M_{1}}\log\frac{1}{\gamma}\right)}{\gamma}$ $\displaystyle C_{s}^{/}=12\max_{s^{\prime}\in{\mathcal{S}}}\left(\frac{2\left\|\bm{q}\right\|_{\infty}}{\alpha_{s^{\prime}}}+\frac{\tau}{M_{1}}\log\frac{1}{\gamma}\right).$ (B.4) $$

###### Proof.

$$ $\displaystyle\left|m^{(t+1)}_{s}-m^{(t)}_{s}\right|=$ $\displaystyle\left|\frac{1}{\mu_{1}^{(t+1)}(\sigma(s))}-\frac{1}{\mu_{1}^{(t)}(\sigma(s))}\right|=\frac{1}{\mu_{1}^{(t+1)}(\sigma(s))}\left|\frac{\mu_{1}^{(t+1)}(\sigma(s))}{\mu_{1}^{(t)}(\sigma(s))}-1\right|.$ $$

We will then use the following lemma which shows the multiplicative stability when using negative entropy regularizer.

###### Lemma B.4 .

When $\psi^{\Delta}_{s}(\bm{u})=\alpha_{s}\left(\log|\mathcal{A}_{s}|+\sum_{a\in\mathcal{A}_{s}}u_{a}\log u_{a}\right)$ for any $s\in{\mathcal{S}}$, [A](#A2.I1.i1), [B](#A2.I1.i2), [C](#A2.I1.i3) are satisfied, then for any $s\in{\mathcal{S}},h\in s,t=1,2,...,T$, we have

$$ $\displaystyle\left|\frac{\mu_{1}^{(t+1)}(\sigma_{1}(h))}{\mu_{1}^{(t)}(\sigma_{1}(h))}-1\right|,\left|\frac{\mu_{2}^{(t+1)}(\sigma_{2}(h))}{\mu_{2}^{(t)}(\sigma_{2}(h))}-1\right|\leq 12\eta_{s}^{\rm anc}\max_{s^{\prime}\in{\mathcal{S}}}\left(\frac{2\left\|\bm{q}\right\|_{\infty}}{\alpha_{s^{\prime}}}+\frac{\tau}{M_{1}}\log\frac{1}{\gamma}\right).$ (B.5) $$

The proof can be found at the end of this section. Then, for any $s\in{\mathcal{S}}_{1}$, we have

$$ $\displaystyle\left|m^{(t+1)}_{s}-m^{(t)}_{s}\right|=\frac{1}{\mu_{1}^{(t+1)}(\sigma(s))}\left|\frac{\mu_{1}^{(t+1)}(\sigma(s))}{\mu_{1}^{(t)}(\sigma(s))}-1\right|\leq$ $\displaystyle\frac{12\eta_{s}^{\rm anc}\max_{s^{\prime}\in{\mathcal{S}}}\left(\frac{2\left\|\bm{q}\right\|_{\infty}}{\alpha_{s^{\prime}}}+\frac{\tau}{M_{1}}\log\frac{1}{\gamma}\right)}{\mu_{1}^{(t+1)}(\sigma(s))}$ $\displaystyle\leq$ $\displaystyle\frac{12\eta_{s}^{\rm anc}\max_{s^{\prime}\in{\mathcal{S}}}\left(\frac{2\left\|\bm{q}\right\|_{\infty}}{\alpha_{s^{\prime}}}+\frac{\tau}{M_{1}}\log\frac{1}{\gamma}\right)}{\gamma}.$ $$

Therefore, $C_{s}^{-}=\frac{12\max_{s^{\prime}\in{\mathcal{S}}}\left(\frac{2\left\|\bm{q}\right\|_{\infty}}{\alpha_{s^{\prime}}}+\frac{\tau}{M_{1}}\log\frac{1}{\gamma}\right)}{\gamma}$.

Similarly, we have $C_{s}^{/}=12\max_{s^{\prime}\in{\mathcal{S}}}\left(\frac{2\left\|\bm{q}\right\|_{\infty}}{\alpha_{s^{\prime}}}+\frac{\tau}{M_{1}}\log\frac{1}{\gamma}\right)$. ∎

###### Proof of Lemma B.4 .

Firstly, we invoke Lemma [B.5](#A2.Thmtheorem5).

###### Lemma B.5 .

Consider update-rule Eq ([5.2](#S5.E2)). When $\psi^{\Delta}_{s}(\bm{u})=\alpha_{s}\left(\log|\mathcal{A}|+\sum_{a\in\mathcal{A}_{s}}u_{a}\log u_{a}\right)$ for any $s\in{\mathcal{S}}$, and [B](#A2.I1.i2) is satisfied, for any $s\in{\mathcal{S}}$, $a\in\mathcal{A}_{s}$ and $t=1,2,...,T$,

$$ $\displaystyle\exp\left(-\frac{\eta_{s}}{\alpha_{s}}\left(2\left\|\bm{q}\right\|_{\infty}+\frac{\tau\alpha_{s}}{M_{1}}\log\frac{1}{\gamma}\right)\right)\leq\frac{\pi^{(t)}(a{\,|\,}s)}{\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}(a{\,|\,}s)},\frac{\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}(a{\,|\,}s)}{\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}(a{\,|\,}s)}\leq\exp\left(\frac{\eta_{s}}{\alpha_{s}}\left(2\left\|\bm{q}\right\|_{\infty}+\frac{\tau\alpha_{s}}{M_{1}}\log\frac{1}{\gamma}\right)\right)$ (B.6) $\displaystyle C_{s}^{\text{diff}}=\frac{2}{\alpha_{s}}\left(2\left\|\bm{q}\right\|_{\infty}+\frac{\tau\alpha_{s}}{M_{1}}\log\frac{1}{\gamma}\right).$ (B.7) $$

The proof is postponed to Appendix [F.3](#A6.SS3).

By Lemma [B.5](#A2.Thmtheorem5), we have

$$ $\displaystyle\frac{\mu_{1}^{(t+1)}(\sigma_{1}(h))}{\mu_{1}^{(t)}(\sigma_{1}(h))}=$ $\displaystyle\frac{\prod_{(s^{\prime},a^{\prime})\sqsubseteq\sigma_{1}(h)}\pi_{1}^{(t+1)}(a^{\prime}{\,|\,}s^{\prime})}{\prod_{(s^{\prime},a^{\prime})\sqsubseteq\sigma_{1}(h)}\pi_{1}^{(t)}(a^{\prime}{\,|\,}s^{\prime})}$ $\displaystyle=$ $\displaystyle\frac{\prod_{(s^{\prime},a^{\prime})\sqsubseteq\sigma_{1}(h)}\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu_{1}^{(t+1)}(a^{\prime}{\,|\,}s^{\prime})}{\prod_{(s^{\prime},a^{\prime})\sqsubseteq\sigma_{1}(h)}\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu_{1}^{(t)}(a^{\prime}{\,|\,}s^{\prime})}\cdot\frac{\prod_{(s^{\prime},a^{\prime})\sqsubseteq\sigma_{1}(h)}\pi_{1}^{(t+1)}(a^{\prime}{\,|\,}s^{\prime})}{\prod_{(s^{\prime},a^{\prime})\sqsubseteq\sigma_{1}(h)}\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu_{1}^{(t+1)}(a^{\prime}{\,|\,}s^{\prime})}\cdot\frac{\prod_{(s^{\prime},a^{\prime})\sqsubseteq\sigma_{1}(h)}\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu_{1}^{(t)}(a^{\prime}{\,|\,}s^{\prime})}{\prod_{(s^{\prime},a^{\prime})\sqsubseteq\sigma_{1}(h)}\pi_{1}^{(t)}(a^{\prime}{\,|\,}s^{\prime})}$ $\displaystyle\leq$ $\displaystyle\exp\left(3\sum_{(s^{\prime},a^{\prime})\sqsubseteq\sigma_{1}(h)}\frac{\eta_{s^{\prime}}}{\alpha_{s^{\prime}}}\left(2\left\|\bm{q}\right\|_{\infty}+\frac{\tau\alpha_{s^{\prime}}}{M_{1}}\log\frac{1}{\gamma}\right)\right)$ $\displaystyle\leq$ $\displaystyle\exp\left(3\max_{s^{\prime}\in{\mathcal{S}}}\left(\frac{2\left\|\bm{q}\right\|_{\infty}}{\alpha_{s^{\prime}}}+\frac{\tau}{M_{1}}\log\frac{1}{\gamma}\right)\sum_{(s^{\prime},a^{\prime})\sqsubseteq\sigma_{1}(h)}\eta_{s^{\prime}}\right)$ $\displaystyle\overset{\ref{lr:cond1}}{\leq}$ $\displaystyle\exp\left(6\max_{s^{\prime}\in{\mathcal{S}}}\left(\frac{2\left\|\bm{q}\right\|_{\infty}}{\alpha_{s^{\prime}}}+\frac{\tau}{M_{1}}\log\frac{1}{\gamma}\right)\eta_{s}^{\rm anc}\right)$ $\displaystyle\leq$ $\displaystyle 1+12\eta_{s}^{\rm anc}\max_{s^{\prime}\in{\mathcal{S}}}\left(\frac{2\left\|\bm{q}\right\|_{\infty}}{\alpha_{s^{\prime}}}+\frac{\tau}{M_{1}}\log\frac{1}{\gamma}\right).$ $$

At the last line, we use the fact that $e^{x}\leq 1+2x$ for $x\in[0,1]$. Similarly, by using $1+x\leq e^{x}$, we can also get the lower-bound $1-6\eta_{s}^{\rm anc}\max_{s^{\prime}\in{\mathcal{S}}}\left(\frac{2\left\|\bm{q}\right\|_{\infty}}{\alpha_{s^{\prime}}}+\frac{\tau}{M_{1}}\log\frac{1}{\gamma}\right)$. ∎

###### Lemma B.1 (Stability of m s ( t ) subscript superscript 𝑚 𝑡 𝑠 m^{(t)}_{s} under Euclidean regularizer) .

###### Proof.

###### Lemma B.2 .

###### Lemma B.3 (Stability of m s ( t ) subscript superscript 𝑚 𝑡 𝑠 m^{(t)}_{s} under entropy regularizer) .

###### Proof.

###### Lemma B.4 .

###### Proof of Lemma B.4 .

###### Lemma B.5 .

### B.2 Stability of Q-Value

###### Lemma B.6 (Stability of $m^{(t)}_{s}$ under Euclidean regularizer) .

Consider when $\psi^{\Delta}_{s}(\bm{u})=\frac{\alpha_{s}}{2}\sum_{a\in\mathcal{A}_{s}}u_{a}^{2}$ for any $s\in{\mathcal{S}}$, and [A](#A2.I1.i1) is satisfied. For any $s\in{\mathcal{S}}$ and $t=1,2,...,T$, when $m^{(t)}_{s}$ is the Q-value feedback, we have

$$ $\displaystyle C_{s}^{-}=6|s|\max_{s^{\prime}\in{\mathcal{S}}}C_{s^{\prime}}^{\rm diff}$ $\displaystyle C_{s}^{/}=\frac{6|s|}{M_{1}}\max_{s^{\prime}\in{\mathcal{S}}}C_{s^{\prime}}^{\rm diff}$ (B.8) $$

where $|s|$ is the number of nodes in infoset $s$.

###### Proof.

With Q-value feedback, for any $s\in{\mathcal{S}}_{1}$,

$$ $\displaystyle\left|m^{(t+1)}_{s}-m^{(t)}_{s}\right|=$ $\displaystyle\left|\sum_{h\in s}\mu_{c}(h)(\mu_{2}^{(t+1)}(\sigma_{2}(h))-\mu_{2}^{(t)}(\sigma_{2}(h)))\right|$ $\displaystyle\leq$ $\displaystyle\sum_{h\in s}\mu_{c}(h)\left|\mu_{2}^{(t+1)}(\sigma_{2}(h))-\mu_{2}^{(t)}(\sigma_{2}(h))\right|$ $\displaystyle\leq$ $\displaystyle|s|\max_{h\in s}\left|\mu_{2}^{(t+1)}(\sigma_{2}(h))-\mu_{2}^{(t)}(\sigma_{2}(h))\right|.$ $$

In the last line, $|s|$ denotes the number of nodes in $s$. By similar argument as in Lemma [B.1](#A2.Thmtheorem1), for any $h\in s$, we have

$$ $\displaystyle\left|\mu_{2}^{(t+1)}(\sigma_{2}(h))-\mu_{2}^{(t)}(\sigma_{2}(h))\right|$ $\displaystyle=$ $\displaystyle\left|\prod_{(s^{\prime},a^{\prime})\sqsubseteq\sigma_{2}(h)}\pi_{2}^{(t+1)}(a^{\prime}{\,|\,}s^{\prime})-\prod_{(s^{\prime},a^{\prime})\sqsubseteq\sigma_{2}(h)}\pi_{2}^{(t)}(a^{\prime}{\,|\,}s^{\prime})\right|$ $\displaystyle\leq$ $\displaystyle\sum_{(s^{\prime},a^{\prime})\sqsubseteq\sigma_{2}(h)}\left|\pi_{2}^{(t+1)}(a^{\prime}{\,|\,}s^{\prime})-\pi_{2}^{(t)}(a^{\prime}{\,|\,}s^{\prime})\right|$ $\displaystyle\leq$ $\displaystyle\sum_{(s^{\prime},a^{\prime})\sqsubseteq\sigma_{2}(h)}\left(\left|\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu_{2}^{(t+1)}(a^{\prime}{\,|\,}s^{\prime})-\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu_{2}^{(t)}(a^{\prime}{\,|\,}s^{\prime})\right|+\left|\pi_{2}^{(t+1)}(a^{\prime}{\,|\,}s^{\prime})-\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu_{2}^{(t+1)}(a^{\prime}{\,|\,}s^{\prime})\right|+\left|\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu_{2}^{(t)}(a^{\prime}{\,|\,}s^{\prime})-\pi_{2}^{(t)}(a^{\prime}{\,|\,}s^{\prime})\right|\right)$ $\displaystyle\leq$ $\displaystyle 3\sum_{(s^{\prime},a^{\prime})\sqsubseteq\sigma_{2}(h)}C_{s^{\prime}}^{\rm diff}\eta_{s^{\prime}}.$ $$

Therefore, $\left|m^{(t+1)}_{s}-m^{(t)}_{s}\right|\leq 3|s|\max_{h\in s}\sum_{(s^{\prime},a^{\prime})\sqsubseteq\sigma_{2}(h)}C_{s^{\prime}}^{\rm diff}\eta_{s^{\prime}}$. Similarly,

$$ $\displaystyle\left|\frac{m^{(t+1)}_{s}}{m^{(t)}_{s}}-1\right|=\frac{1}{m^{(t)}_{s}}\left|m^{(t+1)}_{s}-m^{(t)}_{s}\right|\leq\frac{3|s|}{M_{1}}\max_{h\in s}\sum_{(s^{\prime},a^{\prime})\sqsubseteq\sigma_{2}(h)}C_{s^{\prime}}^{\rm diff}\eta_{s^{\prime}}.$ $$

Finally, $C_{s}^{-}=6|s|\max_{s^{\prime}\in{\mathcal{S}}}C_{s^{\prime}}^{\rm diff}$ and $C_{s}^{/}=\frac{6|s|\max_{s^{\prime}\in{\mathcal{S}}}C_{s^{\prime}}^{\rm diff}}{M_{1}}$ according to [A](#A2.I1.i1). ∎

###### Lemma B.7 (Stability of $m^{(t)}_{s}$ under Entropy regularizer) .

Consider when $\psi^{\Delta}_{s}(\bm{u})=\alpha_{s}\left(\log|\mathcal{A}_{s}|+\sum_{a\in\mathcal{A}_{s}}u_{a}\log u_{a}\right)$ for any $s\in{\mathcal{S}}$, and [A](#A2.I1.i1), [B](#A2.I1.i2), [C](#A2.I1.i3) are satisfied. For any $s\in{\mathcal{S}}$ and $t=1,2,...,T$, when $m^{(t)}_{s}$ is the Q-value feedback, we have

$$ $\displaystyle C_{s}^{-}=12M_{2}\max_{s^{\prime}\in{\mathcal{S}}}\left(\frac{2\left\|\bm{q}\right\|_{\infty}}{\alpha_{s^{\prime}}}+\frac{\tau}{M_{1}}\log\frac{1}{\gamma}\right)$ $\displaystyle C_{s}^{/}=12\max_{s^{\prime}\in{\mathcal{S}}}\left(\frac{2\left\|\bm{q}\right\|_{\infty}}{\alpha_{s^{\prime}}}+\frac{\tau}{M_{1}}\log\frac{1}{\gamma}\right).$ (B.9) $$

###### Proof.

With Q-value, for any $s\in{\mathcal{S}}_{1}$, we have

$$ $\displaystyle\left|\frac{m^{(t+1)}_{s}}{m^{(t)}_{s}}-1\right|=$ $\displaystyle\left|\frac{\sum_{h\in s}\mu_{c}(h)\mu_{2}^{(t+1)}(\sigma_{2}(h))}{\sum_{h\in s}\mu_{c}(h)\mu_{2}^{(t)}(\sigma_{2}(h))}-1\right|.$ $$

By Lemma [B.4](#A2.Thmtheorem4), we have

$$ $\displaystyle\frac{\mu_{2}^{(t+1)}(\sigma_{2}(h))}{\mu_{2}^{(t)}(\sigma_{2}(h))}\leq 1+12\eta_{s}^{\rm anc}\max_{s^{\prime}\in{\mathcal{S}}}\left(\frac{2\left\|\bm{q}\right\|_{\infty}}{\alpha_{s^{\prime}}}+\frac{\tau}{M_{1}}\log\frac{1}{\gamma}\right)$ $$

Therefore,

$$ $\displaystyle\frac{\sum_{h\in s}\mu_{c}(h)\mu_{2}^{(t+1)}(\sigma_{2}(h))}{\sum_{h\in s}\mu_{c}(h)\mu_{2}^{(t)}(\sigma_{2}(h))}\leq$ $\displaystyle\frac{\sum_{h\in s}\mu_{c}(h)\left(1+12\eta_{s}^{\rm anc}\max_{s^{\prime}\in{\mathcal{S}}}\left(\frac{2\left\|\bm{q}\right\|_{\infty}}{\alpha_{s^{\prime}}}+\frac{\tau}{M_{1}}\log\frac{1}{\gamma}\right)\right)\mu_{2}^{(t)}(\sigma_{2}(h))}{\sum_{h\in s}\mu_{c}(h)\mu_{2}^{(t)}(\sigma_{2}(h))}$ $\displaystyle\leq$ $\displaystyle 1+12\eta_{s}^{\rm anc}\max_{s^{\prime}\in{\mathcal{S}}}\left(\frac{2\left\|\bm{q}\right\|_{\infty}}{\alpha_{s^{\prime}}}+\frac{\tau}{M_{1}}\log\frac{1}{\gamma}\right).$ $$

Similarly, we have

$$ $\displaystyle\frac{\sum_{h\in s}\mu_{c}(h)\mu_{2}^{(t+1)}(\sigma_{2}(h))}{\sum_{h\in s}\mu_{c}(h)\mu_{2}^{(t)}(\sigma_{2}(h))}\geq 1-12\eta_{s}^{\rm anc}\max_{s^{\prime}\in{\mathcal{S}}}\left(\frac{2\left\|\bm{q}\right\|_{\infty}}{\alpha_{s^{\prime}}}+\frac{\tau}{M_{1}}\log\frac{1}{\gamma}\right).$ $$

Therefore, $\left|\frac{m^{(t+1)}_{s}}{m^{(t)}_{s}}-1\right|\leq 12\eta_{s}^{\rm anc}\max_{s^{\prime}\in{\mathcal{S}}}\left(\frac{2\left\|\bm{q}\right\|_{\infty}}{\alpha_{s^{\prime}}}+\frac{\tau}{M_{1}}\log\frac{1}{\gamma}\right)$. At the same time,

$$ $\left|m^{(t+1)}_{s}-m^{(t)}_{s}\right|=m^{(t)}_{s}\left|\frac{m^{(t+1)}_{s}}{m^{(t)}_{s}}-1\right|\leq 12\eta_{s}^{\rm anc}M_{2}\max_{s^{\prime}\in{\mathcal{S}}}\left(\frac{2\left\|\bm{q}\right\|_{\infty}}{\alpha_{s^{\prime}}}+\frac{\tau}{M_{1}}\log\frac{1}{\gamma}\right).\qed$ $$

###### Lemma B.6 (Stability of m s ( t ) subscript superscript 𝑚 𝑡 𝑠 m^{(t)}_{s} under Euclidean regularizer) .

###### Proof.

###### Lemma B.7 (Stability of m s ( t ) subscript superscript 𝑚 𝑡 𝑠 m^{(t)}_{s} under Entropy regularizer) .

###### Proof.

## Appendix C Bidilated Regularizer

Dilated regularizer (Hoda et al., ) is the foundation of previous work (Lee et al., ; Liu et al., ; Sokota et al., ) to apply mirror-descent and its variants on sequence-form strategies. Recently, additional regularization has become a powerful tool for learning in EFGs (Liu et al., ; Sokota et al., ). Specifically, we can change the objective of the game to $\max_{\mu_{1}^{\pi_{1}}\in\Pi_{1}}\min_{\mu_{2}^{\pi_{2}}\in\Pi_{2}}\left(\mu_{1}^{\pi_{1}}\right)^{\top}\bm{A}\mu_{2}^{\pi_{2}}-\tau\psi^{\Pi_{1}}(\mu_{1}^{\pi_{1}})+\tau\psi^{\Pi_{2}}(\mu_{2}^{\pi_{2}})$, where $\tau\psi^{\Pi_{1}}(\mu_{1}^{\pi_{1}}),\tau\psi^{\Pi_{2}}(\mu_{2}^{\pi_{2}})$ is the additional regularizer and $\tau$ controls its magnitude. By adding the additional regularizer, the objective becomes strongly convex-concave instead of convex-concave, and thus linear convergence rate can be achieved.

However, the dilated regularizer of player $i\in[2]$ is $\psi^{\Pi_{i}}(\mu_{i}^{\pi_{i}})=\sum_{s\in{\mathcal{S}}_{i}}\mu_{i}^{\pi_{i}}(\sigma(s))\psi_{s}^{\Delta}(\pi_{i}(\cdot{\,|\,}s))$, which only counts the reach probability $\mu_{i}^{\pi_{i}}(\sigma(s))$ of player $i$. Therefore, when sampling a trajectory, to estimate the additional regularization, importance sampling is needed to offset the reach probability of player $3-i$ and the chance player, which causes a large dispersion of feedback. Therefore, to avoid importance sampling on the regularizer, we propose the bidilated regularizer in this section, to which all players contribute symmetrically. The bidilated regularizer of player 1 is defined as,

$$ $\displaystyle\psi^{\Pi_{1}}_{\rm bi}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}})\coloneqq\sum_{s\in{\mathcal{S}}_{1}}\mu_{1}^{\pi_{1}}(\sigma(s))\left(\sum_{h\in s}\mu_{c}(h)\mu_{2}^{\pi_{2}}(\sigma_{2}(h))\right)\psi_{s}^{\Delta}(\pi_{1}(\cdot{\,|\,}s)).$ (C.1) $$

The additional term is the probability of reaching infoset $s$ contributed by player 2 and the chance player. The bidilated regularizer for player 2 can also be defined similarly. In the following, we will show that several preferable properties of dilated regularizer still hold for its bidilated version.

Firstly, the bidilated regularizer $\psi^{\Pi_{1}}_{\rm bi}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}})$ is still convex with respect to $\mu_{1}^{\pi_{1}}$ and $\mu_{2}^{\pi_{2}}$ individually. This can be inferred from the fact that the dilated regularizer is convex with respect to $\mu_{1}^{\pi_{1}}$ (Hoda et al., ). By enforcing $\pi_{2}(\cdot{\,|\,}s)\geq\gamma_{s}\bm{\nu}_{s}$ for every $s\in{\mathcal{S}}_{2}$ with $\gamma_{s}>0,\bm{\nu}_{s}\in\Delta^{|\mathcal{A}_{s}|}$, where $\bm{\nu}_{s}$ has full support, we have $\mu_{2}^{\pi_{2}}(s,a)\geq\gamma>0$ for any $s\in{\mathcal{S}}_{2},a\in\mathcal{A}_{s}$, where $\gamma$ is a constant. Then, we have the following lemma.

###### Lemma C.1 .

For any $\tau,\gamma>0$, the Nash equilibrium $\bm{\mu}^{(\tau,\gamma),*}=(\mu_{1}^{(\tau,\gamma),*},\mu_{2}^{(\tau,\gamma),*})$ of $\max_{\mu_{1}^{\pi_{1}}\in\Pi_{1}\colon\mu_{1}^{\pi_{1}}\succeq\gamma}\allowbreak\min_{\mu_{2}^{\pi_{2}}\in\Pi_{2}\colon\mu_{2}^{\pi_{2}}\succeq\gamma}\allowbreak\left(\mu_{1}^{\pi_{1}}\right)^{\top}\bm{A}\mu_{2}^{\pi_{2}}-\tau\psi_{\rm bi}^{\Pi_{1}}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}})+\tau\psi_{\rm bi}^{\Pi_{2}}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}})$ is unique.

###### Proof.

Let define $F_{1}^{\tau}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}})\coloneqq-\bm{A}\mu_{2}^{\pi_{2}}+\tau\nabla_{\mu_{1}^{\pi_{1}}}\psi^{\Pi_{1}}_{\rm bi}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}})-\tau\nabla_{\mu_{1}^{\pi_{1}}}\psi^{\Pi_{2}}_{\rm bi}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}})$ and $F_{2}^{\tau}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}})\coloneqq\bm{A}^{\top}\mu_{1}^{\pi_{1}}+\tau\nabla_{\mu_{2}^{\pi_{2}}}\psi^{\Pi_{2}}_{\rm bi}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}})-\tau\nabla_{\mu_{2}^{\pi_{2}}}\psi^{\Pi_{2}}_{\rm bi}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}})$.

For any $\mu_{1}^{\pi_{1}^{\prime}}\in\Pi_{1}$, we have

$$ $\displaystyle\left\langle F_{1}^{\tau}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}}),\mu_{1}^{\pi_{1}}-\mu_{1}^{\pi_{1}^{\prime}}\right\rangle=$ $\displaystyle\left\langle-\bm{A}\mu_{2}^{\pi_{2}}+\tau\nabla_{\mu_{1}^{\pi_{1}}}\psi^{\Pi_{1}}_{\rm bi}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}})-\tau\nabla_{\mu_{1}^{\pi_{1}}}\psi^{\Pi_{2}}_{\rm bi}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}}),\mu_{1}^{\pi_{1}}-\mu_{1}^{\pi_{1}^{\prime}}\right\rangle$ $\displaystyle=$ $\displaystyle-\left\langle\bm{A}\mu_{2}^{\pi_{2}},\mu_{1}^{\pi_{1}}-\mu_{1}^{\pi_{1}^{\prime}}\right\rangle+\tau D_{\psi^{\Pi_{1}}_{\rm bi}(\cdot,\mu_{2}^{\pi_{2}})}\left(\mu_{1}^{\pi_{1}^{\prime}},\mu_{1}^{\pi_{1}}\right)$ $\displaystyle-\tau\psi^{\Pi_{1}}_{\rm bi}(\mu_{1}^{\pi_{1}^{\prime}},\mu_{2}^{\pi_{2}})+\tau\psi^{\Pi_{1}}_{\rm bi}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}})-\tau\psi^{\Pi_{2}}_{\rm bi}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}})+\tau\psi^{\Pi_{2}}_{\rm bi}(\mu_{1}^{\pi_{1}^{\prime}},\mu_{2}^{\pi_{2}}).$ $$

The last line uses the fact that $\psi^{\Pi_{2}}_{\rm bi}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}})$ is linear with respect to $\mu_{1}^{\pi_{1}}$.

The counterpart of $\mu_{2}^{\pi_{2}}$ is

$$ $\displaystyle\left\langle F_{2}^{\tau}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}}),\mu_{2}^{\pi_{2}}-\mu_{2}^{\pi_{2}^{\prime}}\right\rangle=$ $\displaystyle\left\langle\bm{A}^{\top}\mu_{1}^{\pi_{1}}+\tau\nabla_{\mu_{2}^{\pi_{2}}}\psi^{\Pi_{2}}_{\rm bi}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}})-\tau\nabla_{\mu_{2}^{\pi_{2}}}\psi^{\Pi_{2}}_{\rm bi}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}}),\mu_{2}^{\pi_{2}}-\mu_{2}^{\pi_{2}^{\prime}}\right\rangle$ $\displaystyle=$ $\displaystyle\left\langle\bm{A}^{\top}\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}}-\mu_{2}^{\pi_{2}^{\prime}}\right\rangle+\tau D_{\psi^{\Pi_{2}}_{\rm bi}(\mu_{1}^{\pi_{1}},\cdot)}\left(\mu_{2}^{\pi_{2}^{\prime}},\mu_{2}^{\pi_{2}}\right)$ $\displaystyle-\tau\psi^{\Pi_{2}}_{\rm bi}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}^{\prime}})+\tau\psi^{\Pi_{2}}_{\rm bi}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}})-\tau\psi^{\Pi_{1}}_{\rm bi}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}})+\tau\psi^{\Pi_{1}}_{\rm bi}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}^{\prime}}).$ $$

Let $\bm{\mu}^{\bm{\pi}}=(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}})$ and $F^{\tau}(\bm{\mu}^{\bm{\pi}})=(F_{1}^{\tau}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}}),F_{2}^{\tau}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}}))$. Then by taking the summation of equations above, we have

$$ $\displaystyle\left\langle F^{\tau}(\bm{\mu}^{\bm{\pi}}),\bm{\mu}^{\bm{\pi}}-\bm{\mu}^{\bm{\pi}^{\prime}}\right\rangle=$ $\displaystyle-\left(\mu_{1}^{\pi_{1}}\right)^{\top}\bm{A}\mu_{2}^{\pi_{2}^{\prime}}+(\mu_{1}^{\pi_{1}^{\prime}})^{\top}\bm{A}\mu_{2}^{\pi_{2}}+\tau D_{\psi^{\Pi_{1}}_{\rm bi}(\cdot,\mu_{2}^{\pi_{2}})}\left(\mu_{1}^{\pi_{1}^{\prime}},\mu_{1}^{\pi_{1}}\right)+\tau D_{\psi^{\Pi_{2}}_{\rm bi}(\mu_{1}^{\pi_{1}},\cdot)}\left(\mu_{2}^{\pi_{2}^{\prime}},\mu_{2}^{\pi_{2}}\right)$ $\displaystyle+\tau\psi^{\Pi_{1}}_{\rm bi}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}^{\prime}})-\tau\psi^{\Pi_{1}}_{\rm bi}(\mu_{1}^{\pi_{1}^{\prime}},\mu_{2}^{\pi_{2}})+\tau\psi^{\Pi_{2}}_{\rm bi}(\mu_{1}^{\pi_{1}^{\prime}},\mu_{2}^{\pi_{2}})-\tau\psi^{\Pi_{2}}_{\rm bi}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}^{\prime}}).$ $$

Then,

$$ $\displaystyle\left\langle F^{\tau}(\bm{\mu}^{\bm{\pi}})-F^{\tau}(\bm{\mu}^{\bm{\pi}^{\prime}}),\bm{\mu}^{\bm{\pi}}-\bm{\mu}^{\bm{\pi}^{\prime}}\right\rangle$ $\displaystyle=$ $\displaystyle\tau\left(D_{\psi^{\Pi_{1}}_{\rm bi}(\cdot,\mu_{2}^{\pi_{2}})}\left(\mu_{1}^{\pi_{1}^{\prime}},\mu_{1}^{\pi_{1}}\right)+D_{\psi^{\Pi_{2}}_{\rm bi}(\mu_{1}^{\pi_{1}},\cdot)}\left(\mu_{2}^{\pi_{2}^{\prime}},\mu_{2}^{\pi_{2}}\right)+D_{\psi^{\Pi_{1}}_{\rm bi}(\cdot,\mu_{2}^{\pi_{2}^{\prime}})}\left(\mu_{1}^{\pi_{1}},\mu_{1}^{\pi_{1}^{\prime}}\right)+D_{\psi^{\Pi_{2}}_{\rm bi}(\mu_{1}^{\pi_{1}^{\prime}},\cdot)}\left(\mu_{2}^{\pi_{2}},\mu_{2}^{\pi_{2}^{\prime}}\right)\right).\qed$ $$

Since $\bm{\mu}^{\bm{\pi}},\bm{\mu}^{\bm{\pi}^{\prime}}\succeq\gamma$, $D_{\psi^{\Pi_{1}}_{\rm bi}(\cdot,\mu_{2}^{\pi_{2}^{\prime}})}\left(\mu_{1}^{\pi_{1}},\mu_{1}^{\pi_{1}^{\prime}}\right)\geq\gamma\min_{h\in\mathcal{H}}\mu_{c}(h)D_{\psi^{\Pi_{1}}}\left(\mu_{1}^{\pi_{1}},\mu_{1}^{\pi_{1}^{\prime}}\right)$ by [Lemma 5.1](#S5.Thmtheorem1). Moreover, there exists $M>0$ so that $D_{\psi^{\Pi_{1}}}\left(\mu_{1}^{\pi_{1}},\mu_{1}^{\pi_{1}^{\prime}}\right)\geq M\left\|\mu_{1}^{\pi_{1}}-\mu_{1}^{\pi_{1}^{\prime}}\right\|^{2}$ according to Hoda et al. (); Lee et al. (). Therefore, the NE is unique when $\tau,\gamma>0$ by Rosen ().∎

###### Lemma C.1 .

###### Proof.

## Appendix D Proof of Theorem 5.2

###### Theorem D.1 (Formal Version of Theorem 5.2 ) .

Consider the update rule ([5.2](#S5.E2)) and $q^{(t)}(s,\cdot)$ is chosen to be counterfactual value, trajectory Q-value, or Q-value. When $\frac{\eta_{s}^{\rm anc}}{\eta_{s}}\leq\tau C_{s}^{\eta}$, where $C_{s}^{\eta}\coloneqq\frac{\gamma}{2C_{s}^{-}}\sum_{h\in s}\mu_{c}(h)$ for any $s\in{\mathcal{S}}$ and [A](#A2.I1.i1), [B](#A2.I1.i2), [C](#A2.I1.i3) are satisfied, we have the following guarantee.

$$ $\displaystyle\sum_{t=2}^{T}D_{\psi^{\Pi}}(\bm{\mu}^{(\tau,\gamma),*},\bm{\mu}^{\mkern 1.5mu\overline{\mkern-1.5mu\bm{\pi}\mkern-1.5mu}\mkern 1.5mu^{(t)}})$ $\displaystyle\leq$ $\displaystyle\frac{2}{\gamma\min_{s\in{\mathcal{S}}}\sum_{h\in s}\mu_{c}(h)}\sum_{s\in{\mathcal{S}}}\left(C_{s}^{/}+C_{s}^{-,Q}\right)\eta_{s}^{\mathrm{anc}}\mu^{(\tau,\gamma),*}(\sigma(s))\sum_{t=1}^{T}\left|\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\psi_{s}^{\Delta}(\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s))\right|$ $\displaystyle+\frac{4}{\tau\gamma\min_{s\in{\mathcal{S}}}\sum_{h\in s}\mu_{c}(h)}\sum_{s\in{\mathcal{S}}}C_{s}^{\mathrm{diff}}\mu^{(\tau,\gamma),*}(\sigma(s))\left\|\bm{q}\right\|_{\infty}\eta_{s}M_{2}T$ (D.1) $\displaystyle+\frac{2}{\tau\gamma\min_{s\in{\mathcal{S}}}\sum_{h\in s}\mu_{c}(h)}\sum_{s\in{\mathcal{S}}}\frac{m^{(1)}_{s}}{\eta_{s}}\mu^{(\tau,\gamma),*}(\sigma(s))D_{\psi_{s}^{\Delta}}(\pi_{p(s)}^{(\tau,\gamma),*}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(1)}_{p(s)}(\cdot{\,|\,}s)),$ $$

where $C_{s}^{-,Q}$ denotes $C_{s}^{-}$ associated with Q-value, regardless of which feedback type $q^{(t)}(s,\cdot)$ is.

Firstly, we will use a standard analysis of the update rule ([5.2](#S5.E2)). For notational simplicity, we define $\mu_{-p(s)}^{(t)}(s)\coloneqq\sum_{h\in s}\mu_{c}(h)\mu_{3-p(s)}^{(t)}(\sigma_{3-p(s)}(h))$.

###### Lemma D.2 (Generalized from Lemma C.2. in Liu et al. ( 2023 ) ) .

Consider the update rule in Eq ([5.2](#S5.E2)). When $\psi_{s}^{\Delta}$ satisfies $D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\pi_{p(s)}^{\prime}(\cdot{\,|\,}s))\geq\frac{1}{2}\|\pi_{p(s)}(\cdot{\,|\,}s)-\pi_{p(s)}^{\prime}(\cdot{\,|\,}s)\|^{2}$, then for any $\pi_{p(s)}(\cdot{\,|\,}s)\in\Delta^{|\mathcal{A}_{s}|}$ and $t\geq 1$, we have

$$ $\begin{split}&\eta_{s}\frac{\tau\mu_{-p(s)}^{(t)}(s)}{m^{(t)}_{s}}\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\eta_{s}\frac{\tau\mu_{-p(s)}^{(t)}(s)}{m^{(t)}_{s}}\psi_{s}^{\Delta}(\pi_{p(s)}(\cdot{\,|\,}s))\\ &+\eta_{s}\tau\left(\frac{\mu_{-p(s)}^{(t-1)}(s)}{m^{(t-1)}_{s}}-\frac{\mu_{-p(s)}^{(t)}(s)}{m^{(t)}_{s}}\right)\left(\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\psi_{s}^{\Delta}(\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s))\right)\\ &+\eta_{s}\left\langle-q^{(t)}(s,\cdot),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\pi_{p(s)}(\cdot{\,|\,}s)\right\rangle\\ \leq&D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s))-(1+\eta_{s}\frac{\tau\mu_{-p(s)}^{(t)}(s)}{m^{(t)}_{s}})D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s))\\ &-(1+\eta_{s}\frac{\tau\mu_{-p(s)}^{(t-1)}(s)}{m^{(t-1)}_{s}})D_{\psi_{s}^{\Delta}}(\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))\\ &-D_{\psi_{s}^{\Delta}}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s))+\eta_{s}\left\langle q^{(t-1)}(s,\cdot)-q^{(t)}(s,\cdot),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s)\right\rangle.\end{split}$ $$

The proof is postponed to Appendix [D.2](#A4.SS2).

Multiplying $m^{(t)}_{s}$ on both sides of Lemma [D.2](#A4.Thmtheorem2), we have

$$ $\displaystyle\eta_{s}\tau\mu_{-p(s)}^{(t)}(s)\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\eta_{s}\tau\mu_{-p(s)}^{(t)}(s)\psi_{s}^{\Delta}(\pi_{p(s)}(\cdot{\,|\,}s))$ $\displaystyle+\eta_{s}\tau\left(\frac{m^{(t)}_{s}}{m^{(t-1)}_{s}}\mu_{-p(s)}^{(t-1)}(s)-\mu_{-p(s)}^{(t)}(s)\right)\left(\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\psi_{s}^{\Delta}(\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s))\right)$ $\displaystyle+\eta_{s}m^{(t)}_{s}\langle-q^{(t)}(s,\cdot),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\pi_{p(s)}(\cdot{\,|\,}s)\rangle$ $\displaystyle\leq$ $\displaystyle m^{(t)}_{s}D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s))-(m^{(t)}_{s}+\eta_{s}\tau\mu_{-p(s)}^{(t)}(s))D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s))$ $\displaystyle-(m^{(t)}_{s}+\eta_{s}\tau\frac{m^{(t)}_{s}}{m^{(t-1)}_{s}}\mu_{-p(s)}^{(t-1)}(s))D_{\psi_{s}^{\Delta}}(\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))$ $\displaystyle-m^{(t)}_{s}D_{\psi_{s}^{\Delta}}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s))+\eta_{s}m^{(t)}_{s}\left\langle q^{(t-1)}(s,\cdot)-q^{(t)}(s,\cdot),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s)\right\rangle.$ $$

By noticing the fact that $\mu_{-p(s)}^{(t)}(s)$ is equal to $m_{s}^{(t)}$ associated with Q-value, we can use [1](#Thmproperty1) and [2](#Thmproperty2) and get,

$$ $\displaystyle\left|\frac{m^{(t)}_{s}}{m^{(t-1)}_{s}}\mu_{-p(s)}^{(t-1)}(s)-\mu_{-p(s)}^{(t)}(s)\right|\leq\left|\frac{m^{(t)}_{s}}{m^{(t-1)}_{s}}-1\right|\mu_{-p(s)}^{(t-1)}(s)+\left|\mu_{-p(s)}^{(t-1)}(s)-\mu_{-p(s)}^{(t)}(s)\right|\leq C_{s}^{/}\eta_{s}^{\rm anc}+C_{s}^{-,Q}\eta_{s}^{\rm anc}.$ $$

We also use the fact that $\mu_{-p(s)}^{(t)}(s)\leq 1$ in the last inequality. We use $C_{s}^{-,Q}$ to denote the $C_{s}^{-}$ associated with Q-value for simplicity.

Furthermore, by using Lemma [B.2](#A2.Thmtheorem2) and Hölder’s Inequality, we have

$$ $\displaystyle\left|\left\langle q^{(t-1)}(s,\cdot)-q^{(t)}(s,\cdot),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s)\right\rangle\right|$ $\displaystyle\leq$ $\displaystyle\left\|q^{(t)}(s,\cdot)-q^{(t-1)}(s,\cdot)\right\|_{\infty}\cdot\left\|\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s)\right\|_{1}\leq 2C_{s}^{\mathrm{diff}}\left\|\bm{q}\right\|_{\infty}\eta_{s}.$ $$

where $\left\|\bm{q}\right\|_{\infty}=\max_{t\in[T],s\in{\mathcal{S}}}\left\|q^{(t)}(s,\cdot)\right\|_{\infty}$.

By telescoping and non-negativity of Bregman divergence, we have

$$ $\displaystyle\sum_{t=1}^{T}\left(\eta_{s}\tau\mu_{-p(s)}^{(t)}(s)\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\eta_{s}\tau\mu_{-p(s)}^{(t)}(s)\psi_{s}^{\Delta}(\pi_{p(s)}(\cdot{\,|\,}s))+\eta_{s}m^{(t)}_{s}\langle-q^{(t)}(s,\cdot),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\pi_{p(s)}(\cdot{\,|\,}s)\rangle\right)$ $\displaystyle\leq$ $\displaystyle\sum_{t=2}^{T}\underbrace{\left(m^{(t)}_{s}-m^{(t-1)}_{s}-\eta_{s}\tau\mu_{-p(s)}^{(t-1)}(s)\right)}_{\leavevmode\hbox to7.23pt{\vbox to7.23pt{\pgfpicture\makeatletter\hbox{\hskip 3.61601pt\lower-3.61601pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.41602pt}{0.0pt}\pgfsys@curveto{3.41602pt}{1.88663pt}{1.88663pt}{3.41602pt}{0.0pt}{3.41602pt}\pgfsys@curveto{-1.88663pt}{3.41602pt}{-3.41602pt}{1.88663pt}{-3.41602pt}{0.0pt}\pgfsys@curveto{-3.41602pt}{-1.88663pt}{-1.88663pt}{-3.41602pt}{0.0pt}{-3.41602pt}\pgfsys@curveto{1.88663pt}{-3.41602pt}{3.41602pt}{-1.88663pt}{3.41602pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s))$ $\displaystyle+\left(C_{s}^{/}+C_{s}^{-,Q}\right)\eta_{s}^{\rm anc}\eta_{s}\tau\sum_{t=1}^{T}\left|\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\psi_{s}^{\Delta}(\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s))\right|+2C_{s}^{\mathrm{diff}}\left\|\bm{q}\right\|_{\infty}\eta_{s}^{2}M_{2}T$ $\displaystyle+m^{(1)}_{s}D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(1)}_{p(s)}(\cdot{\,|\,}s)).$ $$

1 can be upper-bounded by $C_{s}^{-}\eta_{s}^{\mathrm{anc}}-\eta_{s}\tau\gamma\sum_{h\in s}\mu_{c}(h)\leq-\frac{\eta_{s}\tau\gamma}{2}\sum_{h\in s}\mu_{c}(h)$ by [2](#Thmproperty2) and letting $\frac{\eta_{s}^{\mathrm{anc}}}{\eta_{s}}\leq\frac{\tau\gamma}{2C_{s}^{-}}\sum_{h\in s}\mu_{c}(h)$. By non-negativity of Bregman divergence, we have

$$ $\displaystyle\sum_{t=1}^{T}\left(\eta_{s}\tau\mu_{-p(s)}^{(t)}(s)\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\eta_{s}\tau\mu_{-p(s)}^{(t)}(s)\psi_{s}^{\Delta}(\pi_{p(s)}(\cdot{\,|\,}s))+\eta_{s}m^{(t)}_{s}\langle-q^{(t)}(s,\cdot),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\pi_{p(s)}(\cdot{\,|\,}s)\rangle\right)$ $\displaystyle\leq$ $\displaystyle-\frac{\eta_{s}\tau\gamma\sum_{h\in s}\mu_{c}(h)}{2}\sum_{t=2}^{T}D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s))+\left(C_{s}^{/}+C_{s}^{-,Q}\right)\eta_{s}\tau\eta_{s}^{\mathrm{anc}}\sum_{t=1}^{T}\left|\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\psi_{s}^{\Delta}(\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s))\right|$ $\displaystyle+2C_{s}^{\mathrm{diff}}\left\|\bm{q}\right\|_{\infty}\eta_{s}^{2}M_{2}T+m^{(1)}_{s}D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(1)}_{p(s)}(\cdot{\,|\,}s)).$ $$

Then, we will use the following regret decomposition lemma to extend the difference within an infoset above to the difference of the game.

###### Lemma D.3 (Lemma 5.1 in Liu et al. ( 2023 ) ) .

Let $\Pi\coloneqq\Pi_{1}\times\Pi_{2}$, the polytope of all valid sequence-form joint strategies. For any $\mu_{1}^{\pi_{1}}\in\Pi_{1},\mu_{2}^{\pi_{2}}\in\Pi_{2}$, we let $\bm{\mu}^{\bm{\pi}}=(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}})\in\Pi$ to denote the joint strategy, $\psi^{\Pi}(\bm{\mu}^{\bm{\pi}})\colon\Pi\to\mathbb{R}=\psi^{\Pi_{1}}(\mu_{1}^{\pi_{1}})+\psi^{\Pi_{2}}(\mu_{2}^{\pi_{2}})$, and $F(\bm{\mu}^{\bm{\pi}})\coloneqq(-\bm{A}\mu_{2}^{\pi_{2}},\bm{A}^{\top}\mu_{1}^{\pi_{1}})$. For any $\bm{\mu}^{(1)},\bm{\mu}^{(2)},...,\bm{\mu}^{(T)},\bm{\mu}^{\bm{\pi}}\in\Pi$ and $\tau\geq 0$, we have

$$ $\displaystyle G^{(T),\Pi}(\bm{\mu}^{\bm{\pi}})\coloneqq$ $\displaystyle\sum_{t=1}^{T}(F(\bm{\mu}^{(t)})^{\top}(\bm{\mu}^{(t)}-\bm{\mu}^{\bm{\pi}})+\tau\psi^{\Pi}(\bm{\mu}^{(t)})-\tau\psi^{\Pi}(\bm{\mu}^{\bm{\pi}}))$ $\displaystyle=$ $\displaystyle\sum_{s\in{\mathcal{S}}}\mu^{\bm{\pi}}(\sigma(s))G^{(T)}(s;\pi_{p(s)}(\cdot{\,|\,}s))$ (D.2) $\displaystyle R^{(T),\Pi}\coloneqq$ $\displaystyle\max_{\bm{\mu}^{\widehat{\bm{\pi}}}\in\Pi}G^{(T),\Pi}(\bm{\mu}^{\widehat{\bm{\pi}}})\leq\max_{\bm{\mu}^{\widehat{\bm{\pi}}}\in\Pi}\sum_{s\in{\mathcal{S}}}\mu^{\widehat{\bm{\pi}}}(\sigma(s))R^{(T)}(s)$ (D.3) $$

where

$$ $\displaystyle V^{(t)}_{p}(s,a)\coloneqq$ $\displaystyle\sum_{(s,a)\sqsubseteq s^{\prime}}\frac{\mu^{(t)}_{p}(\sigma(s^{\prime}))}{\mu^{(t)}_{p}(s,a)}\psi_{s^{\prime}}^{\Delta}(\pi_{p}^{(t)}(\cdot{\,|\,}s^{\prime}))$ (D.4) $\displaystyle G^{(T)}(s;\pi_{p(s)}(\cdot{\,|\,}s))\coloneqq$ $\displaystyle\sum_{t=1}^{T}\Big{(}\left\langle-\mathsf{CF}_{p(s)}^{(t)}(s,\cdot)+\tau V^{(t)}_{p(s)}(s,\cdot),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\pi_{p(s)}(\cdot{\,|\,}s)\right\rangle$ $\displaystyle+\tau\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\tau\psi_{s}^{\Delta}(\pi_{p(s)}(\cdot{\,|\,}s))\Big{)}$ (D.5) $\displaystyle R^{(T)}(s)\coloneqq$ $\displaystyle\max_{\widehat{\pi}_{p(s)}(\cdot{\,|\,}s)\in\Delta^{|\mathcal{A}_{s}|}}G^{(T)}(s;\widehat{\pi}_{p(s)}(\cdot{\,|\,}s)).$ (D.6) $$

By using [Lemma D.3](#A4.Thmtheorem3)(^3^33It can be easily generalized to bidilated version by absorbing the reach probability of player $3-p$ and the chance player into $\psi_{s}^{\Delta}$ for $\psi^{\Pi_{p}}_{\rm bi}$ and player $p$. For $\psi^{\Pi_{3-p}}_{\rm bi}$, since it is linear with respect to $\mu^{\pi_{p}}_{p}$, it can be combined into the counterfactual value.), we have

$$ $\displaystyle\sum_{s\in{\mathcal{S}}}\mu^{(\tau,\gamma),*}(\sigma(s))\sum_{t=1}^{T}\Big{(}\tau\mu_{-p(s)}^{(t)}(s)\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\tau\mu_{-p(s)}^{(t)}(s)\psi_{s}^{\Delta}(\pi_{p(s)}^{(\tau,\gamma),*}(\cdot{\,|\,}s))$ $\displaystyle+m^{(t)}_{s}\langle-q^{(t)}(s,\cdot),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\pi_{p(s)}^{(\tau,\gamma),*}(\cdot{\,|\,}s)\rangle\Big{)}$ $\displaystyle=$ $\displaystyle\sum_{t=1}^{T}\Big{(}\left(\mu_{1}^{(\tau,\gamma),*}-\mu_{1}^{(t)}\right)^{\top}\bm{A}\mu_{2}^{(t)}+\left(\mu_{1}^{(t)}\right)^{\top}\bm{A}\left(\mu_{2}^{(t)}-\mu_{2}^{(\tau,\gamma),*}\right)$ $\displaystyle+\tau\left(\psi_{\rm bi}^{\Pi_{1}}(\mu_{1}^{(t)},\mu_{2}^{(t)})-\psi_{\rm bi}^{\Pi_{1}}(\mu_{1}^{(\tau,\gamma),*},\mu_{2}^{(t)})-\psi_{\rm bi}^{\Pi_{2}}(\mu_{1}^{(t)},\mu_{2}^{(t)})+\psi_{\rm bi}^{\Pi_{2}}(\mu_{1}^{(\tau,\gamma),*},\mu_{2}^{(t)})\right)$ $\displaystyle+\tau\left(\psi_{\rm bi}^{\Pi_{2}}(\mu_{1}^{(t)},\mu_{2}^{(t)})-\psi_{\rm bi}^{\Pi_{2}}(\mu_{1}^{(t)},\mu_{2}^{(\tau,\gamma),*})-\psi_{\rm bi}^{\Pi_{1}}(\mu_{1}^{(t)},\mu_{2}^{(t)})+\psi_{\rm bi}^{\Pi_{1}}(\mu_{1}^{(t)},\mu_{2}^{(\tau,\gamma),*})\right)\Big{)}$ $\displaystyle=$ $\displaystyle\sum_{t=1}^{T}\Big{(}\left(\mu_{1}^{(\tau,\gamma),*}-\mu_{1}^{(t)}\right)^{\top}\bm{A}\mu_{2}^{(\tau,\gamma),*}+\left(\mu_{1}^{(\tau,\gamma),*}\right)^{\top}\bm{A}\left(\mu_{2}^{(t)}-\mu_{2}^{(\tau,\gamma),*}\right)$ $\displaystyle+\tau\left(\psi_{\rm bi}^{\Pi_{1}}(\mu_{1}^{(t)},\mu_{2}^{(\tau,\gamma),*})-\psi_{\rm bi}^{\Pi_{1}}(\mu_{1}^{(\tau,\gamma),*},\mu_{1}^{(\tau,\gamma),*})+\psi_{\rm bi}^{\Pi_{2}}(\mu_{1}^{(\tau,\gamma),*},\mu_{1}^{(\tau,\gamma),*})-\psi_{\rm bi}^{\Pi_{2}}(\mu_{1}^{(t)},\mu_{2}^{(\tau,\gamma),*})\right)$ $\displaystyle+\tau\left(\psi_{\rm bi}^{\Pi_{2}}(\mu_{1}^{(\tau,\gamma),*},\mu_{2}^{(t)})-\psi_{\rm bi}^{\Pi_{2}}(\mu_{1}^{(\tau,\gamma),*},\mu_{2}^{(\tau,\gamma),*})+\psi_{\rm bi}^{\Pi_{1}}(\mu_{1}^{(\tau,\gamma),*},\mu_{1}^{(\tau,\gamma),*})-\psi_{\rm bi}^{\Pi_{1}}(\mu_{1}^{(\tau,\gamma),*},\mu_{2}^{(t)})\right)\Big{)}$ $\displaystyle\geq$ $\displaystyle 0.$ $$

The last inequality is because $\bm{\mu}^{(\tau,\gamma),*}$ is the NE of $\max_{\mu_{1}^{\pi_{1}}\in\Pi_{1}\colon\mu_{1}^{\pi_{1}}\succeq\gamma}\min_{\mu_{2}^{\pi_{2}}\in\Pi_{2}\colon\mu_{2}^{\pi_{2}}\succeq\gamma}\left(\mu_{1}^{\pi_{1}}\right)^{\top}\bm{A}\mu_{2}^{\pi_{2}}-\tau\psi_{\rm bi}^{\Pi_{1}}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}})+\tau\psi_{\rm bi}^{\Pi_{2}}(\mu_{1}^{\pi_{1}},\mu_{2}^{\pi_{2}})$.

Therefore,

$$ $\displaystyle 0\leq$ $\displaystyle\sum_{s\in{\mathcal{S}}}\mu^{(\tau,\gamma),*}(\sigma(s))\sum_{t=1}^{T}\Big{(}\tau\mu_{-p(s)}^{(t)}(s)\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\tau\mu_{-p(s)}^{(t)}(s)\psi_{s}^{\Delta}(\pi_{p(s)}^{(\tau,\gamma),*}(\cdot{\,|\,}s))$ $\displaystyle+m^{(t)}_{s}\langle-q^{(t)}(s,\cdot),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\pi_{p(s)}^{(\tau,\gamma),*}(\cdot{\,|\,}s)\rangle\Big{)}$ $\displaystyle\leq$ $\displaystyle-\frac{\tau\gamma\min_{s\in{\mathcal{S}}}\sum_{h\in s}\mu_{c}(h)}{2}\sum_{t=2}^{T}\sum_{s\in{\mathcal{S}}}\mu^{(\tau,\gamma),*}(\sigma(s))D_{\psi_{s}^{\Delta}}(\pi_{p(s)}^{(\tau,\gamma),*}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s))$ $\displaystyle+\sum_{s\in{\mathcal{S}}}\left(C_{s}^{/}+C_{s}^{-,Q}\right)\tau\eta_{s}^{\mathrm{anc}}\mu^{(\tau,\gamma),*}(\sigma(s))\sum_{t=1}^{T}\left|\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\psi_{s}^{\Delta}(\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s))\right|$ $\displaystyle+2\sum_{s\in{\mathcal{S}}}C_{s}^{\mathrm{diff}}\mu^{(\tau,\gamma),*}(\sigma(s))\left\|\bm{q}\right\|_{\infty}\eta_{s}M_{2}T+\sum_{s\in{\mathcal{S}}}\frac{m^{(1)}_{s}}{\eta_{s}}\mu^{(\tau,\gamma),*}(\sigma(s))D_{\psi_{s}^{\Delta}}(\pi_{p(s)}^{(\tau,\gamma),*}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(1)}_{p(s)}(\cdot{\,|\,}s)).$ $$

$(i)$ is because $\bm{\mu}^{(\tau,\gamma),*}$ is the NE of the regularized and perturbed EFG. Then, by rearranging the terms, we have

$$ $\displaystyle\sum_{t=2}^{T}D_{\psi^{\Pi}}(\bm{\mu}^{(\tau,\gamma),*},\bm{\mu}^{\mkern 1.5mu\overline{\mkern-1.5mu\bm{\pi}\mkern-1.5mu}\mkern 1.5mu^{(t)}})$ $\displaystyle=$ $\displaystyle\sum_{t=2}^{T}\sum_{s\in{\mathcal{S}}}\mu^{(\tau,\gamma),*}(\sigma(s))D_{\psi_{s}^{\Delta}}(\pi_{p(s)}^{(\tau,\gamma),*}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s))$ $\displaystyle\leq$ $\displaystyle\frac{2}{\gamma\min_{s\in{\mathcal{S}}}\sum_{h\in s}\mu_{c}(h)}\sum_{s\in{\mathcal{S}}}\left(C_{s}^{/}+C_{s}^{-,Q}\right)\eta_{s}^{\mathrm{anc}}\mu^{(\tau,\gamma),*}(\sigma(s))\sum_{t=1}^{T}\left|\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\psi_{s}^{\Delta}(\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s))\right|$ $\displaystyle+\frac{4}{\tau\gamma\min_{s\in{\mathcal{S}}}\sum_{h\in s}\mu_{c}(h)}\sum_{s\in{\mathcal{S}}}C_{s}^{\mathrm{diff}}\mu^{(\tau,\gamma),*}(\sigma(s))\left\|\bm{q}\right\|_{\infty}\eta_{s}M_{2}T$ $\displaystyle+\frac{2}{\tau\gamma\min_{s\in{\mathcal{S}}}\sum_{h\in s}\mu_{c}(h)}\sum_{s\in{\mathcal{S}}}\frac{m^{(1)}_{s}}{\eta_{s}}\mu^{(\tau,\gamma),*}(\sigma(s))D_{\psi_{s}^{\Delta}}(\pi_{p(s)}^{(\tau,\gamma),*}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(1)}_{p(s)}(\cdot{\,|\,}s)).$ $$

The first equality is by [Lemma 5.1](#S5.Thmtheorem1). Now, we achieved best-iterate convergence to the regularized NE $\bm{\mu}^{(\tau,\gamma),*}$ in terms of Bregman divergence.∎

###### Theorem D.1 (Formal Version of Theorem 5.2 ) .

###### Lemma D.2 (Generalized from Lemma C.2. in Liu et al. ( 2023 ) ) .

###### Lemma D.3 (Lemma 5.1 in Liu et al. ( 2023 ) ) .

### D.1 Proof of Lemma 5.1

By definition of Bregman divergence, we have

$$ $\displaystyle D_{\psi^{\Pi}}(\bm{\mu}^{\bm{\pi}},\bm{\mu}^{\widetilde{\bm{\pi}}})=\psi^{\Pi}(\bm{\mu}^{\bm{\pi}})-\psi^{\Pi}(\bm{\mu}^{\widetilde{\bm{\pi}}})-\left\langle\nabla\psi^{\Pi}(\bm{\mu}^{\widetilde{\bm{\pi}}}),\bm{\mu}^{\bm{\pi}}-\bm{\mu}^{\widetilde{\bm{\pi}}}\right\rangle.$ $$

For notational simplicity, we use $\mu^{\bm{\pi}}(s,a)$ as $\mu^{\bm{\pi}}_{p(s)}(s,a)$. Since $\psi^{\Pi}(\bm{\mu}^{\widetilde{\bm{\pi}}})=\sum_{s\in{\mathcal{S}}}\mu^{\widetilde{\bm{\pi}}}(\sigma(s))\psi_{s}^{\Delta}\left(\frac{\mu^{\widetilde{\bm{\pi}}}(s,\cdot)}{\mu^{\widetilde{\bm{\pi}}}(\sigma(s))}\right)$, for any $s\in{\mathcal{S}},a\in\mathcal{A}_{s}$, the gradient $\nabla_{\mu^{\widetilde{\bm{\pi}}}(s,a)}\psi^{\Pi}(\bm{\mu}^{\widetilde{\bm{\pi}}})$ is equal to

$$ $\displaystyle\nabla_{\mu^{\widetilde{\bm{\pi}}}(s,a)}\psi^{\Pi}(\bm{\mu}^{\widetilde{\bm{\pi}}})=$ $\displaystyle\sum_{s^{\prime}\in{\mathcal{S}}\colon\sigma(s^{\prime})=(s,a)}\left(\psi_{s^{\prime}}^{\Delta}\left(\frac{\mu^{\widetilde{\bm{\pi}}}(s^{\prime},\cdot)}{\mu^{\widetilde{\bm{\pi}}}(\sigma(s^{\prime}))}\right)-\left\langle\nabla\psi_{s^{\prime}}^{\Delta}\left(\frac{\mu^{\widetilde{\bm{\pi}}}(s^{\prime},\cdot)}{\mu^{\widetilde{\bm{\pi}}}(\sigma(s^{\prime}))}\right),\frac{\mu^{\widetilde{\bm{\pi}}}(s^{\prime},\cdot)}{\mu^{\widetilde{\bm{\pi}}}(\sigma(s^{\prime}))}\right\rangle\right)$ $\displaystyle+\nabla_{a}\psi_{s}^{\Delta}(\frac{\mu^{\widetilde{\bm{\pi}}}(s,\cdot)}{\mu^{\widetilde{\bm{\pi}}}(\sigma(s))}).$ $$

Therefore,

$$ $\displaystyle\left\langle\nabla\psi^{\Pi}(\bm{\mu}^{\widetilde{\bm{\pi}}}),\bm{\mu}^{\widetilde{\bm{\pi}}}\right\rangle$ $\displaystyle=$ $\displaystyle\sum_{s\in{\mathcal{S}},a\in\mathcal{A}_{s}}\mu^{\widetilde{\bm{\pi}}}(s,a)\sum_{s^{\prime}\in{\mathcal{S}}\colon\sigma(s^{\prime})=(s,a)}\left(\psi_{s^{\prime}}^{\Delta}\left(\frac{\mu^{\widetilde{\bm{\pi}}}(s^{\prime},\cdot)}{\mu^{\widetilde{\bm{\pi}}}(\sigma(s^{\prime}))}\right)-\left\langle\nabla\psi_{s^{\prime}}^{\Delta}\left(\frac{\mu^{\widetilde{\bm{\pi}}}(s^{\prime},\cdot)}{\mu^{\widetilde{\bm{\pi}}}(\sigma(s^{\prime}))}\right),\frac{\mu^{\widetilde{\bm{\pi}}}(s^{\prime},\cdot)}{\mu^{\widetilde{\bm{\pi}}}(\sigma(s^{\prime}))}\right\rangle\right)$ $\displaystyle+\sum_{s\in{\mathcal{S}},a\in\mathcal{A}_{s}}\mu^{\widetilde{\bm{\pi}}}(s,a)\nabla_{a}\psi_{s}^{\Delta}(\frac{\mu^{\widetilde{\bm{\pi}}}(s,\cdot)}{\mu^{\widetilde{\bm{\pi}}}(\sigma(s))})$ $\displaystyle=$ $\displaystyle\sum_{s\in{\mathcal{S}},a\in\mathcal{A}_{s}}\sum_{s^{\prime}\in{\mathcal{S}}\colon\sigma(s^{\prime})=(s,a)}\mu^{\widetilde{\bm{\pi}}}(\sigma(s^{\prime}))\psi_{s^{\prime}}^{\Delta}\left(\frac{\mu^{\widetilde{\bm{\pi}}}(s^{\prime},\cdot)}{\mu^{\widetilde{\bm{\pi}}}(\sigma(s^{\prime}))}\right)$ (D.7) $\displaystyle-\sum_{s\in{\mathcal{S}},a\in\mathcal{A}_{s}}\sum_{s^{\prime}\in{\mathcal{S}}\colon\sigma(s^{\prime})=(s,a)}\left\langle\nabla\psi_{s^{\prime}}^{\Delta}\left(\frac{\mu^{\widetilde{\bm{\pi}}}(s^{\prime},\cdot)}{\mu^{\widetilde{\bm{\pi}}}(\sigma(s^{\prime}))}\right),\mu^{\widetilde{\bm{\pi}}}(s^{\prime},\cdot)\right\rangle$ (D.8) $\displaystyle+\sum_{s\in{\mathcal{S}},a\in\mathcal{A}_{s}}\mu^{\widetilde{\bm{\pi}}}(s,a)\nabla_{a}\psi_{s}^{\Delta}(\frac{\mu^{\widetilde{\bm{\pi}}}(s,\cdot)}{\mu^{\widetilde{\bm{\pi}}}(\sigma(s))}).$ (D.9) $$

Note that Eq ([D.7](#A4.E7)) is equal to $\sum_{s\in{\mathcal{S}}}\mu^{\widetilde{\bm{\pi}}}(\sigma(s))\psi_{s}^{\Delta}\left(\frac{\mu^{\widetilde{\bm{\pi}}}(s,\cdot)}{\mu^{\widetilde{\bm{\pi}}}(\sigma(s))}\right)=\psi^{\Pi}(\bm{\mu}^{\widetilde{\bm{\pi}}})$ due to the uniqueness of $\sigma(s^{\prime})$.

Similarly, due to the uniqueness of $\sigma(s^{\prime})$, Eq ([D.8](#A4.E8)) is equal to $-\sum_{s\in{\mathcal{S}}}\left\langle\nabla\psi_{s}^{\Delta}\left(\frac{\mu^{\widetilde{\bm{\pi}}}(s,\cdot)}{\mu^{\widetilde{\bm{\pi}}}(\sigma(s))}\right),\mu^{\widetilde{\bm{\pi}}}(s,\cdot)\right\rangle$, which is equal to the negative of Eq ([D.9](#A4.E9)) and thus cancel out. Therefore,

$$ $\displaystyle\left\langle\nabla\psi^{\Pi}(\bm{\mu}^{\widetilde{\bm{\pi}}}),\bm{\mu}^{\widetilde{\bm{\pi}}}\right\rangle=\psi^{\Pi}(\bm{\mu}^{\widetilde{\bm{\pi}}}).$ $$

Moreover,

$$ $\displaystyle\left\langle\nabla\psi^{\Pi}(\bm{\mu}^{\widetilde{\bm{\pi}}}),\bm{\mu}^{\bm{\pi}}\right\rangle$ $\displaystyle=$ $\displaystyle\sum_{s\in{\mathcal{S}},a\in\mathcal{A}_{s}}\sum_{s^{\prime}\in{\mathcal{S}}\colon\sigma(s^{\prime})=(s,a)}\mu^{\bm{\pi}}(\sigma(s^{\prime}))\psi_{s^{\prime}}^{\Delta}\left(\frac{\mu^{\widetilde{\bm{\pi}}}(s^{\prime},\cdot)}{\mu^{\widetilde{\bm{\pi}}}(\sigma(s^{\prime}))}\right)$ $\displaystyle-\sum_{s\in{\mathcal{S}},a\in\mathcal{A}_{s}}\mu^{\bm{\pi}}(s,a)\sum_{s^{\prime}\in{\mathcal{S}}\colon\sigma(s^{\prime})=(s,a)}\left\langle\nabla\psi_{s^{\prime}}^{\Delta}\left(\frac{\mu^{\widetilde{\bm{\pi}}}(s^{\prime},\cdot)}{\mu^{\widetilde{\bm{\pi}}}(\sigma(s^{\prime}))}\right),\frac{\mu^{\widetilde{\bm{\pi}}}(s^{\prime},\cdot)}{\mu^{\widetilde{\bm{\pi}}}(\sigma(s^{\prime}))}\right\rangle$ $\displaystyle+\sum_{s\in{\mathcal{S}},a\in\mathcal{A}_{s}}\mu^{\bm{\pi}}(s,a)\nabla_{a}\psi_{s}^{\Delta}(\frac{\mu^{\widetilde{\bm{\pi}}}(s,\cdot)}{\mu^{\widetilde{\bm{\pi}}}(s,a)})$ $\displaystyle=$ $\displaystyle\sum_{s\in{\mathcal{S}}}\mu^{\bm{\pi}}(\sigma(s))\left(\psi_{s}^{\Delta}\left(\frac{\mu^{\widetilde{\bm{\pi}}}(s,\cdot)}{\mu^{\widetilde{\bm{\pi}}}(\sigma(s))}\right)+\left\langle\nabla\psi_{s}^{\Delta}\left(\frac{\mu^{\widetilde{\bm{\pi}}}(s,\cdot)}{\mu^{\widetilde{\bm{\pi}}}(\sigma(s))}\right),\frac{\mu^{\bm{\pi}}(s,\cdot)}{\mu^{\bm{\pi}}(\sigma(s))}-\frac{\mu^{\widetilde{\bm{\pi}}}(s,\cdot)}{\mu^{\widetilde{\bm{\pi}}}(\sigma(s))}\right\rangle\right).$ $$

Therefore,

$$ $\displaystyle D_{\psi^{\Pi}}(\bm{\mu}^{\bm{\pi}},\bm{\mu}^{\widetilde{\bm{\pi}}})$ $\displaystyle=$ $\displaystyle\sum_{s\in{\mathcal{S}}}\mu^{\bm{\pi}}(\sigma(s))\left(\psi_{s}^{\Delta}\left(\frac{\mu^{\bm{\pi}}(s,\cdot)}{\mu^{\bm{\pi}}(\sigma(s))}\right)-\psi_{s}^{\Delta}\left(\frac{\mu^{\widetilde{\bm{\pi}}}(s,\cdot)}{\mu^{\widetilde{\bm{\pi}}}(\sigma(s))}\right)-\left\langle\nabla\psi_{s}^{\Delta}\left(\frac{\mu^{\widetilde{\bm{\pi}}}(s,\cdot)}{\mu^{\widetilde{\bm{\pi}}}(\sigma(s))}\right),\frac{\mu^{\bm{\pi}}(s,\cdot)}{\mu^{\bm{\pi}}(\sigma(s))}-\frac{\mu^{\widetilde{\bm{\pi}}}(s,\cdot)}{\mu^{\widetilde{\bm{\pi}}}(\sigma(s))}\right\rangle\right)$ $\displaystyle=$ $\displaystyle\sum_{s\in{\mathcal{S}}}\mu^{\bm{\pi}}(\sigma(s))\left(\psi_{s}^{\Delta}\left(\pi_{p(s)}(\cdot{\,|\,}s)\right)-\psi_{s}^{\Delta}\left(\widetilde{\pi}_{p(s)}(\cdot{\,|\,}s)\right)-\left\langle\nabla\psi_{s}^{\Delta}\left(\widetilde{\pi}_{p(s)}(\cdot{\,|\,}s)\right),\pi_{p(s)}(\cdot{\,|\,}s)-\widetilde{\pi}_{p(s)}(\cdot{\,|\,}s)\right\rangle\right)$ $\displaystyle=$ $\displaystyle\sum_{s\in{\mathcal{S}}}\mu^{\bm{\pi}}(\sigma(s))D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\widetilde{\pi}_{p(s)}(\cdot{\,|\,}s)).$ ∎ $$

### D.2 Proof of Lemma D.2

Firstly, we introduce the following lemma.

###### Lemma D.4 .

Let $\mathcal{C}$ be a convex set and $\bm{x}^{(1)}=\mathop{\mathrm{argmin}}_{\bm{x}\in\mathcal{C}}\left\{\left\langle\bm{g},\bm{x}\right\rangle+\tau_{0}\psi^{\mathcal{C}}(\bm{x})+\frac{1}{\eta}D_{\psi^{\mathcal{C}}}(\bm{x},\bm{x}^{(0)})\right\}$, where $\psi^{\mathcal{C}}$ is a strongly-convex function in $\mathcal{C}$ and $\tau_{0}\geq 0$ is a constant. Then, for any $\bm{x}^{(2)}\in\mathcal{C}$, we have

$$ $\displaystyle\eta\tau_{0}\psi^{\mathcal{C}}(\bm{x}^{(1)})-\eta\tau_{0}\psi^{\mathcal{C}}(\bm{x}^{(2)})+\eta\left\langle\bm{g},\bm{x}^{(1)}-\bm{x}^{(2)}\right\rangle$ (D.10) $\displaystyle\leq$ $\displaystyle D_{\psi^{\mathcal{C}}}(\bm{x}^{(2)},\bm{x}^{(0)})-(1+\eta\tau_{0})D_{\psi^{\mathcal{C}}}(\bm{x}^{(2)},\bm{x}^{(1)})-D_{\psi^{\mathcal{C}}}(\bm{x}^{(1)},\bm{x}^{(0)}).$ $$

The proof is postponed to the end of this section.

Plug $\bm{x}^{(0)}=\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s),\bm{x}^{(1)}=\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s),\bm{x}^{(2)}=\pi_{p(s)}(\cdot{\,|\,}s),\bm{g}=-q^{(t)}(s,\cdot),\psi^{\mathcal{C}}=\psi_{s}^{\Delta},\eta=\eta_{s},\tau_{0}=\frac{\tau\mu_{-p(s)}^{(t)}(s)}{m^{(t)}_{s}}$ into Lemma [D.4](#A4.Thmtheorem4), with $\mathcal{C}=\Delta^{|\mathcal{A}_{s}|}_{\gamma_{s},\bm{\nu}_{s}}$,

$$ $\displaystyle\eta_{s}\frac{\tau\mu_{-p(s)}^{(t)}(s)}{m^{(t)}_{s}}\psi_{s}^{\Delta}(\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s))-\eta_{s}\frac{\tau\mu_{-p(s)}^{(t)}(s)}{m^{(t)}_{s}}\psi_{s}^{\Delta}(\pi_{p(s)}(\cdot{\,|\,}s))+\eta_{s}\langle\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s)-\pi_{p(s)}(\cdot{\,|\,}s),-q^{(t)}(s,\cdot)\rangle$ $\displaystyle\leq$ $\displaystyle D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s))-\left(1+\eta_{s}\frac{\tau\mu_{-p(s)}^{(t)}(s)}{m^{(t)}_{s}}\right)D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s))-D_{\psi_{s}^{\Delta}}(\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s)).$ $$

Plug $\bm{x}^{(0)}=\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s),\bm{x}^{(1)}=\pi^{(t)}_{p(s)}(\cdot{\,|\,}s),\bm{x}^{(2)}=\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s),\bm{g}=-q^{(t-1)}(s,\cdot),\psi^{\mathcal{C}}=\psi_{s}^{\Delta},\eta=\eta_{s},\tau_{0}=\frac{\tau\mu_{-p(s)}^{(t-1)}(s)}{m^{(t-1)}_{s}}$ into Lemma [D.4](#A4.Thmtheorem4), with $\mathcal{C}=\Delta^{|\mathcal{A}_{s}|}_{\gamma_{s},\bm{\nu}_{s}}$,

$$ $\displaystyle\eta_{s}\frac{\tau\mu_{-p(s)}^{(t-1)}(s)}{m^{(t-1)}_{s}}\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\eta_{s}\frac{\tau\mu_{-p(s)}^{(t-1)}(s)}{m^{(t-1)}_{s}}\psi_{s}^{\Delta}(\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s))+\eta_{s}\langle\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s),-q^{(t-1)}(s,\cdot)\rangle$ $\displaystyle\leq$ $\displaystyle D_{\psi_{s}^{\Delta}}(\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s))-(1+\eta_{s}\frac{\tau\mu_{-p(s)}^{(t-1)}(s)}{m^{(t-1)}_{s}})D_{\psi_{s}^{\Delta}}(\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-D_{\psi_{s}^{\Delta}}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s)).$ $$

Summing them up and adding $\eta_{s}\left\langle q^{(t-1)}(s,\cdot)-q^{(t)}(s,\cdot),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s)\right\rangle$ to both sides, we have

$$ $\displaystyle\eta_{s}\frac{\tau\mu_{-p(s)}^{(t)}(s)}{m^{(t)}_{s}}\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\eta_{s}\frac{\tau\mu_{-p(s)}^{(t)}(s)}{m^{(t)}_{s}}\psi_{s}^{\Delta}(\pi_{p(s)}(\cdot{\,|\,}s))$ (D.11) $\displaystyle+\eta_{s}\tau(\frac{\mu_{-p(s)}^{(t-1)}(s)}{m^{(t-1)}_{s}}-\frac{\mu_{-p(s)}^{(t)}(s)}{m^{(t)}_{s}})(\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\psi_{s}^{\Delta}(\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s)))$ $\displaystyle+\eta_{s}\langle-q^{(t)}(s,\cdot),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\pi_{p(s)}(\cdot{\,|\,}s)\rangle$ $\displaystyle\leq$ $\displaystyle D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s))-(1+\eta_{s}\frac{\tau\mu_{-p(s)}^{(t)}(s)}{m^{(t)}_{s}})D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s))$ $\displaystyle-(1+\eta_{s}\frac{\tau\mu_{-p(s)}^{(t-1)}(s)}{m^{(t-1)}_{s}})D_{\psi_{s}^{\Delta}}(\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))$ $\displaystyle-D_{\psi_{s}^{\Delta}}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s))+\eta_{s}\left\langle q^{(t-1)}(s,\cdot)-q^{(t)}(s,\cdot),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s)\right\rangle.$ ∎ $$

###### Proof of Lemma D.4 .

$$ $\displaystyle D_{\psi^{\mathcal{C}}}(\bm{x}^{(2)},\bm{x}^{(0)})-(1+\eta\tau_{0})D_{\psi^{\mathcal{C}}}(\bm{x}^{(2)},\bm{x}^{(1)})-D_{\psi^{\mathcal{C}}}(\bm{x}^{(1)},\bm{x}^{(0)})$ $\displaystyle=$ $\displaystyle\left(\psi^{\mathcal{C}}(\bm{x}^{(2)})-\psi^{\mathcal{C}}(\bm{x}^{(0)})-\left\langle\nabla\psi^{\mathcal{C}}(\bm{x}^{(0)}),\bm{x}^{(2)}-\bm{x}^{(0)}\right\rangle\right)$ $\displaystyle-(1+\eta\tau_{0})\left(\psi^{\mathcal{C}}(\bm{x}^{(2)})-\psi^{\mathcal{C}}(\bm{x}^{(1)})-\left\langle\nabla\psi^{\mathcal{C}}(\bm{x}^{(1)}),\bm{x}^{(2)}-\bm{x}^{(1)}\right\rangle\right)$ $\displaystyle-\left(\psi^{\mathcal{C}}(\bm{x}^{(1)})-\psi^{\mathcal{C}}(\bm{x}^{(0)})-\left\langle\nabla\psi^{\mathcal{C}}(\bm{x}^{(0)}),\bm{x}^{(1)}-\bm{x}^{(0)}\right\rangle\right)$ $\displaystyle=$ $\displaystyle\eta\tau_{0}\psi^{\mathcal{C}}(\bm{x}^{(1)})-\eta\tau_{0}\psi^{\mathcal{C}}(\bm{x}^{(2)})+\left\langle(1+\eta\tau_{0})\nabla\psi^{\mathcal{C}}(\bm{x}^{(1)})-\nabla\psi^{\mathcal{C}}(\bm{x}^{(0)}),\bm{x}^{(2)}-\bm{x}^{(1)}\right\rangle.$ $$

Since $\bm{x}^{(1)}=\mathop{\mathrm{argmin}}_{\bm{x}\in\mathcal{C}}\left\{\left\langle\bm{g},\bm{x}\right\rangle+\tau_{0}\psi^{\mathcal{C}}(\bm{x})+\frac{1}{\eta}\left(\psi^{\mathcal{C}}(\bm{x})-\psi^{\mathcal{C}}(\bm{x}^{(0)})-\left\langle\nabla\psi^{\mathcal{C}}(\bm{x}^{(0)}),\bm{x}-\bm{x}^{(0)}\right\rangle\right)\right\}$, by first-order optimality, we have,

$$ $\displaystyle\left\langle\eta\bm{g}+(1+\eta\tau_{0})\nabla\psi^{\mathcal{C}}(\bm{x}^{(1)})-\nabla\psi^{\mathcal{C}}(\bm{x}^{(0)}),\bm{x}^{(2)}-\bm{x}^{(1)}\right\rangle\geq 0.$ $$

Therefore,

$$ $\displaystyle D_{\psi^{\mathcal{C}}}(\bm{x}^{(2)},\bm{x}^{(0)})-(1+\eta\tau_{0})D_{\psi^{\mathcal{C}}}(\bm{x}^{(2)},\bm{x}^{(1)})-D_{\psi^{\mathcal{C}}}(\bm{x}^{(1)},\bm{x}^{(0)})$ $\displaystyle\geq$ $\displaystyle\eta\tau_{0}\psi^{\mathcal{C}}(\bm{x}^{(1)})-\eta\tau_{0}\psi^{\mathcal{C}}(\bm{x}^{(2)})+\eta\left\langle\bm{g},\bm{x}^{(1)}-\bm{x}^{(2)}\right\rangle.\qed$ $$

###### Lemma D.4 .

###### Proof of Lemma D.4 .

## Appendix E Proof of Theorem 4.1

###### Theorem E.1 (Formal Version of Theorem 4.1 ) .

Consider [Algorithm 1](#alg1). When $\frac{\eta_{s}^{\rm anc}}{\eta_{s}}\leq\tau C_{s}^{\eta,T}$ for any $s\in{\mathcal{S}}$, where $C_{s}^{\eta,T}\coloneqq\frac{\gamma^{2}\sum_{h\in s}\mu_{c}(h)}{2C_{s}^{-}\left(\log T+\log|{\mathcal{S}}|+\log\frac{1}{\delta}\right)}$, and [A](#A2.I1.i1), [B](#A2.I1.i2), [C](#A2.I1.i3) are satisfied, we have the following guarantee with probability $1-2\delta$.

$$ $\displaystyle\sum_{t=2}^{T}D_{\psi^{\Pi}}(\bm{\mu}^{(\tau,\gamma),*},\bm{\mu}^{\mkern 1.5mu\overline{\mkern-1.5mu\bm{\pi}\mkern-1.5mu}\mkern 1.5mu^{(t)}})$ $\displaystyle\leq$ $\displaystyle\frac{4C_{\rm visit}}{\tau}\sum_{s\in{\mathcal{S}}}C_{s}^{\mathrm{diff}}\mu^{(\tau,\gamma),*}(\sigma(s))\left\|\bm{q}\right\|_{\infty}\eta_{s}M_{2}T+\frac{2C_{\rm visit}}{\tau}\sum_{s\in{\mathcal{S}}}\frac{1}{\eta_{s}\mu_{p(s)}^{(t_{s}^{1})}(\sigma(s))}\mu^{(\tau,\gamma),*}(\sigma(s))\max_{\bm{x},\bm{y}\in\Delta_{\gamma_{s},\bm{\nu}_{s}}^{|\mathcal{A}_{s}|}}D_{\psi_{s}^{\Delta}}(\bm{x},\bm{y})$ $\displaystyle+\frac{4C_{\rm visit}^{2}}{\tau}\sum_{s\in{\mathcal{S}}}\frac{1}{\eta_{s}}\mu^{(\tau,\gamma),*}(\sigma(s))\max_{\bm{x},\bm{y}\in\Delta_{\gamma_{s},\bm{\nu}_{s}}^{|\mathcal{A}_{s}|}}D_{\psi_{s}^{\Delta}}(\bm{x},\bm{y})$ (E.1) $\displaystyle+\frac{4C_{\rm visit}}{\tau}\left(1+\frac{1}{\gamma}\right)\left(\left\|\bm{q}\right\|_{\infty}+\tau\psi^{\max}\right)\sqrt{2T\log\frac{|{\mathcal{S}}|}{\delta}}+\sum_{s\in{\mathcal{S}}}\frac{4C_{\rm visit}^{2}}{\eta_{s}\tau}\max_{\bm{x},\bm{y}\in\Delta_{\gamma_{s},\bm{\nu}_{s}}^{|\mathcal{A}_{s}|}}D_{\psi_{s}^{\Delta}}(\bm{x},\bm{y}),$ $$

where $C_{\rm visit}\coloneqq\frac{\log T+\log|{\mathcal{S}}|+\log\frac{1}{\delta}}{\gamma^{2}\min_{s\in{\mathcal{S}}}\sum_{h\in s}\mu_{c}(h)}$ is the maximum gap between any two adjacent visits to an infoset.

For any infoset $s\in{\mathcal{S}}$, we define $T_{s}\coloneqq\left\{t_{s}^{1},t_{s}^{2},...\right\}$, where each $t_{s}^{k}\in[T]$ is the timestep that $s$ is along the sampled trajectory. Then, we will show [Algorithm 1](#alg1) uses unbiased estimators so that we can derive an upper-bound by [Lemma 5.3](#S5.Thmtheorem3). Note that for any $\bm{u}\in\Delta^{|\mathcal{A}_{s}|}_{\gamma_{s},\bm{\nu}_{s}}$, the expectation of the additional regularizer term is,

$$ $\displaystyle\Pr\left(t\in T_{s}\right)\left(\frac{\tau}{\mu_{p(s)}^{(t)}(\sigma(s))}\psi_{s}^{\Delta}(\bm{u})\right)=$ $\displaystyle\mu_{p(s)}^{(t)}(\sigma(s))\mu_{-p(s)}^{(t)}(s)\left(\frac{\tau}{\mu_{p(s)}^{(t)}(\sigma(s))}\psi_{s}^{\Delta}(\bm{u})\right)=\tau\mu_{-p(s)}^{(t)}(s)\psi_{s}^{\Delta}(\bm{u}).$ $$

Let $s(h)$ denote the infoset that the node $h$ is in. For the original utility, suppose $p(s)=1$ without loss of generality, the expectation of $\widetilde{q}^{(t)}(s,a)$ for any $a\in\mathcal{A}_{s}$ is,

$$ $\displaystyle\frac{1}{\pi^{(t)}_{1}(a{\,|\,}s)}\sum_{h^{\prime}\in\mathcal{H}\colon\exists h\in s,(h,a)\sqsubseteq h^{\prime}}\mu_{1}^{(t)}(\sigma_{1}(h^{\prime}))\mu_{2}^{(t)}(\sigma_{2}(h^{\prime}))\mu_{c}(h^{\prime})\mathcal{U}_{1}(h^{\prime})$ $\displaystyle-\frac{1}{\pi^{(t)}_{1}(a{\,|\,}s)}\sum_{h^{\prime}\in\mathcal{H}_{1}\colon\exists h\in s,(h,a)\sqsubseteq h^{\prime}}\mu_{1}^{(t)}(\sigma_{1}(h^{\prime}))\mu_{2}^{(t)}(\sigma_{2}(h^{\prime}))\mu_{c}(h^{\prime})\psi^{\Delta}_{s(h)}(\pi_{1}^{(t)})$ $\displaystyle+\frac{1}{\pi^{(t)}_{1}(a{\,|\,}s)}\sum_{h^{\prime}\in\mathcal{H}_{2}\colon\exists h\in s,(h,a)\sqsubseteq h^{\prime}}\mu_{1}^{(t)}(\sigma_{1}(h^{\prime}))\mu_{2}^{(t)}(\sigma_{2}(h^{\prime}))\mu_{c}(h^{\prime})\psi^{\Delta}_{s(h)}(\pi_{2}^{(t)}),$ $$

which is equal to $q^{(t)}(s,a)$ by definition.

By Lemma [5.3](#S5.Thmtheorem3) and union bound, with probability at least $1-\delta$, the following is satisfied for all infosets $s\in{\mathcal{S}}$,

$$ $\displaystyle\sum_{t=1}^{T}\left(\tau\mu_{-p(s)}^{(t)}(s)\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\tau\mu_{-p(s)}^{(t)}(s)\psi_{s}^{\Delta}(\pi_{p(s)}(\cdot{\,|\,}s))+\frac{1}{\mu_{p(s)}^{(t)}(\sigma(s))}\langle-q^{(t)}(s,\cdot),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\pi_{p(s)}(\cdot{\,|\,}s)\rangle\right)$ $\displaystyle\leq$ $\displaystyle\sum_{t\in T_{s}}\left(\frac{\tau}{\mu_{p(s)}^{(t)}(\sigma(s))}\left(\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\psi_{s}^{\Delta}(\pi_{p(s)}(\cdot{\,|\,}s))\right)+\frac{1}{\mu_{p(s)}^{(t)}(\sigma(s))}\langle-\widetilde{q}^{(t)}(s,\cdot),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\pi_{p(s)}(\cdot{\,|\,}s)\rangle\right)$ $\displaystyle+2\left(1+\frac{1}{\gamma}\right)\left(\left\|\bm{q}\right\|_{\infty}+\tau\psi^{\max}\right)\sqrt{2T\log\frac{|{\mathcal{S}}|}{\delta}},$ $$

where $\psi^{\max}$ is the upperbound of $\psi_{s}^{\Delta}$, which is $\max_{s\in{\mathcal{S}}}\frac{\alpha_{s}}{2}$ when it is Euclidean norm and $\max_{s\in{\mathcal{S}}}\alpha_{s}\log|\mathcal{A}_{s}|$ when it is entropy.

Let’s define $t_{s}^{0}=1$ for notational simplicity. Similar to the proof of [Theorem 5.2](#S5.Thmtheorem2), for each $k\leq|T_{s}|-1$, we have

$$ $\displaystyle\eta_{s}\tau\psi_{s}^{\Delta}(\pi^{(t_{s}^{k})}_{p(s)}(\cdot{\,|\,}s))-\eta_{s}\tau\psi_{s}^{\Delta}(\pi_{p(s)}(\cdot{\,|\,}s))+\eta_{s}\left\langle-\widetilde{q}^{(t_{s}^{k})}(s,\cdot),\pi^{(t_{s}^{k})}_{p(s)}(\cdot{\,|\,}s)-\pi_{p(s)}(\cdot{\,|\,}s)\right\rangle$ $\displaystyle\leq$ $\displaystyle D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t_{s}^{k})}_{p(s)}(\cdot{\,|\,}s))-(1+\eta_{s}\tau)D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t_{s}^{k+1})}_{p(s)}(\cdot{\,|\,}s))$ $\displaystyle-(1+\eta_{s}\tau)D_{\psi_{s}^{\Delta}}(\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t_{s}^{k+1})}_{p(s)}(\cdot{\,|\,}s),\pi^{(t_{s}^{k})}_{p(s)}(\cdot{\,|\,}s))$ $\displaystyle+\eta_{s}\left\langle\widetilde{q}^{(t_{s}^{k-1})}(s,\cdot)-\widetilde{q}^{(t_{s}^{k})}(s,\cdot),\pi^{(t_{s}^{k})}_{p(s)}(\cdot{\,|\,}s)-\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t_{s}^{k+1})}_{p(s)}(\cdot{\,|\,}s)\right\rangle.$ $$

By multiplying $m_{s}^{(t_{s}^{k})}=\frac{1}{\mu_{p(s)}^{(t_{s}^{k})}(\sigma(s))}$ on both sides and telescoping, we have

$$ $\displaystyle\sum_{k=1}^{|T_{s}|-1}\left(\frac{\tau}{\mu_{p(s)}^{(t_{s}^{k})}(\sigma(s))}\left(\psi_{s}^{\Delta}(\pi^{(t_{s}^{k})}_{p(s)}(\cdot{\,|\,}s))-\psi_{s}^{\Delta}(\pi_{p(s)}(\cdot{\,|\,}s))\right)+\frac{1}{\mu_{p(s)}^{(t_{s}^{k})}(\sigma(s))}\langle-\widetilde{q}^{(t_{s}^{k})}(s,\cdot),\pi^{(t_{s}^{k})}_{p(s)}(\cdot{\,|\,}s)-\pi_{p(s)}(\cdot{\,|\,}s)\rangle\right)$ $\displaystyle\leq$ $\displaystyle\sum_{k=2}^{|T_{s}|}\left(\frac{1}{\mu_{p(s)}^{(t_{s}^{k})}(\sigma(s))}-\frac{1}{\mu_{p(s)}^{(t_{s}^{k-1})}(\sigma(s))}-\frac{\eta_{s}\tau}{\mu_{p(s)}^{(t_{s}^{k-1})}(\sigma(s))}\right)D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t_{s}^{k})}_{p(s)}(\cdot{\,|\,}s))$ $\displaystyle+2C_{s}^{\mathrm{diff}}\left\|\bm{q}\right\|_{\infty}\eta_{s}M_{2}|T_{s}|+\frac{1}{\mu_{p(s)}^{(t_{s}^{1})}(\sigma(s))}D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t_{s}^{1})}_{p(s)}(\cdot{\,|\,}s)).$ $$

Since the probability of visiting infoset $s$ at timestep $t$ is at least $\gamma^{2}\sum_{h\in s}\mu_{c}(h)$,

$$ $\displaystyle\Pr\left(|t_{s}^{k}-t_{s}^{k-1}|>K_{s}\right)\leq(1-\gamma^{2}\sum_{h\in s}\mu_{c}(h))^{K_{s}}\leq\exp(-\gamma^{2}\sum_{h\in s}\mu_{c}(h)K_{s}).$ $$

Therefore, with probability $1-\delta$, all infosets $s\in{\mathcal{S}}$ satisfies that for any $2\leq k\leq|T_{s}|$, $|t_{s}^{k}-t_{s}^{k-1}|\leq\frac{\log T+\log|{\mathcal{S}}|+\log\frac{1}{\delta}}{\gamma^{2}\sum_{h\in s}\mu_{c}(h)}\eqqcolon K_{s}$. Then,

$$ $\displaystyle\frac{1}{\mu_{p(s)}^{(t_{s}^{k})}(\sigma(s))}-\frac{1}{\mu_{p(s)}^{(t_{s}^{k-1})}(\sigma(s))}-\frac{\eta_{s}\tau}{\mu_{p(s)}^{(t_{s}^{k-1})}(\sigma(s))}\leq$ $\displaystyle C_{s}^{-}\eta_{s}^{\rm anc}\frac{\log T+\log|{\mathcal{S}}|+\log\frac{1}{\delta}}{\gamma^{2}\sum_{h\in s}\mu_{c}(h)}-\eta_{s}\tau$ $\displaystyle=$ $\displaystyle C_{s}^{-}\eta_{s}^{\rm anc}\frac{\log T+\log|{\mathcal{S}}|+\log\frac{1}{\delta}}{\gamma^{2}\sum_{h\in s}\mu_{c}(h)}-\eta_{s}\tau.$ $$

Therefore, when $\frac{\eta_{s}^{\rm anc}}{\eta_{s}}\leq\frac{\tau\gamma^{2}\sum_{h\in s}\mu_{c}(h)}{2C_{s}^{-}\left(\log T+\log|{\mathcal{S}}|+\log\frac{1}{\delta}\right)}$, the inequality above is upper-bounded by $-\frac{\eta_{s}\tau}{2}$. Moreover, we can write it as (let $t_{s}^{|T_{s}|+1}=T+1$ for notational simplicity),

$$ $\displaystyle\sum_{k=2}^{|T_{s}|}\left(\frac{1}{\mu_{p(s)}^{(t_{s}^{k})}(\sigma(s))}-\frac{1}{\mu_{p(s)}^{(t_{s}^{k-1})}(\sigma(s))}-\frac{\eta_{s}\tau}{\mu_{p(s)}^{(t_{s}^{k-1})}(\sigma(s))}\right)D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t_{s}^{k})}_{p(s)}(\cdot{\,|\,}s))$ $\displaystyle\leq$ $\displaystyle-\sum_{k=2}^{|T_{s}|}\sum_{t=t_{s}^{(k)}}^{t_{s}^{(k+1)}-1}\frac{\eta_{s}\tau}{2K_{s}}D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t_{s}^{k})}_{p(s)}(\cdot{\,|\,}s))$ $\displaystyle=$ $\displaystyle-\frac{\eta_{s}\tau\gamma^{2}\sum_{h\in s}\mu_{c}(h)}{2\left(\log T+\log|{\mathcal{S}}|+\log\frac{1}{\delta}\right)}\sum_{k=2}^{|T_{s}|}\sum_{t=t_{s}^{(k)}}^{t_{s}^{(k+1)}-1}D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t_{s}^{k})}_{p(s)}(\cdot{\,|\,}s))$ $\displaystyle\overset{(i)}{=}$ $\displaystyle-\frac{\eta_{s}\tau\gamma^{2}\sum_{h\in s}\mu_{c}(h)}{2\left(\log T+\log|{\mathcal{S}}|+\log\frac{1}{\delta}\right)}\sum_{t=t_{s}^{(2)}}^{T}D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s))$ $\displaystyle\leq$ $\displaystyle-\frac{\eta_{s}\tau\gamma^{2}\sum_{h\in s}\mu_{c}(h)}{2\left(\log T+\log|{\mathcal{S}}|+\log\frac{1}{\delta}\right)}\sum_{t=2}^{T}D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s))+2K_{s}\max_{\bm{x},\bm{y}\in\Delta_{\gamma_{s},\bm{\nu}_{s}}^{|\mathcal{A}_{s}|}}D_{\psi_{s}^{\Delta}}(\bm{x},\bm{y}).$ $$

$(i)$ uses the fact that for any $t\in[t_{s}^{k},t_{s}^{k+1}-1]$, $\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu_{p(s)}^{(t)}(\cdot{\,|\,}s)=\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu_{p(s)}^{(t_{s}^{k})}(\cdot{\,|\,}s)$.

Then, following rest of the proof for [Theorem 5.2](#S5.Thmtheorem2), we finish the proof. ∎

###### Theorem E.1 (Formal Version of Theorem 4.1 ) .

### E.1 Proof of Lemma 5.3

Let $d^{(t)}(\bm{u})\coloneqq\left(f^{(t)}(\bm{u})-f^{(t)}(\bm{u}^{(t)})\right)-\left(\widetilde{f}^{(t)}(\bm{u})-\widetilde{f}^{(t)}(\bm{u}^{(t)})\right)$. By the property of $f^{(t)}$, since $\bm{u}^{(t)}$ is deterministically influenced by $\widetilde{f}^{(1)},\widetilde{f}^{(2)},...,\widetilde{f}^{(t-1)}$, $\mathbb{E}\left[\widetilde{f}^{(t)}(\bm{u}^{(t)}){\,|\,}\widetilde{f}^{(1)},\widetilde{f}^{(2)},...,\widetilde{f}^{(t-1)}\right]=f^{(t)}(\bm{u}^{(t)})$. Moreover, $\mathbb{E}\Big{[}\widetilde{f}^{(t)}(\bm{u})\allowbreak{\,|\,}\widetilde{f}^{(1)},\widetilde{f}^{(2)},...,\widetilde{f}^{(t-1)}\Big{]}=f^{(t)}(\bm{u})$ for any fixed $\bm{u}\in\mathcal{C}$. Therefore, $d^{(t)}(\bm{u})$ is a martingale difference sequence. Then, we can apply the Azuma-Hoeffding inequality in the following.

###### Lemma E.2 (Azuma-Hoeffding inequality) .

For any martingale difference sequence $x^{(1)},x^{(2)},...,x^{(T)}$ with $x^{(t)}\in[a^{(t)},b^{(t)}]$, we have

$$ $\displaystyle\Pr\left(\sum_{t=1}^{T}x^{(t)}\geq w\right)\leq\exp\left(-\frac{2w^{2}}{\sum_{t=1}^{T}\left(b^{(t)}-a^{(t)}\right)^{2}}\right).$ $$

Note that $\left|d^{(t)}(\bm{u})\right|\leq M+\widetilde{M}$. By applying [Lemma E.2](#A5.Thmtheorem2), we have

$$ $\displaystyle\Pr\left(\sum_{t=1}^{T}d^{(t)}(\bm{u})\geq w\right)\leq\exp\left(-\frac{2w^{2}}{\sum_{t=1}^{T}4(M+\widetilde{M})^{2}}\right).$ $$

Therefore, when taking $w=(M+\widetilde{M})\sqrt{2T\log\frac{1}{\delta}}$, with probability at least $1-\delta$,

$$ $\displaystyle\sum_{t=1}^{T}\left(f^{(t)}(\bm{u})-f^{(t)}(\bm{u}^{(t)})\right)\leq\sum_{t=1}^{T}\left(\widetilde{f}^{(t)}(\bm{u})-\widetilde{f}^{(t)}(\bm{u}^{(t)})\right)+(M+\widetilde{M})\sqrt{2T\log\frac{1}{\delta}}.$ ∎ $$

###### Lemma E.2 (Azuma-Hoeffding inequality) .

## Appendix F Auxiliary Lemmas

In this section, we present the auxiliary lemmas for the theorems proved in the previous part.

### F.1 Upperbound of Feedback

###### Lemma F.1 (Upperbound of Feedback $q^{(t)}(s,\cdot)$ ) .

Consider the update-rule Eq ([5.2](#S5.E2)). For any timestep $t\in[T]$, we have the following upper-bound on $q^{(t)}(s,\cdot)$ and its unbiased estimator $\widetilde{q}^{(t)}(s,\cdot)$, no matter whether it is counterfactual value, trajectory Q-value, or Q-value.

$$ $\displaystyle\left\|\bm{q}\right\|_{\infty}:=\begin{cases}\frac{\frac{\tau}{M_{1}}\left\|\bm{\alpha}\right\|_{\infty}\mathcal{D}\psi^{\max}+1}{\min_{s\in{\mathcal{S}},a\in\mathcal{A}_{s}}\gamma_{s}\nu_{s,a}}&\text{Outcome Sampling of Trajectory Q-value}\\ \frac{\tau}{M_{1}}\left\|\bm{\alpha}\right\|_{\infty}\mathcal{D}\psi^{\max}+1&\text{Otherwise}\end{cases}$ (F.1) $$

where $\mathcal{D}:=\max_{s\in{\mathcal{S}}}\mathcal{D}(s)$ is the maximum depth of infoset and $\psi^{\max}$ is the maximum of the regularizer, which is $\frac{1}{2\min_{s\in{\mathcal{S}}}|\mathcal{A}_{s}|}$ for Euclidean distance and $\max_{s\in{\mathcal{S}}}\log|\mathcal{A}_{s}|$ for entropy.

###### Proof.

When calculating the feedback $\widetilde{q}^{(t)}(s,a)$ for outcome sampling of trajectory Q-value, we need to divide the probability of choosing action $a$, which is $\pi^{(t)}(a{\,|\,}s)\geq\min_{s\in{\mathcal{S}},a\in\mathcal{A}_{s}}\gamma_{s}\nu_{s,a}$. Then, its upperbound is that of the full-information feedback setting divided by the constant $\min_{s\in{\mathcal{S}},a\in\mathcal{A}_{s}}\gamma_{s}\nu_{s,a}$. Therefore, in the following, we will focus on the upperbound of $q^{(t)}(s,\cdot)$ in the full-information feedback setting.

In the following proof, we only consider $s\in{\mathcal{S}}_{1}$ since player $1,2$ are symmetric. Furthermore, we only need to prove the upper-bound above when $q^{(t)}(s,\cdot)$ is Q-value, since by definition, the Q-value $Q_{i}^{\bm{\pi}}(s,a)=\frac{\mkern 1.5mu\overline{\mkern-1.5muQ\mkern-1.5mu}\mkern 1.5mu_{i}^{\bm{\pi}}(s,a)}{\sum_{h\in s}\mu_{c}(h)\mu_{1}^{\pi_{1}}(\sigma_{1}(h))\mu_{2}^{\pi_{2}}(\sigma_{2}(h))}\geq\mkern 1.5mu\overline{\mkern-1.5muQ\mkern-1.5mu}\mkern 1.5mu_{i}^{\bm{\pi}}(s,a)$ (similarly, it is also larger than the counterfactual value).

Let $s(h)$ be the infoset that node $h$ is in. Firstly, when $\tau=0$, which means only considering the contribution of $\mathcal{U}_{1}$ to $q^{(t)}(s,\cdot)$, for every $s\in{\mathcal{S}}_{1}$, we have

$$ $\displaystyle\left|Q_{i}^{\bm{\pi}}(s,a)\right|=$ $\displaystyle\frac{1}{\sum_{h\in s}\mu_{c}(h)\mu_{1}^{\pi_{1}}(\sigma_{1}(h))\mu_{2}^{\pi_{2}}(\sigma_{2}(h))}\left|\sum_{h^{\prime}\colon\exists h\in s,(h,a)\sqsubseteq h^{\prime}}\mu_{c}(h^{\prime})\mathcal{U}_{1}(h^{\prime})\mu_{1}^{\pi_{1}}(\sigma_{1}(h^{\prime}))\mu_{2}^{\pi_{2}}(\sigma_{2}(h^{\prime}))\right|$ $\displaystyle\overset{(i)}{=}$ $\displaystyle\frac{1}{\sum_{h\in s}\mu_{c}(h)\mu_{1}^{\pi_{1}}(\sigma_{1}(h))\mu_{2}^{\pi_{2}}(\sigma_{2}(h))}\left|\sum_{h^{\prime}\colon\exists h\in s,(h,a)\sqsubseteq h^{\prime},\mathcal{A}_{s(h^{\prime})}=\emptyset}\mu_{c}(h^{\prime})\mathcal{U}_{1}(h^{\prime})\mu_{1}^{\pi_{1}}(\sigma_{1}(h^{\prime}))\mu_{2}^{\pi_{2}}(\sigma_{2}(h^{\prime}))\right|$ $\displaystyle\leq$ $\displaystyle\frac{1}{\sum_{h\in s}\mu_{c}(h)\mu_{1}^{\pi_{1}}(\sigma_{1}(h))\mu_{2}^{\pi_{2}}(\sigma_{2}(h))}\sum_{h^{\prime}\colon\exists h\in s,(h,a)\sqsubseteq h^{\prime},\mathcal{A}_{s(h^{\prime})}=\emptyset}\mu_{c}(h^{\prime})\mu_{1}^{\pi_{1}}(\sigma_{1}(h^{\prime}))\mu_{2}^{\pi_{2}}(\sigma_{2}(h^{\prime}))$ $\displaystyle\overset{(ii)}{=}$ $\displaystyle\frac{1}{\sum_{h\in s}\mu_{c}(h)\mu_{1}^{\pi_{1}}(\sigma_{1}(h))\mu_{2}^{\pi_{2}}(\sigma_{2}(h))}\sum_{h\in s}\mu_{c}(h)\mu_{1}^{\pi_{1}}(\sigma_{1}(h))\mu_{2}^{\pi_{2}}(\sigma_{2}(h))=1.$ $$

$(i)$ is because $\mathcal{U}_{1}(h)\not=0$ only if $h$ is a terminal node. $(ii)$ is by the tree structure of EFG. Now consider $\tau>0$ and $\mathcal{U}_{1}(h)\equiv 0$ for any $h\in\mathcal{H}$. Moreover, we will only show the upperbound when using dilated regularizer, since bidilated regularizer is upperbounded by the dilated one.

Let $S^{(t)}(s)=\left\langle q^{(t)}(s,\cdot),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)\right\rangle-\frac{\tau}{m^{(t)}_{s}}\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))$ when $\mathcal{A}_{s}\not=\emptyset$ ($s$ is not terminal node) and $S^{(t)}(s)=0$ when $\mathcal{A}_{s}=\emptyset$ ($s$ is the terminal node).

We will prove $\left|S^{(t)}(s)\right|\leq\frac{\tau}{M_{1}}\left\|\bm{\alpha}\right\|_{\infty}\left(\mathcal{D}-\mathcal{D}(s)\right)\psi^{\max}$ by induction. For infoset $s\in{\mathcal{S}}_{1}$ with $\mathcal{D}(s)=D$, we have $S^{(t)}(s)=0=\tau\left\|\bm{\alpha}\right\|_{\infty}\left(\mathcal{D}-\mathcal{D}(s)\right)\psi^{\max}$. Therefore, the initial step of induction is completed.

Consider when all $s^{\prime}\in{\mathcal{S}}_{1}$ with $\mathcal{D}(s^{\prime})>d$ for some constant $d$, $S^{(t)}(s^{\prime})\leq\frac{\tau}{M_{1}}\left\|\bm{\alpha}\right\|_{\infty}\left(\mathcal{D}-\mathcal{D}(s^{\prime})\right)\psi^{\max}$. Let $\Pr(h\to h^{\prime})$ be the probability of reaching $h^{\prime}$ from node $h$, when considering all nodes encountered along the path (player $1,2$ action node and the chance node) for notational simplicity. Then, for infoset $s\in{\mathcal{S}}_{1}$ with $\mathcal{D}(s)=d$, we have

$$ $\displaystyle\left|Q_{i}^{\bm{\pi}}(s,a)\right|=$ $\displaystyle\left|\sum_{s^{\prime}\in{\mathcal{S}}_{1}\colon\sigma(s^{\prime})=(s,a)}S^{(t)}(s^{\prime})\sum_{h\in s}\frac{\mu_{c}(h)\mu_{1}^{\pi_{1}}(\sigma_{1}(h))\mu_{2}^{\pi_{2}}(\sigma_{2}(h))}{\sum_{h^{\prime}\in s}\mu_{c}(h^{\prime})\mu_{1}^{\pi_{1}}(\sigma_{1}(h^{\prime}))\mu_{2}^{\pi_{2}}(\sigma_{2}(h^{\prime}))}\sum_{h^{\prime}\in s^{\prime}}\Pr(h\to h^{\prime})\right|$ $\displaystyle\leq$ $\displaystyle\sum_{s^{\prime}\in{\mathcal{S}}_{1}\colon\sigma(s^{\prime})=(s,a)}\frac{\tau}{M_{1}}\left\|\bm{\alpha}\right\|_{\infty}\left(\mathcal{D}-\mathcal{D}(s)-1\right)\psi^{\max}$ $\displaystyle\cdot\sum_{h\in s}\frac{\mu_{c}(h)\mu_{1}^{\pi_{1}}(\sigma_{1}(h))\mu_{2}^{\pi_{2}}(\sigma_{2}(h))}{\sum_{h^{\prime}\in s}\mu_{c}(h^{\prime})\mu_{1}^{\pi_{1}}(\sigma_{1}(h^{\prime}))\mu_{2}^{\pi_{2}}(\sigma_{2}(h^{\prime}))}\sum_{h^{\prime}\in s^{\prime}}\Pr(h\to h^{\prime})$ $\displaystyle=$ $\displaystyle\frac{\tau}{M_{1}}\left\|\bm{\alpha}\right\|_{\infty}\left(\mathcal{D}-\mathcal{D}(s)-1\right)\psi^{\max}$ $\displaystyle\cdot\sum_{h\in s}\frac{\mu_{c}(h)\mu_{1}^{\pi_{1}}(\sigma_{1}(h))\mu_{2}^{\pi_{2}}(\sigma_{2}(h))}{\sum_{h^{\prime}\in s}\mu_{c}(h^{\prime})\mu_{1}^{\pi_{1}}(\sigma_{1}(h^{\prime}))\mu_{2}^{\pi_{2}}(\sigma_{2}(h^{\prime}))}\sum_{h^{\prime}\in\mathcal{H}_{1}\colon\sigma_{1}(h^{\prime})=(s,a)}\Pr(h\to h^{\prime})$ $\displaystyle=$ $\displaystyle\frac{\tau}{M_{1}}\left\|\bm{\alpha}\right\|_{\infty}\left(\mathcal{D}-\mathcal{D}(s)-1\right)\psi^{\max}.$ $$

Therefore,

$$ $\displaystyle\left|S^{(t)}(s)\right|=\left|\left\langle q^{(t)}(s,\cdot),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)\right\rangle-\frac{\tau}{m^{(t)}_{s}}\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))\right|\leq$ $\displaystyle\frac{\tau}{M_{1}}\left\|\bm{\alpha}\right\|_{\infty}\left(\mathcal{D}-\mathcal{D}(s)-1\right)\psi^{\max}+\frac{\tau}{M_{1}}\left\|\bm{\alpha}\right\|_{\infty}\psi^{\max}$ $\displaystyle=$ $\displaystyle\frac{\tau}{M_{1}}\left\|\bm{\alpha}\right\|_{\infty}\left(\mathcal{D}-\mathcal{D}(s)\right)\psi^{\max}.$ $$

This concludes the induction step.∎

###### Lemma F.1 (Upperbound of Feedback q ( t ) ​ ( s , ⋅ ) superscript 𝑞 𝑡 𝑠 ⋅ q^{(t)}(s,\cdot) ) .

###### Proof.

### F.2 Bounding M 1 , M 2 subscript 𝑀 1 subscript 𝑀 2 M_{1},M_{2}

By choosing $\gamma_{s}$ as a fixed constant $\gamma_{0}>0$ for any player $i\in[2]$ and $s\in{\mathcal{S}}_{i}$. $\nu_{s,a}$ is chosen to be proportional to the number of terminal infosets ($s^{\prime}\in{\mathcal{S}}$ with $\mathcal{A}_{s^{\prime}}=\emptyset$) in the subtree rooted at $(s,a)$, we can get $\gamma\geq\frac{\gamma_{0}^{\mathcal{D}}}{|{\mathcal{S}}|}$. Then, we have the following lowerbound and upperbound on $m^{(t)}_{s}$.

###### Lemma F.2 .

When $\mu_{1}^{(t)},\mu_{2}^{(t)}\succeq\gamma$, $m^{(t)}_{s}$ are lowerbounded by $M_{1}$ and upperbounded by $M_{2}$ with the following $M_{1},M_{2}$ for different feedback.

$$ $\displaystyle M_{1}\coloneqq\begin{cases}\gamma\min_{s\in{\mathcal{S}}}\sum_{h\in s}\mu_{c}(h)&\text{Q-value}\\ 1&\text{Trajectory Q-value}\\ 1&\text{ Counterfactual~{}Value}\end{cases}$ $\displaystyle M_{2}\coloneqq\begin{cases}1&\text{Q-value}\\ \frac{1}{\gamma}&\text{Trajectory Q-value}\\ 1&\text{ Counterfactual Value}\end{cases}$ (F.2) $$

###### Proof.

We only prove the lowerbound and upperbound for infoset $s\in{\mathcal{S}}_{1}$ since two players are symmetric.

For counterfactual value, since $m^{(t)}_{s}\equiv 1$, $M_{1},M_{2}=1$.

For trajectory Q-value, since $m^{(t)}_{s}=\frac{1}{\mu_{1}^{(t)}(\sigma(s))}$, we have $M_{2}=\frac{1}{\gamma}\geq m^{(t)}_{s}\geq 1=M_{1}$.

For Q-value, $m^{(t)}_{s}=\sum_{h\in s}\mu_{c}(h)\mu_{2}^{(t)}(\sigma_{2}(h))$. Since the reach probability $\mu_{1}^{\pi_{1}}(\sigma(s))\sum_{h\in s}\mu_{c}(h)\mu_{2}^{(t)}(\sigma_{2}(h))\leq 1$ for any $\pi_{1}$, we can let $\pi_{1}$ play deterministically to reach $s$. In this way, $m^{(t)}_{s}$ is equal to the reach probability so it is also upperbounded by one. At the same time, $m^{(t)}_{s}\geq\gamma\sum_{h\in s}\mu_{c}(h)\geq\gamma\min_{s\in{\mathcal{S}}}\sum_{h\in s}\mu_{c}(h)$.∎

###### Lemma F.2 .

###### Proof.

### F.3 Proof of Lemma B.2

###### Lemma F.3 .

Consider update-rule Eq ([5.2](#S5.E2)). When $\psi^{\Delta}_{s}(\bm{u})=\frac{\alpha_{s}}{2}\sum_{a\in\mathcal{A}_{s}}u_{a}^{2}$ is the Euclidean distance where $\alpha_{s}>0$ is a constant, we have

$$ $\displaystyle C_{s}^{\text{diff}}=\frac{|\mathcal{A}_{s}|}{\alpha_{s}}\left\|\bm{q}\right\|_{\infty}+\frac{\tau}{M_{1}}\sqrt{|\mathcal{A}_{s}|}.$ (F.3) $$

Let $\tau_{s}^{(t)}\coloneq\frac{\tau\mu_{-p(s)}^{(t)}(s)}{m_{s}^{(t)}}$. When $\psi^{\Delta}_{s}(\bm{u})=\frac{\alpha_{s}}{2}\sum_{a\in\mathcal{A}_{s}}u_{a}^{2}$, we have

$$ $\displaystyle\left\|\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s)\right\|=$ $\displaystyle\left\|{\rm Proj}_{\Delta^{|\mathcal{A}_{s}|}_{\gamma_{s},\bm{\nu}_{s}}}\left(\frac{\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s)}{1+\eta_{s}\tau_{s}^{(t-1)}}+\frac{\eta_{s}}{\alpha_{s}(1+\eta_{s}\tau_{s}^{(t-1)})}q^{(t-1)}(s,\cdot)\right)-\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s)\right\|$ $\displaystyle\leq$ $\displaystyle\left\|\frac{\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s)}{1+\eta_{s}\tau_{s}^{(t-1)}}+\frac{\eta_{s}}{\alpha_{s}(1+\eta_{s}\tau_{s}^{(t-1)})}q^{(t-1)}(s,\cdot)-\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s)\right\|$ $\displaystyle\leq$ $\displaystyle\eta_{s}\left(\frac{1}{\alpha_{s}(1+\eta_{s}\tau_{s}^{(t-1)})}\left\|q^{(t-1)}(s,\cdot)\right\|+\frac{\tau_{s}^{(t-1)}}{1+\eta_{s}\tau_{s}^{(t-1)}}\left\|\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s)\right\|\right)$ $\displaystyle\leq$ $\displaystyle\eta_{s}\left(\frac{1}{\alpha_{s}}\left\|q^{(t-1)}(s,\cdot)\right\|+\tau_{s}^{(t-1)}\left\|\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s)\right\|\right)$ $\displaystyle\leq$ $\displaystyle\eta_{s}\left(\frac{\sqrt{|\mathcal{A}_{s}|}}{\alpha_{s}}\left\|\bm{q}\right\|_{\infty}+\frac{\tau}{M_{1}}\right).$ $$

In the last line, we use the fact that $\mu_{-p(s)}^{(t)}(s)\leq 1$.

As a result, $\left\|\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s)\right\|_{1}\leq\eta_{s}\left(\frac{|\mathcal{A}_{s}|}{\alpha_{s}}\left\|\bm{q}\right\|_{\infty}+\frac{\tau}{M_{1}}\sqrt{|\mathcal{A}_{s}|}\right)$.

Similarly, $\left\|\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s)-\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s)\right\|_{1}\leq\eta_{s}\left(\frac{|\mathcal{A}_{s}|}{\alpha_{s}}\left\|\bm{q}\right\|_{\infty}+\frac{\tau}{M_{1}}\sqrt{|\mathcal{A}_{s}|}\right)$.
∎

###### Proof of Lemma B.5 .

Let $\tau_{s}^{(t)}\coloneq\frac{\tau\mu_{-p(s)}^{(t)}(s)}{m_{s}^{(t)}}$. When $\psi^{\Delta}_{s}(\bm{u})=\alpha_{s}\left(\log|\mathcal{A}_{s}|+\sum_{a\in\mathcal{A}_{s}}u_{a}\log u_{a}\right)$, the update-rule Eq ([5.2](#S5.E2)) is equivalent to

$$ $\displaystyle\pi^{(t)}(a{\,|\,}s)=$ $\displaystyle\max\left\{\frac{\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}(a{\,|\,}s)^{\frac{1}{1+\eta_{s}\tau_{s}^{(t-1)}}}\exp\left(\frac{\eta_{s}}{\alpha_{s}\left(1+\eta_{s}\tau_{s}^{(t-1)}\right)}q^{(t)}(s,a)\right)}{Z},\gamma_{s}\nu_{s,a}\right\}$ $\displaystyle=$ $\displaystyle\max\left\{\frac{\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}(a{\,|\,}s)\exp\left(\frac{\eta_{s}}{\alpha_{s}\left(1+\eta_{s}\tau_{s}^{(t-1)}\right)}q^{(t)}(s,a)-\frac{\eta_{s}\tau}{m^{(t-1)}_{s}\left(1+\eta_{s}\tau_{s}^{(t-1)}\right)}\log\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}(a{\,|\,}s)\right)}{Z},\gamma_{s}\nu_{s,a}\right\}$ $$

for any $a\in\mathcal{A}_{s}$, where $Z>0$ is a normalizing constant to ensure $\pi^{(t)}(a{\,|\,}s)$ is still a probability distribution over $\Delta^{|\mathcal{A}_{s}|}$. The equivalency is proved in Lemma [F.4](#A6.Thmtheorem4). For notational simplicity, we define $l^{(t)}(s,a):=-\frac{1}{\alpha_{s}\left(1+\eta_{s}\tau_{s}^{(t-1)}\right)}q^{(t)}(s,a)+\frac{\tau}{m^{(t-1)}_{s}\left(1+\eta_{s}\tau_{s}^{(t-1)}\right)}\log\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}(a{\,|\,}s)$ so that $\pi^{(t)}(a{\,|\,}s)=\max\left\{\frac{\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}(a{\,|\,}s)\exp\left(-\eta_{s}l^{(t)}(s,a)\right)}{Z},\gamma_{s}\nu_{s,a}\right\}$.

Firstly, for $\gamma_{s}=1$, we have $\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)=\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s)=\bm{\nu}_{s}$. Therefore, $C_{s}^{\text{diff}}=0$ and $\frac{\pi^{(t)}(a{\,|\,}s)}{\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}(a{\,|\,}s)}=1$ for any $a\in\mathcal{A}_{s}$. In the following, we assume $\gamma_{s}<1$.

We can see that $\pi^{(t)}(a{\,|\,}s)$ is monotonically decreasing with respect to $Z$. When $Z<\exp\left(-\eta_{s}\max_{a^{\prime}\in\mathcal{A}_{s}}l^{(t)}(s,a^{\prime})\right)$, for any $a\in\mathcal{A}_{s}$, we have $\pi^{(t)}(a{\,|\,}s)\geq\frac{\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}(a{\,|\,}s)\exp\left(-\eta_{s}l^{(t)}(s,a)\right)}{Z}>\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}(a{\,|\,}s)$. Then, $\sum_{a\in\mathcal{A}_{s}}\pi^{(t)}(a{\,|\,}s)>1$.

Therefore, $Z\geq\exp\left(-\eta_{s}\max_{a^{\prime}\in\mathcal{A}_{s}}l^{(t)}(s,a^{\prime})\right)$.

Similarly, when $Z>\exp\left(-\eta_{s}\min_{a^{\prime}\in\mathcal{A}_{s}}l^{(t)}(s,a^{\prime})\right)$, for any $a\in\mathcal{A}_{s}$, we have $\frac{\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}(a{\,|\,}s)\exp\left(-\eta_{s}l^{(t)}(s,a)\right)}{Z}<\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}(a{\,|\,}s)$. It implies that $\sum_{a\in\mathcal{A}_{s}}\pi^{(t)}(a{\,|\,}s)<\sum_{a\in\mathcal{A}_{s}}\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}(a{\,|\,}s)$, unless $\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}(a{\,|\,}s)=\gamma_{s}\nu_{s,a}$ for all $a\in\mathcal{A}_{s}$, which is impossible since we assume $\gamma_{s}<1$. Therefore, $Z\leq\exp\left(-\eta_{s}\min_{a^{\prime}\in\mathcal{A}_{s}}l^{(t)}(s,a^{\prime})\right)$.

Then, if $\frac{\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}(a{\,|\,}s)\exp\left(-\eta_{s}l^{(t)}(s,a)\right)}{Z}\geq\gamma_{s}\nu_{s,a}$, we have

$$ $\displaystyle 1\leq\frac{\pi^{(t)}(a{\,|\,}s)}{\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}(a{\,|\,}s)}=$ $\displaystyle\frac{\exp\left(-\eta_{s}l^{(t)}(s,a)\right)}{Z}$ $\displaystyle\leq$ $\displaystyle\exp\left(\eta_{s}\max_{a^{\prime}\in\mathcal{A}_{s}}l^{(t)}(s,a^{\prime})-\eta_{s}l^{(t)}(s,a)\right)$ $\displaystyle\leq$ $\displaystyle\exp\left(\frac{\eta_{s}}{\alpha_{s}\left(1+\eta_{s}\tau_{s}^{(t-1)}\right)}\left(\max_{a^{\prime}\in\mathcal{A}_{s}}q^{(t)}(s,a^{\prime})-q^{(t)}(s,a)\right)+\frac{\eta_{s}\tau_{s}^{(t-1)}}{1+\eta_{s}\tau_{s}^{(t-1)}}\log\max_{a^{\prime}\in\mathcal{A}_{s}}\frac{\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}(a^{\prime}{\,|\,}s)}{\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}(a{\,|\,}s)}\right)$ $\displaystyle\overset{(i)}{\leq}$ $\displaystyle\exp\left(\frac{\eta_{s}}{\alpha_{s}}\left(2\left\|\bm{q}\right\|_{\infty}+\frac{\tau\alpha_{s}}{M_{1}}\log\frac{1}{\gamma}\right)\right)$ $\displaystyle\overset{(ii)}{\leq}$ $\displaystyle 1+2\frac{\eta_{s}}{\alpha_{s}}\left(2\left\|\bm{q}\right\|_{\infty}+\frac{\tau\alpha_{s}}{M_{1}}\log\frac{1}{\gamma}\right)$ $$

In $(i)$ we use the fact $\left\|\bm{q}\right\|_{\infty}\geq\left|q^{(t)}(s,a)\right|$ for any $a\in\mathcal{A}_{s}$. In $(ii)$ we use $e^{x}\leq 1+2x$ for $x\in[0,1]$.

If $\frac{\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}(a{\,|\,}s)\exp\left(-\eta_{s}l^{(t)}(s,a)\right)}{Z}<\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}(a{\,|\,}s)$, we have

$$ $\displaystyle\frac{\exp\left(-\eta_{s}l^{(t)}(s,a)\right)}{Z}\geq$ $\displaystyle\exp\left(\eta_{s}\min_{a^{\prime}\in\mathcal{A}_{s}}l^{(t)}(s,a^{\prime})-\eta_{s}l^{(t)}(s,a)\right)\geq\exp\left(-\frac{\eta_{s}}{\alpha_{s}}\left(2\left\|\bm{q}\right\|_{\infty}+\frac{\tau\alpha_{s}}{M_{1}}\log\frac{1}{\gamma}\right)\right).$ $$

Therefore,

$$ $\displaystyle 1\geq\frac{\pi^{(t)}(a{\,|\,}s)}{\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}(a{\,|\,}s)}\geq\frac{\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}(a{\,|\,}s)\exp\left(-\eta_{s}l^{(t)}(s,a)\right)}{\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}(a{\,|\,}s)Z}\geq$ $\displaystyle\exp\left(-\frac{\eta_{s}}{\alpha_{s}}\left(2\left\|\bm{q}\right\|_{\infty}+\frac{\tau\alpha_{s}}{M_{1}}\log\frac{1}{\gamma}\right)\right)$ $\displaystyle\geq$ $\displaystyle 1-\frac{\eta_{s}}{\alpha_{s}}\left(2\left\|\bm{q}\right\|_{\infty}+\frac{\tau\alpha_{s}}{M_{1}}\log\frac{1}{\gamma}\right).$ $$

Then, for any $a\in\mathcal{A}_{s}$, we have

$$ $\displaystyle\left|\frac{\pi^{(t)}(a{\,|\,}s)}{\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}(a{\,|\,}s)}-1\right|\leq$ $\displaystyle 2\frac{\eta_{s}}{\alpha_{s}}\left(2\left\|\bm{q}\right\|_{\infty}+\frac{\tau\alpha_{s}}{M_{1}}\log\frac{1}{\gamma}\right).$ $$

Therefore,

$$ $\left\|\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s)\right\|_{1}=\sum_{a\in\mathcal{A}_{s}}\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}(a{\,|\,}s)\left|\frac{\pi^{(t)}(a{\,|\,}s)}{\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}(a{\,|\,}s)}-1\right|\leq 2\frac{\eta_{s}}{\alpha_{s}}\left(2\left\|\bm{q}\right\|_{\infty}+\frac{\tau\alpha_{s}}{M_{1}}\log\frac{1}{\gamma}\right).$ $$

Similarly, the upperbound above also holds for $\left|\frac{\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}(a{\,|\,}s)}{\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}(a{\,|\,}s)}-1\right|$. ∎

###### Lemma F.3 .

###### Proof of Lemma B.5 .

### F.4 Update Rule of MWU

For ease of representation, we ignore the learning rate $\eta$ without loss of generality (the update-rule is the same without $\eta$ when multiplying both the gradient $\bm{g}$ and $\tau$ by $\eta$).

###### Lemma F.4 .

Consider the update-rule $\bm{x}^{(2)}=\mathop{\mathrm{argmin}}_{\bm{x}\in\Delta^{\gamma,\bm{\nu}}_{|\mathcal{A}|}}\left\langle\bm{x},\bm{g}\right\rangle+\tau\psi(\bm{x})+D_{\psi}(\bm{x},\bm{x}^{(1)})$ where $\bm{x}^{(1)}\in\Delta^{\gamma,\bm{\nu}}_{|\mathcal{A}|}$, $\gamma\geq 0$ is a constant, and $\bm{\nu}\in\Delta^{|\mathcal{A}|}$, $\mathcal{A}$ is the action set and $\psi(\bm{x})=\sum_{a\in\mathcal{A}}x\log x+\log|\mathcal{A}|$. Then, the update-rule is equivalent to

$$ $\displaystyle x^{(2)}_{a}=\max\left\{\frac{\left(x^{(1)}_{a}\right)^{\frac{1}{1+\tau}}\exp(-\frac{g_{a}}{1+\tau})}{Z},\gamma\nu_{a}\right\}$ (F.4) $$

for any $a\in\mathcal{A}$. $Z>0$ is the normalizing constant to ensure $\sum_{a\in\mathcal{A}}x^{(2)}_{a}=1$.

###### Proof.

By definition of Bregman divergence, $D_{\psi}(\bm{x},\bm{x}^{(1)})=\sum_{a\in\mathcal{A}}x_{a}\log\frac{x_{a}}{x^{(1)}_{a}}$. Therefore, the Lagrangian function of the update-rule is

$$ $\displaystyle\mathcal{F}(\bm{x},\alpha,\bm{\beta}):=\left\langle\bm{x},\bm{g}\right\rangle+\tau\sum_{a\in\mathcal{A}}x_{a}\log x_{a}+\sum_{a\in\mathcal{A}}x_{a}\log\frac{x_{a}}{x^{(1)}_{a}}+\alpha(\sum_{a\in\mathcal{A}}x_{a}-1)+\sum_{a\in\mathcal{A}}\beta_{a}(x_{a}-\gamma\nu_{a}).$ $$

By taking $\nabla_{\bm{x}}\mathcal{F}(\bm{x},\alpha,\bm{\lambda})=0$, for any $a\in\mathcal{A}$, we have

$$ $\displaystyle g_{a}+\tau\log x^{(2)}_{a}+\log\frac{x^{(2)}_{a}}{x^{(1)}_{a}}+1+\tau+\alpha+\beta_{a}=0,$ $$

which implies that

$$ $\displaystyle x^{(2)}_{a}=\left(x^{(1)}_{a}\right)^{\frac{1}{1+\tau}}\exp\left(-\frac{1}{1+\tau}\left(g_{a}+1+\tau+\alpha+\beta_{a}\right)\right).$ $$

By duality, $\beta_{a}\leq 0$. By complementary slackness, we have $\beta_{a}(x^{(2)}_{a}-\gamma\nu_{a})=0$. Therefore, when $\beta_{a}<0$, we have $x^{(2)}_{a}=\gamma\nu_{a}$, which implies that $\left(x^{(1)}_{a}\right)^{\frac{1}{1+\tau}}\exp\left(-\frac{1}{1+\tau}\left(g_{a}+1+\tau+\alpha\right)\right)<\gamma\nu_{a}$. When $\beta_{a}=0$, we have $x^{(2)}_{a}\geq\gamma\nu_{a}$ so that $\left(x^{(1)}_{a}\right)^{\frac{1}{1+\tau}}\exp\left(-\frac{1}{1+\tau}\left(g_{a}+1+\tau+\alpha\right)\right)\geq\gamma\nu_{a}$. Therefore, the effect of $\beta_{a}$ is equivalent to take a max on $\left(x^{(1)}_{a}\right)^{\frac{1}{1+\tau}}\exp\left(-\frac{1}{1+\tau}\left(g_{a}+1+\tau+\alpha\right)\right)$ and we have the update-rule

$$ $\displaystyle x^{(2)}_{a}=\max\left\{\left(x^{(1)}_{a}\right)^{\frac{1}{1+\tau}}\exp\left(-\frac{1}{1+\tau}\left(g_{a}+1+\tau+\alpha\right)\right),\gamma\nu_{a}\right\}=\max\left\{\frac{\left(x^{(1)}_{a}\right)^{\frac{1}{1+\tau}}\exp(-\frac{g_{a}}{1+\tau})}{Z},\gamma\nu_{a}\right\}$ $$

where $Z=\exp\left(\frac{1+\tau+\alpha}{1+\tau}\right)$.∎

###### Remark F.5 .

In practice, we can implement the update-rule in Lemma [F.4](#A6.Thmtheorem4) as follows. We assume $\gamma<1$ since otherwise we can simply let $\bm{x}^{(2)}=\bm{\nu}$.

- •
Compute $\widehat{x}_{a}=\left(x^{(1)}_{a}\right)^{\frac{1}{1+\tau}}\exp(-\frac{g_{a}}{1+\tau})$ and sort it in increasing order, which is $\widehat{x}_{1}\leq\widehat{x}_{2}\leq...\leq\widehat{x}_{|\mathcal{A}|}$. Simultaneously, adjusting $\bm{\nu}$ according to the sorting of $\widehat{\bm{x}}$ to get $\widehat{\bm{\nu}}$, which is the lowerbound $\widehat{\bm{x}}$ should satisfy.
- •
Enumerate $i=0,1,2,...,|\mathcal{A}|$. Let $Z=\frac{\sum_{j>i}\widehat{x}_{j}}{1-\gamma\sum_{j=1}^{i}\widehat{\nu}_{j}}$.
- •
Check $\widehat{x}_{i}\leq\gamma\widehat{\nu}_{i}Z$ if $i>0$ and $\widehat{x}_{i+1}\geq\gamma\widehat{\nu}_{i+1}Z$ if $i<|\mathcal{A}|$. If the current $Z$ satisfies, return it. Otherwise, continue the enumeration.

According to the monotonicity of $\max\left\{\frac{\left(x^{(1)}_{a}\right)^{\frac{1}{1+\tau}}\exp(-\frac{g_{a}}{1+\tau})}{Z},\gamma\nu_{a}\right\}$ with respect to $Z$, the algorithm above will definitely find the correct $Z$ and the time complexity is $O(|\mathcal{A}|\log|\mathcal{A}|)$ (the bottleneck is the sort).

###### Lemma F.4 .

###### Proof.

###### Remark F.5 .

## Appendix G Experiment Details

In Table [2](#A7.T2), we depict the set of hyper-parameters that the gridsearch is performed on. All experiments are conducted on 240 cores of Intel(R) Xeon(R) Platinum 8260 CPU @ 2.40GHz, and the code is implemented by [LiteEFG](https://github.com/liumy2010/LiteEFG) with game environments implemented by [OpenSpiel](https://github.com/google-deepmind/open_spiel) (Lanctot et al., ). The grid search is applied to the following range of parameters to find the best hyper-parameters.

**Table 2: Parameter grid for gridsearch. The row specifies the algorithm and the column specifies the hyper-parameter. $\alpha,\beta$ is the name of hyper-parameter of DCFR (Brown and Sandholm, ). In the grid search, all possible combinations are performed, and the one with the lowest exploitability of the last iterate is selected. For the stochastic feedback experiments, we repeat the experiments for 100 times on different seeds and use the hyper-parameter with the lowest average exploitability of the last iterate.**
|  | $\eta(\alpha)$ | $\tau(\beta)$ | $\gamma$ | Regularizer |
| --- | --- | --- | --- | --- |
| CFR / CFR+ | N/A | 0.0 | 0.1, 0.01,<br>0.001, 0.0001 | N/A |
| DCFR | $\left\{-\infty,\infty\right\}\cup$<br>$\left\{-2.5,-2.0,...,2.5\right\}$ | $\left\{-\infty,\infty\right\}\cup$<br>$\left\{-2.5,-2.0,...,2.5\right\}$ | 0.5, 1, 1.5,<br>2, 2.5, 3 | N/A |
| PCFR | N/A | 0.0 | 0.0 | N/A |
| MMD | 0.1, 0.01, 0.005,<br>0.001, 0.0001 | 0.1, 0.01, 0.05,<br>0.001, 0.0001, 0.0 | 0.0 | Entropy / Euclidean |
| QFR | 0.1, 0.01, 0.001, 0.0001 | 0.1, 0.01, 0.001,<br>0.0001, 0.0 | 0.1, 0.01,<br>0.001, 0.0001 |  |

We present the experimental results for full information feedback in [Figure 2](#A7.F2), that is, we use trajectory Q-value, Q-value, or counterfactual value as $q^{(t)}(s,\cdot)$ in the update rule ([5.2](#S5.E2)). In Figure [2](#A7.F2), we plot the last-iterate performance for all the algorithms to ensure the comparison is fair.

Figure: Figure 2: The result of full-information feedback in four benchmark games.
Refer to caption: /html/2408.00751/assets/x3.png

## Appendix H QFR with Lazy Update

In this section, we will show a variant of QFR, which we coin it as the lazy update version. In this version, the original dilated regularizer is applied instead of the bidilated one. The advantage of this variant is that the convergence only requires the proportion of $\eta_{s}$ and $\eta_{s}^{\rm anc}$ to be a constant with Q-value and counterfactual value, so that the convergence rate depends polynomially on the game size.

The disadvantage is that importance sampling is needed for the additional regularizer when using stochastic feedback (the dispersion of feedback is not very large since the magnitude of the additional regularizer is controlled by $\tau$). Moreover, when sampling a trajectory, for those infosets that are not on the trajectory, we still need to update the strategy $\pi(\cdot{\,|\,}s)$ in them. In other words, for those infosets with $\widetilde{q}^{(t)}=0$, we still need to update the strategy due to the additional regularizer (please refer to Eq ([H.3](#A8.E3)) for details). In practice, we can ignore the update of those infosets that are not along the trajectory, and postpone the update till the next time visiting them. That’s why we call it a lazy update.

Consider the following update-rule, which is Eq ([5.2](#S5.E2)) with dilated regularizer instead of the bidilated one.

$$ $\begin{split}\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)\!=\!\mathop{\mathrm{argmin}}_{\pi_{p(s)}(\cdot{\,|\,}s)\in\Delta_{|\mathcal{A}_{s}|}^{\gamma_{s},\bm{\nu}_{s}}}&\left\langle\pi_{p(s)}(\cdot{\,|\,}s),-q^{(t-1)}(h,\cdot)\right\rangle+\frac{\tau}{m^{(t-1)}_{s}}\psi_{s}^{\Delta}(\pi_{p(s)}(\cdot{\,|\,}s))+\frac{1}{\eta_{s}}D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s))\\ \mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s)\!=\!\mathop{\mathrm{argmin}}_{\pi_{p(s)}(\cdot{\,|\,}s)\in\Delta_{|\mathcal{A}_{s}|}^{\gamma_{s},\bm{\nu}_{s}}}&\left\langle\pi_{p(s)}(\cdot{\,|\,}s),-q^{(t)}(s,\cdot)\right\rangle+\frac{\tau}{m^{(t)}_{s}}\psi_{s}^{\Delta}(\pi_{p(s)}(\cdot{\,|\,}s))+\frac{1}{\eta_{s}}D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s))\\ \end{split}$ (H.1) $$

As [Theorem 5.2](#S5.Thmtheorem2), we can show the convergence of this update-rule. Note that in the following theorem, the proportion of $\eta_{s}$ and $\eta_{s}^{\rm anc}$ is now a constant when the feedback is Q-value or counterfactual value, which implies a polynomial dependence on the game size.

###### Theorem H.1 .

Consider the update rule ([H.1](#A8.E1)) and $q^{(t)}(s,\cdot)$ is chosen to be counterfactual value, trajectory Q-value, or Q-value. When $\frac{\eta_{s}^{\rm anc}}{\eta_{s}}\leq\frac{\tau}{2C_{s}^{-}}$ for any $s\in{\mathcal{S}}$ and [A](#A2.I1.i1),[B](#A2.I1.i2),[C](#A2.I1.i3) are satisfied, we have the following guarantee.

$$ $\displaystyle\sum_{t=2}^{T}D_{\psi^{\Pi}}(\bm{\mu}^{(\tau,\gamma),*},\mkern 1.5mu\overline{\mkern-1.5mu\bm{\mu}\mkern-1.5mu}\mkern 1.5mu^{(t)})\leq$ $\displaystyle 2\sum_{s\in{\mathcal{S}}}C_{s}^{/}\eta_{s}^{\rm anc}\mu^{(\tau,\gamma),*}(\sigma(s))\sum_{t=1}^{T}\left|\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\psi_{s}^{\Delta}(\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s))\right|$ (H.2) $\displaystyle+\frac{4}{\tau}\sum_{s\in{\mathcal{S}}}C_{s}^{\text{diff}}\mu^{(\tau,\gamma),*}(\sigma(s))\left\|\bm{q}\right\|_{\infty}\eta_{s}M_{2}T+\frac{2}{\tau}\sum_{s\in{\mathcal{S}}}\frac{M_{2}}{\eta_{s}}\mu^{(\tau,\gamma),*}(\sigma(s))D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(1)}_{p(s)}(\cdot{\,|\,}s)).$ $$

###### Lemma H.2 (Generalized from Lemma C.2. in Liu et al. ( 2023 ) ) .

Consider the update rule in Eq ([5.2](#S5.E2)). When $\psi_{s}^{\Delta}$ satisfies $D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\pi_{p(s)}(\cdot{\,|\,}s)^{\prime})\geq\frac{1}{2}\|\pi_{p(s)}(\cdot{\,|\,}s)-\pi_{p(s)}(\cdot{\,|\,}s)^{\prime}\|_{p}^{2}$ with $p=2$, then for any $\pi_{p(s)}(\cdot{\,|\,}s)\in\Pi$ and $t\geq 1$, we have

$$ $\begin{split}&\eta_{s}\frac{\tau}{m^{(t)}_{s}}\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\eta_{s}\frac{\tau}{m^{(t)}_{s}}\psi_{s}^{\Delta}(\pi_{p(s)}(\cdot{\,|\,}s))+\eta_{s}\tau(\frac{1}{m^{(t-1)}_{s}}-\frac{1}{m^{(t)}_{s}})(\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\psi_{s}^{\Delta}(\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s)))\\ &+\eta_{s}\langle-q^{(t)}(s,\cdot),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\pi_{p(s)}(\cdot{\,|\,}s)\rangle\\ \leq&D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s))-(1+\eta_{s}\frac{\tau}{m^{(t)}_{s}})D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s))\\ &-(1+\eta_{s}\frac{\tau}{m^{(t-1)}_{s}})D_{\psi_{s}^{\Delta}}(\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))\\ &-D_{\psi_{s}^{\Delta}}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s))+\eta_{s}\left\langle q^{(t-1)}(h,\cdot)-q^{(t)}(s,\cdot),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s)\right\rangle.\end{split}$ $$

The lemma’s proof is similar to [Lemma D.2](#A4.Thmtheorem2).

Multiplying $m^{(t)}_{s}$ on both sides of Lemma [D.2](#A4.Thmtheorem2), we have

$$ $\displaystyle\eta_{s}\tau\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\eta_{s}\tau\psi_{s}^{\Delta}(\pi_{p(s)}(\cdot{\,|\,}s))+\eta_{s}\tau(\frac{m^{(t)}_{s}}{m^{(t-1)}_{s}}-1)(\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\psi_{s}^{\Delta}(\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s)))$ $\displaystyle+\eta_{s}m^{(t)}_{s}\langle-q^{(t)}(s,\cdot),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\pi_{p(s)}(\cdot{\,|\,}s)\rangle$ $\displaystyle\leq$ $\displaystyle m^{(t)}_{s}D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s))-(m^{(t)}_{s}+\eta_{s}\tau)D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s))$ $\displaystyle-(m^{(t)}_{s}+\eta_{s}\tau\frac{m^{(t)}_{s}}{m^{(t-1)}_{s}})D_{\psi_{s}^{\Delta}}(\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))$ $\displaystyle-m^{(t)}_{s}D_{\psi_{s}^{\Delta}}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s))+\eta_{s}m^{(t)}_{s}\left\langle q^{(t-1)}(h,\cdot)-q^{(t)}(s,\cdot),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s)\right\rangle.$ $$

By using Property [2](#Thmproperty2), we have

$$ $\displaystyle\left(\frac{m^{(t)}_{s}}{m^{(t-1)}_{s}}-1\right)(\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\psi_{s}^{\Delta}(\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s)))\geq-C_{s}^{/}\eta_{s}^{\mathrm{anc}}\left|\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\psi_{s}^{\Delta}(\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s))\right|.$ $$

Furthermore, by using Lemma [B.2](#A2.Thmtheorem2) and Hölder’s Inequality, we have

$$ $\displaystyle\left|\left\langle q^{(t-1)}(h,\cdot)-q^{(t)}(s,\cdot),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s)\right\rangle\right|$ $\displaystyle\leq$ $\displaystyle\left\|q^{(t)}(s,\cdot)-q^{(t-1)}(h,\cdot)\right\|_{\infty}\cdot\left\|\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s)\right\|_{1}\leq 2C_{s}^{\mathrm{diff}}\left\|\bm{q}\right\|_{\infty}\eta_{s}.$ $$

where $\left\|\bm{q}\right\|_{\infty}=\max_{t\in[T],s\in{\mathcal{S}}}\left\|q^{(t)}(s,\cdot)\right\|_{\infty}$.

By telescoping and non-negativity of Bregman divergence, we have

$$ $\displaystyle\sum_{t=1}^{T}\left(\eta_{s}\tau\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\eta_{s}\tau\psi_{s}^{\Delta}(\pi_{p(s)}(\cdot{\,|\,}s))+\eta_{s}m^{(t)}_{s}\langle-q^{(t)}(s,\cdot),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\pi_{p(s)}(\cdot{\,|\,}s)\rangle\right)$ $\displaystyle\leq$ $\displaystyle\sum_{t=2}^{T}\underbrace{\left(m^{(t)}_{s}-m^{(t-1)}_{s}-\eta_{s}\tau\right)}_{\leavevmode\hbox to7.23pt{\vbox to7.23pt{\pgfpicture\makeatletter\hbox{\hskip 3.61601pt\lower-3.61601pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.41602pt}{0.0pt}\pgfsys@curveto{3.41602pt}{1.88663pt}{1.88663pt}{3.41602pt}{0.0pt}{3.41602pt}\pgfsys@curveto{-1.88663pt}{3.41602pt}{-3.41602pt}{1.88663pt}{-3.41602pt}{0.0pt}\pgfsys@curveto{-3.41602pt}{-1.88663pt}{-1.88663pt}{-3.41602pt}{0.0pt}{-3.41602pt}\pgfsys@curveto{1.88663pt}{-3.41602pt}{3.41602pt}{-1.88663pt}{3.41602pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s))$ $\displaystyle+C_{s}^{/}\eta_{s}\tau\eta_{s}^{\mathrm{anc}}\sum_{t=1}^{T}\left|\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\psi_{s}^{\Delta}(\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s))\right|+2C_{s}^{\mathrm{diff}}\left\|\bm{q}\right\|_{\infty}\eta_{s}^{2}M_{2}T$ $\displaystyle+m^{(1)}_{s}D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(1)}_{p(s)}(\cdot{\,|\,}s)).$ $$

1 can be upper-bounded by $C_{s}^{-}\eta_{s}^{\mathrm{anc}}-\eta_{s}\tau\leq-\frac{\eta_{s}\tau}{2}$ by Property [2](#Thmproperty2) and letting $\frac{\eta_{s}^{\mathrm{anc}}}{\eta_{s}}\leq\frac{\tau}{2C_{s}^{-}}$. By non-negativity of Bregman divergence, we have

$$ $\displaystyle\sum_{t=1}^{T}\left(\eta_{s}\tau\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\eta_{s}\tau\psi_{s}^{\Delta}(\pi_{p(s)}(\cdot{\,|\,}s))+\eta_{s}m^{(t)}_{s}\langle-q^{(t)}(s,\cdot),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\pi_{p(s)}(\cdot{\,|\,}s)\rangle\right)$ $\displaystyle\leq$ $\displaystyle-\frac{\eta_{s}\tau}{2}\sum_{t=2}^{T}D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s))+C_{s}^{/}\eta_{s}\tau\eta_{s}^{\mathrm{anc}}\sum_{t=1}^{T}\left|\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\psi_{s}^{\Delta}(\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s))\right|$ $\displaystyle+2C_{s}^{\mathrm{diff}}\left\|\bm{q}\right\|_{\infty}\eta_{s}^{2}M_{2}T+m^{(1)}_{s}D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(1)}_{p(s)}(\cdot{\,|\,}s)).$ $$

For simplicity, we use $\bm{\mu}\coloneqq(\bm{x},\bm{y})$, $F(\bm{\mu}^{\bm{\pi}})\coloneqq(-\bm{A}\bm{y},\bm{A}^{\top}\bm{x})$, $\Pi\coloneqq\Pi_{1}\times\Pi_{2}$, and ${\mathcal{S}}\coloneqq{\mathcal{S}}_{1}\times{\mathcal{S}}_{2}$.

By using Lemma [D.3](#A4.Thmtheorem3), we have

$$ $\displaystyle 0\overset{(i)}{\leq}$ $\displaystyle G^{(T),\Pi}(\bm{\mu}^{(\tau,\gamma),*})$ $\displaystyle=$ $\displaystyle\sum_{s\in{\mathcal{S}}}\mu^{(\tau,\gamma),*}(\sigma(s))G^{(T)}(h;\pi_{p(s)}^{(\tau,\gamma),*}(\cdot{\,|\,}h))$ $\displaystyle=$ $\displaystyle\sum_{s\in{\mathcal{S}}}\mu^{(\tau,\gamma),*}(\sigma(s))\sum_{t=1}^{T}\left(\tau\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\tau\psi_{s}^{\Delta}(\pi_{p(s)}^{(\tau,\gamma),*}(\cdot{\,|\,}h))+m^{(t)}_{s}\langle-q^{(t)}(s,\cdot),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\pi_{p(s)}^{(\tau,\gamma),*}(\cdot{\,|\,}h)\rangle\right)$ $\displaystyle\leq$ $\displaystyle-\frac{\tau}{2}\sum_{t=2}^{T}\sum_{s\in{\mathcal{S}}}\mu^{(\tau,\gamma),*}(\sigma(s))D_{\psi_{s}^{\Delta}}(\pi_{p(s)}^{(\tau,\gamma),*}(\cdot{\,|\,}h),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s))$ $\displaystyle+\sum_{s\in{\mathcal{S}}}C_{s}^{/}\tau\eta_{s}^{\mathrm{anc}}\mu^{(\tau,\gamma),*}(\sigma(s))\sum_{t=1}^{T}\left|\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\psi_{s}^{\Delta}(\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s))\right|$ $\displaystyle+2\sum_{s\in{\mathcal{S}}}C_{s}^{\mathrm{diff}}\mu^{(\tau,\gamma),*}(\sigma(s))\left\|\bm{q}\right\|_{\infty}\eta_{s}M_{2}T+\sum_{s\in{\mathcal{S}}}\frac{m^{(1)}_{s}}{\eta_{s}}\mu^{(\tau,\gamma),*}(\sigma(s))D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(1)}_{p(s)}(\cdot{\,|\,}s)).$ $$

$(i)$ is because $\bm{\mu}^{(\tau,\gamma),*}$ is the NE of the regularized and perturbed EFG. Then, by rearranging the terms, we have

$$ $\displaystyle\sum_{t=2}^{T}D_{\psi^{\Pi}}(\bm{\mu}^{(\tau,\gamma),*},\mkern 1.5mu\overline{\mkern-1.5mu\bm{\mu}\mkern-1.5mu}\mkern 1.5mu^{(t)})=$ $\displaystyle\sum_{t=2}^{T}\sum_{s\in{\mathcal{S}}}\mu^{(\tau,\gamma),*}(\sigma(s))D_{\psi_{s}^{\Delta}}(\pi_{p(s)}^{(\tau,\gamma),*}(\cdot{\,|\,}h),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s))$ $\displaystyle\leq$ $\displaystyle 2\sum_{s\in{\mathcal{S}}}C_{s}^{/}\eta_{s}^{\mathrm{anc}}\mu^{(\tau,\gamma),*}(\sigma(s))\sum_{t=1}^{T}\left|\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\psi_{s}^{\Delta}(\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s))\right|$ $\displaystyle+\frac{4}{\tau}\sum_{s\in{\mathcal{S}}}C_{s}^{\mathrm{diff}}\mu^{(\tau,\gamma),*}(\sigma(s))\left\|\bm{q}\right\|_{\infty}\eta_{s}M_{2}T+\frac{2}{\tau}\sum_{s\in{\mathcal{S}}}\frac{m^{(1)}_{s}}{\eta_{s}}\mu^{(\tau,\gamma),*}(\sigma(s))D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(1)}_{p(s)}(\cdot{\,|\,}s)).$ $$

The first line is by Lemma [5.1](#S5.Thmtheorem1). Now, we achieved best-iterate convergence to the regularized NE $\bm{\mu}^{(\tau,\gamma),*}$ in terms of Bregman divergence.∎

###### Theorem H.1 .

###### Lemma H.2 (Generalized from Lemma C.2. in Liu et al. ( 2023 ) ) .

### H.1 Lazy QFR with Stochastic Feedback

Consider when we can only estimate $q^{(t)}$ at each iteration, we apply the following update-rule to *each individual* infoset $s\in{\mathcal{S}}$,

$$ $\begin{split}\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)\!=\!\mathop{\mathrm{argmin}}_{\pi_{p(s)}(\cdot{\,|\,}s)\in\Delta_{|\mathcal{A}_{s}|}^{\gamma_{s},\bm{\nu}_{s}}}&\left\langle\pi_{p(s)}(\cdot{\,|\,}s),-\widetilde{q}^{(t-1)}(h,\cdot)\right\rangle+\frac{\tau}{m^{(t-1)}_{s}}\psi_{s}^{\Delta}(\pi_{p(s)}(\cdot{\,|\,}s))+\frac{1}{\eta_{s}}D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s))\\ \mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s)\!=\!\mathop{\mathrm{argmin}}_{\pi_{p(s)}(\cdot{\,|\,}s)\in\Delta_{|\mathcal{A}_{s}|}^{\gamma_{s},\bm{\nu}_{s}}}&\left\langle\pi_{p(s)}(\cdot{\,|\,}s),-\widetilde{q}^{(t)}(s,\cdot)\right\rangle+\frac{\tau}{m^{(t)}_{s}}\psi_{s}^{\Delta}(\pi_{p(s)}(\cdot{\,|\,}s))+\frac{1}{\eta_{s}}D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s)).\end{split}$ (H.3) $$

###### Remark H.3 .

Note that the update-rule above is not realistic, since even when an infoset is unvisited at timestep $t$, *i.e.* $\widetilde{q}^{(t)}=0$, we still need to update the strategy $\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s)$ and $\pi^{(t+1)}_{p(s)}(\cdot{\,|\,}s)$ due to the regularization term. However, we can do a lazy update. We will record the update time $t_{h}$ of each infoset $s\in{\mathcal{S}}$. Once we touch a infoset $s\in{\mathcal{S}}$ at timestep $t$, we will do $t-t_{h}$ steps update with a zero $q^{(t)}(s,\cdot)$ and update the time stamp $t_{h}\leftarrow t$.

Then, we have the following theorem. Note that the dependence on game size is still polynomial for Q-value and counterfactual value, since $\frac{\eta_{s}^{\rm anc}}{\eta_{s}}$ is bounded by a constant.

###### Theorem H.4 .

Consider update-rule Eq ([H.3](#A8.E3)) and $q^{(t)}(s,\cdot)$ is chosen to be counterfactual value, trajectory Q-value, or Q-value. When $\frac{\eta_{s}^{\rm anc}}{\eta_{s}}\leq\frac{\tau}{2C_{s}^{-}}$ for any $s\in{\mathcal{S}}$ and [A](#A2.I1.i1), [B](#A2.I1.i2), [C](#A2.I1.i3) are satisfied, we have the following guarantee with probability $1-\delta$.

$$ $\displaystyle\sum_{t=2}^{T}D_{\psi^{\Pi}}(\bm{\mu}^{(\tau,\gamma),*},\mkern 1.5mu\overline{\mkern-1.5mu\bm{\mu}\mkern-1.5mu}\mkern 1.5mu^{(t)})\leq$ $\displaystyle 2\sum_{s\in{\mathcal{S}}}C_{s}^{/}\eta_{s}^{\text{\rm anc}}\mu^{(\tau,\gamma),*}(\sigma(s))\sum_{t=1}^{T}\left|\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\psi_{s}^{\Delta}(\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s))\right|$ $\displaystyle+\frac{4}{\tau}\sum_{s\in{\mathcal{S}}}C_{s}^{\text{diff}}\mu^{(\tau,\gamma),*}(\sigma(s))\left\|\bm{q}\right\|_{\infty}\eta_{s}M_{2}T$ (H.4) $\displaystyle+\frac{2}{\tau}\sum_{s\in{\mathcal{S}}}\frac{m^{(1)}_{s}}{\eta_{s}}\mu^{(\tau,\gamma),*}(\sigma(s))D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu_{p(s)}^{(1)}(\cdot{\,|\,}s))+\frac{8}{\tau}\left\|\bm{q}\right\|_{\infty}\cdot\left|{\mathcal{S}}\right|\sqrt{2T\log\frac{1}{\delta}}.$ $$

By Lemma [5.3](#S5.Thmtheorem3), once we have an unbiased estimator $\widetilde{q}^{(t)}(s,\cdot)$ for $q^{(t)}(s,\cdot)$ in each infoset $s\in{\mathcal{S}}$ with the same upper-bound $\left\|\bm{q}\right\|_{\infty}$, by [Lemma 5.3](#S5.Thmtheorem3), with probability $1-\delta$, we have

$$ $\displaystyle\sum_{t=1}^{T}\left(\tau\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\tau\psi_{s}^{\Delta}(\pi_{p(s)}(\cdot{\,|\,}s))+m^{(t)}_{s}\langle-q^{(t)}(s,\cdot),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\pi_{p(s)}(\cdot{\,|\,}s)\rangle\right)$ $\displaystyle\leq$ $\displaystyle\sum_{t=1}^{T}\left(\tau\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\tau\psi_{s}^{\Delta}(\pi_{p(s)}(\cdot{\,|\,}s))+m^{(t)}_{s}\langle-\widetilde{q}^{(t)}(s,\cdot),\pi^{(t)}_{p(s)}(\cdot{\,|\,}s)-\pi_{p(s)}(\cdot{\,|\,}s)\rangle\right)+4\left\|\bm{q}\right\|_{\infty}\sqrt{2T\log\frac{1}{\delta}}$ $\displaystyle\overset{(i)}{\leq}$ $\displaystyle-\frac{\tau}{2}\sum_{t=2}^{T}D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t)}_{p(s)}(\cdot{\,|\,}s))+C_{s}^{/}\tau\eta_{s}^{\rm anc}\sum_{t=1}^{T}\left|\psi_{s}^{\Delta}(\pi^{(t)}_{p(s)}(\cdot{\,|\,}s))-\psi_{s}^{\Delta}(\mkern 1.5mu\overline{\mkern-1.5mu\pi\mkern-1.5mu}\mkern 1.5mu^{(t+1)}_{p(s)}(\cdot{\,|\,}s))\right|+2C_{s}^{\text{diff}}\left\|\bm{q}\right\|_{\infty}\eta_{s}m^{(t)}_{s}T$ $\displaystyle+\frac{m^{(1)}_{s}}{\eta_{s}}D_{\psi_{s}^{\Delta}}(\pi_{p(s)}(\cdot{\,|\,}s),\pi_{p(s)}^{(1)}(\cdot{\,|\,}s))+4\left\|\bm{q}\right\|_{\infty}\sqrt{2T\log\frac{1}{\delta}}.$ $$

$(i)$ follows the discussion in Appendix [D](#A4).

Then, the proof follows the proof of Theorem [5.2](#S5.Thmtheorem2). ∎

###### Remark H.3 .

###### Theorem H.4 .

## Appendix I Conclusions and Future Work

In this paper, we propose QFR, the first policy gradient algorithm for two-player zero-sum EFGs with iterate convergence. This is the first algorithm that can learn in EFGs with stochastic feedback while maintaining iterate-convergence. Moreover, QFR also first achieves learning in EFG without importance sampling. Albeit empirically we show that QFR works with uniform learning rates across all infosets, an interesting future direction is to prove that uniform learning rate also works for QFR. Further, whether it is possible to achieve polynomial, instead of pseudo-polynomial, dependence on the game size is unknown. We propose Lazy QFR in [Appendix H](#A8) with polynomial dependence on game size for Q-value and counterfactual feedback, but it requires lazy-update, which is impractical in non-tabular games. Moreover, an interesting future direction is to scale up QFR for large games.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: Please see weakness section.
soundness: 3
strengths: The analysis is sound with sublinear iterate average convergence. Proposed idea is novel and easy to follow.
summary: The authors propose an algorithm named QFR, which performs policy gradient updates to solve for regularized Nash equilibrium of two-player zero-sum EFGs. Convergence analysis is presented with sublinear rates. Experiment results also show the compatibility of Q-value based policy gradient updates to two-player zero-sum EFGs.
weaknesses: Analysis section:

- Although it makes sense to enforce strong convexity to the bilinear objective via regularization for easier analysis and stronger convergence guarantee, it also brings a bias to the equilibrium. As the authors are introducing a new regularization as their part of the novelty, it is also expected that the authors show how large this bias is.

Experiment section:

- As the authors mentioned in intro, the motivation behind proposing and proving the convergence of policy gradient based algorithm is to fit better under today's DRL trend. However, the experiment section does not show the advantage of QFR in this regard. As such, I suggest the authors to perform experiment on larger size and compare the solution performance (sample efficiency, computational efficiency etc) across all the different baseline algorithms.

- In figure 1, the convergence seems not reached for Liar's Dice and Leduc Poker. What is the reason behind truncation at the iteration 1000?

---

confidence: 2
contribution: 3
initial_rating: 5
presentation: 3
questions: The three desirable properties were mentioned at the beginning of the paper and seem to be important. But they seem to be not mentioned in later sections. For example, how can be observe from experiments the advantage of not using importance sampling in QFR? Does it make the proposed method have smaller variance than other methods? And also, how is the using rollout property helpful? Does it make the proposed method more sample efficient than other methods in the experiments?
soundness: 3
strengths: The idea of using Q-value in regret minimization is reasonable.

The writing is clear and and the paper is easy to follow.
summary: This paper proposes a policy gradient method, Q-Function based Regret Minimization (QFR) for solving two-player zero-sum extensive-form games, which uses rollouts to estimate values without importance sampling and achieves best-iterate convergence. Experiments on poker and Hex support the proposed method.
weaknesses: The proposed algorithm combines optimistic mirror descent updates and estimating Q-values from rollouts, both of which seem to be well known techniques. The technical novelty might be limited. 

Motivations seem to be disconnected with later sections, such as experiments.

---

confidence: 3
contribution: 4
initial_rating: 6
presentation: 3
questions: 1. Eq (2.3): should the direction of the inequality be flipped?
2. Have the author(s) tried to anneal the regularization? Or the results given in the experiments are all subject to regularized objective functions?
3. The proposed approach samples one trajectory using the current policy to compute estimates of value function at each iteration, I feel like this approach might have a high variance for larger games. Did author(s) have any observation and/or explanation regarding this?
4. The method seems to be a value function-based RL approach, as it estimates value functions and computes policies by maximizing the value functions. Why call it “policy gradient” method? Am I missing something?
5. The approach integrates existing approaches, e.g., convex regularizers and mirror descent. Could the author (s) clarify in the text clearly, what are the algorithmic modifications of the proposed approach beyond existing methods that enable the main features? My sense is that weighting of the regularizers considering both players’ paths along the tree is the main stretch, but I would like to know more specifically.
soundness: 3
strengths: - The contribution of the paper is strong, where the proposed approach only requires sampling of randomly generated trajectories (as opposed to using importance sampling) to estimate value function and compute policy. The approach is proved to have best-iterate convergence guarantees to the Nash equilibria of the regularized game under both full and imperfect information. 
- Clear introduction of related works and main obstacles in the field as well as contribution statement. I really enjoyed reading this part.
summary: The author(s) propose a Q-function based RL approach to solve zero-sum, extensive-form games under imperfect information. The proposed approach only requires sampling randomly generated trajectories and has iterate convergence guarantees.
weaknesses: 1. Line 280: The introduction of the algorithm can be more detailed. Right now, it is only a few lines and assumes the readers are already familiar with the references. For example, the author(s) ca n do a better job walking the readers through their update of the regularizer at Line 8.
2. The exploitability metric used in the experiment section is undefined. The experiment section can be better presented: what makes the proposed approach outperform a certain baseline in a certain setting? Why in certain setting, the proposed approach is inferior? Could the author(s) comment on how many samples are required by their approach vs. the baselines?
3. Completeness of the main text: In my opinion, discussion and conclusion should definitely be in the main text. Right now, the main text is not self-contained. That being said, while I appreciate the completeness of the first two sections, I also feel that they could probably be tightened to make room for other important content without losing much information. If the author(s) finds it impossible to fit the important content all in the main text, this paper might fit better for a journal. 
4. Other minor points: 
- Introduction (line 35): The statements (I) and (III) overlap with each other; they might be merged into one
- Line 91 “Techniques based on rollouts of …” overlaps the previous paragraph. Author(s) could move this point to above
- line 245: “additional”
- Algorithm 1 line 6: indentation of the if-else statement is broken
- Line 282: “Lastly, all infosets along the trajectory…” - I think the author(s) meant to point to Line 12 rather than Line 11

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 2
questions: I am really struggling to understand how Equation 4.3 is derived. Is there somewhere in the appendix that describes it? This confusion snowballed throughout the rest of Section 4.2.

“We can see QFR outperforms BOMD in all games”. Does it in Liar’s Dice?

Minor:

* Line 208: I find the definition of d(h|s) hard to understand. Can another sentence be added, or some more steps shown? Footnote 2 did not seem to enlighten it for me.
* Line 240: The notation of the policies is confusing. And what is pi bar? Has it been defined?
* Line 245: “ad ditional”
* Line 245: What does subscript “bi” mean on the regularizer? Bilinear? (edit: later on line 269, bidilated)
* Line 256: mu should be a psi?
* Line 296: Dodgy line formatting of “else”
* Line 303: Algo line 10. Where did this come from? Add a couple more words explaining the policy gradient update.
* Line 323: “...learning *rate* of inforset…”
* Line 411: +“the”, “and” -> “or”
* Line 417: I am really struggling to see where this inequality comes from.
* Line 469: “... with under …”
* Line 716: “a NE” -> “an NE”
* Line 796: What is alpha_s’? Did it get defined?
soundness: 3
strengths: The paper proposes a compelling algorithm and goes to great lengths to prove its convergence properties. Not all competing algorithms in the class have proven convergence properties. Some strengths over CFR:

* Best iterate convergence is more convenient than time-average convergence
* No importance sampling

The paper seems technically sound – I haven’t found a flaw yet – however there are parts that I did not understand (see weakness/questions). I am very open minded to increase the soundness score and overall rating of this paper after discussions with authors and other reviewers.
summary: The paper introduces a policy gradient method, QFR, for two-player (imperfect-information) zero-sum extensive-form games. The algorithm can approximate best-iterate convergence to a regularized Nash equilibrium. Policy gradient updates are preferred over CFR’s counterfactual updates because they can be computed from rollouts and do not require importance sampling. The paper proves its findings and runs some benchmarks on toy environments.
weaknesses: Some terms seem to be undefined which compounded confusion on an already complex paper. Please fix the undefined symbols (see questions for concrete examples).

There are many step-jumps in the main text that are not immediately clear to me. Some of these are explained in the appendices, but they are not always well sign-posted. Improved sign-posting may make reading through the paper easier (see questions for concrete examples).

Focuses on two-player zero-sum (a simple game-theoretic setting).

Meta-review: Most reviewers agree that this work makes a valuable contribution to policy gradient methods in 2p0s IIEFG with best-iterate convergence. However, concerns were raised regarding the quality of the presentation, which I believe can be addressed in a revised version. I strongly encourage the authors to enhance the presentation to make the work more accessible and coherent.

Decision: Accept (Poster)