Federated Multi-armed Bandits with Efficient Bit-Level Communications
Authors: Haoran Zhang
Yang Xu
Xuchuang Wang
Hao-Xu Chen
Hao Qiu
Lin Yang
Yang Gao
Venue: NeurIPS 2025 poster ()
Keywords: federated multi-armed bandit
communication-efficient algorithm
Primary area: reinforcement_learning

Abstract: In this work, we study the federated multi-armed bandit (FMAB) problem, where a set of distributed agents collaboratively aim to minimize cumulative regret while interacting with a shared set of arms. Unlike traditional centralized bandit models, agents in FMAB settings are connected via a communication graph and cannot share data freely due to bandwidth limitations or privacy constraints. This raises a fundamental challenge: how to achieve optimal learning performance under stringent communication budgets.
We propose a novel communication-efficient algorithm that decouples the learning process into two phases: one for eliminating suboptimal arms through early and frequent communication of key decisions, and another for refining global estimates using buffered, quantized, and differentially transmitted statistics. By carefully balancing the communication frequency and precision of shared information, our algorithm achieves the optimal individual regret bound $O(N^{-1}\log T)$ while significantly reducing the total number of communication rounds and transmitted bits.
Theoretically, we derive tight upper bounds on both individual cumulative regret and group regret, and prove that our method asymptotically matches the lower bound of regret in federated settings. Experimental results on synthetic data validate the effectiveness of the proposed approach in various graph topologies and under heterogeneous feedback.

Federated Multi-armed Bandits with Efficient Bit-Level Communications
Haoran Zhang Nanjing University
Yang Xu
Nanjing University yang. xu@smail -nju edu on
6020237100040smail .nj.. edu. en
Xuchuang Wang
Hao-Xu Chen Nanjing University 27 27185226370qq com
University of Massachusetts Amherst xuchuangv@gmail. com
Hao Qiu
Lin Yang"
Yang Gao Nanjing University gaoyōnju. edu. cn
Università degli Studi di Milano hao. aeoo.qu@unn qiu@unimi.it
Nanjing University
linyang@nju edu. cn
edu.
Abstract
this work, we study the federated multi-armed bandit (FMAB) problem, where set of agents collaboratively aim to minimize cumulative regret. Unlike tradi- tional centralized bandit models, agents in FMAB settings are connected via a communication graph and cannot share data freely due to bandwidth limitations privacy constraints. This raises a fundamental challenge: how to achieve optimal learning performance under stringent communication budgets. We propose novel communication- -ffficeent algorithm containing two points: one for climinating suboptimal arms through early and frequent communication of key decisions, and the other for refining global estimates using incremental epoch, quantized, and differentially transmitted statisties. Incremental Epoch-based Successive Elimina- tion Algorithm (EpoInc-SE) is presented by carefully balancing communication frequency and precision of global estimates. Theoretically, we derive tight upper bounds on both individual cumulative regret and group regret, and prove that our method asymptotically matches the lower bound of regret in federated settings. Experimental results on synthetic data validate the effectiveness of EpoInc-SE in various settings and under heterogeneous feedback.
Introduction
The stochastic multi-armed bandit (MAB) problem is classic and influential research topic in the field of sequential decision-making [Bandits Lattimore and Szepesvári, 2020]. In this model, decision-maker must select an arm from set of actions at each time step to pull and receive random reward. The core objective is to maximize cumulative rewards, or equivalently, minimize cumulative regret, which is defined the reward lost compared to always selecting the optimal arm. Due to its powerful modeling capabilities and wide applicability. the MAB framework has been successfully applied in numerous domains, such clinical trials [Wang] 1991), online advertising recommendations (Tang al., 2015) and resource allocation [Latimmore et 2015).
In recent years, with the development of distributed systems and increasing awareness of data privacy, traditional single-agent MAB models have gradually extended to multi-agent collaborative scenarios,
*Corresooniigg author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table 1: Comparison of existing FMAB algorithms with our proposed method EpoInc-SE.
Algorithm
Central Server
Home-
Hetev/
Individual Regret
Regret
Group
Bit-Com
7hu et al
Gossip DCB
2021
Hete-
O NA, TogT)
1 N A TogT)
O(T log T)
D15 D0B
0 20 Nania A, logT) o DA NN A logT)
O(T T)
Zhu and Liu
2023
UCS-TTUR
Homo-
0 Miaa,,50 N AA,1 log T)
O 47 log
Ó T)
Wang and Yang
2023
Fe8:2-0CB
Homo-
O1EnA N N
", logT)
0 O 47 log?")
O(T log ?')
Shi and Shen
2021
EpoIne-SB (our work)
Hete-
0 D N A, log
OiE,,,,0 A, log 7')
O(vlog T)
Regret lower bound
Hete-
"( N AA," log
D A,
log T)
Niin denotes the smallest number of neighbors for any agent, including the agent itself.
where the Federated Multi-Armed Bandit (FMAB) problem has garnered increasing attention Li eet al. 2024 Boursier and Perchet 2024). In large-scale sensor networks, environmental constraints and cost considerations often prevent full physical connectivity or the deployment of a central server, naturally leading to the need for distributed information processing and computation [Xiao al.) 2005 Golovin et al. 20110]. Moreover, online service platforms with many servers often store large volumes of data locally. To protect user privacy, centralizing this data for computation and training is impractical, where federated learning is a useful and crucial approach to complete the two tasks Ellison and Fudenberg [1995]. Sankararaman et al. [2019].
In FMAB problems, the primary objective is to minimize the total regret accumulated across all agents, referred as group regret in this paper. This metric has been widely studied in prior works (Kalathil eet al. 2014 (Shi and Shen. 2021 Xu and Klabjan| 2024). However, in many practical scenarios, the performance of individual agents also plays critical role, as it can become the bottleneck that limits overall system effectiveness. In network optimization literature (Srikant and Ying] 2014). the max-min fairness system's 's fairness, Another important metric in FMAB problems is communication bit incurred by all agents. In real-world scenarios, communication is often expensive and establishing peer-to-peer (P2P) connectivity may be impractical. To evaluate this cost, the number of communication rounds is a commonly used metric [Cho et al. 2020 Li and Song 2022]. However, a single round may involve transmitting multiple messages, which is misleading for evaluating an algorithm. Therefore, more precise and informative measure is the total number of communication bits, which has been adopted in recent studies (Wang et al. 2020 Agarwal et al. 2022].
maximie the minimal individual reward- is widely used to measure
Related Works. The most relevant prior works on FMAB have been summarized in Table Among them, Gossip_UCH [Zhu et al.) (02T] and Dis_ UCB [Zhu and Liu 2023) are the two works most related to ours, which are all heterogeneous FMAB without central server. However, they could not obtain the optimal results compared with Epo Inc-SE (our work). Fed2-UCB (Shi and Shen 2021] and UCB-TCOM [Wang and Yang 2023] are two typical Homgeneous FMAB algorithms that use central server and fully distributed communication, respectively. Meanwhile, they all achieve the optimal result and UCB-TCOM (Wang and Yang 2023] also optimizes the communication rounds. The two algorithms provide classic frameworks for bandit learning. Hence, we apply consensus estimator on them and take them as the baseline in Section [5] Several works have investigated the regret lower bound in federated bandit settings [Xu and Klabjan 2023 Wang et al.) 2020). Specifically, they establish group regret lower bounds for heterogeneous and homogeneous FMAB problems, respectively. In addition, Xuu and Klabjan| [2023) shows that, in the absence of information exchange with neighbors, an agent in a federated setting can suffer linear regret O For bit communication techniques, there are not too many works on heterogeneous FMAB. But there are also some interesting works about bit communication in other directions [McMahan et al. 2017 Casteigts ct al. 2019 Wang et al. 2019 Boursier and Perchet 2019 Shi et al. 2021 Wang al. 2019 and Shi et al. [021] reduced the communication rounds of the algorithm under a homogeneous setting. These works [McMahan et al.] [017]] Boursier and Perchet 2019 considered communication bits for the first time in bandit problems. The truncation of messages is proposed in Casteigts et al. (2019), Shi al. 2022T] Our communication optimization method combines the advantages of works above.
Contribution. Addressing the aforementioned challenges, this paper proposes a novel federated multi-armed bandit algorithm designed for fully distributed communication networks. It enables

---

agents to effectively solve the global MAB problem and simultaneously optimize individual and group regrets by communicating solely with their neighbors. Distinct from previous work, our main contributions and innovations include:
(1) Optimization of Communication Efficiency: EpoInc-SE is the first work considering the com- munication cost in heterogeneous federated bandit learning. By employing epoch-based exploration reduce communication rounds and designing an adaptive difference communication mechanism, we significantly reduce the communication rounds and the number of effective information bits per communication round. Additionally, we introduce a two-phase communication strategy differen- tiate the transmission priority of different types of information, thereby enhancing communication efficiency while preserving regret performance.
(2) Near-Optimal Regret Performance: We propose the first lower bound of heterogeneous federated bandit E N A N log T) with the dependence of the number of agent N, which matches the upper bound EpoInc-SE SE in terms of agent number N, reward gap A; and time horizon T, thereby proving the optimality of our algorithm design and analysis.
(3) Efficient Online Consensus Estimator: We design and introduce an epoch-based consensus estimation subroutine EBCES that allows each agent to unbiasedly estimate the global mean of arms under the condition of fully distributed communication and buffering broadcast. This is crucial for resolving heterogeneity and communication optimization.
The remainder of this paper organized as follows: details the problem model, including the communication model, the federated multi-armed bandit model, and performance metrics. Section 3 introduces our proposed
ceaimmnniaationefffiieeeee algorithm design, covering its core ideas, epoch- based exploration strategy, arm elimination mechanism, adaptive difference communication scheme, and consensus estimation policy. Section 4 provides the theoretical analysis of the algorithm, including proofs for regret upper and lower bounds. Section5]provian simulations to validate the theoretical analysis. Finally, Section 6 concludes the paper.
2 Problem Formulation
Communication Model. Consider fully distributed network, which works only via finite paths among agents, i.e., without a central server. The data exchanged between agents, called a message, is a string of binary numbers. The network is a (fully) connected graph, defined as g (N,E, A) (Huang et al. [022]. . is an agent set, where agents are labeled by {1...., .N. The E c N x W denotes the set of edges in the network. determine whether two agents are connected. For agent j, define its neighborhood as Ny. To meet computing needs, an additional matrix W- = (a.a.
[Qu.tl (a.beN
an adjacency matrix, used to
describes the weight of agents in their neighborhoods. The definition of W is W = I - BL, where L is the Laplacian matrix and (0, 1/N] the coefficient that reflects whether this agent believes its neighbors. If B = O, we have W = I, which means that the agent itself occupies all the weight. If 3 1/N, it indicates that the agent assigns equal trust to all of its neighbors.
System Model. There are N agents repeatedly making decisions from a fixed arm set KC (1...., K} over a time horizon T. At each time step t, agent j selects an arm A, and re- ceives reward (t) if (t) with an unknown (local) mean Mi.j E [0, 1]. These rewards serve as real-time feedback to guide agents in learning the expected rewards of the arms. In federated settings, the reward X,, is local observation that agent j samples from arm i. For arm Az(t) = i, there also exists a global reward (t) that is contributed by all agents' observations, i.c., (t) = Xt(t)= = ΣØ= X (t). The mean of X; is denoted by the global mean 14; == N ΣØ= M4g E [0,1], Without loss of generality, let 2t arg max; μ4 denote the unique optimal arm with the highest global mean among all arms. Define the suboptimality gap for each arm i as A := /4,- /4.. In this work, we consider a hetero- geneous setting where the local reward mean of arm may differ across agents, i.e., Pi,j * Pi.jz for ji + j2- There is no collision in this setting, implying that all agents can obtain rewards without degradation, even if they pull the same arm.
i. The reward X (t) is drawn from a --suu- Gaussian distribution
Individual regret. The individual regret of agent j is defined as the cumulative regret incurred all agents are to follow agent j's decision. This metric is crucial in federated learning, where the
3

---

Symbol/Term
Definition
K
The arm set
N
The agent set
A1(1)
The decision of agent time slot (1 E
Xiz(t)
The local reward of arm sampled by agent 7 at time slot t, Xi, (t) E 00
Pig
The local mean of arm for agent j. p E [0,
X,(t)
The global reward of arm i. (t) Σ (t)(t)
The global mean of arm i. μ4 = /=1 Ma.j
1*
The optimal arm with the largest global mean, i" E arg max; μi The gap between arm and the optimal arm, A; M4 14
A;
Table 2: Symbols of the multi-agent bandit problem
objective is to identify the arm with the highest global mean reward. Since relying solely on local rewards can be misleading, individual regret provides more meaningful measure of an agent's contribution to the global goal. The formal definition is given as follows,
E E (T) = Tp Σ ((
(I)
Group regret. The group regret is defined as the cumulative regret caused by all agents, which is also seen as main performance metric of the algorithm. The optimal performance of an algorithm is that all agents pull the optimal arm during the time horizon T.. Hence, for a distributed algorithm, the expected group regret of the entire system is defined as
B[R(T)) Σ (T))
Communication cost. Besides two regrets, the communication cost is also an important performance metric evaluate federated bandit algorithm. Two types of communication metrics are commonly used in previous works: communication rounds and communication bits. While the communication costs are primarily measured by the number of communication rounds, c.g.. Tao al. [2019), Yang et al. (2024). the number of communication bits is a more practical and realistic metric that accurately reflects the real-world cost of data transmission. In this paper, we define the communication cost in bit level, denoted C(T) as the total number of bits consumed from communicating all messages among all agents. In this work, we assume that any message (a number of bits) can be broadcast within single time slot. For any messages, we do not consider the identifiers, and there is no limitation on the message size.
EpoInc-SE: A Communication--Efiieen Algorithm Design
3.1 Key Ideas and Algorithm Structure
To achieve optimal regret bounds under limited communication, the core challenge lies in ensuring that the exchanged information is just sufficient to support accurate consensus estimation. Due to the heterogeneity in rewards, these local estimates often deviate from the global mean, making communication with neighbors necessary. This creates fundamental trade-off: sharing highly precise and real-time information provides limited improvement to the convergence of consensus estimation but results in excessive communication overhead. In Boursier and Perchet (209 Wang et al. 2019) information quantization and epoch-based exploration techniques were proposed to control the size of the message adaptively. However, these approaches are typically developed for homogeneous bandits with centralized structures, such as having a leader agent directly connected to all followers, and thus do not apply to settings with heterogeneity and fully distributed graphs.
In this work, we extend the classical successive elimination algorithm to a fully distributed setting, achieving an improved regret bound of O(E N N log T). Building on this, we further optimize the communication cost at the bit level, which comprises two key components: the number

---

of communication rounds (optimized in Section 3.2 and the message size (optimized in Section 3.3 The first component leverages a batched sampling strategy to reduce communication rounds. In distributed bandit settings, each agent must sample arms sufficiently to ensure accurate local estimates. Rather than communicating after every pull, agents accumulate multiple samples before sharing with neighbors. This reduces communication frequency and ensures that shared information is more reliable, particularly as early-stage observations tend to be noisy. Epoch-based exploration thus offers principled trade-off between statistical efficiency and communication cost, making the approach scalable in large, decentralized systems. The second component for optimizing communication complexity reduces the bit-width of the transmitted messages. Three kinds of statistics need to be optimized, including the indices of arms, the sample count of each arm, and the global estimate. The indexes of arms consume only Olog K) bits. which has no room for optimization. The sample count is implicit information considering the algorithm's 's synchronization. Hence, we improve the message size of global estimates from Olog T) (1)) bits. To realize this task, we propose differential encoding approach where agents share only the quantized change between consecutive estimates instead of the full values.
To further reduce communication costs while maintaining regret performance, we categorize shared information into two types based on their impact on the algorithm's 's efficiency. The first type includes indexes of eliminated arms, which are broadcast immediately to accelerate arm elimination and improve regret. The second type of shared information includes global estimates of arm means, which are tightly coupled with the sampling process. Sharing them too frequently does not directly contribute to faster convergence, but can significantly increase communication overhead. Therefore, this type of information should be buffered and communicated less frequently. Based on this insight, our algorithm divides communication into two distinet phases. Communication Phase is responsible for sharing the indexes of eliminated arms. This phase operates at a high frequency to ensure the timely elimination of suboptimal arms across agents. In contrast, Communication Phase II handles the exchange of global estimates. The frequency of this phase is intentionally kept low to limit communication costs. This design is especially effective when updates are frequent but minor, avoiding redundant communication.
Below, we introduce the details of the algorithm design. We start from the epoch-based exploration paradigm in Section 3.2 and then introduce three key modules of the algorithm design: an adaptive difference communication in Section 3.3 a consensus estimation policy in Section 3.4land and an arm
elimination policy in Section 3.5
3.2
The Epoch-based Exploration
In this section, we primarily introduce the epoch-based exploration strategy. To reduce the number of communication rounds overhead in federated learning, a buffering scheme that compresses communication rounds by delaying broadcasts is proposed. The main challenge is that excessive compression may cause newly collected local data to dominate the consensus estimation, which affects the contribution of agents' local observations in the global estimate (introduced in Section Therefore, we carefully make a trade-off between minimizing communication rounds and maintaining the accuracy of the consensus estimation.
Next, we present an incremental epoch-based exploration where later epochs contain increasingly more time slots. Without loss of generality, we concentrate the discussion on a specific agent j. The time horizon T is partitioned into series of subprocesses, labeled by Tj 1,2, ..... In epoch rj. agents maintain candidate set S to decide which arm pull. The initial set is S K. In epoch Ty, all arms in the candidate set S will be sampled p"s a(r, 1) times uniformly, where is hyper-parameter that determines the size of each epoch. Therefore, the number of epochs is at most O(VT) for the time horizon T. The time slot at the beginning of the epoch rj is denoted by byy. and the local empirical estimate the arm i during epoch ry is defined as follows
dryti-1 (1T((()) = i} Σ
bry
X[
(3)
a(r,+1)
5

---

Algorithm 1: Epoch-based Successive Elimination Algorithm (EpoInc-SE)(Co) agent j)
Input:
Weight matrix of graph W. time horizon T, set K. diameter D and integer Output: == 0, = 0, Ug = 1, S = K, X, = 0, By = Ø for all arms
Let agent j pull each arm times and receive sequence of rewards {X (t)]
Fig -- average X.))) P XT; for r 1,2,... do juna t- arg maxies, Fi for p' E f1....,,(4? a(,, + 1)] do
for i E Sj do
Pull arm and obtain the reward x Xi, t (x's - 1) Xxy)/p">; I/ Communication phase Receive By and f; from agent j's neighborhood Nj;
10
B; 2 then
11
Send Bj. fzy to all agent j's neighbors:
12
Update the new candidate set B, - B, U
U By J'ENG
B
// Communication phase II Update the global estimates via the adaptive difference communication (Algorithm) 2 Update UTS via equation (6)
14
15
for i E S do
16
if Paj
S Pigmx
2U then
17
P +
+1
D
B, + B,
18
for each arm i in Bj whose r, 2 do
19
[S then Sj + S (i), B, + Bi) else S, + SS
3.3
Adaptive Difference Communication
In this section, we optimize the communication cost by minimizing the message size. As outlined in Section global estimates occupy the main channel resources and they consume O(log T`) bits per message. Hence, we concentrate on optimizing the global estimate Pr, (introduced in Section 3.4..
native intuition to send brief information instead of precise global estimates. the early stages of consensus estimation, high precision unnecessary-initte rounds only require estimates accurate to single decimal place. This motivates the use of information quantization, where the quantized global estimate epoch rj is denoted as "[,.. The quantization is adaptive: larger messages yield higher accuracy. Specifically, the estimate epoch r, is represented using [1 + log, rj] bits.
To further reduce the message size, another approach based on sharing differential information rather than full local estimates. Instead of transmitting quantized statistics each round, agents communicate only the differences between their current and previous values, i.e., quantization error 8 = nK, r-1 This technique leverages the temporal smoothness of learning processes, significantly reducing the communication overhead while maintaining estimation accuracy.
Due to that ,h, has [1 + log, ry] bits and p is a quantization version of Ni,3. the error between them is bounded by
1 2r
ML 1 S 211+log, rs
r3 +2
Remark Wang et [2019] has proved that OQlog T) bits are sufficient to distinguish the optimal arm from the arm set K. considering that the gap D; may be small enough. The global estimates contribute large number of bits to the communication cost. By exploiting the quantized variable Di reduce the message size to O0V1o11 T). ). By using differential communication,
only

---

Algorithm 2: Epoch-based consensus estimation subroutine (EBCES) (for agent
Input: The local reward X Xi.j- the candidate set Sy, the epoch ry and the weight matrix
W = [w].)r]
Output: The latest estimate Pú,j and elimination arm set B3j it [S]] > 1 then
Communicate the global error 5/5 with its neighbors:
// Communication phase
Receive the global estimate / ,J' E NG from agent j's neighbors;
for j' do P o
L Pig
Update the global estimate pig via equation 5 Pig f- )))
o + Pij Pl.
use (() bits per message. is also the first work that obtains optimal message size in heterogeneous federated bandit learning.
3.4 Consensus Estimation Policy
The heterogeneous reward in this problem motivates agents learn the global means of arms and cooperate with their neighborhoods. Therefore, an epoch-based consensus estimation subroutine (EBCES), exploiting epoch-based exploration (Section 3.2p and differential information quantization (Section 3.3 is proposed to be integrated into Inc
The core idea of EBCES is synchronize information exchange among neighbors and effectively utilize their shared data to achieve an unbiased global estimate. As discussed in Section 3.3 agents exchange 5 instead of Mi and reduce the information bits O(1) order. In the consensus estimation process, agents combine differential information 8%, with the historical quantized variable
" to compute the latest global estimates from neighbors (Line Algorithm 2). On the basis of the information exchange above, fair estimation mechanism is presented in which samples from all agents are used equally estimate the global mean.
To obtain global estimates, agent j combines its neighbors' historical data and its own average empirical reward X Up to the end of epoch r,, agent j collects 33 o NN and updates its global estimate as follows:
M. = (1-0((r))
Σ W + (r(r))&i J'EN,
(5)
where o:(-) is the weight that adjusts the contribution of the information in the global estimate (
3.5 Arm Elimination Policy
In this section, we introduce an elimination arm set BY that stores the indexes of arms identified as suboptimal. At the beginning each epoch, each agent compares the global estimates of all arms and selects the one with the highest estimated reward as the bascline (Line Algorithm []]. Then, each arm will be compared with arm juna, which is considered sub-optimal and added to the climination set Bj if it falls below the baseline by margin that is related to the confidence radius.
Denote the sample count of agent j on arm until epoch ry by TI, = a(r, + 1)(rr + 222/2. The total sample count on arm is T." NTTz because of synchronous sampling. Define pJ as the global estimate of agent on arm According to Hoeffding's inequality, there exists a radius of confidence interval UT, such that 1 [M: U i4 U[gl. with
log 5-1
2C
(6) = aN(Tr + 1)(r, + 2)
(6)
(ry + 2)(1 X2)
ry +
(a)
(c)

---

where 5 specifies the violation probability, Tenms (a) and (b) are from Lemmas 2 and 3 Term (c) is
caused by information quantization (introduced in Section B.3). The detailed proof of the confidence interval 6 is proposed in Appendix D.I Arm i is identified as sub-optimal if it satisfies
Pi + U S Mi U..g
To help agent j determine whether the information in B has been acknowledged by all agents, we introduce epoch label F;s which denotes the latest epoch by which all agents guaranteed to know that arm is suboptimal. Then, all agents agree to eliminate it from the candidate set at epoch f.
D
A - ry +
(8)
a(ry+1) + 1)
where D is the diameter of the graph g. The elimination arm set Bj is constructed
BJ = {ú, i E Sj 3/' E Sj {i} such that Wii5 S F 201T)- The candidate set S is updated based on the information in 13 until only one arm remains, which is identified as the optimal arm. Once an arm is eliminated from Sy. it also removed from B, to avoid redundant communication (Line 19 Algorithm T).
(9)
4 Analysis
In this section, we summarize the theoretical results concerning both regret and communication cost. We begin by introducing Lemmal] [ which provides a concentration bound for the global mean. Unlike traditional concentration results based real-time data, approach leverages batched information to perform consensus estimation, which obtains a similar performance. This key insight allows us establish upper bounds on both communication rounds and regret, which are detailed in Section 4.1 Finally, Section (42 presents the corresponding lower bounds.
Lemma 1. Let i E K. be any arm, E N be any agent, and r E (1,1,... .......... be any epoch. Assume reward X (1) is an i.i.d. process with unknown mean pi.. (r,) r Then, with probubility at least - 26, the gap between the global estimate Pi.5 and the global mean μs satisfies
log 8-1
2C
|mh, -
-p:lm mil=
aN(r, + 1)(r, +2) + (1--2)(r, +2)
+
(10)
T3 22'
where X2 is the second largest eigenvalue of the weight matrix W (characterizing network con- nectivity), or(r;) is the variance proxy of local means across agents, and C is positive constant determined by 9, ie., C when G is balanced; otherwise, C' VN.
Proof Sketch of Lemma D We decompose the estimation error into three parts: quantization error |T4 Pi.yl l. consensus error 1اt A I. and concentration error [ÃT - #4/. The quantization етгоr arises from limited communication precision and is controlled by the quantization scheme. The consensus error results from averaging over a network with imperfect information propagation and is bounded using spectral properties of the communication matrix. Finally, the concentration error comes from estimating the true mean using sub- Gaussian samples and is handled via standard probabilistic bounds. Combining these yields confidence interval for the global estimate.
4.1 Upper Bound
Theorem 1 (Upper regret bound). Let UTJ in (6) with 8 T be the radius of the confidence interval of a random [0. 1]-valued i.i.d. process. Given any constant y > and or(r,) 2/ + 2). Algorithm 7 could achieve the following results.
ii) For each agent j, individual regret:
(T) SO
Σ NN log
(ii) Group regret:
B[R(T) 0o Σ A logT 1ogTT
8

---

Proof Sketch of Theorem 1 To bound both types of regret, we first establish an upper bound on the sample counts of sub-optimal arms. From equation ( we derive an instance-dependent bound, then account for the additional samples required to synchronize agents under the communication delay. This adjustment depends on the graph's 's diameter and the theoretical result in equation (7). Finally, combining the gap terms with these sample counts yields the overall regret bounds. Detailed proofs are provided in Appendix D.2
Theorem 2 (Upper communication cost). When all agents execute EpoInc-S2 (Algorithm 7 the total communication cost over the entire time horizon is at most O(Ei,,,0 VNA," Vlog T) bits, in order to achieve the regret bounds stated in Theorem 7
Proof Sketch of Theorem 2 To optimize communication cost, the key idea is minimize both the size of global estimates and the number of communication rounds. The message size is reduced to O(1) through differential communication, while the epoch-based exploration policy decreases the communication frequency to the order of ( OVVlog I'). By combining these two strategies, we derive the upper bound of the overall communication cost.
The lower bound of the communication cost is still important problem for heteroge- neous bandit problems. The previous work Wang et al. [2019] provides constant level lower bound for the homogeneous bandit. However, the heterogeneous bandit setting poses more challenging property, i.e., heterogeneous feedback, which implies that more essential communication is needed for obtaining a near-optimal result. It is interesting work that is worth learning.
Remark 2.
Remark 3. In the worst case, the message in the communication phase I will consume at most O(NK)
bits. In the communication phase the message will consume at most log K + K log log T bits.
4.2 Lower regret bound
Besides the upper bounds of regrets, we also present lower bounds for this problem. We investigate the lower bounds of both individual and group regrets, where the elements in the upper bounds match those in the lower bounds.
Theorem 3 (Regret lower bound). For FMAB problems with any number of agents, arms, and stochastic rewards satisfying 1-Gaussian distribution, if the graph G is connected, any federated bandit algorithu must incur regrets at least:
(i) For each agent j. individual regret:
(T)
lim inf
T-000
log
NA,
0A,30
(ii) Group regret:
lim inf
B[R(T)]
Σ
2
log T
A
EAID
Proof Sketch of Theorem 3 To derive the lower bound for federated heterogeneous bandit problems, the main challenge lies handling the randomness of decision-making across multiple agents. To address this, we introduce other agents' observations on the same arm. This additional information does not tighten the lower bound. We then show that it does not affect the consensus estimation, after which the regret lower bound follows directly from the proof techniques in [Lattimore and Szepesvári 2020].
auxiliary "replica" subsystem that allows agent j to access
Remark 4. The lower bound of the heterogeneous federated bandit problem is also discussed in Theorem 3 in and Klabjan [2023]. Different from the previous work, we prove the lower bound by using a relaxed model. In this model, each agent obtains additional information (Details are given in Section 3), and the result is obtained directly by using Theorem in Garivier el al. 2019))
5 Experiments
In this section, we conduct a series of experiments on different algorithms. All experiments are repeated for 50 trials, with means plotted lines and standard deviations as shaded regions.

---

Setups and Baselines. Unless otherwise stated, the experiment scenario involves a network of N = 8 agents and K 10 arms, parameters C = vV, = 5 and T = 10% To ensure fair comparison, we use ring graph and all agents occupy the same weight in their neighborhoods, which common undirected connected graph with the second largest eigenvalue 22 0.5713. We consider four baselines: Gossip_UGe UCB [Zhu al. [02T] Dis-UCK [Zhu and Liu 2023]. Fed2-UCB (Shi and Shen. 2021] and UCB-TCOM [Wang and Yang 2023]. The theoretical results of them are discussed in Table The individual regret evaluated by the maximum individual regret among all agents. For Fed2-UCB and UCB-TCOM, a consensus estimation module is attached to them to help them against heterogeneity. The two algorithms communicate the historical reward at each time slot. Hence, the
consensus estimator is (t) = NI Σ E (k).
Observations. From Figures Ta and Tb both group and individual regrets of EpoInc- are only slightly worse than that of Fed2-UCB, primarily because Fed2-UCB leverages central server, which enables faster convergence compared fully distributed graph. Figure shows that EpoInc-SE results in the lowest bit-level communication overhead among all compared methods, highlighting the efficiency of our algorithm in minimizing communication costs. Figures [d] indicate that Epoinc- still has good performance when N, K, 6 vary. We also make some experiments under homogeneous settings in Section and some experiments large-scale multi-agent systems in Section F
Gossip UCB --X--
Dis-UCB -- Fed2-UCB
UCB-TCOM
Epolnc-SE(Our works)
Comsasati etten
100
3.0
(a) Individual regret
(b) Group regret
(c) Communication cost
Comm monmmmattiionnn Bitls
104
Commmmtaation
10/9
10"
301
10:
Number
Number
(d) Vary reward gap
(e) Vary arm number
(I) Vary agent number
Figure Performance comparison with different algorithms.
Conclusion
This paper proposed a communication-sunn solution address the challenges faced by FMAB problems in environments with heterogeneous rewards and fully distributed communication networks. We successfully tackled the shortcomings of existing research in areas such as information fusion, regret performance, and communication efficiency, particularly in scenarios where there is no central coordinator and agents can only communicate with their neighbors. The main contribution of this paper lies in the design and introduction of an efficient federated learning algorithm IpoInc-SC which greatly reduces the communication cost and obtains ((1) bits. Besides, we first propose a lower regret bound in this setting and prove that Epo Inc-SE is near-optimal under limited communication. Future work could explore applying this framework to more complex network dynamics or considering more advanced
mechanisms.
10

---

7 Acknowledgment
This work was supported by NSFC (no. 62306138), JiangsuNSF (no. BK20230784), and the Innovation Program of State Key Laboratory for Novel Software Technology at Nanjing University (no. ZZKT2025B25). HQ acknowledges the financial support from the EU Horizon CL4-2022- HUMAN-02 research and innovation action under grant agreement 101 120237, project ELIAS (European Lighthouse Al Sustainability) and from One Health Action Hub, University Task Force for the resilience of territorial ecosystems, funded by Università degli Studi di Milano (PSR 2021-GSA-Lines 6).
References
Mridul Agarwal, Vaneet Aggarwal, and Kamyar Azizzadenesheli. Multi-agent multi-armed bandits with limited communication. Journal of Machine Learning Research, 23(212):1-24, 2022.
Multi-Armed Bandits. Introduction multi-armed bandits.
Etienne Boursier and Vianney Perchet. Sic-mmab: Synchronisation involves communication in
multiplayer multi-armed bandits. Advances in Neural Information Processing Systems, 32, 2019.
Etienne Boursier and Vianney Perchet. A survey multi-player bandits. Journal of Machine Learning Research, 25(137):1-45, 2024.
Arnaud Casteigts, Yves Métivier, John Michael Robson, and Akka Zemmari. Deterministic leader election takes / (d+ (d+\log n) 0 (d+ log n) bit rounds. Algorithmica, 81:1901-1920, 2019.
Yae Jee Cho, Samarth Gupta, Gauri Joshi, and Osman Yagan. Bandit-based communication-efienee client selection strategies for federated learning. In 2020 54th Asilomar Conference on Signals, Systems, and Computers, pages 1066-1069. IEEE, 2020.
Devdatt P Dubhashi and Alessandro Panconesi. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, 2009.
Glenn Ellison and Drew Fudenberg. Word-of-mouth communication and social learning. The Quarterly Journal of Economics, 10(1))93-125,, 1995.
Aurélien Garivier, Pieme Ménard, and Gilles Stoltz. Explore first, exploit next: The true shape of regret in bandit problems. Mathematics of Operations Research, 44(2):377-399, 2019.
Daniel Golovin, Matthew Faulkner, and Andreas Krause. Online distributed sensor selection. In Proceedings of the 9th ACM/IEEE International Conference on Information Processing Sensor Networks, pages 220-231, 2010.
Jun Huang, Haoran Zhang, and Tarek Raïssi. Distributed interval estimation methods for multiagent systems. JEEE Systems Journal, 17(2):1843-13 2022.
Dileep Kalathil, Naumaan Nayyar, and Rahul Jain. Decentralized learning for multiplayer multiarmed bandits. IEEE Transactions on Information Theory, 60(4):2331-234) 2014.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Tor Lattimore, Koby Crammer, and Csaba Szepesvári. Linear multi-resource allocation with semi- bandit feedback. Advances Neural Information Processing Systems, 28, 2015.
Jian Li, Tongbao Chen, and Shaohua Teng. A comprehensive survey on client selection strategies in federated learning. Computer Networks, page I 10663, 2024.
Tan Li and Linqi Song. Privacy-preservve communication--fffccleooooooo federated multi-armed bandits.
IEEE Journal on Selected Areas in Communications, 40(3):773-787, 2022.
Brendan McMahan, Fider 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.

---

Michael Molloy and Bruce Reed. Graph colouring and the probabilisstc method, volume 23. Springer Science & Business Media, 2002.
Reza Olfati-Saber, J Alex Fax, and Richard M Murray. Consensus and cooperation in networked multi-agent systems. Proceedings of the IEEE, (5(1):215-22) 233, 2007.
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 (3):1-35, 2019.
Chengshuai Shi and Cong Shen. Federated multi-armed bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 9603-96111 11119961,,20 2021.
Chengshuai Shi, Wei Xiong, Cong Shen, and Jing Yang. Hetcrogeneous multi-player multi-armed bandits: Closing the gap and generalization. Advances in neural information processing systems, 01122392-2240- 2021.
Rayadurgam Srikant and Lei Ying. Communication networks: An optimization, control and stochastic networks perspective. Cambridge University Press, 2014.
Liang Tang, Yexi Jiang, Lei Li, Chunqiu Zeng, and Tao Li. Personalized recommendation via parameter-free contextual bandits. In Proceedings of the 38th international ACM SIGIR conference on research and development in information retrieval, pages 323-332, 2015.
Chao Tao, Qin Zhang, and Yuan Zhou Collaborative learning with limited interaction: Tight bounds for distributed exploration in multi-armed bandits. In 2019 IEEE 60th Annual Symposium Foundations of Computer Science (FOCS), pages 126-146, 2019, doi: 10.1109/FOCS 2019.00017.
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 4120-4129. PMLR, 2020.
Xuchuang Wang and Lin Yang. Achieving near-optimal individual regret low communications in multi-agent bandits. In The Eleventh International Conference on Learning Representations (ICLR), 2023.
You-Gan Wang. Sequential allocation in clinical trials. Communications in Statistics-Theory and Methods, 20(3):791-805, 1991.
Yuanhao Wang, Jiachen Hu, Xiaoyu Chen, and Liwei Wang. Distributed bandit learning: Near-optimal 2019.
regret with efficient communication. arXiv preprint
Lin Xiao, Stephen Boyd, and Sanjay Lall. A scheme for robust distributed sensor fusion based on average consensus. In IPSN 2005. Fourth International Symposium Information Processing in Sensor Networks, 2005., pages 63-70. IEEE, 2005.
Mengfan Xu and Diego Klabjan. Regret lower bounds in multi-agent multi-armed bandit. arXiv preprint arXiv:2308.
2023.
Mengfan Xu and Diego Klabjan. Decentralized randomly distributed multi-agent multi-armed bandit with heterogeneous rewards. Advances in Neural Information Processing Systems, 36, 2024.
Feng Yan, Shreyas Sundaram, SVN Vishwanathan, and Yuan Qi. Distributed autonomous online learning: Regrets and intrinsic preseeviin properties. IEEE Transactions on Knowledge and Data Engineering. 25(1 1):2443-2499, 2012.
Lin Yang, Xuchuang Wang, Mohammad Hajiesmaili, Lijun Zhang, John C.S. Lui, and Don Towsley, Cooperative multi-agent bandits: Distributed algorithms with optimal individual regret and commu- nication costs. In Coordination and Cooperation for Multi-Agent Reinforcement Learning Methods Workshop, 2024.
Jingxuan Zhu and Ji Liu. Distributed multi-armed bandits. IEEE Transactions on Automatic Control, 2023.
Zhaowei Zhu, Jingxuan Zhu, Ji Liu, and Yang Liu. Federated bandit: A gossiping approach. Proceedings of the ACM Measurement and Analysis of Computing Systems, 5(1):1-29, 2021.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract reflects our work and contributions greatly.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in 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 perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: by [Yes]
The limitations are written in Appendix
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in 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 the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might 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 address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
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]
13

---

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

---

Answer: [Yes]
This work does not have any dataset, but we provide all code in the supple- mental material.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (httpss//nips.ccppbblee guidessCoeeSubmissionnn
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 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 Sttppabicgguuieeeooeeebbbbbeeeee
for more details.
The authors should provide instructions 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 new 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, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The experimental details are given in Section 5
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, 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:
The confidence interval defined in Section 3.5
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall 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).
15

---

It should be clear whether the error bar is the standard deviation or 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 еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: Our work is theoretical, and the experiment is not the core. Besides, our experiment a small simulation that could work on any computer with VS Code. Hence, we think it is unnecessary.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer:[Yes)
Justification:
This paper is theoretical work that has nothing do with human morality.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: This paper is theoretical work that has nothing to do with human society.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 being used as 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 (e.g., gated release of 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 MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper is not connected with models that have a high risk.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses 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: The codes in this paper are all from the authors.
Guidelines:
The answer NA means that the paper does not 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.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode, pepersswihhcdde.co//ltttsee has curated licenses for some datasets. Their licensing guide can help determine the license of a 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.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset'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: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is 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. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in 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 the NeurIPS Code of Ethics, workers involved in data collection, curation, or 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending 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 to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
18

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: This research does not involve LLMs any important, original, non- standard components.
Guidelines:
The answer NA means that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy http://leeuig..ccccommcre////sss for what should or should not be described.
19

---

A Appendix Symbol explanation
For all symbols in this article, we give explanations of them in Table 3
Symbol/Term
Definition
E( A)
A graph to describe a multi-agent system Set of agents in a mulli-agent system
N 11,..,,
Ec N X N
The edge set in graph G
A= (1.5) NNN
NXN
The weight matrix to describe the relations between agents Neighborhood of agent j. excluding agent j
N2
W
Wa.b NxN
Communication matrix
D
The diameter of graph g
A2
The second largest eigenvalue of W
A symbol to describe whether the graph is balance Set of arms in multi multi-armed bandit (MAB) problem
K [1....,
K
Total number of time slots
(t)
Arm chosen by agent j at time s
X (t)
Random reward received by agent j after pulling arm (y()) at time slot t
(t)
Random reward for arm observed by agent, j at time slot
Ma.
Mean reward for arm observed by agent j. bounded in [0,1]
(,(t)
Global reward for arm i at time slot t
a
Constant that determines the size of an epoch
p'
The sample count of any in S in epoch rj. p" alr; + 1)
X
The average local reward of X;,; in epoch r'
Global mean reward for arm 2
(t)
The global estimate of agent j on arm i at time slot t The unique optimal arm with the largest global mean reward
jmax
mmax arg maxies; Pt.j
S
The candidate arm set of agent j at time slot
B7
The elimination arm set of agent j at time slot /
The epoch label attached to arm
A
14/
Reward gap between the optimal arm and arm
The sample count of agent j on arm i until epoch rj
T
The global sample count on arm until epoch rj
The violation probability confidence interval
UE, (0)
The radius of confidence interval
[] E[
Expected group regret
Expected individual regret of agent
Table 3: Summary of symbols and Definitions
B Appendix/ / some knowledge of graphs
Throughout this paper, we consider a FMAB problem with N agents operating in time-invariant network. The network represented by communication graph (NN E.A,, which consists of three components:
1. - (I....,NT N is the set of agents in the network, corresponding to the number of agents in the distributed system.
2. & C N is the edge set, which determines the connectivity between agents.
3. A- 1a-aaa.-ina n is the adjacency matrix of the graph G, where "jا"" denotes the weight of the edge between agents j and j".
Notably, the adjacency matrix represents the importance of one agent to its neighbors and encodes neighborhood information in G. Specifically, ajsy is the weight from agent j' to agent j. Since the graph is directed, we have ajs' # g.
20

---

The graph has no self-loops, meaning that aj. 0 for all j E N. An edge between agents j and j' exists and only if 'j.s' + 0, i.e. (i.'')
For each agent j. its neighborhood denoted as N, = ( أ E N,,a + 0, * j}. Finally, define the diameter of the graph 9 as D. which represents the longest distance between any two agents in the network.
For graph G, its corresponding Laplacian matrix L is defined as follows
i i
N
ajs j=
The maximum degree of graph G is defined as e = max, (E ag.e). Then, for any constant E (0, 1/c,, the Perron matrix W = -3C could be obtained. The Perron matrix W [wr,yNxx a doubly random matrix and both the sum of elements and column elements in W is 1. In the multi-agent bandit setting, is widely used to solve the consensus problem Olfati-Saber et al. 2007
C Appendix Preliminaries of the problem
Lemma 2.
\Yan al.) 2012) For doubly random matrix W, it is irreducible, doubly stochastic matrix with strictly positive diagonal entries, then there exists positive constant C such that
N
1 1 + C.S. N
Σ j=1
(11)
where wi,, represents the element in the i-th row and j-th column of the matrix W ls represents the iteration step and X2 is the second largest value of matrix W. C equal to the graph G is balanced, otherwise, C = VN.
Lemma 3. MMolloy and Reed 2002 Assume that X(1) - 1 is independent, sub-Gaussian random
variable. Then for any e U,
n P( 2 u+ S exp(
20 )
ne²
P( S p 2 exp(
20
where jt Et X(t and is the sample count.
Lemma 4. (Lattimore and Szepesvári 2020 Suppose that X; of sub-Gaussian and X are all independent for [I,...,NN] N.. Then we have 1/2 DN X; is ΣN N sub-Gausiian
Lemma 5. (Dubhashi and Panconesi 2009 If random variable X has a finite mean and X S b almost surely, then X is [bb a)a nub-Gaussian.
D Appendix Missed proofs
D.1 Proof of Lemmali
Proof. The goal is obtain an unbiased estimation Pi,5 of the global mean μq, To achieve the goal, we could divide the problem into three parts: |pL, Mi,l, 1 fuyl and [ã, p4/- According to the triangle inequality, we have
m.
|05 25 I2T pal-
(12)
The first term |p introduced in Section 3.3
As.j is bounded according to the definition of information quantization We have
1
Ip - B.g
Tú 2
21

---

Since all agents make decisions synchronously, we remove the subseript j from the epoch number r.. The consensus process mainly acts at the end of each epoch; therefore, we consider the average reward { during the total epoch instead of the real-time reward x (t) in each time slot To facilitate matrix-based operations, we stack equation 5 as follows
i = (1 o.(r)) W P (x(r)
(13)
where ii and.X are defined as
x = ,",... X!,N'"
The coefficient (r(r) represents the ratio of the total amount of data aggregated by variable X to the overall data volume. The iteration of occurs at the end of each epoch r',, which implies that the sample count could be connected to epoch r. Hence, we define o;(r,) = +01r+)))) +ry2 where a is the pre-trained sample count at the beginning of the algorithm.
+1)
According to the state above, iterating 13
each epoch yields that
2
i ++2 W
+
X
r +
W 14g +
W - +akk+((x+
a(r 1)(rr 22
a(r + +r + 1)
(14)
k=1
(a)
W k a(k + 1)x;*
a(r + 2r 1)
k=
where equation (a) is obtained by setting p = X Then, separate agent j's global estimate from the vector i.. have
2 Fi a(r + 2) 11 k=0
of a(k 1)8
(15)
For the fully connected graph, each agent can observe all other agents' observations. Hence, their global estimates 2 on arm are the same, which is written as
2
pJ a(r + 2)(r 1)
(T)(T)
T=0
J=1
(16)
N a(k + 1)
2
a + (r 11)
k=
j=1
where equation (a) is obtained because the concentration accrues at the end of each epoch, i.c., t t= a + 22
The error between Hi and f is
2
1 MT a(r +1)(++2
)a(k + 1)X
33''
N
k=0/==1
CX2
CV- x k)
(r+1)(r + 2)
(17)
k=0
(3)
20
X X2
2C
X
(r + 1)(r
(1- X²)
(r 21 X2)
20
(1 (r)
22

---

where equation (a) yields from Lemma and equation (b) is derived based on the properties of arithmetic and geometric sequences.
For a federated setting with N agents, the global reward defined as Xx(1) = N Xt, where (1) E [0, 1] represents the local reward observed by agent j. According to Lemma 5 each (t) is 1
(t)
1 -sub-- Gaussian. By applying Lemma which addresses linear combinations of
sub-Gaussian variables, it follows that the global reward (t(t) is 4N -uuu-uuussian
log and o² Iv the probability that the estimate j 2Nr exceeds the confidence interval after round is given by
By using Lemma 3 and setting
logo-1 d-1
(i(t)) Mit
56
aN 1)(r + +2)
(18)
log 8-1
(A((t) S 14
aN(r 1)(r + 2) 1
i.e, with probability least 1 - 28, have
log 8-1
A n.l
(19)
aN 1)(r + 2)
Combining the upper bounds of the three terms, we obtain the following result based equation
(12)
logo-1
2C
1
mil aN(r +)
(1 - 11- + 22
r r
which is the radius of the confidence interval.
D.2 Proof of Theorem 1
Proof. To establish bounds on both regret and communication cost, the key step is to characterize the sample complexity of all agents. Hence, the proof is divided into three parts: (1) bounding the total number of samples collected by each agent, (2) deriving the corresponding regret bounds, and (3) analyzing the total communication cost.
Since Algorithm[[p embedded in each agent and executed in a similar representative agent Agent j usually distinguishes whether an arm suboptimal at the end of each epoch. Recall that for all arms i K. X )i*). A, > O. Agents learn the gap A, > 0 and continuously eliminate the arms i A; O. To accelerate the update of the candidate set Sy. detection is performed at the end of each epoch. Once suboptimal arm is identified through this detection, agent will add it into the elimination arm set 33 and later initiate communication phase that broadcasts the elimination set B, across the distributed system in waves.
Bound the sample counts:
manner, focus our analysis
Since that Kh, is to estimate (4,, the reward gap A; for each agent j E N is related to U. The gap between Kimos , and 3 is
(a)
20 Plmax, F4 2 A, 2U
(20)
where inequality (a) is because Miuns 2 1 2 pi. Ug, and F S #4 + Uf
Denote Ai.j,t as the event of agent j pulling arm i at the time slot t, then we have
P
A
Aija
= 1- -
21 Σ P((ALu)) 21 --NNNk
i.j.t
At the end of each epoch rj. we take detection for each arm in the candidate set SJ. The corresponding sample count is equal to T.j a(r, + 1)(r, + 2)/2. Equation 20) is written
as
log 5-1
SC 4 1-1a
A < 400 S VV aNir + 1)(r 2)
+
T3 + 2
23

---

i.e.,
84,
+1)
16(
2C 1)2
16 16 0-1
4
+
X-X2
r+2
(r + 2)
aN + 1)(r + +
8(
I-12
20
+1)
1olog 8-1
(r+1)(r+2 +2-
4
a ?
4 4 0-1
8(
1-
2C + 1)
r
2+
VoNA,
A
According to the definition of the epoch label f; in equation
it follows that any suboptimal
Vlog8-1
81 8
arm will be added into the climination set BJ no later than the next epoch (Communication phase I).
In
VaNA.
A
4
8( 20
+1) + 1, agent will broadcast arm i to all neighbors
VaN
A.
As the number of time slots per epoch grows time, the number of epochs needed for information to propagate from a single agent to the entire network decreases accordingly. The maximum communication epoch required is determined by
mii
1)
(21)
where F represents the most epoch number. From the optimization problem (2 the epoch number is
most [
2D
to broadcast the message to all agents. In Algorithm the epoch for sampling
4 4vlog 6-1
22 +1)
suboptimal arm i is donated by
-2
VaNA.
A.
Bound the regrets: According to the basic regret decomposition identity, the individual regret in equation (1) of agent j could be written
T
(T( = Tup
E[X (()))())))) -T Σ (A,(1)
ad.(F: + 1) 2)
Σ
(T) Σ
x
2
#A,30
8AI30
aA; 4Vllg 8-1
2
+ +
VaNA.
:A,30
T
2d, 2a log T
ad.
NA:
VN
2
30
where
d, = 16C + 812
,, Xz)
According to the definition of group regret and the individual regret bound, equation 2 is written as
16 Tog
+ 2d, v 2aN log + aNd
R(T) = - RT(T) Σ
A;
2
1=1
:A:50
D.3
Proof of Theorem 2
Proof. The communication Algorithm I has two types, i.e., Communication phase and II. In Communication phase I, agents mainly share the indexes of sub-optimal arms and their corresponding

---

epoch label f.. In Communication phase II, agents mainly share differential information o about the global estimates.
Consider the size of each message: There are three types of information that need to be communi- cated in this setting: (a) the arm set Bjj. (b) the epoch label f. and (c) the global estimate 5.5- The message size for type (a) requires only Olog K) bits. For type (b), the size depends on the epoch label fs. which is upper bounded by Fi and can be encoded using O( Vlog 7') bits, as shown in the proof of Theorem 1 For type (c), the global estimate o lies in [0, 1] and is adaptively quantized. It is the most important part that needs to be optimized, as it dominates the total communication cost. The key challenge is to transmit the order of the global estimate from (log(T)) O())
After agent j computes the global estimate Pi at the end of epoch r, it will be transmitted into a more concise version H,,, with [1 + logg ryl ] bits. Then, the difference is calculated from 8 mi, = Hence, we could bound o to reduce the total communication cost. The difference ,i holds that
|0%,1 = |p - 135 = 1p4.5 - Pl. - A +
p +
Pi. - 1 (a)
(22)
1 +
1
S s |3ا + |ا | 1 M5
+
where equation (a) yields from the quantization process in Algorithm 2 Due to that mi contains [1 + loga ryl bits, which implies that there a quantization error at most 1/r, compared with the true estimate value Fi.. For the term |p45 - A455 |. we have
Mh ".. I = 1 127- P5,5""
+ i0g + pig 11 '1
W 11% - 17 + 114.5"
11, + 1i - P3
20
20
s (1 - X2)(1; + 2)
+
+ 1Rg - 1 %
(1 - (2) +
where
stry 1 1e6r 1)
2 11)
Ei=0 2
(1)
Ei=0 (t(
A p
a(ry + 1) + 2)/2
ary(t, + 1)/2
Due to that (t) is 1 Gaus-an random variable, Af p5-11 could be considered as
2/N
V ZaNiry + +2) Sub-Gaussian random variable.
Thus, we can further derive that, for a dummy variable Vln
a(r, a(r,+1)(r; x DI
x²
2
IP
< eexp
2aN(r; + 1)(r, 22
2 X AN
2 expp=222
which implies that
1
1
20
20
x²
P
18 >
rj
rj
(1 (r) +2)
+ 11-x2)(rg +1
*V
2aN(ry 2)2
< Dexpl-x²
2+
40
+
+ P
|8 >
1-12
V2aN
< 22expl=x2/2
r3 +2
(g) P
14 2 3 + log, r, + logg
2+ +C/C0(1 - x22) + x/V2oN
< 22expl_1221
ry +2
+ P [L1, > 3 + log, + 4C/(1 - X2) + x/ V vaNN)
3 22 22expl=>²
(
[14 33+ + 12g (2 4C/(1 - -A2) + x V2aN))
21 - 2 2expp /2),
25

---

where Diy in implication (a) represents the length of the truncated version [6%_] and it is bounded by
L + logg (1/16 DJJ - + log2 ryl.
(23)
Denote that = 3-+ 1o - A2) x NaN i.e., V2NN(21-33 could be written
2-11-x
) and (b)
P P S1) 2 2expl 2 exx
-aN(2'-3-
- -2
40
)
(24)
X2
With the above results and viewing Li random variable, we have that its cumulative distribution function (CDF) FLr, (1) satisfies the following property:
In
1I 2 i= 3 1ogz2 (2 4C/(1 (12)
x2)
2uN
4C
FEr, (1) 2exp -aN 2/-3
X2
Using the property of CDF, bound the expectation of
B|4, = Σ (1
FEi,(1)
1=0
$ 11+1+ i+
Σ
FL; (1))
(25)
1=|
40 27
<1+1+
2exp
-aN
21-3
dl
1=l
1 Ag
22+
Thus, we have that in expectation, the truncated version of [8% has length that is less than +- bits.
Consider the total number communication rounds in communication phase Communi- cation phase I is a novel phase, used to broadcast the indices of sub-optimal arms. When an arm is identified as sub-optimal, the arm index will be exchanged at most a(r+ a(ry + 1) rounds. The
total communication rounds on the arm is at most (K - 1) - 1)² +(r a(r, + 1) because agent jı may share the information with j2 even if the information from f2 initially. Considering N agents pulling K arms, the number broadcast round during the total horizon T in phase is at
most (K' - () - 1)2
o(r a(rr + 1).
D
Consider the total number of communication rounds in communication phase II. According to Theorem [] each suboptimal arm is pulled for at most F; epochs. the structure of Algorithm agents exchange their differential information 87, at the end of each epoch. Therefore, the total
number of communication rounds in Communication Phase II is upper bounded by N EK Ti-
According to the discussion above, the total communication cost of the entire system bounded by
K
C(T) < (2+
F, + (loge f, - logg -)(K-))(()))) 1) - 112 alr3 + +1)
a(r, +1)
1=1
(26)
$ 5 Σ NA Vl
#A:50
26

---

D.4 Proof of Theorem 3
Proof. We will present the proof of the lower bound in three parts.
Problem setting, First of all, we need to consider a more relaxed scenario. Consider a multi- agent system with N agents, which is fully connected graph. For each agent j. suppose that there is associated "replica" subsystem, j that can provide samples of agents {1 , NY \ (j)- When agent j samples i and obtains a reward Xi.j- replica subsystem provides rewards Xi,k, k E [1...., N) (i). This construction allows j to leverage peer observations without requiring global synchronization. In this construction, all agents in A could make different decisions. which means that the lower bound is compatible with all bandit algorithms.
Consensus estimation evaluation. Then, need to ensure the convergence of consensus estimation in this setting. In each round, the agents obtain not only the global estimates from their neighbors but also information from their replica subsystems. From the replica subsystem, agent could obtain global reward and denote it by X The concentration function for the fully connected graph is
Considering that Xi are all I-sub-Gaussian variables, the linear combination reward ji شه
/ - No and μ4 in this setting is
+ sub-Gaassiaan variable. By using Lemma 3
the relationship between jo
N
log 8-1
PP
M 2 14
8 $ 5,
log 5-1
P
P S 14
8N2T $
The confidence interval an additional factor 1 VN- Hence, the consensus estimation performance in this setting is better than that of general federated bandit settings. Hence, could derive more convincing lower bounds regrets.
V
log 5 processes better concentration performance than (6) because has 8N2,
Lower bound proof. Let M be set of distributions with finite means, and let μ MM + R be the function that maps E .M its mean. Let p4: E R and P E M have p(P) < pa and define
dę dit (P. pr M) inf (D(P, ((P)) > pr
P'EM
where D(P, P') is the relative entropy between P and P
Define two reward distributions follows
(PI.... P..... ... Pk).
v' = ===PP (PI....,PP P Pk).
Let all arms except arm i be the same in the two distributions. For arm i, let e be an arbitrary small value such that D(P,, P!) < de + and u(P,) > n4.
According to Lemma 15.1 in reference [Latimore and Szepesvári 2020), the divergence between and y/ is decomposed into
D(P,,Pu Pv)
Σ (T)) P.) El (T)) +c), k=1
where equation (a) is obtained based on D(P,, P3) = 0 +
According to Bretagnolle Huber inequality (Theorem 14.2 Lattimore and Szepesvári [2020)), ) for any event A, we have
1 (xp(-EEr,, + +c)
(A) + (A9) 2 (pp(-DPP,,,A. 2
2
27

---

Choose A = (T,s(T) > T/2], and let Rr (r v) and R.T- (T((A,))) Then
Pr + R4 2
(p((A) + P (49) -(-))
2
2
2
min(A., 14 p. (PP(())))))))))))))))){{)))))))) + PA)(
T
min min(Ar,14 p4) exp( E [T)) +))
Rearranging and taking the limit inferior leads to
minl A.. A. p4gn + +16
(T.s(())
log
lim inf T-000
lim inf
log T
dj +
T-000
log T
log RT + R4T)
(1
lim inf
d: +
700000
log T
d; +
where the last equality follows from the definition of consistency, which says that for any p > there exists constant Cp such that for sufficiently large T, Rr + Hy S CpTP, which implies that
log( Rr + FTy))
lim inf T-000
S.
log T
Considering p 0 was arbitrary and
0 limited zero, have
lim inf Bi (T))
2
T-000
log T
d,
In the proof of the lower bound regret, agents only the information from their replica subsystems and the reward mean is a _ VN -ubb-Gaussaa variable. According to Table 16.1 1 given in Lattimore and
Szepesvári 2020 we have d, .AA The individual regret of the problem lower bounded by
(T)
A,E(T,,(T)
inf T log T
2 inf
T-000
log T
d
NA,
&A,
AA,
The group lower regret is
R(T)
Σn j=1 (T)
A E Te. (T)
lim inf
lim inf T-000
lim
Σ
T
log
log T
7
log T
#A::00
A
j=1 1A:>0
:A:20
E Appendix Experiments on homogeneous settings
Under the conditions in Section some experiments are conducted in this section. Our algorithm (EpoInc-SE. also obtain similar result compared to the optimal homogeneous bandit algorithm in Figure
Appendix / Experiments on large-scale multi-agent systems
For large-scale deployments, the agent number N would play an important role in communication cost and regrets. order further verify the performance of our algorithm, we conducted an experiment involving 100 agents. The main results are shown in Figure The proposed algorithm (EpoInc-SE) also processes the advantage in communication cost, while can obtain near-optimal regret compared with other algorithms.
28

---

Gossip UCB
Dis-IJCB --A- Fad2-UCB
UCB-ICOM
FpoInc-SE works)
13
101
2014
140
12"
23000
$3300
5300
00000
200000
20000
40060
00030
100006
20030
40663
G006
0000
100603
Individual regret
(b) Group regret
(c) Communication
Figure 2: Performance in homogeneous settings.
Gossip UCB --X- Dis-UCB -- Ped2-UCB
UCB-TCOM
EpooIneSS((Our works)
Fate-iza Deeis DCt
3611
147
3.0
10
(a) Individual regret
(b) Group regret
(c) Communication cost
Figure 3: Performance in large-scale multi-agent systems.
G
Appendix / Limitations
Although algorithm has obtained near-optimal result, it still has certain limitations follows:
a The algorithm proposed in this work is the successive elimination algorithm, which relies on round-robin sampling. A similar result can not be introduced UCB-based algorithms, which are the mainstream algorithms in bandit problems.
For time-varee variant communication graphs, EpoInc-S would be not work because the con- sensus estimation part EBCES could not work in random graphs. This is because Lemma relies on a Markov Decision process, which needs a fixed graph.
In some practical distributed systems, information may unavailable or costly to obtain. For the first condition, the information is unavailable to some agents, which implies that the graph G is disconnected with a dique-cconnectd component. Then, agents cannot learn global estimates without bias because agents lack other agents' local observations. Thus. the regret would be linear !(T),, which has been discussed in reference [Xu and Klabjan [023). For the second condition, the communication cost cannot be upper-bounded because the cost of each message is unknown.
29


Reviews:
[{"review_id": "5NKbTATKlc", "reviewer": "Reviewer_Md65", "summary": "This paper addresses the Federated Multi-Armed Bandit (FMAB) problem in fully distributed networks with communication constraints. The main contribution is EpoInc-SE, a communication-efficient successive elimination algorithm that balances regret minimization with reduced bit-level communication. The algorithm incorporates (1) an epoch-based exploration strategy, (2) an adaptive differential communication scheme that transmits only quantized incremental updates, and (3) a consensus estimation routine to aggregate local statistics. Theoretically, the paper establishes tight upper and lower bounds on both individual and group regret, showing that EpoInc-SE achieves near-optimal performance. Empirically, it outperforms or matches baselines in regret while significantly reducing communication cost.", "questions": "1. Given my concerns regarding the novelty of the work, could you clarify the main technical challenges involved in proving the regret and communication upper bounds presented in Theorems 1 and 2?\n2. Additionally, in Theorem 3, what distinguishes your proof of the regret lower bounds from the arguments of a similar lower bound for the single-agent case in [1], which your approach seems to closely follow? What are the key technical hurdles specific to your setting?\n3. What are the main obstacles to establishing a lower bound for the communication cost? Do you believe the current upper bound of $O(\\sqrt{\\log T})$ is tight, or is there potential for further improvement?\n4. In Section 5, you mention incorporating a consensus estimation module into Fed2-UCB and UCB-TCOM, but the details are not elaborated. Could you provide more information on this?\n5. In lines 111–112, the global rewards are defined as sums over agents' local rewards, whereas the global means are defined as averages of the agents’ local means. Is this intentional?\n\n[1] 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": 3, "clarity": 2, "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 methods over existing baselines.\n- **Clarity:** The proposed algorithm and accompanying proof techniques are presented with intuitive explanations in the main text, and their effectiveness is validated through a basic experimental evaluation.\n- **Significance:** This work advances the state of the art by introducing a distributed algorithm for the heterogeneous FMAB setting with the lowest known communication cost, and with tight individual and group regret upper bounds. \n- **Originality:** Although the authors build on established techniques such as quantized communication [1], epoch-based communication [2] and successive elimination-based implicit synchronization [3], they employ them in a novel manner in the heterogeneous setting to achieve an algorithm with tight bounds and low communication cost. \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 primary concern with this work lies in its level of novelty. The contributions appear to be incremental, building upon established techniques in cooperative bandit literature—such as epoch-based communication [2], successive elimination with implicit synchronization [3], and running-consensus estimation [4]. That said, my current score reflects the view that this is a complete study in a new heterogeneous setting. It rigorously analyzes both group and individual regret under communication constraints, matches known lower bounds, and includes a basic experimental validation.\n- Implementing the proposed algorithm appears to require agents to have access to global properties of the communication graph, such as its diameter, the eigenvalues of the weight matrix, and whether the graph is balanced. This raises concerns regarding the practicality of the approach, particularly in fully distributed settings where such information may be unavailable or costly to obtain. These limitations should be explicitly discussed in the paper.\n- Furthermore, the analysis of the proposed algorithm relies heavily on implicit synchronization among agents when selecting arms. This dependence raises additional concerns about the algorithm’s applicability in more realistic settings, such as those involving unreliable communication or asynchronous decision-making. \n\nOther issues –\n- The authors highlight low communication cost as a key contribution of their work. However, it remains unclear whether the stated $O(\\sqrt{\\log T})$ bit complexity is optimal, as the paper does not provide a corresponding lower bound. Including such a bound or discussing the potential for further improvement would strengthen the contribution.\n- While the intuitive explanation of the algorithm in Section 3 is helpful, the use of numerous similar notations in this section makes the presentation difficult to follow. Additionally, Section 2 would benefit from revision to improve clarity.\n- Unfortunately, the main text does not include proof outlines for Theorems 1, 2, and 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- Additional proofreading would improve the paper. For example, the meaning of the parameter $a$ should be explained at its first appearance (line 196). In line 197, “epochs” should be used instead of “epoch.” Referring to the global estimator in line 203 before its formal definition is confusing and should be avoided. In equation (5), the quantized estimators of neighbors should be used instead of the true estimators, which are not available to individual agents. Line 260 describes a sample count bound, but Lemma 1 provides a concentration bound for the means. Lines 266–267 contain unnecessary repetition, and the reference to Section 3 in line 300 appears to be misplaced. Finally, in line 305, the notation “C” should be used instead of “c”.\n\n[1] Shi, Chengshuai, et al. \"Heterogeneous multi-player multi-armed bandits: Closing the gap and generalization.\" Advances in neural information processing systems 34 (2021): 22392-22404.\\\n[2] Wang, Yuanhao, et al. \"Distributed bandit learning: Near-optimal regret with efficient communication.\" arXiv preprint arXiv:1904.06309 (2019).\\\n[3] 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[4] Martínez-Rubio, David, Varun Kanade, and Patrick Rebeschini. \"Decentralized cooperative stochastic bandits.\" Advances in Neural Information Processing Systems 32 (2019).", "was_revised": true, "final_justification": "My comment to the AC details my reasoning for changing the score.", "rebuttal": "# On novelty and challenge\n>Q: My primary concern with this work lies in its level of novelty ....\n\nA: We sincerely appreciate your clear and succinct summary of our contribution. Our work is indeed built upon the three previously mentioned works. However, the existing results cannot be obtained through a mere aggregation of prior work without additional innovation. We highlight three novel contributions of our work: \n\n**(1) Adaptively Quantized communication for arm elimination:** The first novelty is that transmitting information precisely meets the requirement of arm elimination at the current moment. In the communication optimization problem, the most important challenge is to avoid the waste caused by the premature transmission of precise information. To handle the challenge, we design an adaptive difference communication policy to reduce the message size per round. \n\n**(2) Suitable epoch design for unbiased estimation:** The second novelty is to design a suitable epoch-based exploration policy that matches the consensus estimation policy, to estimate the global mean without bias. In the consensus estimation policy, the information from the current epoch typically needs to be integrated with historical information. Both excessively large and overly small epoch sizes can introduce bias in the consensus estimation policy. To ensure unbiased estimation, we adopt a novel epoch size to avoid excessive accumulation of sampling information within the current epoch.\n        \n**(3) Two-phase communication strategy for reducing time delay:** The third novelty is in designing two separate communication pathways to reduce the time delay caused by the fully distributed graph. For the general information (global estimates), it broadcasts at the end of the epoch. For urgent information (eliminated arms), immediate informing all agents is needed. Hence, we introduce the other communication phase to broadcast them, which reduces the time delay from $D$ epochs to one or two epochs.\n\n>Q: Given my concerns regarding the novelty of the work, could you clarify the main technical challenges involved in proving the regret and communication upper bounds presented in Theorems 1 and 2?\n\nA: Thank the reviewer for the comment. Our main technical challenge lies in how to reduce the number of communication bits, while maintaining a near-optimal regret performance. In the most recent prior work, the number of communication rounds was reduced to $O(\\log T)$. However, each of these communication rounds incurs a large number of bits cost, which can be as large as $O(T)$. While many sophisticated communication protocols proposed in the non-federated multi-agent bandits problems can be applied here to reduce both the number of communication rounds and the per-round bits, our problem setting is more challenging in three main aspects. \n\n(1) How to avoid transmitting useless information is one of the key challenges. In the process of the algorithm, the premature transmission of precise information is a waste of resources, which accounts for a major component of the communication cost. \n\n(2) How to avoid the biased estimation caused by the unreasonable epoch size. Both excessively large and overly small epoch sizes can introduce bias in the consensus estimation policy.\n\n(3) How to deal with the time delay is the third challenge. Time delay in epoch-based algorithms is fatal because the delay may occupy $O(\\log T)$ rounds. \n\n# On limitations\n>Q: Implementing the proposed algorithm appears to require ...\n\nA: We thank the reviewer for the insightful comment. While the lack of global property can make our algorithms invalid, obtaining this global information is usually inexpensive. \nGiven that the agents can communicate with each other and are aware of their local graph (e.g., their neighbors and their weights), a warm-up stage with merely several rounds (at most $N^2$) is enough for all agents to get the full global property. \n\nIn cases where the communication is unavailable or costly, this is a very different assumption from where our paper stands. It is an interesting work that we will research in the future. Meanwhile, we will add a limitation in Appendix / Limitations\n    \n “**F Appendix / Limitations**: In practical distributed systems, information may be unavailable or costly to obtain. (a) For the first condition, the information is unavailable to some agents, which implies that the graph $\\mathcal{G}$ is disconnected with a clique-connected component. Then, agents cannot learn global estimates without bias because agents lack other agents' local observations. Thus, the regret would be linear $\\Omega(T)$, which has been proposed in reference [2]. (b) For the second condition, the communication cost cannot be upper bounded because the cost of each message is unknown. ”\n\n>Q: Furthermore, the analysis of the proposed algorithm...\n\nA: Thank the reviewer for the comment. Synchronized communication is the core characteristic of the Successive Elimination algorithm, which has been used in works [1,3]. Hence, our work is common practice. We agree that they are intriguing directions. Nevertheless, they are out of the scope of this paper. There are also many asynchronous algorithms, such as UCB-based algorithms [4,5]. However, the existing algorithms cannot obtain a performance similar to this work, which has been listed in Table 1. Regarding unreliable communication, it can be considered that the information is unavailable, which has been discussed in weakness 2.  To solve the problem, we try to combine UCB with SE to reduce the influence of implicit communication. We will incorporate this direction into our discussion of future work.\n\n# On the communication cost\n>Q: The authors highlight low communication cost...\n\n>Q: What are the main obstacles to establishing...\n\nThank the reviewer for the valuable comments. There are some results on lower bounds of communication cost in homogeneous bandit problems [3], but heterogeneous and homogeneous are not the same. We will add a discussion after Theorem 2 as follows,\n\n\"**Remark 2**: The lower bound of the communication cost is still an important problem for heterogeneous bandit problems. There is previous work [6] that provides a constant level lower bound for the homogeneous bandit. However, the heterogeneous bandit setting poses a more challenging challenge, i.e., heterogeneous feedback, which implies that more essential communication is needed for a near-optimal algorithm. It is an interesting work that is worth learning. \"\n\n# On the proof\n>Q: Unfortunately, the main text does not include proof outlines...\n\nA: Thank the reviewer for the insightful suggestion. We will add the proof sketches in the latest version. Due to space limitations, we are unable to provide the full details here. However, a summary can be found in the subparts of the detailed proof section.\n\n>Q: Additionally, in Theorem 3, what distinguishes...\n\nA: While the lower bound proofs of our Theorem 3 and that in [7] both follow the standard three steps---(1) Construct the hard instances, (2) Devise a quantity to measure the difference/distance between the instances. (3) Use an asymptotic KL-divergence argument to prove the lower bound, the steps (1) and (2) in our federated bandit rely on different techniques from those of [1]. Step (1) carefully chooses the instances different for *each* agent, and Step (2) measures the concentration difference in terms of our consensus communication, both of which are different from [7]. \n\n# On definition\n>Q: In lines 111–112, the global rewards are defined\n\nA: We thank the reviewer for pointing out this confusion. Below, we clarify the definition of the global mean of each arm. We will introduce the setting from the following two angles. \n\n(1) Application: Since each agent can only observe local sampling information, it needs to aggregate information from all other agents to evaluate the overall performance of arms, which is also a key challenge in federated bandit learning. With the loss of a central server, enabling agents to collaboratively perform information collection and aggregation through distributed communication and identifying the optimal arm is the core contribution of this paper. This topic has strong practical significance in the medical field [8]. \n\n(2) Previous work: Both the definition of heterogeneity and the heterogeneous case are presented in many previous works, such as [4,5] and we follow the problem setting of them.\n\n# On clarity\n>Q: While the intuitive explanation of the...\n\n>Q: Additional proofreading would improve the paper...\n\nA: We appreciate the reviewer’s valuable feedback. For the explanation of symbols, we have proposed a detailed symbol table in Appendix A. To help with reading, we will add a refined table in Section 2. We will fix these typos in the latest revision.\n\n>Q: In Section 5, you mention incorporating a consensus estimation...\n\nA: Thank you for your correction. We have added a consensus estimation module to help them address the heterogeneity. We will add some details in the new version as follows\n\n\"For Fed2-UCB and UCB-TCOM, a consensus estimation module is attached to them to help them against heterogeneity. The two algorithms communicate the historical reward at each time slot. Hence, the consensus estimator is \n$\\hat{\\mu}\\_i(t)=\\frac{\\sum\\_{j=1}\\^N \\sum\\_{k=1}^t X\\_{i,j}(k)}{Nt}$.\"\n\n# References\n[1] Optimal algorithms for multiplayer multi-armed bandits\n\n[2] Regret lower bounds in multi-agent multi-armed bandit\n\n[3] Cooperative multi-agent bandits: Distributed algorithms with optimal individual regret and communication costs\n\n[4] Distributed multi-armed bandits\n\n[5] Decentralized randomly distributed multi-agent multi-armed bandit with heterogeneous rewards\n\n[6] Distributed bandit learning: Near-optimal regret with efficient communication\n\n[7] Bandit algorithms\n\n[8] Federated learning for healthcare: Systematic review and architecture proposal"}, {"review_id": "Bgu36pwVHi", "reviewer": "Reviewer_7iqF", "summary": "The authors consider the problem of cumulative regret minimization in decentralized heterogeneous federated bandits with non-complete communication graphs. Agents can only communicate with their neighbors on the graph and aim to find the optimal arm across agents while having access to potentially diverse local expected rewards. They propose an algorithm called EpoInc-SE which features several aspects: epoch-based increasing uniform sampling of arms, modulated communication with distinct phases depending on the type of transmitted information, computation of quantized estimates and transmission of differential estimates across neighbors to reduce the communication cost, and refined elimination criterion to take into account quantization and consensus estimation errors in addition to the standard concentration inequality. They show that their algorithmic contribution has an improved upper bound on both the individual and group regrets compared to the state-of-the-art in heterogeneous bandits and asymptotically matching the lower bound, while considerably reducing the communication cost. Finally, experiments are performed on synthetic data compared to the baselines in heterogeneous and homogeneous, centralized and decentralized bandits.", "questions": "- Can you discuss the importance and the source of the agents’ weights in the communication graph and its potential impact on the regret upper bounds? \n\nMinor concern: Ideally, the code should feature a README file to document which commands should be run for each figure in the paper.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths:**\n- Quality: The paper looks technically solid. The limitations mentioned in the paper make sense but should perhaps be featured in the main paper instead of the appendix.\n- Clarity: The paper is well-written, and its algorithmic and theoretical contributions are clear. \n- Significance: The proposed algorithm matches the lower bound for cumulative individual and group regret minimization (which the authors rederive), while considerably reducing the upper bound on the communication cost. These results seem confirmed by the experimental results in Section 5. In particular, this is the first algorithm for heterogeneous federated bandits matching those bounds.\n- Originality: The quantization and consensus algorithm for estimation are interesting, rather new contributions which required refined confidence bounds for the arm elimination procedure.\n\n**Weaknesses:**\n- Significance: The importance and the source of the agents’ weights in the communication graph is difficult to assess. Reading the appendix (Section B), it seems that this matrix is roughly fixed, up to a parameter $\\beta$ which exact value in practice is unspecified. I think this information should be present in the main text.", "was_revised": true, "final_justification": "The part about the communication graph is solved in the rebuttal to Md65 and myself I think. Albeit it is a strong assumption in practice, similar assumptions are present in the literature, so I think the paper's theoretical work is still worthwhile. Combining the three aspects (epoch-based increasing uniform sampling of arms, modulated communication, computation of quantized estimates and transmission of differential estimates, refined elimination criterion) does not seem straightforward, so I would think that the significance of the work is good enough, and possibly usable in related problems.\n\nThere are indeed some presentation issues as highlighted by Ftja, but they seem solvable within the camera-ready deadline. The paper still brings an interesting contribution to the topic with solid technical elements, so I would lean towards acceptance.", "rebuttal": "# On graph\n\n>Q: Significance: The importance and the source of the agents’ weights in the communication graph is difficult to assess. Reading the appendix (Section B), it seems that this matrix is roughly fixed, up to a parameter $\\beta$ which exact value in practice is unspecified. I think this information should be present in the main text.\n\nA: Thank the reviewer for the insightful suggestion. We will add the definition of $W$ and $\\beta$ in Line 104, Section 2. The concrete content is as follows\n\n\"The definition of $W$ is $W=I−\\beta\\mathcal{L}$, where $\\mathcal{L}$ is the Laplacian matrix and $\\beta\\in(0, 1/N]$ is the coefficient that reflects whether this agent believes its neighbors. If $\\beta=0$, we have $W=I$, which means that the agent itself occupies all the weight. If$\\beta=1/N$, it indicates that the agent assigns equal trust to all of its neighbors.\"\n\n>Q: Can you discuss the importance and the source of the agents’ weights in the communication graph and its potential impact on the regret upper bounds?\n\nA: Thank the reviewer for the comment. The agent weights determine how each agent integrates information from its neighbors. The weights between agents determine the connectivity of information flow, which in turn affects the convergence of the consensus estimation. Higher weights accelerate the spread of local observations or estimates across the network.  Properly balanced weights help ensure all agents converge to a common estimate or belief. The details have been written in Appendix B. \n\nThe weight matrix influences the convergence of consensus estimation, which could lead to additional constant-level regret because more sample counts are needed. The details of regrets are shown in the proof of Theorem 1.\n\n# On README\n\n>Q: Minor concern: Ideally, the code should feature a README file to document which commands should be run for each figure in the paper.\n\nA: Thank you for your suggestion. We will add a README file in the new version to explain how to run each figure in this paper."}, {"review_id": "RY7svSLfvv", "reviewer": "Reviewer_3qLe", "summary": "This paper addresses the Federated Multi-Armed Bandit (FMAB) problem. Under this problem setting, multiple agents aim to minimize cumulative regret while constrained by limited communication cost and privacy restrictions. In contrast to centralized bandit models, FMAB agents operate in a decentralized network, communicating only with neighbors, which makes effective coordination challenging. The paper proposes a new algorithm, EpoInc-SE (Incremental Epoch-based Successive Elimination), which is designed to balance communication cost with learning performance by incorporating early arm elimination, epoch-based exploration, and a quantized, differentially transmitted statistics mechanism. The paper shows that the algorithm achieves near-optimal regret both at the group and individual levels, and matches the theoretical lower bounds on regret in heterogeneous federated settings. EpoInc-SE is the first method to consider communication bit cost in such settings, introducing a two-phase communication strategy to prioritize important information and reduce overhead. Additionally, the authors propose a consensus estimator subroutine (EBCES) that allows agents to estimate global arm rewards accurately under distributed communication constraints. Theoretical analysis and empirical evaluations show the algorithm’s effectiveness, demonstrating good performance in both regret minimization and communication efficiency compared to existing approaches.", "questions": "1. What is the notable technical challenge in the theoretical analysis of the upper and/or lower bounds?\n\n2. The experiments are run on a small network (i.e., 8 agents). Any comment on how communication and regret behave in more realistic, large-scale deployments?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\n**Quality**\n\nThe paper has a fine quality. The proposed algorithm, EpoInc-SE, is well-motivated and specifically designed to deal with the communication efficiency in federated bandit. The theoretical analysis covers both regret upper and lower bounds, and shows that the algorithm is near-optimal. \n\n**Clarity**\n\nThe paper is largely well-structured. On the theoretical part, mathematical concepts and definitions are well introduced. Section 3 presents a good introduction of the propose algorithm. \n\n**Significance**\n\nThe work addresses a meaningful and increasingly important problem—efficient distributed learning in the presence of communication constraints and heterogeneity. Federated bandit and distributed decision-making is an important research topic and applicable to various areas such as finance and network optimization. The paper's theoretical contribution is a good one. The practical implications of reducing communication to O(1) bits per message while preserving regret performance are substantial.\n\n**Originality**\n\nThe paper introduces several novel elements. It is, to the authors’ knowledge, the first to optimize bit-level communication in heterogeneous FMAB settings and to propose a lower bound on regret that explicitly incorporates agent heterogeneity. \n\n**Weaknesses**\n\n**Lack of Novel Analysis Techniques**\n\nThe theoretical analysis relies entirely on standard techniques like Hoeffding’s inequality, spectral graph theory, and existing lower bound arguments from prior work. It does not introduce new analytical tools or proof techniques. The regret decomposition into quantization, consensus, and concentration errors is standard, and the lower bounds are derived using known results in a relaxed model. For a theory-focused paper, this lack of technical novelty in the analysis is a notable weakness.\n\n**Minor Weakness**\n\nThe empirical evaluation is limited to synthetic experiments; performance on real-world federated datasets would make the results more compelling.", "was_revised": false, "final_justification": "", "rebuttal": "# On novelty \n\n>Q: The theoretical analysis relies entirely on standard techniques like Hoeffding’s inequality, spectral graph theory, and existing lower bound arguments from prior work. It does not introduce new analytical tools or proof techniques. The regret decomposition into quantization, consensus, and concentration errors is standard, and the lower bounds are derived using known results in a relaxed model. For a theory-focused paper, this lack of technical novelty in the analysis is a notable weakness.\n\nA:  Thank the reviewer for the comment. Our work is indeed built upon the three previously mentioned works. However, the existing results cannot be obtained through a mere aggregation of prior work without additional innovation. We highlight three novel contributions of our work: \n\n**Adaptively Quantized communication for arm elimination:** The first novelty is that transmitting information precisely meets the requirement of arm elimination at the current moment. In the communication optimization problem, the most important challenge is to avoid the waste caused by the premature transmission of precise information. To handle the challenge, we design an adaptive difference communication policy (Section 3.3) to reduce the message size per round. \n\n**Suitable epoch design for unbiased estimation:** The second novelty is to design a suitable epoch-based exploration policy that matches the consensus estimation policy, so as to estimate the global mean without bias. In the consensus estimation policy (Section 3.4), the information from the current epoch typically needs to be integrated with historical information. Both excessively large and overly small epoch sizes can introduce bias in the consensus estimation policy. To avoid the biased consensus estimation, we adopt an accumulative epoch size instead of the traditional binary epoch size to avoid excessive accumulation of sampling information within the current epoch.\n        \n**Two-phase communication strategy for reducing time delay:** The third novelty is in designing two separate communication pathways to reduce the time delay caused by the fully distributed graph. For the general information (global estimates), it broadcasts at the end of the epoch. For the urgent information (eliminated arms), we need to immediately inform all the agents. Hence, we introduce the other communication phase to broadcast them, which reduces the time delay from $D$ epochs to one or two epochs.\n\nFor the lower bound proof, while the lower bound proofs of our Theorem 3 and that in [1] both follow the standard three steps---(1) Construct the hard instances, (2) Devise a quantity to measure the difference/distance between the instances. (3) Use an asymptotic KL-divergence argument to prove the lower bound; the steps (1) and (2) in our federated bandit rely on different techniques from those of [1]. Step (1) carefully chooses the instances different for *each* agent, and Step (2) measures the concentration difference in terms of our consensus communication, both of which are different from [1]. \n\n# On experiment\n\n>Q: The empirical evaluation is limited to synthetic experiments; performance on real-world federated datasets would make the results more compelling.\n\nA: Thank the reviewer for the valuable comment. We will add real-world federated datasets in the latest version.\n\n>Q: The experiments are run on a small network (i.e., 8 agents). Any comment on how communication and regret behave in more realistic, large-scale deployments?\n\nA: Thank you for your review. For large-scale deployments, the agent number $N$ would play an important role in communication cost and the individual regret. In order to further verify the performance of our algorithm, we conducted an experiment involving 100 agents. Due to the limitations of the format, we present the performance results of the three algorithms in the large-scale multi-agent system in the form of a table here. From the table, we can learn that our algorithm consumes the least resources and obtains a near-optimal result. \n\n| Name   |  Individual regret     | Group regret   | Communication cost | \n|:--------|:------------:|---------:|---------:|\n| Fed2-UCB   | $10^4 $    | $10^6 $  | $ 10^9 $ |\n| Dis-UCB  | $10^6$     | $10^8 $   |  $10^8$  |\n| EpoInc-SE  | $10^5 $    | $10^7$    |  $10^6$  |\n\n\n\n\n# Reference\n\n[1] Lattimore, Tor, and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020."}, {"review_id": "a8mnGjhK3s", "reviewer": "Reviewer_Ftja", "summary": "This paper studies the federated multi-armed bandit (FMAB) problem where N agents connected via a communication graph collaborate to identify the optimal arm while minimizing communication costs. The paper focuses on the heterogeneous setting where local reward distributions differ across agents. The main contribution is EpoInc-SE (Incremental Epoch-based Successive Elimination), an algorithm that combines epoch-based exploration, two-phase communication, and adaptive differential encoding to achieve near-optimal regret bounds while reducing communication to $O(\\sqrt{log T})$ total bits with $O(1)$ bits per message in expectation. The authors provide both upper and lower bounds for individual and group regret, claiming their algorithm is near-optimal.", "questions": "1. what is the computational complexity?\n2. what are the implications of these different communication schemes on privacy?\n3. What is the worst-case number of bits required per message?", "limitations": "Yes, they provided discussions to some limitations. More on computational complexity and privacy implications should also be discussed", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 1, "significance": 2, "originality": 3, "strengths_and_weaknesses": "# Strengths:\n\n- The paper addresses a practically relevant setting combining federated learning with communication efficiency, which is crucial for distributed systems with bandwidth constraints.\n- The adaptive differential encoding technique that reduces message size from $O(\\sqrt{log T})$ to $O(1)$ bits (in expectation) is creative and represents a genuine technical contribution to the federated bandits literature, to the best of my knowledge.\n- The separation of urgent information (arm elimination) from routine updates (estimates) is an elegant design principle that balances latency and efficiency.\n\n# weakness\n\n1. The paper could benefit from a clearer articulation of the precise problem it aims to solve. Currently, it addresses multiple aspects—communication efficiency, heterogeneity handling, optimal regret, and consensus estimation—without clearly identifying which is the primary contribution versus supporting components. This scattered presentation makes it challenging to evaluate the paper’s specific goals and their contribution to the existing literature. To strengthen the work, the authors are encouraged to explicitly state the primary problem, separate necessary technical elements from the key scholarly advancements, and include a comparison of communication costs with prior methods to highlight the approach’s improvements.\n2. in lines 40-42, Srikant & Ying study service‐fairness in queueing networks—not learning agents’ regret—so the citation is a domain mismatch. And the statement itself is not rigorous as \"fairness\" has been formalized in several distinct ways in the bandits literature.\n3. The O(1) bit communication claim is only in expectation, not worst-case, which is not clearly stated in the main results.\n4. The lower bound proof uses \"replica subsystems\" that fundamentally change the problem by giving each agent access to N times more information, making the comparison invalid.\n5. Experiments only use synthetic data with small problem instances (N=8, K=10). And there is no direct validation of the O(1) bit communication claim. The authors are encouraged to conduct ablation studies as the work involves multiple components.\n\nMinor\n\n- multiple grammar issues and typos (e.g., \"were\" vs “are” in line 50; \"with non-server\" in line 51; a space missing in line 52, etc.)", "was_revised": true, "final_justification": "After reading the rebuttal and other reviews, my overall assessment remains that the paper is not ready for acceptance in its current form. While the authors have made a commendable effort to clarify their contributions and address specific points (e.g., separating elimination/estimation communication, adding a worst-case bit count remark, acknowledging the fairness citation), the paper still needs major revision to both presentation and  technical content. In particular:\n- The manuscript needs a substantial rewrite to integrate the explanations provided in the rebuttal, improving both presentation clarity and the focus of the contributions.\n- The paper still mixes per-message $\\mathrm{O}(1)$ bits/message (in expectation), table-level $\\mathrm{O}(\\sqrt{ \\log \\mathrm{T})}$ vs. theorem-level $O\\left(\\sum_{i: \\Delta_i>0} \\sqrt{N} \\Delta_i^{-1} \\sqrt{\\log T}\\right)$. The worst-case bound now stated in the rebuttal is useful, but the paper still lacks a fully specified, reproducible message schema and unified metric. This undermines one of the main selling points, as also noted by Reviewer Md65.\n- Other tecchnical consistency issue (such as the global reward definition confusion noted by Reviewer Md65) also requires more careful polishing.\nGiven these points, my opinion remains unchanged, and I lean toward rejection in its current form.", "rebuttal": "# On contribution\n>Q: The paper could benefit from a clearer articulation of the precise problem it aims to solve. Currently, it addresses multiple aspects—communication efficiency, heterogeneity handling, optimal regret, and consensus estimation—without clearly identifying which is the primary contribution versus supporting components. This scattered presentation makes it challenging to evaluate the paper’s specific goals and their contribution to the existing literature. To strengthen the work, the authors are encouraged to explicitly state the primary problem, separate necessary technical elements from the key scholarly advancements, and include a comparison of communication costs with prior methods to highlight the approach’s improvements.\n\nA: Thank the reviewer for the comment. The core goal of this article is to optimize the communication cost while maintaining the near-optimal regret. The consensus estimation is to handle the heterogeneous feedback, and the optimal regret is an intermediate result. For the novelty, we list them as follows\n\n**(1) Adaptively Quantized communication for arm elimination:** The first novelty is that transmitting information precisely meets the requirement of arm elimination at the current moment. In the communication optimization problem, the most important challenge is to avoid the waste caused by the premature transmission of precise information. To handle the challenge, we design an adaptive difference communication policy to reduce the message size per round. \n\n**(2) Suitable epoch design for unbiased estimation:** The second novelty is to design a suitable epoch-based exploration policy that matches the consensus estimation policy, to estimate the global mean without bias. In the consensus estimation policy, the information from the current epoch typically needs to be integrated with historical information. Both excessively large and overly small epoch sizes can introduce bias in the consensus estimation policy. To ensure unbiased estimation, we adopt a novel epoch size to avoid excessive accumulation of sampling information within the current epoch.\n        \n**(3) Two-phase communication strategy for reducing time delay:** The third novelty is in designing two separate communication pathways to reduce the time delay caused by the fully distributed graph. For the general information (global estimates), it broadcasts at the end of the epoch. For urgent information (eliminated arms), immediate informing all agents is needed. Hence, we introduce the other communication phase to broadcast them, which reduces the time delay from $D$ epochs to one or two epochs.\n\nFor the lower bound, while the lower bound proofs of our Theorem 3 and that in [1] both follow the standard three steps---(1) Construct the hard instances, (2) Devise a quantity to measure the difference/distance between the instances. (3) Use an asymptotic KL-divergence argument to prove the lower bound, the steps (1) and (2) in our federated bandit rely on different techniques from those of [1]. Step (1) carefully chooses the instances different for *each* agent, and Step (2) measures the concentration difference in terms of our consensus communication, both of which are different from [1]. \n\n# On literature\n\n>Q: In lines 40-42, Srikant & Ying study service‐fairness in queueing networks—not learning agents’ regret—so the citation is a domain mismatch. And the statement itself is not rigorous as \"fairness\" has been formalized in several distinct ways in the bandits literature.\n\nA: Thank the reviewer for pointing out this issue. We mainly use the definition of max-min fairness in Section 2.1.1, but not the full book. Hence, we will modify our clarity of this part as follows\n        \n\"In network optimization literature [1], the max-min fairness metric—maximize the minimal individual reward—is widely used to measure a system’s fairness. \"\n\n# On communication cost\n\n>Q: The $O(1)$ bit communication claim is only in expectation, not worst-case, which is not clearly stated in the main results.\n\n>Q: What is the worst-case number of bits required per message?\n\nA: Thank the reviewer for the insightful suggestion. We will add a remark after Theorem 2 to explain the bits consumed at each time slot as follows\n\n\"**Remark 3**: In the worst case, the message in the communication phase I will consume at most $KN(2+\\hat{l})$ bits. In the communication phase II, the message will consume at most $K\\log K+K\\log\\log T$ bits.\"\n\n>Q: Experiments only use synthetic data with small problem instances (N=8, K=10). And there is no direct validation of the $O(1)$ bit communication claim. The authors are encouraged to conduct ablation studies as the work involves multiple components.\n\nA: Thank the reviewer for the comment. We have added the experiment on large-scale multi-agent systems. The result is shown in the following table, which is in line with our theoretical proof. For the ablation studies, we will add them in the latest version.\n\n| Name   |  Individual regret     | Group regret   | Communication cost | \n|:--------|:------------:|---------:|---------:|\n| Fed2-UCB   | $10^4$     | $10^6 $   |  $10^9$  |\n| Dis-UCB  | $10^6$     | $10^8$    |  $10^8$  |\n| EpoInc-SE  | $10^5$     | $10^7$    |  $10^6$  |\n\n# On the proof of the lower bound \n\n>Q: The lower bound proof uses \"replica subsystems\" that fundamentally change the problem by giving each agent access to N times more information, making the comparison invalid.\n\nA: Thank the reviewer for the comment. In Theorem 3, we are focused on searching for a lower bound. More information gives each agent access to N times more information, and the lower bound of this problem will be lower than that of the original problem. To find the lower bound of the original problem is different, while we can consider the new problem's lower bound as the lower bound of our problem. \n\n# On computational complexity\n\n>Q: What is the computational complexity?\n\nA: Thank the reviewer for the valuable comment. The computational complexity of our algorithm is $O(\\log TN^2K)$. \n\n# On privacy\n\n>Q: What are the implications of these different communication schemes on privacy?\n\nA: Thank the reviewer for the comment. The privacy of users is protected in our algorithm because we only transmit the differential quantization value of the global estimates, while the practical rewards $X_{i,j}(t)$ are not transformed, which greatly protects the privacy of statistics. However, in some algorithms, the reward  $X_{i,j}(t)$ is directly transmitted between agents, which is easily attacked. \n\n# On writing\n\n>Q: Multiple grammar issues and typos (e.g., \"were\" vs “are” in line 50; \"with non-server\" in line 51; a space missing in line 52, etc.)\n\nA: Thank the reviewer for the correction. We will fix the typo in the latest revision. \n\n\n# Reference\n\n[1] Rayadurgam Srikant and Lei Ying. Communication networks: An optimization, control and stochastic networks perspective. Cambridge University Press, 2014."}]

Author rebuttal:

Meta-review: This paper studies the federated bandit problem considering the communication cost between agents. A phased algorithm is proposed with its guarantees on the regret and the communication bits.

For this paper various aspects are discussed between the reviewers from the clarity of the presentation to the required knowledge of the communication graph and the novelty of the communication strategy. After examining these materials, I determined to recommend acceptance considering the novelty of the new communication strategy. Though the concern on the presentation still remains, the reviewers mostly came to the opinion that it is manageable within the revision toward the final version. I agree with this opinion and expect that the author thoroughly address the presentation issues as well as other concerns raised by the reviewers in the camera-ready version.

My own minor concern is the motivation for the individual/group regret. As far as I understand, the individual regret corresponds to a hypothetical reward if the all agents would have pulled the same arm. Then, the total group rewards over agents by pulling $i^{\star}$ is no better than pulling the best arm $\arg \max_i \mu_{i,j}$ for each agent, and similarly the actual reward of each agent by pulling $i^{\star}$ is no better than pulling the best arm for each agent. I believe that this point is already well-discussed in the literature and the idea of this paper also applies to other federated settings, but I would expect that this point is discussed within the paper in more details.
Decision: Accept (poster)