Decentralized Multi-Armed Bandit Can Outperform Classic Upper Confidence Bound
Year: 2021

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

This paper studies a decentralized multi-armed bandit problem in a multi-agent1 network. The problem is simultaneously solved by N agents assuming they face2 a common set of M arms and share the same mean of each arm’s reward. Each3 agent can receive information only from its neighbors, where the neighbor relations4 among the agents are described by a directed graph whose vertices represent5 agents and whose directed edges depict neighbor relations. A fully decentralized6 multi-armed bandit algorithm is proposed for each agent, which twists the classic7 consensus algorithm and upper confidence bound (UCB) algorithm. It is shown8 that the algorithm guarantees each agent to achieve a better logarithmic asymptotic9 regret than the classic UCB provided the neighbor graph is strongly connected.10 The regret can be further improved if the neighbor graph is undirected.11
1 Introduction12
Multi-armed bandit (MAB) is a basic but fundamental reinforcement learning problem which has13 a wide range of applications in natural and engineered systems including clinical trials, adaptive14 routing, cognitive radio networks, and online recommendation systems [1]. The problem has various15 formulations. In a classical and conventional MAB problem setting, a single decision maker (or16 player) makes a sequential decision to select one arm at each discrete time from a given finite set of17 arms (or choices) and then receives a reward corresponding to the chosen arm, generated according to18 a random variable with an unknown distribution. In general, different arms have different distributions19 and reward means. The target of the decision maker is to minimize its cumulative expected regret,20 i.e., the difference between the decision maker’s accumulated (expected) reward and the maximum21 which could have been obtained had the reward information been known. For this conventional MAB22 problem, both lower and upper bounds on the asymptotic regret were derived in the seminal work [2],23 and classic UCB algorithms were proposed in [3] which achieve an O(log T ) regret. Since multi-24 armed bandits have been studied for decades, it is impossible to survey the entire bandit literature25 here. For an introductory survey, see a recent book [4].26
Over the past decade, our social networks, communication infrastructure, data centers, and societal27 systems have become increasingly massive and complex, which can all be modeled as networked28 multi-agent systems. In such a large-scale multi-agent network, e.g. a sensor network and a multi-29 robot system, the need for decentralized information processing and decision making arises naturally30 since the sensors or robots in the network are equipped with on-board processors and are physically31 separated from each other. Concurrently, the emerging big data era brings restrictions on information32 flow to human-involved networks, primarily due to privacy concerns, and thus precludes conventional33 centralized and parallel information processing and decision making algorithms, which typically34 rely on a center collecting all information or taking the lead. Therefore, there is ample motivation to35 develop multi-agent, decentralized, multi-armed bandit algorithms.36
Over the past year, there has been increasing interest to extend conventional single-player bandit37 settings to multi-player frameworks. Notable examples include [5–17], to name a few. Among38 all the existing multi-agent settings, we are motivated by a cooperative setting which makes use39 of a consensus process [18, 19] among all agents. Such a setting was first proposed in [16] with40 homogeneous reward distributions, i.e., all agents share the same distribution of each arm’s reward.41 The problem has recently attracted increasing attention and quite a few different consensus-based42
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.
decentralized algorithms have been proposed and developed [16, 17, 20–23]. Note that in such a43 homogeneous reward distribution setting, each agent in a network actually can independently learn an44 optimal arm using any conventional single-agent UCB algorithm, ignoring any information received45 from other agents. Notwithstanding, all the existing algorithms for the decentralized multi-armed46 bandit problem with homogeneous reward distributions require that each agent be aware of certain47 network-wise global information, such as spectral properties of the underlying graph or total number48 of agents in the network. Such a requirement leads to a counterintuitive observation: compared49 with the conventional single agent case, each agent in a multi-agent network can collect more arm-50 related information while its bandit learning becomes more restrictive or less independent. Motivated51 by this issue, this paper aims to develop a fully decentralized multi-armed bandit algorithm for52 a general directed graph, which does not require any global information, and further shows that53 the decentralized algorithm can ensure each agent in the network learns faster in contrast to the54 conventional single-agent case.55
Related Work Multi-agent MAB problems have been studied in various settings [5–17]. For exam-56 ple, [5, 6, 9, 24] preclude communications among agents but allow them to receive “collision” signals57 when more than one agent selects the same arm, which has applications in wireless communication58 and cognitive radio. A distributed setting with a central controller is studied in [13, 25] in a federated59 learning context. Other federated bandit settings are considered in [12, 23, 26] with additional focus60 on theoretical privacy preservation.61
Consensus-based decentralized MAB algorithms are developed in [16, 17, 20–23] for homogeneous62 reward distributions in a cooperative multi-agent setting. Very recently, cooperative multi-agent63 bandits have been extended to heterogeneous reward settings, that is, different agents may have64 different reward distributions and means for each arm. A heterogeneous decentralized problem is65 solved in [23] using the idea of gossiping to improve communication efficiency and privacy. All these66 consensus- or gossip-based MAB algorithms require global information. An exception is [27] which67 considers a heterogeneous setting but focuses on a complete graph, which implicitly allows each68 agent to collect all other agents’ information.69
Technical Challenges The design of a suitable upper confidence bound function is a critical step in70 crafting a multi-armed bandit algorithm for the conventional single-agent case, which determines71 the decision of which arm to choose at each time and thus plays an important role in quantifying the72 cumulative regret. Such a relationship between upper confidence bound and regret becomes much73 more complicated in the decentralized setting because with the agents’ information propagating over74 the network, each individual agent’s regret is coupled with all the other agents’ upper confidence75 bound functions. This is likely the reason why all the existing algorithms for a similar decentralized76 multi-armed bandit problem under consideration require that each agent be aware of certain network-77 wise information, such as spectral properties of the underlying graph or total number of agents in the78 network [16, 17, 20–22]. Thus, the key technical challenge here is how to design a fully local upper79 confidence bound function for each agent, which does not require any global information. To achieve80 this, we aim to bound the variance proxy of each agent’s local estimate of each arm’s sample mean81 by a function of the agent’s local sample counter, in contrast to a function of all N agents’ sample82 counters used in the existing literature. To this end, another salient challenge arises, due to information83 latency. Although each agent can directly or indirectly receive processed information from all other84 agents in a connected network, it takes extra time from the agents other than its neighbors. Thus, the85 information each agent receives does not reveal the “current” states of all other agents. Meanwhile,86 each agent may have different exploration trajectories of the arms. Information coupling and latency87 may further increase this exploration “imbalance” among the network, leading to poor learning88 performance of those agents with relatively insufficient exploration. This is a typical bottleneck of89 multi-armed bandit learning processes. To tackle this, we design a local decision making criterion90 which provably bounds the difference between each agent’s local sample number and the maximal91 number of samples over the network. The criterion enables the explorations of each arm among all92 the agents approximately “on the same page” and thus gets around the “imbalance” bottleneck.93
Contributions We propose a fully decentralized multi-armed bandit algorithm for directed, strongly94 connected graphs, without requiring any global information. The algorithm is shown to guarantee95 that each agent achieves a better logarithmic asymptotic regret than the classic single-agent UCB196 algorithm. It appears that our work provides the first fully decentralized multi-armed bandit algorithm97 for directed graphs, with a provable regret guarantee for strongly connected graphs. Extensive98 simulations show that the algorithm also works for more general weakly connected graphs. For99
the special case when the underlying graph is undirected, our algorithm can be modified to have a100 further improved regret which reflects the effect of each agent’s degree centrality in the graph. In this101 case, the algorithm enables faster learning for any agent in the network contrasted with the UCB1102 algorithm, as long as the agent has at least one neighbor.103
2 Problem Formulation104
As mentioned in the introduction, we are interested in a decentralized multi-armed bandit problem105 formulated as follows. Consider a multi-agent network consisting of N agents (or players). For106 presentation purposes, we label the agents from 1 through N . It is worth emphasizing that the agents107 are not aware of such a global labeling, but each agent can differentiate between its neighbors. The108 neighbor relations among the N agents are described by a directed graph G = (V, E) with N vertices,109 where the vertex set V = [N ] , {1, 2, . . . , N} represents the N agents and the set of directed edges110 (or arcs) E depicts the neighbor relations where agent j is a neighbor of agent i whenever (j, i)111 is a directed edge in G. Each agent can receive information only from its neighbors (i.e., lies in112 its neighbors’ broadcast ranges). Thus, the directions of directed edges represent the directions of113 information flow. For convenience, we assume each agent is a neighbor of itself, or equivalently, each114 vertex of G has a self-arc. Clearly, a directed graph G may allow uni-directional communication115 among the agents. In the case when (i, j) is an edge in G as long as (j, i) is an edge in the graph, G116 becomes an undirected graph which only allows bi-directional communication.117
All N agents face a common set of M arms (or decisions) which is denoted by [M ] , {1, 2, . . . ,M}.118 At each discrete time t ∈ {0, 1, 2, . . . , T}, each agent i makes a decision on which arm to select from119 the M choices, and the selected arm is denoted by ai(t). If agent i selects an arm k, it will receive a120 random reward Xi,k(t). For each i ∈ [N ] and k ∈ [M ], {Xi,k(t)}Tt=1 is an unknown i.i.d. random121 process. For each arm k ∈ [M ], all Xi,k(t), i ∈ [N ], share the same expectation µk. It is worth122 emphasizing that this setting allows different agents to have different reward probability distributions123 for each arm, so long as their means are the same. Without loss of generality, we assume that all124 Xi,k(t) have bounded support [0, 1] and that µ1 ≥ µ2 ≥ · · · ≥ µM , which implies that arm 1 has the125 largest reward mean and thus is always an optimal choice.126
The goal of the decentralized multi-armed bandit problem just described is to devise a decentralized127 algorithm for each agent in the network which will enable agent i to minimize its expected cumulative128 regret, defined as129
Ri(T ) = Tµ1 − T∑ t=1 E [ Xai(t) ] ,
at an order at least as good as Ri(T ) = o(T ), i.e., Ri(T )/T → 0 as T →∞, for all i ∈ [N ].130 It is worth re-emphasizing that all the existing algorithms [16, 17, 20–22] for the above decentralized131 MAB problem require each agent to make use of certain network-wise global information such as the132 spectral properties of the neighbor graph or total number of agents in the network. In the next section,133 we propose a fully decentralized multi-armed bandit algorithm which does not require any global134 information.135
3 Algorithm136
We begin with some important variables to help present our algorithm.137
Local sample counter: Let ni,k(t) be the number of times agent i pulls arm k by time t.138
Local sample mean: Let 1(·) be the indicator function that returns 1 if the statement is true and 0139 otherwise. Define140
x̄i,k(t) = 1
ni,k(t) t∑ τ=0 1(ai(τ) = k)Xi,k(τ), (1)
which represents the average reward that agent i receives from arm k until time t. This is analogous141 to how a single agent estimates the reward mean in UCB1 [3].142
Two local estimates: Each agent can have more sample information and a more accurate reward143 mean estimate for each arm by exploiting information received from its neighbors, since all the agents144
are simultaneously exploring the arms. To this end, each agent i uses two variables, mi,k(t) and145 zi,k(t), to locally estimate two pieces of global information, the maximal number of samples of arm146 k pulled among all the N agents till time t, maxj∈[N ] nj,k(t), and the sample mean of arm k among147 all the N agents, respectively. At each time t, each agent i updates its zi,k(t) and mi,k(t) as follows:148
mi,k(t+ 1) = max {ni,k(t+ 1), mj,k(t), j ∈ Ni} , (2) zi,k(t+ 1) = ∑ j∈Ni wijzj,k(t) + x̄i,k(t+ 1)− x̄i,k(t), (3)
where Ni denotes the set of neighbors of agent i including itself, and wij , j ∈ Ni, are “consensus”149 weights to be designed using local information only. It is worth emphasizing that both mi,k(t) and150 zi,k(t) are updated in a distributed manner as only information from agent i’s neighbors are needed.151
The updates (2) and (3) are intended to reach an “approximate” agreement on the two estimates152 among the N agents. The update (2) makes use of the idea of max-consensus [28]. The update (3)153 consists of two components, ∑ j∈Ni wijzj,k(t), a linear consensus term, and x̄i,k(t+ 1)− x̄i,k(t),154 which can be regarded as a local “gradient” term. Intuitively, zi,k(t) is a better estimate of the reward155 mean compared with the local sample mean x̄i,k(t), as zi,k(t) exploits more sample information.156
Two local design objects: Each agent i needs to specify two objects in its local implementation. The157 first object is the consensus weights wij , j ∈ Ni, which will be used in the update (3). Consensus158 algorithms have been studied for many years. We will appeal to two classic linear consensus processes:159 the flocking algorithm [29] and the Metropolis algorithm [30], tailored for consensus over directed160 graphs and average consensus over undirected graphs, respectively. The second object is the upper161 confidence bound function Ci,k(t) which will be used to quantify agent i’s belief on its estimate of162 arm k’s reward mean. Upper confidence bound functions are critical in single-agent UCB algorithm163 design. As we will see, coordination among the agents allows us to design upper confidence bound164 functions “better” than that in the classic UCB1 algorithm [3]. Detailed expressions of the consensus165 weights and upper confidence bound functions will be specified in the theorems.166
A detailed description of our decentralized UCB algorithm, named Dec_UCB, is presented as follows.167
3.1 Dec_UCB: Decentralized UCB168
Initialization: At time t = 0, each agent i samples each arm k exactly once, setting mi,k(0) =169 ni,k(0) = 1, zi,k(0) = x̄i,k(0) = Xi,k(0), and Ci,k(0) = 0.170
Iteration: Between clock times t and t + 1, t ∈ {0, 1, . . . , T}, each agent i performs the steps171 enumerated below in the order indicated.172
1. Decision Making: Each agent i picks exactly one arm according to the following rule:173 (a) If there is no arm k such that ni,k(t) ≤ mi,k(t)−M , agent i computes the index174
Qi,k(t) = zi,k(t) + Ci,k(t),
and then pulls the arm ai(t+ 1) that maximizes Qi,k(t), with ties broken arbitrarily,175 and receives reward Xi,ai(t+1)(t+ 1).176 (b) If there exists at least one arm k such that ni,k(t) ≤ mi,k(t)−M , then agent i randomly177 pulls one such arm.178
2. Transmission: Agent i broadcasts its mi,k(t) and zi,k(t); at the same time, agent i receives179 mj,k(t) and zj,k(t) from each of its neighbors j ∈ Ni.180
3. Updating: Each agent i updates the following variables for each arm k:181
ni,k(t+ 1) = { ni,k(t) + 1 if k = ai(t+ 1), ni,k(t) if k 6= ai(t+ 1),
x̄i,k(t+ 1) = 1
ni,k(t+ 1) t+1∑ τ=0 1(ai(τ) = k)Xi,k(τ),
mi,k(t+ 1) = max {ni,k(t+ 1), mj,k(t), j ∈ Ni} , zi,k(t+ 1) = ∑ j∈Ni wijzj,k(t) + x̄i,k(t+ 1)− x̄i,k(t).
For a concise presentation of the algorithm, we refer to the pseudocode in Appendix A.182
To better understand the algorithm just described, we provide the following remarks.183 Remark 1. In the special case when N = 1, i.e., the single-agent case, let agent i be the unique184 agent in the network. Clearly, there is no information transmission involved. Note that in this case,185 ni,k(t) always equals mi,k(t), which implies that the inequality ni,k(t) > mi,k(t)−M always holds.186 Thus, at each time, the agent pulls an arm that maximizes Qi,k(t). Also, the update of zi,k(t) can be187 simplified as zi,k(t + 1) − zi,k(t) = x̄i,k(t + 1) − x̄i,k(t). Since zi,k(0) = x̄i,k(0), it follows that188 the reward mean estimate zi,k(t) is always the same as the sample mean x̄i,k(t). Therefore, Dec_UCB189 is essentially the same as the classic single-agent UCB1 algorithm proposed in [3] when N = 1. 190
Since our decentralized UCB algorithm simplifies to the classic UCB1 [3] as explained in the191 above remark, we will focus on our algorithm performance comparison with respect to UCB1, both192 theoretically and experimentally. It is worth mentioning that [3] also proposes another single-agent193 UCB algorithm, named UCB2.194 Remark 2. A key aspect of the algorithm design, which is different from classic single-agent UCB195 algorithms and existing decentralized MAB algorithms [16, 17, 20, 21], is the inequality criterion196 in the Decision Making rule (a), ni,k(t) ≤ mi,k(t) −M . The intuition behind this is to restrict197 the difference between the local sample counter ni,k(t) and the local estimate mi,k(t). Since the198 differences are uniformly bounded above by M , the inequality to some extent enables all the agents199 to be “consistent” in exploring the arms, that is, no agent will be behind too much in exploring any200 arm. The motivation in doing so is that a typical bottleneck of multi-armed bandits lies in insufficient201 exploration of one or more arms. In our decentralized setting, if one agent does not sufficiently202 explore an arm, it will affect the accuracy of the reward mean estimate of all other agents as the graph203 is connected in some form. Keeping the explorations of each arm among all the agents approximately204 “on the same page” gets around the bottleneck. 205
3.2 Results206
To state our first result, we need the following concepts.207
Let zk(t) and x̄k(t) be the N -dimensional vectors whose ith entries equal zi,k(t) and x̄i,k(t), respec-208 tively. Then, the updates (3) for the N agents can be combined as209
zk(t+ 1) = Wzk(t) + x̄k(t+ 1)− x̄k(t), (4) where W is the N ×N matrix whose ijth entry equals wij if j ∈ Ni and zero otherwise. In the case210 where each agent adopts the flocking algorithm [29], i.e., (5) in Theorem 1, W is a stochastic matrix211 whose diagonal entries are all positive. The flocking algorithm can be applied to both directed and212 undirected graphs. In the case where each agent adopts the Metropolis algorithm [30], i.e., (8) in213 Theorem 2, W is a symmetric doubly stochastic matrix whose diagonal entries are all positive. The214 Metropolis algorithm can only be applied to undirected graphs [30].215
3.2.1 Strongly Connected Graphs216
A directed graph is strongly connected if it has a directed path from any vertex to any other vertex.217 For a strongly connected graph G, the distance from vertex i to another vertex j is the length of the218 shortest directed path from i to j; the longest distance among all ordered pairs of distinct vertices i219 and j in G is called the diameter of G.220 Let ∆k = µ1 − µk for each k ∈ [M ], denoting the gap of reward means between arm 1 and arm k.221 Theorem 1. Suppose that G is strongly connected and all N agents adhere to Dec_UCB. Then, with222
Ci,k(t) =
√ 4 log t
3ni,k(t) and wij =
1
|Ni| , j ∈ Ni, (5)
the regret of each agent i ∈ [N ] until time T satisfies223
Ri(T ) ≤ ∑
k:∆k>0
( max { 16
3∆2k log T, 2(M2 + 2Md+ d), L
} + 2π2
3 +M2 + (2M − 1)d
) ∆k,
where d is the diameter of G, and L is a constant defined in Remark 3.224
Here |Ni| denotes the cardinality ofNi, or equivalently, the number of neighbors of agent i including225 itself. Thus, |Ni| is always positive.226 It is worth noting that the above regret bound intuitively decreases as the diameter of neighbor graph227 G decreases or the network connectivity increases (see Remark 3).228 To better understand the above theorem, let T be sufficiently large. Then, the regret bound in the229 theorem can be written as ∑ ∆k>0
( 163∆K +o(1)) log T . Compared with the regret bound of the classic230 single-agent UCB1 given in [3], which is ∑ ∆k>0 ( 8∆k + o(1)) log T , we have the following result.231 Corollary 1. If the neighbor graph is strongly connected, Dec_UCB guarantees each agent to achieve232 a better logarithmic asymptotic regret than the classic UCB1.233 Remark 3. It can be seen that W is an irreducible and aperiodic stochastic matrix (which holds for234 both Theorem 1 and Theorem 2). Then, it is well known that there exists a rank-one stochastic matrix235 W∞ for which W t converges to W∞ exponentially fast as t→∞ [31]. To be more precise, letting236 ρ2 denote the second largest among the magnitudes of the N eigenvalues of W , then ρ2 ∈ [0, 1) and237 there exists a positive constant c such that238 ∣∣∣[W t]
ij − [W∞]ij ∣∣∣ ≤ cρt2 (6) for all i, j ∈ [N ], where [·]ij denotes the ijth entry of a matrix. With the above c and ρ2, L is defined239 as the smallest value such that when t ≥ L, there holds240
72Ndcetρ t 12Ndce−1 2 < 1, (7)
where d·e denotes the ceiling function.241 Since ρ2 is nonnegative, LHS of (7) is decreasing in terms of t when t is large enough and converges242 to 0 as t→∞, which implies that the inequality always holds after some finite time. Thus, L must243 be nonnegative and uniquely exist by its definition. Also, LHS is a power function of ρ2, thus it is244 increasing in terms of ρ2, i.e., the smaller ρ2 is, the smaller LHS would be, given a fixed t. In another245 aspect, the smaller ρ2 is, the faster the LHS converges to 0 as t→∞, which implies that L decreases246 as ρ2 decreases. Since ρ2 can be regarded as an index of connectivity of G with weight matrix247 W in that the smaller ρ2 is, the higher connectivity the network has, L decreases as the network248 connectivity increases. In the special case when ρ2 = 0, it is easy to verify that L = 0. 249
Proof Sketch of Theorem 1 The proof makes use of important properties of sub-Gaussian random250 variables (see Appendix B.1). Since any random variable with bounded support is sub-Gaussian, so is251 any Xi,k(t). With this in mind, we write each zi,k(t) as a linear combination of a set of sub-Gaussian252 random variablesXj,k(τ), j ∈ [N ], τ ∈ {0, 1, . . . , t}, which is also sub-Gaussian due to the additivity253 property of sub-Gaussian random variables. A particularly important property of a sub-Gaussian254
random variable X with mean µ and variance proxy σ2 is that P(|X − µ| ≥ a) ≤ 2e− a2
2σ2 holds for255 any non-negative a. To make use of this property, our next step is to estimate the variance proxy of256 zi,k(t), denoted by σ2i,k(t). To this end, we first show that σ 2 i,k(t) is bounded above by a function of all257 N sample counters, nj,k(t), j ∈ [N ], that is, σ2i,k(t) ≤ f(n1,k(t), n2,k(t), . . . , nN,k(t)). A critical258 technical challenge here is to bound the f function with a local function, i.e., a function depending only259 on agent i’s local sample counter ni,k(t). To tackle this, we invoke the key algorithm step in Dec_UCB,260 which is the inequality criterion in the Decision Making rule (a), designed to ensure all the agents261 will be “consistent” in exploring each arm (see Remark 2). Using this “consistency”, we are able262 to replace the f function with a local function g with which σ2i,k(t) ≤ g(ni,k(t)). Substituting this263 function and the upper confidence bound Ci,k(t) into the inequality of sub-Gaussian random variables264 mentioned above, we can show that the reward mean µk is within the range of the confidence interval265 of agent i’s local estimate zi,k(t) with high probability, i.e., P(|zi,k(t)− µk| ≥ Ci,k(t)) = o(1/t),266 which is also the key idea of how we design Ci,k(t). What remains is to apply the analysis of267 UCB1 [3] to further transform the upper confidence bound to the regret bound. Specifically, we are268 then able to bound E(ni,k(t)) by a uniform constant for all non-optimal arms. This and the fact that269 Ri(T ) = ∑ ∆k>0 E(ni,k(T ))∆k yield the upper bound of agent i’s regret. 270
3.2.2 Undirected Graphs271
Note that the regret bound in Theorem 1, derived for strongly connected graphs using the flocking272 algorithm weights, is independent of agent index i and thus each agent’s centrality. In the following273
theorem, we will show that when the neighbor graph is undirected, we can have a better regret bound274 using the Metropolis algorithm weights, which shows how each agent’s regret bound depends on the275 number of its neighbors, i.e., the degree centrality.276
For an undirected, connected graph G, the distance between two different vertices is the length of277 the shortest path connecting them, and the diameter of G is the longest distance among all pairs of278 distinct vertices in G.279 Theorem 2. Suppose that G is undirected, connected, and all N agents adhere to Dec_UCB. Then,280 with281
Ci,k(t) =
√ 3 log t
|Ni|ni,k(t) and
 wij = 1 max{|Ni|,|Nj |} , j ∈ Ni, j 6= i,
wii = 1− ∑ j∈Ni 1 max{|Ni|,|Nj |} ,
(8)
the regret of each agent i ∈ [N ] until time T satisfies282
Ri(T ) ≤ ∑
k:∆k>0
( max { 12
|Ni|∆2k log T, 2(M2 +2Md+d), L
} + 2π2
3 +M2 +(2M −1)d
) ∆k,
where d is the diameter of G, and L is a constant defined in Remark 3.283
To better understand the above theorem, let T be sufficiently large. Then, the regret bound in the284 theorem can be written as ∑ ∆k>0
( 12|Ni|∆k + o(1)) log T . Comparing this bound with the asymptotic285 regret bound in Theorem 1, that is ∑ ∆k>0
( 163∆K + o(1)) log T , it can be seen that the former is286 smaller than the latter if |Ni| ≥ 3, which leads to the following result.287 Corollary 2. Dec_UCB guarantees an agent to learn faster in an undirected, connected graph than288 when the graph is directed, strongly connected, as long as the agent has at least two neighbors289 excluding itself.290
Simulations for the case when an agent only has two neighbors excluding itself can be found in291 Section 4 and Appendix C.292
Next we compare ∑
∆k>0 ( 12|Ni|∆k + o(1)) log T with the asymptotic regret bound of the classic293 UCB1 algorithm, that is ∑
∆k>0 ( 8∆k + o(1)) log T . The former is smaller than the latter if |Ni| > 1.294 Since each agent always has itself as a neighbor by assumption, and each agent must have at least295 one neighbor excluding itself in a connected graphs, |Ni| > 1 always holds in a connected graph. We296 are led to the following result.297 Corollary 3. If the neighbor graph with N > 1 agents is undirected and connected, Dec_UCB298 guarantees each agent to achieve a better logarithmic asymptotic regret than the classic UCB1.299
Note that any undirected graph can always be divided into one or more connected components.300 Thus, each connected component can be analyzed separately and independently. Corollary 3 has the301 following immediate consequence.302 Corollary 4. If the neighbor graph is undirected, Dec_UCB guarantees an agent to achieve a better303 logarithmic asymptotic regret than the classic UCB1, as long as the agent has at least one neighbor304 excluding itself.305
3.2.3 Weakly Connected Graphs306
Corollary 4 shows that when the neighbor graph is undirected, Dec_UCB is still functional with307 provable performance even if the graph is disconnected. However, the case of directed graphs is much308 more complicated. A disconnected directed graph can also be divided into more than one “connected”309 component, yet each component is “weakly connected”, and not necessarily strongly connected. A310 directed graph is weakly connected if replacing all of its directed edges with undirected ones results311 in a connected graph. A strongly connected graph is weakly connected, but not vice versa. Thus, our312 results in Section 3.2.1 cannot be applied to weakly connected graphs, whose complete analysis has313 so far eluded us. Notwithstanding this, it is worth noting that simulations in Section 4 suggest that314 Dec_UCB works well for weakly connected graphs, and thus also for any directed graphs, as long as315 each agent has at least one neighbor excluding itself.316
4 Simulations317
This section presents various simulations created with the aid of Python packages [32–35] which were318 used to experimentally verify the validity and performance of our proposed Dec_UCB algorithm. We319 focus on the heterogeneous reward distribution case here. Additional simulations and observations,320 including the homogeneous reward distribution case, are presented in Appendix C.321
Small-size Graphs Simulations were run on three types of graphs, namely strongly connected,322 undirected connected, and weakly connected graphs1, allowing for the reward distribution to vary323 between agents for a given arm. A given agent and arm pair can draw rewards from an arm-specific324 Beta distribution with mean µk and standard deviation 0.05, an arm-specific Bernoulli distribution325 with mean µk, or an arm-specific truncated normal distribution within [0, 1] with mean µk and326 standard deviation 0.05. The distribution used is randomly assigned to each agent/arm pair upon327 initialization. The reward means µk are the same for all agents on a given arm, with each µk randomly328 chosen from a uniform distribution on [0.05, 0.95]. Rewards are bounded by definition from the329 used distributions to be within [0, 1]. Each experiment is run for T = 1000 time steps with results330 for each graph obtained by averaging over 100 experiments. The results obtained from running331 Dec_UCB alongside UCB1 on small 6-agent graphs are illustrated in Figures 1, 2, and 3 for the three332 graph types, respectively. These results empirically back the claims of Theorem 1, Theorem 2, and333 Corollaries 1–3 in the presence of heterogeneous arm reward distributions.334
Large-scale Graphs Larger scale simulations were run for the three graph types with heterogeneous335 reward distributions, averaging results from 100 different randomly generated Erdős–Rényi 50-agent336 graphs for each graph type. Additionally, 10 arms with rewards following a randomly chosen Beta,337 Bernoulli, or truncated normal distribution were used, with means µk randomly chosen from a338 uniform distribution bounded within [0.05, 0.95]. A standard deviation of 0.05 was used for the Beta339 and truncated normal distributions. Rewards were bounded by the used distributions to be within340 [0, 1]. The algorithms were run for T = 1000 iterations for each different random graph, testing the341
1We focus on 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 case.
worst performing agent of Dec_UCB against the best performing results from the UCB1 algorithm.342 Results are shown in Figure 4. In all cases, Dec_UCB achieves better performance than UCB1.
343
Observations There are several key observations to take from these simulations. The first of these is344 that Dec_UCB appears to perform better on the undirected graphs than it does on the strongly connected345 graphs. This validates the theoretical results presented in Theorem 2 and Corollary 2. Additionally,346 the performance of each agent in the strongly connected graphs appears to be independent of its347 number of neighbors, indicating that performance is reliant only on the diameter of the graph as348 demonstrated in Section 3.2.1. In contrast, as shown in Section 3.2.2, for undirected graphs, each349 agent’s regret also depends on its number of neighbors. In total, performance of Dec_UCB appears350 to be unaffected by the choice of using homogeneous arm rewards or heterogeneous arm rewards;351 expected cumulative regrets appear to be nearly equivalent for all graph types in either case.352
5 Conclusion353
In this paper, we have studied a decentralized multi-armed bandit problem over directed graphs354 and proposed a fully decentralized UCB algorithm, which provably achieves a better logarithmic355 asymptotic regret than the classic UCB1 algorithm provided the neighbor graph is strongly connected.356 We have further improved the algorithm’s performance for undirected graphs. Simulations have357 been provided to validate our theoretical results and test the performance on more general weakly358 connected graphs. Future directions are to study the limitations of the paper, including analysis for359 weakly connected graphs and time-varying graphs, experiments with real data sets, and development360 of a decentralized counterpart for the classic UCB2 algorithm [3].361
References362
[1] D. Bouneffouf, I. Rish, and C. Aggarwal. Survey on applications of multi-armed and contextual363 bandits. In 2020 IEEE Congress on Evolutionary Computation, 2020.364
[2] T. L. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in365 Applied Mathematics, 6(1):4–22, 1985.366
[3] P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem.367 Machine Learning, 47(2-3):235–256, 2002.368
[4] A. Slivkins. Introduction to Multi-Armed Bandits. 2019. arXiv:1904.07272v5 [cs.LG].369
[5] L. Lai, H. Jiang, and H.V. Poor. Medium access in cognitive radio networks: A competitive multi-370 armed bandit framework. In 42nd Asilomar Conference on Signals, Systems and Computers,371 pages 98–102, 2008.372
[6] K. Liu and Q. Zhao. Distributed learning in multi-armed bandit with multiple players. IEEE373 Transactions on Signal Processing, 58(11):5667–5681, 2010.374
[7] B. Szorenyi, R. Busa-Fekete, I. Hegedus, R. Ormándi, M. Jelasity, and B. Kégl. Gossip-based375 distributed stochastic bandit algorithms. In 30th International Conference on Machine Learning,376 2013.377
[8] D. Kalathil, N. Nayyar, and R. Jain. Decentralized learning for multiplayer multiarmed bandits.378 IEEE Transactions on Information Theory, 60(4):2331–2345, 2014.379
[9] I. Bistritz and A. Leshem. Distributed multi-player bandits – a game of thrones approach. In380 32nd International Conference on Neural Information Processing Systems, pages 7222–7232,381 2018.382
[10] A. Sankararaman, A. Ganesh, and S. Shakkottai. Social learning in multi agent multi armed383 bandits. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 3(3):1–384 35, 2019.385
[11] Y. Wang, J. Hu, X. Chen, and L. Wang. Distributed bandit learning: Near-optimal regret with386 efficient communication. In International Conference on Learning Representations, 2020.387
[12] A. Dubey and A. Pentland. Differentially-private federated linear bandits. In 34th Conference388 on Neural Information Processing Systems, 2020.389
[13] C. Shi and C. Shen. Federated multi-armed bandits. In 35th AAAI Conference on Artificial390 Intelligence, 2021.391
[14] U. Madhushani and N.E. Leonard. A dynamic observation strategy for multi-agent multi-armed392 bandit problem. In European Control Conference, 2020.393
[15] U. Madhushani and N.E. Leonard. Heterogeneous explore-exploit strategies on multi-star394 networks. IEEE Control Systems Letters, 2020.395
[16] P. Landgren, V. Srivastava, and N.E. Leonard. On distributed cooperative decision-making in396 multiarmed bandits. In Proceedings of the European Control Conference, 2016.397
[17] D. Martínez-Rubio, V. Kanade, and P. Rebeschini. Decentralized cooperative stochastic bandits.398 In 33rd Conference on Neural Information Processing Systems, pages 4531–4542, 2019.399
[18] A. Jadbabaie, J. Lin, and A. S. Morse. Coordination of groups of mobile autonomous agents400 using nearest neighbor rules. IEEE Transactions on Automatic Control, 48(6):988–1001, 2003.401
[19] R. Olfati-Saber, J. A. Fax, and R. M. Murray. Consensus and cooperation in networked402 multi-agent systems. Proceedings of the IEEE, 95(1):215–233, 2007.403
[20] P. Landgren, V. Srivastava, and N.E. Leonard. Distributed cooperative decision-making in404 multiarmed bandits: Frequentist and bayesian algorithms. In Proceedings of the 55th IEEE405 Conference on Decision and Control, pages 167–172, 2016.406
[21] P. Landgrena, V. Srivastavab, and N.E. Leonarda. Distributed cooperative decision making in407 multi-agent multi-armed bandits. Automatica, 2021.408
[22] J. Zhu, R. Sandhu, and J. Liu. A distributed algorithm for sequential decision making in409 multi-armed bandit with homogeneous rewards. In Proceedings of the 59th IEEE Conference410 on Decision and Control, pages 3078–3083, 2020.411
[23] Z. Zhu, J. Zhu, J. Liu, and Y. Liu. Federated bandit: a gossiping approach. Proceedings of the412 ACM on Measurement and Analysis of Computing Systems, 5(1), 2021.413
[24] N. Nayyar, D. Kalathil, and R. Jain. On regret-optimal learning in decentralized multi-player414 multi-armed bandits. IEEE Transactions on Control of Network Systems, 2016.415
[25] C. Shi, C. Shen, and J. Yang. Federated multi-armed bandits with personalization. CoRR,416 abs/2102.13101, 2021.417
[26] T. Li, L. Song, and C. Fragouli. Federated recommendation system via differential privacy. In418 2020 IEEE International Symposium on Information Theory (ISIT), pages 2592–2597, 2020.419
[27] Z. Wang, C. Zhang, M. K. Singh, L. Riek, and K. Chaudhuri. Multitask bandit learning through420 heterogeneous feedback aggregation. In Arindam Banerjee and Kenji Fukumizu, editors,421 Proceedings of The 24th International Conference on Artificial Intelligence and Statistics,422 volume 130 of Proceedings of Machine Learning Research, pages 1531–1539. PMLR, 13–15423 Apr 2021.424
[28] F. Iutzeler, P. Ciblat, and J. Jakubowicz. Analysis of max-consensus algorithms in wireless425 channels. IEEE Transactions on Signal Processing, 60(11):6103–6107, 2012.426
[29] A. Jadbabaie, J. Lin, and A.S. Morse. Coordination of groups of mobile autonomous agents427 using nearest neighbor rules. IEEE Transactions on Automatic Control, 48(6):988–1001, 2003.428
[30] L. Xiao, S. Boyd, and S. Lall. A scheme for robust distributed sensor fusion based on average429 consensus. In Proceedings of the 4th International Conference on Information Processing in430 Sensor Networks, pages 63–70, 2005.431
[31] L. Xiao and S. Boyd. Fast linear iterations for distributed averaging. Systems & Control Letters,432 53(1):65–78, 2004.433
[32] C. R. Harris, K. J. Millman, S. J. van der Walt, et al. Array programming with NumPy. Nature,434 585(7825):357–362, September 2020.435
[33] P. Virtanen, R. Gommers, T. E. Oliphant, et al. SciPy 1.0: Fundamental Algorithms for Scientific436 Computing in Python. Nature Methods, 17:261–272, 2020.437
[34] J. D. Hunter. Matplotlib: A 2d graphics environment. Computing in Science & Engineering,438 9(3):90–95, 2007.439
[35] A. Hagberg, D. Schult, and P. Swart. Exploring network structure, dynamics, and function using440 networkx. In Gaël Varoquaux, Travis Vaught, and Jarrod Millman, editors, Proceedings of the441 7th Python in Science Conference, pages 11 – 15, Pasadena, CA USA, 2008.442
[36] T. Lattimore and C. Szepesvári. Bandit Algorithms. Cambridge University Press, 2018.443 [37] W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the444 American Statistical Association, 58(301):13–30, 1963.445
Checklist446
1. For all authors...447 (a) Do the main claims made in the abstract and introduction accurately reflect the paper’s448 contributions and scope? [Yes] See Abstract and Section 1.449 (b) Did you describe the limitations of your work? [Yes] See Section 3.2.3 and conclusion.450 (c) Did you discuss any potential negative societal impacts of your work? [N/A]451 (d) Have you read the ethics review guidelines and ensured that your paper conforms to452 them? [Yes]453 2. If you are including theoretical results...454
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 2455 and Section 3.2.456
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix B.457 3. If you ran experiments...458
(a) Did you include the code, data, and instructions needed to reproduce the main experi-459 mental results (either in the supplemental material or as a URL)? [Yes] See Appendix C460 and the supplemental material.461
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they462 were chosen)? [Yes] See Section 4 and Appendix C.463
(c) Did you report error bars (e.g., with respect to the random seed after running experi-464 ments multiple times)? [N/A]465
(d) Did you include the total amount of compute and the type of resources used (e.g., type466 of GPUs, internal cluster, or cloud provider)? [N/A]467
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...468 (a) If your work uses existing assets, did you cite the creators? [N/A]469 (b) Did you mention the license of the assets? [N/A]470 (c) Did you include any new assets either in the supplemental material or as a URL? [N/A]471
472
(d) Did you discuss whether and how consent was obtained from people whose data you’re473 using/curating? [N/A]474
(e) Did you discuss whether the data you are using/curating contains personally identifiable475 information or offensive content? [N/A]476
5. If you used crowdsourcing or conducted research with human subjects...477 (a) Did you include the full text of instructions given to participants and screenshots, if478 applicable? [N/A]479 (b) Did you describe any potential participant risks, with links to Institutional Review480 Board (IRB) approvals, if applicable? [N/A]481 (c) Did you include the estimated hourly wage paid to participants and the total amount482 spent on participant compensation? [N/A]483

Review summaries:
A multi-agent pure-distributed (no shared data) algorithm for the stochastic Multi Armed Bandit setting is presented and analyzed. Regret 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.

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