A Policy-Gradient Approach to Solving Imperfect-Information Games with Best-Iterate Convergence
Authors: Mingyang Liu
Gabriele Farina
Asuman E. Ozdaglar
Venue: ICLR 2025 Poster (2025)
Keywords: Game Theory
Reinforcement Learning
Primary area: reinforcement learning
TL;DR: A scalable policy gradient approach for solving two-player zero-sum extensive-form games

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 \emph{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.

Published as a conference paper at ICLR 2025
A POLICY-GRADIENT APPROACH IMPERFECT-INFORRATION GAMES ITERATE CONVERGENCE
TO SOLVING WITH BEST
Mingyang Liu, Gabriele Farina Asuman Ozdaglar LIDS, EECS Massachusetts Institute Technology Cambridge, MA 02139, USA (1iumy19 9, gfarina asuman emit.edu
ABSTRACT
Policy gradient methods have become staple of any single-agent reinforce- ment learning toolbox, due to their combination of desirable properties: iterate convergence, efficient 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. In- stead, sound methods for extensive-form games rely approximating counter- factual values (as opposed to Q values), which are incompatible with policy gra- dient methodologies.
this paper, we investigate whether policy gradient can be safely used in two-player zero-sum imperfecctinfoomation (EFGs). We establish positive results, showing for the first time that a policy gradient method leads to provable best-iterate convergence to regularized Nash equilibrium in self-play.
extensive-form games
INTRODUCTION
In recent years, deep reinforcement learning (DRL. has succeeded tremendously in many applica- tions with large and complex environments, such as games (Mnih et al. 2013] Silver et al. 2017). autonomous driving (Kiran et al., (021), robotics (Ibarz et al. (021), and large language models (e.g. Ouyang et al. (2022) and ChatGPT), Much of these successes are due to the applicability of scalable algorithms,, such as proximal policy optimization (PPO) (Schulman et al. 2017) and soft actor-critic (SAC) (Haarnoja et al. 2018). The success of these algorithms hinges on a few critical properties- these algorithms (I) only require value estimates obtained from repeated random roll- outs which can be implemented efficiently: (II) converge in iterates (as opposed to in averages), removing the need for either training average policy approximator 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 imperfectt-nffomaatio settings, such as Texas Hold' em poker, where they tend to end up trapped in cycles without making progress (Balduzzi al.) 2019) Constructing policy gradient algorithms that enjoy the same wide applicability as their DRL counterparts and yet retain theoretical guarantees tabular settings even imperfect-infond informatton 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 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 equi- librium strategies in two-player zero-sum imperfect-informatiin extensive-fie games (EFGs) have been based Counterfactual Regret Minimization (CFR) (Zinkevich al. (007) and its modern variants [Tammelin et al.] 2015) Farina et al.) 2019a; Brown and Sandholm, 2019, Farina et al.) 202 These algorithms guarantee that their average strategy converges to the set of Nash equi-

---

Published as a conference paper at ICLR 2025
librium (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 (Steinberger 2019; Steinberger et al. 2020), sampling one at random; this can quickly become expensive in large games (Liu al. (023) ). Alternatively, some authors have included part of their pipeline-trainiee
a second network whose goal is approximating the av- erage strategy (Brown al. 2019). This approach is also undesirable, 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 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 (2019); Anagnostides et al. (2022); Wei et al. (202T); Lee et al. (202T); []; Cen et al. (2021); Liu et al. (2023), 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 re- inforcement learning, commonly based 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 payoffss of taking action a at an information set s need to consider the opponent's reach probabilities to 8, 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 '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 coun- terfactual values, several techniques have been proposed. A popular technique in this space using importance sampling to estimate the counterfactual values (Lanctot et al. 2009 Farina al.) 2020). 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 (Kozuno et al., [202): Bai et al. [022)] Fiegel et al.] (202)), thus hindering the stable training of neural networks. Certain variance reduction techniques, such those by Schmid et al. (2019), still suffer a large dispersion even though the variance is reduced.
External Sampling vs Trajectory Rollouts. Algorithms that sidestep the need for importance sam- pling, such as External Monte Carlo CFR (Lanctot et al.; 2009), do that at the expense of exploring about square-root of the EFG size in every iteration 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. In large games such as Stratego, where the size of the game tree is approximately 10535 (Perolat et al., 2022], external sampling needs to visit more than 10200 infosets at each iteration while trajectory rollouts only visits no more than 4 103 infosets per iteration.
Contributions. Given the above discussion, a question is natural:
Is it possible to design theoretically sound policy gradient method for solving two-player zero-sum extensive-form games that achieves the desiderata
(III) listed in the introduction?
Such algorithm would enable estimating values via rollouts, without need of importance sam- pling, all while ensuring iterate convergence, bringing EFG technology more in line with modern DRL technology. Our aim in this paper is to show that positive answer to the question is possible.
In this work, we develop the first principled policy gradient approach for solving imperfect infor- mation EFGs. Our approach builds on 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 new regularizer for EFGs, which 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
2

---

Published as a conference paper at ICLR 2025
the results, we devised a novel learning rate schedule that increases with the depth of the game tree. 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.
The discussion about related work is postponed to Appendix A
and summarized in Table L
Algorithm
Iterate convergence
Q-values
Stochastic feedback
DREAM, DEEP-CFR
Steinberger et al. 2020 Brown ct al. 2019
OOMD,
MMD
/ (last)
X
x
Lee al 2021 Liu et al. 2023 Sokota et al.
2023
DDAPTIVEFTRO (Fiegl et al. 2023
X
X
ESCHER. LOCALOMD McAleer et al.
2023
X
/
(off (off-policy)
Fregel al. 2024
ARMAC, ACH (rrssly atal. 2020: Fu
2021
(infinite samples)
OFR (this paper)
(bbet)
The table above compares the related work in three aspects: convergence guarantec, feed- back type, and supporting sampling or not. (last) and (best) denote last-iterate convergence and best-iterate convergence, respectively.
Table I:
2 PRELIMINARIES
For any vector x, we use 2; as element of vector x and | as the p-norm. We let ||>||| denote the Euclidean norm | We use A" to denote the (n - 1)-dimensional probabil- ity simplex {a E 00, 1]": Ei= = 1). We also define the Bregman divergence (2 y) = y) with respect to the c-strongly convex function vb The c-strong
(xx) (yy)) (Vv(y),
convexity of implies the bound Da y) 2 & || y|²² For any integer n 2 0, we use [x] == -1,2, .n. n. For any set S, we denote with [S] as its cardinality.
rooted game tree. In this paper focus on two- player zero-sum EFGs; hence, each node (also known as history) belongs to exactly one player out of the set [1 U {c). The special player e 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 H1, H2, He to denote the set of nodes belonging to each of the players. Terminal nodes (nodes without children) have an associated payoff for each player, i.e. Ui (h), (2) for player 1, 2 individually and Un (h) = (2) for any terminal node h since the game is zero- sum.
Extensive-Form Games. EFGs are played
To model imperfect information, the set of nodes H4 of each player i [2] is partitioned into infor- mation sets (or infosets for short) 82, 8m. Nodes in the same infoset are indistinguishable for the acting player that infoset. For example, in poker player cannot distinguish two nodes in the game tree that only differ on the private cards of player 2, since player does not observe the hand of the opponent. We use S == {s1, 82..... .... Im to denote the collection of all infosets of player i. Let H. := Hi U22 and S == Si U22 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 A, as the action set of infoset S. Furthermore, p: S + 21, 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 assump- tion is that nodes in the same infoset s E S, 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' e H, we write h - h if h is on the path from the root of the game tree to N'. Suppose h E and for any a E As. we write (h, a) E h/ the path from the root of the game tree to node h includes the edge corresponding to taking action a at s. For any two infosets 8, E S; that belong to the same player E [2], whenever there exist two nodes h E ht' E s' such that h C ht, we write [ s'. Similarly, we write (s, a) C s' for any a E A, when there exist nodes h E s, h' E s' such that (h, a) C h'. Moreover, we can define (s) C (s',a') for s' E S, for some i [2] and
Ag, a' Agr. Furthermore, for any player i e [2], we define the parent sequence (s)) of an infoset s E S, as the last infoset-action pair (s', a'), where s' &S, a' Ast, encountered along the path from root any nodes in (the choice of node
3

---

Published as a conference paper at ICLR 2025
in is irrelevant and (s) is either unique non-existing due to the perfect-recall assumption If there does not exist such infoset-action pair, we let o(s) = 0. For any node h E H. we define a, (h) as the last infoset-action pair (s, a). where E S,. encountered along the path from root to h. Finally, we define the depth ((h) of a node h E H. as the number of actions (of all players) on the path from the root of the game tree to h. The depth ((s) of an infoset E S is the maximum depth of any node h E s. Furthermore, D = maX (hh is the depth of the game.
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 E S; (i.e. p(s) = i), we use Ti(a 8) to denote the probability of taking action E AA, at any node in infoset s. We use π
[Ti. T2) to denote the strategy profile. For a player i, given an assignment of T. [s) for each s E S. a E A., then we can represent strategies for the EFG via their sequence-ford representation {Von Stengel, 1996). This is a mapping 14,", USES..EA, ((8, a)} + [0. 1] associated with strategy π, for each player i E [2]. where μ, (s,a) (a(s)) T.(a s) for any S Ag. Note that Ju (0) 1. For each h E H. according to the definition above, μ. (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 (c(h) to
denote the probability of reaching h E H contributed by the chance player. We assume me (h) > 0 for any h E H. since otherwise h will never be reached and thus can be removed from the game tree.
For simplicity, let 1r to be a vector with index (s, where S a As. and (pF))ss.a)
M (s, In this representation, the expected utility for Player 1 is the bilinear function (TT') Auo (the utility for Player 2 is -(uT') Aμ,² since the game is zero-sum). We de- fine the convex polytope of all valid sequence-form strategics as 111 I1g for player 1, 2 respectively, and II Iı x llg. For simplicity, let μ= == (n,7) fuz as the concatenation of the sequence- form strategy of both players. Sometimes, we will omit the subscript of μ when is clear from the Fp(s)) (s, as μz (s.-).
context, such as writing Hp(s)
Counterfactual and Q-Values. In this section we recall some key notions of values for EFGs. Our exposition mostly intuitive avoid notational burden; all definitions can be found in Appendix B 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 QT (h, a) associated with strategies TT, T2 for node-action pair (h, a) is defined as Player I's expected utility in the subtree rooted h, when Player 1 follows n and Player follows T2 after first selecting a as their first action.
The counterfactual value CFT (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.
CFT (h, == 2= (12( (h) QT (h,
The trajectory Q-value QT (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,
O7 (h, a) = 14 (on (h)) p5 (a2())) (h)hh) QT (h,
We now extend these definitions from nodes infosets. Consider infoset E S and action a As. For trajectory Q-value and counterfactual value we simply have QT (8, a). == Eneo QT (h, a) and CFT (s, a) == Eneo CFT (h, a). For Q-value, QT a) == En-a( 1) (h, where d(h s) x (h(hh) 21 (h))n² (12(h) (h))))( xx (o2())))))))))) for any E 8. All definitions are symmetric
for Player 2.
Ta respectively, Regret and Equilibrium. When players 1 and 2 play according to strategies μ P2 the utility of Player 1 is (TTT)) Apz² and that of Player 2 is - (4T)) ) A since the game is zero- sum. An e-approximate Nash equilibrium (NE) of the game is then defined as follows.
Definition 2.1 (e-approximate Nash Equilibrium). For compact convex set C1, C2, strategy profile (21, E Ci x C2 is an e-approximate NE if
max PJ Ape EC
min PgEC2
T Aîe S p
(2.1)
'A E Es IA.I 1
is the utility matrix of the game.
Because (h) = (s) for any 8 S and h due the perfect-recall assumption.
4

---

Published as a conference paper at ICLR 2025
When O, also simply call the strategy profile Nash equilibrium (NE). Equation 2.. is also called the exploitability of the strategy profile (H1,H2).
Given sequence of T strategy pairs (41) ) E Ci x C2, we can define the regret of Player 1 as (Player 2's is analogous).
T Σ
(8) T M1 (1--11
R
max Bi
Aug 60
(2.2)
EC1
A folklore result establishes a direct connection between regret minimization and approximate Nash equilibrium. Specifically, when the players' strategies incur regret R and R!!") respectively, then the average strategies of the players form an e-approximate NE, where
c= (R + //T.
(2.3)
3 Q-FUNCTION BASED REGRET MINIMIZATION (QFR)
In this section, we propose our policy gradient algorithm for EFGs, which we coin Q-Function based Regrel Minimization (QFR). In QFR, for each player i [2] and state E S₁, enforce the strategy (t) Ti (+|s) to explore with probability using the exploration strategy Us. in order to ensure that each infoset will be reached with positive probability > 0.
Then, we show that QFR converges in best iterate to the regularized Nash equilibrium. Specifically,
OFR will converge the solution (((,)))+ (p) (1(=>)) ,142 (T:7))=)) of the original bilinear minimax objective plus additional regularization term Vii (nT 112 and 1 (m"', which we call bidi- lated regularizer. wii (nf" .122) is strongly convex with respect to u and convex with respect to plz 32 Conversely, vo (4r² . is strongly convex with respect to 2 and convex with respect 11 In contrast to the original bilinear objective, optimizing the regularized objective will sta- bilize the training process, and result in better convergence results. Formally, the regularized and perturbed (perturb refers the exploration) game is,
max T gll VaES,, mi (1(- Teih (/) VseS. m2(- [s)
min "2 E
Th (n Aug TVbi (MT) ,15)) + Tuh (M T ,
(3.1)
where A 14.1 T, = f Va E As, Uo 2 )o and 5 2 0 controls the magnitude of the regularizer. Note that the NE of the non-regularized game can be computed by annealing the regularization coefficient r by using standard technique (Liu et al. 2023
To decompose the regularizer th to each infoset for efficient update, we resort to the concept di- lated regularizer (Hoda al.] 2010]. Take Euclidean norm for example, unlike naively choosing || as the regularizer, dilated regularizer weights the regularizer 2 [- b)]| 2 at each infoset
S; by the reach probability of player i to s, i.e. & ExEs, n (a(s)) [+] =)]l It is shown in Hoda et al. (2010) that the dilated regularizer is strongly convex with respect to nT" However, dilated regularizer vt"l. only weights the reach probability of player i, neglecting that of the oppo- nents, which the asymmetry causes importance sampling when estimating the regularizer term in rolling trajectory. Therefore, natural solution is weighting the strongly convex regularizer WA AlAJl + IR at each infoset E S (typically it is Euclidean norm or negative entropy) by the reach probability of all players. Formally, the bidilated regularizer II, (4T 2²²)) of player is defined as (that of player 2 can defined similarly).
Vi (MT) 22) = Σ uT (a(s)) Σ EHe(h))p3(0a(1))) os (T (Bidilated regularizer)
SES,
hEN
th (1T1)= = Σ 1 (a (mT()))))
(Dilated regularizer)
SES,
5

---

Published as a conference paper at ICLR 2025
The details can be referred to Appendix D For notational simplicity, let a (1 II R wi (x²)) + (1²2 and (1 IT ents at hand, we can introduce the algorithm Q-Function based Regret minimi zat (OFR). At each timestep t, OFR will sample a trajectory according to the current strategy π ((t-1) (Line 3 of Algorithm[ Then, the trajectory Q-value will be estimated from the trajectory (Line 10- 12, & estimates the trajectory Q-value contributed by additional bidilated regularizer of the game, W estimates the that contributed by the reward of the original game). Lastly, all infosets along the trajectory will be updated with a variant of Regularized Optimistic Mirror Descent (Reg-OMD) at timestep i, the strategy T(() serves as Then in the next timestep 1, ((1) will be updated with the trajectory
R &i ;4?)) wil (14 122) ) With all ingredi- 2
proposed in Liu et al. (2023) (Line 14). In
the prediction of л (t++),
Q-value estimated at π (t), The pseudocode of QFR is proposed in Algorithm |
Algorithm Q-Function based Regret minimization (QFR)
(- (-|s) as uniform distribution over A AAA,l for any E [2] and S,. Initialize π (-1s) :H
2: for t- 2, , do
3: Sample a trajectory (ho, ao, hu, .()) ~ π (t-11) where = and hg is terminal
4: Let $1, 88K be the infosets corresponding to has hi, lxg for 1: = K
5:
--,
do
6:
if node h& belongs to the chance player then continue to the new iteration directly
7:
8:
else
9:
- p(s))
v/ Σ 1 Way (mp (=((-1)) Σx 1 1=(()))=33- Va (m3-pp)) (
10:
11:
W + Upxx))
W ). end-of-trajectory utility of player p (only terminal nodes have utility * 0)
12:
Compute the unbiased estimator of trajectory Q-value as
g (Sk. a)
(W + Tbb) V. log mp
(t (t-1) (al (a|ss)
ag Otherwise.
0
13:
Compute the estimated value function as
(*r(s)) = Ea (1xx) g ()x
(sk al] - TVe (Tp(-1sk)).
Update n (t-1) (t-1)
Ap
according
1
( (-1x)) + argmax LAup)
TTH (8k)
Dua (Tp(- (xp(-15),, xf1-1)( [sx))
Mau
(- (1
argmax
5ah (sx)
Duv (Tp(-1 sx), s 2 sx)), (3.2)
Ty(: 1x)) E
no
where 121, = {u AlAl;; Va E As, un 2 YsMx,a
(t-1) For all infosets not visited timestep I, let क (1) (- (-18) = π p(e)
(same for x(1)
15:
p(o)
p(())
We define the largest learning rate among all ancestor infosets of max max N7 (n, is the learning rate of infoset s), and have the follow- ing theorem that establishes the best-iterate convergence of Algorithm to the NE ((n))
as v
(T.9).*) of Equation 3..1) with high probbbbbbbbblitt..
P2
Theorem 3.1 (Informal). Consider Algorithm I
When T S SCC.F where CT is game- %
dependent constant, and 7) is smaller than game dependent constant (formally defined in Ap- pendix Fb for any E S, we have the following guarantee with probability 28.
T
+ō (VTloS) 1
D D (n (7)) ( δ
n.T .EB
+ō min.es 17
(3.3)

---

Published as a conference paper at ICLR 2025
The Ô notion hides the logarithm T. The proof and the formal version are postponed to Appendix Theorem 3.1 gives a high-prue boobbbbbayiilityy upper-bound on the cumulative Bregman divergence. By letting 7 (1/vVT) for all infoset E S, the right-hand-side of (3.3) is bounded by Ö(VT). Therefore, it implies that Ei= Pen (1(t)) (x*()) is upper-bounded by Ö(VT) with probability 1-26. Then, there must exist some 1' (7' that Dam (anllnnt) . Õ(1/VT), because the ): 2,3, ... ,T] must be bounded by the average, which is Õ(1/VT). Therefore, by computing the exploitability (the expected utility confronting best- responding opponent) routinely, we can find an approximate NE (Liu et al. 2023) of the regularized game. Moreover, according to Lemma Liu et al. (2023) Lemma D.I.), the exploitability of the regularized NE will be bounded by ((T) in the original game so that our iterates will also get a low exploitability in the original game by fixing to be small or anneal it as Liu et al. (2023).
minimum over { {D (pelt)))
4 ANALYSIS
In this section, we provide the proof sketch of Theorem 3.1 Section 4.1 introduces some necessary
notions and properties for the analysis. Section 4.2 shows the convergence of OFR under full- information feedback (traversing all infosets at each iteration), and Section 4.3 generalizes to the stochastic setting Section
4.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 (s, TRA, For each E Ass (we will use ((
CF(") (s, a) instead of CFT (4) (s, a) and μ! instead of u of counterfactual values and the feedback is.
as the shorthand notion), the relationship
EnerMe (0) (o2(1)) (o2()))))))()))))))))))))))))()) (s,
(0) (s, is Q-value
(s)
(s.a)
( (s, is trajectory Q-value
(4.1)
(o(a)
(s,
(s, is counterfactual value
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 CF(1) (s, a). we need to divide the reaching probability (*) (a(s)) of s, which can be extremely small and thus induces large variance.
In the following, we will write CF(!) (s, a) (1) (x) a) and m (1) is different for different types of (s,-) according Equation 4.1
Note that the value of m in most cases depends on the strategies that are produced by the algo- rithm; hence, there is some circularity in the dependence between the properties satisfied by m and those satisfied by our algorithm. To break this circularity, at the heart of our correctness proof
(t) that arises from using our we will verify and leverage two key properties of the sequence of ms algorithm: boundedness and stability, as detailed next.
Property 1 (Boundedness). For any t E [T] and E S, we have m E [M1. M2] where 0 < Mj < M2 < +00.
Property 2 (Stability). For any E [T 1] and E S, define the largest learning rate among all ancestor infosets of 8 as yn = maxic(2),ees max (.)) Ys, where n is the learning rate of infoset s', then
m 1) m
< S 1/a anc
(Additive Stability)
(t+1)
mg
1
< nnc.
(Multiplicative Stability)
(t)
m.
7

---

Published as a conference paper at ICLR 2025
Property will be satisfied by enforcing (-1s) > Yo,, for every S, where % E (0, 1] and A [A,l are specified in Appendix G.2
The proof that algorithm produces iterates that
satisfy Property 2 can be found Appendix C
4.2 CONVERGENCE WITH FULL INFORMATION FEEDBACK
QFR runs variant of Regularized Optimistic Mirror Descent (Reg-OMD) (Liu et al. 2023) algo- rithm to update the strategy in each infoset. For notational simplicity, we define the reach probability
(h)) The update rule of opponents to infoset S as p " p(aa(() (s) EeEsMe(h)) p-()) (33-p(s) m(a)
(t)
Teost To (Tpc)((10)) -q (s. TH p(o) T
(())(11))=
argmin
we (T)()))11))
m x-11)
(Tp (l) (-1s)
(4.2)
TH m())
(-1s) argmin p())
(=)) (s.)
vs (1p())))1))
m!
"26) (
Da (Tpco)) (), p(a) (t)) (-1s)
T
where A 1AA,) {u E AlAil; Va E A,, ua 2 YoMs.a and w/ is the regularizer chosen for in- foset s. Here (s. can be the trajectory Q-value, Q-value, or counterfactual value associated
with (1), When (s. is the trajectory Q-value, (4.2) is the full-information version of (3.2).
By analyzing the update rule (4.2), we can get the following inequality. For any s E S and strategy (p(s) (s) A have
TT -P-)) (s)re (T 6)) - -T -p (s) (-pes))) ())
-), p(ss] ()ss) (-
m ((t
TM (m)))s)
(T (1))))))))0))))))))))))))))) (-1()) 0(n.) 2
(4.3)
1 7
Then, since m m (1-1)
(t)
Om 1 < -p < - Enes Mo(h) when vy is
smaller then by small enough constant (please refer to Appendix E for details). Then, by applying the generalized regret decomposition lemma (Liu al. (023) (details can be found in
Lemma E.3 to Equation (4.3). difference of "p(s) and Tp(e) an infoset s can be extended to
(t)
the difference of the whole game. Specifically, by letting
(n* (a") (N.) (M1--13 -rr)) Ar-
(wDl (of' .=23) "!! (ef .x23)) + (i (P (
and diff, similarly, then the summation of the left-hand-side of Equation (4.3) over all infoset S is equal to is equal to
Σ diff, (f(tn)) ,0 + diff, (μ (mm)) (1) 2 O.
(4.4)
The non-negativity is because (((r)) is the NE of Equation 3.1 By combining
(4.3) and
4.4
we have
0 5
(r(s)
T7
Σ
(o(h) Σ Dep (1) (1x7))
p(e) (-1s)) + O(n.T)
1
2
7l
hEs
T
(0)
min SES
(h) Σ
D u (1 1 (
O T) + 0 sES
minses Tl5
hE#
t=2
8

---

Published as a conference paper at ICLR 2025
(a) is by Lemma 4.1 in the following. By rearranging the terms, can get an upperbound on Ei Dam (an(uue ((TT))) ())
Lemma 4.1 (Lemma D.2. Liu et al. 2022)). For any strategy 1=t 1 E IT and regularizer
w.a A A R for each infoset 8 S, we have
Dun (p 11
Σ (o(s)
s), (-)s)((s))
(4.5)
.ESS
For completeness, the proof of the lemma can be found in Appendix E.1 Here is the full theorem.
Theorem 4.2 (Informal). Consider the update rule (4.2) and (s, chosen to be counterfactual
value, trajectory Q-value, Q-value. When Ve < where C is game-dependent constant,
7he and 7/s is smaller than game dependent constant (formally defined in Appendix E for any E S,
we have the following guarantee.
Dan 2=
#0
max n.. #ES
+ +0+
(4.6)
minlggs 1)
The proof and the formal version are postponed to Appendix Therefore, by choosing 7/s
θ VT for any E S as in Theorem 4.2 QFR enjoys best-iterate convergence with full-
information feedback.
4.3 CONVERGENCE WITH STOCHASTIC FEEDBACK
We complement the results of Section by showing that the best-iterate convergence guaranteed by QFR is still guaranteed when only visiting trajectory at each iteration. The proof utilizes standard concentration inequalities, incurring an additional sublinear cost caused by the noise incurred from sampling, recalled in the following lemma.
Lemma 4.3 (Generalization of Proposition in Farina al. (2020)) Let M, M be positive
< M for any u' E C for any t E [T]. where a convex set. Then, if for any u, E[f(" f F(2),
stants such that ( (u) (ux)) S M and
(w) (() (u')
f = (u) and (9) is deterministically influenced by f(z), f(z) ... f(t-2), then for any 8 E (0. 1) and E C,
have
Pr
Σ (Fl)))) (w) 5
(w) (w(()) (M + M) 2T log 2og
1 --
Next, we will substitute the following values into Lemma 4.3
(u)
pis) (s(s) (s. ), Tp (t) to (o()))(())) (8, ), (o w (u)
1
Tp- pps) (s)
1 (u)
is visited timestep /
(m))
Otherwise
The proof of 7!0) being an unbiased esti- Then, Equation 4.3 can be bounded by (-[s))). which can be further bounded by analyzing the update-rule Equation (3.2). The analysis is similar the one in Section 4.2 and can be found in Appendix F Finally, we have Theorem 3.1
where g(t) is defined in Algorithm
mator of f!t)) is postponed to Appendix
Σ. ((0)) (-
(T (T - p(x) (T (-
5 EXPERIMENTS
In the experiments, we apply QFR in 4-Sided Liar's Dice, Ledue Poker (Southey et al.) 2005), Kuhn Poker (Kuhn 1950), and 2 Abrupt Dark Hex. The learning rate the same in all infosets,

---

Published as a conference paper at ICLR 2025
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.) 2023), there is no theory for convergence when using trajectory Valuuue and Q-value feedback, while OFR has.
In order to pick hyperparameters, we performed a grid-search for QER and MMD on learning rate n), regularization 7, perturbation y, and the regularizer is either negative entropy Euclidean distance. For BalancedOMD (BOMD) (Bai et al. 2022) and BalancedFTRL. (BFTRL) (Fiegel et al.) [2023). applied grid search to the learning rate v and fixed the exploration rate (IX parameter) to 20 as suggested in Fiegel et al. (2023). For the outcome-sampling CFR / CFR+, we also applies grid- search on the exploration parameter. The details of experiments, the comparison between QFR and baselines with full- full-information, and the ablation study of OFR when the strategy is approximated by neural network, can be found in Appendix H
4-sided Liar's Dice
Ledue Poker
Kuhn Poker
2x2 Abrupt Dark Hex
10"
100
Exploitalility
10
10
10
10
10
10-22
500
500
500
1000
1000
Iteration (x 1x
Iteration (x
Iteration (x 10"))
Iterntionn (x
<100
MMD
QFR
BOMD
BPTRL
Counter feodbock
Traj-Q foolback
Figure 1: Exploitability of Algorithm I in 4 benchmark games. We can see that QFR outperforms oumpone-sampling CFR / CFR+, MMD, and BOMD in all games. It outperforms BFTRL in all games except Liar's Dice. For each line, we repeat the experiments 100 times with different seeds.
The experimental result of Algorithm i presented in Figure 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.
Figure D shows that QFR outperforms outcome-sampling CFR, CFR+, and BOMD in all games. Moreover, QFR outperforms BFTRL in all games except Liar's Dice, with a relatively small gap (QFR 0.174 v.s. BFTRL 0.167 in exploitability). The reason may be Liar's Dice is too easy since it can be solved within 50 iterations with full-information feedback (see Figure in Appendix H). Lastly, QFR outperforms MMD in all games.
The superiority of QFR over CFR, CFR+, BOMD, and BFTRL may be attributed to both the ad- ditional regularization (best-iterate convergence) and the avoidance of importance sampling. For MMD, QFR is superior due to the optimistic updates, since optimistic updates allow predictions of the gradients at the next iteration. The code of QFR and baselines for tabular games can be found in LiteEFG (Liu et al. 2024).
6 CONCLUSIONS AND FUTURE WORK
In this paper, we focused on the question of whether the following properties can coexist while solv- ing two-player zero-sum extensive-form games: (I) learning with random rollouts, (II) converging in iterates, and (III) avoiding importance sampling. These properties are standard desiderata in the reinforcement learning literature for single-agent settings, but have thus far eluded extensive-form games. The answer is affirmative, and we propose an algorithm, QFR, that achieves all of them. We hope this work can serve as a step in the direction of bridging the gap between reinforcement learning techniques and imperfect-informale teresting to investigate the performance of algorithms that are both sound and work well in large domains.
extensive-form games. In the future, it would be in-
10

---

Published as a conference paper at ICLR 2025
7
ACKNOWLEDGEMENT
The authors would like to thank the support of Siebel Scholarship and NSF Award CCF-2443068.
REFERENCES
loannis Anagnostides, Ioannis Panageas, Gabriele Farina, and Tuomas Sandholm. On last-iterate convergence beyond zero-sum games. In International Conference on Machine Learning (ICML), 2022.
Yu Bai, Chi Jin, Song Mei, and Tiancheng Yu. Near-optimal learning of extensive-form games with imperfect information. International Conference on Machine Learning (ICML), 2022.
David Balduzzi, Marta Garnelo, Yoram Bachrach, Wojeiech Czarnecki, Julien Perolat, Max Jader- berg, and Thore Graepel. Open-ended learning symmetric zero-sum games. In International Conference Machine Learning (ICML), 2019.
Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. Heads-up Limit Hold em poker is solved. Science, 347(6218):145-144) 2015.
Noam Brown and Tuomas Sandholm. Solving imperfect-informanee games via discounted regret minimization. In AAA/ Conference on Artificial Intelligence (AAAI), 2019.
Noam Brown, Adam Lerer, Sam Gross, and Tuomas Sandholm. Deep counterfactual regret mini- mization. In International Conference Machine Learning (ICMI.), 2019.
Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Tight last-iterate convergence of the extragra- dient and the optimistic gradient descent-ascent algorithm for constrained monotone variational inequalities. arXiv preprint arXiv:2204.092238 2022.
Shicong Cen, Yuting Wei, and Yuejie Chi. Fast policy extragradient methods for competitive games with entropy regularization. In Neural Information Processing Systems (NeurIPS), 2021.
Constantinos Daskalakis and loannis Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. In Innovations in Theoretical Computer Science (ITCS), 2019.
Gabriele Farina and Tuomas Sandholm. Model-free online learning in unknown sequential decision making problems and games. In AAAI Conference on Artificial Intelligence (AAAI), 2021.
Gabriele Farina, Christian Kroer, Noam Brown, and Tuomas Sandholm. Stable-predictive optimistic counterfactual regret minimization. In International Conference Machine Learning (ICML), 2019a.
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Optimistic regret minimization for extensive-form games via dilated distance-generating functions. Neural Information Processing Systems (NeurIPS), 2019b.
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Stochastic regret minimization in extensive-form games. In International Conference on Machine Learning (ICML), 2020.
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Faster game solving via predictive black- well approachability: Connecting regret matching and mirror descent. In AAA/ Conference on Artificial Intelligence (AAAI), 2021a.
Gabriele Farina, Robin Schmucker, and Tuomas Sandholm. Bandit linear optimization for sequential decision making and extensive-form games. In AAAI Conference Artificial Intelligence (AAAI), 2021b.
Côme Fiegel, Pierre Ménard, Tadashi Kozuno, Rémi Munos, Vianney Perchet, and Michal Valko. Adapting to game trees zero-sum imperfect information games. In International Conference Machine Learning (ICMI.), 2023.
11

---

Published as a conference paper at ICLR 2025
Côme Fiegel, Pierre Ménard, Tadashi Kozuno, Rémi Munos, Vianney Perchet, and Michal Valko. Local and adaptive mirror descents in extensive-form games. Neural Information Processing Systems (NeurIPS), 2024.
Haobo Fu, Weiming Liu, Shuang Wu, Yijia Wang, Tao Yang, Kai Li, Junliang Xing, Bin Li, Bo Ma, Qiang Fu, al. Actor-critic policy optimization in a large-scale pnpperfect-iffommtiion game. In International Conference Learning Representations (ICLR), 2021.
Audrūnas Gruslys, Marc Lanctot, Rémi Munos, Finbarr Timbers, Martin Schmid, Julien Perolat, Dustin Morrill, Vinicius Zambaldi, Jean- Ccan-Baptiste Lespiau, John Schultz, et al. The advantage regret-matching actor-critic. arXiv preprint arXiv:2008. 12234, 2020.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International Confer- ence on Machine Learning (ICML), 2018.
Samid Hoda, Andrew Gilpin, Javier Peña, and Tuomas Sandholm. Smoothing techniques for computing Nash Equilibria sequential games. Math. Oper. Res., 35(2):494-512 2010. doi: 10. 1100.0452.
Shengyi Huang, Rousslan Fernand Julien Dossa, Chang Ye. Jeff Braga, Dipam Chakraborty, Ki- nal Mehta, and João G.M. Araújo. Cleanrl: High-qualit, single-file implementations of deep reinforcement learning algorithmms Journal of Machine Learning Research, 23(274):1-18, 2022. html
URL http::///// /mm
Julian Ibarz, Jie Tan, Chelsea Finn, Mrinal Kalakrishnan, Peter Pastor, and Sergey Levine. How to train your robot with deep reinforcement learning: lessons we have learned. The International Journal of Robotics Research, 40(4-5):698-75) 2021.
B Ravi Kiran, Ibrahim Sobh, Victor Talpaert, Patrick Mannion, Ahmad A Al Sallab, Senthil Yoga- mani, and Patrick Pérez. Deep reinforcement learning for autonomous driving: A survey. IEEE Transactions on Intelligent Transportation Systems, 23(6))4909-4499) 2021.
Tadashi Kozuno, Pierre Ménard, Remi Munos, and Michal Valko. Learning two-player zero-sum partially observable markov games with perfect recall. Neural Information Processing Systems (NeurIPS), 2021.
Christian Kroer, Kevin Waugh, Fatma Kılınę-Krrznn and Tuomas Sandholm. Faster algorithms for extensive-form game solving via improved smoothing functions. Mathematical Programming, 179(1):385-417, 2020.
Harold W Kuhn. A simplified two-person poker. Contributions to the Theory of Games, 1(417): 97-103, 1950.
Mare Lanctot, Kevin Waugh, Martin Zinkevich, and Michael Bowling. Monte carlo sampling for regret minimization in extensive games. Neural Information Processing Systems (NeurIPS), 2009.
Mare Lanctot, Edward Lockhart, Jean- lean-Baptiste Lespiau, Vinicius Zambaldi, Satyaki Upadhyay, Julien Pérolat, Sriram Srinivasan, Finbarr Timbers, Karl Tuyls, Shayegan Omidshafiei, et al. Openspiel: A framework for reinforcement learning in games. arXiv preprint 1XXXv:1908.000 2019.
Chung-Wei Lee, Christian Kroer, and Haipeng Luo. Last-iterate convergence in extensive-form games. In Neural Information Processing Systems (NeurIPS), 2021.
Mingyang Liu, Asuman E. Ozdaglar, Tiancheng Yu, and Kaiqing Zhang. The power of regulariza- tion in solving extensive-form games. In International Conference on Learning Representations (ICLR), 2023.
Mingyang Liu, Gabriele Farina, and Asuman Ozdaglar. LiteEFG: An efficient python library for solving extensive-form games, 2024.
220351 2
12

---

Published as a conference paper at ICLR 2025
Weiming Liu, Huacong Jiang, Bin Li, and Houqiang Li. Equivalence analysis between counter- factual regret minimization and online mirror descent. In International Conference on Machine Learning (ICML), 2022.
Stephen Mareus McAleer, Gabriele Farina, Mare Lanctot, and Tuomas Sandholm. ESCHER: es- chewing importance sampling in games by computing history value function estimate regret. In International Conference on Learning Representations (ICI.), 2023.
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chan- drasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point proolee Going the extra (gradient) mile. In International Conference Learning Representations (ICLR), 2019.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, loannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprini arXiv:1312.5602, 2013.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Neural Information Processing Systems (NeurIPS), 2022.
Julien Perolat, Remi Munos, Jean -aatittp Lespiau, Shayegan Omidshafiei, Mark Rowland, Pedro Ortega, Neil Burch, Thomas Anthony, David Balduzzi, Bart De Vylder, al. From poincaré re- currence to convergence in imperfect information games: Finding equilibrium via regularization. In International Conference on Machine Learning (ICML), 2021.
Julien Perolat, Bart De Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome T Connor, Neil Burch, Thomas Anthony, et al. Mastering the game of stratego with model-free multiagent reinforcement learning. Science, 378(6633,990-996, 2022.
J Ben Rosen. Existence and uniqueness of equilibrium points for concave n n-person games. Econo- metrica: Journal of the Econometric Society, pages 520-534, 1965.
Martin Schmid, Neil Burch, Mare Lanctot, Matej Moravcik, Rudolf Kadlec, and Michael Bowling. Variance reduction in monte carlo counterfactual regret minimization (vr-meefr) for extensive form games using baselines. AAAI Conference on Artificial Intelligence (AAAI), 2019.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint
2017.
David Silver. Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354-3333 0595544-35,,2 2017.
Samuel Sokota, Ryan D'Orazio, J. Zico Kolter, Nicolas Loizou, Mare Lanctot, Ioannis Mitliagkas, Noam Brown, and Christian Kroer. A unified approach to reinforcement learning, quantal sponse equilibria, and two-player zero-sum games. In International Conference on Learning Representations (ICLR), 2023.
Finnegan Southey, Michael Bowling, Bryce Larson, Carmelo Piccione, Neil Burch, Darse Billings, and Chris Rayner. Bayes' bluff: opponent modelling in poker. In Conference on Uncertainty in Artificial Intelligence (UAI), 2005.
Eric Steinberger. Single deep counterfactual regret minimization. CoRR, 2019.
Eric Steinberger, Adam Lerer, and Noam Brown. Dream: Deep regret minimization with advantage baselines and model-free learning. arXiv preprint arXiv:2006. 10410, 2020.
Oskari Tammelin, Neil Burch, Michael Johanson, and Michael Bowling. Solving Heads-Up Limit Texas Hold'em. em. In International Joint Conference on Artificial Intelligence (IJCAI), 2015.
Bernhard Von Stengel. Efficient computation of behavior strategies. Games and Economic Behavior, 14(2):20-246,, 1996.
13

---

Published as a conference paper at ICLR 2025
Chen- Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate convergence in constrained saddle-poin optimization. In International Conference on Learning Representa- tions (ICLR), 2021.
Martin Zinkevich, Michael Johanson, Michael H. Bowling, and Carmelo Piccione. Regret minimiza- tion in games with incomplete information. In Neural Information Processing Systems (NeurIPS), 2007.
14

---

Published as a conference paper at ICLR 2025
Supplementary Material
A ADDITIONAL 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
Convergence Guarantee. Most CFR-basee algorithms (Zinkevich et al., 2007 Tammelin et al. 2013 Steinherger al. 2020) only guarantee that the average strategy converges to an NE, though empirically some variants of CFR exhibit last-iterate convergence (Bowling et al., 2015 Tammelin itt al., 2015). Motivated by the success of Optimistic Mirror Descent (OMD) achieving last-iterate convergence in normal-form games (NFGs) (Mertikopoulos et al. 2019; Wei et al. 2021 Cai al. 2022), Farina et al. (2019b) first empirically showed that OMD also enjoys last-iterate convergence in EFGs. Then, Lee et al. (2021) theoretically proved that Optimistic Mulriplicative Weights Update (OMWU), an instance of OMD, converges in EFGs with unique NE assumption.
[hen,
Use of Q-Values To achieve last-iterate convergence in EFGs, additional regularization and op- timism are widely used. |Perolat et al. (2021) used that approach in continuous time, using coun- terfactual values under full-information (L.e., non-sampled) feedback. Lee al. (2021): Liu et al. (2023) achieved last-iterate convergence in EFGs using discrete-time updates, but both of their con- vergence results are based on counterfactual values in the non-sampled case. [Sokota al. 2023) MMD algorithm empirically observed convergence by using sampled (trajectory) Q-values in con- junction with entropic regularization, without theoretical guarantees. In this paper, we combine reg- ularization 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. (2009) proposed Outcome-Sampling Monte-Carlo CFR (OS-MCCFR), a variant of CFR which uses random rollouts to estimate counterfactual values. Later, Farina and Sandholm 2 Farina et al. (2021b;; Bai et al. (2022), and Fiegel et al. (2023) proposed algorithms that converge in EFGs with trajectories at each iteration. However, those al- gorithms rely importance sampling, which causes numerical instability due to the large range of feedback. ESCHER McAleer et al.] (2023) and LocalOMD (Fiegel et al., 2024) sample trajecto- ries off-policy. This is usually undesirable to uniform random probability, rather than focusing on those that are more likely given the policy. ARMAC (Gruslys et al.) 2020) and ACH (Fu al. 202I) support both Q-values and approximately- on-policy estimation, but like ESCHER and LocalOMD they do not guarantee convergence of the iterates. Moreover, neither of them is computationally efficient since they need sample many trajectories (possibly infinite) at each iteration to ensure that the estimation of feedback is totally accurate. Also, ACH does not converge the set of NEs, even in terms of average-iterate conver- gence.
it favors exploring parts of the game tree according
B FORMAL DEFINITION OF TRAJECTORY Q- Q-VALUE, Q- Q-VALUE, AND COUNTERFACTUAL VALUE
In the following, we will formally define trajectory Q-value, Q-value, and counterfactual value spectively,
For any 8 E S,a E Ag. the trajectory Q-value Q (s, is formally defined as,
Q7 (8, Ti (a(as)
Σ
(B.1)
M: (he
In (..I. (h) denotes the probability of reaching contributed by the chance player. We use
(U: H [-1, 1)a denote the utility assigned to each player each node of the game. We
15

---

Published as a conference paper at ICLR 2025
assume this is nonzero only at terminal nodes (nodes with empty action set) without loss of generality.
At the same time, define the Q-value, defined as the expected utility conditioned on reaching infoset s,
Q7
(s, = Ener Me (o10))
(B.2)
Typically, algorithms like CFR and its variants (Tammelin al. 2015 Brown and Sandholm, 2019) use counterfactual values as feedback to learn the equilibrium. The counterfactual value at infoset of player is the Q-value at s times the reach probability of the opponent and the chance player to Formally, for any E S,a E As, we can define the counterfactual value CFT as,
19 ((1'(11))) PclN)
(FT
E (h,,,
19 (8, 12 (o2(N)))
(B.3)
CFT is compatible with rolling out trajectories reinforcement learning usually does, since rolling trajectory includes the probability of both players reaching infoset which hinders extending algorithms to large games.
Also, for any E S1 and a E As (similar for player 2), we have
CFT (8,a)
(1(()( (s,
(B.4)
CFT (s) Enes Me Ma(h) (an (h)) (o2()))
(
(s,
M (a(s)
hEs
(B.5)
where equality (i) follows from (h) (s) for any S1 and h E s, which a consequence to the perfect-recall assumption.
C STABILITY OF TRAJECTORY Q-VALUE AND QALUE
In this section, we will show the stability of trajectory Q-value and Q-value, iee. proving Property P when the regularizer in each infoset s E S can be written as,
Gs E,EA, u 2 (u) = 2
(Euclidean Norm)
(C.1)
as (log Aal +.EA, Uh log un)
(Negative Entropy),
where a, > is state-dependent constant. We add log [A, the negative entropy to ensure the regularizer is always positive. Previous work (Kroer et al.) (2020) chose specific to ensure the dilated regularizer associated with vi is I-strongly convex. For generality of the result, we keep the a, in the regularizer.
Due the symmetry between two players, we will only prove that for St. Moreover, stabilize trajectory Q-value and Q-value, the learning rate need to satisfy the following conditions.
(A) maxXEs E(drad) Vo S 1/s for any E ESS [2]
(B) 6n max [llulll> T a max || (s, 11ob and its upperbound is given in Lemma G.1
Mi log s for any 8 E S, where ||g/|
(C) Ts (2l1ello ra M,
+
log ) < 1 for any S
ensures that Σ (()te))CCoe)) n/ 2n for any S.
B (C) ensure that the update each
tteration will not change the strategy much.
16

---

Published as a conference paper at ICLR 2025
C.1 STABILITY OF TRAJECTORY Q- Q-VALUE
Lemma C.1 (Stability of me under Euclidean regularizer). Consider when v (u) (
=
de EOEA, u for any E S and (A) is satisfied. For any S and t 1,2, T, when
2
(0) is the trajectory Q-value feedback, have m
6 max Cdift S'ES
6 max Cdiff. s'ES
CT
C
(C.2)
?2
M
Proof. For trajectory Q-value feedback, for any E St
m mm(+1) m6{
1
Mi (o(s))
1 (o)))
pi (o()))
pi (a(s)
M (o(s)
II( "1
(a' (s)) Ils of (a'ss')
[++ (o
Σ
#1 (( (8)
(s(sa))o(s))
In the last line, we use the fact 14 ((+1)) (a(s) Mi (0) (a(s)) 2 y, and
II (s)))))((s)
(1+1)
(a
(a'l
II
" (d'(s')
11
(a(())
II (a)(())))
( (a' 1
(
(a(s)) 1 (o(s))
+ t (T()s)
II
11 (a'18))
II
1 (a'18))
(s (a(a()))()()))
(a(())
< | (a(s)
x (9) (a(s))
II
ক (
II
+
(o((())
(o(oa))
We abuse the notion of क (a)s)) as mi 8') and (a(()) o(8) given (()) = (s/,a').
By recursively applying the process above, we will get
II
m (
II
(" S
Σ
((t1)) (a' (s''ssss)))))) - -100) (
m
(s)()
(o)a)))((s))
Lemma C.2. Consider the update-rule clidean distance, we have
When we choose كربج to be negative entropy or Eu-
100 (.1s) (+) p(s)
(11))
(++1) (-1s) ((1)
p(e) (11) < Crditt ns:
(C.3)
p(a) p(s)
where
2 22|g|l 0c
+ ra. log 1 ;
Negative Entropy
diiiff
a,
Mr
(C.4)
[d
|gll
Euclidean Distance.
Mi
17

---

Published as a conference paper at ICLR 2025
The proof is postponed to Appendix G.3
By using Lemma
C.2
have
m m
Σ (of (e(aa'([oa))
(d - (d'
Σ
(1 (1 (a') 18') 1 (d'ls')))))))))))) + m1 (d (o/d(18)))))))))))) =1 (d
(a(a)))
(a' 5))
Σ
Cat T7--
72
(o)()))
At the same time,
m (+++) 1)
3 3 (d) Ct "/s M
1
((+1)
m!!/
m
(e) ms
(1)
ms
Therefore, C, 72 msx Cddift and C 6max,'es Cdiif MMM,
by (A)
Lemma C.3 (Stability of m under entropy regularizer). Consider when (
are satisfied. For any E S and = 1, 2, ... T, when m² is the trajectory Q-value feedback, we have
Os (log A.I + EaeA, Uh log ua) for any E S, and
(A)
B
(C)
22]g + M. log +
12 maxyles
2 21gll Oss'
+ T log ) (C.5)
C
a,'
C/
12 max s'ES
7
Mi
Proof.
pi ((+1) (a(s)
mg m1(+1)
mb!
M (o(s))
P1 (++1)
(a(s))
(a(s))
1 (o(s)
We will then use the following lemma which shows the multiplicative stability when using negative entropy regularizer.
Lemma C.4. When v satisfied, then for any S, E 8, 1,2, ... T. we have
(log AAl + Σ Ene A, log u.) for any S.
A
B
(C)
are
( ( 11 (h))
-1
P2 (b)
(++1)
2 12lgglo
T log +
41 10 (2)())
S 12
ane
max
s'ES
O+''
Mi
(C.6)
The proof can be found at the end of this section. Then, for any E St, we have
(++1) (a(s))
-1 12 maxves
+ x
log
(t+1) (((et))
-m!
a
Mr
(+
(o(s))
Pi (a(s))
(8)
[t+
(o(s))
pi
12m ane max
21lalla as
+ M,
log
7
12 max, c 22llllas
s7, log :))
Therefore, C
Similarly, we have Co 12 maxves (2lgg) + Mr log 4
18

---

Published as a conference paper at ICLR 2025
Proof of Lemma C.4 Firstly, invoke Lemma C.3
Lemma C.5. Consider update-rule (4.2). When (u) = as (log [A| + +LEEs. uo loguo) for any
8 E S, and
[B) satisfied, for any 8 E E. E A, and & 1,2, , ,
2 1l + Tas log 1))
n (a|s)) (a)))
4 as
(21lalla +
Tas log
1)
exp
(a (()(ass) S exp
M1
M1
(C.7)
C
22|lll
Tak
log ))
(C.8)
Mi
The proof is postponed to Appendix G.3
By Lemma
C.5
we have
11 (o)
M1 (o1(1))
Il (
कं कf (d' (d'ls')
Io (N) को (d'ls)
[I को ( (d'ls')
II
x1 कं ((+ (a' (a'ls')
II a' af" (s') को (a' (s)
[( क| (a' (a'1s') (s)
ar #1 ((+1) (a'ls') sy)
2llalloo + Tas log 11
sexp
3
as'
Mi
2 211410a
log 1
1)
Σ
< exp
3 max YE
+ M1
0²'
(s'sa'E
2 2||
7 log
1)
exp
max S'ES
+
rnauc
Ogs'
M1
2 2||lll
1
<1
12
anc max
log
7/
s'ES
Otg'
M1
At the last line, the fact that ea 2x for E [0, 1). Similarly, by using 1 S e", can also get the dower-bound 1 - 617,nc max
221 a, + log
C.2 STABILITY OF Q-VALUE
Lemma C.6 (Stability of m² under Euclidean regularizer). Consider when 3 (u)
6e EoEA, u for any E S, and (A) is satisfied. For any E S and = 1, 2, ... T. when
2 (t) is the Q-value feedback, we have
C/ = 6)sl
C s) max Cdif
max Cdiff s'ES
(C.9)
s'ES
M1
where |s| is the number of nodes infoset
Proof. With Q-value feedback, for any E Si.
m (1+1)
m0)
Σ (e(h)((g (t+1) ((-1))))))))))))))))))))))))))))
(a2(h)) ((
- 12 2 (oz(h)))
hev
(e(h)
112
((+1) (o2(1))) 212 (o2(h))
<|s| max
112
(1+1) (o2()) - 1 1 (o2(1))
hes
19

---

Published as a conference paper at ICLR 2025
In the last line, |s| denotes the number of nodes in By similar argument as in Lemma C.1 E 8, we have
for any
(++1) (o2(h)) P2 (o2(
22
tet1) (d'
II
12 10) (a'ls))
(ox(A))
Σ
(e+1) (d' (d'ss') - T (a' |s')
(e' a (o)(
Σ
(
( (d'18') - मे (a') ss)) + n2
(a) (d'ls') =2 =((+1) (a'1s))
(sf (12(()))))))
+ 2 (a' (8') 12 (a') 85)
33
Σ
Cdift As--
(o)(
Therefore, ma (1+1)
-m
(1)
I 3/s maxhe: (o) Cdiff no. Similarly,
mg
(++1)
(1(++) -m(")
3/s
Σ
difff Tlst
(t)
(t)
M1
max hER
ms
(oz(a))
Finally, CT = 6|s] max Cgftt and C².
6]s/ mls|max,res Gdif Mr
according to (A)
Lemma C.7 (Stability of m (t) under Entropy regularizer). Consider when o Os (log A, EaeA, Un log ua) for any E S, and (A) BB)
(C)
satisfied. For any S
and 1,2, ... T, when m!)) is the Q-value feedback, we have
(2lggll + Mi
log 2)
22lg
+ T log ;) (C.10)
CT = 12M2 max
C² = 12 max
s'ES
agy'
s'E8 as
M1
Proof. With Q-value, for any s S1, have
(++1)
1 = Ener Hc(h) ((+1) (oz(h))
my
(()
Enes Me (h) (az(h)
By Lemma C.4 we have
(1+1)
(o2(h))
2 2l1
+ T log ))
< 1
12n e'ES
max
12 (02(h))
as
Mi
Therefore,
Eneo (c)pp (1 (t (o2(t)) Enes ((
EnecHe(h) (1+ 12m ane max
21|g
+ T
log )) 2hS (o2(h)
a,
Mi
Ener (a(h) (o2(h))
2 12lllloe
log 1
<1 + 12 max
+ M1
eE
Similarly, we have
Enes (t+))))))))))) (t+1) (o2(1))
2 2
log !
21 12
anc max
+
Eneo (h) (o2(h))
Ogs
Mi
20

---

Published as a conference paper at ICLR 2025
Therefore,
m((+1)
m
S
12
max
2|| 0g1
+ J log 2
Mi
At the same time,
1
(1++)
mn!
mm
(c)
ma
(++1)
1
I
1 121
M2
max e'ES
[2
+
log 5
m
Ogs'
Mi
D BIDILATED REGULARIZER
Dilated regularizer (Hoda al. 2010) is the foundation of previous work (Lee et al. 202 Liu
et al.
2023; Sokota et al., 2023) to apply mirror-descent and its variants on sequence- strate-
gies.
Recently. additional regularization has become a powerful tool for learning in EFGs (Liu
et al.
2023 Sokota et al. (023). Specifically, we can change the objective of the game to
max,,," T ell, min,,, H T Ell, (nT)) Au -Tb"h (x7²) + Tullla (m5²), where Tqilll ( (x²²)
the additional regularizer and controls its magnitude. By adding the additional regularizer, the objective becomes strongly convex-concave instead of convex-concave, and thus linear convergence
rate be achieved.
However, the dilated regularizer of player i E [2] is 16 (p.)) Eses, 14.h (o(s) (T:(111))
which only counts the reach probability ni 14," (s)) of player i. Therefore, when sampling a tra- jectory, estimate the additional regularization, importance sampling is needed 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 is defined as,
Th 4
Σ (o((((s)) SES:
Σ [uo(tt)p((a((1)) hES
(-)(()))))
(D.I)
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 Th (1T²) .120) is still convex with respect to p and 2²² individ- ually. This can be inferred from the fact that the dilated regularizer is convex with respect to jl (Hoda et al. (2100). By enforcing (- |) 2 V. for every E S₂ with Ya > 0,v, E A where v, has full support, we have 1uz² (s, a) 2 7 for any 8 E S2,a E Ass where 7 is a constant. Then, we have the following lemma.
Lemma D.I. For any 7,7 > O. the Nash equilibrium ( tion (3. is unique.
(41 (Ti))) (60)))) of Equa- ,10 ,
Proof. Let define FT (NTT 127)) = +
(UT) ,157) and 11 Wi (TTT,;?) - -V -V voll [l
FI (MT), ,12 = A AT + TV pTz v (4T ,,,)
TV
11
2 (1TT,,133)
For any i E II, have
FT FT . 12). p
Apra +
+TV +TV,,"" pi witl (1r 11²2 - T
ni Pbl (MT 13)), -177
Ap?
uu 1 - + + + mu (ججيع
=
vor
Tull (147 Ki )د + Till (1r مدم
Tul (uT مد
+ TV I1 (#t ,172).
The last line uses the fact that ll (MT²) n1²2) is linear with respect to n
21

---

Published as a conference paper at ICLR 2025
The counterpart of μ22 is
F2 (HT : 12 ,, 12
A pi VV M2 2h
I1 (Mi
u1 2
~V μ uu Th (M ,122), P12 11
A pi 112 112
To2
T2 (4s ())
(122 ,
Pbi
Tu (MT) 1 H2 + T4
11l (MT |
To/ (1r ,/ا ) + Tu (pT .,-))
Let nT = ( ) and F (1*) (FT (MT 22²), FI
Then by taking the summa-
tion of equations above, we have
FF (1" 14" 1
-- - Ap + (11 Auz + + Di (-022) (1i 2i 11.1)) + DD
(122 1
Vol (m])
+ +T/bi ,12 122) Twb (41 ,122) + Tub (11
11 ,1122) ) Tubi (uTT,112 ,112)
Then,
(T(1T)) FT 1. n
,47
(12 (22
12
th (115))
Mh (MT) ()
( p2 )
(1 Hi
+
Voi (122)))
Vol
Since y=, pTT = 9 D
Poi (: ) 14 147
2 mimnne Me (h) (1 14 oi
by Lemma 4.1
Moreover, there exists M > so that Dam, (MT', ,nT 2 M
| - Mi"
according to Hoda
et (2010); Lee al. 2021 Therefore, the NE is unique when 7,7 0 by Rosen (1965).
E PROOF OF THEOREM
Theorem E.1 (Formal Version of Theorem
4.2 Consider the update rule 4.2 and (s, is 2nt chosen be counterfactual value, trajectory Q-value, Q-value. When
S <C7, where CИ
"/- (C) are satisfied, we have the following guarantee.
Ener (e(h) for any s and (A)
B
20,
T Σ Dun (oo u )
2m2
T anc 11 (1 Σ (ol (cl + +
Σ
(m - (A (-13))
min.ss
Enee Ma(h) sES
Cillfl H (trd)) (o(s)) 11gl n.MoT
(E.1)
Ty minnes Ener Me(h)
NEG
2
ms
(.t (o()) D3 (- (r2)) (-1s), = ( (1))))
Ty ryminess Ener (h)
EES
where C-º denotes C, associated with Q-value, regardless of which feedback type (s, is.
Proof Sketch. The structure of this section will be as follows. (i). By analyzing the update-rule 4.2)). we can get the difference of utilities between our strategy π (1) and an arbitrary strategy л at single timestep t in each infoset. (ii.. By telescoping and using the smoothness (the strategy as well as the feedback will not change much at each iteration) of the update-rule, we can further get
an upperbound the cumulated difference. (iii). By decomposition lemma (Liu et al. 2023). the
22

---

Published as a conference paper at ICLR 2025
difference in each infoset can be extended to the difference of utility in the whole game. Then, by rearranging the terms we can get an upperbound on the cumulated distance to the NE.
Firstly, we will use standard analysis of the update rule (.2 For notational simplicity, we define (1)
1 "-pts) (+) = Enes (e(hh)usp((e (()-)()((h))
Lemma E.2 (Generalized from Lemma C.2. in Liu al. (023)) ) Consider the update rule in (.2
When / is strongly convex, then for any Tpts) (- (s) E [A. and 2 1, we have
(0) Tu
(e)
p(s)
(2) p(c)) (.16)
TM m(s)
(-p)))(1ss)
7
-7
(1)
m
(8)
1
p(o)
v/ (+)))))
p(s) (-18))
+ T)&T
(1-1)
m!
m8
(8, 1); mp(s (-18) Tp(o)(118)
(t)
+ 1/s
TH (2)
p(s) (8)
<D 22 (TT(s) (-1 [s) = (-1s) - (1+ +
) o2 (-)))) p(s) (- (-1s)
ms (2)
THe ((-1)
p(a) Dog (T (66)) (-1 (ss, x({) (11s)
- -11+ + 1//-
ms
(t) - D p(s)( (.1 s), x (1)
(: 5)) 77 (q" - (0) -
(0) = (116)
p(s)
The proof is postponed to Appendix
E.2
Multiplying m on both sides of Lemma E.2 we have
(1)
TATH (1)
(T)))) (: [s) TT p(s) (s) (T(()((1s))
(2)
(
p(s)
ms (1-1) - (s) - (s)
ms
(-1 {)) (T))))
Ma) (-1s))
+ n,T
+ n.m! (1) (-9 ) π p(s) (-1 s) (p(o)(1)s) 1s)
[m (1) Dup (TM(s)
8), R1 (1)
[1)) - (ml") + no -p(a) -p(s) uy (Tpc))))))) =(),))))))))) (1)))((())))
p(s) (-1s)
p(a)
- (ml) + noT
m
1)
(s) D موو ( (
15) M/ (-1s))
(1-1) p(0)
p(a)
m
- -m{9 a (T p(o)
- 8) p(s) (: 8)) + mm! ( (5.0 (x. 22 x p(s) (.1 (11))
(1)
By noticing the fact that p(s) (8) is equal to m associated with Q-value, we can use Property and Property and get,
mia (1)
m [1]
mm (c-1) (()())))))))
(t-1)
(8)
(0) (s)
<
1 [ (0) + p (x)()())) (8) 1100) (l(pee)())
<C/
1/ anc + C2 1/an
We also use the fact that 1t p(s) (s) S in the last inequality. We use C-2 to denote the C₂- associated with Q-value for simplicity. Furthermore, by using Lemma C.2 and Hölder's Inequality, we have
(t)
( (-))(s)) -) - " (s. -,, m(s) (-1s) s) - (-1ss)
< (8.)) n (s, - |||= 1 (-) -(0))) (- (-1s)] < 2C |/ ne
23

---

Published as a conference paper at ICLR 2025
where |/ [M,,s (s.))
By telescoping and non-negativity of Bregman divergence, we have
Σ (OTTH p(a) (8) (5) (()) 7OTH (p) (Tp (1()))11)))
+ 7am! (t) <-q (0 (s. )), x p(e) (: 18) - [p()){-1s))
T
m (t)
m (f(-1) n 4pto) (s) Das (T)(o) (l)
+ (c! + +0
r/amc 175
n
w (TT (t)
p(s) (-1s)) v (1 20 10lloc nh
+ m (1) Dag (-p())-110) (), क p(s) (1) (-1x)).
① can be upper-bounded by Cg 1/ an Ty Ener 7,73 Enew (c( by Property 2 and N/ letting
11 1 205
Ene, Mc(h). By non-negativity of Bregman divergence, have
Σ MoTU
(5) (m (.) (.11)) noTH (s) (Tp())(118)
-p(s) p(o)
+ nam!! (-q
(s, :), p(x)
(1)
( (8) (-)))((1))))
5 To Enes (h)
T
Dog (Tp(s) (:15), [() (-)) s))
2
t=2
+ (c% + 0)
anc Σ
d p(a) (-1s) ( ( (-1s))
1=1
+ 20.lift ||all50
MM + m Das (Tp(s) (0), (()
( ()).
p(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 E.3 (Lemma 5.1 in Liu et al. (023)), Let 1I, x XI2, the polytope of all valid sequence- form joint strategies. For any 1 11, p1 Ilg. we let nM "uT.142 E II denote the joint strategy, a (= II
" (MT + "i (HT²), and F(u") (-App A p. For any
u()) (2)), .... (T) p E II and 0, we have
G(Tiill Σ (F(m()) -1*) + (1)) (1T)
nr (a(s)) (5: (1T (s:Tp())
(E.2)
SES
R max G (T), (μ1
< max Σ Lnt (((()( n SES
(E.3)
n ElT
24

---

Published as a conference paper at ICLR 2025
where
Be (s, = Σ (o((s)
W/ (Tp (-)
(E.4)
10 (s,a)
(sr))E
T
(F(()) p(s) (8, + r =B (t)
p(s) (s. (5))) (.)))(-1s) I)(o)(11s))
=
1=1
Tw (sT (t)
(. (-18)) - - (
(F.5)
(s)
max
G (s: (s)s))
(E.6)
p-o (+)))AAA))
By using Lemma E.3 we have
Σ (a(s))
(TM (s)
(m (1())))))))))))))))))))))))))))
SES
+ +m (-q (s) ). (2) (1ss) - "p(c) (115))))1))))
[1 ( - -1ah) T App" + (uf)) T A (112) 112 m
M (u(1) (0)) vill (uiT))) ,1 (H() .12 + will (u) (u(tr))) (1
(m)
(22 will (m1") (1) (22 will (41 22) will (u1²) (0) 2n ((m)))))))
T
Σ (uft - -ma")² A + [4] ( (n - μ )
|| (()));)) + will (ml ( |4| ((r-))))) - wil (Af .42 (mbm))))))) Mi (ul)) .p4 (.)t))))) w (p) (m)))
(UM (ufte)) ,1b)) 2 (TM)) p2 ())))))))))))))))))))) wht (w) (())) pl (((-)))))) will (p( (1))
20.
The last inequality is because 4 (T,)),
NE of 12 Ell;: 22 (1TT) A To - -vpi (MT ,155)) + +Tuh (MT 1122).
the Tl
max,," 1, eTTy oP' by min
111
Therefore,
0 0 Σ (o())) Σ
TH (1) (po (T (-
mes (s)0 p(0)
SES
+ m!!!) (-q :), x p(o)
(.18)
x p(s)
(- (-1s))
T -- mininsss EnEs (h)
(m)) (a
sa (.)))))))1)))) M(a) (-1s)
2
2
(o. 05 T1/ anc (1)))))())
Σ
(= (4)
p(s) (11))
())
(1 (1+1) (-1s))
p(a)
SES
2
Cdiff ((())) (o || M2T
#ES
ms (I)
s), p(s) (11s)))))) (11))
'It can be easily generalized to bidilated version by absorbing the reach probability of player 3 and the chance player into ف/ for Up and player p. For W since it is linear with respect to ng" it can be combined into the counterfactual value.
25

---

Published as a conference paper at ICLR 2025
(i) is because f (T7))* is the NE of the regularized and perturbed EFG. Then, by rearranging the terms, we have
T
Σ
D wn (n
(o )
t=2
T
Σ>
( (a(s)) (= (1p))) (-16), (()(()))
1=2
minses Ene, (h(h)) <
E(' +5
and 10
( (a(s)) Σ (T (.
(11)))
4 myminses Ehea (c(h)
Cdlitt (T (o(s)) Ilall M27
2 myminges Ehea (h)
ma
1 (.)))
( (o(s)) (1 (-16), (
1/
The first equality is by Lemma 4.1
Now, we achieved best-iterate convergence to the regularized NE μ ((72))) in terms of Bregman divergence.
E. PROOF OF LEMMA
By definition of Bregman divergence, we have
Don (p" 1²*) (H")) (1*))) (u"""("";""""" =²²))
For notational simplicity, " for any E S. E A., the gradient V n (1) is
(s) (7ts) (s. a).
Since 2i'
Exes 1rah (s()))
equal
(5
( (1=((((11)
(=1ss))) (**(0(6)))
V (x.0))) (u*) (M*)))
Σ
VVa
10th (o(s)))
S'S:: (s)) (s,a))
a / 1 (s.
11ah (o()s)
Therefore,
(Vi""( (1* 1*
11 ( (T
(d(.))
Σ sES,aEA,
4 (s,
Σ
(
(
"
r'ES: ((.a)
1 (8,
11 (s,sa)
sES,
1r (s'..)
Σ
# (o((ss)
(E.7)
(a((0()
A, s'ES ((s)=
VWA (=((s-))
Σ Σ
1 (b..))
(F.8)
(+((((s))
sES, e'ES: ((8))
(s,
(s, V
(E.9)
11th (a(())))
Note that E.7 equal Eves 1t (a(s)) (s').
[+(e.)) ((*( due the uniqueness of (a(o))
26

---

Published as a conference paper at ICLR 2025
Similarly, due to the uniqueness of (ss)). (E.)) is equal to - E (v [- which is equal to the negative of E..9) and thus cancel out. Therefore,
( (..
(v (1 ( ),11)) = (1*))
Moreover,
(Vi (n )
1r))
(d'.))
E
E
1² (o(('))
(a(()(
sES,uEA, SEES: o(s)))
VV2a ( 10 (17)))))
(8)))
Σ
1² (s,
Σ
(07(0())) (a(s))
sES,nEA,
d'ES: ((x))=(s.a)
1 (s, 1ºTH (s
Σ
11 a)
SES.
[or(o(s)) (
(3,))
+ (v/22) 1
n² (s.-)
H (s.
(a(s)
()())) (a(s))
()(()))
SES
Therefore,
(1"),, 10T 1²))
TT Ap.z2 + ( T A1122 32 TD
Pal (1:12)) (19 ( + TD TD (1T+.) (1))))))))
Vol wol
+ 1122) + Tu (pT 1 .152) - TT/l (nTt,11) Tu Ih (MT), .1 ( Tu (14
E.2 PROOF OF LEMMA
Firstly, we introduce the following lemma.
Lemma E.4. Let C. be convex set and (1) argmin
{ (g. x) + roy + ,/ D (x, 20))
where &c is strongly-convex function in C and To 2 a constant. Then, for any e2)) E C, we have
(x - (x) + 17 (g x2(3))
(E.10)
<D (x) (0)) (1 + moo D (z0 xe(1)) - Dwo (2011) 201))
The proof is postponed to the end of this section.
Plug ar (0)
म (t)
p(a) (. (0))
((+1) क p(s)
(. 1)) (2) (1)c))11))00)) (0, 1,,00 10 -A.0
(m)) into Lemma E.4 with C A |del
Tサ (
Na. To
m
(1)
T/o (1)
Tp p())
(T (++)) (-1s)) - 17x
-p(s)
we (-s))
7
p(s)
m (t)
+ no p(s)
(1(ttt)
(-1s) pp) (:1 8), (s.))s
p(e) T (5)
(t)
<D (Tp()) (-1 s), ग ppa) (-|s)) -
1 +
TH
D Daa (T # (-1s)
m (2)
- DDy ( (
(-1s), (1)
p(.) (-1)).
p(s)
27

---

Published as a conference paper at ICLR 2025
Plug (0) = - (6)
p(a) (- 8), a1
T (1)
p(e) ( (), (11)), x2(2)
=pt))
(1+1) (- (-1s), -0(0-1) 1, = 1/2111
T4 -m (6)
into Lemma E.4 with C = A
ne: To =
m!
TH T/-1 (s)
TH (1-1) (5)
-pep
mi 1) U/ (TT p(a) (. (-1s) - 7/
v/ (T ( (-18)
17
mi m!
+ no p(s) (T) (-15) 8) - म p(o)
(-1s), -q (Q( (s,
THe [t- ( (8)
<D DD N2 (T p(s) (-1 o p(()) (-1s) - (1 + n7s
-v()
(1-1) ) (-1)) (1)
[ (- (-1s)
m
(t) (T p(s) (. 8), क (t)
(. 8))-
p(s)
Summing them up and adding 17s (gt - (()).)))))))))))).))))))))))))))
(. (0)
- 7.1 (1()) to both sides,
we have
17
-p-p
TH
10 (IT
(1)
p(s))
(.15) - -7
Tp
(t)
mla) (s)
2/ (-)(s)(-1s))
(E.11)
m3
m
(1-1)
(s)
(2)
+ T)&T(
p(a)
[v. (T p(a) (+18))
(F(tt))) (- (-1s))
(t-1)
Ms
ms
+ ( (s, ); Tp(()( (-)) (-1s) (.pc)((1ss)
TH (1)
p(a) (s)
<D ug (Tp(s) (.1 (18), = p(a) (.18) - -1+ + 1/4
) wa (Tp())(-15)) (t)) Dao
m (2)
Tu TH (1-1)
- -1++1 17s
p(s)
) (TT ( (-1s), (t)
=((s) (1|s)) s))
m (1-1)
- Dag (T((1) (t)
(. s), o (t)
(-1 + no ( (1) - - (s,)
p(s) (11s) = (1)))))()(()))))))((()))))111)11
p(s)
p(s)
Proof of Lemma F.4
Dec (x) (2) (0)) - (1 + 170) ( (ss((e (2)1)) - Duvo 20)0
= (2)) (x) - (VDS (2))) ) x,((2) - =0()) ))
(1 (1+m)) (ro) (x()))) (20(1)) - ( (T 2,((() - =0(1)))
(w 10 (z) ( (Fr (z) (1)) - =0(0))
(2000) - mTo
( (x(3)) + (11 (1
(z(((((0))) x,()) -,()))))(()))
Since
{ (00.0) m)) + (x))(())))))))))(())) + 17
1 (W8(z)) v)((((0)) - (z))) x -ax(00))) 2 }.
a: (1) = argmin
#EC
by first-order optimality, we have,
( 119 + (1 + 1750) - V (V) (2)))==11 -1(1))
(2)
20.
Therefore,
D Duc (20(2)),2x0)) - (1 + +1770) Duy (0(22),xx11) - D Desc (1) (0011),0(00) (0))
217O (20 - (20)) + g xx! (1) - x212))
28

---

Published as a conference paper at ICLR 2025
F PROOF OF THEOREM 3.1
When 2 % S TOy." for
Theorem F.1 (Formal Version Theorem 3.1
Consider Algorithm
any 8 E S, where CT.."
Ene (b(h)
and (A)
(B)
are satisfied, have the (C)
2C. (log T +log [S|+ })
following guarantee with probability 26.
Σ
Dan (fe (mo), )
4Cvislt
Culltt (1
11g1l M²T
vivis
(TT)) (a(s))
max
(2,
7al p(s) (o(s))
40 visit
(n))) (a(s))
max x. A S..
Dua (x, 3)
(F.1)
sES 17
4Cvisit
(119110 Txmux (1 ;)
[8] 2og 2T log
40
visit
(
8
n.
SES
log T' log HS|+ is the maximum gap between any two adjacent visits to an where Cvisit == 77t min.gs Enee (NJ infoset.
Proof Sketch. ()). Firstly, we show that the estimates in Algorithm are unbiased so that the conditions of Lemma 4.3 are met. (ii). By Lemma 4.3 and union bound, we can extend the result of full information feedback cumulated distance to NE after telescoping is still positive, we need to bound the largest gap between the timesteps two consecutive visits of any infoset.
the stochastic feedback. (iii). To ensure the coefficient for the
For any infoset E S, we define T, {1g G2 ..... }. where each 15 [T) is the timestep that uses unbiased estimators so that Note that for any u E N.. the expectation of the
along the sampled trajectory. Then, we will show Algorithm |
we can derive an upper-bound by Lemma 4.3 additional regularizer term is,
Pr T.)
(2)
= (4) p(o) (o(s)) (s)
3 (2)) (o)(ss
(o()
(c)
-TP Mls) v5) (u).
Let s(h) denote the infoset that the node h is in. For the original utility, suppose p(s) 1 without (s,a) for any E A. is.
loss of generality, the expectation of (t)),,
Σ
M 1 (a1())))) (o2(h')) ( (oa(t")))
(a 8) MEH: (ha)EN
Σ
(T((1)
1 (a 8) MeH (h.)EE
+
Σ
(H) (T)
पl (a s) MeH2: CM.
which is equal to (f) a) by definition.
By Lemma 4.3 and union bound, with probability at least 5, the following is satisfied for all infosets S.
Pr E T.)
(o) (u)) -u (a())
23 (()()) (s)) (u).
(o())(
29

---

Published as a conference paper at ICLR 2025
where v is the upperbound of v/g. which is max,es 2 when it is Euclidean norm and max,es 0g log [A when it is entropy.
Let's define to for notational simplicity. Similar to the proof of Theorem 4.2 for each & I [Ta] 1, we have
1oT (T) (-))))))) [8) T (T)()((-18)) + 7, (s (1:) (.1s) (o(o)(11s)
Tp(s)
De s), p(a) {)) (1 + (TTTT)D vu (T
(t--1)
p(a) (-1s))
[) (.) (.1))
(1+ 20 p(e)
n1 (7th)
(s, - q ) (8, p(o) (-18)
(-1)))
p(s)
By multiplying m
on both sides and telescoping, we have (o()))
11-11
(16 (T - us ( (s)
Hp(a) (o)s)
(05)
1
(- (s, (11) Tx(r)( ss)
+
pp(x) (s(s)
(1b)
n&T
Deg (Tp()) (.1))
(15)
(o)s)
( (o(s))
(o(s))
M2(a)
Meis)
pp(s)
+ 20 ||g|lc no M2/Tal +
Dop (Tpc)) 18), ( (11)).
(o))))
Since the probability of visiting infoset at timestep is at least 72 (h),
Pr 01 011--1 -/--1>> K.) S (11-5 -1-- x- Σ
S <exp(->2>> > (xa()>-Ena(t))Kk))) Ms)
hE*
hes
Therefore, with probability 1 8, all infosets s E S satisfies that for any 2 5 A: S log T+log [S|+log =: Kg. Then,
11 (Ta).
2 Ene, (c(h)
1
M&T
log T + log |S| log 3
(1t) p(s)
(x))
( (+t
(o(s)
(a(s))
(1
(a(s))
<0, 1/5
722 >iees (h)
1787
p(s))
pp(e)
log T + log |S| + log 1
C na
176T.
722 Σ nee Mo(h)
30

---

Published as a conference paper at ICLR 2025
Therefore, when ame 7y c (h(h)
the inequality above is upper-hounded by ReT 2-
20, (log2 2lloo +lo+ ;)*
Moreover, we can write it as (let 1, 1.2.+1 T + 1 for notational simplicity).
IT.
Σ
Dug (1)),()))))))))))))))) (()) (.)
k=2
pp(s)
(o(())
( (o(s))
p(s)
(o(s))
17. -1
s
Σ
Σ
NeT 2K,
Dug (.
ppe))
p(() p-))(-16))
(tt)
ToTY Enes (h)
T.
Σ
Dag 18),
(log T + +log [S) + +lg 1)
2=
@ 7, EnES EhEEMe(M) (h(
T
Σ
Dog (-)))
2 (log] T + +log |S| + +og
8)
1)
T, Ener (1)
T
(log T + log [S] + log ))
Σ
Dag (Tp(s) (15)) (1 (.15))
p(s)
2K,
max WEA
A.
Dup (2, y).
1=2
(i) uses the fact that for any t E [t,, 19,
1], T0o (-1s) = न p(s) (-1 (-13).
Then, following rest of the proof for Theorem 4.2 we finish the proof.
F.1 PROOF OF LEMMA 4.3
Let (u) = (u) - (u)))) - (Fil(()) (u(()) By the property of ( since (()) deterministically influenced by f(),, f(2), ,.. f(- f(,11,, frol (m(o)
f(--) =
(w) Moreover, E (w) 7(a,, j(a).... ji--]] = (u) for any fixed u E C. There-
fore, d(t) (u) is martingale difference sequence. Then, equality in the following.
apply the Azuma-Hoeffäiee in-
Lemma F2 (Azuma-Hoeffding inequality). For any martingale difference sequence x(1) (2) (TT) with ((t) E (t( b(+),, we have
2w alt))
Pr Σ
(1)
w s exp
(T
ΣT
(b(t)
Note that (t (u) S M + M. By applying Lemma
F.2
we have
T
2w
Pr
(w) 2 w S exp
E 4(M + M)²
Therefore, when taking w = (M + M) v
2T log J. with probability at least 6,
1 (u) - (w())) (M My 27 log g
2T
G AUXILIARY LEMMAS
In this section, we present the auxiliary lemmas for the theorems proved in the previous part.
31

---

Published as a conference paper at ICLR 2025
G.1 UPPERBOUND OF FEEDBACK
Lemma G.1 (Upperbound of Feedback (s, Consider the update-rule (42) For any timestep
I E [T], we have the following upper-bound on (s.-) and its unbiased estimator (8, :), no matter whether it is counterfactual value, trajectory Q-value, Q-value.
Mi al Dymma++ +1
Outcome Sampling of Trajectory Q-value
| =
min.es, Tallin
(G.1)
| Dylmaxx +1
Otherwise
Mi
where D max Phh) is the maximum depth of infoset and g.max is the maximum of the regularizer, which minacs [A.] for Euclidean distance and max log [Ag] for entropy.
Proof. When calculating the feedback (s, a) for outcome sampling of trajectory Q-value, need to divide the probability of choosing action a, which is (a](s) 2 mitlses, TaMa,a- Then, its upperbound is that the full-information feedback setting divided by the constant min,es..e.A "."..a- Therefore, in the following, we will focus on the upperbound of (s,-) in the full-information feedback setting.
In the following proof, we only consider E S₁ since player 1,2 are symmetric. Furthermore, we only need prove the upper-bound above when (s, is Q-value, since by definition, the Q-value Q (s. a) Ene, dhe (hij,, (a, (o2(h)) Q7 (s, a) (similarly, it is also larger than the counterfactual value).
Q7 (a.0)
Let s(h) be the infoset that node h is in. Firstly, when 0, which means only considering the contribution uf to (s, for every S1, have
Q (s)
Σ
E her Mo(h) (oi(h)))
M: (h
Σ
Pe ((
Ener no (h)) (or
M: 3hea,th,a) A A
Σ
Σner no (1)) (a:
the A
(8)
=.
Ener No (h)Hi (h)))
(i) is because U1 (h) स 0 only if is terminal node. (ii) is by the tree structure of EFG. Now consider 7 > 0 and U (h) for any h E H. Moreover, we will only show the upperbound when using dilated regularizer, since bidilated regularizer is upperbounded by the dilated one.
Let S(9 = (x), :) -. (( (-1s)
A (T ple) (s))) when A, + (s is not terminal node)
mi
and (() 0 when A, = @ (s is the terminal node).
We will prove (s) <
- ||o|| (D D(s)) maax by induction. For infoset & E S with 0 T|[aoloo (D - -D(s)) mmax Therefore, the initial step of
Mr
D(s) D. we have ((t)
induction is completed.
Consider when all 8 E S with D(s') > for some constant d. ( J ||00/000 (D D(s')) mmax Let Pr(h h() be the probability of reaching / from node h. when considering all nodes encountered along the path (player 1, action node and the chance node) for
32

---

Published as a conference paper at ICLR 2025
notational simplicity. Then, for infoset St with D(s) d, we have
(s)
(011))) Me (or (1"") (oz(h))
Σ MESI a(3)) (s,a)
(5) Σ
Σ hres'
Pr(h +1)
Σ
||a|| (D-((s) max
Mi
r'E (()))=(e,0)
He
Σ Pr(h- + WES
INE Me Mo(h")ai (0 (1"))
bES
||al (D ((s) 1) max
M1
Σ uo(h)14 (a (1) (0) hEs
Σ
Pr(h - h²)
EnEs Mo (1 (o1 (1') (1
MEH:: on (W)))(())))
||al (D-((s) 1) u max
M1
Therefore.
500 (8) (s,,,, (.)))))))))
(e) (
me
S M |0 (D -D(s) - 1) wim
+
T
||al wanx
M1
Mi ||a|| (D-D(s)) e/uaxx
This concludes the induction step.
G.2 BOUNDING M1, M2
By choosing "s as a fixed constant " > for any player i [2] and S,, Vs,a is chosen to be proportional to the number of terminal infosets (8' S with A, = 0) in the subtree rooted at (s,a),
we can get y 2 20
Then, we have the following lowerbound and upperbound on m
(8)
Lemma G.2. When ii flg 7. m (c) the following MI, M2 for different feedback.
(t) (c)
lowerbounded by Mj and upperbounded by M2 with
min.es EnEs (e(h)
Q-value
Q-value
{
M
Trajectory Q-value
M2
Trajectory Q-value Counterfactual Value
Counterfactual Value
(G.2)
Proof. We only prove the lowerbound and upperbound for infoset E S2 since two players are symmetric.
For counterfactual value, since m (#) = 1, M1, M2 = 1.
For trajectory Q-value, since m
Mi (a(s)) we have M2 = m. (1) > 1 M1.
For Q-value, m (1) ( (o2(h))
Enes Ho (o2(h)). (
Since the reach probability 1 for any Ti, we can let क play deterministically to
" (o(s)) Enes (e(h) reach In this way, ms is equal to the reach probability so it is also upperbounded by one. At the same time, ml! 2 7 Σbes (h) 2 min (nespe(h)
33

---

Published as a conference paper at ICLR 2025
G.3 PROOF OF LEMMA C.2
Lemma G.3. Consider update-rule where ag is a constant, we have
4.2 When 2/ = a, EnEd, ung is the Euclidean distance
C
1 + T VlA.l.
(G.3)
d2s
M1
Let (t) =
ru (2)
p(,(()) (s)
When v/
= 24 =
EaEd, ug we have
m
(t) p(a)
(118)
Tp(s) (1.s))
7
# (1)
p(aa) (-18)
Proja
(t 11-1) 1 (1- (s)))
- 112
(.1s)
+ T) (1-1)
as + n7
p(a)
((s)(11s)) (-1s)
(1)
pp(a)
ns
(t)1)(ss))
pps))(-1 (-1s)
(t-1) 1]
17 1111
To (1-1)
1
1 11
x (1)
D(a) (-18)
a,5(1
+ T7
1111)
1 1 115 (2-1)
1
(1))
+
+ ((-11)
x pca (11)(118))
VIAgo
||
+
Ois
M2
the last line, we use the fact that "m (s) S 1.
As result, | (e) ( ()
# =(() ( s)
$ M)
[A. a,
||
+ - v /All....
Similarly, ( (. (.1s)
= (e)
pt) (11s)
< 1/s
[Ad
|||||
+ Mr v [Agl)
a
Proof of Lemma
C.5 Let 7
=
ru (9)
plo (5)
When (w) = as (log |Aal + EaEs, un log ua).
m
the update-rule
4.2 is equivalent to
(a
(a (a) s4mr
q (0 (s)
ax exp
11+
(1-
max
YoVVaa
Z
#00 (a sxp
exp
(s)
log (t)) (a|s)
(1+n.
m 1)
[1m,
(1-1)
= max
MoMaa
2
for any a E As, where Z > 0 is a normalizing constant to ensure n (+) s) is still a proba- bility distribution over Aldl, The equivalency proved in Lemma G.4 For notational simplic- ity, we define (s,
a, (1+ [e- g (s)
1
m () [1+ (t- (t-1) log #(t) (a s) so that
1(00 s)xxp( 100 (s.o))
(a) 8) = max
NoVoa
34

---

Published as a conference paper at ICLR 2025
Firstly, for Y = 1, we have क (- = p(a) (-()) = Vs. Therefore, C. = and for any E As. In the following, we assume < 1.
(a
2 [s)
We can see that (a 8) is monotonically decreasing with respect to Z. When 7 -n.
<
exp (-7,s EaN (s,,,, d')), for any As, we have ( 8) 2 ( e) exp 7(*) (a) s). Then, EoEs, 10 (a (S) >1
7
Therefore, Z exp (-1), maxa'EA, (s)
Similarly, when Z (a) s) 1.. < # 710 (a 8). It implies that EmeA, (a 8) < EnEA, (10 8). un- less (a 8) Nousa for all A., which is impossible since assume Y 1. Therefore, Z S exp (11/ EA,, (s)
exp (-1 mina EA, (s, for any E As. we have
(a) (xss))expnneeee (oon--n (x.0)) 2 7o9s,a we have
Then, if
(1) (a s)
(11)
(a [}
(-11. (8,
exp
2
(1 (x:a') 112 (s.0)
S exp
7/4 max d'E
max o" (s,aa) (s.,)) ToTs
Tot(t-1)
(
[8)
I exp
log max d'ed, (a)
0. 1 11
aLEd,
+ goTO (1-1)
(8)
< exp
The
2 2|lgl +
Tuh
log 1 7 M1
a2
(18)
2 1/4
Tak log 2 |1
1
1
Os
Mi 7/
(i) we use the fact l1qll.o 2 (5, a) for any a E Ag. In (ii) we use ex 11 2x for x E [0, 1].
(0 8) exp( - no (0) (s.a))
If
<=(0 (a 8), we have
(-n)l(())s, a))
exp
exp
To min a'EA,
1/s 22|glloo + Tass log 1 2))
exp
Mi ب,
02
Therefore,
t 7 (a 8)
(als) exp (+
1/s (
+ TWss log - )
1 12
>
2 exp
2 22|lll 0z
n 700 (a
xa ss)
a,
M1
21
1/s
22|g +
Tas log 7/
as
Mi
Then, for any E Ag, we have
n (00) 8)
Tass log 2)
52 1/
22|g|1=o +
(a 8)
as
Mr
Therefore,
(-) - " (111) = ΣΣ (a)
(( 8)
1
< 2 7/
22|glloo
+ Tos log -
(a 8)
02
Mi
aEA.
(0+t) [s){a(s)
Similarly, the upperbound above also holds for
35

---

Published as a conference paper at ICLR 2025
G.4 UPDATE RULE OF MWU
For ease of representation, we ignore the learning rate without loss of generality (the update-rule the without 7) when multiplying both the gradient g and T by 17).
Lemma G.4. Consider the update-rule x?)) = arggin (a. g) (Tb(x) + D& (2x, x(1)) where
x(1) E A T 2 0 is constant, and / E A (A), A is the action set and (x)x = EeEA x log +
log [A]. Then, the update-rule is equivalent to
(1)
1+r
Za
exp
147
max
Vaa
(G.4)
Z
for any a E A. Z > 0 the normalizing constant to ensure EmEA tia
(2) =1
Proof. By definition of Bregman divergence, (a v1))) EoEd To log (.) Therefore, the Lagrangian function of the update-rule is
F(x, 3) (xx g) + Σ
Ia log To +
Σ
log
Co
a
Σ
Ia - 1 Σ
Ba(xo yVa)
[1)
aeA
aEAA
La
aEA
aEA
By taking VaF((xr ar A) = 0, for any a E A, we have
za
9a + log (2)
+ log
+
(1)
Za
which implies that
2 x
exp
I (ga + Ba)
By duality, 3a O. By complementary slackness, have Ba(x!? -V,)) Therefore, when
8a < O, we have (2) Ma, which implies that
(1)
exp
(ga + +1 +
at) Vaa-
When Ba O, we have Ta (2) 7P so that
(1)
I
exp
1+r (ga + +1+ 2 Va
Therefore, the effect of 8a is equivalent to take max on and have the update-rule
(1(1)
14r
exp
(- (ga + +1+
(1)
r
cxp
(ga
+1+ .
+
(1)
1+1
Ta
exp(
1+r
max
Va
Z
where Z exp
++++o I++
Remark G.5. In practice, we can implement the update-rule in Lemma G.4 as follows. We assume < since otherwise we can simply let (2) V.
Compute &, =
exp( )+) and sort it in increasing order, which is R < T2 <
< LA Simultaneously, adjusting v according to the sorting to get D, which is the lowerbound Eे should satisfy.
ΣSs, 3
Enumerate 0, 1,2, ..A.. Let Z
1-7
36

---

Published as a conference paper at ICLR 2025
4-sided Liar's Dicc
Ledue Poker
Kubn Poker
2x2 Abrupt Dark Hex
J0P
Explozzbility
10
10
2om-
10-7
10
10-12
10-11
10 13
10m3
40
100
50
100
50
100
Dteaaion
Terniion (x 10")
Deration Ex 10")
Iteration (x10
CFR
-+-
CFR+
MMD
QFF
DEFR
PCFR-
.....
Countrriattal Feeeback
Traj-Q foatleck
Figure 2: The result of full-information feedback in four benchmark games. We compare with CFR (Zinkevich et al., 2007), CFR+ (Tammelin et al. 2015), MMD (Sokota al. 2023), DCFR (Brown) and Sandholm 2019), and PCFR+ (Farina et al. 202 We can see that QFR outperforms MMD in all games. However, due to multiplicative noise caused by using Q-values, QFR cannot outperform PCFR+, an advanced variant of CFR.
Check 7. S 20, if i O and Fi41 2 70++1 if < [A]. If the current Z satisfies, return it. Otherwise, continue the enumeration.
(x= exp(
Wo with respect Z, the algorithm above will definitely find the correct Z and the time complexity is O(I log (Al) (the bottleneck is the sort).
According to the monotonicity of max
H EXPERIMENT DETAILS
Figure D and Figure 2 are conducted on 240 cores of Intel Xeon Platinum 8260 and Figure conducted on Intel(R) Xeon Gold 6248 with NVidia Volta V100. The code is based on Lite EFG (Liu et al. 2024) with game environments implemented by OpenSpiel (Lanctot al. 2019 The
range of grid search and the best
can be found in the supplementary materials.
We present the experimental results for full information feedback Figure that is, we use trajec-
tory Q-value, Q-value, counterfactual value (s. in the update rule 4.2 In Figure 2
plot the last-iterate performance for all the algorithms to ensure the comparison is fair.
In Figure we present the ablation study on importance sampling when the strategy is approximated by the neural network. Our implementation of QFR is based on PPO (Schulman et al., (017)) in CleanRL (Huang et al., (022)). We can see that with importance sampling, the network gradient blows so that the network does not converge, even though we have applied gradient clipping.
I QFR WITH LAZY UPDATE
In this section, we will show 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 that the convergence only requires the proportion of 1) and n to be 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 feedback not very large since the magnitude of the addi- tional regularizer is controlled by r). Moreover, when sampling trajectory, for those infosets that are not on the trajectory. we still need to update the strategy ( s) in them. In other words, for those infosets with 7()) = 0, we still need to update the strategy due to the additional regularizer (please refer (.4) for details). In practice,
ignore the update of those infosets that not along the trajectory, and postpone the update till the next time visiting them. That's why we call it a lazy update.
37

---

Published as a conference paper at ICLR 2025
Ledue Poker
Exploitability
Gradient Norm (Before Clipping)
2 10"
10
10a
10a
10 X
x 10
100
200
300
0
100
200
300
Iteration (x10*)
Iteration (x10*)
QFR
Counterfactual feedback
Traj- feedback
Figure 3: The result of QFR with sampling feedback. We can see that with importance sampling, the gradient norm keeps growing so that the network does not converge even with gradient clipping. The right figure shows the gradient before clipping and the gradient will be clipped so that its norm bounded by 0.5.
Consider the following update-rule, which is 4.2 with dilated regularizer instead of the bidilated one.
Tn(s (-1s)
argmin T. (
T (Tp(s)(11)) 18), (s, +
1--1) wo (-p(s)))1s))
1 + - Deg (-)), [100 (-
(L.I)
Th
7(1 (-1s(-
(T(s))( (ss)) (s" (s. + - v v (T((s)(11s))
argmin T- 7717
ms
Pa (Tp(o) 8), 1i s))
(1.2)
7
As Theorem 4.2 we can show the convergence of this update-rule. Note that in the following theo- rem, the proportion of n)s and nuae is now a constant when the feedback is Q-value or counterfactual value, which implies polynomial dependence on the game size.
Theorem L.I Consider the update rule L.I and qi)) :) is chosen to be counterfactual value, trajectory Q-value, or Q-value. When 2 have the following guarantee.
" 205 for any E S and (A) (B) (C) are satisfied, we
T
Σ
D (m). (1)))
T
2
Cl anc (Tr)))
Σ
w (T (8)
((e) (118)
w (A
p(e) (.1s))
(L.3)
$ES
4
diff (1rn)) (a(s)) Il MrT
#ES
2
M2 p (o(s))
(1))s 7 (1s)).
#ES
38

---

Published as a conference paper at ICLR 2025
Lemma 1.2 (Generalized from Lemma C.2. in Liu et al. (2023)) ). Consider the update rule in (4.
When / is strongly convex, then for any Tp(a)( ()) E A Al and 2 1, we have
1
(1)
w (TT p(a)
( (8)) - 7 ms
v (Tp(e)
m
+ 1)
(1 (T)(s)
p(s) (-1s) - vz (+ (-1s))
mg (t-1)
ma
+ + ( (0) (8, )) 7 p(s) (-1 8) (p (1s))
<Dep vg (Tp(s) (-1 [s), x (t)
(-1 (8) (1 + 1/s m
Dug (-
18), ())
p((a) ( (-|s)
p())
(1)
(1 + 778 m
(1-1) D وo (5 11
(. s); π
p(a) (.15))
p(a)
- Dog (2)
((p)) (. 18, क (0)
(. 8)) + 7 (a (s. (T (1) (-18) - =((+)(( (-16))
p(a)
The lemma's proof is similar to Lemma E.2
Multiplying m (9 on both sides of Lemma E.2 we have
To (T)))) (: (-)=)) - Th (Tp(o)( 8)) + net
m (t-1) -1 (v (= (1() (-)(()1))) (1
m
n-m! (- (s, -), (-(,)())))
(-1s) - [- $))
Sm (4) Dup (Tp(s) pls) (1)))) - (m! + n D (1), (-1s)
- -mm!) + not
ms
D pa p(a) (t [s); ( [s)
11-1)
m
mm D (TT p(a)
8),
क (8)
p(a)
(- (s) n.m!!) (g (0 6 (s, (5,
By using Property 2 we have
ma
1 (w (T (-)) W (T (-1s))
(t-1)
2 C.
We (1
(t) (()) (-1=)) we (+ (: 1s)
Furthermore, by using Lemma C.2 and Hölder's Inequality, we have
K (- - " (s. +), "P(s) (-1s) -====1(41 #((+2) (-1s))
(t)
$ (s.)) () ) 1|k- ()a) (11))
(s.
- -(+))) (- (8) s 2C I1all no-
where || = max (0 (l
By telescoping and non-negativity of Bregman divergence, we have
T
(t) 1s n (=p 8)) - T. (Tppe) [8)) (1)) + nmm!" (-q (T - =x(o((1)))
m(t))
m - nxT)
Duo (Tp(o) (.)) (() (s)s)
+ C n.TH
anc
2 (T p(s) (- [s) - vo (= (-1s)) + 20 || M.T
1=1
+ m! (1) Du (Tp (,)(s)
(-1s)).
39

---

Published as a conference paper at ICLR 2025
! can be upper-bounded by C₂ 1/2 178T S - - by Property 2 and letting D2 7/
20, By
non-negativity of Bregman divergence, we have
T
Th (Tp(s) (11)) noT (Tp(e) ( + (-g00
.), ((o))(1)))) Tp (()))()))))) b)))
7
Σ (Tp())) (1)), (1)
(. (-1)) C noTT and Σ
1o (T
+ (x))
p(t) (. (.18))
t=
+ 20
||all v. M2T + m D (T)(s) 8)), (-)))((11))
For simplicity, we use μ (a. F(u))= = (- Ay, A x) 11 == 11, x 11,, and S = S1 S2.
By using Lemma E.3 we have
0
= Σ
(lmm) (a
(h: (1,2). (-1
pls)
SES
Σ (olra))(((ss) (a(s)) Σ
Tu/ (m
p(a) (.1 (1)) -T// (=(2)))))) (.)
(t)
sES
+ m (1) (-9
(2) (8, ) mps) (.18) - x65 ((77))(( (- (-11))
T
(o(s)) ( (-) me (+))))
< 2 1=2
+
Σ
p
((t))) (a(s) Σ d ( - w p(s) (-1 s))
SES
+ 2 Σ Callff μ ((())
llllo M.T
SES
ma
(F))))
(o) 18), = (11)).
SES
(i) is because 4 (T is the NE of the regularized and perturbed EFG. Then, by rearranging the terms, we have
Σ
Dannul (u(ti) ,)
Σ (
(o (Tn))) [h), (()) ( (+1s))
t=2
<
anc p (Ta)) Σ
w (- (s)) (= p(e) (.1 {))
(2)
S
4
ddiff (1 (im))(((s))) A/ MoT
sES
2
(1)
(T)) (1))) (o(s)) (s), ( (-1s)
s)).
SES
The first line is by Lemma 4.1 Now, we achieved best-iterate convergence to the regularized NE (l in terms of Bregman divergence.
40

---

Published as a conference paper at ICLR 2025
1.1 LAZY QFR WITH STOCHASTIC FEEDBACK
Consider when we can only estimate g()) at each iteration, we apply the following update-rule to each individual infoset S,
(-1))
argmin
(1)6 + 1t-1) v (-1ss)
(T(s)((1s)) -()
ms
+ To
D (Tp(ss)) (1) (-) (-1))
(1.4)
(.1s)
argmin Tptes (5)A Axl
(T(e)(: [8), -(0( + t
2 (T(())(188)
ms
(-)ps))(1))))))))))))))))) + D uo (Tp(s) 8), . p(s)
(- s)).
Remark L.3. Note that the update-rule above is not realistic, since even when an infoset is unvisited at timestep t, ie. git) O, still need to update the strategy म (+++1) p(s) (- s) and (++1) (-1 due to
(P(s)
the regularization term. However, we can do a lazy update. We will record the update time &a of
each infoset E S. Once we touch infoset E S at timestep t, we will do - ty. steps update with a zero (0) (x, and update the time stamp lA, <- l.
Then, we have the following theorem. Note that the dependence on game size is still polynomial for Q-value and counterfactual value, since y-t is bounded by a constant.
7
Theorem L.4. Consider update-rule (14) and (0) (8, is chosen to be counterfactual value, trajec-
tory Q-value, or Q-value. When % aic the following guarantee with probability 1 5.
for any s E S and (A)
B (C) are satisfied, we have
205
Σ Den(u (t))i (0))
T C a0e (T.11)))))
Σ
j (x (-1s)) (((+))))
p(a) (+|s))
p(e)
SES
diff ( (o()) (on)) M,T
(I.5)
ms (1)
( (mp())) (:)s),
(1) s)) (1)))
-191l -181 2T 7
p(s)
77
#ES
41

---

Published as a conference paper at ICLR 2025
By Lemma 4.3 once we have unbiased estimator (s, for (s. -) in each infoset S with the same upper- upper-bound bound |l by Lemma 4.3 with probability 6, we have
( (()) To. (Tp(o) ()) + m! (-0 (s, -) p(e) (-1s) -p(o)(-1))) (s))ss)))
(TU p(s) (-1s) - (Tpcs)) + (-)") (la (-1s)
x-(a)((1 plo)
2T log 1 5
+ 4 ||lll00 V
T
Σ
D& (p)))) (.))(. + C Tmp
anc Σ
ve (16))
(= (.1))
2 1=2
+ 20
|1allc T
ms (1)
Dog (T)( 8), p(s) (-18)) + 4 ||alao 12T 8.
+
1/s
(i) follows the discussion in Appendix
Then, the proof follows the proof of Theorem 4.2
42


Reviews:
[{"review_id": "thU5nOe243", "reviewer": "Reviewer_ggwY", "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.", "questions": "Please see weakness section.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The analysis is sound with sublinear iterate average convergence. Proposed idea is novel and easy to follow.", "weaknesses": "Analysis section:\n\n- 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.\n\nExperiment section:\n\n- 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.\n\n- 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vcHBEGFCGf", "reviewer": "Reviewer_msNB", "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.", "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?", "limitations": "", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The idea of using Q-value in regret minimization is reasonable.\n\nThe writing is clear and and the paper is easy to follow.", "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. \n\nMotivations seem to be disconnected with later sections, such as experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tFfLX8Gg5S", "reviewer": "Reviewer_XFQu", "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.", "questions": "1. Eq (2.3): should the direction of the inequality be flipped?\n2. Have the author(s) tried to anneal the regularization? Or the results given in the experiments are all subject to regularized objective functions?\n3. 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?\n4. 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?\n5. 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.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "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. \n- Clear introduction of related works and main obstacles in the field as well as contribution statement. I really enjoyed reading this part.", "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.\n2. 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?\n3. 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. \n4. Other minor points: \n- Introduction (line 35): The statements (I) and (III) overlap with each other; they might be merged into one\n- Line 91 “Techniques based on rollouts of …” overlaps the previous paragraph. Author(s) could move this point to above\n- line 245: “additional”\n- Algorithm 1 line 6: indentation of the if-else statement is broken\n- Line 282: “Lastly, all infosets along the trajectory…” - I think the author(s) meant to point to Line 12 rather than Line 11", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HefjAGAowb", "reviewer": "Reviewer_66ub", "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.", "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.\n\n“We can see QFR outperforms BOMD in all games”. Does it in Liar’s Dice?\n\nMinor:\n\n* 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.\n* Line 240: The notation of the policies is confusing. And what is pi bar? Has it been defined?\n* Line 245: “ad ditional”\n* Line 245: What does subscript “bi” mean on the regularizer? Bilinear? (edit: later on line 269, bidilated)\n* Line 256: mu should be a psi?\n* Line 296: Dodgy line formatting of “else”\n* Line 303: Algo line 10. Where did this come from? Add a couple more words explaining the policy gradient update.\n* Line 323: “...learning *rate* of inforset…”\n* Line 411: +“the”, “and” -> “or”\n* Line 417: I am really struggling to see where this inequality comes from.\n* Line 469: “... with under …”\n* Line 716: “a NE” -> “an NE”\n* Line 796: What is alpha_s’? Did it get defined?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 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:\n\n* Best iterate convergence is more convenient than time-average convergence\n* No importance sampling\n\nThe 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.", "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).\n\nThere 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).\n\nFocuses on two-player zero-sum (a simple game-theoretic setting).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)