Distributed Multi-Agent Bandits Over Erdős-Rényi Random Networks
Authors: Jingyuan Liu
Hao Qiu
Lin Yang
Mengfan Xu
Venue: NeurIPS 2025 poster ()
Keywords: distributed stochastic bandit
Primary area: theory

Abstract: We study the distributed multi-agent multi-armed bandit problem with heterogeneous rewards over random communication graphs. Uniquely, at each time step $t$ agents communicate over a time-varying random graph $\mathcal{G}\_t$ generated by applying the Erdős–Rényi model to a fixed connected base graph $\mathcal{G}$ (for classical Erdos-Rényi graphs, $\mathcal{G}$ is a complete graph), where each potential edge in $\mathcal{G}$ is randomly and independently present with the link probability $p$. Notably, the resulting random graph is not necessarily connected at each time step. Each agent's arm rewards follow time-invariant distributions, and the reward distribution for the same arm may differ across agents. The goal is to minimize the cumulative expected regret relative to the global mean reward of each arm, defined as the average of that arm’s mean rewards across all agents. To this end, we propose a fully distributed algorithm that integrates the arm elimination strategy with the random gossip algorithm. We theoretically show that the regret upper bound is of order $\log T$ and is highly interpretable, where $T$ is the time horizon. It includes the optimal centralized regret $\mathcal O\left(\sum_{k: \Delta_k>0} \frac{\log T}{\Delta_k}\right)$ and an additional term $\mathcal O\left(\frac{N^2 \log T}{p \lambda_{N-1}(\operatorname{Lap}(\mathcal{G}))} + \frac{KN^2 \log T}{p}\right)$ where $N$ and $K$ denote the total number of agents and arms, respectively. This term reflects the impact of $\mathcal G$'s algebraic connectivity $\lambda_{N-1}(\operatorname{Lap}(\mathcal{G}))$ and the link probability $p$, and thus highlights a fundamental trade-off between communication efficiency and regret. As a by-product, we show a nearly optimal regret lower bound. Finally, our numerical experiments not only show the superiority of our algorithm over existing benchmarks, but also validate the theoretical regret scaling with problem complexity.

Distributed Multi-Agent Bandits Over Erdős-Rényi Random Networks
Jingyuan Liu" Nanjing University j iingyuanliu@smail nju. edu. cn
Hao Qiu'
Università degli Studi di Milano hao qiu@unimi... it
Lin Yang
Mengfan Xu University of Massachusetts Amherst mengf anxu@umas..eeeemmmmo edu
Nanjing University 1 linyangenju, edu. cn
Abstract
We study the distributed multi-agent multi-armed bandit problem with heteroge- neous rewards over random communication graphs. Uniquely, each time step agents communicate over time-varying random graph G. generated by applying the Erdös-Rényí model fixed connected base graph (for classical Erdos- Rényi graphs, G is complete graph), where each potential edge in G is randomly and independently present with the link probability p. Notably, the resulting ran- dom graph is not necessarily connected at each time step. Each agent's 's arm rewards follow time-invariant distributions, and the reward distribution for the same arm may differ across agents. The goal is to minimize the cumulative expected regret relative the global mean reward of each arm, defined the average of that arm't 's mean rewards across all agents. To this end, we propose fully distributed algo- rithm that integrates the arm elimination strategy with random gossip algorithm. We theoretically show that the regret upper bound is of order log 7 and is highly interpretable, where T is the time horizon. includes the optimal centralized re- K log
gret O [EnAnSo
log'T) and an additional term O As
N²3 log
p
where N and K denote the total number of agents and arms, respectively. This term reflects the impact G's algebraic connectivity A (Lap(9)) and the link probability p. and thus highlights fundamental trade-off between communication efficiency and regret. As by-product, we show a nearly optimal regret lower bound. Finally, our numerical experiments not only show the superiority of our algorithm over existing benchmarks, but also validate the theoretical regret scaling with problem complexity.
Introduction
Multi-armed bandit (MAB) is a widely studied framework for sequential decision-making under uncertainty [Auer et al., 2002]. In this setting, an agent selects an arm from multiple options in each round, observes the reward from the chosen arm, and aims maximize the cumulative expected reward. The emergence of large-scale cooperative systems holds true in various applications ranging from sensor networks [Ganesan et al., 2004, Zhu et al., 2016] to federated learning [Ye et al., 2023, McMahan al., 2017] and edge computing [Wang al., 2022a, Ghoorchian and Maghsudi, 2020]. has naturally motivated interest distributed multi-agent multi-ane nulti-armed bandit
Equual contribution, alphabetical order. 'Coresponding author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

(MA-MAB) problem, where multiple agents collaboratively learn to optimize rewards. MA-MAB settings are typically categorized as homogeneous [Landgren et al., 2016a, Martinez-Rubio et al.. 2019] or heterogeneous [7hu et al., 2021, Xu and Klabjan, 2023], depending on whether the reward distributions for the same arm are identical across agents. The heterogeneous setting, in which reward distributions vary across agents, is significantly more general but more challenging, and thus has attracted growing attention. It introduces substantial difficulties, as agents must make sequential decisions under uncertainty while relying limited information about both their own rewards and the actions or observations of other agents.
Another challenging aspect of MA-MAB lies in the underlying communication protocol, which constrains how agents share information with one another. Decentralized MA-MAB settings are more realistic than centralized ones-where all agents can communicate with any other agent- as they restrict communication to immediate neighbors defined by a graph structure. Much of the existing work has focused on time-invariant graphs [Zhu et al., 30 where the communication graph remains fixed throughout. However, the complexity of many real-world decentralized systems, such wireless ad-hoc networks, necessitates the use of time-varying graphs [Zhu and Liu, 2023], particularly random graphs [Xu and Klabjan, 2023]. This added complexity significantly complicates both the communication and learning dynamics. Notably, [Xu and Klabjan, 2023] is the first to consider classical Erdös Rénti (E-R) random graphs in the MA-MAB setting, where any two agents can communicate with probability p at each time step. However, it is possible that some pairs of agents can never communicate directly due to inherent topological constraints. This scenario has been formulated as more general version of the E-R graph, where two agents can communicate with probability/ p only if there is an edge between them in a base graph. Note that when the base graph is a complete graph, it is equivalent to classical (E-R) random graphs, implying consistency. To date, this setting remains unexplored, which motivates our work.
To date, a line of work has studied regret bounds under various graph structures, where connectivity or sequential connectivity is typically required. For example, in the context of time- invariatt graphs, Martinez- Rubio et al. [2019] and Zhu et al. [2021] analyze distributed bandits over connected graphs and derive log T' regret bounds. For time-varying graphs, Zhu et al. [2025] obtains log T regret bounds under the assumption of B-connectivity, where the union of any I consecutive graphs must be connected. In the classical Erdōs-Rényi model [Erdos et al., 1960] over fully connected agent communication, Xu and Klabjan [2023] derive regret of order log T but only under the assumption that p 1/2 + 1/2/11 1 - (//NT)9/N- which is larger than 1/2 and can even approach when the number of agents N or the time horizon T is large. This is a strong assumption, as it may not hold in many real-world settings, but is required in their analysis to ensure that the graph is connected with high probability. Relaxing this comnectivity requirement to allow arbitrary p presents a significant challenge. Moreover, their regret bound does not reflect how the link probability p impacts the regret. Incorporating p into the regret expression would significantly improve our understanding of how to choose p in practice a gap that remains open. In this work, we address both of these gaps. To this end, we address the following key research question: Can we solve MA-MAB under new Erdös-Rényl Rényi random networks and heterogeneous rewards, and derive regret bounds that captures graph complexity under much milder assumptions?
Contribution. We provide an affirmative answer to the above question via the following contribu- tions. Methodologically, we solve the MA-MAB problem over general networks with a gossip algorithm, which is widely adopted in distributed settings. Moreover, we adopt an arm elimination based algorithm with minimal number of arm pulls required for each arm to guarantee sufficient information for each agent, which addresses the E-R communication networks.
communication
Analytically, we study the regret of MA-MAB under our proposed algorithm over general Erdōs-Rényi communication networks for any p E (0, 1]. leading to novel contributions. We are the first to 1) explore general Erdos Erdos-Rényi graphs induced by any fixed connected base graphs beyond classical setting that assumes a complete base graphs; 2) obtain a tighter and more interpretable regret bound, which generalizes the bound from the homogeneous Exed-graph setting studied in Martínez- Rubio et al. [2019] to our more challenging heterogeneous setting, as shown in Section 5; 3) relax the assumption of a sufficiently large p used in Xu and Klabjan [2023] and reduce the order of N in the upper bound in their analysis of classical Erdōs Rényi models with complete base graphs. Precisely, N2 log T
we obtain a regret upper bound of order of O (En As the first term accounts for optimal centralized regret, aligning with the lower bound established
Tog + pAx (Lap(()) + KN log KN where
2

---

in Section 5.2, and the last two terms capture the effects of both the link probability and the algebraic connectivity AN-1 (Lap(g)) of the base graph. Moreover, we uniquely characterize how the regret upper bounds are influenced by and A (Lap(g)), which highlights tradeoff between the communication cost (i.e., the number of communication rounds) and regret performance.
Numerically, we implement our proposed algorithm and conduct experiments to validate our theo- retical results with multiple random graph settings and the link probability p. We also compare our methods with existing approaches to demonstrate their effectiveness.
2 Related Works
Distributed online algorithm. Our framework builds on the classical line of work on gossip algorithms [Xiao and Boyd, 2004, Boyd et al., 2006]. Specifically, when agent has access only to local information and communicates solely with its immediate neighbors, adopts a gossip algorithm to aggregate information from agents beyond its local neighborhood, based on weight matrix. Notably, gossip algorithms are widely used in distributed optimization. For example, Duchi et al. [2011], 11, Nedic and Ozdaglar [2009] address distributed convex optimization problems using gossip algorithms. Subsequently, Hosseini et al. [2013], Yan et al. [2013] extend the gossip approach to the online setting and achieve a regret of order vT, assuming convex loss functions. Later, Mateos-Núnez and Cortés [2014] consider distributed online optimization over B-connected and design distributed online primal-dual algorithm coupled with a gossip protocol, also achieving vT regret bound. More recently, Lei et al. [2020] study the same problem over random communication networks CardössRééyy networks) and obtain the same regret order. They further characterize how regret is affected by the link probability p in the Erdōs-Rényi model and the algebraic connectivity of the base graph G. We consider the same graph topology but focus on multi-agent multi-armed bandits, which differ significantly from online convex optimization and introduce the additional challenge of learning the dynamics of bandits. For more comprehensive survey on distributed online optimization, we recommend the reader to Li et al. [2023] and Yuan et al. [2024].
Distributed multi-agent multi-armed bandit. Along the line of work on MA-MAB, several studies [Landgren et al., 201 ba Zhu et al., 2020, Chawla et al., 2020, Wang et al., 2022b, 2020, Zhu et al., 2025, Martínez- Rubio et al., 2019, Agarwal et al., 2022, Sankararaman et al., 2019, Zhu et al., 2021, Zhu and Liu, 2023, Xu and Klabjan, 2023, Yi and Vojnovic, 2023] have investigated both homogeneous and heterogeneous settings. In homogeneous settings, numerous works incorporate gossip algorithms to reduce regret in terms of the number of agents; information sharing among agents accelerates the concentration of reward observations. For example, Landgren et al. b2)16a, firstly formulate this problem and solve it using gossip algorithms. Martínez- Rubio et al. [2019] achieves the optimal centralized regret-indepeent independent of the number of agents and matching that of the single-agent bandit-plus an additional term depending the spectral gap of the communication matrix. Chawla et al. [2020] characterizes the segret-cmmmnication tradeoff, considers circular ring graphs, and improves regret. Wang al. [2022b, 2020] further focus optimizing communication efficiency to minimize the number of communication rounds while guaranteeing regret performance. In contrast, we consider more challenging heterogeneous settings and also characterize the regret- communication trade-off. Here gossiping enables regret reduction in terms of the order of T; without information from other agents, the regret can easily be linear in T [Xu and Klabjan, 2025]. In this direction, Zhu et al. [2021] is the first to study heterogeneous rewards over a time-invariant connected graph and establishes regret bounds of order log T' Zhu and Liu [2023] extend this to B-connected graphs, also achieving regret bounds of order log T'. Recently, Xu and Klabjan [2023] propose a basei algorithm for the classical E-R model and obtain regret bounds of order log ' when p is sufficiently larger than 1/2 to ensure the graph is connected with high probability. More generally, Yi and Vojnovic [2023] consider MA-MAB with heterogeneous rewards in the adversarial environment and establishes a regret bound of order 22/3 In contrast, we consider the stochastic setting with general Erdös-Rény: Rényi random networks, without any assumption on p.
3 Setting and Notations
In this section, we formally define the problem of interest, starting with general notations. A full notation chart can be found in Appendix E.
3

---

General Notations. For a matrix M E R let [M], denote the entry in the i-th row and j-th column. Given a doubly stochastic matrix P E Edxd we denote by (P) its second largest eigenvalue, Let 6; E R be the i-th standard basis vector, 1 E IR" the all-ones vector, and la the d x d identity matrix. We use I[-} denote the indicator function, which equals 1 if the condition inside holds, and 0 otherwise. Moreover, we use [n]] (1.2, _n} to denote set of indices.
Multi-Agent Multi-armed Bandit. We consider a multi-agent multi-armed bandit (MA-MAB) setting involving N agents. The bandit problem is run over time horizon of T' In each round t E [T], every agent E [N] selects an arm (t(t) E [K] and receives a local stochastic reward Xs,A.10 (t) drawn independently from unknown, time-invariant distribution IP (1) supported on [0, with mean Ms,A.(1) = B[[X (.)) E [0,1]. However, the agent's true objective depends on the global reward X (1) (t), where X (A())) N EjE[N (,,A,to())) which is the average reward over all agents and is not observable by any agent. Accordingly, define the global mean reward for arm k as ur == N ΣjENN] M5,. by taking the expectation of xx),), where j'j,: is the mean of Fj The underlying target is to optimize the global mean reward, and hence agents require estimates of the global mean reward values for each arm in order to identify the global optimal arm with the highest global mean reward. We further use Ti to denote the total number of times agent i has selected arm k up time by (t) E. == (s) k).
Throughout, we focus on decentralized setting where N agents are distributed on undirected time-varying graphs and communicate via the graphs. Specifically, we consider a communication graph based on Erdös-Rény Rényyi random graphs. More precisely, agents communicate via a time- varring graph G; EV,&e), where the vertex set V = [N]] is fixed, but the edge set & may vary at each round t. Uniquely, each communication graph G, is generated based on an underlying undirected, fixed, and connected (but not necessarily complete) buse graph G (V, E) that defines all feasible communication edges. The connectedness of the base graph is essential to avoid linear regret as proved in Theorem 4 in Xu and Klabjan [2025]. In every round f, each edge in graph G is independently in G. with probability p E (0, 1]. Two agents can communicate if and only if there is an edge between them in o--namely, an active edge. Formally, the random graph generation reads as follows.
Assumption 3.1 (Erdös-Rényi Random Graph), In each round f, the random communication graph G. (V, E,,, generated from the base graph G meets:
[p. if (f. E,,
P ((i.j) E &))
10, otherwise,
for all vertices i.j E V. We refer to p as the link probability.
Thus, & C E for all t. N; = {j E V: (i.j) E E} denote the neighbors of agent i in the base graph G, and (N(() = (j E V: (1.f) E 3.} denote the active neighbors of agent in round f, clearly satisfying (t) C.M
The shared objective for each agent is design distributed algorithm æ that minimizes the global regret over T' rounds; in other words, all agents share a common target that makes consensus possible and necessary. Precisely, we first define the individual regret, which represents the objective of any agent i E [N]. as:
T (eg.r((T) = Ty² Σ (A.0)) = Σ ΣSA.0. A. t=1
T
(1)
t=1
where 1²' ma M4 is the optimal global mean reward, and A = kt- pg is the global suboptimality gap for arm k. Notably, agents aim to optimize the global mean rewards of the pulled arms, i.c., to pull the global optimal arm. We define the individual regret as the cumulative difference between the global mean reward of the global optimal arm and that of the actual arm pulled by each agent. Building on this, we define the global regret of the entire system for algorithm æ as the sum of the individual regret over all agents:
T
Reg (T)
Σ (T) = NT KE[N]
ΣΣ
MAR())
ΣΣ
A A.(0)
RE[M
REIN] 1
which establishes the equivalence of Equation (1) in the context of individual agents.
4

---

4 Algorithm: Gossip Successive Elimination
In this section, present our proposed methodology. Unlike existing work gossip ban- dits [Martínez-Rubic et al., 2019, Zhu et al., 2021], which assumes fixed connected graphs, we handle the fundamental challenges of randomness and possible disconnectivity in the random com- munication graph. To this end, we propose distributed bandit algorithm designed for Erdös-Rény random graphs (Assumption 3.1) based on arm elimination, named Gossip Successive Elimination (GSE) (Algorithm 1). GSE combines three key components: an arm elimination protocol, refined weight matrix, and novel confidence interval design. Specifically, we adopt the arm elimination framework [Even-Dar et al., 2006] in distributed bandits setting, which naturally ensures that all agents pull each arm comparable number of times, so that the global estimates obtained via gossip are not largely biased and not dominated by any single agent's 's feedback. Second, we design a refined weight matrix based on the Laplacian. which guarantees that the weight matrices are i.i.d. across rounds. This construction is crucial to balance information among agents over time and to ensure that the global reward estimates converge to the true global mean reward for each arm. Finally, GSE introduces a new confidence interval with two terms: the first term captures the estimation error due to finite sampling, while the second term accounts for the consensus error, reflecting the approximation introduced by time-delayed information propagation under random gossip. Together, all these novel components enable GSE to jointly address reward heterogeneity and random communication in a principled and analytical paradigm.
The agent needs several parameters, including the link probability p and algebraic connectivity AN-1(Lap(9)) as inputs. Initially, agent i's active arm set S; is set to the full set of arms [K], while both the local reward estimate f (t) and global reward estimate (t + 1) are initialized zero (t = 0). Following the standard practice in existing work [Martínez-Rubil et al., 2019, Zhu et al., 2021, Xu and Klabjan, 2023], we assume that XN-1(Lap(G)) is known, while allowing the link probability p to remain unknown. In this case, the algorithm can still be implemented, and the corresponding regret upper bound preserved, by adding short burn-in phase to estimate a value ÿ E (). This estimation requires only Ollog 7') time steps. We refer the reader to Appendix C for the details and theoretical analysis of this procedure.
At each round f, agent i observes its active neighbors (t(()) in the communication graph G. which randomly generated from the base graph G according to Assumption 3.1. As part of our key contributions, we consider a weighting matrix W; for gossip as
W. IN
N Tap(G.),
where Lap(G:) denotes the Laplacian matrix of the communication graph G.-
Algorithm 1 Gossip Successive Elimination for Agent i E [N]
Input: Algebraic connectivity (L=i(La)()). total time horizon T, set of arms [K]. link probability
2: Initialization: Active set S; < [K] local reward estimate (r,x (0) <- 0, global reward estimate (1) < 0 for all & E [K]. 3: for part=1 1,2...., T do
4: Select arm (!( E S; with the minimum pull count (t) and update (t)
5: Receive feedback and update statistics for each arm using Equation (4)
6: Remove arm & E S; if there exists an arm k' E St, k' o k. satisfying the elimination condition
in Equation (7)
7: Update the active set S, according to Equation (8)
8: end for
The execution steps of agents run as follow. Agent i selects arm A,(!) from the active set S; with the least number of pulls (t), observes the local reward of (t),, and updates the reward estimates as follows:
Ti.,a (1) [(A((T)= x Xxxu(T))
21 (1)= Σ [Wll.35,&()) + (,, - -t, - 1),
(4)
JEN(()UU()
5

---

where X1 is the feedback observed by agent from pulling arm & at round т. The global estimate (t)(t) is updated via a gossip protocol: at each round E, agent aggregates its own and its active neighbors' estimates, weighting each neighbor j E (t) (i) by the corresponding entry [We]k, of the matrix Wr We also define the gossip-basee upper and lower confidence bounds for arm which remain key criteria for arm elimination and updating S;, as
GUCB, (t, + C. (t), GLCB,, 21,(() c,
Here the confidence bound Cg reads as
(T)
4(VN + +T)
(1) = V N max (mxx(Ti.at) KL*,1)
(5)
max (Tx(() K
with
2N (Tg
2 log (NT) (lg((NTT log(1 - P))
x" =
L' = N
(6)
p\x-1(Lap(O))
The confidence radius in Equation (5) decomposes into two parts. The first term captures the estimation error, arising from the statistical variance of independently sampled rewards for each arm. The second term captures the consensus error, which stems from the cumulative approximation error eтror incurred as agents reach consensus via a gossip- possip-based communication protocol.
Arm elimination occurs if and only if there exists an arm k' + k in S; that meets the condition
GLCB, (t) 2 (
which means that arm has a higher global reward estimate than arm l with high probability. Subsequently, the active set S, is updated
S
Sj- JENi
(8)
This procedure coupled with the arm-elimination strategy ensures that, for every agent, each arm in the active set is pulled roughly equal number of times, ensuring consensus.
5 Regret Analyses
In this section, we analyze the regret of the proposed algorithm and establish an upper bound on the corresponding regret, demonstrating its theoretical effectiveness. Additionally, we derive lower bound for our problem setting, highlighting the problem's inherent complexity and showing that the algorithm is nearly optimal up to some interpretable factors.
5.1
Upper Bound
We start by presenting the regret upper bound for Algorithm To that end, first introduce several technical lemmas that play a key role in the regret analysis. The proofs can be found in Appendix B.
Lemma 5.1. Let us assume that the communication graph follows Assumption 3. Then we have that for Algorithm I, for any agent i E [N), any arm k E [K), and any t E (T), the following holds with probability at least 3
(z),(()) - pul S (t),
where (t) is the confidence bound defined in Equation (5), and T" and L" are the parameters introduced in Equation (6).
Importantly, we show that the estimation error compared to the global mean value is upper bounded by the confidence bound (t). Notably, Ct (t) monotonically decreasing in the number of pulls of arm & by agent i.e., (t), when (t,((t) > KL* Here, KL is the minimal number of pulls required to ensure that agent i has collected sufficient information from all other agents. This also implies that the global estimate ((,(() becomes increasingly accurate and approaches the true mean reward μ4 as the number of pulls increases. As a result, based on Lemma 5.1, we derive the following regret bound for individual agents.

---

Lemma 5.2. Let us assume that the communication graph follows Assumption 3.1. The individual regret of agent defined in Equation (1) for Algorithm 1 bounded as:
Reg., (GSE) I
Σ
(44log(T)
+ 16 166166+N (VN++)) + KL' 3K max:
NA
k:A+30
where Amax = [
Ds denotes the largest reward gap across all arms.
In other words, Lemma 5.2 shows that the regret incurred by any individual agent can be effectively bounded. This result naturally extends to the global regret, as stated in the theorem below.
Theorem 5.3. Let us assume that the communication graph follows Assumption 3.1. The global regret defined in Equation (2) for Algorithm is bounded as:
log(T) AK
No Log(TT
KN log( (NT)
Regr(GSE)
Reg,,((GSE) S SO iE(N]
Σ
Σ k=
pAN-1(Lap(3))
p
where AN- (Lap(G)) is the second smallest eigenvalue of Lap(G).
We continue our discussion how the base graph 9 topology affects the regret bound. In addi- tion to the parameter p. which determines the difference between G and gr, another key factor is \x=((La)()), which reflects the topology of the base graph G. This value is the algebraic con- nectivity or Fiedler value of G, which reflects how well connected the overall graph is. To illustrate this, we next provide more explicit regret upper bounds by specifying A base graph topologies commonly used in distributed optimization Duchi et al. [2011]. The following corollary summarises how the choice of the random gossip matrix in Equation (3) interacts with different topologies of the base graph. The proof of X AN-i(Lap(g) for various base graphs G can be found in Corollary 1 of Duchi et al. [2011].
for different
Corollary 5.4. For specific choices of the base graph G, the global regret upper bound in Theorem 5.3 simplifies as follows:
1) When G is a complete graph with AN AN-1(Lap(9))
= N, and refining L
2 log(NT) log(1 1-p)
in
Equation (6), Theorem 5.3 simplifies to: O (ER:
log T Ae
+ KolgoT
p
2) When G is a VN x VN 2D grid with AN (N-I(Lap(G)) = cos
)) VNN
O(L/N), Theo-
rem 5.3 simplifies to: O (Et-seso Tog
AL
3) When G is an expander graph with bounded ratio between minimum and maximum node degrees and thus A >N=((La)()) = -1)), Theorem 5.3 simplifies to: O (Enouso log KN2 log
+
A
P
Remark 5.5 (Comparison of Regret Bounds). In Theorem 5.3, for any fixed connected base graph G and 0 p 1, obtain the optimal centralized regret O (ERAASO
log (see the lower bound in
D
We emphasize that our regret bound outperforms existing work- many of which are special (degenerated) cases of our more general framework-and and easier to interpret. Notably, Xu and Klabjan [2023] study MA-MAB under the classical E-R model (where G is complete graph) with largely over 1 1/2, and derive a regret bound
Section 5.2) plus an additional term O N2 Tog
KNZ log
p
of O Σ EmAD log(T) A
NlogT")
In the same setting, based on Corollary 5.4, we obtain a regret bound A
of O Σ ER:AAS consider B-connected graphs, which do not capture E-R random graphs; the distinction between the two models is discussed in detail in Yuan et al. [2024]. Finally, when p 1, the communication graph becomes time-invariant, which corresponds to most existing work where connected graphs are assumed. For example, Zhu et al. [2021] and Zhu and Liu [2023] study such settings. The former derive a regret bound of O (EmA
+ KN log())) which is significantly smaller. Also, Zhu and Liu [2023]
N² log which is worse than our results with a dependency A
on N. The latter obtain O max (Endiso
No N. K1. K2) where K2 and K₂ depend on T but lack explicit formulas, may grow arbitrarily large, and are difficult to interpret- at least to the best of our knowledge.
7

---

Remark 5.6 (Regret and Communication Trade-off). We emphasize that our regret upper bound exhibits a novel trade-off between regret performance and communication efficiency in the presence of random graphs. It is straightforward to observe that increasing p reduces the regret bound but increases communication overhead, thereby lowering communication efficiency. For classical E-R graphs. the expected number of agent-to-agent communications per agent over the given time horizon is pNT, while the expected regrets decrease as p increases. Therefore, for fixed time horizon T and given base graph G, be tuned to balance communication overhead and reward maximization, informing practical decision making.
5.2 Lower Bound
In this section, we establish a lower bound on the global regret, as defined in Equation (2). Unlike the upper bound, this lower bound applies to any reasonable algorithm under a specific problem instance, highlighting the problem complexity. Detailed proofs are deferred to Appendix B. We begin by introducing several definitions related to the problem instance and the notion of reasonable algorithm.
Definition 5.7 (Gaussian Instance). An instance v is called a Gaussian instance if, for every agent i [N] and arm k E [K], the reward distribution Pi,, Gaussian with unit variance.
Definition 5.8 (Consistent Policy). Let I denote class of problem instances, and let Reg((z)) (x) denote the regret incurred by policy æ on instance v. A policy (algorithm) is said to be consistent on I if there exist constants C > 0 and E (0, 1) such that Regi (T) meets Reg* (T) < CT for all instances V E I.
We next present the problem instance constructed to establish the regret lower bound. Note that an alternative, equivalent expression the global regret reads as
Reg"(T)
Σ A Σ ([T),(T)).
KE[K]
iE[N]
Thus, to derive a lower bound on regret, it suffices to lower bound the total expected number of pulls ESEIN] & (T)) for suboptimal arms & E [K]. To this end, consider Gaussian instance where each P', k = N(H,, 1) with the random graph communication protocal based any connected base graph G and connection probability and construct perturbed instance v such that:
[N 1), (N + + el)a;) 1), if a k
if a + k,
Pi,.
for small constant (0, 1) representing the level of perturbation. The communication protocal for v' is the same as that for v. Under this perturbation, which defines a new problem instance, we derive the following cemmaation-thhoreeee inequality:
(1 =)+
NTEA: log (R))" + Reg (T))
Σ ([T,,(() JE[N]
(9)
2
which imposes a lower bound on the total number of pulls of arm i across all agents.
By applying this inequality to consistent policy and rearranging the terms, we obtain the following lower bound on regret. The formal statement reads as follows.
Theorem 5.9. Let be consistent policy the class I of Gaussian instances for some E (0, 1).
Then, for all instances v E I and any & E (0, 1), the the following holds:
Regh(T)
2(1-s)
lim T-+00
Σ
log T
(1+))aAr
K: >0
Remark 10 (Comparison with Upper Bounds). Recall that the regret upper bound in Theorem 5.3 consists of two terms: centralized term and additional terms that capture the influence of the communication graph. The lower bound in Theorem 5.9 shows that the centralized component, log O EE-A,s Ay ). tight, thereby establishing the optimality of the centralized regret achieved by Algorithm 1. This result is intuitive: the problem effectively involves N agents collaboratively solving

---

global multi--rmed bandit task. With appropriate information sharing, the collective performance can match that of single-agent bandit problem with full access all rewards. Hence, achieving a global regret of the same order as the classical centralized bandit setting is both natural and optimal. The additional term related to the communication graph, though not captured in Theorem 5.9, can be interpreted intuitively. Consider, for instance, a circular base graph G: on average, it takes O rounds for information from one agent to propagate to all others, Aggregating over all N agents, this leads to an unavoidable lower bound of O(N /p) in the global regret. Providing formal lower bound proof that fully characterizes this effect remains an interesting direction for future work.
Experiments
In this section, we demonstrate the effectiveness of our algorithm through numerical experiments on both synthetic and real-world datasets." 3 The objective is twofold. First, we show that the cumulative regret of our algorithm grows logarithmically with respect to T and significantly smaller than that of existing benchmarks, thereby validating our theoretical findings. We use DrFed-UCB, proposed by [Xu and Klabjan, 2023], as the baseline. Second, we conduct a simulation study to examine how the regret depends on the link probability p and the algebraic connectivity of the base graph G, as reflected in the regret bound. We evaluate the impact of different values of p across various base graphs, including the complete graph, grid, and Petersen graph [Holton and Sheehan, 1993]. Each edge in the base graph & appears in the communication graph Ge with probability p. Moreover, we provide additional experiments (i.e., ablation study) in Appendix D, illustrating the regret dependency on the key parameters and (x=1(La)(G) that determine the problem complexity beyond T, to validate our theoretical findings.
Experimental Settings. For synthetic experiment setting, We set T' = 10000, N = 16, and K = 5; for the Petersen graph, we use N 10 by definition. For the comparison with DrFed-UCB, we consider a complete graph and high link probability (p- 0.9), as required therein. Before the game starts, we sample each qi independently and uniformly from the interval [0, 1] for each agent The k-1, and the global mean reward of K-I+
local mean reward of arm & on agent is given by p4,A = q:
K-1 Zienn %h At each time step f, each agent i E [M] selects an arm and observes arm k is μ4 K-T N the local reward. For real-world experiments, we use the MovieLen dataset and refer to Yi and Vojnovic [2023] for details. We the horizon T = 10,000, and select 20 users as agents (N = 20) and 5 genres as arms (K = 5). At each time step I, each agent randomly selects a movie from the genres. All ratings (rewards) of movies are normalised to [0, 1].
Experimental Results. All experiments are performed with 20 independent replications. The shaded areas consider a range centered around the mean with half-width corresponding to the empirical standard deviation over 20 repetitions. In Figures la and 1b, we observe that our algorithm consistently outperforms DrFed-UCB on both synthetic and real-world datasets. an initial exploration period, our algorithm eliminates significant number of suboptimal actions, resulting in ncar-constant regret thereafter. In Figures Ic and 1d, we observe that increasing the link probability p improves the algorithm's 's performance, clearly validating the regret- communicomiiinittionn trade-off. Additionally, different base graphs significantly impact the regret under the same p the complete graph yielding the lowest regret.
runs, after
7 Conclusion and Future Work
In this paper, we study the multi-agent multi-armed bandit (MA-MAB) problem under general Erdös-Rényi random networks with heterogeneous rewards. To the best of our knowledge, we are the first to formulate MA-MAB with Erdōs-Rényl random networks, where the communication graph induced by a base graph and each edge in the base graph appears the communication graph with probability p. This formulation generalizes the classical Erdōs Erdös-Rényi model, in which the base graph is complete. We propose an algorithmic framework that incorporates the gossip communication protocol into arm elimination. Importantly, we analyze the regret bound of the algorithm and show that it improves the regret even under the classical Erdōs-Rényi model. Moreover, our regret bound
The code for the experiments is available at https://ittabb.com/acqog///////p
bandit.

---

500
Drfec-UCB
400
Drfed-UCB
400
Regret
Regret
100
2000
4000
6000
8000
10000
2000
4000
6000
8000
10000
(a) Synthetic data
(b) Real- wooldw data
800
graph PETERSEN graph
Complete graph
1000
graph PETERSEN graph
Complete graph
700
Regret
Regret
500
600
400
200
200
100
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
(c) Syathetic data
(d) Real-world data
Figure 1: Top two: comparison of the empirical results of our algorithm and DrFed-UCB (complete base graph, link probability p 0.9). Bottom two: regret of our algorithm on different base graphs as varies.
holds for any p, explicitly characterizes its dependency on and the algebraic connectivity of the base graph. This naturally reveals trade-off between regret and communication efficiency. Moving forward, while we focus extensively on the stochastic setting, it would be valuable and exciting explore other reward models- non-stationary contexts. In addition, achieving the optimal trade-off among regret, communication. and privacy, as previously studied in homogeneous MA-MAB settings, points out meaningful direction for future research.
contextual bandits, where rewards depend dynamic,
Acknowledgments and Disclosure of Funding
Hao Qiu acknowledges the financial support from the EU Horizon CL4- and innovation action under grant agreement 101 120237, project ELIAS (European Lighthouse of AI Sustainability) and from the One Health Action Hub, University Task Force for the resilience of territorial ecosystems, funded by Università degli Studi di Milano (PSR 2021 1221-GSA-iine 6).
research
10

---

References
Juliette Achddou, Nicolò Cesa- Biaa-Bianchi, and Hao Qiu. Distributed online optimization with stochastic agent availability. arXiv preprint arXiv:2411. 2024.
Mridul Agarwal, Vaneet Aggarwal, and Kamyar Azizzadenesheli. Multi-agent multi-armed bandits with limited communication. The Journal of Machine Learning Research, 23(1):9529-955) 99522, 2022.
Peter Auer, Nicolo Cesa- Desa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47:235-256. 2002.
Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip algorithms. IEEE transactions information theory, 52(6):2508-22 2530, 2006.
Ronshee Chawla, Abishek Sankararaman, Ayalvadi Ganesh, and Sanjay Shakkottai. The gossip- ing insert- insert-eliminate algorithm for multi-agent bandits. In International conference on artificial intelligence and statistics, pages 3471 -3481. PMLR, 2020.
John C Duchi, Alekh Agarwal, and Martin J Wainwright. Dual averaging for distributed optimization: Convergence analysis and network scaling. IEEE Transactions on Automatic control, 57(3): 592-606, 2011.
Paul Erdos, Alfréd Rényi, et al. On the evolution of random graphs. Publ. math. inst. hung. acad. sci, 5(1):17-60, 1960.
Eyal Even-Dar, Shie Mannor, Yishay Mansour, and Sridhar Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of machine learning research, 7(6), 2006.
Deepak Ganesan, Alberto Cerpa, Wei Ye, Yan Yu, Jerry Zhao, and Deborah Estrin. Networking issues in wireless sensor networks. Journal of parallel and distributed computing, 64(7):799-8)) -14, 2004.
Saeed Ghoorchian and Setarch Maghsudi. Multi-armed bandit for energy-efficient and delay-sensitive edge computing in dynamic networks with uncertainty. IEEE Transactions on Cognitive Commu- nications and Networking, 7(1):279-292) 293999299.990 2020.
Derek Allan Holton and John Sheehan. The petersen graph, volume Cambridge University Press, 1993.
Saghar Hosseini, Airlie Chapman, and Mehran Meshahi. Online distributed optimization via dual averaging. In 52nd IEEE Conference on Decision and Control, pages 1484-1489, IEEE, 2013.
Peter Landgren, Vaibhav Srivastava, and Naomi Ehrich Leonard. Distributed cooperative decision- making in multiarmed bandits: Frequentist and bayesian algorithms. In 2016 IEEE 55th Conference on Decision and Control (CDC), pages 167-172. IEEE, 2016a.
Peter Landgren, Vaibhav Srivastava, and Naomi Ehrich Leonard. On distributed cooperative decision- making multiarmed bandits. In 2016 European Control Conference (ECC), pages 243-248. IEEE, 2016b.
Jinlong Lei, Peng Yi, Yiguang Hong, Jie Chen, and Guodong Shi. Online convex optimization over erdos-rényi random networks. Advances in neural information processing systems, 33: 15591-15601, 2020.
Xiuxian Li, Lihua Xie, and Na Li. A survey on distributed online optimization and online games. Annual Reviews in Control, 56:100904, 2023.
David Martinez-Rubic Varun Kanade, and Patrick Rebeschini. Decentralized cooperative stochastic bandits. Advances in Neural Information Processing Systems, 32, 2019.
David Mateos-Nánez and Jorge Cortés. Distributed online convex optimization over jointly connected digraphs. IEEE Transactions Network Science and Engineering, 1(1):23-37, 2014.
11

---

Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication-effee learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pages 1273-1282. PMLR, 2017.
Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 54(1):48-66 61, 2009.
Abishek Sankararaman, Ayalvadi Ganesh, and Sanjay Shakkottai. Social learning in multi agent multi armed bandits. Proceedings of the ACM on Measurement and Analysis of Computing Systems, (3):1-35, 2019.
Po-An Wang, Alexandre Proutiere, Kaito Ariu, Yassir Jedra, and Alessio Russo. Optimal algorithms for multiplayer multi-armed bandits. In International Conference on Artificial Intelligence and Statistics, pages
PMLR, 2020.
Xiong Wang, Jiancheng Ye, and John CS Lui. Decentralized task offloading in edge computing: A multi-user multi-armed bandit approach. In IEEE INFOCOM 2022-IEEE Conference on Computer Communications, pages 199-12008 IEEE, 2022a.
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 Kleventh International Conference Learning Representations, 2022b.
Lin Xiao and Stephen Boyd. Fast linear iterations for distributed averaging. Systems & Control Letters. 53(1)65--7, 2004.
Mengfan Xu and Diego Klabjan. Decentralized randomly distributed multi- multi-armed bandit with heterogeneous rewards. Advances in Neural Information Processing Systems, 36: 74799-748555 2023.
Mengfan Xu and Diego Klabjan. Multi-agent multi-armed bandit regret complexity and optimality. In The 28th International Conference Artificial Intelligence and Statistics, 2025.
Feng Yan, Shreyas Sundaram, SVN Vishwanathan, and Yuan Qi. Distributed autonomous online learning: Regrets and intrinsic and Data Engineering, 25(1 2)23323224 2013.
properties. IEEE Transactions on Knowledge
Mang Ye, Xiuwen Fang, Bo Du, Pong C Yuen, and Dacheng Tao. Heterogeneous federated learning: State-of- oottth-rrtttttttoo and research challenges. ACM Computing Surveys, 56(3):1-44, 2023.
Jialin Yi and Milan Vojnovic. Doubly adversarial federated bandits. In International Conference on Machine Learning, pages 39951-39967. PMIRR 2023.
Deming Yuan, Alexandre Proutiere, Guodong Shi, et al. Multi-agent online optimization. Foundations and Trends@ in Optimization, ((2-3):81-663 2024.
Jiang Zhu, Yonghui Song, Dingde Jiang, and Houbing Song. Multi-armed bandit channel access scheme with cognitive radio technology in wireless sensor networks for the internet of things. IEEE access, 0:4609-4617, 2016.
Jingxuan Zhu and Ji Liu. Distributed multiarmed bandits. IEEE Transactions on Automatic Control, (8(5):3025-3044 2023.
Jingxuan Zhu, Romeil Sandhu, and Ji Liu. A distributed algorithm for sequential decision making in multi-armed bandit with homogeneous rewards. In 2020 59th IEEE Conference on Decision and Control (CDC), pages 3078-3083, IEEE, 2020.
Jingxuan Zhu, Ethan Mulle, Christopher S Smith, Alec Koppel. and Ji Liu. Decentralized upper con- fidence bound algorithms for homogencous multi-agent multi-armed bandits. IEEE Transactions Automatic Control, 2025.
Zhaowei Zhu, Jingxuan Zhu, Ji Liu, and Yang Liu. Federated bandit: A gossiping approach. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 5(1):1-29, 2021.
12

---

A Auxiliary results
In this section, show several auxiliary lemmas that will be helpful throughout the paper. The following lemma the concentration bound for the estimation of the observed expected rewards, Lemma A.1. Let (t) be the observed empirical average of the expected reward up to the end of round L. Then,
2 log T
IP
(ea((() Mackl
V
T
I
7
for E [N], & [K] and E [2] holds.
Proof of Lemma A.I. This lemma follows immediately from Hoeffding's inequality and a union bound.
The following lemma the concentration bound for the estimation of the observed expected rewards. Lemma A.2. Let (t) be the observed empirical average of the expected reward for agent pulling arm Then,
P
Σ
Σ
M4.
(T, S
4N 4N T
2 T
E
NE[N]
holds for any i E [N], [K] and t E [2].
Proof of Lemma A.2. We sample (1) number of random variables iid from P., for each i [N], each taking values in [0, 1], and hence X1,((T) Miik is 1-subgaussian for each T.
According to the property of subgaussian variables, can obtain that
1/2
Σ
(Ti, - -bC,k)
Σ iE[N
-uugauussan..
Tt,x(t)
iE|M]
N Moreover, note that EIEINT T:,(1)) S mintein (1)
1
then by applying Chernoff's bound, we have
(-
2 min (Ti, (1))
P
Σ
(t) Pi, 26
< 2xxp
2.N
iEIN
Taking
4N T
we obtain that
min:c[N] (OTT
4N log' 2
IP
Σ (1) KE[N]
p4i. 2
mingett (Tc.((t)
72
which ends the proof of Lemma A.1
We provide lemmas for the convergence bound of randomised gossip algorithms. Similar proof could be found Lei et al. [2020), Achddou et al. [2024].
Lemma A.3 (Random Graph). Let us assume that the communication graph follows Assumption 3.1. For t = 1... T, W. is doubly stochastic matrix and symmetric and i.i.d. Then Vu E V. Vs, t [T] such that > s,
W ..... Wotie, 1
>2 22
IP
82
2
When 1
3 log (7)
r', we have
log (E
P W. W Ws+1ey
8
<
(10)
Furthermore, when xx =
aN Iog(T)
T'_ Equation (10) still holds.
pAN-1 (Lap(())
13

---

Proof. Using Markov's inequality we have
P ([Iw.... W 1I co
E
W
Wot1es x1112)
26)
N
2
Let W/ Wi 111 and assume
k-s-1
1 N
E
W ... Wot1e
S e ev
11
for some lt - 1>>6
N
Let FR-1 be the o-algebra generated by all random events up to time K - 1. We have that
B
Wx W. 11
1 N
R
WI
W. W- W Wstie WT
W W.W,BWW We F
W W11
E
EEW, WiJWa (by independence of W&)
W Ws+1e,
k-8-1
< B|WWWTT)
e 11
B[WW
N
N
op
B[W
11 T
N
op
which by induction, suffices to prove the lemma. Moreover, the proof of T* 2 r' follows from the fact that
(z(E) < pAN-1(Lapf and 1
S p
1og2z
1- A2
N
log(1 p)
where the second inequality is taken from Theorem 6.1 in Achddou al. [2024].
The following lemmas guarantee local consistency between agents.
Lemma A.4. Let assume that the communication graph follows Assumption 3.1. Then with probability N2T5, Algorithum guarantees that for fixed arm E [K], and for every i, E [N] for every t [2]]
[Ti,((t) (1) (N
where Lp(0)= =
Tog(1-p) denotes the maximum number of rounds each edge within base graph G connected the communication graph G. with probability 8.
log(d)
Proof. Fix an agent [N] and time step t [T]. According to Assumption 3.1 and Algorithm be the probability that agent i communicates with fixed neighbour j E .N,(t) in any given step, independently of the past. For non-negative integer T., we have
(i does not contact j during the next T. + steps) = (1 - p) 1+1
The communication gap length at time f is the number of steps starting from time until agent next successfully communicates with agent j. Choose confidence parameter 8 (0, 1), we have
IP (time until first contact between agents and j exceeds (5)) < 6.
Applying a union bound to gives IP (3i e [N],j E Nr, e [T] time until first contact between i and j after time exceeds (5))
< 2288.
14

---

Note that we have (t) C N, where N₁ is fixed superset of possible neighbors. Hence with probability least 1 2266, for every agent E [AV] every time step E [T]. and every neighbor j E M,, the time until the next communication between i and is at most (6) time steps.
For any two agents i and j. let d(i, < N denote the shortest path length between and j in the base graph G. Because with high probability, information can gossip across each edge within at most (6) steps, it follows that information originating at at time step reaches j at most by time step
t + (o) d(i,j) S Lp( N.
(11)
In order to be cautious for notations, we use (,) to denote the active set in round for Algorithm 1. According to Algorithm 1, during every communication, each agent replaces its active set by the intersection with its neighbors:
+ (ENG(())U(S)
S,(t).
because for all (0) [K], at most K distinct arms can wave of disagreement. Each wave of disagreement at most last (5) NN. In the worst case, the waves do not overlap. Consenquently the longest possible sequence of rounds in which S((() o (,) is K N Lp()). During the disagreement period, for fixed arm i we could upper bound of maximum pull of (p)) and lower bound of maximum pull of is Hence we have
removed. Each arm can new
(t) (t)( S KNL (
B Omitted details in Section 5
In this section, we show the omitted details in Section 5.
Proof of Lemma 5.1. When (t) S KL', the bound trivially holds.
Now we consider the case when Ti, (1) KL*, We first define the following event:
EsEI (7),)(() M)ja)
4 llg((T) N minje(N] {TH, (t)
E
kE[K]
tE[2]]
11 2
1
W W Ws+ie,
-Tx(()-T55(0) - T3x((1) S KI
T2
JE[N]
iJEiN
St-aST
KEIK TE[T]
(12)
In Equation (12), the first event bounds the global estimation error for each arm, the second ensures near-uniform information mixing across agents after sufficient communication rounds, and the
third guarantees that the number of pulls for any remains approximately balanced across agents at each time step. By applying Lemma A.2, A.3, A.4 and union bound, we obtain that [E
+
3NK when we set x²T2 and I, NL (x²T=) N log (T) log(1 11))
We define Th (t) +
EJENT (t) be an intermediate variable that has access each agent's average mean on arm time I.
For any agent i, we have
(t) - -ual (t),((t) - Ti (t) + (t) - pul
[t)(t) (t) + 1i mm6
(Triangle incquality)
15

---

EjEIN (Pgalt) mg)N))
= (() 2
(13)
N
Consensus Error
Estimation Error
The last equality is due to the definition of the global mean reward and (t). Let us first focus on Consensus Error. For any E [N], According to the update in Equation (4) we have
(t,(()) = Σ
W.-1k
1) + Pi. - 1) Tta, - 2)
JE[N]
1-2
= Σ [ ... We- - -8)+
Σ
Σ
W ... Wrisks (Fgx(T) PT -1))
JE[N]
-=
+ Tei,eet 1) -p 2)
(14)
t-2
Σ [ Wilss + Σ
Σ
[K-2 -. Wlls (P) (T 1))
JE(N]
JEIN]
+ (t, 1) (t
(setting - 1)
We also have
(t) = N
Σ (t)
jE[N]
t-1
= Tūu(t 3) + N
Σ Σ (T)) - -ūg - 1))
-=
1 Σ Σ (Pa((T) PAu 1))
= -ix(1) +
(setting s = 1)
N
Σ
(1, + Σ
Σ (P))(T)) Rg 1))
N
JE(N]
JE(N)
1 f-2
Σ
(1,x (1) + Σ
Σ (P)))(T) - Rg 1))
N
JE[N]
[=(NE(N]
+ N
Σ (P),((t -2) 1) -ty - 2))
(15)
JE[N]
Hence, we obtain
2
1
-We-----Wrtllly ) (Pga(T)) PT (T))) 11)
(t) (t) =
Σ
Σ
N
JE[NI
1
Σ
(Mg,((1- - -oaull 2)) (7 - 1) - Te 2))
N
JE(N]
Σ
21,x(1) Σ HT-l...-WilassAAlle
JE[N]
JEIN
N -W Ws+1les) (P).((T) - PT, 1))
JE[N]
Σ
(Bg.ect 11 Po. 2)) (7 1) -t, - (2-))
N
JEIN]
16

---

Taking absolute values on both sides, we have
1
14x 22), -
Σ JEIN]
W W. (BAA(T)) -saaT P
N
Σ
(ūgu(t - -t 2)) - -Miialt - - -ti,a(t 2))
N
SE[M]
1Wi-2... .. Wr+slhs) ..aa...WWthh
(2gh(T) - PT - 1))
N
JE[N]
Σ
Σ
2 Wri1lis) (Rgaa(T) - (T -1))
N
JE(N
Σ
(ugatt- - 1) Pz - 2)) -(ii, - - Mt, 2)) (16)
N
JEIN
Now analyze three terms the right-hand side of Equation (16).
Bounding term V. Conditioning on event E, we obtain
2 .. Wo+tks) -2, 1))
N
jE(N]
W -
(rewards are bounded in the interval [0, 1)
N
JE[N]
1 111
Σ
Wi- Wo+10
N
t-r--2
SVN. Σ
Wi-2..-WH+le N
VN(t- -T)
72
VN
T
VN
(17)
where the third inequality comes from the condition that t - 7 1 E [7", t- - 3] and the event
Bounding term
We have
Σ
[W._1-...
Wr+slss) Di-1....WW+ikks
(D)M(T)- - -f,,()))))
N
r=
JEIN]
1-2
Σ
[We1 ... WsHilks)
N
JE(N]
17

---

HA,(s) = {) )
E HAj(s) = (s))
(definition of fr (f)
(T)
(T -
Σ
Σ
-W-1- V..-I-..WWHikkss))
JE(N]
[(A)(8) = k) ( + Xxx(T)
EE [(A((8) k) (1)2,166) ) Tyu(T)
TT,
Σ
Σ
N [W (W-.i-..W+++lkk))
-=--r--
JE[N]
[() = k) X (8) + (TiM(T) 1)xx
T3 (T) (T)x(T)-1)
+ 1W-11- ... Wot1l:s)
Σ
Σ
(T,(T) (rewards are bounded in the interval [0, 1))
f=1-T -1 [J[[
Σ
N WW-1 W Wo+1lss)
(event E)
max (TT,(T)) 1L
r=1-T
JE[N
47
max
- [Tr,(t-KKL,,) 1}'
where the second inequality follows from the fact that there only possible cases for (.x(T) and (7 - 1). When
1 1) the absolute difference of means is trivially 0, so the consider is when (T) TT 1) The last inequality is due that the upper bound of the total-variation distance from any distribution to the uniform distribution 1.
only non-trivial
Bounding term Conditioning E, obtain
(t - 1) (tj,,(tt-
- 2)) (fi, - - Pa,a(t 2))
N
JEIM
2
Σ JEIN]
NT, ( (1) (t
max (Ti, KL
Next, let us analyse Estimation Error. Conditioned on E, for all e [K] and f [T] we obtain
ΣSENN (Ty, M5,.))
4 4log(?)
N
N minje(N) (Tz,((1}
4 4lgg(7)
(18)
N max KL*
where the last inequality is due to the event
Combining all the results collected so far, we can finally derive the concentration bound conditioned on the event F. For any E [N] and & [K]. we obtain
4 (VN + +T*
4log(T)
1 (1) - pkll < V Max (Ti,(()) - KL*,1]
(19)
max (Tin(!) KL*,1)
18

---

Proof of Lemma 5.2. First, for all agents we consider the cases under the event E. According Algorithm 1, if arm & is eliminated, there are only two possible cases: 1) there exists some k' such that (1) + (La(l) < x1,
(1); 2) When Algorithm updates the active set St + 1) + (EAA S,(), x Sj for any E (1)...
For Case 1, Since we have (,,(() + Cs (1) S pa + 20,xx (1) as well as (1) - (1, 2 uu 20,x (1), then when
((c,x(t)) + C2 (t)) S pk
ps S As
arm Is will be essentially eliminated. Due to the pulling rule of Algorithm 1, have (T (t)
Ti (1) S 1. Thus when
(VN++*)
(T)g(T) ( N (T) KL
A 2
max (Ti KL*,1}
Hence, here we know that when
16 VN + 7*)
(1) (T)
KL",
NA
A
arm k will be essentially eliminated.
For Case 2,the optimal arm k- it cannot be eliminated, because for agents we consider the cases under the event E.
For all agents cases under event E have
T T-P(E") A max S 3KN A max.
Therefore, combining all inequalities above, we have
64 (64log(T) 16 (VN++)) KKL + 3.3AANAa
Reg.r (TT) <
Σ
NA
which ends the proof.
Proof of Theorem 5.3. By adding up Lemma 5.2 for all agents i E N, Theorem 5.3 can be proved through the facts that
1- (2 < pAv-1(Lap(G))
1 < p
N and
log25
log(1 p)
where the second inequality is taken from Theorem 6.1 in Achddou et al. [2024].
Proof of Corollary 5.4. If G is complete, then d(i.j) for all i.j A, and the gossip time simplifies to L + L. Recall Equation (11), with the same steps we can prove that
log(d)
(t) - (t)) & (L) = log( 1 p)
for any arm & E [K] and agents i,j E [N]] for any t [T].
Hence by the fact that A (w-1(Lap(g)) N and let L* as defined in Corollary 5,4 we can prove the case for complete graph.
For the rest two cases, we can just prove which by substituting the exact values of AN (Lap(()) in Theorem 5.3.
Proof of Theorem 5.9. First, note that
(eg)(())
Σ Reg) Σ
Σ
E[TT
Σ A E ET
iE[N]
VE[NI KE[K]
kE|K]
iE[N]
19

---

In order to show Theorem 5.9, we only need to prove that
ENENN] [(TT,((T)
2(1 - 8) (1 =)+
lim 7-+00
(20)
logT
for p and and some sub-optimal arm k **.
Suppose the distribution over instance is given by P (PM Consider another instance v' with P = =(P',a) (E(K) such that
Pi,. = [N(Mua: a
(N + (1 (1+E) =e)aa, 1), a=
for E [M] where Pi,a- = (P 1) and E (0, 1].
According to the consistency of policy æ,, it holds that
(T) + Rege ( - 2CT
for some constant C' and 10,
Simultaneously, event A; = (T) 2 T1. then
Reg (T) + Reg", v/' (T)
>
As P [Ai] +
2 E Dp. [A
2
T
A (Pu [A:] + Pur, (A
T
e
D
exp (-KL(1,
e exp
Σ
B[TT,o(T) (L P pjaa)
4
JEIM
T expexp
(1+
Σ
(T)]
2
JE[M]
Hence, summing the above inequality for all agents i [N]. we obtain
NT E exp
(T)] (1 +)+
Regi (T) + Regi (T)
2
Σ
(21)
4
2
JEIN
Rearranging the terms in Equation (21), holds that
Σ (T)] (1 c) log Regi + Reg (T))
NTaA:/4
JEIN]
NTeAR
NeA
> log
=(1 log(T) + log
SCT's
8C'
Therefore, we can show
Σ E[T,,(
2(1 -
lim T-000
log T
+1+
which is the goal in Equation (20).
C
Estimation of unknown link probability
Since G is connected, each agent has at least one neighbor. This allows every agent to estimate the edge activation probability p by observing its connectivity status over multiple rounds. We design the following procedure for each agent i [N] to compute estimate of
20

---

Algorithm 2 Burn-in Phase for Estimating p by Agent i [N]
1: Input: Confidence level
(0, 1), any fixed neighhor n, [N] of agent in the base graph
2: Initialization: Set F2 f 0, t < 0, p.(0) < 0 and (0) + 00
while p.(t) (t), < 0 do
4: Increment time & + t + and observe (t(
5: if n; E (t) then
6: F; 4- +
7: end if
8: Select an arm uniformly at random
9: Update (t( and CI2()) V (2g(2/))
end while
11:
Output: p; = p= (t.
Lemma C.1. For the agent and each 1, it holds that
(lé:(() pl S CI((1) 2 - 8.
Proof of Lemma C.I. Lemma C.1 comes directly from Hoeffding's 's inequality.
Theorem C.2. Let 2. Then, with probability at least -
2N
T. the estimate Ps returned by
T..- Algorithm satisfies P4 (p.p) for every agent i [N] Furthermore, the cumulative regret incurred during the burn-in phase across all agents is bounded by O N Nlog
p
Proof of Theorem C.2. Suppose the end round for Algorithm 2 is t" As p. p,( Ct,()) sp according to Lemma C.1, we only need to show i.: 2.
D. This can be verified by
P. = (t( - -1,)) (1(1) (L,()
P
2
2
By combining each E [T] and E [A] and union bound, we can obtain the first part Theorem C.2.
Moreover, for t* > 16 (o)) we have
g²
(t) 3CI, 2-1))pp-000 4CL(t) = p -P-41 log T
0,
hence the stopping condition in Algorithm 2 holds. By the fact that Amax S 1 for all arms, we can obtain the second part of Theorem C.2 through adding the regret for all agents E [N].
D Additional experiments
To further validate the dependence of the regret on the link probability p and algebraic connectivity ) we run the following additional experiments.
Experiment on Link Probability p. We conduct additional experiments complete base graphs with E [0.04, 0.18). and report the log-log relationship between and the resulting regret. The results are shown in Figure 2. By performing linear regression between log(p) and log (eggret, we obtain a slope & -0.93 with 1i2 1.0, indicating a nearly perfect linear fit (of order माकक )
Surprisingly, we also report the R² corresponding to the curve of fit n and find out that R² is 0.995, which represents that the curve fit quite statistically significant and thus perfect linear fit. This strongly supports the inverse proportionality between regret and p. i.e., regret scales approximately as O(1/p), which consistent with our theoretical upper bound. This result empirically also validates that p leads to significantly higher regret due to slower information diffusion across agents.
21

---

Log-log data and linear fits
Fit (slope free): A'=1.000
7.4
Fit y= =*=0.995
Data (log p. log Regret)
7.2
7.0
log/Regrel)
6.8
-3.2
-3.0
-2.8
-2.6
-2,4
-2.2
-2.0
-1.8
-1
Iaglp)
Figure 2: Log-log data for GSE: log(p) and (Regre)) with classical ER graph, p = 0.9)
Experiment Algebraic Connectivity \x-r(Ta)())). We conduct experiments using d-regular graphs with varying degrees d. Specifically, we construct the base graphs as circulant graphs. This structure provides controllable family of regular graphs with increasing algebraic connectivity grows. We run our algorithm GSE under this setting with the link probability p = 0.9. Table shows a clear inverse relationship: A (Lap(g)) increases with higher the regret decreases significantly. This supports our theoretical findings that larger algebra connectivity leads to more efficient information propagation and thus lower regret.
Table Average regret of GSE with d-regular graph
d-regular graph
6
8
10
12
14
AG)
0.1716 751.28
1.39
1.97
3.97
6.73
10.15
14.00
Regret
255.52
165.66
133.92
121.93
115.12
112.47
E Notations
The following notation chart provide notation used throughout the paper.
22

---

N
Number of agents.
T
Number of time steps.
K
Number of actions.
W,
Gossip matrix.
d1 A........ AN
Eigenvalues of P sorted by norm, i.c. |All
>
M2
>
1a
... AN|. It
is always ग 1 [A2].
Ji,k
global mean reward of arm k on agent i.
Pkk
global mean reward of arm k. Reward gaps, i.e. /41 14.
A
p
the link probability p of the Random graph
9 = (V,E)
base graph.
G. (V,&,)
Communication network at time t.
N;
the neighbors of agent in the base graph G
Ni(t)
the neighbors of agent in the communication network time
(t,(())
Number times arm & is pulled by node up to time t.
Xaa(t)
Local reward of arm & on agent i at time step t.
(1)
Local estimate of Pi,k agent at time step
(t)
Global estimate of P4 on agent i at time step t.
A,(1)
Action played by agent i at time t.
23

---

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: In Abstract have stated our main contributions and scope. Moreover, in Section we provide further details of our contributions.
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 are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss several limitations of the work in Section
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]

---

Justification:
We have stated every necessary assumptions before each theorem and lemma in the work. Detail proofs can be found in Appendix and
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 the statement of any theorems.
The proofs 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 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 be 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 it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide all the information for reproducing the results of the paper in Section 6.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a 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 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 a specific model and empirical evaluation, it may be necessary either make it 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 appropriate to the research performed.
While NeurlPS 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) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) 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 describe 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., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
25

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide open access the data and code used in this paper in the supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm aablic/guides/Codeee
wwwassooooliii imPolicy) for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is 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 NeurlPS code and data submission guidelines (https: / /ttpp.ccpppblliiipppp wwtpcccpppcc/ccccccccccccccccclt wwtpcc//g///eeieeeeeeeeeeeeeee
seabbmmmsssooPae ssiiisolicyyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. 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 as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is 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: [Yes]
Justification: Details for our experiments are given in both Section 6 and our supplementary materials.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core 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, appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Although the error bars in our paper are very small, the figures within our paper still include which.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
26

---

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, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
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 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: [No]
Justification: Our experiments can be run just on laptop, and thus our paper do not include any further information on computer resources.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as 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 fidn't make it 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 /ttps://neurrie http://uuurrpp.ccpuup.pttee cc/public/ httppppllttttiiaiiiiiiepp (thhicsuuidelieee""
Answer: [Yes]
Justification: respect.
We believe that our paper correspond the NeurIPS Code of Ethics in every
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is 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: Since this is work focusing on machine learning theory, we do not have any societal impact.
Guidelines:
27

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymentt 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to 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 to 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 intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how 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: As this is a theory work, we do not have data or models that have high risk for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a 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 not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or 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:
As this is a machine learning theory work, we do not use any 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 or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
28

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com conddatasess 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 it has changed) should be provided.
If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Since our work focuses machine learning theory, we do not provide any new asset.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of 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 an 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: As this is theory work, we do 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.
15. 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 institution) were obtained?
Answer: [NA]
Justification: As this a machine learning theory work, we do not involve crowdsourcing nor research with human subjects.
Guidelines:

---

The answer NA means that the paper does not involve crowdsoureing 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 expect authors adhere 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
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does involve LLMs as any crucial components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to LLM policy (https: : wtwpe//pp.../oooeeeeeeeeeeeeeeee ccc/ooofeeenee///0000 /LLM) for what should or should not be described.
30


Reviews:
[{"review_id": "VSnK0sRUcH", "reviewer": "Reviewer_bG2e", "summary": "This paper studies the heterogeneous multi-agent bandit setting, where the goal of each bandit is to minimize regret with respect to the globally best arm. The agents are assumed to exist on a fixed graph $\\mathcal{G}$, and communicate with neighbors with probability $p$.\n\nThe authors propose an arm elimination algorithm that uses gossip to reach a consensus. The paper provides an upper bound on the regret of the algorithm, $\\mathcal{O}\\left(\\sum_{k:\\Delta_k>0}\\Delta_k^{-1}\\log(T)+p^{-1}\\lambda^{-1}N^2\\log(T)+p^{-1}N^2\\log(T)\\right)$, where $\\lambda$ is the spectral graph of the graph $\\mathcal{G}$, that neatly decomposes into a centralized regret bound and a consensus/decentralization term. \n\nThe authors provide a lower bound for the centralized regret that matches their upper bound. Lastly, experiments to demonstrate the algorithm are conducted.", "questions": "1. How tight is the consensus/gossip upper bound? Would it be possible to come up with a lower bound that includes the communication cost for some specific graph, like a tree or a cycle?\n\n2. In Lemma B.4, is the $K$ in the upper bound necessary? The \"waves\" for each of the arms should happen in \"parallel\", which should render the argument in lines 512 to 515 unnecessary.\n\n3. How is the second equality in equation (14) (line 531-532, the equality after the definition) obtained?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1. The authors provide a stronger regret bound compared to many papers analyzing similar settings. Previous works have obtained regret bounds such as $\\mathcal{O}\\left(\\sum_{k:\\Delta_k>0} \\Delta_k^{-1}N\\log(T)\\right)$ in [1]. The algorithm presented in this paper has a superior bound of $\\mathcal{O}\\left(\\sum_{k:\\Delta_k>0} \\Delta_k^{-1}\\log(T) + KN\\log(T)\\right)$.\n\n2. The algorithm is simpler than many similar algorithms and uses fewer hyperparameters. Previous algorithms require a burn-in time $L$, with $L$ being a complicated function of other hyperparameters. These algorithms also require $p>1/2$. Furthermore, the gossip mechanism is simplified with each bandit maintaining a local record of the values of the arms, which is communicated over the graph. \n\n3. Previous works do not capture the consensus/communication term of the regret as neatly as the regret bound presented. In [1], the communication cost is largely captured by the burn-in period $L$, which does not depend directly on the graph structure.\n\n[1] Xu, Mengfan, and Diego Klabjan. \"Decentralized randomly distributed multi-agent multi-armed bandit with heterogeneous rewards.\" Advances in Neural Information Processing Systems 36 (2023): 74799-74855.\n\nWeaknesses:\n\nThe motivation for seeking global optimality rather than local is lacking. It would be best to include a statement, i.e., that the local bandits might have biases, to clarify this.\n\nThe experiments are lacking. In particular:\n\n1. There should be more experiments with varied time horizons $T$, with comparisons to the upper bound. Specifically, Figure $1$ records the running regret given a fixed horizon $T$. Another graph showing the terminal regret for different horizons $T$ may better capture the dependence of the regret on $T$.\n\n2. Figure 2 would benefit from more data points, particularly with $p$ close to $0$. Figure $2$ may also benefit from a log-scale, and linear fits to verify the $p^{-1}$ relation of the regret.\n\n3. The experiments do not sufficiently capture the dependence on the spectral gaps of the base graph. A graph of the regret v/s the spectral gaps for a family of graphs, e.g., expander graphs, might be useful to verify the dependence on the graph structure.\n\nFurther, the conclusion and future work section of the paper has been included in the appendix rather than the main body.", "was_revised": true, "final_justification": "The authors have addressed my questions. Thus I am increasing my score.", "rebuttal": "Thank you for your feedback and hope our responses address your concerns. If this is the case, we would appreciate it if you can reconsider your score.\n\n**Q1:** Position of the conclusion and future work\n\n**A1:** Thank you for pointing that out. We will reorganize the paper and move the conclusion and future work section to the main body as the final section in the revised version.  \n\n**Q2:** Motivation of global optimality.\n\n**A2:** Thank you for this suggestion. In many real‐world applications, global rather than local optimality is the true objective. For instance, a company with multiple branches may face region‐specific demands: a policy that maximizes one branch’s profit could inadvertently harm others. To avoid such \"local bias\", each branch must choose a policy that maximizes the **aggregate** reward across all branches.\n\nMotivated by the real-world applications, we model this problem as $N$ agents seeking to maximise the **global reward**, as the sum of each agent’s expected reward. If each agent only optimizes its own local bandit, these local biases can cause the global regret to grow linearly in $T$ (as illustrated in [1], where linear regret is shown to be unavoidable if the graph is disconnected, preventing optimization toward global optimality). By contrast, our GSE algorithm is designed to minimise this global regret. As established in Lemma 5.2 and Theorem 5.3, both the per‐agent and total global regret under GSE converge at a logarithmic rate, demonstrating that GSE indeed achieves true global optimality rather than merely local gains.\n\n**Q3:** Additional experiments\n\n**A3:** Based on the suggestions, we conduct additional experiments as follows. For each experiment, we run the algorithm for 20 times and report the average performance. \n\n(i) To further investigate the regret’s dependence on the time horizon $T$, we report in Table 1 the final cumulative regret of GSE and DrFed-UCB across a range of $T$ values. The results show that GSE scales much more slowly with $T$ compared to DrFed-UCB, aligning with our theoretical tighter upper bound. This experiment confirms the favorable scaling behavior of GSE and supports the tightness of our regret analysis.\n\n*Table 1: Regret of GSE vs. DrFed-UCB for varying T with classical ER graph and p=0.9.* \n|Algorithms\\T|1000|2000|3000|4000|5000|6000|7000|8000|9000|10000|11000|12000|\n|------------|----:|----:|----:|----:|----:|----:|----:|----:|----:|-----:|-----:|-----:|\n|**GSE**|83.64|91.53|97.03|100.20|103.35|104.94|106.81|108.03|110.21|111.42|113.01|113.00|\n|**DrFed-UCB**|158.04|243.58|305.32|354.99|393.03|425.75|453.93|481.16|499.52|520.04|527.65|529.93|\n\n\n(ii) To better understand the dependence of the regret on the link probability \\(p\\), we conduct additional experiments on complete base graphs with small values of $p\\in[0.04, 0.18]$, and report the log–log relationship between $p$ and the resulting regret. The results are shown in the Table 2. By performing a linear regression between $\\log(p)$ and $\\log(\\text{Regret})$, we obtain a slope $\\hat\\alpha = -0.93$ with $R^2 = 1.0$, indicating a nearly perfect linear fit (of order $\\frac{1}{p^{0.93}}$). Surprisingly, we also report the $R^2$ corresponding to the curve of fit $\\frac{1}{p}$, and find out that $R^2$ is $0.995$, which represents that the curve fit is quite statistically significant and thus a perfect linear fit. This strongly supports the inverse proportionality between regret and $p$, i.e., regret scales approximately as $O(1/p)$, which is consistent with our theoretical upper bound. This result empirically also validates that smaller $p$ leads to significantly higher regret due to slower information diffusion across agents.\n\n*Table 2: Log–log data for GSE: $\\log(p)$ and $\\log(\\mathrm{Regret})$ with classical ER graph, p=0.9)*  \n|$p$|0.04|0.06|0.08|0.10|0.12|0.14|0.16|0.18|\n|---|----|----|----|----|----|----|----|----|\n|**$\\log(\\mathrm{Regret})$**|7.4019|7.0136|6.7405|6.5331|6.3653|6.2232|6.1045|6.0000|\n|**$\\log(p)$**|–3.2189|–2.8134|–2.5257|–2.3026|–2.1203|–1.9661|–1.8326|–1.7148|\n\n**Fit allowing slope free**  \n|Statistic|Value|\n|---------|-----|\n|Slope $\\hat\\alpha$|–0.93|\n|Intercept $b$|4.39|\n|$R^2$|1.00|\n\n**Fit with fixed slope = –1**  \n|Statistic|Value|\n|---------|-----|\n|Slope $\\hat\\alpha$ (fixed)|–1.00|\n|Intercept $b$|4.236|\n|$R^2$|0.995|\n\n\n(iii) To empirically investigate the dependence of regret on the spectral gap of the base graph, we conduct experiments using $d$-regular graphs with varying degrees $d$. Specifically, we construct the base graphs as circulant graphs. This structure provides a controllable family of regular graphs with increasing algebraic connectivity as $d$ grows. We run our algorithm GSE under this setting with the link probability $p = 0.9$. Table 3 shows a clear inverse relationship: as $\\lambda_{N-1}$ increases with higher $d$, the regret decreases significantly. This supports our theoretical findings that larger algebra connectivity leads to more efficient information propagation and thus lower regret.\n\n*Table 3: Average regret of GSE with d-regular graph*\n\n|d-regular graph|2|4|6|8|10|12|14|\n|---------------|--|--|--|--|--|--|--|\n|$\\lambda_{N-1}$|0.1716|1.39|1.97|3.97|6.73|10.15|14.00|\n|$\\mathrm{Regret}$|751.28|255.52|165.66|133.92|121.93|115.12|112.47|\n\n**Q4:** Regarding the tightness of bounds and possibility to include communication cost of graph in lower bound\n\n**A4:** Thank you for the insightful question. In our paper, we provide a theoretical regret upper bound in Theorem 5.3 and a corresponding lower bound in Theorem 5.9. The first term in the upper bound, which captures the centralized regret due to the statistical uncertainty from limited samples, matches the lower bound, indicating that this term is tight and optimal. The remaining two terms in the upper bound arise from delays in information propagation due to random communication, and these are not yet matched by a lower bound.\n\nTo gain intuition on the potential tightness of these communication-related terms, consider a simple cycle graph where each edge is activated independently with probability $p$ at each round. On average, it would take $O(N/p)$ rounds for information from one agent to reach all the other agents (can be viewed as reward delay in [3]). Since agents are optimizing for global rewards, one agent must wait to receive information from all others to make informed decisions. This implies that each agent may need $O(N/p)$ rounds to effectively optimize its local policy with respect to the global objective. Summing across all $N$ agents gives a global regret contribution of at least $O(N^2/p)$, which intuitively explains the dependency on $p$ and $N$ in the graph-dependent terms in our upper bound. This argument provides heuristic evidence for partial tightness of our bound with respect to communication regret.\n\nWe would also like to add that we make contributions toward narrowing the gap between the lower and upper bounds in existing work. Notably, our upper bound is smaller compared to [2]. More importantly, it also introduces a novel reflection of the communication graph through the presence of $\\frac{1}{p}$ in the upper bound. Empirically, Table 2 in A3 shows that the actual regret exhibits a dependency of $\\frac{1}{p}$, which numerically validates the near-tightness of our upper bound. On the other hand, our lower bound improves upon existing work [1] by explicitly incorporating the sub-optimality gap. We acknowledge that a formal lower bound capturing communication costs—especially for specific topologies such as trees or cycles—remains open and is an important direction for future work. \n\n**Q5:** Regarding the necessity of $K$ in Lemma B.4\n\n**A5:** \nWe thank the reviewer for this insightful comment. Indeed, under our round‐robin protocol, the “waves” for different arms proceed **in parallel**, so we can refine the disagreement‐length bound as follows.  At any time $t$, if $|\\mathcal S_i(t)|=m$, each wave lasts at most $\\left\\lceil \\frac{N L_p(\\delta)}{m} \\right\\rceil$ rounds for agent $i$. Since $|\\mathcal S_i(t)|$ decreases by at least one each time a wave completes, the total number of disagreement rounds is bounded by\n$\\sum_{m=1}^K  \\left\\lceil \\frac{N L_p(\\delta)}{m} \\right\\rceil=NL_p(\\delta)\\sum_{m=1}^K \\frac{1}{m} + O(K)\n=NL_p(\\delta)(H_K + O(1)),\n$\nwhere $H_K=\\sum_{m=1}^K 1/m=O(\\log K)$.  Consequently, the right‐hand side of Lemma B.4 can be improved toO(NL_p(\\delta)\\log K).$ We appreciate the suggestion and will incorporate this tighter bound and its detailed proof in the revised version of the paper. \n\n**Q6:** The derivation of Eq.(14) (line 531-532)\n\n**A6:** The second equality holds because of the definition of $z_{i, k}(t)$ and the doubly stochasticity of the matrix of $W_t$. \n\nReferences \n\n[1] Mengfan Xu, and Diego Klabjan. Multi-agent multi-armed bandit regret complexity and optimality.\nIn International Conference on Artificial Intelligence and Statistics, 2025.\n\n[2] Mengfan Xu, and Diego Klabjan.\nDecentralized randomly distributed multi-agent multi-armed bandit with heterogeneous rewards. Advances in Neural Information Processing Systems, 2023.\n\n[3] Tal Lancewicki, Shahar Segal, Tomer Koren, Yishay Mansour. Stochastic multi-armed bandits with unrestricted delay distributions. In International Conference on Machine Learning, 2021."}, {"review_id": "igr7zyZpFx", "reviewer": "Reviewer_nBgW", "summary": "This paper studies the problem of multi-agent multi-armed bandit. In particular, it accounts for a scenario where the rewards are heterogeneous across the $N$ agents and the communication graph is stochastic and sampled from an Erdos-Renyi model at every round.  The paper's main contribution is analyzing this setting, which generalizes the models that have been proposed in the literature so far: the authors propose an algorithm that achieves no-regret and highlight the components of the regret upper bound, that are interpretable; moreover, they provide a lower bound that proves that at least one component of the upper bound is tight. Finally, some experimental evaluations on both synthetic and real-world data are provided.", "questions": "Can the authors argue whether the upper bound is tight or not about the problem-dependent quantities?\n\nThis is a major point; if I missed some parts of the submission, and the authors can answer this positively, I would reconsider my score positively. However, note that this is not my only evaluation criterion, because I also think that the methodological contribution is not a breakthrough if compared to previous works in this literature.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n- The paper is overall well written, the narration can be followed without any trouble, and the message of the paper is clear.\n- The comparison with existing results is fair and highlights the additional difficulties of this setting. \n- The experimental campaign goes beyond the simple comparison with the competing algorithms and explores the links between the regret and the problem parameters.\n\nWeaknesses:\n\n- I don't like how the conclusions and future work are presented as an appendix. There are two cases: either this section is important (and I believe it is, as the future work is one of the most interesting parts of a paper) and you find a spot for that in the main paper; or this section is not crucial for the paper and you just avoid it. In both cases, having an appendix for this makes no sense in my opinion. This is not a major point, but I wanted to report it.\n\n- The regret-communication trade-off that appears in the regret upper bound does not appear in the lower bound, and thus there is no way to be sure that this trade-off actually exists and is not a byproduct of the regret analysis. **This is a major point**: the narration of the paper strongly depends on this \"instance-dependent\" type of guarantee, and the meaning of the problem parameters appearing in it. The authors provide a lower bound, which basically resorts to the standard MAB lower bound but does not explore the presence of $p$ or other graph-dependent quantities. There is some algorithmic contribution, but since the overall approach is based on existing families of algorithms, the technical contribution is what can make this paper accepted or not, in my opinion. \n\n- The methodological contribution is not a breakthrough if compared to previous works in this literature. The authors provide algorithmic routines to deal with the stochasticity of the graph and the heterogeneity of rewards simultaneously, but overall the main underlying ideas to tackle the MA-MAB problem have already been outlined in previous works.", "was_revised": true, "final_justification": "The authors' arguments about the actual existence of a trade-off in the regret lower bound convinced me. This paper is not a breakthrough, but there are some contributions which makes it pend slightly more towards accept rather than reject. I'm fine with either decision anyways.", "rebuttal": "**Q1:** Concerns about conclusion and future works.\n\n**A1:** Thank you for the suggestion. We will revise the paper by moving the conclusion and future work to the final section of the main body.\n\n**Q2:** Concerns about tightness of upper bound and regret-communication trade-off existence\n\n**A2:** We acknowledge that verifying the presence of graph-dependent terms in the lower bound is essential to substantiate the regret-communication trade-off emphasized in our upper bound analysis. While Theorem 5.3 presents an upper bound that includes terms dependent on graph properties such as the link probability $p$, the lower bound in Theorem 5.9 does not yet capture these dependencies. However, we argue that the trade-off is inherent to the problem and not merely an artifact of the analysis, and we make contributions towards this direction.\n\nTo support this claim, consider a cycle graph over $N$ agents, where each edge is activated independently with probability $p$. On average, it takes $O(N/p)$ rounds for information to propagate from one agent to reach all the other agents. Since our setting requires each agent to optimize with respect to global rewards, which depend on data from all agents, this information delay directly impacts the agent's ability to make optimal decisions. Therefore, each agent may suffer at least $O(N/p)$ regret, leading to a total global regret of at least $O(N^2/p)$. This suggests a fundamental dependence on $p$, even in the lower bound. Combined with the lower bound on the statistical noise term in Theorem 5.9, this observation highlights that the regret-communication trade-off should indeed exist. Intuitively, as $p$ decreases, it takes longer for information to diffuse across the network, resulting in larger regret. In the extreme case where $p$ approaches zero, inter-agent communication becomes virtually impossible, and no agent can optimize global performance, leading to linear regret. This aligns with the trade-off discussed in Remark 5.6: more frequent communication reduces regret, while sparse communication increases it.\n\nWe would also like to add that we make contributions toward narrowing the gap between the lower and upper bounds in existing work. Notably, our upper bound is smaller compared to [1]. More importantly, it also introduces a novel reflection of the communication graph through the presence of $\\frac{1}{p}$ in the upper bound. Surprisingly, our newly added experiment ((ii), Table 2 in A3 for Q3 raised by reviewer bG2e) shows that the actual regret exhibits a dependency of $\\frac{1}{p^{1}}$, which numerically validates the near-tightness of our upper bound. On the other hand, our lower bound improves upon existing work [4] by explicitly incorporating the sub-optimality gap.\n\nWe do sincerely agree that formally incorporating this communication-related dependency (e.g., via $p$ or $\\lambda_{N-1}(\\text{Lap}(\\mathcal{G}))$) into the lower bound remains an important open direction. We hope our work could inspire future work on how to close the gap between upper and lower bounds in terms of graph-dependent terms.\n\n**Q3:** Concerns about our methodological contribution\n\n**A3:** The core contribution of our work lies in studying the multi-agent bandit problem under a general random communication graph, where each edge is independently active with probability $p\\in(0,1]$. In contrast, prior works either assume strongly connected communication graphs at all times [2,3], or require the graph to be strongly connected with high probability at each round [1]. While [1] is the only work that explicitly incorporates the edge activation probability $p\\ge 1/2+1/2\\sqrt{1-(\\epsilon/{NT})^{2/(N-1)}}$,\nwhich requires $p$ to be significantly large—approaching $1$ as $N$ or $T$ grows—and yields a regret bound ($O\\left(\\sum_{k:\\Delta_k>0}\\Delta_k^{-1}\\log(T)+KN\\log(T)\\right)$ in [1]) that is worse than ours ($O\\left(\\sum_{k:\\Delta_k>0}\\Delta_k^{-1}N\\log(T)\\right)$ in ours) by a factor of $N$. \n\nIn our novel and more general setting, our proposed algorithm (GSE) introduces several key methodological innovations compared to prior work. These include a new algorithmic framework based on arm elimination, refined weight matrix for gossip, and a carefully designed confidence interval that accounts for both estimation and consensus errors. Each of these components is tailored to the challenges of heterogeneous MA-MAB with random communication and plays a critical role in achieving stronger theoretical guarantees under minimal connectivity assumptions. \n\n**Algorithmically, we introduce them as follows:**\n\n(i) Algorithm framework: From the perspective of algorithmic protocol, our method adopts a *arm elimination* framework, whereas prior works in this literature primarily rely on *UCB-style algorithms* [1,2,3]. While arm elimination is not new, it is particularly well-suited to the heterogeneous MA-MAB setting. In this setting, each agent only observes local rewards, while the goal is to minimize cumulative *global regret*. To ensure the global estimate—obtained via gossip averaging—is unbiased and not overly influenced by individual agents’ feedback, it is important that all agents pull *each arm a comparable number of times*. Arm elimination naturally enforces such balance, as shown in Lemma B.4, which bounds pull count differences across agents. In contrast, UCB-based gossip algorithms need to prioritize under-sampled arms, requiring complex detection mechanisms and making them harder to implement and analyze under heterogeneous feedback. Our approach provides a simpler and more robust solution tailored for this setting.\n\n(ii) Refined weight matrix: The design of the weight matrix $W_t$ is another key aspect of our algorithm’s novelty. As defined in Eq.(2), we construct $W_t$ using the Laplacian matrix, which ensures that the weight matrices are independent and identically distributed (i.i.d.) across rounds. This property is essential for satisfying the conditions in Lemma B.3, enabling us to rigorously show that information from different agents becomes sufficiently balanced over time. As a result, the local estimates $z_{i,k}(t)$ on each agent converge to the true global mean reward $\\mu_k$ as the number of rounds increases. \n\n(iii) Confidence interval design: Furthermore, we propose a *novel confidence interval* (Eq.~(4)) that captures both *estimation error* and *consensus error*, which is critical under the stochastic communication graph and heterogeneous reward model. Specifically, the estimation error term $\\sqrt\\frac{4\\log(T)}{N\\max(T\\_{i,k}(t)-KL^\\*,1)}$\naccounts for the statistical variance due to finite sampling, while the consensus error term $\\frac{4(\\sqrt{N}+\\tau^*)}{\\max(T_{i,k}(t)-KL^\\*,1)}$ reflects the additional approximation error incurred due to time-delayed information propagation through the gossip protocol under a random graph. To our knowledge, this is the first formulation of a confidence bound that explicitly captures this two-fold structure in the heterogeneous MA-MAB setting.\n\n**Analytically, we introduce the following contribution.**  \n\nMoreover, the analysis and theoretical results of our algorithm form a central—and arguably the most crucial—part of our contribution. In Theorem 5.3, we establish an upper bound on the global regret for the heterogeneous MA-MAB problem under random graph communication. The first term in the bound, $O\\left(\\sum_{k:\\Delta_k>0}\\frac{\\log T}{\\Delta_k} \\right)$, reflects the estimation error originating from limited samples and matches the theoretical lower bound in Theorem 5.9, confirming its optimality. The second and third terms, $O\\left( \\frac{N^2\\log T}{p\\lambda_{N-1}(\\text{Lap}(\\mathcal{G}))}+\\frac{KN^2\\log(NT)}{p} \\right)$, stem from consensus errors and reveal the regret’s dependence on key graph parameters, including connection probability $p$ and algebraic connectivity $\\lambda_{N-1}(\\text{Lap}(\\mathcal{G}))$. As the first work to consider MA-MAB with general random graphs where each edge appears independently with arbitrary probability $p \\in (0,1]$, we also provide the first regret bounds that explicitly reflect these structural dependencies. Remark 5.6 highlights the inherent trade-off between communication frequency and regret. As previously discussed, this trade-off is fundamental: for example, in a cycle graph with edge appearance probability $p$, information may require $O(N/p)$ rounds to propagate (similar philosophy as suggested by the reward delay in [6]). Since each agent must access global information to achieve optimality, this implies a fundamental regret lower bound of $O(N^2/p)$. Finally, as shown in Remark 5.5, our results generalize existing works as special cases (e.g., fixed or strongly connected graphs), underscoring the broad applicability of our framework.\n\nTogether, these innovations enable us to systematically address both reward heterogeneity and random graph communication—an unexplored combination in prior work.\n\n[1] Mengfan Xu, and Diego Klabjan.\nDecentralized randomly distributed multi-agent multi-armed bandit with heterogeneous rewards. Advances in Neural Information Processing Systems, 2023.\n\n\n[2] Zhaowei Zhu, Jingxuan Zhu, Ji Liu, and Yang Liu. Federated bandit: A gossiping approach. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 2021.\n\n[3] Jingxuan Zhu, and Ji Liu. Distributed multiarmed bandits. IEEE Transactions on Automatic Control, 2023.\n\n[4] Mengfan Xu, and Diego Klabjan. Multi-agent multi-armed bandit regret complexity and optimality. The 28th International Conference on Artificial Intelligence and Statistics, 2025.\n\n[5] David Martínez-Rubio, Varun Kanade, and Patrick Rebeschini. Decentralized cooperative stochastic bandits. Advances in Neural Information Processing Systems, 2019.\n\n[6] Tal Lancewicki, Shahar Segal, Tomer Koren, Yishay Mansour. Stochastic multi-armed bandits with unrestricted delay distributions. In International Conference on Machine Learning, 2021."}, {"review_id": "fAFaXdvBOp", "reviewer": "Reviewer_6FB3", "summary": "This paper studies a distributed multi-agent multi-armed bandit (MA-MAB) problem in a heterogeneous reward setting where agents communicate over time-varying random graphs derived from a fixed base graph via the Erdős–Rényi model. The authors propose a fully distributed algorithm that combines successive arm elimination with a gossip-based communication protocol, enabling agents to estimate global rewards despite potentially disconnected communication at each round. Theoretical analysis shows that the algorithm achieves a regret bound of order $O(\\log T)$, which is highly interpretable in terms of the graph properties and connectivity. The paper also establishes a matching lower bound up to constant factors, and provides empirical results validating the regret–communication trade-off and superiority over prior work.", "questions": "As noted earlier, my primary concerns relate to the level of novelty and the tightness of the proposed regret bounds.\n1. Could you clarify the main technical challenges in establishing the regret upper bounds in Lemma 5.2 and Theorem 5.3? In particular, what are the key obstacles in reducing the second and third terms in Theorem 5.3? Do you believe it is possible to improve these terms to at least match known bounds in the time-invariant, homogeneous setting [1]?\n2. Additionally, in Theorem 5.9, what distinguishes your proof of the regret lower bound from the arguments of a similar lower bound for the single-agent case in [1], which your approach seems to closely follow? Is there potential to strengthen the lower bound by incorporating graph-dependent terms, such as the communication probability $p$?\n3. For a revised version, I recommend moving the Conclusion and Future Work section into the main text, while optionally relocating part of the Related Work section to the appendix if space is limited.\n\n[1] Martínez-Rubio, David, Varun Kanade, and Patrick Rebeschini. \"Decentralized cooperative stochastic bandits.\" Advances in Neural Information Processing Systems 32 (2019).\\\n[2] Lattimore, Tor, and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n- **Quality:** The paper’s main claims are supported by rigorous and well-structured proofs, demonstrating a solid theoretical foundation. Additionally, the paper includes a basic experimental evaluation that demonstrates the superiority of the proposed method.\n- **Clarity:** The proposed algorithm is well-motivated and clearly explained, with intuitive justifications provided in the main text. The authors carefully analyze the theoretical results, offering meaningful comparisons with prior work. Finally, the effectiveness of the method is supported by a set of illustrative experimental evaluations.\n- **Significance:** This work advances the state-of-the-art by providing an algorithm with provable regret bounds that operates in a distributed and heterogeneous environment with more limited connectivity than considered in prior works [1,2]. Additionally, the regret bounds improve the state-of-the-art in a relaxed setting [1]. \n- **Originality:** Although the authors build on established techniques such as running-consensus-based estimation [3] and successive elimination-based implicit synchronization [4], they employ them in a novel manner in the random connectivity heterogeneous setting to achieve an algorithm with improved performance. \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- My main concern lies in the tightness of the proposed regret bounds. While the first term in the upper bound of Theorem 5.3 matches the lower bound and scales as $O(\\sum \\log T /\\Delta_k)$, the remaining terms—particularly $O(KN^2\\log T/p)$—dominate the overall regret (up to the reward gaps). This discrepancy is not adequately addressed in the proposed lower bound or in the accompanying discussion in Remark 5.10, leaving a notable gap between the upper and lower bounds. Furthermore, it appears that even in homogeneous settings with time-invariant graphs, the regret of the proposed algorithm still scales as $O(KN^2\\log T)$, which is significantly worse than the bounds achieved in prior work, such as [3]. That said, this limitation seems to be common in the literature, and as acknowledged in Remark 5.5, the authors’ results nonetheless represent a meaningful improvement over those in [1,2].\n- Given the aforementioned limitations, this work represents an incremental advancement in the state of the art for heterogeneous MAMAB under time-varying communication graphs. While it offers meaningful improvements, several known challenges in this setting remain unresolved.\n- The techniques employed in this work—such as successive elimination [4], running consensus estimation [3], and the lower bound proof strategy [5]—are based on established methods, which limits the overall novelty of the contribution.\n\nOther issues – \n- Implementing the proposed algorithm requires agents to have global knowledge of certain properties of the communication graph, such as the eigenvalues of its Laplacian. Although this assumption has been adopted in prior work [3], it remains unrealistic in many practical settings.\n- Although the edge communication probability $p$ can be estimated during a burn-in phase, this introduces an additional term in the regret upper bound—$O(N^2\\log T/p^2)$ (Theorem D.2)—which can be larger and further impacts the algorithm’s performance.\n- In the proposed algorithm, agents exchange their estimates of the global mean for each arm in every round, resulting in high communication overhead—linear in $T$—and complex message structures. Unfortunately, the communication cost is neither optimized nor analyzed at the bit level in this work.\n- The main text does not include proof outlines for Lemma 5.2 and Theorem 5.3. Given that this is primarily a theoretical contribution, providing such outlines is important for guiding readers through the core ideas of the analysis. I strongly recommend including them in a revised version of the paper.\n- The authors claim that the numerical experiments validate the theoretical regret scaling with problem complexity; however, Figure 2 only illustrates the general trend of regret as the communication probability $p$ and base graph connectivity vary. It does not empirically validate the precise dependence on these factors as specified in the regret upper bound of Theorem 5.3, which I suspect may be loose.\n- Additional proofreading would improve the paper. For example, in line 81 “the” should be removed, and the sentence in lines 190-191 has been stated before in the same paragraph. \n\n\n[1] Xu, Mengfan, and Diego Klabjan. \"Decentralized randomly distributed multi-agent multi-armed bandit with heterogeneous rewards.\" Advances in Neural Information Processing Systems 36 (2023): 74799-74855.\\\n[2] Zhu, Zhaowei, et al. \"Federated bandit: A gossiping approach.\" Proceedings of the ACM on Measurement and Analysis of Computing Systems 5.1 (2021): 1-29.\\\n[3] Martínez-Rubio, David, Varun Kanade, and Patrick Rebeschini. \"Decentralized cooperative stochastic bandits.\" Advances in Neural Information Processing Systems 32 (2019).\\\n[4] Yang, Lin, et al. \"Cooperative multi-agent bandits: Distributed algorithms with optimal individual regret and constant communication costs.\" arXiv preprint arXiv:2308.04314 (2023).\\\n[5] Lattimore, Tor, and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.", "was_revised": true, "final_justification": "My primary concerns were with the level of novelty in this work, and with the gaps between upper and lower bounds, and between the heterogeneous and homogeneous settings. These concerns have been partially addressed by a well-written rebuttal, which makes me more comfortable recommending this work for publication. Please see my response to the rebuttal below for more details.", "rebuttal": "Thanks for your positive feedback. We address your concerns as follows.\n\n**Q1:** Concerns about algorithm novelty\n\n**A1:** Reviewer nBgW raised a similar concern; please see Q3 and A3 in response to reviewer nBgW for a detailed explanation of algorithmic novelties and corresponding theoretical analysis.\n\n**Q2:** Concerns about knowledge of $\\lambda_{N-1}$\n\n**A2:** We appreciate the reviewer’s concern about algebraic connectivity $\\lambda_{N-1}$. Similar to prior work [2,3], our confidence bound requires knowledge of $\\lambda_{N-1}$. However, $\\lambda_{N-1}$ can be estimated in a fully decentralized manner (e.g. brief gossip-based power iteration [7]).\n\n**Q3:** Concerns about additional term on estimating $p$\n\n**A3:** We appreciate and agree that estimating $p$ without prior knowledge inevitably incurs extra regret. In future work, we plan to reduce this overhead by (1) improving the sample efficiency of the estimation phase, or (2) incorporating the estimated $p$ into decision making during exploitation instead of requiring the exact value.\n\n**Q4:** Concerns about the communication complexity\n\n**A4:** Thanks for highlighting this point. As discussed in Remark 5.6, the average communication complexity per agent in our setting is $O(p|\\mathcal{E}|T/N)$, where $p$ is the edge activation probability and $\\mathcal{E}$ is the edge set of the base graph with $|\\mathcal{E}| \\leq O(N^2)$. In contrast, [1] assumes a complete graph and incurs $O(pNT)$ communication. Notably, when $|\\mathcal{E}|=O(N)$, our complexity becomes $O(pT)$, independent of $N$, indicating better scalability. Exploring ways to further reduce communication—building on recent advances in cost-efficient protocols [5]—is an exciting future direction.\n\n**Q5:** Challenges in upper bounds in Lemma 5.2 and Theorem 5.3\n\n**A5:** Thanks for the question. The main technical challenge in establishing the regret bounds in Lemma 5.2 and Theorem 5.3 lies in the general communication model we consider. Unlike prior works that assume fixed or strongly connected graphs w.h.p., our setting allows each edge to appear independently with probability $p>0$, meaning the graph may be disconnected in many rounds. As a result, traditional confidence bounds—designed to handle sampling noise—are no longer sufficient, since error also arises from communication delays. The key challenge is thus to design a confidence interval that accounts for both statistical estimation and consensus error.\n\nTo this end, we introduce the confidence interval $c_{i,k}(t)$ in Eq.(4), which captures both estimation and consensus error. The regret bounds in Lemma 5.2 and Theorem 5.3 build upon Lemma 5.1, which guarantees convergence of each agent’s estimate $z_{i,k}(t)$ to the global mean $\\mu_k$ under this interval. The proof involves defining several high-probability events (Appendix C, Line 520) ensuring: (i) concentration of local estimates, (ii) sufficient mixing of information across agents to reach consensus, and (iii) balanced arm pulls for different agents. These allow us to decompose the error in $z_{i,k}(t)$ into estimation and consensus components (Eq.(12)), which are then bounded separately. We will incorporate the above explanation into the revised version of the paper.\n\n**Q6:** Tightness of regret bounds and obstacles in reducing upper bound \n\n**A6:** We acknowledge that there remains a gap between the theoretical upper and lower bounds in our current analysis. Specifically, while the first term in Theorem 5.3—which captures the centralized noise matches the lower bound in Theorem 5.9, the remaining terms in the upper bound depending on graph properties such as $p$ and $\\lambda_{N-1}$, are not yet matched by our lower bound. However, we would also like to add that we make contributions toward narrowing the gap between the lower and upper bounds in existing work. Notably, our upper bound is smaller by the order of $O(N)$ compared to that in [3] for the centralized regret term under their assumptions. More importantly, it also introduces a novel reflection of the communication graph through the presence of $1/p$ in the upper bound. Our newly added experiment (A3(ii), Table 2 in responses to reviewer bG2e) shows that the actual regret exhibits a dependency of $1/p^{0.93}$, which numerically validates the near-tightness of our upper bound. On the other hand, our lower bound improves upon existing work [1] by explicitly incorporating the sub-optimality gap.\n\nMoreover, we believe that the $O(N^2/p)$ term in the upper bound reflects a fundamental limitation due to communication delays and is unlikely to be avoided. Consider, for instance, a communication graph structured as a cycle, where each edge is connected independently with probability $p$ in each round. In such a scenario, it takes on average $O(N/p)$ rounds for information from one agent to reach all other agents (similar philosophy as suggested by the reward delay in [6]). Since each agent must collect information from all others to compute a globally optimal policy, this implies a minimum communication delay of $O(N/p)$ for each agent. Summing up across all $N$ agents, this suggests a lower bound of $O(N^2/p)$ on the global regret, indicating that the communication-induced term in Theorem 5.3 is intrinsic to the problem. While we have explored ideas for reducing the last two terms in Theorem 5.3 (e.g., potentially improving dependency on $K$ in the third term from $O(K)$ to $O(\\log K)$, as discussed in our reply to Reviewer bG2e), we still anticipate that any meaningful upper bound must involve a term of at least $O(N^2/p)$ to account for the global information aggregation delay. Closing this remaining gap and formally establishing a lower bound that includes $p$ and $\\lambda_{N-1}$ remains an important direction for future work.\n\n**Q7:** Possibility to improve the graph-dependent terms to match bounds in time-invariant, homogeneous setting\n\n**A7:** While there remains a gap between our regret bound in the time-invariant and homogeneous setting and the result in [2], we believe that this gap is not merely due to our analysis, but rather stems from a fundamental difference between the homogeneous and heterogeneous settings which results in the difference in the algorithm design.\n\nThe dependence on $N$ in our second and third terms is $O(N^2)$, while the corresponding dependence in Theorem 3.2 of [2] is only $O(N\\log N)$. As explained in A6, in the heterogeneous setting, each agent must collect information from *all* other agents to accurately estimate the global reward and make optimal decisions. This necessity leads to an inherent $O(N^2)$ communication delay (even in the time-invariant case when $p=1$). In contrast, in the homogeneous setting, agents share the same reward structure and do not necessarily need information from others, enabling a regret bound with only $O(N\\log N)$ dependence. This core difference fundamentally limits the possibility of matching the bounds in [2] within our heterogeneous setting. \n\nGiven this, we see potential to improve our bounds via algorithmic modifications for best-of-both-worlds performance—i.e., optimality in both heterogeneous and homogeneous settings. One idea is to detect reward consistency across agents and switch accordingly between heterogeneous and homogeneous algorithms, akin to prior work adapting to stochastic vs. adversarial regimes [4]. This may also reduce the $\\log T$ dependence in Theorem 5.3, as achieved in [2] for homogeneous setting. We leave this for future work.\n\n**Q8:** Distinctions between our lower bound and single-agent lower bound and the possibility to add graph-dependent terms in our lower bound\n\n**A8:**  Our proof extends beyond the single-agent case by directly targeting *global* regret across all $N$ agents. Unlike classical lower bounds that perturb one arm's mean for a single agent, we construct two instances $\\nu$ and $\\nu'$ that shift the mean of the same arm for all agents simultaneously (see lines 305–308), yielding a lower bound on $\\sum_{i=1}^N \\mathbb{E}[T_{i,k}(T)]$ and thus the global regret. This primarily establishes the tightness of the centralized term. That said, we acknowledge that the lower bound is not our main contribution. The key novelties lie in: 1) a *new setting* with generalized random graphs; 2) a *new algorithm* based on successive elimination with a novel confidence bound adapted to random gossip; and 3) an *upper-bound analysis* that explicitly captures graph parameters ($p$, $\\lambda_{N-1}$), removing the strong assumptions on $p$ in [3]. Still, our lower bound improves upon [1], and we agree that extending it to incorporate graph-dependent terms remains a challenging and important direction.\n\n**Q9:** Regarding the concerns about the placement of conclusion, future work and proofreading modifications\n\n**A9:** Thank you for the suggestions. We will move the conclusion and future work to the main body, proofread, and incorporate these changes in the revision.\n\nReferences\n\n[1] Mengfan Xu and Diego Klabjan. Multi-agent multi-armed bandit regret complexity and optimality. AISTATS, 2025.\n\n[2] David Martínez-Rubio, Varun Kanade, and Patrick Rebeschini. Decentralized cooperative stochastic bandits. NeurIPS, 2019.\n\n[3] Mengfan Xu and Diego Klabjan. Decentralized randomly distributed multi-agent multi-armed bandit with heterogeneous rewards. NeurIPS, 2023.\n\n[4] Bubeck, Sébastien, and Aleksandrs Slivkins. The best of both worlds: Stochastic and adversarial bandits. COLT, 2012.\n\n[5] Xuchuang Wang, Lin Yang, Yu-Zhen Janice Chen, Xutong Liu, Mohammad Hajiesmaili, Don Towsley, John C.S. Lui. Achieving near-optimal individual regret low communications in multi-agent bandits. ICLR, 2023.\n\n[6] Tal Lancewicki, Shahar Segal, Tomer Koren, Yishay Mansour. Stochastic multi-armed bandits with unrestricted delay distributions. ICML, 2021.\n\n[7] David Kempe, Alin Dobra, and Johannes Gehrke. Gossip‐based computation of aggregate information. FOCS, 2003."}, {"review_id": "cg9CJEE6Yx", "reviewer": "Reviewer_PxL7", "summary": "The authors consider a random graph setting where the nodes are agents each of whom can select several arms for rewards. The stochasticity in the graph drives whether the agents communicate with each other based on the existence of a sampled edge. They then use gossip based reward estimation algorithm for agents to get both a personal and a global idea of the rewards that the arms provide and then which arms to keep and which to do away with. For this stochastic and challenging setting, they first upper bound the agent-wise and global community expected regret, then they interpret those results based on the obtained expression terms, ultimately relating it to graph parameters of p and graph connectivity (using Laplace matrix of the base graph). They discuss some specific upper boundds on known graph structures as examples. Then they proceed with lower bound definition on such class of problems. For these assumptions they have a LB estimate that is again a reinterpreted term from the UB. Then their experiments follow to validate their the bounds on the algorithm used on this problem.", "questions": "1. Its mentioned in the experimental settings that regret graphs show confidence intervals too. But the plots (Figure 2) doesnt clearly illustrate the same. Can this be made clearer?\n2. Line 337 (...we sample each <> independently...) seems to have a missing term. Is it \"edge\"? \n3. In line 338, what is this new term $q_i$ used to define means? They dont seem to have a definition either above or in the appendix table symbology! Is this expected?\n4. In line 348 authors briefly discuss the algorithm's performance based on the rate at which agents discard their dominated arms. A graph on these dynamics, something like %arms discarded over total arms discarded along with the regret in a temporal phase, like in Figure 1 would be very informative, right? This could help clearly define for the agents' exploitation phase of farming rewards from the \"trusted\" arms!", "limitations": "1. A bit mild on the multi-agent side of problem formulation: getting information from agents, even ones you are neighbors with can be noisy/adversarial from the agents' perspective! Basically, assuming agents can always get a noiseless global estimate is a milder study on behalf of multi agent interaction. This enforces their \"distributed\" nature of their algorithm on a practical domain.\n2. While authors already clearly acknowledge their algorithm suffers from a tradeoff between regret minimization and communication cost reduction, they could probably benefit from analyzing the communication in a broadcasted sense that emerges from the connected components in the $\\mathcal{G}_t$, rather than a one-to-one communication between edges several times.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. Consideration of a practical yet less investigated problem in contemporary literature using random graphs with Multi-Arm Bandits for communication.\n2. Work translates to stricter bounds on simplified problems already studied in the literature.\n3. Actionable interpretation of the regret bound terms: global regret, $delta_k$, connectivity parameters $p$ and eigen values of the graph.\n4. A sound initiative to define minimum requirements on the class of problem and prepare a lower bound on the same.\n5. While the originality is not with the algorithm itself, its application to a defined problem and its performance bounds is novel. \n \nWeakness:\n1. A bit mild on the multi-agent side of problem formulation: getting information from agents, even ones you are neighbors with can be noisy/adversarial from the agents' perspective!\n2. In section 3 lines 146-166, authors could be upfront about why they define both local and global reward definitions and how would it be helpful in the algorithm later! Specifically, line 151 (However...) could be made more concrete. Specifically in 173-175 they define the global objective that the policy should optimize. But what is individual agent trying to optimize? Local estimate of sampled arms? Global estiamte of sampled arms? A combination of them with a confidence bound? This only gets concrete by 201-204 when the actual algorithm details appear. An equivalent of equation (1) for individual agents can be made more explicit, just as they did so for the regret bounds later.", "was_revised": true, "final_justification": "The authors have answered my queries, including results from additional experiments and clarified regret formulation presentation for their revision. As acknowledged before, I'll keep my score.", "rebuttal": "We thank the reviewer for the valuable suggestions and address the concerns as follows.\n\n**Q1:** Regarding concern on the confidence interval in Figure 2\n\n**A1:** Thank you for your careful review. We would like to note that Figure 2 includes confidence intervals in a different format from Figure 1, using error bars rather than shaded regions (as in Figure 1). We chose this format because the confidence intervals are relatively small in this case, which may make them less visually prominent. This small variance across runs also supports the robustness and stability of our proposed algorithm, GSE. To improve clarity, we will revise Figure 2 either to be consistent with Figure 1 by using shaded areas or to enlarge the error bars to make the confidence intervals more apparent. \n\n\n**Q2:** Line 337 (...we sample $<>$ each  independently...) seems to have a missing term. Is it \"edge\"? In line 338 , what is this new term $q_i$ used to define means? They dont seem to have a definition either above or in the appendix table symbology! Is this expected?\n\n**A2:** Thank you for pointing this out. The missing term in Line 337 should be $q_i$. The variable $q_i$ is intentionally introduced to model the heterogeneity across agents by ensuring that each agent $i \\in [N]$ has a different reward distribution for the same arm $k$. Specifically, $q_i$ is independently and uniformly sampled from $[0,1]$ at the beginning, and the local mean reward is defined as $\\mu_{i,k} = q_i \\cdot \\frac{k-1}{K-1}$, which induces global heterogeneity. This experimental design follows a similar approach as in [1], and we will revise the text to clearly define $q_i$ and eliminate any ambiguity in the revised version.\n\n\n\n**Q3:** In line 348 authors briefly discuss the algorithm's performance based on the rate at which agents discard\ntheir dominated arms. A graph on these dynamics, something like that arms discarded over total arms discarded along with the regret in a temporal phase, like in Figure 1 would be very informative, right? This\ncould help clearly define for the agents' exploitation phase of farming rewards from the \"trusted\" arms!\n\n**A3:** To further investigate the dynamic behavior of our algorithm during the arm elimination phase, we track the regret progression at each point where an arm is eliminated. Table 4 records five independent trials under a classical Erdős–Rényi communication graph with $p=0.9$. After averaging over 20 trials, we report the average timestep when an arm is eliminated and the average corresponding cumulative regret. We observe a consistent trend across experiments: each elimination event corresponds to a gradual transition from exploration to exploitation, as reflected in the slower growth rate of regret after the elimination of more suboptimal arms. This illustrates that agents progressively narrow their action set to focus on near-optimal arms, thereby stabilizing their regret growth. This temporal analysis provides empirical support for our theoretical discussion, and highlights the importance of timely arm elimination in reducing long-term regret.\n\n\n*Table 4: Average over 20 runs of GSE with classical Erdős–Rényi graph and p=0.9.*\n\n| # Eliminated Arms | Avg. Timestep | Avg. Regret |\n|-------------------|--------------:|------------:|\n| 1                 |        332.0  |     81.9875 |\n| 2                 |        372.4  |     89.5367 |\n| 3                 |        443.4  |     98.1758 |\n| 4                 |        650.2  |    111.0484 |\n\n\n**Q4:** A bit mild on the multi-agent side of problem formulation: getting information from agents, even ones you are neighbors with can be noisy/adversarial from the agents' perspective!\n\n**A4:** We appreciate the valuable suggestions and would include the discussion on scenarios with noisy and adversarial agents in the future work section as well. The discussion reads as follows verbatim. 1. Noisy agents: When information from other agents is noisy—meaning that the shared reward data consists of the original reward signal plus potentially random noise or has correlation risks [4], as commonly observed in digital communication channels—this issue can, in principle, be addressed using techniques from noisy optimization [6]. These methods combine statistical and optimization tools to effectively handle function optimization under noise, which can be leveraged in the construction of reward estimators when using such noisy information. Also, this problem is novel and meaningful in the sense that random communication and random noise coexist, making the noisy optimization problem more challenging. 2. Adversarial agents: When other agents are adversarial—intentionally broadcasting malicious information—we will adopt a Byzantine-robust framework [2, 5], in which the reward information is truncated to produce robust estimators, such as the trimmed mean or median of means, to filter out malicious reward information. Notably, this direction is novel in that the presence of random graphs with underlying base graphs further complicates the construction of Byzantine-robust estimators, compared to traditional multi-agent bandits or distributed robust optimization settings with fixed, connected graphs or assuming linear reward models.\n\n\n**Q5:** While authors already clearly acknowledge their algorithm suffers from a tradeoff between regret minimization and communication cost reduction, they could probably benefit from analyzing the communication in a broadcasted sense that emerges from the connected components in the $\\mathcal{G}_t$, rather than a one-to-one communication between edges several times.\n\n**A5:** We appreciate this suggestion and will include the idea of communication cost reduction through the information propagation of graph-level analysis rather than edge-level analysis in the discussion of future work. Hypothetically, communication based on connected components can be illustrated using $l$-connected graphs [3], which consider the composition of subgraphs across time steps. Instead of analyzing a single graph at each time step, we consider the joint information provided by graphs from previous steps, which could potentially further reduce communication costs.\n\n[1] Jialin Yi and Milan Vojnovic. Doubly adversarial federated bandits. In the International Conference on Machine Learning, 2023.\n\n[2] Vial, Daniel, Sanjay Shakkottai, and R. Srikant. Robust multi-agent bandits over undirected graphs. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 2022\n\n[3] Zhu, Jingxuan, and Ji Liu. Distributed multiarmed bandits.  IEEE Transactions on Automatic Control, 2023\n\n[4] Shao, Qi, Jiancheng Ye, and John CS Lui. Risk-aware multi-agent multi-armed bandits. Proceedings of the Twenty-fifth International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, 2024.\n\n[5] Mitra, Aritra, Arman Adibi, George J. Pappas, and Hamed Hassani. Collaborative linear bandits with adversarial agents: Near-optimal regret bounds. Advances in neural information processing systems, 2022\n\n[6] Mai, Van Sy, Richard J. La, Tao Zhang, and Abdella Battou. Distributed optimization with global constraints using noisy measurements. IEEE Transactions on Automatic Control, 2023"}]

Author rebuttal:

Meta-review: The paper studies the multi-agent multi-armed bandits problem over random communication graphs (Erdos-Renyi, each edge appears with probability p). The authors propose an algorithm that achieves roughly log T regret and has dependence on the connectivity of the communication graph, the number of agents and arms and provide a matching lower bound. The reviewers were engaged in the discussion and provided thorough comments. The overall opinion was positive after the rebuttal. We recommend acceptance and advise the authors to invoke the reviewers' thorough comments in the camera ready version.
Decision: Accept (poster)