Decentralized Randomly Distributed Multi-agent Multi-armed Bandit with Heterogeneous Rewards
Authors: Mengfan Xu
Diego Klabjan
Venue: NeurIPS 2023 spotlight (2023)
Keywords: decentralized multi-agent MAB
heterogeneous light-tailed and heavy-tailed rewards
time dependent random graphs

Abstract: We study a decentralized multi-agent multi-armed bandit problem in which multiple clients are connected by time dependent random graphs provided by an environment. The reward distributions of each arm vary across clients and rewards are generated independently over time by an environment based on distributions that include both sub-exponential and sub-gaussian distributions. Each client pulls an arm and communicates with neighbors based on the graph provided by the environment. The goal is to minimize the overall regret of the entire system through collaborations. To this end, we introduce a novel algorithmic framework, which first provides robust simulation methods for generating random graphs using rapidly mixing markov chains or the random graph model, and then combines an averaging-based consensus approach with a newly proposed weighting technique and the upper confidence bound to deliver a UCB-type solution. Our algorithms account for the randomness in the graphs, removing the conventional doubly stochasticity assumption, and only require the knowledge of the number of clients at initialization. We derive optimal instance-dependent regret upper bounds of order $\log{T}$ in both sub-gaussian and sub-exponential environments, and a nearly optimal instance-free regret upper bound of order $\sqrt{T}\log T$ up to a $\log T$ factor. Importantly, our regret bounds hold with high probability and capture graph randomness, whereas prior works consider expected regret under assumptions and require more stringent reward distributions.

Decentralized Randomly Distributed Multi-agent Multi-armed Bandit with Heterogeneous Rewards
Mengfan Xu'
Diego Klabjan'
Department of Industrial Engineering and Management Sciences, Northwestern University edu
MengfanXu20230u.
nowthwestern. oorerreeee...t...tteeeeeerer..
edu, d-klabjan@horthweestao
Abstract
We study a decentralized multi-agent multi-armed bandit problem in which mul- tiple clients are connected by time dependent random graphs provided by an environment. The reward distributions of each arm vary across clients and rewards are generated independently over time by environment based on distributions that include both sub-exponential and sub- Gab-Gaassian distributions. Each client pulls an arm and communicates with neighbors based on the graph provided by the environment. The goal is to minimize the overall regret the entire system through collaborations. To this end, we introduce novel algorithmic framework, which first provides robust simulation methods for generating random graphs using rapidly mixing Markov chains the random graph model, and then combines averaging based consensus approach with a newly proposed weighting technique and the upper confidence bound to deliver UCB-type solution. Our algorithms account for the randomness in the graphs, removing the conventional doubly stochasticity assumption, and only require the knowledge of the number of clients at initialization. We derive optimal instance-dependent regret upper bounds of order log 7 in both sub-Gausee Gaussian and sub-exponential environments, and nearly optimal mean-gap independent regret upper bound of order vT log T up log factor. Importantly, our regret bounds hold with high probability and capture graph randomness, whereas prior works consider expected regret under assumptions and require more stringent reward distributions.
Introduction
Multi-armed Bandit (MAB) Auer et al., 2002a b) is an online sequential decision- makinn process that balances exploration and exploitation while given partial information. In this process, a single player (agent, client) aims to maximize a cumulative reward or, equivalently, minimize the cumulative loss, known as regret, by pulling an arm and observing the reward of that arm at each time step. The two variants of MAB are adversarial and stochastic MAB, depending whether rewards chosen arbitrarily or follow a time-invariant distribution, respectively. Recently, motivated by the development of federated learning [McMahan al., 2017]. multi-agent stochastic multi-armed bandit has been drawing increasing attention (commonly referred to as multi-agent MAB). In this variant, multiple clients collaboratively work with multiple stochastic MABs to maximize the overall performance the entire system. Likewise, regret is an important performance measure, which is the difference between the cumulative reward of always pulling the global optimal arm by all clients and the actual cumulative reward gained by the clients at the end of the game, where global optimality is clients. Thereafter, the
defined with respect to the average expected reward values of arms question for each client to answer is essentially how to guarantee an optimal regret with limited observations arms and insufficient information of other clients. Assuming the existence of central server, also known as the controller, [Bistritz and Leshem [018 Zhu et al. 202 Huang et al., 2202 Mitra al., 2021] Réda al. 2022 Yan et al. 2022]. allow controller- framework where the controller integrates and distributes the inputs from and to clients, adequately addressing the challenge
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

posed by the lack of information of other clients. However, this centralization implicitly requires all clients to communicate with one another through the central server and may fail to include common networks with graph structures where clients perform only pair-wise communications within the neighborhoods on the given graphs. Non-complete graphs capture the reality of failed communication links. Removing the centralization assumption leads to decentralized multi-agent MAB problem, which is a challenging but attracting direction as it connects the bandit problem and graph theory, and precludes traditional centralized processing.
In the field of decentralized multi-agent MAB, it is commonly assumed that the mean reward value of an arm for different clients is the same, or equivalently, homogeneous. This assumption is encountered
in [Landgren et al. 2016a b 2021 Zhu et al. [2020] Martínez- et al. 2019 Agarwal et al.,
2022 Wang et al. 2022 2020 Li and Song 2022 Sankararaman et al.) 2019 Chawla et al. [020]. However, this assumption may not always hold in practical scenarios. In recent years, there has been an increasing emphasis on heterogeneous reward settings, where clients can retain different mean values for the rewards of the same arm. The transition to heterogeneous reward settings presents additional technical challenges. Clients are unable to infer the global optimal arms without sequential communications regarding the rewards of the same arm at other clients. Such communications, however, are limited by the partially observed rewards, as other clients may not pull the same arm, and constrained by the underlying graph structure. We study the heterogeneous setting with time varying graphs
Traditionally, rewards are assumed to be sub-Gaussian distributed. However, there has been recent focus on MAB with heavy-tailed reward distributions. This presents a non-trivial challenge as it is harder to concentrate reward observations in sublinear time compared the light-tailed counterpart [Tao et al. [002]]. In the work of (Jia et al. 202T). sub-exponential rewards are considered and analyzed in the single-aentt MAB setting with newly proposed upper confidence bounds. Meanwhile, for multi-agen MAB. heavy-tailed distributions are examined in a homogeneous setting in (Dubey et al. 2020]. However, the heterogeneous setting studied herein has not yet been formulated or analyzed, posing more challenges compared to the homogeneous setting, as discussed earlier.
Besides rewards, the underlying graph assumptions are essential to the decentralized multi-agent MAB problem, as increased communication among clients leads to better identification of global optimal arms and smaller regret. The existing works [Sankararaman et al.] 2019 Chawla et al. 2020) relate regret with graph structures and characterize the dependency of regret on the graph complexity with respect to conductance. When considering two special cases, [Chawla et al.) 2020 demonstrates the theoretical improvement achieved by circular ring graphs compared to complete graphs, and [Li and Song 2022) numerically shows that the circular ring graph presents the most challenging scenario with the largest regret, while the complete graph the simplest. There are two types of graphs from a time perspective: time-invariant graphs, which remain constant over time, and varying graphs, which depend on time steps and are more challenging but more general. Assumptions on tine-invrrian graphs include complete graphs [Wang et al.) 2021] where all clients can communicate, regular graphs (Jiang and Cheng, 2023] where each client has the same number of neighbors, and connected graphs under the doubly stochasticity assumption (Zuu et al. 2020 2021a b). Independently from our work, recent work (Zhu and Liu 2023) has focused on viry-ng B-connected graphs, where the composition of every I consecutive graphs is a strongly connected graph. However, their doubly stochasticity assumption, where all elements of edge probability also called weight matrices are uniformly bounded by positive constant, can be violated in several cases. Additionally, their graphs may be strongly correlated to meet the connectivity condition when I >> 1, which may not always hold in practice. No research has been conducted on time-varying graphs with only connectivity constraints or without constraints on connectivity. Additionally, current time-varying graphs do not provide insight into how the graphs change over time. As the graphs are generated by the environment, similar to the generation of rewards, it remained unexplored considering random graphs in an i.i.d manner, such as random edge failures or random realizations as et al. 2019 We also address this situation.
pointed out for future research in [Martinez-Rubiee
Traditionally, random graphs have often been formulated using the Erdös- Rényi (E-R) model, which has been widely adopted in various research domains. The model, described by G(M, c). consists of M vertices with each pair of vertices being connected with probability e. Notably, the E-R model is 1) not necessarily connected and 2) stochastic that allows for random edge failures, and has found applications in mean-field game [Delarue] 2017] and majority vote settings [Lima et al., 2008). Though it has only been used in numerical experiments for the decentralized multi-agent MAB
2

---

setting with homogeneous rewards (Dubey et al. 2020), the theoretical study of this model in this context remained unexplored until this work, let alone with heterogeneous rewards and time-varying graphs. Alternatively, one can consider all connected graphs (there are exponentially many of them), and the environment can randomly sample connected graph and produce i.i.d. samples of such random connected graphs. This approach mimics the behavior of stochastic rewards and allows the environment to exhaust the sample space of connected graphs independently, without the doubly stochasticity assumption, which, however, has not yet been studied and it is also addressed herein.
For the multi-agent MAB framework, methods in MAB are a natural extension. (Zhu et al. 202 adapt the UCB algorithm to the multi-agent setting. This algorithm uses weighted averages to achieve consensus among clients and is shown to have a regret of order log 7 for time-invariant graphs. A follow-up study in [Zhu and Liu, 2023] re-analyzes this algorithm for time-varying B-connected graphs under the aforementioned assumptions under the doubly stochasticity assumption by adding an additional term compared to UCB. An effective UCB-based method for random graphs without doubly stochasticity assumption and for sub-exponential distributed rewards remained unexplored.
This paper presents a novel contribution to the decentralized multi-agent MAB problem by studying both heterogencous rewards and time-vrryin random graphs, where the distributions of rewards and graphs are independent of time. To the best of our knowledge, this is the first work to consider this problem and to investigate it with heavy-tailed reward distributions. Specifically, the paper investigates 1) heterogeneous sub-exponential and sub-Gaussian distributed rewards and 2) random graphs including the possibly disconnected E-R model and random connected graphs, and applies them to the decentralized multi-agent MAB framework. This work bridges the gap between large- deviation theories for sub-exponential distributions and multi-agent MAB with heterogeneous rewards, and the gap between random graphs and decentralized multi-agent MAB.
To this end, we propose a brand new algorithmic framework consisting of three main components: graph generation, DrFed-UCB: burn-in period, and DrFed-UCB: learning period. For the learning period, we modify the algorithm by [Zhu et al. 2021b] by introducing new UCB quantities that are consistent with the conventional UCB algorithm and generalize to sub-exponential settings. We also introduce a newly proposed stopping time and a new weight matrix without the doubly stochasticity assumption to leverage more information in random graphs. A burn-in period is crucial in estimating the graph distribution and initializing the weight matrix. We embed and analyze techniques from random graphs since the number of connected graphs is exponentially large in the number of vertices, and directly sampling such a graph is an NP-hard problem. In particular, we use the Metropolis- Metroooois-Hasttings method with rapidly mixing Markov chains, as proposed in [Gray et al. 2019]. to approximately generate random connected graphs in polynomial time. We additionally demonstrate its theoretical convergence rate, making it feasible consider random connected graphs in the era of large-scale inference.
We present comprehensive analyses of the regret of the proposed algorithm, using the same regret definition as in existing literature. Firstly. we show that algorithm DrFed-UCB achieves optimal instance-dependent regret upper bounds of order log T with high probability, in both sub- nub-Gaussian and sub-exponential settings, consistent with prior works. We add that although both (Zhu et al., 2020) and our analyses use the UCB framework, the important algorithmic steps are different and thus also the analyses. Secondly, we demonstrate that with high probability, the regret is universally upper bounded by O(vT log T)) in sub-exponential settings, including sub- Gaussian settings. This upper bound matches the upper and lower bounds in single-agent settings up to a log T factor, establishing its tightness.
The paper is organized as follows. We first introduce the notations used throughout the paper, present the problem formulation, and propose algorithms for solving the problem. Following that, we provide theoretical results on the regret of the proposed algorithm in various settings.
Problem Formulation and Methodologies
2.1 Problem Formulation
Throughout, we consider decentralized system with M clients that are labeled as nodes 1,2,..., M on tire-ngrying network, which is described by an undirected graph G, for 1 S 1 S 7 where parameter T denotes the time horizon of the problem. Formally, at time step I, G. = (V, F.)) where V {1,2..... M) and E, denotes the edge set consisting of pair-wir wise nodes and representing the
3

---

neighborhood information in G₁. The neighbor set (t) include all neighbors of client m based on G, Equivalently, the graph G, can be represented by the adjacency matrix (Xx, (Xx,) 1 where the element X 1.j = 1 if there is an edge between clients and j and X = 0 otherwise. We let X1, = 1 for any 1 S S M. With this notation at hand, we define the empirical graph (adjacency matrix) Pa as P. Ei X X.NissusMM
It is worth emphasizing that 1) the matrix P. is not necessarily doubly stochastic, 2) the matrix captures more information about G, than the prior works based on (n.(()). and 3) each client only knows the m-th row of Pa without knowledge of G2, i... (m, f) are known to client m, while {Pa (k. J)ly for k + m are always unknown. Let us denote the set of all possible connected graphs on M nodes as GM.
I
We next consider the bandit problems faced by the clients. In the MAB setting, the environment generates rewards. Likewise, we again use the term, the environment, to represent the source of graphs G. and rewards rt"(t) (t) in the decentralized multi-agent MAB setting. Formally, there are K' arms faced by each client. At each time step for each client 1 S m S M, let the reward of arm S S K' be r?" (t), which is i.i.d. distributed across time with the mean value μr" and is drawn independently across the clients. Here consider heterogeneous setting where ju"" is not necessarily the same as ne for m + j. At each time step t, client m pulls an arm o only observes the reward of that arm r (t) from the environment, and exchanges information with neighbors in G2 given by the environment, In other words, two clients communicate only when there is an edge between them.
By taking the average over clients in the existing literature, we define the global reward of arm i at each time step t as ri (t) M Σm=1 r (t) and the subsequent expected value of the global reward as f4= Ad Em p. We define the global optimal arm as i" = arg max; Ps and arm * i" is called global sub-optimal. Let A, = μt- p4 be the sub-optimality gap. This enables us to quantify the regret of the action sequence (policy) t [1mmmmm M as follows. Ideally, clients would like to pull arm if knowledge of { were available. Given the partially observed rewards due to bandits (dimension i) and limited accesses to information from other clients (dimension m), the regret is defined RT Tu- M Et= E 1% which measures the difference of the cumulative expected reward between the global optimal arm and the action sequence. The main objective of this paper is to develop theoretically robust solutions to minimize Ry for clients operating on time-varying random graphs that are vulnerable to random communication failures, which only require knowledge of M.
2.2 Algorithms
In this section, we introduce a new algorithmic framework that incorporates two graph generation algorithms, one for the E-R model and the other for uniformly distributed connected graphs. More importantly, the framework includes UCB-varian algorithm that runs a learning period after a burn-in period, which is commonly referred to as a warm-up phase in statistical procedures.
2.2.1 Graph Generation
We investigate two types of graph dynamics as follows, for which we propose simulation methods that enable us to generate and analyze the resulting random graphs.
E-R random graphs At each time step t, the adjacency matrix of graph G, is generated by the environment by element-wise sampling X1, according to Bernoulli distribution. Specifically, X follows Bernoulli distribution with parameter c.
Uniformly distributed connected graphs At each time step I, the random graph G, is generated by the environment by uniformly sampling a graph from the sample space of all connected graphs GM. which yields the adjacency matrix (X²,) (Xi,)isi M corresponding to G,. Generating uniformly distributed connected graphs is presented in Algorithm 3 as in Appendix. It is computationally infeasible to exhaust the sample space Gas since the number of connected graphs is exponentially large. To this end, we import the Metropolis-Hastingg method in (Gray et al., 2019) and leverage rapidly mixing Markov chains. Remarkably, by adapting the algorithm into our setting which yields a new algorithm, we construct a Markov chain that converges to the target distribution after a finite number of burn-in steps. This essentially traverses graphs in Gar through step-wise transitions, with a complexity of O(M²) from previous states. More precisely, at time step s with connected graph G., we randomly choose a pair of nodes and check whether it exists in the edge set. If this is the case,

---

remove the edge from G, and check whether the remaining graph is connected, and only accept the graph as G.+1 1 in the connected case. If the edge does not exist in the edge set, we add it to G2 and get
Gs+1- In this setting, let cM) be the number of times an edge is present among all connected
graphs divided by the total number of connected graphs. It is known that 2 M-T M (1) [Tevisan]
The distribution of G2 eventually converges to the uniform distribution in Gas. The formal statements are Appendix.
2.2.2 Main Algorithm
In the following, we present the proposed algorithm, DrFed-UCB, which comprises of a burn-in period and a learning period described in Algorithm and Algorithm respectively.
We start by introducing the variables used in the algorithm with respect to client m. We use i. (L), (t) to denote reward estimators and counters based on client m'' own pulls of arm i, respectively, and use "i"", (t) to denote reward estimators and counters based on the network- wide pulls of arm i, respectively. By network-wide we refer to the clients in Nm (t). Denote the stopping time for the filtration {G.]=== as h = mar,st (m,, E E it represents the most recent communication between clients m and J. The weights for the network-wide and local estimators are P/ (m. j) and dm, defined later, respectively.
There are two stages in Algorithm ! wheree i S I, follows. For the first T steps, the environment generates graphs based on one of the aforementioned graph generation algorithms to arrive at the steady state, while client m pulls arms randomly and updates local estimators {,7T" m, J. Afterwards. the environment generates the graph G2 that follows the distribution of interest, while client m updates {nETh nn 3s and row m of P. by exchanging information with its neighbors in the graph G,- Note that client m does not have any global information about Gt. At the end of the burn-in period, client m computes the network wide estimator 2:Th by taking the weighted average of local estimators of other clients (including itself), where the weights are given by the m-th row of weight matrix P' and d, which depend on P and knowledge of M and satisfy Σ P.(m, j) + dm,, M 1.
Subsequently, we describe Algorithm 2 where 1 2 ++ 1. There are four phases in one iteration enumerated below in the order indicated. A flowchart of this algorithm is provided in Appendix.
UCB Given the estimators ". (4), (l), (t,,(),, (t), client m either randomly samples an arm or pulls the arm that maximizes the upper confidence bound using 5T (L), i depending on whether ) (1) S (() - K holds for some arm i. This additional condition ensures consensus among clients regarding which arm to pull. The upper confidence bound F(m, i, t) is specified
as F(m, i, 1) v (t)
C. Int and F(m, i,() = v sub-exponential rewards, respectively. Constants C₁ and C2 are determined in the analyses and they depend on a which is an upper bound of standard deviations of the reward values (it is formally defined later).
C. ln + CaIn in settings with aub-Gaussian and (0,.(0) [f).s(f]
Environment and client interaction After client m pulls arm a the environment sends the reward ydt mm,a, and the neighbor set N,, mm (f) in G, to client m. Client m does not know the whole Ge and obtains only the neighbor set (t).
Transmission Client m sends the maintained local and nedwork-wide estimators (1eT (1), ()))(())))))))) (0.T((()) (1), ((), (t)} to all clients in Nm (t) and receives the ones from them.
Update estimators At the end of iteration, client m first updates the m-th row of matrix Pt. Subsequently, client m updates the quantities (7TT (t), (TT(() (t), (t,st), ft), Nm.:(t))ssss adhereing to: tm.j max.2n {(m, j) E.)} and 0 if such does not exist
(t 1) (t) + 1. =i, st + 1) = max (t + 1), Ng E (t)
(2)
M-1 a.Th (L + 1)= (t) mm. (0) (t) (t)- Dat P P(( = 3ot
if P. j) > and O otherwise
(t)
(1 + 1) = -EM (((m, Der (mm)) + dmn,t EjeN...0) Prryy (1) + dm,, Esen... dng (bmm)
with dm,t- = -11-EA Ene Pl(m, J))MM
Similar to (hhu et al. 2021b Zhu and Liu 2023 J. the algorithm balances between exploration and exploitation by the upper confidence bound and a criterion on n (L) and (!) that ensures that all clients explore arms at similar rates and thereby "staying on the same page." After interacting
5

---

Algorithm 1: DrFed-UCB: Burn-in period
Initialization: The length of the burn-in period is I. and also given Ti L,; In the time
step t= 0, the estimates are initialized as p (0) = 0, m0, = 0, P (0) = 0, and
Po(m.j) = for any arm and clients m,
for 1 S S TI do
The environment generates a sample graph G+ (V, Ex) based on either E-R or Algorithm
end
for 1 S S do
for each client m do
Sample arm a,"h = (t mod K);
Receive reward az (t) and update (1) Dmm, - 1) + 1 L =
nm., itt 1), (t- (t)
Update the local estimate for any arm p. (t)
end
end
for
<ts L do
The environment generates a sample graph G2 = (V, Ex) based on either E-R or Algorithm 3 for each client m do
Sample arm a, - mod K);
Receive rewards a.. (1) and update (m,,(()) (1) il 1) 1
Update the local estimates for any arm i: p3 (t) Am. 1)p (t- 12 1am
am aaa
Update the maintained matrix Pr(m, j) (t-1)Pt 1 (mmj)+XX my for each j E EV;
Send {atT [=) K to all clients in Nm(t):
Receive (t) from all clients j Nm and store them as poy (t).
end end
for each client m. and arm i do
For client S j S M, set h (m, j) = max.2n ((m, E E.} or if such s does not exist
1. if (m,,, > 0
(I. + 1) = Σme Pin. (T) (bim,)) where Pmg (b.
M
x
0
otherwise
end
with the environment, clients move to the transmission stage, where they share information with the neighbors on GG, as preparation for the update stage.
Different from the upper confidence bound approach in [huu and Liu 2023 which has an extra term of? } in the UCB criterion, proposal is aligned with the conventional UCB algorithm. Meanwhile, our update rule differs from that in (Zhu et al., 2021b Zhu and Liu 2023 in three key aspects: (1) maintaining stopping time tm. that tracks the most recent communication to client j. and (2) updating i based on both ji and şo! for j Nm (t), and (3) using a weight matrix based on P and Pt computed from the trajectory [G. in the previous steps. The first point ensures that the latest information from other clients is leveraged, in case there is no communication the current time step. The second point ensures proper integration of both network-wide and local information, smoothing out biases from local estimators and reducing variances through averaging. The third point distills the information carried by the time-varying graphs and determines the weights of the available local and network-wiid wide estimators, removing the need for the doubly stochasticity assumption. The algorithm assumes that the clients know M and o²
We note that tm. is the stopping time by definition and that प is an unbiased estimator for μQ"" with a decaying variance proxy. Meanwhile, the matrices P/ and P, are not doubly stochastic and keep track of the history of the random graphs. By introducing tm and Pt, global estimator j. (1) behaves similarly to hab--auusiannsu--xpoonnttt random variable with an expectation μu; and a time-decaying variance proxy proportional to min, (f) This ensures that the concentration inequality holds for (t) with respect to μ4 and that client m tends to identify the
show that the

---

Algorithm 2: DrFed-UCB: Learning period
Initialization: For each client m and arm {1, ..... K), we have 12," + 1), Nm. (L. + Rmm,i (L); all other values at I. + 1 are initialized as 0; for 1, 1. 2....+2..... ....., do
for each client do there no arm i such that nm, S (t, - then o' agg max; (t, + ((m,i,t) i,
// UCB
else
Randomly sample arm am
end
Pull arm in and receive reward I'm mm, (t);
end
The environment generates sample graph G. (V, Ex)
based on E-R or Algorithm
// Env
Rach client sends p. (1), (4) (()))))()((()))))))))))))))) (1), (1) to each client in Nt):;);
Each client m receives μud (t), (t), (t), from all clients j E No (t) and stores
them P (t), NT, (t), P (t), (t);
// Transmission
for each client m do for 1,....
Update P. for S j by Pr(m, (t- P-- (mm.))) X
Update Pt for 1 S S M by (m(,, {I if Pm
if Pm.. j) =
Update (t), (t,, and 3 (t) based equations (2)
end end
end
global optimal arms with high probability, which plays important role in minimizing regret. The formal statements are presented in the next section.
Regret Analyses
In this section, we show the theoretical guarantees of the proposed algorithm, assuming mild conditions on the environment. Specifically, we consider various settings with different model assumptions. We prove that the regret of Algorithm Saarthm@@an has different instance- instance-dependen upper bounds of order log for settings with Gab-Ganssinn and sub-exponential distributed rewards, and mean- gap independent upper bound of order vT log T across settings. Many researchers call such a bound instance independent but we believe such a terminology is misleading and thus we prefer to call it man-gap independent, given that still has dependency on parameters pertaining to the problem instance. The results are consistent with the regret bounds in prior works.
3.1 Model Assumptions
By definition, the environment is determined by how the graphs (E-R or uniform) and rewards are generated. For reward we consider two cases.
Sub-g At time step I, the reward of arm at client m has bounded support (0. 1]. and is drawn from
a Sab-Gaussian distribution with mean n < 1 and variance proxy 0 < (a.") m o².
Sub-e At time step I, the reward of arm i at client has bounded support [0. 1], and follows sub-exponential distribution with mean < 11 and parameters S (a 0² < a!" S a.
With these considerations, we investigate four different environments (settings) based on the two graph assumptions and the two reward assumptions: Setting 1.1 corresponds to E-R and Sub-g. Setting 1.2 to Uniform and Sub-g, Setting 2.1 to E-R and Sub-e, and Setting 2.2 to Uniform and Sub-e. For each setting, derive upper bounds on the regret in the next section.

---

3.2 Regret Analyses
In this section, we establish the regret bounds formally when clients adhere to Algorithm 2 in various settings. We denote Setting 1.1, Setting 1.2 with M < 11, and Setting 1.2 with M 2 11 as $1, 82 and 83. respectively. Likewise, we denote Setting 2.1, Setting 2.2 with M < 11, and Setting 2.2 with M 2 11 as S S2 and Sz, respectively. See Table I in Appendix for tabular view of the various settings.
Note that the randomness of Ri arises from both the reward and graph observations. Considering S1, S3 differ in the reward assumptions compared to $1, 82, 83. we define an event A that preserves the properties of the variables with respect to the random graphs. Given the length of the burn- in period L, for i E {81, 82, sa} and the fact that L.. = Ls, since it only relies on the graph assumptions, we use L to denote max; Lap. Parameters 0 < o,e <<> 1 are any constants, and the parameter c = c( represents the mean value of the Bernoulli distribution in 81, S] and the probability of edge in 82, S2, 83, and S3 among all connected graphs (see (T)) We define events A1 = (vt 2 L, I| - cElloc I 6}:A2 = {Eto, V 2 L, Vj. Vm, t + 1 miny tm S to S co miny (t + 1)3, and As {vt 2 L, G2 connected]. Here E is the matrix with all values of L. Constant co co (, min; A,. M, 6) is defined later. Since c c(M) this implies that G2 depends on M. We define A = AA,6 = A A₂ n Ag. which yields
E with E being the sub-o--la sub-o-algebra formed by {$2, 0, A, J. This implies El-[Ac,s] and P[-[Ac.]] are well-defines since A only relies on the graphs and removes the differences among $1, $2, 83 (S1, S2, Sz), enabling universal regret upper bounds.
Next, we demonstrate that event A holds with high probability.
Theorem 1. For event A, and any 1 >> e > O, we have P(Ac,6) 2 1 1-117 7e.
Proof Sketch. The complete proof is deferred to Appendix; we discuss the main logic here. The proof relies on bounding the probabilities of A1, A2, A3 separately. For A₁, its upper bound holds by the analysis of the mixing time of the Markov chain underlying G, and on the matrix-form Hoeffding inequality. We obtain an upper bound on P(A2) by analyzing the stopping time f and the counter (t). For the last term P(As), we show that the minimum degree of G, has a high probability lower bound that is sufficient for claiming the connectivity of G.. To put all together, we use the Bonferroni's 's inequality and reach the lower bound of P(A..5).
Subsequently, we have the following general upper bound on the regret Ry of Algorithm 2 in the high probability sense, which holds on A in any of the settings $1, 82, 83 with sub- Gaussian rewards.
Theorem 2. Let I be a function specific to a setting and detailed later. For every 0 < 6 and 0 < 8 < [(e, M,T), in setting 81 with e 2 1/2
( 82 and 83. with the time horizon T satisfying T 2 L, the regret of Algorithm 2 with F(m,i,t) = 1,2 + MK)} 3P(A,))
1/V1
lnt
satisfies that ElRT| Ar, S L ++ Eitr {[ 1C loe
2n²
K² (2M 1)K) O(I where the length of the burn-in period is explicitly L. K Kin MF
T In 2c
4K log,
In Co Inp"
T
8
1+
T
4K log,
T
In
8
1 + In
T
10 25
2
10 25
2
max
28
28
Co
In 1n
282
CO
Tuug with X being the spectral gap of the Markov chain in 82, 83 that satisfies - X
T.og
2
ln2 144+1'
p" -p'(M) < and co Cu(K, min D., M, e, E),, and the instance- deeendend constant G = -8822mas max M(M+2)
(MMx(12((M22))
A54
Sketch. The proof is carried out in Appendix; here we describe the main ideas as follows. We note that the regret is proportional to the total number of pulling global sub sub-optimal arms by the end of round T. We fix client m for illustration without loss of generality. We tackle all the possible cases when clients pull such sub-optimal arm - (i) the condition nmm, (t) S N (t).(t) (t)- - K is met, (ii) the upper confidence bounds of global sub-optimal arms deviate from the true means, (iii) the upper confidence bounds of global optimal arms deviate from the true means, and (iv) the mean values of global sub-optimal arms are greater than the mean values of global optimal arms. The technical novelty of our proof is in that 1) we deduce that the total number of events (ii) and (ii) occurring can
8

---

be bounded by some constants using newly derived conditional concentration inequalities that hold by our upper bounds on the conditional moment generating functions and by the unbiasedness of the network- wide estimators and 2) we control (i) by analyzing the scenarios where the criteria are met, which do not occur frequently.
Remark (Specification of the parameters). Note that the choice of J ddepends on the problem
settings. Specifically, in setting 8t, we set [(e, M,T) = = + 2V (MT)) )² By the definition of c. we have f(e, M) < c. In setting $2 with M < 11, we specify (e,,,,T) = which meets < e due to (.). Lastly, in setting 83 with M Z 11, we choose ((e, = 1/2 lug M and again we have J < due to 17). We observe that the regret bound is dependent on the transition kernel t and the spectral gap X of the underlying Markov chain associated with т. This indicates the significance of graph complexities and distributions within the framework of the random graph model when deriving the regret bounds, in similar manner as the role of graph conductance in the regret bounds established in (Sankararaman al. 2019 Chawla et al. [020] for time-invariant graphs.
M-1
To proceed, we show a high probability upper bound on the regret R Ac,6) of Algorithm 2 for settings S1, S2, Sy with sub-exponential rewards.
Theorem 3. Let f be a function specific to a setting and defined the above remark. For every 0
E << 1 and 0 < 8 < f M,T), in settings S₁ with c 2 1 + 2
S,, Sg with the time
MT
InT + C. InT satisfies horizon T satisfying T 2 L,, the regret of Algorithm with F(m, i,t) Rmm (1)
mm,il()
E| S L+ 1 (A, +) (max( 160r log
TO 1, log TT 21, + MK)) + s(A
Ai
K² + (2M- - 1)K) (l) where L, Ci are specified as in Theorem and C2 2/5
Proof Sketch. The proof is detailed in Appendix. The proof logic is similar to that of Theorem 2 However, the main differences lie in the upper confidence bounds, which require proving new concentration inequalities and moment generating functions for the network-wide estimators. O
In addition to the instance-dependent regret bounds of order O that depend on the sub- optimality gap A which may be arbitrarily small and thereby leading to large regret, we also establish a universal, mean-gap independent regret bound that applies to settings with sub-exponential and aub-Gaussiia rewards. A formal proof is deferred to Appendix.
Theorem 4. Assume the same conditions in Theorems and The regret of Algorithm AM PTS K (C2(In T)² L, L,C C 2 2. The involved constants depend on 0² but not on A.
satisfies that E E[RT Ac,a) S Li 3T7 + ++ (C1, C2) In T
O2 In T +y In TT(nn + 1)) OVVTIn T). where L max(L, (L, (2((2++MK) specified as Theorem and C2
3.3 Other Performance Measures
Communication cost
Assuming a constant cost of establishing a communication link, as defined in 2020 Li and Song 2022), denoted C1, the communication cost Cr can be calculated
Wang et al.
as Cr = C1
EE
E which is proportional to T E. Alternatively. following the framework
2022 Li and Wang 2022 Sankararaman et al.] 2019) Chawla et al. 2020). proposed in Wang et al. the communication cost can be detined as the total number of communications among clients, which
can be represented as Cr = Et= [Eel similar to the previous definition. Regarding the quantity TT - Eel. the number of edges E, could be O(M) for sparse graphs, and at most (AM?). In the random graph model, the expected number of edges is M(M-1) in the worst case scenario and the total communication cost, in worst-case scenario, is of order O(T This analysis holds also for the random connected graph case where e represents the probability of having an edge. This cost aligns with the existing work of research decentralized distributed multi-agent MAB problems without a focus on the communication cost, where edge-wise communication is standard practice. Optimizing communication costs to achieve sublinearity, as discussed in (Sankararaman et al. 2019 Chawla et al. 2020). is a subject for future research.
2 c, which implies (
Complexity and privacy guarantee At each time step, the time complexity of the graph generation algorithm is O + M + Exl) < O(M2), where the first term accounts for edge selection, and the second and third terms are for graph connectivity verification using Algorithm (benefitting from the use of Markov chains for graph generation). The main algorithm comprises various stages involving

---

multiple agents. The overall time complexity is calculated as O(MK + M + MK + M2) = O(M² + .M), consistent with that of [Zhu et al. 2021b Dubey al. 2020]. is noteworthy that most procedures can operate in parallel (synchronously), such as arm pulling, broadcasting, estimator updating, and E-R model generation, with the exception being random connected graph generation due to the Markovian property. Privacy guarantees are also important. Here, we note that clients only communicate aggregated values of raw rewards. Differential privacy is not the focus of this work but may be considered in future research.
4 Numerical Results
In this section, we present a numerical study of the proposed algorithm. Specifically, we first demonstrate the regret performance of Algorithms 2 and 3, in comparison with existing benchmark methods from the literature, in a setting with time-invariant graphs. Moreover, we conduct numerical experiment with respect to time-varying graphs, comparing the proposed algorithm with the most recent work [Zhu and Liu 2023). Furthermore, the theoretical regret bounds of the proposed algorithm, as discussed in the previous section, exhibit different dependencies on the parameters that determine the underlying problem settings. Therefore, we examine these dependencies through simulations to gain insights into the exact regret incurred by the algorithm in practice. The benchmark algorithms include GoSInE [Chawla et al. 2020). Gossip_UCh, (Zhu et al. (021b), and Dist_ USB (Zhu and Liu 2023]. Notably, GoSInE and Gossip_Uc JCB are designed for time-invariant graphs, while Dist_UCB and the proposed algorithm (referred to as DrFed-UCB) are tailored for time-varying graphs. Details about numerical experiments are refered to Appendix.
Benchmark comparison results The visualizations for both time-invariant and time-varying graphs are in Appendix. We evaluated regret by averaging over 50 runs, along with the corresponding 95% confidence intervals. In time-invariant graphs, DrFed-UCB consistently demonstrates the lowest average regret, showcasing significant improvements. Dist UCB and DrFed-UCB exhibit larger variances (Dist UCB having the largest variances), which might have resulted from the communication mechanisms designed for time-varying graphs. In time-varying graphs, our regret is substantially lower compared to that of Dist_UCB. UCB. In terms of time complexity, DrFed-UCB and GoSInE are approximately six times faster than Dist_ UCB.
Regret dependency results Additionally, we illustrate how the regret of DrFed-UCB depends on several factors, including the number of clients M, the number of arms K, the Bernoulli parameter for the E-R model, and heterogeneity measured by maxi.j. |u - n/1- The visualizations are available in Appendix. We observe that regret monotonically increases with the level of heterogeneity and the number of arms, while it monotonically decreases with connectivity, which is equivalent to an increase in graph complexity. However, this monotonic dependency does not hold with respect to M due the accumulation of the information gain.
Conclusions
In this paper, we consider a decentralized multi-agent multi-armed bandit problem in a fully stochastic environment that generates varriig random graphs and heterogeneous rewards following sub- gaussian and sub-exponential distributions, which has not yet been studied in existing works. To the best of our knowledge, this is the first theoretical work on random graphs including the E-R model and random connected graphs, and the first work on heterogeneous rewards with heavy tailed rewards. To tackle this problem, we develop a series of new algorithms, which first simulate graphs of interest, then run a warm-up phase handle graph dynamics and initialization, and proceed to the learning period using a combination of upper confidence bounds (UCB) with a consensus mechanism that relies on newly proposed weight matrices and updates, and using a stopping time to handle randomly delayed feedback. Our technical novelties in the results and the analyses are as follows. We prove high probability instance- dependent regret bounds of the order of log T in both sub-gaussian and sub-exponent only consider the expected regret. Moreover, we establish a nearly tight instance- free regret bound of order /T log T for both sub-exponential and sub- aub-gaussian distributions, up to a log T factor. We leverage probabilistic graphical methods on random graphs and draw on theories related to rapidly mixing Markov chains, which allows us to eliminate the doubly stochasticity assumption through new weight matrices and stopping time. We construct new network-wide estimators and invent new concentration inequalities for them, and subsequently incorporate the seminal UCB algorithm into this distributed setting, A discussion on future work is refered to Appendix.
cases, consistent with the regret bound in the existing works that
10

---

Acknowledgement
We deeply appreciate the NeurIPS anonymous reviewers and the meta-reviewer for their valuable and insightful suggestions and discussions. This final version of the paper has been made possible through their great help. Additionally, we are much obliged to the authors of the papers [Chawla la et al. 2020 Zhu al. 2021b], especially Ronshee Chawla from [Chawla et al., (020) and Zhaowei Zhu from [Zhu et al. 2021b], for promptly sharing the code of their algorithms, which has helped us to run the benchmarks presented in this work. Their gesture definitely improves the advancement of the field.
References
M. Agarwal, V. Aggarwal, and K. Azizzadenesheli. Multi-agent multi-armed bandits with limited communication. The Journal of Machine Learning Research, 23(1):9529-9555 2022.
P. Auer, N. Desa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning. 47(2-3):235-255 2002a.
Auer, N. Cesa-Bianchi, Freund, and R. E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48-77, 2002b.
I. Bistritz and A. Leshem. Distributed multi multi-player bandits-a game of thrones approach. Advances in Neural Information Processing Systems, 31, 2018.
R. Chawla, A. Sankararaman, A. Ganesh, and S. Shakkottai. The gossiping insert-eliminate algorithm for multi-agent bandits. In International conference artificial intelligence and statistics, pages 3471-3481. PMLR, 2020.
S. Chib and E. Greenberg. Understanding the satropolis-hasttngg algorithm. The american statisti- cian, 49(4):327-335, 1995.
F. Delarue. Mean field games: A toy model on erdös-renyi graph. ESAIM: Proceedings and Surveys, 60:1 60,1-26, 2017.
A. Dubey et al. Cooperative multi-agent bandits with heavy tails. International conference on machine learning, pages 2730-22 2739. PMLR, 2020.
J. C. Duchi, A. Agarwal, and M. J. Wainwright. Dual averaging for distributed optimization: Convergence analysis and network scaling. IEEE Transactions on Automatic control, 57(3): 592 606, 2011.
J. Fan, B. Jiang, and Q. Sun. Hoeffding's inequality for general markov chains and its applications statistical learning. The Journal of Machine Learning Research, 22(1)66185-6219, 2021.
C. Gray, L. Mitchell, and M. Roughan. Generating connected random graphs. Journal of Complex Networks, 766)8896-912, 2019.
R. Huang, W. Wu, Yang, and C. Shen. Federated linear contextual bandits. Advances in neural information processing systems, 34:27057-27068, 2021.
H. Jia, C. Shi, and S. Shen. Multi-armed bandit with sub- cub-exponential rewards. Operations Research Letters, 49(5):728-733 2021.
Jiang and Cheng. Multi-agent bandit with dependee expected rewards. Swarm Intelli- gence, pages 1-33, 2023.
P. Landgren, V. Srivastava, and N. E. Leonard. On distributed cooperative Docision-making in multiarmed bandits. In 2016 European Control Conference (ECC), pages 243-248 248. IEEE, 2016a.
Landgren, V. Srivastava, and N. E. Leonard. Distributed cooperative decision-making in multiarmed bandits: Frequentist and bayesian algorithms. In 20/6 IEEE 55th Conference on Decision and Control (CDC), pages 167-172. IEEE, 2016b.
Landgren, V. Srivastava, and N. F. Leonard. Distributed cooperative decision making in multi-agent multi-armed bandits. Automatica, 125:109445, 2021.

---

C. Li and H. Wang. Communication efficient federated learning for generalized linear bandits. Advances in Neural Information Processing Systems. 35:38411 15:38411-38423, 138423, 2022.
Li and L. Song. Journal on Selected Areas in Communications, 40(3):773-787, 2022.
communication-efficcenn federated multi-arma bandits. IEEE
W. Lima, Sousa, and M. Sumuor. Majority-vote on directed erdös erdös-rényi random graphs. Physica A: Statistical Mechanics and its Applications, Applications,388((4)3330003)0 3371))333330 2008.
D. Martinez-Rubio, V. Kanade, and P. Rebeschini. Decentralized cooperative stochastic bandits. Advances in Neural Information Processing Systems, 32, 2019.
B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. Arcas. Communication-effiiine learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1282-1282. PMLR, 2017.
N. McNew. The eigenvalue gap and mixing time. 2011.
A. Mitra, H. Hassani, and G. Pappas. Exploiting heterogeneity in robust federated best-arm identifi- cation. arXiv preprint arXiv:2109.055
2021.
A. Nedic and A. Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 54(1): 2009.
V. Perchet, P. Rigollet, S. Chassang, and E. Snowberg. Batched bandit problems. The Annals of Statistics, pages 660-681, 2016.
C. Réda, S. Vakili, and E. Kaufmann. Near-optimal collaborative learning in bandits. In NeurIPS 2022-36th Conference on Neural Information Processing System, 2022.
A. Sankararaman, A. Ganesh, and S. 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.
K. Scaman, F. Bach, S. Bubeck, Y. T. Lee, and L. Massoulié. Optimal algorithms for smooth and strongly convex distributed optimization networks. international conference on machine learning, pages 3027-3036. PMLR, 2017.
A. Slivkins al. Introduction multi-armed bandits. Foundations and Trends@ in Machine Learning, 12(1-2):1-286, 2019.
Y. Tao, Y. Wu, P. Zhao, and D. Wang, Optimal rates of (locally) differentially private heavy-tailed multi-armed bandits. In International Conference on Artificial Intelligence and Statistics, pages 1544-1574. PMLR, 2022.
L. Trevisan. Cs 174 randomized algorithms. URL UtLLtttt///heerrr..tttttttteeee cs174/
P.-. Wang, A. Proutiere, K. Ariu, Y. Jedra, and A. Russo. Optimal algorithms for multiplayer multi-armed bandits. In International Conference on Artificial Intelligence and Statistics, pages 4120-4129. PMLR, 2020.
X. Wang, L. Yang, Y. Chen, X. Liu, M. Hajiesmaili, D. Towsley, and J. C. Lui. Achieving near-optimal individual regret & low communications in multi-agent bandits. In The Eleventh International Conference on Learning Representations, 2022.
Z. Wang, C. Zhang, M. K. Singh, L. Riek, and K. Chaudhuri. Multitask bandit learning through heterogeneous feedback aggregation. In International Conference Artificial Intelligence and Statistics, pages 1531-1539, PMLR, 2021.
Z. Yan, Q. Xiao, T. Chen, and A. Tajer. Federated multi-armed bandit via uncoordinated exploration. In ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 5248-5252. IEEE, 2022.
J. Zhu and J. Liu. Distributed multi-armed bandits. IEEE Transactions on Automatic Control, 2023.
12

---

J. Zhu, R. Sandhu, and J. Liu. A distributed algorithm for sequential decision making in multi-armed bandit with homogeneous rewards. In 2020 59th IEEE Conference on Decision and Control (CDC), pages 3078-3083. IEEE, 2020.
J. Zhu, E. Mulle, C. S. Smith, and J. Liu. Decentralized multi-armed bandit can outperform classic upper confidence bound. arXiv preprint arXiv:2111.10333 2021a.
Z. Zhu, J. Zhu, J. Liu, and Y. Liu. Federated bandit: A gossiping approach. In Abstract Proceedings of the 2021 ACM SIGMErRICCS/meerattond Conference Measurement and Modeling of Computer Systems, pages 3-4, 2021b.
13

---

A Additional Background Work
Developing efficient algorithms for decentralized systems has been popular research area in recent years. Among them, gossiping algorithms have been proven to be successful (Scaman et al. 2017 Duchi al., 201T Nedic and Ozdaglar 2009]. In this approach, each client computes iteratively weighted average of local estimators and network-wide estimators obtained from neighbors. The goal derive an estimator that converges to the average of the true values across the entire system. The weights are represented by a matrix that respects the graph structure under certain conditions. The gossiping-based averaging approach enables the incorporation of MAB methods in decentralized
settings. In particular, motivated by the success of the UCB algorithm [Auer et al. 2002a in stochastic MAB, [Landgren et al.]|2111160 22116a b. 202T, Zhu et al. 2020 202 Rartinez-Rubio et al. 2019 Chawla et al. Wang et al. [222]] import it to various decentralized settings under the assumption of sub- Gaussiassi,,,,, including homogeneous or heterogeneous rewards, different graph assumptions, and various levels of global information. The regret bounds obtained are typically of order log T. However, most existing works assume that the graph is time-invariant under further conditions, which is often not the case. For example, (Wang et al. [202]] provide a optimal regret guarantee for complete graphs which are essentially a centralized batched bandit problem [Perchet et al. 2016). Connected graphs are also considered, but (Zhu et al.) [020) assume that the rewards are homogeneous and graphs are time-invariant related to doubly stochastic matrices. In addition, [Martinez- Rubio et al. 2019) propose the DDUCB algorithm for settings with time-invariant graphs and homogeneous rewards, dealing with deterministically delayed feedback and assuming knowing the number of vertices and the spectral gap of the given graph. Meanwhile, [Jiang and Cheng, (023) propose an algorithm C-CBGE that is robust to Gaussian noises and deals with client-dependen MAB, but requires time-invariant regular graphs. (Zhu al., [021b) propose gossiping-basee UCB-variant algorithm for time-invariant graphs. In this approach, each client maintains a weighted averaged estimator by gossiping. uses doubly stochastic weight matrices depending on global information of the graph, and adopts a UCB-based decision rule by constructing upper confidence bounds. Recently, [Zhu and Liu 2023], revisit the algorithm and add an additional term the UCB rule for time-varying repeatedly strongly connected graphs, assuming no global information. However, the doubly stochasticity assumption excludes many graphs from consideration. Our algorithm builds on the approach proposed by (Zhu et al. [2021b) with new weight matrices that do not require the doubly stochasticity assumption. Our weight matrices leverage more local graph information, rather than just the size of the vertex set as in [hu and Liu 2023 Zhu et al. 2021b). We introduce the terminology of the stopping time for randomly delayed feedback, along with new upper confidence bounds that consider random graphs and sub-ex sub-exponentiality. This leads to smaller high probability
regret bounds, and the algorithm only requires knowledge of the number of vertices that can be obtained initialization or estimated as in Martinez-Rubio al. 2019].
In the context of bandits with heavy-tailed distributed rewards, the UCB algorithm continues to play a significant role. (Dubey et al. [220] are the first to consider the multi-agent MAB setting with homogeneous heavy-tailed rewards. They develop a UCB-based algorithm with an instance- dependent regret bound of order log Z". They achieve this by adopting larger upper confidence bounds and finding cliques of vertices, even though the graphs are iine-invaiiant and known to clients. In a separate line of work, [Jia et al. 2021] consider the single-agem aggnt MAB setting with sub- sub-exponential rewards, and propose a UCBB-asee algorithm that enlarges or pretrains the upper confidence bounds, achieving a mean-gap gap independent regret bound of order VTlog T. We extend this technique to the decentralized multi-agent MAB setting with heterogeneous sub-exponential rewards, using a gossiping approach, and establish both an optimal instance-dependent regret bound of O(log T) and nearly optimal gepan-gap independent regret bound of O(VT log up to a log T factor.
Our work draws on the classical literature on random graphs. From the perspective of generating random connected graphs, we build upon a numerically efficient algorithm introduced in |Gray et al. 2019). which is based on the Settrooois-Hasstine its lack of finite convergence rate for non-sparse graphs. We follow their algorithm and, in addition, provide a new analysis on the convergence rate and mixing time of the underlying Markov chain. In terms of the E-R model, it has been thoroughly examined in various areas, such as mean-fiee field games [Delarue| 2017) and majority vote settings [Lima et al., 2008). However, these random graphs have not yet been applied to the decentralized multi-agent MAB setting that is partially determined by the underlying graphs. Our formulation and analyses bridge this gap, providing insights into the dynamics of decentralized multi-agent MAB in the context of random graphs.
algorithm (Chb and Greenberg 1995). despite
14

---

B Future work
Recent advancements have been made reducing communication costs with respect to the depen-
dency in multi-agent MAB with homogeneous rewards (in the generalized linear bandit setting [Li
and Wang 2022]. the ground truth of the unknown parameter is the same for all clients), such as
achieving O ((VTM M²) in (Li and Wang 2022] for centralized settings or ((M log T') through Global
Information Synchronization (GIS) communication protocols assuming time-invariant graphs in [Li and Song 2022]. Likewise, [Sankararaman et al. 2019 Chawla et al. 2020] improve the communi- cation cost of order log' or o(T") through asynchronous communication protocols and balancing the trade-off between regret and communication cost. More recently, [Wang et al., [022] establish novel communication protocol, TCOM, which is of order log log I by means of concentrating communication around sub-optimal arms and performing aggregation of estimators across time steps. Furthermore, [Wang et al.] [0200 develops new leader-follower communication protocol, which selects a leader that communicates to the followers. Here the communication cost is independent of T which is much smaller. The incorporation of random graph structures and heterogeneous rewards introduces its own complexities, which poses challenges to reductions in communication costs. These great advancements introduce promising direction for communication efficiency next step within the context herein.
C Details on numerical experiments in Section 4
We report the experimental details in Section 4, including both benchmarking and regret properties of the algorithms. The implementation details of the experiments as follows, including the data generation, benchmarks, and the evaluation metrics.
The process of data generation involves both reward generation and graph generation. First we generate different numbers of arms and clients, denoted as K and M, respectively. Specifically, we generate rewards using the Bernoulli distribution in the sub-Gaussian distribution family, varying the mean values yu"" by introducing multiple levels of heterogeneity denoted as = max; 1u." - ارب and then for each arm k, partitioning the range [0.1, 0.1 - (k + 1) h/ into M intervals. In terms of graph generation, we generate E-R models with varying values of c, to capture graph complexity. Specifically, for the benchmarking experiment with time-invariant graphs, we set K = M = 5, h = 0.1,c c = 1. i.e. complete graphs. For the benchmarking experiment with time-varying graphs, we set K 2, M 5 = 0.1, 0.9. For the regret experiments, the parameters are h E {0.1, 0.2, 0.3), M E {5. 12), c E {0.2, 0.5, 0.9, 1}, and K E {2, 3, 4}. We selected the least positive number of arms K 2 keep computational times low and M 5 to have small graphs but still a variety of them.
We compare the new method DrFed-UCB with the classical methods, such as the Gossiping Insert- Eliminate algorithm (GoSInE) in [Chawla et al. 2020] which focuses on deterministic graphs and sub-Gaussian rewards and motivated our work. We also include the Gossip UCB algorithm (Gossip_ JCB) [Zhu et al.) 2021b) as a benchmark. Meanwhile, in terms of time-varying graphs, implement the algorithm, Distributed UCB (Dist UCB) in [Zhu and Liu 2023) that has been developed for varying graphs, and compare our algorithm to this benchmark.
The evaluation metric is the regret measure defined in Section 4. More specifically, for the experiments, we use the average regret over 50 runs for each benchmark and also report the 95% confidence intervals across the 50 runs. With respect to the communication cost another performance measure, it is computed explicitly. Additionally, the runtime can provide insights into the time complexity of the models.
Evaluation
Benchmark comparison results The results for time-invariant and time-varying graphs are pre- sented in Figure I (a) and Figure (b), respectively. The x-axis represents time steps, while the y-axis shows the average regret up to that time step. Figure I (a) demonstrates that DrFed-UCH exhibits the smallest average regret among all methods in time-invariant graphs, with significant improvements. More precisely, with respect to the Area Under the Curve (AUC) of the regret curve, the improvements of DrFed-UCB over GoSInE, Gossip_ UCB, and Dist UCB are 132%, 158%, and 1 128%, respectively, showcasing the regret improvement of the newly proposed algorithm compared to the benchmarks. Notably, both Dist_UCB and DrFed-UCB result in larger variances, primarily observed in Dist_UCH This phenomenon may be attributed to the communication mechanisms designed for time-varying graphs. In Figure (b), we observe that our regret is notably smaller compared to Dist UCB in settings with varying graphs. Specificaly, the AUC of Dist_UCB is
15

---

... GaSinE
Dist. UCB
Die UCB
Dffedi UCB
Gosup, UCB
DiFed-UCB
Cumuuetve Regre:
20
Cummente
100
250
1000
1250
1500
1750
2000
500
1000
1250
1500
1750
Time Horizon
(a) time-invariant graphs
(b) time-varying graphs
Figure 1: The regret of different methods in settings with both time-invariant and time-varying graphs
0.1
D.2
0.3
Come benee Regpet
250
500
750
1000
:250
1500
1750
2000
250
500
720
1900
1250
1500
1250
2000
Tiire Harizon
Timd Hor Loon
(a)
(b)
8-
0.9
Camuder detion Btreret
Cum servee
250
500
750
2000 1000
:250
1500
3750
250
500
1900
1250
1500 1750
2000
Time Harizon
Tima Horizon
(C)
(d) K
Figure 2: The regret of the proposed algorithm in problem settings with different parameters
96.6% larger than that of regret curve, which implies the significant improvement in this setting with time-varying graphs. Furthermore, we perform a time complexity comparison, revealing that DrFed-UCB and GoSInE approximately six times faster than Dist UCB. Lastly, communication cost is directly computed by the total number of communication rounds and follows an explicit formula. Specifically, the communication costs of DrFed-UCB, Gossip_ JCB, and Dist_UCB UCB are of order T', whereas GoSInE exhibits only o(T",, suggesting a potential direction for optimizing communication costs.
Regret dependency results Meanwhile, we illustrate how DrFed-UCB's regret depends on several factors: the number of clients (M), the number of arms (K), the Bernoulli parameter (c) for the E-R model, and heterogeneity measured by h. The regret metrics are presented as (a). (b), (c), and (d) in Figure respectively. We observe that regret monotonically increases with the level of heterogeneity and the number of arms, while decreasing with connectivity, which is equivalent to an increase in graph complexity. However, this monotonic trend does not apply to the number clients. This is due to the following considerations. On one hand, large M implics greater number of incident edges
16

---

Start
Environment
determine which aim pull
puil an ar
reward neighbbor set
an edge with other clients
exchange estimators
Skip
Update
Figure Flowchart of Algorithm 2
of each client, providing global information access and potentially leading smaller regret. On the other hand, large M also weakens the Chemoff--Hoeffdnn inequality for clients transmitting information, which might result in larger regret.
D Algorithms and Tables in Section 3
The algorithm for generating random connected graphs is presented in Algorithm as follows.
Algorithm 3: Generate uniformly distributed connected graph
Initialization: Let Tı be given; Generate random graph Grintt by selecting each edge with probability 1;
Connectivity: make Ginit connected by adding the least many edges to get Go
for ( 0, 1......:; do Randomly sample an edge pair e e= (i,,)) Denote the edge set of G, as Eg; e E E, then
Remove from E, to get G², (V, Ex(e)): if G', is connected then G =G.;
else
reject G', and G G5; end
else
G.+1 (V,E,
end
end
The flowchart of Algorithm is presented in Figure 3 to illustrate the information flow in the algorithm. The table below displays the various settings we consider for the regret analysis.
17

---

Table I: Settings
E-R
uniform
reward
81
any
sub-g
82
[1,
10
sub-g
v
[11,00 00)
sub-g
S1
any
sub-e
82
v
[1,10]
sub-e
Sy
[11,
sub-e
E Remarks on the theoretical results in Section 3.2
E.1 Remarks on Theorem 2
Remark (The condition on the time horizon). Although the above regret bound holds for any T > L, the same bound applies T L as follows. Assuming T < L, we obtain El RT A S T < L where the first inequality is by noting that the rewards are within the range of [0, 1).
Remark The upper bound on the expected regret). Theorem 2 states a high probability regret bound, while the expected regret is often considered in the existing literature. As corollary of follows. Note that
Theorem 2
establish the upper bound on E[RT] if log T MT
E R
E E(RT| P(A + E( A P(A S P(Ac,) -E Ae,) T (1 (1-1P((A..)))
P(Ac5)
4C1 log T A?
2n²
< (1-7e)(L+ + Σ (max
2(K + *MK) + 3P(Ac.))
+ K (2M - 1)K)) + 7eT
4C₁ log T
2n²²
+ +22 1)K) + log T
$/1 + 12ggo +
(max {[
1,2((2 MK)] + 3(1 7e)
A?
M
where the first inequality uses E[BT|Ac,5) S T and the second inequality follows by Theorem Here L and l2 are constants depending on K, M, 8, ming Ai, and X.
Remark (Comparison with previous work). A comparison to the regret bounds in the existing literature considering sub- Gaussian rewards is as follows. Our regret bounds are consistent with the prior works where the expected regret bounds are of order log'T' T. Note that the regret bounds in [Zhu and Liu y cannot be used here since the update rule and the settings are different. Their update rule and analyses cannot carry over to our settings, which explains why we invent these modifications and proofs. On the one hand, the time-varying graphs they consider do not include the E-R model, and we can find counter-exan examples where their doubly stochastic weight matrices We result in the divergence W, W2... WT. This makes the key proof step invalid in our framework. On the other hand, their time-varying gruphs include the connected graphs when = 1, but they also make an additional assumption of doubly stochastic weight matrices, which is not applicable to regular graphs. Furthermore, they study an expected regret upper bound, while we prove a high probability regret bound that captures the dynamics in the random graphs. The graph assumptions in other works, however, are stronger, such as (Zhu al. (2021b] consider Wang et al.) [2021) assume graphs are complete (Perchet et al. 2016]. In contrast to some work that focuses homogeneous rewards in decentralized multi-agent MAB, we derive regret bounds of the same order log T in a heterogeneous setting. If we take a closer look at the coefficients in terms of 1+> K, M, X, A, regret bound is determined by O(max(Is K, 1-Xx 1 log T). The work of [Zhu and Liu y023 arrives at (max log T K1, K2)) where K1, K2 are related to T without explicit formulas. Our regret smaller when D; S and 1+A
inveiinvarantt graphs and
A;
1-X A. S 1, which can always hold by rescaling A, i.e. for many cases we get substantial improvement.
18

---

E.2 Remarks on Theorem 4
Remark. Based on the expression of L1, obtain that L1 is independent of the sub-optimality gap
D, Meanwhile, we have C1 80 12 M (M and C2 C 12o2 1 M(M+2) This implies that the established regret bound Theorem does not rety on A but does depend on o² To this end, we use the terminology. mean-gap gap independent bounds, to only represent bounds having no dependency on As rather than instance independent that seems to be an overclaim this case.
M1
Remark (Comparison with previous work). For decentralized multi-agent MAB with homogeneous heavy-tailed rewards and fime-invariant graphs, [Dubey al. 2020] provide instance instance-dependen dependent regret bound of order log T. contrast, our regret bound has the same order for heterogeneous settings with random graphs, shown in Theorem 3 Additionally,
provide mean-gap inde- pendent regret bound as in Theorem 4 In the single-agent MAB setting, ÍJia et al. 2021 consider sub-exponential rewards and derive mean-gap gap independent regret upper bound of order Voog' T. Our regret bound of VT log T is consistent with theirs, up logarithmic factor. Furthermore, our result is consistent with the regret lower bound as proposed in (Slivkins et al. 2019). up to a log T factor, indicating the tightness of our regret bound.
Remark. The discussion regarding the conditions on the expected regret E. R and the parame- ter specifications follow the same logic as those in Theorem 2 We omit the details here.
F Proof of results in Section 3.2
F1 Lemmas and Propositions
Lemma 1, For any m, i, L. > L, we have
Tem,i (1) 2 (t,((1) - K(K + 2M)
Proof of Lemma 7
The proof is referred to [Zhu and Liu 2023
Lemma 2. For any m,i,t> L, if Rmm (1) 2 2(K2 + KM + M) and graph Gt is connected, then we have
nm (1) 2 min 2m)n
where the min taken over all clients, not just the neighbors.
Proof of Lemma
The proof referred [Zhu and Liu 2023
Lemma 3 (Generalized Holder's inequality). For any and measurable functions h4 for then
i 1,...,m. n, if > iml
Th hill
II
The proof follows from the Young's 's inequality for products.
Lemma 4. Suppose that random variables X1, X1, Xn are such that YE F((X,,...., "x,,xx,) 221, X,41y.... X,)) proxy 01, 02.0...... respectively. Then the sum of these lub-Gaussian random variables, Σn X,, again sub- Gaussian with variance proxy (Ei 2.
sub-Gaussian distributed with variance
Proof. First, without loss of generality, let us assume F[X;] = 0. Otherwise, we can always construct random variable X; E[X,] which has the same variance proxy with a difference up constant.
19

---

Defining Pi Eii ah gives Ei=1 Pi = 1. Let be the distribution function of random vector ai (X1...., X,). By specifying hx(x) exp (Ax) and r 1, we obtain that for any we have
Elexp (A
XJH
ElTT= exple (AX;))
IT exp hd
< 11 (XX;)
00
=I[=1
exp(AX;)
oo dp) -k-1
2k ok }] 2=k==
= =I
(Ex (exp
EE 1 0k)
at
< _Ix=_ 20/
2
= lexpt 12
σk) (?
Di-1 DE=1
expl x
1
)3)
k=1
where the first inequality by Lemma and the second inequality follows the definition of sub- Gaussian random variables.
Lemma 5. Suppose that random variables X1. X Xa are independent sub- Gab-Gaassian dis- tributed with variance proxy 02.02..... respectively. Then we have that the sum of these tab-GGussian random variables, Et=1 X4, is again sub Gaussian with variance proxy Σi= o.
Proof. For any note that
Fleep (X X,)
Since X2, .,, Xn are independent random variables, we further have
Elexp (X
X
11 Elexp AX,]
S mT expl 2 x²?
= expl 1 12 Σo? ?
where the inequality is by the definition of sub-Gaussian random variables. This concludes the proof.
Proposition 1. Under E-R, for any 1 > 5,c O. and any fixed t L,,, the maintained matrix P satisfies
|PP -PP-cEllas cEl1oc 2
20

---

with probability 1 T. This implies that with probability at least for any t 2 Loy we have
cb 0c S 6. ||
Proof. We start with the convergence rate of matrix P. for fixed
We recall that in E-R, the indicator function Xi, for edge (i,j) at time step follows a Bernoulli distribution with mean value c. This implies that {X are i..d. random variables which allows us to use the Chernoff- Chernoff-Hoeffding Hoeffding inequality
X
P(
-cl > 5 -260")
For the probability term, we note that for any 1 2 Lans
2 2expl - S
6 T
T 28 by the choice L,, of the burn-in period in setting 1. As result, the maintained matrix P: satisfies with probability least 2 that
since 2 L,, 2
Pt - cE o0
E X
max fJ)
<
which concludes the first part of the statement. Subsequently, consider the probability P(IP: cbilo < < > L.,). We obtain
P( cEll < 6, > L,,)
- P(Uizk, || cE <8)
Σ P(I cE 10 8)
12.
2 - (T L.r E 2 -
where the first inequality uses the Bonferroni's 's inequality. This completes the second part of the statement.
We next pin down the Markov chain governing Algorithm 1. Its states compound to all connected graphs if G and G' are connected, then the transition probability is defined by
0 if E(G))E())) >
GG
2 if ((G))))F(() =1
MCM
M(M Gf = G.
20G
Here A denotes the symmetric difference and (G) is the number of all connected graph that differ with G by at most one edge. Algorithm is a random walk in the Markov chain denoted as CG - -CC. The intriguing question is if the stationary distribution corresponds the uniform distribution on all connected graphs on M nodes and if it is rapidly mixing. The next paragraph gives affirmative answers.
Proposition 2. CG Mor any time step n 2 and initial connected graph Ginit, we have
||="((|("mitt - x" (- S 2(p")"
where D= (M) and n² is the uniform distribution on all connected graphs.
21

---

Proof. Based on the definition of π,, we have
n
# #connected graphs}
Therefore, there exists a constant < Cs < 1 such that for any two connected graphs G, G' with [E(G)AE(G") 1 have
(G|G") 2 Cys².
In essence Cj = ming,o (G <.
If = G', then there are two possible cases. First, if (G) < (M(M-L), then TG]]) > M(M >
r and GG 0. Otherwise, we have (GGGG) 0. In other words, the set G & (G': mG' G) S
T ( > 0}.
This implies that for G' (G': = (G)) > 0}, we have [(G)) = and subsequently x (G] 2 Cyτ".
We start with the one-step transition and obtain
||+(-)) x= (-)lrv
=2sup A (
2
11:1(1100-- (-x(G"IG) + +'
2
[d'T(G(6)=0]
2
(0=x(010000((10-00100010) + (G")
/ 1 (T" + Cj)
/c0=xarnccx-011110--11000 //0o///0-22|/////////cc/roooooo0 ( (G")))
22
s 2P((G' = + - Cy)( [([C)
<2 (conneeced graphs)]
+ 2 2(1
01)(1 (1 (1-
#connected graphs} ))
2p' + 2(1 Cj)(1 -0) = 2(p' + (1 (,)(1
2p"
where we denote the term # (connected graphs) and the term + (1- -1-C by p' and pp, respectively. It is worth noting that p* = (M) and p* since p', C' < 1. Here the third inequality uses the above argument on the graphs in the set ( = S (G')), " G) > 0}. and the last inequality uses the following result. By definition,
P([G' (G'G)) = 03)
P((G' : (G')G) > 0})
< -P((' (B(G)AE(G)) 13)
a(G)
1 #cconeected graphs}
#connected graphs}
where the last inequality uses a<G) 2 by the definition of (G)). Suppose at time step n, the result holds, i.e. for any G
(+IG) x (-)llv $ 2(p")".
22

---

Then we consider the transition kernel at the n + 1 step. Note that
1+++((11))
(-)lTV (5
T"
2ssup
A
/
s 2supl
- x (G')) ( - (5)))
(T((|G) **(s)) / (="(G")s) n-" (G dsl
ssu
1
< 2
2 "11m"(11)- +-1llrV | - =>1lv
2 ||((--)-- - ( ())
- T² (-IlzV
$ 2 "" .2p" 2(p")
where the second inequality by using the definition of || l|r and the last inequality holds by the results in the basis step and the induction step, respectively. The first inequality requires more arguments as follows. Consider the integral
J (C))) - -
J 7 *C [ (
(G'GG)d (G')doa
[ (S)ds + [ (G')do
- -/ -G
JA *S)dds
where the results hold by exchanging the orders of the integrals as a result of Funibi's Theorem and the inequality uses the fact that JA n" (G") < 1.
This completes the proof by concluding the mathematical induction.
Proposition 3. For any > d,e O, obtain that for setting 2, for any fixed 2 Luz the maintained matrix Pe satisfies with probability 24
||P: cE oc 8. 8.
Meanwhile, the graph generated by Algorithum 3 converges to the stationary distribution with
16
||a'(-I)) x² <+ 5
where x² is the uniform distribution on all connected graphs.
In $
Proof. Suppose run the rapidly mixing markov chain for time period of length 71 Ing where
Ç <<> 5. By applying Proposition 2 we obtain that for any time step t
|| - fOlllv S "
23

---

For the second phase, we reset the counter of time step and denote the starting point + 1 as t = 1. Based on the definition of Pt, we have Pt = بيت X I5i$5 where X2 is the indicator function for edge (i.j) on Graph G. that follows the distribution (G.-). Let us denote Y the indicator function for edge (i.j) on Graph G following the distribution rT(() peb (2:-1 Y. ISFSSM.
(-) and
By the Chermoff-Hoeffdiee inequality and specifying = 21p")", we derive
E Y
P([E(T
2 S (exp(-21(")
i..
pP cElloc S
holds with probability 2 eexp-21(())
Consider the difference between and p.abi and obtain that
P. pobj
Ex=1 X2, -' Ve
IsiAjSM
Ea Xi.,.
Σ Y
E|X + EXX!, x + E|
t 15SISEM
where the last term is bounded by 3
For the second quantity E - ViJ)], we have that for any 8, i,
E[ - G2 G
=ca. contains adge (195 does not contain edge (i.j)
GG, does not contain edge (1. (f. contains edge (F.))
24

---

and subsequently by the law of total expectation, we further obtain
EI(XY, Y255] - -Y,,)G,,
EELG contains edge (1.5)&:G7*)) does not contain edge (f.) (G, does not contain edge (f.))& contains odge (k.j))
E E, contains edge (i.j)l E'1 Egl does not contain edge (1.5)
([G does not contain odge (..r)) El1og*) Goh1 contains edge (f.5)) since G2 and G are independent
/
1 S contains edge (1,) (S)G)dS
1 does not contain edge (1.j) (S)ds
JA 1s does not edge (f.j) JT (S|G))S S 1s contains edge (t.j) (S)))
-AA 1 s contains edge (1.) " +
8 does contain edge (4.j) > (S)dS
J. 1s comtains edge (i.)) (i.)) (S)dSS
J. is does not cuminin edge (f.j)
JA 1s contains edge (1.1) " (t (5)ds
f 1s does contain edge ((.))"((())))))
J 1s does not contain edge (i.j) IT "
S, is contains edge ((.))r(((S)))
1 does not edge (f.j) ा. (S)dS(
19 contains edge (i.)) (S - =
JA Is contains edge (t.j) ा. (S))
/
1 contains edge (1,5) (- +
1 does not comtain edge (i.j) - (S)d5 7 1| - x (-)llv+
SA I contains adge (1.1) x (S)dS 1| n 7-)lrv
=|| (+GG) =')llrrv < yz
In like manner, achieve
E[(-Xi, Y )
We now proceed the analysis on the first term Though {X;}}= are neither independent or identically distributed random variables, the difference Xi, E(X,,)) can be upper bounded by the convergence property of π", Note that X is only different from X when edge (i, is sampled at time step and the generated graph is accepted.
(.j
We observe that
P(G,+i|G,, G.-n...,,Gi P(G
Meanwhile, we can write X 1x,+'= 1G contains edge (i.j) and similarly, Xł, = Lxt,=I LG, comtains edge (i,j) Denote event E as E' = (connected graph G contains edge (i.j)). This gives us
x -IG
X = IG,EE.
25

---

Furthermore, the quantity SA ISEET" (S)dS can be simplified as
B|y = El1 6.h EBl
= = 1sEET"
since G follows a distribution with density x² (-).
A new Hoeffding lemma for markov chains has been recently shown follows in (Fan et al. 2021]] Let (A) 1+ where À is the spectrum of the Markov chain CG MC and by the Theorem 2.
in Fan et al. 2021
we obtain that
P(I S..EE-tE|EE > t() S 2exp( [{²
P.e.P( #=1 Xis
E[ C) S 2exp(-2a(\)
(5)
since Xf, 1G,ER satisfies 0 S la,eF S 1, i.e the values are within the range of [0, 1].
By the result E[X
- E( - E + Ç, we obtain
E X E E > 2() < P(
(6)
Putting the results 3
4 and 66 together, derive
P
P
Σ. mmm
X
E. 1.
max
E[X
+
+
m [.]
===
1.
X
Y |
Σ Yi
t
2 + 5 45
which holds with probability at least 1 - 2 2exp(_2a(A))-1)) - 2 eexp 1axpp-21(9' 2)
For the probability term 1- 2 exp( -xxp-2a(aA) [((2 2exp1-221 - we have
2 expl -2a()) [(53} S T
2 ex S T
6
which holds by
In πr 2 T.ng - Ti a())
2C
Therefore, the distance between the empirical matrix and the constant matrix reads as with probability at least 1 - -2
|P: - cE'loo
< IP. pock) 11 + || cE'loo
< 44 + < 5C <
where Ç = 2(p")** < 5 by the choice of parameter 8 and Ç. This completes the proof of Proposition 3.
Next, we proceed to explicitly characterize the spectrum of CG MC which plays a role in the length of burning period Loz and Leg-
26

---

Proposition 4. In setting 2, the spectral gap - X of CG - MC satisfies for 8 > 1,
1 -
2 2p
In 20 +
Proof. is worth noting that for G + G¹ and |E(G)AF(G)) = 1, we have
by the fact that T² =²" and [GG =G = M(M-1))
2
For + G' and [E(G)AE(G)) > or [[G)) = O. we have TT(G)=(G'))) = Tt (G")TTGG(") since (G]G")
For G G", we have x''
=
by the expression.
As result, CG MC is reversible. Meanwhile, ergodic since has a stationary distribution as stated in Proposition 2
Henceforth, by the result of Theorem 1 in McNew 2011 that holds for any ergodic and reversible Markov chain, have
A2
S r(e)
2
X2
where T(c) is the mixing time for tolerance and X2 is the second largest eigenvalue of CG MC. Choosing e > immediately gives us
(n(e)ln211 A S (7( In 2e +1
(7)
Again by Proposition we have
||
- (()l & 2(pt)((e) =c.
Consequently, arrive
In In 2p
r(c)
and subsequently
2 Inc.
In 2e
In 2p"
A2 S
2 In
In 2e +
2p
by plugging (()) into 77
This completes the proof of the lower bound on the spectral gap 1 - X2.
In the following proposition, we show the sufficient condition for graphs generated by the E-R model being connected.
Proposition 5. Assume e in setfing meets the condition
12c2 + 2\
MT
where < 6 < 1. Then, with probability e, for any O, G. following the E-R model connected.
27

---

Proof. For 1 i M, we denote the degree of client j as dz.
It is straightforward to have 1) プز d2 total number of edegs, 2) Eltotal number of edges) M(M-1) and 3) random variables d1, dz,..... da dependent but follow the same distribution.
Note that d, follows binomial distribution with Eid,] = c- (M - 1) where is the probability of an edge. Then by the Chernoff Bound inequality, we have
M - < exp (-(M -M 1) (0.55l)))) 2
P(dj <
where (O.5ll) denotes the KL divergence between Bernoulli(0.5) and Bernoulli(c). For the term L(O.5lle), we can further show that
KL(05) 2 log 2 log 1-c 2
1
1
1 4c(1 c)
log
2
which leads to P(dj < - S exp {M - 1) 1/ log 40(1 - cc)
Meanwhile, have specified the choice of as
2 cc<
+
2
2
MT
which guarantees exp {(M 1). log 4c(1
c)} S
follow. We observe that
MT
1 +
1
E
c
2
2
2\
MT
4c(1 - c) S
_
N
MT
log WT
log 4c(1 c) -
M- - 1
1
log 4c(1 -c) S log é
(M - 1).
2
MT
= exp((M 1)
log 4c(1 - -c) S MT
2
This is summarized as for any j
P(d < M --
S exp {MM -1) log 4c(1 - c)} S MT
(8)
2
Mcanwhile, it is known as if 8(G.) 2 M-1 then have that graph G. is connected where 5(Gr) = minm dm-
As result, consider the probability and we obtain that P(graph G. is connected)
M 2 P(mindj 2
2
M 1
= =P( (dg
})
M -
1--P(Ud; <
})
2
M 11
2 Σ P(d <
2
= 1 - MP(dj < 1
2
21 1 M C = 1
c
MT
T
28

---

where the second inequality holds by the Bonferroni's 's inequality and the third inequality uses 8 Consequently, we obtain
P(graph Gg is connected)
P(nnGG is connected])
21 Σ P(G, is not connected)
(1 E
P(G, is connected))
2 Σ (1- -
where the first inequality holds again by the Bonferroni's inequality and the second inequality results from the above derivation. This completes the proof.
On graphs with the established properties, we next show the results on the transmission gap between two consecutive rounds of communication for any two clients and the number of arm pulls for all clients.
Proposition 6. We have that with probability c, for any t L and any m, there exists to such that
++ 1 - min bm $0,.0 S co minni,(k
where Co co(K, min; A,, M,c
Proof. The edges in setting follow a Bernoulli distribution with given parameter by definition. Though setting does not explicitly define the edge distribution, the probability of an edge existing in connected graph, denoted as is deterministie, independent of time since graphs are i..d. over time and homogeneous among edges.
Henceforth, is straightforward that e satisfies
M(M 1) c= E(N)
and equivalently
2E(N) M(M 1) where N denotes the number of edges in random connected graph.
We observe that N M(M-1) Furthermore, the existing result in Trevisan yields
E[N] M log M.
Consequently, the probability term has an explicit expressions c
2E[N] M(M-1)
2og M M
For setting 82, S2 we have e = 21og 2 since M < 10, while in setting 81, Si. the condition on M
guarantees 2. Note that f + - tm.y follows a geometric distribution since each edge follows Bernoulli distribution, which holds by
P(t + bm.j = 1/tm..)
Pttheee is an edge between m and j time step t+1 and km..)
P(there is an edge between m and at time step km..)
(c)
29

---

and
P(t P kmmmm))
P(there is edge between and at time step t+k and fm..j edge at time stepl ,...,,
P(there an edge between m and j at time step km.j)
(1- (1-c)h-1c² = c(1 - c)
Note that (t. + miny fm.j (o) which denotes the tail of geometric distribution depends on the choice of c. More precisely, the tail probability Po is monotone decreasing in c.
When 2. we obtain that
1 -
)0. 2
Po = P(L min Am > to) S
(9)
2
8310
In M In2
Choosing 40
leads to Po = 1 -0))0 = M and
cp minni (t+ + +1) 2 co
min nt, (L)
L In MT 2 co K
MºT In 2
la
Co In2
where the last inequality holds by the choice of L. This implies min; nt, + 1) to 2 (1 co) miny (t, + 1), i.e. to I miny (t + 1). Therefore, with probability 1 NTT.
min (lmm))
min ni. (min tm.
minmy, tu)
minmi, to
1 co) min mi
where the first inequality results from the fact 1m,i miny bnjj the second inequality uses the fact from (9) the third inequality applies the definition of n, and the last inequality holds by the choice of to-
Consider setting 83, S3 where M > 10. Generally, for given parameter c, we obtain
P(t 1 min tm.j 1) c,
P(t 1 - min tm.j = =2) = c(1 - c)2
....
P(I min bmjj = c(1 - -c
and subsequently
1 (1 c)
Po P(t min mintm. tm to) S Σ (1- s cc
(1 00
c
c
For the probability term Po. we further arrive at
Po
MºT
In( k
by the choice of to > In(I-e)
30

---

Meanwhile, we claim that the choice of to satisfies
to S co I
minmsstt 1)
1n| 32r S co miny (t,(t + 1) holds by noting nt,((t 1) mL,(LL) 2 t and
since In
K k MeT cp In -c
K In MP co
In 1-c
To summarize, in all the settings, have that with probability least N²T
+ min m. S to.
to S co min nt, + 1).
(10)
Therefore, we obtain that in setting $1, S1
P(Vm, 1 - min j S lo S co minnus + 1))
- (1- - Po) 2 1- MPo MT
(11)
where the inequality is a result of the Bernoulli's ' inequality.
In setting 82, S2, 83, S3. {t miny /1.j.... I +- miny (ars) follow the same distribution, but are dependent since they construct connected graph. However, we have the following result
j P(Vm, t 1 mintm m to co min nt, + 1))
= 1 - P(
min m.j 2 tol)
2 1 - Ep(t
P(t +1++1111 min t 2 to)
3
1 MP. = 1 MT
(12)
by the Bonferroni's inequality.
As consequence, we arrive at that in setting $1, 11, 82, S2, $3 Sz.
P(Vt, Vm, + min En I to S min nt, + 1))
21 Σ Σ P(t + min mmj S to S Co min mta(t + 1))
2 MT(1
MT 1-
where the first inequality again uses the Bonferroni's inequality and the second inequality holds by and
applying
12
After establishing the transmissions among clients, next proceed to show the concentration properties the network-wide estimators maintained by the clients.
The first is demonstrate the unbiasedness of these estimators with respect to the global expected rewards.
Proposition Assume the parameter satisfies that 0 < <<= f(c, For any am and any client at every time step we have
E (t) Ac p4.
31

---

Proof. The result can be shown by induction as follows. We start with the basis step by considering any time step & I L + 1. By the definition of (t) p. (L 1), we arrive
ET Ac))
Ela (L + 1)
M
E
Pmn (L) (Hmo)))Aed
(13)
==1
if Pm. The definition of A., and the choice of å guarantee that
where ; M
{0, else
Prr. cE| < 8 < c on event Ar,6, i.e. we have for any 2 L, > 0 and thereby obtaining
P (L) M
(14)
Therefore, we continue with 13 and have
M
am
(k Acss
Pig
M
j=1
Elpy (1
Ee (( Mij,t (hii
E
Ac,ol
M
M
E. 10 lo A.,6AA.))
E
M
nz (h
==
where the last equality uses the law of total expectation. With the derivations, we further have
13
F
Fl
Σ
M
ni
El
Σ
Elr((s)o(nns Ac.s (15)
M
(h
nz m.n
j=1
smy,a(s) -(y,
E
Σ m
(16)
M
nz.2 ( (s) (s- 1)=1
1=1
1 M
= M
Elu Ac,5]= =ps
(17)
1=1
where the second equality 15 uses the fact that {s R2,,(s) - n15((s- 1) = }} is contained in (I),)()))s Lm.. and the third equality (16) results from that (s) is independent of everything else given s and ETr (s)] p!-
The induction step follows similar analysis as follows. Suppose that for any S we have Elū Ac,) μ4-
32

---

For time step t + 1, we first write it as
Bl (t 1)
M
E
(m.. P) (tmms) + dmn JeN... (t)
Σ
(t) + dm,t
Σ (ty(tm)))A
j=1
ju.N (t)
M i) (tm.s) + drngt jENm((t
F
Σ
(L((1) + dmn
Σ
(((mm))la
Ac,l
jgNm(()
(18)
where (m j) and d are constants since (t(m.j) for t 2 L event Ac,s and the last equality again by the law of total expectation.
This gives us that by the law of total expectation
M
18 = E
dmnt
Σ #l)((t))ddm::::))))ss+)1a)
(EN
dmn.t
(gN..(()
M
P'mm, j) (4m.)))FFFF.i(d(o)o00000:00)00a0
3=1
Eldm,t Σ
JEN...()
dm,t
Σ
(EN..(()
P'mm, j) Eli (mm.s))eee)) + Eldm, Σ E (0 Ac.lAee))
P' P'mm, (i.ii))BB (1m.))
dm,, Σ E(E
Σ (r((
sm)))( 10-1
M
P((m,J)m + dm, Mp P'(m..) + Mddma) 14
where the first equality uses (mm, and are constants on event A..6, the second equality is derived by re-organizing the terms, the third equality again uses the law of total expectation and integrates the second term by fm.j. the fourth equality elaborate the second term and the equality in the last line follows from the induction and 16
This completes the induction step and thus shows the unbiasedness of the network-wide estimators conditional event Ac.b-
Then we characterize the moment generating functions the network- wide estimators and conclude that they have similar properties as their local rewards.
Proposition Assume the parameter 5 satisfies that 0 < < c= f(e, M,T). In setting 81, 82, 83. where rewards follow sub- gaussian distributions, for any m, X and t > L where L is the length of
33

---

the burn-in period, the global estimator P (t) is sub- Gaussiann distributed. Moreover, the conditional moment generating function satisfies that with P(Ar,6) = 7c,
Fleex (M(1)) (1)-11))
I exp { X² Co²
2 ming ny,s(t)
L(M+2) 2(M++)) )a
where o² mox and C' = max
(M + 2)(1 + 4MM
(1
Proof. We prove the statement on the conditional moment generating functions by induction. Let us start with the basis step.
Note that the definition of A., and the choice of 6 again guarantee that for / 2 L, PP - cEI < <8c on event A,,8- This implies that for any 2 I, and j. P (m, >> O, and if / = L
P.(m, M
(19)
and i > L.
(m M
(20)
M
Consider the time step t < L + 1. The quantity satisfies that
Elexp (A(TT" (t) (4) HAr, (ot.m/loommmmmmmeemmm (t))e..m
= Elexp (xTTTT + 1) [4)} [ LA, (()
Elexp {1)
P mig (L) (, (1hh.)) 14) (1tmm:00m
M
= =Elexp {A(
Mig
am (hmm - pi) (x))))al((((((mm)())))))
M
j=1
M
Eleexp {>
Σ
(i (1i)))) - - (((m)))))((
1=1
S MI (ET(epp {(>
(1) (1(())) - p #()LA,,)) (MmmmMMMmtt)).aaa... M
(21)
where the third equality holds by 119 the fourth equality uses the definition the last inequality results from the generalized hoeffding inequality as Lemma 3 Any (hmng)) 3k
37 Σ 1 1 and
and the fact that
Note that for any client j, we have
El(exp {(2 M
(H(( 11)
Elexp {(((T)) (A(T((NL 11))),,,,))) (lo,,,))((())))) [t))
Elexp {(1 E. (r(((s) - 14
}1,
(t))e.mll
nj (k
(r! (3) m1²)
Eleexp
A (ltmm))mommmmmm....m (1))...))))
(22)
n2 (
34

---

It is worth noting that given s, r (s) is independent of everything else, which gives us
II, Elex {A (s) (²)
22
1T,ep (1 (b) Hz)
ng (l0((mm (1)).mm) El1 a.o Jo (mm,i(1))...
(r) -12?
-11,E/lexp
{1
H. E[LA,s (ftm,
Mi
m.))
)²00
< II, exp
L (t)e.m))))
2
12
Rg.s(h
(exp {
2
A
o²
23. (h m..)
=exp {
2
X²02
S exp (
(23)
2 2min nz (h
m.j
where the first inequality holds by the definition of sub-Gaussian random variables (s) p with an mean value O, the second inequality results from A I 1, and the last inequality uses (h 2 miny ny.a(hm..) for any j.
Therefore, we obtain that by plugging
23 into 21
2²02
21
IIM j=1 (exp min, nz (h
})st
X²0²
((exp { 2 2min nz (
}) )ad
X²0²
exp {
2 2in, (h,r
which completes the basis step.
Now we proceed to the induction step. Suppose that for any s < f+ 1 where t 2 L, we have
Elexp (M(iT' (8) [1))1 A A ( X2
sexp 1 / 2 min; (s)) }.
Co²
(24)
35

---

The update rule of p." implies that
Elexp {}(2)" (t 1) - pe) A. lor (s
M
= =Elexp A Σ P( (tmp) - (4:) + dm JENm
Σ
(1 - m$)
Σ (bm))) -1)11) A ((mm:
(1)
=lexppMM A() Σ P) (tm.s) - (s)) + dm. E
(z)
jENm(()
+ dm,
(p)(t m2)))AA,
(1N
= EE f=1 (XP (4m.s) - 14) A..s II exp(Adm, - (t)) expl (ddm (F (fmm.) - 1
S (E[[exp (m. () (m - (1) M A.
ElIl (expl
(t) (
E(IllgN...t) exp Adm. (p)) (fmJ) - (4 lo
= (E((((((((c(APPPmmm))))) + 2) (fm..) - 14) ( + (t) - ((())))))))),,) (1 s.) मों.. x (P +22
E j (cxp(AAcc.) + 2) (tm.)) ( (f (8)) कनक
Co²
< 11, M (exp(
}) 1)
2
miny nij, (tmms)
I1 (e) Addm. (M + 2) (s) - 12:
}1 EE a lo (((()mm(()))..m) x'zz
m1,((1)
Co,,,.. (ddm, (M 22 (F((s) - -1b) H1 E[LA, (((mmm)()))ss पें (mm)))
(25)
where the first inequality uses Lemma 3 and the second inequality applies (24) the assumption for the induction step and holds by exchanging the expectations with the multiplication since again given s the reward (s) - x4) is independent of other random variables.
We continue bounding the last two terms by using the definition of sub-Gaussian random variables (r/ (s) m and obtain
X2 (M + 2
Co²
25
(expl {
2
miny ng.((tm.)
2a m. (M + 222002
IjEN,, (1) (exp
2n 2t²,(t)
X² X2 (M + 2)20²
Hj (1) (cxp
2n (tm.s)
X² ()) + 2)²
Co²
(expl (
1)
2
minj ngji(bmm))
(t)
d2 &2 (M + 2)²222
(1) exp
M
+
2n
ni (m)
22 (M + 2)202
(1) (1) exp
M +2
2n S (tmm.))
36

---

Building on that, we establish
(m. + 2)
Co
25
(expl {
}) w
2
ming nz.((m..)
(M + 2)22
(expl
B E'1A, 1)|8m((0)
min, nt,,(t)
X dm, (M +220²
(expl
})1M EELL, (0mmmmmmm))e)
miny ng.:((m.))
2 ()) M)M +
Co
Xmmm, + 2) (t)
Fl(exp
miny R2,j }) (exp
})
2 2min, nz,;
d2 m. (M + 2)02 Nm (t)l
(M
(expl {
(( (1)).mm)))))))))))
2 2min (mm()
()) MM +2)
Co²
22 m, (M + 2) Nm (1)|0² })
S El(exp
}) (exp
2(1 - c0)
miny Nz, (1
L/K
miny nz,s 1)
1/K41
de + M - (0]o
(exp {
A) )(mm)))o(((mm:(()))))))
2(1 co) min, n1, +)
where the first inequality uses the fact that for any j. (t))(t) 2 min, (t,a() and (fm.) W miny (t,
For the second inequality, the first term is a result of miny (f+( L/K
miny (t)(t)
IM
min, (1) miny (f)++)+T 2 L/K+I since (t,a(t) > (T,(L)) L/K and the ratio is monotone increasing
in n, and the second term is bounded based the following derivations
min (tm 2 min (,, + -1 to)
min (t + to
2 min (t. + 1) co mi + +1) 3 (1 co) min mtn
where the last inequality holds by applying Proposition 6 that holds on event Ac,5- Therefore, we can rewrite the above expression as
X²0²
C( C(P((m,)))MM + +2)
25
El(exp(
2 minj nijh (t (t+1)
2(1-co)
(M + 2) (m)
d (M + +2) +2)))-Na((t) 1ll (()
L/K
(1-
L/K+I
C2
Elexp(
} LA (a
2 miny ni +
CX202
expl nys(1 1)
where the first inequality holds by the choice of (m,,, j),mt,, co and C and the second inequality uses the fact that LA.s < and miny (t + 1) E a (() ht))...))
This completes the induction step and subsequently concludes the proof.
Proposition 9. Assume the parameter satisfies that f(e M, setting 81, 82, and 33, for any m, i and > L where L is the length of the burn-in period, (m) satisfies that if if
37

---

(t, 2 2(K2 KM + M). then with P(Ac,6) = 1 7E,
Ci Cg (L)
P(ūmm(() Mei
AA,,)) S P(Ac,b) (22
C1 logt V 7m,i(() (1)
1
P( (tm,(t)) 2
AA,8)) S p(A
Proof. By Proposition 7 we have (l)ma(() - Ac = 0, which allows us to consider the tail bound of the global estimator p. (t) conditional on event A,,5 as follows.
Note that
C1 logt (Ac,)) (1,
P(ūm, Mi
=E[1 Ci los Plm
Ac,sl
(t)
E[1
Ci log A.
P(A.,)
Am. -ai
mm.
E[1
Ci locc lAnd "m,tl))
P(A..)
exp (0))))/mmm.000-0-)))0000000100
exp (pm - -11) LAndl
(26)
P(A.))
exp(>(n) C log! km,
where the last inequality is by the fact that 1 (xD(M)))(Gmm::0--:)))))) 2xxx)))()))))))))))
C lox "m.a
(x0(A))((mmm000pp))) exp/>(n)
9 loxt
(0)
By the assumption that d < c, we have Proposition 8 holds. Subsequently, by Proposition g and Lemma 2 which holds since (t) 2 2(K + KM + M), we have for any X
X2 Co2
E'exp
exp 1 miny mz)(()
< exp ( X² Co²
(27)
(1)
Again, we utilize the law of total expectation and further obtain
1
exp(A(n)((m)) (t) pp)
26
E
LA. la (())m,,(t)))ma.l
P(Ac,)
exp(A(n), V m0)
C. log?
1
(xp(A( - pb)}
E
Ac.o (1)
P(Ac,)
Ci loge exp(A(n), V mm..(1))
1
E
([exp(M()((mm;:C - p4) (o(mm,, (m))m,
P(A,s)
exp()(n)
log (t)
1
exp X²(n) Co²
<
P(Acs)
exp()(n)
C. log! x10)
nom (1)
$ P(Acs)
expf-2log -2og
(28)
)(
38

---

Ci log
where the first inequality holds by 444) and the second inequality holds by choosing X(n)
mmm,200
and by the choice of parameter C₁ such that
4Co 2 2 or equivalently C₁ 2 8Co2.
C
In like manner, we obtain that by repeating the above steps with (4; ( (t), we have
C1 log Ac,b) S p(Ac,5)t2 (t)
P(ps it) 2
(29)
which complete the proof.
Proposition 10. Assume the parameter 6 satisfies that < 8 f(,, An arm k is said to be sub- sub-optimal if k * where i' is the unique optimal arm in terms of the global reward, i.e. i* = arg max 1 Md
M 2z=1 1r. Then in setting $1,82 and 83, when the game ends, for every client m, 0 0<<< and T L, the expected numbers of pulling sub- sub-optimal arm k after the burn-in period satisfies with P(Ac.5)
Te
Em (A)s
401 log T 1,2(K2 + MK + M)) + A
2T
< max {[
+ K2 (2M 1)K
(P(sA.))
< O(log T).
Proof of Proposition 10 We claim that what lead to pulling an sub-optimal arm i are explicit by the decision rule of Algorithm 2 meaning that the result at" = holds when any of the following conditions is met:
Case 1: Rmm,(tt) (t), K.
Case 2: Amm5 pi >
log Am.:(t-133
Case -pmm Mbi
Ci log Dep (t-1)
Case 4: P4- p4 <2 2
Ci log Pt
Then we formally consider the number of pulling arms (T,((T) starting from I. + 1. For any > 1, we have that based on the above listed conditions
Bm, (
1 (o (m)3)
Tol1
< 1+
(pm
C₁ log
1=
[ +
Wmm i6 13 <les (tm.s
C logt
t=
T
Σ
+
(1i (1++2,
Ce Ton 2Me 1t-..(111222 (t-2(t-
1=L#1
39

---

Consequently, the expected value of (t) conditional on Ac,5 reads as
Fl (T)
T
C₁ logt
=++
Σ
P(
it -1 > Mi, Dma(t- -1) 11A,,))
L+1
Ci Cilogi < pir pir,, Rm, - 1) 2 1/Ac.))
P(
Rm. (t-
((- (()m.((1) < <Nmalll) K, = i, Mm, 11) 2 1 Ac,b))
1=++1
Ci
+
Σ
P(us + V nt,i(t-1 -t) > pe: nmm , -
2 ((Ac,5)
1+++1
T
=1+
P(Case2, Fm mm)(l-1) 11) A1 + Σ
(Caaee3nm.tte 1)
1)2 2 (1Ar,))
1=++1
1=++1
T
T
Σ
P(Casel, = ii, - 1) 2 1 Ac,6) +
Σ
P(Case4, nmm - 1 2 (|Ac,6)
t=
t=/-1
(30)
where max {[ 1C log A
2(K2 + MK M)).
For the last term in 30 we have
C logt
Σ
P(Case4: u4 2
(t 1m, 1) > po, (t, 1) 2 21 =
(31)
since the choice of I satisfies Z
4C log T A7
with A, = p4.- - M4.
For the first two terms, we have on event Ac,5
T
Σ
P(Case2, At, 2 (Ar,)) +
P(Case3,
(t, Camase,,,m,,(tte
-t 2 11 AA,))
t=L+1
Cg
T
C1 logt
P( - 14
(Ac,)) +
Σ
Pm- + +14 >
nmm (t 11 (Aco)
it - 1)
1=L+1
1=1
(32)
where the first inequality holds by the property of the probability measure when removing the event at, 1) > and the second inequality holds by (47) and (29) as stated in Proposition 9 which holds by the assumption that d < c.
For Case 1, we note that Lemma D Dimplies that
(l) > N1, - K(K + 2M)
with the definition of (t,,(t + 1) max (t) (N.
Departing from the result that the difference between (t),(t) and (tm,i(t) is at most K(K + 2M).
we then present the following analysis how long takes for the value (t) + (t,,(t) to be smaller than K.
At time step I, if Case holds for client then (l,+(1+11 1) is increasing by 1 on the basis of xl)) What follows characterizes the change of N (t+1))))). Client m satisfying (t, S (f) (1)-K K will not change the value of it, + 1) by the definition a + 1) max + 1), N,, Nt,(t). e
(1).
40

---

(t). Moreover, for client j E (t) with (t,((t < NN,((t) K, i... Ng.lt + 1) will be affected by Rz. + 1) I n,,e(t) + Thus, the value of Nt, + 1), (().. E (m)(()) (()) is independent of such clients. We observe that for client j E Nm (1) with N5,a(t) > (t,(()) K, the value (t,)(t) will the same if the client does not sample arm i, which leads to a decrease of 1 in the difference -tm,a(t) + N,,, (t). Otherwise, if such a client samples arm i which brings an increment
na
to (t), the difference between ( and (t) will remain the same. However, the latter has just been discussed and must be the cases as in Case 2 and Case 3, the total length of which has already been upper bounded by x² as shown 32
Therefore, the gap is at most KKK + 2M) K _ i.e.
T
P(Casel, = (t -0 2 4A) S K(K + 2M) - K π²
Σ
(33)
3
Subsequently, we derive that
7²
K + n²
El :T)m..()))Aed S 51+
+ K(K + 2M)
+0
3
3
2n²²
= +
+ 2 + (2M - 1)K
3
4C1 log T
2x²
max
1,2(K
MK M)]
K2 + (2M 1)K
A
where the inequality results from 30
and 13
This completes the proof steps.
Next, we establish the concentration inequalities of the network- estimators when the rewards follow sub-exponential distributions, i.c. in setting S1, S2. and Sz.
Proposition 11. Assume the parameter 8 satisfies that 0 < 8 fc, In setting St, S2. and S3, for any m, i, X and t >> L where L is the length of the burn-in period, the global estimator iT (t) is sub-expone -ub-exponentially distributed. Moreover, the conditional moment generating function satisfies that with P(A..s)
for |||<
Elexp (AGE (f) (1)) LA.))aa.lll (ommmmm) X² Co²
< exp -/x
miny (1)
where x² (o and C = max 4(M+2)(1- 3.M 29 )a
(1-c))) (M + 2)(1 4Md,,
Proof. Assume that parameter [X| 1. We prove the statement the conditional moment generating function by induction. Let us start with the basis step.
Note that the definition A and the choice of again guarantee that for t 2 L, P. - cE < <<c on event A. This implies that for any 2 L, Pt O and thereby obtaining that if t L
pl. Pt,,(() (t)
(34)
M
and if > L
M P m.
(35)
2
41

---

Consider the time step t & L + 1. The quantity
Elexp (A( (1) - LA.. (at....llllmmmmm))aaa..a
Elexp {A(2TT (I [L+11 1) - [A)) (f
M
= Eleepp {a(
pm (L. (M (Mmm Ac, (0
A
==1
M
Elexp {A(
M
j=1
Elexp {2 Σ
-
14))1 (0mm))::000
M
S (Ei(ep {(>
(1t (Hin)))) - Mo(((mmm())))))). M
1
(36)
where the third equality holds by (44, the fourth equality uses the definition μ4 the last inequality results from the generalized hoeffding inequality as in Lemma 3
E mg and
Note that for any client j. by the definition of F (h we have
El(exp {(2 M
(1
MIo (1 (1)mmm))
Elexp { (A( mz) ( (l0 (t)
= Elexp {(A (r(r(()) - mz)
}La lo (ltm)))(
12g,s (h...
Elexp 1 (A (1 (x) - H4)
11 A., (o
(37)
It is worth noting that given s, r (s) is independent of everything else, which gives us
E1,E exp {A (r( m²)
}1 A. ll (f)mm
Elexp {} (s) m²:
(4 (lo((mm.(())aaa ElLA, (o(mmmm))mmm
(r (8) mn))
Fxxp {A
H1 F[LA, (o ((mmm
M3 (nt
022
< II, exp {
m..))
E( Aea ((nm,
2
222
< (exp {
(
2
X
(h2
X²02
exp
} S exp { min, ni, (h
(38)
2
where the first inequality holds by the definition of sub-exponential random variables r (s) - m with mean 0, the second inequality again uses 1A,, I 1, and the last inequality is by the fact that mi 2 min, ng (hh.))
42

---

Therefore, we obtain that by plugging 38 into 36
0
36
i M (exp (
2 min, ns (b m.j
X²
X²0²
= ((exp {
}) 19 3 exp 2in mz (h.
2 miny Mz (h, (hm)))
which completes the basis step.
Now we proceed to the induction step. Suppose that for any < ++ where + +1> L 1, we have
Elexp (A( -4) (
exp 1 -/t Co²
X²
(39)
minj (s)
The update rule of puth again and (25 implies that
Elexp (1 (t 1) - 14)] (.)))
X (P) +22
Co²
142.
miny Teja (mm)))
TI JN (t) (Fx (ddm, (M + (x) - 14:
}1 El aes (1)] में..
nt,(t)
(eg ( + (r) - 12) H ETLA, (((nm, art2. (t,
(40)
We continue bounding the last two terms by using the definition of sub-exponential random variables (r? (s) m2) and obtain
(P) + 2)²
Co²
x पFं.. -E(LA.a (ffm,,(()) 11 srzz.
40
< (exp
miny ()a((mm.))
2 m (M + 2)202
HJ (1) (exp
2n 2 m. (M + 2)202
ij (1)
-E(LA, l (t)a. Nriz
2n (tm.j)
(expp ()) + 2)
C
}) 1iz
miny Rija(bm)))
[1) exp { (t) da (M + 2))00²
} E(LAA (()mm.(t))e...m
M +
2n (t)
TigN (1) exp { (lm((m
22 Pe (M + 2)
El E[LA,alo (fnmm (1))a,m))
M +
2n (tm..)
43

---

Building on that, we establish
(m, (M)
Co
40
(exp {
miny ngj(bmmj) }) 11zz2.
2
X m. (M + 2)0²²
(exp
2 min, (t)
Xe +2)0² }) 1)|M BlLA, (o
(exp
min, n..6(mm.))
X² (P/ M)) +
Co²
22 2m/
El(exp
}) (exp
})
miny Mzja (bmos)
2 2miny ng,((()
d2 m.t (M + 2)0 (m((t)
(exp {
2 min (mp((mm))
- El(exp (P (m, (mmmm))) j)) +2)
Co²
22 m, (M 2) Nm Nm (t)|o²
miny (t (t+ +) 1) (exp
})
2(1 - co)
L/K
ming (t + +]
1./K+I
dd , (M + 2 Nm
(exp {
2(1 - cb) min, 11, (1+
where the first inequality uses the fact that (5,(()) 2 minj (1 and ng, (m.m)) ) 2 min, (z,.((m..) For the second inequality, the first term is result of min, (.,(())
miny (t++( Z miny n,,((1)+1
min, (f L/K
T since
(t,((t) > (L) = L/K K and the ratio is monotone increasing in n, and the second term is bounded through applying Proposition 6 which holds on event A.,5 and leads to
min (tmm) Z min nt 1-tta to)
j
wv min (t + 1) to
minn +) co minn 1)
(1 co) min (t,
Therefore, rewrite the above expression
X²02
(A +
El(exp( 2 minj Tij, 11)
2(1-00)
de (M + Nm)
de (M + +) Nm)())
| (0 (fmmm.((t))))
(1-
L/K+I
C'2202
Elexp( 2 miny (1 + (l
CX20"
< exp( 2 min, (t
where the first inequality holds again by the choice of P/(m,, dm,.. L and and the second inequality uses the fact that IA,, S
This completes the induction step and subsequently concludes the proof.
Proposition 12. Assume the parameter 8 satisfies that < <c= [e, M,T). In setting St, Sa. and Sz. for any m, i and t >> L where L is the length of the burn-in period, the deviation of Pm, (t)
44

---

satisfies that if (t) 2(K2 + KM + M), then with P(Ac,5) = - 76,
C1 logt
+ C2logt
P()m,;(0) -
Ac,b) P(Ar,) T
V
Ams
mm,((1)
Ci log'
C2 C2log
P(u: - (t, 2
V nmy (t)
+
7mm.((t)
(Ac,)) I P(Ac,)) T
Proof. By Proposition 7 we have Elimm, mi|A..s = 0, which allows us to consider the tail bound of the global estimator (t) conditional on event A.,8. It is worth mentioning that by the choice of C₁ and C2, we have
a C7
04 S CG
where 8² is 200²2
Note that since we set Rad
C₁ InT (l,
+ In we obtain (t))
C1 In T
(() Mul
Rad|Ac.6 < P( ull>
Ac,o,
(41)
nmm (t)
C2 In
P( (t) - Mil
Rad A.,)) < P(IAT (t) - mul
mm,s(t) Ar,s)
(42)
Cr lug T mm,((0)
On the one hand, if
1 i.e. (1) & C1 log (8) we have
82
a
C2 In T
(1) 1m/1
AA,,))
n (t)
Eill (2m (1)
Cu Ac.l
E[1 (1)-)aa
T 1A,5) ml))
= P(A{))
E
(SppA())((imm.(0)--)))) () (e Colan }1 mm.ste)
P(A,,)
1
(() mil) 1Ama]
< P(Ag,)
E exp(A(n) C2 In
(43)
kt))())
where the last inequality is by the fact that (00 mmyete) (00,) exp(A(n) C3 2
Caln
By the assumption that d < c, we have Proposition II holds. Subsequently, by Proposition and
Lemma 2 which holds since (t) 2 2(K K M M). we have for any {
Elexp (1( - 1 (t)m. $ exp ( 12
2 02).
(44)
Likewise, we obtain that by taking = A.
Elexp (1(=iT' (t) + H4) 1 (o(fnmmat))ean S exp { X2
--2
j2)
(45)
2
With 44 and 45 we arrive at for any |>|
1 that
a
E eexp (A( [7 (f) [4)1 (f $ 2 exx { -0)
(46)
2
45

---

Again, we utilize the law of total expectation and further obtain that [A(=)l < 4
1
exp(A(m) (t)
43
E
LAc.o (f (t)mm)))
p(Ar,))
exp(A(n)
1
1
E ((e)p(((n)((Am))))
Aal) (((Rm,i(t)mm...
p(A,,))
exp(X(n)
Co In
(8)
exp { >²(1) Ca (.)
2 P(A.6)
E exp(A(n)
0²11
(47)
where the first inequality holds by (46).
C. Ton'T Promett (C)
Note that the condition
implies that R2m (t) <
In In
which is the global optima of
@2
2
the function in 47). This is true since (t) S C1 log T
o² (σ)
(C2log Ci
Henceforth, (47 is
monotone decreasing in X(n) E (0, ( and we obtain a minima when choosing X(n) 1 and using the continuity (47p.
Formally, yields that
477
S 2
Fl
exp 2n 02]]
p(Ac,)
expla C2 IT
a mm,
1
Elexp( 02 1 In H
P(Ac,))
2a
a (() 2
1
expl expl-4logT)
(48)
P(Ac,))
P(Ac,s)
where the last inequality uses the choice C2 and the condition that - 02 In which holds by the following derivation. Notably, we have
S -4
1 C In a
C2 In #²
0²
2a2 2020²
2a
st))
a h
C2 g²
2a
C2 a²
Ci To
C log
2
C2
1022
P!.il!)
1
Ca
(t)
C
2
C
C1 Cogog
C1
log T < -4log T
(t)
20
2
C
2Co
(t)
where the first inequality uses (t)
C1 In and the last inequality is by the choices of parameters
(
4.
2C
C₁ log Rm, (80)
On the other hand, if
1 i.c. (t) 2 C1 log T o² (ā]z. we observe for [A(n)] <
g2
C1 In Rmm (t)
P( (t) - mil >
Ac,s)
(²(n) σ
< 2 P(Acs)
El
exp
(49)
exp (M())
C In (t)
2
by same argument from (43 to (47 replacing
Ca In with (B)
Ci in T (m)aa()
When choosing X(n)
Cy log. T
log
that meets the condition X under the assumption
1 and noting that
82
46

---

Ct 2 4, we obtain 2C
C1 log
49
2
E. exepp(
}1
p(Ac,5)
n2 (t)
C₁ log
1
Elexp(
p(Ar,s)
Am,,i(1)
2C
Rm, (f)
s p(Ac,))
= P
To conclude, by 41 and (42 have
P(InT (t) - 14l Rad Aao) s(
which completes the proof.
Proposition 13. Assume the parameter 5 satisfies that O < f<, An arm l is said be sub- sub-optimal if k + where i' is the unique optimal arm in terms of the global reward, i.e. i" arg max ΣN M J.. Then in setting S1.S2 and S3, when the game ends, for every client m, 0<E< < 1 and I' L, the expected numbers of pulling sub-optimal arm k after the burn-in period satisfies with P(A,,5) = Te
El (T)
160, log T 4C₂ log T max((
A: 1,2(K² MK + P(A + -K2 (2M 1)K
A,
O(log
Proof. Recall that Rod
C In (t)
In (t)
We again have ot" = holds when any of the
following conditions is met: Case 1: (t) S (t) K, Case 2: jum,i 1mm,i-44 14
G In In mm) (B)
Case 3: - + Ma-
C. IT
C and Case 4: pa 14 2(1 Dmm (8)
In CaInT m.)(())
mm,s())
By 30). the expected value of (t) conditional on A reads
E'Tm, (A)ss
T
T
=l+
Σ
P(Case2, mm. - 1) 1|A,.)) +
Σ
P(Case3, nm, - 11Ac,))
t=
1=L+1
T
T
Σ
P(Casel, at = i, - 1) 2 2 (A..)) +
Σ
P(Case4, Rmm - 1) 2 (|Ac,5)
L=
1=1-1
(50)
where is specified as 1 = max [[ 4C1 log
1,2(K2 MK + M)) with A, = =/1 - Pk.
A
For the last term the above upper bound, we have
T
InT (t)
C2InT (t,
P(Case4 : /4 +2(
+
> M1g=, nm, 11) 2 =0
(51)
1=L+1
since the choice of satisfies 2 max(
160, log
4Ca log A.
122K2 + MK)).
A
47

---

For the first two terms, we have on event Ac,6
T
T
P(Case2, -1- (1 +
Σ
P(Case3, - 1) 2 ((Ar,))
Cn C2
P(im,
u4 V (t)
Ac,s)+
(t)
T
Ci
Cn
Pl-Mmm.. + +u
im (1) (Ae,))
mm (1)
t=1
Σ P(A D(PAATT
Σ
P(A
S P(Ar,)TT
2
(52)
where the first inequality holds by the property of the probability measure when removing the event (t (t- 1) 2 and the second inequality holds by Proposition [2 which holds by the assumption
that 6 < c.
For Case 1, we note that Lemma ! Timplies that
(tm,i(t) > (t) - K(K + 2M)
with the definition of (t,
+ 1) max + 1), (t.. E (t).
Departing from the result that the difference between (t) and nmm (t) is at most K(K + 2M).
then present the following analysis how long takes for the value (tm,((t) + (t,,(t) to be smaller than K.
At time step i, if Case holds for client m, then a (1++)] 1) is increasing by 1 on the basis of nmm (t).
What follows characterizes the change of N (t+-1.+)). Client m satisfying (t) < N Nm.(t) K will
not change the value of Nm. (t + 1) by the definition Nt, +
max (nm, (t + 1), N (,,(().3 (t).j e
Nm(t)) Moreover, for client j E Nm (t) with (ta(() < N2,((t) K, i.. Nta(t (f + 1) will not be affected by nz.(( + 1) I (t, + Thus, the value of Nm. +
ma
1), ((), E N. (()} is independent of such clients. We observe that for client j E Nm (1) with (t)x(t) > (t) K, the value (t) will be the same if the client does not sample arm i, which leads to decrease of 1 in the difference a (t) + (t). Otherwise, if such a client samples
arm i which brings an increment of to (t). the difference between (t) and Nm, will remain the same. However, the latter has just been discussed and must be the cases as in Case 2 and Case 3, the total length of which has already been upper bounded by P(A..6)T as shown in (52).
Therefore, the gap is at most K(K + 2M) K P(A,,))ss, i.e.
T
Σ P(Casel, at" =i, (t 1) 2 ((A,,)) S K(K- + 2M) K+ P(A.s)T3
(53)
Subsequently, we derive that
E mm [A,
2
< +
+ K(K + 2M) K + P(A +0
P(A,s)TT
2T
-I+
+ K2
+ (2M - 1)K
160, log
4C, log
max(
1. 1,2(K2 + MK + M)) +
p(A.,) + +K² + (2M - -1K
A
A
where the inequality results from
50
51
52
and 53
48

---

F.2 Proof of Theorems
Theorem 1, For event Ac and any 1 e, have P(Ac,)) 2 7e.
Proof. Recall that we define events
A [Vi 2 I., IP: cE - 6);
A2 (Vt 2 L, Vj. m,
min Em.j S to S co min ni,((t + 1)}.
A3 [Vi 2 L, G. is connected]
where A1, A2, A3 belong to the o-algebra in the probability space since the time horizon is countable, iec. for the probability space (St, 2, P), A1, A2, A3 E E.
Meanwhile, obtain
P(A)) = P([Vt 2 L. cEi S (.) 2 P(n 2 L, Pt cE ()]
2 1 Σ (1 ((n 2 La cE s ())))
2 1 Σ (1-c))
=1 3c
(54)
where the first inequality includes all settings and I, L... the second inequality results from the Bonferroni's 's inequality and the third inequality holds by Proposition [ and Proposition
At the same time, note that P(A2) = P( 2 L, Vj. m. + min fm.. I to S co min nI, + 1)})
P(N > TIN.y Vj, m, t min I to cn 1 ni, 1)})
21 E p(fv 2 Leg Vj. + min tm.j S to S co (t 1)})
21 (1- (1 c)) =1
(55)
where the first inequality is by the definition of L, the second incquality again uses the Bonferroni's inequality, and the third inequality results from Proposition 6
Moreover, we observer that
P(As) P([Vt 2 L, G. connected))
2 P(n 2 L,,, Ge is connected))
2 1 Σ (1 P((Vt 2 Ly,, G. is connected)))
21 (1- )) 1=1
(56)
where the first inequality uses the definition of L. the second inequality is by the Bonferroni's incquality and the third inequality holds by Proposition 5 and the definition $2; $3 where all graphs guaranteed to be connected.
Consequently, arrive
P(A.s) P(A n A2 Aa)
P(Af A5 U US)
2 (P(49) + P(4)) + P(A5))
(3e 3e +) 1
where the first inequality utilizes the Bonferroni's inequality, the second inequality results from (53), and (56).
54
This concludes the proof and shows the validness of the statement.
49

---

Theorem 2. Let f be function specific to a setting and detailed later. For every 0 < é < 1 and 0 0<8= < M,, in setting $1 with 2 1/8 + 2 (MT)) 82 and $3, with the time horizon T' satisfying T 2 L, the regret of Algorithm with i,t,
C. In satisfies that (m,
4C1 log
2T²
E| SL
maax
2,2(22 + MK + M)) + (P((A.))
+ + + (2M 1)K)
where the length of the burn-in period is explicitly
In
4K
logg T
In
8 10
1
+ A
In
4K log, T
L = max
2c
25
2r
252
co
In pr
X
28
co
L.
1/2
K In(
MT)
In
1 1+ X In
T
In
2 A
+ 25
28
In pr
1 - À 28
CO
with X being the spectral gap of the Markov chain in 82, 83 that satisfies - X D" p" (M) < and co co (K mingzi- Di, M, e,,,)), and the instance- instance-dependent constant C So² max (1 12 (M+22)
tn 4+4+1'
M
Proof. The optimal arm is denoted as i satisfying
Σ PT
arg max
For the proposed regret, we have that for any constant L,
M
Rr
maxx
T
M
T
M
m
M
M
Pam
m=1
1=1
m=1
M
M
T
M
M
m Mayi
+
P
Σ
M
M
M
M
m=1
m=1
(=++1
m=1
m=1
1
Σ
Σ
m
M
M
M
1
L+
(ni:
Σ
M
t=L-1
m=l
M
K
= L (T L)
Pr
T ( yp
M
where the first inequality is by taking the absolute value and the second inequality results from the assumption that 0 < pd < 1 for any arm i and client j.
50

---

(T L) where by definition R is the number of pulls of arm at chient m from time step L + time step T, which yields that
Note that L==1 2m=1 Rm. (T)
K
M
K
1
Rr S L
Rm pT)
Pom (T)
M
M
2=
i=1
m=
4
1
Σ
Tom (T) pF")
M
K
S
Σ
Rm, (T) 1e."))
M
mippe - >0
= = Σ Σ
nm, (T) p,!").
ii mapt -PP
where the second inequality uses the fact that Emauy pm mm (T p1, S 0 holds for any arm i and the last equality is true since nm, i (TT) p1! 0 for i i" and any
Meanwhile, by the choices of 5 such that < c= M,,, we apply Proposition 10 which leads for any client m and arm ii,
4C1 log T E fm (T)(Aee) & max [[
2n
A 1,2(K2 + MK + M)} +
+ + + (2M 1) (57)
3
As result, the upper bound on Rr can be derived as by taking the conditional expectation over Rr on A
E E Ac,s)
+
1
1
Σ
Σ
pTT))
(58)
M
sefi" mpp
p. >0
L+
1
Σ
(max {1
401 log T
1,2(K² + +K)] + 2x²
K2 + (2M 1)K) 147)
M
A7
ifi mip 11
L++
1
4C1 log T
2x²
mmax
[|
1,2(K2 + MK)}
+ + xx2 (2M 1)K)
Σ
(M pa"")
M
3
map
>0
(59)
where the second inequality holds by plugging in (57p
Meanwhile, we note that for any + i*
Σ
10 +
Σ
(n - pT)
>0
map
4 <0
M
(1TH 14
m=1
= M A > 0
and
Σ
(N |.
M
51

---

which gives us that
Σ
(4 -9
ma P. >0
MA,
Σ
(1T pT))
map P <0
= MA. +1
Σ
(10 Th
11 1
MEAT -0
< MA, M M= M(A
(60)
Hence, the regret can be upper bounded by
59
4 E(A ()xx {1 401 log T
2T
1,2(K² + MK + M)}
+ K²² + +2M - K)
A
3
0 [L, log T})
where the inequality derived from 660p and is the same constant as in the definition of Ac,6-
This completes the proof.
Theorem 3. Let f be a function specific to setting and defined the above remark. For every O << c < and O < < (,,, in settings S1 with e 2 1 + 2 (NiT) ~ं ,S,, S3 with the time horizon T satisfying T 2 L, the regret of Algorithm with F(m, i,t) V satisfies
C1 In Cs T (m)
pm,((()
16C1 log T
4C2 log T
P[RT|Acd
+ Σ (A: (A,+1) +1 (max((
1.2(K2 +MK + M))
A
A:
+
K + (2M 1)K)
T3 P(A. T3
where L, C1 are specified as in Theorem and
2'
Proof. By the regret decomposition as in 58
we obtain that
E|RT A
S
1
Σ Σ
Elum, (T)) p.").
(61)
M
By Proposition
13 have that with probability at least 7
E [mm, (A,
16C log
4C2 log T
< max((
1,2(K2 + MK + M)) + P(A,,))T + K + (2M 1)K.
A?
A,
(62)
Following
(60 gives that
Σ
(NT - -4T S M M(A + 1).
(63)
Therefore, we derive that with probability at least P(Ac.) = 1 7
(max([ 16C, log T
4C₂ log T
F A < + Σ (A++1)
1.2(K2 + MK + +M)
A
A:
4
+
+ + + (2M 1)K)
sT
52

---

which completes the proof.
Theorem 4. Assume the same conditions as in Theorems and 3
The regret of Algorithm
satisfies
that
4
B[RT| S
P(Ac,)T3 +
2
(1 + max (Ctaaa(VGiT,,CCCT)))) + 2M) - K
P(Ac,)) (T )+
+ C2In+ GGITTTTTTTT +2
= O ln.).
where L1 max(L, + MK + M))), L, C1 is specified as in Theorem 2 and C2 2.2 The
involved constants depend on a² but not on A..
Proof. Define U (i) and L (i) as p. (1) + Rod(i, m, 1) and (TTT (1) Rod(i, m, t), respectively, Ci I C2 In'f' We observe that by definition, where Rad is previously defined as Rad(i, m,t) t) V (m, Rm)
the regret Rr can be written as
1
T
M
RT
(uso - Maye.)
M
1=1
m=1
T
1
Σ
(14.
Uh (a + U (o L'm (d L'm (a - M
M
1=1
m=1
Subsequently, the conditional expectation of Rr has the following decomposition
E(Rr|Acd
1
(Elpa Uh. Uh, (a + (am)) L (Amm)))))) + E(Li, (o'm) - Mas. (Ac
.M m=1
In+ +
Σ
(Fl (()) ( U Ac,)++
1=
E (a'm) - I (o Ac,o) + ( poo (Ac,6)
(64)
where I = max I,, 2KK + MK + M)).
For the first term, we derive its upper bound as follows.
Note that
Ely U (i*) (it)
< El(u- - -n
Ellu- 10
A -0
I Elyu- 1 1,. Ac,o)
I El - -1.0)))
= P(ur- U (i") ) > 0|Ac,8)
P(u+ 12 Rad Ac.o)
< P( - - (0) > Rad A.6) S s)
(65)
where the first inequality uses the monotone property of El:), the second inequality omits the latter negative quantity, the third inequality holds by the fact that S uu S 1, and the last inequality by Proposition 12
53

---

In like manner, we have that the last term satisfies that
2
E (( Mas Ae P(Ac,a)T
(66)
by the same logic as the above and substituting i* with ain- and thus we omit the details here.
We then proceed to bound the second term. Based on the decision rule in Algorithm 2 we have either
E (1*)((())
U (a |4,
Tim.i()) Nm,((t) K. This is equivalent
El ) U [Ac,s]
El (2') - U I (4)2 K Ac,
ElU (i*) U (o 1m (1t) . x Ac,66
El U (amm) nm, (1)= (1)
(1)- Ac,s) E ( (0) (1) Ac,a).
(67)
By definition, (1') = pi- + Rad(i", m, 1) implies that U (t)(t") & 1 + Rad(i", m,
which leads
Fi((1 + Rad(i", m, ()) (1) Ac,o) max Rad(i", m,
Ac.
(1 m Cn C2 In IT) (1) Acc Ac,6)
and subsequently
1
Σ Σ ElU (om)))))
M
+
(68)
M (=L++ m=
Following (53) that only depends whether clients stay the same page that relies the transmission, we obtain
Σ Fl F0 K(K +M) K
2
P(A,s)TT
which immediately leads to
s (1 + max In (K(K + +M) K s(A
Afterwards, we consider the third term and have
FUU (amm) 1 (Ac,) Fad m, Ac,5)
(69)
Putting 65
66
68
69
all together, we deduce that
M
64
< 11
1
Σ Σ
2
F(2 m, ()|Ac.)) + P(Ac,s)T4
2
M
P(Ac.)
t=L1
2
(1 max
Ci CTTTTC2TT7) (K(K + 2M) K
6(Ac,))TT)
Sh + P(A.
+ M
1
ΣΣ
Σ
(E]2Ra((o', m, 6))+
73
t>4
2
(1 (ax In (K(K + 2M) K P(A
54

---

Meanwhile, we observe that by definition
1 M
Σ E
(E(2Rod(a a m. s)l)
ΣΣΣ
E[]Rad((, m, m, Ac,ol)
M
am L>L
C In (t,((t)
C2 In Ar,s). (t)
ΣEΣ>
2
(70)
M
M1
1>
By the of the Harmonic series, have
12
I C2 Cn + C2 +
(71)
(l)
1S4
Meanwhile, by the Cauchy-Schwart inequality, obtain
C2 In (1)
Rm 1>
$ V
1)
)2)
(t)
< v Ci In TTh
where the last inequality again uses the result on the Harmonic series in 71 Therefore, the cumulative value can be bounded as
ΣΣ (C2(In))² + +2 In T(nT 1))
70
S
M
( V
Using the result of 770.. we have
64 < L
P(A.s) +
C2 VC
1))+
2
(1 max IT,,T,, (K(K + 2M) K + s)
= O(max( In (In
which completes the proof.
G Choices of parameter co in Theorem 2
that co a pre-specified parameter which are different different settings. The choices of cu are as follows. Meanwhile, we need to study whether the possible choices of co explode terms of the order Tf
Parameter co We
Remark (2). The regret reads
4 log T 1) + (K -K-KKK)6 1)(2(K2 (K-1)(( MK) + A
2m
E [r S + C2
Σ
R + (2M 1)K)
3
55

---

with L denoted as L max L1, Ls. = maxfa1, a2, as, bi bz by } and C₁ denoted as max m J. where parameters a1, 02, 03, b1, b2, by, e are specified
In 27
d1 20
b 4K log2 T
In 10
1 + x A
42
+5
In np"
1 1 X 28a
b2 4K log,
In TO
1 1 In
27
25 1 À 282
In p K Klnn MT)
by
In( -
6 16 4(M +2)
3M
f = 16(M + 2) + 4Mdmm.))
This function of eo is non-differentiable which brings additional challenges and requires a case-by- case analysis.
Let a {ai, 02 0z} and (bb,bb, ba). Then continue with the decision rule in the previous discussion.
Case 1: there exists eo such that 2 L.e. and & S 1 Then Rr is monotone increasing due to C₁ and co = b gives us the optimal regret RT.
Case 2: if S b.e co S
00
if < f.ie co 1 then min f2 1- - /) is the minima.
- -else we have co 2 1
if1 {> > it leads to contradiction and this not be the
* else
a' we obtain
b e <
4log A
2T
RT
1)(2(K2 (K-1 + 1 MK) + K2 (2M - 1)K)
+
+
cp
CO
which implies that the optimal choice of co is Vo+ / Enger (1 (1
Ab
if 9 Vb+ ve Ei $lox
Vb
a this gives us the final choice of co and
the subsequent local optimal regret RG.
elif Jo+ v E subsequent local optimal regret is R2.
vB
< 5, the optimal choice of Co is and the
Flog
else the optimal choice of ca is and the subsequent local optimal regret is R2. Compare R2 and R2, and choose the co associated with the smaller value.
56

---

The possible choices of are L2 min
(1
8).
vb
i.e.
vot, v V.Dvrr (1 (1
1)
1j
+ b2
+ bb
b1 + b2 + bg
16 3M
1(M+2)
vb
Co
min
1
01 + a2 + a3
01 + 02
+ 03
16(M + 2) 4Md
Vb+ /e /eCifs- (1
(1=log
bi + b2 + by
+ 0 + 0z
16 4(M+22
vb
min
1
3M
01 + 02 +03
+ +
16(M - 2) + 4M
vb+ VeEigi- (11log A
In( AT
8K log T
In(
In 22
2 In
+ 50 1+A In
20
lag
1-X 20
8K log T + KIn MZ)
16 4(M+2) 3M
min {
In 27
4 2
+ 50
1+1
16(M + 2)(1 + 4M 4Md
28
Ip
1-X 23
log T K Iu( AT) In( T
8K log T KIn
+ Ve Eier (1 T D7
(1
In[
Iu M7
8K log T+
Ind r-o)
which implies the choice of co is between
and
88 log T4
Ial MTT Inc y
Eipeo ( 1
TD
16 42
16(M42)) Meanwhile, we observe that the choice of co satisfies
16 ((+2)
A S RT(11 16(M 2) + 4M m.t
3M
Ollog T).
57


Reviews:
[{"review_id": "LBc9IE6Dbe", "reviewer": "Reviewer_a3u4", "summary": "This paper studies a multiplayer graph bandit setting. In particular, they consider  heterogenous rewards in which the mean rewards for each agent are different, and are allowed to be both sub-gaussian and sub-exponential. They also consider random graphs between agents, which dictates which agents are allowed to communicate their rewards with each other. This graph structure is allowed to vary with time. They consider two types of graph generations as well as two types fo reward families for a total of 4 settings. \n\nThey propose an algorithm with the following components (1) graph generation, (2) DrFed-UCB (burn in period), and (3) DrFed-UCB (learning period). \n\nTheir regret analysis achieves optimal instance dependent regret on the order of log T with high probability.", "questions": "I'm not sure I understand S_1, S_2, and S_3. This is described in the first paragraph of sction 3.2 and it's worded quite confusingly. for isntance I'm not sure what M is referring to in describing Seettings 1.1, 1.2, 2.1, and 2.2. Also ,whcih setting is theorem 4 for? S_1, S_2 or S_3?", "limitations": "The graph generation is limited to two distributions (ER and uniform). Furthermore, their algorithm can be costly in communication. ", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "This paper considers a setting that is very general and interesting as well. For instance rewards can vary as well as the communication graphs which are generally assumed to be fixed. Furthermore, they allow for heavy tailed reward dsitributions where as standard bandit literature only considers subgaussian rewards. Their results seem to be very strong for this rather general setting. ", "weaknesses": " I think the organization of the settings as well as the key results can be better (Maybe each setting gets its own theorem latex environment). Moreover, I'd use section 3.2 to list the regret bounds, and outline the analysis in a section following that (theorem 1 can go in that section). Kind of related to this point I think the statements of theorem 2 , theorem 3, theorem 4 are too detailed. Maybe just state the regret bound and define the constants in paragraph below it or in the proof. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for reviewing the paper and providing the detailed comments and suggestions. For the questions and limitations, we would like to include some responses as follows. \n\nQ1. I think the organization of the settings as well as the key results can be better (Maybe each setting gets its own theorem latex environment).\n\nA1. We have improved the presentation of these settings in the revised paper, as detailed in Table 1 in A4, to provide a clearer structure for the setting information. In addition, we will use different latex environments for the results corresponding to different settings.   \n\nQ2. Moreover, I'd use section 3.2 to list the regret bounds, and outline the analysis in a section following that (theorem 1 can go in that section).\n \nA2. We will include a summary of instance-dependent and instance-free regret bounds in settings $s_1,s_2,s_3,S_1,S_2,S_3$ in Section 3.2,  and put the formal statements of theorems and the analyses to Section 3.3.  \n\nQ3. I think the statements of theorem 2, theorem 3, theorem 4 are too detailed. \n\nA3. In the new Section 3.3, we will revise Theorems 2, 3, and 4 by providing a concise version that emphasizes the order of the regret bound. Additionally, we will include remarks immediately after the theorems, paraphrasing the details about the constants and parameters, to enhance the clarity and presentation of the results. \n\nQ4. $S_1, S_2$, and $S_3$ the first paragraph of section 3.2; M; Theorem 4\n\nA4. We apologize for the unclear presentation and will include a table in the paper, which is shown in the uploaded pdf, to outline the notations for each setting (Setting 1.1, 1.2, 2.1, 2.2; $s_1, s_2, s_3, S_1,S_2,S_3$). When defining Setting 1.1, 1.2, 2.1 and 2.2, we are considering the possible combinations of graphs and reward assumptions for any $M$. If we further impose constraints on $M$ within setting 1.2 to be either $[1,10]$ or $[11, \\infty)$, we obtain setting $s_2$ and $s_3$ respectively. Likewise, we define $S_2$ and $S_3$ by applying the same $M$ conditions in setting 2.2. \n\nTheorem 4 holds for setting $S_1,S_2$ and $S_3$ with sub-exponential rewards, as well as $s_1,s_2$ and $s_3$ with sub-gaussian rewards. We apologize for the typo in the sentence \"Assume the same conditions as in Theorem 2 and 4,\" which should read \"Assume the same conditions as in Theorem 2 and 3.\"  In Theorem 2, we address settings $s_1, s_2$, and $s_3$, and in Theorem 3, we address settings $S_1, S_2, S_3.$ We will include these specific setting specifications in the revised statement of Theorem 4. \n\nQ5. The graph generation is limited to two distributions (ER and uniform). \n\nA5. Thank you for your perspective and suggestion regarding the graph assumptions. We would like to add that this paper considers these two types of random graphs for the following reasons, both from the edge and the graph perspective.\n\nThe E-R model, comprising $G(M,c)$ and $G(M,m)$, is a seminal random graph model. Particularly, $G(M,c)$ is commonly used for subsets of graph edges, as in mean field games, majority voting, and multi-agent MAB experiments [1] where it's fixed after generation. This inspires its integration into the decentralized distributed multi-agent MAB problem. While other models like edge randomness [2] exist, they are less prevalent in the literature.\n\nOn the other hand, the E-R model $G(M,m)$ generates graphs uniformly with $M$ nodes and $m$ edges. In decentralized multi-agent MAB problems, connectivity is often assumed for obtaining global information in finite time. This motivates us to explore a uniform distribution in the connected graph family. We adapt MCMC techniques where matching and coupling are well cited applications [3], from graph generation, inspired by [4], to generate uniformly distributed connected graphs, providing the very first finite-time convergence rate analysis. This offers insights into the domain of random graph generation.\n \nWe appreciate the comment on the possibilities of other random graphs, which inspires us to consider other distributions besides uniform distributions, random weighted graphs [2] and waxman random graphs [5], as future directions. \n\nQ6. Furthermore, their algorithm can be costly in communication.\n\nA6. In federated learning, research has explored communication costs defined as proportional to model sizes [6]. In the context of multi-agent MAB, we may consider defining costs as the number of estimators, yielding $O(MK)$ due to $M$ clients each maintaining $K$ estimators. Existing work on decentralized multi-agent MAB [1,2] has exhibited the same order, although communication costs have not been addressed.\n\nAlternatively, for multi-agent MAB with communication cost, cumulative building costs have been defined [7], where each edge incurs a constant cost. This implies communication cost is proportional to the number of edges or communication rounds. In our random graph model, the expected edge count is $\\frac{M(M-1)}{2}c$, implying worst-case $O(M^2)$. Comparatively, this cost aligns with $O(M^3\\frac{\\log T}{T})$ in [7]; it's more favorable for $M\\log T \\leq T$ (e.g., small $M$ or large $T$), and less favorable otherwise (e.g., $M = O(T)$). Our algorithm's communication cost is similar to that in [7] for small $M$ or large $T$. Despite having chances of a larger communication cost, we extend the time-invariant connected graph in [7] to time-dependent random graphs.\n\nThe GIS protocol in [7] indicates potential to enhance efficiency ($O(M^3\\frac{\\log T}{T})$), particularly with small $M$ or large $T$. We appreciate your comment and for raising this important aspect for further consideration.\n\nFrom a time perspective, parallel synchronization can optimize communication. Clients could independently communicate information they possess ((although this might raise concerns about channel congestion if only one communication channel is available per client). This strategy could accelerate communication.\n"}, {"review_id": "Ubkr0kvsEh", "reviewer": "Reviewer_NP2Q", "summary": "The paper studies stochastic multi-armed bandit over a network of agents communicating locally. Specifically, for each of the K arms, each agent has an associated underlying arm-mean. The agents can only communicate with their neighbors in each round to exchange information. The goal of the agents is to pull arms so that the regret with respect to the average arm-mean averaged over the agents is minimized. This is a challenging problem since the agents can only infer their arm mean from the observed rewards and must rely on information sharing to learn the average of the arm means averaged over the network.\n\nIn order to model information sharing, the paper assumes that the communication graph over agents is a stochastic process that possibly changes over time. This allows for the information about an arm collected by an agent to percolate over the network so that all agents can potentially learn of the mean of an arm averaged over agents. However, the agents never have full information on the graph connectivity and at each time, can only observe who their neighbors are. \n\nIn this scenario, the paper proposes an algorithm based on initial coordinated exploration and information sharing followed by UCB based on estimated network sample average over arms. The proposed algorithm is elegant and practical. ", "questions": "Can the authors substantiate the insights using synthetic simulations? For example, it will be nice if the authors can\n\n-  \"visualize\" the flow of information in the algorithm, \n-  the impact of heterogeneity to the resulting regret\n-  Impact of the graph generation process on regret. For example complete graphs is the easiest while a ring graph is the hardest? Perhaps the graph spectrum plays a role in the regret? \n\nOf-course these are a lot of changes, but will appreciate intuition/insights on these questions and will make the paper more complete.\n\n***EDIT Post Rebuttal:***\n--\n I thank the authors for the thorough response and would encourage them to add it to the camera ready. I would further propose to add two related references to the additional list of references. \n\nSankararaman et.al. Social Learning in Multi Armed Bandits, SIGMETRICS 2019\n\nChawla et.al. The Gossiping Insert-Eliminate Algorithm for multi-agent Bandits, AISTATS 2020", "limitations": "NA ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "A clear articulation of the problem and an elegant algorithm to solve it. Good analysis of the algorithm so that a reader can follow along. High probability bounds that do not average over the randomness in the graph generation process that is typical of results in this area.", "weaknesses": "Lack of experimental evidence. Given one of the core contributions of the paper is an elegant algorithm, presenting synthetic simulations will substantiate the contributions of the paper. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for reviewing the paper and for sharing the suggestions and perspectives. We would like to add some responses as follows. \n\nQ1. Lack of experimental evidence. \n\nA1. We will add an experimental illustration of the proposed algorithms using synthetic simulations to the paper, and compare these algorithms to existing ones as benchmarks. While we were not be able to conduct a comprehensive experiment during the response period, we present the details which we will use for running the simulation experiments. The official comment below the rebuttal includes details on data generation, models, benchmarks [1,2], and model evaluation.\n\nQ2. Can the authors substantiate the insights using synthetic simulations? For example, \n\na) it will be nice if the authors can \"visualize\" the flow of information in the algorithm\n\nA. We will add a flowchart to the paper to visualize the flow of the algorithm. \n\nb) the impact of heterogeneity to the resulting regret\n\nA. Indeed, heterogeneity does impact the regret, and it is a great point to examine the degree of this impact through numerical experiments.\n\nTheoretically, the current methods and regret bounds are applicable to both homogeneous and heterogeneous settings. However, algorithms developed for homogeneous settings may not be effective in heterogeneous settings. Developing solutions that provide guarantees for heterogeneous settings is one of our motivations. It is true that smaller regret is possible in homogeneous settings, and the regret bounds do not reflect such differences between the two settings. This necessitates a direct comparison of exact regrets through numerical experiments.\n\nWe introduce a variable denoted as $h$, which refers to the discrepancy, representing the heterogeneity of the problem setting and defined as $h = \\max_{m,j,i}|\\mu_i^m - \\mu_i^j|$. During the generation of synthetic datasets, we generate various settings with different discrepancies, such as $h = 0, 0.1, 0.2, \\ldots, 1$, while keeping all other parameters/settings constant. Subsequently, we execute the algorithm across these datasets and compare the regrets among different settings.\n\nc) Impact of the graph generation process on regret. For example complete graphs is the easiest while a ring graph is the hardest? Perhaps the graph spectrum plays a role in the regret?\n\nA. We appreciate the perspective on the dependency of regret on graph generation. In deterministic graph scenarios, [3] investigates regret under various graph structures, including star, circular ring, complete, and d-regular graphs. This study demonstrates that the circular ring graph presents the most challenging scenario with the largest regret, while the complete graph is the simplest. Notably, their regret bound is influenced by the graph's diameter and thus by the graph's spectrum.\n\nIn our cases involving random graphs generated by MCMC which might have different spectrum at different time steps, the regret bounds exhibit a dependence on the spectrum of the associated Markov chain, denoted as $\\lambda$ depending on the targeted distribution $f$ of the graphs. In our study, we focus on random connected graphs, where $f(\\cdot) = P(\\cdot | G \\text{ is connected})$. This relationship can be expressed as $1 - \\lambda  \\geq \\frac{1}{2\\frac{\\ln{2}}{\\ln{2p^*}}\\ln{4} + 1}$, where $p^* = p^*(M) < 1$ is specific to the distribution $f$. \n\nNumerical experiments could establish such dependencies for different graphs besides the studied graphs here. To observe the algorithm's regret given complete graphs, we set the parameter $c$ in the E-R model $G(M,c)$ to $1$, with the regret being computed at the end of the game. If we consider circular ring graphs or star graphs, generating the graph becomes feasible in polynomial time due to the small sample space ($O(M^2)$ or $O(M)$). Following this, experiments could be conducted using these graphs in combination with our main algorithm, allowing us to examine the resulting regret accordingly. For the case of ring graphs, a family of random ring graphs might be established by adapting Algorithm 1 [4]. In this case, the target distribution would be $f(\\cdot) = P(\\cdot | G \\text{ is a connected ring graph})$. Developing an MCMC simulation method for generating graphs based on this distribution, as well as for generating other types of graphs like d-regular graphs, presents a potential direction for future exploration. One conjecture is to initialize the distribution as $P(|G \\text{ is a ring})$, which requires knowledge of how to randomly generate a ring graph. Following this, the MCMC method outlined in Algorithm 1 could be employed.  \n \nThank you once again for the suggestions and perspectives on the numerical experiments. We hope the above illustrations could be informative. We will add the numerical experiments to the paper to establish the tightness of the dependencies of the regret bounds on the various aspects of the settings.\n\n[1] A. Dubey and A. Pentland. Cooperative multi-agent bandits with heavy tails. In International Conference on Machine Learning, 2730–2739, 2020.\n\n[2] Z. Zhu, J. Zhu, J. Liu, and Y. Liu. Federated bandit: A gossiping approach. In Abstract Proceedings of the 2021 ACM SIGMETRICS/International Conference on Measurement and Modeling of Computer Systems, 3–4, 2021.\n\n[3]  T. Li and L. Song. Privacy-preserving communication-efficient federated multi-armed bandits.466\nIEEE Journal on Selected Areas in Communications, 40(3):773–787, 2022\n\n[4] I. Gitler, E. Reyes, and R. H. Villarreal. Ring graphs and complete intersection toric ideals. Discrete mathematics, 310(3):430–441, 2010."}, {"review_id": "2WwpLy5Oes", "reviewer": "Reviewer_3jx9", "summary": "This paper presents a novel algorithm for solving decentralized multi-agent multi-armed bandit problems for two graph dynamics under both sub-exponential and sub-gaussian reward distributions. Their whole algorithm framework can be divided into a Burn-in period and a Learning period, ensuring a process warm-up phase before getting UCB-type estimators. The paper includes detailed theorems and proofs in both the main manuscript and appendix with regret analysis.", "questions": "1. In line 368, is there any typo mentioning the same conditions as in Theorem 2 and $\\textbf{4}$?\n2. In line 312, the 3rd and 4th terms are exactly the same. Is there any typo?\n3. Could you please elaborate more about how you get L1 in theorem 4?\n", "limitations": "No", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. Authors fill in the gap in the multi-agent multi-armed bandit problem with the intersection between heavy-tailed reward distributions and heterogeneous settings with time-varying graphs.\n2. The paper is clearly written and easy to follow.\n", "weaknesses": "1. The paper is full of details but without a conclusion to re-emphasize the main statement and contribution of this paper.\n2. Please refer to the questions\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the review and providing the suggestions and insights. We would like to add responses as follows. \n\nQ1. The paper is full of details but without a conclusion\n\nA1. We will incorporate a concluding section into the paper, as shown in the official comment.\n\nQ2. In line 368, is there any typo mentioning the same conditions as in Theorem 2 and 4?\n\nA2. Thank you for bringing this to our attention, and we apologize for the typo. The correct phrase should be \"Assume the same conditions as Theorem 2 and 3,\" where Theorem 2 and Theorem 3 refer to settings $s_1,s_2,s_3$ and $S_1, S_2, S_3$, respectively. This has been revised in the revised paper.\n\nQ3. In line 312, the 3rd and 4th terms are exactly the same. Is there any typo?\n\nA3. The 3rd and 4th terms are the same. This term is due to the convergence rate of the simulated graph based on Algorithm 1 and of the empirical matrix $P_t$, given the uniform random connected graph that has a dependency on the spectral gap $\\lambda$. Since both setting $s_2$ and $s_3$ are under the uniform random connected graph assumption generated by Algorithm 1, and they only differ in the number of clients $M$, this term appears twice in the length of the burn-in period.  One alternative approach is to retain only one instance of this term in the expression for $L$, written as $L = \\max\\{\\frac{{}\\ln{\\frac{2T}{\\epsilon}}}{2\\delta^2}, \\frac{4K\\log_{2}T}{c_0}, \\frac{\\ln{\\frac{\\delta}{10}}}{\\ln{p^*}} +25\\frac{1+\\lambda}{1-\\lambda}\\frac{\\ln{\\frac{2T}{\\epsilon}}}{2\\delta^2}, \\frac{K\\ln(\\frac{MT}{\\epsilon})}{c_0\\ln(\\frac{1}{1-\\frac{2\\log M}{M-1}})}\\}$.  An alternative expression for $L$  keeping both terms is presented in the official comment.\n\nThank you again for the point. We hope this could provide a more detailed explanation of the rationale behind the choice of $L$. \n\nQ4. Could you please elaborate more about how you get L1 in theorem 4?\n\nA4. A sketch is as follows. First and foremost, we would like to add that the upper bound on $L_1$ is $\\max(L, K \\cdot 2(K^2+MK))$ based on the proof steps outlined in Appendix, which aligns with the concept of instance-free regret bounds. This upper bound does not rely on the $\\frac{1}{\\Delta_i}$ factor that could be problematic with small $\\Delta_i$. The terms $[\\frac{16C_1\\log T}{\\Delta_i^2}]$ and $[\\frac{4C_2\\log T}{\\Delta_i}]$ are not utilized and $L_1$ should be $\\max(L, K \\cdot 2(K^2+MK))$ in the statement. We will update this term in the statement of Theorem 4.\n\nThe proof sketch of Theorem 4 is as follows. We directly decompose $E[R_T|A]$ based on any $L_1$ as $E[R_T|A] = L_1 + \\frac{1}{M}\\sum_{t=L_1}^T\\sum_{m=1}^M(E[\\mu_{i^*} - U_m^t(i^*)|A] + E[U_m^t(i^*) - U_m^t(a_m^t)|A] +  E[U_m^t(a_m^t) - L_m^t(a_m^t) |A] + E[L_m^t(a_m^t) - \\mu_{a_m^t}^t|A])$ where $U_m^t(a_m^t), L_m^t(a_m^t)$ are the upper and lower confidence bounds of the network-wide estimators. This is the sum of (i) the differences between the confidence bounds and the true mean values, (ii) the differences in the upper confidence bounds between the global optimal and sub-optimal arms and (iii) the differences between the upper and lower confidence bounds $\\sum_t U_m^t(a_m^t) - L_m^t(a_m^t)$ which is the dominating term. The term (i) relies on the concentration inequalities for the network-wide estimators. The second term (ii) is based on the number of time steps when the clients do not follow UCB, which is relevant to the criterion $n_{m,i}(t) \\leq N_{m,i}(t) - K$. The third term (iii) is proportional to the cumulative sum of $\\sqrt{\\frac{C_1\\ln{T}}{n_{m,i}(t)}} + \\frac{C_2\\ln{T}}{n_{m,i}(t)}$ which has an upper bound $O(\\sqrt{T}\\log T)$, i.e. $\\sum_t U_m^t(a_m^t) - L_m^t(a_m^t) \\propto \\sum_t\\sqrt{\\frac{C_1\\ln{T}}{n_{m,i}(t)}} + \\frac{C_2\\ln{T}}{n_{m,i}(t)} = O(\\sqrt{T}\\log T)$ by the Harmonic series and the Cauchy Schwartz's inequality. The choice of $L_1$ is a necessary condition for the concentration inequalities in (i).\n\nThe first term, $L$, in the expression for $L_1$ originates from the definition of event $A$, where $t > L$ is assumed with respect to the graph's randomness in the context of considering the regret $E[R_T|A]$ conditioned on $A$. The event $A$ becomes crucial for the concentration inequalities of the network-wide estimators (i), and the rationale behind introducing term $L$ is discussed in A3.\n\nThe second term, $L_1 \\geq K \\cdot 2(K^2+MK)$, is necessitated by the condition that, for $t \\geq L_1$, $n_{m,i}(t) \\geq n_{m,i}(L_1) \\geq \\frac{L_1}{K} \\geq 2(K^2+MK)$. This condition ensures the validity of the subsequent lemma in Appendix: For any $m,i$, if $n_{m,i}(t) \\geq 2(K^2+2KM)$ and graph $G_t$ is connected, then we have $n_{m,i}(t) \\leq 2\\min_{j}n_{j,i}(t)$\nwhere the min is taken over all the clients. This lemma guarantees that the clients would stay on the same page (in terms of the variance proxies of the network-wide estimators), which is important to the concentration inequalities of network-wide estimators (i).\n\nThis lemma is equally essential for both Theorem 2 and Theorem 3. The rationale behind the absence of the condition $L \\geq K \\cdot 2(K^2+MK)$ in Theorem 2 and Theorem 3 lies in the different analytical strategies. These two theorems rely on an alternative decomposition, namely $E[R_T|A] \\propto  L + \\sum_i\\Delta_iE[n_{m,i}(T)| A]$, which enables us to achieve instance-dependent results. The absence of the condition $L \\geq K \\cdot 2(K^2+MK)$ in Theorem 2 and Theorem 3 arises from bounding the terms based on this alternative decomposition. The condition $n_{m,i}(t) \\geq 2(K^2+MK)$ is incorporated into the upper bound of the second term $E[n_{m,i}(T)| A]$. This upper bound reads as\n$\\max({[\\frac{4C_1\\log T}{\\Delta_i^2}], 2(K^2+MK) })$ and $\\max([\\frac{16C_1\\log T}{\\Delta_i^2}], [\\frac{4C_2\\log T}{\\Delta_i}], 2(K^2+MK))$ in Theorem 2 and Theorem 3, respectively.\n\nWe hope the discussions on $L_1$ could elaborate the derivation of $L_1$ in Theorem 4 and illustrate why it is unique to this particular theorem. "}, {"review_id": "tH4wFd1R7X", "reviewer": "Reviewer_zM1d", "summary": "Update: I've read the authors' rebuttal as well as all the reviews from other reviewers. The authors' clarification are helpful and mitigate my concerns. I've raised the score from 6 to 7 and I think this manuscript is acceptable for publication.\n\nThis paper aims at making contributions to decentralized multi-agent MAB problem research by studying both heterogeneous rewards (with heavy-tailed reward distributions) and time-varying random graphs, where the distributions of rewards and graphs are independent of time. It is claimed that this is the first work to consider this problem and to investigate it with heavy-tailed reward distributions. To be more specific, the paper investigates 1) heterogeneous sub-exponential and sub-gaussian distributed rewards and 2) random graphs including the possibly unconnected E-R model and random connected graphs, and applies them to the decentralized multi-agent MAB framework using a proposed UCB-type solution. It is considered as an extension of relevant existing literature (especially [Dubey et al.,2020] and and [Zhu et al., 2021b]) on decentralized multi-agent MAB  research area.", "questions": "Please see my questions in my above comment when taking about the weakness.", "limitations": "N/A.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Paper presentation is clean and clear, and overall speaking, the manuscript is reader friendly and straightforward to follow.\n2. There are quite nontrivial novel theoretical analysis results included in the paper, which seems to be solid.\n3. There are quite a couple of helpful remarks/explanations comparing with existing literature.", "weaknesses": "1. I'd like to see more more explanations/elaborations about the motivation/practical backgrounds why those types graphs are considered and what are some example real world applications that might have those types of graphs. For example, this paper consider the uniformly distributed connected graph generated using Algorithm 1, but could the author provide any example real world applications that have that kind of graphs? Especially about the part of adding extra minimum number of edges to make the randomly sampled graph to be connected . That seems to be a purely artificial/simulation based approach, and I don't obviously see much real world applications that demonstrate such behavior. The paper introduction briefly mention random failure graph in real world applications as motivation, but obviously random failed graphs have essential difference compared with such formulated graphs. More elaborations/explanations about the motivations/applications would be helpful to convince that such an artificial formulation is not just for convenient mathematical analysis, but also very beneficial to real world applications, rather than just a mathematical game.\n\n2. In algorithm 1, I saw a constant probability \"1/2\" in the graph sampling part. Why this specific \"1/2\" is used here? Would any constant probability 0<p<1 work the same here for the analysis and theoretical results (as well as obtained bounds when comparing with literature)? It would be great if the authors could help clarify/confirm this in the manuscript.\n\n3. I saw undirected graph is considered/assumed in this paper. How hard/difficult to consider the more generic scenario of directed graphs and what are the main challenges? It would be valuable to see some discussions on this for future research directions.\n\n4. I'd like to see some scaling and complexity discussions. Is the proposed method naturally scalable to large multi-agent systems? It would be good to see some experiments and analysis on this, ideally comparing with relevant literature.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for the review and for sharing your comments and perspectives. We would like to include the following perspectives. \n\nQ1. the motivation/practical backgrounds of graphs\n\nA1. We would like to refer to A5 in response to the comment Q5 from reviewer a3u4 where we provide detailed elaboration on the motivations. In what follows, we present the practical applications of the graph under consideration, along with the generation process.\n\na) uniformly distributed connected graph\n\nNote that in some real-world scenarios, the graph may be changing, yet it can still retain a robust connectivity property. For instance, on a cluster, certain connections between servers might be dynamically disrupted, but the overall cluster of servers remains functional. This means that servers can communicate with each other through multi-step paths, and the way servers are interconnected within the cluster might be time-dependent. This rationale clarifies our choice to sample from the connected graph family, which in line with established literature.  Simultaneously, the uniform distribution aligns with the foundational Erdős-Rényi (E-R) model $G(M,m)$, wherein a graph is uniformly selected from the set of all graphs with $M$ nodes and $m$ edges.\n\nb) adding extra minimum number of edges to make the randomly sampled graph to be connected \n\nWe would like to add that this step aims to ensure the connectedness of the initialization graph, denoted as $G_0$, before constructing the subsequent Markov chain within the for loop. Initially, we assess whether $G^{init}$ is already connected; if it is, then there is no need to add any edges. If it is not connected, starting from a vertex we iteratively add edges to the graph, checking its connectivity after each addition. This process continues until the graph becomes connected. By following this approach, we ensure that the complexity of the process remains within $M(M^2+M)$ (the worst case scenario), wherein the first term accounts for the steps taken and the second term accounts for the graph connectivity verification. This method generates an initialized connected graph, denoted as $G_0$, based on $G^{init}$ in polynomial time, preceding the subsequent for loop. While the number of edges added might not necessarily be globally optimal (we are not backtracking), it suffices that it is locally optimal, in order to efficiently obtain a connected graph. \nWe can rephrase this as \"adding an additional minimal number of edges oriented from a single vertex.\" In the sensor cluster, we consistently establish connections between a designated sensor and other sensors until the entire cluster becomes connected.\n\nc) random failure graph in real world applications\n\nFor a practical application, our objective is to illustrate the professional connection relationships among individuals on social media through a use case. In this context, we establish an edge between two users when they are mutually connected or follow each other on a platform. However, there is a possibility that a user might accidentally tap the \"remove connection\" or \"unfollow\" button, leading to the disruption of the connection. Even though these accidental events are infrequent and random, they can still happen. It is important to note that such behaviors are independent among users, and the likelihood of them occurring may be similar for users with similar features. Therefore, we can model this process using an Erdős-Rényi (E-R) model, denoted as $G(M,c)$, where the parameter $c$ signifies the probability of such disconnections not taking place. Essentially, this parameter reflects the likelihood of these accidental edge removals, which is assumed to be quite small in this use case.\n\n\nQ2. In algorithm 1, Why this \"1/2\" is used here? Would any 0<p<1 work? \n\nWe achieve an observation of a graph with a probability of $(\\frac{1}{2})^{\\frac{M(M-1)}{2}}$ by assigning a probability of $\\frac{1}{2}$ to the generation of each edge, considering that we have $\\frac{M(M-1)}{2}$ potential edge candidates. Simultaneously, the total number of possible graphs with $M$ nodes is $2^{\\frac{M(M-1)}{2}}$. This implies that a uniform distribution over all possible graphs is equivalent to generating each graph observation with a probability of $\\frac{1}{2^{\\frac{M(M-1)}{2}}}$. As a result, the edge-wise sampling with a probability of $\\frac{1}{2}$ creates a uniform distribution over all possible graphs, which is a necessary precondition for simulating the original underlying distribution $P(\\cdot)$ constrained within the connected graph family (our intended distribution $f(\\cdot) = P(\\cdot | G \\text{ is connected})$) as described in [1]. The selection of $p = \\frac{1}{2}$ transforms the problem of graph sampling based on $P(\\cdot)$, with its exponentially large sample space, into a manageable edge-wise sampling task.\n\nThe graph generation and the corresponding convergence rate analysis rely on obtaining a sample based on $P(\\cdot)$, a condition that is met when selecting $p = \\frac{1}{2}$ (if and only if), so for settings $s_2$, $s_3$, $S_2$, and $S_3$, the current analysis and results are valid when specifying $p = \\frac{1}{2}$ at the initialization in Algorithm 1. Moreover, it would be promising to explore the modifications needed in Algorithm 1 when $p \\neq \\frac{1}{2}$ during the initialization step. This could involve adjusting the distribution $p^{\\frac{M(M-1)}{2}}$ to match the original underlying distribution $P(\\cdot)$ through importance sampling. Additionally, investigating other types of random graphs with non-uniform distributions $p^{\\frac{M(M-1)}{2}}$ rather than the uniform distributions $P(\\cdot)$ paves the way for future research directions in random graph simulation. \n\nThank you again for the comments and reviews. The responses to Q3 and Q4 are included in the official comments.\n\n[1] C. Gray, L. Mitchell, and M. Roughan. Generating connected random graphs. Journal of Complex Networks, 7(6):896–912, 2019.\n"}, {"review_id": "emoZSfJQ28", "reviewer": "Reviewer_H8V9", "summary": "This paper studies the problem of multi-agent multi-armed bandits where the arm rewards generated for each agent is heterogeneous across agents, and the goal is to find the global optimal arm, where the reward of the global optimal arm is the mean of the mean reward observed by agents. In addition, this work considers that the agents are connected through an incomplete and time-varying topology. Both heterogeneous agent-specific reward and time-varying underlying topology make sense from a practical perspective and also add intellectually interesting technical challenges to the multi-agent MAB problem. The authors propose a series of algorithms for graph generation and bandit learning and then analyze the regret of the proposed algorithms under multiple different assumptions and in both problem-dependent and problem-independent settings. The regret bounds are interesting and (near) optimal in most cases. ", "questions": "see two questions above. ", "limitations": "n/a", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "++ This paper addresses a very challenging setting of multi-agent MAB problem where reward generation is heterogeneous and the graph is time-varying. \n\n++ The presentation of the paper is clear and solid and it clearly explains the challenges and missing points in the existing literature. \n\n++ The proposed algorithms make sense intuitively.\n\n++ The statements of the results sound solid (even though, I cannot confirm the details of the proof) and significant, with sufficient explanations in comparison with the literature. ", "weaknesses": "-- Overall, this paper is a solid work with novel and non-trivial contributions. Unfortunately, the technical part of this paper is beyond my core expertise, and I can't note on the correctness of the proofs. \n\n-- In the literature of multi-agent bandits, there is a substantial thread of the work that considers communication cost as a metric to improve upon. This work, however, does not touch at all the communication complexity in their study. Can authors comment on whether or not it makes sense to add communication cost analysis to their work? \n\n-- In this work, the authors, by default, assume that the goal of the game is to find the global optimal arm. However, one may suggest that in a multi-agent setting, each agent may care more about their local optimal arm. Can the authors comment on how the algorithms may or may not work when the objective is to find local optimal arms? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the review and for providing your suggestions and comments. We would like to present the responses to the questions as follows. \n\nQ1. This work, however, does not touch at all the communication complexity in their study. Can authors comment on whether or not it makes sense to add communication cost analysis to their work?\n\nA1. We will add the analysis on the communication cost to the paper, consistent with the existing literature on multi-agent MAB, and present the analysis as follows (we would also like to refer to A6 in response to the comment Q6 from reviewer a3u4 where we provide elaborations on communication cost.)\n\nAssuming a constant cost of establishing a communication link, as defined in [1], denoted as $c_1$, the communication cost $C_T$ can be calculated as $C_T = c_1 \\cdot \\sum_{t=1}^T |E_t|$, which is proportional to $\\sum_{t=1}^T |E_t|$. Alternatively, following the framework proposed in [2], the communication cost can be defined as the total number of communications among clients, which can be represented as $C_T = \\sum_{t=1}^T |E_t|$, similar to the previous definition. Regarding the quantity $C_T = \\sum_{t=1}^T |E_t|$, the number of edges $E_t$ could be $O(M)$ for sparse graphs, and at most $O(M^2)$. This implies that the communication cost, in a worst-case scenario, is of order $O(TM^2)$. This cost aligns with the existing work of research on decentralized distributed multi-agent MAB problems without a focus on communication cost, where edge-wise communication is a standard practice.\n\nRecent advancements have been made in reducing communication costs, such as achieving $O(\\sqrt{T}M^2)$ in [2] for centralized settings or $O(M^3\\log T)$ through Global Information Synchronization (GIS) communication protocols assuming time-invariant graphs in [1]. The incorporation of random graph structures introduces its own complexities, which poses challenges to reductions in communication costs. These advancements introduce a promising direction for communication efficiency within the context of random graphs.\n\nWe value and appreciate your perspective on communication cost which enriches the paper and suggests a promising avenue for future research – enhancing communication cost efficiency based on various communication protocols in decentralized distributed multi-agent MAB problems.\n\n\n\n\n\nQ2. The authors, by default, assume that the goal of the game is to find the global optimal arm. Can the authors comment on how the algorithms may or may not work when the objective is to find local optimal arms?\n\nA2. The regret measure is defined with respect to the reward of the globally optimal arm, and the algorithms are designed to minimize this regret. As the regret is proportional to $T$ - the number of pulls of the global optimal arm, a $\\log T$ regret implies the identification of the global optimal arm, given that the time horizon $T$ is sufficiently large to ensure $T >> \\log T$.\n\nIf the objective is to find local optimal arms, locality can be interpreted in two ways: (a) local as in global local arm, or (b) optimal arm with respect to a subset of the nodes, e.g., a node and all adjacent nodes. Regarding the former interpretation, the algorithm guarantees a global optimal solution on average if $T$ is large; it is thus likely to find an optimal arm if $T$ is large. If $T$ is not large, there is no such guarantee and thus the algorithm will identify a good arm within a limited number of pulls. With respect to the latter interpretation, if local is defined as at a node, then this entails executing standard MAB at each node. If locality is defined with respect to 1-neighborhood of a node, then this is the centralized distributed version of MAB. If locality is defined based on some other sets, then the algorithm can be executed recursively on each set of interest. We do not provide an analysis of such a recursive version of the algorithm.\n\n[1] T. Li and L. Song. Privacy-preserving communication-efficient federated multi-armed bandits. IEEE Journal on Selected Areas in Communications, 40(3):773–787, 2022.\n\n[2] C. Li and H. Wang. Communication efficient federated learning for generalized linear bandits. Advances in Neural Information Processing Systems, 35:38411–38423, 2022.\n\n"}]

Author rebuttal:
We would like to thank all the reviewers for their valuable suggestions and comments. We have carefully considered the comments and provided additional perspectives accordingly. Thank you so much for your time and effort in reading the responses.

Additionally, in the uploaded file, we incorporate a table that presents the settings more clearly. 







Meta-review: This paper introduces an innovative approach to the decentralized multi-agent multi-armed bandit (MAMAB) problem, incorporating the study of heterogeneous rewards and time-varying random graphs with time-independent reward and graph distributions. Notably, the authors delve into both sub-exponential and sub-gaussian reward settings, an area that is currently underrepresented in existing literature.

All reviewers concurred that this paper represents a significant contribution to the field of decentralized MAMAB and have thus recommended it for acceptance. The authors are urged to incorporate all the points discussed during the rebuttal phase into the final version of the paper. This should include a comparison and discussion on how the regret depends on various problem-dependent variables.

Lastly, congratulations on this well-executed piece of work!
Decision: Accept (spotlight)