Adaptive Sample Sharing for Multi Agent Linear Bandits
Authors: Hamza Cherkaoui
Merwan Barlier
Igor Colin
Venue: ICML 2025 poster (2025)
Keywords: linear bandit
collaboration
sample sharing
Primary area: theory->online_learning_and_bandits
TL;DR: This paper addresses the agent collaboration in linear bandit problems via sample sharing, deriving an effective bias-variance trade-off for regret minimization.

Abstract: The multi-agent linear bandit setting is a well-known setting for which designing efficient collaboration between agents remains challenging. This paper studies the impact of data sharing among agents on regret minimization. Unlike most existing approaches, our contribution does not rely on any assumptions on the bandit parameters structure. Our main result formalizes the trade-off between the bias and uncertainty of the bandit parameter estimation for efficient collaboration. This result is the cornerstone of the Bandit Adaptive Sample Sharing (BASS) algorithm, whose efficiency over the current state-of-the-art is validated through both theoretical analysis and empirical evaluations on both synthetic and real-world datasets. Furthermore, we demonstrate that, when agents' parameters display a cluster structure, our algorithm accurately recovers them.

Adaptive Sample Sharing for Multi Agent Linear Bandits
Hamza Cherkaoui Merwan Barlier' Igor Colin
Abstract
accurate estimate of the parameter O" with respect to some metric. For example, in the context of regret mini- mization (Li et al., 2010; Chu et al., 2011), the goal is to obtain an estimate of 0 that is particularly accurate in the directions associated with large rewards.
The multi-agent linear bandit setting is well- known setting for which designing efficient col- laboration between agents remains challenging. This paper studies the impact of data sharing among agents on regret minimization. Unlike most existing approaches, our contribution does not rely on any assumptions on the bandit param- eters structure. Our main result formalizes the trade-off between the bias and uncertainty of the bandit parameter estimation for efficient collabo- ration. This result is the cornerstone of the Ban- dit Adaptive Sample Sharing (BASS) algorithm, whose efficiency over the current state-of-ther afrtthe-rrt is validated through both theoretical analysis and empirical evaluations on both synthetic and real- world datasets. Furthermore, we demonstrate that, when agents' parameters display cluster struc- ture, our algorithm accurately recovers them.
In the last decade, there has been an increasing focus on the multi-agent setting (Cesa-Bianchi Bianchi al., 2013; Gentile et al., 2014; Nguyen & Lauw, 2014; Ban & He, 2021; Ghosh et al., 2022; Do et al., 2023; Yang et al., 2024), where multiple agents share samples to make better decisions together. For example. consider the problem of optimizing the parameters of wireless antennas in a network to improve the quality of service for nearby users. Antennas that belong to similar environments and constraints should yield similar rewards and are likely to benefit from sharing their observations, at least in the early stages of the optimization process. In- deed, if the rewards are derived from similar parameter 0", sharing observations effectively reduces the noise variance, making the estimator more accurate. Similar arguments can be made for recommendation systems or drug trials (Sarwar et al., 2002; Su & Khoshgoftaar, 2009; Li et al., 2010; Chu et al., 20, where similar profiles should lead similar observations.
1. Introduction
The stochastic multi-armed bandit (MAB) framework pro- vides efficient tools for solving sequential optimization prob- lems (Lai & Robbins, 1985; Abbasi-Yadkori et al., 1; Dani et al., 2008; Soare, 2015). In this setting, an agent repeatedly pulls an arm from a finite set of candidates and observes the associated noisy reward, sampled from an un- known fixed distribution.
This problem, known in the literature as Heterogeneous Multi-Agent Linear Stochastic Bandits, has been mostly approached using Euclidean similarity to define clusters of agents (Gentile et al., 2014; Nguyen & Lauw, 2014), within which sample sharing is allowed.
This paper develops
new approach to determine, without assumption a clustered structure, when agents should share samples, focusing on the bias introduced by hetero- geneous agents, the resulting reduction in uncertainty, and the trade-offs between these factors. Based on our simi- larity metric on the Mahalanobis distance induced by the observations focus on directions with large reward and avoiding using the overly conservative Fuclidean distance, we introduce the Bandit Adaptive Sample Sharing (BASS) algorithm. This method outperforms the state-of-thh-ant by pairing similarity learning with regret minimization.
A common extension of the MAB problem is the linear bandit setting (Lattimore & Szepesvári, 2020), where each arm is associated with a vector æ E Rdd and its expected reward is a linear combination the vector and an unknown bandit parameter 0* e IRd. The linear bandits framework is a generalization of MAB that takes into account the similar- ities between the arms to identify better pulling strategies. Efficiently solving this problem often consists in obtaining
'Huawei Noah's 's Ark Lab, France 'LTCI. Télécom Paris, Insti- tut Polytcchnique Paris, France. Correspondence to: Hamza Cherkaoui <hamza.chere cherkaoui @ huawei.com>.
We organize our paper as follows: detail how this problem was addressed the literature and summarize our contributions, Section 3 provides the intu- ition on how our approach challenges it. Then in Section 4,
first, in Section 2, we
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

Adaptive Sample Sharing for Multi Agent Linear Bandits
formalize the linear bandit setting for the single agent case. Section 5 explores sample sharing in multi-agent context and introduces our sharing criterion. In Section 6, we present and detail our algorithm, followed by a theoret- ical analysis. Finally, we empirically evaluate our method in Section 7.
proving the clustering process with the Euclidean similarity introduced by Gentile et al. (2014), this paper takes advan- tage of the Mahalanobis distance, as regret minimization problems require focusing primarily on the directions with the highest rewards. Furthermore, unlike most existing ap- proaches that rely on the assumption of an agent clustered structure, our contribution does not impose such constraint.
2. Related Work
Multivariate approaches In an opposite research direc- tion, the approach in Nguyen & Lauw (2014) takes advan- tage of the k-means (MacQueen (1967)) algorithm to cluster the agents. Alternatively, instead of making the hypothesis of clusters, other approaches propose enforce some regu- larization on the bandit parameter estimation to introduce structure between agents. The Non-negative Matrix Factor- ization (NMF) technique in Song et al. (2018) allows them to recover a probability distribution on the cluster labels for each agent. Finally, a low-rank decomposition of the stacked bandit parameter matrix in Yang et al. (2020) yields the desired cluster structure of the problem, by combining the decomposition with sparsity constraint.
Cluster structure known in advance Some work has assumed that the parameter structure is known in advance. Cesa-Bianchi et al. (2013) modifies the problem variables to consider all agents simultaneously, allowing them to mimic a classical single-agent scenario while proposing an efficient multi-agent algorithm. In Wu et al. (2016), the problem is modeled to compute each reward of neighbors parameters, leading to a collaborative setting. More recently, Moradipari et al. (2022) defined setting in which agents aim to maximize the average reward of the network, forcing agents to share their observations during a communication phase.
linear combination
In real-world scenarios, however, the parameter structure is often unknown, natural goal is to recover it before enabling collaboration.
However, the multivariate aspect of these approaches makes them less suitable for a distributed framework, which is often required in real-world applications (e.g., recommen- dation systems, wireless antenna network).
Estimating the cluster structure as graph The sem- inal work of Gentile et al. (2014) introduces novel collab- orative framework: agents are grouped into clusters, and agents within the same cluster have the Euclidean distance between their bandit parameters smaller than a given thresh- old. With this assumption, the authors derive a similarity measure based on this distance and use the corresponding graph recover clusters. Since then, variants have been pro- posed to improve the accuracy of the parameter estimates, e.g., by averaging over connected components rather than neighborhoods (Li & Zhang, 2018), or by improving the robustness of the estimates by offsetting the OLS (Wang et al., 2023). Other work has focused on improving the quality of the clustering itself: Ban & He (2021) allows overlapping clusters, Li et al. (2019); Xiangyu et al. (2024) each proposes splitting and merging procedure to correct for potential clustering errors, and Ghosh et al. (2022) aims to control the minimum cluster size. Although still based on a Huclidean similarity measure, Cheng et al. (2023) opts for a different clustering routine to take advantage of hedonic game theory. Do et al. (2023) and Yang et al. (2024) trigger collaboration rounds, controlled by collaboration budget, when the design matrices deviate too much from each other. Finally, Li et al. (2016); Gentile et al. (2017) base their similarity on the rewards themselves, rather than the param- eters, alleviating some of the dimensionality issues of the Euclidean similarity.
2.1. Our contributions
We propose a novel algorithm that addresses several previ- ous limitations and introduces key features that distinguish it from previous work.
1. No Assumption on Bandit Parameters: Our approach does not rely on any assumptions on the bandit param- eter structure to enable collaboration, and learns to balance the trade-off between the collaborative bias and the uncertainty reduction.
2. Anisotropic Approach: In regret minimization, we fo- cus on directions with large reward; our approach there- fore focuses on the same directions to quantify the bias with adequate precision.
3. Theoretical and Empirical Analysis: We formally de- fine the problem, conduct an exhaustive analysis of collaborative stopping time, and cumulative and in- stantaneous regret. In addition, we present a fair and comprehensive empirical evaluation of our algorithm using both synthetic and real-world data.
3. Preliminaries
3.1. Notation
We use lowercase (e.g., a)) to denote a scalar, bold (e.g., x) to denote a vector, and uppercase bold (e.g., A) is reserved
While most contributions have relied or focused on im-
2

---

Adaptive Sample Sharing for Multi Agent Linear Bandits
for a matrix. The 2z-norm of vector æe is || = Vx æ and the Mahalanobis weighted (2-seminorm is || V x Ax, where A is semidefinite positive. The ellip- soid of center E IRd, shape A > 0 and radius is denoted
where 3, =O(Vlog()) will be detailed later. Similarly,
1
10 0,1| S 10 02 + 3
V2
A A, r), that is
Therefore, the collaborative estimate d,, improves the reg- ular OLS estimator when
E(c, A, = {ac E RR, || cllA sr}
|00 - l.. S (2 22)
(1)
An exhaustive notation summary can be found in the sup- plementary material Appendix B.
Equation (1) suggests that collaboration reduces the error as long the bias introduced |0 - 0 A, is less than fraction of the uncertainty of the estimation 3
3.2. A simple two agent problem
To build intuition about sample sharing in the regret min- imization problem, we first examine the simpler case of parameter estimation with two agents.
With this simple case, we argue that, given sampling ap- proach of the arms (æ:))==1> we need to adapt when the col- laboration should occur to accelerate the estimation process. The key point is to detect when the condition of Equation (1) stops being verified to end the collaboration and to avoid introducing detrimental bias.
Consider two agents, each one with the aim of estimating its linear parameter 0 E Rd E {1,2). To do this, each agent i has series of actions (3t,1..... ;...,,,,,;,,)))) (...)) associated with series of /. noisy rewards (Vi.1, .... Vi.t) such that for 1 S s S t:
Vi.s 0 Di.s Th.
Figure I. Estimation of 07 de- picted with (resp. 0: with 01 with (resp. Oe.e with A). along with the correspond- ing confidence ellipsoid in blue (resp. in orange). The collabora- tive estimate has reduced uncer- tainty ellipsoid |0o,, 0. ||
for some 1 uub-Gaussian' noise nk... The unbiased Ordinary Least Squares (OLS) estimator is then:
0,,
Σ La
Σ Di = 0 A
where Ai, Et 20 Z Σ.= Ti and for any M E Rdxd M is the Moore-Penrose inverse. For simplicity, we assume that both agents hold the same series of actions, so AI,: A2,- A..
The later intuitive result can be easily illustrated. In Figure 1, display 0 and 9 along with their confidence ellipsoid in blue and their collaborative counterparts in orange. We notice the well-known estimation bias variance trade-off.
If the two agents shared their observations, the OLS of the merged dataset would be
4. Single agent regret minimization
Pc.- = 0: + A (21.1 A +2, 22,1)
In the linear bandit setting, at each time step an agent chooses an arm S; from set X (xx) E RRd and receives reward signal y x; 0- 17. where 0* is the (unknown) bandit parameter and v is some centered noise. For the remainder of the paper, we assume that the arms and the bandit parameters are bounded as depicted in Assump- tion 4.1
where 0- = (0 05).. If both parameters are equal, then the merged OLS improves each independent OLS, since it is unbiased and the noise only V2 Lub-Gaussian, However, if the parameters are different, the merged OLS is biased, and the question becomes whether the noise reduction out- weighs the bias.
Assumption 4.1 (Bounded Norms). We assume there exists a constant I such that the true parameter satisfies | < L, and all context vectors satisfy ||>x||| < 1 for all < k K.
Since the overall goal is to consider the regret minimization problem, we measure the accuracy of an estimator by its Mahalanobis distance w.r.t. the design matrix A., Indeed, the larger the reward, the more accurate the estimate needs to be. Using the analysis of Abhasi-Yadkori et al. (2011), we have, with high probability,
F. be the o-algebra generated by (y1...., St-1. $1..... æ;), then æ; is F-measurable and Vt-1 is F--maasurable. Moreover, we make the common Assumption 4.2 that the noise is conditionally Dsub-Gauussann for some constant R > 0.
Let
||0., l,,, < 3t
'see Assumption 4.2 for a formal definition -ausasssiintty.
3

---

Adaptive Sample Sharing for Multi Agent Linear Bandits
Assumption 4.2 noise term li is conditionally R-sub-Gaussion for some con- stant R > 0. That is. for all X E I.
of the Noise). The
5.1. Collaborative setting
We consider a multi-agent setting where each agent [1....,N} is able to pull arms from linear bandit of unknown parameters 0 E R.. Every linear bandit uses the same set of arms X'. We assume that the historical data are known to a central controller. At each time step 4, the controller selects the arm to be pulled by the agents and observes the noisy rewards.
R² 2
E8 (exp(An)
| Fr-1] S exp
The goal is to minimize the cumulative pseudo-regret, formally defined in Audibert et al. (2009) Rr (xx - a.)) and x² arg max; O"T.A. æx- For this purpose, the OFUL algo- rithm (Abbasi-Yadie) Yadkori et al., 2011) implements the prin- ciple of optimism in the face of uncertainty in the linear bandit case. At each time step i, the learner pulls the arm that maximizes the expected reward associated with the best parameter in a confidence region around the Ordinary Least Squares (OLS) estimator. Formally, time t + 1, given previous OLS estimator 0, and a Ca (o)), the selected arm maximizes the optimist reward
Ex with Te
We are interested in comparing two pulling strategies: local strategy, where each agent can only use its own ob- servations to derive a pulling policy, and collaborative strategy, where agents are allowed to regroup their observa- tions in order to derive more general policies. Throughout the paper, we denote by (t) the set of agents sharing their data with agent at time I, we index a quantity by if is computed using only local observations of agent i, and by Nt(t) if it is computed using observations from the set of all agents that share their data with i at time t. In both cases, we focus on an OFUL approach, so the two strategies can be summarized as follows.
TO
I++1 E arg max max ØEA (EC)(O,))
where (0.) is such that IP E Cs().)) 2 1 5. In practice the confidence ellipsoid C3, is constructed from the previous pulls using Hoeffding's 's concentration inequal- ity (Tropp et al., 2015), which leads to the theorem Theo- rem 4.1 from Abbasi-Yadkori et al. (2011):
Local strategy: use OFUL with local observations, com- pute the local OLS 0, and the confidence region Cs (O.):
Collaborative strategy: use OFUL with the observations of the collaborating agents, compute the associated OLS i (c)) and the confidence region Cs (x.)))
Theorem 4.1 (Confidence Ellipsoid for Bandit Parameter Estimation). Let d E (0,
O, and 0 Rd. Let (a.)i denote the sequence of arms pulled up to time t. Under Assumption 4.1 and Assumption 4.2, the following holds with probability at least - 6:
5.2. Separation test
We now analyze the impact of sample sharing on the regret and formally introduce the test to detect when beneficial sharing stops. The arm selection strategy is based on OFUL and depends whether not the observations are shared to define the OLS estimator and the confidence ellipsoid. Unlike the analysis in Subsection 3.2, we focus on regret minimization rather than parameter estimation. To this end, we recall the following bounds on OFUL. instantaneous regret for both independent and data-sharing settings.
p P(8 CCo())) 21 1
where
S $ Co((.) = (110- -0'1 A.
A() = R 2log
1 de)(Ai)
Lemma 5.1 (Instantaneous Regret Upper Bounds), Let 0 8 < 1 and t >> O. Let (0j)ssjsN E RaxN be the true parameters of N lineur bandit models. Denote by Fi,t (resp. x (x((t) ) the arm selected by agent using the local (resp. collaborative) strategy. Then, with probability at least 1 - 8, the instantaneous regret of agent is bounded as follows:
Vv det(AA)
and A, = -.==1 x, is the empirical design matrix.
For the remainder of the paper, we assume that X spans IRd. Also, we set Ao = I, so:
(i) Local strategy:
B(6, A.) = Ry 2log log 5 + log dee((e)))
ri(l) 23 (5, A.,)) ||sssell
5. A Adptiiee sample sharing
(ii) Collaborative strategy:
In this section, we consider the collaborative setting and examine the impact of sharing samples on regret minimiza- tion.
re(t) < 23(66 m m.A))
1 1 + m
Σ Au,
Vm

---

Adaptive Sample Sharing for Multi Agent Linear Bandits
where (1) and A | -Oill
Figure Estimation 0 de- picted with (resp. 0j with +). d., with (resp. Oj., with A). along with the correspond- ing confidence ellipsoid in blue (resp. in orange). With high probability, the bias, depicted with a red dashed line becomes detrimental when the ellipsoids are separated.
Following the analysis of Subsection 3.2 and substituting the unknown parameters in their OLS estimates, we com- pare the right-hand side of the inequalities, For E (t),,, we outline the same condition than Equation (1), see Ap- pendix G:
00, - - S (2- (2)3(6,)
(3)
We almost recover the overlapping ellipsoid test derived in Gilitschenski & Hanebeck (2012) and based on the fol- lowing function:
agents follow two different bandit parameters, as illustrated in Figure
x) = 1 min 10, -031 9 A,,,)
It should be noted that collaboration criteria based on the Euclidean distance (e.g., Gentile al. (2014); Ban & He equivalent to the Gilitschen- ski & Hanebeck (2012) test where the ellipsoids considered are E(O; Amin A, 3) and E(),, Amin (A 8), ignor- ing most of the arm pulling history.
(4) The ellipsoid separation property is obtained from the sign of j),, that is E(O, B,) n E(0,, Age, Bj) 0 if and only if j) - 0.
=EJo.1
(2021); Wang et al. (2023))
Since we consider a synchronous pulling, we have A A,,t A,, and B. = 3 = (6, At). Indeed, in this setting, all collaborating agents select an arm based on the same shared history. Choosing deterministic arm policy yields that two agents using the same history will select the same arm. Therefore, their design matrices will also be identical. The separation condition can be reformulated as stated in the following corollary.
In practice, computing (4) is expensive, instead we consider cheaper, equivalent test function", defined as follows.
Definition 5.1 (7yrelaxed ellipsoid separation test function). For any iteration and any two agents i and j. we denote as (i, j, the quantity
Tt 3nd (8) <0
(1,,,,t) = min sE/0..]
Since we consider a synchronous setting, we have A A₁.t A, and 3, B, = (68, At). this case, all collab- orating agents operate on the same shared history. Because the arm selection policy (e.g., UCB) is deterministic, agents with identical histories will always select the same arms. As a result, their design matrices evolve identically over time.
with
(.) 72 ---e
s(1 (1-s) s)
Pl.
Pe, 8 (17, 32,
1m1
where Y > and μ = t T (T.O. - 0z.)) such as n and T are the eigenvalues and the eigenvectors of the generalized eigenvalue problem:
Under this assumption, the separation condition can be re- formulated as stated the following corollary.
Lemma 5.2 (Ellipsoid Separation Under Synchronous < 1, and consider two agents and j. Under Assumption 4.1 and Assumption 4.2, define 3 (1 + 1/,2),366, At). Then the following statements
A = (diag((() with $ Ay, =1
Pulling). Let
The parameter in v is related to the ellipsoid radius and therefore depends on the level of confidence ò required for the separation.
equivalent:
(i) 00 10-80/11 8,ll,, 2 (2 (2) A.)
5.3. Separation time
(i) E(0, A0 A,, n) A, /)
Two agents i and may have a beneficial collaboration as long (i t) 1. Therefore, we consider collaboration sets of the form Nr, = {i (i.j, = 1}. and define the separation time between two agents as follows. Note that with algorithm, once two agents are separated, they no longer share samples.
This shed a new light on the preliminary work in Subsec- tion 3.2 and Subsection 5.2. The collaborative condition in Equation (1) matches the separation condition for ellipsoids E(O,, A,, 3) and E(,,. A., (). Interestingly, denoting as 5 the value for which 3 = 3(5, At), the bias is detrimental when we know with probability at least 1 5 that both
We proof the ellipsoid separation property of T in the supple- mentary material Appendix I
5

---

Adaptive Sample Sharing for Multi Agent Linear Bandits
Definition 5.2 (Separation Time). For two agents and j. the separation time 5 is defined as
Algorithm 1 Bandit Adaptive Sample Sharing (BASS) algo-
rithm
To (i = min {t E N ((.j,,)) -
Input:
The UCB parameter a, the exploration parameter ca and the confidence level 8.
The following result gives a lower bound on the separation time based on the parameter gap.
Initialization:
For i = =,...., N set b,.0 0d. A4,0 la
Theorem 5.1 (Lower Bound on the Separation Time T3 Be- tween Two Agents). Let 0 < 8 < 1. Consider two agents and j. and suppose that Assumption 4. and Assumption 4.2
and the complete graph Go = (V, Eo);
1: for =ort=1,.... Lo.t do
2: for i E V do
hold. Then, with probability at least - 6, the separation
3: Determine the neighbors No.e- of agent i;
time satisfies:
4: Update its current neighbor weights, set:
AN A + Ey (Ajee- - A5,0).
(erl (1 6) -o)( 21
(i) 2
b Ejer. bj,c-1.
110 0j112 2l
0 @Niyt
- Nir.e- biii
where c.) denotes the Gauss error function.
Select Kg E arg max OT
FK 3AAL N
(10k)
k=I...KK Ni
6. The Bandit Adaptive Sample Sharing algorithm
with AA-1 (a)) = a K Pull ky and observe payoff ye: Update weights, set:
x A No
x log(t)
6:
7:
6.1. Description of the algorithm
A A 2k, /b
Following Definition 5.1, we define similarity graph G. Ec). where V NN} and E, fi.j ((),j,t) = 1}. initialized as a complete graph. Therefore, agents and j share their observations if and only if (i.j) E E,. The Bandit Adaptive Sample Sharing (BASS) Algorithm goes as follows.
b,, b,,t-1 + ye ; end for
8:
9: Update graph G. = (N, Et):
Remove all (i.j) such as (i. = 0
10:
end for
At each iteration I, for each agent E V2, the shared esti- mator (H) is updated and an arm is pulled according to OFUL policy with an exploration parameter The agent then uses the observed rewards to update its local estimate 0, Once every active agent has pulled an arm and updated its local estimate, the similarity graph G. is updated accord- ing to Definition 5.1. The complete procedure is detailed in Algorithm 1.
the algorithm BASS where the OFUL. sampling replaced with a uniform sampling with probability ee, ensure ex- ploration in all directions. Empirically, we did not notice any difference with the above version.
Theorem 6. (Upper Bound on the Separation Time TT). Let < 1, and consider two agents i and j. Let e. >> 0 satisfy
The overall complexity of the BASS algorithm is O (T(N- + Kd + (N + 1)d")). We report the computa- tional details and the associated complexity in the supple- mentary material Appendix Q
(1 (1+ 22)RR with Q
1 K
Σ (a (0 07))²
K
Q
Then, under Assumption 4.1, Assumption 4.2, and following Figure 1, we have, with probability at least 1 - 8,
Moreover, let C(T) denote the total communication cost up to time T. In the worst-case scenario- all N agents share identical bandit parameters and communicate their observations at each round we have C(T) & (N -IT.
4(2 + /2) log 2e.Qi.. -
We focus on the particular case of collaboration between two agents, as it can be casily generalized to N agents by considering all pairs. We focus on the eumulative regret separation time, as the problem transitions to the well-known single agent setting afterward: Rgoolab Rgollab (,o,T.(i..)) Ei=T,6.)) Tie
Cumulative pseudo-regret upper bound
6.2. Theoretical analysis
Separation time upper-bound To facilitate this theo- retical analysis, we consider slightly modified version of
See the experiments in Section 7 for the case of single agent pulling an arm at each iteration.
with Rcollab T.1..) rit
6

---

Adaptive Sample Sharing for Multi Agent Linear Bandits
Theorem 6.2 (Individual Regret During the Collaboration
Assumption 6.1 (Clustering Structure). We assume
Phase). Let Ts j) denote the separation time in- troduced in Definition 5.2. Under Assumption 4.1 and As- sumption 4.2, the cumulative regret of agent i during the collaboration phase is bounded as:
that there exist M & N distinct bandit parameters 10 ........ O35s C R such that, for all agents i [1....,NY, NY, the true parameter satisfies:
0 E E:0i..... 0h1)
Reollab S ((),d,7) ((.,d.T)) Ts (0: - -0)) a
Under the assumption of clustered parameters, the collabora- tion may always be beneficial. We also introduce additional notation: for given agent i, we define its true neighbor- hood (i.e., the set of agents within its cluster) as M₁. We also introduce the cardinalities N, Pmm(j) N [Mi] and No. WW.ee Finally, we denote by NN,, the gap between both cardinalities, that is, N₁, | - N.,ll. The follow- ing result upper bounds the number of misassigned agents.
where
(( = 7
d log 2
1
4
2v2
2 1og 1
and
T d
((,,dTT)) - V 43(6, AT,ddlg 1
Lemma 6.1 (Expected Number of Misassigned Agents). Let 0 < ô < Under Assumption 4.1, Assumption 4.2, and Assumption I, we have, with probability at least ō:
With v66, Ta) we recognize the upper bound in the case
of single agent derived in Abbasi- Yadkori et al. 12011), thus (u66, d, 7) represents the collaborative gain and 4 (0 0 xt the result of the induced bias. Setting 7 < 2
E [[)(()) S (t)
where
v2 1 (d log (2 log }). we have u(ō, d, 7) < 1.
N /ddet(Ar))
m((1)= =
Pmnc)
Network cumulative pseudo-regret upper bound
exp
1 (Amin
min
-7/(0, A1))
Looking at the cumulative regret of all agents, we can further refine our upper bound. Let us set Roollab O.T.
and
E I the averaged cumulative pseudo-regret.
A min min 00; -0]1lA, 1
A.
Theorem 6.3 (Regret During the Collaboration Phase). Let T. = J) denote the separation time introduced in Definition 5.2. Under Assumption 4.1 and Assumption 4.2, the cumulative regret of all agents during the collaboration phase is bounded as:
With this clustering error bound, we can derive an upper bound on the cumulative pseudo-regret denoted R2 We provide additional theoretical results in the supplemen- tary material Appendix P.
To (0;- 4
Theorem 6.4 (Cumulative Pseudo Regurt with Clustered Agents). Under Assumption 4. I, Assumption 4.2, and As- sumption 6.1, after T iterations of the BASS algorishm, the cumulative pseudo-regret of agent i satisfies:
Roollab S
-0;)
(a) -xa)
where
1
d dlog
1
22
logg?
peluster S (o", v + 8pmin N C,(TT) R
4L
and v(6,d,T.) d.))) is as previously defined.
where:
Similarly to Theorem 6.2 we recognize the upper bound in the case of single agent, thus (d, represents the collaborative gain and T (0) 07) (aī - -wz) bias-related quantity.
min(T,T2)
C,(Te) Σ nf(()
dlog N
16 d, N) =
1 +
Regret analysis with clustered parameters Most ex- isting algorithms rely on the assumption that the linear ban- dit parameters are clustered around a few centroids. We thus extend our analysis to this specific assumption, which formalized as:
Vamin N
2 log
I
8
Tg = max T3 (1, Pmin 3
min Pm((j) j
and v(5, d, T) is as previously defined.
7

---

Adaptive Sample Sharing for Multi Agent Linear Bandits
Discussion To better interpret this result, we derive lower bound the cumulative pseudo-regret in the ideal- ized case where all agents share the same bandit parameter and form a single, known cluster, we obtain:
Cumul. regret
202 = 0.2
A0.2 1.27
Ind
6100.7 +/- 468.4
5465.0 +/- 352.7
Oracle
318.5 +/- 684.0
292.9 +/- 914.3
DynUCB
$765.5 +/- 10439.5
15081.6 +/- 15299.7
CLUB (1 Amia /4)
5772.5 532.4
5822.7 +/- 430.6
d( N
CLUB (7
402 (2)
5739.4 +/- 521.5
6138.1 +/- 659.8
R,O
SCLUB (7 402/4 /4)
6038.5 +/- 744.8
5949.3 +/- 501.0
SCLUB (7 A5
6165,6 +/- 366.0
5775.3 416.8
4L This bound emphasizes the additional cost term 8pmin NV (TT)) in Theorem 6.4, which accounts for the effort re- quired to correctly identify agent clusters.
BASS (6 0.1)
1096.8 +/- 411.9
1617.5 +/- 689.8
BASS (6 0.9)
1140.5 +/- 641.4
1563.2 +/- 750.7
CMLB (7 = 882 /4)
5895.3 382.5
$372. +/- 7575.0
CMLB (7 = -A (2)
5918. +/- 431.3
20948.5 +/- 5355.5
Additionally, we summarize in Table 1 the upper bounds available for the concurrent algorithms considered under the structure assumption of the clustered agents. We provide the derivation steps for this table and include an additional oracle case in the supplementary materials Appendix P.
Table 2. Comparison of the averaged cumulative regret last value Pr for the different synthetic environments.
same size with bandit parameter (0m (m......) defined
as: VI S q S M canonical basis and 02, having its q-th entry being cosw, its (q+ 1)-th entry being sin w and all the other entries being 0, with { /6, 7 (16. The angle induces a problem complexity A min, denoted D in Figure 4, of 0.2 in the first scenario and 1.27 in the second.
2 102--1 = Eq. with (e;); being the
Cumululative
Expected number of misassigned agents
pseudo regret
DynUCB
not available
not available
CLUB
((dy N VT log(T))
not available
SCLUB
dd N VT log(T))
not available
CMLB
va
VT log(T)3
not available
We consider K = 5 x M arms of dimension d = 10. The algorithms are set to iterate for T = 50000. We set the number of agents to N = 100 and corrupt the reward obser- vation with a centered and normalized Gaussian noise. As baselines, we choose Ind, which proposes to run the agents independently and Oracle which knows the true group struc- ture and shares observations within the same cluster. We also compare our performance to state-of-the-art algorithms: DynUCB, CLUB, SCLUB, CMLB. For each algorithm, we consider two sets of hyper-parameters for which the result is shown in the 'dashed' and 'solid' lines. For each method, we line-search the a parameter. We set our hyperparameter y to 2 to match Gilitschenski & Hanebeck (2012). The experiment is run 50 times to average across runs. We detail the experimental setting and a description of the concurrent algorithms in Appendix R.
V
BASS
VT (T)))/
Vimin
Table 1. Summary of available upper- upper-bounds for clustered agents.
Our analysis of the cumulative pseudo-regret with clustered agents establishes the tightest upper bounds, incorporating a vd/ V pun constant term and T/d term within the logarithm. Furthermore, to our knowledge, this is the first work to provide an analysis of the clustering error of the algorithm.
7. Experiment
All upper bounds include an gain term compared to the sin- gle agent case and a loss term from the introduced bias. In this section, we demonstrate that the combination of these two terms results in overall improved regret minimization on both synthetic and real data experiments. The experi- ments were run in Python on 50 'Intel Xeon @ 3.20 GIlz' CPUs and lasted a week. The code is publicly available and can be found at this repository.
We report an additional case with M = 6 and an additional synthetic benchmark with Gaussian arms and bandit param- eters in Appendix S.
In Table 2 (resp. Figure 3), we report the cumulative regret last value Rr (resp. R₂) for all concurrent and baseline methods. First, we note the expected behavior of the base- lines: Oracle provides the best performance for all scenarios, and the Ind algorithm provides intermediate performance, as the agent does not share its observations, but avoids introduc- ing detrimental estimation bias. We find that our approach, BASS, significantly outperforms all the other algorithms. In particular, we notice that our approach always results in a gain in comparison to Ind, as underlined by Section 6. Moreover, in Figure 4 we show the cumulative regret last value, Rr, of the evolution w.r.t. the UCB parameter a. We
Benchmark on synthetic data To match the asyn- chronous pulling commonly used in the literature, we con- sider that only one agent, randomly chosen by the environ- ment, pulls an arm at each iteration. Similarly, to match the common assumption of the clustering structure, we con- sider Assumption 6.1 for the experiments. We propose to benchmark the algorithm on two variations of a syn- thetic environment. We consider M = 3 clusters of the
8

---

Adaptive Sample Sharing for Multi Agent Linear Bandits
angle = 1 π /
Clustering score
Am 0.2
A02 1.27
(i.e. D - 0.20)
Ind
0,0 +/ 0.0
0.0 +/- 0.0
5000
Oracle
1.0 +/- 0.0
1,0 +/- 0.0
R.
DynUCB
0.7 +/- 0.1
0,9 +/- 0.2
CLUB (1 4g2 /4)
0.0 0.0
0.0 0.0
20000
40000
CLUB (7
252/2 (2)
0.0 +00+/0000 0.0
0.0 0.0
SCLUB ( Ag2 /4)
0.0 0.0+//0.0
0,0 +/-+00..0
SCLUB (> 4/2 /2)
0.0 0/0
0.0 0/0+//-0 0.0
angle 7 π 7/16
BASS (6 0.1)
0.7 0.0
0,9 +/- 0.0
(i.e. D 1.27)
BASS (6 0.9)
0.7++/00 0.0
0.8+/-00 +.0
5000
CMLB (7 Ag.2 /4)
+/- 0.0
0.0 0.2
Re
CMLB (7- = 48. /2)
0.0 +/- 0.0
0.6 +/- 0.1
20000
40000
Table 3. Comparison of the averaged Fl score of the estimated graph Gr for the different synthetic environments.
Figure 3. Comparison of the averaged evolution of the cumulative regret last value Re for the different synthetic environments con- sidered.
Cumul. regret
Movie Lens
Yahoo
Ind
11825.2 +/- 594.1
14800.5 +/- 876.0
DynUCB (M 5)
16835.0 +/- 5429.9
14689.5 +/ 1912.7
angle 1 7/16
angle 7 m/16 (ic. D - 1.27)
DynUCB (M 20)
17256.0 2314.2
16860.5 +/- 1625.3
(ic: D 0.20)
Grade
CLUB 0.1)
11504.2 +/- 509.3
13321.5 +/- 4228.8
DvrUCB
8002
5000
CLUB b
CLUB (? 1.0)
11804.8 +/- 562.4
13536.5 6548.2
SCLUB (+ 0.1)
11425.2 +/- 764.0
13663.0 1444.0
(000
6000
CLUB
SCLUB (7 = 1.0)
11085.5 +/- 701.3
13751.5 +/- 820.
<
SCLUB (+
BASS (6 0.11
10273.2 +/- 686.3
12456.0 2096.1
4000
4000+
SCLUB (-
BASS (5 = 0.9)
10840.2 +/- 831.7
12533.5 +/- 1959.5
2003
2000
8455
BASS (5- 0.9)
CMLB (7 0.1)
14944.2 #/- 341.6
16812.5 +/- 405.1
CMLB (7 = 1.0)
12010.8 +/- 669.4
16757.5 +/- 607.2
CMLB
10
10
1//
Table 4. Comparison of the averaged cumulative regret last value Hr for the two datasets.
Figure 4. Comparison of the averaged evolution of the cumulative regret last value Rr w.r.t. the UCB parameter a for the different synthetic environments considered.
In Table 4, we show the final cumulative regret Ry for the considered datasets. We observe that our approach again outperforms all the others in both scenarios. The overall performance comparison between the algorithms remains consistent with the synthetic experiment and confirms the good behavior of our algorithm; additional results are re- ported in Appendix S.
can see that our approach systematically provides a lower regret than the state-of-the-art algorithms, underscoring the robustness of BASS.
In Table 3, we show the final clustering score value for all clustering algorithms. To quantify the degree of agree- ment between the estimated clusters/neighborhoodss and the ground truth, compute the Fi-score the graph Ge w.r.t. the true cluster graph G. Details of the score computation are reported in Appendix R. We observe that our approach al- ways achieves the best performances. Moreover, most of the concurrent methods recover the clustering structure poorly. Since Nguyen & Lauw (2014); Gentile al. (2014); Li et al. (2019); Ghosh et al. (2022) do not provide any experiment to verify this aspect, these results are not surprising.
8. Conclusion
This paper explores collaboration sample sharing pro- cess, highlighting the benefits of introducing bias, pro- vided that it remains smaller than the current uncertainty. We derive a collaboration condition and propose an algo- rithm that takes advantage of sample sharing. Our approach has been extensively analyzed both theoretically and empiri- cally, highlighting the key quantities involved in the process and demonstrating strong empirical performance on both synthetic and real-world datasets.
Benchmark on real data study of our method, we propose a second benchmark with real datasets. We consider two public datasets of ranking scenarios: MovieLens and Yahoo! dataset. Since Orucle is not available for real data, we consider all other previ- ous algorithms except it, keeping the same experimental setting. Details of the experimental setting are reported in Appendix R.
To complete the performance
To our knowledge, this is the first work to have comprehen- sively analyzed the introduction of bias in this context or established an efficient condition and collaboration scheme with anisotropic testing. In line with these research direc- tions, designing an arm-pulling strategy aimed at efficiently estimating the similarities could be promising avenue.
9

---

Adaptive Sample Sharing for Multi Agent Linear Bandits
Acknowledgements
Dani, V., Hayes, T. P., and Kakade, S. M. Stochastic linear optimization under bandit feedback. In Proceedings of the Annual Conference on Learning Theory, pp. 355-366, Helsinki, 2008. Omnipress.
The authors would like to thank Pierre Ablin and levgen Redko for their insightful comments and valuable sugges- tions, which helped improve the quality and clarity of this work. We also thank anonymous reviewers for their con- structive feedback during the review process.
Do, A., Nguyen-Tang, T., and Arora, R. Multi-agent learn- ing with heterogeneous linear contextual bandits. In Pro- ceedings of the International Conference on Neural Infor- mation Processing Systems, volume 36, pp. 15836-15848. Curran Associates, Inc., 2023.
Impact Statement
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Gentile, C., Li, S., and Zappella, G. Online clustering of bandits. In Proceedings of the International Conference on International Conference on Machine Learning, vol- ume 32, pp. 757-765, Beijing, China, 2014. JMLR.org.
References
Gentile, C., Li, S., Kar, P., Karatzoglou, A., Zappella, G., and Etrue, E. On context-dependent clustering of ban- dits. In Proceedings of the International Conference on Machine Learning, volume 70, pp. 1253-1262, Sydney, Australia, 2017. PMLR.
Abbasi-Yadiae Yadkori, Y., Pál. D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. In Proceedings of the International Conference on Neural Information Processing Systems, volume 24, Granada, Spain, 2011. Curran Associates, Inc.
Ghosh, A., Sankararaman, A., and Ramchandran, K. Multi- agent heterogeneous stochastic linear bandits. Joint Euro- pean Conference on Machine Learning and Knowledge Discovery in Databases, pp. 300-316, 2022.
Audibert, J.-Y. Munos, R., and Szepesvári, C. Exploration- exploitation tradeoff using variance estimates in multi- armed bandits. Theoretical Computer Science, 410(19): 1876-1902, 2009.
Gilitschenski, I. and Hanebeck, U. D. robust computa- tional test for overlap of two arbitrary-dimensional ellip- soids in fault-detection of kalman filters. In International Conference on Information Fusion, pp. 396-401, Singa- pore, 2012. Curran Associates, Inc.
Ban, Y. and He, J. Local clustering in contextual multi- armed bandits. In Proceedings of the Web Conference 2021, pp. 2335-2346, New York, NY, USA. 2021. Asso- ciation for Computing Machinery.
Harper, F. M. and Konstan, J. A. The movielens datasets: History and context. ACM Trans. Interact. Intell. Syst., 5: 1-19, 2015.
Basa-Bianchi,ao N., Gentile, C., and Zappella, G. A gang of bandits. In Proceedings of the International Conference on Neural Information P Processing Systems, volume 26, pp. 737-745, Red Hook, NY. USA, 2013. Curran Asso- ciates Inc.
Lai, T. and Robbins, H. Asymptotically efficient adaptive allocation rules. Adv Appl. Math., 6:4-22, 1985.
Lattimore, T. and Szepesvári, C. Bandit algorithms. Cam- bridge University Press, 2020.
Chapelle, O. and Chang, Y. Yahoo! learning to rank chal- lenge overview. In Proceedings of the 2010 International Conference on Yahoo! Learning to Rank Challenge, vol- ume 14, pp. 1-24, Haifa, Israel, 2010. JMLR.org.
Li, L., Chu, W., Langford, J., and Schapire, R. E. A contextual-bandit approach to personalized news article recommendation.
Proceedings of the International Conference on World Wide Web, pp. 661-670, New York, NY, USA, 2010. Association for Computing Machinery.
Cheng, X., Pan, C., and Maghsudi, S. Parallel online clus- tering of bandits via hedonic game. In Proceedings of the 40th International Conference on Machine Learning, vol- ume 202 of Proceedings of Machine Learning Research, pp. 5485-5503. PMLR, 2023.
Li, S. and Zhang, Online clustering of contextual cas- cading bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 3554 3561. AAAI Press, 2018.
Chu, W., Li, I.,, Reyzin, I.., and Schapire, R. E. Contextual bandits with linear payoff functions. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), volume 15, pp. -, Fort Lauderdale, FL. USA, 2011. 1. JMLR.org.
Li, S., Karatzoglou, A., and Gentile, C. Collaborative fil- tering bandits. In Proceedings of the International ACM SIGIR Conference on Research and Development in Infor- mation Retrieval, pp. 558, New York, NY, USA, 2016. Association for Computing Machinery.
10

---

Adaptive Sample Sharing for Multi Agent Linear Bandits
Li, S., Chen, W., Li, S., and Leung, K.-S. Improved al- gorithm online clustering of bandits. In Proceedings of the International Joint Conference Artificial Intel- ligence, pp. 2923 2929, Macao, China, 2019. AAAI Press.
Wu, Q.. Wang, H., Gu, Q., and Wang. H. Contextual ban- dits in collaborative environment. In Proceedings of the International ACM SIGIR Conference Research and Development in Information Retrieval, pp. 52-538, New York, NY, USA, 2016. Association for Computing Machinery.
MacQueen, J. Classification and analysis of multivariate observations. In Proceedings of the Berkeley Symp. Math. Statist. Probability, pp. 281-297, Berkeley, USA, 1967. University of California Press.
Xiangyu, X., Qifeng, Z., Qing, W., and Langcai, C. Swob: An efficient switch-clustering of bandit model. In Pro- ceedings of the Chinese Control and Decision Conference, volume 36, pp. -. IEEE, 2024.
Moradipari, A., Ghavamzadeh, M., and Alizadeh, M. Col- laborative multi-agent stochastic linear bandits. Pro- ceedings of the 2022 American Control Conference (ACC). PP. 2761-2766. IEEE, 2022. doi: 10.23919/ ACC53348. ACC55334.2002..86777 2022.96622222
Yang, H.,, Liu, X., Wang, Z., Xie, H.,, Lui, J. C. S.,, Lian, D., and Chen, E. Federated contextual cascading bandits with asynchronous communication and heterogeneous users. Proceedings of the AAAI Conference on Artificial In- telligence, volume 38 of AAAI '24 Technical Tracks, pp. 20596-20660 Association for the Advancement of Arti- ficial Intelligence, 2024.
Nguyen, T. T. and Lauw, H. W. Dynamic clustering of con- textual multi-armed bandits. In Proceedings of the ACM International Conference on Conference on Information and Knowledge Management, pp. 1959-1962, New York, NY, USA, 2014. Association for Computing Machinery.
Yang, L., Liu, B., Lin, L., Xia, F., Chen, K., and Yang, Q. Exploring clustering of bandits for online recommen- dation system. In Proceedings of the ACM Conference on Recommender Systems, pp. 120-129, New York, NY, USA, 2020. Association for Computing Machinery.
Rendle, S. and Schmidt-Thieme, L. Online-updating regu- larized kernel matrix factorization models for large-scale recommender systems. In Proceedings of the 2008 ACM Conference on Recommender Systems, pp. 251-228, New York, NY, USA, 2008. Association for Computing Machinery.
Sarwar, B. M., Karypis, G., Konstan, J., and Riedl, J. Incre- mental svd-based algorithms for highly scaleable recom- mender systems. In Pruceedings of the Fifth International Conference on Computer and Information Technology. pp. 345-354, 2002.
Soare, M. Sequential resource allocation in linear stochas- tic bandits. PhD thesis, Université Lille 1-Sciences et Technologies, 2015.
Song, I.., Kwon, J. K., and Li, S. Overlapping clustering of contextual bandits with nmf techniques. Undergraduate report, Georgia Institute of Technology, Atlanta, GA, 2018.
Su, X. and Khoshgoftaar, T. M. A survey of collaborative filtering techniques. Adv. in Artif. Intell., 2009, 2009.
Tropp, J. A. et al. An introduction to matrix concentra- tion inequalities. Foundations and Trends@ in Machine Learning, 8(122):1223,, 2015.
Wang, Z., Xie, J., Liu, X., Li, S., and Lui, J. C. S. Online clustering of bandits with misspecified user models. In Proceedings of the International Conference on Neural Information Processing Systems. volume 36, pp. 3785- 3818. Curran Associates, Inc., 2023.

---

Adaptive Sample Sharing for Multi Agent Linear Bandits
A. Appendix: table of contents
Appendix: Notations summary
13
Appendix: simple two agents problem: Details on Subsection 3.2
14
C Appendix: Technical lemmas
15
D Appendix: Bandit parameter estimation error bounding: Details on Theorem 4.1
17
Appendix: Instantaneous regret upper bounds: Proof of Lemma 5.1
17
Appendix: Collaboration condition: Details Equation (3)
.88
G Appendix: Ellipsoid separation under synchronous pulling: Proof of Lemma 5.2
19
Appendix: Ellipsoid separation test function: Details on Definition 5.1
.9
Appendix:
Lower bound on the separation time: Proof of Theorem 5.1
20
J Appendix: Upper bound the separation time: Proof of Theorem 6.1
21
K Appendix: Cumulative pseudo-regret upper bound: Proof of Theorem 6.2
22
Appendix: Network cumulative pseudo-regret upper bound: Proof of Theorem 6.3
23
M Appendix: Expected number of misassigned agents: Proof of Lemma 6.1
.55
N Appendix: Cumulative pscudo regret with clustered agents: Proof of Theorem 6.4
26
Appendix: Additional theoretical analysis:
27
Appendix: Implementation details
Appendix:
Experimental details
29
R Appendix:
Additional details
.30
12

---

Adaptive Sample Sharing for Multi Agent Linear Bandits
B. Appendix: Notations summary
Variables and parameters
Details
deN
Dimension
KEN
Number of arms
NEN
Number of agents
MEN
True number of clusters
ANEN
Number of agents within the neighborhood agent
TEN
Total number of iterations
Separation iteration of agent i and j
T. max, T,(i.))
Iteration at which the cluster is adequately estimated
X= {AK E K 2 E Rd with
|0|| S
Arm set
0, C Rd
True bandit parameter of agent
LE R'+
Bound of the bandit parameter norm i.e., Vi 0 la
1) R
Reward observation noise
RET RR'+
Sub-Gaussianity parameter of the noise
M1 x 11
Reward signal at iteration t
Fr
o-algebra generated by (æ), (Z1.V1...... By 1. 1.
1. max; 9-1 Dg 0" D4 R*
Instantaneous regret
A, Ex=1 Di 1.
Radd
Design matrix at iteration of agent i
A AN... A,, + EjENT. (A A,,) E ddd
Design matrix at itcration of neighborhood
b Ei=1 +i Rd
Regressand for the estimation of the bandit parameter of
the agent i at iteration /
b, EESeR 63.0-1 E Rd
Regressand for the estimation of the bandit parameter of the neighborhood at iteration t
0 ON =A-
Ni bi E Rd
Bandit parameter estimation from neighborhood i
0. FRd
Bandit parameter estimation from agent
6
Confidence level parameter
Cs(O.)
Confidence region of the estimated bandil parameter
B(8,t) = R log 1 + log (et(AA) E R*+
Confidence level of set of the previous region
Ni(t) = 1i (i 1}
Neighborhood of agent
NE(()
Number of agents wrongly assigned to neighborhood i at
iteration t
A 00 07 L R²+
Bandit parameters Euclidean distance
Amin
min
0 0j11 R
Isotrope complexity of the problem
1, 12)
M 10; 0j E R
Bandit parameters Mahalanobis distance weighted by ma- trix M R
AM = min
10
Ml E R
Anisotrope complexity of the problem weighted by matrix M d
E. ((i,5) (i.j)) = 0)
Edges modelling the interaction between the agents
V [1...N}
Set of all agents
G. = Kb)
Estimated agent graph at iteration t
I V
Agent pulling set at iteration t
case I = {i)
Asynchronous pulling (with draw randomly from V)
case I V
Synchronous pulling
13

---

Adaptive Sample Sharing for Multi Agent Linear Bandits
C. Appendix: A simple two agents problem
C.1. Preliminary theoretical results
We detail here the bounding of estimation error of 0f. From the series of noisy projections (y1,e) with Vi,, 0 F1,s + T1 with (== X" a fixed series of arms. We consider the observation matrix to be invertible; the proof remains similar to the case involving the Moore-Penrose inverse. We can cancel the gradient of the OLS estimator to obtain:
0, 0f
A
11,
with
A.
Σ
1
s=1
00.
0i
4,
A-
00. 09
$ 3(,, At)
as defined in Theorem 4.1
A.
Similarly, for the collahoration case we have:
@collab
1
(0) + 0%)
A,7"
Σ 11 + 12,5))
2
1
@collab
07
07)
A,7
01,0
12,5)
2
A As) as defined in Theorem 4.1
@collab
07
1
100
0
A.
+
B(8,
A,
V2"
Using the two previous error bounds, we compute the ratio of the bounding terms and compare it gain insight into the collaboration condition, leading to:
1 ||0
0::
+
/3 3(5, Ac)
$
Ai)
110 021l A. (2 - (2--2)8(66A)
C.2. Empirical illustration
To generate Figure I, we consider a simple case with d and set of two arms X' (2),, where e and e2 are the canonical basis vectors. We set Oi = e₁ and define 0; 0 + p, where p represents significant perturbation. The noise modeled normalized Gaussian noise. We set 10, allowing us gather 10 noisy projections for each bandit estimation problem, denoted by (1 and (2 with V1,s
0 x M1, (resp. V2. 0; x. + 22,,). The design matrix is shared between both problems, i.e., A, = A,, A2, Σ1 10 2. T. each iteration, the arm ag is chosen random uniformly.
C.3. The Bandit Adaptive Sample Sharing algorithm
We include simplified flow chart clarify and summarize the main steps of our algorithm.
14

---

Adaptive Sample Sharing for Multi Agent Linear Bandits
fort=
Receive agent i
Identify agent neighbors
Compute shared variables
Select arm using OFUL policy
Observe payoff and update local variables
Update agent neighbors
Figure 5. Overview the Bandit Adaptive Sample Sharing (BASS) Algorithm
In Figure 5, we summarize the main steps of the BASS algorithm, illustrating the process from selecting an arm using the OFUL policy, to identifying the agent's neighborhood, updating shared and local variables, and updating the agent graph.
D. Appendix: Technical lemmas
We gather here technical lemmas used later in the remaining proofs.
Lemma D.1 (Error vector of the difference of two estimated bandit parameters). At iteration t, considering the agent i, and their corresponding bandit parameter estimation 0. 0s.,. with 0 * 0j. we have:
- 0 -0 A, Zz.at with Z Tss Bj.s
Proof of Lemma D.1. At iteration f, considering the agent i and their corresponding bandit parameter estimation oz,, with 0g its true bandit parameter, we have:
i..
0 +
A
aa
with Ai
Di
The last equation being obtained by cancelling the gradient associated with the OLS. Similarly, we consider a second agent and their difference, we have:
0.. 0.. 0
-0;
+++A A Σ Tis a + Aji Σ
00
0 A,
Ci Mj since synchronous pulling, have A. Aj, A.
0 8 + A,
Zzga with Zr Σ
15

---

Adaptive Sample Sharing for Multi Agent Linear Bandits
Definition D.1 (Optimistic true bandit parameter). Let 0 R a E R2 and A Raxd a positive semi-definite matrix, define by the optimistic true bandit parameter, the vector 0 defined as:
i = arg max T such as ||0 S
BERA
Lemma D.2 (Characterization of the optimistic true bandit parameter), Let 3 > 0, O R A Rdxd a positive semi-definite matrix and E R the corresponding optimistic true bandit parameter is:
B
i 0
A-to
A
|
Proof of Lemma D.2. Let consider 3 > 0, 0 R Rd, A E R dxd positive semi-definite matrix, the corresponding E Rd and the following optimization problem:
θ arg max 0Tx such as |0 01 S 6 PER
We derive the corresponding Lagrandian: L(,, p)) = OT u equivalent to:
0
B²) and cancelling the associated gradient
A0 1 x + A0
2n
B = 1|0 0
1 = 2p A x +0
| 412
B
0 0+
A-1a
x A-1
Lemma D.3 (Positivity of the clustering error). For each agent i, at probability have:
Vt
have: Ño. - Pm()) N 2 0
Proof of Lemma D.3. By using proof by contradiction, iteration Nu, I P. This implies there exists an agent such (i, 1 and 0 0. Let us develop (i. t) 1, probability 1 - 5, we have:
let us consider an agent and suppose that
10, 0,ll,, 2 23(6, A.) 110 - -0 || A- 2 23(6, A.)
(2,(68, A,) 2 23(6,
Hence, for each agent i, at iteration > 0, with probability 8: No. Z P
Lemma D.4 (3 ratio upper- Ler O. N N.N. and A, the design matrix obtained after iterations for given agent, we have:
B(),NAt) <
dlog N
B(ō, A.)
2 2og
16

---

Adaptive Sample Sharing for Multi Agent Linear Bandits
Proof of Lemma D.4. Let us consider 8 O, N.N., and A, the design matrix of a given agent, have:
B(,, A..)
2 2 + log det(NV At)
B(6, As)
2 log 8 + log (At)
2 log + doo N + log (A,)
2 log ; + log (A.)
d log N
since det(A:) 2 det( (ee((A)1)) and Ao I
2 2log
E. Appendix: Bandit parameter estimation error bounding
Theorem 4.1 (Confidence Ellipsoid for Bandit Parameter Estimation). Let 5 E (0, 13,1),.00 0, and 0 E TRd. Let (xx)) denote the sequence of arms pulled up to time t. Under Assumption 4.1 and Assumption 4.2, the following holds with probability at least 6:
P p( Co(0.) 2 1
where
{100- 0-
Co,
$ $866, Ar)
A.
(2)
1 (Ar)
8(6, A.) R.
2 2
σv det(An)
and A, Esmi 2,,0 the empirical design matrix.
Proof Theorem 4.1. The proof can be founded in the supplementary material of Abbasi- Yadkori al. (2011).
F. Appendix: Instantaneous regret upper bounds
Lemma 5.1 (Instantaneous Regret Upper Bounds), Let < 8 < and Let (0j)ssJSN RaxN be the true parameters of N linear bandit models. Denote by æi,t (resp. 2 ((())) the arm selected by agent using the local (resp. collaborative) strategy. Then, with probability at least the instantaneous regret of agent i bounded as follows:
Local strategy:
rt()) s 23 23 A,,) ||
(ii) Collaborative strategy:
re(1) S 23(6, 23(6, mAi))
2 Σ
| AT
+
A' SEN.(1)
Vm
m
where m = (Wt(t) and A = =|00; - | A..'
A..
Proof of Lemma 5.1. For the single case, at round f, for a given agent by considering the optimistic arm æ, and the optimal arm n,, we have:
17

---

Adaptive Sample Sharing for Multi Agent Linear Bandits
Ti, 0 T (a) Fi,1)
0 T Tait
0 1 T since (0i,,, vi.))
are the optimistic tuple
3(6, A.)
00.- +
A, A - 0
The from Lemma D.2
|
3(6.A))
00.. 07 A.
|,a,,ella;" A.
| A,"
x A,'
$ 23, A.)l(oa,lll,
Moreover, for the collaborative case, at round t, for given agent i, by considering the optimistic arm V.(0)) and the optimal arm 27, have:
Ti, 07 (o) 2 (((1))
00 M100
0 Ne(1 + 0,) (2) RR(())
0 Ri010 of O Ri100 NN100) (0, R(00) ) (x0; (.N1(1)
<00,00 T N.(0) - -10000 RM(0) (0;- - (2()0 (xt )x(e))
since (0 2x(o)) are the optimistic tuple
s (0,211)) - Ma T T + (0) (2 (xt - )M(
(5)
We now consider the corresponding norms, we have:
$ (0 (1) (22))) Z50000 + 100 -0 (R Ex A.'
(0 (1(1) -M2()) " ( =211% 0illa, from Assumption 4.1
3(6, A ARai)
< 0 (1) +
A
Ni(t) Ni(1)) - (2200 2)01 + +2110 2700) - ll from Lemma D.2
| AR
B(6, Ar(o))
-IT
x NNi(11) + (0xice) - -0 0220)) DNN1 +21 R.(1)) - 0, ll
| 29(19)
< (6, A ki(a) ) (1) AA 7i000
+ +10 Ni(1) +100x(11)
02 (lx, |1 |
+ -2110 (1 07 1l.
< (3(6, A Mn(e) + 110 x7(1) x(x0) - -0 11 )
11
|| ||0, A3,00
+ +2110 M1
0, A
< 23(6 A A111)) 2,.00 +2110 Ni(1))
- -7 by definition of 3 A Ar,a))
N
S VN
366, (6,,NA:) 1 |A-1 1
Σ
1107 0, ||
/=1
G. Appendix: Collaboration condition
We proof Equation (3). With Assumption 4.1, we can bound the term | A. in Lemma 5.1, leading to:
Ti, S 2,865 A.)
(6)
18

---

Adaptive Sample Sharing for Multi Agent Linear Bandits
Similarly, for the collaborating case of two agents, we have:
FiA S v23(0,2A,) + |10 1,
7
Equation (6) and Equation (7) leads us to:
1 ((6, 2A,
10 li
22 3(6, A.)
2,(6, A,)
|07 l,
2(a)
2,(6, A.)
V2 3(5,A)
107 0,11a,
2 V2
23(5, At)
|0] 07 f. S (2 V2) A.)
H. Appendix: Ellipsoid separation under synchronous pulling
Lemma 5.2 (Ellipsoid Separation Under Synchronous Pulling), Let 0 8 < 1, and consider two agents and Under
Assumption 4. and Assumption 4.2, define 3 (1 (1 A.). Then the following statements are equivalent:
(i) 00 8.1A, 2 (2 ())
(ii) E(O,, A., B) n 8 (0,, A,, 3) =
Proof Lemma 5.2. The proof can be founded in the supplementary material of Gilitschenski & Hanebeck (2012).
Appendix: Ellipsoid separation test function
We prove the ellipsoid separation property of the Y function.
Property 11 (kellipsoid separation property of the y function.). Let 0 <, 8 < 1, for two agents i and j. and following As- sumption 4.1 and Assumption 4.2, the following statements are equivalent:
V iijt (i.j.t) = + E(O,, A., 3) nE Ar, 3) = 0
Proof of Property L.I. Let us consider two agents i and j. with their associated unknown bandit parameter estimates O and θ,, the observation matrices A; and A, along with their local confidence level briefly noted 3r and By as in (4.1), If we consider that & and diag(1)), the eigenvectors and the eigenvalues of the generalized eigenvalue problem, we have:
A A, (diag()))) with + A =1
First, with the given scaling of this problem being, one can recover the following equivalent constraints:
Φ A diag(n) (n)
c T A
Which gives us:
A + d
A t +
Secondly, we consider the function Vs E]0,
(iy(s) = 3/2 -Et 1u B7+0(37n
s(1-s)
and μ TT(0, 0,) from Def-
inition 5.1, we have the following:
19

---

Adaptive Sample Sharing for Multi Agent Linear Bandits
7-
d
s(1 -18 8)
(2)(8)= =
1
4
B + 8B3311 - BQ))
1=1
1
8(1 -8)
/ T diag(
87 $.33m m (82)) )
4
1-
8
83
/ diag(
1 11) 1
4
12
82
8
11 T
+
diag(1)
4
1
B $
8
(0, - 0,)
+
@diag(n)) (1)
(0, - 0,)
4
-
B A7 +
18
-1
(0,
0,)T
A
(0: (0)
from Equation
2
110:
0
4
For 2, we recover the function x. as defined in Equation (4), from Gilitschenski & Hanebeck (2012), and conclude the property.
J. Appendix: Lower bound on the separation time
With our algorithm, once agents separated at iteration & (t,j)) (i.e., ((i,j, =1), they longer share samples. Hence the separation is definitive. We proof the lower bound on the separation time based on the parameter gap. Theorem 5.1 (Lower Bound on the Separation Time T, Between Two Agents). Let 0 < 8 < Consider two agents and j. and suppose that Assumption 4.1 and Assumption 4.2 hold. Then, with probability at least 1 - 6, the separation time satisfies:
8 (erf (1 - 8) - erf()))² 27
Ts(i.))
10: - -0
where e-) denotes the Gauss error function.
Proof of Theorem 5.1. To derive a lower bound, we examine simplified case where the separation time occurs earlier than in any typical scenario.
We consider two agents and j, iteration Ti(j,) < assume the nature of the noise is known and modeled as
normalized Gaussian noise. We suppose that the set of arm is reduce to single arm, i.e., X = { 0: 03 most favorable case to distinguish the two bandit parameters.
which the
|o 0
First, we bound 0. llll in our specific setting:
|00 0l = || (0. 0
1 Ar(O. 01)112
since
A
A₁ vtxx" T Vi
Vt
n with
7o 1()
20

---

Adaptive Sample Sharing for Multi Agent Linear Bandits
We have P
1 E. no 2 a = 1 - erf( (2). So with probability 1 - 8, we have:
110. Ai s ((0) with B(6) /2eer -
Secondly, we bound 0 A.lllA, in our setting similarly to the previous approach, we have:
| 0gellar = ||| | - -0 -
1
Σ mm, -m8.e) 2
Vt ==1
with
Zuza NVVEl0 2)112.2) 2)
Lastly we consider our collaboration criterion with t = 5). we have:
||0., 0j.ell,, 2 23(6)
[Z 2 23(6)
Moreover setting P 5| 2 28(6)] 1 and since P [|Zz,,ee| 23(6)] 2(1 - P Pizg, S 23()))). we have:
1
1 =0
+
erf
2/2 (23(0) - v - -0]122
2 2
1
223(8) Vel10, 071l2)
1- = erf
2/2
2erl (6)) 23) vil10 071
So, iteration = (i,
4(8(8) (116)-v2aam /2erf (8))
with probability 1 - 6, we have ||0., 0g.11a. 23(6), which leads to:
100 -
8(erf (1 - 8) - ())
||0 0j
Although focus simple case, demonstrate that the separation time scales inversely with |10; 0J]l2 which characterize how difficult the problem is.
K. Appendix: Upper bound on the separation time
Theorem 6.1 (Upper Bound on the Separation Time T.). Let < 8 < 1, and consider two agents and j. Let e, > 0 satisfy
(1+ R2 with Qi,
( (0) -0;))
E
Qii
K
Then, under Assumption 4.1, Assumption 4.2, and following Figure 1, we have, with probability at least 1 ò,
4(2 + V2)2 log
T.(i.))
2G.Qr.j (2 2
Proof of Theorem 6.1. Given two agents and j, iteration
S (t, from Gilitschenski & Hanebeck (2012), under
21

---

Adaptive Sample Sharing for Multi Agent Linear Bandits
synchronous pulling, we have:
||0,, A, S 25( At)
10: -ljlA, - |Z s 233(6, As) from Lemma D.1
||0 07112, $ (2 (6,
K
( _ (0) - 0;))² s (2 32) A,)² with Tee the number of pulling of arm a% at iteration &
We have The = Tiiif + ( e with Tuuif the number of pulling of arm ay iteration following the Uniform policy" and TUCB the number of pulling of arm 2y at iteration &. following the UCB policy as depicted in Figure 1, we have with large enough:
ee
kt
The Tuiif +11 11--6, -e)
EO K
Thus, we have:
aa (0: 03)) < (2+ 32)3 (2++2)3300 A.)²
K
1 + log det(Ae))
2log g ( (0, - 07))² (2+ 12
6
K
K
1
d
1+ ))
( (0) - 03)}² s (2+ R2
2log
+
log
K
5
2
k=
1
t
c.
(a% (0; 03)) (2+ 128A88
22lg
g
2
K
(2 + 12 (0) - 0;))
(ark
S 22 42 R² log
K
2
Finally, we conclude that:
4(2 22 R log 3
Te(i,))
2c.Qi.j (2 + V2)2 R2
with an Signal to Noise Ratio (SNR) such as:
QQu R
(2+v2) and Qi, = K Ek vi.
(2) (0; - 0)))
L. Appendix: Cumulative pseudo-regret upper bound
Theorem 6.2 (Individual Regret During the Collaboration Phase). Let T. (i.jj) denote the separation time introduced in Definition 5.2. Under Assumption 4.1 I and Assumption 4.2, the cumulative regret of agent during the collaboration phase
is bounded as:
To
R & ((5,,,7) u d, T.)
+
(0:
07)
x
2
where
1 ((,,,>)= - 7 1
4 2
d log 2
1 +
2/2
log
*hii highlight the particular utility the e- uniform sampling, as the typical UCB lower bounds are asymptotically.
22

---

Adaptive Sample Sharing for Multi Agent Linear Bandits
and
To 1+
((,d, 43(6, Ar, Ard)
d
Proof of Theorem 6.2. We consider the case of two agents i and j. focusing the instantaneous regret Tit given that t S. 5) we have M(()) = {i}, from Equation (5), we have:
(02,(1) -0 (10)))
0: + +0 O27(0) (x.(0) + (0, - -0 022))'
T
B(6, A
A 1-1
+ +0 +xx1(0) -0;
x Nx1( + -0;]
N.(1)
2 (, + 02) +,)
1 (0, - 0.) NN(()))
2 - -07) -0;]=a; "x
1
S (6, A
0
2
(66,
(210: 0,l|A, +10, 0,11a,
| A + 1
(0; 03) mt
V2
1 ((6,2A.)
2 060 A.) + +16 A.) ||
2 10; 07)* xa
V2
22
1 ((6,2At) 2
-
2
1
8(6, A,] +
1 (0 07) Ta a
2/2 316, A1)
2)
2
1 + 2
1 (())
1 22(0 0;) Tx; a;
2
((0, ||A +
2
2/2 B(6, A.)
1 2
1
llog
1 20; 07) TT)x²²
2
1
B(6, A1)
+
x
from Lemma D.4
2
2v2
2og
$ 2p(66 d, ()8 A.)
(
(0: Tx; with d(),
7 +
1
d dlog' 2
4
2/2
2 log 1
3
With Abbasi-Yadkori et al. (2011) and by setting T.) /48(5, Ar,) )T, log(1 12), have:
T. (0) -07 x
R,O,T. S <1(6,d,))u(6 Ts)
Note that in order to enforce p15, d, 7) < 1, we need set < -2 + (d] f). For example, for d 10 and 5 = 0.001, we have is 7 < 0.27.
Moreover, recall that in Gilitschenski & Hanebeck (2012), the authors consider 7 = to derive their ellipsoid separation test. Here, the term v 1 + (d (olg +) could be interpreted as a correction that accounts for the regret minimization objective. Note that this term is derived from the loose upper-bound of (65, (6,,2AA)//(0 ((5, At), which is close to 1 and relatively insensitive to both the number of agents and the problem's 's dimensionality.
M. Appendix: Network cumulative pseudo-regret upper bound
Theorem 6.3 (Regret During the Collaboration Phase). Let T, = (i. denote the separation time introduced in Definition 5.2. Under Assumption 4. I and Assumption 4.2, the cumulative regret of all agents during the collaboration phase
23

---

Adaptive Sample Sharing for Multi Agent Linear Bandits
is bounded as:
R,T, S ('(, d(),d
T. (0 - -0))
T (x)
az)
where
d log? 2
((
1 1+
v2 /
2 log 8
and (6,,,TT, T2) is as previously defined.
Proof of Theorem 6.3. We consider the case of two agents i and j. focusing the averaged instantaneous regret FiA (Fi, + Ty,)). given that t 2 5i we have Mi()) = {i} and (t) = {i}. which give us:
(Tit + +gaa)
1
(0 T (a; 2x((1)) +0, 00; (x}
x x)))
2
R (1)) + 2 x; + 2 07 xj
0iT
2
= Mann (1)00)) - -xN1)) Ni t ki(1)) + 2 0; x; +
1 1
+ 10 aj
Moreover, since 0 x²
0
(2 + #z)), we have:
N111 Nc(1)
Nitt)
1 [(m + mn)
1
Fit S (i(1) N.(1)) -x "x(())
(1)
0-T
+ 2 0r a. + 00 m3
(i(1)
=2"0
1
1
1
3 Man (x (.(1)) -x(()) +
0,
x; - 00 a3 2
07 x
03
xj - 07
xt + 07 x3
2
2
1
Ni R.0 xx(
+ (0 07) [a; - xj))
23(6, A (1
11
A
+ - 10 Tx; - xjj)
N((1)
4
1
21.
|A
1 0 (x:
T(x - =3²)
2
1
3(8,2A,)
| AA,1 + 1 10; 07) T (xx - xx})
V2 3(6, Ar)
1
d dlog 2
2
8(5, A 4.- + 1 (0 89)T [(x; - =z²)
V2
log
< (8, d)3(6, A.) A." + + (xx (x)) with n'(8,)) v2
d dog
+
2 log
With Abbasi- Yaakori et al. (2011) and by setting T.) / //8(5 (T, 2T, log(1 4) we have:
T, (0: ()){((3) x;))
{1((6, T,) + 4
O,T,
Note that for reasonable values of d and 6, we have: (( d) < p(6 7, which gives us the intuition that the network of agents an improvement over the single agent case.
24

---

Adaptive Sample Sharing for Multi Agent Linear Bandits
The same intuition applies for the second term _ (0: -P7-00) 0)) - ærj). Since the bandit parameters and the norms bounded, the only configuration for which this inner product is high, is when least arm is approximately in the direction of 0 1-07 j. With this conditioning, the separation of the two bandit parameters is accelerated and the collaboration ceases shortly after.
In summary, taking into account the averaged cumulative pseudo regret better underlines the adaptive aspect of our collaboration.
N. Appendix: Expected number of misassigned agents
We detail the proof of the upper-bound on the clustering error in Lemma 6.1 Lemma 6.1 (Expected Number of Misassigned Agents). Let 0 < < 1. Under Assumption 4.1, Assumption 4.2, and Assumption 6.1, we have, with probability at least 1 6:
E [NE(O) S mn(().
where
N det((A)
nt(()=
Pm(
A -3(6, A.))
exp
and
A min A.
min 110 - -03 07
{+)
Proof of Lemma 6.1. We have, iteration estimated cluster, we have:
Ni,, IN.. - Pm with Ni. the number of agents within the
E
N
= E
[Na, Pince N
E
No. Pm(s)-N)
from Lemma D.3
N
E
Σ 1 [((()_))=0) P
N
P (i.ji, 0] P
==
Focusing on (i. = 0). we have:
P P(v(i...)) = 0]
||0, - 0, s 233(6, A.)
< [Za.jollA 2 23(6, At) - -100 - 07 |A.
By introducing and by using the Chernoff bound, we have:
P P( = 0] < exp(-u) with v 2u + log del A, = =110; - -0i1AA - -23(6, A.)
1 2 (110; - 0jlla, -23(6, A.))² + 2
log det A,)
S exp
det(Ai)
(()(i.,))) 0 5|
exp((A min
-7/3(6, A.))2)
Which yield us the desired result:
[(
Ny dde((AA)
E [ (0)
exT( 3 mim .A. -798(6, -7.8(6,A.)))
25

---

Adaptive Sample Sharing for Multi Agent Linear Bandits
where Amia min 10 0jllA, A, and Pm(()) N the number of agents in the cluster m(i), the agent's cluster. w
inj
O. Appendix: Cumulative pseudo regret with clustered agents
Theorem 6.4 (Cumulative Pseudo-Regret with Clustered Agents). Under Assumption 4. Assumption 4.2, and Assump- tion 6.1, after T iterations of the BASS algorithm, the cumulative pseudo-regret of agent satisfies:
4L
Rehuster 1,0.T
(6, ((,,d,T) + Ppmin N
CT(T.)
where:
min(T;7e)
C,(T.) Σ m5(1)
d doog
(6 (6,6 N)
1 1+
PPmin
2 log 3
T. maxT.(i..))
Pwin min Pm(j)
)
and v(5,dd d, T) as previously defined.
Proof of Theorem 6.4. At round t, for given agent i, by considering the optimistic arm x (,)))) and the optimal arm 2;, from Equation (5), we have:
26

---

Adaptive Sample Sharing for Multi Agent Linear Bandits
Fiee s (0x.00) 0 )2n))
T 2 (.(()) + (0 - 0 (i(t)) T xxx,())
2 (0x.00 (20))) " (5,((1) + 21100(00 0ill2 from Assumption 4.1
& 02,00 + B(6, N((0))
A A-IT
Ni(1) N.(1)) - 0xi(0
NN,0 +2 k.,00 - -0; from Lemma D.2
(x)((()) Xx00)
S (6, A
+ (0x210) - -00000 )700)
(N2(1) + +21 N.(1) 0f1l2
< (865, A AR(O)) N.(1) (21001 | PERICOI1A
+21 k,000 0,112
RiC0)
s 23(6, A 1110) AA +2110%(00) - -0,112
2
$
3(6, (N, + + +2110
N.(0) 01112
/N. + (t(()
$
2
366, (N; + 11 +2
(t) O + N. + N((t)
E 03
VN++ + (t(()
N₂ N (E(())
JENANN
2
866, (N, (N +
NT(1)
L +
1
Σ
L from Assumption 4.1
VN++ + (t())
N. + (t(
N. N5(0
JENAN:
2
366 (N: + 400 A- + (L)
V N + (T(1)
N; + (t((t)
2
4L
3(6, (N: (. A- + SN," (1) from Lemma 6.1 and Markov inequality
VN++ + (1
2
4L 8pmin N (1(()
3(5, N A.)
N
A.)
4L
2
B(6, (16, A-"
n (1)
Pmmin N
B(5, A.)
8pmnn N
log N 2 I
4L
22
((6,A,)) (0)l(( A-'
5pmin N n((()
VPmin
4L 8pmin N
dlog N
< 26 N) A.) 12 IA,"
nt(t)
with d", v Vpnin N
2 log
With Yabksi-Yadkorii-ao et al. (2011) and by setting v(),T.)
/ AT, d 1 + 7)), we have:
4L
Reluster S S N)u(
Ci(Te)
5pmin N
with (T,))) = Em (TT(.. nf (t), (t) defined in Lemma 6.1, Tc max, (1, and Pmin = miny Pm(j)-
Note that this upper bound is somewhat loose, as it introduces the iteration T, which the cluster is adequately estimated. While it does not highlight the adaptive nature of our collaboration, still provides the asymptotic behavior of the BASS algorithm.
P. Appendix: Additional theoretical analysis
We gather additional theoretical results here to provide comparative baselines of our analysis.
27

---

Adaptive Sample Sharing for Multi Agent Linear Bandits
P.I. Proof of the cumulative pseudo regret upper-bound for the BASS-Oracle algorithm
Corollary P.I (Cumulative pseudo regret upper-bound for Oracle). Under the assumptions made above, if we consider Oracle controller that know in advance the true clusters, after I iterations the pseudo-regret be bounded as follows:
R,D (T)(,,T)y(O
with (6, VN V 1
dloog N and v(ō, T) defined as previously. 2
Proof Corollary P.1. This a direct application of Theorem 6.4 with null neighborhood estimation error i.e., for and t 1> 0, we have (t) 0.
P.2. Asymptotic Analysis Theoretical Bounds
Building upon the result in Theorem 6.4, we derive the corresponding asymptotic behavior. First, we observe that the additive tern in the bound is subdominant in T' and can be ignored asymptotically. Furthermore, have:
3(6, Ar,) = o
Also, by comparing the confidence terms under collaborative and local designs, we obtain:
B(5, (A.) 0
Vd VVminn
V Pinin-V N
B(6, A₂)
which leads the following asymptotic regret bound:
Relnster =0
O (oyaa
Vd
VT log
))
T 7
VPmin N
Regarding the expected number of misassigned agents, we use the approximation:
v (ct)
which implies the asymptotic expression:
N 1112
O
This analysis, in conjunction with previous results, such those of Gentile et al. (2014); ei al. (2019); Ghosh et al. (2022).
supports the comparison table.
P.3. Summary of Clustering Assumptions
We summarize below the main clustering assumptions considered in the literature, well those adopted in work:
No assumption: considered in our paper, except for the setting of Theorem 6.4.
Identical bandit parameters within each cluster: used in our paper under Assumption 6.1.
Identical bandil parameters within each cluster, with minimum separation between clusters: commonly assumed in
prior work such Gentile et al. (2014); Li et al. (2016); Li & Zhang (2018); Ghosh et al. (2022); Wang et al. (2023);
Yang et al. (2024).
Approximately similar parameters within clusters, allowing overlapping cluster memberships: considered Ban & He (2021).
28

---

Adaptive Sample Sharing for Multi Agent Linear Bandits
Q. Appendix: Implementation details
At each iteration, our BASS algorithm calls at most - time the function V, which involves to inverse multiple matrices. We propose an efficient implementation involving the use of the Cholesky decomposition, the Moerman-Moorioon identity or the eigenvalues decomposition. We report here the implementation details for the main parts of the BASS algorithm and their associated complexity.
Agent separation test Recall that the ellipsoid separation test relies on the function defined in Definition 5.1, which involves computing:
2
s(1 5)
vs ej0, 1[ ()))(s)
Σ
B + s(33 + 33)
with v 4b such as ry and d are the eigenvalues and the eigenvectors of the matrix
B; (hh)((A)) Bj
Q
A chol(A)).
with chol() being the Cholesky decomposition. Moreover, one can derive the first and the second derivatives of Vi.j and performs the minimization of vi.j with the Newton's method. The eigen decomposition features a complexity of order O (d²) and the computation of the first and second derivatives has a complexity of order (d). Hence, the complexity of the separation test is of order O (rd + d²), with r being the number of iterations of the minimization algorithm. However since we use second order optimization method, in practice only a couple of iterations is needed (i.e., t < 50), so practically the separation test is of order O (dP)
Arm selection Recall that the amm selection strategy, at iteration t, for an agent i is defined as h2 log(() which features com- / A Ne,a-1
0 0 Tk + B BA (ok) with B AA (x)
k N
arg max
plexity of O (Kd).
Following the different implementations detailed here, the overall complexity of the BASS algorithm is of order O (T(N+ Kd + (N )). We notice that the BASS algorithm as linear complexity toward the number of agents N, the number of arms K and the number of iterations T. However, it features cubic dependence toward the dimension d of the problem.
R. Appendix: Experimental details
Description of the concurrent algorithms For the benchmarks, we select four other concurrent algorithms: DynUCB, CLUB, SCLUB, CMLB. First, DynUCB is simple yet efficient approach perform agent clustering in linear bandit setting. Proposed in Nguyen & Lauw (2014), it relies the k-means algorithms MacQueen (I (1967) to update the clusters each iteration. This algorithm needs to set the number of estimated clusters. For this experiment, we set it to the true number of clusters. To our knowledge, no other method proposes this k-means-based approach for this class of problems, which makes it of particular interest. Second, CLUB and its improved version SCLUB are likely the most benchmarked algorithms for the clustering linear bandit problem and can be considered the reference for it. CLUB was introduced in Gentile et al. (2014) and SCLUB resp. in Li et al. (2019), both propose to determine whether two agents belong to the same cluster by performing test the form of the difference of their bandit parameters. The improved version SCLUB provides more flexible cluster estimation by iteratively splitting and merging the clusters. Finally, we consider CMLB form Ghosh et al. (2022) which is more recent approach closely related to CLUB using the same method to determine whether two agents belong to the same cluster. However, this approach controls the minimum number of agents in cluster. Note that these last three algorithms need to set a scalar to scale the clustering threshold that determines whether this difference is significant.
Synthetic experiment settings In Section 7, in the synthetic experiment, we consider M = 3 clusters of the same size with bandit parameter (0m)mm()....)) ()) defined as: V1 < q S [ 10 C,, with (e;); being the canonical basis and 02, having its g-th entry being cos w, its + 1)-th entry being sin w and all the other entries being 0, with w E {M/16, 7 /16]. Indeed, these configurations are of particular interest because they correspond to the case where the bandit parameters are
29

---

Adaptive Sample Sharing for Multi Agent Linear Bandits
positively correlated and almost orthogonal. With w = 1/16, the bandit parameters (0m) (I.... are similar. Thus, assigning the wrong cluster will not overly perturb the agent, even though discriminating clusters will be tougher. The second scenario with ب = 7 16 the two bandit parameters are almost orthogonal which makes them easier to separate one another and thus identify the cluster. However, the two models are very different thus if an agent is assigned to the wrong cluster, he will most likely perform poorly once he will gather the observations of the other agents. For the CLUBB, SCLUB and CMLB algorithms we test two levels of clustering exploration 7 E
{ - 2-) ). the result is shown in the 'dashed' and 'solid' lines. For DynUCB, we explore M and M 20 for the k-means algorithms MacQueen (1967) with the same visual coding for the two cases. For the BASS algorithm, we test two values for E {0.1, 0.9} equivalently, with the same choice of result visualization. We keep the same color code for the rest of the experiment: DynUCB in pink. CLUB in blue, SCLUB in brown, CMLB in red and our approach BASS in orange, Ind in light gray and when available Oracle in dark gray. We choose the a-LinUCB agent policy for our algorithm and line-search the UCB parameter a within [0.1,3.0]
Clustering score computation To quantify the degree of agreement between the estimated clustershnighhorroodds and the ground truth, we compute the F1 Fi-score the graph G. w.r.t. the true eluster graph G. For the DynUCB we define G. = (V, E,) such as E, = { [ (kmeans- (aabelns-labe(0)) (aal)))==mmuuuaaaaaaaa The clustering score will output value within [o, 1].
where 1 is a perfect cluster match.
Description of the datasets and experiment settings Recall that in Section 7, we perform experiments on two real datasets. We detail here their characteristics. First we select the MovieLens dataset Harper & Konstan (2015): which is dataset that proposes the rating (from 1 to 5) of 62,000 movies by 162,000 users for a total of 25 million ratings. Each movic is represented by features describing its genre and historical records. Since the users did not rate all the movies systematically, we fill the missing values with a mmatrix-factorizatin approach Rendle & Schmidt-Thies complete dataset, we are able, for a given aser-agent-and a given movie-arm- to fetch the corresponding reward.
(2008). From this
Second, we consider, Yahoo! dataset Chapelle & Chang (2010): which is a dataset of recommendations made from queries on the Yahoo! search engine. For each query, documents are received, represented by sparse features vectors of dimension 500 and their corresponding reward (from 1 to 4) which measures how relevant the returned documents were. We consider the queries -ggets------ and the document the aee-arms-, reduce their cardinality, perform the k-means algorithm and retained only K 30 arms. As with the previous dataset, we complete the preprocessing by filling the missing rewards with the same mnttrix-acttorization approach to obtain, for each user, a reward for every arm.
We consider the same setting as the synthetic experiment: we select N = 100 agents and reduce the arm dimension to = 10 by taking the d first dimensions of the native data space. Since the randomness of our preprocessing is the user's draft be retained on the N agents, we run the experiment 50 times to average across runs.
S. Appendix: Additional details
S.1. Appendix: Additional synthetic experiment results
To complete the analysis with the synthetic data scenario considered in Section 7, we report here the evolution of the cumulative regret value in the case of M = 3 and M = 6. We consider the same experimental setting as in the synthetic data experiment of Section 7.
AAaiilable httpp::/groupl /ow.a//tt//atttta//////oo/e/e ens/
"Aaiilable at https: htapp:://wbbbseee /wwwww/wb.......o/oo//. sandbox, yahoo, com/ cataa log lo.ooopph. wttppppptppppeeeeee.eeeee
30

---

Adaptive Sample Sharing for Multi Agent Linear Bandits
(a)
(b)
angle πT 1
(i.e. D 0.20)
5000
angle
x/16
angle 7 x/16
R
(i.e. D 0.20)
(i.e. D 1.27)
5000
8000
20000
40000
6000
6000
M=3
1000
4000
angle = 7 π 16
(i.e. D) = 1.27)
5000
RA
10P
10
20000
40000
angle π 8/16
(i.e. D = 0.20)
angle x/16
angle 7 7/16 (i.e. = 1.27)
5000
R
(i.e D 0.20)
10000
10000
20000
40000
7500
7500
t
M=6
5000
5000
angle 7 πT 16
2500
2500
(i.e. D 1.27)
5000
Rs
10
109
10
10"
a
20000
40000
Figure 6. (a) Comparison of the averaged. across runs, cumulative regret evolution (Rt), for the synthetic environments considered, M the top and 6 on the bottom. (b) Comparison the averaged, across runs, evolution the cumulative regret value Ry w.r.t the UCB parameter or for the different synthetic environments considered, with the same color code as previously.
In Figure 6 a display the cumulative regret evolution (Rt), M the top and M 6 the bottom and in Figure 6 b, we display the cumulative regret last value, Rr, evolution w.r.t the UCB parameter M = 3 on the top and M = 6 on the bottom, both for all the concurrent and baseline methods. The overall performance comparison between the algorithms stays coherent with all the previous experiments and confirms the robustness and the good behavior of our algorithm. Interestingly, for BASS, we systematically observe an inflection of the curve to a quasi no-regret plateau.
S.2. Appendix: Additional real data experiment results
To complete the analysis with the real data scenario considered in the paper, we report here the evolution the cumulative regret last value w.r.t. the UCB parameter.
31

---

Adaptive Sample Sharing for Multi Agent Linear Bandits
Movie Lens
Yahoo
20000
20000
15000
15000
RT
10000-
10000
3000
5000
10
109
10
10
Figure 7. Comparison of the averaged, runs, evolution of the cumulative regret last value Rr w.r.t the UCB parameter for the different synthetic environments considered, with the same color code as previously.
In Figure 7, we display the cumulative regret last value, Rr, evolution w.r.. the UCB parameter We notice that again BASS performs better than the other algorithms, it is more pronounced in the case of the Yahoo dataset.
S.3. Appendix: Additional benchmark experiment
Additionally, consider simpler benchmark underline the robustness of the results depicted in the paper. In this benchmark, we consider the same experimental setting as in the synthetic data experiment of Section 7, but in this case, we randomly draw the bandit parameters and the arms from a standard Gaussian distribution and consider M 3. We consider three levels of noise with o {0.5, 1.0, 2.0}
5000
20000
40000
Ind
Oracle
DynUCB
1.0
CLUB
483
CLUB (>
4TH
5000
R
SCLUB (7 283
SCLUB (7 ?
A31
20000
40000
BASS ( = 0.1)
BASS (5 0.9)
CMLB ( AFT
= 2.0
47 CMLB (7 2
5000
Rs
20000
40000
Figure 8. Comparison the averaged, across runs, cumulative regret evolution (Rt); for the different synthetic environments considered
with M 3.
In Figure we display the cumulative regret evolution (Re), for all the concurrent and baseline methods, We notice the
32

---

Adaptive Sample Sharing for Multi Agent Linear Bandits
good performance of the BASS algorithm and interestingly in the where a 2.0, we notice that the difference of performance compare the other increase, which emphasize how robust the noise level our algorithm is.
0.5
clustering score
20000
40000
Ind
t
Oracle
DynUCB
0 1.0
CLUB (>
202
4
clustering score
CLUB (> 2
AP2
SCLUB (1 AgT
SCLUB (1 = AgT
20000
40000
BASS (6 0.1)
t
BASS (6 0.9)
CMLB (? A2T
0 2.0
CMLB ( 4g
clustering score
20000
40000
Figure 9. Comparison of the averaged, across runs, clustering score evolution for the different synthetic environments considered with
M
In Figure 9, we display the clustering score evolution for all the clustering algorithms. We quantify the clustering estimation quality as previously and notice that our approach achieves again the best performance. Indeed, observe that most of the concurrent algorithms did not manage recover any clusters.
33


Reviews:
[{"review_id": "U2L1KNgCGl", "reviewer": "Reviewer_VM4K", "summary": "This paper considers a multi-agent linear bandit problem in which each agent seeks to estimate its own linear parameter (so that they can minimize regret) while all agents select arms from a shared set. In this setting, agents are allowed to share reward observations with other agents to reduce the uncertainty of parameter estimates at the cost of increasing the bias of the estimates. To construct proper collaboration sets for agents, the authors leverage the idea of overlapping ellipsoid test, proposing an OFUL-based algorithm with Mahalanobis distance-based agent similarity criterion. This paper provides theoretical guarantees for cumulative pseud-regret, agent separation time (length of communication), and the expected number of misassigned agents. The proposed algorithm is also numerically evaluated in both synthetic and real-world 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": "We would like to thank the reviewer for their positive and constructive comments. Below, we address your concerns and provide detailed answers to your questions.\n\n1/ We will add a specific section in the appendix, featuring a flow-chart, where we will better expand the description of the algorithm major steps: a/ the samples sharing (L 2-4), b/ the UCB pulling (L 5-6), c/ the local variables update (L 7) and d/ the graph $\\mathcal{G}_t$ update (L 9).\n\n2/ The focus of this paper is to analyze the effect of sample sharing on regret minimization in the general case—i.e., without any assumption on the agent clustering structure. To that end, we ignore considerations such as communication cost. However, for completeness, we will add a section in the appendix presenting the empirical communication cost in the federated setting (using a central server), along with a theoretical upper bound in the case where the clustering structure is assumed (since in that setting, the number of agents per cluster can be quantified).\n\n3/ The term $\\beta(\\delta, \\mathbf{A}_t)$ is stated in Theorem 4.1 and corresponds to the confidence ellipsoid radius of the OLS estimate. We will restate and clarify the definition of $\\beta(\\delta, \\mathbf{A}_t)$ in Theorems 5.1, 6.1, 6.2, 6.3, and 6.4, and underline that the definition of $\\nu$ remains unchanged across these theorems.\n\n4/ A particularity of the sample sharing problem is that it unfolds in two distinct phases: one where sharing is beneficial, and another where independent parameter estimation is preferable. Theorems 6.2 and 6.3 present the cumulative regret at the transition point between these phases, highlighting the gain from sharing before switching to an independent regime. Table 1 reports the asymptotic regret in the independent setting, after collaboration has ceased. Thus, the results of Theorems 6.2 and 6.3 cannot be presented in the same form. However, the upper bound can be summarized as a tradeoff between the acceleration of the first term (in $\\mu$), compared to the independent regret ($\\nu$), and the bias from data sharing, captured in the second term.\n\n5/ The other algorithms perform poorly in terms of clustering. Rather than accurately recovering the cluster structure, other approaches focus on regret minimization, either by design or by regret-oriented hyperparameter optimization. Figure 8 in Appendix R.3 shows the progressive degradation of the clustering score. Notably, no existing work in the literature provides theoretical guarantees or empirical validation regarding the quality of the clustering.\n\n6/ Beyond the analysis of sample sharing itself, the most significant aspect to revise is the use of the Euclidean distance criterion (as in Gentile et al. (2014); Ban & He (2021); Wang et al. (2023)), which is effectively equivalent to the test proposed by Gilitschenski et al. (2012), where the ellipsoids considered are $\\mathcal{E}(\\hat{\\mathbf{\\theta}}_i, \\lambda^{\\min}(\\mathbf{A}_t)\\mathbf{I}, \\tilde{\\beta})$ and $\\mathcal{E}(\\hat{\\mathbf{\\theta}}_j, \\lambda^{\\min}(\\mathbf{A}_t)\\mathbf{I}, \\tilde{\\beta})$  thereby ignoring most of the arm-pulling history. \n\n7/ We will add a summary table in the appendix outlining the different clustering assumptions considered in the literature and mentioned in our related work:\n* no assumption: our paper, except in “Regret analysis with clustered parameters”.\n* same bandit parameter within a cluster: our paper with Assumption 6.1.\n* same bandit parameter within a cluster and a minimum distance between clusters: Gentile et al. 2014, Li et al. 2016, Li & Zhang, 2018, Wang et al. 2023, Yang et al. 2024.\n* close bandit parameters within a cluster and overlapping clusters definition:  Ban & He 2021.\n\nNote that our primary intention is to derive a principle rule to share samples between agents without introducing assumptions on their distribution. We then extend our results to the clustered setting to provide a fair comparison to existing work.\n\n8/ In the synchronous setting, all agents in a cluster select an arm based on the same shared history. Since UCB is a deterministic rule, two agents using the same history will select the same arm. Therefore, their design matrices will also be identical. We will add an additional section in the appendix to better explain this aspect of our setting.\n\nAdditional comments:\n\nIf you have any additional questions about the paper and the theoretical and empirical analysis, we would be happy to provide further clarification.\n\nPlease let us know if you need any additional information, clarification or modification that we could provide for you to improve your score.", "claims_and_evidence": "This paper claims three key contributions: no parameter assumption, anisotropic approach, and analysis. However, as one of the main contributions, the algorithm description in Section 6.1 appears too brief. Could the authors provide a more detailed explanation to enhance clarity?", "methods_and_evaluation_criteria": "This paper employs appropriate metrics, such as cumulative pseudo-regret and clustering scores, to evaluate performance. However, while the number of communications (i.e., agent separation time) appears to be considered in the theoretical analysis, it is not reported in the numerical study. Could the authors clarify this or provide the corresponding simulation results?", "theoretical_claims": "- In Theorem 6.2, the term $ \\beta(\\delta, {\\bf A}_{T_s}) $ is not explicitly specified.\n- In Theorems 6.3 and 6.4, the terms $ \\nu(\\delta, T) $ are not explicitly specified. Could the authors clarify whether they take the same form as in Theorem 6.2? \n- I am seeking a better understanding of the general regret upper bound for all agents presented in Theorem 6.3. Could the authors summarize the assumption-free bounds in a similar manner to Table 1 for clarity?\n\nProviding these clarifications in the paper would enhance readability.", "experimental_designs_or_analyses": "Could the authors provide comments on the results presented in Table 3? In particular, could they offer an explanation or intuition for why almost all benchmark algorithms received zero scores? Additionally, could the authors discuss whether the approaches proposed in this paper could be incorporated into these algorithms?", "relation_to_broader_scientific_literature": "This work may bring attention to the potential of incorporating Mahalanobis distance as a similarity measure in the multi-agent regret minimization research community.", "essential_references_not_discussed": "I am not aware of essential references that were not discussed.", "other_strengths_and_weaknesses": "Strength:\n- This paper proposes an interesting algorithm for multi-agent linear bandit and provides extensive theoretical analysis. \n\nWeakness:\n- Some of the results are not presented clearly.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "- I am trying to better understand the claim that, unlike \"most\" existing approaches, this work does not rely on any assumptions about the structure of the bandit parameters. Do works that assume an agent cluster structure (e.g., Gentile et al. 2014, Ban & He 2021, Wang et al. 2023) impose assumptions on the parameters? Could the authors clarify this point?\n\n- I am puzzled by the discussion following Lemma 5.1, which states that as we consider synchronous pulling, we have $ {\\bf A}\\_{i, t} = {\\bf A}\\_{i, t} = {\\bf A}\\_t$. My understanding is that even if agents $i$ and $j$ are synchronous, if they pull different arms, then ${\\bf A}\\_{i, t} \\neq {\\bf A}\\_{j, t}$. Could the authors clarify this point? Please let me know if I have misunderstood anything.", "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": "vWfFE9QP0B", "reviewer": "Reviewer_R5Cg", "summary": "This paper studies the collaboration of multiple heterogeneous agents in addressing a linear bandit problem. It proposes an adaptive sample approach to dynamically determine whether agent pairs should cooperate (utilize observations). Based on the technique, the paper proposes the BASS algorithm to address the multi-agent linear bandit problem with a tighter theoretical regret bound and better empirical performance.\n\n\n#### After rebuttal\n\nThis is a nice piece of work. The reviewer would like to see the final version with all the comments addressed accordingly.", "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": "We would like to thank the reviewer for their positive and constructive comments. Below, we address your concerns and provide detailed answers to your questions.\n\n1/ Thank you for the remark; we will revise the structure of our paper, as we agree it improves the overall logical flow.\n\n2/ There is indeed a challenge in analyzing the effects of asynchronous pulling. It leads to differently shaped ellipsoids and requires a rescaling term in the form of $\\mathbf{A}_i^{-1} \\mathbf{A}_j$, which makes the proof much more difficult. Therefore, we restrict our analysis to the synchronous setting. In Definition 5.1, we use the general case because this definition is used in the practical implementation of the algorithm, which allows for empirical evaluation of our method in the asynchronous setting.\n\n3/ Thank you for pointing out this typo: the correct definition consider the minimum w.r.t $s$ and compare the later to 0:\n$$\n\\Psi(i, j, t) = \\mathbf{1}\\left \\\\{ \\min_{s \\in ]0, 1[} \\frac{\\gamma^2}{4} - \\sum_{l=1}^d \\mu_{tl}^2 \\frac{s (1 - s)}{\\beta_{i,t}^2 + s (\\beta_{j,t}^2\\eta_{tl} - \\beta_{i,t}^2)} < 0 \\right\\\\} \\enspace.\n$$\nWe will correct this and update the corresponding subscripts.\n\n4/ The graph $\\mathcal{G}_t$ is updated and stored in a central server that first requests the design matrix and the regressand of each agent in the neighborhood of agent $i$. Then, send collaborative OLS variables to agent $i$ to pull an arm. Hence the neighborhood is determined by a central server to manage the sampling sharing logic within the agents network. Note that our work focuses on sample efficiency rather than communication; however, sample sharing for a general decentralized setting is a promising line of future work.\n\nAdditional comments:\n\nIf you have any additional questions about the paper and the theoretical and empirical analysis, we would be happy to provide further clarification.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "The reviewer does not check the proof in detail, but the reviewer goes through the detail explanation in the main text and believes the intuition before the theoretical results of this paper make sense.", "experimental_designs_or_analyses": "Yes, the simulations look reasonable to the reviewer.", "relation_to_broader_scientific_literature": "The idea proposed in this paper may initiate a broader impact in the community of sequential decision-making and reinforcement learning.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Overall, the reviewer believes the paper makes a fair contribution, and thinks the approach can be extended in broader areas, like other heterogeneous multi-agent bandits setting, and MARL as well. \n\n### Strengths:\n- New approach and better results: the adaptive proof discussed in Sections 3.2 and 5 is new to the reviewer, and the BASS algorithm based on the technique is also novel in the literature with slightly tighter regret bounds. \n\n- Clear writing: the authors did a good job in presenting their work, with toy two-agent as an example, and then extended to multi-agent, with synchronous action as a start, and then generalized to heterogenous actions. The illustrative figures (Figures 1 and 2) also help the reviewer better appreciate the fundamental idea behind the approach. \n\n### Weakness:\n- Some sections can be merged; for example, Section 4 should be in the Preliminaries, and Section 7 should just be put as a remark for Theorem 6.4 instead of a full section. \n- Some presentation/writing needs further clarifications, see \"Other Comments\" below.", "other_comments_or_suggestions": "In Section 5:\n- The presentation logic also makes the reviewer a bit confused. At the end, the action sequence, or $\\bm A_i$, are different across agents. Why the section starts from the general case in Eqs. (3) and (4), and then go to the homogeneous sequence case in Lemma 5.2, and then go back to general case in Definition 5.1? Is there a challenge of extending from Lemma 5.2 to Definition 5.1?\n- In the equation of definition 5.1, the reviewer is a little bit lost: what is $s$ in the definition, and where $t$ as an input to $\\Psi$ appears in the equation?\n\nIn Section 6:\n- In Algorithm 1’s Line 3, how the neighbors $\\hat{\\mathcal{N}}$ are determined by the updated graph $\\mathcal{G}_t$ in Line 9, or by the environment?", "questions_for_authors": "See 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": "am85eZ5l2E", "reviewer": "Reviewer_vhoL", "summary": "This paper considers the problem of multi-agent linear bandits in a collaborative setting where the aim is to maximise the cumulative reward across all agents. In this problem each agent has the same (static) set of arms but has a different parameter. The idea is if the parameters of two agents are close enough together then pooling their results to create a single parameter estimator is better than learning independently. \n\nWhereas previous works assume that the agents form clusters in which the intra-cluster parameter distances are within a certain threshold, this work has no such assumptions. They also show that in the clustering case their algorithm theoretically outperforms existing algorithms for that case. The algorithm is also relatively efficient.\n\nThey also give the results of experiments, both on real and synthetic data, showing that their algorithm outperforms others.", "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": "We would like to thank the reviewer for their very positive and insightful comments. Thank you very much for your kind appreciation of the paper's results.\n\nThank you for the suggestion regarding the structure of the paper; we will revise it, as we agree it improves the overall logical flow.\n\nAdditional comments:\n\nIf you have any additional questions about the paper and the theoretical and empirical analysis, we would be happy to provide further clarification.", "claims_and_evidence": "I have not read the proofs so can’t confirm", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I have not read the proofs", "experimental_designs_or_analyses": "I did not check", "relation_to_broader_scientific_literature": "There has been much work on collaborative multi-agent linear bandits. This paper gives the first algorithm that makes no assumptions on the distances between the parameters of the agents. Most other works assume a clustering assumption, and this work also shows that the same algorithm has a state of the art result there as well (albeit only a slight improvement on the previous state of the art). These two facts combined make this work a significant contribution to the field.", "essential_references_not_discussed": "Unknown", "other_strengths_and_weaknesses": "I feel the result is strong. But also, as far as I am aware from interacting with ChatGPT, the original clustering algorithm of Claudio Gentile et. Al. treats all agents in a cluster the same when it has learnt it. If significant time passes the strategy of playing each agent the same in a given cluster is non optimal and it is better to learn them independently, whilst the algorithm of this paper appears to eventually learn them independently, which seems to be another strength (although I guess other clustering algorithms have been proposed that do this).", "other_comments_or_suggestions": "I very much like the way the paper is presented - building up from the fundamental principles of two agents sharing observations and the single agent stochastic linear bandit. However, in my subjective opinion I believe that it is best to place the full theoretical result as soon as possible in the work (which would be before these sections).", "questions_for_authors": "None", "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": "omXYaxzqgU", "reviewer": "Reviewer_R3aR", "summary": "The paper studies an adaptive sample sharing problem for multi-agent linear bandits, where agents' true parameters may be different. The authors propose a separation test, which detects the stopping time for beneficial collaboration. The authors provide both the separation time upper-bound and cumulative pseudo-regret upper bound. The authors also compared the pseudo regret with existing methods. Finally, the authors empirically conduct experiments using both synthetic data and real-world data.", "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": "We would like to thank the reviewer for their positive and constructive comments. Below, we address your concerns and provide detailed answers to your questions.\n\n1/ The orange ellipsoid (representing the collaborative estimation) corresponds to a reduced estimation variance, as it yields a smaller Mahalanobis radius of the confidence ellipsoid—note that the smaller ellipsoid might not be contained in the bigger one, we will provide a more general illustration to underline that. However, notice that the center of the orange ellipsoid differs from that of the blue ellipsoid due to the introduced bias, illustrating the bias (OLS estimate deviation) - variance (confidence ellipsoid radius reduction) tradeoff. \n\n2/ We will add a section in the appendix to properly detail the steps to obtain Table 1 from Theorem 6.4 and Lemma 6.1. The proof is similar to CLUB and SCLUB, and the improvements stem from both the Mahalanobis separation criterion and a refined analysis from Abbasi-Yadkori et al 2011.\n\n3/ The definition of $\\nu$ remains unchanged across all theorems: it is the regret upper bound without sample sharing. Considering the upper bound of Theorem 6.4, the first term corresponds to the regret minimization improvement due to the variance reduction (represented by $\\mu$) and the second term corresponds to the cost of sharing (i.e., the shared OLS estimate bias, due to misassigned agents). This second term features an interplay between the determinant and the exponential term in $n_i^e(t)$, which overall results in a $\\mathcal{O}(\\frac{4L}{\\delta \\rho_{\\min}\\sqrt{T}^{\\gamma^2R^2 - 1}})$ regret. This leads to an overall behavior of the upper bound in $\\mathcal{O}(\\sqrt{T} \\log (T/d))$ as depicted in Table 1.\n\n4/ Thank you for pointing out the inconsistency in the appendix content table; we will revise the naming of the appendix sections accordingly.\n\n5/ To derive a lower bound on the cumulative pseudo-regret, we consider the optimal case of $N$ collaborative agents sharing the same bandit parameters, forming a single—known—cluster. This leads to: $\\frac{1}{N}\\mu(\\delta, T) \\leq R_{i,0,T}^{\\mathrm{cluster}}$. We will further compare the additional terms stemming from the clustering estimation in the upper bound of Theorem 6.4 to this lower bound to underline the cost of clustering.\n\n6/ As defined by in [1], pseudo-regret uses expected rewards, while regret uses realized rewards; for our paper we use Bubeck’s definition.\n\n7/ Thank you for pointing out the typo in Table 1: the proper constant term should be $d\\sqrt{\\frac{M}{N}}$ for CLUB and SCLUB which is equivalent to $\\frac{d}{\\sqrt{\\rho_{\\min}N}}$ for balanced cluster sizes. As mentioned in 2/, the differences ($\\sqrt{d}$ factor and $T/d$ in the logarithm)  are due to the use of a Mahalanobis metric combined with a refined analysis (i.e., applying the Elliptical Potential lemma on the design matrix $\\mathbf{A}_i$).\n\n[1] Bubeck, S., & Cesa-Bianchi, N. (2012). Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends® in Machine Learning, 5(1), 1-122.\n\nAdditional comments:\n\nIf you have any additional questions about the paper and the theoretical and empirical analysis, we would be happy to provide further clarification.\n\nPlease let us know if you need any additional information, clarification or modification that we could provide for you to improve your score.", "claims_and_evidence": "I have several confusions when reading the paper. \n\n1. Can you elaborate on the bias-variance tradeoff in Figure 1? Why is the orange ellipsoid inside the blue ellipsoid?\n\n2. I'm confused of the connection between Table 1 and Theorem 6.4? How do you get the $\\sqrt{T}\\log(T/d)$ upper bound from Theorem 6.4?", "methods_and_evaluation_criteria": "The paper studies the separation time and cumulative regret of the proposed algorithm, which looks reasonable to me.", "theoretical_claims": "I feel the theoretical parts are not well presented. More specifically in Theorem 6.4, what is $v(\\delta, T)$? How do you quantify $n_i^e(t)$? The authors should have a remark to discuss the quantity of the bound. Currently, the upper bound is not very clear to me.", "experimental_designs_or_analyses": "I do not find big issues in experiments. This paper is mostly a theoretical work.", "relation_to_broader_scientific_literature": "This research is related to the broader multi-agent collaborative learning, where multiple agents collaboratively share data for learning purposes.", "essential_references_not_discussed": "I am not very familiar with the collaborative learning literature in linear bandits so I'm unsure whether essential references are missed.", "other_strengths_and_weaknesses": "The paper provides detailed upper bound analysis on pseudo regrets, the number of misaligned agents, and separation time. They also provides the lower bound on separation time. However, the lower bound for pseudo regrets is missed. How close is your algorithm's upper bound to the lower bound?", "other_comments_or_suggestions": "I'm curious why the authors define \"pseudo regret\" instead of \"regret\". The definition looks the same as the standard regret.", "questions_for_authors": "In Figure 1, how do you compare BASS with CLUB and SCLUB? The constant term of SCLUB and CLUB depend on $M$, and your algorithm's upper bound has different parameters. It's unclear why BASS has tighter upper bound.", "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": {}}]

Author rebuttal:

Meta-review: I appreciate the work as collaborative learning in bandits is an important and practical topic and the results obtained in this paper are solid. Two of the four reviewers are on the fence and remain so after the rebuttal. While the overall evaluation is a bit on the borderline, I'm leaning towards accepting the paper and concur more with the two reviewers that are more positive.
Decision: Accept (poster)