# Multi-Agent Bandit Learning through
Heterogeneous Action Erasure Channels

Osama A. Hanna†*, Merve Karakas†*, Lin F. Yang†, and Christina Fragouli†
†University of California, Los Angeles
Email:{ohanna, mervekarakas, linyang<EMAIL_ADDRESS>*
indicates equal contribution. This work is partially supported by NSF grants
#2221871, #2007714, and #2221871, by Army Research Laboratory grant under
Cooperative Agreement W911NF-17-2-0196, and by Amazon Faculty Award.

###### Abstract

Multi-Armed Bandit (MAB) systems are witnessing an upswing in applications
within multi-agent distributed environments, leading to the advancement of
collaborative MAB algorithms. In such settings, communication between agents
executing actions and the primary learner making decisions can hinder the
learning process. A prevalent challenge in distributed learning is action
erasure, often induced by communication delays and/or channel noise. This
results in agents possibly not receiving the intended action from the learner,
subsequently leading to misguided feedback. In this paper, we introduce novel
algorithms that enable learners to interact concurrently with distributed
agents across heterogeneous action erasure channels with different action
erasure probabilities. We illustrate that, in contrast to existing bandit
algorithms, which experience linear regret, our algorithms assure sub-linear
regret guarantees. Our proposed solutions are founded on a meticulously
crafted repetition protocol and scheduling of learning across heterogeneous
channels. To our knowledge, these are the first algorithms capable of
effectively learning through heterogeneous action erasure channels. We
substantiate the superior performance of our algorithm through numerical
experiments, emphasizing their practical significance in addressing issues
related to communication constraints and delays in multi-agent environments.

##  I INTRODUCTION

Multi-armed bandits, a well-established and effective online learning model,
are increasingly finding applications in multi-agent distributed environments.
One notable use-case involves leveraging a central learner, with actions
(arms) communicated to remote agents to collect rewards, as discussed in [1,
2, 3]. However, a noteworthy gap in the existing literature pertains to
scenarios where the communicated actions may be lost due to communication
channel issues such as delays or noise interference. This challenge becomes
even more pronounced when various agents possess communication channels with
varying capabilities, and these channels do not provide feedback regarding the
receipt of actions. Throughout this paper, we will refer to “feedback” to
denote receipt acknowledgments from the channel, distinguishing this from the
rewards, which represent feedback on the learned actions.

This challenge has not been well explored in the literature, as most works
assume that agents will acknowledge whether an action request has been
received or not. Yet the assumption of feedback availability can have high
cost or simply not be possible. For instance, distributed recommendation
systems may send content (action requests) over wireless channels that are
notoriously subject to delays due to varying channel conditions and lost
packets[4] ; even wired networks are subject to significant delay variability
due to factors such as network topology, queuing delay and prioritization
within cloud databases [5, 6, 4] . Meanwhile, even if the content is delivered
and displayed to the agents (e.g., an app recommending to follow a route,
visit a restaurant, etc.), we cannot be sure when exactly a human user sees
it, if at all.

Another motivating case is when the agents are devices with very limited
communication capabilities. One such application is fleets of medical micro-
robots (which today can be even of nanometre-scale) that propel themselves
through biological media, such as the veins and the gastrointestinal tract [7,
8, 9] . Multi-agent MAB algorithms can facilitate personalizing the robot’s
actions to different patients, for instance, to release tailored amounts of
substances or to attack specific particles. The rewards (capturing action
outcomes) are usually observed through external medical equipment, such as
ultrasound or other imaging; however, conveying what action to play to the
robots, can be communication challenging. A third case is that of military
operations, where a central commander may want to communicate actions to
agents (such as small robots), who do not wish to communicate back so as not
to reveal their position in a hostile territory, yet their actions may have
impact observable through satellite imaging or sensors.

In this work, we dispense with the need for feedback. We ask, what performance
can we achieve if the learner action requests are delivered according to a
known probabilistic model, but we have no additional information on whether
each specific request is delivered or not. In particular, we assume operation
over $T$ rounds, where at each round a central learner sends commands (which
action to play) to $M$ agents through erasure channels with erasure
probability $\epsilon_{i}$, $i=1\ldots M$, where these probabilities can be
arbitrarily different across channels. This induces a probability distribution
on the reception time of each action request, different for each agent111We
note that our schemes extend to more general such probability distributions..
The agents send no feedback (thus the learner does not know which action
request the agents are following); the agents play at each round the last
action command they received. The learner observes the reward for the (uknown)
action played through an error-free channel - which can lead to erroneous
action-reward associations. Indeed, energy and space limitations of micro-
robots, security constraints in military applications, or simply the structure
of the communication protocol can prevent transmitting feedback back to the
learner; and agents are required to perform an action at each time, since even
no action (for instance staying still) is also an action, see Table I for a
small example.

Our objective is to design multi-agent MAB schemes that minimize the impact of
action erasures on the regret, while also leveraging the multi-agent setting
to expedite the learning process. Our main contributions are as follows:

  * •

We propose BatchSP2 , a Successive Arm Elimination based repetition algorithm
with a crafted scheduling part for multi-agent MAB setup with erasures, and
prove sub-linear regret guarantees on the proposed algorithm.

  * •

We provide numerical comparisons with a number of baseline algorithms, show
the superiority of our algorithm to the benchmarks and that simply applying
existing MAB algorithms in a manner oblivious to action erasures can lead to
linear regret.

#### Related Work.

Various MAB algorithms achieving optimal or near-optimal regret bounds under
different assumptions have been proposed over the years [10]. Previous studies
designed optimal algorithms for the simple MAB setting through providing gap
dependent regret of $\tilde{O}(\sum_{a:\Delta_{a}>0}\frac{1}{\Delta_{a}})$ and
worst-case regret of $O(\sqrt{KT\log{T}})$ [11, 12, 13] . However, these
algorithms are not resilient to action erasures and they are not optimized for
multi-agent settings.

Taking a step back, our work fits within the framework of heterogeneous
distributed agents supporting central learning. The heterogeneity in our setup
comes from the diversity in the communication channels (different erasure
probabilities). Although as we discuss next several works have considered
heterogeneous setups, communication channel diversity and how it can affect
MAB learning is we believe a natural setup that has not been widely explored.

Multi-armed bandits with delayed feedback has been studied in recent years
under different settings due to its practical applications. For the stochastic
setting, [14] shows that bounded unknown i.i.d. delays cause an additive
increase in the regret, i.e., $O(\sqrt{KT\log{T}}+K\mathbb{E}\left[D\right])$
where the first term is the regret of stochastic MAB problem with no delays at
round $T$, $K$ is the number of actions, and $\mathbb{E}\left[D\right]$ is the
expected delay. Following the work in [14], [15] proposes a queue-based MAB
algorithm to handle delays. Later, [16] achieves the same additive increase in
regret as in [14] under delayed aggregated anonymous feedback. [17] studies
Bernoulli bandits with known delay distribution where some feedback could also
be censored, i.e., do not reach the learner. Relevant to these works, [18]
proposes an algorithm for the best arm identification problem in stochastic
MABs with partial and delayed feedback where the aim is to minimize the number
of samples for identifying the best action. They extend their methods to the
parallel MAB setting, i.e., multiple actions are pulled at each time; however,
they provide no lower bounds on the sample complexity of their problem
setting. While these works incorporate delays into the stochastic MAB model,
delays are associated with action pulls whereas, in our setup,delays are
associated with agents instead.

A recent work considers the single agent action erasure channel [19] and they
provide a generic repetition scheme that works on top of any MAB algorithm and
gets regret at most $O(1/\sqrt{1-\epsilon})$ away, and a specific algorithm
that gets $O(\sqrt{KT}+K/\sqrt{1-\epsilon})$ regret that is near optimal; our
model accepts their work as a special case; however, extending their methods
to our case is highly non-trivial, as the main challenge being the variability
between erasure probabilities of each channel, that induces a need for careful
scheduling across agents.

#### Paper Organization

In Section II we introduce the notation and system model; we explain the
proposed algorithm in Section III; analyze it in Section IV and provide upper
bounds; evaluate and compare with possible baselines in Section V; and
conclude in Section VI.

##  II PROBLEM FORMULATION

###  II-A Multi-armed Bandits

We consider a stochastic multi-armed bandit problem in which a learner plays
an action $a_{t}\in{\mathcal{A}}$ at each round $t$ from the set of possible
actions $\mathcal{A}$ and receives a reward $r_{t}$ associated with the played
action. This interaction is repeated over a horizon $T$, i.e.,
$t\in\left\\{1,2,...,T\right\\}$ and the learner aims to maximize the
cumulative reward at the end of $T$ rounds. The set of possible actions
${\mathcal{A}}$ are the same throughout the horizon and have $K$ elements,
i.e., $|{\mathcal{A}}|=K$. The decision of the learner on which action to play
may depend on the history
${\mathcal{H}}_{t}=\left\\{a_{1},r_{1},a_{2},r_{2},...,a_{t-1},r_{t-1}\right\\}$.
Additionally, in a stochastic setting, the reward for each action $a$ is
generated from an unknown reward distribution with an unknown mean $\mu_{a}$.
In our analysis, we assume that the rewards are in the interval
$\left[0,1\right]$; however, our results directly extend to sub-Gaussian
distributions. The objective of the learner is minimize the regret over a time
horizon $T$ defined as

$R_{T}=T\max_{a\in{\mathcal{A}}}\mu_{a}-\mathbb{E}\left[\sum_{t=1}^{T}r_{t}\right]$

TABLE I: Example of a MA-MAB Learning over action erasure channels. At each
time $t$ the learner sends action requests to each agent; an agent that does
not receive the request, simply continues to play the last received action.

| t=1 | t=2 | t=3 | t=4 | t=5 | …
---|---|---|---|---|---|---
Learner | $\\{a_{1}^{(m)}\\}_{m=1}^{M}$ | $\\{a_{2}^{(m)}\\}_{m=1}^{M}$ | $\\{a_{3}^{(m)}\\}_{m=1}^{M}$ | $\\{a_{4}^{(m)}\\}_{m=1}^{M}$ | $\\{a_{5}^{(m)}\\}_{m=1}^{M}$ | $\cdots$
Erasure ($\epsilon_{1}=0.1$) |  |  |  | X |  | $\cdots$
Agent 1 ($\tilde{a}_{t}^{(1)}$) | $a_{1}^{(1)}$ | $a_{2}^{(1)}$ | $a_{3}^{(1)}$ | $a_{3}^{(1)}$ | $a_{5}^{(1)}$ | $\cdots$
$\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$
Erasure ($\epsilon_{M}=0.9$) | X | X |  | X | X | $\cdots$
Agent M ($\tilde{a}_{t}^{(M)}$) | $\tilde{a}_{0}^{(M)}$ | $\tilde{a}_{0}^{(M)}$ | $a_{3}^{(M)}$ | $a_{3}^{(M)}$ | $a_{3}^{(M)}$ | $\cdots$

  * •

X denotes the erasure of the action for the given round and agent.

###  II-B Multi-Agent Multi-Armed Bandits with Action Erasures

Consider a central learner connected to $M$ distributed agents, indexed by
$[M]$, over heterogeneous erasure channels. The learner faces a stochastic
$K$-armed bandit problem, i.e., $|{\mathcal{A}}|=K$. At each round $t$ during
a time horizon $T$, the learner selects an action
$a_{t}^{(m)}\in{\mathcal{A}}$ for each agent $m\in[M]$ to play. That is, $M$
actions are played per round (unlike the traditional setting described above).
When an action is chosen for agent $m$, it is communicated through an i.i.d.
action erasure channel characterized by erasure probability $\epsilon_{m}$,
and may or may not be received. That is, independently from other rounds and
agents, each agent $m$ receives $a_{t}^{(m)}$ with probability
$1-\epsilon_{m}$ and does not receive an action with probability
$\epsilon_{m}$. The learner does not know which action requests get erased,
but has knowledge of upper bounds on the erasure probabilities. The agents, on
the other hand, perceive their own erasures but they do not have a feedback
mechanism to inform the learner, i.e., there is no uplink between the agents
and the learner. Furthermore, as motivated from applications discussed in
Section I, we assume that the agents cannot (or do not wish to) run the
algorithm themselves and and continues to play the same action (last
successfully received action), denoted as
$\tilde{a}_{t}^{(m)}\in{\mathcal{A}}$ to play in the case of an erasure.
$\tilde{a}_{0}^{(m)}\in{\mathcal{A}}$ denotes the action performed by the
agent $m$ if the action in first round is erased, it is chosen uniformly at
random. An example of multi-agent multi-armed bandit learning with action
erasures is provided in Table I.

Observation. Although we focus on channels with erasures, our model can also
apply over action delays: an agent receives an action not at the timeslot
sent, but at a later time, based on a (known) delay probability distribution,
and only changes the action she plays once she receives a new action. Our
algorithms naturally extend and apply to this setting as well.

Design Objective. Our objective is to formulate a distributed learning policy
composed of two key elements: a decision strategy that directs the selection
of actions $a_{t}^{(m)}$ for each agent $m$ at each time $t$, and a coping
mechanism for the possible mismatch between the selected actions and received
rewards due to erasures. The performance metric we want to optimize is the
total cumulative regret incurred by the policy over time $T$ and over all $M$
agents:

$R_{T}=\sum_{m=1}^{M}\left(T\max_{a\in{\mathcal{A}}}\mu_{a}-\mathbb{E}\left[\sum_{t=1}^{T}r^{(m)}_{t}\right]\right)$

We note that the cumulative regret in a perfect communication setting (no
action erasures) is lower bounded by $\Omega(\sqrt{KMT})$. This bound
corresponds to the optimal regret order in a centralized $K$-armed bandit
setup, where a total of $MT$ reward observations are centrally accessible for
learning.

##  III PROPOSED ALGORITHM

In this section, we introduce Batched Scheduled Persistent Pulls (BatchSP2 ),
a Successive Arm Elimination (SAE) based multi-agent multi-armed bandit
algorithm with a crafted scheduling part. The pseudocode can be found in
Algorithm 1.

For the problem we consider, misinformation (associating rewards with the
wrong action) can create shifts in the action means. For instance, in the
erasures example in Table I, at time $t=3$ the learner observes the reward of
the action agent $M$ plays, but does not know whether this reward is
associated with action $\tilde{a}_{0}^{(M)}$, $a_{1}^{(M)},a_{2}^{(M)}$, or
$a_{3}^{(M)}.$ Intuitively, to minimize this shift, it is meaningful to study
an algorithm where the same action pulls are repeated several times; in the
example in Table I, if we had selected
$a_{1}^{(M)}=a_{2}^{(M)}=a_{3}^{(M)}=a$, then, we could correctly associate
reward at time $t=3$ with action $a$. Moreover, the fact that we need to play
in parallel across $M$ agents, implies that we need to use a batched
algorithm. Accordingly, we base our proposed algorithm on SAE [20] , described
next, with modifications that enable robustness to misinformation.

SAE is a batched algorithm, i.e., it divides the horizon into batches of
exponentially increasing length and eliminates actions based on a shrinking
confidence region defined by the number of pulls [20] . In each batch $i$, all
remaining actions, included in a set ${\mathcal{A}}_{i}$, are pulled $4^{i}$
times, and after all pulls of the batch are completed, actions are retained
if:

${\mathcal{A}}_{i+1}\leftarrow\\{a\in{\mathcal{A}}_{i}|\max\limits_{\bar{a}\in{\mathcal{A}}_{i}}\hat{\mu}_{\bar{a}}^{(i)}-\hat{\mu}_{a}^{(i)}\leq
4\sqrt{\log{(KT)}/2\cdot 4^{i}}\\}$

where $\hat{\mu}_{a}^{(i)}$ indicates the empirical mean of the reward of
action $a$ in batch $i$.

Note that applying SAE directly in our setup does not perform well, due to two
issues that need attention: (1) it may eliminate the best arm in early batches
due to wrong feedback resulting in linear regret, (2) allocate an unnecessary
amount of resource to bad channels. We have to modify SAE to address these two
issues, as otherwise, as Examples 1 and 2 later in this section illustrate, we
may accrue large regret.

Addressing the first issue is straightforward: the learner simply repeats each
action222A similar scheme was proposed in [19] for the case of a single agent
system. until the probability the correct action has been successfully
received by the agent is sufficiently high. Only after this point the learner
starts associating rewards with actions, thus minimizing the probability of
misinformation. More specifically, if the learner decides to receive $p$
number of rewards for an action $a$ through agent $m$, the learner first asks
the agent $m$ to repeat the action $\alpha_{m}=\lceil
4\log{T}/\log{(1/\epsilon_{m})}\rceil-1$ additional times to ensure a success
probability of at least $1-1/poly(T)$. A total of $\alpha_{m}+p$ rewards are
generated in the environment, but only the last $p$ are taken into account by
the learner to update the mean estimate of action $a$. This ensures with high
probability that the rewards considered (effective rewards) are generated from
the distribution associated with the selected action. We note however that all
$\alpha_{m}+p$ rewards generated are counted in our regret, and thus, large
$\alpha_{m}$ values can affect the regret values we get, as we will also see
in Section IV.

Addressing the second issue, scheduling how action pulls are allocated across
agents, is significantly more challenging. One issue is that, we need to wait
for all pulls of batch $i$ to finish (agents that finish their tasks earlier
will simply play random actions, potentially accumulating regret) before
starting the next batch. Thus, the total regret we will accrue at batch $i$,
is mainly determined333Recall that all actions in the set ${\mathcal{A}}_{i}$
are expected to have mean values within a bounded distance from the optimal;
thus the suboptimal actions in ${\mathcal{A}}_{i}$ are expected to accumulate
similar regret. by $T^{(i)}$, the time at which all $4^{i}$ pulls of the
actions in ${\mathcal{A}}_{i}$ are completed; and $T^{(i)}$ highly depends on
the schedule, as simple examples can illustrate.

The following examples illustrate that two (natural to consider) scheduling
algorithms (one playing all $4^{i}$ pulls of an action at only one agent, and
the other splitting the pulls of each action across all agents) can lead to
larger than needed $T^{(i)}$ and thus suboptimal regret.

Example 1 Assume that we order the agents so that
$\alpha_{1}\leq\alpha_{2}\leq\ldots\alpha_{M}$ (where $\alpha_{m}$ is the
number of repetitions in each channel to ensure high probability action
delivery). One intuitive schedule could be, to assign $\lfloor
K^{(i)}/M\rfloor$ actions to each agent and place the remaining
$\hat{K}=K-\lfloor K^{(i)}/M\rfloor M$ actions to the first (fastest)
$\hat{K}$ agents, where $K^{(i)}$ is the number of active actions in batch
$i$, i.e., $|{\mathcal{A}}_{i}|=K^{(i)}$ . This scheduling has end time
$T^{(i)}=\max{\left(\lfloor\frac{K^{(i)}}{M}\rfloor(\alpha_{M}+4^{i}),(\lfloor\frac{K^{(i)}}{M}\rfloor+1)(\alpha_{\hat{K}}+4^{i})\right)}$
\- and although for some $\alpha_{i}$ values it can perform well, it also
fails in many scenarios. For instance, if $\epsilon_{m}=0~{}\forall m\in[M]$,
the end time becomes $4^{i}K^{(i)}$ whereas the optimal end time is $\lceil
4^{i}K^{(i)}/M\rceil$ (which is smaller by a factor of $M$).

Example 2 Another straightforward approach is to first complete $4^{i}$ pulls
for one action by distributing the pulls across all agents, and then move onto
the next. That is, for each action, the learner sends it to all agents, and
waits until $4^{i}$ effective pulls (i.e., not counting repetitions) are
received back. Note that even if an agent $m$ needs to play one pull, we still
need to wait first for $\alpha_{m}$ rounds before collecting this effective
reward. This scheduling has an end time
$T^{(i)}=K^{(i)}\min\limits_{\tilde{M}\in[M]}(\frac{\sum_{m=1}^{\tilde{M}}\alpha_{m}+4^{i}}{\tilde{M}})$,
where $K^{(i)}=|{\mathcal{A}}_{i}|$. This can be suboptimal; for instance, if
$\alpha_{m}=\alpha~{}\forall m\in[M]$, then the end time of this scheduling is
$T^{(i)}=K^{(i)}\alpha+K^{(i)}\lceil\frac{4^{i}}{M}\rceil$, whereas an end
time of $\lceil\frac{K^{(i)}}{M}\rceil(\alpha+4^{i})$ can be achieved using
the scheduling explained in Example 1.

Our scheduling goal is, given
$\alpha_{1}\leq\alpha_{2}\leq\ldots\leq\alpha_{M}$, to find a schedule that
minimizes $T^{(i)}$. As the previous examples illustrate, neither distributing
actions across all agents, nor restricting each action to be played in one
agent, is optimal. One natural approach is to express the schedule through an
Integer Linear Program (provided in appendix A). The associated LP relaxation,
as also discussed in the appendix, essentially associates a cost
$\frac{a_{m}}{4^{i}}$ with each action pull at agent $m$, and solves a cost-
minimization resource allocation problem. The resulting LP solution gives us a
lower bound $\tau$ on $T^{(i)}$, where:

$\tau:=4^{i}K^{(i)}/\sum_{m=1}^{M}1/(\frac{\alpha_{m}}{4^{i}}+1).$ (1)

Unfortunately, the LP solution cannot always be easily translated to an
integral solution (where each agent $m$ actually plays $a_{m}$ pulls even if
she needs to collect reward for an action only once) while avoiding suboptimal
regrets (as compared to the ILP solution).

Instead, we develop a scheduling algorithm that is polynomial time, and
carefully balances how to split the $4^{i}$ pulls of each action across
agents, so as to decrease the number of required repetitions $\alpha_{i}$,
while still taking advantage as needed from the fact that we have multiple
agents. The pseudocode can be found in Algorithm 2.

Algorithm 1 BatchSP2 ($K$, $M$, ${\bm{\alpha}}$)

1:Input: number of actions $K$, number of agents $M$, repetitions
${\bm{\alpha}}\in{\mathbb{Z}}^{M}_{+}$

2:Initialize batch index $i=1$, set of active actions
${\mathcal{A}}_{1}=\left[K\right]$

3:for batch $i$ do

4: ${\bm{S}},T^{(i)}$ = Schedule$({\mathcal{A}}_{i},{\bm{\alpha}},i)$ (see
Algorithm 2)

5: for $t$ in $[T^{(i)}]$ do

6: send action ${S}_{mt}$ to agent $m$ $\quad\forall m\in\left[M\right]$

7: receive reward $r_{mt}$ $\quad\forall m\in\left[M\right]$

8: Update means of the actions
$~{}~{}{\mu}^{(i)}_{a}=\sum\limits_{m\in{\mathbb{M}}^{(i)}_{a}}\sum_{t=b_{am}^{(i)}}^{e_{am}^{(i)}}r_{mt}/4^{i}\quad\forall
a\in{\mathcal{A}}_{i}$

9: (${\mathbb{M}}^{(i)}_{a}$: set of agents that pulls action $a$ in batch
$i$, $b_{am}^{(i)}$ and $e_{am}^{(i)}$: start and end time of the effective
pulls, respectively, of $a$ in agent $m$ in batch $i$,
$b_{am}^{(i)},e_{am}^{(i)}\in[T^{(i)}]$)

10: Update active action set:
${\mathcal{A}}_{i+1}\leftarrow\\{a\in{\mathcal{A}}_{i}|\max\limits_{j\in{\mathcal{A}}_{i}}{\mu}^{(i)}_{j}-{\mu}^{(i)}_{a}\leq
4\sqrt{\log{(KMT)}/2\cdot 4^{i}}\\}$

11: $i\leftarrow i+1$

The algorithm works in two stages: We first round the LP solution to an
integer solution, which can schedule at least $(K-M)^{+}$ actions. In this
stage, each action is assigned to at most one agent. In the second stage, we
schedule the remaining unscheduled actions by splitting each action among
multiple agents. In particular, we assign to the first stage (where we do not
split action pulls) a duration $\tau$ as in (1): since the LP relaxation
manages to allocate the $4^{i}$ pulls for all actions before $\tau$, keeping
all pulls of an action together before that time can only decrease the total
number of repetitions required by each allocated action. We prove in Section
IV that at least $(K-M)^{+}$444$x^{+}=\max{(x,0)}~{}~{}\forall x\in\mathbb{R}$
actions will be successfully allocated at this stage, leaving $\hat{K}$
remaining actions. In the second stage, we partition the pulls of the
remaining $\hat{K}$ actions into smaller parts of size $\max{(1,\lfloor
M/2\hat{K}\rfloor)}$ and use the first $\lfloor M/2\rfloor$ agents to do the
scheduling. Utilizing only the first $\lfloor M/2\rfloor$ agents allows to
find an end time on the scheduling in terms of $c\sum_{m=1}^{M}\alpha_{m}$
where $c>0$ is some constant instead of a term that depends on $K$ or $M$, as
will become apparent in Section IV.

Algorithm 2 Schedule (${\mathcal{A}}$, ${\bm{\alpha}}$, $i$)

1:Input: set of actions ${\mathcal{A}}$ with $|{\mathcal{A}}|=K$, repetitions
${\bm{\alpha}}\in{\mathbb{Z}}^{M}_{+}$, batch index $i$

2:Initialize $k=0,~{}T^{(i)}=\tau$ (see Eq. 1)

3:Shuffle the set ${\mathcal{A}}$ randomly

4:for agent $m\in[M]$ do

5: Initialize $t_{end}=0,~{}p={\alpha}_{m}+4^{i}$

6: while $t_{end}+p\leq T^{(i)}$ do

7: Assign next action to agent

8: $k\leftarrow k+1$

9: $t_{\text{end}}\leftarrow t_{\text{end}}+p$

10:for $\hat{K}=K-k$ unassigned actions do

11: Divide pulls into $\max{(1,\lfloor M/2\hat{K}\rfloor)}$ equal parts

12:Assign each part to first $\lfloor M/2\rfloor$ agents one by one

13:Imitate assignments of first $\lfloor M/2\rfloor$ agents for remaining
$M-\lfloor M/2\rfloor$ agents (with their own repetitions)

14:Update $T^{(i)}$, the end time of the batch, to agent finishing last in
first $\lfloor M/2\rfloor$ agents

15:Fill remaining slots of the agents randomly

16:Output: ${\bm{S}}\in{\mathbb{R}}^{M\times T^{(i)}}$ the schedule of actions
to agents, $T^{(i)}$ end time

Connecting to channels with delays. We note that our algorithm BatchSP2 (and
its analysis, in the next section), directly applies to channels with delays,
where an action sent by the learner to an agent $m$ is received after $t$
rounds with some probability $p_{t}^{(m)}$, according to some probability
distribution. Indeed, although we used erasure channels for our narrative in
this paper, and motivated use of repetitions over such channels, the only fact
that BatchSP2 essentially hinges on is that, agent $m$ will receive a sent
action with probability at least $\frac{1}{T}$ after $\alpha_{m}$ rounds,
where $\alpha_{m}$ is known. In our case $\alpha_{m}$ was dictated from the
repetition protocol, in other setups it could be dictated from delivery delay
or delivery uncertainty.

##  IV REGRET ANALYSIS

This section provides our theoretical analysis: we first calculate an upper
bound on the end time of each batch in Lemma 1, then use this to derive an
upper bound on the expected regret that depends on suboptimality gaps on
Theorem 1, and provide a gap-independent regret upper bound on Theorem 2.

###### Lemma 1

If the scheduling algorithm outlined in Algorithm 2 is run for batch $i$, then
the end time $T^{(i)}$ of the batch can be bounded as

$T^{(i)}\leq
K4^{i}\tau+6\left(\sum_{m=1}^{M}\frac{\alpha_{m}}{M}+2\frac{K4^{i}}{M}\right)$

where $\tau=\frac{1}{\sum\limits_{m=1}^{M}1/(\alpha_{m}/4^{i}+1)}$,
$\alpha_{m}=\lceil 4\frac{\log{T}}{\log{(1/\epsilon_{m})}}\rceil-1$, $K$ is
the number of actions, and $M$ is the number of agents.

Proof Sketch of Lemma 1. The upper bound on the scheduling end time, hence,
total number of pulled actions in a batch, is obtained in two steps. First,
because $\alpha_{m}+4^{i}$ rounds are sufficient to schedule $4^{i}$ effective
pulls for a single arm at agent $m$, we prove that Algorithm 2 schedules at
least $(K-M)^{+}$ agents in time $K4^{i}\tau$. This implies that at step $10$
of Algorithm 2, the number of remaining arms to be scheduled is bounded by
$M$. As the algorithm schedules these arms among the best $M/2$ agents, each
agent will be assigned a constant number of arms. The final end time is
bounded by noticing that from the averaging principle, the delay of all agents
in the best half is bounded by the average delay $\sum_{m}\alpha_{m}/M$.

The complete proof is provided in Appendix B-A.

###### Theorem 1

Consider a distributed multi-armed bandit setting with $K$ actions and $M$
agents connected through heterogeneous erasure channels with erasure
probabilities $\\{\epsilon_{i}\\}_{i=1}^{M}$. If BatchSP2  is run with horizon
$T$, then the expected regret is,

$\displaystyle\mathbb{E}[R_{T}]\leq
c\Bigg{(}\Bigg{.}\sum_{a:\Delta_{a}>0}\Big{(}\Big{.}\frac{\log{(KMT)}}{\Delta_{a}}+\frac{M\log{(MT)}}{\sum\limits_{m=1}^{M}1/(\alpha_{m}+\frac{\log{(KMT)}}{\Delta_{a}})}\Big{.}\Big{)}+\sum_{m=1}^{M}\alpha_{m}\log{(MT)}+\log{(MT)}\Bigg{.}\Bigg{)}$

where $\alpha_{m}=\lceil 4\log{T}/\log{(1/\epsilon_{m})}\rceil-1$ is the
number of repetitions at agent $m$, $\Delta_{a}$ is the suboptimality gap for
action $a$, and $c>0$ a constant.

Proof Sketch of Theorem 1. The regret bound is achieved by decomposing the
regret of each batch as $\mathbb{E}[R_{T}^{(i)}]=\sum_{a}T_{ia}\Delta_{a}$ and
bounding the expected number of times $\mathbb{E}[T_{ia}]$ that arm $a$ is
pulled in batch $i$. To that end, we condition on a good event entailing that
for each agent $m$ and each consecutive $\alpha_{m}+x$ pulls from action $a$,
the last $x$ rewards are samples from the distribution of action $a$. This
provides a concentration of the empirical means used in Algorithm 1 with high
probability. As a result, we get an upper bound on the number of batches a
suboptimal arm can survive. Having this, to bound $T_{ia}$, it only remains to
bound the number of times an active action is pulled in batch $i$. This is
proved by utilizing the upper bound on the number of pulls in Lemma 1 and
using the symmetry imposed by the randomization in Algorithm 2 to show that
each action has an equal contribution in the total number of pulls. The final
regret bound is obtained by showing that the good event has high probability.

Bounding the excess regret from the rewards not used by the algorithm is a
challenging part of the regret analysis. If the schedule is designed naively,
these rewards may come from the action with the largest gap in the batch.
However, as we show in the proof of Theorem 1, the randomization and shuffling
performed in Algorithm 2 make the contributions of the different arms in the
excess regret uniform in expectation.

The complete proof is provided in Appendix B-B.

The regret bound in Theorem 1 is nearly constant for constant gaps and erasure
probabilities. However, for small gaps, the regret bound can be large. It is
important to note that this will not be the actual regret suffered when the
gaps are small, as for small $\Delta$, the regret is bounded by $TM\Delta$.
The following theorem provides an instance-dependent regret bound that works
for all values of the suboptimality gaps.

###### Theorem 2

Consider the distributed multi-armed bandit setting with $K$ actions and $M$
agents connected through heterogeneous erasure channels
$\\{\epsilon_{i}\\}_{i=1}^{M}$. If BatchSP2 is run for horizon $T$, then the
expected regret is

$\displaystyle R_{T}\leq
c\Bigg{(}\Bigg{.}M\sqrt{\frac{KT\log{(MT)}}{\sum_{m=1}^{M}1/(\alpha_{m}\Delta_{\star}+\log{(KMT)})}}+\sum_{m=1}^{M}\alpha_{m}\log{(KMT)}\Bigg{.}\Bigg{)}$

where $\Delta_{\star}$ is the value satisfying

$\Delta_{\star}=\frac{c^{\prime}K\log{(MT)}}{T\sum\limits_{m=1}^{M}1/(\alpha_{m}+\frac{\log{(KMT)}}{\Delta_{\star}})},$

which can be efficiently approximated using the bisection method,
$\alpha_{m}=\lceil 4\log{T}/\log{(1/\epsilon_{m})}\rceil-1$ number of
repetitions and $c,c^{\prime}>0$ constants.

Proof Sketch of Theorem 2. The regret bound is proved by bounding the regret
bound for arms with small gap (less than $\Delta_{\star}$) by
$TM\Delta_{\star}$ and using the bound in Theorem 1 for the remaining arms
with large gap (greater than $\Delta_{\star}$). The value of $\Delta_{\star}$
is chosen to balance the regret resulting from arms with small gaps and the
regret from arms with large gaps.

The complete proof is provided in Appendix B-C.

It is worth noting that for $\alpha_{m}=0\quad\forall m$ (no erasures), the
regret bound in Theorem 2 reduces to $\tilde{O}(\sqrt{KTM})$, nearly matching
the lower bound on the regret for the model considered in [10] . More
importantly, our bound shows that if
$\alpha_{m}=\tilde{O}(1/\Delta_{\max})\quad\forall m$, where $\Delta_{\max}$
is the maximum gap, then the regret bound is still $\tilde{O}(\sqrt{KTM})$,
hence, we (nearly) suffer no extra regret beyond the no erasure case.

For the single agent case $M=1$, the regret bound in Theorem 2 reduces to
$\tilde{O}(\sqrt{KT}+K\alpha)$ which is shown to be nearly optimal in [19] .

##  V EXPERIMENTS

Figure 1: Comparison results for different numbers of agents. From left to
right, the plots show cumulative regret as a function of rounds t for (a) 4
agents, (b) 20 agents, and (c) 40 agents, respectively.

In this section, we empirically evaluate the regret performance of our
proposed algorithm, BatchSP2, and compare against the following methods:

  * •

MA-SAE: This is an extension of SAE [20] to multi-agent setting. It utilizes
the agents without repeating any actions and considers all the rewards
generated in the environment.

  * •

MA-LSAE-V: This is an extension of SAE to multi-agent setting, that restricts
all pulls of an action to be played at the same agent, as described in Example
1 in Section III.

  * •

MA-LSAE-H: This is another extension of SAE to multi-agent setting, that
distributes the pulls of an action across all agents, as described in Example
2 in Section III.

  * •

MA-UCB: This is an extension of Upper Confidence Bound (UCB) [12, 13]
algorithm to multi-agent setting. UCB is an optimal algorithm for a simple MAB
setting. Compared to SAE, it makes the decision on which action to pull at
each round instead of at each batch.

We have explored a number of experimental setups (in terms of number of
actions, channel quality, horizons, etc); we here show results for two
experiments that we believe are representative:

$\bullet$ Experiment 1, shown in Figure 1, uses $K=10$ actions, with Gaussian
reward distributions that have variance $1$ and means
$\left[0.8,1,0,\cdots,0\right]$. The time horizon is $T=5\times 10^{4}$ and
the regret in each plot is averaged over $100$ experiments with arms shuffled.
The channels have erasure probabilities $0.2$, $0.7$, $0.9$, and $0.99$, and
there is an equal number of $M/4$ channels for each erasure probability.

$\bullet$ Experiment 2, shown in Figure 2, has all parameters the same as
Experiment 1, with the difference that we have now channels with similar
erasure probabilities of $0.9$, $0.93$, $0.95$, and $0.99$ (as before, there
is an equal number of channels for each erasure probability).

From Figure 1, it can be seen that extensions of UCB and SAE may result in
linear regret under action erasures even when the suboptimality gap is large
(0.2 for the instance used in this experiment). Comparing Figure 1 (a) to (c)
for MA-LSAE-V, we can observe how waiting for a bad channel to finish pulling
actions slows down the learning: when the number of agents with erasure
probability 0.2 increases from left to right, MA-LSAE-V starts assigning
actions to agents with small number of repetitions, and cumulative regret gets
smaller. This supports the splitting idea behind our algorithm.

From Figure 2, it can be seen that while trends of algorithms are similar to
Figure 1 (b) in terms of learning (linear versus logarithmic cumulative
regret); when the channel quality gets worse, the gap between MA-LSAE-H and
our algorithm widens. This indicates that while repetitions ensure learning
with high probability, if we assign action pulls to agents without considering
how many additional repetitions are evoked, it can significantly slow down the
learning process. In some cases, it might even result in UCB or SAE to having
lower regret for an extended period of time, despite their linear regret
behavior.

Figure 2: Same scenario as in Figure 1 (b) with worse channel quality.

##  VI CONCLUSION

In this work, we consider the case of a learner connected to multiple
distributed agents through heterogeneous channels, that are subject to action
erasures without action feedback (the same setup can also capture delays and
uncertainty on action reception). If rewards can be externally observed, we
may have misinformation, a mismatch between the action the learner requests
and the agent plays. Because of this, traditional algorithms can easily fail;
instead, we introduce BatchSP2, an efficient algorithm that uses repetition to
achieve robustness over erasures and careful allocation of action pulls to
agents to minimize regret. We provide a theoretical regret analysis of
BatchSP2, which allows to recover as special cases existing bounds, as well as
numerical evaluations that show Batch2SP can achieve superior performance over
baseline schemes.

##  Appendix A LINEAR PROGRAM FORMULATION

We first formulate a (nonlinear integer) program that minimizes the end time
to schedule action pulls in batch $i$ with $K$ actions across $M$ agents as
follows:

$\displaystyle\min\limits_{{\bm{X}}\in\mathbb{R}^{M\times K}}$
$\displaystyle~{}~{}\max\limits_{m\in[M]}\sum\limits_{k=1}^{K}\left(\alpha_{m}\mathds{1}[X_{mk}>0]+X_{mk}\right)$
(2a) s.t.
$\displaystyle~{}~{}\sum\limits_{m=1}^{M}X_{mk}=4^{i}~{}~{}~{}\forall k\in[K]$
(2b) $\displaystyle~{}~{}X_{mk}\in\\{0,1,2,\cdots,4^{i}\\}~{}~{}~{}\forall
m\in[M],~{}\forall k\in[K],$ (2c)

where ${\bm{X}}\in\mathbb{R}^{M\times K}$ captures the variables of the
program, with $X_{mk}$ indicating the number of effective pulls of action $k$
performed by agent $m$. The objective function (2a) is to minimize the latest
end time among agents. Constraint (2b) ensures that the total number of
effective pulls for each action is $4^{i}$; and constraint (2c) forces
effective pulls assigned to each agent per action to be an integral value in
$[0,4^{i}]$. It is easy to see that the progam in (2) is equivalent to the
following integer linear program (ILP):

$\displaystyle\min\limits_{\begin{subarray}{c}{\bm{X}},{\bm{W}}\in\mathbb{R}^{M\times
K}\\\ t\in\mathbb{R}\end{subarray}}$ $\displaystyle~{}~{}~{}~{}t$ (3a) s.t.
$\displaystyle~{}~{}\sum\limits_{k=1}^{K}\left(\alpha_{m}W_{mk}+X_{mk}\right)\leq
t,~{}~{}~{}\forall m\in[M]$ (3b) $\displaystyle~{}~{}X_{mk}\leq
4^{i}W_{mk}~{}~{}~{}\forall m\in[M],~{}\forall k\in[K]$ (3c)
$\displaystyle~{}~{}\sum\limits_{m=1}^{M}X_{mk}=4^{i}~{}~{}~{}\forall k\in[K]$
(3d) $\displaystyle~{}~{}X_{mk}\in\\{0,1,2,\cdots,4^{i}\\}~{}~{}~{}\forall
m\in[M],~{}\forall k\in[K]$ (3e)
$\displaystyle~{}~{}W_{mk}\in\\{0,1\\}~{}~{}~{}\forall m\in[M],~{}\forall
k\in[K],$ (3f)

where the variable $t\in\mathbb{R}$ replaces the $\max$ in objective equation
2a and the variable ${\bm{W}}\in\mathbb{R}^{M\times K}$ replaces the indicator
function. Notice that for any feasible solution ${\bm{X}}$, if $X_{mk}>0$,
$W_{mk}=1$. The relaxed version of the ILP in (3) can be written as

$\displaystyle\min\limits_{\begin{subarray}{c}{\bm{X}},{\bm{W}}\in\mathbb{R}^{M\times
K}\\\ t\in\mathbb{R}\end{subarray}}$ $\displaystyle~{}~{}~{}~{}t$ (4a) s.t.
$\displaystyle~{}~{}\sum\limits_{k=1}^{K}\left(\alpha_{m}W_{mk}+X_{mk}\right)\leq
t,~{}~{}~{}\forall m\in[M]$ (4b) $\displaystyle~{}~{}{\bm{X}}_{mk}\leq
4^{i}W_{mk}~{}~{}~{}\forall m\in[M],~{}\forall k\in[K]$ (4c)
$\displaystyle~{}~{}\sum\limits_{m=1}^{M}X_{mk}=4^{i}~{}~{}~{}\forall k\in[K]$
(4d) $\displaystyle~{}~{}0\leq X_{mk}\leq 4^{i}~{}~{}~{}\forall
m\in[M],~{}\forall k\in[K]$ (4e) $\displaystyle~{}~{}0\leq W_{mk}\leq
1~{}~{}~{}\forall m\in[M],~{}\forall k\in[K],$ (4f)

Notice that the minimum value $W_{mk}$ can take is $X_{mk}/4^{i}$ due to (4c);
hence, by replacing $W_{mk}$ with its minimum value, we get the following
linear program which gives a lower bound on the ILP (3):

$\displaystyle\min\limits_{\begin{subarray}{c}{\bm{X}}\in\mathbb{R}^{M\times
K}\\\ t\in\mathbb{R}\end{subarray}}$ $\displaystyle~{}~{}~{}~{}t$ (5a) s.t.
$\displaystyle~{}~{}\sum\limits_{k=1}^{K}X_{mk}\left(\frac{\alpha_{m}}{4^{i}}+1\right)\leq
t~{}~{}~{}\forall m\in[M]$ (5b)
$\displaystyle~{}~{}\sum\limits_{m=1}^{M}X_{mk}=4^{i}~{}~{}~{}\forall k\in[K]$
(5c) $\displaystyle~{}~{}0\leq X_{mk}~{}~{}~{}\forall m\in[M],~{}\forall
k\in[K],$ (5d)

In the linear program (5), $X_{mk}$ is the variable that indicates how many
effective pulls are assigned to agent $m$ for action $k$. (5c) forces each
action to be pulled $4^{i}$ effective times; however, instead of an integer
number of pulls, each agent is allowed to perform nonnegative fractional
pulls. Furthermore, (5b) indicates that for each agent $m$, one effective pull
has a cost of $\frac{\alpha_{m}}{4^{i}}+1$.

###### Claim 1

The optimal objective value of (5) satisfies,
$t^{\star}=\sum_{k=1}^{K}X_{mk}^{\star}(\alpha_{m}/4^{i}+1)~{}\forall m\in M$,
where ($t^{\star},{\bm{X}}^{\star}$) is the optimal solution of 5.

Proof of Claim 1. First, we observe that at least one of the inequalities in
(5b) holds with equality, otherwise the value of $t^{\star}$ can be decreased
leading to a better objective. Define the set of indices
${\mathcal{E}}_{i}:=\\{m\in[M]:\sum_{k=1}^{K}X_{mk}^{\star}(\alpha_{m}/4^{i}+1)=t^{\star}\\}$.

Now, assume Claim 1 is not correct. And let $m_{s}$ be such that

$\sum_{k=1}^{K}X_{m_{s}k}^{\star}(\alpha_{m_{s}}/4^{i}+1)<t^{\star}.$

Then $\forall m\in{\mathcal{E}}_{i}~{}\exists\\{\beta_{mk}\\}_{k=1}^{K}\geq
0:\sum_{k}\beta_{mk}>0$ small enough such that

$\displaystyle
X^{\prime}_{mk}=\begin{cases}X^{\star}_{mk}-\beta_{mk},&m\in{\mathcal{E}}_{i},~{}\forall
k\in[K]\\\ X^{\star}_{mk}+\sum_{k=1}^{K}\beta_{mk},&~{}m_{s}=m\\\
X^{\star}_{mk}&~{}\text{otherwise}\end{cases}$ $\displaystyle
t^{\prime}=\max_{m}\\{\sum_{k=1}^{K}X_{mk}^{{}^{\prime}}(\alpha_{m}/4^{i}+1)\\}<t^{\star}$

forms a feasible solution in (5) with a smaller objective value
$t^{\prime}<t^{\star}$; hence, $(t^{\star},{\bm{X}}^{\star})$ cannot be
optimal. Then at the optimal solution $(t^{\star},{\bm{X}}^{\star})$,
$t^{\star}=\sum_{k=1}^{K}X_{mk}^{\star}(\alpha_{m}/4^{i}+1)~{}\forall m\in M$.

Using Claim 1 and the constraint (5c);

$\displaystyle
4^{i}K=\sum_{m=1}^{M}\sum_{k=1}^{K}X^{\star}_{mk}=\sum_{m=1}^{M}\frac{t^{\star}}{(\alpha_{m}/4^{i}+1)}~{}=~{}t^{\star}\sum_{m=1}^{M}\frac{1}{(\alpha_{m}/4^{i}+1)}$
$\displaystyle~{}\Rightarrow~{}~{}t^{\star}~{}=~{}\frac{4^{i}K}{\sum_{m=1}^{M}1/(\alpha_{m}/4^{i}+1)}$
(6)

which justifies equation 1.

#### Observation

Note that the solution of the relaxed LP (5) can be directly used for
scheduling of actions by adding $\max{(2\alpha_{M-1},\alpha_{m})}$ to the end
time $t^{\star}$. Since the relaxation in general does not give a feasible
solution for the ILP, we add $\max{(2\alpha_{M-1},\alpha_{M})}$ to the end
time of the relaxed ILP to guarantee a feasible solution for the ILP. As the
additional time slots accumulate regret across all agents, this can result in
$\Omega(M\alpha_{M})$ additional regret which can be large for large $M$. Our
algorithm improves the $M$ factor in $M\alpha_{M}$.

##  Appendix B MISSING PROOFS

TABLE II: Notation $4^{i}$ | : | Number of effective pulls in batch $i$ for each active action
---|---|---
${\mathcal{A}}$ | : | Set of actions, $|{\mathcal{A}}|=K$
${\mathcal{A}}_{i}$ | : | Set of active actions in batch $i$, $|{\mathcal{A}}_{i}|=K^{(i)}$
$\alpha_{m}$ | : |  $=\lceil 4\log{T}/\log{(1/\epsilon_{m})}\rceil-1$, number of repetitions for agent $m$
$\Delta_{a}$ | : |  $=\max_{a^{\prime}\in{\mathcal{A}}}\mu_{a^{\prime}}-\mu_{a}$, suboptimality gap for action $a$
$G$ | : | The event that at least one instruction among the times $t,t+1,\cdots,t+\alpha_{m}-1$ will not be
|  | erased for all agents $m$ and all times $t$
$G_{i}^{\prime}$ | : |  $=\left\\{|{\mu}^{(j)}_{a}-{\mu}_{a}|~{}\leq~{}2\sqrt{\frac{\log{(KMT)}}{2\cdot 4^{j}}}~{}~{}\forall a\in{\mathcal{A}}_{j},~{}j\in[i-1]\right\\}$, the event that empirical means of
|  | active actions in batch $j$ ($\forall a\in A_{j}$) is in confidence region for all batches until batch $i$
$M$ | : | Number of agents
$\mu_{a}$ | : | Reward mean of action $a$
$\mu^{(i)}_{a}$ | : | The empirical mean calculated for action $a$ at batch $i$ (as defined in step 8 in Algorithm 1)
$N_{1}^{(i)}$ | : |  $=\frac{M}{\sum\limits_{m=1}^{M}1/(\alpha_{m}+4^{i})}$, a term that appears in regret
$N_{2}^{(i)}$ | : |  $=12\cdot 4^{i}$, a term that appears in regret
$R_{T}$ | : | Regret of $K$ arm bandit over $M$ channels with horizon $T$
$R^{(i)}_{T}$ | : | Regret of batch $i$ for $K$ arm bandit over $M$ channels with horizon $T$
$T^{(i)}$ | : | Length of the scheduling outputted by Algorithm 2 for batch $i$
$T_{i}$ | : | The total number of instructions played by all agents due to instructions sent in batch $i$
$T_{ia}$ | : | Number of times action $a$ is played by agents due to an instruction sent in batch $i$
$\hat{K}$ | : | Number of actions unassigned in the first part of the scheduling (as described in Algorithm 2 line 10)

###  B-A Proof of Lemma 1

In this section, we present the detailed proof of Lemma 1.

See 1

We prove the upper bound on the end time in two steps.
Step A. First, we claim that the algorithm uses the first $4^{i}K\tau$ rounds
to schedule all $4^{i}$ pulls of at least $(K-M)^{+}$ actions:
Each agent $m$ takes $\alpha_{m}+4^{i}$ to complete all pulls of an action;
hence, it can play all pulls of at least

$\left\lfloor\frac{4^{i}K\tau}{\alpha_{m}+4^{i}}\right\rfloor$

actions. Hence, the total number of actions scheduled across all channels
during the first $4^{i}K\tau$ rounds is

$\displaystyle\sum\limits_{m=1}^{M}\left\lfloor\frac{4^{i}K\tau}{\alpha_{m}+4^{i}}\right\rfloor~{}\geq~{}\sum\limits_{m=1}^{M}\left(\frac{4^{i}K\tau}{\alpha_{m}+4^{i}}-1\right)~{}=~{}K\tau\sum\limits_{m=1}^{M}\frac{1}{\alpha_{m}/4^{i}+1}-M~{}=~{}K-M.$

A lower bound of $(K-M)^{+}$ follows by the non-negativity of the number of
scheduled pulls.
Step B. The second step is to show that the remaining number of actions
$\hat{K}\leq K-(K-M)^{+}=\min{(K,M)}$ can be scheduled using an additional
time of

$6\left(\frac{\sum_{m=1}^{M}\alpha_{m}}{M}+2\frac{4^{i}K}{M}\right).$

Recall that Algorithm 2 divides the $4^{i}$ pulls of each of the remaining
actions into $\max{(1,\lfloor\frac{M}{2\hat{K}}}\rfloor)$ equal parts and
assign each part to an agent. Hence, each part will have number of pulls

$\displaystyle\frac{4^{i}}{\max{(1,\lfloor
M/2\hat{K}}\rfloor)}~{}\overset{(a)}{\leq}~{}\min{(4^{i},\frac{4\hat{K}}{M}4^{i})}$
(7)

and there will be at most $M$ such parts. The first $\lfloor M/2\rfloor$
agents can be used for scheduling these parts in a way such that each agent is
assigned at most three parts. It follows that each agent $m$ needs at most
$3\alpha_{m}+3\min{(4^{i},\frac{4\hat{K}}{M}4^{i})}$ time to perform the
scheduled pulls. Thus the total number of rounds required to schedule the
remaining pulls can be bounded by

$\displaystyle 3\max_{m\in\\{1,\cdots,\lfloor
M/2\rfloor\\}}\alpha_{m}+3\min{(4^{i},\frac{4\hat{K}}{M}4^{i})}$
$\displaystyle~{}\stackrel{{\scriptstyle(i)}}{{=}}~{}3\alpha_{\lfloor
M/2\rfloor}+3\min{(4^{i},\frac{4\hat{K}}{M}4^{i})}$
$\displaystyle~{}\stackrel{{\scriptstyle(ii)}}{{\leq}}~{}6\frac{\sum_{m=1}^{M}\alpha_{m}}{M}+3\min{(4^{i},\frac{4\hat{K}}{M}4^{i})}$
(8)

where $(i),(ii)$ follow from the fact that $\alpha_{m}$’s are ordered, i.e.,
$\alpha_{1}\leq\alpha_{2}\leq\cdots\leq\alpha_{M}$. Combining this with the
result from Step A, we get that the end time needed to send all actions in
batch $i$.

###  B-B Proof of Theorem 1

Theorem 1 Consider a distributed multi-armed bandit setting with $K$ actions
and $M$ agents connected through heterogeneous erasure channels with erasure
probabilities $\\{\epsilon_{i}\\}_{i=1}^{M}$. If BatchSP2  is run with horizon
$T$, then the expected regret is,

$\displaystyle\mathbb{E}[R_{T}]\leq
c\Bigg{(}\Bigg{.}\sum_{a:\Delta_{a}>0}\Big{(}\Big{.}\frac{\log{(KMT)}}{\Delta_{a}}+\frac{M\log{(MT)}}{\sum\limits_{m=1}^{M}1/(\alpha_{m}+\frac{\log{(KMT)}}{\Delta_{a}})}\Big{.}\Big{)}+\sum_{m=1}^{M}\alpha_{m}\log{(MT)}+\log{(MT)}\Bigg{.}\Bigg{)}$

where $\alpha_{m}=\lceil 4\log{T}/\log{(1/\epsilon_{m})}\rceil-1$ is the
number of repetitions at agent $m$, $\Delta_{a}$ is the suboptimality gap for
action $a$, and $c>0$ a constant.

The regret bound is reached by bounding the number of batches a suboptimal arm
can survive as a function of the suboptimality gap, conditioned on a good
event that we specify later. This gives a bound on the maximum sub-optimality
gap at each batch which in turn gives a bound on the regret using the bound on
the batch length given in Lemma 1.

Let $G$ be the event that for all agents $m$ and for all times $t$, at least
one instruction among the times $t,t+1,\cdots,t+\alpha_{m}-1$ will not be
erased. Hence, the event $G$ means that for any agent $m$, we cannot have
$\alpha_{m}$ or more consecutive erasures. This implies that, conditioned on
$G$, when an action $a$ is sent $\alpha_{m}+4^{i}$ consecutive times by the
learner to agent $m$, each of the last $4^{i}$ pulls will generate a reward
from the distribution of action $a$. We call these last $4^{i}$ pulls, the
effective pulls. The probability of the compliment of $G$ can be bounded as

$\displaystyle{\mathbb{P}}[G^{c}]\stackrel{{\scriptstyle(i)}}{{\leq}}\sum_{m=1}^{M}\sum_{t=1}^{T}{\epsilon_{m}}^{\alpha_{m}}\stackrel{{\scriptstyle(ii)}}{{\leq}}\sum_{m=1}^{M}\sum_{t=1}^{T}\frac{1}{T^{4}}\stackrel{{\scriptstyle(iii)}}{{\leq}}\frac{1}{MT},$
(9)

where $(i)$ follows by the union bound over all agents $m$ and times $t$,
$(ii)$ uses $\alpha_{m}=\lceil\frac{4\log{T}}{\log{(1/\epsilon_{m})}}\rceil-1$
, and $(iii)$ follows from $M\leq T$.

Define an event $G^{\prime}_{i}$ as

$G^{\prime}_{i}=\left\\{|{\mu}^{(j)}_{a}-{\mu}_{a}|~{}\leq~{}2\sqrt{\frac{\log{(KMT)}}{2\cdot
4^{j}}}~{}~{}\forall a\in{\mathcal{A}}_{j},~{}j\in[i-1]\right\\},$

where $\mu_{a}^{(j)}$ is the empirical mean calculated for action $a$ at batch
$j$, as defined in step 8 in Algorithm 1. By Hoeffding’s inequality and the
fact that rewards lie in $[0,1]$ almost surely, we have that
${\mathbb{P}}[G^{\prime}_{i}|G]\geq 1-0.25/{(MT)}$. Consequently, events $G$
and $G^{\prime}_{i}$ happening together have a probability

${\mathbb{P}}[G^{\prime}_{i}\cap
G]~{}\geq~{}(1-0.25/(MT))^{2}~{}\geq~{}1-2/(MT).$ (10)

We first bound the number of batches, a suboptimal arm can survive as a
function of the suboptimality gap. Conditioned on $G\cap G^{\prime}_{i+1}$ and
the elimination criterion in Algorithm 1, a sub-optimal action $a$ can survive
getting eliminated in batch $i$ only if $4\sqrt{\frac{\log{(KMT)}}{2\cdot
4^{i}}}\geq\Delta_{a}/2$. This implies that $a$ can be in
${\mathcal{A}}_{i+1}$ only when

$i\leq\left\lceil\log_{4}{\left(\frac{32\log{(KMT)}}{\Delta_{a}^{2}}\right)}\right\rceil,$
(11)

i.e., whenever the batch number $i$ is greater than the bound provided in
equation 11, $a\not\in{\mathcal{A}}_{i}$.

Using the result of Lemma 1, we know the number of sent instructions in each
batch $i$ is upper bounded as

$MT^{(i)}~{}\leq~{}K^{(i)}M\cdot
4^{i}\tau+6\sum_{m=1}^{M}\alpha_{m}+12K^{(i)}4^{i},$ (12)

where $K^{(i)}=|{\mathcal{A}}_{i}|$ is the number of actions at the start of
batch $i$ and $T^{(i)}$ is the length of batch $i$. Conditioned on the event
$G$ (we cannot have $\alpha_{m}$ consecutive erasures for any agent $m$), the
last action played by agent $m$ in batch $i$ will be played at most
$\alpha_{m}$ times in batch $i+1$ (due to potential erasures). This implies
that the total number of instructions, $T_{i}$, played by all agents due to
instructions sent in batch $i$, can be bounded as

$T_{i}~{}\leq~{}\sum_{m=1}^{M}(T^{(i)}+\alpha_{m})~{}\leq~{}K^{(i)}M\cdot
4^{i}\tau+7\sum_{m=1}^{M}\alpha_{m}+12K^{(i)}4^{i}.$ (13)

We utilize the following proposition, restated and proved at the end of
section B-B, to bound the expected number of times a certain action is played
due to an instruction sent in batch $i$.

###### Proposition 1

Conditioned on $(G\cap G^{\prime}_{i},\mathcal{A}_{i})$, the expected number
of times arm $a$ is played due to an instruction sent in batch $i$ is the same
for all $a\in\mathcal{A}_{i}$. In particular, $\mathbb{E}[T_{ia}|G\cap
G^{\prime}_{i},\mathcal{A}_{i}]=\mathbb{E}[T_{ia^{\prime}}|G\cap
G^{\prime}_{i},\mathcal{A}_{i}],\quad\forall a,a^{\prime}\in\mathcal{A}_{i}$.

Conditioning on $\mathcal{A}_{i}$ in the previous proposition and in the
following abbreviates conditioning on the event that the random set of surving
actions in batch $i$ takes the value $\mathcal{A}_{i}$.

Then, we have that

$\displaystyle\mathbb{E}[T_{ia}|G\cap
G^{\prime}_{i},{\mathcal{A}}_{i}]~{}=~{}\frac{\mathbb{E}[T_{i}|G\cap
G^{\prime}_{i},{\mathcal{A}}_{i}]}{K^{(i)}}~{}\leq~{}M\cdot
4^{i}\tau+7\frac{\sum_{m=1}^{M}\alpha_{m}}{K^{(i)}}+12\cdot 4^{i}\ \
~{}\forall a\in\mathcal{A}_{i}.$ (14)

Let $R_{T}^{(i)}$ be the regret of batch $i$. The regret of the algorithm can
be bounded as

$\displaystyle\mathbb{E}[R_{T}]$
$\displaystyle~{}=~{}\sum\limits_{i=1}^{\log{(MT)}}\mathbb{E}[R_{T}^{(i)}]~{}\leq~{}\sum\limits_{i=1}^{\log{(MT)}}\Big{(}\Big{.}\mathbb{E}[R_{T}^{(i)}|G\cap
G^{\prime}_{i}]+MT(1-\mathbb{P}[G\cap G^{\prime}_{i}])\Big{.}\Big{)}$
$\displaystyle~{}\stackrel{{\scriptstyle(a)}}{{\leq}}~{}\sum\limits_{i=1}^{\log{(MT)}}(\mathbb{E}[\mathbb{E}[R_{T}^{(i)}|G\cap
G^{\prime}_{i},{\mathcal{A}}_{i}]]+1)$
$\displaystyle~{}=~{}\sum\limits_{i=1}^{\log{(MT)}}\mathbb{E}[\sum_{a}\mathbb{E}[T_{ia}|G\cap
G^{\prime}_{i},{\mathcal{A}}_{i}]\Delta_{a}]+\log{(MT)}$
$\displaystyle~{}\stackrel{{\scriptstyle(b)}}{{\leq}}~{}\sum\limits_{i=1}^{\log{(MT)}}\Bigg{(}\Bigg{.}\mathbb{E}[\sum_{a}(N_{1}^{(i)}+N_{2}^{(i)})\mathbb{E}[\mathds{1}[a\in{\mathcal{A}}_{i}]|G\cap
G^{\prime}_{i}]\Delta_{a}]$
$\displaystyle\qquad\qquad\qquad+\mathbb{E}[\sum_{a}7\sum_{m=1}^{M}\frac{\alpha_{m}}{K^{(i)}}\mathbb{E}[\mathds{1}[a\in{\mathcal{A}}_{i}]|G\cap
G^{\prime}_{i},{\mathcal{A}}_{i}]\Delta_{a}]\Bigg{.}\Bigg{)}+\log{(MT)}$
$\displaystyle~{}\leq~{}\sum\limits_{i=1}^{\log{(MT)}}\sum_{a}(N_{1}^{(i)}+N_{2}^{(i)})\mathbb{E}[\mathds{1}[a\in{\mathcal{A}}_{i}]|G\cap
G^{\prime}_{i}]\Delta_{a}+\mathbb{E}[7\sum_{m=1}^{M}\alpha_{m}]+\log{(MT)}$
$\displaystyle~{}\leq~{}\sum\limits_{i=1}^{\log{(MT)}}\sum_{a}(N_{1}^{(i)}+N_{2}^{(i)})\mathbb{E}[\mathds{1}[a\in{\mathcal{A}}_{i}]|G\cap
G^{\prime}_{i}]\Delta_{a}+c^{\prime\prime}\log{(MT)}\sum_{m=1}^{M}\alpha_{m}+\log{(MT)},$
(15)

where $(a)$ follows from law of total expectation and equation 10, $(b)$
follows from equation 14 and we use
$N_{1}^{(i)}=\frac{M}{\sum\limits_{m=1}^{M}1/(\alpha_{m}+4^{i})}$ and
$N_{2}^{(i)}=12\cdot 4^{i}$ for these quantities that do not depend on
$\mathcal{A}_{i}$. We will bound each term in equation B-B separately to get
the final regret bound.

We start by bounding the effect of the first term in equation B-B,
$N_{1}^{(i)}=\frac{M}{\sum\limits_{m=1}^{M}1/(\alpha_{m}+4^{i})}$, on the
final regret bound. We have that

$\displaystyle\sum\limits_{i=1}^{\log{(MT)}}\sum_{a}N_{1}^{(i)}\mathbb{E}[\mathds{1}[a\in{\mathcal{A}}_{i}]|G\cap
G^{\prime}_{i}]\Delta_{a}$
$\displaystyle~{}=~{}\sum\limits_{a}\sum\limits_{i=1}^{\log{(MT)}}\Delta_{a}\frac{M\mathbb{E}[\mathds{1}[a\in{\mathcal{A}}_{i}]|G\cap
G^{\prime}_{i}]}{\sum\limits_{m=1}^{M}1/(\alpha_{m}+4^{i})}$
$\displaystyle~{}\stackrel{{\scriptstyle(a)}}{{\leq}}~{}c\sum\limits_{a:\Delta_{a}>0}\frac{M\log{(MT)}}{\sum\limits_{m=1}^{M}1/(\alpha_{m}+\frac{\log{(KMT)}}{\Delta_{a}})}$
(16)

where $c$ is a universal constant, and $(a)$ follows from equation 11 and the
bound being an increasing function of $i$.

The effect of the second term in equation B-B, $N_{2}^{(i)}=12\cdot 4^{i}$,

$\displaystyle\sum_{a}\sum\limits_{i=1}^{\log{(MT)}}N_{2}^{(i)}\mathbb{E}[\mathds{1}[a\in{\mathcal{A}}_{i}]|G\cap
G^{\prime}_{i}]\Delta_{a}$
$\displaystyle~{}=~{}12\sum\limits_{a}\sum\limits_{i=1}^{\left\lceil\log_{4}{\left(\frac{32\log{(KMT)}}{\Delta_{a}^{2}}\right)}\right\rceil}4^{i}\Delta_{a}$
$\displaystyle~{}\stackrel{{\scriptstyle(a)}}{{\leq}}~{}c^{\prime}\sum_{a:\Delta_{a}>0}\frac{\log{(KMT)}}{\Delta_{a}},$
(17)

where $(a)$ follows from equation 11, and $c^{\prime}$ is a universal
constant. The final result follows by summing the bounds in equation B-B and
equation B-B.

See 1 Proof. Recall that $T_{ia}$ is the number of times an agent plays arm
$a$ due to an instruction sent in batch $i$. We represent the schedule by the
set $S=\\{\\{S_{mt}\\}_{m=1}^{M}\\}_{t=1}^{T^{(i)}}$, where $S_{mt}$ is the
action the learner sends to agent $m$ at time $t$. Let $S(a\leftrightarrow
a^{\prime})$ represents the schedule where actions $a,a^{\prime}$ are
exchanged in the schedule $S$, i.e., $S(a\leftrightarrow a^{\prime})_{mt}=a$
whenever $S_{mt}=a^{\prime}$, $S(a\leftrightarrow a^{\prime})_{mt}=a^{\prime}$
whenever $S_{mt}=a$, otherwise $S(a\leftrightarrow a^{\prime})_{mt}=S_{mt}$.
We notice that conditioned on the schedule $S$ in batch $i$, whether an action
is played in slot $t$ due to an instruction sent in batch $i$ is only a
function of the erasures in batches $i,i+1,..$. Hence, we have that

$\displaystyle\mathbb{E}[T_{ia}|G\cap G_{i}^{\prime},\mathcal{A}_{i}]$
$\displaystyle=~{}\sum\limits_{S\in\mathbb{S}}\mathbb{P}[S|G\cap
G_{i}^{\prime},\mathcal{A}_{i}]\mathbb{E}[T_{ia}|G\cap
G_{i}^{\prime},\mathcal{A}_{i},S]=~{}\sum\limits_{S\in\mathbb{S}}\mathbb{P}[S|\mathcal{A}_{i}]\mathbb{E}[T_{ia}|G,S]$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum\limits_{S\in\mathbb{S}}\frac{1}{|\mathbb{S}|}\mathbb{E}[T_{ia}|G,S]=\sum\limits_{S\in\mathbb{S}}\frac{1}{|\mathbb{S}|}\mathbb{E}[T_{ia^{\prime}}|G,S(a\leftrightarrow
a^{\prime})]=\sum\limits_{S\in\mathbb{S}}\frac{1}{|\mathbb{S}|}\mathbb{E}[T_{ia^{\prime}}|G,S]$
$\displaystyle=~{}\mathbb{E}[T_{ia^{\prime}}|G\cap
G_{i}^{\prime},\mathcal{A}_{i}],$ (18)

where $\mathbb{S}$ is the set of all (non-zero probability) possible schedules
for batch $i$, and $(a)$ follows since the randomization in Algorithm 2 makes
all the schedules in $\mathbb{S}$ equally probable.

###  B-C Proof of Theorem 2

Theorem 2 Consider the distributed multi-armed bandit setting with $K$ actions
and $M$ agents connected through heterogeneous erasure channels
$\\{\epsilon_{i}\\}_{i=1}^{M}$. If BatchSP2 is run for horizon $T$, then the
expected regret is

$\displaystyle R_{T}\leq
c\Bigg{(}\Bigg{.}M\sqrt{\frac{KT\log{(MT)}}{\sum_{m=1}^{M}1/(\alpha_{m}\Delta_{\star}+\log{(KMT)})}}~{}+\sum_{m=1}^{M}\alpha_{m}\log{(KMT)}\Bigg{.}\Bigg{)}$

where $\Delta_{\star}$ is the value satisfying

$\Delta_{\star}=\frac{c^{\prime}K\log{(MT)}}{T\sum\limits_{m=1}^{M}1/(\alpha_{m}+\frac{\log{(KMT)}}{\Delta_{\star}})},$

which can be efficiently approximated using the bisection method,
$\alpha_{m}=\lceil 4\log{T}/\log{(1/\epsilon_{m})}\rceil-1$ number of
repetitions and $c,c^{\prime}>0$ constants.

Proof of Theorem 2. From equation B-B, the expected regret can be bounded as

$\displaystyle\mathbb{E}[R_{T}]$
$\displaystyle~{}\leq~{}\sum\limits_{i=1}^{\log{(MT)}}\sum_{a}\mathbb{E}[T_{ia}|G\cap
G^{\prime}_{i}]\Delta_{a}+\log{(MT)}$
$\displaystyle~{}\leq~{}MT\Delta+\sum\limits_{i=1}^{\log{(MT)}}\sum_{a:\Delta_{a}>\Delta}\mathbb{E}[T_{ia}|G\cap
G^{\prime}_{i}]\Delta_{a}+\log{(MT)}$
$\displaystyle~{}\stackrel{{\scriptstyle(a)}}{{\leq}}~{}MT\Delta+\sum\limits_{i=1}^{\log{(MT)}}\sum_{a:\Delta_{a}>\Delta}(N_{1}^{(i)}+N_{2}^{(i)})\mathds{1}[a\in{\mathcal{A}}_{i}]\Delta_{a}+c^{\prime\prime\prime}\log{(MT)}\sum_{m=1}^{M}\alpha_{m}+\log{(MT)}$
$\displaystyle~{}\stackrel{{\scriptstyle(b)}}{{\leq}}~{}MT\Delta+c\sum\limits_{a:\Delta_{a}>\Delta}\left(\frac{M\log{(MT)}}{\sum\limits_{m=1}^{M}1/(\alpha_{m}+\frac{\log{(KMT)}}{\Delta_{a}})}+\frac{\log{(KMT)}}{\Delta_{a}}\right)+f(M,T,{\bm{\alpha}})$
$\displaystyle~{}\stackrel{{\scriptstyle(c)}}{{\leq}}~{}MT\Delta+c\sum\limits_{a:\Delta_{a}>\Delta}\frac{2M\log{(MT)}}{\sum\limits_{m=1}^{M}1/(\alpha_{m}+\frac{\log{(KMT)}}{\Delta_{a}})}+f(M,T,{\bm{\alpha}})$
$\displaystyle~{}\stackrel{{\scriptstyle(d)}}{{=}}~{}MT\Delta+\frac{c^{\prime}KM\log{(MT)}}{\sum\limits_{m=1}^{M}1/(\alpha_{m}+\frac{\log{(KMT)}}{\Delta})}+f(M,T,{\bm{\alpha}})$
$\displaystyle~{}\leq~{}2\max{\left\\{TM\Delta,\frac{c^{\prime}KM\log{(MT)}}{\sum\limits_{m=1}^{M}1/(\alpha_{m}+\frac{\log{(KMT)}}{\Delta})}\right\\}}+f(M,T,{\bm{\alpha}})~{}~{}\forall\Delta>0$
(19)

where
$f(M,T,{\bm{\alpha}})=c^{\prime\prime\prime}\log{(MT)}\sum_{m=1}^{M}\alpha_{m}+\log{(MT)}$
and $c,c^{\prime},c^{\prime\prime\prime}>0$ some constants. (a) follows from
equation 14 where $N_{1}^{(i)}=M/(\sum_{m=1}^{M}1/(\alpha_{m}+4^{i}))$ and
$N_{2}^{(i)}=12\cdot 4^{i}$. (b) follows from directly substituting equation
B-B and equation B-B for the terms; and (c) follows from the fact that the
first term is an increasing function of $\alpha_{m}$’s; therefore,

$\frac{M\log{(MT)}}{\sum\limits_{m=1}^{M}1/(\alpha_{m}+\frac{\log{(KMT)}}{\Delta_{a}})}~{}\geq~{}\frac{M\log{(MT)}}{\sum\limits_{m=1}^{M}1/\frac{\log{(KMT)}}{\Delta_{a}}}~{}\geq~{}\frac{\log{(KMT)}}{\Delta_{a}}~{}~{}~{}\forall\\{\alpha_{m}\\}_{m=1}^{M}\geq
0.$

(d) follows from the term inside the summation being a decreasing function of
$\Delta_{a}$.

We choose $\Delta$ to be the value that minimizes the bound. Hence the optimal
value $\Delta_{\star}$ satisfies:

$\displaystyle
TM\Delta_{\star}=\frac{c^{\prime}KM\log{(MT)}}{\sum\limits_{m=1}^{M}1/(\alpha_{m}+\frac{\log{(KMT)}}{\Delta_{\star}})}$
(20)

Substituting equation 20 to the bound in equation B-C, we get that

$\displaystyle\mathbb{E}[R_{T}]$
$\displaystyle~{}\leq~{}2M\sqrt{\frac{c^{\prime}KT\log{(MT)}}{\sum\limits_{m=1}^{M}1/(\alpha_{m}\Delta_{\star}+\log{(KMT)})}}+c^{\prime\prime\prime}\log{(MT)}\sum_{m=1}^{M}\alpha_{m}+\log{(MT)}.$
(21)

## References

  * [1] O. A. Hanna, L. Yang, and C. Fragouli, “Solving multi-arm bandit using a few bits of communication,” in _International Conference on Artificial Intelligence and Statistics_. PMLR, 2022, pp. 11 215–11 236.
  * [2] O. Hanna, L. Yang, and C. Fragouli, “Learning from distributed users in contextual linear bandits without sharing the context,” _Advances in Neural Information Processing Systems_ , vol. 35, pp. 11 049–11 062, 2022.
  * [3] O. A. Hanna, L. F. Yang, and C. Fragouli, “Compression for multi-arm bandits,” _IEEE Journal on Selected Areas in Information Theory_ , 2023.
  * [4] J. F. Kurose and K. W. Ross, _Computer Networking: A Top-Down Approach_ , 6th ed. Pearson, 2012.
  * [5] E. Yeh, T. Ho, Y. Cui, M. Burd, R. Liu, and D. Leong, “Vip: A framework for joint dynamic forwarding and caching in named data networks,” in _Proceedings of the 1st ACM Conference on Information-Centric Networking_ , 2014, pp. 117–126.
  * [6] M. Dehghan, W. Chu, P. Nain, D. Towsley, and Z.-L. Zhang, “Sharing cache resources among content providers: A utility-based approach,” _IEEE/ACM Transactions on Networking_ , vol. 27, no. 2, pp. 477–490, 2019.
  * [7] Y. Liu, Z. Zou, O. S. Pak, and A. C. H. Tsang, “Learning to cooperate for low-reynolds-number swimming: a model problem for gait coordination,” _Scientific Reports_ , vol. 13, 2023.
  * [8] Z. Zou, Y. Liu, Y. N. Young, and et al., “Gait switching and targeted navigation of microswimmers via deep reinforcement learning,” _Communications Physics_ , vol. 5, p. 158, 2022.
  * [9] I. Amir, I. Attias, T. Koren, Y. Mansour, and R. Livni, “Prediction with corrupted expert advice,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 14 315–14 325, 2020.
  * [10] T. Lattimore and C. Szepesvári, _Bandit algorithms_. Cambridge University Press, 2020.
  * [11] W. R. Thompson, “On the likelihood that one unknown probability exceeds another in view of the evidence of two samples,” _Biometrika_ , vol. 25, pp. 285–294, 1933.
  * [12] P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire, “The nonstochastic multiarmed bandit problem,” _SIAM Journal on Computing_ , vol. 32, no. 1, pp. 48–77, 2002.
  * [13] T. L. Lai, “Adaptive treatment allocation and the multi-armed bandit problem,” _Annals of Statistics_ , vol. 15, pp. 1091–1114, 1987.
  * [14] P. Joulani, A. Gyorgy, and C. Szepesvari, “Online learning under delayed feedback,” in _Proceedings of the 30th International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, S. Dasgupta and D. McAllester, Eds., vol. 28. Atlanta, Georgia, USA: PMLR, 6 2013, pp. 1453–1461.
  * [15] T. Mandel, Y.-E. Liu, E. Brunskill, and Z. Popović, “The queue method: Handling delay, heuristics, prior data, and evaluation in bandits,” _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 29, no. 1, 2 2015.
  * [16] C. Pike-Burke, S. Agrawal, C. Szepesvari, and S. Grunewalder, “Bandits with delayed, aggregated anonymous feedback,” in _International Conference on Machine Learning_. PMLR, 2018, pp. 4105–4113.
  * [17] C. Vernade, O. Cappé, and V. Perchet, “Stochastic bandit models for delayed conversions,” _arXiv preprint arXiv:1706.09186_ , 2017.
  * [18] A. Grover, T. Markov, P. Attia, N. Jin, N. Perkins, B. Cheong, M. Chen, Z. Yang, S. Harris, W. Chueh, and S. Ermon, “Best arm identification in multi-armed bandits with delayed feedback,” in _Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics_ , ser. Proceedings of Machine Learning Research, A. Storkey and F. Perez-Cruz, Eds., vol. 84. PMLR, 4 2018, pp. 833–842.
  * [19] O. A. Hanna, M. Karakas, L. F. Yang, and C. Fragouli, “Multi-arm bandits over action erasure channels,” in _2023 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2023, pp. 1312–1317.
  * [20] P. Auer and R. Ortner, “Ucb revisited: Improved regret bounds for the stochastic multi-armed bandit problem,” _Periodica Mathematica Hungarica_ , vol. 61, no. 1-2, pp. 55–65, 2010.