# Cooperative Multi-agent Bandits: Distributed Algorithms with Optimal
Individual Regret and Constant Communication Costs

Lin Yang
Nanjing University
<EMAIL_ADDRESS>
&Xuchuang Wang
The Chinese University of Hong Kong
<EMAIL_ADDRESS>
&Mohammad H. Hajiesmaili
University of Massachusetts Amherst
<EMAIL_ADDRESS>
&Lijun Zhang
Nanjing University
<EMAIL_ADDRESS>
&John C. S. Lui
The Chinese University of Hong Kong
<EMAIL_ADDRESS>
&Don Towsley
University of Massachusetts Amherst
<EMAIL_ADDRESS>

###### Abstract

Recently, there has been extensive study of cooperative multi-agent multi-
armed bandits where a set of distributed agents cooperatively play the same
multi-armed bandit game. The goal is to develop bandit algorithms with the
optimal group and individual regrets and low communication between agents. The
prior work tackled this problem using two paradigms: leader-follower and fully
distributed algorithms. Prior algorithms in both paradigms achieve the optimal
group regret. The leader-follower algorithms achieve constant communication
costs but fail to achieve optimal individual regrets. The state-of-the-art
fully distributed algorithms achieve optimal individual regrets but fail to
achieve constant communication costs. This paper presents a simple yet
effective communication policy and integrates it into a learning algorithm for
cooperative bandits. Our algorithm achieves the best of both paradigms:
optimal individual regret and constant communication costs.

##  1 Introduction

Recently there has been a surge of various online learning problems in
distributed settings, where a set of agents perform individual learning
algorithms to complete a common task and can cooperate with each other to
improve the performance of the learning process. Distributed online learning
is naturally motivated by a broad range of applications where computational
resources are geographically distributed, and a group of machines has to
communicate with each other to complete a common task cooperatively. Examples
include inference engines in a software-defined network, servers in a data
center, and drones in a swarm. In distributed online learning settings, agents
take actions over time and receive sequential samples associated with the
selected actions. While the agents can cooperate to speed up the learning
process, it comes at the expense of communication overhead in sharing
sequential samples with others. Hence, distributed online learning problems
involve a natural trade-off between learning performance and communication
overheads.

Algorithm | Fully distributed | Individual regret | Communication cost
---|---|---|---
DPE2 [30] | No (leader-follower) | $O(K\log T)$ | $O(K^{2}M^{2}\Delta^{-2})$
ComEx [20] | Yes | $O(K\log T)$ | $O(KM\log T)$
GosInE [9] | Yes | $O((K/M+2)\log T)$ | $\Omega(\log T)$
Dec_UCB [36] | Yes | $O((K/M)\log T)$ | $O(MT)$
UCB-TCOM [31] | Yes | $O((K/M)\log T)$ | $O(KM\log\log T)$
DoE-bandit (this work) | Yes | $O((K/M)\log T)$ | $O(KM\log\Delta^{-1})$
Table 1: A comparison summary of prior literature and this work. Note that all
algorithms in this table achieve the optimal group regret of $O(K\log T)$.
Hence, we only compare the individual and communication costs of different
algorithms.

This paper focuses on studying Cooperative Multi-Agent Multi-Armed Bandit
(CMA2B) problems where multiple agents tackle the same instance of a bandit
problem. In the standard setting of CMA2B, a set of $M$ independent agents
existing over the entire time horizon pull an arm at each time from a common
set of $K$ arms. Associated with arms are mutually independent sequences of
i.i.d. $[0,1]$-valued rewards with mean $0\leq\mu(i)\leq 1$, for arm
$i\in[K]$. Each agent has full access to the set of arms: agents are allowed
to pull and receive a reward from any arm in the common set without any reward
degradation when pulling the same arm. The goal of each agent is to learn the
best arm, with performance characterized by group regret and maximum
individual regret according to different application scenarios. In addition to
regret, another important metric is the communication overheads that the
agents spend in cooperative learning.

The above CMA2B problem is a natural extension of the basic MAB problem [1, 5]
in a cooperative multi-agent setting, with extensive recent literature [29,
15, 6, 7, 19, 8, 18, 22, 25, 12, 30, 10, 4, 9, 33, 21, 20, 36, 34, 35, 31]. In
terms of solution design, the prior work could be categorized into two
paradigms of leader-follower, where a leader agent coordinates the learning
process, and fully distributed algorithms, where there is no central
coordinator between agents.

In the leader-follower paradigm [27, 23, 28, 26, 32, 30, 3, 8, 10], a leader
agent coordinates the learning process among all agents. The state-of-the-art
result in this paradigm is the DPE2 algorithm proposed in [30] and achieves
the optimal group regret with a constant number of communication
overheads111Constant communication cost in this paper means it is independent
of time horizon $T$., Yet, DPE2 (and all other leader-follower-based
algorithms) relies on a structure where the leader solely pays the exploration
costs and incurs almost all the regret in the system. Hence, by nature, this
paradigm fails to achieve a good individual regret since all the regret is
imposed on the leader agent. It is worth noting that in many practical
applications, agents’ individual regrets are crucial for a system’s overall
performance. For example, in a drone swarm, the failure/misbehavior of a
single drone, e.g., it crashes into other drones, can dramatically degrade the
whole system’s overall performance; or in network measurement, the slowest
inference engine determines how fast the network parameters, e.g., traffic
flows and channel bandwidths, are learned.

An alternative approach is to remove the leader as the central coordinator and
design fully distributed cooperative algorithms. While there has been a
success in achieving the optimal group and individual regrets for fully
distributed algorithms, they still fail to achieve low communication overhead,
such as those in the leader-follower-based algorithms. Early works in this
space, e.g., [6, 34, 35] adopted immediate broadcasting as their communication
scheme, incurring a high communication cost of $O(T)$. More recent works [22,
32, 9], improved the communication overhead of the cooperative algorithms to
$O(\log T)$ by optimizing the use of communication budget. The state-of-the-
art in this line of work is the UCB-TCOM algorithm [31] that achieves the
optimal individual regret of $O(K/M\log T)$ with communication cost of
$O(KM\log\log T)$. Despite the above efforts, prior to this work, no existing
algorithm, either based on leader-follower or fully distributed, achieves
optimal group and individual regret with constant communication costs.

Besides the literature on distributed multi-agent bandits, there is a line of
works on batched bandits [24, 13, 11, 16, 17] that relate to CMA2B. In batched
bandits, the time horizon is separated into several batches, and the reward
observations of pulling arms during each batch are only revealed at the end of
the batch. This scheme is similar to the distributed bandits, where the
observations of other agents after the last communication are only revealed at
these agents’ next communication. Therefore, the batched bandits algorithm can
straightforwardly adapt to our multi-agent bandits setting. The current state-
of-the-art batched algorithm requires $O(\log\log T)$ batches to attain the
near-optimal problem-dependent regret bound [16]. That is, directly
transferring their algorithms to the distributed setting leads to $O(\log\log
T)$ communication costs. In contrast, our work shows a constant communication
cost is enough to guarantee the optimal individual and group regrets.

###  1.1 Contributions

This paper presents DoE-bandit, the first fully distributed algorithm that
guarantees the optimal group and maximum individual regrets with constant
communication costs (see Theorem 1). Specifically, DoE-bandit achieves an
$O(\sum_{i:\Delta_{i}>0}\log T/\Delta_{i})$ group regret and an
$O((1/M)\sum_{i:\Delta_{i}>0}\log T/\Delta_{i})$ maximum individual regret,
where $\Delta_{i}$ is the gap of reward means between the optimal arm and the
$i$-th one. Further, DoE-bandit achieves the constant communication complexity
of $O(KM\log(1/\Delta))$, where $\Delta=\min_{i}\Delta_{i}$. A summary of our
results and the most relevant prior work is given in Table 1.

To achieve the above results, DoE-bandit leverages a communication policy
called Distributed Online Estimation (DoE), which is the main algorithmic
contribution of this work. The key idea behind DoE is to determine the
synchronization frequency of sharing local empirical estimates of agents so
that the quality of estimates is maintained compared to the full cooperation
policy. The full cooperation is equivalent to the existence of centralized
estimator with the best possible estimate using all agents’ samples. With
limited cooperation, individual agents have access to their locally observed
samples, which could cause intrinsic deviations from the centralized
estimator. DoE measures the deviations precisely and uses them as an indicator
to trigger a communication round. That is, DoE may urge the agents to
communicate with others to synchronize the estimates on the mean of arms once
it realizes that the deviation is large. By controlling the deviation in a
proper margin, DoE guarantees the optimal learning performance, i.e., the one
achievable by the centralized estimator, for individual agents with low
communication overheads. By plugging DoE into an elimination-based bandit
algorithm, we derive DoE-bandit that improves the state-of-the-art results for
the CMA2B problem. Last, using real datasets, we include experiments that
demonstrate the improved performance of DoE-bandit compared to all benchmark
algorithms listed in Table 1.

##  2 Problem Description

In the following, we introduce a basic multi-agent multi-armed bandit system
model. We note that the communication policy developed in this paper is
generic and could be applied to a broad range of cooperative online learning
settings.

Consider a multi-agent stochastic bandit setting with a set
$\mathcal{M}=\\{1,\dots,M\\}$ of independent agents existing over the entire
time period, and a set $\mathcal{K}=\\{1,2,\dots,K\\}$ of arms. Associated
with arms are mutually independent sequences of i.i.d. $[0,1]$-valued (e.g.,
Bernoulli) rewards with mean $0\leq\mu(i)\leq 1$, for arm $i\in\mathcal{K}$.
Agent $j\in\mathcal{M}$ has full access to the set of arms. Agents are allowed
to pull and receive a reward from any arm from $\mathcal{K}$. Note that for
ease of presentation, we focus on a basic model formulation where agents
reside on a complete graph, incur no communication delays, and the
communication is lossless. However, the basic model and communication policy
proposed in this paper could be extended to account for these practical
additions.

In bandit learning, the goal of each agent $j$ is to learn the best arm as
fast as possible with minimizing the pseudo-regret (called regret for short in
the rest of this paper). The expected regret of an agent $j$ is formally
defined as

$\mathbb{E}\left[R_{T}^{j}\right]:=\mu(i^{*})T-\mathbb{E}\left[\sum\nolimits_{t=1}^{T}x_{t}(I_{t}^{j})\right],$

where $i^{*}$ is the optimal arm, $I_{t}^{j}$ is the action taken by agent $j$
at round $t$, and $x_{t}(I_{t}^{j})$ is the realized reward. Also, the
expectation is taken over the randomness of stochastic rewards and the
algorithm’s (agents’) decisions. In a multi-agent setting, the total
performance is measured by the total expected regret of all agents, defined as

$\mathbb{E}\left[R_{T}\right]:=\sum\nolimits_{j\in\mathcal{M}}\mathbb{E}\left[R_{T}^{j}\right].$

In addition to the group regret, which characterizes overall performance, the
individual performance of each agent is also important. To capture this
individual performance, we measure the maximum individual regret defined as
follows,

$\mathbb{E}\left[\bar{R}_{T}\right]:=\max_{j\in\mathcal{M}}\mathbb{E}\left[R_{T}^{j}\right].$

Similar to other distributed learning problems, the multi-agent MAB setting
encourages distributed agents to cooperate with each other by sharing
information through messages, which include reward observations, reward
averages, or arm indices. We assume any message can be communicated within a
single time slot. The total number of messages communicated among these agents
quantifies the communication complexity of an algorithm.

##  3 Algorithm

This section presents an algorithm that adds a Distributed Online Estimation
(DoE) subroutine to each learning agent $j$ and enables them to approximate
the estimate of the optimal centralized algorithm having all samples when
estimating the parameter of a common i.i.d. process. We introduce the details
of the DoE algorithms in Section 3.1 and then integrate it to a bandit
algorithm in Section 3.2.

###  3.1 Distributed Online Estimation Algorithm (DoE)

To facilitate the presentation of the high-level idea of DoE, let us focus on
a simplified setting that involves only one arm $i$ whose reward mean $\mu(i)$
is unknown to the distributed agents that sample the process simultaneously in
each slot. Since each agent possesses the same number of pulls, we denote
$n_{t}(i)$ as the number of samples available to each agent up to time $t$.
The idea of DoE is to synchronize the estimates of distributed agents when the
local estimates deviate substantially from the centralized one with all
samples. By properly configuring DoE, each individual agent manages to
efficiently control the deviation of the estimates of individual agents with
incurring low communication costs.

More specifically, during the running time, DoE adopts a thresholding policy
to decide whether to trigger a communication round so that agents can exchange
messages with each other to synchronize their estimates with all samples in
the system. To decide whether to start a communication round, each agent
maintains the so-called Common Mean (CM) for the mean over all system-wide
available samples in the last communication round, and simply compare CM with
Auxiliary Local Estimates (ALE, details shown in 3.1.1).

The value of CM is calculated by averaging all samples in the last
communication round, so, its value becomes updated only once at each
communication round and remains unchanged in the subsequent non-communication
rounds. The value of CM at time $t$ is denoted as
$\hat{\mu}_{\texttt{com},t}(i)$. At specific time slots, each agent checks
whether the gap between CM and ALE is smaller than some threshold value. In
DoE, all agents share a common threshold value, which can be time-varying with
the number of available samples, $n_{t}(i)$, and thus the threshold value at
time $t$ is denoted as $G_{n_{t}(i)}$. If the gap between ALE and CM is larger
than the threshold value, a new communication round is triggered to
synchronize the estimates. By doing so, the sum of new samples from other
agents will be collected, a new common mean is calculated, and then the agent
broadcasts the new CM to all others.

In DoE, the threshold value $G_{n_{t}(i)}$ plays a key role in controlling
estimate deviations and communication overheads. Intuitively, when the ALEs of
each individual agent center around the common mean, the actual estimates of
all agents center around CM as well. Thus, no communication is needed.
Otherwise, a communication round is triggered to synchronize the estimates of
all agents. Hence, the threshold value determines how far the estimates
deviate from each other during the non-communication rounds; the smaller the
radius, the smaller the deviations, and the closer the estimates of each agent
approach the mean over all samples. On the other hand, with smaller threshold
values $G_{n_{t}(i)}$, agents communicate more frequently with each other.
Hence, the trade-off of estimation performance versus communication overheads
is associated with $G_{n_{t}(i)}$.

In the following, we present the technical details of the DoE algorithm and
first show how to construct the estimate interval for each agent by using
local estimates.

Algorithm 1 DoE: an algorithm for estimating the mean of arm $i$ by agent $j$,
subscript $t$ is dropped

1:Parameters: $\beta>1$; $G_{n},n=1,2,\dots$

2:Variables: $\hat{\mu}^{j}_{\texttt{aux}}(i)$, $n(i)\leftarrow 0$
$\hat{\mu}_{\texttt{com}}(i)\leftarrow 0$, $G_{\texttt{last}}\leftarrow
G_{1}$; $X^{j^{\prime}}(i)\leftarrow 0$,
$X_{\texttt{last}}^{j^{\prime}}(i)\leftarrow 0$, $\forall
j^{\prime}\in\mathcal{M}$

3:for each round $t$ when the agent gets a new sample do

4: $n(i)\leftarrow n(i)+1$

5: Update $X^{j}(i)$ with the new sample

6: if $\beta G_{n(i)}\leq G_{\texttt{last}}$ then

7: $G_{\texttt{last}}\leftarrow G_{n(i)}$

8: if $|\hat{\mu}_{\texttt{aux}}^{j}(i)-\hat{\mu}_{\texttt{com}}(i)|>G_{n(i)}$
then

9: //Communicate to synchronize the estimates

10: — Collect $X^{j^{\prime}}(i)$ from other agents and calculate the new
$\hat{\mu}_{\texttt{com}}(i)$

11: — Broadcast the new $\hat{\mu}_{\texttt{com}}(i)$ to other agents

12: — $X_{\texttt{last}}^{j^{\prime}}(i)\leftarrow X^{j^{\prime}}(i)$ for all
$j^{\prime}\in\mathcal{M}$

13: end if

14: end if

15: Update $\hat{\mu}_{\texttt{aux}}^{j}(i)$ according to Eq. (1) and
$\hat{\mu}^{j}(i)$ according to Eq. (2)

16:end for

####  3.1.1 Constructing the Auxiliary Local Estimates (ALE)

At a non-communication round $t$, an agent only accesses partial external
samples from others. Below we introduce how an agent builds up the Auxiliary
Local Estimate with missing samples from others.

Note that $n_{t}(i)$ is the number of samples that an agent has made for arm
$i$ up to time slot $t$. Let $t_{\texttt{last}}$ denote the last round before
$t$ that the condition in Line 6 holds, and $X_{t}^{j}(i)$ be the sum of
rewards from $n_{t}(i)$ samples of agent $j$ at time slot $t$ for arm $i$. For
agent $j$, there are $n_{t}(i)-n_{t_{\texttt{last}}}(i)$ missing samples from
any other agents. In DoE, agent $j$ uses local samples in the same time slot
to compensate the missing samples from other agents to construct ALE, denoted
by $\hat{\mu}_{\texttt{aux},t}^{j}(i)$. That is

$\hat{\mu}_{\texttt{aux},t}^{j}(i)=\frac{1}{Mn_{t}(i)}\sum_{j^{\prime}=1}^{M}\left(X_{t_{\texttt{last}}}^{j^{\prime}}(i)+X_{t}^{j}(i)-X_{t_{\texttt{last}}}^{j}(i)\right)$
(1)

where the term $X_{t}^{j}(i)-X_{t_{\texttt{last}}}^{j}(i)$ serves as the
compensation for the missing samples from agent $j^{\prime}$ from
$t_{\texttt{last}}$ to $t$. In DoE, ALE mimics the estimate of the estimator,
which possesses all $Mn_{t}(i)$ samples and serves as an index through which
the agents decide when to communicate.

We weight the local estimates in ALE such that it may involve a larger
estimation error. Hence, in addition to ALE, each agent $j$ calculates the
local estimate $\hat{\mu}_{t}^{j}(i)$ to be used in a bandit algorithm using
the following equation.

$\hat{\mu}_{t}^{j}(i)=\frac{1}{Mn_{t_{\texttt{last}}}(i)+n_{t}(i)-n_{t_{\texttt{last}}}(i)}\left(\sum_{j^{\prime}=1}^{M}X_{t_{\texttt{last}}}^{j^{\prime}}(i)+X_{t}^{j}(i)-X_{t_{\texttt{last}}}^{j}(i)\right)$
(2)

####  3.1.2 Communication Policy of DoE

Now with the definition of ALE, we present the communication policy of DoE.
The pseudocode of DoE is summarized in Algorithm 1. To decide a communication
round, an agent $j$ checks the values of $\hat{\mu}_{\texttt{aux},t}^{j}(i)$
and
$\hat{\mu}_{\texttt{com},t}(i):=(\sum_{j=1}^{M}X_{t_{\texttt{last}}}^{j}(i))/(Mn_{t_{\texttt{last}}}(i))$
every time the specified threshold value, i.e., $G_{n_{t}(i)}$, reduces to
$1/\beta$ $(\beta>1)$ times of the original value (Lines 6, 7 in Algorithm 1).
In DoE, $\beta$ determines how frequently the algorithm checks those values.
Once the deviation of the local estimate $\hat{\mu}_{\texttt{aux},t}^{j}(i)$
from the common mean, $\hat{\mu}_{\texttt{com},t}(i)$, is larger than the
specified threshold value, $G_{n_{t}(i)}$, agent $j$ calls for triggering of a
new communication round. In a communication round triggered by agent $j$, the
sum of missing samples from the last communication round $t_{\texttt{last}}$
from each other agent will be collected to calculate a new common mean. Then,
this new common mean will be broadcast to all other agents.

Our analysis in Lemma 1 shows that DoE can provide a provable performance
guarantee for the single-arm-estimation problem (in the form of confidence
interval) with a tunable trade-off between the estimation quality and
communication overheads. With a richer communication budget, the estimation
performance of DoE approaches that of the optimal estimator with full access
to the samples. Since DoE can provide an explicit confidence interval for the
mean to be estimated, it is straightforward to plug DoE into bandit
algorithms, as exemplified in the next section.

Algorithm 2 DoE-bandit for agent $j$; subscript $t$ is dropped

1:Parameters: $\alpha>0$, $\beta>1$; $G_{n}$, $n=1,2,\ldots$

2:Initialization: $\hat{\mu}_{\texttt{com}}^{j}(i)\leftarrow 0$;
$G_{\texttt{last},i}\leftarrow G_{1}$; $n(i)\leftarrow 0$,
$\hat{\mu}^{j}_{\texttt{aux}}(i)$, for $\forall i$;
$G_{n}\leftarrow\alpha\textsc{CI}(Mn,\delta)$, $n=1,2,\ldots$

3:for each round $t$ do

4: if an arm is eliminated by some other agent then

5: Update the candidate set

6: end if

7: Pull an arm $i$ from the candidate set in a round-robin manner

8: if $\beta G_{n(i)}\leq G_{\texttt{last},i}$ then

9: $G_{\texttt{last},i}\leftarrow G_{n(i)}$

10: if
$|\hat{\mu}^{j}_{\texttt{aux}}(i)-\hat{\mu}_{\texttt{com}}(i)|>G_{n(i)}$ and
the candidate set contains more than one arms then

11: Start a communication round to synchronize the estimates on arm $i$

12: //Execute Algorithm 1’s Lines 10,11,12

13: end if

14: end if

15: Update $n(i)$, $\hat{\mu}^{j}(i)$ and $\hat{\mu}_{\texttt{aux}}^{j}(i)$

16: Update the candidate set via Eq. (4)

17: Notify other agents if an arm is eliminated

18:end for

###  3.2 Integrating DoE to a Bandit Learning Algorithm

In this section, we present a distributed bandit algorithm named DoE-bandit
that uses DoE as the underlying communication policy. We summarize the
pseudocode of DoE-bandit in Algorithm 2.

DoE-bandit is based on active arm elimination, which is a classic approach to
address the well-known tradeoff between exploration (acquiring new
information) and exploitation (optimizing based on available information) in
bandit problems. In this approach, the learner constructs a candidate set for
the arms, which are likely to be optimal, and exploration is allowed only from
the arms in the candidate set. When exploring the candidate set, the algorithm
periodically pulls an arm in and dynamically eliminates the arms which are
unlikely to be optimal.

To integrate DoE with the bandit algorithm, we initiate multiple instances of
DoE run by DoE-bandit, each of which tackles the estimation of a single arm.
To implement the DoE subroutine, each agent notifies others once an arm is
eliminated (Line 17 in Algorithm 2) and pulls arms in the candidate set in a
round-robin manner (Line 7), in order that all agents always pull the same arm
at each time slot and DoE is able to keep track of the total number of samples
in the system by $Mn_{t}(i)$ for all agents. The above rules imply that all
agents have a common candidate set, which is denoted by $\mathcal{C}_{t}$.

Constructing the candidate set. To construct the candidate set, DoE-bandit
determines an explicit confidence interval for the reward means of arms.
Define $\textsc{CI}(n,\delta)$ as the radius of the confidence interval for
the reward process with $n$ samples and confidence level $1-\delta$. If the
reward process is $[0,1]$-valued, we define

$\textsc{CI}(n,\delta)=\sqrt{\frac{\log\delta^{-1}}{2n}},$ (3)

where $\delta$ specifies the violation probability that the true mean lies
outside the above confidence interval. As we mentioned, the threshold value,
$G_{n_{t}(i)}$, in DoE determines the deviation of the estimates in individual
agents from the optimal one with all samples. Hence, in order to guarantee
distributed agents to achieve the same order of the convergence rate as the
optimal one, we set $G_{n_{t}(i)}$ according to the confidence interval with
the total of $Mn_{t}(i)$ samples. By setting
$G_{n_{t}(i)}=\alpha\textsc{CI}(Mn_{t}(i),\delta)$ where $\alpha>0$, DoE
yields a confidence interval for the mean of arm $i$, whose radius is
$(2\alpha\beta+\beta)\textsc{CI}(Mn_{t}(i),\delta)$ (see Lemma 1 on detailed
derivation). With the above result, an arm $i$ is eliminated by agent $j$ from
the candidate set $\mathcal{C}_{t}$ at time $t$ if there exist an arm
$i^{\prime}\in\mathcal{C}_{t}$ such that

$\begin{split}\hat{\mu}^{j}_{t}(i)+&(2\alpha\beta+\beta)\textsc{CI}(Mn_{t}(i),\delta)<\hat{\mu}^{j}_{t}(i^{\prime})-(2\alpha\beta+\beta)\textsc{CI}(Mn_{t}(i^{\prime}),\delta).\end{split}$
(4)

##  4 Theoretical Results for Regret and Communication Cost

In this section, we summarize the theoretical results, through which we show
that the DoE-bandit can achieve the same order of optimal regret as the
optimal centralized one while incurring constant communication overheads.

###  4.1 Main Results

The following lemma shows the performance of DoE with the upper bound of
estimation error proportional to the radius of the confidence interval with
system-wide samples. Then, we summarize the results for DoE-bandit in Theorem
1.

######  Lemma 1.

Assume $M$ agents independently sample an arm with an i.i.d. reward process
with unknown mean $\mu(i)$, and $n_{t}(i)$ is the available samples for each
agent up to time slot $t$. With $\beta>1$ and
$G_{n_{t}(i)}=\alpha\textsc{CI}(Mn_{t}(i),\delta)$, for any $t$, with
probability $1-\delta$, we have

$|\hat{\mu}_{t}^{j}(i)-\mu(i)|\leq(2\alpha\beta+\beta)\textsc{CI}(Mn_{t}(i),\delta).$

######  Theorem 1.

Let $\textsc{CI}_{[0,1]}(n,\delta)$ in Eq. (3) with $1\geq\delta>0$ be the
radius of the confidence interval of a $[0,1]$-valued i.i.d. process with $n$
samples. Set $\beta>1$ and
$G_{n}=\alpha\min\\{1,\textsc{CI}_{[0,1]}(Mn,\delta)\\}$, where $\alpha>0$.
_DoE-bandit_ achieves the following performance.
(i) (Group Regret)

$\mathbb{E}\left[R_{T}\right]\\!=\\!O\left(\sum_{i:\Delta_{i}>0}\\!\\!\\!\frac{8(2\alpha+1)^{2}\beta^{2}\log\delta^{-1}}{\Delta_{i}}\\!+\frac{KM^{3}{\tau}^{2}T\delta}{2}\\!\right)\\!,$
(5)

where $\tau:=\frac{8(2\alpha+1)^{2}\beta^{2}\log\delta^{-1}K}{\Delta^{2}}$.

(ii) (Maximum individual regret)

$\mathbb{E}\left[\bar{R}_{T}\right]\\!=\\!O\left(\sum_{i:\Delta_{i}>0}\\!\frac{8(2\alpha+1)^{2}\beta^{2}\log\delta^{-1}}{M\Delta_{i}}\\!+\\!\frac{KM^{2}{\tau}^{2}T\delta}{2}\right).$
(6)

(iii) (Communication costs) The expected number of messages sent by all agents
running _DoE-bandit_ satisfies the following upper bound.

$\sum_{i:\Delta_{i}>0}6M\log_{\beta}\left(\frac{4(2\alpha\beta+\beta)}{\Delta_{i}}\right)+\frac{KM^{3}{\tau}^{2}T\delta}{2}+M(K-1).$
(7)

In what follows, we sketch the high-level idea of the proof of Theorem 1 for
both regret and communication costs of DoE-bandit. A formal proof is given in
Appendix A. In Section 3, we tailor the elimination-based strategy in DoE-
bandit such that all agents pull arms in a synchronized manner. Hence, each
agent can always track the number of pulls of any arm $i$ by $Mn_{t}(i)$. In
this way, CMA2B involves multiple distributed online estimation problems, each
of which can be solved by DoE separately. In Lemma 1, we show that the DoE
subroutine builds up a confidence interval for the mean reward of an arm
(involving an additional constant factor compared to the one in single-agent
settings with all samples always being available). Then, we can prove the
regret bound in Theorem 1 by applying the results of Lemma 1 to the standard
analysis for a multi-armed bandit problem. Specifically, the expected number
of pulls when the true mean of an arm is outside of the characterized
confidence interval is very small. Thus the probability of eliminating the
optimal by DoE-bandit is low. In other words, the major part of the regret of
DoE-bandit is introduced during the elimination phase when the candidate set
contains more than one arm. Upper bounding the length of the above-mentioned
elimination phase of DoE-bandit yields the regret result in Eq. (6).

To prove the communication cost, we highlight the fact that agents communicate
the mean of arm $i$ only when the radius of the confidence interval provided
by DoE is larger than $\Delta_{i}/2$ (such that the investigated arm remains
in the candidate set). Combining with the rule of DoE that agents communicate
only when the radius of the confidence interval reduces to $1/\beta$ of the
previous, we prove the bound for the communication cost.

###  4.2 Discussion

In the following, we discuss several remarks regarding the significance of our
results.

##### Optimality.

When $\delta=O(1/T^{s})$, $s\geq 2$, the second term in Eq. (5) and (6)
becomes constant. Hence, we can recover a
$O(\sum_{i:\Delta_{i}>0}(1/\Delta_{i})\log T)$ group regret and
$O(\sum_{i:\Delta_{i}>0}(1/\Delta_{i})\log T/M)$ individual regret for the
distributed bandit problem, implying that the proposed algorithm attains both
the (order-) optimal group and maximum individual regrets. In the meantime, it
is possible to drop the second term in Eq. (7), and thus DoE-bandit incurs
constant $O(MK\log(1/\Delta))$ communication costs. This result substantially
improves the state-of-the-art result for fully distributed bandit algorithms
(see Table 1).

##### Influence of $\alpha$ and $\beta$.

Eq. (7) shows that communication overheads influence the estimation quality
through parameters $\alpha$ and $\beta$. Generally speaking, $\beta$ specifies
the frequency that DoE checks the deviation of individual estimates, directly
upper bounding the communication overheads for DoE-bandit. Hence, $\beta$
seems to have a larger influence in the communication overheads bound in
Theorem 1 than $\alpha$. On the other hand, $\alpha$ specifies the radius of
the estimate interval or the threshold for the estimate deviation, which
triggers an actual communication demand. Thus, the influence of $\alpha$ is
more reflected in the empirical performance. Actually, the empirical
performance of DoE-bandit in communication complexity can be much better than
the theoretical bound since agents running the DoE-bandit algorithm start a
communication round in an on-demand manner, i.e., only when their estimates
deviate a lot from each other. For example, if the investigated process is
benign, our algorithm can achieve much lower communication overheads
empirically than those works whose communication policies fail to adapt to
dynamic environments.

##### Results for other i.i.d. processes.

DoE-bandit triggers a communication round based on the variation of the
threshold, with the communication overheads on a suboptimal arm $i$ being
$O(\log_{\beta}(G_{1}/G_{n_{T}(i)}))$, approximately. In DoE-bandit, the
threshold value is set based on that of the confidence interval with all
samples (up to a tunable parameter $\alpha$). For a Bernoulli process, the
mean always lies in $[0,1]$. Hence, we can set $G_{1}=1$, which results in
$O(\log(1/G_{n_{T}}(i)))$ or $O(\log(1/\Delta))$ communication overheads. We
note that by slight modification, the DoE-bandit algorithm can tackle other
i.i.d. processes with similar results obtained. For an i.i.d. process with an
unbounded mean, such as the Gaussian process, the DoE-bandit may choose to
start a communication round only when the size of the confidence interval
shrinks to $O(\sqrt{M})$. This will not degrade the regret results guaranteed
in Theorem 1, since the algorithm only has to spend on average $O(\log T)$
samples in shrinking the confidence intervals of all arms, with an increase of
$O(K\log T)$ regret. On the other hand, the communication overheads is only
$O(\log(\sqrt{M}/\Delta))$, since $G_{1}$ can be set to $O(\sqrt{M})$.

(a)

(a) Communication cost

(b) Group regret

(c) Individual regret

Figure 1: DoE-bandit (this work) vs. baseline algorithms listed in Table 1

(a) Vary reward gap ($10$ arms, $5$ agents)

(b) Vary agent number ($20$ arms)

(c) Vary arm number ($25$ agents)

Figure 2:  Communications: DoE-bandit vs. DPE2

##  5 Numerical Results

In this section, we conduct numerical experiments to corroborate the
performance of the DoE-bandit algorithm. We aim to highlight the advantage of
DoE-bandit in group and individual regrets and in communication costs over
start-of-the-art baselines.

##### Experimental Setups and Baseline Algorithms

We consider a multi-agent bandits setting with $K=100$ arms, $M=50$ agents,
and $T=30K$, and each arm is associated with a Bernoulli distribution with
mean randomly taken from the click-through-rate in Ad-Clicks [2]. In DoE-
bandit algorithm, we set parameters $\alpha=1,\beta=3$ and $\delta=1/T^{2}$.
We run $50$ trials of each experiment and plot the means as lines and their
standard deviations as shaded regions.

We compare the regret and communication costs of DoE-bandit with five
baselines (ComEx [20], GosInE [9], Dec_UCB [36], DPE2 [30], and UCB-TCOM [31])
outlined in Table 1. We note that some of the baseline algorithms are
developed for a set of agents that are connected through an underlying graph
topology. Hence, to make the comparison fair, we consider a complete graph for
all algorithms so that any two agents can communicate.

##### Experimental Results

Figure 1 reports the comparison results. Figure 1a shows that DoE-bandit
achieves the smallest communication costs among all algorithms. Note that DoE-
bandit and DPE2 are the only two algorithms with constant communication costs,
better than others and matching the theoretical results in Table 1. Figure 1b
reports the group regrets of algorithms. The results show DoE-bandit is not as
good as DPE2, ComEx, and UCB-TCOM. This is because DoE-bandit is based on the
arm-elimination policy and others are UCB-like algorithms. It is known that
with the same order-wise regret performance, UCB algorithms are empirically
better than elimination ones in general [14, §6]. Figure 1c reports the
maximum individual regrets of agents. UCB-like algorithms perform still better
than others. However, DPE2—the other algorithm with constant communication
cost—suffers poor individual regret since it leverages a leader-follower
structure to complete the learning task, and the leader agent incurs high
individual regret in the leader.

To further investigate the communication costs of DoE-bandit, in Figure 2, we
report the communication costs of DoE-bandit in comparison to DPE2, as the
only alternative with constant communication costs, under a variety of
different parameter settings. We study the impact of three parameters on the
communications costs of DoE-bandit and DPE2: (1) the reward gap $\Delta$
between arms in Figure 2a; (2) the number of agents $M$ in Figure 2b; and (3)
the number of arms $K$ in Figure 2c. The log-y-axis of these three figures is
the final cumulative communication costs at the end of the time horizon. In
all figures, the communication cost of DoE-bandit is always better than
DPE2’s. Figure 2a shows when $\Delta$ decreases, the communication costs of
DoE-bandit only change slightly while DPE2’s increase. This is because the
communication cost of DoE-bandit is $O(KM\log\Delta^{-1})$ which is much
better than that of DPE2 which is $O(K^{2}M^{2}\Delta^{-2})$. Last, the
communication costs of both DoE-bandit and DPE2 increases as the number of
agents $M$ (Figure 2b) or arms $K$ (Figure 2c) increases. This corroborates
their communication cost upper bounds’ dependency on $K$ and $M$.

##  6 Conclusions

This paper presented DoE-bandit, a fully distributed algorithm for a
cooperative multi-agent multi-armed bandits problem. The proposed algorithm
achieves the optimal group and individual regret with constant communication
overhead. The theoretical claims are verified by numerical experiments and
show that DoE-bandit outperforms prior algorithms.

The core communication policy proposed in this paper could be further extended
in multiple directions. To address the exploitation-exploration dilemma in
bandit learning, DoE-bandit adopts an elimination-based strategy to determine
the arms which will be pulled. The elimination-based strategy is thought to be
less practically efficient than others, such as the UCB strategy (Upper
Confidence Bound) and the TS strategy (Thompson sampling). This phenomenon is
also observed in the multi-agent multi-armed bandit setting (see our
experimental results in Figure 1). Hence, it is meaningful to develop an
UCB/TS-based algorithm which achieves better practical performance with
guaranteeing the same optimal theoretical results claimed in this work.
Second, one can extend the work to capture more practical concerns, such as
considering an underlying topology for agents, communication delays between
agents, and lossy communication between agents.

## References

  * Auer et al. [2002] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer.  Finite-time analysis of the multiarmed bandit problem.  _Machine learning_ , 47(2):235–256, 2002.
  * Avito [2015] Avito.  _Avito Context Ad Clicks_ , 2015.  https://www.kaggle.com/c/avito-context-ad-clicks.
  * Bar-On and Mansour [2019] Yogev Bar-On and Yishay Mansour.  Individual regret in cooperative nonstochastic multi-armed bandits.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Bistritz and Bambos [2020] Ilai Bistritz and Nicholas Bambos.  Cooperative multi-player bandit optimization.  _Advances in Neural Information Processing Systems_ , 33:2016–2027, 2020.
  * Bubeck [2010] Sébastien Bubeck.  _Bandits games and clustering foundations_.  PhD thesis, Université des Sciences et Technologie de Lille-Lille I, 2010.
  * Buccapatnam et al. [2015] Swapna Buccapatnam, Jian Tan, and Li Zhang.  Information sharing in distributed stochastic bandits.  In _2015 IEEE Conference on Computer Communications (INFOCOM)_ , pages 2605–2613. IEEE, 2015.
  * Cesa-Bianchi et al. [2016] Nicol‘o Cesa-Bianchi, Claudio Gentile, Yishay Mansour, and Alberto Minora.  Delay and cooperation in nonstochastic bandits.  In _Conference on Learning Theory_ , pages 605–622. PMLR, 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 _IJCAI_ , pages 164–170, 2017.
  * Chawla et al. [2020] Ronshee Chawla, Abishek Sankararaman, Ayalvadi Ganesh, and Sanjay Shakkottai.  The gossiping insert-eliminate algorithm for multi-agent bandits.  In _International Conference on Artificial Intelligence and Statistics_ , pages 3471–3481. PMLR, 2020.
  * Dubey et al. [2020] Abhimanyu Dubey et al.  Cooperative multi-agent bandits with heavy tails.  In _International Conference on Machine Learning_ , pages 2730–2739. PMLR, 2020.
  * Esfandiari et al. [2021] Hossein Esfandiari, Amin Karbasi, Abbas Mehrabian, and Vahab Mirrokni.  Regret bounds for batched bandits.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pages 7340–7348, 2021.
  * Féraud et al. [2019] Raphaël Féraud, Réda Alami, and Romain Laroche.  Decentralized exploration in multi-armed bandits.  In _International Conference on Machine Learning_ , pages 1901–1909. PMLR, 2019.
  * Gao et al. [2019] Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengqing Zhou.  Batched multi-armed bandits problem.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Garivier et al. [2016] Aurélien Garivier, Tor Lattimore, and Emilie Kaufmann.  On explore-then-commit strategies.  _Advances in Neural Information Processing Systems_ , 29, 2016.
  * Hillel et al. [2013] Eshcar Hillel, Zohar S Karnin, Tomer Koren, Ronny Lempel, and Oren Somekh.  Distributed exploration in multi-armed bandits.  _Advances in Neural Information Processing Systems_ , 26, 2013.
  * Jin et al. [2021] Tianyuan Jin, Jing Tang, Pan Xu, Keke Huang, Xiaokui Xiao, and Quanquan Gu.  Almost optimal anytime algorithm for batched multi-armed bandits.  In _International Conference on Machine Learning_ , pages 5065–5073. PMLR, 2021.
  * Karpov and Zhang [2023] Nikolai Karpov and Qin Zhang.  Collaborative regret minimization in multi-armed bandits.  _arXiv preprint arXiv:2301.11442_ , 2023.
  * Kolla et al. [2018] Ravi Kumar Kolla, Krishna Jagannathan, and Aditya Gopalan.  Collaborative learning of stochastic bandits over a social network.  _IEEE/ACM Transactions on Networking_ , 26(4):1782–1795, 2018.
  * Landgren et al. [2016] Peter Landgren, Vaibhav Srivastava, and Naomi Ehrich Leonard.  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, 2016.
  * Madhushani and Leonard [2021] Udari Madhushani and Naomi Leonard.  When to call your neighbor? strategic communication in cooperative stochastic bandits.  _arXiv preprint arXiv:2110.04396_ , 2021.
  * Madhushani et al. [2021] Udari Madhushani, Abhimanyu Dubey, Naomi Leonard, and Alex Pentland.  One more step towards reality: Cooperative bandits with imperfect communication.  _Advances in Neural Information Processing Systems_ , 34:7813–7824, 2021.
  * Martínez-Rubio et al. [2019] David Martínez-Rubio, Varun Kanade, and Patrick Rebeschini.  Decentralized cooperative stochastic bandits.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Mehrabian et al. [2020] Abbas Mehrabian, Etienne Boursier, Emilie Kaufmann, and Vianney Perchet.  A practical algorithm for multiplayer bandits when arm means vary among players.  In _International Conference on Artificial Intelligence and Statistics_ , pages 1211–1221. PMLR, 2020.
  * Perchet et al. [2016] Vianney Perchet, Philippe Rigollet, Sylvain Chassang, and Erik Snowberg.  Batched bandit problems.  _The Annals of Statistics_ , pages 660–681, 2016.
  * Sankararaman et al. [2019] Abishek Sankararaman, Ayalvadi Ganesh, and Sanjay Shakkottai.  Social learning in multi agent multi armed bandits.  _Proceedings of the ACM on Measurement and Analysis of Computing Systems_ , 3(3):1–35, 2019.
  * Shi and Shen [2021] Chengshuai Shi and Cong Shen.  Federated multi-armed bandits.  In _Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI)_ , 2021.
  * Shi et al. [2021a] Chengshuai Shi, Cong Shen, and Jing Yang.  Federated multi-armed bandits with personalization.  In _International Conference on Artificial Intelligence and Statistics_ , pages 2917–2925. PMLR, 2021a.
  * Shi et al. [2021b] Chengshuai Shi, Wei Xiong, Cong Shen, and Jing Yang.  Heterogeneous multi-player multi-armed bandits: Closing the gap and generalization.  _Advances in Neural Information Processing Systems_ , 34, 2021b.
  * Szorenyi et al. [2013] Balazs Szorenyi, Róbert Busa-Fekete, István Hegedus, Róbert Ormándi, Márk Jelasity, and Balázs Kégl.  Gossip-based distributed stochastic bandit algorithms.  In _International Conference on Machine Learning_ , pages 19–27. PMLR, 2013.
  * Wang et al. [2020a] Po-An Wang, Alexandre Proutiere, Kaito Ariu, Yassir Jedra, and Alessio Russo.  Optimal algorithms for multiplayer multi-armed bandits.  In _International Conference on Artificial Intelligence and Statistics_ , pages 4120–4129. PMLR, 2020a.
  * Wang et al. [2023] Xuchuang Wang, Lin Yang, Yu-zhen Janice Chen, Xutong Liu, Mohammad Hajiesmaili, John Lui, and Don Towsley.  Achieve near-optimal individual regret & low communications in multi-agent bandits.  In _International Conference on Learning Representations_ , 2023.
  * Wang et al. [2019] Yuanhao Wang, Jiachen Hu, Xiaoyu Chen, and Liwei Wang.  Distributed bandit learning: Near-optimal regret with efficient communication.  In _International Conference on Learning Representations_ , 2019.
  * Wang et al. [2020b] Yuanhao Wang, Jiachen Hu, Xiaoyu Chen, and Liwei Wang.  Distributed bandit learning: Near-optimal regret with efficient communication.  In _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_ , 2020b.
  * Yang et al. [2021] Lin Yang, Yu-Zhen Janice Chen, Stephen Pasteris, Mohammad Hajiesmaili, John Lui, and Don Towsley.  Cooperative stochastic bandits with asynchronous agents and constrained feedback.  _Advances in Neural Information Processing Systems_ , 34:8885–8897, 2021.
  * Yang et al. [2022] Lin Yang, Yu-zhen Janice Chen, Mohammad Hajiesmaili, John Lui, and Don Towsley.  Distributed bandits with heterogeneous agents.  _arXiv preprint arXiv:2201.09353_ , 2022.
  * Zhu et al. [2021] Jingxuan Zhu, Ethan Mulle, Christopher Salomon Smith, and Ji Liu.  Decentralized multi-armed bandit can outperform classic upper confidence bound.  _arXiv preprint arXiv:2111.10933_ , 2021.

##  Appendix A Proofs

###  A.1 Proof for Main Theorem 1

##### Proof for the Regret Results

By running the DoE subroutine, the bandit learning algorithm can build up a
confidence interval for the mean reward of an arm. In Lemma 1, we provide the
estimation performance of DoE in estimating the mean of an arm.

According to the results in Lemma 1, letting
$G_{n}=\alpha\min\\{1,\textsc{CI}_{[0,1]}(Mn,\delta)\\}$, each agent can
attain the order-optimal estimate (up to a constant factor
$2\alpha\beta+\beta$) for the mean reward, which slightly degrades the
performance of the bandit algorithm. We prove the regret of DoE-bandit by
using the observation in Lemma 1.

In our analysis, we categorize decisions made by the agents into Type-I and
Type-II decisions. Type-I corresponds to the decisions of an agent when the
true mean values of all arms lie in the confidence intervals calculated by
each agent, i.e., for any arm $i$ and agent $j$,

$\begin{split}\mu\in\left[\hat{\mu}^{j}_{t}\left(i\right)-(2\alpha\beta+\beta)\textsc{CI}_{[0,1]}(Mn_{t}(i),\delta),\hat{\mu}^{j}_{t}\left(i\right)+(2\alpha\beta+\beta)\textsc{CI}_{[0,1]}(Mn_{t}(i),\delta)\right].\end{split}$

Otherwise, Type-II decision occurs, i.e., the actual mean value of some arm is
not within the confidence interval calculated by some agents. Note that agents
may incur high regret when wrongly eliminating the optimal arm from the
candidate set at some time slot with making a Type-II decision. To prove the
regret, we upper bound the probability that a Type-II decision happens and the
number of pulls of suboptimal arms without any Type-II decision occurring,
respectively.

We first upper bound the probability that there is a Type-II decision. Note
that an agent makes a Type-II decision once the true mean of some arm is
outside the confidence interval. For any time slot $t$, any agent $j$ and any
arm $i$, we have

$\begin{split}&\Pr\left[\mu(i)\notin\left[\hat{\mu}^{j}_{t}\left(i\right)-F(n_{t}(i)),\hat{\mu}^{j}_{t}\left(i\right)+F(n_{t}(i))\right]\right]\\\
&\qquad\qquad\qquad\qquad=\sum_{n=1}^{Mt}\Pr\left.\left[\mu(i)\\!\notin\left[\hat{\mu}^{j}_{t}\left(i\right)-F(n),\hat{\mu}^{j}_{t}\left(i\right)+F(n)\right]\right|n_{t}(i)=n\right]\leq
Mt\delta,\end{split}$

where
$F(n_{t}(i)):=(2\alpha\beta+\beta)\textsc{CI}_{[0,1]}(Mn_{t}(i),\delta)$.
Then, an agent at any time slot makes a Type-II decision with probability at
most $KMt\delta$ (there are $K$ arms). Hence, with a union bound, the
probability that a Type-II decision has happened before a time slot $s$ can be
obtained by summing up the above probabilities over investigated time slots
(up to $s$) and agents, which is $KM^{2}s^{2}\delta/2$.

Now we proceed to upper bound the number of pulls of a suboptimal arm with
only Type-I decisions happening. According to the rule of the elimination-
based bandit algorithm, a suboptimal arm will be removed from the candidate
set without further consideration only when the radius of the confidence
interval for this arm reduces to a small value with enough samples. By the
following lemma, we upper bound the number of pulls of suboptimal arms by
agents ($Mn_{t}(i)$) when Type-I decision happens.

######  Lemma 2.

At any time $t\leq T$, if the optimal arm lies in the candidate set and an
agent makes a Type-I decision with pulling a suboptimal arm $i$, i.e.,
$I_{t}^{j}=i$, there is

$Mn_{t}(i)\leq\frac{8(2\alpha+1)^{2}\beta^{2}\log\delta^{-1}}{\Delta^{2}_{i}}+M.$

Lemma 2 holds for any arm, and, therefore, the total number of times of
pulling all $K$ arms (before elimination, in a round-robin manner) is upper
bounded by
$\tau\coloneqq\frac{8(2\alpha+1)^{2}\beta^{2}\log\delta^{-1}K}{\Delta^{2}}$.
Hence, if there is no Type-II decision happening before $\tau$, the optimal
arm will stay in the candidate set all the time, and the regret of DoE-bandit
in this case is

$\begin{split}\sum_{i:\Delta_{i}>0}Mn_{t}(i)\Delta_{i}=\sum_{i:\Delta_{i}>0}\left(\frac{8(2\alpha\beta+\beta)^{2}\log\delta^{-1}}{\Delta_{i}}+M\Delta_{i}\right).\end{split}$

On the other hand, if there is a Type-II decision happening before $\tau$, we
can upper bound the regret of DoE-bandit by $MT$.

Last, with the regrets in the cases with/without a Type-II decision, we can
upper bound the expected regret of the DoE-bandit algorithm.

$\begin{split}\mathbb{E}\left[R_{T}\right]\leq&\sum_{i:\Delta_{i}>0}\left(\frac{8(2\alpha\beta+\beta)^{2}\log\delta^{-1}}{\Delta_{i}}+M\Delta_{i}\right)+\frac{KM^{3}{\tau}^{2}T\delta}{2},\\\
\end{split}$

where the first term on the right-hand side corresponds to the regret portion
when there is no Type-II decision before $\tau$, and the second term
corresponds to the other case.

Due to the same round-robin arm pulling manner in Line 7 of Algorithm 2, all
agents by DoE-bandit pull the same arm at any time slot, and, therefore, all
agents’ individual regrets (rewards) are equal. So, we obtain the individual
regret for each agent by dividing the above total regret upper bound equally.
We summarize the above results and give the regret upper bounds for DoE-bandit
in Theorem 1.

##### Proof for the Communication Costs

We analyze the communication overheads of DoE-bandit arm by arm. If there is a
Type-II decision before $\tau$, we use $MT$ to upper bound the communication
overheads. The expected communication complexity in this case is then

$\frac{KM^{3}{\tau}^{2}T\delta}{2}.$ (8)

In the following, we focus on Type-I decisions. For any suboptimal arm $i$
(with $\Delta_{i}>0$), let $\tau_{i}$ be the last time that DoE-bandit pulls
the arm $i$. At $\tau_{i}$, we have

$4(2\alpha\beta+\beta)\textsc{CI}_{[0,1]}\left(Mn_{\tau_{i}}(i),\delta\right)\geq\Delta_{i}.$

The above equation is proved in the proof of Lemma 2 (at Appendix A.3). When
setting $G_{n}=\alpha\min\\{1,\textsc{CI}_{[0,1]}(Mn,\delta)\\}$, there is
$G_{n_{\tau_{i}}(i)}=\alpha\textsc{CI}_{[0,1]}(Mn_{\tau_{i}}(i),\delta)$, and

$4(2\alpha\beta+\beta)\frac{1}{\alpha}G_{n_{\tau_{i}}(i)}\geq\Delta_{i}.$

Hence, up to time $\tau_{i}$, the communications due to arm $i$ is (recall
$G_{1}=\alpha$)

$\log_{\beta}(G_{1}/G_{n_{\tau_{i}}(i)})\leq\log_{\beta}\left(\frac{4(2\alpha\beta+\beta)}{\Delta_{i}}\right).$

The expected number of communications by suboptimal arms is at most

$\sum_{i:\Delta_{i}>0}\log_{\beta}\left(\frac{4(2\alpha\beta+\beta)}{\alpha\Delta_{i}}\right).$

For the optimal arm, the number of communications (when there is no Type-II
decision) can be upper bounded by the largest communication overheads of
suboptimal arms. That is, the number of communications about the optimal arm
is upper bounded by $O(\log_{\beta}(1/\Delta))$ where the $\Delta$ corresponds
to the smallest non-zero reward gap. That is because when there are multiple
arms in the candidate set, the optimal arm with others in the candidate set is
pulled in a round-robin manner and incurs the same communication overheads as
others in the set; and when there is only one arm left in the candidate set,
the DoE-bandit stops communication. So, to sum up, the total communication
overheads is upper bounded by

$\sum_{i:\Delta_{i}>0}\log_{\beta}\left(\frac{4(2\alpha\beta+\beta)}{\Delta_{i}}\right)+\log_{\beta}\left(\frac{4(2\alpha\beta+\beta)}{\Delta_{\text{min}}}\right)\leq
2\cdot\sum_{i:\Delta_{i}>0}\log_{\beta}\left(\frac{4(2\alpha\beta+\beta)}{\Delta_{i}}\right)$

At each communication time, agents spend totally $3M$ messages in collecting
messages and synchronize the estimates in each agent. In addition, DoE may
update the candidate set in agents when an arm is eliminated, that costs
another $M(K-1)$ messages. Therefore, combined with Eq. (8), the expected
communication overheads of DoE-bandit (the total number of messages) is upper
bounded by Eq. (7).

###  A.2 A Proof of Lemma 1

We prove the lemma by analyzing the following two cases. Let $s$ denote the
last detection point, i.e., the last time slot (before $t$) that the condition
in Line 8 of Algorithm 2 holds.

Case (1): the agent communicated at the last detection point $s$. In this
case, the estimate $\hat{\mu}_{t}^{j}(i)$ is obtained by averaging
$Mn_{s}(i)+n_{t}(i)-n_{s}(i)$ samples. Hence, the following equation holds
with probability $1-\delta$.

$\begin{split}|\hat{\mu}_{t}^{j}(i)-\mu(i)|\leq&\textsc{CI}_{[0,1]}(Mn_{s}(i)+n_{t}(i)-n_{s}(i),\delta)\\\
\overset{(a)}{\leq}&\textsc{CI}_{[0,1]}(Mn_{s}(i),\delta)\\\
\overset{(b)}{\leq}&\beta\textsc{CI}_{[0,1]}(Mn_{t}(i),\delta),\end{split}$

where the inequality (a) is due to that the width of confidence interval
increases with smaller number of samples, and the inequality (b) is due to
that the condition in Line 8 is false at time slot $t$.

In this case, the result in Lemma 1 holds.

Case (2): there is no communication at $s$. Let $A$ be the sum of samples
obtained by agent $j$ if communication _happened_ at $s$. We have

$\begin{split}&\left|(Mn_{s}(i)+n_{t}(i)-n_{s}(i))\hat{\mu}_{t}^{j}(i)-A\right|\\\
=&\left|\left(Mn_{s}(i)\hat{\mu}_{\texttt{aux},s}^{j}(i)+\left(X_{t}^{j}(i)-X_{s}^{j}(i)\right)\right)-\left(\sum_{j^{\prime}=1}^{M}X_{s}^{j^{\prime}}(i)+\left(X_{t}^{j}(i)-X_{s}^{j}(i)\right)\right)\right|\\\
=&\left|Mn_{s}(i)\hat{\mu}_{\texttt{aux},s}^{j}(i)-\sum_{j^{\prime}=1}^{M}X_{s}^{j^{\prime}}(i)\right|.\end{split}$

The above equation is based on the fact that agent always has the local
samples after $s$ no matter there is communication at $s$.

Hence,

$\begin{split}\left|\hat{\mu}_{t}^{j}(i)-\frac{A}{Mn_{s}(i)+n_{t}(i)-n_{s}(i)}\right|&=\frac{1}{(Mn_{s}(i)+n_{t}(i)-n_{s}(i))}\left|Mn_{s}(i)\hat{\mu}_{\texttt{aux},s}^{j}(i)-\sum_{j^{\prime}=1}^{M}X_{s}^{j^{\prime}}(i)\right|\\\
&=\frac{Mn_{s}(i)}{(Mn_{s}(i)+n_{t}(i)-n_{s}(i))}\left|\hat{\mu}_{\texttt{aux},s}^{j}(i)-\frac{1}{Mn_{s}(i)}\sum_{j^{\prime}=1}^{M}X_{s}^{j^{\prime}}(i)\right|\\\
&\leq\left|\hat{\mu}_{\texttt{aux},s}^{j}(i)-\frac{1}{Mn_{s}(i)}\sum_{j^{\prime}=1}^{M}X_{s}^{j^{\prime}}(i)\right|\\\
&\leq 2\alpha\textsc{CI}_{[0,1]}(Mn_{s}(i),\delta)\leq
2\alpha\beta\textsc{CI}_{[0,1]}(Mn_{t}(i),\delta).\end{split}$

where the second inequality is because the condition in Line 10 in Algorithm 2
does not hold at time slot $s$ (since there is no communication at $s$). In
this case,
$\left|\hat{\mu}_{\texttt{aux},s}^{j}(i)-\hat{\mu}_{\texttt{aux},s}^{j^{\prime}}(i)\right|\leq
2G_{n_{s}(i)}=2\alpha\textsc{CI}_{[0,1]}(Mn_{s}(i),\delta)$ for any agents $j$
and $j^{\prime}$. Also,
$\frac{1}{Mn_{s}(i)}\sum_{j^{\prime}=1}^{M}X_{s}^{j^{\prime}}(i)$ averages all
samples up to $s$, and hence its value lies between
$\min_{j^{\prime}}\hat{\mu}_{\texttt{aux},s}^{j^{\prime}}(i)$ and
$\max_{j^{\prime}}\hat{\mu}_{\texttt{aux},s}^{j^{\prime}}(i)$, which weight
partial local samples with a factor $M$ to replace missing ones. Combining the
two facts, we prove the second inequality.

Since $A$ contains the same set of samples as the $\hat{\mu}_{t}^{j}(i)$ in
Case (1), the following equation also holds with probability $1-\delta$:

$\left|\frac{A}{Mn_{s}(i)+n_{t}(i)-n_{s}(i)}-\mu(i)\right|\leq\beta\textsc{CI}_{[0,1]}(Mn_{t}(i),\delta).$

Combining the above two equations yields

$\left|\hat{\mu}_{t}^{j}(i)-\mu(i)\right|\leq(2\alpha+1)\beta\textsc{CI}_{[0,1]}(Mn_{t}(i),\delta),~{}\text{with
~{}probability}~{}1-\delta.$

As a result, we prove the Lemma 1.

###  A.3 A Proof of Lemma 2

We consider agent $j$ running the proposed algorithm makes a Type-I decision
at time $t$ and $I_{t}^{j}=i$. First, we claim that the following holds.

$2(2\alpha\beta+\beta)\textsc{CI}_{[0,1]}\left(Mn_{t}(i),\delta\right)+2(2\alpha\beta+\beta)\textsc{CI}_{[0,1]}\left(Mn_{t}(i^{*}),\delta\right)\geq\Delta_{i}.$
(9)

Otherwise, we have

$\begin{split}&\quad\hat{\mu}^{j}_{t}\left(i^{*}\right)-(2\alpha\beta+\beta)\textsc{CI}_{[0,1]}\left(Mn_{t}(i^{*}),\delta\right)\\\
&=\hat{\mu}^{j}_{t}\left(i^{*}\right)+(2\alpha\beta+\beta)\textsc{CI}_{[0,1]}\left(Mn_{t}(i^{*}),\delta\right)-2(2\alpha\beta+\beta)\textsc{CI}_{[0,1]}\left(Mn_{t}(i^{*}),\delta\right)\\\
&\geq\mu\left(i^{*}\right)-2(2\alpha\beta+\beta)\textsc{CI}_{[0,1]}\left(Mn_{t}(i^{*}),\delta\right)\\\
&=\mu(i)+\Delta_{i}-2(2\alpha\beta+\beta)\textsc{CI}_{[0,1]}\left(Mn_{t}(i^{*}),\delta\right)\\\
&>\mu(i)+2(2\alpha\beta+\beta)\textsc{CI}_{[0,1]}\left(Mn_{t}(i),\delta\right)\\\
&\geq\hat{\mu}_{t}^{j}\left(i\right)+(2\alpha\beta+\beta)\textsc{CI}_{[0,1]}\left(Mn_{t}(i),\delta\right).\end{split}$

It shows the fact that the lower confidence bound of arm $i^{*}$ is larger
than the upper confidence bound of arm $i$, contradicting the rules of the
algorithm to pull arm $i$.

It follows from Equation (9) that
$4(2\alpha\beta+\beta)\textsc{CI}_{[0,1]}\left(M(n_{t}(i)-1),\delta\right)\geq\Delta_{i}$,
since the algorithm pull arms in a round robin manner. Last, we apply the
confidence interval function for a Bernoulli process, and prove that the
number of observations of $i$ received by agent $j$ is upper bounded by

$Mn_{t}(i)\leq\frac{8(2\alpha+1)^{2}\beta^{2}\log\delta^{-1}}{\Delta^{2}_{i}}+M.$