Near Optimal Best Arm Identification for Clustered Bandits
Authors: Yash
Avishek Ghosh
Nikhil Karamchandani
Venue: ICML 2025 poster (2025)
Keywords: Best Arm Identification
Multi-Armed Bandits (MAB)
Clustered Bandits
Pure Exploration
Primary area: general_machine_learning->online_learning_active_learning_and_bandits
TL;DR: We address the best arm identification problem for Federated (Distributed) Bandits

Abstract: This work investigates the problem of best arm identification for multi-agent multi-armed bandits. We consider $N$ agents grouped into $M$ clusters, where each cluster solves a stochastic bandit problem. The mapping between agents and bandits is \textit{a priori} unknown. Each bandit is associated with $K$ arms, and the goal is to identify the best arm for each agent under a $\delta$-probably correct ($\delta$-PC) framework, while minimizing sample complexity and communication overhead. We propose two novel algorithms: \emph{Clustering then Best Arm Identification} (\texttt{Cl-BAI}) and \emph{Best Arm Identification then Clustering} (\texttt{BAI-Cl}). \texttt{Cl-BAI} employs a two-phase approach that first clusters agents based on the bandit problems they are learning, followed by identifying the best arm for each cluster. \texttt{BAI-Cl} reverses the sequence by identifying the best arms first and then clustering agents accordingly. Both algorithms exploit the successive elimination framework to ensure computational efficiency and high accuracy. Theoretical analysis establishes $\delta$-PC guarantees for both methods, derives bounds on their sample complexity, and provides a lower bound for the problem class. Moreover, when $M$ is small (a constant), we show that the sample complexity of (a variant of) \texttt{BAI-Cl} is (order-wise) minimax optimal. Experiments on synthetic and real-world (Movie Lens, Yelp) data demonstrates the superior performance of the proposed algorithms in terms of sample and communication efficiency, particularly in settings where $M \ll N$.

Near Optimal Best Arm Identification for Clustered Bandits
Yash Avishek Ghosh Nikhil Karamchandani
Abstract
1. Introduction
Multi armed bandits (MAB) (1) has become classical framework for modeling sequential learning as it carefully captures the shown great success applications like advertisement (Ad) placement, clinical trials, and recommendation system (see (I; 2)). In the past decade, there has been an enormous increase in the amount of processed data to the extent that it has become pivotal to distribute the learning process and leverage collaboration among multiple agents.
This work investigates the problem of best arm identification for multi-agent multi-armed bandits. We consider N agents grouped into M clusters, where each cluster solves a stochastic bandit problem. The mapping between agents and bandits is a priori unknown. Each bandit associated with K arms, and the goal is to identify the best arm for each agent under ô-probably correct (8-PC) framework, while minimizing sample complexity and communication overhead. We propose two novel algorithms: Clustering then Best Arm Identification (CI-BAT) and Best Arm Identification then Clustering (BAI-C1). Cl-BAI employs two-phase approach that clusters agents based on the bandit problems they are learning, followed by identifying the reverses the
dilemma. has
In licu of this, (3) introduced Federated Multi Armed Bandit (F-MAB), where we have N agents and a central learner; the agents can only talk one another through the central learner. This framework is particularly interesting when the (sequential) data is observed in distributed fashion and the action is also taken by the agents individually. This is a highly decentralized paradigm with lots of challenges (see (4; 5; 6)). In this paper, we propose and analyze learning algorithms that aim to address one the major challenges in F-MAB F-MAB--eteroone het--heeerogeeetty across agents.
best arm for each cluster. sequence by identifying the best arms first and then clustering agents accordingly. Both algorithms exploit the successive elimination framework to ensure computational efficiency and high accuracy. Theoretical analysis establishes 8-PC guarantees for both methods, derives bounds their sample complexity, and provides a lower bound for the problem class. Moreover, when M is small (a constant), we show that the sample complexity of (a variant of) BAI-C1 is (order-wise) wise) minimax optimal. Experiments on synthetic and real- woold (Movie Lens, Yelp) data demonstrates the superior performance of the proposed algorithms in terms of sample and communication efficiency, particularly in settings where M < N.
In F-MAB, the problem of heterogeneity naturally arises since the preferences of different agents may not be identical. In the movie recommendation example, different agents prefer different genres of movies like comedy, drama, action etc. Hence, the recommendation platform needs to identify agents based on their preferences and suggest movies accordingly. similar situation pops up in Ad placement, where the type of Ads shown to different people might be based on their taste. Moreover, in social recommendation platforms like Yelp, this heterogeneity effect needs to be addressed for better restaurant recommendation.
In this work, we model the heterogeneity of the agents through clustering. Note that clustering is canonical way to group similar agents for better collaboration. We consider multi-agent multi-an aintid-reeddd bandit problem with N agents, grouped into Af clusters (which are priori unknown). All the agents have access to a common collection of K arms, i.e., the set of arms is common for all N agents across the M clusters. Each cluster m E [M]] is trying to learn a stochastic bandit problem with best arm k Hence, all the agents belonging to cluster m share the (unique) best arm ky and
'Department of Electrical Engineering, IIT Bombay, India 'Department of Computer Science and Engineering, IIT Bombay, India. Correspondence to: Avishek Ghosh <avishck.ghoss @ int...cin.>..
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the au)hor(s).
For a positive r, we denote [r] (1,2......)

---

Near Optimal Best Arm Identification for Clustered Bandits
agents belonging to different clusters will have different best arms, i.e., if agents in and i2 belong in clusters my and m2 (with mi Fm2), we have km + Kma.
1.1. Our Contributions
Algorithm Design: We propose and analyze two novel algorithms; (i) Clustering then Best Arm Identification (C1-BAI) and (ii) Arm Identification then Clustering (BAI-C1). We use successive elimination for clustering and BAI primarily because of its simplicity and easy-tuning ability. We remark that other algorithms may also be used for these in our framework. Both the algorithms judiciously pull arms so that both clustering and BAI can be done in a sample efficient manner. Our algorithms are also efficient in terms of communication cost (to be defined shortly) between the agents and the central learner.
Federated Bandits (F-MAB) has received a lot of interest in the past few years. In (7; 8: 9), the authors consider distributed pure exploration with N agents learning the same bandit problem, with some communication allowed amongst them and study the tradeoff between the number of arm pulls needed per agent and the number of rounds of communica- tion. Moreover, in (3; 10; 11) the federated pure exploration setting is studied where multiple agents are learning different bandit problems (i.e., each agent has its own associated mean reward vector for the arms) and need to communicate with a central server to learn the arm with the highest sum of mean rewards across the agents. The setting of (12) is similar to above works (i.e., unstructured with no clustering), where the goal is to find not just the global best arm, but also the local best arms for each agent in a communication efficient manner. Furthermore, (3; 13) consider the federated bandits setup within a regret minimization framework.
Theoretical Guarantees: For a fixed confidence 8 E (0, 1), we obtain the sample complexity for CL- and BAI-CL for identifying the best arm for all N agents. Leveraging separability condition (for identifiability) across clusters, we analyze CL-BAI. On the other hand, for BAI-CL, using probabilistic argument, similar to the classical coupon collector problem, we first identify representatives from each cluster, and then judiciously construct subset of candidate best arms to reduce the number of arm-pulls. We characterize the benefits of BAI-CL over CL-BAI rigorously. We also study a variation of BAI CI, namely BAI- CLL++
In this paper, we address the problem of best arm identifi- cation (BAI) for all N agents in F-MAB in a heterogeneous (clustered) setup. We propose and analyze Successive Elimi- nation based learning algorithms for this task. Our algorithms are efficient in terms of sample complexity (the number of pulls) as well as communication cost between the agents and the central leaner (which is desirable in F-MAB, see (12)).
Lower Bound and Optimality: Considering large class of problem instances and using change-of-measure style arguments, we obtain minimax lower bound over the class of all learning algorithms. An interesting feature of our lower bound is that it is the maximum of two terms, each corresponding to a different sub-task which any feasible scheme should be able complete; one being identifying the set of best arms across the M bandits and the second being identifying for cach agent the index of the bandit problem that it is learning. Finally, we show that if the number of clusters, M, is small (constant), the algorithm BAI - CL+++ + is order-wise minimax optimal in terms of sample complexity.
Clustering in F-MAB also has a rich literature. In (14; 15; 16; 17; 18; 19) the authors study regret minimization in clustered linear bandits framework. Also (20) studies regret minimization where agents are divided into clusters and agents in the same cluster have the same mean rewards vector. The paper employs techniques from online matrix completion under an incoherence condition. Another line of works (see (21;22;33) assumes that each arm pull generates a vector feedback and arms in the same cluster have the same mean reward vector.
Experiments: We validate the theoretical findings through extensive experiments, both on synthetic and real-world datasets. We find that our proposed schemes are able to efficiently cluster and significantly reduce the overall sample complexity. For example, in a movie recommendation application with 100 users, clustered into 6 different age groups, each with different preferences derived from the MovieLens- IM dataset, BAI-CI++ is able to provide a 72% improvement in the sample complexity over a naive cluster-oblivious scheme. A 65% improvement is observed in similar experiment conducted with the Yelp dataset.
Perhaps the work closest to us is (24). Here, agents are grouped into roughly equal sized clusters and all agents in one cluster are solving the same bandit, with the goal being to min- imize an appropriately defined cumulative group regret. is assumed that agents form graph and can talk one another through a gossip style protocol. Although the cluster struc- ture here is similar ours, (24) studies group regret whereas we focus on the sample complexity for best arm identification Moreover, (24) allows gossip style communication protocol which is prohibited in our F-MAB setup. Finally, (25) uses a similar setting and identifies the best arm for a single bandit instance by several agents, each of which can only access a subset of the arms, thus necessitating communication.
2. Problem Setup
We have N agents, each of which is trying to learn one out of M stochastic bandit problems. Let.M: [N] - [M] denote the mapping from the set of agents to the set of bandits
2

---

Near Optimal Best Arm Identification for Clustered Bandits
which is not known apriori. Each of the M bandit problems is associated with a common collection of K arms. For each m E [M] k E [K], arm & in bandit m is associated with a reward distribution Im,,k= which we will assume to be 1-subGaassian" with a priori unknown mean Jmn.k E TR. Each pull of an arm results in a random reward, drawn independently from the corresponding reward distribution. Furthermore, we define the best arm km for bandit m as the arm with the largest mean amongst the arms of bandit m, i.e., km : argmax/m..k we assume that kn is unique for each m. Finally, for each bandit m, we will denote the gap be- tween the mean rewards of the best arm kn and another arm.j as Am.j = Am - Mmmy: and let Am, = = Am.j- We will make the following assumption throughout regarding the underlying reward distributions of the M bandits.
Note that any online algorithm involves communication from the (central) learner the different agents, well as vice-versa. In addition to the sample complexity, we also measure the communication complexity of the schemes we propose'. To do so, we will assume a cost of or units for communicating a real number and c units for each bit corresponding to a discrete quantity (i.e., to communicate x X' incurs a total cost of ct. [log]>X[] units). In general, one would expect o, be significantly larger than ey. For example, if in a system each real number is represented using 32 bits, then we will have c, =32cb-
3. Related Work
Best arm identification: In MAB literature, finding the best arm with probability at least 1 8 (for a 6 E (0, 1)), also known as the pure exploration problem is well studied; for ex- ample see (26; 27; 28; 29; 30; 31) and the references therein. Moreover (32; 33; 34; 35; 36;37) study various variants of pure exploration, such as identifying A out of top m arms; identifying arms with mean rewards above a threshold etc.
Assumption 2.1. 3 1y > such that for any two different bandits a,b, the best arm Kn for bandit performs at least 1) worse under bandit b than the corresponding best arm kig, i., Pb,
Mb 2 n7, Va, Ab..
The assumption above is natural for several settings and encodes a certain form of 'separability' amongst the different bandit problems; in particular, the above assumption implies that each of the M bandit instances have different best arm and hence K 2 M. As we will see later, this assumption enables us to efficiently match agents with the bandit problem they are solving.
Federated Bandits (F-MAB): More recently, distributed learning in MAB, also known as Federated Bandits has received a lot of attention alluded in Section 1. In (7; 8: 9), the authors study the distributed pure exploration problems with some allowed communication among them. On the other hand, (3; 10; 11; 38; 39; 40; 12) study the federated pure exploration problem with heterogencous reward structure across agents. Moreover, (3; 13; 41) address the F-MAB problem in a regret minimization framework.
Thus, an instance of the our problem is defined by I = [M]]] where II =I= (Imm.. [M].k E [K]). There is a learner whose goal is to identify the best arm KMig for each agent i. To accomplish this, the learner can use an online algorithm, say A, which at each time can either choose an agent and an arm to sample based on past observations; or decide to stop and output estimated collection of best arms given by (O1,02...,,O,, ON). Given an error threshold 8 E (0,1), we say that the algorithm A is d d-probably correct (6-PC) if, for any underlying problem instance I, the probability that algorithm output is incorrect is at most 6. More formally, denoting the total number of pulls (random) before stopping time of algorithm AA on instance I by T3. (A), is 5-PC if, for any instance I,
Clustered Federated bandits: In F-MAB, one of the major challenges is heterogeneity across agents and hence Clustered F-MAB is a popular area of research. In the (simple parametric) linear bandit setup, the clustering problem is studied by (14; 16; 17; 18; 42). Moreover (24; 25; 20; 21; 22) study clustered F-MAB without linear structure, and a detailed discussion as well comparison of these works with our work are presented in Section 1.
4. Algorithm I: C1-BAI
Throughout the algorithm, we will often calculate the average of the reward samples observed from the arm thus far. For generic arm k. we will refer to it by jug When considering the k-th arm of agent i, we will refer it by i Note that the true mean reward for this arm is given by PM((),
TP P(T
DiE [N] s.t. O * 58.
We will measure the performance of a 5-PC algorithm A by its sample complexity 7 (A). Our goal in this paper is to design 8-PC schemes for our problem whose sample complexity T7(( (AA) as small as possible. Note that TJ (A) is itself random quantity, and our results will be in terms of expectation or high probability bounds.
Our first algorithm, Clustering then Best Arm Identification (C1-BAT), is presented in Algorithm I and it consists of two phases. The goal of the first phase is to 'cluster' the agents based on the bandit problem that they are learning, so that for
"This is important in F-MAB since it may be directly related to internet bandwidth of the agents which is resource constraint.
?A random variable X is a-suhGaussian if, for any t > O. P( - [EX] >t) S 2exp(-tx -t²/20")
3

---

Near Optimal Best Arm Identification for Clustered Bandits
Algorithm 1 CI-BAI
Algorithm SE (A,7,
1: Input: 8, yy, Initialize: Best fent_Arm+ee ON
1: Input: A,y,R: Initialize: Ao A 0 0K
2: First phase:
2: while [A,] and r R do
3: for i [N] [N] do
3: rertlc,=22*
4: Agent runs Successive Elimination:
Pull each arm in A,-1 for 8log( 11 A|r times 4 5: Estimate jag for all h: E A from these samples
St,fi = -=]]]==E((]]] 12NK , (17m)))))
5:
Agent communicates S learner
6: Set A, A jeAr-1
max Py - 6r}
6:
if | - then
7: Best Armli] [N
7: end while
8: return Ar. f
8: end if
9: end for
10: Learner constructs graph 9 with [V] as set of vertices.
11: for e do
any two agents i.j learning different bandits, 3 k: E S, US} s.t. 10 2 n/2. Next, each agent i communicates the quantities S, fu' to the leamer (line 6), who uses this information to cluster the agents as described in lines 11-15. We will show that the above properties of the SE procedure ensure that with high probability, for each identified cluster, all its member agents are associated with the same bandit.
12: Create edge between vertices i.j Ip A 1//
SUU,
13: end for
14: Label connected components as O₁ C2,C2
15: Second phase:
16: for iE [m]] do
17: Learner selects one agent a, from C; and instructs 0;
describe the second phase of our scheme Cl C1-BAI. The learner selects one representative agent a; from every cluster i, and then instructs it to again call the successive ellminnation procedure SE, with input parameters -
Lines 16
to run Successive Elimination
end for
for fori do
20:
Agent a, runs Successive Elimination: S (/(2 ([2M), R-
and - This implies that for each representative agent, the SE procedure is run till there is only one arm left in the active set, which is then declared as the best arm estimate for the representative arm as well as all the other agents in the same cluster.
21:
22:
Agent a, communicates B; to learner
23: end for
24: for ie [ do
E do
Remark 4.1 (Successive Elimination). We use successive elimination for its simplicity and easy-to-tune capability. We comment that general other BAI (like track and stop (45)) and clustering ((20) algorithms may also be used in this framework.
26: Learner sets Best_Armly =B:
27: end for
28:
end for
29:
Return Best.Arm
Remark 4.2 (Knowledge of separation 17). We emphasize that the (exact) knowledge of separation r) may not be required. Any lower bound on ry is sufficient for theoretical results.
each bandit problem j [M], there is one cluster consisting of all the agents learning bandit j. In the second phase, the learner chooses one representative agent from each cluster, finds the best arm for that agent, and then declares that arm as the best arm for all the agents in the corresponding cluster.
The following results demonstrate the correctness and sample complexity of C1-BAI
Theorem 4.3. Suppose Assumption 2.1 holds. Given any 8 (0,1), the Cl C1-BAI scheme (see Algorithm 1) is 8-PC.
Lines 3-15 describe the first phase where agents sample arms so that at the end of the phase, the learner can accurately map each agent to the bandit problem it is learning. To do this efficiently, each agent uses the successive elimination procedure SE (43; 44) described in Algorithm
Theorem 4.4. With probability at least 1 5, 5, the sample complexity of Ci-BAI for an instance I, denoted by TF(CI-BAI) satisfies TV (CL-BAI) <T, +T2, where*
For agent i, we will use S; and ğ (pt fg.. . x to
TiS max (AMG) -"oog +lgg.V EE[M
denote the set of surviving active arms and the vector of updated empirical mean rewards
returned by the SE procedure, respectively. We will prove in Appendix 10.2 that the SE procedure in the first phase, when run with suitable choices for yy and R, guarantees the following with high probability: (i) For any two agents i.j learning the same bandit, k E S, U Sy. we have litg G S 2/2; (ii) For
+ +loglog (max AMMi)),A +og log()/)))
TAS Σ > AJ (logK (A,,)) 8og(1/))) JEIM
We use S denote a Cb, where is positive constant.

---

Near Optimal Best Arm Identification for Clustered Bandits
Note that Ti and T3 represent upper bounds on the total number of arm pulls in the first and second phases, respec- tively. In particular, recall that the second phase involves solving the standard best arm identification problem for M bandits at one representative agent each and with target error probability of 6/(2M); ); this problem has been studied extensively and the expression directly follows from the literature, see for example (44).
representative agent from each cluster and instructs it run Successive Elimination. This incurs a cost of O(c,.M) units.
Summing up and using M S N, ca S Cr. the total commu- nication cost required by C1-BAI is at most O(N.K.c,) units. In comparison, the communication cost of a naive scheme, where each agent independently identifies their best arm and then communicates the result to the learner, is at most O log .s)) units. Thus, C1- C1-BAI helps reduce the sample complexity by introducing interaction between the learner and the agents, which naturally induces a higher communication cost.
Remark 4.5 (Comparison with a naive algorithm). We can compare the sample complexity of C1 -BAT with a naive single-phase scheme where the learner instructs each agent to independently identify their best arm using successive elimination, and then communicate the result back to the agent. Note that this scheme completely ignores the under- lying mapping of agents to bandits. It follows immediately from (26) that for any agent learning bandit j. the sample complexity for the naive scheme is the order of ΣX A 3.8 Let us also assume balanced clusters, i.e., the cluster sizes are (N//M). Thus the overall average (normalized) sample complexity of the naive scheme across all agents is given by NK. मेे Σ) A == NK A -2, where A can be thought of as representing the average problem complexity across the M bandits.
5. Algorithm II: BAI-C1
Our second algorithm, Best Arm Identification then Clustering (BAI-C1) is presented in Algorithm 3 and it also consists of two phases. In the first phase, the goal is to identify the set of best arms, i.e., (Kr, m E [M] This is done by sampling agents randomly and finding their best arm, till we have identified M different best arms. In the second phase, we aim to 'cluster' the remaining agents which were not sampled in the first phase and find the best arm corresponding each of them. For each such agent, we do so by applying successive elimination only the set of best arms identified in the first phase.
On the other hand, from Theorem 4.4, the dominant terms in the (normalized) sample complexity of CI-BAI are given by NK 1 EjE(a] Σ max[[A,,,) - + MK A мK* Comparing, we can see that the first term may be smaller than that of the naive algorithm since it involves terms of the form max n. -2, which is at most ,7,3 that appears in the naive scheme, In fact, it can be much smaller depending on the value of the 'separability" parameter v) from Assump- tion 2.1 vis-a-vis the bandit gaps; in particular when 1) >> A. The second term in the above expression of the sample complexity of C1-BAI will be much smaller whenever M & N, i.e., the number of bandits M is much smaller than the number of agents N. We anticipate these conditions to be true in many scenarios of interest and thus expect our pro- posed scheme C1 -BAI I to outperform the naive strategy. Our numerical experiments in Section& 8 validate this intuition.
In the first phase (described in lines 3-17) the learner samples an agent uniformly at random from the set A, and then com- municates the current set of best arms S to agent i. The agent then proceeds to apply successive elimination (as prescribed in Algorithm 2) on the set of arms [K] so that the end of the SE procedure, we are confident that a) the returned set S; contains the best arm for agent i; and b) it does not contain the best arm corresponding to any of the other bandit instances.
The agent considers the intersection Sns, it is non-empty, then it implies that another agent with the same best arm as agent i had been sampled previously. In fact, the intersection will then have exactly one arm with high probability, corresponding to the best arm for agent i, and hence its index is communicated to the learner. On the other hand, if S = & it means that the bandit that current agent is learning hasn't 't been explored yet. Hence, agent i continues to run successive elimination on the set of arms S (line 12) till only one arm remains, which guaranteed to be the best arm for the agent with high probability and hence its index is communicated to the learner. The sets A and S, as well as the array Rest..rrm are updated appropriately.
Remark 4.6 (Communication Cost). Next, we consider the communication complexity of C1-BAI. Starting with communication from the agents the central learner, it happens once in the first phase (line 6) where every agent communicates the active set and the empirical reward vector to the learner, thus resulting in total cost of at most O(N.(c,, K + K)) units; and then once in the second phase (line 23) where the selected representative from each cluster communicates the identity of its best arm to the learner, requiring a total cost of (c,,.M K) units. Communication from the learner to agents happens only once in the second phase (line 18) when the learner selects
At the end of the first phase, the set S contains the indices of the M best arms corresponding to the different bandit instances. What remains is to identify for each remaining agent in A, its corresponding best arm from within the set S.
We say x= Ogy) if there exists positive constants C1 and C2 such that S
Lines 18 - 25 describe the second phase of our algorithm,
5

---

Near Optimal Best Arm Identification for Clustered Bandits
Algorithm 3 BAI-CI
(BAI-CI)) where,
1: Input: 17.6
K m,d
2: Initialize: A+ (e
Ti x [logK logy loglog A
3: First Phase:
m
4: while |S] < M do
3.M
K
5: Learner samples agent from A uniformly at random; communicates set S i
+ +M.log(
max me
(n,
6: Agent runs Successive Elimination:
T..N.
" (logM+loog
+logN Bogg++loge +loglogn
5.log( 3T log _- Roloooooo))+
7:
=SE=K= if SrS, then
Ti and T2 denote the no. of pulls in first phase and second phase respectively. Ti involves the pulls assigned for finding the best M arms which given by (ignoring log M
8:
9:
Agent i sends arm of E ENS, to learner
10: else
11:
Agent further rums Successive Elimination:
ΣE m.t along with that we will have at-most m=11= M. (0M(3//8) agents, learning a bandit already been explored earlier. T2 includes the pulls from applying SE on the set S for at-most N agents with 6/3N error probability. Remark 5.4 (Comparison between BAI-C1 and C1 C1-BAI). Remark 4.5 that the dominant terms in the sample complexity of C1-BAI are given by ΣjE[N] Σ Ex max A My))..) + M.K.K.. Ā- On the other hand, from Theorem 5.3, we have that the dominant terms in the sample complexity of BAI-Cl are given by M.K.Ä-²
factors),
SS,,, 6. x
12:
log( م ,
Agent sends arm at to the learner
14:
end if
15: Update at learner:
16:
A=A\(ii, Best Arm[i]= a;; S= SS
We saw previously
17: end while
18: Second Phase:
19: for A do
20:
Learner communicates the S with agent
21: "i "E.,"=SE(S,0/311))
K
the under- lying instance is such that is large enough; in particular say that in each bandit there is at least sizeable fraction of the arms whose mean reward is within r of the correspond- ing best arm. Then have, Σ max AM())::))) O(Kn 2), so that the respective complexities of C1-BAI and BAI-C1 become N. K. + M.K.A- and N.M. 2 MKn +.M.K respectively. Clearly, the main difference is between N.K. for C1 BBI and (N K) K).M.r for -AI- Thus, BAI-CI C1 will perform much better whenever M < N, i.e., the number of bandits is much smaller than the number of agents and arms, which is a natural scenario. Another point to note is that while we expect BAI-C Cl to perform better than C1 C1-BAI in most cases, the latter has the advantage that the agent pulls in the first phase happen in parallel which can sometimes be advantageous. Remark 5.5 (Communication Cost). Communication from the learner to the agents happen in the first phase (line 5) where leamer sequentially samples an agent and communi- cates the current set S c [K] (of size at most M) to the agent; and then in the second phase where the learner communicates the final set (of size ) to all the remaining agents resulting total cost of (c,,.N ZM (f)) O(c, N...N. N.M Nog.k) units. The communication from agents to the learner happens in the first phase (line 9 or 13) where each sampled agent incurs a cost of cs- [look) Since O (MMoggM agents are sampled in the first phase with high probability, the total cost incurred (c,, M. K). In the second phase (line 24), each remaining agent indicates one amongst the M arms in their best arm, requiring a total cost of
M.max
NN
22: Agent i communicates arm at to the learner
23:
Learner sets [esstAAm(i]]
24: end for
25:
Return Best Arm
where the learner communicates the set S to the remaining agents the set A. Each such agent applies successive elim- ination on the set S with target error probability y 8//NN, till the best arm is identified; and then communicates the arm index to the learner.
Remark 5.1 (Coupon Collector). The first phase ends when we see at least one agent from all M bandits. This related to the classical coupon collector problem, and those results to ensure that ((M log M) agents will be sampled in this phase woth high probability.
The following result demonstrates the correctness of our proposed scheme BAI-CI. The proof can be found in Appendix 10.
Theorem 5.2. Given any ò (0,1), the BAI-CI scheme (see Algorithm 3) is 8-PC.
Theorem 5.3. Suppose each agent belongs one of the M clusters uniformly at random. Then, with probability at least 5, the sample complexity TI. (BAI-CT) satisfies
6

---

Near Optimal Best Arm Identification for Clustered Bandits
Ol Using M < KN,K, the total communication cost is at most C1-BAI which incurs communication cost of O(N.K.c,)) units (see Remark 4,6), we note that BAI-C1 is more communication--ffiiiee (in addition to being better in terms of sample complexity) whenever MlogK SK
Algorithm 4 (.
units. Comparing this with
Input: 7. Initialize: k+
2: while True do
3: 6g = 10 a. SE(SS,,,,R-
4: Pull à for 32 log(4.k2 /w) times
"i
Remark 5.6 (Non-uniform Clusters). We assume that the each agent belongs to one of M clusters uniformly. This can be easily generalized as this is equivalent to solving coupon collector problem with unequal probabilities (see (46)).
if Aau MS < m then
6: return @ as the best arm
else
8:
k+
9: end if
10:
end while
6. Improved BAI-C1: BAI-C1++
Recall Assumption 2.1 that requires any admissible instance to satisfy 'separability' constraint. In this section, we present a variant of BAI-CI which requires an additional assumption other than Assumption 2.1, but can provide significant savings in terms of sample complexity.
We have the following lower bound on the expected sample complexity of any 6-PC scheme over the class of instances I.
Theorem 7.1. For any 8-PC algorithm A, there exists a problem instance v E such that the expected sample complexity E[Ty (A)] satisfies
Assumption 6.1. 3 1/2 2 0 such that for any two bandits i, J. the performance of the best arm k of bandit i, differs by at least under bandit j. i.e, |p:,; -HjA; mm. Vi.j [M] [M].ij..
log(1/0 1/0) A
E E
(I)
BAT-C1++ is identical to BAI-CI except that (i) in the first phase, after running SE procedure(line 12) agent will pull arm a;. 32log(12M/66 times and communicates 'i
Proof Sketch: Let I be an instance for which the mean reward vector corresponding to bandit i satisfies, Mt, Au H Note that the best arm for bandit is arm under instance v. With perturbed instance and change of measure (30, Lemma 1) argument we conclude the proof (details in Appendix 10.9).
to the learner the estimated mean reward associated with af: and (ii) in the second phase (line 21 of Algorithm 3), it uses SE (Algorithm 4) instead of the SE procedure. We will assume that at the end of the first phase, the learner stores the identified M best arms and their estimated mean rewards in S and Fy respectively. The SE procedure uses Assumption 6.1 to provide a more efficient scheme for identifying the best arm amongst the set S for each agent.
Remark 7.2 (Orderwise Optimaity of BAT-C1++). The above described class of Instance satisfies As- sumptions 2.1 and 6.1 with parameter A for both. For BAI-CI++, the order-wise sample complexity is M.K.A-2 + (M I)NA -2, We compare it with Equa- > tion 1. Suppose N K,M and moreover M is a constant (i.e., M = 0(1)). In that setup, the dominating term in the sample complexity of DAI-CI++ is N A -2 which matches the lower bound (Equation 1). Hence BAI-C1++ is wnder-wise optimal in this setting.
We defer the formal guarantees of BAI-CI++ to Ap- pendix 10.1. Similar to BAI-C1, BAI-C1++ is 8-PC. Regarding sample complexity, in the first phase, both BAI-CI++ and BAI-CI require similar pulls (in fact BAI-CI++ requires Mn more pulls than BAI-C1). However, in the second phase, instead of, N.M.A T.M.A-"(logM.. MIogg+++ log 8-1 + log N log log A - in BAI- C1 we have, N.M.A-²
Remark 7.3 (Instance Dependent Lower Bound). The lower bound proposed in Theorem 7.1 is a worst-case bound. Using similar ideas, we can also derive an instance -deendeed lower bound which is more general but requires additional notation. Details can be found in Appendix 10.10.
+ log log -1) + No (log + log N). Hence, we will gain in no. of pulls using BAI-CI+ over BAI-CI as long as N.M.A (N+M)m
7. Lower Bound
8. Numerical Results
In this section, consider the class of problem instances I which in addition to Assumption 2.1, also satisfy the following condition on the mean reward gaps for each bandit m E [M]: km, 2 Pm.k + A, Yk + k Also, we will restrict attention to unit variance Gaussian rewards for simplicity, although this can be readily generalized.
We conduct empirical evaluation of proposed algorithms using both synthetic and real-world datasets. We set the error probability ó = 10 for our experiments and present sample complexity results which are averaged over multiple independent runs of the corresponding algorithms.
7

---

Near Optimal Best Arm Identification for Clustered Bandits
(8)
(b)
(c)
(d)
(f)
Figure I. (c)()(c) Performance with varying number of agents N for synthetic datasets 1, 2, (d) Varying clustering parameter for dataset
3 (e) Skewed cluster sizes for dataset 3 (f) Performance with varying number of agents N for MovieLens dataset
8.1. Synthetic Datasets
with Remark 4.5 since both the clustering parameter and the individual bandit arm reward gaps are 17 in this case.
We take the reward distribution for each arm to be unit- variance Gaussian. We consider three problem instances.
Variation in clustering parameter (n)): For dataset 3, we varied 1 over the set (0.05.0.100.2.0)) while keeping other parameters constant follows: K 100, M 20, and N = 100. From Figure ((d), see that the sample complex- ity decays rapidly as the clustering parameter 1) increases and thus the underlying problem instance becomes easier.
First: We consider a small instance with M = 3 bandits/clusters and K = 10 arms, with mean arm rewards for the three bandits given by 1 [.09, 26, .49, .91, .56, .16, .31, .75, .76, .77;; 22 = [.02, 27, 36, 42, 47, .92, .3,, .62, .8, and The best arms for the bandits are arms 4, 6, and 7 respectively, and both Assumptions 2.1 and 6.1 hold with parameter 7 7= = 0.3.
A3 [6,,,46,60 44,,446, 7,,4,,,,,3,966,,77,,,
Variation in cluster sizes: While the previous experiments assume that all clusters are of the same size, here we study the impact non- uonffrmtrrttt of cluster sizes on the performance of the various algorithms. We consider dataset with N = 500 agents and M 100 clusters, where the cluster sizes follow power-law distribution. In particular, each agent is mapped to cluster i with probability proportional to 1a where a governs the skewness of the cluster sizes. As a increases, the cluster sizes become more skewed. Figure I(e) presents the average number of pulls for the various schemes as varied. While the sample complexity of the naive scheme and C1 is invariant to a, the performance of BAI-Cl and BAI-C1+ worsens as increases. This is because these algorithms are required to identify all the best arms in the first phase by randomly sampling agents; and this task becomes significantly harder when there are clusters with much fewer agents as compared to others.
Second: Next, we consider a larger instance with M = 20 bandits/clusters and K = 100 arms. There is a unique best arm for each of the M bandit problems. For each bandit, the mean reward for the assigned best arm is sampled from uniform distribution U(1 - n, 1). Next, the means of the M-1 11-1am arms that are best for other bandits are sampled from U00,1-200 2n). For the remaining K- - MM arms, their mean rewards are sampled uniformly between 0 and the mean reward of the best arm. It can be verified that Assumptions 2.1 and 6.1 are satisfied with parameter 1). We set 0.15.
We again set M = 20, K 100, with unique best arm for each bandit having mean reward 1, while all other arms have mean 1 1-1). Again, both Assumptions 2. and 6.1 hold with parameter 17. We set y= 0.15.
Third:
8.2. MovieLens Dataset
Finally, there are N' agents, divided into N/M sized clusters.
We perform experiments using the MooieLLnn-IIM dataset, which contains movie ratings from a large number of users. We group the users into six age categories: 18-24, 25-34, 35-44, 45-49, 50-55, and 56+. The 0-18 age group is excluded due to insufficient ratings for many movies. We restrict our study to movies that received at least 30 ratings in each of the six age groups, leaving 316 movies.
Variation with number of agents (N): For the three datasets constructed above, we vary N and plot the average number of pulls for the various schemes in Figures (c). We observe that BAI-C1 and BAI perform the best for all the datasets. For datasets 1 and 2, C1 -BAI also pro- vides a significant improvement over the naive single-phase scheme (with no clustering). This is in line with Remarks 4.5 and 5.4 which suggest that C1-BAI performs better than the naive scheme when the clustering parameter 1) is large as compared to the individual bandit arm reward gaps. For example, for dataset 1, is .3. while the minimum arm mean reward gaps for the three bandits are .14.022.01 respectively. On the other hand, for dataset both the naive scheme and Cl B have poor performance. Again, this is consistent
We have M = 6 bandits, one corresponding to each age group. Each of the K = 316 movies represents an arm. For each bandit and arm pair, the reward distribution is taken to be the empirical average score distribution calculated from the reviews for the corresponding movie given by users that age group, suitably normalized to make it 1-subGaussian.
We find that each of the 6 bandits (user age groups) has
8

---

Near Optimal Best Arm Identification for Clustered Bandits
distinct best arm (movie with highest average rating). For example, the highest rated movie for the 18-24 group is "The Usual Suspects (1995)", while it is "To Kill Mockingbird (1962)" for the 56+ age group. The dataset satisfies Assumptions 2.1 and 6.1 with clustering parameters 0000007 and 7/1 = 0.006 respectively.
how do this appropriately and hence this is deferred as a future work.
Also, in this work we use Successive elimination for easy tunability. There are other best arm identification algorithms,, such as Track And Stop (45), which are asymptotically optimal. An interesting future direction is to use such algorithms the clustered multi-agent bandits framework.
As before, we assume that there are N aggntts divided into M equal-sized clusters. The goal of the learner is to identify the best arm (movie with highest expected score) for each agent.
A Acknowledgements
Figure 1(f) plots the average sample complexity for the various schemes as we vary N. Our results demonstrate that clustering- based methods, especially BAI-CI++, significantly reduce the sample complexity compared to the naive scheme. BAI-C1 also achieves competitive performance but is less efficient than BAI-Ci+
AG would like to acknowledge Amazon grant (RD/0123- AMAZ009-005). NK's work was supported by SERB MATRICS grant and a CSR grant from SBI. Yash ac- knowledges funding support from the Centre for Machine Intelligence and Data Science (C-MInDS), IIT Bombay.
8.3. Yelp Dataset
Impact Statement
We conducted a similar experiment using the Yelp dataset as well. Those results along with some additional numerics can be found Appendix 10.11.
This paper presents work whose goal is to advance the field of Machine Learning, especially in the field for Federated and (distributed) multi-agent bandits. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
9. Conclusions and Future Work
In this paper, we propose and analyze algorithms for best arm identification in a multi-agen multi- aumti-armed bandit setting, with agents grouped into (a priori unknown) clusters. Out of these, the algorithm BAI-C1 (actually, its improved version BAI-CI++) obtains near optimal sample complexity, which is validated by lower bounds. One drawback of BAI-Cl is that it requires the knowledge of the cluster separation n. One immediate future work is to propose and analyze algorithms which do not require knowledge of n7
References
[1] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[2] Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
Towards this, we ran additional experiments with the Movie-lens and Yelp datasets, and observed that in practice, BAI-CI is indeed robust to 7). Theoretically we believe a successive estimation based algorithm may work, and here we sketch the rough idea. We can propose a multi-phase algorithm where we start with large enough value of 1/, and at the beginning of each phase, we reduce 17 by factor of 2. So, for the first few phases, the algorithm will not perform well, since y is still large enough. However, after some phases, the value of by falls below the actual gap and the algo- rithms start learning the best arm. If we select exponentially increasing phase lengths, we can show that these multi- -haase algorithm will succeed in finding the best arms of all the agents. Of course, the sample complexity of this algorithm will be worse compared to the current ones; however, we believe the orderwise sample complexity will remain the same (with worse constants) if the initial phase-length and the exponential increase factor are properly chosen.
[3] Chengshuai Shi and Cong Shen. Federated multi-armed bandits. In Proceedings the AAAI Conference on Arti- ficial Intelligence, volume 35, pages 9603-96 1, 2021.
[4] Chengshuai Shi, Cong Shen, and Jing Yang. Feder- ated multi-armed bandits with personalization. In International Conference on Artificial Intelligence and Statistics, pages 2917-2925. PMLR, 2021.
[5] Tan Li and Linqi Song.
sveccyppeeeervng communicaiion-effiieen federated multi-armed bandits. IEEE Journal on Selected Areas in Commu- nications, 40(3):773-787, 2022.
[6] Artun Saday, ilker Demirel, Yiggit Yıldırı, and Cem Tekin. Federated multi-armed bandits under byzantine attacks. IEEE Transactions on Artificial Intelligence, 2025.
[7] Eshcar Hillel, Zohar S Karnin, Tomer Koren, Ronny Lempel, and Oren Somekh. Distributed exploration in multi multi-armed bandits. Advances in Neural Information Processing Systems, 26, 2013.
However, we need to come-up up with stopping criteria for halving 7) which may be crucial. Currently, we do not know
9

---

Near Optimal Best Arm Identification for Clustered Bandits
[8] Chao Tao, Qin Zhang, and Yuan Zhou. Collaborative learning with limited interaction: Tight bounds for distributed exploration in multi-armed bandits. In 2019 IEEE 60th Annual Symposium on Foundations of Com- puter Science (FOCS), pages 126-146. IEEE, 2019.
[20] Soumyabrata Pal, Arun Sai Suggala, Karthikeyan Shanmugam, and Prateek Jain. Optimal algorithms for latent bandits with cluster structure. In International Conference on Artificial Intelligence and Statistics, pages 7540-7577. PMLR, 2023.
[9] Nikolai Karpov, Qin Zhang, and Yuan Zhou. Collab- orative top distribution identifications with limited interaction. In 2020 IEEE 6lst Annual Symposium on Foundations of Computer Science (FOCS), pages 160-171. IEEE, 2020.
[21] Junwen Yang, Zixin Zhong, and Vincent YF Tan. Optimal clustering with bandit feedback. Journal of Machine Learning Research, 15118)):155422 2024..
[22] Recep Can Yavas, Yuqi Huang, Vincent YF Tan, and Jonathan Scarlett. A general framework for clustering and distribution matching with bandit feedback. IEEE Transactions on Information Theory, 2025.
[10] Clémence Réda, Sattar Vakili, and Emilie Kaufmann. Near-optimal collaborative learning in bandits. Advances in Neural Information Processing Systems,
35:14183-14195, 2022.
[23] Victor Thuot, Alexandra Carpentier, Christophe Giraud, and Nicolas Verzelen. Active clustering with bandit feedback. arXiv preprint arXiv: / 2024.
[11] Zhirui Chen, PN Karthik, Vincent YF Tan, and Yeow Meng Chee. Federated best arm identification with heterogeneous clients. IEEE Transactions on Information Theory, 2023.
[24] Ronshee Chawla, Daniel Vial, Sanjay Shakkottai, and R Srikant. Collaborative multi-agent heterogeneous multi-armed bandits. In International Conference on Machine Learning, pages
[12] Srinivas Reddy Kota, PN Karthik, and Vincent YF Tan. Almost cost-free communication in federated best arm identification. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37. pages 8378-8385, 2023.
PMLR, 2023.
[25] Aritra Mitra, Hamed Hassani, and George Pappas. Exploiting heterogeneity in robust federated best-arm identification. arXiv preprint w:Xiv:2109.05700 2021.
[13] Zhaowei Zhu, Jingxuan Zhu, Ji Liu, and Yang Liu. Fed- erated bandit: A gossiping approach. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 5(1):1-29, 29112999222 2021.
[26] Kevin Jamieson and Robert Nowak. Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting. In 2014 48th Annual Conference on Information Sciences and Systems (CISS), pages 1-6. IEEE, 2014.
[14] Claudio Gentile, Shuai Li, and Giovanni Zappella. On- line clustering of bandits. In International conference on machine learning, pages 757-765. PMLR, 2014.
[27] Jean- Yves Audibert and Sébastien Bubeck. Best arm identification in multi-armed bandits. In COLT-23th Conference on learning theory-2010, pages 13-p, p. 2010.
[15] Shuai Li, Wei Chen, Shuai Li, and K Kwong-Safe Sak Leung. Improved algorithm on online clustering of bandits. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 2923-2929, 2019.
[28] Emilie Kaufmann, Olivier Cappé, and Aurélien Gariv- ier. On the complexity of a/b testing. In Conference Learning Theory, Pageesy.aagessseee 461-487 PMLR, 2014.
[16) Nathan Korda, Balazs Szorenyi, and Shuai Li. Dis- tributed clustering of linear bandits in peer to peer networks. In International conference on machine learning, pages 1301-1309 100.1113......R.... 2016.
[29] Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone. Pac subset selection in stochastic multi-armed bandits. In International Conference on Machine Learning, volume 12, pages 655-662, 2012.
[17] Hamza Cherkaoui, Merwan Barlier, and Igor Colin. Clustered multi-agent linear bandits. arXiv preprint arXiv:2309.088 10, 2023.
[30] Emilic Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best-arm identification in multi-armed bandit models. The Journal of Machine Learning Research, 17(1):1-42, 2016.
[18] Yikun Ban and Jingrui He. Local clustering in contextual multi-armed bandits. In Proceedings of the Web Conference 2021, pages 2335-2346, 2021.
[19] Xutong Liu, Haoru Zhao, Tong Yu, Shuai Li, and John CS Lui. Federated online clustering of bandits. In Uncertainty in Artificial Intelligence, pages 1221-1231.
[31] Zohar Karnin, Tomer Koren, and Oren Somekh. Almost optimal exploration multi-armed bandits. In International conference on machine learning, pages 1238 1246. PMLR, 2013.
PMLR, 2022.
10

---

Near Optimal Best Arm Identification for Clustered Bandits
[32] Rémy Degenne and Wouter M Koolen. Pure explo- ration with multiple correct answers. Advances in Neural Information Processing Systems, 32, 2019.
[44] Eyal Even-Dar, Shie Mannor, and Yishay Mansour. Pac bounds for multi-armed bandit and markov decision processes. In Computational Learning Theory: 15th Annual Conference on Computational Learning Theory, COLI 2002 Sydney, Australia, July 8-10, 2002 Proceedings 15, pages 255-270. Springer, 2002.
[33] Andrea Locatelli, Maurilio Gutzeit, and Alexandra Carpentier. An optimal algorithm for the thresholding bandit problem. In International Conference on Machine Learning, pages 1690-1698. PMIR, 2016.
[45] Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pages 998-1027. PMLR, 2016.
[34] Arghya Roy Chaudhuri and Shivaram Kalyanakrishnan. Pac identification of a bandit arm relative to a reward quantile. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
[46] Stella Dudzic. 93. the coupon collector's problem with unequal probabilities. The Mathematical Gazette, 23(526):126- 10:0::126-..,,,, 130, 2009.
[35] Arghya Roy Chaudhuri and Shivaram Kalyanakrishnan. Pac identification of many good arms in stochastic multi-armed bandits. In International Conference Machine Learning, pages 991-1000. PMLR, 2019.
[36] Nikolai Karpov and Qin Zhang. Batched coarse rank- ing in multi-armed bandits. In Conference Neural Information Processing Systems (NeurIPS), 2020..
[37] Sarvesh Gharat, Aniket Yadav, Nikhil Karamchan- dani, and Jayakrishnan Nair. Representative arm identification: A fixed confidence approach to identify cluster representatives. In ICASSP 2025-2025 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1-5. IEEE, 2025.
[38] Nikolai Karpov and Qin Zhang. Communication- efficient collaborative best arm identification. In Proceedings of the AAAI Conference Artificial Intelligence, volume 37, pages 8203-82116 2023.
[39] Nikolai Karpoy and Qin Zhang. Parallel best identification in heterogeneous environments. In Pro- ceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures, pages 53-64, 2024.
[40] Ziehen Wang, Chuanhao Li, Chenyu Song, Lianghui Wang, Quanquan Gu, and Huazheng Wang. Pure exploration in asynchronous federated bandits. Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, pages 3540-3570, 2024.
[41] Jingxuan Zhu and Ji Liu. Distributed multiarmed bandits. IEEE Transactions Automatic Control, 68(5):3025-300 2023.
[42] Avishek Ghosh, Abishek Sankararaman, and Kannan Ramchandran. Adaptive clustering and personalization in multi-agent stochastic linear bandits. arXiv preprint arXiv:2106.08902 2021.
[43] Yuan Zhou. Ie 498: Online learning and decision making, fall 2019 sep. 5th lecture 04: Pure explo- ration algorithms for mab problem, September 2019. Lecturer: Yuan Zhou Scribe: Juan Xu, Rahul Swamy.

---

Near Optimal Best Arm Identification for Clustered Bandits
10. Appendix
10.1. Guarantees for BAI-CI++
We have the following results.
Theorem 10.1. Given any òe (0.1), the BAI-CI++ scheme 6-PC.
Theorem 10.2. Suppose each agent belongs to one of the M clusters uniformly at random. With probability at least 1 5, the sample complexity To (BAI-CI++) of + for an instance satisfies
log( and log( (
(B((AA-C+++ where y= =
M K
7S
2 mit (log +logg++ooo+ooooo toggo
m= 1m
3.M
+M
max mE [M]
Plog logg
log(d 1
+ogllggmax(1,mmm.
}} +M
of
T2 N.M.1 (loM
+ +N. [[logó-++loge
Remark 10.3. Comparing the sample complexity BAI-CH+ to BAI-CI. In the first phase we have an additional M log(5 ()+log(M) pulls since want estimated mean of the best arm be within i of the true mean get correct result from SE procedure. the second phase instead of,
"i
N.M..j (log -looggg-++ooo
+log +logNolooooooo loglogn
we have,
2 (logo 'log.N)
Hence, we will gain no. of pulls using BAI-CI+ over BAI-CI as long as N. 22 M
Remark 10.4 (Communication Cost). Note that the modifications made to BAI-CI to get BAI-CI++ introduce additional communication in the first phase of the scheme. Each sampled agent, in addition to the identity of its identified best arm, also communicates an estimate of its mean reward to the learner. This incurs a total additional cost at most ((M.cr) units. Thus, the overall communication cost for BAI-CH+ is at most ONN.M.log..o. +...cMMMMMM. M.c,) units.
10.2. Proof of Successive Elimination
Assume there are arms (1,2,....z) .n) in A with corresponding means μn 2/2 ... pn. and are sub-Gaussian. Also, let = - 14; for iE (2,3,...,.) and A = A2. Consider the successive climination procedure SE applied to the set A. The following result well known (43; 44) and we include a proof here for completeness.
Theorem 10.5. With probability at least 1 y, RE oo) satisfies the following properties:
It returns the best arm in A, i.e., arm 1.
The total number of arm pulls needed is at most
plogA,
log
Proof. After r rounds of Successive Elimination, the total no. of pulls for any surviving arm the active set A, at least 8.1og(4nr2 /2)/2. Then using Hoeffding's inequality for sub-gaussian, we have the following bound on the difference
12

---

Near Optimal Best Arm Identification for Clustered Bandits
between the true mean μr of any i and its empirical estimate já, the end of any round r.
P 14 P4s 2 cr - 2nr
(2)
For each r define the event E, (1 A, and & A, A.vjeAs.t My < U1 )e,). Clearly event Eg holds true since the active set Ao is initialized to include all arms in the set A. Furthermore, note that the event == F, refers to the event that only the best arm, i.e. arm 1, remains in the active set and is thus returned by the SE procedure.
We have
PIE,In Pl Prl
Er ViE ViE - -
7
? 2r
21 n. 2nr² P(E)
where the last inequality follows from (2). Next,
P E
Er|nk== k=1
r=1
7
2r
30
7
21
2r
21
Thus we have that with probability at least 1 SE (E,,,,,ARRRRRR (, returns the best arm in A, i.e., arm 1. Next, we will now prove the upper bound on the number of pulls required by the SE procedure. Note that with probability at least 1 1-77 7, each arm i 2 2 is removed from the active set by at most round [1 [1+log, log, + 1. Also, the number pulls of arm at most the number of pulls any other arm. Thus, the total number of pulls for the SE procedure is at most
loga 2.
4n 8.log(
7
2-2r
nlog
log
0
(3)
10.3. Proof of Theorem 1
Proposition 10.6. Let fieer denote the estimated mean of 1thh arm of th agent th round. Consider the bad event eo. which occurs if in the first phase for any round of Successive Elimination for any agent and for any arm k. -( (Prrr)) 2/2 happens. Using union bound and theorem 10.5 we have
P(eo)SN.r
We will assume that cy does not occur with probability 1-Nr and proceed with our proof.
Proposition 10.7. Consider the bad event e7 to be when there exist two agents learning the same bandit and are clustered different clusters. Then
0.75
P(einG)
(4)
K0.75
K
Proof. Two agents, and j. learning the same bandit will not be assigned to the same cluster if D( ,,)) 2. i.c. there exists an arm in the union of the active sets of these two agents, whose estimated means for agents and differ by more than 7.
13

---

Near Optimal Best Arm Identification for Clustered Bandits
Proof sketch: We want prove that the probability that there exist agents i and j. and arm l: in St U Sy such that
[ - n is less than NK 2v 20. + k We first prove the following claims.
Claim I states that, given 6o, for any agent i, all the arms in S; will be "good" arms. We define the set of "good" arms for agent i, denoted as G3, as the set of arms whose true mean is within 2 of the mean the best arm for agent
From Claim 2, we conclude that e₁ 6 implies there must exist an agent i and an arm & G2 such that the estimate the 1tth arm for the jth agent is at least 1/22 2 eR/2 less than its true mean.
Claim 3 puts upper bound on the probability that a "good" arm gets eliminated after rounds of successive elimination.
Finally, we combine Claims 1, 2, and 3 to obtain the upper bound on the event C1.
Claim I. For all i [M] and & E S;, we have (M((), 2 (MM(), -2ER.
Proof. All arms with mean at least 2e less than the mean of the best will be eliminated after round R. i.e., all the arms in the set
E (=| SPMOAAM n2cn)
(5)
From Proposition 10.6, for E E, we have:
(.M(), - StR/2,
Ab Moyo AM10).MM ScR/2,
Hence, 1 100---a ME,
Claim 2. e1 neo > There exists a pair of agents i.j with ((x)-M(()))) -M(j) and an arm A E S.US, such that
1 SLM()
(3
CR
2221
or (2- (7_ CR
PA.SMMU
- 2
Proof. é1 implies that there exists pair of agents i,j such that M(i) = M(j) and some arm & E S; U.S for which the difference in estimated means that arm between the two agents i.j is more than n/2,i.e.
lit P n/2.
Since ls must belong either S; Sj. let's assume & Sy. Then, from Claim 1, we have k: E G, GG- Also, from Proposition 10.6, we have
|(M6)A - 12// Sen/2
and hence
IMMOAA -Mpl> "
6R
2 2
This implies:
= Mr PMOOAS -17 ER
2 2 )
(6)
or
> M PMOOE&
2
But Equation (7) isn't possible under the good event eo. because arm k must get eliminated from agent in some round T [1. If arm & is in both S, and Sy. then
li 1 S cn.
14

---

Near Optimal Best Arm Identification for Clustered Bandits
and hence, error cannot occur due to this arm. Arm k gets eliminated in round only if there exists some k' whose estimated mean is greater than fig 6 (see line of Algorithm 2). This implies:
2 Pi ter,
4 2 (MMO)
17
CR
MM +
+
2
2
2
17ER
ER
6r.
2 AMG)A
2
2
2
> +
(8)
Equation (8) violates Claim hence (7) isn't possible. Therefore, Equation (6) proves our claim.
Claim 3. For any arm & of agent i satisfying P.((),. > (M((). r rounds, assuming én holds, is less than
-2nn, the probability that this gets eliminated after
lox
2k.2
(==2=))"
Proof. Arm can removed from agent after r rounds only
pskrr < Pher -r
for some arm K.
From Proposition 10.6, we know that
pper N.M.MMMM fr
Therefore, we can deduce:
6 + Per SUMOAN
(9)
After r rounds, the total number of pulls for any arm is greater than 8 8.log can bound the probability of the event in equation (9) by:
4Kr² /e2. Using Hoeffding's inequality, we
low
2 (4 22e
Se
This concludes the proof for Claim
From Claim 3, we have the probability of an arm getting eliminated in round r. Also, after round r, the total number of pulls of any arm is at least 8 8-log
3Kr²
/e2. Hence, from Hoeffding's inequality, can derive the following:
- (3 ( < exp
-4log
4
<R
2
7
2
To bound the probability of é1 Neg, using Claim 2, can say that it is upper-bounded by the probability that there exists an arm & of agent and agent satisfying & S S;US, such that jij,- S (.M - = We assume that arm k gets eliminated after some round r E [1. since it doesn't 't get eliminated after round R, its estimated mean will be within 2
and thus i < P (3 cR) won't hold, e 2 -og =
The number pulls for an arm that gets eliminated after round will be at least log
/E2. Hence, the probability
that after rounds gets eliminated and has an estimated mean z fa less than its true is bounded by
4log
4x.2
(4
22g)
Alop 4x.2
(
min
47
15

---

Near Optimal Best Arm Identification for Clustered Bandits
Taking the union bound over all such arms and corresponding agent i, obtain the following equation:
R 4log
[Kr2 7
( =2 JKr
4log
(3
P(einεo) SN- K
min
?
+ 20n)
)
min
-Alog
skr2
-log
iKr2
N K
(4-
R
1-8
7
max
??
N K
4kr2
1=1
ER 2 2 (09(1//)) -n/17,
CR 8
2075 for r -R- R-5
1 for 2 R-4
2
Hence,
R-3
N.K
10775
Σ
4krz2)
4Kr2
T=
0.75
S <N.K(2V2. +
K0.75 K
Proposition 10.8. Consider the event e2 as the event where two agents learning different bandits get clustered into the same cluster, i... if ((pss)))) y. then
( (
(10)
Proof. Proof sketch: We want to bound the probability that any agents who are learning different bandits get clustered in the same cluster. Throughout this proof, we consider the possibilities only under the event C. and the probabilities are bounded as intersections with Eo-
We first claim (Claim 4) that if there exist two agents i.j who get clustered into the same cluster, then the estimated mean of arm (Mg) for the ith user must satisfy
cn
P Miy
2 2MMG)AA
Next, in Claim 5, we state that if k MG) from Claim 4 gets eliminated for user i after r rounds of successive elimination, then there must exist arm 1' E [KK] (KM))) such that
Pki00) +
We bound the probabilities of the events from Claims 4 and 5 using Hoeffding's 's inequality for sub-Gaussian random variables. Since the events from Claims 4 and are independent, we can take the product of their probabilities to obtain an upper bound on the probability of their intersection.
16

---

Near Optimal Best Arm Identification for Clustered Bandits
Define ez as the event that agents and with different best arms KM(() and Kyoy where (M(())EMM PMM()) MMo) are clustered into the same cluster. Claim 4. The event 62 implies that there exists agent í and arm Ki()) (ki kū .., kir) kM()) where MM 2 2MM()) such that
ER 2 2
Bki 2 2MMO))M
Proof. The event e2 implies that there exist two agents i,j such that e/2 holds. From the definition of e2 and our condition for clustering we have,
(Ietsaco
? -Phinco 1=2) (1R - -Mhino <>/)
(HMM))) ZPMOAATA))
(11)
From Assumption 2.1, we have
(PLAFSCC) ( ) 1271
Also, since Mj
Macy it follows that
(15,A300)) - -Mekkmnrs) )2n.
From the equation above, we have
10lme -Akiess < 11
Thus,
Alimos -HNMM0 2 (Pskiin -Mi Mi.k
17
2 or I -M3A3000
CR
12 CR
Using Proposition 10.6, exclude the second term in the equation above. Therefore,
c/2 - (Deines - -Midkuen 2 2(1jAme
) 11 6R 2
Hence, we conclude that
- 1ikie 2MM
2 2
Claim 5. Assume that arm k kMG) gets eliminated after round for user i. Then, there must exist an arm ke' E [K] [K]) ()M such that
7 ER 2 2
PM-)) 24
at the end of round r.
Proof. The arm kMnn) is eliminated after round only if there exists an arm k E [K]] kM))) such that
/ 2 u Meri
ter.
From Claim have
1) ER.
1lanas 2 (MM))AMM
2 2
Substituting this into the previous inequality:
p 2 2MMG)AAG
+G,
1 CR 2
2
17

---

Near Optimal Best Arm Identification for Clustered Bandits
Since (MM()))85)))
(MM
obtain:
Pe. 2 (.(0)A
7] ER +er
2
Thus,
71 ER PMM 26,
2
This completes the proof of Claim
From claim and 5, we conclude that e2 can only occur if:
There exists an agent and an arm (Mi)) Kii (i((s)
where (M(())M)))
2MMM(8)) such that,
! en
Bejnes ZMMG)AA
(12)
2
1fk) is eliminated after round from user i, then some arm k',
P MM-MMM)AAMO 26,
(13)
Given Co. for Eq. 12 hold, k)M)) must get eliminated after some round [1. as 3 sn > 2. After rounds
4K?
Elog
of successive elimination, any arm in the active set will have probability that after the th round,
pulls. Hence, from Hoeffding's 's inequality, the
P (PE 2PMG1AMO 2 2
=P
(ihiees) 2HM + (HMGGMMMO -MM(0) ) 2 2
6R
SP sP(Wiinns 2 2MM(())Ase)) (HMOAASO -MM(A)AAss)) )
6R
2
SP
<P
2MM(3AM3 +カ 77 ER
2
BK?
4lex
Se
(14)
Also, the probability that there exists an arm e [K]]VMG) such that
P 1M--MM())Aie)) 26r
17
(15)
2
less than
4log
3x2
(er 5B 2)
(K-1)-e
The events in equations 14 and are independent; hence, we can multiply their corresponding probubiiiiis obtain the upper bound on ee as follows:
R -e
Alogt 3K. Me.
212
Atogt
3K.2
1n/2
58
= P(eg (M
47
(rr
4 H4/2 2p 2
S(M-1).N.K.
3K
18

---

Near Optimal Best Arm Identification for Clustered Bandits
"R = 1/17 Hence,
12cr
TV
1
169
17
N
3K
(M--1)-N- K.
3K?
1=1 (2
<(M-I)-N-K
K
Proposition 10.9. From Proposition 2, and 3, the total probability of error until clustering is bounded by:
P(ectsstering) = -laaaVaaaaa--PPPaaaaaaalleeeeeee
SN.K K 2v2. 70.5
+
+
KU.75
K
8
<6NK~> K- 0.75
S
2
Proposition 10.10. From Theorem 10.5 and the union bound, the probubility of error in the second phase is bounded by:
P(e phasse S M.
(16)
2M
2
From proposition 10.9 and 10.10 we can get to the statement of theorem 4.3.
10.4. Proof of Theorem 2
Assuming our algorithm doesn't enter the error event eg, using equation of Theorem 10.5, for the first phase, we can bound the sample complexity for any arm [K] of any agent by:
loga maxteh,..)
8 8-log
Anr 7
2 2r
$ max ..,))
logn + tog - + (oglo((max((..))) -1)))))))))))))))))))
S <max(A..)) (logK+logh Nog loglog (..
Hence, we can bound the total sample complexity in the first phase as:
(1)
)))
T Σ max max AMx).))).)) 22 [logK +lollo (Ma)l)o))mm((MMM))))))))( +lg. +log :=
8)
Similarly, can bound the total number of pulls in the second phase as:
T2
M
(logK+
+logM +log++log/ +log
10.5. proof of Theorem 5.2
Proposition 10.11. With probability at least 1 228//, the end first phase we will correctly detect
The best arm for all the agents not in set
19

---

Assuming each agent is assigned to one of the bandit randomly with equal probability, then the number of agents Near Optimal Best Arm Identification for Clustered Bandits
The best arm for all the M bandits
Proof.
Claim 6.
picked in first phase is less than or equal to log( 2.a with probability at least 1 1-5/3.
Proof.
The probability by which an agent gets picked from a given bandit will be 1/M. Hence, the probability that after 3,
log
log( A logl - we arrive at eqn. 17.
picking
agents, no agent gets picked learning bandit m. is (1 lost
Putting union bound for all M bandits
log( 3.M 8
logt
P([[N]]
>
M.(1
loxt
(17)
Log(
M
M
log(
3.M
P([[]]| >
8
//833
(18)
log(
M
M
If successive elimination doesn't 't enter event, then it is clear that the statements of this proposition will be true. Hence, we bound the probability of successive elimination entering an error event for any agent in the first phase.
From the union bound, P(e) S (Number of agents picked in the first round) (Probability of error for each agent). Hence,
P(e)
Σ
PSE giving error for one agent)
VE(NIVA
5. 5l
M M 3.1l 0
3log(
8. 8llog
M
log(
<
<|[N]\A]
.1
3log(
3.M (2.0))
log
M
M-11
log
3.M
Ms 5 8.log
M-1
log
M-1
M
3.3 3log
0
3
28
3
3
From above equations and theorem 10.5 we can come directly to the first statements of the theorem,
Proposition 10.12. In the second phase, with probability 1 - 3. we will correctly detect the best arm for all the agents remaining in the set A.
Proof. Using the union bound, the probability of error < JN < Hence, from theorem 10.5, we will detect the best arm with probability at least
From propositions 10.11 and 10.12, the total probability of error for the 3.AT-C7 algorithm less than
20

---

Near Optimal Best Arm Identification for Clustered Bandits
10.6. Proof of theorem 5.3
Proposition 10.13. From equation 3, we can say that with probability least 1 25 algorithm in the first phase will be less than:
the total number of pulls for the
3
n
R
Σ
Σ
A m.s"
(logK + +logy loglog4 m.))
3M
72 Σ
max (n. (log (m +log max (7) Am.i) Am)))-))
+ M log
mmx m=11
log
M
Y= 8-
(19)
log(
Proposition 10.14. Similarly with probability least 1 6/3 total Number of pulls for the algorithm the second phase will be less than:
-N - logó 1 +og.N logllgn ))
(20)
10.7. Proof of theorem 10.1
Proposition 10.15. Given an instance == ([ satisfying assumptions and with parameters v and
nh and given that [0, -MMG) - EEjE from the first phase, the procedure SE identifies the best arm with at least
1 1-7 probabilii...
Proof. Denote as our potential candidate for the best arm and a" the true best arm for the current agent. jāa the estimated mean arm à =a" which we calculated in the first phase. Therefore, after the 6tt round, error can occur if:
Pa 2 711 or à=a" and līa Fal S
71
a
and
jía
Hence:
P(e)
P
(Alãa mal In In(ā=aa))u (fisa
m (n((aaa)) ((())) (ilida-ial mal
2
1=
à===", a", then ja 1la-4a Hal s 4. otherwise jīa Maa 2 3m hence:
20
P(e) Σ (1lAa-Mal) Mal In( ((1))))(()))))0 (1laa-Hal2 In
Using Hoeffding's inequality for --sub-Gausiian random variables, have:
27 P(e) < 4
k: 25
1=1
Proposition 10.16. With probability least 1 -2//3, the end of first phase we will correctly detect
The best arm for all the agents not in set A
The best arm for all the M bandits
Proof. Proof will be same as in 10.1 as we don't ccange anything in BAI-CI+ in first phase except calculating additional estimates the means of the best arms.
21

---

Near Optimal Best Arm Identification for Clustered Bandits
Proposition 10.17. After the first phase, followinng will hold true.
Proof. We will pull each arm is the set S at-least (22lo((12M/ times. Hence using union bound over all the arms in the set M[ and Hoeffding's incquality for I-SubGaussian random variable we have.
Proposition 10.18. In second phase, with probabiliiy 1 1-6/6 will correctly detect the best arm for all the agents remaining in the set A
Proof. Using union bound probability of enror is S.N. probability at-least 1 -8/6.
6 6N
I 0. Hence from theorem 10.5 we will detect the best arm with
From proposition 10.15 ,0.16,, 10.17,10.18 total probability of error for the BAI -M--Cl+- algorithm is less than 8.
10.8. Proof of Theorem 10.2
Proposition 10.19. In phuse k. the probability that the is at least 1 1-
subroutine returns the true best arm
Proof. Since the minimum arm gap is at least 7), under the good which occurs with probability at least - 5y the algorithm returns the best arm while taking at most log(111)) /nn)+ +1 rounds.
Proposition 10.20. Given an instance y/= Th, and given that
MIIII satisfying Assumptions 6. and 2.1 with parameters nj and
Vh 4
|0g (wjーМMy AMM)
VjES,
from the first phase, the procedure SE will take at most
O(M (log 1) 1/ Plog7)
pulls.
Proof. Using eqn. we bound the number of pulls in phase & by:
log
[Sllog 2
log (4k² log(4k2 (4k2/7)
S
+0
172
7/
Denote Eg the event that the algorithm has not terminated in stage k. If the algorithm has not terminated in stage k then is not the case that á a" and j.. 733 /
By union bound, the probability that these two events do not occur is at most
2y
2
1 54
5
412
Finally, we obtain:
12
41.2
E T S 2 (P(E511)
log
+
[T]
(21)
172
k=
32
4122
log
Mlogn 2 k
Eg,,Ag [T] -
log
+M
(22)
17
172
k=1
AE [T] -1 MloggM +logogg
1) 1 Plog7
(23)
22

---

Near Optimal Best Arm Identification for Clustered Bandits
Proposition 10.21. No. of pulls in the first phase the BAI-CI ++ Algorithm will be less than
M K T Σ E
A m.
(logK +logy toglog + M.ooo( (
3.M,
max mM(M
Σ max(1) (n.x())Am..)) 3 -llog((oooo +logy
m=li=1
(log(6-1) (0g(6))))(og(MM))
M log( M- log( 3.
+ +oglogmax((nAmm)) ")) M
where
n
Proof. In the first phase of ++ we only require an additional M Hence from eqn. 19 we can conclude the proposition.
> M)
pulls compared to BAI-C1,
"1
Proposition 10.22. The number of pulls in the second phase of the BAI BAI-CI++ + algorithm will be at most
N m/ 2 Th N. M -77 - (lollggn +N
+logN).
(24)
Proof. From Proposition 10.20 and setting 7 7-666N, we directly obtain the given claim.
Adding the number of pulls from Propositions 10.21 and 10.22 completes our proof.
10.9. Proof of Theorem 7.1
We start with the first bound. Consider an alternate instance // EZ which is identical to v. except that for some m E [M] and >> M, the mean reward for arm & in bandit m is changed to 2- Note that the set of best arms under v and v' are distinct; in particular, they are [M]] and ([MJ', {m²) [ respectively. Hence, any feasible algorithm should be able to reliably infer the underlying instance v or v/. Then from (30, Lemma 1) based on a 'change of measure' technique, we have the following lower bound on the expected number of total pulls of arm by agents learning bandit m under instance
E[T (A)) log(1/2.40) 1og(1/2.48)
D(,.p++nn)
4n²
where ()) denotes the Kullback-Leible divergence between two Gaussian distributions with means a and b respectively, and is equal to (a (a).) Summing over all possible alternate best arms k and bandits m., we get the first lower bound
E (A)) (KK-M-KK--M -K- 1og(1/45)
(25)
4n²
We now demonstrate the second lower bound in the expression of the theorem. Again, consider the instance v E I as defined before. Here, for each agent i, we lower bound the total number of samples required from that agent to reliably infer which of the M bandits it is learning. Assume that agent i is learning bandit m (with best arm m.) under the instance v; and consider an alternate instance // where is mapped a different bandit m' (which by definition has different best arm m (). Note that under either mapping, the mean rewards of all the arms remains the same except arms and m for which the mean reward is switched from + to and vire-versa. Clearly, any feasible algorithm should be able to reliably distinguish between the original and alternate problem instances.
Again, using (30, Lemma 1), we have the following lower bound on the expected number of pulls of arms m and m' by agent under instance v;
log(1/2.46) log (/2.46))
E
(A)+TH (A))
D(u.u++))
which also serves as lower bound on the expected number of pulls by agent i. Since each agent is independently mapped to bandit, the total number of pulls across all agents has to satisfy the following lower bound:
log(1 (og(1/2.45)
BTT
(26)
n7
Combining (25) and (26) completes the proof.
23

---

Near Optimal Best Arm Identification for Clustered Bandits
10.10. Instance Dependent Lower Bound
We can write the following bound the total expected no. of pulls for any 0-PAC algorithm for any instance satisfying assumption 1.
log(1/2.45) mEMKESmm D(MMO),AHMMM.A)
log log(1/2.46)
2 max
min max RE be(K)eejjM())+MM)) D(HMMO,A..MMM)))
E
Similar to the proof in theorem 7.1, we will show two lower bounds one for each sub-task, first we show lower bound on identifying for each agent the index bandit problem that is learning. Consider an instance / the set of feasible instances(satisfying assumption 1). Now, assume agent is learning bandit m in the instance consider an alternate instance where it gets mapped to bandit m' m, any correct algorithm should be able to distinguish that for all m' m. using (? Lemma [Jauffmann20) 1ccopllexity we can write eq. 27
in
E[T DMMM. (E(K]
Σ
(jE(IM()+MOi)
(27)
We further modify eq.27 bound total of pulls for agent i in the following eqn.
log(1/2.46)
T
2 min ke(K(JJEGjMü)) ((MM))))
max
hence, total no. of pulls for a problem instance can be bounded as follows.
ETT Σ ETTT
(28)
XE[N]
Next, we show a lower bound on the no. of pulls for identifying the best arm of each bandit. Consider the instance y= ([N], with clustering parameter equal to 17. now for a bandit m consider the set arms Sm,, which are at-least 17 worse than the best arm all the other bandits i.e
Sm. = [k| S Hmisk -1, E mM]
We can bound the no. of pulls for a bandit m by change of measure technique, as we for all m in [M] for all arm k in Sm., we can consider an alternate instance where we alter the mean h arm to pm.k,, +e where can be arbitrarily small. The instance will be an alternate instance as has different arm for bandit m and it will satisfy the assumption 6. Hence, the expected no. of pulls for an arm & of bandit m is bounded by,
E ((H.)( (og(1/2.46)))mm vm [M]Kke S.n..
Further, total no. of pulls can be bounded by,
log(1/2.46)
E ETT
Σ
(29)
MEMKES D(PMi)..MMMi).
10.11. Additional numerical results
1..1 YELP DATASET
We perform experiments using the Yelp dataset, which contains ratings for various businesses given by users across different states of the US. We consider M states with the highest number of ratings as our bandits, namely Louisiana, Tennessee, Mis- souri, and Indiana. We identify 211 businesses which are present in all the selected states, and these constitute the bandit
"htnss/wwww.yeep.co/ddaaac
24

---

Near Optimal Best Arm Identification for Clustered Bandits
algoritim without chotering(nnive))
DBM
CHBAI
307
BAI Cle-4
227
227
124
122
187
70
No. ageres
agents
(a)
(b)
BAI
107
BAI-G++
Communiccsonn COSt 100g scale!
106
100
10
10
No. of agents
(c)
Figure (a) Performance with varying number agents for Yelp dataset (b)(c) Communication cost with varying number of agents for datasets 2,
arms. For each bandit and arm pair (state-business pair), we assign its expected reward to be the average review score the corre- sponding business got from users that state. We assume all reward distributions to be 1-Gaussian with the appropriate means.
We find that each of the bandits (states) has distinet best arm (business with highest average rating). For example, the highest rated business in Louisiana is 'Painting with Twist', while is 'Nothing Bundt Cakes' Indiana. In fact, the dataset satisfies Assumptions 2.1 and 6.1 with clustering parameters 7) = 0.375 and 7) 0.166 respectively.
As before, we assume that there are N agents divided into M clusters, each of size N/M, and mapped to one of the M bandits. The goal of the learner is to identify the best arm (highest rated business) for each agent.
Figure 2(a) plots the average sample complexity for the various schemes as we vary N. Our results demonstrate that clustering-basee methods, especially BAI-CI++ significantly reduce the sample complexity compared to the naive scheme. BAI-Cl also achieves competitive performance but is less efficient than BAI-C1++. Also, we see that both the naive scheme and CI-BAI have poor performance. Again, this is consistent with Remark 4.5 since the clustering parameter y and the individual bandit arm reward gaps close this case.
10. 1..2. COMMUNICATION COST
We will assume cost of C₁ 1 unit for communicating each bit, and c, 32c; 32 units for communicating real number.
Figure 2(b)(c) plots the the overall communication cost the various algorithms for datasets 2 and (synthetically generated, as described in Section 8), while varying the number of agents N. We can see that the communication cost of c1 C1-BAI
25

---

Near Optimal Best Arm Identification for Clustered Bandits
is lower than that of BAI-CI, which is itself little smaller than for BAI-CI+ Note that this order is opposite of that observed for sample complexity, thus indicating trade-off between the two quantities. This behaviour is also consistent with our observations in Remarks 4.6 and 5.5,
26


Reviews:
[{"review_id": "pJTtZHXUTR", "reviewer": "Reviewer_Dq4J", "summary": "The paper considers the problem of federated fixed-confidence best arm identification, where the agents are assumed to be clustered and the agents of the same cluster share the same bandit instance. The authors propose two algorithms, Cl-BAI (cluster-then-BAI) and BAI-Cl (BAI-then-cluster) and show their sample complexities with high probability. Under an additional assumption, the authors propose BAI-Cl++ with improved sample complexity. Then, the authors provide an in-expectation lower bound for the class of instances with mean reward gap assumption, which implies that BAI-Cl++ is orderwise optimal. The algorithms are tested numerically on various datasets, showing their efficacy.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "**Nearest neighbor and pairwise distance:** The claim being discussed here considers the `bad' event that two agents belonging to the same cluster get assigned to different clusters, i.e., there exists an arm in the union of the active sets of these two agents, whose estimated means for agents $i$ and $j$ differ by more than $\\eta/2$. Our claim is a high probability result and it implies that while the bad event (including for example the specific case that the reviewer has mentioned) can happen, it will occur with very small probability because the underlying ground truth dictates that for any $i,j,k$ which are in the same cluster, their true mean reward vectors will all be identical and thus, when the SE procedure (as prescribed by our algorithm) is run by each of them in the first (clustering) phase, it is very unlikely that the mean reward estimates will be significantly far apart. The claim essentially provides an upper bound on the probability that the bad event occurs. \n \n**Number of independent runs** 50 \n\n**Writing, Typos, Figures** We apologize. We have actively worked on the writing in the revised draft and also improved the figures.\n\n**Knowledge of $M$:** The number of clusters $M$ is not needed to be known for  Cl-BAI, where the clusters are created based on a nearest-neighbor graph type construction. For BAI-Cl and BAI-Cl++, knowledge of $M$ (or an upper bound) is needed since the first phase corresponds to recovering the set of all possible best arms. \n\n**Communication cost:** We believe there is a tradeoff between the sample complexity and the communication cost; we see some evidence of this in our analysis. Any algorithm will incur at least $N\\cdot \\log M \\cdot c_b$ communication cost since the learner has to infer each agent's cluster membership. However, we believe this to be weak and identifying the optimal tradeoff is of interest. We have included a more thorough discussion on this.\n\n**Random selection in Algo 1:** The agent is selected arbitrarily from each cluster. We have clarified this in the revised manuscript.\n\n**SE is easy-to-tune:** We say this because SE provides a general procedure which can be altered using three `knobs': the subset of arms, the target error probability, and the number of rounds. We use different combinations of these parameters in different schemes (as well as stages of the same scheme) to achieve various guarantees on surviving arms, their confidence interval sizes etc.\n\n**Robustness with respect to $\\eta$:** The reviewer is correct in stating that if $\\eta' \\leq \\eta$, our sample complexity results hold with $\\eta$ replaced by $\\eta'$. We have run additional experiments to validate the robustness of our schemes with respect to $\\eta$. Please see the response for Reviewer  UFPL.\n\n**Parameter-free algorithm** We can remove the knowledge of $\\eta$ from our learning algorithms completely. We can propose a multi-phase algorithm where we start with a large enough value of $\\eta$, and at the beginning of each phase, we halve $\\eta$. After some phases, the value of $\\eta$ falls below the actual gap and the algorithms start learning the best arm. If we select exponentially increasing phase length, we can show this multi-phase algorithm will succeed in finding the best arms of all the agents. Rigorously proving the correctness is part of our future plans.\n\n**Yun $\\&$ Proutiere, 16** Yun and Proutiere consider cluster recovery in the Stochastic Block Model, where the feedback structure (edge label) is quite different to our setting. However, we do agree that some similar spectral decomposition based method might be feasible for our setting as well. \n\n**Performance gap between Cl-BAI and BAI-Cl** Cl-BAI clusters the users in the first phase and then employs one agent from each cluster to identify the corresponding best arms. However all $K$ arms remain active throughout, including the first phase where all the agents participate. On the other hand, in Cl-BAI, the first phase reduces the active set of arms from $K$ to only $M$ using participation from only $O(M\\log M)$ agents and this provides a great reduction in the sample complexity.\n\n**Expected sample complexity** Similar to several works of best arm identification (BAI) in multi-armed bandits, our upper bounds (achievability) are stated as high-probability results whereas the lower bounds are in expectation. However, there are works available in the literature which prove expected sample complexity upper bounds for BAI. For example, Kalyanakrishnan et. al. (2012) for the LUCB scheme and Even-Dar et. al. (2006) for SE style schemes. We believe that similar ideas can potentially be used to derive expected sample complexity bounds for our schemes as well. \n\n**References**\n1) S. Kalyanakrishnan et. al., PAC subset selection in stochastic multi-armed bandits, ICML 2012.\n2) E. Even-Dar et. al., Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems, JMLR 2006.", "claims_and_evidence": "See my comments on Theoretical Results and Experiments", "methods_and_evaluation_criteria": "See Experimental Designs or Analyses", "theoretical_claims": "I didn't check the whole proof in detail, but I have checked and concurred the correctness of the lower bound proof.\n\n\nI want the authors to clarify the following issue during the proof of Cl-BAI:\n\nIn line 658, it states that $i$ and $j$ will not be assigned to the same cluster if $|\\hat{\\mu}^i - \\hat{\\mu}^j| > \\eta / 2$. However, as Cl-BAI is constructing a nearest neighbor graph, I don't think this is necessarily the case. It may be that there is a $k$ such that $|\\hat{\\mu}^i - \\hat{\\mu}^k| \\leq \\eta / 2$ and $|\\hat{\\mu}^j - \\hat{\\mu}^k| \\leq \\eta / 2$, yet  $|\\hat{\\mu}^i - \\hat{\\mu}^j| > \\eta / 2$ (e.g., consider $\\hat{\\mu}^i = \\eta / 2, \\hat{\\mu}^j = - \\eta / 2, \\hat{\\mu}^k = 0$) But, as $i \\sim k \\sim j$, $i$ and $j$ are indeed in a same cluster.", "experimental_designs_or_analyses": "The experimental designs seem appropriate. Some minor comments:\n\n1. Error bars missing from all experiments (Figure 1, Figure 2)\n2. The legends in Figure 1 is too small... As it seems that the legend is the same across the subfigures, consider separating the legend so that the text is legible...\n3. Section 8 states that each algorithm went through multiple independent runs. How many?", "relation_to_broader_scientific_literature": "- To the best of my knowledge, it tackles a new problem setting of federated FC-BAI with clustering structure\n- Interesting algorithmic idea of running SE with coupon-collected best arm candidates.", "essential_references_not_discussed": "None to my knowledge.", "other_strengths_and_weaknesses": "**Strengths:**\n1. New problem setting not considered before\n2. Interesting algorithms, especially BAI-Cl; the idea of using the coupon-collected best arms as input to the SE is quite interesting and to the best of my knowledge, novel\n3. Extensive related works\n4. Experimental results showing the efficacy\n\n**Weaknesses:**\n1. Writing should definitely be improved. The Appendix is especially riddled with unnecessary typos, hindering its readability. See Suggestions for a *partial* list of things that I found. This is one of the main reasons of my score not being higher; I could not check the correctness of the proofs in detail.\n2. There was a potential error in the proof, which (even though I didn't check the remainder of the proof for the reason mentioned above) makes me question the rigorous correctness of the overall proof. The algorithm design itself looks solid.", "other_comments_or_suggestions": "1. Why are all multiplications written as $a.b$? I've never seen this notation...\n2. Line 290 (right column): extra $+$\n3. Line 346: $>>$ => $\\gg$\n4. Line 698: $G_i, G_j$?\n5. Line 1225: broken citation\n6. Please use \\appendix before starting the Appendix, and please consider reorganizing/restructuring the Appendix..\n7. Misnumbering in the Appendix: What is Theorem 1? (Sec. 9.3)\n8. Not defined notations: what is $D(\\cdot, \\cdot)$ in line 657?\n9. The authors should remind in the Appendix that $\\epsilon_r = 2^{-r}$.\n10. Why say **proof sketch**?\n11. Table of sample complexities as well as communication costs for the three algorithms would help a lot in comparing those.\n12. It seems that the number of clusters $M$ does not need to be known in advance. The authors should mention this explicitly, as if $M$ is known, then one could just do 1-dimensional $M$-means clustering.\n13. (very minor) Could the authors consider using the author-year format (or something similar) throughout the main text? It's very hard to keep track of the references when they are referred to only by numbers.\n14. Conclusion (and preferably Future Work) should be included. Maybe move some of the related work part to the Appendix.", "questions_for_authors": "1. Can the authors comment on the optimality of the communication cost? I also suggest putting in such discussions in the main text.\n2. In Algorithm 1 line 17, is the agent selected randomly from each cluster? I don't think this is critical, but for rigorousness, this should be made precise.\n3. Can the authors elaborate on why SE is \"*easy-to-tune*\"?\n4. The algorithms are dependent on the knowledge of $\\eta$. What happens if the learner misspecifies $\\eta$ by overestimating or grossly underestimating it? Especially for the latter case, the authors mentioned in Remark 4.2 that it doesn't change the theoretical results. Does this mean that the theoretical guarantees with the *same* $\\eta$ hold regardless of which $\\eta' \\leq \\eta$ is used? Or is the guarantees holding with $\\eta$ replaced with $\\eta'$?\n5. Going further, one future work the authors could mention is making the algorithm parameter-free. For instance, Ghosh et al. (2023) (ref. [40]) proposed a double trick-type wrapper algorithm whose guarantee does not depend on the problem-specific parameter. \n6. Instead of constructing a nearest neighbor graph, how about taking a similar approach to Algorithm 2 of Yun & Proutiere (2016)?\n7. Overall, what is the main reason (theoretical intuition) for the performance gap between Cl-BAI and BAI-Cl? \n8. The upper bounds are with high probability, but the lower bounds are in-expectation. Any chance of closing this gap, either by adapting high-probability lower bound techniques (multiple hypotheses) of Tsybakov (2009), or different analysis of the algorithms?\n\n\nSe-Young Yun and Alexadre Proutiere. Optimal Cluster Recovery in the Labeled Stochastic Block Model. NIPS 2016 (https://arxiv.org/abs/1510.05956)", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kMCYSOx7YJ", "reviewer": "Reviewer_UFPL", "summary": "This work studies the problem of best arm identification for clustering of multi-armed bandits, where $N$ agents are grouped into $M$ clusters, with each cluster solving a stochastic bandit problem. The goal is to identify the best arm for each agent under a $\\delta$-probably correct ($\\delta$-PC) framework, while minimizing sample complexity and communication overhead.  The authors propose two algorithms: Clustering then Best Arm Identification (C1-BAI) and Best Arm Identification then Clustering (BAI-C1). They provide $\\delta$-PC guarantees for both methods, derive bounds on their sample complexity, and provide a lower bound for the problem class. They also propose a variant of BAI-C1 under additional assumptions, which is (order-wise) minimax optimal when $M$ is small. They also provide experimental results to validate the theoretical findings.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "**Additional references** We thank the reviewer for these pointers. As suggested by the reviewer, we will aim to do a more extensive review of the related literature on clustering in bandits. We would like to point out that one key difference between most of the literature there (including the papers pointed out above) and our work is in how the clusters are defined. While the literature mainly considers parameterized settings such as linear / contextual bandits where the clusters are based on the unknown user preference vectors, our setting is non-parameterized and the cluster definition is based on the mean reward vectors.\n\n**Assumptions 2.1 and 6.1** Thank you for raising this point. Note that our objective is to find the best arm for every agent\nin the system, and so it seems reasonable to *define* the clustering based on the best arms. Assumptions 2.1 and 6.1 essentially quantify a *separability* condition amongst clusters, based on how the best arm of a given cluster performs in other clusters. These assumptions allow us to provide analytical guarantees on the performance of our proposed algorithms; furthermore, as part of our numerical evaluation, we are able to at least identify a few real-life datasets where these assumptions do hold and our proposed schemes are able to provide significant savings in terms of sample complexity and communication cost.\n\nHaving said that, there might be other definitions of separability which might also be suited to our setup. However, we choose this since it aligns well with our overall objective of best arm identification.\n\n**Knowledge of $\\eta$** The reviewer's point is well-taken. Our response to this is two-fold:\n\n1) *Robustness to $\\eta$*: We have run additional experiments to illustrate that our algorithms are robust to the choice of $\\eta$. For the Movielens and the Yelp datasets, we run our algorithms assuming different values of $\\eta$ and have tabulated the results below. Each experiment is repeated 10 times. \n\nWe have the following observations on the impact of $\\eta$-misspecification on correctness and sample complexity. Firstly, as expected, when the assumed $\\eta$ is smaller than the true value, the algorithm recovers the best arms correctly. Surprisingly, the same in fact holds true even with larger values of $\\eta$ which illustrates that our algorithms are in fact quite robust to the choice of $\\eta$. Again, as expected, the incurred sample complexity grows as the gap between the assumed $\\eta$ and the true value increases, and there are errors in recovery when $\\eta$ is chosen too large.\n\n\n*Movielens*: $M= 6, N = 120, K = 316 , \\eta_{true} = 0.0027$\n\n| $\\eta$  | Cl-BAI (No. of Pulls) | Cl-BAI (Error) | BAI-Cl (No. of Pulls) | BAI-Cl (Error) |\n|-----------|----------------------|---------------|----------------------|---------------|\n| 0.16      | 7.9739185e+08     | 10          | 4.27459816e+08       | 10            |\n| 0.08      | 1.59879063e+09       | 0            | 9.29866052e+08     | 8          |\n| 0.04      | 3.15616948e+09       | 0            | 6.21368206e+08       | 5         |\n| 0.02      | 6.33333662e+09       | 0            | 1.02040616e+09       | 0         |\n| 0.01      | 1.26017946e+10       | 0             | 3.44881983e+09       | 0             |\n| 0.005     | 1.25831127e+10       | 0             | 3.73592584e+09       | 0             |\n| 0.0027    | 1.25917968e+10       | 0             | 3.90723456e+09       | 0             |\n| 0.0015    | 1.25652013e+10       | 0             | 3.71104286e+09       | 0             |\n\n \n*Yelp*: $M= 4, N = 80, K = 211 , \\eta_{true} = 0.375$\n \n| η     | Cl-BAI #Error | Cl-BAI #Pulls | BAI-Cl #Error | BAI-Cl #Pulls |\n|-------|-------------|---------------|-------------|---------------|\n| 3     | 10          | 10991089.6    | 10          | 4930620.3     |\n| 1.5   | 10          | 13096451.2    | 0           | 973381.7      |\n| 0.75  | 0           | 13062668.6    | 0           | 1403340.3     |\n| 0.375 | 0           | 13071359.4    | 0           | 985600.6      |\n| 0.187 | 0           | 13079278.4    | 0           | 1148393.8     |\n \n\n\n2) *$\\eta$ free algorithm*: Alternatively, we can remove the knowledge of $\\eta$ from our learning algorithms completely. We can propose a multi-phase algorithm where we start with a large enough value of $\\eta$, and at the beginning of each phase, we halve $\\eta$. After some phases, the value of $\\eta$ falls below the actual gap and the algorithms start learning the best arm. If we select exponentially increasing phase length, we can show this multi-phase algorithm will succeed in finding the best arms of all the agents. Rigorously proving the correctness is part of our future plans.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "No.", "experimental_designs_or_analyses": "No.", "relation_to_broader_scientific_literature": "The work is closely related to the literature of clustering of bandits. The authors study the setting of best arm identification for clustering of MAB, which is not yet studied to the best of my knowledge.", "essential_references_not_discussed": "This work is closely related to clustering of bandits. Though the authors have mentioned some works in this line, I think the related literature should be discussed more. Below are some references (not a complete list):\n1. Online Clustering of Contextual Cascading Bandits, AAAI 2018.\n2. Improved Algorithm on Online Clustering of Bandits, IJCAI 2019.\n3. Federated Online Clustering of Bandits, UAI 2022.\n4. Online Clustering of Bandits with Misspecified User Models, NeurIPS 2023.", "other_strengths_and_weaknesses": "Strengths:\n\n1. To the best of my knowledge, this is the first work to study the best arm identification in the clustering of MAB setting. \n2. The paper is well-written and easy-to-follow.\n3. The authors provide algorithms with sample complexity bounds, and prove a lower bound. \n4. They also provide experimental results to support the theoretical findings.\n\nWeaknesses:\n\nThe main weakness I am concerned about is the assumptions (Assumption 2.1 and Assumption 6.1), which seem to be strong. Additionally, for example, under Assumption 2.1, the algorithms need to know $\\eta$ (or a lower bound). In the clustering of linear bandit literature, there is also a similar assumption about the separation gap of the different feature vectors, but it does not need to be known. I am wondering if these assumptions can be relaxed.", "other_comments_or_suggestions": "No.", "questions_for_authors": "Please see the weaknesses above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "W0BxEWl5yv", "reviewer": "Reviewer_eVTA", "summary": "The paper explores the problem of identifying the best arms in a multi-agent bandit setting, where agents form (unknown) cluster-based structures.\nTo address this challenge, the authors propose two algorithms. The first algorithm, CI-BAI, first clusters the agents and then identifies the best arm for a randomly chosen representative from each cluster. The second algorithm follows the same two phases but in a different order.\nTheoretical analyses of both algorithms provide insights into their sample complexity and communication efficiency. Additionally, experimental studies demonstrate the effectiveness of the proposed algorithms.\n\n##  Update After Rebuttal\nAfter reviewing the authors’ response, I have decided to maintain my current score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "**Current state-of-the-art algorithm for Best Arm Identification (BAI):**  We choose Successive Elimination (SE) over other state of the art algorithms like Track And Stop (TAS) or Lower Upper Confidence bound (LUCB) for a number of reasons:\n\n(i) We aim to address the problem of Clustering and BAI jointly, and SE is a common tool to address both of these problems. In other words, SE could seamlessly be adapted to our problem formulation. The same thing can not be said for TAS and LUCB.\n\n(ii) For TAS, in general asymptotic guarantees are known, where as we require sharp non-asymptotic guarantees for proving correctness of our proposed algorithms. Some non-asymptotic guarantees of LUCB is known, however they are not immediately adaptable to our problem formulation. Moreover, SE has $3$ tuning parameters, namely the subset of arms, success probability and the number of rounds. Overall, SE is easier to tune compared to other best arm identification algorithms like TAS.\n\n(iii) We would like to clarify that the order-wise performance (sample complexity) of both SE and TAS are similar, whereas SE may have sub-optimal constants. In this work, we provide guarantees on order-wise sample complexity and hence TAS and SE would yield similar results.\n\n(iv) In terms of experiments, one can use other BAI algorithms. However, TAS is computation heavy as compared to SE. Hence, we have taken SE as a default choice.\n\n**Typos and Related work** We apologize for the typos. We have corrected them in the modified version. We have also added a few relevant and recent papers in the Related Work section and provided comparisons with them.\n\n**The paper lacks a discussion/conclusion section** Thank you for the suggestion. Indeed, we have added a Conclusion section now. Additionally we have corrected the typos, actively worked on the writing, and re-organized a few section (including appendix) to improve readability.\n\n**Why optimal TAS is not used?** Although we have discussed this in the first question, we summarize the comparison with TAS here:\n\n(i) Note that for TAS, in general asymptotic guarantees are known, where as we require sharp non-asymptotic guarantees for proving correctness of our proposed algorithms. Moreover, SE has $3$ tuning parameters, namely the subset of arms, success probability and the number of rounds. Overall, SE is easier to tune compared to other best arm identification algorithms like TAS.\n\n(ii) We would like to clarify that the order-wise performance (sample complexity) of both SE and TAS are similar, whereas SE may have sub-optimal constants. In this work, we provide guarantees on order-wise sample complexity and hence TAS and SE would yield similar results.\n\n(iii) We aim to address the problem of Clustering and Best Arm Identification (BAI) jointly, and SE is a common tool to address both of these problems. In other words, SE could seamlessly be adapted to our problem formulation. The same thing can not be said for TAS.\n\n(iv) Finally, in experiments, one can use other Best arm Identification algorithm like TAS. Hoever, TAS is computation heavy compared to SE. Hence, we have taken SE as a default choice.\n\n**Other relevant algorithms and comparison** There are a lot of works in bandit clustering albeit in a parametric setting. In other words, for linear bandits and contextual bandits (which are parameterized), one can naturally define a clustering based on the underlying unknown parameters. On the other hand, needless to say that there is a rich literature on the Best Arm Identification (BAI) problem without clustering structure. However, we are not aware of any other papers in the intersection of non-parametric bandit clustering and BAI, where our work lies.\n\nAlternatively, there are a few works on the BAI problem for Federated Bandits. Out of these, we consider [1]. Note that if we remove the notion of *Global best arm* from [1] and only focus on recovering *Local best arms*, the proposed algorithm there reduces to the naive algorithm we compare against since they do not consider any underlying clustering among agents. We would like to point out that, since we are interested in the BAI for all the agents, naturally the notion of *Global best arm* makes little sense in our setup.\n\n**Reference:** [1] Almost Cost-Free Communication in Federated Best Arm Identification; Kota Srinivas Reddy, P. N. Karthik, and Vincent Y. F. Tan; AAAI 2023.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes. The work is primarily theoretical but includes experiments with a reasonably well-designed evaluation.", "theoretical_claims": "I reviewed the flow of some parts of the proofs but cannot confirm the correctness of all of them.", "experimental_designs_or_analyses": "The design of the experiments conducted on synthetic and real datasets appears sound.", "relation_to_broader_scientific_literature": "The key contributions of paper are in direction of online decision-making (bandits) and distributed/federated learning.", "essential_references_not_discussed": "I am not aware of any missing prior works.", "other_strengths_and_weaknesses": "Strengths:\n\n1. The paper addresses a novel problem in best-arm identification (BAI) with clustered bandits.\n2. To tackle this problem, the authors propose two main algorithms. The second algorithm, BAI-Cl, presents a particularly interesting approach and demonstrates superior performance both theoretically and experimentally.\n3. The paper establishes worst-case and instance-based lower bounds for the problem.\n4. The conducted experiments show that the proposed algorithms are effective compared to the naive method and also the results align with some findings in the theoretical part. \n\nWeaknesses:\n1. It is unclear why the authors did not use the current state-of-the-art algorithm for BAI to achieve better sample complexity.\n2. The paper contains numerous typos and needs refinement. Additionally, a more comprehensive discussion of related work could be provided.", "other_comments_or_suggestions": "The paper lacks a discussion/conclusion section, and I believe the overall writing could be improved. Additionally, there are some typos, which I highlight below:\n\n* Line 117: It would be clearer to replace $ \\Delta_{m, k^{*}_{m}} $ \n\nwith\n$\\Delta^{*}_{m}$\n, for example, as the current notation is somewhat confusing.\n* Remark 5.1: \"woth\" → \"with\".\n* Line 1225: Possible typo and citation issue.", "questions_for_authors": "1. I did not fully understand Remark 4.1. Since the TAS algorithm is optimal, wouldn’t it be more reasonable to incorporate it into the proposed algorithm? What challenges prevent the direct application of TAS?\n\n2. Are there any other relevant algorithms that could tackle the problem, even sub-optimally? In the experiments, you compared your approach only against a naive method for identifying the best arms. Are there any alternative approaches beyond yours and the naive baseline that could serve as a more competitive comparison?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AFe28nG479", "reviewer": "Reviewer_n5GW", "summary": "This paper introduces a Best Arm Identification problem with clustering structures. Specifically, given $N$ agents and $M$ bandits instances (Usually $N>M$), each agent faces one of the bandit instance, but the mapping is unknown. The goal is to identify the best arm for each agent with probability at least $1-\\delta$. By making use of the clustering structure among the agents, this paper wishes to avoid repeated best arm identification within the same bandit instance, as the agents facing the same instance share the same best arm. Two algorithms (with an improved one) are proposed, CI-BAI and BAI-CI(++), which cluster the arms before and after the best arm identification process, respectively. Theoretical guarantees on the sample complexity are provided and a minimax lower bound is also provided. Experiments are conducted on synthetic and real datasets.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "**Knowledge of $\\eta$:** We run additional experiments to validate the robustness of our schemes. Please refer to our rebuttal of Reviewer UFPL.\n\n**Different bandit instances have Different best arms:** Our objective is to find the best arm for every agent, and so it seems reasonable to *define* the clustering based on best arms. Naturally, we put all the agents in a cluster who possess the same best arm. Furthermore, we are able to at least identify a few real-life datasets where these assumptions do hold.\n\n**$\\eta-free algorithm:** We can remove the knowledge of $\\eta$ from our learning algorithms completely. We can propose a multi-phase algorithm where we start with a large enough value of $\\eta$, and at the beginning of each phase, we reduce it by a factor of 2. After some phases, the value of $\\eta$ falls below the actual separation and the algorithms start learning the best arm. If we select exponentially increasing phase length, we can show this multi-phase algorithm will succeed in finding the best arms of all the agents. Rigorously proving the correctness is part of our future plans.\n\n**Cl-BAI vs Naive in real data:** As explained in the same paragraph (line 234-248), Cl-BAI will out-perform the naive algorithm if the `separability' parameter $\\eta$ is much bigger than the bandit sub-optimality (arm) gaps $\\bar{\\Delta}$; {in particular when $\\eta \\gg \\bar{\\Delta}$}. While this is the case in synthetic datasets, for the real datasets we chose, it turns out (based on our sub-sampling of data) that the bandit arm gaps are comparable to the cluster separation (e.g for Yelp, $\\eta=0.375$ and $\\bar{\\Delta} = 0.25$) , and hence the sample complexities are comparable.\n\n**Results for non-uniform clusters:** We invoke the results of coupon collector problem with unequal probabilities $p_1,\\ldots,p_M$, where $p_i$ is proportional to size of cluster $i$. From [1], the term $\\mathcal{O}(M\\log M/\\delta)$ in Theorem 5.3 will be replaced with the following term:\n$\n \\mathcal{O}[\\int_0^\\infty [1- \\prod_{i=1}^M (1-e^{-p_it})] dt]\\log(1/\\delta).\n$\n\n**Novelty and reliance on SE** Our goal is to perform both clustering and best arm identification jointly, and SE is a common tool to help in both the jobs. We believe the novelty of this work lies in utilizing SE for both clustering and best arm identification judiciously in a *sample efficient* manner. We choose to run SE with different combinations of the subset of arms, success probability and number of rounds to reduce the sample complexity which is highly non-trivial. The *easy tunability* of SE allows us do do this and obtain *near optimal* performance. To the best of our knowledge, this is not done in the literature yet. \n\nThis work may be viewed as the first step towards understanding parameter-free clustering in the Federated setup with the objective of finding best arms for all the agents (not *appropriately defined Global best arm*).\n\n**Knowledge of $M$:** The number of clusters $M$ is not needed to be known for Cl-BAI, where the clusters are created based on a nearest-neighbor graph type construction. For BAI-Cl and BAI-Cl++, knowledge of $M$ is needed since the first phase corresponds to recovering the set of all possible best arms using random sampling. Here, we do not require the exact value, any upper bound will suffice with a small increase in sample complexity.\n\n**Technical Contribution:**  (i) *Successive Elimination (SE):*  We believe the contribution of this work lies in utilizing and tuning SE for both clustering and best arm identification judiciously in a *sample efficient* manner which is highly non-trivial. As a result, we obtain *near optimal* performance in terms of sample complexity. Even though this seems apparently simple, to the best of our knowledge, this is currently absent from the literature.\n\n(ii) *Coupon Collector:* We use ideas from the *Coupon Collector* problem to improve the sample complexity of our proposed algorithm, $BAI-Cl$. Using this with SE, we find at least one agent from each cluster with a set of active arms containing the best arms from all $M$ clusters. In the subsequent phase, we let the rest of the agents play only from the obtained subset. Since the cardinality of this set can be much smaller than the total number of arms, we get an improved sample complexity, which is near optimal.\n\n(iii) *Lower Bound* We also use instance perturbation based technique to obtain lower bounds on the expected sample complexity. We obtain both instance dependent as well as instance independent bounds. The lower bound we obtain (nearly) matches the sample complexity of our proposed algorithm rendering them near optimal. Such a lower bound is also novel for this multi agent best arm identification problem.\n\n(iv) *Experiments* We run experiments on real datasets, Yelp and Movielens dataset.\n\n**Reference** [1]  \"Birthday paradox, coupon collectors, caching algorithms and self-organizing search\", Philippe et.al, Discrete Applied Math, 1992.", "claims_and_evidence": "The authors provide proofs for the theorems in the main paper. I skimmed through the proofs and it looks reasonable to me.", "methods_and_evaluation_criteria": "This paper makes extensive use of the Successive Elimination algorithm, a commonly used method in Best Arm Identification. It is employed to facilitate agent clustering and to identify the best arm for each bandit instance.", "theoretical_claims": "I skimmed through the proofs for the theoretical guarantees. They appear reasonable to me. I did not check every detail.", "experimental_designs_or_analyses": "For the synthetic dataset, it serves as a sanity check for the proposed algorithms. The experimental results align well with the remarks in the preceding sections.\n\nFor the real dataset, while the experimental results appear reasonable, I am not entirely convinced by the choice of \\eta. Assumption 2.1 is crucial throughout the paper, as the value of \\eta directly impacts the advantage of the proposed algorithms over the naive approach. However, the choice of $\\eta$ (and $\\eta_1$) seems highly instance-dependent. For example, in the MovieLens dataset, $\\eta = 0.0027$, whereas in the Yelp dataset, it is significantly larger at $\\eta = 0.375$. Additionally, the authors verify that these datasets satisfy Assumptions 2.1 and 6.1 using ground truth instance parameters, which are not accessible in real-world scenarios.\n\nTo address this concern, I recommend that the authors conduct experiments to evaluate the robustness of the proposed algorithms when Assumption 2.1 does not hold or when $\\eta$ is misspecified.", "relation_to_broader_scientific_literature": "This paper falls within the field of Bandit Algorithms, specifically focusing on Best Arm Identification with fixed confidence. The authors assume the presence of $N$ agents and $M$ bandit instances, along with an unknown mapping between them. An effective algorithm should leverage the clustering structure to minimize redundant identification efforts.", "essential_references_not_discussed": "The references appear well-selected and appropriate.", "other_strengths_and_weaknesses": "**Strengths**\n1. The problem formulation is well stated. \n2. Upper bounds of the proposed algorithms are presented, as well as a minimax lower bound which indicates the upper bound is tight in some parameters under some instances.\n3. The paper also discussed the communication efficiency of the proposed methods, indicating a trade-off between communication cost and identification efficiency.\n\n\n**Weaknesses**:\n1. The assumptions are quite strong\n\t1. It assumes different bandit instances have different best arms, which may not be general enough.\n\t2. Assumption 2.1 requires the knowledge of $\\eta$, which is crucial for the proposed algorithm.\n2. While Line 248 claims that CI-BAI will be better than the naive algorithm, it is not observed in the experiments with real datasets.\n3. It would be great if the authors can specify the results for the case for non-uniform clusters, as mentioned in Remark 5.6, since the assumption that the agents are uniformly distributed is restrictive in Theorem 5.3.\n4. The paper relies heavily on Successive Elimination, which makes it difficult for me to discern the technical novelty of the proposed method.", "other_comments_or_suggestions": "1. Line 274 right: woth high probability -> with high probability.", "questions_for_authors": "1. This paper assumes the number of bandits $M$ is known at the beginning. Is it possible to remove such knowledge? e.g., in the MovieLens experiment, authors manually classify the users according to the ages and obtain $6$ clusters. Is it possible to remove the knowledge of $6$ and let the algorithm learn this automatically?\n2. Can the authors highlight the technical contribution of the proposed method?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "None."}}]

Author rebuttal:

Meta-review: This paper consideres the problem of finding the best arm among $K$ arms for each of $N$ agent simultaneously with probability at least $1-\delta$. Each agent belong to one of $M$ groups and reward distribution is per each group. The author proposed algorithm CI-BAI (clustering then BAI) and BAI-CI (BAi then clustering). The sample complexity of the algorithms are analyzed and matches to the possible limit in terms of minimum suboptimality gap $\Delta$ and $K,M,N$. 

All reviewers are positive about the paper and these comments are informative enough. The problem setting seems to novel and there is no critical concern, Rev Dq4J considers potential mistake on the proof but it seems the reviewer is fine on the main results. Therefore, I recommends an acceptance. I recommend the authors to revise the paper according to the reviewers' suggestions. For example, most reviewers discuss the knowledge on $\eta$ (suboptimality gap between two clusters). Also Rev n5GW pointed out on the assumption of uniform distribution of the agents to clusters. Finally, please make sure to address the concerns of Rev Dq4J on the solidness of the results.
Decision: Accept (poster)