Efficient Kernelized Learning in Polyhedral Games beyond Full Information: From Colonel Blotto to Congestion Games
Authors: Andreas Kontogiannis
Vasilis Pollatos
Gabriele Farina
Panayotis Mertikopoulos
Ioannis Panageas
Venue: NeurIPS 2025 poster ()
Keywords: Colonel Blotto
Congestion Games
CCE
No-Regret Learning
Kernelization
Primary area: theory
TL;DR: We provide computationally efficient payoff-based learning algorithms which significantly improve upon prior work in terms of runtime for learning CCE

Abstract: We examine the problem of efficiently learning coarse correlated equilibria (CCE) in polyhedral games, that is, normal-form games with an exponentially large number of actions per player and an underlying combinatorial structure—such as the classic Colonel Blotto game or congestion games. Achieving computational efficiency in this setting requires learning algorithms whose regret and per-iteration complexity scale at most polylogarithmically with the size of the players’ action sets. This challenge has recently been addressed in the full-information setting, primarily through the use of kernelization; however, in the more realistic partial information setting, the situation is much more challenging, and existing approaches result in suboptimal and impractical runtime complexity to learn CCE. We address this gap via a novel kernelization-based framework for payoff-based learning in polyhedral games, which we then apply to certain key classes of polyhedral games—namely Colonel Blotto, graphic matroid and network congestion games. In so doing, we obtain a range of computationally efficient payoff-based learning algorithms which significantly improve upon prior work in terms of the runtime for learning CCE.

of Efficient Kernelized Learning in Polyhedral Games beyond Full Information: From Colonel Blotto to Congestion Games
Andreas Kontogiannis'
Vasilis Pollatos
Gabriele Farina MIT
NTUA & Archimedes/ / Athena RC
NKUA Archimedes/ Athena RC
Panayotis Mertikopoulos
Ioannis Panageas UC Irvine Archimedes / Athena RC
Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP LIG 38000 Grenoble, France Archimedes/ Athena RC
Abstract
We examine the problem of efficiently learning coarse correlated equilibria (CCE) in polyhedral games, that is, normal-form games with exponentially large number of actions per player and an underlying combinatorial structure suchhsuchhhh as the classic Colonel Blotto game congestion games. Achieving computational efficiency in this setting requires learning algorithms whose regret and per-iteration complexity scale at most polylogarithmicall with the size of the players' action sets. This challenge has recently been addressed in the full-information setting, primarily through the of kernelization; however, in the more realistic partial information setting, the situation is much more challenging, and existing approaches result suboptimal and impractical runtime complexity learn CCE. We address this gap via a novel kernelization-baate -aased framework for payoff-based learning in polyhedral games, which then apply certain key classes of polyhedral games-namely Colonel Blotto, graphic matroid and network congestion games. In so doing, we obtain range of computationally efficient payoff-basee learning algorithms which significantly improve upon prior work in terms of the runtime for learning CCE.
Introduction
Learning dynamics for computing equilibria games have been extensively studied over recent decades. The origins trace back to the work of Brown and Robinson in the 1950s (2 51 who introduced and analyzed fictitious play. major conceptual breakthrough came with Blackwell's approachability theorem (16), which laid the foundation for the field of online learning and, in particular, for the development no-regret learning 23 Several influential learning algorithms--
such multiplicative weights update (MWU) [7], gellow-thereggulaiize-eeeee
[54). and follow-the-
perturbed- -eaderr [37] have been shown to satisfy the no-regret property. These algorithms typically maintain probability distribution (commonly referred to "policy") over actions and update iteratively, with per-iteration complexity that is polynomial in the number of actions.
Remarkably, no-regret algorithms can be used as black-box in repeated games under the full- information setting, where each player observes the cost of all available actions, to recover well- established equilibrium concepts, such as coarse correlated equilibria (CCE). The no-regret property of great importance for learning in games, as it guarantees that the time-average cost of any player using such an algorithm is no worse than the cost of the best fixed action in
'Equal contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

how the other players choose their actions. Consequently, if all players adopt no-regret algorithms, the learning dynamics converge to CCE.
motivation and challenges. In this paper, we focus on the problem of learning CCE in multi-player games with combinatorial structure and large action spaces where the players simultaneously use no-regret learning dynamics for ''' rounds. Specifically, we consider polyhedral games (32) (also dubbed linear hypergraph games [12), a rich class of normal-form games where the actions per player are d-dimensional binary vectors with at most m S d ones.
Polyhedral Games:
Polyhedral games capture important classes of games with large action sets, including the well-studied Colonel Blotto game [18), congestion games (52), extensive-form games [40], and dueling games 36). For example, in multi-phl playerr Colonel Blotto games, each player must allocate soldiers among k battlefields. where n is typically much larger than k. In this case, using the one-hot representation (see Section 4 we have that m = k; d = nk and N = -"*=11 ) with the latter being of order nz* In graphic matroid congestion games, given undirected graph G(V, E), each player must choose spanning tree, that is the basis of graphic matroid of rank V 1. In this case m V 1, d = E and N is of order IVI, Similarly, in network congestion games, each player needs to choose path from 8 + t, and the maximal path length is K. Here, m = K, d = [ and N is of order |E|
In all the aforementioned examples, the number of actions N per player, grows exponentially with m (approximately of order d'"), and as a result the vanilla learning methods for finding CCE become computationally inefficient since their per-iteration complexity is polynomial in N and not polynomial in d, m. This computational challenge has recently been addressed the full-information setting. Beaglehole al. [12] demonstrated how perform approximate fast sampling from the MWU distribution in specific polyhedral games (including the Colonel Blotto and graphic matroid congestion games). However, their approach is somewhat restrictive beyond approximately sampling from MWU, and thus sub-optimal in convergence rate, as it is unknown how to use their techniques efficiently deploy the near-optimal Optimistic MWU 300 in such game settings. In contrast, Farina et al. 32] proposed an efficient general methodology to simulate the exact MWU (which allows to use optimism) algorithm via kernelization, requiring only ((d) kernel computations (see Section 2 for a formal definition) per iteration for any polyhedral game. In particular, the kerneiization approach developed in 32 has led to state-of-the-art runtime to find CCE in extensive-form games,
as recently established in 31.
However, the applicability of kernelization polyhedral games remains largely unexplored beyond the full-information setting-that is, in the bandit (and also semi-bandit) feedback settings. These settings are of particular interest in practice, as the full-information all available actions are revealed after each round-is often unrealistic. In contrast, bandit feedback reflects a more practical regime in which only the cost of the selected action observed. For example, learning under full-infone inllrfffoomaton feedback in network congestion games would impractically require each player to be able to observe the cost of all paths of the network, rather than just the cost of the path she actually chose.
couuppiion-wherr the costs of
In order obtain equilibrium convergence guarantees in bandit setting, the learning dynamics of each player must satisfy no-realized-regret guarantees that hold with high probability against adaptive adversaries (i.e., assuming that the other players can potentially adjust their policies based on the player's ' past actions)-a stringent and technically demanding requirement. This stands in contrast to the more commonly studied expected regret from the online learning literature (e.g., see 38 24 26).. An even more challenging, but very practical, requirement is to ensure that the learning dynamics achieve an efficient runtime complexity to find CCE, with minimal dependence on the game parameters d and m, while still maintaining the no-regret property with favorable dependence on T as much as possible.
Many algorithms from the bandit linear optimization literature 41 can be leveraged to learn e-CCE in polyhedral games. Bartlett et al. [11] provide algorithm with high probability guarantees that achieves a VT regret bound, albeit requiring a prohibitive per-iteration complexity of PN)y The well-established GEOMETRICHEDE
algorithm (also known as COMBAND (24,, or EXP2 (22))
originally proposed by Dani et al. 28 has been shown to achieve 22/3 regret with high probability
53 19
Despite GEOMETRICHEDGE being a classical algorithm in the literature, how to efficiently
"The runtime of an algorithm for finding an equilibrium is defined as the product between the number of iterations I' needed to compute the equilibrium and the algorithm's per- iteration complexity.
2

---

implement it remains generally unclear, with path planning being the only setting where efficient
implementations (e.g., via weight pushing [58: 62 631) were known prior to our work. Recently, Lee et al. [22 and Zimmert and Lattimore 655 proposed algorithms for continuous action spaces-
can be extended to polyhedral games using the same techniques as Abernethy et al. T acchieiing a regret bound of (mmd//2 /T) and O(md2 vT), respectively. However, the above bounds combined with a per-iteration complexity D which suboptimally depends on d, result in impractical runtime complexity results for learning e- E-CCE. In particular, the runtime of the algorithm in 44 to find e-CCE scales as d' while that of [65] scales as bo-both exhibiting impractically large dependence on the game parameters. Even more recently, the concurrent work of [46] proposed an algorithm for online shortest paths in DAGs with a near-optimal regret bound of ( (ETT). However, their algorithm also comes with a polynomial yet impractical runtime complexity to find an approximate CCE stemming from ellipsoid method calls and other costly procedures.
Given the impractical runtime complexity results of the aforementioned approaches for learning CCE in polyhedral games, in this paper, we aim to address the following question:
Can kernelization techniques be extended beyond the full-infor tull-information setting to de- sign no-regret learning dynamics for computing CCE with state-of-the the-art runtime minimal dependence on the game parameters d and m.?
Main Contributions and Techniques. In this paper, we answer the above question affirmatively.
Due to the exponentially large (in m) per-player action sets in polyhedral games, designing efficient payoff-based learning algorithms involves addressing three primary challenges: (a) fast calculating the loss estimators which are used to update each player's 's policy, (b) fast sampling from each player's policy, and (c) ensuring that each player achieves efficient no-realized-regre guarantees, which imply efficiently learning E-CCE.
To face the above challenges, we propose kernelization- framework, which allows us to efficiently implement standard loss estimators from bandit linear optimization. Specifically, in the bandit setting (Section (.1), we propose kernelized customization of the well-established
GeometriCHEDGE algorithm (2 (see Algorithm[] [ In contrast to the full-information setting, where the approach of [32] required the first moments of MWU distribution, in the bandit setting, we require the second moments of MWU, needed to construct the unbiased combinatorial bandit estimator (28) 244. Importantly, we show that we can efficiently calculate such second moments via only (dd²) kernel computations (Theorem 3.1). In the semi-bande setting, our approach (see Section 3.2) utilizes the implicit exploration loss estimator [48] which, we show that is compatible with the kernels used for the first moment of MWU. In addition, we propose general efficient sampling scheme (Procedure SAMPLING in Algorithm T. based on kernelization, which only requires extra (d) kernel computations.
Apart from improvements in the per-iteration complexity, our analysis provides the following no- regret results for learning in polyhedral games: In the bandit setting. we achieve
regret with high probability (Theorem 3.2), improving upon baselines [53] 19] in the dependence on the game parameters. Moreover, we achieve better regret than (65 in the realistic regime where
T S d= Regarding the semi-bandit setting, we achieve Ó(m Td) regret with high probability (Theorem 3.4), which is factor /m worse than the optimal expected regret guarantee 88. To the best of our knowledge, this is the first high probability result on the general setting.
To showcase the power of our general framework, we study three important classes of polyhedral games: the multi-player Colonel Blotto, graphic matroid and network congestion games.
In Colonel Blotto games, we use kernelization techniques based on the generator function induced by the game's combinatorial structure, in order to efficiently compute the required kernels. Remarkably, our kernelization- based approach operates directly on the geometry of the Colonel Blotto game, by allowing us leverage an efficient (((kk)-reprseenn) -representation. Prior work had only been able to operate with DAG representations of the set, leading to suboptimal formulations with O(n2k) edges. As shown in Table [ (and stated in Theorem 4.4. in the bandit setting, our approach learns an c-CCE in time ① (n2+w10rn k6+ )e²) wheree w is the multiplication exponent (currently the best known is
"The per-iteration complexity of the algorithm in 42 is (dd) due to the fact that the optimization step is solved via an interior point method (see (2). while that of 65 is (dd) due to the pre- processing step needed
sample from log-concave distribution (see 44
3

---

Algorithm
Runtime to c-CCE
Representation
Feedback
Bcaglehole et al.
Önk'' /E²)
(I
Full-Info
Our Work
O([Pink]
((nk)
Full-Info
Our Work
(n"
((nk)
Semi-Bandit
Leon et al. 45
Ö n
max
n
(nn*k)
Bandit
Arii
Zimmert and Lattimore 65
((m""k"11 (1 fE
(
Bandit
Our Work
①
O(nk)
Bandit
Table I: Comparison of results in Colonel Blotto games, split by feedback type (full-information,
semi-bandit, and bandit). t: The approach of [65] is evaluated using the layered graph polytope [6]]
of size n² k. The runtime of [4] depends the arbitrarily large 1/Amin that is, the inverse of the
minimum eigenvalue of E[vv") under the exploration distribution.
Algorithm
Runtime to c-CCE
Feedback
Algorithm Runtime to s-CCE
Feedback
12
((VV1%=*)
Full-Info
B5
Õ(E + - K2/-²)
Semi-Bandit
Our Work ((PPIV]"(VV" |
[BIV/e
Full-Info
49
0(1E) /E")"
Semi-Bandit
Our Work
Semi-Bande
Our Work 5(EB1=*3/EE)
Semi-Bandit
65
Bandit
65
0(1E)*^29/33
Bandit
Our Work Ō (111)=+ (EI)/")
Bandit
Our Work 0(1E)==**/6>)
Bandit
Table 2: Comparison in Graphic Matroid Con- gestion Games. To assess [65] we used the polytope representation of [47 that uses d [V|3 and has a small number of constraints.
Table 3: Comparison of results in Network Congestion Games. *: The algorithm pro- posed in [49] also achieves convergence to Nash equilibria, albeit with slower rates.
thereby significantly improving over (65] in the dependence on the game parameters by a factor = n 13222 In the semi-bandit setting, our approach learns an e-CCE time O (n? /E?).
2.372 5
In graphic matroid congestion games, we design kernelization techniques based on the celebrated Matrix-Tree Theorem [59]. To reduce amortized kernel computation time, we use fast rank-1 updates of the LU decomposition of Laplacian matrices based on the structure of the required kernels. Moreover, we perform efficient exact sampling via an incremental kernelization approach. As shown in Table
2 (and also in Theorem 5.2). in the bandit setting, approach Iearns an e-CCE in time 8 (IV] + (=)) significantly improving upon the very impractical dependence |V|29 of (65). In the semi-bandit setting, our approach learns an e-CCE in time ((
O E ((E))
Remark 1.1. We can combine our kernelization results for Colonel Blotto and graphic matroid congestion games with the null-information framework developed in (32) to yield 1/c convergence to e-CCE in these games-thus addressing an open question of Beaglehole et al. [12]
Remark 1.2. Our kernelization techniques developed for graphic matroids (see Lemma 5.1 allow spanning trees thus, to the the best of our
efficiently implement GEOMETRICHEDGE knowledge, resolving an open question posed by Cesa-Bianchi and Lugosi (24).
In network congestion games, our framework improves upon 35
65 For summary of our results, we refer to Table Due to space constraints, our formal results can be found in Appendix I Further details on existing approaches for each of the above games can be found in Appendix A
Preliminaries
Polyhedral Games. this paper, we consider Polyhedral Games, a structured class of normal- form games with exponentially large action sets, where each action can be represented binary

---

d-dimensional vector of at most m ones and the incurred cost is linear in the action vector. For simplicity, here we assume that all players have the same action sets. Formally. we represent polyhedral game as tuple G = (P, V. {T,) ). The set P defines the set of players, each of which is assigned unique player identifier in [P]] := 21.2..... [P]]. The finite set V C Rd of size N represents the actions available each player E [[PI], such that for any v E V, ||lll I m. We denote by - all agents except i. We define the loss vector function L VIPl + R4 L; : VIPI + R+ is the cost function, which is linear in Uy that is, L((u;u-)) = {by v-.)
Online Learning Setup in Polyhedral Games. In polyhedral game dynamics under partial- information feedback, each player iteratively updates her strategies based on the feedback she receives about the loss. We consider the bandit and semi-bandit settings. In the semi-bandit setting, each player selects action U; V. and receives the losses (j) of the loss vector L = (1;; v-4) for all j such that (i( = 1. In the bandit setting, each player receives only L,(1;,=)))
However, it is not clear how a selfish player should update her strategy in order to minimize her overall loss, since the strategies of the other players can arbitrarily change over time. Thus, player i tries to minimize her experienced loss under the worst-case assumption that the loss of each coordinate selected by malicious adversary.
Based on the above, we focus on the single-player's perspective and examine an abstract-online learning-moel,, where each player is a decision maker interacting with an unknown and potentially adversarial environment. At each round / = 1, 1.,..... T of the online learning process, the decision maker samples an action V2 E from a probability distribution Pt A(V). Subsequently, the environment chooses loss vector le Ted potentially in an adversarial fashion. This is the same setup adopted in [49] 27. Given any round T, we define the regret up to round T as follows:
T 0 lr
RT
la min
1=1
We note that the above notion measures realized regret, that is, it measures the performance of the algorithm based on the actions sampled from the distribution pt. We say that players are playing no-regret learning in the game if each one of them achieves sublinear regret.
prominent result in the theory of learning games establishes a celebrated connection between no-regret learning and CCE of the game (which, in two-player zero-sum games, are Nash equilibria).
Theorem 2.1 (Informal, 34
Suppose IP players are playing no-regret learning in the game. Let dipi be the time-average joint actions over T rounds. Then, o* forms
o² == + E u an T 'max I......., apprrxiapto CCE of the game, where RT is the regret for the i-th player at the T-th round.
Kernelized MWU. Multiplicative Weights Update (MWU) is online learning algorithm that iteratively updates a distribution Pt over actions in V. Let po := M
1 1 E A(V). The MWU rule at
each time step t is pv(v) x Pt-1(v) e mw)e(v) Ve E V. In the standard MWU variant we set
Wt : 1, where - is the loss vector observed at t - 1. By setting w; := 26,-1 l we derive the Optimistic MWU (OMWU) algorithm (30], which achieves constant regret (up to logarithmic factors), and thus 1/2 convergence to CCE in the context of learning in games.
In polyhedral games, we are interested in the efficient calculation of moments of the MWU distribution. For this aim, a useful tool introduced in [58] 32) is the kernel function Rd x I + R defined as follows: Ky y) EvEv [)=E=())= x(j) v().. The next theorem shows how to compute the first moment of Pt via + 1 kernel computations.
Theorem 2.2 (First Moment Calculation, distribution, Pt, can be calculated as follows:
32 all rounds 2 0, the first moment of the MWU
E Eunpe [0] (1
K Kv(Cr,
Kv(Cr,ed) Ky(Ci, 1)
1y(C,,1)
where C,()= == exp {- -- 13 (i) and e,(h) = 1(h + j}. for h E (d]
5

---

Kernelized Payoff-based Learning in Polyhedral Games
In this section, we design a framework for efficient payoff-basse learning in polyhedral games, under bandit and semi-bandit feedback. Upon this framework, we build learning algorithms, which achieve efficient no-realized-regre learning with high probability guarantees against adaptive adversaries-a key requirement to show convergence to CCE. For algorithms to be efficiently implementable, as we will see, it suffices that the kernels used constructing the loss estimators and for sampling (highlighted in orange in Algorithm[[] (T) can be computed efficiently. This can be achieved by effectively leveraging the game's 's combinatorial structure, as we will explain in depth later in the paper. For the remainder of this section, assume that we have oracles for calculating the required kernels. In the next sections, we will demonstrate how our algorithms can be implemented efficiently in prominent examples of polyhedral games.
3.1 Kernelized GEOMETRICHEDGE for Bandit No-Regret Learning
Algorithm 1: Kernelized GEOMETRICHEGDA
Data: d, m, > 0, 7 E [0. Compute
bwr.eeerrceiiiippeeerrrrr B Initialize 4o = [1/N, 1/N] A(V), {ll E BJ, co(i) = 0 and Co(i) = 1, Vj [d]
for tort11 1,..,, do
Mixing: Pr = (1- ()- yH, where T: MWU(C,)
Compute the kernels: Kv(C,-1,1) and (k Vj.j' [d]
Sample 82 (1 7)SAMPLING()), C.-1) 7
Observe the bandit loss L, U.
Compute (g)) using Theorem 3.1 and set E, (1 7))E{ 2 BBB
Compute the unbiased loss estimator:
2- 1 U2
10
Update the aggregated loss estimators:
a(j) = c-1 (()),, Vj E [d]
11 Update the exponential cumulative estimators:
C+(j) = (7)(--))()),,
12
13 Procedure: SAMPLING
14 Input: V.C
Sample v[1] ~ Be (1
Kv(C.E)) Kv[C,1]
16 for j = 2,... d do
Compute the kernel: Ky()
Set V(j) (v' E V: v'(i] v[],, Vi -1]} and pj (C.1
Kum (C,a,)
19
Sample v[ii- ~ Be(p,)
20
Return: V
We present our first algorithm, which establishes efficient no-regret learning polyhedral games under bandit feedback. Our algorithm (Algorithm is a kernelized customization of GEOMETRICHEDGE 28 a classical algorithm in the study of combinatorial bandits [4T]. Despite GEOMETRICHEDGE being an algorithm with well-studied expected regret analysis, how to efficiently implement it remains largely unclear. The primary challenges in applying the vanilla method are the following:
Calculating Σ E[ee") needed to construct the unbiased loss estimates which will be used by MWU routine in poly(d, m) time.
2. Sampling from MWU in poly(d, m) time.
In this paper, we tackle the above challenges in the context of polyhedral games (however, our approach can also be applied to the well-studied combinatorial settings discussed in (24). The main idea of our approach is to utilize a loss estimate for each coordinate j E [d]. which can be

---

kernelized efficiently, and simulate MWU using a fast sampling schema based on the computed kernels. Subsequently, we present the main components of our approach.
Second Moment Kernelization. Algorithm I uses a distribution pt which is the mixture between a MWU distribution qe and the uniform distribution, μ., over a 2-approximate barycentric spanner of V. Due to space constraints, we prompt the interested reader to Appendix [D for background on barycentric spanners. In contrast the full-information setting, where kernelized MWU (32) requires the first moment of the MWU distribution to simulate the update rule, our algorithm also requires the second moment of Pt (i..,, the autocorrelation matrix, denoted by Σ,) construct the standard unbiased estimator of GEOMETRIC HEDGE (Step 9). Through Step 8, it suffices to efficiently calculate (g)), , that is the autocorrelation matrix under the law of qt. which in general was not known how to efficiently compute prior to our work (with the only exception being path planning problems where weight pushing techniques [8 53 can be applied).
For this purpose, we will make use of kernelization. The next theorem shows that we can efficiently calculate the second moment of q: using only d² + kernel computations [
Theorem 3.1 (Second Moment Calculation). Lei Ee():) := --EEv ((()) (vo")) be the autocorrela- tion matrix under the law of a MWU distribution qu- Then, for all j.j E [d].
Ee(g:)li.3'' 1 Kv(Ci, 8ÿ) + Kv(C,,Ey) K Kv(Cr,
Kv(C,, 1)
where Eny = 1 ( j and h + for h M,J [d] and (h))) = [ + for h [d].
Kernelization implies efficient exact sampling. Based on kernelization, we propose an efficient sampling scheme (Procedure SAMPLING in Algorithm I that only requires extra d kernel compu- tations. We are interested in sampling v ~ Pt- By using the chain rule on the probability of the intersection events, we derive the following:
Pt (v) Pr[ Pr((()))))) ... (frp)))))))())))P(()))))(())...,
o(d 1)]
(2)
It is easy to see that the j-th term of the above product equals the j-th coordinate of the first moment kernelization (see Theorem 2.2 and Observation 3.3) of the conditional polytope V the polytope which has the first Based on this, we iteratively sample each coordinate j E [d] from a Bernoulli distribution (Step 19),
coordinate values equal to the 1 sampled values (Step 18).
which has probability equal to P. Pr(u())l((),..... "Ij 1)] 1 (vC)(C.))
(y,)((C (Step 19).
Improved regret dependence on the game parameters. Our analysis differs from that of the original paper of GEOMETRICHEDGE (28. which studied expected regret. Importantly, we improve upon prior analyses [53] 19), which also studied the realized regret of the algorithm, by reducing the regret's dependence minimum eigenvalue, Amin. of the autocorrelation matrix under the law of the initial distribution. In particular, we achieve this by using more careful analysis on the effect of the barycentric spanner to the variance of the estimator. The following theorem shows that Algorithm Tis is no-regret.
d and m, while avoiding dependence on the possibly exponentially small
Theorem 3.2 (No-Regret under Bandit Feedback). For T 2 8dLm by setting = d2/3m 1/ and T173
Algorithm i achieves regret Ry S O(dP/3mm with high probubility.
1) 1777777/87177
3.2 The Semi-Bandit Feedback Case: Kernelizing Implicit Exploration
Now, we discuss our second learning algorithm for polyhedral games which establishes efficient no-regret learning under semi-bandit feedback. The main idea is similar to that of the bandit setting- that is, we utilize a loss estimator for each coordinate j E [d], which can be kernelized efficiently, and use the SAMPLING procedure fast sample from a MWU routine using the computed kernels. Due to the exponentially large action set V, one challenge here is that it is intractable to brute-force over V in order to compute the unconditional probabilities, Pr(vx(s) 1}. of selecting j [d] as an active coordinate, needed to compute the standard loss estimators used in adversarial multi-armed bandits (MABs) [41] The following observation suggests that we can kernelize such loss estimators.
'Related results were concurrently shown in 55 to compute the Hessian of self-coneordant function, which is needed to implement Newton's 's method.
7

---

we can compute the first moment 2t, which it turns out to provide the probabilities needed to compute the standard loss estimators used in adversarial MABs,
Observation 3.3. Using Theorem 2.2
since for any E [dl, we have that mn(()) == Evrpp [1 [T((j) = 1}] = Pr(c())=11
Our algorithm (Algorithm in Appendix B) kernelizes the implicit exploration (IX) loss estimator, f.( + 1
(.)) =
(ve(s) = 1}, proposed in [48], which ensures sufficient exploration for each
coordinate j [d] with low variance. Despite the fact that the implicit exploration loss estimator is biased, it satisfies the important property that, with high probability, the aggregated estimator losses are upper bounded by the realized losses plus factor of ((1/)). The following theorem shows that the proposed algorithm is no-regret.
Theorem 3.4 (No-Regret under Semi-Bandit Feedback). By setting = m//dT and 1j = I/T
Algorithm 2 achieves regret Rr S Td) with high probability.
4 Efficient Kernelization in Colonel Blotto Games (CBGs)
We consider the setting proposed in [ for the multiplayer Colonel Blotto game 17
Each player
i [[P[] must allocate soldiers among & battlefields. Let variable 8i,6 denote the number of soldiers allocated by the i-th player to the h-th battlefield. Given the soldier assignments of all players, a per-battlefield loss is defined for each player i [[]] and and the incurred cost of player i is given by the sum of her per-battlefield losses.
@ (nk))- representation. We aim to find succinct vector representations of each player's actions and the loss. One challenge here that we need the action and loss representations to satisfy the definition of polyhedral games- that is, the cost of each action, given the actions of other players, must equal the dot product of the action and loss representations. One such representation is through the layered graph [33 (also used in 160 6 43),, which implies a representation dimensionality of @(n²)) k) that can be a bottleneck for efficiently learning CCE, as shown in Table
Without loss of generality, we focus on player i and drop the subscript i. We use the notation [b/o {0, 1,.., b) for b E N. Let d = (n + 1)k. For any action a E A, we consider its succiner representation v e c {0, 1]dd such that for all h e [k] and [m]].. e[h, s] = iff a assigns s soldiers to the h-th battlefield. We similarly define the representation of the loss L, such that for all h [k] and s [n]o. fh,, s] is the h-th battlefield loss observed when assigning s soldiers to the h-th battlefield, given the assignments of the other players in h.
Remark 4.1. Although the ((nk)) representation is more straightforward to design and more succinct (6]), it is not known how derive a polytope description in
than the (n= -er--arrrpreeeetttuie the form of a small number of linear inequalities with the pure actions as corners-thue common techniques, such Carathéodory decomposition (e.g., (26)) and barrier methods (e.g. [42] 65))
cannot be used. Kernelization overcomes this obstacle by operating directly on the game's 's geometry.
Kernelization.
With the succinct representation established above, we are now ready describe how fast kernel computations are achieved in Colonel Blotto games.
Given weight vectors 2, y {0, 1]dd we define the polynomial (2.)(2) as follows:
A: n
x Th, [[hh,))=" (2) = I
A==1 ==0
The key point is that the n-th coefficient of in (2) generates kernel Kv y). The main idea is as follows. To compute the n-th coefficient o execute running product over the factors of the polynomial. This process involves ls updates of the partial product. After each update, the partial product is truncated down degree n. Thus, inductively we ensure that all multiplications involve polynomials of degree at most n. Based on the above, we derive the following proposition.
Proposition 4.2. For given x, y E {0, 134 kernel Kv(x, y) can be computed in time lngh)
To construct the loss estimators of the proposed algorithms, we need compute d kemeels Ky (C ēÿ), for j E [d]. for the semi-bandit setting and d² kernels Kv E ). for j.3 E [d], for the bandit
8

---

setting, as well as the kemne (C, 1). A naive approach is to use Proposition 4.2 separately for each kernel, resulting in a total kernel computation time O(n" k log n) for the bandit setting and O(n*k² log n) for the semi-bandit.
We provide two algorithms, namely Algorithm 3 and 4 (Appendix G), which speed up the process of computing all required kernels by leveraging the above ideas and appropriate precomputing.
Lemma 4.3. At each round I E (T), all kernely (y(Ct, E1),,,)),. Onk logn). Moreover, all kernels Ky(C,, ). j.3 [d], can be computed in time O(n²
E [d], can be computed in time
Combining the above with the exact sampling procedure provided in [12] (see Algorithm Appendix G.3), based on which we can calculate the required kernels of our SAMPLING procedure in time Onk log n), the per-iteration complexities for the bandit and semi-bandi are On kn log n) and (nk log nt), respectively. Putting everything together, we derive the following main result.
Theorem 4.4 (Runtime learn s-CCE). In Colonel Blotto game, under bandit feedback, if all players adopt Algorithm 2 then the total runtime for finding an e-CCE, with high probability, is (n2++u2++ (2)). Under semi bandit feedback, if all players adopt Algorithm 2 (Appendix By. then the total runtime for finding an e-CCE, with high probabilit, is O(n-k2/e2))
Remark 4.5. If the Colonel Blotto game is two-player zero-sum (a more traditional setting which has received much attention 14 15 4)) then our algorithm learns an c-Nash equilibrium.
5 Efficient Kernelization in Graphic Matroid Congestion Games (GMCGs)
In a graphic matroid congestion game (GMCG), players compete for the edges of connected undirected graph G = (V, E). with the actions of each player being spanning trees in G 64 3 3
We use the incidence vector representation of actions u E {0, 1 and denote by V the set of all these incidence vectors. Given an action profile (v,, v-z), the total loss of player i is the sum of the losses of the selected edges of u; Typically the cost of each edge is equal to the number of players using it but our framework can also handle arbitrary edge cost functions. Next, we will show how to efficiently compute the required kernels and perform efficient sampling in GMCGs.
Kernelization. Given an edge weight vector C' E we make use of the weighted Matrix- Tree Theorem 159
to compute the kernel Kv 1). which states that the value of Erev ILEE C'(e) equals the value of a cofactor of the weighted Laplacian A of the graph, where Au, = Le'eF incident to C(e') and Au, = - C(e) llfe E E} for u + v and edge e = (u, v).
R E
45
A naive approach is to use the Mree Theorem for each kernel separately, taking total time ((E)))V))) for the kernel computations in the bandit and O(EIIV))
(*) in the semi-bandit setting.
We provide an algorithm (see Appendix H) that reduces the amortized time per kernl computation. Notably, the Matrix-Tree Theorem holds for any cofactor of the Laplacian matrix. We leverage this property by making a strategic choice of which row and column to delete. For each edge E [[]]] consider the Laplacian used for the computation of the kernel Ky (C,e,). The Laplacian for this kernel is constructed in the same way as the one we described above for (v 1) but with the difference that C(j) is set to zero. The main idea is that for each node v E V. we can precompute the LU decomposition of A A_o.- -. that is the submatrix of A derived by deleting row and column v, and then for each j = (u, u') E E, we can fast compute kernel K ((C,,)) by computing the determinant of that kernel's 's Laplacian via recursive LU updating [56) in O(VV)). The key point in this analysis is that we can always select submatrix of the kernel's 's Laplacian that only differs in one element than A A-a,-a. Similar arguments can also be used for fast computing (v(C, (..").
Sampling. We provide an efficient implementation of the SAMPLING procedure of Algorithm | for GMCGs (see Appendix H. Algorithm 8). Our approach is based on an iterative kernelization process where we sample each coordinate incrementally. The challenge here is how to perform kernelization on the conditional action set V()), for j E [[E'], induced by the so far sampled coordinates up to j. Interestingly, Vij) operates on underlying multi-graph. The main idea is to transform this multi-graph into meta-graph, where a meta-node merges the nodes of the j-th edge of the initial graph and a meta-edge accumulates the weights of parallel edges connecting the same nodes. First,

---

we show that it suffices to perform kernelization on the meta- geeta-graph (Proposition H. and, based on that, we show that our approach is efficient via an induction argument. Importantly, we derive the following lemma.
Lemma 5.1. At each round [TT, all kernels Ky(C,, Ej), for E [[B|], can be computed in time @ + ( and all kernels Ky(Cr, F3 for j.j E (d,, can be computed in time O( | + [B))) Moreover, SAMPLING(V, C+) can be implemented in time O(EV))V)))
Putting everything together, we derive the following main result.
Theorem 5.2 (Runtime to learn E-CCE), In a graphic matroid congestion game, under bandit feedback, if all players adopt Algorithm 7 then the total runtime for finding an e-CCE, with high probability, is ((E))1116 [[[VVie11 + )=*) Under semi-bandit feedback, if all players adopt Algorithm (Appendix B then the total runtime for finding an e-CCE, with high probability, is
O( 2+w/e= fE²).
Conclusion
In this paper, focused on the problem of efficiently learning coarse correlated equilibrium (CCE) in polyhedral games via kernelization-beyeeee
full-information feedback. In particular, we proposed kernelized no-regret learning algorithms that improve the runtime of state-of-the-art methods in three important classes of polyhedral games, namely Colonel Blotto, graphic matroid and network congestion games.
There are several important open questions for follow-up research:
Most important of all is whether we can design an FPTAS algorithm for efficiently learning correlated equilibria (CE) in polyhedral games; stronger equilibrium notion than CCE,
Another interesting open question is whether we can further leverage kernelization to achieve 1/E² dependence in the bandit setting, with a better dependence on d than Zimmert and Lattimore [65].
Computing Nash equilibria the general setting of the Colonel Blotto games we have studied in this paper is PPAD-hard, as any m-player normal-form game can be polynomially reduced to an m-player Colonel Blotto game. However, what can said about the computa- tional complexity of computing Nash equilibria in Colonel Blotto games with monotone seecewise-constan utility functions (e.g., see 12
We leave these as open questions for future work on the topic.
Acknowledgments
Gabriele Farina supported in part by the National Science Foundation award CCF-2443068, ONR grant NO001422 12001125110 02544222222 1229., and an AI2050 Early Career Fellowship. Ioannis Panageas was supported by NSF grant CCF-2454115. Most of this work was done while all authors were visiting Archimedes Research Unit, Athens, Greece. This work was also supported by the French National Research Agency (ANR) in the framework of the PEPR IA FOUNDRY project (ANR-23-PELA-0003) the grant IRGA-SPICE (G7H-IRG24999 and project MIS 5154714 of the National Recovery and Resilience Plan Greece 2.0 funded by the European Union under the NextGenerationEU Program.
References
[1] Jacob D Abernethy, Elad Hazan, and Alexander Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. In COLT, pages 263-274. Citeseer, 2008
[2] Jacob D Abernethy, Elad Hazan, and Alexander Rakhlin. Interior-point methods for full- information and bandit online learning. IEEE Transactions on Information Theory, 58(7): 4164-4175, 2012.
10

---

[3] Heiner Ackermann, Heiko Röglin, and Berthold Vöcking. On the impact of combinatorial structure on congestion games. Journal of the ACM (JACM), 55(6):1-22, 2008.
[4] AmirMahdi Ahmadinejad, Sina Dehghann, MohammadTaghi Hajiaghayi, Brendan Lucier, Hamid Mahini, and Saeed Seddighin. From duels to battlefields: Computing equilibria of blotto and other games, Mathematics of Operations Research, 14(4):13041135, 2019.
[5] Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. TheoretiCS, 3, 2024.
[6] loannis Anagnostides, Gabriele Farina, Christian Kroer, Chung-We Wei Lee, Haipeng Luo, and Tuomas Sandholm. Uncoupled learning dynamics with Oflog 7') swap regret in multiplayer games. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28- December 9, 2022, 2022.
[7] Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta-algorithm and applications. Theory of computing, 8(1):121-164, 2012.
[8] rean-Yves Audibert, Sébastien Bubeck, and Gábor Lugosi. Regret in online combinatorial optimization. Mathematics of Operations Research, (9(1):31-44) 2014.
[9] Baruch Awerbuch and Robert Kleinberg. Online linear optimization and adaptive routing. Journal of Computer and System Sciences, 74(1)-97-114, 2008
[10] Baruch Awerbuch and Robert D Kleinberg. Adaptive routing with end-to-end feedback: Dis- tributed learning and geometric approaches. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 45-53, 2004.
[11] Peter Bartlett, Varsha Dani, Thomas Hayes, Sham Kakade, Alexander Rakhlin, and Ambuj Tewari. High-probability regret bounds for bandit online linear optimization. In Proceedings of the 21 Annual Conference on Learning Mheory-COLL 2008, pages 335-342. Omnipress, 2008.
[12] Daniel Beaglehole, Max Hopkins. Daniel Kane, Sihan Liu, and Shachar Lovett. Sampling equilibria: Fast no-regret learning in structured games. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3817-3855, SIAM, 2023.
[13] Soheil Behnezhad, Sina Dehghani, Mahsa Derakhshan. MohammadTaghh HajiAghayi, and Saeed Seddighin. Faster and simpler algorithm for optimal strategies of blotto game. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
[14] Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan, MohammadTaghi HajiAghayi, Moham- mad Mahdian, Christos H Papadimitriou, Ronald L Rivest, Saeed Seddighin, and Philip Stark. From battlefields to elections: Winning strategies of blotto and auditing games. In Proceedings of the Twenty-inthh Annual ACM-SIAM Symposium on Discrete Algorithmss pages 2291 2291-2310 10.0. SIAM, 2018.
[15] Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan, Mohammad Taghi Hajiaghayi, Christos H Papadimitriou, and Saeed Seddighin. Optimal strategies of blotto games: Beyond convexity. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 597-616,
2019.
[16] David Blackwell. An analog of the minimax theorem for vector payoffs. 1956.
[17] Enric Boix-Adserà, Benjamin L Edelman, and Siddhartha Jayanti. The multiplayer colonel blotto game. In Proceedings of the 21st ACM Conference on Economics and Computation, pages 47 2020.
[18] Emile Borel. The theory of play and integral equations with skew symmetric kemelss. Econo- metrica: journal of the Econometric Society, pages 97-100, 1953.
[19] Gábor Braun and Sebastian Pokutta. An efficient high-probability algorithm for linear bandits. arXiv preprint arXiv.1610.02072, 2016.

---

[20] EO Brigham. The fast fourier transform and its applications, 1988.
[21] George W Brown. Iterative solution of games by fictitious play. Act. Anal. Prod Allocation, 13 (1):374 1951.
[22] Sébastien Bubeck, Nicolo Resa-Bianchi, and Sham M Kakade. Towards minimax policies for online linear optimization with handit feedback. In Conference on Learning Theory, pages
41-1, JMLR Workshop and Conference Proceedings, 2012.
[23] Nicolo
and Gábor Lugosi. Prediction, learning, and games. Cambridge university
press, 2006.
[24] Nicolo Cesa-Bianchi and Gábor Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 78(5):1404 1422, 2012.
[25] Xi Chen and Binghui Peng. Hedging in games: Faster convergence of external and swap regrets. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors. Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[26] Richard Combes, Mohammad Sadegh Talebi Mazrach Shahi, Alexandre Proutiere, et al. Com- binatorial bandits revisited. Advances in neural information processing systems, 28, 2015.
[27] Leello Dadi, Ioannis Panageas, Stratis Skoulakis, Luca Viano, and Volkan Cevher. Poly- nomial convergence of bandit no-regret dynamics in congestion games. arXiv preprint arXiv:2401.09628, 2024.
[28] Varsha Dani, Sham M Kakade, and Thomas Hayes. The price of bandit information for online optimization. Advances in Neural Information Processing Systems, 20, 2007.
[29] Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. Near-optimal no-regret algo- rithms for zero-sum games. In Dana Randall, editor, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 201 pages 235-254. SIAM, 2011.
[30] Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. Advances in Neural Information Processing Systems, 34:27604-
27616. 2021.
[31] Zhiyuan Fan, Christian Kroer, and Gabriele Farina. On the optimality of dilated entropy and lower bounds for online learning in extensive-form games, Advances in Neural Information Processing Systems, 37:88373-8844 88849,, 2024.
[32] Gabriele Farina, Chung- Wei Lee, Haipeng Luo, and Christian Kroer. Kernelized multiplicative weights for 0/1-polyhedral games: Bridging the gap between learning in extensive-forn and normal-form games. In International Conference on Machine Learning, pages 6337-6357. PMLR, 2022.
[33] Wouter Fokkema, Ruben Hoeksma, and Mare Uetz. Price of anarchy for graphic matroid congestion games. In International Symposium on Algorithmic Game Theory, pages 371-388. Springer, 2024.
[34] Yoav Freund and Robert E Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1-2):79-103. 1999.
[35] András György, Tamás Linder, Gábor Lugosi, and György Ottuesák. The on-line shortest path problem under partial monitoring. Journal of Machine Learning Research, 8(10), 2007.
[36] Nicole Immorlica, Adam Tauman Kalai, Brendan Lucier, Ankur Moitra, Andrew Postlewaite, and Moshe Tennenholtz. Dueling algorithms. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 215-224, 2011.
[37] Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(33)291-307, 2005.
12

---

[38] Satyen Kale, Lev Reyzin, and Robert E Schapire. Non-stochastic bandit slate problems. Advances Neural Information Processing Systems, 23, 2010.
[39] Terry Koo, Amir Globerson, Xavier Carreras Pérez, and Michael Collins. Structured prediction models via the matrix-tree theorem. In Joint Conference Empirical Methods in Natural Language Processing and Computational Natural Language Learning SAMNLP-CoNLLL pages 141-150, 2007.
[40] Harold W Kuhn. Extensive games and the problem of information. Contributions to the Theory of Games, 2928):193-216, 1953.
[41] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[42] Chung- Wei Lee, Haipeng Luo, Chen-Yu Yu Wei, and Mengxiao Zhang. Bias no more: high- probability data-dependent regret bounds for adversarial bandits and mdps. Advances in neural information processing systems, 33:1 33:15522-15533, 2020.
[43] Vincent Leon and Rasoul Etesami. Bandit learning for dynamic colonel blotto game with a budget constraint. In 2021 60th IEEE Conference on Decision and Control (CDC), pages 3313..83.. IEEE, 2021.
[44] László Lovász and Santosh Vempala. The geometry of logconcave functions and sampling algorithms. Random Structures & Algorithms, 30(3):307-358, 2007.
[45] Russell Lyons and Yuval Peres. Probability on trees and networks, volume 42. Cambridge University Press, 2017.
[46] Arnab Maiti, Zhiyuan Fan, Kevin Jamieson, Lillian J Ratliff, and Gabriele Farina. Efficient near-optimal algorithm for online shortest paths in directed acyelic graphs with bandit feedback against adaptive adversaries. In Conference on Learning Theory (COLT), 2025.
[47] R Kipp Martin. Using separation algorithms to generate mixed integer model reformulations. Operations Research Letters, 10(3): 199-128, 1991.
[48] Gergely Neu. Explore no more: Improved high-probability regret bounds for non-stochastic bandits, Advances in Neural Information Processing Systems, 28, 2015.
[49] loannis Panageas, Stratis Skoulakis, Luca Viano, Xiao Wang, and Volkan Cevher. Semi bandit dynamics in congestion games: Convergence nash equilibrium and no-regret guarantees. In International Conference on Machine Learning, pages 26904-26930, PMLR, 2023.
[50] Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. Advances in Neural Information Processing Systems, 26, 2013.
[51] Julia Robinson. An iterative method of solving game. Annals of mathematics, 54(2):296-301, 1951.
[52] Robert W Rosenthal. A class of games possessing pure-strategy nash equilibria. International Journal of Game Theory, 2:65-67, 1973.
[53] Shinsaku Sakaue, Masakazu Ishihata, and Shin-ichi Minato. Efficient bandit combinatorial opti- mization algorithm with zero-suppressed binary decision diagrams. International Conference on Artificial Intelligence and Statistics, pages 585-594. PMLR, 2018.
[54] Shai Trendso in Machine Learning, 102):107-194, 2012.
al. Online learning and online convex optimization. Foundations and
[55] 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 Theory of Computing, pages 518 1295 2025.
[56] Peter Stange, Andreas Griewank, and Matthias Bollhöfer. On the efficient update of rectangular lu factorizations subject to low rank modifications. 2006.
13

---

[57] Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E. Schapire. Fast convergence of regularized learning games. In Corinna Cortes, Neil D. Lawrence, Daniel Lee, Masashi Sugiyama, and Roman Garnett, editors, Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 2989-2997 2015.
[58] Eiji Takimoto and Manfred K Warmuth. Path kemels and multiplicative updates. The Journal of Machine Learning Research, 4:773-818, 2003.
[59] William Thomas Tutte. Graph theory, volume 21. Cambridge university press, 2001.
[60] Dong Quan Vu, Patrick Loiseau, and Alonso Silva. Combinatorial bandits for sequential learning in colonel blotto games. In 2019 IEEE 58th conference on decision and control (CDC), pages 867-876 872. IEEE, 2019.
[61] Dong Quan Vu, Patrick Loiseau, Alonso Silva, and Long Tran-Thanh. Path planning prob- lems with side observations colonels play hide-and-seek. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pages 2252-2259, 2020.
[62] Dong Quan Vu, Kimon Antonakopoulos, and Panayotis Mertikopoulos. Fast routing under uncertainty: Adaptive learning in congestion games with exponential weights. In NeurIPS '21: Proceedings of the 35th International Conference Neural Information Processing Systems, 2021.
[63] Dong Quan Vu, Kimon Antonakopoulos, and Panayotis Mertikopoolos. Routing in an uncertain world: Adaptivity, efficiency, and equilibrium.
222900 January 2022.
[64] Renato Werneck, Joao Setubal, and Arlindo da Conceicao. Finding minimum congestion spanning trees. Journal of Experimental Algorithmics (JEA), 5:1s-es, 2000.
[65] Julian Zimmert and Tor Lattimore. Return of the bias: Almost minimax optimal high probability bounds for adversarial linear bandits. In Conference on Learning Theory, pages 3285-3312. PMLR, 2022.
14

---

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

---

Answer:
[Yes]
Justification:
The proofs of our claims can be found in the appendix due to space limitations.
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 proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
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 new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., 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
16

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /otee//guudddeeeeoSuuubbmiibii ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as 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 (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper 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
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper 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, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
17

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper 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 GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make 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 http:p/ss//aacsss.cppo/o//////ea
Answer: [Yes]
Justification:
The research conducted in the paper conforms with the NeurIPS Code of
Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work deals with computing coarse correlated equilibrium in various game settings and is theoretical. As result, there is no social impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
18

---

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 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: The paper poses no such risks.
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
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
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.
19

---

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: The paper does not release new assets.
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: The paper 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:
The paper 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
20

---

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 of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy fattps://neurd/: /00p://ccc...cc.eeeee//////////0 for what should or should not be described.
21

---

Contents
Introduction
2
Preliminaries
3
Kernelized Payoff-based Learning in Polyhedral Games
3.1
Kernelized GEOMETRICHEDGE for Bandit No-Regret Learning
3.2
The Semi-Bandit Feedback Case: Kernelizing Implicit Exploration
4
Efficient Kernelization in Colonel Blotto Games (CBGs)
5
Efficient Kernelization in Graphic Matroid Congestion Games (GMCGs)
6
Conclusion
10
Extended Related Work
24
Semi-bandit No-Regret Learning: Analysis of Algorithm
25
Second Moment Calculation via Kernelization
28
D
Layered Graph Representation in Colonel Blotto
29
Barycentric Spanners
29
E.
Computing Approximate Barycentric Spanner for Colonel Blotto Games
29
Computing an
Barycentric Spanner for Graphic Matroid Congestion
Games
30
Bandit No-Regret Learning: Analysis of Algorithm
31
Kernelization in Colonel Blotto games
36
G.I
Proof of Proposition
37
Proof of Lemma 4.3
38
G.3
Alternative Proof of Lemmal 4.3
38
Proof of Theorem
42
G.5
Similar Techniques for Efficient Impl emplemmnttiion of Kernelized GEOMETRIC HEGDE ....ess.........................
in m-sets
G.5.1
Comparison with a DAG approach
46
H Kernelization in Graphic Matroid Congestion Games
47
H.1 Proof of Proposition H.I
47
2 Proof of Lemmal5.
48
3 Proof of Theorem 5.2
49
Kernelization in Network Congestion Games
50
22

---

Efficient Uniform Random Path Sampling from a DAG
50
23

---

A Extended Related Work
Online learning in games. The connection between no-regret learning and the computation of approximate CCE in games has been well-known since the work of Freund and Schapire 34 (see
also 23 ; assuming that all players use no-regret learning algorithms with regret (VT)) the time-
averaged history of joint-play consists a O -CCE. In 29 it was shown for two player zero-sum
games that rate of convergence ((1/T)) can be achieved, improving the standard O (I/VT) that can be derived from black-box regret analysis. Further improvements using the idea of optimism were shown in (5) and for general-sum sum games appeared in later works [57 25 30 6
(see also references therein as there a vast literature in learning in games and is impossible to cite properly all works).
Colonel Blotto games. The classical Colonel Blotto game introduced by Borel [8 dates back to 1953. Some notable works about computing NE in two-player zero-sum games include 4 [5], and for learning CCE in multi-player games include [2, 43. Moreover, [60] 61] show no-expected- regret learning Colonel Blotto games which does not suffice for convergence to CCE. Our work improves upon previous works the runtime time to learn a CCE (see also Table IT.
Congestion games. Congestion games are potential games 52 and always admit a pure Nash Equilibrium (NE); i.e, state in which no agent has incentive to unilaterally deviate. In full- information feedback, long line research studies the convergence properties to NE of game dynamics (e.g. best/better response play or no-regret). The seminal work of Takimoto and Warmuth [58] which studies online shortest paths, provides an efficient learning algorithm for network congestion games. Regarding the semi-bandit and bandit feedback settings, György al. (35, based on [58), provide efficient algorithms for online shortest paths, which can also be applied to network congestion games. Moreover, efficient algorithms based online gradient descent have also been established [49 27). The regret rate and per-iteration complexity. i.e., the total running time to reach CCE of the aforementioned works is inferior spanning trees, Koo et al. (39 used the Matrix- Tree Theorem in the context of directed spanning trees for calculating the normalization factor of exponentiated gradient algorithm. However, their approach does not provide exact sampling, nor kernelization of bandit estimators.
(See also Table 3). Regarding learning on
24

---

Algorithm 2: Kernelized Algorithm based on IX under semi-bandit feedback
Data: d, m, 0 and [0,
Initialize (u( = and Co(5) = for all E [d], Pu [1/N 1/N] 1I/N,...,1I/ AV,))
for t .... T do
Compute the kernels: (y(C,-1, and {Ky(Ct-1,E)) for j E [d] (MWU) using 02 = SAMPLING(V, C)-1))
Sample an action
Observe semi-bandit losses & E IRd
Compute the unconditional probabilities:
It
Kv(Cr-1,81)
Kv(Ct-1.1)
Ky(Co-1.fd)
Ky(C2-1.1)
Compute the loss estimators:
(()) 2,00++ ((((()) =1},
400
E [d]
Update the aggregated loss estimators:
c+j) = (-) +260,, E
Update the exponential cumulative loss estimators:
Ci()) = exp
exp)) (-)(-n(()), E
Procedure: SAMPLING
12 Input: V.C
13 Sample e[1] ~ Be (1 Kv(C,e))
Ky(C,1)
14 for j = ,,.,, d do
15
Compute the kernel: Kvú)
Set V(j) = fo' E V o'(i] vlt], vi E j 1]} and pj = =1 (C,)(Ce,)
16
(C.1
Sample v[j] ~ Be(p,)
Return:
B Semi-bandit No-Regret Learning: Analysis of Algorithm 2
Lemma B.1 (Corollary
48
Let 7t = 0oror all With probability least 8',
Σ (((1))((0 log(d/8")
24
simultaneously holds for all E [d].
Theorem B.2 (Theorem 3.4 restated). For any E (0, 1), the sequence Ui,.., VT of actions played by Algorithm 2 with 7 VdT and
VaT satisfies
R(T) s O ((mvTd+ log(d/6)).
with probability at least 1-
Proof. Let [v((v) = Eiey (i) be the loss estimator of selecting pure action time step and L.(v) = Eiey (i) the corresponding true loss. Moreover, let Č,(v) Et= (v) be the cumulative loss estimator of selecting pure action for the first t time steps. Also, let wr(x) = (x)(- where is the learning rate of MWU, and let W. = ='ey wx)v), with Wo = |V] N.
Wr. First, we As in the standard analysis of MWU, we will upper and lower bound the quantity log Wo fix pure action v* E V and using the fact that Wr(v) 2 wy(o"), ), for all t, we have the following lower bound:
Wr
2 -nCr("") - log N log Wo
(4)
On the other hand, assuming n/(4(v) < 1 for all A E A (this condition will be verified later), using
the elementary inequalities e² 1 x + x2 for |a| and In(1 + y) S y for y > -1, we get the
standard following upper bound:
25

---

W
log Wi-1
log
Σ Pe(u) exp((n(((())
(5)
NEV
I log
Σ (c(A)(1 - +
(6)
NEV
S n²² Σ Pc(u) Pc(u)
Σ ((())
(7)
#EV
AEA
Now, we will upper bound the first term and lower bound the second term of as follows:
Σ
(())
(8)
VEV
NEV
NEW
S m
Σ Pc(v)
Σ (1)
(9)
VEV
KEV
m
(1)2
Σ
(r(e)
(10)
kE[d]
VEViEE
m
Σ
(i(())((1))
(11)
iE(d]
(())
E m1 v 100
m
Σ
si(1)
xz(1) +x
(12)
iE(d]
< m
((1)).)())
(13)
V.
S m 2.(1)
(14)
where in 9 we have used the property that the arithmetic mean is less or equal than the guadratic
a.(() mean, in 13 we have used the fact that (e) < and we defined gc( (x)+) the fact that (i) < 1.
and in 14 we have
Similarly, we lower bound the second term as follows:
Ep((o)do()) = [p((v) 44(1
(15)
NEV
VEV
NEV
Σ (1(1) Σ
pe(u)
(16)
VE
VEVieh
(i)(i)
Σ
(i)
(17)
Zi(1) +
NE
(((1)
Σ (1) Σ
(18)
x1(1) +
IEV
SE
Σ 41) Σ (1)
(19)
SE
Now, summing for t 1,2, ..., T, we get:
26

---

T
T
log
WT
S n m
Σ
Σ
(e,(1)
(20)
Wo
t=
iE
Combining the above with the lower bound of
we get the following:
T 7J Σ E (e((1) - -()())
-n(C((0²) - log N S v/mm
Le(t)
(21)
1= 1EM
t=1 ME
which implies that
log N
Σ E
((11)
Cr((")
+ 1pm Σ
Σ Cee(1) Σ Ele(1)
(22)
r= KEN
T
T
(.(v))
Σ L
log
(mm + 7)e(())
(23)
7
1=1
1=1
1= 1E
Then, using Lemma B.1
with probability at least 1 - 8', we get the following:
T
mog(d//8)
log N
Σ Lo(v))
Σ L,(v))
(mm 7)
2((1)
(24)
27
"
m log(d/8))
log N
T
+ (m + +2)
Σ
(25)
27
xE[d] 1
Now, we can apply Lemma B.1 to the term Eiela Et= (e()). Then with probability at least we obtain:
28'
T
m log(//6))
log N
T
d dloo(d/o')
[T(vr)) Ix(x"))
<
+
+ (1m + 7)
Σ [=
Σ
E((i) + (1m + 7)
24
n
27
(26)
m log(d/0")
2m log
+ (zjdm + Td)T + (mm + 7) dlog(d/8))
+
24
27
(27)
where in the last inequality we have used the fact that S Σi= (*) I md" = log N < 2m log
and that Eiew, (i) & m, which holds because |0:11 S m.
Next we will optimize over parameters ? and to minimize the RHS in 27 We have one constraint
over the parameters. In the proof of we used the condition nL)(vr) < for all E [T] It is easy to verify that if rmm S y then the above condition is satisfied. We set y vdT and r var balance the dominating terms in the regret bound. Moreover, we set 5 = 28'. Therefore, using the above and plug them in 27] we get the following:
T Σ (L.(v)) - Le(v")) mvdT (2g(d/6))) + 2n logd + 2mv/T + dlog(2d/0) (28)
1=1
27

---

Finally, we obtain our result by setting v" = arg min DEV Et=1 Le(e).
C
Second Moment Calculation via Kernelization
Theorem C.1 (Theorem 3.1 restated). Let Ee(gt) := Ever qevv)ve" be the antocorrelation matrix under the law of qt. Then, for all j.3 E [d], holds that:
-.00)). =1 K(O0 BG) + K(bl),e)) K(b K(bO),,,5)
K(b(),
Proof. We observe that for all j.j E [d]. the feature map ((ers') satisfies for all v E V
[[{))r)[[[]= = II
[x = II
LKSjAHY = jevngger
k=v(k)=1
k:o(k)=1
-jjer- - 1rev + wer
=gg + 1840 -ise
Using the fact that ((1) = 1 and (bt;)[u] = Ie we conclude that for all j.j e [d] EV
Lis'e = (1][[c] + )(E [o] - -
(29)
Therefore, for all j,J [d]. we obtain for the autocorrelation matrix
(n = Σ (u()) [i.'" = Σ (e(v) j.'
(30)
VEV
EEV
Σ (1()) + - (o)
(31)
NEW
(0((()), + (o(b()), ol (( - (6(b(0) o(E,)) - (6(b())) M(E,))
(32)
K K(b1), 1)
K(b0), + K(b E..y) )- K(b(), .e,) K(b(),,)) Egy)
(33)
K(b(), 1)
22) K(b9), ,2) + K(b()) Eg) K K(b(), (..)) K(bO)1) 1)
(34)
where the third equation follows from 29 the fourth from Theorem 2.2 and the fifth from the definition of K(.-)).
28

---

D Layered Graph Representation in Colonel Blotto
Definition D.1 (Layered Graph [3] The layered graph has 1 layers and ++1 vertices in each layer. Let oi denote the j-th vertex in the i-th layer (0 S S k and 0 s j s n). For any 0 S i S k there exists directed edge from vi-1,j to Vi, iff j sis n.
Lemma D.2 (Pure actions in a Layered Graph (3).. Each directed path in the layered graph starting from Vo,0 and ending at &n is equivalent to exactly one pure action of the Colonel Blotto game, and vice versa. For each pure action, the reward for each battlefield is associated with unique edge of the directed path.
However, the layered graph, which has been used to succinetly represent the action space for learning in Colonel Blotto games, see [60] 61 43 implies a representation complexity of (n?Ak) 3)) that can be bottleneck for efficient no-regret learning and convergence to CCE.
E Barycentric Spanners
Before proceeding with the proposed algorithm for the bandit setting, we introduce the important notion of barycentric spanners [10]. We will use barycentric spanners to ensure adequate exploration of each coordinate j E [d], sufficient to guarantee low variance of the loss estimators.
Definition E.1. A subset of independent vectors (bi,....du, ba} S V is said to be C-approximate barycentric spanner of Vú, with 1, for all E V. there exists a E I2 such that
Σ bgby and
|ayl S C, for all j E [d].
We define to be the matrix whose columns are the barycentric spanners {bi,...,ba) bb)-
The following proposition ensures that, if specific conditions hold, there exists efficient algorithm for computing a C-approximate barycentric spanner.
Proposition E.2 (Proposition 2.5, (2). Suppose S C Rd is compact set not contained in any proper linear subspace. Given an oracle for optimizing linear functions over S. for any C >>> 1 there exists an algorithm that computes a C-upproximate baryceniric spanner for S in polynomial time, using O d log calls to the optimization oracle.
E.1 Computing an Baproximate-Barycenttee Spanner for Colonel Blotto Games
Proposition E.3 (Oracle for finding best-response in polynomial-time) Given reward vector the following linear optimization problem
max TV VEV.
can be solved in time (n.2k).
Proof. We will solve the following linear optimization problem (which corresponds to playing best-response with respect to the reward vector r):
max T TV VEV.
(35)
The above problem is equivalent to the problem of finding the longest path from a directed weighted DAG (with [V| nodes and |E| edges), which can be solved via Dynamic Programming in time |V|- |E). To do so, we leverage the Layered Graph representation (see Section D). which is a DAG with (nkk) nodes and O(n2k) edges. More specifically, in the Layered Graph, layer the edge ε사 = (uN.s: U.j1,)) for < and i,j [n]o corresponds to assigning j - soldiers on battlefield h + 1. On each edge, we use as edge weight the battlefield reward taken by assigning the corresponding number of soldiers the corresponding battlefield, and the longest path of this graph,
[k]
29

---

denoted by x" E I=* represents the best response with respect to Thus, we can solve the linear optimization problem in time (nn²k)
The only thing left to do is to get V = arg maxvev, v'V from x². It is straightforward that there exists one-to-one correspondence between these two vectors. To get V*, one must do the following:
Initialize
V R4.
For each layer h E [k], given the selected edge en (up,is ub+1,)) in x", assign V* [h, i]
=1.
Lemma E.4 (Polynomial-time algorithm for C-barycentric spanner in Colonel Blotto). In Colonel Blotto, for > 1, there exists a polynomial-time algorithm that computes a C-approximate barycen- tric spanner for V; in time O(n"k k3 logo
Proof. To prove Lemma E.4. first observe that Vi satisfies Proposition E.2 because is compact and not contained in any proper linear subspace of R.d Now, need have access to oracle for optimizing linear functions over V. To do so, we utilize the oracle for finding a best response given reward vector from Proposition E.3
Therefore, each oracle call needs time On)*k). Now, using Proposition E.2 to compute the barycen- tric spanner for V., one may the algorithm defined in [9 that computes approximate C-spanner (with C 1) in time O(n 413 (nk))
E.2
Computing an Barpocntattc-Bayceentiiccc Spanner for Graphic Matroid Congestion Games
The idea is similar to above but using the Kruskal algorithm as the oracle. To compute a C-barycentric spanner here we need O[EE| (ogc((E))
30

---

Bandit No-Regret Learning: Analysis of Algorithm
We have the following:
sup x E R.vvV
sup a,
a² FB" B3
(36)
1
sup
a' B3
(37)
||||=||/||=CV
I Ccdd. 11B"
En Bll2
(38)
Cld Amax (B B)
(39)
1
C²d Aminn (B-12,B-7
(40)
C² Amin (B-1 (3 + (1 Bp, (vve') B-T)
(41)
C²2
(42)
Manin (B (B- 3--BBTB-7 B-T)
C²
(43)
where Raxd is a full rank matrix that has the approximate spanners as columns. In 40 we have
used the fact that B is invertible because it is full rank, and also that Σ, is non-singular (see (28)) which implies that Σ, exists and thus the pseudo-inverse matrix Σ equals the inverse matrix, i.e., Σ = E Moreover, in 42 we used the Weyl's inequality.
Let C, be the autocorrelation matrix under the law of the exploration distribution on the barycentric spanner. We aim to bound the minimum non-zero eigenvalue of C.. Similarly to above, we have
sup x. C x =EV
a TBT C, Ba -E(-C,C
sup
(44)
sup
T B CT- Ba
(45)
|
< cCd. |
CT Bll2
(46)
Cld Amax (B7 C, B)
(47)
c2d
(48)
Amin d
-T)
C² Amin (B-1 (2BBT) B-T)
(49)
< C²d
(50)
Let [.] denote expectation conditioned on the past events; i.e. the realized rewards received and the actions taken by player up to time step f- 1. Also, let be the ones vector. We define L,(v) = 4 v, Eg- v. In the following analysis, we drop the superscript i and sometimes write qe and Pt for the distributions of player i. For now, we assume that T' & m, an assumption that will be verified later by the average regret guarantee for the convergence to CCE.
and similarly (v) (v)
Using the above analysis, along with the basic lemma of 11. can easily get the following lemma with the basic properties of the algorithm.
Lemma F.I. For any U E V; and e [T]. the following hold:
1. (unbiasedness) Eelle] be
31

---

2. "²' u S de
7
3. Ei(wo) S dml
4. of u11 =
5. E2 (R...) 2)
S m² 2 l
Now, using Lemma F.1 and selecting 7 = Fmcza 20333/952711333 we have
nia(w) 1.
Lemma F.2 (Bernstein's inequality for martingales). Let Y1, .. YT be a martingale difference sequence. Suppose that Y, [a, b] and
E [ X1-1,
X1] so
for all I E (I,...,Ty, Then for all > 0,
Pr Σ Y 20 In(//) + (ln a)/3 -a)/3 S d
Lemma F.3. Simultaneously for any E Vú with probability at least - 6, it holds that
dmm + + 22T + In(d/8) ( (Lenz²² - m²
(L,()) (L())) $
Proof. Fix any 8 E V., we define Yı(v) L.(v) L.(v). Y, martingale difference sequence.
Using Lemma F.I the following hold:
Var, Y((u) = V Var [E((v) - L((1)]
(51)
(Ia(o)- -L((o)) Ln(co)
)
B,
(52)
(En(oo)
E.
+ VVV (Lo(v))²
(53)
$ mn
T Σ,
+ m
(54)
dPC2
S
mm
+
(55)
mdC
+ m
(56)
where in 53 we used the Cauchy-Schwarz inequality inequalll and in 55 we used Lemma F.
cd2C2
[.(v)- - L.
<
+
(57)
7
Now by applying the Bernstein's 's inequality (Lemma
R22
with probability at least
8
we obtain
32

---

mdC
mmdC2
E Y((0) -
+ +m)
12T 1n([v:166)
+ +m)
(58)
Vy
-(<mp) (dm)
mm²dC2
+ / (n(/0)) + 3 7
ln(d/8)
+ m2
(59)
Taking the union bound, we obtain the desired result.
Lemma F.4. With probability at least 1 - 8,
-i,(t) S ymml' + (Vrdm +m 22T (n(00))
+3 - In(d/8) (m² +yme)
1=1 WEB
Proof. Using Lemma
with probability least 8, have, simultaneously for all B,
E
1 (L(())
1
(10)))+
+7
dm3
+ m²/3)
(2n(///)
d
d
V7
1
+ In(d/8)
47
[mm²22
+ +m²²)
(60)
d ymT (vidm?12 + ym²/3) /21((d/)
1
+ In(d/)) (dm=²C² + +mm²)
(61)
Summing the d elements of the spanner, and using the fact that Lv(v) m, get the result of the statement.
Lemma F.5. With probability at least 1 - 8.
Σ le Ur ΣΣ us
T
T
4 In(1/0) (n((1)))))1(()
[dmC2 -
dm
Proof. The proof follows directly from the proof of Lemma 6 in using |Y|
m, and
7
Var, Y, S mnvd d + m..
Lemma F6. With probability at least 1 - 8,
Σ n Σ Pe(u) (Ze ndm? +
+ dm²) (2T
VEV.
Proof. The proof directly follows the proof Lemma from by using that the summands of E "t are bounded by d²c²
Theorem F.7 (Theorem 3.2 restated), For T & and any E (0, 1), the sequence vi....,Ur of actions played by Algorithm with d m/ and 444/3/2/77777 satisfies T1/3
Rs S δ (m
33

---

Proof. Following the standard analysis of MWU (also similar to our analysis in the setting), have that,
we(w)
exp (n)
Wi-1
(62)
W,
We
.EV;
Σ
wa(t)
I-nnIa()) 17² (E)(o)))
(63)
Wt
VEVi
(-I E(()) + Σ
pe(w)n (Ta(tI)
< 1 +
d [v)+ + Σ
(64)
1 1-7
DE
DEB
VEV,
since by definition of pt-
Wa(v)
Pa(u) 31100 E B
W.
1-7 7
Fix any o E V4 We have that,
Wr+1
Σ E((())) In 11/
In
(65)
W1
T
L((0*)+ + (dm2iic
+ m2/3) (
m In
2 11
22T In(d/)) + In(d/o)
+ m2
+
7
(66)
T L((x)+ + (a(0*)+(pP/3m)))) + m3/2/T) (2ln(d/5
2 2n
t=1
+ In(d/5) m233 + +m²) + m In
(67)
f2/8m,
where in 66 we used Lemma F.3 and in 67 used the fact that y
T473
Putting these together, using Lemmas and F.6
64
have
W441 W.
Σ Le(we) + (mvd+ m) m) + 1n(1/8) (Lmce + +m)
< 1 +
+ 7mT (
7m3312
(2T ( In(d/5) (22 + +m²)
+ ndm 2T +m @mm=² dm²) 22T
(68)
Taking logs, using the fact that In(1 + x) S x, and also the fact that - < 21,, because we have assumed that T 2 m,, and summing over t, we have
34

---

Wr+1 W1
4 in(1/6) (1n11/)))) [emc² + +m)
In
s 2n
Σ Le(u)) + (mVd+
7mm
C (2T(n/(00))
+
4
In(d/0) (d +ym²²
dmm2² dm3 (2Tlm(118)
ndm +1l
(69)
2n
Σ
+ + (nVdd (aa11110)(11111)) 1n(1110) (2403m2/33 +m)
m
2/322/3
(d/333//CT// + m V2ln(d/0)
4
In(d/o)
3
m3/37/13
m2/371/6 2llm(1/6)
(
(70)
d/3
d1/3
where in 70 we used the definitions of y and 17.
Finally, using 67 and 70 rearranging terms, dividing with 7, using the fact that Ind/n m/33 In d, and rescaling 5 45, with probability at least - 6, simultaneously for all u² E Vs we have that,
(Ta(ve) Ix(1") s 20 so (1833m44182111)
35

---

G
Kernelization in Colonel Blotto games
Algorithm 3: Efficient First-Moment Kernel Computations in Colonel Blotto games
Data: C₁
/" Compute the partial products P1 and P2 *
2 p[0 = 1
for h O,.... k- do
Pun(z) ()))) 1,
==0
pe [](2) truncate Pon(() degree 2
[0] =1
for O,... k do
(z) = () [M](2) Σ
C,sh 1, 2*
==0
ph [h- + 1](2) truncate (z)g((z) to degree n
Compute the d kernels */
Kv 1) n-th degree coefficient of P(() [k] for = 1,.... do
12
P- p [h- 1](z) P [k h1)(2)
13
14
Σ ag -2- truncate P-h to degree
s=0
15
for s = O..... do
Ky(C,, Eh,a) Kv(C2, 1) On-s &]
36

---

Algorithm 4 Efficient
Kernel Computations in Colonel Blotto games
Require: C(
1: # Compute the interval products
2: for h, h² in [/: + 11 x [k + 1lo do
3: Pont h²]
4: for h L,..., k do
5: Pint [h, (2)(2) Σ
C
h,a
6:
for h = l1,.... do
7:
P(z) Ponel (1, 12(22)
h41,s"
(1)
8: Pins [h, h1 + 1](2) truncate P(2) to degree
9: Pinehh, (x)) = II Σ c00
imhh s
10: # Compute the d2 kernels
11: for h 1,.... do
12:
# case 1: h'
(-)(z) P 1](z) Pinch + (z)
14:
0s 2² truncate P-n to degree 6=0
Σ
for 8 0,..., do
16:
for 8' = =0...,, do
(y(C(t) Eh.,,,,s)) Kv(C(9, 1) -n-- 0.00 On-s' Ch. 1(s +
# case 2: N/
19:
h < k then
for h' h + 1,... do
(a(2) = Σ ((() h,s" 2
21:
==0
for 0, .... do
(2) = Pn(z) - ((t) 2
23:
P-A (2) = Pin[1, h h.s
24:
1](2). Pomelh lh + 1, - 1](2) Pine + 1, [](2)
(-)(2) 2) P- (2) Ph,s(2)
26:
Σ 2² truncate P_ to degree n
27:
for s' = =0...., do
28:
Kv(C(t, @n.))s,ss) Kv(C(t), 1) -nnos' W
(1)
G.1 Proof of Proposition 4.2
Proposition G.1. For given x, E {0, 10, there exists an algorithmm that computes the kernel K(I, y) in time Onkk log n).
Proof. To compute the n-th coefficient of we execute a rumning product over the factors of the
polynomial. This process involves updates of the partial product. After each update, the partial product is truncated down to degree n. Thus, inductively we ensure that all multiplications involve polynomials of degree most n. Each multiplication in On log n) time. The overall complexity over the & multiplications is (nk log n) and after the truncated product is computed the target coefficient is obtained in O(1).
be implemented with FFT (20)
37

---

G.2 Proof of Lemma 4.3
The proof is based on Algorithm We define the running product [|] from left right, which is the sum of the degree 0 to n terms of the polynomial
" Σ CFF' . z), We can compute all ;'=1 =
II
polynomials p( [1]. for = 1.... k in total time nk log using the following induction argument:
Given Pf [i], we compute pi + 1] by performing the polynomial multiplication p)" [1]())
1, 2d and truncating all terms of degree greater than n. The two multiplied polynomials 5=0
have degree n, so the multiplication can be done in time n log using FFT, while the truncation of the higher degree terms can done in time n since the product polynomial has degree 2n. Repeating this procedure for i 1,.... k 1 we get all left-to-right partial products in total time nk log
Similarly, we define the running product p! [i] from right to left as the sum of the degree
terms of the polynomial
II Σ C,VL j] 23, Similarly to p(() we can compute all right-to-lefft
partial products p
[1]. for I,.... total time nk logn.
Now, using the above partial products, we compute all the kemnlss required for (O)MWU at time step All polynomial multiplications in the Algorithm are performed using FFT so that each of them takes time log(n).
Following similar logic above, via Algorithm 4 we get the desired result.
G.3 Alternative Proof of Lemma
Efficient sampling of MWU in CBGs has been studied in Beaglehole et al. [12] A useful tool for this purpose is the partition function defined in equation I00 Here we describe their method with details and we extend their ideas to the efficient calculation of first and second order moments of the MWU distribution.
Remark G.2. We give an algorithm (Algorithm 4 that performs the second moment computation in terms of kernels. The algorithum follows similar logic to Algorithm but is somewhat more complicated, due to the nature of the problem. In steps where polynomial multiplication is performed, imply that the multiplication is implemented efficiently through FFT.
We remind that the calculation of first order moments was used in our method for learning in the semi-bandit setting and the second moments appear in the calculation of the autocorrelation matrix which is used in the bandit setting. Next we proceed to the technical details of our methods.
Focusing on single player, at time step I, let &, [h, s] be the loss observed by the player when assigning s soldiers to the h-th battleficld, given the assignments the other players in this battlefield. Moreover, let
10 (s)
e le 8)
We define the partition function
Σ II exp (-nef (t) (a:)).
fu(v)
(71)
21 2141
We also define the partition function gr (y), which similar to fn(()) but aggregates battlefields in the reverse order.
k
gn = Σ
II
exp -rT((((=)))
(72)
34 4 = i=
38

---

Let (Z1, 24,) be the cumulative loss at timestep t. ( can be decomposed into the cumulative
losses per battlefield as follows:
k
1 (T), I1h
(TA)
(73)
h=1
Under MWU the probability of some assignment 21 Fa at timestep I can be written as
Pr[si, Sp = I1, Ikk x exp
Ikk)
(74)
exp
(I%).
(75)
Marginal probabilities of soldier assignments at a single battlefield can be written as follows:
Pr(sk- = =]==
Σ
Pr[si, m 1k-1, 1, Sp. I1 a 26 s]
(76)
Σ
exp
-1
19 (x))
(s)
(77)
h=1
1-1
exp
(nncck
11) (s) (s)
exp
1]
ch (IIA.
(1)
(78)
-1 =
h=1
k-1
eexp
(-11eh (s) (()
Σ
exp
(nnch (2)
(mn)
(79)
+1 =h=
(8) (8)
= exp
fk-1
(80)
Moreover, we can compute the conditional probability of each soldier assignment a single battlefield, given a set of soldier assignments at other battlefields:
Pr 8k-h =8 8k-h+1,..- 8k)
Σ
Pr|st 8k- 8k-h = I1, Tk h 8 8k 3e-ntt,..... 86]
21 -E 1=
89
(81)
hーhー1
h Σ
Σ
-17 Σ
9 (zz) - (2 -
(
x
exp
21 +8k- h-1
j=1
(82)
exp
(1) - -1
(1)
Σ
(
Σ
exp
-
Σ
1m h+l
#1 +. h 1
1=1
(83)
exp
(1) [1) - 77
Σ
(0((s))
sn-h-1
n1
Σ
8j
-
j=k- h+1
(84)
x exp (-nc((a(s)) fh-h-1 n
Σ
8j
j=k-At1
h+1
(85)
39

---

Similarly, in terms of the partition function (v). we derive
Pr(s] =] x exp (-nc(² (8)) 1n-1(n -8) 8)
(86)
Pr(Sa = 5 51$1 $1..... sh-13 x exp (-nch (s) -h-
(-rcc((s))
n
Σ j=l
8j
- 3
(87)
The conditional probabilities can be used implement an efficient sampling procedure for the MWU distribution, as was proposed in [1]. For completeness we write the algorithm below.
Algorithm Sampling from the MWU distibution Colonel Blotto games
Require: Soldiers 2 0, battlefields k 2 and cumulative loss ch (s) for h, 8 E [A:] x [n]o fo(s) = for all 8 E [ri]o 2: for h = 1,.... k - do
3: Using FFT, calculate the convolution (a * (s) where a(s) = exp (-moh²
( (s) and b(s)
Sn-1 i (s), 8 E [n]o-
4: V E [ri]o. calculate the partition function for battlefield h:
[a()) = Σ exp (-n00) Sn (s - 8') (a (s),
8'=0
5: Sample the number 85 of soldiers at the last battlefield:
Pr[sk = s] x exp (-ne (s))
(t) Is--((n - 8), E [n]o
6: for = 1,...., k do
7: Sample the number - of soldiers at battlefield k h given the numbers of soldiers,
$h-ht1s..., 8p, assigned to battlefields k I,..., l as follows:
Pr(se-h 8 8k-h+1 813 x exp (-nof=a(0)) (5)) -k---1 11
8j
8
b=kー
for E n
$j
j=k-h- h-1
0
Remark G.3. Algorithm implements the SAMPLING procedure of Algorithms 7 Mand The key point is that instead of explicitly calculating the required kernels, directly computes the conditional probabilities via a partition function, which corresponds to kernelizing the conditional polytope.
40

---

The unconditional marginals that constitute the first moment are calculated as follows:
Pr [sh = s) = Σ
Pr((st,... 8h, Sh, sk) (01, ..., 8, ....., xx)]]
(88)
E B-=n-s Juh
x
Σ
exp
11
9
(x2) - 1/c (s)
(89)
Σ mn=n-s Jihh
jzh
h-1
exp
(-/c[/(0))
Σ
Σ exp
-1
-11
9g
(2)
Σ
exp
1
Σ j=h+1
oy
(127)
j=1
Ry=s'
zソ=n-sーs
amh+1
(90)
R-9
exp
(-1c((()) Σ
Sh- (f)9 (
(91)
8'=0
(-nch) (1) (s)) (fh-1* (n+
exp
(92)
We can precompute the partition functions fa (v), Ih (v), for all h E [k] and y E [nlo in total time kn log n utilizing the self reducible structure of the partition function (see algorithm 6 flines 1-5 for details). Then we compute fa-1 9h+11 for all h [k] and y E [n]o in total time kn log with FFT. Using these calculations each term Pr [s, = s] computation takes constant time. Note that this method is essentially equivalent to the kernel method we describe in the main paper (Algorithm 3
For the calculation of the second-order marginals that constitute the second moment, we will make use of the interval partition function fu. (y), that aggregates possible assignments between the h and the h'' battlefields.
(n)
Σ
II exp (-neş") (1) (1:)) (xzi))
(93)
34 2h + my i=h
Pr [sh, Si =,,s]= =
Σ
Pr[(s1..... ................................ Sh. .... Sh. "h'...., Sk) = (x1.... s,...,',, S'..........,
Σ ss=n-s-8
(94)
Σ
exp
-17 Σ
1/ (xz) - 1/0 - 172 (0')
(95)
Σ = jihh.
jzhin
h-1
= eexp
(-1o(((()) exp
(-ncch (5')
Σ
exp
1|
Σ
(x,))
j=1
m==I
n-1
Σ
exp
-
Σ
c (mz)
10)
Σ
exp
-11
Σ
(0)
(xz)
j=h+1
+=
Σ 2y y j-kl1
zy=n-s-'----
J=
(96)
4-1
exp
(-noh) (s)) exp
(-nch2 (2) (6')
Σ
Σ
exp
-17
(2g)
2=1
41

---

Σ (zg)
Σ
Σ
(1))
exp
-
exp
-
j=
jーh'-
suht1
+mh+1
(97)
n----s
exp
[ exp
(s')
Σ
f1,6-1(z)
x=0
1 -
(98)
n---a
exp
(-no((((s) (s) exp
(-n0 (50))
Σ
(1 fi++1&) 8-88 s's's -x)
(-noh (s) exp (-neh) (1) (5') (fi (J++IN-1 (n)
=ex
(99)
We observe that the marginal probabilities only depend the interval partition function and the cumulative loss per battlefield. We can precompute the partition function (y), , for all h h E [k]² h S h' and y E 'nlp in total time nk.2 log n utilizing the self reducible structure of the partition function (see Algorithm|5) 5). Then we compute the convolutions (fi f f1(+1,)) for all h, h E [A]2 h < TV' and E [n]o in total time nk3 log with FFT. Using these calculations each term Pr 88h; 8h s, computation takes constant time.
G.4 Proof of Theorem 4.4
Proof. Using Lemma 4.3 and the exact sampling procedure provided in 12 (see Algorithm 5), based on which we can calculate the required kernels our SAMPLING procedure time O(nk log n). the per-iteration complexity for the bandit and semi- bandit algorithms is O k log n) and O (nk log n.). we can achieve the desired
respectively. By combining Theorems 3.2 and 3.4 with Theorem 2.1 results.
42

---

G.5 Similar Techniques for Efficient Implementation of Kernelized GEOMETRICHEGDE in m-sets
Algorithm Sampling the MWU distribution m-sets
Require: Soldiers 0, battlefields d 2 and cumulative loss ch for h, E [d] x [nlo 1: fo(y) for all y E [ml]
2: for h I,..., df - do
3: V y [m]o. calculate the partition function for item
fv = exp (-ne)t)) fn-1 (y - fn- (2),
4: Sample the selection of the last item:
Pr(va x exp (-mel( bb) fa-1(m b). b (0.1)
5: for h 1, ,,,. d do
6: Sample the selection Ud-h of item d - h given the selections, vd-h-1.... Vd, of items
d 1..... as follows:
Prfua-A = b 0a-h41..... dat exp (-ned-n bb) fa-
Uj
b
j=d-k+1
for b E 0. 1,m
U/ -++
Summary: We can apply similar techniques to efficiently compute the second moment used in Algorithm for the classic m-sets setting. In particular, our approach requires time O(md)), improving upon the DAG formulation approach of [24 58) which requires time Omn²dd)
A classic setting in combinatorial bandits which is also considered in [32] are m-sets, where actions are selections of m of items. Its binary representation the action set can be written {0, 1)dd Σ, U; m).
{v
will show how perform efficient exact sampling and autocorrelation matrix calculation in m-sets. For this purpose we will use the partition function defined in equation 100 similarly to Blotto. The partition function resembles the kernels used kernelized MWU. Next we proceed to the technical details of our methods.
At time step let Eg]i] be the loss observed by the player when selecting the i-th item. Moreover, let
be the cumulative loss of the i-th item over the first time steps. We define the partition function
fa(
Σ
II
exp (-no(t) (1) .2x)
(100)
where x; E {0,1). E [d] and y E [m].
We also define the partition function gn (y). which is similar to fy( but aggregates the set items in the reverse order.
d
(n(v)
Σ
II
exp (-nc,"..o xx.)
(101)
By 2 F.mm i=
43

---

Let ( za) be the cumulative loss at timestep t. ( can be decomposed into the cumulative losses per item as follows:
I. (11, Fa)
3h
(102)
Under MWU the probability of some assignment 21, Fdd at timestep t can be written as
Pr(ui,.. - Ud 21, Tel exp -nn (x1, 1.11- (r))
(103)
exp
3h
(104)
Marginal probabilities over assignments can be written as follows:
Pr(ua = bj =
Σ
Pr[ui,
Ud- I1, 18-1,
(105)
2i t. -
Σ
exp
Th - 11cd b
(106)
21 + -
h=1
d-1
exp
(1)
Σ
exp
T.h
(107)
T1 #1+ Fig =
h=1
eep
(npcc (1) b)
Σ
exp
-nych (2)
In
(108)
bb=1
exp
(-mes
(1) b) fa-1(m - b)
(109)
Conditional probabilities over assignments are calculated as follows:
Pr(va-h =b ua- v2)
Σ
Pr[ui, ... Cd-a-1, Ve-h "......d-hl. 1-,, Ud- Val
m 1=d-1+1 %5
(110)
d-h-1
Σ
exp 11 Σ
n
(1)
b n
Σ
1=
==1
j=d- h+1
m
1=d-h+1 81
==
(111)
d
d hー
(t) b - 17 -nccgh
Σ
Σ
exp
exp
-17
j=d-h+1
h+l
m m-b- s=a-1+
(112)
exp
(1) b 1
Σ
ge . fa-h-1
Σ
- b
j-d-h+1 h+1
j=d- h+1
(113)
d
(-mo@2n b) Sa- m
x exp
Ui -
j -
(114)
44

---

Similarly we derive
Pr[ei = bj x exp (-nel) b) gd- 1m b)
(115)
Pr(un- = 6 , 2h-13 exp
(-nek) (1) b) -a-n-1
Σ Uj
b
(116)
The conditional probabilities can be used to implement an efficient sampling procedure for the MWU distribution. We write the algorithm below.
For the calculation of second-order marginals we will make use of the interval partition function fuy that aggregates possible assignments between the h and the h battlefields.
(n,
Σ
II exp (-ne²" (a:))
(a:c)((a:))
(117)
Pr [U%, Uh = b,6
Σ
Pr[(U1, ... Uh ................................ the,.,, Un) = (#1,...,b, (....,za)
Σ カー=
(118)
Σ
exp
-77
Σ
21 - (1) b ncw 6¹)
(119)
Σ
b-=
jFh,hh
m- b' m m-
h-
exp
(-mceh²
(1) .b)
exp
(-nch b6)
Σ
exp
(t)
Fjj
z=0
y=0
j=1
Σ
(8)
Σ
exp
-17
cj
exp
j=h+1
j=h'+1
j-hh
(120)
Th カー
h-1
exp
(-11e)
(1) b) exp
(-nc 11) 18)
Σ
exp
- 1
Tj
j=1
Σ z==r
m2
b-
h¹ -1
d
Σ
Σ
exp
oj Iz
exp
-77
2j
y=0
6
j=h'+1
Σ æ,=
ay=m- b-
j=n
(121)
m-
exp
(mpel
(1) b) exp
(-noff- 6)
Σ
f1,
z=0
b-6 -
Σ
Jo44:--1000---ammm b' y)
(122)
m m- Σ
= =xxp
(-1eot) b) exp
(-noh) .B)
f1a- * fM+1,2) - b - x))
z=0
(123)
45

---

exp (-npch-- -b) exp (-ne 6) (fi (fh+IN-1 fm b')
(124)
We observe that the marginal probabilities only depend on the interval partition function and the cumulative loss per battlefield. We can precompute the partition function fu, for all h, h' E [d]2 h < N' and y E [n]o in total time mad log m utilizing the self reducible structure of the partition function (see algorithm 6 lines 1-5 for details). Then we compute the convolutions (f1,a11 f * f1++ (у) for all h, h E [d]² h < h and E [n]o in total time ma log m with FFT. Using these calculations, each term Pr [Uh, U/ b, b'] computation takes constant time.
We remind that the autocorrelation matrix, which is used to construct the loss estimator in GEOMETRICHEGDE,, has the probabilities Pr [U,, 2/r b. entries. At this point we have shown how to efficiently sample from MWU and how to compute the autocorrelation matrix and thus that GEOMETRICHEGDS can be efficiently implemented.
G.5.1 Comparison with a DAG approach
One can easily see that online learning in m-sets can be modeled as online path planning in an appropriately constructed DAG with E Old m) edges. In this graph, nodes are parameterized by two indices i, E [d + 1] x [m]. The source is node (0, 0) and the sink is [(d + 1, m). At node N (i.
S d we have considered items to 1 and we have selected, j of them. If select item i we make a transition from (i.j)) to Nii + 1, + 1), otherwise we make transition (( + 1. Transitions that lead to selecting more than m items are illegal and at the sink node N(d + 1, m) we should have selected exactly m items. This way, there is an equivalence between paths in the constructed DAG and selections of out of d items and in both cases the reward linear to the components.
For m-sets d items the corresponding DAG has F ((md) edges. Then, sampling can be performed through weight pushing [58] in O () = O (md). which similar to complexity of sampling via the partition function. For the calculation of the autocorrelation matrix the approach O(m²d') using the techniques of (58). an m factor. Thus, along with partitions (which the
of path planning in the m-set DAG would need (
Compared the above our approach action set in Blotto) m-sets is another application, where kernelization is beneficial compared to standard techniques such as weight pushing.
46

---

H
Kernelization in Graphic Matroid Congestion Games
Algorithm 7: Efficient First-Moment Kernel Computations in Graphic Matroid Congestion games
Data: C E E
Compute the weighted Laplacian A gMVx //
EEEE incident C(e) if = if e = (u,
2 Alu, v)
C(e)
otherwise.
/" Compute the LUU decompositions of the submatrices A A-u,-u/ '/
for uu uu do
A_ the submatrix of A derived by deleting row u and column
Compute the LU decomposition (Lus Uu) of A-u,-u- that is lower triangular Ly and upper triangular U,, such that A_a. Lu Un
Compute the d kernels * for j I..,, E|| do
Let uj By be the two nodes connected by edge j
10
Let E-, = E F (j) be the subgraph that does not have edge
1" Compute the weighted Laplacian A in the subgraph where edge is missing */
11
EeEE_ incident u C(e) if
12
[ oj
C(e)
if = (u, E E-j
otherwise.
A A my the submatrix of AD) derived by deleting row uy and column "y
13
Compute the LU decomposition (L, U) of A -, in O(IVI²) using the precomputed
matrices Luy, Un, and the technique of [56]
15
Compute the kernel Ky(C, Eg) det T, U) in O((V)2)
H.1 Proof of Proposition H.1
Let & = (V, E) connected multigraph, and let G = (V, f.) be the meta-graph associated with
G. defined as follows:
1. The vertex sets coincide:
1= D.
2. For edge (u, E with weight (()):
e is the unique edge between u and v, then e É with the same weight:
((e) @(e).
Otherwise, let (e') F. be all parallel edges connecting u and v. Then, we define single meta-edge è E É with weight equal to the total weight of the merged edges:
w(
Σ w(e').
d'Ele')
We say that è a merged edge, and write el C if the edge e' e E participates in the construction of F..
3. Let T denote the set of spanning trees of G, and let 7 denote the set of spanning trees of G.
We derive the following proposition.
47

---

Proposition H.1. It holds that K (v 1) = (x, 1).
Proof. It holds that:
Ki 1)= = ΣI
II
i(()
(125)
FEV
Σ
II
w(e)
II
vi(e)
(126)
fEVEEtie te not merged
ëeTiè merged
=E
II
w(e)
II
Σ
w(ee)
(127)
TEVcET te not merged
B merged CE
EI TEV Ky
i(e)
(128)
(129)
H.2 Proof of Lemma 5.1
Proof. Kernelization.
The above algorithm (Algorithm 7) shows how to compute the first-moment kernel computations in Graphic Matroid Congestion games. The time complexity and correctness of the algorithm are discussed below.
We will use the following:
We need O(VV)* time for computing an LU decomposition.
We need (([V)+t)) time for precomputing the LU decompositions of the minors.
We leverage the property the Matrix-Tree Theorem which allows us to use any submatrix to compute the determinant of the Laplacian matrix. Therefore, we can always make a strategic choice of which row and column to delete. For each edge j Fi]] consider the Laplacian used for the computation of the kernel Ky(C, ē,). The Laplacian for this kernel is constructed in the same way as the one we described above for Ky(C,1 1) but with the difference that C(j) is set to zero. For each node E V. we precompute the LU decomposition of the minors A_,, v,- that is the submatrix of derived by deleting row v and column v-and then for each j = (u, u') E E, we fast compute kernel K(C, 2g) by computing the determinant of that kernel's Laplacian via recursive LU updating [56] in (2 The latter is due to the fact that we can always select a submatrix of the kernel's ' Laplacian that only differs in one element from A_,.-u so we can apply the techniques of [56]. Similar arguments can also be used for fast computing (v Es,') to derive the desired results.
Per-Iteration complexity of SAMPLING.
We implement the SAMPLING procedure of Algorithms and based on the above algorithm (Algorithm 8). Since have guaranteed that the SAMPLING procedure performs exact sampling from a MWU(V, C), what remains to prove is that the implementation we propose correctly computes the conditional kernels. We will prove this using induction argument the iterations [[E]] of the algorithm. We will show that the algorithm correctly computes the new Bernoulli probability 1-
Basis:
The meta- meta-graph is initialized as the initial graph. From Theorem 2.2 and Observation
3.3 we get the unconditional probability P1- The algorithm samples r(1) ~ P1- If the first edge (u, v) is not selected then the algorithm removes it from the new meta-graph and computes Kyg) via the cofactor of the Laplacian of the new meta-graph. the first edge is selected then: (a) if the first edge is not a merging meta-edge (that is, nodes
48

---

Algorithm 8: Elficient Exact Sampling of MWU in Graphic Matroids
Data: C E R
Initialize Meta-Graph = GV, E) and assign weight C(e) to each edge
Compute kernels Ky C, (1) and (v(C, 1) using the Matrix Tree Theorem
Sample r(1) Be [ Kv(C.E))
[v(C,1)
Initialize the cumulative weight w for j == 2, 2.., d do
vjj 1)= then
Find the meta-edge
Graaa containing edge j and reduce its weight by
C(j-1) 1 1)
else
Find the meta-edge of Meta- Graph containing edge 1
10
Update w = w weight(e)
Merge the meta-nodes connected by the meta-edge
12
parallel edges are created then merge them into a single meta-edge containing all the parallel edges and assign to the meta edge weight equal the sum of the weights of the parallel edges
1' Compute the kernel Kyg)
Compute cofactor of the Laplacian of the Meta-Graph (v 1) w
15
16
Find the meta-edge of Meta-Graph containing the edge j and reduce its weight by C(j)
Compute cofactor e' of the Meta-Graph Laplacian using the weights of the meta-edges
18
Kyt)(C (C, E,) w
19
Find the meta-edge of Meta-Graph containing the edge j and increase its weight by C(j)
K (C,)))
20
Pj
Kvu)
Sample v(j) Be(p;)
and do not have common neighbors in the meta-graph then the algorithm removes this edge from the graph, merges the two associated nodes of this edge in the new meta-graph, updates the cumulative weight with the weight of this edge, and computes K Ky()), (b) the first edge is a merging meia-edge (i.e., nodes and do have common neighbors in the meta-graph), then the algorithm makes the above steps, but now the meta-graph is multi-graph. In this case, the algorithm also merges the resulted parallel edges connecting the associated nodes into meta-edge with weight equal with the sum the weights of merged edges. The computation of Kv(2) is correct, due to Proposition H.T because the kernel computation on a multi--raph (that is, the meta -atta-graph after merging the nodes and but before merging the resulted parallel edges) equals the kernel computation on the corresponding new meta-graph.
We use similar arguments with the basis, with the only difference when removing edge. Now, if edge is not selected by the Bernoulli distribution p, but j is part a merged meta-edge (i.c., a meta-edge consisting of many edges of the initial graph), then the algorithm removes its weight from this meta-edge and computes the Again the computation of Kv(+1) is correct due to Proposition H.1
Induction Step:
meta-graph.
Therefore, SAMPLING(V, C.) can implemented in time ((E))VI)), where [V is due to the time we need to compute single kernel.
H.3 Proof of Theorem 5.2
Proof. We directly derive the statement of the theorem by combining Theorems 3.2 and 3.4 with
Theorem 2. and Lemma 5.1
49

---

I Kernelization in Network Congestion Games
We consider the setting used in 49) 27 that is, the network congestion game takes place DAG, consisting of nodes V and edges E. and thus an action of each player is path of DAG. We assume that the maximal path length is K. Following [24], we represent an action of each player E [[]]] as the incidence vector v E {0, 1] of the corresponding path: for all [[]. v(f) = 1 if and only the corresponding edge is present in the path. We denote the action set (i.e., a set of path vectors) of player E [[]]] by VL. Given an action profile (v,, v-4) the total loss player i, L,. the sum the losses of the selected edges of vú Based on the above, it is easy to check that network congestion game is a combinatorial game with [P] players, actions sets {V:} and losses {Li}. where the action vectors are | -immensiooaal and their L1 -n-rm is at most K.
To perform efficient sampling in DAGs and compute all kernels needed by Algorithms 2 and utilize the methodology based on DP developed by [58]. For sampling we need time O(E)) (E) For the first moment calculation we need time ((E)), while for the second moment calculation need time (( Using also the fact that we can compute 2-approximate barycentric spanner in time O(LE) + IV1))), obtain the following CCE convergence results.
Theorem 1.1 (Semi-bandit Convergence CCE). In network congestion game, under the semi- bandit online learning setup, all players adopt Algorithm 2 then after ((E))="K3 runtime, with T 2 | / the time-average joint actions, o" == - D Ø ... @ Vip forms an E- E-CCE of the game with high probability.
Theorem I.2 (Bandit Convergence to CCE). In network congestion game, under the bandit online learning setup, if all players adopt Algorithm [ then after O( E [22+=k=/ee)) runtime, with T 2 K* / the time-average joint actions, o² := Er= of the game with high probability.
(t) u an E-CCE
J Efficient Uniform Random Path Sampling from a DAG
In this section, we describe method for efficiently and exactly sampling paths uniformly at random from a Directed Acyclic Graph (DAG). This process is essential for the initialization phase of MWU. We present the algorithm's 'ss pseudocode and analyze its computational complexity well as its correctness.
Algorithm 9 Uniform Random Path Sampling from a DAG
Require: A DAG G (V, E), source node s, target node t Ensure: A uniformly random path P from s to
1: /* Path Count Precomputation: *
2: Perform a topological sort of the nodes in G.
3: Set C(v) <- for all V, and C(t) 1.
4: for each node in reverse topological order do
5: C(u) E(EN)EE C(u)
6: /" Path Sampling: */
7: Initialize P and set +
8: while v do
9: Calculate probabilities P(u) + Etewee C(w) for all (v, u) E E.
C(u)
10: Select the next node u based on probabilities P(u).
11: Add to P and update t-
12:
return P
Computationally Complexity. The precomputation step requires O(V + E) for the topological sort and another O(V + E) for calculating the path counts. Therefore, the overall complexity of the precomputation step is O(V + E). During the sampling phase, there are at most O(V) iterations, one for each node in the path. Computing transition probabilities takes (ddg(()) for each node v, leading to total of OEE) operations. Thus, the complexity of the sampling phase is OEE).
50

---

Combining both steps, the total complexity of the algorithm is OVV + E).
Correctness Proof. with equal probability.
To demonstrate correctness, we prove that every path P from is selected
The dynamic programming step calculates C(u). the number of paths from node t. Using the recurrence relation:
C(v)
Σ C(u),
(M,
ensure that C(s) represents the total number of paths from to t. and C(t) indicates the number of paths passing through v. At each node v, the transition probability to a neighboring node u is:
C(u)
C(u)
P(u v)
E(ew)e B C(w)
C(v)
For any path p= 8 +
+ 22
in G the probability of selecting it is given by the
product transition probabilities:
P(P) P(m 8) P(u2 v1) P(t [K].
C(u) By substituting P(u v) C(o)
we get:
P(P) = ((v)) C(
C(t)
C(t) 1
((s) C(e1
C(eg)
C(s)
C(s)
Since C(s) equals the total number paths from 8 to every path is selected with an equal probability of c(s)*
51


Reviews:
[{"review_id": "nKUoBHzIg6", "reviewer": "Reviewer_zzYs", "summary": "This paper is concerned with learning coarse correlated equilibria (CCE) in normal form games with an exponentially large number of This paper is concerned with learning coarse correlated equilibria (CCE) in normal form games with an exponentially large number of actions per player, making the problem non-trivial and computationally expensive. While existing works have addressed the challenge via kernelization, they have only done so in the full-information setting; and the ones that solve the games under bandit-feedback have impractical runtimes. By building on the existing algorithm for bandit-feedback, namely the GeometricHedge, and kernelization framework, the authors propose a new computationally efficient framework that can learn CCE of several polyhedral games under partial-information settings. The authors provide efficient kernalization approach for three different games: the multi-player Colonel Blotto, graphic matroid and network congestion game.", "questions": "1. Kernelization is the core of the proposed method, and the authors provide kernelization techniques for each of the three games. My questions are: \n\n   a) Do these three techniques encompass the majority of the polyhedral games? \n\n   b) Do you envision a higher‑level framework into which any polyhedral game can be cast, so that a “universal” kernelization technique could be applied?\n\n2. What do you think the challenges are when it comes to extending your method to solve for tighter equilibrium concepts: both CE and NE? Could you comment on the complexity of reaching an NE with the current approach?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n- The paper is well written with clearly laid out motivation for studying the problem of **efficiently** learning CCEs of polyhedral games under partial-information setting. \n- Detailed pseudocode for the proposed algorithm and proofs. \n\n\n\n**Limitations**\n- While theoretical complexity are provided and proved, empirical studies are lacking. Given that one of the motivations for studying the problem was lack of \"efficient implementation\" of GeometricHedge algorithm, I think empirical results, such as: average regret over iterations, would make the paper stronger.", "was_revised": true, "final_justification": "I thank the authors for their thorough response. They have detailed the additional experiments they plan to include, rather than merely saying “we will add empirical results”, which directly addresses my primary concern about insufficient empirical evidence. Accordingly, I am raising my score to 5.", "rebuttal": "Dear reviewer,\n\nThank you for your time, and your positive evaluation! We reply to your remarks and questions below:\n\n\n> While theoretical complexity are provided and proved, empirical studies are lacking. Given that one of the motivations for studying the problem was lack of \"efficient implementation\" of GeometricHedge algorithm, I think empirical results, such as: average regret over iterations, would make the paper stronger.\n\nThe way that OpenReview has been set up this year, it is not possible to include any simulations during the rebuttal stage (or even the result thereof through an anonymized picture or github link). However, we will be happy to take advantage of the extra page to include proof-of-concept experiments aimed at validating the efficiency of our approach—specifically, measuring $\\mathrm{Reg}(T)/T$ as a function of $T$ until convergence to an ε-CCE.\n\nIn more detail, we will add the following experimental setups:\n1. Experiments on congestion games under (semi-)bandit feedback. We will use the Sioux Falls dataset (part of the well-known TransportationNetworks collection), which has been widely used in the literature to evaluate performance in congestion games. The dataset represents a network with 24 nodes and 76 edges. We will use 100 players and standard linear cost functions per edge. \n2. Experiments on Colonel Blotto games under (semi-)bandit feedback. We will use different seeds to produce randomized Colonel Blotto games consisting of 10 players, 100 battlefields and 1000 soldiers per player. The reward function will be defined as \"Winner Takes All\" (that is, the battlefield reward of player $i$ is 1 if player $i$ assigned more soldiers in this battlefield than all other players, otherwise 0).\n\n---\n> Do these three techniques encompass the majority of the polyhedral games?\n\nWe have considered some of the most prominent examples of polyhedral games and have demonstrated a wide array of kernelization techniques (i.e., generating functions in Colonel Blotto, weighted counting in Graphic Matroid Congestion Games and dynamic programming in Network Congestion Games). We believe that our techniques may be leveraged for other polyhedral game settings as well, but we leave such a direction as an avenue for future research. \n\n---\n> Do you envision a higher‑level framework into which any polyhedral game can be cast, so that a “universal” kernelization technique could be applied?\n\nBoth yes and no. The proposed learning algorithms can indeed be applied to any polyhedral game as a general, umbrella framework and achieve the same no-regret guarantees (in terms of $T$, $m$, and $d$). The obstacle however is the kernelization part, which is not application-agnostic and indeed needs to leverage the specific structure of the class of polyhedral games in question (in terms of the facet structure of the underlying polyhedra etc.)\n\nWe should note here that not all polyhedral structures are amenable to efficient kernelization, since for some classes of polyhedra kernelization is provably hard. For example, consider the problem of finding Hamiltonian cycles in a graph. In this setting, the action vectors are binary edge-incidence vectors of size $|E|$, similarly to the case of congestion games that we consider in the paper. However, in this case, kernelization is NP-hard, because the all-ones kernel $K(1,1)$ is equal to the total number of Hamilton cycles in the graph and if positive it would imply the existence of a Hamiltonian cycle, and vice versa (thus sovling a well-known NP-hard decision problem).\n\n---\n> What do you think the challenges are when it comes to extending your method to solve for tighter equilibrium concepts: both CE and NE? Could you comment on the complexity of reaching an NE with the current approach?\n\n- **For Nash equilibria:** there is no connection to no-regret learning in the general case and thus kernelization does not seem to be relevant. Note that finding approximate Nash equilibria in general-sum normal-form games is PPAD-hard, and normal-form games are a special case of polyhedral games where the action polyhedron is a simplex. Thus, even through kernelization there is no hope for efficient learning of Nash equilibria in general. In specific cases however, kernelization can indeed be used to learn Nash equilibria efficiently: \n    1. First, in zero-sum games, due to the so-called equilibrium collapse property, the set of coarse correlated equilibria coincides in value with the set of Nash equilibria in zero-sum games and  the marginalization of a CCE is a Nash equilibrium in these games. Thus, our kernelization method for learning CCE can be used to learn Nash as well. \n    2. Second, in potential games (such as the congestion games we consider), even though there is no collapse, Nash equilibria can be easily learnt, and there exist algorithms based on MWU to learn Nash equilibria in the full information setting (see [1]). Since kernelization is used to implement MWU efficiently, the approach of [1] paired with the kernelization trick can be used to efficiently learn Nash equilibria in polyhedral potential games.\n\n- **For correlated equilibria:** it is a major open question in the field whether one can design FPTAS algorithms to find CE in polyhedral games. Only a PTAS algorithm is known [2,3], which is a learning approach and depends on efficient MWU implementation in the game's action space. Thus, kernelization can be also used in this framework and yield efficient (PTAS) algorithms for learning CE in polyhedral games.\n\n---\nThank you again for your constructive input and positive evaluation—please do not hesitate to reach out if you have any further questions or remarks, we are looking forward to a constructive exchange during the rebuttal phase!\n\nKind regards,\n\nThe authors \n\n---\n### References\n\n[1] Cen, Shicong, Fan Chen, and Yuejie Chi. \"Independent natural policy gradient methods for potential games: Finite-time global convergence with entropy regularization.\" 2022 IEEE 61st Conference on Decision and Control (CDC). IEEE, 2022.\n\n[2] Dagan, Yuval, et al. \"From external to swap regret 2.0: An efficient reduction for large action spaces.\" Proceedings of the 56th Annual ACM Symposium on Theory of Computing. 2024.\n\n[3] Peng, Binghui, and Aviad Rubinstein. \"Fast swap regret minimization and applications to approximate correlated equilibria.\" Proceedings of the 56th Annual ACM Symposium on Theory of Computing. 2024."}, {"review_id": "kr0xxsQLE9", "reviewer": "Reviewer_pKuV", "summary": "This paper investigates how to efficiently learn coarse correlated equilibria (CCE) in large structured games (polyhedral games) when players have only partial feedback—that is, they only observe the outcomes of the actions they took, rather than all possible actions. The key idea is to extend recent kernelization techniques that have previously worked only when full information is available to settings where only bandit or semi-bandit feedback is given.\n\nThe paper develops new algorithms for this setting, analyzes their performance in several game types (e.g., Colonel Blotto, congestion games), and claims significant improvements in both theoretical regret bounds and runtime. The paper appears to resolve some known open problems in this domain.", "questions": "1. Could the authors provide simple, concrete examples (e.g., toy games) to illustrate how the algorithms work in practice?\n\n2. Are there any empirical results or experiments—even small simulations—that could demonstrate the effectiveness or practicality of the approach?\n\n3. How broadly applicable are these techniques beyond the specific game classes discussed (e.g., Colonel Blotto, matroid games)?\n\n4. Are there existing systems or domains where these methods could be deployed or tested?\n\n5. What are the main barriers to implementation? Are the kernel computations feasible for moderate-scale problems?", "limitations": "No", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n1. The paper is clearly written, with helpful figures and detailed explanations that aid understanding despite the technical subject matter.\n\n2. It appears to be a significant theoretical contribution, pushing the boundaries of what’s possible in a well-studied class of game-theoretic learning problems.\n\n3. The organization is effective, with a logical flow from problem motivation to technical development and results.\n\n4. The comparison tables with prior work are helpful for understanding claimed improvements.\n\nWeaknesses\n1. The paper is technically dense, and many results depend on domain-specific knowledge of combinatorial games, kernel methods, and no-regret learning, which may limit accessibility to a broader audience.\n\n2. There are no empirical experiments or simulations to demonstrate the practical utility or performance of the proposed algorithms.\n\n3. From a non-expert (in normal-form games and polyhedral games) perspective, it is difficult to judge the novelty or correctness of the technical contributions or to verify the extent to which the improvements over previous work are significant.\n\n4. The assumptions and applicability to real-world systems are not always clear—for example, it is not obvious where such structured games arise in practice or how feasible these methods would be to implement.", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer,\n\nThank you for your time, constructive input, and positive evaluation! We reply to your remarks and questions below:\n\n---\n> The paper is technically dense, and many results depend on domain-specific knowledge of combinatorial games, kernel methods, and no-regret learning, which may limit accessibility to a broader audience.\n\nWe tried to strike a balance between describing concepts that are relatively well known in the fields (such as no-regret learning), and providing the necessary intuition and background for our contributions. We understand however that some more specialized topics—such as kernelization and combinatorial games—could have been explained in more detail, and we will be happy to take advantage of the extra page available in the camera-ready round to do so. In the same spirit, we will also include a non-technical, high-level description of our results and the challenges involved for a broader audience—that is, not necessarily with a background in online learning and/or game theory.\n\n---\n> From a non-expert (in normal-form games and polyhedral games) perspective, it is difficult to judge the novelty or correctness of the technical contributions or to verify the extent to which the improvements over previous work are significant.\n\nWhile our work builds on the general idea of kernelization from prior literature, our main novelty lies in extending it to previously unexplored settings—both in terms of feedback models (semi-bandit and bandit) and game structures (such as Colonel Blotto and Matroid Congestion Games).\n\nIn particular, our main technical novelties are as follows:\n\n1. Kernelization in the (semi-)bandit setting: We show how to use kernelization not only for first-moment calculations, as in prior work on full-information feedback [1], but also to efficiently compute second moments and perform exact sampling. These operations are essential in the (semi-)bandit setting and, to the best of our knowledge, had not been addressed in earlier work.\n2. We employ new kernelization techniques for classes of polyhedral games that had not been analyzed from this perspective before: \n    - In Graphic Matroid Congestion Games, we design novel algorithms and analysis (see Appendix H) for exact sampling and moment computation, resolving a long-standing open problem posed by Cesa-Bianchi & Lugosi [7] on how to perform exact sampling from the ComBand algorithm (and thus MWU) in spanning trees. In particular, the kernels used for sampling are on the conditional polytope, that is on subsets of the original actions where some coordinates are restricted to have a specific 0-1 value. Computing such conditional kernels presents additional challenges compared to standard kernels: while standard kernels can be obtained by directly applying the Matrix Tree Theorem as a black box, conditional kernels require several non-trivial technical steps before the theorem can be applied. \n    - In Colonel Blotto games, we introduce an efficient action representation of size $nk$, develop a kernelization procedure in this representation, and apply acceleration techniques to reduce the amortized kernel computation time to $O(\\log n)$. This kernelization also resolves an open question from [8]. Our techniques share similarities with those in [6] for the kernelization of m-sets, in the sense that, in both settings, a kernel can be computed via specific coefficients of some polynomial (see Eq. 3 for Colonel Blotto); however, designing fast kernelization algorithms in Colonel Blotto is substantially more challenging because the polynomial factors are $n$-degree polynomials as opposed to the binomials used for m-sets (see also Algorithm 4, Appendix G).  \n3. Our regret analysis paired with the above contributions led to a significant improvement of the total runtime to learn CCE in terms of the game parameters.\n\nWe will make sure to highlight the above discussion in the camera-ready version of the paper.\n\n---\n> There are no empirical experiments or simulations to demonstrate the practical utility or performance of the proposed algorithms. Could the authors provide simple, concrete examples (e.g., toy games) to illustrate how the algorithms work in practice? Are there any empirical results or experiments—even small simulations—that could demonstrate the effectiveness or practicality of the approach?\n\nThe way that OpenReview has been set up this year, it is not possible to include any simulations during the rebuttal stage (or even the result thereof through an anonymized picture or github link). However, we will be happy to take advantage of the extra page to include proof-of-concept experiments aimed at validating the efficiency of our approach—specifically, measuring $\\mathrm{Reg}(T)/T$ as a function of $T$ until convergence to an ε-CCE.\n\nIn more detail, we will add the following experimental setups:\n1. Experiments on congestion games under (semi-)bandit feedback. We will use the Sioux Falls dataset (part of the well-known TransportationNetworks collection), which has been widely used in the literature to evaluate regret-like performance in congestion games. The dataset represents a network with 24 nodes and 76 edges. We will use 100 players and the standard linear cost function per edge. \n2. Experiments on Colonel Blotto games under (semi-)bandit feedback. We will use different seeds to produce randomized Colonel Blotto games consisting of 10 players, 100 battlefields and 1000 soldiers per player. The reward function will be defined as \"Winner Takes All\" (that is, the battlefield reward of player $i$ is 1 if player $i$ assigned more soldiers in this battlefield than all other players, otherwise 0).\n\n---\n> How broadly applicable are these techniques beyond the specific game classes discussed (e.g., Colonel Blotto, matroid games)?\n\nWe have considered some of the most prominent examples of polyhedral games and have demonstrated a wide array of kernelization techniques (i.e., generating functions in Colonel Blotto, weighted counting in Graphic Matroid Congestion Games and dynamic programming in Network Congestion Games). We believe that our techniques may be leveraged for other polyhedral settings as well, but we leave such a direction as an avenue for future research. \n\n---\n> The assumptions and applicability to real-world systems are not always clear, for example, it is not obvious where such structured games arise in practice or how feasible these methods would be to implement. Are there existing systems or domains where these methods could be deployed or tested?\n\nAll game settings we consider are of particular interest in the theoretical computer science and game theory community, as they can model many real-world applications. The Colonel Blotto games are often used to model political campaigns [1], where battles represent voting districts, and also have applications in security problems in IoT networks and cognitive radio [2] and ecological modeling [3]. Network congestion games have been widely used to model traffic congestion and routing problems [4], while graphic matroid congestion are used to model network design problems in which players compete for the edges of a graph in order to build a spanning tree [5].\n\n---\n> What are the main barriers to implementation? Are the kernel computations feasible for moderate-scale problems?\n\nYes, indeed, the overall kernel computation time required for an iteration of our method is $O(nk\\log n)$ for the full-information and semi-bandit and $O(n^2 k^2)$ for the bandit setting in Colonel Blotto, $O(|E||V|^ω)$ for the full-information and semi-bandit and $O(|E||V|^{ω+1} + |E|^2|V|^2)$ for the bandit setting in graphic matroid congestion games (where $ω < 2.5$). For instance, consider the semi-bandit setting. Our method can be implemented efficiently for an input of $n=10^5$ and $k=10^4$ in Colonel Blotto, and for a complete graph of 100 nodes in graphic matroid congestion games.  \n\n---\nThank you again for your input and positive evaluation—please do not hesitate to reach out if you have any more questions or remarks, we are looking forward to a further constructive exchanges during the discussion phase!\n\nKind regards,\n\nThe authors \n\n---\n\n\n### References\n\n[1] Behnezhad, Soheil, et al. \"Optimal strategies of blotto games: Beyond convexity.\" Proceedings of the 2019 ACM Conference on Economics and Computation. 2019.\n\n[2] Min, Minghui, et al. \"Defense against advanced persistent threats in dynamic cloud storage: A colonel blotto game approach.\" IEEE Internet of Things Journal 5.6 (2018): 4250-4261.\n\n[3] Golman, Russell, and Scott E. Page. \"General Blotto: games of allocative strategic mismatch.\" Public Choice 138.3 (2009): 279-299.\n\n[4] Roughgarden, Tim, and Éva Tardos. \"How bad is selfish routing?.\" Journal of the ACM (JACM) 49.2 (2002): 236-259.\n\n[5] Ackermann, Heiner, Heiko Röglin, and Berthold Vöcking. \"On the impact of combinatorial structure on congestion games.\" Journal of the ACM (JACM) 55.6 (2008): 1-22.\n\n[6] Farina, Gabriele, et al. \"Kernelized multiplicative weights for 0/1-polyhedral games: Bridging the gap between learning in extensive-form and normal-form games.\" International Conference on Machine Learning. PMLR, 2022.\n\n[7] Cesa-Bianchi, Nicolo, and Gábor Lugosi. \"Combinatorial bandits.\" Journal of Computer and System Sciences 78.5 (2012): 1404-1422.\n\n[8] Beaglehole, Daniel, et al. \"Sampling equilibria: Fast no-regret learning in structured games.\" Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, 2023."}, {"review_id": "TnuypGYo2f", "reviewer": "Reviewer_wspx", "summary": "The authors consider the problem of computing coarse correlated equilibria for games that have succinct representation. In particular, they focus on polyhedral games, including network congestion games, Colonet Blotto games. Building upon a recent development that enables to “kernelize” no-regret like dynamics, the authors are able to provide algorithms that provably converge to a CCE and that do so requiring an amount of computation that depends polynomially on the size of the succinct game (as opposed to polynomially in the size of the expanded game, which will be exponential in the size of the original succinct game)", "questions": "Besides the review, it would be good to obtain some more understanding on the challenges one has to overcome to apply the \"kernelization\" trick in these settings? How much can one use from previous work as opposed to having to develop new ideas?", "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": "Assessment:\n-  I found the paper very well structured and written, and I enjoyed reading through it. \n- The technical results are novel and focus on an area that has received increased attention.  \n- The main idea is to extend kernelization tricks from previous work. This is not immediate and requires additional work (e.g., second moments). However the idea itself mostly follows previous work, so the novelty is curtailed by that.\n- There are no numerics. How does this approach compare “in practice” on standard network congestion games, eg Sioux Fall? In other words: is the analysis better, or is the algorithm itself better?\n- I also note that in certain bandit / semi-bandit settings, the authors are not the first to obtain a dependance on the size of the game that is polynomial (e.g., compare with previous work cited where their dependence is polynomial, albeit with a bad exponent d^10). It would be good to make this clear in the intro too.", "was_revised": true, "final_justification": "After engaging in the rebuttal: a strong paper with a clear case for acceptance.", "rebuttal": "Dear reviewer,\n\nThank you for your time, and your positive evaluation! We reply to your remarks and questions below:\n\n> The main idea is to extend kernelization tricks from previous work. This is not immediate and requires additional work (e.g., second moments). However the idea itself mostly follows previous work, so the novelty is curtailed by that. \n\nWe certainly do not claim any primarcy in introducing kernelization as a concept: the novelty of our contributions lie in extending it to settings with partial information (semi-bandit and bandit feedback) and the polyhedral structure of the underlying game (such as Colonel Blotto and Matroid Congestion Games). \n\nIn particular, our main technical novelties are as follows:\n\n1. Kernelization in the (semi-)bandit setting: We show how to use kernelization not only for first-moment calculations, as in prior work on full-information feedback [1], but also to efficiently compute second moments and perform exact sampling. These operations are essential in the (semi-)bandit setting and, to the best of our knowledge, had not been addressed in earlier work.\n2. We utilize novel kernelization techniques to classes of polyhedral games that had not been analyzed from this perspective before:\n    - In Graphic Matroid Congestion Games, we design novel algorithms and analysis (see Appendix H) for exact sampling and moment computation, resolving a long-standing open problem posed by Cesa-Bianchi & Lugosi [3] on how to perform exact sampling from the ComBand algorithm (and thus MWU) in spanning trees. In particular, the kernels used for sampling are on the conditional polytope, that is on subsets of the original actions where some coordinates are restricted to have a specific 0-1 value. Computing such conditional kernels presents additional challenges compared to standard kernels: while standard kernels can be obtained by directly applying the Matrix Tree Theorem as a black box, conditional kernels require several non-trivial technical steps before the theorem can be applied. \n    - In Colonel Blotto games, we introduce an efficient action representation of size $nk$, develop a kernelization procedure in this representation, and apply acceleration techniques to reduce the amortized kernel computation time to $O(\\log n)$. This kernelization also resolves an open question from [4]. Our techniques share similarities with those in [5] for the kernelization of m-sets, in the sense that, in both settings, a kernel can be computed via specific coefficients of some polynomial (see Eq. 3 for Colonel Blotto); however, designing fast kernelization algorithms in Colonel Blotto is substantially more challenging because the polynomial factors are $n$-degree polynomials as opposed to the binomials used for m-sets (see also Algorithm 4, Appendix G).  \n\n---\n> Besides the review, it would be good to obtain some more understanding on the challenges one has to overcome to apply the \"kernelization\" trick in these settings? How much can one use from previous work as opposed to having to develop new ideas?\n\nWe used kernelization to efficiently implement some demanding operations that appear in our learning algorithms. \n\nIn the semi-bandit case, we designed the learning algorithm from scratch. It turned out that the unbiased estimator uses the first moments of the policy and thus we could directly use the kernel trick proposed in [5] for the calculation of first moments in polyhedral games. \n\nAn extra demanding operation required for the semi-bandit and the bandit learning is sampling from the player's policy. This operation is not required in the full information setting and we had to design from scratch a method for efficient sampling based on kernelization. In particular, the kernels used for sampling are on the conditional polytope, that is on subsets of the original actions where some coordinates are restricted to have a specific 0-1 value. The computation of such conditional kernels has extra challenges compared to the standard kernels as can be seen in our study of Graphic Matroid Congestion Games (Appendix H). In these polyhedra, the standard kernels could be computed by using the Matrix Tree Theorem as a blackbox but conditional kernels required several technicalities before the Matrix Tree Theorem could be applied. \n\nIn the bandit setting, second moment calculation is required for the construction of the loss estimator. Inspired by the ideas of [5] for the use of kernels in first moment calculation we extend the idea to the second moment. In this case, the formulas are slightly more complicated and the use of inclusion-exclusion principle is required as an extra step. This is a significant difference compared to the first moment calculation and actually opens a path to generalizing the technique to higher order moments. However, note that the use of inclusion-exclusion principle for higher order moments has the limitation that the dependence on the degree of the moment is exponential. This is the reason that we can not directly use this trick for the calculation of conditional kernels required in sampling.\n\nRegarding applications of kernelization on specific polytopes of interest, we considered Colonel Blotto and Graphic Matroids, two games that have not been studied through the prism of kernelization before. In Graphic Matroids, we observed that kernel computation can be performed by a direct application of the Matrix Tree Theorem. However, in order to accelerate the calculation of groups of kernels we use some technical precomputing based on rank 1 modifications. For the calculation of conditional kernels used for sampling there are significant challenges as we described above. For an overview of our techniques for the kernelization of Colonel Blotto, see our answer to the previous question, in particular paragraph 2(b).\n\n---\n> There are no numerics. How does this approach compare “in practice” on standard network congestion games, eg Sioux Fall? In other words: is the analysis better, or is the algorithm itself better?\n\nThe way that OpenReview has been set up this year, it is not possible to include any simulations during the rebuttal stage (or even the result thereof through an anonymized picture or github link). However, we will be happy to take advantage of the extra page to include proof-of-concept experiments aimed at validating the efficiency of our approach—specifically, measuring $\\mathrm{Reg}(T)/T$ as a function of $T$ until convergence to an ε-CCE.\n\nIn more detail, we will add the following experimental setups:\n\n1. Experiments on congestion games under (semi-)bandit feedback. We will use the Sioux Falls dataset (part of the well-known TransportationNetworks collection), which has been widely used in the literature to evaluate regret-like performance in congestion games. The dataset represents a network with 24 nodes and 76 edges. We will use 100 players and the standard linear cost function per edge. \n2. Experiments on Colonel Blotto games under (semi-)bandit feedback. We will use different seeds to produce randomized Colonel Blotto games consisting of 10 players, 100 battlefields and 1000 soldiers per player. The reward function will be defined as \"Winner Takes All\" (that is, the battlefield reward of player $i$ is 1 if player $i$ assigned more soldiers in this battlefield than all other players, otherwise 0).\n\n---\n> I also note that in certain bandit / semi-bandit settings, the authors are not the first to obtain a dependance on the size of the game that is polynomial (e.g., compare with previous work cited where their dependence is polynomial, albeit with a bad exponent d^10). It would be good to make this clear in the intro too.\n\nIndeed our paper is not the first to obtain a polynomial dependence on the game parameters $d$ and $m$. As we have discussed in the paper, for generic polyhedral games (that is, without considering a specific structure, e.g., Colonel Blotto), [1] and [2] proposed algorithms for continuous action spaces, which can be extended to polyhedral games achieving a regret bound of $\\mathcal{O}(md^{7/2}\\sqrt{T})$ and $\\mathcal{O}(md^{2}\\sqrt{T})$, respectively. However, the above bounds combined with a per-iteration complexity, which heavily depends on $d$, result in impractical runtime complexity results for learning CCE. In particular, the runtime of the algorithm in [1] to find CCE scales as $d^{10}$, while that of [2] scales as $d^9$; both exhibiting impractically large dependence on the game parameters. We have already referred to these previous works in the introduction, but we can use the extra space to make a more extended comparison. \n\nRegarding the applications of interest (Colonel Blotto and Congestion games), we have included a discussion in Appendix A (Further Related Work) with previous works appearing in the Tables. We could incorporate that discussion into the introduction as well.  \n\n---\nThank you again for your time, input and positive evaluation—we remain at your disposal if you have any further questions!\n\nKind regards,\n\nThe authors \n\n---\n\n### References\n\n[1] Lee et al. \"Bias no more: high-probability data-dependent regret bounds for adversarial bandits and mdps.\" NeurIPS (2020).\n\n[2] Zimmert and Lattimore. \"Return of the bias: Almost minimax optimal high probability bounds for adversarial linear bandits.\" Conference on Learning Theory. 2022.\n\n[3] Cesa-Bianchi, Nicolo, and Gábor Lugosi. \"Combinatorial bandits.\" Journal of Computer and System Sciences 78.5 (2012): 1404-1422.\n\n[4] Beaglehole, Daniel, et al. \"Sampling equilibria: Fast no-regret learning in structured games.\" Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, 2023.\n\n[5] Farina, Gabriele, et al. \"Kernelized multiplicative weights for 0/1-polyhedral games: Bridging the gap between learning in extensive-form and normal-form games.\" International Conference on Machine Learning. PMLR, 2022."}, {"review_id": "ttuP0djaXc", "reviewer": "Reviewer_CYJo", "summary": "This paper develops efficient payoff-based learning algorithms for computing coarse correlated equilibria (CCE) in polyhedral games, which have exponentially large action spaces and combinatorial structure. These include Colonel Blotto and congestion games. This paper extends kernelization techniques from full-information setting to partial-information regimes (bandit and semi-bandit feedback), enabling no-regret learning with improved runtime and regret bounds. The authors proposed efficient loss estimation and sampling methods in two games: Colonel blotto and congestion games, addressing key open problems in the literature.", "questions": "See weakness", "limitations": "See weakness", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths \n1. The paper is clearly written, and the theoretical results and proofs appear sound and rigorous. \n2. It proposes efficient kernel-based algorithms for learning coarse correlated equilibria in Colonel Blotto and congestion games, achieving several state-of-the-art runtime guarantees. Notably, the work addresses key open problems in the literature, including extending kernelization techniques to the bandit setting and improving regret bounds under partial information. \n\nWeaknesses \nIt is unclear whether the obtained runtime bounds are tight. The authors do not provide matching lower bounds or discuss potential optimality, leaving open the question of whether further improvements are possible.", "was_revised": true, "final_justification": "Thanks for the response. I will maintain my score.", "rebuttal": "Dear reviewer,\n\nThank you for your time, and your positive evaluation! We reply to your remarks and questions below:\n\n> It is unclear whether the obtained runtime bounds are tight. The authors do not provide matching lower bounds or discuss potential optimality, leaving open the question of whether further improvements are possible.\n\nTo the best of our knowledge, there are no lower bounds for the specific setting we consider, that is runtime to learn CCE. In terms of regret, for the full-info case, the regret is polylogarithmic in terms of $T$ and thus near-optimal (see [1] for more details). However, in the semi-bandit and bandit case it is a major open question whether it is possible to improve on the $\\sqrt{T}$, which is optimal for adversarial learning. In fully adversarial semi-bandit problems, our regret is indeed optimal in terms of $d$ and $T$ and only a factor of $\\sqrt{m}$ away from the lower bound for expected regret. Nevertheless, our paper focuses on realised regret which is a stronger notion than the ordinary expected regret, so it is not clear if this is a gap that can actually be closed in this case. In the adversarial bandit case, the situation is much more complicated because the minimax optimal regret bound of $\\sqrt{dT \\log(|A|)}$ is currently only known to be achieved by inefficient algorithms (e.g., see [2]), which have exponential (in $d$) per-iteration complexity.\n\n\n---\n\nThank you again for your constructive input and encouraging words - please do not hesitate to reach out if you have any further questions!\n\nKind regards,\n\nThe authors \n\n---\n\n### References \n[1] Farina, Gabriele, et al. \"Kernelized multiplicative weights for 0/1-polyhedral games: Bridging the gap between learning in extensive-form and normal-form games.\" International Conference on Machine Learning. PMLR, 2022.\n\n[2] Zimmert, Julian, and Tor Lattimore. \"Return of the bias: Almost minimax optimal high probability bounds for adversarial linear bandits.\" Conference on Learning Theory. PMLR, 2022."}, {"review_id": "XcKsYEWeVU", "reviewer": "Reviewer_x1xn", "summary": "This paper studies no-regret learning and approximate Coarse Correlated Equilibria (CCE) computation under different information settings. The authors demonstrate that efficient approaches for adversarial linear bandits can be applied to several classes of prominent games. These settings include Congestion and Colonel Blotto games, which have garnered significant attention over many decades across disciplines. In particular, the authors introduce Kernelized Geometric Hedge to achieve significant, though polynomial, improvements in runtime and representation costs. To implement their algorithm efficiently, the authors demonstrate that the second-moment of the MWU distribution can also be kernelized, and the authors design appropriate representations and kernel functions for the games they consider. For Colonel Blotto, this involved computing a generating polynomial for this kernel.", "questions": "What about Nash Equilibria in two player settings? Can these results be applied the obtain stronger results there?\n\nWhat prevents kernelized approaches from being applied to Correlated Equilibria computation? Are these limitations fundamental?\n\nCan you explain the semi-bandit feedback setting for your representation in Colonel Blotto? Why does semi-bandit feedback make sense in this setting?\n\nIn Beaglehole et al. 2023, they perform a piece-wise approximation of a partition function to achieve polylogarithmic dependence on the number of soldiers, can a similar trick be applied here?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\\\n-\tThe authors address fundamental and well-studied challenges in (algorithmic) game theory and online learning.\\\n-\tTheir approach significantly improves over previous approaches, especially in bandit and semi-bandit settings.\n\nWeaknesses:\\\n-\tThe aspects of their method that are novel, as opposed to being applications of existing ideas is unclear. This is a small weakness given the improvements they achieved on important problems. The paper may benefit from clarifying which technical ideas are adapted from other words and which are more ‘original’. \\\n-\tThe runtimes still appear somewhat large, the paper might benefit from a minimal experiment demonstrating the practicality of their proposed algorithm.\n\nOther Minor comments:\\\n-\tThe Kernelized MWU formula (184-193) is a bit difficult to understand. This part could benefit from some additional explanation given how crucial it is to the techniques in the paper. For example, the first moment calculation theorem seems unmotivated at that position.\\\n-\tIs there a type in Eqn 3? Why is there a j exponent over z?\\\n-\tIt would be nice to have some explanation for how this polynomial in Eqn 3 is used to compute the kernels.", "was_revised": true, "final_justification": "This paper develops efficient algorithms for important problems in online learning and algorithmic game theory. I therefore recommend acceptance.", "rebuttal": "Dear reviewer,\n\nThank you for your time, and your positive evaluation! We reply to your remarks and questions below:\n\n> The aspects of their method that are novel, as opposed to being applications of existing ideas is unclear. This is a small weakness given the improvements they achieved on important problems. The paper may benefit from clarifying which technical ideas are adapted from other works and which are more ‘original’.\n\nWhile our work builds on the general idea of kernelization from prior literature, our main novelty lies in extending it to previously unexplored settings—both in terms of feedback models (semi-bandit and bandit) and game structures (such as Colonel Blotto and Matroid Congestion Games).\n\nIn particular, our main technical novelties are as follows:\n\n1. Kernelization in the (semi-)bandit setting: We show how to use kernelization not only for first-moment calculations, as in prior work on full-information feedback [1], but also to efficiently compute second moments and perform exact sampling. These operations are essential in the (semi-)bandit setting and, to the best of our knowledge, had not been addressed in earlier work.\n2. We utilize novel kernelization techniques to classes of polyhedral games that had not been analyzed from this perspective before: \n(a) In Graphic Matroid Congestion Games, we design novel algorithms and analysis (see Appendix H) for exact sampling and moment computation, resolving a long-standing open problem posed by Cesa-Bianchi & Lugosi [4] on how to perform exact sampling from the ComBand algorithm (and thus MWU) in spanning trees. In particular, the kernels used for sampling are on the conditional polytope, that is on subsets of the original actions where some coordinates are restricted to have a specific 0-1 value. Computing such conditional kernels presents additional challenges compared to standard kernels: while standard kernels can be obtained by directly applying the Matrix Tree Theorem as a black box, conditional kernels require several non-trivial technical steps before the theorem can be applied. \n(b) In Colonel Blotto games, we introduce an efficient action representation of size $nk$, develop a kernelization procedure in this representation, and apply acceleration techniques to reduce the amortized kernel computation time to $O(\\log n)$. This kernelization also resolves an open question from [5]. Our techniques share similarities with those in [1] for the kernelization of m-sets, in the sense that, in both settings, a kernel can be computed via specific coefficients of some polynomial (see Eq. 3 for Colonel Blotto); however, designing fast kernelization algorithms in Colonel Blotto is substantially more challenging because the polynomial factors are $n$-degree polynomials as opposed to the binomials used for m-sets (see also Algorithm 4, Appendix G).  \n\n\n> The runtimes still appear somewhat large, the paper might benefit from a minimal experiment demonstrating the practicality of their proposed algorithm.\n\nThe way that OpenReview has been set up this year, it is not possible to include any simulations during the rebuttal stage (or even the result thereof through an anonymized picture or github link). However, we will be happy to take advantage of the extra page to include proof-of-concept experiments aimed at validating the efficiency of our approach—specifically, measuring $\\mathrm{Reg}(T)/T$ as a function of $T$ until convergence to an ε-CCE.\n\nIn more detail, we will add the following experimental setups:\n1. Experiments on congestion games under (semi-)bandit feedback. We will use the Sioux Falls dataset (part of the well-known TransportationNetworks collection), which has been widely used in the literature to evaluate regret-like performance in congestion games. The dataset represents a network with 24 nodes and 76 edges. We will use 100 players and the standard linear cost function per edge. \n2. Experiments on Colonel Blotto games under (semi-)bandit feedback. We will use different seeds to produce randomized Colonel Blotto games consisting of 10 players, 100 battlefields and 1000 soldiers per player. The reward function will be defined as \"Winner Takes All\" (that is, the battlefield reward of player $i$ is 1 if player $i$ assigned more soldiers in this battlefield than all other players, otherwise 0).\n\n>  The Kernelized MWU formula (184-193) is a bit difficult to understand. This part could benefit from some additional explanation given how crucial it is to the techniques in the paper. For example, the first moment calculation theorem seems unmotivated at that position.\n\nThanks a lot for this comment. The key idea, as shown in [1], is that computing the first moment is sufficient to simulate MWU under full-information feedback. This is because, in the full-information setting of [1], each agent plays a mixed strategy - which is exactly this first moment - rather than sampling an action from the MWU distribution. Moreover, this first moment encapsulates sufficient information about the MWU distribution, because, using standard Carathéodory decomposition techniques, it can be efficiently decomposed into a low-support distribution, from which sampling becomes efficient. We will use the extra space to clarify this part of the preliminaries in the camera-ready version. \n\n> Is there a typo in Eqn 3? Why is there a j exponent over z?\n\nYes, it is indeed a typo: j should have been s. Thanks!\n\n> It would be nice to have some explanation for how this polynomial in Eqn 3 is used to compute the kernels.\n\nSure, we will include some more explanation on this in the camera-ready version.\n\n> What about Nash Equilibria in two player settings? Can these results be applied the obtain stronger results there? \n\nYes, our results can be applied to learning Nash equilibria in the case of two-player zero-sum polyhedral games (e.g., two-player Colonel Blotto), due to equilibrium collapse. We will make sure to include a remark in the camera-ready version. \n\n> What prevents kernelized approaches from being applied to Correlated Equilibria computation? Are these limitations fundamental?\n\nIn learning CE, the situation gets much more challenging. Actually, it is a major open question in the field whether one can design FPTAS algorithms to find CE in polyhedral games. Only a PTAS algorithm is known due to the recent results of [2,3]. This is actually a learning approach and it depends on efficient MWU implementation in the game's action space. Thus, kernelization can be used in this framework and yield efficient (PTAS) algorithms for learning CE in polyhedral games.\n\n> Can you explain the semi-bandit feedback setting for your representation in Colonel Blotto? Why does semi-bandit feedback make sense in this setting?\n\nIn the semi-bandit setting of the Colonel Blotto game, in each battlefield, a player observes only the reward resulting from the number of soldiers they allocated to that battlefield. This setup is more realistic than the full-information setting, as in many practical scenarios players cannot access the payoffs of allocations they did not commit. For example, in real-world resource allocation tasks, feedback is typically limited to the outcomes of the specific allocations made, and obtaining counterfactual rewards for unrealized allocations is often infeasible.\n\n> In Beaglehole et al. 2023, they perform a piece-wise approximation of a partition function to achieve polylogarithmic dependence on the number of soldiers, can a similar trick be applied here?\n\nThat's a great question! The technique in [5] exploits a particular structural property of the utility function, that is increasing q-piece-wise constant. In contrast, we make no such assumptions, and our result applies to general (linear) utility functions. Actually, we did explore this direction as well, but the approach encountered several obstacles. A key challenge is that, to enable learning, we need an efficient representation of each player's action and reward vectors such that the reward remains linear in the action vector. Unfortunately, a $k \\log n$ representation does not seem to be able to achieve this linearity. We therefore view this as a very interesting direction for future work.\n\n---\n\nThank you again for your constructive input and encouraging words—please do not hesitate to reach out if you have any further questions!\n\nKind regards,\n\nThe authors \n\n---\n\n### References\n\n[1] Farina, Gabriele, et al. \"Kernelized multiplicative weights for 0/1-polyhedral games: Bridging the gap between learning in extensive-form and normal-form games.\" International Conference on Machine Learning. PMLR, 2022.\n\n[2] Dagan, Yuval, et al. \"From external to swap regret 2.0: An efficient reduction for large action spaces.\" Proceedings of the 56th Annual ACM Symposium on Theory of Computing. 2024.\n\n[3] Peng, Binghui, and Aviad Rubinstein. \"Fast swap regret minimization and applications to approximate correlated equilibria.\" Proceedings of the 56th Annual ACM Symposium on Theory of Computing. 2024.\n\n[4] Cesa-Bianchi, Nicolo, and Gábor Lugosi. \"Combinatorial bandits.\" Journal of Computer and System Sciences 78.5 (2012): 1404-1422.\n\n[5] Beaglehole, Daniel, et al. \"Sampling equilibria: Fast no-regret learning in structured games.\" Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, 2023."}]

Author rebuttal:

Meta-review: This paper develops efficient payoff-based learning algorithms for computing coarse correlated equilibria (CCE) in polyhedral games, which have exponentially large action spaces and combinatorial structure (including Colonel Blotto and congestion games). Building upon a recent development that enables to “kernelize” no-regret like dynamics, the authors are able to provide algorithms that provably converge to a CCE with running time that depends polynomially on the size of the succinct game.

The reviewers all agree that this submission makes progress on fundamental and well-studied challenges in (algorithmic) game theory and online learning. The contribution is technically interesting, and the submission is written very clearly. The only weakness mentioned by multiple reviewers are missing experimental results. The authors have, however, conducted experiments in the discussion phase and provided a summary of their findings. They promised to include this in the final version of the paper. The reviewers were all satisfied with this and consider also the experimental results as promising. Overall, the clear suggestion is to accept this submission.
Decision: Accept (poster)