Extensive-Form Game Solving via Blackwell Approachability on Treeplexes
Authors: Darshan Chakrabarti
Julien Grand-Clément
Christian Kroer
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Extensive-form games
Blackwell approachability
counterfactual regret minimization
Primary area: algorithmic_game_theory

Abstract: We introduce the first algorithmic framework for Blackwell approachability on the sequence-form polytope, the class of convex polytopes capturing the strategies of players in extensive-form games (EFGs).
This leads to a new class of regret-minimization algorithms that are stepsize-invariant, in the same sense as the Regret Matching and Regret Matching$^+$ algorithms for the simplex.
Our modular framework can be combined with any existing regret minimizer over cones to compute a Nash equilibrium in two-player zero-sum EFGs with perfect recall, through the self-play framework. Leveraging predictive online mirror descent, we introduce *Predictive Treeplex Blackwell$^+$* (PTB$^+$), and show a $O(1/\sqrt{T})$ convergence rate to Nash equilibrium in self-play. We then show how to stabilize PTB$^+$ with a stepsize, resulting in an algorithm with a state-of-the-art $O(1/T)$ convergence rate. 
We provide an extensive set of experiments to compare our framework with several algorithmic benchmarks, including CFR$^+$ and its predictive variant, and we highlight interesting connections between practical performance and the stepsize-dependence or stepsize-invariance properties of classical algorithms.

Extensive-Form Game Solving via Blackwell Approachability on Treeplexes
Darshan Chakrabarti
Julien Grand-Clément
Christian Kroer
IEOR Department Columbia University dc3595@columiia edu
ISOM Department HEC Paris
IEOR Department
Columbia University
gr grand-clementhec.ff fr
christian. kroer@co wwwrrreoollaaaaa..mmmmomemmaaaaa edu
Abstract
We introduce the first algorithmic framework for Blackwell approachability on the sequence-form polytope, the class of convex polytopes capturing the strategies of players in extensive-form games (EFGs). This leads to new class of regret- minimization algorithms that are stepsize-invarian in the same sense as the Regret Matching and Regret Matching" algorithms for the simplex. Our modular frame- work can be combined with any existing regret minimizer over cones to compute Nash equilibrium in two-player zero-sum EFGs with perfect recall, through the self-play framework. Leveraging predictive online mirror descent, we introduce Predictive Treeplex Blackwell* (PTB"), and show a O(1/VT) convergence rate to Nash equilibrium in self-play We then show how stabilize PTB* with stepsize, resulting in an algorithm with a state-of-the-ane O(1/T) convergence rate. We provide extensive set of experiments compare our framework with several algorithmic benchmarks, including CFR and its predictive variant, and we highlight interesting connections between practical performance and the stepsize-dependenee or stepsize-invarians properties of classical algorithms.
Introduction
In this paper, we focus on solving Extensive-Fore Games (EFGs). Finding a Nash equilibrium of two-player zero-sum EFG can be cast as solving
min max (x, My)
(1)
#EA' yEy
where the sets X, y are two sequence-forn polytopes (also referred to as treeplexes) representing the strategies æ. y of each player, and M is payoff matrix. EFGs have been successfully used to obtain superhuman performances in several recent poker Al breakthroughs 37
Many algorithms have been developed based on (1. Since X' and y are polytopes, (1 can be formulated as a linear program [38]. However, because and y themselves have very large dimensions in realistic applications, first-order first-orre methods (FOMs) and regret minimization approaches are preferred for large-scale game solving. FOMs such as the Excessive Gap Technique (EGT, (32) and Mirror Prox [31] instantiated for EFGs [3] 27 converge Nash equilibrium rate of O(ITT), where T is the number of iterations. Regret minimization techniques rely on folk theorem relating the regrets of the players and the duality gap of the average iterates [19]. For instance, predictive online mirror descent with the treeplexes X' and y as decision sets achieves a OLL/T") convergence rate [14.
4 5..
regret minimizer for the treeplex that regret minimizers locally, i.e. directly at the level of the information sets of each player. CFR", used in instantiates the CFR framework with regret minimizer
Counterfactual regret minimization (CFR) 39
virtually all poker AI milestones 37 30 5,
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

called Regret Matching* + (RM") [7 and guarantees a O(1/VT) convergence rate. The strong empirical performance of CFR remains mostly unexplained, since this algorithm does not achieve the fastest theoretical Q convergence rate. Interestingly, there is a stark contrast between the role of stepsizes in CFR versus in other algorithms. CFR may use different stepsizes across different infosets, and the iterates of CFR do not depend on the values of these stepsizes. We identify this property as infoset stepsize invariance. In contrast, the convergence properties of FOMs depend on the choice of single stepsize used across the entire treeplex, which may be hard to tune in practice.
RM" is an instantiation of Blackwell approachabiliity 3 for the simplex, versatile framework with connections to online learning []] Empirically, using regret minimizer (over simplexes) based on Blackwell approachability (RM") is central the success of CFR": combining CFR with other local regret minimizers than RM", e.g., Online Mirror Descent (OMD), leads to much weaker practical performance [G. This raises the question of whether the performance of CFR is mostly explained by the use of Blackwell approachability on simplexes (RM"), and if a Blackwell approachability-bann based algorithm operating directly on treeplexes, bypassing the CFR decomposition, could outperform CFR'. Our goal in this paper is to address these questions. To do so, we develop the first Blackwell approachability-batn -base algorithms for treeplexes, and we provide a new hypothesis for explaining the performance of CFR'. In particular, our main contributions are follows.
Treeplex Blackwell approachability. We introduce the first Blackwell approachability based regret minimizer for treeplexes. Using the seaf- framework, we correspondingly get the first framework for solving two-player zero-sum EFGs via Blackwell approachability on treeplexes. Blackwell approachability enables an equivalence between regret minimization over the treeplex 'T and over its conic hull cone(T), ). and any existing regret minimizer for cone(T) yields new algorithm for solving EFGs. A crucial advantage of using Blackwell approachability on the treeplex, rather than regret minimization directly on the treeplex, is that it leads to a variety of interesting stepsize properties (e.g. stepsize invariance), which are not achieved by regret minimizers such as OMD on the treeplex.
We then provide several instantiations of our framework. PTB" (Predictive Treeplex Blackwell+, Algorithm 2 combines our framework with predictive OMD over cone(T) and achieves a O(L/VT) convergence rate. PTB' is treeplex stepsize invariant: its iterates do not change if we rescale all stepsizes by positive constant. This a desirable property for practical use, although is a weaker property than the infoset stepsize invariance of CFR'. Smooth PTB" (Algorithm 3 is a variant of PTB* ensuring that successive iterates vary smoothly. We show that Smooth PTB" the first solving algorithm based on Blackwell approachabilitty achieving O1/TT) convergence rate, answering an important open question. Crucially, it is necessary to introduce a stepsize to achieve this faster convergence, and thus Smooth PTB" is not treeplex stepsize invariant; this is analogous to existing FOM-based -mmthhdss for solving EFGs. We also consider AdaGradTB* and AdamTB", which learn different stepsizes for every dimension of the treeplexes, based on AdaGrad [12] and Adam (25) We present the convergence properties of our algorithms in Table !
Numerical experiments. We provide two comprehensive sets of numerical experiments over benchmark EFGs. We find that PTB" performs the best among all the algorithms introduced in our paper (Figure 4 highlighting the advantage of treeplex stepsize invariant algorithms (PTB") over stepsize-dependent algorithms achieving faster theoretical convergence rate (Smooth PTB*), and over adaptive algorithms learning decreasing stepsizes (AdaGradTB AdamTB"). We then compare our best method (PTB') with CFR", predictive CFR" (PCFR"), ) and predictive OMD (POMD) (Figure 2). We expected PTB" to perform on par with PCFR*, since PTB" is stepsize invariant, predictive, and based on Blackwell approachability. However, we find that PCFR* outperforms all other algorithms. This suggests that infoset stepsize invariance is important property, even more than the treeplex stepsize invariance of PTB'. Due to the CFR decomposition, PCFR* can use different stepsizes at different infosets, where the values of the variables may be of very different magnitudes (typically, smaller for infosets appearing deeper in the treeplex), and PCFR* does not require tuning these different stepsizes, which may be impossible for large instances. No algorithms appear to consistently outperform the others for the last-iterate performances, and we leave studying this as an open question.
A new hypothesis on EFG-solving algorithms: of our main contributions, we identify and distinguish the infoset and treeplex stepsize invariance properties, and based on our empirical experiments, we posit that infoset stepsize invariance explains part of the puzzle behind the strong empirical performance of CFR' and PCFR'. Our results highlight that for practical performance, the stepsize invariance properties may be more important than faster
the role of stepsize invariance. Overall, as part

---

theoretical convergence rates, which require introducing a stepsize, as for Smooth PTB" or POMD. The very strong empirical performance of (predictive) CFR' has been unexplained for long time and is one of the major open questions in EFG-solving; we view providing a new hypothesis for this phenomenon (infoset stepsize invariance) as important contributions to the FFG-solving community.
Algorithms
Convergence rate
Stepsize invariance
CFR 37
1/VT
PCFR* 16
1/VT
EGT 126
1/T
POMD
1/T
PTB' (Algorithm
1/VT
Smooth PTB' (A gorithm
1/T
AdaGradTe" (Algorithm 6
1/VT ?
X
AdamTB' (Algorithm
X
Table I: Convergence rates to Nash equilibrium of two-player zero-sum EFG for several algorithms.
V / refers to infoset stepsize invariance and v refers to treeplex stepsize invariance.
2 Preliminaries on EFGs
We first provide some background on EFGs and treeplexes.
Extensive-form games. Two-player zero-sum extensive-fomm games (later referred to as EFGs) are represented by game tree and payoff matrix. Each node of the tree belongs either to one of the players, or to chance player, modeling the random events in the game, e.g., tossing a coin. The players are assigned payoffs at the terminal nodes only. Imperfect information is modeled using information sets (infosets), which are subsets of nodes of the game tree. A player cannot distinguish between the nodes a given infoset, and they must take the same action at all these nodes.
Treeplexes.
The strategy of a player can be described by a polytope called the treeplex, also known as the sequence-form polytope. The treeplex is constructed follows. We index the infosets of a player The set of actions available at infoset j E J is written A, with cardinality J by sequence (j. a), and
by J = |
[A,1 nj. We represent choosing action Aj at infoset denote by Cjn the set of next infosets reachable from (j. a) (possibly empty if the game terminates). j: note that p5 is unique assuming
The parent Py of an infoset j I is the sequence leading perfect recall. We assume that there is a single root denoted as Ø and called the emply sequence. If the player does not take any action before reaching j J, then by convention p, = Ø. Under the perfect recall assumption, the set of infosets has a tree structure: Cja Cr = 0, for all pairs of sequences (j. a) and (j', a') such that j + j', a + a'. This tree is the treeplex and represents the set of all admissible strategies for given player. We denote by E N the total number of sequences (j, a) with j E I and Az. With these notations, the treeplex T of given player is
T = fx E RR ZØ 1, Σ
Ija Tp,, AJEJT
(2)
aeA;
where the first component Te is related to the empty sequence Ø. A player makes observation to arrive at j. if |C,,1 > 1. We define the depth d of treeplex to be the maximum number of actions and observations that can be made starting at the root until reaching leaf infoset. Computing Nash equilibrium of EFGs can be formulated as solving ( (under the perfect recall assumption). with X' c 1= and ) C 1 the treeplex of each player, nı and n2 are the number of sequences of each player, and M E [(n++1)x(pa++)) the payoff matrix such that for a pair of strategy (x, y) E X x y, (x, My) is the expected value that the second player receives from the first player.
Regret minimization and self-play framework. A regret minimizer Regmin over decision set Z Idd is an algorithm such that, at every iteration. Regmin chooses decision z' Z, loss vector E Rdd is observed, and the scalar loss (e', x²) is incurred. A regret minimizer ensures that the regret Reg" max Σ (L', z' Σ) grows at most as O O(VT). As an example, predictive online mirror descent (POMD, 34 generates a sequence of decisions ø1, 2T E Z as follows:
2 ll (2, 1771)) 2 1lz (ž. nl,)
33)
3

---

with mi..... mr E R' some predictions of the losses lr. E R and where we write the orthogonal projection y I onto Z as II (y) == arg minzez || az-yyl yll-
The self-play framework solves EFGs via regret minimization. The players compute two sequences of strategies æ1; ... Fr and y1,--,97 yr such that, at iteration & > 1, the first player observes its loss vector M y and the second player observes its loss vector - M æt-1- Each player computes their current strategies 2, E X and y/ E y via regret minimization. A well-known theorem states that the duality gap of the average of the iterates is bounded by the sum of the average regrets of the players.
Proposition 2.1 (199). Let 2,, ET E X and yı...., yr y be computed in the self-play framework. Let (TT, yT) = ΣT (ot, y1). Then, for Regi
T and Regè the regret of each player,
max (iT. Mÿ) min (#. MyT) = (Regi' + Regb /T.
yey
REX
We present more details the self-play framework in Appendix A
CFR and Regret Matching*. Counterfactual Regret minimization (CFR, (39]) runs independent regret minimizers with counterfactual losses at each infoset of the treeplexes. This considerably simplifies the optimization problem, since the decision set at each infoset j E J is the simplex over the set of next available actions " {xc E E+ >> I; = 1}. In the CFR framework, the regret of each player (over the treeplex) bounded by the maximum of the local regrets incurred at each infoset. Therefore, CFR combined with any regret minimizer over the simplex converges to Nash equilibrium at rate of O(1/VT) We refer to Appendix B for more details. Combining CFR with a local regret minimizer called Regret Matching (RM", [37] along with alternation and linear averaging yields an algorithm called CFR", which has been observed attain strong practical performance compared to theoretically-fant faster methods [27]. Crucially, RM can only be implemented on the simplex and not for other decision sets, and proceeds as follows: given sequence of loss Li..... ly E Rd, RM" maintains a sequence Ri,..., Rr E Rd such that R₁ = O and
Bt = R || |1 R++1 1lz4 (R, ng(g,, (()
(4)
with y > 0 and 0/0:= = (1/d)1 for == (1,..., 1) E R2, and, for x, E Rd.
g(, (- (x.
(5)
RM" is stepsize invariant: 21, TT are independent of 1), since x, R and n only rescales the entire sequence R1, ..., Ry. Since CFR runs RM" at each infoset independently. CFR" is infoset stepsize invariant: there may be different stepsizes across different infosets and the iterates of CFR' do not depend on them, which is desirable for large-scale EFGs where stepsize tuning may be difficult.
RM" can be interpreted as an instantiation of Blackwell approachability M. where the goal of the decision maker is to compute the sequence of strategies 21, ..., DT E A d to ensure that the auxiliary sequence R3 /T Rd approaches the target set Rdd as T - D00 Since R2 RR.. this is equivalent to ensuring that + R = O. The vector g g E) is interpreted as an instantaneous loss for the approachability instance. As instantiation of Blackwell approachability, at each iteration RM computes an orthogonal projection onto the conic hull of the decision set:
Rd
cone( A
with cone(2) 2) = faxe x E 2, 2 0} for set Z. The function R + R/| is based on
A c (x E ddd
(x, 1) = 1}.
Since for R E RR. (R, 1) a vector such that the decision set A satisfies This ensures that
|| R||,, then a,
R,/ [R,]1 can be written a, Re/(RR, 1), with 1
(Re, g p,, e)) 0, V l E IRd.
8
We provide an illustration of the dynamics of RM in Figure ! Equation 8 is known as hyperplane forcing condition and is a key ingredient in any Blackwell approachability-basee algorithm; it ensures that the vector Ri grows at most at a rate of O(v so that limr- RT/T = O. We refer to and to Appendix forr more details Blackwell approachability.
33 2

---

Blackwell Approachability on Treeplexes
In this section we introduce a modular regret minimization framework for the treeplex based on Blackwell approachability. This framework can be used regret minimizer over in the self-play framework (described in the previous section and in Appendix A) to obtain an algorithm for solving
EFGs. Our algorithms are based on the fact that for 7 C I + a treeplex as defined in we have
T C {w E R
(z. a) =
(9)
for a (1,0) E R+ with 0 = (O. 0) E R" This property is analogous to 7 for the simplex. With this analogy in mind, we define C R++1 and f(x L) E TR=+1 as, for a, R
C == cone(
(10)
f f(x, E) == (xx (z,
(11)
Equation (T0) and Equation 11 are analogous (6) and (5) The cone and the vector f L) play
similar role for T as R and g E) play for c in RM Our framework is described in Algorithm
I and relies on running a regret minimizer Regmin over C cone(T) against the losses f L) to
obtain a regret minimizer over against the losses l, for t 2 1.
Algorithm 1 Blackwell approachability on the treeplex
R
R
1: Input: A regret minimizer Regmin with decision
set C
2: Initialization: R. = RR+11
R, +
3: for t l,..,,.... .odo
4: TG = RRe(RRR
A
5: Observe the loss vector & E R=+1
R2
6: Regmin observes f f Le) E R=+1
7: R Regmin (.)
Figure 1: RM in RR,, with g. g(x,; le).
By convention that 0/0 is the uniform strategy for the treeplex. Algorithm I is the first Blackwell approachability- based algorithm operating on the entire treeplex (in contrast to CFR' which relies on Blackwell approachability locally at the infosets level). We first describe some important properties of Algorithm 0
Feasibility of the iterates. Algorithm I produces feasible strategies, i.c., D E 7,Vt2 2 1. Indeed, since Regmin is regret minimizer with C as the decision set, R, E cone (T), i.c. Rr with 1 and T. From ( we have (z, a) = 1. Therefore, 2 (R, This is analogous to RM", where æ, is proportional to R., see and Figure (2.n)
R.
T.
foriing. For any E N we have
RRe, fw 2)} = 0, e R*+
(12)
The hyperplane forcing equation approachability. It ensures that Rell2 O(VT). Equation (12) is analogous (8) for RM and
12 crucial component of algorithms based on Blackwell
R, so that follows from æ; (R.aay
R. (Re, (Re, (at, 2) (Re, l) - (ar, () = (Re, ((R a)
() a) (R., (Re, E)
Regret minimization over T. Algorithm Talways yields a regret minimizer over the treeplex T, i.e.,
ensures that the regret of I1,..., ØT E T against any LI,..,, by E g=+1 is bounded by O(vT). The proof instructive and shows central component Blackwell approachability- minimizing regret over T can be achieved by minimizing regret over cone(T).
algorithms:
Proposition 3.1. Let Regmin be regret minimizer with C as the decision set. Let æι ET E T be computed by Algorithm Then max.eT ΣT (xx ã, Re) O(VT).
5

---

Proof.
Let ④ E T and let us write R = 2. We have
Σ (1. - az Ri) Σ 2. (r, (.)) - (ar, Ex) = E R, (a Ee))
where the first equality follows from the definition of f (ax, l,) and (z, a) for any E T, the second equality is because - R. and the last equality follows from the hyperplane forcing condition (12). Now note that Σt=1( (R, R. f (It, Le)) is the regret of a regret minimizer Regmin choosing . Ri in the decision set == cone(T) (T) against a sequence of loss f (I1. b,)..... (IT Cr) and a comparator R cone(T). Therefore, Σi= (R, R. f (1,, R)) = O(VT).
Remark 3.2. In their seminal paper, Abernethy el al. A show general reduction from regret minimization to Blackwell approachabilityy for compact convex decision sets. Our reduction from Algorithum [ builds upon the ideas []]. but our reduction is different and exploits the structure of treeplexes. Additionally, Ml focuses on the case of adversarial losss, whereas we focus on solving EFGs, where stepsize invariance properties is crucial and where we can prove fast (1//T) convergence rates. We provide more detailed comparison with M7 in Appendix C
4 Instantiations of Algorithm
1
We can instantiate Algorithm [ with any regret minimizer over C to obtain various properties such as stepsize invariance or achieving (1/TT) convergence rate. We show next how to do so.
Predictive Treeplex Blackwell+ (PTB"). We first introduce Predictive Treeplex Blackwell+ (Algo- rithm 2, combining Algorithm 1 with POMD with C as a decision set.
Algorithm 2 PTB"
Algorithm 3 Smooth PTB*
Input: 7) > 0, my.... my R=+1
Input: 17 > 0, m, my R*+1
2: Initialization: R =0 E R
Initialization: R = 0 E Ra+1
3: for trrt- = wart=1.... T,...,Tdh do
3: for f = 1..... T do
4: R2 E 11 1ym;
4:
R, E lcc R2 - mm:
5: Ft = Re/ R
Dt R2/ (Re, R
6: Observe the loss vector l E Ru+1
6: Observe the loss vector Ee E RR++1
7:
R E Ie RR (f Et)
Ru41 ITc
Ri, nf la)
We start by highlighting crucial property of PTB", treeplex stepsize invariance. The sequence of iterates T1...., DT generated by Algorithm? 2 independent of the choice of the stepsize 77 > 0, that only rescales the sequences R,,... R and R....., Rr, the orthogonal projection onto a cone is positively homogeneous of degree IIc (1)) = n)llc(z) for 1) and R=+1 and the function R R + R/ RR a) scale-invariant: [( (R,a) for > and R E g=+1, We provide a rigorous statement in the following proposition and we present the proof in Appendix D
(nR)
Proposition 4.1. The sequence Ii...., ØT computed by PTB' is independent on the stepsize n >> 0.
Treeplex stepsize invariance is a crucial property, since in large EFGs, stepsize tuning is difficult and resource-consuming This is the main advantage of using Blackwell approachability: running POMD directly on the treeplex does not result in stepsize invariant algorithm, whereas PTB" runs POMD cone(T) and is stepsize invariant. To our knowledge, CFR' and PCFR' are the only other treeplex stepsize invariant algorithms for solving EFGs. In fact, they satisfy a stronger infoset stepsize invariance property: different stepsizes be used at different infosets, and the iterates do not depend on their values. We discuss the relation between PTB* and known instantiations of Blackwell approachability over the simplex (RM" and CBA* (22) in Appendix E
From Proposition 3.1 and the regret bounds on POMD (see for instance section 3.1.1 in 34 or section
6 in [16). we obtain the following proposition. We define Ω E IR,, Ω == maX.eT - |z|22

---

Proposition 4.2. Let 21..... 2r be computed by PTB". Then maxæeT Et= (az - 2. 1
O EL [f ((m),,.) (1) mm.1i
From Proposition 4.2 PTB" is a regret minimizer over treeplexes, and we can combine with
the self-play framework to solve EFGs, as shown in the next corollary. We use the notations
== max {n, m) + 1, = max(1l= z E UUD,, || == sup |Mvl2
l|lla
Corollary 4.3. Let (2t)121 and (yd)12 be the sequence of strategies computed by both play- ers employing PTB* in the self-play framework, with previous losses as predictions: m =
f f My--),,
100-1 -M x1-1). 1). Let (Ør, (r)) = Et=n (2 Vr). Then
max (TT, My) EEy
min (a, Mÿr) S
=ex
VT
Finally, we can efficiently compute the orthogonal projection onto C, since C admits the following simple formulation of as polytope: C = {x E TR++1 EuEA, Pja- = Tpp V E J}.
Proposition 4,4. Let T be treeplex with depth d, number of sequences number of leaf sequences I, and number of infosets m. The orthogonal projection lcy(y) of a point y E Ig++1 onto cone(T) can be computed in Odn log(l + m)) arithmetic operations.
stable algorithm: Smooth PTB". We now modify PTB' to obtain faster convergence rates. The O(1/vT) average convergence rate of PTB" may seem surprising since in the matrix game setting, POMD over the simplexes obtains a O (1/ average convergence [36]. This discrepancy comes from PTB' running POMD on the set = cone (T) instead of the original decision set T, so that the Lipschtiz continuity of the loss function and the classical RVU bounds (Regret Bounded by Variation in Utilities, see Equation (1) in (36)), central to proving the fast convergence of predictive algorithms, may not -+ f fax, E) with x R (R, a) depends + R R. a) over C, which we analyze next.
hold. For PTB", the Lipschitz continuity of the loss R
the Lipschitz continuity of the decision function R
Proposition 4.5. Let R1, R. E cTne(T). Then
R.
R max R, (R,aa)
RR R2.a)
(2.a))
We present the proof of Proposition 4.5 in Appendix F Proposition 4.5 shows that when the vector R
is such that (R, a. is small, the decision function R + R/(R, a) may vary rapidly, an issue known as instability and also observed for predictive variant of RM the decision function, we can ensure that R, and R, always belong to the stable region C2:
[8. To ensure the Lipschitzness of
C2 == cone (T) n (R E Ra++1 | (R, a) 2 Ro}
for Ro > 0, and we recover Lipschitz continuity over Cz:
R
R2
Ω
R
Rella, V R1, R2 E Cz.
a
R2 a)
Ro
This leads us introduce Smooth PTB' (Algorithm belong to Cz. For Smooth PTB" ,e; E T since R, E C2 c cone(T), and we also have the hyperplane foreing property (12). which only depends on æ, R,/ a). However, Smooth PTB* is not treeplex stepsize invariant, because the orthogonal projections are onto Cz which is not a cone. Note that C2 admits a simple polytope formulation:
variant of PTB" where RG and Rd always
C2 = fx E 187+1 I > Ro. Σ
Izn -
aEAA,
so the complexity of computing the orthogonal projection onto C- is the same as computing the orthogonal projection onto C. We provide a proof in Appendix H We now show that Smooth PTB* regret minimizer. Indeed, the proof of Proposition 3.1 can adapted relate the regret in
Ti, BT in T to regret in R,...., Rr in Cz.
Proposition 4.6. Let Ei,..., Te be computed by Smooth PTB". Let 1)
If [xt, & m,
Then max (t= - áz lx) 2V Ei= (1, le) m. mm:mmmm1.
7

---

In Smooth PTB" R3 and R, always belong to Cz, and we are able to recover a RVU bound and show faster convergence. We let |M be the maximum l 2--nom of any column and any row of M.
Theorem 4.7. Let (2)))21 and (2)))21 be the sequence of strategies computed by both play- ers employing Smooth PTB" in the self-play framework, with previous losses as predictions: m f( My--1), m f(yc-1, -M" x(-1). -Mxx(11) Let 1f
Rg and (FT, yr) =
T E vt). Then maxyey (ØT, My) mingex (1, (0,MÿT) S
20'
T
We present the proof of Theorem 4.7 Appendix [ To the best of our knowledge, Smooth PTB* is the first algorithm based on Blackwell approachability achieving a O(1/T) convergence rate for solving EFGs in ( answering an important open question. However, achieving the faster rate in Smooth PTB" requires introducing stepsize, situation similar to all other ((1/TT)-methee
for EFGs, like Mirror Prox and Excessive Gap Technique for EFGs [27 and predictive OMD directly on the treeplex [4]. We can compare the O(1/T) convergence rate of Smooth PTB' with the O(L/VT) convergence rate of Predictive CFR' [6]. which combines CFR with Predictive RM" (see Appendix B). Despite its predictive nature, Predictive CFR only achieves a O(1/VT) convergence rate because of the CFR decomposition, which enables running regret minimizers independently and locally at each infoset, and it is not clear how to combine, at the treeplex level, the regret bounds obtained at each infoset. Since Smooth PTB" operates over the entire treeplex, we can combine the RVU bound for each player to obtain O(1/T) convergence rate.
Remark 4.8. The Clairvoyant CFR algorithm from [18] is based on Blackwell approachability over simplexes, combined with the CFR decomposition and Mirror Prox-style update [31]. For solving EFGs, Clairvoyant CFR achieves a (log(T))TT convergence rate, slower than the O(1/T) convergence rate of Smooth PTB", where the additional log(T) factor occurs because each outer iteration of Clairvoyant CFR itself solves an approximate fixed-poit problem.
For completeness, we also instantiate Algorithm I with regret minimizers that learn heterogencous stepsizes across information sets in an adaptive fashion. This results in AdaGradTB' (aaGrradB"(AAgoriiii (Algorithm 66 and AdamTB' AdamTB"(Algorithe (Algorithm 7) which adapt the scale of the stepsizes for each dimension to the magnitude of the observed gradients for this dimension based AdaGrad [12] and Adam (25). This may be useful the losses across different dimensions differ in magnitudes, but the stepsizes decrease over time, which could be conservative. These algorithms are presented in Appendix []
Remark 4.9 (Comparison with Lagrangian Hedging). Algorithm is related to Lagrangian Hedg- ing 127 ПTY. Lagrangian Hedging builds upon Blackwell approachabillty with various potential functions to construct regret minimizers for general decision sets. As explained in the introduction, the main focus of our paper is on two-player zero-sum EFGs, i.e., on the case where the decision sets are obtain several additional interesting properties not studied in [21 [7]],
treeplexes, and where such as stepsize invariance, fast convergence rates, and efficient projection, as we detail in the next section. If one would yield the regret minimizer for treeplexes studied in Gordon (2I), and our Proposition (4.4 in the next section yields an efficient projection oracle for the setup in Gordon 121,, which appealed to general convex optimization as an oracle.
instantiate Algorithm| |
with the Follow-The Tee-ThhheReeerizeee Leader algorithm,
5 Numerical Experiments
Kihe
Dice
Gootiiel
Butteship
Dollyyn ptp
10--
10
10
10
10
10-
10
102
10
10' Iecottoss
112
Berattos
Ieeetions
gradadi
Sana:
qudiak
$2-P000 qualinds
Figure 2: Convergence Nash equilibrium for PTB", CFR PCFR* and SC-POMD. All algorithms alternation and quadratic averaging except CFR instantiated with linear averaging.
8

---

Kaltt
Ledie
Lia''s Dise
Godsgid
Batllhhp
10
10f
Daalty gap
10
1o7
10-7
141
10
10-32
10-7
13
30
10
10
licnation
Tacrations
Dirnations
Damation
Figure 3: Convergence to Nash equilibrium for the last iterates of PTB", CFR", PCFR", and SC-POMD. Every algorithm is using alternation.
We conduct two sets of numerical experiments to investigate the performance of our algorithms for solving several two-player zero-sum EFG benchmark games: Kuhn poker, Ledue poker, Liar's Dice, Goofspiel and Battleship. Additional experimental detail is given in Appendix
We first determine the best instantiatons our framework. We compare PTB", Smooth PTB" and AdaGradTB" in the self-play framework with alternation (see Appendix [A] and uniform, linear or quadratic weights for the iterates. PTB" and Smooth PTB" use the previous losses as predictions. We also study Treeplex Blackwell* (TB"), corresponding to PTB without predictions (m, = 0), and AdamTB". For conciseness, we present our plots in Appendix K.3 (Figure 4) and state our conclusion here. We find that, for every game, PTB* performs the best or is among the best algorithms. This underlines the advantage of treeplex stepsize invariance over algorithms that require tuning a stepsize (Smooth PTB') and adaptive algorithms (AdaGradTB"), which may perform poorly due to the stepsize decreasing at a rate of O(1/VT). AdamTB" does not even converge in some games.
We then compare the best of our algorithms (PTB") with some of the best existing methods for solving EFGs: CFR [37), predictive CFR (PCFR', [16], see Appendix B)) and a version of optimistic online mirror descent with single call to the orthogonal projection every iteration (SC-POMD, (24)) achieving a O1/TT) convergence rate; there are a variety of FOMs with a O(/TT) rate, SC-POMD was observed to perform well in (8). We determine the best empirical setup for each algorithm in Appendix|K.44 [4.4 In Figure 2 we compare the performance of the (weighted) average iterates. We find that PCFR outperforms both CFR and the theoretically- faster SC-POMD, as expected from past work. We had hoped to see at least comparable performance between PTB" and PCFR", since they are both based on saaccweellapprrrccchbiitty regret minimizers derived from applying POMD on the conic hull of their respective decision sets (simplexes at each infoset for PCFR", treeplexes of each player for PTB"). However, in some games PCFR* performs much better than PTB". Given the similarity between PTB' and PCFR*, our results suggest that the use of the CFR decomposition is part of the key to the performance of PCFR". The CFR decomposition allows PCFR' to have stepsize invariance at an infoset level, as opposed to stepsize invariance at the treeplex level in PTB". Because of the structure of treeplexes, the numerical values of variables associated with infosets appearing late in the game, i.e., deeper in the treeplexes, may be much smaller than the numerical values of the variables appearing closer the root. For this reason, allowing for different stepsizes each infosets (like CFR and PCFR* do) appears to be more efficient than using a single stepsize across all the infosets, even when the iterates do not depend on the value of this single stepsize (like in PTB") and when this stepsize is fine-tuned (like in SC-POMD). Of course one could try to run SC-POMD with different stepsizes at each infoset and attempt to tune each of these stepsizes, but this is impossible in practical instances where the number of actions is large, c.g., 4.9 x 10 actions in Liar's Dice and 5.3 10 actions in Goofspiel. CFR* and PCFR* bypass this issue with their infoset stepsize invariance, which enables both each infoset to have its own stepsize (via the CFR decomposition) and not needing to choose these stepsizes (via using RM and PRM as local regret minimizers, which are stepsize invariant).
We also investigate the performance of the last iterates in Figure 3 No algorithm appears to be the best across all game instances. CFR" may not converge to a Nash equilibrium (e.g., on Kuhn), as has been observed before 229. PCFR* exhibits linear convergence in some games (Kuhn, Liar's Dice, Goofspiel) but not others (Ledduc). The same is true for PTB Further investigations about last-iterate convergence are left an important open question.

---

6 Conclusion
propose the first Blackwell approachbbilty--aeee regret minimizer over the treeplex (Algorithm D and we give several instantiations of our framework with different properties, including treeplex stepsize invariance (PTB"), ) adaptive stepsizes (AdaGradTB") and achieving (11TT)) convergence rates on EFGs with a Blackwell approachability-bast
algorithm for the first time (Smooth PTB'). Since CFR and PCFR* are stepsize invariant and have strong empirical performance, we were expecting PTB" to have comparable performance. However, experiments show that PTB" often converges slower than CFR* and PCFR", so this treeplex stepsize invariance is not the only driver behind the practical performance of CFR* and PCFR". We view this negative result of our paper, since it rules out previously plausible explanation for the practical performance of CFR'. Instead, propose that piece of the puzzle behind the CFR and PCFR" performances is their infosel stepsize invariance, a consequence of combining the CFR framework with Blackwell approachability-bunn regret minimizers (RM' and PRM", themselves stepsize invariant over simplexes). Future directions include better understanding the last-iterate performance of algorithms based on Blackwell approachability as well as the role of alternation. It would also be interesting explore EFG applications of new reductions between Blackwell approachability and regret minimization [IO] (which differs from the reduction in 2 and Blackwell approachability generalizations based on
important contribution
various norms and pseudo-norms 28
potentially to obtain better stepsize invariance properties.
Acknowledgments and Disclosure of Funding
Darshan Chakrabarti was supported by the National Science Foundation Graduate Research Fellow- ship Program under award number DGE-2036197, Julien Grand-Clément was supported by Hi! Paris and Agence Nationale de la Recherche (Grant I1-LABX-0047), Christian Kroer was supported by the Office of Naval Research awards 200014-22-1-2538 and N00014-23-1-23744 and the National Science Foundation awards IIS-2147361 and 113-223..60.
References
[1] J. Abernethy, P. L. Bartlett, and E. Hazan. Blackwell approachability and no-regret learning equivalent. In Proceedings of the 24th Anmual Conference on Learning Theory, pages 27-46. JMLR Workshop and Conference Proceedings, 2011.
[2] J. D. Abernethy, E. Hazan, and A. Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. 2009.
[3] D. Blackwell. An analog of the minimax theorem for vector payoffs. Pacific Journal of Mathematics, 6(1):1-8, 1956.
[4] N. Brown and T. Sandholm. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418-444, 2018.
[5] N. Brown and T. Sandholm. Superhuman Al for multiplayer poker. Science, (656646))85)88888880
2019.
[6] N. Brown, C. Kroer, and T. Sandholm. Dynamic thresholding and pruning for regret minimiza- tion. In Proceedings of the AAAI conference on artificial intelligence, volume 31, 2017.
[7] N. Burch, M. Moravcik, and M. Schmid. Revisiting CFR+ and alternating updates. Journal of Artificial Intelligence Research, 64:429-443, 2019.
[8] D. Chakrabarti, J. Diakonikolas, and C. Kroer. Block-coordinate methods and restarting for solving extensive-form games. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[9] C. Dann, Y. Mansour, M. Mohri, J. Schneider, and B. Sivan. Pseudonorm approachability and applications regret minimization. In International Conference on Algorithmic Learning Theory, pages 471-509. PMLR, 2023.
10

---

[10] C. Dann, Y. Mansour, M. Mohri, J. Schneider, and B. Sivan. Rate-presenne reductions for blackwell approachability. arXiv preprint arXiv:2406.07583 2024.
[11] R. D'Orazio and R. Huang. Optimistic and adaptive lagrangian hedging. In Thirty-fisth AAAI conference on artificial intelligence, 2021.
[12] J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
[13] G. Farina, C. Kroer, and T. Sandholm. Online convex optimization for sequential decision processes and extensive-form games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1917-1925, 2019.
[14] G. Farina, C. Kroer, and T. Sandholm. Optimistic regret minimization for extensive-form games via dilated distance-generating functions. In Advances in Neural Information Processing Systems, pages 5222-5232, 2019.
[15] G. Farina, Kroer, and Sandholm. Better regularization for sequential decision spaces fast convergence rates for Nash, correlated, and team equilibria. In EC'21: Proceedings of the 22nd ACM Conference on Economics and Computation, 2021.
[16] G. Farina, C. Kroer, and T. Sandholm. Faster game solving via predictive Blackwell approacha- bility: Connecting regret matching and mirror descent. In Proceedings of the AAAI Conference on Artificial Intelligence. AAAL, 2021.
[17] G. Farina, I. Anagnostides, H. Luo, C.-W.Lec C. Kroer, and T. Sandholm. Near-optimal no- regret learning dynamics for general convex games. Advances in Neural Information Processing Systems, 35:39076-39089, 2022.
[18] G. Farina, J. Crémen,,é C. Kroer, C.-W. Lee, and H. Luo. Regret matching+: (in)stabilitty and fast convergence in games. In Advances in Neural Information Processing Systems, 2023.
[19] Y. Freund and R. E. Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1-2):79-11 1999.
[20] A. Gilpin, J. Pena, and T. Sandholm. First-order algorithm with convergence for-equilibrium in two-person zero-sum games. Mathematical programming, (33(122)2279-2)) 298, 2012.
[21] G. J. Gordon. No-regret algorithms for online convex programs. In Advances in Neural Information Processing Systems, pages 489-496. Citeseer, 2007.
[22] J. Grand-Clément and C. Kroer. Solving optimization problems with Blackwell approachability. Mathematics of Operations Research, 2023.
[23] S. Hoda, A. Gilpin, J. Pena, and T. Sandholm. Smoothing techniques for computing Nash equilibria of sequential games. Mathematics of Operations Research, 35(2):494-512, 2010.
[24] P. Joulani, A. György, and C. Szepesvári. A modular analysis of adaptive (non-) convex opti- mization: Optimism, composite objectives, and variational bounds. International Conference on Algorithmic Learning l'heory, pages 681-720. PMLR, 2017.
[25] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations, ICLR, 2015.
[26] C. Kroer, G. Farina, and T. Sandholm. Solving large sequential games with the excessive gap technique. In Advances in Neural Information Processing Systems, pages 864-874, 2018.
[27] C. Kroer. K. Waugh, F. Kilin-- Karzan, and T. Sandholm. Faster algorithms for extensive-fome game solving via improved smoothing functions. Mathematical Programming, pages 1-33, 2020.
[28] Kwon. Refined approachability algorithms and application to regret minimization with global costs. Journal of Machine Learning Research, 22(200):1-36 2021.

---

[29] C.-W. Lee. C. Kroer, and H. Luo. Last-iterate convergence in extensive-form games, Advances in Neural Information Processing Systems, 11114293-13055. 2021.
[30] M. Moravčík, M. Schmid, N. Burch, Lisy, D. Morrill, N. Bard, T. Davis, K. Waugh, M. Johanson, and M. Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337):508 513, 2017.
[31] A. Nemirovski. Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229-251 2004.
[32] Y. Nesterov. Excessive gap technique in nonsmooth convex minimization. SIAM Journal on Optimization, 16(1):235-249, 2005.
[33] V. Perchet. Approachability Calibration and Regret in Games with Partial Observations. Phl) thesis, PhD thesis, Université Pierre et Marie Curie, 2010.
[34] A. Rakhlin and K. Sridharan. Online learning with predictable sequences. In Conference Learning Theory, pages 993-1019. PMLR, 2013.
[35] S. J. Reddi, Kale, and Kumar. On the convergence of Adam and beyond. International Conference Learning Representations (ICLR), 2018.
[36] V. Syrgkanis, Agarwal, H. Luo, and E. Schapire. Fast convergence of regularized learning in games. Advances in Neural Information Processing Systems, 28, 2015.
[37] O. Tammelin, N. Burch, M. Johanson, and M. Bowling. Solving heads-up limit Texas hold' em. In Twenty- Fourth International Joint Conference on Artificial Intelligence, 2015.
[38] B. von Stengel. Efficient computation of behavior strategies. Games and Economic Behavior, 14(2):220-22 226,22266622 1996.
[39] M. Zinkevich, M. Johanson, M. Bowling, and C. Piccione. Regret minimization in games with incomplete information. In Advances in neural information processing systems, pages 1729-1736, 2007.
12

---

A Self-Play Framework
The (vanilla) self-play framework for two-player zero-sum EFGs is presented Algorithm The
Algorithm 4 self- play-playyaa framework
I: Input: Regmin x regret minimizer over A' Regminy a regret minimizer over y
2: for 1..... T do
3:
Regmin x (-)
4: y/: = Regminy (-)
5: The first player observes the loss vector Ay; 1R
6: The second player observes the loss vector A AUx, x E R
self-play framework can be combined with alternation, simple variant that is known lead to significant empirical speedups, for instance, when CFR and predictive CFR are used regret minimizers [37 6 7 When using alternation, at iteration & the second player is provided with the current strategy of the first player before choosing its own strategy. We describe the self-play framework with alternation Algorithm
Algorithm 5 helf-play framework with alternation
1: Input: Regmin regret minimizer over X, Regminy regret minimizer over y
2: for .,....77 7 do
3: = Regminx x (-)
4: The second player observes the loss vector - 2g E R
5: y/ = Regminy (-)
6: The first player observes the loss vector Ay; R11+1
B Counterfactual Regret Minimization (CFR), CFR* and Predic- tive CFR
Counterfactual Regret Minimization (CFR, (3 is framework for regret minimization over the treeplex. CFR runs regret minimizer Regmin, locally at each infoset j E J of the treeplex. Note that here Regmin, is regret minimizer over the simplex A with n, |Ayl i.e. over the set of probability distributions over Aj. the set of actions available at infoset j E J. Let a! E A be the decision chosen by Regmin, at iteration t in CFR and let l, E R"+1 be the loss across the entire treeplex. The local loss E Th that CFR passes to Regmin,
lg = (i,(i,a) + Σ V',.OEAA,JEE
f'EC,u
where V2 is the value function for infoset j at iteration t, defined inductively:
V = Σ xh.ae,1i.))) + Σ
REA;
J'ECja
The regret over the entire treeplex can related the regrets accumulated at each infoset via the following laminar regret decomposition [3
T = max Reg
Fr & (,) S
max RET
Sp, Reg (a')
GET
JEJJ
with Reg. (+)) : Σ { al ())) the regret incured by Regmin' for the sequence of losses
Bi.... by against the comparator á) E A Combining CFR with regret minimizers at each information set ensures Reg" = (TT).
13

---

CFR 37 corresponds to instantiating the self- framework with alternation (Algorithm 5 and Regret Matching" (RM" as presented in ( as a regret minimizer at each information set. Additionally, CFR' uses linear averaging, i.c., it returns Tr such that Ty = " wi Ei= w with wi = t. We
also consider uniform weights (w; = 1) and quadratic weights (w = f²) in our simulations (Figure
10
CFR guarantees ((1/v convergence rate to a Nash equilibrium.
Predictive CFR"(PCFR", [66] corresponds to instantiating the self-play framework with alternation
(Algorithm 5) and Predictive Regret Matching* (PRM") as regret minimizer at each information set.
Given simplex Ad, PRM" is regret minimizer that returns sequence of decisions 21; Zr E A
as follows:
R2 = Re (R+ -nggg---11 (1(22-1,
21 R
(PRM")
R++1 = pg (R, - (21, Et)
where the function g is defined in (5). Similar to CFR for PCFR* we investigate different weighting not known if the self-play framework with alternation, combined with PCFR", has convergence guarantees, but PCFR* has been observed to achieve statc-of-the-ar practical performance in many EFG instances [16]
schemes our numerical experiments (Figure TT..
C Comparison with
In this appendix, we describe the results in I connecting Blackwell approachability and regret minimization, and we highlight the main differences with our framework described in Algorithm [|
In particular, Abernethy et al. [ describe meta-algorithm connecting Blackwell approachability and regret minimization. Given a decision set X c IR" assumed be convex and compact, Abernethy al. consider lifted ser X {H} x X C R=++1 with
K == max || =EX
Abernethy al. [ then constructs regret minimizer over by considering a Blackwell approacha- bility instance, where the target set is defined as cone(X') C Ra+1, the decision is X' C R"," and the instantaneous loss time / is (ms,.e)) -e) E B with E R the loss vector when the ~
decision maker chooses ae X. The average aggregated loss vector u, E R is updated using regret minimizer over cone(A") and the decision maker in the Blackwell approachability instance chooses the sequence of decisions I1, ...,,.. By to ensure that (fwr)rz approaches the target set, defined as the polar cone of cone( We refer to Section 4 in [1 for more detail on this construction.
As evident from the description in the previous paragraph, our framework described in Algorithm | differs from the meta-algorithm from [ in various ways. In particular, one were to directly use the reduction from [1] for deriving regret minimizers over treeplexes, one would need to consider T = {x} x T, with T a treeplex and ạ max ||0||2, and one would need to consider bound for the value of k, which could be conservative for large-scale EFG instances. However, since we have designed Algorithm (ppritimmsssecificalll for treeplexes as decision sets, we do not need to lift the set T by adding an additional dimension depending on the maximum f--norm over T. We can circumvent relying k and therefore obtain simpler, more practical framework as in Algorithm byy exploiting the structure of treeplexes. This is because the variable Zg associated with the empty sequence always has value of 1: Zg 1, and we can then exploit the fact that T {x ga+l (x, a) 1}, as in the proof of Proposition 3.1
Another fundamental difference with 1 is our positioning and our objectives. Abernethy et al. analyze Blackwell approachability with adversial losses and in more theoretical way (e.g., no implementations or simulations), whereas we focus on practically solving EFGs with Blackwell approachabilityy i.e., we focus on the game setting and on explaining the empirical performance of CFR direct application of the results in I would only result in algorithms achieving O(1/VT) convergence rates, and for which no concrete implementations are known. In contrast, provide
14

---

details on the practical implementations of our algorithms (Proposition 4.4 and Appendix H we are the first to highlight the role of stepsize invariance, which only makes sense for EFGs (and not for the adversarial loss setup in [], and in our EFG applications we can obtain faster 0 /T)
convergence rate (e.g. for Smooth PTB", see our new results as in Proposition 4.5 and Theorem which is impossible against adversarial losses.
D Proof of Proposition 4.1
Proof. The proof of Proposition based on the following lemma.
Lemma D.I. Let C C I be convex cone and let u E IR", > 0. Then
[m(mu) = (u))..
Proof of Lemma D.1
We have, by definition,
llc())) = arg min R 17uu12- REC
Now we also have
min R - r/ull2 l|22-120 = 7 min R REC
R u112
min R 2//2
Rec
1)
REC
where the last equality follows from C being cone. This shows that arg minnec | 22--1p -1jul22 is attained at 17TTc (u), i.e., that (nju) (u).
L
We are now ready to prove Proposition 4.1 For the sake of conciseness we prove this with mn
mr = 0; the proof for PTB* with predictions is identical. In this case, R. RG, V 1 1. Consider the sequence of strategies क i,.... Ø7 and Ri,..., Rr generated by PTB" with step size of We also consider the sequence of strategies #1, 2T and Ri...., Rr generated with a step size 7) 0. We claim that
3t = Ft, R. = n Rr. AAE (1....,T}.
We prove this by induction. Both sequences of iterates are initialized with R₁ Ri = so that i = 11 Therefore, both sequences face the same loss &₁ at / 1, and we have
R2 = (z ())
TTc (- fz li)) n2
Let us now consider an iteration t 2 1 and suppose that i, = It. Rs = n2 Since i, 2, then both algorithms will face the next loss vector l, Then
R Te(R, nf(x,, (()
f Li) Re(n fofRa-nf(ze
=yme (Re - f(x le))
=mR++1
which in turns implies that 20+1 1 We conclude that æt 3i, V 1, I,.., T.
E Comparison Between RM* and PTB*
For the sake of discussion, assume that the original decision set of each player is simplex A and that there are no predictions: m, = 0, V t
PTB' over the simplex. For PTB", the empty sequence variable ze is introduced and appended to the decision A The resulting treepplex can be written T = {1} x Ad, the set C becomes C = cTne(T) cone((1) A and = (1, 0) E Id+1 with 1 on the first component related to Ve and 0 everywhere else. this case, PTB" without prediction exactly the Conic Blackwell Algorithm+ (CBA* (22)). Crucially, to run PTB" we need to compute the orthogonal projection onto cone(T) = cone( (1) x A) at every iteration, which can not be computed closed-form, but can be computed in Oín log(n)) arithmetic operations (sce Appendix G.1 in (22).
15

---

Regret Matching". RM" operates directly over the simplex A without the introduction of the empty sequence zæ, in contrast to PTB" which operates over {1} A Importantly. in RM", at every iteration the orthogonal projection onto R4 can be computed in closed form by simply thresholding to zero the negative components (and leaving unchanged the positive components): lg (z) (max(za žg. 0}) for any IRd.
Empirical comparisons over simplexes. The numerical experiments in 22 show that CBA" may be slightly faster than RM" for some matrix games in terms of speed of convergence as a function of the number of iterations, but it be slower in running times because of the orthogonal projections onto cone([1) [1] x A) at each iteration (Figures 2,3,4 in (22)). When is a treeplex that is not the simplex, introducing Fig also changes the resulting algorithm but not the complexity of the orthogonal projection onto cone(T), since there is no closed-form anymore, even without Tg. As a convention, in this paper, will always use 2e in our description of treeplexes and of our algorithms since is convenient from a writing and implementation standpoint.
Overall, notice that in the case of the simplex introducing the empty sequence variable ze radically alters the complexity per iterations and the resulting algorithm, a fact that has not been noticed in previous work.
Empirical comparisons for EFGs. For solving EFGs, (2] combine the CFR decomposition with CBA' and compare the resulting algorithm with CFR' (i.c., combining the CFR decomposition with RM"). The authors in (2) observe similar numerical results for the cases of simplexes: the resulting algorithm may slightly outperform CFR in terms of duality gap achieved after a certain number of iterations, but is outperformed by CFR in terms of duality gap achieved after certain computation time, because of the orthogonal projection required at every iteration at every simplex present the treeplexes of each player.
F Proof of Proposition 4.5
Proof of Proposition 4.5
1. Let Rs = R2/l| R2lp be the unit vector pointing in the same
direction as R2 and let = ((R), R2) Rg the orthogonal projection of R₁ onto
{als a a R). We thus have || Rall2 2 [ h1ll.
2. Let p [R
(R.a) R2. Since p and R2 are colinear, we have
R
R2
R
P
RR,a)
(R2
a)
(R
(p.a)
Additionally, by construction, (p, a)
(RI, a), so that we obtain
R
R₂
R
p
(R
a)
R2 a)
(R
(R a)
= (R
Ri - -pllz-
Note that (Ri, a) 2 since RS E cone(T) and T c {o E R | (x, a) 1}. Assume that we can compute D > O such that
R: -pllp hllz
< D. Then we have
R
R2
D
D
<
R1
h1l2
R4 R2
R1
(R2 a)
a)
R2 a)
3. The rest of this proof focuses on showing that
|R: pllp
< Ω with = max x E T).
R1 - hl22
Note that (R) p, a) 0. Therefore, [Rll (R. p) and
aa a can be completed to
form an orthonormal basis of RD. this basis, we have
(Ri p. RR)
(a, Ra)
R
pl
|
2
16

---

Note that by construction we have ||2l22 1. Additionally, R2 E cone(T) so that there exists > 0 and E T such that R2 By construction of R2, we have R2 a l || and (a, a) = 1. This shows that
(a, R2))
((a, x))² a 2
||a|
2 a l2
with S2 max [| æ E TJ. Recall that we have chosen Overall, we have obtained
(1, 0) so that |a]|| 1.
[ p.
p. R2))
Q
|R p11
From the definition of the vectors p, and f2g we have
(R) p, R2)
pp h2l2
R 211
R1 -plp
Hence, we have
|pp - 12l2 - (1
RR p1
??
This shows that ||
R1
h
112
2
1
| p12--
[22
4. We conclude that
R1 (R1.a) a)
R₂
Ω
RR R2
(R2,
a) 2
max (Ri,a), (R2, a}}
G Proof of Proposition 4.4
In this section we show how to efficiently compute the orthogonal projection onto the cone C == cone(7). We start by reviewing the existing methods for computing the orthogonal projection the treeplex T. This is an important cornerstone of our analysis, since the treeplex T and the cone C share analogous structure:
= (o E RT
Te 1, Σ Iju = aEA;
C = (x R
Σ Tp,
20 were the first show algorithm for computing Euclidean projection the treeplex. They do this by defining a value function for the projection of a given point y onto the closed and convex scaled set I.Z, letting it be half the squared distance between y and I.Z for / Rx
1
(1, 3) = min
2
2 ZErZ
20 show how to recursively compute Az y). the derivative this function with respect to t, for given treeplex, since treeplexes can be constructed recursively using two operations: branching and Cartesian product. In the first case, given & treeplexes Zi,..., Zk, then = (a, _=[]]21.... x [k] 23 A 2 ZiVi E [k]] is also treeplex. In the second case, given it treeplexes Z1, Zı.... ZR. then - 2, x ... x Z₁ also a treeplex. In fact, letting the empty set be a treeplex as a base case, all treeplexes be constructed in this way.
However, 20 did not state the total complexity computing the projection, instead only stating the complexity of computing >a y) given the corresponding λz, (t, y:) functions for the treeplexes Z,
17

---

that are used to construct 2 using E [k.. They state that this complexity is O n), where n is the number of sequences in Z. Their analysis involves showing that the function Ag (t, y) is piecewise linear.
17 also consider this problem, generalizing the problem weighted projection the scaled treeplex, by adding an additional positive parameter w E 1850:
1 2z (t. (t, y. == min ZE12 2
2
1=1
They do similar analysis 20 by showing how compute the derivative Az y: w)) of Uz (f, y, w) with respect to t recursively. They show that + Az y, w) are strictly-monotonically increasing piecewise-linear (SMPL) functions. We will follow the analysis in [7]. letting w 1.
We first define standard representation of a SMPL function.
Definition G.1 (117). Given a SMPI. f, standard representation is an expression of the form
f(x) 5 +-g + Σ as max -3,}
valid for all x E dom(J), NU (0), and B1 ..... < Bs. The size of the standard representation defined to be S.
Next, we prove the following lemma, showing the computational complexity of computing the derivative of the value function for given treeplex.
Lemma G.2. For given treeplex Z with depth d, n sequences, leaf sequences, and mn infosets, and y R", w R5o a standard representation of Az(t, y, w) can be computed in O(dn log(l + m)) time.
Proof. We will proceed by structural induction over treeplexes, following the analysis done by The base case is trivially true, because the empty set has no sequences or depth.
For the inductive case, will assume that it requires O 1 1)m log(1 + m)) time to compute the respective Euclidean projections onto the subtreeplexes that we use to inductively construct our current treeplex, where
1 the depth of given subtreeplex, is the number of sequences in the subtreeplex, and m is the total number of sequences among both players and chance corresponding to the game from which the treeplex originates.
We will use two results shown in Lemma 14 17
Lemma G.3 (Recursive complexity of Euclidean projection for branching operation (77). Consider a treeplex Z that can be written as the result of a branching operation on treeplexes Zi...., Ze:
= xx x [I]
x E Dgy z; Z [k]].
Let have n sequences and let y, w E R", and let yli] and wiil denote the corresponding respective components of y and w for the treeplex Z,
Then, given standard representations of Xz, (t, Yis wi) of size n, for all E [k], where n4 is the number of sequences that Z, has, a standard representation of X2 (t,t, y, w) of size can be computed in O(n log k) time.
Furthermore, given a value of 1, the argument x which leads to the realization of the optimal value of the value function,
be computed in time (n).
Lemma G.4 (Recursive complexity of Euclidean projection for Cartesian product [7]). Consider a treeplex Z that can be written Cartesian product k. treeplexes ZI...., Z
Z Zi X Zk-
Let Z have n sequences and let y, R", and let yld and wiil denote the corresponding respective components of y and w for the treeplex Z,.
Then, given standard representations of Xz (1, yi, we) of size for all i E [k], where is the number of sequences that 2, has, a standard representation of Az (1, y, w)) of size n can be computed in On log k) time.
18

---

First, we consider the case that the last operation used to construct our treeplex was the branching operation. Let the root of of the treeplex be called j. Define 2; as the treeplex that is underneath action E A Let denote the number of sequences in 2,, denote the number of infosets in 2,, 1 denote the number of leaf sequences in 2,, and subtreeplexes.
be the maximum depth of any of these
Given standard representation λz, (t, yis w.) of size n, for all E [|A,]]. by Lemma G.3 takes ( log [Ayl) time to compute a standard representation of Az y, w) of size n. By induction, it takes O ((d - 1), log m²) to compute Az (1, yı. w;) for treeplex 2, Thus the total computation required to compute (t, y: w)) is
Oon ((nlog|A)))) + Σ O((d 1), log(1, + mi)) = On log A,1) + Σ ((d- ((d= log(1 + m))
:E|1A,1]
iE[1A,l
O(n A2)) + (Od -1
Σ
my log(( + m))
KEILA;
O log A,)) + ((d - 1)m log(1 + m))
= Oogl + m)) + ((d 1)m log(1 + m))
= Odn + m))
since have necessarily that 1 and m, for all
[|Ai]]. EiE[AA S n, and
[A,] S l + m.
Second, we consider the case the last operation to construct our treeplex was a Cartesian product. Let Z 2, x... 2, and again define n, the number of sequences in 2,, my the number of infosets in Z,, 4 as the number of leaf sequences in Z,, and d - 1 as the maximum depth of any of these subtreeplexes.
Given a standard representation of Az, (t. yr, w;) of size n, for all E [M]. by Lemma G.4 it takes On log k) to compute standard representation of (z y, w) of size By induction, it takes ((dd I)n, log(4: m.)) to compute λz, (1, Vi, wx) for treeplex 2, Thus the total computation required to compute Az (t, y. w. w) is
O(nlog k)) + Σ O((d-1)m 1)ldd-1n,hae log(4, + m.)) = On k.) + Σ O(d 1)m, log(1 + m))
kE(M]
iE(M]
O log k)) + ( - 1)
Σ T
n. log(1 + m))
(nnoo k) + O(d - 1 n log(1 + m))
O(n log m) + ((d 1) log(1 (1 + +))
Oldn m))
since we have necessarily that 1, < and m, S m for E [Mi], and m.
Finally, we are ready to prove the main statement.
Proof of Proposition 4.4 By Lemma G.2 we know that we can recursively compute standard representation of 22 (t,y, w) Odn log( +m)) time. Assuming we use this construction, invoking Lemma G.3 given an optimal value of t, we can compute the partial argument corresponding to the values of the sequences that originate the root infosets, which allow the optimal value to be realized for the value function. Then, we can use optimal arguments for these sequences recursively at the subtreeplexes to continue computing the optimal argument at sequences lower on the treeplex. We can do this because in the process of computing the derivative of the value function of the entire treeplex, we have also computed the derivative of the value function for each of the subtreeplexes. Thus, once have computed an optimval value of for the value function at the top level, we can
19

---

do top-down pass to compute the optimal values for all sequences that occur at any level in the treeplex. This is detailed in the analysis done the proof Lemma 14 [T7].
In order to pick the optimal value of & for the value function, since (- y. w) is strictly increasing.
only have to consider two cases: (0, y, w) value function (z y, w) will be minimized when Az computed using the standard representation (it will be necessarily 0 somewhere because it is strictly monotone). In the second case, since Az(-, y, w) is strictly monotone and Az(0, y, w) 2 O, we must have that (z(- y, w) 2 0, which means that U2 (+, y, w)) minimized at t 0.
and (0 y: w)) 2 O. In the first case, the
) is equal to 0, and this can be directly
H Practical Implementation of Smooth PTB*
We have the following lemma, which shows that the stable region Cy admits relatively simple formulation.
Lemma H.1. The stable region
Cz == cone (RE Rut1 (R, 2 Ro}
can be reformulated as follows:
C2 {oa a Ro, x E T
{a Byt [Ig Ro, Σ Vi J}. aEA,,
Proof. By definition, we have
C2= = (R E cone(T) | (R, a) 2 Ro].
Note that for R E cone(T), = ar with a 2 and (ax, a) 1. Therefore, for E we have (R, a) 2 Ro = a 2 Ro. This shows that
write
C2 = fax a 2 Ru, x E TT.
Now let x E Cz, i.e., let æ = az with a 2 Ro and æ E T. Since d E T, we have 2g = 1, so that ig 2 Ro. Additionally, have & 2 EnEA, Hja Sp,, V j E J. Multiplying by 2 Ro. we obtain that æ 2 and EeEA, 2ja = p, A j E J. Overall we have shown
C₂ S (0 E R ( 2 Ru, Σ
Ija - xpp Vje. 0j.
aEA,
We now consider æ fx R [g 2 Ro. EneA, Tja Tja = -p,, q E J, x 2 0} with +
Then x = a with a = Ig, so that a 2 Ro and
Ija V Σ
Σ aed;
Ija = Ip
- AJE..
a
REA;;
Therefore
(o Ru+l
[r 2 Ro, Σ
= = 0) C2
rEA,
This shows that we have
C2 fxr I= 1x0 2 Ru, Σ
=ja= 0).
aEA,
Proposition H.2. For a treeplex T with depth d, number of sequences n, number of leaf sequences I, and number of infosets m. the complexity of computing the orthogonal projection of a point y E 1 onto C2 {ax > Ro. T) is ((dn log(l + m)).
20

---

Proof. The proof is the same as that for Proposition 4.4, since the derivative of the value function can be computed in O Odn log(1 + m)) time. However, this time, we have an additional constraint that we check the sign Ro-
t 2 Rg. Thus instead of checking the sign of (z y, w) at
( y, w) < O, then because Az( y, w) is a strictly monotone function, the function will be 0 for some value of t, and this is exactly t", which minimizes the value function with respect to when t 2 Ru- On the other hand, if Az 3g y. w) 2 O, then again because the function strictly monotone in t, argument as in the proof of Proposition 4.4) since we have computed the standard representations of the derivatives of the value functions all of the treeplexes,
know that the value function must get minimized at t" Ru- Using the same
do top-down pass to compute the argument which leads to the optimal value of the value function.
I Proof of Theorem 4.7
Proof of Theorem 4.7 For the sake of conciseness write ff ((x.MMy and ff²
f M x,).
From our Proposition 4.2 we have that, for the first player,
T (z, - 2. My = - R.).).
T
Σ
[=1
Now Σ (R RR f() is the regret obtained by rumning Predictive OMD on C2 against the sequence of loss f y.,. f7. From Proposition 5 in [16), have that
T
T
T
Σ - Nt, f t=1
Σ
nS
121l
R
R
2
811
Since R, E Cz, we can use our Proposition 4.5
to show that
|
R
R 12.
R
R
This shows that
|
Σ R R
f2)
S
+ 1)
f
f
112
R
R
2n
8
which gives, using the norm equivalence || 112 1|- S vn 11|
|12, the following inequality:
E RR- Rt, 5i)
1st
f 12
R R2+111
2n
80 + 1)m
The above inequality is a RVU bound:
T
(R. f. < a 8
Σ
llft
f-
R +
R
1=1
[=1
with
Ril
RC
a:
2n
3 = 11,
802 (n 1)
(13)
To invoke Theorem 4 in [36]. be done can rescaling f My, and f M x,, particular, we know that
we also need the utilities of each player to be bounded by 1. This can
My <
M MMle 1lll2 | Ω
21

---

with || = max f (Ais) jelm+1 (A)))( lla and Ω max(max 1| E N,y y}. This corresponds to multiplying B in max (I) 1IM.lle,, To apply Theorem in need the same condition for the second player, we take
13 by || 5 with || ==
36 we also need / S 7. Since we
R= (V (Vs
Under this condition on the stepsize, we can invoke Theorem 4 in 36 to conclude that
|
- E Re ,1"
"
Since the duality gap is bounded by the average of the sum of the regrets of both players 19 and replacing 17 by its expression, we obtain that
20 1
(Dr, My)
min (a., M I #EX
NEY
n T
AdaGradTB" and AdamTB*
AdaGradTB'. We introduce AdaGradTB' in Algorithm 6
Given matrix and vector y R=+1, let
dy) be the diagonal matrix with on its diagonal and 11 (y) = arg min (x y, A(x x y)). We first show that AdaGradTB" is regret minimizer.
Proposition J.1. Let 01 2T be computed by AdaGradTB'. For max.er +
we have
mAX Ei a, La) 2n E V (fi(æe, E.)
We omit the proof of Proposition J.I for conciseness; it follows from the regret guarantees of AdaGrad (Theorem in (12) and Proposition 3.1 We conclude that combining AdaGradTB' with the self-play framework ensures O(1/vT convergence rate.
Algorithm AdaGradTB*
1: Input: 77,
2: Initialization: R 80 go 0 1
3: for = I,..., T.....Too Todo
4: T; Re/(Re, a)
5: Observe the loss vector l E Ru+1
6:
8; $1-1 f(E l @ f( Le)
7:
H; = diag (8a=- el)
8:
R E I (R. - f(x
AdamTB". We present AdamTB", instantiation of Algorithm inspired from the adaptive algorithm Adam 255 in Algorithm 7 Since Adam is not necessarily a regret minimizer [35], there are no regret guarantees for AdamTB*. We choose to consider this algorithm for the sake of completeness, since Adam is widely used in other settings.
K Details on Numerical Experiments
K.1 Additional Algorithms
Single-call Predictive Online Mirror Descent (SC-POMD). We present SC-POMD in Algorithm This algorithm runs variant of predictive online mirror descent with only one orthogonal projection
22

---

Algorithm 7 AdamTB
1: Input: 7, > 0, 1,31, 32 00.1
2: Initialization: R. = E g=+l 30 = = 6 R"+l
900 = =
3: for = 1.......1 -' do
4: 2; = R2/RR,,
5: Observe the loss vector l E Ra+1
6:
S B28;-1
B2) (2t, (4) @ f(z),1)
[tt
7:
& $1/(1 (35
8:
gr 319h-1 + (1
B1)5 (1t)
9:
gr gt (1 81)
10:
H. diag (V3, + c1)
11:
R E I (R - ---n HH g1)
every iteration 24 The pseudocode from Algorithm g corresponds to choosing the squared 22-norm as distance generating function in principle, other distance generating functions are possible, e.g. dilated entropy [15]. Combined with the self-play framework, SC-POMD ensures that the average of the visited iterates converges to Nash equilibrium at rate of O(1/T) similar to the variant of predictive online mirror descent with two orthogonal projections every iteration [15]
Algorithm 8 Single-call predictive online mirror descent (SC-POMD)
1: Input: v) >
2: Initialization: To = tu L-1 =0 R1+1
3: for t
do
4: Iz = 11 (zt-1 n7 1
- 222))
5: Observe the loss vector l E Ru+1
K.2 Algorithm Implementation Details
All algorithms are initialized using the uniform strategy (placing equal probability on each action at each decision point). For algorithms that not stepsize invariant (Smooth PTB" and SC-POMD), try stepsizes in 7) E (0.05, 0.1, 0.5, 1, 2, 5) and we present the performance with the best stepsize. Ro 0.1. For both AdaGradTB* and AdamTB", use d 1 10-6 and
For Smooth PTB",
for A we use 31 = 0.9 and B2 = 0.999.
K.3 Comparing the Performance of our Algorithms
In Figure 4
compare the performance of TB', PTB", Smooth PTB", AdaGradTB* and AdamTB*.
be seen that PTB" and Smooth PTB" perform similarly, both when using quadratic averaging and when using the last iterate, and they generally outperform the other algorithms. In Kuhn, Liar's Dice, and Battleship, the last iterate seems to perform quite well, whereas Ledue and Goofspiel, the quadratic averaging scheme works better. AdamTB* seems to not converge in any of the games, which is not surprising, because it does not have theoretical guarantees for convergence.
K.4 Individual Performance
In Figure 5ig:scpoodd we compare the individual performance of TB", PTB", Smooth PTB". AdaGradTB" AdamTB*, CFR', PCFR" and SC-POMD with different weighting schemes, with and without alternation. We also show the performance of the last iterate. The goal is to choose the most favorable framework for each algorithms, in order to have fair comparison. We find that all algorithms benefit from using alternation. CFR* enjoys stronger performance using linear weights, whereas PTB*, PCFR* and SC-POMD have stronger performances with quadratic weights. For this reason this the setup that present for comparing the performance of these algorithms in our main body (Figure 2).
23

---

Kuio
Lodie
Lise's Dice
Bunleship
111
10
olp
10
10r1
10
30
11
102
11
10F
Smooth QEADEA
quadaac
Figure 4: Convergence to Nash equilibrium function of number of iterations for TB' with quadratic averaging, PTB" with quadratic averaging and last iterate, and Smooth PTB' with quadratic averaging and last iterate. Every algorithm is using alternation.
Kihr
11f
IIf
po
10
10-2
10
12
20
10
30'
10
10
20'
10
10
10
10
107
10'
117
107
Figure 5: Convergence Nash equilibrium a function of number of iterations using uniform, linear, and quadratic averaging, as well as the last iterate, with and without alternation for TB".
NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We provide all proofs.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
This is done in the main body.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
24

---

Dise
Goofigidl
Banlehip
Daaliy pp
10-5
107
10
11f
10"
10-10
10
11
10
10
11
10
10
10'
10
Berations
PI qudeie alcreatee
Figure 6: Convergence Nash equilibrium as a function of number of iterations using uniform, linear, and quadratic averaging, as well as the last iterate, with and without alternation for PTB"..
Kiita
Ledue
Liar's Dics
Goufigid
Batkesip
Duatyy gip
10
10771
10
10
10m
10:
10
10m7
16
11 Berainss
licnstios
laratiion
licnation
Rxcation
Smooth T18" anfsen
Smauch 1D
Secoth F12
Smouth F78"
Smouth Fi8" unformiieermiinn
Seauch *B
Smooth P18 kat shonmans
Figure 7: Convergence to Nash equilibrium as a function of number of iterations using uniform, linear, and quadratic averaging, as well as the last iterate, with and without alternation for Smooth PTB".
Kihe
Ledic
Lav's
Gootyppe
Batteshi
IIf
Dadlt
10
10
10-
10
10
10
177
-0'
10'
10F
10
10
10'
10
Denaiioss
Dersiams
Figure 8: Convergence to Nash equilibrium as function of number of iterations using uniform, linear, and quadratic averaging, as well as the last iterate, with and without alternation for AdaGradTB*.
Kithi
111
Ledus
211
Lib''s Dice
10"
Goohspel
10
Hotteehip
Dualty
20
10
11F
11P
Peration
Herraions
Figure 9: Convergence to Nash equilibrium as function of number of iterations using uniform, linear, and quadratic averaging, as well as the last iterate, with and without alternation for AdaGradTB'.
Kilts
Lodae
Liw's Dice
GuoGpii
Butteship
Donity pi
10
1If
111
10
10
10
11F
Incutions
heratioss
Irccatons
Ineorions
Ch1 seikers
of gadsic
CE8 selfers Aturatioon
CPF Tacar airmatioo
one
be ahamatin
Figure 10: Convergence to Nash equilibrium as a function of number of iterations using uniform, linear, and quadratic averaging, as well as the last iterate, with and without alternation for CFR
25

---

Ledue
Lia''s Dise
Godfgid
Batlehie
10
11f
Daalty gap
107
10"
101
10
10"
10
10
10 Dersionn
10 Ticrations
10
10
lienatoon
Tecrations
Damations
quire:
PC'1 bat
FCW! undcrm Acreuxee
skoraton
PC lot ehomaazs
Figure 11: Convergence to Nash equilibrium as a function of number of iterations using uniform, linear, and quadratic averaging, as well as the last iterate, with and without alternation for PCFR
Kihn
Lecha
Lier's Diee
Gouferiel
Batkkship
pip
10
307
10
10-1
10"7
10
100-2
licnstios
lacrationn
licration
3C- F210 an
2C- PC10 Baiar
Sc- 700 qcc.
SC 700
3C 7210 anfene shomadoo
PCD laau shoralkon
700 quaiiiii Alurmation
5C NBD dlscratto
Figure 12: Convergence Nash equilibrium as a function of number of iterations using uniform, linear, and quadratic averaging, as well as the last iterate, with and without alternation for SC-POMD.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-tex system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faireess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
This is done in the main body and in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
26

---

Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
We do so in the main body and in the appendices (Appendix Appendix K).
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g.. with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification:
We plan to do so after the revision process.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
27

---

The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ /nips..c/puul
ssionPo licy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if' applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification:
We do so in the main body and in the appendices.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: No random experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
28

---

Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification:
We do so in the main body and in the appendices.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
The research conducted in the paper conform with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This research focuses on foundational questions. There is no direct societal impacts of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymentt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
29

---

If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks. mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Not applicable to our paper. There no release of data.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual- use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We provide citations to the packages use.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, ppaper swi thcode. com/ com/datasert has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Not applicable to paper.
Guidelines:
The answer NA means that the paper does not release new assets.
30

---

Researchers should communicate the details of the dataset/codeemmodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Not applicable to our paper.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: Not applicable to our paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
31


Reviews:
[{"review_id": "oBrvR1q4n5", "reviewer": "Reviewer_WD2M", "summary": "This paper studies computations via regret minimization of Nash equilibria in zero-sum extensive form games (EFG) with the perfect recall assumption.\nThe actions of the players are a sequence of polytopes (treeplexes).\n\nIn prior work (counterfactual regret minimization framework), this was solved with methods that run regret minimization locally for a phase in the game on the corresponding information sets.\nCommon regret minimization algorithms used are regret matching that operates on the simplex and is based on Blackwell approachability, or online mirror descent (OMD). \nUsing regret matching as a local optimizer showed a better empirical performance. \nThis paper to develop Blackwell approachability-based algorithms directly for the treeplexes (instead of locally). The benefit of using Blackwell approachability is a property named \"stepsize invariant\", which means that stepsizes across different information sets, and the iterates of the algorithm main do not depend on them. This is different from running OMD on the treeplex. \n\nSeveral algorithm instantiations are also provided and tested via numerical experiments. \nThe main message of the papers is to claim that information sets stepsize invariance seems like a crucial property for good empirical performance  and shed light on the strong empirical performance with such property, such as CFR+ (Counterfactual regret minimization with regret matching+ as a local optimizer)", "questions": "-", "limitations": "The limitations are properly addressed.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The computation of Nash equilibria in zero-sum extensive form games via iterative methods is fundamental in \"learning with games\"/\"self-play\".\nThis paper studies natural approaches to tackle this problem and perhaps sheds light on an interesting property for strong empirical performance. \n\nAlthough I'm not an expert in the field, the authors give enough background to explain how their approach is related to prior work. \n\nIn my understanding, this paper makes a significant contribution.", "weaknesses": "Couldn't find Weaknesses", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your time reviewing the paper and for your positive review. If you have any questions about our work, we remain available during the rebuttal period.", "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": "OouhL3BTlv", "reviewer": "Reviewer_n7s4", "summary": "This paper designs a new algorithm for computing minimax equilibria in two-player zero-sum extensive form games. It is well-known that one way to do this is to have both players run no-regret algorithms against each other and take the time-average of their strategies. The main innovation of this paper is designing a new class of no-regret algorithms for extensive form games via a reduction from Blackwell approachability. \n\nIn particular, minimizing regret in a zero-sum extensive form game is equivalent to minnimizing external regret in an online linear optimization problem over a polytope called the treeplex. The authors show that if you cast this OLO problem as a Blackwell approachability problem, and then perform an approachability to OLO reduction (along the lines of Abernethy et al.), you can reduce the original OLO problem of minimizing external regret over the treeplex to minimizing external regret over the conical hull of the treeplex. \n\nIf you use predictive online mirror descent (with Euclidean distance) to solve the resulting OLO problem, you get an algorithm for the original problem the authors call Predictive Treeplex Blackwell+ (PTB+). This algorithm is stepsize independent and has O(1/sqrt(T)) convergence to equilibria. If you “smooth” this algorithm by projecting onto a truncation of the cone, you get a different algorithm the authors call Smooth PTB+, which the authors show has O(1/T) convergence to equilibria (but is no longer stepsize invariant). \n\nThe authors implement these algorithms (and some other transformations of existing algorithms, e.g. Adam and AdaGrad) and compare them experimentally to a range of existing algorithms. They find that PTB+ performs the best out of these new algorithms, but still is significantly worse than the state-of-the-art PCFR+ (predictive counterfactual regret minimization) on some games. The authors hypothesize this is due to the fact that PCFR+ has an even stronger form of stepsize invariance than PTB+.", "questions": "Feel free to reply to any part of the review above.", "limitations": "Limitations adequately addressed.", "rating": 4, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "Extensive-form game solving is one of the big successes of the theory of learning in games (with tools like regret minimization being directly used to construct superhuman-level algorithms for games like poker). This paper proposes a class of novel algorithms for extensive form game solving and both theoretically and empirically analyzes their performance (showing that this class of algorithms can have theoretical convergence rates on par with the best known algorithms). This analysis is relatively thorough and the paper is well-written and easy to read.", "weaknesses": "Overall, I am a little unimpressed by the results of this paper. While it is true to the best of my knowledge that this class of algorithms (as applied to extensive-form game solving) is novel, it doesn’t really seem like they unlock any new guarantees that were not previously achievable. Several times throughout the paper the authors emphasize that this is the first algorithm “based on Blackwell approachability” to achieve these guarantees, and that this resolves an interesting open question. But it is not clear to me that “based on Blackwell approachability” is really a well-defined concept (perhaps you could recover some existing algorithms via other applications of approachability) or even a desired one.\n\nI also feel that the use of Blackwell approachability here is a little superfluous. The authors use Blackwell approachability to reduce an OLO problem on T to an OLO problem on cone(T). The eventual reduction is very simple (it essentially boils down to “projectvizing” T by adding an extra coordinate) and it is easy to see directly that the regret of the cone(T) OLO algorithm bounds the regret of the overall algorithm (that said, it is a nice observation that OLO algorithms for cone(T) seem give rise to \"stepsize invariant\" algorithms for original problem). It should also be pointed out that there has been significant work on Blackwell approachability since the work of Abernethy et al., including several papers which resolve some of the deficiencies the authors point out in Appendix C (which mostly stem from the fact that Abernethy et al. only consider the L_2 norm). I would recommend the authors look at “Refined approachability algorithms and application to regret minimization with global costs” by Kwon or “Pseudonorm Approachability and Applications to Regret Minimization” by Dann et al.\n\nThis would perhaps be okay if these new algorithms were shown to empirically significantly outperform state-of-the-art on some class of games, but this does not seem to be the case; if anything, they seem to underperform existing algorithms such as PCFR+. I think some of the resulting conjectures about the role of stepsize invariance (and different types of step-size of invariance) on the practical performance of these algorithms are interesting, but they are not very convincingly explored in this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your time reviewing the paper. We quote your comments in italic and we respond to them in regular font.\n\n## Response to your questions.\n\n* *But it is not clear to me that “based on Blackwell approachability” is really a well-defined concept (perhaps you could recover some existing algorithms via other applications of approachability) or even a desired one.*\n\nThe algorithms derived from Algorithm 1 in our paper are derived from Blackwell approachability instances where the decision set is the treeplex $\\mathcal{T}$ and the target set is the polar of the cone $\\mathcal{C} = cone(\\mathcal{T})$. The vector payoff is $f(x,\\ell)$, given a decision $x \\in \\mathcal{T}$ and an instantaneous loss $\\ell$. We will make this more explicit in our revised paper.\n\nAt a higher level, our goal in searching for an algorithm based on Blackwell approachability was to develop algorithms that share similar principles as the RM, RM+ and PRM+ algorithms for regret minimization on the simplex, in particular, their strong stepsize invariance properties. We believe that we do achieve this goal, and that it is a desirable concept; we think it is fair to say that our algorithm is the direct analogue of the RM+ algorithm extended to the treeplex. Perhaps we should better explain that this is really what we are looking for, as opposed to *any* algorithm that could be constructed as being based on Blackwell approachability. You are right that, perhaps, one could derive other existing methods such as e.g. projected OGD with a sufficiently clever Blackwell reduction, and this would not yield the type of algorithm that we were looking for. We will better clarify this in the revised paper.\n\n* *It should also be pointed out that there has been significant work on Blackwell approachability since the work of Abernethy et al., including several papers which resolve some of the deficiencies the authors point out in Appendix C (which mostly stem from the fact that Abernethy et al. only consider the L_2 norm). I would recommend the authors look at [1] “Refined approachability algorithms and application to regret minimization with global costs” by Kwon or [2] “Pseudonorm Approachability and Applications to Regret Minimization” by Dann et al.*\n\nThanks for pointing us to these references. We agree that [1,2] provide interesting extensions to the seminal work from [0] Abernethy et al., focusing on the case of approachability based on other (pseudo)norms. We would like to emphasize that our problem setting is different, and therefore our objectives too – we focus specifically on game solving, on fast convergence rates to Nash equilibrium, and on the stepsize properties of our algorithms. This is a fundamental difference with previous works like [1,2], which improve the reduction from [0] in other directions than ours (using other norms, focusing on regret minimization). We recognize that it is currently somewhat unknown whether game solving could benefit from Blackwell approachability based on other norms than the $\\ell_2$-norm, and we will list it in our discussion section. That said, we are somewhat skeptical that alternative norms or Bregman divergences would lead to a numerical improvement. To give an analogy that we believe is fitting: we already know that the \"right\" distance generating function for the simplex is an entropy-based measure, or the dilated variant for EFGs, at least if we care about the ergodic rate of convergence. Yet such approaches have not performed very well numerically compared to the \"Blackwell approachability-based\" algorithms developed via RM+ or PRM+ run on each simplex via CFR. This is the sense in which we believe it was important to understand the performance of this type of \"Blackwell approachability-based\" algorithm directly on the treeplex. We also believe that some variants of the potential-based Blackwell generalizations have likely been tried, since they are known in the game-solving community. Yet, nobody ever wrote about such experiments in papers, most likely because the numerical performance was disappointing.\n\n* *This would perhaps be okay if these new algorithms were shown to empirically significantly outperform state-of-the-art on some class of games, but this does not seem to be the case; if anything, they seem to underperform existing algorithms such as PCFR+. I think some of the resulting conjectures about the role of stepsize invariance (and different types of step-size of invariance) on the practical performance of these algorithms are interesting, but they are not very convincingly explored in this work.*\n\nWe agree that it would be more attractive if our algorithms outperformed the state-of-the-art. At the same time, for the reasons stated above, we do believe that it was a hole in the literature that nobody understood whether it was possible to get useful algorithms by performing some form of Blackwell approachability-style algorithm directly on the treeplex. Our results show that, indeed, such algorithms can be designed, implemented efficiently, and we explore their numerical performance. We believe that understanding the performance of such an approach was needed in the literature, although it is disappointing that we do not recover performance similar to what can be achieved via PCFR+. At the same time, given this conclusion, we also believe that identifying the new stepsize invariance conjecture is a valuable contribution toward understanding the performance of PCFR+.\n\n\n## Conclusion. \n\nWe thank you again for giving us the opportunity to improve our work. Please let us know if there are any other questions that we should address.", "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": "QOcB6rSAXP", "reviewer": "Reviewer_PEWS", "summary": "This paper studies a Blackwell's approachability method for solving extensive-form game. Rather than applying it at each infoset as in the CFR approach, it applies it globally, which allows for a $\\mathcal{O}(1/T)$ convergence rate with a predictive version.", "questions": "The conclusion mentions that the algorithm gets worse practical results than the CFR approaches, despite the stepsize invariance. This implies that the invariance may be necessary at the infoset level. Do you think it is possible to change your approach to allow for such infoset invariance?", "limitations": "The authors mentioned the limit of their approach (mainly the invariance mentioned above). There is no potential negative societal impact behind their work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper is well written and well presented. \n\nThe results are sound, and the authors are the first to obtain a $\\mathcal{O}(1/T)$ regret .\n\nIt is surprising that such an approach has not been published before.", "weaknesses": "The fact that CFR+ obtains good practical results because no learning tuning is needed is more or less already known. \n\nThe experiments are a bit hard to read.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your positive reviews. We answer your questions below, quoting them in italics and answering in regular font. We remain available during the rebuttal period if you have any other questions/comments.\n\n* *The experiments are a bit hard to read.*\n\nIn the camera-ready version, we will use our additional page to describe in more detail our numerical experiments.\n\n* *The conclusion mentions that the algorithm gets worse practical results than the CFR approaches, despite the stepsize invariance. This implies that the invariance may be necessary at the infoset level. Do you think it is possible to change your approach to allow for such infoset invariance?*\n\nThanks for this interesting question. We hypothesize that obtaining an infoset stepsize invariant algorithm may require a different reduction from the one we propose in Proposition 3.1, which relates the regret in the simplex $\\mathcal{T}$ to the regret in the cone $cone(\\mathcal{T})$. To obtain an infoset stepsize invariant algorithm, it may necessary to relate the regret in $\\mathcal{T}$ to the regret in another conic set different from $cone(\\mathcal{T})$, but we were not able to provide a complete answer here. We will include this question in a discussion section at the end of our revised version.", "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": "QqDqsUQknh", "reviewer": "Reviewer_qS3q", "summary": "This paper introduces a method, predictive treeplex Blackwell, for using Blackwell approachability directly on the treeplex in order to perform regret minimization in extensive-form strategy sets. They show that their algorithm achieves $O(\\sqrt{T})$ regret (where $O$ hides polynomial factors in the game size), and a smoothed version of their algorithm enjoys $O(1/T)$ convergence toward Nash equilibrium when used by both players in zero-sum game.", "questions": "1. The paper claims that Smooth PTB+ is the first Blackwell-based $O(1/T)$-converging algorithm for EFGs. But doesn't the algorithm it is based on, namely the Clairvoyant CFR+ algorithm of [14], also achieve the same convergence rate? (see Appendix J of [14]).\n1. It is interesting to me that RM+ does not coincide with TB+ when the domain is a simplex (Appendix E). What happens experimentally if you use (P)TB+ instead of (P)RM+ at every information set in CFR?\n1. Is it possible to extend the fundamental ideas of this paper beyond treeplexes to other convex sets, to obtain more stepsize-invariant regret minimizers?", "limitations": "yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The method is conceptually very interesting, and shows that Blackwell-based stepsize-invariant regret minimizers are not solely restricted to the simplex. The experiments are comprehensive and illuminate clearly the authors' message about the role of infoset-level stepsize invariance. Thus, despite some minor issues listed below, I am generally in favor of acceptance.", "weaknesses": "My most significant issue is simple: although the method is conceptually interesting, it is unclear if it carries any advantages over CFR (see also questions below re. clairvoyant CFR). For example, in theory, by Corollary 4.3 it seems that the convergence rate is something like $O(d^{5/2}/\\sqrt{T})$ (since $\\hat\\Omega \\le \\sqrt{d}; \\lVert \\boldsymbol M \\rVert_2 \\le d$ -- maybe tighter analysis is possible but my point would stand regardless), compared to the $O(d/\\sqrt{T})$ achieved by CFR-based methods. Similarly, the method seems consistently outperformed or matched by PCFR+ in basically every game, and the per-iteration complexity is inferior by a logarithmic factor.\n\nMinor notes:\n1. In Proposition 3.1, the regret of Algorithm 1 should be expressed in terms of the regret of the regret minimizer on $\\mathcal C$. Also, technically, $\\text{cone}(\\mathcal T)$ is an infinite set, so by \"regret of  the regret minimizer on $\\mathcal C$\" I really mean \"regret of the regret minimizer on $\\mathcal C$ against vectors $\\boldsymbol{\\hat x} \\in \\mathcal T$\". The proper regret bound holds for OMD/FTRL with gradient dynamics, but these details, I think, should be spelled out. See e.g. Proposition 2 and the discussion afterward in [12].", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank for your time reviewing the paper and for your encouraging comments. We answer your questions below.\n\n### Response to questions.\n\n* *My most significant issue is simple: although the method is conceptually interesting, it is unclear if it carries any advantages over CFR (see also questions below re. clairvoyant CFR).*\n\nThanks for mentioning this. It is correct that our proposed algorithms may not outperform CFR on every front:\n\n* In terms of theoretical properties, Smooth PTB+ achieves a faster $O(1/T)$ convergence rate, superior to the $O(1/\\sqrt{T})$ rate for CFR-based algorithms. However, Smooth PTB+ loses stepsize invariance.\n* In terms of empirical convergence/practical performance, PTB+ is our best algorithm but it is outperformed by PCFR+ for solving the game instances that we have tried. \n\nWe would like to emphasize that one of our main objectives in this paper is to provide a novel understanding of CFR-based algorithms; beating PCFR+ is not our main target, and this has been observed as very difficult repeatedly in prior work. In light of this, we view our main contribution as providing the first coherent hypothesis for the strong practical performances of PCFR+. To do so, we first introduce the first *theoretical* distinction between infoset stepsize invariance and treeplex stepsize invariance. We then explore numerically the impact of these properties. We first run a set of extensive numerical experiments to notice that among all the algorithms studied in our framework (PTB+, Smooth PTB+, AdagradTB+, AdamTB+) the best one is PTB+, the only (treeplex) stepsize invariance one. We then run additional experiments to highlight that PCFR+ outperforms PTB+, emphasizing the *practical* distinction between infoset vs. treeplex stepsize invariance.\n\n**Questions**:\n\n* *The paper claims that Smooth PTB+ is the first Blackwell-based O(1/T)-converging algorithm for EFGs. But doesn't the algorithm it is based on, namely the Clairvoyant CFR+ algorithm of [14], also achieve the same convergence rate? (see Appendix J of [14]).*\n\nThanks for mentioning this point. The Clairvoyant CFR (CCFR) algorithm from [14] is also based on Blackwell approachability, but on Blackwell approachability *over simplexes*, since it is based on the CFR decomposition, which enables the decision-maker to run independent regret minimizers at each information set, where the decision set is a simplex. It is true that [14] achieves $O(1/T)$ convergence for games played on simplexes with a similar type of \"Blackwell-based\" algorithm in self-play. However, it is not true that Clairvoyant CFR achieves a $O(1/T)$ rate on EFGs. Instead, it achieves a $O(\\log T / T)$ rate. This $\\log T$ dependence occurs because each outer iteration of CCFR itself must solve a fixed-point problem, and thus the algorithm does not even fall under the category of \"self-play via regret minimization\" algorithms. Practically speaking, this is not very desirable. In contrast, we achieve $O(1/T)$ in the sense of e.g. optimistic FTRL or OMD, where we only require simple repeated self-play. We will make this more precise in our revision.\n\n* *It is interesting to me that RM+ does not coincide with TB+ when the domain is a simplex (Appendix E). What happens experimentally if you use (P)TB+ instead of (P)RM+ at every information set in CFR?*\n\nTB+ implemented on the simplex is similar to the CBA+ algorithm from [17] (though not quite the same due to the lifting procedure in [17] being different). The authors in [17] provide numerical experiments combining the CFR decomposition with CBA+ as a regret minimizer at the infoset level, see Figure 3 and Figure 4 in [17], which show that this algorithm may outperform CFR+ in terms of the duality gap *after $T$ iterations*, but is outperformed by CFR+ in terms of the duality gap *after the same computation time*. We emphasize that [17] do not study the treeplex/EFG settings, which is the main focus of our work, and for which we can prove faster convergence rates and distinguish between interesting stepsize invariance properties. We will add a remark on this in our section on numerical experiments.\n\n* *Is it possible to extend the fundamental ideas of this paper beyond treeplexes to other convex sets, to obtain more stepsize-invariant regret minimizers?*\n\nOur ideas can be extended directly to any convex *compact* decision sets, as can be verified by inspecting the proof of Proposition 3.1. We only need the decision set $X$ to be convex, compact, and such that we can find a vector $a$ such that $\\langle a,x\\rangle=1$ for any $x \\in X$. To ensure this last condition, we can augment the decision set $X$ with an extra dimension, i.e. we can consider the $X’ = ${$1$} $\\times X$ and $a=(1,\\boldsymbol{0})$. In this sense, our framework can be extended to work with any convex compact sets, and the regret bounds shown in our main propositions and theorems still hold with $\\Omega$ the maximum $\\ell_2$ norm of elements in $X$. \nThanks for mentioning this interesting point. We will discuss it at the end of our revised paper.\n\n[13] G. Farina, J. Grand-Clément, C. Kroer, C.-W. Lee, and H. Luo. Regret matching+: (in)stability\nand fast convergence in games. In Advances in Neural Information Processing Systems, 2023.\n\n[17] J. Grand-Clement and C. Kroer. Solving optimization problems with Blackwell approachability. Mathematics of Operations Research, 2023.] \n\n\n### Conclusion.\n\nWe thank you again for your interesting comments, which will lead to an improved paper. Please let us know if you have any questions.", "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:

Meta-review: The paper makes an interesting conceptual contribution to the topic of extensive form games (EFGs), which is a foundational and well studied problem in game-theory as well as in ML. The paper shows a somewhat surprising result regarding Blackwell approachability based algorithms and their invariance to the choice of the stepsize, which is an intriguing property that does not apply to existing algorithms towards EFGs.
From these reasons I recommend to accept this paper.
Decision: Accept (spotlight)