Block-Coordinate Methods and Restarting for Solving Extensive-Form Games
Authors: Darshan Chakrabarti
Jelena Diakonikolas
Christian Kroer
Venue: NeurIPS 2023 poster (2023)
Keywords: extensive-form games
first-order methods
coordinate descent

Abstract: Coordinate descent methods are popular in machine learning and optimization for their simple sparse updates and excellent practical performance. 
In the context of large-scale sequential game solving, these same properties would be attractive, but until now no such methods were known, because the strategy spaces do not satisfy the typical separable block structure exploited by such methods.
We present the first cyclic coordinate-descent-like method for the polytope of sequence-form strategies, which form the strategy spaces for the players in an extensive-form game (EFG). 
Our method exploits the recursive structure of the proximal update induced by what are known as dilated regularizers, in order to allow for a pseudo block-wise update.
We show that our method enjoys a O(1/T) convergence rate to a two-player zero-sum Nash equilibrium, while avoiding the worst-case polynomial scaling with the number of blocks common to cyclic methods. We empirically show that our algorithm usually performs better than other state-of-the-art first-order methods (i.e., mirror prox), and occasionally can even beat CFR$^+$, a state-of-the-art algorithm for numerical equilibrium computation in zero-sum EFGs. 
We then introduce a restarting heuristic for EFG solving. We show empirically that restarting can lead to speedups, sometimes huge, both for our cyclic method, as well as for existing methods such as mirror prox and predictive CFR$^+$.

Block-Coordinate Methods and Restarting for Solving Extensive-Form Games*
Darshan Chakrabarti
Jelena Diakonikolas
IEOR Department Columbia University New York, NY 10025 dc359500 co www.umbbiaaaa a..mbia.eee edu
Department of Computer Sciences University of Ausconsin-Madison
Madison, WI 53706 jelena wisc edu
Christian Kroer
IEOR Department Columbia University
New York, NY 10025
ck2945@columbia edu
Abstract
Coordinate descent methods are popular machine learning and optimization for their simple sparse updates and excellent practical performance. In the context of large-scale sequential game solving, these same properties would be attractive, but until now no such methods were known, because the strategy spaces do not satisfy the typical separable block structure exploited by such methods. We present the first cyclic werrdinatedesceet--eee strategies, which form the strategy spaces for the players in an extensive-fore game (EFG). Our method exploits the recursive structure of the proximal update induced by what are known as dilated regularizers, in order to allow for a pseudo block-wise update. We show that our method enjoys O(1/T)) convergence rate a two-player zero-sum Nash equilibrium, while avoiding the worst-case polynomial scaling with the number of blocks common to cyclic methods. We empirically show that our algorithm usually performs better than other state-of-the art first-order methods (i.c., mirror prox), and occasionally can even beat CFR state-of- the-art algorithm for numerical equilibrium computation in zero-sum EFGs. We then introduce restarting heuristic for EFG solving. We show empirically that restarting can lead to speedups, sometimes huge, both for our cyclic method, as well for existing methods such as mirror prox and predictive CFR
method for the polytope of sequence-form
Introduction
Extensive-form games (EFGs) are broad class of game-theoretic models which are played tree. They can compactly model both simultaneous and sequential moves, private and/or imperfect information, and stochasticity. Equilibrium computation for two-player zero-sum EFG can be formulated as the following bilinear saddle-point problem (BSPP)
min max (Mx,y). xEX yey
(PD)
Here, the set of strategies X. for the x and players are convex polytopes known as sequence--frm polytopes 44 The (PD) formulation lends itself first-order methods (FOMs) [4] 25), linear
AAthhors ordered alphabetically.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

programming 44 and online learning- basedd approaches 8 15 are convex and compact polytopes, and the objective is bilinear.
17
42 49, since the feasible sets
A common approach for solving BSPPs is by using first-order methods, where local gradient informa- tion is used to iteratively improve the solution in order to converge to an equilibrium asymptotically. In the game-solving context, such methods rely on two oracles: a first-order oracle that returns a (sub)gradient at the current pair of strategies, and a pair of prox oracles for the strategy spaces X which allow one to perform a generalized form of projected gradient descent steps on X, y. These prox oracles are usually constructed through the choice of an appropriate regularizer. For EFGs, is standard to focus on regularizers for which the prox oracle can be computed in linear time with respect to the size of the polytope. which is only known to be achievable through what known as dilated regularizers [23]. Most first-order methods for EFGs require full-tree traversals for the first-order oracle, and full traversals of the decision sets for the prox computation, before making a strategy update for each player. For large EFGs these full traversals, especially for the first-order oracle, can be very expensive, and may be desirable to make strategy updates before a full traversal has been performed, in order to more rapidly incorporate partial first-order information.
In other settings, one commonly used approach for solving large-scale problems is through coordinate methods (CMs) [3 46. These methods involve computing the gradient for a restricted set of coordinates at each iteration of the algorithm, and using these partial gradients to construct descent directions. The convergence rate of these methods typically is able to match the rate of full gradient methods. However, in some cases they may exhibit worse runtime due constants introduced by the method. In spite of this, they often serve practical benefits of being more time and space efficient, and enabling distributed computation 2
19 22
28
32
47 48
Generally, coordinate descent methods assume that the problem is separable, i.e., there exists a partition of the coordinates into blocks so that the feasible set can be decomposed as Cartesian product of feasible sets, one for each block. This assumption is crucial, as it allows the methods to perform block-wise updates without worrying about feasibility, and it simplifies the convergence analysis. Extending CDMs to EFGs is non-trivial because the constraints of the sequence-fone polytope do not possess this separable structure; instead the strategy space such that the decision at given decision point affects all variables that occur after that decision. We are only aware of a couple examples in the literature where separability not assumed 1 10 but those methods require strong assumptions which are not applicable in EFG settings.
Contributions. We propose the Extrapolated Cyclic Primal-Dual Algorithm (ECyclicDDA). Our algorithm the first cyclic coordinate method for the polytope of sequence-form strategies. achieves a O1//T) convergence rate to two-player zero-sum Nash equilibrium, with no dependence on the number of blocks; this, is in contrast with the worst-case polynomial dependence on the number of blocks that commonly appears in convergence rate guarantees for cyclic methods. Our method crucially leverages the recursive structure of the prox updates induced by dilated regularizers. In contrast to true cyclic (block) coordinate descent methods, the intermediate iterates generated during one iteration of ECyclicPDA are not feasible because of the sepaaabaeb nature of the constraints of sequence-form polytopes. Due to this infeasibility we refer to our updates as being pseudo-blodd block updates. The only information that is fully determined after one pseudo-block update, is the behavioral strategy for all sequences at decision points in the block that was just considered. The behavioral strategy is converted back to sequence-fore form at the end of a full iteration of our algorithm.
At very high level, our algorithm is inspired by the CODER algorithm due to Song and Diakonikolas 39.. However, there are several important differences due to the specific structure of the bilinear problem (PD) that we solve. First of all, the CODER algorithm is not directly applicable to our setting, as the feasible set (treeplex) that appears in our problem formulation is not separable. Additionally, CODER only considers Euclidean setups with quadratic regularizers, whereas work considers more general normed settings; in particular, the f setup is of primary interest for our problem setup, since it yields much better dependence on the game size.
These two issues regarding the nonssaparyyylity of the feasible set and the more general normed spaces and regularizers are handled in our work by (i) considering dilated regularizers, which allow for blockwise (up to scaling) updates in a bottom-up fashion, respecting the treeplex ordering: and (ii) introducing different extrapolation steps (see Lines 10 and 13 in Algorithm [ that are unique to our work and specific to the bilinear EFG problem formulation. Additionally, our special problem structure and the choice of the extrapolation sequences X₁ and y& allows to remove

---

any nonstandard Lipschitz assumptions used in Song and Diakonikolas [3. Notably, unlike Song and Diakonikolas (39] and essentially all the work on cyclic methods we are aware of, which pay polynonially for the number of blocks in the convergence bound, our convergence bound in the & setting is never worse than the optimal bound of full vector-update methods such as mirror prox 33
and dual extrapolation [35] which we consider major contribution of our work.
Numerically, we demonstrate that our algorithm performs better than mirror prox (MP), and can be competitive with CFR and its variants on certain domains. We also propose the use of adaptive restarting as a general heuristic tool for EFG solving: whenever an EFG solver constructs a solution with duality gap at most a constant fraction of its initial value since the last restart, we restart it and initialize the new run with the output solution at restart. Restarting is theoretically supported by the fact that BSPPs possess the sharpness property [8 21 45], and restarting combined with certain Fuclidean-based FOMs leads to linear convergence rate under sharpness 5 21.. We show that with restarting, it is possible for our ECycliePDA methods to outperform CFR+ + on some games; this is the first time that a FOM has been observed to outperform CFR+ on non-trivial EFGs. Somewhat surprisingly, we then show that for some games, restarting can drastically speed up CFR+ well. In particular, we find that on one game, CFR + with restarting exhibits a linear convergence rate, and so does a recent predictive variant of CFR + [15. on the same game and on an additional one.
Related Work. CMs have been widely studied the past decade and half T3 7
22
28
46 48) CMs can be grouped into three broad classes 38 greedy methods, which greedily select coordinates that will lead to the largest progress; randomized methods, which select (blocks of) coordinates according to a probability distribution over the blocks; and cyclic methods, which make updates in cyclic orders. Because greedy methods typically require full gradient evaluation (to make the greedy selection), the focus in the literature has primarily been on randomized (RCMs) and cyclic (CCMs) variants. RCMs require separability of the problem's 's constraints focus CCMs. However, establishing convergence arguments for CCMs through connections with convergence arguments for full gradient methods is difficult. Some guarantees have been provided in the literature, either making restrictive assumptions [7 or by treating the cyclical coordinate gradient as an approximation of a full gradient 77], and thus incurring a linear dependence the number of blocks in the convergence guarantee. Song and Diakonikolas (39) were the first make an improvement on reducing the dependence on the number of blocks by using a novel extrapolation strategy and introducing new block Lipschitz assumptions. That paper was the main inspiration for our work, but inapplicable to our setting, thus necessitating new technical ideas, as already discussed. While primal-dual coordinate methods for bilinear saddle-point problems have been explored in Carmon et al. (9), their techniques are not clearly extendable to our problem. The f - l1 setup they consider is the one which is relevant to the two-player zero-sum game setting we study, but their assumption in that case is that the feasible set for each of the players is a probability simplex, which is much simpler feasible set than the treeplex considered in our work. It is unclear how to generalize their result to our setting, as their results depend on the simplex structure.
30
34
37
There has also been significant work on FOMs for two-player zero-sum EFG solving. Because this is a BSPP, off-the-shelff FOMs for BSPPs can be applied, with the caveat that proximal oracles are required. The most popular proximal oracles have been based on dilated regularizers [23], which lead to a proximal update that can be performed with a single pass over the decision space, and strong theoretical dependence on game constants 1 [4 25 251. A second popular approach is
the counterfactual regret minimization (CFR) framework, which decomposes regret minimization on the EFG decision sets into local simplex-bur -ased regret minimization (49 In theory, CFseb
results have mostly led to inferior --22 rate of convergence, but in practice the CFR framework instantiated with regret matching- (RM+) [41) or predictive RM+ (PRM+) [15] is the fastest approach for essentially every EFG setting. The most competitive FOM-based approaches for practical performance are based on dilated regularizers [14] (24), but these have not been able to beat CFR+ on EFG settings; we show for the first time that it is possible to beat CFR + through
a combination of block coorddcoe updates and restarting, at least on some games. An extended discussion of FOM and CFR approaches to EFG solving is given in Appendix
2 Notation and Preliminaries
In this section, we provide the necessary background and notation subsequently used to describe and analyze our algorithm. As discussed in the introduction, our focus is on bilinear problems (PD).
3

---

2.1 Notation and Optimization Background
We use bold lowercase letters to denote vectors and bold uppercase letters to denote matrices. We use || || to denote an arbitrary lp norm for p 2 1 applied to vector in either R or I", depending on the context. The norm dual || || is denoted by || ll+ and defined in the standard way as || - x Txx where (z, x) denotes the standard inner product. In particular, for |- - I1-11p-
(a.x)
where p 2 1, we have || Il+ || lll=, where 1 + 1 = 1. We further use || ||+ to denote the p
| In particular, for the Euclidean norm induced matrix norm defined by ||M]]. = x |x|
|M||= |M|l is the matrix operator norm. For the l norm || -1 = || ll.. the dual norm is the & -nomm
||. = || - ll, the dual norm - llx |l. ll2 is also the Fuclidean norm, and
||- ||+ = || ll while the matrix norm is [M]] = |M
| max,, [Myl suPxy0 ||x||
We use A " = {x E R" x 0, (1, = 1} to denote the probability simplex in n dimensions.
Primal-dual Gap. Given x E Rdd, the primal value of the problem (PD) is maxvex (Mx, v) Similarly, the dual value of (PD) is defined by minlayy (Mu,y) y). Given a primal-dual pair y) E X' x y, the primal-dual gap (or saddle-point gap) is defined by
Gap(x.y) y)
max (Mx, v) min (Mu, y) = max VEX
(x,),, (u,))Xxy
uEy
where we define Gap
"ap":\(x> (x. y) = (Mx, v) (Mu,y). For our analysis, it is useful to work with the relaxed gap Gap"> Ex," yx for some arbitrary but fixed u E X, v E V, and then draw conclusions about a candidate solution by making concrete choices of u. V.
Definitions and Facts from Convex Analysis. In this paper, we primarily work with convex functions f R" + IR U (#00) } that are differentiable on the interior of their domain. We say that is cy-strongly convex w.r.t. a norm || || Vy E I", Vx E int domf.
f(y) 2 f(x) + (V (
x)
Cf lyy x1
We will also need convex conjugates and Bregman divergences. Given an extended real valued
function f IR" Ru(o)), its convex conjugate defined by (z) = supaer" I (Z, fx)=
Let f : R" + R U } be function that is differentiable on the interior of its domain. Given
y E R and x E int domʃ, the Bregman divergence Dy x) is defined by Dy x) = f(y)
f(x) - (x)(x). x). 3. If the function f cy-stroggly convex, then Dy x) 2 of ly x|
-
2.2 Extensive-Form Games: Background and Additional Notation
Extensive form games are represented by game trees. Each node v in the game tree belongs to exactly one player i E (I,....u) n) U {c) whose turn it is to move. Player c is a special player called the chance player; it is used to denote random events that happen in the game, such as drawing card from a deck or tossing a coin. At terminal nodes of the game, players are assigned payoffs. We focus on two-player zero-sum games, where 2 and payoff's sum to zero. Private information is modeled using information sets (infosets): a player cannot distinguish between nodes in the same infoset, so the set of actions available them must be the same at each node in the infoset.
The decision problem for a player There exists a set of decision points J, and at each decision point; j the player has set of actions A; with |4,1 = ny actions total. These decision points coincide with infosets the EFG. Without loss of generality, we let there be single root decision point, representing the first decision the player makes in the game. The choice to play an action a E Ay for a decision point j E J is represented using sequence (j, a), and after playing this sequence, the set of possible next decision points is denoted by Cz., (which may be empty in case the game terminates). The set of decisions form a tree, meaning that Cj.a nCy..a
Treeplexes.
perfect recall EFG can be described as follows.
0 unless j j and sequence (necessarily unique) encountered on the path from the root to decision point j is denoted by Pj- We define 4 j as the set consisting of all decision points that can be reached from j. An example of the use of this notation for a player in Kuhn poker (26 can be found in Appendix B
a': this is known as perfect recall. The last
The set of strategies for player can be characterized using the sequence-form, where the value of the decision variable assigned to playing the sequence (j,a) the product of the decision variable assigned to playing the parent sequence p5 and the probability of playing action when j [44]

---

Ty((", while zero The set of all sequence-form strategies of a player form a polytope known as the sequence-form polytope. Sequence-form polytopes fall into a class polytopes known as treeplexes [23] which can be characterized inductively using convex hull and Cartesian product operations:
Definition 2.1 (Treeplex). A treeplex X' for player can be characterized recursively as follows, where r is the the root decision point for a player.
X3.a
II XA3 J'ECsia
XJ {(A1,..., AAAl AIXI............................ MAA, (M4A...M (Aay)...A11a)))) E A A.l, ,x E NzaJ,
X [1] X Nir.
This formulation allows the expected loss of a player to be formulated as a bilinear function (Mx, y) of players' strategies y. This gives rise the BSPP in Equation (PD). and the set of saddle points of that BSPP are exactly the set of Nash equilibria of the EFG. The payoff matrix M is sparse matrix, whose nonzeroes correspond to the set of leaf nodes of the game tree.
Indexing Notation. A sequence- form strategy of a player can be written as a vector with an entry for each sequence (j. a). We use v denote the subset of size |4,1 of entries of that correspond to sequences (j, a) formed by taking actions a E A, and let v denote the subset of entries of v that are indexed by sequences that occur in the subtreeplex rooted at j. Additionally, we use yPr to denote the (scalar) value of the parent sequence of decision point j. By convention, for the root decision point j, we let uP = I. Observe that for any j E J. v /p is in the probability simplex.
Given a treeplex Z we denote by Jz the set of infosets for this treeplex. We say that a partition of Jz into & < |Jz] sets Jz (") "".."....
respects the treeplex ordering for any two sets Jz (*)
(8)) with i < i' and any two infosets j Jz J2(), j' E (1((", j does not intersect the path from j' to the root decision point. The set of infosets for the player x is denoted by Jx, while the set of infosets for player is denoted by Jy. We assume that Jx and Jy are partitioned into s nonempty
Jz
where s I min(1Ixl [Ty1} and the ordering of the sets in the two partitions respect the treeplex ordering of X, y, respectively.
sets Jx (1) Jxx (2)
Jx (+) and Jy (")") JT, (2),)...., Ty Ty(+),
Given a pair (t, (), we use M to denote the full-dimensional (m x n)) matrix obtained from the
matrix M by keeping all entries indexed by Jx (t) and (") and zeroing out the rest. When in place of f or t' we use ".", it corresponds to keeping as non-zeros all rows (for the first index) or all columns (for the second index). In particular, M,, is the matrix that keeps all rows of M indexed
by Tx (1) intact and zeros out the rest. Further, notation Mr.t: is used to indicate that we select rows indexed by (t) and all columns of M indexed by Jy Ty("), .Jy (t-1),
out the rest; similarly for M Notation Me, is used to indicate that we select rows indexed by Jx (x) and all columns of M indexed by Ty
(1) Jy ,...,, Ty (t), while we zero out the rest; similarly for MI.,e. Given vector X, (t) denotes the entries of indexed by the elements of Jxxh; (); similarly, for y E V, (1) denotes the entries of y indexed by the elements of Jy (*)
Additionally, use M(t.()) denote the submatrix of M obtained by selecting rows indexed by Jx (9) and columns indexed by Jy (t") ((t.')) is (p x -)dimeensinal,, for Σxer, |A,l and = Ejezy(e) |4yl- Notation ":" has the same meaning as in the previous paragraph.
Dilated Regularizers. We assume access to strongly convex functions Φ : X + R and y I with known strong convexity parameters cs >> 0 and Go > and that continuously differentiable on the interiors of their respective domains. We further assume that these functions are nice as defined by Farina al. [44] ; their gradients and the gradients of their convex conjugates can be computed in time linear (or nearly linear) in the dimension of the treeplex.
A dilated regularizer is a framework for constructing nice regularizing functions for treeplexes. It makes use of the inductive characterization of a treeplex via Cartesian product and convex hull operations to generalize from the local simplex structure of the sequence-forn polytope at decision point to the entire sequence-fome polytope. In particular, given a local "nice" regularizer 6 for each
decision point j. a dilated regularizer for the treeplex can be defined d(x) Σjerx x 0 (z)).
5

---

The key property of these dilated regularizing functions is that the prox computations of the form X argminxext (h, x) (XE, xx-1)} decompose into bottom-up updates, where, up scaling factor, each set of coordinates from set Jx (t) can be computed solely based on the coordinates of X5: from sets Tx" (1)
..... Tx Jxx"") (t-1) and coordinates of from sets Jx ..... Tx Concretely, the recursive structure of the prox update is as follows (this was originally shown by 23 here we
show a variation from Farina et al. [3]:
Proposition 2.2 (Farina et al. (3). A prox update to compute X with gradient h and center X on a treeplex X using a Bregman divergence constructed from a dilated DGF can be decomposed into local prox updates at each decision point j Tx as follows:
x = Pi arrginn DiEA"
(h' - 1², Dos
b'
x--1
h(iaaa
Σ
( (-h'd + + (xt - 05'
x
Vo"
X
+
(.0)
(1:))
(i.))
J'EC,,a
I
2
k
3 Extrapolated Cyclic Algorithm
Our extrapolated cyclic primal-dual algorithm is summarized in Algorithm 1 As discussed in Section 2 under the block partition and ordering that respects the treeplex ordering, the updates for (t) in Line 9 (respectively, (() in Line 12), up to scaling by the value of their respective parent زي and s sequences, can be carried out using only the information about Y and h2 (respectively, 2y
Mik
for infosets j that are "lower" on the treeplex. The specific choices of the extrapolation sequences X f
and y& that only utilize the information from prior cycles and the scaled values of and xi for infosets j updated up to the block t updates for x3: and yı are what crucially enables us to decompose the updates for X2 and yı into local block updates carried out in the bottom-up up manner. the end of the cycle, once and y Ve.
xi /
has been updated for all infosets, we can carry out a top-to-botton
update to fully determine vectors x and Yk. as summarized in the last two for loops in Algorithm [ We present an iipllmmnntationspeciitt version of the algorithm in Appendix [ which explicitly demonstrates that our algorithm's 's runtime does not have dependence on the number of blocks used. In our analysis of the pppllemmntationsspeciiii complexity of our algorithm matches that of MP. To support this analysis, we compare the empirical runtimes of our algorithm with MP and CFR+ variants in Section 4
version of the algorithm, we argue that the per-iteration
Our convergence argument built on the decomposition of the relaxed gap Gap">Y v&) for arbitrary but fixed (u. v) E X' x y into telescoping and non-positive terms, which is common in first-order methods. The first idea that enables leveraging cyclic updates lies in replacing vectors Mx, and M yı: by "extrapolated" vectors and h2 that can be partially updated in a blockwise fashion as a cycle of the algorithm progresses, as stated in Proposition 3.] To our knowledge, this basic idea originates in Song and Diakonikolas (39]. Unique to our work are the specific choices of ge and hg, which leverage all the partial information known to the algorithm up to the current iteration and block update. Crucially, we leverage the treeplex structure to show that our chosen updates are sufficient to bound the error sequence ε and obtain the claimed convergence bound in Theorem 3.2 Due to space constraints, the proof is deferred to Appendix C
".
To simplify the exposition, we introduce the following notation:
M2 = Mi My := M M2 = Σ M
(3.1)
1=1
Ps = M- + |Myllr. My: = | Il + IM
When the norm of the space is ||- || = || |||, both par and Myy are bounded above by 2 maxij [Mal-- The next proposition decomposes the relaxed gap into an error term and telescoping terms. The proposition is independent of the specific choices of extrapolated vectors gk h

---

Algorithm Extrapolated Cyclic Primal-Dual EFG Solver (ECyclicPDA)
1: Initialization: Xo E X, y. Hu = 0,
Vegce Metiy"
No Xo. No = Yo. go 0, ho
2: for k= 1: K do
3: Choose 77K S 7/, H = Hk-1 + 1/k:
4: gk 1 h& hg-1
5:
X₁ x + 16-1 (Xk-1 2)- Yk = Yk-1
Th-1 71
Vy--1 yk-2)
6:
for f =
1 :: do
7:
h (MG)) T Yk
Do(x, xk 11 (t)
(t) argmin xEX Th (x, h2)
8:
X
9:
X
x Pj
+ M1-1 (x]
"
[x
1x-1
x/-1 xx
k-
jEIx(0)
(1) (1.)5
Yk arginaxee> The (Be, - -D (v, y }} (1)
(6)
(1) = Uk-1 +
M6-1 (vk-1
1/2
12:
1/ レ (E
13:
for E Jx do
14:
P3 x = k
15:
for
E Jy do
16:
17:
84
Hy xk +
He
Xk, V&
H4-mk He
Fk-1 + 1e
H2
Yk
18: Return: KK.NK JK
Proposition 3.1. Let Xk, Y be the iterates of Algorithm Mfr k 2 1. Then, for all h: 2 1, x X, Yk E y, we have
Th Gap". (x;,, S & Dz xx) + Dæ x+-1) (v. Dv(V.
where the error sequence En is defined
E = 7k (Mx;
gk. V yk) (u Xu-
h4) De (x (
To obtain our main result, we leverage the blockwise structure of the problem, the bilinear structure of the objective, and the treeplex structure of the feasible sets control the error sequence & key property that enables this result that normalized entries x from the same information set belong to a probability simplex. This property is crucially used in controlling the enror of the extrapolation vectors. The main result summarized in the following theorem.
Theorem 3.2. Consider the iterates Xx. Yk for in Algorithm I and the output primal-dual pair RK. KK. Then, Vk 2 1, Py Do (x", xx) + My (y", (x(x", + (y ,o),, and, further,
Ne + By
{MMX, v) (M), sUPueX (De (D xo) + Dol
Gap(XK, 8k)
sup VEX,
HK
In the above bound, if 1, 1,Tk=11
then HK Kn, As consequence, for any 0,
Bo Biy (Matiyy) wey DD De iterations.
Gap(XK, FK) S after at most
wey
Pegcue
Experimental Evaluation and Discussion
We evaluate the performance of ECyclicPDA instantiated with three different dilated regularizers: dilated entropy (25), dilatable global entropy [1), and dilated d [13]. In the case of the dilated e
7

---

regularizer, we use dual averaging of the "extrapolated" vectors g and h& in our algorithm, since otherwise we have no guarantee that the iterates would remain in the relative interior of the domain of the dilated DGF, and the Bregman divergence may become undefined. We compare our method to MP, which is state-of- -frtte-rtttttttt-- among first-order methods for EFG solving. We test ECyclicPDA and MP with three different averaging schemes: uniform, linear, and quadratic averaging since Gao et al. [20] suggest that these different averaging schemes can lead to faster convergence in practice. We also compare against empirical state-of-the-art CFR variants: CFR 41]. and the predictive CFR variant (PCFR*) [S]. We emphasize that our method achieves the same O(+) average-iteraie convergence rate as MP, and that all the CFR+ variants have the same suboptimal O( ) average-iterate convergence rate. We experiment on four standard benchmark games for EFG solving: Goofspiel (4 ranks), Liar's s Dice, Leduc (13 ranks), and Battleship. In all experiments, we run for 10, 000 full (or equivalent) gradient computations. This corresponds to 5,000 iterations of ECyclicPDA, CFR and PCFR*, and 2,500 iterations of MP A description of all games is provided in Appendix EE]
Additional experimental details are provided in Appendix G
For each instantiation of ECyclicPDA considered on a given game (choice of regularizer, averaging, and block construction strategy) the stepsize is tuned by taking power of 2 multiples of 1) (2' 1 for I E N), where 1) is the theoretical stepsize stated in Theorem 3.2 and then choosing the stepsize 17" among these multiples of r) that has the best performance. Within the algorithm, we use a constant stepsize, letting 77- = for all k. We apply the same tuning scheme for MP stepsizes (for a given choice of regularizer and averaging). Note that this stepsize tuning coarse, and so it is possible that better results can be achieved for ECyclicPDA and MP using finer stepsize tuning.
We test our algorithm with four different block construction strategies. The single block construction strategy puts every decision point in a single block, and thus it corresponds to the non-block-band based version of ECyclicPDA. The children construction strategy iterates through the decision points of the treeplex bottom-up (by definition, this will respect the treeplex ordering), and placing each set of decision points that have parent sequences starting from the same decision point in its own block. The postorder construction strategy iterates through the decision points bottom-up (again, by definition, this will respect the treeplex ordering). The order is given by a postorder traversal of the treeplex, treating all decision points that have the same parent sequence as a single node (and when the node is processed, all decision points are sequentially added to the block). It greedily makes blocks as large as possible, while only creating new block if it causes a parent decision point and child decision point to end up in the same block. The infosets construction strategy places each decision point in its own block. We provide further description of the block construction strategies in Appendix F
We show the results of different block construction strategies in Figure [ For each block construction strategy, ECyclicPDA is instantiated with the choice of regularizer and averaging that yields the fastest convergence among all choices of parameters. We can see that the different block construction strategies do not make a significant difference in Goofspiel (4 ranks) or in Ledue (13 ranks). However, we see benefits of using blocks in Liar's Dice and Battleship. In Liar's Dice, children and postorder have a clear advantage, and children outperforms the other block construction strategies in Battleship.
We show the results of comparing ECyclicPDA is instantiated with the choice of regularizer, averaging, and block construction strategy that yields the fastest convergence among all choices for ECyclicPDA, and MP is instantiated with the choice of regularizer and averaging that yields the fastest convergence among all choices for MP. We that ECyelicPDA performs better than MP in all games besides Goofspiel (4 ranks), where they perform about the same. In Liar's Dice and Battleship. the games where ECyclicPDA benefits from having multiple blocks, we see competitiveness with CFR + and PCFR + In particular, in Liar's Dice, ECyclicPDA is overtaking CFR + at 10, 000 gradient computations. On Battleship, we see that both ECyclicPDA and MP outperform CFR + and that ECyelicPDA is competitive with PCFR
algorithm against MP, CFR and PCFR in Figure 2
Restarting. We now introduce restarting as a heuristic tool for speeding up EFG solving. While restarting is only known to lead to linear convergence rate in the case of using the E2 regularizer in certain FOMs (5) 21,, we apply restarting as a heuristic across our methods based on dilated regularizers and to based methods. To the best of our knowledge, restarting schemes have not been empirically evaluated on EFG algorithms such as MP, CFR or (obviously), our new method. We implement restarting by resetting the averaging process when the duality gap has halved since the last time the averaging process was reset. After resetting, the initial iterate is set equal to the last
2 Here count gradient evaluation for x and one for y gradient evaluations total.
8

---

Groffspiel (4 ranks)
Lar's Diee
Leduc (13 ranks)
Hattleship
Duality gop
tf
Gradicnt computations
Gradicat computations
Gradiont computations
Gradicnt computations
ECyeliePDA single block
ECyolicPDA postonder
ECyeliePDA children
ECyeliePDA infosets
Figure 1: Duality gap function of the number of full (or equivalent) gradient computations for ECyclicPDA with different block construction strategies.
Goofspiel (4 ranks)
Liar's Diec
Lediee (13 ranks)
Battleship
Duality gap
1011
if Gradient computations
IP
Gradient computations
Gradient computations
Gradient computations
ECycliePDA
MP
CFR
PCFR
Figure 2: Duality gap as function of the number of full (or equivalent) gradient computations for ECyclicPDA, MP, CFR +, PCFR*
iterate saw before restarting. Since the restarting heuristic is one introduce, we distinguish restarted variants in the plots by prepending the name of the algorithm with "r".. For example, when restarting is applied to CFR the label used is ICFR*
We show the results of different block construction strategies when restarting is used on ECyclicPDA in Figure 3 As before, we take the combination of regularizer and averaging scheme that works best. Again, we can see that the different block construction strategies do not make a significant difference in Goofspiel (4 ranks) or in Leduc (13 ranks), while making a difference for Liar's Dice and Battleship. However, with restarting, the benefit the children and postorder for Liar's Dice and Battleship is even more pronounced relative to the other block construction strategies; the gap is several orders of magnitude after 10t gradient computations. Note that while children performed worse than single block for Battleship previously, with restarting, children performs much better.
Finally, we compare the performance of the restarted version of our algorithm, with restarted versions of MP, CFR +, and PCFR* + in Figure 4 As before, we take the combination of regularizer, averaging scheme, and block construction strategy that works best for ECyclicPDA, and the combination of regularizer and averaging scheme that works best for MP. Firstly, we note that the scale of the y-axis different from Figure 2 for all games besides Ledue (13 ranks), because restarting tends to hit much higher levels of precision. We see that restarting provides significant benefits for PCFR in Goofspiel (4 ranks) allowing it to converge to numerical precision, while the other algorithms do not benefit much. In Liar's Dice, restarted CFR and PCFR converge to numerical precision within 200 gradient computations, and restarted ECyclicPDA converges to numerical precision at 104 gradient computations. Additionally, restarted MP achieves a much lower duality gap. For Battleship. ECyclicPDA, MP, and PCFR all benefit from restarting, and restarted ECyclicPDA is competitive with restarted PCFR Similar to the magnification in benefit of using blocks versus not using blocks when restarting in Liar's Dice and Battleship. we see that restarted ECyclicPDA achieves significantly better duality gap than MP in these games.
Wall-clock time experiments. In Table [ we show the average wall-clock time per iteration of our algorithm instantiated with different block construction strategies as well as MP, CFR + and PCFR* It is clear from this table that the runtimes are pretty similar to each other, and this is without extensive optimization of our particular implementation. Clearly, our algorithm at least as fast as MP per "full" gradient computation. Since the computational bottleneck of gradient and prox computations becomes apparent in bigger games, Battleship demonstrates the speed of our algorithm relative to MP best.

---

Groffspiel (4 ranks)
Liar's Diee
Leduc (13 ranks)
Hattleship
Duality gop
10"13
10
Gradicnt computations
Gradicat compatations
Gradiont computations
Gradient computations
rbCyelicPDA single block
yCCyllePDA postorder
rCCyeliePDA children
#CCylliPDA infosets
Duality gap function of the number of full (or equivalent) gradient computations for when restarting applied to ECyclicPDA with different block construction strategies. We take the best duality gap seen so far so that the plot is monotonic.
Figure 3:
Goofspiel (4 ranks)
Linr's Dice
Ledoc (13 rankss
Batrleship
Duality gap
10:10
10-10
Ti Gradient computations
Gradicnt Gradicnteompuuatoonns
Gradient computations
Gradicnt computations
:BCycliPDA
-X-
MMP
CFF
#CCR
Figure 4: Duality gap function of the number of full (or equivalent) gradient computations for when restarting is applied to ECycliePDA, MP, CFR+, PCFR+ We take best duality gap seen so far that the plot is monotonic.
Table The average wall clock time per iteration in milliseconds of ECyclicPDA instantiated with different block construction strategies, MP, CFR+, and PCFR+ The duality gap is computed every 100 iterations.
Name
Goofspiel (4 ranks)
Liar's Dice
Leduc (13 ranks)
Battleship
ECycliePDA single block
2.470
11.370
6.770
46.020
ECycliePDA children
4.270
15.020
7.450
47.230
ECyclicPDA infosets
8,850
16.240
7,370
53.490
ECyelicPDA postorder
4.340
14.350
7.430
49.020
3.720
19.530
10,360
83,450
CFR
1.330
1.360
0.370
7.980
Predictive CFR+
1.750
1.920
0.430
9.410
Discussion. We develop the first cyclic Mlock-coordinate-lkk method for two-player zero-sum EFGs. Our algorithm relies the recursive nature of the prox updates for dilated regularizers, cycling through blocks that respect the partial order induced on decision points by the treeplex, and extrapolation conduct pseudo-block updates, produce feasible iterates, and achieve ( ergodic convergence. Furthermore, the runtime of our algorithm has no dependence on the number of blocks. We present empirical evidence that our algorithm generally outperforms MP, and is the first FOM to compete with CFR+ and PCFR+ on non-trivial EFGs. Finally, we introduce a restarting heuristic for EFG solving, and demonstrate often huge gains in convergence rate. An open question raised by our work is understanding what makes restarting work for methods used with regularizers besides the l regularizer (the only setting for which there exist linear convergence guarantees). This may be challenging because existing proofs require upper bounding the corresponding Bregman divergence (for a given non-ly regularizer) between iterates by the distance to optimality. This difficult for entropy or any dilated regularizer because the initial iterate used by the algorithm after restarting may have entries arbitrarily close to zero even if they are guaranteed to not exactly be zero (as the case for entropy). Relatedly, both our block-coordinate method and restarting have much bigger advantage in some numerical instances (Battleship. Liar's Dice) than others (Ledue and Goofspiel); crucial question is to understand what type of game structure drives this behavior.
10

---

Acknowledgements
Darshan Chakrabarti was supported by National Science Foundation Graduate Research Fellowship Program under award number DGE-2036197. Jelena Diakonikolas supported by the Office Christian Kroer was supported by the Office of Naval Research awards N00014-22-1-2534 and N00014-23-1-2374, and the National Science Foundation awards IIS-2147361 and IIS-2238960.
of Naval Research under award number 100014-22-1-2445
References
[1] Aviad Aberdam and Amir Beck. An accelerated coordinate gradient descent algorithm for non-separable composite optimization. Journal of Optimization Theory and Applications, 193 (1-3):219-246, 2021.
[2] Ahmet Alacaoglu, Quoc Tran Dinh, Olivier Fercoq, and Volkan Cevher. Smooth primal-dual coordinate descent algorithms for nonsmooth convex optimization. In Advances in Neural Information Processing Systems, 2017.
[3] Zeyuan Allen-Zhu, Zheng Qu, Peter Richtárik, and Yang Yuan. Even faster accelerated coordinate descent using non-uniform sampling. In Proceedings of International Conference Machine Learning, 2016.
[4] loannis Anagnostides, Gabriele Farina, and Tuomas Sandholm. Near-optimal d-regret learning in extensive-form games. arXiv preprint arXiv:2208.09747. 2022.
[5] David Applegate, Oliver Hinder, Haihao Lu, and Miles Lubin. Faster first-order primal- methods for linear programming using restarts and sharpness. arXiv preprint arXiv:2105.12715. 2022.
[6] Yu Bai, Chi Jin, Song Mei, Ziang Song, and Tiancheng Yu. Efficient phi-regret minimization in extensive-form games via online mirror descent. In Advances in Neural Information Processing Systems, 2022.
[7] Amir Beck and Luba Tetruashvili. On the convergence of block coordinate descent type methods. SIAM Journal on Optimization, 23(4):2037-2060 2013.
[8] Noam Brown and Tuomas Sandholm. Solving imperfectt-informaiion games via discounted regret minimization. In Proceedings of the AAAI Conference on Artificial Intelligence, 2019.
[9] Yair Carmon, Yujia Jin, Aaron Sidford, and Kevin Tian. Coordinate methods for matrix games. arXiv preprint 07X4 2020.
[10] Flavia Chorobura and Ion Necoara. Random coordinate descent methods for nonseparable composite optimization. arxiv preprint arXiv:2203. /4368, 2022.
[11] Jelena Diakonikolas and Lorenzo Orecchia. Alternating randomized block coordinate descent. In Proceedings of International Conference on Machine Learning, 2018.
[12] Gabriele Farina, Christian Kroer, Noam Brown, and Tuomas Sandholm. Stable-predictive optimistic counterfactual regret minimization. In Proceedings of the International Conference on Machine Learning, 2019.
[13] Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Optimistic regret minimization for extensive-form games via dilated distance-generating functions. In Advances in Neural Information Processing Systems, 2019.
[14) Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Better regularization for sequential decision spaces: Fast convergence rates for Nash, correlated, and team equilibria. In Proceedings of the ACM Conference on Economics and Computation, 2021.
[15] Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Faster game solving via predictive blackwell approachability: Connecting regret matching and mirror descent. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.

---

[16] Gabriele Farina, Ioannis Anagnostides, Haipeng Luo, Chung- Wei Lee, Christian Kroer, and Tuomas Sandholm. Near-optimal no-regret learning dynamics for general convex games. Advances in Neural Information Processing Systems, 2022.
[17] Gabriele Farina, Chung-Wa Wei Lee, Haipeng Luo, and Christian Kroer. Kernelized multiplicative weights for -llpolyyedaall games: Bridging the gap between learning in extensive-form and normal-form games. In Proceedings of the International Conference on Machine Learning, 2022.
[18] Olivier Fercoq. Quadratic error bound of the smoothed gap and the restarted averaged primal- dual hybrid gradient. arXiv preprint arXiv:2206. 220,000400334 2023.
[19] Jerome Friedman, Trevor Hastie, and Rob Tibshirani. Regularization paths for generalized linear models via coordinate descent. Journal of statistical software, 33(1):1, 2010.
[20] Yuan Gao, Christian Kroer, and Donald Goldfarb. Increasing iterate averaging for solving saddle-point problems. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
[21] Andrew Gilpin, Javier Pena, and Tuomas Sandholm. First-order algorithm with ( convergence for e-equilibrium in two-person zero-suma sum games. Mathematical programming, 133 (1):279-298, 2012.
[22] Mert Gürbüzbalaban, Asuman Ozdaglar, Pablo Parrilo, and N Denizcan Vanli. When cyclic coordinate descent outperforms randomized coordinate descent. In Advances in Neural Information Processing Systems, 2017.
[23] Samid Hoda, Andrew Gilpin, Javier Pena, and Tuomas Sandholm. Smoothing techniques for computing Nash equilibria of sequential games. Mathematics of Operations Research, 35(2): 494-512, 2010.
[24] Christian Kroer, Gabriele Farina, and Tuomas Sandholm. Solving large sequential games with the excessive gap technique. In Advances in Neural Information Processing Systems, 2018.
[25] Christian Kroer, Kevin Waugh, Fatma Kıling-Kazzn, and Tuomas Sandholm. Faster algo- rithms for extensive-fone game solving via improved smoothing functions. Mathematical Programminng pages 1-33, 2020.
[26] Harold William Kuhn and Albert William Tucker, editors. 11. Extensive Games and the Problem of Information, pages 193-216. Princeton University Press, 2016.
[27] Chung- Wei Lee, Christian Kroer, and Haipeng Luo. Last-iterate convergence in extensive-form games. In Advances Neural Information Processing Systems, 2021.
[28] Qihang Lin, Zhaosong Lu, and Lin Xiao. An accelerated randomized proximal coordinate gradient method and its application to regularized empirical risk minimization. SIAM Journal on Optimization, 25(4):2244-2773, 2015.
[29] Viliam Lisý, Marc Lanctot, and Michael Bowling. Online monte carlo counterfactual re- gret minimization for search in imperfect information games. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, AAMAS '15, page 27-36. International Foundation for Autonomous Agents and Multiagent Systems, 2015, ISBN 9781450334133
[30] Ji Liu, Stephen J. Wright, Christopher Ré, Victor Bittorf, and Srikrishna Sridhar, An asyn- chronous parallel stochastic coordinate descent algorithm. arXiv preprint arxiv:1311.1873 2014.
[31] Mingyang Liu, Asuman Ozdaglar, Tiancheng Yu, and Kaiging Zhang, The power of regular- ization in solving extensive-fomt games. Proceedings of the International Conference on Learning Representations, 2023.
[32] Rahul Mazumder, Jerome H Friedman, and Trevor Hastie. Sparsenet: Coordinate descent with nonconvex penalties. Journal of the American Statistical Association, 106(495): 125-1
2011.
12

---

[33] Arkadi Nemirovski. Frox-method with rate of convergence o (1/t) for variational inequali- ties with lipschitz continuous monotone operators and smooth convex-concayy saddle point problems. SIAM Journal on Optimization, 15(1):229-251, 2004.
[34] Yu. Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization, 22(2):341-300 2012.
[35] Yurii Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Programmingg 109(2-3):319-33) 344, 2007.
[36] Sheldon M. Ross. Goofspiel the game of pure strategy. Journal of Applied Probability, 8(3): 621-625, 1971.
[37] Ankan Saha and Ambuj Tewari. On the nonasymptotic convergence of cyclic coordinate descent methods. SIAM Journal on Optimization, 23(1):576-601, 2013.
[38] Hao-Jun Michael Shi, Shenyinying Tu, Yangyang Xu, and Wotao Yin. primer on coordinate descent algorithms. arXiv preprint arXiv:1610.000400, 2016.
[39] Chaobing Song and Jelena Diakonikolas. Fast cyclic coordinate dual averaging with extrapola- tion for generalized variational inequalities. arXiv preprint 122.::22022.2244., 2021.
[40] Finnegan Southey, Michael P. Bowling, Bryce Larson, Carmelo Piccione, Neil Burch, Darse Billings, and Chris Rayner. Bayes' bluff: Opponent modelling in poker. arXiv preprint 1rX7vv1207.1444 2012.
[41] Oskari Tammelin. Solving large imperfect information games using CFR+. arXiv preprint arXiv: 1407.5004 2014.
[42] Oskari Tammelin, Neil Burch, Michael Johanson, and Michael Bowling. Solving heads-up limit Texas hold' em. In Tweent-Fourth International Joint Conference Artificial Intelligence. 2015.
[43] Paul Tseng, On linear convergence of iterative methods for the variational inequality problem. Journal of Computational and Applied Mathematics, 60(1-2):237-252, 1995.
[44] Bernhard von Stengel. Efficient computation of behavior strategies. Games and Economic Behavior, 14(2):220-244 1996.
[45] Chen-Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate conver- gence in constrained saddle-point optimization. In Proceedings of International Conference on Learning Representations, 2021.
[46] Stephen J. Wright. Coordinate descent algorithms. Mathematical Programming, 151(1):3-34, 2015.
[47] Tong Tong Wu and Kenneth Lange. Coordinate descent algorithms for lasso penalized regression. The Annals of Applied Statisties, 2(1):224-244: 244, 2008
[48] Yuchen Zhang and Xiao Lin. Stochastic primal-dual coordinate method for regularized empirical risk minimization. In Proceedings of International Conference on Machine Learning, 2015.
[49] Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret mini- mization games with incomplete information. In Advances in Neural Information Processing Systems, 2007.
13

---

A Additional Related Work
There has been significant work on FOMs for two-player zero-sum EFG solving. Because this BSPP, off-the-shelf FOMs for BSPPs can be applied, with the caveat that proximal oracles are required. The standard Euclidean distance has been used in some cases [2T] but it requires solving a projection problem that takes (n log" n) time, where n is the dimension of a player's decision space [16] 21). While this is "nearly" linear time, such projections have not been used much in practice. Proximal oracles have instead been based on dilated regularizers [23], which lead to a proximal update that can be performed with a single pass over the decision space. With the dilated entropy regularizer, this can be performed in linear time, and this regularizer leads to the strongest bounds on game constants that impact the convergence rate of proximal-oracle-bee FOMs [14 25 More recently, it has been shown that a specialized kernelization can be used to achieve linear-time proximal updates and stronger convergence rates specifically for the dilated entropy with optimistic online mirror descent through correspondence with optimistic multiplicative weights on the exponentially-many vertices of the decision polytope 17). Yet this approach was shown to have somewhat disappointing numerical performance in Farina et al. 17 and thus is less important practically despite its theoretical significance.
A completely different approach for first-orders order-based updates is the CFR framework, which decom- poses regret minimization on the EFG decision sets into local simplex- based regret minimization [49] In theory, CFR-based results have mostly led to an inferior 1 rate of convergence, but in practice the CFR framework instantiated with regret matching* (RM-) [41] or predictive RM (PRM+) [[5] is the fastest approach for essentially every EFG setting. RM+ is often fastest for "poker-like" EFGs, while PRM+ is often fastest for other classes of games [15]. Improved rates on the order of T-3/1 12 and log T/T [4] have been achieved within the CFR framework, but only while using regret minimizers that lead significantly worse practical performance (in particular, numerically these perform worse than the best I/T FOMs such as mirror prox with appropriate stepsize tuning).
In the last few years there has been a growing literature on last-iterate convergence in EFGs. There, the goal is to show that one can converge to an equilibrium without averaging the iterates generated by FOM or CFR-bil based method. It has long been known that with the Euclidean regularizer, it is possible to converge at a linear rate in last iterate with e.g., the extragradient method (a.k.a. mirror prox with the Euclidean regularizer)
BSPPs with polyhedral decision sets, they are in EFGs [1 45 (55. More recently, it has been shown that a linear rate can be achieved with certain dilated regularizers (27), with the kernelization approach of Farina et al. [7]. and in regularized CFR setup 31. At this stage, however, these last-iterate results are of greater theoretical significance than practical significance, because the linear rate often does not occur until after quite many iterations, and typically the methods do not match the performance of ergodic methods at reasonable time scales. For this reason, we do not compare to last-iterate algorithms in our experiments.
B Treeplex Example
As an example, consider the treeplex of Kuhn poker (26 adapted from 13 shown in Figure 5 Kuhn
poker is game played with three card deck: jack, queen, and king. In this case, for example, we
have Jx - {0, 1, 3, 4,5,6), P0- 0. pI = p22 p3 - (0, start), P4 = (1, check), p5- = (2, check), ) Ps = (3, check). Ao = [start), A = A2 = Ag = {check, raise), A4 = A5 = As = ffold, call].
Cio.sum) (1, C(I,rass))
C(I.mis))) = C(2,mise) = C ((3.ra)s)) C(4,60l)) = C(s.tou) = Cio
C( = C(I.cal)) C(6,call) = 0. 1 a= Jx, 4 {1, 4 {2, 5). 3 (3, 6). 4 4 = (4).
45 (5). 16- 6 {6). In this case, 0 represents the empty sequence.
C Proofs
C.1 Proof of Proposition 3.1
Proof. The claim that x2 E EY 3/ immediate from the algorithm description, as both are solutions to constrained optimization problems with these same constraints.
14

---

X
start
Jack
quéen
king
check
check raisp
check
raise
check rajsc
check cajse
check raise
X4
Xs
Xe
fold call
fold call fold call
Figure 5: The sequential decision problem for the first player in Kuhn poker. represents the end of the decision process and @ represents an observation (which may lead to multiple decision points). Adapted from [13]
For the remaining claim, observe first that
Tis (Mx;, v) IJs (ge, v) D& (v. Dv (Mxs 8R, v).
Recall from Algorithm that
Yk = argmax vEY
Thk (gk. v) 100--Dov. Do.v.
Define the function under the max defining yı by Mx Then as 2 ) is the sum of -+(-) and linear terms, have Dwa (: ( y), for any y. Further, as V/ is maximized by yk: have P (v) I (v() D (v. Thus, it follows that
(Mx,, v) S m/ yk) - Yk + (Mxs - -kk, DDp(v. + Dolv,
(C.1)
Using the same ideas for the primal side, we have Thk (Mu, yu)
mh (Xx, h&) Ds(x,, Xx- + 176 (u, M TTy ya - ha)
(C.2)
+ Do xx) Do(u, xx-1)
Combining
C.II and C.2
ni Gap u.v (Xk, I M4 (Mx; - Bk. V -
yk) - 17k (u Xx. M yk - -ha)
- (o (x(x x6-1)
Do(u, + (D(1,,
xx-1) - (v, + (v.
To complete the proof, it remains to combine the definition of Eg from the proposition statement with the last inequality.
C.2 Proof of Theorem 3.2
For notational convenience, in this proof we define vectors & and 8x by 8g
x x for
21
j E Jx and 8k. y2 V for j Ty, so that X 8x 1e-1 7/
(XK-1
8R-1)
and
Ys = yk 84 7h-1 (yk-1
v2-1).
To prove the theorem, first prove the following auxiliary lemma which bounds the inner product terms appearing in the error terms ε
Lemma C.1. In all iterations k of Algorithm 7 for any (u, v) X x y and any a, 8 > O,
mh (Mx ga, yx) S Th (My (X+ &2), yk) T)--1 (My (x-11 3x-1), Yk-1) + mh (Mx(xx X1 xx_1), -- yn) Mh- (M (xx 1 - Xx-2), v yk-
Mx + || (al|xx-1
Xx 21 +|Myyll(a||xxX-1
1
Ily yx-1113)
77
2
a
15

---

and
-ink (u (u, Mr yk -be) S - 7h (M, (yx Fk., u - Xx + n (M, (y x- - Fk-1); u - xK-1)
Tn (My (y= yk-1), -xx) + 7/=- (M, (yx-1 Ya 2k- xx-1)
M +My 1l. [8|xx-11 - xx112 lyk-1 - -xx-2yx-21 y2-21?²) 3
+ 7
Proof. Observe first that, by Algorithm 1
M Xx 8k
(8)
(t.1.a)
Xx 86
7k-1
(xk-1 82-11) (1:)
1/k
(C.3)
11 (x - -Xx-)) xx-2)
((+1:))
X;: - -X
7/1
Additionally, by definition (see Eq.
331 Ei=1 M = M MM- - -My. Hence,
M
x5
-8p
(xk-1 {( (1:) v(()) Yk
(2)
11
M2,1.a
Xx - xx
7 (x *(-1)) .v - -Yv
My Xk 8x 77-1 (xx-1 - 8z -1 v yk
Th
1/2
= 7T (My (X: -x), v - yyk) 1--- (My (x - 8b-1), V yk-1)
7k-1 1 (My (xx-1 -8:-1), Yk-1 yk)
(C.4)
The
first
two terms in C.4
telescope,
focus
bounding
Th
(M 2x-1),yk-o Yk) By definition of & for all j E Jx,
x
x
x
(alt k- - x2-2).
By the definition of a treeplex, each vector size. This further implies that
belongs a probability simplex of the appropriate
|x=-1 84-111 =
(2h x
x
jEJX
< || p1 2'=Dle
< || x6-2l1 ell
(C.5)
where the notation (e')jen, is used to denote the vector with entries a², for j E Jx. The first inequality in (C.5) holds for any l, norm (p 2 1), by its definition and (1,x = 1, Vj. Thus, applying the definitions of the norms from the preliminaries,
-(My 21-1). ya) < [M xx - ykl
< My M Xx-22llly+-1 - y+ll
My (al|xe-1- - 21 - lyyk 11-1 (C.6)
2
where the last line is by Young's inequality and holds for any > 0.
16

---

On the other hand, recalling that Mx -i==
Mc,++:ss we also have
(
Xk
X
7k-1
1K--1-XX-20
Xx-2) (e+1:s)
v(t) yk
1/k
7/
M
Xk Xx
Th-1
(Xk-1 Xx-2)) .v- yk
1/6e
1=1
Xx: Xk=1 1 (xx-1 - xxx-2) -Yk
Mx
9/6:
7h (Mx (X): - 1)) V- 10--y, V&) - 17/=11 (Mx xx- V - -Vk)
7T (Mx(XX (Xk- - -k--)); V-
11y-yy, yu) - -1]--1 1 x2- - v-yk-)
+ - (Mx(Xx-11 - Xk- 2) -k-1)
(C.7)
Observe that in (C.7) the first two terms telescope and thus only need to focus bounding the last term. Applying the definitions of dual and matrix norms from Section 2 and using Young's 's inequality, we have that for any a 0,
(Mx(xx-1- - Xk- 2k-2), Yk Yk-1) S -xx
- yx-1ll
S [ [x
x Yk-1
| (al|xt-1 Xk x1- llye yx-112). (C.8)
s 2
Hence, combining
CC33
C.S), we can conclude that
Th (Mx² gk. V Yk) S The (My(x; &2), V - yx) - 17--1 (My (xx-1 - 1)=1); V- - y2-1)
Tk (Mx Xx-1), yk) 7/-11 (Mx xx-2); yk-1)
Mx + |Myll (al|xx- Xx 211 _ Ily& yx-111?)
7/
2
a
completing the proof of the first claim.
Similarly, we observe from Algorithm Dthat
(M Yk b (M(() T (yx -8x +
9k-11 (yk-1 8(-1) (lit-1)
+ (M(2)).)) T (yk- vk-1+
1/k-1 (yk-1 yk-2) (1:8)
Observing that Σi= M1 = Mx and Σi=1 My:s, = My. using the same sequence of argu-
ments as for bounding CC.)) we can conclude that for any B >
7]k (u Xk. M Yk h4)
5 -m (M (yn ~n); u xx) + 7/ (M (yk-1 8k- 1)=-1), 1), xx-1)
; u - Xx-1) .T (My (yx - yk-1), u -xx) + 7/-1-1 (My (yk-1 22-
J + +MJ 11+ (81 - x4112 -
+ 7
2
completing the proof.
Proof Theorem 3.2 Recalling the definition of Ex, by Lemma
Ex S 7k
My (xk 8x), v yu) 7 (My (x:-1 8x ) v yb-1)
+ 7h MM - xx-1), v- - yt) - 7 (Mx (x6-1 X4-2), v - Yk-1)
| |1+ + || (allxx-1- 2 + |lyx - yx-2l1 112)
+ 7/4
Th (MI (ya - -ba), u xxx) + 71-1 (M, (yk-1 - 8 ()=1), xx-1)
(C.9)
"Th (M. (yx 1k- u xx) + 71- (M,) (y yx-2), ) u xx-1)
[M ||- + |IM]]I I1. (311x8-1- xx 11yy1----221
1
+1h-1
2 - -Do(ys, - Do( Xx-1).
17

---

Recalling that 1p is Cg -t--nnyy convex, is C6. co-strongly convex, setting = B =
/ and using
that f/k-1 S |Mall++ I1- Vegge
yages
C.99
simplifies to
M + I 1- Ra thy
Ex S Th (My Xx xx); V- yn) - 9k-1 (My (x xx_), --kk1)
+ Th (Mx (X: - Xt-1), v -yx) - (M, [x Xx xx- 2),y yk-1)
mh (M& (yx= -5k), u -xxx + 7 (Mx (yk-1 1),1), -X--1)
The (My (yx: - -Yk-1), u - xx) + 7 (My (yk-1 yk-22,, u - xk-1)
(C.10)
colly (1y%-1 - yk-2 lly: - yk--1
+ 2(U + kg)
+ 2( + Hy)
Calfiz
(1xx/-1 - xx-2 ||x - -x--1
Telescoping (0.10) and recalling that Y/o = 0, we now have
K
E S 1KK (Mx(xK- - xK-1), - yx) 1K (My (yx - -y--)) u- xk)
1=1
лk (My(X - -R). v- yk) 7K (yK -xx), xx)
(C.11)
Coply
|yK -x--1 1l?
2(1 Byy)
Coffe
2(1 (yy) |IK 1111112
Observe that Gap">(.)) is linear in both its arguments. Hence, Gap". 5K)
1 Ei= The Gap" (Xxa"""X; Yk)) Applying Proposition 3.1 and combining with (C.1l) we now have
Hx
Gap (Rt. Fx) S Du xo) + yo)
+ TK (Mx(xX - XK-I), yK) TKK (M2 (yK - YKK-)), u xK)
+ T (My(xx- - v
- yK) - 1IK (M, xy - -Kx), u u-x)
Coply. 1lyk- - 112 2(1z + Myy
Coflz
||Xx - x22
2( + My)
Do xK) - Dv)
(C.12)
To complete bounding the gap. it remains to argue that the right-hand side of (C.12 is bounded (v, This is done using the same
by (u, Xo) + yo) - M.t (u, put
By
sequence of arguments as in bounding & and is omitted.
Let y") X x Y' be any primal-dual solution can conclude that
PD). Then Gap y (Xx, FK) 2 and
fi Dx(x" xk) + By D yK) s (o(x', xo) + D No))
Ne My Further, using that De(..)) 2 0, Dw(.,)) N 0, we can also conclude that
Hz + Bly
sup vEX.VEy
Gap u. (Kx, uEX.VEy
sup
{MMX, v) (Mu}
SuPuEX (D Xo) + (v, HK
Finally, setting 7p
Siag for all l: immediately leads the conclusion that Hx K Pagie Pyy
Mrttyy
k= as Hx = Ekn Mk, by definition. The last bound is by setting suPucx.vey ( (D)( < E, and solving for K.
HK
D Algorithm Implementation Details
In Algorithm 2. we present an implemmnttaiion-specfff version of ECyclicPDA, in order to make it clear that our algorithm can be implemented without any extra computation compared to the
18

---

We focus the updates for x; the argument is analogous for y- When applying this local prox update for decision point j E (x)",, we have already correctly computed h', the contributions to the gradient for the local prox update that originate from the children of j, again because the blocks represent the treeplex ordering: in particular, whenever we have encountered child decision point j j in the past, we accumulate its contribution to the gradient for its parent at hi Since the prox update decomposition from Proposition 2.2 has to be applied for every single decision point in Jx in computation needed for gradient and prox updates in MP. Note that MP performs two gradient computations and two prox computations per player, due how achieves "extrapolation", we want to argue that we perform an equivalent number operations as needed for a single gradient computation and prox computation per player. Note that the overall complexity of first-order methods when applied to EFGs is dominated by the gradient and prox update computations; this is why we compare our algorithm to MP on this basis. The key differences from Algorithm [ are that we explicitly use x and y& to represent the behavioral strategy that is computed via the partial prox updates (which then scaled the end of full iteration of our method to X and yı), and that use hy and g to accumulate gradient contributions from decision points that occur underneath j, to make the partial prox update explicit.
In Lines [3] we are only dealing with the columns and rows, respectively, of the payoff matrix that correspond to the current block number t, which means that as ranges from 1 to for the computation of the gradient, we will only consider each column and row, respectively, once, as would have to be done in full gradient computation for MP.
The more difficult aspect of the implementation is ensuring that we do the same number of operations for the prox computation in ECyclicPDA as an analogous single prox computation in MP. We achieve this by applying the updates in Proposition 2.2 only for the decision points in the current block, in Lines 9 to 12 for and 14 to 17 for y-
a full prox update (as done in MP), we again do not incur any dependence on the number of blocks.
E
Description of EFG Benchmarks
We provide game descriptions of the games we run our experiments on below. Our game descriptions are adapted from Farina et al. [15). In Table 2 we provide the number of sequences for player x (n), the number of sequences for player (m), and the number of leaves in the game (NNZ(M)).
Table 2: Number of sequences for both players and number of leaves for each game. These correspond to the dimensions and of M, and the number of nonzero entries of M, respectively.
Game
Num. of x sequences
Num. of sequences
Num. of leaves
Goofspiel (4 ranks)
21329
21329
13824
Liar's Dice
24571
24571
147420
Leduc (13 ranks)
6007
6007
98956
Battleship
73130
253940
552132
E.1 Goofspiel (4 ranks)
Goofspiel is a card-based game that is a standard benchmark in the EFG-solving community [36]. In the version that we test on, there are 4 unique cards (ranks), and there are 3 copies of each rank, divided into separate decks. Each player gets a deck, and the third deck known as the prize deck. Cards are randomly drawn from the prize deck, and each player submits bid for the drawn card by submitting card from one of their respective decks, the value of which represents their bid. Whoever submits the higher bid wins the card from the prize deck. Once all the cards from the prize deck have been drawn, bid on, and won by one of the players, the game terminates, and the payoff' for players given by the sum of the prize cards they won.
19

---

Algorithm 2 Extrapolated Cyclic Primal-Dual EFG Solver (Implementation Version)
1: Input: M, M,
2: Initialization: Xg NY Yo EV, Hog 0,
8o Xo. 8o
yo. go 0, ho
3: for == 1: K do
4: Choose ?K S 7, H5 Hk-1 + 1/K
5: Bk 0, h2 O. 8k
0, hR:
6:
X = x;-1 +
Mh-1 (xk-1 xx--),, = -x- Yk-1
(yk-1 -x-22 M--1 mu
7:
for / = 1 do
h1 (MG.) Ty
8:
9:
for j E Jx (t) do
x argmin EA {(ig hig, by) Dev (b,,%
11:
(i', a) Pj
h/ += ألا"" (-ng² + Vot (att di (x%=1) ( (V (861))
12:
13:
8t ( Xk
for j E Jy (t) do
14:
15:
8/ = argmingres">
(B b')) + Das (b'.8%-1))
16:
(J',a) = Pj
hg += ر/ (-Bt + Viiitt (x - w/اt (Hk-1) + ( (Te
17:
18:
for j E Jx" (8) do
Mh- (xx (x - 8/L z =
19:
x = x x
+
ma
20:
for j E Jy do
21:
5/
Mk-1 4h
(yk-
22:
for j E Ix do
23:
x = zx x
24:
for j E Jy do
25:
y/ = y/ y
26:
X4
H2 Ue -1-1 + H
Hu
Xb.
V4
Hg-mE tee Hu
v +
D/t Hg Yk
27:
Return: JK
E.2
Liar's Dice
Liar's Dice is another standard benchmark in the EFG-solving community (29). In the version that we test on, each player rolls an unbiased six-sided die, and they take turns either calling higher bids challenging the other player. A bid consists of combination of value between and a number of dice between one and two, n, representing the number of dice between the two players that has pips showing. A higher bid involves either increasing holding u fixed, increasing e holding n fixed, or both. When a player is challenged (or the highest possible bid of "two dice each showing six pips" is called), the dice are revealed, and whoever is correct wins I (either the challenger if the bid is not true, or the player who last called a bid, if the bid is true), and the other player receives utility -1.
and six,
E.3 Ledue (13 ranks)
Ledue is yet another standard benchmark in the EFG-solving community 40 and is simplified version of Texas Hold'Eni Em. In the version we test on, there are 13 unique cards (ranks), and there are 2 copies of each rank (half the size of a standard 52 card deck). There are two rounds of betting that take place, and before the first round each player places an ante of into the pot, and is dealt a single pocket (private) card. In addition, two cards are placed face down, and these are community cards that will be used to form hands. The two hands that can be formed with the community cards are pair, and highest card.
20

---

During the first round of betting, player acts first. There is max of two raises allowed in each round of betting. Each player can either check, raise, or fold. a player folds, the other player immediately wins the pots and the game terminates. If player checks, the other player has an opportunity to raise if they have not already previously checked or raised, and if they previously checked, the game moves to the next round. If player raises, the other player has an opportunity to raise if they have not already previously raised, The game then moves on the second round, during which one of the community cards is placed face up, and then similar betting dynamics the first round take place. After the second round terminates, there a showdown, and whoever can form the better hand (higher ranked pair, or highest card) with the community cards takes the pot.
E.4 Battleship
This is instantiation of the classic board game, Battleship, in which players take turns shooting at the opposing player's ships. Before the game begins, the players place two ships of length 2 and value 4, on grid of size 2 by The ships need be placed a way so that the ships take up exactly four spaces within the grid (they do not overlap with each other, and are contained entirely in the grid). Each player gets three shots, and players take turns firing at cells of their opponent's 's grid. A ship is sunk when the two cells it has been placed on have been shot at. At the end of the game, the utility for a player is the difference between the cumulative value of the opponent's 's sunk ships and the cumulative value of the player's sunk ships.
F Block Construction Strategies
As discussed in the main paper, the postorder block construction strategy be viewed traversing the decision points of the treeplex in postorder, treating decision points with the same parent sequence the same node, and then greedily putting decision points in the same block until reach decision point that has child decision point in the current block (at which point we start a new block). We make this postorder traversal and greedy block construction explicit in Algorithm
In Algorithm/ 4 we provide pseudocode for constructing blocks using the children block construction strategy. As discussed in the main paper. the children block construction strategy corresponds to placing decision points with the same parent decision point (same decision point at which their parent sequences start at) in the same block. In our implementation, instead of doing bottom-up traversal, we do a top down implementation, and at the end, reverse the order of the blocks (this allows us to respect the treeplex ordering).
both Algorithm and Algorithm
@ represents the empty sequence.
Algorithm 3 Postorder Block Construction
1: procedure POSTORDERHELLPERj, a)
2: accumulator =
3: for j' E Cr.a do
4: for a' E Ay. do
5:
accumulaor.inerrppsooddeett
6: for j' E Cj.a do vicuuulator.inser((j)
7:
8: Return: accumulator
9: procedure POSTORDERBLOCKSLL
ordered POSTORDER 11: blocks =
12: current_blec blockllcc----
13:
for j E ordered do
if ar' current block s.t. j' is child decision point of j then blocks.inser(ccurentt block)
15:
current_block [i]
17:
else
current block.insert(j)
19:
return: blocks
21

---

Algorithm 4 Children Block Construction
1: procedure CHILDRENBLOCKS(())
2: blocks 0
3: explore = Co
4: for j E explore do current block = 6: for a E A; do for E Cj,a do current prveet_bbock.iiee )nnerti))) innser()))))r((() blocks boocks.insert(ee cerseertcureet_ba.. block)
5:
7:
8:
9:
10:
return: rloerse))verse()
We can now illustrate each of the block construction strategies on the treeplex for player in Kuhn that was presented in Appendix B If we use single block, then we have Jx (1) Jx 2, 3, 4, 5, 6}. If we use infosets, then have Jx (4) {7 i) for E 21, 4, 5, 6, 7) (we have subtract in order to label the infosets in manner that respects the treeplex ordering) If we use children, then
(4) {1, 3). and Jx (5) = {0}. If we use we have Jx (1) = (4). Jx (2) {5}. Jx (3) (6) = 21,2,3),
postorder, then have Jx (1) (4,5, 6). 3,, and Jx (3) {0}.
Note that in the implementation of our algorithm, blocks for both players are the same; if one player has more blocks than the other, for iterations of our algorithm that correspond to block numbers that do not exist for the other player, we just do not do anything for the other player. Nevertheless, the output of the algorithm does not change if we combine all the blocks for the player with more blocks after the minimum number of blocks between the two players is exceeded, into one block. For example, if player I has 81 blocks, and player 2 has 82 blocks, with 81 < 82, we can actually combine blocks 81 + 1,..., for player 2, and this would not change the execution of the algorithm. This is what do in our implementation.
not actually important that the number of
,.....,8 82 all into the same block
Additionally, given a choice of a partition of decision points into blocks, there may exist many permutations of decision points within the blocks which satisfy the treeplex ordering of the decision points. Unless the game that is being tested upon possesses some structure which leads to a single canonical ordering of the decision points (which respects the treeplex ordering), an arbitrary decision needs to be made regarding what order is used.
G Experiments
G.1 Additional Experimental Details
Block Construction Strategy Comparison. In this section, we provide additional plots (Figures 6 14) comparing different block construction strategies for our algorithm, for specific choices of regularizer and averaging scheme. Note that for the games for which there is a benefit to using blocks (Liar's Dice and Battleship). the benefit is generally apparent across different regularizers and averaging schemes. Furthermore, when there is not a benefit for a particular regularizer and averaging scheme, there is significant cost either (using blocks does not lead to worse performance).
Block Construction Strategy Comparison with Restarts. We repeat similar analysis as above (comparing the block construction strategies holding regularizer and averaging scheme fixed) but this time with the adaptive restarting heuristic applied to our algorithm: the plots can be seen in (Figures 15 to 23). As mentioned in Section 4 we prepend the algorithm name with "Y" to denote the restarted variant of the algorithm in the plots.
As discussed in the main body, the trend of the benefit of using blocks being more pronounced with restarting (for games for which blocks are beneficial) holds generally even when holding the regularizer and averaging scheme fixed. This can be seen by comparing each of the restarted block construction strategy comparison plots with the corresponding non-restarted block construction strategy comparison plot.
22

---

Gooffpicl ranks)
Lior's Diec
Ledue ranks)
Battleship
Dualiy gan
y/
uf Gradient computations
Gradient computations
Gradient computatiooss
Gradient computations
BCyeliePDA single block
BCyellePDA postorder
BCyeliePDA children
ECyelicPDA infoects
Figure 6: Duality gap as function of the number of full (or equivalent) gradient computations for ECyclicPDA with different block construction strategies when using the dilated entropy regularizer and uniform averaging.
Goofspicl
Lediee
Battleship
Dualit gop
Gradient computations
Gradient computations
Gradlent computations
Gradient computations
BCyeliePDA single
BCyelicPDA postorder
ECyclieDA children
ECyelicPDA
Figure 7: Duality gap as function of the number of full (or equivalent) gradient computations for ECyclicPDA with different block construction strategies when using the dilatable global entropy regularizer and uniform averaging.
Grafspiel ranks)
Liar's Dice
Leduc ranks)
Ratrleship
Duality gop
10
10
Gradient computations
Gradient computations
Gradiont computations
Gradient computations
ECyaliePDA single block
ECyelicPDA postonder
ECyclicPDA children
ECyeliePDA infosets
Figure 8: Duality gap as function of the number of full (or equivalent) gradient computations for ECyclicPDA with different block construction strategies when using the dilated &² regularizer and uniform averaging.
Goofspiel ranks)
Liar's Diee
Ledue ranks)
Baitleship
Duality gap
>
122
tom
Gradient computations
Gradient computations
Gracient computations
Gradient computations
ECyeliePDA single block
BCyeliePDA postorder
ECyeliePDA children
HCyelicPDA infoscts
Figure 9: Duality gap as function of the number of full (or equivalent) gradient computations for ECyclicPDA with different block construction strategies when using the dilated entropy regularizer and linear averaging.
23

---

Goofspiel ranks)
Lior's Diec
Ledne ranks)
Battleship
>f
Duality gap
10
1pf
uf Gradient computations
Gradient computations
Gradient computatioon
Gradient compurations
BCyeliePDA single block
BCyellePDA postorder
BCyclicPDA children
ECyelicPDA infoscts
Figure 10: Duality gap as a function of the number of full (or equivalent) gradient computations for ECyclicPDA with different block construction strategies when using the dilatable global entropy regularizer and linear averaging.
Goofspiel
Lediee ranks)
Battleship
Dualtt gop
if Gradient computations
Gradient computations
Gradient computations
Gradlent computations
BCyeliePDA single
BCyelicPDA postorder
ECyclieDA children
ECyelicPDA infoscts
Figure 11: Duality gap as a function of the number of full (or equivalent) gradient computations for ECycliePDA with different block construction strategies when using the dilated &² regularizer and linear averaging.
Grafspiel ranks)
Liar's Dice
Leduc ranks)
Rairleship
Duality gop
12
10
10:7
Gradient computations
Gradient computations
Gradiont computations
Gradient computations
ECyaliePDA single block
PCyelicPDA postonder
ECyclicPDA children
ECyeliePDA infosets
Figure 12: Duality gap as a function of the number of full (or equivalent) gradient computations for ECyclicPDA with different block construction strategies when using the dilated entropy regularizer and quadratic averaging.
Goofspiel ranks)
Liar's Diee
Ledue ranks)
Battleship
Duality gop
Gradient computations
Gradient computations
Gradient computations
Gradient computations
ECyeliePDA single block
BCyeliePDA postorder
ECyeliePDA childron
ECyelicPDA infoscts
Duality gap as a function of the number of full (or equivalent) gradient computations for ECyclicPDA with different block construction strategies when using the dilatable global entropy regularizer and quadratic averaging.
Figure 13:

---

Gootspiel (4 ranks)
Liar's Dioe
Ledine (13 ranks)
Harrlship
Duality gap
12"
1f"
w/ Gradient computations
Gradient computations
Gradient compotations
Gradient computations
BCyellePDA single block
BCydleeDA postonder
BCydlcPPAA children
HCycliePDA infosets
Figure 14: Duality gap as function of the number of full (or equivalent) gradient computations for ECyclicPDA with different block construction strategies when using the dilated regularizer and quadratic averaging.
Goofspicl
Leduc ranks)
Battleship
Duality gop
1o
10:2
Gradicnt computations
Gradicnt computations
Gradiont computations
Gradient computations
rBCyclicPDA single block
rBCyeli<DDA postorder
cCyelicPDA
rECycliePDA infosets
Figure 15: Duality gap as a function of number of full (or equivalent) gradient computations for ECyclicPDA with different block construction strategies when using the dilated entropy regularizer and uniform averaging as well as restarting. We take the best duality gap seen so far so that the plot
monotonic.
Goafspiel ranks)
Liar's Dice
Leduc ranks)
Battleship
Duality gap
Gradient computations
Grudient computations
Gradient computations
Gradient computations
rFCyclicPDA single block
#ECyclicPDA postonder
rECyalicDA children
rBCycliePDA infosets
Figure 16: Duality gap as function of the number of full (or equivalent) gradient computations for ECyclicPDA with different block construction strategies when using the dilatable global entropy regularizer and uniform averaging as well as restarting. We take the best duality gap seen so far so that the plot is monotonic.
Goofspiel (4 ranks)
Liar's Diec
Lediee (13
Battleship
Duality gop
10
10:2
122
of
tnd Gradient computations
122
tel Gradient computations
Gradient computations
Gradlent computations
iBCyclicPDA single block
rBCycliePD postorder
iECyclicDA children
rBCyclieDA infosets
Figure 17: Duality gap as function of the number of full (or equivalent) gradient computations for ECycliePDA with different block construction strategies when using the dilated e regularizer and uniform averaging as well as restarting. We take the best duality gap seen so far that the plot is monotonic.
25

---

Gooffpiel (4 ranks)
Liar's
Ledne rooks)
Battlehip
Dualry gap
10111
computations
Gradient computations
compurations
Gradient computations
iBCyelicPDA single bloek
BCCycliPDA postorder
ECyelicPDA childrea
rBCyctieDDA infosets
Figure 18: Duality gap as a function of the number of full (or equivalent) gradient computations for ECyclicPDA with different block construction strategies when using the dilated entropy regularizer and linear averaging as well as restarting. We take the best duality gap seen so far so that the plot is monotonic.
Goofspiel (4 ranks)
Liar's Diee
Ledue ranks)
Battleship
Dualit gop
10"7
Gradient computations
Gradient computations
Gradlent computations
Gradient compatations
rECyclicPDA single block
PDC postorder
rECyelicDDA
rBCyclicPDA infosets
Figure 19: Duality gap as a function of the number of full (or equivalent) gradient computations for ECyclicPDA with different block construction strategies when using the dilatable global entropy regularizer and linear averaging as well as restarting. We take the best duality gap seen so far so that the plot is monotonic.
Gonffspiel ranks)
Leduc ranks)
Hatrleship
Duality gap
1o17
10""
Gradient computations
Grudient computations
computations
Gradient computations
rSCyclicPDA single block
#CCycliPDA postorder
#HCyelicDDA chikdren
rHCycliePDA
Figure 20: Duality gap as a function of the number of full (or equivalent) gradient computations for ECycliePDA with different block construction strategies when using the dilated g2 regularizer and linear averaging as well as restarting. We take the best duality gap seen so far so that the plot is monotonie.
Goofspiel ranks)
Liar's
Ledue ranks)
Battleshp
Dualty gap
10-1
10"5
computations
Grudient computations
compurations
Gradient computations
iBCyelicPDA single block
rCCeclePDA postorder
ECyelicPDA children
rBCyetiePDA infosets
Figure 21: Duality gap as a function of the number of full (or equivalent) gradient computations for ECyclicPDA with different block construction strategies when using the dilated entropy regularizer and quadratic averaging as well as restarting. We take the best duality gap seen so far so that the plot monotonic.
26

---

Groffspiel (4 ranks)
Liar's Diee
Leduc (13 ranks)
Hattleship
Duality gop
10
Gradicnt computations
Gradicat compatations
Gradiont computations
Gradient computations
rbCyelicPDA single block
(CCycliPDAA postorder
#CyellieDA children
rHCycliePDA infosets
Figure 22: Duality gap as function of the number of full (or equivalent) gradient computations for ECyclicPDA with different block construction strategies when using the dilatable global entropy regularizer and quadratic averaging as well as restarting. We take the best duality gap seen so far so that the plot monotonic.
Goofspiel (4 ranks)
Liar's Dice
Leduc ranks)
Battleship
Duality gop
>f
10:2
Gradient computations
Gradient computations
Gradient computations
Gradient computations
:BCyclicPDA single block
rBCyclieDA postorder
rCyelicPDA children
:ECyclieDA infosets
Figure 23: Duality gap as a function of the number of full (or equivalent) gradient computations for ECyclicPDA with different block construction strategies when using the dilated (2 regularizer and quadratic averaging as well as restarting, We take the best duality gap seen so far so that the plot is monotonie.
Regularizer Comparison. In this section (Figures 24 to 26 we compare the performance of ECyclicPDA and MP instantiated with different regularizers for each averaging scheme, against the performance of CFR and PCFR
is apparent from these plots, that our algorithm generally outperforms MP, holding the averaging scheme and regularizer fixed. This can be seen by examining the corresponding figure for choice of averaging scheme, and noting that for any given regularizer, the corresponding MP line generally above the corresponding ECyclicPDA line.
Regularizer Comparisons with Restarts. We repeat similar analysis in this section (Figures 27 to 29). instead now comparing the performance of ECyclicPDA and MP instantiated with different regularizers for each averaging scheme, against the performance of CFR and PCFR+ when all methods are restarted. The trend noted above of our method generally beating MP, even holding the regularizer and averaging scheme fixed, still holds even when restarting.
Goofspiel ranks)
Liar's
Ledue ranks)
Battleship
Dusliyy gan
ton
12'
Gradient computations
Gradient computations
Gracieet computations
Gradient computations
ECyeliPDAA dilated entropy
ECyeliePDA dilated
dilatable global entropy
CHR
ECyeliePDA dilatable global entropy
dilated entropy
dilated
Figure 24: Duality gap as a function of the number of full (or equivalent) gradient computations for ECyclicPDA, MP, CFR+, PCFR+ using a uniform averaging scheme for ECyclicPDA and MP.
27

---

Goofspiel (4 ranks)
Liar's Dice
Leduc (13 ranks)
Battleship
Duality gap
of Gradient computations
Gradient computations
Gradient computations
Gradient computations
BCyeliePDA dilated entropy
ECyclicPDA dilated
MP dilatable glohal entroy
CFR
BCyeliePDA dilatable glohal enimpy
MP dilated entropy
MP dilated
POFK
Figure 25: Duality gap as function of the number of full (or equivalent) gradient computations for ECyclicPDA, MP, CFR PCFR + using a linear averaging scheme for ECyclicPDA and MP.
Goafspiel (4 ranks)
Liar's Diee
Lediee (13 ranks)
Harreship
Duality pap
10
12'
of
n' Gradient computations
Gradient computations
Gradient computations
Gradient computations
HCcliePDA dilated entropy
FCycliePDA dilated
MP dilatable glohal entrogy
CFR*
KCyeliPDA dilatable global
MP dilated entropy
MP dilated
PCHK
Figure 26: Duality gap as function of the number of full (or equivalent) gradient computations for ECyclicPDA, MP, CFR+, PCFR+, using a quadratic averaging scheme for ECyclicPDA and MP.
Goofspicl ranks)
Liar's Dice
Ledas ranks)
Hatteship
Duality gap
10-10
Gradient computations
Gradient computations
Gradient computations
Gradient computations
:ECyclicPDA dilated entropy
#DCyclicPDA dilated i rMP dilated
rMP dilatable global entropy
rCFR
:ECyclicPDA dilarable global entropy
rMP dilated entrapy
IPCFR
Figure 27: Duality gap as a function of the number of full (or equivalent) gradient computations for when restarting is applied to ECyclicPDA, MP, CFR PCFR using uniform averaging scheme for ECyclicPDA and MP. We take the best duality gap seen so far so that the plot monotonic.
Goofspiel (4 ranks)
Linr's Dice
Ledoc (13 ranks)
Battleship
Duality pop
of
Gradient computations
Gradient cemputations
Gradient computations
Gradient computations
:ECyclicPDA dilated catropy
rECycliPDA dilated
X
iMP dilatable global entropy
CCF
:ECyclicPDA dilatable global entropy
IMP dilated entropy
IMP dilated
PCFR
Figure 28: Duality gap as function of the number of full (or equivalent) gradient computations for when restarting is applied to ECyelicPDA, MP, CFR+, PCFR+ using linear averaging scheme for ECyclicPDA and MP. We take the best duality gap far that the plot is monotonic.
28

---

Goofspiel (4 ranks)
Lin''s Dice
Ledie ranks)
Hattleship
Diality gop
10"
33
af Grudient comgutations
Gradient computations
Gradient computations
Gradient computations
:ECyclicPDA dilated entropy
rECycli.PAA dilated
rMP dilatable global entropy
CTR
:ECyclicPDA dilarable global entropy
1MP dilated entropy
rMP dilated
PCCR-
Duality gap as a function of the number of full (or equivalent) gradient computations for when restarting is applied ECyclicPDA, MP, CFR+, PCFR* using quadratic averaging scheme for ECyclicPDA and MP. We take the best duality gap seen so far so that the plot is monotonic.
Figure 29:
Additional wall-clock time experiments Table 3 we show the wall-clock time required to reach duality gap of 10-4, It is clear that algorithm is competitive with MP: MP and its restarted variant time out on Leduc, and MP times out on Battleship (while our algorithm does not even take close to 30 seconds). Furthermore,
outperforming CFR and its restarted variant in Battleship.
Table The wall clock time seconds required ECyclicPDA, MP, CFR+, and PCFR+ and their restarted variants, denoted using "r" at the front of the algorithm name, reach duality gap of 10-4. We let each algorithm rum for at most 30 seconds; a value of 30.000 means the algorithm could not reach the target gap in 30 seconds. The duality gap is computed every 100 iterations.
Name
Goofspiel ranks) Liar's Dice
Leduc (13 ranks)
Battleship
ECyclicPDA
8.797
6.148
9.343
16.818
+FCyclicDDA
6,688
3.519
10.724
4.914
MP
3.183
3,930
30.000
30.000
rMP
2.691
2.360
30.000
8.374
CFR
5.869
0.111
0.236
6.001
ICFR*
5,866
0.057
0.161
6.042
PCPR
0.244
0.067
0.225
0.736
+PCER
0.208
0.077
0.197
0.736
29


Reviews:
[{"review_id": "oQUteZYY8F", "reviewer": "Reviewer_c8Uw", "summary": "The proposed Extrapolated Cyclic Primal-Dual Algorithm (ECyclicPDA) is a solution technique for large-scale extensive-form games (EFG) that resembles first-order coordinate descent. To enable pseudo block-wise updates, it takes use of the recursive nature of the proximal update caused by dilated regularizers. A restarting heuristic for EFG solution is also presented by the authors, and it has the potential to significantly speed up both their cyclic technique as well as other current methods like mirror prox and (predictive) CFR+.", "questions": "1) The authors claim, \"For the first time, a first-order method has surpassed CFR+ in performance on non-trivial EFGs.\" However, it seems that in the paper titled \"Equivalence Analysis between Counterfactual Regret Minimization and Online Mirror Descent\" by Liu et al., the authors also demonstrate instances where first-order OMD methods can outperform CFR+.\n\n2) How strong is the assumption that the strongly convex functions are nice, see page 5, paragraph  \"Dilated Regularizers\"?\n\n3) In the appendix, the last three figures share the same caption. Do these plots refer to linear, quadratic, and uniform averaging?", "limitations": "During the experiments, ECyclicPDA demonstrated superior performance compared to CFR+ solely in the Battleship game. This stands as the only instance where the results were competitive with PCFR+, which still remains the overall best-performing strategy. However, it is not entirely clear from the overall text why ECyclicPDA outperformed CFR+ specifically in the Battleship game.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "In summary, the ECyclicPDA algorithm introduces a novel and effective solution technique for tackling large-scale sequential games, demonstrating superior performance compared to current state-of-the-art techniques in some scenarios. The paper examines prior research on coordinate descent methods and first-order techniques for solving EFGs, highlighting the originality and benefits of their proposed ECyclicPDA approach.", "weaknesses": "The execution times and computational demands of the ECyclicPDA method in comparison to other cutting-edge approaches are not thoroughly analyzed in the paper. It is essential to evaluate such a comparison in order to ascertain the proposed algorithm's applicability and practical effectiveness. Although it is mentioned that the runtime of ECyclicPDA is independent of the number of blocks, a comprehensive evaluation is still lacking. Additionally, the paper overlooks competitive alternatives like DCFR, despite making references to these methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper. We provide responses to your concerns below:\n\n> The execution times [...] comprehensive evaluation is still lacking. \n\nWe address this in our top-level comment (5), the pdf attached to it (containing  numerical evidence that ECyclicPDA scales independently of the number of blocks), and Appendix D. \n\n> Additionally, the paper overlooks competitive alternatives [...]\n\nPredictive CFR$^+$, referred to in our paper as PCFR$^+$, is state-of-the-art among CFR variants for games outside of poker. It is true that specifically in poker-like games, DCFR seems to be better than PCFR$^+$. These conclusions can be found in [14]. We can add DCFR as well if you insist, but it will do worse than regular CFR+ in the non-poker games, and it will not change the takeaways from our experiments and mostly just clutter the plots.\n\n> The authors claim, \"For the first time, a first-order method has surpassed CFR+ in performance on non-trivial EFGs.\" [...]\n\nWhile we were already aware of that paper, we do thank the reviewer for bringing it to our attention. We would like to argue that the algorithms in Liu et al. are not natural instances of first-order methods, or of OMD/FTRL, for several reasons: \n* The algorithms are what Liu et al. call *future-dependent* OMD/FTRL. “Future-dependent” refers to a very particular design of the regularizer: it has the usual FTRL/OMD regularization of the strategy, but also an additional regularization term that depends on the future strategy. This future strategy has to do with the updates being made in the tree below a given decision point, and is explicitly there to make the algorithm look like CFR/CFR+. Yet, the authors do not show that this odd modification of regularization maintains 1-strong-convexity, a prerequisite for applying OMD/FTRL regret bounds.\n* We do not think it is clear that the proofs in Liu et al are correct. Specifically, their proof of convergence of their future-dependent FTRL/OMD algorithms rely directly on convergence results in [a]. Looking at the proof of Theorem 3.5 in Liu et al, they seem to have at least two major issues:\n  * They invoke Lemma 2 and Theorem 3 of [a] to give a regret bound that they start their derivation from (in equation (59)).  But this is not the bound implied by [a], the bounds implied by [a] are given in equations (A.1) and (A.2) in [a], and they involve several additional terms that must be handled. \n  * Liu et al. state that “Assumptions 1,2,3,5, and 8 in [a] have already been fulfilled.” Assumption 8 in [a] is the assumption that the regularizer is 1-strongly convex with respect to some norm. However, the words “strongly convex” or “strong convexity” do not even appear anywhere in Liu et al., and it is not clear that their time-varying sequence of regularizers satisfies 1-strong-convexity. Our best guess is that it does not, since usually with dilated DGFs the weights need to be chosen carefully in order to secure 1-strong-convexity.\n  * The dilated L2 DGF, which Liu et al. use for their equivalence, is not known to be directionally differentiable, as is required by [a]. Specifically, if an action in an internal decision point is set to zero, then it causes problems with the dilation operation for child decision points. It is unclear what this does to their result. This is a general issue with the dilated L2 DGF, and it causes problems when using it in OMD, because it may require taking the gradient at the relative boundary, which is not well-defined.\n\nWe would also like to note that of the three games that overlap between our experiments and theirs, Liar’s Dice, Battleship, and Goofspiel 4 ranks, examining their graphs and ours seems to indicate that we would outperform their algorithms on Battleship and their algorithms would beat us on Goofspiel 4 ranks. We cannot replicate their results for CFR+ for Liar’s Dice (this is evident from the fact that CFR+ reaches a duality gap of $10^{-4}$ before 1000 gradient computations in our experiments, whereas it is not clear if their CFR+ curve reaches an approximate duality gap of $10^{-4}$ even at 4000 gradient computations in their plots). It is not clear why CFR+ would perform so poorly in their experiments.\n\nWe are happy to update our paper to discuss the Liu et al. paper. But we prefer not to do so unless the discussion phase for our paper helps us understand whether the Liu et al. paper is correct.\n\n[a] Joulani, Pooria, András György, and Csaba Szepesvári. \"A modular analysis of adaptive (non-) convex optimization: Optimism, composite objectives, variance reduction, and variational bounds.\" Theoretical Computer Science 808 (2020): 108-138.\n\n> How strong is the assumption that the strongly convex functions are nice [...]\n\nThe assumption that the strongly convex regularizers are nice is not a strong assumption. This is necessary to develop scalable first-order methods (FOMs) for EFG solving, and is considered in existing FOMs in the EFG literature [13,22,24]. There are several regularizers that are known to be “nice” that lend themselves to use in FOMs for EFG solving. These include the dilated $\\ell_2$ regularizer, dilatable global entropy regularizer, and dilated entropy regularizer, which are the three regularizers that we use in our experiments. See [13, 22, 24] which introduce/study these regularizers.\n\n> In the appendix, the last three figures share the same caption [...]\n\nThank you for pointing this typo out. Yes, figs. 27, 28, 29 depict uniform, linear, and quadratic averaging respectively. We will fix this in a revision.\n\n> During the experiments, ECyclicPDA demonstrated superior performance [...]\n\nWe note in our conclusion that we do not know why ECyclicPDA performs better in certain games. Please see the top level comment (6,7) regarding the performance of CFR+. We believe that our introduction of restarting is significant even in the context of PCFR+, given the impressive speedup obtained for some games.\n\n"}, {"review_id": "iMDgMgshHU", "reviewer": "Reviewer_Lrca", "summary": "\nThis paper develops a cyclic block-coordinate-descent-like method for two-player zero-sum extensive-form games (EFG). Such methods for EFG are  difficult due to non-separable nature of block structure of the problem. The decision problem for a player in a EFG can be formulated using Treeplex, for which regularizing functions can be constructed through the framework of dilated regularizers. These dilated regularizing functions allow recursive prox computations. This paper utilizes this frame work to develop an extrapolated cyclic algorithm to perform pseudo-block updates.  They demonstrate O(1/T) convergence rate for two-player zero-sum Nash equilibrium  using this method, and provide a specific algorithmic implementation which shows that runtime of the proposed method  is independent of the number of blocks. \n\nExperimental evaluation on EFG benchmark games is performed using three different dilated regularizers -dilated entropy, dilated global entropy, and dilated $\\ell_2$ with different block construction strategies. Experiments demonstrate the benefit of using blocks over non-block based approach in  some games, and no significant diffference between different block construction methods in others.  The results show improved  performance over the state of the art first order method (Mirror-Prox). Further, they introduce a restarting heuristic which speeds up the proposed method as well as the baselines.", "questions": "-", "limitations": "The authors discuss open question of why restarting work with regularizers  other than $\\ell_2$. The authors adequately addressed the limitations.", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is generally well written, describing necessary background to help readers understand the paper.\n\nThe proposed algorithm seems novel, though I must admit I am not familiar with the literature.\n\nThe experimental evaluation seems convincing, the proposed method outperforms SOTA FOM\n", "weaknesses": "line 105-``As discussed before RCMs are not applicable to our setting''. It is not discussed anywhere in the paper why randomized coordinate methods are not applicable.\n\nThe paper could include a discussion in the related work about [i]  which develops primal-dual coordinate methods for solving bilinear saddle-point problems.\n\n[i] Carmon et al. Coordinate Methods for Matrix Games", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper. We provide responses to your concerns below:\n\n> line 105-``As discussed before RCMs are not applicable to our setting''. It is not discussed anywhere in the paper why randomized coordinate methods are not applicable.\n\nWe address this in our top-level comment (1, 2). In line 53 of our paper, we mention that in EFGs we do not have the separable structure typically required to use coordinate descent methods. If one is to construct blocks of sequences (which correspond to coordinates in the EFG setting), and sample randomly, there is no guarantee that we can take a gradient step and be at a feasible strategy without projecting back onto the entire sequence-form polytope/treeplex (but this would be too computationally expensive since it would cause the number of (equivalent to) total proximal updates to scale linearly with the number of blocks).  This prevents random sampling of blocks, and requires careful construction and cyclic traversal of the blocks, to ensure that we can generate feasible iterates that will converge ergodically to a Nash equilibrium without incurring a dependence on the number of blocks.  We have made the connection between RCMs not being applicable and lack of separable structure more explicit in a revision of our paper.\n\n> The paper could include a discussion in the related work about [i] which develops primal-dual coordinate methods for solving bilinear saddle-point problems\n\nWe appreciate the suggestion and will add this discussion in a revised version of the paper. Briefly: the only setting studied in that paper that is relevant to our work is their $\\ell_1-\\ell_1$ setting. Their assumption in that case is that the feasible set for each of the players is a probability simplex, which is a much simpler feasible set than the treeplex considered in our work. Importantly, it is unclear how to generalize their result to our setting, as it crucially depends on the simplex structure (see, for example, Eqs. (2) and (5) and the discussion of the data structure design on page 7 in the arXiv version of the cited paper).   \n"}, {"review_id": "LplZ1Jxtn6", "reviewer": "Reviewer_u8q2", "summary": "The paper introduces a novel method for solving Extensive-Form Games based on a block-coordinate approach. The authors motivate and explain their idea and experimentally evaluate its performance in terms of primal-dual gap in four different games. The method features a favorable theoretical convergence rate but the empirical results are often comparable or worse than existing methods in terms of the duality gap.", "questions": "- How does the run-time of the tested methods compare in practice?\n\n*** Rebuttal Acknowledgment ***\n\nI have read the author's rebuttal. The answer covers my questions well and the explanation the authors provides logical justification of the potential shortcomings. Therefore, I am of the opinion that the paper is sound and I increased my rating accordingly. I do not go higher due to my very limited familiarity with the subfield.", "limitations": "- The discussion of limitation is not very thorough and it is mostly limited to a mention of a lack of understanding of the game type effect on the performance.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is well written and free of grammar and stylistic issues.\n- The introduction to the problem is very approachable even to domain non-experts.\n- Experimental validation of the block construction strategy choice.\n- Favorable converge properties.", "weaknesses": "- It seems that in empirical studies the method is consistently worse than PCFR+ (Fig 2 and 4). I have a difficulty to find a complete justification for this in the paper.\n- Only a theoretical convergence rate and not an actual computation cost measured in units of time is reported.\n- The plots lack error bars (unless no variance is possible to obtain).\n- The contributions are explained indirectly. They could be listed in a more compact and more explicit form (e.g., a numbered list) to allow for critical assessment.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper. We provide responses to your concerns below:\n\n> It seems that in empirical studies the method is consistently worse than PCFR$^+$ (Fig 2 and 4). I have a difficulty to find a complete justification for this in the paper.\n\nAs we have discussed in our top level comment (6, 7), the practical performance of CFR$^+$ and its variants is not well understood, and not within the scope of our paper. Our primary contribution is theoretical, and it is surprising that a first-order method is able to compete with it. Moreover, as stated in the overall comment, \"PCFR$^+$\"  in Fig 4 is actually restarted PCFR$^+$, a new method introduced by us, and we have made this clear in a revision of our paper (including using \"rPCFR$^+$\"  to denote this adaptive restarting variant that we introduce).\n\n> Only a theoretical convergence rate and not an actual computation cost measured in units of time is reported.\n\nWe discuss this in our top-level comment (5). There is a runtime analysis that demonstrates that our per-iteration complexity is comparable to that of Mirror Prox, and we provide tables reporting results in units of time.\n\n> The plots lack error bars (unless no variance is possible to obtain).\n\nOur method and all methods compared against are deterministic so there are no relevant error bars to report.\n\n> How does the run-time of the tested methods compare in practice?\n\nWe have provided wall-clock comparisons in the top-level comment (5).\n\n> The discussion of limitation is not very thorough and it is mostly limited to a mention of a lack of understanding of the game type effect on the performance.\n\nWe appreciate the suggestion. In a revised version, we will create an explicit limitations section and add discussion of comparisons to CFR$^+$ variants, as well as note that our algorithm performs better on larger games.\n"}, {"review_id": "X20iBWjNtB", "reviewer": "Reviewer_udTT", "summary": "The draft considers solving the extended-form game (EFG) with extrapolated block-coordinate descent methods, proving that it achieves O(1/T) convergence. The authors further show that with a restarting strategy, the proposed algorithm may be comparable sometimes to state-of-the-art algorithms like CFR+. In my understanding, the proposed algorithm is essentially a generalization of the CODER algorithm proposed by Song [37] in a way from coordinate descent (CD) to blockwise CD and specializes the domain to be linear functional and treeplex. I.e., the algorithm is essentially the same (line-by-line corresponded) as CODER but generalizes the scalar coordinate to blocks of \"separable\" variables.  For the specialization, the authors focus on the context of EFG with bilinear score function and 2-player treeplex (linear probability simplex), where the prox is taken on L1-norm instead of the L2-norm by CODER. Implementation-wise, the proposed algorithm uses the recursive structure of the treeplex for efficient linear time computation.", "questions": "1. (Figure 2) Only doing the step-size optimization for your method and not the baseline is tricky for the experiment. For fairness, it should be either all constant step-size or all step-size tuned for the baseline. Otherwise, the reader cannot be sure whether the proposed method is better than MP.\n2. (Figure 4) The vertical drop in the curves looks like either a numerical issue or a wrong optimal value.\n3. (Algorithm 1) Adding parenthesis and denoting what you maintain in the computation may be good for clarity.", "limitations": "Not applicable since the paper does not have a limitation section.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The major contribution of the draft is that it provides an instance to efficiently implement the CODER algorithm on EFG with blockwise L1 proximal and shows that with restarting, such implementation may be comparable with the state-of-the-art algorithm like CFR+. It also analyzes the scenario and provides an O(1/T) convergence rate without dependence on the number of variables. To summarize, the draft shows that a simple CODER extrapolation works well when taking L1 specialization on EFG.", "weaknesses": "However, I would like to claim that the original CODER method may already cover the blockwise updates. I.e., if you look into the proof of CODER, it generally does not use the scalar property of the proximal and treats variables as blocks. They are using the $d$-dimension notation for simplicity and already claiming they are doing block CD in their abstract. In the EFG case, the d=2, so naturally (if the proximal works), the convergence complexity doesn't depend on the number of variables since blocks=2 is a constant. So the draft's theoretical result (independence on the number of variables) is not surprising. And the proposed method does not relax the \"separability assumption\" since the 2-player treeplex is separable as two blocks. The major difference/contribution here is that it performs the analysis on the L1 proximal and does the analysis.\n\nFurther, although it's good to see that the simple method works with restarting, the restarting part doesn't have theoretical support. I.e., without restarting, the theoretically supported method is not comparable to the state-of-the-art. And with restarting, the \"full\" method is comparable but not really much better than CFR+. Thus these factors put the paper in a borderline condition. However, the analysis seems solid, and I would give a borderline acceptance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> However, I would like to claim that the original CODER method may already cover the blockwise updates. [...]  So the draft's theoretical result (independence on the number of variables) is not surprising. And the proposed method does not relax the \"separability assumption\" since the 2-player treeplex is separable as two blocks. The major difference/contribution here is that it performs the analysis on the L1 proximal and does the analysis.\n\nWe would like to clarify a few points here that may have been missed by the reviewer. We will make sure to highlight them more in the revision. \n\nFirst, CODER is not directly applicable to our setting and it is not only because of ell_1 vs ell_2 settings. As discussed in the second paragraph of “Contributions” in the introduction and in the introductory part of Section 3, and in our top-level comment (1), our feasible region (treeplex) is not block separable (except for the trivial primal-dual separation mentioned in the review), hence it violates one of the main assumptions made in CODER. Note that block coordinate algorithms are mainly useful and applied with many small blocks (see, e.g., the block partition strategies described in our experimental section). Even ignoring this point and trying to apply CODER bottom up, there are at least two other issues. First, the extrapolation step in CODER would require exact (non-scaled) values of the blocks of $\\mathbf{x}_k$ and $\\mathbf{y}_k$ that got traversed up to the cycle iteration $t$, which are simply not available without a full tree traversal – these values are only available up to normalizing factors that can get computed only at the end of the bottom-up traversal, in the top-down (rescaling) traversal (Lines 13-16 in Algorithm 1). This fundamentally changes the analysis. Second, we do a block partition on both the primal and the dual side, thus the number of blocks is $2 \\cdot m$ (not $2$, as there are $m$ blocks per player and the number of blocks can be as large as the number of infosets, which can be order-dimension). Even if CODER’s analysis was applicable here, its convergence bound would scale with $\\sqrt{m}$. Our analysis does not incur such a dependence and this comes precisely from a careful interleaving argument carried out in the proof of Theorem 3.2 (please see Lemma C.1 and its proof in the appendix).  \n\n> Further, although it's good to see that the simple method works with restarting, the restarting part doesn't have theoretical support. I.e., without restarting, the theoretically supported method is not comparable to the state-of-the-art. And with restarting, the \"full\" method is comparable but not really much better than CFR+. Thus these factors put the paper in a borderline condition. However, the analysis seems solid, and I would give a borderline acceptance.\n\nAs we have discussed in our top level comment (6, 7), the practical performance of CFR+ and its variants is not well understood, and not within the scope of our paper (also note that the theoretical guarantees for CFR+ and its variants are worse than the guarantees that exist for MP as well as our method). Our primary contribution is theoretical, and it is surprising that a first-order method is able to compete with it. Furthermore, experimentally, it is a contribution of our paper to demonstrate that “restarting” works well even as a heuristic for our method, MP, and the CFR variants. To the best of our knowledge, this has not been discussed in the literature previously. \n\n> (Figure 2) Only doing the step-size optimization for your method and not the baseline is tricky for the experiment. For fairness, it should be either all constant step-size or all step-size tuned for the baseline. Otherwise, the reader cannot be sure whether the proposed method is better than MP.\n\nStep size optimization is done for MP (as noted in lines 293-294) as well as our method.\n> (Figure 4) The vertical drop in the curves looks like either a numerical issue or a wrong optimal value.\n\nThe vertical drop in the curves is not a numerical issue since precision on the order of $10^{-15}$ can be reasonably computed and represented as a double. The algorithms appear to exhibit a linear rate-like convergence when they have that sudden drop-off, which is actually a feature of using the restarting heuristic; this demonstrates that our restarting heuristic works well.\n> (Algorithm 1) Adding parenthesis and denoting what you maintain in the computation may be good for clarity.\n\nAs we mention in the top-level comment (5), we have an algorithmic specific implementation in Appendix D that makes clear what quantities are maintained in the computation. The algorithm presented in the main body is for convenience of presenting the main ideas without a too detailed exposition, and for theoretical analysis.\n\n\n"}, {"review_id": "lzubIJmuAA", "reviewer": "Reviewer_Y4SP", "summary": "This paper introduces ECyclicPDA, a new first order method for solving extensive form games.  The main idea is to implement something in the spirit of coordinate descent where improving directions can be found by considering a part of the current iterate in isolation.  Empirical results show it generally outperforms other first-order methods and approaches the performance of CFR+.  Additionally, a heuristic to restart the process is introduced which improves the performance of both ECyclicPDA and CFR+", "questions": "Please comment on the questions about resetting.", "limitations": "Adequate", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "ECyclicPDA is a nice contribution that takes the growing collection of FOMs for EFGs in a new direction.  The analysis seems to involve non-trivial technical innovations.  The empirical results are convining and show continued progress toward cloasing the gap with CFR-based approaches.\n\nThe restarting heuristic is also very interesting, and the ability to get performance improvements with CFR+ is particularly nice (and intuitive in hindsight).\n", "weaknesses": "As far as I can tell, the details of how restarting is implemented are never clearly explained.  The clearest explanation I can find is in the introduction on lines 88-91, but even taking that as the full specification, I don’t see where the tuning of the parameter about when to restart is specified.  It would also be nice to have a bit of explanation / intuition for how restarting is benefiting various algorithms.  For CFR+ I can see how resetting the regret sums and the averaging process could be beneficial.  For FOMs I’m less clear why it is useful.  Is it purely from resetting the averaging process?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper. We are glad that you found our contributions interesting. We provide responses to your concerns below:\n\n> As far as I can tell, the details of how restarting is implemented are never clearly explained. The clearest explanation I can find is in the introduction on lines 88-91, but even taking that as the full specification, I don’t see where the tuning of the parameter about when to restart is specified. It would also be nice to have a bit of explanation / intuition for how restarting is benefiting various algorithms. For CFR+ I can see how resetting the regret sums and the averaging process could be beneficial. For FOMs I’m less clear why it is useful. Is it purely from resetting the averaging process?\n\nIn our numerical experiments, we are restarting the algorithms every time the duality gap has been halved and initializing the next run at the output (averaged) iterate. We did not explore tuning parameters pertaining to when to restart. We will update this in a revision of our paper to make clear how restarting is implemented in our experiments. For FOMs, we believe that the primary benefit comes from resetting the averaging process, though it is somewhat unclear whether there exists a more intuitive or deeper explanation than this.\n"}, {"review_id": "ib6enKVPYV", "reviewer": "Reviewer_rJqj", "summary": "This paper combines the local prox update technique with the extrapolated cyclic algorithm and proposes the ECyclicPDA algorithm. While the local prox update technique is well understood, the authors reinterpret it as a coordinate method (CM). Then, the method is combined with a new extrapolated method. Theoretical analysis shows that the proposed algorithm can converge at a rate of O(1/T).", "questions": "none", "limitations": "The authors have stated the limitations properly. No potential negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper presents a new understanding of the local update rules of OMD with dilated DGF. The combination of local OMD updates and extrapolated updates is original and interesting.\n2. The theoretical results seem sound.\n3. The paper is well-written.", "weaknesses": "1. It is hard to understand why we want to reinterpret the well-known local update rules of OMD with dilated DGF to CM. As we know, people already compute the strategy in a bottom-up fashion in previous work [1, 2, 3]. So, I think the main contribution is the combination of the local update method and the extrapolated cyclic method.\n2. However, the ECyclicPDA algorithm seems less efficient than the traditional MP algorithm. For every infoset, an extra traversal of the subgame rooted at the infoset is needed to compute the “extrapolated” vector. This could be infeasible for large-scale games.\n3. The experimental results show that the proposed ECyclicPDA performs better than MP. The results are not surprising when considering that ECyclicPDA can be very time-consuming.\n4. The algorithm does not compare with related optimistic OMD [4] algorithms for EFGs.\n\n\n[1] Farina, Gabriele, Christian Kroer, and Tuomas Sandholm. \"Optimistic regret minimization for extensive-form games via dilated distance-generating functions.\" Advances in neural information processing systems 32 (2019).\n[2] Farina, Gabriele, Christian Kroer, and Tuomas Sandholm. \"Better regularization for sequential decision spaces: Fast convergence rates for Nash, correlated, and team equilibria.\" arXiv preprint arXiv:2105.12954 (2021).\n[3] Liu, Weiming, et al. \"Equivalence analysis between counterfactual regret minimization and online mirror descent.\" International Conference on Machine Learning. PMLR, 2022.\n[4] Lee, Chung-Wei, Christian Kroer, and Haipeng Luo. \"Last-iterate convergence in extensive-form games.\" Advances in Neural Information Processing Systems 34 (2021): 14293-14305.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper. We provide responses to your concerns below:\n\n> It is hard to understand why we want to reinterpret the well-known local update rules of OMD with dilated DGF to CM. As we know, people already compute the strategy in a bottom-up fashion in previous work [1, 2, 3]. So, I think the main contribution is the combination of the local update method and the extrapolated cyclic method.\n\nWe mention in our paper and in the top-level comment (3), that the recursive computation of the prox update when using dilated regularizers in EFGs is well-known. The main contribution of *our* paper is different though (as mentioned in top-level comment (4)): what we are showing is that the ``local update’’ structure of dilated DGFs enables us to perform extrapolated cyclic block-coordinate updates. This is completely new, and different from the purpose of the local updates in prior works. In prior works the local updates were merely a way to efficiently implement deterministic full-gradient updates. \n\n> However, the ECyclicPDA algorithm seems less efficient than the traditional MP algorithm. For every infoset, an extra traversal of the subgame rooted at the infoset is needed to compute the “extrapolated” vector. This could be infeasible for large-scale games\n\nWe have discussed this issue in the top level comment (5) and there is an analysis of the per-iteration complexity provided in Appendix D, where we note that the per-iteration complexity is comparable to that of MP. The scaled values used for extrapolation can be computed while we are traversing the treeplex to do the partial prox update; note that because of the recursive nature of the prox update (as discussed in the top level comment (3,5)), this does not require any extra traversal through the treeplex as compared to a full-gradient method and thus neither does the computation of the “extrapolated vector”. We will make this more explicit in the main body in a revised version of the paper.\n\n> The experimental results show that the proposed ECyclicPDA performs better than MP. The results are not surprising when considering that ECyclicPDA can be very time-consuming.\n\nWe have discussed this in our top level comment (5), and the attached pdf contains data on the runtime of our algorithm and the other algorithms we compare against. ECyclicPDA does not take more time than MP (in fact, it usually takes *less* time per outer iteration) and performs about half as many arithmetic operations per outer iteration (note that one outer iteration for ECyclicPDA corresponds to a full gradient update, and is thus is comparable to one iteration of MP).\n\n> The algorithm does not compare with related optimistic OMD [4] algorithms for EFGs.\n\nWe will add this in a revised version of the paper; we were not able to obtain results for this in time for the rebuttal. We suspect that the performance will be comparable to MP, perhaps very slightly better, based on prior work.\n"}, {"review_id": "W4zRlqRmYU", "reviewer": "Reviewer_XCKi", "summary": "This work proposes a cyclic coordinate descent method to solve the two-player zero-sum extended form game (EFG) and derives the convergence.", "questions": "no", "limitations": "I do not see any potential negative societal impact.", "rating": 5, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "To me, solving problems with non-separable constraints by coordinate-descent-type methods is novel and interesting. Therefore, I believe that this is indeed a contribution.", "weaknesses": "I'm not familiar with this area so please forgave me if I made some mistakes.\n\n1. Possibly expensive computational cost per iteration. Following the literature survey in the manuscript, I read reference [1] which studies coordinate descent for solving optimization problems with non-separable non-smooth objective functions. I found that in both the algorithm in [1] and the algorithm in this paper, although only partial gradient is needed at each update, the proximal step with respect to the whole nonsmooth function is needed. More specifically, in Lines 8 and 11, the argmin step might be difficult and computationally expensive since the argmin step is over the whole X and Y and involve all the blocks.\n\n2.  This concern follows the first one but focuses on the experiments: the comparison with non-coordinate algorithms may be unfair. The current comparison is in terms of the number of full gradient computations. However, gradient computation is not the only computation cost, Lines 8 and 11 also cause computation costs. I would suggest a comparison in terms of wall clock time.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper. We provide responses to your concerns below:\n\n> Possibly expensive computational cost per iteration. Following the literature survey in the manuscript, I read reference [1] which studies coordinate descent for solving optimization problems with non-separable non-smooth objective functions. I found that in both the algorithm in [1] and the algorithm in this paper, although only partial gradient is needed at each update, the proximal step with respect to the whole nonsmooth function is needed. More specifically, in Lines 8 and 11, the argmin step might be difficult and computationally expensive since the argmin step is over the whole X and Y and involve all the blocks.\n\nWe have addressed this in the top-level comment (5). While the argmin in Lines 8 and 11 of Algorithm 1 might make it seem like we are doing a proximal update with respect to the entire feasible set, in fact, we can do this computation without having to consider the entire feasible set (and this is the primary premise of our paper). Please also see the implementation version of the algorithm in Appendix D that makes this more transparent.\n\nAs mentioned in the top-level comment (1-4), the primary contribution of our paper is to provide a coordinate-descent-like method which circumvents the issue of non-separability without having to compute a proximal update with respect to the entire feasible set every time a partial gradient is taken with respect to a block. We do this by combining the recursive prox update structure that dilated regularizers are known  to have (Proposition 2.2) with an extrapolated cyclic method.  We have an implementation-specific algorithm in Appendix D which demonstrates that the computation done for gradient updates and prox updates (which are the computational bottleneck when applying first-order methods to EFGs) for our method is comparable to the respective computations done for MP. In fact, after performing one whole iteration of the outer loop (line 2 in Alg 1), we will have spent almost exactly the same amount of time as a single prox computation + gradient computation when running Mirror Prox. However, we agree that the body could have more clearly explained this, and we will update the paper to reflect this.\n\n> This concern follows the first one but focuses on the experiments: the comparison with non-coordinate algorithms may be unfair. The current comparison is in terms of the number of full gradient computations. However, gradient computation is not the only computation cost, Lines 8 and 11 also cause computation costs. I would suggest a comparison in terms of wall clock time.\n\nWe have addressed this in the top-level comment (5) and also earlier in our response. We demonstrate in Appendix D that Lines 8 and 11 (the prox updates for each of the players) require comparable computation to the prox updates done in MP. We will make this more explicit in the main body (as we note in the top-level comment). Note that the wall-clock times of our algorithm are comparable to MP per “full” gradient computation (as shown in Tables 1 and 2 in the attached pdf).\n"}]

Author rebuttal:
We would like to thank all of the reviewers for taking the time to provide valuable feedback for our paper. Here we provide clarifications for a couple of points raised by multiple reviews. Please note that we have attached a PDF containing tables that we refer to in the rebuttal.

### Theoretical contributions:

(1) The feasible region considered by our problem is non-separable. The feasible region for our problem consists of the strategy space for each of the two players. Players’ strategies are represented using sequences, and the space of these sequences can be formulated as a treeplex, which is essentially a Cartesian product of scaled treeplexes, the base case being that the treeplex is a simplex. (2) If we were to apply a randomized block coordinate method, we would not be able to update one (or a constant number of) those simplices, as (unless we are at a leaf) this would violate feasibility for the entire subtree rooted at the simplex we update. (3) We get around this issue by having a deterministic method that traverses the treeplex bottom-to-top, updating *scaled* values of the coordinates (scaled by the value of the parent node, so each update is on a probability simplex). We can do this thanks to decomposability of the prox update ([12, 22] and stated as Proposition 2.2 in our paper), because we are moving bottom to top, and because another top to bottom traversal fixes the scaling. (4) On a theoretical front, it is surprising that the result we get for such a deterministic, cyclic block coordinate method is independent of the number of blocks (which can be order-dimension) and, to our knowledge, is the first result of this kind for cyclic block coordinate methods. It is also the first block coordinate method whatsoever for EFGs. This would be interesting even if no practical improvements were shown in our experiments. 

### Per-iteration complexity of ECyclicPDA: 

(5) We consistently beat MP, both in terms of oracle queries and in terms of wall-clock time (attached pdf). We compare to MP because it is a full vector update from the same class of (first-order) methods. We expect similar results for OMD and will include added comparison in a revised version. Several reviewers brought up the per-iteration complexity of our method, with an incorrect understanding that it is more expensive than e.g., the per-iteration cost of MP. The per-iteration complexity of our method is discussed in Appendix D (as is stated in Section 3). In Appendix D, we provide an implementation specific version of our algorithm and a computational complexity analysis of it. We demonstrate that the necessary computations for our method are comparable to those necessary for a full gradient method (i.e., MP). In particular, when first-order methods are applied to solving EFGs, the computational bottleneck are the gradient and proximal update computations (this is noted in lines 38 and 39 in our paper). We will update our paper to emphasize in the main body that the per-iteration complexity is comparable to MP.

In Table 1, we provide a table demonstrating the per-iteration runtime in milliseconds of our algorithm (for each of the different block construction strategies we consider) as well as the algorithms we compare against. It is clear from this table that the runtimes are pretty similar to each other, and this is without extensive optimization of our particular implementation. Clearly, our algorithm is at least as fast as MP per “full” gradient computation. Since the computational bottleneck of gradient and prox computations becomes apparent in bigger games, Battleship demonstrates the speed of our algorithm relative to MP best.

In Table 2, we provide a table demonstrating the wall clock time in seconds of our algorithm to reach a duality gap of $10^{-4}$ (with a timeout of 30 seconds).  It is clear that our algorithm is competitive with MP: MP and its restarted variant time out on Leduc, and MP times out on Battleship (while our algorithm does not even take close to 30 seconds).  Furthermore, we are outperforming CFR+ and its restarted variant in Battleship. 

### Restarting as heuristic and comparison to CFR+:

(6) The adaptive restarting heuristic for all methods considered is a contribution of our work since restarting has not been applied to EFG solving previously. We will update the paper to emphasize this by using “r” as a prefix on all algorithms when the restarting heuristic is applied. (7) We would like to note that CFR+ and its variants have a slower convergence rate in the worst case and their good practical performance is still not well understood [11, 12, 23, 24, a]; the strong practical performance of CFR+ and variations is a long-standing open problem in the field and explaining this strong practical performance is outside the scope of the paper. Furthermore, there is recent work [b] which provides evidence that there exist games where the worst-case convergence rates are realized. Nonetheless, we reiterate that our paper is the first paper to *ever* give a first-order method that outperforms CFR+ on EFGs beyond Kuhn poker (which is almost a normal-form game). Secondly, we would like to emphasize that in Fig. 2, the “PCFR+” algorithm is a *new* algorithm, as it is restarted, and restarted PCFR+ had never been considered before; as stated above, we will update the plots to say “rPCFR+” in order to emphasize that it is different from regular PCFR+ (and will update the other restarted versions of other algorithms similarly). Finally, we view our most important contribution as being theoretical in showing the possibility of block-coordinate approaches, as explained above.

[a] Neil Burch. Time and Space: Why Imperfect Information Games are Hard. PhD thesis, University of Alberta, 2017.

[b] Gabriele Farina, Julien Grand-Clément, Christian Kroer, Chung-Wei Lee, and Haipeng Luo. Regret Matching+: (In)Stability and Fast Convergence in Games. arXiv preprint arXiv: 2305.14709, 2023.


Meta-review: We had an especially hard time trying to get reviewers for this paper. Reading the reviews and responses to the reviewers, the contributions to cyclic coordinate descent methods for EFG when the space of strategies for the players is non-separable warrant acceptance.
Decision: Accept (poster)