Oracle-Efficient Combinatorial Semi-Bandits
Authors: Jung-hun Kim
Milan Vojnovic
Min-hwan Oh
Venue: NeurIPS 2025 poster ()
Keywords: Combinatorial Bandits
Oracle-Efficiency
Primary area: theory
TL;DR: We propose oracle-efficient algorithms for combinatorial semi-bandits.

Abstract: We study the combinatorial semi-bandit problem where an agent selects a subset of base arms and receives individual feedback. While this generalizes the classical multi-armed bandit and has broad applicability, its scalability is limited by the high cost of combinatorial optimization, requiring oracle queries at *every* round. To tackle this, we propose oracle-efficient frameworks that significantly reduce oracle calls while maintaining tight regret guarantees. For worst-case linear rewards, our algorithms achieve $\tilde{O}(\sqrt{T})$ regret using only $O(\log\log T)$ oracle queries. We also propose covariance-adaptive algorithms that leverage noise structure for improved regret, and extend our approach to general (non-linear) rewards. Overall, our methods reduce oracle usage from linear to (doubly) logarithmic in time, with strong theoretical guarantees.

Oracle-Efficient Combinatorial Semi-Bandits
Jung-hun Kim CREST, ENSAE, Paris FairPlay joint team, France j junghun. kim@ensae...
Milan Vojnović
Min-hwan Oh Seoul National University South Korea minohesnu, ac
London School of Economics United Kingdom
m. wo..jooovvc@@le.accc ac..ul...
Abstract
We study the combinatorial semi-bandit problem where agent selects subset of base arms and receives individual feedback. While this generalizes the classical multi-armed bandit and has broad applicability, its scalability is limited by the high cost of combinatorial optimization, requiring oracle queries at every round. To tackle this, propose oracle-efficient frameworks that significantly reduce oracle calls while maintaining tight regret guarantees. For the worst-case linear reward setting, our algorithms achieve Õ( regret using only Oloog log T) oracle queries. We also propose covariance-adaptivs algorithms that leverage noise structure for improved regret, and extend our approach to general (non- linear) rewards. Overall, our methods reduce oracle usage from linear to (doubly) logarithmic in time, with strong theoretical guarantees.
Introduction
The combinatorial semi- bandit problem extends the classical multi-armed bandit (MAB) model to settings where an agent selects a subset base arms (a combinatorial action) and receives individual feedback for each. This general framework captures many real-world scenarios, such as product recommendation, where set of items is recommended to a user [16]; ad slot allocation, where multiple ads are displayed on webpage [12] and network routing, where path comprising several links selected in a communication network 27
Due to its broad applicability, the combinatorial semi-bandit problem has been extensively studied in the literature (5 18
32] However, central challenge lies in the computational complexity of solving the combinatorial optimization problem, which is often NP-hard. As result, most existing algorithms assume access to an oracle that returns solution the combinatorial problem. These algorithms rely on querying the oracle at every round, leading to excessive oracle usage and substantial computational overhead in practice.
In this work, following the computational complexity notions introduced in Balkanski and Singer (1. Fahrbach al. (TI), distinguish between two measures of oracle efficiency: adaptivity complexity and query complexity, which are defined later. Our goal is to improve oracle efficiency by substantially reducing the overall oracle adaptivity and query complexities in decision-making over time horizon T', while maintaining tight gap-free regret guarantees that do not depend on the suboptimality gaps. Our main contributions summarized below and compared with prior work on gap-free combinatorial
in Table
Oracle-efficient algorithms for worst-case linear rewards: that significantly reduce oracle query usage while maintaining tight regret guarantees. Using adaptive oracle query framework, AROQ-CMAB achieves near-optimal regret of ( mmdT), with both adaptivity and query complexity bounded by Oddlog (og(Tm/d), where denotes the number of base arms and is the maximum number of activated base arms per action. To further improve computational practicality by reducing adaptivity complexity.
We propose two frameworks
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table 1: Gap-free regret bounds for combinatorial semi-bandit algorithms.
Combinatorial
Adaptivity Complexity
Query
Algorithm
Regret
Reward Model
Complexity
CUCB
(mm/aT)
e(T)
@(T)
Linear
CUCB
18
O (VmdT)
((T)
(
(Worst-case)
AROQ (our work)
Ó (VmdT)
O log log( T
O log log( Tmm
SROQ-CMA (our work)
(m
@llg log T)
Old T)
OLS-UCB-C 32
Σ
of(AT
((T)
(
sE(d] dEAxtiEa
Linear
(Covariance
AROQ-C-CMAB (our work)
SEAstiie (a))
O log(Tm))
(d log(Tm))
-dependent)
iEId
SROQ-C-CKAB (our work)
d daax (a))TT GEA iEa
@log
O log log T)
SDCB 4
O(LvmdT) O(L/mdT
((T)
(T)
General
ARDQ-GR-CMAN CMAB (our work)
Od log( Tm ld log( d''
SROQ-GR-CMAB (our work)
OLLmVdI dT)
@ log T)
Old T')
we propose a scheduled oracle query framework that executes multiple independent oracle queries in parallel. Under this framework, SROQ-CMAB achieves regret (m dl') with adaptivity complexity of O(log log and query complexity of O(d log log T').
Covariance-adaptive oracle-efficient algorithms for linear rewards: Utilizing our proposed frameworks, design oracle-efficient algorithms that leverage the estimated covariance structure of the reward noise. AROQ-C-CMAB achieves near-optimal regret
Ö( Eie(d maxceAst. iee df(a)T), where (a) denotes the variance contribution of base arm i under action a, with adaptivity and query complexities of O log(Tm)).. SROQ-C-CMAB achieves regret Ö( maxag Eiea (a)T) with adaptivity complexity (log log T) and query complexity of Odd log log T).
Oracle-efficient algorithm for general reward models: We extend our frameworks to general (non-linear) reward functions. AROQ-GR-CMAB achieves regret Ö (LLymmd)) with adaptivity and query complexities of (d ((dlop log log((Tm/))) where L denotes the maximum possible value of the reward. SROQ-GR-CMA achieves regret D(LmvdT) with adaptivity complexity of Ollog log T) and query complexity of (d log T)..
Related Work. The combinatorial cemi-bandit problems have been extensively studied, starting from the foundational work of Chen et al. [5]. Kveton et al. 18] established tight regret bounds that netrmoptimal. Further improvements were made Combes al. [7]. who derived better bounds under the assumption that the feedback from selected arms is independent.
More recently, unified framework that accounts for both dependent and independent feedback through covariance analysis was introduced by Degenne and Perchet [9], assuming knowledge of the covariance matrix. This line of research has been further advanced by Perrault et al. [22] and Zhou et al. [32], who developed covariance- covariance-adaptive algorithms based on confidence ellipsoids. In addition to linear reward structures, generalized linear reward functions have also been studied in the
combinatorial semi-bandit setting by Chen et al. [
Despite these advances, all of the aforementioned works require solving a combinatorial optimization problem frequently at every round using an offline oracle, which generally NP-hard (8). To alleviate the computational burden, Cuvelier et al. [ proposed approximation-base approach that achieves polynomial-time complexity. However, their method introduces trade-off between regret and computational cost, achieving near-optimal regret necessitates increasingly accurate

---

approximations ppproiimtiooss-leddnnn to potentially unbounded computational time Similarly, Chen et al. [S] considered approximation oracles but focused on minimizing approximate regret, rather than the original regret, and their method is limited to cases where such approximation oracles are available. Neu and Bartók (20] studied efficient algorithms the adversarial semi-bandit setting, but their method still requires solving the optimization problem at every round and does not attain optimal regret in the stochastic setting. Similarly, Zhou et al. [32] proposed an adaptive covariance-base algorithm using ellipsoidal confidence regions, yet it also incurs oracle calls at every round. Lastly, Tzeng et al. [26] studied matroid cemi-bandits with sublinear per-round computational complexity by exploiting matroid structure, direction that is complementary to our focus reducing the number of oracle calls for combinatorial aani-bandits with arbitrary action sets.
As related line of research, oracle-efficient algorithms have been studied for submodular function optimization problems [ 11. However, these approaches do not involve latent models that can be learned from stochastic sequential feedback, as in bandit learning. As a result, they differ fundamentally in formulation and are not applicable to the bandit setting. Oracle-efficient bandit algorithms have also been proposed for bandit linear optimization 177. achieving Oppoly (d, log T)) oracle complexity. However, these approaches assume linear rewards with full-arm decisions and do not handle combinatorial action spaces semi-bandit feedback, which are central to our setting. To the best of our knowledge, rare oracle queries in combinatorial semi- bandit problems have only been empirically explored by Combes et al. [7]. who proposed a heuristic using Oloo T) oracle calls but without theoretical regret guarantees. Furthermore, several variants of combinatorial bandits heavily rely on frequent oracle queries, including Thompson Sampling methods 28), maximum- reward feedback settings [29]. and pure exploration problems s
2 Problem Formulation
There are d base arms, and let A S 13 denote the set of available actions, where each action a E A a binary vector indicating the activated base arms. We allow A to be an arbitrary subset of {0, 1)d Then, we define m = A A |lallo as the maximum number of activated base arms across all actions. At each time t = [T], the environment samples a vector of rewards E [0. 1]d from a fixed distribution D that is unknown to the agent, and the agent chooses an action a₂ E A. For any vector I E IRd we use to denote its i-th entry. Then, the agent receives reward r(az, Dt) where (semi-bandit feedback). The mean of the latent distribution D is denoted by l (MI,.... Md)). We first focus on the standard linear reward setting studied in prior work [88 7 9 [2 32), where the reward is given by ra., yt) == (a. 31). We will discuss generalizations beyond the linear case later.
r: Ax [0, 1j + R, and observes the values of yt, for each i E [d] such that dr.
Regret. Let a" be optimal action, a" E argmax aE F(a), where F(a) Ey (r(a, y)] repre- sents the expected reward function (e.g., F(a) = (a, p) in the linear case). The goal is to minimize the cumulative regret over horizon T, defined as R(T) = E (F(a") F(a+))).
Combinatorial Optimization. For finding an optimal action, it is required to solve the combina- torial optimization problem argmax F(a). whose computational cost, in general with arbitrary A C {0, 17d, is proportional to the size of A which is (dd)). To address this computational complexity, the previous work on combinatorial semi-bandits 7 I8 assumed access to an oracle, which returns a solution for the combinatorial optimization. However, these methods require querying the oracle at every round. In this work, we aim to substantially reduce the number of oracle queries while achieving tight regret. Formally, as in the previous work, we assume access to an oracle that returns at E argmax (a) for given f A - IR. Furthermore, our oracle-efficient approach can be incorporated with an approximation oracle, which will be discussed later.
Oracle Efficiency. Following the computational complexity notions introduced in |_, we evaluate the oracle efficiency of our algorithms using two key measures, which are described as follows and illustrated in Figure I Query complexity refers to the total number of individual oracle queries made over the entire time horizon. This reflects the standard computational workload of the
'To reach optimal regret, the approximation level & must satisfy lim òz = 0. and each round incurs cost ((166)) +
3

---

Adaptivity Complexity:
Query Complexity: :
3
2
Query
Parallel <
Oracle Query
No Queries
No Queries
Oracle Query
Oracle Query
Oracle
Oracle Query
Round
Round
Figure I: Oracle adaptivity and query complexities.
algorithm. Adaptivity complexity captures the number of sequential rounds oracle queries, where each round may consist of a set of queries that can be executed in parallel without depending on each other.
While query complexity is important in general, adaptivity complexity often dominates the actual runtime cost in parallel or distributed environments, where parallelizing queries within a round is easy, but synchronizing between rounds incurs overhead. Our goal is to reduce both measures of oracle complexity while maintaining tight regret guarantees.
Additional Notation. With a slight abuse of notation, we write E a for a A the i-th coordinate of satisfies = 1. For any b, E I, we write $ to indicate that b is upper bounded by up to constant factor. We use b4 for max(b,0)
Oracie-Efficien Algorithms and Regret Analysis
We present two frameworks for combinatorial semi-bandit problems with rare oracle queries: one based on an adaptive oracle calls, and the other based on scheduled oracle queries, both inspired by batch learning 21 25
13
10
15
23 30 14.
3.1 Adaptive Rare Oracle Queries
We propose algorithm (Algorithm 1 that leverages adaptive oracle queries. The algorithm employs a UCB-based strategy with adaptive epoch- epoch-based updates, enabling efficient exploration despite infrequent oracle access. We the UCB indices defined for some constant C >>> 0,
Clogt n4,4
UCB (CB((a)= ri
Σ
Po,s +
where jr,; (1/n,,) E Vs, 1(i ag) and nt,i n4, -+,== E E a,). The UCB index for each action is updated when there exists base arm i whose selection count exceeds a specified threshold. More precisely, the indices are updated when the number of rounds in which arm has been selected in the current epoch, denoted by [T:)), satisfies [T((T)) 2 /Tm I7a(T - 1)l/d, where 7, is the epoch index for arm i, and TT(T) is the set of rounds in epoch T where i was selected.
The intuition for the threshold condition of oracle queries is follows: for E [d] with Tr the instance regret is bounded by /I/[T,(T: 1)] that with the bound for [T.(T:)] from the update condition, the overall regret for T epochs is bounded by (T(()))////TT( - -1) x /Tm Ti(r, d//1t// - 1)1 = /Tm//e /d By considering all T, for E [d], we can obtain the optr-mltimal regret bound with oracle efficiency.
Theorem With oracle adaptivity and query complexities of Od log(Tm/d)), respectively, Algorithm 7 achieves a regret bound of
R(T) = (V log log log log(Tm/dd)
Proof. The full version of the proof is provided in Appendix

---

Algorithm Adaptive Rare Oracle Queries for Combinatorial MAB (AROQ-CMAB)
Initialize: 7; for all i [d] for t = 1.2... T..,T'oo do
for iE [d]]s.. (T)(T)) 2 1 T x+ T T((Ti) F
[T(T; Tmm
1)l/d do
Update <- True
if U Updaae True then
at arg max rt UCB (a) with ①
I/ Oracle Query
Update + False else
L Ot < a:-1
Play aj and observe feedback yt for E at T((T) T((T)) U {t} for all i a2
Comparison to Previous Work. The worst-case regret lower bound for this problem is known be Q(vmdT) [5), and near-optimal regret was achieved by the algorithm of Chen al. [5], Kveton et al. [1]] However, their approach requires ((T)) oracle adaptivity and query complexity, respectively. In contrast, our proposed algorithm, AROQ-CMAL (Algorithm [ achieves a near-optimal regret bound while significantly reducing both oracle adaptivity and query complexities to Od log(( m /d)).
--AApprxxmmaton Oracle. Prior work on combinatorial bandits (5) mitigates the cost of exact ora- cles by using a-approximation oracles, which return an action al satisfying f(al) 2 a max (a) for some approximation factor [0, 1], when such oracles are available. This leads analyzing the regret relative to the best a-approximate reward, rather than the true optimal reward. In contrast, our method targets the original voonaapprxximtt) regret while reducing the frequency of oracle queries. Nevertheless, our framework can naturally incorporate a-approximation oracles, achieving the same regret guarantee in terms of a-approximate regret with only infrequent approximate oracle calls. See Appendix A.3 for details.
3.2 Scheduled Rare Oracle Queries
To further reduce adaptivity complexity and enable more efficient distributed computation, we propose an algorithm that performs scheduled batched oracle queries at predetermined epochs (Algorithm) 2) allowing these oracle queries to synchronized and executed in parallel. At each epoch т, we define UCB and LCB indices as: for some constant C >>> 0
Cllog T
C'log T n2,5
UBB PT
Σ
Ar. +
and LCB (a)
Σ
n7,5
where Pr.s = (1/n,,s) E(=i' Vi,e (i ac), n2, E 1(2 at), and t, denotes the start time of the 7-th epoch.
To schedule oracle queries, we adopt an elimination- bbasdd bandit strategy 25 However, in combi- natorial bandits, the exponentially large number of suboptimal actions poses significant challenge for efficient exploration. To address this, we construct a representative action af for each base arm e [d] in epoch т. Using elimination conditions applied these representative actions, we can efficiently eliminate large number of suboptimal actions by focusing on suboptimal base arms those that are part of the optimal action a'. In each epoch, these representative actions are selected for exploration, after which the estimators and representative actions are updated. This process requires oracle queries but only the batch level, keeping the query frequency low.
Let T = (t, (t....... tt denote the set of time steps at which oracle queries are made, where M > 0. 1, lM T, and for scaling factor is set to 17 = (1/(2-21- We choose M = (log log T) to ensure doubly logarithmic adaptivity and query complexity. Parallel execution of oracle queries is discussed in Appendix A.1
< M, the sequence defined recursively
n/TT-i The
5

---

Algorithm 2 Scheduled Rare Oracle Queries for Combinatorial MAB (SROQ-CMAB)
Input: T
1 for T = : do
Update Hi, = (1T,,).... Ar,d)
af aE 14 (a) for all i E with
I/ Oracle Queries // Oracle Query
Nr. - (iEN,-1 | (a. (1)) 2 max (40B(a) with
Ar - A-
ai a-= 0 for all i [d]/N;]
T + 1,.1++1
fort E Tr do
it ((t 1) mod |W] + 1) element of Ng.
(4) and observe feedhack yt, for E at
Play ar = dr
Theorem With oracle adaptivity complexity of O(log log T) and oracle query complexity of Odd log Algorithm 2 achievess a regret bound of
R(T) 0 log logT)
Proof. The full version of the proof is provided in Appendix A.4
We observe that Algorithm 2 improves the adaptivity complexity from Old log(Tm/d)) in Algorithm to (log log T), at the cost of an additional vm factor in the regret.
Remark In practice, Algorithm can be more computationally efficient than Algorithm 7 First, due its reduced adaptivity complexity, Algorithm P enables more efficient parallel execution of oracle queries. Second, the elimination process progressively discards suboptimal base arms, reducing the oracle query complexity per round from (dd)) to (( where Nr1 S d denotes the number of remuining buse arms at epoch These computational advantages are further supported by our experimental results presented later.
Our proposed frameworks for combinatorial semi-bandits with rare oracle queries can be extended to variants of the combinatorial semi-bandit, including covariance-depender CMAB and general-reward CMAB. In the following, we examine each of these settings in turn.
4 Extension to Covariance-dependen CMAB
In this section, instead of targeting worst-case regret, consider covariance-dependent regret, inspired by (9] 22 32). The covariance-depente
analysis can cover independent or dependent (worst-case) semi- bandit rewards of arms in an action. Here, the covariance matrix for the reward distribution D is denoted by E E Rdxd which is assumed to be unknown to the agent.
assume that for any 1 a, aj = 1. When this assumption does not hold, our algorithms and analysis extend naturally by restricting attention to observable pairs, that is, pairs (i, for which there exists action A with 0; aj = 1. All results continue to hold under this extension, with the same regret guarantees.
For simplicity,
S j d, there exists action a A such that
In the following, we propose covariance-adaptive algorithms based on our two frameworks- adaptiv and scheduled rare oracle queries to handle this setting.
4.1 Adaptive Rare Oracle Queries for Covariance-adaptive Approach
We first propose an algorithm (Algorithm 3 based on the adaptive rare oracle query framework. Recall that n4,; = E 1(i matrices, where D. has the entries of vector z on its diagonal, and Dx has the diagonal entries of matrix X.
a.) and n4 := (n.. R),a). Let D, and Dx denote diagonal
We define the estimated means as f4t D-1 D Da, We also define covariance estimator
E, = S - PupT where Se,0.) (1,(6.) Σ 0g il..s.... and confidence bound Eg,6,)) =

---

Algorithm 3 Adaptive Rare Oracle Queries for Covariance-adaptive CMAB (AROQ-C-CMAB)
Initialize: Ti.j for all i, [d] [d]
for t = 1. 2..... T....To do
if < [d(d+1) log" (T) then
Let (i,j) the ((1 (1-1) mod did-1)
+ +1)-th pair a fixed enumeration of pairs (i, j)
2
with 1 _
d
Cr - any a E A s.t. a
ift= [ 1) log (T) /2] then
F. T.. for all i,j E [d] x [d]
else
for i,j E [d] x [d] s.t. (T)( 1+ (T - 1) do
R. T1.j +1, T (Teg)
Update t True
if U Ddaaee True then
at + arg max.ca UCB (a) with 3 Updale & False else
I/ Oracle Query
L at at-1
Play d and observe feedback yi,r for E at (Ty(T (Ta)) (t) for all i a and j E at.
E1,(1s) + 1 5he
where (1.5) = - 1(i E.) E a.) with (e,(4.)
Wr.i and h, = O bog( t + log d). Define the gram matrix Gt Ex1 Da, D,,,, + DDz, Dns +I.
Then, we utilize the UCB index, defined
ucB (C) = (c) + Dzl allo.
(3)
where /: - Ollog t + lol log t).
To initialize, the algorithm uniformly explores actions a warm-up phase for the stability of the covariance estimator. Then in the main stage, for the adaptive update condition, we adopt a stricter criterion than that of (worst-case) Algorithm[]] resulting in more frequent updates-though oracle queries remain rare-while handling the covariance- deeanneeddeedentt bound to achieve a tighter guarantee. For the covariance dependent regret bound, define of (a) Ejea(E (E.,)) The algorithm achieves near-optimal regret bound asymptotically as follows.
Theorem With oracle adaptivity and query complexities of (dd log(Tm))) respectively, Algo- rithm achieves an asymptotic regret bound of
R(T)= =
T #EId
max
o?(a)
eEAst sEa
Proof. The full version of the proof provided in Appendix A.5
In the worst case of dependent base rewards, regret bound becomes Ö Ö(vmdl)) which is the same as that of Algorithm [ However, for the independent reward case across all base arms (i.c., y = I), the regret bound becomes Ō VdT)), which is tighter by a factor of /m.
Comparison to Previous Work.
As discussed in (32. the proposed algorithms in 22 achieved gap-dependent asymptotic regret bound, which is not tight for the gap-free bound with respect to T because of the additional 1/42 min factor. The regret lower bound of this problem is
0 /T Diela max sL iea
(a))
32 and 32 propose algorithm achieving near-optimal gap-
free asymptotic regret bound of Ō Σ leg max tEa (a())) with ( oracle adaptivity
7

---

Algorithm 4 Scheduled Rare Oracle Queries for Covariance-adaptive CMAB (SROQ-C-CMAB)
Input: T
10 for t E [.[ddd+ + 1)/ do
Let (1, be the (t (t-1) mod d(d+1)
2 + +1)-th pair in fixed enumeration of all pairs (i,j) with
11
1 1 d a: - any a E A.t. i a,jEa
12
for 1, ... .M do
Update ü ((,)) for all (i,j) E [d] x [d]
14
af argmax AEA, neea 1 (BB (a) for all AG-1 with 44
// Oracle Queries
ar (i.)) argmax,EAAH nijcco 17 (CB(() (a) for all (i. :
16
// Oracle Queries
17
N + NG- |,+ PBB (a! 2 max
1T LCB (a)) with
// Oracle Query
A ( a; for all i [d]/}}}
19
N ((i,)) E EN, N, (r (13) 2 maxaEA; 17 (C),
1/ Oracle Query
A, + fa Ar aa, = = or a, = 0 for all (i.j) [d] x [d]/N/ ,
20
T,") + 1,,,,,,7,, - (d log 27 / 11. (2) + [tr +T, md log T) T) ,t++1 -
21
for f do
22
23
it (t mod [ 1-th element in N Play 0r = at Receive reward (ar, vt) and observe feedback yr, for E [d] s.t. az
24
25
for 1 E T do
26
(i,5) (t mod (Nr2) I)- element in A/
27
Play d at ((-)
28
29
Receive reward (at, ya) and observe feedback yr, for E [d] s.t. 04,1 =
and query complexity, respectively, Our algorithm achieves the near-optimal asymptotic regret bound with reduced oracle adaptivity and query complexity of ( log(m?))). respectively.
4.2 Scheduled Rare Oracle Queries for Covariance-adaptive Approach
Here, we propose a covariance-adaptive algorithm (Algorithm 4 by utilizing the framework of scheduled rare oracle queries. Recall that for each epoch Pr, = (1/nr,s) El= vt.; 1 (i a,) where R4,; Eir 1( at) and t, is the start time of epoch in the algorithm. For the covariance estimator, we define Σt, = ST ÚT where ST,16.)) = (1/n7,i.)) El- Nt.
and confidence bound Er,(i,)) = ET,(K)) + + Mintes
5hr + (e.(i.5)
n2. + n2
where RT,(6.))
E 1(2 E a,)1(j E az), (T,(6.)) = n7,i, and hy = O( ((Vlo T+ log d). Define the gram matrix G, = Σ.T D.. D,D,, Dr= Dn. Then, for the confidence bounds, utilize
(4) where fr = Ollog T + d log log T). For scheduled oracle queries, we employ the same time grid
NOB (a) (a, M(T)) fr frl1 and L (a, ((()) - 12.1
T -4,,..., ..r) as in Algorithm 2 shifted by [d(d+1) time steps to account for the warm-up phase, that is, la < la [d(d 1)/2 for all [M]. Parallel execution of oracle discussed in Appendix A.I
Theorem With oracle adaptivity complexity of O(log log T) and oracle query complexity of (d log log T),, Algorithm achieves an asymptotic regret bound of
R(T) = (1
(1/mex
/max Eof(arr aeA sEa

---

Proof. The full version of the proof is provided in Appendix A.6
In the worst case, the scheduled query-based Algorithm achieves regret bound of Ommval dTT). which matches that of the scheduled query-based Algorithm 2 but is larger than the bounds achieved by the adaptive oracle query framework of Algorithm and Algorithm 3 by a factor of Vm. This gap arises from the inefficiency of using a fixed-time framework compared to an adaptive-time framework. However, the oracle complexities of Algorithm 4 are significantly lower than the (d log(m"))) complexities of Algorithm 3 query complexity.
achieving (log log adaptivity and (dd² log log T)
5 Extension to General-Rewarte CMAB
In this section, beyond a linear reward function we explored in the previous sections, we consider general reward functions r(a, y) defined on A x [o, 1 + [0, L] for L > 0. We adopt the same setting with assumptions as in [4. Specifically, at each time t. the arms produce stochastic outcomes (e [0, 1] drawn i.i.d. over time from distribution D with finite suppor
f and the expected reward is denote by F(a) = Ey~zl[(( [r(a, y)]. In this setting, we consider the following assumption.
Assumption (Monotone reward function) For any y, v/ E [0, 1]a satisfying yc S for all i E [d] and any A, we have r(a,y) S x'(a,y').
The assumption for the monotone reward function is commonly observed in various combinatorial problems such as K-MAX [24]. K-SUM [5), and Expected Utility Maximization [19]
By adopting our adaptive and scheduled frameworks for rare oracle queries, we propose oracle- efficient algorithms for general reward CMAB; Algorithms 6 and 7 respectively. The details of
the algorithms are provided in Appendix A.7 In what follows, we provide theorems for oracle complexities and regret of each algorithm. The proofs are provided in Appendices A.8 A.9
Theorem With oracle adaptivity and query complexities of Old log(Tm/d)) /d), respectively, Algorithm 6 achieves a regret bound of R(T) = dLLV
Theorem With oracle adaptivity complexity of O(log log'T) 1) and oracle query complexity of Od log T), Algorithm 7 achiivess a regret bound of R(T) = (Lm
Comparison to Previous Work. Chen et al. [4] proposed algorithm achieving regret bound of Ö(LVmdI) with oracle adaptivity and oracle query complexities of ((T). However, our algo- rithms achieve OLLvmdT) and (Lmy respectively, requiring significantly reduced oracle complexities of of order log To
6 Experiments
We compare our algorithms to benchmarks in terms of oracle efficiency and regret using synthetic dataset+ We begin with the linear reward setting, where the mean vector is sampled from Uniff0, 1] with d = 20 and m = 3, and stochastic rewards are uniformly generated around these means at each round. As shown in Figure 2] (a,b), our algorithms (AROQ- CMAB, SROQ-CMAR achieve significantly lower oracle adaptivity and query complexities than CUCB [5] consistent with Theorems and [ Importantly, as shown in Figure 2 (d), our algorithms achieve faster runtime than the benchmark. In particular, SROQ-CMAR CMAB outperforms AROQ-CMAB in runtime, benefiting from a lower total adaptivity complexity up to T (Figure 2 (c)). which enables more efficient parallel oracle execution (Remark D Figure 2(c) demonstrates that AROQ-CMAB incurs slightly higher regret and SROQ-CMAB incurs somewhat larger regret than CUCB, which is consistent with our theoretical predictions: the regret bounds involve an additional logarithmic factor for AROQ-CMAR and vm
"The dinite-support assumption simplifies the algorithms and analysis but is not essential. As noted in Chen al. [4] the results can extend to Lipschitz contiiuuz reward functions by discretization techniques that preserve the same regret bound (see Appendix A.
Source Code: https:

---

Cursulativee
Cumulative Grade Query Complexity over Time
18
Cumulative Regret over Time
2.0
CUCB
peapivity Comp cutty
1.5
Qvery Complcatty
1.5
GRC0-CMA (i22)
ARCO-CMAR
SRDO--MAA (Aig2)
Comdktive
Camulativn
1.0
1.0
0-
5000
10000
15000
20000
0
5000
10000
15600
20000
Timet
Time
Timm t
(a)
(b)
(c)
Buntime parison
20000
Total Dracis Adaptivity Complesity
20000
Total Dracts Complexit
"oal Addpbrrii Compleakes
TMAA
1000
300
(Alg))
(4/g2)
(A
(Ag1)
(Ag2)
Mpor thins
Algoritmms
Algorthrss
(d)
(1)
Figure 2: Experimental results for linear rewards with d = 20 and m
factor for SROQ-CMAB. Additional results for the covariance-alaative variants and general reward functions are provided Appendix
A.II II
7 Conclusion
In this work, we proposed oracle-efficient algorithms for comi-combinatorial bandits. We intro- duced two algorithmic frameworks for handling rare oracle queries-adaptinn adaptive and scheduled- demonstrated that our algorithms significantly improve oracle efficiency while maintaining tight regret guarantees for worst-case linear rewards, covariance-dependent linear rewards, and general (non-linear) reward functions.
Societal Impact. The research is primarily theoretical and does not engage with human subjects, sensitive data, or domains with identifiable risks of negative societal impact.
Acknowledgements
J. Kim acknowledges the support of ANR through the PEPR IA FOUNDRY project (ANR-23- PEIA-0003) and the Doom project LLAN-23-CE22--00 -002), well as the ERC through the Ocean project
M. Oh was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. RS-2022-NR071 and RS-2023-00222663), by the Global-LAMP Program of the NRF grant funded by the Ministry of Education (No. RS-2023-00301976; and by AI-Bio Research Grant through Seoul National University.
AACEAN-101071610
References
[1] Balkanski, E. and Singer, Y. (2018). The adaptive complexity of maximizing a submodular function. In Proceedings the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, page 1151,, New York, NY, USA. Association for Computing Machinery.
[2] Chekuri, C. and Quanrud, K. (2019). Parallelizing greedy for submodular set function maximiza- tion in matroids and beyond. In Proceedings of the 51 Annual ACM SIGACT Symposium Theory of Computing, pages 78-89.
[3] Chen, S., Lin, T., King, I., Lyu, R., and Chen, W. (2014). Combinatorial pure exploration of multi-armed bandits. Advances in neural information processing systems, 27.
10

---

[4] Chen, W., Hu. W., F., Liu, Y., and Lu, P. (2016). Combinatorial multi-armed bandit with general reward functions. Advances in Neural Information Processing Systems, 29,
[5] Chen, W., Wang, Y., and Yuan, Y. (2013). Combinatorial multi-armed bandit: General framework and applications. In International conference on machine learning, pages 151-159. PMLR.
[6] Chen, X., Krishnamurthy. A., and Wang, Y. (2024). Robust dynamic assortment optimization in the presence of outlier customers. Operations Research, 72(3):999-1011
[7] Combes, R.,
Talebi Mazrach Shahi, M. S., Proutiere, A., et al. (2015). Combinatorial bandits revisited, Advances in neural information processing systems, 28.
[8] Cuvelier, T., Combes, R., and Gourdin, E. (2021). Statistically efficient, polynomial-tin time algorithms for combinatorial semi-bandits. Proceedings the ACM on Measurement and Analysis of Computing Systems, 5(1):1-31.
[9] Degenne, R. and Perchet, V. (2016). Combinatorial semi-bandit with known covariance. Advances Neural Information Processing Systems, 29.
[10] Dong, Ki, Y., Zhang, Q.. and Zhou, Y. (2020). Multinomial logit bandit with low switching cost. In International Conference on Machine Learning, pages 2607-2615, PMLR.
[11] Fahrbach, M., Mirrokni, V., and Zadimoghaddam, M. (2019). Non-monotone submodular maximization with nearly optimal adaptivity and query complexity. In International Conference on Machine Learning, pages 1833-1842. PMLR.
[12] Feldman, J., Henzinger, M., Korula, N., Mirrokni, V. S., and Stein, C. (2010). Online stochastic packing applied display ad allocation. In European Symposium on Algorithms,, pages 182-18 194. Springer.
[13] Gao, Z., Han, Y., Ren, Z., and Zhou, Z. (2019). Batched multi-armed bandits problem. Advances Neural Information Processing Systems, 32.
[14] Hanna, O., Yang. L., and Fragouli, C. (2023a). Efficient batched algorithm for contextual linear bandits with large action space via soft elimination. Advances in Neural Information Processing Systems, 36:56772-56788
[15] Hanna, O. A., Yang, L., and Fragouli, C. (2023b). Contexts can be cheap: Solving stochastic contextual bandits with linear bandit algorithms. In The Thirty Sixth Annual Conference Learning Theory, pages 1791-1821. PMLR.
[16] Hao, J., Zhao, T., Li, J., Dong, L.,, Faloutsos, C., Sun, Y., and Wang. W. (2020). P-companion: A principled framework for diversified complementary product recommendation. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pages 2517-2524
[17] Ito, S., Hatano, D., Sumita, H., Takemura, K., Fukunaga, T., Kakimura, N., and Kawarabayashi, K.-I. (2019). Oracle-efficient algorithms for online linear optimization with bandit feedback. Advances in Neural Information Processing Systems, 32.
[18] Kveton, B., Wen, 7., Ashkan, A., and Szepesvari, C. (2015). Tight regret bounds for stochastic combinatorial semi-bandits. In Artificial Intelligence and Statistics, pages 535-543. PMLR.
[19] Li, J. and Deshpande, A. (2011). Maximizing expected utility for stochastic combinatorial optimization problems. In 201 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 797-806. JEEE,
[20] Neu, G. and Bartók, G. (2013), An efficient algorithm for learning with semi-bandit feedback. In International Conference Algorithmic Learning Theory, pages 234-248. Springer.
[21] Perchet, V., Rigollet, P., Chassang, S., and Snowberg, E. (2015). Batched bandit problems. In Conference on Learning Theory, pages 1456-1456. PMLR.
[22] Perrault, P., Valko, M., and Perchet, V. (2020). Covariance-adapting algorithm for semi-bandits with application to sparse outcomes. In Conference on Learning Theory, pages 3152-3184. PMLR.

---

[23] Ren, X., Jin, T., and Xu, P. (2024). Optimal batched linear bandits. In International Conference on Machine Learning, pages 42391-42416. PMLR.
[24] Simchowitz, M., Jamieson, K., and Recht, B. (2016), Best-of-k-bandits. In Conference on Learning Theory, pages 1440-1489. PMLR.
[25] Slivkins, A. et al. (2019). Introduction to multi-armed bandits. Foundations and Trends@ in Machine Learning, 12(1-2):1-286.
[26] Tzeng, R.-.., Ohsaka, N., and Ariu, K. (2024). Matroid semi-handits in sublinear time. In Proceedings of the slst International Conference on Machine Learning, pages 48855-48877.
[27] Vesselinova, N., Steinert, R., Perez-Ramirez, D. F., and Boman, M. (2020). Learning com- binatorial optimization on graphs: A survey with applications to networking. IEEE Access, 8:120388-128 120416.
[28] Wang, S. and Chen, W. (2018). Thompson sampling for combinatorial semi-bandits, In International Conference on Machine Learning, pages 5114-5122. PMLR.
[29] Wang, Y., Chen, W., and Vojnović, M. (2023). Combinatorial bandits for maximum value reward function under max value-index feedback. arXiv preprint arXiv:2305. 160.244...607.
[30] Yu, S. and Oh, M.-h. (2025), Optimal and practical batched linear bandit algorithm. In Proceed- ings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 73262-73285. PMLR.
[31] Zhang, 7., Ji, X., and Zhou, Y. (2021). Almost optimal batch-regret tradeoff for batch linear contextual bandits. arXiv preprint arXiv:21 10.08057.
[32] Zhou, J., Gaillard, P., Rahier, T., Zenati, H., and Arbel, (2024). Towards efficient and optimal covariance-adaptico algorithms for combinatorial semi mani-ssndits. Advances in Neural Information Processing Systems, 37:30474-30521.
12

---

A Appendix
A.1 Details for Parallel Execution of Oracle Queries in the Scheduled Framework
This section provides further details on the parallel execution of oracle queries within the scheduled framework. Specifically, we describe how our proposed algorithms (Algorithms 2 and 7 support parallel execution of oracle queries to reduce adaptivity complexity.
Worst-Case Linear Rewards. In Algorithm 2 the beginning of each epoch, the oracle queries
in Line 3 can be executed in parallel. Moreover, although Line 4 depends on the result of Line 3 the oracle queries in Lines and 4 can still be executed in parallel, as they involve independent computations. Specifically, evaluating maXaęA (a) in Line requires only a single independent
oracle call that returns the maximizer at = argmax, REA FT LLB maximum value (a²)
(a), allowing us to directly retrieve the
Covariance- Deeenneent Linear Rewards. In Algorithm 4 the oracle queries in Lines 15 16 and 17 can be executed in parallel, following the same principle as in the worst-case linear rewards setting. In contrast, the query Line 19 must be performed sequentially afterward since the oracle relies on the updated set A', resulting from the preceding computation.
General Rewards. In Algorithm 7 following the same principle in the worst-case linear rewards setting, the oracle queries in Lines 32 and 33 can be executed in parallel.
A.2 Proof of Theorem
Let T((1) be the value of at time / in the algorithm. Then T; (T') represents the number of updates, each update requiring oracle queries, up to T from arm Then, for the bound the total oracle queries up to T, by adopting the proof techniques in (10), we have the following lemma.
Lemma (Oracle Queries Bound) We have
Σ T, (T)
Odlog (oolooommm//loo (Tm/d)).
KE dj
Proof. We first provide the following lemma.
Lemma 2 For M 2 0 and sequence Tn, F1,... such that 33 2 1 1 MRi- for all
have that 2 M 1-2--++1 for all 2 1.
Proof. For T 1, we have
21 2 1 + Mao 2 1 = M
which satisfies the desired inequality. We now proceed by induction. Suppose that for some 7 2 1, the inequality 2, 2 M 1 holds. Then, using the recurrence, we have
F74 + Mæ,
2 + M MI-2-
1 + (22-2-T-1/22
= 1 + -1-2--
-
Thus, by induction, we conclude that
x+ 2 1-2
for all 7 2 1.
13

---

Let To log log(Tm/d). From Lemma 2 if 2 + 1 and T is not the last stage, for any i [d]. we have
77 (Tm/d)²-2 2 (Tm/d)²= loxlox(Tm/d) Tmm2d.
Therefore, from the fact that Et=1 |la/lo S mT. there are at most 2d + d (including the last stages for all E [d] pairs of (i, 7) for [d] and [T)( satisfying 2 + 1. This implies that for i E [d] s.t. (T) 2 To + 1, we have Lieig (T)(T) 2 To + (T) S dro + 3d. Therefore, we have
Σ (T)
S d +E
Σ se|d
20 2 1)(())
dTo = log logg (Tm/d);
[e|d
which concludes the proof.
For the proof of regret bound, utilize the Azuma- Azuma-Hoeffding inequality provided in the following lemma.
Lemma (Azuma-Hoeffding Inequality) For martingale difference sequence XI...., Xn with support of size 1 for all X,, for > 0 we have
IP
Σ
Xi 2 mm
S 22xxp-22²2))
From Lemma
show that the event & {1p Aayi
1.5 Rh,
tii [d]
(1)). For ease of presentation, we define auxiliary variables ni, and i for each [d] and time step & (7] for the analysis the rare updated indexes as follows: If the selected action at time t is newly updated in the algorithm (i.c., Update = True), then
holds with probability of least 1 ((
n n4,,
P4.5 Pr.
Otherwise, if the previously selected action is maintained (i.e., Update = False), then
n/,, 14
Pl. 1
Using these adjusted statistics, we define the UCB-based optimistic reward estimate for any action
Clogt ni,s
FUCB (a) Σ
Pl.s +
TEa
Now we provide bound for the regret as follows:
R(T) = Σ -(()))
+ IE
Σ (E(T]
(F(a*) - -(())))((E))
[E(T]
S
Σ F(ax))
+ (dm)
EE[T]
x E
((iCB( -(a)))()())
[E[T]
< E
Σ
UBCB (at) (at) F(a)))
1E[2]
log T Th
< EE
1E(T] 1Eor
14

---

where the second and last inequalities are obtained from &g. For bounding the last term, we have
E
Σ
log
Σ
Σ
Σ
log T Th,
V
2
[E
ie(d)
(((x((T)((ET((1
Σ
E
E
log T Ti(T - 1)
V
iEId
logT
Σ
Σ
[T((T))
[Ti(T - 1)1
kE(d) rE(n(T))
Tm |T(T [0]-
log T [Ti(T 1)1
Σ
d
iE(d rE(N((T)
T'm logT
(T)
d
iE(d
S log log(Tm/ h/m/dd/// d dmmlogg?
where the first inequality is obtained from ni, [T((T 1)I for E Ti(T), the second equality is obtained from the condition of updates in the algorithm, and the last inequality is obtained from Lemma
Oracle Complexity Bounds. Based Lemma 1 can show that the oracle query complexity bounded by Old log log( Since the epochs for each base arm are updated separately, the adaptivity complexity is also bounded by O(d log log(Tmm/d)).
A.3 e-Approximation Oracle
In this section, we provide a detailed explanation for a-approximation oracle. We focus on the adaptive rare oracle query framework, noting that similar results can be derived for the scheduled framework, which we omit to avoid redundancy. Instead of obtaining the exact solution, the a- approximation oracle, denoted by Og, outputs action of E A satisfying
UCB (at)
max UCB (a) aEA
for a > We investigate the a-regret, which is defined as
Ra (T) E
Σ
ar(a") F(a:)
EE(T]
Algorithm 5 a-approximated Adaptive Rare Oracle Queries for Combinatorial MAB (a- -ROQQ-CMMM
Initialize: T for all i [N]
for / = 1, 2..., do
4: Q:-1
for E [d] s.I. TT(T:)
> 1+ Tm [T( 1)l/d do
7 Te(Ti)
- 0
Updale t- True
Update = True then
+00 Update + False
Play a; and observe feedback y for E at
T((T.) + T(()) U {t} for all i a;
15

---

Theorem With oracle adaptivity and query complexities of Old logTm//d) respectively, Algorithm achieves a a--regret bound of
(T) = (Vmdm mdd T Tog log (og((m//d))
Proof. Here we provide the part that is different from the proof Theorem for the regret follows:
!
We provide a bound
RT =
(af(a") -((a))(((E)
+
Σ [E(T]
(ar(a") F(ox))
[E
< E
Σ -
(md))
CE|T
$ E
LE|T
< E
Σ
(Tr
UCB (at)
((ax))
4E|21
log 1/,ss
$ E
[E[T]
iEae
where the second last inequality is obtained from 0g. The other parts of the proof are the same as those Theorem
A.4 Proof of Theorem 2
From Lemma
show that the event & f114 fi((T)
/ Vr [M], Vi [d] nrd
holds with probability of at least - _. Then by adopting the proof technique in 6 under the event &, we show that Ar, activated arm set for 7-th epoch, always contains optimal arm a* in the following lemma.
Lemma 4 Under E, we can show that for all E [M], a" E Ar.
Proof. This can be shown by induction. Suppose a" E A, for fixed E [M]. Under &, we have F(a) S (UCB (a) and F(a) 2 7 (a) for any E A, Then for any fixed a", for any a Ay, we can show that
UCB 7+1 (a,+1) 2
UCB (a') 2 F(a") LCB T+1
where the first inequality is obtained from the definition of (00 with a" Ar. This implies that
UCB 741 (1 2 max LCB r+1 (a), aEA.
which implies that i a" not eliminated from the elimination condition the T + 1-th epoch. This holds for all E a" so that a" Ar+1. With a" Ao = A. we conclude the induction.
16

---

Under &, we have
1.5 logt
1.5 1.5 tr nrj
R(a")-
S Sr. +a")+2 +2 Σ
77
MOB
(a +2 Σ
SEG
jEat
log 4T nts
log IT nr.j
JEa
JEaL
d'logt+ t TT--1
dllogt
7---1
JEa
jEaL
ty dlog
V [Tr-1]
where the first inequality is obtained from &, the second inequality comes from the fact that a* A from I Lemma 4 and maxagA, ,LCB( (a) S rr ,CBB (a+)) ( from the algorithm, and the third inequality obtained from ny EieT.-1 1 ae) -T>-1//d from the exploration in the algorithm the 1-th epoch.
Finally, we can show that
R(T)
<
E
F(a') -((a)) E
P(E) + E
Σ
F(a") - F(a.) E P(E9)
LET.
M
md T2
E
F(a") - F(a+) E
+
7= TE
M
dlog
TT m
11--1
M
mm d log
t=1
mn JMM
S mv dT log log log(
which concludes the proof for the regret bound.
Oracle Complexity Bounds. Based on the oracle calls in Lines Sines3aane and of Algorithm we observe that each epoch involves at most d independent oracle queries (Line 3) and one sequential oracle query (Line[4). 4). Since the total number of epochs is (log log T), the overall adaptivity complexity is bounded by (log log T), and the query complexity is bounded by Old log log T).
A.5 Proof of Theorem
Let (t) be the value of T..j time t in the algorithm. Then T. (T) represents the number of updates, each update requiring Oracle queries, up to T' from pair of arms i, For the bound of the Oracle queries up T' for each arm, we have the following lemma.
Lemma (Oracle Queries Bound for Each Arm) For (i, E [d] x [d], we always have
Tre (T)) = (log((Tm))
Proof. For i [d] [d], if Ti.j not the last stage for j. it holds that (Tey( > 2 This can be derived from the update condition in the algorithm so that (Te,( 2 (T 1)}. Let
To lom). If 7 2 + 1, for any i E [d] [d], have
[Tr)(T) 2 2- 2 2log(Tm) = Tm.
17

---

Therefore, given the fact that the total number of selected bases over T is at most mT. if To + S Ta (T), there is always most pair of [(,,j,,7 r) for the fixed (i.j) [d] x [d] and for all
E To 1, (T)) This implies that for (š, E [d] [d] s.t. (T)(T)
+ 1, we have
(T) S To + 2, which concludes the proof.
From the above lemma, we can show that the oracle adaptivity complexity and query complexity are bounded by
Σ TT( = Odd log(T'm)).
(i
Let G. = Du, + DrN, I. For the regret bound, we first provide lemmas to define favorable event of concentration bounds.
Lemma 6 (Proposition 1 in 32 (((t)og())) for all E A.
Ler t 2 d(d + 1) log)) (T)/2. With probability at least 1
Ka, pr p1) S fell alla.
From lemma we define event Et,1 flka A. μill S T.11Da,,a|12 Vs
[[d(d
1) log (T)/2), (4 | Va E A), which holds with probability of at least 1 - 1111loog log
Lemma 7 (Proposition 5 in 322 Let t 2 d(d + (T))222)
(T)/2.
With probability at least 1
(og())))))) for all (i,j) E [) x [d]. we have
(u),) - Engl S (
5he
+
(t,(
n 14,(6-))
From the above lemma, we define event E,2 {(Si,((.) Ensl S 7 Mo..i.33
A?
L. E [[d(d + 1) log (T)/21,) V(i.j) E [d] which holds with probability of at least (2,0,))
1- 1ot (t).
Recall Er,(1,) = (1,(1,)) +
5h.
Under & we have Et,( 2 Ens
Re.(i.2)
(
for all (i.j) E [d]2. This implies that G. 2 Gz(z 0) so that |Dz,'alla, 1D7i'allzz, Therefore, under E, = Er, E have Ka, fr - n\ S fell a allza which implies
/ (ECB(a) (a) 2 F(a).
UCB
Under E,, we can show that
D aal = a DT
G.
Ge.(i.))
Σ
(is)eaxa
nell Pig
1 h
h
Σ
3/2
n
(L,)aaxa
(1,))axx
(((())
(t,(1))
Me,j Eis
h2
h4
1
+
3/2
(HJ)aaxa ((,(is)
Ti,(),))
(a)
h
h4
1
3/2
(((())
11,(5-5)
where the first inequality is obtained from E1,()) I Eis + 1 Mee(ed) Egp and the second inequality is obtained from (e,( Ne.j.
5h
under
18

---

For ease of presentation, we define auxiliary variables " Mo, Co and St for each i E [d] and time step E [2] as follows: If the selected action time & newly updated in the algorithm (Update = True), then
pl, Pe.
C. Ct
fi= fc.
Otherwise, if the previously selected action is maintained (Update = False), then
n4,5 14-1 14--8-111
G.
f1
Using these adjusted statistics, we define the UCB-based optimistic reward estimate for any action
#1 (C) (a) (a, (4) 1111,77aaa;
Now we provide bound for the regret as follows:
R(T)
E
Σ
(faa") ((E)))
rEld(d+1) log (T)/2,7)
+ E
Σ
F(a")) ((a)){((
+ +((d))
(ng log (T)/2.7)
E
Σ
(F(a") -(aa))-((a)))) F(a)))((EE
+ +((P)
rEld(d+1) log (12))/2211 (T)/2.1
2N
E
Σ
T (UC (a*) ((()))(((()
+ +
(E[d(d+1) (T))227)
S E
Σ
(UUB - - ((E,)
+ +
rEld(d+1) log (TY)222 (T)/2
fr
Σ
Dij aclo!
log" EE (og (T)
of(at)
1
hh
E
fr
T Σ
+
Σ
+
13/2
jea:
(Ka)
(((i))
E
frie
T
E (TT
Σ
Σ E
1
acAdca
The
13/2
iEld
(i.)) (T') (.,3)
19

---

For bounding the last term, we have
E
ITIT
T
Σ
Σ
E
max aEAsEa The
(((a))
E
Σ
Σ
13/2
(E|d]
(ET..))))))TT.))))
(W.) refn (T) " (((()))
S R
JTII
EEED iEld rEN..(()))TTTT..
Σ
E
max aEdiEo
[Tr,(T -1]
207
E
Σ
E
E
IT 1)
(
(T)
E İTIT
Σ Σ
[Ta(TT]
max aEArEo
(0)
Σ
Σ
(T))(T)
1
[Ti,(T 1)1
[T. 1)|3/2
iE|d rE(T..(T)
(A.) (T)
E
fTiT
T
Σ iEld rE(T..(T))
Σ
4|Tr,(T - 1)
max
Σ
Σ
2T - 1)1
[Ti(T -1)
Tho - 1)/3/2
(K.))(d2 (T)
E
fTiT
T
Σ
(T) maxo +
Σ (T)(T)
aEA
VITrs(T- 1)
iEld
(K.))(d)
E fTiTT T
Σ max of log(m)), aEA
*E(d
where the first inequality obtained from ni,; [T((- 1)], the third inequality is obtained from the condition of updates in the algorithm, and the last inequality is obtained from Lemma [T - 1)1 2 log"(1 (T") from warm-up stage in the algorithm, and large enough T. This concludes the proof with the fact that fr Ollg(TT) when T is large enough.
Oracle Complexity Bounds. Based on Lemma 5 we can show that the oracle query complexity is bounded by Odd log(Tm)).. Since the epochs for each base arm updated separately, the adaptivity complexity is also bounded by Odd lod(Tm))
A.6 Proof of Theorem
From lemma 6 we define event & = {1 fr m}] - fr A.D,,,//l,,Kt allz, Va E A, E [M]} which holds with probability of at least 1 (/(Toog2(T)
From Lemma 7 we define event
& = ((Em,,))) - Eiyl S { ((r,())))
5hy + n)((5))
v(i E [d],, Vr E [M]), which holds + n (....
with probability of least 1 - 1/(Tlog'(T))
Under Ex, have Er,( 2 Σn, for all (i.j) E [d] This implies that G, ž G,(2 0) so that ||D,/aala, < 1| alla, Therefore, under & := E n Eg, we have (a, Pr - 4) S fr a ||
which implies
r (BC 2 F(a) 2 rr (aB Similar to Lemma then have the following lemma.
Lemma Under E, we can show that for all T E [M), E A-.
Proof. This can be shown by induction. Suppose a' E A, for fixed 7 E [M 1]. Under E, we have F(a) S UUC (a) and F(a) > ,LCBB (a) for any A. Then for any fixed i E a", for any A,, we can show that
UCB (a ( r+1 (a" 2 F(a") 2 LLBB
where the first inequality is obtained from the definition of a,41 with a" E Ar. This implies that
.UB (1) 2 max LCB r 741 (a7+1)
r (a), aEA.
20

---

which implies that i E a" is not eliminated from the elimination condition at the T + 1-th epoch. This holds for all E a" so that A
Then for any fixed E a" and j E a² /(), for any E A4, we can show that
r+1 (a 2 r+1 (a") 2 F(a") (.CB(a)) (a),
(1.) UCB
where the first inequality is obtained from the definition of 0++1 with a" E A This implies that
UCB (i-) max r+1 (a oEA'+:
(CP
which implies that i a and j E a"
[i} are not eliminated from the elimination condition the
+ 1-th epoch. This holds for all i E a" and j E a"/ /(i) that a" E Ar+1. With a" E Ao = A. we can conclude the induction.
Under E, we can show that
1| m. alla. = DT,
Gr.(h.))
(i))
(r,(h.)) Ens
n1.
hr
1
+
+
(i.))axa
(T,
(i.))axa
n
(,((5))
(T((1))
3/2
n (
(T,(1.)) Eis
h2
l1
Σ
iEa JEa
(7,(i.5)
(i.))axa
n2
(,(j.))
ni
(.
3/2
n2
(..5))
(a)
h2.
hr
1
+ 3/2
+
(5)
n (T,(1.5)
iEa (1.()
(ax))axa
7,(1.)
(T,(1))
where the first inequality is obtained from E E., S Eng + 1 5hm
+
+ n (.6.))
under
& and the second inequality is obtained from n (7,(1)) S (1r
Then, under E, for t E ( ?.
have
LCB (CB))a))fr F(a")- - -(az)) S 1r
Σ ,a(aa))
h2
ht
1
iE
(1,61.))
(a xa"
n
(((i))
3/2
n2
UCB ((t) + ST.
Σ (ar))
Σ
h2
hr
1
+
sEae
(er(
(R.) X
n²
7.(1.)
n1 (T((i))
3/2
n
7,(15)
(a(a)
h2
2 fr
max aEA,
iEa
(i.()
3/2 (K))Eaxa
ni (T,(i.)
do?(a)
dh?
S fr,
max BEAr
Σ VEa
T (dm?T,-1 log (Tg(3))2/3
T,-1 (T)
(a(a)
S frher V
d max
A.
T,-1
SEa
where the first inequality is obtained from E, the second inequality comes from the fact that a" E Ar-1 from Lemma Mand elimination conditions from the algorithm, and the third inequality is obtained from Nr.(1.) 2 EieT("y 1(i az) Z (Tr-1- (dm2T,- (j a.) 2 (dm?T,-, 2og(3))2/33/4) ////////d2 d for + j from the exploration in the algorithm at the 1-th epoch, and the last inequality obtained from large enough T.
(2/(3 /d and (,,(6)) 2 Eier( 1 E
21

---

Finally, we can show that
M
M
R(T) E
-F(as) 1 F(a") F(at) 18
F(a")
P(E) + E
F(a") - F(as) _ P(E)) + 0
TE
T=
M
md
T + Odd9)
LET
Σ (a) T--1
T FThT
max d
aEA
T--1
iEa
Σ nfrhr
dmax aEA
(2(a)
M STiTT
dmax
Σ [o((a)
aEA
frhr log (T)
d max aEA
Σ of(aT),
which concludes the proof with the fact that fr Ollg(TT) when T is large enough.
Oracle Complexity Bounds. Based on the oracle calls Lines TS 17 and of Algorithm 4
we observe that each epoch involves at most d + de independent oracle queries (Lines 15 16 and two sequential oracle queries (Lines 17 19. Since the total number of epochs M O log T).
the overall adaptivity complexity is bounded by O(log logT)) and the query complexity is bounded by Odd log log T'.
A.7 Rare Oracle Queries for General-Reward CMAB
A.7.1 Adaptive Rare Oracle Queries for General Reward CMAB
We first propose an algorithm (Algorithm for rare oracle queries for general reward CMAB using the adaptive framework as in Algorithm| For E [d]. let (x) be the fraction the observed feedback from arm that is no longer than 0 < x S 1 before time By inspired by [4) for i [d].
we define D,,; to be the distribution whose CDF is, for some constant C' > 0.
max (T,(())
Clntt (0
if S <1
Ex,(r)
if
Then we construct UCB for each action based on D, as follows:
UCB (a) =
(6)
A.7.2 Scheduled Rare Oracle Queries for General Reward CMAB
For e [d], let (z) be the fraction the observed feedback from arm that is no longer than 0 & 1 before epoch r. Then, for some constant C > define D, be the distribution
whose CDF
mmx(fFr
Cha 0}
if < x <
(x((x)
1
if =
and define D,, to be the distribution whose CDF is
F7,(2)) = min(f;,(x)) +
Cla ne.
1}
i <
=
22

---

Algorithm 6 Adaptive Rare Oracle Queries for General-Reward CMAB (AROQ-GR-CMAB)
Init: 7: 1 for all i [d] for f = 1.2... T do
for iE [d] s.I. (T((T)) 7 Ti T((T)) K
2 1
Tm [T(T; 1)l/d do
Update <- True
if U Updaae True then
arg m rt UCB (a) with (
// Oracle Query
Update + False else
L Ot < a:-1
Play aj and observe feedback yt for E at T((T) T((T)) U {t} for all i a2
We construct UCB and LCB for each action based D, and D,, respectively, as follows:
(a) -ENDD [F(xx, a)] and (a) Bya,, [F(x,
Let grid T= = (= 1)..... t=
(t) 7)}, where t, = // and = T' for M > 0. We set
M Olog (T))
Algorithm 7 Scheduled Rare Oracle Queries for General-Reward CMAB (SROQ-GR-CMAB)
Input:
30
for r = 1, M do
31
Update (xx
32
a = argmax DEA, piaa Pr (a) for all E N with
// Oracle Queries
33
NG + (iEN
rr ,CB (4)
(ar 2 max 1t LCB (CBB(a) with
// Oracle Query
34
A, + {a A-
a, = for all i [d/N+}
T, = 1t,1 1
36
for T, do
37
it ((t 1) mod |W+ + 1)-th element in N
(4) Play a and observe feedback Yt, for E de
38
A.8 Proof of Theorem
Let Tt()) be the value of at time t in the algorithm. Then 7, (T') represents the number of updates, each update requiring Oracle queries, up T' from arm i. For a slight abuse notation, we use T((T)) for the set TT(T:) in the algorithm at the last time step T. For the bound of the total Oracle we have
queries up to T, from Lemma
E
(T)
(dloglog([T)
(8)
For of presentation, we FD(a) Ex-D (r(a, X)).
x PA be two probability distributions D and D', respectively, over [0. 1jd. Let F, and F be the CDFs of and P', respectively for i E [d]. Suppose each P. is discrete distribution with finite support.
Lemma (Lemma in 4) P x ... x Ps and F = P' x..
(a) If we have (x) S F((x) for any [d], x [0, 1), then for any a E A, we have (a) 2 (a)
23

---

(b) If we have F((x) [x) I 2; with 2, > forrr any i E [d]. E [0, 11, then for any A. we have (Dr TD(aa 2L Eiea 2x.
Lemma 10
inequality) For i.i.d. samples of Xi...., Xu drawn
from distribution D, let empirical CDF (x) 1/2 E 1(; S x). Then, for any > 0 and any N, we have
sup
Fa - F(x)] 2 < 2exp JEE
2ni 2nd2
From the above lemma, define favorable event & (suPae(o.1) Fi,,,, (x) F.(x)] $
3lus Vs E [1,t] Vi E [d], which holds with probability at least Odd/t²). Recall that 2na.i
( (a) = By~g, a(y.a)).
For case of presentation, we define auxiliary variables D2 and n²,s for i E [d] and time step t E [2] follows: If the selected action time is newly updated the algorithm (Update True), then D' = 2, and n/g, = 7,, Otherwise, if the previously selected action is maintained (Update False), then D' D'_ and n',; 14-1,- Using these adjusted statistics, we define the UCB-based optimistic reward estimate for any action a as
71 JUCB (a) = -E [))
Now we provide bound for the regret as follows:
R(T)= = E
Σ F(a))=((a)))(EE))
+
[E[T]
[E(T]
3 3ln
<
Σ
(F(a") - F(at))
+
sup =c[6._]
[,,(()) Rx(x)) V
[E[T]
tE(T))
iE|d
(liCB( -a)))((a))(
Ld
SE[T]
- E
Σ 1E
FUCB ((.)-
log T Ti
KE
L
(E(T] KEar
24

---

where the second inequality is obtained from (a) in Lemma and the last inequality comes from & and (b) Lemma 9
For bounding the last term, have
log T nh
E
ALY
E
Σ
EE T]
FEaL
E
L
EE iE(d (TT
Σ Σ
log T n/,55
log? T TT(T 1)
$ E
L Σ
Σ
Σ
iEld (ET(()))))TT()
log T
=
E
L
Σ
[T((T)
[T((T - 1)1
KEld rE(T(TT)
Tm 1T((T 1)1
log T
E
L
Σ
d
[T(T - 1)1
(E(d (E(
T TmlogT
E L iE(d
(i(TT
$ I. log log(Tm//)) h /dddmlloo
where the first inequality is obtained from ni,; 2 [T((T 1) for E Ti(T), the second equality is obtained from the condition of updates in the algorithm, and the last inequality is obtained from (8).
Oracle Complexity Bounds. Based on 8 we can show that the oracle query complexity is bounded by log log(Tm/dd). Since the epochs for each base arm updated separately, the adaptivity complexity is also bounded by OOd log log(Tm/d))
A.9 Proof of Theorem
From Lemma
3hn Vr E [M], Vi e 10 we define the event & = (supseto,1) (Fr,(z) F((x)) S V 2n,,;
[d]. Then, similar to Lemma 4 under the event E, we show that A,, activated arm set for 7-th epoch, always contains the optimal arm a*.
Lemma Under E, we can show that for all T E [M], a" E Ar.
Proof. The proof is the same as that of Lemma This can be shown by induction. Suppose a" E Ar for fixed E [M]. Under E, have F(a) < r+1 for any fixed E a", for any a E A,, we can show that
rLCB (a) for any A,. Then CCB (a) and F(a) 2 r,41
UCB (1) ( 7+
UCB (a ((((())) LCB (a), 7+1
(6) where the first inequality is obtained from the definition of a with a" Ar. This implies that
UCB (
LCB T+1 (a), AE
7+1 (a7+1)
which implies that i a" not eliminated from the elimination condition the T + 1-th epoch. This holds for all E a" so that a" Ar+1. With a" Ao = A. we conclude the induction.
25

---

Under &, we have
1.5 T
1.5 log T Bra
F(a*) -((a)) S LCB (r()((a"++ + 21.
2I.
Σ
r
UCB
(a 2L
JEar
jea
Tog
log T
S
+
n
Bnd
JEa
jEaf
dlogg T TT--1
dlogg T
L E
TT--1
jea
SEat
dlogT |--
Tm
where the first inequality is obtained from E, the second inequality comes from the fact that a* e Ar-1 from Lemma 11 and maxaed=-1 17 LCB (a) rr ,LCB (ar") (ar") from the algorithm, and the third
inequality is obtained from nt,i 2 LLET.-, 1 E ax) Z 11/d from the exploration in the
algorithm at the 1-th epoch.
Finally, we can show that
R(T) S
Σ Σ
F(a')
F(a:)
P(E) +E Σ
- -(a')-F(a;)) Ee P(E9)
IET
TET
3 Int
< EE
Σ F(a") F(ar)
+L
P
sup zE|o,1]
Ft,(z) Fi(x) 2 1
21
[E[T] t=1 (
dlog T
Tr Lmm
|T--1
S TTmy / d[T=-1
= Lmnny dMTlog
2 Lmv dT lTg log log(T),
which concludes the proof.
Oracle Complexity Bounds. Based on the oracle calls in Lines 32 and 33 of Algorithm 7 we
observe that each epoch involves at most independent oracle queries (Line 32) and one sequential oracle query (Line 33). Since the total number of epochs is M (log log T). the overall adaptivity complexity is bounded by (loo logT). T), and the query complexity bounded by Old log T)).
A.10 Extension to Continuous Distributions for General Reward Functions
We now consider the setting where each yr. E [0, is drawn from continuous distribution D. In this case, we impose the additional Lipschitz-continuity assumption on the reward function as follows.
Assumption There exists C > such that for any a A and any y, v.v' e [0, we have [r(a, y) - r(a. s/) < Cies y: - -/il-
Here we provide a regret bound for the discretization of Algorithm b and that of Algorithm 7 is omitted due to its redundancy.
Theorem 8 Algorithm with Algorithm achieves regret bound of R(T) Ō(LVmdT)
26

---

Algorithm 8 Discretizations
Set the number of intervals < [CvmT]]
for j = 1 do
0. 11 j= (--) 27
Define interval 1
j= = ,
Invoke Algorithm orr Algorithm| 7 for T rounds with the following modification:
for i do
Upon observing an outcome Vr, E [0, 1], identify [s] such that yr,i E I
Treat the observation 1
Proof. We define D to be the discretized distribution of D. For ease presentation, we use FD(a) Ex=
Lemma 12 (Lemma 7 in 44) For any a E A, we have (Fz(a) - F5(aa $ /
Then, from the above lemma, we have
R(T) E
FD(a") rD(aI)
SE
Σ
ps(a") =g(at)
+ Σ
T
[E|T]
[E(T]
:E(T)
To(a") (s(a))
VmT.
(9)
[E|T]
For the regret bound of the first term in the above, we treat D as the true distribution. By following the proof steps in Theorem we provide a bound for the regret as follows:
E
Fs(aa) =(((a))
1E12
E
(Fz(a") (a)))))((EE)
+
Σ LE(T)
(T - (((o)))((E))
[E[T]
3 In
< E
Σ
(iz(a") - -(((a)))((E))
Σ
sup =E(0.1]
[(((x) - F((x)
EE|T
E
1=1 vE(d
E
Σ
JJB (a") (f)(0)))))))
Ld
1E|2
E
(at -
LE|2
log T ni,s
E
7
[
iEa:
27

---

where the second inequality is obtained from (a) in Lemma and the last inequality comes from & and (b) Lemma 9
For bounding the last term, have
log T n
E
(E(T]
FEar
log T n2e,i
E
L
Σ iE|d (E(x((1))
Σ
E
S
L
Σ
Σ
Σ
log T TT(T 1)
iEld (E)
log T
E
L
Σ
Σ
(T((T)
TT(TT - 1)1
ield [E(
T'm |T(T - 1)
log
E
L
d
[T(T 1)
kEld TE(T((T)
Tmllgg
E L REId
(T)
< L log log(Tm/d)) / dm' dmm log
where the first inequality is obtained from n',, 2 [Ti(T - 1) for E Ti(T), the second equality is obtained from the condition updates in the algorithm, and the last inequality obtained from (8) This concludes the proof with (9)
A.11 Additional Experiments
Here, we present additional experimental results for the covariance-adaptive algorithms and for the setting with general reward function. The following results confirm that, consistent with the observa- tions the worst-case linear reward setting (Section[)). our algorithms achieve significantly reduced oracle usage and improved computational efficiency, while maintaining tight regret performance.
A.11.1 Covariance-adaptive
Here, we present experiments (Figure 3) on eevariance-daapien frameworks under lincar reward settings. The mean reward of each base anm is independently sampled from uniform distribution over [0, 1], with
10 base arms and cardinality constraint m = 3. The reward noise correlated according to x d positive semi-definite covariance matrix Σ, constructed as AA La with normalization, where A E Rdxd is randomly generated matrix. The stochastic rewards are then sampled from a multivariate Gaussian distribution with the specified mean vector and covariance matrix Σ.
A.11.2 General Reward
Next, we present experiments (Figure on general (non-linear) reward settings with 5 and 2. For each arm E [d]. the reward is sampled from discrete distribution supported on the finite set (0.2, 0.4, 0.6, 0.8, 1}. The probability distribution for each arm is generated as follows: one value is randomly assigned to each arm. Then the value is assigned a large probability mass of 0.99, while the remaining values share the remaining 0.01 probability mass equally. The reward for an action is defined as the square root of the sum of the sampled rewards from the selected arms.
28

---

Cursulativve
Cumulative Grade Query Complexity over Time
10
Cumulative Regret over Time
1.0
O1SUCC-C
peapevitty Comp cuuttty
0.0
Qvery Complcatty
6.8
SRDO-C-WAB (Np1)
AROQ-G-CMA
Comukttee
0.5-
Camuuaatio
0.6
0.4-
OLS-UCB-C
ARDO C-CMA (Agg3]
(Aig4)
0-
4000 6000
8000
10000
0
2000
4000
6000
8000
10000
Time
Time!
Timw t
(a)
(c)
Comparison
Adaptivity
Adaphaat Comoleerty
9500
0500
ThaN
102
500
500
4400 C CAA
ShO0 CRAS
ARD0 C-0RA5
3R00 CHAAS
OLS
ARUO CKA5
5400 C
OLS
Algel
(A]44
Aggnnthmm
Alporinmx
Algorinma
(d)
(f)
Figure 3: Experimental results for covariance-adaptivig under linear reward with d == 10 and (a) cumulative oracle adaptivity complexity, (b) cumulative oracle query complexity, (c) regret, (d) runtime, (e) overall oracle adaptivity complexity, and (f) overall oracle query complexity of algorithms.
162 Cumulative Regret
Cumulative Gracie Adaptivity Complasity ouer Time
Cumulative Dracie Quary Complesity over Time
2.0
1013
2.0
SDCS
7daptteity Campleoty tort
16:00 (a CMAB (Mb))
1800 GI/ORAS (Ago)
Query Comoleekky
1.5
1.5-
E100
1.0
1.0
AROQ-GI-CMAB (Alg8)
BROQ-GR-CMAB (Alg7)
0.0
300
1000
1500
2050
500
1000
1500
2000
500
1000
1500
2000
Time7
Time
(a)
(b)
Buntine
20:00
Gracle Adaptivity Complesity
Total Orade Complexhty
Burtime (recon00
60
Adaelisity Comptestty
Thte Quary Camptartty
30.
1800
X200
1.0
1R0G-GR-CMA
SR00-6R-CMW
SDXI
SR00-GB-CWA
50EB
5RDO-GREEWA
(Al
(A
(Alps)
(Aip7)
(d)
(e)
(f)
Figure 4: Experimental results for non non-linear reward with d 5 and m = 2: (a) cumulative oracle adaptivity complexity, (b) cumulative oracle query complexity, (c) regret, (d) runtime, (c) overall oracle adaptivity complexity, and (f) overall oracle query complexity of algorithms.
29

---

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 explain our contributions and scope in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not 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: We compare our algorithms to the previous methods. Please see Table [ lines 141 145, 217 223, and 262 265.
Guidelines:
The answer NA means that the paper has no 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 their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
30

---

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

---

Answer: [Yes]
Justification:
The paper provides a link to the source code the experimental section.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/
stipaiisssooooioyyyo. for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The paper provides details to understand and reproduce the experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The experimental results include appropriate error bars to indicate statistical variation across repeated trials.
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 capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
32

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: The experiments are simple and do not require significant computational resources.
Guidelines:
The answer NA means that the paper does not 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 as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http://wwrrg..coooaaaaccccccccca
Answer: [Yes]
Justification: The research does not involve human subjects, sensitive data, or applications with foresecable negative socictal impact.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there a 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: [Yes]
Justification: Please see Section 7
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
33

---

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:
This work is primarily theoretical.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This work is primarily theoretical.
Guidelines:
The answer NA means that the paper does not 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.
34

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This work is primarily theoretical.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This work is primarily theoretical.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
This work is primarily theoretical.
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
35

---

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: LLMs were not used in the development of core methods; they were used only for improving writing.
Guidelines:
The answer NA means that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
36


Reviews:
[{"review_id": "5hux48cTCV", "reviewer": "Reviewer_RoU1", "summary": "The paper considers the problem of minimizing the queries to an oracle to find the optimal arm to play at every round in a combinatorial semi-bandit setup. The oracle calls can be costly as the oracle needs to find the optimal arm from a set which is exponentially large in the number of base arms. For this setup, the authors use an interesting insight where the confidence intervals of the arms rewards do not change by $O(1/\\sqrt{\\mathcal{T}_i}(\\tau_i))$ where $\\mathcal{T}_i(\\tau_i)$ is the number of times arm $i$ is played in epoch $\\tau_i$ and the regret is upper bounded by the length of the next epoch times the gap in the current round. With this insight, the authors are able to bound the calls to the computation oracle to switch the policy or the optimal arm to play in the epoch, while still maintaining low regret. The authors then extend the findings to parallelize oracle calls for each base arms and further reduce the adaptive calls.", "questions": "None", "limitations": "None", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. The use of bounding the algorithm regret by the confidence interval gaps of previous round for combinatorial bandits is interesting.\n\n2. The parallelization of oracle calls to further reduce policy switches is interesting and novel.\n\n\nWeakness:\n\n1. Algorithm 2 takes in the pre-determined sequence of policy updates. What happens if the pre-determined sequence is mis-configured? Ideally, the algorithm should determine the sequence.\n\n2. Weak evaluations: Authors must discuss the findings of the evaluation results in details and must elaborate why the algorithms behave as they do. Also, in the appendix, new algorithms are introduced without description. It is a good practice to remind the reader what the baseline algorithms are and how do they work.\n\n3. I think the authors have incorrect references. The proof of Theorem 1 maps to the proof of Theorem 2.", "was_revised": true, "final_justification": "Authors have added details regarding experiment evaluations which was my major criticism.", "rebuttal": "We sincerely thank the reviewer for the thoughtful comments. Below, we provide point-by-point responses to each one.\n\n\n$\\bullet$ **Algorithm 2 takes in the pre-determined sequence of policy updates.**\n\n\n\n**Response:**  You are correct that Algorithm 2 relies on a pre-determined sequence of policy updates. This design choice is intentional and central to our goal of reducing oracle adaptivity complexity: it enables synchronized oracle queries that further reduce adaptivity complexity, even beyond what is achieved by Algorithm 1. Reducing oracle adaptivity is essential to reduce computation cost, and using pre-scheduled, infrequent updates aligns with prior research on batched bandit algorithms [14, 19], which inspired our framework as discussed in the main text.\n\nIn practice, a fixed update schedule is rarely a significant limitation. In many real-world applications, computational budgets and synchronization constraints are known in advance, making it natural to plan update schedules accordingly. Moreover, as shown in Figures 2, 3, and 4, our approach with synchronized updates achieves the best runtime performance compared to other algorithms.\n\nDeveloping an adaptive version of the synchronized update scheme could be an interesting direction for future research. We will include this discussion in the final version.\n\n\n\n\n$\\bullet$ **Authors must discuss the findings of the evaluation results in details and must elaborate why the algorithms behave as they do.**\n \n**Response:** Thank you for your helpful feedback. We agree that interpreting evaluation results is important, and we are happy to elaborate further.\n\nAs predicted by our theoretical analysis, the proposed algorithms significantly reduce oracle complexity through rare update policies. This is clearly demonstrated in Figure 2(a) and 2(b), where the oracle query and adaptivity complexities of baseline methods grow linearly with time, whereas our algorithms exhibit sublinear growth. This results in substantial computational savings, as shown by the faster runtime in Figure 2(d), and reduced total oracle usage in Figures 2(e) and 2(f).\n\nAs expected, the infrequent updates result in slightly higher regret in the early rounds (Figure 2(c)). However, as more information is accumulated, the performance of our algorithms improves and eventually approaches that of the baseline, while maintaining significantly better oracle efficiency. This improvement occurs as the cumulative information gained over time mitigates the impact of rare updates. Similar trends are also observed in the covariance-dependent and general reward settings (Appendix B.11).\n\nWe will clarify these points and expand the discussion in the final version to better guide the reader through the observed behavior.\n\n\n\n$\\bullet$ **In the appendix, new algorithms are introduced without description.**\n\n**Response:**  Thank you for your comments. We clarify that each algorithm introduced in the appendix is referenced and motivated in the main text.\n\nSpecifically, Algorithm 5 in Appendix B is introduced in connection with the discussion of $\\alpha$-approximation oracles in the last paragraph of Section 3.1 of the main text (Lines 147-154). Algorithms 6 and 7 in Appendix B correspond to our oracle-efficient methods for the general reward setting, as indicated in Section 5 of the main text (Lines 255-258). Furthermore, Algorithm 8 in Appendix B formalizes our extension from discrete to continuous reward distributions, which is referenced in footnote 2 of Section 5.\n\nWe will make these cross-references more explicit in the final version to improve clarity and readability.\n\n\n\n$\\bullet$ **It is a good practice to remind the reader what the baseline algorithms are and how do they work.**\n\n**Response:** Thank you for your suggestion. Regarding baselines, each representing the **state-of-the-art** in its respective setting, we provide a brief summary here:\n\n- *For the worst-case linear reward setting*, CUCB [6, 16]   serves as our benchmark. It uses a standard UCB strategy by constructing upper confidence bounds for each base arm and summing them over actions.\n\n- *For the covariance-dependent setting*, we use OLS-UCB-C [26] as a benchmark, which is a covariance-adaptive algorithm that estimates the noise structure online and selects actions optimistically based on this estimation.\n\n- *For the general reward setting*, SDCB [5] is the benchmark. It estimates the distributions of the reward variables and constructs stochastically dominant confidence bounds for action selection.\n\nA key difference is that all baseline methods require an oracle call at every round, whereas our algorithms significantly reduce oracle usage while maintaining competitive regret. We will clarify these baselines and their connections to our methods in our final version.\n\n\n$\\bullet$ **I think the authors have incorrect references. The proof of Theorem 1 maps to the proof of Theorem 2.**\n\n\n**Response:** Thank you for pointing this out. You are correct. The references to the appendix for the proofs of Theorems 1 and 2 were mistakenly interchanged. We will revise the text to ensure that each theorem correctly points to its corresponding appendix section.\n\n---\n**Overall**: We sincerely appreciate the reviewer’s constructive feedback, which has helped us clarify and improve our work. We hope that the responses and clarifications above address the concerns raised, and we would be grateful if the reviewer would consider them in their final evaluation. We would be happy to provide further clarifications if needed."}, {"review_id": "EUz5Wr9FSB", "reviewer": "Reviewer_LFor", "summary": "This paper studies the **combinatorial semi-bandit** problem, a generalization of the classical multi-armed bandit (MAB) framework in which an agent selects a subset of base arms and receives individual feedback for each selected arm. A major bottleneck in this setting is the **high computational cost of solving the underlying combinatorial optimization problem**, which is often NP-hard. Existing algorithms typically assume access to an **oracle** that must be queried at every round, resulting in high adaptivity and query complexity.\n\nTo address this, the authors propose two novel **oracle-efficient algorithmic frameworks** that significantly reduce oracle usage while retaining strong theoretical guarantees:\n\n1. **Adaptive Rare Oracle Queries (AROQ)** – adaptively schedules oracle queries to reduce invocation frequency.\n2. **Synchronized Rare Oracle Queries (SROQ)** – synchronizes and batches oracle queries at fixed epochs, allowing for parallelism and even lower adaptivity.\n\nThe frameworks are instantiated and analyzed under three reward models:\n\n- Worst-case linear rewards,\n- Covariance-adaptive linear rewards,\n- General non-linear reward models.\n\nTheoretical results show that the proposed algorithms **reduce oracle usage from linear to (doubly) logarithmic** in time $T$, while achieving near-optimal regret bounds. These results are supported by empirical evaluations on synthetic datasets.", "questions": "Please comment on or discuss the above weakness points.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### **Strengths**\n\n1. **Addresses a Critical Practical Challenge**: The work tackles the key limitation of **excessive oracle invocation** in combinatorial semi-bandits, which severely limits scalability. The paper clearly identifies this as a computational bottleneck and proposes a principled solution.\n2. **Novel Oracle-Efficient Frameworks**: The proposed **AROQ** and **SROQ** frameworks represent an important methodological innovation. While adaptive querying has been explored in other bandit settings, this is the first work (to the authors’ knowledge) to explicitly target **oracle efficiency** in the **combinatorial semi-bandit** setting. The two approaches also offer flexibility: AROQ is simple and adaptive, while SROQ supports **parallelization** via synchronized updates.\n3. **Strong and General Theoretical Results**: The paper provides regret guarantees that match known lower bounds (up to logarithmic factors), while simultaneously reducing oracle usage:\n    - For **worst-case linear rewards**, the AROQ-CMAB algorithm achieves regret $\\tilde{O} (\\sqrt{mdT})$ with oracle query complexity $O(d \\log \\log(Tm/d))$, a significant improvement over the standard $\\Theta(T)$ baseline.\n    - The SROQ-CMAB algorithm further reduces **oracle adaptivity** to $\\Theta(\\log \\log T)$, while maintaining the same query complexity.\n    - For **covariance-adaptive linear rewards**, AROQ-C-CMAB achieves query complexity $O(d^2 \\log(Tm))$, and SROQ-C-CMAB maintains $\\Theta(\\log \\log T)$ adaptivity.\n    - For **general reward models**, AROQ-GR-CMAB achieves $O(d \\log \\log(Tm/d))$ query complexity and SROQ-GR-CMAB again attains $\\Theta(\\log \\log T)$ adaptivity.\n    \n    These results are substantial as they show the feasibility of low-adaptivity learning even in high-dimensional, structured settings.\n    \n4. **Broad Applicability and Model Generality**: The proposed methods are not limited to a specific reward structure. Extensions to **covariance-aware** and **general non-linear** reward models greatly enhance the framework’s **practical scope**, making it applicable to domains like recommender systems, online resource allocation, and network routing.\n\n\n---\n\n### **Weaknesses / Limitations**\n\n1. **Gap-Dependent Regret Bounds Not Discussed**: The paper only presents **gap-free** regret bounds. It would strengthen the contribution to investigate whether the same frameworks can be extended to derive **gap-dependent** bounds, which often provide **tighter** and **problem-dependent** regret characterizations, especially in practical settings.\n2. **Experimental Evaluation is Limited**: The empirical results are based solely on **small-scale synthetic datasets**. There is no validation on **real-world datasets**, which weakens the practical evaluation. It would be valuable to include experiments on datasets from real applications (e.g., recommendation, online ads, network routing) to demonstrate scalability and generalization.\n3. **Minor Presentation Issues**:\n    - In **line 140**, the proof of **Theorem 1** is said to be in Appendix B.2, but the citation appears to be off.\n    - In **line 175**, the proof of **Theorem 2** is listed incorrectly; it should refer to Appendix B.4.\n    - In **line 174**, the adaptivity complexity uses $\\Theta(\\log \\log T)$; However, there is no lower bound showing lower bound results.", "was_revised": true, "final_justification": "I believe this paper is solid and is valuable for advancing the field of efficient combinatorial MAB, so I vote for acceptance of the current paper.", "rebuttal": "We sincerely thank the reviewer for the thoughtful comments. Below, we provide point-by-point responses to each one.\n\n$\\bullet$ **Discussion on Gap-Dependent Regret Bounds**\n\n\n**Response:** Thank you for your insightful comment. In this work, we focused on the gap-free setting as a foundational step toward oracle-efficient algorithms for combinatorial semi-bandits. Extending our frameworks to derive gap-dependent regret bounds is indeed a valuable direction for future work.\n\nOne natural approach would be to incorporate elimination-based strategies, as commonly used in the batched multi-armed bandit literature [14]. However, in the combinatorial setting, elimination becomes more involved due to the need to construct representative actions for each base arm, as described in Line 3 of Algorithm 2. These representative actions allow us to eliminate large sets of suboptimal actions by targeting individual suboptimal base arms. However, pulling representative actions does not guarantee a uniform number of base-arm observations across epochs. This mismatch can introduce inefficiencies and prevent standard elimination techniques from achieving tight gap-dependent bounds, thereby limiting their direct applicability in our combinatorial setting.\n\nNonetheless, we consider the development of gap-dependent oracle-efficient algorithms an exciting and important direction for future work.\n\n\n$\\bullet$ **There is no validation on real-world datasets.**\n\n**Response:** Thank you for the thoughtful comment. We appreciate the importance of real-world validation, particularly in application-driven domains. However, in the bandit literature, particularly in combinatorial and semi-bandit settings,  the primary focus is on theoretical contributions [6, 5, 16, 10, 20, 26]. Even when experiments are included, they are typically conducted on controlled synthetic environments to precisely validate regret behavior and algorithmic properties.\n\nOur main objective in this work is to investigate oracle efficiency in combinatorial semi-bandits from a theoretical standpoint. Accordingly, our synthetic experiments are conducted to support and illustrate the theoretical guarantees, in line with standard practice in the literature.\n\nWhile real-world datasets are outside the scope of this work, we believe that incorporating domain-inspired structures (e.g., recommendation or routing) could be an interesting extension for future empirical validation.\n\n$\\bullet$ **Minor Presentation Issues: In line 140, the proof of Theorem 1 is said to be in Appendix B.2, but the citation appears to be off. In line 175, the proof of Theorem 2 is listed incorrectly; it should refer to Appendix B.4.**\n\n**Response:**\nThank you for your helpful comments. You are correct - the appendix references for the proofs of Theorems 1 and 2 were mistakenly interchanged. We will correct these citations to ensure that each theorem properly points to its corresponding appendix section.\n\n\n\n$\\bullet$ **Minor Presentation Issues: In line 174, the adaptivity complexity uses  $\\Theta(\\log\\log T)$; However, there is no lower bound showing lower bound results.**\n\n**Response:** Thank you for pointing this out. To clarify, the oracle adaptivity complexity of $\\Theta(\\log\\log T)$ in Theorem 2 is not derived from a lower-bound analysis, but rather corresponds to the *explicit number of synchronized update steps* used by Algorithm 2. Specifically, the algorithm sets the number of updates to $M = \\Theta(\\log\\log T)$, as stated in Section 3.2 (Lines 170-173). As shown in Lines 763-766 of the appendix, since each update requires a round of oracle queries, the total adaptivity complexity directly follows from this setting of $M$. For a more detailed explanation regarding synchronized updates, please refer to Appendix B.1.\n\nWe will revise the main text to better explain this connection and avoid confusion regarding the interpretation of this complexity term."}, {"review_id": "wacZIguFTj", "reviewer": "Reviewer_nCut", "summary": "In this work, the authors consider the combinatorial semi-bandits under the spectrum of computation complexity. \nPrecisely, they consider a problem where at each round, a learner has to choose at most $m$ out of the $d$ available arms to play, and then observes a stochastic reward $y_i$ for each of the individual arms $i$ that were selected. These rewards are then combined into the global reward received by the learner. They mainly focus on the case where the reward function is a linear function of the arms ie $r(a_t, y_t) = <a, y_t>$ where $a_t$ is the binary vector indicating which of the $d$ arms are picked. (they also later generalize that notion to reward functions that are monotonous).\nWhen the learner can make as many queries as they want, the problem is fairly well understood (see [16] in the authors references) where at each round of the game the learner can choose the subset of arms to play freely and [16] already provides a tight-up-to-log-factors regret bound of order $ O (\\sqrt{mdT \\log T})$ using the current paper's notations. The novelty of this work is that the authors propose novel algorithms that reduce the query complexity.\n\nThey consider two measures: adaptability complexity, where the learner essentially limits the number of rounds where the algorithm queries an optimisation oracle (several queries can happen in parallel and still count as 1) , and the query complexity where every single query is counted instead.\n\nThe authors propose two algorithms tailored for each of these measures, and then they provide a regret analysis as well as both query complexity measures for both algorithms.\n\nThe first algorithm, AROQ - CMAB achieves a $O( \\sqrt{mdT \\log T} \\log\\log(Tm/d))$ regret bound (which is only a $\\log\\log$ term over the bound of [16] while reducing the query complexity to $O(d\\log\\log(Tm/d))$ for both measures.\nThe second algorithm reduces the complexity further by removing the $d$ dependency of the total number of arms, but comes at the cost of a multiplicative $\\sqrt m$ factor in the regret bound.\n\nThe authors provide detailed proofs in the appendix for all their results and experiments that compare the performance (both in regret and query cost) of their algorithm vs the non-query efficient baselines.", "questions": "See weaknesses:\nIs there a reason why you don't also propose the regret bounds also expressed in a problem-dependent $\\log T/\\Delta$ type of regret?", "limitations": "yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "This paper takes the problem of combinatorial bandits, which appears well understood and tackles the problem of query complexity in a new way. Their results seem to indicate that they would be useful in practice, as a big limitation of combinatorial semi-bandit problems is that the arm selection is an NP-hard problem, which can be very computationally expensive. While previous approaches might have considered using approximation algorithms for this optimisation, the authors' approach goes in a different direction of reducing the number of queries to this oracle rather than decreasing the quality (and complexity cost) of the oracle.\n\nThe paper is well written, the results are intuitive and the algorithms simple, which should make them easy to apply in practice.\n\nAs a potential weakness, it would be interesting to also get log-type regret bounds for this algorithm (that depend on sub-optimality gaps). \nSome parts of the experiments (at least their description) have to be reworked, but I believe that this is relatively easily fixable.\n\nIn section 6, why do you use the algorithm of [6] in your baseline when the algorithm of [16] achieves better performance?\n(Note that the algorithm of [6] is called CUCB, and CMAB is just the name of the problem.) This doesn't make for a fair comparison.\nIt would be interesting to take a slightly larger time horizon to compare the methods better, as your AROQ-CMAB has a better upper bound than CUCB when $m$ is large enough. \nFor the experiments in the appendix, it is even less clear which algorithms you are talking about. If the readers are not very familiar with the literature on these extensions of CMAB, they won't know where these algorithms are from.\n\nIf the time and space permit in the final version of the paper, it would be interesting to have different experiment ratios of $d$ and $m$ to get a better picture of the trade-offs (in particular, the query-cost vs regret between your two methods).", "was_revised": true, "final_justification": "I maintain my score and believe the paper should be accepted. The paper is interesting, and the comments mainly regarded the structure and clarity of the paper, which I am confident will be appropriately addressed in the final version.", "rebuttal": "We sincerely thank the reviewer for the thoughtful comments. Below, we provide point-by-point responses to each one.\n\n\n$\\bullet$ **It would be interesting to also get log-type regret bounds for this algorithm.**\n\n**Response:** Thank you for your insightful comment. In this work, we focused on the gap-free setting as a foundational step toward oracle-efficient algorithms for combinatorial semi-bandits. Extending our frameworks to derive gap-dependent regret bounds is indeed a valuable direction for future work.\n\nOne natural approach would be to incorporate elimination-based strategies, as commonly used in the batched multi-armed bandit literature [14]. However, in the combinatorial setting, elimination becomes more involved due to the need to construct representative actions for each base arm, as described in Line 3 of Algorithm 2. These representative actions allow us to eliminate large sets of suboptimal actions by targeting individual suboptimal base arms. However, pulling representative actions does not guarantee a uniform number of base-arm observations across epochs. This mismatch can introduce inefficiencies and prevent standard elimination techniques from achieving tight gap-dependent bounds, thereby limiting their direct applicability in our combinatorial setting. \n\nNevertheless, we agree that developing gap-dependent variants within our oracle-efficient framework is a promising and important direction for future research.\n\n\n\n$\\bullet$ **In section 6, why do you use the algorithm of [6] in your baseline when the algorithm of [16] achieves better performance? (Note that the algorithm of [6] is called CUCB, and CMAB is just the name of the problem.) This doesn't make for a fair comparison. It would be interesting to take a slightly larger time horizon to compare the methods better, as your AROQ-CMAB has a better upper bound than CUCB when \n is large enough.**\n\n**Response:** Thank you for pointing this out. You are absolutely right; we should refer to the algorithm from [6] as CUCB, not CMAB, since CMAB refers to the problem setting rather than the algorithm itself. We will revise the terminology accordingly in the final version.\n\nRegarding the choice of baseline, all benchmark algorithms used in our experiments represent the state-of-the-art for each respective setting. For the linear reward setting,\n both [6] and [16] analyze the same CUCB algorithm. In fact, [16] refers to it as CombUCB1 (see the second paragraph of their introduction), but the algorithm remains unchanged. This is why we use the same name for the algorithm in both [6] and [16] in Table 1. The main difference lies in the analysis: [16] provides a tighter bound than that in [6], establishing a near-optimal regret of $\\widetilde{O}(\\sqrt{mdT})$. In our work, AROC-CMAB (Algorithm 1) achieves the same near-optimal regret order (up to logarithmic factors), while significantly reducing oracle complexity -- which is our primary focus.\n\n\nWe agree that evaluating longer horizons could further highlight the benefits of our algorithm.\n\nWe will revise the terminology, clarify our choice of benchmarks, and elaborate on additional experiments in the final version.\n\n\n\n$\\bullet$ **For the experiments in the appendix, it is even less clear which algorithms you are talking about. If the readers are not very familiar with the literature on these extensions of CMAB, they won't know where these algorithms are from.**\n\n**Response:** Thank you for the helpful comment. We agree that the appendix could be made clearer for readers who may not be deeply familiar with the literature on CMAB extensions. Regarding baselines, each representing the state of the art in its respective setting, we provide a brief summary here:\n\n- *Worst-case linear reward setting*: We use CUCB [6, 16] as the benchmark, which applies a standard UCB strategy by computing confidence bounds for each base arm and summing them over the selected actions. This algorithm was introduced in [6] and further analyzed in [16].\n\n- *Covariance-dependent setting*: We use OLS-UCB-C [26], a covariance-adaptive algorithm that estimates the noise structure online and selects actions optimistically based on this estimation.\n\n- *General reward setting*: We use SDCB [5], which estimates the reward distributions of individual arms and constructs stochastically dominant confidence bounds for action selection.\n\nWe will revise the appendix in the final version to clearly reference the sources of these algorithms and provide brief descriptions to help guide the reader.\n\n$\\bullet$ **If the time and space permit in the final version of the paper, it would be interesting to have different experiment ratios of $d$\n and $m$ \n to get a better picture of the trade-offs (in particular, the query-cost vs regret between your two methods).**\n\n**Response:** Thank you for the constructive suggestion. We appreciate your point about exploring different ratios of $d$ (number of base arms) and $m$ (action size) to better understand the trade-offs between query cost and regret.\n\nWe agree that varying these parameters could reveal interesting regime-dependent behaviors between our two algorithms. In particular, increasing $m$ may widen the regret gap between the methods, while increasing $d$ may amplify differences in oracle adaptivity complexity.\n\nFor example, in additional experiments when increasing $d$ from 20 to 30, the synchronized algorithm of SROQ-CMAB (Algorithm 2) demonstrated a substantial advantage in oracle adaptivity complexity. The total adaptivity complexities were: SROQ-CMAB (Algorithm 2): 6, ARQO-CMAB (Algorithm 1): 73, and CUCB: 19,999 -- reflecting the theoretical improvements achieved by the synchronized update mechanism.\n\n\nWhen we increased $m$ from 3 to 5, the regret of SROQ-CMAB  became much larger than that of AROQ-CMAB  and CUCB. Specifically, the cumulative regret at time $T$ was: SROQ-CMAB: 1140, ARQO-CMAB: 678, and CUCB: 659 -- consistent with our theoretical result that the synchronized version incurs an additional $\\sqrt{m}$ factor in regret.\n\n\n\nWe will add such an ablation study in the final version."}]

Author rebuttal:

Meta-review: The authors study the combinatorial bandit problem with semi-bandit feedback. They demonstrate the existence of an algorithm that achieves a near-optimal minimax regret bound while only requiring a number of argmax oracle calls that scales like loglog(T). This is significant because some combinatorial optimizations made not be efficient, thus making it desirable to minimize the number of calls. The reviewers found the algorithm design to be novel and the results to be a substantial contribution to the area.
Decision: Accept (poster)