# Multi-Agent Multi-Armed Bandits with Limited Communication

Mridul Agarwal, Vaneet Aggarwal, Kamyar Azizzadenesheli The authors are with
Purdue University, West Lafayette IN 47907, USA,
<EMAIL_ADDRESS>
###### Abstract

We consider the problem where $N$ agents collaboratively interact with an
instance of a stochastic $K$ arm bandit problem for $K\gg N$. The agents aim
to simultaneously minimize the cumulative regret over all the agents for a
total of $T$ time steps, the number of communication rounds, and the number of
bits in each communication round. We present Limited Communication
Collaboration - Upper Confidence Bound (LCC-UCB), a doubling-epoch based
algorithm where each agent communicates only after the end of the epoch and
shares the index of the best arm it knows. With our algorithm, LCC-UCB, each
agent enjoys a regret of $\tilde{O}\left(\sqrt{({K/N}+N)T}\right)$,
communicates for $O(\log T)$ steps and broadcasts $O(\log K)$ bits in each
communication step. We extend the work to sparse graphs with maximum degree
$K_{G}$, and diameter $D$ and propose LCC-UCB-GRAPH which enjoys a regret
bound of $\tilde{O}\left(D\sqrt{(K/N+K_{G})DT}\right)$. Finally, we
empirically show that the LCC-UCB and the LCC-UCB-GRAPH algorithm perform well
and outperform strategies that communicate through a central node.

##  I Introduction

We consider a setup where $N$ agents connected over a network, interact with a
multi armed bandit (MAB) environment Lattimore and Szepesvári, (2020). The
agents aim to collaborate with other agents in the network to minimize their
regret. The agents also aim to reduce the number of messages and the size of
messages communicated with others. Consider a case of an e-commerce company
serving its users by recommending its vast number of items through multiple
servers for quick response times. It attempts to learn the user preferences
using a MAB algorithm. If each of the multiple servers run their own
algorithm, they waste the large amount of data which other servers collect.
Or, if they communicate after every recommendation, the communication
complexity becomes high within the servers themselves.

As observed from the example above, communicating after each time step is not
favorable because of the increased communication cost. If $N$ agents
communicate after every round to reduce the regret for $T$ time steps, their
total regret is lower bounded by the regret of a super agent solving the MAB
problem with $NT$ time steps. This bounds the total regret as at least
$\tilde{O}(\sqrt{NKT})$ or a per agent regret of $\tilde{O}(\sqrt{KT/N})$.
Whereas, if the $N$ agents interact with the MAB problem independently,
without any information exchange with other agents, the individual regret
bound is upper bounded by $\tilde{O}(\sqrt{KT})$. We aim to find an algorithm
which can obtain the regret bound of the super agent setup, $i.e.$,
$\tilde{O}(\sqrt{KT/N})$, though with limited communication between the
agents.

We provide an algorithm, Limited Communication Collaboration - UCB, (LCC-UCB),
to minimize the regret. LCC-UCB divides the arms among multiple agents, such
that each agent only interacts with the MAB instance but plays arms only from
a subset of all the arms. The algorithm proceeds in epochs which double in
duration, where the agents use UCB algorithm to find the best arm in their
smaller MAB problem and communicate at the end of each epoch. On receiving the
messages from other agents, each agent updates its set of arms and restarts
its algorithm. We prove the regret of LCC-UCB is upper bounded by
$\tilde{O}\left(\sqrt{\left(K/N+N-1\right)T}\right)$. For $N=1$, the regret of
the LCC-UCB algorithm reduces to the standard regret bounds of
$\tilde{O}(\sqrt{KT})$.

We also consider a general setup where the network of agents may not be
completely connected and the agents may not be able to broadcast knowledge to
all the other agents at once. Under such case, we propose LCC-UCB-GRAPH
algorithm that sub divides epochs into sub-epochs of equal length. The agents
restart their UCB algorithm in each sub phases with the new information
available from their neighbors. We show that the regret bound of this modified
algorithm with divided phases changes to
$\tilde{O}\left(D\sqrt{\left(K/N+K_{G}\right)DT}\right)$, where $K_{G}$ is the
maximum degree of the nodes in the graph. Also, the increased communication
complexity of this algorithm is bounded by $O\left(K_{G}D\log T\right)$
message exchanges per node. The key novelty in both the algorithms is that the
gap between the recommended arms and the optimal arm reduces with epochs.

Finally, we simulate and compare our algorithms with other communication
protocols. We show that the algorithm behaves close to the communication
strategy where the agents share the knowledge at each time step. For the LCC-
UCB-GRAPH algorithm we consider sparse graphs with more than $100$ nodes. We
observe that the LCC-UCB-GRPAH algorithm performs better than the
communication strategy where the agents share local data with all their
neighbors at every time step. Further, the LCC-UCB and the LCC-UCB-GRAPH
algorithms also outperforms the DEMAB algorithm Wang et al., (2020) where
agents communicate for only $O(N\log(NK))$ rounds.

##  II Related Works

Optimal action selection problem dates back to (Thompson,, 1933), and since
then many algorithm have been proposed and studied to solve the MAB problem
ranging from index based policies (Gittins,, 1979), Optimism in the Face of
Uncertainty based UCB algorithm (Auer,, 2002; Auer and Ortner,, 2010; Audibert
and Bubeck,, 2009), to Thompson Sampling algorithm (Agrawal and Goyal,, 2013).
All the algorithms achieve a bound on regret $\tilde{O}(\sqrt{KT})$ and match
the lower bound of $\Omega(\sqrt{KT})$ upto logarithmic factors. Since then,
various generalization and extensions have been proposed to solve various
online learning problems using a bandit framework (Abbasi-Yadkori et al.,,
2011; Li et al.,, 2010; Lattimore et al.,, 2018; Lale et al.,, 2019). However,
all these problems consider a single agent interacting with the environment.

Since the last decade, there has been a thrust in studying distributed agents
solving an instance of MAB problems. Kanade et al., (2012) consider a model
where $N$ agents talk to a central controller at every round. However, they
considered the problem of reducing the communication cost for each agents
connected in a star topology with a controller as the central node which is
unlike our setup where we allow any topology, including central node/agent.
Hillel et al., (2013) consider the problem of reducing communication cost for
stochastic bandits in a setup where every agent can communicate with each
other. Their work also bound the total communication rounds by $O(\log_{2}T)$
using an action elimination based algorithm. However, their agents communicate
the estimates of arm rewards for all the $K$ arms in each message, whereas, we
bound the number of bits required in each message by $O(\log_{2}K)$.
Shahrampour et al., (2017) consider a setup where multiple agents collectively
select an arm at a time step and observe different rewards sampled from
different distribution for each agent.

Other works consider a setup where the agents talk to only one of the other
nodes in a network at any given time step (gossiping style algorithm)
(Landgren et al.,, 2016; Martínez-Rubio et al.,, 2019; Wang et al.,, 2020).
However, they allow their agents to communicate at every time step which is a
different setup, and do not optimize a regret-communication trade-off.
Further, they also send estimates of arm rewards in each message. Sankararaman
et al., (2019); Chawla et al., (2020) also consider a gossip style algorithms.
Similar to us, these works divide the time horizon into epochs of variable
length. Their strategies also divide the arms among the agents and the agents
unicast the knowledge of the best arm they have using $O(\log K)$ bits in each
epoch. However, because of gossip style communication protocols, an agent
becomes aware of the best arm after it has already incurred
$O(\frac{1}{\Delta^{2}})$ regret which translates to a problem independent
bound of $\tilde{O}(T^{2/3})$. We note that we use the same number of
communication as these papers, while achieve better regret bound of
$\tilde{O}(T^{1/2})$. Further, we can convert the proposed broadcast based
communication of our work to a unicast based strategy by sending a message to
each neighbor at one timestep for $N$ timesteps.

Wang et al., (2019); Dubey and Pentland, 2020b ; Dubey and Pentland, 2020a
consider the problem of distributed linear bandits. They considered a fully
connected network for reducing the communication messages and reduce the
average regret for $N$ agents. In contrast, we aim to find bounds on the
regret of each of the $N$ agents for $K$-armed stochastic bandits.

Wang et al., (2019) propose DEMAB algorithm for a distributed bandit setup
where all the nodes communicates with a central node. The setup assumes
knowledge of the time horizon to cleverly obtain a bound on number of
communications messages that is independent of time. The DEMAB algorithm is
based on action elimination that also proceeds in epochs with duration growing
exponentially after an initial period of length $T/(NK)$ where every agent
eliminates arms independently. In each epoch, the algorithm generates new
estimates of arm rewards discarding the old samples. This results in high
constants $O(\sqrt{2^{14}})$ in the regret term. The regret bounds of the
proposed LCC-UCB algorithm only exceeds the regret of DEMAB for
$\log_{2}T>2^{14}/144$. Additionally, the DEMAB algorithm requires a central
coordinating node, which may not always be the case. Lastly, for an unknown
time horizon the number of messages increases back to $O(\log T)$ which is the
same as ours.

The proposed algorithm, LCC-UCB, obtains $\tilde{O}(\sqrt{(N/K)T})$ for each
agent with messages of size $O(\log K)$ with a total of $O(\log T)$ messages,
thus achieving the regret of $\tilde{O}(\sqrt{T})$ Additionally, the proposed
LCC-UCB-GRAPH algorithm works well on sparse graphs with large number of
agents with communication complexity of $O(D\log_{2}T)$.

##  III Problem Formulation

We consider a network of $N$ agents, indexed as $n\in[N]=\\{1,2,\cdots,N\\}$.
Each agent $n\in[N]$ interacts with the same instance of stochastic $K$ armed
bandit over $T$ time steps. An agent $n$, at time $t$, plays an arm
$i_{n}(t)$. The expected reward of arm $i$ is $\mu_{i}$ for all $i\in[K]$. On
playing an arm $i_{n}(t)\in[K]$ at time $t$, the $n$’th agent receives a
reward of $r_{n,t}=\mu_{i_{n}(t)}+\eta_{n,t}$. We assume that $\eta_{n,t}$ is
$1$-sub Gaussian at every time step $t$, i.e., for any $\lambda\in\mathbb{R}$,
we have
$\mathbb{E}[\exp{(\lambda\eta_{n,t})}]\leq\exp{(\lambda^{2}/2)},~{}\forall(n,t)\in[N]\times[T]$.
For our analysis, we assume that $\mu_{1}\geq\mu_{2}\geq\cdots\geq\mu_{K}$.
However, the ordering is unknown to the agents. We also define the gap between
two arms as $\Delta_{i}\coloneqq\mu_{1}-\mu_{i}$. For our analysis we assume
$0\leq\mu_{i}\leq 1\ \forall\ i\in[K]$. For our system model, we assume that
$N\ll K$ as observed in many practical setups. For example, an e-commerce
website will have many more products listed than the number of servers
deployed.

We assume that all the agents can communicate with each other (we later relax
this assumption in Section VI). This implies, whenever an agent broadcasts a
message, all the other $N-1$ agents receive the message. Further, we assume
that each agent only communicates the index of the best arm it knows. This
requires $\lceil\log(K)\rceil$ bits for every message and since there are
$N-1$ other agents to send the message, the total bits required by any agent
is $(N-1)\lceil\log(K)\rceil$ bits in every communication round.

An agent $n$ aims to minimize its cumulative regret over time $T$, $R_{n}(T)$,
defined as:

$\displaystyle R_{n}(T)$
$\displaystyle=T\mu_{1}-\mathbb{E}\left[\sum_{t=1}^{T}\sum_{i=1}^{K}\mu_{i}\bm{1}\\{i_{n}(t)=i\\}\right]$
(1)

Note that minimizing regret $R_{n}(T)$ for all agents $n\in[N]$ also minimizes
the total cumulative regret over the agents as well.

##  IV LCC-UCB Algorithm

We design our algorithm LCC-UCB on the basis of the fact that the regret of
UCB algorithms Auer, (2002); Bubeck et al., (2011); Lattimore and Szepesvári,
(2020) scales as $\tilde{O}(\sqrt{KT})$. We reduce the per step regret by
distributing the $K$ arms among the $N$ agents in growing in length epochs. An
agent $n$ chooses to interact with a potentially smaller set of arms
$\mathcal{S}_{n}$ where
$\mathcal{S}_{n}=\\{\left((n-1)\lceil\frac{K}{N}\rceil\mod
K\right)+1,\cdots,\left((n\lceil\frac{K}{N}\rceil-1)\mod K\right)+1\\}$. For
the first epoch, i.e., $j=0$, each agent starts with possibly sub-optimal
arms, even the worst possible arms. As the algorithm proceeds, in epoch $j\geq
1$, agents broadcast the most played arm by UCB algorithm during epoch $j$ to
all the other agents. Each agent $n\in[N]$ receives $\mathcal{R}_{n,j}$, a set
of arm recommendations from other $N-1$ agents. The agent now runs the UCB
algorithm Bubeck et al., (2011) over the arms in the augmented set
$\mathcal{A}_{n,j}=\mathcal{S}_{n}\cup\mathcal{R}_{n,j}$. At the end of any
epoch, the agent purges any old recommendations it has and starts again with
the new recommendations received after an epoch. This ensures that the number
of arms with any agent does not exceed $K^{\prime}\coloneqq\lceil
K/N\rceil+N-1$. This approach helps to bound the regret of any agent $n\in[N]$
by $\tilde{O}\left(\sqrt{\left(\lceil{K/N}\rceil+N-1\right)T}\right)$.

The LCC-UCB algorithm running at an agent $n\in[{N}]$ is described in
Algorithm 1. The algorithm at agent $n$ receives the set of initial arms
$\mathcal{S}_{n}$, the indices of other agents, and the total horizon $T$. The
agent $n$ maintains a set $\mathcal{R}_{n}$ of the arms received from the
remaining $[N]\setminus\\{n\\}$ agents. For the first epoch
$\mathcal{R}_{n}=\emptyset$ as the agent has not heard anything from the
remaining agents and the augmented set is same as the initial set of arms,
$\mathcal{A}_{n,0}=\mathcal{S}_{n}$. As the algorithm proceeds, it runs the
UCB algorithm (Auer et al.,, 2002; Bubeck et al.,, 2011), described in
Algorithm 2, on the arms in the augmented set $\mathcal{A}_{n,j}$ for epoch
duration $K^{\prime}(K^{\prime}+1)2^{j}$. If at time $t$, remaining time is
not sufficient to run a complete epoch of duration $T_{j}$, it just runs the
UCB algorithm for the remaining horizon $T-t$.

1: $t=0,j=0$

2: $\mathcal{R}_{n,j}=\emptyset$

3: while $t<T$ do

4: Set augmented set $\mathcal{A}_{n,j}=\mathcal{S}_{n}\cup\mathcal{R}_{n,j}$

5: $i^{*}$ =
UCB($\mathcal{A}_{n,j},\min\left(T-t,K^{\prime}(K^{\prime}+1)2^{j}\right)$)

6: $t=t+K^{\prime}(K^{\prime}+1)2^{j}$

7: $j=j+1$

8: Send $i^{*}$ to other $[N]\setminus\\{n\\}$ agents

9: Receive most played arms of $[N]\setminus\\{n\\}$ agents as
$\mathcal{R}_{n,j}$

10: end while

Algorithm 1 LCC-UCB$\left(\mathcal{S}_{n},[N]\setminus\\{n\\},T\right)$

1: $t_{j}=0$

2: $N_{i}(t_{j})=0,\hat{\mu}_{i}=0,B_{i}=\infty,~{}\forall\ i\in\mathcal{A}$

3: for $t_{j}=1,\cdots,T_{j}$ do

4: Obtain reward $r_{t}$ by playing arm $i_{t}$, where
$i_{t_{j}}=\arg\max_{i\in\mathcal{A}}\left\\{\hat{\mu}_{i}+\sqrt{\frac{2\log(t_{j})}{N_{i}(t_{j})}}\right\\}$

5:
$N_{i}(t_{j})=N_{i}(t_{j}-1)+\bm{1}_{\\{i_{t_{j}}=i\\}}~{}\forall~{}i\in\cal
A$

6: Update $\hat{\mu}(i_{t})=\frac{\hat{\mu}_{i}\times
N_{i}(t_{j}-1)+r_{t}}{N_{i}(t_{j})}$

7: end for

8: Return $i^{*}=\arg\max_{i\in\mathcal{A}}N_{i}(T_{j})$

Algorithm 2 UCB$\left(\mathcal{A},T_{j}\right)$

##  V Main Result

We now state the main result for bounding the regret and number of
communications for the proposed LCC-UCB algorithm.

######  Theorem 1.

The regret of any agent $n$ following LCC-UCB algorithm is bounded by

$\displaystyle R_{n}(T)\leq O\left(\sqrt{K^{\prime}T}\log(T)\right),$ (2)

where $K^{\prime}=\lceil K/N\rceil+N-1$.

To prove Theorem 1, we first state the necessary lemmas required for the
construction of the proof. Note that, the LCC-UCB algorithm bounds regret when
agent $1$ recommends an arm $i^{*}$ which is “close” to the best arm ($i=1$)
from its augmented set $\mathcal{A}_{1,j}$ at every epoch, and then, in the
following epoch, every other agent $n$ minimizes the regret with respect to
the their augmented sets $\mathcal{A}_{n,j+1}$ which now contain the arm
$i^{*}$.

Since, the agent runs UCB algorithm (Algorithm 2) which returns the most
played arm for each epoch. We now state and prove the lemma that the most
played arms by the UCB algorithm is “good”, or
$\mu_{i^{*}}\geq\mu_{1}-\tilde{\Delta_{j}}$, with high probability for some
$\tilde{\Delta_{j}}$.

######  Lemma 1.

For any epoch $j$, such that $T_{j}\geq K^{\prime}(K^{\prime}+1)$, instance of
the UCB Algorithm 2 running at agent $1$ returns an arm $i^{*}$ that satisfies
$\mu_{i^{*}}\geq\mu_{i}-\tilde{\Delta}_{j}$, with probability atleast

$\displaystyle 1-K^{\prime}\left(\frac{T_{j}}{K^{\prime}}-1\right)^{-2},$ (3)

for $\tilde{\Delta}_{j}=\sqrt{\frac{16K^{\prime}\log T}{T_{j}}}$.

###### Proof.

We first note that the augmented set at agent $1$ contains the best arm $1$ as
arm index $\left((n-1)\lceil\frac{K}{N}\rceil\mod
K\right)+1\in\mathcal{S}_{n}$. From Algorithm 2 instance that ran at epoch
$j$, $N_{i}(T_{j})$ is the number of times arm $i\in\mathcal{A}_{1,j}$ is
played in epoch $j$. We now prove that the arm
$i_{n,j}^{*}=\arg\max_{i\in\mathcal{A}_{1,j}}N_{i}(T_{j})$ is at most
$\tilde{\Delta}_{j}$ far from the true optimal arm $1$.

For time step $t_{j}$ in epoch $j$, we construct an event where arm $i$ is
selected and the total plays $N_{i}(t_{j}-1)$ of arm $i$ has exceeded some
number $l$ as ${\cal
G}_{t_{j}}(i)=\left\\{\\{i_{t_{j}}=i\\}\cap\\{N_{i}(t_{j}-1)\geq
l_{i}\\}\right\\}$ for $l_{i}=1+\frac{8\log T}{\Delta_{i}^{2}}$ and $t_{j}\geq
K+1$ as each arm is played atleast once. Then, the Theorem 1 of Auer et al.,
(2002) states that the probability of the event ${\cal G}_{t_{j}}(i)$ is upper
bounded by $2t_{j}^{-3}$. Using the probability of the event ${\cal
G}_{t_{j}}(i)$, we can bound the probability of the event that the number of
plays of an arm exceeds $l_{i}$ by using union bound. Specifically we have:

$\displaystyle Pr\left(N_{i}(T_{j})\geq l_{i}\right)$
$\displaystyle\leq\bigcup_{t_{j}=l_{i}}^{T_{j}}Pr\left({\cal
G}_{t_{j}}(i)\right)$ (4)
$\displaystyle\leq\sum_{t_{j}=l_{i}}^{T_{j}}2t_{j}^{-3}$ (5)
$\displaystyle<\sum_{t_{j}=l_{i}}^{\infty}2t_{j}^{-3}$ (6)
$\displaystyle\leq\int_{t_{j}=l_{i}-1}^{\infty}2t_{j}^{-3}=\frac{1}{(l_{i}-1)^{2}}$
(7)

Now, for an arms $i$ such that $\Delta_{i}>\sqrt{\frac{8K^{\prime}\log
T}{T_{j}-K^{\prime}}}\geq\sqrt{\frac{16K^{\prime}\log
T}{T_{j}}}\eqqcolon\tilde{\Delta}_{j}$, we have,

$\displaystyle l_{i}$ $\displaystyle=1+\frac{8\log T}{\Delta_{i}^{2}}$ (8)
$\displaystyle<1+\frac{8\log T}{\tilde{\Delta}_{j}^{2}}$ (9)
$\displaystyle\leq
1+\frac{T_{j}-K^{\prime}}{K^{\prime}}=\frac{T_{j}}{K^{\prime}}.$ (10)

Hence, $N_{i}(T_{j})\leq T_{j}/K^{\prime}-1$ with probability at least
$1-(T_{j}/K-1)^{2}$. Further, taking a union bound over all arms, we obtain
that for any arm $i$, such that $\Delta_{i}\geq\tilde{\Delta}_{j}$,
$N_{i}(T_{j})\leq T_{j}/K^{\prime}$ with probability at least
$1-K^{\prime}(T_{j}/K-1)^{2}$.

After bounding the number of plays of arms $i$, such that
$\mu_{i}\leq\mu_{1}-\tilde{\Delta}_{j}$, with high probability, we show that
the most played arm $i^{*}$ has expected reward
$\mu_{i^{*}}\geq\mu_{1}-\tilde{\Delta}_{j}$. Let
$\mathcal{B}_{1,j}=\\{i\in\mathcal{A}_{1,j}|\mu_{i}<\mu_{i_{n,j}^{*}}-\tilde{\Delta}_{j}\\}$
be the set of “bad” arms in the augmented set of agent $n$ in epoch $j$. We
have:

$\displaystyle\max_{i\in\mathcal{A}_{1,j}\setminus\mathcal{B}_{1,j}}N_{i}(T_{j})$
$\displaystyle\geq\frac{1}{|\mathcal{A}_{1,j}\setminus\mathcal{B}_{1,j}|}\sum_{i\in\mathcal{A}_{1,j}\setminus\mathcal{B}_{1,j}}N_{i}(T_{j})$
(11)
$\displaystyle=\frac{1}{|\mathcal{A}_{1,j}\setminus\mathcal{B}_{1,j}|}\left(T_{j}-\sum_{i\in\mathcal{B}_{1,j}}N_{i}(T_{j})\right)$
(12)
$\displaystyle>\frac{1}{|\mathcal{A}_{1,j}\setminus\mathcal{B}_{1,j}|}\left(T_{j}-\sum_{i\in\mathcal{B}_{1,j}}\left(\frac{T_{j}}{K^{\prime}}\right)\right)$
(13)
$\displaystyle=\frac{1}{|\mathcal{A}_{1,j}\setminus\mathcal{B}_{1,j}|}\left(K^{\prime}\frac{T_{j}}{K^{\prime}}-|\mathcal{B}_{1,j}|\left(\frac{T_{j}}{K^{\prime}}\right)\right)$
(14)
$\displaystyle=\frac{1}{|\mathcal{A}_{1,j}\setminus\mathcal{B}_{1,j}|}\left(K^{\prime}-|\mathcal{B}_{1,j}|\right)\frac{T_{j}}{K}$
(15)
$\displaystyle=\frac{1}{|\mathcal{A}_{1,j}\setminus\mathcal{B}_{1,j}|}|\mathcal{A}_{1,j}\setminus\mathcal{B}_{1,j}|\frac{T_{j}}{K}=\frac{T_{j}}{K}$
(16)

This proves that the most played arm in $\mathcal{A}_{1,j}$, $i_{n,j}^{*}$, is
at most $\tilde{\Delta}_{j}$ far from the optimal arm $1$. ∎

After showing that the agent $1$ returns a good arm after each epoch, we now
show that the regret of all the other agents is bounded in the following epoch
$j+1$. Lemma 2 bounds the regret of an agent $n$ running UCB Algorithm 2
during an epoch $j$. We then sum over all the epochs to obtain the total
regret of the algorithm. We focus our analysis on an agent $n$. The analysis
of the remaining agents follows identically.

######  Lemma 2 (UCB regret bound).

The regret of any agent $n$ running UCB algorithm described in Algorithm 2 for
an epoch $j\geq 2$ with $T_{j}$ time steps is upper bounded by

$\displaystyle R(T_{j})$ $\displaystyle\leq 6\sqrt{2K^{\prime}T_{j}\log
T}+\frac{16K^{\prime 3}}{T_{j}}+2K^{\prime}$ (17)

###### Proof.

We first consider the case of an agent $n\neq 1$. The agent receives
recommendations from all the other $N-1$ agents including the agent $1$ and
hence contains the arm $i^{*}$ recommended by the agent $1$.

To analyze the regret, we first create some events that will help in analysis.
The first event denotes the case where the agent $1$, after the end of epoch
$j-1$, recommends arm $i^{*}$ such that
$\mu_{i^{*}}\geq\mu_{1}-\tilde{\Delta}_{j-1}$. We denote this event as
$\tilde{\cal G}_{1}$. Further note that $N_{i}(T_{j})$ is the number of times
agent plays arm $i\in\mathcal{A}_{n,j}$ in epoch $j$. We note that when the
event $\tilde{\mathcal{G}}_{1}$ occurs
$\Delta_{i^{*}}\leq\tilde{\Delta}_{j-1}$. We assume that $i^{*}$ satisfies
$\mu_{i^{*}}=\max_{i\in\mathcal{A}_{n,j}}\mu_{i}$. In case the assumption is
not valid, we redefine $i^{*}$ as
$i^{*}=\arg\max_{i\in\mathcal{A}_{n,j}}\mu_{i}$, and we still have
$\mu_{1}-\mu_{i^{*}}\leq\tilde{\Delta}_{j}$. Also, for the simplicity of
notation, we define $\Delta_{i^{*},i}=\mu_{i^{*}}-\mu_{i}$. Then, using the
regret decomposition lemma (Lemma 4.5) from Lattimore and Szepesvári, (2020),
the regret of the UCB algorithm for epoch $j$ is upper bounded as:

$\displaystyle R(T_{j})$
$\displaystyle=\sum_{i\in\mathcal{A}_{n,j}}\mathbb{E}\left[\Delta_{i}N_{i}(T_{j})\right]$
(18)
$\displaystyle=\sum_{i\in\mathcal{A}_{n,j}}\mathbb{E}\left[(\mu_{1}-\mu_{i})N_{i}(T_{j})\right]$
(19)
$\displaystyle=\sum_{i\in\mathcal{A}_{n,j}}\mathbb{E}\left[(\mu_{1}-\mu_{i^{*}}+\mu_{i^{*}}-\mu_{i})N_{i}(T_{j})\right]$
(20)
$\displaystyle=\sum_{i\in\mathcal{A}_{n,j}}\mathbb{E}\left[(\Delta_{i^{*}}+\Delta_{i^{*},i})N_{i}(T_{j})\right]$
(21)
$\displaystyle=\sum_{i\in\mathcal{A}_{n,j}}\mathbb{E}\left[\Delta_{i^{*}}N_{i}(T_{j})\right]+\sum_{i\in\mathcal{A}_{n,j}}\mathbb{E}\left[(\Delta_{i^{*},i})N_{i}(T_{j})\right]$
(22)
$\displaystyle=\sum_{i\in\mathcal{A}_{n,j}}\mathbb{E}\left[\Delta_{i^{*}}N_{i}(T_{j})|\tilde{\mathcal{G}}_{1}\right]Pr(\tilde{\mathcal{G}}_{1})+\sum_{i\in\mathcal{A}_{n,j}}\mathbb{E}\left[\Delta_{i^{*}}N_{i}(T_{j})|\tilde{\mathcal{G}}_{1}^{c}\right]Pr(\tilde{\mathcal{G}}_{1}^{c})+\sum_{i\in\mathcal{A}_{n,j}}\mathbb{E}\left[(\Delta_{i^{*},i})N_{i}(T_{j})\right]$
(23)
$\displaystyle\leq\sum_{i\in\mathcal{A}_{n,j}}\tilde{\Delta}_{j-1}\mathbb{E}\left[N_{i}(T_{j})|\tilde{\mathcal{G}}_{1}\right]Pr(\tilde{\mathcal{G}}_{1})+\sum_{i\in\mathcal{A}_{n,j}}\mathbb{E}\left[N_{i}(T_{j})|\tilde{\mathcal{G}}_{1}^{c}\right]Pr(\tilde{\mathcal{G}}_{1}^{c})+\sum_{i\in\mathcal{A}_{n,j}}\mathbb{E}\left[(\Delta_{i^{*},i})N_{i}(T_{j})\right]$
(24)
$\displaystyle\leq\tilde{\Delta}_{j-1}\mathbb{E}\left[\sum_{i\in\mathcal{A}_{n,j}}N_{i}(T_{j})|\tilde{\mathcal{G}}_{1}\right]+Pr(\tilde{\mathcal{G}}_{1}^{c})\mathbb{E}\left[\sum_{i\in\mathcal{A}_{n,j}}N_{i}(T_{j})|\tilde{\mathcal{G}}_{1}^{c}\right]+\sum_{i\in\mathcal{A}_{n,j}}\mathbb{E}\left[(\Delta_{i^{*},i})N_{i}(T_{j})\right]$
(25)
$\displaystyle\leq\tilde{\Delta}_{j-1}T_{j}+K^{\prime}\left(\frac{K^{\prime}}{T_{j-1}-K^{\prime}}\right)^{2}T_{j}+\sum_{i\in\mathcal{A}_{n,j}}\mathbb{E}\left[(\Delta_{i^{*},i})N_{i}(T_{j})\right]$
(26) $\displaystyle\leq 4\sqrt{\frac{K^{\prime}\log
T}{T_{j-1}}}T_{j}+K^{\prime}\left(\frac{2K^{\prime}}{T_{j-1}}\right)^{2}T_{j}+\sum_{i\in\mathcal{A}_{n,j}}\mathbb{E}\left[(\Delta_{i^{*},i})N_{i}(T_{j})\right]$
(27) $\displaystyle\leq 4\sqrt{2K^{\prime}T_{j}\log T}+\frac{16K^{\prime
3}}{T_{j}}+\sum_{i\in\mathcal{A}_{n,j}}\mathbb{E}\left[(\Delta_{i*,i})N_{i}(T_{j})\right]$
(28)

We now focus on the last term. We define event where the UCB algorithm plays
arm $i$ after the number of plays of an arm $i$ is has crossed $l_{i}$, or

$\displaystyle{\cal
G}_{n,i}(t_{j})=\left\\{\\{i_{t}=i\\}\cap\\{N_{i}(t_{j}-1)\geq
l_{i}\\}\right\\}\text{, where }l_{i}=\frac{1}{\Delta_{i^{*},i}},$ (29)

Again, similar to Lemma 1, we use the Theorem 1 of Auer et al., (2002) to
upper bound the probability of the event ${\cal G}_{t_{j}}(i)$ by
$2t_{j}^{-3}$. Then we can bound the last term in Equation 28 as:

$\displaystyle\sum_{i\in\mathcal{A}_{n,j}}\mathbb{E}\left[(\Delta_{i*,i})N_{i}(T_{j})\right]$
$\displaystyle\leq\sum_{i\in\mathcal{A}_{n,j}}\Delta_{i*,i}l_{i}+\sum_{i\in\mathcal{A}_{n,j}}\sum_{t_{j}=l_{i}}^{T_{j}}Pr\left({\cal
G}_{n,i}(t_{j})\right)$ (30)
$\displaystyle\leq\sum_{i\in\mathcal{A}_{n.j}}\Delta_{i^{*},i}\left(1+\frac{8\log
T}{\Delta_{i^{*},i}^{2}}\right)+\sum_{i\in\mathcal{A}_{n.j}}\sum_{t_{j}=1}^{T_{j}}t_{j}^{-2}$
(31) $\displaystyle\leq\sum_{i\in\mathcal{A}_{n.j}}\frac{8\log
T}{\Delta_{i^{*},i}}+K^{\prime}+\frac{K^{\prime}\pi}{6}$ (32)
$\displaystyle\leq\sqrt{8K^{\prime}T_{j}\log
T}+K^{\prime}+\frac{K^{\prime}\pi}{6}$ (33)

Replacing the value in Equation 28, we get the required result for $n\neq 1$.

Further, note that for $n=1$, the true optimal arm $1$ is always present in
$\mathcal{A}_{1,j}$ for all $j\geq 1$. ∎

We are now ready to prove Theorem 1. We first note that for epoch $j=0$, not
agents have yet communicated, and hence the regret of any agent is trivially
bounded by $T_{0}=K^{\prime}(K^{\prime}+1)$. For the later epochs, we sum over
the regret incurred in each epoch using Lemma 2. To do so, we first bound the
total number of epochs. Let the total number of epochs be $J$, then noting
that the total number of time steps is $T$, we get:

$\displaystyle T\leq\sum_{j=0}^{J-1}K^{\prime}(K^{\prime}+1)2^{j}<2T$
$\displaystyle\implies$ $\displaystyle
2^{J}-1<\frac{2T}{K^{\prime}(K^{\prime}+1)}$ $\displaystyle\implies$
$\displaystyle J<\log_{2}\left(\frac{T}{K^{\prime}(K^{\prime}+1)}+1\right)$
$\displaystyle\implies$ $\displaystyle
J=\lfloor\log_{2}\left(\frac{T}{K^{\prime}(K^{\prime}+1)}+1\right)\rfloor$

After bounding the regret in each epoch $R(T_{j})$ and bounding the total
number of epochs, we can bound the total regret as,

$\displaystyle R_{n}(T)$ $\displaystyle=\sum_{j=0}^{J-1}R(T_{j})$ (34)
$\displaystyle\leq 6\sum_{j=1}^{J-1}\sqrt{2K^{\prime}T_{j}\log
T}+\sum_{j=1}^{J-1}\frac{16K^{\prime
3}}{T_{j}}+2K^{\prime}\log_{2}(2T+1)+K^{\prime}(K^{\prime}+1)$ (35)
$\displaystyle\leq 6\sqrt{J\sum_{j=1}^{J-1}2K^{\prime}T_{j}\log
T}+16K^{\prime}+2K^{\prime}\log_{2}(2T+1)+K^{\prime}(K^{\prime}+1)$ (36)
$\displaystyle\leq 6\sqrt{2K^{\prime}\log_{2}(2T+1)\log
T(2T)}+16K^{\prime}+2K^{\prime}\log_{2}(2T+1)+K^{\prime}(K^{\prime}+1)$ (37)
$\displaystyle\leq 12\sqrt{K^{\prime}T(\log_{2}(2T+1))\log
T}+16K^{\prime}+2K^{\prime}\log_{2}(2T+1)+K^{\prime}(K^{\prime}+1),$ (38)

where Equation (36) follows from the Cauchy Schwarz inequality.

######  Theorem 2.

For LCC-UCB algorithm, total number of bits exchanged by an agent is bounded
by $O\left(N\log(K)\log(T)\right)$.

###### Proof.

An agent sends or receives only arm index, which requires $\log_{2}(K)$ bits.
In each epoch, the agents communicates with $N-1$ agents and sends and
receives $2(N-1)\log_{2}(K)$ bits. Finally, there are $\log_{2}(T)$ epochs.
This bounds the total number of bits as $O\left(K\log(K)\log(T)\right)$. ∎

We note that the algorithm proposed by Sankararaman et al., (2019) also
divides the time horizon into epochs with $K$ arms divided among $N$ agents.
However, they consider the first few epochs to be of fixed length where agents
only explore to find the best arm within themselves. Our algorithm runs UCB
from the very first epoch. Also, the length of the first epoch is $o(1)$ in
LCC-UCB algorithm which limits the regret. These novel changes allow for a
significantly improved regret bound as compared to the state of the art with
limited communications.

##  VI Extension to general network structures

So far we assumed that all the nodes are connected to each and every other
node. However, this might not always be true. We now assume a general
structure where a graph $G=(V,E)$ that has the different agents as vertices
and the connections as edges represents the network structure. We assume that
the graph representing the network is sparsely connected with a small diameter
and degree for example Erdős-Rényi graphs Chung and Lu, (2001). We assume that
the maximum degree of $G$ is $K_{G}$ and the diameter of $G$ is $D$.

For this setup, we assume that an agent or node can communicate with only its
neighbors. Under this assumption, it may take multiple epochs for the
knowledge of the best arm to reach an agent that may not have the best arm to
begin with. Further, the number of epochs where an agent does not hear from
the agent that has the best arm is bounded by the diameter $D$. Also, the
maximum size of $\mathcal{G}_{n}$ is now upper bounded by
$\lceil\frac{K}{N}\rceil+K_{G}$ instead of $\lceil\frac{K}{N}\rceil+N-1$.

We first start with a direct extension of the result in Theorem 1, and by
understanding the issues in the direct extension, will propose an algorithm to
improve the results for general networks. The following result gives a
corollary for Theorem 1 for general graphs.

######  Corollary 1.

For graph $G=(V,E)$ with agents as nodes $V$, LCC-UCB algorithm results in a
regret bound of:

$\displaystyle R_{n}(T)\leq\tilde{\mathcal{O}}\left(2^{D}K^{\prime
2}+\sqrt{D(2^{D})K^{\prime}T}\right)$ (39)

where $D$ is the diameter of the graph $G$,
$K^{\prime}=\left(\Big{\lceil}\frac{K}{N}\Big{\rceil}+K_{G}\right)$ and
$K_{G}$ is the maximum degree of any node in the graph $G$.

###### Proof.

An agent $n\neq 1$ receives arm recommendations only from its neighboring
nodes which results in reduction of $K^{\prime}$ from $\lceil K/N\rceil+N$ to
$\lceil K/N\rceil+K_{G}$. However, this also implies that the $n\neq 1$ does
not obtains information about a good arm from the agent $1$ directly. Note
that applying Lemma 1 on UCB algorithm ran by agent $n\neq 1$ suggests that
the agent recommends an arm $i_{n}^{*}$ such that
$\mu_{i_{n}^{*}}\geq\mu_{i^{*}}-\tilde{\Delta}_{j}$ where
$i^{*}=\arg\max_{i\in\mathcal{A}_{n,j}}\mu_{i}$. This implies that the agent
(or node) located farthest from the agent $1$ receives knowledge about a good
arm, (1) only after $D$ epochs for the very first time, and (2) the best arm
in the received $i^{*}=\arg\max_{i\in\mathcal{R}_{n,j}}\mu_{i}$ set $i^{*}$
satisfies $\mu_{i}^{*}\geq\mu_{1}-\sum_{j=1}^{D}\tilde{\Delta}_{j-1}$.

This results in an additional constant regret during the first $D$ epochs as:

$\displaystyle\sum_{j=0}^{D-1}T_{j}=\sum_{j=0}^{D-1}(K^{\prime}+1)K^{\prime}2^{j}=(K^{\prime}+1)K^{\prime}(2^{D}-1)$
(40)

Further, the gap incurred from receiving a bad recommendation in each epoch
scales as:

$\displaystyle(\mu_{1}-\mu_{i^{*}})T_{j}$
$\displaystyle\leq\sum_{j^{\prime}=1}^{D}\tilde{\Delta}_{j^{\prime}-1}T_{j}=\sum_{j^{\prime}=1}^{D}4\sqrt{\frac{K^{\prime}\log
T}{T_{j^{\prime}-1}}}T_{j}$ (41)
$\displaystyle=\sum_{j^{\prime}=1}^{D}4\sqrt{K^{\prime}2^{j^{\prime}}T_{j}\log
T}$ (42)
$\displaystyle=4\sqrt{D\sum_{j^{\prime}=1}^{D}K^{\prime}2^{j^{\prime}}T_{j}\log
T}$ (43) $\displaystyle=4\sqrt{DK^{\prime}2(2^{D}-1)T_{j}\log T}$ (44)

∎

######  Remark 1.

Note that for $D=1$ and $K_{G}=N-1$, or the case for a completely connected
graph, the result of Theorem 1 is obtained.

To avoid the exponential blow-up of $2^{D}$ in the regret, we first consider a
strategy where an agent forwards the messages from one neighbor to all the
other neighbor. However, this increases the message size from
$O(K_{G}\log_{2}K)$ bits to $O(N\log_{2}K)$ bits. Further, additional
complexity is added to reduce repeated propagation of messages. In order to
avoid the potential exponential increase in regret or increase in the message
size and the communication complexity, we propose a modification of the LCC-
UCB algorithm as LCC-UCB-GRAPH algorithm. The proposed LCC-UCB-GRAPH algorithm
is described in Algorithm 3.

1: $t=0,j=0$

2: $\mathcal{R}_{n,1,0}=\emptyset$

3: for $t<T$ do

4: $d=1$

5: for $d\leq D$ do

6: Set augmented set
$\mathcal{A}_{n,d,j}=\mathcal{S}_{n}\cup\mathcal{R}_{n,d,j}$

7: $i^{*}$ =
UCB($\mathcal{A}_{n,d,j},\min(T-t,K^{\prime}(K^{\prime}+1)2^{j})$)

8: $t=t+K^{\prime}(K^{\prime}+1)2^{j}$

9: Send $i^{*}$ to neighbors

10: Receive most played arms of neighbors as $\mathcal{R}_{n,d,j}$

11: $d=d+1$

12: end for

13: $j=j+1$

14: end for

Algorithm 3 LCC-UCB-GRAPH$\left(\mathcal{S}_{n},G,T_{0},T\right)$

The LCC-UCB-GRAPH algorithm further divides an epoch $j$ into $D$ sub-epochs
indexed as $d$. The duration of each sub-epoch in epoch $j$ is
$T_{j}=K^{\prime}(K^{\prime}+1)2^{j}$. Now, the LCC-UCB-GRAPH algorithm
restarts UCB algorithm for sub epochs (Line 6-12). Additionally, the agents
now communicate after every sub-epoch, but, only with their neighbors. This
gives the $K^{\prime}\leq\lceil\frac{K}{N}\rceil+K_{G}$.

Note that results from sub-epoch $d$ of epoch $j$ are propagated throughout
the graph by the time sub-epoch $d$ starts in epoch $j+1$. Hence, for
$\tilde{\Delta}_{j}\coloneqq\sqrt{\frac{16K^{\prime}\log(T)}{T_{j}}}$, this
approach allows to propagate arms with $\Delta_{i}\leq D\tilde{\Delta}_{j-1}$
instead of $\sum_{j^{\prime}=j-D}^{j}\tilde{\Delta}_{j^{\prime}}$. Based on
this modification, we can bound the regret of LCC-UCB-GRAPH algorithm and the
number of bits required for communications by LCC-UCB-GRAPH algorithm.

######  Theorem 3.

Let $G=(V,E)$ be the graph representing the network structure of agents
$n\in[N]$, and let $D$ be the diameter of the graph $G$ and let $K_{G}$ be the
maximum degree of the vertices of the graph $G$. Then, the regret of any agent
$n$ following LCC-UCB-GRAPH algorithm is bounded by

$\displaystyle R_{n}(T)\leq\tilde{O}\left(D\sqrt{DK^{\prime}T}\right),$ (45)

where $K^{\prime}=\lceil\frac{K}{N}\rceil+K_{G}$.

###### Proof.

Note that at the beginning of the phase of a sub-epoch $d$ in epoch $j$, the
information from the farthest node $D$ edges away is also received for epoch
$j-1$ sub-epoch $d$. This is because exactly $D$ communications happens
between sub-epoch, epoch pair $d,j-1$ and $d,j$. Further, each intermediate
$D$ nodes drifts from the optimal arm found in sub-epoch, epoch $d,j-1$ by at
most $\tilde{\Delta}_{j-1}$. This suggest that instead of receiving an arm
with $\Delta_{i}\leq\tilde{\Delta}_{j-1}$, the node actually receives an arm
$i^{*}=\arg\max_{i\in\mathcal{A}_{n,d,j}}\mu_{i}$ with $\Delta_{i^{*}}\leq
D\tilde{\Delta}_{j-1}$. Hence, extending Lemma 2 with $D$ hops, the regret
$R(d,j)$ in each sub-epoch $d$ and epoch $j$ is now upper bounded as

$\displaystyle R(d,j)$ $\displaystyle\leq 2(2D+1)\sqrt{2K^{\prime}T_{j}\log
T}+\frac{16DK^{\prime 3}}{T_{j}}+2K^{\prime}$ (46)

In Equation (46), the extra factors of $D$ comes from the fact that now each
of the agents in $D$ hops recommends an arm $i$ such that
$\mu_{i_{d}^{*}}\geq\mu_{i_{d-1}^{*}}-\tilde{\Delta}_{j}$ for all $d\geq 1$
and $i_{0}^{*}=1$, the true best arm. Note that the duration of any sub-epoch
$d$ is $K^{\prime}(K^{\prime}+1)2^{j}$ and it depends only on the epoch $j$.
Hence, the regret $R(d,j)$ is only a function of epoch count $j$.

The total regret of the agent $n$, which is the sum of regrets over all sub-
epochs in every epoch, can now be bounded as:

$\displaystyle R_{n}(T)$ $\displaystyle=\sum_{j=0}^{J-1}\sum_{d=1}^{D}R(d,j)$
$\displaystyle=\sum_{j=1}^{J-1}\sum_{d=1}^{D}R(d,j)+\sum_{d=1}^{D}R(d,0)$
$\displaystyle=\sum_{j=1}^{J-1}\sum_{d=1}^{D}\Big{(}2(2D+1)\sqrt{2K^{\prime}T_{j}\log
T}$ $\displaystyle~{}~{}~{}+\frac{16DK^{\prime
3}}{T_{j}}+2K^{\prime}\Big{)}+\sum_{d=1}^{D}K^{\prime}(K^{\prime}+1)$ (47)
$\displaystyle=2(2D+1)\sqrt{DJ\sum_{d=1}^{D}\sum_{j=0}^{J-1}2K^{\prime}T_{j}\log
T}$ $\displaystyle~{}~{}~{}+DJ\frac{16DK^{\prime
3}}{T_{j}}+2DJK^{\prime}+DK^{\prime}(K^{\prime}+1)$
$\displaystyle=4(2D+1)\sqrt{K^{\prime}DT(\log_{2}(2T+1))\log T}$
$\displaystyle~{}~{}~{}+16D^{2}K^{\prime}+2K^{\prime}D\log_{2}(2T+1)+DK^{\prime}(K^{\prime}+1)$

∎

The key novelty of LCC-UCB-GRAPH algorithm is to let sub-epochs $0\leq d<D$
collect the messages from the entire graph. The equal length of each sub-epoch
avoids the exponential blow-up in the regret. Further, the exponential length
of each epoch $j$ still keeps the total messages in logarithmic order of $T$.

######  Theorem 4.

For LCC-UCBGRAPH algorithm, total number of bits exchanged by an agent is
bounded by $O\left(K_{G}D\log(K)\log(T)\right)$.

###### Proof.

An agent sends or receives only arm index, which requires $\log_{2}(K)$ bits.
The agent communicates at the end of every sub-epoch of every epoch. In each
communications, the agents talks to at most $K_{G}$ neighbors and sends and
receives $2K_{G}\log_{2}(K)$ bits. Finally, there are $D$ sub-epochs in every
$\log_{2}(T)$ epochs. This bounds the total number of bits as
$O\left(DK_{G}\log(K)\log(T)\right)$. ∎

Results from Theorem 3 and Theorem 4 suggest that it is possible to reduce the
regret from an exponential order of the diameter $D$ of the graph $G$ at the
expense of $D$ times more communication rounds. Further, since each
communication involves only exchange of arm indices, the cost of
communications is not high ($O(K_{G}\log_{2}K)$ bits) for power constrained
devices such as sensor networks.

(a) $(N,K)=(10,100)$

(b) $(N,K)=(20,100)$

(c) $(N,K)=(10,200)$

Figure 1: Per-step cumulative regret for a single agent under various
communication strategies.

(a) $(N,K)=(10,100)$

(b) $(N,K)=(20,100)$

(c) $(N,K)=(10,200)$

Figure 2: Per-step cumulative regret for a single agent under various
communication strategies. (Excluding plots from DEMAB algorithm to the regret
growth of other algorithms)

(a) $(N,K)=(100,250)$

(b) $(N,K)=(150,250)$

(c) $(N,K)=(100,500)$

Figure 3: Per-step cumulative regret for a single agent, in a sparse graph,
under various communication strategies.

##  VII Evaluations

We consider various problem setups to evaluate our algorithms. We compare with
the setting where agents can communicate with their neighbors every time and
with the setting where agents do not communicate with anyone for the entire
time horizon. We also compare with the DEMAB algorithm, proposed by Wang et
al., (2020), which requires only $O(M\log(MK)$ communication rounds for known
time horizons.

We first present the comparison results for Algorithm 1. We consider a horizon
of $T=10^{5}$ steps. We study the behaviour of the algorithm by varying the
number of agents $N$ and the number of arms $K$. We choose three pairs
$(N,K)$, which are $(10,100)$, $(20,100)$, $(10,200)$. We present the result
in Fig. 1 for $30$ independent runs for expected rewards drawn from uniform
$\mathbb{U}(0,1)$ distribution. We plot the median of the cumulative regret
incurred by a single angle at each time step and the $95\%$ confidence
intervals.

We first note that the regret of the DEMAB algorithm is even larger than the
no-communication strategy. The high regret in the DEMAB algorithm is expected
because the algorithm purges the observations collected after each epoch.
Further, the agents do not share the knowledge of the best arm and continue to
redivide the remaining arms to quickly eliminate the bad arms, and hence not
all agents are able to exploit the best arm. This results in the high regret
of the algorithm. To show the scale between the remaining communication
strategies, we plot the regret curves with the DEMAB algorithm in Figure 2.

The start of an epoch $j$ can be observed as the jumps in the cumulative
regret. We observe that the initial epochs incur the largest regret despite
the duration $T_{j}$ being small. This is because the agents are not aware of
the best arm yet and are exploring from possibly worst arms. Also, the regret
grows very slowly in the later phase because most agents send the same arm
index (the optimal arm) and the effective regret in the later rounds increase
only as $\tilde{O}\left(\sqrt{\left(1+\lceil N/K\rceil\right)T_{j}}\right)$,
instead of the upper bound of $\tilde{O}\left(\sqrt{\left(N-1+\lceil
N/K\rceil\right)T_{j}}\right)$. We note that for small number of agents $N$
compared to the number of arms $K$, $(N,K)=(10,100)$ and $(N,K)=(10,200)$, the
algorithm performs closer to the optimal case where the agents could
communicate with each other as observed from Fig. 2(a) and Fig. 2(c). This is
because of the reduced overhead of re-sampling new arms obtained from all the
agents.

We now evaluate the proposed LCC-UCB-GRAPH algorithm on sparse graphs. We
specifically consider Erdős-Rényi graphs $G(N,p)$ where $N\geq 100$ vertices
are a swarm of $N$ agent. Also, $p=10/N\geq\ln{N}/N$ is the edge selection
probability. This gives an expected number of total edges in the graph to be
$5N$. We consider only connected graphs (If the resulting graph is not
connected, we sample another graph.). Once initiated, the graph does not
changes structure over the subsequent time steps. This setup is typically used
in placement of IoT devices communicating with only neighbors Avner and
Mannor, (2016); Sankararaman et al., (2019).

We again consider $3$ cases of $(N,K)$ that are $(100,250)$, $(150,250)$, and
$(100,500)$. We present the result in Fig. 3 for $30$ independent runs. Along
with the expected rewards of the arms, graph structure is also different for
each run. We plot the median of the cumulative regret incurred by a single
angle at each time step and the $95\%$ confidence intervals.

We note that for $K=250$, the performance is similar for $N=100$ (Fig. 3(b))
and $N=150$ (Fig. 3(b)). This is expected for no-communication strategy as the
number of arms are same. For LCC-UCB-GRAPH algorithm, this makes sense as the
degree of the graph $K_{G}$ is higher than the the number of arms allocated to
every agent $\lceil K/N\rceil$. For full communication strategy, this happens
because the expected degree of each agent is same for both graphs. Each agent
can access data from only neighbors, and that remains same. On doubling $K$
from $250$ to $500$, we observe that the regret increases at lower rate for
LCC-UCB-GRAPH than for the other two strategies. This is again attributed to
the fact that $K_{G}$ dominates $\lceil K/N\rceil$ term in regret. We note
that the performance of the DEMAB algorithm is still sub-par to the all the
other three strategies. Note that the LCC-UCB-GRAPH algorithm accumulates
extremely low regret because of the reduced arms per agent $(\leq 5)$ and the
degree of any node is also very low as we considered sparse $G(N,p)$ graphs
with $p=10/N$.

As expected, we note that the proposed strategy performs better than the no
communication strategy. Further, we note that the proposed strategy even
outperforms the strategy where communication happens after every time step and
lags behind in initial time steps only. This is because an agent only shares
what it knows with its neighbors and thus is not able to fully utilize the
graph with $N$ agents. For the initial time steps, the LCC-UCB-GRAPH algorithm
performs pure exploration, hence incurs regret.

We also compare the performance of the LCC-UCB-GRAPH algorithm against a
modified LCC-UCB algorithm which relays messages from other nodes. This
modification allows every agent to receive recommendations from all the other
agents after every epoch. However, the performance of the LCC-UCB-GRAPH
algorithm is significantly better than the relay based LCC-UCB algorithm which
justifies the sub-epoch based modification used in LCC-UCB-GRAPH. LCC-UCB
algorithm wastes a significant portion of the time to generate good
recommendations and hence incur a large regret. The better performance of the
LCC-UCB-GRAPH algorithm is because after each epoch, an agent only receives
arm updates from its neighbors, and hence, the $\sqrt{K/N+K_{G}}$ term in
regret is very small.

##  VIII Conclusion

We considered the problem of reducing communications between $N$ agents and
minimizing the regret of agents interacting with an instance of a Multi Armed
Bandit problem with $K$ arms for time horizon $T$. We proposed two algorithm
LCC-UCB for fully connected networks and LCC-UCB-GRAPH for sparse networks
with maximum degree $K_{G}$ and diameter $D$. We analyzed the algorithms and
obtain regret bound of $\tilde{O}(\sqrt{T(N+K/N)})$ and
$\tilde{O}(D\sqrt{D(K/N+K_{G})T})$ for LCC-UCB and LCC-UCB-GRAPH algorithms
respectively. We found that the algorithms perform well empirically with the
LCC-UCB-GRAPH algorithm outperforming every time communication strategy in
which an agent shares knowledge only with its neighbors. Further, both the
LCC-UCB and the LCC-UCB-GRAPH algorithm beat the existing state of the art
results. Additionally, the low bit complexity for communication in both the
algorithms makes them a suitable choice for power constrained devices.

## References

  * Abbasi-Yadkori et al., (2011) Abbasi-Yadkori, Y., Pál, D., and Szepesvári, C. (2011).  Improved algorithms for linear stochastic bandits.  In Advances in Neural Information Processing Systems, pages 2312–2320.
  * Agrawal and Goyal, (2013) Agrawal, S. and Goyal, N. (2013).  Further optimal regret bounds for thompson sampling.  In Artificial intelligence and statistics, pages 99–107.
  * Audibert and Bubeck, (2009) Audibert, J.-Y. and Bubeck, S. (2009).  Minimax policies for adversarial and stochastic bandits.
  * Auer, (2002) Auer, P. (2002).  Using confidence bounds for exploitation-exploration trade-offs.  Journal of Machine Learning Research, 3(Nov):397–422.
  * Auer et al., (2002) Auer, P., Cesa-Bianchi, N., and Fischer, P. (2002).  Finite-time analysis of the multiarmed bandit problem.  Machine learning, 47(2):235–256.
  * Auer and Ortner, (2010) Auer, P. and Ortner, R. (2010).  Ucb revisited: Improved regret bounds for the stochastic multi-armed bandit problem.  Periodica Mathematica Hungarica, 61(1-2):55–65.
  * Avner and Mannor, (2016) Avner, O. and Mannor, S. (2016).  Multi-user lax communications: a multi-armed bandit approach.  In IEEE INFOCOM 2016-The 35th Annual IEEE International Conference on Computer Communications, pages 1–9. IEEE.
  * Bubeck et al., (2011) Bubeck, S., Munos, R., and Stoltz, G. (2011).  Pure exploration in finitely-armed and continuous-armed bandits.  Theoretical Computer Science, 412(19):1832–1852.
  * Chawla et al., (2020) Chawla, R., Sankararaman, A., Ganesh, A., and Shakkottai, S. (2020).  The gossiping insert-eliminate algorithm for multi-agent bandits.  volume 108 of Proceedings of Machine Learning Research, pages 3471–3481, Online. PMLR.
  * Chung and Lu, (2001) Chung, F. and Lu, L. (2001).  The diameter of sparse random graphs.  Advances in Applied Mathematics, 26(4):257–279.
  * (11) Dubey, A. and Pentland, A. (2020a).  Differentially-private federated linear bandits.  arXiv preprint arXiv:2010.11425.
  * (12) Dubey, A. and Pentland, A. (2020b).  Kernel methods for cooperative contextual bandits.  In International Conference on Machine Learning.
  * Gittins, (1979) Gittins, J. C. (1979).  Bandit processes and dynamic allocation indices.  Journal of the Royal Statistical Society: Series B (Methodological), 41(2):148–164.
  * Hillel et al., (2013) Hillel, E., Karnin, Z. S., Koren, T., Lempel, R., and Somekh, O. (2013).  Distributed exploration in multi-armed bandits.  In Advances in Neural Information Processing Systems, pages 854–862.
  * Kanade et al., (2012) Kanade, V., Liu, Z., and Radunovic, B. (2012).  Distributed non-stochastic experts.  In Advances in Neural Information Processing Systems, pages 260–268.
  * Lale et al., (2019) Lale, S., Azizzadenesheli, K., Anandkumar, A., and Hassibi, B. (2019).  Stochastic linear bandits with hidden low rank structure.  arXiv preprint arXiv:1901.09490.
  * Landgren et al., (2016) Landgren, P., Srivastava, V., and Leonard, N. E. (2016).  Distributed cooperative decision-making in multiarmed bandits: Frequentist and bayesian algorithms.  In 2016 IEEE 55th Conference on Decision and Control (CDC), pages 167–172. IEEE.
  * Lattimore et al., (2018) Lattimore, T., Kveton, B., Li, S., and Szepesvari, C. (2018).  Toprank: A practical algorithm for online stochastic ranking.  In Advances in Neural Information Processing Systems, pages 3945–3954.
  * Lattimore and Szepesvári, (2020) Lattimore, T. and Szepesvári, C. (2020).  Bandit algorithms.  Cambridge University Press.
  * Li et al., (2010) Li, L., Chu, W., Langford, J., and Schapire, R. E. (2010).  A contextual-bandit approach to personalized news article recommendation.  In Proceedings of the 19th international conference on World wide web, pages 661–670.
  * Martínez-Rubio et al., (2019) Martínez-Rubio, D., Kanade, V., and Rebeschini, P. (2019).  Decentralized cooperative stochastic bandits.  In Advances in Neural Information Processing Systems, pages 4529–4540.
  * Sankararaman et al., (2019) Sankararaman, A., Ganesh, A., and Shakkottai, S. (2019).  Social learning in multi agent multi armed bandits.  Proceedings of the ACM on Measurement and Analysis of Computing Systems, 3(3):1–35.
  * Shahrampour et al., (2017) Shahrampour, S., Rakhlin, A., and Jadbabaie, A. (2017).  Multi-armed bandits in multi-agent networks.  In 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 2786–2790. IEEE.
  * Thompson, (1933) Thompson, W. R. (1933).  On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.  Biometrika, 25(3/4):285–294.
  * Wang et al., (2020) Wang, P.-A., Proutiere, A., Ariu, K., Jedra, Y., and Russo, A. (2020).  Optimal algorithms for multiplayer multi-armed bandits.  In International Conference on Artificial Intelligence and Statistics, pages 4120–4129. PMLR.
  * Wang et al., (2019) Wang, Y., Hu, J., Chen, X., and Wang, L. (2019).  Distributed bandit learning: Near-optimal regret with efficient communication.  In International Conference on Learning Representations.