# When are Bandits Robust to Misspecification?

Debangshu Banerjee  Aditya Gopalan

###### Abstract

Parametric feature-based reward models are widely employed by algorithms for
decision making settings such as bandits and contextual bandits. The typical
assumption under which they are analysed is realizability, i.e., that the true
rewards of actions are perfectly explained by some parametric model in the
class. We are, however, interested in the situation where the true rewards are
(potentially significantly) misspecified with respect to the model class. For
parameterized bandits and contextual bandits, we identify sufficient
conditions, depending on the problem instance and model class, under which
classic algorithms such as $\varepsilon$-greedy and LinUCB enjoy sublinear (in
the time horizon) regret guarantees under even grossly misspecified rewards.
This is in contrast to existing worst-case results for misspecified bandits
which show regret bounds that scale linearly with time, and shows that there
can be a nontrivially large set of bandit instances that are robust to
misspecification.

##  1 Introduction

Sequential optimization over a set of decisions, e.g., actions in a multi-
armed bandit and policies in an MDP, is often carried out by assuming a
parametric model for the payoff of a decision, which is learnt with time.
Well-known instantiations of this approach are algorithms for structured
multi-armed bandits, e.g., linear bandits Rusmevichientong and Tsitsiklis
(2010) and generalized linear bandits Filippi et al. (2010), linear contextual
bandits Chu et al. (2011), and value function approximation-based methods for
Markov Decision Processes Sutton and Barto (2018).

Algorithms that make decisions based on an estimated reward model are known to
enjoy attractive regret guarantees when the true rewards encountered are
perfectly realizable by the model, see, e.g., Abbasi-Yadkori et al. (2011);
Filippi et al. (2010); Jin et al. (2020). However, it is more likely than not
that a parametric class of models is, at best, only an approximation of
reality, succinctly expressed by the aphorism ‘all models are wrong, but some
are useful’ Box (1976). This is quite likely true in the context of sequential
decision-making – after all, even if the rewards of, say, arms in a multi-
armed bandit, are estimated with (significantly) large error, one may still
hope to discern the optimal arm if its (erroneous) estimate ends up dominating
those of the other arms. This begs a natural question—While the task of reward
estimation can be fraught with error under misspecified models, when can the
task of optimal action learning remain immune to it?

We initiate a rigorous study of the extent to which sequential decision-making
algorithms based on estimating reward models can be robust to misspecification
in the model. In particular, we are interested in characterizing the interplay
between the (true) arms’ rewards of a bandit and the reward model class
assumed by the algorithm, and how it governs whether the algorithm can still
learn to play optimally if the true rewards are not realizable by the reward
model. In this respect, our specific contributions are as follows:

  1. 1.

For misspecified linear bandits, we identify a novel family of instances
(reward vectors, in dimension the number of arms), which we term the robust
observation region. Reward vectors in this region are characterized by an
invariance property of the greedy action that they induce after being
projected, with respect to any weighted Euclidean norm, onto the linear
feature subspace. This region, depending upon the feature subspace, can be
non-trivially large, and need not be confined to within a small deviation from
the subspace.

  2. 2.

We prove that for any instance with the arms’ rewards in the robust
observation region, both (i) the $\varepsilon$-greedy algorithm, with least-
squares parameter estimation and an exploration rate of $1/\sqrt{t}$ in each
round $t$, and (ii) the LinUCB (or OFUL) algorithm, achieve $O(\sqrt{T})$
regret in the time horizon $T$.

  3. 3.

We extend the notion of robust reward instances to the problem of linear
contextual bandits, for which we provide a generalization of the robust
observation region. We show that both the $\varepsilon$-greedy and LinUCB
algorithms for linear contextual bandits get $O(\sqrt{T})$ regret whenever the
true, misspecified, reward vector belongs to this robust observation region.

We stress that our results pertain to the original algorithms (i.e., not
modified to be misspecification-aware in any manner). It is our novel
analytical approach that shows that they achieve nontrivial sublinear regret,
even under arbitrarily large misspecification error111The term
‘misspecification error’ is to be understood as the distance of the arms’
reward vector to the model reward subspace.. This is in contrast to, and
incomparable with, existing results that argue that, in the ‘worst case’
across all reward vectors that are a constant distance away from the feature
subspace, any algorithm must incur regret that scales linearly with the time
horizon, e.g., (Lattimore et al., 2020, Thm. F.1).

Our results lend credence, in a strong theoretical sense, to the observation
that reinforcement learning algorithms based on presumably approximate value
function models are often able to learn (near-) optimal behavior in practice
across challenging benchmarks Mnih et al. (2013); Lillicrap et al. (2015).
They also shine light on the precise structure of bandit problems that makes
robustness possible in the face of significant misspecification.

##### Illustrative Example

The key concepts and results of this paper can be understood using a simple
toy example of a misspecified 2-armed (non-contextual) linear bandit. Assume
that the vector of mean rewards of the arms (the “instance”) is
$\bm{\mu}=\begin{bmatrix}\mu_{1},\mu_{2}\end{bmatrix}^{\top}=\begin{bmatrix}20,3\end{bmatrix}^{\top}$.
This instance can be thought of as an element in the $\mathbb{R}^{2}$ plane
(marked by $\times$ in Fig. 1). Suppose one attempts to learn this bandit via
a 1-dimensional linear reward model in which the arms’ features are assumed to
be $\varphi_{1}=3,\varphi_{2}=1$. It follows that (i) any (2-armed) bandit
instance in this linear model is of the form $\bm{\Phi}\theta$, where
$\theta\in\mathbb{R}$ and
$\bm{\Phi}=\begin{bmatrix}\varphi_{1},\varphi_{2}\end{bmatrix}^{\top}=\begin{bmatrix}3,1\end{bmatrix}^{\top}\in\mathbb{R}^{2\times
1}$, and corresponds to an element in the range space of $\bm{\Phi}$, and (ii)
the instance $\bm{\mu}$ is misspecified as it is off the subspace222The
$l_{\infty}$ misspecification error (deviation from subspace) of $\bm{\mu}$ is
$2.75$ for this example..

For ease of exposition, consider that there is no noise in the rewards
observed by pulling arms. In this case, the ordinary least squares estimate of
$\theta$, computed at time $t$ from $n_{1}$ observations of arm $1$ and
$n_{2}$ observations of arm $2$, is
$\widehat{\theta}_{t}=\frac{n_{1}\varphi_{1}\mu_{1}+n_{2}\varphi_{2}\mu_{2}}{n_{1}\varphi_{1}^{2}+n_{2}\varphi_{2}^{2}}$.
A key observation is that $\widehat{\theta}_{t}$ can be written as a convex
combination of $\mu_{1}/\varphi_{1}=6.7$ and $\mu_{2}/\varphi_{2}=3$:
$\widehat{\theta}_{t}=\frac{n_{1}\varphi_{1}^{2}}{n_{1}\varphi_{1}^{2}+n_{2}\varphi_{2}^{2}}\Big{(}\mu_{1}/\varphi_{1}\Big{)}+\frac{n_{2}\varphi_{2}^{2}}{n_{1}\varphi_{1}^{2}+n_{2}\varphi_{2}^{2}}\Big{(}\mu_{2}/\varphi_{2}\Big{)}$,
regardless of the past sampling distribution of the arms. The corresponding
parametric estimated rewards $\bm{\Phi}\widehat{\theta}_{t}$, must thus lie in
the set $\\{[3\theta,\theta]^{\top}:\theta\in[3,6.7]\\}$, which appears as the
hypotenuse of the right triangle with vertex $(20,3)$ in Fig. 1.

Note that if a greedy rule is applied to play all subsequent actions
($A_{t+1}=\mathop{\mathrm{argmax}}_{i=1,2}\varphi_{i}^{\top}\widehat{\theta}_{t}$),
then the action will be $1$, since the point $\bm{\Phi}\widehat{\theta}_{t}$
is always ‘below’ the standard diagonal $\mu_{1}=\mu_{2}$ (the black line in
Fig. 1). Since action $1$ is optimal for the (true) rewards $\bm{\mu}$, the
algorithm will never incur regret in the future.

The instance above has a misspecification error significantly smaller than the
reward gap ($2.75<17$). One can also find instances at the other extreme,
e.g., $\bm{\tilde{\mu}}=[20,18]^{\top}$ (marked by $\circ$ in Fig. 1) for
which the misspecification error is much larger than the gap ($8.5>2$), that
remain robust in the sense of regret. Such instances fall outside the scope of
existing work on misspecified bandits Zhang et al. (2023), and we address them
in our work.

The remainder of the paper generalizes this observation for stochastic arm
rewards and algorithms that incorporate some form of exploration
($\varepsilon$-greedy and optimism-based) and explicitly characterizes the set
of all true reward instances for which no-regret learning is possible.

Figure 1: A 2-armed, noiseless bandit with 1-dimensional linear approximation.
Each point in the plane represents the true rewards of both arms (the
“instance”). The red line is the set of instances expressed by the linear
approximation. The gray and turquoise regions, above and below the main
diagonal $\mu_{1}=\mu_{2}$, denote instances whose best arm is 2 and 1,
respectively. The misspecified instances $(20,3)$ and $(20,18)$ yield no
regret under greedy arm selection based on an estimated linear model since any
linear estimate of the rewards always has arm $1$ dominating arm $2$.

###  1.1 Related Work

Existing work on misspecified bandits contributes results that can be put into
two categories. The first category is negative results of a worst-case form,
for instance: there exist reward instances for linear bandits for which (i)
the model misspecification error ($l_{\infty}$ distance of the reward vector
from the model subspace $\text{Range}(\bm{\Phi})$) is at most $\rho>0$ and
(ii) the LinUCB algorithm suffers regret $\Omega(\rho T)$ in $T$ rounds.
Results of this nature are well established in the misspecified bandit and
contextual bandit literature, including but not limited to the works of Ghosh
et al. (2017); Lattimore et al. (2020); Zanette et al. (2020). Lattimore et
al. (2020) present a frequentist analysis that shows that even with the
knowledge of the misspecification error, a modified form of LinUCB fails to
give sub-linear regret in the misspecified contextual setting. Zanette et al.
(2020) extend a similar analysis to learning Markov Decision Processes.

The second type of result is along a positive direction: to develop
conditions, and associated algorithms, under which misspecified bandits can
give sub-linear regret. The work of Liu et al. (2023) analyzes the LinUCB
algorithm when the sub-optimality gaps of the arms bound the misspecification.
They show that when the misspecification is of low order, the algorithm enjoys
sub-linear regret. Under a similar condition, Zhang et al. (2023) were able to
extend the study to the contextual setting. They propose a phased arm
elimination algorithm, which performs similarly to SupLinUCB Chu et al. (2011)
but requires knowledge of the sub-optimality gap.

Our results, in this positive spirit, give more fine-grained structural
conditions instead of the coarse notion of misspecification error to ensure
that algorithms such as $\varepsilon$-greedy and LinUCB can achieve robust
learning without any additional modifications. A detailed comparison of our
results with Zhang et al. (2023) appears at the end of Sec. 2 and a more
detailed survey of previous work in the appendix.

##  2 Problem Statement and Results

We describe our results for misspecified linear bandits and then proceed to
the misspecified contextual case in the second part of this section.

###  2.1 Linear Bandits

##### Problem Statement

We consider a $K$-armed bandit with mean rewards $\\{\mu_{i}\\}_{i=1}^{K}$. We
assume each arm $i$ is associated with a known feature vector
$\varphi_{i}\in\mathbb{R}^{d}$. We also have a given parametric class of
functions serving to (approximately) model the mean reward of each arm; each
function in this class is of the form $f_{\theta}:\mathbb{R}^{d}\to\mathbb{R}$
for a parameter $\theta\in\Theta$, and applying it to arm $i$ yields the
expressed reward $f_{\theta}(\varphi_{i})\in\mathbb{R}$.

Let us assume that the number of arms, $K$, is larger than the dimensionality
of the parameter $\theta$, that is $K>d$ and, for ease of analysis, consider
the set of features $\\{\varphi_{i}\\}_{i=1}^{K}$ to span $\mathbb{R}^{d}$. We
shall denote the set of true mean rewards by the vector,
$\bm{\mu}=\begin{bmatrix}\mu_{i}\end{bmatrix}_{i\in[K]}\in\mathbb{R}^{\mathrm{K}}$
and the feature matrix
$\bm{\Phi}=\begin{bmatrix}\cdots\varphi_{i}^{\top}\cdots\\\
\end{bmatrix}_{i\in[K]}\in\mathbb{R}^{K\times d}$. The assumption on the
features fixes the rank of $\bm{\Phi}$ as $d$.

######  Remark 2.1 (Linear Bandits).

Our setting is rather general and covers a broad class of parametric bandits.
For example, in linear bandits Dani et al. (2008), it is assumed that the
means are linear functions of the features, that is, there exists a
$\theta^{*}$, such that $\bm{\mu}=\bm{\Phi}\theta^{*}$.

######  Remark 2.2 (Misspecification).

We allow the vector of true rewards $\bm{\mu}$ to be arbitrary, without
imposing a realizability condition like
$\bm{\mu}\in\\{f_{\theta}(\varphi_{i})\;\forall\;i\in[K]:\theta\in\mathbb{R}^{d}\\}$.

We shall derive sufficient conditions under which (misspecified) bandit
instances $\bm{\mu}$ can yield sub-linear regret under standard algorithms
like $\varepsilon$-greedy and LinUCB. A key step towards this is to identify a
_robust region_ which depends on the model class such that any instance in
this region is guaranteed to enjoy sub-linear regret.

We begin by recalling the usual _greedy regions_ in $\mathbb{R}^{\mathrm{K}}$
which characterize reward vectors that share the same optimal arm.

######  Definition 2.3 (Greedy Region $\mathcal{R}$).

Define by $\mathcal{R}_{k}$, for any $k\in[K]$, as the region in
$\mathbb{R}^{\mathrm{K}}$ for which the $k^{th}$ arm is optimal, i.e.,
$\mathcal{R}_{k}\triangleq\Big{\\{}\bm{\mu}\in\mathbb{R}^{\mathrm{K}}:\mu_{k}>\mu_{i}\forall
i\neq k\Big{\\}}$.

For the purposes of clarity, let us fix our model class to be linear, so that
the least squares estimate has a closed form solution amenable to explicit
analysis. Denoting the play count of each arm $i$ up to time $t$ by
$\alpha(i,t)=\sum_{s=1}^{t}\mathbb{1}\\{A_{s}=i\\}$, the least squares
estimate $\widehat{\theta}_{t+1}$ can be written as

$\displaystyle\widehat{\theta}_{t+1}$
$\displaystyle=\Big{[}\sum_{i=1}^{K}\alpha(i,t)\varphi_{i}\varphi_{i}^{\top}\Big{]}^{-1}(\sum_{i=1}^{K}\alpha(i,t)\varphi_{i}\widehat{\mu}_{i,t})$
$\displaystyle=(\bm{\Phi}^{\top}\Lambda(t)\bm{\Phi})^{-1}\bm{\Phi}^{\top}\Lambda\bm{\widehat{\mu}_{t}}\,,$
(1)

where $\widehat{\mu}_{i,t}$ is the sample mean of the rewards from arm $i$ as
observed till time $t$, that is
$\widehat{\mu}_{i,t}=\frac{\sum_{s=1}^{t}y_{s}\mathbb{1}\\{A_{s}=i\\}}{\sum_{s=1}^{t}\mathbb{1}\\{A_{s}=i\\}}$,
$\Lambda(t)$ is a $K\times K$ diagonal matrix with $\alpha(i,t)$ terms on the
diagonal and $\bm{\widehat{\mu}_{t}}$ is a $K$ dimensional vector with
$\widehat{\mu}_{i,t}$ as it’s elements. Gopalan et al. (2016).

######  Remark 2.4.

Note that as per our assumption on the rank of the feature matrix,
$\bm{\Phi}^{\top}\Lambda(t)\bm{\Phi}$ is invertible if $\alpha(i,t)>0$ for any
$d$ linearly independent features. This can be ensured by explicitly forcing
the algorithm to sample $d$ such features at least once. For ease of
exposition, we shall assume that $\bm{\Phi}^{\top}\Lambda(t)\bm{\Phi}$ is
invertible.

######  Remark 2.5.

We note from the closed form solution of the least squares estimate, Equation
1, that we can equivalently interpret the play counts $\alpha(i,t)$ for any
arm $i\in[K]$ in terms of (normalized) sampling frequencies:
$\alpha(i)=\frac{\sum_{s=1}^{t}\mathbb{1}\\{A_{s}=i\\}}{t}$ for any
$t\geqslant 1$, so that $\\{\alpha(i)\\}_{i=1}^{K}$ belongs to the $K$
dimensional simplex $\Delta_{\mathrm{K}}$. that is
$\sum_{i=1}^{K}\alpha(i)=1$.

######  Remark 2.6.

With this notation, we can observe that any least squares estimate is
calculated based upon some sampling frequency
$\\{\alpha(i)\\}_{i=1}^{K}\in\Delta_{\mathrm{K}}$ and the corresponding sample
estimates $\bm{\widehat{\mu}_{t}}$. The least squares estimate can now be
rewritten as an optimization problem with respect to a weighted norm:
$\widehat{\theta}_{t}=\mathop{\mathrm{argmin}}_{\theta}\Big{\|}\bm{\Phi}\theta-\bm{\widehat{\mu}_{t}}\Big{\|}_{\Lambda^{1/2}}$,
where $\Lambda=\mathrm{diag}(\\{\alpha(i)\\}_{i=1}^{K})$ for some sampling
frequency in the simplex $\Delta_{\mathrm{K}}$. With this interpretation, we
define the model estimate.

######  Definition 2.7 (Model Estimate under Sampling Distribution).

For any bandit instance $\bm{\mu}$ in $\mathbb{R}^{\mathrm{K}}$, we shall
denote the model estimate of the $K$ dimensional element $\bm{\mu}$ under any
sampling distribution, defined by
$\Lambda=\mathrm{diag}(\\{\alpha(i)\\}_{i=1}^{K})$, as
$\mathbf{P}^{\Lambda}(\bm{\mu})\triangleq\mathop{\mathrm{argmin}}_{\theta}\Big{\|}\bm{\Phi}\theta-\bm{\mu}\Big{\|}_{\Lambda^{1/2}}$.

######  Remark 2.8.

With this definition, we observe that the least squares estimate
$\widehat{\theta}_{t}$ is $\mathbf{P}^{\Lambda}(\bm{\widehat{\mu}_{t}})$ in
our notation, for some sampling distribution defined by
$\Lambda=\mathrm{diag}(\\{\alpha(i)\\}_{i=1}^{K})$ and the corresponding
sample estimates of $\bm{\widehat{\mu}_{t}}$.

######  Remark 2.9.

Another way of describing $\mathbf{P}^{\Lambda}(\bm{\mu})$ is by considering
the least squares estimate, Equation 1, with $\bm{\widehat{\mu}_{t}}$ being
exactly $\bm{\mu}$, which is equivalent of saying there is no stochasticity in
the observations of each arm pull.

Given a given bandit instance $\bm{\mu}\in\mathbb{R}^{\mathrm{K}}$, assume,
without loss of generality, that $k$ is the optimal arm, that is $\bm{\mu}$
belongs to the $k^{th}$ greedy region $\mathcal{R}_{k}$. Now consider the
model estimate $\mathbf{P}^{\Lambda}(\bm{\mu})$ estimated under exact
observations of $\bm{\mu}$ (that is, no stochasticity), using a sampling
distribution of $\Lambda=\mathrm{diag}(\\{\alpha(i)\\}_{i=1}^{K})$. If the
projection, $\bm{\Phi}\mathbf{P}^{\Lambda}(\bm{\mu})$ belongs to the true
greedy region $\mathcal{R}_{k}$, then under this sampling distribution, the
model estimate would always return the optimal arm under a greedy strategy.
That is,
$\mathop{\mathrm{argmax}}_{i\in[K]}\varphi_{i}^{\top}\mathbf{P}^{\Lambda}(\bm{\mu})$
would result in the $k^{th}$ arm being pulled. With this motivation, we define
_robust regions_.

######  Definition 2.10 (Robust Parameter Region).

For a given feature matrix $\bm{\Phi}$, we define the $k^{th}$ _robust
parameter region_ $\Theta_{k}$ as the the set of all parameters
$\theta\in\mathbb{R}^{d}$ such that the range space of $\bm{\Phi}$ restricted
to $\Theta_{k}$ lies in the $k^{th}$ greedy region $\mathcal{R}_{k}$.

$\displaystyle\Theta_{k}=\Big{\\{}\theta\in\mathbb{R}^{d}:\bm{\Phi}\theta\in\mathcal{R}_{k}\Big{\\}},\;\;\;\text{for
any arm }k.$

######  Definition 2.11 (Robust Observation Region).

For a given feature matrix $\bm{\Phi}$, we define the $k^{th}$ _robust
observation region_ $\mathcal{C}_{k}$, as the set of all $K$ armed bandit
instances $\bm{\mu}$ with optimal arm $k$, such that under any sampling
distribution $\\{\alpha(i)\\}_{i=1}^{K}\in\Delta_{\mathrm{K}}$, the
corresponding model estimate, $\mathbf{P}^{\Lambda}(\bm{\mu})$, lies in the
$k^{th}$ robust parameter region, $\Theta_{k}$.

$\displaystyle\mathcal{C}_{k}=\Big{\\{}\bm{\mu}\in\mathcal{R}_{k}:\mathbf{P}^{\Lambda}(\bm{\mu})\in\Theta_{k}\;\forall\;\Lambda\in\bm{\Lambda}\Big{\\}}\;\;\;\textit{for
any arm }k,$

where

$\displaystyle\bm{\Lambda}=\Big{\\{}\Lambda=\mathrm{diag}(\\{\alpha(i)\\}_{i=1}^{K}):\\{\alpha(i)\\}_{i=1}^{K}\in\Delta_{\mathrm{K}}\Big{\\}}.$

######  Remark 2.12.

As already mentioned, we will assume, without any serious consequences, that
we will be looking at the set of diagonal matrices $\bm{\Lambda}$ for which
$\bm{\Phi}^{\top}\Lambda\bm{\Phi}$ is invertible.

From the definitions of the _robust observation region_ and _robust parameter
region_ , we observe that if $\bm{\mu}$ belongs to the $k^{th}$ robust
observation region $\mathcal{C}_{k}$, then the greedy strategy
$\mathop{\mathrm{argmax}}_{i\in[K]}\varphi_{i}^{\top}\mathbf{P}^{\Lambda}(\mu)$
would ensure the optimal arm $k$ is chosen under any sampling distribution of
the arms.

##### Characterization of the Robust Observation Space

In the class of linear models, the _robust observation region_
$\mathcal{C}_{k}$ has a closed-form structure that can be evaluated.

######  Theorem 2.13.

For any reward vector $\bm{\mu}$ with optimal arm $k$, $\bm{\mu}$ belongs to
the _robust observation region_ $\mathcal{C}_{k}$ if and only if each $d\times
d$ full rank sub-matrix of $\bm{\Phi}$, denoted by $\Phi_{d}$, along with the
corresponding $d$ rows of $\bm{\mu}$, denoted by $\bm{\mu}_{d}$, satisfies the
condition that $\Phi_{d}^{-1}\bm{\mu}_{d}\in\Theta_{k}$. In other words,

$\displaystyle\forall\bm{\mu}\in\mathcal{R}_{k}:\bm{\mu}\in\mathcal{C}_{k}\iff\Phi_{d}^{-1}\bm{\mu}_{d}\in\Theta_{k}\;$

for all $d\times d$ full rank sub-matrices of $\bm{\Phi}$ (denoted as
$\Phi_{d}$) and the corresponding $d$ rows of $\bm{\mu}$ (denoted as
$\bm{\mu}_{d}$).

###### Proof.

The proof uses a result of Forsgren (1996), presented in Lemma H.4, that for
any any sampling distribution
$\\{\alpha(i)\\}_{i=1}^{K}\in\Delta_{\mathrm{K}}$, the model estimate
$\mathbf{P}^{\Lambda}(\bm{\mu})$, with
$\Lambda=\mathrm{diag}(\\{\alpha(i)\\}_{i=1}^{K})$, lies in the convex hull of
the basic solutions $\Phi_{d}^{-1}\bm{\mu}_{d}$. 333Where we have implicitly
assumed that $\bm{\Phi}^{\top}\Lambda\bm{\Phi}$ is invertible Thus for any
$\bm{\mu}\in\mathcal{R}_{k}$

$\displaystyle\bm{\mu}\in\mathcal{C}_{k}$
$\displaystyle\iff\mathbf{P}^{\Lambda}(\bm{\mu})\in\Theta_{k}\;\forall\;\Lambda\in\bm{\Lambda}$
$\displaystyle\iff\mathrm{conv}\\{\Phi_{d}^{-1}\bm{\mu}_{d}\;\forall\;\Phi_{d}\subset\bm{\Phi}\\}\subset\Theta_{k},$
$\displaystyle\iff\Phi_{d}^{-1}\bm{\mu}_{d}\in\Theta_{k}\;\forall\;\Phi_{d}\subset\Phi.$

The first line above follows from Definition 2.11, and the second line follows
from Lemma H.4. (We abuse notation to denote $d\times d$ full rank sub-
matrices of $\bm{\Phi}$ by $\Phi_{d}\subset\bm{\Phi}$ and use $\mathrm{conv}$
to denote the convex hull.) The last assertion follows because $\Theta_{k}$ is
a convex set. ∎

##### Example

We return to our example presented at the beginning (in Figure 1) to highlight
the definitions we have made so far. The greedy regions, $\mathcal{R}_{1}$ and
$\mathcal{R}_{2}$, are shown by the turquoise shade and the gray shade
respectively. From our choice of the feature matrix $\bm{\Phi}$ as
$\begin{bmatrix}3,1\end{bmatrix}^{\top}$, we note that for any parameter
$\theta$ more than $0$, the range space of $\bm{\Phi}$ belong to
$\mathcal{R}_{1}$. Thus $\Theta_{1}$, the robust parameter region
corresponding to arm $1$, is the set of all positive scalars. Similarly,
$\Theta_{2}$, is the set of all negative scalars. $\mathcal{C}_{1}$, the
robust observation region, corresponding to arm $1$, is given by the set,
$\\{\bm{\mu}\in\mathbb{R}^{2}\,:\,\mu_{1}>\mu_{2}>0\\}$. The robust
observation region for arm $2$, $\mathcal{C}_{2}$ is given by the set
$\\{\bm{\mu}\in\mathbb{R}^{2}\,:\,\mu_{1}<\mu_{2}<0\\}$. This illustrates the
existence of a large class of bandit problems which are misspecified but
robust for our model class.

##### Sufficient Conditions for Zero Regret with Stochastic Rewards

The astute reader must have noticed by now that we have made our claims of
robustness based on least squares estimates calculated from noiseless
observations of $\bm{\mu}$. In the general setting of stochastic rewards, the
empirical estimate of $\bm{\widehat{\mu_{t}}}$ need not always belong to the
_robust observation region_. We shall show, however, that (under standard sub-
Gaussian noise assumptions) this estimate will eventually fall inside the
_robust_ region when playing $\varepsilon$-greedy and LinUCB algorithms, after
which the algorithms cease to suffer linear regret.

We make the following standard assumption regarding the noise in rewards being
sub-Gaussian.

######  Assumption 2.14 (sub-Gaussian Reward Observations).

We shall assume that the $K$ armed bandit instance $\bm{\mu}$ is $1/2\text{
sub-Gaussian}$444The reason for choosing $1/2$ is purely for ease of
calculation and can be replaced by any other constant..

We shall show that $\bm{\mu}$ belonging to a robust region is a sufficient
condition for $\varepsilon$-greedy to achieve sub-linear regret. For a
technical reason we shall require a bit stronger condition, namely that
$\bm{\mu}$ is an interior point of a robust region, that is, there exists a
ball $\mathcal{B}_{\delta}(\bm{\mu})$ for some $\delta>0$ contained in
$\mathcal{C}_{k}$ 555Here without loss of generality, we assume that the
$k^{th}$ arm is optimal for the bandit instance.. For the purpose of analysis
we take the topology of $\mathbb{R}^{\mathrm{K}}$, as open rectangles in
$\mathbb{R}^{\mathrm{K}}$. With this topology we can define an interior point
as follows.

######  Definition 2.15 (Interior Point).

$\bm{\mu}$ is an interior point of $\mathcal{C}_{k}$ implies that there exists
a $\delta>0$, such the $K$-dimensional cell, with size $\delta$ and centre
$\bm{\mu}$, is a subset of $\mathcal{C}_{k}$. That is,

$\displaystyle\bm{\mu}\in\mathrm{Int}(\mathcal{C}_{k})\iff\exists\;\delta>0\;s.t.\;\mathbf{1}_{\delta}(\bm{\mu})\subset\mathcal{C}_{k},$

where $\mathbf{1}_{\delta}(\bm{\mu})$ is the $K$-dimensional cell defined as,

$\displaystyle\mathbf{1}_{\delta}(\bm{\mu})\triangleq\\{\bm{\xi}\in\mathbb{R}^{\mathrm{K}}:\xi_{i}\in(\mu_{i}-\delta,\mu_{i}+\delta)\;\forall
i\in[K]\\}.$

######  Remark 2.16.

As can be observed from Figure 1, larger the separation between the arms,
$\Delta_{i}=\mu^{*}-\mu_{i}$, the larger the $\delta$ one can choose so that
$\mathbf{1}_{\delta}(\bm{\mu})$ is contained in $\mathcal{C}_{k}$. Thus
instances with larger sub-optimality gaps are more interior, and hence more
robust. This observation leads us to think of $\delta$ as a measure of
robustness.

######  Remark 2.17.

The reason that we demand explicitly for $\bm{\mu}$ to be an interior point of
$\mathcal{C}_{k}$, is because $\mathcal{C}_{k}$ is not necessarily an open
set, as shown in Proposition 2.18 whose proof is deferred to the Appendix B.3.

######  Proposition 2.18.

The _robust observation region_ $\mathcal{C}_{k}$ is a $G_{\delta}$ set, that
is a countable intersection of open sets.

#####  $\varepsilon$-greedy algorithm

The $\varepsilon$-greedy algorithm is one of the more popular algorithms in
bandit and reinforcement learning literature Sutton and Barto (2018). We show
that if any bandit instance lies in a robust region then $\varepsilon$-greedy
is guaranteed to enjoy sub-linear regret. We present the result here
informally while deferring the full details in Appendix B.1

######  Theorem 2.19 (Sufficient Condition for Zero Regret in Misspecified
Bandits).

For a given feature matrix $\bm{\Phi}$ the $\varepsilon$-greedy algorithm with
$\varepsilon_{t}$ set as $1/\sqrt{t}$ achieves $O(\sqrt{T})$ regret for any
bandit instance belonging to the robust observation region.

We run some simple experiments to corroborate our theorem. We consider the set
of all $3$ armed bandits. We use a fixed $2$ dimensional linear model,
$\bm{\Phi}=\begin{bmatrix}2&3\\\ 4&5\\\ 2&1\\\ \end{bmatrix}$ for learning
this set of instances. We use Theorem 2.13 to explicitly calculate the robust
regions and sample $5$ instances from the robust region $\mathcal{C}_{2}$. We
observe from Figure 2 the mean and dispersion of the cumulative regret
generated by $\varepsilon$-greedy algorithm with $\varepsilon_{t}=1/\sqrt{t}$
of these sampled examples along with their misspecification error and their
minimum sub-optimality gap, $\Delta_{\min}$. In order to demonstrate our
results with high probability, we form confidence intervals of the cumulative
regret with three standard deviations. It is observed that the cumulative
regret along with the high confidence bands, grows at a sub-linear rate. We
also note that each of these instances are misspecified and we observe one
example where the misspecification error is greater than $\Delta_{\min}$. We
provide more details of the experiments in Appendix F.1.

Figure 2: The growth of the cumulative regret for $5$ misspecified bandit
instances generated by $\varepsilon$-greedy algorithm with
$\varepsilon_{t}=1/\sqrt{t}$. The plot represent the average of $10$ trials.
The $Y$-axis denotes the cumulative regret
$\sum_{t=1}^{T}\mu^{*}-\mu_{A_{t}}$. The $X$-axis denotes the rounds $T$. We
observe the sub-linear growth trend of the cumulative regret.

##### LinUCB

The LinUCB algorithm is a classic algorithm Abbasi-Yadkori et al. (2011) which
is known to be regret optimal in the perfect realizability setting. The
technical difficulty in the regret analysis of LinUCB is that while the
analysis of $\varepsilon$-greedy algorithm can be done entirely in the space
of the bandit instances $\bm{\mu}$, the analysis of the former needs to be
done in the parameter space. We present the informal result here while
deferring the details to Appendix C.

######  Theorem 2.20 (Sufficient Condition for Zero Regret in Misspecified
Bandits).

For a feature matrix $\Phi$ and it’s associated robust observation region
$\mathcal{C}_{k}$, the LinUCB algorithm achieves a regret of $O(d\sqrt{T})$ on
any bandit parameter $\bm{\mu}$ which in an interior point of the robust
observation region.

##### Comparison to the works of Liu et al. (2023)

The authors study the problem of misspecification under a robustness criterion
which characterizes the misspecification to be dominated by the sub-optimality
gap. Under such a condition, they show that LinUCB enjoys $O(\sqrt{T})$ regret
when the misspecification has low order, specifically, it is of order
$O\Big{(}\frac{1}{d\sqrt{\log{T}}}\Big{)}$. Note that this result is still
non-trivial, since the worst case regret for LinUCB under uniform model error
is $\rho T$, if $\rho$ is the misspecification error. However, we would like
to address the following points while comparing our work

  1. 1.

Our notion of robustness is significantly different from theirs as we are able
to show examples which achieve sub-linear regret even if the misspecification
error dominates the sub-optimality gap.

  2. 2.

For our analysis of LinUCB we do not require the assumption of low
misspecification error.

  3. 3.

We were able to analyse both $\varepsilon$-greedy and LinUCB under our notion
of robustness in both the bandit and the contextual setting. Our analysis of
LinUCB indicates that Thompson Sampling could be analysed as well under the
same robustness condition, whereas with their notion of robustness, they were
only able to analyse LinUCB under a low misspecification assumption.

###  2.2 Contextual Linear Bandits

##### Problem Statement

We consider the contextual bandit setting where contexts are drawn from a
finite set $\mathcal{X}$, and each context has finite arms in $\mathcal{A}$
giving rewards with means
$\\{\mu_{x,a}\\}_{(x,a)\in\mathcal{X}\times\mathcal{A}}$. We assume that each
context-arm pair $(x,a)$ is associated with a known feature $\varphi(x,a)$ in
$\mathbb{R}^{d}$. We also have an available parametric class of functions that
serves to (approximately) model the mean reward of each context-arm pair; each
function in this class is of the form $f_{\theta}:\mathbb{R}^{d}\to\mathbb{R}$
for a parameter $\theta\in\Theta$, and applying it to arm $a$ at context $x$
yields the expressed reward $f_{\theta}(\varphi(x,a))\in\mathbb{R}$.

##### Notation

We denote the context space size and the action space size by
$\left|\mathcal{X}\right|$ and $\left|\mathcal{A}\right|$, respectively. We
shall assume that the number of arms is larger than the dimension of the
parameter, that is $\left|\mathcal{A}\right|>d$ and, for ease of analysis,
consider the set of features
$\\{\varphi(x,a)\\}_{x\in\mathcal{X},a\in\mathcal{A}}$ to span
$\mathbb{R}^{d}$. We shall denote the true reward mean as a vector in
${\left|\mathcal{X}\mathcal{A}\right|}$-dimension,
$\bm{\mu}=\begin{bmatrix}\mu_{x,a}\end{bmatrix}_{x\in\mathcal{X},a\in\mathcal{A}}\in\mathbb{R}^{\left|\mathcal{X}\mathcal{A}\right|}$
and the feature matrix by
$\bm{\Phi}=\begin{bmatrix}\cdots\varphi(x,a)^{\top}\cdots\end{bmatrix}_{x\in\mathcal{X},a\in\mathcal{A}}$
an element in $\mathbb{R}^{\left|\mathcal{X}\mathcal{A}\right|\times d}$.
666By abuse of notation we will write
$\mathbb{R}^{\left|\mathcal{X}\mathcal{A}\right|}$ to denote the dimension of
the product space
$\mathbb{R}^{\left|\mathcal{X}\right|\left|\mathcal{A}\right|}$. We shall
denote by $\bm{\Phi_{x}}$, the context specific feature matrix, as the
$\left|\mathcal{A}\right|\times d$ sub-matrix of $\bm{\Phi}$ corresponding to
the features $[\varphi(x,a)]_{a\in\mathcal{A}}$ for a fixed context $x$.
Similarly we shall denote by $\bm{\mu_{x}}$, the context specific reward
vector, as the $\left|\mathcal{A}\right|$ dimensional sub-vector of $\bm{\mu}$
corresponding to the rewards $[\mu_{x,a}]_{a\in\mathcal{A}}$ for a fixed
context $x$.

######  Remark 2.21 (Linear Contextual bandits).

In linear contextual bandits Chu et al. (2011), it is assumed that the mean
rewards for a context-action pair $\mu_{x,a}$ is a linear function of the
features $\varphi(x,a)$, that is there exists a $\theta^{*}$ such that
$\bm{\mu}=\bm{\Phi}\theta^{*}$. Note that we make no such assumption.

##### Technical Definitions

We define analogous concepts as those introduced in the bandits setting for
the contextual setting. The critical observation is that we recover the multi-
armed bandit setup for any fixed context.

We define the greedy regions for any context $x\in\mathcal{X}$.

######  Definition 2.22 (Greedy Region $\mathcal{R}$ for context $x$).

Define by $\mathcal{R}^{x}_{a}$, for any context $x\in\mathcal{X}$ and any arm
$a\in\mathcal{A}$, as the region in $\mathbb{R}^{\left|\mathcal{A}\right|}$
for which the $a^{th}$ arm is the optimal arm at context $x$, that is

$\displaystyle\mathcal{R}^{x}_{a}\triangleq\Big{\\{}\bm{\mu_{x}}\in\mathbb{R}^{\mathcal{A}}:\mu_{x,a}>\mu_{x,b}\;\forall\;b\neq
a\Big{\\}}.$

For clarity, let us fix our model class to be linear, which results in the
least square estimate to have a closed-form solution given by,

$\displaystyle\widehat{\theta}_{t+1}=(\bm{\Phi}^{\top}\Lambda\bm{\Phi})^{-1}\bm{\Phi}^{\top}\Lambda\bm{\widehat{\mu}_{t}},$
(2)

where $\Lambda$ is a diagonal matrix of size
$\left|\mathcal{X}\mathcal{A}\right|\times\left|\mathcal{X}\mathcal{A}\right|$
consisting of the normalized sample frequencies
$\\{\alpha(x,a)\\}_{(x,a)\in\mathcal{X}\times\mathcal{A}}$ in the
$\left|\mathcal{X}\mathcal{A}\right|$ dimensional simplex
$\Delta_{\mathrm{XA}}$, and $\bm{\widehat{\mu}_{t}}$ is a vector in
$\mathbb{R}^{\left|\mathcal{X}\mathcal{A}\right|}$ consisting of the sample
estimates $\widehat{\mu}_{x,a,t}$, the sample mean of the observations from
context-arm pair $(x,a)$ till time $t$. 777Like in the bandit section, we
shall assume $\bm{\Phi}\Lambda\bm{\Phi}$ is invertible, which can be ensured
by a forced sampling of $d$ linearly independent features.

We define the _model estimate under a sampling distribution_ as

######  Definition 2.23 (Model Estimate under Sampling Distribution).

For any contextual bandit instance $\bm{\mu}$ in the
$\left|\mathcal{X}\mathcal{A}\right|$ dimensional space, we shall denote the
model estimate of the element $\bm{\mu}$ under any sampling distribution
$\Lambda=\mathrm{diag}(\\{\alpha(x,a)\\}_{(x,a)\in\mathcal{X}\times\mathcal{A}})$,
as

$\displaystyle\mathbf{P}^{\Lambda}(\bm{\mu})\triangleq\mathop{\mathrm{argmin}}_{\theta}\Big{\|}\bm{\Phi}\theta-\bm{\mu}\Big{\|}_{\Lambda^{1/2}}\;,$

where $\\{\alpha(x,a)\\}_{(x,a)\in\mathcal{X}\times\mathcal{A}}$ belongs to
the $\left|\mathcal{X}\mathcal{A}\right|$ dimensional simplex
$\Delta_{\mathrm{XA}}$.

Analogous to the bandits setting, we define the robust regions, namely _robust
parameter region_ and _robust observation region_ , for any arbitrary but
fixed context $x$.

######  Definition 2.24 (Robust Parameter Region for context $x$).

For a given feature matrix $\bm{\Phi}$ and a context $x$, define the $a^{th}$
_robust parameter region_ $\Theta^{x}_{a}$ as the set of all parameters
$\theta\in\mathbb{R}^{d}$ such that the range space of the context-specific
feature matrix, $\bm{\Phi_{x}}$, restricted to $\Theta^{x}_{a}$ lies in the
corresponding $(x,a)^{th}$ greedy region $\mathcal{R}^{x}_{a}$. That is,

$\displaystyle\Theta^{x}_{a}=\Big{\\{}\theta\in\mathbb{R}^{d}:\bm{\Phi_{x}}\theta\in\mathcal{R}^{x}_{a}\Big{\\}}\;\;\;\textit{for
any arm }a\in\mathcal{A}.$

######  Definition 2.25 (Robust Observation Region for context $x$).

For a given feature matrix $\bm{\Phi}$ and a context $x$, we define the
$a^{th}$ _robust observation region_ $\mathcal{C}^{x}_{a}$ as the set of all
$\left|\mathcal{X}\mathcal{A}\right|$ dimensional contextual bandit instances
$\bm{\mu}$ such that (i) the $\left|\mathcal{A}\right|$ armed bandit problem
at context $x$ has arm $a$ as the optimal and (ii) the model estimate
$\mathbf{P}^{\Lambda}(\bm{\mu})$ calculated under any sampling distribution
$\\{\alpha(x,a)\\}_{(x,a)\in\mathcal{X}\times\mathcal{A}}$ belongs in the
$(x,a)^{th}$ robust parameter region $\Theta^{x}_{a}$. That is,

$\mathcal{C}^{x}_{a}=\Big{\\{}\bm{\mu}\in\mathbb{R}^{\left|\mathcal{X}\mathcal{A}\right|}:\bm{\mu_{x}}\in\mathcal{R}^{x}_{a}\text{
and
}\mathbf{P}^{\Lambda}(\bm{\mu})\in\Theta^{x}_{a}\;\;\forall\;\;\Lambda\in\bm{\Lambda}\Big{\\}}\,,$

where

$\begin{split}\bm{\Lambda}=\Big{\\{}\Lambda=\mathrm{diag}(\\{\alpha(x,a)\\}_{(x,a)\in\mathcal{X}\times\mathcal{A}})\text{
such that }\\\
\\{\alpha(x,a)\\}_{(x,a)\in\mathcal{X}\times\mathcal{A}}\in\Delta_{\mathrm{XA}}\Big{\\}}.\end{split}$

With the help of these definitions we arrive at a sufficient condition for
robustness: any contextual bandit $\bm{\mu}$ that belongs in a robust
observation region, the _noiseless_ model estimate,
$\mathbf{P}^{\Lambda}(\bm{\mu})-$ computed under any sampling distribution$-$
would cause the greedy algorithm to be consistently optimal at every context.

######  Theorem 2.26.

Define
$\mathcal{C}^{\mathcal{X}}\triangleq\bigcap_{x\in\mathcal{X}}\mathcal{C}^{x}_{\mathrm{OPT}(x)}$.
If a contextual bandit instance $\bm{\mu}$ belongs in the robust region
$\mathcal{C}^{\mathcal{X}}$ then
$\bm{\Phi_{x}}\mathbf{P}^{\Lambda}(\bm{\mu})\in\mathcal{R}^{x}_{\mathrm{OPT}(x)}\;\forall
x\in\mathcal{X}$ under any sampling distribution
$\\{\alpha(x,a)\\}_{(x,a)\in\mathcal{X}\times\mathcal{A}}\in\Delta_{\mathrm{XA}}$.

###### Proof.

If $\bm{\mu}\in\mathcal{C}^{\mathcal{X}}$, then
$\bm{\mu}\in\mathcal{C}^{x}_{\mathrm{OPT}(x)}$ for every context $x$. This
implies, from the definition of $\mathcal{C}^{x}_{\mathrm{OPT}(x)}$, that
$\bm{\mu_{x}}\in\mathcal{R}^{x}_{\mathrm{OPT}(x)}$ and
$\mathbf{P}^{\Lambda}(\bm{\mu})\in\Theta^{x}_{\mathrm{OPT}(x)}$ for any
sampling distribution
$\\{\alpha(x,a)\\}_{(x,a)\in\mathcal{X}\times\mathcal{A}}$ and for every
context $x$. This implies, from the definition of
$\Theta^{x}_{\mathrm{OPT}(x)}$, that
$\bm{\Phi_{x}}\mathbf{P}^{\Lambda}(\bm{\mu})\in\mathcal{R}^{x}_{\mathrm{OPT}(x)}$
under any sampling distribution
$\\{\alpha(x,a)\\}_{(x,a)\in\mathcal{X}\times\mathcal{A}}$ and for every
context $x\in\mathcal{X}$. Therefore the greedy algorithm is guaranteed to
play optimally at every context. ∎

As a corollary we can show that the model estimate
$\mathbf{P}^{\Lambda}(\bm{\mu})$ computed under any sampling distribution
$\\{\alpha(x,a)\\}_{(x,a)\in\mathcal{X}\times\mathcal{A}}$ must belong to the
robust parameter region $\Theta^{x}_{\mathrm{OPT}(x)}$ for every context $x$.
We present the proof of it in Appendix B.6.

######  Corollary 2.27.

For any contextual bandit instance $\bm{\mu}$, we have
$\bm{\mu}\in\mathcal{C}^{\mathcal{X}}$ if and only if the model estimate
$\mathbf{P}^{\Lambda}(\bm{\mu})$, computed under any sampling distribution
$\\{\alpha(x,a)\\}_{(x,a)\in\mathcal{X}\times\mathcal{A}}\in\Delta_{\mathrm{XA}}$,
belongs to $\Theta^{\mathcal{X}}$, where
$\Theta^{\mathcal{X}}\triangleq\bigcap_{x\in\mathcal{X}}\Theta^{x}_{\mathrm{OPT}(x)}$.

######  Remark 2.28.

We shall refer to $\mathcal{C}^{\mathcal{X}}$ and $\Theta^{\mathcal{X}}$, as
defined above, as the _robust observation region_ and _robust parameter
region_ respectively.

##### Characterization of the Robust Observation Region

For the linear model class we can use Lemma H.4 to characterize the _Robust
Observation Region_ , $\mathcal{C}^{\mathcal{X}}$, in a manner analogous to
the bandit setting in Theorem 2.13.

######  Theorem 2.29.

For any contextual bandit instance $\bm{\mu}$ we have, $\bm{\mu}$ belongs to
the _robust observation region_ $\mathcal{C}^{\mathcal{X}}$ if and only if for
each $d\times d$ full rank sub-matrix of $\bm{\Phi}$, denoted by $\Phi_{d}$,
along with the corresponding $d$ rows of $\bm{\mu}$, denoted as
$\bm{\mu}_{d}$, satisfy $\Phi_{d}^{-1}\bm{\mu}_{d}\in\Theta^{\mathcal{X}}$.
That is for any $\bm{\mu}$

$\displaystyle\bm{\mu}\in\mathcal{C}^{\mathcal{X}}\iff\Phi_{d}^{-1}\bm{\mu}_{d}\in\Theta^{\mathcal{X}}\;$

for all $d\times d$ full rank sub-matrices of $\bm{\Phi}$ (denoted as
$\Phi_{d}$) and the corresponding $d$ rows of $\bm{\mu}$ (denoted as
$\bm{\mu}_{d}$).

The proof of Theorem 2.29 is presented in Appendix B.7.

##### Sufficient Condition

We show that under the assumption of sub-Gaussian noise and a technical
assumption of the true contextual instance being an interior point of the
robust observation region, $\varepsilon$-greedy and LinUCB algorithm is able
to achieve sub-linear regret.

######  Assumption 2.30 (sub-Gaussian Observations).

We shall assume that for any context $x$, the $\left|\mathcal{A}\right|$ armed
bandit instance $\bm{\mu_{x}}$ is $1/2\text{ sub-Gaussian}$.

We also assume that every context has a positive probability of observation.

######  Assumption 2.31 (Context Distribution).

Each context $x\in\mathcal{X}$ has positive probability $\mathbf{p}_{x}$ of
observation.

Similar to the bandit setting, since the robust observation region is not
necessarily an open set, we require explicitly for the contextual bandit
instance to be an interior point of the robust observation region, where we
define the open sets in the $\left|\mathcal{X}\mathcal{A}\right|$ dimensional
space as open rectangles.

######  Definition 2.32 (Interior Point).

$\bm{\mu}$ is an interior point of $\mathcal{C}^{\mathcal{X}}$ if and only if
there exists a $\delta>0$, such the
$\left|\mathcal{X}\mathcal{A}\right|$-dimensional cell, with size $\delta$ and
centre $\bm{\mu}$, is a subset of $\mathcal{C}^{\mathcal{X}}$. That is,

$\displaystyle\bm{\mu}\in\mathrm{Int}(\mathcal{C}^{\mathcal{X}})\iff\exists\;\delta>0\;s.t.\;\mathbf{1}_{\delta}(\bm{\mu})\subset\mathcal{C}^{\mathcal{X}},$

where $\mathbf{1}_{\delta}(\bm{\mu})$ is the
$\left|\mathcal{X}\mathcal{A}\right|$-dimensional cell in
$\mathbb{R}^{\left|\mathcal{X}\mathcal{A}\right|}$ topology defined as,

$\displaystyle\mathbf{1}_{\delta}(\bm{\mu})\triangleq\\{\bm{\xi}\in\mathbb{R}^{\left|\mathcal{X}\mathcal{A}\right|}:\xi_{i}\in(\mu_{i}-\delta,\mu_{i}+\delta)\;\forall
i\in[\left|\mathcal{X}\mathcal{A}\right|]\\}.$

#####  $\varepsilon$-greedy Algorithm

The $\varepsilon$-greedy algorithm is arguably the simplest and one of the
most popular algorithms in bandits and reinforcement learning. We show that if
a contextual bandit belongs to the robust region then the $\varepsilon$-greedy
algorithm is able to achieve sub-linear regret. We present the result
informally here, while presenting it in detail in Appendix B.4.

######  Theorem 2.33 (Sufficient Condition for Zero Regret in Misspecified
Contextual Bandits).

For a given feature matrix $\bm{\Phi}$ the $\varepsilon$-greedy algorithm with
$\varepsilon_{t}$ set as $1/\sqrt{t}$ achieves a regret of $O(\sqrt{T})$ for
any contextual bandit instance belonging to the robust observation region.

######  Remark 2.34.

The regret analysis similar to one in the bandit setting, where we control the
number of times any sub-optimal arm is sampled, while allowing sufficient
exploration so that the estimates converge within the robust region.

We run some simple experiments to corroborate our findings. We consider the
set of all $2$ context bandits, each having $3$ arms and fix the context
distribution to be uniform. We use a fixed $2$ dimensional linear model,
$\bm{\Phi_{x_{1}}}=\begin{bmatrix}2&3\\\ 4&5\\\ 2&1\\\ \end{bmatrix}$ and
$\bm{\Phi_{x_{2}}}=\begin{bmatrix}2&3\\\ 4&5\\\ 6&7\end{bmatrix}$
corresponding to the two contexts for learning this set of instances. We use
Theorem 2.29 to explicitly calculate the robust regions and sample $5$
instances from the robust region
$\mathcal{C}^{x_{1}}_{1}\cap\mathcal{C}^{x_{2}}_{1}$. We observe from Figure 3
the mean and dispersion of the cumulative regret of these sampled examples
along with their misspecification error and their minimum sub-optimality gap,
$\Delta_{\min}$ generated by $\varepsilon$-greedy algorithm with
$\varepsilon_{t}=1/\sqrt{t}$. In order to demonstrate our results with high
probability, we form confidence intervals of the cumulative regret with three
standard deviations. It is observed that the cumulative regret along with the
high confidence bands, is sub-linear. We also note that each of these
instances are misspecified and we observe one example where the
misspecification error is greater than $\Delta_{\min}$. We provide more
details of the experiments in Appendix F.2.

Figure 3: The growth of the cumulative regret for $5$ misspecified contextual
instances generated by $\varepsilon$-greedy algorithm with
$\varepsilon_{t}=1/\sqrt{t}$. The plot represent the average of $10$ trials.
The $Y$-axis denotes the cumulative regret
$\sum_{t=1}^{T}\mu^{*}_{t}-\mu_{A_{t}}$. The $X$-axis denotes the rounds $T$.
We observe the sub-linear growth trend of the cumulative regret.

##### LinUCB

Our robustness definition is used to analyze LinUCB in the contextual setting
as well. We present the theorem here informally, deferring the details to
Appendix D.

######  Theorem 2.35.

For a given feature matrix $\bm{\Phi}$ the LinUCB algorithm achieves a regret
of $O(\sqrt{T})$ for any contextual bandit instance belonging to the robust
observation region.

######  Remark 2.36.

The proof of the theorem essentially follows the proof of the LinUCB algorithm
for the bandit setting as presented in Appendix C and is presented in Theorem
D.9.

##### Comparison to Zhang et al. (2023)

The authors have studied misspecified contextual bandits with the
misspecification dominated by the minimum sub-optimality gap. In this regard,
we believe this is more in line with the work of Liu et al. (2023). Under this
robustness criterion, they developed a sophisticated algorithm, DS-OFUL, which
they analyzed to be regret optimal. In terms of the characterization of
robustness, we believe that it is not comparable to our work. For example, we
are able to analyze problems whose misspecification error is larger than the
sub-optimality gap. This is also corroborated in our experiment, as shown in
Figure 3, where we see the last example has a misspecification error larger
than the sub-optimality gap. Moreover, while they analyzed a highly
sophisticated algorithm with their definition of robustness, we were able to
analyze much simpler algorithms with our theory of robustness.

## References

  * Abbasi-Yadkori et al. (2011) Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári.  Improved algorithms for linear stochastic bandits.  In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger, editors, _Advances in Neural Information Processing Systems_ , volume 24, pages 2312–2320. Curran Associates, Inc., 2011.
  * Abeille and Lazaric (2017) Marc Abeille and Alessandro Lazaric.  Linear Thompson Sampling Revisited.  In Aarti Singh and Jerry Zhu, editors, _Proceedings of the 20th International Conference on Artificial Intelligence and Statistics_ , volume 54 of _Proceedings of Machine Learning Research_ , pages 176–184. PMLR, 20–22 Apr 2017.  URL https://proceedings.mlr.press/v54/abeille17a.html.
  * Agrawal and Goyal (2012) Shipra Agrawal and Navin Goyal.  Analysis of thompson sampling for the multi-armed bandit problem.  In Shie Mannor, Nathan Srebro, and Robert C. Williamson, editors, _Proceedings of the 25th Annual Conference on Learning Theory_ , volume 23 of _Proceedings of Machine Learning Research_ , pages 39.1–39.26, Edinburgh, Scotland, 25–27 Jun 2012. PMLR.  URL https://proceedings.mlr.press/v23/agrawal12.html.
  * Agrawal and Goyal (2013) Shipra Agrawal and Navin Goyal.  Thompson sampling for contextual bandits with linear payoffs.  In Sanjoy Dasgupta and David McAllester, editors, _Proceedings of the 30th International Conference on Machine Learning_ , volume 28 of _Proceedings of Machine Learning Research_ , pages 127–135, Atlanta, Georgia, USA, 17–19 Jun 2013. PMLR.  URL https://proceedings.mlr.press/v28/agrawal13.html.
  * Auer (2002) Peter Auer.  Using confidence bounds for exploitation-exploration trade-offs.  _Journal of Machine Learning Research_ , 3(Nov):397–422, 2002.
  * Auer et al. (2002) Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer.  Finite-time analysis of the multiarmed bandit problem.  _Machine learning_ , 47:235–256, 2002.
  * Box (1976) George EP Box.  Science and statistics.  _Journal of the American Statistical Association_ , 71(356):791–799, 1976.
  * Chu et al. (2011) Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire.  Contextual bandits with linear payoff functions.  In _Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics_ , pages 208–214. JMLR Workshop and Conference Proceedings, 2011.
  * Dani et al. (2008) Varsha Dani, Thomas P Hayes, and Sham M Kakade.  Stochastic linear optimization under bandit feedback.  2008\.
  * Filippi et al. (2010) Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári.  Parametric bandits: The generalized linear case.  _Advances in neural information processing systems_ , 23, 2010.
  * Forsgren (1996) Anders Forsgren.  On linear least-squares problems with diagonally dominant weight matrices.  _SIAM Journal on Matrix Analysis and Applications_ , 17(4):763–788, 1996.  doi: 10.1137/S0895479895284014.
  * Foster and Rakhlin (2020) Dylan Foster and Alexander Rakhlin.  Beyond UCB: Optimal and efficient contextual bandits with regression oracles.  In Hal Daumé III and Aarti Singh, editors, _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 3199–3210. PMLR, 13–18 Jul 2020.  URL https://proceedings.mlr.press/v119/foster20a.html.
  * Ghosh et al. (2017) Avishek Ghosh, Sayak Ray Chowdhury, and Aditya Gopalan.  Misspecified linear bandits.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 31, 2017.
  * Gopalan et al. (2016) Aditya Gopalan, Odalric-Ambrym Maillard, and Mohammadi Zaki.  Low-rank bandits with latent mixtures.  _arXiv preprint arXiv:1609.01508_ , 2016.
  * Jin et al. (2020) Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan.  Provably efficient reinforcement learning with linear function approximation.  In _Conference on Learning Theory_ , pages 2137–2143. PMLR, 2020.
  * Kumar Krishnamurthy et al. (2021) Sanath Kumar Krishnamurthy, Vitor Hadad, and Susan Athey.  Tractable contextual bandits beyond realizability.  In Arindam Banerjee and Kenji Fukumizu, editors, _Proceedings of The 24th International Conference on Artificial Intelligence and Statistics_ , volume 130 of _Proceedings of Machine Learning Research_ , pages 1423–1431. PMLR, 13–15 Apr 2021.  URL https://proceedings.mlr.press/v130/kumar-krishnamurthy21a.html.
  * Lattimore and Szepesvári (2020) Tor Lattimore and Csaba Szepesvári.  _Bandit algorithms_.  Cambridge University Press, 2020.
  * Lattimore et al. (2020) Tor Lattimore, Csaba Szepesvari, and Gellert Weisz.  Learning with good feature representations in bandits and in RL with a generative model.  In Hal Daumé III and Aarti Singh, editors, _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 5662–5670. PMLR, 13–18 Jul 2020.  URL https://proceedings.mlr.press/v119/lattimore20a.html.
  * Lillicrap et al. (2015) Timothy P Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra.  Continuous control with deep reinforcement learning.  _arXiv preprint arXiv:1509.02971_ , 2015.
  * Liu et al. (2023) Chong Liu, Ming Yin, and Yu-Xiang Wang.  No-regret linear bandits beyond realizability.  In Robin J. Evans and Ilya Shpitser, editors, _Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence_ , volume 216 of _Proceedings of Machine Learning Research_ , pages 1294–1303. PMLR, 31 Jul–04 Aug 2023.  URL https://proceedings.mlr.press/v216/liu23c.html.
  * Mnih et al. (2013) Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller.  Playing atari with deep reinforcement learning.  _arXiv preprint arXiv:1312.5602_ , 2013.
  * Rusmevichientong and Tsitsiklis (2010) Paat Rusmevichientong and John N Tsitsiklis.  Linearly parameterized bandits.  _Mathematics of Operations Research_ , 35(2):395–411, 2010.
  * Sutton and Barto (2018) Richard S Sutton and Andrew G Barto.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Zanette et al. (2020) Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill.  Learning near optimal policies with low inherent bellman error.  In _International Conference on Machine Learning_ , pages 10978–10989. PMLR, 2020.
  * Zhang et al. (2023) Weitong Zhang, Jiafan He, Zhiyuan Fan, and Quanquan Gu.  On the interplay between misspecification and sub-optimality gap in linear contextual bandits.  In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, _Proceedings of the 40th International Conference on Machine Learning_ , volume 202 of _Proceedings of Machine Learning Research_ , pages 41111–41132. PMLR, 23–29 Jul 2023.  URL https://proceedings.mlr.press/v202/zhang23n.html.

##  Appendix A Errata

We noticed that we had used a notation in the contextual bandit section 2.2
that first appeared in Theorem 2.26, which we have not defined formally.
Though we believe that the notation is self-explanatory, we admit it was an
overlook on our behalf. The notation in question is $\mathrm{OPT}(x)$ for a
context $x$. This notation represents the optimal arm at context $x$. To be
formally correct, we define

$\displaystyle\mathrm{OPT}:\mathbb{R}^{\left|\mathcal{A}\right|}\to\mathcal{A}\;\text{
as }$
$\displaystyle\mathrm{OPT}(\bm{\mu})=\mathop{\mathrm{argmax}}_{a\in\mathcal{A}}\mu_{a}\;,$

to represent the optimal arm for an $\left|\mathcal{A}\right|$ armed bandit
problem. Similarly for the contextual setting given any fixed context $x$ and
it’s corresponding context-specific reward vector $\bm{\mu_{x}}$, we have

$\displaystyle\mathrm{OPT}:\mathbb{R}^{\left|\mathcal{A}\right|}\to\mathcal{A}\;\text{
as }$
$\displaystyle\mathrm{OPT}(\bm{\mu_{x}})=\mathop{\mathrm{argmax}}_{a\in\mathcal{A}}\mu_{x,a}\;.$

to denote the optimal arm at context $x$. We abuse notation and write
$\mathrm{OPT}(x)$ to denote $\mathrm{OPT}(\bm{\mu_{x}})$ as the optimal arm at
context $x$.

##  Appendix B Description of Algorithms and Proofs of Theorems

In this section we provide the proofs of all theorems presented in the main
paper.

###  B.1 Bandits

#####  $\varepsilon$-greedy

$\varepsilon$-greedy algorithm is a popular forced-exploration based algorithm
widely used in practice. We describe it in Algorithm 1 for the sake of
completeness.

Algorithm 1 $\varepsilon$-greedy algorithm

1: for t = 1 to T do

2: With an estimate $\widehat{\theta}_{t}$, play arm $i$ such that
$\displaystyle A_{t}$
$\displaystyle=\mathop{\mathrm{argmax}}_{i\in[K]}\varphi_{i}^{\top}\widehat{\theta}_{t}\;\mathrm{w.p.}\;1-\varepsilon_{t}$
$\displaystyle=\textit{play uniformly over }K\textit{
arms}\;\mathrm{w.p.}\;\varepsilon_{t}$

3: Observe the reward $Y_{t}$.

4: Update the estimate as
$\displaystyle\widehat{\theta}_{t+1}=\mathop{\mathrm{argmin}}_{\theta}\sum_{s=1}^{t}[\varphi_{A_{s}}^{\top}\theta-
Y_{s}]^{2}$

5: end for

We give a detailed description and proof of the result presented in Theorem
2.19.

######  Theorem B.1 (Sufficient Condition for Zero Regret in Misspecified
Bandits).

For a feature matrix $\bm{\Phi}$, and it’s associated robust observation
region $\mathcal{C}_{k}$, any $\frac{1}{2}\text{ sub-Gaussian}$ bandit
parameter $\bm{\mu}$ which is an interior point of the robust observation
region, that is $\bm{\mu}\in\mathrm{Int}(\mathcal{C}_{k})$, the
$\varepsilon$-greedy algorithm with $\varepsilon_{t}$ set as
$\frac{1}{\sqrt{t}}$, achieves a regret of $O(\Delta_{\max}\sqrt{T})$, where
$\Delta_{\max}$ is the largest sub-optimal gap, that is
$\Delta_{\max}=\max_{i\in[K]}\mu_{k}-\mu_{i}$.

######  Remark B.2.

The proof essentially uses the same technique as presented in Auer et al.
(2002). The key observation is that the least squares estimate
$\widehat{\theta}_{t}$, in our notation
$\mathbf{P}^{\Lambda}(\bm{\widehat{\mu}_{t}})$, is guaranteed to generate
optimal play under the greedy strategy, if the sample mean estimate
$\bm{\widehat{\mu}_{t}}$ falls inside the robust region $\mathcal{C}_{k}$. The
concentration of sub-Gaussian random variables ensure that given enough
samples $\bm{\widehat{\mu}_{t}}$ will fall within a $\delta$-neighbourhood of
the true rewards $\bm{\mu}$. The fact that $\bm{\mu}$ is an interior point of
$\mathcal{C}_{k}$, ensures a that there exists $\delta$\- neighbourhood about
$\bm{\mu}$ that is contained in the robust region $\mathcal{C}_{k}$.

###### Proof.

Since $\bm{\mu}$ is an interior point of the robust region $\mathcal{C}_{k}$,
by Definition 2.15, there exists a $\delta$-cell centred at $\bm{\mu}$,
denoted as $\mathbf{1}_{\delta}(\bm{\mu})$ which is contained in the robust
observation region $\mathcal{C}_{k}$. We observe that the probability of
choosing a sub-optimal arm $i$ at $t^{th}$ round is either due to a random
play, which happens with probability $\frac{\varepsilon_{t}}{K}$ or during the
greedy play, when the reward estimate $\bm{\widehat{\mu}_{t}}$ does not belong
to $\mathbf{1}_{\delta}(\mu)$, the $\delta$ cell of $\bm{\mu}$. That is,

$\displaystyle\mathbb{P}\left[{A_{t}=i}\right]\leqslant\frac{\varepsilon_{t}}{K}+(1-\frac{\varepsilon_{t}}{K})\mathbb{P}\left[{\bm{\widehat{\mu}_{t}}\notin\mathbf{1}_{\delta}(\bm{\mu})}\right].$

Now
$\mathbb{P}\left[{\bm{\widehat{\mu}_{t}}\notin\mathbf{1}_{\delta}(\bm{\mu})}\right]$,
from the definition of the $\delta$-cell, can be upper bounded by taking a
union bound over all arms to give

$\displaystyle\mathbb{P}\left[{\bm{\widehat{\mu}_{t}}\notin\mathbf{1}_{\delta}(\bm{\mu})}\right]\leqslant\sum_{i=1}^{K}\mathbb{P}\left[{|\widehat{\mu}_{i}^{n_{i,t}}-\mu_{i}|\geqslant\delta}\right]\;,$

where $\widehat{\mu}_{i}^{n_{i,t}}$ is the sample estimate of arm $i$, having
played $n_{i,t}$ times till time $t$. The remainder of the proof has the same
flavour as in the work of Auer et al. (2002). We provide here for the sake of
completeness. Note that each term
$\mathbb{P}\left[{|\widehat{\mu}_{i}^{n_{i,t}}-\mu_{i}|\geqslant\delta}\right]$
can be bounded in the following manner,

$\displaystyle\mathbb{P}\Big{\\{}|\widehat{\mu}_{i}^{n_{i,t}}-\mu_{i}|\geqslant\delta\Big{\\}}=\sum_{s=1}^{t}\mathbb{P}\Big{\\{}|\widehat{\mu}_{i}^{s}-\mu_{i}|\geqslant\delta,n_{i,t}=s\Big{\\}}$
$\displaystyle=\sum_{s=1}^{t}\mathbb{P}\Big{\\{}n_{i,t}=s\mid\left|\widehat{\mu}_{i}^{s}-\mu_{i}\right|\geqslant\delta\Big{\\}}\mathbb{P}\Big{\\{}|\widehat{\mu}_{i}^{s}-\mu_{i}|\geqslant\delta\Big{\\}}$
$\displaystyle\leqslant\sum_{s=1}^{t}\mathbb{P}\Big{\\{}n_{i,t}=s\mid\left|\widehat{\mu}_{i}^{s}-\mu_{i}\right|\geqslant\delta\Big{\\}}2\exp{(-2s\delta^{2})},$

where we use the sub-Gaussian concentration by Assumption 2.14 and Lemma H.5,

$\displaystyle\leqslant\sum_{s=1}^{t_{0}}\mathbb{P}\Big{\\{}n_{i,t}=s\mid\left|\widehat{\mu}_{i}^{s}-\mu_{i}\right|\geqslant\delta\Big{\\}}+\sum_{s=t_{0}+1}^{t}2\exp{(-2s\delta^{2})}$
$\displaystyle\leqslant\sum_{s=1}^{t_{0}}\mathbb{P}\Big{\\{}n_{i,t}=s\mid\left|\widehat{\mu}_{i}^{s}-\mu_{i}\right|\geqslant\delta\Big{\\}}+\frac{1}{\delta^{2}}\exp{(-2t_{0}\delta^{2})}\;,$

where we use the identity $\sum_{t=x+1}^{\infty}\exp(-\kappa
t)\leqslant\frac{1}{\kappa}\exp(-\kappa x)$. Let $n_{i,t}^{R}$ be the number
of times arm $i$ has been played randomly till time $t$, then,

$\displaystyle\sum_{s=1}^{t_{0}}\mathbb{P}\Big{\\{}n_{i,t}=s\mid\left|\widehat{\mu}_{i}^{s}-\mu_{i}\right|\geqslant\delta\Big{\\}}$
$\displaystyle\leqslant\sum_{s=1}^{t_{0}}\mathbb{P}\Big{\\{}n_{i,t}^{R}\leqslant
s\mid\left|\widehat{\mu}_{i}^{s}-\mu_{i}\right|\geqslant\delta\Big{\\}}$
$\displaystyle\leqslant\sum_{s=1}^{t_{0}}\mathbb{P}\\{n_{i,t}^{R}\leqslant
s\\}$ $\displaystyle\leqslant t_{0}\mathbb{P}\\{n_{i,t}^{R}\leqslant
t_{0}\\}.$

Now

$\displaystyle\mathbb{E}\left[{n_{i,t}^{R}}\right]=\frac{1}{K}\sum_{s=1}^{t}\varepsilon_{s}$

and variance of $n_{i,t}^{R}$ is

$\displaystyle\mathbb{V}[n_{i,t}^{R}]=\sum_{s=1}^{t}\frac{\varepsilon_{s}}{K}\Big{(}1-\frac{\varepsilon_{s}}{K}\Big{)}\leqslant\sum_{s=1}^{t}\frac{\varepsilon_{s}}{K}.$

Thus, choosing $t_{0}=\frac{1}{2K}\sum_{s=1}^{t}\varepsilon_{s}$, we have

$\displaystyle\mathbb{P}\\{n_{i,t}^{R}\leqslant
t_{0}\\}\leqslant\exp(-t_{0}/5)\;,$

from Bernstein’s Inequality, Lemma H.6. Thus putting it all together we have,

$\displaystyle\mathbb{P}\left[{A_{t}=i}\right]\leqslant\frac{\varepsilon_{t}}{K}+Kt_{0}\exp(-t_{0}/5)+\frac{K}{\delta^{2}}\exp{(-2t_{0}\delta^{2})}.$

Thus, in order to complete the proof we only need to find a lower bound on
$t_{0}$. As per our definition,

$\displaystyle t_{0}$
$\displaystyle=\frac{1}{2K}\sum_{s=1}^{t}\varepsilon_{s}.$

Plugging the value of $\varepsilon_{s}=1/\sqrt{s}$, we get

$\displaystyle t_{0}$
$\displaystyle=\frac{1}{2K}\sum_{s=1}^{t}\frac{1}{\sqrt{s}}$
$\displaystyle\geqslant\frac{1}{K}(\sqrt{t+1}-1).$

Thus,

$\displaystyle\mathbb{P}\left[{A_{t}=i}\right]\leqslant\frac{1}{K\sqrt{t}}+(\sqrt{t+1}-1)\exp(-\frac{\sqrt{t+1}-1}{5K})+\frac{K}{\delta^{2}}\exp{\Big{(}-\frac{2\delta^{2}(\sqrt{t+1}-1)}{K}\Big{)}}.$

Therefore regret at any time $t$ is

$\displaystyle\mathrm{Regret_{t}}=\sum_{i=1}^{K}\Delta_{i}\mathbb{P}\left[{A_{t}=i}\right]\leqslant\frac{\Delta_{\max}}{\sqrt{t}}+o(1/t),$

where $\Delta_{i}$ is the sub-optimality gap $\mu_{k}-\mu_{i}$. Thus
cumulative regret is
$\sum_{t=1}^{T}\mathrm{Regret}_{t}=O(\Delta_{\max}\sqrt{T})$. ∎

We prove Proposition 2.18, that was presented in the main paper. To recall we
shall show that the _robust observation region_ is not an open set.

######  Proposition B.3.

The _robust observation region_ $\mathcal{C}_{k}$ is a $G_{\delta}$ set, that
is a countable intersection of open sets.

###### Proof.

Note that the for any arbitrary but fixed sampling distribution
$\\{\alpha(i)\\}_{i=1}^{K}$ belonging in the $K$ dimensional simplex
$\Delta_{\mathrm{K}}$, we have

$\displaystyle\Big{\\{}\bm{\mu}\in\mathcal{R}_{k}:\mathbf{P}^{\Lambda}(\bm{\mu})\in\Theta_{k}\Big{\\}}\;,$

is an open set as the set $\Theta_{k}$ is an open set and the projection
operator is continuous. Now, since any sampling distribution
$\\{\alpha(i)\\}_{i=1}^{K}$ are rationals, that is
$\\{\alpha(i)\\}_{i=1}^{K}\in\mathbb{Q}^{\mathrm{K}}$, we have

$\displaystyle\mathcal{C}_{k}\triangleq\bigcap_{\\{\alpha(i)\\}_{i=1}^{K}\in\Delta_{\mathrm{K}}}\Big{\\{}\mu\in\mathcal{R}_{k}:\mathbf{P}^{\Lambda}(\bm{\mu})\in\Theta_{k}\Big{\\}}\;,$

is a $G_{\delta}$ set. ∎

###  B.2 Contextual Bandits

The $\varepsilon$-greedy algorithm in the contextual setup is described in
Algorithm 2 for the sake of completeness.

Algorithm 2 Generic $\varepsilon$-greedy algorithm

1: for t = 1 to T do

2: Observe context $X_{t}$ at time $t$

3: With an estimate $\widehat{\theta}_{t}$, play arm $A_{t}$ such that
$\displaystyle A_{t}$
$\displaystyle=\mathop{\mathrm{argmax}}_{a\in\mathcal{A}}\varphi(X_{t},a)^{\top}\widehat{\theta}_{t}\;\mathrm{w.p.}\;1-\varepsilon_{t}$
$\displaystyle=\textit{play uniformly over }\mathcal{A}\textit{
arms}\;\mathrm{w.p.}\;\varepsilon_{t}$

4: Observe the reward $Y_{t}$.

5: Update the estimate as
$\displaystyle\widehat{\theta}_{t+1}=\mathop{\mathrm{argmin}}_{\theta}\sum_{s=1}^{t}[\varphi(X_{s},A_{s})^{\top}\theta-
Y_{s}]^{2}.$

6: end for

We now give a detailed description and proof of the result presented in
Theorem 2.33.

######  Theorem B.4 (Sufficient Condition for Zero Regret in Misspecified
Contextual Bandits).

For a given feature matrix $\Phi$, any $\frac{1}{2}\text{ sub-Gaussian}$
contextual bandit instance $\bm{\mu}$ which is an interior point of the robust
observation region, that is $\bm{\mu}\in\mathrm{Int}(\mathcal{C}^{cX})$, the
$\varepsilon$-greedy algorithm with $\varepsilon_{t}$ set as
$\frac{1}{\sqrt{t}}$, achieves a regret of $O(\Delta_{\max}\sqrt{T})$, where
$\Delta_{\max}=\max_{x\in\mathcal{X},a\in\mathcal{A}}\Delta_{x,a}$ and
$\Delta_{x,a}=\mu_{x,\mathrm{OPT}(x)}-\mu_{x,a}$

######  Remark B.5.

The proof essentially uses the same technique as presented in the proof for
the bandits section. The key observation is that the least squares estimate
$\widehat{\theta}_{t}$, in our notation
$\mathbf{P}^{\Lambda}(\bm{\widehat{\mu}_{t}})$, is guaranteed to generate
optimal play under the greedy strategy, if the sample mean estimate
$\bm{\widehat{\mu}_{t}}$ falls inside the robust region
$\mathcal{C}^{\mathcal{X}}$. The concentration of sub-Gaussian random
variables ensure that given enough samples $\bm{\widehat{\mu}_{t}}$ will fall
within a $\delta$-neighbourhood of the true rewards $\bm{\mu}$. The fact that
$\bm{\mu}$ is an interior point of $\mathcal{C}^{\mathcal{X}}$, ensures a that
there exists $\delta$\- neighbourhood about $\bm{\mu}$ that is contained in
the robust region $\mathcal{C}^{\mathcal{X}}$.

###### Proof.

Since $\bm{\mu}$ is an interior point of the robust region
$\mathcal{C}^{\mathcal{X}}$, by Definition 2.32, there exists a $\delta$-cell
centred at $\bm{\mu}$, defined as $\mathbf{1}_{\delta}(\bm{\mu})$ which is
contained in the robust observation region $\mathcal{C}^{\mathcal{X}}$. The
probability of choosing a sub-optimal arm $a$ in state $x$ at $t^{th}$ round
is either due to a random play, which happens with probability
$\frac{\varepsilon_{t}}{\left|\mathcal{A}\right|}$ or, during the greedy play,
the reward estimate
$\bm{{\widehat{\mu}_{t}}}\in\mathbb{R}^{\left|\mathcal{X}\mathcal{A}\right|}$
does not belong to the $\delta$ cell of $\bm{\mu}$,
$\mathbf{1}_{\delta}(\bm{\mu})$. That is,

$\displaystyle\mathbb{P}\left[{A_{t}=a\mid
X_{t}=x}\right]\leqslant\frac{\varepsilon_{t}}{\left|\mathcal{A}\right|}+(1-\frac{\varepsilon_{t}}{\left|\mathcal{A}\right|})\mathbb{P}\left[{\bm{\widehat{\mu}_{t}}\notin\mathbf{1}_{\delta}(\bm{\mu})}\right].$

Now
$\mathbb{P}\left[{\bm{\widehat{\mu}_{t}}\notin\mathbf{1}_{\delta}(\bm{\mu})}\right]$,
from the definition of the $\delta$-cell, can be upper bounded by taking a
union bound over all arms and contexts to give

$\displaystyle\mathbb{P}\left[{\bm{\widehat{\mu}_{t}}\notin\mathbf{1}_{\delta}(\bm{\mu})}\right]\leqslant\sum_{a\in\mathcal{A}}\sum_{x\in\mathcal{X}}\mathbb{P}\left[{|\widehat{\mu}_{x,a}^{n_{x,a,t}}-\mu_{x,a}|\geqslant\delta}\right]\;,$

where $\widehat{\mu}_{x,a}^{n_{x,a,t}}$ is the sample estimate of the state-
action pair $(x,a)$, having been sampled $n_{x,a,t}$ times till time $t$. The
remainder of the proof has the same flavor as in the work of Auer et al.
(2002). We provide here for the sake of completeness. Note that each term
$\mathbb{P}\left[{|\widehat{\mu}_{x,a}^{n_{x,a,t}}-\mu_{x,a}||\geqslant\delta}\right]$
can be bounded in the following manner,

$\displaystyle\mathbb{P}\Big{\\{}|\widehat{\mu}_{x,a}^{n_{x,a,t}}-\mu_{x,a}|\geqslant\delta\Big{\\}}=\sum_{s=1}^{t}\mathbb{P}\Big{\\{}|\widehat{\mu}_{x,a}^{s}-\mu_{x,a}|\geqslant\delta,{n_{x,a,t}}=s\Big{\\}}$
$\displaystyle=\sum_{s=1}^{t}\mathbb{P}\Big{\\{}{n_{x,a,t}}=s\mid\left|\widehat{\mu}_{x,a}^{s}-\mu_{x,a}\right|\geqslant\delta\Big{\\}}\mathbb{P}\Big{\\{}|\widehat{\mu}_{x,a}^{s}-\mu_{x,a}|\geqslant\delta\Big{\\}}$
$\displaystyle\leqslant\sum_{s=1}^{t}\mathbb{P}\Big{\\{}n_{x,a,t}=s\mid\left|\widehat{\mu}_{x,a}^{s}-\mu_{x,a}\right|\geqslant\delta\Big{\\}}2\exp{(-2s\delta^{2})},$

where we use the sub-Gaussian concentration by Assumption 2.30 and Lemma H.5,

$\displaystyle\leqslant\sum_{s=1}^{t_{0}}\mathbb{P}\Big{\\{}n_{x,a,t}=s\mid\left|\widehat{\mu}_{x,a}^{s}-\mu_{x,a}\right|\geqslant\delta\Big{\\}}+\sum_{s=t_{0}+1}^{t}2\exp{(-2s\delta^{2})}$
$\displaystyle\leqslant\sum_{s=1}^{t_{0}}\mathbb{P}\Big{\\{}n_{x,a,t}=s\mid\left|\widehat{\mu}_{x,a}^{s}-\mu_{x,a}\right|\geqslant\delta\Big{\\}}+\frac{1}{\delta^{2}}\exp{(-2t_{0}\delta^{2})}\;,$

where we use the identity $\sum_{t=x+1}^{\infty}\exp(-\kappa
t)\leqslant\frac{1}{\kappa}\exp(-\kappa x)$. Let $n_{x,a,t}^{R}$ be the number
of times arm $a$ has been played randomly at state $x$ till time $t$, then,

$\displaystyle\sum_{s=1}^{t_{0}}\mathbb{P}\Big{\\{}n_{x,a,t}=s\mid\left|\widehat{\mu}_{x,a}^{s}-\mu_{x,a}\right|\geqslant\delta\Big{\\}}$
$\displaystyle\leqslant\sum_{s=1}^{t_{0}}\mathbb{P}\Big{\\{}n_{x,a,t}^{R}\leqslant
s\mid\left|\widehat{\mu}_{i}^{s}-\mu_{i}\right|\geqslant\delta\Big{\\}}$
$\displaystyle\leqslant\sum_{s=1}^{t_{0}}\mathbb{P}\\{n_{x,a,t}^{R}\leqslant
s\\}$ $\displaystyle\leqslant t_{0}\mathbb{P}\\{n_{i,t}^{R}\leqslant
t_{0}\\}.$

Now, since states $x\in\mathcal{X}$ is chosen statistically independently with
probability $\mathbf{p}_{x}$ over the state-space (Assumption 2.31) and during
random play actions are chosen independently and uniformly over action space
$\mathcal{A}$, we have,

$\displaystyle\mathbb{E}\left[{n_{x,a,t}^{R}}\right]=\frac{\mathbf{p}_{x}}{\left|\mathcal{A}\right|}\sum_{s=1}^{t}\varepsilon_{s}$

and variance of $n_{x,a,t}^{R}$ is

$\displaystyle\mathbb{V}[n_{x,a,t}^{R}]=\sum_{s=1}^{t}\frac{\mathbf{p}_{x}\varepsilon_{s}}{\left|\mathcal{A}\right|}\Big{(}1-\frac{\mathbf{p}_{x}\varepsilon_{s}}{\left|\mathcal{A}\right|}\Big{)}\leqslant\frac{\mathbf{p}_{x}}{\left|\mathcal{A}\right|}\sum_{s=1}^{t}\varepsilon_{s}.$

Thus, choosing
$t_{0}=\frac{\mathbf{p}_{x}}{2\left|\mathcal{A}\right|}\sum_{s=1}^{t}\varepsilon_{s}$,
we have

$\displaystyle\mathbb{P}\\{n_{x,a,t}^{R}\leqslant
t_{0}\\}\leqslant\exp(-t_{0}/5)\;,$

from Bernstein’s Inequality, Lemma H.6. Thus putting it all together, we have,

$\displaystyle\mathbb{P}\left[{A_{t}=a\mid
X_{t}=x}\right]\leqslant\frac{\varepsilon_{t}}{\left|\mathcal{A}\right|}+\left|\mathcal{X}\mathcal{A}\right|t_{0}\exp(-t_{0}/5)+\frac{\left|\mathcal{X}\mathcal{A}\right|}{\delta^{2}}\exp{(-2t_{0}\delta^{2})}.$

Thus, to complete the proof, we only need to find a lower bound on $t_{0}$. As
per our definition,

$\displaystyle t_{0}$
$\displaystyle=\frac{\mathbf{p}_{x}}{2\left|\mathcal{A}\right|}\sum_{s=1}^{t}\varepsilon_{s}$

Plugging the value of $\varepsilon_{s}=1/\sqrt{s}$, we get

$\displaystyle t_{0}$
$\displaystyle=\frac{\mathbf{p}_{x}}{2\left|\mathcal{A}\right|}\sum_{s=1}^{t}\frac{1}{\sqrt{s}}$
$\displaystyle\geqslant\frac{\mathbf{p}_{x}}{\left|\mathcal{A}\right|}(\sqrt{t+1}-1).$

Thus,

$\displaystyle\mathbb{P}\left[{A_{t}=a\mid
X_{t}=x}\right]\leqslant\frac{1}{\left|\mathcal{A}\right|\sqrt{t}}+\mathbf{p}_{x}\left|\mathcal{X}\right|(\sqrt{t+1}-1)\exp(-\frac{\mathbf{p}_{x}(\sqrt{t+1}-1)}{5\left|\mathcal{A}\right|})+\frac{\left|\mathcal{X}\mathcal{A}\right|}{\delta^{2}}\exp{\Big{(}-\frac{2\delta^{2}\mathbf{p}_{x}(\sqrt{t+1}-1)}{\left|\mathcal{A}\right|}\Big{)}}.$

Thus, the expected regret at time $t$ at state $x$ is

$\displaystyle\mathrm{Regret}_{x,t}$
$\displaystyle=\sum_{a\in\mathcal{A}}\Delta_{x,a}\mathbb{P}\left[{A_{t}=a\mid
X_{t}=x}\right]$
$\displaystyle\leqslant\Delta_{x,\max}\frac{1}{\sqrt{t}}+o(1/t)\;,$

where $\Delta_{x,\max}=\max_{a\in\mathcal{A}}\Delta_{x,a}$ and
$\Delta_{x,a}=\mu_{x,\mathrm{OPT}(x)}-\mu_{x,a}$. Thus the expected regret at
time $t$ is

$\displaystyle\mathrm{Regret}_{t}$
$\displaystyle=\sum_{x\in\mathcal{X}}\mathrm{Regret}_{x,t}\mathbb{P}\left[{X_{t}=x}\right]\leqslant\sum_{x\in\mathcal{X}}\mathbf{p}_{x}\Big{(}\Delta_{x,\max}\frac{1}{\sqrt{t}}+o(1/t)\Big{)}$
$\displaystyle\leqslant\frac{\Delta_{\max}}{\sqrt{t}}+o(1/t).$

The cumulative regret is, therefore,

$\displaystyle\sum_{t=1}^{T}\mathrm{Regret}_{t}\leqslant
O(\Delta_{\max}\sqrt{T}).$

∎

The remainder of this subsection is devoted to the proof of the two results
presented in the main paper. We provide proof of Corollary 2.27 that we
presented in the main paper.

######  Corollary B.6.

For any contextual bandit instance $\bm{\mu}$, we have
$\bm{\mu}\in\mathcal{C}^{\mathcal{X}}$ if and only if the model estimate
$\mathbf{P}^{\Lambda}(\bm{\mu})$, computed under any sampling distribution
$\\{\alpha(x,a)\\}_{(x,a)\in\mathcal{X}\times\mathcal{A}}\in\Delta_{\mathrm{XA}}$,
belongs to $\Theta^{\mathcal{X}}$, where
$\Theta^{\mathcal{X}}\triangleq\bigcap_{x\in\mathcal{X}}\Theta^{x}_{\mathrm{OPT}(x)}$.

###### Proof.

For any $\bm{\mu}$ we have $\bm{\mu}_{x}\in\mathcal{R}^{x}_{\mathrm{OPT}(x)}$
for every context $x$, by definition. Thus, from definition of
$\mathcal{C}^{\mathcal{X}}=\bigcap_{x\in\mathcal{X}}\mathcal{C}^{x}_{\mathrm{OPT(x)}}$
we have,

$\displaystyle\bm{\mu}\in\mathcal{C}^{\mathcal{X}}$
$\displaystyle\iff\bm{\mu}_{x}\in\mathcal{C}^{x}_{\mathrm{OPT}(x)}\;\forall
x\in\mathcal{X}.$
$\displaystyle\iff\mathbf{P}^{\Lambda}(\bm{\mu})\in\Theta^{x}_{\mathrm{OPT}(x)}\;\forall
x\in\mathcal{X}.$

for any sampling distribution
$\\{\alpha(x,a)\\}_{(x,a)\in\mathcal{X}\times\mathcal{A}}\in\Delta_{\mathcal{X}\mathcal{A}}$.
This follows from definition of $\mathcal{C}^{x}_{\mathrm{OPT}(x)}$. But this
is the definition of set intersection, that is,

$\displaystyle\iff\mathbf{P}^{\Lambda}(\bm{\mu})\in\bigcap_{x\in\mathcal{X}}\Theta^{x}_{\mathrm{OPT}(x)}\;$

for any sampling distribution
$\\{\alpha(x,a)\\}_{(x,a)\in\mathcal{X}\times\mathcal{A}}\in\Delta_{\mathcal{X}\mathcal{A}}$.
∎

##### Characterization of the Robust Observation Region in Contextual Settings

When the model class is chosen to be linear, the _robust observation region_ ,
$\mathcal{C}^{\mathcal{X}}$, has an explicit analytic description which was
presented without proof in Theorem 2.29. We provide the proof here.

######  Theorem B.7.

For any contextual bandit instance $\bm{\mu}$ we have, $\bm{\mu}$ belongs to
the _robust observation region_ $\mathcal{C}^{\mathcal{X}}$ if and only if for
each $d\times d$ full rank sub-matrix of $\bm{\Phi}$, denoted by $\Phi_{d}$,
along with the corresponding $d$ rows of $\bm{\mu}$, denoted as
$\bm{\mu}_{d}$, satisfy $\Phi_{d}^{-1}\bm{\mu}_{d}\in\Theta^{\mathcal{X}}$.
That is for any $\bm{\mu}$

$\displaystyle\bm{\mu}\in\mathcal{C}^{\mathcal{X}}\iff\Phi_{d}^{-1}\bm{\mu}_{d}\in\Theta^{\mathcal{X}}\;$

for all $d\times d$ full rank sub-matrices of $\bm{\Phi}$ (denoted as
$\Phi_{d}$) and the corresponding $d$ rows of $\bm{\mu}$ (denoted as
$\bm{\mu}_{d}$).

###### Proof.

The proof uses a result of Forsgren (1996), presented in Lemma H.4, that for
any any sampling distribution
$\\{\alpha(x,a)\\}_{(x,a)\in\mathcal{X}\times\mathcal{A}}\in\Delta_{\mathrm{XA}}$,
the model estimate $\mathbf{P}^{\Lambda}(\bm{\mu})$, with
$\Lambda=\mathrm{diag}(\\{\alpha(x,a)\\}_{x,a)\in\mathcal{X}\times\mathcal{A}})$,
lies in the convex hull of the basic solutions $\Phi_{d}^{-1}\bm{\mu}_{d}$.
Note that for any $\bm{\mu}$, we have
$\bm{\mu}_{x}\in\mathcal{R}^{x}_{\mathrm{OPT}(x)}$ for any context $x$ by
definition. Therefore, we have

$\displaystyle\bm{\mu}\in\mathcal{C}^{\mathcal{X}}$
$\displaystyle\iff\mathbf{P}^{\Lambda}(\bm{\mu})\in\Theta^{\mathcal{X}}\;\forall\;\Lambda\in\bm{\Lambda}$
$\displaystyle\iff\mathrm{conv}\\{\Phi_{d}^{-1}\bm{\mu}_{d}\;\forall\;\Phi_{d}\subset\bm{\Phi}\\}\subset\Theta^{\mathcal{X}},$
$\displaystyle\iff\Phi_{d}^{-1}\bm{\mu}_{d}\in\Theta^{\mathcal{X}}\;\forall\;\Phi_{d}\subset\bm{\Phi}.$

The first line above follows from Corollary B.6, and the second line follows
from Lemma H.4. (We abuse notation to denote $d\times d$ full rank sub-
matrices of $\bm{\Phi}$ by $\Phi_{d}\subset\bm{\Phi}$ and use $\mathrm{conv}$
to denote the convex hull.) The last assertion follows because
$\Theta^{\mathcal{X}}$ is a convex set. ∎

##  Appendix C LinUCB

LinUCB remains a canonical regret optimal bandit algorithm. In this section we
show that under standard assumptions, we retain the optimal regret of LinUCB
even under misspecified settings, given that the bandit instance belongs to
the robust region. We begin by first introducing the algorithm in Algorithm 3.

Algorithm 3 OFUL Algorithm

1: Forced Exploration Phase of $d$ linearly independent features

2: Set $V=\mathbf{0}^{d\times d}$ and $S=\mathbf{0}^{d}$

3: for i = 1 to d do

4: Play feature $\varphi_{i}$ and observe noisy reward $y_{i}$

5: Compute $V=V+\varphi_{i}\varphi_{i}^{\top}$

6: Compute $S=S+\varphi_{i}y_{i}$

7: end for

8: Standard OFUL Phase

9: Set $V_{t}=V$ and $S_{t}=S$

10: for t = 1 to T do

11: Estimate $\widehat{\theta}_{t}=\big{[}V_{t}\big{]}^{-1}S_{t}$

12: Play arm $A_{t}$, such that
$\varphi_{A_{t}},\tilde{\theta}_{t}=\mathop{\mathrm{argmax}}_{i\in[K],\theta\in\mathcal{C}_{t}}\varphi_{i}^{\top}\theta$,
where
$\mathcal{C}_{t}=\Big{\\{}\theta\;:\;\big{\|}\theta-\widehat{\theta}_{t}\big{\|}_{V_{t}}\leqslant\sqrt{\beta_{t}(\delta)}\Big{\\}}$

13: Observe the reward $y_{t}$.

14: Update $V_{t+1}=V_{t}+\varphi_{A_{t}}\varphi_{A_{t}}^{\top}$

15: Update $S_{t+1}=S_{t}+\varphi_{A_{t}}y_{t}$

16: end for

######  Remark C.1.

Note that the only non standard modification that we have included in the
algorithm as given in Abbasi-Yadkori et al. (2011) is that instead of using a
regularizer to ensure invertibility of the design matrix
($\sum_{s=1}^{t}\varphi_{A_{s}}\varphi_{A_{s}}^{\top}$), we sample $d$
linearly independent arms explicitly, to ensure that the design matrix is
invertible. This is a mild technicality and can be removed by the introduction
of regularizers as discussed in Appendix E.

We have the following standard assumptions Abbasi-Yadkori et al. (2011).

######  Assumption C.2 (Conditionally sub-Gaussian Noise).

At any time $t$, the observation $y_{t}$ corresponding to the arm played
$A_{t}$, is given by

$\displaystyle y_{t}=\mu_{A_{t}}+\eta_{t},$

where $\eta_{t}$ is conditionally $R$-sub Gaussian, that is,

$\displaystyle\mathbf{E}[e^{\lambda\eta_{t}}\mid
A_{1:t},\eta_{1:t-1}]\leqslant\exp{\Big{(}\frac{\lambda^{2}R^{2}}{2}\Big{)}}\;\;\;\;\forall\;\lambda\in\mathbb{R}.$

######  Assumption C.3 (Bounded Features).

We assume that for any arm $i$ in the arm set $[K]$, the corresponding feature
$\varphi_{i}$ is bounded in the $l^{2}$ norm by $1$, that is,

$\displaystyle\|\varphi_{i}\|_{2}\leqslant 1\;\;\;\forall\;i\in[K].$

######  Assumption C.4 ($d$ rank feature matrix).

We assume that the feature matrix $\bm{\Phi}\in\mathbb{R}^{\mathrm{K}\times
d}$ is of full column rank and that the first $d$ rows are an orthogonal basis
of $\mathbb{R}^{d}$, such that at the end of the forced exploration phase, the
design matrix $V$ has minimum eigenvalue $\lambda_{\min}(V)$ more than $1$.

######  Remark C.5.

The last two assumptions are connected via the technical result, Lemma H.3. In
general, if the norm of the features were bounded by $L$, that is, if
$\|\varphi_{i}\|_{2}\leqslant L$ for any $i\in[K]$, then we would require a
forced exploration phase till the design matrix $V$ has minimum eigenvalue
satisfying $\lambda_{\min}(V)\geqslant\max\\{1,L^{2}\\}$.

######  Remark C.6.

The last assumption can be dropped by introducing regularizers and ensuring
that the regularization parameter, $\lambda$ satisfies the condition
$\lambda\geqslant\max\\{1,L^{2}\\}$ if the features are bounded by $L$. As
mentioned, we discuss the regularized estimates in Appendix E.

We refer to the result in the main paper in Theorem 2.20 here.

######  Theorem C.7 (Sufficient Condition for Zero Regret in Misspecified
Bandits).

Given a feature matrix $\bm{\Phi}$ satisfying Assumptions C.3 and C.4, and any
bandit parameter $\bm{\mu}$ which is an interior point of the _robust
observation region_ , $\mathcal{C}_{\mathrm{OPT}(\bm{\mu})}$ and satisfies
Assumption C.2, the LinUCB algorithm, Algorithm 3, enjoys a regret of
$\widetilde{O}(d\sqrt{T})$ on $\bm{\mu}$.

######  Remark C.8.

The main difficulty is while we can prove that the sample estimates
$\bm{\widehat{\mu}_{t}}$ must fall inside the _robust observation regions_
with high probability, we cannot trivially conclude the same for the high
confidence ellipsoids of the least squares estimate formed under LinUCB.

Consider the model estimate, $\mathbf{P}^{\Lambda(t)}(\bm{\mu})$ based on
noiseless observations of $\bm{\mu}$ under the sampling distribution
$\\{\alpha(i,t)\\}_{i=1}^{K}$ at time $t$, that is,

$\displaystyle\mathbf{P}^{\Lambda(t)}(\bm{\mu})=\Big{(}\sum_{i\in[K]}\alpha(i,t)\varphi_{i}\varphi_{i}^{\top}\Big{)}^{-1}\sum_{i\in[K]}\alpha(i,t)\varphi_{i}\mu_{i}\;.$

Here we use $\Lambda(t)=\operatorname{diag}\\{\alpha(i,t)\\}_{i\in[K]}$ to
denote the weight matrix of the least squares problem. We now make the
following observation.

######  Lemma C.9 (Lower Bound of per instant Regret in the Function Space).

If $\bm{\mu}$ is an interior point of the robust observation region, that is,
if $\bm{\mu}\in\mathrm{Int}(\mathcal{C}_{\mathrm{OPT}(\bm{\mu})})$, then there
exists a $\Delta_{\min}>0$, such that for any sampling distribution
$\\{\alpha(i,t)\\}_{i\in[K]}$ at any time $t\geqslant 1$, we have
$\varphi_{\mathrm{OPT}(\bm{\mu})}^{\top}\mathbf{P}^{\Lambda(t)}(\bm{\mu})-\varphi_{i}^{\top}\mathbf{P}^{\Lambda(t)}(\bm{\mu})\geqslant\Delta_{\min}$
for any sub-optimal arm $i$.

###### Proof.

By definition of _robust observation region_ , Definition 2.11,
$\bm{\mu}\in\mathrm{Int}(\mathcal{C}_{\mathrm{OPT}(\bm{\mu})})$, if and only
if, $\mathbf{P}^{\Lambda}(\bm{\mu})$ belongs to the robust parameter region
$\Theta_{\mathrm{OPT}(\bm{\mu})}$ for any sampling distributions
$\\{\alpha(i)\\}_{i\in[K]}$ in the $K$-dimensional simplex. From the
definition of $\Lambda(t)$ which is defined by the sampling distribution
$\\{\alpha(i,t)\\}_{i\in[K]}$ till time $t$, we must have
$\mathbf{P}^{\Lambda(t)}(\bm{\mu})$ belonging to the robust parameter region
$\Theta_{\mathrm{OPT}(\bm{\mu})}$ for all $t\geqslant 1$ when
$\bm{\mu}\in\mathrm{Int}(\mathcal{C}_{\mathrm{OPT}(\bm{\mu})})$. Therefore,
$\bm{\Phi}\mathbf{P}^{\Lambda(t)}(\bm{\mu})$ belongs to the greedy region
$\mathcal{R}_{\mathrm{OPT}(\bm{\mu})}$ and hence
$\varphi_{\mathrm{OPT}(\bm{\mu})}^{\top}\mathbf{P}^{\Lambda(t)}(\bm{\mu})>\varphi_{i}^{\top}\mathbf{P}^{\Lambda(t)}(\bm{\mu})$
for any sub-optimal arm $i$ for all time $t\geqslant 1$.

Now note that from Theorem 2.13 we have $\mathbf{P}^{\Lambda(t)}(\bm{\mu})$
belongs to the closed convex hull, $\overline{\mathcal{M}}$, of all $K\choose
d$ basic solutions, where
$\overline{\mathcal{M}}\subset\Theta_{\mathrm{OPT}(\bm{\mu})}$. Note that
$0\notin\overline{\mathcal{M}}$ for otherwise
$0\in\Theta_{\mathrm{OPT}(\bm{\mu})}$ which results in $0^{K}$, the $0$ vector
in $\mathbb{R}^{K}$ to belong to a greedy region, a contradiction. Thus for
any time $t\geqslant 1$, and for any sub-optimal arm $i$

$\displaystyle\varphi_{\mathrm{OPT}(\bm{\mu})}^{\top}\mathbf{P}^{\Lambda(t)}(\bm{\mu})-\varphi_{i}^{\top}\mathbf{P}^{\Lambda(t)}(\bm{\mu})\geqslant\min_{\theta\in\overline{\mathcal{M}}}\varphi_{\mathrm{OPT}(\bm{\mu})}^{\top}\theta-\varphi_{i}^{\top}\theta=\Delta_{i}>0.$

where we have used the standard result that minimization of a linear function
over a convex polytope must occur at one of the $K\choose d$ vertices to
define $\Delta_{i}$ and that
$\overline{\mathcal{M}}\subset\Theta_{\mathrm{OPT}(\bm{\mu})}$ to conclude
that $\Delta_{i}>0$. Define $\Delta_{\min}=\min_{i\in K}\Delta_{i}$.
Intuitively, $\Delta_{\min}$ represents the minimum sub-optimality gap of the
bandit instance in the model space.

∎

The crux of the proof of Theorem C.7 relies on the following observation,
whose proof is similar to the one found in Abbasi-Yadkori et al. (2011).

######  Lemma C.10 (Upper Bound of Sub-Optimal Plays).

Given a feature matrix $\bm{\Phi}$ satisfying Assumptions C.3 and C.4, and any
bandit parameter $\bm{\mu}$ which is an interior point of the _robust
observation region_ , $\mathcal{C}_{\mathrm{OPT}(\bm{\mu})}$ and satisfies
Assumption C.2, the LinUCB algorithm, Algorithm 3, plays sub-optimally at most
$\tilde{O}(d\sqrt{t})$.

That is, with $\beta_{t}(\delta)$ set as
$2R^{2}\log\Big{(}\frac{(1+t/d)^{d/2}}{\delta}\Big{)}$ for any $\delta>0$, we
have with probability at least $1-\delta$

$\displaystyle\sum_{s=1}^{t}\mathbb{1}\\{A_{s}\neq\mathrm{OPT}(\bm{\mu})\\}\leqslant\frac{4\sqrt{t}R}{\Delta_{\min}}\sqrt{\log\Big{(}\frac{(1+t/d)^{d/2}}{\delta}\Big{)}}\sqrt{\log{(1+t/d)^{d}}},$

where $\Delta_{\min}$ is as defined in the previous Lemma C.9.

With the above lemma the regret bound is straightforward. Formally,

######  Lemma C.11.

Given a feature matrix $\bm{\Phi}$ satisfying Assumptions C.3 and C.4, and any
bandit parameter $\bm{\mu}$ which is an interior point of the _robust
observation region_ , $\mathcal{C}_{\mathrm{OPT}(\bm{\mu})}$ and satisfies
Assumption C.2, the LinUCB algorithm, Algorithm 3, achieves regret of the
order $\tilde{O}(d\sqrt{t})$.

That is, with $\beta_{t}(\delta)$ set as
$2R^{2}\log\Big{(}\frac{(1+t/d)^{d/2}}{\delta}\Big{)}$ for any $\delta>0$, we
have with probability at least $1-\delta$

$\displaystyle\sum_{s=1}^{t}\mu_{\mathrm{OPT}(\bm{\mu})}-\mu_{A_{s}}\leqslant\frac{4\sqrt{t}R\Delta_{\max}}{\Delta_{\min}}\sqrt{\log\Big{(}\frac{(1+t/d)^{d/2}}{\delta}\Big{)}}\sqrt{\log{(1+t/d)^{d}}},$

where $\Delta_{\min}$ is as defined in Lemma C.9 and $\Delta_{\max}$ is
defined as the worst sub-optimal gap, that is,
$\Delta_{\max}=\max_{i\in[K]}\mu_{\mathrm{OPT}(\bm{\mu})}-\mu_{i}$.

This proves our Theorem C.7. We present the proof of Lemma C.11 for the sake
of completeness.

###### Proof of Lemma C.11.

The cumulative regret is defined as,

$\displaystyle\sum_{s=1}^{t}\mu_{\mathrm{OPT}(\bm{\mu})}-\mu_{A_{s}}$
$\displaystyle=\sum_{s=1}^{t}\Big{(}\mu_{\mathrm{OPT}(\bm{\mu})}-\mu_{A_{s}}\Big{)}\mathbb{1}\\{A_{s}\neq\mathrm{OPT}(\bm{\mu})\\}$
$\displaystyle\leqslant\Delta_{\max}\sum_{s=1}^{t}\mathbb{1}\\{A_{s}\neq\mathrm{OPT}(\bm{\mu})\\}.$

The proof is completed using Lemma C.10. ∎

We present the proof of Lemma C.10

###### Proof of Lemma C.10.

Consider the following quantity,

$\displaystyle
x^{\top}\mathbf{P}^{\Lambda(t)}(\bm{\widehat{\mu}_{t}})-x^{\top}\mathbf{P}^{\Lambda(t)}(\bm{\mu}),$

for any vector $x\in\mathbb{R}^{d}$. Recall the definitions of
$\mathbf{P}^{\Lambda(t)}(\bm{\widehat{\mu}_{t}})$ and
$\mathbf{P}^{\Lambda(t)}(\bm{\mu})$, as

$\displaystyle\mathbf{P}^{\Lambda(t)}(\bm{\widehat{\mu}_{t}})=\Big{(}\sum_{s=1}^{t}\varphi_{A_{s}}\varphi_{A_{s}}^{\top}\Big{)}^{-1}\sum_{s=1}^{t}\varphi_{A_{s}}(\mu_{A_{s}}+\eta_{s})\triangleq\widehat{\theta}_{t}$
$\displaystyle\mathbf{P}^{\Lambda(t)}(\bm{\mu})=\Big{(}\sum_{s=1}^{t}\varphi_{A_{s}}\varphi_{A_{s}}^{\top}\Big{)}^{-1}\sum_{s=1}^{t}\varphi_{A_{s}}\mu_{A_{s}},$

where $\varphi_{A_{s}}$ is the feature of the arm played at time $s$ and
$\mu_{A_{s}}+\eta_{s}$ is the observation at time $s$ having played arm
$A_{s}$. This gives

$\displaystyle
x^{\top}\mathbf{P}^{\Lambda(t)}(\bm{\widehat{\mu}_{t}})-x^{\top}\mathbf{P}^{\Lambda(t)}(\bm{\mu})$
$\displaystyle=x^{\top}\Big{(}\sum_{s=1}^{t}\varphi_{A_{s}}\varphi_{A_{s}}^{\top}\Big{)}^{-1}\sum_{s=1}^{t}\varphi_{A_{s}}\eta_{s}$
$\displaystyle\leqslant\|x\|_{{V_{t}}^{-1}}\Big{\|}\sum_{s=1}^{t}\varphi_{A_{s}}\eta_{s}\Big{\|}_{{V_{t}}^{-1}}.$

We can now use Lemma H.1 to write (after noting that $V=I$, the Identity
Matrix in $d$ dimension),

$\displaystyle
x^{\top}\mathbf{P}^{\Lambda(t)}(\bm{\widehat{\mu}_{t}})-x^{\top}\mathbf{P}^{\Lambda(t)}(\bm{\mu})\leqslant|x\|_{{V_{t}}^{-1}}R\sqrt{2\log\Big{(}\frac{\mathrm{det}V_{t}^{1/2}}{\delta}\Big{)}}.$

Thus setting
$x=V_{t}\Big{(}\mathbf{P}^{\Lambda(t)}(\bm{\widehat{\mu}_{t}})-\mathbf{P}^{\Lambda(t)}(\bm{\mu})\Big{)}$,
we have

$\displaystyle\Big{\|}\mathbf{P}^{\Lambda(t)}(\bm{\widehat{\mu}_{t}})-\mathbf{P}^{\Lambda(t)}(\bm{\mu})\Big{\|}_{V_{t}}\leqslant
R\sqrt{2\log\Big{(}\frac{\mathrm{det}V_{t}^{1/2}}{\delta}\Big{)}},$ (3)

with probability at least $1-\delta$ for all $t\geqslant 1$.

What this means is that under any sampling distribution, the Projection under
that sampling distribution ( Definition 2.7) lies within the high confidence
ellipsoid centred around the estimated least squares solution.

Now let us consider the regret in the function space at any time $t$ as
defined by the sampling distribution $\Lambda(t)$, given by

$\displaystyle\varphi_{\mathrm{OPT}(\bm{\mu})}^{\top}\mathbf{P}^{\Lambda(t)}(\bm{\mu})-\varphi_{A_{t}}^{\top}\mathbf{P}^{\Lambda(t)}(\bm{\mu}).$

The algorithm, at any time chooses $(\varphi_{A_{t}},\tilde{\theta}_{t})$ as
the optimistic estimate, where $\tilde{\theta}_{t}$ lies in the high
confidence ellipsoid defined by Equation 3. To be consistent in our notation,
we shall call the optimistic estimate $\tilde{\theta}_{t}$ as
$\mathbf{P}^{\Lambda(t)}(\bm{\tilde{\mu}_{t}})$. This gives,

$\displaystyle\varphi_{\mathrm{OPT}(\bm{\mu})}^{\top}\mathbf{P}^{\Lambda(t)}(\bm{\mu})-\varphi_{A_{t}}^{\top}\mathbf{P}^{\Lambda(t)}(\bm{\mu})$
$\displaystyle\leqslant\varphi_{A_{t}}^{\top}\mathbf{P}^{\Lambda(t)}(\bm{\tilde{\mu}_{t}})-\varphi_{A_{t}}^{\top}\mathbf{P}^{\Lambda(t)}(\bm{\mu})$
$\displaystyle=\varphi_{A_{t}}^{\top}\mathbf{P}^{\Lambda(t)}(\bm{\tilde{\mu}_{t}})-\varphi_{A_{t}}^{\top}\mathbf{P}^{\Lambda(t)}(\bm{\widehat{\mu}_{t}})+\varphi_{A_{t}}^{\top}\mathbf{P}^{\Lambda(t)}(\bm{\widehat{\mu}_{t}})-\varphi_{A_{t}}^{\top}\mathbf{P}^{\Lambda(t)}(\bm{\mu})$
$\displaystyle=\varphi_{A_{t}}^{\top}\Big{(}\mathbf{P}^{\Lambda(t)}(\bm{\tilde{\mu}_{t}})-\mathbf{P}^{\Lambda(t)}(\bm{\widehat{\mu}_{t}})\Big{)}+\varphi_{A_{t}}^{\top}\Big{(}\mathbf{P}^{\Lambda(t)}(\bm{\widehat{\mu}_{t}})-\mathbf{P}^{\Lambda(t)}(\bm{\mu})\Big{)}$
$\displaystyle\leqslant\|\varphi_{A_{t}}\|_{{V_{t}}^{-1}}\Big{\|}\mathbf{P}^{\Lambda(t)}(\bm{\tilde{\mu}_{t}})-\mathbf{P}^{\Lambda(t)}(\bm{\widehat{\mu}_{t}})\Big{\|}_{V_{t}}+\|\varphi_{A_{t}}\|_{{V_{t}}^{-1}}\Big{\|}\mathbf{P}^{\Lambda(t)}(\bm{\tilde{\mu}_{t}})-\mathbf{P}^{\Lambda(t)}(\bm{\widehat{\mu}_{t}})\Big{\|}_{V_{t}}$
$\displaystyle\leqslant
2\|\varphi_{A_{t}}\|_{{V_{t}}^{-1}}\sqrt{\beta_{t}(\delta)},$

where
$\beta_{t}(\delta)=2R^{2}\log\Big{(}\frac{\mathrm{det}V_{t}^{1/2}}{\delta}\Big{)}$,
with probability at least $1-\delta$. Thus the cumulative regret in the
function space is

$\displaystyle\sum_{s=1}^{t}\varphi_{\mathrm{OPT}(\bm{\mu})}^{\top}\mathbf{P}^{\Lambda(s)}(\bm{\mu})-\varphi_{A_{s}}^{\top}\mathbf{P}^{\Lambda(s)}(\bm{\mu})$
$\displaystyle\leqslant\sum_{s=1}^{t}2\|\varphi_{A_{s}}\|_{{V_{s}}^{-1}}\sqrt{\beta_{s}(\delta)}$
$\displaystyle=\sum_{s=1}^{t}2\|\varphi_{A_{s}}\|_{{V_{s}}^{-1}}R\sqrt{2\log\Big{(}\frac{\mathrm{det}V_{s}^{1/2}}{\delta}\Big{)}}$
$\displaystyle\leqslant
2\sqrt{2}R\sum_{s=1}^{t}\|\varphi_{A_{s}}\|_{{V_{s}}^{-1}}\sqrt{\log\Big{(}\frac{(1+s/d)^{d/2}}{\delta}\Big{)}},$

where in the last inequality we use Lemma H.2 and our Assumption C.3 on
bounded features. Thus continuing, we have,

$\displaystyle
2\sqrt{2}R\sum_{s=1}^{t}\|\varphi_{A_{s}}\|_{{V_{s}}^{-1}}\sqrt{\log\Big{(}\frac{(1+t/d)^{d/2}}{\delta}\Big{)}}$
$\displaystyle\leqslant
2\sqrt{2}R\sqrt{\log\Big{(}\frac{(1+t/d)^{d/2}}{\delta}\Big{)}}\sum_{s=1}^{t}\|\varphi_{A_{s}}\|_{{V_{s}}^{-1}}$
$\displaystyle\leqslant
2\sqrt{2}R\sqrt{\log\Big{(}\frac{(1+t/d)^{d/2}}{\delta}\Big{)}}\sqrt{t}\sqrt{\sum_{s=1}^{t}\|\varphi_{A_{s}}\|^{2}_{{V_{s}}^{-1}}}.$

From our assumption that $\|\varphi_{A_{s}}\|_{2}\leqslant 1$ and from the
forced exploration start we have $\lambda_{\min}(V)=1$, we use Lemma H.3 to
get,

$\displaystyle
2\sqrt{2}R\sqrt{\log\Big{(}\frac{(1+t/d)^{d/2}}{\delta}\Big{)}}\sqrt{t}\sqrt{\sum_{s=1}^{t}\|\varphi_{A_{s}}\|^{2}_{{V_{s}}^{-1}}}$
$\displaystyle
4\sqrt{t}R\sqrt{\log\Big{(}\frac{(1+t/d)^{d/2}}{\delta}\Big{)}}\sqrt{\log\mathrm{det}V_{t}}$
$\displaystyle\leqslant
4\sqrt{t}R\sqrt{\log\Big{(}\frac{(1+t/d)^{d/2}}{\delta}\Big{)}}\sqrt{\log{(1+t/d)^{d}}}$
$\displaystyle=\tilde{O}(d\sqrt{t}).$

Thus what we have shown is that the regret in the function space is of order
$\tilde{O}(d\sqrt{t})$. Note that from our definition of the minimum regret in
the function space, $\Delta_{\min}$ given by Lemma C.9, we have

$\displaystyle\sum_{s=1}^{t}\varphi_{\mathrm{OPT}(\bm{\mu})}^{\top}\mathbf{P}^{\Lambda(s)}(\bm{\mu})-\varphi_{A_{s}}^{\top}\mathbf{P}^{\Lambda(s)}(\bm{\mu})$
$\displaystyle\geqslant\sum_{s=1}^{t}\mathbb{1}\\{A_{s}\neq\mathrm{OPT}(\bm{\mu})\\}\Delta_{\min}.$

Together, this gives the result. ∎

######  Remark C.12.

Note that from the results of Abbasi-Yadkori et al. (2011), we can also derive
a logarithmic regret bound. However, we leave that as an exercise for the
reader.

##  Appendix D LinUCB in Contextual Bandits

We show that in the contextual setting, LinUCB achieves sub-linear regret for
any contextual bandit instance lying in the robust observation region. In
particular, we give the details and the proof of Theorem 2.35 presented in the
main paper.

Algorithm 4 OFUL Algorithm

1: Forced Exploration Phase of $d$ linearly independent features

2: Set $V=\mathbf{0}^{d\times d}$ and $S=\mathbf{0}^{d}$

3: for i = 1 to d do

4: Observe context $X_{i}$

5: Play feature $\varphi_{X_{i},A_{i}}$ and observe noisy reward $Y_{i}$

6: Compute $V=V+\varphi_{X_{i},A_{i}}\varphi_{X_{i},A_{i}}^{\top}$

7: Compute $S=S+\varphi_{X_{i},A_{i}}Y_{i}$

8: end for

9: Standard OFUL Phase

10: Set $V_{t}=V$ and $S_{t}=S$

11: for t = 1 to T do

12: Estimate $\widehat{\theta}_{t}=\big{[}V_{t}\big{]}^{-1}S_{t}$

13: Observe context $X_{t}$

14: Play arm $A_{t}$, such that
$\varphi_{A_{t}},\tilde{\theta}_{t}=\mathop{\mathrm{argmax}}_{a\in\mathcal{A},\theta\in\mathcal{C}_{t}}\varphi_{X_{t},A}^{\top}\theta$,
where
$\mathcal{C}_{t}=\Big{\\{}\theta\;:\;\big{\|}\theta-\widehat{\theta}_{t}\big{\|}_{V_{t}}\leqslant\sqrt{\beta_{t}(\delta)}\Big{\\}}$

15: Observe the reward $Y_{t}$.

16: Update $V_{t+1}=V_{t}+\varphi_{X_{t},A_{t}}\varphi_{X_{t},A_{t}}^{\top}$

17: Update $S_{t+1}=S_{t}+\varphi_{A_{t}}Y_{t}$

18: end for

As in the bandit setting, we shall have a forced exploration phase of $d$
linearly independent features to ensure the invertibility of the design
matrix. This adds, at most, a constant order of regret. The remaining
assumptions for the bandit setting also remain valid for the contextual
setting. We shall see in Appendix E how to remove this condition by bringing a
regularizer.

######  Assumption D.1 (Conditionally sub-Gaussian Noise).

At any time $t$, the observation $Y_{t}$ corresponding to the arm played
$A_{t}$ at context $X_{t}$, is given by

$\displaystyle Y_{t}=\mu_{X_{t},A_{t}}+\eta_{t},$

where $\eta_{t}$ is conditionally $R$-sub Gaussian, that is,

$\displaystyle\mathbf{E}[e^{\lambda\eta_{t}}\mid
A_{1:t},\eta_{1:t-1}]\leqslant\exp{\Big{(}\frac{\lambda^{2}R^{2}}{2}\Big{)}}\;\;\;\;\forall\;\lambda\in\mathbb{R}.$

######  Assumption D.2 (Bounded Features).

We assume that the features $\varphi_{x,a}$ is bounded in the $l^{2}$ norm by
$1$, that is,

$\displaystyle\|\varphi_{x,a}\|_{2}\leqslant
1\;\;\;\forall\;x\in\mathcal{X}\,,a\in\mathcal{A}.$

######  Assumption D.3 ($d$ rank feature matrix).

We assume that the design matrix computed in the forced exploration phase, $V$
has minimum eigenvalue $\lambda_{\min}(V)\geqslant 1$.

######  Remark D.4.

The last assumption can be satisfied by designing the context-specific feature
matrix $\bm{\Phi_{x}}$, a $\left|\mathcal{A}\right|\times d$ matrix to have
the first $d$ features from an orthonormal basis from $\mathbb{R}^{d}$ for
every context $x$. This assumption can be dropped by introducing a
regularization parameter $\lambda$ and requiring $\lambda\geqslant 1$. We
shall see this in Appendix E.

From the definition of the model estimate $\mathbf{P}^{\Lambda(t)}(\bm{\mu})$
being the $t^{th}$ least squares estimate under noiseless observations of
$\bm{\mu}$ under a sampling distribution
$\\{\alpha(x,a,t)\\}_{(x,a)\in\mathcal{X}\times\mathcal{A}}$ in the
$\left|\mathcal{X}\mathcal{A}\right|$ dimensional simplex
$\Delta_{\mathrm{XA}}$, we have the following lemma.

######  Lemma D.5 (Lower Bound of per instant Regret in the Function Space).

If $\bm{\mu}$ is an interior point of the robust observation region, that is,
if $\bm{\mu}\in\mathrm{Int}(\mathcal{C}^{\mathcal{X}})$, then there exists a
$\Delta_{\min}>0$, such that under any sampling distribution
$\\{\alpha(x,a,t)\\}_{a\in\mathcal{A}}$ at any time $t\geqslant 1$, we have
for any context $x$,

$\displaystyle\varphi_{x,\mathrm{OPT}(x)}^{\top}\mathbf{P}^{\Lambda(t)}(\bm{\mu})-\varphi_{x,a}^{\top}\mathbf{P}^{\Lambda(t)}(\bm{\mu})\geqslant\Delta_{\min}\;,$

for any sub-optimal arm $a$ at context $x$.

The proof uses the same argument as in the bandit setting (see Proof of Lemma
C.9).

We also have, in a similar argument as for the bandit setting, the following
results (See Proof of Lemma C.10)

######  Lemma D.6 (High Confidence Ellipsoids).

Under Assumptions D.1, D.2 and D.3,we have for any that for $t\geqslant 1$ and
for any $\delta>0$, we have,

$\displaystyle\Big{\|}\mathbf{P}^{\Lambda(t)}(\bm{\widehat{\mu}_{t}})-\mathbf{P}^{\Lambda(t)}(\bm{\mu})\Big{\|}_{V_{t}}\leqslant
R\sqrt{2\log\Big{(}\frac{(1+t/d)^{d/2}}{\delta}\Big{)}},$

with probability at least $1-\delta$.

Recall from our notation of $\mathbf{P}^{\Lambda(t)}(\bm{\widehat{\mu}_{t}})$
to denote the usual least squares estimate $\widehat{\theta}_{t}$.

######  Lemma D.7 (Cumulative Regret in the Model Space).

Under Assumptions D.1, D.2 and D.3,we have for any that for $t\geqslant 1$ and
for any $\delta>0$, we have,

$\displaystyle\sum_{s=1}^{t}\varphi_{X_{s},\mathrm{OPT}(X_{s})}^{\top}\mathbf{P}^{\Lambda(s)}(\bm{\mu})-\varphi_{X_{s},A_{s}}^{\top}\mathbf{P}^{\Lambda(s)}(\bm{\mu})\leqslant
4\sqrt{t}R\sqrt{\log\Big{(}\frac{(1+t/d)^{d/2}}{\delta}\Big{)}}\sqrt{\log{(1+t/d)^{d}}}\;,$

with probability at least $1-\delta$

Lemma D.5 and Lemma D.7 gives us the number of times any sub-optimal arm is
played at any given context.

######  Lemma D.8 (Upper Bound on Sup-Optimal Plays).

Under Assumptions D.1, D.2 and D.3, for any contextual bandit instance
$\bm{\mu}$ lying in the robust region $\mathcal{C}^{\mathcal{X}}$, we have for
any $t\geqslant 1$, and for any $\delta>0$,

$\displaystyle\sum_{s=1}^{t}\mathbb{1}\\{A_{S}\neq\mathrm{OPT}(X_{s})\\}\leqslant\frac{4\sqrt{t}R}{\Delta_{\min}}\sqrt{\log\Big{(}\frac{(1+t/d)^{d/2}}{\delta}\Big{)}}\sqrt{\log{(1+t/d)^{d}}}\;,$

with probability at least $1-\delta$.

This gives us the regret for LinUCB in contextual bandits,

######  Theorem D.9.

Under Assumptions D.1, D.2 and D.3, for any contextual bandit instance
$\bm{\mu}$ lying in the robust region $\mathcal{C}^{\mathcal{X}}$ of a given
feature matrix $\bm{\Phi}$, we have for any $t\geqslant 1$, and for any
$\delta>0$, the regret of LinUCB as,

$\displaystyle\sum_{s=1}^{T}\mu_{X_{s},\mathrm{OPT}(X_{s})}-\mu_{X_{s},A_{S}}\leqslant\frac{4\sqrt{t}R\Delta_{\max}}{\Delta_{\min}}\sqrt{\log\Big{(}\frac{(1+t/d)^{d/2}}{\delta}\Big{)}}\sqrt{\log{(1+t/d)^{d}}}\;,$

with probability at least $1-\delta$. Here
$\Delta_{\max}=\max_{(x,a)\in\mathcal{X}\times\mathcal{A}}\mu_{x\mathrm{OPT}(x)}-\mu_{x,a}$.

###### Proof.

$\displaystyle\sum_{s=1}^{T}\mu_{X_{s},\mathrm{OPT}(X_{s})}-\mu_{X_{s},A_{S}}$
$\displaystyle=\sum_{s=1}^{T}\mathbb{1}\\{A_{S}\neq\mathrm{OPT}(X_{s})\\}\Delta_{X_{s},A_{s}}$
$\displaystyle\leqslant\sum_{s=1}^{T}\mathbb{1}\\{A_{S}\neq\mathrm{OPT}(X_{s})\\}\Delta_{\max}$
$\displaystyle\leqslant\frac{4\sqrt{t}R\Delta_{\max}}{\Delta_{\min}}\sqrt{\log\Big{(}\frac{(1+t/d)^{d/2}}{\delta}\Big{)}}\sqrt{\log{(1+t/d)^{d}}}\;.$

∎

This completes the proof our Theorem 2.35.

##  Appendix E Weighted Ridge Regression

In our definition of the _robust observation region_ we have implicitly
assumed invertibility of the design matrix. For the purposes of mathematical
rigor, a consistent definition of the robust observation region would be (see
Lemma H.4),

######  Definition E.1 (Robust Observation Region).

For a given feature matrix $\bm{\Phi}$, we define the $k^{th}$ _robust
observation region_ $\mathcal{C}_{k}$, as the set of all $K$ armed bandit
instances $\bm{\mu}$ with optimal arm $k$, such that under any sampling
distribution $\\{\alpha(i)\\}_{i=1}^{K}\in\Delta_{\mathrm{K}}$, the
corresponding regularized model estimate,
$\mathbf{P}^{\Lambda}_{\lambda}(\bm{\mu})$, lies in the $k^{th}$ robust
parameter region, $\Theta_{k}$.

$\displaystyle\mathcal{C}_{k}=\Big{\\{}\bm{\mu}\in\mathcal{R}_{k}:\mathbf{P}^{\Lambda}(\bm{\mu})\in\Theta_{k}\;\forall\;\Lambda\in\bm{\Lambda}\Big{\\}}\;\;\;\textit{for
any arm }k,$

where

$\displaystyle\bm{\Lambda}=\Big{\\{}\Lambda=\mathrm{diag}(\\{\alpha(i)\\}_{i=1}^{K}):\\{\alpha(i)\\}_{i=1}^{K}\in\Delta_{\mathrm{K}}\;\land\;\bm{\Phi}^{\top}\Lambda\bm{\Phi}\text{
is invertible}\Big{\\}}.$

This necessitates a forced exploration phase in our algorithms. In practice,
however one uses a regularizer $\lambda>0$ to by pass the issue of
invertibility. We discuss, how our theory of robust regions extend naturally
to the case when one uses a weighted regularized least squares estimate rather
than the ordinary least squares estimate. Consider the weighted regularized
least squares estimate, defined as per our notation, the _regularized model
estimate_ with regularizer $\lambda>0$.

######  Definition E.2 (Regularized Model Estimate under Sampling
Distribution).

For any bandit instance $\bm{\mu}$ in $\mathbb{R}^{\mathrm{K}}$, we shall
denote the model estimate of the $K$ dimensional element $\bm{\mu}$ under a
sampling distribution, defined by
$\Lambda=\mathrm{diag}(\\{\alpha(i)\\}_{i=1}^{K})$, as

$\displaystyle\mathbf{P}^{\Lambda}_{\lambda}(\bm{\mu})\triangleq\Big{(}\bm{\Phi}^{\top}\Lambda\bm{\Phi}+\lambda
I\Big{)}^{-1}\bm{\Phi}^{\top}\Lambda\bm{\mu}\;,$

for some $\lambda>0$.

Define the corresponding _regularized robust observation region_ as

######  Definition E.3 (Regularized Robust Observation Region).

For a given feature matrix $\bm{\Phi}$, we define the $k^{th}$ _robust
observation region_ $\mathcal{C}_{k}$, as the set of all $K$ armed bandit
instances $\bm{\mu}$ with optimal arm $k$, such that under any sampling
distribution $\\{\alpha(i)\\}_{i=1}^{K}\in\Delta_{\mathrm{K}}$, the
corresponding regularized model estimate,
$\mathbf{P}^{\Lambda}_{\lambda}(\bm{\mu})$, lies in the $k^{th}$ robust
parameter region, $\Theta_{k}$.

$\displaystyle\mathcal{C}^{\lambda}_{k}=\Big{\\{}\bm{\mu}\in\mathcal{R}_{k}:\mathbf{P}^{\Lambda}_{\lambda}(\bm{\mu})\in\Theta_{k}\;\forall\;\Lambda\in\bm{\Lambda}\Big{\\}}\;\;\;\textit{for
any arm }k,$

where

$\displaystyle\bm{\Lambda}=\Big{\\{}\Lambda=\mathrm{diag}(\\{\alpha(i)\\}_{i=1}^{K}):\\{\alpha(i)\\}_{i=1}^{K}\in\Delta_{\mathrm{K}}\Big{\\}}.$

Here $\Theta_{k}$ is the _robust parameter region_ as defined in Definition
2.10. Note that with this definition we have solved all our problems regarding
invertibility. We can again give an explicit description of the set
$\mathcal{C}^{\lambda}_{k}$. Given a feature matrix $\bm{\Phi}$, a sampling
distribution $\Lambda\in\bm{\Lambda}$ and a $K$ dimensional element
$\bm{\mu}$, define the following augmented elements

$\displaystyle\bm{\Phi}^{*}=\begin{bmatrix}\bm{\Phi}\\\
\sqrt{\lambda}I_{d\times
d}\end{bmatrix}\;,\;\;\;\;\;\;\Lambda^{*}=\begin{bmatrix}\Lambda&&0\\\
0&&I_{d\times d}\end{bmatrix}\;\;\;\;\;\text{and
}\;\;\bm{\mu}^{*}=\begin{bmatrix}\bm{\mu}\\\ 0\end{bmatrix},$

where $\bm{\Phi}^{*}\in\mathbb{R}^{K+d\times d}$,
$\Lambda^{*}\in\mathbb{R}^{K+d\times K+d}$ and
$\bm{\mu}^{*}\in\mathbb{R}^{K+d}$. Define the set $\mathcal{J}(\bm{\Phi}^{*})$
as the set of row indices associated with non-singular $d\times d$ sub-
matrices of $\bm{\Phi}^{*}$, and let $\mathcal{I}$ be the set of row indices
corresponding to $\\{K+1,\cdots,K+d\\}$. Then we have the following
characterization of the regularized robust observation region.

######  Theorem E.4.

For any reward vector $\bm{\mu}$ with optimal arm $k$,

$\displaystyle\bm{\mu}\in\mathcal{C}^{\lambda}_{k}\iff\Phi_{J}^{*^{-1}}\bm{\mu}^{*}_{J}\in\Theta_{k}$

for all $J\in\mathcal{J}(\bm{\Phi}^{*})\setminus\mathcal{I}$.

###### Proof.

For a sampling distribution, defined by $\Lambda\in\bm{\Lambda}$ we have

$\displaystyle\mathbf{P}^{\Lambda}_{\lambda}(\bm{\mu})$
$\displaystyle=\Big{(}\bm{\Phi}^{\top}\Lambda\bm{\Phi}+\lambda
I\Big{)}^{-1}\bm{\Phi}^{\top}\Lambda\bm{\mu}$
$\displaystyle=\Big{(}\bm{\Phi}^{*^{\top}}\Lambda^{*}\bm{\Phi}^{*}\Big{)}^{-1}\bm{\Phi}^{*^{\top}}\Lambda^{*}\bm{\mu}^{*}$

where

$\displaystyle\bm{\Phi}^{*}=\begin{bmatrix}\bm{\Phi}\\\
\sqrt{\lambda}I_{d\times
d}\end{bmatrix}\;,\;\;\;\;\;\;\Lambda^{*}=\begin{bmatrix}\Lambda&&0\\\
0&&I_{d\times d}\end{bmatrix}\;\;\;\;\;\text{and
}\;\;\bm{\mu}^{*}=\begin{bmatrix}\bm{\mu}\\\ 0\end{bmatrix}.$

Here $\bm{\Phi}^{*}\in\mathbb{R}^{K+d\times d}$,
$\Lambda^{*}\in\mathbb{R}^{K+d\times K+d}$ and
$\bm{\mu}^{*}\in\mathbb{R}^{K+d}$. Thus, from the result in Lemma H.4, we have
that regularized model estimate $\mathbf{P}^{\Lambda}_{\lambda}(\bm{\mu})$ to
lie within the convex hull of at most $K+d\choose d$ basic solutions
$\Phi_{d}^{*^{-1}}\bm{\mu}_{d}^{*}$ for any $\Lambda\in\bm{\Lambda}$. That is,

$\displaystyle\mathbf{P}^{\Lambda}_{\lambda}(\bm{\mu})=\sum_{J\in\mathcal{J}(\bm{\Phi}^{*})}\Big{(}\frac{\mathrm{det}\Lambda^{*}_{J}\,\mathrm{det}\Phi_{J}^{*^{2}}}{\sum_{K\in\mathcal{J}(\bm{\Phi}^{*})}\mathrm{det}\Lambda^{*}_{K}\,\mathrm{det}\Phi_{K}^{*^{2}}}\Big{)}\Phi_{J}^{*^{-1}}\bm{\mu}^{*}_{J}\,,\;\;\;\forall\,\Lambda\in\bm{\Lambda}$

where $\mathcal{J}(\bm{\Phi}^{*})$ is the is the set of row indices associated
with non-singular $d\times d$ sub-matrices of $\bm{\Phi}^{*}$. Consider the
set of row indices, $\mathcal{I}=\\{K+1,\cdots,K+d\\}$. Corresponding to this
set of indices, $\Phi^{*^{-1}}_{\mathcal{I}}\bm{\mu}^{*}_{\mathcal{I}}$ is
$0$. Thus decomposing the set of row indices $\mathcal{J}(\bm{\Phi}^{*})$ into
$\widetilde{\mathcal{J}}(\bm{\Phi}^{*})$ and $\mathcal{I}$, we observe,

$\displaystyle\mathbf{P}^{\Lambda}_{\lambda}(\bm{\mu})$
$\displaystyle=\sum_{J\in\mathcal{J}(\bm{\Phi}^{*})}\Big{(}\frac{\mathrm{det}\Lambda^{*}_{J}\,\mathrm{det}\Phi_{J}^{*^{2}}}{\sum_{K\in\mathcal{J}(\bm{\Phi}^{*})}\mathrm{det}\Lambda^{*}_{K}\,\mathrm{det}\Phi_{K}^{*^{2}}}\Big{)}\Phi_{J}^{*^{-1}}\bm{\mu}^{*}_{J}$
$\displaystyle=\sum_{J\in\widetilde{\mathcal{J}}(\bm{\Phi}^{*})}\Big{(}\frac{\mathrm{det}\Lambda^{*}_{J}\,\mathrm{det}\Phi_{J}^{*^{2}}}{\sum_{K\in\widetilde{\mathcal{J}}(\bm{\Phi}^{*})}\mathrm{det}\Lambda^{*}_{K}\,\mathrm{det}\Phi_{K}^{*^{2}}+\lambda^{d}}\Big{)}\Phi_{J}^{*^{-1}}\bm{\mu}^{*}_{J}$
$\displaystyle=\sum_{J\in\widetilde{\mathcal{J}}(\bm{\Phi}^{*})}\Big{(}\frac{\mathrm{det}\Lambda^{*}_{J}\,\mathrm{det}\Phi_{J}^{*^{2}}}{\sum_{K\in\widetilde{\mathcal{J}}(\bm{\Phi}^{*})}\mathrm{det}\Lambda^{*}_{K}\,\mathrm{det}\Phi_{K}^{*^{2}}}\Big{)}c^{\lambda}\Phi_{J}^{*^{-1}}\bm{\mu}^{*}_{J}\,,$

where
$c^{\lambda}=\frac{\sum_{K\in\widetilde{\mathcal{J}}(\bm{\Phi}^{*})}\mathrm{det}\Lambda^{*}_{K}\,\mathrm{det}\Phi_{K}^{*^{2}}}{\sum_{K\in\widetilde{\mathcal{J}}(\bm{\Phi}^{*})}\mathrm{det}\Lambda^{*}_{K}\,\mathrm{det}\Phi_{K}^{*^{2}}+\lambda^{d}}$
is necessarily positive for any $\Lambda\in\bm{\Lambda}$.

Thus, we have

$\displaystyle\bm{\mu}\in\mathcal{C}^{\lambda}_{k}\iff\Phi_{J}^{*^{-1}}\bm{\mu}^{*}_{J}\in\Theta_{k}$

for all row indices $J$ in the set
$\mathcal{J}(\bm{\Phi}^{*})\setminus\mathcal{I}$ associated with non-singular
$d\times d$ sub-matrices of $\bm{\Phi}^{*}$.

∎

With this notion of robust region, we immediately have the following results
for the $\varepsilon$-greedy algorithm, but without requiring any forced
exploration phase.

######  Theorem E.5.

For a feature matrix $\bm{\Phi}$, and its associated regularized robust
observation region $\mathcal{C}^{\lambda}_{k}$, any $\frac{1}{2}\text{ sub-
Gaussian}$ bandit parameter $\bm{\mu}$ which is an interior point of the
regularized robust observation region, that is
$\bm{\mu}\in\mathrm{Int}(\mathcal{C}^{\lambda}_{k})$, the $\varepsilon$-greedy
algorithm with $\varepsilon_{t}$ set as $\frac{1}{\sqrt{t}}$, achieves a
regret of $O(\Delta_{\max}\sqrt{T})$, where $\Delta_{\max}$ is the largest
sub-optimal gap, that is $\Delta_{\max}=\max_{i\in[K]}\mu_{k}-\mu_{i}$.

We also have a more relaxed version of the LinUCB result because we don’t need
any forced exploration phase. The only change in the assumptions required for
the analysis to go through is presented.

######  Assumption E.6 (Bounded Features).

We assume that for any arm $i$ in the arm set $[K]$, the corresponding feature
$\varphi_{i}$ is bounded in the $l^{2}$ norm by $1$, that is,

$\displaystyle\|\varphi_{i}\|_{2}\leqslant L\;\;\;\forall\;i\in[K].$

######  Assumption E.7 (Regularization).

We assume that the regularizer $\lambda$, so chosen satisfies

$\displaystyle\lambda\geqslant\max\\{1,L^{2}\\}\;,$

where $L$ is as defined in Assumption E.6

Note that these are more relaxed Assumptions than the one presented in Section
C. With this new set of assumptions, we have the following result.

######  Theorem E.8.

Given a feature matrix $\bm{\Phi}$ satisfying Assumptions E.6, any bandit
parameter $\bm{\mu}$ which is an interior point of the regularized _robust
observation region_ , $\mathcal{C}^{\lambda}_{\mathrm{OPT}(\bm{\mu})}$ and
satisfies Assumption C.2, the LinUCB algorithm, with regularizer chosen as
according to Assumption E.7, enjoys a regret of $\widetilde{O}(d\sqrt{T})$ on
$\bm{\mu}$.

We leave the verification of these results to the reader. We note that these
results could also be extended to the contextual bandit setting. With this, we
can conclude that the algorithms in practice are well suited for
misspecification, provided the misspecified instances fall in the notion of
robustness as defined.

##  Appendix F Experiments

In this section we run some simple experiments to corroborate our findings.

###  F.1 Bandits

In this section we shall focus on the bandit setting and deal with the
contextual setting in the next section. We shall use Theorem 2.13 to
explicitly calculate the _robust observation region_ for a simple feature
matrix. We shall then sample bandit instances from the calculated _robust
observation region_ and run $\varepsilon$-greedy algorithm on these bandit
instances. We shall demonstrate two phenomenon

  1. 1.

Visualization of the _robust observation regions_.

  2. 2.

Sub-linear growth of cumulative regret on misspecified bandits.

####  F.1.1 Robust Regions

Calculation of the _robust parameter region_ essentially involves solving a
system of over-specified linear inequalities. Given a feature matrix of size
$K\times d$, we need to solve a system of $K-1$ linear inequalities in $d$
parameters estimate the robust parameter region corresponding to arm i,
$\Theta_{i}$. We can do this for each arm $i\in[K]$, to get all possible
robust parameter regions, $\Theta_{i}\,\forall\,i\in[K]$. We can now use
Theorem 2.13 to calculate each _robust observation region_ for any arm. This
involves solving at most $K\choose d$ linear inequalities in $d$ dimensions
corresponding to the basic solutions as defined in Theorem 2.13.

For the purposes of visualization and ease of calculation, let us work in the
space of all $3$ armed bandit problems. To avoid trivialization, we choose the
ambient parameter dimension, $d$, to be two. We choose an arbitrary feature
matrix, $\bm{\Phi}$ in $3\times 2$ dimension as $\begin{bmatrix}2&3\\\ 4&5\\\
2&1\end{bmatrix}$. We note that there is nothing special about this feature
matrix, except that it has full rank. We shall start by computing the _robust
parameter regions_. Recall from the definition of the robust parameter region
$\Theta_{i}$ as the domain of the feature matrix $\bm{\Phi}$ such that the
range belongs to the $i^{th}$ greedy region $\mathcal{R}_{i}$ (see Definition
2.10). Thus for any arm in $[3]$, we have
$\Theta_{i}=\Big{\\{}\theta\in\mathbb{R}^{2}\;:\begin{bmatrix}2&3\\\ 4&5\\\
2&1\end{bmatrix}\theta\in\mathcal{R}_{i}\Big{\\}}$. Thus for each $i\in[3]$,
we need to solve for $2$ linear inequalities in $2$ unknowns. Namely for
$\Theta_{1}$ we have the following set of inequalities

$\displaystyle\varphi_{1}^{\top}\theta-\varphi_{2}^{\top}\theta>0$
$\displaystyle\varphi_{1}^{\top}\theta-\varphi_{3}^{\top}\theta>0\;,$

which upon solving, we get the following condition
$\theta_{1}<-\theta_{2}\land\theta_{2}>0$ for any
$\theta=\begin{bmatrix}\theta_{1}\\\ \theta_{2}\end{bmatrix}$ to belong to
$\Theta_{1}$

Similarly, for the regions $\Theta_{2}$ and $\Theta_{3}$ we have the following
set of equations,

$\displaystyle\varphi_{2}^{\top}\theta-\varphi_{1}^{\top}\theta>0$
$\displaystyle\varphi_{2}^{\top}\theta-\varphi_{3}^{\top}\theta>0$

and

$\displaystyle\varphi_{3}^{\top}\theta-\varphi_{2}^{\top}\theta>0$
$\displaystyle\varphi_{3}^{\top}\theta-\varphi_{1}^{\top}\theta>0.$

Upon solving, we arrive at the following descriptions of the _robust parameter
regions_

$\displaystyle\Theta_{1}=\\{\theta\in\mathbb{R}^{2}\;:\theta_{1}<-\theta_{2}\land\theta_{2}>0\\}$
(4)
$\displaystyle\Theta_{2}=\\{\theta\in\mathbb{R}^{2}\;:(\theta_{1}>0\land\theta_{2}>-\theta_{1}/2)\lor(\theta_{1}<0\land\theta_{2}>-\theta_{1})\\}$
(5)
$\displaystyle\Theta_{3}=\\{\theta\in\mathbb{R}^{2}\;:\theta_{2}<0\land\theta_{2}<-\theta_{1}/2\\}.$
(6)

In Figure 4, as a matter of interest, we plot _robust parameter regions_ in
$\mathbb{R}^{2}$ . We note that the parameter space $\mathbb{R}^{2}$ is
partitioned by the _robust parameter regions_. This is not surprising since
the greedy regions $\mathcal{R}_{i}$ partition the $\mathbb{R}^{\mathrm{K}}$
space.

Figure 4: The parameter space $\mathbb{R}^{2}$ is partitioned into disjoint
sets of the _robust parameter regions_ corresponding to the different arms for
feature matrix $\Phi=\begin{bmatrix}2&3\\\ 4&5\\\ 2&1\end{bmatrix}$.

With the exact descriptions of the sets $\Theta_{i}$, we can calculate the
_robust observation regions_. Recall that the robust observation region for
any arm arm $i$ is defined as
$\mathcal{C}_{i}=\\{\bm{\mu}\in\mathbb{R}^{3}\;:\mathbf{P}^{\Lambda}(\bm{\mu})\in\Theta_{i}\\}$
for all sampling distribution $\Lambda$ (see Definition 2.11). Using Theorem
2.13), this turns out to be the set of all $\bm{\mu}$ such that
$\Phi_{2}^{-1}\bm{\mu}_{2}$ belongs to $\Theta_{i}$ for every $2\times 2$ full
rank sub-matrix $\Phi_{2}$ of $\bm{\Phi}$. What this means is that for the
_robust observation region_ corresponding to arm one, $\mathcal{C}_{1}$, we
have the following equations,

$\displaystyle\begin{bmatrix}2\;&\;3\\\
4\;&\;5\end{bmatrix}^{-1}\begin{bmatrix}\mu_{1}\\\
\mu_{2}\end{bmatrix}\in\Theta_{1}\;,$ $\displaystyle\begin{bmatrix}2\;&\;3\\\
2\;&\;1\end{bmatrix}^{-1}\begin{bmatrix}\mu_{1}\\\
\mu_{3}\end{bmatrix}\in\Theta_{1}\;,$ $\displaystyle\begin{bmatrix}4\;&\;5\\\
2\;&\;1\end{bmatrix}^{-1}\begin{bmatrix}\mu_{2}\\\
\mu_{3}\end{bmatrix}\in\Theta_{1}.$

Thus solving for $\mu_{1},\mu_{2}$ and $\mu_{3}$ gives the description for
$\mathcal{C}_{1}$ as

$\displaystyle\mathcal{C}_{1}=\Big{\\{}\bm{\mu}\in\mathbb{R}^{3}\;:(\mu_{1}>\mu_{2}/2)\land(\mu_{1}>\mu_{2})\land(\mu_{2}>2\mu_{3})\land(\mu_{2}<-\mu_{3})\land(\mu_{1}>\mu_{3})\land(\mu_{1}<-\mu_{3})\Big{\\}}\;.$

Similarly from the descriptions of $\Theta_{2}$ and $\Theta_{3}$, we get the
following descriptions for $\mathcal{C}_{2}$ and $\mathcal{C}_{3}$
respectively,

$\displaystyle\mathcal{C}_{2}=\Big{\\{}\bm{\mu}\in\mathbb{R}^{3}\;:(\mu_{1}<\mu_{2}<3\mu_{1})\land(-\mu_{1}<\mu_{3}<3\mu_{1})\land\big{(}(\mu_{3}<\mu_{2}<5\mu_{3})\lor(\mu_{2}>5\mu_{3}\land\mu_{2}>-\mu_{3})\big{)}\Big{\\}}$

and

$\displaystyle\mathcal{C}_{3}=\Big{\\{}\bm{\mu}\in\mathbb{R}^{3}\;:(\mu_{1}<\mu_{2}/2)\land(\mu_{1}<\mu_{2}/3)\land(\mu_{3}>3\mu_{1})\land(\mu_{3}>\mu_{1})\land(\mu_{3}>\mu_{2})\land(\mu_{3}>\mu_{2}/2)\Big{\\}}.$

In Figure 5 we try to visualize these regions in $\mathbb{R}^{3}$. In
particular Figures 5(a), 5(b) and 5(c) represent the regions
$\mathcal{C}_{1},\mathcal{C}_{2}$ and $\mathcal{C}_{3}$ respectively. Note
that these images represent regions in $\mathbb{R}^{3}$. In particular, to
highlight the three dimensional nature of the regions, we have used a shading
effect. The range space of the feature matrix, $\bm{\Phi}\theta$, has also
been highlighted as a two dimensional plane, passing through the robust
regions in Figures 5(a) and 5(b), while bordering the region $\mathcal{C}_{3}$
in Figure 5(c). Note that these images were plotted by restricting $\bm{\mu}$
to lie within a bounded region and so might give the appearance of being
bounded. As could be deduced from the set theoretic descriptions of the
_robust observation regions_ these are convex cones and are unbounded sets.

####  F.1.2 Experiments with $\varepsilon$-greedy Algorithm.

We sample $10$ instances from the robust region $\mathcal{C}_{2}$. We observe
from Figure 6 the mean and dispersion of the cumulative regret generated by
$\varepsilon$-greedy algorithm with $\varepsilon_{t}=1/\sqrt{t}$ on these
sampled instances. We also note the misspecification error (denoted by
$\rho$), the maximum sub-optimality gap (denoted by $\Delta_{\max}$) and the
minimum sub-optimality gap (denoted by $\Delta_{\min}$) for each of these
instances. In order to demonstrate our results with high probability, we form
confidence intervals of the cumulative regret with three standard deviations.
It is observed that the cumulative regret grows at a sub-linear rate with high
probability. We note that instances with higher $\Delta_{\max}$ values tend to
have higher regret than the instances with lower $\Delta_{\max}$ values. We
also note the presence of one sampled instance whose $\Delta_{\min}$ is
dominated by the misspecification error $\rho$. This is in sharp contrast to
the type of robust instances considered in the works of Liu et al. (2023).

(a) The robust region for arm one $\mathcal{C}_{1}$, shown in the blue shade,
is a subset of $\mathbb{R}^{3}$. The range space of the feature matrix is
depicted as the plane.

(b) The robust region for arm two $\mathcal{C}_{2}$ shown in the gray shade,
is a subset of $\mathbb{R}^{3}$. The range space of the feature matrix is
depicted as the plane.

(c) The robust region for arm three $\mathcal{C}_{3}$, shown in the green
shade, is a subset of $\mathbb{R}^{3}$. The range space of the feature matrix
is depicted as the plane.

Figure 5: Visualization of the _robust observation regions_ $-\mathcal{C}_{i}$
for a three armed bandit problem, calculated for the feature matrix
$\bm{\Phi}=\begin{bmatrix}2&3\\\ 4&5\\\ 2&1\end{bmatrix}$, along with the
range space of the feature matrix $\bm{\Phi}\theta$. Note that these are
$3$-dimensional plots with the robust regions $\mathcal{C}_{i}$ shown in
shaded regions of colors blue, gray and green. These regions are subsets of
$\mathbb{R}^{3}$ whereas the range space of the feature matrix, shown in a
”plasma” color, spans $\mathbb{R}^{2}$.  Figure 6: The growth of the
cumulative regret for $10$ misspecified bandit instances sampled from the
robust region of $\mathcal{C}_{2}$ under the $\varepsilon$-greedy algorithm
with $\varepsilon_{t}=1/\sqrt{t}$. The plot represent the average of $10$
trials. The $Y$-axis denotes the cumulative regret
$\sum_{t=1}^{T}\mu^{*}-\mu_{A_{t}}$. The $X$-axis denotes the rounds $T$. We
observe the sub-linear growth trend of the cumulative regret. For each
instance the values of the $l_{\infty}$ misspecification error ($\rho$), the
maximum sub-optimality gap ($\Delta_{\max}$) and the minimum sub-optimality
gap ($\Delta_{\min}$) are also noted. It is observed that instances with
higher $\Delta_{\max}$ suffer more regret at any time than instances with
lower $\Delta_{\max}$ as expected from our theorem.

###  F.2 Contextual Bandits

We repeat the same exercise for the contextual bandit setting. However,
visualization in the contextual setting is more difficult since the reward
vector for any non-trivial problem lies in a space of more than three
dimensions.

####  F.2.1 Robust Observation

We shall look at a $2$ context bandit setting, with contexts $x_{1}$ and
$x_{2}$, each having $3$ arms. We shall keep the feature matrix of the first
context as in the example in the previous section, namely
$\bm{\Phi_{x_{1}}}=\begin{bmatrix}2&3\\\ 4&5\\\ 2&1\end{bmatrix}$ and we shall
set the feature matrix for the second context as
$\bm{\Phi_{x_{2}}}=\begin{bmatrix}2&3\\\ 4&5\\\ 6&7\end{bmatrix}$. Note that
for this setting, contextual rewards are in $\mathbb{R}^{6}$, and thus the
_robust observation regions_ would be of dimension at most $6$. From the
definition of the _robust parameter region_ for context $x_{1}$ and the
calculation done in the previous section we have,

$\displaystyle\Theta^{x_{1}}_{1}=\\{\theta\in\mathbb{R}^{2}\;:\theta_{1}<-\theta_{2}\land\theta_{2}>0\\}$
$\displaystyle\Theta^{x_{1}}_{2}=\\{\theta\in\mathbb{R}^{2}\;:(\theta_{1}>0\land\theta_{2}>-\theta_{1}/2)\lor(\theta_{1}<0\land\theta_{2}>-\theta_{1})\\}$
$\displaystyle\Theta^{x_{1}}_{3}=\\{\theta\in\mathbb{R}^{2}\;:\theta_{2}<0\land\theta_{2}<-\theta_{1}/2\\}.$

For context $x_{2}$, we can repeat the same procedure to find the _robust
parameter space for context $x_{2}$_ as

$\displaystyle\Theta^{x_{2}}_{1}=\\{\theta\in\mathbb{R}^{2}\;:\theta_{1}<-\theta_{2}\\}$
$\displaystyle\Theta^{x_{2}}_{3}=\\{\theta\in\mathbb{R}^{2}\;:\theta_{1}>-\theta_{2}\\}.$

Note that for this feature matrix choice we have found that the robust
parameter region for arm two at context $x_{2}$, $\Theta^{x_{2}}_{2}$ is
$\emptyset$.

We shall now use Theorem 2.29 to evaluate the _robust observation regions_ ,
namely a bandit instance
$\bm{\mu}\in\mathcal{C}^{x_{1}}_{i}\cap\mathcal{C}^{x_{2}}_{j}$ if and only if
the basic solutions belong to
$\Theta^{x_{1}}_{i}\cap\Theta^{x_{2}}_{j}$.888See Theorem 2.29 for what we
mean by basic solutions The non empty intersections of $\Theta^{x_{1}}_{i}$
and $\Theta^{x_{2}}_{j}$ are as follows

$\displaystyle\Theta^{x_{1}}_{1}\cap\Theta^{x_{2}}_{1}=\Theta^{x_{1}}_{1}$
$\displaystyle\Theta^{x_{1}}_{3}\cap\Theta^{x_{2}}_{1}=\\{\theta\in\mathbb{R}^{2}\;:\;\theta_{1}<-\theta_{2}\land\theta_{2}<0\\}$
$\displaystyle\Theta^{x_{1}}_{2}\cap\Theta^{x_{2}}_{3}=\Theta^{x_{1}}_{2}$
$\displaystyle\Theta^{x_{1}}_{3}\cap\Theta^{x_{2}}_{3}=\\{\theta\in\mathbb{R}^{2}\;:\;\theta_{2}<0,-\theta_{1}<\theta_{2}<-\theta_{1}/2\\}.$

Thus $\mathcal{C}^{x_{1}}_{1}\cap\mathcal{C}^{x_{2}}_{1}$ is the set of all
$\bm{\mu}\in\mathbb{R}^{6}$, such that the basic solutions are in
$\Theta^{x_{1}}_{1}\cap\Theta^{x_{2}}_{1}=\Theta^{x_{1}}_{1}$.

Solving, gives us the description of the set
$\mathcal{C}^{x_{1}}_{1}\cap\mathcal{C}^{x_{2}}_{1}$ as the set of all
$\bm{\mu}\in\mathbb{R}^{6}$ such that the following conditions are satisfied

$\displaystyle\mathcal{C}^{x_{1}}_{1}\cap\mathcal{C}^{x_{2}}_{1}=\Big{\\{}\bm{\mu}\in\mathbb{R}^{6}\;:\;$
$\displaystyle\mu_{1}>\mu_{2}\land\mu_{1}>\mu_{2}/2,$
$\displaystyle\mu_{1}>\mu_{3}\land\mu_{1}<-\mu_{3},$
$\displaystyle\mu_{1}>\mu_{5}\land\mu_{1}>\mu_{5}/2,$
$\displaystyle\mu_{1}>\mu_{6}\land\mu_{1}>\mu_{6}/3,$
$\displaystyle\mu_{2}>2\mu_{3}\land\mu_{2}<-\mu_{3},$
$\displaystyle\mu_{4}>\mu_{2}/2\land\mu_{2}<\mu_{4},$
$\displaystyle\mu_{2}>\mu_{6}\land\mu_{2}>2/3\mu_{6},$
$\displaystyle\mu_{4}>\mu_{3}\land\mu_{3}<-\mu_{4},$
$\displaystyle\mu_{5}>2\mu_{3}\land\mu_{3}<-\mu_{5},$
$\displaystyle\mu_{6}>3\mu_{3}\land\mu_{3}<-\mu_{6},$
$\displaystyle\mu_{4}>\mu_{5}\land\mu_{4}>\mu_{5}/2,$
$\displaystyle\mu_{4}>\mu_{6}\land\mu_{4}>\mu_{6}/3,$
$\displaystyle\mu_{5}>\mu_{6}\land\mu_{5}>2/3\mu_{6}\Big{\\}}.$

In Figure 7 we try to visualize the region
$\mathcal{C}^{x_{1}}_{1}\cap\mathcal{C}^{x_{2}}_{1}$ an element in
$\mathbb{R}^{6}$ in terms of its projections in the $\mathbb{R}^{3}$ space. To
do so, we have taken projections of the six dimensional region in every
possible three dimensional basis representation of $(\mu_{i},\mu_{j},\mu_{k})$
and plotted it. For example the first image in the top most row of Figure 7 is
the plot of $(\mu_{1},\mu_{2},,\mu_{3})$ for any
$\bm{\mu}\in\mathcal{C}^{x_{1}}_{1}\cap\mathcal{C}^{x_{2}}_{1}$. Similarly the
plot to the immediate right of it is the plot of $(\mu_{1},\mu_{2},\mu_{4})$
and so on. Note that each of these plots represents a three dimensional
projection of the high dimensional region. To highlight the $3$-D nature of
these plots, we have used a gradient color shading to give the perception of
depth999The specific type of shading we have used is ’viridis’ in Matplotlib.
Note that these images were plotted by restricting $\bm{\mu}$ to lie within a
bounded region and so might give the appearance of being bounded. As could be
deduced from the set theoretic descriptions of the _robust observation
regions_ these are convex cones and are unbounded sets.

As an exercise we also compute
$\mathcal{C}^{x_{1}}_{3}\cap\mathcal{C}^{x_{2}}_{1}$, the robust region of all
contextual bandit problems where context $x_{1}$ has arm $3$ as optimal and
context $x_{2}$ has arm $1$ as optimal. In the same procedure, we calculate
the region $\mathcal{C}^{x_{1}}_{3}\cap\mathcal{C}^{x_{2}}_{1}$ as the set of
all $\bm{\mu}\in\mathbb{R}^{6}$ such that the following conditions are
satisfied

$\displaystyle\mathcal{C}^{x_{1}}_{3}\cap\mathcal{C}^{x_{2}}_{1}=\Big{\\{}\bm{\mu}\in\mathbb{R}^{6}\;:\;$
$\displaystyle\mu_{1}>\mu_{2}\land\mu_{1}<\mu_{2}/2,$
$\displaystyle\mu_{1}<\mu_{3}\land\mu_{1}<-\mu_{3},$
$\displaystyle\mu_{1}>\mu_{5}\land\mu_{1}<\mu_{5}/2,$
$\displaystyle\mu_{1}>\mu_{6}\land\mu_{1}<\mu_{6}/3,$
$\displaystyle\mu_{2}<2\mu_{3}\land\mu_{2}<-\mu_{3},$
$\displaystyle\mu_{4}<\mu_{2}/2\land\mu_{2}<\mu_{4},$
$\displaystyle\mu_{2}>\mu_{6}\land\mu_{2}<2/3\mu_{6},$
$\displaystyle\mu_{4}<\mu_{3}\land\mu_{3}<-\mu_{4},$
$\displaystyle\mu_{5}<2\mu_{3}\land\mu_{3}<-\mu_{5},$
$\displaystyle\mu_{6}<3\mu_{3}\land\mu_{3}<-\mu_{6},$
$\displaystyle\mu_{4}>\mu_{5}\land\mu_{4}<\mu_{5}/2,$
$\displaystyle\mu_{4}>\mu_{6}\land\mu_{4}<\mu_{6}/3,$
$\displaystyle\mu_{5}>\mu_{6}\land\mu_{5}<2/3\mu_{6}\Big{\\}}.$

In Figure 9 we plot the region
$\mathcal{C}^{x_{1}}_{3}\cap\mathcal{C}^{x_{2}}_{1}$, in the same principle as
in the previous visualization. In this figure, we have also plotted the range
space of the feature matrix $\bm{\Phi}\theta$ along every possible three-
dimensional basis representation of $(\mu_{i},\mu_{j},\mu_{k})$ in a shade of
’plasma’. For example, the first image of the topmost row of Figure 9 shows
the plot of the first three coordinates of $\bm{\Phi}\theta$ as $\theta$
ranges in $\Theta^{x_{1}}_{3}\cap\Theta^{x_{2}}_{1}$ alongside the projection
of the robust observation region. Similarly, the figure to the immediate right