Efficient Best-of-Both-Worlds Algorithms for Contextual Combinatorial Semi-Bandits
Authors: Mengmeng Li
Philipp J. Schneider
Jelisaveta Aleksic
Daniel Kuhn
Venue: ICLR 2026 Poster (2026)
Keywords: best-of-both-worlds
combinatorial semi-bandits
follow-the-regularized-leader
Primary area: other topics in machine learning (i.e., none of the above)

Abstract: We introduce the first best-of-both-worlds algorithm for contextual combinatorial semi-bandits that simultaneously guarantees $\widetilde{\mathcal{O}}(\sqrt{T})$ regret in the adversarial regime and $\widetilde{\mathcal{O}}(\ln T)$ regret in the corrupted stochastic regime. Our approach builds on the Follow-the-Regularized-Leader (FTRL) framework equipped with a Shannon entropy regularizer, yielding a flexible method that admits efficient implementations.
Beyond regret bounds, we tackle the practical bottleneck in FTRL (or, equivalently, Online Stochastic Mirror Descent) arising from the high-dimensional projection step encountered in each round of interaction. By leveraging the Karush-Kuhn-Tucker conditions, we transform the $K$-dimensional convex projection problem into a single-variable root-finding problem, dramatically accelerating each round. Empirical evaluations demonstrate that this combined strategy not only attains the attractive regret bounds of best-of-both-worlds algorithms but also delivers substantial per-round speed-ups, making it well-suited for large-scale, real-time applications.

Published as a conference paper at ICLR 2026
EFFICIENT BEST-OF-BOTH- WORLDS ALGORITHMS FOR CONTEXTUAL COMBINATORIAL
Mengmeng Li
Philipp J. Schneider
Risk Analytics and Optimization Chair
Risk Analytics and Optimization Chair
EPFL.
EPFL
Lausanne, Switzerland
Lausanne, Switzerland
mengmeng. aiieppl..c
philipp. schne ceraneider@epl.... ch
Jelisaveta Aleksic
Daniel Kuhn
Risk Analytics and Optimization Chair
Risk Analytics and Optimization Chair
EPFL.
EPFL
Lausanne, Switzerland
Lausanne, Switzerland
jelisaveta wle.ssieeeessssee...e. .c
daniel. kuhn@epf1.ch
ABSTRACT
We introduce the first bandits that simultaneously guarantees Ø(VT) regret in the adversarial regime and (In regret in the corrupted stochastic regime. Our approach builds on the heweettheRReullazzee--eeeee Shannon entropy regularizer, yielding flexible method that admits efficient imple- mentations. Beyond regret bounds, tackle the practical bottleneck in FTRL (or, equivalently, Online Stochastic Mirror Descent) arising from the high-dimensional projection step encountered in each round of interaction. By leveraging the Karush- Kuhn-Tucke conditions, we transform the K <-dimensional convex projection prob- lem into a dinglevarrabll root- moot-finding problem, dramatically accelerating each round. Empirical evaluations demonstrate that this combined strategy not only attains the attractive regret bounds of saa---ffoothhworlllee algorithms but also deliv- substantial per-round speed-ups, making it well-suited for scaee, real-time applications.
algorithm for contextual combinatorial
(FTRL) framework equipped with negative
INTRODUCTION
Online decision-making is often modeled via the multi-armed bandit framework: over T rounds, a learner selects an action and incurs a loss, observing only partial feedback. Many real-world tasks from selecting most movies streaming platform to curating list of m products on an e-commerce homepage-requin choosing subset of up to m items from K > m base arms in each round. This combinatorial bandil variant admits either semi-bandit feedback (per-arm losses) or full-bandit feedback (aggregate loss). Semi-bandit feedback is realistic web analytics record click-through outcomes for each displayed item and statistically advantageous: for m-set combinatorial bandits improves the minimax rate from [(myK7) under full-bandit feedback to Ō(VKKT) under aani-bandit feedback (Audibert et al. 2014). In each round, the learner faces either stochastic losses (e.g., from a fixed linear model on random contexts) or adversarial losses (modeling malicious perturbations). Contexts consist of user-feature vectors drawn i.i.d. from distribution, and instantancous losses are linear in these features. The best-of-both-woodd worlds (BOBW) paradigm unifies strategies across stochastic and adversarial loss regimes, achieving optimal regret guarantees both (Zimmert et al. 2019 Tsuchiya et al. 2023). However, gaps remain in current BOBW approaches for contextual combinatorial bandits highlighted by Tsuchiya et al. (202);; Kuroki et al. (2024) and exacerbated by evolving regulations and emerging technologies motssattiniinggggi revisit the problem.

---

Published as a conference paper at ICLR 2026
Challenges. While many companies possess extensive data, their operating environments rarely stationary and face multiple challenges:
Adversarial and Corrupted Stochastic Regimes. Advertising markets, for instance. evolve in real time as competitors react to each other (Balseiro et al., 2013 Jin et al. 2018), while recommendation systems must adapt shifting user preferences (Koren 2009) and defend against malicious actors (Mukherjee et al. 2013 Christakopoulou Banerjee 1019112hagg et al. 2020). A
natural remedy is best-of-both-worldd strviegy-provieed is computationally efficient. However, recent privacy regulations (e.g., the EU's GDPR (GDPR) 2016)) restrict context collection (for example, via third-party cookies), so the assumption of perfect knowledge of the context distribution no longer holds. This gap motivates BOBW algorithms that explicitly handle corrupted stochastic contexts treating unexpected losses as corruptions to secure optimal regret guarantees, which existing literature has yet to address.
Subroutine Computational Efficiency for Combinatorial Bandits. Advances in large language models (LLMs) allow platforms to generate vast pools of candidate ads at negligible cost, which can then be deployed for personalized advertising (Meguellati al. 2024). Yet most existing algorithms require solving a K-dimensional convex program in each round, making them increasingly expensive K grows. Moreover, on-the-fi fly customization of ad attributes (e.g., color, layout) via generative models further increases the runtime of these subroutines. Consequently, accelerating the per-round projection step is essential for practical, large-scale deployment.
Contributions. Our key contributions are summarized as follows.
Best-of-Both-Worte for Contextual Combinatorial Semi-Bandits. We propose algorithm for general contextual combinatorial semi-bandits that achieves both Ō TT) regret in the adver- sarial regime and (InT)) regret in the corrupted stochastic regime Our method instantiates Nealow-thh-Regulariieee
(FTRL) with Shannon-entropy regularizer, enabling efficient implementations in many practical settings (see Sec. 2
Accelerated Projection for FTRL/OSMD. For a popular class of combinatorial action sets, namely the m-set, we accelerate the projection subroutine any FTRL scheme with Legendre in Online Stochastic Mirror Descent (OSMD) for linear payoffs under the corresponding mirror map (Shale-Shwartz 2012). By exploiting the Karush-Kuhn- Kuhn- (KKT) conditions, we reduce the typical K K-dimensional convex projection to a one-dimensional root- finding problem (see See. Se. Results therein are generalizable a broader class of combinatorial action sets that admit separable structure, e.g., separable matroids.
As a result, our algorithm comparable to the per-iteration complexity of Follow-the- -erruurbbed Leader (FTPL) (Neul 2015 Neu & Bartók (206))which injects random noise to cumulative losses and selects the action with minimal perturbed total boss-while preserving the tight adversarial and stochastic regret guarantees characteristic of FTRL. Hence, we achieve both statistical and computational efficiency.
1.1 RELATED WORK
Our work builds on three streams of literature: (i) contextual combinatorial bandits, (ii) algorithms that exploit semi-bandit feedback, and (iii) adversarial linear bandits and best-of-both-weee worlds algorithms.
(i) Contextual Combinatorial Bandits. The contextual combinatorial bandit problem was introduced biiQin et al. 2014). who proposed the CCUCB algorithm for multi-item recommendations. This framework builds on earlier combinatorial semi-bandi models motivated by influence maximization in social networks Chen et al. (2013). Under the i.i.d. reward assumption, linear generalization across arms reduces the regret dependence on the action-set size K from VK to the context dimension d. Consequently, when d < K, the regret scales with VdT instead of VKT, offering substantial statistical advantage. Stochastic variants have explored Thompson sampling Wang & Chen (2018) and refined confidence sets TTakemura et al. (2021); however, none of these algorithms provide optimal regret guarantees against an adaptive adversary.
Here, (0-) suppresses poly-logarithmic factors.
2

---

Published as a conference paper at ICLR 2026
Table 1: Comparison of regret bounds across different settings.
Our Paper
Qin et al.
2014
Zieruhn et al.
2023
Ito et al.
2022
Kong et ul. 2023
Feedback
Semi-bandit
Full-bandit
Semi/Fullbundit
Gruph bandit
Linear bandit
Adv. Regret
mn
N/A
(o
(VaT
((VT)
Stoch. Regret
/ (0)olydd.,,K)(m777))
(dvmT
N/A
a(InT)
(InT)
Amiz
Agin
(ii) Semi-Bandit Feedback and Efficient Optimization. Combinatorial bandits were first formal- ized by Cesa-Bianchi & Lugosi 2012), who generalized EXP3 (Auer et al. (002)) from single arms to binary action vectors. Their algorithm, COMBAND, operates under full-bandir feedback the learner only observes an aggregated loss for the binary action vector they have chosen and achieves Ō( @(Vmkk77 VMKTTI(K/mm)
regret. Follow-up work connected this update to mirror descent on combinato- rial polytopes: COMPONENTHEDGE Koolen et al. (2010) COMBEXP Combes et al. (2015), and the DOMBexs OSMD analysis of offAudibert et al. (2014). AAuiiertt et al. (2014) provide concise taxonomy and prove matching lower bounds, showing that the VmKT rate is information-theortiiaalll optimal whenever semi-bandit feedback available. These results are also summarized in (Bubeck & Cesa-Bianchi 2012, Section 5.6. 1). To reduce per-round runtime, Neu & Bartók
( (2016) introduced a stochastic mirror-descent update that samples a single action and updates only the observed coordinates, thereby avoiding the full Bregman projection required by standard OSMD FTRL. The trade-off is an extra logarithmic factor in the regret bound. Variance-reduced estimators and high-probability analyses later refined these guarantees (Zimmert et al. 2019), yet computing the exact Bregman projection still requires time linear in the number of arms K.
(iii) Adversarial Linear Bandits and Best-of- Bitt--of-oth--orlds. Worlds. When losses can adapt to the learner's past, the i.i.d. assumption no longer holds. For single-arm actions (m = 1) the classical EXP4 algo- rithm attains ((VT) regret, but its running time and memory scale with the number of experts that is, the total number of deterministic policies mapping contexts arms- arms-which grows exponentially in the arm size K (Auer et al.] 2002). Neu & Olkhovskaya (2020) mitigated this explosion with REALLINEXP3, achieving (VVd') (VdKT) regret under the strong assumption that the context distribution is known. Liu et al. (2023) proposed an algorithm that achieves ((dm)²/TT) regret bound when applied to combinatorial semi-bandit case with only access to context sample per time period f, though the resulting oog-determinant FTRL remains intractable for the combinatorial bandits case because of exponentially many constraints Foster et al. (2020); Zimmert & Lattimore| (2022) and the nonlinearity introduced by their lifting covariance technique. The first near-optimal treatment the Geometrii--Rssmmlling Resampling (MGR) algorithm of Zierahn et al. Zierahn et al. (2023), which
achieves Ø (VmKT max (d, m Amin min (Σ))) regret but fails to provide bosst-of-bothwoor
regret guar- antees and relies on a sampling subroutine which requires (InT) samples in each round. Similar to the issue of generalizing (Liu et al. 2023), a straightforward extension of the rest-of-bothh botd-ooot-wordss (BOBW) algorithm from the linear contextual bandit setting, as studied by Kuroki et al. (2024), to the contextual combinatorial bandit framework yields action space whose cardinality grows exponentially with the size of the combinatorial decision variables. This exponential growth ren- ders the resulting optimization problem NP-hard and computationally infeasible for large-scale applications. More broadly, the BOBW achsiving (InT) under stochastic contexts and (VVT) under adversarial ones without prior
in the K-armed bandit setting (Bubeck Slivkins 2012, Seldin & Slivkins 2014) and has since been settled for linear bandits via data-dependent stability (Lee et al.]|2021] and streamlined FTRL scheme (Kong et al. 2023) and for contextual bandits via Exp4-style expert reductions (Pacchiano et al. 2022 Dann et al. 2023), at the cost of exponential enlicy-enumeration. In the purely combinatorial semi-bandit setting, hybrid-regularizer methods (Zimmert et al. 2019 Ito 2021) achieve the optimal BOBW rates but do not consider contextual information and the stemming difficulty of inverse-covariance matrix estimation. Consequently, no prior method simultaneously handles unknown covariance, large/infinite policy classes, and combinatorial action structure while maintaining BOBW regret bounds. We close this gap with a lhamnon-entropy FTRL algorithm that requires neither policy enumeration nor known Σ, yet still achieves optimal BOBW rates arbitrary combinatorial action sets.
3

---

Published as a conference paper at ICLR 2026
2
ALGORITHM FOR CONTEXTUAL COMBINATORIAL
SEMI-BANDITS
We begin our analysis of contextual combinatorial bandits by describing the interaction protocol that the learner follows and the problem settings that the best-of-both-wee base arms, m maximum number of base arms allowed to pull per round, an action set S' {0, 11. Σ (A)x m). and context space 2 Rd, the interaction protocol for the contextual combinatorial bandit problem proceeds as follows.
framework unifies. Given K
Interaction Protocol. In each round 1 = I,..., T the interaction protocol proceeds as follows. The environment first chooses the loss coefficients .j. . 0, E R and draws an i.idd context X, Φ. The learner observes X; and plays the vector A, E s/ The learner then observes the arm-wise losses (X) (X, 0, for every k such that (A,) 1 and suffers the total loss Σ (),, Consistent with the prior work on linear contextual bandits such as (Kuroki et al. 2024), we adopt the following assumption throughout this paper.
Assumption 1. The distribution D. from which contexts X are independently drawn, satisfies E[XX = Σ> 0: || 2 S D-almost surely; |0,,1l2 S 1 for all k E [K] and E [T]; (x, = (x. O. E [-1, for all E 2., K K), and E (T].
Under this assumption, we distinguish between the adversarial and stochastic regimes as follows. In the adversarial regime, the unknown loss coefficients {0,x)²_] may vary arbitrarily with respect to time but are independent of the learner's action sequence. In the stochastic regime, the loss function takes the form (X,,k) = (X,, 0₂) + EX,, k) for all k E [K], where 0₂ is also unknown but fixed throughout the T' interaction periods, and kk) is independent zero-mean noise. There is an additional intermediate regime that interpolates between the adversarial and stochastic regime, referred as corrupled stochastic regime (Zimmert & Seldin 2021 Kuroki et al. 2024). In this case, the loss function associated with each base arm k is defined by k) = (X,, 0,2/ + EX,,kk) where e(,,k) k) is independent zero-mean noise. On the other hand, the coefficients 0, are such that there exist fixed and unknown vectors . 0g and that satisfy Σ max ΣK 0 (xll((A) S for a fixed corruption level constant C > O. Note that C 0 corresponds to the stochastic regime and C= (T) corresponds to the adversarial regime with additional zero-mean noise. For any fixed context vector x 2., we define u²: : 2 st the optimal context- context-dependent action map that achieves minimum loss in hindsight, that is,
u" (x) = argmin E
Σ Σ ((x,))(A))
AE
The learner's performance is then measured by the pseudo-regret
Σ K
(x., (A))))((
2T
where the expectation is taken with respect the action-selection distribution chosen by the learner and the sequence of random contexts and loss coefficients chosen by the environment. As noted in the introduction, it is well-established in the literature that the optimal regret bounds are 0IIn T) in the stochastic regime and ((VT) ) in the adversarial regime. Algorithms that achieve both rates simultaneously and without prior knowledge of the environment's nature are referred to as "best-of- both-worlds" (Bubeck & Slivkins 2012, Seldin & Slivkins 2014).
In the stochastic regime, we define the suboptimality gap associated with an arbitrary action A E of and a fixed context E V through (x = Σx_ (x, (a)( (u' (x))x), and its minimum as Amin min (u'" (x). Additionally, we denote F, (XI,AI,.... AA,)) as the a- algebra generated by the history of contexts and actions up to and including time 1. For any positive semi-definite matrix M E dddd" we denote by (M) its smallest eigenvalue. With these definitions and notation in place, we now turn to our proposed method. Algorithm [ consists of an action- selection rule and loss-estimation procedure. The action-selection rule applies entropy cittooyy-rgularizedd FTRL to the convex hull of the action set, then samples an action from the original combinatorial action space, whose cardinality grows exponentially with m. Namely, denote the Shannon entropy
4

---

Published as a conference paper at ICLR 2026
Algorithm 1 FTRL for contextual combinatorial semi-bandits
Require: Context dimension d, subset size m 1 K, exploration set E S od learning rates (ne
{at [a))_11 {M, )/ initialization 6b. = 0 for all k [K]
1: for forr=1,, I,..,, do
2: Observe context X, E Rdd
3: Compute A, (X,) argmin (af) E E (X,, 0.x)a (1((a)
4:
Find a distribution pr(-[X;) over of such that (-xx = (x)x)
5:
Set π (a(x,) = (1 04 a. (app((a())) + 077 Iaa E|/|E| for all a al and sample A, ~ n (-1,)
6:
Observe loss (X,,k) k) for all & E K] such that (A,)2
7:
Subroutine Precision matrix estimation(T, M,)
8:
for n I..... M, do
9:
Draw X (n) ~ 2 and A(n) ~ TH (-)(
10:
Compute C. = IT (1- M₁
for all & [K]
11:
return Σt = (I+ n= C2 for all k E [
12:
End Subroutine
13:
Compute 0,1 I,, (X,, for all k [K]
H. conv od) + Rb (AA = - -AE (A), and specify the time-varying regularizer used in Step of Algorithm ! as ([(A)==H(AA)
The loss estimation is particularly relevant for the contextual case, as learning the optimal action hinges on computationally tractable approximation of the unknown parameter 0,2 governing the known that we can construct the unbiased estimator O. defined through 0; X,, &,,,X, (A,), for all k E [K]. However, computing this estimator is computationally inefficient as its construction requires computing the inverse of the d covariance matrix Σ, which of complexity (dd). Furthermore, this estimation approach assumes that the covariance matrix is known in advance, which is not the case in most real-world scenarios. To avoid such practical problems, we consider relying on the approach of the Matrix- Serrix-Geemmtric-Reseeeee Resampling method proposed by (Neu & Olkhovskaya (2020), as described by the subroutine within Algorithm| | This approach improves the computational efficiency by factor on the order of (d) compared to computing the naïve unbiased estimator and does not require full knowledge of the context distribution Φ, at the cost of introducing an additional bias the estimation of the precision matrix _ Note that we only require M, = [4K (n(r)/ (a& min (Σ)) = 0( In())) context samples at every time step. Additionally, an exploration set E C a is introduced to bound Amin x away from zero. The set E thus must satisfy that, for every E [K], there is at least one action A E such that (A)x 1. For simplicity, we select E. {A E (0, _ (A)x 1). in which case |E| = K. For every E [T]. we specify the remaining algorithmic parameters as = I/8, where B, max c2 I } and B = B + c + (mln(K/m))) E' (1(, (x2)) 1/2 We also let a = 4K In(r)/ (E). In addition, we set the problem-dependent constants C₁ = [d + In++1n7 Amii ( (mm ln(K/m) as well as C = 8K/ /mii (2). For initializations, we choose Bi - 21 These definitions ensure that S a 11 I 1/2 and n < 1/2 throughout i I....,
loss. Given the covariance matrix Σ,, = xx,, F.-1),
rounds.
We state our main results in Theorem and sketch the key elements of its proof in the next section. The regret upper bounds presented in Theorem 2. are optimal in the dependence on 7 up to logarithmic factors and, to the best of our knowledge, constitute the first known best-of-hoot--wolldd results for contextual combinatorial semi-bandits. Note that in the corrupted stochastic regime, the corruption budget enters only as an additive constant in the regret bound (see Appendix A. for details) and is therefore subsumed by the (-) notation.
Theorem 2.1 -oest-of-both-woor regret guarantee for contextual combinatorial bandits). The regret of Algorithm Z satisfies the following.
(i) In the adversarial regime, we have Ry 0 (m (ImKKI((/m)TTTT(((4= /2 (E)))
5

---

Published as a conference paper at ICLR 2026
(ii) In the stochastic regime and the corrupted stochastic regime, 6 In((K X mn]")dd (7min
have Rt
Amin
2.1 REGRET ANALYSIS
Establishing best-of-bothh botth-wohhddds guarantee with a computationally efficient algorithm poses several challenges. First, the approach of Zierahn et al. (Zierahn et al. (023), which uses fixed learning and sampling rates yields only (vVT) suboptimal regret bound in the stochastic regime-a result of its constant-learning-rate schedule and the coarse penalty bound in the FTRL analysis. Second, adopting the context- less fest-of-both-wor
analysis for combinatorial comi-bandits by Zimmert al. (Zimmert et al., 2019) relies on a hybrid regularizer to control arm-wise entropy; this, however, estimators cannot guarantee
demands arm- arm-wise bias control that state-of-the-ae art precision- under standard assumptions. To overcome these limitations, we exploit the time-varying learning rate to refine the regret analysis to be compatible with the stochastic regime, and we lift the mean-action space (support size K) to the space of action distributions (support size exponential in m). Together, these approaches enable self-bounding argument commonly used to achieve O 7) regret bound in the stochastic and corrupted stochastic regimes.
Analyzing regret in the contextual combinatorial semi-bandit setting presents an inherent challenge due to the evolving dependency between the sequence of observed contexts x Xy, and the learned parameters (6
(6r,)K= To address this, we follow strategy inspired by (Neu & Olkhovskaya 2020 Zierahn et al. 2023). in which we introduce an auxiliary game that simplities the regret analysis. We define an auxiliary regret notion by introducing ghost context sample Xy ~ 9, The regret in this drawn independently from the data used to construct the estimates (0,) auxiliary game then
T
K
Xo)
E
Σ
Σ
(Xo, 0.x) ((x (1) (Xo))=)
This fixed-context formulation decouples the randomness in the context sequence from the random- ness in parameter estimation, making the analysis more tractable. The following result relates the regret in the original contextual semi-bandit setting (as defined in the previous section) to the regret the auxiliary game.
Lemma 2.2 (Original game vs. auxiliary game (Neu & Olkhovskaya 2020 Equation (6))). For any Xo 2, the regret of Algorithm 7 satisfies
& (Xo) +2
K Σ
2T E
max AEAF
E
(X,, 0 ()))( F--1
I=1
This decomposition allows us to break down the regret into two components: the auxiliary regret, which captures the performance of the algorithm fixed-context game, and the excess bias-induced regrer, which reflects the cumulative effect of using θ, rather than the unbiased estimator ,, By analyzing these two terms separately, we can control the total regret under both stochastic and adversarial assumptions.
As an initial step in our regret analysis, we state the following lemma, which bounds the per-round excess regret introduced by the bias the precision-matrix estimation subroutine. This result enables us to bound the total bias-induced regret in Lemma 2.2 by ((IT) and to control the additional exploration regret the auxiliary game.
Lemma 2.3 (Bias control). For all t E [T], the estimates (θ.e1 constructed in Algorithm I satisfy of E. K (x. θ, (A)x F--1] < m//² for all x T.
We proceed to bound the regret for the auxiliary game, whose proof strategy follows by an FTRL analysis with a carefully-chosed learning-rate schedule, while taking context into account.
Lemma 2.4 (Regret decomposition for the auxiliary game). The regret of Algorithm 7 evaaluated in the auxiliary game satisfies
(I) (kdInT+ VmK (In 7)2
T
8KmIn(A K//KKmmmm)) In
E L T
(Xo)
$4/
E (XH())
Amin (E)
2min (Σ)

---

Published as a conference paper at ICLR 2026
where L 0 is universal constant.
Lemma 2.4 serves as the combinatorial bandits analogue of Lemma 3 in (Kuroki et al. 2024), which was established for linear contextual bandits. However, while (Kuroki al. (204) defines entropy over the space of action distributions, our setting defines entropy over the mean-action polytope. As result, directly generalizing their entropy bound settings with multiple establishing an optimal regret bound in the stochastic regime for contextual combinatorial bandits. To overcome these limitations, we derive a refined entropy bound by exploiting careful partitioning of the base arm set [K] and lifting the mean-action space (support size K) to the space of action distributions (support size exponential in m).. This refined bound enables the application of the self-bounding technique from (Zimmert & Seldin (02T) in the stochastic setting.
pulls is insufficient for
Lemma 2.5 (Refined entropy bound in the stochastic regime). Take a ghost sample Xo 9 and any action sequence Al generated under the policy sequence T1...., Nr using Algorithm Suppose that Ei=1 Ens(u' (x0))= (X0))==((A)) 2 e, where denotes Euler's 's number. The mean-action sequence
Å1, Ai,...,A ,r generated by Algorithm / then satisfies
T Σ
TH Σ 1EIAE
E
S {
Σ
(A|X,)
The proof for Theorem 2.1 then follows by combining the insights of all lemmas presented in this section. The complete proof and auxiliary results are deferred to Appendix A.
EFFICIENT NUMERICAL SCHEME FOR COMBINATORIAL
In the adversarial combinatorial semi-bandit setting, presented in Section 2 the learner must perform FTRL/OSMD updates over the convex hull of the combinatorial action space-an operation that naively entails K-dimensional Bregman projection. By exploiting the KKT conditions of this convex subproblem, we reduce each update to single one-dimensional root-finding call per round, yielding a more computationally efficient scheme. We first formalize the interaction protocol and then present the OSMD algorithm (Algorithm) 2 under the context-free regime. For simplicity, we study this section the m-set setting, where exactly m arms are pulled in each round. Note that in terms of computing Bregman projection, the context-free m-set setting is without loss of generality, since Step of Algorithm D is computed under fixed context and we may iterate through m number of j-subsets, where j= = 1,..., m. An efficient ((K) action-sampling procedure in the m-set setting is proposed in (Zimmert al. 2019. Appendix B.2).
Interaction Protocol. Fix the number of base arms K and m-set size m < K. Let of = E 1)x =m) Then, in each round = I..... T, the interaction protocol proceeds as follows. The environment chooses an adversarial loss vector &, = (f,, ,x...,,,xx)) [- 1| The learner then plays the vector A, E a, suffers the total loss (A,,e) = 1 (A())) and observes the coordinate losses 4, for every k such that (A:); 1.
Algorithm 2 Online stochastic mirror descent for semi-bandits (Lattimore & Szepesvári 2020 Algorithm 18)
Require: m-set size m < K, learning rate n, function F Initialize A₁ arg aicoon/eoovvee (())
2: for for/=1,.. 1,... T do
3: Choose distribution pt over a such that Ranp, [a] A,
4: Sample action A, ~ Pt. observe partial losses l,x for all & with (A,) =1
5: Compute the importance- empirtence-weighteed weighted loss estimator E. - (At) i (A,) for all k k [K]
6: Update the decision vector by solving A,41 = arg mi (1 (a, + Dr(a,A))
Algorithm proceeds in each round by: (i) sampling an action A, ~ Pr. (ii) computing the importance- weighted loss estimator lex, and (iii) updating the mean action via the Bregman projection. Here, Dr (a) ) is the Bregman divergence from Definition
7

---

Published as a conference paper at ICLR 2026
Definition 1 (Bregman divergence). Given convex differentiable function F conv( - R, the Bregman divergence DF conv(af) conv( - R, associated with F is defined as
Dy F F(a) F (A) ( (VF(A), A) Ya,A conv(
Assuming that the convex potential function F conv (of) - R is separable, that is, F can be expressed as (a) = f(=))(a) where f: IR - is convex, and dg. is the k-th coordinate of E ad Hence, the update step amounts to solving the convex subproblem
min (f)
DF DD
(1)
whose unique minimizer we denote by a".
We derive the KKT conditions as the following. Let us assign the following Lagrangian multipliers A R the constraint Σ a4 m, then μ E IR& to the of constraints dx 0, vk E [K]
and E R the set of inequality constraints d₃ 1, Ak [K]. Then the Lagrangian has the form L(a, M,,,, v) Σx Ix=1 f(()) ((A, (A.) 2 ΣK Meay + Σ (a(at 1). The resulting KKT conditions for equation are as follows.
ag - a; = m Yk E [K] Pk
(Primal feasibility)
0, vk E [K]
(Dual feasibility)
4: = 0, V (a: - 1) = 0, vk E [
(Complementary slackness)
+ 0, vk E [K]
(Stationarity)
We continue to reformulate the stationarity condition by distinguishing between cases for an arbitrary arm index & [K]. First, note that when dk > 0, complementary slackness implies that 0. Substituting into the stationarity condition yields f"(44) + + = 00, where we use the shorthand notation C = n - ((A:))) Inverting f' then gives (-1)-1(-2 ( -cx) = ag. Next, consider the case
when dg- = 0, the stationarity condition together with dual feasibility H4 2 0 gives f'(0) + à + Cg
He 2 0, which implies
cx) < O. Since the range of (f*)-1 is [0, 1J. we conclude that
(-2 - c2)
dj.
Thus, we have shown that solving the K K-dimensional convex optimization problem equation reduces to vne-dimensionll root-finding problem Σk= (f)- c2) = m.
Algorithm 3 Bisection algorithm for solving equation]
Require: Tolerance E, loss parameters c
1: Initialize 2 minke x] (-c - (mmm K)) and = max (Y (m(mkK)
2: for / = 1 to lo 22L/K() - 22) do
3: 2 == (2+ 22/2
4: if (f') (-A
- cx) then
5:
5+メ à
6:
else
7:
2+ A
8:
return a; = m/ =/
for all [K]
Similar to the result in (Li ct al. 2024 Theorem 6.1), which analyzes a perturbation- algorithm specialized for multi-armed bandits, bisection algorithm enjoys the following convergence guarantee.
Theorem 3.1 (Convergence Algorithm and that (f')-1 is L-Lipschitz continuous. Then, for any tolerance 0, Algorithm 3 outputs E conv( of) with Σ ag m and 1
3). Suppose that f is strictly convex and differentiable,
Even when (f')-1 1 is not available in closed form, may resort approximation oracle. Below we discuss how the convergence proof could be modified to accommodate the approximation enror.
8

---

Published as a conference paper at ICLR 2026
Corollary 3.2 (Convergence with approximate inverse oracle). Assume have oracle that, i E R. returns ý = (f ((f'''(((( (z) satisfying V (f" S t for some known tolerance t >> Then, under the same assumptions as in Theorem 3.1 and provided that t S (2y/K), the approximate algorithm yields vector ä E conv(c/) satisfying ||ā - a" S in (In(LVK 2))E)) bisection iterations.
Note that Algorithm 2 calls Algorithm with input <g - for all k É [K] in each iteration , T in order compute the mean-action vector A, Thus, the width of the search interval 2 2. is the order of (r) with high probability. This observation implies that the r-th call to Algorithm| Baaaammm@@euriii requires (In( v [n) iterations with high probability. In addition, each iteration in time (K). Hence, if 17 (1//T)), then the r-th call of Algorithm runs in time at most ((KIn( (KT)) (K) with high probability. Using the sampling scheme of complexity ((K) proposed by Zimmert al. (2019), the efficiency of Algorithm 3 as used by Algorithm 2 is thus comparable to the sampling procedure employed by FTPL (Neu & Bartók 2016).
We remark on the extension of our results in this section settings beyond m-set such as partition matroid (Oxley] 201T). Although we now have cardinality constraints per partition instead a single cardinality constraint, each partition is handled by its scalar root not-finding problem, and every arm enters exactly one partition. Hence, the work across all partitions sums to K, which the same the mairord case. Building the previous observation, the Bregman projection using our method still runs in time O(K (n(1/e)) the bisection method over partition runs time ((c,n((1))) with K Cj
3.1 NUMERICAL EXPERIMENTS
We now evaluate the per-iteration runtime of Algorithm 3 All experiments are conducted on a machine with 2.3 GHz 8-core Intel Core 19 processor and all optimization problems modeled in Python. In all experiments, we fix the m-set size to m 5, vary the number of base arms K E (10,.... 100), and run each algorithm for N 25 iterations entries are drawn uniformly at random. Mean per-iteration runtimes and their 95% confidence intervals are reported, and two instances of problem equation [ each employing different regularizer. are evaluated. The first instance uses Tsallis entropy with parameter & = 1/2, as in (Zimmert et al. 2019 Zimmert & Seldin 202T). which is known to achieve best-of both-worlds results. This corresponds to the regularizer f(x) -vx (labeled as "Tsallis"). The second instance employs the widely used negative Shannon entropy, induced by the regularizer f(x) xlnx (labeled as "Negative Shannon entropy").
loss vector y E [0, 1] whose
10"
10
Risection (Our)
Bisection (Ours)
Per-iteration runtime (5)
Newton
Per ieritteaatoon runtime (s)
Newton MOSEK
10
10
MOSEK
10
10
10
10
10
10
10
50
80
90
30
40
70
100
(K)
[f of
(K)
(a) Tsallis.
(b) Negative Shannon entropy.
Figure Per-iteration runtime for different regularizers.
We compute the mean-action projection of FTRL via Algorithm 3 and compare it against two
baselines: the heuristic Newton method used in Zimmert et al. 2019 and a direct implementation
TThe source code for this method is available
https: chub. com/d di ku-dk/
CombSemi Bandits

---

Published as a conference paper at ICLR 2026
of the optimization step using MOSEK In all cases, solve to enror tolerance of E 10 matching the suboptimality and feasibility tolerances used MOSEK. Figure] I visualizes the per- iteration runtimes of Algorithm [3 the Newton method, and MOSEK,
function of the number K of base arms. We observe that Algorithm B runs nearly 10 times faster than the Newton baseline for K = 100, and consistently outperforms MOSEK by factor of approximately across all values of K. This highlights the computational efficiency of our bisection-baas baaseddn-baeddd Algorithm 3
4 CONCLUDING REMARKS AND LIMITATIONS
We introduce the first algorithm for contextual combinatorial semi-bandin that simultaneously guarantees O (VVT) regret in the adversarial regime and (InT) ) in the corrupted stochastic regime. (FTRL) scheme with a Shannon-entropy regularizer
At its core is a Mello--tth-Rguulrizeel with vareing learning rate. Vanilla FTRL., however, requires solving K K-dimensional convex projection in each round, which limits scalability, whereas
(FTPL) is favored for its speed. We recover FTPL-style speed-ups by exploiting the KKT conditions reduce the projection to one-dimensional root-fine poot-finding problem. This hybrid design preserves FTRL's strong theoretical guarantees while matching FTPL's per-round efficiency. Despite these advances, our approach has two main limitations. First, the Shannon-enten
regularizer introduces an additional
(In 7') term in the adversarial regret. Second, the dependence on the combinatorial action size scales as ym, which is suboptimal relative to known lower bounds (Zierahn et al. 2023). Addressing the aforementioned limitations would be promising direction for further enhancing both the theory and practice of best-of-both- worlds bandit algorithms.
ACKNOWLEDGEMENTS
This work was supported as part of the NCCR Automation, a National Center of Competence in Research, funded by the Swiss National Science Foundation (grant number 51NF40 225155).
REFERENCES
MOSEK ApS. The MOSEK Python Fusion API manual. Version 11.0., 2025. URL https
//docs www.mos.kk..mmm www.mm..../..ateeeee..
html
Jean- Yves Audibert, Sébastien Bubeck, and Gáhor Lugosi. Regret in online combinatorial optimiza tion Mathematics of Operations Research, 39(1):31 2014.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem SIAM Journal on Computing, 32(1):48-77, 2002.
Santiago R Balseiro, Omar Besbes, and Gabriel Y Weintraub. Reepeated auctions with budgets in ad
exchanges: Approximations and design Management Science, 61(4):864-884 2015.
Sébastien Bubeck and Nicolo Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi
armed bandit problems Foundations and Trends@ in Machine Learning, 5(1):1-122, 2012.
Sébastien Bubeck and Aleksandrs Slivkins. The best of both worlds: Stochastic and adversarial bandits In Conference on Learning Theory, pp. 42.1 122.23,, 2012.
Nicolo Cesa-Bianchi and Gábor Lugosi. Combinatorial bandits Journal of Computer and System
Sciences, 78(5): 1424-142,, 2012.
Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armed bandit: General framework and applications In International Conference Machine Learning, pp. 151-159, PMLR, 2013.
Konstantina Christakopoulou and Arindam Banerjee. Adversarial attacks on an oblivious recom- mender In Proceedings of the 13th ACM Conference on Recommender Systems, pp. 322-330, 2019.
3 MOSEK accessed via the Python Fusion API ApS
2025
10

---

Published as a conference paper at ICLR 2026
Richard Combes, Mohammad Sadegh Talebi Mazrach Shahi, Alexandre Proutiere, al. Combinato rial bandits revisited Advances in Neural Information Processing Systems, 28, 2015.
Chris Dann, Chen- Yu Wei, and Julian Zimmert. A blackbox approach to best of both worlds in In Conference on Learning Theory, pp. 5503-5577 PMLR, 2023.
bandits and beyond
Dylan Foster, Claudio Gentile, Mehryar Mohri, and Julian Zimmert. Adapting to misspecification in contextual bandits Advances Neural Information Processing Systems, 33:11 11778 11489, 2020.
GDPR. Regulation (EU) 2016/679 of the European Parliament and of the Council of 27 April 2016 on the protection natural persons with regard to the processing of personal data and on the free movement of such data, and repealing Directive 95/46/EC (General Data Protection Regulation) (Text with HHA relevance) OJ, (I. 119):1888, 2016.
Shinji Ito. Hybrid regret bounds for combinatorial semi-bandits and adversarial linear bandits Advances in Neural Information Processing Systems, 1422554-667,, 2021.
Shinji Ito, Taira Tsuchiya, and Junya Honda. Nearly optimal best-of-both-worldd algorithms for online learning with feedback graphs. In Advances in Neu-
ral Information Processing Systems, volume 35. pp. 25834-25846, 2022. URL
www.fiieeppppaeeee Abstract oot.reeeeeectttttttooooeeeeeeeed
Junqi Jin, Chengru Song, Han Li, Kun Gai, Jun Wang, and Weinan Zhang. Real-time bidding
with multi-agent reinforcement learning in display advertising In Proceedings of the 27th ACM International Conference on Information and Knowledge Management, pp. 1193-2201, 2018.
Fang Kong, Canzhe Zhao, and Shuai Li. Best-offthree-wordds analysis for linear bandits with algorithm, In Conference on Learning Theory, pp. 657-673. PMLR,
2023.
Wouter M Koolen, Manfred K Warmuth, Jyrki Kivinen, et al. Hedging structured concepts In Conference on Learning Theory, pp. 93-105. Citeseer, 2010.
Yehuda Koren. Collaborative filtering with temporal dynamics, In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 447 4564 2009.
Yuko Kuroki, Alberto Rumi, Taira Tsuchiya, Fabio Vitale, and Nicolò BisachBa Best-of borh-worlds algorithms for linear contextual bandits In International Conference on Artificial Intelligence and Statistics, pp. 1216-1224. PMLR, 2024.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithmss
Cambridge University Press, 2020.
Chung-Was Wei Lee, Haipeng Luo, Chen- Yu Wei, Mengxiao Zhang, and Xiaojin Zhang. Achieving near instance-optimality and Minimax-ootimalln in stochastic and adversarial linear bandits Simultaneously In International Conference on Machine Learning, pp. 6142-6151. PMLR, 2021.
Mengmeng Li, Daniel Kuhn, and Bahar Taşkesen. Optimism in the face of ambiguity principle for multi-armed bandits arXiv preprint arXi::2409.204440 2024.
Haolin Liu, Chen-Ye Yu Wei, and Julian Zimmert. Bypassing the simulator: Near-optimal adversarial
linear contextual bandits Advances in Neural Information Processing Systems, 36:52086-52131, 2023.
Elyas Meguellati. Lei Han, Abraham Bernstein, Shazia Sadiq, and Gianluca Demartini. How good are LLMs in generating personalized advertisements? In Companion Proceedings of the ACM Web Conference 2024, pp. 826 0266829911 2024.
Arjun Mukherjee, Abhinav Kumar, Bing Liu, Junhui Wang, Meichun Hsu, Malu Castellanos, and Riddhiman Ghosh. (Spotting opinion spammers using behavioral footprints) In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 632-640, 2013.
11

---

Published as a conference paper at ICLR 2026
Gergely Neu. First-order regret bounds for combinatorial semi-bandits In Conference on Learning Theory, pp. 3360-1375 PMLR, 2013.
Gergely Neu and Gábor Bartók. Importance weighting without importance weights: An efficient
algorithm for combinatorial semi-bandits) Journal of Machine Learning Research, 17(154):1-21, 2016.
Gergely Neu and Julia Olkhovskaya. Efficient and robust algorithms for adversarial linear contextual bandits In Conference on Learning Theory, pp. 3049-30--000 3068. PMLR, 2020.
James G Oxley. Matroid Theory Oxford University Press, 2 edition, 2011.
Aldo Pacchiano, Christoph Dann, and Claudio Gentile. Best of both worlds model selection, Advances in Neural Information Processing Systems, 35:1883-188 1895, 2022.
Lijing Qin, Shouyuan Chen, and Xiaoyan Zhu. Contextual combinatorial bandit and its application on diversified online recommennationn In Proceedings of the 2014 SIAM International Conference on Data Mining, pp. 461-469. SIAM, 2014.
Yevgeny Seldin and Aleksandrs Slivkins. One practical algorithm for both stochastic and adversarial bandits In International Conference on Machine Learning, pp. 1287-1295, PMLR, 2014.
Shai Shalev-Shwarz. Online learning and online convex optimization. Foundations and Trends@ in
Machine Learning, 4(2):107-194, 2012.
Kei Takemura, Shinji Ito, Daisuke Hatano, Hanna Sumita, Takuro Fukunaga, Naonori Kakimura, and Ken-ichi Kawarabayashi. Near-optimal regret bounds for contextual combinatorial semi-bandits with linear payoff functions In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 9791-9798, 2021. 2021.
Taira Tsuchiya, Shinji Ito, and Junya Honda. Further adaptive best-of-both-worldd algorithm for combinatorial bandits In International Conference on Artificial Intelligence and Statisties, pp. 8117-8144. PMLR, 2023.
Siwei Wang and Wei Chen. Thompson sampling for combinatorial semi-bandits In International Conference Machine Learning, pp. 5122-5122. PMLR, 2018
Hengtong Zhang, Yaliang Li, Bolin Ding, and Jing Gao. Practical data poisoning attack against next-item recommendation, In Proceedings of the Web Conference 2020, pp. 2458 0488-244, 2020.
Lukas Zierahn, Dirk van der Hoeven, Nicolo Cesa-Bianchi and Gergely Neu. Nonstochastic contextual combinatorial bandits In International Conference on Artificial Intelligence and Statistics, pp. 8771-8813 PMLR, 2023.
Julian Zimmert and Tor Lattimore. Return of the bias: Almost minimax optimal high probability bounds for adversarial linear bandits. In Conference on Learning Theory, pp. 3285-3312. PMLR, 2022.
Julian Zimmert and Yevgeny Seldin. INF An optimal algoorith for stochastic and adversarial bandits Journal of Machine Learning Research, 22(28):1149) 2021.
Julian Zimmert, Haipeng Luo, and Chen-Yu Wei. Beating stochastic and adversarial banddt optimally and simultaneously In International Conference on Machine Learning, pp. 7683-7692. PMLR, 2019.
A APPENDIX
A.1 PROOFS AND AUXILIARY RESULTS FOR SECTION 2
For ease of notation the proofs, we set // = a, 17, throughout this section. We start by addressing the terms relevant to the regret induced the auxiliary game for a fixed context (x). Denote as well the time-varying Bregman divergence from p E conv( g E conv(a/) through
D,(g.P) P) = vi(g) (p) - (V (p).q p)-
We start by the following lemma by following standard FTRL analysis with varying potentials.
12

---

Published as a conference paper at ICLR 2026
Lemma A.1 (Stability-penaall decomposition). For any context x E and S for all r [T],
have
E
fx, (.))((A)) (4' (x))x)
=Ik1
(v (x)) Voti (Ar+1 + vr++(4 W
Penalty
T
%)
(x 0.2 ((Ar(x)) (s)
U(x)
-1
Exploration inducedd regret
Stability
(2)
where Uxx)=
-Tm 7/ E (z, (1/ (x))))
Proof of Lemma
A.I.
It follows from the construction of (x) that
K
E,,
Σ
Σ
(s. ((Ar)(
(x)
T Σ Σ (1- -ik=
T K
(u" (x)) 0rx)
ΣΣ
(u" (x))2 (x. Q.))
[
Applying standard FTRL regret decomposition result (see e.g. (Lattimore & Szepesvári 2020
Exercise 28. 12)) to the first term on the right-ham side of the above expression and applying the definition of U (x) yields the desired result.
The following lemma is building block for bounding the stability term appearing Lemma A.1
Lemma A.2 (Bound for the scaled per-arm loss). Under the assumptions of Lemmal A.7 we have
max kE[K]
In, (x, 0,,a)
Proof of Lemma A.2
Observe that
max AE[K]
m (x, 0,2) = max
(r. 7
E XXX
RE(K]
n X
max kE(K]
(M, + 1) 24 Amnaa (2)
Th
4K Infe)
+1)
< 17 max
EEpelop kE[K]
5 1,
where the second inequality exploits Hölder's inequality, which applies because |X+||2 S 1 by assumption, the third inequality holds thanks to (Zierahn et al. 20023] Lemma 1), the fourth inequality holds due to the parameter choice a, The last inequality again follows by the parameter choices 0 = 4K (n() /0mimmn (Z) and n, < 1/2.
We now decompose the regret for the auxiliary game stated in Lemma A. as follows.
Lemma A.3 (Regret breakdown for the auxiliary game). Under the assumptions of Lemma A.J
have
T (x) - Ux) Σ (1 m)e Σ (x, (A)()))
Σ (B (A+4(()) + mc2 In In
13

---

Published as a conference paper at ICLR 2026
Proof of Lemma A.3 We analyze the stability and penalty terms appearing in Lemma A.1 First,
bound the per-round stability term in equation 2 By (Lattimore & Szepesvári 2020 Theorem 26.13)
and using that
2²
(x(()
से for all x E conv( we have
(ax)
Σ (x xx) - A:
Σ (x, 2) (2))ss
(3)
2
where 2, lies the line segment connecting (x) and q" argmax Σ (x. θ (AA, qR) - (x)).
addition, by the first-order optimality conditions we have qi exp) - 7r (x, 0.))). Combining the previous observation with Lemma A.2 which states that -n (x, 0..) 1, for all & E [K]. we deduce that o E (e,(s))))eee((((( Because lies on the line segment connecting A, and q", we then have (z)), S e(A, for all & E [K]. which in turn implies that
x (2) (x. (A,))))
Substituting equation 4 into equation establishes the upper bound for the stability term as claimed. As for the penalty term, we have
(Art) (x)) - -hh + vr+1(1 - un (AI(x))
BB -n(k)) In(K/m) <
where the first inequality holds because of Jensen's ' inequality and noting that H takes nonnegative values on conv( and the second inequality holds because of the choice B1 c2
Thus, the claim follows.
We continue to bound the extra regret for the auxiliary game due to exploration, which uses Lemma 2.3 as building block. For the sake of completeness we first state the proof of Lemma 2.3
Proof of Lemma imply that
2.3
Zierahn et al. 2023 Lemma 3) and our choice of E that satisfies [ = K
K
Y: (E)M,
max AE
Σ
xx, - ())) F. S <mmxpp
Vx L.
2K
The claim then follows by the choice of M, used in Algorithm
We are now equipped with the technical tools necessary to bound the exploration induced regret, as stated below.
Lemma A.4 (Extra regret due to exploration). We have S <
Proof of Lemma
A.4
Observe that
K
Xoo d. (a)) ((((A)(1111)) [
EXU(
< E
Y max Nedf
T
Xo. θ (A) + k(xo. 1
E
Σ
Y max E Ae
T
T Y
E
Y/ max E AE
Xoo 0, (A)) +1 S. <(m 1)
where the second inequality follows by the unbiasedness of θ, the third inequality holds by the assumption that (x,k) < for all x E 2 and E [K], and the last inequality holds because of
Lemma 2.3
14

---

Published as a conference paper at ICLR 2026
The following is another preparation lemma for establishing Lemma 2.4
which constitutes adaptation of (Kuroki et al. [2024] Lemma 18) to the combinatorial aami-bandit setting. provides a refined bound on the penalty term induced by the Shannon entropy regularizer with respect to the ghost sample.
Lemma A.5 (Entropic bound for the ghost sample). We have
I
- (B) = ( ((H((X
E
Σ 1
Proof of Lemma
A.5 By definition of B/, we obtain
T
T
E
Σ (p/+1 B)) H (A.++
=E
Σ
H H(A++1(60)
V (m K k/m))
E H(A,(x.))
(XAr)1(Xo))
2c1 V m (onkln/mm))
Σ
(x.) + V (X.)
where in the last step we used the fact that H (A,((X)) S m ( (4/m)) /m). The above upper bound further reduces
(Xo)+1(X0))
201 m mln( (mln(K/nng K/
++ (X)) + H
H(Ar+
H())(X))) Ex= H(ar(X,)))
= =2c1 mln(K/m))
Σ
H(A++1(X0))
V
ス =(((()))
= =2c mwlnk//j]]
(A,((x)))
= =2c1 FonymlnnK/mmeB
Σ H(A,(,)))
(xI)
< <cc (oiV/llnK//mBBB
Σ (())(x)))
mcy/mln(k/m
Σ B(H(A,(x.))),
where the first equality holds because Ex Ex ( (X)+))) = Exo~9 H (Ar+ +1 (Xo) F.).
The first inequality exploits the fact that (X.)).)) S (A1 (X1)) mIn(K/ k/m,, and the second inequality follows from Jensen's inequality. Thus, the claim follows.
The following lemma provides an upper bound on the refined per-round stability term established in K for all I....,T.
Lemma A.3 in the form of variance of the parameter estimates {0,x)
Lemma A.6 (Variance control (Zierahn et al. 2023 Lemma 5)). For any context x E L, conditioning on the history F,-1 yields the variance bound
(1 - E)
Σ (x. (A())) 8,-1 <
3Kd.
We are now equipped with all the technicalities needed to establish the regret bound for the original game.
Proof of Lemma 2.4 We begin by establishing an upper bound on the sum of learning rates, Σ nh which will be useful throughout the proof. Observe first that by construction of B/, have
B c1
C1
+ (mln
|x=1 (AA((X)))
(ml(kk/mm) E. H(A,(X.))
15

---

Published as a conference paper at ICLR 2026
where the inequality holds because (X,)(X.)) for all u e [r]. Thus,
I+ (mln(//m)) E. ((),(X))
Σ
n
P
c11
1=1
+ In
1+ (m(((((//m))
Σ (())
(5)
In
E (((((()))
0
C1 Div/in(///)
where we used (AI = mln(K/m), It then follows that
E
Σ (1
ee Σ xx. (A)
n
= E
Σ nee
(1 - 16)
E (x. (A) 1
InT
Σ (((
S
6
IE
(6)
mln(k/mm (K/m)
Kd-In7
T Σ H(
0
E
cr/mln((/mm
where the equality holds due to the law of iterated expectations, the first inequality holds thanks to Lemma and equation 5 and the second inequality follows from Jensen's 's inequality.
We continue to bound the extra regret due to exploration by the cumulative entropy term. It follows from Lemma A.4 that
Σ 4n, K In
[X)( ( (vm IJE
Σ %
I (vm + I)E
Amin (2)
( K(InT)2
Σ ((((()))))))
c: (E) /In(/m)
where the second incquality holds because y/ = 04 and the choice of a as well as the fact that Inr < InT. The equality then holds because of equation 5
Finally, we establish an upper bound for the penalty term the regret decomposition. Denote by the first round in which B becomes larger than the constant F = max c2 i.e., to min fr E [T] B f). We then have
T
E
Σ
(B. 1 (.)
T (B..1 (B))1
E
Σ (B++1 (A,
+
1=
(8)
E
(B%,
+
Σ
(Bi+ (A)
Σ (B/ (A) (Xo))
= ci cci/mlnnK/m m)
Σ 18 H (A, (X,)))
by construc- tion, and B = B, for r 2 to. The second inequality holds because B/ is increasing in f. while the second equality holds thanks to Lemma A.5] The claim then follows by substituting equation 6 equation 7 and equation X into terms the statement of Lemma (t bound the regret for the auxiliary game) well Lemma 2.2 (to bound the regret for the original game).
where the first inequality due to the fact that B, = B++1 while E [to - 2] P 8/
16

---

Published as a conference paper at ICLR 2026
The crux to show the best-of-both-wordde result now lies in constructing tight upper bound on the cumulative entropy term that dominates the regret bound Lemma 2.4
Proof of Lemma 2.5
Observe that for any conv (of) and any S C [K] with [S] S m, it follows that
H(A)
Σ (A)x
Σ
(A)x
1
(A)x
(A)x
RES
K K-1S) |S|
1
-1)
Σ (A)x In
E(A)
Exps(A)s
(A)x
AgS
KES
K --16 - In
(A)x KEES
Ekgs(A) +1)
where the inequality holds because of Jensen's inequality and because In(1/x) S 1/x- and the second equality holds because [AEs(A)x (Ags(A)x thanks to the membership of A in conv(s/). Applying the above incquality to the entropy with respect to action given the ghost sample Xo and S = E [K] (M" (Xo))x 1} gives
K K- |S]
Σ (A)) S
Σ
Σ
(Acle
In "Eucr10)))=-0A.. +1)
k:(w
(Xa))=0)
e(K-151)7
< Σ
Σ
(A
(9)
Σ (xll
k=(w (Xo))e
< <In((K - (SI)T)
Σ
E (A:)a:
I=
where the second inequality follows by Jensen's inequality, and the third inequality holds because
Σ
Σ
(Ar) Ze.
ks(we
(Xo))==0
We continue to bound the term Σ Ex:(ar (X))) -00)
(Ar)e. Taking expectations yields
Σ Σ (A,)a = Σ Σ
Σ
x. (A())(AA)
A:((" (X=))440
(x((e((X) (0) =0AER
=
Σ Σ
E
(A))))(A)
(x)))
(Xo)
S
(A())).
(Xo))
Substituting the above expression into equation noticing that (1 (Xo))
(x))),)))), and that [S] < m thus establishes the claim.
Finally, Theorem 2.1 can be established via combining all of the insights yielded in the above lemmas.
Proof of Theorem 2.7 For ease of notation, let us denote k / Kndln'' + K (In / (E). The regret bound stated ii) follows immediately from Lemma 2.2 combined with Lemmal a. well as the observation that Y (Ax(()))) < mIn (K/ /m).. We now show claim (ii) Note that in the case of ET_ Eeeaa (Xa)) (A,)) (A,) < e, we have Σ (Ar(())) S eIn(e(K - m)T) 1/e, in which case we already have the desired bound. We thus continue to consider the case when Σ = 2 Observe that due to the definition of suboptimality gap Ax(x) and the corruption budget C,
17

---

Published as a conference paper at ICLR 2026
follows that
T
20T 2 E
Σ
Σ
2T
Σ Aead
max
0all((A)²
AE (X))
(10)
I
min E
Σ
Σ
(A(x))
2C.
-=
(X)))
For any 2 E [0, 11. may decompose the regret as
8 = (1+1) 2BT
T
$ (1+ 1)K
E
Σ (X)(
2.
TE
Σ
E
(1)x)
+22C
+
mln(K (inn(/m))nn) mm)
Amnin (2)
- (-m)) m)
mE
Σ
Σ (A(x)
LoE AeEor (Xi))
A. E
Σ E
(A|x))
+
K
m mln( (ll(m/m) InT
7mmin
AE (x)()))
50 (1 22 (K-(K)
(mml(((-m)77)
42in
Amin
where the first inequality holds thanks to Lemma 2.2 combined with Lemma 2.4 as well as the lower
bound equation [0] the second inequality follows by Lemma 2.5 The third inequality holds by the
observation a /xxx- bx S a² /(4b) for any nonnegative scalars a, b,x, and the last equality follows by
choosing À 1.
A.2 PROOFS AND AUXILIARY RESULTS FOR SECTION 3
Example 1 (Choices of f). We provide three examples of the arm-wise regularizer f on domain [0.1 or (0,1) 1] that admits a closed-form expression of (f')-1 and satisfies the assumptions of Theorem 3.1
1. f(x) [0, R is defined through f(x) xlnx x for x E (0, and f(0) = O, which is continuous on [0,1] and differentiable on (0, 1]. Note that although Inx is not defined at O, we have tim-0-xxnnx
Observe that its first derivative for (0, is Inx. then follows that (f') -x) = for all k E [K] In addition, note that z f')) = Inx ranges over the interval Z (=oo.), On that interval, the derivative of the inverse de /dz e satisfies e e e for all Z (-c0, 0). By the mean- theorem, for any Z1, [- there exists between them such that (ea1 = = e 21 - 22 S 1|21 z2)-
Hence, the function (f')) -xx) = 2 h- is 1-Lipschitz.
2. f(x)= on [0. 1). It then follows that (f") (f')-1(z) (2) 2/2 2/2 all E [0,2]. As in the previous Cb. for all k E [K] we have ( (-2 c2) = (-A-cx)/22 cx)/2. Note also
case, with == that the function ( (-2 -x) = (-2 c2)/2 is globally (1/2)-Lipschitz on its entire domain.
3. - (0,
Similar previous calculations, we have (z) = 1/(422)) Note that it must hold
z <<00 O for the expression to be defined properly. Hence with 2 -7 < 0, for all k E K). we have (f')- -x) = 11/4(-( -) As x (0, we have = 1-0--1ffi 1/(22/x) E
(0o0,- - 1/2]. On that interval, the derivative of the inverse is:
0
1
dz
42
2
18

---

Published as a conference paper at ICLR 2026
On the interval Z (-) the largest magnitude of the inverse of the derivative map (z)) occurs the smallest |z), namely at |z| 1/2. This follows from the fact that (())) is decreasing |2| grows. Then, sup ( (z) = 4, on Z (-00-11 1/2
So. (z))))(())) (22) I 4/21 -2)), all 21.22 -1/) Therefore, (f*)-1 is
4-Lipschitz.
Proof of Theorem 3.7 negative and strictly positive function values, respectively. The definition of À in of Algorithm implies that
We first show that the endpoints of the search interval give rise to strictly
-f(mm/) ((mKK)= S - - e [K].
(11)
As f is strictly convex, its first derivative 1" is strictly increasing, which in turn implies that its inverse (f")-1 1 is also strictly increasing. Applying the inverse function both sides of equation 11 yields
(-2 (-2-c))
K E [K].
Summing over k == 1....., .. K gives Σ Ex) - c+) 2 m. similar argument applied to ă
gives Σx -k=1 (f)) - ct) S m. Thus, by the intermediate value theorem, there exists at least one 2 E [. such that
2-"-
Next, we show that the prescribed iteration number gives an approximate solution of 2 upon termination. By the assumed L-Lipschitz continuity of (ft)-1, we have
(x)) S -|x-y| Vr,eRR.
(12)
Define the modulus of uniform continuity 8(e) by // Vx,y E with |x- 8).
((E) max ( 8>0
Choosing &n (/(2Lv gives (x) L8 L8 =/(2VK)) which implies that
8(E) 2 (/(2LV/). Let the initial interval length be Ao = 2 2, where ă, A are initializations specified in [t Algorithm 3 Note that each bisection iteration halves the interval's length. Therefore, the interval length after iterations is A An/2'. Denote by À the midpoint of the 1-th interval. Since the true root 2 lies within this interval, the error satisfies
A A 2
A 2
2
To guarantee that the propagated through the L-Lipschitz function (f")-1 remains below e/(2VK) in each coordinate, it suffices have L|4; A I (/(2K), or equivalently, An/2/+1 e/(2LVK), K). J. follows that the bisection algorithm should terminate soon as
2LV KAo
12 logz
1.
Let denote with L the number of iterations after bisection algorithm terminates. Then,
PA - 2 2LV
and thus 1," < (2gg(22 The output of Algorithm is defined
A
(-A K'
VK [K].
(13)
where A (f)
2²). For each coordinate the eттor induced by the difference
between 2 and 2 is dominated by the Lipschitz property equation 12 through
- -x) s - 2
19

---

Published as a conference paper at ICLR 2026
which in turn implies that (f*))~(-a - (f)) (-2- -cx) (/(2K) Summing over k
cx)
I,..., K and by defining A₂ = m [-=1(") (112-10) -cx) yields:
K E(r) - cc) EVK
A m-
2
By the definition of A we can bound A as A S S w K/2. In the worst-case scenario when the computed error A₂ is close to O, the inequality above reduces to A z 4 EVK/2. Since 4 is nearly 0 or in the worst-case non-positive, this yields the bound - - K/2. Therefore, from equation 13 the error in each coordinate satisfies |ax axl S Se/VK, and therefore || - I|2 S Thus, the claim follows.
Proof of Corollary 3.2 Define the exact residual s(2) = m (0)- (2) and the approxi-
< r. To measure the oracle's perturbation, set E(2) = (22) x22) = Σ [ - (-A- Since this is sum of K individual errors, the triangle inequality gives (E(2) S Ex 82 (--(()-(-- (-2 -c+) < Kt.
mate residual ((2) = m m 1 where each f& satisfies 1i2 - (-)
In the exact inverse case assume g22) 2 0 and g²)) I 0, which guarantees root 2 E A..
Accounting for the oracle error then yields (22) 2 -KK Kr and g²)) < Kr.
Provided that ( -{)) Kt, the sign test ğ still selects the correct subinterval: hence the bisection converges with each evaluation of g perturbed by at most =Kt. After / iterations, the midpoint 2 satisfies 1 - 2-1 < A0/2 with An
2. Upon termination at 2,, define ā= (2,) for all & E [K]. Finally, subtract the mean of ā to ensure that Σ ā exactly.
Subtracting the mean of introduces uniform shift of magnitude C= = 0(T + L 1) ) Hence each coordinate error can be bounded as
a a5l S 10") 100) - (1) cx) + 5 - 2 cc) cx) + +
<1124-2-1
Since (f')-1 -1 is L-Lipschitz and each oracle error is bounded by r, it follows that [āx - dzl S L|24- +1 C. Taking the f2-norm of the coordinatewise bound gives
|| l a-2al22 S VK max àg - ail S V K -
Hence, to ensure ||ä - a²112 S e, it suffices that
and J E
L -
2 K
2 K
The first inequality follows from
Ao
< E
1 2
21+1
KV
which is equivalent to
2 2vKLA0
2 log,
E
while the second is simply S k/(2/K). Together, these conditions imply the claimed iteration bound o (In(LVK(2 - A)/=)). This observation completes the proof.
B ADDITIONAL NUMERICAL EXPERIMENTS
In Sec. 3.1 we reported the per-iteration runtime of Algorithm 3 and our implementation, we plot cumulative-regre trajectories for OSMD (Algorithm 2), comparing (a) our Bisection-based projection with (b) direct solution of the projection step via MOSEK 3
To further validate hoth the approach
4 'lll code reproduce the figures is available at ht httpss://ggge cot. www.oo//ROOOPPP.....
20

---

Published as a conference paper at ICLR 2026
Mean cumulative regrets for the stochastic and adversarial settings shown in Figs. 2 and 5 respectively, under the Tsallis and negative Shannon entropy regularizers. We consider m 3, 5, (20,40) base arms, and horizon of 10* rounds.
-etanonnentroppy
Across all configurations, the two implementations yield indistinguishable regret curves (up to numerical tolerance), supporting the correctness our implementation. For completeness, Tables] and report final cumulative regret for all projection subroutines considered in the paper (Bisection, Newton, MOSEK) under the Tsallis and negative Shamnon-entrop regularizers, respectively.
1750
1750
(m--3 R X02
[m=1, X-20)
Cumulative rogret (R.)
1500
-0-
(mr=, X=20)
Cumulative regret (R.)
1500
-0-
[wr=5, K=20)
1250
2- (m==3 K=40)
...................... B............ B............
[mr=3, K=
(m--5 K-40)
[nz-5, K-40)
1000-
1000
710
750-
-0
250
250
0.2
0-1
2000
4000
8000
Rounds (f)
Rounds (f)
(a) Bisection (Ours).
(b) MOSEK.
Figure 2: Stochastic setting for A 0.0625 (Tsallis regularizer).
1750
1750
(m-33 K020)
[m=-3 K-20)
Cumulative regret (R.)
-0-
(m=5, K=20)
Cumulative regret (R.)
-0-
[m==5 K=20)
1250
(m-3, K K-40)
1250
[m==3 K K-40)
(m=5, K=40)
[m==5 K=40)
1000
1000
250
250-
2000
4000
(100
8000
10000
Rounds (f)
Rounds (f)
(a) Bisection (Ours).
(b) MOSEK.
Figure 3: Stochastic setting for A 0.0625 (Negative Shannon entropy regularizer).
1750
1750
(m==3 K=20)
[m==3 K=
Cumulative regret (R.)
1500)
K=20)
Cumulative regret (RR))
[m=5, K=20)
1250
(m=3, K=40)
1250
[wim3 K=40)
(m=5, K=40)
[m=55 K=400
1000
1000
500
300
250
250
2000
8000
8000
1000
2000
4000
6000
8000
10000
Rounds (4)
Rounds (4)
(a) Bisection (Ours).
(b) MOSEK.
Figure 4: Adversarial setting for A = 0.0625 (Tsallis regularizer).
21

---

Published as a conference paper at ICLR 2026
1710
1750
-0- (m-=3, K-20)
........ D......... ......... ................ "...............................
[m=1, K-20)
Cumulative regret (R,)
1500
-Q- (mm=5, K=20)
Cumulative regret (R.)
1500
-O-
[wr=5, K=20)
1250
2-
(mn-3, K04
[m=-3 K-40)
(m=5, K=
[m==5 K=
1000
1000
710
750-
250
250
8000
Rounds (t)
Rounds (f)
(a) Bisection (Ours).
(b) MOSEK.
Figure Adversarial setting for 0.0625 (Negative Shannon entropy regularizer).
Table 2: Cumulative regret
10 for A 0.0625 (Tsallis regularizer).
Method
Stochastic (μ + σ)
Adversarial (μ σ))
Bisection (Ours)
711.3 146.3
694.6 + 161.2
3
Newton
726.2 + 170.1
710.8 + 130.4
MOSEK
734.5 + 143.0
686.6 + 88.1
20
Bisection (Ours)
775.7 + 170.2
736.5 + 119.7
5 Newton
761.2 164.3
734.7 + 121.3
MOSEK
758.8 170.1
721.5 137.4
Bisection (Ours)
1059.4 190.2
1099.7 + 143.4
3
Newton
1114.8 181.4
1117.4 + 171.5
MOSEK
1095.2 + 176.1
1101.4 1 119.7
40
Bisection (Ours)
1303.2 167.3
1312.6 + 199.0
5 Newton
1314.9 + 210.2
1309.8 = 187.6
MOSEK
1338.0 + 197.4
1285.6 + 164.9
Table 3: Cumulative regret at 7 10 for = 0.0625 (Negative Shannon entropy regularizer).
K
Method
Stochastic (u + o)
Adversarial (μ ())
Bisection (Ours)
845.1
160.9
871.5 = 107.2
Newton
835.6
136.9
874.0 102.8
MOSEK
847.4 115.7
887.6 131.4
20
Bisection (Ours)
910.2 164.4
914.8 126.2
5 Newton
914.4 + 152.4
900.5 + 128.8
MOSEK
925.1 + 160.6
893.7 + 129.9
Bisection (Ours)
1300.8 + 149.4
1339.2 + 115.3
3
Newton
1281.1 + 118.8
1342.8 + 101.9
MOSEK
1340.1 144.5
1325.0 + 123.5
40
Bisection (Ours)
1636.6 + 193.4
1648.3 + 156.4
5 Newton
1568.7 168.5
1629.0 = 141.8
MOSEK
1612.7 + 168.0
1642.0 + 170.9
22


Reviews:
[{"review_id": "LiJ5dgia4o", "reviewer": "Reviewer_SW5m", "summary": "The paper proposes an FTRL-based algorithm for contextual combinatorial semi-bandits. It achieves best-of-both-worlds (BOBW) regret: $O(\\sqrt{T})$in adversarial settings and $O(\\log T)$ in corrupted stochastic settings.\nIt uses a Shannon-entropy regularizer together with an efficient projection routine derived from the KKT conditions over the convex hull of the m-set. This reduction converts a high-dimensional optimization into a one-dimensional root-finding task per round, yielding computational savings. Empirical evaluations demonstrate the effectiveness of the proposed method.", "questions": "1) The analysis relies on linear reward assumptions. Could the proposed method be extended to generalized linear or nonlinear reward functions (e.g., incorporating a link function)?\n2) The efficient projection routine appears tailored to m-sets (and perhaps partition matroids). What are the main challenges for generalization, e.g., non-separability, lack of monotonicity, or absence of closed-form inverses?\n3) Shannon entropy has been widely used in FTRL. Is the contribution mainly its specific integration into the BOBW setting or the projection simplification that follows from its analytical form? How does this choice compare with other regularizers employed in similar contexts?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1) This paper presents the first best-of-both-worlds (BOBW) regret guarantee for contextual combinatorial semi-bandits. \n2) It introduces an efficient numerical scheme for the FTRL update that significantly reduces computational cost while preserving the theoretical guarantees. \n3) The theoretical analysis is well-structured, with a new auxiliary “ghost context” game that simplifies the regret analysis. \n4) Empirical evaluations demonstrate substantial runtime improvements compared with Newton and MOSEK solvers.", "weaknesses": "1) This paper assumes a linear reward (or loss) function. The framework does not yet handle nonlinear or generalized linear models.\n2) The proposed efficient projection scheme is tailored to the m-set (and potentially partition matroids). For more general combinatorial structures, this computational savings may no longer hold.\n3) The Shannon-entropy regularizer adds an additional $O(\\log T)$ term in the adversarial regret, slightly weakening the asymptotic bound.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZmyPbzbvIH", "reviewer": "Reviewer_PYJa", "summary": "This paper studies a special case of contextual combinatorial semi-bandits and provides best-of-both-world guarantees for it. The setting is as follows: At each time step $t$, a $d$-dimensional context $X_t$ is revealed, then the learner has to select $m$ out of $K$ actions. Each action $k$ is associated with a $d$-dimensional vector $\\theta_{t,k}$, whose scalar product with $X_t$ defines its loss at time $t$. The instantaneous loss incurred by the learner is the sum of the losses of the action chosen at that time step. The total loss of the learner is given by the sum of the instantaneous losses, and it is compared to the total loss of the optimal context-dependent action map that achieves minimum loss in hindsight.\n\nThe authors study the (oblivious) adversarial setting, where the $\\theta_{t,k}$ vectors are chosen up-front by an adversary in an arbitrary way, the stochastic setting, where the  $\\theta_{t,k}$ are drawn i.i.d. from a fixed distribution for each action, and the corrupted case, where such distributions may slowly change over time, and some unbiased noise is added at each iteration.\n\nThe main contribution of the paper is a best-of-both-worlds algorithm, which the authors claim has an $O(\\sqrt{T})$ regret bound in the stochastic setting, and an $O(\\log T)$ instance-dependent bound otherwise.", "questions": "Please address my comments above. In particular, am I missing something about the $\\kappa$ parameter?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "- The authors complemented their theoretical results with some experiments. Although this is not strictly mandatory for theoretical online learning submissions, it is a nice addition. \n- To the best of my understanding, the paper is correct\n- Best-of-both-world results are important and of practical value\n- The authors also propose a numerical speed-up that enhances applicability", "weaknesses": "- The topic of the paper is extremely narrow, as the problem studied is quite involved and specialized. I am unsure whether it will garner general interest among the vast ICLR audience. \n- It is very challenging to gain a comprehensive understanding of the state-of-the-art and to compare it with the results presented in the paper. There are many parameters (namely, the context dimension $d$, the number of base actions $K$, and the cardinality constraint $m$), as well as numerous results implied by past works. Therefore, I strongly suggest that the authors include a table comparing the regret rates across various settings/assumptions. \n- The modeling assumption that the contexts are independent and identically distributed (i.i.d.) is somewhat surprising. What can be said when they are generated adversarially as well?\n- The overall algorithm construction is non-trivial but not novel, as it follows the standard FTRL template for BOBW. \n- My main issue is with the presentation of the results, which seems to me quite misleading: in the statement of Theorem 1, there is a parameter $\\kappa$ that inexplicably hides some important terms, making the understanding of the regret rates complicated.  $\\kappa \\in \\Theta(\\log T)$ term, this means that the stochastic regret is $O(\\log^2T)$, and not $\\log T$ as claimed in the introduction. The term $\\kappa$ also depends linearly on $\\sqrt{K}$, so that the overall regret rates depend polynomially on $K$, and not only on $m$, which may be drastically smaller. \n\nMinor:\n- The title ``Combinatorial Semi-Bandits'' is a bit misleading, as I was expecting a model similar to the one in the seminal paper by Cesa-Bianchi and Lugosi, where the action set could have any combinatorial structure (thus not only the cardinality constraint proposed in this paper). I am aware that other papers have already employed the generic combinatorial term for this specific case, but I still find it somewhat unusual. \n- In line 99, the authors refer to a lower bound by Bubeck & Cesa-Bianchi (2012), but I think that the citation is to the wrong paper. Shouldn’t it be Bubeck, Cesa-Bianchi, and Kakade COLT 12? In particular, does the cited lower bound apply to the special case of combinatorial bandits studied in this paper?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BmSj2Hb9xL", "reviewer": "Reviewer_4Chh", "summary": "This work studies the best-of-both-worlds (BOBW) algorithm for linear contextual combinatorial bandits. The algorithm leverages the follow-the-regularized-leader (FTRL) framework with a data-dependent learning rate to achieve the BOBW guarantee. Due to the monotonicity of the first-order derivative, the authors also prove that the optimization problem of FTRL can be efficiently approximately solved using KKT conditions and bisection. Experiments on the running time and cumulative regret of the proposed algorithm are conducted.", "questions": "1. Typically, FTRL with Shannon entropy regularization requires updating the policy distribution over the action space. This is computationally inefficient for linear bandits if action sets are exponentially large. To avoid this drawback, previous works have leveraged FTRL with self-concordant regularizers, which is operated in the convex set of the action feature set and is even shown to be possible to achieve the BOBW bound for linear bandits [7]. Is FTRL with a self-concordant regularizer also applicable to the linear contextual combinatorial problem?\n2. I notice that the dependence on $\\log T$ of the proposed algorithm in this work seems to be slightly better than previous works using FTRL with Shannon entropy regularizer (say, [1,2]). Could the authors comment more on this?\n\n[7] Ito et al. Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Bounds. COLT, 23.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This work seems to be the first work in the literature to study the BOBW linear contextual combinatorial bandit.\n2. Most parts of this work are generally well-written.", "weaknesses": "1. **Motivation**: I understand that the linear contextual combinatorial problem might be of some practical interest. However, given (a large number of) previous advances for BOBW combinatorial bandits, linear bandits, and linear contextual bandits, at this point, studying the BOBW linear contextual combinatorial problem seems somewhat not so technically appealing.\n2. **Novelty**: My main concern is about the novelty of this work, which is also partially related to the concern above. In recent years, it has been widely observed in various bandit problems that data-dependent learning rates can lead to BOBW regret guarantees. For this work, though the problem formulation is new, the used data-dependent learning rate $\\beta_t$ has a very similar form to those in previous works studying BOBW graph bandit [1], linear bandit [2], and linear contextual bandit [3]. The resulting intermediate regret bound (Lemma 2.4), depending on the summation of the entropy values, is also very similar to those in previous works. In this work, the use of FTRL with Shannon entropy over the convex set of super-arms, instead of the space of distributions over super-arms, has already been proposed in previous work for the adversarial contextual combinatorial problem [4]. Also, the used techniques for contextual bandits, including matrix geometric resampling and ghost context sampling, are standard in the literature for contextual bandits [5]. Therefore, to me, the main contribution of this work is that the authors find that the optimization problem of FTRL with Shannon entropy over the convex set of super-arms in special cases of $m$-set and partition matroid can be efficiently addressed by leveraging KKT condition and the monotonicity of the first-order derivative of the regularizer (btw, the definition of $m$-set seems to be that $\\sum\\_{k=1}^K(A)\\_k = m $ instead of $ \\sum\\_{k=1}^K(A)\\_k \\leq m$).\nTherefore, from the viewpoint of bandit learning, the novelty of the proposed algorithm and results appears to be limited. On the other hand, I am not working in the optimization area, so I think my sense for evaluating the novelty of the approximate solution to the FTRL optimization considered in this work might not be accurate. However, I also personally feel that using the KKT condition to solve a constrained optimization is standard, which I believe appears in most (basic) convex optimization courses.\n3. **Presentation**: It is good to see there are many discussions about the computation details of the FTRL update. However, for bandit learning, I personally think that the discussions and comparisons between regret bounds might be the most important parts to be included in the main paper body. For example, when specializing the results in the special cases of linear contextual combinatorial bandits, what are the advantages and disadvantages of the regret bound in this work when compared with previous works studying BOBW combinatorial bandits [6], linear bandits [2], and linear contextual bandits [3]? \n\n[1] Ito et al. Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs. NeurIPS, 22.\n\n[2] Kong et al. Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithm. COLT, 23.\n\n[3] Kuroki et al. Best-of-Both-Worlds Algorithms for Linear Contextual Bandits. AISTATS, 24.\n\n[4] Zierahn et al. Nonstochastic Contextual Combinatorial Bandits. AISTATS, 23.\n\n[5] Neu et al. Efficient and robust algorithms for adversarial linear contextual bandit. COLT, 20.\n\n[6] Zimmert et al. Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously. ICML, 19.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "R4pLGIpIY7", "reviewer": "Reviewer_vDJH", "summary": "This paper studies the contextual combinatorial bandit problems and investigates the best-of-both-worlds algorithm that achieves $O(\\sqrt{T} )$ regret in the adversarial regime.\nand polylog T regret in the stochastic regime. The paper proposes  the Follow-the-Regularized-Leader with a Shannon entropy regularizer, which is built upon the BOBW result of the contextual linear bandit. In addition to regret guarantees, the authors also propose the efficient projection subroutine in any FTRL with a Legendre regularizer. They show the reduction of the typical K-dimensional convex projection to a one-dimensional root-finding problem by KKT conditions. Finally, they provided the empirical experimental evaluations of the proposed methods.", "questions": "- Does the stochastic regime coincide with the setting by Qin et al. (2014)? Is so, could you provide the comparison with existing regret bounds? If not, could you describe what is the existing bound and also discuss the difference in the existing problem setting including the assumptions. For example, many stochastic combinatorial bandits assume $R$-sub Gaussian noise, but in the paper, you can only deal with the bounded noise due to the technical reason in the best-of-both-worlds algorithms. Is the context space allowed to be infinite?\n- Regarding the reduction of K-dimensional projection to a 1D root-finding using KKT, in special structures such as spanning tree or matroid bases, one could instead apply a Frank–Wolfe update to obtain a convex decomposition at extreme points in the FTRL framework.\nFrank–Wolfe update is already wildly applicable for various combinatorial actions.  Could you comment on whether the KKT-based projection offers additional benefits or theoretical guarantees beyond such structure-dependent methods?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- First result of the best-of-both-worlds algorithm for contextual combinatorial bandits.\n- The novel choice of the Shannon entropy regularizer, which is defined over the continuous actions of conv(Action space).\n- The computational advantage of the projection subroutine can be applicable to any FTRL framework in combinatorial semi-bandits. This advantage of Bisection over MOSEK/Newton is empirically validated.", "weaknesses": "- The problem formulation for adversarial combinatorial semi-bandits is based on Zierahn et al. (2023). However, a comparison with Zierahn et al. (2023) is missing in the empirical evaluation.\n- There are several formulations in  existing works on Contextual combinatorial bandits. Qin et al. (2014) is another formulation for the stochastic setting while Zierahn et al. (2023) is only for the adversarial setting. The paper needs to discuss the regret bound for stochastic regimes more carefully.\n- Due to the use of Shannon entropy regularizer and Precision-matrix estimation, the regret bound in the stochastic regime is $O(\\log^3 T)$ as $\\kappa=O(\\log T)$. Arguments of $O(\\log {T} )$ bound in the abstract/Introduction might be overclaimed.\n- The algorithm design and theoretical analysis is built upon the contextual linear bandits of Kuroki et al. (2024). The main difference is induced by the fact that Shannon entropy is now defined over the convex hull of the combinatorial action set. Given the fact that the proposed algorithm is not applicable to the case with $\\alpha$-approximate oracles for the offline comibinatorial problem, the techniques and theoretical analysis employed here is not significantly different from known results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)