# Kernel $\epsilon$-Greedy for Contextual Bandits

Sakshi Arya and Bharath K. Sriperumbudur  Department of Statistics,
Pennsylvania State University
University Park, PA 16802, USA.
arya.sakshi44<EMAIL_ADDRESS>
###### Abstract

We consider a kernelized version of the $\epsilon$-greedy strategy for
contextual bandits. More precisely, in a setting with finitely many arms, we
consider that the mean reward functions lie in a reproducing kernel Hilbert
space (RKHS). We propose an online weighted kernel ridge regression estimator
for the reward functions. Under some conditions on the exploration probability
sequence, $\\{\epsilon_{t}\\}_{t}$, and choice of the regularization
parameter, $\\{\lambda_{t}\\}_{t}$, we show that the proposed estimator is
consistent. We also show that for any choice of kernel and the corresponding
RKHS, we achieve a sub-linear regret rate depending on the intrinsic
dimensionality of the RKHS. Furthermore, we achieve the optimal regret rate of
$\sqrt{T}$ under a margin condition for finite-dimensional RKHS.

MSC 2010 subject classification: Primary: 62L10; Secondary: 62G05, 68T05.
Keywords and phrases: Contextual bandits, reproducing kernel Hilbert space,
covariance operator, $\epsilon$-greedy, cumulative regret, inverse probability
weighting, kernel ridge regression

##  1 Introduction

Sequential decision-making in real time is increasingly becoming important in
various applications, such as clinical trials (Bather,, 1985; Villar et al.,,
2015), news article recommendation (Li et al.,, 2010) and mobile health
(Nahum-Shani et al.,, 2017). In all such problems, the decision-maker is faced
with several alternatives, from which they have to make a series of choices
(referred to as _arms_) sequentially, based on the information available at
any given time. In doing so, the decision-maker takes into account additional
information or covariates (characteristics) which help in making informed
decisions. This framework is popularly known as the contextual bandit problem
(Langford and Zhang,, 2007). In a treatment allocation problem, this can be
described as follows: given finitely many competing treatments for a disease,
the decision-maker (physician) chooses the treatment best suited for
individual patients as they arrive, and each allocated treatment results in a
reward (outcome). While doing so, the decision-maker takes into account the
patient’s covariates and information available about previous patients with
the same disease, with the eventual goal of maximizing the total reward
accumulated over a period of time. The technical challenge in achieving this
is two-fold: 1) learning the relationship between the covariates and optimal
arms, and, 2) balancing the exploration-exploitation trade-off, which arises
due to the sequential (or online) nature of the problem. In other words, in a
sequential setup, at each time point the physician has to effectively identify
the best treatment (exploration) and treat patients as effectively as possible
during the trial (exploitation). Since there has been a substantial number of
advancements in the contextual bandit problem in recent years, we refer the
reader to Lattimore and Szepesvári, (2020) for a detailed description of
recent developments in this area and Tewari and Murphy, (2017) for a
comprehensive survey of both parametric and nonparametric methods in
contextual bandits.

In this paper, we consider a kernelized contextual bandit framework, where the
relationship between the rewards and covariates for each arm is modeled by
functions in a reproducing kernel Hilbert space (RKHS), and study a popular
heuristic in multi-armed bandit problems known as the annealed
$\epsilon$-greedy strategy (Sutton and Barto,, 2018). This strategy allocates
arms based on a randomized strategy to balance the exploration-exploitation
trade-off, with a careful reduction in exploration over time. For example, in
a two-armed bandit, the $\epsilon$-greedy strategy chooses the current best-
performing arm with probability $1-\epsilon$ and makes a random decision with
a small probability $\epsilon$. In the annealed version of the algorithm,
$\epsilon$ is a non-increasing function of time. This algorithm falls in the
broad category of ‘algorithms with myopic exploration’, which are easy to
implement and could result in good empirical performance in some situations
with appropriate exploration probability choices (Bietti et al.,, 2021; Mnih
et al.,, 2015). In practice, they are often selected as the top choices due to
their simplicity. However, they have not been studied extensively in the
literature. Recently, Dann et al., (2022) studied the $\epsilon$-greedy
strategy in the more general reinforcement learning setup and provided
theoretical guarantees in terms of what they define as the myopic exploration
gap, which is a problem-dependent quantity. Using $\epsilon$-greedy strategy,
they achieve the optimal regret rate of $\tilde{O}(T^{2/3})$ for contextual
bandits, which matches the rate we obtain for our algorithm when the RKHS is
finite-dimensional. We also show that we can get the same rate for an
infinite-dimensional RKHS under the margin condition. Chen et al., (2021)
study the $\epsilon$-greedy strategy for the linear bandit problem (parametric
contextual bandit with a linear regression framework) and establish the regret
rate of $\tilde{O}(\sqrt{T})$, which our work recovers when the RKHS is
finite-dimensional and under the margin condition.

###  1.1 Contributions

The main contribution of this work is in developing a theoretical
understanding of kernelized $\epsilon$-greedy algorithm. More specifically:

  * •

We propose an inverse probability weighted kernel ridge (IPWKR) regression
type of online estimator for the mean reward functions in Section 3.2, whose
implementation details are provided in Section 3.3. Such estimators have been
studied in the context of linear bandits for mitigating the problem of
estimation bias in adaptively collected data (Dimakopoulou et al.,, 2019).
Using IPWKR estimator, we propose a kernel $\epsilon$-greedy algorithm for
contextual bandits and provide regret bounds. We highlight here that the
inverse probability weights appearing in IPWKR are deterministic known
quantities that involve user-determined exploration probabilities.

  * •

In Section 4, we establish upper bounds on the estimation error (see Theorem
1) for the proposed IPWKR estimator, which we specialize to the setting of
finite-dimensional RKHS in Theorem 2. These results hold for specific
conditions on the exploration probability sequence $\\{\epsilon_{t}\\}_{t}$
and choices of the regularization parameter sequence $\\{\lambda_{t}\\}_{t}$.
As a comparison, in the linear bandit framework, Chen et al., (2021) propose
an online weighted least squares (WLS) estimator similar to our proposed IPWKR
estimator but without regularization. In fact, when the kernel is linear, our
proposed estimator can be seen as a dualized representation of their online
WLS estimator if $\lambda=0$. In Section 4 (Theorem 2 and Remark 1), we show
that our consistency result is stronger than (Chen et al.,, 2021, Proposition
4.1) in the sense that we achieve consistency in estimation for large ranges
of the exploration probabilities, $\\{\epsilon_{t}\\}_{t}$, i.e., for decaying
choices of $\\{\epsilon_{t}\\}_{t}$ faster than those considered in Chen et
al., (2021). Interestingly, for these choices of $\\{\epsilon_{t}\\}_{t}$, we
obtain the same convergence rate as in Chen et al., (2021)—obtained for linear
contextual bandits—even when the true regression functions are non-linear, as
long as the RKHS is finite-dimensional. Also, we highlight that, compared to
the existing literature (Valko et al.,, 2013; Zenati et al.,, 2022), in a
finite-dimensional setting, our analysis provides an explicit data-dependent
choice for regularization parameter, $\\{\lambda_{t}\\}_{t}$, circumventing
the need to tune it when implementing the algorithm.

  * •

In Theorem 3 of Section 5, we establish finite-time regret bounds for kernel
$\epsilon$-greedy strategy for contextual bandits with finitely many arms when
the mean reward functions are assumed to be in an RKHS. These regret bounds
are sub-linear for all choices of bounded, positive definite, and symmetric
kernels. Compared to the results in the literature, this is a significant
result since the Matérn kernel may have a linear regret for some choices of
the kernel parameters (Vakili et al., 2021b, ; Scarlett et al.,, 2017). In
fact, our finite-time regret bound matches the state-of-the-art upper bound
for $\epsilon$-greedy strategy when the RKHS is finite-dimensional (Theorem
4), both with and without the _margin condition_ —the margin conditions
ensures that there is sufficient gap between the rewards for different arms—,
which are $\tilde{O}(T^{1/2})$ and $\tilde{O}(T^{2/3})$, respectively. When
the RKHS is infinite-dimensional, the bounds are controlled by the intrinsic
dimensionality of the RKHS—in turn, controlled by the decay rate of the
eigenvalues of the covariance operator—and a source condition, which captures
the smoothness of the target.

  * •

In contrast to the literature, the above results are obtained by only assuming
the noise variance to be finite, instead of the commonly assumed sub-Gaussian
structure on the noise in (1). Moreover, our analysis does not require any
martingale concentration results as in Chen et al., (2021) but uses
Chebyshev’s inequality, however at the cost of losing exponential
concentration for polynomial concentration.

###  1.2 Related research

Contextual bandits in a parametric framework, especially linear bandits have
been extensively studied in the bandit literature (Lattimore and Szepesvári,,
2020). In a linear bandit framework, every arm corresponds to a known, finite-
dimensional context, and its expected reward is assumed to be an unknown
linear function of its context. Upper Confidence Bound (UCB) and Thompson
sampling strategies are the most commonly used bandit algorithms. While the
UCB uses the optimism in the face of uncertainty idea where the exploration-
exploitation trade-off is balanced by creating confidence sets on the unknown
reward functions, Thompson sampling is a randomized algorithm and a popular
heuristic based on Bayesian ideas. Both these types of algorithms are
extremely popular, well-studied, and enjoy tight regret guarantees (Dani et
al.,, 2008; Li et al.,, 2010; Abbasi-Yadkori et al.,, 2011; Agarwal et al.,,
2012). On the other hand, there are relatively fewer works on
$\epsilon$-greedy strategy except for the epoch-greedy version of Langford and
Zhang, (2007) and the mostly exploration-free algorithms based on Bastani et
al., (2021), which have gained a lot of popularity recently. In a
nonparametric framework, $\epsilon$-greedy strategies and modifications of the
same have been studied by Yang and Zhu, (2002); Qian and Yang, (2016); Arya
and Yang, (2020); Qian et al., (2023).

In the contextual bandit framework, there are also two types of setups that
are considered in the literature: (a) continuous action space linear bandits:
action (arm) space is the same as the context (covariate) space (Abbasi-
Yadkori et al.,, 2011; Dani et al.,, 2008; Rusmevichientong and Tsitsiklis,,
2010) and (b) finite action space linear bandits: finite action (arm) set
which is different from the context space (Li et al.,, 2010; Chen et al.,,
2021). Under these two steps, infinite-dimensional extensions of contexts
and/or arms have been considered in both the frequentist and Bayesian
perspectives. In the frequentist perspective, Valko et al., (2013) propose a
KernelUCB algorithm for finite action space, which is obtained by kernelizing
the LinUCB and SupLinUCB algorithm of Li et al., (2010); Chu et al., (2011),
and Auer et al., (2002). They give a bound on the regret in terms of a data-
dependent quantity, the effective dimension, $\tilde{d}$. In the Bayesian
perspective, Srinivas et al., (2010) propose the Gaussian Process (GP)-UCB for
the context-free stochastic bandit problem, which assumes that the reward
function is drawn from a GP prior. Krause and Ong, (2011) generalize the GP-
UCB algorithm by taking context information into account in the decision-
making process. Gopalan et al., (2014) study the stochastic multi-armed bandit
problem with continuous action space and propose an improved version of GP-
UCB, which they call IGP-UCB. In this work, they also propose a nonparametric
version of Thompson sampling, GP-Thompson sampling. The regret bounds in all
of the Gaussian process bandits line of work are in terms of the quantity,
$\gamma_{t}$, which is the maximum information gain at time $t$ and depends on
the choice of kernels that define the underlying RKHS containing the reward
functions. Moreover, Valko et al., (2013) show $\tilde{d}$ to be closely
related to $\gamma_{t}$. Zhou et al., (2020) propose a neural-net-based
algorithm, called NeuralUCB, which uses a neural network-based random feature
mapping to construct an upper confidence bound (UCB). More recently, Zenati et
al., (2022) propose an efficient contextual UCB type algorithm for
computational efficiency. This algorithm relies on incremental Nyström
approximations of the joint kernel embedding of contexts and actions.
Furthermore, Janz et al., (2020) and Vakili et al., 2021a  provide improved
regret bounds for GP bandits with Mátern kernels. Scarlett et al., (2017) and
Cai and Scarlett, (2021) provide lower bounds for the Gaussian Process bandit
optimization problem with squared exponential and Mátern kernel for the
contextual bandit problem with continuous action space. Another approach for
kernelized contextual bandits is related to experimental design and also aims
at optimal pure exploration in kernel bandits as has been studied by Camilleri
et al., (2021) and Zhu et al., (2021). A partial list of some of the other
unrelated work in nonparametric contextual bandit problem includes Yang and
Zhu, (2002); Rigollet and Zeevi, (2010); Magureanu et al., (2014); Hu et al.,
(2022); Kleinberg et al., (2008); Slivkins, (2014); Zhou et al., (2020).

While UCB and Thompson sampling algorithms for kernel contextual bandits have
received considerable attention in the recent past, to the best of our
knowledge, the kernelized version of the $\epsilon$-greedy algorithm has not
been studied previously. Our setup is similar to the agnostic setup of Valko
et al., (2013) for a contextual bandit framework with finitely many arms,
where we propose a kernelized version of the $\epsilon$-greedy algorithm,
which can be seen as a nonparametric extension to the linear $\epsilon$-greedy
algorithm studied by Chen et al., (2021). Our main contribution is a
theoretical analysis of this kernelized $\epsilon$-greedy approach validated
by some numerical results. The regret bounds we achieve are different from the
previous line of work, as our results do not depend on the data-dependent
quantities such as $\tilde{d}$ in Valko et al., (2013) or maximum information
gain $\gamma_{t}$ as in the GP-bandits line of work. One can quantify this
information gain for a specific kernel choice and find the corresponding
regret rate, see Scarlett et al., (2017). Therefore, for some choices of
kernel parameters for the Mátern kernel, it has been observed that one could
obtain a linear cumulative regret. On the other hand, our results depend on
the intrinsic dimensionality of the RKHS stemming from the assumption on the
rate of the eigenvalue decay for the covariance operator and the source
condition for the space in which the true mean reward functions are assumed to
belong. As a result, we always obtain a sub-linear regret rate irrespective of
the kernel choice. Note that, the $\epsilon$-greedy algorithm that we propose
uses an inverse probability-weighted online kernel ridge regression estimator.
The inverse probability weighting is reminiscent of the inverse propensity
score weighted algorithms considered in parametric frameworks to handle model
misspecifications. These are known as balanced bandit algorithms (Dimakopoulou
et al.,, 2019) where each observation is divided by its propensity score to
correct for estimation bias. Dimakopoulou et al., (2019) propose the balanced
linear UCB and balanced Thompson sampling algorithms, establish their
corresponding regret rates, and assess empirical performances under model
misspecifications. Bogunovic and Krause, (2021) study misspecified Gaussian
Process bandit optimization, but for continuous action space and they
establish regret bounds in terms of the amount of model misspecification. Chen
et al., (2021) consider an ‘balanced’ (weighted) linear $\epsilon$-greedy
strategy for handling model-misspecification with weighted least squares
estimator. Our work can be thought of as an extension to their work offering
flexible and nonparametric modeling for the relationship between the rewards
and covariates, where we study a kernelized version of the weighted linear
$\epsilon$-greedy algorithm.

###  1.3 Organization

The rest of the paper is organized as follows. In Section 2.1, we define the
notations used in the rest of the paper. In Section 2.2, we introduce the
setting of contextual bandits and the online regression framework along with
the definition of regret that is used to assess the performance of the
proposed algorithm. In Section 3, we present the kernel $\epsilon$-greedy
strategy and the online kernel ridge-regression estimator studied in the
following sections. In Section 3.3, we provide an implementable version of the
regression estimator that is then employed in the proposed algorithm for
empirical evaluation on synthetic data sets in Section 6. We provide
convergence rates for the estimation error in Section 4 for both the infinite-
dimensional and finite-dimensional RKHS settings. In Section 5, we present the
regret rates for both the infinite-dimensional and finite-dimensional RKHSs.
Under an additional assumption of the margin condition, improved regret bounds
are presented for the kernel $\epsilon$-greedy algorithm in Section 5.1.
Finally, all the proofs are provided in Section 8.

##  2 Background and problem setup

In this section, we introduce the notations followed by the problem setup of
the sequential decision-making framework of contextual bandits.

###  2.1 Notations

For a Hilbert Space $\mathcal{H}$, $\langle f,g\rangle_{\mathcal{H}}$ denotes
the inner product of $f,g\in\mathcal{H}$. We denote $\|\cdot\|$ or
$\|\cdot\|_{\mathcal{H}}$ to denote the corresponding norm in $\mathcal{H}$.
For $h\in\mathcal{H}$, we use $\|h\|_{\mathcal{H}}=\sqrt{\langle
h,h\rangle_{\mathcal{H}}}$ to denote the RKHS norm and $\|A\|_{\infty}$
denotes the operator norm of a bounded operator $A$. For operators $A$ and $B$
on $\mathcal{H}$, $A\preceq B$ if and only if $B-A$ is a positive definite
operator. For two real numbers $x$ and $y$, $x\lesssim y$ denotes that $x$ is
less than or equal to $y$ up to a constant factor, and $\otimes$ denotes the
tensor product. The notation $X\perp Y$ for two random variables, $X$ and $Y$,
translates to $X$ is independent of $Y$. $\tilde{O}(\cdot)$ denotes the order
of approximation (big-$O$) with some additional constant terms or terms of
logarithmic order in time.

###  2.2 Problem Setup

In the contextual bandit problem with finitely many arms, the decision-maker
has $L\in\mathbb{N}$ competing choices of arms (or actions), say
$\mathcal{A}:=\\{1,\ldots,L\\}$, and have to choose arms sequentially over
time, $\mathcal{T}=\\{1,\ldots,T\\}$, while using the contextual information
available at each time point, with $T$ being the horizon. The contextual
information can be thought of as patient characteristics in a treatment
allocation problem or user information in a recommender system application.
That is, at each time point $t\in\mathcal{T}$, the decision-maker observes
contextual information (covariate), $X_{t}\in\mathbb{R}^{d}$, from an
underlying probability distribution $\mathcal{P}_{X}$. Now, based on the
available information until time $t$, the decision-maker then chooses an arm
$a_{t}$ from a finite set of arms, $\mathcal{A}=\\{1,\ldots,L\\}$. Choosing
(pulling) the arm $a_{t}$ results in a reward, $y_{t}\in\mathbb{R}$. The
reward can be thought of as a quantitative outcome of assigning the arm at
that time. For instance, it could mean the amount of benefit caused by
assigning a particular treatment to a patient at a given time.

In order to make informed decisions, the decision-maker must understand the
relationship between the rewards, $\\{y_{t}\\}_{t=1}^{T}$, and covariates,
$\\{X_{t}\\}_{t=1}^{T}$, for each arm in $\\{1,\ldots,L\\}$. This
relationship, usually stochastic in nature, can naturally be formulated as a
regression problem. In this work, we assume a nonparametric regression
framework to model this relationship. For each arm, $i\in 1,\ldots,L$, we
consider the following regression model:

$\displaystyle y_{t}=f_{i}(X_{t})+e_{t},$ (1)

where the corresponding mean reward function $f_{i}\in\mathcal{H}$, with
$\mathcal{H}$ being a reproducing Kernel Hilbert space (RKHS) with reproducing
kernel $k:\mathcal{X}\times\mathcal{X}\rightarrow\mathcal{H}$, where
$\mathcal{X}$ is a separable topological space. We assume that $k$ is bounded
and continuous, i.e., there exists a $\kappa>0$, such that
$\sup_{x\in\mathcal{X}}k(x,x)\leq\kappa$. Note that, by the reproducing
property, $f_{i}(x_{t})=\langle f_{i},k(\cdot,x_{t})\rangle_{H}$. We make the
following model assumptions:

######  $(\mathcal{A}_{1})$.

Errors $\\{e_{t}\\}_{t}$ conditioned on an arm, i.e., $\\{e_{t}|i\\}_{t}$ are
i.i.d. random variables with mean 0 and finite variance,
$\sigma^{2}:=\mathbb{E}(e_{t}^{2}|i)<\infty$ for $i=1,\ldots,L$.

######  $(\mathcal{A}_{2})$.

$e_{t}\perp x_{t}|a_{t}=i$ for all $t=1,\ldots,T$, and $i=1,\ldots,L$.

Note that the above distributional assumptions on the error are weaker than
that made in Chen et al., (2021), where the errors are assumed to be sub-
Gaussian in addition to satisfying the assumptions $(\mathcal{A}_{1})$ and
$(\mathcal{A}_{2})$. Higher variability in the noise would lead to larger
regret bounds but would not change the rate of convergence for our proposed
allocation strategy.

In Section 3.1, we propose an allocation strategy or an algorithm,
$\mathcal{B}$, for choosing the next arm based on the sequence of past
information on arms played, the covariates, and the rewards obtained
respectively. We will build online estimators for the mean reward functions,
$f_{i},i=1,\ldots L$, in Section 3.2. Then, we use these estimators to make
optimal decisions about arms in a sequential manner. Next, we formulate the
notion of regret which is a standard way to assess the performance of
contextual bandit algorithms.

For covariate $X_{t}=x_{t}$, let,

$a^{*}_{t}:=\text{arg\ max}_{a\in\\{1,\ldots,L\\}}f_{a}(x_{t})$

be the true best arm at time $t$ and $f_{a^{*}_{t}}(x_{t})$ the corresponding
best function value. Then, given the previously observed contexts, arms and
rewards $\\{(X_{s},a_{s},y_{s})\\}_{s=1,\ldots,t-1}$ and the current context
$X_{t}=x_{t}$, a standard goal in a contextual bandit problem is to choose an
action $a_{t}$ in order to minimize the regret (see Definition 1) after $T$
rounds. Let $\mathcal{F}_{t}=\sigma\langle
a_{1},x_{1},y_{1},a_{2},x_{2},y_{2},\ldots,a_{t},x_{t},y_{t}\rangle$ denote
the sigma-field generated by all information on the covariates observed, arms
pulled, and rewards obtained, respectively, until time $t$.

######  Definition 1.

The instantaneous regret at time $t$ is
$r_{t}(\mathcal{B}):=f_{a^{*}_{t}}(x_{t})-f_{a_{t}}(x_{t})$, where $a^{*}_{t}$
is the optimal arm at time $t$ and $a_{t}$ is the arm chosen by the bandit
algorithm, $\mathcal{B}$, at time $t$. The cumulative regret
$R_{T}(\mathcal{B})$ with horizon $T$ is defined as:

$\displaystyle
R_{T}(\mathcal{B}):=\sum_{t=1}^{T}(f_{a^{*}_{t}}(X_{t})-f_{a_{t}}(X_{t})).$

Note that, the regret as defined above is a random quantity. Thus, we are
interested in finding an upper bound for regret in probability or in
expectation. Since our method aims at providing model flexibility by allowing
us to discover a non-linear relationship between expected rewards and
covariates in an RKHS while trying to achieve contextual bandit designs which
are less prone to problems of bias, we also study the estimation error. Let
$\hat{f}_{a}$ denote the proposed estimator for $f_{a}$. The estimation error
at time $t$ is defined as $\|\hat{f}_{a_{t}}-f_{a_{t}}\|_{\mathcal{H}}$, where
$a_{t}$ is the arm chosen by the algorithm.

##  3 Kernel $\epsilon$-greedy algorithm & IPKWR estimator

A simple policy to make sequential decisions in a contextual bandit framework
is to be greedy and choose the arm yielding the highest estimated reward for
that covariate. However, this could lead to under-exploring some arms thus
adversely affecting the performance of the algorithm. A way around this is to
use $\epsilon$-greedy, a randomized version of the greedy algorithm, which
chooses the best arm with a large probability, i.e., $(1-\epsilon)$ and
explores the remaining arms with a small probability, i.e., $\epsilon$. In the
following, we propose a kernel $\epsilon$-greedy algorithm that sequentially
makes decisions about which arms to play for the contextual bandits’ problem
as described in Section 2.2.

###  3.1 Kernel $\epsilon$-greedy algorithm

The proposed algorithm is a kernelized version of the popular
$\epsilon$-greedy algorithm for the contextual bandit problem. Let
$\\{\epsilon_{t}\\}_{t}$ be a sequence of non-increasing probabilities, such
that $\epsilon_{t}\rightarrow 0$ as $t\rightarrow\infty$. We denote
$\hat{a}_{t}$ to be the arm chosen by the proposed algorithm at time $t$, as
it depends on all previous data. Below, we describe the kernel
$\epsilon$-greedy strategy.

  1. 1.

Initialize. Randomly select among the $L$ arms up to time $t_{0}$ for
$t=1,2,\ldots,t_{0}$, such that at least one reward per arm is obtained by
time $t_{0}$.

  2. 2.

Estimate $f_{i}$. At time $t_{0}$, construct regression estimators for the $L$
arms and denote them by $\hat{f}_{i,t_{0}},i=1,\ldots,L$.

  3. 3.

Most promising arm at time $t$. For $t=t_{0}+1$, observe covariate
$X_{t}=x_{t}$ and define:

$\displaystyle A_{t}=\text{arg\ max}_{i\in\mathcal{A}}\hat{f}_{i,t-1}(x_{t}),$

be the arm corresponding to the highest estimated value at the current
covariate.

  4. 4.

$\epsilon$-greedy step. For a non-increasing probability sequence
$\\{\epsilon_{t}\\}_{t}$, the arm pulled is given by the following randomized
scheme:

$\displaystyle\hat{a}_{t}=\begin{cases}A_{t}&\ \text{with probability
}1-\epsilon_{t}\\\ \\{1,\ldots,L\\}\backslash A_{t}&\ \text{with probability
}\frac{\epsilon_{t}}{L-1}\end{cases}.$ (2)

  5. 5.

Update the estimators. Corresponding to the arm pulled at time $t=t_{0}+1$,
observe reward $Y_{t}$ and update $\hat{f}_{\hat{a}_{t},t}$. For the remaining
arms, $i\neq\hat{a}_{t}$, $\hat{f}_{i,t}=\hat{f}_{i,t-1}$.

  6. 6.

Repeat steps 3-5 for $t=t_{0}+2$ and so on up to time $T$.

Note that step 1 is an initialization step, where we randomly assign the $L$
arms until time $t_{0}$, such that at least one reward is observed per arm by
then. In step 2, we construct regression estimators for each arm using the
information gathered during the initialization phase. Step 2 is presented as a
generic step as we do not describe how the regression estimator is
constructed. We propose an inverse probability weighted kernel ridge
regression estimator in Section 3.2 and study the above algorithm for that
specific estimator. In step 3, at time $t=t_{0}+1$, we evaluate estimated mean
reward functions at the covariate $X_{t}$ for each arm using the estimators
constructed in step 2 and find the arm $A_{t}$ that maximizes the estimated
mean reward. Note that, at this instant, we face the exploration-exploitation
dilemma. That is, we can either choose the most promising arm, $A_{t}$, based
on the data available so far or explore the remaining arms, $a\neq A_{t}$. We
use the $\epsilon$-greedy strategy in step 4 in order to balance this trade-
off. This is a randomization scheme where we choose the best promising arm
$A_{t}$ with a larger probability $1-\epsilon_{t}$ and explore the other arms
$a\neq A_{t}$ with the remaining probabilities $\epsilon_{t}/(L-1)$. We also
assume that $\epsilon_{t}\leq(L-1)/L$ for $t>t_{0}$, so that
$1-\epsilon_{t}\geq\epsilon_{t}/(L-1)$. Note that, the exploration
probabilities $\\{\epsilon_{t}\\}_{t}$ are chosen to be a decreasing sequence
of probabilities converging to 0 as $t\rightarrow\infty$, hence exploiting
more with time. This is because as we accumulate more data, we gain more
confidence in our estimates for the mean rewards for each of the arms. Then,
the same process is repeated sequentially until we hit the time horizon $T$.
In Section 3.2, we propose an online kernel regression estimator, which we use
in this algorithm. Note that, we have a ‘hat’ on the proposed arm notation,
$\hat{a}_{t}$, to highlight that the choice of the arm is data dependent.

###  3.2 Inverse probability weighted kernel ridge regression estimator

In this section, we propose an online version of the kernel ridge regression
estimator for the mean reward functions $f_{i},i=1,\ldots,L$. Recall,
$\mathcal{F}_{t}=\sigma\langle\hat{a}_{1},x_{1},y_{1},\hat{a}_{2},x_{2},y_{2},\ldots,\hat{a}_{t},x_{t},y_{t}\rangle$
denotes the sigma-field generated by all information on the covariates
observed, arms pulled, and rewards obtained, respectively, until time $t$. In
order to build an online kernel ridge regression estimator, we solve the
following optimization problem with Tikhonov regularization,

$\displaystyle\hat{f}_{i,t}=\text{arg\
min}_{f_{i}\in\mathcal{H}}\sum_{s=1}^{t}I\\{\hat{a}_{s}=i\\}(Y_{s}-\langle
f_{i},k(\cdot,X_{s})\rangle_{\mathcal{H}})^{2}+\lambda\|f_{i}\|_{\mathcal{H}}^{2},$

where $\lambda>0$ is the regularization parameter. Using the same ideas as in
kernel ridge regression, it is easy to verify that

$\displaystyle\hat{f}_{i,t}$
$\displaystyle=\left(\sum_{s=1}^{t}I\\{\hat{a}_{s}=i\\}k(\cdot,X_{s})\otimes
k(\cdot,X_{s})+{\lambda}I\right)^{-1}\sum_{s=1}^{t}I\\{\hat{a}_{s}=i\\}k(\cdot,X_{s})Y_{s},$
(3)

where $I\\{\hat{a}_{s}=i\\}$ denotes the indicator function which is 1 if the
arm chosen by the algorithm at time $s$ is $i$ and is 0 otherwise. While the
online kernel-ridge regression estimator in (3) could be a potential candidate
to consider, we work with a modified version of this estimator which provides
an unbiased estimator of the covariance operator, i.e.,
$\mathbb{E}[k(\cdot,X)\otimes k(\cdot,X)]$, as shown in Lemma 1. Specifically,
we consider an online Inverse Probability Weighted Kernel Ridge (IPWKR)
regression estimator given by:

$\displaystyle\hat{f}_{i,t}=\left(\dfrac{1}{t}\sum_{s=1}^{t}\dfrac{I\\{\hat{a}_{s}=i\\}}{P(\hat{a}_{s}=i|\mathcal{F}_{s-1},X_{s})}k(\cdot,X_{s})\otimes
k(\cdot,X_{s})+\lambda
I\right)^{-1}\dfrac{1}{t}\sum_{s=1}^{t}\dfrac{I\\{\hat{a}_{s}=i\\}}{P(\hat{a}_{s}=i|\mathcal{F}_{s-1},X_{s})}k(\cdot,X_{s})Y_{s},$
(4)

for $i=1,\ldots,L$. Note that, in the above algorithm, the probability weights
$P(\hat{a}_{s}=i|\mathcal{F}_{s-1},X_{s})$ are known at time $s$. More
specifically, since we know $A_{s}$ and $\epsilon_{s}$ at time step $s$,
$P(\hat{a}_{s}=A_{s}|\mathcal{F}_{s-1},X_{s})=1-\epsilon_{s}$ and
$P(\hat{a}_{s}=a|\mathcal{F}_{s-1},X_{s})=\epsilon_{s}/(L-1)$ for $a\neq
A_{s}$, therefore $\hat{f}_{i,s}$ for $i=1,\ldots,L$ and for $s=1,\ldots,t$
are data-determined estimates and can be used for estimation at the $(t+1)$th
time. Note that the definitions of the arm pulled (see (2)) and the online
IPWKR estimator in (4) depend on each other. Since the data are not
independent, the consistency of the estimator does not follow immediately from
the classical tools in kernel methods. Therefore, one of our contributions is
in analyzing the estimation error associated with the online IPWKR estimator,
and establish its consistency and rate of convergence.

From the proposed estimator, it is easy to see that a natural candidate for
the estimator of the covariance operator is:

$\displaystyle\hat{\Sigma}_{i,t}=\dfrac{1}{t}\sum_{s=1}^{t}\frac{I\\{\hat{a}_{s}=i\\}}{P(\hat{a}_{s}=i|\mathcal{F}_{s-1},X_{s})}k(\cdot,X_{s})\otimes
k(\cdot,X_{s}),$ (5)

which can be shown (see Lemma 1) to be an unbiased estimator of the covariance
operator $\Sigma:=\mathbb{E}(k(\cdot,X_{s})\otimes k(\cdot,X_{s}))$. We
highlight that the unbiasedness of the covariance estimator is critical in our
analysis. In the following, we re-write the proposed kernel $\epsilon$-greedy
algorithm of Section 3.1 in an implementable format.

###  3.3 Implementation of kernel $\epsilon$-greedy algorithm

In this section, we devise an implementable version of the proposed strategy.
To this, we define the following.

  * •

Let $S_{t,X}:\mathcal{H}\rightarrow\mathbb{R}^{t}$ be the sampling operator,
such that $S_{t,X}f=\frac{1}{\sqrt{t}}[f(X_{1}),\ldots,f(X_{t})]^{\top}$.

  * •

The reconstruction operator is given by
$S_{t,X}^{*}:\mathbb{R}^{t}\rightarrow\mathcal{H}$, where
$S_{t,X}^{*}\underline{\alpha}=\frac{1}{\sqrt{t}}\sum_{s=1}^{t}\alpha_{s}k(\cdot,X_{s})$,
for $\underline{\alpha}\in\mathbb{R}^{t}$.

  * •

$S_{t,X}S_{t,X}^{*}=\frac{K_{t}}{t}:\mathbb{R}^{t}\rightarrow\mathbb{R}^{t}$,
where $K_{t}$ is the kernel/Gram matrix.

We express the empirical covariance operator in (5) in terms of these
operators. Let $\Lambda_{i,t}$ be a diagonal matrix in $\mathbb{R}^{t\times
t}$ with diagonal elements given by,

$\left\\{w_{s,i}:=\frac{I\\{\hat{a}_{s}=i\\}}{P(\hat{a}_{s}=i|\mathcal{F}_{s-1},X_{s})},s=1,\ldots,t\right\\}.$

Then note that, $\hat{\Sigma}_{i,t}=S_{t,X}^{*}\Lambda_{i,t}S_{t,X}$ and,

$\displaystyle\hat{\Sigma}_{i,t}f=\dfrac{1}{t}\sum_{s=1}^{t}w_{s,i}f(X_{s})k(\cdot,X_{s})\
\text{for all}\ i=1,\ldots,L.$

Let ${Y}_{t}=(y_{1},\ldots,y_{t})^{\prime}$. Then, the proposed estimator in
(4) can be written as:

$\displaystyle\hat{f}_{i,t}$
$\displaystyle=\dfrac{1}{\sqrt{t}}(S_{t,X}^{*}\Lambda_{i,t}S_{t,X}+\lambda
I)^{-1}\dfrac{1}{\sqrt{t}}\sum_{s=1}^{t}w_{s,i}k(\cdot,X_{s})y_{s}$
$\displaystyle=\dfrac{1}{\sqrt{t}}(S_{t,X}^{*}\Lambda_{i,t}S_{t,X}+\lambda
I)^{-1}S_{t,X}^{*}\Lambda_{i,t}{Y}_{t}$
$\displaystyle=\dfrac{1}{\sqrt{t}}S_{t,X}^{*}(\Lambda_{i,t}S_{t,X}S_{t,X}^{*}+\lambda
I)^{-1}\Lambda_{i,t}Y_{t},$

where the last equality follows from the fact that,

$\displaystyle(S_{t,X}^{*}\Lambda_{i,t}S_{t,X}+\lambda
I)^{-1}S_{t,X}^{*}=S_{t,X}^{*}(\Lambda_{i,t}S_{t,X}S_{t,X}^{*}+\lambda
I)^{-1}.$

Therefore we obtain

$\displaystyle\hat{f}_{i,t}$
$\displaystyle=\dfrac{1}{\sqrt{t}}S_{t,X}^{*}\left(\Lambda_{i,t}\frac{K_{t}}{t}+\lambda
I\right)^{-1}\Lambda_{i,t}Y_{t},\ \text{for}\ i=1,\ldots,L.$ (6)

Then, using the definition of $S_{t,X}^{*}$, the estimated reward function
value at $X_{t+1}$ for arm $i$ is given by:

$\displaystyle\hat{f}_{i,t}(X_{t+1})$
$\displaystyle=\dfrac{1}{t}\bar{k}_{t+1}^{\top}\left(\Lambda_{i,t}\frac{K_{t}}{t}+\lambda_{t}I\right)^{-1}\Lambda_{i,t}Y_{t}$
$\displaystyle=\bar{k}_{t+1}^{\top}(\Lambda_{i,t}{K_{t}}+t\lambda_{t}I)^{-1}\Lambda_{i,t}Y_{t}\
\text{for}\ i=1,\ldots,L,$ (7)

where,
$\bar{k}_{t+1}=\left(k(X_{1},X_{t+1}),k(X_{2},X_{t+1}),\ldots,k(X_{t},X_{t+1})\right)^{\top}$.
Note that (7) involves only inverting a $t\times t$ matrix and therefore this
version of the estimator is implementable. In order to facilitate faster
computation, we use SVD for finding the inverse in (7).

1:Randomly select arms
$\hat{a}_{1},\hat{a}_{2},\ldots,\hat{a}_{t_{0}}\in\mathcal{A}=\\{1,\ldots,L\\}$
until each arm is selected at least once.

2:for $t=t_{0}+1,\ldots,T$ do

3: Estimate $\hat{f}_{i,t-1}(X_{t})$, for each $i=\mathcal{A}$ using (7).

4: Calculate the best-performing arm so far: $A_{t}=\text{arg\
max}_{i\in\mathcal{A}}\hat{f}_{i,t-1}(X_{t})$.

5: For a non-increasing exploration probability sequence
$\\{\epsilon_{t},t\geq 1\\}$, the arm pulled is given by:
$\displaystyle\hat{a}_{t}=\begin{cases}A_{t}&\ \text{with probability}\
1-\epsilon_{t}\\\ \\{1,\ldots,L\\}\backslash A_{t}&\ \text{with probability}\
\frac{\epsilon_{t}}{L-1}.\end{cases}$

6: Observe reward $Y_{t}$ corresponding to $\hat{a}_{t}$.

7: For $i=\hat{a}_{t}$, update $\hat{f}_{i,t}$ using (6) and use
$\hat{f}_{i,t}=\hat{f}_{i,t-1}$ for $i\in\mathcal{A}\backslash\hat{a}_{t}$.

8:end for

Algorithm 1 Kernel $\epsilon$-greedy algorithm

##  4 Estimation error: Convergence rates

In this section, we present the theoretical results for the proposed algorithm
for which the proofs can be found in Section 8. We make the following
assumptions throughout this paper whenever we are working under the assumption
that the mean reward functions lie in an RKHS $\mathcal{H}$.

######  $(\mathcal{A}_{3})$.

$\eta_{i}(\Sigma)\leq\bar{C}i^{-\alpha},\alpha>1$ where $\eta_{i}(\Sigma)$
denotes the $i^{th}$ eigenvalue of $\Sigma=\mathbb{E}(k(\cdot,X_{s})\otimes
k(\cdot,X_{s}))$ and $\bar{C}\in(0,\infty)$.

######  $(\mathcal{A}_{4})$.

For all $i=1,\ldots,L$, $f_{i}\in\emph{Ran}(\Sigma^{\gamma_{i}})$,
$0<\gamma_{i}\leq\frac{1}{2}$, i.e., there exists $h\in\mathcal{H}$ such that
$f_{i}=\Sigma^{\gamma_{i}}h$ for $i=1,\ldots,L$.

Note that, $(\mathcal{A}_{3})$ implies that the effective dimension,
$N_{\Sigma,1}(\lambda):=\operatorname{Tr}\left((\Sigma+\lambda
I)^{-1}\Sigma\right)\lesssim\lambda^{-1/\alpha}$, which controls the
complexity of $\mathcal{H}$ and $(\mathcal{A}_{4})$ determines the smoothness
of the true mean reward functions. Next, in Theorem 1, which is proved in
Section 8.1, we present an upper bound on the estimation error both in
probability and in expectation.

######  Theorem 1.

Suppose $(\mathcal{A}_{1})$–$(\mathcal{A}_{4})$ hold and
$\\{\epsilon_{s}\\}^{t}_{s=1}$ is such that for any $\delta>0$ and $t\geq 1$,

$\displaystyle\lambda_{i,t}=\left[\dfrac{1}{\delta
t^{2}}\left(\sum_{s=1}^{t}\dfrac{1}{\epsilon_{s}}\right)\right]^{\alpha/(2\gamma_{i}\alpha+\alpha+1)},\,\,i=1,\ldots,L,$
(8)

satisfies

$\displaystyle\lambda_{i,t}\geq\left[\dfrac{4(L-1)\kappa
A_{1}(\bar{C},\alpha)}{\delta
t^{2}}\left(\sum_{s=1}^{t}\dfrac{1}{\epsilon_{s}}\right)\right]^{\alpha/(1+\alpha)}.$
(9)

Then, the following holds with probability at least $1-2\delta$:

$\displaystyle\|\hat{f}_{i,t}-f_{i}\|_{\mathcal{H}}\leq
2\sqrt{2}\max\\{C_{0},C_{i}\\}\left[\dfrac{1}{\delta
t^{2}}\left(\sum_{s=1}^{t}\frac{1}{\epsilon_{s}}\right)\right]^{\gamma_{i}\alpha/(2\gamma_{i}\alpha+\alpha+1)},\,\,i=1,\ldots,L.$
(10)

Furthermore, for
$0\leq\zeta<\frac{\gamma_{i}\alpha+\alpha+1}{\gamma_{i}\alpha}$,

$\displaystyle\mathbb{E}[\|\hat{f}_{i,t}-f_{i}\|_{\mathcal{H}}^{1+\zeta}]\leq
B(C_{0},C_{i},\gamma_{i},\zeta,\alpha)\left[\dfrac{1}{t^{2}}\sum_{s=1}^{t}\dfrac{1}{\epsilon_{s}}\right]^{w_{i}(1+\zeta)},\,\,i=1,\ldots,L,$
(11)

where $C_{0}=\sqrt{\sigma^{2}(L-1)A_{1}(\bar{C},\alpha)}$,
$A_{1}(\bar{C},\alpha)=\bar{C}^{-1/\alpha}\int^{\infty}_{0}(1+x^{\alpha})^{-1}\,dx$,
$C_{i}=\|\Sigma^{-\gamma_{i}}f_{i}\|_{\mathcal{H}}$,
$w_{i}=\frac{\gamma_{i}\alpha}{2\gamma_{i}\alpha+\alpha+1}$, and
$B(C_{0},C_{i},\gamma_{i},\zeta,\alpha)$ is a constant depending only on its
arguments and not on $t$ and $\\{\epsilon_{s}\\}_{s}$.

Note that the upper bound on the estimation error depends on the exploration
probability sequence $\\{\epsilon_{s}\\}_{s=1}^{t}$, and for consistent
estimation, we require $\sum_{s=1}^{t}\epsilon^{-1}_{s}=o(t^{2})$ as
$t\rightarrow\infty$. Under this requirement of
$\sum_{s=1}^{t}\epsilon^{-1}_{s}=o(t^{2})$ as $t\rightarrow\infty$, it is easy
to verify that (9) holds. Also, we would like to highlight that the
restriction on $\zeta$ appearing in Theorem 1 is due to polynomial (precisely,
quadratic) concentration in (10), which if improved to sub-exponential or sub-
Gaussian concentration would remove the upper bound restriction on $\zeta$.

In order to compare Theorem 1 with Proposition 4.1 in Chen et al., (2021), we
assume that the underlying RKHS, $\mathcal{H}$, is finite-dimensional, and
make the following assumption instead of $(\mathcal{A}_{4})$:

######  $(\mathcal{A}_{5})$.

The minimum eigenvalue of $\Sigma$, denoted as $\eta_{\emph{min}}(\Sigma)$
satisfies $\eta_{\emph{min}}(\Sigma)>\eta$ for some $\eta>0$.

Since Chen et al., (2021) study linear contextual bandits which are equivalent
to our approach when the kernel is linear, i.e., the corresponding RKHS is
finite-dimensional, we would like to specialize Theorem 1 to finite-
dimensional RKHS. This assumption of finite-dimensional RKHS is imposed
through $(\mathcal{A}_{5})$, which is also assumed in Chen et al., (2021).

######  Theorem 2.

Suppose $(\mathcal{A}_{1})$, $(\mathcal{A}_{2})$ and $(\mathcal{A}_{5})$ hold.
For any $\delta>0$ and $t\geq 1$, suppose $\\{\epsilon_{s}\\}^{t}_{s=1}$
satisfies

$\displaystyle\frac{1}{t^{2}}\sum^{t}_{s=1}\frac{1}{\epsilon_{s}}\leq\frac{\delta\eta}{4(L-1)d\kappa},$
(12)

where $d:=\emph{dim}(\mathcal{H})$. Then, for any $\delta>0$ and $t\geq 1$,
with the choice of

$\displaystyle\lambda_{i,t}=\left[\dfrac{1}{\delta
t^{2}}\left(\sum_{s=1}^{t}\dfrac{1}{\epsilon_{s}}\right)\right]^{1/2},\,\,i=1,\ldots,L,$

the following holds with probability at least $1-2\delta$:

$\displaystyle\|\hat{f}_{i,t}-f_{i}\|_{\mathcal{H}}\leq
4\max\\{\tilde{C}_{0},\tilde{C}_{i}\\}\left[\dfrac{1}{\delta
t^{2}}\left(\sum_{s=1}^{t}\frac{1}{\epsilon_{s}}\right)\right]^{1/2},\
i=1,\ldots,L.$

Moreover, for $0\leq\zeta<1$,

$\displaystyle\mathbb{E}[\|\hat{f}_{i,t}-f_{i}\|_{\mathcal{H}}^{1+\zeta}]\leq
B(\tilde{C}_{0},\tilde{C}_{i},\zeta,\eta)\left[\dfrac{1}{t^{2}}\sum_{s=1}^{t}\dfrac{1}{\epsilon_{s}}\right]^{\frac{1+\zeta}{2}},\,\,i=1,\ldots,L,$
(13)

where $\tilde{C}_{0}:=\sqrt{\frac{(L-1)d\sigma^{2}}{\eta}}$ and
$\tilde{C}_{i}:=\frac{\|f_{i}\|_{\mathcal{H}}}{\eta}$. Here
$B(\tilde{C}_{0},\tilde{C}_{i},\zeta,\eta)$ is a constant that depends only on
its arguments and not on $t$ and $\\{\epsilon_{s}\\}_{s}$.

Note that in the above result, the choice of $\lambda_{i,t}$ is independent of
$i$ unlike in the infinite-dimensional case of Theorem 1. Moreover, unlike in
Theorem 1, the choice of $\lambda_{i,t}$ in Theorem 2 has an exponent of
$\frac{1}{2}$ instead of the term depending on $\gamma_{i}$ and $\alpha$ in
(10). Clearly, the estimators are consistent if
$\sum_{s=1}^{t}\epsilon^{-1}_{s}=o(t^{2})$ as $t\rightarrow\infty$. Under this
requirement on $\\{\epsilon_{s}\\}_{s}$, it is easy to verify that (12) holds.
The proof of Theorem 2 is provided in Section 8.2.

######  Remark 1.

Chen et al., (2021) proposed a weighted online least squares estimator similar
to the IPWKR estimator for the linear contextual bandit problem with 2 arms
($L=2$) and a finite-dimensional context space. However, unlike our estimator,
they study an unregularized online weighted least squares (WLS) estimator.
Under the assumptions of (i) bounded covariates, (ii) reliability of linear
approximation, and (iii) minimum eigenvalue are bounded from below, they
provide a bound (see Proposition 4.1) on the estimation error, which can be
summarized to behave as

$\displaystyle\tilde{O}\left(\left[\dfrac{d^{2}\log(4d/\delta)}{t\epsilon_{t}^{4}}\right]^{1/2}\right)$
(14)

with probability at least $1-\delta$. On the other hand, our method provides a
bound of

$\displaystyle\tilde{O}\left(\left[\dfrac{d}{\delta}\dfrac{1}{t^{2}}\Big{(}\sum_{s=1}^{t}\dfrac{1}{\epsilon_{s}}\Big{)}\right]^{1/2}\right),$
(15)

which also holds with probability $1-\delta$. By comparing (14) and (15), it
can be observed that the bound in Chen et al., (2021) holds with sub-Gaussian
concentration while ours holds with polynomial concentration. Another key
distinction is the requirement of $\frac{1}{\epsilon_{t}}=o(t^{1/4})$ in (14)
vs. $\sum_{s=1}^{t}\epsilon^{-1}_{s}=o(t^{2})$ in (15) for the estimators to
be consistent, as $t\rightarrow\infty$. Clearly, a sufficient condition for
our estimator to be consistent is $\frac{1}{\epsilon_{t}}=o(t)$. Therefore,
our result is stronger than that of Chen et al., (2021), as the exploration
probability can decay at a faster rate while still guaranteeing the
consistency of our estimator. This is promising as for situations where the
reward functions are relatively easier to learn, more exploitative strategies
can significantly reduce the regret. Another key highlight of our work is that
these improved results are obtained for any $f_{i}$ belonging to a finite-
dimensional RKHS, that is not necessarily linear.

##  5 Regret analysis

In this section, we construct upper bounds for the regret defined in
Definition 1 for the algorithm proposed in Section 3 that involves using the
IPWKR estimator studied in Section 3.2. Recall, $a^{*}_{t}=\text{arg\
max}_{a\in\mathcal{A}}f_{a}(x_{t}),$ where $f_{a}(x_{t})=\langle
f_{a},k(\cdot,x_{t})\rangle_{\mathcal{H}}$. Let $A_{t}=\text{arg\
max}_{a\in\mathcal{A}}\hat{f}_{a}(x_{t})$ and note that by definition of
$A_{t}$, $\hat{f}_{a^{*}_{t}}(X_{t})\leq\hat{f}_{A_{t}}(X_{t})$. Then, the
cumulative regret for the proposed algorithm up to some time horizon $T$ is
given by,

$\displaystyle R_{T}$
$\displaystyle=\sum_{t=1}^{T}f_{a^{*}_{t}}(X_{t})-f_{\hat{a}_{t}}(X_{t})=\sum_{t=1}^{t_{0}}f_{a^{*}_{t}}(X_{t})-f_{\hat{a}_{t}}(X_{t})+\sum_{t=t_{0}+1}^{T}f_{a^{*}_{t}}(X_{t})-f_{\hat{a}_{t}}(X_{t})$
$\displaystyle=\sum_{t=1}^{t_{0}}\langle
f_{a^{*}_{t}}-f_{\hat{a}_{t}},k(\cdot,X_{t})\rangle_{\mathcal{H}}+\sum_{t=t_{0}+1}^{T}f_{a^{*}_{t}}(X_{t})-f_{\hat{a}_{t}}(X_{t})$
$\displaystyle\leq\sum_{t=1}^{t_{0}}\kappa\|f_{a^{*}_{t}}-f_{\hat{a}_{t}}\|_{\mathcal{H}}+\sum_{t=t_{0}+1}^{T}f_{a^{*}_{t}}(X_{t})-f_{\hat{a}_{t}}(X_{t})\leq\Lambda
t_{0}+\sum_{t=t_{0}+1}^{T}f_{a^{*}_{t}}(X_{t})-f_{\hat{a}_{t}}(X_{t})$
$\displaystyle=\Lambda
t_{0}+\sum_{t=t_{0}+1}^{T}\left[f_{a^{*}_{t}}(X_{t})-\hat{f}_{a^{*}_{t}}(X_{t})+\hat{f}_{a^{*}_{t}}(X_{t})-f_{A_{t}}(X_{t})+f_{A_{t}}(X_{t})-f_{\hat{a}_{t}}(X_{t})\right]$
$\displaystyle\leq\Lambda
t_{0}+\sum_{t=t_{0}+1}^{T}\left[f_{a^{*}_{t}}(X_{t})-\hat{f}_{a^{*}_{t}}(X_{t})+\hat{f}_{A_{t}}(X_{t})-f_{A_{t}}(X_{t})+f_{A_{t}}(X_{t})-f_{\hat{a}_{t}}(X_{t})\right]$
$\displaystyle\leq\Lambda
t_{0}+2\underbrace{\sum_{t=t_{0}+1}^{T}\sup_{a\in\mathcal{A}}|(f_{a}(X_{t})-\hat{f}_{a,t}(X_{t}))|}_{\text{Cumulative
estimation
error}}+\underbrace{\sum_{t=t_{0}+1}^{T}|f_{A_{t}}(X_{t})-f_{\hat{a}_{t}}(X_{t})|}_{\text{Randomization
error}},$ (16)

where
$\Lambda:=\sup\\{\|f_{a}-f_{a^{\prime}}\|_{\mathcal{H}}:a,a^{\prime}\in\mathcal{A},a\neq
a^{\prime}\\}$, and for simplicity, we did not put the algorithm within
parenthesis for $R_{T}$ (as in Definition 1) though all the presented results
are for the proposed kernel $\epsilon$-greedy algorithm. Note that the first
term in (16) is the regret incurred due to the random initialization up to
time $t_{0}$. We call the second term on the right-hand side in (16) as
cumulative estimation error, as it measures the error in estimating the
function accumulated over time, and the third term as randomization error
since it measures the error incurred due to the randomization scheme
($\epsilon$-greedy in step 4 of the proposed algorithm in Section 3). Note
that, the initialization phase regret can be trivially bounded by $O(t_{0})$,
but the regret incurred during the post-initialization phase dominates over
the regret incurred over the initialization phase. Hence, without the loss of
generality, we set $t_{0}=0$ in the following results and in the corresponding
proofs.

######  Theorem 3.

Suppose $(\mathcal{A}_{1})$–$(\mathcal{A}_{4})$ hold,
$\sup_{\begin{subarray}{c}a,a^{\prime}\in\mathcal{A}\\\ a\neq
a^{\prime}\end{subarray}}\|f_{a}-f_{a^{\prime}}\|_{\mathcal{H}}<\infty$, and
$\\{\epsilon_{s}\\}^{T}_{s=1}$ is such that for any $\delta>0$, and $T\geq 1$,

$\displaystyle\lambda_{i,t}=\left[\dfrac{L}{\delta
t^{2}}\left(\sum_{s=1}^{t}\dfrac{1}{\epsilon_{s}}\right)\right]^{\alpha/(2\gamma_{i}\alpha+\alpha+1)},\,\,i\in\\{1,\ldots,L\\},\,\,0<t\leq
T,$ (17)

satisfies

$\lambda_{i,t}\geq\left[\dfrac{4L(L-1)\kappa A_{1}(\bar{C},\alpha)}{\delta
t^{2}}\left(\sum_{s=1}^{t}\dfrac{1}{\epsilon_{s}}\right)\right]^{\alpha/(1+\alpha)}\,\,i\in\\{1,\ldots,L\\},\,\,0<t\leq
T.$

Define

$\Delta_{t}=\frac{L}{\delta t^{2}}\sum_{s=1}^{t}\frac{1}{\epsilon_{s}}.$

Then, for $\delta>0$, $1\leq p\leq\infty$ and $T\geq 1$, the following holds
with probability at least $1-2\delta$:

$\displaystyle R_{T}$
$\displaystyle\leq\kappa\Theta\sum_{t=1}^{T}\left(I\\{\Delta_{t}<1\\}\Delta_{t}^{\frac{(\min_{i\in\mathcal{A}}\gamma_{i})\alpha}{2(\min_{i\in\mathcal{A}}\gamma_{i})\alpha+\alpha+1}}+I\\{\Delta_{t}\geq
1\\}\Delta_{t}^{\frac{(\max_{i\in\mathcal{A}}\gamma_{i})\alpha}{2(\max_{i\in\mathcal{A}}\gamma_{i})\alpha+\alpha+1}}\right)$
$\displaystyle\quad+\kappa
T^{1-\frac{1}{p}}\left[\sum_{t=1}^{T}\dfrac{\epsilon_{t}}{L-1}+\left\\{\dfrac{1}{\delta}\sum_{t=1}^{T}\dfrac{\epsilon_{t}}{L-1}\right\\}^{1/2}\right]^{1/p}\sup_{\begin{subarray}{c}a,a^{\prime}\in\mathcal{A}\\\
a\neq a^{\prime}\end{subarray}}\|f_{a}-f_{a^{\prime}}\|_{\mathcal{H}},$ (18)

where $\Theta=4\sqrt{2}\max\\{C_{0},\max_{i\in\mathcal{A}}C_{i}\\}$ with
$C_{0}$, $C_{i}$ and $A_{1}(\bar{C},\alpha)$ being defined in Theorem 1.

The first term in the r.h.s. of (18) corresponds to the estimation error
accumulated by time $T$ and the second term corresponds to the randomization
error. The cumulative estimation error bound follows from the estimation error
analysis in Theorem 1, after applying a union bound over the arms. Note that
for a given sequence of exploration probability, the cumulative estimation
error and the randomization error behave inversely to each other. Further,
note that if $\sum^{t}_{s=1}\epsilon^{-1}_{s}=o(t^{2})$ as
$t\rightarrow\infty$, then clearly $\Delta_{t}<1$ for some large enough $t$.
Let $t_{1}=\min_{t}I\\{\Delta_{t}<1\\}$. Then, we can choose the
initialization phase endpoint to be $\tilde{t}_{0}=\max\\{t_{0},t_{1}\\}$,
which means only the first term in the accumulated estimation error would
contribute to the regret bound. This reflects that the estimation error
incurred due to the arm with the lowest smoothness parameter for the
respective reward function dominates.

######  Remark 2.

Suppose $\epsilon_{t}=t^{-\beta}$ for some $0<\beta<1$ and $t\in\mathbb{N}$,
which satisfies the requirement that $\sum^{t}_{s=1}\epsilon^{-1}_{s}\lesssim
t^{\beta+1}=o(t^{2})$ as $t\rightarrow\infty$. Then under the assumptions of
Theorem 3, for large enough $T$, (18) reduces to

$R_{T}\lesssim T^{(\beta-1)w+1}+T^{1-\frac{\beta}{p}},$

for the choice of $\lambda_{i,t}$ as in (17) and

$w={\frac{(\min_{i\in\mathcal{A}}\gamma_{i})\alpha}{2(\min_{i\in\mathcal{A}}\gamma_{i})\alpha+\alpha+1}}.$

Since $1\leq p\leq\infty$ is arbitrary, the best regret is achieved at $p=1$,
yielding

$R_{T}\lesssim T^{(\beta-1)w+1}+T^{1-\beta}.$ (19)

In (19), the first term corresponds to an upper bound on the cumulative
estimation error, which is increasing in $\beta$ and the second term
corresponds to an upper bound on the randomization error, which is decreasing
in $\beta$. By balancing these two terms, the optimal choice of $\beta$ is
given by

$\displaystyle\beta=\frac{w}{w+1}=\dfrac{(\min_{i\in\mathcal{A}}\gamma_{i})\alpha}{3(\min_{i\in\mathcal{A}}\gamma_{i})\alpha+\alpha+1}=:\beta^{*}.$

This means the optimal exploration probability sequence depends on the
smoothness of the targets and the intrinsic dimensionality of $\mathcal{H}$,
which is controlled by $\alpha$. Clearly, if $\beta>\beta^{*}$, i.e.,
exploitation is favored over exploration, the estimation error dominates the
randomization error and the converse happens when $\beta<\beta^{*}$, i.e.,
exploration is favored over exploitation. Note that for any choice of
$\gamma_{i}$ and $\alpha$, we have $\beta^{*}\leq\frac{1}{5}$, which implies
the growth rate of regret is at least of the order $T^{4/5}$.

Next, in order to compare with the regret rate in Section 7.1 of Chen et al.,
(2021) for the $\epsilon$-greedy strategy, we specialize Theorem 3 to a
finite-dimensional setting. While the randomization error bound can be
obtained similarly as the second term in (18), we modify the bounding for the
cumulative estimation error (see the proof in Section 8.4 for details).

######  Theorem 4.

Suppose $(\mathcal{A}_{1})$, $(\mathcal{A}_{2})$ and $(\mathcal{A}_{5})$ hold,
and $\sup_{\begin{subarray}{c}a,a^{\prime}\in\mathcal{A}\\\ a\neq
a^{\prime}\end{subarray}}\|f_{a}-f_{a^{\prime}}\|_{\mathcal{H}}<\infty$. For
any $\delta>0$, suppose $\\{\epsilon_{s}\\}^{T}_{s=1}$ satisfies

$\frac{1}{t^{2}}\sum^{t}_{s=1}\frac{1}{\epsilon_{s}}\leq\frac{\delta\eta}{4L(L-1)d\kappa}$

for all $0<t\leq T$, where $d:=\emph{dim}(\mathcal{H})$. Then, for any
$\delta>0$, $1\leq p\leq\infty$, $T\geq 1$, and

$\displaystyle\lambda_{i,t}=\left[\dfrac{L}{\delta
t^{2}}\left(\sum_{s=1}^{t}\dfrac{1}{\epsilon_{s}}\right)\right]^{1/2},\,\,i\in\\{1,\ldots,L\\},\,\,0<t\leq
T,$

the following holds with probability at least $1-2\delta$:

$\displaystyle R_{T}$ $\displaystyle\leq
8\kappa\max\\{\tilde{C}_{0},\tilde{C}_{*}\\}\sum_{t=1}^{T}\left[\dfrac{L}{\delta
t^{2}}\Big{(}\sum_{s=1}^{t}\dfrac{1}{\epsilon_{s}}\Big{)}\right]^{1/2}$
$\displaystyle\quad+\kappa
T^{1-\frac{1}{p}}\left[\sum_{t=1}^{T}\dfrac{\epsilon_{t}}{L-1}+\left\\{\dfrac{1}{\delta}\sum_{t=1}^{T}\dfrac{\epsilon_{t}}{L-1}\right\\}^{1/2}\right]^{1/p}\sup_{\begin{subarray}{c}a,a^{\prime}\in\mathcal{A}\\\
a\neq a^{\prime}\end{subarray}}\|f_{a}-f_{a^{\prime}}\|_{\mathcal{H}},$ (20)

where $\tilde{C}_{0}=\sqrt{\frac{(L-1)d\sigma^{2}}{\eta}}$ and
$\tilde{C}_{*}=\max_{1\leq i\leq L}\frac{\|f_{i}\|_{\mathcal{H}}}{\eta}$.

######  Remark 3.

As in Remark 2, the choice of $\epsilon_{t}=t^{-\beta}$ for some $0<\beta<1$
reduces (20) to

$\displaystyle R_{T}\lesssim T^{\frac{\beta+1}{2}}+T^{1-\beta},$

Balancing these terms yields that $R_{T}$ has a growth order of at least
$T^{2/3}$ with the choice of $\beta=\frac{1}{3}$. Note that the estimation
error (resp. randomization error) dominates the randomization error (resp.
estimation error) if $\beta>\frac{1}{3}$ (resp. $\beta<\frac{1}{3}$). We would
like to highlight that this rate of $T^{2/3}$ is optimal for contextual
bandits using an $\epsilon$-greedy strategy, i.e., this strategy cannot
achieve regret rates slower than $T^{2/3}$ for contextual bandits (Dann et
al.,, 2022, Theorem 3).

###  5.1 Regret analysis with the margin condition

In this section, we make an additional assumption known as the ‘margin
condition’ on the underlying reward functions as is commonly assumed in the
contextual bandit’s literature (Chen et al.,, 2021; Goldenshluger and Zeevi,,
2013). Under this assumption, we can achieve significant improvement in the
expected regret rate as compared to the previous results. Note that, here we
construct regret upper bounds in expectation unlike the previous results in
Section 5 where we constructed upper bounds on the regret in probability. As
in the literature, we focus our analysis on $L=2$ (two arms) though it can be
extended to $L$ arms.

######  $(\mathcal{A}_{6})$.

Margin Condition: There exists $C>0$ such that
$P_{X\sim\mathcal{P}_{X}}\left(0<|\langle
f_{1}-f_{0},k(\cdot,X)\rangle_{\mathcal{H}}|\leq l\right)\leq Cl,\,\,\forall
l>0.$

The assumption is related to the behavior of the distribution of the
covariates near the decision boundary $\\{x:f_{1}(x)=f_{0}(x)\\}$. As it is
difficult to distinguish between the arms near the boundary, imposing such an
assumption helps to control the contribution of incorrect decisions being made
near the decision boundary. In the following theorem, we present an upper
bound on the expected regret for the kernel $\epsilon$-greedy algorithm when
the true mean reward functions lie in an RKHS $\mathcal{H}$.

######  Theorem 5.

Let $L=2$. Suppose $(\mathcal{A}_{1})$–$(\mathcal{A}_{4})$ and
$(\mathcal{A}_{6})$ hold with $\gamma_{0}=\gamma_{1}=\gamma$,
$\|f_{1}-f_{0}\|_{\mathcal{H}}<\infty$ and $\\{\epsilon_{s}\\}^{T}_{s=1}$ is
such that for $\delta>0$, and $T\geq 1$,

$\displaystyle\lambda_{t}=\left[\dfrac{1}{\delta
t^{2}}\left(\sum_{s=1}^{t}\dfrac{1}{\epsilon_{s}}\right)\right]^{\alpha/(2\gamma\alpha+\alpha+1)},\,\,0<t\leq
T,$

satisfies

$\lambda_{t}\geq\left[\dfrac{4(L-1)\kappa A_{1}(\bar{C},\alpha)}{\delta
t^{2}}\left(\sum_{s=1}^{t}\dfrac{1}{\epsilon_{s}}\right)\right]^{\alpha/(1+\alpha)},\,\,0<t\leq
T.$

Then, for $T\geq 1$, $\theta>0$, and
$0\leq\zeta<(\gamma\alpha+\alpha+1)/\gamma\alpha$, the following holds:

$\displaystyle\mathbb{E}R_{T}$
$\displaystyle\leq\kappa\|f_{1}-f_{0}\|_{\mathcal{H}}\sum_{t=1}^{T}\dfrac{\epsilon_{t}}{2}$
$\displaystyle\quad\quad+A_{0}(\zeta,\kappa,C_{0},C,C_{*},\gamma,\alpha)\left[T^{-\theta}\sum_{t=1}^{T}\left(\dfrac{1}{t^{2}}\sum_{s=1}^{t}\dfrac{1}{\epsilon_{s}}\right)^{w}+T^{\theta\zeta}\sum_{t=1}^{T}\left(\dfrac{1}{t^{2}}\sum_{s=1}^{t}\dfrac{1}{\epsilon_{s}}\right)^{w(1+\zeta)}\right],$
(21)

where $A_{0}(\zeta,\kappa,C_{0},C,C_{*},\gamma,\alpha)$ is a constant that
depends only on its arguments and not on $T$ and $\\{\epsilon_{s}\\}_{s}$,
$w=\alpha\gamma/(2\alpha\gamma+\alpha+1)$, $C_{*}=\max_{1\leq i\leq
L}\|\Sigma^{-\gamma_{i}}f_{i}\|_{\mathcal{H}}$, $C_{0}$ and
$A_{1}(\bar{C},\alpha)$ are defined in Theorem 1, and $C$ is defined in
$(\mathcal{A}_{6})$.

######  Remark 4.

As in Remark 2, the choice of $\epsilon_{t}=t^{-\beta}$ for some $0<\beta<1$
and $0\leq\zeta<(1-w)/w$ for $w=\alpha\gamma/(2\alpha\gamma+\alpha+1)$,
reduces (21) to

$\displaystyle\mathbb{E}R_{T}\lesssim\underbrace{T^{1-\beta}}_{\rm
I}+\underbrace{T^{-\theta+(\beta-1)w+1}}_{\rm
II}+\underbrace{T^{{(\beta-1)(1+\zeta)w}+\theta\zeta+1}}_{\rm III}.$

To get the final rate, we first balance ${\rm II}$ and ${\rm III}$, and then
balance the resulting rate and ${\rm I}$. Note that $\rm II$ is decreasing in
$\theta$ while $\rm III$ is increasing in $\theta$, and they are balanced when

$\theta=\Big{(}\frac{\zeta}{1+\zeta}\Big{)}w(1-\beta),$

resulting in

${\rm{IV}}:={\rm{II}}+{\rm{III}}=T^{(\beta-1)w\frac{(1+2\zeta)}{(1+\zeta)}+1}.$

Clearly, $\rm{IV}$ and $\rm{I}$ are increasing and decreasing functions of
$\beta$ for $0<\beta<1$, respectively, which are balanced when

$\displaystyle\zeta=\frac{\beta-(1-\beta)w}{2w(1-\beta)-\beta}.$

For $\zeta$ to satisfy

$\displaystyle 0\leq\zeta<\dfrac{1-w}{w},$

we need the condition

$\displaystyle\dfrac{w}{w+1}\leq\beta<\dfrac{2w}{2w+1}.$

Therefore, $\epsilon$-greedy algorithm achieves
$\mathbb{E}R_{T}=O(T^{1-\beta})$ as $T\rightarrow\infty$ for
$w/(w+1)\leq\beta<2w/(2w+1)$. This means the best regret rate that we can
achieve is $T^{\frac{2}{3}+\varepsilon}$ for any $\varepsilon>0$ when
$\gamma=\frac{1}{2}$ and $\alpha\rightarrow\infty$ with the exploration
sequence being chosen to satisfy
$\epsilon_{t}=t^{-\beta},\frac{1}{5}\leq\beta<\frac{1}{3}$. In contrast to
Remark 2 where the regret rate is at least $T^{4/5}$, the margin condition in
$(\mathcal{A}_{6})$ improves the best rate to $T^{\frac{2}{3}+\varepsilon}$,
$\varepsilon>0$.

Next, we bound the expected cumulative regret in the finite-dimensional case
and show it is almost minimax optimal.

######  Theorem 6.

Let $L=2$. Suppose $(\mathcal{A}_{1})$, $(\mathcal{A}_{2})$,
$(\mathcal{A}_{5})$, and $(\mathcal{A}_{6})$ hold,
$\|f_{1}-f_{0}\|_{\mathcal{H}}<\infty$, and for any $\delta>0$, $T\geq 1$,
$\\{\epsilon_{s}\\}^{T}_{s=1}$ satisfies

$\frac{1}{t^{2}}\sum^{t}_{s=1}\frac{1}{\epsilon_{s}}\leq\frac{\delta\eta}{4(L-1)d\kappa},\,\,0<t\leq
T,$

where $d:=\emph{dim}(\mathcal{H})$. Then for $\delta>0$, $T\geq 1$,
$\theta>0$, $0\leq\zeta<1$, and

$\displaystyle\lambda_{t}=\left[\dfrac{1}{\delta
t^{2}}\left(\sum_{s=1}^{t}\dfrac{1}{\epsilon_{s}}\right)\right]^{1/2},\,\,0<t\leq
T,$ (22)

the following holds:

$\displaystyle\mathbb{E}R_{T}$
$\displaystyle\leq\kappa\|f_{1}-f_{0}\|_{\mathcal{H}}\sum_{t=1}^{T}\dfrac{\epsilon_{t}}{2}$
$\displaystyle\qquad+\tilde{A}(\zeta,\kappa,\tilde{C}_{0},C,\tilde{C}_{*})\left[T^{-\theta}\sum_{t=1}^{T}\left[\dfrac{1}{t^{2}}\sum_{s=1}^{t}\dfrac{1}{\epsilon_{s}}\right]^{1/2}+T^{\theta\zeta}\sum_{t=1}^{T}\left(\dfrac{1}{t^{2}}\sum_{s=1}^{t}\dfrac{1}{\epsilon_{s}}\right)^{(1+\zeta)/2}\right],$
(23)

where $\tilde{A}(\zeta,\kappa,\tilde{C}_{0},C,\tilde{C}_{*})$ is a constant
that depends only on its arguments and not on $T$ and
$\\{\epsilon_{s}\\}_{s}$, $\tilde{C}_{0}$, and $\tilde{C}_{*}$ are defined in
Theorem 4, and $C$ is defined in $(\mathcal{A}_{6})$.

######  Remark 5.

The choice of $\epsilon_{t}=t^{-\beta}$ for some $0<\beta<1$ and
$0\leq\zeta<1$, reduces (23) to

$\displaystyle\mathbb{E}R_{T}\lesssim
T^{1-\beta}+T^{-\theta+\frac{\beta+1}{2}}+T^{\frac{(\beta-1)(1+\zeta)}{2}+\theta\zeta+1}.$
(24)

Similar to Remark 4, we first balance the second and the third term in (24),
and then balance the resulting rate with the first term in (24). As a result
we obtain $\mathbb{E}R_{T}={O}(T^{1-\beta})$ where
$\frac{3}{7}\leq\beta<\frac{1}{2}$. Therefore, the best regret we can achieve
in the setting of Theorem 6 is $T^{\frac{1}{2}+\varepsilon}$, $\varepsilon>0$,
which is almost minimax optimal with $T^{1/2}$ being the minimax optimal rate
for linear contextual bandits (Chen et al.,, 2021).

##  6 Numerical experiments

In this section, we compare the performance of the proposed kernel
$\epsilon$-greedy strategy with other contextual bandit algorithms through
numerical experiments. We use a Gaussian kernel parameterized by $\gamma>0$,
i.e.,

$K(x,x^{\prime})=\exp\left(-\gamma^{2}\|x-x^{\prime}\|^{2}\right),$

for the kernel bandit algorithms. We compare the following four strategies
(with parameters defined the parentheses to be tuned and selected) based on
the cumulative regret incurred until time horizon $T=1000$:

  1. 1.

Kernel $\epsilon$-greedy algorithm with Gaussian kernel (regularization
parameter $\lambda_{t}$, length-scale parameter $\gamma$)

  2. 2.

    1. (a)

Kernel $\epsilon$-greedy algorithm with linear kernel using the choice of
$\lambda_{t}$ as in Theorem 2,

    2. (b)

Weighted linear $\epsilon$-greedy algorithm of Chen et al., (2021) with ridge
regression estimator and regularization parameter $\lambda_{t}$ as in Theorem
2,

  3. 3.

Weighted linear $\epsilon$-greedy algorithm of Chen et al., (2021) (i.e.,
without regularization),

  4. 4.

Kernel Upper Confidence Bound (Kernel UCB) algorithm of Valko et al., (2013)
with Gaussian kernel (exploration parameter $\tau$, regularization parameter
$\lambda_{t}$, length-scale parameter $\gamma$).

Note that 2(a) and 2(b) are essentially the same algorithm since our estimator
(3.2) with a linear kernel is just a dual representation of the ridge
regression version of the weighted linear $\epsilon$-greedy estimator of Chen
et al., (2021). This is also reflected in the regret curves in Figures
1(b),(d) and Figure 2(a),(b). For all the $\epsilon$-greedy based algorithms
(1-3), we choose the exploration probability sequence
$\epsilon_{t}=\max\\{\frac{t^{-1/2}\log{(t)}}{10},0.02\\}$, which is the same
choice as used by Chen et al., (2021) in their simulation setup. For
algorithms 1 and 4, i.e., the kernel $\epsilon$-greedy and kernel UCB with
Gaussian kernel, we do cross-validation as described in Section 6.1 to
determine the right choice of the parameters in the parentheses.

We consider four simulated data experiments for $d$-dimensional context space
for $d\in\\{1,2,3\\}$ and for $L=2$ arms. All algorithms are run until the
time horizon $T=1000$ with initial random exploration time, $t_{0}=50$. For
the initialization phase until $t_{0}=50$, we randomly assign both arms 25
times each. In Figures 1(b), 1(d) and Figures 2(a), 2(b), we plot the average
cumulative regret (averaged over 25 runs) over time for the four strategies.
It can be seen that in all four settings, the kernel $\epsilon$-greedy with
Gaussian kernel outperforms the linear strategies by significantly reducing
the regret incurred.

Setting 1: We let $d=1$ and sample
$X_{t}\overset{\text{i.i.d.}}{\sim}\text{Unif}(-1,1)$ for $t=1,\ldots,T$. The
mean reward functions considered are: $f_{1}(x)=\sin(\pi x)$ and
$f_{2}(x)=\cos(\pi x)$ for $-1<x<1$ as in Figure 1(a). In Figure 1(b), note
that kernel UCB performs the poorest amongst all four strategies while kernel
$\epsilon$-greedy performs the best.

Setting 2: We consider a ‘chessboard’ like setup (see Figure 1(c)) similar to
the experimental setup of Zenati et al., (2022), where $d=2$, and the mean
reward functions are $f_{1}(x)=1$ and $f_{2}(x)=1$ in the green and red
regions, respectively, and $0$ elsewhere. Here, we sample each component of
the covariates $X_{t}\in\mathbb{R}^{2},t=1,\ldots,T$ independently from
Unif(-1,1) distribution. Note that, in Figure 1(d), kernel UCB and kernel
$\epsilon$-greedy perform better than the weighted $\epsilon$-greedy linear
algorithms. Both these algorithms give comparable performance with the former
being slightly better.

Settings 3 and 4: We consider two arms, $L=2$, and covariate dimension, $d=3$.
For both these settings, we follow the data generation process of Chen et al.,
(2021), wherein the covariates $X_{t}$ are sampled i.i.d. from a truncated
normal distribution supported on $[-10,10]$ with mean zero and scale parameter
one. In Setting 3, we use a discretized version of the ‘Bump’ synthetic
environment as in the experimental setup of Zenati et al., (2022). The rewards
are generated using the functions, $f_{a}(x)=\max(0,1-\|a-a^{*}\|_{1}-\langle
w^{*},x-x^{*}\rangle_{2}),a=1,2$ for some fixed $a^{*},x^{*}$ and $w^{*}$. We
fix $a^{*}=2$ and randomly generate $d$-dimensional vectors $x^{*}$ and
$w^{*}$. In Setting 4, we consider the following function:
$f_{a}(x)=I\\{\|x-a+0.5\|_{1}<4\\}+0.5I\\{\|x-(a-1)\|_{1}<4\\}$ for $a=1,2$.
For setting 3, as can be seen in Figure 2(a), both kernel UCB and kernel
$\epsilon$-greedy perform at par with each other and result in significantly
lower regret than the linear algorithms. For setting 4 as can be seen in
Figure 2(b), kernel $\epsilon$-greedy performs better than the kernel UCB
algorithm and significantly outperforms the linear algorithms.

|
---|---
(a) Setting 1: Mean Reward functions | (b) Average cumulative regret over time
|
(c) Setting 2: Mean reward functions | (d) Average cumulative regret over time.
Figure 1: Left: Mean reward functions for settings 1 and 2. Right: Average cumulative regret over 25 runs for the five strategies over time for $T=1000$. |
---|---
(a) Setting 3: Average cumulative regret | (b) Setting 4: Average cumulative regret
Figure 2: Average cumulative regret over time for kernel $\epsilon$-greedy
algorithm with Gaussian kernel, linear kernel (with and without
regularization), and kernel UCB with Gaussian kernel.

###  6.1 Choice of kernel parameters

In this section, we describe the methodology we use to tune and select the
parameters in the proposed kernel $\epsilon$-greedy algorithm and the kernel
UCB algorithm of Valko et al., (2013). Note that for the kernel
$\epsilon$-greedy algorithm with Gaussian kernel, we need to tune two
parameters, $\lambda_{t}$ and $\gamma$, while for the kernel UCB algorithm, we
need to tune three parameters, $\lambda$, $\gamma$, and the exploration
parameter, $\tau$. Below, we describe the steps for tuning the two parameters
in the former, while the same methodology is used to tune the three parameters
in the latter.

For selecting the two parameters $\gamma$ and $\lambda$ in implementing the
kernel $\epsilon$-greedy algorithm (corresponding to the purple line in
Figures 1(b),(d) and Figure 2), we use the following cross-validation
approach. We consider the following choices for $\lambda_{t}$ and $\gamma$,
respectively:

$\displaystyle\lambda_{t}$ $\displaystyle\in\left\\{\frac{t^{-1/2}}{\sqrt{\log
t}},\frac{t^{-1/4}}{\sqrt{\log t}},\frac{t^{-1/6}}{\sqrt{\log
t}},\frac{t^{-1/8}}{\sqrt{\log t}},\frac{t^{-1/16}}{\sqrt{(}\log t)},5\times
10^{-5},0.005,0.5\right\\},\,\,\text{and}$ $\displaystyle\gamma$
$\displaystyle\in\\{0.1,0.3,0.5,\ldots,5\\}.$

Then, we use the following $k$-fold cross-validation approach with $k=10$:

  1. 1.

Sample $X\in\mathbb{R}^{T(k+1)\times d}$.

  2. 2.

Split this data into $(k+1)$ subsets, each of size $T$. First $k$ subsets are
used as training datasets and the $(k+1)$th dataset is used as the test data.

  3. 3.

For each pair of $(\lambda_{t},\gamma)$, run the algorithms independently on
each of the training sets (first $k$ subsets) and note the regret incurred.
Take the average cumulative regret across all the $k$ subsets.

  4. 4.

Choose $(\lambda_{t}^{*},\gamma^{*})$ that minimized the average regret at
time $T$.

  5. 5.

Run the kernel $\epsilon$-greedy algorithm using the Gaussian kernel with
length-scale $\gamma^{*}$ and regularization parameter $\lambda_{t}^{*}$ on
the test dataset and repeat the experiment on this dataset 25 times. The
results reported in Figures 1(b),(d) and 2(a),(b) are the averages of the
cumulative regret over these 25 runs.

For Kernel UCB, we follow the same cross-validation approach but with the
following grid choices for $\lambda,\gamma$ and $\tau$:

$\displaystyle\lambda$
$\displaystyle\in\\{0.05,0.15,0.25,\ldots,5\\},\,\,\gamma\in\\{0.5,1.5,2.5,\ldots,15\\},\text{and}\,\,\tau\in\\{0.05,0.1,0.15,\ldots,0.9\\},$

where it has to be noted that Kernel UCB uses $\lambda$ that does not vary
with time (as suggested in Valko et al.,, 2013) in contrast to ours which is
time dependent.

For cases where a linear approximation would lead to a good classification of
arms, our algorithm still performs on par with the linear algorithms. However
if one knows that the true model is linear, it might be computationally
efficient to opt for the linear $\epsilon$-greedy algorithm. If that is not
the case, we can say that using the kernel $\epsilon$\- greedy can be
beneficial in most settings with the right choice of kernel.

##  7 Discussion

In this work, we proposes the kernel $\epsilon$-greedy algorithm for
contextual bandit problems with finitely many arms. We provided upper bounds
on the estimation error for the proposed online regression estimator and
provided sub-linear regret rates for the proposed algorithm. While, the
kernelized versions of UCB and Thompson sampling have been well-studied, to
our knowledge this is the first attempt at studying kernelized
$\epsilon$-greedy algorithm. The theoretical analysis presented is novel, as
it utilizes the intrinsic properties of the RKHS and exploits the simplicity
of the $\epsilon$-greedy algorithm, resulting in upper bounds that do not
depend on quantities like the maximum information gain like previous works. An
advantage of the analysis is that we achieve sub-linear regret bounds for wide
choices of kernels, along with achieving state-of-the-art regret bounds in a
finite-dimensional setting, even when the regressors are not linear. Simple
strategies like $\epsilon$-greedy are easy to implement and deeper theoretical
understanding helps in supporting their application in real-life sequential
decision-making problems. From a practical point of view, addressing
computational challenges in implementing the $\epsilon$-greedy algorithm needs
further research. One way to address time and computational complexity would
be by using incremental Nystr̈om approximations as done by Zenati et al.,
(2022). While we employ cross-validation to tune for the kernel parameters and
regularization parameters, it can be time-consuming to do an exhaustive
search. Therefore, new computational techniques need to be devised to help
with parameter tuning. Another possible future direction is to study the
effect of delayed feedback on the kernel $\epsilon$-greedy strategy, similar
to Vakili et al., (2023). On the theoretical front, though the results
presented in this paper are non-asymptotic, they are based on Chebyshev’s
inequality in separable Hilbert spaces and so they only provide quadratic
concentration. A future direction is to develop sharp Bernstein-type
concentration inequality for operator norm of a self-adjoint Hilbert-Schmidt
operator-valued random element defined on a separable Hilbert space, which
would provide similar results as in this paper but with sub-Gaussian
concentration.

##  8 Proofs

In this section, we present the proofs of the main results of the paper.
Before we present the proofs, we present a result that is used in many of
these proofs.

######  Lemma 1.

$\mathbb{E}(\hat{\Sigma}_{i,t})=\Sigma$, where $\hat{\Sigma}_{i,t}$ is defined
in (5).

###### Proof.

Consider,

$\displaystyle\mathbb{E}(\hat{\Sigma}_{i,t})$
$\displaystyle=\mathbb{E}\left[\dfrac{1}{t}\sum_{s=1}^{t}\dfrac{I\\{\hat{a}_{s}=i\\}}{P(\hat{a}_{s}=i|\mathcal{F}_{s-1},X_{s})}k(\cdot,X_{s})\otimes
k(\cdot,X_{s})\right]$
$\displaystyle=\dfrac{1}{t}\sum_{s=1}^{t}\mathbb{E}\left[\dfrac{I\\{\hat{a}_{s}=i\\}}{P(\hat{a}_{s}=i|\mathcal{F}_{s-1},X_{s})}k(\cdot,X_{s})\otimes
k(\cdot,X_{s})\right]$
$\displaystyle=\dfrac{1}{t}\sum_{s=1}^{t}\mathbb{E}\left[\mathbb{E}\left(\dfrac{I\\{\hat{a}_{s}=i\\}}{P(\hat{a}_{s}=i|\mathcal{F}_{s-1},X_{s})}k(\cdot,X_{s})\otimes
k(\cdot,X_{s})\middle|\mathcal{F}_{s-1},X_{s}\right)\right]$
$\displaystyle=\dfrac{1}{t}\sum_{s=1}^{t}\mathbb{E}\left[\dfrac{P(\hat{a}_{s}=i|\mathcal{F}_{s-1},X_{s})}{P(\hat{a}_{s}=i|\mathcal{F}_{s-1},X_{s})}k(\cdot,X_{s})\otimes
k(\cdot,X_{s})\right]$
$\displaystyle=\dfrac{1}{t}\sum_{s=1}^{t}\mathbb{E}(k(\cdot,X_{s})\otimes
k(\cdot,X_{s}))=\Sigma,\ \text{for}\ i=1,\ldots,L,$

where the third equality follows from the law of iterated expectations. ∎

###  8.1 Proof of Theorem 1

Without loss of generality, we will assume $i=1$. Let
$\hat{\pi}_{s}:=P(\hat{a}_{s}=1|\mathcal{F}_{s-1},X_{s})$. Then,

$\displaystyle\hat{f}_{1,t}-f_{1}$
$\displaystyle=\left(\hat{\Sigma}_{1,t}+\lambda
I\right)^{-1}\dfrac{1}{t}\sum_{s=1}^{t}\dfrac{I\\{\hat{a}_{s}=1\\}}{\hat{\pi}_{s}}k(\cdot,X_{s})y_{s}-f_{1}$
$\displaystyle=\left(\hat{\Sigma}_{1,t}+\lambda
I\right)^{-1}\dfrac{1}{t}\sum_{s=1}^{t}\dfrac{I\\{\hat{a}_{s}=1\\}}{\hat{\pi}_{s}}k(\cdot,X_{s})[\langle
k(\cdot,X_{s}),f_{1}\rangle_{\mathcal{H}}+e_{s}]-f_{1}$
$\displaystyle=\left(\hat{\Sigma}_{1,t}+\lambda I\right)^{-1}\left[-\lambda
f_{1}+\dfrac{1}{t}\sum_{s=1}^{t}\dfrac{I\\{\hat{a}_{s}=1\\}}{\hat{\pi}_{s}}k(\cdot,X_{s})e_{s}\right]$
$\displaystyle=\left(\hat{\Sigma}_{1,t}+\lambda
I\right)^{-1/2}\left(\hat{\Sigma}_{1,t}+\lambda
I\right)^{-1/2}\left({\Sigma}+\lambda I\right)^{1/2}\left({\Sigma}+\lambda
I\right)^{-1/2}$ $\displaystyle\qquad\qquad\times\left[-\lambda
f_{1}+\dfrac{1}{t}\sum_{s=1}^{t}\dfrac{I\\{\hat{a}_{s}=1\\}}{\hat{\pi}_{s}}k(\cdot,X_{s})e_{s}\right].$

This implies that,

$\displaystyle\|\hat{f}_{1,t}-f_{1}\|_{\mathcal{H}}$
$\displaystyle\leq\left\lVert\left(\hat{\Sigma}_{1,t}+\lambda
I\right)^{-1/2}\left(\hat{\Sigma}_{1,t}+\lambda
I\right)^{-1/2}\left({\Sigma}+\lambda I\right)^{1/2}\right\rVert_{\infty}$
$\displaystyle\quad\quad\times\left\|\left({\Sigma}+\lambda
I\right)^{-1/2}\left[-\lambda
f_{1}+\dfrac{1}{t}\sum_{s=1}^{t}\dfrac{I\\{\hat{a}_{s}=1\\}}{\hat{\pi}_{s}}k(\cdot,X_{s})e_{s}\right]\right\|_{\mathcal{H}}$
$\displaystyle\leq\|(\hat{\Sigma}_{1,t}+\lambda
I)^{-1/2}\|_{\infty}\|(\hat{\Sigma}_{1,t}+\lambda I)^{-1/2}(\Sigma+\lambda
I)^{1/2}\|_{\infty}$
$\displaystyle\quad\quad\times\left\|\left({\Sigma}+\lambda
I\right)^{-1/2}\left[-\lambda
f_{1}+\dfrac{1}{t}\sum_{s=1}^{t}\dfrac{I\\{\hat{a}_{s}=1\\}}{\hat{\pi}_{s}}k(\cdot,X_{s})e_{s}\right]\right\|_{\mathcal{H}}\leq\frac{\mathcal{S}_{1}\mathcal{S}_{2}}{\sqrt{\lambda}},$
(25)

where

$\displaystyle\mathcal{S}_{1}$
$\displaystyle:=\left\|\left(\hat{\Sigma}_{1,t}+\lambda
I\right)^{-1/2}\left({\Sigma}+\lambda
I\right)^{1/2}\right\|_{\infty},\,\,\text{and}$ $\displaystyle\mathcal{S}_{2}$
$\displaystyle:=\left\|\left({\Sigma}+\lambda I\right)^{-1/2}\left[-\lambda
f_{1}+\dfrac{1}{t}\sum_{s=1}^{t}\dfrac{I\\{\hat{a}_{s}=1\\}}{\hat{\pi}_{s}}k(\cdot,X_{s})e_{s}\right]\right\|_{\mathcal{H}}.$

We now bound $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$. By defining
$B_{t}:=(\Sigma+\lambda I)^{-1/2}(\Sigma-\hat{\Sigma}_{1,t})(\Sigma+\lambda
I)^{-1/2}$, we have

$\displaystyle\mathcal{S}_{1}=\|(\hat{\Sigma}_{1,t}+\lambda
I)^{-1/2}(\Sigma+\lambda I)^{1/2}\|_{\infty}$ $\displaystyle=\|(\Sigma+\lambda
I)^{1/2}(\hat{\Sigma}_{1,t}+\lambda I)^{-1}(\Sigma+\lambda
I)^{1/2}\|_{\infty}^{1/2}$ $\displaystyle=\|(I-B_{t})^{-1}\|_{\infty}^{1/2}$
$\displaystyle\leq(1-\|B_{t}\|_{\infty})^{-1/2},$

where the last inequality follows from Lemma 3.6 of (Rudi et al., 2013). Note,
$\|B_{t}\|_{\infty}\leq\|B_{t}\|_{HS}$, where $\|\cdot\|_{HS}$ denotes the
Hilbert-Schmidt norm. Using Chebyshev’s inequality we obtain,

$\displaystyle P(\|B_{t}\|_{HS}\geq\epsilon)$
$\displaystyle\leq\dfrac{\mathbb{E}\|B_{t}\|_{HS}^{2}}{\epsilon^{2}}.$

It follows from Lemma 1 that

$\displaystyle\mathbb{E}\|B_{t}\|_{HS}^{2}$
$\displaystyle=\mathbb{E}\|(\Sigma+\lambda
I)^{-1/2}(\hat{\Sigma}_{1,t}-\Sigma)(\Sigma+\lambda I)^{-1/2}\|_{HS}^{2}$
$\displaystyle=\mathbb{E}\|(\Sigma+\lambda
I)^{-1/2}\hat{\Sigma}_{1,t}(\Sigma+\lambda
I)^{-1/2}\|_{HS}^{2}-\|(\Sigma+\lambda I)^{-1/2}\Sigma(\Sigma+\lambda
I)^{-1/2}\|_{HS}^{2}.$ (26)

Define $N_{\Sigma,2}(\lambda):=\|(\Sigma+\lambda
I)^{-1/2}\Sigma(\Sigma+\lambda I)^{-1/2}\|_{HS}^{2}$ and consider,

$\displaystyle\mathbb{E}$ $\displaystyle\|(\Sigma+\lambda
I)^{-1/2}\hat{\Sigma}_{1,t}(\Sigma+\lambda I)^{-1/2}\|_{HS}^{2}$
$\displaystyle=\mathbb{E}\left\langle(\Sigma+\lambda
I)^{-1/2}\hat{\Sigma}_{1,t}(\Sigma+\lambda I)^{-1/2},(\Sigma+\lambda
I)^{-1/2}\hat{\Sigma}_{1,t}(\Sigma+\lambda I)^{-1/2}\right\rangle_{HS}$
$\displaystyle=\mathbb{E}\operatorname{Tr}\left[(\Sigma+\lambda
I)^{-1/2}\hat{\Sigma}_{1,t}(\Sigma+\lambda
I)^{-1}\hat{\Sigma}_{1,t}(\Sigma+\lambda I)^{-1/2}\right]$
$\displaystyle=\mathbb{E}\operatorname{Tr}\left[(\Sigma+\lambda
I)^{-1}\hat{\Sigma}_{1,t}(\Sigma+\lambda I)^{-1}\hat{\Sigma}_{1,t}\right].$

Now, plugging in the definition of $\hat{\Sigma}_{1,t}$ from (5) and defining
$\hat{\tau}_{s}=I\\{\hat{a}_{s}=1\\}/\hat{\pi}_{s}$, we obtain

$\displaystyle\mathbb{E}$ $\displaystyle\|(\Sigma+\lambda
I)^{-1/2}\hat{\Sigma}_{1,t}(\Sigma+\lambda I)^{-1/2}\|_{HS}^{2}$
$\displaystyle=\mathbb{E}\left[\dfrac{1}{t^{2}}\sum_{s=1}^{t}\sum_{\ell=1}^{t}\hat{\tau}_{s}\hat{\tau}_{\ell}\operatorname{Tr}\left((\Sigma+\lambda
I)^{-1}k(\cdot,X_{s})\otimes k(\cdot,X_{s})(\Sigma+\lambda
I)^{-1}k(\cdot,X_{\ell})\otimes k(\cdot,X_{\ell})\right)\right].$

By breaking the double sum in the above expression into the cases when, (1)
$s=\ell$, (2) $s>\ell$, and (3) $s<\ell$, yields

$\displaystyle\mathbb{E}$ $\displaystyle\|(\Sigma+\lambda
I)^{-1/2}\hat{\Sigma}_{1,t}(\Sigma+\lambda I)^{-1/2}\|_{HS}^{2}$
$\displaystyle=\mathbb{E}\left[\dfrac{1}{t^{2}}\sum_{s=1}^{t}\hat{\tau}_{s}^{2}\operatorname{Tr}\left((\Sigma+\lambda
I)^{-1}k(\cdot,X_{s})\otimes k(\cdot,X_{s})(\Sigma+\lambda
I)^{-1}k(\cdot,X_{s})\otimes k(\cdot,X_{s})\right)\right]$
$\displaystyle\quad+\mathbb{E}\left[\dfrac{1}{t^{2}}\sum_{\ell=1}^{t-1}\sum_{s=\ell+1}^{t}\hat{\tau}_{s}\hat{\tau}_{\ell}\operatorname{Tr}\left((\Sigma+\lambda
I)^{-1}k(\cdot,X_{s})\otimes k(\cdot,X_{s})(\Sigma+\lambda
I)^{-1}k(\cdot,X_{\ell})\otimes k(\cdot,X_{\ell})\right)\right]$
$\displaystyle\quad\quad+\mathbb{E}\left[\dfrac{1}{t^{2}}\sum_{\ell=2}^{t}\sum_{s=1}^{\ell-1}\hat{\tau}_{s}\hat{\tau}_{\ell}\operatorname{Tr}\left((\Sigma+\lambda
I)^{-1}k(\cdot,X_{s})\otimes k(\cdot,X_{s})(\Sigma+\lambda
I)^{-1}k(\cdot,X_{\ell})\otimes k(\cdot,X_{\ell})\right)\right]$
$\displaystyle=\leavevmode\hbox to12.54pt{\vbox
to12.54pt{\pgfpicture\makeatletter\hbox{\hskip 6.27202pt\lower-6.27202pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{6.07202pt}{0.0pt}\pgfsys@curveto{6.07202pt}{3.35352pt}{3.35352pt}{6.07202pt}{0.0pt}{6.07202pt}\pgfsys@curveto{-3.35352pt}{6.07202pt}{-6.07202pt}{3.35352pt}{-6.07202pt}{0.0pt}\pgfsys@curveto{-6.07202pt}{-3.35352pt}{-3.35352pt}{-6.07202pt}{0.0pt}{-6.07202pt}\pgfsys@curveto{3.35352pt}{-6.07202pt}{6.07202pt}{-3.35352pt}{6.07202pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.0pt}{-2.57777pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\footnotesize{1}}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}+\leavevmode\hbox
to12.54pt{\vbox to12.54pt{\pgfpicture\makeatletter\hbox{\hskip
6.27202pt\lower-6.27202pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{6.07202pt}{0.0pt}\pgfsys@curveto{6.07202pt}{3.35352pt}{3.35352pt}{6.07202pt}{0.0pt}{6.07202pt}\pgfsys@curveto{-3.35352pt}{6.07202pt}{-6.07202pt}{3.35352pt}{-6.07202pt}{0.0pt}\pgfsys@curveto{-6.07202pt}{-3.35352pt}{-3.35352pt}{-6.07202pt}{0.0pt}{-6.07202pt}\pgfsys@curveto{3.35352pt}{-6.07202pt}{6.07202pt}{-3.35352pt}{6.07202pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.0pt}{-2.57777pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\footnotesize{2}}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}+\leavevmode\hbox
to12.54pt{\vbox to12.54pt{\pgfpicture\makeatletter\hbox{\hskip
6.27202pt\lower-6.27202pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{6.07202pt}{0.0pt}\pgfsys@curveto{6.07202pt}{3.35352pt}{3.35352pt}{6.07202pt}{0.0pt}{6.07202pt}\pgfsys@curveto{-3.35352pt}{6.07202pt}{-6.07202pt}{3.35352pt}{-6.07202pt}{0.0pt}\pgfsys@curveto{-6.07202pt}{-3.35352pt}{-3.35352pt}{-6.07202pt}{0.0pt}{-6.07202pt}\pgfsys@curveto{3.35352pt}{-6.07202pt}{6.07202pt}{-3.35352pt}{6.07202pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.0pt}{-2.57777pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\footnotesize{3}}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}},$ (27)

where we bound 1–3 as follows.

1
$\displaystyle=\dfrac{1}{t^{2}}\sum_{s=1}^{t}\mathbb{E}[\hat{\tau}_{s}^{2}\operatorname{Tr}((\Sigma+\lambda
I)^{-1}k(\cdot,X_{s})\otimes k(\cdot,X_{s})(\Sigma+\lambda
I)^{-1}k(\cdot,X_{s})\otimes k(\cdot,X_{s}))]$
$\displaystyle=\dfrac{1}{t^{2}}\sum_{s=1}^{t}\mathbb{E}\left[\mathbb{E}[\hat{\tau}_{s}^{2}\operatorname{Tr}((\Sigma+\lambda
I)^{-1}k(\cdot,X_{s})\otimes k(\cdot,X_{s})(\Sigma+\lambda
I)^{-1}k(\cdot,X_{s})\otimes
k(\cdot,X_{s}))\middle|\mathcal{F}_{s-1},X_{s}]\right]$
$\displaystyle=\dfrac{1}{t^{2}}\sum_{s=1}^{t}\mathbb{E}\left[\mathbb{E}(\hat{\tau}_{s}^{2}|\mathcal{F}_{s-1},X_{s})\operatorname{Tr}((\Sigma+\lambda
I)^{-1}k(\cdot,X_{s})\otimes k(\cdot,X_{s})(\Sigma+\lambda
I)^{-1}k(\cdot,X_{s})\otimes k(\cdot,X_{s}))\right],$ (28)

where

$\displaystyle\mathbb{E}(\hat{\tau}_{s}^{2}|\mathcal{F}_{s-1},X_{s})$
$\displaystyle=\mathbb{E}\left[\dfrac{I\\{\hat{a}_{s}=1\\}}{\hat{\pi}_{s}^{2}}\middle|\mathcal{F}_{s-1},X_{s}\right]=\dfrac{\hat{\pi}_{s}}{\hat{\pi}_{s}^{2}}=\dfrac{1}{\hat{\pi}_{s}}\leq\dfrac{L-1}{\epsilon_{s}},$

since $1-\epsilon_{s}\geq\frac{\epsilon_{s}}{L-1}$, resulting in

$\displaystyle\eqref{eq: sum1_part1}$
$\displaystyle\leq\dfrac{1}{t^{2}}\sum_{s=1}^{t}\mathbb{E}\left[\dfrac{L-1}{\epsilon_{s}}\operatorname{Tr}\left((\Sigma+\lambda
I)^{-1}k(\cdot,X_{s})\otimes k(\cdot,X_{s})(\Sigma+\lambda
I)^{-1}k(\cdot,X_{s})\otimes k(\cdot,X_{s})\right)\right]$
$\displaystyle\leq\dfrac{1}{t^{2}}\sum_{s=1}^{t}\dfrac{L-1}{\epsilon_{s}}\mathbb{E}\operatorname{Tr}\left((\Sigma+\lambda
I)^{-1}k(\cdot,X_{s})\otimes
k(\cdot,X_{s})\right)\sup_{X_{s}}\|(\Sigma+\lambda
I)^{-1}k(\cdot,X_{s})\otimes k(\cdot,X_{s})\|_{\infty}$
$\displaystyle\leq\dfrac{1}{t^{2}}\sum_{s=1}^{t}\dfrac{L-1}{\epsilon_{s}}\operatorname{Tr}\left((\Sigma+\lambda
I)^{-1}\Sigma\right)\|(\Sigma+\lambda
I)^{-1}\|_{\infty}\sup_{X_{s}}\|k(\cdot,X_{s})\otimes
k(\cdot,X_{s})\|_{\infty}$ (29)
$\displaystyle\leq\dfrac{1}{t^{2}}\left(\sum_{s=1}^{t}\dfrac{L-1}{\epsilon_{s}}\right)N_{\Sigma,1}(\lambda)\dfrac{\kappa}{\lambda},$
(30)

where $N_{\Sigma,1}(\lambda):=\operatorname{Tr}\left((\Sigma+\lambda
I)^{-1}\Sigma\right)$.

2
$\displaystyle=\dfrac{1}{t^{2}}\sum_{\ell=1}^{t-1}\sum_{s=\ell+1}^{t}\mathbb{E}\left[\hat{\tau}_{s}\hat{\tau}_{\ell}\operatorname{Tr}\left((\Sigma+\lambda
I)^{-1}k(\cdot,X_{s})\otimes k(\cdot,X_{s})(\Sigma+\lambda
I)^{-1}k(\cdot,X_{\ell})\otimes k(\cdot,X_{\ell})\right)\right]$
$\displaystyle=\dfrac{1}{t^{2}}\sum_{\ell=1}^{t-1}\sum_{s=\ell+1}^{t}\mathbb{E}\left[\mathbb{E}[\hat{\tau}_{s}\hat{\tau}_{\ell}\operatorname{Tr}\left((\Sigma+\lambda
I)^{-1}k(\cdot,X_{s})\otimes k(\cdot,X_{s})(\Sigma+\lambda
I)^{-1}\right.\right.$ $\displaystyle\qquad\qquad\qquad\left.\left.\times
k(\cdot,X_{\ell})\otimes
k(\cdot,X_{\ell})\right)\middle|\mathcal{F}_{s-1},X_{s}]\right]$
$\displaystyle\stackrel{{\scriptstyle(\dagger)}}{{=}}\dfrac{1}{t^{2}}\sum_{\ell=1}^{t-1}\sum_{s=\ell+1}^{t}\mathbb{E}\left[\hat{\tau}_{\ell}\mathbb{E}(\hat{\tau}_{s}|\mathcal{F}_{s-1},X_{s})\operatorname{Tr}\left((\Sigma+\lambda
I)^{-1}k(\cdot,X_{s})\otimes k(\cdot,X_{s})(\Sigma+\lambda
I)^{-1}\right.\right.$ $\displaystyle\qquad\qquad\qquad\left.\left.\times
k(\cdot,X_{\ell})\otimes k(\cdot,X_{\ell})\right)\right]$
$\displaystyle=\dfrac{1}{t^{2}}\sum_{\ell=1}^{t-1}\sum_{s=\ell+1}^{t}\mathbb{E}\left[\hat{\tau}_{\ell}\operatorname{Tr}\left((\Sigma+\lambda
I)^{-1}k(\cdot,X_{s})\otimes k(\cdot,X_{s})(\Sigma+\lambda
I)^{-1}k(\cdot,X_{\ell})\otimes k(\cdot,X_{\ell})\right)\right],$ (31)

where we used

$\displaystyle\mathbb{E}(\hat{\tau}_{s}|\mathcal{F}_{s-1},X_{s})$
$\displaystyle=\mathbb{E}\left[\dfrac{I\\{\hat{a}_{s}=1\\}}{\hat{\pi}_{s}}\Big{|}\mathcal{F}_{s-1},X_{s}\right]=1$
(32)

in $(\dagger)$. Now using the law of iterated expectation, we obtain

$\displaystyle\eqref{Eq:11}$
$\displaystyle=\dfrac{1}{t^{2}}\sum_{\ell=1}^{t-1}\mathbb{E}\left[\sum_{s=\ell+1}^{t}\mathbb{E}[\hat{\tau}_{\ell}\operatorname{Tr}\left((\Sigma+\lambda
I)^{-1}k(\cdot,X_{s})\otimes k(\cdot,X_{s})(\Sigma+\lambda
I)^{-1}k(\cdot,X_{\ell})\otimes
k(\cdot,X_{\ell})\right)|\mathcal{F}_{\ell}]\right]$
$\displaystyle=\dfrac{1}{t^{2}}\sum_{\ell=1}^{t-1}\mathbb{E}\left[\hat{\tau}_{\ell}\operatorname{Tr}\Big{(}(\Sigma+\lambda
I)^{-1}\Big{(}\sum_{s=\ell+1}^{t}\mathbb{E}(k(\cdot,X_{s})\otimes
k(\cdot,X_{s})|\mathcal{F}_{\ell})\Big{)}(\Sigma+\lambda I)^{-1}\right.$
$\displaystyle\qquad\qquad\qquad\left.\times k(\cdot,X_{\ell})\otimes
k(\cdot,X_{\ell})\Big{)}\right]$
$\displaystyle=\dfrac{1}{t^{2}}\sum_{\ell=1}^{t-1}\mathbb{E}\left[\hat{\tau}_{\ell}\operatorname{Tr}\Big{(}(\Sigma+\lambda
I)^{-1}(t-\ell)\Sigma(\Sigma+\lambda I)^{-1}k(\cdot,X_{\ell})\otimes
k(\cdot,X_{\ell})\Big{)}\right]$
$\displaystyle=\dfrac{1}{t^{2}}\sum_{\ell=1}^{t-1}(t-\ell)\mathbb{E}\left[\hat{\tau}_{\ell}\operatorname{Tr}\Big{(}(\Sigma+\lambda
I)^{-1}\Sigma(\Sigma+\lambda I)^{-1}k(\cdot,X_{\ell})\otimes
k(\cdot,X_{\ell})\Big{)}\right]$
$\displaystyle=\dfrac{1}{t^{2}}\sum_{\ell=1}^{t-1}(t-\ell)\mathbb{E}\left[\mathbb{E}\Big{[}\hat{\tau}_{\ell}\operatorname{Tr}\Big{(}(\Sigma+\lambda
I)^{-1}\Sigma(\Sigma+\lambda I)^{-1}k(\cdot,X_{\ell})\otimes
k(\cdot,X_{\ell})\Big{)}\middle|\mathcal{F}_{\ell-1},X_{\ell}\Big{]}\right]$
$\displaystyle=\dfrac{1}{t^{2}}\sum_{\ell=1}^{t-1}(t-\ell)\mathbb{E}\left[\mathbb{E}(\hat{\tau}_{\ell}|\mathcal{F}_{\ell-1},X_{\ell})\operatorname{Tr}\left((\Sigma+\lambda
I)^{-1}\Sigma(\Sigma+\lambda I)^{-1}k(\cdot,X_{\ell})\otimes
k(\cdot,X_{\ell})\right)\right].$ (33)

Again, using (32), we get

$\displaystyle\eqref{Eq:12}$
$\displaystyle=\dfrac{1}{t^{2}}\sum_{\ell=1}^{t-1}(t-\ell)\mathbb{E}\left[\operatorname{Tr}\left((\Sigma+\lambda
I)^{-1}\Sigma(\Sigma+\lambda I)^{-1}k(\cdot,X_{\ell})\otimes
k(\cdot,X_{\ell})\right)\right]$
$\displaystyle=\dfrac{1}{t^{2}}\sum_{\ell=1}^{t-1}(t-\ell)\left[\operatorname{Tr}\left((\Sigma+\lambda
I)^{-1}\Sigma(\Sigma+\lambda I)^{-1}\Sigma\right)\right]$
$\displaystyle=\dfrac{1}{t^{2}}\sum_{\ell=1}^{t-1}(t-\ell)N_{\Sigma,2}(\lambda)=\dfrac{1}{t^{2}}\left[t(t-1)-\dfrac{(t-1)t}{2}\right]N_{\Sigma,2}(\lambda)$
$\displaystyle=\dfrac{N_{\Sigma,2}(\lambda)}{2}-\dfrac{N_{\Sigma,2}(\lambda)}{2t}.$
(34) 3
$\displaystyle=\dfrac{1}{t^{2}}\sum_{\ell=2}^{t}\sum_{s=1}^{\ell-1}\mathbb{E}\left[\hat{\tau}_{s}\hat{\tau}_{\ell}\operatorname{Tr}\left((\Sigma+\lambda
I)^{-1}k(\cdot,X_{s})\otimes k(\cdot,X_{s})(\Sigma+\lambda
I)^{-1}k(\cdot,X_{\ell})\otimes k(\cdot,X_{\ell})\right)\right]$
$\displaystyle=\dfrac{1}{t^{2}}\sum_{\ell=2}^{t}\sum_{s=1}^{\ell-1}\mathbb{E}\left[\mathbb{E}[\hat{\tau}_{s}\hat{\tau}_{\ell}\operatorname{Tr}\left((\Sigma+\lambda
I)^{-1}k(\cdot,X_{s})\otimes k(\cdot,X_{s})(\Sigma+\lambda
I)^{-1}\right.\right.$ $\displaystyle\qquad\qquad\left.\left.\times
k(\cdot,X_{\ell})\otimes
k(\cdot,X_{\ell})\right)\middle|\mathcal{F}_{\ell-1},X_{\ell}]\right]$
$\displaystyle=\dfrac{1}{t^{2}}\sum_{\ell=2}^{t}\sum_{s=1}^{\ell-1}\mathbb{E}\left[\hat{\tau}_{s}\mathbb{E}(\hat{\tau}_{\ell}|\mathcal{F}_{\ell-1},X_{\ell})\operatorname{Tr}\left((\Sigma+\lambda
I)^{-1}k(\cdot,X_{s})\otimes k(\cdot,X_{s})(\Sigma+\lambda
I)^{-1}\right.\right.$ $\displaystyle\qquad\qquad\left.\left.\times
k(\cdot,X_{\ell})\otimes k(\cdot,X_{\ell})\right)\right]$
$\displaystyle=\dfrac{1}{t^{2}}\sum_{\ell=2}^{t}\sum_{s=1}^{\ell-1}\mathbb{E}\left[\hat{\tau}_{s}\operatorname{Tr}\left((\Sigma+\lambda
I)^{-1}k(\cdot,X_{s})\otimes k(\cdot,X_{s})(\Sigma+\lambda
I)^{-1}k(\cdot,X_{\ell})\otimes k(\cdot,X_{\ell})\right)\right].$ (35)

Now, using law of iterated expectations, we have

$\displaystyle\eqref{Eq:13}$
$\displaystyle=\dfrac{1}{t^{2}}\sum_{\ell=2}^{t}\sum_{s=1}^{\ell-1}\mathbb{E}\left[\mathbb{E}[\hat{\tau}_{s}\operatorname{Tr}\left((\Sigma+\lambda
I)^{-1}k(\cdot,X_{s})\otimes k(\cdot,X_{s})(\Sigma+\lambda
I)^{-1}k(\cdot,X_{\ell})\otimes
k(\cdot,X_{\ell})\right)\middle|\mathcal{F}_{s}]\right]$
$\displaystyle=\dfrac{1}{t^{2}}\sum_{\ell=2}^{t}\sum_{s=1}^{\ell-1}\mathbb{E}\left[\hat{\tau}_{s}\operatorname{Tr}\left((\Sigma+\lambda
I)^{-1}k(\cdot,X_{s})\otimes k(\cdot,X_{s})(\Sigma+\lambda
I)^{-1}\mathbb{E}[k(\cdot,X_{\ell})\otimes
k(\cdot,X_{\ell})\middle|\mathcal{F}_{s}]\right)\right]$
$\displaystyle=\dfrac{1}{t^{2}}\sum_{\ell=2}^{t}\sum_{s=1}^{\ell-1}\mathbb{E}\left[\mathbb{E}\left(\hat{\tau}_{s}\operatorname{Tr}\left((\Sigma+\lambda
I)^{-1}k(\cdot,X_{s})\otimes k(\cdot,X_{s})(\Sigma+\lambda
I)^{-1}\Sigma\right)|\mathcal{F}_{s-1},X_{s}\right)\right]$
$\displaystyle=\dfrac{1}{t^{2}}\sum_{\ell=2}^{t}\sum_{s=1}^{\ell-1}\mathbb{E}\left[\operatorname{Tr}\left(\mathbb{E}(\hat{\tau}_{s}|\mathcal{F}_{s-1},X_{s})(\Sigma+\lambda
I)^{-1}k(\cdot,X_{s})\otimes k(\cdot,X_{s})(\Sigma+\lambda
I)^{-1}\Sigma\right)\right]$
$\displaystyle=\dfrac{1}{t^{2}}\sum_{\ell=2}^{t}\sum_{s=1}^{\ell-1}\mathbb{E}\left[\operatorname{Tr}\left(\mathbb{E}(\hat{\tau}_{s}|\mathcal{F}_{s-1},X_{s})(\Sigma+\lambda
I)^{-1}k(\cdot,X_{s})\otimes k(\cdot,X_{s})(\Sigma+\lambda
I)^{-1}\Sigma\right)\right]$
$\displaystyle=\dfrac{1}{t^{2}}\sum_{\ell=2}^{t}\sum_{s=1}^{\ell-1}\mathbb{E}\left[\operatorname{Tr}\left((\Sigma+\lambda
I)^{-1}k(\cdot,X_{s})\otimes k(\cdot,X_{s})(\Sigma+\lambda
I)^{-1}\Sigma\right)\right]$
$\displaystyle=\dfrac{1}{t^{2}}\sum_{\ell=2}^{t}(\ell-1)N_{\Sigma,2}(\lambda)=\dfrac{1}{t^{2}}\left[\dfrac{t(t-1)}{2}\right]N_{\Sigma,2}(\lambda)$
$\displaystyle=\dfrac{N_{\Sigma,2}(\lambda)}{2}-\dfrac{N_{\Sigma,2}(\lambda)}{2t}.$
(36)

Putting together (30), (34) and (36) in (27), and the result in (26), we get,

$\displaystyle\mathbb{E}\|B_{t}\|_{HS}^{2}$
$\displaystyle\leq\dfrac{1}{t^{2}}\left(\sum_{s=1}^{t}\dfrac{L-1}{\epsilon_{s}}\right)N_{\Sigma,1}(\lambda)\dfrac{\kappa}{\lambda}+2\left(\dfrac{N_{\Sigma,2}(\lambda)}{2}-\dfrac{1}{2t}N_{\Sigma,2}(\lambda)\right)-N_{\Sigma,2}(\lambda)$
$\displaystyle\leq\dfrac{1}{t^{2}}\left(\sum_{s=1}^{t}\dfrac{L-1}{\epsilon_{s}}\right)N_{\Sigma,1}(\lambda)\dfrac{\kappa}{\lambda}.$
(37)

Using Assumption $(\mathcal{A}_{3})$, we obtain,

$\displaystyle\mathbb{E}\|B_{t}\|_{HS}^{2}$ $\displaystyle\leq
A_{1}(\bar{C},\alpha)\dfrac{\kappa}{t^{2}}\left(\sum_{s=1}^{t}\dfrac{L-1}{\epsilon_{s}}\right)\lambda^{-(1+1/\alpha)},\
\alpha>1,$

where $A_{1}(\bar{C},\alpha)$ is a constant depending only on $\bar{C}$ and
$\alpha$. Therefore,

$\displaystyle P\left(\|B_{t}\|_{HS}\geq\frac{1}{2}\right)$ $\displaystyle\leq
4\mathbb{E}\|B_{t}\|_{HS}^{2}\leq\dfrac{4\kappa}{t^{2}}A_{1}(\bar{C},\alpha)\lambda^{-(1+1/\alpha)}\left(\sum_{s=1}^{t}\dfrac{L-1}{\epsilon_{s}}\right).$

Thus for $\delta>0$, choosing

$\displaystyle\lambda\geq\left[\dfrac{4\kappa
A_{1}(\bar{C},\alpha)}{t^{2}\delta}\left(\sum_{s=1}^{t}\dfrac{L-1}{\epsilon_{s}}\right)\right]^{\alpha/(1+\alpha)},\
\alpha>1,$

yields

$P\left(\|B_{t}\|_{HS}\geq\frac{1}{2}\right)\leq\delta,$

implying that with probability at least $1-\delta$,

$\mathcal{S}_{1}\leq\sqrt{2}.$ (38)

We now bound $\mathcal{S}_{2}$ as

$\displaystyle\mathcal{S}_{2}$ $\displaystyle=\left\|\left({\Sigma}+\lambda
I\right)^{-1/2}\left[-\lambda
f_{1}+\dfrac{1}{t}\sum_{s=1}^{t}\dfrac{I\\{\hat{a}_{s}=1\\}}{\hat{\pi}_{s}}k(\cdot,X_{s})e_{s}\right]\right\|_{\mathcal{H}}$
$\displaystyle\leq\left\|(\Sigma+\lambda
I)^{-1/2}\dfrac{1}{t}\sum_{s=1}^{t}\dfrac{I\\{\hat{a}_{s}=1\\}}{\hat{\pi}_{s}}k(\cdot,X_{s})e_{s}\right\|_{\mathcal{H}}+\lambda\|(\Sigma+\lambda
I)^{-1/2}f_{1}\|_{\mathcal{H}}.$ (39)

For the second term in (39), using Assumption $(\mathcal{A}_{4})$, we have

$\displaystyle\left\|(\Sigma+\lambda I)^{-1/2}f_{1}\right\|_{\mathcal{H}}$
$\displaystyle\leq\left\|(\Sigma+\lambda
I)^{-1/2}\Sigma^{\gamma_{1}}h\right\|_{\mathcal{H}}\leq\left\|(\Sigma+\lambda
I)^{-1/2}\Sigma^{\gamma_{1}}\right\|_{\infty}\|\Sigma^{-\gamma_{1}}f_{1}\|_{\mathcal{H}}$
$\displaystyle\leq\sup_{i}\dfrac{\eta_{i}^{\gamma_{1}}}{(\eta_{i}+\lambda)^{1/2}}\|\Sigma^{-\gamma_{1}}f_{1}\|_{\mathcal{H}}\leq\sup_{x\geq
0}\left[\dfrac{x^{2\gamma_{1}}}{x+\lambda}\right]^{1/2}\|\Sigma^{-\gamma_{1}}f_{1}\|_{\mathcal{H}}$
$\displaystyle\leq\lambda^{\gamma_{1}-\frac{1}{2}}\|\Sigma^{-\gamma_{1}}f_{1}\|_{\mathcal{H}},$
(40)

where the last inequality follows by noting that for $0<\gamma_{1}\leq 1/2$,

$\displaystyle\left(\sup_{x\geq
0}\dfrac{x^{2\gamma_{1}}}{x+\lambda}\right)^{1/2}$
$\displaystyle=\left(\sup_{x\geq
0}\left(\dfrac{x}{x+\lambda}\right)^{2\gamma_{1}}\dfrac{1}{(x+\lambda)^{1-2\gamma_{1}}}\right)^{1/2}\leq\lambda^{\gamma_{1}-\frac{1}{2}}.$

For any $\xi>0$, applying Chebyshev’s inequality to the first term in (39)
yields

$\displaystyle P$ $\displaystyle\left(\left\|(\Sigma+\lambda
I)^{-1/2}\dfrac{1}{t}\sum_{s=1}^{t}\dfrac{I\\{\hat{a}_{s}=1\\}}{\hat{\pi}_{s}}k(\cdot,X_{s})e_{s}\right\|_{\mathcal{H}}\geq\xi\right)$
$\displaystyle\leq\dfrac{1}{\xi^{2}}\mathbb{E}\left\|(\Sigma+\lambda
I)^{-1/2}\dfrac{1}{t}\sum_{s=1}^{t}\dfrac{I\\{\hat{a}_{s}=1\\}}{\hat{\pi}_{s}}k(\cdot,X_{s})e_{s}\right\|_{\mathcal{H}}^{2}$
$\displaystyle=\dfrac{1}{\xi^{2}}\mathbb{E}\left\langle(\Sigma+\lambda
I)^{-1/2}\dfrac{1}{t}\sum_{s=1}^{t}\dfrac{I\\{\hat{a}_{s}=1\\}}{\hat{\pi}_{s}}k(\cdot,X_{s})e_{s},(\Sigma+\lambda
I)^{-1/2}\dfrac{1}{t}\sum_{\ell=1}^{t}\dfrac{I\\{\hat{a}_{\ell}=1\\}}{\hat{\pi}_{\ell}}k(\cdot,X_{\ell})e_{\ell}\right\rangle_{\mathcal{H}}$
$\displaystyle=\dfrac{1}{\xi^{2}}\mathbb{E}\left\langle(\Sigma+\lambda
I)^{-1},\dfrac{1}{t^{2}}\sum_{s=1}^{t}\sum_{\ell=1}^{t}\dfrac{I\\{\hat{a}_{s}=1\\}}{\hat{\pi}_{s}}\dfrac{I\\{\hat{a}_{\ell}=1\\}}{\hat{\pi}_{\ell}}e_{s}e_{\ell}k(\cdot,X_{s})\otimes
k(\cdot,X_{\ell})\right\rangle_{HS}$
$\displaystyle=\dfrac{1}{\xi^{2}}\left\langle(\Sigma+\lambda
I)^{-1},\mathbb{E}\left(\dfrac{1}{t^{2}}\sum_{s=1}^{t}\sum_{\ell=1}^{t}\dfrac{I\\{\hat{a}_{s}=1\\}}{\hat{\pi}_{s}}\dfrac{I\\{\hat{a}_{\ell}=1\\}}{\hat{\pi}_{\ell}}e_{s}e_{\ell}k(\cdot,X_{s})\otimes
k(\cdot,X_{\ell})\right)\right\rangle_{HS}.$ (41)

In the following, we simplify the expectation term in (41) by considering
three cases for the double sum: (1) $\ell=s$, (2) $\ell>s$ and (3) $\ell<s$.
Recall $\hat{\tau}_{s}=I\\{\hat{a}_{s}=1\\}/\hat{\pi}_{s}$, where
$\hat{\pi}_{s}=P(\hat{a}_{s}=1|\mathcal{F}_{s-1},X_{s})$. Consider

$\displaystyle\mathbb{E}$
$\displaystyle\left(\dfrac{1}{t^{2}}\sum_{s=1}^{t}\sum_{\ell=1}^{t}\dfrac{I\\{\hat{a}_{s}=1\\}}{\hat{\pi}_{s}}\dfrac{I\\{\hat{a}_{\ell}=1\\}}{\hat{\pi}_{\ell}}e_{s}e_{\ell}k(\cdot,X_{s})\otimes
k(\cdot,X_{\ell})\right)$
$\displaystyle=\mathbb{E}\left(\dfrac{1}{t^{2}}\sum_{s=1}^{t}\dfrac{I\\{\hat{a}_{s}=1\\}}{\hat{\pi}_{s}^{2}}e_{s}^{2}k(\cdot,X_{s})\otimes
k(\cdot,X_{s})\right)+\mathbb{E}\left(\dfrac{1}{t^{2}}\sum_{\ell=1}^{t-1}\sum_{s=\ell+1}^{t}\hat{\tau}_{s}\hat{\tau}_{\ell}e_{s}e_{\ell}k(\cdot,X_{s})\otimes
k(\cdot,X_{\ell})\right)$
$\displaystyle\quad\quad\quad+\mathbb{E}\left(\dfrac{1}{t^{2}}\sum_{\ell=2}^{t}\sum_{s=1}^{\ell-1}\hat{\tau}_{s}\hat{\tau}_{\ell}e_{s}e_{\ell}k(\cdot,X_{s})\otimes
k(\cdot,X_{\ell})\right)$ $\displaystyle=\leavevmode\hbox to12.54pt{\vbox
to12.54pt{\pgfpicture\makeatletter\hbox{\hskip 6.27202pt\lower-6.27202pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{6.07202pt}{0.0pt}\pgfsys@curveto{6.07202pt}{3.35352pt}{3.35352pt}{6.07202pt}{0.0pt}{6.07202pt}\pgfsys@curveto{-3.35352pt}{6.07202pt}{-6.07202pt}{3.35352pt}{-6.07202pt}{0.0pt}\pgfsys@curveto{-6.07202pt}{-3.35352pt}{-3.35352pt}{-6.07202pt}{0.0pt}{-6.07202pt}\pgfsys@curveto{3.35352pt}{-6.07202pt}{6.07202pt}{-3.35352pt}{6.07202pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.0pt}{-2.57777pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\footnotesize{4}}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}+\leavevmode\hbox
to12.54pt{\vbox to12.54pt{\pgfpicture\makeatletter\hbox{\hskip
6.27202pt\lower-6.27202pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{6.07202pt}{0.0pt}\pgfsys@curveto{6.07202pt}{3.35352pt}{3.35352pt}{6.07202pt}{0.0pt}{6.07202pt}\pgfsys@curveto{-3.35352pt}{6.07202pt}{-6.07202pt}{3.35352pt}{-6.07202pt}{0.0pt}\pgfsys@curveto{-6.07202pt}{-3.35352pt}{-3.35352pt}{-6.07202pt}{0.0pt}{-6.07202pt}\pgfsys@curveto{3.35352pt}{-6.07202pt}{6.07202pt}{-3.35352pt}{6.07202pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.0pt}{-2.57777pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\footnotesize{5}}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}+\leavevmode\hbox
to12.54pt{\vbox to12.54pt{\pgfpicture\makeatletter\hbox{\hskip
6.27202pt\lower-6.27202pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{6.07202pt}{0.0pt}\pgfsys@curveto{6.07202pt}{3.35352pt}{3.35352pt}{6.07202pt}{0.0pt}{6.07202pt}\pgfsys@curveto{-3.35352pt}{6.07202pt}{-6.07202pt}{3.35352pt}{-6.07202pt}{0.0pt}\pgfsys@curveto{-6.07202pt}{-3.35352pt}{-3.35352pt}{-6.07202pt}{0.0pt}{-6.07202pt}\pgfsys@curveto{3.35352pt}{-6.07202pt}{6.07202pt}{-3.35352pt}{6.07202pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.0pt}{-2.57777pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\footnotesize{6}}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}},$

where

4
$\displaystyle=\mathbb{E}\left(\dfrac{1}{t^{2}}\sum_{s=1}^{t}\dfrac{I\\{\hat{a}_{s}=1\\}}{\hat{\pi}_{s}^{2}}e_{s}^{2}k(\cdot,X_{s})\otimes
k(\cdot,X_{s})\right)$
$\displaystyle=\dfrac{1}{t^{2}}\sum_{s=1}^{t}\mathbb{E}\left[\mathbb{E}\left(\dfrac{I\\{\hat{a}_{s}=1\\}}{\hat{\pi}_{s}^{2}}e_{s}^{2}k(\cdot,X_{s})\otimes
k(\cdot,X_{s})\middle|\mathcal{F}_{s-1},X_{s},\hat{a}_{s}\right)\right]$
$\displaystyle=\dfrac{1}{t^{2}}\sum_{s=1}^{t}\mathbb{E}\left[\dfrac{I\\{\hat{a}_{s}=1\\}}{\hat{\pi}_{s}^{2}}k(\cdot,X_{s})\otimes
k(\cdot,X_{s})\mathbb{E}\left(e_{s}^{2}\middle|\mathcal{F}_{s-1},X_{s},\hat{a}_{s}\right)\right]$
$\displaystyle\preceq\dfrac{\sigma^{2}}{t^{2}}\sum_{s=1}^{t}\mathbb{E}\left[\dfrac{I\\{\hat{a}_{s}=1\\}}{\hat{\pi}_{s}^{2}}k(\cdot,X_{s})\otimes
k(\cdot,X_{s})\right]$
$\displaystyle=\dfrac{\sigma^{2}}{t^{2}}\sum_{s=1}^{t}\mathbb{E}\left[\mathbb{E}\Bigg{[}\dfrac{I\\{\hat{a}_{s}=1\\}}{\hat{\pi}_{s}^{2}}k(\cdot,X_{s})\otimes
k(\cdot,X_{s})\middle|\mathcal{F}_{s-1},X_{s}\Bigg{]}\right]$
$\displaystyle=\dfrac{\sigma^{2}}{t^{2}}\sum_{s=1}^{t}\mathbb{E}\left[\dfrac{1}{\hat{\pi}_{s}}k(\cdot,X_{s})\otimes
k(\cdot,X_{s})\right]\preceq\dfrac{\sigma^{2}}{t^{2}}\left(\sum_{s=1}^{t}\dfrac{L-1}{\epsilon_{s}}\right)\Sigma,$
(42)

where the above inequality follows from $(\mathcal{A}_{1})$, and the fact that
$\hat{\pi}_{s}\geq\epsilon_{s}/(L-1)$. To bound 5, define
$D_{s\ell}:=\\{\hat{a}_{s}=\hat{a}_{\ell}=1\\}$. Then the complement of this
event consists of situations when the two arms are not the same or either (or
both) are not arm $1$, i.e., one or both of $\hat{\tau_{s}}$ and
$\hat{\tau_{\ell}}$ will be zero. Therefore,

5
$\displaystyle=\mathbb{E}\left(\dfrac{1}{t^{2}}\sum_{\ell=1}^{t-1}\sum_{s=\ell+1}^{t}\hat{\tau}_{s}\hat{\tau}_{\ell}e_{s}e_{\ell}k(\cdot,X_{s})\otimes
k(\cdot,X_{\ell})\right)$
$\displaystyle=\dfrac{1}{t^{2}}\sum_{\ell=1}^{t-1}\sum_{s=\ell+1}^{t}\mathbb{E}\left[E\left(\hat{\tau}_{s}\hat{\tau}_{\ell}e_{s}e_{\ell}k(\cdot,X_{s})\otimes
k(\cdot,X_{\ell})\middle|\mathcal{F}_{s-1},X_{s},D_{s\ell}\right)\right]$
$\displaystyle=\dfrac{1}{t^{2}}\sum_{\ell=1}^{t-1}\sum_{s=\ell+1}^{t}\mathbb{E}\left[\dfrac{1}{\hat{\pi}_{s}\hat{\pi}_{\ell}}\mathbb{E}(e_{s}e_{\ell}|\mathcal{F}_{s-1},X_{s},D_{s\ell})k(\cdot,X_{s})\otimes
k(\cdot,X_{\ell})\right]$
$\displaystyle=\dfrac{1}{t^{2}}\sum_{\ell=1}^{t-1}\sum_{s=\ell+1}^{t}\mathbb{E}\left[\dfrac{1}{\hat{\pi}_{s}\hat{\pi}_{\ell}}\mathbb{E}(e_{s}|\mathcal{F}_{s-1},X_{s},\hat{a}_{s}=1)\mathbb{E}(e_{\ell}|\mathcal{F}_{s-1},X_{s},\hat{a}_{\ell}=1)k(\cdot,X_{s})\otimes
k(\cdot,X_{\ell})\right]$ (43) $\displaystyle=0,$ (44)

where (43) follows from $(\mathcal{A}_{2})$, i.e., errors and covariates at
time $t$ are independent for a given arm. Similar to 5, we obtain

6
$\displaystyle=\mathbb{E}\left(\dfrac{1}{t^{2}}\sum_{\ell=2}^{t}\sum_{s=1}^{\ell-1}\hat{\tau}_{s}\hat{\tau}_{\ell}e_{s}e_{\ell}k(\cdot,X_{s})\otimes
k(\cdot,X_{\ell})\right)$
$\displaystyle=\dfrac{1}{t^{2}}\sum_{\ell=2}^{t}\sum_{s=1}^{\ell-1}\mathbb{E}\left[E\left(\hat{\tau}_{s}\hat{\tau}_{\ell}e_{s}e_{\ell}k(\cdot,X_{s})\otimes
k(\cdot,X_{\ell})\middle|\mathcal{F}_{\ell-1},X_{\ell},D_{s\ell}\right)\right]$
$\displaystyle=\dfrac{1}{t^{2}}\sum_{\ell=2}^{t}\sum_{s=1}^{\ell-1}\mathbb{E}\left[\dfrac{1}{\hat{\pi}_{s}\hat{\pi}_{\ell}}\mathbb{E}(e_{s}e_{\ell}|\mathcal{F}_{\ell-1},X_{\ell},D_{s\ell})k(\cdot,X_{s})\otimes
k(\cdot,X_{\ell})\right]$
$\displaystyle=\dfrac{1}{t^{2}}\sum_{\ell=2}^{t}\sum_{s=1}^{\ell-1}\mathbb{E}\left[\dfrac{1}{\hat{\pi}_{s}\hat{\pi}_{\ell}}\mathbb{E}(e_{s}|\mathcal{F}_{\ell-1},X_{\ell},\hat{a}_{s}=1)\mathbb{E}(e_{\ell}|\mathcal{F}_{\ell-1},X_{\ell},\hat{a}_{\ell}=1)k(\cdot,X_{s})\otimes
k(\cdot,X_{\ell})\right]$ $\displaystyle=0.$ (45)

Combining (42), (44) and (45) in (41), we obtain

$\displaystyle P\left(\left\|(\Sigma+\lambda
I)^{-1/2}\dfrac{1}{t}\sum_{s=1}^{t}\dfrac{I\\{\hat{a}_{s}=1\\}}{\hat{\pi}_{s}}k(\cdot,X_{s})e_{s}\right\|_{\mathcal{H}}\geq\xi\right)\leq\dfrac{1}{\xi^{2}}\left\langle(\Sigma+\lambda
I)^{-1},\dfrac{\sigma^{2}}{t^{2}}\left(\sum_{s=1}^{t}\dfrac{L-1}{\epsilon_{s}}\right)\Sigma\right\rangle_{HS}$
$\displaystyle=\dfrac{\sigma^{2}}{t^{2}\xi^{2}}\left(\sum_{s=1}^{t}\dfrac{L-1}{\epsilon_{s}}\right)\operatorname{Tr}\left[(\Sigma+\lambda
I)^{-1}\Sigma\right]=\dfrac{\sigma^{2}}{t^{2}\xi^{2}}\left(\sum_{s=1}^{t}\dfrac{L-1}{\epsilon_{s}}\right)N_{\Sigma,1}(\lambda)$
(46)
$\displaystyle\leq\dfrac{\sigma^{2}A_{1}(\bar{C},\alpha)}{t^{2}\xi^{2}}\left(\sum_{s=1}^{t}\dfrac{L-1}{\epsilon_{s}}\right)\lambda^{-1/\alpha},$
(47)

where we used $(\mathcal{A}_{3})$ in the last inequality. Combining (40) and
(47) in (39), and choosing

$\displaystyle\xi=\left[\dfrac{\sigma^{2}A_{1}(\bar{C},\alpha)}{\delta
t^{2}}\left(\sum_{s=1}^{t}\dfrac{L-1}{\epsilon_{s}}\right)\lambda^{-1/\alpha}\right]^{1/2},$

yields that with probability at least $1-\delta$,

$\displaystyle\mathcal{S}_{2}\leq\left[\dfrac{\sigma^{2}A_{1}(\bar{C},\alpha)}{\delta
t^{2}}\left(\sum_{s=1}^{t}\dfrac{L-1}{\epsilon_{s}}\right)\lambda^{-1/\alpha}\right]^{1/2}+\lambda^{\gamma_{1}+\frac{1}{2}}\|\Sigma^{-\gamma_{1}}f_{1}\|_{\mathcal{H}}.$
(48)

Using (38) and (48) in (25) yields that with probability at least $1-2\delta$,
we have

$\displaystyle\|\hat{f}_{1,t}-f_{1}\|_{\mathcal{H}}$
$\displaystyle\leq\left[\dfrac{2\sigma^{2}A_{1}(\bar{C},\alpha)}{\delta
t^{2}}\left(\sum_{s=1}^{t}\dfrac{L-1}{\epsilon_{s}}\right)\lambda^{-(1+1/\alpha)}\right]^{1/2}+\sqrt{2}\lambda^{\gamma_{1}}\|\Sigma^{-\gamma_{1}}f_{1}\|_{\mathcal{H}}$
$\displaystyle\leq\sqrt{2}\max\\{C_{0},C_{1}\\}\left[\left(\dfrac{1}{\delta
t^{2}}\left(\sum_{s=1}^{t}\dfrac{1}{\epsilon_{s}}\right)\lambda^{-(1+1/\alpha)}\right)^{1/2}+\lambda^{\gamma_{1}}\right],$
(49)

where $C_{0}=\sqrt{\sigma^{2}(L-1)A_{1}(\bar{C},\alpha)}$ and
$C_{1}=\|\Sigma^{-\gamma_{1}}f_{1}\|_{\mathcal{H}}$. The result follows by
choosing

$\displaystyle\lambda=\lambda_{1,t}:=\left[\dfrac{1}{\delta
t^{2}}\left(\sum_{s=1}^{t}\dfrac{1}{\epsilon_{s}}\right)\right]^{\alpha/(2\gamma_{1}\alpha+\alpha+1)}$

in (49). Also, the same proof works for all arms $i=1,\ldots,L$, by defining
$\hat{\pi}_{s}=P(\hat{a}_{s}=i|\mathcal{F}_{s-1},X_{s})$.

Next, we derive the bound for the estimation error in expectation. From the
above, note that, for $i=1,\ldots,L$ and any $\delta>0$,

$\displaystyle P(\|\hat{f}_{i,t}-f_{i}\|_{\mathcal{H}}\leq\theta_{t})\geq
1-2\delta,$

where,

$\displaystyle\theta_{t}=2\sqrt{2}\max\\{C_{0},C_{i}\\}\left[\dfrac{1}{\delta
t^{2}}\left(\sum_{s=1}^{t}\dfrac{1}{\epsilon_{s}}\right)\right]^{\gamma_{i}\alpha/(2\gamma_{i}\alpha+\alpha+1)}.$

For any $\theta>0$, the above inequality can be alternately written as

$\displaystyle
P(\|\hat{f}_{i,t}-f_{i}\|_{\mathcal{H}}>\theta)\leq\min\left\\{1,\left(\dfrac{2\sqrt{2}\max\\{C_{0},C_{i}\\}}{\theta}\right)^{\frac{2\gamma_{i}\alpha+\alpha+1}{\gamma_{i}\alpha}}\left[\dfrac{1}{t^{2}}\left(\sum_{s=1}^{t}\dfrac{1}{\epsilon_{s}}\right)\right]\right\\}.$

The expectation result therefore follows by using
$\mathbb{E}(\|\hat{f}_{i,t}-f_{i}\|^{1+\zeta}_{\mathcal{H}})=\int_{0}^{\infty}P(\|\hat{f}_{i,t}-f_{i}\|_{\mathcal{H}}>\theta)\theta^{\zeta}d\theta$.

###  8.2 Proof of Theorem 2

Since most steps in the proof of Theorem 2 follow that of the proof of Theorem
1, we only highlight the differences when $\mathcal{H}$ is finite-dimensional.
Again, without loss of generality, we assume that $i=1$ and the proof for
other arms follows similarly. Recall,
$\hat{\pi}_{s}:=P(\hat{a}_{s}=1|\mathcal{F}_{s-1},X_{s})$. Note that
$(\mathcal{A}_{5})$ implies $\mathcal{H}$ is finite-dimensional. Define
$d:=\text{dim}(\mathcal{H})$. Then

$\displaystyle N_{\Sigma,1}(\lambda)$ $\displaystyle=\text{Tr}((\Sigma+\lambda
I)^{-1}\Sigma)=\sup_{i}\dfrac{\eta_{i}(\Sigma)d}{(\eta_{i}(\Sigma)+\lambda)}\leq
d,\,\,\,\text{and}\,\,\,\|(\Sigma+\lambda
I)^{-1}\|_{\infty}\leq\dfrac{1}{\eta}.$ (50)

Therefore (25) modifies to

$\displaystyle\|\hat{f}_{1,t}-f_{1}\|_{\mathcal{H}}$
$\displaystyle\leq\|(\hat{\Sigma}_{1,t}+\lambda
I)^{-1/2}\|_{\infty}\|(\hat{\Sigma}_{1,t}+\lambda I)^{-1/2}(\Sigma+\lambda
I)^{1/2}\|_{\infty}$
$\displaystyle\quad\quad\times\left\lVert\left({\Sigma}+\lambda
I\right)^{-1/2}\left[-\lambda
f_{1}+\dfrac{1}{t}\sum_{s=1}^{t}\dfrac{I\\{\hat{a}_{s}=1\\}}{\hat{\pi}_{s}}k(\cdot,X_{s})\epsilon_{s}\right]\right\rVert_{\mathcal{H}}$
$\displaystyle\leq\|(\Sigma+\lambda
I)^{-1/2}\|_{\infty}\|(\hat{\Sigma}_{1,t}+\lambda I)^{-1/2}(\Sigma+\lambda
I)^{1/2}\|_{\infty}^{2}$
$\displaystyle\quad\quad\times\left\lVert\left({\Sigma}+\lambda
I\right)^{-1/2}\left[-\lambda
f_{1}+\dfrac{1}{t}\sum_{s=1}^{t}\dfrac{I\\{\hat{a}_{s}=1\\}}{\hat{\pi}_{s}}k(\cdot,X_{s})\epsilon_{s}\right]\right\rVert_{\mathcal{H}}$
$\displaystyle\leq\frac{\mathcal{S}^{2}_{1}\mathcal{S}_{2}}{\sqrt{\eta}}.$
(51)

We now bound $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$. Bounding
$\mathcal{S}_{1}$ proceeds exactly as in the proof of Theorem 1 until (29)
yielding

1
$\displaystyle\leq\dfrac{1}{t^{2}}\sum_{s=1}^{t}\dfrac{L-1}{\epsilon_{s}}\operatorname{Tr}\left((\Sigma+\lambda
I)^{-1}\Sigma\right)\|(\Sigma+\lambda
I)^{-1}\|_{\infty}\sup_{X_{s}}\|k(\cdot,X_{s})\otimes
k(\cdot,X_{s})\|_{\infty}$
$\displaystyle\leq\dfrac{1}{t^{2}}\left(\sum_{s=1}^{t}\dfrac{L-1}{\epsilon_{s}}\right)\frac{d\kappa}{\eta},$
(52)

where we use (50) in the last line of the above inequality. Putting together
(52), (34) and (36) in (27), and the result in (26), we get the following
analog of (37):

$\displaystyle\mathbb{E}\|B_{t}\|_{HS}^{2}\leq\dfrac{(L-1)d\kappa}{\eta}\left(\frac{1}{t^{2}}\sum_{s=1}^{t}\dfrac{1}{\epsilon_{s}}\right).$

Therefore, using Chebyshev’s inequality,

$\displaystyle P\left(\|B_{t}\|_{HS}\geq\frac{1}{2}\right)$ $\displaystyle\leq
4\mathbb{E}\|B_{t}\|_{HS}^{2}\leq\dfrac{4(L-1)d\kappa}{\eta}\left(\frac{1}{t^{2}}\sum_{s=1}^{t}\dfrac{1}{\epsilon_{s}}\right)\leq\delta.$

Thus for $\delta>0$, with probability at least $1-\delta$, we obtain

$\displaystyle\mathcal{S}^{2}_{1}\leq 2.$

To bound $\mathcal{S}_{2}$, we bound the second term in (39) as

$\displaystyle\lambda\|(\Sigma+\lambda
I)^{-1/2}f_{1}\|_{\mathcal{H}}\leq\lambda\|(\Sigma+\lambda
I)^{-1/2}\|_{\infty}\|f_{1}\|_{\mathcal{H}}\leq\dfrac{\lambda}{\sqrt{\eta}}\|f_{1}\|_{\mathcal{H}}.$
(53)

For bounding the first term of (39), we follow the same steps as in the proof
of Theorem 1 until (46). By using (50) in (46), we obtain

$\displaystyle P\left(\left\|(\Sigma+\lambda
I)^{-1/2}\dfrac{1}{t}\sum_{s=1}^{t}\dfrac{I\\{\hat{a}_{s}=1\\}}{\hat{\pi}_{s}}k(\cdot,X_{s})e_{s}\right\|_{\mathcal{H}}\geq\xi\right)\leq\dfrac{(L-1)\sigma^{2}d}{\xi^{2}}\left(\frac{1}{t^{2}}\sum_{s=1}^{t}\dfrac{1}{\epsilon_{s}}\right),$

i.e., with probability at least $1-\delta$,

$\displaystyle\left\|(\Sigma+\lambda
I)^{-1/2}\dfrac{1}{t}\sum_{s=1}^{t}\dfrac{I\\{\hat{a}_{s}=1\\}}{\hat{\pi}_{s}}k(\cdot,X_{s})e_{s}\right\|_{\mathcal{H}}\leq\sqrt{\dfrac{(L-1)\sigma^{2}d}{\delta}}\left(\frac{1}{t^{2}}\sum_{s=1}^{t}\dfrac{1}{\epsilon_{s}}\right)^{\frac{1}{2}}.$
(54)

Combining (53) and (54) in (39), we obtain that with probability at least
$1-\delta$,

$\mathcal{S}_{2}\leq\sqrt{\dfrac{(L-1)\sigma^{2}d}{\delta}}\left(\frac{1}{t^{2}}\sum_{s=1}^{t}\dfrac{1}{\epsilon_{s}}\right)^{\frac{1}{2}}+\frac{\lambda}{\sqrt{\eta}}\|f_{1}\|_{\mathcal{H}}.$

Using these bounds on $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$ in (51), we
obtain that with probability at least $1-2\delta$,

$\displaystyle\|\hat{f}_{1,t}-f_{1}\|_{\mathcal{H}}$
$\displaystyle\leq\left[\dfrac{4(L-1)\sigma^{2}d}{\delta\eta}\left(\frac{1}{t^{2}}\sum_{s=1}^{t}\dfrac{1}{\epsilon_{s}}\right)\right]^{1/2}+\dfrac{2\lambda}{\eta}\|f_{1}\|_{\mathcal{H}}$
$\displaystyle\leq
2\max\\{\tilde{C}_{0},\tilde{C}_{1}\\}\left[\left(\dfrac{1}{\delta
t^{2}}\left(\sum_{s=1}^{t}\dfrac{1}{\epsilon_{s}}\right)\right)^{1/2}+\lambda\right],$

where $\tilde{C}_{0}:=\sqrt{(L-1)\sigma^{2}d/\eta}$ and
$\tilde{C}_{1}:=\|f_{1}\|_{\mathcal{H}}/\eta$. The result, therefore, follows
by choosing

$\lambda=\lambda_{t}:=\left[\dfrac{1}{\delta
t^{2}}\left(\sum_{s=1}^{t}\dfrac{1}{\epsilon_{s}}\right)\right]^{1/2}.$

Note, that same proof works for all arms $i=1,\ldots,L$, by defining
$\hat{\pi}_{s}=P(\hat{a}_{s}=i|\mathcal{F}_{s-1},X_{s})$. The expectation
bound follows the same idea as in the proof of Theorem 1.

###  8.3 Proof of Theorem 3

The randomization error in the regret decomposition in (16) can be bounded as

$\displaystyle\sum_{t=1}^{T}\left|f_{A_{t}}(X_{t})-f_{\hat{a}_{t}}(X_{t})\right|=\sum_{t=1}^{T}\left|\left\langle
f_{A_{t}}-f_{\hat{a}_{t}},k(\cdot,X_{t})\right\rangle_{\mathcal{H}}\right|$
$\displaystyle=\sum_{t=1}^{T}I\\{\hat{a}_{t}\neq A_{t}\\}|\left\langle
f_{A_{t}}-f_{\hat{a}_{t}},k(\cdot,X_{t})\right\rangle_{\mathcal{H}}|\leq\kappa\sum_{t=1}^{T}I\\{\hat{a}_{t}\neq
A_{t}\\}\|f_{A_{t}}-f_{\hat{a}_{t}}\|_{\mathcal{H}}$
$\displaystyle\leq\kappa\left(\sum_{t=1}^{T}I\\{\hat{a}_{t}\neq
A_{t}\\}\right)^{1/p}\left(\sum_{t=1}^{T}\|f_{A_{t}}-f_{\hat{a}_{t}}\|_{\mathcal{H}}^{q}\right)^{1/q},$
(55) $\displaystyle\leq\kappa\left(\sum_{t=1}^{T}I\\{\hat{a}_{t}\neq
A_{t}\\}\right)^{1/p}\left(T\sup_{\begin{subarray}{c}a,a^{\prime}\in\mathcal{A}\\\
a\neq
a^{\prime}\end{subarray}}\|f_{a}-f_{a^{\prime}}\|_{\mathcal{H}}^{q}\right)^{1/q}$
$\displaystyle=\kappa T^{1/q}\left(\sum_{t=1}^{T}I\\{\hat{a}_{t}\neq
A_{t}\\}\right)^{1/p}\sup_{\begin{subarray}{c}a,a^{\prime}\in\mathcal{A}\\\
a\neq a^{\prime}\end{subarray}}\|f_{a}-f_{a^{\prime}}\|_{\mathcal{H}},$ (56)

where we obtain (55) by Hölder’s inequality with $p$ and $q$ such that
$\frac{1}{p}+\frac{1}{q}=1$, for $p,q\in[1,\infty]$. Next, we bound the first
term in (56) below. By the law of iterated expectations, we obtain

$\displaystyle\mathbb{E}[I\\{\hat{a}_{t}\neq A_{t}\\}]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}(I\\{\hat{a}_{t}\neq
A_{t}\\}|\mathcal{F}_{t-1},X_{t})\right]=\mathbb{E}[P(\hat{a}_{t}\neq
A_{t}|\mathcal{F}_{t-1},X_{t})]=\dfrac{\epsilon_{t}}{L-1}.$ (57)

Therefore, for any $\xi>0$, Chebyshev’s inequality yields

$\displaystyle P\left(\left|\sum_{t=1}^{T}I\\{\hat{a}_{t}\neq
A_{t}\\}-\sum_{t=1}^{T}\dfrac{\epsilon_{t}}{L-1}\right|\geq\xi\right)\leq\dfrac{1}{\xi^{2}}\mathbb{E}\left[\sum_{t=1}^{T}\left(I\\{\hat{a}_{t}\neq
A_{t}\\}-\dfrac{\epsilon_{t}}{L-1}\right)\right]^{2}$
$\displaystyle=\dfrac{1}{\xi^{2}}\mathbb{E}\left[\sum_{t=1}^{T}\sum_{s=1}^{T}\left(I\\{\hat{a}_{t}\neq
A_{t}\\}I\\{\hat{a}_{s}\neq
A_{s}\\}-\dfrac{\epsilon_{t}}{L-1}I\\{\hat{a}_{s}\neq
A_{s}\\}-\dfrac{\epsilon_{s}}{L-1}I\\{\hat{a}_{t}\neq
A_{t}\\}+\dfrac{\epsilon_{t}\epsilon_{s}}{(L-1)^{2}}\right)\right].$

Now, we simplify the expectation in the r.h.s. of the above inequality by
considering cases: (i) $s=t$, (ii) $s<t$ and (iii) $s>t$ as

$\displaystyle P\left(\left|\sum_{t=1}^{T}I\\{\hat{a}_{t}\neq
A_{t}\\}-\sum_{t=1}^{T}\dfrac{\epsilon_{t}}{L-1}\right|\geq\xi\right)\leq\leavevmode\hbox
to12.54pt{\vbox to12.54pt{\pgfpicture\makeatletter\hbox{\hskip
6.27202pt\lower-6.27202pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{6.07202pt}{0.0pt}\pgfsys@curveto{6.07202pt}{3.35352pt}{3.35352pt}{6.07202pt}{0.0pt}{6.07202pt}\pgfsys@curveto{-3.35352pt}{6.07202pt}{-6.07202pt}{3.35352pt}{-6.07202pt}{0.0pt}\pgfsys@curveto{-6.07202pt}{-3.35352pt}{-3.35352pt}{-6.07202pt}{0.0pt}{-6.07202pt}\pgfsys@curveto{3.35352pt}{-6.07202pt}{6.07202pt}{-3.35352pt}{6.07202pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.0pt}{-2.57777pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\footnotesize{7}}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}+\leavevmode\hbox
to12.54pt{\vbox to12.54pt{\pgfpicture\makeatletter\hbox{\hskip
6.27202pt\lower-6.27202pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{6.07202pt}{0.0pt}\pgfsys@curveto{6.07202pt}{3.35352pt}{3.35352pt}{6.07202pt}{0.0pt}{6.07202pt}\pgfsys@curveto{-3.35352pt}{6.07202pt}{-6.07202pt}{3.35352pt}{-6.07202pt}{0.0pt}\pgfsys@curveto{-6.07202pt}{-3.35352pt}{-3.35352pt}{-6.07202pt}{0.0pt}{-6.07202pt}\pgfsys@curveto{3.35352pt}{-6.07202pt}{6.07202pt}{-3.35352pt}{6.07202pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.0pt}{-2.57777pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\footnotesize{8}}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}+\leavevmode\hbox
to12.54pt{\vbox to12.54pt{\pgfpicture\makeatletter\hbox{\hskip
6.27202pt\lower-6.27202pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{6.07202pt}{0.0pt}\pgfsys@curveto{6.07202pt}{3.35352pt}{3.35352pt}{6.07202pt}{0.0pt}{6.07202pt}\pgfsys@curveto{-3.35352pt}{6.07202pt}{-6.07202pt}{3.35352pt}{-6.07202pt}{0.0pt}\pgfsys@curveto{-6.07202pt}{-3.35352pt}{-3.35352pt}{-6.07202pt}{0.0pt}{-6.07202pt}\pgfsys@curveto{3.35352pt}{-6.07202pt}{6.07202pt}{-3.35352pt}{6.07202pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.0pt}{-2.57777pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\footnotesize{9}}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}},$

where

7
$\displaystyle:=\dfrac{1}{\xi^{2}}\mathbb{E}\left[\sum_{t=1}^{T}\left(1-\dfrac{2\epsilon_{t}}{L-1}\right)I\\{\hat{a}_{t}\neq
A_{t}\\}+\dfrac{\epsilon_{t}^{2}}{(L-1)^{2}}\right]$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:
expectation_indicator}}}{{=}}\dfrac{1}{\xi^{2}}\sum_{t=1}^{T}\left[\left(1-\dfrac{2\epsilon_{t}}{L-1}\right)\left(\dfrac{\epsilon_{t}}{L-1}\right)+\dfrac{\epsilon_{t}^{2}}{(L-1)^{2}}\right]$
$\displaystyle=\dfrac{1}{\xi^{2}}\sum_{t=1}^{T}\dfrac{\epsilon_{t}}{L-1}-\dfrac{\epsilon_{t}^{2}}{(L-1)^{2}}=\dfrac{1}{\xi^{2}}\sum_{t=1}^{T}\dfrac{\epsilon_{t}}{L-1}\left[1-\dfrac{\epsilon_{t}}{L-1}\right],$

and

8
$\displaystyle:=\dfrac{1}{\xi^{2}}\sum_{t=2}^{T}\sum_{s=1}^{t-1}\left[\mathbb{E}\big{[}I\\{\hat{a}_{t}\neq
A_{t}\\}I\\{\hat{a}_{s}\neq
A_{s}\\}\big{]}-\dfrac{\epsilon_{t}}{L-1}\mathbb{E}\big{[}I\\{\hat{a}_{s}\neq
A_{s}\\}\big{]}-\dfrac{\epsilon_{s}}{L-1}\mathbb{E}\big{[}I\\{\hat{a}_{t}\neq
A_{t}\\}\big{]}\right.$
$\displaystyle\qquad\qquad\qquad\left.+\dfrac{\epsilon_{t}\epsilon_{s}}{(L-1)^{2}}\right]$
$\displaystyle=0,$

which follows from (57) and for $s<t$,

$\displaystyle\mathbb{E}\big{[}I\\{\hat{a}_{t}\neq A_{t}\\}I\\{\hat{a}_{s}\neq
A_{s}\\}\big{]}$
$\displaystyle=\mathbb{E}\big{[}\mathbb{E}(I\\{\hat{a}_{t}\neq
A_{t}\\}I\\{\hat{a}_{s}\neq A_{s}\\}\mid\mathcal{F}_{t-1},X_{t})\big{]}$
$\displaystyle=\mathbb{E}\big{[}I\\{\hat{a}_{s}\neq A_{s}\\}P(\hat{a}_{t}\neq
A_{t}|\mathcal{F}_{t-1},X_{t})\big{]}$
$\displaystyle=\mathbb{E}\Big{[}I\\{\hat{a}_{s}\neq
A_{s}\\}\times\dfrac{\epsilon_{t}}{L-1}\Big{]}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:
expectation_indicator}}}{{=}}\left(\dfrac{\epsilon_{s}}{L-1}\right)\left(\dfrac{\epsilon_{t}}{L-1}\right)=\mathbb{E}[I\\{\hat{a}_{t}\neq
A_{t}\\}]\mathbb{E}[I\\{\hat{a}_{s}\neq A_{s}\\}].$

Through similar calculation, it follows that

9
$\displaystyle:=\dfrac{1}{\xi^{2}}\left[\sum_{t=1}^{T-1}\sum_{s=t+1}^{T}\mathbb{E}[I\\{\hat{a}_{t}\neq
A_{t}\\}I\\{\hat{a}_{s}\neq
A_{s}\\}]-\dfrac{\epsilon_{t}}{L-1}\mathbb{E}[I\\{\hat{a}_{s}\neq
A_{s}\\}]-\dfrac{\epsilon_{s}}{L-1}\mathbb{E}[I\\{\hat{a}_{t}\neq
A_{t}\\}]\right.$
$\displaystyle\qquad\qquad\qquad\left.+\dfrac{\epsilon_{t}\epsilon_{s}}{(L-1)^{2}}\right]$
$\displaystyle=0.$

Therefore, we obtain

$\displaystyle P\left(\left|\sum_{t=1}^{T}I\\{\hat{a}_{t}\neq
A_{t}\\}-\sum_{t=1}^{T}\dfrac{\epsilon_{t}}{L-1}\right|\geq\xi\right)\leq\dfrac{1}{\xi^{2}}\sum_{t=1}^{T}\dfrac{\epsilon_{t}}{L-1}\left[1-\dfrac{\epsilon_{t}}{L-1}\right]\leq\dfrac{1}{\xi^{2}}\sum_{t=1}^{T}\dfrac{\epsilon_{t}}{L-1},$

which implies for any $\delta>0$, with probability at least $1-\delta$,

$\displaystyle\sum_{t=1}^{T}\dfrac{\epsilon_{t}}{L-1}-\left[\dfrac{1}{\delta}\sum_{t=1}^{T}\dfrac{\epsilon_{t}}{L-1}\right]^{1/2}\leq\sum_{t=1}^{T}I\\{\hat{a}_{t}\neq
A_{t}\\}\leq\sum_{t=1}^{T}\dfrac{\epsilon_{t}}{L-1}+\left[\dfrac{1}{\delta}\sum_{t=1}^{T}\dfrac{\epsilon_{t}}{L-1}\right]^{1/2}.$
(58)

Using (58) in (56) yields that with probability at least $1-\delta$,

$\displaystyle\sum_{t=1}^{T}|f_{A_{t}}(X_{t})-f_{\hat{a}_{t}}(X_{t})|$
$\displaystyle\leq\kappa
T^{1-\frac{1}{p}}\left[\sum_{t=1}^{T}\dfrac{\epsilon_{t}}{L-1}+\left\\{\dfrac{1}{\delta}\sum_{t=1}^{T}\dfrac{\epsilon_{t}}{L-1}\right\\}^{1/2}\right]^{1/p}\sup_{\begin{subarray}{c}a,a^{\prime}\in\mathcal{A}\\\
a\neq a^{\prime}\end{subarray}}\|f_{a}-f_{a^{\prime}}\|_{\mathcal{H}}.$ (59)

Next, we construct an upper bound for the cumulative estimation error in the
regret decomposition in (16). By recalling $\mathcal{A}:=\\{1,\ldots,L\\}$,
consider

$\displaystyle\sup_{i\in\mathcal{A}}|(f_{i}(X_{t})-\hat{f}_{i}(X_{t}))|$
$\displaystyle=\sup_{i\in\mathcal{A}}|\langle
f_{i}-\hat{f}_{i,t},k(\cdot,X_{t})\rangle_{\mathcal{H}}|\leq\kappa\sup_{i\in\mathcal{A}}\|f_{i}-\hat{f}_{i,t}\|_{\mathcal{H}},$
(60)

where we will use Theorem 1 to bound (60). To this end, by union bounding, we
have

$\displaystyle
P\left(\sup_{i\in\mathcal{A}}\|f_{i}-\hat{f}_{i,t}\|_{\mathcal{H}}\geq
b_{t}\right)\leq\sum_{i=1}^{L}P\left(\|f_{i}-\hat{f}_{i,t}\|_{\mathcal{H}}\geq
b_{t}\right)$
$\displaystyle\leq\left(\frac{1}{t^{2}}\sum^{t}_{s=1}\frac{1}{\epsilon_{s}}\right)\sum^{L}_{i=1}\left(\frac{2\sqrt{2}\max\\{C_{0},C_{i}\\}}{b_{t}}\right)^{1/w_{i}}$
$\displaystyle\leq
L\left(\frac{1}{t^{2}}\sum^{t}_{s=1}\frac{1}{\epsilon_{s}}\right)\max_{i\in\mathcal{A}}\left(\frac{2\sqrt{2}\max\\{C_{0},C_{i}\\}}{b_{t}}\right)^{1/w_{i}}$
$\displaystyle\leq
L\left(\frac{1}{t^{2}}\sum^{t}_{s=1}\frac{1}{\epsilon_{s}}\right)\max_{i\in\mathcal{A}}\left(\frac{\Theta}{b_{t}}\right)^{1/w_{i}}$
$\displaystyle\leq
L\left(\frac{1}{t^{2}}\sum^{t}_{s=1}\frac{1}{\epsilon_{s}}\right)\times\begin{cases}\left(\frac{\Theta}{b_{t}}\right)^{\max_{i\in\mathcal{A}}1/w_{i}},&b_{t}<\Theta\\\
\left(\frac{\Theta}{b_{t}}\right)^{\min_{i\in\mathcal{A}}1/w_{i}},&b_{t}\geq\Theta\end{cases},$

where $\Theta:=\max_{i\in\mathcal{A}}2\sqrt{2}\max\\{C_{0},C_{i}\\}$ and
$w_{i}={\gamma_{i}\alpha}/{(2\gamma_{i}\alpha+\alpha+1)}$. This means with
probability at least $1-\delta$,

$\displaystyle\sup_{i\in\mathcal{A}}\|f_{i}-\hat{f}_{i,t}\|_{\mathcal{H}}\leq\begin{cases}\Theta\Delta_{t}^{\min_{i\in\mathcal{A}}w_{i}},&\Delta_{t}<1\\\
\Theta\Delta_{t}^{\max_{i\in\mathcal{A}}w_{i}},&\Delta_{t}\geq 1\\\
\end{cases}=\begin{cases}\Theta\Delta_{t}^{\frac{(\min_{i\in\mathcal{A}}\gamma_{i})\alpha}{2(\min_{i\in\mathcal{A}}\gamma_{i})\alpha+\alpha+1}},&\Delta_{t}<1\\\