Multi-Agent Learning with Heterogeneous Linear Contextual Bandits
Authors: Anh Do
Thanh Nguyen-Tang
Raman Arora
Venue: NeurIPS 2023 poster (2023)
Keywords: Multi-agent
Bandits
Cooperative

Abstract: As trained intelligent systems become increasingly pervasive, multiagent learning has emerged as a popular framework for studying complex interactions between autonomous agents. Yet, a formal understanding of how and when learners in heterogeneous environments benefit from sharing their respective experiences is far from complete. In this paper, we seek answers to these questions in the context of linear contextual bandits. We present a novel distributed learning algorithm based on the upper confidence bound (UCB) algorithm, which we refer to as H-LINUCB, wherein agents cooperatively minimize the group regret under the coordination of a central server. In the setting where the level of heterogeneity or dissimilarity across the environments is known to the agents, we show that H-LINUCB is provably optimal in regimes where the tasks are highly similar or highly dissimilar.

Multi-Agent Learning with Heterogeneous Linear Contextual Bandits
Anh Do
Thanh Nguyen-Tang Johns Hopkins University nguyent@cs. jhu. edu
Raman Arora Johns Hopkins University arora@cs, .hh edu
Johns Hopkins University ado8@jhu. edu
Abstract
As trained intelligent systems become increasingly pervasive, multi-agent learning has emerged popular framework for studying complex interactions between autonomous agents. Yet, a formal understanding of how and when learners heterogeneous environments benefit from sharing their respective experiences is still in its infancy. this paper, we seek answers to these questions in the context linear contextual bandits. We present novel distributed learning algorithm based on the upper confidence bound (UCB) algorithm, which we refer to as H-LINUCB, wherein agents cooperatively minimize the group regret under the coordination of central server. In the setting where the level of heterogeneity or dissimilarity across the environments is known the agents, show that H H-LINUCB is provably optimal in regimes where the tasks are highly similar or highly dissimilar.
Introduction
Heterogeneous multi-agent systems enable agents to work together and coordinate their actions to solve complex problems. These systems inherently scalable, they distribute the computational load across multiple agents. This scalability allows the system handle large and sophisticated tasks beyond the capabilities of single agent. Despite the potential of multi-agent systems, it poses the following fundamental challenges.
Statistical challenge. Each agent's reward distribution may vary, meaning that differ- agents receive different rewards for the
action. This heterogeneity in reward distributions introduces complexity and makes coordination among agents more difficult. Furthermore, |Wang al. [202T] point that ineffective use of shared data could lead to a significant negative impact on the overall performance. In particular, sharing experiences amongst agents may hinder the system's performance if the tasks are dissimilar (Rosen- stein, 2005 Brunskill and Li 2013).
Computational complexity. Coordinating the decisions of numerous agents and performing complex computations pose challenges in terms of computational resources, time constraints, and algorithmic scalability.
Communication cost. Efficient communication is also fundamental challenge for a large- scale multi- Maltti-agettttt system. As the number of agents system increases, the complexity of interactions between agents grows exponentially. Managing the interaction of numerous agents and making decisions in a timely manner becomes increasingly difficult.
Several works address these challenges for heterogeneous multi-agent systems, including federated linear bandits (Huang al.) [02 | Li and Wang 2022), clustering bandits [Gentile et | [014 Ghosh al. 2023], multi-task linear bandits Huu ct al. 202 Yang et al. 2021]. However, these works either rely some special structure of the parameter Li and Wang 2022 e.g., low-rank structure Hu
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

et al.. 2021 or make different assumptions, e.g., stochastic contexts, finite decision set (Huang et al. 2021
Ghosh et al. 2023). etc.
In this work, we provide a general notion of heterogeneous multi-agent linear contextual bandits (e-MALCB) and give analytical results under different regimes of heterogeneity. Specifically, study a model that consists of M agents. Each agent E [M] plays a d-dimensional linear contextual bandit, parametrized by 0g (see Section for more details), for T' rounds. We capture the heterogeneity by dissimilarity parameter > 0 such that 110; 0z e|l2 S E, for all i, E [M]. Notably, we do not assume any special structure on the linear parameter, and we allow the decision set to be infinite and possibly chosen adversarially.
Motivating application. Consider a personalized recommendation system for online advertise- ments [Li et af.] 2010 (Boneefoou et al.] 2020), Ghosh et al. [023). Here, the platform needs to be adaptive user preferences and maximize total user clicks based user-click feedback. Each ad can be represented as a context vector, encoding information such as publisher, topic, ad content, etc. The inner product of the ad's context vector and user preference represents the alignment. A higher inner product value indicates greater relevance of the ad. Furthermore, the recommended ads must be personalized to accommodate user preference differences. One naive approach would involve solving separate linear contextual bandit problem for each user. However, we can pose the following question: Can we enhance the system's performance by pooling data from other users? If so, to what extent of user heterogeneity can we achieve that?
Contributions. We make the following contributions in this paper.
First, we formulate the heterogeneous multi-agent linear contextual bandits as e-MALCB problem. building on the classic notion of heterogeneity in multiarmed bandits (MABs) Wang et al. [2021]. Our notion of heterogeneity is natural and captures many settings in real-world applications.
Second, when the level of dissimilarity is known, we propose a distributed algorithm, namely H-LINUCB which achieves regret of (dd/MT MT + min(sdMT, d.M vT)) under the coordination of a central server. We discuss in detail how to handle the dissimilarity and introduce a criterion for stopping collaboration when the level of dissimilarity is high. We show that under the regime of low dissimilarity, we can still achieve regret of ((dVMT), which is the same regret rate as M agents collaborate to solve the same task. In this regime, H-LINUCB outperforms independent learners improving by a factor of v VM, from OdM TT) to (dV)MT). This is significant when we have a large number of agents.
Third, we complement the upper bound with a lower bound of Q(dvMT + min(sMT, dMM VT)). This suggests that our theoretical guarantees are tight in settings where tasks are highly similar or highly dissimilar.
theoretical results with numerical simulations synthetic data. When the level of dissimilarity is small, H-LINUCB outperforms independent learning. When the level of dissimilarity is high, our simulation shows that blindly using shared data can lead to linear regret, emphasizing the importance of the criterion we propose for when stop the collaboration.
Finally, we validate
2
Related work
The classic linear bandits have a rich literature in both theory and application: see, for exam-
ple. [Abbasi- Yadkori et al.] 2011 Li et al. 2010 Chu et al.] 2011 Chatterji al. 2020 Rus mevichientong and Tsitsiklis 2010 Bouneftouf et al.) 2020) Mahadik et al. 2020 to name a few.
With surge in distributed computing, multi-agent systems have shown their potential and gained more attention in recent years. A large body of works dedicated to studying the homogeneous setting of multiple collaborating agents solve a global linear bandits problem [Wang et al. 2020 Dubey and
Pentland 2020 Moradipari et al. 2022 Mitra et al. 2022 Martinez- et al. 2019 Chawla et al. 2022).
The problem of multi-agent linear bandits in heterogeneous environments, on the other hand, has received limited attention. /Soare et al. [214] were amongst the first to study heterogencous linear

---

bandits; however, the focus in that work is not on group regret, and the authors only consider the setting where tasks are similar. More recently, Huang al. [02T] proposed an algorithm with novel multi-agent G-Optimal design. They assume that the heterogeneity comes from the contexts associated with each agent, but agents can still collaborate since they share the same arm parameters. aid Wang [022] consider an extension where they assume that each agent's parameter has two components a shared global component and an individual local component. This formalization requires agents to work on their respective tasks (the local component) but still allows agents to collaborate on the common task (the global component). Wang et al.) [02T] study heterogeneity of the Bernoulli MABs problem and provide guarantees for both cases when the level of heterogeneity is known and unknown.
A related line of work studies heterogeneous linear bandits through clustering (Gentile et al. 2014 Li et al. 2016, 2019] Korda et al., 2016, Ghosh al. 2023]. These works give a guarantee based on the clustering structure of the different linear bandit problems agents belonging to the same cluster will likely achieve the highest collaboration gain. We do not make any assumption about the "clusterability" of different bandit problems may encounter. A yet another approach focuses on multi-task linear bandits, wherein we solve multiple different but closely related linear bandits tasks (Yang et al.] 2021 2022 these works rely on the assumption that all tasks share a common k-dimensional representation, where k < d. Then, pooling data from different bandits helps learn good representation and reduces the statistical burden of learning by reducing the linear bandit problem in dimensions to a k k-dimensional setting. We do not consider multi-task learning here.
Hu et al. 2021 Cella et al. 2023 Du et al. 2023]. In particular,
Our formulation of heterogeneous contextual linear bandits is similar that of misspecified and corrupted bandits setting (Remark(3. 3.1 for more details) [hhosh et al. 2017 Lattimore and Csaba 2020 Takemura et al. 2021 Foster et al. 2020 He et al. 2022]. It is then natural to ask we can apply the techniques from that part of the literature to deal with the dissimilarity between different bandits in heterogeneous setting. However, there a fundamental difference in how the two problems manifest themselves. While misspecification may be typically unavoidable in many settings, in a heterogeneous bandit setting, an agent can always choose to rely solely on its own data if finds that the data from other agents too dissimilar.
3 Preliminaries
Multi-Agent Linear Contextual Bandits. We consider a multi-agent learning setting with M agents, At each round E [T', each agent E [M] picks an action (context)) Im.t E Dm,,, where Dm,,t C IRd is given decision set. The agent m receives reward Vm,t nm Om + Tmm,o where Om Idd is an unknown but fixed parameter and 7/, r is sub-Gaussian noise. Let F. denote the filtration, i.e., the o-algebra, induced by a (f [[#m,kmme]MM [ee[MM..SHH+ (Dm.teJm((M]jss)
Regret. Our goal is to design algorithms for multi-agent linear contextual bandits that achieve small group regret defined
T M
R(M,T)
max (x, Om) - (F 0mn)
1=1 m=
Assumption 3.1. Without loss of generality, we assume that,
1. Bounded parameters: ||0m.|| S 1, |x||2 S 1, Va E Dm,,, E [M], E (T].
2. Sub-Gaussian noise: 7/m, is conditionally zero-mean 1-sub-Gaussian random variable with respect to Ft-1-
We note that the assumptions above are standard in linear bandits literature [Abbasi-Yadkori et al., 2011 Hu et al. |202 Huang et al.] 2022]. Further, it is straightforward to let |0mm S B, for some constant B, by appropriately scaling the rewards. We make no additional assumptions on the context. The decision set could be infinite, and given to each agent possibly adversarially.
'Throughout the paper, use the terms action and context interchangeably.
3

---

Definition 3.1. (E-MALCB Problem) A multi-agent linear contextual bandits problem is said to be an E-MALCB problem instance, for any two agents i.j [M]. 10, -8yl2 S for an ε 2 0. We call & the dissimilarity parameter.
Definition 3.2. (Homogeneous setting) A multi-agent linear contextual bandits problem is homoge- neous, if it is an E-MALCB with e = 0, i.e., 02 = for all i, E [M]]
Given the bound on the parameters, we have that ||0, 0, S 2 for any i,j E [M]. Therefore, suffices to only consider the case where s E 2].
Remark 3.1. (Misspecified structure) Under the Assumption 3.1 for any two agents i, have that 0. r - E - 0J x I 0. x + E. Then, Elyj.e| = 0. x + A
(x), for A(x) E [-e, El. This represents
misspecified structure wherein agent receives the reward Vi.. from agent + i.
Remark 3.2. (Recover the E-MPMAB of Wang al. [20T]). We note that the s-MPMAB is
special case of E-MALCB. Define the mean reward of K arms for agent m as 6m = [4" Pk]
Then, the reward for arm k at round t is vr = 0. e + 7h-- The decision set D = {ei...., eg
are the standard basis vectors. This a fixed set of arms, given to all agents at each round. The dissimilarity parameter is defined as: ||0, 0y
for all i, [M].
Nonetheless, the results in Wang et al. 202 I are not directly comparable to ours since the dissimilarity parameter E hides inside the size of the set of subpar arms [ Furthermore, Wang et al. [2021) give guarantees in full-communication setting, in which each agent has full access to the past data of all other agents at every round.
Remark 3.3. There are other formulations that also capture the heterogeneity in multi-agent linear bandits. Huang al. [202I] consider multi-agent linear bandits setting with a fixed size decision set, containing K actions, [00 which is unknown to the agents. Each agent is associated with K different contexts Ja=1- At reach round, each agent i picks an action a E [K], and receives reward rt == + a/ Since Fi,a can vary for different agents, this captures the heterogeneity across agents. It also allows for collaboration across agents since they share the same decision set.
Li and Wang 2022 assume that each agent parameter 0 has special structure that consists of shared global component and a unique local component. The reward of agent i can be given as,
((()
x(9)
We do not assume such special structure of the linear parameter.
((s)
(()
The notion of c-MALCB is in the worst-case sense. One can imagine M-MACCB instance of M agents, such that M - 1 agents have identical linear parameter, i.e. 8 = fj. Vi,j E [M - 1], and the parameter of the last agent |0 Ow 1| = e. With this type of instance, for large M, we can simply use DISLINUCB of Wang et al. 2021 and achieve nearly optimal regret. Clustering bandits framework could also be used for this -MA.CB instance since it presents strong cluster structure. Even though our formulation takes a pessimistic approach but it can handle the case that handits are largely unclustered.
Our goal is to design a system such that its performance is no worse than running M independent bandit algorithms for each user (zero collaboration). The system should also be adaptive to the heterogeneity in the problem instance, i.e., it should automatically leverage any structure in the problem parameters {8.. J.M. to collaboratively solve all bandit problems at "faster" rate. To benchmark the performance of such a system, we consider the following baseline.
Independent Learners (IND-OFUL). We establish a baseline algorithm in which each agent independently runs an optimal linear contextual bandits algorithm (OFUL, [Abbasi- Yadkori et al.) 2011I) without any communication. Each agent incurs (dvTT) regret, and Ó VT) group regret.
Notation. We denote the weighted norm of vector x w.t.t matrix A (Mahalanobis norm) as || = V Ar. We write >> iff A - B is a positive semi-definite matrix. We use Ô (-) to hide the polylogarithmic factors in standard Big O notation.
'ROBUSTAGG(E) algorithm achieves Ó O(VI. MT + M ( -17 + M regret when e is known.
The subpar arms Iz is defined in Wang al. 2021 Section 3.2].

---

Main Results
In this section, present H-LINUCB, UCB-style algorithm for e-MALCB problem, and give guarantees for the case when the dissimilarity & is known to the agents. In Section 4.2 we present a lower bound and discuss the implication of our results in different regimes of dissimilarity. We defer the detailed proof to the Appendix.
Algorithm H-LINUCB
Input: Dissimilarity parameter number of agents M, number of rounds T', regularization parameter
X, dimension confidence parameters 3r, Vt E [T], weight threshold parameter a, collaboration
budget т, synchronization threshold D
D lsyn is the index of the last synchronized round 2: V sgm f- 0, bsyn + 00 Vayn, bagn store the relevant statistics of all agents after synchronization
Lynn 4-1
3: Vepach.. <- 0, Depoch,m <- 0, Vm E [M]
Vepocch. pepoch. store the relevant statisties of
agent m in the current epoch
4: for = 1,... T do
5:
for Agent
1.... M do if / - then
6:
7:
V sym f- 0, Daynn + 0 Vepoch.m f 0, bepoch.m f-
8:
9:
end if
10:
Vine +- AT Vayn + Vepoch,, Om,t f- V (bayn + Depoch,m)
11:
1 Raa :100m
0 Vmn {Ba
12:
Construct the confidence ellipsoid C.,,
13:
(Im,t 0m.z) = arg max(x,0)EDD XCm,
(0, x))
14:
Play Zm,t and get reward ym,t
15:
Wm,t 1 [t r] min (1, ml (lllmmmmll))))))) + 1lt 2 r]
16:
Vepach, m Vepochh.. n t FFmtt Depoch,m. + ,epoch,m + Wm, F Im.t log [Vet(Vm., + 1mm a Fm, det + Vsyn)] (L - (syn) 2 D and I. < then
17:
18:
19:
Send synchronization signal to the server start communication round
20:
end if communication round started then
22:
Agent sends Vepoch,i; bepoch, to the server, Vi E [M] Server computes Vayn V agns. + Vepoch,is in bayn f- bagn + bepoch, Vi E [M] Server sends V Vsyn bagn back to all agents
23:
24:
Vepoch.a + O; bepoch, + vi [M]
Reset Vepoch, bepoch, for the new epoch
26: tzgn + -t
end
28: end for
29:
end for
4.1 H-LINUCB Algorithm
H-LINUCB is a distributed UCB-style algorithm (see A pseudocode), which agents work cooperatively under the coordination of central server.
H-LINUCB has two learning phases: the collaboration phase (for rounds t E {l...., 1}) and the independent learning phase (for rounds t E {r,..., TT),, where budget. Intuitively, our two-phase learning framework ensures that the agents stop collaboration after rounds lest they incur linear regret in bandit environments with large dissimilarity. Naturally, then, the parameter 7 should depend on the dissimilarity parameter, E. We give an optimal choice of in Theorem 4.1
T' is the collaboration
At each round < r (the collaboration phase), each agent's data is weighted to adapt to the dissimilarity across different agents (Line 15). Then, each agent uses the weighted data construct
5

---

its Confidence Ellipsoid (Line [2] and makes a decision following the optimism principle (Line l3p. When certain condition is met (Line 18). data is pooled and synchronized across the agents. Starting from round т, all collaboration ceases and each agent enters the independent learning mode and runs an independent copy of the OFUL algorithm [Abbasi-Yadkon) al. 2011 locally for the last
T T + 1 rounds.
We note that H-LINUCB builds upon DISLINUCB of Wang et al. 2020 Protocol 8] with the following modifications:
We scale each agent's data using the weight min(1, az <</ll,,,)llv;..) which we adopt from He et al. [022]] to handle the dissimilarity across different agents (Line
We only allow collaboration until round (Line [8.. The value of depends the dissimilarity parameter, which we assume is given.
We reset the variables Vayn, Dayn Vepoch, m: bepoch,m at round T (Lines 6 agent switches to the independent learning mode. Here, epoch refers to the time period between two consecutive synchronization rounds.
where each
Each agent uses all of the data available to them at each round to construct the Confidence Ellipsoid Cn.t using the result in Lemma 4.1 Given the confidence ellipsoid, the agent chooses the action optimistically: (em.):0m...)
arg maX(x.0)e (...::.................... XC... (0, z)). During the collaboration phase, if the variation in the volume of the ellipsoid exceeds a certain synchronization threshold, D, it triggers a synchronization condition (Lines 18 20p. Subsequently, the central server commences the synchronization procedure to update Vsyn. Deyn across all participating agents (Lines 21 27| The optimal value of D depends on the number of agents M, dimension d, and the collaboration budget
The weight min(1, a/ aaaaa//lmmmmll// ||=mm is a truncation of the inverse bonus, where a is threshold parameter that shall be optimized later. When Im,r is not explored much, we have a large exploration bonus || (low confidence). Hence, the algorithm will put small weight on it to avoid large regret due to stochastic noise and misspecification. When |.m.elly=. is small (high confidence),
H-LINUCB puts large weight on it, and it can be as large as one [He et al. 2022 We note that using this weighting could have a significant negative impact on the performance if we are not careful. Several recent studies show that we can incur regret of Ódd =v/T) and (dd + edT) for misspecified and corrupted linear bandits, respectively [Lattimore and Csaba, 2020 Takemura et al., 2021 Foster et al., 2020 He et al., 2022 However, a direct application of an algorithm designed for misspecifhee//crrppte linear bandits to our setting can lead to linear regret when (()) This is significantly worse as compared to naive independent learning, which always achieves sub-linear ÖdM /T) regret.
We emphasize that the condition (t < r) in Line 18 is crucial to avoid linear regret for H-LINUCB in the regime of large E. For example, for O(1. T. Algorithm | ineurs Ö(dMT) regret, which is linear in term of MT. Furthermore, Theorem 4.3 indicates that there exists an instance of M-MACCB such that any algorithm incurs at least R(dM (T) T) regret. Then, each agent playing OFUL. independently would be enough to achieve an optimal (dd (T) regret. This suggests that we get a tighter upper bound we cease collaboration; we discuss the stopping criterion and the choice of F in Theorem 4.2
Communication protocol. We use star-shaped communication network where M agents can in- teract with central server [Wang et al. 2020 Dubey and Pentland| 2020). Each agent communicates with the server by uploading and downloading its data but does not communicate directly with each other. The communication will be triggered only if any agent has enough new data since the last synchronization round. Finally, we assume no latency, or error in the communication between the central server and agents.
'The technique of using the exploration bonus to control misspecification is also used in Zhang et al. 2023 Takemura et al. [021]. /Foster et al. (2020) give guarantees for when the misspecification level is unknown. The CW-OFUL algorithm of He et al. 2022 has Ö(dvT + dC) regret, where C' is the total amount of corruption. Setting C = eT', where is the level of misspecification at each round, gives us D(dVT+edh regret.

---

Remark 4.1. Wang et al. [020] show that DISLINUCB can rely on old data and produce nearly optimal policy without much communication, only incurring logarithmic factors in the final regret. H-LINUCB has the same communication cost of D(ML..))) as DISLINUCB, which does not depend on the horizon
When an agent uses data from other agents, due to the dissimilarity, we need to adjust our confidence bound to make sure the true linear parameter Om lies in the defined ellipsoid with high probability. The next result shows how to construct such a Confidence Ellipsoid.
Lemma 4.1. (Confidence Ellipsoid). With probability at least 1 Md1 Md2. for each agent m E [M]. 9m lies in the confidence set.
Cm.tt (0 EERR 110m= 1 -
S 31
V.n.
where
VA + +aM++ V
/dlog
1+Mt/(Ad) b1
ffor t <
Be
V v dlog
[-(/((dd) 62
for 2
Note that the result above provides two separate confidence bounds for 0m one for the period before round and the other one for after round r. Before round т, agent will use all the data from other agents to construct Cm,t- The proof follows by first bounding 0m.. 0m VA,)(A)
as
0m. -0n. (A) Regulurization term
Σ Pylm 1m
Wa A T - 0m)
13
Voml(()
Noise term
1 Disiisiimillartt term
Here, Jn is a bounded regularization term, I3 is noise term that can be bounded by self- normalization lemma Lemma|[C.4) Finally, the dissimilarity term In is bounded from above by az Mt using the
definition of dissimilarity |10, 0m.! S e, and applying a similar argument as He et al. [2022] and the
choice of the weight Wm,t min(1, (1, a/ /////mmmmlllll )- For the phase after round т, we use the same
argument as Abbasi- Yadkori et al. [011 to construct the confidence bound.
Next, we present the group regret upper bound of Algorithm | up to round T.
Theorem 4.1. Given Assumption 3.1 T 2 any T ST, T, and 8₃ O. setting À A= 1 and </d
eMTT in the upper bound of 3t on the confidence interval according to Lemma 4. E [T', and setting the synchronization threshold D r log(Mr)/ (dM), we have that with probability at least 1 - 06, the group regret of Algorithm
up to round r, is bounded as
R(M,T) S 20v2 (dVMTe, + =dM
where &, = log (e/d)
Theorem 4.1 shows that Algorithm 1 iinuurs (dd MT) regret in the first term (which is the same order as a single agent playing for Mr rounds) plus a penalty of using the data from other agents in the order of () The regret ('d Mr) is unavoidable for any regime of e, and this rate is known to be optimal in the case of homogeneous multi-agent. Since we use the technique from He et al. 2022] to handle the dissimilarity. the corruption amount of each round is E, and a total corruption of EdMT when the central server allows collaborate up round To the best of our knowledge, we are not aware of any UCB-based algorithm for misspecified linear bandits in the setting of infinite arms. We expect that employing misspecified linear bandits algorithm would achieve a regret of (dV/MT + cVMT), which is tighter by factor of Vd. It is worth noting that the CW-OFUL algorithm He et al. [2022) is designed for handling corruption, whether it can achieve ÖddV + eVdT) in a misspecified setting remains an open question.
We now present our main result giving upper bound on the group regret of H- H-C.
7

---

Theorem 4.2. Given Assumption 3.1
T let == 1,
62 MaT in the upper =MTT
dd 81
bound of 3g on the confidence interval (see Lemma 4.1 Vt E [T] ==t== min( 2ズ I.T,, and let the synchronization threshold D = T log Mr)/(dM) Then, the expected group regret of Algorithm bounded as
E [R(M - 320 MT + min EdMTT dMMV) log (MT).
Here, is the maximum round that the central server allows communication. After that, all agents switch to independent learning. By choosing т min( I, agents fully cooperate in the regime E E [0, /2T T S Zez. and gradually reduce T as increases from /2T to +00. This is important for avoiding linear regret since when is large, most of the regret comes from the edMT term and dominates the dvM7 MT term. The condition on 6 discards all of the synchronized data. In the extreme case, when E > 1, there is no collaboration happening due to the condition in Line 18 failing every round. In other words, H-LINUCB behaves like IND-OFUL.
In the other extreme case, when e = 0, all agents solve identical linear bandits. The weight in Line 15 always evaluates to its minimum value of 1 for all & [7] since EMST for all rounds. Therefore, the reset condition Line i never triggered and H-LINUCB behaves exactly like DISLINUCB, achieving a regret of (dv MT), which is optimal up to some logarithmic factors.
/d - +o0 We have 1 < E?
Theorem 4.2 suggests that the upper bound of H-LINUCB is tighter than IND-OFUL for all
Remark 4.2. Ghosh et al. 2023] also propose a personalized algorithm (PMLB) for the heteroge- neous multi agent linear bandits; however, our problem setting fundamentally different than that of Ghosh et al. [2023] They consider a finite action set and impose strong distributional assumption on how contexts are generated, i.e., the stochastic context Zi,t for each action and at each round t is zero-mean and forms positive-definite covariance matrix. In stark contrast, we consider the adversarial setting where the context set is adversarially generated at each round (and thus, the associated action set can be infinite and arbitrary). This renders the algorithm and guarantees of Ghosh et al. [0033] inapplicable in our setting and, thus, requires a completely different treatment. Those assumptions of Ghosh et al. (2023) are crucial for them to obtain the OTT/44) bound (for = 0). We note that this bound is not coommation-theorttictn
possible in our adversarial setting; the minimax lower bound in such settings is 2( ((VT) (Theorem 4.3
4.2 Lower bound
In this section, we present a lower bound result for the e-MACCB problem. We denote RA (M, as regret of algorithm A on problem instance I of M agents run for T rounds.
Theorem 4.3. Let I(z) denote the class of e-MALB problem instances that satisfy the Assump- zt with d T,
tion 3.1 Then for any d, d,M, E
2 48 S T, VE 2 O, we have the following,
inf sup RA = Ω MT + min {cMT, aM (EMT,aMVT))) A IEI(e)
The first term is straightforward observation that solving an e-MALCB is at least as hard as solving a single linear bandits for MT rounds, or M agents solving identical bandits for T rounds. The second term suggests that we pay additional regret of eMT for small e E [0, A. and ((dMVT) for a large e 2 d VT
We note that M(dM VT) is also the lower bound of IND-OFUL when each
agent incurs regret of at least ((dvT). We believe that the analysis of the lower bound could be tightened by using the arguments from misspecified bandits literature, achieving a lower bound of O(dvMT + min(ev VdMT, vT)).
The lower bound suggests that our upper bound is tight up to logarithmic factors in the following extreme regimes, (i) E E [0, 7 where R(M,T) = @(dvMT); (ii) E E 17 +o0], where
R(M, T) = ((dMVT) In regime (i), all agents solve tasks that are similar to one another, yielding the highest collaborative gain. In regime (ii), tasks are highly dissimilar, H-LINUCB turns off the collaboration and lets agents solve their own tasks individually.
8

---

Ind-OFUL
DisLinucB
H-nnCC
40000
30000
Group Regret
20000
10000
2500
5000
7500
10000
0
2500
5000
7500
10000
2500
5000
7500
10000
(a) 0.0
(b) - 0.00067
(c) 0.00268
50000
Group Ragrot
40000
30000
20000
10000
2500
5000
7500
10000
0
2500
5000
7500
10000
2500
5000
7500
10000
(d) e 0.27
(6) = 0.68
=076
Figure 1: Simulation on synthetic data with M 60, d = 30, T 10000.
Finally, in the regime that E VMT vT our results illustrate the interpolation between two extremes. In this regime, our upper bound presents a gap of d in the dissimilarity term EdMT compared to eT in the lower bound.
The key idea in the proof Theorem Lemma C.TI wherein we extend the result from (single-agent) linear bandits to heterogeneous multi-agent linear bandits. Here, we give the lower bound result without any constraints on the communication. hence, this is also the lower bound of the H-LINUCB algorithm.
based on an information-theoreti lower bound of
5 Numerical Simulations
In this section, provide some numerical simulations to support theory. Our goal is to address the following question: how does H-LINUCB perform three different regimes of dissimilarity: (i)
E E
ATT (ii) E VMT: )) (iii) ε [ +
We compare the performance of H-LINUCB with that the following two algorithms: (a) In- dependent Learners (IND-OFUL), wherein each agent independently runs OFUL algorithm of Abbasi- Yadkori et al. [20I]], and there no communication between agents (zero collaboration), and (b) DISLINUCB, for which we use the implementation of Wang et al. 2020 without any modification.
Simulation setup. We generate the e-MALCB problem for M = 60, d 30, T 10000 via the following procedure. We first choose a value of in each of the three dissimilarity regimes. Then we create the linear parameters {fm J.M,,
follows. Let u, {um, J be random vectors with unit norm. set O., = e u + Um, where e is constant in the range [0, - e). This guarantees |0,, S and |00 0اl < for any two agents j, At each round, for each agent, we create new decision The random noise is sampled from
set with a size of 50, each action is random and normalized the standard normal distribution, 17 A0, 1). We run each experiment 10 times, then report the

---

group regret averaged over the runs and the confidence intervals in Figure 1 Our code is available here: https:///iithbb. com/ anhddo/hlinloe
Results and discussions. In regime (i), where the level of dissimilarity is small, plots (a) and (b) show that H-LINUCB retains regret comparable with DISLINUCB.
In regime (ii), plots (c) and (d) illustrate the interpolation between the two extreme regimes.
In regime (iii), plots (e) and (f), DISLINUCB incurs linear regret, H-LINUCB has the same rate with IND-OFUL. This illustrates that collaboration brings no benefit when the dissimilarity is high.
Conclusions
In this paper, studied the heterogeneous multi-agent linear contextual bandit problem. We formulated the problem under the notion of E-MALCB, and provided the upper and lower bounds when e is known. We showed that our results provably optimal in the regime where tasks are highly similar or highly dissimilar. Finally, we validated our theorctical results with numerical simulations synthetic data.
A natural avenue for future work would be to close the gap in the regime s E ( VMT vT Another research direction pertains to designing adaptive algorithm when is unknown. Such an algorithm would be practical and flexible enough to apply to a wide range heterogeneous multi-agent bandit problems. We are also interested in extending this work to more challenging setting such as Reinforcement Learning.
Acknowledgements
This research supported, in part, by DARPA GARD award HR001 12020004, NSF CAREER award 194321,, funding from the Institute for Assured Autonomy (IAA) at JHU, and the Spring workshop on "Learning and Games" at the Simons Institute for the Theory of Computing.
References
Yasin Abbasi-Yadkond Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Djallel Bouneffouf, Irina Rish, and Charu Aggarwal. Survey on applications of multi-armed and contextual bandits. In 2020 IEEE Congress Evolutionary Computation (CEC), pages 1-8. IEEE,
2020. 2
Emma Brunskill and Lihong Li. Sample complexity of multi-task reinforcement learning. In Uncertainty in Artificial Intelligence, page 122. Citeseer, 2013.
Leonardo Cella, Karim Lounici, Grégoire Pacreau, and Massimiliano Pontil. Multi-task representation learning with stochastic linear bandits. In International Conference on Artificial Intelligence and Statistics, pages 4822 4847. PMLR, 2023.
Niladri Chatterji, Vidya Muthukumar, and Peter Bartlett Osom: A simultaneously optimal algorithm for multi-armed and linear contextual bandits. In International Conference on Artificial Intelligence and Statisties, pages 1844-1854, PMLR, 2020.
Ronshee Chawla, Abishek Sankararaman, and Sanjay Shakkottai. Multi-agent tow-dimensional linear bandits. IEEE Transactions on Automatic Control, 2022. 2
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 208 214. JMLR Workshop and Conference Proceedings, 2011. 1. 2
Yihan Du, Longbo Huang, and Wen Sun. Multi-task representation learning for pure exploration in linear bandits. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardr, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference
10

---

Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 8511-8564 PMLR, 23-29 Jul 2023.
Abhimanyu Dubey and Alex Sandy Pentland. Differentially-priie federated linear bandits. In
H. Larochelle, M. Ranzato, Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 6003-6014, Curran Associates, Inc., 2020.
14
Dylan Foster, Claudio Gentile, Mchryar Mohri, and Julian Zimmert. Adapting to misspecification in contextual bandits. Advances in Neural Information Processing Systems, 33:11478 1489, 2020.
Claudio Gentile, Shuai Li, and Giovanni Zappella. Online clustering of bandits. In International Conference on Machine Learning, pages 757-765. PMLR, 2014.
Avishek Ghosh, Sayak Ray Chowdhury, and Aditya Gopalan. Misspecified linear bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017. 3
Avishek Ghosh, Abishek Sankararaman, and Kannan Ramchandran. Multi-agent heterogeneous stochastic linear bandits. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2022, Grenoble, France, September 19-23, 2022, Proceedings. Part IV, pages 300-316. Springer, 2023.
8
Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu. Nearly optimal algorithms for linear contextual bandits with adversarial corruptions. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave. and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. 6
15
Jiachen Hu, Xiaoyu Chen, Chi Jin, Lihong Li, and Liwei Wang. Near-optimal representation learning for linear bandits and linear rl. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 1349-4358. PMLR, 18-24 Jul 2021.
Ruiquan Huang, Weiqiang Wu, Jing Yang, and Cong Shen. Federated linear contextual bandits. Advances in Neural Informtionn Processing Systems, 01-27057-27066 2021. 2
Nathan Korda, Balazs Szorenyi, and Shuai Li. Distributed clustering of linear bandits in peer to peer networks. In International conference on machine learning, pages 1301-1309. PMLR, 2016.
Tor Lattimore and Szepesvári Csaba. Bandit algorithms. Cambridge University Press, 2020.
3
23
Chuanhao Li and Hongning Wang. Asynchronous upper confidence bound algorithms for federated
linear bandits. In Gustau Camps-Vallss, Francisco J. R. Ruiz, and Isabel Valera, editors, Proceedings of The 25th International Conference Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 6529-6553, PMLR, 28-30 Mar 2022.
Lihong Li. Wei Chu, John Langford, and Robert E. Schapire. contextual- approach to personalized news article recommendation. Proceedings of the 19th international conference on World wide web WWW 10, 2010. doi: 011144/17726901177777 2
Shuai Li, Claudio Gentile, and Alexandros Karatzoglou. Graph clustering bandits for recommendation.
arXiv preprint arXiv: 006.600.05999 2016. 3
Shuai Li, Wei Chen, Shuai Li, and Kwong-Sak Leung. Improved algorithm online clustering of bandits. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAI'19 19, page 2923-2929. AAAI Press, 2019. ISBN 9780999241141.
Kanak Mahadik, Qingyun Wu, Shuai Li, and Amit Sabne. Fast distributed bandits for online recom- mendation systems. In Proceedings of the 34th ACM international conference on supercomputing
pages 1-13, 2020. 2
11

---

David Martinez-Rubic Varun Kanade. and Patrick Rebeschini. Decentralized cooperative stochastic bandits. H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, Buch E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. 2
Aritra Mitra, Arman Adibi, George J. Pappas, and Hamed Hassani. Collaborative linear bandits with adversarial agents: Near-optimal regret bounds. In Alice H. Oh, Alckh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. 2
Ahmadreza Moradipari, Mohammad Ghavamzadeh, and Mahnoosh Alizadeh. Collaborative multi- agent stochastic linear bandits. In 2022 American Control Conference (ACC), pages 2761-2766. IEEE, 2022. 2
Michael T. Rosenstein. To transfer or not to transfer. In NIPS 2005, 2005.
Paat Rusmevichientong and John N Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395 411, 2010. 2
Marta Soare, Ouais Alsharif, Alessandro Lazaric, and Joelle Pineau. Multi-task linear bandits. In NIPS2014 workshop transfer and multi- task learning: theory meets practice, 2014. 2
Kei Takemura, Shinji Ito, Daisuke Hatano, Hanna Sumita, Takuro Fukunaga, Naonori Kakimura, and
Ken-ichi Kawarabayashi. A parameter-free algorithm for misspecified linear contextual bandits. In International Conference on Artificial Intelligence and Statistics, pages 3367-3375. PMLR, 2021.
Yuanhao Wang. Jiachen Hu, Xiaoyu Chen, and Liwei Wang. Distributed bandit learning: Near-optime regret with efficient communication. In International Conference on Learning Representations, 2020.
15
Zhi Wang, Chicheng Zhang, Manish Kumar Singh, Laurel Riek, and Kamalika Chaudhuri. Multitask bandit learning through heterogeneous feedback aggregation. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 13-15 Apr 2021.
PMLR,
4
Jiaqi Yang, Wei Hu, Jason D. Lee, and Simon Shaolei Du Impact of representation learning in linear bandits. In International Conference on Learning Representations, 2021. 3
Jiaqi Yang, Qi Lei, Jason D Lee, and Simon S Du. Nearly minimax algorithms for linear bandits with shared representation. arXiv preprint arXiv:2203. 15664, 2022.
Weitong Zhang, Jiafan He, Zhiyuan Fan, and Quanquan Gu. On the interplay between misspecifi- cation and sub-optimality gap in linear contextual bandits. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 41111-41133 PMLR, 23-29 Jul 2023. 6
12

---

A Proof of Upper Bound
A.1 Proof of Lemma 4.1
Proof. We prove that the true parameter of each agent lies in the Confidence Ellipsoid with high probability, In particular, we prove such results for periods, for round and & 2 We denote o1, 62 as the probabilities such that true linear parameters outside the confidence ellipsoid for the period of t 7, and t 2 T, respectively.
For the round < т, let te be the last round that synchronization occurs, where i, < Then each agent's s statistics can be divided into two parts, its own data and the pooled data from other agents since round tg. Specifically, for an agent m, at round t, we have the following for Vn,t, bm,
Vn,t AI +
dm m. +
1=1
igfm k=1
m
Wm x m. Um. +
Wi Vi.k
k=1
i 1=1
We then have the following for 0m,ts
mm = V.m.t bm,t
m,
Wm, TTn k. +
Wss Wi,
sittrr 1m
Wm, Wm, Km,k pmm + kmm,k) +
WitTi (1T + me.k)
= m.t
(gfor 1=1
V-1
Σ
Wm, mm k
U.s.A.T.,, pm
m.f
ipttr A
V-1
W W. (0, 6m)
m.t
k=1
---1
Wm Mm. &
Wi &
Notice that the summation in the first term is the covariance matrix Vm.: but missing the regularization term AI; thus, the first term be simplified as On Om Applying triangle inequality,
have the following for [0m,.
6m Vm..
10mm Om Vin.
A A10mlllm mit I R:Rgulaaization term
Σ
Wi, Wi ,. (0; - 0m)
smf 1=1
V
Ia Disimmiilyrry
Wm. mm
w 20
s 1=
m.
No:No term
For the regularization term I, it is upper bounded by.
A
h > 100m Iv== 5
10mll2 Vā 11m0l11 Vλ.
Amin
V2/2 m,
13

---

For the dissimilarity term I2, we have,
1
Σ
wir W. - 6m))
kylm Rmm
M
|000,.-T...2 - mmm v
Wi,h | mm) ||
M
T 0mlla
k=1
S aEMts,
where we use triangle inequality in the first inequality, the second inequality holds since Wm.t S a/Il=m, lly. by the definition of wm,ts the last inequality holds due to the bounded parameters assumption and the e-MALCB definition (see Assumption 3.1 and Definition 3.1
To bound term 13. denote vector Fm. Lmm and the random noise 7m,,t - mm U'm, We have Wm, I 1, therefore. Mm, is 1-subGaussian. Furthermore, we rewrite the covariance matrix as Vm,t Al + Σ e= Im. T Eifm Eke & term /3.
We then have the following for the noise
I3
E mm Tma,
T Ti.k
ifmm Toml
F-1
det (Vm,.)
1/2
det deo
log
81
1 + Mt/(Ad))
I d loo
51
where we apply Lemma C.4 in the first inequality, Now, putting these three terms together, we have the following Confidence Ellipsoid bound for round <<>.
| - 8m Pmmllyn S <(VA+ + d
1 Mt/(Ad)
81
We now turn our attention to the round 2 Since agents switch to independent learning, we follow the same argument for confidence ellipsoid as in Theorem 2 Abbasi Yadkori et [2011]. and get
1 11 t/Ad))
VX+ dlog
82
Finally, we complete the proof by taking union bound over all agents.
A.2 Proof of Theorem
give an upper bound the pseudo-regret, Tm,ts in the next proposition. The proof fol standard arguments for linear bandits; most of the arguments can be extracted from Wang al. 2020 Dubey and Pentland 2020).
Before proving Theorem 4.1
14

---

Proposition A.1. The pseudo-regret obtained by any agent at round t. is upper bounded as Tm,t 23 min (I, [IFFm.lllm..
Proof. Recall that an agent makes decisions optimistically: (Im,, mm,,)
arg max (s.0))Dm..a XCm,
Let a, denote the optimal action at round t of agent m, i.c., Fm,e arg max æ Om. xEDm,
We then have the following for the pseudo-regret
Fmm Om - Fmmt T 0m
Fm.t =
Fmmt "m,t Fm,t 7m
(Since (Im,,t 0m,,) is optimistic)
-Im (0mmt - 0m)
-VVm,d// Tmmtt Voll2 (0m,t 0m))
11/2
(Vm,t &
[1mmt v=! Om. Om Vimi IIyme
GGuuch-SchwaazZ inequality)
(10mm Bllel + 110m,t 6m llvm..)
(Triangle inequality)
23, [mmelllym
(Since On, 0m,t E C.)
$ 23, min (1, 1,
where the last inequality is due to the fact that 3, 2 and that suboptimality is no more than 2.
We now proceed to prove Theorem 4.1 The proof technique follows the analysis of group regret in Wang et al.) [2020) and applies the arguments from Theorem 4.2 He et al. [2022 to handle the dissimilarity.
Theorem A.1 (Theorem 4.1 restated). For given T, and 7 T, we set D log log(M))/(dM)) and 3r, Vt E [T] according to Lemma 4.1 then, given Assumption 3.1 with probability at least 1 Md,, the group regret Algorithm
up to round is upper bounded
R(M,7) S 4V (VVAMM((()) 1.5 aeVd(MT)) 1.5 VE, + dVM + VAdE. + edMTE.
(dE)) + o +dV
where &, = log upper bounded as
1+Mt/((d) 61
Furthermore, we choose À = 1, a eM7'
vdd
then the group regret is
R(M,7) S 20 (dv 20 edM
We refer to this group regret as the "collaboration" regret, and denote it as Reolla((M. T).
Proof. Let P be the total number of synchronization rounds, then, we index the synchronization matrix Vayn for P epoch as [Vagn.p) and define V, = AI + Vayn.- Observe that det(Vo) det(A/) = d and det(Vp) < (trace(Vp)/d) < (A+ MT MT/d)d. Therefore.
det(Vp)
MT
log det(Vo)
S dlog 1+
Xd
By telescoping, we have that log det(Vp) det(Vo)
Ep= log det(V).
dct(Vp-1)) Therefore, we have at most
R = [dlog(1 + Mt)] epochs such that log det(V 1)
dot(l)))
2 1; otherwise, it violates the condition
15

---

in Equation ①T) WLOG, we use logarithm base 2 for the determinant ratio. This implies that for all but R. epochs.
de)(V)) v
$ 2,
(2)
dct(Vp-1)
We call the epochs satisfying Equation
good epochs. We imagine single agent play-
ing MT 1) actions F1.1; 121.... 1. M,r sequentially. Let Wm, Al Di=1 Σ Wi, + + " be the covariance matrix of this imaginary agent when it gets t- If 2m, belongs to good epoch, say the j-th epoch, we have the following:
Fmm.ellymm
det det( det(Vm.tt
det(V,) det(V,-1)
1 S
S
S V2,
Em,t Wm
where the first inequality due to the fact that Wm,t & Vm,es and the second inequality follows from Lemma C
Now, applying the Proposition
we bound the pseudo-regret Tm, of these good epochs follows:
Tm,t I 28g min (1,1(mmeellvmt)
det(Wm.. det(Vmm.)
< 28, min
1, 1, V
- 2V223, min
(1, (L.llmmllllw.tt)
where we use Lemma C.2 in the second inequality, and Equation 3 in the third inequality.
Let (g,
r) be the group regret of these good epochs up to round Suppose P ggood contains all the good epochs, and B, contains all the pairs (m, t) belonging to epoch We have
Rgoodd (M,
Σ
Σ
Tm,1
pe BePaaos Roood (m,t)EB,
Σ
Σ
2/233-1 min (1, [1.1lmm.lllwa
pEP (m,t)EB,
2V23r-1 min (1, lIl.m.elllw!
pEP pePg good (m. !
I Rooudss of good epoch with wm,1=1
Σ
2/23,-1 min (1, [1, (llem
Pood (m AyA.M.
1x:Rounds of good epoch with um,e<1
where in the last equality we split the summation two cases: Wm,t 1, and Wm.t <.
For term J, we consider all the pair (m, t) in good epochs up to round 7 such that Wm.t = 1; assume that have total of such K pairs, and these pairs be sequentially listed as {(m1, (mz, ..., (mx, [x)]. With this notation, for & K, we construct the auxiliary covariance matrix Am, XI E1- Ima me Thus, we have W Wm..., Am,to which implies || & -1 1, 11! m,.Fs
16

---

We now have the following for term I
1= Σ
Σ
2V23, min (1, 1mm W
pt le Food
(m, Aam,.
- min
1in
1. (1.1/=mattellnn llwaa
km
2V min
1, 1, llaai
K
22228 -188,,1VVM,.. VT
min
1, LEller (isil
1=1
det(Vp) det(VV)
$ 48,
2M
Mr
I <4V28, 1
dM 1
Ad
< AV28,-VVdMTE,
where in the second inequality we use Cauchy Schwarz's inequality and the fact that K S Mr, and Lemma C.3 in the second inequality.
For term 12. since we consider the case such that Wm,t < 1, thus, by the definition wm, we have Wm,t || llv= 1. Therefore, we have.
= 1v2 Σ PE Proud
Σ
min (1, (L ll
Wm.e 2mm mml a Wm,el "mm,elIFmm Fmm, Wwmtt
2V2
Σ
Σ
min
B,
Im, ll mit
PE P. good (m, (m.1))B,,... Bm,,))Bp.W....
min 1, 1,
a
PEP good PEPdood (MW
where the last inequality follows from Equation
Similarly what we have done with 41, we consider all the pair (m, t) in good epochs up round such that Wm, < 1; we assume that we have a total of such K pairs, and these pairs can be sequentially listed as {( f1), (mz, f2),.... (mx, fx)). Furthermore, we define F,n,t / ummtt and construct the auxiliary covariance matrix,
W Wm. = X
Wmy Jn Tmn Fe = AI + Em To TT T
A
Thus, have W T. > W E. which implies [| 1l 5 l
mish
17

---

Therefore,
k
1 4
min
1.Br-1W0mell I Te I Wimee
k=1
K
min
1 3--1/ (1 Br-1//0)lll Wmn I Emast li minis
km
min (1. I. liiv
$ 4(1 + By 1--1/a)
Σ
#=1
Mr (1+
< 4(1 + 8 2
Ad
< 4 B--1/a)dEr
where we use Lemma C.3 in the fourth inequality. Putting the bounds for 1 and I2 together, we have
R good (M, + 4V28,- + (1 B--1
de.
=4 S--V + dc, a
Br- der
Plugging 8--1= Vt+ a + v Vilog( 1+Mr/A b1
the regret of the good epochs is bounded as
(M S VAdMTE, + aE a VE, dv dVMTE, + VAder + edMrE, + (dE,) 1.5
Now, focus the epochs that not good, which do not satisfy Equation one such epoch, and let to be the first round and n be the length, respectively, of the epoch Recall that the beginning of each epoch, agents' covariance matrices are synchronized, i.e.
Let p be
Vm,to = Al + Vayn, Vm E [M]. We can then bound the regret of the (bad) epoch as follows.
tatn
Read ( (M,p) s 2
Σ min (1, ||.F.mmmlllvl!
to
1,, Il ell Vonl
23
Σ min 1=to
m=l
det det(V (Vmmtott
23,-1 Σ
log
det (emm)aa))))
m=1
where we use Schwarz's 's inequality and Lemma
C.3 in the second inequality.
Lets say the synchronization is triggered on round to + n + 1, i.., for one of the agents we have that
(n + 1) log det(Vm.to-n44)) > D. Since n log det(Vmm.to=n) D for all [M], for this bad epoch det(Vm...o)
det(Vmn.g))
(i.c., from round to to round to + n), we can bound the group regret as
Road (M, p) S 28.-IMVD.
As we argued earlier, since det V,, < (A y the bad epochs are rare, i.e., there are at most R log + afT]] (otherwise, if det(V,)) dct(V,-1) > 2 for more than R rounds, then the condition of Equation I is violated). Setting D = bound above,
and plugging 8,-1 into the
Road (M, 2R3,-1MVD
2 de (VX+ (EA+ GEMT+ vdg.) MVD)
2 (AdMM((Ss)25 +uvvd(MTSs)L +d........................ +de
18

---

We finish the proof by putting the regret of the good and the bad epochs toeeherr.
R(M,T)- R Roood (M, + Road (M
4v VAdMT((S) ).5 + aEVd((M)) VE, + dVM + VAdg. edMTEr (dE,) + a + dv MTE))
a
A.3 Proof of Theorem 4.2
Proof. Setting 81 = 62 = 1/(M))), then the group regret caused by failure event, which does not
satisfy Lemma 4.1 most MT (Mo + M = O(1). Thus, we mainly consider the group regret when Lemma 4.1 holds.
From round onward, agents switch to independent learning mode, this is the group regret from round T to the end, we denote it as (M, T). Furthermore, for round t 2 т, we have Vn,
AI + E Imm.smm. m, as the gram matrix which only contains agent's 's data.
Applying Proposition A.I
we have the following
Rind Bind(M,2 (M,T)
Σ
Σ
2 min (1, ||
M
T
< 2
BTVT
T
Σ min
1, 12 Vintt
m=1
M
1 1 (Add
) VT -T 2d (1+
T Ad
2 2
Σ
VX+ dlog
82
m=1
< 442MdvT-T22 TÊT,
where we use Cauchy-Schware 's inequality in the first inequality, and Lemma 4.1 in the second inequality. Combining with the regret from the beginning up to round 7 from Thcorem 4.1 we have
RRM,IT T) = Reollaa (M,T) + Rind (M,T)
< 200/ dd + EdMT + dM -T E
We notice that Equation (4) has the second term that is linear in term of Mr. To avoid linear regret, the choice of needs to adapt to the dissimilarity level E.
For the last two terms, by Cauchy-Schwarz's inequality, we have adMr + dMVT-7 < d.M 7( + + -T)), this term can be optimized by setting = +/2 We need to restrict (1 - 2..7) since can not exceed T. In other words, all agents can collaborate up to round min (1)
Next, we consider the following two cases:
Case 1: For f - T, we have that edMr + dM - < VT.
dMVT, and edMr dMr < dMVT. Thus,
Case 2: For E
2 > T. we have T. This implies that edM + dM edMT. We also
have edMT 1 ddM due e T. V2
Notice that, in both cases, sdMT + dM /T - is evaluated small as edMT and always be upper bounded by 2dM /T. Therefore, in Equation (4). the summation of the last two terms of the group regret is upper bounded by min(sdMT, dM VT).
19

---

By the choice of 81, 62. X, and assume that 2 1, we can upper bound &r S 4log(MT). Therefore, we have the following for the expected group regret
E [[)( - 20 MT 2 &
S 320V2 dv MT MT + MiinfedMT,dMMV (MT)
B Proof of Lower Bound
B.1 Proof of Theorem 4.3
Before proving the theorem, we give a formal definition of E-MALCB problem for p-norm, Definition B.1. Given an instance of mulli-agent linear bandits, it belongs to the class of p-norm E-MALCB, which denote as IE)E), if for all i,j [M], ||0, 0gllp S
To prove Theorem 4.3 we use the results of the two following lemmas on max-norm E-MACC instances.
Lemma B.1. Iso (c) be the class of max-norm e-MALCB instances that satisfy the Assumption 3.1 For E 2 0, we have the following.
inf sup RAI(M,T) = MT).
A IEI
Lemma B.2. Let Ino (c) be the class of max-norm e-MALCB instances that satisfy the Assumption 3.1 d
Assume d < 2T, S T. For = 2 O, we have the following,
48
RAI((M,T) Ω min foinffemn {MMTV,, dd
inf sup IEIa(e)
Proof of Theorem 4.3 Combining the results of Lemma B.1 and Lemma B.2 we have the following results for the class of max-norm E-MALCB, for 2 0,
inf sup RA,,(M,,T Ω (dVMT min (SNTVV,aNVT) A (E)
In addition, || $ implies ||>|| I EVd, therefore, Ixo(E) S Iz(EV/d. other words, for E 2 0,
RAI((,,))= = (dVMT min min (EMTTaMNTT)
inf sup RAI((M,TT inf A IETa(s)
sup IEIN (+t)
A
Proof of Lemma B. In this lemma, we prove that solving any c-MALCB instance for T rounds at least as hard as solving a (single-agent) linear bandits for MT rounds. We prove the lemma by contradiction, which is based on linear bandits lower bound of Lemma C.1 (e') C (s), for e' e. This implies, for 2 O, inf sup RAI( TETx(())
We have that
> inf sup RAI,M.
A TeTx
We completes the proof by proving inf supreT=< (0) RAI = 1 (dVMT))
Now, we assume there exists an algorithm which achieves SUPIEI> (0) RAI((M,T). <
M
16.3
We observe that (0) is the class of multi-agent solving exactly the same linear bandits problem.
We simulate the algorithm B a single agent linear bandits for MT rounds by the protocol of M agents solving an identical linear bandits for rounds. Therefore, if we have RA, T) <
d MT then we also achieve (M.((M))
MVMT which contradicts Lemma C.1 Thus, we have 16.3
16v3
suPrez (0) RAI((M,) 2
dVMT 16/3
which completes the proof.
20

---

Proof of Lemmal B.2 We extend Lemma C.1 to multi-agent linear contextual bandit by constructing the following max-norm E-MALCB instance.
Max-norm E-MALCB instance. The set of linear parameter of M agents {0mm Jm belong to d-dimensional hypercube On E {[te] where E [0, v/al Let D = {ar E IR | S } be the action set given agents at every round. The reward when agent m picks action is defined as Tm.. = 0, + Tm,, where the noise samples from a standard normal distribution, 1mm.. ~ ~N 1).
We first verify if the instance satisfies the Assumption 3.1 It satisfies the context assumption since we also restrict the context vector to in the unit ball. It also satisfies the ||0m. s assumption because we restrict
10, //al. Finally, 7m, ~ (O 1) is I-subGaussian distribution. This instance belongs to oo (2e) since |0;; - 0, S 2e for all i E [M].
Now, proceed prove Lemma B.22 Let {0n JM be set of parameters of the max-norm E-MALCB instance. For brevity, we omit the commas in the subscripts when it is clear from the context, e.g., 0ms 0 or Temi &t,m, Vt [T', m E [M] [d]. Given E [M], [d]. we define the stopping time Timi = T A minft E Zomi 2 t/d}, and the function Umi(z) = Zemi z)2.
We then have following result for Um)(
Timé
Tmni
Tini
4T
Umi(1 (1)
Σ
Ttmi
d
Trms
2
+ 2.
(5)
Let zn be the optimal action of agent m. We then have the following for the group regret
T M ΣΣΣ
R.(M, = E
Ro. mm mm
Itmmimmi) bmi))
E E 1g ar
Tems sigu(0mi)
evd
T
M
27
E Beo.. J
Timi sign( sign(Omi)
Vd
evd
M E (0m pM
Etmi sign (ggn(mm))
Vd
m=
Omn where we use the fact that optimal action oi = [[@0m.]]
Omd 1|0m
which a unit vector and has
the same direction with 6m. the first inequality holds due ||
< 1.
Now, let {0', LM be another set of linear parameters that are different at only one coordinate of
m==1- Specifically, fix g E M) [d] the linear parameter of only one agent compared to {0,, AM
we have fg = 8/,'' otherwise, 0x.j = 8kyy for (k,j) * (g,1), Vk E [M], E [d]. To simplify the notion, we define 2, & as Mdddimennionaal vectors, where & Ø' E {#e]Mr That is, 4 &' represent {0m J. 10' IM Jm= respectively. We let IP and IP' be the law of Uzi(z) w.r.t. the interaction of the multi-agent linear bandits induced by Φ &,, respectively. We then get
4T (
Eg [Ug. Eq [T)
+2)
DKL (PI[P')
V
2 Ex (Ug
8
4T
+
E
Σ
x
2
E
4T
T
> Ex (Uni((1)
+2
+1
2
d
T
3/2
2 Egr (1)( - 4/33
d
21

---

where the first inequality holds due to Lemma C.5 and Equation 5 the second inequality follows the stopping time arguments from Lattimore and Csaba 2020). the last inequality holds due the assumption that d s 2T. Then,
T d
3/2
Es (Ug((1)) + E.g (Ugr(-1) 2 Es (Ugi(1) + (-1
4v
Tax
3/2
2
Tgi
2 Egi
Av36
d
1=1
2T
T
3/2
T
2
4v3E
where the last inequality holds for E [0, 4/3 V 41 this satisfies the requirement E [0, 1 Val of
1
the instance construction due to the assumption that di T. Furthermore, we denote & P-mi ( (Md - l)-dimensional vector, which is obtained by excluding Pmi from vector Φ. Let RR (M, be the regret w.r.t 4, and applying randomization hammer, we have the following.
evd
Σ M
Ro (M,,)))
Σ
Σ
Es (Umm (sign (Eme))]
ME(=E)
8 ev M
E
Σ @msefte)
Es (Umi (sign (Emi))
2
E(=))
cvd M
Σ
T
d = 2d- 2
2
m=1 E
Therefore, we conclude that there exists an instance with the parameter set of {0m m such that R(M,T) 2 eMTVd for E [0, 4\3 V f. Notice that this proof holds for Too (2e) class. Scaling down by 2. we have the following for Ioe (E) class,
eMTV
(M,,T) (2 (M,,T)
for E
0,
8
2v3
T
Observe that sMTVd is a strictly increasing function w.r.t. is at most dMvT
when
16v3
2/3 T
In other words, RI (e) (M, T) min( MTVV dMVT for (0, 2
41.
16v3
Recall that inf supreze (c) R(M,T) 2 inf (up I R(M,T), for any E 2 2 Thus, we conclude, Ve 2 0, the following holds,
eTVV dM
inf sup RA,I(M,T) 2 min(
A IEI~ (6)
8
16v3
which completes the proof.
C Supporting Lemmas
Lemma C.1. Lattimore and Csaba 2020 Theorem 24.2]). Assume d 2n and let D {a E RRd || S1.. Then there exists parameter vector 0 E Rd with |10 de (2/(48n) such that R2 (D,0) dvTr/(1633).
Lemma C.2. (Abbasi-- MAbbasi-Yadkorii Yadkori al. 2011 Lemma 121). Let A, B and C be positive semi-definite matrices such that = B + C. Then, we have that
x Ax
del(A)
sup x x Bx
det(B))
22

---

Lemma C.3. (AAbbasi- Yadkori et al. d x d positive definite matrix and define V
2011
Lemma 11]). Let {Xt]i=i be a sequence in R V
V
Σ X, X Then, we have that
det (Vn) det(V)
log
X 1
Further, if X S L. for all then
Σ min [1,11
(log det (V.) -lo) log V) 2 log ((trace(V) + nL2) /d) llog det V)
Lemma C.4. (Self-Normalizer Bound for Vector- Vector-Valued Valued Martingales, [Abbast- Yadkori et al. 2011 Theorem 11). Let (Ft)== be filtration. Let (1p)11) be a real-valued stochastic process such that me is Fe-measurable and Tt is conditionally E-sub-Gaussian for some R Le.
X²
vEE E [ [t-1] exp
Let {Xili=1 be an Rd -valed stochastic process such that X, is Fi---meauurable. Assume that V is d d positive definite matrix. For any t 2 0, define V₁ = V + Σ.= X,X, Then, for any > 0. with probability at least 5, for all 2 0.
2R log det (V.) 1/2 det(V)-14 1/2
Σ
X,
P:-
Lemma C.S. (Pinsker's inequality Lattimore and Csaba 2020 Equation 14.12])
For measures P and on the same probability space (Ω, F), have the following,
sup P(A) - Q(A) $ |
AEF
23


Reviews:
[{"review_id": "ulFr36LAVB", "reviewer": "Reviewer_JJk8", "summary": "This paper studies multi-agent linear contextual bandits problem where each agent faces different bandits model. The heterogeneity is captured by the $l_2$ distance between the environment parameters. An upper confidence bound (UCB) algorithm, termed as H-LinUCB is proposed. The regret upper bound nearly-matches the lower bound proved by this paper in both small and large heterogeneity regime. The experimental results also valid the effectiveness of the proposed algorithm.", "questions": "It seems like we can have a simpler criterion when $\\epsilon$ is known. For example, if $\\epsilon\\leq 1/\\sqrt{T}$, we deploy a H-LinUCB with $\\tau=T$ and when $\\epsilon\\geq 1/\\sqrt{T}$, we deploy individual OFUL algorithm for each agent. The regret upper bound is $O(\\epsilon MT + d\\sqrt{MT})$ and $dM\\sqrt{T}$ respectively, which scales the same as that provided in the paper. In my opinion, this rule is simple and may have lower communication and computation cost since there is no communication when $\\epsilon$ is large.\n\nCan author discuss whether this method works?\n\nAnother question is that is it able to detect the magnitude of $\\epsilon$ when $\\epsilon$ is unknown so that the algorithm can automatically “stop” to aggregate?\n", "limitations": "n/a", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ The paper provides solid theoretical results including both regret upper bound and regret lower bound. The discussion of the small and large $\\epsilon$ cases are insightful.\n\n+ The paper provides experimental results to validate their theoretical results.\n", "weaknesses": "The major weaknesses is the design of the stopping criterion. Please see the question part for detailed discussion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your suggestions. We address your concerns and questions as follows:\n\n>.... Can author discuss whether this method works?\n\nWe appreciate your discussion and thank you for raising an insightful question. Mathematically, in the scenario where $\\epsilon$ is known, your proposed rule would indeed yield the same statistical guarantees. However, our objective was to design a generic algorithm that would be adaptive to an unknown $\\epsilon$, even though in our current results, we only worked in the known $\\epsilon$ setting. Specifically, our stopping rule adjusts the collaboration based on the $\\epsilon$, enabling us to extend the current algorithm to the case of unknown $\\epsilon$. \n\n> Another question is that is it able to detect the magnitude of when $\\epsilon$  is unknown so that the algorithm can automatically “stop” to aggregate?\n\nThat is also an excellent question, something we leave for future work. We do believe that it is possible to estimate $\\epsilon$ (by doubling trick, corralling, etc.) using data collected during early rounds. Depending on the estimate, the algorithm would determine whether it will continue to collaborate or cease it. We note, though, that what we really require is any upper bound on $\\epsilon.$\n"}, {"review_id": "lKrv48gATW", "reviewer": "Reviewer_5b9x", "summary": "This work considers a multi-agent linear contextual bandit model with heterogeneity among the agents. The authors propose a novel algorithm called H-LinUCB to minimize the group cumulative regret when agents communicate through a central server. When the level of heterogeneity is known to the agents, they show that H-LinUCB is provably optimal in regimes when the agents are highly similar or dissimilar. ", "questions": "- Some of the notation isn't defined in Appendix A.2. What is $V_p$ in line 498? How is the condition on the ratio of determinants obtained below line 499? I was hoping if the authors could re-write the proof of Theorem 4.1 so that it is easy to follow\n\n----\n\nPost rebuttal: I have raised the score from 5 to 6.", "limitations": "I don't see any potential negative societal impact of their work", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Originality:\n------------\n- The authors introduced the notion of heterogeneity as a $\\epsilon$-MALCB problem, inspired by (Wang et al. (2021))\n- The model considered in this paper is well-motivated  \n- Related work covered in detail\n\nQuality:\n-----------\n- The theoretical analysis seems to be concrete\n- Numerical simulations are provided to validate the theoretical results\n\nClarity:\n-----------\n- The paper is well-written and easy to follow, with the exception of some proofs in the supplementary material\n\nSignificance:\n-----------\n- The proposed notion of heterogeneity could be of interest to researchers, particularly for the case when the level of heterogeneity is unknown", "weaknesses": "- The algorithmic ideas and the regret analysis are known extensions of the work in (He et al. (2022), Wang et al. (2020), Dubey et al. (2020))\n- The lower bound proof is extended from the ideas in (Lattimore and Csaba (2020))\n- The algorithm depends on the assumption that the level of heterogeneity $\\epsilon$ is known, which need not be true in realistic scenarios\n- The proof of Theorem 4.1 in Appendix A.2 is not easy to follow, because the steps aren't explained in detail. Even though the regret analysis is extended from (He et al. (2022), Wang et al. (2020), Dubey et al. (2020)), I believe a paper should be self-contained.\n- The lower bound seems to be loose, because it is off from the regret upper bound by a factor of $d$ in one of the terms. Furthermore, it is not applicable in the regime $\\epsilon \\in (1/\\sqrt{MT}, d/\\sqrt{T})$\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your time and effort to review our submission. We hope to address your concerns as follows. \n\n> The proof of Theorem 4.1 in Appendix A.2 is not easy to follow, because the steps aren't explained in detail. Even though the regret analysis is extended from (He et al. (2022), Wang et al. (2020), Dubey et al. (2020)), I believe a paper should be self-contained.\n\n> Some of the notation isn't defined in Appendix A.2. What is $V_p$ in line 498?\n\nOn line 196, we denote matrix $V_{sync}$ as a sufficient statistic needed to form a least square estimate. Essentially, the matrix $V_{sync}$ contains all the samples after the synchronization (line 20 algorithm 1). In line 495, we have $P$ as total epochs where the synchronization happens. Here, $V_P$ is a matrix that contains all the samples of the agents at the last synchronization epoch. We apologize for not clearly introducing this bit of notation; we will fix that in the next revision.\n\n> How is the condition on the ratio of determinants obtained below line 499? I was hoping if the authors could re-write the proof of Theorem 4.1 so that it is easy to follow\n\nSure, we will be happy to provide those details. Essentially,\nby telescoping, we have that $\\log \\frac{\\det(V_P)}{\\det(V_0)}=\\log \\frac{\\det(V_P) \\cdot \\det(V_{P-1}) \\cdots \\det(V_{1})}{\\det(V_{P-1}) \\cdots \\det(V_{1}) \\cdot \\det(V_0)}=\\sum_{p=1}^P\\log \\frac{\\det(V_p)}{\\det (V_{p-1})}$.\nFurthermore, we have the following condition (which we state above line 499):   \n\n$\\log \\frac{\\det(V_P)}{\\det(V_0)}\\leq d \\log ( 1+ \\frac{M\\tau }{\\lambda  d } )$    \n\nTherefore, we have at most $R = \\lceil d \\log ( 1+ \\frac{M\\tau }{\\lambda  d } )\\rceil$ epochs such that $\\log \\frac{\\det(V_p)}{\\det(V_{p-1})}\\geq 1$; otherwise, we have $\\log \\frac{\\det(V_P)}{\\det(V_0)}> d \\log ( 1+ \\frac{M\\tau }{\\lambda  d } )$, which violates the condition above. This implies that for all but $R$ epochs, we have that\n$0 \\leq \\log\\frac{\\det(V_p)}{\\det(V_{p-1})}\\leq 1$, which is $1 \\leq \\frac{\\det(V_p)}{\\det(V_{p-1})}\\leq 2$.\n\nWe thank you for your suggestion. We will add the explanations to the proof of Theorem 4.1. in our revision.\n"}, {"review_id": "4g9YOJjtqO", "reviewer": "Reviewer_bsff", "summary": "This paper studies multi-agent linear stochastic bandit under a model of heterogeneity of the agents. Concretely, the model assumes a centralized controller who can communicate information to and from all of the M different agents in the network. At each time, every agent in the network, will play an arm from a set of possible arms (that are adversarially chosen). The choice of which arm an agent plays is a function of only the past information at that agent -- namely the agent's past arms pulled and rewards observed and the information communicated by the central controller to the agent. Subsequently, the agent observes a noisy stochastic reward where the noise is independent across agents and time. \n\nTo facilitate group learning, the paper assumes structure among the heterogeneity. Concretely, the paper assumes that the unknown parameter for any pair of agents is at-most \\epsilon away in L2 distance. This modeling assumes that although the agents are different, nonetheless have a latent structure which can enable faster learning.\n\nUnder this structure, the paper proposes an algorithm such that the sum regret of all agents scale sub-linearly in M and T. The paper also gives lower bound evidencing that their upper bounds are order wise tight. ", "questions": "The main questions for the authors is to elucidate their contributions in comparision to Ghosh et.al.? \n\nSpecifically, \n\n1)The authors make a stronger assumption on the heterogeneity (Defn 3.1) compared to Ghosh et.al. Does this stronger assumption on heterogeneity is what enables the authors to allow for adversarially generated set of arms? \n\n2) The algorithm of Ghosh et.al. does not need \\epsilon while the present paper assumes knowledge of \\epsilon. Can the authors comment on the necessity of this information?\n\n3) In the case of stochastic arms, is the  weaker result of the submission compared to Ghosh et.al. the price needed to pay for having an adversarial arm setup? \n\n***Post Rebuttal: *** Thank you for your response and I have updated my score. ", "limitations": "NA", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Well articulated problem, algorithm, intuition and the key steps of the analysis. ", "weaknesses": "The main weakness is the positioning and contributions of the paper in comparison to \"Multi-agent heterogeneous stochastic linear bandits, Ghosh et.al. in ECML-PKDD 2022\" which the submission cites. \n\nSpecifically, the submission claims that the model of heterogeneity studied is different from Ghosh et.al. (Line 280 of the submission). However, a cursory examination indicates that the assumption of the submission is stronger than Ghosh et.al's in the sense that Defn 3.1 of the submission implies that the average parameter is close to any agent's parameter by \\epsilon, which is the assumption in Ghosh et.al. Does this imply that the assumptions in the present paper with regard to heterogeneity are stronger than Ghosh et.al.'s? \n\nA somewhat less satisfying feature of the algorithm is also the known \\epsilon which seems to be non needed by Ghosh et.al. ?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your insightful feedback and questions. We hope to clarify our contributions compared to Ghosh et al. as follows:\n\nBesides the stochastic assumption, Ghosh et al. also make a **strong distributional assumption** on how the arm is being generated. Essentially, they require a lower bound on the smallest eigenvalue of the covariance matrix of context vectors. Formally, they need that  $E_{t-1}[\\beta_{i,t}\\beta_{i,t}^\\top] \\geq \\rho_{\\min} I$ ; see Equation~1 of Ghosh et al.\nThis assumption is crucial for them as it allows them to estimate the average parameter and motivates the algorithm design. \n\nWe do not make any such distributional assumption since it is often unrealistic in practical settings. On the contrary, we consider an adversarial setting where the arm sets at each round can be selected by an (oblivious) adversary and the size of the arm sets can even be infinite. Our setting renders the algorithmic design and guarantees of Ghosh et al. inapplicable as far as we can tell, thus requiring a completely new treatment.\n\n> Specifically, the submission claims that the model of heterogeneity studied is different from Ghosh et.al. (Line 280 of the submission). However, a cursory examination indicates that the assumption of the submission is stronger than Ghosh et.al's in the sense that Defn 3.1 of the submission implies that the average parameter is close to any agent's parameter by \\epsilon, which is the assumption in Ghosh et.al. Does this imply that the assumptions in the present paper with regard to heterogeneity are stronger than Ghosh et.al.'s?\n\nYes, our notion of heterogeneity is slightly stronger.  However, we can possibly work with the same heterogeneity assumption as in Ghosh et al. This is simply a matter of presentation. In particular, note that for their personalized framework, Ghosh et al. give a regret bound for individual agents – it is, therefore, natural to have a more fine-grained notion of heterogeneity by defining the dissimilarity of the individual parameter with the average parameters. However, our work emphasizes the collaboration among the agents, and we are interested in the _group_ regret instead of individual regret. Therefore, the heterogeneous notion which we proposed is a natural way to capture the heterogeneity among the agents. Again, these differences are merely cosmetic. We can work with the same assumption as Ghosh et al. and present bounds on the individual agent’s regret. \n\n\n> The authors make a stronger assumption on the heterogeneity (Defn 3.1) compared to Ghosh et.al. Does this stronger assumption on heterogeneity is what enables the authors to allow for adversarially generated set of arms?  \n\nNo, as we say in the remarks above, the difference between the two notions of heterogeneity is not significant. We do not rely on the heterogeneity assumption to allow for an adversarially generated set of arms. \n\n> The algorithm of Ghosh et.al. does not need \\epsilon while the present paper assumes knowledge of \\epsilon. Can the authors comment on the necessity of this information?\n\nThe knowledge of (an upper bound on) $\\epsilon$ facilitates our algorithmic design in constructing the confidence bound and controlling the collaboration between tasks. Adapting to the unknown $\\epsilon$ in an adversarial setting that we consider here would require additional work. It is important to note that the adaptation strategy of Ghosh et al. (to unknown $\\epsilon$) _fails_ in an adversarial setting. \n\n> In the case of stochastic arms, is the weaker result of the submission compared to Ghosh et.al. the price needed to pay for having an adversarial arm setup?\n\nYes. However, we would like to reiterate that the two settings are simply _incomparable_. Again, Ghosh et al. need a strong distributional assumption to obtain their bounds. In fact, the $O(T^{1 /4})$ bound that they achieve (for $\\epsilon = 0$) is not even possible information-theoretically in an adversarial setting. The minimax lower bound in such settings is $O(\\sqrt{T})$ which we match. \n"}, {"review_id": "MRGyz4FiiS", "reviewer": "Reviewer_gcmR", "summary": "This paper considers a multi-agent linear contextual bandit (with central server coordination) setting where $M$ agents each has (possibly different) unknown but fixed $d$-dimensional bandit parameter $\\theta_m$, and the $\\ell_2$-norm bound on the bandit parameters $\\epsilon$ (i.e., $||\\theta_i - \\theta_j||_2 \\leq \\epsilon, \\forall i, j \\in [M]$) is known to the agents. The authors propose a UCB-based algorithm that collaborates for the first $\\epsilon^{-2}$ time slots and then learns individually. The authors also present the related regret upper bound and lower bound and run experiments on synthetic data.", "questions": "- How does the algorithm perform if the given $\\epsilon$ is off from the real $\\epsilon$ of the environment? \n- How does the result in this paper generalize to linear (non-contextual) bandit?\n- How important is the dissimilarity defined on $\\ell_2$-norm? Why didn't the authors consider $\\ell_\\infty$ norm as prior work?\n- (minor point) It is not clear what kind of norm the one in line 42 is.\n", "limitations": "The authors discuss some limitations (that $\\epsilon$ is assumed known and that the proposed algorithm is not optimal for some values of $\\epsilon$) in the conclusion section. In my opinion, the primary limitation of this work is the practicality of the proposed algorithm as $\\epsilon$ is often not precisely known in real application.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- Heterogeneous collaborative multi-agent setting is an upcoming area of interest, so this paper is likely to be relevant to the community.\n- The idea of adjusting the length of collaboration by the dissimilarity (i.e., $\\tau = \\min(\\lfloor\\epsilon^{-2}\\rfloor, T)$) is neat and intuitive.\n- The code used for the experiments is also included and the results should be easily replicable.", "weaknesses": "- The introduction of the proposed algorithm (Section 4.1) is not easy to follow and understand, many new variables are used without explanations\n- Notion of heterogeneity and the part of algorithm for handling collaboration with dissimilarity seem to be straightforward extensions of prior works, the new technical challenges for analyzing the proposed model and algorithm are not clearly discussed", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your suggestion. We address your concerns as follow:\n\n> The introduction of the proposed algorithm (Section 4.1) is not easy to follow and understand, many new variables are used without explanations  \n\nIn line 196, we define these variables as sufficient statistics. Specifically, $V$ is the gram matrix, and $b$ is the sum of the product of reward and context vector, which we use to form a regularized least squares solution and construct the confidence bound for our linear bandit problem. \n\n> How does the algorithm perform if the given $\\epsilon$ is off from the real $\\epsilon$ of the environment?  \n\nAs we discussed in our submission, the current scope of our paper is when $\\epsilon$ is known and we leave the case when $\\epsilon$ is unknown to a future work.\n\n> How does the result in this paper generalize to linear (non-contextual) bandit?  \n\nOur setting is linear bandit. The arms in the decision set are also referred to as the contexts in the literature.  \n\n> How important is the dissimilarity defined on $\\ell_2$-norm? Why didn't the authors consider $\\ell_\\infty$-norm as prior work?  \n\nIt is not important. There is no particular reason why we choose $\\ell_2$ over $\\ell_\\infty$, it is just natural to use $\\ell_2$-norm to define the distance of two vectors. When using $\\ell_\\infty$-norm the results would change by a factor of $\\sqrt{d}$. Even if we use $\\ell_\\infty$-norm, it is also not comparable to the prior work of Wang et al. 2021,  because (1) $\\epsilon$ hides inside the subpar-arm set, and (2) it is not possible for us to define such subpar arm set in our setting when the arm sets can be generated arbitrarily.\n\n> (minor point) It is not clear what kind of norm the one in line 42 is.  \n\nIt is $\\ell_2$-norm. We'll add the subscript in the revision.\n"}, {"review_id": "BQ1OPCsIuF", "reviewer": "Reviewer_kifo", "summary": "This paper studies the heterogeneous multi-agent contextual bandit problems. They propose the H-LinUCB algorithm, where agents coordinate at the beginning stage by pooling and synchronizing the data, until a certain time determined by the dissimilarity. They show the algorithm is optimal when the tasks are highly similar or highly dissimilar.", "questions": "Although both plots (c) and (d) correspond to regime (ii), H-LINUCB performs differently in the two settings. It resembles Ind-OFUL in (c) but not in (d). What's the key component that leads to the different behavior? Is there a threshold for $\\epsilon$ above which H-LINUCB could be shown to copy Ind-OFUL?", "limitations": "I don't see any limitations or potential negative societal impact of this work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and organized in general. Multi-agent learning, especially in the heterogeneous setting, is of great interest in the literature. The scenario considered is hard, as they don't add special structures for the parameters other than assuming the dissimilarity is known. Yet the results are strong and seem to be theoretically rigorous. Moreover, this work improves DISLINUCB by discarding coordination when the dissimilarity level is too high and the coordination hurts the regret.", "weaknesses": "The experiment part is relatively weak to me. Currently, the authors consider three settings of different levels of dissimilarity to highlight the advantage of the proposed H-LINUCB in achieving good regret in all settings. However, there isn't a setting where H-LINUCB dominates the other two algorithms. This makes H-LINUCB more likely an interpolation of the fully communicating and fully independent methods. I hope the authors could at least show some experiments where H-LINUCB uniquely succeeds or achieves the best regret, or discuss why this is impossible or hard.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your feedback. We address your concern about the experiments as follows:\n\n> The experiment part is relatively weak to me. Currently, the authors consider three settings of different levels of dissimilarity to highlight the advantage of the proposed H-LINUCB in achieving good regret in all settings. However, there isn't a setting where H-LINUCB dominates the other two algorithms. This makes H-LINUCB more likely an interpolation of the fully communicating and fully independent methods. I hope the authors could at least show some experiments where H-LINUCB uniquely succeeds or achieves the best regret, or discuss why this is impossible or hard. \n\nWe believe that the experiments efficiently demonstrate our objectives. Our goal was to show that H-LinUCB is essentially behaves as “the best of the both worlds” approach. Specifically, our experiment aims to show that H-LinUCB can improve regret when there are opportunities for collaboration, and does not collaborate if it gains no benefit. Therefore, it behaves as DisLinUCB when it is beneficial to collaborate and behaves as Ind-OFUL, otherwise. \n\nOn the contrary, Ind-OFUL is unable to leverage similarity structure between bandits to learn faster, whereas DisLinUCB incurs linear regret in the case that collaboration only hurts the performance. Thus, DisLinUCB and Ind-OFUL both fail in different ways. \n\nRegarding your question on the interpolation, for small $\\epsilon$, we would see that H-LinUCB performs worse than DisLinUCB due to the artifact of the extra term $\\alpha \\epsilon Mt$ to handle the dissimilarity (Lemma 4.1). \n\n> Although both plots (c) and (d) correspond to regime (ii), H-LINUCB performs differently in the two settings. It resembles Ind-OFUL in (c) but not in (d). What's the key component that leads to the different behavior?\n\nThe reason is that $\\epsilon$ increases significantly from plots (c) to (d). In plot (d), H-LinUCB only collaborates for a small number of rounds, and switches to independent learning; the plot therefore looks nearly identical to Ind-OFUL.\n\n> Is there a threshold for $\\epsilon$ above which H-LINUCB could be shown to copy Ind-OFUL?\n\nFrom a theoretical viewpoint, for $\\epsilon=1$, H-linUCB will behave like Ind_OFUL. However, experimentally, it is not clear what that threshold is – it would vary from experiment to experiment due to a randomly generated set of parameters. For some large enough $\\epsilon$ (could be smaller than 1, e.g., plot (d) ), H-LinUCB only allows agents to collaborate for a small number of rounds then switches to learn independently, so the regret of H-LinUCB is nearly identical to that of Ind-OFUL by just looking at the plot. \n"}]

Author rebuttal:

Meta-review: Reviewers all agreed that the problem studied is interesting, and the technical results are solid. There were some concerns regarding the contributions of this paper in comparison to Ghosh et.al. and several other previous works. The authors' rebuttal convinced the reviewer about the novelty of this paper. After the rebuttal, all reviewers view this submission positively.
Decision: Accept (poster)