Decentralized Multi-Armed Bandit Can Outperform Classic Upper Confidence Bound
Authors: Jingxuan Zhu
Ethan Mulle
Christopher Salomon Smith
Ji Liu
Venue: NeurIPS 2021 Submitted (2021)

Abstract: This paper studies a decentralized multi-armed bandit problem in a multi-agent network. The problem is simultaneously solved by $N$ agents assuming they face a common set of $M$ arms and share the same mean of each arm’s reward. Each agent can receive information only from its neighbors, where the neighbor relations among the agents are described by a directed graph whose vertices represent agents and whose directed edges depict neighbor relations. A fully decentralized multi-armed bandit algorithm is proposed for each agent, which twists the classic consensus algorithm and upper confidence bound (UCB) algorithm. It is shown that the algorithm guarantees each agent to achieve a better logarithmic asymptotic regret than the classic UCB provided the neighbor graph is strongly connected. The regret can be further improved if the neighbor graph is undirected and connected. 

21 ie.. the difference between the decision maker's ' accumulated (expected) reward and the maximum Decentralized Multi-Armed Bandit Can Outperform Classic Upper Confidence Bound
Abstract
This paper studies a decentralized network. The problem is simultaneously solved by N agents assuming they face a common set of M arms and share the same mean of each arm's 's reward. Each agent can receive information only from its neighbors, where the neighbor relations among the agents are described by a directed graph whose vertices represent agents and whose directed edges depict neighbor relations. fully decentralized multi-armes bandit algorithm is proposed for each agent, which twists the classic consensus algorithm and upper confidence bound (UCB) algorithm. It is shown that the algorithm guarantees each agent to achieve a better logarithmic asymptotic regret than the classic UCB provided the neighbor graph strongly connected. The regret can be further improved if the neighbor graph is undirected.
bandit problem in a multi-agent
3
5
10
11
Introduction
12
Multi-armed bandit (MAB) is a basic but fundamental reinforcement learning problem which has wide range of applications in natural and engineered systems including clinical trials, adaptive routing, cognitive radio networks, and online recommendation systems [1]. The problem has various formulations. In a classical and conventional MAB problem setting. a single decision maker (or player) makes a sequential decision to select one arm at each discrete time from given finite set of 18 arms (or choices) and then receives reward corresponding to the chosen arm, generated according to random variable with an unknown distribution. In general, different arms have different distributions 20 and reward means. The target of the decision maker minimize its cumulative expected regret,
13.
14
15
16
22 which could have been obtained had the reward information been known. For this conventional MAB problem, both lower and upper bounds on the asymptotic regret were derived in the seminal work [2),
24 and classic UCB algorithms were proposed in [3] which achieve an Ollog T) regret. Since multi- armed bandits have been studied for decades, it is impossible to survey the entire bandit literature here For an introductory survey, see a recent book [4].
26
27
Over the past decade, our social networks, communication infrastructure, data centers, and societal systems have become increasingly massive and complex, which can all modeled as networked multi-agent systems. In such large-scale multi-agent network, e.g. a sensor network and multi-
28
29
30 robot system, the need for decentralized information processing and decision making arises naturally
31 since the sensors robots in the network are equipped with on-board processors and are physically
32 separated from each other. Concurrently, the emerging big data era brings restrictions on information
flow to human-involl involved networks, primarily due privacy concerns, and thus precludes conventional centralized and parallel information processing and decision making algorithms, which typically rely center collecting all information taking the lead. Therefore, there is ample motivation to develop multi-agent, decentralized, multi-armed bandit algorithms.
34
36
Over the past year, there has been increasing interest to extend conventional single-player bandit 38 settings to multi-player frameworks. Notable examples include [5-17], to name few. Among all the existing multi-agent settings, we are motivated by a cooperative setting which makes use 40 of a consensus process [18, 19] among all agents. Such a setting was first proposed in [16] with homogeneous reward distributions, i.e., all agents share the same distribution of each arm's 's reward. The problem has recently attracted increasing attention and quite a few different consensus based
37
42
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

decentralized algorithms have been proposed and developed [16, 17.20-231, Note that in such a homogeneous reward distribution setting, each agent in network actually can independently learn an optimal arm using any conventional single-agent UCB algorithm, ignoring any information received from other agents. Notwithstanding, all the existing algorithms for the decentralized multi-armed bandit problem with homogeneous reward distributions require that each agent be aware of certain network-wise global information, such as spectral properties of the underlying graph or total number 49 of agents in the network. Such a requirement leads to counterintuitive observation: compared with the conventional single agent case, each agent in a multi-agent network can collect more arm-
43
44
45
46
47
48
50
51 related information while its bandit learning becomes more restrictive or less independent. Motivated
52 by this issue, this paper aims to develop a fully decentralized aulti--amedd bandit algorithm for general directed graph, which does not require any global information, and further shows that 54 the decentralized algorithm can ensure each agent in the network learns faster in contrast to the conventional single-agent case.
55
56
Related Work Multi-agent MAB problems have been studied in various settings [5-17]. For exam- plc, [5,6,9, 24] preclude communications among agents but allow them to receive "collision" signals when more than one agent selects the same arm, which has applications in wireless communication and cognitive radio. A distributed setting with central controller is studied in [13, 25J in a federated learning context. Other federated bandit settings are considered in 23, with additional focus on theoretical privacy preservation.
58
59
60
61
62
Consensus- decentralized MAB algorithms are developed in [16, 17,20-23] for homogeneous reward distributions in a cooperative multi-agent setting. Very recently, cooperative multi-agent bandits have been extended to heterogeneous reward settings, that is, different agents may have different reward distributions and means for each arm. A heterogeneous decentralized problem is solved in [23] using the idea of gossiping to improve communication efficiency and privacy. All these consensus- gossip-based MAB algorithms require global information. An exception is [27] which considers heterogeneous setting but focuses on a complete graph, which implicitly allows each agent to collect all other agents' information.
63
64
65
66
68
70
Technical Challenges The design of a suitable upper confidence bound function is a critical step in crafting a mulli-armee bandit algorithm for the conventional single-agent aggent case, which determines 72 the decision of which arm to choose at each time and thus plays an important role in quantifying the cumulative regret. Such a relationship between upper confidence bound and regret becomes much 74 more complicated in the decentralized setting because with the agents' information propagating over
71
73
75 the network, each individual agent's 's regret is coupled with all the other agents' upper confidence
76 bound functions. This is likely the reason why all the existing algorithms for a similar decentralized multi-armed bandit problem under consideration require that each agent be aware of certain network-
78 wise information, such as spectral properties of the underlying graph or total number of agents the
79 network [16, 17, 20.).. Thus, the key technical challenge here is how design fully local upper confidence bound function for each agent, which does not require any global information. To achieve 81 this, we aim to bound the variance proxy of each agent's 's local estimate of each arm's 's sample mean
80
82 by a function of the agent's local sample counter, in contrast to a function of all N agents' sample counters used in the existing literature. To this end, another salient challenge arises, due information latency. Although each agent can directly or indirectly receive processed information from all other agents in connected network, takes extra time from the agents other than its neighbors. Thus, the information each agent receives does not reveal the "current" states of all other agents. Meanwhile, each agent may have different exploration trajectories of the arms. Information coupling and latency may further increase this exploration "imbalance" among the network, leading to poor learning performance of those agents with relatively insufficient exploration. This a typical bottleneck of multi-armed bandit learning processes. To tackle this, we design a local decision making criterion which provably bounds the difference between each agent's 's local sample number and the maximal number of samples over the network. The criterion enables the explorations of each arm among all the agents approximately "on the same page" and thus gets around the "imbalance" bottleneck.
83
84
85
86
87
88
89
90
91
92
93
34
Contributions We propose fully decentralized multi-armed bandit algorithm for directed, strongly connected graphs, without requiring any global information. The algorithm is shown guarantee that each agent achieves a better logarithmic asymptotic regret than the classic single-agent UCB1 algorithm. It appears that our work provides the first fully decentralized multi-armed bandit algorithm
95
96
97
98 for directed graphs, with a provable regret guarantee for strongly connected graphs. Extensive simulations show that the algorithm also works for more general weakly connected graphs. For
99
2

---

100
the special case when the underlying graph is undirected, our algorithm can be modified to have further improved regret which reflects the effect of each agent's 's degree centrality in the graph. In this case, the algorithm enables faster learning for any agent in the network contrasted with the UCB1
101
102
103
algorithm, as long as the agent has at least one neighbor.
104
2
Problem Formulation
105
As mentioned in the introduction, we are interested in a decentralized multi-armed bandit problem formulated as follows. Consider multi-agent network consisting of N agents (or players). For presentation purposes, we label the agents from through N.. It is worth emphasizing that the agents are not aware of such global labeling. but each agent can differentiate between its neighbors. The neighbor relations among the N agents are described by directed graph G = (V, E) with N vertices, where the vertex set V [N] A {1, ] represents the N agents and the set of directed edges (or ares) & depicts the neighbor relations where agent j is a neighbor of agent i whenever (), i) is directed edge in G. Each agent can receive information only from its neighbors (i.e., lies in its neighbors' broadcast ranges). Thus, the directions of directed edges represent the directions of information flow. For convenience, we assume each agent is neighbor of itself, or equivalently, each vertex of G has self-are. Clearly, a directed graph G may allow uni-directional communication among the agents. In the case when (i,j) is an edge in G as long as (j. is edge in the graph, G becomes an undirected graph which only allows bi-directional communication.
106
107
108
109
110
111
112
113
115
117
All N agents face common set of M arms (or decisions) which denoted by [M] ف {1,2. M. At each discrete time t E {0, 1.2..... Th each agent makes a decision on which arm to select from the M choices, and the selected arm is denoted by (t). If agent i selects an arm k, it will receive a random reward X (t). For each i E [N] and & E [M], (xx)
118
119
120
is an unknown i.i.d. random process. For each arm l E [M] all X (t), [N]. share the same expectation μę- It is worth emphasizing that this setting allows different agents to have different reward probability distributions for each arm, so long as their means are the same. Without loss of generality, we assume that all X (l) have bounded support [0. 1] and that #n 2 M22 2 ... 2 P.M which implies that arm I has the largest reward mean and thus is always an optimal choice.
122
124
126
127
The goal of the decentralized multi-armed bandit problem just described is to devise a decentralized algorithm for each agent in the network which will enable agent minimize its expected cumulative regret, defined as
128
129
T Σ E
R&(T) = TM
(a.(t))
E=1
an order at least as good as (T(T) oT)), RT(T) 0s - cc. for all i [N].
130
131
is worth re-emphasizing that all the existing algorithms [16, 17,20-22] for the above decentralized
132
MAB problem require each agent to make use of certain network- wwisrrkwwiseaa global information such the
139
spectral properties of the neighbor graph or total number of agents in the network. In the next section,
134
we propose a fully decentralized multi-armed bandit algorithm which does not require any global information.
135
3
Algorithm
136
We begin with some important variables to help present our algorithm.
138
Local sample counter: Let (t) be the number of times agent pulls arm i by time t.
139
Local sample mean: Let 1(-) be the indicator function that returns if the statement is true and 0 otherwise. Define
140
(t) (1) Σ [[a((T==))xpp
(I)
141 which represents the average reward that agent receives from arm & until time t. This is analogous
142 to how single agent estimates the reward mean in UCBI [3].
143 Two local estimates: Fach agent can have more sample information and a more accurate reward mean estimate for each arm by exploiting information received from its neighbors, since all the agents
3

---

145 are simultaneously exploring the arms. To this end, each agent uses two variables, (²,x(t) and
148 (t), to locally estimate two pieces of global information, the maximal number of samples of arm
147 k pulled among all the N agents till time I, [a n),x(t),, and the sample mean of arm k among
148 all the N agents, respectively. At each time t, each agent i updates its (t, and (t,((t) as follows:
mi, (t + 1) = max (n + 1), (),a(t), j E ].), Fi,h (1+1)= = Σ (1)=),((1) + (1 + (1),
(2)
(3)
JEN.
where Nr; denotes the set of neighbors of agent i including itself, and Waj, j N₁. are "consensus" weights to be designed using local information only. It is worth emphasizing that both (,,)(t) and ,,,)(()) are updated in distributed manner as only information from agent i's neighbors are needed.
150
151
152
The updates (2) and (3) are intended to reach an "approximate" agreement on the two estimates among the N agents. The update (2) makes use of the idea of max-consensus [28]. The update (3) consists of two components, Ejex, W,y22,8 (f), a linear consensus term, and T. (f + 1) (t),
154
155
which can be regarded as a local "gradient" term. Intuitively, 21,x(() is a better estimate of the reward mean compared with the local sample mean Fi. (1), Zi,A (t) exploits more sample information.
156
157
Two local design objects: Each agent needs to specify two objects in its local implementation. The first object is the consensus weights Wij. j E .N. which will be used in the update (3). Consensus algorithms have been studied for many years. We will appeal to two classic linear consensus processes: the flocking algorithm [29] and the Metropolis algorithm [30]. tailored for consensus over directed graphs and average consensus over undirected graphs, respectively. The second object is the upper confidence bound function (t) which will be used to quantify agent i's belief on its estimate of arm ss reward mean. Upper confidence bound functions are critical in single-agent UCB algorithm design. As we will see, coordination among the agents allows to design upper confidence bound functions "hetter" than that in the classic UCB1 I algorithm [3]. Detailed expressions of the consensus
159
161
162
163
165
166
weights and upper confidence bound functions will be specified in the theorems.
167
A detailed description of our decentralized UCB algorithm, named Dec_UCB, is presented as follows.
168
3.1
Dec_UCB: Decentralized UCB
189
Initialization: At time = 0, each agent i samples each arm k exactly once, setting (c,x(0) = a (0) = 1, (0) (0) (0), and (0) = 0.
170
171
Iteration: Between clock times and + 1. E (o, T). each agent i performs the steps enumerated below in the order indicated.
172
173
1. Decision Making: Each agent i picks exactly one arm according to the following rule: (a) If there is no arm ls such that (1) S (l) M, agent computes the index Qi, (1) = (1) (t),
174
175
and then pulls the arm at + 1) that maximizes Qi, (1), with ties broken arbitrarily, and receives reward X (t+ (t. + 1).
176
(b) If there exists at least one arm ls such that (t) S ms, (t) M,, then agent i randomly pulls one such arm.
178
179
2. Transmission:
Agent broadcasts its (t,((t) and (t); at the same time, agent i receives ml,e(() and (1) from each of its neighbors j E EN,.
180
181
3. Updating: Each agent updates the following variables for each arm k:
{ (t)
(t) +1
if = a,(t + 1), if + ai(t + 1),
(1 + +1) =
1+1
(t + (t, + 1)
11 (a:(T) (T),
my,a(t + 1)= max (ne, (t + 1), my,((), j E Mi).
+t Σ (1)zja(t + tz, + +1) - (t).
JEN.
4

---

182
For concise presentation of the algorithm, we refer to the pseudocode in Appendix A.
183
To better understand the algorithm just described, we provide the following remarks.
184
Remark 1. In the special case when N = 1, i.e., the single-ageni case, let agent i be the unique agent in the network. Clearly, there no information transmission involved. Note that in this case,
185
186
n (t) always equals (t), which implies that the inequality (t,&(t) > m,, -M always holds.
187
Thus, at each time, the agent pulls an arm that maximizes (u)(t). Also, the update of 24,((t) can be
188
simplified as 2i,k (t + 1) - Zi. (t) = Fi (t + 1) - T. (t) Since zi, (0) = F.. it follows that the reward mean estimate (t) is always the same as the sample mean (t), Therefore, Dec_ UCB
189
190
is essentially the same as the classic single-agent UCBI algorithm proposed in [3] when N = 1. D
191
Since our decentralized UCB algorithm simplifies the classic UCBI [3] as explained in the above remark, we will focus on our algorithm performance comparison with respect to UCBI, both theoretically and experimentally. It is worth mentioning that [3] also proposes another single-agent UCB algorithm, named UCB2.
192
193
194
195
key aspect of the algorithm design, which is different from classic single-agent UCB algorithms and existing decentralized MAB algorithms [16. 17, 20, 21J, is the inequality criterion in the Decision Making rule (a), (t,x(t) S (t) - M. The intuition behind this is to restrict the difference between the local sample counter (t) and the local estimate (t,(t). Since the differences are uniformly bounded above by M, the inequality to some extent enables all the agents be "consistent" in exploring the arms, that is, no agent will be behind too much in exploring any arm. The motivation in doing so is that a typical bottleneck of multi-armed armed bandits lies in insufficiens exploration of one more arms. In decentralized setting, if one agent does not sufficiently explore an arm, it will affect the accuracy of the reward mean estimate of all other agents as the graph is connected in some form. Keeping the explorations of each arm among all the agents approximately on the same page" gets around the bottleneck.
Remark 2.
196
197
199
201
202
203
205
206
3.2
Results
To state our first result, we need the following concepts.
208
Let Z (t) and (1) be the N-dimensional vectors whose ith entries equal zi,A (f) and (t), respec- tively. Then, the updates (3) for the N agents can be combined as
209
=x + 1) W zu (t) + Tx (t + 1) (t),
(4)
where Win is the N x N matrix whose ijth entry equals way if E NN, and zero otherwise. In the case where each agent adopts the flocking algorithm [29], i.e., (5) in Theorem 1, W is a stochastic matrix whose diagonal entries are all positíve. The flocking algorithm can be applied to both directed and undirected graphs. In the case where each agent adopts the Metropolis algorithm [30], i.e., (8) in Theorem 2, W is a symmetric doubly stochastic matrix whose diagonal entries are all positive. The Metropolis algorithm can only be applied to undirected graphs [30].
211
212
213
214
215
216
3.2.1
Strongly Connected Graphs
217
A directed graph is strongly connected if it has a directed path from any vertex to any other vertex. For strongly connected graph G. the distance from vertex i to another vertex j is the length of the shortest directed path from to j; the longest distance among all ordered pairs of distinct vertices i and j in G is called the diameter of G.
218
219
220
Let A μ1 14k for each & E [M], denoting the gap of reward means between arm I and arm k.
222
Theorem 1. Suppose that G is strongly connected and all N agents adhere to Dec_ UCB, Then, with
4logt (1),x(()
1
(t)
and
wij
Wi]
j j.,
(5)
223
the regret of each agent i E [N] until time T satisfies
(T(T) < Σ
16
log T, 2(M² + 2Md d), L 1
2n
+ M² + +22 42M- 1)d) 1
max
3A4
3
where d is the diameter of G. and L is constant defined in Remark 3.
5

---

225
Here [ denotes the cardinality of N₁, or equivalently, the number of neighbors of agent i including itself. Thus, [N;] is always positive.
226
227
is worth noting that the above regret bound intuitively decreases as the diameter of neighbor graph G decreases or the network connectivity increases (see Remark 3).
228
228
To better understand the above theorem, let 'I' be sufficiently large. Then, the regret bound in the 16 + +[]) log T, Compared with the regret bound of the classic 3Ax 3Ax
theorem can be written as Es,so
single-agent UCBI given in [3], which is Es.sol & + o(1)) log we have the following result.
231
232
Corollary 1. If the neighhor graph is strongly connected, Dec_ UCB guarantees each agent to achieve
233
a better logarithmic asymptotic regret than the classic UCBI.
234
Remark 3. can be seen that W is an irreducible and aperiodic stochastic matrix (which holds for both Theorem I and Theorem 2). Then, it is well known that there exists a rank-one stochastic matrix Wo so for which Wt converges to W exponentially fast as -+ Do [31]. To be more precise, letting
235
236
237 P2 denote the second largest among the magnitudes of the N eigenvalues of W, then P2 E [0, 1) and
238
there exists a positive constant c. such that
[W*], 1ij
solgi S cpp
(6)
239 for all i.j E [N], where Llsy denotes the ijth entry of a matrix. With the above e and p2. L is defined as the smallest value such that when t Z L, there holds
रिगंत <1,
72N[c|tp2
where [.] denotes the ceiling function.
242
Since P2 is nonnegative, LHS of (7) is decreasing in terms of when is large enough and converges to 0 as + 0o, which implies that the inequality always holds after some finite time. Thus, L must be nonnegative and uniquely exist by definition. Also, LHS is power function of p2, thus is
243
244
245 increasing in terms of P2, i.e., the smaller p2 is, the smaller LHS would be, given a fixed t. In another aspect, the smaller P2 is, the faster the LHS converges 0 as -- DC, which implies that L decreases as P2 decreases. Since P2 can be regarded as an index of connectivity of G with weight matrix W in that the smaller P2 is, the higher connectivity the network has, I, decreases as the network connectivity increases. In the special case when P2 -0 it is easy to verify that I, = O.
248
247
248
Proof Sketch of Theorem The proof makes use of important properties of sub- aab-Gaussian random variables (see Appendix B. Since any random variable with bounded support is sub-Gaussian so is any X L (t). With this in mind, we write each zz,x
251
252
linear combination of of sub-Gaussian random variables (r. j E [N]. r E {0, 1, 1,,11,,,,,,, which is also sub-Gaussia Gaussian due to the additivity
253
254
property of sub-Gaussian random variables. A particularly important property of a sub-Gaussian
255
random variable X with mean j and variance proxy o² is that P - μ| 2 a) S 2 2σ holds for any non-negative a. To make use of this property, our next step is to estimate the variance proxy of 2 le (t), denoted by of, (t). To this end, we first show that of, (t) is bounded above by function of all N sample counters, n,,, E [N]. that is, (t) S (mi. (t), (t), ,yy.) (t))
256
257
258
A critical technical challenge here is to bound the f function with local function, i.e., a function depending only on agent i's local sample counter (t). To tackle this, we invoke the key algorithm step in Dec_ UCB, which is the inequality criterion in the Decision Making rule (a), designed to ensure all the agents will be "consistent" in exploring each arm (see Remark 2). Using this "consistency"", we are able to replace the f function with a local function g with which of,, (t) I g()),.ett). Substituting this function and the upper confidence bound Ci, (t) into the inequality of sub-Gaussian random variables can show that the reward mean μ4g is within the range of the confidence interval of agent i's local estimate 21,x (t) with high probability, i.e., P( (t) uul 2 Ct,(())) o(l/t), which is also the key idea of how we design (t). What remains to apply the analysis of UCBI I [3] to further transform the upper confidence bound to the regret bound. Specifically, we are
259
261
263
264
265
mentioned above,
286
287
268
269
then able to bound Enn,, (t)) by uniform constant for all non- non-optimal arms. This and the fact that
270
R, (T) = Es. E(n,AA (T) yield the upper bound of agent i'ss regret.
271
3.2.2
Undirected Graphs
272
Note that the regret bound in Theorem 1, derived for strongly connected graphs using the flocking algorithm weights, is independent of agent index and thus each agent's centrality. In the following

---

274
theorem, we will show that when the neighbor graph is undirected, we can have a better regret bound using the Metropolis algorithm weights, which shows how each agent's regret bound depends on the number of its neighbors, i.e., the degree centrality.
275
For undirected, connected graph G, the distance between different vertices is the length of the shortest path connecting them, and the diameter of G is the longest distance among all pairs of distinct vertices in G.
278
279
Theorem 2. Suppose that G is undirected, connected, and all N agents adhere to Dec_ UCB. Then, with
281
1 max(LNGWNN)) JEN, j *
Wij =
3 3log (t)
(1)
and
(8)
Wii = 1- --EJEN max (ING
282
the regret of each agent i E [M] until time T satisfies
R(TT) S
Σ
max
12
log T, 2(M² +2Md d). 1 } 2n² + +M² + +(M 1)aa
where d is the diameter of G. and L is constant defined in Remark 3.
284
To better understand the above theorem, let T be sufficiently large. Then, the regret bound in the theorem can be written Es. W. o(1)) log T. Comparing this bound with the asymptotic 16 + o(1)) log T, it can be seen that the former is smaller than the latter if [MG] 2 3, which leads to the following result.
12
285
regret bound in Theorem 1, that is Es 3āx
286
Corollary 2. Dec_UCh guarantees an agent to learn faster in an undirected, connected graph than 288
289
when the graph directed, strongly connected, as long as the agent has at least two neighbors excluding itself.
291
Simulations for the case when an agent only has two neighbors excluding itself can be found in Section 4 and Appendix C.
Next we compare Es,SO MA + o(1)) log T with the asymptotic regret bound of the classic o(1) T. The former is smaller than the latter if [W]] > 1. Since each agent always has itself as a neighbor by assumption, and each agent must have at least one neighbor excluding itself in a connected graphs, [N]] always holds a connected graph. We are led to the following result.
293
UCBI algorithm, that is E
296
298
Corollary 3. If the neighbor graph with N > 1 agents is undirected and connected, Dec_UCB guarantees each agent achieve a better logarithmic asymptotic regret than the classic UCBI.
299
300
Note that any undirected graph can always be divided into one or more connected components. Thus, each connected component can analyzed separately and independently. Corollary has the following immediate consequence.
301
303
Corollary 4. If the neighbor graph is undirected, Dec_ UCB guarantees an agent to achieve a better logarithmic asymptotic regret than the classic UCB1, as long as the agent has least one neighbor excluding itself.
304
305
308
3.2.3
Weakly Connected Graphs
307
Corollary 4 shows that when the neighbor graph is undirected, Dec_UCB is still functional with provable performance even if the graph is disconnected. However, the case of directed graphs is much more complicated. A disconnected directed graph can also be divided into more than one "connected" component, yet each component is "weakly connected", and not necessarily strongly connected. A directed graph is weakly connected replacing all of its directed edges with undirected ones results
308
309
310
311
312
in connected graph. A strongly connected graph is weakly connected, but not vice versa. Thus, our results in Section 3.2.1 cannot applied to weakly connected graphs, whose complete analysis has
315
so far eluded us. Notwithstanding this, it is worth noting that simulations in Section 4 suggest that
315
Dec_ UCB works well for weakly connected graphs, and thus also for any directed graphs, as long as
each agent has at least one neighbor excluding itself.
7

---

Simulations
317
318
This section presents various simulations created with the aid of Python packages [32-35] which were used to experimentally verify the validity and performance of our proposed Dec_UCB algorithm. We focus on the heterogeneous reward distribution case here. Additional simulations and observations, including the homogeneous reward distribution case, are presented in Appendix C.
320
322
Small-size Graphs Simulations were run on three types of graphs, namely strongly connected, undirected connected, and weakly connected graphs', allowing for the reward distribution to vary between agents for given arm. given agent and arm pair can draw rewards from an arm-specific Beta distribution with mean μı and standard deviation 0.05, an arm-specific Bernoulli distribution with mean μk., or an arm-specific truncated normal distribution within [0, 1] with mean μ4 and standard deviation 0.05. The distribution used is randomly assigned to each agent/arm pair upon initialization. The reward means μ* are the same for all agents on a given arm, with each μ4s randomly [0.05, 0.95]. Rewards are bounded by definition from the used distributions to within [0, 1]. Each experiment run for 7 1000 time steps with results for each graph obtained by averaging over 100 experiments. The results obtained from running
323
324
326
328
chosen from uniform distribution
330
332
Dec_ UCB alongside UCBI on small 6-agent graphs are illustrated in Figures 1, 2, and 3 for the three
graph types, respectively. These results empirically back the claims of Theorem 1, Theorem 2, and
334
Corollaries 1-3 the presence of heterogeneous arm reward distributions.
Aganc
Agar:3
300
75-
Figure plot the regret of the strongly connected graph, averaged over 100 experiments. Reward distributions vary between agents for given arm.
Aganc
175
Ager
102-
Figure A plot of the regret the undirected and connected graph, averaged over 100 experiments. Reward distributions vary between agents for given arm.
Large-scale Graphs Larger scale simulations were run for the three graph types with heterogeneous reward distributions, averaging results from 100 different randomly generated Erdös-Rényi 50-agent graphs for each graph type. Additionally, 10 arms with rewards following randomly chosen Beta, Bernoulli, or truncated normal distribution were used, with means μ4 randomly chosen from a uniform distribution bounded within (0.05, 0.95). A standard deviation of 0.05 used for the Beta and truncated normal distributions. Rewards were bounded by the used distributions to be within for T 1000 iterations for each different random graph, testing the
336
338
340
[0, 1]. The algorithms
We focus weakly connected graphs in which each agent has at least one neighbor excluding itself; otherwise the agent cannot receive any external information and thus essentially lies in the single-agent

---

Agec
Agmnc
Agec
Ageri
200
630 006
1000
Figure 3: A plot of the regret of the weakly connected graph, averaged over 100 experiments. Reward distributions vary between agents for given arm.
worst performing agent of Dec_ UCB against the best performing results from the UCB1 algorithm. Results are shown in Figure 4. In all cases, Dec_UCB UCB achieves better performance than UCB1.
Decenrraard fegeot
Decart Regeot
175
Deconrratrd fagent
150
Expected Cum. leboe
125
Dxpectee Jabor
060
200
73
50
25
12
230
2006
230
1800
(a) Results for the large strongly connected generated graphs.
(b) Results for the large undirected connected generated graphs.
(c) Results for the large weakly con- nected generated graphs.
Figure 4: Plots of the expected cumulative regret for both the worst performing agent of Dec_UCB and best performance of UCB 1. Results averaged over 100 different randomly generated Frdōs-Réóg weakly connected graphs of 50 agents each. The reward distribution for given arm randomly chosen as a Beta, Bernoulli, or truncated normal distribution.
343
Observations There several key observations to take from these simulations. The first of these is that Dec_UCC appears to perform better on the undirected graphs than does on the strongly connected graphs. This validates the theoretical results presented in Theorem 2 and Corollary 2. Additionally, the performance of each agent in the strongly connected graphs appears to be independent of its number of neighbors, indicating that performance is reliant only the diameter of the graph as demonstrated in Section 3.2.1. In contrast, as shown in Section 3.2.2, for undirected graphs, each agent's regret also depends on its number of neighbors. In total, performance of Dec_UCB appears to be unaffected by the choice of using homogeneous arm rewards or heterogeneous arm rewards;
345
347
349
350
351
352
expected cumulative regrets appear to nearly equivalent for all graph types in either case.
Conclusion
353
In this paper, we have studied decentralized multi-armed bandit problem over directed graphs and proposed a fully decentralized UCB algorithm, which provably achieves a better logarithmic 355
asympiotic regret than the classic UCB1 algorithm provided the neighbor graph is strongly connected.
357
We have further improved the algorithm's performance for undirected graphs. Simulations have more general weakly
thcoretical results and test the performance connected graphs. Future directions are to study the limitations of the paper, including analysis for weakly connected graphs and time-varying graphs, experiments with real data sets, and development of a decentralized counterpart for the classic UCB2 algorithm [3].
been provided to validate
359
361

---

References
362
363
[1] D. Bouneffouf, I. Rish, and C. Aggarwal. Survey on applications of and contextual bandits. In 2020 IEEE Congress on Evolutionary Compulation, 2020.
385
[2] T. L. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mahemattics, 6(1):4-22, 1985.
366
367
[3 Auer, N. Cesa-Bianchi. and P. Fischer. Finite-time analysis of the multiarmed bandit problem.
Machine Learning, 47(2-3):235-2555 2566 2002.
[4] A. Slivkins. Introduction to Multi-Armed Bandits. 2019. arXiv: 1904.0722057 [es.LG]..
370
[5] Lai. H. Jiang, and V. Poor. Medium access in cognitive radio networks: A competitive multi- armed bandit framework, In 42nd Asilomar Conference on Signals, Systems and Computers, pages 98-102,77 2008.
371
372
379
[6] K. Liu and Q. Zhao. Distributed learning in multi-armed bandit with multiple players. IEEE Transactions on Signal Processing, 58(11):5661) 1):566755611 2010.
374
375
[7] B. Szorenyi, R. Busa-Fekete, Hegedus, R. Ormándi, M. Jelasity, and Kégl. Gossip-based distributed stochastic bandit algorithms. In 30th International Conference on Machine Learning. 2013.
376
377
378
[8] D. Kalathil, N. Nayyar, and R. Jain. Decentralized learning for multiplayer multiarmed bandits.
379
IEEE Transactions on Information Theory, 60(4))2331- 2014.
380
[9] I. Bistritz and A. Leshem. Distributed multi-player bandits game of thrones approach. In 32nd International Conference on Neural Information Processing Systems, pages 7222-7232, 2018.
381
[10] A. Sankararaman, A. Ganesh, and S. Shakkottai. Social learning in multi agent multi armed bandits. Proceedings of the ACM on Measurement and Anulysis of Computing Systems, 3(3)11 35, 2019.
384
[1I] Y. Wang, J. Hu, X. Chen, and L. Wang. Distributed bandit learning: Near-optimal regret with efficient communication. In International Conference on Learning Representations, 2020.
387
386
[12] A. Dubey and A. Pentland. Differentially-private federated linear bandits. In 34th Conference on Neural Information Processing Systems, 2020.
[13] C. Shi and C. Shen. Federated multi-armed bandits. In 35th AAAI Conference on Artificial Intelligence, 2021.
381
382
[14] U. Madhushani and N.E. Leonard. A dynamic observation strategy for multi-agent multi-armed bandit problem. In European Control Conference, 2020.
383
394
[15] U. Madhushani and N.E. Leonard. Heterogeneous explore-exploit strategies on multi-star networks. IEEE Control Systems Letters, 2020.
395
396
[16] Landgren, V. Srivastava, and N.E. Leonard. On distributed cooperative decision-making in
multiarmed bandits. In Proceedings of the European Control Conference, 2016.
398
[17] D. Martinez-Rubio, V. Kanade, and P. Rebeschini. Decentralized cooperative stochastic bandits.
399
In 33rd Conference on Neural Information Processing Systems, pages -4522 2019.
400
[18] A. Jadbabaie, J. Lin, and A. S. Morse. Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Transactions on Automatic Control, 1866) 2003.
402
[19] R. Olfati-Saber, J. A. Fax, and R. M. Murray. Consensus and cooperation in networked multi-agent systems. Proceedings of the IEEE, 95(1):215-233, 2007.
403
404
[20]
Landgren, V. Srivastava, and N.E. Leonard. Distributed cooperative decision-making in multiarmed bandits: Frequentist and bayesian algorithms. In Proceedings of the 55th IEEE
406
Conference on Decision and Control, pages 167-172, 2016.
407
[21] P. Landgrena, V. Srivastavab, and N.E. Leonarda. Distributed cooperative decision making in multi-agent multi-armed bandits. Automatica, 2021.
[22] J. Zhu, R. Sandhu, and J. Liu. A distributed algorithm for sequential decision making in armti bandit with homogeneous rewards. In Proceedings of the 59th IEFE Conference on Decision and Control, pages 3078-3083, 2020.
410
10

---

412
[23] Z. Zhu, J. Zhu, J. Liu, and Y. Liu. Federated bandit: a gossiping approach. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 5(1), 2021.
413
[24] N. Nayyar, D. Kalathil, and Jain. On regret-optimal learning in decentralized multi-player
415
multi-armed bandits. IEEE Transactions on Conirol of Network Systems, 2016.
416
[25] C. Shi, C. Shen, and J. Yang. Federated multi--rmed bandits with personalization. CoRR,
abs/2102.13101, 2021.
418
[26] T. Li, L. Song, and C. Fragouli. Federated recommendation system via differential privacy. In 2020 IEEE International Symposium on Information Theory (ISIT), pages 2592-25977, 2020.
419
420
[27] Z. Wang, C. Zhang, M. K. Singh, L. Riek, and K. Chaudhuri. Multitask bandit learning through heterogeneous feedback aggregation. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 1531-1539, PMLR, 13-15 Apr 2021.
421
423
424
[28] F. lutzeler, P. Ciblat, and J. Jakubowicz. Analysis of max-consensus algorithms in wireless channels. IEEE Transactions on Signal Processing, 60(1 :)6103-61107 2012.
426
427
299 A. Jadbabaie, J. Lin, and A.S. Morse. Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Transactions on Automatic Control, 48(6):988-101, 2003.
429
[30] L. Xiao, S. Boyd, and S. Lall. A scheme for robust distributed sensor fusion based on average consensus. In Proceedings of the 4th International Conference on Information Processing in Sensor Networks, pages 63-70, 2005.
430
432
[3]] L. Xiao and S. Boyd. Fast linear iterations for distributed averaging. Systems & Control Letters, 53(1):65-78, 2004.
[32]
C. R. Harris, K. J. Millman, S. J. van der Walt, et al. Array programming with NumPy. Nature, 585(7825):357-362, September 2020.
435
436
[33]
Virtanen, R. Gommers, T. Oliphant, al. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272, 2020.
437
438
[34] J. D. Hunter. Matplotlib: A 2d graphics environment. Computing in Science & Engineering,
9(3):90 95, 2007.
(35] A. Hagberg, D. Schult, and P. Swart. Exploring network structure, dynamics, and function using networkx. In Gaël Varoquaux, Travis Vaught, and Jarrod Millman, editors, Proceedings of the 7th Python in Science Conference, pages 11 15, Pasadena, CA USA, 2008
441
443
[36] T. Lattimore and C. Szepesvári. Bandit Algorithms. Cambridge University Press, 2018.
444
[37] W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, (3(301):13-15) 1963.

---

Checklist
448
447
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
449
contributions and scope? [Yes] See Abstract and Section
450
(b) Did you describe the limitations of your work? [Yes] See Section 3.2.3 and conclusion.
451
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
453
454
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 2 and Section 3.2.
456
457
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix B.
458
3. If you ran experiments..
459
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material as URL)? [Yes] See Appendix C and the supplemental material.
461
462
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 4 and Appendix C.
463
464
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
467
468
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
469
(a) your work uses existing assets, did you eite the creators? [N/A]
470
(b) Did you mention the license of the assets? [N/A]
471
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
473
(d) Did you discuss whether and how consent was obtained from people whose data you're you're using/curating? [N/A]
474
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
476
477
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
479
480
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
481
482
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "xSqYH4WamA-", "reviewer": "Reviewer_HFTD", "summary": "A multi-agent pure-distributed (no shared data) algorithm for the stochastic Multi Armed Bandit setting is presented and analyzed.\nRegret bounds for different agents connectivity schemes are provided, incorporating the related quantities, namely the diameter for strongly connected graphs and the number of each agent neighbors for undirected graphs. Experiments are conducted to illustrate the superiority of the algorithms and the related bounds over the single-agent UCB1 algorithm performance and the qualitative difference of the performance of the agents in the different connectivity settings.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main contribution and novelty of the paper is the pure distributed algorithm and the regret bounds for the different connectivity settings. The (synchronous) algorithm presented is simple and easy to implement, the results are clearly stated, and the experiments nicely illustrate the claims.  The asymptotic performance advantage over the classical UCB1 (or other algorithms in which agents do not share information) is not surprising, nevertheless. Furthermore, the proof sketch of Theorem 1 in the main body of the paper does not provide any insight regarding the incorporation of the characteristics of the connectivity architecture (namely, the diameter of the strongly connected graph) or the constant $L$ of remark 3 into the regret bound (the main contribution of the paper).\nTheory-wise,  beyond the improvement in the constant factor $\\log T$ (from 8 to $\\frac{16}{3}$), also (and probably more) interesting would be a lower bound on the achievable improvement (with a multiplicity of $N$ agents sampling the bandits) and the relation to the better bound of UCB2 (which is indeed mentioned in line 194 but without commenting on the performance or the applicability of the analysis).\n\ntypo: should be $X_{i, a_{i}(t)}$ in the formula after line 129.\n\nomission? rewards after \"arm k\" in line 147.\n\nThe main algorithm is clearly presented, probably with some redundancy as the updates appear several times (e.g., after line 148, in  the algorithm description after line 181 and in the pseudocode in appendix A). ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"ethical_concerns": "no", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "rSLxths8c8U", "reviewer": "Reviewer_oU5f", "summary": "The authors propose a novel algorithm in order to extend the UCB1 algorithm to a distributed setting where agents are represented by the nodes of a digraph and these agents are allowed to exchange information with all of their neighbors at each step. The authors prove two performance guarantees, one for a general connected digraph, another one when the graph is non directed.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1) The communication model is never really clearly stated. What are the agents allowed to exchange ? Are they forced to communicate with each neighbor at each time step ? How many bits are allowed to be exchanged per round ? This is fundamental in order to assess the applicability of the results: for instance it seems that the algorithm requires to exchange real numbers (as opposed to integers) between agents, which is impossible using a communication network unless some quantization is performed. Also communicating with all neighbors all the time might generate a lot of unnecessary traffic etc.\n\n2) The authors do not provide information theoretic lower bounds on the regret of any algorithm in their setting, nor do they try to compare their performance guarantees to other lower bounds. Therefore it is hard to tell whether or not the performance guarantees of Theorem 1 are interesting.\n\n3) Theorem 1 shows only a constant improvement with respect to UCB1, so that the regret of each node scales as $R_i(T) = O(M\\log(T)/\\Delta)$ even though nodes are allowed to exchange a lot of information. One would expect the regret of each node to scale as $R_i(T) = O((M/N) \\log(T)/\\Delta )$ simply based on the argument that, if all agents explore an arm $(1/N) \\log(T)/\\Delta^2$ times and then broadcast their respective estimates to other nodes (one can always broadcast information to all nodes in at most $N$ communication rounds, providing that the graph is connected), then this arm can be safely discarded. \n\n4) In Theorem 2, the choice of weights implies that all nodes know the number of their neighbors, as well as the number of their neighbors neighbors. This contradicts the assumptions in the model (unless one first designs an initial step in the algorithm in order to exchange this information as well).\n\n5) Why not use KL-UCB instead of UCB in the algorithm's design ? Especially since they require the same information. Also, the numerical performance of the proposed algorithm should be compared to that of KL-UCB and Thompson sampling, which are the state-of-the-art algorithms for the centralized case.\n\n6) In Theorem 1, the regret bound features a term proportional to $M^2 \\sum_{k} \\Delta_k$ which can scale like $O(M^3)$. This suggests that the algorithm can sometimes perform much worse than UCB1 since its regret scales like $O(M \\log(T)/\\Delta )$. Why is that so ? Is this an artifact of the analysis or does this phenomenon really appear in numerical experiments ?\n\n7) In Theorem 1, a number $L$ appears, and Remark 3 bounds this number as a function of the eigenvalue gap of the graph. However, how does $L$ scale with $N$ ? Does there exists networks with arbitrarily large L value (if so this is a problem) ? What is the \"worse case\" network ?  \n \nMinor Comments: the authors claim that their approach is \"fully distributed\" which is misleading since a \"full distributed\" setting would be the case where agents are not allowed to exchange any information. Here they do exchange information with their neighbors.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "fZxhoQ3-vhW", "reviewer": "Reviewer_w9xA", "summary": "The paper considers a multi-agent cooperative bandit system, where the agents are connected on a graph and can share messages. The arm-pulls of each agent does not interfere with that of the others, but agents can speed up learning by communicating. The paper proposes a parameter-free (no information on the global system) algorithm that each individual agent executes locally. if the graph is strongly connected, the per-agent regret is shown to be strictly better than that of vanilla UCB. If the graph is undirected, the regret of an agent is inversely proportional to the number of neighbors it can share information with. The key algorithmic innovation is to ensure that the number of times an arm is pulled by all agents are within M (a constant which is a hyper-parameter) of each other. This enables agents to arrive at consensus and get low regret", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is very well written and was a pleasure to read and follow along. Multi-agent bandit algorithms that are truly parameter-free are an important line of work and the present paper makes progress on that front. \n\nMy main question is whether in some case (a class of undirected graphs), can the algorithm achieve a regret reduction by a factor of N (the total number of agents), as opposed to N_i, the number of neighbors. Indeed for the complete graph they are the same, but can they be extended to for example expanders or other fast mixing topologies? \n\nRelated to above is a Missing reference :  The article of \"The gossiping insert-eliminate algorithm for multi-agent bandits by Chawla et.al. in AISTATS 2021\" is relevant to your study. They consider an algorithm that requires knowledge of number of agents, but obtains regret scaling as 1/N times that of the vanilla UCB, \"for any undirected graph\". Thus the regret guarantee is stronger compared to the present paper, but relies on global information.\n\nMore generally, I recommend a survey in the related work along the following lines -\" stronger results have been obtained under global information while the present work obtains weaker results without any assumption of global information.\" ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "W9wrb4H8bb_", "reviewer": "Reviewer_LxWs", "summary": "This paper studies the classic multi-armed bandit problem, but in the presence of many cooperating agents distributed over a graph.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper studies the classic multi-armed bandit problem, but in the presence of many agents distributed over a graph. Each agent is a node in a graph, and can receive messages from the neighbors of that node. Every agent is faced with making a decision in every time step, for t = 1...T. Each agent wants to minimize regret, and the goal is to have even the agent with the largest regret suffer a smaller regret than the standard single-agent UCB algorithm. This can be expected because after all an agent comes to possess more information now with the gossipping that goes on because of the network connections. \n\nThis area of cooperating agents on a network playing MAB has seen decent activity recently, with papers developing methods to achieve exactly this objective of smaller regret than the single-agent case. This paper's goal is to ensure that each agent knows nothing more than their neighbors about the graph --- not the total number of nodes or spectral properties of the graph etc. --- and achieve the same. This would make the cooperation model truly decentralized. The paper achieves this with a variant of UCB called Decentralized_UCB (Dec_UCB).\n\nEvaluation:\n\n1) Overall, at least theoretically, it makes an interesting question to ask what happens if agents cooperate in a network and exchange feedback information. So that's a plus.\n2) But the model itself is not being introduced in this paper. It has been studied in many papers recently, and the paper's main contribution is to make it fully decentralized.\n3) The improvement over UCB can necessarily come only on the constant in front of the log(T) term, and not asymptotically on the log(T) term itself. Also, regarding the improvement in constant, although there is *definitely* work to be done to establish this, overall, given the nature of the setting, it is reasonable to expect that an improvement in constants is going to happen when agents gossip over the network. Therefore, the results are not super surprising. \n4) One interesting part is how the improved constant for the directed graphs case is independent of the number of neighbors, where as it is dependent on the number of neighbors for the undirected graphs case. The authors say that this is also borne out in simulations, although I don't exactly see the simulation plots that vary the number of neighbors.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers have all felt that while this is a decent paper, its contribution is somewhat uninspiring: the model it studies is nice but not new, and the improvement it provides over UCB is marginal and not very surprising.  The paper might benefit from a revision that will include stronger motivation and a more rigorous comparison with existing work---I suggest the authors to follow the suggestions of Reviewer w9xA to this end.
Decision: Reject