Comparator-Adaptive $\Phi$-Regret: Improved Bounds, Simpler Algorithms, and Applications to Games
Authors: Soumita Hait
Ping Li
Haipeng Luo
Mengxiao Zhang
Venue: NeurIPS 2025 spotlight ()
Keywords: Swap Regret
$\Phi$-Regret
Learning in Games
Primary area: theory

Abstract: In the classic expert problem, $\Phi$-regret measures the gap between the learner's total loss and that achieved by applying the best action transformation $\phi \in \Phi$. A recent work by Lu et al., [2025] introduced an adaptive algorithm whose regret against a comparator $\phi$ depends on a certain sparsity-based complexity measure of $\phi$, recovering and interpolating optimal bounds for standard regret notions such as external, internal, and swap regret. In this work, we propose a general idea to achieve an even better comparator-adaptive $\Phi$-regret bound via much simpler algorithms compared to Lu et al., [2025]. Specifically, we discover a prior distribution over all possible binary transformations and show that it suffices to achieve prior-dependent regret against these transformations. Then, we propose two concrete and efficient algorithms to achieve so, where the first one combines multiple copies of the kernelized Hedge algorithm of Farina et al., [2022], and the second one combines multiple copies of a variant of the BM-reduction [Blum and Mansour, 2007]. To further showcase the power of our methods and the advantages over Lu et al., [2025] besides the simplicity and better regret bounds, we also show that our second approach can be extended to the game setting to achieve accelerated and adaptive convergence rate to $\Phi$-equilibria for a class of general-sum games. When specified to the special case of correlated equilibria, our bound improves over the existing ones from Anagnostides et al., [2022a,b].

Comparator-Adaptive Ø-Regret: Improved Bounds, Simpler Algorithms, and Applications to Games
Soumita Hait" University of Southern California hait@usc. edu
Ping Li
Shanghai University of Finance and Economics pingleedstu. sufe. edu.
Haipeng Luo"
Mengxiao Zhang
University of Southern California haipengl pespengl@us......
University of Iowa
nengxiao-zzangguiie
Abstract
In the classic expert problem, d-regret measures the gap between the learner's total loss and that achieved by applying the best action transformation $ recent work by Lu et al. [2025] introduces adaptive algorithm whose regret against a comparator ó depends on a certain sparsity- -ased complexity measure of o, (almost) recovering and interpolating optimal bounds for standard regret notions such as external, internal, and swap regret. this work, we propose a general idea achieve even better comparator-adapee adaptive d-rrerett bound via much simpler algorithms compared to Lu et al. [2025]. Specifically, we discover a prior distribution all possible binary transformations and show that suffices to achieve prior-dependent regret against these transformations. Then, we propose concrete and efficient algorithms achieve so, where the first one learns over multiple copies of a prior-aware variant of the Kernelized MWU algorithm of Farina al. [2022b), and the second one learns over multiple copies of prior- aware variant of the BM-reduction [Blum and Mansour, 2007]. To further showcase the power our methods and the advantages over [Lu al., 2025] besides the simplicity and better regret bounds, we also show that our second approach can be extended the game setting achieve accelerated and adaptive convergence rate to ieequilibria for a class of general-sum games. When specified to the special case of correlated equilibria, our bound improves over the existing ones from Anagnostides et al. [2022a.b].
1 Introduction
Expert problem [Freund and Schapire, 1997] is of the most fundamental online learning problems, where a Iearner repeatedly hedges over d experts with the goal of being comparative to strong benchmark. More concretely, in each round f, the learner proposes distribution Pt A(d) over experts and suffers loss (p., le) where & E [0, 1]d is loss vector decided by adversary. Consider a benchmark that always applies a fixed linear transformation Φ ((d) + A(d) to the learner's strategy and thus suffers loss (ő(p:), &x) in round The regret of the learner against is then defined as Reg(ø) & DTT(P (p: (p:)), (e). that is, the difference between the learner's total loss and that of the benchmark. Given class of linear transformations 4, the learner's 's 4-regret is defined as max Reg(E) (6) [Greenwald and Jafari, 2003]. With an appropriate choice Φ, this general notion of d-rreret subsumes many well-studied regret notions the literature, such external regret, internal regret, and swap regret.
Authors listed in alphabetical order.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

While the optimal P-regret bound naturally depends on the complexity of the class Tb and different algorithms have been proposed for different d's in the literature, a recent work by Lu et al. [2025] developed comparator-adaptivy algorithm whose regret against ø depends on a certain sparsity-based complexity measure Go of Φ. almost recovering the optimal regret bounds for external regret, internal regret, and swap regret simultaneously via one single algorithm. Specifically, their algorithm achieves
Reg (0) - (V co + d) (log d))) for all ø simultaneously, where c = -min d dd .d-d.
dunir 1}. dgelr is the number of experts that are mapped to themselves by Φ, and duair is the maximum number of experts mapped the same expert by & (see Section 2 for formal definitions). The design of their algorithm, however, is somewhat complicated and uses Haar-waye wavelet-insppiee matrix features.
In this work. we significantly improve over Lu et al. [2025] by developing simpler algorithms, achieving better comparator-ddaptiv regret bounds, and demonstrating broader applications to accelerated convergence in games. Specifically, our contributions are as follows.
First, in Section 3, propose a general idea of achieving an improved comparator-adaptii regret bound (eg also the extra log d factor compared to that of Lu et al. [2025]. We achieve so by proposing a prior distribution æ over all binary and linear transformations and showing that as long as a natural prior-dependent regret bound Reg(ø) = comparator-adaptin regret bound holds.
(c d). removing both the extra Õ( ((vcyd) additive term and
holds, then the aforementioned new
While at first glance it is unclear at all how to achieve the prior-dependent regret bound above effi- ciently (since the number of all binary transformations dd), we propose two efficient approaches to achieve so thanks to the special structure of our prior. For the first approach (Section 4), we utilize and extend the Kernelized Multiplicative Weight Update algorithm of Farina et al. [2022b] and show that a certain prior-dependent kernel can be computed efficiently; for the second approach (Section 5), we develop a prior-aware variant of the classic B.M-reduction [Blum and Mansour, 2007] and learn over multiple copies of it. Both approaches are arguably much simpler than the algorithm of Lu et al. [2025].
Besides its simplicity and better regret bounds, we further demonstrate the power of our second approach by extending it to an uncoupled learning dynamic for games and achieving accelerated and adaptive convergence to -eequilibria (Section 6). Specifically, we develop an algorithm such that, when deployed by all players for broad class of N N-player general-sure games considered by Anagnostides et al. [2022c], each player enjoys a T-independent regret bound Reg(Ø) = Ocg log d + N2 log d) for all & simultaneously. Based on standard connection between $- regret and L-equilibria, this implies adaptive (maxşe4 N log d + N2 log d) /T' convergence rate to Deequilibria, simultaneously for all classes t, which is the first result of this kind to our knowledge. Moreover, when specified to the case of correlated equilibria (where & is all binary linear transformations), we improve over Anagnostides et al. [2022b] on the d-dependence and remove any polylog(T") dependence compared to Anagnostides et al. [2022a.b] (although their results hold more generally for any general-sum games). Our technique is also new and relies on the flexibility and particular structure of our second approach, which allows us bound the path-length of the learning dynamic via showing small external regret. We remark that it is highly unclear (if possible all) how to achieve similar results using the algorithm of Lu al. [2025] (or even our first approach).
Related Work We refer the reader to Cesa-Bianchi and Lugosi [2006] for detailed discussions on external regret (e.g., [Freund and Schapire, 1997]), internal regret (e.g.. [Foster and Vohra, 1999, Stoltz and Lugosi, 2005],, and swap regret [Blum and Mansour, 2007], whose formal definition can be found in Section 2. As mentioned, they all belong to the family of @-regret, a concept proposed by Greenwald and Jafari [2003] and further studied in many subsequent works such as Stoltz and Lugosi [2007]. Gordon et al. [2008], Rakhlin et al. [2011]. Piliouras et al. [2022], Bernasconi et al. [2023], Cai et al. [2024], Zhang et al. [2024] due to its generality and connection to various equilibrium concepts. However, comparator-daaptio Ø-regret bounds were only recently considered by Lu et al. [2025] as far as we know.
The concept of comparator-adaptive regret, nevertheless, is much older and has been studied under various different contexts; we refer the reader to Orabona [2019] for in-depth discussion. The algorithm of Lu et al. [2025] makes use of advances from this line of work [Cutkosky, 2018].

---

while ours uses two simpler ideas: prior-dependent external regret via the classic Multiplicative Weight Update (MWU) algorithm [Littlestone and Warmuth, 1994, Freund and Schapire, 1997] and combining multiple algorithms to learn over the learning rates via a meta MWU (an idea that has been used many prior works such as Koolen et al. [2014], Van Erven and Koolen [2016], Foster et al. [2017], Cutkosky [2019], Bhaskara et al. [2020], Chen et al. [2021].
The connection between online learning and games dates back Blackwell [1956], Hannan [1957], Freund and Schapire [1999]. Greenwald and Jafari [2003] showed that in a general-sum game, if all players deploy an online learning algorithm with sublinear Ø-regret, then the empirical distribution of their joint strategy profiles converges to a --equilibrium with the convergence rate being the average (over time) 4-regret. While d-regret is usually of order vT in the worst case (leading to 1/VT convergence rate), since the work of Daskalakis et al. 12011]. Rakhlin and Sridharan [2013], Syrgkanis et al. [2015], there has been a surge of research showing that accelerated convergence rate of order polylog(T)/T is possible in many cases by utilizing the structure of the game and certain optimistic online learning algorithms [Daskalakis et al., 2021, Anagnostides et al., 2022a,b, Farina et al., 2022a]. Our result in Section 6 adds to the growing body of this line of work and is the first accelerated convergence rate that is also adaptive in the complexity of $. Our approach also makes use of standard optimistic online learning algorithms, but existing analysis does not work directly due to various technical hurdles. We resolve them by exploiting a particular structure of our second algorithm, borrowing ideas from a two-layer framework of Zhang et al. [2022], and considering subclass of games where the sum of all players' external regret is always nonnegative (a broad class as shown by Anagnostides et al. [2022c]).
2 Preliminaries
General Notations For a positive integer n, let [rx] denote the set {1, [1,2..... nn.. Define RT to be the positive orthant of the n-dimensional Euclidean space, and Anr) _ { E RT,, >i P; = 1) to be the (n- - ---dimensional simplex. Given a finite set S, denote |S] to be its cardinality and (SS) to be the set of probability distributions over S. Given p, q E Ann), define KL q) 2 Σi= Pt log & as the KL-divergence between p and g. For matrix M E IR=x,, we denote by M. E R" the i-th row of M and M.y E IT the j-th column of M. For two matrices M1, M2 E Rmxx, define the inner product (M1, MM)) P trace (M, Mz). Let 1 and 0 be the all-one and all-zero vector in an appropriate dimension, let e be the one-hot vector in an appropriate dimension with the i-th entry being 1 and all other entries being O, and let be the identity matrix in an appropriate dimension.
Define S A to E (0, 1]dxd] Ox: E A(d), V & E [d] as the set of all row-stochastic matrices, which is also the set of all possible lincar transformations from (dd to A(d) if we treat each ø S as linear operator: <(p) o p. The subset b & {Ø {0, 1 de: E A(d). Y k E [d] C S consisting of all binary now-stochastic matrices is of particular interest. For a distribution x E ( be the probability mass of P,,
we let π (()
Expert Problem and p-regret In expert problem, the interaction between the environment and the learner proceeds for T rounds. At each round t E [T], the learner decides a distribution Pt E ((d) over the d experts and the environment decides a loss vector 4, E [0, 1]d, The learner then
receives l, and suffers loss (pc, La). Given transformation o E S, the regret of the lcarner against this & is defined as Reg(Ø) - Σi= (pr- 1 p(p)), 4,), and given a class of transformations &b S. the Ø-regret is defined as Reg( () 2 max Reg(ø) [Greenwald and Jafari, 2003].
With an appropriate choice of Φ, 4-regret reduces to many standard regret notions. For example, with +- = Exa A [1e,] Jiejaj. Φ-regret recovers the standard external regrel that competes with a fixed expert, and it is well known that the minimax bound in this case is @(VTlog d), achieved by for example the classic Multiplicative Weight Update (MWU) algorithm [Littlestone and Warmuth, 1994, Freund and Schapire, 1997]; with = Pint e [I - e,e, ege, ).. Ø-regret recovers internal regref and competes with strategy that moves all the weights for expert to expert j for some fixed and j. and the minimax bound in this case is also @(VTlog d) [Stoltz and Lugosi, 2005]; and with & 4, é-regret reduces to swap regret and competes with all possible swaps
3

---

between experts, and the minimax bound in this case is @ [Blum and Mansour, 2007, Ito, 2020] for certain regime of ' and d.²
In a recent work by Lu et al. [2025], they derive a comparator-adaptive regret bound of the form Reg (Ø) = 0 (V + d) (log d)²) for all & E S simultaneously, where cæ is certain sparsity- based complexity measure of Φ, formally defined as follows.
Definition 2.1 (Complexity measure of & from Lu et al. [2025]). For any & Db. define co & min(d- - deell d d + 1}, where d'el. the degree of self-map of o, is the number of experts i such that (b(e)) e, (equivalently, deatt trace (ø)), and dggit, the degree of uniformitty of o, is the multiplicity of the most frequent element in the multi-set {o(E)),.... (0),,,,,,,,)),,, For any & E S define co & mingeQ. Egrngley] where Q {q A(D6) E Bgg Φ).
\ Dt.
Direct calculation shows that max Go = max Co 1 and max algorithm achieves almost optimal external regret, internal regret, and swap regret simultaneously.
d, and thus their
We remark that, in fact, Lu et al. [2025] define cs. for Φ E S' \ Φ using the exact same definition as the case when o E 2g. which is rather unnatural and results in discontinuous function over S for example, a slight perturbation for a E L, with a large deell (and thus small ce) can lead to d' E S with d 0 (and thus potentially large car) ). The definition continuous and natural extension from 4, to S. It can be shown that our definition leads to strictly smaller complexity measure; see Proposition A.1 in Appendix A for more discussion.
here, on the other hand,
However, what is perhaps not realized by Lu et al. [2025] is that their bound Reg (ő)
OVec (T d) (log d)") in fact also holds under our better definition of Gp (via the same al- gorithm). The reasoning is the same as our proof for Theorem 3.3: it suffices to show this bound for 4b and then take convex combination of the bound when dealing with á E S 4.. This explains why we change the definition to this version.
One may wonder why we care about any é S after all, since the benchmark Σ (Ø(p:), G)) linear in Φ the best & from a set & is always on its boundary. The reason is that what the learner ultimately cares about is her total loss Σ/= (Pe, le) = Σ (Ø(p)), Le) + Reg(ø), and when a comparator-adaptive bound Reg(ø) is available, we should consider the ø that minimizes the sum Ei (é(pt). ()) + Reg(o), instead just Σ (δ(pt), ee), and in this case, it is totally possible that the best è is not in dg.
3 Achieving Cs DDDeeendent Regret via a Special Prior
In this section, we present a new and general idea to achieve a ca-dependent bound for Reg(o). To this end, we define prior distribution over o through the following definitions, which plays an important role in our approach.
Definition 3.1 (v-induceed distribution). Given a ntw-shcchattic matrix E S, induces a distribu- tion गे E ((4)) such that (Ø) = [a) (1he, 6x.) for all 6 E Dy
Definition 3.2 (special prior distribution R). The prior distribution π over Dy is a mixture of + 1 distributions such that
π
a Tit + widti:
(1)
2d 1=
2
d S are defined as where 1b ....,, 10441 ,..,,
11 Vk E [d], and dd+1 A d-2 I+ d(d ( I1 le d(d
(2)
d
d-
Mooe concretely, for the regime where d log d $ T S d2/2/ //lo///lo// d). For other regimes, see recent work by Dagan et al. [2024], Peng and Rubinstein [2024].
"e remark that this valid distribution since Eoso, ( = Esso, I Viy
I Ep Uig
I 1 1.

---

It is straightforward to verify that e¹ sb are indeed row-stochastic matrices. In fact, when viewed as transformation rules, each eith (for [d]) transforms all experts to expert with large probability mass of 1 - - and to other experts uniformly with the remaining mass, and similarly, gid+1 transforms each expert to itself with a large probability mass of 1 1/d and to other experts uniformly with the remaining mass. At a high-level, e) is intuitively connected to de in the definition of Co and {ı²* {K*)keja) are connected to dggii. Building such connections, prove the following main result.
S + 20s log d. Consequenty, if an algorithm Theorem 3.3. For any @ E tb. we have log( x(0) achieves
(VV (VTloo
Reg(d) -
+ B
(3)
क (
for all 6 E Do and some d-independent term B. then it also achieves Reg (ő)
=
(v(1+ co doT + B) for all & E S simultaneously. O
We defer the proof to Appendix A and give some intuition here by considering two special cases. First, consider a Φ & we know that Φ = 1e, for some E [d]] and thus (Ø) 2 zZ Tz (ő) (1 1)²² = (1/d), meaning that log(1/ 1001/((()) (x)) is of order log and consistent with Gø log As another example, consider a Φ E Iin we have Φ = I I- +
e,e] for some i * j and thus (()) 2 m (1) {1 1) āc-ι = (1 (1/dd), which means
is also of order
log d and consistent with co logd.
To see why Eq. (3) natural bound one should aim for, we recall a standard idea from Blum and Mansour [2007], Gordon et al. [2008] that reduces the Ø-regret for the expert problem to the standard (external) regret of an Online Linear Optimization (OLO) problem over Φ: if at each round the proposed distribution over experts Pt E A(d) is computed as the stationary distribution of some 6e E S (that is, Pt- - (Pe)), then we have Reg(ø) E'= Mr-o(pp), 4,) Ei (dr(pr) op:),, = Et. (o. - &, o,,,,,) which means Reg(ø) is exactly the standard regret of the sequence $1,-... ØT against fixed Φ for an OLO instance with (sPreT) as the linear loss function round l. We can solve this OLOO instance by treating as yet another expert problem with o as the expert set, in which case a bound in the form of Eq. (3) is just the standard prior-dependent regret achievable by many algorithms, such as MWU.
The caveat, of course, is that naively doing so is computationally inefficient since the size of 4, is dd, In fact, a similar concern was raised by Lu et al. [2025] as motivation for their totally different approach. However, thanks to the special structure of our prior æ, we manage to develop two different efficient approaches to achieve Eq. (3), as shown in the next two sections.
Regret comparison with Lu et al. [2025] In our two approaches that achieve Fq. (3), the term B is either OV log d) or O(VT log d), making our final regret bound essentially O( / log d).
Compared the bound o co (T d) (logd)" of Lu et al. [2025]. we have thus removed the extra ((dcdd) additive term and also the extra log d factor. When specified to standard regret notations (external/ntermaa/swws regret), our bound exactly recovers the minimax bound while theirs exhibits a slight gap.
Discussion on the optimality of ca dependency As discussed above, is clear that the dependence on Ga is tight for the standard cases of external, internal, and swap regret, since in these settings co respectively equals 1, 1, and d, matching the known lower bounds. In fact, via simple argument, one can establish a stronger lower bound showing that for any integer k E [d] and any algorithm, there exists a d-expert problem and a comparator mapping ó with cs S 1, such that Reg(o) Q D(Vcol I log co). To see this, consider the following construction. Let d experts that always incur the maximum loss of 1, while the remaining k experts follow the swap-regret lower bound instance of Ito [2020], scaled by a factor of 1/2. We define à E $,, as follows. For each non-dummy expert, á maps it optimally to another non-dummy expert (minimizing the total loss after swapping). For dummy experts, we distinguish two cases: the al algorithm selects dummy experts more than / /kT log k times, we let é map all dummy experts to single fixed non-dummy expert
experts be dummy
5

---

Algorithm 1 MWU over 4, with prior π
Input:
learning rate 7) > 0 and prior distribution defined in Definition 3.2. Initialize qi as for t = 1,2.... do
Propose d, = Eg [o] E S and receive loss matrix pel, [0, 1]
Update 4t+1 such that (+) x (:()) exp (-1) (d. (olp)()))
(so that dggit 2 d - k); otherwise, each dummy expert maps to itself (so that deall 2 d k). In both cases, we have co. S k + 1.
In the first case, the regret satisfies Reg(ø) 2 1 IkT k, since whenever the algorithm chooses dummy expert it incurs loss while ((e,) incurs loss at most 1/2. In the second case, Reg(ø) corresponds to the swap regret of the algorithm on a k-expert problem that lasts for at least ' VkT log rounds. Because this instance follows the lower bound construction of Ito [2020], we again obtain Reg(ø) 2 S2( (2(VkTlo log k). This shows that the dependence on Co in our upper bound is tight.
First Approach: Learning over Multiple Kernelized MWU's
In this section, we introduce our first approach to achieve Eq. (3). As mentioned, based on standard analysis (see e.g., [Freund and Schapire, 1999]), simply running MWU (Algorithm 1) with expert set P, a fixed learning rate >> O, and our prior distribution æ defined in Eq. (1) to get q: E (())) and outputting the stationary distribution of Eg [o] already gives Reg(ø) < KL(g.z) +nI for any & E S "
and 9 Qo (recall Qa defined in Definition 2.1), which further implies Reg(ø) log(1/=(0)) r/T for any Ø 4.. With the "optimal tuning" of r7. Eq. (3) would have been achieved. However, there is no such fixed "optimal tuning" " since we require the bound to hold for all ø simultancously. and different é might lead different optimal tuning. We will first address this issue using a simple idea, before addressing the other obvious issue that naively running MWU is computationally inefficient.
Learning the learning rate via a meta MWU While there are many different ways to handle the aforementioned issue of parameter tuning (see e.g., Luo and Schapire [2015], Koolen and Van Erven [2015]), we resort the most basic idea of learning the learning rate via another meta MWU, which is important for resolving the computational inefficiency later, see Algorithm 2 for the pseudocode. Specifically, the meta MWU learns over and combines decisions from a set of 2[log2 df base learners, the f-thh of which is an instance of MWU (Algorithm 1) with Icarning rate Th = /22/T. This ensures that the optimal learning rate of interest always lies in [M, 27p. for certain h. At each round i, the meta MWU maintains distribution wt over all base learners. After receiving di. the expected transformation matrix from each base learner Bn, the meta MWU computes the weighted average of them using wy and proposes pt the stationary distribution of this weighted average.* 4 Then, after receiving the loss vector f,, the meta MWU constructs the loss fr,,, & (Ø) ( for each B, and updates its weight wi via an exponential weight update. Finally, the meta MWU sends the loss matrix Pel, to each base learner B,. is straightforward to prove the following result.
Theorem 4.1. Algorithm 2 guarantees Reg(ø) = O (VTVLL( σ) + VT log log d) for any & E S and q E Qs Consequently, it also guarantees Eq. (3) with B /T log log d and thus Reg(ø)
O ( +( dyT + log log d) for any &e E S.
The bound in terms of / /TKL-(q .T) is stronger than what we need in Eq. (3), and using this stronger version in fact also allows us to additionally obtain the near-optimal e-quantile regret bound of order O( T (1/s) + TTllog log d) when competing with the top e-quantile of experts [Chaudhuri et al., 2009]; see Theorem B.3 for details.
'We remark that it is important to use the stationary distribution of the weighted average of df but not the weighted average of the stationary distribution of of

---

Algorithm 2 Meta MWU Algorithm
Initialization: Set 77 log logd M 2 2[1og2 d], and w1 J 1 E A(M); initialize M instances
of Algorithm 1 (or Algorithm 3) (B / with the learning rate for Bi, being n7 /2h / for / = 1, ... 1,2..... ,
Receive of = of [0] from B₁ for each h E [M]] and compute oi = k== Wr,n
Play the stationary distribution pa of Φe (that is, pt (p(p)) and receive loss Es.
Update w such that W1+1, We,h exp (-ner,)) where Ei = (Øf pel,) for each h E [M]
Send loss matrix pili to B₁, for each h [M].
Algorithm 3 Kernelized MWU with non-uniform prior
Input: learning rate v) > O and prior distribution æ (Definition 3.2); initialize B1 = 11 E Rdxdd for / 1,2, do
Compute E S such that (ér)st 1 K(B,,11 K(B,,11--xe))
((B,,11')
Receive pell and update Bi+1 E gdxd such that (Bt+1) (Bil exp(-n(pel) )a).
Efficient Implementation of Algorithm via Kernelization To address the computational ineffi- ciency of Algorithm 1, we take inspiration from Farina et al. [2022h] that shows that Algorithm 1 with uniform prior can be simulated efficiently as long as a certain kernel function can be evaluated efficiently, and extend their idea from uniform prior non-uniform prior. Specifically, propose the following prior-dependent kernel function.
Definition 4.2 (kernel function). Define kernel KBB, = Exeer ( IK Big Aig for any B, A E IRdxd
We then show that this kernel function can be evaluated efficiently thanks to the structure of our prior and consequently the key output de in Algorithm (required for Algorithm can also be computed efficiently via the Kernelized MWU shown in Algorithm 3.
Theorem 4.3. The kernel function K defined in Definition 4.2 can be evaluated in time O(d)). Moreover, the de matrix computed by Algorithm and Algorithm are exactly the same.
This theorem already shows that each iteration of Algorithm can be implemented in time (d since it requires evaluating the kernel 2d times. However, by reusing some intermediate statistics that are common in these 2d kernel evaluations and the special structure of the stochastic matrices vii ...., gid+1 defined in Eq. (2), we further speed up the algorithm such that each iteration takes only (d time, making our algorithm as efficient as those by Blum and Mansour [2007], Lu et al. [2025]; see Appendix B.3.2 for details.
Combining Theorem 4.3 and Theorem 4.1, we have thus shown that Algorithm is an efficient algorithm with regret Reg(ø) = ((1(1 + cs log d)T + /T log log d) for all simultaneously.
5 Second Approach: Learning over Multiple BM-Reductions
In this section, we introduce our second approach to achieve Eq. (3) using prior-aware variant of the BM-reduction [Blum and Mansour, 2007]. As a reminder, BM-reduction reduces swap regret minimization to d external regret minimization problems, each with different scaled loss vector in each round, and achieves Reg(ø) < d'oogd + r/T' when each base external regret minimization algorithm is MWU (over (d) with learning rate 7j. Given prior π A(*,), is natural to ask whether a variant of BM-reduction can achieve Reg(ø) < log(1/=(a)) + 1yT, replacing d log d with log(1 / ( (.)). We first show that this is indeed possible, but only when is vi-induced distribution for some E (Definition 3. I), and the only modification needed is to let the i-th MWU subroutine use the prior th. e A(d). See Theorem C.I in Appendix C for details.
7

---

Given that our prior of interest is mixture of d + distributions induced by vt ..... eid+t (Defini- tion 3.2) and also the same issue that a fixed learning rate nj cannot be adaptive different comparator 6, we propose a natural meta-base framework that is very similar to Algorithm 2 and learns over both different v and different learning rates. Specifically, we maintain (d + 1)M (where M is again 2 [1og2 d) base-learners B indexed by & E [d 1] and h E [M]. Each base-learner Bg., is an instance of the prior-aware BM-reduction Algorithm with prior v and learning rate /24/T. With this set of base learners, the rest of the algorithm is exactly the same as Algorithm 2. and we thus defer all details to Algorithm 7 in the appendix. The only crucial point (similar to Footnote 4) is that, even though the standard BM reduction directly outputs the stationary distribution of a stochastic matrix, it is important here that we first take a convex combination of these stochastic matrices and then compute its stationary distribution, instead of using the convex combination of stationary distributions.
The following theorem shows that Algorithm 7 satisfies Eq. (3) with B VTlog d. Theorem 5.1. Algorithmm satisfies Eq. (3) with Vollog Consequently, it guarantees Reg(ø) O ( (V(++ cs log d)T + VTlog d) for any o E S.
Even though the guarantee of this second approach is slightly worse than that of Algorithm (but still better than Lu et al. [2025]), in the next section, show that its particular structure is erucial in extending our results to games.
Applications to Games
In this section, we discuss how to extend Algorithm 7 achieve accelerated and adaptive t- equilibrium convergence in N-player general-sum normal-form games. We first introduce necessary background on the connection between online learning and games. Consider an N-player general-sum normal- game, where each player E [N] has finite set of actions [d]. For a given joint action profile a = (a1..... ...., AN) ) E [d] & A, the loss received by player is given by some loss function g(x) A + [0, 1]. For notational convenience. denote a a- = (a1...., an-1, aa+1,.... an). Given 4 x 2h where each 4, S S is a set of action transformations for player n, the corresponding (approximate) @-equilibrium is defined as follows.
Definition 6.1 (s-approximate @--quilibrium). We call a distribution p E (AA) over all all joint action profiles an s-approximate D-equilibrium for all players n. E [N] and all o E 2n, Ea-p! (a)) S (a- ())((()),, a ) + e. When & = 0, we call a @-equilibrium.
When 2 Exxt for all n, --equilibrium reduces to Coarse Correlated Equilibrium (CCE), and when p, = d for all n, --equilibrium reduces to Correlated Equilibrium (CE).
Approximate d-equilibrium can be found via the following uncoupled no-regret learning dynamic.
At each round E [T], each player n proposes Pi (n) E (d)), forming an uncorrelated distribution
P: (p) ,..,,,.... (N)), Ea-p, [e(a) (a. a [. for any E [d]. The Iegreet for player is then defined as Reg,. & max Reg, (Ø) max ΣT (p(") o(p(")), e(")), and denote the special case of external regret for t = T as Rog The following proposition from Greenwald and Jafari [2003] builds the connection between no- no- --egret learning and convergence to Ø-equilibrium.
and receives a loss vector e(a) E 1jd as the feedback where & -
Proposition 6.2 ((Greenwald and Jafari, 2003]). The empirical distribution of joint strategy profiles, that is, uniform over .i..... .rr is maxnely] (Rgg)) approximate 4-equilibrium.
While one can apply our Algorithm 2 or Algorithm 7 directly for each player to obtain 1/VT convergence rate that is adaptive to the complexity of Φ we are interested in achieving accelerated ( (T) convergence rate that has been shown possible in recent years for canonical 6. For example, for CCE, Daskalakis et al. [2021], Farina et al. [2022a], Soleymani et al. [2025) show the following polylog(T) bound on Rog Ext respectively: ON log d log T), O(N T), ONN log? dlog T);
$ For notational conciseness, we assume that the action set size is the same for all players, but our analysis be directly extended to games with different action sizes.
8

---

Algorithm 4 Meta Algorithm for Accelerated and Adaptive Convergence in Games
Input: learning rate 7mm 0, correction scale À > 0
Initialize: d + 2 base learners _,.... B8+2, all with learning rate 1j = 16N For & < d + 2, Bk is an instance of Algorithm 8 with prior w and SubAlg being OMWU (Algorithm 9); Ba+2 is an 1
instance of Algorithm 9 (with uniform prior); set w1 2d ................................ 2 4' $ A(d+2)
for f 1, 2....... ............ T do
Receive of E S from base learner By for each & E [d (d+2) 2].
Compute e IR++2 where Ct = >1 Pi-211 2l [t 2 3) and j (pr).
Compute m² E Rd+2 where mi.k - Pr- -p--P--1l--
1(t 2 2} for [d+ + 2].
Compute Wi such that Wt, or Wi, exp( (-pm (mi, +,x)).
Compute di Dtt1 d+2 te and play stationary distribution pt satisfying Pt de(re).
Receive l and compute et" Rd+2 where fixx = = for E [d 2
Update We+1 such that 1, . x Wi. exp(-Imm (fr, + c.,))).
Send pel, to B5 for k E [d + 1] and send & to Bat2.
for CE, Anagnostides et al. [2022a,b] show the following bound on Reg,; O(N log d log 7) and (NN log T") Our goal is to achieve similar fast rates while at the same time being adaptive the complexity of 4, and we successfully achieve so, albeit only for the following class of games.
Definition 6.3 external-regret game if E Reg. Ext 2 always holds.
games). We call a game nonnegative-social.
This class was explicitly considered in Anagnostides al. [2022c] and contains broad family of well-studied games, including constant-sun polymatrix games, polymatrix strategically zero-sum games, and general and non-trivial. We are unable to deal with general games using ideas from aforementioned recent work due the two-layer nature of our algorithms. In fact, even when considering only this subclass of games, it is unclear to us how to make our first approach discussed in Section 4 or the algorithm of Lu et al. [2025] work, and we have to resort to extending Algorithm 7. In the following, we discuss how we design our algorithm (shown in Algorithm 4) based on similar ideas of Algorithm and what extra ingredients are needed.
-uassivoovgaeaeeeaaeeeeee games. Therefore, we believe that our results are still very
Base learners Compared to Algorithm 7, there are several differences in the base learner design. First, while we still maintain base learner B& (Algorithm 8) for each prior & we do not need to maintain different copies of it to account for different learning rates, since in the end we will use a fixed constant learning rate, similar to prior work on accelerated convergence. Second, inspired by a long line of work showing that optimism accelerates convergence, for each B* we replace its subroutines from MWU to Optimistic MWU (OMWU) [Rakhlin and Sridharan, 2013, Syrgkanis et al., 2015] (Algorithm 9). Finally, besides these d + 1 base learners, we additionally include a base learner Ba42, an instance of OMWU (Algorithm 9) with a uniform prior, to explicitly minimize external regret. This last modification is in way most crucial to our analysis, since it allows us to utilize the nonnegative-socias wow.sociiil-eeteea--rrreeeeee property and show that the path-length of the entire learning dynamic is T T-independent and of order O(N log d) only; see Appendix D.3 for details.
Meta learner In addition, there are also several modifications to the meta learner compared to Algorithm 7. First, similar to the base learners, instead of using MWU, we apply OMWU to compute wt and the auxiliary @; (Line 5 and Line 8 of Algorithm 4). Importantly, the update of w, uses a "predictive loss vector" my such that mī,, = (ot . E (Line 4). The fact that m² is not simply the previous loss vector f 1. a canonical setup for OMWU, is important for the analysis, as already shown in Zhang et al. [2022] under a different context. Second, also inspired by Zhang et al. [2022], Zhao et al. [2024], in order to aggregate the guarantee for all base learners, in both the update of wi and w. we propose to add a stability correction term e, (Line of Algorithm 4), which guides the meta algorithm to bias toward the more stable base learners, hence also stabilizing the final decision. While the idea is similar, the specific value of Cr is tailored to our analysis and takes into account not only the stability of of from the base learner B& but also the stability of the stationary distribution pt. Our main result is as follows.
9

---

Theorem 6.4. For an N --llayer normal-form general-sum game satisfying Definition 6.3, if each player n E [N] runs Algorithm 4 with 7m GAN and
N. then we have Reg, (6)
Oc logd + N² log d) and Regn Ext = O(N log d) for all n E [N]. Consequently, the uni- form distribution over their joint strategy profiles is an O N Mlogd -approximate CCE and also an
maxne(N) og N log d N2 log
approximate & de-quillirrum. simultaneously for all 4 - CSN..
To our knowledge, our result achieves the first adaptive and accelerated 4-equilibrium guarantee. For the special case of CCE, the rate O T matches that of OMWU (for nonnegative-sociilleettme regret games), and for CE, is unclear at all what better results one can obtain for nonnegative-social external-regred games than those rates from [Anagnostides et al., 2022a,b] for general games. If we compare their bounds ours, since max Co d in this case, improve over Anag- nostides al. [2022b] on the d-dependence and remove any polylog(T) dependence compared to Anagnostides et al. [2022a.b]. One disadvantage of our results is the additive term of N22 log d for Ø-equilibrium other than CCE. Removing this term is an interesting future direction.
7 Conclusion and Future Directions
In this work, significantly improve recent work by Lu et al. [2025] regarding comparator adaptive Q-regret, by developing simpler algorithms, better bounds, and broader applications to games. The most interesting future direction is improve results for games, especially to remove the requirement on nonnegative social external regret. The idea of high-order stability from Daskalakis et al. [2021], Anagnostides et al. [2022a] might be useful, but appropriately combining this idea with our approaches requires further investigation. For the expert problem, it is also interesting to derive comparator-adaptive Ø-regret with respect to other complexity measure of the comparator.
Acknowledgement HL thanks Shinji Ito for initial discussion on this topic. He is supported by NSF award 1943697
References
Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Noah Golowich, and Tuomas Sandholm. Near-optimal no-regret learning for correlated equilibria in multi-player general-sum games. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 736-749, 2022a.
Ioannis Anagnostides, Gabriele Farina, Christian Kroer, Chung-Wor Wei Lee, Haipeng Luo, and Tuomas Sandholm. Uncoupled learning dynamics with o(log t) swap regret in multiplayer games. Advances in Neural Information Processing Systems, 35:3292-3304, 2022b.
Ioannis Anagnostides, Ioannis Panageas, Gabriele Farina, and Tuomas Sandholm. On last-iterate convergence beyond zero-sum games. In International Conference on Machine Learning, pages 536-581, PMLR, 2022c.
Martino Bernasconi, Matteo Castiglioni, Alberto Marchesi, Francesco Trovo, and Nicola Gatti, Constrained phi-equilibria. In International Conference on Machine Learning, pages 2184-2205. PMLR, 2023.
Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit. Online linear optimization with many hints. Advances in neural information processing systems, 33:9530- 9539, 2020.
David Blackwell. An analog of the minimax theorem for vector payoffs. Pacific Journal of Mathe- matics, 6(1):1-8, 1956.
Avrim Blum and Yishay Mansour, From external to internal regret. Journal of Machine Learning Research, 8(6), 2007.
Yang Cai,, Constantinos Daskalakis, Haipeng Luo, Chen- Yu Wei, and Weiqiang Zheng. On tractable 4-cquilibria in non-concave games, Advances in Neural Information Processing Systems, 2024.
10

---

Nicolo and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Kamalika Chaudhuri, Yoav Freund, and Daniel Hsu. A parameter-free hedging algorithm. Advances in neural information processing systems, 22, 2009.
Liyu Chen, Haipeng Luo, and Cuen-Yu Wei. Impossible tuning made possible: A new expert algorithm and its applications. In Conference on Learning Theory, pages 1216-1259, PMLR, 2021.
Ashok Cutkosky. Algorithms and Lower Bounds for Parameter-free Online Learning. Stanford University, 2018.
Ashok Cutkosky. Combining online learning guarantees. In Conference Learning Theory, pages 895-913. PMLR, 2019.
Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. From external to swap regret 2.0: An efficient reduction for large action spaces. In Proceedings of the 56th Anmual ACM Symposium on Theory of Computing, pages 1216-1222, 2024.
Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. Near-optimal no-regret algorithms for zero-sum games. Proceedings of the twenty-secon annual ACM-SIAN symposium on Discrete Algorithms, pages 235-254, SIAM, 2011.
Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. Advances in Neural Information Processing Systems, 34:27604-2787 2021.
Gabriele Farina, loannis Anagnostides, Haipeng Luo, Chung- Lee, Christian Kroer, and Tuomas Sandholm. Near-optimal no-regret learning dynamics for general convex games. Advances in Neural Information Processing Systems, 35:39076-39089) 2022a.
Gabriele Farina, Chung- Wei Lee, Haipeng Luo, and Christian Kroer. Kernelized multiplicative weights for 0o1-polyeedral games: Bridging the gap between learning in extensive- form and normal-form games. In International Conference on Machine Learning, pages 6337-6357. PMLR, 2022b.
Dean P Foster and Rakesh Vohra. Regret in the on-line decision problem. Games and Economic Behavior, (91-7)):733 1999.
Dylan Foster, Satyen Kale, Mchryar Mohri, and Karthik Sridharan. Parameter-fin free online learning via model selection. Advances in Neural Information Processing Systems, 30, 2017.
Yoav Freund and Robert E Schapire. A decision- application to boosting. Journal of computer and system sciences, 55(1):119-139, 1997.
generalization of on-line learning and an
Yoav Freund and Robert E Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1-2):79-103, 1999.
Geoffrey Gordon, Amy Greenwald, and Casey Marks. No-regret learning in convex games. In Proceedings of the 25th international conference on Machine learning, pages 360-367, 2008.
Amy Greenwald and Amir Jafari. general class of no-regret learning algorithms and thee-theo equilibria. In Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLI/Kernel 2003, Washington, DC, USA, August 24-27, 2003. Proceedings, pages 2-12. Springer, 2003.
James Hannan. Approximation to bayes risk in repeated play. Contributions the Theory of Games, 3(2):97-33,, 1957.
Shinji Ito. A tight lower bound and efficient reduction for swap regret. Advances in Neural Information Processing Systems, 33:18550-1855 2020.
Wouter M Koolen and Tim Van Erven. Second-order quantile methods for experts and combinatorial
games. In Conference Learning Theory, pages 1155-1175. PMLR, 2015.
11

---

Wouter M Koolen, Tim Van Erven, and Peter Grünwald. Learning the learning rate for prediction with expert advice. Advances neural information processing systems, 27, 2014.
Nick Littlestone and Manfred Warmuth. The weighted majority algorithm. Information and computation, 108(2):212-261, 1994.
Zhou Lu, Y Jennifer Sun, and Zhiyu Zhang. Sparsity- interpolation of external, internal and swap regret. arXiv preprint 25ti::25020044433 2025.
Haipeng Luo and Robert E Schapire. Achieving all with no parameters: Adanormalhedge. In Conference on Learning Theory, pages 1286-1304. PMLR, 2015.
Jeffrey Negrea, Blair Bilodeau, Nicolò Campolongo, Francesco Orabona, and Dan Roy. Minimax optimal quantile and semi-adversarial regret via root-logari regularizers. Advances in Neural Information Processing Systems, 34:26237-26249 2021.
Francesco Orabona. A modern introduction to online learning. arXiv preprint arXiv: 1rXiv:1912.13211 2019.
Binghui Peng and Aviad Rubinstein. Fast swap regret minimization and applications approximate correlated equilibria. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1223-1234, 2024.
Georgios Piliouras, Mark Rowland, Shayegan Omidshafiei, Romuald Elie, Daniel Hennes, Jerome Connor, and Karl Tuyls. Evolutionary dynamics and phi-regret minimization in games. Journal of Artificial Intelligence Research, 74:1 125 1158, 2022.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Beyond regret. In Proceedings of the 24th Annual Conference on Learning Theory, pages 559-594. JMLR Workshop and Conference Proceedings, 2011.
Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. Advances in Neural Information Processing Systems, 26, 2013.
Ashkan Soleymani, Georgios Piliouras, and Gabriele Farina. Faster rates for no-regret learning in general games via cautious optimism. In Proceedings of the 57th Annual ACM Symposium on Theeor of Computing, 2025.
Gilles Stoltz and Gábor Lugosi, Internal regret in on-line portfolio selection. Machine Learning, 59: 125-159, 2005.
Gilles Stoltz and Gábor Lugosi. Learning correlated equilibria in games with compact sets of strategies. Games and Economic Behavior, 59(1): 2007.
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.
Tim Van Erven and Wouter M Koolen. Metagrad: Multiple learning rates in online learning. Advances in Neural Information Processing Systems, 29, 2016.
Brian Zhang, Ioannis Anagnostides, Gabriele Farina, and Tuomas Sandholm. Efficient --regret minimization with low-degree swap deviations in extensive-form games. Advances in Neural Information Processing Systems, 37:125199 17:125192-125225 2024.
Mengxiao Zhang, Peng Zhao, Haipeng Luo, and Zhi-Hua Zhou. No-regret learning in time-varying zero-sum games. In International Conference on Machine Learning, pages 26772-26808. PMLR, 2022.
Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Adaptivity and non-stationarity: Problem- dependent dynamic regret for online convex optimization. Journal of Machine Learning Research, 25-98):1-52, 2024.
12

---

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:
See abstract and the contribution paragraphs in Section 1.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: See Section and Section for the discussion on the limitations.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
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?
Answer: [Yes]
13

---

See Section 1, Section 2, and Section 6 for the assumptions. See Appendix for complete proofs for all our theoretical results.
Justification:
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 be complemented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: This paper is eecoretic-focueed and does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe 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., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
14

---

Answer:
[NA]
Justification:
This paper is theoretic- and does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
www.sssssslllooooooooooooooooooo iilyyyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" 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 NeurIPS code and data submission guidelines (https: / //iips.cooo wttpccccppppcpeeeececccccccccctc /ttpa////iiieee/eeeuuubiiiiiii /Codeeeooiissseeeeeee
cetpaubmmsssoonnii wsiinnoll onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If 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 possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper is theoretic- and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: This paper is theoretic-focused and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
15

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
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 exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper is theoretic- and does not include experiments.
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 compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http///eerri..eeee
Answer: [Yes]
Justification:
The research conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work is theoretical, and we do not foresee any negative ethical or societal outcomes.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact 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.
16

---

The conference expects that many papers will be foundational research and not tied 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 as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This work is theoretical, and we do not involve data and models.
Guidelines:
The answer NA means that the paper poses 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This work is theoretical, and existing assets are involved in this paper.
Guidelines:
The answer NA means that the paper does 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 is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com 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 it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset'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: This work is theoretical, and new assets involved in this paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel 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 is 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: This work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
This work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor 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.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
18

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: (https://nett http://rpss.cc/oofeeeeeeeeeeeeee ccc.ooooeeeeeccce//22///111 for what should or should be described.
19

---

A Omitted Details in Section 2 and Section 3
As mentioned, Lu et al. [2025] define oo as min(d dgelt d%d + 1} for all Φ E S, while our definition for @ E S \ P is different. The following shows that ours is strictly better.
Proposition A.1. For any & E S, we have co. I min - diett, d - dunif + 1). Moreover, there exists S such that co = (11 and min(d d d damif 1 ((d).
Proof of Proposition A.I. Since
c+ min Eggolcr]] min Bornng [min d 9EQs
qunit + +1]
rEQu
S min min (Ex (Ey - dagh) Egr- [d - dunif + 1}} gEQu
min min Ey - dest)
min By [d - dunif + 11}
qEQu
qEQo
=minfd - trace (1) ,
max Egrnnn (62g + 1}, qEQo
it suffices to prove d'lll < trace (6) and demai I max (ol separately. First, by the definition of delr it directly follows that delti S trace (Ø)
Second, we construct distribution p E ((+)) such that -vver p()') 'o' and show that Eør Eb, p())) 2 damif, which in turn implies that maxgeQ, TEggin (dug 2 dunif Suppose that the most frequent element in (ō(e1), ... o(ea)) is E A(d) and o(e,) = for all j E A S [d] with |A|= dumii Then, can write o as Φ Σ q00, where di(e,) e; for all j E A and (e(e) ((e,) for all j E A. This guarantees that chani 2 damit, Furthermore, let Φb; = Eofe,, pi(o)) of be any convex decomposition of d;, and note that for any of in the support of ps. we must have d((e;) = e; for all j E A, meaning that dami 2 dz for d:
Now we have constructed a convex combination
d
d Σ
Σ
a. p.(: of
i=1
6/
and consequently,
d pmil Σ
quiil
Σ qi P:(
Junif max Egr [dunit]
QEQ.
i=1
i=1 MED.
This proves that dgnif < maxgeQs Eiging (dgoif. Combining with Nelf trace (Ø), we have shown Co I min(d delf d
damir + 1}.
Moreover, the complexity measures and min(d - dzell ,d damir + 1} can differ significantly in some cases. For example, when ái is a row-stochastic matrix with all diagonal entries equal to
1 -- for small e > 0 (implying each row's off-diagonal entries sum to E), trace (Ø1 ) is (1 e)d while dell is O. Similarly, when d2 = (1 4-e) =) 1a ee + al, it can be verified that dunif 1 and maxgEQss Engr~g(dd = (1 e)d + e = d- (d 1)e. With e < J. we have co = 0(1) and min(d- - dretf, d dunif 1 = ((d) for o = -1.02. Φ2.
Next, we prove Theorem 3.3.
Proof of Theorem 3.3. First, for Tgs+1, we have for any @ E L
d
d drc
1
Tiud (Ø)
d(d
1)
gell
1
add
20

---

which leads to
log
S 2(d dellt log + 1,
π gg (6)
since -d log (1- 2) < -dlog (1 - j) I 1 for d 2 2. Then, for Φ E Lb, assume that the most
frequent element in the set
,((aa)) is Cr. It holds that
%
Tea Ter(() (Ø)
1 d
d(d - 1)
%
(2(d-
which leads to
log
$ 2(d damit) log d + 1,
(5)
Tal (Φ)
since -dynif log (1 - 2) S - ldlog (1 - 2) I for d 2 2. Using the definition of a in Definition 3.2
and combining Eq. (4) and Eq. (5), we have
log (Φ)) min log 1
1
Twat: (Ø) log
2d T (Ø)
< min {2(d dzull) log d + 1 + log 2, 2(d - dzaul log d + log(2))
< 2 min(d dell d 1} log 2.
(6)
This completes the proof of the first statement that log =())
S 2 + 2cs log
Next, we prove that Reg(o) o (11 + c. log d)T +B) for all Φ E S when the condition Eq. (3)
holds. Fix a row-stochastic matrix o S and let E Qa be such that Gp Egr~glerr] By linearity
of Reg(() in Φ, we have Reg(ø)= = Eg/ng/ Reg( (d')), and thus
1
Reg(d) Eggng
Tlog
B
(by Eq. (3))
T(Φ)
Eg ~a
T (2car log d + +2) B
(by Eq. (6)
T (2 E. log d + 2) +
(by Jensen's 's inequality)
o (VL djT B)
This completes the proof.
B Omitted Details in Section 4
In this section, we show the omitted proofs in Section
B.1 Proof of Theorem 4.1
First, we provide the general form of vanilla MWU for an arbitrary and finite action space A in Algorithm 5. The following result is well-known for MWU, and we provide proof for completeness.
Lemma B.I. Algorithm ensures that for any comparator g E A(AA), we have
T
W q, la) < (L,9, +
Σ
||e.112.
11
21

---

Algorithm 5 MWU
Input: learning rate v) > finite action space A; prior distribution 21 A(A).
for / 1,2.... do
Play Ty and receive loss & E [0, 1]
Update x++1 such that 2,, 3a, exp (-nles) for all E A.
Proof of Lemma B.I. We aim show that for all & [2].
(x, q, le) (KL((, KL(9,3(41) KL(Te, Ft+1))-
Note that the update rule of MWU implies that 24+1, Exca He,s expl (xp()))e,)) T1. Direct calculation shows that
3a. exp(-1p4.. -1f.s))
with prior distribution
KL 21) KL Ie+1) 1 + (L 2(+1)
7
(1t 4z) log It,i 34+1,1
"7 iEA
(1tt5 9i)
le,i log 7
1
Eans aes exp( (osp(-m(ss))
JEA
(x: le)
Summing Eq. (7) for all t E [T'], we obtain that
1 T
Σ (xe - q, l.)
(KL( - KL(g, x142)) + Kl(s)
(8)
"
Next, we bound KL 2141) as shown below.
(Z
Σ Fe,i log Zt,t
Iz41,
Σ iEA
pp, + Ne,s log
Σ
It expl (xpp((n(ss)
jEA
Σ
t + Dz, log
Σ jEA
Itis (1 nles +1 :rp((.))
(since exp(-x) 5 +x2 for -1)
Σ
gr,ile,i x1,i
1 1- Σ
Figle. + +1² Σ rns e2
jEA
jEA
< Teiilei - 11 Σ
Ttgles +1²
(since log(1 + x) S x for all x)
iEA
JEA
jEA
< 1/ 12ele
Substituting this Eq. (8) and using the fact that KL divergence always non-tegateve, we get,
T
KL (g,
T
(c
ke)
+
1ell1...
n
The following lemma proves the statement Section that the optimal learning rate interest always lies in (m,. 27)a] for certain & [M], where M 2 2|oog, d].
22

---

Lemma B.2. For any Φ E S and E Qs. there exists h E [M], such that
KL(g,s)
max
S 27Th.
Proof of Lemma B.2. For any & E S and E Qs. we have (L( = E ((6') log a
)()) S
Evet, ((0)) log x()) I log mingree, =(#) 2 2d log + where the last inequality follows from
the fact that mingre Ed, T(d) 2 mingred. Tyati (0) 2 ((d-1)) Therefore, we have
min 2 = 2 max (KI 2) - 2d d + S d² = 22 logg d AE[M
max 2 M
and thus, there exists an h E [M], such that S max
{
kL T
21mh-
Now, we provide the proof of the adaptive t-regret bound attained by the Meta MWU algorithm (Algorithm 2) in Section 4.
Proof of Theorem 4.1. Since Pt is stationary distribution of de. have Reg(Ø) E (p: - Lp) = Eis (Ør(p:) o(p.). (,) = Ei= (Ø. - o, prl.) Further using the definition Φ, from Algorithm 2, we can express Reg(Ø) as the sum of the base and meta algo- rithms' regret as follows:
T
M
Reg(ø)
wi - PEET
Σ (wi- e (t)) +
where GrA = P. ofle e [0, 1] and h [M] is the index of arbitrary base learner to be specified.
Regret of the meta MWU algorithm is bounded Σ (wr ene (r) s O (VTlog log d) from Lemma B. since the prior is the uniform distribution over the log, dl base algorithms.
Regret of the base MWU algorithm B₁ is Σ (0f G. p.(.)
KL(g.m) + 7h- T for any dx-
q E Qs based Lemma B.1 and Algorithm 1. Choosing h* according to Lemma B.2, get ( o, peeT) & 3/TKL T) 2/27. Thus, Algorithm 2 achieves Reg(ø) TKL q. T) + log log for all Φ E and e Qp.
By selecting q to be one-hot vector that puts all weights on Φ. we obtain Eq. (3) with B O ( log log d) for any ò E dg. Combining with Theorem 3.3, we prove the desired bound of Reg(Ø) O (V(1+ cs log dyT + /Toog log d for all & S.
B.2 Quantile Regret
In this section, show the near-optimal e-quantile regret bound promised by Algorithm 2. The e-quantile regret [Chaudhuri et al., 2009] is defined as the difference between the cumulative loss of the learner and that of the [ed] -th best expert, where E [1/d, 1). Let is be the [ed]] -th best expert. Then, the e-quantile regret is calculated as:
Reg.
Σ (p. 4
Σ
Ees
Negrea et al. [2021] prove the minimax bound for e-quantile regret to be O ( (vTlog that our Algorithm achieves a near-optimal rate for quantile regret using Theorem 4. and ideas similar to Remark 9.16 of [Orabona, 2019].
!). We show
23

---

Theorem B.3, For all e E [1/d, 11. Algorithm guarantees
(VTlos + VT log
Reg. 0o
Proof of Theorem B.3. We order the experts in increasing order of their cumulative losses, Let be the probability distribution over these d experts with probability mass Ted on the first [ed] experts in the ordered list and on the remaining experts. Let 6 1q.- i.c., each row of oe is 9. We can also express it as E/= (e, ), convex combination of binary swap matrices, Therefore, it can be regarded as distribution over the set {1e] .................... ].
Next, consider the probability assigned by the swap matrices in this set. For all [d] <(le]) 2 2d Th (1e,)
1 (1 - 2) 2 sd for d 2 2. Now, we show that comparing against de 2d
gives us the desired bound for E-quantile regret:
T
T
Rog
(pr. 4x)
Σ
1=1
(pt gc. (e)
Σ
(De(pe) &c(e)); (e)
(since for all p Add), qe)
o
TKKL(g), TT
T log log d
(by Theorem 4.1)
o
T
ge log
ge,i (Ic,)
+ / log logd
i=1
(only the elements in {1e]
lej] have non-zero probability mass in qe)
8d
T Tlog
T lloglog d
(since qe. [Td]] for all E [d)
[ed]
0
TTlog Toll log logd
This completes the proof.
B.3 Kernelized MWU
In this section, we first prove Theorem 4.3, and then discuss how to further speed up Algorithm 3.
B.3.1 Proof of Theorem 4.3
Proof. The kernel function (Definition 4.2) used in Algorithm 3 can be computed follows:
K(B,A) Σ (())
II (.jE(d):u==1
BijAij
DEDD
II
Br Ang + Σ
II
w Bij Aij
2d 1=1 deds
i.jE(d)ou=-1
(from Eq. (1))
Σ
Jy Big +
V Bij
2d
k=
2= ==
24

---

Thus, it takes (dd) time to evaluate it.
To prove the equivalence between Algorithm and Algorithm 3, we denote = J1 J- c and 4., (Ø, pel.) With some abuse in notation, for d E 4 and i [d], we denote by (i()) the unique index E [d] such that Øig = 1.
x(d) expe ex)))xxpp
According to MWU (Algorithm 1), (:()) Evee, ((0') expl - (,00)
for all Φg. From
Kemeliied MWU (Algorithm 3), we have
(),,,)) = Σ
(())
II
(Be)ijJij
SEth
Σ
(())
II exp
Profes
ΦE
==1
and
(() Σ T())
II
(Be)ur (Jis).. wv
6Et6
a.vE +u
- Pr.ultio
exp
pEDx:p(i)
M.PE[d]:Puu=1
So, we have
J) - JT)
=
E T(Φ)
II
exp
Praar
(E)):
3 :e
1=1
t-1
Σ
(Φ)) exp
()
T=1
[-1
ex))exp
-17 Σ4
L
Óij-
S
T=1
Therefore, for all i,j [d]. we get,
(0t)ss = K(Br, J) K(Br. Jú)
J(B,,
Esco, exp) exp
-1) -n 1.,00 Øis
Eveo, T(0)exp
(-1) Σt=1 4.
Σ q(())oi sES,
giving us the required equivalence: Φ; = Eseo, qe(0) 6 Ex (d].
B.3.2 More Efficient Implementation of Algorithm
Based on Theorem B.4, each iteration of Algorithm can be implemented in (dd) time. However, we show below that by reusing intermediate statistics and expanding the terms wh using Eq. (2), this can be improved to (dd)).
Theorem B.4, Algorithm 6 outputs the same o, as Algorithm 3 for all E [T'] and has a time complexity of O (d²) per iteration.
Proof. Similarly, we denote J = 11 and Jıj = J eve]. With some abuse in notation, for ø E Ds and E [d]. we denote by o(i) the unique index E [d] such that Φn 1. Direct calculation shows
25

---

Algorithm 6 Faster Kernelized MWU with non-uniform prior
Input:
learning rate 7 > O.
Initialize: Lo E dddd as the all-zero matrix.
for t 1... T do
Compute the quantities V/2 E Rddd a R. C Rdx(d+1) and St E R as follows:
exp( (oo(-n((L-)aa Vi,kel
(Vi)ia
ΣS exp (n((--1)s)))
Qt Σ1
(Vi)it d(d 2)) II (Vi)a
d(d 2)
1=1=11
1
(Vi)ux + d(d 2)
k E [d],
(9)
(Ct)
ufi
E [d].
1
(V))a + d(d - 2)
k= d+1.
uzi
d (Si): Σ
(C)),, Vie
k=1
Compute de as:
(ot) = (Vi))y(Ca)iss (Vi) + [(d- 2) +1 si) c (d 2)
(Vi),, (V),,(C)))
Vi,j E [d]
Grd
(10)
Receive loss matrix p,l,. and update L, = LG-1 + Ppl..
that
K(B,,
Σ (())
II
(B))
=1
Σ
II
+ 2
gd++
exp (-n(Le-1)
2d
1=
V.j
:0hy=1
d
d
1
M exp (-m((L)))))) +
d+1
exp (-n((r-1)6))
2d
E=1=1
where - is defined in Algorithm 6.
Using the definition of * in Eq. (2), for i, k [d]. have
o exp(-n((r-1)ss)
1 (1-
(xp(-n(Le-1)) + did 1)
Σ exx((-n(Lr-1d))
j
d 2
exp( app(-n(T1-))p)) + d(d
exp( |n (nn-1)))))
-
j=1
d Σ
(a=2)
d d-2)
exp(-1g 7((4<1))sk
exp( (nn( (L(-1)))))
(d-1)
Σj exp( -n (I(-1)
d(d ( 1)
d
Σ expl exxp(_n((r-1))) (ln
(Ne)au + d(d d(d-2) 2)
1
1
d-1
(II)
26

---

Similarly using the definition of gi in Eq. (2), we have
Σ ddt exp(-)((1-1)))) = d 1
d- 2
Σ exp( Eep((-n((e11))) (NV)a + d(d 23 ) (12)
Thus,
d
d
d II
1
K(Br.)) = 2d k=
exp( - (bb-))))s)
(Vi) + d(d - 2)
d
2=1
i=1
1/d-2 d
+ d-1-
II
exp( 77 L1 1-)))
(Voli + d(d - 2)
1=1
d-22 d
Σ /=1
expl ( (nn-1)ss)
d-1
Ce
Similarly, we have
((,
Σ (Φ)
II
(Be)uo (Jis)an
II
+
II
whtt
II
(
2d A= u.
2
$Eth
(dl
M.uE[d]:duoo
w.e :du
II
2d+1 Vun
II u.vE[d]
exp
2d k= =l
2
$00(1)
a.vE|d]:P
This implies:
K(B,, K(Br,Jis)
Σ
II
v +
mbd+1
II (d
exp (-nr(Ta-1)aa 1)mo)
2d
2
(;)()==j
k= u.rE
u.
d
1
Pi
exp (-n( 1<)-)))s))
II
w exp (-1) -mn[ee-1uum
2d
k=
+
1
d++ Vij
exp (-n(Le-1)ss)
II doo(i)=) uffiituuml
bd+l exp (-n(Le-z)
2
d
d witk au
1
exp
(-n(Lo-1)s))
exp (-m)(Le-1hur
2d
k=1
usdi pml
1
+
exp ( (-
I
ad+1 exp (-n((L--1)ao
2
ij
1
d
Vi
exp
(-m(Le-1)8)
II
d - 2
Σ
d
exp( n7( (Lo- 1 (valeu d(d - 2)
2d
d
ufi
1
expl -nn ((Lr))aun) ) ( (vabur + d(d 2) [
d
1
dd+1
exp
(-m(L
2
(from Eq, (11) and Eq. (12))
27

---

d
exp exp(-nn((x )is)
d d-2 d-1
d
II Σ
exp( -nnn-nn (Lt (Lt-1))w))) 1)w))) (Ct).R
2d
De= exp 1-
d dd-1
k=
m=1 ==1
1 d++1
exp (-
d d-2
+
Σ
exp( (on(-n((x -
(Ci),
2
Σ exp (-n) (
d -
Aall v=l
(from Eq, (9))
1 d -
I12 w=1v=1
exp( (Sp(-n(LL-1uu))) (Voles (
( (Ci) + 1//" (C)),,+1
2
d
(from Eq. (9))
Therefore, we get
K(B,, - Jay) K J)
d-1 celd - 2)
(Vi)ss +
(Cil + +. (Co),
where the left-hand side is how (de) is defined in Algorithm
Finally, we consider the following two cases. Case 1: for j # i. we have
(0t)ss Add(d 2)
d (Vi)ss ((1 [ d(d-1)
Σ(C.).)) kØj
d-1 (Vi)ss
1
+ celd-2) -2) (Vt)ss(C))ss
d(d -1 (Ce)..411
(from Eq. (2))
(Vi)
(Vi)is(C))adt
+
(from Eq. (9))
cdd
ad (d 2)
d(d 2)
Case 2: for i, we have
(Φ)) = ad (d 2) (Vi)e (11-2) (Ci) (Ci)ss + '(d kt3
E(GO)))
+ d-1
(Vilis
((d)
d d-1
) (Ct)idt1
(from Eq, (2))
cald -2
d
(Ci)
cdde(d 2) + (d= (C)))(C d(d 2)
(Vt)
(from Eq, (9))
Gd
C
Combining the cases above gives us how (dr)is is defined Algorithm 6, establishing the claimed equivalence.
To calculate the time complexity computing 6r. note that V, can be calculated in O (df) time. Given Ve, computing et takes another O (d2) time. To compute C., we can first compute Ih ((V)us + a(d-2)) k E [d] and IT ((V))u + a(d-2)) in O (d²) time. Then, these values can be used to calculate the matrix C, in O (d2) time because we can compute each entry of Ct in constant time. With Cr, St can also be computed in O (dP) time. Therefore, computing o takes O (d)) time.
C Omitted Details in Section 5
First, we include the meta MWU algorithm discussed in Section 5 in Algorithm 7, which uses base algorithm shown in Algorithm We use U [d + 1] x [M] for notational convenience, where M = 2oog d]. We now show the guarantee for our proposed prior-aware BM-reduction (Algorithm 8).
Theorem C.1. Suppose that xy is a vi-induced distribution as defined in Definition 3.1. Then Algorithm 8 with prior Fw. learning rate n > O, and SubAlg being MWU (Algorithm 5 with A (d)
log T + 7I for all ó db-
guarantees ΣT= (pr ).p(lT)
28

---

Algorithm 7 Meta MWU Algorithm for Learning Multiple BM-Reductions
Initialization: Set learning rate 7j / /boo((d+ [o0((d+))-2[ df) and 1 [4] 1 AUU), where U
[d + 1 [M]]; initialize [u] base-learner B (kc, h) Ut where By is an instance of Algorithm with prior vi learning rate / /T, and subroutine SubAlg being MWU (Algorithm 5 with A [d).
for ( -= 1,2.... do
Receive k.h E S from B for each (k, h) E U and compute oz E(K,)EE Wi,k 1t k.h.
Play the stationary distribution pt of de (that is. Pt = (p())) and receive loss l. where E, (0) .pll)).
Update W1+1 such that W1+1,k,h We.k.h exp(-n Send loss matrix pel, to Bx, for each (k, hi) U.
k.h
Algorithm 8 Prior-Aware BM-Reduction
Input: a prior & E S, a learning rate 77 >> 0, and an external regret minimization subroutine SubAlg. Initialize: d instances of SubAlg, denoted by SubAlg ..... SubAlga, where SubAlg, uses learning rate and prior distribution tha: E (d).
for i 1,2..... ..; T do Propose de E S where the k-th row ΦL, E A (dd) the output SubAlga- Receive a loss matrix paljT and send the k-th row to SubAlga for each k E [d].
Proof of Theorem C.I. First we decompose Σ (or - o. pelt) as Et Ei (6r:: - di Peale.
For each i, based on the algorithm and Lemma B.I, we have
log
Σ (or: di. Pt,li)) s
Σ
Ptç 1=1
1
where db(i) denotes the unique index j such that dij = 1. Noting that Di 1900 is exactly o (e) by definition, we have thus proven
T
d
log she,
T
log (w)
Σ (6: 6, p.PT
+ +1
Σ
Pt,s
+ T/T.
11
1
1=1
Next, we provide the proof for the adaptive r-rreret achieved by Algorithm 7.
Proof of Theurem 5.1. Since Pt is a stationary distribution
dr. we have Reg(ø)
Σ (p: Φ(pc). 4) = Σ (pt) <(pt), (x) = D ( d, pelT). Using the definition
of Φi and eN" from Algorithm 7, for any (k. h) U4 we decompose Reg(Ø) as
T
Reg(d) =
Σ (or p)
1=1
1=1
Ek
(w)
ck
e +
Σ di. δ, pill
Applying Lemma B. the first term can be bounded as
T
Σ (w) - CR,,, ex) s 22 Toog (dd + 1) 2[log, d)) S 4 d.
(13)
29

---

For the second term, by Theorem C.I, it holds that
T o, p.le S
log
E
(ot
T [
+ mm..
(14)
m
Summing up Eq. (13) and Eq. (14), we can bound Reg(ø) as
log
Reg(ø) S
44 logg d.
Th
Since the above inequality holds for all
[d + 1]. we have
log
1
Reg(Ø) S
min kE|d+1]
+ Th 4v Toog
7h
log maxxeld-11 7 (0)
M.T + 4 Togd
7/h
log s() + M.T 4
(15)
7hb
by the definition of æ (Definition 3.2). It is clear that Eq. (15) attains its minimum when 7) is
log Similar to Lemma B.2, we now show that there exists ht such that The close to this 1 optimum. Since b 2 de for all & E [d 1] and i E [d], it holds that
min 2 = S max
log T(ल)² 2 S dl = 22 To d S max 2
Therefore, there exists h" such that
2 < max
log T(Ø)"
2 -
22h"+1
and thus
log m(Φ)
+ mh T
log
T
+ +V V Tlog π(ő)
2h
1
+ 2VT..
7h
T())
2h
Substituting it into Eq. (15) (by picking h"), we have Reg(ø) < 3 /Tolog ক(ल) 1 + 2
न(क) log d o (Tllog 1 + loggd) Therefore, Eq. (3) is satisfied with B T log
The second statement of the theorem then follows directly from Theorem 3.3.
D Omitted Details in Section 6
In this section, we provide the omitted details and proofs for our results Section 6. The section is organized follows. In Appendix D.I, we include the pseudocode for OMWU. In Appendix D.2, we introduce several important lemmas that will be useful in our analysis. Then, in Appendix D.3, provide the full proof for Theorem 6.4. Specifically, we utilize the nonnegative-social eetecialleeteenal-errree property to show that the path-length of the entire learning dynamic is bounded by O(N log d), followed by full proof of Theorem 6.4. Importantly, following the notation convention introduced in Section 6, we use superscript (n) to denote variables associated with agent/player
start with proof sketch, showing how
D.1 Pseudocode for OMWU
Here, we include the pseudocode for OMWU (Algorithm 9) that is used in Algorithm 4. There are two possible outputs for Algorithm 9 at each round 4. For base learner Ba+2 in Algorithm 4, the output in round de E RRdxd while for subroutines used by Bg for & [d + 1], the output
Pt E A(d).
30

---

Algorithm 9 OMWU
Input: learning rate 7) > prior distribution A(d). Initialize: to 0 R for 1,2.... do
Compute pt such that Pr. x Pt,i exp(-nf(-1,)) for E [d] and di = 1p, E Rdxd
Receive & and compute Pi+1 such that Pt+1,i x Pt, exp( -n2,,)) for i E [d].
D.2 Auxiliary Lemmas
To analyze the performance of OMWU, following lemma from Syrgkanis et al. [2015].
Lemma D.1 (Theorem 18 in [Syrgkanis et al., 2015]). OMWU (Algorithm 9) with learning rate 7) > guarantees that
T
(e u, u KL(u,p1) P1)
T ll
Σ
11
1111
111
"
8n
The next lemma shows that the loss vector difference between consecutive rounds for each agent is bounded by the sum the strategy differences over all other agents.
Lemma D.2. For any E [T], [N], we have
|
e 1 s (N-
- Σ (1 jtn
(1)
Proof. For any action a E [d]:
(10
= Σ
II
U Pi,a
( II jfnn
p(x) (ax) (a, a ann)
Pi-1.03
a -(-))
II
(
(since (e(n) s
Pi.y
Pt Pt-1,a3
a(
jzn
jfn
()
1
Pi-1.
jfn 1=1
= Σ 1p - 1 1l.
FR
Taking square on both sides, we know that
2
(1((0) ((2) 11: S
Σ juh
lpr Pinill1
(NV
lpp(
( Pt 11?
jtn
The next lemma shows how the difference between strategies in consecutive rounds is related to the stability of both the base learners and the meta learner.
Lemma D.3. Suppose that every agent n E [N] applies Algorithm 4, then for all 1. > 2, n. [N), have
d-2
(m)
(n)
[n).)
_(n).x
w (a)
Pi
Pi-1
Wi,k
Pt
Pp-1 +
w
1=
where k(n),k ((())((p(()))
(p(:)) ) for each & [d + 2].
31

---

Proof. Direct calculation shows that
(n)
[n) 1
Pi
-P--1 1
(0f (m)
T (m)
Pb
- (00(1))
(--1)
P:-1
(p) (n)
is stationary distribution of m())
d+2
T
d+2
Σ
(
mn)
(m),k
(definition of o ())
W 2,4 pz
W
11-1, 1
Pr
d+2
d+2
2
W Wetk Pi
(n) (n),b
Σ
W
1 1-
(n)
(n).k
(definition of Pe.
R=1
d+2
d+2 Σ
dd2
d+2 Σ
2
Σ
(n) (m),k 1,8 Pt
1,k Pt-1
(n)
[()..
+
Σ
(n) (m),k b P Pi-1
(n) (m),
d-2
$
Wii
Dt
((n),,
+2 11
w
(n)
(Jensen's 's inequality)
1=1
The next lemma further bounds the scale of - [l with respect to the stationary distribution difference [Ip,") p|")11? Ili and the base learner's decision differences.
Lemma D.4. For all k E [d + 2] and E [N]. [I p 12 S
2/1p("))
p|_ 12
(n), 1 (m),k Oif 12-1::
2 3
1=1
Proof. By definition of (n),k we can bound 11 (a).k
f())) || as follows:
1 1
pi-1
(0 p/_ - (m( T (n) 2
Pt-1
2 (of T (n((0) -p,=)) |1?
(n)
2
+2
(0)
(n),k
(m).k T
P
2
2
d
(k),k (p(h) - /
d
2
Σ
+2
(nj.k
/ -i-1.sh
(n),
(n)
2
2
d
2
Σ
P (p
(n).k
(p(
+2
Σ
pr
(n)
o 10
(n),k
(n).k
1=1
i=1
2
d Σ
d
d Σ
d
(
(n)
(m)
(m).k
(n).k
2
Pi,s
Po-1,
+
1o
1,
0t,6j
1-.5
1=
t=1
j=1==1 1=1
2
d Σ
(m)
(n)
(n).k
(n)
(n).k
01-1.e 11,
(c),.
2
Pr.
1,
+2
P=-1,
j=1
= 2
Pt
(n) (m)
p
2
+2
Σ
Pt-1,
(n)
(n),
$2-1.5: I.) 2
(k).k
(since df S)
< <2115 (n) - (m)
1 + 2
Σ
p
(n)
1.
(n).k
1
(n).k
2
(Cauchy-Schward inequality)
1=1
32

---

d
+ 2 - 211p] - -p_1
(m)
112
Pr,y 0z-
(n).k
(m),k
2
which finishes the proof.
The next lemma shows the multiplicative stability of the meta leamer's strategy.
Lemma D.5 (Multiplicative stability lemma). Suppose that each player runs Algorithm 4 with
Mm 8(1+4X] have for all t E [T], [N], and l E [d + 2). (n) [12 2
[m) (n)
Proof. We omit the superseript (n) for conciseness. By definition of 4 my and Ct, we know that max Ile + celloo. I|m"" + ca ] + 4A for all t E [7]. Therefore, according to the update rule of wt and S₁, we know that
W1, exp((xmmm + ct,)))
exp(-1/8)wt.t S Wi,k
S exx((188 Wr,k.
iml W7,i exp 7m (m, + ct,i))
1h 1,8 exp( 7m (f,- + c()),)))
exp S We.
Σ Li=1 11- exp 7/m (m (m c-,,,)) S exp(1/8) 1
d
Therefore, we know that We,k I exp(3/8) I 2 and Wt,k 2 exp(-3/8)uu-111 2 W
The next lemma bounds the external regret for the meta learner with respect to an arbitrary distribution over the d + 2 base learners.
Lemma D.6 (Meta Regret Bound). Suppose that all players apply Algorithu with X S we have
Then,
4%m.
KL(u, w()))
(n) Wi
U, (
< 0O(A)
2m
N
Σ
Σ
(n)
7m
t
14+2
T
12
An)i An)),
-
-Pi-1 11
(n) (m)
Pí
P1-1
t= k=1
for all agent n E [N] and u E A(d + 2).
Proof. According to Lemma D.I, we know that for each u E A(d + 2) and n E [N].
(n) Wi
u, ( + Ct
(x)
KL(u, (m))
1m
m
(n).
113
|m0
(n)
:o(mm) 11?
(Lemma D.1)
Om
8mm
KL(u, w (1))
T
(n)
((()).
(n) (n). ((n)
(()))
2
+ 1m
max
pi:
1b
Um
(E(442
81mm
1=2
KL(u, (u, (()))
T
[1(e()) (n)
-w
7m
811m
t=2
+ 2mm
max kE(d+2)
(K(p)
1p
(n)
0r (())) )²²
2 po-1 of
(N)
((m))(((m)))
-P:-1
(n) (n), ((n)
26
(--1
KL(u,, w(
(m))
2 p 0f
(n) (m).
p.- di 1 +2 (m))) 4n) 12
(n) (m),s
7m
max (E(++2)
7m
T
1
|1o! (n) - w (0(h) 11
(using Hölder's inequality)
811m
t=2
33

---

KL KL(U,,u 2 + 2m (N 1)
T N
T
Σ
lppt (")
- -Pi-1lf
(m)
[mj
(n)
1m
81mm
t= n=1
where the last inequality uses Lemma D.2. Recall the definition
\|(
(o (olm)/) T 211 Allp--1 2-2211 for t 2 3 and Ci, 0 for t {1,2}, we can further upper bound the meta regret as follows:
(n)
u. (m)
Wi
KL(u, )
2m
(N (N
1)
IPt
(n)
Pr-1ll1
(n)
11
(n)
w
w-11l
(n)
7m
8mmm
T d+2
T d+2
E,k 11pi-1
(n) (n).b
Pi-2
(n))
11
Uk Pi-1
(n).k
Pi-2
kn)
k=1
1=3 k=1
KL(u, )
T
T
2mm
lpt
(n))
-
Pi-1
in)
Uk |p
(n),k
_()) 1
7m
1=2 n=1
1=3 km
1 T
T d+2
(n)
w
(n)
ΣΣ
(n)
(n)
(n), Pi-2 1??
817m
t=3 k=1
(w S 2w0 using Lemma D.5)
(n)
KL (2, w( (
T
T 4+2
0(A) +
+ 2mmm N
IP.
(n)
1it -pt-2 11
(n).
7m
t=2 n=1
1=3
T
d+2
811m
1
100 (n)
w
(1))
112
t,k
(n)
P:
mn)
p.. 11
p:-1
k=1
SO()) + KL(U, w (1))
T N Σ
T d+2
2mmm N
lIpb (n)
Pt
+ Σ
Uk 1i
fn).E
7m
1=2 n=1
[=3
X
min
(using Lemma D.3)
161mm
1=2
KL(u, w( (n))
T
5O()) +
2m N
IIP - [((]]
(n)
7m
1=2
1-1d+2
T
ΣΣ l - -P
uk
Ip
(n)
11
(n)
(16)
1=1
where the last inequality uses the condition that 49pmn
D.3
Main Proofs in Section 6
In this section, we provide the proof for Theorem 6.4. Before showing the proof, we first provide an outline to highlight the technical novelties in proving Theorem 6.4.
D.3.1 Proof Outline
As shown in previous literature (e.g. Anagnostides et al. [2022b], Zhang et al. [2022]), in order to show fast convergence, the key to control the stability of the strategies between consecutive rounds. Anagnostides et al. [2022b] use log-barrier regularized online mirror descent control the sum of the squared panh-length between consecutive rounds over the horizon and all the players. However, due to the use of log-barrier regularizer, the obtained bound ( log suffers from a larger
34

---

polynomial dependency of d and log T. Somewhat surprisingly. we show in the following theorem that if the game satisfies Definition 6.3, Algorithm 4 (with entropy regularizer) achieves tighter O d) bound.
Theorem D.7. If each player [M] applies Algorithm 4 with 7m have
1 and X = N, then we GIN
Σ
1 S O(NNogg
We provide proof sketch for Theorem D.7 (with full proof deferred to Appendix D.3.2) and why our modifications to both the meta learner and the base earners are crucial to achieve this. To prove Theorem D.7, consider the each player n's external regret, which can be decomposed the meta learner regret with respect to B642 plus Bat2's ''s external regret:
Reg Ext (u)
ed+2, p(n) we
(n)
(n) -1 Pt oF
(n) ((n)
META-REGRET
BASE-REGRET
Applying Lemma D.I, Lemma D.6, and some direct calculations, we can show that META- REGRET and BASE- REGRET are bounded as follows:
KI. (I.(e2+,, (m)
T
N
META-REGRET & O())
+ 2m
N
llp
(m)
Pi-
7mm
1=2
+
Σ
Pt
Pc-1
dn))d-2
lIp(") (n)
-p1-1 1
(17)
t=2
t=
RASEEREGRET& I
log d
+ 17
[((n)
(
((n)
11:0
1
T
lp
dn).
Pi-1
(n),d42
1
(18)
8n
where Eq. (18) uses the fact that of (n),d+2 1p(")) d2 According Lemma D.2, can further
upper bound both ||e ( p(m Ioo by ONN |p (n) - -|_) lli). Now, we see the importance of
including correction terms in the meta-alae algoritg... Without (()), the two negative term in Eq. (18) is not enough to cancel the above positive term. Thanks to the correction term, we are able to
cancel the positive term O(1mm 1) > E llpp)) P: - by using half of the negative
l
term A DT -=1 |!pp") p(m) 1 taking summation over n E [N], and picking A, 7mm and appropriately. Moreover, the positive term induced by the correction can be canceled by the negative term in Eq. (18). Therefore, summing
REGEET and Um = (1 (1/N), 7 = O(1/N), and X N, we can obtain that ΣN Reg Ext < (N2 log N -= >
for all n [N] with
Eiz lp. (n) (x))
P It). Further using the property that N Reg Ext 0 finish the
proof.
Note that the above proof sketch indeed also proves an O(N log d) external regret for each individual player. To obtain comparator-adaye
f-rrgret, we first consider á E T and obtain Ocos log d N2 log d) by picking the meta learner's comparator Add + 2) be distribution based on Then, the final result is achieved by taking convex combination of the bound.
D.3.2 Proof of Theorem D.7
In this section, we provide a detailed proof for Theorem D.7.
Proof of Theorem D.7. Fix n E [N] and consider the base-regret and the meta-regret for agent with respect to the base algorithm Ad42, which is Algorithm 9 handling the external regret. According
to the construction of df (n).d+2 we have oi (n) Pt p(").d+2 for all i [d], meaning that p dnn).d42 equals to the decision made by Ast2 round t. Therefore, using Lemma D.I, the base regret of
35

---

Au+2 with respect to E (dd is bounded as follows:
Pi,1 u, ((/))
(n)
log d
1
2-1
(()
11
Pi.1
(n)
P1-1.1 112
[n)]
11
87
1=
log d s
+ 77NN
1)
Σ
T
lp
- P
()
1
T
Pi.1
P1-1,1 l1:
(n)
81
1=2
jyn
(19)
As for meta-regret, applying Lemma D.6 with cd+2 and noticing that (n)
iid-2
4' we have
# (m)
cd+2. p(n),.))
IO(A)
log 4
2m N
1pp (n)
p/-"] 17
1/m
1=2
n=
Pr.1
P
P1-1,111
A
Ip
(n)
(20)
Summing up Eq. (19) and Eq. (20), we can bound the external regret for player n as follows:
T
Ext Reg.
Σ
( Pr u, e(w))
1=1
T N
S 5O(A) + log 4
logd d
+ (2 + N)
lp
(n)
-P:-1
7m
n
t= n=1
+
X 2=2
(n),
Pi-1
(2),42212
112
1
dn)
Pt-1
(n).
||
X
|p:
(n)
8m1
t=2
t=2
(A(A) +
log
log d
+ (2 + N
lp
(n)
P
(n)
A T
llp
(n)
Pt
Pi-1
(n)
ll
7m
7
4
(21)
where the last inequality uses = N < 1 2N. Taking summation over n E [N] and using
Ext Definition 6.3 that E Regn. 2 0, we know that
0
Rog Ext
S O(NN)) +
Nlog logd + ((2mm + N2
T
N
Ilp
(n)
(n)
Tm
4
t=
According to the choice of X, we know that gives
2
3N 32
(21mm N)
Rearranging the terms
N
N
lp (n)
p. Ilf < O(2 logd).
8
1=2
n=1
which finishes the proof.
D.3.3 Proof of Theorem 6.4
Now prove main results Theorem 6.4 for multi-agent games. Specifically, split the proof into three parts and first prove the external regret guarantee.
Theorem D.8. Suppose that all agents run Algorithm with = N, nm = edv- Then, we have Reg. Ext
ON log d).
36

---

Proof. According to Eq. (21), we know that
Reg.. log 4
(())
log d
(n) + (2 +n)
lipt (n)
7m
r
n=2
N
ONN loggd +0
ΣΣ
Pp (n) - -0--pp111 11
ON logd),
where the second inequality is due to the choice of Tim 17. and the final inequality is due to Theo- rem D.7.
Next, we prove our results for P-regret. As we sketched in Appendix D.3.1, we first prove our results for binary transformation matrices ó E D,. First, the following theorem shows that our algorithm achieves Reg,, (Ø) = O(N(d - dell) ( log d + N2 log d) for all Φ E $b.-
Theorem D.9. Suppose that all agents run Algorithm 4 with X = N, 1m 64N- Then, have Reg, (0) S O(dd deelt N Nog N log d) for all tb..
Proof. To achieve Reg,, (Ø) S O(N d log d + N2 log d), we consider the regret with respect to base algorithm A4t1. According to Lemma D.6 and Lemma D.4, we bound the meta-regret as follows:
T
-eat1,
-dt11,
el p()),))
T
=A(A) + log4
2m N
Σ
Pt
(m) (m)
-P- +
IP 1
A
IP
(n)
7m
t=2 n=1
t=2
1=1
(A(A)
log
2m
T
1p
Pr- 22 2A
(n)
T-1
l|pt
(n)
p 12
P
(n)
Qm
d
T-1
(m).d+
(n).d+112 1 11
+
j=1
where the second inequality uses Lemma D.4. According to the analysis similar to Theorem C.I, we know that base-regret A441 can bounded as follows:
(n),t1 ),p( (n) (())
T
(n),d22 - ((ee)))))))
Pi,s e((a)
(m)
KL (L(o(e)),
1b (dt1)
T
(n)
((()
(n)
(n)
(n).41
(n),d11 P
1,3
17
Pis
Pi-1
pz.s
17
817
(using Lemma D.1)
log
d
T
1yd+1 (+)
(a),++1
(n),d+]
oif
1-11,
77
8m
t=1
(m)
n
Pê,s
Pi-1.
1=1
m
2(d - drelt) log d +1
(n).t1
0 1,
(n).t+1 2
(according to Eq. (4))
811
37

---

+ 2m
Σ
T
d
elti
-
Pi.
(n)
(1))
2
+
(m)
2
==1 1=1
2(d
) log d +
d
(m)
(n)d++1
1--1
7
8n
T
(n)²
p(n)
(n)
(n)
2ny
Pi.
Pt.
Pt 11-1.1
2(d
(eltt log d +
T
d
b(m)
(n),411
2
0
1,x
811
t=1
T
(m)
(m)
p l!))
+ 2m
pt
1=1
2(d dorl log d +
(n),d+1
((m),++11"
|]
1,
7
81
T
T
+ 2n(NN 1)
Σ
Σ
p
||
+
2n
Σ p -p
(using Lemma D.2)
t=
Summing up the base-regret and meta-regret, we can obtain that
Σ Φ Φ.rt" (n) (l)
5O(A) + log 4
+
2m N
lpt (n)
+ 2A
Σ
||p
(n)
-Pi-1l
(n)
7/m
1=2 n=1
t=2
T-1
+ 2A
P2.y:
(n).
1b-1.::
(x),d1
|?
j=1 t=2
2(d - dell
log d +
1
T
(n),d+1
(x) 2
p1-1,3:
11
81)
[=2 1=1
T
+ (N 1)
(1) - P
())
12
+ 2m
Σ
Pt
(n) (n)
Pi-
(=2 (=2 jfn
1=2
log
2(d
dell
log d +
< O(A) +
+
7m
T
N
+ (21m N + 2n,N + X)
lp
( - 12
(since 2 = 2N < 1
kn))
1=2 1=
Since A N, 7mm.
GIN and 1 I&N and using Theorem D.7, know that
Φi p.p(") (m) <o((a drdh) logd + N2 log
Next, we prove our second bound with respect to d - duuin + 1.
Theorem D.10. Suppose that all agents run Algorithm 4 with X = N, mm G1N.
1
Then, we have
Reg,, (Ø) < O(dd - dgpii N log + N2 log d) for all ó e Dy-
38

---

Proof. Given Φ E bs. suppose that the most frequent element in {é(e1)..... Ō(ea)} is eto for some in E [d]. According to the definition of dunif, we know that there exists dh number of E [d] such that ((e;) = Eig To bound Reg,, (6), we compare to the base-learner Aio. Applying Lemma D.6 gives us
(n) Wi
Gig e(m))w))
I (A) +
log 4d
+
mm N
Σ llp
-
+
Σ t=2
Pt
m),i0
I|
Thm
2= n=1
T
lpp
(n)
11-111?
(m)
log 4d
T N
T-1
I (A))
+
+
2m
N
lp
- p.
11
22
p
(2)
1/m
1=2 n=1
1=2
T-1
(n),50
(n).50 11-1.::11
2
j=1
where the second inequality is because Lemma D.4. Now we analyze the base-algorithm performance of Algi, against de
T
D.Pr (m) p()))
T
(n),50 - -(Ei), (n) p(n))
(L(((e)), 16
(n)
p(())
2
1
T
in (n),50 2
17
Pe.
811
1
log
vo (+)
1
io
1-1,8
(n).g
+ 20
Σ
(1(550)
2
+
(n)
(/0 11:)
11
811
i=1
t=1
20
2(d - unil Φ
log d +
1
1
T
(n).
(n),
|
(according to Eq. (5))
7
817
Pr
11-1,
T
(m)
(n)
p|-] l.²)
+
2m
2-1
+
Pt
1=1
2(d dgnil
log d + 1
1
T d
(n).
(n),6o 2
Pt.t:
11-1,1;
1
81
tm1 aml
+ +2n(N 1)
ΣΣ
Pt
(1)
(2)
2n
pb
pi-1
(n)
(using Lemma D.2)
2=2
ifn
Summing up the meta-regret and the base-regret, we can obtain that
T
Reg,, (d)
Σ
w
(n)
p(n))
(o)
Φ.
(n) p(1)T)
ct
t=1
< (())
log 4d
21mm N
Σ
(n)
(m) 112 + 2A
11p
(n) (n)
P
7m
2=
T-1
+ 21
1
(n),io11
i=1
39

---

2(d d
log d +1
T
(n),to
(n).ig
+
0 t
0
1-11
8n
1=2
1=1
T
T
+ 2n 1)
p1
P:-
(1)
+
2m
Pt P1-
2
2
(() + log 4
2(d
dunif v
log +1
Tmm
7
T
N
+ (2 N 2 + A)
1p
(
- 1.. ll:
(since 2A = 2N S 84)
j=
< 0 (N(dd ب:th + 1) log d + N2 logd) d),
where the last inequality is by picking 7) I6N and using Theorem D.7.
Finally, we are ready to prove Theorem 6.4 by combining Theorem D.9 and Theorem D.10. Proof of Theorem 6.4. Combining Theorem D.9 and Theorem 1.10, we know that for any & 4b.
Reg, (Ø) (c log d N log d).
Then, for Φ E S, define Qs = aargminggq.. Egy [c Then, we know that Go = -Bg [car] and
Regn, (Ø) = Es [o)) S O (E low N log d + N2 NN log d) S OlcoN log d + N2 log d).
Combining the above with Theorem D.8 finishes the proof.
40


Reviews:
[{"review_id": "oTDXx22q1M", "reviewer": "Reviewer_Szbw", "summary": "This paper builds upon the recent work of Lu et al. (2025), providing $\\Phi$-regret bounds that are based on a sparsity complexity measure $c_\\phi$ that recovers the almost optimal no-external, no-internal, and no-swap regret guarantees. $\\Phi$-regret is a well-established regret notion, where given a sequence of probabilities $p_1,\\ldots,p_T \\in \\Delta_d$, it measures the difference between the experienced cost and the cost of the best transformation $\\phi: \\Delta_d \\mapsto \\Delta_d$,\n$\\mathcal{R}(\\phi):=\\sum_{t=1}^T \\ell_t^\\top \\cdot p_t - \\ell_t^\\top \\cdot \\phi(p_t)$. Lu et al. (2025) provide an algorithm with $\\mathcal{R}(\\phi) := O\\left(\\sqrt{c_\\phi(T + d) \\log^3 d}\\right)$, while the authors provide an improved bound of $\\mathcal{R}(\\phi) := O\\left(\\sqrt{c_\\phi T \\log d}\\right)$ with a significantly simpler algorithm.\n\nThe basic technical idea of the authors is to introduce a prior probability distribution on the set of $0$–$1$ row-stochastic matrices and to establish $\\Phi$-regret bounds by running the famous MWU on this set. The authors then use MWU as a meta-algorithm in order to select the optimal step size. The authors additionally show that, despite dealing with an exponentially large action set, their algorithm can be efficiently implemented using kernelization ideas.\n\nIn Section $5$, the authors introduce an alternative approach based on the Blum–Mansour reduction. Finally, in Section 6, the authors show how to extend their algorithm so as to achieve $\\tilde{\\mathcal{O}}(1/T)$ for approximate $\\Phi$-equilibrium in a specific class of normal-form games.", "questions": "1. What are the limitations of extending your results for general sum normal form games?\n\n2. Can you elaborate more on the class of games satisfying Assumption~6.3?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I think the paper presents solid theoretical results that will be of interest to the online learning community at NeurIPS. Beyond the improved regret guarantees over those of Lu et al., the proposed algorithms are both simple and elegant. The presentation of the paper is very clear, and the technical ideas are well-explained.\n\nPerhaps the only result I found somewhat expected was the $\\tilde{O}(1/T)$ convergence rate to $\\Phi$-equilibrium, given the extensive recent literature on the subject. Despite the considered class has been previously considered to the literature, the assumption feels a bit artificial. At the same time, I believe that a similar result for general normal-form games would add value to the paper.", "was_revised": true, "final_justification": "After the author-reviewer discussion I am very confident on the significance of the results provided by the paper. I thus recommend acceptance.", "rebuttal": "Thank you for the very positive review. We address your questions below.\n\n>Q1: What are the limitations of extending your results for general sum normal form games?\n\nWe use the key nonnegative-social-external-regret assumption to establish a small path-length bound $\\mathcal{O}(N\\log d)$ of the entire learning dynamic (see Theorem D.7).\nWithout this assumption, in principle, we could also use the fact that swap regret is by definition nonnegative to establish another path-length bound, but it would be larger than $\\mathcal{O}(N\\log d)$ by some factors of poly$(d)$, making the final bound on\n$\\mathrm{Reg}\\_n(\\phi)$  at least as large as the best existing bound for swap regret [Anagnostides et al., 2022a,b] even for a  $\\phi$ with small $c\\_\\phi$ (and thus vacuous for our purpose).\n\n---\n\n>Q2: Can you elaborate more on the class of games satisfying Assumption~6.3?\n\nWhile there is no obvious intuitive explanation for this assumption,\nas argued by Anagnostides et al. [2022c], this class of games is intricately connected with the admission of a minimax theorem.\nThey show (in their Proposition A.10) that all the following standard and well-studied games satisfy this property:\n1. Two-player zero-sum game;\n2. Polymatrix zero-sum games;\n3. Constant-sum Polymatrix games; \n4. Strategically zero-sum games;\n5. Polymatrix strategically zero-sum games;\n6. Convex-concave (zero-sum) games;\n7. Zero-sum games with objective $f(x,y)$ such that\n   $$\n        \\min\\_{x\\in \\mathcal{X}}\\max\\_{y\\in \\mathcal{Y}} f(x,y)=\\max\\_{y\\in \\mathcal{Y}} \\min\\_{x\\in \\mathcal{X}}f(x,y)\n   $$\n8. Quasiconvex-quasiconcave (zero-sum) games;\n9. Zero-sum stochastic games."}, {"review_id": "Fiqx9oGQcF", "reviewer": "Reviewer_WnBk", "summary": "This paper introduces a novel framework for comparator-adaptive $\\Phi$-regret, significantly improving upon the work of Lu et al. (2025). The authors propose two efficient algorithms—based on kernelized Multiplicative Weight Update (MWU) and a prior-aware BM-reduction—to achieve tighter regret bounds, removing unnecessary terms from the prior work.", "questions": "- Given the focus on upper bounds for comparator-adaptive $\\Phi$-regret, is it possible to provide a lower bound analysis to establish the optimality of the proposed bounds, especially in relation to the complexity measure $c\\_{\\phi}$?\n- Regarding the kernelized MWU algorithm (Section 4), the paper mentions an $O(d^3)$ complexity per iteration. How does this complexity impact the algorithm’s scalability for large $d$? Are there practical optimizations considered to handle high-dimensional scenarios?\n- Can the framework be extended to handle heterogeneous agents with different action spaces and loss functions, as encountered in real-world games, and if so, how would the current analysis need to be adapted to accommodate such heterogeneity?", "limitations": "- Game Assumptions: The nonnegative-social-external-regret assumption restricts the applicability to specific game classes, limiting generality.\n- Lack of Experiments: The absence of empirical results prevents validation of the algorithms’ efficiency and practical utility, especially compared to the method in Lu et al. (2025).", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n- The paper achieves tighter regret bounds, matching the minimax-optimal bounds for standard regret notions (external, internal, swap).\n- The proposed kernelized MWU and BM-reduction approaches are computationally more efficient than prior methods.\n- The extension to games is notable, providing the first adaptive and accelerated $\\Phi$-equilibrium guarantee.\n\n**Weaknesses:**\n\n- Although the work is purely theoretical, lacking experimental results to demonstrate practical performance. Empirical evaluation on real-world datasets or game instances would strengthen the claims.\n- The $\\Phi$-equilibrium bound includes an $O(N^2\\log d)$ term (Theorem 6.4), which scales quadratically with the number of players $N$. This may limit applicability to large multi-agent systems.", "was_revised": true, "final_justification": "The rebuttal has addressed my questions and improved upon the original results. As this is a solid theoretical paper that exceeds the acceptance threshold, I have decided to increase my score.", "rebuttal": "Thank you for your positive review and comments. We address your questions below.\n\n>Q1: Given the focus on upper bounds for comparator-adaptive $\\Phi$-regret, is it possible to provide a lower bound analysis to establish the optimality of the proposed bounds, especially in relation to the complexity measure $c\\_{\\phi}$?\n\nWe already mentioned in the paper that our bound is optimal for the special case of external/internal/swap regret.\nIn fact, by a simple argument, one can establish the following stronger lower bound as well: for any integer $k \\in [d]$ and any algorithm, there exists a $d$-expert problem and a $\\phi$ with $c\\_\\phi \\leq k+1$, such that $\\mathrm{Reg}(\\phi)$ is at least $\\Omega(\\sqrt{c\\_\\phi T\\log c\\_\\phi})$ for this algorithm.\n\nTo see this, simply let $d-k$ experts be dummy experts who always have maximum loss $1$, while the other $k$ experts follow the swap regret lower bound construction of Ito [2020] scaled by $1/2$.\nWe then define $\\phi$ in this way.\nFirst, for a non-dummy expert, $\\phi$ maps it to another non-dummy expert optimally (to minimize the total loss after swap).\nThen, to define $\\phi$'s behavior for dummy experts, we consider two cases:\nin the case where the algorithm picks dummy experts for more than $\\sqrt{kT\\log k}$ times, we let $\\phi$ map all dummy experts to a fixed non-dummy expert (in which case $d_\\phi^{\\text{unif}} \\geq d-k$); otherwise, all dummy experts are mapped to themselves (in which case $d_\\phi^{\\text{self}} \\geq d-k$). \nNote that in both cases, we have $c_\\phi \\leq k+1$.\nMoreover, in the first case, $\\mathrm{Reg}(\\phi)$ is at least $\\frac{1}{2}\\sqrt{kT\\log k}$ since whenever the algorithm picks a dummy expert $i$, it gets loss $1$ while expert $\\phi(i)$ gets loss at most $1/2$ (and the rest of the regret is non-negative by construction).\nIn the second case, $\\mathrm{Reg}(\\phi)$ is essentially the swap regret of the algorithm for a $k$-expert problem that lasts for at least $T-\\sqrt{kT\\log k}$ rounds,\nand since the instance comes from the lower bound construction of Ito [2020], we also have $\\mathrm{Reg}(\\phi)=\\Omega(\\sqrt{k\\log(k)(T-\\sqrt{kT\\log k})}) = \\Omega(\\sqrt{kT\\log k})$.\n\n\n---\n>Q2: Regarding the kernelized MWU algorithm (Section 4), the paper mentions an $\\mathcal{O}(d^3)$ complexity per iteration. How does this complexity impact the algorithm’s scalability for large $d$? Are there practical optimizations considered to handle high-dimensional scenarios?\n\nFirst, we point out that in response to Review zKH9's comment, we have in fact further improved the time complexity of Algorithm 6 from $\\mathcal{O}(d^3)$ to $\\mathcal{O}(d^2)$ (see proof therein).\nSo the final per-round complexity of our algorithm is $\\mathcal{O}(d^2)+\\textrm{FP}_d$ where $\\textrm{FP}_d$ is the complexity of computing the fixed point of a $d\\times d$ stochastic matrix, which is $\\mathcal{O}(d^\\omega)$ in theory with $\\omega \\approx 2.37$, but can be much faster in practice using e.g., power method, as also pointed out by Review zKH9.\nImportantly, our algorithm is thus computationally as efficient as the classic Blum-Mansour algorithm and also the Lu et al. [2025] algorithm (while enjoying strictly better and more adaptive regret bounds).\n\n\n---\n>Q3: Can the framework be extended to handle heterogeneous agents with different action spaces and loss functions, as encountered in real-world games, and if so, how would the current analysis need to be adapted to accommodate such heterogeneity?\n\nFirst, we point out that we definitely do not require the same loss functions for different agents, since we are considering general-sum games.\nSecond, as pointed out in our Footnote 4, we assume that the action set size is the same for all players, but that is completely for notational conciseness, and our analysis\ncan be directly extended to games with different action set sizes, with $d$ now representing the maximum action set size among the agents."}, {"review_id": "R8geIohTtb", "reviewer": "Reviewer_FyQk", "summary": "This paper investigates instance-dependent \\Phi-regret bounds. Building on techniques from prior work, the authors propose a refined complexity measure for the comparator, develop two efficient algorithms, and derive improved regret bounds.", "questions": "See above", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is well written: the discussion of existing work is fair, the motivations behind the algorithmic development are clearly articulated, and the limitations are also acknowledged.\n\nThe construction of the prior is interesting, but the paper lacks a clear motivation for introducing it, and it is unclear whether this prior (and the resulting c_\\phi) is the best possible choice. While the results presented are fairly comprehensive, the paper would benefit from a more thorough justification of the complexity measure c_\\phi. It indeed interpolates between external and swap regret, but it is unclear what precise middle ground it captures. Moreover, c_\\phi is defined as the minimum of two complexities, which seems somewhat ad hoc. It would strengthen the paper to provide a justification showing that c_\\phi is inherent: for example, demonstrating that for some reasonable class of comparators (lying between \\Phi-external/internal and \\Phi-best), c_\\phi is in fact the best complexity measure achievable.", "was_revised": true, "final_justification": "I have no outstanding concerns.", "rebuttal": "Thanks for your positive review and valuable comments. We address the issues mentioned in your review below.\n\n>Q1: The construction of the prior is interesting, but the paper lacks a clear motivation for introducing it, and it is unclear whether this prior (and the resulting c_\\phi) is the best possible choice. While the results presented are fairly comprehensive, the paper would benefit from a more thorough justification of the complexity measure c_\\phi. It indeed interpolates between external and swap regret, but it is unclear what precise middle ground it captures. Moreover, c_\\phi is defined as the minimum of two complexities, which seems somewhat ad hoc. It would strengthen the paper to provide a justification showing that c_\\phi is inherent: for example, demonstrating that for some reasonable class of comparators (lying between \\Phi-external/internal and \\Phi-best), c_\\phi is in fact the best complexity measure achievable.\n\nWhile we also do not believe that our $c_\\phi$ is the ``best'' complexity measure (in the sense that any reasonable algorithms must incur $\\mathrm{Reg}(\\phi)=\\Omega(\\sqrt{c_\\phi T\\log d})$ for all $\\phi$), we note that we can at least say that \nfor any integer $k \\in [d]$ and any algorithm, there exists a $d$-expert problem and a $\\phi$ with $c_\\phi \\leq k+1$, such that $\\mathrm{Reg}(\\phi)$ is at least $\\Omega(\\sqrt{c_\\phi T\\log c_\\phi})$ for this algorithm.\n\nTo see this, simply let $d-k$ experts be dummy experts who always have maximum loss $1$, while the other $k$ experts follow the swap regret lower bound construction of Ito [2020] scaled by $1/2$.\nWe then define $\\phi$ in this way.\nFirst, for a non-dummy expert, $\\phi$ maps it to another non-dummy expert optimally (to minimize the total loss after swap).\nThen, to define $\\phi$'s behavior for dummy experts, we consider two cases:\nin the case where the algorithm picks dummy experts for more than $\\sqrt{kT\\log k}$ times, we let $\\phi$ map all dummy experts to a fixed non-dummy expert (in which case $d_\\phi^{\\text{unif}} \\geq d-k$); otherwise, all dummy experts are mapped to themselves (in which case $d_\\phi^{\\text{self}} \\geq d-k$). \nNote that in both cases, we have $c_\\phi \\leq k+1$.\nMoreover, in the first case, $\\mathrm{Reg}(\\phi)$ is at least $\\frac{1}{2}\\sqrt{kT\\log k}$ since whenever the algorithm picks a dummy expert $i$, it gets loss $1$ while expert $\\phi(i)$ gets loss at most $1/2$ (and the rest of the regret is non-negative by construction).\nIn the second case, $\\mathrm{Reg}(\\phi)$ is essentially the swap regret of the algorithm for a $k$-expert problem that lasts for at least $T-\\sqrt{kT\\log k}$ rounds,\nand since the instance comes from the lower bound construction of Ito [2020], we also have $\\mathrm{Reg}(\\phi)=\\Omega(\\sqrt{k\\log(k)(T-\\sqrt{kT\\log k})}) = \\Omega(\\sqrt{kT\\log k})$."}, {"review_id": "scMqf8VZQV", "reviewer": "Reviewer_zKH9", "summary": "The paper considers minimizing the $\\Phi$ regret in the expert problem, and propose new algorithms achieving certain regret bounds that adapt to a sparsity based complexity measure of each comparing $\\phi$ instance, improving the results from a recent work (Lu et al., 2025). Different from the existing algorithm using wavelet inspired matrix features, the proposed algorithms are based on the arguably simpler idea of expert aggregation, with the twists being the incorporation of a carefully designed prior distribution over all possible $\\phi$s, as well as the idea of kernelization from (Farina et al., 2022). Finally, a variant of the algorithm is proposed to achieve an adaptive version of \"fast rate\" for learning in games, improving (Anagnostides et al., 2022).", "questions": "In the fast kernelized algorithm (Algorithm 6), I wonder if the computation of $\\phi_t$ can be further reduced to matrix multiplication, thus $d^\\omega$ time.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Overall, I think the paper has several notable strengths making it well above the acceptance threshold. \n\n1. The results are strong as it removes several suboptimalities from the prior work and tightens its complexity description for the vast majority of transformation rules that are non-binary. \n\n2. The ideas behind the algorithms are substantially different from that of Lu et al, bringing a novel, complementary perspective to the problem. In general, adaptivity in online learning is typically achieved by either aggregating different nonadaptive subroutines or the \"parameter-free\" type of approaches. Their connections and differences have provided interesting insights to the field, and the present work contributes to this thread as well. \n\n3. The application to the fast rates in games is a nontrivial addition. \n\n4. Writing is exceptionally clear despite the complicated technicalities. \n\nOn the flip side, I would suggest adding an in-depth discussion on the computational complexity. I understand the key motivation of this adaptive $\\Phi$-regret problem as providing a beyond-the-worst improvement over the classical Blum-Mansour algorithm, therefore BM could be seen as the natural baseline. There, given the fixed point computational oracle which is matrix multiplication time ($d^3$ in practice but $d^\\omega$ in theory), the essential online learning occurs in a $d^2$ dimensional space, therefore the fixed point oracle is the only computational bottleneck and there has been some attempts accelerating it (such as power method, discussed in Appendix I.3 by Zhang et al. 2024). (Lu et al, 2025) is computationally similar, but in the present work the essential online learning appears to take $d^3\\log d$ time per iteration for both of the two proposed algorithms, dominating the fixed point computation. This makes the comparison to BM and Lu et al a bit more subtle, and some clarification would be nice. \n\nZhang, Brian, et al. \"Efficient $\\Phi $-Regret Minimization with Low-Degree Swap Deviations in Extensive-Form Games.\" Advances in Neural Information Processing Systems 37 (2024): 125192-125230.", "was_revised": false, "final_justification": "", "rebuttal": ">Q1: In the fast kernelized algorithm (Algorithm 6), I wonder if the computation of $\\phi_t$ can be further reduced to matrix multiplication, thus $d^\\omega$ time.\n\nThis is an excellent question. In fact, we now realize that each $\\\\phi\\_t$ can be computed in $\\\\mathcal{O}(d^2)$ time (so better than the $\\\\mathcal{O}(d^3)$ time we provided in Algorithm 6 and also better than what the reviewer suspected, $\\\\mathcal{O}(d^{\\\\omega})$).\nThis makes the computational complexity of our algorithm exactly the same as Blum-Mansour and Lu et al. [2025].\nWe provide the proof below and will update Algorithm 6 this way in the next version.\nThanks again for your comment.\n\nFirst, note that using the definition of $\\\\phi\\_{t+1}$ in Algorithm 6 and the definition of $\\\\psi^k$, one can verify that the entry of $\\\\phi\\_{t+1}$ takes the following form: if $i\\neq j$,\n\\\\[\n\\(\\phi_{t+1})\\_{ij}=\n\\\\begin{aligned}\n\\\\frac{d-1}{c\\_{t}d(d-2)}(V\\_t)\\_{ij}\\\\left(\\\\frac{d-2}{d-1}(C\\_t)\\_{ij}+\\\\frac{1}{d(d-1)}(S\\_t)\\_i+\\\\frac{1}{d-1}(C\\_t)\\_{i,d+1}\\\\right),\\\\end{aligned}\n\\\\]\n\nif $i=j$,\n\\\\[\n\\\\begin{aligned}\n\\(\\phi_{t+1})\\_{ij}=\n\\\\frac{d-1}{c\\_{t}d(d-2)}(V\\_t)\\_{ij}\\\\left(\\\\frac{d-2}{d-1}(C\\_t)\\_{ij}+\\\\frac{1}{d(d-1)}(S\\_t)\\_i+(d-1)(C\\_t)\\_{i,d+1}\\\\right), \n\\\\end{aligned}\n\\\\]\n\nwhere\n\n - $V_t\\\\in\\\\mathbb{R}^{d\\\\times d}$ is defined by $(V\\_t)\\_{ik} = \\\\frac{\\\\exp(-\\\\eta(L\\_t)\\_{ik})}{\\\\sum\\_{j=1}^d \\\\exp(-\\\\eta(L\\_t)\\_{ij})}$ and can be calculated in $\\\\mathcal{O}(d^2)$ time.\n - $c_{t}\\\\in \\\\mathbb{R}$ is defined as\n$\\\\frac{1}{d} \\\\sum\\_{k=1}^d\\\\prod\\_{i=1}^d\\\\left((V\\_t)\\_{ik}+\\\\frac{1}{d(d-2)}\\\\Big) + \\\\prod\\_{i=1}^d\\\\Big((V\\_t)\\_{ii}+\\\\frac{1}{d(d-2)}\\\\right)$. With $V\\_t$, $c\\_{t}$ can be computed in $\\\\mathcal{O}(d^2)$ time.\n - $C_t\\\\in\\\\mathbb{R}^{d\\\\times (d+1)}$ is defined as follows: for all $k\\\\in[d]$, $(C\\_t)\\_{ik} = \\\\frac{(v\\_{t})\\_k}{(V\\_t)\\_{ik}+\\\\frac{1}{d(d-2)}}$ and $(C\\_t)\\_{i,d+1} = \\\\frac{u\\_t}{(V\\_t)\\_{ii}+\\\\frac{1}{d(d-2)}}$\nwhere $(v\\_{t})\\_k = \\\\prod_{i=1}^d((V\\_t)\\_{ik}+\\\\frac{1}{d(d-2)})$\nand $u\\_t = \\\\prod\\_{i=1}^d((V\\_t)\\_{ii}+\\\\frac{1}{d(d-2)})$.\nAgain, with $V\\_t$, $v\\_t$ and $u\\_t$ can be computed in $\\\\mathcal{O}(d^2)$ time, and then $C\\_t$ can be computed in $\\\\mathcal{O}(d^2)$ time too.\n - $S\\_t\\\\in \\\\mathbb{R}^d$ is defined by\n$(S\\_t)\\_i = \\\\sum\\_{k=1}^d (C\\_t)\\_{ik}$ for $i\\\\in [d]$. With $C\\_t$, $S\\_t$ can be computed in $\\\\mathcal{O}(d^2)$ time too.\n\nTherefore, it is now clear that computing $\\\\phi\\_{t+1}$ also only takes $\\\\mathcal{O}(d^2)$ time."}]

Author rebuttal:

Meta-review: This paper was met with unanimous enthusiasm from all four reviewers. The work introduces a new framework for achieving comparator-adaptive Phi-regret that is simpler, more efficient, and achieves tighter bounds than previous state-of-the-art methods. A key contribution is the extension of these results to game theory, providing the first adaptive and accelerated convergence rates to Phi-equilibria. The authors' rebuttal was comprehensive and successfully addressed all reviewer concerns, including a key point about computational complexity that led one reviewer to raise their score. The work is certainly strong enough for a spotlight presentation.
Decision: Accept (spotlight)