Extensive-Form Game Solving via Blackwell Approachability on Treeplexes

Authors: darshan  chakrabarti
julien  grand-clément
christian  kroer
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-12 13:58:49

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.

Main paper: 
 introduction: 
 In this paper, we focus on solving Extensive-Form Games (EFGs). Finding a Nash equilibrium of a two-player zero-sum EFG can be cast as solvingEQUATIONwhere the sets X , Y are two sequence-form polytopes (also referred to as treeplexes) representing the strategies x, y of each player, and M is a payoff matrix. EFGs have been successfully used to obtain superhuman performances in several recent poker AI breakthroughs [37, 4, 5] . 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 X and Y themselves have very large dimensions in realistic applications, first-order 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 [23, 27] converge to a Nash equilibrium at a rate of O(1/T ), where T is the number of iterations. Regret minimization techniques rely on a 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 O(1/T ) convergence rate [14] .Counterfactual regret minimization (CFR) [39] is a regret minimizer for the treeplex that runs regret minimizers locally, i.e. directly at the level of the information sets of each player. CFR + , used in virtually all poker AI milestones [37, 30, 5] , instantiates the CFR framework with a regret minimizer 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 a 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 EFG-solving community.CFR + [37] 1/ √ T ✓✓ PCFR + [16] 1/ √ T ✓✓ EGT [26] 1/T ✗ POMD [14] 1/T ✗ PTB + (Algorithm 2)1/ √ T ✓ Smooth PTB + (Algorithm 3) 1/T ✗ AdaGradTB + (Algorithm 6) 1/ √ T ✗ AdamTB + (Algorithm 7) ? ✗Table 1 : Convergence rates to a Nash equilibrium of a two-player zero-sum EFG for several algorithms. ✓✓ refers to infoset stepsize invariance and ✓ refers to treeplex stepsize invariance. 
preliminaries on efgs: 
 We first provide some background on EFGs and treeplexes.Extensive-form games. Two-player zero-sum extensive-form games (later referred to as EFGs) are represented by a game tree and a payoff matrix. Each node of the tree belongs either to one of the players, or to a 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 in 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 as follows. We index the infosets of a player by J = {1, ..., |J |}. The set of actions available at infoset j ∈ J is written A j with cardinality |A j | = n j . We represent choosing action a ∈ A j at infoset j ∈ J by a sequence (j, a), and we denote by C ja the set of next infosets reachable from (j, a) (possibly empty if the game terminates). The parent p j of an infoset j ∈ J is the sequence leading to j; note that p j is unique assuming perfect recall. We assume that there is a single root denoted as ∅ and called the empty sequence. If the player does not take any action before reaching j ∈ J , then by convention p j = ∅. Under the perfect recall assumption, the set of infosets has a tree structure: C ja ∩ C j ′ a ′ = ∅, for all pairs of sequences (j, a) and (j ′ , a ′ ) such that j ̸ = j ′ , a ̸ = a ′ . This tree is the treeplex and it represents the set of all admissible strategies for a given player. We denote by n ∈ N the total number of sequences (j, a) with j ∈ J and a ∈ A j . With these notations, the treeplex T of a given player isEQUATIONwhere the first component x ∅ is related to the empty sequence ∅. A player makes an observation to arrive at j, if |C pj | > 1. We define the depth d of a treeplex to be the maximum number of actions and observations that can be made starting at the root until reaching a leaf infoset. Computing a Nash equilibrium of EFGs can be formulated as solving (1) (under the perfect recall assumption), with X ⊂ R n1+1 and Y ⊂ R n2+1 the treeplex of each player, n 1 and n 2 are the number of sequences of each player, and M ∈ R (n1+1)×(n2+1) the payoff matrix such that for a pair of strategy (x, y) ∈ X × Y, ⟨x, M y⟩ is the expected value that the second player receives from the first player.Regret minimization and self-play framework. A regret minimizer Regmin over a decision set Z ⊂ R d is an algorithm such that, at every iteration, Regmin chooses a decision z t ∈ Z, a loss vector ℓ ∈ R d is observed, and the scalar loss ⟨ℓ t , x t ⟩ is incurred. A regret minimizer ensures that the regret Reg T = max ẑ∈Z T t=1 ⟨ℓ t , z t -ẑ⟩ grows at most as O( √ T ). As an example, predictive online mirror descent (POMD, [34] ) generates a sequence of decisions z 1 , ..., z T ∈ Z as follows:EQUATIONwith m 1 , ..., m T ∈ R d some predictions of the losses ℓ 1 , ..., ℓ T ∈ R d , and where we write the orthogonal projection of y ∈ R d onto Z as Π Z (y) := arg min z∈Z ∥z -y∥ 2 .The self-play framework solves EFGs via regret minimization. The players compute two sequences of strategies x 1 , ..., x T and y 1 , ..., y T such that, at iteration t ≥ 1, the first player observes its loss vector M y t-1 and the second player observes its loss vector -M ⊤ x t-1 . Each player computes their current strategies x t ∈ X and y t ∈ 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 ( [19] ). Let x 1 , ..., x T ∈ X and y 1 , ..., y T ∈ Y be computed in the self-play framework. Let ( xT , ȳT ) = 1 T T t=1 (x t , y t ). Then, for Reg T 1 and Reg T 2 the regret of each player,max ŷ∈Y ⟨ xT , M ŷ⟩ -min x∈X ⟨ x, M ȳT ⟩ = Reg T 1 + Reg T 2 /T.We present more details on 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 ∈ J is the simplex over the set of next available actions∆ nj := {x ∈ R nj + | nj i=1 x i = 1}.In the CFR framework, the regret of each player (over the treeplex) is bounded by the maximum of the local regrets incurred at each infoset. Therefore, CFR combined with any regret minimizer over the simplex converges to a Nash equilibrium at a rate of O(1/ √ T ). 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 to attain strong practical performance compared to theoretically-faster methods [27] . Crucially, RM + can only be implemented on the simplex and not for other decision sets, and proceeds as follows: given a sequence of lossEQUATIONwith η > 0 and 0/0 := (1/d)1 for 1 := (1, ..., 1) ∈ R d , and, for x, ℓ ∈ R d , g(x, ℓ) := ℓ -⟨x, ℓ⟩1.(EQUATIONRM + is stepsize invariant: x 1 , ..., x T are independent of η, since x t = R t /∥R t ∥ 1 and η only rescales the entire sequence R 1 , ..., R T . 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 [3, 1] , where the goal of the decision maker is to compute the sequence of strategies x 1 , ..., x T ∈ ∆ d to ensure that the auxiliary sequenceR T /T ∈ R d + approaches the target set R d -as T → +∞. Since R t ∈ R d + ,this is equivalent to ensuring that lim T →+∞ R T /T = 0. The vector g(x, ℓ) is interpreted as an instantaneous loss for the approachability instance. As an instantiation of Blackwell approachability, at each iteration RM + computes an orthogonal projection onto the conic hull of the decision set:EQUATIONwith cone(Z)EQUATIONSince for R ∈ R d + , ⟨R, 1⟩ = ∥R∥ 1 , then x t = R t /∥R t ∥ 1 can be written x t = R t /⟨R t , 1⟩, with 1 a vector such that the decision set ∆ d satisfies (7) . This ensures thatEQUATIONWe provide an illustration of the dynamics of RM + in Figure 1 . Equation ( 8) is known as a hyperplane forcing condition and is a key ingredient in any Blackwell approachability-based algorithm; it ensures that the vector R T grows at most at a rate of O( √ T ) so that lim T →+∞ R T /T = 0. We refer to [33, 22] and to Appendix C for more details on Blackwell approachability.Question: Does the paper discuss the limitations of 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 in 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-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. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a 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 important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
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 as a regret minimizer over T 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 T ⊂ R n+1 a treeplex as defined in (2), we haveEQUATIONfor a = (1, 0) ∈ R n+1 with 0 = (0, ..., 0) ∈ R n . This property is analogous to (7) for the simplex. With this analogy in mind, we define C ⊂ R n+1 and f (x, ℓ) ∈ R n+1 as, for x, ℓ ∈ R n+1 ,EQUATIONEquation (10) and Equation ( 11) are analogous to ( 6) and ( 5). The cone C and the vector f (x, ℓ) play a similar role for T as R d + and g(x, ℓ) play for ∆ d in RM + . Our framework is described in Algorithm 1 and relies on running a regret minimizer Regmin over C = cone(T ) against the losses f (x t , ℓ t ) to obtain a regret minimizer over T against the losses ℓ t , for t ≥ 1.Algorithm 1 Blackwell approachability on the treeplex 1: Input: A regret minimizer Regmin with decision set C 2: Initialization: R 1 = 0 ∈ R n+1 3: for t = 1, . . . , T do 4:x t = R t /⟨R t , a⟩ 5:Observe the loss vector ℓ t ∈ R n+1 6:Regmin observes f (x t , ℓ t ) ∈ R n+1 7:R t+1 = Regmin (•)Figure 1 :RM + in R 2 + , with g t = g(x t , ℓ t ).By convention that 0/0 is the uniform strategy for the treeplex. Algorithm 1 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 1:Feasibility of the iterates. Algorithm 1 produces feasible strategies, i.e., x t ∈ T , ∀ t ≥ 1. Indeed, since Regmin is a regret minimizer with C as the decision set, R t ∈ cone(T ), i.e., R t = αz with α ∈ R + and z ∈ T . From (9), we have ⟨z, a⟩ = 1. Therefore, x t = Rt ⟨Rt,a⟩ = αz α⟨z,a⟩ = z ∈ T . This is analogous to RM + , where x t is proportional to R t , see (4) and Figure 1 .Hyperplane forcing. For any t ∈ N we haveEQUATION)The hyperplane forcing equation ( 12) is a crucial component of algorithms based on Blackwell approachability. It ensures that 12) is analogous to (8) for RM + and follows from x t = Rt ⟨Rt,a⟩ , so that∥R t ∥ 2 = O( √ T ). Equation (⟨R t , f (x t , ℓ)⟩ = ⟨R t , ℓ⟩ -⟨x t , ℓ⟩⟨R t , a⟩ = ⟨R t , ℓ⟩ -⟨ R t ⟨R t , a⟩ , ℓ⟩⟨R t , a⟩ = ⟨R t , ℓ⟩ -⟨R t , ℓ⟩ = 0.Regret minimization over T . Algorithm 1 always yields a regret minimizer over the treeplex T , i.e., it ensures that the regret of x 1 , ..., x T ∈ T against any ℓ 1 , ..., ℓ T ∈ R n+1 is bounded by O( √ T ). The proof is instructive and shows a central component to Blackwell approachability-based algorithms: minimizing regret over T can be achieved by minimizing regret over cone(T ). Proposition 3.1. Let Regmin be a regret minimizer with C as the decision set. Let x 1 , ..., x T ∈ T be computed by Algorithm 1. Then max x∈TT t=1 ⟨x t -x, ℓ t ⟩ = O( √ T ).Proof. Let x ∈ T and let us write R = x. We haveT t=1 ⟨x t -x, ℓ t ⟩ = T t=1 ⟨-x, f (x t , ℓ t )⟩ = T t=1 ⟨-R, f (x t , ℓ t )⟩ = T t=1 ⟨R t -R, f (x t , ℓ t )⟩where the first equality follows from the definition of f (x t , ℓ t ) and ⟨z, a⟩ = 1 for any z ∈ T , the second equality is because x = R, and the last equality follows from the hyperplane forcing condition (12) . Now note that T t=1 ⟨R t -R, f (x t , ℓ t )⟩ is the regret of a regret minimizer Regmin choosing R 1 , ..., R T in the decision set C := cone(T ) against a sequence of loss f (x 1 , ℓ 1 ) , ..., f (x T , ℓ T ) and a comparator R ∈ cone(T ). Therefore,T t=1 ⟨R t -R, f (x t , ℓ t )⟩ = O( √ T ).Remark 3.2. In their seminal paper, Abernethy et al. [1] show a general reduction from regret minimization to Blackwell approachability for compact convex decision sets. Our reduction from Algorithm 1 builds upon the ideas in [1] , but our reduction is different and exploits the structure of treeplexes. Additionally, [1] 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 O(1/T ) convergence rates. We provide a more detailed comparison with [1] in Appendix C.Question: For each theoretical result, does the paper provide the full set of assumptions and a 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 crossreferenced. • All assumptions should be clearly stated or 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 a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.• Theorems and Lemmas that the proof relies upon should be properly referenced. 
instantiations of algorithm 1: 
 We can instantiate Algorithm x t = R t /⟨R t , a⟩ 6:Observe the loss vector ℓ t ∈ R n+1 7:Rt+1 ∈ Π C Rt -ηf (x t , ℓ t ) Algorithm 3 Smooth PTB + 1: Input: η > 0, m 1 , ..., m T ∈ R n+1 2: Initialization: R1 = 0 ∈ R n+1 3: for t = 1, . . . , T do 4:R t ∈ Π C ≥ Rtηm t 5:x t = R t /⟨R t , a⟩ 6:Observe the loss vector ℓ t ∈ R n+1 7:Rt+1 ∈ Π C ≥ Rt -ηf (x t , ℓ t )We start by highlighting a crucial property of PTB + , treeplex stepsize invariance. The sequence of iterates x 1 , ..., x T generated by Algorithm 2 is independent of the choice of the stepsize η > 0, that only rescales the sequences R1 , ..., RT and R 1 , ..., R T , the orthogonal projection onto a cone is positively homogeneous of degree 1: Π C (ηz) = ηΠ C (z) for η > 0 and z ∈ R n+1 , and the function R → R/⟨R, a⟩ is scale-invariant: (ηR) ⟨(ηR),a⟩ = R ⟨R,a⟩ for η > 0 and R ∈ R n+1 . We provide a rigorous statement in the following proposition and we present the proof in Appendix D.Proposition 4.1. The sequence x 1 , ..., x T computed by PTB + is independent on the stepsize η > 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 T does not result in a stepsize invariant algorithm, whereas PTB + runs POMD on 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 can 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 Proposition 4.2. Let x 1 , ..., x T be computed by PTB + . Then max x∈TT t=1 ⟨x t -x, ℓ t ⟩ ≤ Ω T t=1 ∥f (x t , ℓ t ) -m t ∥ 2 2 .From Proposition 4.2, PTB + is a regret minimizer over treeplexes, and we can combine it with the self-play framework to solve EFGs, as shown in the next corollary. We use the notationsd := max{n, m} + 1, Ω := max{∥z∥ 2 | z ∈ X ∪ Y}, ∥M ∥ 2 := sup v̸ =0 ∥M v∥2∥v∥2 . Corollary 4.3. Let (x t ) t≥1 and (y t ) t≥1 be the sequence of strategies computed by both players employing PTB + in the self-play framework, with previous losses as predictions:m x t = f (x t-1 , M y t-1 ), m y t = f (y t-1 , -M ⊤ x t-1 ). Let ( xT , ȳT ) = 1 T T t=1 (x t , y t ). Then max y∈Y ⟨ xT , M y⟩ -min x∈X ⟨x, M ȳT ⟩ ≤ Ω3 √ d ∥M ∥ 2 √ T .Finally, we can efficiently compute the orthogonal projection onto C, since C admits the following simple formulation of as a polytope:C = {x ∈ R n+1 + | a∈Aj x ja = x pj , ∀ j ∈ J }. Proposition 4.4.Let T be a treeplex with depth d, number of sequences n, number of leaf sequences l, and number of infosets m. The orthogonal projection Π C (y) of a point y ∈ R n+1 onto C = cone(T ) can be computed in O(dn log(l + m)) arithmetic operations.A stable algorithm: Smooth PTB + . We now modify PTB + to obtain faster convergence rates. The O(1/ √ T ) average convergence rate of PTB + may seem surprising since in the matrix game setting, POMD over the simplexes obtains a O(1/T ) average convergence [36] . This discrepancy comes from PTB + running POMD on the set C = 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 hold. For PTB + , the Lipschitz continuity of the loss R → f (x, ℓ) with x = R/⟨R, a⟩ depends on the Lipschitz continuity of the decision function R → R/⟨R, a⟩ over C, which we analyze next. 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 a predictive variant of RM + [18] . To ensure the Lipschitzness of the decision function, we can ensure that R t and Rt always belong to the stable region C ≥ :C ≥ := cone(T ) ∩ {R ∈ R n+1 | ⟨R, a⟩ ≥ R 0 }for R 0 > 0, and we recover Lipschitz continuity over C ≥ :R 1 ⟨R 1 , a⟩ - R 2 ⟨R 2 , a⟩ 2 ≤ Ω R 0 ∥R 1 -R 2 ∥ 2 , ∀ R 1 , R 2 ∈ C ≥ .This leads us to introduce Smooth PTB + (Algorithm 3), a variant of PTB + ,where R t and Rt always belong to C ≥ . For Smooth PTB + ,x t ∈ T since R t ∈ C ≥ ⊂ cone(T ), and we also have the hyperplane forcing property (12) , which only depends on x t = R t /⟨R t , a⟩. However, Smooth PTB + is not treeplex stepsize invariant, because the orthogonal projections are onto C ≥ , which is not a cone. Note that C ≥ admits a simple polytope formulation:C ≥ = {x ∈ R n+1 + |x ∅ ≥ R 0 , a∈Aj x ja = x pj , ∀ j ∈ J }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 + is a regret minimizer. Indeed, the proof of Proposition .Thenmax x∈T T t=1 ⟨x t -x, ℓ t ⟩ ≤ Ω T t=1 ∥f (x t , ℓ t ) -m t ∥ 2 2 .In Smooth PTB + R t and Rt always belong to C ≥ , and we are able to recover a RVU bound and show faster convergence. We let ∥M ∥ be the maximum ℓ 2 -norm of any column and any row of M .Theorem 4.7. Let (x t ) t≥1 and (y t ) t≥1 be the sequence of strategies computed by both players employing Smooth PTB + in the self-play framework, with previous losses as predictions:m x t = f (x t-1 , M y t-1 ), m y t = f (y t-1 , -M ⊤ x t-1 ). Let η = R0 √ 8d Ω3 ∥M ∥ and ( xT , ȳT ) = 1 T T t=1 (x t , y t ). Then max y∈Y ⟨ xT , M y⟩ -min x∈X ⟨x, M ȳT ⟩ ≤ 2 Ω2 η 1T . We present the proof of Theorem 4.7 in Appendix I. 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 as in (1) , answering an important open question. However, achieving the faster rate in Smooth PTB + requires introducing a stepsize, a situation similar to all other O(1/T )-methods for EFGs, like Mirror Prox and Excessive Gap Technique for EFGs [27] and predictive OMD directly on the treeplex [14] . We can compare the O(1/T ) convergence rate of Smooth PTB + with the O(1/ √ T ) convergence rate of Predictive CFR + [16] , which combines CFR with Predictive RM + (see Appendix B). Despite its predictive nature, Predictive CFR + only achieves a O(1/ √ T ) 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 a 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 a Mirror Prox-style update [31] . For solving EFGs, Clairvoyant CFR achieves a O(log(T )/T )) 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-point problem.For completeness, we also instantiate Algorithm 1 with regret minimizers that learn heterogeneous stepsizes across information sets in an adaptive fashion. This results in AdaGradTB + (Algorithm 6) and AdamTB + (Algorithm 7), which adapt the scale of the stepsizes for each dimension to the magnitude of the observed gradients for this dimension based on AdaGrad [12] and Adam [25] . This may be useful if the losses across different dimensions differ in magnitudes, but the stepsizes decrease over time, which could be conservative. These algorithms are presented in Appendix J Remark 4.9 (Comparison with Lagrangian Hedging). Algorithm 1 is related to Lagrangian Hedging [21, 11] . Lagrangian Hedging builds upon Blackwell approachability 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 treeplexes, and where we can obtain several additional interesting properties not studied in [21, 11] , such as stepsize invariance, fast convergence rates, and efficient projection, as we detail in the next section. If one were to instantiate Algorithm 1 with the Follow-The-Regularized Leader algorithm, it would yield the regret minimizer for treeplexes studied in Gordon [21] , and our Proposition 4.4 in the next section yields an efficient projection oracle for the setup in Gordon [21] , which appealed to general convex optimization as an oracle. Every algorithm is using alternation.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes]Justification: We do so in the main body and in the appendices (Appendix H, 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 a 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 a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it 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 a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
numerical experiments: 
 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, Leduc poker, Liar's Dice, Goofspiel and Battleship. Additional experimental detail is given in Appendix K.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 t = 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/ √ T ). 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 a single call to the orthogonal projection at every iteration (SC-POMD, [24] ) achieving a O(1/T ) convergence rate; there are a variety of FOMs with a O(1/T ) rate, SC-POMD was observed to perform well in [8] . We determine the best empirical setup for each algorithm in Appendix K.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 Blackwell-approachability 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 to the root. For this reason, allowing for different stepsizes at 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, e.g., 4.9 × 10 4 actions in Liar's Dice and 5.3 × 10 6 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 [29] . PCFR + exhibits linear convergence in some games (Kuhn, Liar's Dice, Goofspiel) but not others (Leduc). The same is true for PTB + . Further investigations about last-iterate convergence are left as an important open question.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as 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. 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 a 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, or as supplemental material. 
conclusion: 
 We propose the first Blackwell approachability-based regret minimizer over the treeplex (Algorithm 1) and we give several instantiations of our framework with different properties, including treeplex stepsize invariance (PTB + ), adaptive stepsizes (AdaGradTB + ) and achieving O(1/T ) convergence rates on EFGs with a Blackwell approachability-based 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, our 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 as an important contribution of our paper, since it rules out a previously plausible explanation for the practical performance of CFR + . Instead, we propose that one piece of the puzzle behind the CFR + and PCFR + performances is their infoset stepsize invariance, a consequence of combining the CFR framework with Blackwell approachability-based 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 to explore EFG applications of new reductions between Blackwell approachability and regret minimization [10] (which differs from the reduction in [2] ) and Blackwell approachability generalizations based on various norms and pseudo-norms [28, 9] , potentially to obtain better stepsize invariance properties. 
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, confidence 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, or 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 or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to 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 as well as 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 or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
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 or 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 or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.• Researchers should communicate the details of the dataset/code/model 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 is used. • 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. 
 
 Appendix: The (vanilla) self-play framework for two-player zero-sum EFGs is presented in Algorithm 4. The Algorithm 4 self-play framework 1: Input: Regmin X a regret minimizer over X , Regmin Y a regret minimizer over Y 2: for t = 1, . . . , T do 3:x t = Regmin X (•)4:y t = Regmin Y (•) 5:The first player observes the loss vector Ay t ∈ R n1+1The second player observes the loss vector-A ⊤ x t ∈ R n2+1self-play framework can be combined with alternation, a simple variant that is known to lead to significant empirical speedups, for instance, when CFR + and predictive CFR + are used as regret minimizers [37, 16, 7] . When using alternation, at iteration t the second player is provided with the current strategy of the first player x t before choosing its own strategy. We describe the self-play framework with alternation in Algorithm 5.Algorithm 5 self-play framework with alternation 1: Input: Regmin X a regret minimizer over X , Regmin Y a regret minimizer over Y 2: for t = 1, . . . , T do 3:x t = Regmin X (•) 4:The second player observes the loss vector -A ⊤ x t ∈ R n2+1 5:y t = Regmin Y (•) 6:The first player observes the loss vector Ay t ∈ R n1+1 B Counterfactual Regret Minimization (CFR), CFR + and Predictive CFR +Counterfactual Regret Minimization (CFR, [39] ) is a framework for regret minimization over the treeplex. CFR runs a regret minimizer Regmin j locally at each infoset j ∈ J of the treeplex. Note that here Regmin j is a regret minimizer over the simplex ∆ nj with n j = |A j |, i.e., over the set of probability distributions over A j , the set of actions available at infoset j ∈ J . Let x j t ∈ ∆ nj be the decision chosen by Regmin j at iteration t in CFR and let ℓ t ∈ R n+1 be the loss across the entire treeplex. The local loss ℓ j t ∈ R nj that CFR passes to Regmin j isℓ j t,a := ℓ t,(j,a) + j ′ ∈Cja V j ′ t , ∀ a ∈ A j , ∀ j ∈ Jwhere V j t is the value function for infoset j at iteration t, defined inductively:V j t := a∈Aj x j t,a ℓ t,(j,a) + j ′ ∈Cja V j ′ t .The regret over the entire treeplex T can be related to the regrets accumulated at each infoset via the following laminar regret decomposition [13] : CFR + [37] corresponds to instantiating the self-play framework with alternation (Algorithm 5) and Regret Matching + (RM + as presented in ( 4)) as a regret minimizer at each information set. Additionally, CFR + uses linear averaging, i.e., it returns xT such that xT = 1 T t=1 ωt T t=1 ω t x t with ω t = t. We also consider uniform weights (ω t = 1) and quadratic weights (ω = t 2 ) in our simulations (Figure 10 ). CFR + guarantees a O(1/ √ T ) convergence rate to a Nash equilibrium. Predictive CFR + (PCFR + , [16] ) corresponds to instantiating the self-play framework with alternation (Algorithm 5) and Predictive Regret Matching + (PRM + ) as a regret minimizer at each information set. Given a simplex ∆ d , PRM + is a regret minimizer that returns a sequence of decisions z 1 , ..., z T ∈ ∆ d as follows:Reg T := max x∈T T t=1 ⟨x t -x, ℓ t ⟩ ≤ maxRt = Π R d + (R t -ηg(z t-1 , ℓ t-1 )) z t = Rt /∥ Rt ∥ 1 , R t+1 = Π R d + (R t -ηg(z t , ℓ t )) (PRM + )where the function g is defined in (5) . Similar to CFR + , for PCFR + we investigate different weighting schemes in our numerical experiments (Figure 11 ). It is not known if the self-play framework with alternation, combined with PCFR + , has convergence guarantees, but PCFR + has been observed to achieve state-of-the-art practical performance in many EFG instances [16] .In this appendix, we describe the results in [1] connecting Blackwell approachability and regret minimization, and we highlight the main differences with our framework described in Algorithm 1.In particular, Abernethy et al. [1] describe a meta-algorithm connecting Blackwell approachability and regret minimization. Given a decision set X ⊂ R n assumed to be convex and compact, Abernethyet al. [1] consider a lifted set X = {κ} × X ⊂ R n+1 with κ := max x∈X ∥x∥ 2 .Abernethy et al. [1] then constructs a regret minimizer over X by considering a Blackwell approachability instance, where the target set is defined as cone( X ) ⊂ R n+1 , the decision set is X ⊂ R n , and the instantaneous loss at time t is ⟨xt,ℓt⟩ κ , -ℓ t ∈ R n+1 with ℓ t ∈ R n the loss vector when the decision maker chooses x t ∈ X . The average aggregated loss vector u t ∈ R n+1 is updated using a regret minimizer over cone( X ) and the decision maker in the Blackwell approachability instance chooses the sequence of decisions x 1 , ..., x T to ensure that 1 T u T T ≥1 approaches the target set, defined as the polar cone of cone( X ). 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 1 differs from the meta-algorithm from [1] in various ways. In particular, if one were to directly use the reduction from [1] for deriving regret minimizers over treeplexes, one would need to consider T = {κ} × T , with T a treeplex and κ = max x∈T ∥x∥ 2 , and one would need to consider a bound for the value of κ, which could be conservative for large-scale EFG instances. However, since we have designed Algorithm 1 specifically for treeplexes as decision sets, we do not need to lift the set T by adding an additional dimension depending on the maximum ℓ 2 -norm over T . We can circumvent relying on κ and therefore obtain a simpler, more practical framework as in Algorithm 1 by exploiting the structure of treeplexes. This is because the variable x ∅ associated with the empty sequence always has a value of 1: x ∅ = 1, and we can then exploit the fact that T ⊂ {x ∈ R n+1 | ⟨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. [1] analyze Blackwell approachability with adversial losses and in a more theoretical way (e.g., no implementations or simulations), whereas we focus on practically solving EFGs with Blackwell approachability, i.e., we focus on the game setting and on explaining the empirical performance of CFR + . A direct application of the results in [1] would only result in algorithms achieving O(1/ √ T ) convergence rates, and for which no concrete implementations are known. In contrast, we provide 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 as in [1] ), and in our EFG applications we can obtain faster O(1/T ) convergence rate (e.g. for Smooth PTB + , see our new results as in Proposition 4.5 and Theorem 4.7), which is impossible against adversarial losses.Proof. The proof of Proposition 4.1 is based on the following lemma.Lemma D.1. Let C ⊂ R n be a convex cone and let u ∈ R n , η > 0. Then Π C (ηu) = ηΠ C (u).Proof of Lemma D.1. We have, by definition,Π C (ηu) = arg min R∈C ∥R -ηu∥ 2 .Now we also havemin R∈C ∥R -ηu∥ 2 = η • min R∈C ∥ 1 η R -u∥ 2 = η • min R∈C ∥R -u∥ 2where the last equality follows from C being a cone. This shows that arg min R∈C ∥R -ηu∥ 2 is attained at ηΠ C (u), i.e., that Π C (ηu) = ηΠ C (u).We are now ready to prove Proposition 4.1. For the sake of conciseness we prove this with m 1 = ... = m T = 0; the proof for PTB + with predictions is identical. In this case,R t = Rt , ∀ t ≥ 1.Consider the sequence of strategies x1 , ..., xT and R1 , ..., RT generated by PTB + with a step size of 1. We also consider the sequence of strategies x 1 , ..., x T and R 1 , ..., R T generated with a step size η > 0. We claim that xt = x t , R t = η Rt , ∀ t ∈ {1, ..., T }. We prove this by induction. Both sequences of iterates are initialized with R 1 = R1 = 0 so that x1 = x 1 . Therefore, both sequences face the same loss ℓ 1 at t = 1, and we haveR 2 = Π C (-ηf (x 1 , ℓ 1 )) = ηπ C (-f (x 1 , ℓ 1 ))) = η R2 .Let us now consider an iteration t ≥ 1 and suppose that xt = x t , R t = η Rt . Since xt = x t then both algorithms will face the next loss vector ℓ t . ThenR t+1 = π C (R t -ηf (x t , ℓ t )) = π C (η Rt -ηf (x t , ℓ t )) = ηπ C ( Rt -f (x t , ℓ t ))= η Rt+1 which in turns implies that x t+1 = xt+1 . We conclude that x t = xt , ∀ t = 1, ..., T .For the sake of discussion, we assume that the original decision set of each player is a simplex ∆ d and that there are no predictions: m t = 0, ∀ t ≥ 1.PTB + over the simplex. For PTB + , the empty sequence variable x ∅ is introduced and appended to the decision ∆ d . The resulting treepplex can be writtenT = {1} × ∆ d , the set C becomes C := cone(T ) = cone({1} × ∆ d ) and a = (1, 0) ∈ R d+1+ with 1 on the first component related to x ∅ and 0 everywhere else. In this case, PTB + without prediction is exactly the Conic Blackwell Algorithm + (CBA + , [22] ). Crucially, to run PTB + we need to compute the orthogonal projection onto cone(T ) = cone({1} × ∆) at every iteration, which can not be computed in closed-form, but it can be computed in O(n log(n)) arithmetic operations (see Appendix G.1 in [22] ).Regret Matching + . RM + operates directly over the simplex ∆ d without the introduction of the empty sequence x ∅ , in contrast to PTB + which operates over {1} × ∆ d . Importantly, in RM + , at every iteration the orthogonal projection onto R d + can be computed in closed form by simply thresholding to zero the negative components (and leaving unchanged the positive components):Π R d + (z) = (max{z i , 0}) i∈[d] for any z ∈ R d .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 can be slower in running times because of the orthogonal projections onto cone({1} × ∆) at each iteration (Figures 2,3,4 in [22] ). When T is a treeplex that is not the simplex, introducing x ∅ 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 x ∅ . As a convention, in this paper, we will always use x ∅ in our description of treeplexes and of our algorithms since it is convenient from a writing and implementation standpoint.Overall, we notice that in the case of the simplex introducing the empty sequence variable x ∅ 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, [22] combine the CFR decomposition with CBA + and compare the resulting algorithm with CFR + (i.e., combining the CFR decomposition with RM + ). The authors in [22] observe similar numerical results as 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 it is outperformed by CFR + in terms of duality gap achieved after a certain computation time, because of the orthogonal projection required at every iteration at every simplex present in the treeplexes of each player.F Proof of Proposition 4.5Proof of Proposition 4.5.1. Let R2 = R 2 /∥R 2 ∥ 2 be the unit vector pointing in the same direction as R 2 and let h := ⟨R 1 , R2 ⟩ R2 the orthogonal projection of R 1 onto{α R2 | α ∈ R}. We thus have ∥R 1 -R 2 ∥ 2 ≥ ∥R 1 -h∥ 2 .2. Let p = ⟨R1,a⟩ ⟨R2,a⟩ R2 . Since p and R 2 are colinear, we haveR 1 ⟨R 1 , a⟩ - R 2 ⟨R 2 , a⟩ 2 = R 1 ⟨R 1 , a⟩ - p ⟨p, a⟩ 2 .Additionally, by construction, ⟨p, a⟩ = ⟨R 1 , a⟩, so that we obtainR 1 ⟨R 1 , a⟩ - R 2 ⟨R 2 , a⟩ 2 = R 1 ⟨R 1 , a⟩ - p ⟨R 1 , a⟩ 2 = 1 ⟨R 1 , a⟩ ∥R 1 -p∥ 2 . Note that ⟨R 1 , a⟩ ≥ 0 since R 1 ∈ cone(T ) and T ⊂ {x ∈ R n+1 | ⟨x, a⟩ = 1}. Assume that we can compute D > 0 such that ∥R1-p∥2 ∥R1-h∥2 ≤ D. Then we have R 1 ⟨R 1 , a⟩ - R 2 ⟨R 2 , a⟩ 2 ≤ D ⟨R 1 , a⟩ ∥R 1 -h∥ 2 ≤ D ⟨R 1 , a⟩ ∥R 1 -R 2 ∥ 2 .3. The rest of this proof focuses on showing that ∥R1-p∥2 ∥R1-h∥2 ≤ Ω with Ω = max{∥x∥ 2 | x ∈ T }. Note that ⟨R 1p, a⟩ = 0. Therefore, 1 ∥R1-p∥2 (R 1p) and 1 ∥a∥2 a can be completed to form an orthonormal basis of R n . In this basis, we have∥ R2 ∥ 2 2 ≥ ⟨R 1 -p, R2 ⟩ 2 ∥R 1 -p∥ 2 2 + ⟨a, R2 ⟩ 2 ∥a∥ 2 2 .Note that by construction we have ∥ R2 ∥ 2 2 = 1. Additionally, R 2 ∈ cone(T ) so that there exists α > 0 and y ∈ T such that R 2 = αx. By construction of R2 , we have R2 = αx ∥αx∥2 = x ∥x∥2 and ⟨x, a⟩ = 1. This shows that⟨a, R2 ⟩ 2 ∥a∥ 2 2 = (⟨a, x⟩) 2 ∥a∥ 2 2 ∥x∥ 2 2 = 1 ∥a∥ 2 2 ∥x∥ 2 2 ≥ 1 Ω∥a∥ 2 2with Ω = max{∥x∥ 2 | x ∈ T }. Recall that we have chosen a = (1, 0) so that ∥a∥ 2 = 1. Overall, we have obtained1 - 1 Ω 2 ≥ ⟨R 1 -p, R2 ⟩ 2 ∥R 1 -p∥ 2 2 .From the definition of the vectors p, h and R2 , we have⟨R 1 -p, R2 ⟩ 2 ∥R 1 -p∥ 2 2 = ∥p -h∥ 2 2 ∥R 1 -p∥ 2 2.Hence, we have∥p -h∥ 2 2 ≤ 1 - 1 Ω 2 ∥R 1 -p∥ 2 2 .This shows that ∥R 1 -h∥ 2 2 ≥ 1 Ω 2 ∥x -p∥ 2 2 . 4. We conclude that R 1 ⟨R 1 , a⟩ - R 2 ⟨R 2 , a⟩ 2 ≤ Ω max{⟨R 1 , a⟩, ⟨R 2 , a⟩} ∥R 1 -R 2 ∥ 2 .In this section we show how to efficiently compute the orthogonal projection onto the cone C := cone(T ). We start by reviewing the existing methods for computing the orthogonal projection onto the treeplex T . This is an important cornerstone of our analysis, since the treeplex T and the cone C share an analogous structure:T = {x ∈ R n+1 + | x ∅ = 1, a∈Aj x ja = x pj , ∀ j ∈ J } C = {x ∈ R n+1 + | a∈Aj x ja = x pj , ∀ j ∈ J }.[20] were the first to show an algorithm for computing Euclidean projection onto 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 tZ, letting it be half the squared distance between y and tZ, for t ∈ R >0 :v Z (t, y) := 1 2 min z∈tZ ∥z -y∥ 2 2 .[20] show how to recursively compute λ Z (t, y), the derivative of this function with respect to t, for a given treeplex, since treeplexes can be constructed recursively using two operations: branching and Cartesian product. In the first case, givenk treeplexes Z 1 , . . . , Z k , then Z = {x, x[1]z 1 , . . . , x[k]z k : x ∈ ∆ k , z i ∈ Z i ∀i ∈ [k]} is also a treeplex. In the second case, given k treeplexes Z 1 , . . . , Z k , thenZ = Z 1 × • • • × Z k is also a treeplex.In fact, letting the empty set be a treeplex as a base case, all treeplexes can be constructed in this way.However, [20] did not state the total complexity of computing the projection, instead only stating the complexity of computing λ Z (t, y) given the corresponding λ Zi (t, y i ) functions for the treeplexes Z i that are used to construct Z using i ∈ [k]. They state that this complexity is O(n log n), where n is the number of sequences in Z. Their analysis involves showing that the function t → λ Z (t, y) is piecewise linear.[17] also consider this problem, generalizing the problem to weighted projection on the scaled treeplex, by adding an additional positive parameter w ∈ R n >0 :v Z (t, y, w) := 1 2 min z∈tZ n i=1 z[i] - y[i] w[i] 2 .They do a similar analysis to [20] , by showing how to compute the derivative λ Z (t, y, w) of v Z (t, y, w) with respect to t recursively. They show that t → λ Z (t, y, w) are strictly-monotonicallyincreasing piecewise-linear (SMPL) functions. We will follow the analysis in [17] , letting w = 1.We first define a standard representation of a SMPL function.). Given a SMPL function f , a standard representation is an expression of the formf (x) = ζ + α 0 x + S s=1 α s max{0, x -β s }valid for all x ∈ dom(f ), S ∈ N ∪ {0}, andβ 1 < • • • < β S .The size of the standard representation is defined to be S.Next, we prove the following lemma, showing the computational complexity of computing the derivative of the value function for a given treeplex.Lemma G.2. For a given treeplex Z with depth d, n sequences, l leaf sequences, and m infosets, and y ∈ R n , w ∈ R n >0 , a standard representation of λ Z (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 [17] . The base case is trivially true, because the empty set has no sequences or depth.For the inductive case, we will assume that it requires O (d -1)n log(l + m) time to compute the respective Euclidean projections onto the subtreeplexes that we use to inductively construct our current treeplex, where d -1 is the depth of a given subtreeplex, n 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 of [17] : Lemma G.3 (Recursive complexity of Euclidean projection for branching operation [17] ). Consider a treeplex Z that can be written as the result of a branching operation on k treeplexes Z 1 , . . . , Z k :Z = {x, x[1]z 1 , . . . , x[k]z k : x ∈ ∆ k , z i ∈ Z i ∀i ∈ [k]}.Let Z have n sequences and let y, w ∈ R n , and let y[i] and w[i] denote the corresponding respective components of y and w for the treeplex Z i .Then, given standard representations of λ Zi (t, y i , w i ) of size n i for all i ∈ [k], where n i is the number of sequences that Z i has, a standard representation of λ Z (t, y, w) of size n can be computed in O(n log k) time.Furthermore, given a value of t, the argument x which leads to the realization of the optimal value of the value function, can be computed in time O(n).Lemma G.4 (Recursive complexity of Euclidean projection for Cartesian product [17] ). Consider a treeplex Z that can be written as a Cartesian product of k treeplexes Z 1 , . . . , Z k :Z = Z 1 × • • • × Z k .Let Z have n sequences and let y, w ∈ R n , and let y[i] and w[i] denote the corresponding respective components of y and w for the treeplex Z i .Then, given standard representations of λ Zi (t, y i , w i ) of size n i for all i ∈ [k], where n i is the number of sequences that Z i has, a standard representation of λ Z (t, y, w) of size n can be computed in O(n log k) time.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 Z i as the treeplex that is underneath action a i ∈ A j . Let n i denote the number of sequences in Z i , m i denote the number of infosets in Z i , l i denote the number of leaf sequences in Z i , and d -1 be the maximum depth of any of these subtreeplexes.Given O(n log |A j |) + i∈[|Aj |] O (d -1)n i log(l i + m i ) = O(n log |A j |) + i∈[|Aj |] O (d -1)n i log(l + m) = O(n log |A j |) + O (d -1) i∈[|Aj |] n i log(l + m) = O(n log |A j |) + O (d -1)n log(l + m) = O n log(l + m) + O (d -1)n log(l + m) = O dn log(l + m)since we have necessarily that l i ≤ l andEQUATION|A j | ≤ l + m.Second, we consider the case the last operation to construct our treeplex was a Cartesian product. Let Z = Z 1 × • • • × Z k ,O(n log k) + i∈[k] O (d -1)n i log(l i + m i ) = O(n log k) + i∈[k] O (d -1)n i log(l + m) = O(n log k) + O (d -1) i∈[k] n i log(l + m) = O(n log k) + O (d -1)n log(l + m) = O(n log m) + O (d -1)n log(l + m) = O(dn log(l + m))since we have necessarily that l i ≤ l and m i ≤ m for all i ∈ [k], and k ≤ 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 a standard representation of λ Z (t, y, w) in O dn log(l+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 at 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 we have computed an optimval value of t for the value function at the top level, we can do a 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 in the proof of Lemma 14 in [17] .In order to pick the optimal value of t for the value function, since λ Z (•, y, w) is strictly increasing, we only have to consider two cases: λ Z (0, y, w) < 0 and λ Z (0, y, w) ≥ 0. In the first case, the value function λ Z (•, y, w) will be minimized when λ Z (•, y, w) is equal to 0, and this can be directly computed using the standard representation (it will be necessarily 0 somewhere because it is strictly monotone). In the second case, since λ Z (•, y, w) is strictly monotone and λ Z (0, y, w) ≥ 0, we must have that λ Z (•, y, w) ≥ 0, which means that v Z (•, y, w) is minimized at t * = 0.We have the following lemma, which shows that the stable region C ≥ admits a relatively simple formulation.Lemma H.1. The stable regionC ≥ := cone(T ) ∩ {R ∈ R n+1 | ⟨R, a⟩ ≥ R 0 }can be reformulated as follows:C ≥ = {αx | α ≥ R 0 , x ∈ T } = {x ∈ R n+1 + |x ∅ ≥ R 0 , a∈Aj x ja = x pj , ∀ j ∈ J }.Proof. By definition, we haveC ≥ = {R ∈ cone(T ) | ⟨R, a⟩ ≥ R 0 }.Note that for R ∈ cone(T ), R = αx with α ≥ 0 and ⟨x, a⟩ = 1. Therefore, for R ∈ C we have ⟨R, a⟩ ≥ R 0 ⇐⇒ α ≥ R 0 . This shows that we can writeC ≥ = {αx | α ≥ R 0 , x ∈ T }.Now let x ∈ C ≥ , i.e., let x = α x with α ≥ R 0 and x ∈ T . Since x ∈ T , we have x ∅ = 1, so that x∅ = α ≥ R 0 . Additionally, we have x ≥ 0, a∈Aj xja = xpj , ∀ j ∈ J . Multiplying by α ≥ R 0 , we obtain that x ≥ 0 and a∈Aj x ja = x pj , ∀ j ∈ J . Overall we have shownC ≥ ⊆ {x ∈ R n+1 |x ∅ ≥ R 0 , a∈Aj x ja = x pj , ∀ j ∈ J , x ≥ 0}. We now consider x ∈ {x ∈ R n+1 |x ∅ ≥ R 0 , a∈Aj x ja = x pj , ∀ j ∈ J , x ≥ 0} with x ̸ = 0. Then x = α x α with α = x ∅ , so that α ≥ R 0 and a∈Aj x ja = x pj , ∀ j ∈ J ⇐⇒ a∈Aj x ja α = x pj α , ∀ j ∈ J . Therefore {x ∈ R n+1 |x ∅ ≥ R 0 , a∈Aj x ja = x pj , ∀ j ∈ J , x ≥ 0} ⊆ C ≥ .This shows that we haveC ≥ = {x ∈ R n+1 |x ∅ ≥ R 0 , a∈Aj x ja = x pj , ∀ j ∈ J , x ≥ 0}.Proposition H.2. For a treeplex T with depth d, number of sequences n, number of leaf sequences l, and number of infosets m, the complexity of computing the orthogonal projection of a pointy ∈ R n+1 onto C ≥ = {αx | α ≥ R 0 , x ∈ T } is O dn log(l + m) .Proof. The proof is the same as that for Proposition 4.4, since the derivative of the value function can be computed in O dn log(l + m) time. However, this time, we have an additional constraint that t ≥ R 0 . Thus instead of checking the sign of λ Z (•, y, w) at t = 0, we check the sign at R 0 . If λ Z (R 0 , y, w) < 0, then because λ Z (•, 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 t, when t ≥ R 0 . On the other hand, if λ Z (R 0 , y, w) ≥ 0, then again because the function is strictly monotone in t, we know that the value function must get minimized at t * = R 0 . Using the same argument as in the proof of Proposition 4.4, since we have computed the standard representations of the derivatives of the value functions at all of the treeplexes, we can do a top-down pass to compute the argument which leads to the optimal value of the value function.Proof of Theorem 4.7. For the sake of conciseness we writef x t = f (x t , M y t ) and f y t = f (y t , -M ⊤ x t ).From our Proposition 4.2, we have that, for the first player,T t=1 ⟨x t -x, M y t ⟩ = T t=1 ⟨R t -R, f x t ⟩. Now T t=1 ⟨R t -R, f x t ⟩is the regret obtained by running Predictive OMD on C ≥ against the sequence of loss f x 1 , ..., f x T . From Proposition 5 in [16] , we have thatT t=1 ⟨R x t -Rx , f x t ⟩ ≤ ∥ R∥ 2 2 2η + η T t=1 ∥f x t -f x t-1 ∥ 2 2 - 1 8η T t=1 ∥R x t+1 -R x t+1 ∥ 2 2 .Since Rt ∈ C ≥ , we can use our Proposition 4.5 to show that∥x t+1 -x t ∥ 2 2 ≤ Ω R 2 0 ∥R x t+1 -R x t+1 ∥ 2 2 .This shows thatT t=1 ⟨R x t -Rx , f x t ⟩ ≤ ∥ R∥ 2 2 2η + η T t=1 ∥f x t -f x t-1 ∥ 2 2 - R 2 0 8Ω 2 η T t=1 ∥R x t+1 -R x t+1 ∥ 2 2which gives, using the norm equivalence∥ • ∥ 2 ≤ ∥ • ∥ 1 ≤ √ n + 1∥ • ∥ 2 , the following inequality: T t=1 ⟨R x t -Rx , f x t ⟩ ≤ ∥ R∥ 2 2 2η + η T t=1 ∥f x t -f x t-1 ∥ 2 1 - R 2 0 8Ω 2 (n + 1)η T t=1 ∥R x t+1 -R x t+1 ∥ 2 2The above inequality is a RVU bound:EQUATION)To invoke Theorem 4 in [36] , we also need the utilities of each player to be bounded by 1. This can be done can rescaling f x t = M y t and f y t = -M ⊤ x t . In particular, we know that∥M y∥ ∞ ≤ ∥M ∥ ℓ2,ℓ∞ ∥y∥ 2 ≤ ∥M ∥ ℓ2,ℓ∞ • Ω with ∥M ∥ ℓ2,ℓ∞ = max i∈[n+1] ∥ (A ij ) j∈[m+1] ∥ 2 and Ω = max{max{∥x∥ 2 , ∥y∥ 2 } x ∈X , y ∈ Y}. This corresponds to multiplying β in (13) by ∥M ∥ × Ω with ∥M ∥ := max{∥M ∥ ℓ2,ℓ∞ , ∥M ⊤ ∥ ℓ2,ℓ∞ }. To apply Theorem 4 in [36] we also need β ≤ γ. Since we need the same condition for the second player, we takeη = R 0 8d Ω3 ∥M ∥ -1. Under this condition on the stepsize, we can invoke Theorem 4 in [36] to conclude thatT t=1 ⟨R x t -Rx , f x t ⟩ + T t=1 ⟨R y t -Ry , f y t ⟩ ≤ ∥ Rx ∥ 2 2 + ∥ Ry ∥ 2 2 η .Since the duality gap is bounded by the average of the sum of the regrets of both players [19] , and replacing η by its expression, we obtain thatmax y∈Y ⟨ xT , M y⟩ -min x∈X ⟨x, M ȳT ⟩ ≤ 2 Ω2 η 1 T .J AdaGradTB + and AdamTB + AdaGradTB + . We introduce AdaGradTB + in Algorithm 6. Given matrix A and a vector y ∈ R n+1 , let diag(y) be the diagonal matrix with y on its diagonal and Π A C (y) = arg min x∈C ⟨xy, A(xy)⟩. We first show that AdaGradTB + is a regret minimizer.Proposition J.1. Let x 1 , ..., x T be computed by AdaGradTB + . For η = max t≤T (∥Rt∥2+Ω) 2 √ 2, we havemax x∈T T t=1 ⟨x t -x, ℓ t ⟩ ≤ 2η d i=1 T t=1 (f t (x t , ℓ t )) 2 i .We omit the proof of Proposition J.1 for conciseness; it follows from the regret guarantees of AdaGrad (Theorem 5 in [12] ) and Proposition 3.1. We conclude that combining AdaGradTB + with the self-play framework ensures a O(1/ √ T ) convergence rate.Algorithm 6 AdaGradTB + 1: Input: η, δ > 0 2: Initialization: R 1 = s 0 = g 0 = 0 ∈ R n+1 3: for t = 1, . . . , T do 4:x t = R t /⟨R t , a⟩ 5:Observe the loss vector ℓ t ∈ R n+1 6:s t = s t-1 + f (x t , ℓ t ) ⊙ f (x t , ℓ t )7:H t = diag √ s t + ϵ1 8: R t+1 ∈ Π Ht C R t -ηH -1 t f (x t , ℓ t )AdamTB + . We present AdamTB + , our instantiation of Algorithm 1 inspired from the adaptive algorithm Adam [25] 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.Single-call Predictive Online Mirror Descent (SC-POMD). We present SC-POMD in Algorithm 8. This algorithm runs a variant of predictive online mirror descent with only one orthogonal projectionAlgorithm 7 AdamTB + 1: Input: η, δ > 0, β 1 , β 2 ∈ [0, 1] 2: Initialization: R 1 = 0 ∈ R n+1 , s 0 = 0 ∈ R n+1 , g 0 = 0 ∈ R n+1 3: for t = 1, . . . , T do 4:x t = R t /⟨R t , a⟩ 5:Observe the loss vector ℓ t ∈ R n+1 6:s t = β 2 s t-1 + (1 -β 2 )f (x t , ℓ t ) ⊙ f (x t , ℓ t ) 7: ŝt = s t /(1 -β t 2 )8:g t = β 1 g t-1 + (1 -β 1 )f (x t , ℓ t ) 9: ĝt = g t /(1 -β t 1 )10:H t = diag √ ŝt + ϵ1 11: R t+1 ∈ Π Ht C R t -ηH -1 t ĝtat every iteration [24] . The pseudocode from Algorithm 8 corresponds to choosing the squared ℓ 2 -norm as a 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 a Nash equilibrium at a rate of O(1/T ), similar to the variant of predictive online mirror descent with two orthogonal projections at every iteration [15] .Algorithm 8 Single-call predictive online mirror descent (SC-POMD) 1: Input: η > 0, 2: Initialization:EQUATIONxEQUATIONObserve the loss vector ℓ t ∈ R n+1All algorithms are initialized using the uniform strategy (placing equal probability on each action at each decision point). For algorithms that are not stepsize invariant (Smooth PTB + and SC-POMD), we try stepsizes in η ∈ {0.05, 0.1, 0.5, 1, 2, 5} and we present the performance with the best stepsize.For Smooth PTB + , we use R 0 = 0.1. For both AdaGradTB + and AdamTB + , we use δ = 1 × 10 -6 , and for AdamTB + we use β 1 = 0.9 and β 2 = 0.999.In Figure 4 we compare the performance of TB + , PTB + , Smooth PTB + , AdaGradTB + and AdamTB + .It can 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 in Leduc 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.In Figure 5fig :scpomd, 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 a 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 is the setup that we present for comparing the performance of these algorithms in our main body (Figure 2 ). Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in 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 as long as it is clear that these goals are not attained by the paper.Justification: The research conducted in the paper conform with the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).in[16]), we obtain the following proposition. We define Ω ∈ R + as Ω := max x∈T ∥x∥ 2 . 


Decision: 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.

Reviews: review: paper_summary: paper_summary: This paper studies computations via regret minimization of Nash equilibria in zero-sum extensive form games (EFG) with the perfect recall assumption.
The actions of the players are a sequence of polytopes (treeplexes).

In 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.
Common regret minimization algorithms used are regret matching that operates on the simplex and is based on Blackwell approachability, or online mirror descent (OMD). 
Using regret matching as a local optimizer showed a better empirical performance. 
This 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. 

Several algorithm instantiations are also provided and tested via numerical experiments. 
The 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)
strength_weakness: strength_weakness: Couldn't find Weaknesses
questions: questions: -
limitations: limitations: The limitations are properly addressed.
paper_summary: paper_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. 

In 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. 

If 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). 

The 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+.
strength_weakness: strength_weakness: 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.

I 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.

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.
questions: questions: Feel free to reply to any part of the review above.
limitations: limitations: Limitations adequately addressed.
paper_summary: paper_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.
strength_weakness: strength_weakness: The fact that CFR+ obtains good practical results because no learning tuning is needed is more or less already known. 

The experiments are a bit hard to read.
questions: 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: limitations: The authors mentioned the limit of their approach (mainly the invariance mentioned above). There is no potential negative societal impact behind their work.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

Minor notes:
1. 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].
questions: 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]).
1. 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?
1. 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: limitations: yes

Comments: comment: Thank you for the detailed response. After reading through it (and the other reviews and comments), I've decided to maintain my current evaluation of the paper.
As the end of the discussion period approaches, we would like to ask if our responses address your concerns and comments. We remain available to provide further clarifications on our work.
Thank you. My opinion of the paper was and remains positive, and I will keep my score.