# Communication-Constrained Bandits under Additive Gaussian Noise

Prathamesh Mayekar
National University of Singapore
<EMAIL_ADDRESS>Jonathan Scarlett
National University of Singapore
<EMAIL_ADDRESS>Vincent Y.F. Tan
National University of Singapore
<EMAIL_ADDRESS>
###### Abstract

We study a distributed stochastic multi-armed bandit where a client supplies
the learner with communication-constrained feedback based on the rewards for
the corresponding arm pulls. In our setup, the client must encode the rewards
such that the second moment of the encoded rewards is no more than $P$, and
this encoded reward is further corrupted by additive Gaussian noise of
variance $\sigma^{2}$; the learner only has access to this corrupted reward.
For this setting, we derive an information-theoretic lower bound of
$\Omega\left(\sqrt{\frac{KT}{\mathtt{SNR}\wedge 1}}\right)$ on the minimax
regret of any scheme, where $\mathtt{SNR}\coloneqq\frac{P}{\sigma^{2}}$, and
$K$ and $T$ are the number of arms and time horizon, respectively.
Furthermore, we propose a multi-phase bandit algorithm,
$\mathtt{UE}\text{-}\mathtt{UCB}\text{++}$, which matches this lower bound to
a minor additive factor. $\mathtt{UE}\text{-}\mathtt{UCB}\text{++}$ performs
uniform exploration in its initial phases and then utilizes the upper
confidence bound (UCB) bandit algorithm in its final phase. An interesting
feature of $\mathtt{UE}\text{-}\mathtt{UCB}\text{++}$ is that the coarser
estimates of the mean rewards formed during a uniform exploration phase help
to refine the encoding protocol in the next phase, leading to more accurate
mean estimates of the rewards in the subsequent phase. This positive
reinforcement cycle is critical to reducing the number of uniform exploration
rounds and closely matching our lower bound.

††An abridged version of this paper will appear in the proceedings of the
International Conference on Machine Learning 2023.

###### Contents

  1. 1 Introduction
    1. 1.1 Our Contributions
  2. 2 Setup and Preliminaries
  3. 3 Information-Theoretic Lower Bound
  4. 4 Bandit Algorithms over an AWGN Channel
    1. 4.1 Our Encoding Algorithm: $\mathtt{CAS}$
    2. 4.2 Warm-up: $\mathtt{UCB0}$ bandit algorithm
    3. 4.3  $\mathtt{UE}\text{-}\mathtt{UCB}$ bandit algorithm
    4. 4.4 $\mathtt{UE}\text{-}\mathtt{UCB}\text{++}$ bandit algorithm
  5. 5 Concluding Remarks
  6. A Proof of Theorem 4.3 (Regret bound of $\mathtt{UE}\text{-}\mathtt{UCB}\text{++}$)
  7. B Proof of Theorem 3.1 (Lower Bound)
  8. C Proofs of Intermediary Results in the Proof of Theorem 3.1
    1. C.1 Proof of Fact 1
    2. C.2 Proof of Fact 2

##  1 Introduction

The stochastic multi-armed bandit (SMAB) is a classic sequential decision-
making problem with decades of research (see [15] for a recent survey). The
SMAB problem crucially captures the trade-off between exploring actions to
find the optimal one or exploiting the action believed to be the best, but
possibly sub optimal action, lying at the heart of many practical sequential
decision-making problems. In its simplest form, the SMAB problem is a
sequential game between the learner and the environment. The game is played
over a finite number of rounds. In each round, the learner plays an arm from a
given set of arms, and then the environment reveals a reward corresponding to
the played arm. The reward for a particular arm is $iid$ across rounds, with
the reward distribution unknown to the learner. The learner’s goal is to
maximize the expected cumulative reward over the entirety of the game.

In another direction, in modern distributed optimization frameworks such as
Federated Learning [14], a central learner trains a global machine learning
model by leveraging updates from remote clients (typically, stochastic
gradients computed on local data). However, a major bottleneck in such
settings is the uplink communication cost – the cost of sending remote
client’s updates to the learner. This has spurred a recent line of work that
seeks to minimize the amount of communication by a remote client while still
maintaining the accuracy of the global model (see [13] for a recent survey).

An emerging abstraction to understand the trade-off between communication and
accuracy in distributed optimization is to understand the one-client setting,
where one remote client supplies the learner with gradient updates over a
rate-limited channel (see, for instance, [17, 1, 16, 10]). A similar
abstraction has been studied for distributed SMAB problems in two interesting
recent works: [11, 18]. Our work is inspired by these two studies.

In particular, [11] studies the distributed SMAB problem where a client
supplies the learner with reward feedback corresponding to its arm pull. To
account for the uplink cost from the client to the learner, at the $t$th
round, the client must quantize the reward feedback to $r_{t}$-bits, and only
the quantized reward feedback is available to the learner for further
decision-making. [18] study a linear distributed SMAB problem where at each
round, the remote client supplies the learner with a $r$-bit quantized version
of its estimate of the $d$-dimensional linear model parameter. These studies
investigate similar questions:
Q1a [11]: What is the minimum average bits $\frac{1}{T}\sum_{t=1}^{T}r_{t}$
needed to attain the regret of the centralized setting in the distributed
bandit game?
Q1b [18]: What is the minimum $r$ needed to attain the regret of the
centralized setting in the distributed bandit game?
[11] shows that $\mathcal{O}(1)$ bits of average communication is sufficient
to attain the regret of centralized setting, and [18] shows that
$r=\mathcal{O}(d)$ is sufficient111The discrepancy between results is because
of different setting: In [11], the scaler reward feedback needs to be
compressed, whereas in [18] the $d$-dimensional linear model parameter needs
to be compressed. to attain the regret of the centralized setting.

In many practical distributed learning scenarios, the updates from the client
to the learner are sent over a noisy wireless network. To model this, recent
works on distributed optimization have considered communication over noisy
channels; see, for instance, [12, 2] and the references therein.
Unfortunately, the results for distributed optimization over noisy channels do
not apply to the distributed SMAB problem over noisy channels. Moreover, the
model for communication constraints in the recent works on distributed SMAB
does not accurately capture communication over noisy channels. To bridge this
gap, we study a distributed SMAB problem where the remote client codes the
reward feedback to ensure that the encoded reward has a second moment less
than $P$, and then the client transmits the encoded reward over an (AWGN)
channel with noise variance $\sigma^{2}$ (this is equivalent to corrupting the
encoded reward with an additive Gaussian noise of mean zero and variance
$\sigma^{2}$); only the channel’s output is available to the learner for
pulling the arm at the next round. We define the signal-to-noise ratio in our
problem as

$\mathtt{SNR}\coloneqq\frac{P}{\sigma^{2}}.$

We remark that the restriction of the second moment of the encoded messages to
$P$ and transmission over an AWGN channel is a ubiquitous communication model
in information theory and communication and dates back to Shannon’s seminal
work; see, for instance, [20], [6, Chapter 9], and [21, Chapter 8]. The second
moment constraint is used to model that most edge devices are restricted to
transmitting up to a particular transmission power due to physical
constraints. The AWGN channel is often used as a first approximation for
various communication settings.

Coming back to comparisons with [11] and [19], the counterpart of Q1 in our
setting is the following question:
Q2: What is the minimum $\mathtt{SNR}$ needed to attain the regret of the
centralized setting in the distributed bandit game over an AWGN channel?
In this work, we resolve the following more general question upto
multiplicative $\log$ and minor additive factors:
Q3: How does the minimax regret scale as a function of $\mathtt{SNR}$?

###  1.1 Our Contributions

We show that any bandit algorithm employed by the learner and any encoding
strategy employed by the client must incur a worst-case expected cumulative
regret of at least222 $a\wedge b\coloneqq\min\\{a,b\\}$; $a\vee
b\coloneqq\max\\{a,b\\}$.

$\Omega\left(\sqrt{\frac{KT}{\mathtt{SNR}\wedge 1}}+KB\right),$

where $K$ is the number of bandit arms, $T$ is time horizon, and $B$ is upper
bound on the $L_{2}$-norm333The $L_{2}$ norm of a random variable $X$ is
$\sqrt{\mathbb{E}\left[X^{2}\right]}.$ of rewards. A technical difficulty in
deriving this lower bound is to account for the loss of information due to
transmission over the AWGN channel. We overcome this difficulty by leveraging
classic information-theoretic results for transmission over an AWGN channel
and combining these techniques with the standard minimax lower bound proof for
SMAB. An interesting consequence of our proof technique is that, up to
constant factors, we can recover the lower bound in [11] with an arguably
simpler proof; see Appendix for details.

Unlike [11] and [18], we don’t quantize our updates. In our setup,
quantization and transmitting over an AWGN channel would lead to decoding
errors at every round, which can pile up and result in linear regret unless
$\mathtt{SNR}$ grows with the time horizon $T$; such a scheme would not allow
us to resolve $\textbf{Q3}.$ Instead, we use a center and scale encoding
protocol $\mathtt{CAS}$, where the centering and scaling factors are learned
over time. We also design a new bandit algorithm
$\mathtt{UE}\text{-}\mathtt{UCB}\text{++}$ which, along with the encoding
protocol $\mathtt{CAS}$, bounds the worst-case expected cumulative regret by a
factor of444$\log(\cdot)$ refers to the logarithm to the base 2; $\ln$ refers
to the logarithm to the base $e$.

$\mathcal{O}\left(\sqrt{\left(\frac{1}{\mathtt{SNR}}+1\right)\cdot KT\ln
T}+\frac{KB\log B}{\mathtt{SNR}\wedge 1}\right).$

Thus, we resolve Q3 up to a multiplicative factor of $\sqrt{\ln T}$ and an
additive factor of $\frac{KB\log B}{\mathtt{SNR}\wedge 1}$.

$\mathtt{UE}\text{-}\mathtt{UCB}\text{++}$ performs uniform exploration for
multiple initial sub-phases and then employs the classic upper confidence
bound $\mathtt{UCB}$ bandit algorithm. The multiple initial uniform
exploration sub-phases allow us to learn $\mathtt{CAS}$’s optimal centering
and scaling factors. An interesting feature of
$\mathtt{UE}\text{-}\mathtt{UCB}\text{++}$ is that we start with coarser mean
reward estimates for all arms in a given sub-phase, which helps us refine the
communication scheme for the subsequent sub-phases. The refined communication
scheme, in turn, leads to better mean rewards estimates in the subsequent sub-
phase. Due to this positive reinforcement cycle, the variance of the mean
reward estimates decays exponentially with respect to the number of uniform
exploration sub-phases. As a result, we can learn an almost optimal encoding
protocol after relatively few rounds of uniform exploration.

We also design a private555As opposed to the popular privacy notion of
differential privacy [9], we emphasize that here we refer to a much more
rudimentary privacy notion, where the learner does not send information to the
remote clients at any of the rounds. scheme where the learner does not send
any information to the client. We show that for such a scheme, the worst-case
expected cumulative regret can be bounded by

$\mathcal{O}\left(\sqrt{\frac{B^{2}}{\mathtt{SNR}}+1}\cdot\sqrt{KT\ln
T}+KB\right).$

This simple scheme nearly matches our lower bound when $B=\mathcal{O}(1).$

##  2 Setup and Preliminaries

LearnerClient$A_{t},S_{t},D_{t}$$D_{t}$$S_{t}$$A_{t}$$D_{t}(Y_{t})$$X_{t,A_{t}}$$C_{t}(X_{t,A_{t}},S_{t})$$Y_{t}$AWGN$\pi$$H_{t-1}$$D_{t}$$C_{t}$
Figure 1: The Distributed Bandit Game over an AWGN channel

We now proceed to describe our setup; see Figure 1 for a pictorial
description.

#### The Distributed SMAB Problem over an AWGN channel:

  1. 1.

At round $t\in[T]$,666For an integer $n$, $[n]\coloneqq\\{1,\ldots,n\\}$. the
learner asks a client to pull an arm $A_{t}$. The learner also sends some side
information $S_{t}$ based on the history of the game until time $t-1$ to aid
the communication at the client.

  2. 2.

Upon receiving this information, the client pulls arm $A_{t}$ and gets a
reward $X_{t,A_{t}}$ corresponding to the arm $A_{t}$. The client then encodes
this reward using an encoding function
$C_{t}\colon\mathbb{R}\times\mathcal{S}\to\mathbb{R}$ to form
$C_{t}(X_{t,A_{t}},S_{t}),$ where $\mathcal{S}$ is the domain of the
information $S_{t}$ sent by the learner. The encoding function must satisfy
the power constraint

$\displaystyle\mathbb{E}\left[C_{t}(X_{t,A_{t}},S_{t})^{2}\right]\leq P$ (1)

for some $P>0.$

  3. 3.

The client sends the encoded reward over the AWGN channel. The output of the
channel $Y_{t}$ is received by the learner, where

$\displaystyle Y_{t}=C_{t}(X_{t,A_{t}},S_{t})+Z_{t}$ (2)

and $\\{Z_{t}\\}_{t=1}^{\infty}$ is sequence of i.i.d. Gaussian random
variables with mean $0$ and variance $\sigma^{2}.$

  4. 4.

The learner decodes $Y_{t}$ using a decoding function
$D_{t}\colon\mathbb{R}\times\mathcal{S}\to\mathbb{R}$ to form a reward
estimate $D_{t}(Y_{t},S_{t}).$ The learner then uses a bandit algorithm $\pi$
to decide on arm $A_{t+1}$, the side information $S_{t+1}$, and decoding
function $D_{t+1}$ using history of the game up to round $t$,
$H_{t}\coloneqq(A_{1},Y_{1},\ldots,A_{t},Y_{t}).$

######  Remark 1.

In most distributed learning settings, the communication from the learner to
client (downlink communication) is not expensive. Therefore, we allow for
schemes where the learner can, in principle, send entire history of the game
up to a particular round as side information for the next round. However, our
proposed scheme will send only a single real number as side information at
each round, which is more desirable in practical settings.

######  Remark 2.

The client is ‘memoryless’ in our setup; the client cannot use rewards from
previous arm pulls to encode the current reward. This is motivated by the fact
that, as observed in [11], in a typical distributed sequential decision-making
problem, the client observing the reward is a low memory sensor. Additionally,
in some applications, the client at any given round may differ from those at
the previous rounds.

Denote by $\Pi_{T}$ be the set of all possible $T$-round bandit algorithms as
described above and denote by $\mathcal{C}$ the set of all possible encoding
strategies satisfying (1). We note that $\Pi_{T}$ contains randomized
algorithms, so our lower bounds hold for such algorithms, too. However, we
will use a deterministic algorithm for our upper bounds.

#### Reward Distributions:

We make the following standard assumptions on the reward distributions. We
assume that the reward sequence $\\{X_{t,i}\\}_{t>1}$ is i.i.d. for all arms
$i$ in $[K]$ and the rewards for different arms are independent of each other.
Denote by $\mu_{i}$ the mean reward of arm $i$. We assume that
$X_{1,i}-\mu_{i}$ is subgaussian with variance factor $1$,777The variance
factor $1$ is without loss of generality; all our regret bounds scale linearly
with this factor. where a subgaussian random variable with a variance factor
$\sigma$ is as defined below.

######  Definition 2.1.

[5] We say a random variable $X$ is subgaussian with a variance factor
$\alpha^{2},$ if for all $\lambda\in\mathbb{R},$ we have

$\ln[\exp(\lambda X)]\leq\frac{\lambda^{2}\alpha^{2}}{2}.$

Furthermore, for a subgaussian random variable with variance factor
$\alpha^{2},$ we have $\mathbb{E}\left[X\right]=0$ and
$\mathbb{E}\left[X^{2}\right]\leq\alpha^{2}.$

Finally, for $B\geq 1$,888Since $X_{1,i}-\mu_{i}$ is subgaussian with variance
factor $1,$ its second moment is bounded by $1$, so we may assume that $B\geq
1$. we assume for all $i\in[K]$, that

$\displaystyle\mathbb{E}\left[X_{1,i}^{2}\right]\leq B^{2}.$ (3)

Denote by $\mathcal{P}$ the set of all subgaussian distributions with variance
factor $1$ whose second moment satisfies (3). Then,
$\mathcal{E}\coloneqq\mathcal{P}^{K}$ describes the set of all possible bandit
instances considered in our setup.

#### Regret:

We define the regret for a bandit instance $\nu\in\mathcal{E}$, when a bandit
algorithm $\pi\in\Pi$ and encoding strategies
$C_{1}^{T}:=(C_{t})_{t\in[T]}\in\mathcal{C}^{T}$ are employed, as

$R_{T}(\nu,\pi,C_{1}^{T})\coloneqq
T\mu_{i^{\ast}}-\mathbb{E}\left[\sum_{t=1}^{T}X_{t,A_{t}}\right],$

where $i^{\ast}$ is the arm with the largest mean for the bandit instance
$\nu$. We are interested in characterizing the minimax regret

$\displaystyle
R^{\ast}_{T}(\mathtt{SNR})\coloneqq\inf_{\pi\in\Pi_{T}}\inf_{C_{1}^{T}\in\mathcal{C}^{T}}\sup_{\nu\in\mathcal{E}}R_{T}(\nu,\pi,C_{1}^{T})$
(4)

as function of $\mathtt{SNR},K,B,$ and $T$.

####  $\mathtt{UCB}$ bandit algorithm:

We now describe the classical Upper Confidence Bound ($\mathtt{UCB}$) bandit
algorithm [4]. We will build on the $\mathtt{UCB}$ algorithm to come up with
our algorithm. Recall that at each round $\mathtt{UCB}$ plays the arm with the
largest upper confidence bound. For subgaussian rewards with variance factor
$\alpha^{2}$, the upper confidence bound for an arm $k\in[K]$ after $t$ rounds
is defined as

$\mathtt{UCB}_{k}(t;\eta)=\begin{cases}\infty\quad\text{if}\quad N_{k}(t)=0\\\
\hat{\mu}_{k}(t)+\sqrt{\frac{4\eta\ln
T}{N_{k}(t)}}\quad\text{otherwise},\end{cases}$

where $N_{k}(t)$ is the number of times the arm $k$ has been played up to
round $t$, and $\hat{\mu}_{k}(t)$ is the empirical mean estimate of arm $k$.
It is not difficult to prove the following regret guarantees for the
$\mathtt{UCB}$ algorithm (see, for instance, [15, Theorem 7.2]).

######  Lemma 2.2.

Suppose we have a classical bandit game over $T$ rounds and $K$ arms with the
following reward feedback: (i), the reward feedback corresponding to all arms
is subgaussian with a variance factor of $\alpha^{2}$; (ii), the second moment
of the reward feedback is at most $B$. Then, the regret of the $\mathtt{UCB}$
algorithm with parameter $\eta=\alpha^{2}$ satisfies

$R_{T}\leq 8\sqrt{\alpha^{2}KT\ln T}+6KB.$

##  3 Information-Theoretic Lower Bound

Our lower bound is stated as follows.

######  Theorem 3.1.

For universal constants $c_{1}$ and $c_{2}$, where $0<c_{1}<1$ and $c_{2}>0,$
we have

$\displaystyle R^{\ast}_{T}(\mathtt{SNR})\geq
c_{1}\bigg{(}\sqrt{KT}\cdot\frac{1}{\sqrt{\frac{1}{2}\log(1+\mathtt{SNR})\wedge
1}}\wedge c_{2}T+KB\bigg{)}$

for all $T\geq\frac{c_{2}K}{\frac{1}{2}\log(1+\mathtt{SNR})\wedge 1}$.

The proof of this lower bound adopts a similar high-level approach to the
lower bound proofs in the standard setting (see, for instance, [15, Chapter
15]). However, a crucial difference from the standard proofs is that we now
have to account for the loss in information due to the rewards being sent over
the Gaussian channel. We defer the proof to the Appendix.

######  Remark 3.

In information theory, the term $\frac{1}{2}\log(1+\mathtt{SNR})$ is the
capacity of the Gaussian channel. It refers to the maximum rate at which
information can be transmitted with arbitrarily small probability of error;
see [6] for details.

The following corollary of Theorem 3.1 will be useful to derive matching upper
bounds.

######  Corollary 3.2.

For universal constants $c_{1}$ and $c_{2}$, where $0<c_{1}<1$ and $c_{2}>0,$
we have

$R^{\ast}_{T}(\mathtt{SNR})\geq
c_{1}\left(\sqrt{KT}\cdot\frac{1}{\sqrt{\mathtt{SNR}\wedge 1}}+KB\right)$

for all $T\geq\frac{c_{2}K}{\frac{1}{2}\log(1+\mathtt{SNR})\wedge 1}$.

###### Proof.

The proof simply follows by combining Theorem 3.1 with the fact that
$\ln(1+x)\leq x$ for $x\geq 0$. ∎

We note while $\mathtt{SNR}\wedge 1$ and
$\frac{1}{2}\log(1+\mathtt{SNR})\wedge 1$ may appear quite different at first
glance, they are, in fact, the same up to constant factors, since
$\frac{1}{2}\log(1+\mathtt{SNR})$ is both upper and lower bounded by a
constant times $\mathtt{SNR}$ for $\mathtt{SNR}\in[0,3],$ whereas for
$\mathtt{SNR}>3$ both terms take the value $1.$

##  4 Bandit Algorithms over an AWGN Channel

###  4.1 Our Encoding Algorithm: $\mathtt{CAS}$

A crucial component of all our schemes is an encoding strategy we refer to as
centered amplitude scaling ($\mathtt{CAS}$). $\mathtt{CAS}$ simply centers the
input $X$ around side information $S$ and multiplies it by $\theta$ to get

$C_{\mathtt{CAS}}(X,S;\theta):=\theta(X-S),$

which is transmitted over the AWGN channel. If the input and side information
are such that $\mathbb{E}\left[(X-S)^{2}\right]\leq\frac{P^{2}}{\theta^{2}},$
then $C(X,S)$ satisfies the power constraint (1).

We now build up to our main algorithm in the following two subsections.

###  4.2 Warm-up: $\mathtt{UCB0}$ bandit algorithm

We begin by describing a simple warm-up which uses $\mathtt{CAS}$ with
parameter $\theta=\frac{\sqrt{P}}{B}$ as the encoding algorithm at each round,
and the $\mathtt{UCB0}$ bandit algorithm described below.

The $\mathtt{UCB0}$ bandit algorithm is a standard bandit algorithm that sends
no side information at all rounds (equivalent to sending zero as the side
information at all rounds). Additionally, $\mathtt{UCB0}$ simply scales
channel output $Y_{t}$ by the inverse of the scaling parameter used by
$\mathtt{CAS}$, $\frac{1}{\theta}=\frac{B}{\sqrt{P}},$ to get

$\tilde{X}_{t,A(t)}=\frac{B}{\sqrt{P}}Y_{t},$

which it uses as the reward estimate for round $t.$ $\mathtt{UCB0}$ along with
its interaction with $\mathtt{CAS}$ is described in Algorithm 1.

1: Parameters: $\eta=\frac{B^{2}}{\mathtt{SNR}}+1$,
$\theta=\frac{\sqrt{P}}{{B}}$ 2:for $t\in[T]$ do 3: At Learner 4:
$\displaystyle{A_{t}=\arg\max_{k\in K}\mathtt{UCB}_{k}\left(t-1;\eta\right)}$
and $S_{t}=0$ 5: Send $A_{t},$ $S_{t}$ to Client  6: At Client 7: Play arm
$A_{t}$ and observe $X_{t,A_{t}}$ 8: Send
$C_{\mathtt{CAS}}(X_{t,A_{t}},0;\theta)$ over the AWGN channel  9: At Learner
10: Observe AWGN Output $Y_{t}=C_{\mathtt{CAS}}(X_{t,A_{t}},0)+Z_{t}$ 11: Use
$\tilde{X}_{t,A_{t}}=\frac{Y_{t}}{\theta}$ as the $t$th round reward  12:
Update UCB index for all arms  Algorithm 1: $\mathtt{UCB0}$ bandit algorithm
along with $\mathtt{CAS}$ encoding algorithm

######  Theorem 4.1.

For all bandit instances $\nu\in\mathcal{E}$, the $\mathtt{UCB0}$ algorithm
along with $\mathtt{CAS}$ encoding satisfies the power constraint (1) at all
rounds and has the following regret guarantee:

$R_{T}(\nu,\mathtt{UCB}0,\mathtt{CAS})\leq
8\sqrt{\frac{B^{2}}{\mathtt{SNR}}+1}\cdot\sqrt{KT\ln T}+6KB.$

###### Proof.

Using (3), we have that
$\mathbb{E}\left[\big{(}\frac{\sqrt{P}}{B}X\big{)}^{2}\right]\leq P.$ We will
show that the reward estimates $\tilde{X}_{t,A_{t}}$ used by the UCB algorithm
are unbiased and subgaussian with a variance factor of
$\frac{B^{2}}{\mathtt{SNR}}+1$. First, notice that
$\tilde{X}_{t,A_{t}}=\frac{BY_{t}}{\sqrt{P}}$ and
$Y_{t}=\frac{\sqrt{P}{X}_{t,A_{t}}}{B}+Z_{t}.$ Combining these, we get

$\tilde{X}_{t,A_{t}}=X_{t,A_{t}}+\frac{BZ_{t}}{\sqrt{P}}.$

Note that $X_{t,A_{t}}$ and $Z_{t}$ are independent and subgaussian with
variance factors $1$ and $\sigma^{2}$, respectively. Therefore, the centered
reward estimate, $\tilde{X}_{t,A_{t}}-\mu_{A_{t}},$ is subgaussian with
variance factor $\frac{B^{2}}{\mathtt{SNR}}+1$.

Hence, this algorithm reduces our problem to playing a bandit game with
subgaussian rewards that have a variance factor of
$\alpha^{2}=\frac{B^{2}}{\mathtt{SNR}}+1.$ Since the learner uses the UCB
algorithm with parameter $\eta=\alpha^{2},$ we can bound the regret by using
Lemma 2.2. ∎

######  Remark 4.

The regret bound of $\mathtt{UCB0}$ matches our lower bound when
$B=\mathcal{O}(1).$ However, for larger values of $B,$ the regret bound of
$\mathtt{UCB0}$ is far from our lower bound. While this is a significant
weakness of $\mathtt{UCB0}$, it is still appealing in settings where the
learner does not want to send any side information to the client due to
privacy concerns.

###  4.3  $\mathtt{UE}\text{-}\mathtt{UCB}$ bandit algorithm

The regret bound in Theorem 4.1 is off by a multiplicative factor of
${\mathcal{O}\big{(}B\big{)}}$ from our lower bound. This gap results from our
encoding algorithm, which leads to subgaussian rewards with a variance factor
of $\frac{B^{2}}{\mathtt{SNR}}$. On the other hand, to match the lower bound
in Theorem 3.1, one requires a strategy such that the encoded rewards are
subgaussian with a variance factor of
$\mathcal{O}\left(\frac{1}{\mathtt{SNR}}\right).$ We take the first step in
arriving at such an algorithm in our second scheme, in which we combine a two-
phase bandit algorithm, Uniform Exploration-Upper Confidence Bound
($\mathtt{UE}\text{-}\mathtt{UCB}$), with the $\mathtt{CAS}$ encoding
algorithm.

In the first phase, $\mathtt{UE}\text{-}\mathtt{UCB}$ performs uniform
exploration, and in the second phase, $\mathtt{UE}\text{-}\mathtt{UCB}$ uses
the $\mathtt{UCB}$ algorithm to select the arm. We will now describe in detail
the $\mathtt{UE}\text{-}\mathtt{UCB}$ algorithm and the encoding strategy at
the client.

#### Phase 1:

In the first phase, the learner uniformly explores all arms, and sends no side
information to the clients. The communication strategy in this phase is the
same as in the previous scheme. In particular, we use $\mathtt{CAS}$ with
parameter $\theta_{1}=\frac{\sqrt{P}}{B}$ for encoding at the client. For
decoding at the learner, $\mathtt{UE}\text{-}\mathtt{UCB}$ scales the channel
output $Y_{t}$ by $1/\theta_{1}$ to get

$\tilde{X}_{t,A(t)}=\frac{B}{\sqrt{P}}Y_{t}.$

We run the phase one of $\mathtt{UE}\text{-}\mathtt{UCB}$ for $K\tau$ rounds,
where999For simplicity of notation, we assume that
$\frac{B^{2}}{\mathtt{SNR}},$ $\frac{1}{\mathtt{SNR}},$ and $\log B$ are
integers throughout the paper. If not, the rounding only slightly impacts the
constant factors in our results. $\tau\coloneqq\frac{B^{2}}{\mathtt{SNR}}+1$.

#### Phase 2:

For all $k\in[K],$ denote by $\hat{\mu}_{k}$ the mean estimates formed for all
arms at the end of the first phase. Then, in the second phase, the learner
runs the classic $\mathtt{UCB}$ algorithm treating $\tilde{X}_{t,A_{t}}$ as
the reward to decide on an arm $A_{t}$. It then informs the client about arm
$A_{t}$ and the mean estimate formed for this arm after phase one,
$\hat{\mu}_{A_{t}}$.

On the client’s side, the reward corresponding to $A_{t}$ is encoded by using
$\mathtt{CAS}$ with parameter $\theta_{2}=\sqrt{\frac{P}{2}}$ to get

$C_{\mathtt{CAS}}(X_{t,A_{t}},\mu_{A_{t}};\theta_{2}):=\sqrt{\frac{P}{2}}(X_{t,A_{t}}-\hat{\mu}_{A_{t}}).$

The decoding at the learner is simply done by scaling $Y_{t}$ by
$\frac{1}{\theta_{2}}$ and adding the mean estimate $\hat{\mu}_{A_{t}}$ to get

$\tilde{X}_{t,A_{t}}=\sqrt{\frac{2}{P}}Y_{t}+\hat{\mu}_{A_{t}}.$

$\mathtt{UE}\text{-}\mathtt{UCB}$ along with its interaction with
$\mathtt{CAS}$ is described in Algorithm 2.

######  Remark 5.

We will soon show in the proof of Theorem 4.2 that
$\mathbb{E}\left[\big{(}X_{t,A_{t}}-\hat{\mu}_{A_{t}}\big{)}^{2}\right]\leq
2.$ Thus our choice of $\theta_{2}$ ensures that the power constraint is
satisfied. Moreover, for $B\geq 2$, $\theta_{2}$ is greater than $\theta_{1}$,
which essentially means that the client can scale the centered reward in the
second phase by a bigger factor as compared to the scaling factor used in
Algorithm 1. In both algorithms, since the learner multiplies $Y_{t}$ by the
inverse of the scaling factor used at the client, the greater value of scaling
factor results in smaller variances for the decoded rewards than in Algorithm
1.

1: Parameters: $\theta_{1}=\frac{\sqrt{P}}{{B}}$,
$\tau=\frac{B^{2}}{\mathtt{SNR}}+1$ 2:Phase $1$ 3:for $k\in[K]$ do 4: for
$t\in\\{(k-1)\tau+1,\ldots,K\tau\\}$ do 5: At Learner 6: $A_{t}=k$ and
$S_{t}=0$ 7: Send $A_{t},S_{t}$ to Client  8: At Client 9: Play arm $A_{t}$
and observe $X_{t,A_{t}}$ 10: Send
$C_{\mathtt{CAS}}(X_{t,A_{t}},0;\theta_{1})$ over the AWGN channel  11: At
Learner 12: Observe AWGN Output
$Y_{t}=C_{\mathtt{CAS}}(X_{t,A_{t}},0;\theta_{1})+Z_{t}$ 13: Use
$\tilde{X}_{t,A_{t}}=\frac{Y_{t}}{\theta_{1}}$ as the $t$th round reward  14:
At Learner 15: Form a mean estimate for arm $k$ $\displaystyle{\hskip
28.45274pt\hat{\mu}_{k}=\frac{1}{\tau}\cdot\sum_{t=(k-1)\tau+1}^{k\tau}\tilde{X}_{t,k}}$
16: 17: Parameters: $B_{2}^{2}=2$, $\eta_{2}=\frac{2}{\mathtt{SNR}}+1$,
$\theta_{2}=\sqrt{\frac{P}{2}}$ 18:Phase $2$ 19:for
$t\in\\{K\tau+1,\ldots,T\\}$ do 20: At Learner 21:
$\displaystyle{A_{t}=\arg\max_{k\in
K}\mathtt{UCB}_{k}\left(t-1;\eta_{2}\right)}$ and $S_{t}=\hat{\mu}_{A_{t}}$
22: Send $A_{t},S_{t}$ to Client  23: At Client 24: Play arm $A_{t}$ and
observe $X_{t,A_{t}}$ 25: Send
$C_{\mathtt{CAS}}(X_{t,A_{t}},S_{t};\theta_{2})$ over the AWGN channel  26: At
Learner 27: Observe AWGN Output
$Y_{t}=C_{\mathtt{CAS}}(X_{t,A_{t}},S_{t};\theta_{2})+Z_{t}$ 28: Use
$\tilde{X}_{t,A_{t}}=\frac{Y_{t}}{\theta_{2}}+S_{t}$ as the $t$th round reward
29: Update UCB index for all arms  Algorithm 2:
$\mathtt{UE}\text{-}\mathtt{UCB}$ Algorithm along with the $\mathtt{CAS}$
encoding algorithm

######  Theorem 4.2.

For all bandit instances $\nu\in\mathcal{E}$, the
$\mathtt{UE}\text{-}\mathtt{UCB}$ algorithm along with $\mathtt{CAS}$ encoding
as described in Algorithm (2) satisfies the power constraint (1) at all rounds
and has the following regret guarantee:

$\displaystyle
R_{T}(\nu,\mathtt{UE}\text{-}\mathtt{UCB},\mathtt{CAS})\leq\frac{2KB^{3}}{\mathtt{SNR}}+8KB+8\sqrt{\frac{2}{\mathtt{SNR}}+1}\sqrt{KT\ln
T}.$

###### Proof.

In the first phase, we incur regret linear regret in the time horizon.
Specifically, since the time horizon for the first phase is
$K\tau=K(B^{2}/\mathtt{SNR}+1)$ and the gap between the mean of the optimal
arm and the suboptimal arm can at most be $2B$, we have that the regret
incurred in the first phase is $(KB^{2}/\mathtt{SNR}+K)\cdot 2B.$ Moreover,
since the encoding of rewards on the client’s side and decoding of the reward
on the learner’s side in the first phase is same as in Algorithm 1, by the
same arguments, the power constraint is satisfied, and for all
$t\in\\{(k-1)\tau+1,\ldots,k\tau\\},$

$\mathbb{E}\left[(\tilde{X}_{t,k}-\mu_{k})^{2}\right]\leq\frac{B^{2}}{\mathtt{SNR}}+1.$
(5)

For the second phase, we will first show that the power constraint is
satisfied. Towards proving this, we will bound the variance of the mean
estimates formed after the first phase. We have from the description of
Algorithm 2 that for all $k\in K,$

$\displaystyle\mathbb{E}\left[(\hat{\mu}_{k}-\mu_{k})^{2}\right]$
$\displaystyle=\frac{1}{\tau^{2}}\sum_{t=(k-1)\tau+1}^{k\tau}\mathbb{E}\left[(\tilde{X}_{t,k}-\mu)^{2}\right]\leq
1,$

where the inequality follows from (5) and the fact that
$\tau=\frac{B^{2}}{\mathtt{SNR}}+1.$

Now, note that for any round $t$ in phase 2, we have

$\displaystyle\mathbb{E}\left[(X_{t,A_{t}}-\hat{\mu}_{A_{t}})^{2}\right]$
$\displaystyle=\mathbb{E}\left[(X_{t,A_{t}}-\mu_{A_{t}})^{2}\right]+\mathbb{E}\left[(\hat{\mu}_{A_{t}}-\mu_{A_{t}})^{2}\right]\leq
2,$

where the equality follows from the independence of $X_{t,A_{t}}$ and
$\hat{\mu}_{A_{t}},$ and the inequality follows from the fact that both
$(X_{t,A_{t}}-\mu_{A_{t}})$ and $(\hat{\mu}_{A_{t}}-\mu_{A_{t}})$ are
subgaussian with a variance factor of $1$.

Therefore, scaling the centered reward $X_{t,k}-\hat{\mu}_{k}$ by
$\frac{\sqrt{P}}{\sqrt{2}}$ satisfies the power constraint.

The reward estimate used by the learner in phase 2 is

$\displaystyle\tilde{X}_{t,A_{t}}$
$\displaystyle=\frac{\sqrt{2}Y_{t}}{\sqrt{P}}+\hat{\mu}_{A_{t}}$
$\displaystyle=X_{t,A_{t}}+\frac{\sqrt{2}Z_{t}}{\sqrt{P}}.$

This implies that the centered reward estimate,
$\tilde{X}_{t,A_{t}}-\mu_{A_{t}}$, is subgaussian with a variance factor of
$2/\mathtt{SNR}+1$ in the second phase. The proof is complete by upper
bounding the regret in the second phase by using Lemma 2.2 and summing the
regret in the two phases. ∎

###  4.4 $\mathtt{UE}\text{-}\mathtt{UCB}\text{++}$ bandit algorithm

Algorithm 2 improves over Algorithm 1 in the sense that the $T$-dependent term
in its regret upper bound does not have the multiplicative $\mathcal{O}(B)$
dependence. This term matches the lower bound in Theorem 3.1 up to logarithmic
factors in $T$. However, this comes at the cost of an additional additive term
of $\mathcal{O}(\frac{KB^{3}}{\mathtt{SNR}})$ in the regret bound of Algorithm
2. The strong dependence on $B$ in this additive term means that for large
values of $B$, Algorithm 2 can be far from optimal. In this section, we
present our main scheme, which improves over this shortcoming of Algorithm 2,
and is only off by a minor additive term from our lower bound. Our scheme will
combine an improved version of the $\mathtt{UE}\text{-}\mathtt{UCB}$
algorithm, $\mathtt{UE}\text{-}\mathtt{UCB}\text{++}$, and the $\mathtt{CAS}$
encoding algorithm.

Like $\mathtt{UE}\text{-}\mathtt{UCB}$,
$\mathtt{UE}\text{-}\mathtt{UCB}\text{++}$ is also a two-phase bandit
algorithm, that performs uniform exploration in the first phase and runs the
$\mathtt{UCB}$ algorithm in the second phase. The second phase of the
algorithm proceeds in the same manner as that of the
$\mathtt{UE}\text{-}\mathtt{UCB}$ algorithm, and the improvement over
$\mathtt{UE}\text{-}\mathtt{UCB}$ is in the phase 1 of the algorithm.

1: Parameters: $L=2\log B$, $\tau=\frac{2}{\mathtt{SNR}},$ $B_{1}^{2}=B^{2}$
2: 3:for $\ell\in[L]$ do 4:$\theta_{\ell}=\frac{\sqrt{P}}{B_{\ell}}$
5:$B^{2}_{\ell+1}=\left(\frac{\frac{B^{2}_{\ell}}{\mathtt{SNR}}+1}{\tau}+1\right)$
6: 7:for $k\in[K]$ do $\hat{\mu}_{0,k}=0$ 8:Phase $1$ 9:for $\ell\in[L]$ do
10: for $k\in[K]$ do 11: for
$t\in\\{(\ell-1)K\tau+(k-1)\tau+1,\ldots,(\ell-1)K\tau+k\tau\\}$ do 12: At
Learner 13: $A_{t}=k$ and $S_{t}=\hat{\mu}_{\ell-1,k}$ 14: $A_{t},$ $S_{t}$ to
the client  15: At Client 16: Play arm $A_{t}$ and observe $X_{t,A_{t}}$ 17:
Send $C_{\mathtt{CAS}}(X_{t,A_{t}},S_{t};\theta_{\ell})$ over the AWGN channel
18: At Learner 19: Observe AWGN Output
$Y_{t}=C_{\mathtt{CAS}}(X_{t,A_{t}},S_{t};\theta_{\ell})+Z_{t}$ 20: Use
$\tilde{X}_{t,A_{t}}=\frac{Y_{t}}{\theta_{t}}+S_{t}$ as the $t$th round reward
21: At Learner 22: Form a mean estimate for arm $k$
$\hat{\mu}_{\ell,k}=\frac{1}{\tau}\cdot\sum_{t=(\ell-1)K\tau+(k-1)\tau+1}^{(\ell-1)K\tau+k\tau}\tilde{X}_{t,k}$
23: 24: Parameters: $\theta_{L+1}=\frac{\sqrt{P}}{B_{L+1}}$,
$\eta_{L+1}=\frac{B^{2}_{L+1}}{\mathtt{SNR}}+1$ 25:Phase $2$ 26:for
$t\in\\{K\tau+1,\ldots,T\\}$ do 27: At Learner 28:
$\displaystyle{A_{t}=\arg\max_{k\in
K}\mathtt{UCB}_{k}\left(t-1;\eta_{L+1}\right)}$ and
$S_{t}=\hat{\mu}_{L,A_{t}}$ 29: Send $A_{t},S_{t}$ to Client  30: At Client
31: Play arm $A_{t}$ and observe $X_{t,A_{t}}$ 32: Send
$C_{\mathtt{CAS}}(X_{t,A_{t}},S_{t};\theta_{L+1})$ over the AWGN channel  33:
At Learner 34: Observe AWGN Output
$Y_{t}=C_{\mathtt{CAS}}(X_{t,A_{t}},S_{t};\theta_{L+1})+Z_{t}$ 35: Use
$\tilde{X}_{t,A_{t}}=\frac{Y_{t}}{\theta_{L+1}}+S_{t}$ as the $t$th round
reward  36: Update UCB index for all arms  Algorithm 3:
$\mathtt{UE}\text{-}\mathtt{UCB}\text{++}$ Algorithm along with the
$\mathtt{CAS}$ encoding algorithm

#### Phase 1:

$\mathtt{UE}\text{-}\mathtt{UCB}\text{++}$, like
$\mathtt{UE}\text{-}\mathtt{UCB}$, does uniform exploration in all rounds of
phase 1. However, phase 1 is divided into $L$ different sub-phases, where the
encoding of rewards is different in each sub-phase. The mean estimates formed
in the previous sub-phase are used as side information in the current sub-
phase and sent to the client for better encoding.

In more detail, we have $L=2\log B$ sub-phases in total and each sub-phase
runs for $K\tau$ rounds, where

$\displaystyle\tau=\frac{2}{\mathtt{SNR}}\vee 2.$ (6)

Thus, phase 1 runs for $L\cdot K\tau\leq\frac{4K\log B}{\mathtt{SNR}}$ rounds.

######  Remark 6.

Phase 1 in $\mathtt{UE}\text{-}\mathtt{UCB}\text{++}$ runs for
$\mathcal{O}{\big{(}\frac{K\log B}{\mathtt{SNR}}\big{)}}$ rounds as opposed to
$\mathcal{O}{\big{(}\frac{KB^{2}}{\mathtt{SNR}}\big{)}}$ rounds used in the
phase 1 of $\mathtt{UE}\text{-}\mathtt{UCB}$. We will show that despite
performing uniform exploration for significantly fewer rounds for all arms, we
will end up with mean estimates with the same variance as the means estimates
formed after phase 1 of $\mathtt{UE}\text{-}\mathtt{UCB}$ because of a
superior encoding protocol in this phase.

The first sub-phase proceeds in exactly the same manner as phase 1 of
Algorithm 2. To describe the algorithm in the subsequent sub-phases, we set up
some notation: For all $k\in[K],$ denote by $\hat{\mu}_{\ell,k}$ the mean
estimates formed for all arms at the end of the $\ell$th sub-phase. For a
round $t$ in $\ell$th sub-phase, the learner informs the client about the arm
$A_{t}$ it wants to play and the mean estimate formed for this arm in the
$(\ell-1)$th sub-phase, $\hat{\mu}_{\ell-1,A_{t}}.$

On the client’s side, the reward corresponding to $A_{t}$ is encoded by using
$\mathtt{CAS}$ with parameter $\theta_{\ell}=\frac{\sqrt{P}}{B_{\ell}}$ to get

$C_{\mathtt{CAS}}(X_{t,A_{t}},\mu_{A_{t}};\theta_{\ell}):=\frac{\sqrt{P}}{B_{\ell}}(X_{t,A_{t}}-\hat{\mu}_{\ell-1,A_{t}}).$

Here $B_{\ell}$, $\ell\in[L]$, will be shown to be an upper bound on the
$L_{2}$-norm of random variable $X_{t,A_{t}}-\hat{\mu}_{\ell-1,A_{t}}$ (see
the proof of Theorem 4.3 ) and is described by the recursion

$\displaystyle
B^{2}_{\ell+1}=\frac{\frac{B^{2}_{\ell}}{\mathtt{SNR}}+1}{\tau}+1\quad\text{and}\quad
B_{1}^{2}=B^{2}.$ (7)

The decoding at the learner is simply done by scaling $Y_{t}$ by
$\frac{1}{\theta_{\ell}}$ and adding the mean estimate
$\hat{\mu}_{\ell,A_{t}}$ to get

$\tilde{X}_{t,A_{t}}=\frac{B_{\ell}}{\sqrt{P}}Y_{t}+\hat{\mu}_{A_{t}}.$

#### Phase 2:

Phase 2 proceeds in the same manner as the phase 2 of Algorithm 2, with
$\theta_{L+1}$ used for encoding at $\mathtt{CAS}$ and the parameter
$\eta_{L+1}$ of the $\mathtt{UCB}$ algorithm set to
$\frac{B^{2}_{L+1}}{\mathtt{SNR}}+1.$

######  Remark 7.

Equation (7) sheds some light on the reasons behind
$\mathtt{UE}\text{-}\mathtt{UCB}\text{++}$ requiring fewer uniform exploration
rounds relative to $\mathtt{UE}\text{-}\mathtt{UCB}$ to come up with mean
estimates of similar variances. Essentially, the centered reward in the
$\ell$th sub-phase has a much smaller $L_{2}$-norm than the centered reward in
the $(\ell-1)$th sub-phase. This smaller second moment allows the client to
scale the centered reward by a larger factor, leading to smaller variances for
the decoded reward. This, in turn, leads to mean estimates formed in that sub-
phase to have smaller variances or, in other words, are more accurate. Then,
in the $(\ell+1)$th sub-phase, since we center the rewards around these more
accurate mean estimates, the centered rewards have even smaller $L_{2}$ norms.
This positive reinforcement cycle leads to the variance of the mean estimates
decreasing exponentially with respect to sub-phases, which, in turn, leads to
much fewer uniform exploration rounds to come up with mean estimates with the
same variance as those after phase 1 of $\mathtt{UE}\text{-}\mathtt{UCB}.$

$\mathtt{UE}\text{-}\mathtt{UCB}\text{++}$, along with its interaction with
$\mathtt{CAS}$, is described in Algorithm 3.

######  Theorem 4.3.

For all bandit instances $\nu\in\mathcal{E}$, the
$\mathtt{UE}\text{-}\mathtt{UCB}\text{++}$ bandit algorithm along with
$\mathtt{CAS}$ encoding algorithm as described in Algorithm (3) satisfies the
power constraint (1) at all rounds and has the following regret guarantee:

$\displaystyle
R_{T}(\nu,\mathtt{UE}\text{-}\mathtt{UCB}\text{++},\mathtt{CAS})\leq\frac{8KB\log
B}{\mathtt{SNR}\wedge
1}+6KB+8\sqrt{\left(\frac{4}{\mathtt{SNR}}+1\right)}\cdot\sqrt{KT\ln T}.$

The key to the proof of Theorem 4.3 is to show that the second moment of the
centered rewards $X_{t,A_{t}}-\hat{\mu}_{\ell-1,A_{t}}$ is less than
$B_{\ell},$ $\ell\in[L],$ when round $t$ belongs to the $\ell$th sub-phase of
phase 1, and when round $t$ belongs to phase 2, it is less than $B_{L+1}.$
Similar arguments as in the proof of Theorem 4.2 can show this. We defer the
details to the Appendix.

######  Remark 8.

The $\ln T$ factor in the third term of Theorem 4.3 can be removed by using
MOSS [3] instead of the $\mathtt{UCB}$ algorithm. Our work focuses on
understanding how the regret grows as a function of $\mathtt{SNR}$; we are not
as concerned with logarithmic factors in $T.$ Hence, we chose the more popular
$\mathtt{UCB}$ algorithm.

##  5 Concluding Remarks

The near-optimal Algorithm 3 use a highly adaptive encoding protocol, where
the history of the game was used to refine the encoding in a particular round.
On the other hand, [1] showed for distributed convex, Lipschitz optimization
under information constraints, a fixed, non-adaptive encoding protocol gives
optimal performance. This suggests an interesting distinction between encoding
for distributed sequential decision-making problems and distributed
optimization problems.

An interesting open problem is closing the additive $\frac{8KB\log
B}{\mathtt{SNR}\wedge 1}$ gap between our upper and lower bound. Furthermore,
the refinement to our model where the learner-to-client communication is also
over an AWGN channel and the multi-client setting are interesting future
research directions.

## Acknowledgement

This work is supported by the Singapore National Research Foundation (NRF)
Fellowship programme (Grant Numbers: A-0005077-01-00 and A-0008064-00-00) and
an MOE Tier 1 Grant (Grant Number: A-0009042-01-00).

## References

  * [1] J. Acharya, C. Canonne, P. Mayekar, and H. Tyagi, “Information-constrained optimization: can adaptive processing of gradients help?” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 7126–7138, 2021.
  * [2] M. M. Amiri and D. Gündüz, “Machine learning at the wireless edge: Distributed stochastic gradient descent over-the-air,” _IEEE Transactions on Signal Processing_ , vol. 68, pp. 2155–2169, 2020.
  * [3] J.-Y. Audibert and S. Bubeck, “Minimax policies for adversarial and stochastic bandits.” in _COLT_ , vol. 7, 2009, pp. 1–122.
  * [4] P. Auer, N. Cesa-Bianchi, and P. Fischer, “Finite-time analysis of the multiarmed bandit problem,” _Machine learning_ , vol. 47, no. 2, pp. 235–256, 2002.
  * [5] S. Boucheron, G. Lugosi, and P. Massart, _Concentration inequalities: A nonasymptotic theory of independence_. Oxford university press, 2013.
  * [6] T. M. Cover and J. A. Thomas, _Elements of Information Theory. 2nd edition_. John Wiley & Sons Inc., 2006\.
  * [7] I. Csiszár, P. C. Shields _et al._ , “Information theory and statistics: A tutorial,” _Foundations and Trends® in Communications and Information Theory_ , vol. 1, no. 4, pp. 417–528, 2004.
  * [8] S. Dragomir, “Upper and lower bounds for csiszár’s f-divergence in terms of the kullback-leibler distance and applications,” _Inequalities for the Csiszár’s_ , 2000.
  * [9] C. Dwork, A. Roth _et al._ , “The algorithmic foundations of differential privacy,” _Foundations and Trends® in Theoretical Computer Science_ , vol. 9, no. 3–4, pp. 211–407, 2014.
  * [10] V. Gandikota, D. Kane, R. K. Maity, and A. Mazumdar, “vqsgd: Vector quantized stochastic gradient descent,” _ICML Workshop on Security and Privacy in Machine Learning)_ , 2019.
  * [11] 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.
  * [12] S. K. Jha, P. Mayekar, and H. Tyagi, “Fundamental limits of over-the-air optimization: Are analog schemes optimal?” _IEEE Journal on Selected Areas in Information Theory_ , vol. 3, no. 2, pp. 217–228, 2022.
  * [13] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings _et al._ , “Advances and open problems in federated learning,” _Foundations and Trends® in Machine Learning_ , vol. 14, no. 1–2, pp. 1–210, 2021\.
  * [14] J. Konečný, H. B. McMahan, F. X. Yu, P. Richtarik, A. T. Suresh, and D. Bacon, “Federated learning: Strategies for improving communication efficiency,” _NIPS Workshop on Private Multi-Party Machine Learning_ , 2016\.
  * [15] T. Lattimore and C. Szepesvári, _Bandit Algorithms_. Cambridge University Press, 2020.
  * [16] C.-Y. Lin, V. Kostina, and B. Hassibi, “Differentially quantized gradient descent,” in _IEEE International Symposium on Information Theory (ISIT)_ , 2021, pp. 1200–1205.
  * [17] P. Mayekar and H. Tyagi, “RATQ: A universal fixed-length quantizer for stochastic optimization,” _IEEE Transactions on Information Theory_ , 2020\.
  * [18] A. Mitra, H. Hassani, and G. J. Pappas, “Linear stochastic bandits over a bit-constrained channel,” _arXiv preprint arXiv:2203.01198_ , 2022.
  * [19] A. Mitra, R. Jaafar, G. J. Pappas, and H. Hassani, “Linear convergence in federated learning: Tackling client heterogeneity and sparse gradients,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 14 606–14 619, 2021.
  * [20] C. E. Shannon, “A mathematical theory of communication,” _The Bell System Technical Journal_ , vol. 27, no. 4, pp. 623–656, 1948.
  * [21] D. Tse and P. Viswanath, _Fundamentals of wireless communication_. Cambridge University Press, 2005.

##  Appendix A Proof of Theorem 4.3 (Regret bound of
$\mathtt{UE}\text{-}\mathtt{UCB}\text{++}$)

We will first show that the centered rewards transmitted by the client satisfy
the power constraint. Note that the centered reward coded by the client at any
round in the $\ell$th sub-phase of phase 1 is
$X_{t,A_{t}}-\hat{\mu}_{\ell-1,A_{t}}$. Furthermore, the client scales the
reward by a factor of $\frac{\sqrt{P}}{B_{\ell}}$. Thus, we need to show that
$\mathbb{E}\left[(X_{t,A_{t}}-\hat{\mu}_{\ell-1,A_{t}})^{2}\right]\leq
B^{2}_{\ell}$. Towards proving this, we write

$\displaystyle\mathbb{E}\left[(X_{t,A_{t}}-\hat{\mu}_{\ell-1,A_{t}})^{2}\right]$
$\displaystyle=\mathbb{E}\left[(X_{t,A_{t}}-\mu_{A_{t}})^{2}\right]+\mathbb{E}\left[(\hat{\mu}_{\ell-1,A_{t}}-\mu_{A_{t}})^{2}\right]$
$\displaystyle\leq
1+\mathbb{E}\left[(\hat{\mu}_{\ell-1,A_{t}}-\mu_{A_{t}})^{2}\right].$

From the description of Algorithm 3, for $k\in[K],$ we have

$\displaystyle\hat{\mu}_{\ell-1,k}=\frac{1}{\tau}\sum_{t=(\ell-2)K\tau+(k-1)\tau+1}^{(\ell-2)K\tau+k\tau}\left(X_{t,k}+\frac{B_{\ell-1}}{\sqrt{P}}Z_{t}\right).$

Therefore, we have

$\displaystyle\mathbb{E}\left[(\hat{\mu}_{\ell,A_{t}}-\mu_{A_{t}})^{2}\right]\leq\frac{\frac{B_{\ell-1}^{2}}{\mathtt{SNR}}+1}{\tau}.$

Using the preceding inequalities and definition of $B_{\ell}$ in (7), we get

$\displaystyle\mathbb{E}\left[(X_{t,A_{t}}-\mu_{\ell-1,A_{t}})^{2}\right]\leq
1+\frac{\frac{B_{\ell-1}^{2}}{\mathtt{SNR}}+1}{\tau}=B_{\ell}^{2}.$

To prove that the power constraint is satisfied in the second phase, note that
the centered reward transmitted by the client in the second phase is
$X_{t,A_{t}}-\hat{\mu}_{L,A_{t}}.$ Furthermore, client scales the reward by a
factor of $\frac{\sqrt{P}}{B_{L+1}}.$ By precisely the same arguments as
above, we can deduce that
$\mathbb{E}\left[(X_{t,A_{t}}-\hat{\mu}_{L,A_{t}})^{2}\right]\leq
B_{L+1}^{2}$.

To bound the regret, first note that we incur linear regret in phase 1 of
$\mathtt{UE}\text{-}\mathtt{UCB}\text{++}$. Specifically, since the time
horizon for phase 1 is $\frac{4K\log B}{\mathtt{SNR}\wedge 1}$ and each
round’s regret is at the most $2B$, we incur a total regret of $\frac{8KB\log
B}{\mathtt{SNR}\wedge 1}$ in the first phase.

To bound the regret in the second phase, note that the centered reward
estimate $\tilde{X}_{t,A_{t}}-\mu_{A_{t}}$ in the second phase is subgaussian
with a variance factor of $\frac{B^{2}_{L+1}}{\mathtt{SNR}}+1.$ Substituting
the value of $\tau$ from (6) in (7), we obtain

$\displaystyle B^{2}_{\ell+1}$
$\displaystyle=\frac{\frac{B^{2}_{\ell}}{\mathtt{SNR}}+1}{\tau}+1$
$\displaystyle\leq\frac{B^{2}_{\ell}}{2}+\frac{\mathtt{SNR}\wedge 1}{2}+1.$

Rearranging the terms, we have

$\displaystyle B^{2}_{\ell+1}-2\left(\frac{\mathtt{SNR}\wedge
1}{2}+1\right)\leq\frac{B^{2}_{\ell}-2\left(\frac{\mathtt{SNR}\wedge
1}{2}+1\right)}{2}.$

Recursively applying the above identity, it follows that

$\displaystyle B^{2}_{L+1}-2\left(\frac{\mathtt{SNR}\wedge
1}{2}+1\right)\leq\frac{B^{2}-2\left(\frac{\mathtt{SNR}\wedge
1}{2}+1\right)}{2^{L}}.$

Substituting $L=2\log B,$ we get $B^{2}_{L+1}$ less than $4$.

The proof is then completed by using Lemma 2.2 to bound the regret in the
second phase and adding the regret from the first phase.

##  Appendix B Proof of Theorem 3.1 (Lower Bound)

We will first show that for $T\geq c_{2}K$ and a universal constant
$c_{1}\in(0,1),$ we have

$R_{T}^{\ast}(\mathtt{SNR})\geq c_{1}KB.$

From the definition of $R_{T}^{\ast}(\mathtt{SNR})$ in (4), it is enough to
prove a lower bound on the average regret when the problem instances are
uniformly chosen from a subset of $\mathcal{E}.$ We choose that finite subset
to be the instances where a single arm has deterministic reward $B$, and the
others deterministic $-B$. Therefore, we have $K$ different instances with the
probability of each instance occurring being $1/K.$ Now, observe that
regardless of the algorithm, the probability of finding the $B$-reward arm is
at the most $\frac{1}{2}$ in the first $\lfloor K/2\rfloor$ arm pulls. Hence
the regret in the first $\lfloor K/2\rfloor$ arm pulls when averaged over the
$K$ instances must be at least $\frac{1}{2}\cdot\lfloor K/2\rfloor\cdot
2B=c_{1}KB.$

In the rest of proof we will show that for
$T\geq\frac{c_{2}K}{\frac{1}{2}\log(1+\mathtt{SNR})\wedge 1},$ we have

$\displaystyle R^{\ast}_{T}(\mathtt{SNR})\geq
c_{1}\left(\sqrt{KT}\cdot\frac{1}{\sqrt{\mathtt{SNR}\wedge 1}}\right).$ (8)

Then, noting that both the bounds hold for
$T\geq\frac{c_{2}K}{\frac{1}{2}\log(1+\mathtt{SNR})\wedge 1}$ and using the
fact that $a\vee b\geq\frac{a+b}{2}$ completes the proof.

Consider the bandit instance $\nu$ where rewards for each arm pull are either
$-1$ or $1$ and the arms have the following means: $\mu_{1}=\Delta$, and
$\mu_{i}=0$ for all $i\in\\{2,\ldots,K\\},$ where $\Delta$ is some parameter
in $(0,1/4)$ whose precise value we will set later. Using the fact that
rewards for all arms lie in $[-1,1]$ and by Hoeffding’s lemma [5, Lemma 2.2],
it is easy to see that the centered rewards for all arms are subgaussian with
a variance factor of 1. Therefore, it follows that $\nu\in\mathcal{E}.$ Now,
fix a bandit algorithm $\pi\in\Pi_{T}$ and an encoding scheme
$C^{T}\in\mathcal{C}^{T}.$ Denote by $P^{T}$ the probability distribution of
the sequence $(A_{1},Y_{1},A_{2},Y_{2},\ldots,A_{T},Y_{T})$ induced by the
algorithm $\pi$ and encoding strategy $C^{T}$ on the instance $\nu$.

Denote by $N_{i}(T)$ the number of times arm $i$ has been played up to and
including round $T$. Let

$j=\operatorname*{arg\,min}_{i>1}\mathbb{E}_{P^{T}}\left[N_{i}(T)\right].$

That is, $j$ is the arm pulled least amount of times from the arms
$\\{2,\ldots,K\\}.$ Trivially,

$\displaystyle\mathbb{E}_{P^{T}}\left[N_{i}(T)\right]\leq\frac{T}{K-1}.$ (9)

Now consider another bandit instance $\nu^{\prime}$ where again the rewards
are either $-1$ or $1$ with the following means: $\mu_{1}=\Delta$,
$\mu_{j}=2\Delta$, $\mu_{i}=0$ for all $i\in\\{2,\ldots,K\\}\setminus\\{j\\}.$
Let $Q^{T}$ be the the probability distribution of the sequence
$(A_{1},Y_{1},A_{2},Y_{2},\ldots,A_{T},Y_{T})$ induced by the algorithm $\pi$
and encoding strategy $C$ on the instance $\nu^{\prime}$.

By a simple calculation, we have

$R_{T}(\nu,\pi,C)\geq\frac{T\Delta}{2}P^{T}(N_{1}(T)\leq
T/2)\quad\text{and}\quad
R_{T}(\nu^{\prime},\pi,C)\geq\frac{T\Delta}{2}Q^{T}(N_{1}(T)>T/2).$

Combining the two inequalities, using the variational formula for total
variation distance, and applying Pinsker’s inequality, we get

$\displaystyle R_{T}(\nu,\pi,C)+R_{T}(\nu^{\prime},\pi,C)$
$\displaystyle\geq\frac{T\Delta}{2}\left(P^{T}(N_{1}(T)\leq
T/2)+Q^{T}(N_{1}(T)>T/2)\right)$
$\displaystyle=\frac{T\Delta}{2}\left(1-(P^{T}(N_{1}(T)>T/2)-Q^{T}(N_{1}(T)>T/2))\right)$
$\displaystyle\geq\frac{T\Delta}{2}\left(1-\mathrm{d_{TV}}(P^{T},Q^{T})\right)$
$\displaystyle\geq\frac{T\Delta}{2}\left(1-\sqrt{\frac{1}{2}D(P^{T}\mid\mid
Q^{T})}\right).$ (10)

Note that $P^{T}$ and $Q^{T}$ differ only when arm $j$ is played. Recall that
the dependence of $Y$ on an encoding strategy $C$ and reward $X$ is given by
(2). For encoding scheme $C$, used in a round $t$, denote by $C(\cdot\mid x)$
the conditional distribution of $Y$ given that the reward is $X=x$. Let
$p_{j}\circ C$ and $q_{j}\circ C$ denote the distribution of $Y$ when arm $j$
is played at round $t$. Recalling the reward distribution for arm $j$, it
follows that,

$\displaystyle(p_{j}\circ C)(Y=y)$ $\displaystyle=\frac{C(y\mid
1)}{2}+\frac{C(y\mid-1)}{2}\quad\text{and}$ $\displaystyle(q_{j}\circ C)(Y=y)$
$\displaystyle=\frac{C(y\mid 1)}{2}+\frac{C(y\mid-1)}{2}+\Delta(C(y\mid
1)-C(y\mid-1)).$

Moreover, using similar arguments as in [15, Lemma 15.1], we can prove the
following lemma.

######  Lemma B.1.

$D(P^{T}\mid\mid
Q^{T})\leq\mathbb{E}_{P^{T}}\left[N_{j}(T)\right]\cdot\sup_{C\in\mathcal{C}}D(p_{j}\circ
C\mid\mid q_{j}\circ C)$

We defer the proof the Lemma to Appendix C and proceed with proving the lower
bound. Combining Lemma B.1 with (9), we have

$\displaystyle D(P^{T}\mid\mid Q^{T})$
$\displaystyle\leq\frac{T}{K-1}\sup_{C\in\mathcal{C}}D(p_{j}\circ C\mid\mid
q_{j}\circ C).$

We will now use the following fact.

######  Fact 1.

Recall that
$d_{\chi^{2}}(p,q)\coloneqq\int\frac{(p(x)-q(x))^{2}}{q(x)}\mathrm{d}x$
denotes the $\chi^{2}$ distance between probability measures $p$ and $q$ when
they are absolutely continuous with respect to the Lebesgue measure
$\mathrm{d}x$. Then, it holds that

$D(p\mid\mid q)\leq d_{\chi^{2}}(p,q).$

Fact 1 is well known (see, for instance [7]]), but we provide a short proof in
Appendix C for completeness.

Using this fact, $D(p_{j}\circ C\mid\mid q_{j}\circ C)$ can be bounded as
follows:

$\displaystyle\mathrm{D}(p_{i}\circ C\mid\mid q_{i}\circ C)$
$\displaystyle\leq d_{\chi^{2}}(p_{i}\circ C,q_{i}\circ C)$
$\displaystyle=\int\frac{(p_{i}\circ C-q_{i}\circ C)^{2}}{q_{i}\circ
C}\,\mathrm{d}y$ $\displaystyle=\Delta^{2}\int\frac{(C(y\mid
1)-C(y\mid-1))^{2}}{\frac{C(y\mid 1)}{2}+\frac{C(y\mid-1)}{2}+\Delta(C(y\mid
1)-C(y\mid-1))}\,\mathrm{d}y$

Now note that for $\Delta\leq 1/4,$ we have $\frac{C(y\mid
1)}{2}+\frac{C(y\mid-1)}{2}+\Delta(C(y\mid 1)-C(y\mid-1))\geq\frac{C(y\mid
1)}{4}+\frac{C(y\mid-1)}{4}.$ Using this fact, we get

$\displaystyle\mathrm{D}(p_{i}\circ C\mid\mid q_{i}\circ C)$
$\displaystyle\leq 2\Delta^{2}\int\frac{(C(y\mid
1)-C(y\mid-1))^{2}}{\frac{C(y\mid 1)}{2}+\frac{C(y\mid-1)}{2}}\,\mathrm{d}y$
$\displaystyle=2\Delta^{2}\left(\frac{1}{2}d_{\chi^{2}}(C(\cdot\mid
1),C(\cdot\mid 1)/2+C(\cdot\mid-1)/2)\right.$ $\displaystyle\hskip
85.35826pt\left.+\frac{1}{2}d_{\chi^{2}}(C(\cdot\mid-1),C(\cdot\mid
1)/2+C(\cdot\mid-1)/2)\right)$ $\displaystyle\leq
4\Delta^{2}\left(\frac{1}{2}\mathrm{D}(C(\cdot\mid 1)\mid\mid C(\cdot\mid
1)/2+C(\cdot\mid-1)/2)\right.$ $\displaystyle\hskip
85.35826pt\left.+\frac{1}{2}\mathrm{D}(C(\cdot\mid-1)\mid\mid C(\cdot\mid
1)/2+C(\cdot\mid-1)/2)\right),$

where the equality is easily verified by substituting the definition
$d_{\chi^{2}}$ and the last inequality uses the following fact.

To proceed further, we will use the following fact.

######  Fact 2.

If $\frac{\mathrm{d}P}{\mathrm{d}Q}(x)\leq c\quad\forall x\in\mathbb{R}$, then

$d_{\chi^{2}}(P,Q)\leq cD(P\mid\mid Q).$

Fact 2 is also known [8], but we provide a proof in Appendix C for
completeness.

Denote by $V$ a hypothetical reward that takes values $-1$ and $1$ with equal
probability, and by $Y$ the output of the AWGN channel when $V$ is further
coded to $C(V)$ to satisfy (1) and transmitted over the AWGN channel. Then,

$\frac{1}{2}\mathrm{D}(C(\cdot\mid 1)\mid\mid C(\cdot\mid
1)/2+C(\cdot\mid-1)/2)+\frac{1}{2}\mathrm{D}(C(\cdot\mid-1)\mid\mid
C(\cdot\mid 1)/2+C(\cdot\mid-1)/2)$

is mutual information between $V$ and $Y$, denoted by $I(V;Y).$ To see this,
note that $I(W_{1};W_{2})\coloneqq D(P_{W_{1},W_{2}}\mid\mid P_{W_{1}}\times
P_{W_{2}})=\mathbb{E}_{P_{W_{1}}}\left[D(P_{W_{2}|W_{1}}\mid\mid
P_{W_{2}})\right].$

We have therefore shown that

$\displaystyle D(P^{T}\mid\mid
Q^{T})\leq\frac{4\Delta^{2}T}{K-1}\sup_{C\in\mathcal{C}}I(V;Y).$ (11)

Note that $I(V;Y)\leq H(V)\leq\ln 2.$ Since $V-C(V)-Y$ forms a Markov chain in
this order, by the data processing inequality [6, Chapter 2], we have that

$\displaystyle I(V;Y)\leq I(C(V);Y).$

Then, using the fact that $I(C(V);Y)$ can be further upper bounded by the
capacity of an AWGN channel [6, Chapter 9], we have

$\displaystyle
I(C(V);Y)\leq\frac{1}{2}\ln(1+\mathtt{SNR})=\frac{1}{2}\log(1+\mathtt{SNR})\cdot\ln
2.$

Thus, we have shown that

$\displaystyle D(P^{T}\mid\mid Q^{T})\leq\frac{4\ln
2\cdot\Delta^{2}T}{K-1}\left(\frac{1}{2}\log(1+\mathtt{SNR})\wedge 1\right).$

Substituting this into (10), we get

$\displaystyle
R_{T}(\nu,\pi,C)+R_{T}(\nu^{\prime},\pi,C)\geq\frac{T\Delta}{2}\left(1-\sqrt{\frac{4\ln
2\cdot\Delta^{2}T}{K-1}\left(\frac{1}{2}\log(1+\mathtt{SNR})\wedge
1\right)}\right).$

Setting $\Delta^{2}=\frac{K-1}{16\ln 2\cdot
T\left(\frac{1}{2}\log(1+\mathtt{SNR})\wedge 1\right)}$ completes the proof.
(Note that we can only set such a $\Delta$ and ensure that
$\Delta\leq\frac{1}{4}$, if $T\geq\frac{K-1}{\ln
2\left(\frac{1}{2}\log(1+\mathtt{SNR})\wedge 1\right)},$ which is the reason
we need this condition in the statement of our lower bound.)

We will now show that for $T\geq\frac{K-1}{\ln
2\left(\frac{1}{2}\log(1+\mathtt{SNR})\wedge 1\right)}\geq K$ and for a
universal constant $c,$ we have

$R_{T}^{\ast}(\mathtt{SNR})\geq cKB.$

In fact, we show the stronger bound

$R_{K}^{\ast}(\mathtt{SNR})\geq cKB.$

Then, using the fact that $a\vee b\geq\frac{a+b}{2}$ completes the proof.

We now choose our instance $\nu$ where rewards for each arm pull are Gaussian
with variance $1$ and the following means: $\mu_{1}=1,$ $\mu_{i}=0$ for all
$i\in\\{2,\ldots,K\\}.$ Once again, let $j$ be the arm pulled least amount of
times. Then define the alternate instance $\nu^{\prime}$ where rewards for
each arm pull are Gaussian with variance $1$ and the following means:
$\mu_{1}=B/2,\mu_{j}=B-1,\mu_{i}=0$ for all $i\in\\{2,\ldots,K\\}/{j}.$ All
the arm rewards have Gaussian distribution with the variance 1 and means
stated above. Proceeding as earlier, we have

$\displaystyle R_{T}(\nu,\pi,C)+R_{T}(\nu^{\prime},\pi,C)$
$\displaystyle\geq\frac{T\Delta}{2}\left(1-\mathrm{d_{TV}}(P^{T},Q^{T})\right)$

Using the fact that $T\geq\frac{K-1}{\ln
2\left(\frac{1}{2}\log(1+\mathtt{SNR})\wedge 1\right)}\geq c(K-1)$ and the
fact that for our chosen distributions $1-\mathrm{d_{TV}}(P^{T},Q^{T})$ is a
constant completes the proof.

######  Remark 9.

(Communication-constrained setting of [11]) We now remark on possibility of
recovering the lower bound in [11] with our proof technique, albeit with
weaker constants. Note that (10) also holds for the setting considered in
[11], where the output $Y$ is restricted to $r$ bits. Therefore, $I(V;Y)\leq
H(Y)\wedge H(V)=(\ln 2)(r\wedge 1)$. Proceeding, in the rest of the proof,
mutatis mutandis, we get that the regret in this setting is bounded by
$\Omega(\sqrt{KT}\cdot\frac{1}{r\wedge 1}).$ Such a lower bound suggests that
even when using code of length 1 to encode our rewards, it might be possible
to achieve the regret of the centralized setting. This is indeed shown to be
possible by the scheme in [11].

##  Appendix C Proofs of Intermediary Results in the Proof of Theorem 3.1

### Proof of Lemma B.1

We prove the inequality by similar arguments as in [15, Lemma 15.1].

Recall that $H_{t}=\\{A_{1},Y_{1},\ldots,A_{t},Y_{t}\\}$ denotes the history
of the game till time $t$. Also recall that the hint $S_{t}$ is a function of
history of the game till time $t-1$. Therefore the encoding scheme at time $t$
depends on $H_{t-1}$, so we write it as $C_{H_{t-1}}.$ We additionally denote
by $p_{A_{t}}$ and $q_{A_{t}}$ the distribution of reward $X_{t,A_{t}}$ under
instances $\nu$ and $\nu^{\prime},$ respectively. Therefore, $p_{A_{t}}\circ
C_{H_{t-1}}$ and $q_{A_{t}}\circ C_{H_{t-1}}$ denote distribution of $Y_{t}$
for an arm pull $A_{t}$ and history $H_{t-1}$ under instances $\nu$ and
$\nu^{\prime},$ respectively.

Using the definition of KL divergence, we have

$\displaystyle D(P^{T}\mid\mid Q^{T})$
$\displaystyle=\mathbb{E}_{P^{T}}\left[\log\left(\frac{P^{T}(A_{1},Y_{1},\ldots,A_{T},Y_{T})}{Q^{T}(A_{1},Y_{1},\ldots,A_{T},Y_{T})}\right)\right]$
$\displaystyle=\sum_{t=1}^{T}\mathbb{E}_{P^{T}}\left[\log\frac{P^{T}(A_{t},Y_{t}\mid
H_{t-1})}{Q^{T}(A_{t},Y_{t}\mid H_{t-1})}\right].$ (12)

By the definition of the bandit algorithm $\pi,$ the distribution over all
actions to be played remains the same for different problem instances as long
as the history is the same. Therefore,

$\displaystyle\frac{P^{T}(A_{t},Y_{t}\mid H_{t-1})}{Q^{T}(A_{t},Y_{t}\mid
H_{t-1})}$ $\displaystyle=\frac{P^{T}(A_{t}\mid H_{t-1})}{Q^{T}(A_{t}\mid
H_{t-1})}\cdot\frac{P^{T}(Y_{t}\mid A_{t},H_{t-1})}{Q^{T}(Y_{t}\mid
A_{t},H_{t-1})}$ $\displaystyle=\frac{P^{T}(Y_{t}\mid
A_{t},H_{t-1})}{Q^{T}(Y_{t}\mid A_{t},H_{t-1})}.$

Substituting the above identity in (C), we have

$\displaystyle D(P^{T}\mid\mid Q^{T})$
$\displaystyle=\sum_{t=1}^{T}\mathbb{E}_{P^{T}}\left[\log\frac{P^{T}(Y_{t}\mid
A_{t},H_{t-1})}{Q^{T}(Y_{t}\mid A_{t},H_{t-1})}\right]$
$\displaystyle=\sum_{t=1}^{T}\mathbb{E}_{P^{T}}\left[\mathbb{E}_{P^{T}}\left[\left.\log\frac{P^{T}(Y_{t}\mid
A_{t},H_{t-1})}{Q^{T}(Y_{t}\mid
A_{t},H_{t-1})}\right|A_{t},H_{t-1}\right]\right]$
$\displaystyle=\sum_{t=1}^{T}\mathbb{E}_{P^{T}}\left[D(p_{A_{t}}\circ
C_{H_{t-1}}\mid\mid q_{A_{t}}\circ C_{H_{t-1}})\right],$

where the second last inequality uses the law of iterated expectations and the
final one uses the definition of KL divergence.

Since $p_{A_{t}}$ and $q_{A_{t}}$ differ only when arm $A_{t}=j,$ we have

$\displaystyle D(P^{T}\mid\mid Q^{T})$
$\displaystyle=\sum_{t=1}^{T}\mathbb{E}_{P^{T}}\left[\mathbf{1}_{A_{t}=j}D(p_{j}\circ
C_{H_{t-1}}\mid\mid q_{j}\circ C_{H_{t-1}})\right]$
$\displaystyle\leq\sum_{t=1}^{T}\mathbb{E}_{P^{T}}\left[\mathbf{1}_{A_{t}=j}\sup_{C\in\mathcal{C}}D(p_{j}\circ
C\mid\mid q_{j}\circ C)\right]$
$\displaystyle\leq\mathbb{E}_{P^{T}}{[N_{j}(T)]}\cdot\sup_{C\in\mathcal{C}}D(p_{j}\circ
C\mid\mid q_{j}\circ C)$
$\displaystyle\leq\frac{T}{K-1}\sup_{C\in\mathcal{C}}D(p_{j}\circ C\mid\mid
q_{j}\circ C).$

∎

###  C.1 Proof of Fact 1

Using the fact that $\ln x\leq x-1$ and
$\int\big{(}p(x)-q(x)\big{)}\mathrm{d}x=0$ , we have

$\displaystyle D(p\mid\mid q)$ $\displaystyle=\int
p(x)\ln\frac{p(x)}{q(x)}\mathrm{d}x-\int\left(p(x)-q(x)\right)\mathrm{d}x$
$\displaystyle\leq\int
p(x)\left(\frac{p(x)}{q(x)}-1\right)\mathrm{d}x-\int\left(p(x)-q(x)\right)\mathrm{d}x$
$\displaystyle=\int\frac{(p(x)-q(x))^{2}}{q(x)}\mathrm{d}x$
$\displaystyle=d_{\chi^{2}}(p,q).$

∎

###  C.2 Proof of Fact 2

We have

$\displaystyle d_{\chi^{2}}(p,q)$
$\displaystyle=\int\frac{(p(x)-q(x))^{2}}{q(x)}\mathrm{d}x$
$\displaystyle=\int
p(x)\left(\frac{p(x)}{q(x)}-1\right)\mathrm{d}x-\int\left(p(x)-q(x)\right)\mathrm{d}x$
$\displaystyle\leq\int
p(x)\cdot\frac{p(x)}{q(x)}\cdot\ln\frac{p(x)}{q(x)}\mathrm{d}x$
$\displaystyle\leq c\int p(x)\ln\frac{p(x)}{q(x)}\mathrm{d}x=cD(p\mid\mid q),$

where the fist inequality follows by using the fact that $\frac{x-1}{x}\leq\ln
x\quad\forall x\geq 0$ and $\int\left(p(x)-q(x)\right)\mathrm{d}x=0$ and the
second inequality follows from the fact that
$\frac{\mathrm{d}P}{\mathrm{d}Q}(x)\leq c\quad\forall x\in\mathbb{R}.$

∎