remresetThe remreset package

# Decentralized Cooperative Stochastic Bandits

David Martínez-Rubio
Department of Computer Science
University of Oxford
Oxford, United Kingdom
<EMAIL_ADDRESS>&Varun Kanade
Department of Computer Science
University of Oxford
Oxford, United Kingdom
<EMAIL_ADDRESS>&Patrick Rebeschini
Department of Statistics
University of Oxford
Oxford, United Kingdom
<EMAIL_ADDRESS>
###### Abstract

We study a decentralized cooperative stochastic multi-armed bandit problem
with $K$ arms on a network of $N$ agents. In our model, the reward
distribution of each arm is the same for each agent and rewards are drawn
independently across agents and time steps. In each round, each agent chooses
an arm to play and subsequently sends a message to her neighbors. The goal is
to minimize the overall regret of the entire network. We design a fully
decentralized algorithm that uses an accelerated consensus procedure to
compute (delayed) estimates of the average of rewards obtained by all the
agents for each arm, and then uses an upper confidence bound (UCB) algorithm
that accounts for the delay and error of the estimates. We analyze the regret
of our algorithm and also provide a lower bound. The regret is bounded by the
optimal centralized regret plus a natural and simple term depending on the
spectral gap of the communication matrix. Our algorithm is simpler to analyze
than those proposed in prior work and it achieves better regret bounds, while
requiring less information about the underlying network. It also performs
better empirically.

##  1 Introduction

The multi-armed bandit (MAB) problem is one of the most widely studied
problems in online learning. In the most basic setting of this problem, an
agent has to pull one among a finite set of arms (or actions), and she
receives a reward that depends on the chosen action. This process is repeated
over a finite time-horizon and the goal is to get a cumulative reward as close
as possible to the reward she could have obtained by committing to the best
fixed action (in hindsight). The agent only observes the rewards corresponding
to the actions she chooses, i.e., the _bandit_ setting as opposed to the full-
information setting.

There are two main variants of the MAB problem—the stochastic and adversarial
versions. In this work, our focus is on the former, where each action yields a
reward that is drawn from a fixed unknown (but stationary) distribution. In
the latter version, rewards may be chosen by an adversary who may be aware of
the strategy employed by the agent, but does not observe the random choices
made by the agent. Optimal algorithms have been developed for both the
stochastic and the adversarial versions (cf. [9] for references). The MAB
problem epitomizes the exploration-exploitation tradeoff that appears in most
online learning settings: in order to maximize the cumulative reward, it is
necessary to trade off between the exploration of the hitherto under-explored
arms and the exploitation of the seemingly best arm. Variants of the MAB
problem are used in a wide variety of applications ranging from online
advertising systems to clinical trials, queuing and scheduling.

In several applications, the “agent” solving the MAB problem may itself be a
distributed system, e.g., [15, 35, 36, 33, 10, 1]. The reason for using
decentralized computation may be an inherent restriction in some cases, or it
could be a choice made to improve the total running time—using $N$ units
allows $N$ arms to be pulled at each time step. When the agent is a
distributed system, restrictions on communication in the system introduce
additional tradeoffs between communication cost and regret. Apart from the one
considered in this work, there are several formulations of decentralized or
distributed MAB problems, some of which are discussed in the related work
section below.

Problem Formulation. This work focuses on a _decentralized_ stochastic MAB
problem. We consider a network consisting of $N$ agents that play the _same_
MAB problem _synchronously_ for $T$ rounds, and the goal is to obtain regret
close to that incurred by an optimal centralized algorithm running for $NT$
rounds ($NT$ is the total number of arm pulls made by the decentralized
algorithm). At each time step, all agents simultaneously pull some arm and
obtain a reward drawn from the distribution corresponding to the pulled arm.
The rewards are drawn independently across the agents and the time steps.
After the rewards have been received, the agents can send messages to their
neighbors.

Main Contributions. We solve the decentralized MAB problem using a _gossip_
algorithm.111A high-level description of some distributed algorithms is given
in the related work section. For further details, the reader is referred to
the references in that section. Our algorithm incurs regret equal to the
optimal regret in the centralized problem plus a term that depends on the
spectral gap of the underlying communication graph and the number of agents
(see Theorem 3.2 for a precise statement). At the end of each round, each
agent sends $O(K)$ values to her neighbors. The amount of communication
permitted can be reduced at the expense of incurring greater regret, capturing
the communication-regret tradeoff. The algorithm needs to know the total
number of agents in the network and an upper bound on the spectral gap of the
communication matrix. We assume the former for clarity of exposition, but the
number of nodes can be estimated, which is enough for our purposes (cf.
Appendix F). The latter is widely made in the decentralized literature [7, 30,
14, 13].

The key contribution of our work is an algorithm for the decentralized setting
that exhibits a natural and simple dependence on the spectral gap of the
communication matrix. In particular, for our algorithm we have:

  * •

A regret bound that is simpler to interpret, and asymptotically lower compared
to other algorithms previously designed for the same setting. We use delayed
estimators of the relevant information that is communicated in order to
significantly reduce their variance.

  * •

A graph-independent factor multiplying $\log T$ in the regret as opposed to
previous works.

  * •

Our algorithm is fully decentralized and can be implemented on an arbitrary
network, unlike some of the other algorithms considered in the literature,
which need to use extra global information. This is of interest for
decentralization purposes but also from the point of view of the total
computational complexity.

  * •

We use accelerated communication, which reduces the regret dependence on the
spectral gap, which is important for scalability purposes.

Future work. Decentralized algorithms of this kind are a first step towards
solving problems on time-varying graphs or on networks prone to communication
errors. We leave for future research an extension to time-varying graphs or
graphs with random edge failures. Further future research can include a change
in the model to allow asynchronous communication, making some assumptions on
the nodes so they have comparable activation frequencies.

###  1.1 Related Work

Distributed Algorithms. The development of distributed algorithms for
optimization and decision-making problems has been an active area of research,
motivated in part by the recent development of large scale distributed systems
that enable speeding up computations. In some cases, distributed computation
is a necessary restriction that is part of the problem, as is the case in
packet routing or sensor networks. _Gossip algorithms_ are a commonly used
framework in this area [7, 28, 31, 13, 14, 30]. In gossip algorithms, we have
an iterative procedure with processing units at the nodes of a graph and the
communication pattern dictated by the edges of the graph. A common sub-problem
in these applications is to have a value at each node that we want to average
or synchronize across the network. In fact, most solutions reduce to
approximate averaging or synchronization. This can be achieved using the
following simple and effective method: make each node compute iteratively a
weighted average of its own value and the ones communicated by its neighbors,
ensuring that the final value at each node converges to the average of the
initial values across the network. Formally, this communication can be
represented as a multiplication by a matrix $P$ that respects the network
structure and satisfies some conditions that guarantee fast averaging. The
averaging can be accelerated by the use of Chebychev polynomials (see Lemma
3.1).

Decentralized Bandits. There are several works that study stochastic and
nonstochastic distributed or decentralized multi-armed bandit problems, but
the precise models vary considerably.

In the stochastic case, the work of Landgren et al. [25, 24] proposes three
algorithms to solve the same problem that we consider in this paper: coop-UCB,
coop-UCB2 and coop-UCL. The algorithm coop-UCB follows a variant of the
natural approach to solve this problem that is discussed in Section 3. It
needs to know more global information about the graph than just the number of
nodes and the spectral gap: the algorithm uses a value per node that depends
on the whole spectrum and the set of eigenvectors of the communication matrix.
The algorithm coop-UCB2 is a modification of coop-UCB, in which the only
information used about the graph is the number of nodes, but the regret is
significantly greater. Finally, coop-UCL is a Bayesian algorithm that also
incurs greater regret than coop-UCB. Our algorithm obtains lower asymptotic
regret than all these algorithms while retaining the same computational
complexity (cf. Remark 3.4).

Our work draws on techniques on gossip acceleration and stochastic bandits
with delayed feedback. A number of works in the literature consider Chebyshev
acceleration applied to gossip algorithms, e.g., [2, 30]. There are various
works about learning with delayed feedback. The most relevant work to our
problem is [19] which studies general online learning problems under delayed
feedback. Our setting differs in that we not only deal with delayed rewards
but with approximations of them.

Several other variants of distributed stochastic MAB problems have been
proposed. Chakraborty et al. [12] consider the setting where at each time
step, the agents can either broadcast the last obtained reward to the whole
network or pull an arm. Korda et al. [22] study the setting where each agent
can only send information to one other agent per round, but this can be any
agent in the network (not necessarily a neighbor). Szörényi et al. [34] study
the MAB problem in P2P random networks and analyze the regret based on delayed
reward estimates. Some other works do not assume independence of the reward
draws across the network. Liu and Zhao [26] and Kalathil et al. [20] consider
a distributed MAB problem with collisions: if two players pull the same arm,
the reward is split or no reward is obtained at all. Moreover in the latter
work and a follow-up [27], the act of communicating increases the regret.
Anandkumar et al. [1] also consider a model with collisions and agents have to
learn from _action collisions_ rather than by exchanging information.
Shahrampour et al. [32] consider the setting where each agent plays a
different MAB problem and the total regret is minimized in order to identify
the best action when averaged across nodes. Nodes only send values to their
neighbors but it is not a completely decentralized algorithm, since at each
time step the arm played by all the nodes is given by the majority vote of the
agents. Xu et al. [38] study a distributed MAB problem with global feedback,
i.e., with no communication involved. Kar et al. [21] also consider a
different distributed bandit model in which only one agent observes the
rewards for the actions she plays, while the others observe nothing and have
to rely on the information broadcast by the first agent.

The problem of identifying an $\varepsilon$-optimal arm using a distributed
network has also been studied. Hillel et al. [16] provide matching upper and
lower bounds in the case that the communication happens only once and when the
graph topology is restricted to be the complete graph. They provide an
algorithm that achieves a speed up of $N$ (the number agents) if $\log
1/\varepsilon$ communication steps are permitted.

In the adversarial version, the best possible regret bound in the centralized
setting is still $\sqrt{KT}$ [3]. In the decentralized case, a trivial
algorithm that has no communication incurs regret $N\sqrt{KT}$; and a lower
bound of $N\sqrt{T}$ is known [11]; thus, only the dependence on $K$ can be
improved. Awerbuch and Kleinberg [6] study a distributed adversarial MAB
problem with some Byzantine users, i.e., users that do not follow the protocol
or report fake observations as they wish. In the case in which there are no
Byzantine users they obtain a regret of $O(T^{2/3}(N+K)\log N\log T)$. To the
best of our knowledge, this is the first work that considers a decentralized
adversarial MAB problem. They allow $\log(N)$ communication rounds between
decision steps so it differs with our model in terms of communication. Also in
the adversarial case, Cesa-Bianchi et al. [11] studied an algorithm that
achieves regret $N(\sqrt{K^{1/2}T\log K}+\sqrt{K}\log T)$ and prove some
results that are graph-dependent. The model is the same as ours, but in
addition to the rewards she obtained, each agent communicates to her neighbors
all the values she received from her neighbors in the last $d$ rounds, that is
potentially $O(Nd)$. Thus, the size of each message could be more than
$\poly(K)$ at a given round. They get the aforementioned regret bound by
setting $d=\sqrt{K}$.

##  2 Model and Problem Formulation

We consider a multi-agent network with $N$ agents. The agents are represented
by the nodes of an undirected and connected graph $G$ and each agent can only
communicate to her neighbors. Agents play the same $K$-armed bandit problem
for $T$ time steps, send some values to their neighbors after each play and
receive the information sent by their respective neighbors to use it in the
next time step if they so wish. If an agent plays arm $k$, she receives a
reward drawn from a fixed distribution with mean $\mu_{k}$ that is independent
of the agent. The draw is independent of actions taken at previous time steps
and of actions played by other agents. We assume that rewards come from
distributions that are subgaussian with variance proxy $\sigma^{2}$.

Assume without loss of generality that
$\mu_{1}\geq\mu_{2}\geq\cdots\geq\mu_{K}$, and let the suboptimality gap be
defined as $\Delta_{k}:=\mu_{1}-\mu_{k}$ for any action $k$. Let $I_{t,i}$ be
the random variable that represents the action played by agent $i$ at time
$t$. Let $n_{t,i}^{k}$ be the number of times arm $k$ is pulled by node $i$ up
to time $t$ and let $n_{t}^{k}:=\sum_{i=1}^{N}n_{t,i}^{k}$ be the number of
times arm $k$ is pulled by all the nodes in the network up to time $t$. We
define the regret of the whole network as

$R(T):=TN\mu_{1}-\mathbb{E}\left[\sum_{t=1}^{T}\sum_{i=1}^{N}\mu_{I_{t,i}}\right]=\sum_{k=1}^{K}\Delta_{k}\mathbb{E}\left[n_{T}^{k}\right].$

We will use this notion of regret, which is the expected regret, in the entire
paper.

The problem is to minimize the regret while allowing each agent to send
$\poly(K)$ values to her neighbors per iteration. We allow to know only little
information about the graph. The total number of nodes and an lower bound on
the spectral gap of the communication matrix $P$, i.e. $1-|\lambda_{2}|$. Here
$\lambda_{2}$ is the second greatest eigenvalue of $P$ in absolute value. The
communication matrix can be build with little extra information about the
graph, like the maximum degree of nodes of the graph [37]. However, building
global structures is not allowed. For instance, a spanning tree to propagate
the information with a message passing algorithm is not valid. This is because
our focus is on designing a decentralized algorithm. Among other things,
finding these kinds of decentralized solutions serves as a first step towards
the design of solutions for the same problem in time varying graphs or in
networks prone to communication errors.

##  3 Algorithm

We propose an algorithm that is an adaptation of UCB to the problem at hand
that uses a gossip protocol. We call the algorithm Decentralized Delayed Upper
Confidence Bound (DDUCB). UCB is a popular algorithm for the stochastic MAB
problem. At each time step, UCB computes an upper bound of a confidence
interval for the mean of each arm $k$, using two values: the empirical mean
observed, $\mu_{t}^{k}$, and the number of times arm $k$ was pulled,
$n_{t}^{k}$. UCB plays at time $t+1$ the arm that maximizes the following
upper confidence bound

$\mu_{t}^{k}+\sqrt{\frac{4\eta\sigma^{2}\ln t}{n_{t}^{k}}},$

where $\eta>1$ is an exploration parameter.

In our setting, as the pulls are distributed across the network, agents do not
have access to these two values, namely the number of times each arm was
pulled across the network and the empirical mean reward observed for each arm
computed using the total number of pulls. Our algorithm maintains good
approximations of these values and it incurs a regret that is no more than the
one for a centralized UCB plus a term depending on the spectral gap and the
number of nodes, but independent of time. The latter term is a consequence of
the approximation of the aforementioned values. Let $m_{t}^{k}$ be the sum of
rewards coming from all the pulls done to arm $k$ by the entire network up to
time $t$. We can use a gossip protocol, for every $k\in\\{1,\dots,K\\}$, to
obtain at each node a good approximation of $m_{t}^{k}$ and the number of
times arm $k$ was pulled, i.e. $n_{t}^{k}$. Let $\widehat{m}_{t,i}^{k}$,
$\widehat{n}_{t,i}^{k}$ be the approximations of $m_{t}^{k}$ and $n_{t}^{k}$
made by node $i$ with a gossip protocol at time $t$, respectively. Having this
information at hand, agents could compute the ratio
$\widehat{m}_{t,i}^{k}/\widehat{n}_{t,i}^{k}$ to get an estimation of the
average reward of each arm. But care needs to be taken when computing the
foregoing approximations.

A classical and effective way to keep a running approximation of the average
of values that are iteratively added at each node is what we will refer to as
the running consensus [8]. Let $\mathcal{N}(i)$ be the set of neighbors of
agent $i$ in graph $G$. In this protocol, every agent stores her current
approximation and performs communication and computing steps alternately: at
each time step each agent computes a weighted average of her neighbors’ values
and adds to it the new value she has computed. We can represent this operation
in the following way. Let $P\in\mathbb{R}^{N\times N}$ be a matrix that
respects the structure of the network, which is represented by a graph $G$. So
$P_{ij}=0$ if there is no edge in $G$ that connects $j$ to $i$. We consider
$P$ for which the sum of each row and the sum of each column is $1$, which
implies that $1$ is an eigenvalue of $P$. We further assume all other
eigenvalues of $P$, namely $\lambda_{2},\dots,\lambda_{N}$, are real and are
less than one in absolute value, i.e.,
$1=\lambda_{1}>|\lambda_{2}|\geq\cdots\geq|\lambda_{N}|\geq 0$. Note that they
are sorted by magnitude. For matrices with real eigenvalues, these three
conditions hold if and only if values in the network are averaged, i.e.,
$P^{s}$ converges to $\mathds{1}\mathds{1}^{\top}/N$ for large $s$. This
defines a so called gossip matrix. See [37] for a proof and [14, 37] for a
discussion on how to choose $P$. If we denote by $x_{t}\in\mathbb{R}^{N}$ the
vector containing the current approximations for all the agents and by
$y_{t}\in\mathbb{R}^{N}$ the vector containing the new values added by each
node, then the running consensus can be written as

$x_{t+1}=Px_{t}+y_{t}.$ (1)

The conditions imposed on $P$ not only ensure that values are averaged but
also that the averaging process is fast. In particular, for any
$s\in\mathbb{N}$ and any $v$ in the $N$-dimensional simplex

$\left\|P^{s}v-\mathds{1}/N\right\|_{2}\leq\left\lvert\lambda_{2}\right\rvert^{s},$
(2)

see [17], for instance. For a general vector, rescale the inequality by its
$1$-norm. A natural approach to the problem is to use $2K$ running consensus
algorithms, computing approximations of $m_{t}^{k}/N$ and $n_{t}^{k}/N$,
$k=1,\dots,K$. Landgren et al. [25] follow this approach and use extra global
information of the graph, as described in the section on related work, to
account for the inaccuracy of the mean estimate. We can estimate average
rewards by their ratio and the number of times each arm was pulled can be
estimated by multiplying the quantity $n_{t}^{k}/N$ by $N$. The running
consensus protocols would be the following. For $k=1,\dots,K$, start with
$\widehat{m}_{1}^{k}=0\in\mathbb{R}^{N}$ and update
$\widehat{m}_{t+1}^{k}=P\widehat{m}_{t}^{k}+\pi_{t}^{k}$, where the $i$-${th}$
entry of $\pi_{t}^{k}\in\mathbb{R}^{N}$ contains the reward observed by node
$i$ at time $t$ if arm $k$ is pulled. Else, it is $0$. Note that the
$i$-${th}$ entry is only computed by the $i$-${th}$ node. Similarly, for
$k=1,\dots,K$, start with $\widehat{n}_{1}^{k}=0\in\mathbb{R}^{N}$ and update
$\widehat{n}_{t+1}^{k}=P\widehat{n}_{t}^{k}+p_{t}^{k}$, where the $i$-${th}$
entry of $p_{t}^{k}\in\mathbb{R}^{N}$ is $1$ if at time $t$ node $i$ pulled
arm $k$ and $0$ otherwise.

The problem with this approach is that even if the values computed are being
mixed at a fast pace it takes some time for the last added values to be mixed,
resulting in poor approximations, especially if $N$ is large. This phenomenon
is more intense when the spectral gap is smaller. Indeed, we can rewrite (1)
as $x_{t}=\sum_{s=1}^{t-1}P^{t-1-s}y_{s}$, assuming that $x_{1}=0$. For the
values of $s$ that are not too close to $t-1$ we have by (2) that
$P^{t-1-s}y_{s}$ is very close to the vector that has as entries the average
of the values in $y_{s}$, that is, $c\mathds{1}$, where
$c=\frac{1}{N}\sum_{j=1}^{N}y_{s,j}$. However, for values of $s$ close to
$t-1$ this is not true and the values of $y_{s}$ influence heavily the
resulting estimate, being specially inaccurate as an estimation of the true
mean if $N$ is large. The key observations that lead to the algorithm we
propose are that the number of these values of $s$ close to $t-1$ is small,
that we can make it even smaller using accelerated gossip techniques and that
the regret of UCB does not increase much when working with delayed values of
rewards so we can temporarily ignore the recently computed rewards in order to
work with much more accurate approximations of $m_{t}^{k}/N$ and
$n_{t}^{k}/N$. In particular, with $C$ communication steps agents can compute
a polynomial $q_{C}$ of degree $C$ of the communication matrix $P$ applied to
a vector, that is, $q_{C}(P)v$. The acceleration comes from computing a
rescaled Chebyshev polynomial and it is encapsulated in the following lemma.
It is the same one can find in previous works [30]. See the supplementary
material for a proof and for the derivation of Section 3 that computes
$(q_{C}(P)v)_{i}$ iteratively after $C$ calls.

######  Lemma 3.1.

Let $P$ be a communication matrix with real eigenvalues such that
$\mathds{1}^{\top}P=\mathds{1}^{\top}$, $P\mathds{1}=\mathds{1}$ and whose
second largest eigenvalue in absolute value is $-1<\lambda_{2}<1$. Let $v$ be
in the $N$-dimensional simplex and let
$C=\lceil\ln(2N/\varepsilon)/\sqrt{2\ln(1/|\lambda_{2}|)}\rceil$. Agents can
compute, after $C$ communication steps, a polynomial $q_{C}$ of degree $C$
which satisfies $\left\|q_{C}(P)v-\mathds{1}/N\right\|_{2}\leq\varepsilon/N$.

Given the previous lemma, we consider that any value that has been computed
since at least $C$ iterations before the current time step is mixed enough to
be used to approximate $m_{t}^{k}/N$ and $n_{t}^{k}/N$.

We now describe DDUCB at node $i$. The pseudocode is given in Section 3. We
use Greek letters to denote variables that contain rewards estimators, and
corresponding Latin letters to denote variables that contain counter
estimators. A notation chart can be found in the supplementary material.
Agents run an accelerated running consensus in stages of $C$ iterations. Each
node maintains three pairs of K-dimensional vectors. The variable $\alpha_{i}$
contains rewards that are mixed, $\beta_{i}$ contains rewards that are being
mixed and $\gamma_{i}$ contains rewards obtained in the current stage. The
vectors $a_{i}$, $b_{i}$ and $c_{i}$ store the number of arm pulls associated
to the quantities $\alpha_{i}$, $\beta_{i}$ and $\gamma_{i}$, respectively. At
the beginning, agent $i$ pulls each arm once and initialize $\alpha_{i}$ and
$a_{i}$ with the observed values divided by $N$. During each stage, for $C$
iterations, agent $i$ uses $\alpha_{i}$ and $a_{i}$, as updated at the end of
the previous stage, to decide which arm to pull using an upper confidence
bound. Variables $\beta_{i}$ and $b_{i}$ are mixed in an accelerated way and
$\gamma_{i}$ and $c_{i}$ are added new values obtained by the new pulls done
in the current stage. After $C$ iterations, values in $\beta_{i}$ and $b_{i}$
are mixed enough so we add them to $\alpha_{i}$ and $a_{i}$. The only
exception being the end of the first stage in which the values of the latter
variables are overwritten by the former ones. Variables $\delta_{i}$ and
$d_{i}$ just serve to make this distinction. The unmixed information about the
pulls obtained in the last stage, i.e. $\gamma_{i}$ and $c_{i}$, is assigned
to $\beta_{i}$ and $b_{i}$ so the process can start again. Variables
$\gamma_{i}$ and $c_{i}$ are reset with zeroes. There are $T$ iterations in
total.

Algorithm 1 DDUCB at node $i$. 1:$\zeta_{i}\leftarrow$
$(X_{i}^{1},\dots,X_{i}^{K})$ ; $z_{i}\leftarrow(1,\dots,1)$
2:$C=\lceil\ln(2N/\varepsilon)/\sqrt{2\ln(1/|\lambda_{2}|)}\rceil$
3:$\alpha_{i}\leftarrow\zeta_{i}/N$ ;$a_{i}\leftarrow z_{i}/N$
;$\beta_{i}\leftarrow\zeta_{i}$ ;$b_{i}\leftarrow z_{i}$
4:$\gamma_{i}\leftarrow$ 0 ; $c_{i}\leftarrow$ 0 ; $\delta_{i}\leftarrow$ 0 ;
$d_{i}\leftarrow$ 0 5:$t\leftarrow K$ ; $s\leftarrow K$ 6:while $t\leq T$ do
7: $k^{\ast}\leftarrow\operatorname*{arg\,max}_{k}\left\\{\
\frac{\alpha_{i}^{k}}{a_{i}^{k}}+\sqrt{\frac{2\eta\sigma^{2}\ln
s}{Na_{i}^{k}}}\right\\}$ 8: for $r\text{ from }0\text{ to }C-1$ do 9:
$u\leftarrow$ Play arm $k^{\ast}$, return reward  10:
$\gamma_{i}^{k^{\ast}}\leftarrow\gamma_{i}^{k^{\ast}}+u$ ;
$c_{i}^{k^{\ast}}\leftarrow c_{i}^{k^{\ast}}+1$ 11: $\beta_{i}\leftarrow$
mix$(\beta_{i},r,i)$ ; $b_{i}\leftarrow$ mix$(b_{i},r,i)$ 12: $t\leftarrow
t+1$ 13: if $t>T$ then return end if 14: end for 15: $s\leftarrow(t-C)N$ 16:
$\delta_{i}\\!\leftarrow\\!\delta_{i}+\\!\beta_{i}$
;$d_{i}\\!\leftarrow\\!d_{i}+\\!b_{i}$ ;$\alpha_{i}\\!\leftarrow\\!\delta_{i}$
;$a_{i}\\!\leftarrow\\!d_{i}$ 17: $\beta_{i}\leftarrow\gamma_{i}$ ;
$b_{i}\leftarrow c_{i}$ ; $\gamma_{i}\leftarrow$ 0 ; $c_{i}\leftarrow$ 0
18:end while Algorithm 2 Accelerated communication and mixing step.
mix$(y_{r,i},r,i)$ 1:if $r$ is $0$ then 2: $w_{0}\leftarrow 1/2$;
$w_{-1}\leftarrow 0$ 3: $y_{0,i}\leftarrow y_{0,i}/2$;
$y_{-1,i}\leftarrow(0,\dots,0)$ 4:end if 5:Send $y_{r,i}$ to neighbors
6:Receive corresp.values $y_{r,j},\forall j\\!\in\\!\mathcal{N}(i)$
7:$y_{r,i}^{\prime}\leftarrow\sum_{j\in\mathcal{N}(i)}2P_{ij}y_{r,j}/|\lambda_{2}|$
8:$w_{r+1}\leftarrow 2w_{r}/|\lambda_{2}|-w_{r-1}$
9:$y_{r+1,i}=\frac{w_{r}}{w_{r+1}}y_{r,i}^{\prime}-\frac{w_{r-1}}{w_{r+1}}y_{r-1,i}$
10:if $r$ is $0$ then 11: $y_{0,i}\leftarrow 2y_{0,i}$ ; $w_{0}\leftarrow
2w_{0}$ 12:end if 13:return $y_{r+1,i}$

Now we describe some mathematical properties about the variables during the
execution of the algorithm. Let $t_{S}$ be the time at which a stage begins,
so it ends at $t_{S}+C-1$. At $t=t_{S}$, using the notation above, it is
$\alpha_{i}^{k}=\sum_{s=1}^{t_{S}-C}\left(q_{C}(P)\pi_{s}^{k}\right)_{i}$ and
$a_{i}^{k}=\sum_{s=1}^{t_{S}-C}\left(q_{C}(P)p_{s}^{k}\right)_{i}$ but in the
first stage, in which their values are initialized from a local pull. In
particular, denote $X_{i}^{1},\dots,X_{i}^{K}$ the rewards obtained when
pulling all the arms before starting the first stage. Then the initialization
is $\alpha_{i}\leftarrow(X_{i}^{1}/N,\dots,X_{i}^{K}/N)$ and
$a_{i}\leftarrow(1/N,\dots,1/N)$. The division by $N$ is due to
$\alpha_{i}^{k}$ and $a_{i}^{k}$ being the approximations for $m_{t,i}^{k}/N$
and $n_{t,i}^{k}/N$. The algorithm does not update $\alpha_{i}$ and $a_{i}$
again until $t=t_{S}+C$, so they contain information that at the end of the
stage is delayed by $2C-1$ iterations. The time step $s$ used to compute the
upper confidence bound is $(t_{S}-C)N$, since $\alpha_{i}$ and $a_{i}$ contain
information about that number of rewards and pulls. The variable $\gamma_{i}$
is needed because we need to mix $\beta_{i}$ for $C$ steps so the Chebyshev
polynomial of degree $C$ is computed. In this way agents compute upper
confidence bounds with accurate approximations, with a delay of at most
$2C-1$. As we will see, the regret of UCB does not increase much when working
with delayed estimates. In particular, having a delay of $\mathfrak{d}$ steps
increases the regret by at most $\mathfrak{d}\sum_{k=1}^{K}\Delta_{k}$.

We now present the regret which the DDUCB algorithm incurs. We use $A\lesssim
B$ to denote there is a constant $c>0$ such that $A\leq cB$. See Section A.1
for a proof.

######  Theorem 3.2 (Regret of DDUCB).

Let $P$ be a communication matrix with real eigenvalues such that
$\mathds{1}^{\top}P=\mathds{1}^{\top}$, $P\mathds{1}=\mathds{1}$ whose second
largest eigenvalue in absolute value is $\lambda_{2}$, with
$\left\lvert\lambda_{2}\right\rvert<1$. Consider the distributed multi-armed
bandit problem with $N$ nodes, $K$ actions and subgaussian rewards with
variance proxy $\sigma^{2}$. The algorithm DDUCB with exploration parameter
$\eta=2$ and $\varepsilon=1/22$ satisfies:

  1. 1.

The following finite-time bound on the regret, for
$C=\lceil\frac{\log(2N/\varepsilon)}{\sqrt{2\ln(1/|\lambda_{2}|)}}\rceil$

$\displaystyle\begin{aligned}
R(T)<&\sum_{k:\Delta_{k}>0}\frac{32(1+1/11)\sigma^{2}\ln(TN)}{\Delta_{k}}+\bigg{(}N(6C+1)+4\bigg{)}\sum_{k=1}^{K}\Delta_{k}.\end{aligned}$

  2. 2.

The corresponding asymptotic bound:

$R(T)\lesssim\sum_{k:\Delta_{k}>0}\frac{\sigma^{2}\ln(TN)}{\Delta_{k}}+\frac{N\ln(N)}{\sqrt{\ln(1/\left\lvert\lambda_{2}\right\rvert)}}\sum_{k=1}^{K}\Delta_{k}.$

For simplicity and comparison purposes we set the value of $\eta$ and
$\varepsilon$ to specific values. For a general version of Theorem 3.2, see
the supplementary material. Note that the algorithm needs to know
$\lambda_{2}$, the second largest eigenvalue of $P$ in absolute value, since
it is used to compute $C$, which is a parameter that indicates when values are
close enough to be mixed. However, if we use DDUCB with $C$ set to any upper
bound $E$ of $C=\lceil\log(2N/\varepsilon)/\sqrt{2\ln(1/|\lambda_{2}|)}\rceil$
the inequality of the finite-time analysis above still holds true,
substituting $C$ by $E$. In the asymptotic bound, $N\ln
N/\sqrt{\ln(1/\left\lvert\lambda_{2}\right\rvert)}$ would be substituted by
$NE$. The knowledge of the spectral gap is an assumption that is widely made
throughout the decentralized literature [30, 14, 13]. We can use Theorem 3.2
to derive an instance-independent analysis of the regret. See Theorem A.3 in
the supplementary material.

######  Remark 3.3 (Lower bound).

In order to interpret the regret obtained in the previous theorem, it is
useful to note that running the centralized UCB algorithm for $TN$ steps
incurs a regret bounded above by
$\sum_{k:\Delta_{k}>0}\frac{\sigma^{2}\ln(TN)}{\Delta_{k}}+\sum_{k=1}^{K}\Delta_{k}$,
up to a constant. Moreover, running $N$ separate instances of UCB at each node
without allowing communication incurs a regret of
$R(T)\lesssim\sum_{k:\Delta_{k}>0}\frac{N\sigma^{2}\ln(T)}{\Delta_{k}}+N\sum_{k=1}^{K}\Delta_{k}$.
On the other hand, the following is an asymptotic lower bound for any
consistent centralized policy [23]:
$\liminf\limits_{T\rightarrow\infty}\frac{R(T)}{\ln
T}\geq\sum_{k:\Delta_{k}>0}\frac{2\sigma^{2}}{\Delta_{k}}.$

Thus, we see that the regret obtained in Theorem 3.2 improves significantly
the dependence on $N$ of the regret with respect to the trivial algorithm that
does not involve communication, and that it is asymptotically optimal in terms
of $T$, with $N$ and $K$ fixed. Since in the first iteration of this problem
$N$ arms have to be pulled and there is no prior information on the arms’
distribution, any asymptotically optimal algorithm in terms of $N$ and $K$
must pull $\Theta(\frac{N}{K}+1)$ times each arm, yielding regret of at least
$\left(\frac{N}{K}+1\right)\sum_{k=1}^{K}\Delta_{k}$, up to a constant. Hence,
by the lower bound above and the latter argument, we can give the following
lower bound for the problem we consider. The regret of our problem must be

$\Omega\Big{(}\sum_{k:\Delta_{k}>0}\frac{\sigma^{2}\ln(TN)}{\Delta_{k}}+\Big{(}\frac{N}{K}+1\Big{)}\sum_{k=1}^{K}\Delta_{k}\Big{)},$

and the regret obtained in Theorem 3.2 is asymptotically optimal up to at most
a factor of $\min(K,N)\ln(N)/\sqrt{\ln(1/\left\lvert\lambda_{2}\right\rvert)}$
in the second summand of the regret.

######  Remark 3.4 (Comparison with previous work).

We note that in [25] the regret bounds were computed applying a concentration
inequality that cannot be used, since it does not take into account that the
number of times an arm was pulled is a random variable. They claim their
analysis follows the one in [4], which does not present this problem. If we
changed their upper confidence bound to be proportional to $\sqrt{6\ln(tN)}$
instead of to $\sqrt{2\ln(t)}$ at time $t$ and follow [4] then, for their best
algorithm in terms of regret, named coopUCB, we can get a very similar regret
bound to the one they obtained. The regret of their algorithm is bounded by
$A+B\sum_{k=1}^{K}\Delta_{k}$, where

$\displaystyle\begin{aligned}
A&:=\sum_{k:\Delta_{k}>0}\sum_{j=1}^{N}\frac{16\gamma\sigma^{2}(1+\varepsilon^{j}_{c})}{N\Delta_{k}}\ln(TN),\quad
B&:=N\Big{(}\frac{\gamma}{\gamma-1}+\sqrt{N}\sum_{j=2}^{N}\frac{|\lambda_{j}|}{1-|\lambda_{j}|}\Big{)}.\end{aligned}$

The difference between this bound and the one presented in [25] is the $N$
inside the logarithm in $A$ and a factor of $2$ in $A$. Here, $\gamma>1$ is an
exploration parameter that the algorithm receives as input and
$\varepsilon^{j}_{c}$ is a non-negative graph-dependent value, which is only
$0$ when the graph is the complete graph. Thus $A$ is at least
$\sum_{k:\Delta_{k}>0}\frac{16\sigma^{2}\ln(TN)}{\Delta_{k}}$. Hence, up to a
constant, $A$ is always greater than the first summand in the regret of our
algorithm in Theorem 3.2. Note that $\frac{\gamma}{\gamma-1}\geq 1$ and
$\frac{1}{1-\left\lvert\lambda_{2}\right\rvert}\geq\frac{1}{\ln(\left\lvert\lambda_{2}\right\rvert^{-1})}$
so

$B\geq
N\left(1+\frac{\lambda_{2}^{\prime}}{\ln(\sqrt{N}/\lambda_{2}^{\prime})}\right),$

where
$\lambda_{2}^{\prime}:=\sqrt{N}\left\lvert\lambda_{2}\right\rvert\in[0,\sqrt{N})$.
The factor multiplying $\sum_{k=1}^{K}\Delta_{k}$ in the second summand in
Theorem 3.2 is $N\ln N/\sqrt{\ln(1/\left\lvert\lambda_{2}\right\rvert})\leq
N\ln N/\ln({1/\left\lvert\lambda_{2}\right\rvert})\leq 2B$, for
$|\lambda_{2}|\geq 1/e$, since the inequality below holds.

$\displaystyle\begin{aligned} 2B\geq
2N\Big{(}1+\frac{\lambda_{2}^{\prime}}{\ln(\sqrt{N}/\lambda_{2}^{\prime})}\Big{)}\geq\frac{N\ln
N}{\ln(\sqrt{N}/\lambda_{2}^{\prime})}\Leftrightarrow\ln
N-2\ln(\lambda_{2}^{\prime})+2\lambda_{2}^{\prime}\geq\ln N.\end{aligned}$

See the case $|\lambda_{2}|<1/e$ in Appendix D. In the case of a complete
graph, the problem reduces to a centralized batched bandit problem, in which N
actions are taken at each time step [29]. The communication in this case is
trivial, just send the obtained rewards to your neighbors, so not surprisingly
our work and [25] incur the same regret in such a case. The previous reasoning
proves, however, that for every graph our asymptotic regret is never worse and
for many graphs we get substantial improvement. Depending on the graph, $A$
and $B$ can be much greater than the lower bound we have used for both of them
for comparison purposes. In the supplementary material, for instance, we show
that in the case of a cycle graph with a natural communication matrix these
two parts are substantially worse in [25], namely $\Theta(N^{2})$ versus
$\Theta(1)$ and $\Theta(N^{7/2})$ versus $\Theta(N^{2}\log N)$ for the term
multiplying $\sum_{k:\Delta_{k}>0}\sigma^{2}\ln(TN)/\Delta_{k}$ in $A$ and for
$B$, respectively. In general, the algorithm we propose presents several
improvements. We get a graph-independent value multiplying $\ln(TN)$ in the
first summand of the regret whereas $A$ contains the $1+\varepsilon^{j}_{c}$
graph-dependent values. In $B$, just the sum
$N(\frac{\gamma}{\gamma-1}+\sqrt{N}\frac{\left\lvert\lambda_{2}\right\rvert}{1-\left\lvert\lambda_{2}\right\rvert})$
is of greater order than our second summand. Moreover, $B$ contains other
terms depending on the eigenvalues $\lambda_{j}$ for $j\geq 3$. Furthermore,
we get this while using less global information about the graph. This is of
interest for decentralization purposes. Note however it has computational
implications as well, since in principle the computation of
$\varepsilon_{c}^{j}$ needs the entire set of eigenvalues and eigenvectors of
$P$. Thus, even if $P$ were input to coopUCB, it would need to run an
expensive procedure to compute these values before starting executing the
decision process, while our algorithm does not need.

######  Remark 3.5 (Variants of DDUCB).

The algorithm can be modified slightly to obtain better estimations of
$m_{t}^{k}/N$ and $n_{t}^{k}/N$, which implies the regret is improved. The
easiest (and recommended) modification is the following. While waiting for the
vectors $\beta_{i}$ and $b_{i}$, $i=1,\dots N$ to be mixed, each node $i$ adds
to the variables $\alpha_{i}$ and $a_{i}$ the information of the pulls that
are done times $1/N$. The variable $s$ accounting for the time step has to be
modified accordingly. It contains the number of pulls made to obtain the
approximations of $\alpha_{i}$ and $a_{i}$, so it needs to be increased by one
when adding one extra reward. This corresponds to uncommenting lines 14-15 in
Algorithm 5, the pseudocode in the supplementary material. Since the values of
$\alpha_{i}$ and $a_{i}$ are overwritten after the for loop, the assignment of
$s$ after the loop remains unchanged. Note that if the lines are not
uncommented then each time the for loop is executed the $C$ pulls that are
made in a node are taken with respect to the same arm. Another variant that
would provide better estimations and therefore better regret, while keeping
the communication cost $O(K)$ would consist of also sending the information of
the new pull, $\pi_{i}$ and $p_{i}$, to the neighbors of $i$, receiving their
respective values of their new pulls and adding these values to $\alpha_{i}$
and $a_{i}$ multiplied by $1/N$, respectively. We analyze the algorithm
without any modification for the sake of clarity of exposition. The same
asymptotic upper bound on the regret in Theorem 3.2 can be computed for these
two variations.

We can vary the communication rate with some trade-offs. On the one hand, we
can mix values of $\delta_{i}$ and $d_{i}$ at each iteration of the for loop,
in an unaccelerated way and with Algorithm 3 (see Algorithm 5, line 17 in the
supplementary material), to get even more precise estimations. In such a case,
we could use $\delta_{i}$ and $d_{i}$ to compute the upper confidence bounds
instead of $\alpha_{i}$ and $a_{i}$. However, that approach cannot benefit
from using the information from local pulls obtained during the stage. On the
other hand, if each agent could not communicate $2K$ values per iteration,
corresponding to the mixing in line 11, the algorithm can be slightly modified
to account for it at the expense of incurring greater regret. Suppose each
agent can only communicate $L$ values to her neighbors per iteration. Let $E$
be $\lceil 2KC/L\rceil$. If each agent runs the algorithm in stages of $E$
iterations, ensuring to send each element of $\beta_{i}$ and $b_{i}$ exactly
$C$ times and using the mixing step $C$ times, then the bounds in Theorem 3.2,
substituting $C$ by $E$, still hold. Again, in the asymptotic bound, $N\ln
N/\sqrt{\ln(1/\left\lvert\lambda_{2}\right\rvert)}$ would be substituted by
$NE$. In each iteration, agents have to send values corresponding to the same
entries of $\beta_{i}$ or $b_{i}$. The factor of $C$ in the second summand of
the regret accounts for the number of rounds of delay since a reward is
obtained until it is used to compute upper confidence bounds. If we decrease
the communication rate and compensate it with a greater delay, the
approximations in $\alpha_{i}$ and $a_{i}$ satisfy the same properties as in
the original algorithm. Only the second summand in the regret increases
because of an increment of the delay.

Experiments. We show that the algorithm proposed in this work, DDUCB, does not
only enjoy a better theoretical regret guarantee but it also performs better
in practice. In general we have observed that the accelerated method performs
well with the recommended values, that is, no tuning, for the exploration
parameter $\eta$ and the parameter $\varepsilon$ that measures the precision
of the mixing after a stage. Remember these values are $\eta=2$,
$\varepsilon=\frac{1}{22}$. On the other hand the constant $C$ that results in
the unaccelerated method is usually excessively large, so it is convenient to
heuristically decrease it, which corresponds to using a different value of
$\varepsilon$. We set $\varepsilon$ so the value of $C$ for the unaccelerated
method is the same as the value of $C$ for the accelerated one. We have used
the recommended modification of DDUCB consisting of adding to the variables
$\alpha_{i}$ and $a_{i}$ the information of the pulls that are done times
$1/N$ while waiting for the vectors $\beta_{i}$ and $b_{i}$ to be mixed. This
modification adds extra information that is at hand at virtually no
computational cost so it is always convenient to use it.

We tuned $\gamma$, the exploration parameter of coopUCB [25], to get best
results for that algorithm and plot the executions for the best $\gamma$’s and
also $\gamma=2$ for comparison purposes. In the figures one can observe that
after a few stages, DDUCB algorithms learn with high precision which the best
arm is and the regret curve that is observed afterwards shows an almost
horizontal behavior. After $10000$ iterations, coopUCB not only accumulates a
greater regret but the slope indicates that it still has not learned
effectively which the best arm is.

See Appendix G for a more detailed description about the experiments.

Figure 1: Simulation of DDUCB and coopUCB for cycles (top) and square grids
(bottom) for $100$ nodes (left) , $200$ nodes (top right) and $225$ nodes
(bottom right).

#### Acknowledgments

The authors thank Raphaël Berthier and Francis Bach for helpful exchanges on
the problem of averaging. David Martínez-Rubio was supported in part by
EP/N509711/1 from the EPSRC MPLS division, grant No 2053152. Varun Kanade and
Patrick Rebeschini were supported in part by the Alan Turing Institute under
the EPSRC grant EP/N510129/1. The authors acknolwedge support from the AWS
Cloud Credits for Research program.

## References

  * Anandkumar et al. [2011] Animashree Anandkumar, Nithin Michael, Ao Kevin Tang, and Ananthram Swami.  Distributed algorithms for learning and cognitive medium access with logarithmic regret.  _IEEE Journal on Selected Areas in Communications_ , 29(4):731–745, 2011.
  * Arioli and Scott [2014] Mario Arioli and J Scott.  Chebyshev acceleration of iterative refinement.  _Numerical Algorithms_ , 66(3):591–608, 2014\.
  * Audibert and Bubeck [2009] Jean-Yves Audibert and Sébastien Bubeck.  Minimax policies for adversarial and stochastic bandits.  In _COLT_ , pages 217–226, 2009.
  * Auer et al. [2002] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer.  Finite-time analysis of the multiarmed bandit problem.  _Machine learning_ , 47(2-3):235–256, 2002.
  * Auzinger and Melenk [2011] W Auzinger and J Melenk.  Iterative solution of large linear systems.  _Lecture notes, TU Wien_ , 2011.
  * Awerbuch and Kleinberg [2008] Baruch Awerbuch and Robert Kleinberg.  Competitive collaborative learning.  _Journal of Computer and System Sciences_ , 74(8):1271–1288, 2008.
  * Boyd et al. [2006] Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah.  Randomized gossip algorithms.  _IEEE transactions on information theory_ , 52(6):2508–2530, 2006.
  * Braca et al. [2008] Paolo Braca, Stefano Marano, and Vincenzo Matta.  Enforcing consensus while monitoring the environment in wireless sensor networks.  _IEEE Transactions on Signal Processing_ , 56(7):3375–3380, 2008.
  * Bubeck and Cesa-Bianchi [2012] Sébastien Bubeck and Nicolo Cesa-Bianchi.  Regret analysis of stochastic and nonstochastic multi-armed bandit problems.  _Foundations and Trends® in Machine Learning_ , 5(1):1–122, 2012.
  * Buccapatnam et al. [2013] Swapna Buccapatnam, Atilla Eryilmaz, and Ness B Shroff.  Multi-armed bandits in the presence of side observations in social networks.  In _Decision and Control (CDC), 2013 IEEE 52nd Annual Conference on_ , pages 7309–7314. IEEE, 2013.
  * Cesa-Bianchi et al. [2016] Nicolo Cesa-Bianchi, Claudio Gentile, Yishay Mansour, and Alberto Minora.  Delay and cooperation in nonstochastic bandits.  _Journal of Machine Learning Research_ , 49:605–622, 2016\.
  * Chakraborty et al. [2017] Mithun Chakraborty, Kai Yee Phoebe Chua, Sanmay Das, and Brendan Juba.  Coordinated versus decentralized exploration in multi-agent multi-armed bandits.  In _Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17_ , pages 164–170, 2017.
  * Dimakis et al. [2010] Alexandros G Dimakis, Soummya Kar, José MF Moura, Michael G Rabbat, and Anna Scaglione.  Gossip algorithms for distributed signal processing.  _Proceedings of the IEEE_ , 98(11):1847–1864, 2010.
  * Duchi et al. [2012] John C Duchi, Alekh Agarwal, and Martin J Wainwright.  Dual averaging for distributed optimization: Convergence analysis and network scaling.  _IEEE Transactions on Automatic control_ , 57(3):592–606, 2012.
  * Gai et al. [2010] Yi Gai, Bhaskar Krishnamachari, and Rahul Jain.  Learning multiuser channel allocations in cognitive radio networks: A combinatorial multi-armed bandit formulation.  In _Symposium on New Frontiers in Dynamic Spectrum_ , pages 1–9. IEEE, 2010.
  * Hillel et al. [2013] Eshcar Hillel, Zohar S Karnin, Tomer Koren, Ronny Lempel, and Oren Somekh.  Distributed exploration in multi-armed bandits.  In _Advances in Neural Information Processing Systems_ , pages 854–862, 2013.
  * Horn and Johnson [1990] Roger A Horn and Charles R Johnson.  _Matrix analysis_.  Cambridge university press, 1990.
  * Ireland and Rosen [2013] Kenneth Ireland and Michael Rosen.  _A classical introduction to modern number theory_ , volume 84.  Springer Science & Business Media, 2013.
  * Joulani et al. [2013] Pooria Joulani, Andras Gyorgy, and Csaba Szepesvári.  Online learning under delayed feedback.  In _International Conference on Machine Learning_ , pages 1453–1461, 2013.
  * Kalathil et al. [2014] Dileep Kalathil, Naumaan Nayyar, and Rahul Jain.  Decentralized learning for multiplayer multiarmed bandits.  _IEEE Transactions on Information Theory_ , 60(4):2331–2345, 2014.
  * Kar et al. [2011] Soummya Kar, H Vincent Poor, and Shuguang Cui.  Bandit problems in networks: Asymptotically efficient distributed allocation rules.  In _Decision and Control and European Control Conference (CDC-ECC), 2011 50th IEEE Conference on_ , pages 1771–1778. IEEE, 2011.
  * Korda et al. [2016] Nathan Korda, Balázs Szörényi, and Li Shuai.  Distributed clustering of linear bandits in peer to peer networks.  In _Journal of Machine Learning Research Workshop and Conference Proceedings_ , volume 48, pages 1301–1309. International Machine Learning Societ, 2016.
  * Lai and Robbins [1985] Tze Leung Lai and Herbert Robbins.  Asymptotically efficient adaptive allocation rules.  _Advances in applied mathematics_ , 6(1):4–22, 1985.
  * Landgren et al. [2016a] Peter Landgren, Vaibhav Srivastava, and Naomi Ehrich Leonard.  Distributed cooperative decision-making in multiarmed bandits: frequentist and bayesian algorithms.  In _Decision and Control (CDC), 2016 IEEE 55th Conference on_ , pages 167–172. IEEE, September 2016a.
  * Landgren et al. [2016b] Peter Landgren, Vaibhav Srivastava, and Naomi Ehrich Leonard.  On distributed cooperative decision-making in multiarmed bandits.  In _Control Conference (ECC), 2016 European_ , pages 243–248. IEEE, May 2016b.
  * Liu and Zhao [2010] Keqin Liu and Qing Zhao.  Distributed learning in multi-armed bandit with multiple players.  _IEEE Transactions on Signal Processing_ , 58(11):5667–5681, 2010.
  * Nayyar et al. [2016] Naumaan Nayyar, Dileep Kalathil, and Rahul Jain.  On regret-optimal learning in decentralized multi-player multi-armed bandits.  _IEEE Transactions on Control of Network Systems_ , 2016.
  * Nedic and Ozdaglar [2009] Angelia Nedic and Asuman Ozdaglar.  Distributed subgradient methods for multi-agent optimization.  _IEEE Transactions on Automatic Control_ , 54(1):48–61, 2009.
  * Perchet et al. [2016] Vianney Perchet, Philippe Rigollet, Sylvain Chassang, Erik Snowberg, et al.  Batched bandit problems.  _The Annals of Statistics_ , 44(2):660–681, 2016\.
  * Scaman et al. [2017] Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, and Laurent Massoulié.  Optimal algorithms for smooth and strongly convex distributed optimization in networks.  _arXiv preprint arXiv:1702.08704_ , 2017.
  * Shah et al. [2009] Devavrat Shah et al.  Gossip algorithms.  _Foundations and Trends® in Networking_ , 3(1):1–125, 2009.
  * Shahrampour et al. [2017] Shahin Shahrampour, Alexander Rakhlin, and Ali Jadbabaie.  Multi-armed bandits in multi-agent networks.  In _Acoustics, Speech and Signal Processing (ICASSP), 2017 IEEE International Conference on_ , pages 2786–2790. IEEE, 2017.
  * Stranders et al. [2012] Ruben Stranders, Long Tran-Thanh, Francesco M Delle Fave, Alex Rogers, and Nicholas R Jennings.  Dcops and bandits: Exploration and exploitation in decentralised coordination.  In _Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems-Volume 1_ , pages 289–296. International Foundation for Autonomous Agents and Multiagent Systems, 2012.
  * Szörényi et al. [2013] Balázs Szörényi, Róbert Busa-Fekete, István Hegedűs, Róbert Ormándi, Márk Jelasity, and Balázs Kégl.  Gossip-based distributed stochastic bandit algorithms.  In _Journal of Machine Learning Research Workshop and Conference Proceedings_ , volume 2, pages 1056–1064. International Machine Learning Societ, 2013.
  * Tekin and Liu [2012] Cem Tekin and Mingyan Liu.  Online learning in decentralized multi-user spectrum access with synchronized explorations.  In _Military Communications Conference_ , pages 1–6. IEEE, 2012.
  * Tran-Thanh et al. [2012] Long Tran-Thanh, Alex Rogers, and Nicholas R Jennings.  Long-term information collection with energy harvesting wireless sensors: a multi-armed bandit based approach.  _Autonomous Agents and Multi-Agent Systems_ , 25(2):352–394, 2012.
  * Xiao and Boyd [2004] Lin Xiao and Stephen Boyd.  Fast linear iterations for distributed averaging.  _Systems & Control Letters_, 53(1):65–78, 2004\.
  * Xu et al. [2015] Jie Xu, Cem Tekin, Simpson Zhang, and Mihaela Van Der Schaar.  Distributed multi-agent online learning based on global feedback.  _IEEE Trans. Signal Processing_ , 63(9):2225–2238, 2015.

##  Appendix A Proofs

###  A.1 Proof of Theorem 3.2

The proof is along the lines of the one for the standard UCB algorithm cf. [4]
but requires a couple of key modifications. Firstly, we need to control the
error due to the fact that each agent decides which arm to pull with some
delay, because only information after it is mixed is used. Secondly, we need
to control the error due to the fact that agents only have approximations of
${m}_{t}^{k}$ and ${n}_{t}^{k}$, that is, to the true sum of rewards and
number of times each arm was pulled respectively.

We present two lemmas before the proof. Their proofs can be found in Section
A.2. Note the running consensus operation is linear. The linearity of $P$
allows us to think about each reward as being at each node weighted by a
number. For each reward, since $P$ is a gossip matrix the sum of the weights
across all the nodes is $1$ and the weights approach $1/N$ quickly.

######  Lemma A.1.

Fix an arm $k$, a node $i$, and a time step $t$. Let $Y_{1},\dots,Y_{D}$ be
independent random variables coming from the distribution associated to arm
$k$, which we assume subgaussian with variance proxy $\sigma^{2}$ and mean
$\mu_{k}$. Let $\varepsilon>0$ be arbitrarily small and less than
$\frac{\eta-1}{7(\eta+1)}$, for $\eta>1$, and let $s>1$. Let $w_{j}$ be a
number such that $|w_{j}-\frac{1}{N}|<\varepsilon/N$, where $j=1,\dots,D$.
Then

$\mathbb{P}\left[\frac{\sum w_{j}Y_{j}}{\sum
w_{j}}\geq\mu_{k}+\sqrt{\frac{4\eta\sigma^{2}\ln s}{N\sum w_{j}}}\
\right]\leq\frac{1}{s^{\eta+1}}\ \text{ and }\ \mathbb{P}\left[\frac{\sum
w_{j}Y_{j}}{\sum w_{j}}\leq\mu_{k}-\sqrt{\frac{4\eta\sigma^{2}\ln s}{N\sum
w_{j}}}\ \right]\leq\frac{1}{s^{\eta+1}},$

where the sums go from $j=1$ to $j=D$.

At time $t$ and at node $i$, we want to use the variables ${\alpha}_{i}$ and
$a_{i}$ defined in Section 3 to decide the next arm to pull in that node.
Consider the rewards computed by all the nodes until $C$ steps before the last
time $\alpha_{i}$ and $a_{i}$ were updated. Let $J_{t}^{k}$ be the number of
these rewards that come from arm $k$ and let $X_{j}^{k},1\leq j\leq J_{t}^{k}$
be such rewards. We can see each of the $X_{j}^{k}$ as being at node $i$ at
the beginning of iteration $t$ multiplied by a weight $w_{t,i,j}^{k}$. Every
weight we are considering corresponds to a reward that has been mixing for at
least
$C=\lceil\frac{\ln(2N/\varepsilon)}{\sqrt{2\ln\left\lvert\lambda_{2}\right\rvert^{-1}}}\rceil$
steps. This ensures
$\left|w_{t,i,j}^{k}-\frac{1}{N}\right|<\frac{\varepsilon}{N}$ by Lemma 3.1,
so the previous lemma can be applied to these weights.

Define the empirical mean of arm $k$ at node $i$ and time $t$ as

$\widehat{\mu}_{t,i}^{k}:=\frac{\sum_{j=1}^{J_{t}^{k}}w_{t,j,i}^{k}X_{j}^{k}}{\sum_{j=1}^{J_{t}^{k}}w_{t,j,i}^{k}},$

Let UCB$(t,s,k,i):=\widehat{\mu}_{t,i}^{k}+\sqrt{\frac{4\eta\sigma^{2}\ln
s}{N\sum_{j}w_{t,i,j}^{k}}}$ and let $I_{t,i}$ be the random variable that
represents the arm pulled at time $t$ by node $i$, which is the one that
maximizes UCB$(t,s,k,i)$, for a certain value $s$.

######  Lemma A.2.

Let $k^{\ast}$ and $k$ be an optimal arm and a suboptimal arm respectively. We
have

$\mathbb{P}\Bigg{(}I_{t,i}=k,N\sum_{j}w_{t,i,j}^{k}>\frac{16\eta\sigma^{2}\ln
s}{\Delta_{k}^{2}}\Bigg{)}\leq\frac{2Ns_{t}}{s^{\eta+1}}.$

where $Ns_{t}=\sum_{k=1}^{K}J_{k}^{t}$ is the number of rewards obtained by
all the nodes until $C$ steps before the last time $\alpha_{i}$ and $a_{i}$
were updated.

Now we proceed to prove the theorem.

######  Proof (Theorem 3.2).

For every $t\geq K$ we can write $t$ uniquely as $K+Cq_{t}+r_{t}$, where
$q_{t}\geq 0$ and $0\leq r_{t}<C$. In such a case it is

$s_{t}=K\max\left(\mathds{1}(q_{t}>0),1/N\right)+C(q_{t}-1)\mathds{1}(q_{t}>1),$

where $s_{t}$ is defined in Lemma A.2. The time step $s$ that we use to
compute the upper confidence bounds at time $t$ is $s=Ns_{t}$. It is fixed
every $C$ iterations. For $t\geq K+C$, the value $s_{t}+C$ is equal to the
last time step in which the variables $\alpha_{i}$ and $a_{i}$ were updated.
Thus by definition $J^{k}_{t}=n^{k}_{s_{t}}$. Remember $n_{t,i}^{k}$ is the
number of times arm $k$ is pulled by node $i$ up to time $t$, and
$n_{t}^{k}=\sum_{i=1}^{N}n_{t,i}^{k}$. Since
$R(T)=\sum_{k=1}^{K}\Delta_{k}\mathbb{E}[n_{T}^{k}]$ it is enough to bound
$\mathbb{E}[n_{T}^{k}]$ for every $k=1,\dots,K$.

Let $k$ be fixed and denote $A_{t,i}$ the event $\\{I_{t,i}=k\\}$. We have

$\displaystyle\mathbb{E}[n^{k}_{T}]=N+\mathbb{E}\left[\sum_{i=1}^{N}\sum_{t=K+1}^{T}\mathds{1}(A_{t,i})\right]$
$\displaystyle=N+\mathbb{E}\left[\sum_{i=1}^{N}\sum_{\begin{subarray}{c}t=K+1\end{subarray}}^{T}\mathds{1}\left(A_{t,i},1\leq\frac{16\eta\sigma^{2}\ln(s_{t}N)}{N\sum_{j}w_{t,i,j}^{k}\Delta_{k}^{2}}\right)+\mathds{1}\left(A_{t,i},1>\frac{16\eta\sigma^{2}\ln(s_{t}N)}{N\sum_{j}w_{t,i,j}^{k}\Delta_{k}^{2}}\right)\right]$
$\displaystyle\stackrel{{\scriptstyle\leavevmode\hbox to8.34pt{\vbox
to8.34pt{\pgfpicture\makeatletter\hbox{\hskip 4.17046pt\lower-4.17046pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.97046pt}{0.0pt}\pgfsys@curveto{3.97046pt}{2.19284pt}{2.19284pt}{3.97046pt}{0.0pt}{3.97046pt}\pgfsys@curveto{-2.19284pt}{3.97046pt}{-3.97046pt}{2.19284pt}{-3.97046pt}{0.0pt}\pgfsys@curveto{-3.97046pt}{-2.19284pt}{-2.19284pt}{-3.97046pt}{0.0pt}{-3.97046pt}\pgfsys@curveto{2.19284pt}{-3.97046pt}{3.97046pt}{-2.19284pt}{3.97046pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{{\leq}}N+\mathbb{E}\left[\sum_{i=1}^{N}\sum_{t=K+1}^{T}\mathds{1}\left(A_{t,i},n_{s_{t}}^{k}\leq\frac{16\eta\sigma^{2}\ln(TN)}{\Delta_{k}^{2}/(1+2\varepsilon)}\right)\right]+N\sum_{t=K+1}^{T}\frac{2}{(s_{t}N)^{\eta}}$
$\displaystyle\stackrel{{\scriptstyle\leavevmode\hbox to8.34pt{\vbox
to8.34pt{\pgfpicture\makeatletter\hbox{\hskip 4.17046pt\lower-4.17046pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.97046pt}{0.0pt}\pgfsys@curveto{3.97046pt}{2.19284pt}{2.19284pt}{3.97046pt}{0.0pt}{3.97046pt}\pgfsys@curveto{-2.19284pt}{3.97046pt}{-3.97046pt}{2.19284pt}{-3.97046pt}{0.0pt}\pgfsys@curveto{-3.97046pt}{-2.19284pt}{-2.19284pt}{-3.97046pt}{0.0pt}{-3.97046pt}\pgfsys@curveto{2.19284pt}{-3.97046pt}{3.97046pt}{-2.19284pt}{3.97046pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{{<}}N+\frac{16\eta\sigma^{2}\ln(TN)}{\Delta_{k}^{2}/(1+2\varepsilon)}+2NC+\frac{2NC}{K^{\eta}}\left(1+\frac{1}{N^{\eta}}\right)+\frac{2}{(NC)^{\eta-1}}\sum_{r=\lfloor
K/C\rfloor+1}^{\infty}\frac{1}{r^{\eta}}$
$\displaystyle\stackrel{{\scriptstyle\leavevmode\hbox to8.34pt{\vbox
to8.34pt{\pgfpicture\makeatletter\hbox{\hskip 4.17046pt\lower-4.17046pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.97046pt}{0.0pt}\pgfsys@curveto{3.97046pt}{2.19284pt}{2.19284pt}{3.97046pt}{0.0pt}{3.97046pt}\pgfsys@curveto{-2.19284pt}{3.97046pt}{-3.97046pt}{2.19284pt}{-3.97046pt}{0.0pt}\pgfsys@curveto{-3.97046pt}{-2.19284pt}{-2.19284pt}{-3.97046pt}{0.0pt}{-3.97046pt}\pgfsys@curveto{2.19284pt}{-3.97046pt}{3.97046pt}{-2.19284pt}{3.97046pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{{\lesssim}}\frac{\eta\sigma^{2}\ln(TN)}{\Delta_{k}^{2}/(1+\varepsilon)}+\frac{N\ln(N/\varepsilon)}{\sqrt{\ln(1/\left\lvert\lambda_{2}\right\rvert)}}+\frac{\eta}{\eta-1}.$

For the bound of the first summand in 1 note that
$\left|w_{t,i,j}^{k}-\frac{1}{N}\right|<\varepsilon/N$ and that
$J^{k}_{t}=n_{s_{t}}^{k}$. Thus

$\Big{(}N\sum_{j}w_{t,i,j}^{k}\Big{)}^{-1}\leq\left(n_{s_{t}}^{k}\left(1-\varepsilon\right)\right)^{-1}\leq\left(1+2\varepsilon\right)/n_{s_{t}}^{k}.$

We have used $\varepsilon<1/2$ for the last step, which is a consequence of
$\varepsilon<\frac{\eta-1}{7(\eta+1)}$ for $\eta>1$. The bound for the second
summand uses Lemma A.2. For the bound of the expectation in 2, note that, by
definition, $A_{t,i}$ for $1\leq t\leq T$ can only happen $n_{t}^{k}$ times
but

$n_{t}^{k}\leq n_{s_{t}}^{k}+N(t-s_{t})\leq n_{s_{t}}^{k}+2NC.$

So
$\mathds{1}\left(I_{t,i+1}=k,n_{s_{t}}^{k}<\frac{8\eta\sigma^{2}\ln(TN)}{\Delta_{k}^{2}/(1+2\varepsilon)}\right)$
can be $1$ at most
$\frac{8\eta\sigma^{2}\ln(TN)}{\Delta_{k}^{2}/(1+2\varepsilon)}+2NC$ times.
The term $2NC$ accounts for the delay of the algorithm. In the second part of
inequality 2 we substitute $s_{t}$ by its value and for $t>K+2C$ we bound it
by the greatest multiple of $C$ that is less than $s_{t}$. For 3, note that
the sum over $r$ is bounded by $\zeta(\eta)$, where $\zeta(\cdot)$ is the
Riemann zeta function. Then we use $\zeta(x)<\frac{x}{x-1}$ for all $x>1$, cf.
[18], Proposition 16.1.2. Substituting the value of $C$ and the values
$\eta=2$, $\varepsilon=1/22$ then yields the bound. The finite-time bound
follows by bounding the Riemann zeta function as above and bounding
$1/N^{\eta}$, $1/K^{\eta}$ and $1/(NC)^{\eta-1}$ by $1$.

###  A.2 Other proofs

######  Lemma 3.1.

Let $P$ be a communication matrix with real eigenvalues such that
$\mathds{1}^{\top}P=\mathds{1}^{\top}$, $P\mathds{1}=\mathds{1}$ and whose
second largest eigenvalue in absolute value is $-1<\lambda_{2}<1$. Let $v$ be
in the $N$-dimensional simplex and let
$C=\lceil\ln(2N/\varepsilon)/\sqrt{2\ln(1/|\lambda_{2}|)}\rceil$. Agents can
compute, after $C$ communication steps, a polynomial $q_{C}$ of degree $C$
which satisfies

$\left\|q_{C}(P)v-\mathds{1}/N\right\|_{2}\leq\varepsilon/N.$

######  Proof.

Define the Chebyshev polynomials as $T_{0}(t)=1$, $T_{1}(t)=t$ and
$T_{r}(t)=2tT_{r-1}(t)-T_{r-2}(t)$ for $r>1$. Then, define

$q_{r}(t)=\frac{T_{r}(t/|\lambda_{2}|)}{T_{r}(1/|\lambda_{2}|)}.$

Let $\kappa=\frac{1+|\lambda_{2}|}{1-|\lambda_{2}|}$, and
$C=\left\lceil\frac{\ln(2N/\varepsilon)}{\sqrt{2\ln(1/|\lambda_{2}|)}}\right\rceil$.
Then for any $t\in[-|\lambda_{2}|,|\lambda_{2}|]$ the polynomial $q_{C}$
satisfies:

$q_{C}(t)\stackrel{{\scriptstyle\leavevmode\hbox to8.34pt{\vbox
to8.34pt{\pgfpicture\makeatletter\hbox{\hskip 4.17046pt\lower-4.17046pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.97046pt}{0.0pt}\pgfsys@curveto{3.97046pt}{2.19284pt}{2.19284pt}{3.97046pt}{0.0pt}{3.97046pt}\pgfsys@curveto{-2.19284pt}{3.97046pt}{-3.97046pt}{2.19284pt}{-3.97046pt}{0.0pt}\pgfsys@curveto{-3.97046pt}{-2.19284pt}{-2.19284pt}{-3.97046pt}{0.0pt}{-3.97046pt}\pgfsys@curveto{2.19284pt}{-3.97046pt}{3.97046pt}{-2.19284pt}{3.97046pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{{\leq}}2\frac{\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^{C}}{1+\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^{2C}}<2\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^{C}\stackrel{{\scriptstyle\leavevmode\hbox
to8.34pt{\vbox to8.34pt{\pgfpicture\makeatletter\hbox{\hskip
4.17046pt\lower-4.17046pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.97046pt}{0.0pt}\pgfsys@curveto{3.97046pt}{2.19284pt}{2.19284pt}{3.97046pt}{0.0pt}{3.97046pt}\pgfsys@curveto{-2.19284pt}{3.97046pt}{-3.97046pt}{2.19284pt}{-3.97046pt}{0.0pt}\pgfsys@curveto{-3.97046pt}{-2.19284pt}{-2.19284pt}{-3.97046pt}{0.0pt}{-3.97046pt}\pgfsys@curveto{2.19284pt}{-3.97046pt}{3.97046pt}{-2.19284pt}{3.97046pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{{\leq}}2\text{exp}\left(-\log(2N/\varepsilon)\right)\leq\frac{\varepsilon}{N}.$

See [5] for 1. Inequality 2 is true since
$\left(1+\frac{-2}{\sqrt{(1+x)/(1-x)}+1}\right)^{1/\sqrt{2\ln(1/x)}}\leq
e^{-1}$ for $x\in[0,1)$, because the expression is monotone and the
$\lim_{x\to 1^{-}}$ of it is $e^{-1}$. It is also $q_{C}(1)=1$. This implies
that the absolute value of all the eigenvalues of the matrix $q_{C}(P)$ is
less than $\frac{\varepsilon}{N}$ but for the greatest, which is $1$. The
previous property implies
$\left\|q_{C}(P)-\frac{1}{N}\mathds{1}\mathds{1}^{\top}\right\|_{2}\leq\frac{\varepsilon}{N}$,
see [37]. Alternatively, the latter can be proven easily if
$q_{C}(P)-\frac{1}{N}\mathds{1}\mathds{1}^{\top}$ is diagonalizable and then
the result can be straightforwardly extended to all matrices since the
property is continuous and the set of diagonalizable matrices is dense.
Finally, for $v$ in the $N$-dimensional simplex we have

$\left\|q_{C}(P)v-\mathds{1}/N\right\|_{2}=\left\|q_{C}(P)v-\frac{1}{N}\mathds{1}\mathds{1}^{\top}v\right\|_{2}\leq\left\|q_{C}(P)-\frac{1}{N}\mathds{1}\mathds{1}^{\top}\right\|_{2}\left\|v\right\|_{2}\leq\frac{\varepsilon}{N}$

Note that the polynomial $q_{r}(P)$ can be computed iteratively as

$w_{r+1}q_{r+1}(P)=\frac{2}{|\lambda_{2}|}w_{r}Pq_{r}(P)-w_{r-1}q_{r-1}(P),$
(3)

for $r\geq 1$ where $w_{r}=T_{r}(1/|\lambda_{2}|)$. By the properties of the
Chebyshev polynomial, $w_{r}$ can be computed iteratively as $w_{0}=1$,
$w_{1}=1/|\lambda_{2}|$ and $w_{r+1}=2w_{r}/|\lambda_{2}|-w_{r-1}$ for $r>1$.

Also note that if we have a vector $u\in\mathbb{R}^{N}$ we can slightly modify
the recursion in Equation 3 to compute $q_{C}(P)u$ using the gossip protocol
$C$ times:

$y_{r+1}=\frac{w_{r}}{w_{r+1}}\frac{2}{|\lambda_{2}|}Py_{r}-\frac{w_{r-1}}{w_{r+1}}y_{r-1}$

for $r>1$, where we denote $y_{r}=q_{r}(P)u\in\mathbb{R}^{N}$. In order to
simplify the code we want to allow the computation of $y_{1}$ with the same
recursion. In such a case we can use by convention $w_{-1}=0$, $y_{-1}=0$ but
also we need to set $w_{0}=1/2$ and $y_{0}=u/2$ temporarily during the
computation of $y_{1}$, the first iteration, instead of having $w_{0}=1$ and
$y_{0}=u$. Pseudocode for an iteration of this recursion at node $i$ is
provided in Section 3, in which we have called
$y_{r}^{\prime}=2/|\lambda_{2}|Py_{r}$. The multiplication by $P$ is performed
using the gossip protocol. Agent $i$ only computes the $i$-${th}$ entry of
$y_{r+1}$, namely $y_{r+1,i}$, and only uses her local information and the
entries of $y_{r}$ corresponding to her neighbors.

######  Lemma A.1.

Fix an arm $k$, a node $i$, and a time step $t$. Let $Y_{1},\dots,Y_{D}$ be
independent random variables coming from the distribution associated to arm
$k$, which we assume subgaussian with variance proxy $\sigma^{2}$ and mean
$\mu_{k}$. Let $\varepsilon>0$ be arbitrarily small and less than
$\frac{\eta-1}{7(\eta+1)}$, for $\eta>1$, and let $s>1$. Let $w_{j}$ be a
number such that $|w_{j}-\frac{1}{N}|<\varepsilon/N$, where $j=1,\dots,D$.
Then

$\mathbb{P}\left[\frac{\sum w_{j}Y_{j}}{\sum
w_{j}}\geq\mu_{k}+\sqrt{\frac{4\eta\sigma^{2}\ln s}{N\sum w_{j}}}\
\right]\leq\frac{1}{s^{\eta+1}}\ \text{ and }\ \mathbb{P}\left[\frac{\sum
w_{j}Y_{j}}{\sum w_{j}}\leq\mu_{k}-\sqrt{\frac{4\eta\sigma^{2}\ln s}{N\sum
w_{j}}}\ \right]\leq\frac{1}{s^{\eta+1}},$

where the sums go from $j=1$ to $j=D$.

######  Proof.

Since $Y_{j}$ is subgaussian with variance proxy $\sigma^{2}$ we have that
$w_{j}Y_{j}/(\sum w_{j})$ is subgaussian with variance proxy
$w_{j}^{2}\sigma^{2}/(\sum w_{j})^{2}$. Therefore, using subgaussianity and
the fact that the random variables $Y_{j}$, for $j=1,\dots,D$, are independent
we obtain by Hoeffding’s inequality for subgaussian random variables

$\displaystyle\begin{aligned} \mathbb{P}&\left[\frac{\sum w_{j}Y_{j}}{\sum
w_{j}}\geq\mu_{k}+\sqrt{\frac{4\eta\sigma^{2}\ln s}{N\sum w_{j}}}\
\right]\leq\text{exp}\left(-\frac{(4\eta\sigma^{2}\ln s)/(N\sum
w_{j})}{2\sigma^{2}\sum w_{j}^{2}/(\sum
w_{j})^{2}}\right)=\frac{1}{s^{2\eta/(NW)}}\end{aligned}$

where $W:=\sum w_{j}^{2}/\sum w_{j}$. Using
$\left|w_{j}-\frac{1}{N}\right|<\varepsilon/N$ we obtain

$\eta/(NW)=\eta\left(N\frac{\sum w_{j}^{2}}{\sum
w_{j}}\right)^{-1}\geq\eta\left(N\frac{D((1+\varepsilon)/N)^{2}}{D((1-\varepsilon)/N)}\right)^{-1}=\frac{\eta(1-\varepsilon)}{(1+\varepsilon)^{2}}>\frac{\eta+1}{2}.$

The last step is a consequence of $\varepsilon<\frac{\eta-1}{7(\eta+1)}$. The
first result follows. The second inequality is analogous.

######  Lemma A.2.

Let $k^{\ast}$ and $k$ be an optimal arm and a suboptimal arm respectively. We
have

$\mathbb{P}\left(I_{t,i}=k,N\sum_{j}w_{t,i,j}^{k}>\frac{16\eta\sigma^{2}\ln
s}{\Delta_{k}^{2}}\right)\leq\frac{2s_{t}N}{s^{\eta+1}}.$

where $Ns_{t}=\sum_{k=1}^{K}J_{k}^{t}$ is the number of rewards obtained by
all the nodes until $C$ steps before the last time $\alpha_{i}$ and $a_{i}$
were updated.

######  Proof.

It is enough to bound
$\mathbb{P}\left(UCB(t,s,k^{\ast},i)\leq\mu_{k^{\ast}}\right)$ and
$\mathbb{P}\left(\widehat{\mu}^{k}_{t,i}>\mu_{k}+\sqrt{\frac{4\eta\sigma^{2}\ln
s}{N\sum w_{j}}}\right)$, since if these two events are false we can apply 1
and 3 in the following and obtain $I_{t,i}\neq k$:

$\displaystyle\begin{aligned}
UCB(t,s,k,i)&=\widehat{\mu}_{t,i}^{k}+\sqrt{\frac{4\eta\sigma^{2}\ln
s}{N\sum_{j}w_{t,i,j}^{k}}}\\\ &\stackrel{{\scriptstyle\leavevmode\hbox
to8.34pt{\vbox to8.34pt{\pgfpicture\makeatletter\hbox{\hskip
4.17046pt\lower-4.17046pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.97046pt}{0.0pt}\pgfsys@curveto{3.97046pt}{2.19284pt}{2.19284pt}{3.97046pt}{0.0pt}{3.97046pt}\pgfsys@curveto{-2.19284pt}{3.97046pt}{-3.97046pt}{2.19284pt}{-3.97046pt}{0.0pt}\pgfsys@curveto{-3.97046pt}{-2.19284pt}{-2.19284pt}{-3.97046pt}{0.0pt}{-3.97046pt}\pgfsys@curveto{2.19284pt}{-3.97046pt}{3.97046pt}{-2.19284pt}{3.97046pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{{\leq}}\mu_{k}+2\sqrt{\frac{4\eta\sigma^{2}\ln
s}{N\sum_{j}w_{t,i,j}^{k}}}\\\ &\stackrel{{\scriptstyle\leavevmode\hbox
to8.34pt{\vbox to8.34pt{\pgfpicture\makeatletter\hbox{\hskip
4.17046pt\lower-4.17046pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.97046pt}{0.0pt}\pgfsys@curveto{3.97046pt}{2.19284pt}{2.19284pt}{3.97046pt}{0.0pt}{3.97046pt}\pgfsys@curveto{-2.19284pt}{3.97046pt}{-3.97046pt}{2.19284pt}{-3.97046pt}{0.0pt}\pgfsys@curveto{-3.97046pt}{-2.19284pt}{-2.19284pt}{-3.97046pt}{0.0pt}{-3.97046pt}\pgfsys@curveto{2.19284pt}{-3.97046pt}{3.97046pt}{-2.19284pt}{3.97046pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{{<}}\mu_{k}+\Delta_{k}\\\
&=\mu_{k^{\ast}}\\\ &\stackrel{{\scriptstyle\leavevmode\hbox to8.34pt{\vbox
to8.34pt{\pgfpicture\makeatletter\hbox{\hskip 4.17046pt\lower-4.17046pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.97046pt}{0.0pt}\pgfsys@curveto{3.97046pt}{2.19284pt}{2.19284pt}{3.97046pt}{0.0pt}{3.97046pt}\pgfsys@curveto{-2.19284pt}{3.97046pt}{-3.97046pt}{2.19284pt}{-3.97046pt}{0.0pt}\pgfsys@curveto{-3.97046pt}{-2.19284pt}{-2.19284pt}{-3.97046pt}{0.0pt}{-3.97046pt}\pgfsys@curveto{2.19284pt}{-3.97046pt}{3.97046pt}{-2.19284pt}{3.97046pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{{<}}UCB(t,s,k^{\ast},i).\end{aligned}$

Inequality 2 is true since $N\sum_{j}w_{t,i,j}^{k}>\frac{16\eta\sigma^{2}\ln
s}{\Delta_{k}^{2}}\iff\sqrt{\frac{4\eta\sigma^{2}\ln
s}{N\sum_{j}w_{t,i,j}^{k}}}<\frac{\Delta}{2}$.

Now since $1\leq J_{k}^{t}\leq Ns_{t}$ we have by the union bound and Lemma
A.1

$\displaystyle\begin{aligned}
\mathbb{P}\left(UCB(t,s,k^{\ast},i)\leq\mu_{k^{\ast}}\right)&\leq\mathbb{P}\left(\exists\ell\in\\{1,\dots,Ns_{t}\\}:J_{k}^{t}=\ell,UCB(t,s,k^{\ast},i)\leq\mu_{k^{\ast}}\right)\\\
&\leq\sum_{\ell=1}^{Ns_{t}}\mathbb{P}\left(UCB(t,s,k^{\ast},i)\leq\mu_{k^{\ast}}|J_{k}^{t}=\ell\right)\\\
&\leq\sum_{\ell=1}^{Ns_{t}}\frac{1}{s^{\eta+1}}=\frac{Ns_{t}}{s^{\eta+1}}.\end{aligned}$

The bound of
$\mathbb{P}\left(\widehat{\mu}^{k}_{t,i}>\mu_{k}+\sqrt{\frac{4\eta\sigma^{2}\ln
s}{N\sum w_{j}}}\right)$ is analogous.

######  Theorem A.3 (Instance Independent Regret Analysis of DDUCB).

The regret achieved by the DDUCB algorithm is

$R(T)\lesssim\sqrt{KTN\sigma^{2}\ln(TN)}+K\frac{N\Lambda\ln
N}{\sqrt{\ln(1/\left\lvert\lambda_{2}\right\rvert)}},$

where $\Lambda$ is an upper bound on the gaps $\Delta_{k}$, $k=1,\dots,K$.
Here, $\lesssim$ does not only hide constants but also $\eta$ and
$\varepsilon$.

######  Proof.

Define $D_{1}$ as the set of arms such that their respective gaps are all less
than $\sqrt{\frac{K}{TN}\sigma^{2}\ln(TN)}$ and $D_{2}$ as the set of arms
that are not in $D_{1}$. Then we can bound the regret incurred by pulling arms
in $D_{1}$, in the following way

$\displaystyle\begin{aligned} \sum_{k\in
D_{1}}\mathbb{E}[n_{T}^{k}]\Delta_{k}&\leq\sqrt{\frac{K}{TN}\sigma^{2}\ln(TN)}\sum_{k\in
D_{1}}\mathbb{E}[n_{T}^{k}]\\\ &\leq\sqrt{KTN\sigma^{2}\ln(TN)}\end{aligned}$

Using Theorem 3.2 we can bound the regret obtained by the pulls done to arms
in $D_{2}$:

$\displaystyle\begin{aligned} \sum_{k\in
D_{2}}\mathbb{E}[n_{T}^{k}]\Delta_{k}&\lesssim\sum_{k\in
D_{2}}\frac{\sigma^{2}\ln(TN)}{\Delta_{k}}+\frac{N\ln(N)}{\sqrt{\ln(1/\left\lvert\lambda_{2}\right\rvert)}}\Delta_{k}\\\
&\leq\sum_{k\in
D_{2}}\sqrt{\frac{TN\sigma^{2}\ln(TN)}{K}}+\frac{N\Lambda\ln(N)}{\sqrt{\ln(1/\left\lvert\lambda_{2}\right\rvert)}}\\\
&\leq\sqrt{KTN\sigma^{2}\ln(TN)}+K\frac{N\Lambda\ln(N)}{\sqrt{\ln(1/\left\lvert\lambda_{2}\right\rvert)}}.\end{aligned}$

Adding the two bounds above yields the result.

##  Appendix B Extended Version of Theorem 3.2

######  Theorem 3.2.

Let $P$ be a communication matrix with real eigenvalues such that
$\mathds{1}^{\top}P=\mathds{1}^{\top}$, $P\mathds{1}=\mathds{1}$ whose second
largest eigenvalue measured in absolute value is $\lambda_{2}$, with
$\left\lvert\lambda_{2}\right\rvert<1$. Let $\eta>1$, and let $\varepsilon>0$
be arbitrarily small and less than $\frac{\eta-1}{7(\eta+1)}$. Consider the
distributed multi-armed bandit problem with $N$ nodes, $K$ actions and
subgaussian rewards with variance proxy $\sigma^{2}$. The algorithm DDUCB with
$C=\lceil\frac{\ln(2N/\varepsilon)}{\sqrt{2\ln\left\lvert\lambda_{2}\right\rvert^{-1}}}\rceil$
and upper confidence bound with exploration parameter $\eta$ satisfies

  1. 1.

The finite-time bound on the regret:

$\displaystyle\begin{aligned}
R(T)<\sum_{k:\Delta_{k}>0}\frac{16\eta(1+2\varepsilon)\sigma^{2}\ln(TN)}{\Delta_{k}}+\bigg{(}N(6C+1)+\frac{2\eta}{(\eta-1)}\bigg{)}\sum_{k=1}^{K}\Delta_{k}.\end{aligned}$

  2. 2.

The sharper finite-time bound on the regret:

$\displaystyle\begin{aligned}
R(T)<&\sum_{k:\Delta_{k}>0}\frac{16\eta(1+2\varepsilon)\sigma^{2}\ln(TN)}{\Delta_{k}}\\\
&+\bigg{(}N(2C+1)+\frac{2NC}{K^{\eta}}\left(1+\frac{1}{N^{\eta}}\right)+\frac{2\eta}{(\eta-1)(NC)^{\eta-1}}\bigg{)}\sum_{k=1}^{K}\Delta_{k}.\end{aligned}$

  3. 3.

The corresponding asymptotic bound:

$R(T)\lesssim\sum_{k:\Delta_{k}>0}\frac{\eta(1+\varepsilon)\sigma^{2}\ln(TN)}{\Delta_{k}}+\left(\frac{N\ln(N/\varepsilon)}{\sqrt{\ln(1/\left\lvert\lambda_{2}\right\rvert)}}+\frac{\eta}{\eta-1}\right)\sum_{k=1}^{K}\Delta_{k}.$

  4. 4.

In particular, if we choose the value $\eta=2$ and we choose
$\varepsilon=\frac{1}{22}$ we have the finite-time bound

$R(T)<\sum_{k:\Delta_{k}>0}\frac{32(1+1/11)\sigma^{2}\ln(TN)}{\Delta_{k}}+\bigg{(}N(6C+1)+4\bigg{)}\sum_{k=1}^{K}\Delta_{k}.$

  5. 5.

The corresponding asymptotic bound

$R(T)\lesssim\sum_{k:\Delta_{k}>0}\frac{\sigma^{2}\ln(TN)}{\Delta_{k}}+\frac{N\ln(N)}{\sqrt{\ln(1/\left\lvert\lambda_{2}\right\rvert)}}\sum_{k=1}^{K}\Delta_{k}.$

  6. 6.

With the same choice of $\eta$ and $\varepsilon$, mixing $\beta_{i}$ and
$b_{i}$ in an unaccelerated way (cf. Algorithm 4) with
$C=\lceil\ln(N/\varepsilon)/\ln(1/|\lambda_{2}|)\rceil$ the regret is :

$R(T)\lesssim\sum_{k:\Delta_{k}>0}\frac{\sigma^{2}\ln(TN)}{\Delta_{k}}+\frac{N\ln(N)}{\ln(1/\left\lvert\lambda_{2}\right\rvert)}\sum_{k=1}^{K}\Delta_{k}.$

The proof given in Section A.1 yields all these results straightforwardly. For
Theorem 3.2.6, Equation 2 must be used instead of Lemma 3.1. Note that for the
unaccelerated version of the algorithm the denominator of the second summand
of the regret does not contain a square root. The accelerated version of the
algorithm improves on this by making the dependence of the regret on the
spectral gap much smaller in the regimes in which the spectral gap is small,
that is, when the problem is harder. This is very important for scaling
issues, since the spectral gap decreases with $N$ in many typical topologies.

##  Appendix C Example for the Regret Comparison in Remark 3.4

If we take $P$ to be symmetric, it is
$\sum_{j=1}^{N}\frac{\varepsilon^{j}_{c}}{N}=\sum_{j=2}^{N}\frac{\lambda_{j}^{2}}{1-\lambda_{j}^{2}}$.
Consider the graph $G$ to be a cycle with an odd number of nodes (and greater
than $1$) and take as $P$ the matrix such that $P_{ij}=1/2$ if $i=j\pm 1\mod
N$ and $P_{ij}=0$ otherwise. Then $P$ is a circulant matrix and their
eigenvalues are $\cos\left(2\pi j/N\right)$, $j=0,1,\dots,N-1$. Then
$\frac{\lambda_{2}^{2}}{1-\lambda_{2}^{2}}=\cot^{2}\left(\frac{2\pi}{N}\right)\geq\frac{N^{2}}{4\pi^{2}}-\frac{2}{3}$
and
$\frac{\lambda_{3}^{2}}{1-\lambda_{3}^{2}}=\cot^{2}\left(\frac{4\pi}{N}\right)\geq\frac{N^{2}}{16\pi^{2}}-\frac{2}{3}$.

As a consequence, $B$ is greater than the corresponding summand in Theorem
3.2.3 in our bound by at least a summand which is $\Theta(N^{7/2})$. On the
other hand our summand is $\Theta(N^{2}\log N)$. In addition, $A$ is greater
than the corresponding summand in Theorem 3.2.3 by a factor of
$\Theta(N^{2})$.

The bounds above can be proven by a Taylor expansion:
$x^{2}\cot^{2}\left(\frac{1}{x}\right)=1-\frac{2x^{2}}{3}+\frac{\xi^{4}}{15}$,
for $x>0$ and $\xi\in[0,x]$. So
$\cot^{2}\left(\frac{1}{x}\right)\geq\frac{1}{x^{2}}-\frac{2}{3}$. The bounds
above are the latter for $x=\frac{N}{2\pi}$ and $x=\frac{N}{4\pi}$.

##  Appendix D Case $|\lambda_{2}|<1/e$ in the comparison of the term B in
Remark 3.4

He finish here the case left in the comparison performed in Remark 3.4. As in
the main paper, note that $\frac{\gamma}{\gamma-1}\geq 1$ and
$\frac{1}{1-\left\lvert\lambda_{2}\right\rvert}\geq\frac{1}{\ln(\left\lvert\lambda_{2}\right\rvert^{-1})}$
so we lower bound $B$ for comparison purposes as $B\geq
N\left(1+\frac{\lambda_{2}^{\prime}}{\ln(\sqrt{N}/\lambda_{2}^{\prime})}\right)$,
where
$\lambda_{2}^{\prime}:=\sqrt{N}\left\lvert\lambda_{2}\right\rvert\in[0,\sqrt{N})$.
We use the regret in Theorem 3.2.6 for which, regardless of the value of
$\lambda_{2}$, the second summand of the regret multiplying
$\sum_{k=1}^{K}\Delta_{k}$ is $N\ln
N/\ln({1/\left\lvert\lambda_{2}\right\rvert})\leq 2B$. The inequality is true
since the second line below is holds

$\displaystyle\begin{aligned} 2B&\geq
2N\left(1+\frac{\lambda_{2}^{\prime}}{\ln(\sqrt{N}/\lambda_{2}^{\prime})}\right)\geq\frac{N\ln
N}{\ln(\sqrt{N}/\lambda_{2}^{\prime})}\\\ &\Leftrightarrow\ln
N-2\ln(\lambda_{2}^{\prime})+2\lambda_{2}^{\prime}\geq\ln N.\end{aligned}$

Note that if $|\lambda_{2}|>1/e$, the accelerated version of the algorithm
incurs even lower regret (cf. Theorem 3.2.3). Problems with a lower spectral
gap (i.e. greater $|\lambda_{2}|$) are harder problems since the mixing
process is slower. The accelerated version improves on the harder regime
$|\lambda_{2}|\in[1/e,1)$.

##  Appendix E Variants of DDUCB

Here we present the code used to exemplify variants proposed in Remark 3.5.
Algorithm 3 ensures further mixing by the property
$\left\|P^{s}v-\mathds{1}/N\right\|_{2}\leq\left\lvert\lambda_{2}\right\rvert^{s}$
explained in Equation 2.

Algorithm 3 Unaccelerated communication and mixing step.
unaccel_mix$(x_{i},i)$

1:Send $x_{i}$ to neighbors

2:Receive corresponding values $x_{j},\ \forall j\in\mathcal{N}(i)$

3:return $\sum_{j\in\mathcal{N}(i)}P_{ij}x_{j}$

Algorithm 4 Unaccelerated version of Decentralized Delayed UCB at node $i$.

1:$\zeta_{i}\leftarrow$ $(X_{i}^{1},\dots,X_{i}^{K})$ ;
$z_{i}\leftarrow(1,\dots,1)$

2:$C=\lceil\ln(N/\varepsilon)/\ln(1/|\lambda_{2}|)\rceil$

3:$\alpha_{i}\leftarrow\zeta_{i}/N$ ; $a_{i}\leftarrow z_{i}/N$ ;
$\beta_{i}\leftarrow\zeta_{i}$ ; $b_{i}\leftarrow z_{i}$

4:$\gamma_{i}\leftarrow$ 0 ; $c_{i}\leftarrow$ 0 ; $\delta_{i}\leftarrow$ 0 ;
$d_{i}\leftarrow$ 0

5:$t\leftarrow K$ ; $s\leftarrow K$

6:while $t\leq T$ do

7: $k^{\ast}\leftarrow\operatorname*{arg\,max}_{k\in\\{1,\dots,K\\}}\left\\{\
\frac{\alpha_{i}^{k}}{a_{i}^{k}}+\sqrt{\frac{2\eta\sigma^{2}\ln
s}{Na_{i}^{k}}}\right\\}$

8: for $r\text{ from }0\text{ to }C-1$ do

9: $u\leftarrow$ Play arm $k^{\ast}$, return reward

10: $\gamma_{i}^{k^{\ast}}\leftarrow\gamma_{i}^{k^{\ast}}+u$ ;
$c_{i}^{k^{\ast}}\leftarrow c_{i}^{k^{\ast}}+1$

11: $\beta_{i}\leftarrow$ unaccel_mix$(\beta_{i},r,i)$ ; $b_{i}\leftarrow$
unaccel_mix$(b_{i},r,i)$

12: $t\leftarrow t+1$

13: if $t>T$ then

14: return

15: end if

16: end for

17: $s\leftarrow(t-C)N$

18: $\delta_{i}\leftarrow\delta_{i}+\beta_{i}$ ; $d_{i}\leftarrow d_{i}+b_{i}$
; $\alpha_{i}\leftarrow\delta_{i}$ ; $a_{i}\leftarrow d_{i}$

19: $\beta_{i}\leftarrow\gamma_{i}$ ; $b_{i}\leftarrow c_{i}$ ;
$\gamma_{i}\leftarrow$ 0 ; $c_{i}\leftarrow$ 0

20:end while

Algorithm 5 Accelerated Decentralized Delayed UCB at node $i$ with some
variants.

1:$\zeta_{i}\leftarrow$ $(X_{i}^{1},\dots,X_{i}^{K})$ ;
$z_{i}\leftarrow(1,\dots,1)$

2:$C=\lceil\ln(2N/\varepsilon)/\sqrt{2\ln(1/|\lambda_{2}|)}\rceil$

3:$\alpha_{i}\leftarrow\zeta_{i}/N$ ; $a_{i}\leftarrow z_{i}/N$ ;
$\beta_{i}\leftarrow\zeta_{i}$ ; $b_{i}\leftarrow z_{i}$

4:$\gamma_{i}\leftarrow$ 0 ; $c_{i}\leftarrow$ 0 ; $\delta_{i}\leftarrow$ 0 ;
$d_{i}\leftarrow$ 0

5:$t\leftarrow K$ ; $s\leftarrow K$

6:while $t\leq T$ do

7: for $r\text{ from }0\text{ to }C-1$ do

8: $k^{\ast}\leftarrow\operatorname*{arg\,max}_{k\in\\{1,\dots,K\\}}\left\\{\
\frac{\alpha_{i}^{k}}{a_{i}^{k}}+\sqrt{\frac{2\eta\sigma^{2}\ln
s}{Na_{i}^{k}}}\right\\}$

9: $u\leftarrow$ Play arm $k^{\ast}$, return reward

10: $\gamma_{i}^{k^{\ast}}\leftarrow\gamma_{i}^{k^{\ast}}+u$ ;
$c_{i}^{k^{\ast}}\leftarrow c_{i}^{k^{\ast}}+1$

11: $\beta_{i}\leftarrow$ mix$(\beta_{i},r,i)$ ; $b_{i}\leftarrow$
mix$(b_{i},r,i)$

12: $t\leftarrow t+1$

13: // It also works adding this:

14: // $\alpha_{i}^{k^{\ast}}\leftarrow\alpha_{i}^{k^{\ast}}+u/N$ ;
$a_{i}^{k^{\ast}}\leftarrow a_{i}^{k^{\ast}}+1/N$

15: // $s\leftarrow s+1$

16: // and / or this:

17: // $\delta_{i}\leftarrow$ unaccel_mix$(\delta_{i},i)$ ; $d_{i}\leftarrow$
unaccel_mix$(d_{i},i)$

18: if $t>T$ then

19: return

20: end if

21: end for

22: $s\leftarrow(t-C)N$

23: $\delta_{i}\leftarrow\delta_{i}+\beta_{i}$ ; $d_{i}\leftarrow d_{i}+b_{i}$
; $\alpha_{i}\leftarrow\delta_{i}$ ; $a_{i}\leftarrow d_{i}$

24: $\beta_{i}\leftarrow\gamma_{i}$ ; $b_{i}\leftarrow c_{i}$ ;
$\gamma_{i}\leftarrow$ 0 ; $c_{i}\leftarrow$ 0

25:end while

##  Appendix F Estimation of the number of nodes

The total number of nodes can be estimated at the beginning of the algorithm,
with high probability. Given a value per node, the gossip protocol allows for
the computation at each node of the average of those values. If a node starts
with a number $u\neq 0$ and the rest of the nodes start with the value $0$,
then using the gossip protocol after some iterations makes the nodes hold an
approximation of the value $u/N$. The approximation improves exponentially in
the number of steps (cf. Equation 2, for instance) and does not depend on $N$,
but in the spectral gap. To recover $N$, the value $u$ is broadcast at the
same time the values are being mixed, so at each time step a node receives
from her neighbors the mixing value and $u$. Since we want to run this
procedure in a decentralized way, we cannot tell which node should start with
the value $u$, so we make every node compute a number $u_{i}$ at random and
they start broadcasting and mixing it. However, during the mixing process, we
make each node only keep and mix the value corresponding to the minimum
$u_{i}$ so at the end of this process, each node only contains $u=\min u_{i}$
and the approximate value of $u/N$, if no two nodes started with $\min u_{i}$,
which only occurs with low probability. The procedure can be repeated to
increase the probability of success.

The approximations of $N$ can be broadcast and nodes could use the minimum and
maximum as lower and upper bounds on $N$. The algorithm really only needs
upper and lower bounds on $N$. The delay constant $C$ would be computed with
the upper bound on $N$ and the upper confidence bound would be computed using
the lower bound, which translates to using a greater exploration parameter
$\eta$. Since our analysis was done in general for the delay and the
exploration parameters, the bounds in Theorem 3.2 hold, substituting the delay
and exploration parameters by the new values.

##  Appendix G Experiments

We have observed that the accelerated method performs well with the
recommended values for the exploration parameter $\eta$ and the parameter
$\varepsilon$ that measures the precision of the mixing after a stage. So we
use these recommended values, that are $\eta=2$, $\varepsilon=\frac{1}{22}$.

The distributions of the arms in the bandit problem used in the experiments
are Gaussian with variance $1$. There is one arm with mean $1$ and $16$ other
arms with mean $0.8$. We have executed the algorithms for cycle graphs of size
$100$ and $200$ and for square grids of size $100$ and $225$. We compare
executions of coopUCB [25] using different exploration parameters with $DDUCB$
with the fixed exploration parameter $\eta=2$ and observe that DDUCB
outperforms every execution of coopUCB. Each algorithm for each setting was
executed $10$ times. Average regret is shown in the figures. The experiments
we present are representative of the regret behavior we have observed in a
greater variety of scenarios upon different choices of means, number of arms
and variance. Using different exploration parameters for coopUCB did not make
it show a behavior as effective as the one observed for DDUCB. We tuned
$\gamma$, the exploration parameter of coopUCB, to get best results for that
algorithm and report also $\gamma=2$ for comparison purposes. In the figures
one can observe that after a few stages, DDUCB algorithms learn with high
precision which the best arm is and the regret curve that is observed
afterwards shows an almost horizontal behavior. After $10000$ iterations,
coopUCB not only accumulates a greater regret but the slope indicates that it
still has not learned effectively which the best arm is. The graphs for
coopUCB $\gamma=1.01$ and $\gamma=1.001$ are very similar but the smaller
$\gamma=1.001$ seems to work slightly better.

The constant $C$ for the unaccelerated method is usually excessively large, so
we found it is convenient to heuristically decrease it, or equivalently to use
a different value of $\varepsilon$. Experiments shown below, Figure 2 and
Figure 3, are the same as the plots in the main paper in a bigger format. The
parameter $\varepsilon$ for the unaccelerated method was picked so that the
value of $C$ for is the same for both the unaccelerated and the accelerated
method. We used the recommended modification of DDUCB consisting of adding to
the variables $\alpha_{i}$ and $a_{i}$ the information of the pulls that are
done times $1/N$

The matrix $P$ was chosen according to [14]. That is, we define the graph
Laplacian as $\mathcal{L}=I-D^{-1/2}AD^{-1/2}$, where $A$ is the adjacency
matrix of the communication graph $G$ and $D$ is a diagonal matrix such that
$D_{ii}$ contains the degree of node $i$. Then for regular graphs, if we call
$\delta$ the common degree of every node, we pick
$P=I-\frac{\delta}{\delta+1}\mathcal{L}$. For non regular graphs, like the
square grid we used, letting $\delta_{\max}$ be the maximum degree of the
nodes we pick $P=I-\frac{1}{\delta_{\max}+1}D^{1/2}\mathcal{L}D^{1/2}$. These
matrices always satisfy the assumptions needed on $P$. For reference, for our
choice of $P$, the inverse of the spectral graph of the cycle is $O(N^{2})$
and it is $O(N)$ for the grid [14]. Note that for an expander graph it is
$O(1)$.

Figure 2: Simulation of DDUCB and coopUCB for a cycle graph of $100$ nodes
(left), $200$ nodes (right).

Figure 3: Simulation of DDUCB and coopUCB for a square grid of $100$ nodes
(left) and $225$ nodes (right)

##  Appendix H Notation

$N$ |  Number of agents.
---|---
$T$ |  Number of time steps.
$K$ |  Number of actions.
$P$ |  Communication matrix.
$\lambda_{1},\lambda_{2},\dots,\lambda_{N}$ |  Eigenvalues of $P$ sorted by norm, i.e. $|\lambda_{1}|>|\lambda_{2}|\geq|\lambda_{3}|\geq\cdots\geq|\lambda_{n}|$. It is always $\lambda_{1}=1>|\lambda_{2}|$.
$\mu_{1}\geq\mu_{2}\geq\dots\geq\mu_{K}$ |  Means of arms’ distributions.
$\Delta_{i}$ |  Reward gaps, i.e. $\mu_{1}-\mu_{i}$.
$\alpha_{i}$, $a_{i}$ |  Normalized delayed sum of rewards and number of pulls that are mixed. Normalization accounts for a division by $N$.
$\beta_{i}$, $b_{i}$ |  Sum of rewards and number of pulls done that are being mixed.
$\gamma_{i}$, $c_{i}$ |  Sum of new rewards and new number of pulls.
$\pi_{t}^{k}$ |  Vectors in $\mathbb{R}^{N}$ whose $i$-${th}$ entry is the current reward obtained at time $t$ by node $i$ if arm $k$ was pulled; it is $0$ otherwise.
$p_{t}^{k}$ |  Vector in $\mathbb{R}^{N}$ whose $i$-${th}$ entry is $1$ if arm $k$ was pulled at time $t$ by node $i$, or $0$ otherwise.
$C$ |  Number of steps that define the stages of the algorithm.
$X_{j}^{k}$ |  Reward obtained by pulling arm $k$ for the $j$-${th}$ time. If arm $k$ is played several times in one time step lower indices are assigned to agents with lower indices.
$n_{t,i}^{k}$ |  Number of times arm $k$ is pulled by node $i$ up to time $t$.
$n_{t}^{k}$ |  $\sum_{i=1}^{n}n_{t,i}^{k}$.
$m_{t}^{k}$ |  Sum of rewards coming from all the pulls done to arm $k$ by the entire network up to time $t$.
$I_{t,i}$ |  Action played by agent $i$ at time $t$.
$J^{k}_{t}$ |  Number of rewards that come from arm $k$ that were computed up to $C$ steps before the last time the variables $\alpha_{i}$ and $a_{i}$ were updated if current time is $t$.