Individual Regret in Cooperative Stochastic Multi-Armed Bandits
Authors: Idan Barnea
Tal Lancewicki
Yishay Mansour
Venue: NeurIPS 2025 poster ()
Keywords: MAB
Multi-armed bandit
stochastic MAB
cooperation
Primary area: theory
TL;DR: We provided individual regret bounds for cooperative stochastic multi-armed bandits over communication graphs, independent of graph diameter, and also analyzed trade-offs with message size and communication rounds.

Abstract: We study the regret in stochastic Multi-Armed Bandits (MAB) with multiple agents that communicate over an arbitrary connected communication graph.
We analyzed a variant of Cooperative Successive Elimination algorithm, $\texttt{Coop-SE}$, and show an individual regret bound of ${O}(\mathcal{R} / m + A^2   + A \sqrt{\log T})$ and a nearly matching lower bound.
Here $A$ is the number of actions, $T$ the time horizon, $m$ the number of agents, and $\mathcal{R} = \sum_{\Delta_i > 0}\log(T)/\Delta_i$ is the optimal single agent regret, where $\Delta_i$ is the sub-optimality gap of action $i$.
Our work is the first to show an individual regret bound in cooperative stochastic MAB that is independent of the graph's diameter.

When considering communication networks there are additional considerations beyond regret, such as message size and number of communication rounds.
First, we show that our regret bound holds even if we restrict the messages to be of logarithmic size.
Second, for logarithmic number of
communication rounds, we obtain a regret bound of ${O}(\mathcal{R} / m+A \log T)$.

Individual Regret in Cooperative Stochastic Multi-Armed Bandits
Idan Barnea
Tal Lancewieki
Blavatnik School of Computer Science and AI Blavatnik School of Computer Science and AI
Tel Aviv University, Israel
Tel Aviv University, Israel lancewick (alaaimmmal..mmmmmmmm tau ac il
idanbarnea @maill tau. ac .c.il il
Yishay Mansour
Blavatnik School of Computer Science and Tel Aviv University, Israel Google Research, Tel Aviv, Israel
Abstract
We study the regret in stochastic Multi-Armed Bandits (MAB) with multiple agents that communicate over an arbitrary connected communication graph. We analyzed variant of Cooperative Successive Elimination algorithm, Coop-SE, and show an individual regret bound of ORR/m + A + Avlog T)) and a nearly matching lower bound. Here the number of actions, T the time horizon, m the number of agents, and R Ea.s0 log(T)) A, is the optimal single agent regret, where A is the sub-optimality gap of action Our work is the first to show an individual regret bound in cooperative stochastic MAB that is independent of the graph's s diameter.
When considering communication networks there are additional considerations beyond regret, such message size and number of communication rounds. First, we show that our regret bound holds even we restrict the messages to be of logarithmic size. Second, for logarithmic number of communication rounds, we obtain regret bound of O(R/m + Alog T").
Introduction
Multi-Armed Bandit (MAB) is a fundamental framework for studying sequential decision making, with an expanding scope of practical applications (see, 22 33
Recent research expanded the classic MAB problem into cooperative setting, sometimes referred to cooperative multiplayer or multi-agent MAB, where multiple agents share the same goal and can communicate with each other.
A significant focus of recent research has centered on cooperating agents within communication graph, often referred as communication network. This framework, which all agents address the same problem, dates back to Landgren et al. 18] for stochastic rewards and Cesa-Bianch et al. (5) for the nonstochastic case. this setting, agents transmit information to adjacent neighbors, from which it continues to propagate throughout the entire network while encountering delay at each step. Communication graphs paired with stochastic Multi-Armed Bandits provide a framework for distributed decision-makin under uncertainty. As example of our setting, consider computer networks. large-scale High Performance Computing (HPC) or systems, individual machines often have flexible hardware, e.g., tunable cores, caches, or memory controllers, that adapt based on workload pattern. These computers (agents), connected over network (graph), must quickly choose a hardware configuration (action) to optimize their performance (reward). Social networks are good examples as well: individuals share experiences directly with friends, forming a natural
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

communication structure for learning to propagate and improve collective decision maaiing. In the non-stochastic setting Bar-On and Mansour B showed nearly optimal individual regret bound of Ó(v(1+ + A/N()))T), where (w)) is the number neighbors for the agent v. This setting differs from the stochastic case: notably, the optimal bound in the non-stochastic setting includes a vT term, even if m s T, since the full information lower bound is ((VT). On the other hand, in the stochastic setting, we achieve something much stronger. With sufficiently many agents, our worst-case regret can be as small as O A /log(T)). Importantly, this is independent of the sub-optimality gaps.
The literature of cooperative stochastic MAB distinguishes between group regret (a.k.a. average regret) [18/21 6 29 35 39] [ and individual regret (3). where the latter is much stronger and more challenging to achieve. Additionally, significant attention is given to minimizing the number of messages each agent sends 33 25 26
28
30
and reducing message size
1.1 Graph diameter and individual regret bounds
Let the single-agent regret bound be denoted with R == := E, (Tg())/AA For cooperation to be meaningful, one needs sufficiently large number of agents m. Our goal is to reduce the individual regret from R to R/m. A potential problem can be if regret bounds include an additive term of the order of D, the graph's diameter, which can be large in practical scenarios. A regret of the form R//m- + D might provide a limited guarantee: for a cycle graph (D = (m)) it will give R/m + m which is at least / = (E: log )1/2 for any m; for a grid graph (D = @(v the regret will be at least R1/3 = CE: log /1/3. Note that in these scenarios, the inverse dependency on A, remains, even if the number of agents m goes to infinity and the term R/m m vanishes. This explains our desire to avoid this additive D.
A.
Our diameter- free bound is only A² + (og()))))) for sufficiently large m, entirely independent of the gaps. An interesting case is when the gaps are small, leading to high single-agent regret. For example, when A VA/T, we get R x VAT. In this case, regret bounds with an additive D term may still yield R1/3 (AT) 1/6 for grid graphs, whereas diameter- bound grows is only A A AAoooTT)
To the best of our knowledge, this is the first paper to show a graph-independent individual regret bound, Additionally, we present similar individual regret bound for scenarios of small message size, as well as for scenarios of limited number of messages.
1.2 Key contributions
Our key contributions are follows:
We prove that Coop-SE (Algorithm achieves a near-optimal individual regret bound of ORR/m + A2 + A Alg((T), which is independent of the graph's diameter. The regret bound in minimax form is O( O(yTAloggg (og()))m)) + A2 - A (Tgg(T)) When Coop-SE is played with random action choices instead of round-robin we get O(R/m /m + Alog(T)) and accordingly, O(gTTlog(T))m + Alg((T))
We show a lower bound for the individual regret of Q( / + VA), which almost matches our upper bound in the minimax form.
For settings with restricted message sizes of OllogmmA)) also known of the CONGEST model (see (31),, we introduce Soop-SE-CONGEEN which achieves individual regret of O(R/m- A + ATlog(T)). In minimax form O(vT'A logg))) A + AVlog(T)).
For scenarios where agents are limited to O(log(T)) communication rounds, present Soop-SE-Comm-Cost, that achieves individual regret of O(lo((A)R, m + A log( (og)))))) and in the minimax form ( AogTAlog(A) log(T)/m + A log(A) (A) log(T)).
Kolla et al. [16] raised the question of whether it is feasible to surpass the performance of well- established single-agent policies, such as UCB (2] and SE, when these policies are executed indepen- dently across the network. While this question has also been explored in several prior works (see, for example, (0), our contribution provides complementary perspective by analyzing individual

---

Table 1: Performance Comparison of Multi-Armed Bandit Algorithms in Cooperative Settings. Notation: Horizon Т; Number of agents m: Actions A; Graph's s diameter D; Graph G; R log T is the optimal single agent instance-dependent regret.
Ea,0 A.
Requires only local graph info.
Indiv.
Message size
Comm. rounds
Algorithm
Regret
regret
Coop-UCB2 21
R/m + Af(g))
Alog(mT)
DDUCB [99
R/m + Ah(g)
Alog(mil
T
UCB-TCOM 36
R/m + AD
d
m mlog(AA))
D log( 1og
R/m
Coop-SE
/
m.llog(T)
T
+ A min{ A + Vlg / T, D}
Goop-SE-CONGEST
R R/m + A² + Avlog
log(mA)
X
R ( (r)(())
Prop-SE-Comm-One
Alog(m)
log(T')
X
+ A log loog A
regret that is independent of the graph's 's diameter. The combination of our lower bound and the analysis of our Coop-St algorithm thus refines the understanding of this question in the cooperative setting.
1.3 Relation to Prior Algorithms
We start with brief explanation of the Successive Elimination (SE) algorithm [3] SE is a classical multi-armed bandit algorithm that achieves low regret for single agent. progressively eliminates suboptimal actions by repeatedly sampling all active actions, estimating their mean rewards, and removing any action whose confidence interval clearly worse than that of some other action. In cooperative multi-agent settings, variants of SE have been studied in which agents exchange rewards and elimination signals and use them to refine their own action sets Yang et 38 39), Zhang et al. 44). Our proposed algorithm, Coop-SE, builds upon these works: it employs Successive Elimination combined with message passing, and allows each agent to use the elimination signals of others in order to eliminate its own actions. The main contribution of this paper is new analysis of the Coop-SE algorithm.
1.4 Related work
Average regret was studied by Landgren et al. 19 20 21), Martfnez-Rubio et al. (29]. Chen
et al. [8] who achieved an average regret guarantee of O m + Af(G)), where f(g) a function of the eigenvalues of the adjacency matrix of the graph, which is related expansion properties. The consensus-based algorithm Coop-UCB2 presented in Landgren et al. 21 requires the construction of matrix based on the graph's s structure. This dependency means the algorithm cannot rely solely on local information. The algorithm's regret bound is R/m + A f()), where f(G) represents graph-dependent function. For certain graph topologies, such cycles, this function f()) may be at least m. Martínez-Ruule knowledge of the graph's 's topology. Their regret bound is R/m + hG)), where the function
et al. (29] presented DDUCB, consensus- based algorithm that requires
is defined as hg) = lmg(m)/ /aamm////oo(//////// //og(1//A))) Here, A2 is the second largest eigenvalue (in absolute value) of the communication matrix, also known the gossip matrix (see (37 12.7). The eigenvalue Ag related to how the graph expands and can be very close to one for some graphs. For instance, in circle graph, A = cos(2T) (2TT) /m) ss 1 1/m², resulting in h()) regret bound of DDUCB becomes R/m Am.
Consequently, the average
Gossip algorithms traditionally operate through networks where nodes communicate along graph edges to achieve consensus, typically by converging to average values across all nodes. However, the Coop-SE algorithm takes different approach. Instead of seeking to synchronize nodes to common average values, we focus on ensuring nodes maintain similar sets of active actions. This key distinction drives the innovation in our approach.

---

Average regret was also studied by B35 6 as well. Wang et al. [35] has an additive term in the regret that scales with the diameter of the graph. Chakraborty et al. 6 consider model with non-fresh randomness, where the reward for each action is generated once per timestep, and agents choosing the same action receive the same feedback. Even with full communication, the best attainable regret is that of full information.
Small number of messages and small messages. Wang et al. 36 show an individual regret guarantee of O + AD), where each agent sends at most O log (To messages. Their algorithm, UCB-TCOM, needs to know the value of D in advance and uses it to synchronize between agents. Yang et al. (39] present SE algorithm achieving similar regret bound, but their analysis limited to connecco graphs, with each agent sending (llog(1/A) (1/A)) messages. Note that whenever A = ()) for a E (0, 1), the number of messages in both of these works is of order of (Tg( Madhushani and Leonard (26 introduces an algorithm with log(T) communication steps, and their regret scales as (og(T)x( (T) (Am)), where x(G) is the clique cover number of the graph. For instance, for trees, cycles, and grids, the regret bound on the order of T/A. similar to non-cooperative scenarios, while for fully connected graphs, it is ( Agarwal et al. MI] have D lT') communication rounds and only (A) bits per message, but their regret scales as [(A/m + deg(g)) where deg(g) is the maximum degree of the graph. Note that their regret bound is at least VT.
Other related problems, such as directed communication, cooperation in Markov-Decision Desoo-DDesiioonPPocsssse (MDPs) and best-arm identification, have also been studied. For a more comprehensive discussion, we refer the reader Appendix A
2 Model and problem formulation
Stochastic MAB (SMAB): A stochastic Multi-armed bandit problem has A actions, denoted by A = {l...., AJ. Each action a E A has a reward distribution Da, whose support is [0, 1], and its expectation pag. EErDD [r]. An optimal action is denoted with a", where a* E arg maX.eA Max and μr Par. The gap of a sub-optimal action a is A. = ue² Ma.
Multi-agent MAB: We have an undirected connected graph G(V,E), where is the set of vertices and E the set of edges. Every vertex represents an agent. An agent u is a neighbor of agent u iff (v. u) E. The diameter of the graph is denoted by D. Let N be the set of agents at distance at most d from agent v, i.e., _ = {u E Vidg(e, u) S d), where (g u) is the minimal path length (number of edges) from
G. For simplicity, we assume m, S poly(T))
There are T rounds of play. Each agent v E V, in each round of play E [T] does the following: (1) selects an action a/ E A and observes reward r` ~ Day (note that the rewards of the different agents are different random variables). (2) sends messages to neighboring agents u E N (3)
receives messages from neighboring agents u E N See the protocol in Algorithm D
Regret definition: The individual (pseudo) regret of an agent is defined by Ry BI (n" -r (at))) In this paper, focus on minimizing the individual (pseudo) regret of every agent.
Events and Messages: Our algorithms will have the agents broadcasting about the progress they make. There will be two types of progress. The first is a new observation of reward, which will be a reward event. The second is decision to eliminate certain action. This will be an elimination event. Formally, an event is a tuple describing reward, or a tuple describing an elimination of an action. A reward event is (rwd, tt v. a, r), where is the timestep, is the agent's ID, and r = rf (a.) ) is the reward. An elimination event is (elim, U, a), where u is the agent and a is the eliminated action. To denote individual elements within event tuple, we use subscript notation. For example, if we have an event event = (rwd, f, v. a, r), we denote the action a using eventa. We define a message be a set of events.
of is the action,
These functions can be as large as see discussion in related work. h(g) = log(m)/ V log (1/ Aaa)) Here f()) defined from Corollary 2 and Eq. (19) in (1]: the definition is very complex. but note that may be as large as m.
'The expectation of the pseudo regret is also over the randomness of the algorithm. We will refer to the pseudo regret as the regret for the rest of the article.

---

Algorithm Stochastic MAB on Graph. Protocol for agent
1: for E [T] do
2: Agent pieks an action oj E A.
3: Environment samples reward, rī (aj") ~ Day.
4: Agent observes reward r""(a"".
5: Agent sends messages m, m.." to each neighbor u.
6: Agent receives messages m,
a." from each neighbor u.
7: end for
Warm-up: diameter dependency
In this section, refine the best-known regret bound that depends the diameter. Specifically, we reduce the additive term from DA to D logg(A) + A. Our analysis builds on recent techniques developed for delayed MAB settings, leading relatively simple proof (see Appendix (D). This section serves as warm-up, introducing a straightforward algorithm that still relies on the graph's 's diameter, and provides useful reference point for the subsequent sections, where this dependency is removed.
Our algorithm in this section, Sus-Act (Algorithm 2) builds SE, but utilizes only samples that are already observed by all agents. Specifically, at any timestep t, each agent has already observed the samples collected by every other agent up to time D. where D is the diameter of the graph. computes its LCB and UCB Slower/Upper Confidence Bounds) based on
Thus, at time f, all samples from actions taken up time D. Consequently, all agents have exactly the same LCB and UCB, leading them to select identical actions and experience the same individual regret. Notice that the actions' tie-breaking is the same across all agents.
Conceptually, the shared information between agents increases the number of observed samples per played action by factor of m, the number of agents. On the other hand, samples from the last D steps are not processed (and will be processed when their delay would be exactly D). This is equivalent to environment with D-steps delayed feedback, typically introducing an additive D term to the regret.
Theorem 1. When each agent plays algorithm
2 the individual regret of each agent is,
lTg(T) + D A A
Ry
O
Σ A,20
mA,
The proof of Theorem [ is deferred to the supplementary material. In summary, when the regret bound depends on the diameter, the analysis remains relatively straightforward. In the following sections, move beyond this setting and show how remove the diameter dependence altogether, while retaining comparable guarantees.
Algorithm Sus-Act: Successive Elimination with Suspended Act (see Algorithm for detailed version)
1: Input: Diameter 1)
2: for t= 1,2, d
3: The agent plays Successive Elimination using information available up to time - D.
4: Send and receive rewards: The agent sends her reward from the current round and forwards to
all neighbors any previously unsent rewards (message passing).
5: end for
4 The Coop- SE algorithm and individual regret guarantees
We study Coop-SE, Algorithm 3 which is particular variant of Cooperative Successive Elimination rather than a new algorithmic concept. Coop-SE fully decentralized, and each agent plays independently. In Coop-SE, each agent runs SE with all the information available to it, while exchanging messages with neighbors that contain both locally generated and relayed information, including observed rewards and climination signals (i.e., message passing).

---

Algorithm 3 Cooperative Successive Elimination (Coop-SE)- simplified version (see Algorithm for full pseudo-code)
1: Init: Set the active actions set be all actions A A.
2: for = 1... I" do
3: Eliminate actions from incoming climination messages
4: Calculate counts and empirical mean for each active action based on all seen messages
5:
Calculate UCB, and LCB, based on the above counts and means (see Definition 12)
6: E {a E A 3a' E A such that (a) < LC A = A E
7: Choose action round-robin from the active action, d E A. Play it and get reward ry (at)
8: Send eliminations E, reward (0,, rt), and all messages received at 1 (message passing)
9: Receive messages from the neighboring agents
10:
end for
This increased information significantly reduces the regret compared to the non-cooperatiee setting. The formal description of the algorithm is provided in Algorithm Our main result the following theorem.
Theorem 2. When each agent plays Coop-SE SE (Algorithm 3y
the regret of each agent u E V is,
log(T")
Rg =
+ A AVlog(T)
mA;
A;50
To the best of our knowledge, this is the only individual regret bound that is independent the graph diameter. For comparison with prior work, we also derive improved variant of the bound that
+ A min (A + Vlog(T), D} The diameter term arises from refined analysis but is required by the algorithm; agents do not need know D. The full proof is provided in the appendix.
includes the diameter: - =
Es,o
log(T) m..
In 6 we present a lower bound of C2(TTAA TA/m+/////V/ which almost matches the upper bound of the individual minimax regret of Coop-SE. We note that slight variant of the algorithm, which samples actions uniformly from the set of active arms rather than using round-robin selection, incurs an additive term of A log T instead of A + A (see Thcorem S This is tighter whenever A >> log Tee Appendix Foor more details. However, the precise dependence on A in this additive term remains open question.
important insight that follows from these theorems that for sufficiently large number of agents, e.g., when R, achieve individual regret bound of O(A² Avlog T') that does not depends on the sub-optimality gaps.
In the following section, we present the key ideas employed in the analysis of the individual regret.
5 Individual regret analysis
In this section, we provide a proof sketch that outlines the key steps in our analysis. We analyze the regret of an arbitrary agent v, and all the definitions are referenced to this agent unless explicitly stated otherwise.
Our proof heavily relies on notion we call stages. These are the time intervals between the eliminations of agent Formally, a stage j [A] is the interval [tj, (z1)) where 4 1, and 4i+1 the timestep of the j'th elimination. We 11 also denote by Tý the length of the j'th stage and the number of active actions in that stage by A,
j +
The stages is one our core ideas, and they allow us to do the following. We bound the agent's regret in terms of stage length, and we bound the stage length function of the number of samples. Finally, we bound the number of samples in the standard approach. By combining these results, we obtain main theorem.
Bounding the regret in term of stage length We start by bounding agent v's regret in terms of stage lengths. Fix sub-optimal action and assume that is the last stage in which was active.

---

Since chooses active actions in round-robin, in each stage S i, she samples approximately Ty/A, times. Thus, the total number of times plays is approximately Σj=1 A, and we can roughly bound the regret with,
Ry x
Σ
A. i=1 A
(I)
where we slightly abuse notation and let A; be the sub-optimality gap of the action that was eliminated at the end of stage
Number of samples in terms of stage length Consider the j j'th stage and an action which is still active in that stage. For the sake of intuition, assume that the agents are completely synchronized, i.e. have the same set of active actions. In the first quarter of the stage, each agent who is close to contributes to v's information approximately Ty (4/(4) samples of action a. Since there were Ty /4 timesteps and each agent chooses action out of Aj. Moreover, these samples are observed by v with a delay of at most / and thus will reach e before the end of the stage.
If action a is active in the first stages, we would expect that the number of samples that reaches v for that action from the first i stages is at least of order of E)=1 A, |Ngr,/al, where Ngrr,/4 is v's neighborhood of radius 7,/4.
The above result implies that the amount of observed feedback from each stage is boosted by a factor |Ngr,/4l compared to the number of times that itself chooses the action.
However, in general, the agent's policies are not completely synchronized, and thus, we need a stronger argument to rigorously establish the above claim. In the next subsection, we show that under Coop-SE, the agents implicitly synchronize with each other.
Implicit synchronization of neighborhoods over intervals We now outline another core idea of our work: how agents implicitly synchronize under our algorithm, key component for proving individual regret.
Lemma Consider an agent v. Let j be stage index such that T.. > 16. Then every agent Sry/ /4 plays the same policy (i.e., has the same set of active actions) at time interval [t] [T 1r//41, + LT5/22]]
Proof sketch. Let us denote the active set of actions of at stage with AØ. Since dg (u, v) S ST//4 agent u receives all eliminations of A \ AZ from no later than fj + +T5 /4. Hence, after this timestep u's active actions in [t] + T + /2] must be contained in Aj. For the reverse direction, let E A². Assume by contradiction that encounters an elimination of before tj + TJ//2. Since hh/nt//4 dg (u, v) I TT /4, this elimination reaches within more than / additional steps. Therefore,
gets the elimination at t`j + 3/4r] < tj+1 contradicting the stage definition which requires the stage to end precisely when an active action is eliminated. Thus, all agents in /r /4 maintain exactly Aj
as active actions throughout [1y- + 7//4, 14 + /2]. See Appendix E.3 for the detailed proof. IT
Combining the results With the above result we get that in each round j that the action was active, the agent gets at least 7 |NN,,rr samples. Hence, the number of samples of an action that was active in the end of stage can be bounded from below. Let us denote the last round in stage
i with & ;= t++1 - 1. We get ny (a) 2 2j=1 E 7/AA,|Nsr,al Using standard concentration bounds, we show that the number of samples can see from sub-optimal action a, without eliminating it, is approximately 1/42. Hence, nyg (a) X 1/
On the other hand, we can bound N S with the stages and the number of agents m: N Ngr,/4 2 min (m, }.
Using the lower bound on the number of samples we get,
1 nz(aa) 2 Σ N
Tj 16A,
2 Σ
min (m, Tj Tj
2 ny
A
16A,
1=1
j=1
7

---

We split the analysis into stages where m < T;/4 and stages where m 2 Ty/4. The first case is simpler, while the second is bounded using Cauchy- These stages are used only for analysis, we ultimately bound Σ; Ii A, using only m, A., A, and T. Full details are deferred to the 4
appendix (see Appendix E.3 for this part).
Lower bound
In this section, we present a lower bound, demonstrating that our algorithm achieves near-optimal individual regret.
The problem we study in this paper is obtaining upper bound on individual regret which is independent of the graph's diameter or other graph properties. This means the bound should hold for any communication graph, and since we focus on individual regret, must hold for every agent. Consequently, when proving a lower bound, we can consider any graph, including the worst-case one, and we only need to identify at least one agent that incurs this level of regret.
Note that the lower bound is stated in the minimax form, where the sub-optimality gaps are on the order of / We believe this formulation captures the essence of the problem more clearly, though it be equivalently expressed in problem-specific form. For consistency, also provide the minimax forms of the regret in Section and in the appendix.
Theorem For every algorithm, and for every T, A, m, there exists a problem instance of the cooperative stochastic MAB over communication graph such that there exists agent for which the individual minimax regret is at least, S2 AT + VA).
Note that the statement specifies "there exists an agent", and cannot be improved to "for every agent". This is because, with least A agents, it is always possible for one agent to have zero regret by assigning each agent to select a distinct action for the entire horizon.
The primary implication of the lower bound is that even if m - oo, the individual regret still scales with the number of actions. The main gap from our upper bound the exact dependency in A in the additive term well as the logarithmic dependency; these gaps still remain open questions.
The lower bound combines two separate lower bounds, 21( / AT/m) and Si ((VA). The 2 B(VAT) /m) bound holds even in fully connected network and follows directly from the lower bound established by Ito et al. (15). We also remark that an instance-dependent variation of this lower bound, specifically @1(1- -=)) )μ² Σs,> ITg(T)/ (m)))) where μ² is the expectation of the optimal action, can be obtained using the same technique.
Recall that our upper bound holds for any graph and does not depend on the diameter. Thus, in order to show that it cannot be improved in general, it is sufficient to show a lower bound for a specific graph. Hence, to obtain the ((vAA) we focus on a line graph. The intuition of the proof is the following. We consider a deterministic MAB where one action has reward 1 and all other actions have reward O. An agent, during the first T timesteps receives ((72) observations. Therefore, S A//10, then an agent receives information about at most A 1/100 of the actions. We construct probability function where each optimal action has equal probability of being selected. Under this distribution, with probability 0.99, the agent fails to observe the optimal action, resulting in an individual regret of at least 0.99- VA/10. Therefore, there must exist at least one specific problem instance that induces this regret. For the formal proof see Theorem 10 in the appendix. Note that the technique employed for this lower bound can extend to other graph structures; for instance, grid graph can yield a lower bound of 2/4
7 Communication results
In practical distributed systems, communication constraints can significantly impact the performance of cooperative learning algorithms. We examined two restricted communication settings: The first limits messages to (log( Am)) bits, which corresponds to the well-known CONGEST model in distributed systems (see Peleg (3I). The second allows agents to send messages in only O(log(T)) timesteps throughout the entire horizon, a constraint sometimes referred to as communication cost in the literature. Our results show that effective cooperative learning remains possible even under these
8

---

constraints, with agents maintaining strong individual regret guarantees that do not depend on the diameter.
7.1 The CONGEST model
To establish our communication--fiii results, we begin by showing that our base algorithm Coop-SE, when operating on a spanning tree, can function effectively with reduced message size of [om(m))). This initial compression serves as stepping stone toward our full CONGEST model analysis, where we further reduce communication by having agents share information about only single actions at time.
The key insight is that we can aggregate information about each action without losing accuracy. Instead of transmitting individual reward observations and elimination events, we can simply maintain running sums of rewards and single elimination flag per action. This compression requires only O (oAloo(Am) bits per message, representing each action's 's new information: observation count, cumulative reward, and elimination status that reached to the agent in the previous round or produced by the agent in the current round. However, this aggregation is only valid when agents don't 't receive duplicate information. We achieve this by restricting communication to a spanning tree of the network, where messages are forwarded along the tree nodes. This simple modification eliminates redundant transmissions while preserving Coop-SE's regret guarantees, as our bounds are independent of the graph structure. Algorithm Coop-SE- SE-Restricted (Algorithm 9 in the appendix) implements these ideas.
For completeness, we note that our analysis assumes all agents share the same spanning tree, which can be computed in a preprocessing phase prior to the execution of the algorithm. Otherwise, we can use one of the many distributed algorithms for this purpose (see (31]..
Moving to the full CONGEST, let us now consider the case that the size of the messages is limited to O(log(AAn)) Am)) bits- - this is done using our algorithm COOp-SE-CONGEST (Algorithm) 11 in the appendix). Here is the high-level idea of the algorithm. As before, we construct original graph, and aggregate messages and avoid duplicates. But rather than sending A messages each of size (log((mA)) the agent sends in each round only one message regarding only one action. The action for which the agent sends the information is chosen in a round robin, without considering if the action is active not. The key idea that the round robin scheduling starts at different action for each agent. This mechanism ensures that when a message travels from any node v to the root node w, apart from the distance between nodes it will not encounter any delay after has been sent from its originating node. Similarly, messages from outward from the root will not encounter delay.
from the
Let us denote the spanning tree with T, and the distance the tree from to with d (v, w). The mechanism works as follows: agent v, located at distance d == dr (v, w) from the root to, sends messages for action to its parent, i.e., toward the root, at timesteps i such that t ++ d (mod A), and to its children whenever = t - d (mod A).
Here is example of how the idea works. For the up-stream, assume that at timestep & message about action a was sent from v to its parent 0. The message reaches é, which is at distance 1 from the root, at timestep t + 1. At timestep + 1 the agent i sends this message é's parent since t ++ ++ 1) = t + d = a (mod A), and the message continues up up-stream with no delay. Similarly for the down- Additionally, message that travels from to u might wait at most A timesteps at their common ancestor until the round-robin reaches this action. We get the following theorem.
Theorem When all the agents play Coop-SE: SE-CONGEST/Algorinn 77 in the appendix) the individ- ual regret of each agent V is bounded by,
R4 o Σ
log(mT ( A) A² + Avlog(mTAA)
m.
|E
7.2 Small number of messages
In this section, we present Coop-SE-Comn-Cont a variant of Successive Elimination that requires only Ollgg(T) communication rounds per agent. The algorithm operates in phases and commu- nicates along a spanning tree, clustering agents into groups of size at least min(2', 22', m) phase i. Within each cluster, the maximum distance between the cluster root and any descendant is at most

---

2 The existence and computation of such clustering is shown in Lemma 31 and Algorithm in the appendix.
Each phase consists of three 2 -eegthh steps: first, agents send information upward to their cluster root; next, the root determines the active set of actions and broadcasts it downward; finally, agents synchronously sample active actions, During the sampling step, no communication occurs. This structure allows each cluster to collect 02(2'... min m3) samples while sending messages in only (() timesteps per phase.
The analysis's ' complexity arises because agents determine their current phase's active action set using information from the previous phase rather than the current one. Let A₂ be the number of active actions in phase i (for agent v). Unlike single-agent phased algorithms,, to sample each costly action for 2' steps, since this would underuse cooperation. algorithm, the phase lasts 2 steps, and each action is sampled 2*/A, times and the regret scales as (2' //,AA)), To illustrate the problem, notice that the number of samples used for the elimination at the start of phase is inversely related A;- not to A,, in contrast to the regret. If A,-1 > A,, might be that easy-to-eliminate actions were eliminated at the beginning of phase i, leaving only the costly ones in phase i.
do not require agents
our phasing
We addressed this challenge through amortized analysis: phases with a low ratio of previous-to- current active actions (A,-1/A, I 2) effectively subsidize phases with high ratio. The complete analysis can be found in the appendix, specifically in Lemma [4] Formally, we get,
Theorem When all agents play Coop-SE- Cea---E-Coom--On Cost Coon-CCst(Algoriille (Algorithm in the appendix) the individ-
ual regret of each agent is,
log(m7 A) log(A) + A Alog(mTA) loggA) log(A)
Ry = 0
Aa
AEA
8
Future Work
Our work leaves several interesting directions for future works. First, our algorithms can either handle logarithmic message size or logarithmic number of communication rounds. An interesting future work would be achieve our near-optimal regret bounds while simultaneously maintaining both logarithmic message size and logarithmic number of communication rounds. Second, extending our results to other MAB algorithms, specifically, Upper Confidence Bound (UCB) and Thompson Sampling, would be very interesting. The technical challenge is that in UCB (or Thompson sampling) there are actions which are selected very rarely. Such actions can cause different agents to behave differently. Our methodology builds on having the different agents behave similarly (as is shown through the implicit or explicit synchronization). One can implement explicit synchronization at the cost of the diameter, which will result in significantly inferior regret.
Another interesting direction for future work is to more explicitly leverage the graph structure to improve cooperation efficiency. In particular, characterizing how the regret depends on the topology of the communication graph may enable reducing the additive term in our bound.
Finally, a natural open question is closing the gap in the additive term between our upper and lower regret bounds.
Acknowledgments
This project is supported by the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation program (grant agreement No. 882396), by the Israel Science Foundation and the Yandex Initiative for Machine Learning at Tel Aviv University and by a grant from the Tel Aviy University Center for Al and Data Science (TAD).
10

---

References
[1] Mridul Agarwal, Vaneet Aggarwal, and Kamyar Azizzadenesheli. Multi-agent multi-armed bandits with limited communication. J. Mach. Learn. Res., 2022.
[2] Peter Auer, Nicolò multiarmed bandit problem. SIAM J. Comput., 2002.
Yoav Freund, and Robert E. Schapire. The nonstochastic
[3] Yogev Bar-On and Yishay Mansour. Individual regret in cooperative nonstochastic multi-armed bandits. Advances in Neural Information Processing Systems, 2019.
[4] Nicolò Cesa- Baaa-Bianhi, Claudio Gentile, and Giovanni Zappella. A gang of bandits. In Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, 2013.
[5] Nicolò Cesa-Bianchi, Claudio Gentile, Yishay Mansour, and Alberto Minora. Delay and cooperation in nonstochastic bandits. In Proceedings of the 29th Conference on Learning Theory, COLT 2016. New York, USA, June 23-26. 2016, JMLR Workshop and Conference Proceedings. JMLR.org, 2016.
[6] Mithun Chakraborty, Kai Yee Phoebe Chua, Sanmay Das, and Brendan Juba. Coordinated versus decentralized exploration in multi-agent multi-armed bandits. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, 2017.
[7] Ronshee Chawla, Abishek Sankararaman, Ayalvadi Ganesh, and Sanjay Shakkottai. The gossip- ing insert-eliminate algorithm for multi-agent bandits. In The 23rd International Conference on Artificial Intelligence and Statistics, A/STATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy]. Proceedings of Machine Learning Research. PMLR, 2020.
[8] Ziqun Chen, Kechao Cai, Jinbei Zhang, and Zhigang Yu. Fair distributed cooperative bandit learning on networks for intelligent internet of things systems (technical report). CoRR, 2024.
[9] Alon Cohen, Yonathan Efroni, Yishay Mansour, and Aviv Rosenberg. Minimax regret for stochastic shortest path. Advances in Neural Information Processing Systems, 2021.
[10] Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying PAC and regret: Uniform pac bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 2017.
[11] Abhimanyu Dubey and Alex 'Sandy' Pentland. Cooperative multi-agent bandits with heavy tails. In Proceedings of the 37th International Conference on Machine Learning, ICMI. 2020, 13-18 July 2020, Virtual Event, Proceedings of Machine Learning Research. PMLR, 2020.
[12] John C. Duchi, Alekh Agarwal, and Martin J. Wainwright. Dual averaging for distributed optimization: Convergence analysis and network scaling. IEEE Trans. Autom. Control., 2012.
[13] Eyal Even-Dar, Shie Mannor, and Yishay Mansour. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. J. Mach. Learn. Res., 2006.
[14] Eshcar Hillel, Zohar Shay Karnin, Tomer Koren, Ronny Lempel, and Oren Somekh. Distributed exploration in multi-armed bandits. In Advances Neural Information Processing Systems 26:
27th Annual Conference on Neural Information Processing Systems 2013., 2013.
[15] Shinji Ito, Daisuke Hatano, Hanna Sumita, Kei Takemura, Takuro Fukunaga, Naonori Kakimura, and Ken-Ichi Kawarabayashi. Delay and cooperation in nonstochastic linear bandits. In Advances in Neural Information Processing Systems. Curran Associates, Inc., 2020.
[16] Ravi Kumar Kolla, Krishna P. Jagannathan, and Aditya Gopalan. Collaborative learning of stochastic bandits over a social network. IEEE/ACM Trans. Netw,, 2018
[17] Tal Lancewicki, Aviv Rosenberg. and Yishay Mansour. Cooperative online learning in stochastic and adversarial MDPs. In Proceedings of the 39th International Conference on Machine Learning, Proceedings of Machine Learning Research. PMLR, 17-23 Jul 2022.

---

[18] Peter Landgren, Vaibhav Srivastava, and Naomi Ehrich Leonard. On distributed cooperative decision-makie multiarmed bandits. In 15th European Control Conference, ECC 2016, Aalborg, Denmark, June 29- July 1, 2016. IEEE, 2016.
[19] Peter Landgren, Vaibhav Srivastava, and Naomi Ehrich Leonard. Distributed cooperative Eecision-makinge in multiarmed bandits: Frequentist and bayesian algorithms. In 55th IEEE Conference Decision and Control, CDC 2016, Las Vegas, NV, USA, December 12-14, 2016. IEEE, 2016.
[20] Peter Landgren, Vaibhav Srivastava, and Naomi Ehrich Leonard. Social imitation in cooperative multiarmed bandits: Partition-basee algorithms with strictly local information. In 57th IEEE Conference on Decision and Control, CDC 2018, Miami, FL, USA, December 17-19, 2018. IEEE, 2018.
[21] Peter Landgren, Vaibhav Srivastava, and Naomi Ehrich Leonard. Distributed cooperative decision making in multi-agent multi-armed bandits. Autom., 2021.
[22] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[23] Justin Lidard, Udari Madhushani, and Naomi Ehrich Leonard. Provably efficient multi-agent reinforcement learning with fully decentralized communication. In 2022 American Control Conference (ACC). IEEE, 2022.
[24] Udari Madhushani and Naomi Ehrich Leonard. Heterogeneous stochastic interactions for multiple agents in a multi- armed bandit problem. In 17th European Control Conference, ECC 2019, Naples, Italy, June 25-28, 2019. IEEE, 2019.
[25] Udari Madhushani and Naomi Ehrich Leonard. Distributed learning: Sequential decision making in resource-constrained environments. CoRR, 2020.
[26] Udari Madhushani and Naomi Ehrich Leonard. When to call your neighbor? strategic commu- nication in cooperative stochastic bandits. CoRR, 2021.
[27] Udari Madhushani and Naomi Ehrich Leonard. Heterogeneous explore-exploit strategies on multi-star networks. IEEE Control. Syst. Lett., 2021.
[28] Udari Madhushani, Abhimanyu Dubey, Naomi Ehrich Leonard, and Alex Pentland. One more step towards reality: Cooperative bandits with imperfect communication. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, 2021.
[29] David Martinez-Rubio. Varun Kanade, and Patrick Rebeschini. Decentralized cooperative stochastic bandits. Advances in Neural Information Processing Systems 32: Annual Confer- on Neural Information Processing Systems 2019, NeurlPS 2019, December 8- 8-14, 2019, Vancouver, BC, Canada, 2019.
[30] Nikola Pavlovic, Sudeep Salgia, and Qing Zhao. Order-optimal regret in distributed kernel bandits using uniform sampling with shared randomness. CoRR, 2024.
[31] David Peleg. Distributed computing: a locality- approach. SIAM, 2000.
[32] Abishek Sankararaman, Ayalvadi Ganesh, and Sanjay Shakkottai. Social learning in multi agent multi armed bandits. Proc. ACM Meas. Anal. Comput. Syst., 2019.
[33] Aleksandrs Slivkins. Introduction to multi-armed bandits. Found. Trends Mach. Learn., 2019.
[34] Chao Tao, Qin Zhang, and Yuan Zhou Collaborative learning with limited interaction: Tight bounds for distributed exploration in multi- bandits. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019. IEEE Computer Society, 2019.
[35] Po-An Wang, Alexandre Proutière, Kaito Ariu, Yassir Jedra, and Alessio Russo. Optimal algorithms for multiplayer multi-armed bandits. In The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, Proceedings of Machine Learning Research.
PMLR, 2020.
12

---

[36] Xuchuang Wang, Lin Yang, Yu-zhen Janice Chen, Xutong Liu, Mohammad Hajiesmaili, Don Towsley, and John CS Lui. Achieving near-optimal individual regret low communications in multi-agent bandits. In The Eleventh International Conference on Learning Representations, 2022.
[37] Lin Xiao and Stephen P. Boyd. Fast linear iterations for distributed averaging. Syst. Control. Lett., 2004.
[38] Lin Yang, Yu-Zhen Janice Chen, Mohammad Hassan Hajiesmaili, John C. S. Lui, and Don Towsley. Distributed bandits with heterogeneous agents. In IEEE INFOCOM 2022 IEEE Conference Computer Communications, London, United Kingdom, May 2-5, 2022. IEEE, 2022.
[39] Lin Yang, Xuchuang Wang. Mohammad Hajiesmaili, Lijun Zhang, John C.S. Lui, and Don Towsley. Cooperative multi-agent bandits: Distributed algorithms with optimal individual regret and communication costs. In Coordination and Cooperation Multi-Agen Reinforcement Learning Methods Workshop, 2024.
[40] Haoran Zhang, Xuchuang Wang, Hao-Xu Chen, Hao Qiu, Lin Yang, and Yang Gao. Near- optimal regret bounds for federated multi-armed bandits with fully distributed communication. In The 41st Conference on Uncertainty in Artificial Intelligence, 2025.
[41] Jingxuan Zhu and Ji Liu. distributed algorithm for multi-armed bandit with homogeneous rewards over directed graphs. In 202/ American Control Conference, ACC 2021, New Orleans, LA, USA, May 25-28, 2021. IEEE, 2021.
[42] Jingxuan Zhu and Ji Liu. Distributed multiarmed bandits. IEEE Trans. Autom, Control., 2023.
[43] Jingxuan Zhu, Ethan Mulle, Christopher Salomon Smith, and Ji Liu. Decentralized multi-armed bandit can outperform classic upper confidence bound. arXiv preprint arXiv:2111 109933, 2021.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract reflect the paper's content and the paper contains proofs for the claims.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer:
[Yes]
Justification:
We discussed the limitations and our assumptions throughout the paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

Justification:
The precise setting and assumptions are given in Section 2 All the theorems and lemmas are rigorously proved in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
15

---

Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ccpppi.ccppulli//uuuiu wwwiicccguie//eeeeeeeeeis CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
16

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: httpp::s////rriss...e http:///......occcttccccccccaea.
Answer:
[Yes]
Justification:
We followed NeurlPS Code of Ethies.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: We did not find any direct societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
17

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwppppsiipteeeee whworeeswthhhe....c. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
18

---

Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
19

---

The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non- standad components.
Please refer to our LLM policy hattps://neurips... 200ps//ee///0ooeeeeeee////////// for what should or should not be described.
20

---

A Other Related Work
Cooperative MAB with heavy tail distributions was M. They show individual regret bound that scales inversely with the number of neighbors, as opposed to the total number of agents, as in our regret bounds. Asynchronous model was considered by 7 In this model, agents do not have shared global system clock, and thus, it is harder setting than that considered in this work. Consequently, the regret bounds they achieve are significantly weaker, scaling as
I[A/m]+ (Tg(T") A. where A S A < <. AA-1- Directed communication graphs and random graphs was studied well. In 41 42 they considered directed communication graphs. Their instance-dependent regret has an additive term that is linear in the number of agents. In (28) they considered a setting where the communication graph is stochastic, such that messages have random delays and adversarial corruptions. Their regret has multiplicative factor that can be as large as the clique cover number. Best action identification using cooperation was studied in 14 where the network is fully connected and they also minimize the number of messages. Heterogeneous agents which observe their neighbors with some probability and minimize the group regret were also In [24] they derived group regret based on various properties of the graph and in [27] they studied group regret in multi-star networks. The case each agent having a subset of actions that are relevant them was studied in [38], and the group regret bound was derived. Linear contextual MAB with a network of users of similar linear utility was analyzed 44] Cooperation in Maarovv-eciiioon Decision-Processee (MDPs) has been studied in [23]. who have shown group regret guarantees in cooperative stochastic MDPs over a general network. In 177 they considered both the stochastic and non-stochastic cases in cooperative MDPs but only over a fully connected graph.
addressed by 24 27
B Summery of Notations
For convenience, the table below summarizes most of the notation used throughout the paper.
Da
The reward distribution of action
Pa
The expected reward of action a
The maximal expected reward
at
An optimal action
A.
The sub-optimality gap of action a
Naa
The set of agents at distance most from agent u
Nsa
For ease of notation Nga N see Remark
de(e, u)
The minimal path length (number of edges) from to u
t
The beginning of stage j of agent v; see Remark
Tj
The length of stage, of agent see Remark
A
The number of active actions in the j'th step of agent o; see Remark 2
log(3mTA)
(a)
The number of samples that u observed by the beginning of time t For ease of notation (a) n, (a); see Remark 2
ma(a)
(a)
The number of times agent u played action a until the beginning of round t.
ba(a)
For ease of notation ba(a) = bij (a); Remark 2
Pk
The policy of agent u at time
Aa
The set of elimination indices (with respect to agent v) with gaps larger than
A
T'
4;
The i'th action being eliminaed by agent
A;
The sub-optimality gap of o;
G-
The set of "Good Intervals": (jiT 16).
S,
The set of "Short Intervals": Gj & 7 < m) The maximum between the elements. V = max(a,b)
V
21

---

C Instance independent Bounds
The instance independent bounds follow immediately from the instance dependent bounds. It works generally as follows. The analysis divides the gaps into two. The first group of gaps the small gaps, where A, S / A This group contributes no more than T v T'
Iog(T)A T' =v /T to m the regret. The gaps from second group appear as inverse in the bounds, and we get log log(T)/mmAi) S
log(TT) Summing all the actions get / (ug(T)AT
D Omitted Proof from Section
Remark 1. The problem independent bound for Sus- Act is
..- O log(m(TAAy
AT
+ log A+ A).
m
Proof of Theorem Without loss of generality, we assume that D > 1. Let us define the good event as the event which in every timestep the mean of the action is the confidence interval. is 14). From Lemma the complementary event occurs only with probability of at most 1 1/T², and thus, adds no more than to the regret. For the rest of the proof will assume that the good event holds. Therefore, for all a,
described in detailed in the appendix (see Definition
UCB.(a") 2 nr* Ma LCB.(a).
Where (C) the upper confidence bound that was calculated at the timestep and similarly LCB,(a). Therefore at is never eliminated.
Let (a(a) be the number of suspended counts until the beginning of timestep t, i.e., na(a) Σ E.I(aa a}. Denote by (a) the total number of times that was played by all agents until the beginning of round I. L.e. B,(a) = f4 D-1 (a) = - Evev Ia" a}. Let to be the last elimination step which was not yet eliminated. By definition, since a was not eliminated,
LCB,, s UCB,,
Under the good event,
2 2log(3
2log(3mTA)
LCBi,(a') -i (a')
2 plaa))))))))))))))) -
V
nie (a+) V1
nto (a*) V
(3m3TA) T4, (a) V1 S mla) + /
2 2o (lm(( n1, (a)
UCB,, (a) pra (a) +
where x V max (ax Combining with the last display we get,
A, / log(3mITA)
log(3mL ne. (a+)
16(log(3m11A) V (mn, m) V
+ VV
ne. V1
16 16log(3mTA)
- (a)
+ m
A3
where we've used the fact that active actions are played at the same rate, and thus the number of suspended counts of two active actions differs by at most m. Sicne to is the last elimination step in which a was not eliminated, a was played is no more than Br,, (a) + m times (in ta the agents still didn't eliminate a). Thus, the total sum of regret form action a is bounded by.
(m + Br, (a))Aa m Da + ne, (a) + (Br, (a) nt. (a))
16 16log (m
2m A
+ (a) T4., (a))
22

---

Denote by (a) the number of active actions at time tg. Notice that every agents waits at least D timetsteps before the first elimination, hence to 2 D. We can bound the last term above by,
Bi (a) - T4. (a) =
I4a = =a}
(2)
D+1
to
Haj = a}
r=lu-D+1
mD
Σ
((aa +11 1 +
+ m
(3)
o (aa)
where the inequality holds since there are at most D 1 timesteps, and the agnet chooses the actions in round robin. By combining ( and (3) summing over the actions, and noting that
Enda c[aj log A + (regardless of the climination order, see Lemma 7), get that the total
regret is bounded by.
16 16log(3mTA)
Σ d=
2m A. +
mD A + 1) + m.A
Aa
Finally, since all agents play the exact actions get the the individual regret of each agent is bounded by,
16 16log(3mIIA) + D(log A A+ + A
RT S
Σ
2A, +
m.
agaa
16 1og
+ D(log A + +3,
mA,
where the last inequality since E. A. S A. This finishes the proof for the gaps dependent bound.
Now we will reach the
bound. All actions with small gaps, {a E A|A. S to the regret. There are at most T round in which the agent
Tm contribute no more than
AT m
chooses actions with small gaps, their contribution is bounded by TV Tm
AT
For large
gaps, i.e., Da we get
16 log log A)
T'm A
AT
Σ
S 16 16log(3miTAA)
A) m
m
0.36 A..
Putting all together with the small gaps and with the good event, we get
AT
Ry S 17(log(3mTA))
m +
D(lo +1 + 3.4
E Proof of the Main Theorem
Remark 2. For the ease of notation, the following proof and definitions focus on specific agent,
named v.
E.1 Definitions
Definition 1. A stage is timestep-intent interval when its boundaries are the eliminations. The stage's 's index usually denoted by j. The time interval split into different stages. Assume that the elimination timesteps are 81, 82..... The first stage starts at 1. = and ends with the first elimination. Le., it is the timesteps that are in time interval (1,81) The second stage is (81, 82), etc. Denote 1 to be the timestep in which the agent started the j 'tth stage, where t = 1 and t = T +
23

---

Definition 2. Denote T to be the length of the j th stage (for agent v).
Definition 3. Denole A₃ - j j+ to be the number of remained actions in the j I'th stage. Definition 4. Elimination index of the action a is the stage index in which in its end the action is eliminated. Every action has a unique elimination index.
some actions are eliminated in the same timestep, then the stage of zero length and the elimination index are chosen arbitrary. The elimination index of a is denoted by ia. and the appropriate action for elimination index is denoted by 04-
Definition 5. Denote with A& the set of elimination indices of large gaps. As = (i] 2
Tm
Definition 6. For the ease of notation, denote A; == Da.-
Definition Define the set of "Good Intervals" to be the set of long enough intervals: G, {ilT 16A5). These are the intervals we will focus in the proofs.
Definition 8. Denote the group of indices of short stages with Sr. Specifically,
S, = {ilá E G. & Ty/4 < m]
Definition 9. Denote the number of samples agent sees for action a until the beginning of timestep with ni (a). For the ease of notation, denote n, nr(a) ;= (a).
Definition 10. Denote by by (a) the number of times agent u played action a until the beginning of round t.
Definition 11. Denote the maximum of elements with V, ie., V := max(a,b)
Definition 12. Denote the upper confidence bound for agent u for action with UCB"(a) (a) = (a(a)
2 Al where n(a) is the number of times agent u observed action a, and (a(a) is the n(a)vi
empirical mean calculated by for action a. Similarly, let LCB n(o) (a) j((a) - Al n(o]vl denote the corresponding lower confidence bound. In other words, UCB (a)a)(a))))) and LCB" nla) (a) are the confidence bounds calculated in Algorithm 5 Equation (20) when agent u calls this algorithm with parameters n, a vector containing the number of observations for each action, and the vector of empirical means.
Definition 13. Denote the logarithmic term used in Algorithm 5 with i, i.e., 1 = log(3mTTA)
E.2 The Good Event
The good event G captures the intuition that the true expectation of each action is between the UCB and the LCB.
Definition 14. Define the good event, G to be the event in which for every agent u, for every action and for every rud-event that was received, the empirical mean is in the confidence interval, i.e.,
Pa E |LCB UatBa
where n(aa is the number of rud-events that received for this action by the agent Lemma 2. The good event G happens with high probability. Specifically,
PP-G') S 3m A
37
Proof. Event - Denote (k) to be the k'th rwd event agent u received for action a. Define
(a) = Σx= (M) Pa) and An = / 26 Note that (a) is martingale. From Azuma's
inequality we get
(a)
1
Pr
Ma
Am
3m
There are at most m T rud events the agent can get. The same holds for every action and for every message. The upper confidence bound (UCB(() defined as (a((a) + Xn and the lower confidence bound (LCB) is defined as X (a) An. From the union bound we get that with
24

---

high probability for every agent, for every timestep, for every action and for every rwd event message the agent get, the actual mean of the action would be inside the confidence bound. Specifically
G = vu E V, E A, [m TM (LCEE(O)
P(-G") S 3mT² S 37
E.3 Proof of Theorem 2
Lemma 3. The complementary event of the good event adds no more than the regret of each
agent.
Proof. From Lemma the complementary event of the good event happens in probability lower than
7z. Every agent plays timesteps, and the gaps are bounded by I, i.e., for every action a we have A, S 1. Hence, in expectation, this adds at most + I 1 to the regret.
In the proof from now on, we assume the good event holds.
Proof of Lemma D Let t E [ty + [rj/44, LTj /2]] and let E N Sry//4 Denote the set active actions of the j 'th stage as AV. We will show that an action is active for u at iff a E Aj.
Let be an active action of at time i, where t [t, [Ty/41,t, [r//2]]". Since E N Srj/44 have dg (u, S T The distance (u, v) is natural number, so it is at most [rj/4JJ Therefore gets all v's climinations (the first - eliminated actions) until the beginning of round tj + LTj//4] By the stage's s definition, the agent doesn't It encounter any new elimination. Therefore, along the stage, she doesn't 't send any new elimination event regarding her active actions. Hence, for any 2 ty + [T]/44 /4], [ u does not have any active action which is not in Añ. Hence, a E Aj.
Let a be an action in A.- We will show that a is an active action of u at time 1, where / E [y + [4/ 17 + LT5/22 /2]]. Assume for contradiction that u, at timestep tý + [T5//2] or before, encounters an elimination of a. The elimination event should arrive to in no more than LT)/ /4/
timesteps, should get the elimination event at most timestep + LT))
But TJJ 16A, 16, then / > 4, so fy 3r" < t5+1 -4. 4. Therefore, the elimination event begins. This is
about an action in A" should arrive to v at least 5 timesteps before stage contradiction to the definition of stage: a stage ends when an active action in this stage eliminated, and not before. Therefore, a is an active action of u at t.
We get that for every E [ty + [rj/41, + LTf) /2_] and for every u E No Syy/1> the active actions of u at are exactly Aÿ. In other words, we get that in time interval [t" + [T.] 27//41,25 tj + 12,] all agents No ST//1 /1 play the same policy, i.e., choosing randomly from Ay.
Lemma 4. For every action that was not eliminated before the end of stage i, we have
T 11:1-1(01) ((0)
Σ
T 8A,
INN
j=LjEG,
Proof. In each stage j E Gr, all the samples that each agent in Nsr,/4 produces reach agent v before the end of the stage. Therefore, each agent contibutes at least [7,/(4A)) samples. Since j E G [Tg/(4A;)] 2 (8,,)
Lemma S. For every action that was not eliminated before the end of stage i,
Σ
Id
N
256
Ag
A
j=l.jE,,
25

---

Proof. Fix an action that was not eliminated before the end of stage i. Denote t' f++1 - 1. The action a is still active by agent time t', and thus, UCB; 2 LCB;(a")) Note the slightly abuse of notation, when UCB (a) is actually UCB (a) (a), and the same for LCB. Under the good event G
Ma + (a) 2 (a) 2 (CB 2 Ha 2x²(a").
Rearranging it we get,
21
Aa S 2
2 Tee (a*)
(a((a)
Recall that under the good event, a" is never eliminated. Thus, apply Lemma on both and at and further bound Aa by,
2O
A S 4
| l.ja, 8A,
I NNr,/Al
then
2r
A Σ 16
Σ
jj=ljEG- 8 N555441
we get
Σ
Tj
I |Nst,/ll=
5 A3"
32
84,
j=1.jEG,
and,
Tj 8A,
N NF S A
32
j=1,EEG,
By rearranging terms get the Lemma's statement. Lemma 6. For any 2 0
min(T, S |N
Proof. The graph is connected, so either there exists an agent at distance [r] from v, in which case Ngr 2 [r] 2 T, or all the agents are at distance at most T from v, in which case Ngr = m.
Lemma 7. ΣØ 2/2 log A+1
Proof.
Σ
Σ
1
Aj
A
A-j+1
j=1
j=1
A Σ
-=1
1+
<
+
dx
+ log
26

---

Lemma 8. The regret of agent (under the good event) of action from stages j G. is bounded by
2Tj Aj
A
Proof. In each round that action is active the agent plays it at most [T//A;] times. Since we count here only the regret from the "good stages", i.., j E Gy, [T//A,] s Arz/Aj-
Lemma 9. The regret for all actions from the stages & G- is at most 16.42
Proof. There are at most A such stages. Each stage is at most of 16A length. The gaps are bound by and the result follows.
Lemma 10. For every action elimination index i, it holds that
Σ
Tj S A
256r
4Aj
Aj
j=L.EEs,
jmIjEG, As,
where S, = filj G, & 7,/4 m), and [Tylí [A]] are the stage lengths.
Proof.
From Lemma 5
Σ j=L.jEG,
Ta
N
ST5///l S A2
256r
A
On the other hand, using Lemma
Σ
Ij
N
2
Tj min(m, ///4]
A
Aj
j=IjEG,
j=1,EEG
Tj m j=1.jEG\\5.
4Aj
Aj
j=1,jES,
Lemma 11. The regret for action a; from stages G most
512: mA,
64V
Σ 1=1 Ay
(5)
Proof. We'll break the the regret per action into "short stages" and "long stages", where both "good stages". Specifically, we define S, = [j:3 E G. & T < m) and break the regret per action into two:
2(
Σ
3 A +
Σ
TA). A,
(6)
A
j=IJES,
j=1.jEG+8s
For the first term above, using Lemma
Σ
1A
A
Tj
A
A
j=
256r.
(7)
mA,
27

---

For the second term, using Cauchy-Schwarz Schwarz inequality
Σ
JASSA.
Σ
7
Σ
Aj
Aj
Aj
j=LjES.
j=1JES,
256
A
A
1
I
1004
A
1
32
A
1=1
where the second inequality is from Lemma 10
Lemma 12. Σ
Ej गे A A
Proof. Using Cauchy-Schward inequality
VA
A
V
A
A -1
VA
Σ
A
A
V
Σ
= A.
Theorem 6. When all the agents play Coop -E, i.e., Algorithm 6 the individual regret of each agent
U is
512 log (3MTA) A)
Ri
64 Av/og(3mTTA) + 16A2 11643 1.
mA;
Proof. From Lemma 3 the complementary event of the good event adds no more than to the regret. Let's assume that the good event hold.
From Lemma the regret of all stages j & G. is at most 16.42. Using Lemma 12 summing over all actions we get the second term in Equation (5) is bounded by 64Avi. Combining this with the other terms in Equation (5) yields the part of the bound corresponding the good event. We get,
512 logglo03 (3mTA) A)
Ri <
+ 64 Avlog(3mTTA) + 164² + 1.
m.;
EA
28

---

Theorem 7. When each agent plays Coop-55 SE the regret of each agent is also bounded by
512 (3mT A) 16AD +1
Mt
mA;
Proof. When we take into account only stages that are longer than 16D the other stages adds more than 16AD. The analysis of the regret that stems from the stages {i Ty 2 16D) can be simplified, compared to when the stages are {j T 2 16A,). In each such stage in which Ty 2 16D, N the entire graph. So Lemma becomes
Σ
T m
Σ
TJ Aj
N Sr,
N
256r A
A
J=1.7,216D
j=1,7,216D
And the regret in Equation (6) becomes only the first part. Lee., Equation 7 the term that left. The term that was solved with Cauchy-Schwand does not appear when the neighborhood is the entire graph.
Proof of Theorem 2 Theorem
The proof follows immediately from the two regret bounds, Theorem and
F Proofs for Random Choices in Coop-SE
Theorem 8. When all the agents play coop-SE-rand. i.e., Algorithm 6 with random choices, the individual regret of each agent is,
TA log(mTA) (
+ log(m'T
m
problem-specific flavor an individual regret bound can also be established:
Theorem 9. When all the agents play coop-SE-rand, i.e, Algorithm O with random choices, the individual regret of each agent E is
log(mTA) Alog(mTAA)
Ry O
Σ
mA.
A >0
F1 Definitions
Definition 15. Denote with A the set of elimination indices of large gaps. As = (ilAa, 2
Ac Tm
V
Definition 16. Define the set of "Good Intervals" be the of long enough intervals: G, {jlt, > 16). These are the intervals we will focus in the proofs.
Definition 17. Denote the group of indices of short stages with S,. Specifically,
S, = Lilj G, & T2/4 < m}
Definition 18. Denote the number of samples an agent sees for action a until the beginning of timestep with ni (a). For the ease of notation, denote ny n₂(a) : : (a).
Definition 19, Denote by by (a) the number of times agent u played action a until the beginning of round
F.2 The Good Event
The first good event G captures is the same as the one that was defined earlier.
Lemma 13. Let be an agent and let X (a) = Ia("" a) be the indicator that w plays action at timestep I. Then for any agent u, timestep I, and action a,
n(((a) = Σ Σ
(a)
WENU
29

---

Proof. Let w be an agent such that w & u and dg(w, u) = d. Every X (a) reaches at the end of round k + 1.1 Therefore, it contributes ni (a) timestep t' k d. We get that for * E N St-k- (a) reaches u until the beginning of timestep I.
Now, let w = u and < t. An agent u uses the information she creates only at the next timestep.
Since do not sum the information for the current timestep f, i..., f 2 1, the information
creates is summed only for timesteps that passed. In other words, for w = u, X (a) is summed only at timesteps t' < f, for them the information reaches until the beginning of t. Therefore, that for all < I, E N X (a) reaches until the beginning of timestep l. Summing over all the timesteps which information action
get
be produced and obtain the result.
The second good event G2 requires that the number of observations of an action is not much less than the expectation of the number of observations.
Definition 20. Define the good event G2 to be the event in which for all u E V, action a and timestep t T simultaneously,
ni (a) 2
(k(a) 21.
o WENT WENS
The third good event G requires that the number of plays of an action is not much more than the expectation of the number of plays. Definition 21. Define the good event G to be the event in which for all u E V, action a and timestep t e T simultaneously,
(- (a) 2 Σ pk(a) + 12c
Definition 22. The good event is the event in which all the previous sub-good-events happen. Lee,,
G G==G-U- G
The following lemma show that with high probability all the good events hold. Lemma 14. When all agents play Algorithm 6 with random choices the good event, G = G U G3, happens with probability of least
Proof. We will show that each of the events - G2 and -G3 happens with probability of most 1
322 Thus, by the union bound, G occur with probability of at least 1 T
Event - Fix an action a and agent Let Xx = I[a = a} and Ft.. be the sigma algebra induced by the first 1 rounds; and the actions chosen by the first we assume linear order on the agents for example the alphabetic order induced by their IDs). Notice that F.,1 is induced simply by the first E|X,, F PK (a) and that Xk.w is Mhatt-measurable (or if w is the last agent, Xx, is Fx+1,1 measurable). By applying Lemma 46 with probability 1 974A2m for all E [T] simultaneously we have,
agents in round (where
rounds. Note that pK (a) is measuualee..
n (a) = Σ
Σ
(a)
Σ
Σ
(a) - 22,
2
1=
WE N
w Si-
where the equality is from Lemma get that IP(-22) 1/(9mAT2) S I/TT2)
13
By taking the union bound over all actions, a, and agents u we
Event G Fix an action a, agent u and timestep 1. Let X, = T[a a) and F, be the sigma algebra induced by the first & 1 rounds. Note that p ( is Fe-measurable, E|X2 Fi] = (a)
and that X₃ is 7e-1-measurable By applying Lemma 47 with probability Amma
6% (a) = Σ (x(a)= <
Σ (a) + 12. k=
k=
30

---

By taking the union bound over all time steps t, actions a, and agents u we have P( - 277-A-m2
Taking the union bound over -G U -G U-U-CC U-G and from Lemma we complete the proof.
Lemma 15. The complementary event of the good event adds more than 1 to the regret of each
agent.
Proof. From Lemma 2 the complementary event of the good event happens in probability lower than Tz. Every agent plays T timesteps, and the gaps are bounded by i.e., for every action a we have
A 1. Hence, in expectation, this adds at most + I 1 to the regret.
F.3 Proof of Theorem
In the proof from now on, we assume the good event G == GD UZ G holds.
Remark 3. Note that in the proof of Lemma 7 we used Tÿ > 16 and not T 16Aj Hence, the results follows immediately here as well. We will use the same lemma, Lemmal 4 here as well.
Lemma 16. For every action a that was not eliminated before the end of stage we have
ne. (a)) 2
Tj Ti ST,5 /1l - 21.
16A,
J=1,EE,
Proof.
Under the good event G²,
4
B 11) 2
Σ
(a) 2t
2
[=1
NENgt:
i 4
Σ
Σ
(a) 2
2
j=1
NEN
1/////2
Σ
Σ
Σ
pT(a) - 2
2
1= I,E t IT// MEN WENEet11--2
L/
Σ
Σ
(a) 2t.
2
j=I,EGG + WENery
The second incquality is by splitting the rounds to stages and summing partially. The third inequality by summing partially over j E G, ([T,/2] | I T - ---2),, 2). The last inequality since
N /4 S. &Nst.1it-- -1- for all j [ 2 G, and & $ t, [7/2]]
f++1 - 1++1 t, - |2]
2 т - T2 3 3 T2
7//4.
Finally, by Lemma ! all agents u E N play the same policy at time steps E it + 745/44,6 ty [r//2]] which is uniform over the active actions. L.c,, (a) = X for active actions in it.
[T /4, ty [2. The interval [t, + [ry/4],t + [1, is of size at least 7,/8, since t; -2
[r/4] -t, 11/2 2
2
Ty. g when the last inequality follows from the that
for for every G.. 16. Thus,
Σ
Σ
(i(a) N
Ty 16A;
| N
j=L.jEG, t=t++/1//4
j=IjEG.
as desired.
Lemma 17. For every action a that was not eliminated before the end of stage i,
Σ
Id
N <
544
A
A
j=l.ee,
31

---

Proof. Fix an action that was not eliminated before the end of stage i. Denote t' f++1 - 1. The action a is still active by agent time t', and thus, UCB; 2 (CB"((") Note the slightly abuse of notation, when UCB (a) is actually UCB good event G
(a) (a), and the same for LCB. Under the
Na + (x) 2 (C) 2 (C 2 pa 2X)(
Rearranging it get,
2r
2t nee ne (a*)
A, S 2
21
nr (a)
Recall that under the good event, a" is never eliminated. Thus, we can apply Lemma 16 on both and a and further bound A, by,
2r IN |N -2
A S 4 V
Σ Ej=.jEG, 164,
then
2 NNs//al 20
A S 16
Ej= IJEG, I64,
we get
Σ
Tj 16A,
N Wrr 2
32i
A?
jmm jmIJEG,
and,
Σ
| /N
<
32t
+
2t <
34
164,
A
A?
j=1jEG,
By rearranging terms we get the Lemma's statement.
Lemma 18. When all agents plays Coop- Poop-SE with random choices, the regret of agent v (under the good event) is bounded by
Ry 2 Σ Σ
TS J
TA + 44Ai
(8)
Aj
m
iEAA j=l.jEE,
Proof. Under the good event,
Disbn (a:) 2 Σ
pk((:)) + 12c
1=1
1
2 J=l t=
Σ pT(a:) + 12c
Σ T
+ 12
Ag
j=1
32

---

Now the regret can be bounded by,
Ri = Σ
bears (a:)a
SE[A]
2 Σ
A + 12AL
A
KE KA| j=1
2
A + Σ
bl (ai))
Ae T'm
+ 12Ac
A
iE4x ;=1
iEAD
A
2 Σ5
A + T
+ 12AL
A
Tm
iEA j=1
2 Σ
Σ
3 1 E
Σ
TA
+ 12A
iEdD j=ljEC, Aj
Aj
m
iEAA j=IjEG,
< Σ
Σ
Tj A
A
44AI,
Aj
m
1EAa/=1,,E0
where the last is since,
A
Σ
A S
J
Σ
16
AA
16 Aj
I 32A log A.
Aj
Aj
KEAD IJEG,
kEAAj=l
3=1
as Σe= 2, S log A + by Lemma
Lemma 19. For every action elimination index i E As, it holds that
Σ
544c
4Aj +
S
A A
j=1.jES,
j=I.EEG X8,
where S, == Lili G, & T,/4 m), and {Tyli e [A]] are the stage lengths.
Proof.
From Lemma 17
Σ
I1 NNts/all
544
A,
j=l.eE,
On the other hand, using Lemma
Σ
I Ag
INs//122
Σ
Ij min(m, 7j/4}
Aj
j=IjEE,
j=1,EEG
Tj m
4A
Aj
J=LJEES
j=1jeG, AS,
Proof of Theorem 8 Let us write again the Right-Hand- Hand-Side of Equation
3
TA m
2
+
44AL
A
iEdA j=L.jEG
33

---

Note that the bound on the regret that is depicted in Equation 8 assumes that the good event holds, and we later will remove this assumption. Let's assume that the good event hold. We'll break the first sum in the Right-Hand Light-Hand-Side Side of Equation (8) as
Σ iEAAJ= J=jjE,
Σ
7 A A
Σ
T
D
(10)
Aj
TEAL j=LjjE.,
and we remind that S, {j : G, & T//4 for every E As.
m). For the first term above, using Lemma 19
A A
4
Tj
Aj
Aj
j=I,EE, A8,
j=,,,EG,
544.
(11)
mA;
Te
5
mA
where the second inequality is since i E Aa. Summing over all elimination indices in As get that the first term in Equation (10) is bounded by 544 AA
For the second term, for every i, using
Schwarz inequality
JASA
SA
Σ
Aj
Aj
Aj
j=I,EEs,
j=1JES,
j=I.jEs,
544
$ A
A
Aj
S 2216
Σ
1
j=1 Aj
Using Lemma 12 summing over all actions get the second term in Equation (10) is bounded by 47AVT. Combining this with the other terms Equation (8) yields the part of the bound corresponding to the good event. From Lemma [5] the complementary event of the good events adds no more than to the regret. We get,
where the second inequality from Lemma 19
TA
T
Ri S 2. 544
V
+2. 47AVi +
+ 444 +1
m
m
TAb + 94Ac +
TA + 44Ac +1
1088 <
TA
1089
+ 138 +1
T logmm33 A)
1089
138. log (3mTT + 1.
F.4 Instance Dependent Bound
It is important to note that when the analysis is not split into large and small gaps, bound specific to the problem instance can also be derived. We can conclude that the individual regret bounded by,
Σ mdo
a:
34

---

as depicted in Theorem 9
Despite being suitable bound for various scenarios, there approximation. For example, two action and the gap is A, = 1/7 m. We will get regret which is linear in T. We have made this distinction between large and short gaps be problem independent.
where it fails provide good
Although the changes that yield the instance dependent bound are simple, we provide for clarity the relevant parts where the proof changes.
Lemma 20. Under the good event, the regret of agent v is bounded by
Rr 2 2 Σ Σ
3A
+ 44A.
(12)
|E[A) Aj
Proof.
The proof follows the same steps as Lemma 18 but without splitting the gaps as Equation 9
Lemma 21. Under the good event, the following holds,
Σ
Σ
Tj JASS Aj
Σ (E(A),A;>0
544.
+ 47AVI.
mA,
A
Proof. The proof follows the same steps as the proof of Theorem but treating all non optimal actions the same. and stopping the analysis in Equation (11). i.e., without bounding the expression with Ti/mA.
Proof of Theorem 9 The proof follows by combining the results of Lemma 20 and Lemma 21 and with the fact from Lemma 15 that the complementary event of the good events adds no more than
the regret. We get,
Ri 2 Σ Σ
IA
44Ar + 1
Aj
iE[A] j=1.EE,
2
Σ
544
+2 +2.47A/L
+ 44A +1
mA,
1088
E
94A
44Ar +1
mA,
=
Σ
1088
138A +
mA,
log(3mTA)
1088
Σ
+ 138A log(3mTA)
+
mA;
(E[A),A;>0
G Lower Bound
Theorem 10. For any algorithm, there exists an instance of the cooperative MAB over com- munication graph problem, for which the individual regret of any agent is bounded from below by
2(VA) < RT.
Proof. Let the graph be a line of length at least T. Lee, m 2 Let be the number of actions such that V > Let a* be the only best action. Let A, = 1 for every a + a". Namely the reward of a" is 1 and the rewards of the other actions * a" is 0.
35

---

Let be an agent in the graph. After t timesteps, the maximum number of samples sees, for all actions together, no more than (2 + + 1)t/2= (t + 3)8 (twice the sum of arithmetic series).
At timestep V AA/20 the agent sees at most 4+30vA samples for all the actions together.
400
From the assumption on A,
3vA 40
I 200
implies that
+ 30v
A
A
3VA
-
+
400
200
20
100"
It means that until this timestep, the agent didn't 't see at least 0.99.A of the actions.
Let randomly choose instantiation of the best action a". Define the random variable X that chooses the best action uniformly. Le., P(X = a) = 1 Denote the event in which the agent doesn't 't see the best action until timestep
A
vA with E. From the above, event happens with probability at 20
least 99 Lee, IPE))= 2
99 Under event E, from the assumption that Aa = 1, the regret until this
100
100
timestep is
V and we get
V < Ry.
20
20
For any algorithm the agents play,
99
A
E (RT))
1).
100
20
Therefore, for any algorithm, there exists an instance such that Ry 2
99
( (VA
1).
100
H Bounded Communication
This section relies on the definitions and theorems that are depicted in Appendix
E
We introduce a new event type, the aggregated event for many rewards.
Definition 23. A reward-many event is tuple (rudMany, v, T, n. that represents aggregation of many rewards, where e is the agent's 's ID, a the action, r is the reward, and n. the number of samples of this event.
Remark 4. The good event occurs with probability higher than or equal to 1 1-T/ when all agents play Algorithm 9 Although this algorithm uses the rudMany events, the same proof of Lemma applies also to them, but the graph is the induced tree.
Proof of restricted communication. In Algorithm 9 we do not have duplicated messages. We achieve this by the tree structure, and by not sending to a neighbor u information that u already sent to v. The tree structure guarantees that there is only one path from agent to another. This property ensures that a message originating from one agent will reach all other agents exactly once, as it traverses the tree along the single possible route. Consequently, the combination of the spanning tree structure and the selective forwarding of messages allows for efficient and duplicate-free communication among all agents.
The Coop- Senp-SS-Resttee Restricted algorithm aggregate all events regarding an action a into two events: rwdMany for rewards and elim for elimination. The message contains information about action its elimination status, observation count, and sum of observed rewards, requiring O log( Am)) bits. This is all the information agents need from multiple messages.
Therefore, the agent has exactly the same information all agents had played Algorithm 6 on that spanning tree. The individual regret bound that is induced from Coop-SE does not depend on the structure of the graph, therefore the same regret bound applied for Soop-SE-Restricted as well.
The agent sends to each neighbor 2A events. Each event has O(log(Am)) bits. Therefore each
message is bounded by (A log( (Am)) bits. This completes the proof.
H.1 CONGEST Model: O (log(AmT)) Bits
Remark 5. The problem independent regret bound for Coop- SEoopSEECONNEEE CE--CONGETT is
Ri o (V TAlogmmTA) + A² + Alog(miTAA)
m
36

---

Lemma 22. Let u, u be two agents such that either is a descendant of or u is descendant of (with respect to the root w). When all agents play Algorithm 17 every message sent from arrives dr (v, u) timesteps after it has been sent (and vice versa).
Proof. Let us first assume that is descendant u. Every message contains information about one action. Denote that action by for the message that has been sent from We will prove the lemma by induction on dr (v, u).
dy (v, u) = 1: Immediately true.
Let's denote the timestep when the message was sent with to. Let's assume the claim is true for now assume the distance is d + 1.
The message is sent toward the root at to + dy v) (mod A). One of u's children, is on the path between v and u and is with distance from v. Since is descendant of u, it is also descendant of z. Therefore, from the induction hypothesis, at timestep message. The message is sent from x to u at timestep such that + dr (2, w) = a (mod A). 1= since to d + dr w) = lo + (v w) (mod A). Then u gets the message after (1( + d7(u, u) timesteps.
+ d, receives the
Similarly, assume is descendant of u. We will prove by induction d7(u, u). dr(v, u) = 1: Immediately true. Let's denote the timestep when the message was sent out with to. Let's assume true for d, now assume the distance is d + 1.
The message is sent from outward from the root at to do (ws, v) = a (mod A). Let be u's parent and note that is also descendant of v. Therefore, from the induction hypothesis, at timestep to + d, receives the message. The message will be sent from (mod A). 1 = to + d since to + d d7(2, w) to d7(v, w) (mod A). Then gets the message after dr (v, x) + = dr u) timesteps.
at timestep such that t- t-att-dy(e dr w)
Lemma 23. When all agents play Algorithm everr reward information that arrives to one agent v timestep and was not produced by another agent u, arrives agent most at L+ (v, 42 Where reward information is a reward from some action some agent experienced.
Proof. Let's denote with x the common ancestor of v and u, i.e. the closest agent to the root among all the agents shortest path from e to u. Notice that it is possible that v = and that z. We have that both v and are either itself or descendants of x. The reward information that reaches at timestep can wait A timesteps at e before being sent, since v sends the actions in round robin. From Lemma 22] after being sent from v toward the root, the message that contains the reward information arrives after (v, 2). At it might wait again for A timesteps, because of the round-robin sending the actions. After the message is sent from æ to u, takes d (2, u) timesteps to arrive at u. per Lemma 22
Overall it took the message pass from to more than d7 u) + 2A
timesteps.
H.1.1 Good Event
The good event for this section is exactly as in Appendix
H.1.2
Adjusting the Proofs
Definition 24. The "good intervals", G',,from now on are Tj > 32A. G², (ilr, 32A).
Lemma 24. Assume all agents play Coop-SE- SE-CCOTE Let j be stage index such that Tj > 32A. Then every agent u E Ner,/a /4 plays the same policy (i.e., has the same set of active actions) time interval [t, ( 35,//8,444 12 + [T./2]].
Proof. Let E [t, + / + 1r,/2[] and let u E Ngr,/4-
Denote the active actions of in the j' stage Aj. We will show that action is active for 1 iff a E Aÿ.
Let be active action of u at time Since NSr,/t, have dg(u, (u, v) S 7
37

---

From Lemma 23 gets all v's eliminations (the first j 1 eliminated actions) until the beginning of round ł, + [T/44] + 2A. Since T > 16A we get + [T,/4] +2 <
+ 3T,/8.
By the stage's ' definition, the agent v does not send any elimination event about one of her active actions until the end of the stage. Therefore, for any t' 2 1 + Bry/88 u does not have any active action which is not in Aj. Hence, E Aj.
Let be action in Aj. We will show that is active action of time t. Assume for contradiction that u, at timestep i, + LT//2] ] or before, encounters an elimination of a. From Lemma 23 the elimination event should arrive
in more than LTy/4 2A < /T, timesteps, so should get the elimination event at most at timestep 1 + [Ty/2] 1 S +
But Tj > 16A, then T;/8 >> 2A > 2, so + 7r < l+t1 2. Therefore, the elimination event about an action in Aj should arrive to at least 2 timesteps before stage + 1 begin. Contradiction. Therefore, is an active action of at t.
8.
We get that for every E [t, + [3ry/8], & + LTy/2]] and for every E Nsr//4. the active actions of u at are exactly Aj. In other words, we get that in time interval [L [3y//8], Lj [Tj/2_] all agents in S plays the same policy, i.e., choosing randomly from Aj.
Lemma 25. When all agent play Coop-SE-CONGEST (Algorithm 77
each sends no more than
O(log(mA)) bits per messages.
Proof. According to Send-One-Action procedure, agents sends only one elim event or one rwdMany event. An elim message is of size 1 + log(m) log(A), A rwdMany message is of size + log(m) + log(A) + 2 Im). Together we get O(log(m.A)) bits.
Lemma 26. For every action a that was not eliminated before the end of stage i, we have
m (1)) 2
Σ
Tj IN SNsr//ll- 32A,
j=I.jE0-
Proof. By Lemma 24, all agents u E Nerry4 have the same active set on the interval t E [tg + [3T,/8], tt +1g++1+100 [1,//22]] By lemma 23 every pull of E Nsr,/4 that is sampled before time t, [T observed by by time
4 + LTy/2] LT//4|
+24 S + [,,22] [r,/4] 76/16 14 = 4++1 - S 4+1 -
(since G. (for j S i)
The interval [t, + / (1, is of size at least r since I, + - > T
1 - 3 - 5 2 TØ. when the last inequality follows from the that for every j jE G 32A 32. Thus, the number of samples from each active action at stage j that each 3 for G²,. Moreover, these samples agent in Nsr//4 gathers is least 1 2 T2 1 324,
164,
are observed by by time f++1 - 1. In total,
B (1)) 2
Σ
I NNry/4l.
32A,
j=1.jG;
Lemma 27. When all agent play Algorithm end of stage
11 for every action a that was not eliminated before the
Ij I NN <
1088.
A
A
Proof. The proof follows the same steps as the proof of Lemma Lemma The claim involves a slightly different constants due the factor of 1/32 in Lemma 26 as
5 but employs Lemma 26 instead of
opposed to 1/ 166 in Lemma 4
38

---

Lemma 28. bounded by
When all agent play Algoritim 17
the regret of agent (under the good event) is
Rr 2 Σ Σ
D4. +
TA
+ 16A7.
(13)
Aj
AE JEG,
Proof. Similar to the proof of Lemma 8 and Lemma
18
Ry 2 Σ
Σ
3
A
Σ
Σ
A
TA
Aj
Aj
NE xEAD IJEG,
YEAA j=1.jEG,
2 Σ
Σ
A
TA
+ 16A
Aj
sEAS j=1,EEC,
where the last is since,
Σ Σ
SAS
Σ
32A
32
Σ Σ
1 32
A(A
1A-11
I 16A4.
A
A
2
iEAa j=IjEG,
iEAA
j=1
YEAA j=1
Proof of Theorem
Let us write again the Right-Hand Hand-Side of Equation 13
2 3 24.+1
TA
iE A₁
m
Similarly to the proof of Theorem as
2
we'll break the first sum in the Hight-Hand-Boe of Equation [3
T A
(14)
JEAAJ=IJES, Aj
Aj
We can adjust Lemma 10 the only change is the constant of 1088 instead 256. Using this adjusted lemma, get that for every i E As.
Σ
IA
T
Tj
A
Aj
j=1,jEG,
AS+
1088.
(15)
mA,
< 1088
mA
Similarly to the proof of Theorem for the second term, for every i, using Cauchy-Schwarz inequality
Σ
3 SASA
Σ
A
A
Aj
JESS
4 1088
1
A
A?
A
1
< 4355
A₁
39

---

Using Lemma 12 summing over all actions we get the second term in Equation 14 is bounded by 66Avt. Combining this with the other terms in Equation (3) yields the part of the bound corresponding to the good event. From Lemma 3 the complementary event of the good events adds no more than I to the regret. We get,
TA 2 6..V6 +
T
Rr S 2- 1088
+ 16A4
m
m
TA
TA:
2177
132A
+ 16A4 +
m
m
A problem-specifie flavor of individual regret bound can also be found: The proof is similar to the proof Theorem Lemma 29. Under the good event, the regret of agent bounded by
Ri 2 Σ Σ
2A
164
(16)
A
iE[A J=IjEG,
Proof. The proof follows the steps Lemma gaps and large gaps.
28 but without splitting the analysis for small
Lemma 30. Under the good event, the following holds,
Tj JAS A Aj
Σ E
Σ RE[A],A.>0
1088. + 66AVL.
mA,
Proof. The proof follows the same steps the proof of Theorem but treating all non-optimal actions the same, and stopping the analysis in Equation 15)) i.c., without bounding the expression with /T/mmA.
Proof of Theorem 4 (instance-dependen bound). The proof follows by combining the results of Lemma 29 and Lemma 300, and with the fact from Lemma that the complementary event of the good events adds no more than the regret. We get,
Ri 2 Σ
Σ
T A,
A: + 16A2 + 12Ar +
(E[A) j- J.jG.
2
Σ
1088.
2 66. W + 1642 +1
mA:
aE(A),
2176r.
Σ
+ 1324
/ 16A2 +1.
mA,
RE[A],,,0
40

---

H.2
Communication Cost - Low Number of Messages
Algorithm 4
1: Input: Communication tree T = EV with root w E V, stage i
2: Define: V, : {u V dr [u. v)
1
3: Initialize the set of clusters: C 2-4-0 /
4: for each such that dy w. u) = 2a do
5: Let Tu = (V., E.) be the sub-tree of T rooted at u
6: if Vv 2' then
7:
V. + V. UV
8:
else
9:
// then [V. 2
10: run Create-Clusters on Tu with root u and stage i, and get output C2
11: Add Cu. the set of clusters when is the root, to the set of all clusters: C +- C CCC
12: end if
13: end for
14: C CUCU [
15: return C
Definition 25. Let 'T be tree, T = E). We say that C is a clustering T if C is a partition of V and each set of nodes W E CC connected.
Definition 26. Let T be a tree, T EV and C clustering of For each cluster W E C define the cluster's 's root of W to be the root node of the sub-tree that is defined by W. The cluster's root of the cluster in which agent resides in the phase is denoted with cluster-root((u) or simply cluster-root when the context is clear. Every connected sub- sub-graph of a tree is tree, so the existence and uniqueness immediate follows.
Definition 27. Let a tree T = (V, E) and C clustering Tf T. For each cluster W C, say that E W is cluster boundary if u has no children in W. When u is a cluster boundary node for cluster in which agent v resides in the phase we denote it with cluster-boundd bluste-- boundary if the context is clear.
(v), or simply
Lemma 31. Let C be the clustering that Secate-Clustenn outputs with stage properties hold:
The following
1. Each cluster W E C is at a size of at least m.).
2. For each cluster W E C and its associated cluster root w, for any agent u E W, dw,,, u) S 2
We will prove by induction on the number of times Sreate-Clusters is called recursively. For the base case, assume that Create-Clusters Clusters called only once. For the first property, note that since Seeate-Clustene is not called again, the only cluster added is V which at this point is V itself, and the size is m.
Proof.
For the second property, note that the only cluster can either contain nodes that are at most distance from the root (added in line 2), nodes that added if there not enough nodes to create a full cluster in the tail (when [Vl < 2¹). For the latter, since |V, < 2 for any v E V., follows that (v, u) < 2'. Also dr (w, u) 2' by definition, and thus d7 (w, v) < 21+1
1
Moving to the induction step. assume that the propertics hold whenever Create- Clasterrs is called most times. Now, consider a run where Create- Clusters is called + times. It means that every call for Now will show that the outer call (the first call) to the algorithm holds these two conditions as well. For the first property, if a cluster is added in line 14, then since V,, at least of size min (m. 2 (line 2) and can only increase in line it satisfies the property. If is added in line 11, then since call Ceatee-Cuuters on a sub-te tree with at least 2 nodes in line 10, by the induction assumption any cluster that it outputs is of size at least 2
Create-Clusters
-llaterr in this run which is not the outer call, holds the two properties.
For the second property, similar to the base case, for the cluster added line 14, any node is added either in line 2 (in which case satisfies the condition) or in line 7, in which case since Vvl < 2', for
41

---

any v e V., dr(2, u) S 2", And for the latter (r v) I dr(w, 2) + dr(u, 2) S 2 Since the induction assumption hold for Cluster line 10, the all clusters that are added in line 11 satisfy the second property.
Lemma 32. Let C be the clustering that Create- Claster- outputs at phase i when run on the tree rooted at w. u + cluster root if and only if dT w) = k 2 for some I and it has at least 2' descendants.
Proof. Cluster roots at distance (u, w) k 2' for some & N U {0) by construction: The initial cluster root is w itself. At the first recursive level, cluster roots are away from w. At the second level, they are 2' from cluster root at the first level, that is, distance of 2 2'2' from And so on for subsequent levels. Hence, u * w a cluster root, then (u, = 2 for some k N. Furthermore, must have served "else" condition, u is guaranteed to have at least 2 descendants.
at line 10 of the algorithm. Specifically, under the
Conversely, if d u, w) k 2' for some & N. it will be iterated over at some recursion level in line 4. If it also has 1 descendants, then it will reach line 10 as the tree root and thus will be a cluster root.
Lemma 33. Let Cs and Ci+1 be the clustering that Create-Clustere outputs at phases i and i + respectively. U E C. then U is contained some cluster in Ci+1-
Proof. Let U E C, let u its cluster root and let some v E U.
If u is also cluster root at C.+1- We will show that v is in u's cluster also at phase i + 1.
If d(u, v) < 2' - 1, then since u's cluster at phase i contains {v' e V dr(u, v') s 2 1}. it also contains v.
Otherwise, U is of distance at least 2 from Let o' E U be the node between and that is distance exactly 2 from u. of is not cluster root (since there is a unique cluster root in U). Thus, by Lemma 32 it has no more than 2 - decedents. Therefore, v' not cluster root also in phase i We conclude that there are no cluster roots between e and u also phase i 1, mcaning that must be in u's cluster also in phase + 1.
If u is not a cluster root at C++1
u is at distance k' 2i+1 (K' E N) from w then since is not a cluster root at phase i we know that it has less than 2 descendants (otherwise, Lemma 32 was still be cluster root). In this case, none of the descendants of u are cluster roots. In particular, they are all descendants of the same cluster root at phase + 1 and thus contained in the same cluster as u itself.
Otherwise, want to claim that each by contradiction that v E U is a cluster root at phase + 1, then by Lemma 32 descendants. In this case, again
U is not cluster root in phase i. Assume
d(c, w) k' 2 (K' E N) and has at least 2 by Lemma 32 v was also cluster root at phase i. In particular e & U since u is the unique cluster root in U. A contradiction. Since U does not contain cluster roots at phase + they all must be descendants of the same cluster root at phase + 1 and thus contained in the same cluster itself.
Remark 6. Throughout this section, assume that, with a lack of other context, always refer to a specific agent v.
Remark 7. The good event this section is the same as G in Definition 14 and from now on we assume it holds.
42

---

Definition 28. The length of the cluster is the distance between the cluster-root and the farthest cluster- boundarr
Definition 29. A phase the context of Coop-SE SE- Comm- Cost is all the timesteps between the changes of the counter i. Specifically, a phase is all timesteps [3 (2' 1),3 (2' 1)). and for the last phase,
[3. (2 -2- (for i = [[og(T] (T6]
1).
Definition 30. The active set of actions of u at phase i is the set of actions that cluster- sent in that phase, and it is denoted by A.. We denote its size by |A,l= = A. An action is denoted as "active" in phase i it belongs to Ai. The last phase of a is sometimes denoted with in- We denote Ag == A and A++1 O where i' is the global last phase.
Remark 8. Notice that while some actions that are not active for v in phase i may be played in phase i by u. This since the active set of actions didn't propagate yet to v. Eventually, the set of active actions will arrive v, and in the last third of the phase will play only active actions.
Lemma 34. The set of active actions (for vertex v) is non-increasing. L.e., for any phase i, A, 2 A:+1-
Proof. Let un and Ui+1 be v's cluster root at phases and + 1, respectively.
u; = uf+1 then by definition A,+1 = A, B where B is the set of actions eliminated that phase (either due to the elimination step of due to elimination messages). In particular Ar+1 S A4-
If u4+1 # uy then by Lemma 33 since v and u, are on the same cluster at phase i, they are also on the same cluster in phase + 1. That is Mi++1 is also the cluster root of vy in phase i + 1. In particular, at the beginning of the phase v, pass message to 4,+1 with the aggregated eliminations which contain at least all of the inactive actions at phase i. In particular, if an action was inactive at phase i it will be also inactive at phase + 1. That is, A++1 S A₁
Lemma 35.
When all agents play Coop-SE- Comm- Cost (Algorithm (3) then for every phase Z loga( except the last phase, and for every active action in that phase a, each agent in the cluster of plays action at least 2' /A, times in phase i.
Proof. In the middle of each phase, there are 2 rounds in which the agent plays the active actions A, The number of times the agent plays active action is at least [2 /Ar]. We get
2
2i+1
2
1 2
A
A
A,"
where the last inequality is from 2 (og)(A.).
Lemma 36. When all agents play Coop- Comm-Com (Algorithm 13 then after the gathering
part of phase s.t. i i (A) + 1, the root of the cluster has at least 2 2-1 min mm ,m]/A,-1 At1 samples for every active action that phase.
Proof. Let a be an active action in phase i, i..., a E Ai. From lemma 34 a was active at A, From 1 each agent in the same cluster of in the previous stage i plays at A, times action a. The size of the cluster at phase - is at least min m). from Lemma 31 By 2. in Lemma 3T the distance between each agent in the cluster and the cluster root is
Lemma 35| at phase
least 2
at most 2 hence all agents contribute all their samples. Together it completes the proof.
Lemma 37. Assume that is phase in which action a is active, and i 2 logg (A) Then
A
Aa s 4 $ 2log(3mmT A) 2'. min (2', (2', m]
Proof. Since action wasn't eliminated at phase for the agent v, it means the cluster-root of at this phase didn't 't eliminate it in the beginning of phase i.
From Lemma 36
we know that the counters of cluster-root, when the cluster-root is
doing the eliminations at phase i, are at least n(aa) 2 26-1 min (2--1, m--11.m//AA A;-1, n(a*) 2
26-1. min mm/ /AA- Notice that 2--1 min(2'-1 .m
,m)/A A 2 1
2 min m
43

---

The root didn't tt eliminate the action a, hence
2t
21
Ha +
V n((a)
2 Ma -1 n((a)
\n(aa
We get
A-1 21 2 min [2,m} m]
Dg S 14112
Lemma 38. Assume that i is the last phase in which action is active, and i 2 lA) Then the number of limes plays action in phases j 2 logg (A) most
2'
48
A;
Proof. Let us analyze each sub-phase part of a phase j in which action is active. In the first third of the phase, where agents gather the information in the cluster and send the root, the agent plays action a at most [2)+1 /Aj-1l. From lemma 34 we have Aj S Aj-1, than in this sub-phase the agent plays action a at most 124+/A,]] times. In the second third of the phase the agent get the new active of actions, Aj. So part of this third is with A, and part with A5-1- Then we can bound the number of plays in this part with [2 /Ay]-
]. In the last third the agent plays actions from Aj. then this third contributes no more than [2 /A,1 samples. We get that in each phase j where action is active, agent plays action a at most 3
If / is not the global last phase, it is possible that plays action at phase + 1. In this case, v plays only this action no more than 2/2 < 1124+2/A,] Notice that the denominator has A, and not A4+1, since v didn't eliminate any action in this round yet.
Since j 2 lAg we get /A, 2 A/A, 2 1.
Then we get [2 S 2. /A₁ S
2/+1 /As. Hence, the agents play this action phases j 2 log, (A) no more than
21+1
2
4 28+1 +
2
2
+2
W 3
S 48
A
A;
A
A A
3=1
Lemma 39. Let i be the last phase in which action a is active, and i > log2(A) + 1. The regret that action a contributes for phases j 2 loga (A) bounded by
2 A
64 2log A)
(17)
A,
min m
Proof. Let i be the last phase in which action is active. From Lemma 38 the regret is bounded by
A, 48 2
A;
From Lemma 37
A
A < 4,
21 2
min (2 m]
get
2
A D. 64v2i
2 A
Aa 16
4, 2
A,
min (nin(2ii,n) m]
A
min m)
Since Ao < 1, we get the full result.
44

---

Lemma 40. Let 2 log + be phase. The regret from phases j 2 log2(A) of all actions that è was their last phase is bounded by
A4+1 A:
2 A;-1
64 2 log(3mm A)
(18)
A;
min (2', m]
Proof. From Lemma 39 the regret from phases (A) of action that i was its last active phase bounded by
A
64 2t
A,
min m)
There are A; - A4+1 such actions. Hence, we get the results.
Definition 31. Let us denote the regret bound of an action from phases j 2 log2(A). Equation with by. I.e.,
2 A
bj = :4 2og (3mg
Aj
V
min mb
Definition 32. Denote the expression in Equation active phase is j) with Bj. L.e.,
18
(the regret bound of all actions that their last
Bj = (A, Aj-1)b, 64 log(3mm Aj Ast1
2 A
V
(19)
Aj
min (2), m/
The following lemma captures the core insight our amortized analysis. It bounds the regret in high-ratio phase with low-ratio phase. Formally,
Lemma 41. Ler log, be phase such that A5-1 2A3. Let be the first phase such that
(i) i log2(A)
(ii) The phase i is the first such that there exists sequence to such that A, > 2A,+1 > > 1--1-1 Aj-1 > 20-1Ag.
Then,
B₁ S 4B;.
Proof. First we prove that & j. The existence of is immediate, from its definition. is either i is the closest phase to j that has A;-1/A, A/A, 2 (breaking the sequence, while i S j) or that i == [log (A)]. Assume by contradiction that i = j. We will see that ju holds these two conditions. First, j 1 + (A), then j 2 (A). Second, Ay-1 2A, by the definition of contradiction to the condition that says that is the first phase to start this sequence. Therefore, i =
Since i + 1 S get that A//A441 2. Then A41//A 1/2, and A51/A; 1/2. We
will use this inequality later in the proof.
The ratio By/Ba is
A 1141
A
min m
2 PAg
Aiti
A;
25- A5-1 min m2in m)
As As-A A.
2'A11
A
A min min (2), 12).m m)
min
A,
Ast1
<
A;
2/-
A--1
(a)
A
A
A
A 1-1
2
2
(b)
A
A
22
2
(c)
A
45

---

Where the first inequality (a) is since min(2',m min min (2)m)
S 1 as i j and min ; m] is increasing with a.
The next inequality (b) used the facts that 1
A++1 A++1 1 1 A:
A; I 1, and 2 2 2 I A,. We A; - holds since A++1
showed earlier that A.+1 1. The inequality 1 A,+1
A; 2 2'
Aj 2 0 (even where
j is the global last phase, there defined Aj+1 == 0), and 2 A5-1 I A, holds because of the definition of i and from the fact that i + j. The last inequality (c) uses the fact that A, S A; by lemma
L
The following lemma bounds the regret of all high ratio phases (A,-1/A; > 2), with other low ratio phases. Each phase that has low ratio between the previous and the current number of actions
(A,11/A; I 2) is paying has high ratio, so one phase with low ratio can't pay for the rest by multiplying just with constant. Since there are at most (og)(A) high ratio phases, we can bound the regret of all high ratio phases with low ratio phases. Formally we get,
phase with high ratio. But there might be a sequence of phases that
Lemma 42. Let us denote the set of phases with low ratio between the number of actions. Specifically, denote I == {i E N 2 log2(A). 1/A// S 2) U [[og2 (A)]}. Then,
Σ
B₁ S Σ
(5 log2 Bi),
(A)
iET
where
Bj = (Aj Aj-1)bū-
Proof. From Lemma 41 for each j 2 logg (A) + such that A,-1/A, > 2, there exists E I such that B; < 4B, The number of remaining actions decreases by more than half each round. We have A > A; > 2/- Aj,, then j -- < loga(A) Let 7 I,..., + j be sequence as defined in Lemma 41 Lee., i 2 (A). And the phase i the first such that there exists a sequence to j that 2
holds A, > 2A;41
1 A3-1 > 2 2 Ag. Then
Σ By S B
Σ k=it1
4B; S B, + log, (A)4B, S 5 log (A)B..
Hence, each such sum of Σ B& a sequence A; > 2A,+1 > ... > 2A, is bounded by the 5 lo) where is the beginning of the sequence. We can break the sum Σzz Bj into sums of such sequences, and the results follows.
Lemma 43. All the actions for which their last active phase is smaller equal to log)(A) contribute to the regret no more than 24 - A.
Proof. In the phase j there are 3 2/+1 timesteps. An action that its last active phase can be played until the stage + 1, included. So until the phase i + the number of timesteps is at most
i+1
3
2
Σ
2 = 6. (2 1).
Therefore, for actions that were eliminated at phases smaller than log)(A) we get that the regret that is contributed from all these actions is bounded by
6 (A)+2 1) S 6 (A)42 24- A.
(082(A) (A)]. Specifi- cally, denote I == {i E N 2 logz (A) + 1, A:/A,-1 I 2}. Let Ag2 be the set of action such their last active phase is in I+ Then we gel
Lemma 44. Let denote with I+ the set of low-ratio phases, without the phase Nogz
1024e
Σ eEAga
bi
+ 157 log(3m
Au
aEd
46

---

Proof. We first focus on actions for which 2 < m. We get that
2 A ( m)
A
64v 2t
64v
21-
A..
Aia
Let us order all the actions in weak linear order of which they were eliminated. For the simplicity of the notation, assume it is their order in (and A [A]). Let define two vectors of length each.
Aig-1 Aia
aE[A]
and
1
V Ain
aE[A]
With these vector notations we get
A
Σ
64v20
Σ
64v2r
Aia
A
aEAga,2' cm
aE[A],20<m cm
S 64 20
For we get
A
[u 2
Σ A S A².
Aia
For we get
||
Σ
1 1 + log 1 3log A.
A,
where the first inequality is since
PEAA A >
1
< 14
dr 1+ +loog. A.
The first inequality holds since if phase was the last active phase for x actions, then z/A; < 1/(A.) 1/(A, 1) + ... + 1/(A, (x 1)). The last inequality since assume A >
From Sauchy-Schwarrd we get
(u, w) S ||u||2 || S VA2 - A Avglog A.
For all actions which their last active phase is smaller than m we have that their contribution to the regret is no more than
64 A/3 3og A < 157.Alog33TAA)
We now focus on actions for which 2 2 m.
1 A = 64V2)
2ha
A
br, = =64/2loo(3mm A) A, V
min (2's m3
Ai
Assume 2' > m. Then, from Lemma
37
2s A
A S 4
m
Square everything and we will get
Ai-
A
32t
2 m
47

---

A:-1
$ 321
A? m
Substituting 2 with the previous term and get,
1
2ia Aia
321. Ai, -1
Aia
64v2r 2t
64v2c 20-
m
Ai,
A m
111
A
64.v64 64
Aia
An 17L
1
64. 64
Da 171
1024 log(lm3 (3mTA)
Au m
where the last inequality is since a E Ag2. Overall we get
2 A
1024
Σ aEAga
64v22-
Aa 157AA
Aig
min
2'a
m
aEAga
1024 log A)
+ 157 ())
a A
Proof of Theorem 5 We can bound the overall regret in the following way. First, the regret of the
first [A)] phases is bounded by 24A4, from Lemma 43 For actions that were eliminated at
phases 2 log,(A), from Lemma 40 the regret from phases j 2 log2(A) all these actions is
bounded by
Ai Ai41
2 Ai-
Σ
64 (64/2log(31) (0mg333TA) A)
A
min m}
(4)
Notice that this is is exactly B; from Equation the sum,
19 From Lemma
42
we get bound for this part of
A411 A
2 A
Σ
64 64/2log((mTTA))
5 5lgg(A) B..
As
min (2 m
(A)
iez
Converting the analysis into actions-baut -based analysis and we get
A min 22,m m]
[l)g(A)]1 A (A))
Σ 5 logo = (A))(()) SEZ
Σ
64V2.
+ 64V2. 2:
A,
Apog((A)]
min min ([10)((A)] .A)l.
aEAgg
Where Aça is the set of action in that their last active phase is in fi E N > log,(A) + A:/Ai1 S 2).
Focusing on the part that belongs the phase [log((A) we get
2 (A)] A (10g
2A A min(A, m)
64 2r
64v2.
A,
min [oog (A) m}
TV
64v2 V2A
256AVT
256A 2564log(3mT (og(3mTT))
48

---

For the rest of the actions, from Lemma 44 we know that
2 . Ala-1
1024 log (3mT A)
Σ
+ 157 Algg(3TTA)
As, min m
A
REAg
aEA
Multiplying everything with (A) we get
1024 log((mTA)) (157 + 156))1log(3mTTA
A. m
aEA
5120 loga (A) log(3mTA)
+ 2065.
log2(4) log2 log(3mTT
A. m
REAA
The complementary event to the good event adds no more than the regret. The overall regret bounded by
5120 (ogg (og((IIAA)
Br
S
+ 2065 log, (A) log(3mI + 24A + 1.
Ao
.EAA
Lemma 45. When all agents play Caop-SE- Comm- Cast (Algorithm) 13 with spanning tree T the number of messages each agent u sends is no more than
[log2 (T' (T/6)T)6)))) /6)] degr (v),
where (v) is the degree of v in the spanning tree graph (the number of neighbors).
Proof. In each phase each agent sends messages in no more than 2 timesteps: One message of of the cluster. This
the collected information from the boundary vertices (cluster-boundal) message is sent to the parent agent. Note that the agent waits until all messages from her descendants arrive before she sends the message to the parent agent. This adds message for each phase. The other timesteps the agent sends messages is when she tells her descendants the set of active actions. This adds dw) messages for each phase. There are [Tog)(7/)) phases, and the result follows.
49

---

I Auxiliary Lemmas
Lemma 46 (Lemma F.4 TO]. Les {X,)==1 be a sequence of Bernoulli random variables and filtration Fi F2 Fr.Frr with P(X; = Fi) P. P: is Fi-measurable and X is Fit1-
measurable. Then, for all t E [T] simultaneously with probability 1 8,
Σ Xx R=1
Ps log 1
Lemma 47 (Consequence Freedman's 's Inequality, e.g. Lemma E.2 in 9). Let (Xihe21 be
sequence of random variables, supported in [0, Rl. and adapted to filtration Fi S F2 S Fr. For any T, with probability 1 - 6,
T X1 S 2 FF + 4R log
1 0
50

---

Detailed Algorithms
Algorithm 5 Elimination Step (Elim-Step)
1: Input: active actions A, number of samples na))) for each active action empirical mean for
every active action (a)).
2: E
3: for E do
4:
2
X(a) = V n(a)
UCB(a) = p(a)) + X(a), LCB(a) = fi(a) - X(a) (20)
where 6:= l::mon3
5: end for
6: for A do
if exists a' with UCB((a) < LCB(d') then 8: E [a
7:
9: end if
10: end for
11: Return E
Algorithm Cooperative Successive Elimination (Coop-SE) detailed
1: Input: number of rounds T, neighbor agents N, number of actions A, ID of current agent v.
2: Initialization: / <- 1; Set of active actions A = A: R4 (a)
(a 0 for every action o;
Min = 0: Mupdates = 0; Maant = 0; Maaen 0:
3: for = 1,.... T do
4: for event E Mupdates do
5: event & Masen then
6:
Masen = Ma U event 7: if event is elim-event then
8:
A = AA event,
9:
else if eventa A then
10:
(a) (a) + 1, (a) R,(a) + event,
end end if
12:
end for
14:
E Elim-Step(A, nr, Re/n.)) A==AA
15:
Choose action a, in round robin from A, and get reward rr(aa)
16:
// Send and receive messages
17:
Mae = { (rwd, f, v, a,, re())) U f(elim, v, a) E E}. Mf = (Mno U Maa)
\ Moent
18:
Send message MP to all neighbors, receive messages My from each neighbor of E N
19:
Meent Mgent U My, Mapdates
Mas UNEN Mr Mia Mia UPEN M,
end for
51

---

Algorithm 7 Successive Elimination with Suspended Act for agent (Sus-Act)
1: Input: number of rounds T, number actions A, diameter the graph D, number of agents m, neighbor agents N, factor for the confidence bound L.
2: Initialization: t 1; set of active actions &- A; Maant
Set incoming messages
Min 0; Set of seen messages Maeen 0.
3: while < do
4: Calculate suspended counts and empirical means for each active action from the Maeen messages
t-D ΣΣ
mx(a) = ΣE' Ma =a}; Ac(a) 1
(a)][aa" = a}
n((a) VI 7m1
5:
A = A\ Elim-Step(A, (n.(a)la E A}, (Aa(a)la A})
6:
Choose one action a, A in round robin and receive Ta.
7:
Let Me (RR D, f. 0z, (a.))
8:
Let M.¹ = (M U (MM)) Maent
9:
Send message M2 to all neighbors
10:
Mast Maant U M,
11:
Receive messages M, from each neighbor v'
12:
Set incoming messages Min Min U {M,' o' is neighbor of c}
13:
Set seen messages Maeen = Maeen U Min U Mae
14:
t == +++1 1
15:
end while
Algorithm 8 Update Step Tree Update the counters with the received information and prepare them for sending in tree graph (Update-Tree-Stee
1: Input: Neighbor agents N; Set of active actions A; M Mupdates.
2: for
3: n²aa) 0, R(aa)
4: for u E N do
5: N 0, R 0
6: end for
7:
end for
8:
for event E Mupdates do
9:
if eventa E A & event is rwdMany then
10:
I/ event- = (rwdMany, id, a, r, n).
11:
n(aa) n((a) + evend, R(a) R(a) event,
12:
for u E do
if eventtu * then No N + event,; R = R + event, end if 16: end for
14:
end if
18: end for
// Return the self counters and the values send.
20:
Return n(a), R((a) for each A; Return N R for each A and for each N.
52

---

Algorithm Cooperative
Successive
Elimination
with Restricted
Communication
(Coop-SE- Restricted)
1: Input: number of rounds T, neighbor agents N, number of actions A, id of current agent v, spanning tree, T, of the communication tree ç (identical to all agents).
2: Initialization: < 1; Set of active actions A A; Re (a) 0, ne for every action a;
Min = 0: updates = 0; Meentt = 0; 3: Set N be the agent's neighbors in
4: for 1,..... T do
5: Ereceived
Geventa/Bevent E Mupsstes event elim-event)
6: A A Eracaived
7: n4, Rr, N,
N,R. R. Treate-Tree-Step/AN M Mupdates)
8:
Mupdatez = 0
9:
F= -Stimm nes Rg/me)
10:
A=AV
11:
Choose action a, uniformly from A, and get reward re(a;)
12:
(a(a;) (a())) + 1, (a,) (a,),) (r()))
13:
for u E N' do
14:
No = N +1, +1, R + Ra()))
15:
end for
for u E N' do
17:
Maisn(u) = [(elim, v aa E F} U ((elim, eventa) Bevent E Fracasved, evenlid + w)
18:
Myua (u) = (Iwddany, a, R. N A}
M.' (u) Moria(Ul U Muva(u)
20:
Send (M) and receive (v)
Mapdates Mapdates (e)
22:
end for
end for
Algorithm 10 Send one action CONGEST -Send-One-Action
Input: Neighbor agent u; Received eliminations-events Fracoived: New eliminations E; Action a'; Counters to send N Rewards to send R
2: if Ea' E then
3: send (elim, v.a") to return.
4: else if Jevent E Eracasved, eventia + u, event, = a' then
5: send (elim, a') to return.
6: else
7: send (rwdMany, a', Rg No) to return.
8: end
53

---

Algorithm 11 Cooperative Successive Elimination CONGEST SROp-SEE-ONGESST detailed
1: Input: number of rounds T, neighbor agents N, number of actions A, id of current agent v, spanning tree, T, of the connected communication graph G, with a root agent w (same node for all agents).
2: Initialization: t +- 1; Set of active actions A A; Ro(a) = 0, no (a) = 0 for every action a;
Mupdates 0;
3: Calculate the distance between the root w and the current agent v, := d w), where dy is the distance in the tree.
4: Set N to be the agent's neighbors in T.
5: Set N' C N to be the set of v's children on the tree T rooted w.
6: Set u E N to be e's parant in the tree T rooted at w. Le.. {ū} = N N'. Notice that ū exists
only is not the root.
7: for = 1, ..... 7 do
8:
Preceived feventa Bevent E Mupdatas event el alim-event) R, N, R Update- Sipdate-Tree-eee Step N, A, Mapdates) n4 n + n. R. R R
9:
11:
E Elim-Step(AA, n,, n,, Pr = Rr/n,)
12:
= A
13:
Choose action in round-robin from A, and get reward (a()))
me(a:) = n4 (a:))) + (ax) (a)))) (((e))
15:
for u N do
16:
(a:) = NÝ (a:) + R (a.) = R2 (a:) re(at)
17:
end for
18:
Choose the action d', the action to send to v's children: ='= - d (mod A)
19:
Choose the action ä, the action to send to e's parent: t + dl (mod A)
20:
for u E N' do
21:
// Send the messages outward from the root.
22:
Send-One- Aine-Action(u, Fracaived. E, a. ,N, R end for Send-One-Actionfs Frecesved. E, 0,N R.) // Send the messages toward the root. Mupdates 0
23:
24:
26: for u E N do
Receive (v)
28: Mapdates M Madatee U (F)
end for
30: end for
Algorithm 12 Play round robin and increment the timestep counter (Play-Action-Rel Hound-Robin)
1: if' = + 1 then
2: Terminate the program
3: end if
4: Play action at in round robin from the set of active actions, get reward (a.))
5: = t++
6: return de, de,re(as ra()
54

---

Algorithm 13 Cooperative Successive Elimination
with
Communication
Cost
1: Input: spanning tree T (same tree for all vertices); Children C, and parent p in the tree; Actions A.
2: Initialize: t = 1; Rd (a) = 0, (a) = for each a E A; Set of active actions A A;
forward=false.
3: for phase = -.....; (T/6) do
4: Based T, compute for this phase if this agent v is cluster-root cluster-boundary
or none of these
5:
6: Sub-Phase 1: Gather and Aggregate Information
7: for k 1, 1......2 .2+1 do
8:
Te = Mewcciioo--unnd---eeeee
// Play one action from the current active actions
9:
Update rewards and counters Rd (a,) + R" (a,) + n" (a:) + (ax) +1
if k
and is cluster-boundary for i then Send to parent agent:
11:
1. Set of active actions: (is-active(c)
(a E A)
A)
13:
2. Rewards and counts for each action: 1/ (II" (a), n((()))()))))))))))) (a) E A}
14:
else if received messages from all children then
15:
Aggregate children's 's rewards with local rewards: (a) Rº (a) + Evec (a) Aggregate eliminations, set is is-active(a)=faat if at least one message contains an elimination about this action forward=true
16:
17:
else if forward=true then
19:
forward=false Forward aggregated data,
20:
| a E A}, to the parent agent
21:
Set !t' (? 0, nt = 0 for each A
22:
end
23:
end for
24:
25:
Sub-Phase 2: Synchronize Active Actions
26:
for k = 1.....,22 2 do
27:
at.
Hlay-Acttoo-Round-RRot
28:
Update rewards and counters Rº (ar) + R²" (ar) + rr, n" + (ar) +1
if k 1 and is cluster-root for then
30:
A
A Eliminate actions based aggregated eliminations
A {a
is-active()==falee)
31:
A
A
Elim-Step(A,n) n,, .
RR /nn)
Eliminate actions based on aggregated rewards Send A, the new active action set, to descendants else if received active-actions message then Update local active actions set if is not mannterr-bundary then
32:
33:
34:
36:
Forward message to descendants in the next timestep end
37:
38:
end if
39:
end for
40:
41:
Sub-Phase 3: Execute with Updated Actions
42:
for k = 1,..., 2 do
43:
or. rt = Saay-AAtion-RRund-Roooe
44:
Update rewards and counters R R" (a.) RR (ar) + rt. (a:) na +
45:
end for
46:
end for
55


Reviews:
[{"review_id": "jB735msd95", "reviewer": "Reviewer_xuc7", "summary": "This paper addresses the cooperative stochastic multi-armed bandit problem, where a number of agents ($m$), connected via a fixed graph, face the same bandit instance and can exchange information with their neighbours. The goal here is to guarantee small regret for every individual agent in the network. The authors noted that previous works achieve regret bounds of the form $\\mathcal{R}/m + D$, where $\\mathcal{R}$ is the optimal single-player regret and $D$ denotes the diameter (or some other function) of the graph that can be as large as $m$ in some cases. This additive dependence on $m$ means that the contribution of $\\mathcal{R}$ to the regret bound cannot be made arbitrarily small in general as $m$ increases. The authors address this issue by proposing an algorithm that enjoys a similar regret bound but replaces $D$ with $A \\cdot \\min(D, A + \\sqrt{\\log T})$, where $A$ is the number of actions and $T$ the time horizon. A worst-case lower bound of $\\sqrt{AT / m} + \\sqrt{A}$ is also provided, matching the first term of the upper bound in a worst-case sense and showing that some additive dependence on $A$ can be unavoidable for some graphs. The adopted algorithm, Coop-SE, is an adaptation of the successive elimination algorithm to the cooperative setting that is completely decentralized and uses only local graph information. Similar regret guarantees are also provided for two extensions of the algorithm that respect constraints on the message size or the number of communication rounds.", "questions": "Concerning the additive term, do you believe that the shortcoming is in the upper bound? If so, could this be a limitation of the successive elimination algorithm? Could it be a limitation of only using local graph information?", "limitations": "Yes, a brief discussion on the limitations of this work are discussed in the future work section.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper seems to provide a solid contribution to the literature on this problem. Unlike the cited regret bounds previous works, the dependence of the new regret bound on the reciprocals of the sub-optimality gaps can get arbitrarily small as the number of agents increase, regardless of the structure of the graph, so long as it is connected. The adopted algorithm is simple and intuitive, and the explanations are fairly clear.\n\nOn the other hand, the presented results still do not provide a clear idea as to what extent the structure of the graph can be exploited, particularly concerning the second (additive term) in the regret. This term seems to be at least $A$ in the upper bound for any graph (including, e.g., the complete graph), while the opposing $\\sqrt{A}$ term in the lower bound only concerns a particular structure (the line graph) and does not seem to apply in a graph-specific sense. Perhaps this should be emphasized more. Aside from this, I see no major weaknesses in the paper. Some minor points concerning the introduction; it does not seem that the additive terms in Theorems 4 and 5 are exactly as reported in Section 1.2 and Table 1; moreover, in lines 91-93, it seems that the argument should be that $h(\\mathcal{G})$ can increase (potentially up to $m$) if $\\lambda_2$ is close to $1$, not $0$.", "was_revised": true, "final_justification": "My evaluation remains on the positive side. I think the regret bound presented in the paper brings an interesting improvement over the cited prior results, particularly in the worst-case regime where the sub-optimality gaps are small. The presentation of the algorithm and the results is fairly nice and clear. However, I think the authors should do a more thorough job in highlighting the limitations of their results; e.g., regimes where their bound fails to bring an improvement, the gap between the upper and lower bounds, and the fact that the lower bound has a worst-case flavour in terms of the graph structure. In addition, of course, to highlighting more clearly the similarities with algorithms from prior works as mentioned by other reviewers.", "rebuttal": "Thank you for your comments. We hope to have addressed all your comments in the rebuttal below, and will be happy to continue discussing this with you during the author-reviewer discussion period. \n\n\n> “the presented results still do not provide a clear idea as to what extent the structure of the graph can be exploited”\n\nWe will emphasize in the final version that leveraging the graph structure can potentially reduce the additive term in the regret. For instance, in the case of a complete graph, the regret can be as low as $\\mathcal{R}/m$, and if $m > \\mathcal{R}$ the regret is constant.\nAn interesting open problem is to characterize the dependencies of the regret on the graph’s structure. We will add it to the Future Work section.\n\nOur goal is to derive graph-independent regret bounds and to give regret bounds that hold for any graph. As you remark, the only potential gains are in the dependency of the additive term, which is already rather insignificant compared to the regular single-agent regret.\n\n\n>”Some minor points concerning the introduction; it does not seem that the additive terms in Theorems 4 and 5 are exactly as reported in Section 1.2 and Table 1”\n\nThank you for noticing the mismatch between Theorems 4 and 5 and to the statements elsewhere. We will fix this. Theorem 4 should be: $O(\\mathcal{R}/m + A\\sqrt{\\log(mAT)} + A^2)$, and Theorem 5 should be: $O(\\mathcal{R}\\log(A)/m + A\\log(A)\\log(mAT)) $.\n\n>”moreover, in lines 91-93, it seems that the argument should be that $h(\\mathcal{G})$ can increase (potentially up to $m$) if $\\lambda_2$ is close to $1$, not $0$.\n\nIt indeed should be “The eigenvalue … can be very close to \\textbf{one} for some graphs” (not to zero). Thanks again.\n\n# Questions\n\n>”Concerning the additive term, do you believe that the shortcoming is in the upper bound? If so, could this be a limitation of the successive elimination algorithm? Could it be a limitation of only using local graph information?”\n\nWe believe that this is an artifact of the analysis rather than of the algorithm. The additive $A$ term arises in part because we treat each stage as having a length of at least $1$, which leads to a regret of at least $A$. However, potentially, multiple stages may have length $0$. Unfortunately, we were unable to refine our analysis to account for this.\nWhen the agents are completely connected (there is no issue of local graph information), i.e., the graph is a complete graph, the additive term is eliminated with our algorithm."}, {"review_id": "IYnmiu3pv2", "reviewer": "Reviewer_Kf67", "summary": "This paper examines individual regret in multi-agent stochastic MABs residing on a communication graph. This paper explicitly investigates how to remove the dependency on the graph diameter from the regret upper bound, which is achieved through a more sophisticated analysis of the Coop-SE algorithm. Then, the paper extends the Coop-SE algorithm to two types of low-communication variants, which have reasonably worse regret upper bounds.", "questions": "- Line 37: why omit the $\\log T$ regret term here? It dominates the $\\sqrt{\\log T}$ term.\n- Line 65: the $\\mathcal R$ still dependent on the gaps.\n- Line 67: It would be better to present the upper bound in minimax form here as well.\n- Line 74—79: the open problem can be addressed by other prior works mentioned in the related work section, why emphasizes it here? Is there a special insight of the current work on the problem?\n- The communication round of TCOM should be additive $D$ instead of multiplicative $D$.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "- S1: The analysis for Coop-SE (especially Lemma 1) is more sophisticated than prior ones, enabling the removal of dependence on $D$.  The reviewer thinks that it is an interesting new approach.\n- S2: The writing of this paper is clear and motivating. S1.1 did a good job of motivating the study, and S5 provides an easy-to-follow proof sketch.\n---\n- W1: Although concretely new progress on the direction of multi-agent MAB, the reviewer thinks that the result in this paper is not very significant (even the authors did a good job in the discussion in S1.1). The main improvement of this paper is from $D$ to $\\min\\{A+\\sqrt{\\log T}, D\\}$, where the latter can remove the dependence of $D$ when the graph has a large diameter. However, \n    - (1) the $O(\\sqrt{\\log T})$ term is still relatively large since the time horizon $T$ in the bandit setting is typically the largest constant. \n    - (2) The improvement only happens when the graph has a large diameter (larger than $\\sqrt{\\log T}$!).\n- W2: The current results are not tight. The upper bound $O(A^2)$ has a large gap in comparison with the $\\Omega(\\sqrt A)$ lower bound.\n- W3: Although the analysis is new, the Coop-SE algorithm has been proposed multiple times in various prior works (as the authors are also aware). It would be better to posit the contribution of this work on the analysis side and attribute the merit of the Coop-SE algorithm design to these prior works (e.g., remove “ours” after Coop-SE in Table 1).", "was_revised": true, "final_justification": "While the reviewer decides to maintain the borderline accept evaluation of this paper, the reviewer feels that the contribution of this paper does not reach the bar of NeurIPS, and is ok with a rejection decision.\n\nThis paper studies a known multi-agent bandits problem, analyses a known algorithm Coop-SE, and only provides a new regret upper bound, which is tighter than the known bounds only in some special cases, i.e., $D>\\sqrt{\\log T}$.", "rebuttal": "Thank you for your comments. We hope to have addressed all your comments in the rebuttal below, and would be happy to continue discussing this with you during the author-reviewer discussion period. \nIf you find our answers appropriate and satisfactory, we would be grateful if you would consider raising your score.\n\n\n>W1: “Although concretely new progress on the direction of multi-agent MAB, the reviewer thinks that the result in this paper is not very significant (even the authors did a good job in the discussion in S1.1). The main improvement of this paper is from $D$  to $\\min \\{A+\\sqrt{\\log(T)},D\\}$, where the latter can remove the dependence of $D$ when the graph has a large diameter. However, (1) the $O(\\sqrt{log(T)})$ term is still relatively large since the time horizon $T$ in the bandit setting is typically the largest constant.\n(2) The improvement only happens when the graph has a large diameter (larger than $\\sqrt{\\log(T)}$!).”\n\n\nWe emphasize that the main focus of our paper is theoretical. We would like to understand the inherent regret bound and its dependency on the various parameters of the problem.\n\nPrevious works had an additive term of $D$, the diameter of the graph.\nWe highlight that one needs to think of the diameter $D$ as a function of $m$, the number of nodes in the graph, which is also the number of agents.\nAn interesting communication network is a grid graph where $D=\\sqrt{m}$. Since the ideal regret would be at least $\\mathcal{R} / m$, if we aim for low regret, the number of agents $m$ should be a function of $T$.\nThis implies that $D$ is also a function of $T$ (indirectly, through $m$).\nHence, the dependency on $D$ hides a dependency on $T$, which is potentially polynomial for small gaps.\n\nRegarding the actual parameters, even in the extreme case that $T=10^{50}$, the number of atoms on Earth, our bound is very reasonable, since $\\sqrt{\\log(T)} < 11$. Having a diameter greater than $11$ is definitely reasonable in many cases. We stress again that our focus is theoretical, and this numerical example is only to highlight why in many cases the main term would be $D$.\n\nAs discussed in Section 1.1, one can see that small sub-optimality gaps ($\\Delta \\approx 1/\\sqrt{T}$) may contribute a lot to the regret. If the regret bound depends on the diameter, one remains with a polynomial dependency on $T$ (for example, $T^{1/6}$ for a grid graph), and increasing the number of agents will not help. But with the bounds from Coop-SE, for a sufficiently large number of agents, one remains with only $A^2+A\\sqrt{\\log(T)}$ individual regret.\n\n\n> W2: “The current results are not tight. The upper bound $O(A^2)$ has a large gap in comparison with the $\\Omega(\\sqrt A)$ lower bound.”\n\n\nRegarding the gap in the additive term between the lower bound and the upper bound, the reviewer may find it interesting that when the played action is selected randomly from the set of active actions, we get $\\mathcal{R}/m + A \\log(mAT)$ (instead of the $\\mathcal{R}/m + A^2 + A\\sqrt{\\log(mAT)}$  with round-robin).\n\nIt is still an open question whether the lower bound of $\\sqrt{A}$ is indeed the tightest, and we mention it in the future work section (lines 201-202 and in Appendix A, lines 818-819).\n\n\n> W3: “Although the analysis is new, the Coop-SE algorithm has been proposed multiple times in various prior works (as the authors are also aware). It would be better to posit the contribution of this work on the analysis side and attribute the merit of the Coop-SE algorithm design to these prior works (e.g., remove “ours” after Coop-SE in Table 1).”\n\n\nWe will emphasize in the final version that SE with message passing in the cooperative setting is not a new algorithm.\n\nThe algorithm we introduced, Coop-SE, is new since it is not just SE with message passing, but in our implementation each agent eliminates what **other** agents eliminated according to **their** observations (with elimination messages), as well as what the agent observed and calculated. This is a critical modification, which makes it possible to align the policies of the different agents. \n\nWithout this modification, an agent might not eliminate a sub-optimal action, even if other agents eliminated it. \nIn such a case, such an agent will continue sampling this sub-optimal action alone and might incur high individual regret in this scenario.\n\nIn Coop-SE, we eliminate this action due to the elimination messages from other agents.\nThis algorithmic change is crucial in our analysis for the individual regret.\n\n\n# Questions\n\n>”Line 37: why omit the $\\log(T)$ regret term here? It dominates the $\\sqrt{\\log(T)}$ term.”\n\nWe omitted the $\\log(T)$ term since for a large number of agents this term vanishes.\n\n>”Line 65: the $\\mathcal{R}$ still dependent on the gaps.”\n\nThank you, we will change this.\n\n>”Line 67: It would be better to present the upper bound in minimax form here as well.”\n\nYes, we agree, and we will present both bounds in the minimax form.\n\n>”Line 74—79: the open problem can be addressed by other prior works mentioned in the related work section, why emphasizes it here? Is there a special insight of the current work on the problem?”\n\nWe will definitely add a discussion regarding this point.\nWe acknowledge that this question has been addressed by prior works. While our contribution lies in analyzing individual regret independent of the graph’s diameter, we will explicitly state in the final version that prior works have also contributed to this specific question.\n\n>”The communication round of TCOM should be additive $D$ instead of multiplicative $D$.”\n\nThanks, we will change this."}, {"review_id": "dp6JiGj2DP", "reviewer": "Reviewer_r6fA", "summary": "This paper studies individual regret in cooperative stochastic multi-armed bandit (MAB) problems, where multiple agents interact over a communication graph. The authors propose Coop-SE, a fully decentralized extension of the Successive Elimination algorithm, and prove that it achieves individual regret bounds of $O(\\mathcal{R}/m+A^2+A\\sqrt{\\log T})$, which is importantly independent of the graph's diameter. They also introduce two variants that handle communication constraints: Coop-SE-CONGEST (for small message sizes) and Coop-SE-Comm-Cost (for few communication rounds), both maintaining diameter independent regret guarantees. A lower bound is also presented, supporting the near-optimality of their approach.", "questions": "1. As noted earlier, the primary reason for my current score is the $T$-dependent gap between the regret upper bounds and the lower bound. That said, I do recognize the motivation outlined in Section 1.1 for pursuing diameter-independent bounds, particularly through the use of $T$-dependent terms to illustrate worst-case scenarios. I also acknowledge that the bounds presented in this work are strictly stronger than those in prior studies such as [1]. Given this, could the authors clarify how their algorithms are expected to perform on a fixed problem instance as a function of $T$? Specifically, do the proposed methods offer practical advantages over existing algorithms in such settings?\n2. Could the authors provide an intuitive explanation for the emergence of the $O(\\sqrt{\\log T})$ and $O(\\log T)$ terms in the regret upper bounds? What underlying factors contribute to this dependence? Additionally, have any attempts been made to reduce or eliminate this $T$-dependence, and if so, what challenges made it difficult to achieve?\n3. In Sections 7.1 and 7.2, the authors describe preprocessing phases required to construct a spanning tree or clustering for the limited communication algorithms. How much global knowledge about the communication graph is assumed or required from the agents during these phases? Additionally, could the authors clarify how regret is accounted for during these preprocessing steps? Since each round contributes to the overall regret, it would be helpful to understand how these initial phases impact the total regret accumulation.\n\n[1] Wang, Xuchuang, and Lin Yang. \"Achieving near-optimal individual regret low communications in multi-agent bandits.\" The Eleventh International Conference on Learning Representations (ICLR). 2023.", "limitations": "Yes", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n- **Quality:** The paper’s main claims are backed by thorough and well-structured proofs, demonstrating a strong theoretical foundation.\n- **Clarity:** The authors effectively explain the motivation behind removing diameter dependence, using intuitive examples. The algorithms and proof techniques are clearly described and mostly self-contained within the main paper.\n- **Significance:** Although cooperative multi-agent MAB has been studied extensively, this is the first work to achieve individual regret bounds that are independent of both the graph diameter and the number of agents.\n- **Originality:** While the Successive Elimination and message passing ideas are not new in this setting, the paper introduces original contributions—such as implicit synchronization across agents and cluster-based strategies—to obtain diameter-independent bounds.\n\nOverall, I am convinced that achieving diameter-independent bounds is important, and appreciate the authors’ effort to also discuss limited communication settings. \n\n**Weaknesses:**\nRather than separating into broad quality, clarity, significance and originality categories, I will outline my main concerns in a more detailed manner below.\n- While the regret bound in Theorem 2 (As well as Theorems 4 and 5) is claimed to be significant due to its independence from the graph diameter, I am not fully convinced of its practical value because of the presence of a $O(\\sqrt{\\log T})$-dependent term. As $T$ grows, this term can dominate, potentially nullifying the advantage of removing diameter dependence. In fact, as noted in line 194, the *actual* bound is $O(A\\min (A+\\sqrt{\\log T},D))$, meaning that for sufficiently large horizons, the regret essentially matches the bound of [1]. This raises concerns about the tightness and novelty of the result. The absence of experimental validation to support the claimed improvements further amplifies this concern, as it leaves open the question of whether the proposed algorithm offers tangible advantages in realistic settings.\n- This concern is further reinforced by the significant gap between the $O(A\\sqrt{\\log T})$ additive term in the upper bound and the $\\Omega(\\sqrt{A})$ term in the lower bound. It remains unclear whether the $T$-dependence in the additive term is truly necessary, or whether a tighter, $T$-independent bound might be achievable.\n- While the treatment of limited communication settings in Sections 7 and 8 is valuable and introduces novel ideas, I believe addressing the substantial gap in all of the regret bounds is a more pressing issue. This gap makes the overall theoretical contribution feel somewhat incomplete. Furthermore, the regret bound for Coop-SE-Comm-Cost includes a larger additive term of $O(A\\log T)$, which—aside from being independent of the gaps—effectively offsets the cooperative benefit of the $O(1/m)$ term by dominating it for large $T$.\n- As previously noted, this work does not include any experimental evaluation. While the primary contributions are theoretical, it would still be valuable to empirically demonstrate that the proposed algorithms outperform baseline methods in practice—at least in representative scenarios. This is particularly important given the noticeable gap between the upper and lower bounds on regret, which raises questions about the practical tightness of the theoretical results.\n\n[1] Wang, Xuchuang, and Lin Yang. \"Achieving near-optimal individual regret low communications in multi-agent bandits.\" The Eleventh International Conference on Learning Representations (ICLR). 2023.\n\nSome other concerns – \n- The overall structure of the paper could benefit from refinement. The Introduction and Related Work sections extend to page 4, which feels overly long. Consider moving parts of the Related Work—particularly the final paragraph, which discusses broad extensions of cooperative bandits not directly relevant to the paper’s main contributions—to the appendix. This would free up space to include a more detailed explanation of the Coop-SE algorithm in Section 4, and to add a proper Conclusion and Future Work section to the main paper.\n- Additional proofreading would improve the paper. For instance, there appears to be a typo in line 73 regarding the regret bound for Coop-SE-Comm-Cost, which is inconsistent with the other results presented. The algorithms proposed in the paper should also be mentioned explicitly in the abstract. In line 184, the word “is” should be removed. Moreover, Algorithm 2—a simplified version of Coop-SE—is included in the main text but is never referenced or discussed, which may confuse readers. There is also a mismatch in the presentation of regret bounds: the lower bound is given in minimax form, while the upper bounds are instance-dependent. This transition should be explicitly addressed in the main paper. Lastly, the spanning tree notation $\\mathcal{T}$, introduced in line 335, is used without prior definition in the main text.", "was_revised": true, "final_justification": "As I detailed in my response to the discussion initiated by the AC, I will not be changing my score at this time.", "rebuttal": "Thank you for your comments. We hope to have addressed all your comments in the rebuttal below, and would be happy to continue discussing this with you during the author-reviewer discussion period. \nIf you find our answers appropriate and satisfactory, we would be grateful if you would consider raising your score.\n\n# Weaknesses\n\n>”...I am not fully convinced of its practical value because of the presence of a $O(\\sqrt{\\log(T)})$-dependent term. As $T$ grows, this term can dominate, potentially nullifying the advantage of removing diameter dependence...”\n\nWe emphasize that the main focus of our paper is theoretical. We would like to understand the inherent regret bound and its dependence on the various parameters of the problem.\nPrevious works had an additive term of $D$, the diameter of the graph.\nWe highlight that one needs to think of the diameter $D$ as a function of $m$, the number of nodes in the graph, which is also the number of agents.\nAn interesting communication network is a grid graph where $D=\\sqrt{m}$. Since the ideal regret would be at least $\\mathcal{R} / m$, if we aim for low regret, the number of agents $m$ should be a function of $T$.\nThis implies that $D$ is also a function of $T$ (indirectly, through $m$).\nHence, the dependency on $D$ hides a dependency on $T$, which is potentially polynomial for small gaps.\n\nAbout the actual parameters, even in the extreme case that $T=10^{50}$, the number of atoms on Earth, our bound is very reasonable, since $\\sqrt{\\log(T)} < 11$. Having a diameter more than 11 is definitely reasonable in many cases. We stress again that our focus is theoretical, and this numerical example is only to highlight why in many cases the main term would be $D$.\n\n\nAs discussed in Section 1.1, one can see that small sub-optimality gaps ($\\Delta \\approx 1/\\sqrt{T}$) may contribute a lot to the regret. If the regret bound depends on the diameter, one remains with a polynomial dependency on $T$ (for example, $T^{1/6}$ for a grid graph), and increasing the number of agents will not help. But with the bounds from Coop-SE, for a sufficiently large number of agents, one remains with only $A^2+A\\sqrt{\\log(T)}$ regret.\n\n>”...It remains unclear whether the $T$-dependence in the additive term is truly necessary, or whether a tighter, $T$-independent bound might be achievable.”\n\n\nLet us give an intuition about the $\\log(T)$ and $\\sqrt{\\log(T)}$ in the additive terms. The $\\log(T)$ terms (or $\\sqrt{\\log(T)}$) are there to ensure high-probability concentration bounds. \nSince we need the concentration bound to hold simultaneously for any agent, action and time step, we have an actual $\\sqrt{log(mAT)}$ term.\n\nThe additive $\\sqrt{\\log(mAT)}$ term arises in cases where the number of agents is large compared to the stage length. In sparse graphs like the line graph, even with many agents, only $O(t^2)$ samples can be collected by time $t$. This leads to a $\\sqrt{\\log(mAT)}$ term from concentration bounds. See line 977 in the appendix.\n\nTo summarize, these logarithmic terms are due to the concentration bounds, which we require for our analysis. The tightness of the lower bound remains an open question, as we mention in lines 201-202.\n\n\n>\"While the treatment of limited communication settings in Sections 7 and 8 is valuable and introduces novel ideas, I believe addressing the substantial gap in all of the regret bounds is a more pressing issue.”\n\nWe agree that achieving an algorithm that gives the best possible regret bound would be a substantial contribution, however, we feel that we made significant progress in that direction.\nIt is still an open question whether the lower bound of $\\sqrt{A}$ is indeed the tightest, and we mention this open problem in the paper (lines 201-202 and in Appendix A lines 818-819).\n\n>”This gap makes the overall theoretical contribution feel somewhat incomplete.”\n\nThe main contribution of the paper is a simple algorithm, and an analysis that shows that this algorithm achieves $\\mathcal{R}/m + A^2 + A\\sqrt{\\log(T)}$ individual regret for any graph.\nOther methods depend on the diameter $D$.\nAs we mentioned before, the diameter naturally depends on the size of the graph, $m$, the number of agents. The number of agents is a function of $T$, if we aim to achieve low regret. Please see Section 1.1 for more explanation of why in some natural cases, those methods yield $T^c$ regret, for $c>0$.\n\n>”Furthermore, the regret bound for Coop-SE-Comm-Cost includes a larger additive term of $O(A\\log T)$, which—aside from being independent of the gaps—effectively offsets the cooperative benefit of the $O(1/m)$ term by dominating it for large $T$.”\n\nWe discussed before the relationship between $A\\sqrt{\\log(T)}$ and the diameter $D$.\nAn additional issue that one needs to consider is the sub-optimality gaps.\nThe gaps are parameters that may contribute substantially to the regret. The benefit of $O(1/m)$ still has a high impact, since the gaps might contribute $\\sqrt{T}$ regret, as explained in Section 1.1. The $(1/m)$ term overcomes this potentially large $\\sqrt{T}$ regret.\n\n>”As previously noted, this work does not include any experimental evaluation...”\n\nThis work's main focus is theoretical and therefore does not include experiments.\n\n# Other concerns\n\nWe thank the reviewer for their suggestions.\nWe will correct the typos and inconsistencies.\nFor completeness, Theorem 4 should be stated as: $O(\\mathcal{R}/m + A\\sqrt{\\log(mAT)} + A^2)$, and Theorem 5 as: $O(\\mathcal{R}\\log(A)/m + A\\log(A)\\log(mAT)) $.\n\n\n# Questions\n\n>Q1 “...could the authors clarify how their algorithms are expected to perform on a fixed problem instance as a function of $T$? Specifically, do the proposed methods offer practical advantages over existing algorithms in such settings?”\n\nOther methods suffer from a regret of at least $D$, where $D$ is the diameter of the graph. This holds independently from the number of agents.\nOur algorithm offers a much better regret.\n\nHere is how we expect our algorithm to work on a cycle graph with sufficiently many agents.\nAn agent at time $t$ will receive about $t^2$ samples. This implies that it will be able to discard a sub-optimal action $i$ after roughly $\\log (T) / \\Delta_i$ rounds, in contrast to the single-agent setting where the elimination occurs only after $\\log (T) / \\Delta_i^2$ . Note that this time can be much smaller than the diameter $D$, and this is the main advantage of our algorithms and analysis.\nAn important aspect of the algorithm is that agents send the actions they discarded, and therefore guarantee that the agents have similar policies.\n\n\n**A more detailed comparison with other methods:**\nIn UCB there is no guarantee regarding the order in which the agent explores.\nThe UCB algorithm analysis bounds the number of rounds the sub-optimal actions are chosen.\n\nIn the multi-player setting, if we only bound the number of times the sub-optimal actions are played, this is not sufficient to guarantee that the following scenario will not happen.\nIt could be that many agents played the best action in many rounds. They enjoy extremely low individual regret, but these agents didn’t contribute to the exploration of sub optimal actions.\nOn the other hand, a few agents that played the sub optimal actions can play them many times. Hence, in such a scenario we have high individual regret, yet small group regret.\n\nIf one wants to use UCB and achieve individual regret, one must show that the individual exploration of different agents is similar. Alternatively, one can use a reduction to a complete graph, as mentioned in Wang et al. [1]. In a reduction to a complete graph, one introduces a delay of $D$, which is added to the regret.\n\nWang et al. [1] use a version of UCB and give a precise analysis for the complete graph with extremely low communication. To address a general graph, they give a general reduction.\nTheir reduction implicitly assumes that all agents’ policies are the same (as far as we understand). The reviewer may look at Wang et al. [1], section G.2: “the algorithm solves a problem equivalent to a CMA2B with communication delay D on a complete graph”. (CMA2B is an abbreviation of “Cooperative multi-agent multi-armed bandits”, and $D$ is the diameter). The reduction to a complete graph requires delay of $D$ which is added to the regret.\n\nCoop-SE does not depend on the diameter $D$, and enjoys better regret.\n\n\n\n>Q2 ”Could the authors provide an intuitive explanation for the emergence of the  $O(\\sqrt{\\log(T)})$  and $O(\\log(T))$ terms in the regret upper bounds? ... Additionally, have any attempts been made to reduce or eliminate this $T$-dependence…?”\n\nAs we mentioned before, the $\\sqrt{\\log(T)}$ and the $\\log(T)$ terms in the additive term are due to the use of concentration bounds, which are required for our analysis.\nThe reviewer may refer to our answer to a previous comment they made.\n\n\n> Q3 “How much global knowledge about the communication graph is assumed or required from the agents during these phases? Additionally, could the authors clarify how regret is accounted for during these preprocessing steps?”\n\nSince we assume the agents have common knowledge of the communication graph, the spanning tree is also part of it, and all the agents know it in advance. \n\nConstructing a spanning tree in a distributed way has been studied in the communication networks community; see Peleg [2].\n\nConstructing the spanning tree in an online fashion while maintaining low regret under communication constraints remains an open question that is beyond the scope of this paper.\n\n--------------\n\n[1] Wang, Xuchuang, and Lin Yang. \"Achieving near-optimal individual regret low communications in multi-agent bandits.\" The Eleventh International Conference on Learning Representations (ICLR). 2023.\n\n[2] Peleg, David. “Distributed computing: a locality-sensitive approach”. SIAM, 2000."}, {"review_id": "Uexcdadbxm", "reviewer": "Reviewer_oAWf", "summary": "This paper studies the cooperative stochastic multi-agent multi-armed bandits problem, where multiple agents are connected by a undirected connected graph. In this model, multiple agents aggregate information via communication to speedup the learning process. Importantly, this paper proposes a cooperative algorithm with a regret bound, independent of any graph parameter. Authors also provide a lower bound and discusses the regret achievability under two communication constraints, including communication-round constraint and communication-bit constraint.", "questions": "- Can authors discuss more why the current method does not work for UCB?\n\n- I am a bit worried about the significance of individual regret in the stochastic multi-agent MAB setting, though it is indeed interesting in non-stationary setting, Many existing papers in stochastic setting use group regret (or equivalently average regret) as the metric, but those algorithms also have a low individual regret, and they just not give a formal proof on that. This is because in stochastic setting, the high-level behind speedup is to aggregate samples across agents, in light of the Hoeffding bound. Can author mention a paper in the stochastic setting that have low group regret, but individual regret is large?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength: \n\n- This paper proposes a simple cooperative algorithm, ensuring a low individual regret for each agent. Importantly, the regret bound is independent of any graph parameter. This result implies that if the number of agents goes to infinity, the regret bound is entirely independent of arm gap.\n\n- This paper presents a lower bound for the individual regret nearly matching the upper bound in the minimax form.\n\n- Further, authors consider the constrained communication setting. For both logarithmic communication bit and logarithmic communication  rounds, two algorithms are proposed to achieve regret bounds, independent of graph parameter.\n\n\nWeakness: I don't see any major weakness of this paper, and authors have acknowledged that there exists a gap between the upper and lower bounds. Though the design of algorithm is simple, ie., extending elimination based algorithms to multi-agent setup, it is indeed effective, and authors do a careful analysis to get a good regret bound. \n\nThe reason why I don't give a higher score is that this paper does not give any algorithmic contribution and the analysis, though careful, seem not to be applicable to broader cases (i.e., applying to UCB or TS algorithm, but the current analysis only works for elimination algorithms).\n\n\nSome minor suggestions on presentation:\n\n- For Table 1, I'd suggest adding the definitions of $f(G)$ and $h(G)$ in either the table caption or the footnote to remind readers.\n- In warmup section, authors do not provide any pseudocode, even no informal version and informative description, which makes the section less informative. After quick passing section 3 (warmup section), I don't feel any connection between section 3 and section 4. This means I can directly read section 4 without reading section 3, which makes section 3 redundant. I would suggest removing section 3 if it does not give any warmup functionality.\n- In line 12, algorithm 6, it should take union over all neighbors $v'$.", "was_revised": true, "final_justification": "While there is room for further improvement, I find the overall contributions good and lean toward a weak acceptance.", "rebuttal": "Thank you for your comments. We hope to have addressed all your comments in the rebuttal below, and would be happy to continue discussing this with you during the author-reviewer discussion period. \nIf you find our answers appropriate and satisfactory, we would be grateful if you would consider raising your score.\n\n\n# Weaknesses\n\n>“The reason why I don't give a higher score is that this paper does not give any algorithmic contribution and the analysis, though careful, seem not to be applicable to broader cases (i.e., applying to UCB or TS algorithm, but the current analysis only works for elimination algorithms)”\n\n> Q1: “Can authors discuss more why the current method does not work for UCB?”\n\nWe will answer the weakness and the question together.\n\nThe algorithm we introduced, Coop-SE, is new since it is not just SE with message passing, but in our implementation each agent eliminates what **other** agents have eliminated according to **their** observations (up to the delay) as well as what the agent observed and calculated. This is a critical modification, which makes it possible to align the policies. \n\nWithout this modification, an agent might not eliminate a sub-optimal action, even if other agents eliminated it. \nIn such a case, that agent will continue sampling this sub-optimal action alone and might incur high individual regret in this scenario.\n\nIn Coop-SE, we eliminate this action due to the elimination messages from the other agents.\nThis algorithmic change is crucial in our analysis of individual regret.\n\nThe following is a discussion of the challenges of achieving individual regret using UCB.\n\nIn UCB there is no guarantee regarding the order in which the agent explores.\nThe UCB algorithm analysis bounds the number of rounds in which the sub-optimal actions are chosen.\n\nIn the multi-player setting, if we only bound the number of times the sub-optimal actions are played, this is not sufficient to guarantee that the following scenario will not happen.\nIt could be that many agents played the best action in many rounds. They enjoy extremely low individual regret, but these agents didn’t contribute to the exploration of sub-optimal actions.\nOn the other hand, a few agents that played the sub optimal actions can play them many times. Hence, in such a scenario we have high individual regret, yet small group regret.\n\nIf one wants to use UCB and achieve individual regret, one must show that the individual exploration of different agents is similar. Alternatively, one can use a reduction to a complete graph. In a reduction to a complete graph, one introduces a delay of $D$, which is added to the regret.\n\n\n>“Can author mention a paper in the stochastic setting that have low group regret, but individual regret is large?”\n\nTo see the main difference between group regret and individual regret, note that when we have $m=T$ agents, we can take any agent and let it play randomly, and this increases the group regret by only $1$. This simple example shows the challenges in establishing a general transformation from group regret to individual regret.\n\nFrom a theoretical perspective, it is highly challenging to show individual regret and somewhat easier to prove group regret. As a concrete example, UCB-like algorithms are highly challenging for providing individual regret guarantees, although they have been shown to achieve good group regret."}, {"review_id": "iZZkosAFfF", "reviewer": "Reviewer_LDks", "summary": "The paper considers the problem in which multiple agents (vertices of a graph) face the same stochastic bandit problem and can communicate over the edges of the graph. The authors give algorithms for this problem with strong individual regret guarantees. Importantly, these bounds are independent of the diameter of the graph. The first algorithm requires much information to be passed across each edge on each trial. However, the later algorithms require much less, and one algorithm only requires a logarithmic number of trials in which to communicate. The authors also give an almost matching lower bound on the individual regret.", "questions": "I have no questions for the authors as I feel I understand the results. Since there is no section for comments I will point out some typos here:\n\nIn Line 149 you say that the agent observes a reward but you don’t say that the reward is drawn from the SMAB distribution.\n\nYou have some small brackets in Theorem 2 which should be big brackets. Same for Line 194.\n\nTypo in definition 10 - begging instead of beginning", "limitations": "No limitations noticed.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "I think that the results of this paper are quite remarkable. At first I didn’t believe that the results could be possible (especially the O(log(m)) message size results) but after thinking about it I now believe that they could be true. Unfortunately, I haven’t had the time to read through the proof and verify the results.\n\nThe lower bound is also a nice addition to the paper.\n\nThe results of the paper are clearly communicated.\n\nAlthough this is not a weakness of the result itself, I feel that, in order to make the paper self contained, there should be some explanation of how SE works before we jump into the description of Coop-SE as the explanation of the latter assumes familiarity with the former.", "was_revised": true, "final_justification": "Surprising result - I am on the fence between borderline and full accept although tend towards borderline.", "rebuttal": "We thank the reviewer for their highly positive review.\nWe're happy to address any questions the reviewer might have during the author-reviewer discussion. If we have resolved the reviewer's concerns, we would appreciate it if they could consider raising their scores.\n\n\n>\"Although this is not a weakness of the result itself, I feel that, in order to make the paper self contained, there should be some explanation of how SE works before we jump into the description of Coop-SE as the explanation of the latter assumes familiarity with the former.\"\n\nWe will certainly include this in the final version.\n\n\n# Questions\n\n>”In Line 149 you say that the agent observes a reward but you don’t say that the reward is drawn from the SMAB distribution.”\n\n>”You have some small brackets in Theorem 2 which should be big brackets. Same for Line 194.”\n\n>”Typo in definition 10 - begging instead of beginning”\n\nThank you for the suggestions. We will address all of them in the final version."}]

Author rebuttal:

Meta-review: **Summay**

This paper provides individual regret bounds for cooperative multi-agent multi-armed bandits over an underlying topology, independent of graph diameter, and also analyzes trade-offs with message size and communication rounds.

** Strengths**
* The paper has a solid and clear contribution in the relatively crowded space of multi-agent stochastic bandits.
* While fundamental ideas have been proposed in the literature, this paper elegantly leverages these ideas to achieve the improved individual regret in this setting. 

** Weaknessess** 
* The paper presentation in its current form could be improved in terms of distinguishing the claimed contributions from what is already known in the literature. 

** Final justifications**
* There were extensive and engaging discussions between the authors and reviewers regarding the novelty of the ideas and the theoretical analysis. While the authors acknowledged that the paper could better clarify how the proposed algorithms and analysis differ from prior work, the AC and most reviewers remain positive about its merits. Therefore, I recommend acceptance. That said, the paper should go through substantial revision in the camera-ready version to address the reviewers’ comments.
Decision: Accept (poster)