# ICQ: A Quantization Scheme for Best-Arm Identification Over Bit-Constrained
Channels

Fathima Zarin Faizal  Department of Electrical Engineering, IIT Bombay  Adway
Girish  School of Computer and Communication Sciences, EPFL  Manjesh Kumar
Hanawal  Industrial Engineering and Operations Research, IIT Bombay  Nikhil
Karamchandani  Department of Electrical Engineering, IIT Bombay

(April 25, 2023)

###### Abstract

We study the problem of best-arm identification in a distributed variant of
the multi-armed bandit setting, with a central learner and multiple agents.
Each agent is associated with an arm of the bandit, generating stochastic
rewards following an unknown distribution. Further, each agent can communicate
the observed rewards with the learner over a bit-constrained channel. We
propose a novel quantization scheme called Inflating Confidence for
Quantization (ICQ) that can be applied to existing confidence-bound based
learning algorithms such as Successive Elimination. We analyze the performance
of ICQ applied to Successive Elimination and show that the overall algorithm,
named ICQ-SE, has the order-optimal sample complexity as that of the
(unquantized) SE algorithm. Moreover, it requires only an exponentially sparse
frequency of communication between the learner and the agents, thus requiring
considerably fewer bits than existing quantization schemes to successfully
identify the best arm. We validate the performance improvement offered by ICQ
with other quantization methods through numerical experiments.

###### Contents

  1. 1 Introduction
  2. 2 Related work
  3. 3 Problem setup
  4. 4 Proposed quantization scheme and algorithm
  5. 5 Analysis of the ICQ-SE algorithm
  6. 6 Numerical experiments
  7. 7 Conclusion
  8. A Proofs

##  1 Introduction

The _multi-armed bandit_ (MAB) problem is a sequential decision-making model
involving a learner and an environment, where in each round, the learner
chooses from $K$ actions or arms. Each arm is associated with a reward
distribution that is a priori unknown to the learner. The learner then
receives a random reward drawn from the distribution of the chosen arm. We
consider the _pure exploration_ variant [1] of this problem, where the learner
is required to identify the best arm, i.e., the arm with the highest mean
reward, with accuracy better than a prescribed confidence level. The learner
is evaluated based on the number of samples (_sample complexity_) it requires
to identify the best arm. Thus a ‘desirable’ algorithm is one that identifies
the best arm with a smaller sample complexity, for a given confidence level.
The pure exploration setting is well-studied [2, 3, 4] under the assumption
that the learner gets to observe the reward values with full precision.

We consider a distributed variant of the pure exploration MAB setup where the
learner cannot observe the reward samples directly, but through intermediate
agents that act as an interface for each arm. Unlike the traditional pure
exploration MAB setup, the learner no longer has access to the rewards with
full precision, i.e., the agents observe the rewards obtained and communicate
aggregated information to the learner over noiseless, bit-constrained
channels. A key point is that each agent ‘represents’ a single arm, i.e., each
agent pulls and observes rewards from only one fixed arm associated with it.

Motivation. Such distributed learning setups with limited communication arise
in many real-world systems. For example, in wireless networks with bandwidth
constraints involving remote and low-complexity agents, the cost of
communicating the rewards could become a performance bottleneck. Reducing the
number of bits transmitted would result in lower power consumption and
wireless interference. This is particularly significant in IoT networks where
devices are typically resource-constrained and battery-powered [5, 6, 7, 8].
It may then be easier to have the agents process/compress the observations
locally, before passing on information in a more condensed format. Finally,
when learning from privacy-sensitive data, quantization can be used to hide
the exact rewards obtained in such a way that the specific contents remain
unintelligible to the learner, but there is still enough information to carry
out the overall learning task, as in [9].

Contributions. To overcome constraints on the precision with which information
can be sent from the agents to the learner, we develop a quantization scheme
called _Inflating Confidence for Quantization_ (ICQ) for the best-arm
identification problem. Our quantization scheme allows agents to communicate
the reward information with fewer bits while still allowing the learner to
extract enough information to identify the best arm. The key idea behind the
scheme is to generate a high-probability range for the mean reward estimator
at the agent that is smaller than the actual range of the rewards to reduce
the range over which quantization needs to be done. This is done using
appropriately defined confidence intervals for the quantized values.

While we build our scheme on top of the successive elimination framework
proposed for the standard best-arm identification problem [1], and develop an
algorithm called ICQ-SE, a key feature of our proposed quantization strategy
is that it can be used in conjunction with a broad class of alternate schemes
(such as LUCB [10] and lil’UCB [11], to obtain corresponding algorithms ICQ-
LUCB and ICQ-lil’UCB, and so on). This ‘universality’ is clearly desirable and
draws inspiration from [12] where the proposed quantization strategy had a
similar feature with relation to a broad class of regret-minimization
algorithms. Our algorithm ICQ-SE has the following features (shown in Section
5):

  1. 1.

the learner needs to communicate with the agents only exponentially sparsely;

  2. 2.

requires only $B\geq 1$ number of bits for each round of communication for
bounded rewards;

  3. 3.

ensures order-optimal sample complexity compared to the distributed setup with
no bit constraints; and

  4. 4.

can be easily modified to be used with other confidence bound based algorithms
(see Remark 1).

In Section 6, through simulations, we show that this scheme performs better
than other quantization schemes in the MAB literature, for both bounded and
unbounded rewards.

##  2 Related work

MAB problems are well explored in the literature in various settings like
expected regret minimization, simple regret minimization, and Best Arm
Identification (BAI) [13]. For BAI problems [2, 3, 4, 1, 10, 11, 14], the goal
is to identify the best arm either with high confidence within a given budget
(_fixed budget_) or with fewer samples for a given threshold on the
probability of making a mistake (_fixed confidence_). The algorithms developed
for these settings assume that the learner has access to samples from the
reward distributions with full precision. However, this assumption need not
hold in federated setups [15] where the learners and the agents need to
exchange information, and any bottleneck in communication needs to be taken
into account. Some recent works have addressed such issues by modeling
communication bottlenecks as capacity constraints [12, 16, 17] or as a limited
resource that comes at an additional cost [18].

Our work is closer to [12, 16, 17], which propose quantization methods to
improve the performance of learning algorithms under channel capacity
constraints. In [12], the authors propose a quantization scheme, named QuBan,
that can be used over a large class of MAB algorithms in the regret
minimization setting to achieve order-optimal regret. QuBan differs from our
method as it does not make use of confidence bounds for the mean reward
estimators. In [16], the authors propose an adaptive quantization scheme and a
decision-making policy for the Linear Stochastic Bandit setting and show that
$B=\mathcal{O}(d)$ bits guarantees order-optimal regret, where $d$ is the
dimension of the arm set. Their scheme is the closest to ours, where
confidence bounds for the mean reward estimators are used to find a smaller
range to quantize on, albeit for the regret minimization setting. Moreover,
similar to us, they show that using 1 bit for each transmission from the agent
to the learner is sufficient to ensure order-optimal regret compared to the
unquantized setting when the reward distributions have bounded support.

In [17], a pure exploration setting is considered, where a learner and
multiple clients identify the best arm together, with each client being
allotted a disjoint subset of the arms. Like us, they also propose a
quantization scheme for communicating rewards between the clients and the
learner; the difference being that their scheme only works with bounded
rewards. Also, it is hard to control the number of bits used by their
algorithm whereas our proposed scheme ICQ-SE provably allows for a trade-off
between the amount of communication and performance. See Section 6 for a more
detailed comparison.

##  3 Problem setup

In this section, we define notation that will be used throughout the paper and
formalize our system model. The overall setup has been illustrated in Figure
1. Broadly, we study a distributed multi-armed bandit (MAB) problem where the
decision-making and observing entities are separated. They must communicate
their ‘results’ (decisions or observations) to each other over a noiseless
channel using a finite number of bits, with the overall goal of performing a
learning task.

Learner Decode $\mathbf{s}_{1,i},\mathbf{s}_{3,i}$and broadcast $c_{i+1}$
Agent 1 encode informationinto $\mathbf{s}_{1,i}$action $c_{i}$finite-bit
symbol $\mathbf{s}_{1,i}$ Agent 2 Inactive incomm. round $i$action $c_{i}$
Agent 3 encode informationinto $\mathbf{s}_{3,i}$action $c_{i}$finite-bit
symbol $\mathbf{s}_{3,i}$ Figure 1: Block diagram illustrating the overall
setup, shown here for the case with 3 agents, i.e., $K=3$.

The distributed MAB. There is a central learner, connected to each of the $K$
distributed agents, via a noiseless channel that is bit-constrained from the
agent to the learner. The learner and the agents work together to solve a
fixed confidence stochastic MAB problem consisting of $K$ arms. Agent
$i\in\\{1,\ldots,K\\}\triangleq[K]$ has access to arm $i$ of the MAB, which is
associated with a reward distribution $\nu_{i}$. We assume that the
distributions $\\{\nu_{i}\\}_{i=1}^{K}$ are $\sigma^{2}$-subgaussian111A
random variable $X$ is said to be $\sigma^{2}$-subgaussian if for any $t>0$,
$\mathbb{P}\left(|X-\mathbb{E}[X]|>t\right)\leq
2\exp\left(-t^{2}/2\sigma^{2}\right)$ and bounded on $[a,b]$. For $i\in[K]$,
let $\mu_{i}$ denote the mean of the distribution $\nu_{i}$ and $r_{i,t}$
denote the $t^{\text{th}}$ reward sample drawn from $\nu_{i}$. For each arm
$i$, $\\{r_{i,t}:t\geq 1\\}$ is an i.i.d. process; furthermore the reward
samples are independent across different arms. We also assume that arm 1 is
the best arm for notational convenience, i.e., $\mu_{1}\geq\mu_{i}$ where
$i\neq 1$. Also, define the suboptimality gaps $\Delta_{i}=\mu_{1}-\mu_{i}$
for $i\in[K]$.

The broad objective for the learner is to identify the arm with the highest
mean reward by sequentially selecting arms and sampling from their associated
reward distributions.

The communication model. Our communication model is summarized in Figure 1.
Communication between the learner and the agents happens in rounds. At the
beginning of (communication) round $i$, based on the information the learner
has seen till $i-1$, it broadcasts an action $c_{i}$ to all the $K$ agents,
where $c_{i}$ encodes the information about the actions to be taken by each
agent at round $i$. The agents respond to the learner after a fixed
synchronized duration and the learner updates its estimate of the best arm
based on the information it has received from the agents at round $i$. This
constitutes one round. Each agent communicates at most once in each round.

We assume that each agent is only capable of collecting samples from its
associated arm reward distribution, aggregating the information from the
samples it has seen so far and transmitting it to the central learner. The
agents cannot share information between each other and can communicate only
with the central learner. This is commonly the case with low-complexity and
resource-constrained devices such as drones and sensors. Moreover, they are
only allowed to use a finite number of bits for each transmission to the
learner. We assume that these transmissions are completed without any errors
or erasures. Note that we do not assume that communication from the learner to
the agents is bit-constrained and also do not put any computational
restrictions on it; this is true for several application settings and similar
assumptions are also common in the literature [17, 16, 12].

Performance metrics. We consider the _fixed confidence_ BAI problem for the
distributed MAB setting described above. The goal here is to find _sound_
strategies that find the optimal arm in a finite number of rounds for a given
confidence level $\delta$. Formally, if the strategy stops after using
$\tau_{\delta}$ samples and outputs arm $J_{\tau_{\delta}}$, a sound strategy
ensures that $\mathbb{P}(\tau_{\delta}<\infty,J_{\tau_{\delta}}\neq
1)\leq\delta$. Since we are dealing with a communication-constrained setting,
we also use the metrics of _(communication) round complexity_
$\tau_{r,\delta}$ (the number of communication rounds needed) and
_communication complexity_ $B_{\delta}$ (the total number of bits used by the
algorithm) to study the performance of any sound strategy.

An online learning algorithm for this distributed MAB setup has the following
components: (1) a sampling rule at the learner that at each time considers the
history of communicated messages received from the agents thus far, and
prescribes the arm(s) to be pulled in the next round; (2) a communication rule
at each agent that prescribes the rounds at which the agent will communicate
with the learner and also specifies the content of the message; (3) a stopping
rule at the learner that specifies when the learner will stop sampling arms
any further; and (4) a recommendation rule at the learner that specifies its
estimate for the best arm after the algorithm terminates.

Objective. We develop learning algorithms for the distributed MAB setting
outlined above where the agents need to limit the amount of communication with
the learner. This is done via restricting both the frequency of communication
(in terms of rounds) as well as the sizes of the messages exchanged (in terms
of bits). Using too little communication can of course lead to a large penalty
in terms of the sample complexity, and therein lies the main technical
challenge of designing communication and quantization strategies which can
effectively navigate this trade-off.

In the following sections, we propose a class of policies parameterized by the
frequency of communication and the number of bits used in each message, and
then explicitly characterize the impact of these parameters on the sample
complexity.

##  4 Proposed quantization scheme and algorithm

This section is devoted to the description of our proposed quantization scheme
_Inflating Confidence for Quantization_ (ICQ) and its application to
Successive Elimination as ICQ-SE. Algorithm 1 describes the actions to be
taken by the learner while Algorithm 2 describes the agent operation
(definitions of the additional notation involved can be found in (1), (4) and
(5)). We provide more details below.

Algorithm 1 ICQ-SE algorithm (learner-side)

1:procedure ICQ-SE-learner($K,\delta,B,\\{b_{i}\\}$)

2: Let $S\leftarrow\\{1,\ldots,K\\}$

3: For $1\leq j\leq K$, let $\tilde{\mu}_{j,0}$ be sampled uniformly from
$[a,b]$

4: for $1\leq i<\infty$ do

5: for $j\in S$ do

6: Instruct agent $j$ to sample $b_{i}$ times

7: Receive quantized value $\mathbf{s}_{j,i}$ from agent $j$

8: $L_{i,j}\leftarrow[\operatorname*{LCB}(j,i-1,\delta)-U^{\prime}(i,\delta),\
\operatorname*{UCB}(j,i-1,\delta)+U^{\prime}(i,\delta)]$

9: Decode $\tilde{\mu}_{j,i}=\mathsf{dec}(\mathbf{s}_{j,i},B,L_{i,j})$

10: end for

11: $S\leftarrow S\setminus\\{m\in
S:\underset{j\in[K]}{\max}\operatorname*{LCB}(j,i,\delta)\geq\operatorname*{UCB}(m,i,\delta)\\}$

12: STOP if $|S|=1$

13: end for

14: return only element in $S$

15:end procedure

Algorithm 2 ICQ-SE algorithm (agent-side)

1:procedure ICQ-SE-agentj($\delta,B,i,\tilde{\mu}_{j,i-1}$)

2: Pull arm $j$ $b_{i}$ times

3: $L_{i,j}\leftarrow[\operatorname*{LCB}(j,i-1,\delta)-U^{\prime}(i,\delta),\
\operatorname*{UCB}(j,i-1,\delta)+U^{\prime}(i,\delta)]$

4: Send $\mathbf{s}_{j,i}=\mathsf{enc}(\hat{\mu}_{j,i},B,L_{i,j})$

5: return quantized value $\mathbf{s}_{j,i}$

6:end procedure

Successive Elimination. The broad idea behind the _Successive Elimination_
(SE) framework [1] for a classical MAB setting (where there is only a learner
observing full-precision rewards and no intermediate agents) is to
characterize high-confidence bounds for the means of the distributions of each
arm. One derives confidence widths $U^{\prime}(i,\delta)$ such that the
empirical mean $\hat{\mu}_{j,i}$ of arm $j$ at round $i$ lies in the interval
$[\hat{\mu}_{j,i}-U^{\prime}(i,\delta),\hat{\mu}_{j,i}+U^{\prime}(i,\delta)]$
around the actual mean $\mu_{j}$ with a ‘high’ probability (we make this
formal later). The upper limit is called the Upper Confidence Bound (UCB) and
the lower limit is called the Lower Confidence Bound (LCB). The learner
constantly keeps track of a set $S$ of _active arms_ , i.e., the set of arms
still in contention to be the best arm. The set $S$ is initialized to be the
set of all arms $[K]$. At the end of a round, if the UCB of any arm $k$ lies
below the LCB of any other arm $j$, then arm $k$ is removed from the active
set. Thus, under the high probability event that these confidence bounds
contain the actual reward means, removing arms whose UCBs lie below the LCB of
some other arm would guarantee that the algorithm is removing only suboptimal
arms. The algorithm makes a mistake only when these high probability events do
not occur.

High-level description of the algorithm. In our setting, the learner no longer
has access to full-precision rewards, and instead receives quantized estimates
from the agents associated with each arm. In line with the SE framework, we
also refer to the agents corresponding to the active arms as _active agents_.
As we would like to reduce the number of bits used, it is inefficient for the
agent to communicate each sample that it sees. We thus consider a batched
approach that ensures that communication happens in a sparse manner. The
learner pulls active arms (through the agents) in batches; in particular,
during (communication) round $i$, the agents pull and observe rewards from
their associated arms $b_{i}$ times before sending (a summary of) the results
to the learner. We also define $t_{i}$ to be the cumulative sum of arm pulls
for each active arm till round $i$, i.e., $t_{i}=\sum_{j=1}^{i}b_{j}$. We show
our results for an _exponentially-sparse_ communication framework similar to
[18], i.e., $t_{i}=\alpha^{i}$ for some $\alpha>1$.

At the beginning of round $i$, the learner instructs each agent in $S$, the
set of active agents, to sample from their associated reward distributions
$b_{i}$ times. At the end of round $i$, each active agent must have made a
total of $t_{i}$ cumulative arm pulls and sends to the learner a quantized
estimate of the empirical mean of the rewards obtained. The learner first
decodes the quantized estimate, then decides which arms will remain in the
active set using the SE framework. This update requires defining new
confidence intervals that account for quantization; details will be provided
later. This marks the end of a communication round. The algorithm terminates
when there is only one arm left in the active set, which is the recommended
arm. Before describing the working of the algorithm in more detail, it is
instructive to look at the quantization part separately.

Quantization scheme. Each agent calculates the empirical mean of the observed
rewards, which must first be quantized and encoded into a bit string to be
sent over the bit-constrained channel. Similarly, at the learner, we must be
able to obtain a decoded estimate of the empirical mean from the encoded bit
string. This is achieved as follows. We first fix an interval that we ‘expect’
the empirical mean to belong to with high probability (this will become clear
later), divide it into $2^{B}$ equal bins, then transmit a bit string that
will be decoded at the learner as the midpoint of the bin. We formalize this
below.

Let $[\alpha,\beta]$ be the ‘expected’ real interval as described above.
First, divide $[\alpha,\beta]$ into $2^{B}$ bins of equal width
$\frac{\beta-\alpha}{2^{B}}$, and associate with the midpoint of each bin, a
$B$-length bit string. Then, the encoder $\mathsf{enc}(x,B,[\alpha,\beta])$
returns the bit string $\mathbf{s}$ associated with its nearest bin midpoint
(even if $x\notin[\alpha,\beta]$), and the decoder
$\mathsf{dec}(\mathbf{s},B,[\alpha,\beta])$ returns the midpoint (a real
number in $[\alpha,\beta]$) corresponding to the bit string $\mathbf{s}$. We
may simply refer to them as $\mathsf{enc}(x)$ and $\mathsf{dec}(\mathbf{s})$
when $B$ and the interval are clear from context. The quantization scheme is
summarized in Figure 2. Note that this quantization scheme uses $B$ bits for
each transmission. Another point to note is that if $x\in[\alpha,\beta]$, the
quantization error between $x$ and the decoded quantized value
$\mathsf{dec}(\mathsf{enc}(x))$ is at most $\frac{\beta-\alpha}{2\cdot
2^{B}}$, i.e., if $x$ is known to lie within the interval, then the
quantization error is at most a factor of $\frac{1}{2^{B+1}}$ times the width
of the interval.

$\mathbb{R}$$\beta$$\alpha$$\ell_{0}$$\ell_{1}$$\ell_{2}$$\ell_{3}$$\ell_{4}$$\ell_{5}$$\ell_{6}$$\ell_{7}$$\ell_{8}$000001010011100101110111$\times$$\times$$\times$
Figure 2: Illustration of the quantization scheme when $B=3$ — the blue lines
given by $\ell_{i}$ mark the separation between the $2^{B}$ equal bins, the
red points denote the midpoints of these bins, and the green ‘$\times$’s (the
values to be quantized) get mapped to their nearest midpoints.

Details of the algorithm. At round $i$, consider the agent $j\in[K]$ making
its $k$th cumulative arm pull, where $1\leq k\leq t_{i}$. It observes a reward
$r_{j,k}$. At the end of this round, it calculates the empirical mean of the
rewards from arm $j$ observed over all rounds upto and including round $i$,
$\hat{\mu}_{j,i}=\frac{1}{t_{i}}\sum_{k=1}^{t_{i}}r_{j,k}$. By defining the
confidence width

$U^{\prime}(i,\delta)=\sigma\sqrt{\frac{2\log(4Kt_{i}^{2}/\delta)}{t_{i}}},$
(1)

for each round $i$ and arbitrary $\delta>0$, it can be shown (as in the proof
of Lemma 3) from the subgaussian concentration inequality [13] and a union
bound that

$\mathbb{P}\left(\cup_{i\geq
1}\cup_{j\in[K]}|\hat{\mu}_{j,i}-\mu_{j}|>U^{\prime}(i,\delta)\right)\leq\delta.$
(2)

Thus, at any round $i$, the actual mean of arm $j$ lies in the interval
$[\hat{\mu}_{j,i}-U^{\prime}(i,\delta),\hat{\mu}_{j,i}+U^{\prime}(i,\delta)]$
w.h.p. However, since the communication channel is bit-constrained, the agents
cannot simply transmit the infinite precision real number $\hat{\mu}_{j,i}$ as
is — they instead transmit a quantized version of $\hat{\mu}_{j,i}$ as
described above. Let $\tilde{\mu}_{j,i}$ be the decoded estimate of the mean
of arm $j$ that the learner recovers at the end of round $i$, i.e.,
$\tilde{\mu}_{j,i}=\mathsf{dec}(\mathsf{enc}(\hat{\mu}_{j,i}))$.

To account for the potential increase in error due to the quantization
necessitated by the bit-constrained channel, we introduce a slack in the
confidence interval through a different confidence width $U(i,\delta)$. The
goal is to obtain a concentration bound for $\tilde{\mu}_{j,i}-\mu_{j}$ in
terms of $U(i,\delta)$, in a form similar to (2). We now provide an intuitive
explanation to motivate an expression of $U(i,\delta)$ that achieves exactly
this. (Note that this is not meant to be a proof; that this does indeed work
will be shown in Section 5). First note that a straightforward application of
the triangle inequality gives

$|\tilde{\mu}_{j,i}-\mu_{j}|\leq|\tilde{\mu}_{j,i}-\hat{\mu}_{j,i}|+|\hat{\mu}_{j,i}-\mu_{j}|.$
(3)

The first term corresponds to the quantization error and the second term
corresponds to the error in the empirical mean itself. An interval in which
the latter lies w.h.p. is taken care of by the bound (2), so it is enough to
establish such an interval for the quantization error. Recall from the
‘Quantization scheme’ description before Figure 2 that the quantization error
is at most $\frac{1}{2^{B+1}}$ times the width of the interval if the
empirical mean $\hat{\mu}_{j,i}$ is known to originally lie in the interval.
Thus, our task is to find an appropriate interval in which $\hat{\mu}_{j,i}$
lies w.h.p. to perform the quantization.

As the latest estimate of the mean that the learner has access to at the
beginning of round $i$ is the quantized estimate at round $i-1$, i.e.,
$\tilde{\mu}_{j,i-1}$, we construct the interval to be centered around
$\tilde{\mu}_{j,i-1}$. We also want that this interval contain the new
empirical mean at round $i$, i.e., $\hat{\mu}_{j,i}$, w.h.p. We now find a
recursive expression for $U(i,\delta)$ that inductively satisfies these
properties. We first make the inductive assumption that $\tilde{\mu}_{j,i-1}$
lies in $[\mu_{j}-U(i-1,\delta),\mu_{j}+U(i-1,\delta)]$ w.h.p. Combined with
the knowledge that $\hat{\mu}_{j,i}$ lies in
$[\mu_{j}-U^{\prime}(i,\delta),\mu_{j}+U^{\prime}(i,\delta)]$ w.h.p. from (2),
we have that the interval
$[\tilde{\mu}_{j,i-1}-U^{\prime}(i,\delta)-U(i-1,\delta),\tilde{\mu}_{j,i-1}+U^{\prime}(i,\delta)+U(i-1,\delta)]$
contains $\hat{\mu}_{j,i}$ w.h.p. This is illustrated in Figure 3. Note that
we have found an interval that we ‘expect’ the empirical mean to belong to, as
promised when defining the quantization scheme relative to an interval. Thus,
we perform the quantization over an interval of width
$2[U^{\prime}(i,\delta)+U(i-1,\delta)]$ centered at $\tilde{\mu}_{j,i-1}$, and
hence, the quantization error is at most
$\frac{1}{2^{B}}[U^{\prime}(i,\delta)+U(i-1,\delta)]$.

$\mathbb{R}$$\tilde{\mu}_{j,i-1}$$\operatorname*{UCB}(j,i-1,\delta)$$\operatorname*{LCB}(j,i-1,\delta)$$U(i-1,\delta)$$U(i-1,\delta)$$\mu_{j}$$U^{\prime}(i,\delta)$$U^{\prime}(i,\delta)$
$\hat{\mu}_{j,i}$ guaranteed to be here given this position of $\mu_{j}$
$U^{\prime}(i,\delta)$$U^{\prime}(i,\delta)$$\hat{\mu}_{j,i}$ guaranteed to be
here in general, relative to $\tilde{\mu}_{j,i-1}$ Figure 3: Motivation for
defining $U(i,\delta)$ as (4) – Start with $\tilde{\mu}_{j,i-1}$, then by the
inductive hypothesis, $\mu_{j}$ should lie within $U(i-1,\delta)$ of
$\tilde{\mu}_{j,i-1}$ (blue interval). From (2), $\hat{\mu}_{j,i}$ lies within
$U^{\prime}(i,\delta)$ of $\mu_{j}$ (red interval). Putting them together,
$\hat{\mu}_{j,i}$ lies within $U(i-1,\delta)+U^{\prime}(i,\delta)$ of
$\tilde{\mu}_{j,i-1}$.

Motivated by the above and (3), define, for $i\geq 1,j\in[K]$,

$\displaystyle U(i,\delta)$
$\displaystyle=\frac{1}{2^{B}}\left[U^{\prime}(i,\delta)+U(i-1,\delta)\right]+U^{\prime}(i,\delta),$
(4)

where we set $U(0,\delta)=b-a$ to ensure that the induction hypothesis
(namely, that $\tilde{\mu}_{j,i-1}$ satisfies its confidence bounds) holds for
the index $i-1=0$. Now that we have an appropriate confidence width
$U(i,\delta)$ that we expect (heuristically, from the above discussion; this
will be proved in Section 5) to provide a similar confidence bound for
$\tilde{\mu}_{j,i}$ as (2) does for $\hat{\mu}_{j,i}$, we define the
appropriate LCB and UCB for our algorithm, as

$\begin{split}\operatorname*{LCB}(j,i,\delta)&=\tilde{\mu}_{j,i}-U(i,\delta),\\\
\operatorname*{UCB}(j,i,\delta)&=\tilde{\mu}_{j,i}+U(i,\delta).\end{split}$
(5)

##  5 Analysis of the ICQ-SE algorithm

The following result can be shown for the sample complexity of SE run on the
distributed MAB setup outlined above if the channel from the agent to the
learner is not bit-constrained:

######  Theorem 1.

SE is a sound algorithm. Moreover, with probability at least $1-\delta$, it
successfully identifies the best arm using at most

$\displaystyle\mathcal{O}\left(\sum_{j\neq
1}\frac{102\alpha\sigma^{2}}{\Delta_{j}^{2}}\ln\left(\frac{64\sigma^{2}\sqrt{4K\delta}}{\Delta_{j}^{2}}\right)+1\right)$

samples.

We now show that ICQ-SE is a sound algorithm and also analyze its sample
complexity. We restrict our attention to ICQ-SE just to provide concrete
results, but a similar analysis can be carried out for other confidence bound-
based algorithms as well (see Remark 1). We do so by a sequence of lemmas and
theorems, similar to a standard analysis of Successive Elimination-type
algorithms, such as in [1] and [18]. The main novelties in our work are Lemma
2 and Theorem 6, where we relate the confidence intervals $U(i,\delta)$ and
$U^{\prime}(i,\delta)$ at the agents and the learner respectively, thereby
allowing us to prove similar results as for vanilla Successive Elimination.
Proofs of all lemmas and theorems stated below can be found in the Appendix.

Recall that $\mu_{j}$ is the mean of arm $j\in[K]$, $\hat{\mu}_{j,i}$ is the
empirical mean of arm $j$ at round $i$ at the agent (which will then be
encoded and sent to the learner), and $\tilde{\mu}_{j,i}$ is the decoded
estimate of the mean of arm $j$ at round $i$ at the learner. Note that the
only concentration bound we know about these quantities a priori is (2), which
relates $\hat{\mu}_{j,i}$ and $U^{\prime}(i,\delta)$. The learner, however,
observes $\tilde{\mu}_{j,i}$ and constructs confidence intervals of width
$U(i,\delta)$. Our goal is for the learner to be able to identify w.h.p. the
best arm in $[K]$. To this end, it is desirable to have a concentration bound
on the quantities available at the learner, namely, $\tilde{\mu}_{j,i}$ and
$U(i,\delta)$.

Lemma 2 below relates the following — (1) the event that in some round $i$
(hence the union over rounds), the estimated mean of arm $j$,
$\hat{\mu}_{j,i}$, falls outside the confidence interval of width
$U^{\prime}(i,\delta)$ centered about the true mean $\mu_{j}$, and (2) the
identical event at the learner, except with the decoded mean
$\tilde{\mu}_{j,i}$ and confidence width $U(i,\delta)$.

######  Lemma 2.

For all arms $1\leq j\leq K$, and any $\delta>0$,

$\displaystyle\bigcup_{i=1}^{\infty}\left\\{|\tilde{\mu}_{j,i}-\mu_{j}|>U(i,\delta)\right\\}\subseteq\bigcup_{i=1}^{\infty}\left\\{|\hat{\mu}_{j,i}-\mu_{j}|>U^{\prime}(i,\delta)\right\\}.$

Using Lemma 2, we obtain the desired confidence bound on the decoded means at
the learner, stated formally below.

######  Lemma 3.

For any $\delta>0$, define the event

$\mathcal{E}:=\bigcup_{j=1}^{K}\bigcup_{i=1}^{\infty}\left\\{|\tilde{\mu}_{j,i}-\mu_{j}|>U(i,\delta)\right\\},$

then $\mathbb{P}\left(\mathcal{E}\right)\leq\delta$.

The above lemma establishes that the event $\mathcal{E}^{c}$, wherein for each
arm $j$ and at every round $i$, the decoded estimate at the learner
$\hat{\mu}_{j,i}$ is sufficiently close to the actual mean $\mu_{j}$, occurs
with large probability. It then follows that with high probability, any arm
that is eliminated during the successive elimination procedure must be
suboptimal, as stated in Theorem 4. We now show that ICQ-SE is a sound
algorithm and provide an upper bound for its sample complexity in the
exponentially sparse regime (i.e., with $t_{i}=\alpha^{i}$) in Theorem 6.

######  Theorem 4.

With probability $\geq 1-\delta$, the best arm remains in the active set S
until termination.

To prove our main result in Theorem 6, we require a technical lemma that
relates the confidence widths $U(i,\delta)$ and $U^{\prime}(i,\delta)$.

######  Lemma 5.

Consider $B\geq 1$ and let $t_{i}=\alpha^{i}$ where $\alpha\in\mathbb{N}$ such
that $\alpha<2^{2B}$. Then for $i\geq 1$,

$\displaystyle U(i,\delta)\leq 2c\,U^{\prime}(i,\delta),$

where

$\displaystyle
c=\left(1+\frac{2}{2^{B}}\right)\frac{2^{B}}{2^{B}-\sqrt{\alpha}}.$

######  Theorem 6.

Consider $B\geq 1$ and let $t_{i}=\alpha^{i}$ where $\alpha\in\mathbb{N}$ and
$1<\alpha<2^{2B}$. With probability at least $1-\delta$, ICQ-SE will terminate
and successfully identify the best arm after using

$\displaystyle\mathcal{O}\left(\sum_{j\neq 1}\frac{410\alpha
c^{2}\sigma^{2}}{\Delta_{j}^{2}}\ln\left(\frac{256c^{2}\sigma^{2}\sqrt{4K\delta}}{\Delta_{j}^{2}}\right)+1\right)$

samples,

$\displaystyle\mathcal{O}\left(\sum_{j\neq
1}\log_{\alpha}\left(\frac{410\alpha
c^{2}\sigma^{2}}{\Delta_{j}^{2}}\ln\left(\frac{256c^{2}\sigma^{2}\sqrt{4K\delta}}{\Delta_{j}^{2}}\right)+1\right)\right)$

rounds, and

$\displaystyle\mathcal{O}\left(B\sum_{j\neq
1}\log_{\alpha}\left(\frac{410\alpha
c^{2}\sigma^{2}}{\Delta_{j}^{2}}\ln\left(\frac{256c^{2}\sigma^{2}\sqrt{4K\delta}}{\Delta_{j}^{2}}\right)+1\right)\right)$

bits, where $c$ is as defined in Lemma 5.

Comparing Theorem 6 with the equivalent result for Successive Elimination with
no quantization in Theorem 1, we see that the upper bound for the sample
complexity is worse only by a constant factor, i.e., we have order-optimal
performance.

Additionally, note that $c$ depends on the choice of $B$ and $\alpha$, and in
fact decreases as $B$ and $\alpha$ increase. Combined with the upper bound on
sample complexity in Theorem 6, we thus see a trade-off between the
performance of the algorithm and the number of bits that it is allowed to use.
In addition to the above theoretical result, we also investigate this trade-
off via numerical simulations in Section 6.

######  Remark 1.

The quantization scheme ICQ can in fact be used for any other algorithm that
uses confidence bounds, such as LUCB [10] and lil’UCB [11], to obtain
algorithms ICQ-LUCB and ICQ-lil’UCB. This is because the crux of this scheme
is the recursive definition for $U(\cdot,\cdot)$ that we obtain by separating
the quantization error and the error in the empirical mean itself, via (3). A
similar analysis can be carried out for ICQ-LUCB and ICQ-lil’UCB too, that we
omit here for brevity.

######  Remark 2.

We use the boundedness of the rewards only in the definition of $U(0,\delta)$.
Recall that the algorithm proceeds with an initial random guess for the mean
of each arm $\\{\tilde{\mu}_{j,0}\\}_{j=1}^{K}$. As $U(i,\delta)$ is defined
in a recursive fashion, for the induction in the proof of Lemma 2 to hold,
$U(0,\delta)$ needs to be such that $\\{\tilde{\mu}_{j,0}\\}_{j=1}^{K}$ are
good guesses for the actual means with high probability satisfying Lemma 2.
For $[a,b]$-bounded rewards, this holds trivially by taking
$U(0,\delta)=(b-a)$, as
$\left\\{|\tilde{\mu}_{j,0}-\mu_{j}|>U(0,\delta)\right\\}=\left\\{|\tilde{\mu}_{j,0}-\mu_{j}|>(b-a)\right\\}=\emptyset$.
For unbounded rewards, however, we can no longer use a constant number of bits
in each round. Specifically, in round 1, it is not possible to obtain a high-
probability guess for the mean by using a bounded number of bits. Nonetheless,
we can use a different quantization scheme just for the first round to ensure
that the quantization error is bounded. The problem is then reduced to that
with bounded rewards from round 2, whence we can use ICQ-SE as is. In Section
6, we demonstrate this on Gaussian rewards by running QuBan [12] (designed for
unbounded rewards) in the first round.

##  6 Numerical experiments

In this section, we present results of numerical experiments comparing the
performance of ICQ-SE with other quantization algorithms proposed for multi-
armed bandits in the literature. In addition to the unquantized setting as a
baseline, we compare ICQ-SE with the quantization schemes QuBan [12] and Fed-
SEL [17]. Each of these schemes is implemented on top of the same batched
Successive Elimination algorithm that ICQ-SE uses to highlight the difference
between the quantization schemes. The algorithms are compared based on their
(expected) sample complexity $E\left[\tau_{\delta}\right]$, (expected) round
complexity $E\left[\tau_{r,\delta}\right]$ and (expected) communication
complexity $E\left[B_{\delta}\right]$. In all our experiments, the performance
of each algorithm was averaged over 4000 iterations.

QuBan [12] was proposed for the regret minimization setting where each sample
that the agent observes is quantized and sent to the learner. A key feature of
QuBan is that the agent uses shorter codewords to quantize samples close to
the current estimate of the mean at the learner, while reward samples which
are farther away are assigned longer codewords. This helps to minimize the
expected number of bits used at each round. While this is a sound approach, it
could result in a higher number of bits being used unnecessarily for our
framework. QuBan has a parameter $\epsilon>0$ that provides a trade-off
between the number of bits used and the performance of the algorithm (a
smaller value of $\epsilon$ provides a smaller regret using a higher number of
bits).

In Fed-SEL [17], in each round $i$, the entire interval $[a,b]$ is divided
into bins of length $U^{\prime}(i,\delta)$ and the empirical mean is quantized
to the midpoint of one of these bins. The main drawback of this approach is
that the number of bits used at each round is inversely proportional to the
confidence bound at each round, i.e., the number of bits used per round grows
with the number of rounds, making it hard to control the cumulative number of
bits that the algorithm uses.

The first set of experiments in Figures 5a, 5b, 5c, 5d and 5e analyze the
dependence of the performance of ICQ-SE on the parameters $\alpha$
(controlling the sparsity of communication) and $B$ (the number of bits in
each transmission). We consider a five-armed multi-armed bandit instance where
each arm is associated with a $\mathrm{Beta}(\gamma,1-\gamma)$ distribution,
with $\gamma$ generated uniformly at random from $[0,1]$. In Figures 5a and
5b, we observe that the number of communication rounds used by ICQ-SE to
converge decreases with $\alpha$ while the number of samples used increases
with $\alpha$. This is expected because increasing $\alpha$ results in sparser
communication between the agents and the learner reducing the round complexity
while the number of samples used increases. Figure 5c shows the dependence of
the cumulative number of bits used by the algorithm to converge (which we call
communication complexity) on $\alpha$. The decrease in the communication
complexity with $\alpha$ is a natural consequence of the decrease in the
communication round complexity.

Figures 4a, 4b, and 4c compare the performance of ICQ-SE, QuBan and Fed-SEL.
We consider a five-armed multi-armed bandit instance where each arm is
associated with a bounded support reward distribution, in particular the
$\mathrm{Beta}(\gamma,1-\gamma)$ distribution with $\gamma$ generated
uniformly at random from $[0,1]$. We observe that ICQ-SE with $B=3$ performs
comparably with QuBan ($\epsilon=0.5$), and better than QuBan ($\epsilon=2$)
and Fed-SEL in terms of sample and round complexity, while using a much lesser
number of bits than all of them.

In Figures 4d, 4e, and 4f, we compare the performance of ICQ-SE and QuBan when
the reward distributions associated with the arms are Gaussian (and hence
unbounded; recall Remark 2). We consider a five-armed multi-armed bandit
instance where each arm is associated with a Gaussian reward distribution of
standard deviation 0.125 whose means are generated uniformly at random from
the interval $[0,N]$, where $N$ is a sample drawn from a Gaussian distribution
$\mathcal{N}(0,9)$. We use QuBan with $\epsilon=2$ for the first round of ICQ-
SE as discussed in Remark 2. We again observe that ICQ-SE with $B=3$ performs
comparably with the others in terms of sample and round complexity while using
a much lesser number of bits. We make no comparison with Fed-SEL in this case
because it is unclear how to extend the scheme to unbounded rewards, since it
starts by dividing the finite-size reward range into bins of length
$U^{\prime}(i,\delta)$.

The final set of experiments in Figures 4g, 4h and 4i compare the dependence
of the performance of ICQ-SE and QuBan on the hardness of the underlying
bandit instance when the reward distributions associated with the arms are
Gaussian. We consider a five-armed multi-armed bandit instance where each arm
is associated with a Gaussian distribution of standard deviation 0.125. Four
of the arms have mean 0 and the remaining arm has mean $\Delta\in[0,1]$. A
lower $\Delta$ implies that the mean of the optimal arm is closer to that of
the non-optimal arms, resulting in a harder instance. As expected, the
performance of all the algorithms improves as the hardness of the instance
decreases. Moreover, we see the same trend with ICQ-SE ($B=3$) as earlier,
especially on the harder instances.

Finally, in Figure 5, we also numerically analyze the impact of varying
$\alpha$ (controlling the sparsity of communication) and $B$ (the number of
bits in each transmission) on the performance of ICQ-SE.

$4$$6$$8$$10$$12$$14$$8$$10$$12$$\displaystyle\log(1/\delta)$Round
complexityQuBan ($\epsilon=2$)QuBan ($\epsilon=0.5$)Fed-SELICQ-SE ($B=2$)ICQ-
SE ($B=3$)Unquantized SE

(a)

$4$$6$$8$$10$$12$$14$$0$$1{,}000$$2{,}000$$3{,}000$$4{,}000$$\displaystyle\log(1/\delta)$Sample
complexityQuBan ($\epsilon=2$)QuBan ($\epsilon=0.5$)Fed-SELICQ-SE ($B=2$)ICQ-
SE ($B=3$)Unquantized SE

(b)

$4$$6$$8$$10$$12$$14$$100$$150$$200$$\displaystyle\log(1/\delta)$Communication
complexity#bits for QuBan ($\epsilon=2$)#bits for QuBan ($\epsilon=0.5$)#bits
for Fed-SEL#bits for ICQ-SE ($B=2$)#bits for ICQ-SE ($B=3$)

(c)

$4$$6$$8$$10$$12$$14$$3$$4$$5$$6$$7$$8$$\displaystyle\log(1/\delta)$Round
complexityQuBan ($\epsilon=2$)QuBan ($\epsilon=0.5$)ICQ-SE ($B=2$)ICQ-SE
($B=3$)Unquantized SE

(d)

$4$$6$$8$$10$$12$$14$$0$$50$$100$$150$$200$$\displaystyle\log(1/\delta)$Sample
complexityQuBan ($\epsilon=2$)QuBan ($\epsilon=0.5$)ICQ-SE ($B=2$)ICQ-SE
($B=3$)Unquantized SE

(e)

$4$$6$$8$$10$$12$$14$$40$$50$$60$$70$$80$$\displaystyle\log(1/\delta)$Communication
complexity#bits for QuBan ($\epsilon=2$)#bits for QuBan ($\epsilon=0.5$)#bits
for ICQ-SE ($B=2$)#bits for ICQ-SE ($B=3$)

(f)

$0.2$$0.4$$0.6$$0.8$$1$$2$$4$$6$$8$$10$$12$$\displaystyle\Delta$Round
complexityQuBan ($\epsilon=2$)QuBan ($\epsilon=0.5$)ICQ-SE ($B=2$)ICQ-SE
($B=3$)Unquantized SE

(g)

$0.2$$0.4$$0.6$$0.8$$1$$0$$0.2$$0.4$$0.6$$0.8$$1$$\cdot
10^{4}$$\displaystyle\Delta$Sample complexityQuBan ($\epsilon=2$)QuBan
($\epsilon=0.5$)ICQ-SE ($B=2$)ICQ-SE ($B=3$)Unquantized SE

(h)

$0.2$$0.4$$0.6$$0.8$$1$$50$$100$$150$$\displaystyle\Delta$Communication
complexity#bits for QuBan ($\epsilon=2$)#bits for QuBan ($\epsilon=0.5$)#bits
for ICQ-SE ($B=2$)#bits for ICQ-SE ($B=3$)

(i)

Figure 4: Figures 5a, 5b and 5c demonstrate the dependence of the performance
of ICQ-SE on $\alpha$. Figures 5d and 5e demonstrate the dependence on
$\beta$. Figures 4a, 4b and 4c compare ICQ-SE with QuBan [12] and Fed-SEL [17]
for bounded rewards while Figures 4d, 4e and 4f compare ICQ-SE with QuBan for
unbounded rewards. Finally, Figures 4g, 4h and 4i compare the dependence of
ICQ-SE and QuBan on the hardness of the underlying instance.

$2$$4$$6$$8$$5$$6$$7$$8$$9$$10$$\displaystyle\alpha$Communication round
complexity

(a)

$2$$4$$6$$8$$0$$0.5$$1$$1.5$$2$$\cdot 10^{5}$$\displaystyle\alpha$Sample
complexity

(b)

$2$$4$$6$$8$$25$$30$$35$$40$$45$$\displaystyle\alpha$Communication complexity

(c)

$2$$4$$6$$8$$6$$7$$8$$9$$10$$\displaystyle B$Communication round complexity

(d)

$2$$4$$6$$8$$0$$1{,}000$$2{,}000$$3{,}000$$4{,}000$$5{,}000$$\displaystyle
B$Sample complexity

(e)

Figure 5: Figures 5a, 5b and 5c demonstrate the dependence of the performance
of ICQ-SE on $\alpha$. Figures 5d and 5e demonstrate the dependence on
$\beta$.

##  7 Conclusion

We propose ICQ, a novel quantization scheme for the distributed best-arm
identification problem where the learner does not have access to full-
precision rewards, and analyze ICQ-SE, which is the application of ICQ to the
Successive Elimination algorithm for this setting. Future lines of work
include: (1) using a variable-length and adaptive quantization scheme in each
round to reduce the communication complexity; for example, a Lloyd-Max
quantizer based on the empirical distribution, (2) characterizing a lower
bound on the communication complexity required to ensure a certain
sample/round complexity, and (3) developing quantization schemes for the fixed
budget variant of the best-arm identification problem.

## References

  * [1] E. Even-Dar, S. Mannor, and Y. Mansour, “PAC bounds for multi-armed bandit and markov decision processes,” in _Computational Learning Theory_. Springer, 2002.
  * [2] J. Audibert, S. Bubeck, and R. Munos, “Best arm identification in multi-armed bandits,” in _COLT_ , 2010.
  * [3] K. Jamieson and R. Nowak, “Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting,” in _CISS_ , 2014.
  * [4] S. Bubeck, R. Munos, and G. Stoltz, “Pure exploration in finitely-armed and continuous-armed bandits,” _Theoretical Computer Science_ , 2011.
  * [5] P. Dames, P. Tokekar, and V. Kumar, “Detecting, localizing, and tracking an unknown number of moving targets using a team of mobile robots,” _The International Journal of Robotics Research_ , 2017.
  * [6] V. Savic, H. Wymeersch, and S. Zazo, “Belief consensus algorithms for fast distributed target tracking in wireless sensor networks,” _Signal Processing_ , 2014.
  * [7] L. Song, C. Fragouli, and D. Shah, “Recommender systems over wireless: Challenges and opportunities,” in _IEEE Information Theory Workshop (ITW)_ , 2018.
  * [8] K. Ding, J. Li, and H. Liu, “Interactive anomaly detection on attributed networks,” in _Proceedings of the 12th ACM international conference on web search and data mining (WSDM)_ , 2019.
  * [9] V. Gandikota, D. Kane, R. K. Maity, and A. Mazumdar, “vqSGD: Vector quantized stochastic gradient descent,” _IEEE Transactions on Information Theory_ , 2022.
  * [10] S. Kalyanakrishnan, A. Tewari, P. Auer, and P. Stone, “PAC subset selection in stochastic multi-armed bandits.” in _ICML_ , 2012.
  * [11] K. Jamieson, M. Malloy, R. Nowak, and S. Bubeck, “lil’ucb: An optimal exploration algorithm for multi-armed bandits,” in _COLT_. PMLR, 2014.
  * [12] 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\.
  * [13] T. Lattimore and C. Szepesvári, _Bandit algorithms_. Cambridge University Press, 2020.
  * [14] A. Garivier and E. Kaufmann, “Optimal best arm identification with fixed confidence,” in _COLT_. PMLR, 2016\.
  * [15] C. Shi and C. Shen, “Federated multi-armed bandits,” _Proceedings of the AAAI Conference on Artificial Intelligence_ , May 2021.
  * [16] A. Mitra, H. Hassani, and G. J. Pappas, “Linear stochastic bandits over a bit-constrained channel,” 2022. [Online]. Available: https://arxiv.org/abs/2203.01198
  * [17] A. Mitra, H. Hassani, and G. Pappas, “Exploiting heterogeneity in robust federated best-arm identification,” 2021. [Online]. Available: https://arxiv.org/abs/2109.05700
  * [18] K. S. Reddy, P. N. Karthik, and V. Y. F. Tan, “Almost cost-free communication in federated best arm identification,” _AAAI (to appear)_ , 2023. [Online]. Available: https://arxiv.org/abs/2208.09215
  * [19] F. Alzahrani and A. Salem, “Sharp bounds for the Lambert W function,” _Integral Transforms and Special Functions_ , 2018.

##  Appendix A Proofs

###### Proof of Lemma 2.

We wish to show that for all arms $1\leq j\leq K$ and any $\delta>0$,

$\displaystyle\bigcup_{i=1}^{\infty}\left\\{|\tilde{\mu}_{j,i}-\mu_{j}|>U(i,\delta)\right\\}\subseteq\bigcup_{i=1}^{\infty}\left\\{|\hat{\mu}_{j,i}-\mu_{j}|>U^{\prime}(i,\delta)\right\\}.$

First observe that the sets on the left-hand side are empty when $i=0$, as

$\displaystyle\left\\{|\tilde{\mu}_{j,0}-\mu_{j}|>U(0,\delta)\right\\}=\left\\{|\tilde{\mu}_{j,0}-\mu_{j}|>(b-a)\right\\}=\emptyset,$
(6)

so it is sufficient to show that

$\displaystyle\bigcup_{i=0}^{\infty}\left\\{|\tilde{\mu}_{j,i}-\mu_{j}|>U(i,\delta)\right\\}\subseteq\bigcup_{i=1}^{\infty}\left\\{|\hat{\mu}_{j,i}-\mu_{j}|>U^{\prime}(i,\delta)\right\\}.$

We do so by instead proving the following equivalent statement — for each
$0\leq i<\infty$,

$\left\\{|\tilde{\mu}_{j,i}-\mu_{j}|>U(i,\delta)\right\\}\subseteq\bigcup_{k=1}^{\infty}\left\\{|\hat{\mu}_{j,k}-\mu_{j}|>U^{\prime}(k,\delta)\right\\}.$

The proof is by induction over $i$. The base case, $i=0$, holds trivially as
the left-hand side is $\emptyset$. Assume now that this property holds for
index $i-1\geq 0$, i.e.,

$\left\\{|\tilde{\mu}_{j,i-1}-\mu_{j}|>U(i-1,\delta)\right\\}\subseteq\bigcup_{k=1}^{\infty}\left\\{|\hat{\mu}_{j,k}-\mu_{j}|>U^{\prime}(k,\delta)\right\\}.$

Using (3) and (4) respectively, we have

$\displaystyle\left\\{|\tilde{\mu}_{j,i}-\mu_{j}|>U(i,\delta)\right\\}$
$\displaystyle\subseteq$
$\displaystyle\left\\{|\tilde{\mu}_{j,i}-\hat{\mu}_{j,i}|+|\hat{\mu}_{j,i}-\mu_{j}|>U(i,\delta)\right\\},$
$\displaystyle\subseteq$
$\displaystyle\left\\{|\hat{\mu}_{j,i}-\mu_{j}|>U^{\prime}(i,\delta)\right\\}\cup$
$\displaystyle\left\\{|\tilde{\mu}_{j,i}-\hat{\mu}_{j,i}|>\frac{1}{2^{B}}U^{\prime}(i,\delta)+\frac{1}{2^{B}}U(i-1,\delta)\right\\},$

where the second step follows as
$U(i,\delta)=U^{\prime}(i,\delta)+\frac{1}{2^{B}}U^{\prime}(i,\delta)+\frac{1}{2^{B}}U(i-1,\delta)$
and $a+b>x+y$ requires at least one of $a>x$ or $b>y$.

We now bound the second term in the union on the right-hand side. The
estimated mean is encoded using $\mathsf{enc}$ on the interval
$[\operatorname*{LCB}(j,i-1,\delta)-U^{\prime}(i,\delta),\operatorname*{UCB}(j,i-1,\delta)+U^{\prime}(i,\delta)]$.
As long as $\hat{\mu}_{j,i}$ lies in this interval, the learner can decode
$\tilde{\mu}_{j,i}$ to an error within $\frac{1}{2}\cdot\frac{1}{2^{B}}$ times
the width of this interval, given by
$2\left(U^{\prime}(i,\delta)+U(i-1,\delta)\right)$. Hence we have

$\displaystyle\left\\{|\tilde{\mu}_{j,i}-\hat{\mu}_{j,i}|>\frac{1}{2^{B}}U^{\prime}(i,\delta)+\frac{1}{2^{B}}U(i-1,\delta)\right\\}$
$\displaystyle\subseteq$
$\displaystyle\left\\{|\tilde{\mu}_{j,i-1}-\hat{\mu}_{j,i}|>U^{\prime}(i,\delta)+U(i-1,\delta)\right\\}$
$\displaystyle\subseteq$
$\displaystyle\left\\{|\tilde{\mu}_{j,i-1}-\mu_{j}|+|\hat{\mu}_{j,i}-\mu_{j}|>U^{\prime}(i,\delta)+U(i-1,\delta)\right\\}$
$\displaystyle\subseteq$
$\displaystyle\left\\{|\tilde{\mu}_{j,i-1}-\mu_{j}|>U(i-1,\delta)\right\\}\cup\left\\{|\hat{\mu}_{j,i}-\mu_{j}|>U^{\prime}(i,\delta)\right\\}$
$\displaystyle\subseteq$
$\displaystyle\bigcup_{k=1}^{\infty}\left\\{|\hat{\mu}_{j,k}-\mu_{j}|>U^{\prime}(k,\delta)\right\\},$
(7)

where the last step follows from the induction hypothesis. ∎

###### Proof of Lemma 3.

This follows easily by a union bound, as

$\displaystyle\mathbb{P}(\mathcal{E})$
$\displaystyle=\mathbb{P}\left(\bigcup_{j=1}^{K}\bigcup_{i=1}^{\infty}\left\\{|\tilde{\mu}_{j,i}-\mu_{j}|>U(i,\delta)\right\\}\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\mathbb{P}\left(\bigcup_{j=1}^{K}\bigcup_{i=1}^{\infty}\left\\{|\hat{\mu}_{j,i}-\mu_{j}|>U^{\prime}(i,\delta)\right\\}\right)$
$\displaystyle\leq\mathbb{P}\left(\bigcup_{j=1}^{K}\bigcup_{i=1}^{\infty}\left\\{|\hat{\mu}_{j,i}-\mu_{j}|>\sigma\sqrt{\frac{2\log(4Kt_{i}^{2}/\delta)}{t_{i}}}\right\\}\right)$
$\displaystyle\leq\sum_{j=1}^{K}\sum_{i=1}^{\infty}\mathbb{P}\left(\left|\frac{1}{t_{i}}\sum_{k=1}^{t_{i}}r_{j,k}-\mu_{j}\right|>\sigma\sqrt{\frac{2\log(4Kt_{i}^{2}/\delta)}{t_{i}}}\right)$
$\displaystyle\leq\sum_{j=1}^{K}\sum_{i=1}^{\infty}\mathbb{P}\left(\left|\frac{1}{t_{i}}\sum_{k=1}^{t_{i}}r_{j,k}-\mu_{j}\right|>\sigma\sqrt{\frac{2\log(4Kt_{i}^{2}/\delta)}{t_{i}}}\right)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\sum_{j=1}^{K}\sum_{i=1}^{\infty}2\exp\left(-\log(4Kt_{i}^{2}/\delta)\right)=\sum_{j=1}^{K}\sum_{i=1}^{\infty}2\left(\frac{\delta}{4Kt_{i}^{2}}\right)$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{<}}\sum_{j=1}^{K}\frac{\delta}{K}=\delta,$

where (a) follows from Lemma 2, (b) from the definition of
$\sigma^{2}$-subgaussianity, and (c) from
$\sum_{i=1}^{\infty}\frac{1}{t_{i}^{2}}\leq\sum_{i=1}^{\infty}\frac{1}{i^{2}}<2$.
∎

###### Proof of Theorem 4.

For arm $k$ to be dropped from the active set $S$ at round $i$, there must
exist an arm $l$ such that

$\displaystyle\operatorname*{LCB}(l,i,\delta)$
$\displaystyle\geq\operatorname*{UCB}(k,i,\delta)$
$\displaystyle\iff\tilde{\mu}_{l,i}-U(i,\delta)$
$\displaystyle\geq\tilde{\mu}_{k,i}+U(i,\delta).$

On the set $\mathcal{E}^{c}$ (with $\mathcal{E}$ as defined in Lemma 3), we
have for all arms $j$ at round $i$, $|\tilde{\mu}_{j,i}-\mu_{j}|\leq
U(i,\delta)$. In particular, for arms $k$ and $l$, we have

$\mu_{l}+U(i,\delta)\geq\tilde{\mu}_{l,i}\text{ and
}\tilde{\mu}_{k,i}\geq\mu_{k}-U(i,\delta).$

Combining the above inequalities, we have that arm $k$ can be dropped from $S$
only if there exists an arm $l$ such that

$\displaystyle\mu_{l}+U(i,\delta)-U(i,\delta)$
$\displaystyle\geq\mu_{k}-U(i,\delta)+U(i,\delta)$ $\displaystyle\iff\mu_{l}$
$\displaystyle\geq\mu_{k}.$

We thus have that the best arm will always remain in the active set under
$\mathcal{E}^{c}$, which completes the proof. ∎

###### Proof of Lemma 5.

Let $i\geq 1$. From the definition of $U(i,\delta)$ and using the result that
for $j\leq i$, $t_{j}\leq t_{i}$, it follows that

$\displaystyle U(i,\delta)$
$\displaystyle=U^{\prime}(i,\delta)+\frac{1}{2^{B}}\left[U^{\prime}(i,\delta)+U(i-1,\delta)\right]$
$\displaystyle=\left(1+\frac{1}{2^{B}}\right)\sum_{j=1}^{i}\left(\frac{1}{2^{B}}\right)^{i-j}U^{\prime}(j,\delta){}+\left(\frac{1}{2^{B}}\right)^{i}(b-a)$
$\displaystyle=\left(1+\frac{1}{2^{B}}\right){}\sum_{j=1}^{i}\left(\frac{1}{2^{B}}\right)^{i-j}\sigma\sqrt{\frac{2\log\left(4Kt_{j}^{2}/\delta\right)}{t_{j}}}{}+\left(\frac{1}{2^{B}}\right)^{i}(b-a)$
$\displaystyle\leq\sigma\left(1+\frac{1}{2^{B}}\right)\sqrt{2\log\left(4Kt_{i}^{2}/\delta\right)}{}\sum_{j=1}^{i}\left(\frac{1}{2^{B}}\right)^{i-j}\frac{1}{\sqrt{t_{j}}}+\left(\frac{1}{2^{B}}\right)^{i}(b-a).$

Now, using $t_{i}=\alpha^{i}$ gives us that

$\displaystyle U(i,\delta)$
$\displaystyle\leq\sigma\left(1+\frac{1}{2^{B}}\right)\sqrt{2\log\left(4Kt_{i}^{2}/\delta\right)}{}\left(\frac{1}{2^{B}}\right)^{i}\sum_{j=1}^{i}\left(\frac{2^{B}}{\sqrt{\alpha}}\right)^{j}{}+\left(\frac{1}{2^{B}}\right)^{i}(b-a).$

As $\sqrt{\alpha}<2^{B}$, it follows that

$\displaystyle U(i,\delta)$
$\displaystyle\leq\sigma\left(1+\frac{1}{2^{B}}\right)\sqrt{2\log\left(4Kt_{i}^{2}/\delta\right)}{}\left(\frac{1}{2^{B}}\right)^{i}\frac{2^{B}}{\sqrt{\alpha}}\frac{\left(\frac{2^{B}}{\sqrt{\alpha}}\right)^{i}-1}{\frac{2^{B}}{\sqrt{\alpha}}-1}{}+\left(\frac{1}{2^{B}}\right)^{i}(b-a)$
$\displaystyle\leq\sigma\left(1+\frac{1}{2^{B}}\right)\sqrt{2\log\left(4Kt_{i}^{2}/\delta\right)}{}\left(\frac{1}{2^{B}}\right)^{i}\frac{2^{B}}{\sqrt{\alpha}}\frac{\left(\frac{2^{B}}{\sqrt{\alpha}}\right)^{i}}{\frac{2^{B}}{\sqrt{\alpha}}-1}{}\hskip
20.00003pt+\left(\frac{1}{2^{B}}\right)^{i}(b-a)$
$\displaystyle=\sigma\left(1+\frac{1}{2^{B}}\right)\sqrt{2\log\left(4Kt_{i}^{2}/\delta\right)}{}\frac{2^{B}}{\sqrt{t_{i}}}\frac{1}{{2^{B}}-{\sqrt{\alpha}}}{}+\left(\frac{1}{2^{B}}\right)^{i}(b-a)$
$\displaystyle=\left(1+\frac{1}{2^{B}}\right)\frac{2^{B}}{{2^{B}}-{\sqrt{\alpha}}}U^{\prime}(i,\delta){}+\left(\frac{1}{2^{B}}\right)^{i}(b-a).$

To show that

$\displaystyle U(i,\delta)\leq
2\left(1+\frac{1}{2^{B}}\right)\frac{2^{B}}{{2^{B}}-{\sqrt{\alpha}}}U^{\prime}(i,\delta),$

it suffices to show that

$\displaystyle\left(\frac{1}{2^{B}}\right)^{i}(b-a)\leq\left(1+\frac{1}{2^{B}}\right)\frac{2^{B}}{{2^{B}}-{\sqrt{\alpha}}}U^{\prime}(i,\delta).$

As

$\displaystyle\left(1+\frac{1}{2^{B}}\right)\frac{2^{B}}{{2^{B}}-{\sqrt{\alpha}}}\geq
1,$

for $i\geq 1$, and the denominator of $U^{\prime}(i,\delta)$ satisfies the
following result:

$\displaystyle\sqrt{t_{i}}=\left(\sqrt{\alpha}\right)^{i}<\left({2^{B}}\right)^{i},$

it suffices to show that
$\sigma\sqrt{2\log\left(4Kt_{i}^{2}/\delta\right)}\geq(b-a)$. This will hold
as long as

$\displaystyle
i\geq\log_{\alpha}\left(\sqrt{\frac{\delta}{4K}\exp\left(\frac{(b-a)^{2}}{2\sigma^{2}}\right)}\right).$

For a small enough $\delta$, this will be satisfied trivially. If

$\displaystyle\delta<4K\alpha^{2}\exp\left(-(b-a)^{2}/(2\sigma^{2})\right),$

then we have that for all $i\geq 1$,

$\displaystyle U(i,\delta)\leq
2\left(1+\frac{1}{2^{B}}\right)\frac{2^{B}}{{2^{B}}-{\sqrt{\alpha}}}U^{\prime}(i,\delta).$

∎

###### Proof of Theorem 6.

Assume w.l.o.g. that the optimal arm is arm 1. Similar to the proof of Theorem
4, a suboptimal arm $j$ will be removed if

$\displaystyle\operatorname*{LCB}(1,i,\delta)>\operatorname*{UCB}(j,i,\delta).$
(8)

On $\mathcal{E}^{c}$, we have that

$\displaystyle\tilde{\mu}_{1,i}$ $\displaystyle\geq\mu_{1}-U(i,\delta),$
$\displaystyle\tilde{\mu}_{j,i}$ $\displaystyle\leq\mu_{j}+U(i,\delta).$

The equation (8) is guaranteed to occur if

$\displaystyle\mu_{1}-2U(i,\delta)\geq\mu_{j}+2U(i,\delta).$

Define $\Delta_{j}=\mu_{1}-\mu_{j}$ to be the suboptimality gap of arm $j$ for
$j\in\\{2,\ldots,K\\}$. The sample complexity of arm $j$ is the number of
samples needed to remove the suboptimal arm $j$ from $S$. Define $T_{j}$ to be
the smallest value of $t_{i}$ that satisfies

$\displaystyle\Delta_{j}\geq 4U(i,\delta).$

Then $\alpha T_{j}$ is an upper bound on the sample complexity of arm $j$. The
factor of $\alpha$ is needed here as we communicate exponentially sparsely
only. For $t_{i}=\alpha^{i}$, we have, from Lemma 5,

$\displaystyle U(i,\delta)\leq 2c\,U^{\prime}(i,\delta),$

where

$\displaystyle
c=\left(1+\frac{1}{2^{B}}\right)\frac{2^{B}}{2^{B}-\sqrt{\alpha}}.$

If $T_{j}^{\prime}$ is the smallest value of $t_{i}$ satisfying

$\displaystyle U^{\prime}(i,\delta)\leq\frac{\Delta_{j}}{8c},$

then $\alpha T_{j}^{\prime}$ is an upper bound on $\alpha T_{j}$ and thus an
upper bound on the sample complexity of suboptimal arm $j$. Define
$a=\frac{\Delta_{j}^{2}}{256c^{2}\sigma^{2}}$ and $b=\ln(4K/\delta)/2$. Then
the smallest value of $i$ that is a solution to

$\displaystyle U^{\prime}(i,\delta)=\frac{\Delta_{j}}{8c}$

satisfies

$\displaystyle-at_{i}e^{-at_{i}}=-ae^{-b}.$

Let $\delta$ be small enough such that

$\displaystyle
ae^{-b}=\frac{\Delta_{j}^{2}}{256c^{2}\sigma^{2}}e^{-\ln(4K/\delta)/2}=\frac{\Delta_{j}^{2}}{256c^{2}\sigma^{2}}\sqrt{\frac{\delta}{4K}}<\frac{1}{e}.$

Then the solution to this equation would be
$\lceil\frac{-1}{a}W_{-1}(-ae^{-b})\rceil$, where $W_{-1}(y),\frac{-1}{e}<y<0$
is the smallest value of $x<0$ satisfying $xe^{x}=y$. There are in fact two
solutions, $W_{0}(y)$ and $W_{-1}(y)$, out of which $W_{-1}(y)$ is smaller
(more negative) and belongs to $\left(-\infty,-1\right)$. Using Theorem 3.1 of
[19], we have that $W_{-1}(y)>\frac{e}{e-1}\ln(-y)$. It follows that

$\displaystyle\alpha T_{j}$
$\displaystyle\leq\frac{-\alpha}{a}\frac{e}{e-1}\ln(ae^{-b})+1$
$\displaystyle=\frac{\alpha
e}{e-1}\frac{256c^{2}\sigma^{2}}{\Delta_{j}^{2}}(b-\ln a)+1$
$\displaystyle\leq\frac{410\alpha
c^{2}\sigma^{2}}{\Delta_{j}^{2}}\ln\left(\frac{256c^{2}\sigma^{2}\sqrt{4K\delta}}{\Delta_{j}^{2}}\right)+1.$

∎