On the Optimality of Dilated Entropy and Lower Bounds for Online Learning in Extensive-Form Games
Authors: Zhiyuan Fan
Christian Kroer
Gabriele Farina
Venue: NeurIPS 2024 poster (2024)
Keywords: extensive-form games
first order methods
dilated entropy
equilibrium computation
Primary area: online_learning

Abstract: First-order methods (FOMs) are arguably the most scalable algorithms for equilibrium computation in large extensive-form games. To operationalize these methods, a distance-generating function, acting as a regularizer for the strategy space, must be chosen. 
The ratio between the strong convexity modulus and the diameter of the regularizer is a key parameter in the analysis of FOMs.
A natural question is then: what is the optimal distance-generating function for extensive-form decision spaces? In this paper, we make a number of contributions, ultimately establishing that the weight-one dilated entropy (DilEnt) distance-generating function is optimal up to logarithmic factors. 
The DilEnt regularizer is notable due to its iterate-equivalence with Kernelized OMWU (KOMWU)---the algorithm with state-of-the-art dependence on the game tree size in extensive-form games---when used in conjunction with the online mirror descent (OMD) algorithm. However, the standard analysis for OMD is unable to establish such a result; the only current analysis is by appealing to the iterate equivalence to KOMWU. 
We close this gap by introducing a pair of primal-dual treeplex norms, which we contend form the natural analytic viewpoint for studying the strong convexity of DilEnt. 
Using these norm pairs, we recover the diameter-to-strong-convexity ratio that predicts the same performance as KOMWU. Along with a new regret lower bound for online learning in sequence-form strategy spaces, we show that this ratio is nearly optimal.
Finally, we showcase our analytic techniques by refining the analysis of Clairvoyant OMD when paired with DilEnt, establishing an $\mathcal{O}(n \log |\mathcal{V}| \log T/T)$ approximation rate to coarse correlated equilibrium in $n$-player games, where $|\mathcal{V}|$ is the number of reduced normal-form strategies of the players, establishing the new state of the art.

On the Optimality of Dilated Entropy and Lower Bounds for Online Learning in Extensive-Form Games
Zhiyuan Fan
Christian Kroer
MIT
Columbia University
fanzyCmit. edu
christian www.krorrorombbaaccoooo edu
Gabriele Farina MIT gfarinaCmit.co edu
Abstract
First-order methods (FOMs) are arguably the most scalable algorithms for equilib- rium computation in large extensive-form games. To operationalize these methods, distance-generating function, acting regularizer for the strategy space, must be chosen. The ratio between the strong convexity modulus and the diameter of the regularizer is key parameter the analysis of FOMs. A natural question then: what is the optimal eestance-generttngg function for extensive- form decision spaces? In this paper, we make a number of contributions, ultimately establish- ing that the weight-one dilated entropy (DilEnt) sestance-generaaiog function is optimal up to logarithmic factors. The Dillnt regularizer notable due its iterate-qquivalence with Kernelized OMWU (KOMWU) the algorithm with state- of-the-art dependence on the game tree size in extensive-form games-when used in conjunction with the online mirror descent (OMD) algorithm. However, the standard analysis for OMD is unable to establish such a result; the only current analysis is by appealing to the iterate equivalence to KOMWU. We close this gap by introducing a pair of primal- treeplex norms, which we contend form the natural analytic viewpoint for studying the strong convexity of DilEnt. Using these ratio that predicts the same regret lower bound for online learning
norm pairs, we recover the diameter-to-see ceo--strong-conveee performance as KOMWU. Along with in sequence-form strategy spaces, we show that this ratio is nearly optimal. Finally, we showcase our analytic techniques by refining the analysis of Clairvoyant OMD when paired with DilEnt, establishing an (n log [V] log T/T) approximation rate coarse correlated equilibrium in n-player games, where |V] is the number of reduced normal-form strategies of the players, establishing the new state of the art.
Introduction
Extensive-form games (EFG) are a popular framework for modeling sequential games with imperfect information. The framework has been widely used build superhuman Al agents in real-world imperfect information games [5, 31, 6, 8]. Several notions equilibrium, including Nash equilibrium [32] in two-player zero-sum and coarse correlated equilibrium in general multiplayer EFGs, can be computed in polynomial time in the size of the game tree under the standard hypothesis of perfect recall [41, 35, 23, 24]. These polynomial-time algorithms, however, require running the ellipsoid method or polynomial algorithm for linear programming, both of which are impractical for large-scale games, due to the high memory usage and large per-iteration computational costs [38].
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Instead, fast iterative methods based on convex first-order optimization methods (FOMs) [43, 12, 40, 15, 27, 16, 28-30] are commonly used to find an approximate equilibrium. These iterative methods define strategy update rules that each player can apply iteratively while training in self-play with other players, and that guarantee ergodic convergence to the set of equilibria the long run. Three popular classes of such FOMs are employed in EFGs: methods based on online mirror descent (OMD) [4, 12], methods based on the counterfactual regret minimization framework [43], and (in the context of two-player zero-sum games specifically) accelerated offline methods such as mirror prox [33] and the excessive gap technique [34] algorithm. In general, these methods are all proximal methods that is, they perform generalized notion of projected gradient descent step at each iteration. Some do this explicitly, including OMD and mirror prox, while others do it implicitly, including the counterfactual regret minimization algorithm, which runs proximal steps locally at each decision point [17].
In all methods mentioned above, except CFR, the constraint set for the proximal step (i.e., the set on which gradient steps must be projected onto) is the strategy polytope of the EFG. The proximal steps are parameterized by a choice of senttaacegeeeratingg function (DGF) for the strategy polytope, which acts regularizer. The performance of FOMs is sensitive to the properties of the DGF. In particular, two qualities are often desired: (1) the ratio between the diameter of the feasible domain (as measured with the DGF) and the strong convexity modulus, with respect to given norm, of the DGF must be as small as possible; and (2) projections with respect to the DGF onto the feasible set should take linear time in the dimension of the set.
In EFGs, the only DGF family that satisfies the second requirement is based on the framework of dilated regularization introduced by Hoda et al. [22]. Within this framework, Kroer et al. [27] gave the first explicit strong convexity bounds based on the dilation framework, specifically for the dilated entropy DGF. By combining optimistic regret minimizers for general convex sets with this DGF, one gets an algorithm that achieves a - EFGs. Subsequent work by Farina et al. [16] introduced the dilated global entropy DGF with an improved wwwpeeteeet-ssttoncoooneeeeeeeee
convergence rate for two-player zero-sum
ratio. By plugging their DGF results into the genereic OMD regret bound, one immediately achieves a regret bound of O[ @11 Vlog [AVT)). This was the tfate-of-theant art regret bound when introduced, in terms of dependence on game constants. Moreover, until now, it was the best bound known to be achievable through the direct application of OMD regret bounds combined with DGF results. However, Farina et al. [20] developed a, seemingly, different approach based on kernelization, which is a way to simulate, in linear time in the EFG size, the results of applying optimistic multiplicative weights (OMWU) on the normal- reduction of an EFG. They call their algorithm KOMWU. KOMWU achieves a better, and now ofate-of-the-art, regret bound (V log (VVTT) in online learning with full-information feedback. Based on their result, two open questions emerged: 1) is this the best possible regret bound that one can achieve? 2) is possible to achieve such a bound directly using the standard OMD machinery, without resorting to this kemelization trick? Bai et al. [2] made highly interesting progress on the second question: they show that, in fact, the KOMWU algorithm is iterate equivalent to OMD, with the specific version of dilated entropy that uses weight one everywhere. However, their result only shows state-of-the-a rate by equivalence to KOMWU, and it is still unknown whether this state-of -ftt rate is achieveable directly through results on DGF properties and the standard OMD regret bound. In this paper, we answer these two open questions, by answering the following question:
What is the optimal DGF for FOMs in solving EFGs?
We show that weight-one dilated entropy (DilEnt) is indeed the optimal DGF for FOMs in solving EFGs with full-information feedback, terms of the diameter-to-strong- too-stronn-coovxiity ratio (DI/p), up to logarithmic factors. We note that the diameter-to-strre pro-strong-con conoontty ratio of the regularizer is key factor in the performance of FOMs. Intuitively, performance degrades as the diameter increases (since there is more "space" to search), and improves as the regularizer becomes more bowl-shaped (i.e., strongly convex). Consequently, a smaller diameter-to-strone www.tttonn-oooeeeeeeeee ratio leads to better performance of the corresponding FOM. Our contributions can be summarized as follows:
We introduce a pair of primal-dual treeplex norms for the extensive-form decision space. These norms establish an improved framework for analyzing FOMs in EFGs, leading to results with better dependence on the size of the game. Based on this framework, we derive a new state-of-the-art
In CFR, the gradient steps are projected onto the nonnegative cone locally at each decision point of the game, and then renormalized to be valid probability distribution over the actions.

---

Regularizer
Norm pair
[D//u ratio
Max gradient norm
Dilated Entropy [27]
{ and fo norms
(22 log (.Al)
1 1
Dilated GI. Entropy [16]
{ and fo norms
011 log (AA))
S 1
DilEnt (this paper)
treeplex norms
In |
Table I: Comparison of the Mlameter-to-strong--oomee
(PP)/)) ratio with prior results in DGFs for EFGs, where the "Norm pair" indicates the primal norm used in establishing the strong convexity, and its dual. "Max gradient norm" indicates the maximum norm-measured in the dual of the norm with respect to which each DGF is strongly convex- of any reward vector, or the gradient of utility function, that can be encountered during optimization, assuming that all payoff's at the terminal nodes of the EFG are in the range [0, 1]. D denotes the depth of the tree, || 2 the tree size (see Section 3), [A]] the maximum number of actions, and |D] the number of reduced normal-form strategies. We remark that In [V] & (11 log (Al)).
diameter-to thumeter-to-strong-eee -o--t--ttoo-oooveeitii ratio among all known DGFs for the EFG strategy spaces (see Table I for comparison). By combining this new results with the standard OMD) regret bound, we establish a regret upper bound that aligns with the results achieved by KOMWU.
By establishing a matching regret lower bound, we identify a minimum diameter-to-strong. convexity ratio for any regularizer. We find that the DilEnt regularizer achieves the optimal ratio up to logarithmic factors, making it a natural candidate for FOMs on EFGs.
An advantage of our new results, as compared to showing regret bound through the KOMWU equivalence, is that our DGF result can also be combined with other algorithmic setups. As an example of our results, we show that by equipping Clairvoyant OMD [19] with the DilEnt DGF, we enable convergence to a coarse correlated equilibrium at rate of O h log |V T/T) in n-player EFGs. This improves upon the previous results of On log | log* T/T) by Farina et al. [20] and (n [J x All Q1?? log T/ T/T) by Farina et al. [18], establishing a new state-of-the-ar rate.
2 Related Works
Equilibrium Computation in General-Sum Extensive-Form Games The first line work in the equilibrium computation on general-sum EFGs used linear program (LP) which can be solved efficiently [35, 24]. However, due to the large exponent of LP solvers, it is impractical to run such algorithms on large-scale games. The modern equilibrium computation using fast-iterative methods: Syrgkanis et al. [39] introduced the RVU property the regret bound for broad class of optimistic no-regret learning algorithms. With that property, they demonstrated that the individual regret of cach player grows as T1/4 in general games, thus leading to a 7-3/4 converge rate to the coarse correlated equilibrium (CCE). near cear-optimal bound of order log" (T) was established by Daskalakis al. [13], which implies a fast convergence rate of order ((LTT). Subsequent work by Farina et al. [20] generalized the result to class of polyhedral games that includes EFG. Concurrently, Piliouras et al. [36] introduced the Clairvoyant MWÚ. Although the algorithm is not non-regret learning, a subset of the steps converge to CCE with rate of log T/T. Farina et al. [19] showed that the algorithm is an instantiation of the conceptual proximal methods, which has been studied in the literature of FOMs [10, 33]. Using another technique, Farina al. [18] also achieved this rate with worse game size dependence. Another class of fast iterative methods follows from counterfactual regret minimization (CFR) [43], which guarantees a regret bound of order VT. Farina et al. [14] showed that running OMWU at each decision point achieves a 1/4 external regret, thus leading to 3 approximation rate to the CCE. Although CFR has weaker guarantee convergence rate, variants of the algorithm are widely used in practice due to their superior practical performance [26].
Regret Lower Bounds in Extensive-Form Games Several works have studied lower bounds in EFGs across various settings. Koolen et al. [25] established a lower bound dependent on the number of orthogonal strategy profiles in the decision set for structured games, including EFGs, resulting in a bound of ((v Tlog [A). Syrgkanis et [39] demonstrated that two-player zero-sum games, if one player uses MWU while the other best responds, the former must endure regret of at least
3

---

((VT). Similarly, Chen and Peng [11] gave the same lower bound when both players use MWU. For equilibrium computation, Anagnostides et al. [1] analyzed the sparse-CCE in EFGs, showing that under certain assumptions, no polynomial-time algorithm can learn an &-CCE with less than
21og) (7] oracle accesses to the game for even constantly large E > O, where [7] is the number of nodes of the EFG. In the context of stochastic bandit, Bai et al. [3], Fiegel et al. [21] investigated online learning in EFGs with bandit feedback, establishing matched lower and upper bounds.
3 Preliminaries
General Notation We use lowercase boldface letters, such x, to denote vectors. Let x Ô represent the element- product of two vectors, and x the element-wis wise absolute value. For an index set C, denote by x(C] E I the entries of x at indices in C. and by [C] the set cardinality. Let
[A]]] be the set {1, 2, ....................... k} and Ø the empty set. Denote the simplex over the set by A The logarithm of to base 2 is denoted as log z. For non-negative sequences (an) and {bx) an S (b,,) or bn 2 (a,,) indicates the existence
global constant > such that an S Cbb, for all n 0.
Extensive-Form Games An extensive-form game (EFG) is an n--layer game with sequential structure that can be represented using a tree. A detailed definition of EFG is available in Appendix A. Each node represents a game state where an agent (a. player) E [[]] or the environment takes action. We use superscript (i) to denote properties of player i, but also omitting the superscript when context allows. Internal nodes branch into feasible actions. At these nodes, the designated player selects an action, ad advancing the game to the subsequent state according to the tree. The game concludes at a terminal node & E Z, where players receive a reward u[z]. The goal of each player is to maximize their expected reward. We assume the reward for each player is bounded by follows:
Assumption 3.1. The reward received by player at any terminal node Z satisfies u ( E [o, 1].
Tree-Form Sequential Decision Process In EFG, individual player i's decision problem can be modeled by a tree-form sequential decision process (TFSDP). Let J denote the set of decision points, where each point j E I corresponds to an information set in the EFG. At each decision point, the player is provided with a set of available actions Aj and must select an action a E Aj. After an action is taken at decision point j. the game either concludes before the player acts again or continues to set of possible next decision points determined by actions of other players or by stochastic events. We denote the set of potential subsequent decision points as Cja S J, which are reached immediately after action at decision point j. The tree structure guarantees non-overlapping successors, meaning Cja n Cy'a'
for any distinct pairs ja and j'a', where j # j' or a o a'. This encapsulation of all past actions and outcomes at each decision point is known as perfect recall.
The point-action pair ja, where action is taken at decision point j. is referred to an observation point. This leads to a new state influenced by other agents and the environment. We denote the set of all point-action pairs Σ = {ja j E J, a E A; ). Each decision point E J has parent Pj. the last observation point on the path from the root of the decision process to j. If no action precedes j. Pj defaults to the special observation point Ø. We define Σ : Σ {ē) as the set of observation points, each also called a sequence. The total set of points in the TFSDP, H := J U U., includes both decision points and sequences. We use h E H. for unspecified point types. The TFSDP concludes at terminal observation points & = (or E Σ : C. = Ø}, where reward r r|a] is observed. Under Assumption 3.1, it holds that r/o] E 10.
Strategies and Transition Kernels A strategy profile for player in a TFSDP is an assignment of probability distributions over actions A, at each decision point j E J. As customary when using convex optimization techniques in EFGs, we represent strategies in the sequence-form representation [41]. This representation stores player's strategy as a vector whose entries represent the probability of all of the player's actions on the path from the root to the points. Since products of probabilities on paths are stored directly as variables, expected utilities are multilinear in the requence-form representation of the players' strategies. For symmetry reasons which will become apparent later, we slightly depart from the typical definition of the sequence form, by storing the product of player's action probabilities on paths from the root to all points in the not only those that belong to the player. We call this representation the extended sequence-form representation. For extended

---

sequence form strategy to be valid, probability conservation constraints must be satisfied at every point of the tree. Specifically, the set of all valid extended sequence-form strategies is given by
x|Ø]
x(o| x(j]
Va E
2 = (0, 1|a:
x(j] = Σ x(ja]
Ej E J
aeA;
The distribution of observation outcomes at each observation point, or the transition kernel, is determined by the strategy played by other agents as well as the environment. It can viewed as an opponent who only acts at the observation points. This allows us to encode the transition kernel using vector y E [0, 1 similar to the sequence-form strategy. The entry corresponding to each point h & H represents the product of transition probabilities on the path from the root to the point. Formally, the transition kernel space is given by
y|ø| =1
== y E
[0, 11 ylo| = Σ viil
Yo VO
JEC.
vlj y[ja]
We parameterize the vector spaces primarily over the terminals, since the reach of internal points can be uniquely determined by terminal reaches. We define the compressed extensive-form decision space Q = [x[E] x E ② and the compressed transition kernel y := {y[E] y E 5}. representing the projection of the corresponding spaces onto the vector space generated by terminal observation points. The existing of one-to-one mapping guarantees that Q and y are homogeneous Q and 5. For each non-terminal point E H &, we denote by [h] the value of x [[h] in Q corresponding to Q while the transition kernel aligns with y E Y, the reach probability terminal point a E E is given by x|o]y[o]. The expected reward of the player can be computed from u(x; w) (x, w), where == r is the reward vector, or the gradient utility.
the compressed strategy profile x. When the agent adopts strategy profile
To assess the complexity of the game, we use several complexity measures for the extensive- decision space. We define the tree size and leaf count, denoted as Q111 and || as the maximum number of observation points and terminal observation points that can be reached among all pure strategy profiles, respectively. Formally, we write
|| 1|] == sup [x|I||1= sup Σ x(a]) x
||||| == sup ||x||1 sup Σ x(o)) XE
xE FEE
xe@
OEE
where we implicitly extend the domain of x to when writing x[=). We further define V = on (0, 1) as the vertices in the extensive-form decision space. Each vertex refers to pure strategy profile of the player, which reduced to a norm-form strategy. The number of reduced normal-form strategy is given by [ We remark that both || and [V] have been used in the literature [e.g.. 20].
As we will often incorporate the recursive structure TFSDP, we define a subtree as the subgame starting from some internal point h H. For two points h, h H. write h >= h if h' is reachable from h in TFSDP. Let H,, = {h' E H. : h ž h} and E, = {o E a 2 h} be the sets of points and terminals reachable from h. We denote by Qn and V/ the projected spaces of Q and y over (0. 1J with restrictions x x(h] = and y [4] 1, respectively. Formally, for any point E H. define the compressed projected decision space Q, {x(E,] x Q x [h] 1}. From the definition of the compressed extensive-forn decision space, this space can be seen as projection of
Subtree
x(h] = 1
x(i] x(o]
Wo YEEE E.j C
2 = x E
00,
x(j] Σ x[ja] aEA,
VjEJ
Similarly, we define the compressed projected transition kernel space as yn, [E( y y = 1). important to note that this space exhibits similar closed form that of the compressed extensive-for decision space.
5

---

Proximal Methods We review the standard objects and notations that relate to proximal methods. For a given decision set 2. the proximal method requires distance generating function (DGF) p Q + R defined on the decision set. The algorithm is valid when the DGF is j-strongly convex with respect to some norm ||-I|- The DGF induces a generalized notion of distance D + Q Rgo. referred to as the Bregman Divergence, which is defined by
D == -=:0==p(80 (x) pxx) - x
We define the proximal operator with respect to the feasible space Q and the DGF p. Given a pivot point x and gradient vector g IR the proximal operator 11 (g, x) generalizes the notion of gradient ascent step, and is defined as
pg x) == argmax (g. x) D (x]])) R
For the extensive-form decision space Q, the DGF is usually restricted to the dilated DGF [22] so that the proximal operator can be efficiently computed. Moreover, is well known that the proximal operator is Lipschitz continuous: [e.g. 33, Lemma 2.1]
Lemma 3.2. For any g, g' E R it satisfies that [g. (gp x)]l S n u g'll..
4 Primal-Dual Treeplex Norms
We first introduce the treeplex & norm || I1x,,1 and the treeplex fox norm |2x,00. which are primal-dual norm pair defined over the vector space RR, with respect to a given TFSDP with the point set H. As we will show later, these norms enable better framework for analyzing FOMs in EFGs. Specifically, in the analysis of OMD, we use the fact that the foo norm for any feasible reward vector w satisfies ||w]| S Although treeplex foo norm is relaxation of the Eo norm, can still preserve the same guarantee such that || H, I 1. With the relaxation, we have that the treeplex l norm generates smaller distance compared to the & norm, which allows us to provide better strong convexity modulus for the regularizer, finally improving the induced regret upper bound.
Both treeplex norms defined as the support functions with respect to the vector of element-wise absolute values. Specifically, the support function of treeplex l norm is defined using the transition kernel space V, while the support function of treeplex lo norm is defined using the extensive-form decision space Q. Formally, for some vector E RR we denote
|u H.1 == sup (1 (lul,y) = sup yEy 0EE
|uj]]
y(a],
yey
11,0 == sup |||||
( (/u|,x) x) = sup Σ
|ulo]| x(o].
x
X
AEE
We remark that the treeplex loo norm has been used by Zhang et al. [42] for analyzing low-degree swap regret minimization. When the EFG degenerates an NFG (normal-form game), i.e. |J] the extensive-form decision space Q in the TFSDP becomes a simplex A and the transition kernel [1] only contains the all-one vector. It follows that the treeplex & norm || ll and the treeplex fo norm || ||, degenerate to the conventional f norm and loo norm for the vector space, respectively. The following lemma verifies that both treeplex E norm and treeplex tx norm are norms in the technical sense. The missing proofs in this section are provided in Appendix C.
Lemma 4.1. The functions
I|x, and || |lx, are norms defined the space R
Thanks to the recursive structure of TFSDP, the maximization among Y Q in the treeplex norms can be decomposed at each point h E H. This decomposition allows us to compute both treeplex norms in recursive manner.
Lemma 4.2. Let E be a vector with respect to some point h E H. The treeplex é norm and the treeplex fo norm of vector u over HA can be computed recursively as follows.
If h = E E is terminal observation point, then:
| Ho.1 = |uja]].
||u||,,,,o == |u[a]]

---

If j J is decision point, then:
u = EaEA, | ||u|| = maxaed, || m[Eejallngn.o
If = O E/ is non-terminal observation point, them:
1 | Hty. == max.EA, ||] || == EaEd, |
Equipped with the recursive formula, we are able to show that the two treeplex norms with respect to the same TFSDP are pair of primal-dual norms.
Theorem 4.3. We have | and || |1 a pair of primal-dual norms for given TFSDP with point set H. Specifically, for any vector E R
u,, v)
||ul
sup VERS
||
V |
Furthermore, the recursive formula also enables us to bound the treeplex norms for specific vectors.
Lemma 4.4. We have ||x||H,1 = for any strategy profile x E 2, | = for any transition kernel y VM and || [ for any feasible reward vector under Assumption 3.1.
5 Metric Properties of the DilEnt Regularizer and Improved Regret Bounds
In this section, we study the strong convexity modulus of the weight-one dilated entropy (DilEnt) function with respect to the treeplex norms defined above. The DilEnt regularizer is an instantiation of the more general dilated DGFs framework [22]. Specifically, a dilated DGF for an extensive-fore decision space is constructed by taking weighted sum over suitable local regularizers, yo for each j E J, and is of the form
وgpo (x(ja))aa))) JEJ
Σ
where
(0
if x = otherwisc
of (x(py)) (x[ja]xaaaaaa =
[x]jallasa x|p3]
x
and aj > O are flexible weight terms that can be chosen to ensure good properties. Note that we have implicitly extended the domain of to Q. Each local function 99 : A -> TR is required to be continuously differentiable and strongly convex on the relative interior of the local probability simplex A4, They show that the proximal steps on the dilated DGF can be efficiently computed, provided that the proximal steps for each individual S) can be efficiently computed.
The DilEnt regularizer 1 and each local regularizer d, being the negative entropy function. has been used as a specific instantiation for practical implementations (e.g. 28]. The function has the following closed form.
R is specific instantiation of the dilated DGF with a, 1
x x[ja]
: ΣΣ
x[ja]]n In
x(p3)
JEJ aEA,
Prior to our work, weighted variants of the dilated entropy had been the only variants known have concrete strong convexity bounds, all with weights that grew with the size of the decision space beneath a given decision point [27, 16]. These results used the standard & norm as the corresponding norm for showing strong convexity. With the help of our new primal-dual treeplex norms, we can show that the DilEnt regularizer enjoys very strong properties on the extensive-form decision space. We inspect the following y weeihtted dilated entropy for e e):
{xija] x(pp)
Σ Σ ylja|x[ja] JEJ DEA;
Py I
By showing that the function equivalent the y-weighted negative entropy on the terminal reach, we are able to prove by is 1-strongly convex with respect to the y-weighted & norm. Since the difference 1 Py is summation of convex functions, it can be finally demonstrated that the Dillnt regularizer is 1-strongly convex with respect to the treeplex E norm.
7

---

Lemma 5.1. The weight-one dilated entropy (DilEnt) is 1-strongly convex within the extensive-form decision space with respect the treeplex & norm and strategy profile x E Q, we have that |zz| (1()))
|| || Specifically, for any vector R 2 H11
The complete proof is provided in Appendix D. Next, we inspect the diameter of the decision space measured by DilEnt. Using an induction statement, show that in |/] f (x) S 0 holds for any strategy profile x E Q. By choosing the initial strategy that minimizes the DilEnt regularizer, we upper bound the diameter of the sequence-form decision space with respect the DilEnt regularizer.
Lemma 5.2. Xet argmin (Pi (x) be the strategy profile minimize the DilEnt regularizer.
The Bregman divergence generated by the DilEnt regularizer between X and any x, E Q can be upper bounded by P4p (x,, x1) S In V//.
By combining the above lemmas, have that the DilEnt regularizer achieves |D|/ S In [V]- Using this result, we can establish performance guarantees for FOMs with the DilEnt regularizer. We list these results in the following sections.
5.1 Results on Online Mirror Descent
We first inspect online learning in TFSDP with coll-informatio feedback. Consider the use of (Predictive) OMD [12]. The pseudocode of the algorithm be found in Algorithm I in Appendix B. The algorithm starts from X1 <- argmin ( and follows a straightforward structure in each episode t: Take proximal gradient step from X, according to the prediction m, get the policy x,; Execute policy x,; Take another proximal gradient step from X, according to the observed reward vector W; to get X++1- The algorithm takes some DGF &o execute proximal steps:
f [m x2), X++1 + X,).
The value of prediction m, depends on the specific variant used (e.g. m, <- W,-1 in Optimistic OMD). For the non-predictive variant, algorithm has the following regret bound with respect to given pair of primal-dum norms.
m, O, and thus x; = Xg. It is known that the
Theorem 5.3 (Regret Bound for (Predictive) OMD, Rakhlin and Sridharan [37], Syrgkanis et al. [39]). Let || Il and ||- Il. be pair of primal-dual norm defined R Let yo be DGF that is p-strongly convex on || |]. Denote we as the reward gradient received in episode t. The cumulative regret of running (Predictive) OMD with DGF oo and learning rate 17 can be upper bounded by
T
Regret(T) max X.EO
Σ xx X1, w.)
1 (x., +
7 2p
Σ
W; m
Consider using non-predictive OMD with the DilEnt regularizer ş1. The performance of the algorithm can be analyzed by selecting the treeplex { norm and the treeplex Eoo norm as the desired pair of primal-dual norms. Using the diameter-to-strong- www-strrnnn-ovexitty ratio of Dillnnt, we can immediately get regret upper bound that recovers the state-of -ftee--f-hhearr result given by KOMWU [20].
Theorem 5.4. Let &o be regularizer for extensive-form decision space Q which is ju-strongly convex on || |/x,1 and has diameter [D] := sup,. (xp æ1). Under Assumption 3.1, the cumulative
regret of running OMD with regularizer yp and learning rate 77 == /2/D)/(u(T) is upper bounded by
Regret(T) I ( /2D///
Moreover, if we use the Dillnnt regularizer i0 proximal steps, the result can be specified
Regret(T) < /VVT.
5.2 Results on Clairvoyant Online Mirror Descent
Consider equilibrium computation in n-player EFGs. In this scenario, group of agents aim to jointly learn the coarse correlated equilibrium (CCE) given only oracle access to the game (See Appendix for detailed definition). We adopt Clairvoyant OMD to compute CCE, introduced by Piliouras et al.

---

[36], Farina et al. [19]. The pseudocode of the algorithm can be found in Algorithm 2 in Appendix B. The algorithm can be viewed as a specialized form of predictive OMD, in each episode [K] an additional routines is introduced to compute the prediction vector m, for each player (we omit the superscript). The prediction the episode is calculated through L. steps of fixed-point iteration starting from x,,1 x, In each step / E [T.]. each player i computes proximal step
X1,+1 < ( xx).
where we denote by Wt, the reward vector observed by the player joint policy is corresponding to Xt,-- Clairvoyant OMD finally sets the prediction m; to the iteration result Wr,z. In this case, the committed policy X, + (v)m, Xx) in the OMD framework equal X,,I and the reward vector W, is W1.++1- We show the fixed-point iteration achieves linear convergence. Thus, the difference [|Wr,L+1- Wr, can be made as arbitrarily small. The proof starts from the following inequality, establishing that the reward vector is Lipschitz continuous with respect to the joint strategy:
R
Σ ==1
( |
( X2 ||0,111
W
W2
HG
S
We denote by Wi the reward vector of player i when all the players align with joint policy {x[ j==1 Together with the fact that the proximal operator Lipschitz (Lemma 3.2), we can show that the fixed-point iteration achieves a linear convergence rate when the learning rate ry is sufficiently small.
(1)
Lemma 5.5. Under Assumption 3.1, when running COMD with DilEnt, the reward vector w!. (.)
received by player in any (t, l) E [K] x [Z]] satisfies [ w 121 S 2(nn)(-1
Therefore, with a logarithmic number of iterations, the discrepancy between the reward vector and the | We.r wl I 1/K. Substituting this result into Theorem 5.3 implies the average joint policy given by all x, among t t [K] episodes in Clairvoyant OMD only causes constant regret. Using the standard online- to-batch conversion [9], we can demonstrate that Clairvoyant OMD finds an c-CCE with only a near-linear number of oracle accesses to the game, establishing the new state of the art.
prediction in the OMD framework can be made as small as ||w, /ww,m,ll....
Theorem 5.6. Under Assumption 3.1, if every player runs Clairvoyant OMD with DilEnt regularizer and learning rate 1 1/(2n) for K episodes. With L = [log K1 steps of inner iterations, the average joint policy म is an e-CCE for e S (n In / K). This implies the algorithm converge to CCE at rate (n log log T where T KL is the number of oracle access to the game.
6 Lower Bounds for Regret Minimization in EFGs and Optimality of DilEnt
In this section, we show that the DilEnt regularizer has a nearly optimal ratio within the extensive- decision space. To establish this, we prove lower bound for online learning in TFSDP with full-information feedback. We show that every algorithm must suffer a regret lower bound that matches our regret upper bound in Theorem 5.4. The optimality of the DilEnt regularizer is demonstrated by contradiction: If there were a regularizer with much better diameter- poneette-tt-sttoore tow-ttoo-s--oooott -tovviico ratio, then the regret of running OMD with that regularizer would violate the established regret lower bound. We prove the lower bound by constructing a hard instance that is completely random. In this scenario, no online learning algorithm can benefit from historical data, while the cumulative reward of the optimal policy benefits from the anti-concentration properties of the maximum among random distributions.
Theorem 6.1. Given a TFSDP with decision space Q, there is an EFG satisfying Assumption 3.1 such that: when the other players are controlled by the adversary, any algorithm Alg incurs an expected regret of at least O /I Q i log Aul MolVT) for given of episode number T > || where |Aol = minjez |A,1 is the size of the minimum action set.
We provide missing proofs in Appendix E. Comparing Theorem 6.1 with Theorem 5.4, we estab- lish a lower bound for the diameter- soneeter-to-ssrorn to-strong coonnn-tcovxxttyy ratio, |DI/# 2 2[I|Q]] log (Aal) for any regularizer on the extensive-form decision space with respect to our new treeplex norms. Recall the poneterrto--sroong-coveeee
ratio of the DilEnt regularizer is at most /D//u < In \V) derived from combining Lemma 5.1 and Lemma 5.2. We establish connections between these two quantities using the following lemma, implying that the ratio achieved by the DilEnt regularizer is nearly optimal.

---

Lemma 6.2. Consider a TFSDP with given point set H. Define |A] := maxjez |Ay] as the size of the largest action set. If there no non-root observation point yields exactly one observation outcome, that is, Cal 2 2 for any E X+ \ &, then it follows that In VI v [[]] log [l). Without this structural condition, we have In [V] I (I log J x Al) general.
According Lemma 6.2, if every each action set has the same number of actions |Ap = |A|,, and no non-root observation point yields only one outcome, we have [DI/ S |n|V] S @[I _ log | )), implying the DilEnt regularizer achieves the optimal soameter-o-sttrog-comm factors in this scenario. If the action sets vary in size, it creates gap logarithmic to the size of the maximal action set. If there is some observation point that yields only one observation, the gap inflates with another factor of logarithmic to the number of decision points. All in all, the DilEnt regularizer achieves the optimal Saamelerto--ttrog--oonee
ratio up to constant
ratio up to only logarithmic factors.
Conclusion, Limitations, and Open Questions
In this paper, introduce a new primal-dual norm pair for studying the strong convexity properties of distance-ges eestance-generating functions for sequence-form strategy polytopes arising in extensive- games. Quantifying these properties is key component in the construction of efficient first-order optimization methods for equilibrium computation. Our techniques enable us to explain the strong theoretical performance of the DilEnt regularizer, for which meaningful strong convexity bounds were previously known. In fact, we find that among all convex regularizers for extensive-fome games, DilEnt is optimal up logarithmic factors. To establish this result, we introduced new regret lower bound for learning in extensive-form games, which is likely of independent relevance.
We remark that our lower bound only applies to extensive- a setting common in self-playing algorithms. Thus, the optimality of the DilEnt regularizer may not extend scenarios with stochastic feedback. It would be interesting for learning under other types of feedback. While Fiegel et al. [21] gave matching lower and upper bounds under trajectory bandit feedback, results for external sampling remain open
games with full-information feedback,
study tight lower bounds
knowledge.
Furthermore, we can only prove tight upper and lower bounds up to constant factors for the diameter- lo-strong-convexityy ratio in specific family of TFSDPs. There still remains logarithmic gap related to the total number of sequences in general. In principle, it is possible that this gap could be further reduced, yielding different regularizer that offers logarithmic advantages over the DilEnt regularizer. Overcoming this technical hurdle and showing that the DilEnt regularizer indeed achieves the optimal rate remains interesting direction of research. Notably, Fiegel et al. [21] were also only able to prove lower bounds in specific games under bandit feedback, alluding to the intrinsic hardness of proving lower bounds without slight restrictions to the game class.
Acknowledgments and Disclosure of Funding
Christian Kroer was supported by the Office of Naval Research awards N00014-22-1-2530 and 1-114---3--23744 and the National Science Foundation awards IIS-2147361 and LSS-2289900.
10

---

References
[1] Ioannis Anagnostides, Alkis Kalavasis, Tuomas Sandholm, and Manolis Zampetakis. On the complexity of computing sparse equilibria and lower bounds for no-regret learning games. arXiv preprint urXiv:2311.14800 2023.
[2] Yu Bai, Chi Jin, Song Mei, Ziang Song, and Tiancheng Yu. Efficient t-regret minimization in extensive-form games via online mirror descent. Advances in Neural Information Processing Systems, 35:22313 22325, 2022.
[3] Yu Bai, Chi Jin, Song Mei, and Tiancheng Yu. Near-optimal learning of extensive-form games with imperfect information. In International Conference on Machine Learning, pages 1337-1382. PMLR, 2022.
[4] Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):167-175, 200. 2003.
[5] Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. Heads-up limit hold'em poker is solved. Science, 14:46621):145-1444 2015.
[6] Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 35906374):41-4444.200 2018.
[7] Noam Brown and Tuomas Sandholm. Solving imperfect-inge innermaatinnooooaiionn games via discounted re- gret minimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1829-18366 2019.
[8] Noam Brown and Tuomas Sandholm. Superhuman ai multiplayer poker. Science, 365 (6456):885889, 2019.
[9] Nicolo Cesa-Biande and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[10] Gong Chen and Marc Teboulle. Convergence analysis of proximal-like minimization algorithm using bregman functions. SIAM Journal Optimization,, 3(3):538-543, 1993.
[11] Xi Chen and Binghui Peng. Hedging in games: Faster convergence of external and swap regrets. Advances in Neural Information Processing Systems, 33: 33:18990-18999 2020.
[12] Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. Conference on Learning Theory, pages JMLR Workshop and Conference Proceedings, 2012.
[13] Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. Advances in Neural Information Processing Systems, 34:27604- 27616, 2021.
[14] Gabriele Farina, Christian Kroer, Noam Brown, and Tuomas Sandholm. Stable-predictive optimistic counterfactual regret minimization. In International conference on machine learning. pages
PMLR, 2019.
[15] Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Online convex optimization for sequential decision processes and extensive-form games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1917-1925, 2019.
[16] 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 2021 ACM Conference on Economics and Computation, 2021.
[17] 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, volume 35, pages 5363-5371, 2021.

---

[18] 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, 35:39076-39088 2022.
[19] Gabriele Farina, Christian Kroer, Chung-Wa Wei Lee, and Haipeng Luo. Clairvoyant regret minimization: Equivalence with Nemirovski's conceptual prox method and extension to general convex games. arXiv preprint arXiv:2208. 14891, 2022.
[20] Gabriele Farina, Chung-Wai Wei Lee, Haipeng Luo, and Christian Kroer. Kernelized multiplicative weights for O/1-polyhedral games: Bridging the gap between learning in extensive-form and normal-form games. In International Conference on Machine Learning, pages 6337-6357. PMLR, 2022.
[21] Côme Fiegel, Pierre Ménard, Tadashi Kozuno, Rémi Munos, Vianney Perchet, and Michal Valko. Adapting to game trees in zero-sum imperfect information games. In International Conference on Machine Learning, pages 10093-10135. PMIR, 2023.
[22] Samid Hoda, Andrew Gilpin, Javier Peña, and Tuomas Sandholm. Smoothing techniques for computing nash equilibria of sequential games. Mathematics of Operations Research, 35(2): 494-512, 2010.
[23] Wan Huang and Bernhard von Stengel. Computing extensive-form correlated equilibrium in polynomial time. In International Workshop on Internet and Network Economics, pages 506 513. Springer, 2008
[24] Albert Xin Jiang and Kevin Leyton- Brown. Polynomial time computation of exact correlated equilibrium in compact games. In Proceedings of the 12th ACM conference on Electronic commerce, pages 119-126, 2011.
[25] Wouter M Koolen, Manfred K Warmuth, and Jyrki Kivinen. Hedging structured concepts. In COLT 2010: Proceedings of the 23rd Annual Conference on Learning Theory, pages 93-105, 2010.
[26] Christian Kroer, Gabriele Farina, and Tuomas Sandholm. Solving large sequential games with the excessive gap technique. Advances neural information processing systems, 31, 2018.
[27] Christian Kroer, Kevin Waugh, Fatma Kilınç-Karzan, and Tuomas Sandholm. Faster algo- rithms for extensive-fome game solving via improved smoothing functions. Mathematical Programmingg pages 1-33, 2020.
[28] Chung-War Wei Lee, Christian Kroer, and Haipeng Luo. Last-iterate convergence in extensive-form games. Advances in Neural Information Processing Systems, 34: 12114414405,,,, 2021.
[29] Mingyang Liu, Asuman E Ozdaglar, Tiancheng Yu, and Kaiqing Zhang. The power of regular- ization in solving extensive-form games. In The Eleventh International Conference on Learning Representations.
[30] Mingyang Liu, Gabriele Farina, and Asuman Ozdaglar. A policy-gradient approach to solving imperfect-infooration games with iterate convergence. arXiv preprint arXiv:2408. 00751, 2024.
[31] Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337):588-51,, 2017.
[32] John F Nash Equilibrium points in n-person games. Proceedings of the national academy of sciences, 36(1):48 49, 1950.
[33] Arkadi Nemirovski. Prox-method with rate of convergence (1/t) for variational inequali- ties with lipschitz. continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229-255 2004.
[34] Yu Nesterov. Excessive gap technique in nonsmooth convex minimization. SIAM Journal on Optimization, 16(1):235-249, 2005.
12

---

[35]
Christos H Papadimitriou and Tim Roughgarden. Computing correlated equilibria in multi- player games. Journal of the ACM (JACM), 55(3):1-29, 2008
[36] Georgios Piliouras, Ryann Sim, and Stratis Skoulakis. Beyond time-average convergence: Near- optimal uncoupled online learning via clairvoyant multiplicative weights update. Advances in Neural Information Processing Systems, 35:22258-22223 2022.
[37] Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Conference Learning Theory, pages 993-1019 PMLR, 2013.
[38] Tuomas Sandholm. The state of solving large incomplete-information games, and application to poker. Ai Magazine, +1(4):13-33 2010.
[39] Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast convergence of regularized learning in games. Advances in Neural Information Processing Systems, 28, 2015.
[40] Oskari Tammelin, Neil Burch, Michael Johanson, and Michael Bowling. Solving heads-up limit texas hold'em em. In Twenty-fourhh international joint conference artificial intelligence, 2015.
[41] Bernhard Von Stengel. Efficient computation of behavior strategies. Games and Economic Behavior, 14(2):220-22 246, 1996.
[42] Brian Hu Zhang, Ioannis Anagnostides, Gabriele Farina, and Tuomas Sandholm. Efficient d-regret minimization with low-degree swap deviations in extensive-form games, arXiv preprint arXiv:2402.09670 2024.
[43] Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret mini- mization in games with incomplete information. Advances neural information processing systems, 20, 2007.
13

---

A Extended Preliminaries
An extensive-form game (EFG) is n-player game with sequential structure representable tree. Let ' be the set all nodes the tree, where each node 2 E corresponds to a game state. Each node is assigned to either player i E [[]]] or the environment for action. The subset T C T comprises nodes assigned to player i. The environment, treated as special player, acts according to a fixed distribution, modeling stochastic outcomes like card dealing in games. Each node's branches represent possible actions. Upon reaching node, the assigned player selects an action, moving the game to the next node per the tree structure. Let be the set of terminal nodes. The game concludes when it reaches terminal node 2, where each player receives reward (2). Players aim to maximize their expected reward by reaching these terminal nodes. We assume [=] [o, 1]. following Assumption 3.1.
Player
A
Player
Information set
Decision point
Logend
B
X
Observation point
8
8
Terminal point(node)
Figure I: An two-player extensive-form game and the corresponding TFSDP of player 1. The TFSDP
has decision point J {A. B, D). It has tree size | 4 and leaf count ||Q] 2. both
given by the pure strategy {A + 1,B - 3,C + 5}. Furthermore, The player has [V = 7 pure strategy profiles in total.
We model imperfect information with information sets. An information set I S ( subset of nodes assigned to player i, which the player cannot distinguish. The player must act consistently across all nodes within the same information set. For example, in poker, an information set includes all states with identical public cards and bets, with each node representing a different potential hand held by the opponent. Each terminal observation point a E g() is associated with set Ig S Z of (4) denotes the
corresponding terminal nodes in the original EFG. For each terminal node Z, of observation point of player in the TFSDP.
Let ग (x) )==1 be joint policy of n players. We denote by ( (i) the expected reward received by player. Consider the terminal node E Z, the reach of probability can be computed by
p[=] [ī x00 (o("),, where p(z] is the product of transition probability of the environment actions from the root In this case, the expected reward of player is given by
( (T)) = Σ [2) p[2] II
x (o
ZEZ
5=1
Consider the corresponding reward vector w( = (z) E R of player when the players
agree on joint policy x [x{)) The vector satisfies that u(() (T) = (xl(), w()).. is clear that
the reward vector has the following closed form for each entry:
( (0)
Σ ((() [=] plz] II (1) (o!))
Vo g
SEI.
jf1
In this work, we examine two problems in EFGs. For the online learning problem, an agent seeks to maximize their expected reward while facing an adversarial environment and other players in the online measioonmakinn process. The agent can observe the reward vector w, after committing the strategy profile x, in episode t. We measure the performance of the online learning algorithm using regret. The cumulative (extemall) regret over T episodes is defined as:
Regret(T) == max
X., W.)
Σ (x,. w.).
14

---

where x; is the strategy proposed by the player in episode t. This definition quantifies the cumulative difference between the expected rewards that could have been obtained by the optimal strategy and those achieved under the actual strategy used.
For equilibrium computation, group of agents aim to jointly learn the coarse correlated equilibrium (CCE) given only oracle access to the game. A joint policy profile т is said an s-CCE, if for any player i, it satisfies that
(x(1)) x) S (x) Vx E eQ'
where we denote by x0 (-(()) the joint policy in which player i takes strategy profile x(!) while other players still follows It is known that the equilibrium computation he reduced to online learning: every player runs a no-regret learning algorithm simultaneously, then the average joint policy ör of the interaction history is an &-CCE with & < max (T) [9]. As the players are not adversarial against each other, the regret bound of the learning algorithm can sometimes be improved compared to the online learning setting.
B Pseudocode of Predictive OMD and Clairvoyant OMD
In this section, we list the pseudocode of the algorithms used in the paper.
Algorithm 1: (Predictive) Online Mirror Descent
X1 <- argmin xxx)
for do
Receive prediction m, (set m, = 0 for the non-predictive variant)
X; IT (1),; x2)
Commit policy Xx, receive reward (x,, wx) and observe reward vector w:
8,+1 + 11p (1/W,,
end
The (Predictive) OMD framework [12, 39] depicts a family of no-regret learning algorithms. The pseudocode of the algorithm can be found in Algorithm 1. The algorithm takes learning rate μ and a DGF yp for the decision set of the TFSDP as parameters. starts from an initial point X and follows straightforward structure in each episode t:
Receive prediction vector m, from external logic (set m; = 0 for the non-predictive variant)
Take a proximal gradient step from X, according to the prediction m, to get the policy x,
Execute policy x; and observe reward vector Wt.
Take another proximal gradient step from X, according to w, to get X,41 for the next episode.
can be shown from Theorem 5.3 that the algorithm achieves sub-linear regret rate of /T in general. The performance of the algorithm can be further improved by selecting more accurate m,, For example, if we can ensure m, = Wt, then the algorithm suffers only constant regret, upper bounded by (x., (x.xxx))/1 x1)/n.
Although the reward vector w, in the adversarial setting is given by the environment which is generally unpredictable, in self-playing, it is determined by other agents, which generally follow smooth dynamic and thus be predictable. Syrgkanis al. [39] introduced Optimistic OMD, which sets the prediction m, + w,-1 as the reward vector given from the previous play. This allows them to establish a regret bound of OTT1/), By analyzing the higher-order derivatives, Daskalakis al. [13] show [m,- w,|l+ small in Optimistic OMD, which finally leads a logarithmic regret bound of Ollog" T).
Note that the desired prediction m, = w, is solution to w (, (IT) for every player i, where 11 (nw, xx(") for each player i.
the joint policy n, (x(") J is given by proximal step x; (8)
15

---

Algorithm 2: Clairvoyant OMD, Decentralized
for each player E [n|], in parallel do
x argminxegen (x(
for to K do
x, t x(1)
for | = 1 to do
Synchronous with other players and commit joint policy Te, (x 1i
Observe reward vector w!() 0₂u()) 0,u(%(Te.)) (me,)
11+1 To (nw x(
end
(i)
m
w
1/ x; 1I 11 1pss((1p)) (1) (6) 52))
Xt
f L f- TI,L
(5)
W
f W Wil+1
(i)
1/ x0 = II o6o (n/W? x(())
1+1 < X (,L+1
end end
Report average joint policy 7 of m. among E [K]
Note this is fixed-point to dynamics
fx; 1n li=l
+ ( (TT))
t- -rp (1/w x())
Clairvoyant OMD [36, 19] uses these update rules to find m, through the fixed-point iteration. By showing that all these updating rules are Lipschitz, one can see that this fixed-point iteration achieves a linear convergence rate when the learning rate rj small. Let K be the number of episodes used for aggravating the average joint policy. The linear convergence rate allows one to find m, where [|m - well+ is polynomially small with (1//K) in only Olog K) steps, indicating that the corresponding OMD dynamics only suffer from constant regret bound. This finally establishes that the algorithm has an almost-optimal convergence rate of log T/T where K L is the number of oracle access to the game.
C Proof of Treeplex Norm
C.1 Proof of Lemma 4.1
Lemma 4.1 (restatement). The functions || || and
|| are norms defined the space R
Proof. We verify that || ||H.1 and || 1 are norms as follows:
Positive definiteness: It is clear from the definition that ||u||æ.1 H1 0 and ||u||/, = 0 when u 0. When u * O, there exists ou E such that |u[ou]| O. From the definition of 3/, we can always find some transition kernel Yu such that du is reachable. In this case, yulam] >> 0 and we have
||u|l 2
yulo] 2 |u[ax]] yuloul > 0. Σ |u[o]] OEE
Similarly, always find some strategy profile x with xu(oul which implies that
|
Elulol x. |o| 2 |u[ax]| xulau] > 0.
OEE
This verifies that both functions are strictly positive non-zero vectors.
16

---

Homogeneity: For any k E R and u E R it holds that
sup yEV DEE
ku[o y[o]]
|k| sup
||or]
y/a]
[k| ||ulbx
yey oE
ku 11,00
sup x
x(o]
| sup x 3EE
|uo]]
x
[k]
|
which verifies absolute homogeneity.
Triangle inequality: We verify the triangle inequality for any u1 R$ by
[1 + u2/1 sup yEy
|
+
u2[o]] ylol
sup yEy dEg
[a]] ylo] + sup
|2[aa] ylo]
||u 1l,,, + || 2,11
yE
With similar calculation, it straightforward check || also satisfies triangle inequality, To conclude, both || ||x,1 and || H,o norms.
C.2 Proof of Lemma 4.2
Lemma 4.2 (restatement). Let u E R be vector with respect to some point h E H. The treeplex l norm and the treeplex to norm of vector over Hr can be computed recursively as follows.
If h a E & is terminal observation point, then:
||,l|,,,,1 H,,1 := |ujo]]
||ul|,.,,. == |=|[o]]
I = E J is decision point, then:
|| EnEA, || ||ul|,y,,0 := max [|u[Eja]l
If = E Σ | max.eA; ||u[Ejalllu,a..
non-terminal observation point, then:
||ul| = EaEd, ||4|Ea [ijjallusssee.
Proof. Consider the statement for treeplex & norm. The plan is to prove the statement by induction on H from the bottom up on TFSDP. We will show that the recursive definition ensures ||u|| u.. represents the treeplex & norm restricted to the subtree of h. Specifically, we will demonstrate that for every point h E and vector E E the recursive formula at point matches the original definition of treeplex & norm with restricted in the subtree HA. which is:
u HA.
sup y)
yeM
Case 1: The base case for the induction occurs when h = where E is a terminal point. We verify the induction basis by
|ul|,..1 |u[a]] 1 = sup (/u),y),
yEv,
where the last equality is given by the fact that y(Ea] = for y E Vo.
Case 2: For any decision point h j J. it holds that
| 11, Σ
|u[8 |u[5a]|lx,,..1
nEAA,
Σ sup aEA, y,
Σ (1lEgall:
sup (ynxe)aaaaa, aEA,
ssup Σ ((l yEv; aE.Aj
sup (lu).)). yE);
17

---

where the first equality holds according to the recursive definition of ||u]],,, the second equality follows from the induction hypothesis, the third equality holds as the set of terminal points Eja are disjoint for each E Aj. the fourth equality follows from the fact that V/ can be decomposed into the Cartesian produet of Vja among all A, for any j E J. and the last equality holds as each term of the & norm is positive.
Case For some non-terminal observation point o 21 &, will show that quantity ||u|| Ho.1 = maxjec, ||u[E]]] Ht, is neither less than nor greater than supyey, (lu), y(&))) Firstly, for decision point j C. that a successor of o, satisfies that
|| 11,,,, sup (I(E)llyy.)) S sup (Jul,y). ye
ye>,
where the equality holds from the induction hypothesis and the inequality holds since the inner product be upper bounded according to [[[[E]ll I (jul.y) and 3 is subset of a By taking the maximal among all successor j E Co. this inequality immediately establishes an upper bound for ||u]|
|ull max |u[E,]|,,,,1 sup ()ul.y). yEy.
(C.1)
JEC.
Moreover, fix some transition kernel y Vo. According the tree-structure the TFSDP, we have that the vector y [Ej]/y[5] with respect to some successor j E C. is valid transition kernel with in the subtree of j. other words, we have vector y|E]//y(i V/, Thus, we can write
(lul,))
Σ vli JECs
$
Σ
ylil sup
JEC.
yee3
Σ JEC.
ybo |
max JEC,
|||,,
where the first equality follows from the fact that Ej, for all successor Co. forms partition of E., the first inequality holds since yEı]//yjj] E )), the second equality follows from induction hypothesis, and the last inequality holds since Ejec, yOil and yij] 2 for transition kernel E Vo. By taking supremum among all transition kernel E Vo, we establishes an lower bound ||l|| Ho.1
sup (lul,) yEV.
S max |||[,]]|,,,, = ||u||
(C.2)
jEC,
As the upper bound in (C.1) and the lower bound in (C.2) agrees on the same quantity, we immediately reach the following equation
||u]| max
[u(E,)
Rt,1
sup (lul.y)
jEC.
ye
which proves the induction statement on observation point
In general, the induction hypothesis always holds. By inspecting h Ø, we reach the desired
statement in which ||u|/ supyey (/ul/ ||u||H,1
Finally, since the treeplex lxo norm closely mirrors treeplex & norm, the result for treeplex los norm can be directly reached with the only modification being the interchange of cases 2 and 3. [
C.3 Proof of Theorem 4.3
Theorem 4.3 (restatement). We have || l|x.1 and || ol a pair of primal-dual norms for a given TFSDP with point H. Specifically, for any vector u E E
(u, v)
| VERE
sup
||l|| H
||
18

---

Proof. Firstly, from the definition of the treeplex & norm and the treeplex & norm, the nomn of any vector is equal to the norm of the vector that takes the absolute value at each index, that is, we have ||, = lllvll and | |||
holds for any u, E IR Therefore, we can always choose such that matches the sign of maximize the inner product the dual norm, which implies
(u, v)
| = sup
sup
| vERF l|v|l
VERF
We will use induction on 7. from the bottom up, demonstrating that || || = || 20. always holds for every H. Specifically, will show that for every H. and IR:";
(u [vl)
||
sup vER%
Case 1: The induction basis occurs at h E E, where the statement can be verified from
(Lu), [v])
|ulo]|
vloll
sup
sup vER
|uoo]
Ha,00
VER M Ho.1
|voa]
where the first equality is given by Lemma 4.2 and last equality given by Lemma 4.2.
Case 2: Consider some decision point = j E J. It satisfies that
(Jul. [v) sup ExEd, |v[Ejall Myy.a (v Ee
ExEA, [v
[v[E,a])
EnEA, (lu(Eja]l (vaal? EeEr, Vijallyaa
sup vER", [ VER*,
sup
(C.3)
where the expression for the numerator in the first equality is valid since Eja for a E Aj a partition of Ej. while the expression for the denominator follows from Lemma 4.2. The fraction can be interpreted as weighted average (lu[E,a]], (/alll///ll////// // Hy.. indicating that
EaEA, (ulEgall-lvsal max aEA,
EnEA; [[valll Hy..
V Hy..
Additionally, by choosing some specific E A, and assigning Vja' = for any a' o we have that E,EA, (lu(Eja]b (Vjal)
sup [v ER haed These inequalities define the upper and lower bounds for the same quantity, leading to the equation:
sup E3
ExEd, || "Jal|
V (
[V EnEA, (vaal) max sup aEA; cR || Hya.l
(lu[Ejall//vjal
sup (vJoCR )aCAAj
(C.4)
EnEA, Vaalll3and
Moreover, according to the induction hypothesis, we can replace the inner supremum by
(lu(E,all- (Vjal)
sup
(C.5)
V Mla.1
By combining (C.3), (C.4), (C.5), and Lemma 4.2, we establish the induction statement on E J:
[ul]
[v))
sup vER*,
max ||u[Eju]llx,,..e ||u||
| M1,1
aEA;
Case When = E E\E, follows from the symmetric relationship between treeplex E norm and treeplex for norm that, similarly to the previous arguments, can conclude that
(lu).
sup vERE.
||u||
|
This suggests that the norm desired statement, in which
|| Il is dual norm of || Il which immediately leads to the
[v))
sup
|
veRE.
19

---

C.4 Proof of Lemma 4.4
Lemma 4.4 (restatement). We have | for any strategy profile x E Q, |l 1 for any transition kernel y E V and |w S for any feasible reward vector under Assumption 3.1.
Proof. According to the definition of Q and y, for any element x Q and y y, it is established that |x ly, and their respective x[h] and y(h] agree on the same recursive formula across all E H given by Lemmas 4.2. Consequently, Ityll,,, = ylh,, thereby implying ||x||x.1 = and || 1. Finally, we have = y r for r E [0, 1] under Assumption 3.1. Thus, we have
always true that ||x||x. = x(h] and
|w|l
sup (Iw) x sup (|r| o ly.x) S sup (v/l. xE
|lll,, =1
x
xEQ
where the inequality is given by the x is always non-negative as well as S 1.
D Proof of Regret Upper Bounds
D.1 Proof of Lemma 5.1
Lemma 5,1 (restatement). The weight-one dilated entropy (DilEEnt) is 1-strongly convex within the extensive-forn decision space Q with respect to the treeplex & norm l| Specifically, for any
vector z E R and strategy profile x E Q, we have that || |z|](>=p1(() | k.1
Proof. For some transition kernel y E V/ we define the y-weighted dilated entropy:
[ja] x(ps
(x Σ Σ
y[ja|x[ja] In
JEJ aEA,
By decomposing the logarithm term in the summation, we get
My (x)x)=
Σ ylja|x[ja] xnjaja]= Σ Σ JEA
y[ja]x[ja] In xpppp
(D.I)
JET REA,
Ia
We rewrite the first term as
I Σ Σ
in Σ
(D.2)
jEJ aEA;
For the second term, we can further write:
In Σ Σ
y[ja|xjja] In x|ppp
JEJ REA,
Σ [5]x
IEJ
Σ Σ
[nxx
OEDIE JEC,
Σ
y/o]x|o] Inx[o]
(D.3)
OEDVE
where the second equality is given by y[u] yija] for transition kernel E y and x[p;] E.CA, x[ja] for strategy profile x E Q, the third equality is derived from the fact that Cr, for E Σ E, forms a partition of J. and the last equality follows from y(a] Σjec, ylil for any non-terminal observation point E Σ \ E over y e
Plugging (D.2) and (D.3) into (D.1), we obtain the following result, indicating that function My can be expressed as the weighted negative entropy over all terminal observation points a E E:
(x = [ylo[x(a] Inx[a].
aEE
20

---

We are ready to show the strong convexity of weight-one dilated entropy 91. Consider vector z R.. Since function By is additively separable over all variables x(o]. the Hessian matrix of Py PPy() (x) diagonal. Thus, the squared norm of z over Vy (x) can be interpreted according to
Py = Σ
2/003.
V (y)
3EE
y(a)
Σ
z/0
x
ylol
(Σ yoox(oo)) 3EE
x(o]
3E0
y/o
Vylo|x(ol)
X|07
||||||
ylol) (12),
(D.4)
E
where the first inequality follows from Lemma 4.4 which implies Eoee y|o|x|o| I |yllu,
1 as
X E X and y E y and the second incquality is given by the Cauchy-Schwarz Schwarz incquality.
Moreover, consider the difference between function (-1(t) and sy (.), we have
x x
P1-y(x) = P1 fy = Σ (1 =
y(ja)) x|ja| In
JEJ aEA,
From transition kernel y y, we always have y[ja] 2 for any jE J and E Aj. Together with the fact that a (n(bb) is convex for a, b E Rz0, we have that the difference (1-y is positive combination of convex functions. Thus, function f1-y is a convex function, which implies
z T Pi 2 0.
(D.5)
Using additivity of the Hessian and inequalities (D.5) and (D.4), we obtain
v pz (x)z = z (x)x + V (1-y(x)) 2 (lz),))
By taking the supremum among all transition kernels y VM we reach the final statement
| 1z|2=pp(0s v2 (x max |zz y)² ||z||
yEy
This concludes that the weight-one dilated entropy &1 is 1-strongly convex with respect to the treeplex E norm
|| 1
D.2 Proof of Lemma 5.2
Lemma D.1. The value of the DilEnt regularizer for some strategy profile x E Q can be bounded by - || < pp (x) < 0, where [V] is the number of reduced normal-form strategies.
Proof. Since the DilEnt regularizer is the weighted summation of negative entropy, and the fact that
negative entropy is always non-pon non-positive, by induction on the TFSDP from the bottom up. In specific, we will show that for any point e H and corresponding strategy profile x₁, E Qh. the DilEnt with retricted Hr satisfies
directly get 4p (x) 0. We will prove (p1 (x) > In |
[xAjja]
(xx) := Σ Σ
xx[ja] In
2 - In DVal
Xx [p5]
JEd,
Case 1: The induction basis occurs at h = E E, where the statement holds since for any E Qa.
(x,)
Vall
where we have V&l = 1 from Lemma F.2.
21

---

Case 2: Consider some decision point h = E J. We can decompose the DilEnt regularizer over
X, E 2 according to
())((x)=
Σ EEA,,
xj [njl|ni + Σ E x,(j'a' In
(D.6)
X, xy(py'
REA, J'E.Tuu d'EAy'
Consider the vector Xja
for some action E Aj. If xf
we have
(2)5)/9 x,[pyl = - xx In Vaal=
Σ E J'EJJa d'EA,
x, x,Ii'a In
Otherwise, it satisfies that Xja E 2ja according to the tree-structure of TFSDP. Thus, we can write
X Xx In
Σ J'EJaa a'Eyy
xsli'a' Exl''d In
X3[ja| Σ
x, xy(py|
x,lja|
Xj [pyr]
J'EJ,a d'EA,
Xioli'a a')
=xylja|
E
E
Xja (pr)
J'EJJu d'EA,
=x((jalp1.ja((5a)) 2 L-j In Vial:
where the last inequality is given by induction hypothesis. In general, it always satisfies that
Xy xxy5''4| x,|p,]
Σ ExI'd'
In
-xy(ja] [Vjal=
J'EJTo d'E
Plugging this inequality into (D.6) gives
(x,) 2
Σ
xylia| In [ -
Σ
x, x In 1
ac
aed;
2 In aEA,
cxp(-In in 1nl1al)))
In
Σ M2jal) aeA,
In |Vyl-
where the first inequality holds since the minimizer is given by xzlia] x exp(- ()ja)), and the last equality is given by Lemma F.2.
Case 3: Consider some decision point h J E Σ. We can decompose the weight-one dilated entropy according to the tree-structure of TFSDP. Thus, we can write
Xx [j'a"' x. [3'aa"] In
11.0 (x,)) = Σ
X [py]]
JEC.
J'EJT d'EAy
Σ
Pi.j (xo [E,])
jEC.
Σ In V
GEC. [Vol.
In
where the second inequality is given by induction hypothesis, and the last equality given by Lemma F.2.
In general, it always holds that sP (9,,((x)) (xx) 2 In Val. which concludes the proof. Substituting this with h = Ø reaches the desired result.
D
22

---

Lemma 5.2 (restatement). Let X1 argminxeg 91 (x) be the strategy profile minimize the DilEnt regularizer. The Bregman divergence generated by the DilEnt regularizer between x and any x. Q can be upper bounded by D4 (x., x1) ) s In [/].
Proof. From the definition of Bregman divergence Per, we can write
D2 x1) (1(x)) 4 (x(x)) (Vy1(x1). x1)
(D.7)
According to Lemma D.I, we have 4o (x.) (x1) - In [V]. From the chosen of X1 we have (Vpi(xi), -xi) 0. By plugging both inequalities into (D.7), reach the desired result
Deg (x.. x1) S In l//-
D.3 Proof of Theorem 5.4
Theorem 5.4 (restatement). Let sp be regularizer for extensive-form decision space Q which is j--strongly convex ||, and has a diameter [D] == sups, eQ (e( #1). Under Assumption 3.1, the cumulative regret of running OMD with regularizer and learning rate = (2TD)/(HTT is upper bounded by
(T"r S V2/D//uVT.
Moreover, we use the DilEnt regularizer yp proximal steps, the result can specified as
(T) z /2 MVVT.
Proof. We will apply Theorem 5.3 with || |lx,1 and || 1/x,00 be the desired primal-dual pair. In the context of the theorem, we have ||wall S 1 for any t [I']] from Lemma 4.4. Together with Dz(X,, x1) I (D), when choosing learning rate 17 / (u(T), we have the regret be upper bounded by
1 [D]
7 = V2DD/ 2
Regret(T)
7)
When selecting DilEnt as the regularizer, we have |D| < In |V] from Lemma 5.2 and μ 2 1 from Lemma 5.1. Plugging these results indicates
Regret(T) S 22 VV...
D.4 Proof of Lemma 5.5
We first prove the lemma starts from the following locally Lipshitz.
Lemma D.2. In Algorithm 2, consider two joint policies that agree on all strategy profile expect
for player E [m]] क == (xx²) (1) x(") .... xx") and = {x(²) (1) .... xx , ,x(")) Under (f)
Assumption 1, we have the reward vector is locally Lipschitz under the treeplex l norm, that is,
denote by w (8) == ()) and w! = 0. (m2) the reward vector of player i, it satisfies that
| W H0 I (x()) x2 1h
Proof. If we have (() w and the statement holds true from
|| | 0 s ||x
(7)
H0,1-
Otherwise it satisfies that o i. According to the definition of treeplex foo norm, we have that
(((() - 2001lx00000
sup (/w(" w(
Σ
w ["'[o]] x[o]. (D.8)
sup
xEQ())
x
dEEO)
23

---

By expressing the reward vector using the strategy of other players, we have that
w lol Σ
[2]
p/a]
x [
II " [o!")
(D.9)
=ET
Plugging (D.9) into (D.8) gives
| (5)
2
(1)
1,00000
(D.10)
sup xEQ( OEE
Σ
x
Σ
u
[=]
- - x 1o!')
II
x To!
SET.
Rights
< sup xc
Σ
x
Σ
p|2]
[0000 x x
II
x (o!-
TE8()
ZEI,
sup XEQ
_
p|1]
6
[o
- x o
II kyf
x
(k)
(D.11)
SE2
where the inequality holds since the reward [2] E [0. 1] and the last equality is given by permuting the summation.
According to the definition of treeplex l norm, we have
| () x2 |100,,11 = sup ()x{)
(f) - xx
l.y) 1))) = sup
(1)
Σ [x]
xx y[o]. (D.12)
yEys)
yeys) OEEO)
By expressing the transition kernel using the strategy of other players, we can write
yla] = Σ x(() [o p[a]]
II x (k) {
(D.13)
SEI.
Reghts
such that x(() E @60 and (k) E ((A), Plugging (D.13) into (D.12) gives
||x{]) - (1) (1),1 = sup
Σ x
()) [a]
x2
[o]|
Σ x
x
(o
1 p|2]
II
x (o
(2ih)) Jays dEE
#EZ.
2 sup xEQ()) rEEG)
Σ
(1) [o]
X2
[o]|
(3)
[o]]
Σ x (2)
X
(A)
(o(
ZEIe
sup
Σ
x
1
pla]
X2
(
II A
(k) x
(N), (D.14)
xEQ
=EZ
where the inequality holds as x
E Q(k) and the last equality is given by permuting the summation. By combining (D.10) and (D.14), we can reach that
|| w2 (1) l0, S [|x{ x 112661111
(D.15)
Lemma D.3. In Algorithm 2, for two joint policy कi = {x{ in and क (x,
(1)
} where
@(3) are the strategy profiles for player j E [r]]]. Consider the corresponding reward vectors wi (6) == (T)) and w/ 0, (m²) of player i E [n] when other players follow the joint policy. Under Assumption 3.1, we have the reward vector is Lipschitz under the treeplex & norm, that is,
(
| ())
w2 (
1x
(
(
1
x2
(")) which are generated by the joint policy that aligns with joint policy T2 on the first players while aligns with
Proof. Consider series of reward vector policy T6) = {x2
(1)
x1
(++1)
Ti on the rest. Denote by w (t)
(5) -0.l0) (TT)) the reward vector. Under this definition, it satisfies
that w (8) (4) and W (+)
(0) w
(m) w Therefore, we can write
n
Ghooo S
Σ [xx - x(()
j=1 where the first inequality follows from the triangle inequality and the second inequality given by Lemma D.2.
5=1
D
24

---

Lemma 5.5 (restatement). Under Assumption 3.1, when running COMD with DilEnt, the reward
vector Wa, received by player in any (t,1) [K] [L] satisfies || Walll S
(1)
2(1n))-1
(e) Proof. By applying Lemma 3.2 to the proximal steps Xi,
< p1 (nw (1-1 x(")) and 1,1+1 f
p (nww)) (i) x
have that for every / 2 1,
X 1.11
x ppce,,, S m/|l
(1) Wel-
721-111200,00 ,001
(D.16)
where the strongly convex modulus 1a 2 is given by Lemma 5.1. From Lemma D.3, have that
||
1,41 warllao
(0)
(8) ,00
X4,+1
(
(
(D.17)
In addition, the difference between the initial steps can be upper bounded according to
wi Wolllao S || [| w22.lllo,, + || ol 2
(D.18)
where the first inequality follows from the triangle inequality and the second inequality given by Lemma 4.4. By combining (D.16), (D.17), and (D.18), we reach the desired statement:
wel 11,000000000000 - 2(mn))-1
6141
D.5 Proof of Theorem 5.6
Theorem 5.6 (restatement). Under Assumption 3.1, if every player runs Clairvoyant OMD with DilEnt regularizer and learning rate 1/(2n) for K episodes. With [log K1 steps of inner iterations, the average joint policy म is an s-CCE for I O(n In V//K). This implies the algorithm converge to a CCE at rate (n log |V] log T/T) where KL is the number of oracle access to the game.
Proof. When 7) S 12m),, we have ny S 1 1/2. According Lemma 5.5, the difference between the actual reward vector and the prediction can be upper bounded by
1|w (8) m, (2) 11a0 = 1|w i.++1 w
W., wiiee 2(nn) < 22-L
Therefore, with [log K] steps of fixed txxed-point iterations, the difference can be as small as (5)
[[w(() m |1 S 4/K. K.
Let || |1a and ||. 1l be the pair of primal-dual norms required by Theorem 5.3. In the context of the theorem, we have || ,o I for any E [K] given by the definition of treeplex lo norm, Du (X., x1) & In [V] according to Lemma 5.2, μ 2 1 according to Lemma 5. and ||w m ( ('1l < 1/K K from the reasoning above. Plugging these results into the statement of
Theorem 5.3 gives:
- 1 11 |V]
nK 2
Regret( K) (erret(K55
With = 1/(2)), we get that
Regret(A K) & (n log VI).
According to the online-to-batch conversion [see e.g. 36), we can conclude that average joint policy 7x is e-CCE with < O(n log [V/K). Given oracle access budget T, we can select K = [ /o/lo T] satisfying KT. S T. This indicates that the algorithm converge CCE with approximation rate O(n log log T/T).
25

---

E Proof of Regret Lower Bounds
E.1 Proof of Theorem 6.1
Theorem 6.1 (restatement). Given a TFSDP with decision space Q, there is an EFG satisfying Assumption 3.1 such that: when the other players are controlled by the adversary, any algorithm Alg incurs an expected regret of at least O ((v Q L log (oolVT) for given of episode number T 1 I, where |Au] == minjez [Ay] is the size of the minimum action set.
Proof. We will prove the statement by induction on from the bottom up. For each point H. \ E, we construct a hard instance Σ, (T) such that any algorithm H. playing in subgame Hr incurs an expected regret of at least 12( Qh | log AA AolvT)) We construct hard instance In (T) to be two-player
information EFG that has the same structure as the given TFSDP, where all the observation points are the decision points of an adversarial opponent. It can be represented using set of random variables (yb,t, Th T== where yh. E V is the transition kernel and Th E [o, 1J encodes the expected reward of player conditional on each terminal observation point. Note that the transition kernel Ys, is also the strategy profile of the opponent his extensive-form decision space. In this case, the expected reward of playing strategy profile Xa,r on Hr. on episode can be computed by (Xh,,, Wa,s) where Wh. == Th Yh, a is the reward vector.
Case 1: The base case of the induction is that h j E I and ja E & holds for every E AA,. In this case, the TFSDP with point set Hr is equivalent to a full-information multi-arm bandit problem ka. expert problem). We construct the hard instance I, (T') by assigning
Yıa[ja] = 1, r,jj,[ja] (n0,
for every episode E case, the entries of the reward vector w, Fy, @ yy. independently random variables. Thus, the expected cumulative reward among 7 episodes of any algorithm Alg can be computed by
[2]] where Unif((0,) 1}) is the Bernoulli random variable with = 0.5. In this
T
1 Σー
E
(E.I)
2
t=1
(=1
Additionally, the cumulative reward of the optimal policy can be computed according to
)
1
max
jjar W wirD
= E
max A
aat
+
LEEA,
1=1
t=1
T
E
max
Jot
+ 2
2
LOEA,
1=1
T 2
2 S2 TTog A
(E.2)
where eja is the pure strategy profile that always executes action a at decision point y and oa, ~ 1ni are independent Rademacher random variables for A; and [7]] The last inequality follows from Lemma A. A.11 in Cesa-Bianchi and Lugosi [9]. Combining (E. 1) and (E.2)
indicates that any algorithm suffer an expected regret of least
Regret, (T)
E max LEEA
Σ jej w7 EE
Σ Xy. wo.e 2 ( (o | vT)
Note that for the j E J. we have || from Lemma F.1. Together with |A,1 2 |o from the definition of Anl, we conclude that
Regret, (T) 2 07 2 log AolVT).
establishing the induction basis.
Case 2: For any other decision point h = EE&& E I that is non-terminal, a. = argmax |1 || be the action that maximizes the leaf count in the subtree (breaking ties arbitrarily). Let I Ija. (T)
26

---

jyj,,,s Fja.,tff= . be the hard instance built in the subtree satisfying the induction hypothesis. We
construct the hard instance (T) {Yja,,s t: Fa. according
[l if o E E(ja)) .x,ooo]
{ (0
if E E(ja.) [T
y [h]
otherwise
otherwise
where refers to any valid transition kernel. other words, the construction ensures taking action a, leads to the hard instance Ija= (I') while taking any other actions always results in reward of O.
Since any action different from a, will result in a reward of O, any algorithm Alg that ever assigned weight outside ja, end up in lower cumulative reward compared to the other algorithm Alg' that consistently play action a, on decision point j. Together with the fact that playing a, will reduce the problem to Lja. (T)), no algorithm can achieve higher reward on the hard instance (T) comparing Ijn. (T). Moreover, the strategy profile given by choosing a, then following the optimal strategy profile Ijo. (T)) leads to the same cumulative reward as the optimal strategy profile on Ija. (T). This indicates that the cumulative reward of the optimal strategy profile on (T) no less than its counterpart on Ija. (T). Combining the two statements, we have that the regret lower bound on (T) is no less than the regret lower bound on ZJa. (T). This implies the regret of any algorithm Alg be lower bounded by
Regret,((2 (T) 2 St S2 (Vi logl AolVT) = 2 = (V110111 AolVT)
where the last equality follows from Lemma F.I, which indicates | = maxaed, 1/alll = 1Qaa, [L. where the last equality follows from the choice of action a..
Case 3: I - a E Σ \ E is some non-terminal observation point, we construct the hard instance (T) by concatenating several hard instance blocks, each block for one observation outcome j E C., For E C., taking observation at point always leads to decision point j. Let (T} E bzo)jec. be partition which maximizes Σ, || under the constraint E, Tj T. This ensures
T3 x T|00/11//|2 We construct the hard instance block II = (Io,e.Noalte using
the hard instance (T)) (1,4.,5,ch22n in Hj given by the induction, by assigning
Yo,lo' = [yrllo' if of E E otherwise
[rall''] if if E())
(0
otherwise
We construct the hard instance I, (T) by concatenating Io (TT) over episodes.
From the property of observation point, the cumulative regret of any algorithm on hard instance Ia-t((T) (T)) is equal that on (T;)). Since hard instances I, (T₃) are independent on the decision space, the cumulative regret on I, (T) ) is the summation the cumulative regret among all I,- (T,). This indicates that any algorithm Alg will suffer regret of least
Regret,
Σ
Regret Regret,-,(TT)
jEC.
Σ Regret, (T))
jeC.
Σ
2
110 Aua VTA
jeC,
2
( 11 log Abl T11
JeC
22 -R(V log Ao AnlvT),
where the second inequality is given by the assignment of T3 and the last equality is given by Lemma 1 in which ||Q, -1l = Ejec, 1
In general, the induction hypothesis always holds, indicating that for any algorithm Alg, suffers an expected regret of least 22( Qu] log AolvT) in subtree h. The desired result can be reached by inspecting h Ø.
27

---

E.2 Proof of Lemma 6.2
We first establish a structural result for TFSDPs where no non-root observation point yield exactly one outcome.
Lemma E.1. For a TFSDP with a given point set H. if no non-root observation point yield exactly
one outcome, that is, [Col 2 2 for any Σ \ &,, then it follows that || < 2||
Proof. We prove the statement by induction on H from the bottom up, showing that for any strategy profile x Q, and any non-root point h E H \ {2)), satisfies that
Σ x S (211 1). TE%,
Case 1: The base case for the induction occurs when h = a E & is terminal node. In this scenario, the statement holds true since
x = x/h] S x(a] 2o 1). Σ x
where the last inequality is given by Lemma F.1 in which 2110=111
Case 2: For any decision point h =j j E J, it holds that
Σ 0EΣ,
x
Σ
Σ
x[a]
aEAj
aEEja
s Σ
x[ja| (2) ja || 1)
rEA;;
Σ x|ja| (2| 1)
aEA,
- Q, -اا 1),
where the first equality follows from to the tree hierarchy of Σ, the first inequality follows the induction
hypothesis, the second inequality holds since 12jall < | || implied by Lemma F,1, and the last equality follows from x = EueA, x(ja] as x E Q. This indicates that Eeex(N)) x(a] s
[2]|@xll 1l - 1) x[h] holds in this case.
Case 3: For any mrot-noo-terminee observation point h = = E \ E,, it holds that
Σ d'EE.
x x + Σ Σ
x(o')
JEC, d'EE,
5x(o] + Σ
x(j]
-
jEC.
-x(a] (1 + 21| 111 - (C,l)
S xx (21 - 1),
where the the first equality holds due to the tree hierarchy of Σ. the first inequality follows the induction hypothesis, the second equality holds since as Eyec, 112 = I| from Lemma F.1, and the last inequality follows from the assumption
for j' C2 from x e Q as well
that [Cal 2
In general, for any non-root point / E ++, it satisfies that
Σ
x x|o| < @2|
1) x x(h]..
28

---

Now consider the root point h = Ø, we have that
Σ oE
x x|(0] + Σ Σ x(o)
jECo dEE;
S xx + Σ
x(j] . (2) 11
JECs
1 2 1 |Col
- 21
where the the first equality holds due to the tree hierarchy of Σ. the first inequality follows the induction hypothesis, the second equality holds since x[j"| - x for Co from E Q as well as Ey'ec || 2 1| = 22 [ from Lemma F.I, and the last inequality follows from [C 2 1.
According to the definition that ||| = max Eoex x(o], we conclude that ||l S 2|| if
[Co| 2 2 for any E Σ+ E
The next lemma shows any TFSDP can be transformed into TFSDP where no non-root observation point yield exactly one outcome.
Lemma E.2. Given TFSDP with given point set Ho. it can always be represented using another TFSDP H with the same compressed extensive- decision space Q such that no non-root observa- tion point yield exactly one outcome. Furthermore, the leaf count || [ remains unchanged after the transformation, while the total number of actions Σjez |Ayl does not increase.
Proof. We first present transformation which removes each non-root observation point that yields only one outcome while makes the compressed extensive-form decision space Q remain unchanged.
Let Ho be a TFSDP, where some non-root observation point outcome, say C, = {j'} for a single j'. The transformation is achieved by examining the local reduced normal-form strategy decision point j. As taking action a at decision point j invariably leads to the state transition to decision point j'. we can dictate the agent's 's actions at j' contingent on the choice of action a at point j. This eliminates the observation point a while the compressed aitensive-form decision space Q remains unchanged. and the number of actions is reduced by 1 since ja climinated. We present an example of this transformation in Figure 2.
ja Σ+ yields only one
Since the number of actions is bounded, this process will always terminate. At this stage, there is no non-root observation point yield exactly outcome, while the compressed extensive-form decision space Q remains unchanged. The total number of actions Σjer |4yl does not increase. Furthermore, since the leaf count 12] can be determined by Q alone, this suggests the leaf count || also remains unchanged after the transformation.
8
Figure 2: Eliminating observation point A2 from the TFSDP. The compressed extensive- form decision space Q remains unchanged and still has support (3. 4,5, 6, 7, 9). Thus, the leaf count for the new TFSDP remains || i 2. Furthermore the total number of actions is reduced by one.
Lemma 6.2 (restatement). Consider a TFSDP with a given point set H. Define |A| == maxje. |A,l as the size of the largest action set. If there is no non-root observation point yields exactly one obser- vation outcome, that is, |C,| 2 2 for any a E E+ E, then follows that In |V] s ((] log (l). Without this structural condition, we have in | [[[ log [J Al) in general.
29

---

Proof of Lemma 6.2. According to Proposition 5.1 in Farina et al. [20], we have [V] - |||1l When there is no non-root observation point yields exactly one outcome, have ||]] S 2 Q from Lemma F.1. This implies In |V| O(1 log [A]).
In the general cases, In this case, neither the leaf count || nor the total number of actions Σje. |Ayl] increases. The size of the largest action set can be upper bounded using the total number of actions, which can be further upper bounded from Σjer AAyl | Al. This implies In [V] O[] log | x A)) always holds.
Lemma E.2 to transform the TFSDP into the desired representation.
Auxiliary Lemmas
Lemma F.1. The leaf count ||]|_ ||@e|l _ can be computed recursively as:
If a E is terminal observation point, then:
||o == 1.
If h = E J is decision point, then:
TQرlı == maX.e4, [|Qr
If = o E & is non-terminal observation point, then:
| = Ejec. -
Proof. According to the definition of leaf count and the treeplex too norm, we have
||||_
sup
|x||=
sup<|l|, || H
x
xeQ
This establishes connection between leaf count with the treeplex &oo norm. According to Lemma 4.2, we immediately reach the desired statement.
Lemma F22 The number of pure strategy profiles |V| |al can be computed recursively as
If h E & is terminal observation point, then:
V=l:= = 1.
If h = j J is decision point, then:
My := E.EA, D/al.
If o E E \ & is non-terminal observation point, then:
Vol Iliec, [Vyl.
Proof. According to the definition of reduced normal-form strategies, the statement can be immedi-
ately reached by inspecting the vertices of each extensive-form strategy space Qn.
30

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We study the optimality of weight-one dilated entropy from theoretical perceptive. The contribution, assumptions and scope are clearly claimed in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We have discussed the limitation the conclusion section.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specfiiaatinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
31

---

Answer: [Yes]
Justification:
We provide detailed proof for all theorems in the Appendix C, D, and E.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [NA]
Justification: The paper focuses theoretical understanding and does not include experi- ments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path reproducing verifying the results. 5. Open access to data and code
32

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: The paper focuses theoretical understanding and does not include experi- ments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips..
oeeiiooolloooooo icy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ /nips. wctpublic//aeccccccccccccccc gwwpi/gg///////eeee// /Cae//ooeubbiiicc SetsSuumiisions. ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper focuses on theoretical understanding and does not include experi- ments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: ments.
The paper focuses on theoretical understanding and does not include experi-
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
33

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper focuses theoretical understanding and does include experi- ments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: / /tt///neuur /ww.unnuu.pp..// httpppp.cppppbaee cc/public// Ceteiic///eeeeeeeeeeeeeeeeeeeeee csGuidelines?
Answer: [Yes]
Justification:
We have reviewed the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work serves as foundational research for algorithmic game theory. Al- though there might be some potential social impacts on solving large-scale games, according the guidelines, believe result does not have direct connection with these issues.
Guidelines:
34

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: No such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: Does not apply.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
35

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Does not apply.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
No human subjects nor crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: No human subjects nor crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
36

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
37


Reviews:
[{"review_id": "gJkTI1wuIP", "reviewer": "Reviewer_P3Rf", "summary": "The paper offers significant advancements in understanding the efficacy of distance-generating functions (DGFs) for extensive-form games (EFGs), specifically focusing on the optimization and application of first-order methods (FOMs). Central to the study is the exploration of the weight-one dilated entropy (DilEnt) regularizer, which is proven to be optimal up to logarithmic factors for these games. Overall, the paper makes a strong contribution to the field of algorithmic game theory, particularly in optimizing computational approaches for EFGs, and sets a new benchmark for subsequent research in this area. It opens up several avenues for further exploration, particularly in refining these methods for broader classes of games and in practical, real-world settings.", "questions": "Is it possible to conduct some proof of concept experiments to validate the theoretical findings?", "limitations": "The authors discussed in their conclusions limitations and future directions.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper successfully establishes that DilEnt provides an optimal distance-generating function in terms of the diameter-to-strong convexity ratio for the strategy spaces in EFGs.\n- By developing new primal-dual treeplex norms, the authors enhance the analytical framework for FOMs in EFGs, allowing for more precise performance predictions that align with the capabilities of the Kernelized Optimistic Multiplicative Weight Update (KOMWU) algorithm.\n- The research presents a comprehensive analysis of the DilEnt regularizer's performance, including establishing new state-of-the-art approximation rates for achieving coarse correlated equilibrium in multiplayer games.", "weaknesses": "- While the paper makes substantial theoretical advancements, there are less empirical validations of the proposed methods across real-world datasets or diverse game settings, which might be necessary to fully understand the practical implications.\n- The work primarily focuses on EFGs with perfect recall and does not extensively address scenarios with imperfect recall or partial information, which could be relevant for a broader range of applications", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your feedback and your praise of our paper!\n\nWe address the two weaknesses you mentioned:\n\n- Your claim that our paper does not deal with “partial information” is wrong. The techniques of the paper apply to imperfect-information extensive-form games. You are however right that the paper focuses on the case of perfect-recall games (i.e., players that do not forget their observations). This is a standard assumption. Equilibrium computation and learning in imperfect-recall games is known to be computationally intractable.\n\n- Regarding empirical validation: you are right that we dedicated the entire paper on developing theoretical contributions. However, other work has examined the empirical performance of the DilEn regularizer (e.g., [1]), though without the theoretical understanding and machinery that we introduce in this paper to analyze its metric properties.\n\n[1] 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KuxRyQWTZg", "reviewer": "Reviewer_NLU1", "summary": "This paper studies the optimality of diluted entropy functions for online learning in extensive form games. The weighted one diluted entropy is shown to be optimal up to logarithmic factors, for which a new lower bound is also provided.", "questions": "Could you provide some hindsight on how are the treeplex, diameter-to-strong-convexity ratio of DilEnt used?", "limitations": "yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The paper studies a very relevant problem of the optimal choice of diluted entropy function, as it provides insights into the practical implementation of online learning with diluted entropy in real-world applications. The result is that the weight-one diluted entropy and the new matching lower bound is an addition to the field of online learning in games. Additionally, the new analysis of OMD, with the use of treeplex norms, is also new (to my best knowledge), and may be of separate interest for solving extensive form games.", "weaknesses": "I would suggest adding some more explanation and providing some hindsight of the proof of the theorems in the main paper, i.e. how are the treeplex, diameter-to-strong-convexity ratio of DilEnt used.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your feedback!\n\nQ: “Could you provide some hindsight on how are the treeplex, diameter-to-strong-convexity ratio of DilEnt used?”\n\nA: The ratio between diameter and strong convexity of the regularizer on the feasible set (in the case of extensive-form games, the feasible set of every player is their sequence-form strategy polytope, also known as treeplex) is a key quantity in the performance of mirror descent-based algorithms. Intuitively, the performance degrades the more the diameter is large (as there is more “space” to search over), and increases the more the regularizer is bowl-shaped (i.e., strongly convex), as the minimum of the function becomes easier to predict. Of course, there is a tradeoff between these two parameters: if the regularizer is too strongly convex, then it grows really fast, making the diameter of the set $D_\\varphi := \\max_{x \\in Q} D_\\varphi(x \\| x_1) = \\max_{x \\in Q} \\varphi(x) - \\min_{x \\in Q} \\varphi(x)$, larger. \n\nThanks for the suggestion, we will include this intuitive discussion in the revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rdntfPYZk5", "reviewer": "Reviewer_8sgN", "summary": "The paper examines Distance Generating Functions (DGFs), a framework developed for providing online learning and equilibrium-computing first-order methods for extensive-form games (EFGs). Specifically, DGFs were introduced in the literature as a form of regularization tailored to the strategy space of EFGs. Combining Online Mirror Descent with DGFs leads to first-order methods for equilibrium computation in EFGs. A DGF $\\phi$ is required to be $\\mu$-strongly convex with respect to some norm. An important quantity of interest is the ratio between the diameter introduced by the Bregman divergence induced by $\\phi$ and the $\\mu$-strong convexity constant, i.e., $\\mathcal{D_\\phi}/\\mu$. This ratio appears in the regret bounds and affects the convergence rates. Consequently, the authors investigate which DGF achieves the best diameter/strong convexity ratio. They demonstrate that a specific form of DGF, the weight-one dilated entropy (DilEnt), achieves the optimal diameter/strong-convexity ratio up to logarithmic factors out of all DGFs. More precisely, DilEnt admits an $\\mathcal{O}(\\log |V|)$ diameter/strong-convexity ratio, where $V$ denotes the set of possible pure strategies for the EFGs. Additionally, they demonstrate that combining DilEnt with the recently proposed framework of Clairvoyant Mirror Descent can lead to state-of-the-art convergence rates for computing Coarse Correlated Equilibrium (CCE) in EFGs.", "questions": "See weaknesses above.", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The DGF framework has been instrumental in designing no-regret and efficient equilibrium computation algorithms for EFGs. Consequently, I believe that characterizing the DGF that achieves the optimal diameter/strong-convexity ratio is a significant result for the game theory community. Additionally, the paper introduces intriguing technical concepts by incorporating primal-dual treeplex norms to bound the diameter/strong-convexity ratio. Finally, by combining their approach with the Clairvoyant framework, the paper presents a substantial improvement in convergence rates for computing Coarse Correlated Equilibrium (CCE) in EFGs, reducing the rate from $\\mathcal{O}(\\log^4 T/T)$ to $\\mathcal{O}(\\log T/T)$.", "weaknesses": "Despite the fact that all the presented results are interesting and introduce compelling technical ideas, I have some doubts about the main takeaway of the paper. As far as I understand, DilEnt was introduced by [1] to establish an equivalence between Mirror Descent and the kernelized approach of [2], which already achieved the $\\mathcal{O}(\\sqrt{\\log |V| T })$ regret bounds for EFGs. From this perspective, the $\\mathcal{O}(\\log |V|)$ bound on the diameter/strong-convexity ratio is somewhat expected. While I acknowledge that establishing this bound is far from trivial and technically challenging, it can also be seen as an alternative way of retrieving an already known result.\n\nThe main takeaway message of the paper might be the lower bound, which establishes that the results of [2] cannot be improved by adopting the DGF approach. If this is the case, highlighting this point would greatly benefit the paper.\n\nRegarding the improved rate for CCE through the use of Clairvoyant Mirror Descent, is the current result truly necessary to achieve this improvement? I am not entirely sure, but I have a feeling that coupling the clairvoyant approach with the previous results of [2] would result in the same improvement.\n\nThat being said, I believe this is an interesting paper, and I am willing to further increase my score if these points are addressed.\n\n\n[1] Bai et al. Efficient phi-regret minimization in extensive-form games via online mirror descent\n\n[2] Farina et al. Kernelized multiplicative weights for 0/1-polyhedral games: Bridging the gap between learning in extensive-form and normal-form games", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your feedback! \n\nQ1: “The main takeaway message of the paper might be the lower bound, which establishes that the results of [2] cannot be improved by adopting the DGF approach. If this is the case, highlighting this point would greatly benefit the paper.”\n\nA1: Thanks for the suggestions. In our opinion, however, the main takeaway of the paper is twofold. One is the lower bound, which suggests that KOMWU [2] is nearly optimal—as you said. The other, which we think is very important, is the analysis technique based on the treeplex norms. We believe that this contribution creates important analytical tooling that can be of independent interest for future research on regularization of these important combinatorial domains. As a byproduct, we are able to establish that the DilEnt regularizer achieves the near-optimal diameter-to-strong-convexity ratio for EFGs with full-information feedback. This also reconciles the more ad-hoc analysis based on kernelization (references [1,2] in your review) with the standard analysis of first-order methods and mirror descent, resolving the disconnect in the analysis.\n\n\nQ2: “Regarding the improved rate for CCE through the use of Clairvoyant Mirror Descent, is the current result truly necessary to achieve this improvement?”\n\nA2: This question is more speculative and it’s hard to know for sure. But, we are fairly confident that the new analytic tools we introduced, that are in line with the standard analysis of mirror descent-based algorithms, provide the natural groundwork for analyzing the algorithm. \nIn particular, Clairvoyant MWU uses fixed-point iterations on a map that has to be shown to be contractive with respect to some norm. The treeplex norm is a very natural candidate for extensive-form games, as we show in the paper. It does not seem immediately straightforward to replicate these results for the kernelization approach.\n\n[1] Bai, Yu, et al. \"Efficient Phi-regret minimization in extensive-form games via online mirror descent.\" Advances in Neural Information Processing Systems 35 (2022): 22313-22325.\n\n[2] Farina, Gabriele, et al. \"Kernelized multiplicative weights for 0/1-polyhedral games: Bridging the gap between learning in extensive-form and normal-form games.\" International Conference on Machine Learning. PMLR, 2022.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9cqlMt5yvd", "reviewer": "Reviewer_wj5h", "summary": "This work studies first-order methods for equilibrium computation in extensive form games (EFGs) and the effect of the regularization choice (distance-generating function). The key parameter for the performance of these methods is the ratio between the strong convexity modulus and the diameter of the regularizer. The main result is that a particular regularizer, namely the dilated entropy, is an optimal choice in terms of the aforementioned ratio. This regularizer can be used to recover prior results in EFGs such that the regret performance of Kernelized OMWU.", "questions": "1) Is there some motivation in preferring a FOM rather than kernelization? \n\n2) In the Clairvoyant OMD result, is the regret bound achieved by an efficient algorithm? Because clairvoyance requires solving a fixed-point problem, right?\n\n3) Could the results obtained by either first-order methods with DilEnt or KOMWU hold for last-iterate convergence? \n\n4) Regarding the lower bound of Theorem 5: is the result in the adversarial setting, where one player employs some algorithm and the other players decide \"in the worst case\" for the algorithm?", "limitations": "-", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The main result of the paper is essentially a toolbox for the dilated entropy (DilEnt) regularizer that can be then employed to get improved regret bounds. The main corollary of this toolbox is that running OMD with DilEnt gives the same performance as Kernelized OMWU, which employs the \"normal-form reduction\" of the EFG. I find this result interesting since it provides a nice unifying tool between prior works and the power of first-order methods.\n\nThe paper is in general well-written, some parts are a little bit dense and the notation is heavy (this is a general issue in this line of work).\n\nEssentially, the main result of the paper is a matching-performance first-order method compared to KOMWU. I think that the problem studied by the authors has a concrete motivation and the solution is nice. Hence, I believe that the paper is above the borderline for acceptance.", "weaknesses": "In terms of contribution, I believe that the main result complements well the existing literature. I do not have some concrete weakness to point out but I have a couple of clarifying questions for the authors.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your feedback!\n\nQ1: “Is there some motivation in preferring a FOM rather than kernelization?”\n\nA1: Given that FOMs have been extensively explored in the literature, they can benefit from the existing techniques. An example of this is the adoption of the COMD approach in our paper, which leads to a better theoretical convergence rate for learning CCE in extensive-form games.\nAlso, FOMs are more flexible than kernelization, in general. With kernelization, one would be restricted to (variants of) the multiplicative weights update algorithm. In contrast, our DilEnt result can be applied to any first-order method that requires a strongly convex regularizer (including adaptive-stepsize methods, mirror prox, Nesterov’s excessive gap technique, etc., which do not have a kernelization equivalent). Furthermore, the analytic tools we introduce, including the treeplex norms, are likely of independent interest for first-order methods on extensive-form strategy sets and might apply to other regularizers as well.\n\nQ2: “In the Clairvoyant OMD result, is the regret bound achieved by an efficient algorithm? Because clairvoyance requires solving a fixed-point problem, right?”\n\nA2: Yes, COMD is indeed efficient. The fixed-point problem is solved via fixed-point iteration. By proving that the fixed-point iteration steps are contractions with respect to the treeplex norm (Lemma 4.5), the fixed-point subproblem is guaranteed to be solved at $\\varepsilon$-approximation in logarithmic iterations in $1/\\varepsilon$.\n\nQ3: “Could the results obtained by either first-order methods with DilEnt or KOMWU hold for last-iterate convergence?”\n\nA3: While this paper was not concerned with last-iterate convergence guarantees, by applying our new analysis framework to the result in [1], it should be straightforward to establish last-iterate convergence guarantees with a better dependency on game size in the settings for which [1] guarantees convergence.\n\nQ4: “Regarding the lower bound of Theorem 5: is the result in the adversarial setting, where one player employs some algorithm and the other players decide \"in the worst case\" for the algorithm?”\n\nA4: Yes, the result given by Theorem 5.1 is in the adversarial setting, which exactly matches the upper bound provided in Theorem 4.4. This is the standard online learning setting in which the usual lower bounds (for example, $\\Omega(\\sqrt{T \\log n})$ for a probability simplex) are given. Lower bounds in the learning-in-games settings are widely unknown.\n\n[1] 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper advances the understanding on extensive form games. They analyze weight 1 dilated entropy regularizer used in the OMD framework can lead to state of the art results in EFGs. While this result was already established, it was done via identification of iterate equivalence between OMD with DilEnt and a Kernelized Online multiplicative weights. The paper provides a more 'standard' OMD analysis by showing that one can bound the ratio of diameter to strong convexity modulus of these regularizers. They also show this is optimal upto log factors for this setting. This is achieved via the development of appropriate treeplex norms which is interesting in its own right. They further show the use of their result by applying to a Clairvoyant OMD setting for achieving coarse correlated equilibria.

There have been a sequence of results in this area in recent times. The paper provides a nice addition to this sequence and the result as well as the techniques seem useful to the online learning and learning in games community and perhaps beyond. Overall the paper was found to be well written and the reviewers were also unanimous in acceptance. I recommend acceptance.
Decision: Accept (poster)