Combinatorial Multi-armed Bandits: Arm Selection via Group Testing
Authors: Arpan Mukherjee
Shashanka Ubaru
Keerthiram Murugesan
Karthikeyan Shanmugam
Ali Tajer
Venue: Accepted by TMLR ()

Abstract: This paper considers the problem of combinatorial multi-armed bandits with semi-bandit feedback and a cardinality constraint on the super-arm size. Existing algorithms for solving this problem typically involve two key sub-routines: (1) a *parameter estimation* routine that sequentially estimates a set of base-arm parameters, and (2) a *super-arm selection* policy for selecting a subset of base arms deemed optimal based on these parameters. State-of-the-art algorithms assume access to an *exact* oracle for super-arm selection with unbounded computational power. At each instance, this oracle evaluates a list of score functions, the number of which grows as low as linearly and as high as exponentially with the number of arms. This can be prohibitive in the regime of a large number of arms. This paper introduces a novel realistic alternative to the perfect oracle. This algorithm uses a combination of *group-testing* for selecting the super arms and *quantized* Thompson sampling for parameter estimation. Under a general separability assumption on the reward function, the proposed algorithm reduces the complexity of the super-arm-selection oracle to be *logarithmic* in the number of base arms while achieving the same regret order as the state-of-the-art algorithms that use exact oracles. This translates to *at least an exponential* reduction in complexity compared to the oracle-based approaches.

Published in Transactions on Machine Learning Research (06/2025)
Combinatorial Multi-armed Bandits: Arm Selection via Group Testing
Arpan Mukherjee
a.mubberjee@@mppriilccccco
Deportment of Electrical and Electronic Engineering Imperial College London
Shashanka Ubaru
shashanka. wwwruuubb.rr...ooomm com
IBM Research
Keerthiram Murugesan 1BM Research
keerthiram htt.://mmm..mmmmggeaaea...ommmmm
Karthikeyan Shanmugam'
IBM Research
Ali Tajer
tajerGecserrpi.c edu
Deportment of Electrical, Computer and Systems Engineering Renssclacr Polytechnic Institute
Reviewed on OpenReview: http:s//pppmeeeeeeerrr////ommotp
Abstract
This paper addresses the problem of combinatorial multi-armed bandits with semi-bandit feedback and a cardinality constraint on the size of the super-arm. Existing algorithms for solving this problem typically involve two key sub-routines: (1) a parameter estimation routine that sequentially estimates set of base-arm parameters, and (2) super-arm selection policy for selecting subset of base arms deemed optimal based these parameters. State-of-the-aal algorithms assume access to evact oracle for super-arm selection with unbounded computational power. At each instance, this oracle evaluates list of score functions, the number of which grows as low as linearly and as high as exponentially with the number of arms. This can be prohibitive in the regime of a large number arms. This paper introduces a novel realistic alternative to the perfect oracle. This algorithm uses a combination of group-testing for selecting the super arms and quantized Thompson sampling for parameter estimation. Under general separability assumption the reward function, the proposed algorithm reduces the complexity of the super-arm- seleecton oracle to be logarithmic in the number of base arms while achicving the same regret order as the state-of-the-art algorithms that use exact oracles. This translates to at least an exponential reduction in complexity compared to the oracle-based approaches.
1 Introduction
The combinatorial multi-armed bandit (CMAB) problem a generalization the stochastic multi-armed bandit problem, in which there a set of base arms and a learner selects a subset of them at each round. Such
"This research was partially conducted during the author's internship at IBM Research.
The author's contrihution was when the author was part IBM Research. The author is currently with Google Deepmind India, Bangalore.
1

---

Published in Transactions on Machine Learning Research (06/2025)
sets of base arms are called super-arms, and the set of all possible super-arms constitutes the action space of
the learner (Chen et al. 2013 Combes et al. 2015 Chen et al.
201 6a by Wang & Chen 2017
Perrault 2022).
Bandit versus semi-bandit feedback. CMABs can be broadly divided into two settings according to the level of feedback a learner receives in response to its actions: the bandit and the semi-bandit feedback settings. In the bandit feedback setting, the learner pulls a super-arm and observes the aggregate reward value generated by the selected super-arm Nie ct al. (2022): | Jia ct al. (2019). On the other hand, in the semi-bandit leedback setting, in addition to the aggregale reward, the learner has access to set of stochastic observations generated by the individual arms that constitute the selected super arm (Chen et al. 2016a Wang & Chen 2018). This paper focuses on semi-bandit foedback and aims to minimize the average cumulative regret in CMABs under this feedback model. The CMAB model is assumed to belong to the class of Bernoulli bandits.
UCB versus Thompson sampling. Regret minimization algorithms for CMABs with semi-bandit feedback consist of two key sub-routines: an estimation routine and a super-arm selection routine. The estimation routine aims to form reliable estimates of the unknown parameters of the base arms. The super-arm selection routine specifies the sequential selection of the super-arms over time. Super-arm selections rely on the estimates formed by the cstimation routine, and there is a wide range of arm-sclection rules based on the upper confidence bound (UCB) principle (Chen el al.] 2013 Kvelon et al. 2015 Combes et al. 2015 Chen et al., 2016a) or Thompson sampling (TS) (Wang & Chen 2018 Perrault et al., 2021). Recent studies demonstrate that the TS-based approaches are more efficient and empirically outperform the UCB-based
counterparts. Specifically, the combinatorial Thompson sampling (CTS) algorithm in (Wang & Chen 2018 adopts posterior sampling estimator for the bandit. mean values, and uses an oracle that perfectly determines the set of super-arms that are optimal for the estimated means. Under such access to an exact oracle, the studics in (Wang & Chen 2018) and (Perrault et al., 2021) establish that the CTS algorithm achieves an order-wise optimal regret of O log Tog where m denotes the number of base arms, T the horizon, and A specifies the minimum expected reward gap between an optimal super-arm and any other non-optimal super-arm. (Merlis& & Mannor 2019 Liu et al. 2022) investigate the CMAB problem in the batched setting.
Furthermore, (Merlis& & Mannor 2020 provides tight lower bounds for CMABs.
Oracle complexity. Accossing an exact oracle is often computationally prohibitive. In this paper, our objective is to alleviate the oracle complexity of existing methods. This is motivated by the fact that black-box function evaluations can be expensive, and hence, is imperative to minimize the number of black-box queries to the oracle. It is noteworthy that there exist opprozimate alternatives to the exact oracle, which require a polynomial complexity in the number of base arms While offering an improvement in complexity, polynomial complexity can still be excessive, and more importantly, approximate solutions can result in linear cumulative regret. Examples of reward functions facing such issues include submodular reward functions Krause & Golovin 2014) and reward functions modeled as the output of a neural network (Hwang et al. 2023). Therefore, to avoid linear regret, CTS has to inevitably rely on an exact oracle, the computational complexity of which, in general, grows exponentially with the number of base arms.
Group testing. Group testing (GT) is an efficient approach for solving large-scale combinatorial search problems (Dorfman 1943 Du et al., 2000 The basic premise in group testing (GT) is that a small sub- population (size K) of large body (size m >> K) possesses a particular property (e.g., being defective), and the objective of group testing is to identify it without individually testing all members. To avoid individual tests, the population members are pooled into groups, and the group is tested as a whole. The majority of tests are expected to return negative results, i.c., most groups do not have a member with the desired property. This clears the entire group, significantly saving the number of tests administered.
The number of tests required to identify defective items varies widely depending on the settings (see (Aldridge ct al. 2019) for a review). Under both noiscless as well as noisy test outcomes (with a bound on the number of noisy measurementss, when K = 0mm)) where a E (0, 1/3), only O(K2 log m) lests are sufficient to recover the defective subset perfectly (zero-error criterion) (Hwang & T. Sós 1987 Du et al. 2000 Chan et al.) 2011). Under a vanishing error criterion, the number of tests can be reduced to O(K log m) (Zhigljavsky 2003 Gilbert et al. 2012) (partial recovery). Furthermore, GT schemes can be classified into adaptive and non-adaptive methods. In non-adaptive group testing, all the tests are conducted simultaneously. In contrast,
2

---

Published in Transactions on Machine Learning Research (06/2025)
in adaptive group testing, the tests are divided into stages, and the tests for a particular stage are decided based on the outcomes of the previous stage. Adaptive group testing has been shown to significantly reduce the number of tests, requiring only O(K log m + m) tests for exact recovery (Hwang 1975 2005
De Bonis et al.
Different variants of group testing have also been proposed in the literature (Du et al. 2000 Du D 2006 D'yachkov 2014). These include threshold group testing (Damaschke) 2006), where test result is positive if the number of defective items in the pool is above threshold; quantitative additive group testing (D D'yachkov
2014 Du et al., 2000), where the test output is the number of defective items in the pool; probabilistic group testing [Cheraghchi et al. 2011), where we wish to recover the defective items with high probability; graph-constrained group testing (Sihag et al. 2021), where there are constraints how items can be grouped; and semi-quantitative group testing (Emad & Milenkovic 2014 Cheraghehi et al. 2021), where the (additive)
test. outputs are quantized into a fixed set of thresholds. GT has also been adopted to solve largo-scale
learning problems, such as feature selection (Zhou et al.
2014 extreme classification (Ubaru & Mazumdar Ubaru al. 2020), and data valuation (Jia et. al.
2017
2019
Contributions. In this paper, we leverage GT to dispense with the assumption of exact oracle access for the CTS algorithm. This results in an exponential reduction in the oracle complexity without compromising the achievable regret. Specifically, we devise the Group Testing + Quantized Thompson Sampling (GT+QTS) algorithm, which under a mild probabílistic assumption on the separability of the reward function (Assump- tion D will have exponentially lower complexity compared to an exact oracle. Reducing oracle complexity is fundamental challenge with significant practical relovance; a detailed discussion can be found in Appendix A GT+QTS has two key innovations compared to the existing algorithms. First, the complexity reduction is enabled by GT, the success of which fundamentally relies on separability assumptions, lacking which may face sub-optimal (lincar) regret. To address this, as a second contribution, we devise a quantization scheme that ensures the probabilistic separability of the reward function. We show that the GT-based oracle requires only O(log m) black-box queries to discern the optimal set of arms in each round. Furthermore, we show that the GT+QTS algorithm preserves the optimal regret order of m log T)) while providing an exponential roduction the oracle complexity.
Related works. We provide an overview of the most closely related studies to the scope of this paper. The theoretical analysis of the based approaches for MABs was first provided in (Kaufmann et al. 2012 Agrawal & Goyal 2012). These results were later improved in (Agrawal & Goyal 2013) and extended to general action space and feodback in (Gopalan et al. 2014). The CMAB problem is studied under different
settings in (Chen et al. 2013 Combes et al.] 2015 Chen et al. 2016b a). The TS-based approach to CMAB is investigated for top-K K CMAB in (Komiyama et al. 2015), analyzed for contextual CMAB in (Wen et al. 2015), and studied under the Bayesian regret metric by Russo & Van Roy (2016). Furthermore, CMAB has
been investigated in the bull-bandit foedback sctting in Nie ct al. (2022).
The study closest to the scope of this paper is Wang & Chen 2018), which analyzes the CTS algorithm to solve combinatorial semi-bandit under Bernoulli model and Beta prior distribution for the belief parameters. It establishes that the CTS algorithm asymptotically achieves the optimal regret. Another related study is by Perrault et al. (021). which presents a tighter regret bound for the Beta prior. A similar optimal regret analysis is established for multivariate sub-Gaussian outcomes using Gaussian priors.
2 Combinatorial Bandits
2018 Perrault et al. 2021 we consider a CMAB setting with m arms, and define the set [m] := (1, .m.. Each arm E [m is associated with an independent Bernoulli distribution with an unknown mean μy We denote the vector unknown mean values by μ : [p,, -mm]- Sequentially over time, the learner seleets subscts of arms, which we refer to as super-arms. The super-arm selected at time is denoted by S(t) E I, where I 2fml specifies the set of super-arms. We consider the semi-bandit. feedback model, wherein, at each time I, upon pulling a super-arm
Sctting. Similarly to the canonical models in WWag & Chen
3

---

Published in Transactions on Machine Learning Research (06/2025)
St), the learner observes feedback
(x,)= E()))
(1)
where (t) denotes a random observation from arm E [m]] i.e. X,(t) ~ Bern(u4) In addition to the feedback (t). based on the super-arm selected at time i, the learner gains a reward R(t). The average
reward [[](t)] is assumed to depend only on the mean values of the arms i S(t). To formalize this, we assume that there exists a function r [0, 1 + R, such that
[[R(t)] r(S(t): p))
(2)
where the expectation is with respect to the measure induced by the distributions of arms S()). Function is assumed to be wiknown, and the learner only has black-boz access to it, i.e., for any 0 E [0, 1|Th and S E I, the learner queries the black-box and obtains the reward evaluation r(S 0). For any 0 E [0, 1]", we define the optimal super-arm associated with as the permissible set with the largest reward, i.e.,
S* (0) = arg max r(S; 0)
(3)
SEI
If there are multiple optimal super-arms, we randomly select one of them. For a given f and any set I, define the sub-optimality with respect to (0) by
A(S,0) (() 0) r(S: 0)
(4)
Accordingly, we define the minimal and maximal sub-optimality gaps for any parameter 0 E [0. 1) as
A ( =
min
O) and Amax (0) == max AS
(5)
SEI-A(S.0)30
SET
The learner's objective is to minimize the average cumulative regret R()), which is defined as
T R(T) = Σ BIA(S(()..))
(6)
where the expectation is taken with respect the measure induced by the learner's interaction with the bandit instance. For any set 8 S [m] and 0 E 1jm,, we define Og as the vector, whose entries are equal to 0 for every i S, and 0 otherwise.
Assumptions. We start by discussing some of the commonly used assumptions in the CMAB literature the reward function (Wang & Chen 2018 Perrault et al. 2021). Then, we will discuss how to relax some of the idealized assumptions in the literature. Specifically, the existing studies relevant to this work assume access to an exact oracle that can perfectly solve the problem in (3), i.e., it identifies the optimal super-arm (0) for any parameter O [o, 1]mh In this paper, we relax this assumption and replace the oracle with a procedure with only soft (probabilistic) guarantees for solving (3). We begin with the following common assumption in based approaches for CMAB; (Wang & Chen 2018 Perrault et al. 2021).
Assumption 1. The expected reward of super-arm S E I depends only the mean values of the base arms in S.
We note that some studies the confidence interval- based methods have relaxed this assumption (Chen et al, 2016ab. In the context. of CTS, relaxing this assumption presents several technical challenges. Specifically, a ba-based approach at each step samples the super-arm that maximizes the reward function based on posterior mean estimates. However, for rewards, which depend on the arm distributions (and not just the mean values), we need estimates for the distributions. This calls for a separate algorithm design. Our following assumption quantifics the smoothness of the reward function.
Assumption 2 (Lipschitz continuity). The reward function is globally B- B-Lipschitz 0. More specifically, for any S E I and for any 0, 0' E [0,1] the reward function satisfies Ir(S; ; -)rr(S; 0') s B||0s 0'sll: for some universal constant. B Rt
4

---

Published in Transactions on Machine Learning Research (06/2025)
Next, we specify assumptions on the variations of the reward function with respect to S. We adopt common monotonicity assumption based on which adding arms to any super-arm will not decrease the reward. Assumption 3 (Reward monotonicity). The reward function r is monolone and increasing in S, i.e., for any Si S S2 S [m] we have r(S1: 0) S r(S2: 0), 10 E [0,
Without any constraint on the cardinality of the optimal set, the monotonicity assumption implics that the optimal super-arm is [m]. To avoid this, we impose that the cardinality of the optimal super-arm [S] S K E [m]. Besides the above standard CMAB assumptions, we also adopt three more assumptions pertinent to dispensing with access to the exact oracle that solves (3) and designing an efficient probabilistic alternative. The following two assumptions are needed for determining the number of tests in GT procedure.
Assumption 4 (Bounded reward). For any set 8 E I and any 0 E [0, we assume that the reward function satisfies r(S; ; 0) E M), where M is known.
Next, we introduce a probabilistic assumption on the distribution of the minimum gap of the bandit instances. This assumption is critical for facilitating an exponential reduction in oracle complexity. Furthermore, this assumption covers the case where a lower bound on the minimum gap of the class of instances is Bnoow//sssune to be known, which is a common occurrence in many applications such as principal component analysis (minimum singular value gap requirement for iterative partial SVD algorithms Musco & Musco (2015)) topological data analysis (minimum gap requirement for Betti mumber estimation Apers et al. (023 and others.
Assumption 5. The probability of distribution of the minimum gap Amia(p) is known, and its cumulative distribution function (CDF) is denoted by Eu.
The next assumption states that augmenting any subset of arms with an optimal arm results in higher reward gain than augmenting with a non-optimal arm.
Assumption 6 (Separable reward). For any parameter O e [0. 10.,"", any optimal arm s E (O))),, any sub-optimal arm & (0), and any set S c [m] {s,5), we have
r(SU(s) 0) rrr-(Suu (8) 0) >
In many practical settings, Assumption 5 is an artifact of designing the experiments and representing them by bandit arms. Specifically, in real-world settings, when two experiments are deemed to have sufficiently close rewards or utilities, they are effectively considered the same experiment. From this perspective, Amin can be viewod as the minimum scparation of rewards based on which we consider the experiments sufficiently distinct to warrant representing them by distinct arms. So, this is an application-speeiiie constant, and depending the underlying application of interest and what the arms represent, it can be set by the domain expert. Furthermore, in various applications, feedback or utility values are inherently quantized, leading to natural lower bound on the possible difference between two super-arm utilities. For example, consider the case of a recommendation system where the learner aims to suggest content based on user feedback, balancing exploration (new content) with the avoidance of low-quality recommendations. User feedback in such systems is typically discrete (c.g., ratings in the set 21, 3, 4, 4,5)). In this case, the smallest possible difference in utility between any two super-arms is lower bounded by 1, providing concrete and known lower bound on Amin. Furthermore, several commonly used set-valued functions naturally satisfy the separability assumption, e.g., linear rewards, i.e., r(S 0) >>>es >ies Oz, information measure-based functions such as mutual information and f f-divergence (Zhou et al., 2014 Nguyen et al.) 2010). Furthermore, we show that a two-layer neural
network (NN) also satisfies the separability assumption (see Theorem Appendix P
3 Algorithm: GT + Quantized TS
In this section, we provide details of the GT+QTS algorithm, the objective of which is to minimize the average cumulative regret defined in This algorithm has two central sub-routines. The first sub-routine is
In the case of multiple optimal super-arms, 8 belongs the union of optimal arms, and does belong to
5

---

Published in Transactions on Machine Learning Research (06/2025)
7.40
O -ormulative nom separable instances
O (log))
Figure 1: Cumulative number of times that the instance (t) is non-scparable.
an estimation process that computes estimates for the base arm means. The second sub-routine is procedure that, at each round, sequentially determines optimal super-arm to be pulled based on the current base arms' mean estimates. These procedures are discussed next.
3.1 TS-based Estimator
We consider a TS-based approach, where the estimates of the mcan values are generated by sampling from posterior distribution. We adopt a beta distribution to generate the posteriors. A beta posterior naturally comes up the conjugate distribution assuming uniform priors the mean values of the base arms. We denote the distribution associated with arm i [m] at time by (eta(a
We initialize, for t = 0, (0) (0) = 1 for all arms, in which case the beta distribution reduces to a uniform distribution. Subsequently, for each time & E N, super-arm S(() is selected, and we receive the feedback Q(t). Based on the feedback, we update the prior distribution of each base arm by updating ax(t) and (t(t). Furthermore, recall that (t) denotes the feedback from the base arm i S(t). We draw a sample Y:(t) ~ (ern(X;()), and update the posterior distribution as follows.
at ( 1) = + +,())),,(t), b((1) Y(()) +1.
(8)
(1
(9)
Finally, our estimate for z at time t is a random sample from the beta distribution with paramcters specified
in i.e., we generate the posterior estimate 0(1 ((++1) 1) according 0,(1+ 1) Beta(a, 1), 1)).
3.2 GT-based Arm Selection
We design GT-based procedure to select the optimal super-arm in each round. The nature of this procedure is probabilistie, and it is designed to find the optimal super-arm with high probability.
GT involves pooling together several arms and performing a test on the pooled set. Tests are repeated by selecting and pooling different subsets of arms for each test. When we have & tests, the pooling process can be characterized by a test matrix A {0, 1)xxm, where row j E [{] specifics the arms that are included test j. Specifically, A₁;; 1 if the arm i [m]] is contained in test
[f], and otherwise A,, = 0. For each test j E [4], design function P5 : 2(m² x [0, 1)rM + [0, M), that assigns score to the outcome of test j. Next, based on these test scores, we assign a grade to each arm that specifies whether the arm is likely to be in the optimal super-arm or not. This grade assignment is formalized by decoding mechanism specified by the function Φi [0, M + R, which generates the arms' grades. Subsequently, a candidate super-arm is selected as the set of arms with the top K grades.
Group-testing oracle (GTO). Next, we describe our GT encoding and decoding mechanisms. To lay context,, we first describe naïve adaptation of the GT approach (Zhou al.) 2014). It was designed for ranking and can be used find the optimal super-arm at each step. We then describe shortcoming of this naïve approach and modify it to replace the exact oracle used by CTS.

---

Published in Transactions on Machine Learning Research (06/2025)
Algorithm 1: GT+QTS Algorithm
Input: Cardinality constraint K, # rounds T
Initialize t I, ag = b((t) = 1 for all [m]
for t t= ==1...T do
Draw a sample 0.(1) (eta(a:(1); (c) for every arm i E [m), and form O())
4
Play the super-arm St) returned by Oracle(O(t)) (Algorithm
5
Obtain the obscrvations ((t)
Update (t + 1) & (( 1) according to
g
end
Naive GT approach. We adopt a randomized testing mechanism, in which each arm j E [m]] is included in the test by flipping a coin. Specifically, arm i E [m] is included in test j E [e] based on a Bernoulli random variable A3,a ~ Bern(p) such that arm is included in the test. if A₁. 1. Probability p is design parameter to be chosen later. For designing the decoder, at each time N, we set the scoring function of test j, i.e., Pj. to be an evaluation of the average reward function at the current estimates of the mean values, i.., (t) := =Aa ((t)), where A, denotes the jth row of the test matrix A. Based on the test scores p(t) = (Pi(t), ... ,P((t)) we define the arm grading function (t)) ==
(mm()) as follows.
(t) p(t).
(10)
For each arm E [m]] the GT decoder in 10 considers the tests E [$] which contain i, and adds up the scores due to these tests to form an aggregate grade for each arm i. Tf an arm i E [m]] is contained in multiple tests with high scores, and the resulting aggregate score is large, it is highly likely that the arm is responsible for the high scores assigned to the tests. Hence, arm i is more likely candidate to be one of the arms in the optimal super-arm. Hence, the arms with the top-K grades are selected as candidates for the optimal super-arm to be pulled at time
Separability. The naive GT mechanism faces a delicate shortcoming: for the GT to work, the reward function (()) must satisfy C-separabilityy assumption, which is stronger than Assumption i Specifically, under C-separability, any two arms E S (((tt) and & (O(tt), and any set S [m] \ {s, must satisfy
(s) O(t)) r(S (5) ((t)) 2 C.
(11)
Based on C-separability, the number tests required for identifying S (O(()) will then be inversely proportional to C2 Zhou et al., 2014). However, it is impossible to ensure C-separability for the function r(: O(t) round E N, even when the reward function r(-; μ1) at the true mean μ is C-separable. We empirically show that the cumulative number of non-separable instances increases with time t. Figure D for any t, shows the number of times the reward function evaluated at S L is non-separable. Here, by "non-separable" we mean that the reward difference is smaller than C, i.e., U(SU(s) {s}; minimum separability at the true mean. Furthermore, in Figure we plot the function A log(t) and observe that the cumulative number non-soparable instances grows faster than A (1) log(t), which is not desirable, it can result in sub-optimal regret.
- r(S U {3}; O(t)) < C, where C' is the
Quantization. To circumvent the non-separability of the reward function at the posterior means, we use quantized rewards as the test scores for GTO. Specifically, we use a uniform quantizer to discretize the reward values. This quantizer splits the interval [0, .M] into equal sub-intervals of width A/2B, where the quantization level A will be specified in Section 4 to ensure sublinear regre Based on this, we split the reward range into L = [2BM/A] A intervals, where each interval k E [L 1] is defined as
(i 1)A
A
1;
k< I,
(12)
2B
1 2B
(L 1)A
I=:=
:
M
(13)
2B
2IF 2BM/A is not an integer, we absorb the missing fraction in the last interval, making shorter than the preceding ones.
7

---

Published in Transactions on Machine Learning Research (06/2025)
Algorithm 2: Oracle(0)
Input: Parameter 0, quatization level A, cardinality K, parameter
Initialize # tests = ( ()()) log m), Test matrix A E {0, 1] such that A ~ (er
for j = do
Evaluate the average reward function r(A,, 0) the input 0 Assign the quantized score E(r(Ag: 0)) to the test j according to
14
end
Evaluate the grading function using the decoding matrix A according to 10
Output: S(I)= arms having the top-K K grades
Furthermore, we denote the set of quantization levels by L == (A/2B, ... .M. Accordingly, for any E [0, 10m and S E I, the uniform quantizer & [0, B] + C is specified by
E(r(S; 0)) == arg min Ir(S; 0) E
(14)
ZEC
Decoding. Note that quantization alone does not guarantee the separability of the reward defined in evaluated at every test. The reason is that the reward evaluations for the sets S U {s} and SU {5} may be mapped to the same quantization level, even though we have r(S U {s} 0(t)) > r(S U {$} O())) by Assumption 6 Accordingly, at each round 1, let us denote the set of unique (or non-repeated) test scores by Inr(t). Specifically, for any pair of distinct tests S,S' E (t) such that [S] = [8"), it satisfies that E(r(S; (t))) & E(r(S'; ((t))). In the decoding step, we leverage the fact that our quantization scheme enables to sufficiently distinguish the tests contained in (t).
Arm selection. Let denote the subset of arms obtained under test matrix A and the scoring function by GTO(A, p). At each round t, the GT+QTS algorithm uses the quantized average reward function E(r(A, (())) as the scoring function for each test i E [4]. Subsequently, the set of arms to be chosen at time is set to S(t)= = GTO 1)))) The entire algorithm is presented Algorithm
4 Main Results: Efficiency and Regret
In this section, we present the performance guarantees of the proposed GT+QTS algorithm. Specifically, we investigate two key performance metrics of the algorithm: (1) the efficiency of the GTO measured in terms of the number of reward evaluations required in each step, and (2) the average cumulative regret incurred by the GT+QTS algorithm. We show that the GT+QTS algorithm achieves the same order-wise regret guarantee as the combinatorial Thompson sampling using an exact oracle (Wang & Chen 2018 Perrault et al. 2021), while exponentially reducing the number of reward function evaluations. We begin with the results on the efficiency of the GTO.
Efficiency. A naïve approach to finding the optimal super-arm in each round is evaluate the functional value at every subset in I at the current estimate of O(t) at time t. However, this approach requires an exponential number of reward evaluations. An exact oracle may not require an exponential number of evaluations, owing to the separability in Assumption 6 We will first describe a baseline approach, called Oracle+, that provides an eract solution leveraging Assumption G with the reward function evaluations scaling linearly with respect to the number of base arms. Subsequently, we will demonstrate that the GTO described in Section g identifies the optimal arm with high probability, requiring only O(log m) function evaluations, thereby exponentially reducing the complexity compared to the baseline approach.
Oracles:
The baseline approach is a direct consequence of Assumption 6 Since the separability assumption
is valid for any subset S, for any parameter 0 E [0, 1] we may set S = 0. By this choice, for any E S* and & & (0), Assumption implies that
r(s: 0) > r(3: 0)
(15)
8

---

Published in Transactions on Machine Learning Research (06/2025)
Oracle+ makes reward evaluations, each test comprising of single base arm. It then selects the top K arms with the largest reward values. As a consequence of 115,, we immediately conclude that this set of base arms selected by Oracle+ is indeed the optimal super-arm (*)). Therefore, Oracle+ requires m (linear) reward function ovaluations. Next, we analyze the number of tests required by the GTO.
For any separable function, the number of tests required by the GTO is of the order O(logm) where the constants depend on the quantization level A, the set (t), as well as the test matrix parameter For characterizing the number of tests required by GTO, let us denote the probability that any test S belongs to the set of non-repeated tests at time t by
GTO:
(t) = PPS [t)(
(16)
The following lemma formalizes the mumber tests the GTO requires to compute the optimal super-arm at each time & N.
Lemma 1. For any 8 E 10,
B2
[ K)
- log
(17)
tests are sufficient for the GTO to identify an optimal super-arm in each round with probobility ot least - 5.
From 17), observe that the GTO requires O(log m) tests to identify the optimal super-arm in each round with probability at least 1 1-8. Hence, in the regime of a large number of base arms, the GTO significantly reduces the number of reward evaluations required to find the optimal super-arm in each round. We also observe that the number of tests depends on (t),, which is unknown. This can be resolved by adopting an estimator for estimating q()) based on the group tests. Tet us define
((t) = / E EIAA, (n) SEN4
(18)
We show that using O log ()) samples, we have an a-accurate estimate of q(t) with high probability, i.e., P(( - q(t) > =) < 8. Both A and qtt) capture the gramularity of the reward function in identifying the optimal super-arm. We will show that A is chosen based on the CDF F. of the arm gaps Amin(1), which captures the gap between reward due to optimal arm and any other arm. The smaller the quantization level A, the more tests are required to find the optimal super-arm. Similarly, if we face a reward function in which many tests get mapped to the same score, it unlikely that we save much by leveraging group testing.
Regret analysis. Next, we characterize the regret of the GT+QTS algorithm. As a first step, we establish that our quantization scheme for super-arm selection does not compromise the achievable regret. In other words, the regret achieved after reward quantization is equivalent to the regret with unquantizod rewards. For this, we introduce a few notations. Let T(0) denote the set of all optimal super-arms with respect to the parameter 0, i.e., S* T(0). Next, corresponding to the function & specified in [1] we define
Te(0) = arg max m 0)) SeZ
(19)
We show that, with high probability, the set of optimal super-arms with respect to the quantized reward Te(()) is contained in the set of optimal super-arms with respect to the true reward T(u). This is necessary to achieve sublinear regret, as we aim to converge to one of the optimal super-arms after quantization.
Lemma 2. For any Y E 1/2], let set A (7) For the quantization scheme described in Section with probability at least 1 - 27 have Te(m) C (H)).
Next, we provide an upper bound on the average cumulative regret that GT+QTS can achieve. We note that this is similar to the regret bound reported when access to exact oracle for the CTS algorithm is available.
9

---

Published in Transactions on Machine Learning Research (06/2025)
Theorem 1 (Achievable regret). Under Assumptions A = (r) for any " [0, 1/2,, with probability at least 27, the average cumulative regret of the GT+QTS algorithm, conditioned on the bandit instance ,e, satisfies
1
1
by setting ó 2 and the quantization level
log(2"| (IT)
R(T s Σ
(2log K + +6) B)BB²
min (A(S, p4) S
Amin
(K2 + 2)
(E(m)
8 4
K
K
n²
K2
E2 +11
Amax(())
13a
+1
log
(20)
8²
where a E R2 a constant, and E R. is chosen as
min (14) e << 4B(K2 +
(21)
A probabilistic guarantee on the average cumulative regret in Theorem might seem counterintuitive. However, note that the randomness (and hence the probabilistic guarantee) arises from the distribution F2 on the minimum gap Amin (p+,, and the average regret conditioned on the bandit instance μa. The regret bound in Theorem matches that of the CTS algorithm with an exact oracle (Wang & Chen, 2018) order-wise wise, regret bound of O(mAmiu (1) log K log T), despite GT GT-QTS requiring exponentially
Le., both have the fewer reward function evaluations. We note that the regret remains linear in The numerator of the first term in the summand, ie., log(2" [Z]T), can be decomposed into Iwo parts. The first. part is m log(2)Z]), and the second part is Ir. The first part depends on T through log but it is independent of m, and the second part is independent of T but depends on m linearly. Since the sccond part is independent of T, it does not contribule to the regret, and therefore, the regret will be specified only by the first term. other words, after summing both terms m times, we get the total regret of log T + m² which is O(m log T)). Comparing the bound in Theorem [ to that of Wang & Chen 22018 Theorem 1), we observe that GTO only adds a constant term of x² Amax (H) to the regret bound. 6
- GT
CT.CTS
300 300
Lambie of teods
(A)
(B)
(C)
Figure 2: Average cumulative regret versus time for (A) linear reward function and (B)a non-linear 2-layer ANN function, respectively. (C) Average cumnlative regret versus number of tests l.
Proof. We provide overview of the key steps and defer the details of the proof to Appendix D From the definition of regret in 66. with probability at least 1 1-y we have
T
M()) = Σ ([((s()) & T(m) x A(S(t), ())
Σ (((((()) T((A)) x A(S()),
(22)
where (22 result of Lemma 2 Next, we decompose the upper bound on the regret in (22 based on three events. The first event captures the instances at which select sub-optimal super-arm due to inaccurate
10

---

Published in Transactions on Machine Learning Research (06/2025)
sample mean estimates. The second event considers time instances at which the sample mean is close to the true mean, yet we select a sub-optimal super-arm since our posterior mean has a considerable deviation from the true mean. Finally, the third event considers the instances where the posterior mean of the selected super-arm is close to the true mean, and yet, we select a sub-optimal super-arm. The key challenge arises in upper-bounding the regret due to this third event. Specifically, the proof for this term in Waang & Chen (2018) relies on assuming access to an enact oracle- an assumption that we have dispensed with. We show that GTO is sufficient guarantee constant regret for the third set of events.
5 Experiments
In this section, we provide empirical results to assess the performance of GT+QTS and compare it against the state-of-the-art CTS algorithm provided in (Wang & Chen 2018) equipped with Oracle+ described in Section 4 as the exact oracle. We consider two reward functions: linear rewards and non-linear rewards modeled as the output of 2-layer artificial neural network. We conduct experiments on both synthetic data and real-world datasets.
Hyperparameters for GT-QTS. For GT-QTS, we have two hyperparameters: (1) the entries of the encoding and decoding matrix A, and (2) the number of tests f. For (1), the entries Ar, are drawn from a Bernoulli distribution with parameter p. In Lemma [ we show that choosing p = 0.5 results in an Ollog m) number of tests. In the experiments, we observe that choosing each column A.j ~ Bern(O(t). results in a better empirical performance. This implies that the probability of choosing arm E [m]] in a test is directly proportional to the current posterior average (t) of the arm. We adopt this choice in all the experiments. Finally, a sufficient number of tests & has been enumerated in Lemma [ Furthermore, we provide an ablation study of how the number of tests impacts regret in Figure C).
Linear rewards. In this experiment, for any set S E I and any O E [0, 1)m,, we define the reward function as r(S: ; 0) = Eies O.. We set m = 5000 arms, and the mean vector μi is sampled uniformly randomly from [0, 1|5000 Furthermore, the cardinality constraint is set = arms. For this experiment, we choose μ such that Amia (1)) is at least 0.25, and we set A 0.25. Consequently, the group testing oracle requires approximately 302 reward evaluations (order-wise), versus the exact oracle, which requires 5000 reward evaluations in each iteration. Hence, the baseline method (CTS) requires 16x more reward evaluations compared to GT+QTS. However, the regret due to CTS and GT+QTS is comparable, and GT+QTS has a slightly larger regret compared to CTS, as observed in Fig. A).
Furthermore, we empirically observe that the number of lests prescribed by theory is excessive, and in practice, much fewer tests are sufficient guarantee similar cumulative regret. To showcase this, we vary the number of group tests in the GT+QTS algorithm and plot the average cumulative regret against the number of group tests in Figure C)) computed at T = 10, 000. Figure [C) confirms that as few as & = 200 tests are sulficient for the regret. to be within 5% of the regret at the prescribed number of l Rs 310 tests.
Two-layer neural network rewards. Next, evaluate the performance of GT+QTS on nonlinear mean reward functions. Specifically, we choose 2-layer NN with 20 neurons and a sigmoid activation function. For any set S and parameter 0, the mean reward is r(S 0) = (W2,0 (W,,s)) where a(-) denotes the sigmoid activation. The weights are uniformly sampled from a normal distribution, and then we take the absolute value to make all weights positive. We choose m = 1000 arms, which are uniformly sampled at random from [0, 111000 Furthermore, the weight matrices are sampled such that we have Amin (1)) 2 0.2, and we set A 0.2. Figure (B) illustrates the cumulative regret of the CTS algorithm and the GT+QTS algorithm, which follow the same order in T.
Impact of A. To assess the impact of the quantization interval A on the regret, we perform an ablation study for varying levels of A and its impact on the average cumulative regret. Specifically, we adopt the linear reward setting, i.e., r(S, 0) = -ies 6,, and we set m = 505 arms, of which we select a subset of K = arms in each iteration. We have performed 50 independent trials, and the average results of this experiment are provided in Figure AA). We observe that as the quantization level increases, the regret increases. This is expected since the larger the gap, the less distinguishable the sub-optimal super-arms
11

---

Published in Transactions on Machine Learning Research (06/2025)
Normalized Regret
14
80
3,000
60
12
CTS GT+QTS
Regret
Regret
40
10
CTS
2,500
20
GT+QTS
1
2
50
100
A
Computation Time (s)
(A)
(B)
(C)
Figure 3: (A) Average cumulative regret versus A for GT-QTS, when T 5000. (B) Normalized average
regret versus computation time. (C) Average cumulative regret versus time for MovieLens-
are from the optimal ones, resulting in a higher probability of erroneously selecting sub-optimal super-arms. Selecting such super-arms inevitably leads to increased regret.
Computation Times. In Figure B), we plot the regret of the CTS and GT-QTS algorithms for various values of computation time. We adopt a 2-layer ANN with 50 neurons as the reward function for this experiment, where set
500 arms, and we select K = 5 arms in each round. The experiment is averaged over 100 independent trials, and the simulation is performed using Python 3.9.21 MacBook Pro with an M1 Pro processor and 16 GB of RAM. Figure 3 (B) shows that GT-QTS significantly outperforms CTS in terms of regret for specified values of computation time.
Real-world dataset. To capture the regret efficiency of the proposed GT-QTS algorithm, we also test its performance on the MovieLens-100k dataset (Harper & Konstan 2015), which consists of 100, 000 ratings from 943 users for 1682 movies. Each user is asked annotate a minimum of 20 movies. In the experiment, uniformly randomly select user and adopt the goal of recommending set of 5 movies that match the user's preferences. Here, movies are designed learner selects a super-arm of size K = 5 and receives feedback (rating) for each arm. The foedback is a Bernoulli random variable with mean value set to the (scaled) original rating from the dataset. Subsequently, the reward corresponding to the super-arm is chosen as the sum of feedback from the selected arms. For implementing the GT-QTS algorithm, we set A = 0.2, which readily follows from the observation that movie ratings lie the set 3,,2,3,4, 4,5). In Figure C(C), we compare the performance of GT-QTS against CTS, which shows a comparable regret performance to the baseline, which assumes access to an exact oracle.
arms of multi-armed bandit. In each round, the
Conclusions
We investigate the problem of regret minimization in combinatorial semi-bandits. Existing approaches assume the existence of an exact oracle, which may not always be computationally viable. To circumvent this issue, we establish a novel connection between group testing and combinatorial bandits. We propose a new arm-selection strategy that combines a group testing oracle with a Thompson sampling-basse based super-arm selection strategy. Under a probabilistic assumption on the minimum separation over the class of bandit. instances, the proposed GT-QTS algorithm has two key advantages: 1) it is significantly more efficient compared to the exact oracle since it requires exponentially fewer reward evaluations at each step, and 2) it preserves the regret guarantee of the state-of-the-at method order-wise. We provide numerical evaluations to bolster our analytical claims. A promising direction is to investigate the impact of using group testing for CMABs in dynamic environments, iee when the ground truth model is expected to evolve over time, and as a result we face a sequence of models {u(t) :t [T]]. We conjecture that an extension of the GT-QIS algorithm dynamic environments is highly non-trivial, owing challenges induced by the estimator (which now has track an evolving model), and the group testing- based super-arm selection, which crucially hinges designing an appropriate A quantity which is also evolving in the dynamic setting.
12

---

Published in Transactions on Machine Learning Research (06/2025)
Acknowledgments
This work was supported by the Ronssclaer-IBM AI Research Collaboration (ltp.l//aarrrppp..chh part of the IBM AT Horizons Network
References
S. Agrawal and N. Goyal. Analysis of Thompson sampling for the multi-armed bandit problem. In Proc. International Conference on learning theory, Edinburgh, Scotland, June 2012.
S. Agrawal and N. Goyal. Further optimal regret bounds for Thompson sampling. In Proc. Conference Artificial Intelligence and Statistics, Scottsdale, AZ, May 2013.
M. Aldridge, O. Johnson, and Scarlett. Group testing: An information thoory perspective. Foundations and Trends in Communications and Information Theory, 15(3-4):196-39) 392, December 2019.
Simon Apers, Sander Gribling, Sayantan Sen, and Dániel Szabó. A (simple) classical algorithm for estimating betti numbers. Quantum, 7:1202, 2023.
C. L. Chan, P. H. Che, S. Jaggi, and V. Saligrama. Non-adaptive probabilistic group testing with noisy measurements: Near-optimal bounds with efficient algorithms. In Proc. Annual Allerton Conference Communication, Control, and Computing, Monticello, IL, September 2011.
W. Chen, Y. Wang, and Y. Yuan. Combinatorial multi-armed bandit: General framework and applications. In Proc. International Conference on Machine Learning, Atlanta, GA, June 2013.
W. Chen, W. Hu, F. Li, J. Li, Y. Liu, and P. Lu. Combinatorial multi-armed bandit with general reward functions. In Proc. Advances in Newrul Information Processing Systems, Barcelona, Spain, December 2016a.
W. Chen, Y. Wang, Y. Yuan, and Q. Wang. Combinatorial multi-armed bandit and its extension to probabilistiaally triggered arms. Journal of Machine Learning Research, 17(1):1746-1772 Jamuary 2016b.
Mahdi Cheraghchi, Ali Hormati, Amin Karbasi, and Martin Vetterli. Group testing with probabilistic tests: Theory, design and application. IEEE Transactions on Information Theory, 57(10):7057 7067, 2011.
Mahdi Cheraghehi, Ryan Gabrys, and Olgica Milenkovic. Semiquantitative group testing in at most two rounds. In Proc. IEEE International Symposium on Information Theory, pp. 1973-1978, 2021.
Combes, M. Sadegh Talcbi M. S., and A. Proutiere. Combinatorial bandits revisited. In Proc. Advances in Neural Information Processing Systems, Quebec, Canada, December 2015.
Peter Damaschke. Threshold group testing. In Proc. General Theory of Information Transfer and Combina- torics, pp. 707-718. Springer, 2006.
A. De Bonis, L. Gasieniec, and U. Vaccaro. Optimal two-stage algorithms for group testing problems. SIAM Journal Computing, 34(5):1253 1270, 2005.
R. Dorfman. The detection of defective members of large populations. The Annals of Mathematical Statistics, 14(4):436 440, 1943.
D. Du, F. K. Hwang, and F. Hwang, Combinatorial group testing and its applications, volume 12. World Scientific, 2000.
Hwang FK Du D. Pooling designs and nonadaptive group testing. Important tools for DNA sequencing. Series Applied Mathemalics, 18, 2006.
Arkadii G D'yachkov. Lectures on designing screening experiments. arXiv preprint arXiv: 4r 7505, 2014.
Amin Emad and Olgica Milenkovic. Semiquantitative group testing. IEEE Transactions on Information Theory, 60(8):4614 -46444446633 2014.
13

---

Published in Transactions on Machine Learning Research (06/2025)
A. C. Gilbert, B. Hemenway, A. Rudra, M. J. Strauss, and M. Wootters. Recovering simple signals. In Proc. Information Theory and Applications Workshop, Lausanne, Switzerland, February 2012.
A. Gopalan, S. Mannor, and Y. Mansour. Thompson sampling for complex online problems. In Proc. International Conference on Machine Learning, Beijing, China, June 2014.
F Maxwell Harper and Joseph A Konstan. The movielens datasets: History and context. Acm transactions interactive intelligent systems (tils), 5(4):1-19, 2015.
F. K. Hwang and V. T. Sós. Non-adaptive hypergeometric group testing. Studio Scientiarum Mathematicarum Hungarica,
1987.
FK Hwang. generalized binomial group testing problem. Journal of the American Statistionl Association, 70(352):923 926, 1975.
T. Hwang, K. Chai, and M.-h. Oh. Combinatorial neural bandits. aiv 2306. 00242, 2023.
R. Jia, D. Dao, B. Wang, F. A. Hubis, N. Hynes, N. M. Gürel, B. Li, C. Zhang, D. Song, and C. J. Spanos. Towards efficient data valuation based on the shapley value. In Proc. International Conference on Artificial Intelligence and Statislies, Okinawa, Japan, April 2019.
E. Kaufmann, N. Korda, and R. Munos. Thompson sampling: An asymptotically optimal finite-time analysis. In Proc. International conference algorithmic learning theory, Edinburgh, Scotland, June 2012.
J. Komiyama, J. Honda, and H. Nakagawa. Optimal regret analysis of Thompson sampling in stochastic multi-armed bandit problem with multiple plays. In Proc. International Conference on Machine Learning, Lille, France, July 2015.
A. Krause and D. Golovin. Submodular function maximization. Tractability, 3(71-104):3, February 2014.
B. Kveton, Z. Wen, A. Ashkan, and C. Szepesvari. Tight regret bounds for stochastic combinatorial semi-bandits. In Proc. Artificial Intelligence and Statistics, San Diego, CA, May 2015.
Xutong Liu, Jinhang Zuo, Siwei Wang, Carlee Joe- Wong, John Lui, and Wei Chen. Batch-size independent regret bounds for combinatorial semi-bandits with probabilistically triggered arms or independent arms. Advances in Neural Information Processing Systems, 11:14904-1444 2022.
Nadav Merlis and Shie Mannor. Batch-size independent regret bounds for the combinatorial multi-armes bandit problem. In Conference on Learning Theory, pp. 2465-2489. PMLR, 2019.
Nadav Merlis and Shic Mannor. Tight lower bounds for combinatorial multi-armed bandits. In Conference on Learning Theory, pp. 2830 2857. PMLR, 2020.
Cameron Musco and Christopher Musco. Randomized block krylov methods for stronger and faster approxi- mate singular value decomposition. In Proc. Advances in Neural nformation processing systems, volume 28, Montreal, Canada, 2015.
X. Nguyen, M. J. Wainwright, and M. Jordan. Estimating divergence functionals and the likelihood ratio by convex risk minimization. IEEE Transactions on Information Theory, 56(11):5847 5861, October 2010.
G. Nie, M. Agarwal, A. K. Umrawal, V. Aggarwal, and C. J. Quinn. An explore-then-commee algorithum for submodular maximization under full-bandit feedback. Tn Proc. Uncertaindy in Artificial Intelligence, Lindhoven, The Netherlands, August 2022.
P. Perrault, E. Boursier, V. Perchet, and M. Valko. Statistical efficiency of Thompson sampling for combinatorial semi-bandits. arXiv 2006. 06618, 2021.
Pierre Perrault. When combinatorial thompson sampling meets approximation regret. Advances in Neural Information Processing Systems, 35:17639-17633 2022.
14

---

Published in Transactions on Machine Learning Research (06/2025)
Daniel Russo and Benjamin Van Roy. An information-taccretie analysis of Thompson sampling. The Journal of Machine Learning Research, 17(1):2442-2477 January 2016.
S. Sihag, A. Tajer, and U. Mitra. Adaptive graph-constrained group testing. IEEE Transactions on Signal Processing, 70:381-396, December 2021.
S. Ubaru and A. Mazumdar. Multilabel classification with group testing and codes. In Proc. International Conference on Machine Learning, Sydney, Australia, December 2017.
S. Ubaru, S. Dash, A. Mazumdar, and O. Gunluk. Multilabel classification by hierarchical partitioning and data-dependent grouping. In Proc. Advances in Newral Information Processing Systems, Vancouver, Canada, December 2020.
Q. Wang and W. Chen. Improving regret bounds for combinatorial semi-bandits with probabilistically triggered arms and its applications. Proc. Advances in Neural Information Processing Systems, December 2017.
S. Wang and W. Chen. Thompson sampling for combinatorial mani-bandits. In Proc. International Conference Machine Learning, Stockholm, Sweeden, July 2018.
Z. Wen, B. Kveton, and A. Ashkan. Efficient learning in large-scale combinatorial International Conference on Machine Learning, Lille, France, July 2015.
Proc.
A. Zhigljavsky. Probabilistic existence theorems in group testing. Journal of Statistical Planning and Inference, 115(1):1 43, July 2003.
Y. Zhou, U. Porwal, C. Zhang, H. Q. Ngo, X. Nguyen, C. Ré, and V. Govindaraju. Parallel feature selection inspired by group testing. In Proc. Advances in Neural Information Processing Systems, Quebec, Canada, December 2014.
15

---

Published in Transactions on Machine Learning Research (06/2025)
A Practical Implications of the GT-based CMAB Framework
In a broad range of applications, the decision space's cardinality is vast. Furthermore, performing an experiment for each possible decision can have extensive time or monetary costs. For instance, in precision medicine, treatments have to be tailored to individual patients based on genetic, clinical, and lifestyle factors. The number of such treatment regimens, especially when combined with the combination of medications, their dosage, and schedules, results in thousands to millions of candidate treatments (i.e., arms). Furthermore, in many such applications, performing each experiment has high monetary cost and/or is time-consuming.
Experimental time and cost in genomies: In functional genomics, researchers aim to understand how combinations of gene perturbations (e.g., knockouts activations) influence a. biological phenotype-such as drug response or cell viability. A common objective is identifying the subset of genes whose knock-out maximally affects a target phenotype. This naturally lends itself to a combinatorial bandit. formulation, where arms correspond to genes, and each super-arm a subset, of genes to be perturbed. Evaluating a super-arm involves a costly biological experiment - often requiring weeks or months of lab work and substantial monctary investment. Thus, the utility function is expensive to evaluate, and the goal is to minimize regret while limiting the number of such high-cost experiments.
Monetary cost per query: Performing clinical trials in the above genomics example can also be highly costly. In another example, consider the problem of crafting adversarial examples against commercial image classification APIs (e.g,, Google Vision Clarifai). Each query to the API incurs a monetary cost. This setting can be framed as an active learning problem, where the learner selects a batch of queries, receives labels from the APT, and iteratively searches for adversarial inputs - while minimizing financial expenditure. Here, the oracle is the API, and each super-arm (batch) query is associated with a dollar cost.
B Proof of Lemma 1
At any instant t E N, choose an optimal arm s (f((t) and a sub-optimal arm 3 $ (o()))) For accurate prediction, the arm grade (t) for arm should be more than @=(t) assigned to arm 3. Let us denote the ith column of any matrix A by A. Finding the difference between the arm grades, we have
(x(t) dt(t) (A p(t)) (A.s p(t))
(23)
Σ (Aj,s pz()
(24)
Furthermore, we have
[t] [[A (t)))
(25)
E[ A,,s) E(r(A;; O(t)))
(26)
Σ (1(8E - 1 ()) x E(r(s; (()))) x P(S e A)
(27)
Sclm]
Σ
1s - 1(8ES)
x E(((S; 0(1)) x P(S e A)
=0
Σ $CIm)
() 1(8 E S}
x E(r(s; (())) x P(S
+
Σ
L(sE S} 1(3 S
E ((t)) x A((SAA
SCIm)
16

---

Published in Transactions on Machine Learning Research (06/2025)
Σ
[[ - [SES)-1(SES)
E(((s) (()))) P(SEA) EA)
(28)
=-1 ((r(Su(s): 0(1) E(
E
( (()) x E)
(29)
(s.3)
p(1-p) - p)
Σ
(o(r(SU(s) ; (r(su (3) 8()))
x
s1 p) (1- 11-
(30)
Next, let us recall the definitions the set of repeated tests I (t). Accordingly, we have
(t) p(1 p)
Σ
(e(r(Su(6): 0(0)) ( :())))
(C(m)
x x (1-p)
(31)
= =
Σ
-0)) 0(1)))
Amin(
x (1-p)
+ +p(1-p) -)
Σ
Q (Q(1(S) (0) - 0(1))
x pl (1 - m-
(32)
2
P(L PL -p)
A
Σ
p1. (1 - m- -2
(33)
2B
A
2B ((1 p)PP IIr(() ES)
(34)
A
2B 22 - p))(t))
(35)
where 355 follows from the fact that P(S In) 8) P(S E Inr(t) s S)P(s E S) pq(t).
Furthermore, since we have (T(t) E [-M, M, M] as per Assumption by Hoeffding's inequality we have
AApppp - (1)
I o( - 2z(() 2) I exp
(36)
8M2B²
Finally, noting that there K (m K) possible ways to choose and 3, taking union bound along with (36 concludes the proof.
Estimating q: First, note that q(t) is an unbiased estimator of (t). This is because
[l((()]
I4A E Inn(()}
(37)
jeL
Σ P C(AA, E Inn(())
(38)
JEL
P (I)
(39)
q(1)
(40)
17

---

Published in Transactions on Machine Learning Research (06/2025)
Furthermore, since q(t) is an unbiased estimator of q, using the Hoeffding's inequality, we obtain that for any E 12 and 8 E (0,1)
e log z
(41)
2²
tests are sufficient. to ensure that.
(((((t) - -al <d>=) s 8.
(42)
C Proof of Lemma 2
First, we will show that with a high probability, we have To(m) # 0. Note that
P P(Tolu) =
=P(3SET(w),3 e TQ(()) 8 & TQ(m) and S' & T(1)) < E TQ(u): rr(;; n) - -r(';; u) 2 Amin(t))
(43)
(44)
=P(SE TQ(l)):
r(8; m1) E(r(8'; n4) + E(r(S'; ; n)) - -r8'; m) Amin (1i)
(45)
<P(3SE T(p), 38' TQ(m):
r(8: (1) E(r(S; n)) + E(r(S'; 11) - r(S'; 11) 2 Amin(tt)
(46)
A
A
38 T 35' E To(m):
+ 4B
Amin(1s) (11)
(47)
4B
A
2 Amin (4)
(48)
2B
F (7)
> Amiu (11)
(49)
2B
F (7) > Amin (1)
(50)
(51)
where 446 follows from the definition of the set S' 47 follows from the quantization scheme in 14
49
holds since we have set A = (7), and (50 holds since B is the Lipschitz constant in Assumption
2
and it can always be set to be larger than 1/2, if any B < 1/2 satisfics Assumption 2 This proves that Te(u)) (T)) # 0 with probability at least. 1-7. Next, following a similar line of arguments, we will show that TQ(H)= E ((4) with a high probability. Let us define the event
E(p) = (T((H) = o}
(52)
We have,
F(T(N) c TE(W))
= P(3S'e Te(H): :'' $ T(H))
(53)
= 1P(3S' E TT(p)): :S' T()) E(H) F(E(H)) P(SS' E TE(m): S' ST&T(M) E(H) ((E())
(54)
P(33' E Te(H)) S' TTT(()) ((1)) +7
(55)
18

---

Published in Transactions on Machine Learning Research (06/2025)
= :((3'' Te(H). Te(p) : r(5: p) - r(S'; p)) 2 (p) E(Hl) +
(56)
-P(3S' E Te(H), 8 TT(p)) r(s: 11) - -E(r(S"; 1))
=
+ E((((S' 14) - -r(':; 14) min E(ui) +y
(57)
=P(35' E TT(()), 8 E (T(1u) nu (T()): r( m)) - E(r(S;; 1))
-
+E(r(S"; H)) -r(s'; ; μ) 2 Amin (w) E(pi) +
(58)
< P (3 E TT(()), 8 E (T(
A
4B Ami((1)) E(w) +
(59)
4B
s P P35' Te(m)), E Te(u) 2 Amin(1)) | E(He) + +7
(60)
- P
Amia (1))
(61)
2
< 27
(62)
where 661 follows from the fact that the events E(p) and mm)(()) are independent of each other, since the distribution of Amin(1) is property of the environment, and does not depend on the event E(u). This concludes our proof.
D Proof of Theorem 1
Similarly to (Wang & Chen 2018
begin by defining a few events that are instrumental in characterizing the upper bound on the average regret. First, let us denote the number of times that any arm i E [m] is sampled until time I E N by T.(.). Furthermore, let us denote the sample mean for any arm i E [m]] at time E N by pe(t). Accordingly, let us define
1. A(t) = (S(() & TT()))).
B(() = li S(t): (7.(1)) - 14 [
3. C(I) {110s()(() |s(()11 ASS()).
Amin(H)
(K2 + +22+2)6
With a probability least 2y, we can decompose the regret as follows.
R(T) Σ E ((((() T()) x A(S(t), m
(63)
x
B (((((())) x A((())
(64)
Σ
((((( B(0) x A(8())
E (A(() n ((()) (C()) x A(S(),
A
A2
Σ (LA(1) A(8(),
(65)
Aa
where 664) is a result of Lemma Next, we find an upper bound for each of the terms A₁, Ag and Ag
recover the regret bound in Theorem 1
19

---

Published in Transactions on Machine Learning Research (06/2025)
Upper-bounding A1: First, we leverage (Wang & Chen 2018 which we state below for completeness.
Lemma 1) to find upper bound on A1,
Lemma 3 [Wang & Chen (2018)). In Algorithm
we have
E
Σ 1i E S(1), (7:(1) 14l > t)
s 1 8²
(66)
Leveraging Lemma 3 it can be readily verified that the regret due to A can be upper bounded as
(mk²
A1 I
m (p)
(67)
E2
Upper-bounding A2: Next, we provide an upper-bound for the term A2. First, note that under the event B(1)n the event
9()) = {10000000) Assoll
A(S(I),
(min(s) (K² + 1)e
(68)
B
2B
holds. Furthermore, let us define the event
2 A(S(t),
A (m) -KK2 + 2)8)²
H(t) = Σ
I
2B
(69)
Ti(1)
log(2m (T
iES(s)
Subsequently, we may expand the event ((t) as
G(t) ((t) H(t)
g(t)
(70)
Next, note that using Peerauul et al. 2021 Lemma 2), it can be readily verified that
IP (G()) n HH() - T VIEN.
(71)
Hence, what remains to upper-bound the term
T
E ((g(()) n H(O)) x A(S(()
(72)
Similarly to Wang & Chen (2018 81, under the event H(L), we define function that upper-bounds the regret at time due to the super-arm S(t). Specifically, for any arm i E S(t), let (:))((()) denote this function, and we show that Eieso) 9: (T:(()) 2 ())())))). Finally, we have
T
Σ
E (11(() H()) x A(S())
S Σ Σ (T)((t))
(73)
EEN (ES())
For any e [m], let define the function
Amax (4).
if n=
log(2m (2m T[T)
2B
if n S Li11
n1
(n) =
(74)
2B (2g(2m)) I(T)
if L1 n Lig
min S:EES
A(S.
A Amin
(K2 2)
B
0,
n > L22
20

---

Published in Transactions on Machine Learning Research (06/2025)
where we have defined
log [TT)
L11
(75)
min
A(S
Amin (p))
(K2 + 2)
SaeS
2B
and,
K (2(2"'(Z[])
L
(76)
(ASS
Amm (p) (K2 + 2)8)
min SHES
28
Next, we verify that the function 9, defined in [44 satisfies the condition that Eies()) (T.((t)) 2 A(S(t), ())
for every t E N. First, note that if there exists arms S(t) such that (t) 0, we have
Σ (:(((())) 2 (T)) (E)())
(77)
(p)
(78)
> A(S(t),
(79)
Next, if there exists an arm E S(t) such that
log( 1og(2 (IT)
S (t) S
(80)
((8(0)
Amnn
-KK2 + 2)s)*
17
2B
which implics that (t)) & L1,1, we have
Σ 9:(T((() 2 (5(T(())
(81)
#ES(()
log (2Th IIT'
V
(82)
(1
((S(t).
Amin(H)
2 2
(K² + 2)
(83)
B
2B
A(S(t).
(84)
where 84
holds since we have chosen E E R2 such that
Amiu (4)
(85)
4B(K2 (3(K++2) 2)
Next, if, for all E S(() we have
1og(2 (2th) [T
T2(t)
(86)
((S())))
Amn (M) (K² + 2)
B
2B
we can decompose S(I) into three disjoint subsets. Specifically, we define
S,() (i E S()) T.() < [.1)
(87)
S2(t) (i E S(t) L,1 < Ti(t) & L,2).
(88)
Sz(t) = (i e S(t) T.(t) > L,2
(89)
Subsequently, we have
Σ 9a (T:(()) SE)(()
21

---

Published in Transactions on Machine Learning Research (06/2025)
Σ
(c(T((1)) +
Σ (T))((())
(90)
(E))(1)
(E)
log(2m (I(T)
2B 1og(2"m)
[I(
E
2B
(91)
(t(
(t( min
A(S.
(K² + 2)
(e)
(t)
Sac5
B
2B
log( (2Th (I(
2B (og(2"((])) [I[T)
Σ
2B
Σ
(92)
(1(1)
(t( (()())
Amin(
(K² 2)
(t)
(E)
2B
2B log(2 2mm I[T)
Ti(1)( A()
Amm (14)
(K2 + 2)e)*
Σ
x
B
2B
(i(1) (4)
Amm (4)
(K2 + 2)e)
log n [T]T)
(1)
28
2B log 2 I[T)
Σ
(98)
Ti(l) p(
Ami (1L)
(K² + 2)²)
(ES2(1)
B
2
2B 1og(2
I
2B log(2" [I[T
Σ
+ Σ
(94)
(1(1)( (4)
(mm(
(K2 + 2)e)
((( A(S(t).)
(mm
(K2 2)
IES.(1
B
2B
(ES)(1)
2B
2B log(2 (2 (T(
1
Σ
Σ
(95)
A(S())
Amin (pL)
(K2 + 2)6)
Ti(t)
Ti(t)
2B
(ES(()
iES,(1)
2B 12 [TT)
A(S(U)
Amin (pc)
(K2 + 2)
2 (()
Amt((H) (1)
(K² + 2)=)² 2
p))()))
Amir(p) 2B
(K< + 22)=)
B
2B
B
(96)
log(2 (T
log (2t [I(T)
(97)
2 A(S(()) p4)
(98)
where 94 uses the fact that
log(2" (2 [[[T
Ti(1) >
V (i)((),
(99)
((S()).
(p)
(K2 (k)+
1
2B
and 96 holds due to the event H(t along with the definition of the set Sa(t), and 97 holds by the choice
of & E R.. Finally, if all E S(t) satisfy T;(t) > Li we have
Σ VES(1)
Σ
1
(100)
Ti(t)
Li,2
AES(L)
min SaeS
((S,)))
Amin (1L)
(K2 ( 2)))²
B
(101)
K log (m [[[T)
SES())
((S())
A (1s)
(K2 +2))2
2B
(102)
log 1
which is in contradiction with the event H(t). Hence, we have shown that under the event H(t), the functions 9, satisfy the inequality Σ (T)).(()) 2 (SS()), m). Finally, summing up the (T,(1)) functions over time (E)(E)
and the set of arms, following similar procedure to (Wang & Chen 2018
obtain that
B log(2 (2 I
Ag < 2mAmax (1L) + Σ
(2log K + +6)
(103)
min S
A(S.u)
Amia( (1)
3E/ml
B
28
22

---

Published in Transactions on Machine Learning Research (06/2025)
Upper-bounding As: Finally, turn our attention to upper-bounding Ag. Before analyzing the upper bound, let us lay down few notations and definitions required in the analysis. Tet 0, 0 E [0, 1jmh and 2 S [m]. Accordingly, let us define 0' = (0z, 02) as a vector, whose 5th coordinate has the same value as the 8th coordinate of 0 i 2, and otherwise, it has the same value as the 1th coordinate of O. Let S5(H)) E Tg(H)) denote one of the optimal super-arms with respect to the quantized reward function. Furthermore, for any choice of 0 and 2 such that 00 - /2 S e, let us consider the following properties of the vector 0'.
Pl. Z S (0')
P2. Either (0") Te(p)), or 110s3(0r) Msy (A(S)(0), p)) 2B (m) (K² 1)E,
Furthermore, for any 2 S [m] and 0, 0 [0, 11 satisfying ||0z - Mz S 8, let us define the event
(0) == { properties P1 and P2 hold for Z S [m] and e [0, [0m
(104)
Additionally, let us define the event
M(1) = {s()) + (0()))))
(105)
For upper-bounding Aa, we decompose the event A()) n E(() as follows.
A())n(() (())C())) U A(L) ne(1) mLM
(106)
Leveraging Lemma we have that at any time t E N, P(M(t)) S 2.. Hence, we have
E [(((((t)) A(S()) < Amax Σ P(M()))
(107)
max (H)
(108)
6
Next, we upper-bound the regret due to A3 under the event M(t), i.c., when the GTO returns the same super- arm as the exact oracle. We emphasize that under the event A(t) NC(T) the analysis does not reduce to the analysis of the CTS algorithm Wang & Chen (0018), since, an exact oracle operates on the true reward function r(- ; -), whereas the GTO operates on the quantized reward function E(r(-; .)) Next, we prove that if the event A(t) CCt M(t) occurs, then it implies that there exists set Z C ()(() (H) such that the event (O))) occurs. Before formally proving this statement, let us understand its implication. If there cxists 2 C (p(), Z + 0, such that (O()) occurs, then it immediately implies that |10
> 6. This is because, if 100 - Mzllxx S E, then (t) becomes a candidate choice for 0', and thus, either 1) S(t) E Te( (hence contradicting the event A(t)) or 2) (t) - Psuell > AS)()) 4) 22 A min (14) - (K² + 1)s
(hence, contradicting the event C(t)). Subsequently, can leverage (Wang & Chen 2018 Lemma 3) which provides an upper bound on the number of times that the event (t, == (z))( M 2 Il > E} occurs.
Lemma 4 (Wang& & Chen 2018 ) We have
Σ E [B(1(A())e0) n M(t M())n < 13a
T
8 $²
+1)
K
K log
(109)
gz
where a E R. is universal constant.
Hence, we oblain that the regret due to Ag is upper-bounded by
8 4
+1)
K
K
T²
As
<
13a
log
+
Amax (1)
(110)
What remains is to prove the following lemma.
23

---

Published in Transactions on Machine Learning Research (06/2025)
Lemma 5. If the event ((t)) n M(t) happens, then there crists subset 2 C SQ(),, 2 0, such that (0() holds.
Proof. First, let us set 2 (1()) Accordingly, define the vector O' such that 110 (3 Msg Sc. We will show that for any S' such that S' (1) D, S²(0") + S'. S'.
To verify this, note that
E(r(8' 0)) E(r(S'; (())))
(111)
< E(r(S(t): (()))
(112)
r(S(t); 0()) Amia (H)
(113)
4B
cg)
Amin (p)
r(S(t); (¹) + A(S()), 11) B(K2 2 + 1)s
(114)
4B
(1)) 14) -Ka Amin
(115)
4B
A Amin (p)
$ (1) 0¹) + BKE BKE
(116)
4B
((r(SQ(m) 0'))
(117)
where 115
is a consequence of Lemma 2 and 116 follows from Assumption Hence, from 117 we
conclude that S' + (0'). So, we have two possibilitics for Si")"..
a) (H( (0')
b) Let define 2 = S2 (0') ( Then, we have 2, # 0.
For the case (a), if S (0) & T(H), have
r( (0)) 0¹) > r(S)((0); pd BKs
(118)
2 r(( ; n)) A(S)(0"), BKe
(119)
which, along with Assumption implics that
10's (0)) 1ss(0)) ASS) p))
B Ke
(120)
which implics that (O()) holds with 2 = -S)(4). Otherwise, for case (b), we follow the same set of arguments as in (Wang & Chen 2018 Lemma 2), which concludes the proof.
Finally, Theorem is obtained by adding the upeer-bounds obtained due to the terms A,, A and Ag.
E Artificial Neural Network (ANN)
In this section, we show that a 2-layer ANN with sigmoid activation satisfies the separability condition Assumption 6 with some conditions on the weights. Specifically, consider a 2-layer ANN with the hidden layer weight matrix denoted by W, and the output weights denoted by the vector Wa, ic., for any input 0s [0, 1)" the output of the neural network is given by
r(S; 0) = (w2, of (Wi0s))
(121)
where a(x) = Ite- denotes the sigmoid activation function. The result formally defined next.
24

---

Published in Transactions on Machine Learning Research (06/2025)
Theorem 2. Any 2-layer ANN with the hidden layer Wi and output weights w2 is seporable, i.e., for any E (0) and & S* (0), and for any S S [m] {8,8), we have
(() 0) ((S 0) > 0,
(122)
for any 0 E [0,
Proof. Let denote the number of neurons in the hidden layer by N. The difference in rewards for any 0 [0, 1J and sets S, S [0, 1| {3, can be expanded as
u(Su(s) 0) ((Su(3) 0)
W2 (WI, W,, (
(123)
N
Σ
W2nn
(124)
where Wa,n and Yn denote the th coordinates of the vector W2 and y for any E [N]. Furthermore, for any set S _ [m], the th coordinate of the vector := oeW,0 Os) is given by
exp
Σ
0, O,W.i.. w.......)
Un =
iES
(125)
1 1 exp
(-
Σ 0, W I.m.i)
iES
Accordingly, we have for any n E [N].
cxp
(- Σ
0, W Wimss) )) (cxp( 03 W3W I.n.s - exp(- R,W,,, Wi,n,)))
(cxp(-0&
Vn
iES
(126)
1 1 exp
(-
Σ
0, 0,W (Wims)
1 1+ exp (-
Σ
O, W.m.s
(ESU(s)
iESU(S}
Next, let us define the quantities
8(,,3,n) (exp(-0s W,W,WW1.. W.n.. exp(-0. (i0k-0......)) Wim.el))
(127)
and for any set S C [m] 5).
Σ 0, (.Wi..))
exp
a(S: n) =
(128)
1 + exp
(-
Σ
0, W 1....)
1 1+exx exp
Σ iESUYS}
O,Wi,g (ii.)))
(ESUÇs)
Leveraging 127
and 128 we can write
124 as
N
r(Su (s}: 0) - (-Su 0) 22n x a(S; n) x 8(s, 8,n)
Σ
(129)
Next, let us S S' S- {s}. Accordingly, we have that
N r(S*(0); 0) - (S' U (3); 0) = Σ
W2n x a(S'; n) x 6(,,3,n)
(130)
n=1
25

---

Published in Transactions on Machine Learning Research (06/2025)
min (0)
(131)
Furthermore, for any set S _ [m] \\ {)
we have
((S 0) u(
Σ
Wa, a(S n) 8(s, 3,n)
(132)
N
Wan x 8(8,3,n) x a(S' n) x a(S; n)
(133)
a(S" ; n)
Defining = min minnggiaMMa. aS ar n we note that B IR,, since a(S n) E R4 for every
8 E [m]] \ {8,8) and (N]. Hence, (133) can be lower bounded as
rSu {8); 0) - ( 0)
3
u2nn
a(S' n) 0(8,5, 5,
(134)
13
B BA min (0)
(135)
(136)
26


Reviews:
[{"review_id": "bm0JgDn2EA", "reviewer": "Reviewer_yKyq", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Major comments\n\n- The paper seems to state the semi-bandit problem with respect the collection of subsets $\\mathcal{I}$, which correspond to the legal set of super-arms which can be played. However, neither the algorithm restricts itself to sampling super-arms in this set, nor do the analysis / upper bound effectively depend on this set. The upper bound scales with $\\log (2^m |\\mathcal{I}|) \\in [m, 2m]$. Furthermore, Algorithm 2 in the paper queries super-arms according to the test matrix $\\boldsymbol{A}$, which contains randomly sampled rows which are not guaranteed to be the indicators of sets in $\\mathcal{I}$; the output of the algorithm is a super-arm which is also not guaranteed to be in $\\mathcal{I}$.\\\nIs it correct to say that the results are essentially for the setting $\\mathcal{I} = 2^{[m]}$? This is now confusing to me, since it means that the optimal arm under the monotonicity condition (A2) means that the optimal super-arm must be $[m]$. I think the authors may be indicating that the results are for the setting where the optimal comparator super-arm has size $\\le K$, and the algorithm must also finally output a super-arm of size $K$ within each round, however, the reward function can be queried on arbitrary super-arms and parameters when designing an optimization oracle. This distinction needs to be made very clear in the paper. The presentation can also be simplified then, since we may replace $|\\mathcal{I}|$ by $\\binom{m}{K} \\asymp m^K$ in the regret bound.\n\n- The algorithm and its analysis are not surprising. The analysis proceeds in two steps, $(i)$ arguing that Thompson sampling is faithful at estimating the arm means $\\boldsymbol{\\mu}$, $(ii)$ arguing that the group testing can be used to estimate the optimal arms for the current parameter estimate $\\boldsymbol{\\theta}$ (cf. Lemma 1). The latter is complicated a little bit by the fact that group testing succeeds only when the reward function is strictly separable (i.e., A4 holds with the reward gap in eq. (1) above, to be at least some constant $C > 0$ rather than just strictly positive). But this is resolved by quantizing the rewards so that the gap is exactly zero (so that two arms are either exchangeable, or are distinguishable), and arguing that the optimal super-arm corresponding to $\\boldsymbol{\\mu}$ typically does not change (Lemma 2) even under quantization. I am not convinced that there are too many technical challenges in arguing this once quantization is assumed: the analysis is essentially of the form $A + B$ where $A = \\{ \\text{bound on query complexity of GT} \\}$ and $B = \\{ \\text{bound on regret of TS} \\}$, and results of both forms have been established many times in the literature.\n\n- Reward monotonicity is a very strong condition. It essentially means that the top $K$ arms in terms of reward $r(\\{a \\},\\boldsymbol{\\theta})$ are in the optimal set $\\mathcal{S}^\\star (\\boldsymbol{\\theta})$, so I view the group testing approach as a much quicker way of identifying what these arms must be. It would be more interesting if there were weaker conditions under which such a recovery guarantee were true.\n\n- The paper confounds the computational complexity and regret bounds in the experiments: Fig. 2a/2b argues that the regret of the proposed algorithm is not much worse, while the discussion surrounding Fig. 2c argues that the algorithm's cumulative regret improves gracefully as the number of reward queries / tests grow. The fair comparison to make is to identify how much the regret of the algorithms differ by, when the amount of compute is normalized across algorithms. For instance, in Table 1, the comparison showing that the proposed GT+QTS approach scales better in computational complexity, however the cumulative regret in both cases is not going to be the same, and normalizing the table by the number of horizon steps is somewhat meaningless. The reason I point this out is, by a cursory glance at Table 2, it appears that the amount of time taken by QTS+GT @$H=5000$ is comparable with the amount of time taken by CTS @$H=1000$. However, comparing cumulative regret @$H=5000$ for QTS+GT with that of CTS @$H=1000$ appear very close to each other (Fig. 2c). So the gap in computational complexity, after normalizing for the cumulative regret is much less substantial than Table 1 indicates.\n\n- I am not a huge fan of experiments such as that in Table 1 which plot the runtime of two algorithms, without providing any additional implementation details. It is unclear what to attribute the performance gains to, without these details.\n\n- The writing in the paper is good and the assumptions are stated clearly.\n\n### Summarized review\n\nI like the problem that the paper proposes to study, essentially tackling the computational aspects of combinatorial semi-bandit learning (which often forms the bottleneck over worse statistical / regret guarantees. An algorithm cannot achieve low regret, if it cannot be implemented in the first place). I think the paper can be improved if some of the assumptions such as reward monotonicity can be weakened significantly, in a way where it is less obvious what the interaction between the optimizer (i.e., which returns the optimal super-arm) and the exploration algorithm (Thompson sampling) is. I appreciate that the authors decided to evaluate their algorithm empirically, however the settings are quite toy, and so I am not sure how accurately they reflect practical considerations when extended to more general settings. As such, I think the results may be of some interest to the TMLR community.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents computationally efficient algorithms for combinatorial semi-bandits in the setting where the number of arms is extremely large. There is a permissible set of super-arms is denoted $\\mathcal{I} \\subset 2^{[m]}$ with $\\mathcal{A} = [m]$, and upon querying this super-arm, the learner receives a noisy sample of the mean parameter of each arm in the set (arm mean parameters are denoted $\\boldsymbol{\\mu} = \\{ \\mu_i : i \\in [m] \\} \\in [0,1]^m$), and also a noisy sample of the reward corresponding to that super-arm, which is an implicit function of the mean parameters of the arms, denoted $r ( \\mathcal{S}, \\boldsymbol{\\mu})$. The objective is to find the super-arm which obtains the largest reward denoted $\\mathcal{S}^\\star (\\boldsymbol{\\mu})$.\n\nThe suboptimality gap of a super-arm $\\mathcal{S}$ with respect to a parameter estimate $\\boldsymbol{\\theta}$ is denoted $\\Delta (\\mathcal{S}, \\boldsymbol{\\theta}) = \\max_{\\mathcal{S}’ \\in \\mathcal{I}} r(\\mathcal{S}’,\\boldsymbol{\\theta}) - r(\\mathcal{S},\\boldsymbol{\\theta})$. The guarantees in the paper are stated in terms of the minimal and maximal suboptimality gaps, defined as,\n\\begin{align*}\n\\Delta_{\\min} (\\boldsymbol{\\theta}) &= \\min_{\\mathcal{S} \\in \\mathcal{I} : \\Delta (\\mathcal{S} , \\boldsymbol{\\theta}) > 0} \\Delta (\\mathcal{S} , \\boldsymbol{\\theta}),\n\\end{align*}\n\\begin{align*}\n\\Delta_{\\max} (\\boldsymbol{\\theta}) &= \\max_{\\mathcal{S} \\in \\mathcal{I}} \\Delta (\\mathcal{S} , \\boldsymbol{\\theta}),\n\\end{align*}\nWhich respectively capture notions of identifiability, and scale for the reward functions.\n\nExisting work such as that of \\cite{wang2018thompson} has focused on the optimization oracle which for a given parameter estimate $\\boldsymbol{\\theta}$ returns an optimal super-arm, $\\textsf{Alg} (\\boldsymbol{\\theta}) \\in \\arg\\max_{\\mathcal{S} \\in \\mathcal{I}} r(\\mathcal{S}, \\boldsymbol{\\theta})$. This requires solving an extremely large combinatorial problem over $\\mathcal{I}$, which is typically computationally intractable; there are a plethora of NP / approximation hardness results for solving these problems, typically depending on the structure of $r(\\cdot,\\boldsymbol{\\theta})$ or $\\mathcal{I}$. This paper proposes algorithms for this problem in settings where the reward function is structured, and it is possible to circumvent the necessity of such computationally intractable oracles.\n\nThe paper essentially imposes four assumptions on the structure of the super-arm,\n\n- **[A1.]** **The reward function $r(\\mathcal{S}, \\cdot)$ is $M$-bounded and $B$-Lipschitz continuous.** Namely, $r(\\cdot, \\cdot) \\in [0,M]$ pointwise and $|r(\\mathcal{S}, \\boldsymbol{\\theta}) - r(\\mathcal{S}, \\boldsymbol{\\theta}') | \\le B \\| \\boldsymbol{\\theta}\\_{\\mathcal{S}} - \\boldsymbol{\\theta}'\\_{\\mathcal{S}} \\|\\_1$ where the notation $A_{\\mathcal{S}}$ indicates restriction to the set $\\mathcal{S}$ (this needs to be clarified in the paper).\n- **[A2.]** **The reward function is monotone.** Namely,\n    \\begin{align*}\n        \\forall \\boldsymbol{\\theta} \\in [0,1]^m, \\quad \\forall \\mathcal{S}\\_1 \\subseteq \\mathcal{S}\\_2 \\subseteq [m],\\ r(\\mathcal{S}\\_1, \\boldsymbol{\\theta}) \\le r(\\mathcal{S}\\_2, \\boldsymbol{\\theta}).\n    \\end{align*}\n    This assumption is only meaningful when $\\mathcal{I} \\subset 2^{[m]}$, since otherwise, the optimal arm must be $\\mathcal{S}^\\star = [m]$ and independent of $\\boldsymbol{\\mu}$.\n- **[A3.]** **The CDF of $\\Delta_{\\min} (\\boldsymbol{\\mu})$ is known.** The paper does not clarify the source of randomness in this distribution, but upon further reading, it appears that $\\boldsymbol{\\mu}$ is drawn from a prior, and the CDF is computed with respect to this prior.\n- **[A4.]** Lastly, but perhaps most crucially, **the reward function is separable.** For any $\\boldsymbol{\\theta} \\in [0,1]^m$ and any optimal arm $a \\in \\mathcal{S}^\\star (\\boldsymbol{\\theta})$ and any other arm $a' \\not\\in \\mathcal{S}^\\star (\\boldsymbol{\\theta})$, for any $\\mathcal{S} \\subseteq [m] \\setminus \\\\{ a,a' \\\\}$,\n    \\begin{align} \\tag{1}\n        r ( \\mathcal{S} \\cup \\\\{ a \\\\} , \\boldsymbol{\\theta}) - r ( \\mathcal{S} \\cup \\\\{ a' \\\\} , \\boldsymbol{\\theta}) > 0.\n    \\end{align}\n    This structure means that the optimal super-arm for a given $\\boldsymbol{\\theta}$, for instance, can be constructed simply by picking the top $K$ out of $m$ arms as measured by the score $r ( \\\\{ a \\\\}, \\boldsymbol{\\theta} )$.\n\nThe paper establishes bounds on the regret and the computational complexity of a quantized Thompson sampling + group testing based approach for the problem. The bounds are slightly uninterpretable, but have the important characteristics: the group-testing algorithm only carries out $\\log(m)$ tests (i.e., queries of $r (\\cdot , \\boldsymbol{\\theta})$). The computational complexity is still $\\Omega(m)$, since it relies on estimating a score across all $m$ arms. The regret scales as $\\log(T)$, which is the right scaling for this problem, assuming separability-like conditions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "### Additional comments\n\n- The notion $Q(\\cdot)$ is reused between the quantization function, as well as the observations in each round. It is probably a good idea to use different notations for the two.\n- Theorem 1 should not state ``the average regret conditioned on $\\boldsymbol{\\mu}$'': it is my understanding that this is a Bayesian setting and the $1-2 \\gamma$ success probability also includes events which are functions of $\\boldsymbol{\\mu}$ drawn from the prior. Eq. (20) in the paper relies on treating $\\boldsymbol{\\mu}$ as a random variable.\n- Fig 2c should label the Y-axis by average cumulative regret, since the cumulative regret cannot be decreasing.", "broader_impact_concerns": "This work proposes an algorithm of a theoretical nature and is not likely to raise any major ethical implications.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "kdXsIKqyeh", "reviewer": "Reviewer_PRDS", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n1.\tThe problem is well-motivated, focusing on reducing the oracle usage to optimize computational efficiency while maintaining regret guarantees.\n2.\tThe application of group testing in the CMAB setting is novel and clever, leading to exponential reductions in oracle complexity without compromising regret bounds.\n3.\tThe paper is clearly written and technically sound, presenting theoretical analysis and empirical validation.\n\n**Weaknesses**\n\n1.\tAssumption 5 requires knowledge of the distribution $F_{\\mu}$ of the minimum reward gap $\\Delta_{\\min}$, which is typically unknown in real-world scenarios. Although the authors avoid using this distribution directly in the algorithm and only assume access to its quantile for analysis (e.g., $\\Delta = F_{\\mu}^{-1}(\\gamma)$), it would be valuable to include a discussion on how $F_{\\mu}$ (or a lower bound on $\\Delta_{\\min}$) could be estimated in practice—possibly via heuristics. Moreover, an ablation study evaluating the impact of inaccurate $\\Delta$ on regret would make the results more robust and actionable.\n2.\tExperimental evaluation could be improved. The current synthetic setting feels somewhat artificial. The authors are encouraged to incorporate more realistic datasets, such as Yelp or MovieLens, to better reflect real-world arm distributions and validate the algorithm’s performance in practical applications. Moreover, more baselines should be added such as CUCB [1] and variance-adaptive UCB [2,3]. \n3.\tRelated work is missing several recent advances in CMAB with semi-bandit feedback using UCB algoirthms [1, 2, 3, 4] and TS [5] algorithms. The authors should add these new references (but not limited to these) to enhance the timeliness of the work.\n\n[1] Wang, Qinshi, and Wei Chen. \"Improving regret bounds for combinatorial semi-bandits with probabilistically triggered arms and its applications.\" Advances in Neural Information Processing Systems 30 (2017).\n\n[2] Merlis, Nadav, and Shie Mannor. \"Batch-size independent regret bounds for the combinatorial multi-armed bandit problem.\" In Conference on Learning Theory, pp. 2465-2489. PMLR, 2019.\n\n[3] Liu, Xutong, Jinhang Zuo, Siwei Wang, Carlee Joe-Wong, John Lui, and Wei Chen. \"Batch-size independent regret bounds for combinatorial semi-bandits with probabilistically triggered arms or independent arms.\" Advances in Neural Information Processing Systems 35 (2022): 14904-14916.\n\n[4] Merlis, Nadav, and Shie Mannor. \"Tight lower bounds for combinatorial multi-armed bandits.\" In Conference on Learning Theory, pp. 2830-2857. PMLR, 2020.\n\n[5] Perrault, Pierre. \"When combinatorial thompson sampling meets approximation regret.\" Advances in Neural Information Processing Systems 35 (2022): 17639-17651.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the combinatorial multi-armed bandit (CMAB) problem with semi-bandit feedback and cardinality constraints, addressing the practical challenge that most existing CMAB algorithms assume access to an exact optimization oracle, which may be computationally infeasible. To mitigate this, the authors propose a novel approach that combines group testing for efficient super arm selection with quantization techniques for parameter estimation. Under a probabilistic separability assumption, they design a new Thompson Sampling algorithm that matches the regret bound of the Combinatorial Thompson Sampling (CTS) algorithm by Wang and Chen (2018), while reducing the number of oracle calls from $O(m)$ to $O(\\log m)$. Theoretical findings are validated with empirical experiments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1.\tAdd discussion on how to estimate $F_{\\mu}$ or lower bounds on $\\Delta_{\\min}$, and include an ablation study on the impact of inaccurate $\\Delta$ in the algorithm.\n2.\tInclude experiments on more realistic datasets (e.g., Yelp, Movielens) to better assess performance in practical settings.\n3.\tUpdate the related work section to incorporate recent advancements in CMAB, particularly those addressing semi-bandit feedback and using UCB or Thompson Sampling approaches.", "broader_impact_concerns": "This is a theoretical work and there is no concerns on the ethical implications of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "mGVKy6bxQk", "reviewer": "Reviewer_EQq6", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n1. The paper presents a novel combination of group testing with Thompson sampling, which to my knowledge has not been explored in the CMAB context.\n2. The proposed GT+QTS algorithm provides an exponential reduction in oracle complexity while achieving a regret comparable to state-of-the-art methods.\n3. The authors introduce a \"quantized reward function\" to ensure the separability assumption, which is a neat trick, with some caveats (see below)\n4. The paper proves that GT+QTS achieves roughly the same regret as exact-oracle-based methods\n5. The complexity of existing oracle-based approaches grows exponentially with the number of arms, while GT+QTS reduces it to logarithmic complexity\n6. The paper is reasonably well organized and well written\n\nWeaknesses\n\n1. The algorithm relies on Assumption 6 (separability of the reward function), which may not hold in practical scenarios, and is only probabilistic (meaning that in cases where the assumption fails, the algorithm could lead to suboptimal selections). While the authors introduce quantized rewards to address this limitation, it is not clear to me how sensitive the method is to different quantization levels\n2.  The experimental setup considers only two types of reward functions: Linear rewards and Neural-network-based nonlinear rewards. Although these choices are reasonable, more diverse reward functions (e.g., submodular rewards or real-world application settings) would strengthen the empirical validation.\n3. The experiments focus on regret performance, which is great, but it would be useful to also quantify the effect of quantization on arm selection errors\n4. The real-world implications of the group testing framework for CMABs are not fully discussed.\n5. While the approach is computationally efficient, how would it perform in dynamic environments where reward distributions shift over time? (This does not need to be solved, but at least discussed and it would be nice to have some conjectures or educated guesses on it)\n6. The algorithm introduces additional hyperparameters, such as the quantization level $\\Delta$ and the probability $p$ of including arms in group tests. More guidance on tuning these parameters would be beneficial.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces a novel approach to the Combinatorial Multi-Armed Bandit (CMAB) problem by integrating group testing (GT) with \"quantized Thompson sampling (QTS)\" for super-arm selection. The claimed motivation is to replace the exact oracle used in existing methods with a more computationally efficient alternative. The authors propose the GT+QTS algorithm, which reduces the computational complexity of the oracle while maintaining a near-optimal regret. The theoretical analysis is supported by numerical experiments comparing GT+QTS to existing methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Expand on the effect of quantization on arm selection errors (theoretically and/or empirically)\n2. Expand on the real-world implications of the group testing framework for CMABs\n3. Discuss (conjectures are fine, no need to add results) on your approach would perform in dynamic environments\n4. Expand on how to tune the hyperparameters you introduce.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers the problem of combinatorial multi-armed bandits with semi-bandit feedback and proposes a new, more realistic alternative to the "perfect oracle" assumption by combining a group-testing routine for selecting the super-arms and Thompson sampling (TS) for parameter estimation. Under a general separability assumption on the reward function, the proposed algorithm reduces the complexity of the super-arm-selection oracle to be *logarithmic* in the number of base arms while achieving the same regret order as the state-of-the-art algorithms that use exact oracles. 

Overall, all reviewers were positive about this submission, especially highlighting the novelty of the group testing + TS approach in the combinatorial MAB context, the attractive exponential reduction in computational complexity while preserving regret bounds that hold under the perfect oracle assumption, and the high quality of writing and exposition in the paper. Multiple reviewers did critique the initial experimental setup in the paper to be limited -- the authors made a substantial effort to address this concern including running more extensive simulations of computational complexity vs regret and experiments on real-world datasets, which largely addressed these concerns. The authors also made some more minor revisions to discuss some implications of their results and expand on certain assumptions made in the framework (e.g. the separability assumption). One concern that was not addressed by the authors was the perception by one reviewer that the separability/monotonicity assumption on the reward function is rather strong. After the author revision and response, all reviewers are in favor of acceptance. Given all of this, I believe this paper meets the bar for publication at TMLR in its current form.
Decision: Accept (poster)