Near-Optimal Collaborative Learning in Bandits
Authors: Clémence Réda
Sattar Vakili
Emilie Kaufmann
Venue: NeurIPS 2022 Accept (2022)
Keywords: collaborative learning
multi-armed bandit
centralized learning
communication
elimination based-algorithm
data-driven sampling

Abstract: This paper introduces a general multi-agent bandit model in which each agent is facing a finite set of arms and may communicate with other agents through a central controller in order to identify -in pure exploration- or play -in regret minimization- its optimal arm. The twist is that the optimal arm for each agent is the arm with largest expected mixed reward, where the mixed reward of an arm is a weighted sum of the rewards of this arm for all agents. This makes communication between agents often necessary. This general setting allows to recover and extend several recent models for collaborative bandit learning, including the recently proposed federated learning with personalization [Shi et al., 2021]. In this paper, we provide new lower bounds on the sample complexity of pure exploration and on the regret. We then propose a near-optimal algorithm for pure exploration. This algorithm is based on phased elimination with two novel ingredients: a data-dependent sampling scheme within each phase, aimed at matching a relaxation of the lower bound.

Near-Optimal Collaborative Learning in Bandits
Clémence Réda Université Paris Cité, Inserm, NeuroDiderot, F-75019 Paris, France clemence. red.iiniaardiiii
Sattar Vakili
MediaTek Research, Cambourne Business Park, CB23 6DW, United Kingdom sattar, vakili emttreesearch.com com
Emilie Kaufmann
Université de Lille, CNRS, Inria, Centrale Lille, UMR 91 CRISIAL, F-59000 Lille, France
amilie.i kaufmann&umiv--illle
Abstract
This paper introduces a general multi multi-agent bandit model in which each agent facing finite set of arms and may communicate with other agents through a central controller in order identify -in pure exploration- or play -in regret minimization- its optimal arm. The twist is that the optimal arm for each agent is the arm with largest expected mixed reward, where the mixed reward of an arm a weighted sum of the rewards of this arm for all agents. This makes communication between agents often necessary. This general setting allows to recover and extend several recent models for collaborative bandit learning, including the recently proposed federated learning with personalization [30]. In this paper, we provide new lower bounds on the sample complexity of pure exploration and the regret. We then propose a near-optimal algorithm for pure exploration. This algorithm based on phased elimination with two novel ingredients: deta-dependent sampling scheme within each phase, aimed at matching a relaxation the lower bound.
Introduction
Collaborative learning a general machine learning paradigm in which a group of agents collectively train a learning algorithm. Some recent works have investigated how agents can efficiently perform sequential decision making in collaborative context (36). In particular, Shi al. propose an interesting setting to tackle collaborative bandit learning when some level of personalization is required [30]. Personalization leads to the twist that each agent should play best arm a mixed model which is obtained combination of her local model with the local model of other agents. In this work, we introduce a more general model retaining this idea, that we call the weighted collaborative bandit model.
In this model, there are M agents and finite number of K arms. When agent m samples arm at time f, she gets to observe a local reward Xt.m (t). which is drawn from a I-sub-Gaussian distribution of mean 44,m, independently from past observations and from other agents' observations. However, this agent does not necessarily seek to maximize her local reward, but rather some notion of mixed reward, related to the utility of that arm for other agents. More specifically, we assume that agents share a known weight matrix W == (wn,m) m. m.m é [0. Mx.M such that Ene[Mr] Wn.m
A random variable X said to be o -sub-Gaussian if, for any À R, In( s 50 x2
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

for all m [M], where [1, The mixed reward at time t for agent m and arm ls is
defined as weighted average of the local rewards across all agents X km (t) == Σ W/.m X k. (t), and its expectation, called the expected mixed reward, is
M Pk.m Σ n=1
Wn,mPknn
We denote by kn := arg maX Pe.m the arm with largest expected mixed reward for agent m, assumed unique. Besides the degenerated case in which Wn,m = I (n = =m), in which each agent is solving their own bandit problem in isolation, the agents need communicate i.e., to share information about their local rewards to other agents for everyone to be able to estimate their expected mixed rewards. A strategy for an agent is defined follows: at each time t. each agent m samples an arm Tm mt))), (t), based on the available information, and then observes noisy local reward from this arm. She has also the option to communicate information (e.g.. empirical means of past local observations) to central controller (or server), which will broadcast this information to all other agents. Just like in any multi-armed bandit model, several objectives may be considered, either related to maximizing (mixed) rewards -or, equivalently, minimizing regret- or identifying the best arms, while maintaining a reasonably small communication cost.
The weighted collaborative bandit model encompasses different frameworks previously studied in the literature. Notably, the paper [30] studies a special case which, given a level of personalization E [0, 1J, the mixed reward is an interpolation between Pk.m and the average of local rewards
1-a for 1 Emd Me,n which amounts to choosing Wm,m a+ 1-0 and Wn,m M consider the objective of minimizing the regret while minimizing for the number of communication rounds, under the name federated multi-armed bandit with personalization? In this paper, we mainly focus on the counterpart pure exploration problem in which agents should collaboratively identify their own optimal arm in terms of expected mixed reward, with high confidence, and using few exploration rounds as possible. This extends the well-studied fixed- confidence best arm identification problem 2 4 20 to the weighted collaborative bandit setting.
The authors
M
Another related setting is collaborative pure exploration [8 32 35 which considers M agents solving the same best arm identification problem. Most of these papers propose algorithms to solve this problem, while [32) and [2I] also prove lower bounds on sample complexity for the fixed-confidence and the fixed-budgee best arm identification. Unlike our framework, [6] consider asynchronous agents, which can only sample at some times, whereas [35] 36)
consider agents which can only communicate some of the other agents. The goal of collaborative pure exploration is to reduce sample complexity at the cost of some communication rounds. Our model recovers the synchronous setting when considering M Pk.m for all arm i and agents m, m' and W Id,s
Besides collaborative learning, the work of (34 considers a similar weighted model but in a different, contextual bandit setting in which a central controller chooses in each round an arm for the unique agent (corresponding to sub-population) that arrives, and aim at minimizing regret. Finally, the paper [29] considers a pure exploration task in which the value of an arm is the weighted average of its utility for M distinct populations (agents). In this setting Wn.m = ap, so that all agents have a common best arm, but the proposed algorithms do not aim at low communication cost.
Collaborative learning in our general weighted model is also interesting beyond these examples. In particular, the work of (30] mentioned possible applications to recommendation systems, for which one may want to go beyond uniformly personalized learning. The "personalization" part means that we favour the local rewards of agent m over other agents' observations in the identification of optimal arm ki But the introduction of a general weight matrix W our framework allows any agent m to consider any linear combination of the other agents' observations, and then, different degrees of personalization across agents.
Such setting could also be appropriate for adaptive clinical trials on K therapies, run by M teams who have access to different sub-populations of patients. In this context, each sub- uub-population is typically aiming at finding their (local) best treatment. However, solving their best arm identification in isolation may have a large sample complexity. If one willing to assume that we have a
2 Their setting, as well as ours, is neglecting some challenges typically addressed in (centralized) federated learning, such as privacy issues or dealing with communication interruption, this is why we prefer naming our framework "collaborative learning".
2

---

weight matrix W for which the best mixed arm of each agent coincides with its local best arm, i.e. k;, arg [=]] Mk.m for any agent m, then solving best arm identification in the weighted collaborative bandit could have a much smaller sample complexity due to the sharing of information, while allowing the different clinical centers to communicate only once in while. A first possibility to build such a weight matrix is to rely on a clustering of the different sub-populations so that the Mg.m is supposed to be close to un, (but not necessarily equal) for all i: and all agents m, m' in the same cluster. Denoting by C. the cluster to which agent yn belongs, by setting Wm,n 1(Cm C.) Cm] we would have the mixed mean of each agent be very close to their local means. Another possibility is to rely on similarity function S between sub sub-populations and define for all n. m Wm.n to be proportional to 5(m,n), This similarity function could be obtained prior to the learning phase by computing the similarities between subpopulation biomarkers, for instance.
Related work Collaborative bandit learning has recently sparked wide interest in the multi-armed bandit literature. While some works do not deal with personalization [1 31 26), others have for instance studied the integration of arm features in a modified setting with personalization [9]] An interesting kernelized collaborative pure exploration problem was recently studied by (IO). In their model. both agents and arms are described by feature vectors, and there is a known kernel encoding the similarity between the mean reward of each (agent,arm) pair. This independent work follows similar approach as ours and also propose a near-optimal phased elimination algorithm inspired by a lower bound, but the models and related lower bounds are significantly different.
In bandits working in collaboration, the need for a small communication cost indeed makes algorithms based on phased eliminations appealing. In such algorithms, agent(s) maintain set of active arms that are candidate for being optimal, and potentially eliminate arms from this set at the end of each sampling phase. Adaptivity to the observed rewards (and, in our case, communication) is only needed between sampling phases, which are typically long. This type of structure has been used in various
bandit settings, both for regret minimization or pure exploration objectives 2 18 5
30 B).
In some of these algorithms, including the one in [30 which motivates this paper, the number of samples gathered from an arm which active in some phase r is fixed in advance. We believe that going beyond such a deterministic sampling scheme is crucial to achieve optimal performance with phased algorithms. In order to achieve (npaaa-ot other phased algorithms rely computing an oracle allocation from the optimization problem associated with a lower bound on the sample complexity [3 10 In these works, based on this allocation, a total number of samples collect in the current phase is computed, which depends on the identity of the surviving arms. The distribution of samples across arms for the current round is proportional to the oracle allocation, and obtained through a rounding procedure. Compared to these works, our algorithm will show three distinctive features: an allocation inspired by a relaxation of the lower bound, which does not only depend on the identity of surviving arms, and an alternative to the rounding procedure.
Contributions The authors of (30 exhibit an algorithm using phased elimination for federated bandit learning with personalization, and prove a logarithmic regret bound, whose dependency in the parameters of the problem is conjectured be sub-optimal. They also propose a heuristic improvement, based on a more adaptive exploration within each phase. In this work, we take step further in identifying the collaborative bandit model -which includes the setting of [30] as special case- both from the pure exploration and the regret perspective. We propose new information theoretic lower bounds, and recipe to design algorithms (nearly) matching those for pure exploration. Our main algorithmic contribution is for weighted collaborative best arm identification. Our phased ilimination-base algorithm achieves minimal exploration cost up some logarithmic multiplicative factors, while using a constant amount of communication rounds. It relies on a novel data-dependent sampling scheme, which renders its analysis trickier. The structure of the algorithm can easily be extended to Top-N identification, that is, where each agent has to identify her own N best arms (instead of her best for N 1) with respect mixed rewards. We further compare our novel regret lower bound to what was conjectured in [30] for the particular case of federated learning with personalization.
complexity of bandit learning in our novel weighted
Notation For both best arm identification and regret minimization, our complexity terms feature the (mixed) gaps of each agent m and arm h; defined by
Pka... m 1kg. if # kin min p.
D/.m :=
otherwise.
3

---

2 Collaborative Best-Arm Identification
The goal of collaborative best-arm identification is that each agent m identifies its optimal arm kü by sampling the arms as little as possible and with few communication rounds. Formally, collaborative Best Arm Identification (BAI) algorithm consists of sampling rule 3m for each agent m, such that, at time f, either arm Tm (t) [K] is sampled by m, or Tm (t) 0 in that case, instead of picking an arm at time I, we allow the agent to remain idle, and not to select an arm. Similarly to the communication model studied in [32 60 communication only happens at the end of local sampling rounds for all agents, when all agents are idle at the same time. Besides the sampling rule, the BAI algorithm uses a stopping rule J which determines when exploration over for all agents. The end of exploration is decided by the central server. Then, at time T, each player outputs a guess for its optimal arm with respect to mixed rewards, denoted by km.
Our goal is to construct a d-correct strategy A= (IT, T, k), which satisfies, for any model μ IR KxM
Pd (Ym [M = km 2 21-8,
while achieving a small exploration cost (c.g. in high probability or in expectation)
(x)
Σ Σ (N),(()..
122 k=1
where Na.m (1)== Ex-1 I (xm ())= is the number of selections of arm & by agent up to time 4, and a small communication cost, defined
CA) = 1I))
1=1
where Ie is the event that some information is shared between agents at round
In our setting, we do not put constraints on the type of information that is exchanged in each communication round -which can be interesting when we consider privacy issues [I] 36 nor on the lengths of the messages. Each communication round has unit cost. In a communication round, all agents send messages to the central server (e.g., estimates of their local means) and the server can send back arbitrary quantities or instructions (e.g., how many times each arm should be sampled in next exploration phase, and when to communicate next).
Moreover, contrary to the works of [8 32 on collaborative learning, we do not look at strategies explicitly minimizing for the number of communication rounds. Instead, our approach consists in proving a lower bound on the smallest possible exploration cost of 8-correct algorithm which would communicate every round: and then, finding an algorithm for which exploration cost matches this lower bound, while suffering a reasonable communication cost.
3 Lower Bound
We prove the following lower bound on the exploration cost of an algorithm which all agents communicate to the central server their latest observation as soon as they received it. It holds for Gaussian rewards with variance σ² 1, meaning that the reward from an arm & observed time I by agent m will be XR.m (1) μ4 + Et where & N(0, 1). We further assume that the weight matrix W satisfies Wm.m # 0 for any agent m [M].
Theorem 1. Let μ be a fixed matrix of means in RKM For any 8 e (0, 1/2], let A be a 8-correct algorithm under which each agent communicates each reward to the central server after is observed, and let us denote for any k E [K] m e [M], Tk.m := BA
_m{M)
[N (T)] where is the stopping time. B
For any m e [M] and k + W it holds that
(A )2 12
1
Σw 2 n.m.
S
Tkin
The
log (2(48)))
and therefore E, [Exp, (A)] 2 Tw (n') log (222)) ), where
NNot that, in regret setting, idle agent may exploit its empirical best arm.

---

Ti (1)
min te( ) ((mm){[K)[[M
Σ tkmm Vm, + Km
Σ nd Mc[M]
Wn.
1
A
k.m
1k.a
The proof, given in Appendix A. uses standard Dhange-of-distributioo arguments, together with classical results from constrained optimization. Note that, for M 1, we recover the complexity of best arm identification in a Gaussian bandit model [15].
Computing the complexity term The optimization problem which defines Tiy (4) belongs to the family of disciplined convex optimization problems, and can be numerically solved using available solvers, such as CVXPY M 19. We now illustrate, on small example, the possible reduction in exploration cost that can be obtained by solving weighted collaborative best arm identification instead of M parallel best arm identification problems. We consider K M 2 and similarity S(1 2)= = 0.9 between the two agents, which yields the following normalized weight matrix
1
0.9
W
1.9 0.9
1
Considering the following matrix of expected rewards
[..9
0.8
=
0.1
0.5
for which arm 1 is the local best arm for both agents and is also their best mixed arm, we obtain ( 28. However, if cach agent solves its own best arm identification problem in isolation (which amounts to using W Id2), the resulting exploration cost scales with Tía (4) s 101 > (p).
From lower bounds to algorithms In single-agent pure exploration tasks, lower bounds are usually guidelines to design optimal algorithms, as they allow to recover an oracle allocation (i.e., the [ )K.M in the definition of Tw (P)) which algorithms can try to achieve by using some tracking 115 10 29]. Yet, these approaches may be computationally expensive, as they solve the optimization problem featured in the lower bound in every round.
arg min for / ε (IR
In the next section, we will propose an alternative approach for our collaborative setting, which exploits the knowledge of the lower bound within phased elimination algorithm. This is crucial to maintain a small communication cost and also permit to reduce the computational complexity compared to pure tracking approach. Our algorithm will rely on a relaxed complexity term Tw (p). which is within constant factors of Ty (J),, as proved in Appendix C.I
Lemma 1. Introducing the quantity
w Wn,
(A).m))
(p):
min te(R+)KoA KOMM
tR : Vm, Vk [K]. Σ [KK())[
Σ
tke
2
ne[M]
holds that Twr(w) S (w) s (n).
Compared to Tw (n), a nice feature of (H) that its constraint set does not depend on the knowledge of (kin MM] which will allow to design algorithms that do not suffer too much from bad empirical guesses for Kü, in early phases. We further remark that the computation of Tw-(p) and that of its associated oracle allocation (see Definition I are slightly easier than for Ti (μ).. Indeed, the optimization problem which defines Tú (n) can be decoupled across arms. Computing for every arm & [K] the vector
2
km
argmin Σ F (Kmm){[K]{[MM
A The s.t. Vm, Σ ME[M]
S
2
we obtain the argmin in Ti (4) by setting (4a.)) (7h k.mm The computation of T (μ) can therefore be done by solving K disciplined optimization problems (e.g., with CVXPY involving M variables, instead of one optimization problem with K M variables.
5

---

Definition 1. For any A E (R*) KxM, the oracle (*) (A)it is
(B*)
(At.m) )²
arg min (Tk,m) kmmmm ( (oeetRRohh Raad k.m
Σ
Tk s.I.mm [M], vk [K], ne
Tkin
2
With this notation, observe that T (1d) Ek.m Tk.m where (Tk.m) k. P (A). The following lemma will be useful to compare values from different oracle problems. The full lemma along with its proof is available in Appendix C.I
Consider A A' E (IR2) (RRt)RXM, such that T e (A) and I' E fr (A)). Moreover, assume that there is a positive constant such that: V ke m. km km Then
Lemma 2.
12 Tk.m S E
4 A Near-Optimal Algorithm For Best Arm Identification
We now introduce an algorithm for collaborative best-arm identification, called W-CPE-BAI for Weighted Collaborative Phased Elimination, stated Algorithm| [ To present an analysis of this algorithm, we assume that, for any k, m E [K] x [M] Mkkm E [0,1] and that local rewards (X (t)) k,m, are Sauu-Gaussiin.
W-CPE- LACCE-BAIPA proceeds in phases, indexed by r. In phase r we let B, (r) be the set of active arms for agent and B(r) B. (r) be the set of arms that are active for at least one agent. The algorithm maintains proxies for the gaps (Ak, (r)) (r)))e] []me]]] that are halved the end of each phase for arms that remain active. At the beginning of each round, the oracle allocation t(r). with respect to the proxy gaps, is computed, as well as the number of new samples d (r) that player m should get from arm k in phase du. m (r) is defined such that the total number of selections of arm k by agent m becomes close to (a quantity slightly larger than) 1 (r) log(1/
We observe that any arm k B(r) will not get any new samples in phase as the proxy gaps (Ak.a (r)) are identical to those in the previous phase therefore (z,, = (r - 1). In contrast to prior works, where the allocation in each round only depends on the identity of the surviving arms and the round index 13 10 W-CPE-BAL also depends on when the arms have been eliminated (which condition the value of their frozen proxy gaps).
After each agent m samples arm is (r. times, they send their local means Pa m (r) to the central server, which computes the mixed mean estimates (r) := EM= Wn,m/kk (r) The active sets (Bm() (r) Me[M]] of all agents are then updated by removing arms whose mixed means are too small. As in several prior works [22] 30) we rely confidence intervals perform these eliminations. However, constructing confidence intervals on the mixed means -which are linear combinations of the local means- under our adaptive sampling rule is more challenging than when the number of samples from an active arm in phase r is fixed in advance -which is the case for instance in the algorithm in 30 The width of our confidence intervals scales with the following quantity
Definition 2. For any k. m, and round r O. we define
2 m. ne
On = Bs (nx,
Σ 12
where nm.m (r) is the number of times arm was selected by agent m by the end of phase r (included), and + (N) is a threshold function defined for any N (IR+M
Leveraging some recent time-uniform concentration inequalities (3), we exhibit below a choice of threshold that yields valid confidence intervals on the mixed means (by "projecting" confidence intervals that can be obtained on local means, see Proposition 24 (23). The fact that the confidence interval depends on the random number of past draws (and not just the index of the round) leads to some non-trivial complication in the analysis, with the introduction of quantities (dk.,)).. The proof is given in Appendix C.2 where also provide explicit expression of the function gM

---

Algorithm 1 Weighted Collaborative Phased Elimination for Best Arm Identification (W-CPE-BAI)
Input: 8 (0, 1), M agents, K arms, weights matrix W
Initialize O, Vk, m, Am.m (0) nt.. (0) 1, Vm, B, (0) [K]
Draw each arm & by each agent once repeat
# Central server
B(r) - UmE[M]] Bm (r) Compute t(r) + P. ((V2āR,m ())))
k.m
For any KE [K]. compute
Edn s.t. Vm [M], 7k.m (r- dm
(dkm (1)mm(r))mar (r)) [M] arg min deNM
(T)
B8 mk, (r 1) + d)
Send to each agent m (dk. (r)) and dmax maxxe[[]] EKE[K] dr,
Agent m
Sample arm & Br) dr. (r) times, so that (r)) nk.m (r 1) du Remain idle for dmaa - Eke[K] [K] ox (r) rounds
Send to the server empirical mean ou (r) == Eosma.m (r) Xu.m m2/ (r) for any k [K]
Central server
Compute the empirical mixed means (P (r)) based on (p (r)) and W
I/ Update set of candidate best arms for each user
for m M do
k Bm (r) (m)m(r) max jeBm((t (1l.. (r)-((.)()))))) 22)m((1))
Bm (r + 1)
end for
II Update the gap estimates
For all ki, m. Ak. (r 1) (r) x (1/2))(64B. +1
+ r +
until Vm [M]. [Bm (r) $
Output: {&e Bm (r) m e [M]]
Lemma 3. Let us define
3a(N) = 2 9M
+2
Σ m=1
In + In (NNm))
KM/
for any N e (N*) where gMs is some non-explicit function, defined in (23). that satisfies gas (6) Then the good event
log (+) + .M log log
(t). (2)
E = (VrEN, Vm, Vk, p (r) - 1k.mm S 2a.m (r))
holds with probability larger than -
From this lemma, it easily follows that W-CPE-BAL is 5-correct for the above choice of threshold function, as, for any agent m no good arm k;, can ever eliminated from B,, (r) at round r The fact that the sample complexity W-CPE-BAI scales with T (n') on the good event comes from the interplay between the expression of Qtmm (r) (which, up to the threshold function, is exactly one of the constraints featured in the lower bound) together with the definition of the allocation t(r), which leads to the following crucial result in analysis
Lemma 4. On E, Vk, m. 2 0, Qu (r) A (r)

---

Proof. For any round and arm k, by Algorithm and the definition of oracle tk (r), for any agent m,
(r de.) V E wh.n mn - 1) (r) S
En (u.n(r) (r)
2
if k B(r).
(r) =
En (
Am. (1k) Bn (r) otherwise
where when k B(r), r sup(r's / 20:k B(r'),, and we use the fact that dx.m (r) = =0 when k f
We did not put much emphasis on the way communications are performed between the agents and the central server, as several choices are possible. The important part that the server receives all values of the local means (jim. (r)mm())))n) (r)),, at the end of round r Our suggestion is that the central server maintains the sets (Bm (T)) me[Md] calls the oracle, and sends to agents their values of (dk. + k)m km the end of each phase In any case, the number of communication rounds in our definition will be equal to the number of phases used by W-CPE-BAL. All in all, we prove
Theorem 2. With probability exploration at most
W-CPE-BAL outputs the optimal arm for each agent with an
32 (11) log, (8/ log (1) + og loog (
and at most [loga (8/4(min) communication rounds, where A'nin == minge (K) A
Proof sketch The detailed proof given in Appendix B, where we also provide an explicit upper bound the exploration cost. We let R denote the (random) number of phases used by the algorithm before stopping. On the good event & we can prove that the algorithm never eliminates k,m therefore R == max max RR.m where Rg.m is the last phase in which k Bn (r) Using Lemma can easily establish that
Rkm S Thmm == min (r 0: 0:4x2 < m
which satisfies rk.m & log2(8/ m. This yields R s log, (0gg(8/44 (min) and further permits to prove that the proxy gaps can be lower bounded by the true gaps:
1 $ A
Vr s R, Vk [K],, Vm [M], 3e.m
See Corollary 2 in Appendix B Using the monotonicity properties of the oracle that are stated we can then establish that the allocation t(r) computed from the proxy gaps in the algorithm satisfies
in Lemma 2
VrsR. R.
Σ (x) 32 (n)).
(1)
ke[K].me([M
To upper bound the exploration cost, the next step is to relate Tikm m (R) to the oracle allocations. To do so, we observe that Hy is the last round before such that dx (r) + (i.e. the last round in which arm & is actually sampled by agent m then mm (R) = ng ()), we have by definition of the (du, (r) km that
7k.m (R'.m) S tm (R
(Rr,,)) + mm ( (R (nx, (R)) +1
See Lemma 12 in Appendix
We can then upper bound Σk,m 7k,m (R) as follows
T
S
Im (r 38 (R)) KM S Σ Σ 4e (r) (T) + KM, Σ
k.m
k.mreR
and r
S R 32 (p)33 KM, where we use I and introduce
(2)
(r)) (
9M
8
2M In (4+ (n))
KM/
The end of the proof consists using the known upper bound on R, and finding an upper bound for the largest satisfying the inequality in (2).
D

---

Discussion Theorem proves that W-CPE-BALL is matching the exploration lower bound of Theo- rem in a regime where å small, up multiplicative constants, including logarithmic term in 1/4 min- It achieves this using only [log2 (8/2 communication rounds. We note that a similar extra multiplicative logarithmic factor present the analysis of near-optimal phased algorithms in other contexts [33 [O]_ Such quantity appears as upper bound on the number of phases, and may be a price to pay for the phased structure.
On the communication cost We argue that the communication cost of W-CPE-BAL is actually of the same order of magnitude as that featured in some related work. In 30] which is the closest setting to our framework, the equivalent number of communication rounds p needed to solve the regret minimization problem is upper bounded by O (2 log, (8/(VM (Ainn mi)))) ))). In the setting of (2 collaborative learning -where M agents face the same set of arm distributions and W Id- [18] in their Theorem 4.1 prove that an improvement of multiplicative factor 1/ 1/M on the exploration cost for traditional best arm identification algorithm can be reached by using at most [loga (1/Ammm)) communication rounds, where Amin is the gap between the best and second best arms.
Experimental validation We propose Appendix F an empirical evaluation of W-CPE-BAI for the weight matrix Wm.. = a (n m) 1-a which corresponds to the setting studied by 30) In this particular case, we propose as baseline a counterpart of the regret algorithm of (30 which we call PF-UCB-BAL Our experiments similar performances in terms of exploration cost and that W-CPE-BAI becomes better when the level of personalization is smaller than 0.5. Moreover, W-CPE-BAI uses less rounds of communication than PF-UCB-BA BAI for all values of a. Finaly, the near-optimality of W-CPE-BAI empirically observed when compared reader to Appendix E for further details on the optimization libraries that were used.
synthetic instance show that W-CPE-BAL EPPE-BAI and PF- FF-UUC--BAL have
oracle algorithm which has access the true gaps. We refer the
Remark 1. The analysis and the structure of Algorithm 7 have the potential to be extended to other pure exploration problems, with similar guarantees. In Appendix D we illustrate this claim by tackling Top-N identificatin.
5 Regret Lower Bound
In contrast to the BAI setting, 30
considered the objective of minimizing the regret
M T
(T) ==
E
Σ
Σ
(u
m Mm (1) .m)
They provided conjecture the lower bound regret in personalized federated learning [see, 30 Conjecture 1]. As mentioned introduction, their reward model is a special case of ours with In this section, prove regret lower bound with general weights that proves in particular Conjecture 1 in [30]-
weights Wm,m
I-a and Wn,m M
I-a for
Mf
We prove the following result, for an algorithm that selects in each round exactly one arm for each agent, and all agents communicate after each round. This lower bound holds for Gaussian arms with variance x² 1.
Theorem 3. Any uniformly efficient algorithm in which all agents communicate after each round satisfies
lim inf R(T) 7-000 log(T) (T)
2 (w)(
where
wmm (A
(4/.. km
)
min (w)(n) == oz c=(ca.m mackt
Σ Σ Ck 4.m Vk E [K], Vm e [M],
Σ
<
1= mike
noke 2k
Ck,n
2
We recall that for any agent m, Agr ming Ap.m
A uniformly efficient algorithm satisfies R. o(1") for any e (0, 1) and any possible instance μc

---

Theorem may be viewed as an extension of the lower bound of [25] to the collaborative setting. Its proof, given in Appendix A. uses classical ingredients for regret lower bounds in (single agent) structured bandit models
The generic approaches proposed in g for optimal regret minimization in structured bandits could therefore be useful. However, to turn them into a reasonable algorithm for the collaborative setting, we would need to preserve the phased elimination structure. Analogous the relaxation in the BAI setting, can also define a relaxed complexity term Cas(p) which does require the knowledge of the best arms, and is within constant factors of C(x) by the following Lemma 5 (which proof is given in Appendix C.3).
Lemma 5. Introducing the quantity
K
M
M
w
(A km
(u) = min
Σ
Σ
Ck. A s.t. Ak E [K], Vm e [M],
Σ 5
CE(R) JKC
1= m-1
n=l CR,n
2
it holds that Cit (u) Tw (1) S (w)
The constrained optimization problems governing the regret lower bound subtly different from those in the BAI setting. In regret minimization, unknown gaps (4),m) appear both in the constraints and in the objective. In contrast, in BAI, (..,m)).m only appear in the constraints. Due to this difference, designing a similar algorithm for regret minimization leads to an extra multiplicative m(1/mmin) factor in the upper bound. A very similar issue exists in different structured bandit problem, bandits on graphs with side observations, where arms are connected through a graph with unweighted edges, and the agent receives the reward associated with the selected arm and its neighbors at given round. In [4] Problem P1]. authors describe a constrained linear optimization problem which governs the regret lower bound, and face the same issue of scaling in (11/Amin) Dealing with this problem would be an interesting subsequent work.
Conclusion
This paper introduced a general framework for collaborative learning in multi-armed bandits. Our work presents two novel lower bounds: one on the exploration cost for pure exploration, and another on cumulative regret. The latter permits to prove a prior conjecture on the topic. Moreover, we propose a phased elimination algorithm for fixed-confidence best arm identification. This algorithm tracks the optimal allocation from the pure exploration lower bound through novel approach solving a relaxed optimization problem linked to the lower bound. The exploration cost of this algorithm is matching the lower bound up to logarithmic factors. This strategy can be extended to other pure exploration problems, such as Top-N identification, as shown in Appendix[D
As mentioned in introduction, our collaborative setting was motivated by the design of collaborative adaptive clinical trials for personalized drug recommendations, where several patient subpopulations (for instance, representing several subtypes of cancer) are considered and sequentially treated. However, practice, especially when dealing with patient data, disclosing the mean response values to the central server should be handled with care to preserve the anonymity of the patients. A possible solution to overcome this problem would to carefully combine our algorithm with data srivac-preserving method, for instance by adding some noise to the data [1
Our code and run traces are available in an open-source repository.
Acknowledgments and Disclosure of Funding
Clémence Réda supported by the French Ministry of Higher Education and Research SEE.XXIRDEE-SAALLYYSS The authors acknoweldge the support of the French National Research Agency under the project (ANR-19-CE23-0002--0 (BOLD).
10

---

References
[1] Akshay Agrawal, Robin Verschueren, Steven Diamond, and Stephen Boyd. A rewriting system for convex optimization problems. Journal of Control and Decision, 5(1):42-60) 60, 2018.
[2] Peter Auer and Ronald Ortner. Ucb revisited: Improved regret bounds for the stochastic multi-armed bandit problem. Periodica Mathematica Hungarica, 61(1-2):55-65, 2010.
[3] Etienne Boursier, Emilie Kaufmann, Abbas Mehrabian, and Vianney Perchet. A practical algo- rithm for multiplayer bandits when arm means vary among players. In The 23rd International Conference on Artificial Intelligence and Statistics, (AISTATS), 2020.
[4] Swapna Buccapatnam, Atilla Eryilmaz, and Ness B Shroff. Stochastic bandits with side observations networks. In The 2014 ACM international conference on Measurement and modeling of computer systems, pages 289-300, 2014.
[5] Lijie Chen, Jian Li, and Mingda Qiao. Nearly instance optimal sample complexity bounds for top-k arm selection. Artificial Intelligence and Statistics, pages 101-110. PMLR, 2017.
[6] Yu-Zhen Janice Chen, Stephen Pasteris, Mohammad Hajiesmaili, John Lui, Don Towsley, et al. Cooperative stochastic bandits with asynchronous agents and constrained feedback. Advances in Neural Information Processing Systems, 34, 2021.
[7] R. Combes, S. Magureanu, and A. Proutière. Minimal exploration in structured stochastic bandits. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
[8] Rémy Degenne, Han Shao, and Wouter Koolen. Strueture adaptive algorithms for stochastic bandits. In International Conference on Machine Learning, pages 2443-2242 2452. PMLR, 2020.
[9] Steven Diamond and Stephen Boyd. CVXPY: A Python-embeddded modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016.
[10] Yihan Du, Wei Chen, Yuko Yuroki, and Longbo Huang. Collaborative pure exploration in kernel bandit. arXiv preprint arXivv2110.15771 2021.
[11] Abhimanyu Dubey and Alex Sandy Pentland. Differentialll-prrin -private federated linear bandits. In Advances in Neural Information Processing Systems, volume 33, pages 6003-6014, 2020.
[12] E. Even-Dar, S. Mannor, and Y. Mansour. Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Leaminng Problems. Journal of Machine Learning Research, 7:1079-1100 110,, 2006.
[13] Tanner Fiez, Lalit Jain, Kevin Jamieson, and Lillian Ratliff. Sequential experimental design for transductive linear bandits. Advances in neural information processing systems, 32:10667- 10677, 2019.
[14] Victor Gabillon, Mohammad Ghavamzadeh, and Alessandro Lazaric. Best arm identification: A unified approach to fixed budget and fixed confidence. In NIPPS-TwentySSirff Annual Conference on Neural Information Processing Systems, 2012.
[15] Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pages 998-1027. PMLR, 2016.
[16] Aurélien Garivier, Pierre Ménard, and Gilles Stoltz. Explore first, exploit next: The true shape of regret in bandit problems. Mathematics of Operations Research, 2018.
[17] T.L. Graves and T.L. Lai. Asymptotically Efficient adaptive choice of control laws in controlled markov chains. SIAM Journal on Control and Optimization, 35(3):715-743, 1997.
[18] Eshcar Hillel, Zohar Karnin, Tomer Koren, Ronny Lempel, and Oren Somekh. Distributed exploration in multi-armed bandits. In Proceedings of the 26th International Conference on Neural Information Processing Systems- Volume page 354-662, 2013.
[19] Ruiquan Huang, Weiqiang Wu, Jing Yang, and Cong Shen. Federated linear contextual bandits. Advances in Neural Information Processing Systems, 34, 2021.

---

[20] K. Jamieson, M. Malloy, R. Nowak, and S. Bubeck. UiIUCBB an Optimal Exploration Algorithm for Multi-Armed Bandits. In Proceedings of the 27th Conference on Learning Theory, 2014.
[21] Nikolai Karpov, Qin Zhang, and Yuan Zhou. Collaborative top distribution identifications with limited interaction. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 160-171. IEEE, 2020.
[22] Emilie Kaufmann and Shivaram Kalyanakrishnan. Information complexity in bandit subset selection. In Conference on Learning Theorry pages 228-251. PMLR, 2013.
[23] Emilie Kaufmann and Wouter Koolen. Mixture martingales revisited with applications to sequential tests and confidence intervals. Journal of Machine Learning Research, 22((46):1-44, 2021.
[24] Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Edouard Leurent, and Michal Valko. Adaptive reward-free exploration. In Algorithmic Learning Theory, pages 865 891. PMLR, 2021.
[25] T.L. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4-2,, 1985.
[26] Aritra Mitra, Hamed Hassani, and George Pappas. Exploiting heterogeneity in robust federated best-arm identification. CoRR, abs/2109.057000 2021.
[27] MOSEK-ApS. MOSEK Optimizer API for Python 133. 2022.
[28] Clémence Réda, Andrea Tirinzoni, and Rémy Degenne. Dealing with misspecificatioo in fixed-confidence linear top-m identification. In Thirty-Fiftt Conference on Neural Information Processing Systems, 2021.
[29] Yoan Russac, Christina Katsimerou, Dennis Bohle, Olivier Cappé, Aurélien Garivier, and Wouter M Koolen. A/b/n testing with control in the presence of subpopulations. Advances in Neural Information Processing Systems, 34, 2021.
[30] Chengshuai Shi, Cong Shen, and Jing Yang. Federated multi-armed bandits with personalization. In International Conference on Artificial Intelligence and Statistics, pages 2917-2923 PMLR, 2021.
[31] Chengshuai Shi, Haifeng Xu, Wei Xiong, and Cong Shen. (almost) free incentivized exploration from decentralized learning agents. Advances in Neural Information Processing Systems, 34, 2021.
[32] 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 Computer Science (FOCS), pages 126-146. IEEE, 2019.
[33] Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. Nelson, Eric Jones, Robert Kern, Eric Larson, C Carey, ilhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, A. Quintero, Charles R. Harris, Anne M. Archibald, António H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SeiPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-277 2020.
[34] Qingyun Wu, Huazheng Wang, Quanquan Gu, and Hongning Wang. Contextual bandits in a collaborative environment. In Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval, pages 529-538, 2016.
[35] Jingxuan Zhu, Ethan Mulle, Christopher Salomon Smith, and Liu. Decentralized multi-armed bandit outperform classic upper confidence bound. CoRR, abs/211 1. 10933, 2021.
[36] Zhaowei Zhu, Jingxuan Zhu, Ji Liu, and Yang Liu. Federated bandit: A gossiping approach. In Abstract Proceedings of the 202/ ACM SIGMETTICS//memaainnnn Conference on Measurement and Modeling of Computer Systems, pages 3-4, 2021.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes].. general framework which encompasses several prior works is described in Section [ a lower bound on the sample complexity for a pure exploration problem is derived in Section whereas a lower bound regret on the regret minimization counterpart the problem shown Section 5 An algorithm for best arm identification, using a novel approach to achieve near-optimality, is described and analyzed Section
(b) Did you describe the limitations of your work? [Yes], we explained that the weight matrix had to be known in advance (Section []. although there is an application case where it can be computed. Moreover, we explained in conclusion to our work the issue faced when applying the same technique to regret minimization (Section 66.
(c) Did you discuss any potential negative societal impacts of your work? [Yes]. we remarked in our discussion (Section (6) that our collaborative algorithm might not be adapted to private, sensitive data, but might still be interesting for dealing with collaborative adaptive clinical trials between trusting teams.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] 2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] the assump- tions are mentioned both in the statement of the results (Section 3 Section Section and the proofs (Appendix).
(b) Did you include complete proofs of all theoretical results? included in Appendix.
[Yes] proofs in full are
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] the code and
run traces are available in a open-source repository. [
(b) Did you specify all the training details (e.g.. data splits. hyperparameters, how they chosen)? [Yes], this information reported in Appendix B
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]. tables Appendix reports the average values = their standard deviation.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]. this information is provided in Appendix Appendix([I(paaagraaaa (paragraph "Numerical considerations").
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you' rre're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "nSD4AjXXith", "reviewer": "Reviewer_MREF", "summary": "This paper introduces a collaborative learning multi-armed bandits formulation, which generalizes the previous stochastic federated bandit with personalization framework. The authors provide two new lower bounds on the sample complexity of pure exploration and on the regret. They also propose a near-optimal algorithm for pure exploration, achieving the lower bound up to logarithmic factors.", "questions": "No major questions.", "limitations": "The authors did a great job explaining the limitation in the theory side, and the work does not have negative societal impact.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The proposed model is more flexible in terms of how the rewards are mixed, compared with the previous work (Shi et al, 2021a).\n\n- Novel lower bound analyses are provided, which largely answer the open question proposed in Shi et al (2021a). The analysis technique is inspiring not only for federated bandits but also for similar cooperative multi-agent bandits models.\n\n- Inspired by the lower bound analysis, a new algorithm termed W-CPE-BAI is proposed. \n\n- For the best arm identification formulation, the proposed algorithm is shown to be capable of approaching the lower bound.\n\n- For the regret minimization formulation, a regret lower bound is proved, which largely complements the conjecture in Shi et al (2020a) and further sheds light on the corresponding algorithm design.\n\nWeaknesses:\n- Nothing major.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "HBNQ9NIh8L_", "reviewer": "Reviewer_cDN2", "summary": "Authors consider the model that there are $M$ agents and $K$ number of arms. At each round, each agent samples an arm (or is idle) and gets a reward. They assume that the agents share a known weight matrix and the objective function is to find the best arm which has a maximum expected mixed reward. The expected mixed reward of an arm for each agent is the summation of the weighted mean rewards of the arms. Therefore, the agents need to communicate with other agents to share information about their local rewards (collaborative learning). \n\nThey provide a lower regret bound in Theorem 1 for the best arm identification problem, in which the goal is to find a $\\delta$-correct strategy while achieving a small exploration cost and small communication cost. Then they propose an elimination-based algorithm achieving a near-optimal exploration cost bound. The algorithm computes the number of required samples for each arm and agent, using the oracle allocation from proxy mean reward gaps. Based on the rewards, it estimated the weighted mean reward and eliminate bad arms.  With updating gap estimators, it repeats this process. Lastly, they provide a lower regret bound of this problem.\n", "questions": "\n- In lemma 1, I was wondering the reason why the required samples are influenced by $w^2$ rather than $w$?\n\n- $log(1/\\Delta)$ is not familiar to me in performance bounds. Could you explain why this term is hard to remove? or whether this term is significant or not for the algorithm performance?\n\n- In practice, could we compute the oracle $P$ in definition 1 efficiently?\n\n", "limitations": "I believe that it would be better if the paper could provide more convincing motivation examples in which agent-dependent weighted arm rewards should be considered.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- They propose a novel problem in bandit research. In their problem, collaborative learning by sharing information with agents is necessary, which makes the problem non-trivial.\n- They provide a lower bound for exploration cost and propose an algorithm achieving near-optimal exploration cost while requiring a small communication cost. \n\n**Weaknesses**\n- Even though the problem is novel considering collaborative learning and the paper provides some motivation examples, I have a concern about whether there exist convincing applications in the real world. This is because the purpose to find a weighted maximum arm for each agent may not be convincing in a situation where each agent can learn its own best arm individually.  \n\n- For the required samples for each agent and arm in Lemma1, it would be better if the paper provides some detailed interpretation of the influence of weight value on the number of samples such as where $w^2$ comes from.\n\n- Also, it would be better to discuss how to compute oracle $P$ (definition1) efficiently to be used in the algorithm.\n\n- In the regret bound in Theorem 2, $log(1/\\Delta)$ could be large in the worst case, which makes the bound far from the lower bound.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "BFYbJFwjU3B", "reviewer": "Reviewer_Q8Vf", "summary": "The paper proposes a collaborative bandit model in which each player seeks to identify an arm that maximizes an arbitrary weighted sum of the rewards of the players. An algorithm is proposed that is shown to be nearly optimal. The model is a generalization of a recently proposed model, for which a bounded-regret algorithm was previously given, and the paper also establishes a regret lower bound for the generalized model.\n", "questions": "Can you give a setting that is faithfully captured by the proposed model that was not already captured by a previous model?\n\nCan you suggest a concrete family of problems beyond the ones considered in this work that might be addressed by the techniques developed here? (Note: I don't consider the top-N variant of the best arm problem in this model to be substantially more natural.)\n", "limitations": "It's fine. I'm sure that a personalized bandit algorithm could be misused to addict users to continue engaging with content platforms -- indeed, as I understand it, this is already being done. But I don't think the paper needs a \"don't be evil\" warning label or anything like that.\n", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main strength of the paper is the analysis of the algorithm. The algorithm is obtained by relaxing an optimization formulation that characterizes the optimal number of rounds to identify the best arm with high probability. A similar trick is used to obtain the regret bound.\n\nNominally, introducing the generalized model is also a contribution. But, the main weakness of the paper is that I really cannot think of a setting that actually has the key feature of this model: namely, that the player wishes to choose an arm that does not correspond to that player's actual observed reward distribution. What would make sense to me is if the players had reward distributions that were somehow known to be similar, so that perhaps by sharing estimates they might be able to more quickly estimate their own rewards. To me, this is a more appropriate analogue of \"personalization\" in which the parameters (estimates) of the collective can be used as a starting point to reach a more accurate set of parameters for an individual player. (More strongly, in most collaborative bandit formulations, the problem is set up so that the players all have the same reward distributions.) But in such a case, the players can still simply solve their independent bandit instances at a possibly greater cost. The central feature in this model (like the previous \"personalization\" work), by contrast, is that it has been designed so that the players must communicate, since the players need to identify an arm that isn't determined by their\nobserved rewards. While this indeed hadn't been considered previously, in this case I think the reason is in large part the lack of motivation to consider this setting. I certainly don't agree with the claims on lines 67-78 about potential applications; in each case, the success rate for an individual user or a therapy at an individual center corresponds to the reward distribution observed for that\nspecific user or at that specific site. I don't see any compelling reason to choose an arm just because it has higher rewards elsewhere.\n\nSo, in summary, the question to me is whether the technical novelty outweighs the lack of a compelling motivation for the model.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept