# Linear Stochastic Bandits over a Bit-Constrained Channel

Aritra Mitra, Hamed Hassani, and George J. Pappas The authors are with the
Department of Electrical and Systems Engineering, University of Pennsylvania.
Email: {amitra20, hassani<EMAIL_ADDRESS>This work was supported by
NSF Award 1837253, NSF CAREER award CIF 1943064, and the Air Force Office of
Scientific Research Young Investigator Program (AFOSR-YIP) under award
FA9550-20-1-0111.

###### Abstract

One of the primary challenges in large-scale distributed learning stems from
stringent communication constraints. While several recent works address this
challenge for static optimization problems, sequential decision-making under
uncertainty has remained much less explored in this regard. Motivated by this
gap, we introduce a new linear stochastic bandit formulation over a bit-
constrained channel. Specifically, in our setup, an agent interacting with an
environment transmits encoded estimates of an unknown model parameter to a
server over a communication channel of finite capacity. The goal of the server
is to take actions based on these estimates to minimize cumulative regret. To
this end, we develop a novel and general algorithmic framework that hinges on
two main components: (i) an adaptive encoding mechanism that exploits
statistical concentration bounds, and (ii) a decision-making principle based
on confidence sets that account for encoding errors. As our main result, we
prove that when the unknown model is $d$-dimensional, a channel capacity of
$O(d)$ bits suffices to achieve order-optimal regret. To demonstrate the
generality of our approach, we then show that the same result continues to
hold for non-linear observation models satisfying standard regularity
conditions. Finally, we establish that for the simpler unstructured multi-
armed bandit problem, $1$ bit channel-capacity is sufficient for achieving
optimal regret bounds. Overall, our work takes a significant first step
towards paving the way for statistical decision-making over finite-capacity
channels.

##  1 Introduction

In modern distributed computing paradigms such as federated learning (FL), a
group of agents typically interact with a parameter server to train a common
statistical model. A major bottleneck in such settings is the network
communication cost of uploading (potentially high-dimensional) models and
gradient vectors to the server. Motivated by this emerging concern, several
works draw on ideas from quantization theory [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
sparsification [11, 12, 13, 14, 15, 16, 17, 18, 19], and rate-distortion
theory [20] to design communication-efficient algorithms that achieve a
desired level of precision while exchanging as few bits as possible. This rich
body of work contributes significantly to the study of static optimization
problems under communication constraints. Nonetheless, there remains a
considerable gap in our understanding of similar questions when it comes to
sequential decision-making under uncertainty (e.g., bandit problems and
reinforcement learning). Our primary goal in this paper is to bridge the above
gap.

A common abstraction for analyzing optimization under limited communication is
one where a worker agent transmits quantized gradients to a server over a
finite bit-rate communication channel [21, 22, 23]. Inspired by this model,
for our problem of interest, we introduce and study a new linear stochastic
bandit formulation comprising of an agent connected to a decision-making
entity (server) by a noiseless communication channel of finite capacity $B$;
see Fig. 1. The agent interacts with an environment and observes noisy rewards
that depend linearly on an unknown parameter vector
$\theta_{*}\in\mathbb{R}^{d}$. It then encodes and transmits finite-precision
estimates of $\theta_{*}$ to the server. Based on these estimates, the role of
the server is to play a sequence of actions that maximizes the sum of rewards
accrued over a time horizon $T$ \- a performance metric captured by cumulative
regret.111A formal description of our setup is provided in Section 2. Notably,
the agent can only transmit encoded estimates of the parameter vector, but not
the rewards themselves. The reason for this is twofold. First, our formulation
is motivated by the popular federated learning framework [24] where due to
privacy concerns, agents exchange their local models with the server instead
of their raw observations. In our setup, the parameter vector is the model and
the rewards are the observations. Second, our goal is to build a theory that
is eventually applicable to multi-agent decision-making. For such settings, it
is more natural for the server to perform fusion on the agents’ local models
instead of directly fusing observations that may belong to different signal
spaces.

The main technical challenge in our setup arises from the fact that the
channel from the agent to the server introduces additional uncertainty into
the decision-making process. Unless accounted for carefully, the instantaneous
encoding errors resulting from such uncertainty can accumulate over time and
lead to sub-optimal regret bounds. Given this challenge, the central question
we investigate is the following.

Under what conditions on the channel capacity $B$ can we achieve the order-
optimal regret bound $\tilde{O}(d\sqrt{T})$?222When the channel has infinite
capacity, i.e., when $B=\infty$, $\tilde{O}(d\sqrt{T})$ regret is known to be
optimal; see Chapter 24 of [25] for further details on this topic.

In this work, we rigorously answer the above question via a set of algorithmic
and theoretical contributions discussed below.

$\bullet$ Algorithmic Contributions. For the setting of interest, we develop a
novel framework for statistical decision-making under communication
constraints. Our approach hinges on two main components. The first is an
adaptive quantization mechanism that encodes the change (innovation) in
successive estimates of $\theta_{*}$ at the agent. The main intuition here is
that with high probability, the gap between successive model estimates shrinks
over time; as a result, the innovation signals are contained in balls of
progressively smaller radii. Thus, roughly speaking, to achieve the same
precision, it takes fewer bits to encode the innovation signals as compared to
the model estimates (that can be of a much larger magnitude). A key feature of
our encoding scheme is that the dynamic quantizer ranges are designed based on
statistical concentration bounds specific to the stochastic process we study.
As such, our encoding scheme is novel, and differs significantly from standard
quantization approaches for optimization.

The second integral component of our framework is the decision-making policy
at the server that comprises of two phases: (i) a pure exploration phase that
facilitates the estimation of $\theta_{*}$, and (ii) an information-
constrained exploration-exploitation phase. Specifically, in the latter phase,
actions are taken based on certain “inflated” confidence sets that are
carefully constructed: the radii of such sets need to be large enough to
account for the errors induced by compression. At the same time, the
compression errors need to gradually shrink to ensure that taking decisions
based on “inflated” confidence sets does not lead to sub-optimal regret
bounds. Thus, the design of the encoding scheme at the agent is tightly
coupled with the decision-making policy at the server. Notably, the
construction of the confidence sets is a key algorithmic contribution of our
work that sets it apart from communication-constrained static optimization
where a decision-making component is absent. We refer to our overall scheme as
the Information-Constrained LinUCB algorithm (IC-LinUCB).

$\bullet$ Theoretical Contributions. Our first main result (Theorem 1) reveals
that with a channel capacity $B=O(d)$ bits, IC-LinUCB guarantees a regret
bound of $\tilde{O}(d\sqrt{T})$. The main implication of this result is that
one can achieve order-optimal regret guarantees with a bit-rate that is
independent of the horizon $T$, and that depends only on the dimension $d$ of
the unknown model $\theta_{*}$. As far as we are aware, this is the first
result of its kind for linear stochastic bandits, and complements similar
results for stochastic optimization: the authors in [21] recently showed that
with $d$-dimensional quantized gradients, a bit-rate of $\tilde{O}(d)$ bits is
sufficient for achieving the optimal optimization convergence rate. On the
technical front, we note that the proof of Theorem 1 is non-trivial, and
relies on some key intermediate ideas that we outline in Section 4.

To demonstrate the generality of our approach, we significantly extend our
analysis to the generalized linear bandit setting that accounts for non-linear
observation models [26, 27]. Once again, we establish that with a bit-rate of
$O(d)$ bits, one can achieve optimal regret bounds; see Theorem 2 for a formal
statement of the result.

Finally, we ask: When the action sets have additional structure, can we
exploit such structure to achieve optimal performance with fewer than $O(d)$
bits? To answer this question, we study a special case of the linear bandit
problem where the actions are the standard orthonormal basis vectors. This
setting corresponds to the multi-armed bandit (MAB) problem with a finite
number of arms [28]. For this setting, we prove that with a bit-rate $B=1$,
one can achieve both gap-dependent (Theorem 3) and gap-independent (Theorem 4)
regret bounds matching those of the celebrated upper-confidence bound (UCB)
algorithm.

Overall, we envision that the algorithmic and analytical insights from this
work will pave the way for studying more complex statistical decision-making
problems in distributed and multi-agent settings under channel capacity
constraints.

Further Related Work. Our formulation is inspired by the classical work [29]
that studies the problem of stabilizing a linear time-invariant dynamical
system over a bit-constrained channel. There, as in our setup, the estimation
module (sensor) is separated from the decision-making module (controller) by
the channel. Aside from the fact that we study a fundamentally different
problem, our work departs from [29] in that our setup is inherently
stochastic, while the authors in [29] consider a fully deterministic setting.
In particular, while the state estimates encoded in [29] are deterministic,
the model parameter estimates that we encode in our setting are high-
dimensional random vectors.

Our work is naturally related to the seminal papers on linear stochastic
bandits [30, 31] that introduce and analyze the LinUCB algorithm. The results
in this paper extend those in [30, 31] to the communication-constrained
setting that we study. In the context of multi-agent bandits [32, 33, 34, 35,
36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47], a body of work focuses on
achieving benefits of collaboration while minimizing the number of
communication rounds [36, 40, 42, 45]. The main goal of these papers is to
achieve desirable performance while minimizing the frequency of communication.
Our focus is orthogonal - that of studying the impact of finite-precision
communication channels on the performance of bandit algorithms. As a result,
our problem formulation, algorithmic techniques, and theoretical results
differ considerably from the above strand of literature.

Notation. Given two scalars $a$ and $b$, we use $a\vee b$ and $a\wedge b$ to
represent $\max\\{a,b\\}$ and $\min\\{a,b\\}$, respectively. For any positive
integer $n$, we use $[n]$ to denote the set of integers $\\{1,\ldots,n\\}$. We
use $\mathcal{B}_{d}(0,1)$ and $\mathbb{S}^{d-1}$ to represent the
$d$-dimensional Euclidean ball and the $d$-dimensional Euclidean sphere,
respectively, of unit radius centered at the origin. Given a matrix $A$, we
use $\lambda_{\max}(A)$ and $\lambda_{\min}(A)$ to represent the largest and
smallest eigenvalues, respectively, of $A$. Moreover, we use $A^{\prime}$ to
denote the transpose of $A$. Given two symmetric positive semi-definite
matrices $A$ and $B$, we use $B\preccurlyeq A$ to imply that $A-B$ is positive
semi-definite.

##  2 Model and Problem Formulation

AgentServeraction $a_{t}$$B$-bit symbol $\sigma_{t}$ChannelObserve $y_{t}$and
encode $\theta_{*}$Decode $\theta_{*}$and play $a_{t+1}$ Figure 1: At each
round $t$, the action $a_{t}$ played by the server is sent to the agent
without any loss of information. The agent then observes a reward $y_{t}$ as
per Eq. (1), encodes an estimate of the model $\theta_{*}$, and transmits the
encoded symbol $\sigma_{t}$ back to the server under the $B$-bits per round
channel constraint. The server performs decoding and plays the next action
$a_{t+1}$.

We study a setting comprising of an agent and a decision-maker (server)
separated by a noiseless communication channel of finite capacity; see Fig. 1.
Based on all the information acquired by the server up to time-step $t-1$, it
chooses an action $a_{t}\in\mathcal{A}_{t}$ at time $t$, where
$\mathcal{A}_{t}\subset\mathbb{R}^{d}$ is the feasible decision set at time
$t$. The agent then receives a reward (observation) according to the following
model:

$y_{t}=\langle\theta_{*},a_{t}\rangle+\eta_{t},$ (1)

where $\\{\eta_{t}\\}$ is a sequence of i.i.d. $1$-subgaussian noise random
variables. Here, $\theta_{*}$ is an unknown parameter that belongs to a known
compact set $\Theta\subset\mathbb{R}^{d}$; for each $\theta\in\Theta$, it
holds that ${\|\theta\|}_{2}\leq M$, where $M\geq 1$. Our performance measure
of interest is the following regret metric $R_{T}$:

$R_{T}=\mathbb{E}\left[\sum_{t=1}^{T}\max_{a\in\mathcal{A}_{t}}\langle\theta_{*},a-a_{t}\rangle\right],$
(2)

where $T$ is the time horizon. The goal of the server is to play a sequence of
actions such that ${R}_{T}$ grows sub-linearly in $T$. When there is no loss
of information from the agent to the server (i.e., in the absence of the
channel), it is well known that one can achieve
$\tilde{O}\left(d\sqrt{T}\right)$ regret by following the popular LinUCB
algorithm [31]. Our goal in this work is to develop an algorithm that achieves
the same performance subject to communication constraints that we describe
next.

Communication constraints. To capture communication constraints, we assume
that the channel from the agent to the server has a finite capacity of $B$
bits. Thus, at each time-step, the channel can transmit without error one of
$2^{B}$ symbols denoted by $\sigma\in\Sigma$, where $|\Sigma|=2^{B}$. As
explained and motivated in the introduction, we impose an additional
information constraint that the agent can only transmit encoded estimates of
the unknown model parameter $\theta_{*}$, but not the rewards themselves. We
note here that encoding a high-dimensional model estimate is much more
challenging than encoding a scalar-valued reward.

In section 4, we will establish that with $B=O(d)$ bits, one can ensure that
$R_{T}=\tilde{O}\left(d\sqrt{T}\right)$. Arriving at this result is however
quite non-trivial, and requires overcoming certain key technical challenges
that we outline next.

Challenges. In the standard linear stochastic bandit formulation, the chief
difficulty lies in taking decisions that incur low regret despite statistical
uncertainty concerning the unknown parameter $\theta_{*}$. In our setting,
such uncertainty is accentuated by the loss of information incurred over the
finite-capacity channel. Unless the server explicitly accounts for this
additional source of error in its decision-making process, it can end up
taking sub-optimal actions that generate low rewards. Moreover, since our
problem is of an inherently sequential nature, the effect of “poor” actions
coupled with channel-induced errors can pile up over time, resulting in the
agent-server pair suffering linear regret. The above discussion highlights the
challenge in decision-making.

In terms of communication, one natural idea to encode the parameter
$\theta_{*}$ could be to uniformly quantize the set $\Theta$ at each time-
step, since $\theta_{*}\in\Theta$. To ensure that the sum of the instantaneous
encoding errors do not grow linearly with the horizon $T$, such errors need to
scale inversely with $T$. However, to achieve such a precision with a non-
adaptive encoding scheme that always encodes the entire set $\Theta$, the
channel capacity $B$, in turn, needs to scale with $T$. This is highly
undesirable since the horizon-length $T$ can be arbitrarily long. To sum up,
the design of a joint encoding-decoding and decision-making strategy that
achieves order-optimal regret with a horizon-independent channel capacity is
not at all obvious a priori. Nonetheless, we will develop such a strategy in
the next section. For now, we lay down certain standard technical assumptions
that will be made throughout the paper.

######  Assumption 1.

The following hold:

  1. (i)

$\max_{t\in[T]}\sup_{a,b\in\mathcal{A}_{t}}\langle\theta_{*},a-b\rangle\leq
1.$

  2. (ii)

${\|a\|}_{2}\leq L$, $\forall a\in\bigcup_{t=1}^{T}\mathcal{A}_{t}$.

  3. (iii)

At each time-step $t\in[T]$, the decision set $\mathcal{A}_{t}$ contains the
unit sphere $\mathbb{S}^{d-1}$.

While assumptions (i) and (ii) are typical in the literature on linear
stochastic bandits [25], assumption (iii) is also quite standard and has been
used in various different contexts [48, 49]. Without loss of generality, we
assume that $L\geq 1$; furthermore, we assume that the horizon is long-enough
relative to the dimension of the model: $T\geq d^{2}$.

##  3 Information-Constrained Optimism in the Face of Uncertainty

In this section, we will develop our proposed algorithm (Algorithm 2) called
Information Constrained LinUCB (IC-LinUCB) that comprises of two phases. Phase
I is a pure exploration phase where the server picks i.i.d. actions from the
uniform distribution over the unit sphere; such actions are feasible owing to
Assumption 1-(iii). During this phase which lasts for $\bar{T}+1$ time-steps,
the only transmission from the agent to the server takes place at time-step
$\bar{T}+1$. The purpose of the pure exploration phase and the choice of the
parameter $\bar{T}$ will be explained shortly. During each time-step of Phase
II, the agent employs an adaptive encoding strategy (outlined in Algorithm 1)
to transmit information about the unknown parameter $\theta_{*}$ to the
server. Based on this information, the server takes decisions by constructing
an “inflated” confidence that accounts for encoding errors. We now describe in
detail the two key ingredients of IC-LinUCB: (i) the adaptive encoding
strategy at the agent, and (ii) the decision-making rule at the server.

$\bullet$ Adaptive Encoding at Agent. To describe the encoder, we will require
the notion of an $\epsilon$-net [50].

######  Definition 1.

($\epsilon$-net). Consider a subset $\mathcal{K}\subset\mathbb{R}^{d}$ and let
$\epsilon>0$. A subset $\mathcal{N}\subseteq\mathcal{K}$ is called an
$\epsilon$-net of $\mathcal{K}$ if every point in $\mathcal{K}$ is within a
distance of $\epsilon$ of some point of $\mathcal{N}$, i.e.,

$\forall x\in\mathcal{K},\exists
x_{0}\in\mathcal{N}:{\|x-x_{0}\|}_{2}\leq\epsilon.$

Equivalently, $\mathcal{N}$ is an $\epsilon$-net of $\mathcal{K}$ if and only
if $\mathcal{K}$ can be covered by balls with centers in $\mathcal{N}$ and
radii $\epsilon$.

Next, consider the least-squares estimate $\hat{\theta}^{(a)}_{t}$ maintained
by the agent:

$\hat{\theta}^{(a)}_{t}=V^{-1}_{t}\sum_{s=1}^{t}a_{s}y_{s},\hskip
5.69054pt\textrm{where}\hskip 5.69054ptV_{t}=\lambda
I_{d}+\sum_{s=1}^{t}a_{s}a^{\prime}_{s}$ (3)

is the covariance matrix at time-step $t$.333We use $x^{\prime}$ to denote the
transpose of a vector $x$. Here, $\lambda>0$ is a scalar regularization
parameter. Let $\hat{\theta}^{(s)}_{t}$ be the estimate of $\theta_{*}$
maintained by the server; $\hat{\theta}^{(s)}_{t}$ is initialized from any
arbitrary vector in $\Theta$ at time-step $\bar{T}+1$. The choice of this
initial vector is known to both the agent and the server.

Main Ideas. The key ideas guiding our encoding strategy are as follows. Once
the agent has acquired sufficiently many observations, the gap
$\hat{\theta}^{(a)}_{t}-\hat{\theta}^{(a)}_{t-1}$ between successive estimates
will start shrinking due to the pure exploration phase; see Remark 1. Thus, at
this stage, if the gap $\hat{\theta}^{(a)}_{t-1}-\hat{\theta}^{(s)}_{t-1}$ is
not too large, then the gap
$e_{t}=\hat{\theta}^{(a)}_{t}-\hat{\theta}^{(s)}_{t-1}$ should not be too
large either. In other words, eventually, a new observation $y_{t}$ will not
cause the agent’s estimate of $\theta_{*}$ to deviate drastically from the
estimate of $\theta_{*}$ held by the server. Intuitively, it thus makes sense
to encode and transmit only the new information about $\theta_{*}$ contained
in $y_{t}$, i.e., the “innovation” signal $e_{t}$ (as opposed to encoding
$\hat{\theta}^{(a)}_{t}$). However, given the stochastic nature of our setup,
$e_{t}$ is a random variable. Thus, encoding $e_{t}$ poses the technical
hurdle of characterizing the region containing $e_{t}$ with high probability.
To this end, in Lemma 1 of Section 4, we establish that with high probability,
$\forall t\geq\bar{T}+1$, $e_{t}\in\mathcal{B}_{d}(0,p_{t})$, where $p_{t}$ is
the radius of the ball containing the innovation $e_{t}$. Our encoding
strategy is adaptive since it requires dynamically updating the radius $p_{t}$
(as per Eq. (4)) based on statistical concentration bounds specific to our
problem.

Figure 2: Illustration of the encoding technique in Algorithm 1. The agent
computes the innovation signal $e_{t}$ that belongs to
$\mathcal{B}_{d}(0,p_{t})$ with high probability. An $\epsilon p_{t}$-net of
$\mathcal{B}_{d}(0,p_{t})$ is constructed, and the center $\tilde{e}_{t}$ of
the ball containing $e_{t}$ is decoded by the server. Algorithm 1 Adaptive
Encoding at the Agent

1: Input Parameters: $\hat{\theta}^{(s)}_{\bar{T}}$ is any arbitrary vector in
$\Theta$; $q_{\bar{T}}=10M$; and
$f(T)=\frac{3}{5L}\sqrt{\frac{\beta_{T}}{T\log(dLT)}}$.

2:for $t\in\\{\bar{T}+1,\ldots,T\\}$ do

3: Observe $y_{t}$; compute
$\hat{\theta}^{(a)}_{t}=V^{-1}_{t}\sum_{s=1}^{t}a_{s}y_{s}$ and innovation
$e_{t}=\hat{\theta}^{(a)}_{t}-\hat{\theta}^{(s)}_{t-1}$.

4: Encode $e_{t}$ by constructing an $\epsilon p_{t}$-net of
$\mathcal{B}_{d}(0,p_{t})$, where
$q_{t}=\epsilon\left(q_{t-1}+f(T)\right);\hskip 5.69054ptp_{t}=q_{t}+f(T).$
(4)

5:end for

Summary of Encoding Strategy. The overall encoding technique in Algorithm 1
can be summarized as follows. At each time-step $t\geq\bar{T}+1$, the agent
observes $y_{t}$, computes $\hat{\theta}^{(a)}_{t}$ as per (3), and then
evaluates the innovation signal
$e_{t}=\hat{\theta}^{(a)}_{t}-\hat{\theta}^{(s)}_{t-1}$. Given that
$e_{t}\in\mathcal{B}_{d}(0,p_{t})$ with high probability (as justified by
Lemma 1), the region $\mathcal{B}_{d}(0,p_{t})$ is covered by balls of radius
$\epsilon p_{t}$, where $\epsilon\in(0,1)$ is a pre-decided constant, i.e.,
the agent constructs an $\epsilon p_{t}$-net of
$\mathcal{B}_{d}(0,p_{t})$.444For a discussion on constructing such coverings,
see [51, 52] and the references therein. The agent then determines the ball
$e_{t}$ falls into, and transmits the symbol $\sigma\in\Sigma$ corresponding
to that ball.555In case $e_{t}$ lands on the boundary of more than one ball,
it is assigned the label/symbol of any one of those balls based on a fixed
priority rule. If $e_{t}$ falls outside $\mathcal{B}_{d}(0,p_{t})$, the agent
transmits a special symbol to indicate an overflow. We succinctly represent
the entire operation described above by a dynamic encoder map
$\mathcal{E}_{t}$ that takes as input $e_{t}$ and generates as output the
symbolic encoding $\sigma_{t}\in\Sigma$ that is transmitted to the server.

Decoding at Server. As a basic requirement for correct decoding, we assume
that the server is aware of the encoding operation at the agent. Moreover,
note that the sequences $\\{p_{t}\\}$ and $\\{q_{t}\\}$ defined in Eq. (4) are
deterministic, and can be computed by the server at its end. Thus, at any
time-step $t\geq\bar{T}+1$, the server is aware of the region
$\mathcal{B}_{d}(0,p_{t})$ being encoded. Upon receiving $\sigma_{t}$, the
server can thus correctly determine the center $\tilde{e}_{t}$ of the ball
containing $e_{t}$. We represent the above decoding operation at time $t$ by
the decoder map $\mathcal{D}_{t}$ that takes as input $\sigma_{t}$ and outputs
$\tilde{e}_{t}$. Having decoded the innovation signal, the server computes an
estimate $\hat{\theta}^{(s)}_{t}$ of $\theta_{*}$ as per line 7 of Algo. 2.
The agent computes $\hat{\theta}^{(s)}_{t}$ on its end as well in order to
evaluate the innovation signal at time $t+1$; see line 2 of Algo. 1. This
concludes the description of the encoding-decoding operation, a pictorial
illustration of which is presented in Figure 2.

Till now, we have only described how to transit information about $\theta_{*}$
from the agent to the server over a finite-capacity channel. However, the key
question that remains unanswered is the following: How should the server take
decisions that yield low cumulative regret while accounting for the additional
uncertainty introduced by the channel? We now turn to answering this question.

Algorithm 2 Information Constrained LinUCB (IC-LinUCB)

1: Input Parameters: $\bar{T}=\lceil 10L^{2}d\sqrt{T}\log(dLT)\rceil$.

2: Phase I: Pure Exploration

3:for $t\in\\{1,\ldots,\bar{T}+1\\}$ do

4: Server plays $a_{t}\sim\textrm{Unif}(\mathbb{S}^{d-1})$.

5: Agent receives reward $y_{t}$ as per (1) and computes estimate
$\hat{\theta}^{(a)}_{t}=V^{-1}_{t}\sum_{s=1}^{t}a_{s}y_{s}$.

6:end for

7:Agent encodes
$e_{\bar{T}+1}=\hat{\theta}^{(a)}_{\bar{T}+1}-\hat{\theta}^{(s)}_{\bar{T}}$ as
per Algo. 1, and transmits
$\sigma_{\bar{T}+1}=\mathcal{E}_{\bar{T}+1}\left(e_{\bar{T}+1}\right)$.

8:

9: Phase II: Information-Constrained Exploration-Exploitation

10:for $t\in\\{\bar{T}+2,\ldots,T\\}$ do

11: Server decodes $\tilde{e}_{t-1}=\mathcal{D}_{t-1}(\sigma_{t-1})$, and
generates $\hat{\theta}^{(s)}_{t-1}=\hat{\theta}^{(s)}_{t-2}+\tilde{e}_{t-1}$.

12: Server constructs confidence ellipsoid:
$\mathcal{C}^{(s)}_{t}=\\{\theta\in\mathbb{R}^{d}:{\|\theta-\hat{\theta}^{(s)}_{t-1}\|}_{V_{t-1}}\leq\sqrt{\beta_{T}}+{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\left(\sqrt{\lambda+(t-1)L^{2}}\right)q_{t}\\}},$
(5) where $V_{t-1}$, $q_{t}$, and $\sqrt{\beta_{T}}$ are given by (3), (4),
and (7), respectively.

13: Server plays action
$a_{t}=\operatorname*{\arg\\!\max}_{a\in\mathcal{A}_{t}}\max_{\theta\in\mathcal{C}^{(s)}_{t}}\langle\theta,a\rangle$.

14: Agent receives reward $y_{t}$ as per (1) and computes estimate
$\hat{\theta}^{(a)}_{t}=V^{-1}_{t}\sum_{s=1}^{t}a_{s}y_{s}$.

15: Agent encodes the innovation
$e_{t}=\hat{\theta}^{(a)}_{t}-\hat{\theta}^{(s)}_{t-1}$ as per Algo. 1, and
transmits $\sigma_{t}=\mathcal{E}_{t}(e_{t})$.

16:end for

$\bullet$ Decision-Making at the Server. When there is no loss of information
over the channel, i.e., when $\hat{\theta}^{(s)}_{t}=\hat{\theta}^{(a)}_{t}$,
the celebrated LinUCB algorithm relies on the principle of optimism in the
face of uncertainty. Specifically, at each time-step, an ellipsoidal
confidence set is constructed that contains $\theta_{*}$ with high-
probability. The learner then acts optimistically by playing an action that
yields the highest reward over all possible values of $\theta$ in the
confidence set. While our approach builds on the same high-level principle, it
relies crucially on the construction of a new “inflated” ellipsoidal
confidence set:

$\mathcal{C}^{(s)}_{t}=\\{\theta\in\mathbb{R}^{d}:{\|\theta-\hat{\theta}^{(s)}_{t-1}\|}_{V_{t-1}}\leq\sqrt{\beta_{T}}+{\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}\left(\sqrt{\lambda+(t-1)L^{2}}\right)q_{t}\\}},$
(6)

where

$\sqrt{\beta_{T}}=\sqrt{\lambda}M+\sqrt{2\log\left(\frac{1}{\delta}\right)+d\log\left(\frac{d\lambda+TL^{2}}{d\lambda}\right)}.$
(7)

Here, recall that $M\geq 1$ is such that for each $\theta\in\Theta$,
${\|\theta\|}_{2}\leq M$; $\delta\in(0,1)$ is a constant to be picked later.
Notably, when $\hat{\theta}^{(s)}_{t-1}=\hat{\theta}^{(a)}_{t-1}$, and
$q_{t}=0$, $\mathcal{C}^{(s)}_{t}$ reduces to the confidence set in LinUCB.
The inflation in the radius of the confidence set (relative to LinUCB)
carefully accounts for the quantization errors resulting from the finite
capacity of the channel. Our main technical contribution in this regard is to
establish that $\forall t\geq\bar{T}+2$, $\theta_{*}\in\mathcal{C}^{(s)}_{t}$
with high probability; see Lemma 10 in Section 4. This result, in turn,
justifies the optimistic decision-making rule of IC-LinUCB in line 9 of
Algorithm 2. During the pure exploration phase, the server simply samples
actions independently from the uniform distribution over $\mathbb{S}^{d-1}$,
i.e., $a_{t}\sim\textrm{Unif}(\mathbb{S}^{d-1}),\forall t\in[\bar{T}+1]$.666To
be more precise, a random variable $Z$ is uniformly distributed on
$\mathbb{S}^{d-1}$ if, for every Borel subset
$\mathcal{K}\subset\mathbb{S}^{d-1}$, the probability
$\mathbb{P}(Z\in\mathcal{K})$ equals the ratio of the $(d-1)$-dimensional
areas of $\mathcal{K}$ and $\mathbb{S}^{d-1}$. At every time-step $t\in[T]$,
the action $a_{t}$ decided upon by the server is passed down to the agent
without any loss of information.

We summarize below the essential steps of our approach.

  * •

Bound Gap between Successive Model Estimates. Bound the gap
$\hat{\theta}^{(a)}_{t}-\hat{\theta}^{(a)}_{t-1}$ between successive estimates
of $\theta_{*}$ (at the agent), and argue that this gap is eventually small
due to the pure exploration phase; see Remark 1.

  * •

Characterize Encoding Region. Using the bound from the above step, encode the
innovation signal $e_{t}=\hat{\theta}^{(a)}_{t}-\hat{\theta}^{(s)}_{t-1}$ by
characterizing the region that contains $e_{t}$ with high-probability.

  * •

Construct Inflated Confidence Set. Construct a confidence set that (i) is
centered at the server’s estimate of $\theta_{*}$, namely
$\hat{\theta}^{(s)}_{t}$, (ii) accounts for encoding errors, and (iii)
contains $\theta_{*}$ with high-probability. Play actions optimistically
w.r.t. this confidence set.

In Section 5, we will demonstrate that the above ideas are applicable to
parameterized observation models well beyond the specific linear model
considered in Eq. (1). As such, our approach provides a general recipe for
decision-making under information constraints. Before moving on to the
performance guarantees of IC-LinUCB, a couple of important remarks are in
order.

######  Remark 1.

(Need for Pure Exploration Phase) Note that $\forall t\geq\bar{T}+1$,
$\lambda_{min}(V_{t})\geq\lambda_{min}(V_{\bar{T}})$. Moreover, for $\bar{T}$
as chosen in Algorithm 2, the pure exploration phase ensures that
$\lambda_{min}(V_{\bar{T}})$ is bounded below by a linear function of
$\bar{T}$. The above two facts collectively imply that the gap between
consecutive estimates of $\theta_{*}$ (at the agent) is eventually small - a
key requirement for our encoding strategy. This point is made precise in Lemma
39 of Appendix B. The duration $\bar{T}$ of the pure exploration phase is
chosen carefully to ensure that the term
$\left(\sqrt{\lambda+(t-1)L^{2}}\right)q_{t}$ in $\mathcal{C}^{(s)}_{t}$ is
eventually $O\left(\sqrt{\beta_{T}}\right)$. In other words, such a choice of
$\bar{T}$ enables us to preserve order-optimal regret despite taking actions
based on an inflated confidence set.

######  Remark 2.

(Horizon-Independent Channel Capacity) In our encoding technique, although the
radii of the balls used to cover the encoding region shrink over time, the
radius of the ball being encoded shrinks commensurately. This is precisely
what enables us to achieve order-optimal regret with a channel capacity
$B=O(d)$ bits that is independent of the time-horizon $T$. Roughly speaking,
the main intuition here is that to achieve the same level of encoding
precision, it takes fewer bits to encode the innovation $e_{t}$ as compared to
the model $\theta_{*}$. This is because while $e_{t}$ resides (with high
probability) in a ball of progressively shrinking radius, $\theta_{*}$ belongs
to the set $\Theta$ of fixed radius.

##  4 Analysis of the IC-LinUCB Algorithm

Our main result concerning the performance of the IC-LinUCB algorithm is as
follows.

######  Theorem 1.

(Regret of IC-LinUCB) Suppose Assumption 1 holds, and let the channel capacity
satisfy $B\geq 6d$. Then, with $\epsilon=1/2$ and $\delta=1/T$ in Algorithm 2,
the IC-LinUCB algorithm guarantees:

$R_{T}=O\left(L^{2}d\sqrt{T}\log(dLT)\right)=\tilde{O}\left(d\sqrt{T}\right).$
(8)

Discussion. We note that for the IC-LinUCB algorithm, the dependence of the
regret on $d$ and $T$ exactly matches that of LinUCB. Thus, our work is the
first to establish that with a horizon-independent channel capacity of $O(d)$
bits, one can achieve the same performance as when the channel has infinite
capacity. Thus, Theorem 1 can be seen as an extension of the results in [30,
31] to the communication-constrained setting of interest in this work.
Interestingly, [21] recently showed that for stochastic optimization with
$d$-dimensional quantized gradients, a bit-rate of $\Omega(d)$ is necessary
for achieving the optimal convergence rate of $O(1/\sqrt{T})$, where $T$ is
the number of iterations. We conjecture that to achieve order-optimal regret,
a similar lower-bound of $B=\Omega(d)$ will hold for our setup as well; we
leave verifying this as future work.

We prove Theorem 1 in Appendix B. In what follows, we briefly outline the key
technical steps in the proof.

Outline of the proof. We start by constructing an appropriate “clean” event
$\mathcal{G}$ of measure at least $1-5/T$, and condition on this event
throughout the subsequent analysis. There are three main steps in the proof of
Theorem 1, and we describe them below.

$\bullet$ Step 1. On the clean event $\mathcal{G}$, we argue that the gap
between successive model estimates at the agent is eventually small. More
precisely, in Lemma 39 of Appendix B, we establish that

${\|\hat{\theta}^{(a)}_{t+1}-\hat{\theta}^{(a)}_{t}\|}_{2}\leq f(T),\forall
t\geq\bar{T},$

where $f(T)$ is as defined in the input parameters of Algorithm 1. The proof
of Lemma 39 in turn relies on the fact that with high probability,

$\lambda_{\min}(V_{t})\geq 5L^{2}\sqrt{T}\log(dLT),\forall t\geq\bar{T}.$

The above claim is established in Lemma 6 of Appendix B by appealing to the
Matrix Bernstein inequality [50, Theorem 5.4.1].

$\bullet$ Step 2. The next key result justifies the encoding strategy in
Algorithm 1.777We note that results of a similar conceptual flavor are
established in [29] and [23] in the context of stabilization of an LTI system,
and optimization, respectively. While the results in these papers pertain to
deterministic settings, Lemma 1 carefully exploits statistical concentration
bounds specific to the stochastic process we study.

######  Lemma 1.

(Encoding Region) The following is true with probability at least $1-5/T$:

$e_{t}\in\mathcal{B}_{d}(0,p_{t}),\forall t\in\\{\bar{T}+1,\ldots,T\\},$

where $e_{t}$ is the innovation in line 2 of Algorithm 1, and $p_{t}$ is as
defined in Eq. (4).

The above result tells us that the innovation random variable $e_{t}$ always
falls within the desired encoding region on the event $\mathcal{G}$, i.e.,
with high probability, there is never any overflow. It is easy to argue that
$B=O(d)$ bits suffice to construct an $\epsilon p_{t}$ net of
$\mathcal{B}_{d}(0,p_{t})$.

$\bullet$ Step 3. It remains to justify the choice of the confidence set
$\mathcal{C}^{(s)}_{t}$ in Eq. (5). This is achieved in the following lemma.

######  Lemma 2.

(Confidence Region at Server) With probability at least $1-5/T$, the following
is true: $\theta_{*}\in\mathcal{C}^{(s)}_{t},\forall
t\in\\{\bar{T}+2,\ldots,T\\}$, where $\mathcal{C}^{(s)}_{t}$ is the confidence
set defined in Eq. (5). Moreover, $\forall t\geq\bar{T}+\tilde{T}$, we have

$\left(\sqrt{\lambda+(t-1)L^{2}}\right)q_{t}\leq
4\sqrt{\frac{\beta_{T}}{\log(dLT)}},$ (9)

where

$\tilde{T}=\left\lceil\frac{\log\left(\frac{10M}{f(T)}\right)}{\log(2)}\right\rceil\vee
2=O\left(\log(dLT)\right).$ (10)

The above result implies that the inflated confidence set (that accounts for
encoding errors) eventually contains the true parameter $\theta_{*}$ with high
probability. At the same time, the quantization error $q_{t}$ decays fast
enough to ensure that the radius of the confidence set is eventually
$O(\sqrt{\beta_{T}})$ \- exactly as in the LinUCB algorithm. In other words,
our approach ensures that the impact of the quantization error on decision-
making vanishes over time.

Equipped with Lemma’s 1 and 10, the rest of the proof of Theorem 1 follows
fairly standard arguments. We fill in these detailed arguments in Appendix B.

##  5 Extension to Generalized Linear Models

The main goal of this section is to demonstrate the generality of the
algorithmic approach developed in Section 3. To do so, we will now consider an
observation model where the rewards are no longer assumed to be linear
functions of the parameter. Rather, they satisfy the following relationship
[26, 27]:

$y_{t}=\mu\left(\langle\theta^{*},a_{t}\rangle\right)+\eta_{t},$ (11)

where $\mu:\mathbb{R}\rightarrow\mathbb{R}$ is a continuously differentiable
function typically referred to as the (inverse) link function, and
$\\{\eta_{t}\\}$ is a 1-subgaussian noise process as before. Our goal now will
be to control the following notion of regret:

$\bar{R}_{T}=\mathbb{E}\left[\sum_{t=1}^{T}\left(\max_{a\in\mathcal{A}_{t}}\mu(\langle\theta_{*},a\rangle)-\mu(\langle\theta_{*},a_{t}\rangle)\right)\right].$
(12)

In [26], the authors noted the following main difficulty in analyzing the
above non-linear model relative to the linear setting: for the Generalized
Linear Model (GLM) in (1), the relevant confidence regions may have a more
complicated geometry in the parameter space than simple ellipsoids. To
overcome this challenge, the GLM-UCB algorithm is developed in [26] by
focusing on the reward space.

For our setting, however, recall that the agent is not allowed to transmit the
reward $y_{t}$ (neither directly, nor in an encoded form) to the server,
thereby further adding to the technical complexity. This raises the following
questions. (i) How should the agent encode an estimate of $\theta_{*}$ based
on the GLM in Eq. (11)? (ii) How should the server design the confidence
region for decision-making? (iii) Will $B=O(d)$ bits continue to suffice for
achieving order-optimal regret? In what follows, we will answer the last
question in the affirmative by appropriately adapting the general recipe
outlined at the end of Section 3.

To get started, we make the following standard assumption on the inverse link
function [26, 27].

######  Assumption 2.

The function $\mu:\mathbb{R}\rightarrow\mathbb{R}$ is continuously
differentiable, Lipschitz with constant $k_{2}$, and such that

$k_{1}=\min\\{1,\inf_{\theta\in\Theta,a\in\bigcup_{t\in[T]}\mathcal{A}_{t}}\dot{\mu}(\langle\theta,a\rangle)\\}>0.$

Here, $\dot{\mu}(\cdot)$ is used to represent the derivative of $\mu(\cdot)$.

Without loss of generality, we will assume $k_{2}\geq 1$. Next, let us define

$g_{t}(\theta)=\lambda\theta+\sum_{s=1}^{t}\mu(\langle\theta,a_{s}\rangle)a_{s}.$
(13)

We are now ready to describe the Information-Constrained GLMUCB algorithm (IC-
GLMUCB).

Description of IC-GLMUCB. The IC-GLMUCB algorithm shares the same structure as
IC-LinUCB, but has some crucial algorithmic differences that we next outline.
First, instead of computing the least-squares estimate as in Eq. (3), the
agent now computes an estimate $\hat{\theta}^{(a)}_{t}$ of $\theta^{*}$ by
solving the following equation:

$g_{t}(\hat{\theta}^{(a)}_{t})=\sum_{s=1}^{t}y_{s}a_{s}.$ (14)

It then encodes the innovation signal
$e_{t}=\hat{\theta}^{(a)}_{t}-\hat{\theta}^{(s)}_{t-1}$ exactly as in line 3
of Algo. 1, with $f(T)$ in Eq. (4) replaced by

$\bar{f}(T)=\frac{3}{5L}\sqrt{\frac{\beta_{T}}{k_{1}k_{2}T\log(dLT)}},$ (15)

and $q_{\bar{T}}$ set to $\left(4+6/\sqrt{k_{1}k_{2}}\right)M$. The server
performs decoding exactly as in line 7 of Algorithm 2, and computes
$\hat{\theta}^{(s)}_{t}$. The main distinction relative to IC-LinUCB is in the
construction of the confidence region at the server. The server constructs the
following confidence set:

$\mathcal{\bar{C}}^{(s)}_{t}=\\{\theta\in\Theta:\mathcal{H}_{t-1}(\theta)\leq\sqrt{\beta_{T}}+k_{2}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\left(\sqrt{\lambda+(t-1)L^{2}}\right)q_{t}\\}},\hskip
2.84526pt\textrm{where}\hskip
2.84526pt\mathcal{H}_{t}(\theta)\triangleq{\|g_{t}(\theta)-g_{t}(\hat{\theta}^{(s)}_{t})\|}_{V^{-1}_{t}}.$
(16)

The server then acts optimistically w.r.t. the above confidence set:

$a_{t}=\operatorname*{\arg\\!\max}_{a\in\mathcal{A}_{t}}\max_{\theta\in\mathcal{\bar{C}}^{(s)}_{t}}\langle\theta,a\rangle,\forall
t\in\\{\bar{T}+2,\ldots,T\\},$ (17)

with $\bar{T}$ now set to

$\bar{T}=\left\lceil
10\frac{k_{2}}{k_{1}}L^{2}d\sqrt{T}\log(dLT)\right\rceil.$

For completeness, we provide the detailed steps of the IC-GLMUCB algorithm in
Appendix C. To analyze the performance of the IC-GLMUCB algorithm, we will
make the following standard assumption that is in the same spirit as
Assumption 1(i):

$\sup_{a,b\in\bigcup_{t=1}^{T}\mathcal{A}_{t}}\mu(\langle\theta_{*},a\rangle)-\mu(\langle\theta_{*},b\rangle)\leq
1.$

We now state the main result of this section.

######  Theorem 2.

(Regret of IC-GLMUCB) Suppose Assumptions 1(ii)-(iii) hold along with
Assumption 2. Moreover, let the channel capacity satisfy $B\geq 6d$. Then, the
IC-GLMUCB algorithm guarantees:

$\bar{R}_{T}=O\left({\left(\frac{k_{2}}{k_{1}}\right)}^{3/2}L^{2}d\sqrt{T}\log(dLT)\right)=\tilde{O}\left(d\sqrt{T}\right).$
(18)

For the proof of Theorem 2, see Appendix C.

Discussion. The above result significantly generalizes Theorem 1, and reveals
that the IC-GLMUCB algorithm yields the same regret bounds as IC-LinUCB (up to
constants) under identical requirements on the channel capacity as before.
Thus, the main takeaway here is that our approach can readily accommodate
general non-linear observation models as well (albeit with a slightly more
involved analysis).

##  6 One Bit Channel Capacity is Sufficient for the Multi-Armed Bandit
Problem

In Sections 4 and 5, we have seen that for a $d$-dimensional model, $O(d)$
bits suffice to achieve order-optimal regret. In this section, we investigate
whether one can achieve similar order-optimal regret bounds with fewer bits
when the set of feasible actions has additional structure. We will show that
this is indeed the case for a particular setting of interest when
$\mathcal{A}_{t}=\\{e_{1},\ldots,e_{d}\\},\forall t\in[T]$, where
${(e_{i})}_{i}$ are the standard orthonormal unit vectors. This setting
represents the popular unstructured multi-armed bandit problem with a finite
number of arms. Our main insight is the following: playing action/arm $i$ only
reveals information about the $i$-th component of $\theta_{*}$, denoted by
$\theta_{i}$, and hence, when the $i$-th action is played, it makes sense for
the agent to encode and transmit the innovation related to only $\theta_{i}$.
In other words, the above intuition suggests that encoding a scalar innovation
signal (as opposed to a $d$-dimensional innovation vector) should suffice for
the specific setting under consideration. In what follows, we formalize this
reasoning.

To get started, let us note that the optimal action $a_{*}$ is the unit vector
corresponding to the largest component of $\theta_{*}$. Without loss of
generality, let this component be $\theta_{1}$, i.e.,
$\theta_{1}=\max_{i\in[d]}\theta_{i}$. We thus have $a_{*}=e_{1}$. Let us
denote by $\hat{\theta}^{(a)}_{i,k}$ (resp., $\hat{\theta}^{(s)}_{i,k}$) the
estimate of $\theta_{i}$ at the agent (resp., at the server) after arm $i$ has
been played $k$ times. We now develop an information-constrained variant of
the celebrated upper confidence bound algorithm that we call IC-UCB.

Description of IC-UCB. Let $\gamma=1/2^{B}$ where $B$ is the channel capacity,
and define the following sequences for $k\geq 1$:

$p_{k+1}=\gamma p_{k}+2f_{k};\hskip 5.69054ptq_{k}=\gamma p_{k};\hskip
5.69054ptf_{k}=2\sqrt{\frac{\log T}{k}},$ (19)

where $p_{1}=m+f_{1}$, and $m\geq 1$ is such that
$\max_{i\in[d]}|\theta_{i}|\leq m$. Suppose the action at time $t$ is
$a_{t}=e_{i}$. The agent first updates its estimate of $\theta_{i}$:

$\hat{\theta}^{(a)}_{i,n_{i}(t)}=\frac{1}{n_{i}(t)}\sum_{k=1}^{n_{i}(t)}y_{i,k},$
(20)

where $y_{i,k}$ is the agent’s observation when the $i$-th arm is played the
$k$-th time, and $n_{i}(t)$ is the number of times arm $i$ is played up to
(and including) time-step $t$. It then computes the scalar innovation
$e_{i,n_{i}(t)}=\hat{\theta}^{(a)}_{i,n_{i}(t)}-\hat{\theta}^{(s)}_{i,n_{i}(t)-1}$,
where $\hat{\theta}^{(s)}_{i,0}=0,\forall i\in[d]$. If $e_{i,n_{i}(t)}$ falls
in the interval $\mathcal{Z}_{i,t}=[-p_{n_{i}(t)},p_{n_{i}(t)}]$, then
$\mathcal{Z}_{i,t}$ is partitioned uniformly into $2^{B}$ bins, and the symbol
$\sigma_{t}\in\Sigma$ encoding the bin containing $e_{i,n_{i}(t)}$ is
transmitted to the server. The server then decodes the center
$\tilde{e}_{i,n_{i}(t)}$ of that bin, and computes

$\hat{\theta}^{(s)}_{i,n_{i}(t)}=\hat{\theta}^{(s)}_{i,n_{i}(t)-1}+\tilde{e}_{i,n_{i}(t)}.$

If $e_{i,n_{i}(t)}\notin\mathcal{Z}_{i,t}$, then there is no transmission from
the agent to the server. As for decision-making, each arm is first played once
by the server. Subsequently, the action chosen by the server at time-step
$t+1$ is the one that maximizes the following index:

$\texttt{IC-
UCB}_{i}(t)=\hat{\theta}^{(s)}_{i,n_{i}(t)}+q_{n_{i}(t)}+f_{n_{i}(t)},$ (21)

where $q_{n_{i}(t)}$ and $f_{n_{i}(t)}$ are as in Eq. (19).

Let us define by $\Delta_{i}=\theta_{1}-\theta_{i}$ the sub-optimality gap of
arm $i$. To present our results in a clean way, we will focus on the
particularly important case where the sub-optimality gaps are small:
$\Delta_{i}\in(0,1],\forall i\in[d]\setminus\\{1\\}.$ Our results can be
easily generalized to arbitrary values of the sub-optimality gaps. For the
setting considered in this section, it is easy to verify that the regret
$R_{T}$ in Eq. (2) simplifies to

$R_{T}=\sum_{i=1}^{d}\Delta_{i}\mathbb{E}[n_{i}(T)].$

Our main result concerning the regret bound of IC-UCB is as follows.

######  Theorem 3.

(Regret of IC-UCB) Suppose the channel capacity is at least $1$ bit, i.e.,
$B\geq 1$. The IC-UCB algorithm then guarantees:

$R_{T}\leq
5\sum_{i=1}^{d}\Delta_{i}+\sum_{i=1}^{d}O\left(\frac{\log(mT)}{\Delta_{i}}\right).$

We can also establish the following gap-independent bound.

######  Theorem 4.

(Gap-independent regret of IC-UCB) Suppose the channel capacity satisfies
$B\geq 1$. The IC-UCB algorithm then guarantees:

$R_{T}\leq 5\sum_{i=1}^{d}\Delta_{i}+O\left(\sqrt{dT\log(mT)}\right).$

Discussion: Our bounds above match those of the UCB algorithm, revealing that
for the MAB problem, one can achieve order-optimal bounds with a bit-rate of
just $1$ bit. The main takeaway here is that when the action sets have more
structure, there is hope for achieving optimal performance with a channel
capacity of fewer than $O(d)$ bits. As future work, it would be interesting to
see if one can draw similar conclusions for other types of common action sets.

##  7 Conclusion and Future Directions

We introduced and studied a new linear stochastic bandit problem subject to
communication channel constraints. We developed a general algorithmic
framework comprising of an adaptive compression mechanism, and a decision-
making rule that explicitly accounts for encoding errors. We then showed how
this framework leads to order-optimal regret bounds for (i) the linear bandit
setting, (ii) the generalized linear bandit setting, and (iii) the MAB
problem, with horizon-independent bit-rates that depend only on the dimension
of the unknown model parameter. Our work opens up several interesting avenues
of research; we discuss some of them below.

First, an immediate question that remains unresolved is whether $O(d)$ bits is
indeed necessary for achieving order-optimal regret for the linear bandit
problem. Answering this question would require establishing algorithm-
independent lower bounds for our setup - this is quite non-trivial, and is the
subject of our ongoing work. Second, while our focus was on minimizing the
number of bits needed to achieve optimal regret, one may ask the following
alternate question: Given a fixed communication budget, what is the best
cumulative regret bound one can hope for? It would be particularly interesting
to ascertain the minimal communication budget (as a function of the model
parameter dimension) needed to achieve sublinear regret. Third, we plan to
extend the ideas and results in our paper to more complex
distributed/federated settings involving multiple agents. Finally, our goal is
to explore whether the techniques developed in this paper are applicable to
Markov decision processes in the context of reinforcement learning.

## References

  * [1] Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu.  1-bit stochastic gradient descent and its application to data-parallel distributed training of speech dnns.  In Fifteenth Annual Conference of the International Speech Communication Association, 2014.
  * [2] Nikko Strom.  Scalable distributed dnn training using commodity gpu cloud computing.  In Sixteenth Annual Conference of the International Speech Communication Association, 2015.
  * [3] Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li.  Terngrad: Ternary gradients to reduce communication in distributed deep learning.  In Advances in neural information processing systems, pages 1509–1519, 2017.
  * [4] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic.  Qsgd: Communication-efficient sgd via gradient quantization and encoding.  Advances in Neural Information Processing Systems, 30:1709–1720, 2017.
  * [5] Sarit Khirirat, Hamid Reza Feyzmahdavian, and Mikael Johansson.  Distributed learning with compressed gradients.  arXiv preprint arXiv:1806.06573, 2018.
  * [6] Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik.  Distributed learning with compressed gradient differences.  arXiv preprint arXiv:1901.09269, 2019.
  * [7] Zhize Li, Dmitry Kovalev, Xun Qian, and Peter Richtárik.  Acceleration for compressed gradient descent in distributed and federated optimization.  arXiv preprint arXiv:2002.11364, 2020.
  * [8] Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Sebastian Stich, and Peter Richtárik.  Stochastic distributed learning with gradient quantization and variance reduction.  arXiv preprint arXiv:1904.05115, 2019.
  * [9] Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani.  Fedpaq: A communication-efficient federated learning method with periodic averaging and quantization.  In International Conference on Artificial Intelligence and Statistics, pages 2021–2031. PMLR, 2020.
  * [10] Farzin Haddadpour, Mohammad Mahdi Kamani, Aryan Mokhtari, and Mehrdad Mahdavi.  Federated learning with compression: Unified analysis and sharp guarantees.  arXiv preprint arXiv:2007.01154, 2020.
  * [11] Alham Fikri Aji and Kenneth Heafield.  Sparse communication for distributed gradient descent.  arXiv preprint arXiv:1704.05021, 2017.
  * [12] Yujun Lin, Song Han, Huizi Mao, Yu Wang, and William J Dally.  Deep gradient compression: Reducing the communication bandwidth for distributed training.  arXiv preprint arXiv:1712.01887, 2017.
  * [13] Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli.  The convergence of sparsified gradient methods.  In Advances in Neural Information Processing Systems, pages 5973–5983, 2018.
  * [14] Sebastian U Stich, Jean-Baptiste Cordonnier, and Martin Jaggi.  Sparsified sgd with memory.  In Advances in Neural Information Processing Systems, pages 4447–4458, 2018.
  * [15] Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian U Stich, and Martin Jaggi.  Error feedback fixes signsgd and other gradient compression schemes.  arXiv preprint arXiv:1901.09847, 2019.
  * [16] Sebastian U Stich and Sai Praneeth Karimireddy.  The error-feedback framework: Better rates for sgd with delayed gradients and compressed communication.  arXiv preprint arXiv:1909.05350, 2019.
  * [17] Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan.  On biased compression for distributed learning.  arXiv preprint arXiv:2002.12410, 2020.
  * [18] Eduard Gorbunov, Dmitry Kovalev, Dmitry Makarenko, and Peter Richtárik.  Linearly converging error compensated sgd.  Advances in Neural Information Processing Systems, 33, 2020.
  * [19] Aritra Mitra, Rayana Jaafar, George Pappas, and Hamed Hassani.  Linear convergence in federated learning: Tackling client heterogeneity and sparse gradients.  Advances in Neural Information Processing Systems, 34, 2021.
  * [20] Nicole Mitchell, Johannes Ballé, Zachary Charles, and Jakub Konečnỳ.  Optimizing the communication-accuracy trade-off in federated learning with rate-distortion theory.  arXiv preprint arXiv:2201.02664, 2022.
  * [21] Prathamesh Mayekar and Himanshu Tyagi.  Ratq: A universal fixed-length quantizer for stochastic optimization.  In International Conference on Artificial Intelligence and Statistics, pages 1399–1409. PMLR, 2020.
  * [22] Venkata Gandikota, Daniel Kane, Raj Kumar Maity, and Arya Mazumdar.  vqsgd: Vector quantized stochastic gradient descent.  In International Conference on Artificial Intelligence and Statistics, pages 2197–2205. PMLR, 2021.
  * [23] Chung-Yi Lin, Victoria Kostina, and Babak Hassibi.  Differentially quantized gradient descent.  In 2021 IEEE International Symposium on Information Theory (ISIT), pages 1200–1205. IEEE, 2021.
  * [24] Jakub Konečnỳ, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon.  Federated learning: Strategies for improving communication efficiency.  arXiv preprint arXiv:1610.05492, 2016.
  * [25] Tor Lattimore and Csaba Szepesvári.  Bandit algorithms.  Cambridge University Press, 2020.
  * [26] Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári.  Parametric bandits: The generalized linear case.  In NIPS, volume 23, pages 586–594, 2010.
  * [27] Lihong Li, Yu Lu, and Dengyong Zhou.  Provably optimal algorithms for generalized linear contextual bandits.  In International Conference on Machine Learning, pages 2071–2080. PMLR, 2017.
  * [28] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer.  Finite-time analysis of the multiarmed bandit problem.  Machine learning, 47(2):235–256, 2002.
  * [29] Sekhar Tatikonda and Sanjoy Mitter.  Control under communication constraints.  IEEE Transactions on automatic control, 49(7):1056–1068, 2004.
  * [30] Varsha Dani, Thomas P Hayes, and Sham M Kakade.  Stochastic linear optimization under bandit feedback.  2008\.
  * [31] Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári.  Improved algorithms for linear stochastic bandits.  Advances in neural information processing systems, 24:2312–2320, 2011.
  * [32] Peter Landgren, Vaibhav Srivastava, and Naomi Ehrich Leonard.  Distributed cooperative decision-making in multiarmed bandits: Frequentist and bayesian algorithms.  In 2016 IEEE 55th Conference on Decision and Control (CDC), pages 167–172. IEEE, 2016.
  * [33] Peter Landgren, Vaibhav Srivastava, and Naomi Ehrich Leonard.  Distributed cooperative decision making in multi-agent multi-armed bandits.  Automatica, 125:109445, 2021.
  * [34] Shahin Shahrampour, Alexander Rakhlin, and Ali Jadbabaie.  Multi-armed bandits in multi-agent networks.  In 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 2786–2790. IEEE, 2017.
  * [35] Ravi Kumar Kolla, Krishna Jagannathan, and Aditya Gopalan.  Collaborative learning of stochastic bandits over a social network.  IEEE/ACM Transactions on Networking, 26(4):1782–1795, 2018.
  * [36] Yuanhao Wang, Jiachen Hu, Xiaoyu Chen, and Liwei Wang.  Distributed bandit learning: Near-optimal regret with efficient communication.  arXiv preprint arXiv:1904.06309, 2019.
  * [37] Abishek Sankararaman, Ayalvadi Ganesh, and Sanjay Shakkottai.  Social learning in multi agent multi armed bandits.  Proceedings of the ACM on Measurement and Analysis of Computing Systems, 3(3):1–35, 2019.
  * [38] David Martínez-Rubio, Varun Kanade, and Patrick Rebeschini.  Decentralized cooperative stochastic bandits.  arXiv preprint arXiv:1810.04468, 2018.
  * [39] Abhimanyu Dubey et al.  Kernel methods for cooperative multi-agent contextual bandits.  In International Conference on Machine Learning, pages 2740–2750. PMLR, 2020.
  * [40] Abhimanyu Dubey and Alex Pentland.  Differentially-private federated linear bandits.  arXiv preprint arXiv:2010.11425, 2020.
  * [41] Anusha Lalitha and Andrea Goldsmith.  Bayesian algorithms for decentralized stochastic bandits.  arXiv preprint arXiv:2010.10569, 2020.
  * [42] Ronshee Chawla, Abishek Sankararaman, Ayalvadi Ganesh, and Sanjay Shakkottai.  The gossiping insert-eliminate algorithm for multi-agent bandits.  In International Conference on Artificial Intelligence and Statistics, pages 3471–3481. PMLR, 2020.
  * [43] Ronshee Chawla, Abishek Sankararaman, and Sanjay Shakkottai.  Multi-agent low-dimensional linear bandits.  arXiv preprint arXiv:2007.01442, 2020.
  * [44] Avishek Ghosh, Abishek Sankararaman, and Kannan Ramchandran.  Collaborative learning and personalization in multi-agent stochastic linear bandits.  arXiv preprint arXiv:2106.08902, 2021.
  * [45] Mridul Agarwal, Vaneet Aggarwal, and Kamyar Azizzadenesheli.  Multi-agent multi-armed bandits with limited communication.  arXiv preprint arXiv:2102.08462, 2021.
  * [46] Zhaowei Zhu, Jingxuan Zhu, Ji Liu, and Yang Liu.  Federated bandit: A gossiping approach.  In Abstract Proceedings of the 2021 ACM SIGMETRICS/International Conference on Measurement and Modeling of Computer Systems, pages 3–4, 2021\.
  * [47] Chengshuai Shi, Cong Shen, and Jing Yang.  Federated multi-armed bandits with personalization.  In International Conference on Artificial Intelligence and Statistics, pages 2917–2925. PMLR, 2021.
  * [48] Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis.  Linear stochastic bandits under safety constraints.  arXiv preprint arXiv:1908.05814, 2019.
  * [49] Jiaqi Yang, Wei Hu, Jason D Lee, and Simon Shaolei Du.  Impact of representation learning in linear bandits.  In International Conference on Learning Representations, 2020.
  * [50] Roman Vershynin.  High-dimensional probability: An introduction with applications in data science, volume 47.  Cambridge university press, 2018.
  * [51] Ilya Dumer, Mark S Pinsker, and Vyacheslav V Prelov.  On coverings of ellipsoids in euclidean spaces.  IEEE transactions on information theory, 50(10):2348–2356, 2004\.
  * [52] Jean-Louis Verger-Gaugry.  Covering a ball with smaller equal balls in $\mathbb{R}^{n}$.  Discrete & Computational Geometry, 33(1):143–155, 2005.

##  Appendix A Supporting Technical Results

In this section, we compile certain results that will be used in our
subsequent analysis. We start by recalling the Matrix Bernstein inequality
that will be used by us for lower-bounding the smallest eigenvalue of the
covariance matrix $V_{t}$.

######  Lemma 3.

(Matrix Bernstein) [50, Theorem 5.4.1] Let $X_{1},\ldots,X_{N}$ be independent
zero-mean $d\times d$ symmetric random matrices, such that
${\|X_{t}\|}_{2}\leq K$ almost surely, $\forall t\in[N]$. Then, for every
$\epsilon>0$, we have

$\mathbb{P}\left({\bigg{\lVert}\sum_{t=1}^{N}X_{t}\bigg{\rVert}}_{2}\geq\epsilon\right)\leq
2d\exp\left(\frac{-\epsilon^{2}/2}{\sigma^{2}+K\epsilon/3}\right),$ (22)

where
$\sigma^{2}={\bigg{\lVert}\sum\limits_{t=1}^{N}\mathbb{E}[X^{2}_{t}]\bigg{\rVert}}_{2}$
is the norm of the matrix variance of the sum.

The next result is popularly used in the analysis of linear stochastic
bandits. We adapt it based on our notation.

######  Lemma 4.

(Confidence Region) [25, Theorem 20.5] Given any $\delta\in(0,1)$, it holds
that

$\mathbb{P}\left(\exists
t\in[T]:\theta_{*}\notin\mathcal{C}_{t}\right)\leq\delta,$

where

$\mathcal{C}_{t}=\\{\theta\in\mathbb{R}^{d}:{\|\hat{\theta}^{(a)}_{t-1}-\theta\|}_{V_{t-1}}\leq\sqrt{\beta_{T}}\\},$
(23)

and

$\sqrt{\beta_{T}}=\sqrt{\lambda}M+\sqrt{2\log\left(\frac{1}{\delta}\right)+d\log\left(\frac{d\lambda+TL^{2}}{d\lambda}\right)}.$

For reasoning about the capacity of the channel, we will require the concept
of covering numbers.

######  Definition 2.

(Covering Numbers) Let $\mathcal{K}$ be a subset of $\mathbb{R}^{d}$. The
smallest cardinality of an $\epsilon$-net of $\mathcal{K}$ is called the
covering number of $\mathcal{K}$ and is denoted by
$\mathcal{N}(\mathcal{K},\epsilon)$. Equivalently,
$\mathcal{N}(\mathcal{K},\epsilon)$ is the smallest number of closed balls
with centers in $\mathcal{K}$ and radii $\epsilon$ whose union covers
$\mathcal{K}$.

The following key result relates the covering number of a set $\mathcal{K}$ to
its volume.

######  Lemma 5.

(Covering Numbers and Volume) [50, Proposition 4.2.12] Let $\mathcal{K}$ be a
subset of $\mathbb{R}^{d}$, and $\epsilon>0$. Then,

$\mathcal{N}(\mathcal{K},\epsilon)\leq\frac{|\left(\mathcal{K}\oplus(\epsilon/2)\mathcal{B}_{d}(0,1)\right)|}{|(\epsilon/2)\mathcal{B}_{d}(0,1)|}.$

Here, we used $|\mathcal{K}|$ to represent the volume of a set $\mathcal{K}$,
and $\mathcal{K}_{1}\oplus\mathcal{K}_{2}$ to denote the Minkowski sum of two
sets $\mathcal{K}_{1},\mathcal{K}_{2}\subset\mathbb{R}^{d}$.

##  Appendix B Proof of Theorem 1

In this section, we will develop the proof of Theorem 1. In the process, we
will restate some of the key lemmas from Section 4 for the reader’s
convenience. We start with the following result that provides a lower-bound on
the smallest eigenvalue of the covariance matrix $V_{t}$.

######  Lemma 6.

Given any $\delta\in(0,1)$, we have that with probability at least $1-\delta$,

$\lambda_{\min}(V_{t})\geq\frac{\bar{T}}{2d},\forall t\geq\bar{T},$ (24)

as long as $\bar{T}\geq\frac{28d}{3}\log(2d/\delta)$. In particular, with
$\delta=2/T$, and $\bar{T}=\lceil 10L^{2}d\sqrt{T}\log(dLT)\rceil$, we have
that with probability at least $1-2/T$,

$\lambda_{\min}(V_{t})\geq 5L^{2}\sqrt{T}\log(dLT),\forall t\geq\bar{T}.$ (25)

###### Proof.

The proof is an application of the Matrix Bernstein inequality in Lemma 3. To
get started, recall that the pure exploration phase of the IC-LinUCB algorithm
lasts for the first $\bar{T}+1$ time-steps, and that
$a_{t}\sim\textrm{Unif}(\mathbb{S}^{d-1}),\forall t\in[\bar{T}+1]$. Define

$X_{t}\triangleq a_{t}a^{\prime}_{t}-\bar{\Sigma};\hskip
5.69054pt\textrm{and}\hskip 5.69054pt\bar{\Sigma}\triangleq\frac{I_{d}}{d}.$
(26)

From the choice of the actions during the pure exploration phase, we then
immediately have

$\mathbb{E}[X_{t}]=0_{d};\hskip 5.69054pt\textrm{and}\hskip
5.69054pt\lambda_{\max}(X_{t})\leq 1,\forall t\in[\bar{T}],$ (27)

where we used $0_{d}$ to represent a $d\times d$ matrix with every entry equal
to $0$. Since each $X_{t}$ is symmetric, we have ${\|X_{t}\|}_{2}\leq
1,\forall t\in[\bar{T}].$ Now let
$Y=\sum_{t=1}^{\bar{T}}\mathbb{E}[X^{2}_{t}]=\bar{T}\left(\mathbb{E}[{X}^{2}_{1}]\right)$.
Now observe that

$\displaystyle\mathbb{E}[{X}^{2}_{1}]$
$\displaystyle=\mathbb{E}\left[{\left(a_{1}a^{\prime}_{1}-\bar{\Sigma}\right)}^{2}\right]$
(28)
$\displaystyle=\mathbb{E}\left[{\left(a_{1}a^{\prime}_{1}\right)}^{2}\right]-{\bar{\Sigma}}^{2}$
$\displaystyle\preccurlyeq\mathbb{E}\left[{\left(a_{1}a^{\prime}_{1}\right)}^{2}\right]$
$\displaystyle=\mathbb{E}\left[a_{1}a^{\prime}_{1}a_{1}a^{\prime}_{1}\right]$
$\displaystyle=\mathbb{E}\left[\left({\|a_{1}\|}^{2}\right)a_{1}a^{\prime}_{1}\right]$
$\displaystyle=\frac{I_{d}}{d},$

where we used the fact that ${\|a_{1}\|}^{2}=1$. We thus have

$Y\preccurlyeq\frac{\bar{T}}{d}I_{d},$ (29)

and hence,

${\bigg{\lVert}\sum\limits_{t=1}^{\bar{T}}\mathbb{E}[X^{2}_{t}]\bigg{\rVert}}_{2}=\lambda_{\max}(Y)\leq\lambda_{\max}\left(\frac{\bar{T}}{d}I_{d}\right)=\frac{\bar{T}}{d}.$
(30)

Setting $K=1$, $N=\bar{T}$, $\epsilon=\bar{T}/{2d}$, using
$\sigma^{2}\leq\bar{T}/d$, and appealing to Lemma 3, we obtain

$\mathbb{P}\left({\bigg{\lVert}\sum_{t=1}^{\bar{T}}X_{t}\bigg{\rVert}}_{2}\geq\frac{\bar{T}}{2d}\right)\leq\delta,\hskip
5.69054pt\textrm{if}\hskip
5.69054pt\bar{T}\geq\frac{28d}{3}\log\left(\frac{2d}{\delta}\right).$ (31)

Suppose $\bar{T}$ satisfies the condition above, and let
$Z=\sum_{t=1}^{\bar{T}}X_{t}$. We then have that with probability at least
$1-\delta$,

${\|Z\|}_{2}<\frac{\bar{T}}{2d}.$ (32)

Since

$\sum_{t=1}^{\bar{T}}a_{t}a^{\prime}_{t}=Z+\bar{T}\bar{\Sigma},$ (33)

it holds that

$\psi\left(\sum_{t=1}^{\bar{T}}a_{t}a^{\prime}_{t}\right)=\psi(Z)+\frac{\bar{T}}{d},$
(34)

where we used $\psi(A)$ to denote an arbitrary eigenvalue of a matrix $A$. Now
notice that

$|\psi(Z)|\leq\rho(Z)={\|Z\|}_{2}<\frac{\bar{T}}{2d},$

where we used the fact that $Z$ is symmetric, and (32). We also used $\rho(Z)$
to denote the spectral radius of $Z$. The above inequality along with (34)
immediately leads to the following:

$\lambda_{\min}\left(\sum\limits_{t=1}^{\bar{T}}a_{t}a^{\prime}_{t}\right)\geq\frac{\bar{T}}{2d}.$

Combining all the above pieces, we have that with probability at least
$1-\delta$,

$\lambda_{\min}(V_{t})\geq\lambda_{\min}(V_{\bar{T}})\geq\lambda_{\min}\left(\sum\limits_{t=1}^{\bar{T}}a_{t}a^{\prime}_{t}\right)\geq\frac{\bar{T}}{2d},\forall
t\geq\bar{T},$

which is the desired conclusion. To arrive at (25), we simply note that the
choice $\bar{T}=\lceil 10L^{2}d\sqrt{T}\log(dLT)\rceil$ satisfies the
criterion that $\bar{T}\geq\frac{28d}{3}\log(2d/\delta)$, with $\delta=2/T$. ∎

The next simple lemma concerns the deviation of the noise sequence.

######  Lemma 7.

The following is true:

$\mathbb{P}\left(\exists
t\in[T]:|\eta_{t}|\geq\sqrt{4\log(T)}\right)\leq\frac{2}{T}.$ (35)

###### Proof.

Recalling that each $\eta_{t}$ is 1-subgaussian, and applying the union bound,
we obtain

$\displaystyle\mathbb{P}\left(\exists
t\in[T]:|\eta_{t}|\geq\sqrt{4\log(T)}\right)$
$\displaystyle\leq\sum_{t\in[T]}\mathbb{P}\left(|\eta_{t}|\geq\sqrt{4\log(T)}\right)$
(36) $\displaystyle\leq T\times\frac{2}{T^{2}},$

where the last inequality follows from invoking the Hoeffding bound for
subgaussian random variables; see for instance [25, Theorem 5.3]. ∎

The next step is to construct a “clean event” for our subsequent analysis. To
this end, consider the following three events.

$\displaystyle\mathcal{G}_{1}$ $\displaystyle=\\{\lambda_{\min}(V_{t})\geq
5L^{2}\sqrt{T}\log(dLT),\forall t\geq\bar{T}\\}.$ (37)
$\displaystyle\mathcal{G}_{2}$
$\displaystyle=\\{|\eta_{t}|<\sqrt{4\log(T)},\forall t\in[T]\\}.$
$\displaystyle\mathcal{G}_{3}$
$\displaystyle=\\{\theta_{*}\in\mathcal{C}_{t},\forall t\in[T]\\},$

where $\mathcal{C}_{t}$ is as in (23). Let
$\mathcal{G}=\mathcal{G}_{1}\cap\mathcal{G}_{2}\cap\mathcal{G}_{3}$. In words,
$\mathcal{G}$ is an event on which (i) the minimum eigenvalue of the
covariance matrix is suitably bounded from below, (ii) the noise sequence is
well-behaved, and (iii) the true parameter $\theta_{*}$ lies in a known
confidence region. Setting $\delta=1/T$ in Lemma 4, and using Lemma’s 6 and 7,
we immediately obtain that

$\mathbb{P}(\mathcal{G})\geq 1-\frac{5}{T}.$ (38)

In what follows, we will condition on the clean event $\mathcal{G}$. Our next
step is to bound the gap between consecutive estimates of $\theta_{*}$ at the
agent.

######  Lemma 8.

On the event $\mathcal{G}$, the following holds $\forall t\geq\bar{T}$:

${\|\hat{\theta}^{(a)}_{t+1}-\hat{\theta}^{(a)}_{t}\|}_{2}\leq f(T),\hskip
5.69054pt\textrm{where}\hskip
5.69054ptf(T)\triangleq\frac{3}{5L}\sqrt{\frac{\beta_{T}}{T\log(dLT)}}.$ (39)

###### Proof.

We first develop a recursion relating $\hat{\theta}^{(a)}_{t+1}$ to
$\hat{\theta}^{(a)}_{t}$. Based on (3), observe that

$\displaystyle\hat{\theta}^{(a)}_{t+1}$
$\displaystyle=V^{-1}_{t+1}\left(\sum\limits_{s=1}^{t+1}a_{s}y_{s}\right)$
(40)
$\displaystyle=V^{-1}_{t+1}\left(\sum\limits_{s=1}^{t}a_{s}y_{s}+a_{t+1}y_{t+1}\right)$
$\displaystyle=V^{-1}_{t+1}\left(V_{t}\hat{\theta}^{(a)}_{t}+a_{t+1}y_{t+1}\right)$
$\displaystyle=V^{-1}_{t+1}\left(\left(V_{t+1}-a_{t+1}a^{\prime}_{t+1}\right)\hat{\theta}^{(a)}_{t}+a_{t+1}y_{t+1}\right)$
$\displaystyle=\hat{\theta}^{(a)}_{t}+V^{-1}_{t+1}a_{t+1}\left(y_{t+1}-\langle
a_{t+1},\hat{\theta}^{(a)}_{t}\rangle\right)$
$\displaystyle=\hat{\theta}^{(a)}_{t}+V^{-1}_{t+1}a_{t+1}\left(y_{t+1}-\langle
a_{t+1},\theta_{*}\rangle+\langle\theta_{*}-\hat{\theta}^{(a)}_{t},a_{t+1}\rangle\right)$
$\displaystyle=\hat{\theta}^{(a)}_{t}+V^{-1}_{t+1}a_{t+1}\eta_{t+1}+V^{-1}_{t+1}a_{t+1}\left(\langle\theta_{*}-\hat{\theta}^{(a)}_{t},a_{t+1}\rangle\right).$

For the last step, we used the expression of the observation model in (1).
From (40), we immediately obtain:

${\|{\hat{\theta}^{(a)}_{t+1}-\hat{\theta}^{(a)}_{t}}\|}_{2}\leq\underbrace{\bigg{\lVert}V^{-1}_{t+1}a_{t+1}\eta_{t+1}\bigg{\rVert}_{2}}_{T_{1}}+\underbrace{\bigg{\lVert}V^{-1}_{t+1}a_{t+1}\left(\langle\theta_{*}-\hat{\theta}^{(a)}_{t},a_{t+1}\rangle\right)\bigg{\rVert}_{2}}_{T_{2}}.$
(41)

We now proceed to bound each of the terms $T_{1}$ and $T_{2}$ separately. To
this end, suppose $t\geq\bar{T},$ and note that we are on the event
$\mathcal{G}$. We then have

$\displaystyle T_{1}$
$\displaystyle\leq|\eta_{t+1}|{\|a_{t+1}\|}_{2}{\|V^{-1}_{t+1}\|}_{2}$ (42)
$\displaystyle\leq L\sqrt{4\log(T)}{\|V^{-1}_{t+1}\|}_{2},$

where we used the property of event $\mathcal{G}_{2}$ in (37) and the bound on
the actions from Assumption 1. Appealing to the property of event
$\mathcal{G}_{1}$ in (37), we have:

${\|V^{-1}_{t+1}\|}_{2}=\lambda_{\max}(V^{-1}_{t+1})=\frac{1}{\lambda_{\min}(V_{t+1})}\leq\frac{1}{5L^{2}\sqrt{T}\log(dLT)}.$
(43)

Combining the above bound with that in (42), we obtain

$\displaystyle T_{1}$
$\displaystyle\leq\frac{2\sqrt{\log(T)}}{5L\sqrt{T}\log(dLT)}$ (44)
$\displaystyle\leq\frac{2\sqrt{\log(dLT)}}{5L\sqrt{T}\log(dLT)}$
$\displaystyle=\frac{2}{5L\sqrt{T\log(dLT)}},$

where for the second step, we used $dL\geq 1$. For bounding the term $T_{2}$,
we proceed as follows:

$\displaystyle T_{2}$
$\displaystyle\leq{\|V^{-1}_{t+1}\|}_{2}{\|a_{t+1}\|}_{2}\left|\left(\langle\theta_{*}-\hat{\theta}^{(a)}_{t},a_{t+1}\rangle\right)\right|$
(45)
$\displaystyle\overset{(a)}{\leq}\frac{1}{5L\sqrt{T}\log(dLT)}\left|\left(\langle\theta_{*}-\hat{\theta}^{(a)}_{t},a_{t+1}\rangle\right)\right|$
$\displaystyle\leq\frac{1}{5L\sqrt{T}\log(dLT)}{\|\theta_{*}-\hat{\theta}^{(a)}_{t}\|}_{V_{t}}{\|a_{t+1}\|}_{V^{-1}_{t}}$
$\displaystyle\overset{(b)}{\leq}\frac{\sqrt{\beta_{T}}}{5L\sqrt{T}\log(dLT)}{\|a_{t+1}\|}_{V^{-1}_{t}}.$

In the above steps, we used (43) and the bound on the actions for (a); and the
property of the event $\mathcal{G}_{3}$ for (b). As for the term
${\|a_{t+1}\|}_{V^{-1}_{t}}$, observe

$\displaystyle{\|a_{t+1}\|}_{V^{-1}_{t}}$
$\displaystyle=\sqrt{a^{\prime}_{t+1}V^{-1}_{t}a_{t+1}}$ (46)
$\displaystyle\leq\sqrt{{\|a_{t+1}\|}^{2}_{2}\,\lambda_{\max}(V^{-1}_{t})}$
$\displaystyle\leq\sqrt{\frac{1}{5\sqrt{T}\log(dLT)}}.$

For the last step, we used (43). Combining the above inequality with that in
(45), we obtain

$T_{2}\leq\frac{\sqrt{\beta_{T}}}{L{\left(5\sqrt{T}\log(dLT)\right)}^{\frac{3}{2}}}.$
(47)

Putting together the bounds in (41), (44), and (47), and simplifying, we
obtain the bound in (39). This concludes the proof. ∎

The next lemma justifies the adaptive encoding strategy outlined in Algorithm
1.

######  Lemma 9.

(Encoding Region) On the event $\mathcal{G}$, the following is true:

$e_{t}\in\mathcal{B}_{d}(0,p_{t}),\forall t\in\\{\bar{T}+1,\ldots,T\\},$

where $e_{t}$ is the innovation in line 2 of Algorithm 1, and $p_{t}$ is as
defined in Eq. (4).

###### Proof.

We will prove this result by induction. We start by establishing the base
case.

Base Case. Our goal is to establish that
$e_{\bar{T}+1}\in\mathcal{B}_{d}(0,p_{\bar{T}+1})$. Based on the property of
event $\mathcal{G}_{3}$, let us note the following:

$\displaystyle{\|\theta_{*}-\hat{\theta}^{(a)}_{\bar{T}+1}\|}^{2}_{V_{\bar{T}+1}}\leq\beta_{T}$
(48)
$\displaystyle\implies{\left(\theta_{*}-\hat{\theta}^{(a)}_{\bar{T}+1}\right)}^{\prime}V_{\bar{T}+1}\left(\theta_{*}-\hat{\theta}^{(a)}_{\bar{T}+1}\right)\leq\beta_{T}$
$\displaystyle\implies\lambda_{\min}(V_{\bar{T}+1}){\|\theta_{*}-\hat{\theta}^{(a)}_{\bar{T}+1}\|}^{2}_{2}\leq\beta_{T}$
$\displaystyle\implies{\|\theta_{*}-\hat{\theta}^{(a)}_{\bar{T}+1}\|}_{2}\leq\sqrt{\frac{\beta_{T}}{\lambda_{\min}(V_{\bar{T}+1})}}$
$\displaystyle\implies{\|\hat{\theta}^{(a)}_{\bar{T}+1}\|}_{2}\leq{\|\theta_{*}\|}_{2}+\sqrt{\frac{\beta_{T}}{\lambda_{\min}(V_{\bar{T}+1})}}$
$\displaystyle\implies{\|\hat{\theta}^{(a)}_{\bar{T}+1}\|}_{2}\leq
M+\sqrt{\frac{\beta_{T}}{5L^{2}\sqrt{T}\log(dLT)}},$

where for the last step, we used (43), and the fact that
${\|\theta_{*}\|}_{2}\leq M$ since $\theta_{*}\in\Theta$. To proceed, we
simplify the resulting expression above by plugging in the expression for
$\beta_{T}$ from Eq. (7) with $\delta=1/T$. This yields:

$\displaystyle\sqrt{\frac{\beta_{T}}{5L^{2}\sqrt{T}\log(dLT)}}$
$\displaystyle=\frac{\sqrt{\lambda}M}{\sqrt{{5L^{2}\sqrt{T}\log(dLT)}}}+\sqrt{\frac{2\log\left(T\right)+d\log\left(\frac{d\lambda+TL^{2}}{d\lambda}\right)}{5L^{2}\sqrt{T}\log(dLT)}}$
(49)
$\displaystyle\leq\sqrt{\lambda}M+\sqrt{\frac{2}{5L^{2}\sqrt{T}}+\frac{4d}{5L^{2}\sqrt{T}}}$
$\displaystyle\leq\left(\sqrt{\lambda}+\sqrt{\frac{6d}{5L^{2}\sqrt{T}}}\right)M$
$\displaystyle\leq 3M.$

In the above steps, we set the regularization parameter $\lambda=1$, and used
the following facts: $M\geq 1$, $L\geq 1$, $\log(dLT)\geq 1$, and $T\geq
d^{2}$. Combining the above bound with that in (48), we obtain

${\|\hat{\theta}^{(a)}_{\bar{T}+1}\|}_{2}\leq 4M.$

We thus have

$\displaystyle{\|e_{\bar{T}+1}\|}_{2}$
$\displaystyle=\|{\hat{\theta}^{(a)}_{\bar{T}+1}-\hat{\theta}^{(s)}_{\bar{T}}\|}_{2}$
(50)
$\displaystyle\leq\|{\hat{\theta}^{(a)}_{\bar{T}+1}\|}_{2}+\|{\hat{\theta}^{(s)}_{\bar{T}}\|}_{2}$
$\displaystyle\leq 4M+M$ $\displaystyle\leq 5M+\frac{3}{2}f(T)=p_{\bar{T}+1},$

where we used the fact that $\hat{\theta}^{(s)}_{\bar{T}}\in\Theta$, and
hence, $\|{\hat{\theta}^{(s)}_{\bar{T}}\|}_{2}\leq M$. We have thus
established that ${\|e_{\bar{T}+1}\|}_{2}\leq p_{\bar{T}+1}$, implying that
$e_{\bar{T}+1}\in\mathcal{B}_{d}(0,p_{\bar{T}+1}).$ This completes the base
case.

Induction Step. Now suppose for all $t\in\\{\bar{T}+1,\ldots,k\\}$, it holds
that $e_{t}\in\mathcal{B}_{d}(0,p_{t})$. Here,
$k\in\\{\bar{T}+2,\ldots,T-1\\}$. Our goal is to establish that
$e_{k+1}\in\mathcal{B}_{d}(0,p_{k+1})$. Based on the induction hypothesis,
$e_{k}\in\mathcal{B}_{d}(0,p_{k})$, and hence, the encoding operation outlined
in Algorithm 1 is valid at time-step $k$. Recall that $\tilde{e}_{k}$ is the
center of the ball (of radius $\epsilon p_{k}$) that contains $e_{k}$. Based
on the definition of an $\epsilon p_{k}$ net, we then immediately have

${\|\tilde{e}_{k}-e_{k}\|}_{2}\leq\epsilon p_{k}=\frac{1}{2}p_{k},$ (51)

with $\epsilon$ set to $1/2$. Now observe

$\displaystyle\hat{\theta}^{(s)}_{k}$
$\displaystyle=\hat{\theta}^{(s)}_{k-1}+\tilde{e}_{k}$ (52)
$\displaystyle=\hat{\theta}^{(s)}_{k-1}+e_{k}+\tilde{e}_{k}-e_{k}$
$\displaystyle=\hat{\theta}^{(s)}_{k-1}+\left(\hat{\theta}^{(a)}_{k}-\hat{\theta}^{(s)}_{k-1}\right)+\tilde{e}_{k}-e_{k}$
$\displaystyle=\hat{\theta}^{(a)}_{k}+\tilde{e}_{k}-e_{k}.$

Based on the above display and (51), we conclude

${\|\hat{\theta}^{(s)}_{k}-\hat{\theta}^{(a)}_{k}\|}_{2}={\|\tilde{e}_{k}-e_{k}\|}_{2}\leq\frac{1}{2}p_{k}.$
(53)

We then have

$\displaystyle e_{k+1}$
$\displaystyle=\hat{\theta}^{(a)}_{k+1}-\hat{\theta}^{(s)}_{k}$ (54)
$\displaystyle=\left(\hat{\theta}^{(a)}_{k+1}-\hat{\theta}^{(a)}_{k}\right)+\left(\hat{\theta}^{(a)}_{k}-\hat{\theta}^{(s)}_{k}\right).$

The triangle inequality then yields

$\displaystyle{\|e_{k+1}\|}_{2}$
$\displaystyle\leq{\|\hat{\theta}^{(a)}_{k+1}-\hat{\theta}^{(a)}_{k}\|}_{2}+{\|\hat{\theta}^{(a)}_{k}-\hat{\theta}^{(s)}_{k}\|}_{2}$
(55) $\displaystyle\overset{(a)}{\leq}f(T)+\frac{1}{2}p_{k}$
$\displaystyle\overset{(b)}{=}f(T)+\frac{1}{2}\left(q_{k}+f(T)\right)$
$\displaystyle\overset{(c)}{=}f(T)+q_{k+1}$
$\displaystyle\overset{(d)}{=}p_{k+1}.$

In the above steps, we used Lemma 39 and Eq. (53) for (a), and the definitions
of $p_{k},q_{k},p_{k+1}$, and $q_{k+1}$ from Eq. (4) for (b)-(d). Since
${\|e_{k+1}\|}_{2}\leq p_{k+1}$, it follows that
$e_{k+1}\in\mathcal{B}_{d}(0,p_{k+1})$, thereby establishing the induction
claim. This completes the proof. ∎

The next key result justifies the decision-making rule in lines 8-9 of the IC-
LinUCB algorithm.

######  Lemma 10.

(Confidence Region at Server) On the event $\mathcal{G}$, the following is
true: $\theta_{*}\in\mathcal{C}^{(s)}_{t},\forall
t\in\\{\bar{T}+2,\ldots,T\\}$, where

$\mathcal{C}^{(s)}_{t}=\\{\theta\in\mathbb{R}^{d}:{\|\theta-\hat{\theta}^{(s)}_{t-1}\|}_{V_{t-1}}\leq\sqrt{\beta_{T}}+{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\left(\sqrt{\lambda+(t-1)L^{2}}\right)q_{t}\\}}.$

Moreover, $\forall t\geq\bar{T}+\tilde{T}$, we have

$\left(\sqrt{\lambda+(t-1)L^{2}}\right)q_{t}\leq
4\sqrt{\frac{\beta_{T}}{\log(dLT)}},$ (56)

where

$\tilde{T}=\left\lceil\frac{\log\left(\frac{10M}{f(T)}\right)}{\log(2)}\right\rceil\vee
2=O\left(\log(dLT)\right).$ (57)

###### Proof.

Consider any $t\in\\{\bar{T}+2,\ldots,T\\}$. We then have

$\displaystyle{\|\hat{\theta}^{(s)}_{t-1}-\theta^{*}\|}_{V_{t-1}}$
$\displaystyle\overset{(a)}{\leq}{\|\hat{\theta}^{(a)}_{t-1}-\theta^{*}\|}_{V_{t-1}}+{\|\hat{\theta}^{(s)}_{t-1}-\hat{\theta}^{(a)}_{t-1}\|}_{V_{t-1}}$
(58)
$\displaystyle\overset{(b)}{\leq}\sqrt{\beta_{T}}+\sqrt{\left(\hat{\theta}^{(s)}_{t-1}-\hat{\theta}^{(a)}_{t-1}\right)^{\prime}V_{t-1}\left(\hat{\theta}^{(s)}_{t-1}-\hat{\theta}^{(a)}_{t-1}\right)}$
$\displaystyle\leq\sqrt{\beta_{T}}+\sqrt{\lambda_{\max}(V_{t-1}){\|\hat{\theta}^{(s)}_{t-1}-\hat{\theta}^{(a)}_{t-1}\|}^{2}_{2}}$
$\displaystyle\overset{(c)}{\leq}\sqrt{\beta_{T}}+\sqrt{\lambda_{\max}(V_{t-1})}\left(\frac{1}{2}{p_{t-1}}\right)$
$\displaystyle\overset{(d)}{=}\sqrt{\beta_{T}}+\sqrt{\lambda_{\max}(V_{t-1})}\left(\frac{1}{2}\left(q_{t-1}+f(T)\right)\right)$
$\displaystyle\overset{(e)}{=}\sqrt{\beta_{T}}+\left(\sqrt{\lambda_{\max}(V_{t-1})}\right)q_{t}$
$\displaystyle\leq\sqrt{\beta_{T}}+\left(\sqrt{\lambda+(t-1)L^{2}}\right)q_{t}.$

In the above steps, (a) follows from the triangle inequality; (b) follows from
the defining property of event $\mathcal{G}_{3}$; (c) follows from Eq. (53) in
the analysis of Lemma 1 (restated as Lemma 9 in the Appendix); and (d), (e)
are a consequence of Eq. (4). This establishes the first claim of the lemma.

For the second claim of the lemma, we roll out the recursion
$q_{t}=\epsilon(q_{t-1}+f(T))$ for $\tau>0$ time-steps starting from
$\bar{T}$:

$\displaystyle q_{\bar{T}+\tau}$
$\displaystyle={\epsilon}^{\tau}q_{\bar{T}}+\left(\sum\limits_{k=1}^{\tau}\epsilon^{k}\right)f(T)$
(59)
$\displaystyle\leq{\epsilon}^{\tau}q_{\bar{T}}+\left(\sum\limits_{k=0}^{\infty}\epsilon^{k}\right)f(T)$
$\displaystyle={\epsilon}^{\tau}q_{\bar{T}}+\frac{f(T)}{1-\epsilon}$
$\displaystyle=10M{\left(\frac{1}{2}\right)}^{\tau}+2f(T),$

where for the last step, we used $\epsilon=1/2$, and $q_{\bar{T}}=10M$. Now it
is easy to verify that when

$\tau\geq\left\lceil\frac{\log\left(\frac{10M}{f(T)}\right)}{\log(2)}\right\rceil,$

it holds that

$10M{\left(\frac{1}{2}\right)}^{\tau}\leq 2f(T),$

and hence, $q_{\bar{T}+\tau}\leq 4f(T)$. Thus, for $t\geq\bar{T}+\tilde{T}$,
where $\tilde{T}$ is as defined in Eq. (57), we have

$\displaystyle\left(\sqrt{\lambda+(t-1)L^{2}}\right)q_{t}$ $\displaystyle\leq
4\left(\sqrt{\lambda+TL^{2}}\right)f(T)$ (60)
$\displaystyle=\frac{12}{5}\sqrt{\frac{(\lambda+TL^{2})\beta_{T}}{TL^{2}\log(dLT)}}$
$\displaystyle\leq 4\sqrt{\frac{\beta_{T}}{\log(dLT)}},$

where for the last step, we used $\lambda=1$, and $TL^{2}\geq 1$. The fact
that $\tilde{T}=O(\log(dLT))$ follows by plugging in the expression for $f(T)$
from (39), and then some simple algebra. ∎

We are now equipped with all the pieces required for proving Theorem 1.

###### Proof.

(Proof of Theorem 1) Let us condition on the clean event $\mathcal{G}$, and
consider a time-step $t\geq{\bar{T}}+\tilde{T}+1$. Let $\tilde{\theta}_{t}$ be
such that

$(a_{t},\tilde{\theta}_{t})=\operatorname*{\arg\\!\max}_{(a,\theta)\in\mathcal{A}_{t}\times\mathcal{C}^{(s)}_{t}}\langle\theta,a\rangle,$

where $\mathcal{C}^{(s)}_{t}$ is as defined in Eq. (5). Next, let
$a^{*}_{t}=\operatorname*{\arg\\!\max}_{a\in\mathcal{A}_{t}}\langle\theta_{*},a\rangle$
be an optimal action at time-step $t$. We now proceed to bound the
instantaneous regret $r_{t}=\langle\theta_{*},a^{*}_{t}-a_{t}\rangle$ as
follows:

$\displaystyle r_{t}$ $\displaystyle\overset{(a)}{\leq}\langle
a_{t},\tilde{\theta}_{t}-\theta_{*}\rangle$ (61)
$\displaystyle\leq{\|a_{t}\|}_{V^{-1}_{t-1}}\,{\|\theta_{*}-\tilde{\theta}_{t}\|}_{V_{t-1}}$
$\displaystyle\overset{(b)}{\leq}2\left(1+4\sqrt{\frac{1}{\log(dLT)}}\right){\|a_{t}\|}_{V^{-1}_{t-1}}\sqrt{\beta_{T}}$
$\displaystyle\leq 10{\|a_{t}\|}_{V^{-1}_{t-1}}{\sqrt{\beta_{T}}}.$

In the above steps, (a) follows from the fact that
$\theta_{*}\in\mathcal{C}^{(s)}_{t},\forall t\geq\bar{T}+2$ on the event
$\mathcal{G}$ as per Lemma 10. Hence,
$\langle\theta_{*},a^{*}_{t}\rangle\leq\langle\tilde{\theta}_{t},a_{t}\rangle$.
For (b), we invoked the bound from (56), and combined it with Eq. (58). Using
the fact that $r_{t}\leq 10\leq 10\sqrt{\beta_{T}}$ (based on Assumption
1(i)), and combining it with the above bound, we finally obtain

$r_{t}\leq 10\sqrt{\beta_{T}}\left(1\wedge{\|a_{t}\|}_{V^{-1}_{t-1}}\right).$

We now follow certain standard steps.

$\displaystyle\sum_{t=\bar{T}+\tilde{T}+1}^{T}\left(1\wedge{\|a_{t}\|}^{2}_{V^{-1}_{t-1}}\right)$
$\displaystyle\leq
2\sum_{t=\bar{T}+\tilde{T}+1}^{T}\log\left(1+{\|a_{t}\|}^{2}_{V^{-1}_{t-1}}\right)$
(62)
$\displaystyle=2\sum_{t=\bar{T}+\tilde{T}+1}^{T}\log\left(\frac{\det(V_{t})}{\det(V_{t-1})}\right)$
$\displaystyle=2\log\left(\frac{\det(V_{{T}})}{\det(V_{\bar{T}+\tilde{T}})}\right),$

where for the first two steps, we used [25, Lemma 19.4]. Based on Jensen’s
inequality, we then have

$\displaystyle\sum_{t=\bar{T}+\tilde{T}+1}^{T}r_{t}$
$\displaystyle\leq\sqrt{\left(T-(\bar{T}+\tilde{T})\right)\sum_{t=\bar{T}+\tilde{T}+1}^{T}r^{2}_{t}}$
(63) $\displaystyle\leq
10\sqrt{\left(T-(\bar{T}+\tilde{T})\right)\beta_{T}\sum_{t=\bar{T}+\tilde{T}+1}^{T}\left(1\wedge{\|a_{t}\|}^{2}_{V^{-1}_{t-1}}\right)}$
$\displaystyle\leq
10\sqrt{2\left(T-(\bar{T}+\tilde{T})\right)\beta_{T}\log\left(\frac{\det(V_{{T}})}{\det(V_{\bar{T}+\tilde{T}})}\right)}.$

Based on Assumption 1(i), we note that $r_{t}$ is trivially at most $1$ at
each time-step $t\in[\bar{T}+\tilde{T}]$. Thus, we have:

$\displaystyle\sum_{t=1}^{\bar{T}+\tilde{T}}r_{t}$
$\displaystyle\leq\bar{T}+\tilde{T}$ (64) $\displaystyle\leq\left\lceil
10L^{2}d\sqrt{T}\log(dLT)\right\rceil+\left\lceil\frac{\log\left(\frac{10M}{f(T)}\right)}{\log(2)}\right\rceil\vee
2$ $\displaystyle=O(L^{2}d\sqrt{T}\log(dLT)).$

Combining the above bound with that in Eq. (63), we obtain the following bound
on the total regret conditioned on the clean event $\mathcal{G}$:

$\sum_{t=1}^{T}r_{t}\leq
O(L^{2}d\sqrt{T}\log(dLT))+\underbrace{10\sqrt{2\left(T-(\bar{T}+\tilde{T})\right)\beta_{T}\log\left(\frac{\det(V_{{T}})}{\det(V_{\bar{T}+\tilde{T}})}\right)}}_{T_{3}}.$
(65)

For bounding $T_{3}$, we note based on the AM-GM inequality that

$\det(V_{T})=\prod_{i=1}^{d}\lambda_{i}(V_{T})\leq{\left(\frac{1}{d}\textrm{Trace}(V_{T})\right)}^{d}\leq{\left(\frac{d\lambda+TL^{2}}{d}\right)}^{d}.$

Moreover, note that
$\det(V_{\bar{T}+\tilde{T}})\geq\det(V_{0})=\lambda^{d}$.888At this stage, we
could have used a tighter lower bound on $\det(V_{\bar{T}+\tilde{T}})$ as
follows:
$\det(V_{\bar{T}+\tilde{T}})\geq\det(V_{\bar{T}})\geq{\left(\lambda_{\min}(V_{\bar{T}})\right)}^{d}\geq{\left(5L^{2}\sqrt{T}\log(dLT)\right)}^{d}$,
where the last inequality follows from (43). While this will improve the bound
for $T_{3}$, the improvement is of no consequence since $T_{3}$ will be
dominated by the additive term $O(L^{2}d\sqrt{T}\log(dLT))$. Combining this
bound with the one above for $\det(V_{T})$, plugging in the expression for
$\beta_{T}$ from Eq. (7) in $T_{3}$, and then simplifying, it is easy to
verify that $T_{3}=O(d\sqrt{T}\log(LT))$. We have thus argued that on the
clean event $\mathcal{G}$, the overall regret is of order
$O(L^{2}d\sqrt{T}\log(dLT))+O(d\sqrt{T}\log(LT))=O(L^{2}d\sqrt{T}\log(dLT))$.

Let $\mathcal{I}_{\mathcal{G}}$ represent an indicator random variable for the
event $\mathcal{G}$. Moreover, recall from (38) that
$\mathbb{P}(\mathcal{G}^{c})\leq 5/T$. We now proceed to bound the regret
$R_{T}$ as follows:

$\displaystyle R_{T}$
$\displaystyle=\mathbb{E}\left[\sum_{t=1}^{T}r_{t}\right]$ (66)
$\displaystyle=\mathbb{E}\left[\left(\sum_{t=1}^{T}r_{t}\right)\left(\mathcal{I}_{\mathcal{G}}+\mathcal{I}_{\mathcal{G}^{c}}\right)\right]$
$\displaystyle=\mathbb{E}\left[\left(\sum_{t=1}^{T}r_{t}\right)\mathcal{I}_{\mathcal{G}}\right]+\mathbb{E}\left[\left(\sum_{t=1}^{T}r_{t}\right)\mathcal{I}_{\mathcal{G}^{c}}\right]$
$\displaystyle\overset{(a)}{\leq}CL^{2}d\sqrt{T}\log(dLT)+T\mathbb{P}(\mathcal{I}_{\mathcal{G}^{c}})$
$\displaystyle\overset{(b)}{\leq}CL^{2}d\sqrt{T}\log(dLT)+T\times\frac{5}{T}$
$\displaystyle=O(L^{2}d\sqrt{T}\log(dLT)),$

where $C$ is a suitably large universal constant. To bound the second term in
(a), we used the fact that $R_{T}$ is trivially bounded above by $T$. For (b),
we used (38). This establishes the claim regarding the regret. We now turn our
attention to the capacity of the channel.

Communication Complexity. Recall that in the first $\bar{T}$ time-steps, there
is no transmission from the agent to the server. For each $t\geq\bar{T}+1$,
our encoding strategy involves constructing an $\epsilon p_{t}$ \- net of the
ball $\mathcal{B}_{d}(0,p_{t})$. Invoking Lemma 5 with
$\mathcal{K}=\mathcal{B}_{d}(0,p_{t})$, we obtain:

$\displaystyle\mathcal{N}(\mathcal{B}_{d}(0,p_{t}),\epsilon\\-p_{t})$
$\displaystyle\leq\frac{|\left(\mathcal{B}_{d}(0,p_{t})\oplus(\epsilon
p_{t}/2)\mathcal{B}_{d}(0,1)\right)|}{|(\epsilon
p_{t}/2)\mathcal{B}_{d}(0,1)|}$ (67)
$\displaystyle=\frac{|\left(1+\epsilon/2\right)p_{t}\mathcal{B}_{d}(0,1)|}{|(\epsilon
p_{t}/2)\mathcal{B}_{d}(0,1)|}$
$\displaystyle=\frac{\left[{\left(1+\epsilon/2\right)p_{t}}\right]^{d}}{\left[\left(\epsilon/2\right)p_{t}\right]^{d}}$
$\displaystyle=\left(\frac{2}{\epsilon}+1\right)^{d}.$

Thus, with $\epsilon=\frac{1}{2}$ in Algorithm 1, we obtain
$\mathcal{N}(\mathcal{B}_{d}(0,p_{t}),\epsilon\\-p_{t})\leq 5^{d}$. To account
for the possibility of an overflow, we need one additional symbol. Thus, the
size of the alphabet $\Sigma$ needed to encode the innovation $e_{t}$ at any
time-step is at most $5^{d}+1<5^{d+1}$. We conclude that it suffices for the
channel capacity $B$ to satisfy

$B\geq\left\lfloor(d+1)\log_{2}(5)\right\rfloor+1.$

Since $d\geq 1$, $B\geq 6d$ bits suffice. This completes the proof. ∎

##  Appendix C Analysis of the Generalized Linear Model under
Information Constraints

In this section, we will analyze the information constrained GLM-UCB algorithm
that was developed in Section 5. Before doing so, we remind the reader of the
observation model:

$y_{t}=\mu\left(\langle\theta^{*},a_{t}\rangle\right)+\eta_{t},$

and the invertible function $g_{t}(\theta)$ defined as follows:

$g_{t}(\theta)=\lambda\theta+\sum_{s=1}^{t}\mu(\langle\theta,a_{s}\rangle)a_{s}.$

Algorithm 3 Adaptive Encoding at the Agent for the Generalized Linear Model

1: Input Parameters: $\hat{\theta}^{(s)}_{\bar{T}}$ is any arbitrary vector in
$\Theta$; $q_{\bar{T}}=2\left(2+\frac{3}{\sqrt{k_{1}k_{2}}}\right)M$; and
$\bar{f}(T)=\frac{3}{5L}\sqrt{\frac{\beta_{T}}{k_{1}k_{2}T\log(dLT)}}$.

2:for $t\in\\{\bar{T}+1,\ldots,T\\}$ do

3: Observe $y_{t}$ and solve for $\hat{\theta}^{(a)}_{t}$ satisfying
$g_{t}(\hat{\theta}^{(a)}_{t})=\sum_{s=1}^{t}y_{s}a_{s}$. Compute
$e_{t}=\hat{\theta}^{(a)}_{t}-\hat{\theta}^{(s)}_{t-1}$.

4: Encode $e_{t}$ by constructing an $\epsilon p_{t}$-net of
$\mathcal{B}_{d}(0,p_{t})$, where
$q_{t}=\epsilon\left(q_{t-1}+\bar{f}(T)\right);\hskip
5.69054ptp_{t}=q_{t}+\bar{f}(T).$ (68)

5:end for

Algorithm 4 Information Constrained GLMUCB (IC-GLMUCB)

1: Input Parameters: $\bar{T}=\left\lceil
10(k_{2}/k_{1})L^{2}d\sqrt{T}\log(dLT)\right\rceil$.

2: Phase I: Pure Exploration

3:for $t\in\\{1,\ldots,\bar{T}+1\\}$ do

4: Server plays $a_{t}\sim\textrm{Unif}(\mathbb{S}^{d-1})$.

5: Agent receives reward $y_{t}$ as per (11) and solves
$\hat{\theta}^{(a)}_{t}$ satisfying
$g_{t}(\hat{\theta}^{(a)}_{t})=\sum_{s=1}^{t}y_{s}a_{s}.$

6:end for

7:Agent encodes
$e_{\bar{T}+1}=\hat{\theta}^{(a)}_{\bar{T}+1}-\hat{\theta}^{(s)}_{\bar{T}}$ as
per Algo. 3, and transmits
$\sigma_{\bar{T}+1}=\mathcal{E}_{\bar{T}+1}\left(e_{\bar{T}+1}\right)$.

8:

9: Phase II: Information-Constrained Exploration-Exploitation

10:for $t\in\\{\bar{T}+2,\ldots,T\\}$ do

11: Server decodes $\tilde{e}_{t-1}=\mathcal{D}_{t-1}(\sigma_{t-1})$, and
generates $\hat{\theta}^{(s)}_{t-1}=\hat{\theta}^{(s)}_{t-2}+\tilde{e}_{t-1}$.

12: Server constructs the following confidence set:
$\mathcal{\bar{C}}^{(s)}_{t}=\\{\theta\in\Theta:\mathcal{H}_{t-1}(\theta)\leq\sqrt{\beta_{T}}+k_{2}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\left(\sqrt{\lambda+(t-1)L^{2}}\right)q_{t}\\}},\hskip
2.84526pt\textrm{where}\hskip
2.84526pt\mathcal{H}_{t}(\theta)\triangleq{\|g_{t}(\theta)-g_{t}(\hat{\theta}^{(s)}_{t})\|}_{V^{-1}_{t}},$
where $q_{t}$, $V_{t-1}$, and $\sqrt{{\beta}_{T}}$ are given by (68), (3), and
(7), respectively.

13: Server plays action
$a_{t}=\operatorname*{\arg\\!\max}_{a\in\mathcal{A}_{t}}\max_{\theta\in\mathcal{\bar{C}}^{(s)}_{t}}\langle\theta,a\rangle$.

14: Agent receives reward $y_{t}$ as per (11) and solves
$\hat{\theta}^{(a)}_{t}$ satisfying
$g_{t}(\hat{\theta}^{(a)}_{t})=\sum_{s=1}^{t}y_{s}a_{s}$.

15: Agent encodes the innovation
$e_{t}=\hat{\theta}^{(a)}_{t}-\hat{\theta}^{(s)}_{t-1}$ as per Algo. 3, and
transmits $\sigma_{t}=\mathcal{E}_{t}(e_{t})$.

16:end for

###  C.1 Proof of Theorem 2

We start with the following fact that will be used repeatedly in our
subsequent analysis.

######  Lemma 11.

Consider any $\theta_{1},\theta_{2}\in\Theta$, and any $t\in[T]$. There exists
a symmetric positive definite matrix $G_{t}(\theta_{1};\theta_{2})$ satisfying
$k_{1}V_{t}\preccurlyeq G_{t}(\theta_{1};\theta_{2})\preccurlyeq k_{2}V_{t}$,
such that:

$g_{t}(\theta_{1})-g_{t}(\theta_{2})=G_{t}(\theta_{1};\theta_{2})(\theta_{1}-\theta_{2}).$
(69)

###### Proof.

For any $\theta\in\Theta$, let us denote by $\nabla g_{t}(\theta)$ the
Jacobian matrix of $g_{t}(\cdot)$ at $\theta$. Such a matrix exists based on
Assumption 2. Now based on the mean value theorem, $\exists\alpha\in(0,1)$
such that

$g_{t}(\theta_{1})-g_{t}(\theta_{2})=\left(\nabla
g_{t}\left(\alpha\theta_{1}+(1-\alpha)\theta_{2}\right)\right)(\theta_{1}-\theta_{2}).$

Let $\bar{\theta}=\alpha\theta_{1}+(1-\alpha)\theta_{2}$, and
$G_{t}(\theta_{1};\theta_{2})=\nabla g_{t}(\bar{\theta})$. It remains to argue
that the matrix $G_{t}(\theta_{1};\theta_{2})$ so defined is symmetric and
positive definite. To this end, let us note:

$\displaystyle\nabla g_{t}(\bar{\theta})$
$\displaystyle\overset{(a)}{=}\lambda
I+\sum_{s=1}^{t}\dot{\mu}(\langle\bar{\theta},a_{s}\rangle)a_{s}a^{\prime}_{s}$
(70) $\displaystyle\overset{(b)}{\succcurlyeq}k_{1}\left(\lambda
I+\sum_{s=1}^{t}a_{s}a^{\prime}_{s}\right)$ $\displaystyle=k_{1}V_{t}.$

Here, we used the definition of $g_{t}(\cdot)$ in (13) for (a), and for (b),
we used Assumption 2 and the fact that $k_{1}\leq 1$. The above steps reveal
that $G_{t}(\theta_{1};\theta_{2})$ is symmetric and positive definite (as
$V_{t}\succ 0$). The claim that $G_{t}(\theta_{1};\theta_{2})\preccurlyeq
k_{2}V_{t}$ follows a similar reasoning and relies on the fact that
$\mu(\cdot)$ is $k_{2}$-Lipschitz. ∎

The next result will be useful in the construction of the confidence region at
the server.

######  Lemma 12.

Given any $\delta\in(0,1)$, the following holds with probability at least
$1-\delta$:

${\bigg{\lVert}g_{t}(\theta_{*})-\sum_{s=1}^{t}y_{s}a_{s}\bigg{\rVert}}_{V^{-1}_{t}}\leq\sqrt{\beta_{T}},\forall
t\in[T],$

where $\beta_{T}$ is as defined in Eq. (7).

###### Proof.

We have

$\displaystyle{\bigg{\lVert}g_{t}(\theta_{*})-\sum_{s=1}^{t}y_{s}a_{s}\bigg{\rVert}}_{V^{-1}_{t}}$
$\displaystyle\overset{(a)}{=}{\bigg{\lVert}\lambda\theta_{*}+\sum_{s=1}^{t}\mu(\langle\theta_{*},a_{s}\rangle)a_{s}-\sum_{s=1}^{t}y_{s}a_{s}\bigg{\rVert}}_{V^{-1}_{t}}$
(71)
$\displaystyle={\bigg{\lVert}\lambda\theta_{*}+\sum_{s=1}^{t}\left(\mu(\langle\theta_{*},a_{s}\rangle)-y_{s}\right)a_{s}\bigg{\rVert}}_{V^{-1}_{t}}$
$\displaystyle\overset{(b)}{=}{\bigg{\lVert}\lambda\theta_{*}-\sum_{s=1}^{t}\eta_{s}a_{s}\bigg{\rVert}}_{V^{-1}_{t}}$
$\displaystyle\leq{\bigg{\lVert}\lambda\theta_{*}\bigg{\rVert}}_{V^{-1}_{t}}+{\bigg{\lVert}\sum_{s=1}^{t}\eta_{s}a_{s}\bigg{\rVert}}_{V^{-1}_{t}},$

where for (a), we used Eq. (13), and for (b), we used Eq. (11). Using
${\|\theta_{*}\|}_{2}\leq M$ and $\lambda_{\min}(V_{t})\geq\lambda$, it is
easy to see that

${\bigg{\lVert}\lambda\theta_{*}\bigg{\rVert}}_{V^{-1}_{t}}\leq\sqrt{\lambda}M.$

To bound the second term in the RHS of the resulting inequality in (71), we
invoke Theorem 20.4 in [25]. This yields that with probability at least
$1-\delta$, the following is true $\forall t\in[T]$:

${\bigg{\lVert}\sum_{s=1}^{t}\eta_{s}a_{s}\bigg{\rVert}}_{V^{-1}_{t}}\leq\sqrt{2\log\left(\frac{1}{\delta}\right)+\log\left(\frac{\det(V_{T})}{\lambda^{d}}\right)}.$

To complete the proof, we use the following fact derived in the analysis of
Theorem 1:

$\det(V_{T})\leq{\left(\frac{d\lambda+TL^{2}}{d}\right)}^{d}.$

Putting all the above pieces together leads to the desired conclusion. ∎

Since $\bar{T}=\left\lceil 10(k_{2}/k_{1})L^{2}d\sqrt{T}\log(dLT)\right\rceil$
in the IC-GLMUCB algorithm, following the same reasoning as in Lemma 6, we
have that with probability at least $1-2/T$,

$\lambda_{\min}(V_{t})\geq 5\frac{k_{2}}{k_{1}}L^{2}\sqrt{T}\log(dLT),\forall
t\geq\bar{T}.$ (72)

As in the analysis of Theorem 1, we will now work on a clean event that is the
intersection of the following three events.

$\displaystyle\mathcal{F}_{1}$ $\displaystyle=\\{\lambda_{\min}(V_{t})\geq
5(k_{2}/k_{1})L^{2}\sqrt{T}\log(dLT),\forall t\geq\bar{T}\\}.$ (73)
$\displaystyle\mathcal{F}_{2}$
$\displaystyle=\\{|\eta_{t}|<\sqrt{4\log(T)},\forall t\in[T]\\}.$
$\displaystyle\mathcal{F}_{3}$
$\displaystyle=\\{D_{t}(\theta_{*})\leq\sqrt{\beta_{T}},\forall t\in[T]\\},$

where

$D_{t}(\theta)={\bigg{\lVert}g_{t}(\theta)-\sum_{s=1}^{t}y_{s}a_{s}\bigg{\rVert}}_{V^{-1}_{t}}.$

Let $\mathcal{F}=\mathcal{F}_{1}\cap\mathcal{F}_{2}\cap\mathcal{F}_{3}$.
Setting $\delta=1/T$ in Lemma 12, and using Lemma’s 6 and 7, we immediately
obtain that

$\mathbb{P}(\mathcal{F})\geq 1-\frac{5}{T}.$ (74)

We now establish an analog of Lemma 39.

######  Lemma 13.

On the event $\mathcal{F}$, the following holds $\forall t\geq\bar{T}$:

${\|\hat{\theta}^{(a)}_{t+1}-\hat{\theta}^{(a)}_{t}\|}_{2}\leq\bar{f}(T),\hskip
5.69054pt\textrm{where}\hskip
5.69054pt\bar{f}(T)\triangleq\frac{3}{5L}\sqrt{\frac{\beta_{T}}{k_{1}k_{2}T\log(dLT)}}.$
(75)

###### Proof.

We start by noting that based on Eq. (14), $\hat{\theta}^{(a)}_{t+1}$
satisfies the following equation:

$\displaystyle g_{t+1}(\hat{\theta}^{(a)}_{t+1})$
$\displaystyle=\sum_{s=1}^{t+1}y_{s}a_{s}$ (76)
$\displaystyle=\sum_{s=1}^{t}y_{s}a_{s}+y_{t+1}a_{t+1}$
$\displaystyle=g_{t}(\hat{\theta}^{(a)}_{t})+y_{t+1}a_{t+1}.$

At the same time, in view of Eq. (13), we have

$\displaystyle g_{t+1}(\hat{\theta}^{(a)}_{t+1})$
$\displaystyle=\lambda\hat{\theta}^{(a)}_{t+1}+\sum_{s=1}^{t+1}\mu(\langle\hat{\theta}^{(a)}_{t+1},a_{s}\rangle)a_{s}$
(77)
$\displaystyle=g_{t}(\hat{\theta}^{(a)}_{t+1})+\mu(\langle\hat{\theta}^{(a)}_{t+1},a_{t+1}\rangle)a_{t+1}.$

Comparing the above equation with that in Eq. (76), we conclude:

$\displaystyle g_{t}(\hat{\theta}^{(a)}_{t+1})-g_{t}(\hat{\theta}^{(a)}_{t})$
$\displaystyle=\left(y_{t+1}-\mu(\langle\hat{\theta}^{(a)}_{t+1},a_{t+1}\rangle)\right)a_{t+1}$
(78)
$\displaystyle=\left(y_{t+1}-\mu(\langle\theta_{*},a_{t+1}\rangle)\right)a_{t+1}+\left(\mu(\langle\theta_{*},a_{t+1}\rangle)-\mu(\langle\hat{\theta}^{(a)}_{t+1},a_{t+1}\rangle)\right)a_{t+1}$
$\displaystyle=\eta_{t+1}a_{t+1}+\left(\mu(\langle\theta_{*},a_{t+1}\rangle)-\mu(\langle\hat{\theta}^{(a)}_{t+1},a_{t+1}\rangle)\right)a_{t+1},$

where for the last step, we used the observation model (11). Now based on
Lemma 11, we know that

$g_{t}(\hat{\theta}^{(a)}_{t+1})-g_{t}(\hat{\theta}^{(a)}_{t})=G_{t}\left(\hat{\theta}^{(a)}_{t+1}-\hat{\theta}^{(a)}_{t}\right),$

where $G_{t}$ is a symmetric positive definite matrix satisfying
$k_{1}V_{t}\preccurlyeq G_{t}\preccurlyeq k_{2}V_{t}$.999Here, we have
suppressed the dependence of $G_{t}$ on $\hat{\theta}^{(a)}_{t+1}$ and
$\hat{\theta}^{(a)}_{t}$ since this is apparent from context. We will continue
to do so to prevent cluttering the exposition. From the above equation and Eq.
(78), we then have

$\hat{\theta}^{(a)}_{t+1}-\hat{\theta}^{(a)}_{t}=G^{-1}_{t}\left(\eta_{t+1}a_{t+1}+\left(\mu(\langle\theta_{*},a_{t+1}\rangle)-\mu(\langle\hat{\theta}^{(a)}_{t+1},a_{t+1}\rangle)\right)a_{t+1}\right).$

Applying the triangle inequality to the above display, we obtain

${\|\hat{\theta}^{(a)}_{t+1}-\hat{\theta}^{(a)}_{t}\|}_{2}\leq\underbrace{{\|G^{-1}_{t}\eta_{t+1}a_{t+1}\|}_{2}}_{T_{1}}+\underbrace{\bigg{\lVert}G^{-1}_{t}\left(\mu(\langle\theta_{*},a_{t+1}\rangle)-\mu(\langle\hat{\theta}^{(a)}_{t+1},a_{t+1}\rangle)\right)a_{t+1}\bigg{\rVert}_{2}}_{T_{2}}.$

We now proceed to bound each of the terms $T_{1}$ and $T_{2}$ separately. For
bounding $T_{1}$, we note that as $G_{t}\succcurlyeq k_{1}V_{t}$, it holds
that $G^{-1}_{t}\preccurlyeq(1/k_{1})V^{-1}_{t}$. Since $G^{-1}_{t}$ is
symmetric and positive definite, we then have:

$\|{G^{-1}_{t}\|}_{2}=\lambda_{\max}(G^{-1}_{t})\leq\frac{1}{k_{1}}\lambda_{\max}(V^{-1}_{t})=\frac{1}{k_{1}\lambda_{\min}(V_{t})}\leq\frac{1}{k_{1}\lambda_{\min}(V_{\bar{T}})}.$
(79)

We can now bound $T_{1}$ as follows.

$\displaystyle T_{1}$
$\displaystyle\leq|\eta_{t+1}|{\|a_{t+1}\|}_{2}{\|G^{-1}_{t}\|}_{2}$ (80)
$\displaystyle\overset{(a)}{\leq}\frac{L\sqrt{4\log(T)}}{k_{1}\lambda_{\min}(V_{\bar{T}})}$
$\displaystyle\overset{(b)}{\leq}\frac{2\sqrt{\log(T)}}{5Lk_{2}\sqrt{T}\log(dLT)}$
$\displaystyle\leq\frac{2}{5Lk_{2}\sqrt{T\log(dLT)}}.$

In the above steps, we used the properties of event $\mathcal{F}$ and Eq. (79)
for (a), and Eq. (72) for (b). Bounding the term $T_{2}$ requires a bit more
work. Starting from the defining property of event $\mathcal{F}_{3}$, consider
the following set of implications:

$\displaystyle{\bigg{\lVert}g_{t+1}(\theta_{*})-\sum_{s=1}^{t+1}y_{s}a_{s}\bigg{\rVert}}^{2}_{V^{-1}_{t+1}}\leq\beta_{T}$
(81)
$\displaystyle\overset{(a)}{\implies}{\bigg{\lVert}g_{t+1}(\theta_{*})-g_{t+1}(\hat{\theta}^{(a)}_{t+1})\bigg{\rVert}}^{2}_{V^{-1}_{t+1}}\leq\beta_{T}$
$\displaystyle\overset{(b)}{\implies}{\bigg{\lVert}G_{t+1}\left(\theta_{*}-\hat{\theta}^{(a)}_{t+1}\right)\bigg{\rVert}}^{2}_{V^{-1}_{t+1}}\leq\beta_{T}$
$\displaystyle\implies\left(\theta_{*}-\hat{\theta}^{(a)}_{t+1}\right)^{\prime}G_{t+1}V^{-1}_{t+1}G_{t+1}\left(\theta_{*}-\hat{\theta}^{(a)}_{t+1}\right)\leq\beta_{T}$
$\displaystyle\overset{(c)}{\implies}k_{1}\left(\theta_{*}-\hat{\theta}^{(a)}_{t+1}\right)^{\prime}G_{t+1}\left(\theta_{*}-\hat{\theta}^{(a)}_{t+1}\right)\leq\beta_{T}$
$\displaystyle\overset{(d)}{\implies}{(k_{1})}^{2}\left(\theta_{*}-\hat{\theta}^{(a)}_{t+1}\right)^{\prime}V_{t+1}\left(\theta_{*}-\hat{\theta}^{(a)}_{t+1}\right)\leq\beta_{T}$
$\displaystyle\implies{(k_{1})}^{2}\lambda_{\min}(V_{t+1})\bigg{\lVert}\theta_{*}-\hat{\theta}^{(a)}_{t+1}\bigg{\rVert}^{2}_{2}\leq\beta_{T}.$
$\displaystyle\implies\|{\theta_{*}-\hat{\theta}^{(a)}_{t+1}\|}_{2}\leq\frac{1}{k_{1}}\sqrt{\frac{\beta_{T}}{\lambda_{\min}(V_{t+1})}}.$

In the above steps, (a) follows from the definition of
$\hat{\theta}^{(a)}_{t+1}$ in Eq. (14); (b) follows from invoking Lemma 11;
and (c), (d) both follow as a consequence of the fact that
$G_{t+1}\succcurlyeq k_{1}V_{t+1}$.

We can now bound $T_{2}$ as follows.

$\displaystyle T_{2}$
$\displaystyle=\bigg{\lVert}G^{-1}_{t}\left(\mu(\langle\theta_{*},a_{t+1}\rangle)-\mu(\langle\hat{\theta}^{(a)}_{t+1},a_{t+1}\rangle)\right)a_{t+1}\bigg{\rVert}_{2}$
(82)
$\displaystyle\leq\left|\mu(\langle\theta_{*},a_{t+1}\rangle)-\mu(\langle\hat{\theta}^{(a)}_{t+1},a_{t+1}\rangle)\right|{\|G^{-1}_{t}\|}_{2}{\|a_{t+1}\|}_{2}$
$\displaystyle\overset{(a)}{\leq}k_{2}\left|\langle\theta_{*}-\hat{\theta}^{(a)}_{t+1},a_{t+1}\rangle\right|{\|G^{-1}_{t}\|}_{2}{\|a_{t+1}\|}_{2}$
$\displaystyle\leq
k_{2}\bigg{\lVert}\theta_{*}-\hat{\theta}^{(a)}_{t+1}\bigg{\rVert}_{2}{\|G^{-1}_{t}\|}_{2}{\|a_{t+1}\|}^{2}_{2}$
$\displaystyle\overset{(b)}{\leq}\frac{k_{2}L^{2}}{{(k_{1})}^{2}}\frac{\sqrt{\beta_{T}}}{{\left(\lambda_{\min}(V_{\bar{T}})\right)}^{3/2}}$
$\displaystyle\overset{(c)}{\leq}\frac{k_{2}L^{2}}{{(k_{1})}^{2}}\frac{\sqrt{\beta_{T}}}{{\left(5(k_{2}/k_{1})L^{2}\sqrt{T}\log(dLT)\right)}^{3/2}}.$

In the above steps, (a) follows from the fact that $\mu(\cdot)$ is
$k_{2}$-Lipschitz; (b) follows from equations (79), (81), and the bound on the
actions; and (c) follows from Eq. (72). Combining the bounds on $T_{1}$ and
$T_{2}$ from equations (80) and (82) respectively, and simplifying, we
immediately obtain the claim of the lemma. This concludes the proof. ∎

Equipped with the above result, our next goal is to develop analogs of Lemma’s
1 and 10.

######  Lemma 14.

On the event $\mathcal{F}$, the following is true for the IC-GLMUCB algorithm:

$e_{t}\in\mathcal{B}_{d}(0,p_{t}),\forall t\in\\{\bar{T}+1,\ldots,T\\},$

where $e_{t}$ is the innovation in line 2 of Algorithm 3, and $p_{t}$ is as
defined in Eq. (68).

###### Proof.

The proof relies on the same induction technique employed in the analysis of
Lemma 1. We only establish the base case since the proof of the induction step
is identical to that in Lemma 1. To establish the base case, we need to argue
that $e_{\bar{T}+1}\in\mathcal{B}_{d}(0,p_{\bar{T}+1})$. Based on the
arguments used to arrive at (81), we obtain:

$\displaystyle\|{\theta_{*}-\hat{\theta}^{(a)}_{\bar{T}+1}\|}_{2}$
$\displaystyle\leq\frac{1}{k_{1}}\sqrt{\frac{\beta_{T}}{\lambda_{\min}(V_{\bar{T}})}}$
(83)
$\displaystyle\overset{(a)}{\leq}\frac{1}{\sqrt{k_{1}k_{2}}}\sqrt{\frac{\beta_{T}}{5L^{2}\sqrt{T}\log(dLT)}}$
$\displaystyle\overset{(b)}{\leq}\frac{3M}{\sqrt{k_{1}k_{2}}},$

where (a) follows from Eq. (72), and (b) follows from the reasoning used to
arrive at Eq. (49). This immediately implies that

$\bigg{\lVert}\hat{\theta}^{(a)}_{\bar{T}+1}\bigg{\rVert}_{2}\leq{\|\theta_{*}\|}_{2}+\frac{3M}{\sqrt{k_{1}k_{2}}}\leq\left(1+\frac{3}{\sqrt{k_{1}k_{2}}}\right)M.$

Finally, we have

$\displaystyle{\|e_{\bar{T}+1}\|}_{2}$
$\displaystyle=\|{\hat{\theta}^{(a)}_{\bar{T}+1}-\hat{\theta}^{(s)}_{\bar{T}}\|}_{2}$
(84)
$\displaystyle\leq\|{\hat{\theta}^{(a)}_{\bar{T}+1}\|}_{2}+\|{\hat{\theta}^{(s)}_{\bar{T}}\|}_{2}$
$\displaystyle\leq\left(1+\frac{3}{\sqrt{k_{1}k_{2}}}\right)M+M$
$\displaystyle\leq\left(2+\frac{3}{\sqrt{k_{1}k_{2}}}\right)M+\frac{3}{2}f(T)=p_{\bar{T}+1},$

where we used the fact that $\hat{\theta}^{(s)}_{\bar{T}}\in\Theta$, and
hence, $\|{\hat{\theta}^{(s)}_{\bar{T}}\|}_{2}\leq M$. This establishes the
desired claim and completes the proof. ∎

The next result justifies the decision making rule of the IC-GLMUCB algorithm.

######  Lemma 15.

On the event $\mathcal{F}$, the following is true:
$\theta_{*}\in\bar{\mathcal{C}}^{(s)}_{t},\forall
t\in\\{\bar{T}+2,\ldots,T\\}$, where

$\mathcal{\bar{C}}^{(s)}_{t}=\\{\theta\in\Theta:\mathcal{H}_{t-1}(\theta)\leq\sqrt{\beta_{T}}+k_{2}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\left(\sqrt{\lambda+(t-1)L^{2}}\right)q_{t}\\}};\hskip
2.84526pt\hskip
2.84526pt\mathcal{H}_{t}(\theta)\triangleq{\|g_{t}(\theta)-g_{t}(\hat{\theta}^{(s)}_{t})\|}_{V^{-1}_{t}}.$

Moreover, $\forall t\geq\bar{T}+\tilde{T}$, we have

$\left(\sqrt{\lambda+(t-1)L^{2}}\right)q_{t}\leq
4\sqrt{\frac{\beta_{T}}{k_{1}k_{2}\log(dLT)}},$ (85)

where

$\tilde{T}=\left\lceil\frac{\log\left(\frac{(2+3/\sqrt{k_{1}k_{2}})M}{\bar{f}(T)}\right)}{\log(2)}\right\rceil\vee
2=O\left(\log(dLT)\right).$ (86)

###### Proof.

Consider any time-step $t\geq\bar{T}+2$, and observe:

$\displaystyle\bigg{\lVert}g_{t-1}(\theta_{*})-g_{t-1}(\hat{\theta}^{(s)}_{t-1})\bigg{\rVert}_{V^{-1}_{t-1}}$
$\displaystyle\overset{(a)}{\leq}\bigg{\lVert}\
g_{t-1}(\theta_{*})-\sum_{s=1}^{t-1}y_{s}a_{s}\bigg{\rVert}_{V^{-1}_{t-1}}+\bigg{\lVert}\sum_{s=1}^{t-1}y_{s}a_{s}-g_{t-1}(\hat{\theta}^{(s)}_{t-1})\bigg{\rVert}_{V^{-1}_{t-1}}$
(87) $\displaystyle\overset{(b)}{=}\bigg{\lVert}\
g_{t-1}(\theta_{*})-\sum_{s=1}^{t-1}y_{s}a_{s}\bigg{\rVert}_{V^{-1}_{t-1}}+\bigg{\lVert}g_{t-1}(\hat{\theta}^{(a)}_{t-1})-g_{t-1}(\hat{\theta}^{(s)}_{t-1})\bigg{\rVert}_{V^{-1}_{t-1}}$
$\displaystyle\overset{(c)}{\leq}\sqrt{\beta_{T}}+\bigg{\lVert}g_{t-1}(\hat{\theta}^{(a)}_{t-1})-g_{t-1}(\hat{\theta}^{(s)}_{t-1})\bigg{\rVert}_{V^{-1}_{t-1}}$
$\displaystyle\overset{(d)}{=}\sqrt{\beta_{T}}+\bigg{\lVert}G_{t-1}\left(\hat{\theta}^{(a)}_{t-1}-\hat{\theta}^{(s)}_{t-1}\right)\bigg{\rVert}_{V^{-1}_{t-1}}$
$\displaystyle=\sqrt{\beta_{T}}+\sqrt{\left(\hat{\theta}^{(a)}_{t-1}-\hat{\theta}^{(s)}_{t-1}\right)^{\prime}G_{t-1}V^{-1}_{t-1}G_{t-1}\left(\hat{\theta}^{(a)}_{t-1}-\hat{\theta}^{(s)}_{t-1}\right)}$
$\displaystyle\overset{(e)}{\leq}\sqrt{\beta_{T}}+\sqrt{k_{2}\left(\hat{\theta}^{(a)}_{t-1}-\hat{\theta}^{(s)}_{t-1}\right)^{\prime}G_{t-1}\left(\hat{\theta}^{(a)}_{t-1}-\hat{\theta}^{(s)}_{t-1}\right)}$
$\displaystyle\overset{(f)}{\leq}\sqrt{\beta_{T}}+k_{2}\sqrt{\left(\hat{\theta}^{(a)}_{t-1}-\hat{\theta}^{(s)}_{t-1}\right)^{\prime}V_{t-1}\left(\hat{\theta}^{(a)}_{t-1}-\hat{\theta}^{(s)}_{t-1}\right)}$
$\displaystyle\leq\sqrt{\beta_{T}}+k_{2}\left(\sqrt{\lambda_{\max}(V_{t-1})}\right)\bigg{\lVert}\hat{\theta}^{(a)}_{t-1}-\hat{\theta}^{(s)}_{t-1}\bigg{\rVert}_{2}$
$\displaystyle\overset{(g)}{\leq}\sqrt{\beta_{T}}+k_{2}\left(\sqrt{\lambda+(t-1)L^{2}}\right)q_{t}.$

In the above steps, (a) follows from the triangle inequality; (b) follows from
the definition of $\hat{\theta}^{(a)}_{t-1}$ in Eq. (14); (c) follows from
Lemma 12; (d) follows from Lemma 11; (e) and (f) are both a result of the fact
that $G_{t-1}\preccurlyeq k_{2}V_{t-1}$; and (g) follows from the same line of
reasoning as used to arrive at Eq. (58). We have thus argued that
$\theta_{*}\in\bar{\mathcal{C}}^{(s)}_{t},\forall
t\in\\{\bar{T}+2,\ldots,T\\}$. The rest of the proof mimics that of Lemma 10,
and is hence omitted. ∎

We now turn to the proof of Theorem 2.

###### Proof.

(Proof of Theorem 2). As in the proof of Theorem 1, we will condition on the
clean event $\mathcal{F}$, and focus on bounding the instantaneous regret at a
time-step $t\geq\bar{T}+\tilde{T}+1$. To work towards this result, we define
$\tilde{\theta}_{t}$ as

$(a_{t},\tilde{\theta}_{t})=\operatorname*{\arg\\!\max}_{(a,\theta)\in\mathcal{A}_{t}\times\bar{\mathcal{C}}^{(s)}_{t}}\mu(\langle\theta,a\rangle),$

where $\bar{\mathcal{C}}^{(s)}_{t}$ is the confidence set of the IC-GLMUCB
algorithm as defined in Eq. (16). Now let
$a^{*}_{t}=\operatorname*{\arg\\!\max}_{a\in\mathcal{A}_{t}}\mu(\langle\theta_{*},a\rangle)$
be an optimal action at time-step $t$. To bound the instantaneous regret
$r_{t}=\mu(\langle\theta_{*},a^{*}_{t}\rangle)-\mu(\langle\theta_{*},a_{t}\rangle)$,
we first note based on Lemma 11 that

$\tilde{\theta}_{t}-\theta_{*}=G^{-1}_{t-1}\left(g_{t-1}(\tilde{\theta}_{t})-g_{t-1}(\theta_{*})\right).$

This yields

$\displaystyle\bigg{\lVert}\tilde{\theta}_{t}-\theta_{*}\bigg{\rVert}_{V_{t-1}}$
$\displaystyle=\bigg{\lVert}G^{-1}_{t-1}\left(g_{t-1}(\tilde{\theta}_{t})-g_{t-1}(\theta_{*})\right)\bigg{\rVert}_{V_{t-1}}$
(88)
$\displaystyle=\sqrt{\left(g_{t-1}(\tilde{\theta}_{t})-g_{t-1}(\theta_{*})\right)^{\prime}G^{-1}_{t-1}V_{t-1}G^{-1}_{t-1}\left(g_{t-1}(\tilde{\theta}_{t})-g_{t-1}(\theta_{*})\right)}$
$\displaystyle\overset{(a)}{\leq}\sqrt{\frac{1}{k_{1}}\left(g_{t-1}(\tilde{\theta}_{t})-g_{t-1}(\theta_{*})\right)^{\prime}G^{-1}_{t-1}\left(g_{t-1}(\tilde{\theta}_{t})-g_{t-1}(\theta_{*})\right)}$
$\displaystyle\overset{(b)}{\leq}\frac{1}{k_{1}}\sqrt{\left(g_{t-1}(\tilde{\theta}_{t})-g_{t-1}(\theta_{*})\right)^{\prime}V^{-1}_{t-1}\left(g_{t-1}(\tilde{\theta}_{t})-g_{t-1}(\theta_{*})\right)}$
$\displaystyle=\frac{1}{k_{1}}\bigg{\lVert}g_{t-1}(\tilde{\theta}_{t})-g_{t-1}(\theta_{*})\bigg{\rVert}_{V^{-1}_{t-1}}$
$\displaystyle\overset{(c)}{\leq}\frac{1}{k_{1}}\left(\bigg{\lVert}g_{t-1}(\tilde{\theta}_{t})-g_{t-1}(\hat{\theta}^{(s)}_{t-1})\bigg{\rVert}_{V^{-1}_{t-1}}+\bigg{\lVert}g_{t-1}(\hat{\theta}^{(s)}_{t-1})-g_{t-1}(\theta_{*})\bigg{\rVert}_{V^{-1}_{t-1}}\right)$
$\displaystyle=\frac{1}{k_{1}}\left(\mathcal{H}_{t-1}(\tilde{\theta}_{t})+\mathcal{H}_{t-1}(\theta_{*})\right)$
$\displaystyle\overset{(d)}{\leq}\frac{2}{k_{1}}\left(1+4\sqrt{\frac{k_{2}}{k_{1}}}\frac{1}{\sqrt{\log(dLT)}}\right)\sqrt{\beta_{T}}.$

In the above steps, (a) and (b) both follow from the fact that
$G_{t-1}\succcurlyeq k_{1}V_{t-1}$; (c) follows from the triangle inequality;
and (d) follows by noting that
$\theta_{*},\tilde{\theta}_{t}\in\bar{\mathcal{C}}^{(s)}_{t}$, and by
appealing to Lemma 86. We now proceed to bound the instantaneous regret
$r_{t}$ as follows.

$\displaystyle r_{t}$
$\displaystyle=\mu(\langle\theta_{*},a^{*}_{t}\rangle)-\mu(\langle\theta_{*},a_{t}\rangle)$
(89)
$\displaystyle\leq\mu(\langle\tilde{\theta}_{t},a_{t}\rangle)-\mu(\langle\theta_{*},a_{t}\rangle)$
$\displaystyle\overset{(a)}{\leq}k_{2}\langle\tilde{\theta}_{t}-\theta_{*},a_{t}\rangle$
$\displaystyle\leq
k_{2}{\|a_{t}\|}_{V^{-1}_{t-1}}\,{\|\theta_{*}-\tilde{\theta}_{t}\|}_{V_{t-1}}$
$\displaystyle\overset{(b)}{\leq}2\frac{k_{2}}{k_{1}}\left(1+4\sqrt{\frac{k_{2}}{k_{1}}}\sqrt{\frac{1}{\log(dLT)}}\right){\|a_{t}\|}_{V^{-1}_{t-1}}\sqrt{\beta_{T}}$
$\displaystyle\leq
10{\left(\frac{k_{2}}{k_{1}}\right)}^{3/2}{\|a_{t}\|}_{V^{-1}_{t-1}}{\sqrt{\beta_{T}}}.$

Here, (a) follows from the fact that $\mu(\cdot)$ is $k_{2}$-Lipschitz, and
(b) follows from plugging in the bound in Eq. (88). Combining the above bound
with the fact that $r_{t}$ is trivially bounded above by
$10{(k_{2}/k_{1})}^{3/2}\sqrt{\beta_{T}}$, we obtain

$r_{t}\leq
10{\left(\frac{k_{2}}{k_{1}}\right)}^{3/2}\sqrt{\beta_{T}}\left(1\wedge{\|a_{t}\|}_{V^{-1}_{t-1}}\right).$

Now following the exact same reasoning as in the proof of Theorem 1, we can
establish that on the clean event $\mathcal{F}$,

$\sum_{t=\bar{T}+\tilde{T}+1}^{T}r_{t}\leq
O\left({\left(\frac{k_{2}}{k_{1}}\right)}^{3/2}d\sqrt{T}\log(LT)\right).$

Moreover, since the instantaneous regret is trivially at most $1$, we have

$\sum_{t=1}^{\bar{T}+\tilde{T}}r_{t}\leq\bar{T}+\tilde{T}=O\left(\frac{k_{2}}{k_{1}}L^{2}d\sqrt{T}\log(dLT)\right)+O(\log(dLT))=O\left(\frac{k_{2}}{k_{1}}L^{2}d\sqrt{T}\log(dLT)\right).$

We conclude that on the event $\mathcal{F}$ that has measure at least
$1-\frac{5}{T}$, the following is true:

$\sum_{t=1}^{T}r_{t}=O\left({\left(\frac{k_{2}}{k_{1}}\right)}^{3/2}L^{2}d\sqrt{T}\log(dLT)\right).$

The rest of the proof can be completed exactly as in Theorem 1. ∎

##  Appendix D Proof of Theorem 3

In this section, we will prove Theorem 3. To get started, we introduce some
notation. For each arm $i$, let us define the following observation at each
$k\in[T]$:

$y_{i,k}=\langle\theta_{*},e_{i}\rangle+\eta_{i,k}=\theta_{i}+\eta_{i,k},$

where $\\{\eta_{i,k}\\}_{k\in[T]}$ is a sequence of independent 1-subgaussian
random variables drawn ahead of time. In words, $\eta_{i,k}$ is the noise
random variable corresponding to the $k$-th play of arm $i$. We note here that
arm $i$ may not actually be played $k$ times; nonetheless, the above model
offers a simple way to analyze the true dynamics. Next, we define

$\hat{\theta}^{(a)}_{i,k}=\frac{1}{k}\sum_{s=1}^{k}y_{i,s}$

to be the empirical mean of $\theta_{i}$ (maintained by the agent) based on
the first $k$ observations. We start with the following simple lemma that sets
up a clean event for our subsequent analysis.

######  Lemma 16.

Consider the following event:

$\mathcal{G}_{i}=\\{|\hat{\theta}^{(a)}_{i,k}-\theta_{i}|\leq f_{k},\forall
k\in[T]\\},\hskip 5.69054pt\textrm{where}\hskip
5.69054ptf_{k}=2\sqrt{\frac{\log T}{k}}.$

Then, $\mathbb{P}(\mathcal{G}_{i})\geq 1-\frac{2}{T}$.

###### Proof.

The proof is standard, and we only provide it here for completeness. Start by
noting that

$\hat{\theta}^{(a)}_{i,k}=\frac{1}{k}\sum_{s=1}^{k}y_{i,s}=\frac{1}{k}\sum_{s=1}^{k}\left(\theta_{i}+\eta_{i,s}\right)=\theta_{i}+\frac{1}{k}\sum_{s=1}^{k}\eta_{i,s}.$

An application of the union bound yields:

$\displaystyle\mathbb{P}(\mathcal{G}^{c}_{i})$
$\displaystyle=\mathbb{P}\left(\exists
k\in[T]:|\hat{\theta}^{(a)}_{i,k}-\theta_{i}|>f_{k}\right)$ (90)
$\displaystyle\leq\sum_{k\in[T]}\mathbb{P}\left(|\hat{\theta}^{(a)}_{i,k}-\theta_{i}|>f_{k}\right)$
$\displaystyle=\sum_{k\in[T]}\mathbb{P}\left(\left|\frac{1}{k}\sum_{s=1}^{k}\eta_{i,s}\right|>f_{k}\right)$
$\displaystyle\leq\sum_{k\in[T]}\frac{2}{T^{2}}=\frac{2}{T}.$

For the last step, we used the fact that $(1/k)\sum_{s=1}^{k}\eta_{i,s}$ is a
$(1/\sqrt{k})$-subgaussian random variable, and then appealed to [25, Theorem
5.3]. ∎

The next result tells us that with high probability, there is never any
overflow during encoding.

######  Lemma 17.

Fix an action $i\in[d]$. On the event $\mathcal{G}_{i}$, it holds that
$e_{i,n_{i}(t)}\in[-p_{n_{i}(t)},p_{n_{i}(t)}],\forall
t\in\\{d+1,\ldots,T\\}$.

###### Proof.

With $t\in[T]$, since $n_{i}(t)\in[T]$, it suffices to show that on the event
$\mathcal{G}_{i}$, it holds that

$e_{i,k}\in[-p_{k},p_{k}],\forall k\in[T],$

where $p_{k}$ is as given by Eq. (19). The result follows from a simple
inductive argument akin to that employed in the proof of Lemma 1. For the base
case with $k=1$, we have that

$e_{i,1}=\hat{\theta}^{(a)}_{i,1}-\hat{\theta}^{(s)}_{i,0}=\hat{\theta}^{(a)}_{i,1},$

where we used the fact that $\hat{\theta}^{(s)}_{i,0}=0$. We thus have:

$|e_{i,1}|\leq|\hat{\theta}^{(a)}_{i,1}-\theta_{i}|+|\theta_{i}|\leq
f_{1}+m=p_{1},$

where we used the property of event $\mathcal{G}_{i}$, and the fact that
$\max_{i\in[d]}|\theta_{i}|\leq m$. Now suppose $e_{i,k}\in[-p_{k},p_{k}]$
holds for all $k\in[\ell]$, where $\ell\in[T-1]$. For the induction step, our
goal is to then show that $e_{i,\ell+1}\in[-p_{\ell+1},p_{\ell+1}]$. To this
end, we start by noting that

$\displaystyle\left|\hat{\theta}^{(a)}_{i,\ell+1}-\hat{\theta}^{(a)}_{i,\ell}\right|$
$\displaystyle\leq\left|\hat{\theta}^{(a)}_{i,\ell+1}-\theta_{i}\right|+\left|\theta_{i}-\hat{\theta}^{(a)}_{i,\ell}\right|$
(91) $\displaystyle\leq f_{\ell+1}+f_{\ell}$ $\displaystyle\leq 2f_{\ell},$

where for the second inequality, we invoked the property of event
$\mathcal{G}_{i}$. Based on the induction hypothesis,
$e_{i,\ell}\in[-p_{\ell},p_{\ell}]$, i.e., there is no overflow. The encoding-
decoding strategy of IC-UCB then yields

$\left|\hat{\theta}^{(a)}_{i,\ell}-\hat{\theta}^{(s)}_{i,\ell}\right|=|\tilde{e}_{i,\ell}-e_{i,\ell}|\leq\frac{1}{2^{B}}p_{\ell}=\gamma
p_{\ell}.$

Combining the above inequality with that in Eq. (91), we obtain:

$\displaystyle|e_{i,\ell+1}|$
$\displaystyle=\left|\hat{\theta}^{(a)}_{i,\ell+1}-\hat{\theta}^{(s)}_{i,\ell}\right|$
(92)
$\displaystyle\leq\left|\hat{\theta}^{(a)}_{i,\ell+1}-\hat{\theta}^{(a)}_{i,\ell}\right|+\left|\hat{\theta}^{(a)}_{i,\ell}-\hat{\theta}^{(s)}_{i,\ell}\right|$
$\displaystyle\leq 2f_{\ell}+\gamma p_{\ell}$ $\displaystyle=p_{\ell+1}.$

This completes the induction step and the proof. ∎

To proceed, we will require the following intermediate result concerning the
sequence $\\{q_{k}\\}$ generated as per Eq. (19).

######  Lemma 18.

Consider the sequence $\\{q_{k}\\}$ generated as per Eq. (19). For all $k\geq
1$, we have

$q_{k}\leq\gamma^{k}(m+f_{1})+\frac{12}{B}\sqrt{\frac{\log T}{k}}.$ (93)

###### Proof.

Rolling out the recursion $p_{k+1}=\gamma p_{k}+2f_{k}$ yields:

$p_{k}=\gamma^{k-1}p_{1}+2\sum_{s=1}^{k-1}\gamma^{k-1-s}f_{s}.$

With $p_{1}=(m+f_{1})$ and $q_{k}=\gamma p_{k}$, we then have

$q_{k}=\gamma^{k}(m+f_{1})+2\sum_{s=1}^{k-1}\gamma^{k-s}f_{s}=\gamma^{k}(m+f_{1})+4\sqrt{\log
T}\left(\sum_{s=1}^{k-1}\frac{\gamma^{k-s}}{\sqrt{s}}\right).$ (94)

Let $a=1/\gamma$. In what follows, we will bound the following summation

$\sum_{s=1}^{k-1}\frac{a^{s}}{\sqrt{s}}\leq\underbrace{\int_{s=1}^{k}\frac{a^{s}}{\sqrt{s}}\,ds}_{g_{k}},$

where we used the fact that $a^{s}/\sqrt{s}$ is monotonically increasing since
$a=2^{B}\geq 2$. To bound the integral $g_{k}$, we employ a change of
variable: $u=\sqrt{s}$. This yields:

$g_{k}=2\int_{u=1}^{\sqrt{k}}a^{u^{2}}\,du=2\int_{u=1}^{\sqrt{k}}e^{u^{2}\log
a}\,du,$

where we have used $e$ to represent $\exp(1)$. Now let us employ another
change of variable: $z=u\sqrt{\log a}$. We then obtain

$\displaystyle g_{k}$ $\displaystyle=\frac{2}{\sqrt{\log a}}\int_{\sqrt{\log
a}}^{\sqrt{k\log a}}e^{z^{2}}\,dz$ (95) $\displaystyle\leq\frac{2}{\sqrt{\log
a}}\int_{0}^{\sqrt{k\log a}}e^{z^{2}}\,dz$ $\displaystyle=\frac{2}{\sqrt{\log
a}}\int_{0}^{\sqrt{k\log
a}}\left(\sum_{j=0}^{\infty}\frac{z^{2j}}{j!}\right)\,dz$
$\displaystyle=\frac{2}{\sqrt{\log
a}}\sum_{j=0}^{\infty}\left(\int_{0}^{\sqrt{k\log
a}}\frac{z^{2j}}{j!}\,dz\right)$ $\displaystyle=\frac{2}{\sqrt{\log
a}}\sum_{j=0}^{\infty}\frac{{(\sqrt{k\log a})}^{2j+1}}{(2j+1)j!}$
$\displaystyle\leq\frac{2}{\sqrt{k}\log a}\sum_{j=0}^{\infty}\frac{{({k\log
a})}^{j+1}}{(j+1)!}$ $\displaystyle\leq\frac{2e^{k\log a}}{\sqrt{k}\log a}$
$\displaystyle=\frac{2a^{k}}{B\log(2)\sqrt{k}}$
$\displaystyle\leq\frac{3a^{k}}{B\sqrt{k}},$

where the interchange of the integral and the summation in the fourth step is
warranted by the Fubini-Tonelli theorem. Plugging the above bound in Eq. (94)
and simplifying leads to the claim in Eq. (93). ∎

We are now ready to prove Theorem 3.

###### Proof.

(Proof of Theorem 3) We start by defining a few quantities that will be used
in our analysis. Define

$T_{1}=\left\lceil\frac{1}{B}\frac{\log\left(\frac{(m+2\sqrt{\log
T})\sqrt{T}}{\sqrt{\log T}}\right)}{\log(2)}\right\rceil;\hskip
5.69054ptT_{2}=\left\lceil\frac{C}{\Delta^{2}_{i}}\log mT\right\rceil,$

where $C=3600.$ It is easy to verify that for $T_{1}\leq t\leq T$,

$\gamma^{t}(m+f_{1})={\left(\frac{1}{2^{B}}\right)}^{t}(m+2\sqrt{\log
T})\leq\sqrt{\frac{\log T}{T}}\leq\sqrt{\frac{\log T}{t}}.$

Moreover, for $t\geq T_{2}$, we have

$30\sqrt{\frac{\log T}{t}}\leq\frac{\Delta_{i}}{2}.$

Fix any arm $i$ other than arm $1$ and define
$\tilde{T}=\max\\{T_{1},T_{2}\\}$.101010We have suppressed the dependence of
$T_{2}$ and $\tilde{T}$ on $i$ to avoid cluttering the exposition. Next,
define the event $\mathcal{H}_{1i}=\mathcal{G}_{1}\cap\mathcal{G}_{i}$, where
recall that

$\mathcal{G}_{i}=\\{|\hat{\theta}^{(a)}_{i,k}-\theta_{i}|\leq f_{k},\forall
k\in[T]\\}.$

We claim that on the event $\mathcal{H}_{1i}$, action $i$ will be played at
most $\tilde{T}$ times, i.e., $n_{i}(T)\leq\tilde{T}$. To establish this
claim, we proceed via contradiction. Accordingly, suppose that on the event
$\mathcal{H}_{1i}$, $n_{i}(T)>\tilde{T}$. Thus, there must exist a time-step
$t\in[T]$ such that $n_{i}(t-1)=\tilde{T}$, and $a_{t}=e_{i}$. At this time-
step, we have

$\displaystyle\texttt{IC-UCB}_{i}(t-1)$
$\displaystyle=\hat{\theta}^{(s)}_{i,n_{i}(t-1)}+q_{n_{i}(t-1)}+f_{n_{i}(t-1)}$
(96)
$\displaystyle=\hat{\theta}^{(s)}_{i,\tilde{T}}+q_{\tilde{T}}+f_{\tilde{T}}$
$\displaystyle\overset{(a)}{\leq}\hat{\theta}^{(a)}_{i,\tilde{T}}+2q_{\tilde{T}}+f_{\tilde{T}}$
$\displaystyle\overset{(b)}{\leq}\theta_{i}+2\left(q_{\tilde{T}}+f_{\tilde{T}}\right)$
$\displaystyle\overset{(c)}{\leq}\theta_{i}+30\sqrt{\frac{\log T}{\tilde{T}}}$
$\displaystyle\overset{(d)}{\leq}\theta_{i}+\frac{\Delta_{i}}{2}$
$\displaystyle<\theta_{1}$ $\displaystyle\overset{(e)}{\leq}\texttt{IC-
UCB}_{1}(t-1).$

We have thus arrived at a contradiction as
$a_{t}=e_{i}\neq\operatorname*{\arg\\!\max}_{j\in[d]}\texttt{IC-
UCB}_{j}(t-1)$. To complete the proof of the claim, we need to justify each of
the above steps. For (a), we invoked Lemma 17 to conclude that

$\left|\hat{\theta}^{(a)}_{i,\tilde{T}}-\hat{\theta}^{(s)}_{i,\tilde{T}}\right|=|\tilde{e}_{i,\tilde{T}}-e_{i,\tilde{T}}|\leq\gamma
p_{\tilde{T}}=q_{\tilde{T}}.$

For (b), we used the defining property of event $\mathcal{G}_{i}$. For (c), we
appealed to Lemma 18, and used the facts that $\tilde{T}\geq T_{1}$ and $B\geq
1$ to conclude that

$q_{\tilde{T}}\leq\gamma^{\tilde{T}}(m+f_{1})+\frac{12}{B}\sqrt{\frac{\log
T}{\tilde{T}}}\leq 13\sqrt{\frac{\log T}{\tilde{T}}}.$

It remains to argue that on the event $\mathcal{H}_{1i}$ (that contains the
event $\mathcal{G}_{1}$),

$\theta_{1}\leq\texttt{IC-UCB}_{1}(t-1).$

We claim that the above inequality holds for all $t\in[T]$. Suppose by
contradiction that there exist some $t,k\in[T]$ such that $n_{i}(t-1)=k$, and

$\theta_{1}>\hat{\theta}^{(s)}_{i,k}+q_{k}+f_{k}.$

Based on the property of event $\mathcal{G}_{1}$, this would imply that

$\hat{\theta}^{(a)}_{i,k}+f_{k}>\hat{\theta}^{(s)}_{i,k}+q_{k}+f_{k}\implies\hat{\theta}^{(a)}_{i,k}-\hat{\theta}^{(s)}_{i,k}>q_{k},$

which is a contradiction since based on Lemma 17,

$\left|\hat{\theta}^{(a)}_{i,k}-\hat{\theta}^{(s)}_{i,k}\right|\leq q_{k}.$

We have thus established the claim that on the event $\mathcal{H}_{1i}$,
$n_{i}(T)\leq\tilde{T}$. From Lemma 16, we also note that

$\mathbb{P}(\mathcal{H}_{1i})\geq 1-\frac{4}{T}.$

This immediately leads to the following bound:

$\displaystyle\mathbb{E}[n_{i}(T)]$
$\displaystyle=\mathbb{E}[\mathcal{I}_{\mathcal{H}_{1i}}n_{i}(T)]+\mathbb{E}[\mathcal{I}_{\mathcal{H}^{c}_{1i}}n_{i}(T)]$
(97) $\displaystyle\leq\tilde{T}+T\mathbb{P}(\mathcal{H}^{c}_{1i})$
$\displaystyle\leq\tilde{T}+4.$

Using the facts that $m\geq 1$, $B\geq 1$, and $\Delta_{i}\leq 1$, one can
verify that $T_{1}\leq T_{2}$. Hence,

$\mathbb{E}[n_{i}(T)]\leq\frac{C}{\Delta^{2}_{i}}\log(mT)+5.$

This immediately yields the desired regret bound:

$R_{T}=\sum_{i=1}^{d}\Delta_{i}\mathbb{E}[n_{i}(T)]\leq
5\sum_{i=1}^{d}\Delta_{i}+\sum_{i=1}^{d}\frac{C}{\Delta_{i}}\log(mT).$

∎

We now comment on the proof of Theorem 4.

###### Proof.

(Proof of Theorem 4) Starting from the bound

$\mathbb{E}[n_{i}(T)]\leq\frac{C}{\Delta^{2}_{i}}\log(mT)+5$

that we derived in the analysis of Theorem 3, the rest of the proof of Theorem
4 follows exactly the same reasoning as [25, Theorem 7.2]. Hence, we omit the
details. ∎