Stochastic bandits with groups of similar arms.
Authors: Fabien Pesquerel
Hassan SABER
Odalric-Ambrym Maillard
Venue: NeurIPS 2021 Poster (2021)
Keywords: Multi-armed Bandit
Indexed Minimum Empirical Divergence
Structure
Regret analysis
dependent arms

Abstract: We consider a variant of the stochastic multi-armed bandit problem where arms are known to be organized into different groups having the same mean. The groups are unknown but a lower bound $q$ on their size is known. This situation typically appears when each arm can be described with a list of categorical attributes, and the (unknown) mean reward function only depends on a subset of them, the others being redundant. In this case, $q$ is linked naturally to the number of attributes considered redundant, and the number of categories of each attribute. For this structured problem of practical relevance, we first derive the asymptotic regret lower bound and corresponding constrained optimization problem. They reveal  the achievable regret can be substantially reduced when compared to the unstructured setup, possibly by a factor $q$. However, solving exactly the exact constrained optimization problem involves a combinatorial problem. We introduce a lower-bound inspired strategy involving a computationally efficient relaxation that is based on a sorting mechanism. We further prove it achieves a lower bound close to the optimal one up to a controlled factor, and achieves an asymptotic regret $q$ times smaller than the unstructured one. We believe this shows it is a valuable strategy for the practitioner. Last, we illustrate the performance of the considered strategy on numerical experiments involving a large number of arms.

Stochastic bandits with groups of similar arms
Fabien Pesquerel"
Odalric-Ambrym Maillard hassan saber@inria.fr catrric.mallarrdinnn fr
Hassan Saber
fabien. pesquerrelinnia.frr
Univ. Lille, CNRS, Inria, Centrale Lille, UMR 9198-CRISIAL, F-59000 Lille, France
Abstract
We consider variant of the stochastic multi-armed bandit problem where arms known to be organized into different groups having the same mean. The groups are unknown but lower bound q on their size is known. This situation typically appears when each arm can be described with list of categorical attributes, and the (unknown) mean reward function only depends being redundant. In this case, q is linked naturally to the number of attributes considered redundant, and the number of categories of each attribute. For this structured problem of practical relevance, we first derive the asymptotic regret lower bound and corresponding constrained optimization problem. They reveal the achievable regret can be substantially reduced when compared to the unstructured setup, possibly by factor q. However, solving exactly the exact constrained optimization problem involves a combinatorial problem. We introduce lower- bound inspired strategy involving a computationally efficient relaxation that is based on sorting mechanism. We further prove it achieves a lower bound close to the optimal one up to controlled factor, and achieves an asymptotic regret times smaller than the unstructured one. We believe this shows it is valuable strategy for the practitioner. Last, we illustrate the performance of the considered strategy numerical experiments involving large number of arms.
subset of them, the others
Introduction
The finite stochastic multi-armed bandit problem is a popular framework for studying sequential decision making problems in which learner sequentially samples from a finite set of distributions called arms. It was first introduced in the context of medical trials [Thompson] 1933b 1935 and later formalized under this name by Robbins in Robbins
[952]. We refer the interested reader to Lattimore and Szepesvári [2020) for recent survey. This is one of the simplest theoretical framework in which one can study the notion of exploration-exploitttio tradeoff. This tension between exploration and exploitation arises from the sequential optimization problem learner is trying perform while being uncertain about the very problem it optimizing.
Formally, a multi armed bandit configuration is specified by a set of unknown real-valued probability distributions v = (Ma)aELA with means (Ja))ε.A, indexed by a set of arms A. hereafter consider finite A. and that all v.. E A belong to the same family of distributions F (e.g. Bernoulli, Gaussian, etc.), that an arm a, E A based on the past observations and decisions, then receives and observes sample X. (called the reward), conditionally independent, sampled from Va,, Her goal is to maximize the cumulative reward received over time. The mean of each arm is unknown, which makes the problem non-trivial, hence the learner should adjust her sampling strategy based on past information obtained from drawing different arms in order to maximize the expected sum of rewards. The maximal expected value of a finite bandit configuration is denoted by μ., defined as μ4, = max Ha. The aEA
E JAA The bandit game proceeds as follows. At each time E N, the learner chooses
performance of the strategy used by the agent is measured by the (pseudo) regret, that compares the
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

expected sum of rewards obtained by an oracle that would constantly pull an optimal arm and the ones obtained by the learner, up to some time horizon T (that we assume unknown the learner..
Definition 1 (Regret). The regret incurred by sampling strategy after T time steps bandit configuration v is given by:
T (oa--Moa))) Hoi)
)
R (v, T) = Ey
Σ (ur
Σ
(ur - (aa) Ey (No(T)),
aEA
where Na(T)= Σ Tia = a) denotes the number of selection of arm a after T time steps.
Group of similar arms Motivated by various practical reasons, one may want to restrict to a subset B C. FA of allowed bandit configurations instead of the full set F-A, In this paper, we study a variant of the multi-armed bandit problem in which the reward function, μr E A + Pa, is assumed to satisfy a cluster-like structural property. A bandit configuration v is said to satisfy the q-equivalence property if for every arm E A, there are at least q distinct arms having the same expected value:
Va E A, Ma' E Aluaa - -a)) 7 q-
Assuming the set of arms A and base distributions D are known to the learner, we denote by By the set of bandit configurations having the qrequivalence property. We also denote by B3 (1) the set of all expected values in By. Formally, By (u) is the image of Bg under the μ mapping.
Definition 2 (Arm equivalence and equivalence class). Given a bandit configuration v. two arms a, a' E A are said to be equivalent if their associated distributions have the same expected values:
a ~ d' & Ha Mar
An equivalence class in v is a maximal subset of arms in A having the same mean, i.e., for all arms a' in Paa = Paa and for all arm E e and u' E E \ G. Pa & Paa
This situation typically appears in practical situations when each arm can be described with a list of categorical attributes, and the (unknown) mean reward function only depends on subset of them, the others being redundant. In this case, q is naturally linked to the number of attributes considered redundant (or useless descriptors), and the number of categories of cach attribute. Precisely, = -ITER C where R is the set of redundant attributes and e, the number of categories for attribute The learner may know that there exists such structure while not knowing closed form formula mapping the list of categorical attributes to the significant subset. In this case, might be lower bound on the sizes of the class since the set R might not be the largest possible or because the number of redundant attributes depends on the number of relevant attributes. In all cases, the smallest possible number of redundant attributes can be naturally linked q. We hereafter consider the learner only knows g but would like to exploit the prior knowledge of this structure in bandit problem.
Regret lower bounds overview In order assess the performance of bandit algorithm on set of configurations B, one naturally studies the best guarantee achievable by a uniformly efficient algorithm on B, i.e with sub-linear regret on any instance v E B of the bandit problem. When B = F.A,A such a guarantee was first provided by Lai and Robbins [1985) for parametric families F, and then extended by Burnetas and Katehakis [1966] for more general families. It states that any algorithm that is uniformly efficien on family of distributions FF must satisfy
lim inf T-000 log(T)
R(v,T)
Σ
Mo (=(uallut) KF((allu*))
H.
= inf [KL(v. GEF
(I)
Rip 2420
This popular result entails that any strategy having the desirable property to have sub-linear regret on any instance in F must incur a non-trivial minimal regret. When B is strict subset of JF.A, the bandit problem is called structured, as this case pulling an arm may reveal information that makes it possible to refine estimation of other arms (e.g. think of the set of bandit configurations having Lipschitz mean function with respect to A C ) The presence of structure may considerably modify the achievable lowest regret, as shown in Burnetas and Katehakis 1996) and Graves and Lai
Formally, for each bandit on F. for each arm l with As > O, then ([N) =o("") for all a (0, 1].

---

1997]. who extended the (unstructured) lower bounds to arbitrarily structured bandit problems (and
R T) 2 Cz(v), where (v)) is
beyond). These lower bound take the generic form lim inf
lTg(T)
constant term solution of a constrained linear-optimization problem. A bandit algorithm is then called asymptotically optimal for a set when its regret asymptotically matches this lower bound.
Existing strategies In order to minimize the regret, learner faces the classical explo- ration/exploitation dilemma: it needs to balance exploration, that is gaining information about the expected values of the arms by sampling them, and exploitation, that is playing the most promis- ing arm sufficiently often. Many algorithms have been proposed to solve the multi-armed bandits problem (see Lattimore and Szepesvári (2020) for survey). The study of the lower bounds had a crucial impact on the development of provably asymptotically optimal strategies. In the case of unstructured bandit B = F.AA this includes strategies that build on the concept of Optimism in Face of Uncertainty (the most celebrated of which being the Upper Confidence Bound (UCB) algorithms Agrawal 1995]. , Auer et al. (2002), such as KLUCB [Lii 1987 Cappp et al. 2013 Maillard| 20188).
DMED and IMED Honda and Takemura (2011] 2015]. that are proven asymptotically optimal for various families Fe.g. one-dimensional exponential families), and directly exploit the lower bound in their structure. Alternative asymptotically optimal strategies include the Thompson Sampling (TS)
Thompson [1933a], Agrawal and Goyal [2012). which uses a Bayessia posterior distribution given a specific prior, whose optimality was shown in Korda et al. [2013]. See also Kveton et al. [2019]
for other randomized algorithms and Kveton et al. 2020), Chan 2020), Baudry al. [022 for
recent non-pann oo--amametric extensions using re-sampling methods. Further, some authors also allow many optimal arms, see de Heide et al. [2021], or even countably many arms, see Kalvit and Zeevi 2202).
However, these works do not consider nor exploit constraint on the level-sets of the mean function and follow an optimistic paradigm while we follow an information minimization targeting optimality. On the other hand, several instances of structured bandits received considerable attention in the last few years. This the case for instance of linear bandits, see [Abbasi- Yadkori et al. 2011] Srinivas
et al. 2010, Durand et al., 2017 K veetn et al., 2020 and Lattimore and Szepesvari [2017]. Lipschitz
bandits Magureanu et al. 2, Waag et al. [0020]. Lu et al. [201]]. unimodal bandits Yu and
Mannor [2011),Comber Combes and Proutiere 2014), Saber et al. [2200] or combinatorial bandits Kveton
ctt al. 20155] Magureanu| (0118) and more recently Cuvelier et al. 20221b. A generic asymptotically
optimal algorithm, called OSSB (Optimal Structured Stochastic Bandit), has been introduced in the
work of Combes et al. [017]] and proven to be asymptotically optimal for all structures satisfying
some weak properties that include all the aforementioned structures. Although being asymptotically optimal this algorithm often suffers from a long burn-in phase that may hinder its finite practical performance. It further comes with high computational price as it requires to solve empirical
version of the optimization problem (v) at each step. This motivates the quest for alternative specific structure. Inspired by combinatorial structures for which computing (v() is simply not feasible, a relaxation of the generic constrained optimization problem was recently proposed in Cuvelier et al. [2021a). The authors show that this comes at the price of trading-off regret optimality for computational efficiency. Indeed in some structure, combinatorial properties are at stake and asymptotically optimal algorithms may require solving combinatorial optimization problems (see Cuvelier et al. (2021a]) related Cv(v). In order to
strategies, perhaps less generic but better suited
to exploit the combinatorial structures in a numerically efficient way, research has been made in how to relax these combinatorial optimization problems while preserving theoretical properties on the regret of the relaxed algorithms (see Cuvelier et al. [202Tbaa) ). Our work consider similar computational issues, with a different perspective.
Goal For the structure By as we show in Theorem I below, the term Cs, (v) unfortunately makes appear in general combinatorial optimization problem. This makes resorting to OSSB or any strategy targeting exact asymptotic optimality a daunting task for the practitioner. In this paper, our goal is to provide a computationally efficient strategy adapted to the structure B.p that is able to reach optimality up to controlled error term.
Outline and contributions The rest of this paper is organized as follows. In section 2, we derive a lower bound on the regret for the structured set bandit configurations B,,. This bound makes appear two components, one that we call non-combinutoriul as optimizing it can be done efficiently, and second term that we term combinatorial as involves solving a combinatorial problem. Interestingly, using in Lemma I and Theorem 3 that the contribution of the combinatorial part of the lower bound
3

---

can be controlled. Owing to this key insight. we introduce in section B IMED-EG an adaptation of the IMED strategy from HHonda and Takemura 2013] the structured set B. One advantage of IMED over KI.-UCB alternative is its reduced complexity, which translates to the equivalence class setup. At each time step, the complexity of computing the next arm to be pulled by IMED-EC is no more than the one of sorting list of |A| elements once the IMED indexes have been computed, which is only log |A| times larger than looking for the minimal IMED index. In Section 4 we prove that IMED-EC achieves a controlled asymptotic regret that matches the non-combinatorial part of the lower bound and is at most (less than) a factor of 2 times the optimal regret bound. Last, we illustrate the benefit of the IMED-EC over its unstructured version in section where it shows substantial improvement. Our experiments also highlights the robustness of the algorithm to a misspecified parameter q, which is a desirable feature for the practitioner.
2 A regret lower bound with combinatorial and non-combinatorial parts
In this section, we derive a lower bound on the number of pulls of suboptimal arms that involves a combinatorial optimization problem. Using that lower bound, we derive a simple algorithm, IMED-ES EE,, that does not involve any optimization problem. While not being asymptotically optimal, we will show in the next section that our algorithm has an upper bound on its regret that is no more than a fraction of the unstructured regret.
The proof of Theorem is based on the concept of most confusing instance. Most confusing instances allow to assess the intrinsic difficulty of a bandit problem and allow to compute lower bounds on the number of times suboptimal arms are pulled. The lower bound informs us on the minimal amount of exploration one needs to do to solve a bandit problem. More formally, a confusing instance v' associated to a suboptimal arm for a bandit problem is bandit instance with the same set of arms as the original one, but in which faa has been changed to 24ر > M.+ An optimal sampling strategy (one that does not sample suboptimal arms too much) should behave differently on the two problems. Studying this difference, we can compute the minimal amount of exploration performed by an optimal strategy on arm the original problem v. Doing so for all suboptimal arms allows to bound the number of samples of suboptimal arms and therefore characterize the intrinsic complexity of bandit instance v.
In structured setting, a confusing instance also has to respect the structure. In our case, it means that a confusing instance cannot have a class with less than q arms We will therefore consider confusing instances associated to classes rather than individual arms.
Definition 3 (Confusing instance). Given a bandit configuration v E BB. a real number À and subset Cg S of q equivalent arms in v, we denote by Bg (v. Cq. X) the set of all bandit configurations having the same sel of arms and such that for all v' E B, (v, Cap X), v' E B, and for every arm a in Cup 16g 2 X.
When X >> phs, and cy is a subset of a suboptimal class, a bandit configuration in Bg (v, Cq: A) is called a confusing instance of v.
Similarly to the notation introduced above, we will use the notation Bg (u, Cup A) to specify the set of means of bandit configurations in By (μ,, Cg. X).
The aim of an asymptotic lower bound on the number of pulls of suboptimal arm is to mathematically understand the minimal asymptotic amount exploration an algorithm should perform.
The family F is such that for all K E F. KC (к|]μ) and μ r Keg [p) are continuous, where (Kg(K, p)) infeer (KL(K, E)) with KL being notation for the relative entropy or Kullback-Leibler divergence.
Assumption 1:
The family F is an exponential family of dimension 1. Therefore the KL di- vergences are parameterized by the mean and we may write the KL as a function of the means, YK. X E F, KL (Mllx) = KL (Ex*x (X) ||Ex~x (X)) (identification of the KL with its parameteri- zation by the means).
Assumption 2:
Theorem (Asymptotic lower bound). Let q E N. be a positive integer and u E B, be a bandit configuration having the q-equivalence property. Let e C. A be a suboptimal equivalence class in

---

Assuming uniform consistency. for all suboptimal arms a,
Na(TT
Ya > O, lim
(Ta Ta
T-++o
assuming assumption I, we have the following asymptotic bandit dependent lower bound the number of pulls of arms in c:
min E () (vall)) + CEE4
inf E BN(a(()) Keg ('E,,( agtz
in T-000
3 1, (2)
log T
where cy is any subset of e having q distincts arms within it.
We briefly sketch how confusing instances are used in the proof of Theorem [ We consider confusing instances in which arms from suboptimal class mean). there are g arms in the class, then there are no remaining arms to move. If there are more than 2q arms, then moving q confusing instance respects the equivalence structure. However, there are between q + and 29 - 1 arms, then the reminder is of size larger than but strictly smaller than The created confusing instance does not respect the equivalence structure and we have to deal with the arms in the reminder (the infimum of equation 2). There are |c| choose q possible choices to g arms from class (the minimum of equation (2)
moved above the optimal one (w.r.f the
creates reminder of size larger than g meaning that the crafted
All in all, the lower bound involves a combinatorial optimization problem.
While this lower bound involves combinatorial optimization term, can distinguish between two regimes depending on the size of the suboptimal class. The combinatorial regime and the non combinatorial regime.
Non-combinatorial regime For a suboptimal class c, if |c| = q or |c| > 2q, then the lower bound reduces to
min Σ E. (Na(T)) (vallue) aEE
lim inf T-+00
2
log T
because the reminder is of size larger than and the infimum from Theorem disappears Indeed, the infimum is always 0 as this quantity can be obtained by choosing p², Furthermore, the minimum over all q-partitions of in fact the of the smallest elements of {EE, (Na(T) K> (Pallp)))ass ase The search amongst all the q-partitions of e amounts to a research of the q smallest elements which is not more complex than sorting a list of icl elements. Hence, the prob- lem is more combinatorial optimization one and call this the con-combinatorial regime.
for all E c Gy-
Lemma 1. Let Bg be a bandit configuration having the q-equivalence property. Let e be suboptimal class in the non-combinatorial regime, then, under assumption 1 and 2,
Σ EE (Na(T))
[cl q Kr (vallA)
lim inf T-200
log T
While we do not have information about individual number of times arm in class has been sampled, Lemma [ roughly tells us than on average, the lower bound on the minimal amount of exploration of an arm in a suboptimal class has been divided by q.
Lemma 2. If all suboptimal classes are in the non-combinatorial regime, under assumption and the regret may be asymptotically lower bounded by
lim inf T-000
Ru, T)
Σ dEAVA.
H. Pa KF (vallA))
(4)
log
Lemma informs us that the non-combinatorial regime, the classical lower bound on the regret given by equation ( has been divided by q.
5

---

Combinatorial regime For a suboptimal class e to be in the combinatorial regime, we need q < |c| < 2q. since the reminder is such that 0 < |c \ cyl < q and the infimum in Theorem iis not In that case, the lower bound 2 involves combinatorial optimization problem. Two difficulties arise from the term
inf 1r ((EB,() a404
Σ By (Na(T)) (Vollr))-
First, while we could have thought that summing on the reminder Co would be enough, the summand has to be on a & Cq as whole. Indeed, the residual с > Cq may be of size q meaning that it might cost less move an arm from another class the residual in order to complete rather than moving all the reminder. Second, while we could have thought that moving elements from one class of to another might be enough, the infimum has be taken on B, (jt. Cg. A). Ay) Indeed, the residual Cy may be of size q and the nearest class might be of size exactly q. In this case, it may cost less to move all the 2g rather than merging one of the two with the other.
distributions in between the two classes and create a new one
Lemma 3. Let U E Bu be bandit configuration having the g-equivalence property and e. be suboptimal class in the combinatorial regime. Then, under assumptions and 2,
EE (Na(T))
lim inf aEc T0000
(5)
log
K (Valll))) + To
I min Keg (Va (
Σ Ey (N)(T)
lim inf
(6)
T-00c
log T
2y aEc
KrF (Vaaall)))
Those equations be compared to the equation (3) from the non-combinatorial regime. We emphasize the fact that the lower bounds given by equations (5) and (6) are not the largest possible
lower bound and hence do not provide much information about the algorithmically achievable regret as the largest one given by equation (2). However, together with a regret upper bound on
the algorithm IMED-EC, those quantities will help us control the asymptotic discrepancy between IMED-ECT regret and the asymptotic lower bound given by Theorem
3 Information Minimization for bandits with equivalence class
The algorithm we present, IMED-EC, depends on the (weak) indexes introduced in the IMED paper by Honda and Takemura 2015). At each time step i, for each arm a E A. we can compute its IMED index as
(t) (t) (Pa (+)ll(())) + log (t),,,
where (t) max (t) and for each arm E A. (t) is the empirical mean of arm computed with samples from this arm collected up to time t, Poo (1) W.(T) Σx=1 X,1 {a, a}. where X, the sample collected by the algorithm at time step 8. Let u E B, be bandit configuration having the g-equivalence property. We denote by (t) arg max (t)( the set of empirical optimal arms at time f. We will denote by (t) the set of arms having the & smallest IMED indexes (breaking ties randomly that this has size q). We will also consider the two following quantities for each time t:
I
(*(1)= min (EAA(t)
Ia(1) min log No((),
aEA-(t)
((t) min A'CA [1'l= a'E.A'
Σ (t)
Σ la())
a'EAA(
[tt) can be computed efficiently by summing the q smallest elements of the list of IMED indexes. Finding the q smallest elements can be done by maintaining a sorted array of IMED indexes while computing them. The procedure costs a constant factor of log [A]. Computing I(I) therefore costs O (I-A) log [Al). which is only log |A| times larger than looking for the minimal IMED index. Computing A. (t)) can done by maintaining set of arms having the best empirical mean (adds constant factor). The IMED-EC algorithm is presented in Algorithm

---

Algorithm IMED-EC (IMED for Equivalent Classes)
Pull each arm once
for t = |AI.... 7 do
if (t) [(t) then
Pull 04+1 E arg ( (a(t) (chosen arbitrarily)
else
Pull 0++1 E mi) (a) (chosen arbitrarily)
end if
end for
While the orginal problem involves combinatorial quantities, those are not involved in the IMED-EC algorithm. From time complexity viewpoint, this makes this algorithm on par with other popular algorithms such as UCB, KLUCB, and IMED algorithm. On the contrary, the general structure algorithm OSSB involves solving a combinatorial optimization problem at cach time step, which makes numerically inefficient. We are not aware of any general relaxation method for this algorithm that we could compare IMED-EC with. interesting to note that in the case where 1, the IMED-EC algorithms coincide with the IMED algorithm.
Intuition For an arm a, (a( (Pa(t) (t) may be interpreted as the opposite of log- likelihood of optimality of that arm. log (t (t) is linked to the log-frequency of play of that arm, the frequency of play of an arm being interpreted as the probability of pulling that arm is sequence of length t. The IMED algorithm thus can be intuitively understood as an algorithm matching an empirical log-pre probaabbbiltyy with a log-frequence of play. In our setting, there is at least q elements in each group. It therefore makes sense to test for the optimality of a group rather single elements. Since arms are independent,
makes sense to sum the log-likelihood of optimality on all the g-partitions of the set of arms. Since we have the intuition that this first part is the logarithm of a product of probability, we may compare it to the product the frequencies. Therefore, we get that important quantities are the sum of IMED indexes for each & partition of the arms, seen comparison between the optimality of this group of q elements and the associated frequency of play of that group. The minimal IMED index is the one whose frequency of play is the lowest compared to its likelihood of optimality, similarly for the sum of IMED indexes. Other intuitions regarding the faimess (frequency of pulls within the same class) of the algorithm are given in appendix D
4 Regret analysis
In this section, we now detail the main bound on the regret of IMED-EC.
Theorem 2 (Upper bound on the number of pulls). Under the IMED EC algorithms, under assumption I and the number of pulls of a suboptimal arm a upper bounded by:
log T
Ey (Na(T)) & qKCr (vallu.) (1+ + f(e),
where 0 < < min (u, - pa), f is function that depends on concentration properties on F. and tends to 0 as E tends to 0.
Remark: and f functions are mostly used for deriving theoretical guarantees in IMED-EC regret analysis. a is controlled thanks to property 2 as in the paper Hondd and Takemura (2015) for IMED regret analysis. A finite sample analysis can be derived from careful analysis of the term f. Being more precise requires scrutinizing the properties of the considered family.
Corollary 1. Under the IMED-EC EC algorithms, under assumptions I and 2, the number of pulls of a suboptimal arm is upper bounded by:
min CC
E Eu (N.
& (1 + (e)) log + g(E).
(8)
REAg
where 0 < <<EE minaEAAAA (M+ Po) and a tends to tends to 0.
7

---

Theorem 3 (Asymptotic upper bound on the number of pulls). Under the IMED- EC algorithus, under assumption and 2. the number of pulls of a suboptimal arm is asymptotically upper bounded by:
Ey (N)(T))
lim inf +-++0
log
qK,FF (Va (p.)
Discussion This upper bound shows that in particular, the number of pulls of suboptimal class, Eace Ey (NT( is asymptotically no more than (K=x(llll).) log T. This hence matches the lower bound in the non non-combinatorial regime. In the combinatorial regime, along with equation (6). this regret upper bound shows that
lcl
Ex (Na Σ agc
1 qKx (Vallp.)*
ld
iiminf
gK.s (Valla))
7-000
log T
2
proving that the regret of the proposed IMED-EC does not differ from the optimal lower bound by a factor more than 2. This is striking result. Equation (6) can be used to have
more precise control on the discrepancy to the optimal regret bound, as shows the factor can be actually replaced with O and 1 in the combinatorial regime that and the regret of IMED-EC indeed is always bounded by 2. On the other hand, this refined error measurement problem dependant while the factor of 2 is universal.
lel-c minneu [eal Since the factor Ic|-q (ng is strictly between Ky(P, [..] studying, the discrepancy between the lower bound
We provide the full proof of Theorem and Theorem in appendix @hheee we also discuss how to
weaken assumption 2 and still get the result of theorem
5 Experiments
In this section, we support our theoretical analysis by conducting three sets of experiments. The Python code used to perform those experiments is available on Githutf We support our empirical evidences using plots of cumulative regrets. In this section, all the experiments are conducted using gaussian distributions whose means are between 0 and and of unit standard deviation. Those graphs are representative of all the experiments that we conducted and more plots and experiments may be found in the appendix D
Balanced class, perfect knowledge In this set of experiments, see Figure [ we focus on the bandit configurations in which all equivalence classes have the same cardinality and assume that we know the number of elements per class. This setting is interesting for two reasons. First, one can compute the theoretical lowerbound without solving a combinatorial optimization problem. Second, the theoretical analysis shows that IMED-EC is asymptotically optimal in this case. This setting will thus allow us numerically grasp what happens in the most structured case. We compare IMED-EC to unspecialized bandit algorithm, UCB, IMED and KLUCB. To make the comparison fairer we also compare IMED-EB to OSSB, an algorithm specialized in structured bandit. Since OSSB has solve combinatorial optimization problem at each time step, we cannot carry experiments on large sets of arms while comparing IMED-EC it. In this particular setting, we see that while OSSB and IMED-EC are provably asymptotically optimal, IMED EC numerically performs better in finite time horizon. We recall that is furthermore numerically more efficient since does not involve any combinatorial optimization. Without too much surprises, IMED EC also outperforms unspecialized algorithm.
Imperfect knowledge In the experiment plotted Figure 2 we leverage the knowledge hypothesis and assume that we only know lower bound on the number of elements per class while the classes are still balanced. We compare IMED-EC to unspecialized bandit algorithm, IMED and KLUCB. We drop OSSB from our test bed due the computational burden of solving combinatorial optimization problem each time step. We can see that the finite time cunulative regret of IMED-EC indeed much smaller than the regret of the unspecialized a algorithms.
Influence the parameter q Here we show the numerical robustness of IMED-EB EC with respect to the lower bound parameter g the number of elements per classes. On the same bandit problem,
Bhugss/ghhhbbboom//bbeeeeeeeeees bandits- sotth--rouss-o--smmiiit -

---

Mean cumulative regret and quantiles [0.1] 0.9. 0.5]
Horzon 950 Nbr. of experiments 50
175
IMED R -2.0-R
150
Regret lower Bound
tegret
25-
0-
Time stop
Figure classes, distributions per class set of means {0.33, 0.5, 0.9)
Mean cumulative regret and quantiles 0.9.
Horizon experiments
KL-UCB R 515.19
IMED
500
IMED-EC-Q-2 q------2----
1000
2000
Figure 2: 7 classes, distributions per class set of means (0.1, 0.3,0.333444,03.3. 0.7, 0.9}
we compare different instances of IMED-EC where different values of are used, In the legend, opt. stands for optimal and corresponds to the largest valid lower bound the number of elements per class, iee. the minimal number of elements bandit problem with classes and uneven number of distributions per class. The smallest class has elements and the largest 23. While increases up to the minimum cardinality of a class, we that the performances of IMED-EC increases. is rather remarkable that once we go beyond that theoretical threshold, the performances of IMED-EC do not deteriorate. We even found it difficult find settings deteriorate them at all. While the expected regret does not seem deteriorate. we sometimes see that the tails of the regret widen as it can be seen on the plot Figure for 7 and q 20 since the 0.9 quantile curves are large for those values of q. We interpret part of this robustness to the fact that the relaxation induced in TMED-EC makes the algorithm over explore compared to what the true lower bound suggests. Increasing g reduces the exploration and therefore may improve the performances of the algorithm. However, this robustness is observed even in the case where the classes are balanced. This interpretation thus does not explain everything about numerical robustness of IMED-EC. This type of experiment does not take more than roughly 10 to 15 minutes on notebook run in Google Colab depending on the number of arms, the horizon and the number of runs. This supports the numerical efficiency of the relaxation made in IMED-EC.
class. The experiment Figure 3 performed on

---

regret quantiles
Horzzon 2500 Nbr. of expariments = 1000
IMED-EC
IMED-EC- qm4 (opt)- 129.47
MED-EC-q=) -0t-----=12.000000
IMEDECC- -------12--122-2 122.74
MED-EC-Q-20-11 --20----2220
Cumuletive tegret
200
100
1000
1500
2000 2500
Time step
Figure classes, unbalanced set of means = 0.6,0. 0.75,.0,,00..... 0.9}
6 Conclusion
In this paper, we introduced IMED-EC, a numerically efficient algorithm to solve a structured bandit problem for which we derived a lower bound involving combinatorial optimization problem. While not being asymptotically optimal, we proved that the asymptotic regret of IMED- EEC is always smaller than the unstructured one and that we can control the discrepancy with respect to the structured regret lower bound by a factor of at most 2.
Acknowledgments and Disclosure of Funding
This work has been supported by the French Ministry of Higher Education and Research, Inria, Scool, the French Agence Nationale de la Recherche (ANR) under grant ANR 1E-R-16-COO CE40000002 (the BADASS project) the MEL and the I-Site ULNE regarding project -000E-19000-APPPEEN The PhD of Fabien Pesquerel is supported by grant from École Normale Supérieure.
References
Y. Abhasi-Vadkorf D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pages 2312-2320, 2011.
R. Agrawal. Sample mean based index policies with O(log n) regret for the multi-armed bandit problem. Advances in Applied Probability, 27, 1995.
S. Agrawal and N. Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Proceedings of the 25th Annual Conference on Learning Theory, 2012.
P. Auer, N. Cesa-Bianche Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47, 2002.
D. Baudry, E. Kaufmann, and O.-. Maillard. Sub-sampling for Efficient Non-Parametric Ban- dit Exploration. NewrIPS 2020, Vancouver, Canada, Dec. 2020. URL httpss//hal suchhvves-ouvertee fr hwtr/hal-000 - 02977552
A. N. Burnetas and M. N. Katehakis. Optimal adaptive policies for sequential allocation problems. Advances in Applied Mathematics, 17(2):122-143) 1996.
O. Cappé, Garivier, O.-A. Maillard, R. Munos, and Stoltz. Kullhack-Leible upper confidence bounds for optimal sequential allocation. Annals of Statistics, 1163)1111--144,, 2013,, 2013.
10

---

H. P. Chan. The multi-armed bandit problem: An efficient nonparametric solution. The Annals of Statistics, 48(1):346-377 2020.
R. Combes and A. Proutiere. Unimodal bandits: Regret lower bounds and optimal algorithms. In International Conference Machine Learning, 2014.
R. Combes, S. Magureanu, and A. Proutiere. Minimal exploration in structured stochastic bandits. In Advances in Neural Information Processing Systems, pages 1763-1771,200
T. Cuvelier, R. Combes, and E. Gourdin. Asymptotically optimal strategies for combinatorial semi-bandits in polynomial time. In Algorithmic Learning Theory, pages 505-528. PMLR, 2021a. a.
T. Cuvelier, R. Combes, and E. Gourdin. Statistically efficient, polynomial-ting time algorithms for combinatorial semi-bandit, Proceedings of the ACM on Measurement and Analysis of Computing Systems, 5(1):1-31, 2021b.
R. de Heide, J. Cheshire, P. Ménard, and A. Carpentier. Bandits with many optimal arms. In Advances in Neural Information Processing Systems, 2021. URL hattps://arziis orgooogg/a... abaaaba////// /abs/2103... 12452
A. Dembo and O. Zeitouni. Large deviations techniques and applications. Elearn, 1998.
A. Durand, O.-A. Maillard, and J. Pineau. Streaming kernel regression with provably adaptive mean, variance, and regularization. arXiv preprint arXiv: 00768, 2017.
A. Garivier, P. Ménard, and G. Stoltz. Explore first, exploit next: The true shape of regret in bandit problems. arXiv preprint arXiv:160..07182, 2016
L. Graves and T. L. Lai. Asymptotically efficient adaptive choice of control laws incontrolled markov chains. SIAM journal control and optimization, 35(3):715-7433 1997.
J. Honda and A. Takemura. An asymptotically optimal policy for finite support models in the multiarmed bandit problem. Machine Learning, 85(3):361-391, 2011.
J. Honda and A. Takemura. Non-asymptotic analysis of a new bandit algorithm for semi-bounded rewards. Machine Learning, 16:3721-3756, 2015.
A. Kalvit and A. Zeevi. From finite to countable-armed bandits. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 8259-8269. Curran Associates, Inc., 2020. URL http:: http:ttst/s/rrrceeeiingg http://////000/o////////00000000
Pwwpcceappppppppppeeeeeee pdf
N. Korda, E. Kaufmann, and Munos. Thompson Sampling for 1-dimensional Exponential family bandits. In Advances in Neural Informution Processing Systems, 2013.
B. Kveton, Szepesvari, Z. Wen, and A. Ashkan. Cascading bandits: Learning rank in the cascade model. In International Conference on Machine Learning, pages 767-776. PMLR, 2015.
B. Kveton, C. Szepesvari, Z. Wen, M. Ghavamzadeh, and T. Lattimore. Garbage in, reward out: Bootstrapping exploration in multi-armed bandits. In ICML, 2019.
B. Kveton, M. Zaheer, C. Szepesvari, L. Li, M. Ghavamzadeh, and C. Boutilier. Randomized exploration in generalized linear bandits. In S. Chiappa and R. Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 2066-2076. PMLR, 26-28 Aug 2020. URL http::/pee http:///proceedinga mlr, www.sprees//eee wttppp/eessswv/eeeeepe w1t/////00///00aaaa.aa html
T. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6, 1985.
T. L. Lai. Adaptive treatment allocation and the multi-armed handit problem. The Annals of Statistics, pages 1091-1114, 1987.
L.. Lai. Boundary crossing problems for sample means. The Annals of Probability, pages 375-396. 1988.

---

T. Lattimore and C. Szepesvari. The end of optimism? an asymptotic analysis of finite-armed linear bandits. In Artificial Intelligence and Statisties, pages 728-737 2017.
Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Lu, G. Wang, Y. Hu, and L. Zhang. Optimal algorithms for Lipschitz bandits with heavy-tailed rewards. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages URL ptttp://pai http:///rooceedings mlr. wal.spress/v9.. /uu19
4163. PMLR, 09-15 Jun 2019.
html
S. Magureanu. Efficient Online Learning under Bandit Feedback. PhD thesis, KTH Royal Institute of Technology, 2018.
Magureanu, R. Combes, and A. Proutiere. Lipschitz bandits: Regret lower bounds and optimal algorithms. Machine Learning, 35:1-25, 2014.
O.-A. Maillard. Boundary crossing probabilities for general exponential families. Mathematical Methods of Statistics, 27(1):1-31, 2018.
H. Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematics Society, 58:527-535, 1952.
H. Saber, Ménard, and O.-A. Maillard. Forced-exploration free strategies for unimodal bandits. arXiv preprint arXiv:2006. 2606,,69,, 2020.
N. Srinivas, A. Krause, S. Kakade, and M. Seeger. Gaussian process optimization in the bandit setting: no regret and experimental design. In Proceedings of the 27th International Conference on International Conference on Machine Learning, pages 1015-1022. Omnipress, 2010.
W. R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25, 1933a.
W. R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-294, 1933b.
W. Thompson. On criterion for the rejection of observations and the distribution of the ratio of deviation to sample standard deviation. The Annals of Mathematical Statistics, 6(4):214 1935.
Wang, W. Ye, D. Geng, and Rudin. Towards practical lipschitz bandits. Proceedings of the 2020 ACM-IMS on Foundations of Data Science Conference, Oct 2020. doi: 10.1145/3412815.3416683 URL attt:://de doi. org/ /00 1111/14111111..101 11111222811334888888
Yu and S. Mannor. Unimodal bandits. In JCML, 2011.
12


Reviews:
[{"review_id": "rV7xmcNR7mH", "reviewer": "Reviewer_VZyd", "summary": "In this work the authors present an algorithm for the stochastic multi-armed bandits setting where it is known a priori that arms come in group of size at least q, all having the same mean. A lower bound on the regret is given, as well as an asymptotically order-optimal achievability scheme.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. The motivation provided for this problem is relatively weak. The primary example the authors use to motivate this setting involves arms with differing values across several categorical attributes (some of which are redundant), which has significantly more structure than just groups of arms with the same means. This is more reminiscent of Factored Bandits [Zimmert and Seldin, NeurIPS 2018], which the authors should discuss and compare against.\n2. Lack of clarity in simulations; in the paper there are several errors regarding simulations, e.g. for Figure 1 it claims 3 sets of means but lists a set of 4. Similarly in Figures 10,16,17,18,19 it is claimed that there are 4 classes, but 7 means are given. More importantly however, the authors poorly document their simulations, so it is unclear from the paper the true impact of the robustness of the algorithm to the parameter q. For example, it is only given for Fig 3 that there are 7 classes with given means, with an uneven number of Gaussian distributions in each class ranging from 4 to 23. It is not given which class has which size, let alone the total number of arms. For example, if the best class was the one with cardinality 4, this would seem to be a harder problem instance for the algorithm than if the class with cardinality 4 constituted the worst class. As such, the reproducibility and significance of Figure 3 are unclear. Critically, one of the two uses of q is constructing A_*(t), and so the relevant test regarding the robustness of the algorithm to q would seem to be when A_*(t) is impacted, yielding fewer than q optimal arms (which would appear to lead to linear regret, as suboptimal arms are included in A_*(t) ).\n3. The lower bound appears to be novel, but the algorithm itself seems to be only a minor modification of the original IMED.\n4. There does not appear to be any characterization or bounding of alpha or f in Theorem 2 in the main text. While the empirical performance of this algorithm seems promising, a discussion on alpha and f and the possibility for finite sample guarantees would strengthen this paper.\n\nMinor comments:\n- There were many typos and grammatical issues in this paper, which detract from the overall work. Some are listed below \n- Title should not have a period at the end\n- Line 40 that we assume ‘is’ unknown to the learner\n- Lines 55/56 arms should be plural\n- line 127 ‘makes appear’\n- line 135 duplicated text\n- Line 138 “2 time from” -> a factor of 2\n- Line 146 have->has\n- Line 210 summation should start from time index 1, and t is overloaded as both the time index and the dummy variable in the sum\n- line 266 annex->appendix\n- Line 272 duplicated compare\n- line 448 Monotony of the KL -> monotonicity\n\n**After Rebuttal:**\nThe authors clarified some helpful points in the rebuttal:\n\nExperiments: Including all relevant experimental details in the Appendix would help contextualize the simulations; a reader should not need to look at the raw code in order to understand the details of the experiments. \n\nRobustness: Thank you for clarifying $A_{*}(t)$. However, it is still unclear to me if Figure 3 shows robustness of this scheme with respect to q. From my understanding looking at the experiments, the authors simply vary the number of arms in a suboptimal class, where the interesting experiment to run would be seeing how the algorithm performs if there are fewer than q optimal arms (to which Figure 15 offers some partial insight). \n\n$\\alpha$ and $f$: Bounds and / or considerable discussion on these factors would greatly strengthen this work, as these quantities appear in the primary Theorem of this paper. If it is too difficult to provide these in general, specializing to Gaussian or Bernoulli instances would still be extremely helpful, to give a sense of how these quantities can be expected to scale. It was difficult for me to follow the appendix references as the analysis is not very self contained, and it is not clear why $f$ in particular goes to 0 in the limit.\n\nThis paper has its upsides, i.e. the problem is fundamental (equivalence classes of means) even if the motivating example is not well thought out, and the technical contributions (primarily the lower bound) are interesting and novel. However, the additional discussion does not change my score; the vague experiments and general lack of care taken with the writing are concerning. To address these issues, the authors will have to go through and correct the individual points we have listed, and all the others we did not. In its current form the presentation is poor so I cannot recommend acceptance. However, I will not object to acceptance either, so I retain my score of 5.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There are no negative societal impacts in this theoretical paper that focuses on regret minimization in the stochastic multi-armed bandit setting.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.5"}, "extra_text": {}}, {"review_id": "qCaZYEF2niR", "reviewer": "Reviewer_dE1k", "summary": "The paper extends the study of multi-armed bandits to the case where there are groups of arms having the same distribution (in the exponential family), and a lower bound $q$ on the size of these groups is known to the learner. The authors introduce a new parametric asymptotic lower bound for this setting. They build on the IMED strategy from Honda and Takemura to propose an adapted strategy. This new strategy has a regret that is at worst 2 times the asymptotic lower bound, and q-times smaller than the regret of an unstructured bandit instance having the same number of arms.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Originality / Significance\n The authors consider a setting where there are groups of arms having the same distribution and a lower bound $q$ on the size of these groups is known to the learner. They justify the interest of this setting by an example of problem where each arm can be described with a list of categorical attributes, and the reward function only depends on a subset of them. This is an original problem, that has not yet been studied, as I understand. The lower bound is original and even though the algorithm heavily resembles another algorithm( IMED from Honda and Takemura), the algorithm is efficient and the upper bound is technically involved. \n\nHowever, a first question arises regarding the interest and significance of this setting. I would like to understand from the authors what are the practical cases where the learner knows a lower bound on the size of the groups but does not know at least a subset of the features that are redundant and hence the groups? The authors attempt to explain it line 62, but do not succeed in making it clear, in my opinion.\n \n## Clarity/ Soundness\nThe paper lacks precision on multiple occasions, which harms its clarity but also makes the reader doubt its soundness :\n- In Theorem 1, should $\\lambda$ be replaced with $\\mu^*$? Otherwise, how is it defined? (same for l.174 and equation 6)\n- Why does $|c_q|\\geq 2q$ belong to the non-combinatorial regime? There is absolutely no explanation for this fact.\n- The paragraph starting in l186 and explaining the difficulties with the combinatorial regime is not clear. Can the authors reformulate the paragraph?\n- In Theorem 3, is the liminf a limsup? A liminf would not be satisfactory.\n\n## Minor flaws \n- In the proof of Theorem 1, the use of the Fano inequality should be explicit, even if it is classic.\n- Also, the authors should explain how they swap the liminf and the min , line 493.\n- The fact that the distributions are parametrized by their means because of assumption 2 should be explained earlier than on page 4.  Otherwise, the equivalence classes based on the means only seem strange.\n\n## Typos \n- l45 : we study/studies\n- l114 : The authors show\n- l170: combinatorial\n- l175: amounts\n- l178: assumption\n- l179: times\n- l221: makes\n- l246: assumptions\n- l252: a striking result \n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I am satisfied with the way the authors addressed the limitations of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "DpgL6WsSgMm", "reviewer": "Reviewer_KxtC", "summary": "This paper considers a new variant of the classic stochastic bandit problem, analysing the complexity of the problem and proposing an effective algorithm. The new problem matches the classic problem definition of the K-armed bandit, except all arms are grouped into classes with identical distributions. Each class contains at least q arms, and the decision-maker is assumed to know q a priori but not the classes. A motivating scenario where this may arise is one where arms have multiple categorical features but certain features are uniformly redundant in the sense that the reward distributions do not vary with respect to these features. The decision-maker would in such a setting know (a lower bound upon) the number of redundant features but not which features are redundant (and as such which arms are equivalent). \n\nThe authors derive an asymptotic lower bound on the number of plays of suboptimal arms, and then propose an algorithm based on the IMED indices of Honda and Takemura (2015). The regret of this algorithm is shown to coincide with the lower bound in certain settings -  where classes are equally sized (roughly speaking) – and differ from the lower bound by no more than a constant factor in other settings. The algorithm is shown to outperform non-bespoke approaches which treat are unaware of the arm class structure, and have some robustness to misspecification of q.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is generally of a high quality. The theoretical underpinnings are strong, the authors write mostly very well, and the solution to the problem is appropriate and builds nicely on existing work. I have two main issues with the presentation of the material – firstly that the more theoretical aspects could be explained more clearly in the main text (see section ‘Clarity’) and secondly that the motivation for considering the problem could be more detailed and have a potential issue resolved (see section ‘Significance’). I am impressed by the work and would be happy for the paper to be accepted as is, but could also give a yet higher score and feel the paper would be genuinely improved is these issues were addressed.\n\nORIGINALITY AND QUALITY: My view is that the paper clears the acceptance bar in this regard. The problem is interesting and the work on it is new, accurate as far as I can tell (I have not been able to thoroughly inspect the appendices in the time-limited reviewing window) – certainly the main results make sense and have required some effort to derive. The performance of the algorithm is impressive and the algorithm is simple to implement and computationally efficient. \n\nCLARITY: I really enjoyed the introductory section of the paper. The writing is excellent – the authors successfully adopt a blend of conciseness, clarity, and accuracy that explains core concepts quickly but accessibly. This is genuinely some of the best scene-setting I have seen in a bandit theory paper while reviewing at ML conferences. In Section 2, I feel there is something of a departure from this style as the mathematical material becomes more complex. I feel that this is not necessary. There is room within the page limit to guide the reader with more context and intuition here. The definitions and assumptions, and indeed Theorems/Lemmas to some extent, are presented without much linking text or context. The intuitions behind the lower bounds are complex but not (I feel) unaccessible to the unfamiliar reader, and as such I feel more could be done to explain the various steps here. As examples, I would explain to the reader the role of the ‘confusing instances’ (to find the exploration needed in the most challenging cases), give more intuition as to where the various terms in Theorem 1 arise from, percolate the discussion of non-combinatorial and combinatorial regimes with plain text explanations of the concepts (e.g. ‘an instance where all groups of similar of arms are of the same size’), and being more clear in the first instance what the remainder of the section aims to do to improve upon the insight given by Theorem 1. An explanation of how such improvements could be made via the rebuttal would lead me to increase my score.\n\nSIGNIFICANCE: The problem is interesting theoretically, and I could imagine the paper laying the foundation for the study of more complex variants (contextual, combinatorial, non-stationary etc.) which may have genuine applications. The mention of categorical features suggests a setting in which this problem would genuinely arise, however the motivation in this regard is scant. I accept that this predominantly a ‘theory paper’ but I do think the paper could be improved with a more convincing argument as to the motivating applications of the work. If they are genuine – why not explain/cite in more detail? Further, why is it preferable to approach this redundant categorical feature problem via the  approach in this paper over a more structured model selection-type approach where we can use the information that arms which correspond to matching levels of more categorical features are more likely to be part of the same class? I would like to see the motivation for the work addressed in more detail via the rebuttal.\n\nFinally, some minor typographical errors as follows: in line 114, should be ‘authors’ not ‘author’ in line 126, should be ‘paper’ not ‘papers’, in Thm 1, should be ‘suboptimal arms’ not ‘suboptimal arm’ there are further similar issues around pluralisation throughout the remainder - in line 179, should be ‘times’ not ‘time’ in line 180 the l in ‘Lemma 1’ should be capitalised, in line 281, should be ‘imperfect’ not ‘unperfect’. [NB, I have not considered these minor typos in assigning my review score]. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "They have adequately addressed limitations", "review_text": "", "extra_scores": {"ethical_concerns": "n/a", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5.5"}, "extra_text": {}}, {"review_id": "APo70HXQ1fX", "reviewer": "Reviewer_nrkQ", "summary": "The paper studies a version of the stochastic multi-armed bandit problem where arm-means have a multiplicity of at least $q$, meaning, for any given arm \"a,\" there exist at least $q-1$ other (distinct) arms with a mean reward same as that of \"a.\" The parameter $q$ is assumed known. The reward distributions are assumed to belong to a one-dimensional exponential family. Under this premise, the authors show refined lower bounds for the expected sampling times of inferior arms (also regret) that exhibit a $q^{-1}$-scaling. Additionally, leveraging the underlying problem structure, a refinement of the KL-divergence-based terms appearing in the lower bound is also shown. The authors propose a modification of the IMED algorithm that suffers a regret within a multiplicative \"control\" factor of the lower bound. All in all, the takeaway is that the achievable regret is reduced by a factor of $q$. The reported numerical experiments indicate robustness to misspecification of $q$. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "UPDATE: \nI thank the authors for their response; I have revised my rating to 6 since the authors could satisfactorily answer several of my questions. However, in light of the issues raised by the other reviewers, I am also minded to reduce my confidence score to 3.\n\n------------------------------------------------------------------------------------------- \n\n\nThe model and results certainly seem interesting. Since multiplicity of arm-means is a key feature, a brief survey of extant works that have considered such models will only make the literature review more comprehensive. Recent papers that come to mind are https://arxiv.org/pdf/2105.10721.pdf and https://arxiv.org/pdf/2103.12452.pdf (check references for related works). Cited papers assume $q=\\infty$, basically meaning that the arms are sampled from an infinite \"reservoir.\" However, the reservoir is assumed to hold a fixed (positive) fraction of \"optimal\" arms which are \"well-separated\" in the mean-reward from other sub-optimal types. Despite an infinity of arms in said problem, the papers show that logarithmic regret is still achievable. It would be interesting to see how the finite-armed model with a multiplicity of arm-means studied in this paper relates to its infinite-armed counterpart from cited works, achievability of logarithmic regret surprisingly being the unifying thread. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Unfortunately, the paper appears to have overloaded notation with plenty of typos and notational inconsistencies, which make it hard to parse. It could seriously benefit from a revision along these lines. Typos (not a comprehensive list) and some general remarks are noted below:\n\n1. Line 51: I suggest you use a different notation for $\\mathcal{B}_q(\\mu)$, it gets really confusing later on when you overload it further.\n\n2. Lines 134-137: Please rephrase.\n\n3. Line 151: The mapping $\\mu^\\prime$ is not defined before. Also, I believe there is scope for making the definition of \"confusing\" instance, less-confusing (no pun intended).\n\n4. Lines 158-163: Please decide upon a stable convention for KL divergences. As in, KL$(.,.)$ vs. KL$(.||.)$. Similarly for $\\mathcal{K}_{eq}$.\n\n5. Theorem 1 second line: A should be $\\mathcal{A}$, equivalence class in $\\nu$ (not $\\mu$). \n\n6. Line 165: What is a \"bandit dependent lower bound?\"\n\n7. In equation (2), the $\\nu_a$'s should be $\\mu_a$'s (there are other instances too, not noted here). The $\\mu$ below the \"inf\" should be $\\nu$. Also, how is $\\lambda$ specified?\n\n8. It would greatly help the reader if you could provide intuition on the combinatorial vs. non-combinatorial regimes in terms of the $q,2q$ business.\n\n9. Equation (5): $\\nu_a$ should be $\\mu_a$ and a possible summation missing?\n\n10. Equation (6): Extraneous log term and unspecified $\\lambda$.\n\n11. Line 210: Typo in the range of summation. Also, the $X_{t}'s$ haven't been defined before.\n\n12. Just below line 214: It should be $\\mathcal{A}_{\\ast}(t)$ below \"min.\"\n\n13. Please mention the acronym IMED-EC next to Algorithm 1.\n\n14. Line 221: *makes.\n\nSome of these issues recur subsequently too, I am not mentioning them again. Overall, I like the punchline of the paper -- a factor $q$ reduction in achievable regret if arm-means have $q$-multiplicities. But the paper needs a clean-up. I am open to increasing my score if aforementioned points are satisfactorily addressed.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The committee was divided about this paper: while the technical value is recognized by all and praised by one reviewer, it seems like at least two reviewers were puzzled by the clarity of the paper. I decided to read the draft myself to make my own opinion on whether the pass needed was minor (and does not require another cycle of review) or major. I think it is rather the former situation, though I see how a few typos at the wrong places may have mislead reader. Please update your work for the final version, removing typos and adding comments on motivation as well as citations to further highlight the connection with existing work and the potential impact of your discoveries. 
Decision: Accept (Poster)