# Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear
Bandit Algorithms

Osama A. Hanna†, Lin F. Yang† and Christina Fragouli†
†University of California, Los Angeles
Email:{ohanna, linyang<EMAIL_ADDRESS>
###### Abstract

In this paper, we address the stochastic contextual linear bandit problem,
where a decision maker is provided a context (a random set of actions drawn
from a distribution). The expected reward of each action is specified by the
inner product of the action and an unknown parameter. The goal is to design an
algorithm that learns to play as close as possible to the unknown optimal
policy after a number of action plays. This problem is considered more
challenging than the linear bandit problem, which can be viewed as a
contextual bandit problem with a _fixed_ context. Surprisingly, in this paper,
we show that the stochastic contextual problem can be solved as if it is a
linear bandit problem. In particular, we establish a novel reduction framework
that converts every stochastic contextual linear bandit instance to a linear
bandit instance, when the context distribution is known. When the context
distribution is unknown, we establish an algorithm that reduces the stochastic
contextual instance to a sequence of linear bandit instances with small
misspecifications and achieves nearly the same worst-case regret bound as the
algorithm that solves the misspecified linear bandit instances. As a
consequence, our results imply a $O(d\sqrt{T\log T})$ high-probability regret
bound for contextual linear bandits, making progress in resolving an open
problem in [1, 2]. Our reduction framework opens up a new way to approach
stochastic contextual linear bandit problems, and enables improved regret
bounds in a number of instances including the batch setting, contextual
bandits with misspecifications, contextual bandits with sparse unknown
parameters, and contextual bandits with adversarial corruption.

##  1 Introduction

Algorithm | Regret Bound | Type | Assumption/restriction
---|---|---|---
[3] | $O(d\sqrt{T}\log T)$ | w.h.p. |
[2] | $O(d\sqrt{T\log T}poly(\log\log T))$ | exp |
[2] | $O(d\sqrt{T}\log Tpoly(\log\log T))$ | w.h.p. |
Ours | $O(d\sqrt{T\log T})$ | w.h.p. |
[4] | $O(d\sqrt{T\log(d)\log(T)}\log\log T)$ | exp | batch learning with
Ours | $O(d\sqrt{T\log(T)}\log\log T)$ | w.h.p. |  $O(\log\log T)$ batches
[5] | $O(d\sqrt{T}\log T+\epsilon\sqrt{d}T)$ | exp | misspecified
Ours | $O(d\sqrt{T\log T}+\epsilon\sqrt{d}T\log T)$ | w.h.p. |
[5] | $\tilde{O}(d^{4.5}\sqrt{T}+d^{4}C)$ | w.h.p. | adversarial corruption
Ours | $\tilde{O}(d\sqrt{T}+d^{3/2}C)$ | w.h.p. |
[6] | $O(\sqrt{dsT}\log T)$ | w.h.p. | sparse
Ours | $O(\sqrt{dsT\log T})$ | w.h.p. |
Ours | $O(\sqrt{dsT\log T}\log\log T)$ | w.h.p. | sparse with $O(\log\log T)$ batches
Table 1: Comparison of best known in literature vs. our approach regret
bounds. Here, $d$ is the model dimension, $T$ is the time horizon, $\epsilon$
is an upper bound on the amount of misspecification, $C$ limits the power of
adversary, $s$ is an upper bound on the number of non-zero elements in the
unknown parameter, exp indicates a regret bound in expectation, w.h.p.
indicates a regret bound that holds with probability at least $1-1/T$, and
$\tilde{O}$ hides $\log$ factors.

Linear bandit and contextual linear bandit problems are attracting extensive
attention - for example, more than $17,000$ papers appear when searching for
“linear contextual bandit” on Google Scholar during the last 5 years \- as
they enable to support impactful active learning applications through elegant
formulations. In linear bandits, a learner at each time $t\in[T]$, where $T$
is the time horizon, pulls an arm $a_{t}$ from a fixed action space
$\mathcal{A}$ (that may be continuous or discrete), and receives a reward
$r_{t}={\langle a_{t},\theta_{\star}\rangle}+\eta_{t}$, where $\theta_{\star}$
is an unknown $d$-dimensional vector of parameters and $\eta_{t}$ is random
noise. Contextual linear bandits add another layer of complexity by enabling
at each round the action space to be different to capture context; in this
case, the learner at time $t$ observes an action space (context)
$\mathcal{A}_{t}$. That is, we can think of linear bandits as single-context
contextual bandits, observing $\mathcal{A}_{t}=\mathcal{A}$ for all $t$. For
example, while linear bandits are used in recommendation systems where the set
of actions is fixed and oblivious to the individual the recommendation is
addressed to, contextual linear bandits are used in personalized
recommendations, where the action space gets tailored to context attributes
such as age, gender, income and interests of each individual.

It is not surprising that, although more limited in applications, linear
bandits are much better understood in theory than contextual linear bandits.
Indeed, algorithms for linear bandits often leverage the fixed action space
property, and cannot be easily extended to contextual linear bandits. To give
a concrete example, the algorithm Phased Elimination (PE) [7, 8] leverages the
fixed action space by exploring a (small) core set of actions to achieve good
estimates of the rewards for all actions. This algorithm achieves a high
probability regret bound of $O(d\sqrt{T\log T})$. Nevertheless, despite
several attempts over the last decade [3, 2, 1], the best known regret upper
bounds for contextual linear bandits have a $\log$ (or iterated $\log$)
multiplicative gap over the $O(d\sqrt{T\log T})$ bound both in high
probability and in expectation. Similarly, the best known algorithms for
several linear bandits problems (e.g., with misspecification, adversarial
corruption, and others [7, 5, 9, 10, 4]), perform better (in the worst-case)
than the corresponding algorithms for contextual linear bandits.

###  1.1 Our Results

#### The Reduction

We show in this paper the surprising result that, provided the context comes
from a distribution $\mathcal{D}$ (stochastic context), contextual linear
bandit problems can be reduced to solving (single context) linear bandit
problem when the context distribution $\mathcal{D}$ is known, and to linear
bandits with $\tilde{O}(1/\sqrt{T})$ misspecification when the distribution
$\mathcal{D}$ is unknown. These results are presented in the following
informal theorems and their exact statements are given in Theorems 1, 2 and 3.

######  Theorem (Informal Statement of Theorem 1).

For any contextual linear bandit instance $I$ with known context distribution
$\mathcal{D}$, there exists (constructively) a linear bandit instance L with
the same action dimension, and any algorithm solving L solves $I$ with the
same worst-case regret bound as L.

######  Theorem (Informal Statement of Theorem 2).

For any contextual linear bandit instance $I$ with unknown context
distribution $\mathcal{D}$, there exist (constructively) $\log T$ misspecified
linear bandit instances $L_{1},...,L_{\log T}$, where $L_{i}$ operates on part
of the horizon of length $T_{i}$, has
$\tilde{O}(1/\sqrt{T_{i}})$-misspecification and the same action dimension,
and any algorithm solving $L_{1},...,L_{\log T}$ solves $I$ with the same
worst-case regret bound as $L_{1},...,L_{\log T}$.

######  Theorem (Informal Statement of Theorem 3).

For any contextual linear bandit instance $I$ with unknown context
distribution $\mathcal{D}$ but where now the action space has a component-wise
product structure, there exists (constructively) a linear bandit instance L
with double the action dimension of $I$, and any algorithm solving L solves
$I$ with the same worst-case regret bound as L.

Stochastic contextual bandits encompass practical cases where the context is
not selected adversarially; in our example of personalized recommendations,
the age, gender, income, come from distributions. Our framework simplifies the
contextual linear bandit problem and enables to use any existing (or future)
linear bandit algorithms to solve the contextual case. Moreover, our results
separate the case of stochastic contexts from the harder case of adversarial
contexts and explain why good results, which are not achievable for
adversarial contexts, are possible for stochastic contexts.

#### Implications and Related Work

The equivalence we proved opens up a new way to approach stochastic contextual
linear bandit problems, and results in a number of new results or recovery of
existing results in a simpler manner; we next present some of these
implications (summarized in Table 1) and their positioning with respect to
related work. In the discussion next, $d$ is the model dimension and $T$ is
the time horizon.

$\bullet$ Tighter Regret Bounds. To the best of our knowledge, there is a gap
in the regret bounds of contextual linear bandits: the state-of-the-art lower
bounds are, $\Omega(d\sqrt{T})$ for linear bandits [11] and
$\Omega(d\sqrt{T\log T})$ for linear contextual bandit with adversarial
contexts [1].
Our contribution [Corollary 2]. Our approach achieves a regret upper bound
$O(d\sqrt{T\log T})$ with high probability even when the action set is
infinite. While it is not known if a $\Omega(d\sqrt{T\log T})$ lower bound
holds for stochastic contexts, our result improves over state of the art high
probability bounds by at least a factor of $\sqrt{\log T}$ and matches the
best known upper bound for linear bandits.
Related Work. The best attempts of upper bounds are [3, 2, 1]. In particular,
[3] achieves a regret bound of $O(d\sqrt{T}\log T)$ with high probability; [2]
achieves $O(d\sqrt{T\log T}poly(\log\log T))$ in expectation and
$O(d\sqrt{T}\log Tpoly(\log\log T))$ with high probability; and [1] achieves
$O(d\sqrt{T\log T}poly(\log\log(T)))$ _in expectation_ and only when the
number of actions is _finite and bounded by $2^{d/2}$_.

$\bullet$ Batch Learning. In batch learning, instead of observing the reward
at the end of each round to decide what action to play next, the learning
agent is constrained to split the rounds into a fixed number of $M$ batches,
use a predetermined policy within each batch, and it can only observe the
action outcomes and switch the policy at the end of each batch. This is a
central problem in online learning [12, 13, 4, 14] as limited policy
adaptivity enables parallelism and facilitates deployment of learning
algorithms for large-scale models.
Our Contribution [Theorem 4]. Our batch algorithm for contextual linear
bandits achieves with _high probability_ $O(d\sqrt{T\log(T)}\log\log T)$
regret bound for $O(\log\log T)$ batches, a $\sqrt{\log d}$ better than the
_in expectation_ regret bound in [4].
Related Work. A number of works have explored batched contextual linear
bandits, both in adversarial [3, 14] and non-adversarial settings [4, 15]. The
breakthrough work in [4] achieved a nearly optimal _in expectation_ regret
upper bound $O(d\sqrt{T\log d\log(T)}\log\log T)$ using $O(\log\log T)$
batches for the stochastic contexts setting. The near-optimality follows from
the result in [12] which shows that $\Omega(\log\log T)$ batches are required
to achieve a $O(\sqrt{T})$ worst-case regret bound for multi-armed bandits
with a finite number of arms (this is a special case of contextual linear
bandits). If the contexts are chosen adversarially, $\Omega(\sqrt{T})$ batches
are required to achieve a $O(\sqrt{T})$ regret bound [14].

$\bullet$ Misspecified Bandits. Linear bandit algorithms are designed under
the assumption that the expected rewards are perfectly linear functions of the
actions; misspecified bandits relax this assumption by considering
perturbations of the linear model measured by the amount of deviation in the
expected rewards (we call the case $\epsilon$-misspecification if the
deviation is upper bounded by $\epsilon$). The non-linearity in the model
enables to better capture real-world environments and is of high interest in
the literature [16, 17, 7, 5, 18, 19].
Our Contribution [Theorem 5, 6]. We provide a regret bound of $O(d\sqrt{T\log
T}+\epsilon\sqrt{d}T\log T)$ with high probability for contextual bandits with
unknown misspecification, and $O(d\sqrt{T\log T}+\epsilon\sqrt{d}T)$ with high
probability for $\epsilon$ known. To the best of our knowledge, these results
offer the first _optimal regret bounds_ for $\epsilon$-misspecified contextual
linear bandits, and improve over existing literature for unknown $\epsilon$ by
providing high probability bounds and improved $\log$ factors. We also present
the first nearly optimal algorithm for misspecified contextual linear bandits
with $O(\log T)$ batches.
Related Work. The work in [7] shows that PE with modified confidence intervals
achieves the optimal regret bound of $O(d\sqrt{T\log T}+\epsilon\sqrt{d}T)$
with high probability (matching the $\Omega(\epsilon\sqrt{d}T)$ lower bound
[7]) for linear bandits with known $\epsilon$ misspecification. If $\epsilon$
is unknown, the same algorithm was shown to achieve a regret bound of
$O(d\sqrt{T\log T}+\epsilon\sqrt{d}T\log T)$ with high probability. The work
in [20, 7] proposed variants of LinUCB that achieve a regret bound of
$\tilde{O}(d\sqrt{T}+\epsilon\sqrt{d}T)$111 Here $\tilde{O}$ hides $\log$
factors. with high probability for contextual linear bandits with known
$\epsilon$. However, changing action sets with unknown $\epsilon$ was left as
an open problem. The works in [21, 5] made progress in answering this question
by providing a regret bound of $O(d\sqrt{T}\log T+\epsilon\sqrt{d}T)$ in
expectation [5]. However, improving the $\log$ factors in the first term and
strengthening the result to a high probability bound was unresolved. Due to
the challenge that changing action sets impose on the analysis, the techniques
of [5] cannot be directly extended to provide high probability bounds on the
regret. Our result of $O(d\sqrt{T\log T}+\epsilon\sqrt{d}T\log T)$ regret
removes the $\sqrt{\log T}$ factor from the first term and adds a $\log T$
factor in the second term; depending on the value of $\epsilon$ this can lead
to a tighter or looser bound.

$\bullet$ Bandits with Adversarial Corruption. Linear bandits with adversarial
corruption recently attracted significant interest [22, 23, 24, 25, 26, 9, 27,
10] due to the vulnerability of online learning applications to attacks. There
are multiple adversarial models that are proposed in the literature; here we
consider a widely used model that assumes the adversary knows the policy, and
observes the history, but does not observe the current action before
corrupting the rewards.
Our Contribution [Theorem 7]. Our work provides the first algorithm for
contextual linear bandits that achieves a regret bound of
$\tilde{O}(d\sqrt{T}+d^{3/2}C)$ with high probability for unknown $C$, which
upper bounds the total amount of corruption from the adversary. This improves
over the best known $\tilde{O}(d^{4.5}\sqrt{T}+d^{4}C)$ bound for linear
bandits with changing action sets in [10]. We note that in our regret bound,
while the dependency on $d$ in the first term is nearly optimal, the
dependency on $d^{3/2}$ in the second term is not. However, we simplify the
problem of improving this dependency, as any algorithm that improves it for
linear bandits will imply the same improvement for contextual bandits with our
reduction.
Related Work. The work in [9] considers linear bandits with adversarial
corruption and achieves a regret bound of $\tilde{O}(d\sqrt{T}+d^{3/2}C)$ with
high probability for known corruption level $C$ and a regret bound of
$\tilde{O}(d\sqrt{T}+d^{3/2}C+C^{2})$ with high probability for a stronger
adversary that observes the current action and unknown corruption level $C$,
while the work in [10] achieves a regret bound of
$\tilde{O}(d\sqrt{T}+d^{3/2}C)$ with high probability for unknown corruption
$C$. These algorithms have optimal dependency on $T,C$ but it is not known if
the $d^{3/2}$ dependency is tight or not. The work in [27] improves the
dependency on $d$ for linearized corruption, by achieving a regret bound of
$\tilde{O}(d\sqrt{T}+C)$ with high probability which is also nearly optimal
[27]. The proposed algorithms and analysis rely on the assumption that the
action set is fixed, and as far as we know there are no known generalizations
for changing action sets - beyond the work in [9] that considers changing
action sets but imposes a strong assumption on the context distribution. The
work in [28] considers a stronger adversary, that observes the current action,
and achieves an $\tilde{O}(d\sqrt{T})$ regret bound for unknown
$C\leq\sqrt{T}$ and linear regret otherwise. The first paper to prove a regret
bound with nearly optimal dependency on $T,C$ for linear bandits with changing
action sets (linear contextual bandits) is [10] which achieves a regret bound
of $\tilde{O}(d^{4.5}\sqrt{T}+d^{4}C)$ with high probability for unknown $C$.
While the dependency on $T,C$ is nearly optimal, the dependency on $d$ is
clearly not - improving this was left as an open problem. Our results take a
step in this direction by removing a factor of $d^{3.5}$ from the first term,
by removing a factor of $d^{2.5}$ from the second term and by reducing the
problem of further improving the dependency of $d$ in the second term to
achieving this improvement over a linear bandit setup.

$\bullet$ Sparsity. High dimensional linear bandits with sparsity capture
practical cases such as, when there exist a large number of candidate features
and limited information on which of them are useful; use cases include
personalized medicine and online advertising [29]. This setup results in
sparsity in the unknown linear bandit parameters, which can be leveraged for
more efficient learning.
Our Contribution [Theorem 8]. Our work provides the first $O(\sqrt{dsT\log
T})$ regret bound with high probability for contextual linear bandits,
improving a factor of $\sqrt{\log T}$ on the state of the art, where $s$ is an
upper bound of the nonzero elements in the model.
Related Work. Due to its practical significance, a number of works have
examined this setup [30, 6, 31, 32, 33, 34, 35, 36, 37]. To the best of our
knowledge, the best known regret bound is $O(\sqrt{dsT}\log T)$ with high
probability [6]. While this is shown to be nearly optimal [11], improving the
$\log T$ factor was left as an open problem. Our work resolves this.

###  1.2 Technical Overview

Our major technique innovation is in the conception and execution of a
reduction from a stochastic contextual linear bandit instance to a linear
bandit instance. This reduction is made possible by establishing a linear
bandit action for each possible parameter $\theta$ of the contextual bandit
instance. In particular, for a given $\theta$, we establish a new action
$g(\theta)$ that is the expected best action (under the distribution of the
context $\mathcal{A}_{t}$) with respect to the parameter $\theta$, i.e.,
$g(\theta)=\mathbb{E}_{\mathcal{D}}(\arg\max_{\tilde{a}\in\mathcal{A}_{t}}\langle\tilde{a},\theta\rangle)$.
Note that $g(\theta)$ may not correspond to any valid action for the present
context in the corresponding contextual bandit instance. Yet, we show that if
one plays an action
$\arg\max_{\tilde{a}\in\mathcal{A}_{t}}\langle\tilde{a},\theta\rangle$ that is
optimal with respect to $\theta$, then the contextual bandit instance
generates a _linear reward_ with respect to $g(\theta)$. Moreover, the linear
bandit instances share the same optimal parameter $\theta_{\star}$ as in the
contextual instance. Under standard boundedness assumptions of the contexts
and actions, the reward noise in the reduced linear instance and the
contextual bandit instance also share a similar sub-Gaussian tail. By mapping
the linear bandit action $g(\theta)$ to the contextual bandit
$\arg\max_{\tilde{a}\in\mathcal{A}_{t}}\langle\tilde{a},\theta\rangle$ for any
context $\mathcal{A}_{t}$ and $\theta$, any algorithm for the linear bandit
problem can be immediately applied to solve for the contextual bandit problem
and suffer no additional regret in the worst-case.

The reduction becomes more challenging when the context distribution is
unknown. One idea is to estimate $g(\theta)$ for all possible $\theta$.
Unfortunately, doing so would require a large number of samples resulting in
unbounded regret. We resolve this issue by a batched approach where the
batches provide increasingly better estimates of $g(\theta)$. In each batch,
we estimate $g(\theta)$ using all the contexts generated in the previous
batch. Note that this inevitably introduces error which ruins the linearity of
the collected reward from the contextual bandit instance. Hence, we can only
apply algorithms that are designed for misspecified linear bandits. Luckily,
with a carefully designed batch sequence, we show that a linear bandit
algorithm that works for all misspecification levels
$\epsilon\in[1/\sqrt{T},1]$ can be applied to solve the contextual bandit
instance. As it is hard to guarantee a good estimate of $g$ for all $\theta$,
we restrict our attention to a finite subset of the unknown parameter set
$\Theta$ (discretization) that is guaranteed to contain a good action. The
amount of misspecification is bounded using a union bound argument over the
discretization of $\Theta$. While the discretization of $\Theta$ may eliminate
the optimal arm and the function $g$ is shown to be non-smooth, we show that
the function $r(\theta)={\langle g(\theta),\theta_{\star}\rangle}$ is smooth
on a neighborhood of $\theta_{\star}$. This is sufficient to show that if
discretized finely, the discrete set will contain a good arm. The final worst-
case regret bound can be controlled by the regret bound of the linear bandit
algorithm and the batch lengths.

We next provide a high level explanation on why our reduction enables tighter
regret bounds for contextual linear bandits with stochastic contexts. Using
the Phased Elimination algorithm (PE) [7] with modified confidence intervals
to solve the misspecified linear bandit instance, we prove a high probability
bound of $O(d\sqrt{T\log T})$ on the regret of the contextual bandit problem
using our reduction. Existing analysis techniques for changing action sets
suffer $\log$ factors due to several reasons, such as bounding the radius of
an ellipsoid that contains the unknown parameter with high probability,
bounding the regret by the radius of the ellipsoid, or summing the regret over
multiple episodes; in contrast, the $\log$ factors in our analysis appear only
from a union bound used to prove concentration of the estimated arm means with
high probability.

The reduction also implies improved regret bounds for misspecified contextual
linear bandits by leveraging the optimal and nearly optimal regret bounds
proved in the literature [7] for fixed action sets. This results in high
probability bounds; as opposed to the best known results for changing action
sets that add $\log$ factors and only hold in expectation. As the reduction
introduces a small $\tilde{O}(1/\sqrt{T})$ misspecification, this adds to the
possibly unknown misspecification $\epsilon$. There is a little subtlety here;
some algorithms adapt to known $\epsilon$ better than the unknown case. To
avoid adding extra factors to the regret bounds by sub-optimal adaptation to
the known $\tilde{O}(1/\sqrt{T})$ part of misspecification, we slightly modify
existing algorithms to account for this. This is done by increasing the number
of times an arm is explored by a constant factor. Similarly, our results allow
to carry over the better regret bounds for linear bandits with adversarial
corruption to the contextual setting. This is achieved by modifying the
algorithms for linear bandits with adversarial corruption to account for the
known misspecification added by our reduction.

Our reduction has a byproduct; it limits the size of available actions in each
round to the minimum between $|\mathcal{A}|$ and the size of the parameter set
$\Theta$ (recall that we construct an action $g(\theta)$ for each
$\theta\in\Theta$). While in general a discretization of size $T^{\Omega(d)}$
is required to guarantee a good action in the discrete set, if the unknown
parameter follows some structure, a discretization of smaller size can be
sufficient. For example, for contextual linear bandits with $s$-sparse unknown
parameter, we show that a discretization of size $T^{O(s)}$ is sufficient.
This directly implies a high probability $O(\sqrt{dsT\log T})$ regret bound as
opposed to the best known $O(\sqrt{dsT}\log T)$ bound [6] that loses extra
$\log$ factors due to solving a linear regression problem over the space of
sparse unknown parameters.

As it is enough to make only batch updates to our estimates of the actions
$g(\theta)$, our algorithm can be modified to provide improved regret bounds
for contextual linear bandits with $O(\log\log T)$ batches. We use batch
lengths that were introduced in [12] which grow as $T^{1-2^{-m}}$. In each
batch, as action set is fixed, we utilize elimination algorithms with the
G-optimal design. However, at batch $m$, the gaps of sub-optimal actions
depend on the confidence of our estimates in batch $m-1$, which rely on the
G-optimal design using the estimates of $g$ from batch $m-2$. As a result, the
regret in batch $m$ can be at most the ratio between the length of batch $m$
and batch $m-2$. Considering the growth rate of the batch lengths, this ratio
can be large, especially in the first few batches. To fix this, we modify the
batch lengths to grow in length only at the batches with odd index, while even
batches use the same length as the previous batch. Our algorithm results in an
$O(d\sqrt{T\log T}\log\log T)$ regret bound using $O(\log\log T)$ batches,
improving a $\sqrt{\log d}$ factor (that appeared due to the distributional
G-optimal design proposed in [4]) in the regret bound over the best known
result [4]. Our result also provides the first high probability bound under
the $O(\log\log T)$ batches limitation.

As a consequence of the batch learning result and the fact that our reduction
can limit the action set based on the size of $\Theta$, we provide the first
algorithm with $O(\log\log T)$ batches for the sparse setting with a regret
bounded by $O(\sqrt{dsT\log T}\log\log T)$ with high probability, where $s$ is
the sparsity parameter.

###  1.3 Paper organization

Section 2 describes our setup and reviews notation; Section 3 describes our
reduction and main theorems; and Section 4 uses our reduction to prove
improved regret bounds for a number of stochastic linear bandit problems.

##  2 Notation and Models

Notation. We use the following notation throughout the paper. For a vector $X$
we use $X_{i}$ to denote the $i$-th element of the vector $X$. The set
$\\{1,...,i\\}$ for $i\in\mathbb{N},i>0$ is denoted by $[i]$, where
$\mathbb{N}$ is the set of natural numbers. We say that $y=O(f(x))$ if there
is $x_{0}$ and a constant $c$ such that $y\leq cf(x)$ $\forall x>x_{0}$; we
also use $\tilde{O}(f(x))$ to omit $\log$ factors. A $\delta$-net (with
respect to norm-2) of a set $\mathcal{A}\subseteq\mathbb{R}^{d}$ for
$\delta>0$ is any set $\mathcal{B}\subseteq\mathbb{R}^{d}$ such that for every
$a\in\mathcal{A}$, there exists $b\in\mathcal{B}$ with
$\|a-b\|_{2}\leq\delta$, where $\mathbb{R}$ is the set of real numbers. For a
set of sets $\mathcal{S}$, $\cup\mathcal{S}$ denotes the union of all elements
in $\mathcal{S}$. For a family of sets $\\{\mathcal{A}_{i}\\}_{i=1}^{n}$ we
use
$\prod_{i=1}^{n}\mathcal{A}_{i}=\\{(a_{1},...,a_{n})|a_{i}\in\mathcal{A}_{i},\;\forall
i\in[n]\\}$ to denote the product set.

Contextual Linear Bandits. We consider a contextual linear bandit problem,
where a learner interacts with an environment over a time horizon of length
$T$. At time $t\in[T]$, the learner observes a set of admissible arms
$\mathcal{A}_{t}$ representing the context, pulls an arm
$a_{t}\in\mathcal{A}_{t}$, and receives a reward

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

where the context $\mathcal{A}_{t}$ is generated from a distribution
$\mathcal{D}$, $a_{t}$ is a function of the history
$\mathcal{H}_{t}=\\{\mathcal{A}_{1},a_{1},r_{1},...,\mathcal{A}_{t}\\}$,
$\theta_{\star}$ is an unknown parameter vector of dimension $d$, and
$\eta_{t}$ is a random noise. Here, the noise $\eta_{t}$ follows an unknown
distribution that satisfies $\mathbb{E}[\eta_{t}|\mathcal{F}_{t}]=0$,
$\mathbb{E}[\exp(\lambda\eta_{t})|\mathcal{F}_{t}]\leq\exp(\lambda^{2}/2)$
$\forall\lambda\in\mathbb{R}$ (sub-Gaussian), where
$\mathcal{F}_{t}=\sigma\\{\mathcal{A}_{1},a_{1},r_{1},...,\mathcal{A}_{t},a_{t}\\}$
is the filtration of all historic information up to time $t$, and $\sigma(X)$
is the $\sigma$-algebra generated by $X$. We follow the standard assumptions
that $\theta_{\star}\in\Theta\subseteq\\{\theta|\ \|\theta\|_{2}\leq 1\\}$,
$\|a\|_{2}\leq 1$ $\forall a\in\mathcal{A}_{t}$ and $\forall t\in[T]$ almost
surely. The learner adopts a policy $\pi$ that maps the history up to time
$t$,
$(\mathcal{A}_{1},a_{1},r_{1},...,\mathcal{A}_{t-1},a_{t-1},r_{t-1},\mathcal{A}_{t})$,
to a probability distribution over $\mathcal{A}_{t}$; we denote the policy
$\pi(\mathcal{A}_{1},a_{1},r_{1},...,\mathcal{A}_{t-1},a_{t-1},r_{t-1},\mathcal{A}_{t})$
at time $t$ by $\pi_{t}(\mathcal{A}_{t})$. The goal of the learner is to
minimize the regret defined as

$R_{T}=\sum_{t=1}^{T}\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{\star}\rangle}-{\langle a_{t},\theta_{\star}\rangle}.$ (2)

In the next sections we assume for simplicity that for each $\theta\in\Theta$,
there is a unique $a_{t}\in\mathcal{A}_{t}$ that satisfies ${\langle
a_{t},\theta\rangle}=\sup_{a\in\mathcal{A}_{t}}{\langle a,\theta\rangle}$
almost surely. This is to avoid dealing with approximations and choice
functions (if there are multiple optimal actions) in the description of our
algorithms. However, our results do not need this assumption, please see Apps.
A.1.

Batch Learning. In this setting, the learner is allowed to change the policy
$\pi_{t}$ only at $M$ pre-specified time slots $1\leq t^{(1)},...,t^{(M)}\leq
T$, where $M$ is the number of batches.

Misspecified Linear Bandits. Here pulling an action $a\in\mathcal{A}_{t}$
generates a reward perturbed as

$r_{t}={\langle a,\theta_{\star}\rangle}+\eta_{t}+f(a),$ (3)

where $f$ is unknown perturbation function, $\theta_{\star}$ is the unknown
parameter vector, and $\eta_{t}$ is a zero-mean noise that is 1-subgaussian
conditioned on the history. The amount of deviation in the rewards is upper
bounded by $\epsilon=\sup_{a\in\cup\text{Supp}(\mathcal{D})}|f(a)|$, and
$\epsilon$ is called the amount of misspecification, where $\mathcal{D}$ is
the context distribution and $\text{Supp}(\mathcal{D})$ is the support set of
$\mathcal{D}$.

Adversarial Corruption. We assume an adversary that operates as follows at
each time $t$:
$\bullet$ The adversary observes the history of all past contexts
$\mathcal{A}_{1},...,\mathcal{A}_{t-1}$, actions $a_{1},...,a_{t-1}$, rewards
$r_{1},...,r_{t-1}$, and previously corrupted rewards
$\tilde{r}_{1},...,\tilde{r}_{t-1}$, together with the current context
$\mathcal{A}_{t}$.
$\bullet$ The adversary decides on a corruption function
$c_{t}:\mathcal{A}_{t}\to\mathbb{R}$ that determines the amount of corruption
for each action.
$\bullet$ The learner observes the history of contexts
$\mathcal{A}_{1},...,\mathcal{A}_{t}$, actions $a_{1},...,a_{t-1}$, and
previously corrupted rewards $\tilde{r}_{1},...,\tilde{r}_{t-1}$.
$\bullet$ The learner pulls arm $a_{t}$ and observes reward
$\tilde{r}_{t}=r_{t}+c_{t}(a_{t})$, where $c_{t}(a_{t})$ is the corruption
provided by the adversary.
Note that the true reward $r_{t}$ follows the linear bandits model, while the
corrupted rewards do not need to. We assume that the amount of corruption the
adversary can inflict is bounded as

$\sum_{t=1}^{T}\sup_{a\in\mathcal{A}_{t}}|c_{t}(a)|\leq C,$ (4)

where $C$ is the maximum amount of corruption.

Sparsity. We here assume that the $d$-dimensional parameter vector
$\theta_{\star}$ in (1) is sparse, namely $\|\theta_{\star}\|_{0}\leq s$ for
some known $s\in[d]$, where $\|\theta_{\star}\|_{0}$ denotes the norm-0 or
cardinality of the vector $\theta_{\star}$.

##  3 Reduction from Stochastic Contextual to Linear Bandits

###  3.1 Reduction for Known Context Distribution $\mathcal{D}$

We construct a contextual linear bandit algorithm $\mathcal{M}$ that operates
at a high level as follows. At each time $t$, the learner:
Step 1 (plays): observes a set of actions $\mathcal{A}_{t}$, uses $\theta_{t}$
(i.e., the current estimate of $\theta^{*}$) to decide which action
$a_{t}\in\mathcal{A}_{t}$ to play, and observes the associated reward $r_{t}$;
Step 2 (learns): calculates $\theta_{t+1}$, i.e., an updated estimate of
$\theta^{*}$.
In our reduction, we use a single-context algorithm $\Lambda$ for learning the
parameter $\theta_{\star}$ in step 2, i.e., choose $\theta_{t+1}$, and prove
that we can achieve the same worst-case regret bound as $\Lambda$.

##### Fixed action space.

We provide to the linear bandit algorithm $\Lambda$ the fixed action space

$\mathcal{X}=\\{g(\theta)|\theta\in\Theta\\},\mbox{ where
}g(\theta)=\mathbb{E}_{\mathcal{A}_{t}\sim\mathcal{D}}[\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta\rangle}|\theta].$ (5)

That is, for each $\theta$, we create an action $g(\theta)$ that is the
expected best action (under the distribution of the context $\mathcal{D}$)
with respect to the parameter $\theta$. We illustrate using a simple example.

Example 1. Assume that we may observe one out of the two following action sets
$\\{[1],[-1]\\},\\{[1]\\}$ randomly with probability $1/2$. The function
$g(\theta):\mathbb{R}\to\mathbb{R}$ can be calculated as follows

$g(\theta)=\left\\{\begin{array}[]{ll}1&\mbox{if }\theta\geq 0\\\ 0&\mbox{if
}\theta<0\end{array}\right.$ (6)

and thus $\mathcal{X}=\\{[0],[1]\\}.$

##### Reduction Algorithm.

The algorithm $\mathcal{M}$ proceeds at each time $t$ as follows:
1\. The single context algorithm $\Lambda$ decides to play an action
$g(\theta_{t})\in\mathcal{X}$, using the history $\Lambda$ observed. This
action is never actually played. Instead, $\mathcal{M}$ observes what action
$g(\theta_{t})$ that $\Lambda$ selected, and uses the associated $\theta_{t}$
as its current estimate of $\theta_{\star}$.
2\. $\mathcal{M}$ observes $\mathcal{A}_{t}$, plays the action
$a_{t}=\arg\max_{a\in\mathcal{A}_{t}}{\langle a,\theta_{t}\rangle}$ and
receives reward $r_{t}$. It provides this reward to $\Lambda$.
3\. $\Lambda$ assumes that the reward $r_{t}$ it received was generated
according to the linear bandit model $r_{t}={\langle
g(\theta_{t}),\theta_{\star}\rangle}+\eta^{\prime}_{t},$ and adds the action-
reward pair $(g(\theta_{t}),r_{t})$ to its history.

Note that the set of actions $\mathcal{X}$ we created contains actions that
may not be part of the original sets $\mathcal{A}_{t}$’s; this is fine, since
these actions are actually never played - they are used to simulate an
environment that enables $\Lambda$ to correctly update its estimate of
$\theta_{\star}$. That is, although all actions played come from the eligible
sets $\mathcal{A}_{t}$, all learning (updates on $\theta_{t}$) is derived from
the single context algorithm $\Lambda$ that never explicitly learns
$\mathcal{A}_{t}$.

######  Theorem 1.

Let $\Lambda$ be any algorithm for linear bandits and $I$ be a contextual
linear bandit instance with stochastic contexts, unknown parameter
$\theta_{\star}$ and rewards $r_{t}$ generated as described in the reduction
algorithm described above. It holds that
$\bullet$ The reward $r_{t}$ is generated, by pulling the arm $g(\theta_{t})$,
from a linear bandit instance $L$ with action set $\mathcal{X}$, and unknown
parameter $\theta_{\star}$.
$\bullet$ The reduction results in an algorithm $\mathcal{M}$ for contextual
linear bandits such that with probability at least $1-\delta$ we have

$|R_{T}^{\mathcal{M}}(I)-R_{T}^{\Lambda}(L)|\leq c\sqrt{T\log(1/\delta)},$ (7)

where $R^{\Lambda}_{T}(L)$ is the regret of $\Lambda$ over the constructed
linear bandit instance $L$, $R_{T}^{\mathcal{M}}(I)$ is the regret of
algorithm $\mathcal{M}$ over the instance $I$ and $c$ is a universal constant.

Proof Outline. The complete proof is provided in App. A; we here provide a
brief outline. The basic idea is to show that the action taken by algorithm
$\mathcal{M}$ at time $t$ is an unbiased estimate of $g(\theta_{t})$, then
decompose $R_{T}^{\mathcal{M}}(I)$ as

$\displaystyle R_{T}^{\mathcal{M}}(I)$
$\displaystyle=\sum_{t=1}^{T}{\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{\star}\rangle},\theta_{\star}\rangle}-\mathbb{E}[{\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{\star}\rangle},\theta_{\star}\rangle}]$
$\displaystyle\qquad+\mathbb{E}[{\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{t}\rangle},\theta_{\star}\rangle}|\theta_{t}]-{\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{t}\rangle},\theta_{\star}\rangle}+{\langle
g(\theta_{\star}),\theta_{\star}\rangle}-{\langle
g(\theta_{t}),\theta_{\star}\rangle},$ (8)

where the expectation is with respect to the randomness in the context
generation $\mathcal{A}_{t}$. We then prove and use results such as ${\langle
g(\theta^{\prime}),\theta^{\prime}\rangle}=\max_{\theta\in\Theta}{\langle
g(\theta),\theta^{\prime}\rangle},\;\forall\;\theta^{\prime}\in\Theta,$ to
arrive at

$\displaystyle|R_{T}^{\mathcal{M}}(I)-R_{T}^{\Lambda}(L)|$
$\displaystyle\leq|\sum_{t=1}^{T}{\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{\star}\rangle},\theta_{\star}\rangle}-\mathbb{E}[{\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{\star}\rangle},\theta_{\star}\rangle}]|$
$\displaystyle\qquad+|\sum_{t=1}^{T}\mathbb{E}[{\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{t}\rangle},\theta_{\star}\rangle}|\theta_{t}]-{\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{t}\rangle},\theta_{\star}\rangle}|,$ (9)

Next, we show that the quantity
$\Sigma_{T}:=\sum_{t=1}^{T}\mathbb{E}[{\langle\arg\max_{a_{\in}\mathcal{A}_{t}}{\langle
a,\theta_{t}\rangle},\theta_{\star}\rangle}|\theta_{t}]-{\langle\arg\max_{a_{\in}\mathcal{A}_{t}}{\langle
a,\theta_{t}\rangle},\theta_{\star}\rangle}$ is a martingale (using that
$a_{t}$ is unbiased estimate of $g(\theta_{t})$) with a bounded difference (by
boundedness of $\Theta,\mathcal{A}_{t}$) and apply the Azuma–Hoeffding
inequality to bound these terms with high probability. To prove that the
rewards $r_{t}$ come from a linear bandit instance $L$, we finally show that
the reward $r_{t}$ can be expressed as $r_{t}={\langle
g(\theta_{t}),\theta_{\star}\rangle}+\eta^{\prime}_{t}$, where
$\eta^{\prime}_{t}$ is a zero mean $1$-sub-Gaussian noise conditioned on the
filtration of historic information $\theta_{1},...,\theta_{t}$ and rewards
$r_{1},...,r_{t-1}$ of the instance $L$. $\square$

Algorithm 1  Reduction from stochastic contexts to no context

1:Input: confidence parameter $\delta$, phase lengths
$\\{t^{(m)}\\}_{m=1}^{M+1}$, and algorithm ${\Lambda_{\epsilon}}$ for linear
contextual bandits with $\epsilon$ misspecification.

2:Initialize: $g^{(1)}:\Theta^{\prime}\to\mathbb{R}^{d}$ randomly,
$\epsilon_{1}=1$, and let
$\mathcal{X}_{1}=\\{g^{(1)}(\theta)|\theta\in\Theta^{\prime}\\}$.

3:for $m=1:M$ do

4: for $t=t^{(m)}+1,...,t^{(m+1)}$ do

5: Let $g^{(m)}(\theta_{t})\in\mathcal{X}_{m}$ be the arm selected by
$\Lambda_{\epsilon_{m}}$ after observing rewards $r_{t^{(m)}+1},...,r_{t-1}$.

6: Play arm $a_{t}=\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{t}\rangle}$ and receive reward $r_{t}$. Provide $r_{t}$ to
${\Lambda_{\epsilon_{m}}}$.

7: Update:
$g^{(m+1)}(\theta)=\frac{1}{t^{(m+1)}}\sum_{t=1}^{t^{(m+1)}}\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta\rangle}$,
$\mathcal{X}_{m+1}=\\{g^{(m+1)}(\theta)|\theta\in\Theta^{\prime}\\}$, and
$\epsilon_{m+1}=2\sqrt{\log(M|\Theta^{\prime}|/\delta)/t^{(m+1)}}$

###  3.2 Reduction for Unknown Context Distribution

As described in (5), calculating the function $g(\theta)$ requires knowledge
of the distribution $\mathcal{D}$. We do not really need this knowledge; we
prove it is sufficient to use empirical estimation of $g(\theta)$. As a
result, we prove that any stochastic linear contextual bandit instance, even
for unknown context distributions, can be reduced to a linear bandit instance
albeit with a small misspecification.

Our basic approach follows the reduction in Section 3.1 but uses a sequence of
functions $g^{(m)}$ that approximate $g$ increasingly well (as $m$ increases).
To do so, as it is hard to guarantee a good estimate of $g$ for all $\theta$,
we restrict our attention to a finite subset of $\Theta$ that is large enough
to include a good action. In particular, instead of considering actions in a
continuous space $\Theta$, we only consider a finite subset of actions
$\Theta^{\prime}\subseteq\Theta$, where $\Theta^{\prime}$ is an $1/T$-net for
$\Theta$ according to the norm-2 distance. We divide the time horizon $T$ into
$M$ epochs, each of duration $T_{m}=t^{(m+1)}-t^{(m)}$, $m=1\ldots M$. For
each epoch, we construct an empirical estimate of $g$ as
$g^{(m)}(\theta)=\frac{1}{t^{(m)}}\sum_{t=1}^{t^{(m)}}(\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta\rangle})$, and calculate the set of actions
$\mathcal{X}_{m}=\\{g^{(m)}(\theta)|\theta\in\Theta^{\prime}\\}$. We then use
at each epoch a single context algorithm as before, but we now provide at
epoch $m$ the fixed set of actions $\mathcal{X}_{m}$ for the algorithm to
choose from. As a result, the regret of the linear bandit problem is defined
as

$R^{\Lambda_{\epsilon}}_{T}=\sum_{t=1}^{T}\max_{\theta\in\Theta^{\prime}}{\langle
g(\theta),\theta_{\star}\rangle}-{\langle
g(\theta_{t}),\theta_{\star}\rangle}.$ (10)

Our algorithm relies on $\Lambda_{\epsilon}$, an algorithm for linear bandits
with $\epsilon$ misspecification. The misspecification reflects our confidence
in our estimate of the function $g$, hence, decreases each epoch. We start
with a large value of the misspecification parameter $\epsilon_{1}=1$ and a
random initialization of the function $g$ (which we cal $g^{(1)}$), and hence
random initialization of $\mathcal{X}$ denoted $\mathcal{X}_{1}$. At time slot
$t$ of epoch $m$, the algorithm asks $\Lambda_{\epsilon_{m}}$ for an action to
play $g^{(m)}(\theta_{t})\in\mathcal{X}_{m}$ given the history of action and
rewards $\\{(g^{(m)}(\theta_{i}),r_{i})\\}_{i=t^{(m)}+1}^{t-1}$ in epoch $m$
only. The algorithm pulls the action
$a_{t}=\arg\max_{a\in\mathcal{A}_{t}}{\langle a,\theta_{t}\rangle}$ and
observes $r_{t}$. The reward $r_{t}$ is then passed to the algorithm
$\Lambda_{\epsilon_{m}}$. At the end of each epoch, the misspecification
parameter, estimates $g^{(m)}$, and action set $\mathcal{X}_{m}$ are updated.
The pseudo-code of our reduction is provided in Algorithm 1, and the proof in
App. B. To achieve nearly optimal regret bounds, the misspecification
$\epsilon$ need to be $\tilde{O}(1/\sqrt{T})$ (recall the
$\Omega(\sqrt{d}\epsilon T)$ regret lower bound [7]). Attempting to use $M=2$
to first estimate $g$ and then learn in the second epoch, would require the
length of the first epoch to be $\Omega(T)$, to ensure the
$\tilde{O}(1/\sqrt{T})$ misspecification, resulting in linear regret. Instead,
as we clarify next, we use exponentially increasing epoch lengths to mix the
learning with a gradual estimation of $g$ resulting in misspecification that
is effectively $\tilde{O}(1/\sqrt{T})$.

######  Theorem 2.

Let $\Lambda_{\epsilon}$ be an algorithm for linear bandits with $\epsilon$
misspecification and $I$ be a contextual linear bandit instance with
stochastic contexts, unknown parameter $\theta_{\star}$ and rewards $r_{t}$
are generated as described in Algorithm 1. The following holds:
$\bullet$ Conditioned on
$\mathcal{H}_{t^{(m)}}=\sigma(\mathcal{A}_{1},a_{1},r_{1},...,\mathcal{A}_{t^{(m)}},a_{t^{(m)}},r_{t^{(m)}})$:
in epoch $m$, the rewards $r_{t}$ are generated, by pulling arm
$g^{(m)}(\theta_{t})$, from a misspecified linear bandit instance $L_{m}$ for
$t=t^{(m)}+1,...,t^{(m+1)}$, action set
$\mathcal{X}_{m}=\\{g^{(m)}(\theta)|\theta\in\Theta^{\prime}\\}$, unknown
parameter $\theta_{\star}$, mean rewards ${\langle
g(\theta),\theta_{\star}\rangle}$, and unknown misspecification
$\epsilon^{\prime}_{m}$.
$\bullet$ The misspecification $\epsilon^{\prime}_{m}$ is bounded by the known
quantity $\epsilon_{m}$ with probability at least $1-c\delta/M$.
$\bullet$ With probability at least $1-\delta$ we have that
$|R_{T}(I)-\sum_{m=1}^{M}R^{\Lambda_{\epsilon_{m}}}_{T_{m}}(L_{m})|\leq
c\sqrt{T\log(1/\delta)}$, where $R_{T}(I)$ is the regret of Algorithm 1 over
the instance $I$, $R^{\Lambda_{\epsilon_{m}}}_{T_{m}}(L_{m})$ is the regret of
algorithm $\Lambda_{\epsilon_{m}}$ over the bandit instance $L_{m}$ in phase
$m$, $T_{m}=t^{(m+1)}-t^{(m)}$, and $c$ is a universal constant.

As a consequence, we prove the following corollary in Section 4.1.

######  Corollary 1.

For Algorithm 1 with $t^{(m)}=2^{m-1}$ and $\Lambda_{\epsilon}$ to be PE with
modified confidence intervals [7], it holds that with probability at least
$1-c\delta$ we have that $R_{T}=O(d\sqrt{T\log(T/\delta)})$.

Algorithm 2  Reduction from stochastic contexts to no context for product
context sets

1:Input: an algorithm ${\Lambda}$ for linear contextual bandits with action
set  $\mathcal{X}=\\{a^{\prime}\in\\{0,1\\}^{2d}|\
a^{\prime}_{2i-1}+a^{\prime}_{2i}=1\ \forall i\in[d]\\}$ (11)

2:for $t=1:T$ do

3: Ask $\Lambda$ for an arm to play $a^{\prime}_{t}\in\mathcal{X}$ given the
history $r_{1},...,r_{t-1}$.

4: Play arm $a_{t}$ with $(a_{t})_{i}=\max\\{a\in\mathcal{A}_{t}^{(i)}\\}$ if
$a^{\prime}_{2i-1}=1$ and $(a_{t})_{i}=\min\\{a\in\mathcal{A}_{t}^{(i)}\\}$
otherwise. Receive reward $r_{t}$.

###  3.3 Reduction When Context is a Product Set

In this section, we consider the special case where the action distribution
$\mathcal{D}$ is unknown, but the action space has a coordinate-wise product
structure, i.e.,

######  Assumption 1.

$\mathcal{A}_{t}=\prod_{i=1}^{d}\mathcal{A}_{t}^{(i)}$, where
$\mathcal{A}_{t}^{(i)}\subset\mathbb{R}$.

This is an important hard instance that appears in many lower bounds [11]. We
will show that in this case, the $d$-dimensional stochastic contextual bandits
can be reduced to a linear bandit problem with no misspecification, although
the distribution $\mathcal{D}$ is unknown, but where now the parameter vector
is over $2d$ dimensions.

The main idea of the reduction is that $g(\theta)$ can be factored into a
coordinate-wise product between an unknown vector that only depends on the
context distribution and a known vector that only depends on $\theta$. The
unknown vector can be incorporated with $\theta_{\star}$ reducing the
contextual instance to a linear bandit instance but now with a different
unknown parameter $\theta_{\star}^{\prime}$. In particular, we can write
${\langle g(\theta),\theta_{\star}\rangle}={\langle
a^{\prime}(\theta),\theta_{\star}^{\prime}\rangle}$, where
$a^{\prime}(\theta)$ is a vector in $\mathbb{R}^{2d}$ that does not depend on
the distribution, and equals

$(a^{\prime}(\theta))_{2i}=\left\\{\begin{array}[]{ll}1&\mbox{if
}(\theta)_{i}<0\\\ 0&\mbox{otherwise}\end{array}\right.\mbox{ and }\
(a^{\prime}(\theta))_{2i-1}=1-(a^{\prime}(\theta))_{2i}\quad\forall
i=1,\ldots,d,.$ (12)

Thus, we can follow the same reduction algorithm as in Section 3.1, but where
now we call a $2d$-dimensional linear bandit algorithm $\Lambda$ and provide
$\Lambda$ with the fixed action set

$\mathcal{X}=\\{a^{\prime}\in\\{0,1\\}^{2d}|\
a^{\prime}_{2i-1}+a^{\prime}_{2i}=1\ \forall i\in[d]\\}$ (13)

as the pseudocode Algorithm 2 describes.

######  Theorem 3.

Let $\Lambda$ be any algorithm for linear bandits, $I$ be a contextual linear
bandit instance with stochastic contexts that satisfy Assumption 1 with
unknown parameter $\theta_{\star}$, and $r_{t}$ be the rewards generated as
described in Algorithm 2. It holds that
$\bullet$ The rewards $r_{t}$ are generated, by pulling arm $a^{\prime}_{t}$,
from a linear bandit instance $L$ with action set $\mathcal{X}$ in (11), and
unknown parameter $\theta_{\star}^{\prime}\in\mathbb{R}^{2d}$ with
$\|\theta_{\star}^{\prime}\|_{2}\leq 2$.
$\bullet$ With probability at least $1-\delta$ it holds that

$|R_{T}(I)-R_{T}^{\Lambda}(L)|\leq c\sqrt{T\log(1/\delta)},$ (14)

where $R_{T}(I)$ is the regret of Algorithm 2 over the instance $I$ and
$R_{T}^{\Lambda}(L)$ is the regret of algorithm $\Lambda$ over the instance
$L$, and $c$ is a universal constant.

###### Proof.

The proof follows from Theorem 1 using the observation that

$(g(\theta))_{i}=\left\\{\begin{array}[]{ll}\mathbb{E}_{\mathcal{A}\sim\mathcal{D}}[\max_{a\in\mathcal{A}}(a)_{i}]&\mbox{if
}(\theta)_{i}<0\\\
\mathbb{E}_{\mathcal{A}\sim\mathcal{D}}[\min_{a\in\mathcal{A}}(a)_{i}]&\mbox{if
}(\theta)_{i}>0\end{array}\right..$ (15)

and thus, given (13), we can define
$\theta_{\star}^{\prime}\in\mathbb{R}^{2d}$ as

$(\theta_{\star}^{\prime})_{i}=\left\\{\begin{array}[]{ll}\mathbb{E}[\max_{a\in\mathcal{A}}(a)_{(i+1)/2}](\theta_{\star})_{(i+1)/2}&\mbox{if
$i$ is odd}\\\
\mathbb{E}[\min_{a\in\mathcal{A}}(a)_{\lfloor(i+1)/2\rfloor}](\theta_{\star})_{\lfloor(i+1)/2\rfloor}&\mbox{if
$i$ is even.}\end{array}\right.$ (16)

By definition of $a^{\prime}(\theta),\theta_{\star}^{\prime}$, we have that
${\langle g(\theta),\theta_{\star}\rangle}={\langle
a^{\prime}(\theta),\theta_{\star}^{\prime}\rangle}$. To see that
$\|\theta_{\star}^{\prime}\|\leq 2$, we observe that

$\sum_{i=1}^{d}|(\theta_{\star}^{\prime})_{2i}|=\sum_{i=1}^{d}|\mathbb{E}[\max_{a\in\mathcal{A}}(a)_{i}](\theta_{\star})_{i}|\leq{\langle|g(\mathbf{1}/\sqrt{d})|,|\theta_{\star}|\rangle}\leq
1,$ (17)

where absolute value of a vector is defined as a vector with
$(|\theta_{\star}|)_{i}=|(\theta_{\star})_{i}|$. Similarly,
$\sum_{i=1}^{d}|(\theta_{\star}^{\prime})_{2i-1}|\leq 1$. Hence,
$\|\theta_{\star}^{\prime}\|_{2}\leq\|\theta_{\star}^{\prime}\|_{1}\leq 2$.

As before, to construct the linear bandit instance, we need rewards that
follow the stochastic linear bandits model. The result follows from
Proposition 1 and the fact that ${\langle
g(\theta_{t}),\theta_{\star}\rangle}={\langle
a_{t},\theta_{\star}^{\prime}\rangle}$. ∎

##  4 Implications

###  4.1 Tighter Regret Bound for Contextual Linear Bandits

In this subsection, we show that our reduction leads to the first
$O(d\sqrt{T\log T})$ high probability upper bound for linear bandits with
changing action sets. We rely on the Phased Elimination (PE) [7] as our linear
bandit algorithm $\Lambda_{\epsilon}$. PE is the same as Algorithm 3, that we
will use next in the batched setting, except that $\mathcal{X},g$ are fixed
(recall that we apply PE within an epoch that fixes the estimate of $g$). The
parameter $\gamma_{m}$ in Algorithm 3 is called the confidence interval; we
will specify its value in our theorems. In Algorithm 1, setting
$t^{(m)}=2^{m-1}$ and $\Lambda_{\epsilon}$ to be PE with modified confidence
intervals [7] to account for the misspecification we get the following
corollary.

######  Corollary 2.

For Algorithm 1 with $t^{(m)}=2^{m-1}$ and $\Lambda_{\epsilon_{m}}$ to be PE
with $\gamma_{m}=6\sqrt{d\log(T|\Theta^{\prime}|/\delta)/t^{(m)}}$ it holds
that with probability at least $1-c\delta$ we have that $R_{T}\leq
c\sqrt{dT\log(T|\Theta^{\prime}|/\delta)}$.

###### Proof.

Let the length of phase $m$ be $T_{m}=t^{(m+1)}-t^{(m)}=2^{m-1}$. Conditioned
on the event that the misspecification in phase $m$ is bounded by
$\epsilon_{m}$, PE with modified confidence intervals achieves a regret
$R^{\Lambda_{\epsilon_{m}}}_{T_{m}}$ that is upper bounded by
$O(\sqrt{dT_{m}\log(T_{m}M|\Theta^{\prime}|/\delta))}+\sqrt{d}T_{m}\epsilon_{m})$
with probability at least $1-\delta/M$. Hence, by Proposition 2 and the union
bound we have that it holds with probability at least $1-c\delta$ that

$R^{\Lambda_{\epsilon_{m}}}_{T_{m}}\leq
c(\sqrt{dT_{m}\log(T|\Theta^{\prime}|/\delta)}+\sqrt{d}T_{m}\epsilon_{m})\forall
m\in[M],$ (18)

where we used the fact that $T_{m}\leq T,M\leq T$. Substituting the value of
$\epsilon_{m}$ we get that the following holds with probability at least
$1-c\delta$

$\displaystyle R^{\Lambda_{\epsilon_{m}}}_{T_{m}}$ $\displaystyle\leq
c(\sqrt{dT_{m}\log(T|\Theta^{\prime}|/\delta)}+\sqrt{d}T_{m}\sqrt{\frac{\log(M|\Theta^{\prime}|/\delta)}{t^{(m)}}})$
$\displaystyle=c(\sqrt{dT_{m}\log(T|\Theta^{\prime}|/\delta)}+\sqrt{dT_{m}\log(M|\Theta^{\prime}|/\delta)})\forall
m\in[M].$ (19)

Hence, using $M\leq T$, we get that with probability at least $1-c\delta$ we
have

$R^{\Lambda_{\epsilon_{m}}}_{T_{m}}\leq
c\sqrt{dT_{m}\log(T|\Theta^{\prime}|/\delta)}$ (20)

Substituting in Theorem 2, we get that with probability at least $1-c\delta$
it holds that

$\displaystyle R_{T}$ $\displaystyle\leq c\sqrt{T\log
T}+c\sqrt{d\log(T|\Theta^{\prime}|/\delta)}\sum_{m=1}^{\log T}\sqrt{T_{m}}$
$\displaystyle\leq
c^{\prime}\sqrt{dT\log(T|\Theta^{\prime}|/\delta)}\sum_{m=1}^{\log
T}\sqrt{2^{m-\log T}}$ $\displaystyle\leq
c^{\prime}\sqrt{dT\log(T|\Theta^{\prime}|/\delta)}\sum_{i=0}^{\infty}\sqrt{2^{-i}}$
$\displaystyle\leq\frac{c^{\prime}}{1-1/\sqrt{2}}\sqrt{dT\log(T|\Theta^{\prime}|/\delta)}.$
(21)

∎

It is well known that if $\Theta\subseteq\\{a\in\mathbb{R}^{d}|\|a\|_{2}\leq
1\\}$, then there is $1/T$-net of $\Theta$, $\Theta^{\prime}$, such that
$|\Theta^{\prime}|\leq(6T)^{d},\Theta^{\prime}\subseteq\Theta$. This directly
implies that $R_{T}=O(d\sqrt{T\log(T)})$ with probability at least $1-1/T$.
This improves a factor of $\sqrt{\log T}\log\log T$ over [2] and a factor of
$\sqrt{\log T}$ over [3].

###  4.2 Batch Learning

In this subsection, we show that our reduction can be applied to improve the
result of [4] for contextual linear bandits with stochastic contexts by
providing a regret upper bound of $O(d\sqrt{T\log T}\log\log T)$ with high
probability as opposed to the in expectation $O(d\sqrt{T\log d\log T}\log\log
T)$ regret bound in [4]. This can be achieved by replacing
$\Lambda_{\epsilon_{m}}$ with the $G$-optimal design policy constructed using
$\mathcal{X}_{m}$. To compute $t^{(i)}$ we first define

$u_{m}=T^{1-2^{-m}},m=1,...,M/2.$ (22)

We let

$t^{(m)}=\lfloor u_{m//2+1}\rfloor\forall m\in[M],t^{(M+1)}=T.$ (23)

where $//$ denotes integer division. For completeness, we include the pseudo-
code in Algorithm 3. The following result follows using Theorem 2.

######  Theorem 4.

For Algorithm 1 with $M=2\log\log T$ (corresponds to $2\log\log T+1$ batches),
$t^{(m)}$ given in (23) and $\Lambda_{\epsilon_{m}}$ replaced by the
$G$-optimal design policy constructed using $\mathcal{X}_{m}$, it holds that
there is a constant $c$ such that with probability at least $1-c\delta$, we
have

$R_{T}\leq c\sqrt{dT\log(\frac{M|\Theta^{\prime}|}{\delta})}\log\log T.$ (24)

###### Proof.

We first notice that for $M=\log\log T$, we have that
$u_{m+1}/\sqrt{u_{m}}=\sqrt{T}\forall m\in[M-1]$,
$u_{M+1}/\sqrt{u_{M}}=\sqrt{2T}$. Hence, we have that

$u_{m+1}/\sqrt{u_{m}}\leq\sqrt{2T}\forall m\in[M].$ (25)

We also have that $u_{m+1}\geq u_{m}\ \forall m\geq 1$ (since $u_{m}\leq T$).
The proof follows from the properties of the G-optimal design together with
the properties of $g^{(m)}$ in the proof of Theorem 2. The G-optimal design
ensures that for any $\theta\in\Theta^{\prime}$ the following holds with
probability at least $1-\delta$

$|{\langle g^{(m)}(\theta),\hat{\theta}_{m}-\theta_{\star}\rangle}|\leq
2\epsilon^{\prime}_{m}\sqrt{d}+\sqrt{\frac{4d}{T_{m}}\log 1/\delta},$ (26)

where $\epsilon^{\prime}_{m}=\sup_{\theta\in\Theta^{\prime}}|{\langle
g^{(m)}(\theta)-g(\theta),\theta_{\star}\rangle}|$. By the triangle
inequality, we have that

$\displaystyle|{\langle g^{(m)}(\theta),\hat{\theta}_{m}\rangle}-{\langle
g(\theta),\theta_{\star}\rangle}|$ $\displaystyle\leq
2\epsilon^{\prime}_{m}\sqrt{d}+\sqrt{\frac{4d}{T_{m}}\log 1/\delta}+|{\langle
g^{(m)}(\theta)-g(\theta),\theta_{\star}\rangle}|$
$\displaystyle\leq\epsilon^{\prime}_{m}(2\sqrt{d}+1)+\sqrt{\frac{4d}{T_{m}}\log
1/\delta}$ (27)

By Proposition 2 we have that $\epsilon^{\prime}_{m}\leq\epsilon_{m}\forall
m\in[M]$ with probability at least $1-\delta$. Hence, by the union bound we
have that the following holds with probability at least $1-\delta$

$|{\langle g^{(m)}(\theta),\hat{\theta}_{m}\rangle}-{\langle
g(\theta),\theta_{\star}\rangle}|\leq\epsilon_{m}(2\sqrt{d}+1)+\sqrt{\frac{4d}{T_{m}}\log(\frac{M|\Theta^{\prime}|}{\delta})}\forall\theta\in\Theta^{\prime}\forall
m\in[M].$ (28)

Hence, with probability at least $1-\delta$, the best arm is not eliminated
and the arms that are not eliminated at the end of batch $m$, will have a gap
that is at most twice the confidence interval in (28), otherwise, they satisfy
the elimination criterion with $\theta_{\star}$. Hence, the sum regret
$\sum_{m=1}^{M}R^{\Lambda_{\epsilon_{m}}}_{T_{m}}(L_{m})$ is bounded as
follows with probability at least $1-\delta$

$\displaystyle\sum_{m=1}^{M}R^{\Lambda_{\epsilon_{m}}}_{T_{m}}(L_{m})$
$\displaystyle\leq\sqrt{T}+c^{\prime}\sum_{m=1}^{M}\epsilon_{m}(2\sqrt{d}+1)T_{m+1}+c^{\prime}\sqrt{\frac{4d}{T_{m}}\log(\frac{M|\Theta^{\prime}|}{\delta})}T_{m+1}$
$\displaystyle=\sqrt{T}+c\sqrt{d\log(\frac{M|\Theta^{\prime}|}{\delta})}\sum_{m=1}^{M}\frac{T_{m+1}}{\sqrt{T_{m-1}}}+\frac{T_{m+1}}{\sqrt{T_{m}}}$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{\leq}}\sqrt{T}+2c\sqrt{d\log(\frac{M|\Theta^{\prime}|}{\delta})}\sum_{m=1}^{M}\frac{T_{m+1}}{\sqrt{T_{m-1}}}+\sqrt{T}$
$\displaystyle\stackrel{{\scriptstyle(ii)}}{{\leq}}\sqrt{T}+2c\sqrt{d\log(\frac{M|\Theta^{\prime}|}{\delta})}\sum_{m=1}^{M}\sqrt{T}+\sqrt{T}$
$\displaystyle\leq
c^{\prime\prime}\sqrt{dT\log(\frac{M|\Theta^{\prime}|}{\delta})}\log\log T,$
(29)

where $(i)$ uses (25) and the fact that either $T_{m+1}\leq\sqrt{2T_{m}}$ or
$T_{m+1}=T_{m}\leq\sqrt{2TT_{m}}$, and $(ii)$ follows from the fact that
either ($T_{m}=T_{m-1}$ and $T_{m+1}\leq\sqrt{2TT_{m}}$) or
($T_{m}\leq\sqrt{2TT_{m-1}}$ and $T_{m+1}=T_{m}$), hence, in both cases we
have $T_{m+1}\leq\sqrt{2TT_{m-1}}$. The results follow by Theorem 2 and the
union bound. ∎

As in Section 4.1, this implies that $R_{T}=O(d\sqrt{T\log(T)}\log\log T)$
with probability at least $1-1/T$, which strengthens the result in [4] to high
probability result and also improves a factor of $\log d$ in the regret bound.
Moreover, as will be seen in the following subsections, if $\theta_{\star}$ is
$s$-sparse, Theorem 4 implies a regret bound of $O(\sqrt{dsT\log T}\log\log
T)$ with probability at least $1-1/T$. To the best of our knowledge, this is
the first nearly optimal algorithm for sparse unknown parameters that uses
$O(\log\log T)$ batches.

Algorithm 3  Batched algorithm for linear bandits with stochastic context

1:Input: confidence parameter $\delta$, and phase lengths
$\\{t^{(m)}\\}_{m=1}^{M}$.

2:Initialize: $g^{(1)}:\Theta^{\prime}\to\mathbb{R}^{d}$ randomly,
$\Theta_{1}=\Theta^{\prime}$, and let
$\mathcal{X}_{1}=\\{g^{(1)}(\theta)|\theta\in\Theta^{\prime}\\}$.

3:for $m=1:M$ do

4: Find design $\rho:\mathcal{X}_{m}\to[0,1]$ with
$\max_{a\in\text{Supp}(\rho)}\|a\|^{2}_{G^{-1}(\rho)}\leq 2d$,
$|\text{Supp}(\rho)|\leq 4d\log\log d+16$, where
$G(\rho)=\sum_{a\in\text{Supp}(\rho)}\rho(a)aa^{T}$.

5: Compute $u(x)=\lceil\rho(x)T_{m}\rceil$ and
$u=\sum_{x\in\text{Supp}(\rho)}u(x)$.

6: Use the policy described by $a_{t}=\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta\rangle}$ for $u(g^{(m)}(\theta))$ times for each
$\theta\in\Theta_{m}$ with $g^{(m)}(\theta)\in\text{Supp}(\rho)$.

7:
$\hat{\theta}_{m}=(\sum_{g\in\text{Supp}(\rho)}u(g)gg^{T})^{-1}\sum_{i=1}^{u}r_{i}g^{(m)}(\theta_{i})$.

8: Update:
$\Theta_{m+1}=\left\\{\theta\in\Theta_{m}|\max_{\theta^{\prime}\in\Theta_{m}}{\langle\hat{\theta}_{m},g^{(m)}(\theta^{\prime})-g^{(m)}(\theta)\rangle}\leq\gamma_{m}\right\\}$,
$\gamma_{m}=10\sqrt{\frac{d}{T_{m-1}}\log(M|\Theta^{\prime}|/\delta)}$.

9: Update:
$g^{(m+1)}(\theta)=\frac{1}{t^{(m+1)}}\sum_{t=1}^{t^{(m+1)}}\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta\rangle}$, and
$\mathcal{X}_{m+1}=\\{g^{(m+1)}(\theta)|\theta\in\Theta^{\prime}\\}$.

###  4.3 Misspecified Contextual Linear Bandits

Our reduction framework can be used to improve regret bounds for misspecified
contextual linear bandits. By noticing that for $\epsilon$ misspecified
contextual linear bandits, the total amount of misspecification in epoch $m$
is bounded by $\epsilon_{m}+\epsilon$ with high probability, the following
result follows directly from [7].

######  Theorem 5.

For contextual linear bandits with known misspecification that is bounded by
$\epsilon$, Algorithm 1 with $\Lambda_{\epsilon_{m}}$ being PE with
$\gamma_{m}=6d\sqrt{\log(T)/T_{m}}+\epsilon\sqrt{d}$ achieves a regret bound

$R_{T}\leq c(d\sqrt{T\log(T/\delta)}+\epsilon\sqrt{d}T)$ (30)

with probability at least $1-c\delta$.

If $\epsilon$ is unknown, [7] showed that PE achieves a regret upper bounded
by $O(d\sqrt{T\log(T)}+\epsilon\sqrt{d}T\log T$ with high probability. We
notice that the dependency on $\epsilon$ has an extra $\log T$ factor as
compared to the known misspecification result. To avoid adding the $\log T$
factor in the term containing $\epsilon_{m}$, we exploit the knowledge of
$\epsilon_{m}$ to modify the confidence intervals in PE. We note that
following the same analysis in [7] by replacing $\epsilon$ with
$\epsilon+\epsilon_{m}$ results in the same concentration of estimated means
except for constant factors, which implies the following result.

######  Theorem 6.

For contextual linear bandits with unknown misspecification that is bounded by
$\epsilon$, Algorithm 1 with $\Lambda_{\epsilon_{m}}$ being PE with
$\gamma_{m}=6d\sqrt{\log(T)/T_{m}}$ achieves a regret bound

$R_{T}\leq c(d\sqrt{T\log(T/\delta)}+\epsilon\sqrt{d}T\log T)$ (31)

with probability at least $1-c\delta$.

###### Proof.

The proof follows similar steps as in the proof of Proposition 5.1 in [7] with
different constants due to the change in $\gamma_{m}$. ∎

We note that as PE is performed in each epoch, the number of batches is
$\Omega(\log^{2}T)$. However, we constructed the algorithm this way only for
simplicity. It is possible to perform PE once and update the estimates of $g$
at the end of each batch similar to Algorithm 3.

###  4.4 Bandits With Adversarial Corruption

Our reduction directly extends the results for linear bandits with adversarial
corruption to the contextual setting while maintaining the same regret bounds
up to $\log$ factors. This leads to $\tilde{O}(d\sqrt{T}+d^{1.5}C)$ high
probability regret bound as opposed to the best known
$\tilde{O}(d^{4.5}\sqrt{T}+d^{4}C)$ regret bound. It was shown in [9] that PE
with modified confidence intervals achieves an $\tilde{O}(d\sqrt{T}+d^{1.5}C)$
high probability regret bound for unknown corruption $C$. A model selection
based approach in [5] that uses PE as a subroutine is shown to generalize this
result for unknown $C$ without changing the regret bound except for $\log$
factors. By adapting the confidence intervals of PE to account for the known
$\epsilon_{m}$ misspecification the $\tilde{O}(d\sqrt{T}+d^{1.5}C)$ high
probability regret bound extends for a model with $O(\sqrt{d\log T/T})$
misspecification and known corruption $C$. We will modify the PE confidence
interval to be

$\gamma_{m}=8d\sqrt{\log(T)/t^{(m)}}+\frac{2C(4d\log\log
d+18)}{T_{m}}\sqrt{8d}.$ (32)

The model selection approach in [5] implies the following result.

######  Theorem 7.

For contextual linear bandits with unknown corruption that is bounded by $C$,
Algorithm 1 with $t^{(m)}=2^{m-1}$ and $\Lambda_{\epsilon_{m}}$ being G-COBE
in [5] with PE, that uses $\gamma_{m}$ in (32), as a subroutine, achieves

$R_{T}=\tilde{O}(d\sqrt{T}+d^{1.5}C)$ (33)

with probability at least $1-c/T$.

###### Proof.

The proof follows by proving a regret bound for PE with the chosen
$\gamma_{m}$ for known $C$. Then use the model selection result in [5] to
prove a regret bound for unknown $C$ and finally apply our main theorem to
bound the final regret.

We notice that

$\displaystyle|{\langle g^{(m)}(\theta),\hat{\theta}_{m}\rangle}-{\langle
g(\theta),\theta_{\star}\rangle}|\leq|{\langle
g^{(m)}(\theta),\hat{\theta}_{m}-\theta_{\star}\rangle}|+|{\langle
g^{(m)}(\theta)-g(\theta),\theta_{\star}\rangle}|.$ (34)

Using Lemma 1 in [9] and equation (26) to bound the first term and Proposition
2 to bound the second term, we obtain that $|{\langle
g^{(m)}(\theta),\hat{\theta}_{m}\rangle}-{\langle
g(\theta),\theta_{\star}\rangle}|\leq\gamma_{m}/2$ with probability at least
$1-c/T$. A standard calculation in Theorem 1 in [9] implies a regret bound of
$\tilde{O}(d\sqrt{T}+d^{1.5}C)$ with high probability. Hence, Theorem 4 in
[10] implies a regret bound of $\tilde{O}(d\sqrt{T}+d^{1.5}C)$ with high
probability for G-COBE with unknown $C$. Applying Theorem 2 and proceeding as
in equation (4.1) concludes the proof. ∎

###  4.5 Sparsity

For linear contextual bandits with $s$-sparse unknown parameter, our reduction
can be used to prove $O(\sqrt{dsT\log(T)})$ regret bound with high probability
as opposed to the best known $O(\sqrt{dsT}\log^{2}T)$ regret bound. It is not
hard to show that there is $1/T$ cover with size at most $(6T)^{2s+1}$ in that
case; also proved below for completeness. The following result directly
follows from Corollary 2.

######  Theorem 8.

For Algorithm 1 with $t^{(m)}=2^{m-1}$ and $\Lambda_{\epsilon_{m}}$ to be PE
with $\gamma_{m}=6\sqrt{2ds\log(T/\delta)/t^{(m)}}$ it holds that with
probability at least $1-c\delta$ we have that
$R_{T}=O(\sqrt{dsT\log(T/\delta)})$.

###### Proof.

By Corollary 2, we only need to show that $\Theta$ contains an $1/T$-net with
size at most $(6T)^{2s+1}$. We have that there is $1/2T$-net for
$\\{\phi\in\mathbb{R}^{s}|\|\phi\|_{2}\leq 1\\}$ with size at most $(6T)^{s}$.
To construct $s$-sparse vectors in $\mathbb{R}^{d}$, there is
$\sum_{i=1}^{s}{d\choose i}$ ways to choose the non-zero entries. This implies
that the set $\\{\theta\in\mathbb{R}^{d}|\|\theta\|_{2}\leq
1,\|\theta\|_{0}\leq s\\}$ has $1/2T$-net $\mathcal{N}$ of size at most

$|\mathcal{N}|\leq(6T)^{s}\sum_{i=1}^{s}{d\choose
i}\leq(6T)^{s}\sum_{i=1}^{s}d^{i}\leq(6T)^{s}d^{s+1}\leq(6T)^{2s+1}.$ (35)

We next construct an $1/T$-net that is subset of $\Theta$ (recall that this is
required for Theorem 2). For every $x\in\mathcal{N}$, let
$\mathcal{N}_{x}=\\{\theta\in\Theta|\|\theta-x\|\leq 1/2T\\}$. Let
$\alpha:\mathcal{N}\to|\mathcal{N}|$ be an ordering of the set $\mathcal{N}$.
And let $\mathcal{N}^{\prime}\subseteq\mathcal{N}$ be defined as
$\mathcal{N}^{\prime}=\\{x\in\mathcal{N}|\mathcal{N}_{x}\not\subseteq\cup_{y:\alpha(y)\leq\alpha(x)}\mathcal{N}_{y}\\}$.
Hence, $\\{\mathcal{N}_{x}|x\in\mathcal{N}^{\prime}\\}$ is a set of pairwise
disjoint sets. By the axiom of choice, there is a set
$\mathcal{N}^{\prime\prime}$ such that $\mathcal{N}^{\prime\prime}$ contains
exactly one element of each set $\mathcal{N}_{x}\forall
x\in\mathcal{N}^{\prime}$. By construction of $\mathcal{N}^{\prime\prime}$ we
have that $\mathcal{N}^{\prime\prime}\subseteq\Theta$.

We also have that for each $\theta\in\Theta$, there is $x\in\mathcal{N}$ with
$\|x-\theta\|_{2}\leq 1/2T$. Then for each $y\in\mathcal{N}_{x}$, we have by
the triangle inequality that $\|y-\theta\|_{2}\leq 1/T$. By the definition of
$\mathcal{N}^{\prime}$, we have that
$\cup\mathcal{N}^{\prime}=\cup_{z\in\mathcal{N}}\mathcal{N}_{z}$. Then, by
construction of $\mathcal{N}^{\prime\prime}$, there is
$z\in\mathcal{N}^{\prime\prime}$ such that $z\in\mathcal{N}_{x}$. Hence,
$\|z-\theta\|_{2}\leq 1/T$. This implies that
$\mathcal{N}^{\prime\prime}\subseteq\Theta$ is an $1/T$-net of $\Theta$. We
also have by construction that also that
$|\mathcal{N}^{\prime\prime}|\leq|\mathcal{N}|\leq(6T)^{2s+1}$. ∎

###  4.6 Structured Unknown Parameters

In some cases, the dimension $d$ can be large but the unknown parameter is
mapped from a small space of dimension $s$. In particular let
$f:\mathbb{R}^{s}\to\mathbb{R}^{d}$ be such that
$\Theta\subseteq\\{f(\phi)|\|\phi\|_{2}\leq 1\\}$ and

$\|f(\phi)-f(\phi^{\prime})\|_{2}\leq c\|\phi-\phi^{\prime}\|_{2},$ (36)

where $c$ is a universal constant. Finding an $1/T$-net for
$\Phi=\\{\phi|f(\phi)\in\Theta\\}$ implies a $c/T$-net for $\Theta$ with the
same size. Since $\Phi\subseteq\\{\phi\in\mathbb{R}^{s}|\|\phi\|_{2}\leq
1\\}$, we have that there is an $1/T$-net for $\Phi$ that is contained in
$\Phi$ with size at most $(6T)^{s}$. The following result immediately follows
from Corollary 2.

######  Corollary 3.

Under the considered structured unknown parameters assumption, Algorithm 1
with $t^{(m)}=2^{m-1}$ and $\Lambda_{\epsilon_{m}}$ to be PE with
$\gamma_{m}=6\sqrt{ds\log(T/\delta)/t^{(m)}}$ satisfies that with probability
at least $1-c\delta$ we have that $R_{T}=O(\sqrt{dsT\log(T/\delta)})$.

##  5 Conclusions

We presented a novel reduction from stochastic contextual linear bandit
problems to (fixed-context) linear bandit problems; our reduction explains why
results, that are not achievable for adversarial contexts, are possible for
stochastic contextual bandits, and offers a framework that can be leveraged to
gain improved understanding and bounds for contextual linear bandit problems.
We illustrate the power of our approach by applying it to achieve improved
bounds over a number of cases; this is not an exhaustive list, and we hope
that our approach will be a useful tool to researchers in this field.

## References

  * [1] Y. Li, Y. Wang, and Y. Zhou, “Nearly minimax-optimal regret for linearly parameterized bandits,” in _Conference on Learning Theory_. PMLR, 2019, pp. 2173–2174.
  * [2] Y. Li, Y. Wang, X. Chen, and Y. Zhou, “Tight regret bounds for infinite-armed linear contextual bandits,” in _International Conference on Artificial Intelligence and Statistics_. PMLR, 2021, pp. 370–378.
  * [3] Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári, “Improved algorithms for linear stochastic bandits,” _Advances in neural information processing systems_ , vol. 24, 2011.
  * [4] Y. Ruan, J. Yang, and Y. Zhou, “Linear bandits with limited adaptivity and learning distributional optimal design,” in _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ , 2021, pp. 74–87.
  * [5] D. J. Foster, C. Gentile, M. Mohri, and J. Zimmert, “Adapting to misspecification in contextual bandits,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 11 478–11 489, 2020.
  * [6] Y. Abbasi-Yadkori, D. Pal, and C. Szepesvari, “Online-to-confidence-set conversions and application to sparse stochastic bandits,” in _Artificial Intelligence and Statistics_. PMLR, 2012, pp. 1–9.
  * [7] T. Lattimore, C. Szepesvari, and G. Weisz, “Learning with good feature representations in bandits and in rl with a generative model,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 5662–5670.
  * [8] M. Valko, R. Munos, B. Kveton, and T. Kocák, “Spectral bandits for smooth graph functions,” in _International Conference on Machine Learning_. PMLR, 2014, pp. 46–54.
  * [9] I. Bogunovic, A. Losalka, A. Krause, and J. Scarlett, “Stochastic linear bandits robust to adversarial attacks,” in _International Conference on Artificial Intelligence and Statistics_. PMLR, 2021, pp. 991–999.
  * [10] C.-Y. Wei, C. Dann, and J. Zimmert, “A model selection approach for corruption robust reinforcement learning,” in _International Conference on Algorithmic Learning Theory_. PMLR, 2022, pp. 1043–1096.
  * [11] T. Lattimore and C. Szepesvári, _Bandit algorithms_. Cambridge University Press, 2020.
  * [12] Z. Gao, Y. Han, Z. Ren, and Z. Zhou, “Batched multi-armed bandits problem,” _Advances in Neural Information Processing Systems_ , vol. 32, 2019.
  * [13] V. Perchet, P. Rigollet, S. Chassang, and E. Snowberg, “Batched bandit problems,” _The Annals of Statistics_ , pp. 660–681, 2016.
  * [14] Y. Han, Z. Zhou, Z. Zhou, J. Blanchet, P. W. Glynn, and Y. Ye, “Sequential batch learning in finite-action linear contextual bandits,” _arXiv preprint arXiv:2004.06321_ , 2020.
  * [15] Z. Zhang, X. Ji, and Y. Zhou, “Almost optimal batch-regret tradeoff for batch linear contextual bandits,” _arXiv preprint arXiv:2110.08057_ , 2021.
  * [16] S. S. Du, S. M. Kakade, R. Wang, and L. F. Yang, “Is a good representation sufficient for sample efficient reinforcement learning?” _arXiv preprint arXiv:1910.03016_ , 2019.
  * [17] K. Crammer and C. Gentile, “Multiclass classification with bandit feedback using adaptive regularization,” _Machine learning_ , vol. 90, no. 3, pp. 347–383, 2013.
  * [18] A. Ghosh, S. R. Chowdhury, and A. Gopalan, “Misspecified linear bandits,” in _Thirty-First AAAI Conference on Artificial Intelligence_ , 2017.
  * [19] D. Foster and A. Rakhlin, “Beyond ucb: Optimal and efficient contextual bandits with regression oracles,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 3199–3210.
  * [20] A. Zanette, A. Lazaric, M. Kochenderfer, and E. Brunskill, “Learning near optimal policies with low inherent bellman error,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 10 978–10 989.
  * [21] A. Pacchiano, M. Phan, Y. Abbasi Yadkori, A. Rao, J. Zimmert, T. Lattimore, and C. Szepesvari, “Model selection in contextual stochastic bandit problems,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 10 328–10 337, 2020.
  * [22] T. Lykouris, M. Simchowitz, A. Slivkins, and W. Sun, “Corruption-robust exploration in episodic reinforcement learning,” in _Conference on Learning Theory_. PMLR, 2021, pp. 3242–3245.
  * [23] Y. Chen, S. Du, and K. Jamieson, “Improved corruption robust algorithms for episodic reinforcement learning,” in _International Conference on Machine Learning_. PMLR, 2021, pp. 1561–1570.
  * [24] T. Jin, L. Huang, and H. Luo, “The best of both worlds: stochastic and adversarial episodic mdps with unknown transition,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 20 491–20 502, 2021.
  * [25] Y. Li, E. Y. Lou, and L. Shan, “Stochastic linear optimization with adversarial corruption,” _arXiv preprint arXiv:1909.02109_ , 2019.
  * [26] I. Bogunovic, A. Krause, and J. Scarlett, “Corruption-tolerant gaussian process bandit optimization,” in _International Conference on Artificial Intelligence and Statistics_. PMLR, 2020, pp. 1071–1081.
  * [27] C.-W. Lee, H. Luo, C.-Y. Wei, M. Zhang, and X. Zhang, “Achieving near instance-optimality and minimax-optimality in stochastic and adversarial linear bandits simultaneously,” in _International Conference on Machine Learning_. PMLR, 2021, pp. 6142–6151.
  * [28] J. He, D. Zhou, T. Zhang, and Q. Gu, “Nearly optimal algorithms for linear contextual bandits with adversarial corruptions,” _arXiv preprint arXiv:2205.06811_ , 2022.
  * [29] H. Bastani and M. Bayati, “Online decision making with high-dimensional covariates,” _Operations Research_ , vol. 68, no. 1, pp. 276–294, 2020.
  * [30] T. Lattimore, K. Crammer, and C. Szepesvári, “Linear multi-resource allocation with semi-bandit feedback,” _Advances in Neural Information Processing Systems_ , vol. 28, 2015.
  * [31] S. Gerchinovitz, “Sparsity regret bounds for individual sequences in online linear regression,” in _Proceedings of the 24th Annual Conference on Learning Theory_. JMLR Workshop and Conference Proceedings, 2011, pp. 377–396.
  * [32] A. Carpentier and R. Munos, “Bandit theory meets compressed sensing for high dimensional stochastic linear bandit,” in _Artificial Intelligence and Statistics_. PMLR, 2012, pp. 190–198.
  * [33] Y. Chen, Y. Wang, E. X. Fang, Z. Wang, and R. Li, “Nearly dimension-independent sparse linear bandit over small action spaces via best subset selection,” _Journal of the American Statistical Association_ , no. just-accepted, pp. 1–31, 2022.
  * [34] Y. Dai, R. Wang, and S. S. Du, “Variance-aware sparse linear bandits,” _arXiv preprint arXiv:2205.13450_ , 2022.
  * [35] K. Jang, C. Zhang, and K.-S. Jun, “Popart: Efficient sparse regression and experimental design for optimal sparse linear bandits,” _arXiv preprint arXiv:2210.15345_ , 2022.
  * [36] B. Hao, T. Lattimore, and W. Deng, “Information directed sampling for sparse linear bandits,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 16 738–16 750, 2021.
  * [37] B. Hao, T. Lattimore, and M. Wang, “High-dimensional sparse linear bandits,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 10 753–10 763, 2020.
  * [38] M. J. Wainwright, _High-dimensional statistics: A non-asymptotic viewpoint_. Cambridge University Press, 2019, vol. 48.

Appendices

##  Appendix A Proof of Theorem 1

######  Theorem (Restatement of Theorem 1).

Let $\Lambda$ be any algorithm for linear bandits and $I$ be a contextual
linear bandit instance with stochastic contexts, unknown parameter
$\theta_{\star}$ and rewards $r_{t}$ generated as described in the reduction
in Section 3.1. It holds that
$\bullet$ The reward $r_{t}$ is generated, by pulling the arm $g(\theta_{t})$,
from a linear bandit instance $L$ with action set $\mathcal{X}$, and unknown
parameter $\theta_{\star}$.
$\bullet$ The reduction results in an algorithm $\mathcal{M}$ for contextual
linear bandits such that with probability at least $1-\delta$ we have

$|R_{T}^{\mathcal{M}}(I)-R_{T}^{\Lambda}(L)|\leq c\sqrt{T\log(1/\delta)},$
(37)

where $R^{\Lambda}_{T}(L)$ is the regret of $\Lambda$ over the constructed
linear bandit instance $L$, $R_{T}^{\mathcal{M}}(I)$ is the regret of
algorithm $\mathcal{M}$ over the instance $I$ and $c$ is a universal constant.

###### Proof.

Following the reduction described in the section, we start by showing that
$R_{T}^{\Lambda}(L)$, the regret of the algorithm $\Lambda$ on a linear bandit
instance, is at most $\tilde{O}(\sqrt{T})$ away from $R_{T}^{\mathcal{M}}(I)$
with high probability. Recall that the regret $R_{T}^{\Lambda}(L)$ is defined
as

$R_{T}^{\Lambda}(L)=\sum_{t=1}^{T}\max_{\theta\in\Theta}{\langle
g(\theta),\theta_{\star}\rangle}-{\langle
g(\theta_{t}),\theta_{\star}\rangle}.$ (38)

We notice that the function $g$ depends on the context distribution
$\mathcal{D}$. In the following we assume for simplicity that for each
$\theta\in\Theta$, there is a unique $a_{t}\in\mathcal{A}_{t}$ that satisfies
${\langle a_{t},\theta\rangle}=\sup_{a\in\mathcal{A}_{t}}{\langle
a,\theta\rangle}$ almost surely. We discuss how to remove this assumption at
the end of the proof.

The regret $R_{T}^{\mathcal{M}}(I)$ of the contextual algorithm can be
decomposed as

$\displaystyle R_{T}^{\mathcal{M}}(I)$
$\displaystyle=\sum_{t=1}^{T}{\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{\star}\rangle},\theta_{\star}\rangle}-{\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{t}\rangle},\theta_{\star}\rangle}$
$\displaystyle=\sum_{t=1}^{T}{\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{\star}\rangle},\theta_{\star}\rangle}-{\langle\mathbb{E}[\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{\star}\rangle}],\theta_{\star}\rangle}$
$\displaystyle\qquad+{\langle\mathbb{E}[\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{t}\rangle}|\theta_{t}],\theta_{\star}\rangle}-{\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{t}\rangle},\theta_{\star}\rangle}$
$\displaystyle\qquad+{\langle\mathbb{E}[\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{\star}\rangle}],\theta_{\star}\rangle}-{\langle\mathbb{E}[\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{t}\rangle}|\theta_{t}],\theta_{\star}\rangle}$
$\displaystyle=\sum_{t=1}^{T}{\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{\star}\rangle},\theta_{\star}\rangle}-\mathbb{E}[{\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{\star}\rangle},\theta_{\star}\rangle}]$
$\displaystyle\qquad+\mathbb{E}[{\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{t}\rangle},\theta_{\star}\rangle}|\theta_{t}]-{\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{t}\rangle},\theta_{\star}\rangle}$ $\displaystyle\qquad+{\langle
g(\theta_{\star}),\theta_{\star}\rangle}-{\langle
g(\theta_{t}),\theta_{\star}\rangle},$ (39)

where the expectation is with respect to the randomness in the context
generation $\mathcal{A}_{t}$. In the following we will first show that
${\langle
g(\theta_{\star}),\theta_{\star}\rangle}=\max_{\theta\in\Theta^{\prime}}{\langle
g(\theta),\theta_{\star}\rangle}$.

Indeed,we observe that $\forall\theta^{\prime},\theta^{\prime\prime}\in\Theta$
we have

$\displaystyle\max_{\theta\in\Theta}{\langle
g(\theta),\theta^{\prime}\rangle}\geq{\langle
g(\theta^{\prime}),\theta^{\prime}\rangle}$
$\displaystyle=\mathbb{E}[\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta^{\prime}\rangle}]$
$\displaystyle\geq\mathbb{E}[{\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta^{\prime\prime}\rangle},\theta^{\prime}\rangle}]={\langle
g(\theta^{\prime\prime}),\theta^{\prime}\rangle}.$ (40)

The above inequalities have to be met with equality since we can select
$\theta^{\prime\prime}=\arg\max_{\theta\in\Theta}{\langle
g(\theta),\theta^{\prime}\rangle}$ making the first and last terms equal.
Hence, we have proved that

${\langle
g(\theta^{\prime}),\theta^{\prime}\rangle}=\max_{\theta\in\Theta}{\langle
g(\theta),\theta^{\prime}\rangle},\quad\forall\;\theta^{\prime}\in\Theta.$
(41)

Substituting in the last line of (A) using the triangle inequality, we get
that

$\displaystyle|R_{T}^{\mathcal{M}}(I)-R_{T}^{\Lambda}(L)|$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{=}}|\sum_{t=1}^{T}{\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{\star}\rangle},\theta_{\star}\rangle}-\mathbb{E}[{\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{\star}\rangle},\theta_{\star}\rangle}]$
$\displaystyle\qquad+\mathbb{E}[{\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{t}\rangle},\theta_{\star}\rangle}|\theta_{t}]-{\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{t}\rangle},\theta_{\star}\rangle}|$
$\displaystyle\leq|\sum_{t=1}^{T}{\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{\star}\rangle},\theta_{\star}\rangle}-\mathbb{E}[{\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{\star}\rangle},\theta_{\star}\rangle}]|$
$\displaystyle\qquad+|\sum_{t=1}^{T}\mathbb{E}[{\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{t}\rangle},\theta_{\star}\rangle}|\theta_{t}]-{\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{t}\rangle},\theta_{\star}\rangle}|,$ (42)

where $(i)$ follows by definition of $R_{T}^{\Lambda}(L)$ and (41).

We next bound the quantity

$\Sigma_{T}:=\sum_{t=1}^{T}\mathbb{E}[{\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{t}\rangle},\theta_{\star}\rangle}|\theta_{t}]-{\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{t}\rangle},\theta_{\star}\rangle}.$ (43)

Let $\mathcal{F}^{\prime}_{t}=\sigma\\{\theta_{1},r_{1},...,\theta_{t}\\}$ be
the filtration of all historic information of the linear bandit problem up to
time $t$. we notice that

$\displaystyle\mathbb{E}[\Sigma_{t}|\mathcal{F}^{\prime}_{t}]$
$\displaystyle=\mathbb{E}[\Sigma_{t-1}|\mathcal{F}^{\prime}_{t}]+\mathbb{E}[\mathbb{E}[{\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{t}\rangle},\theta_{\star}\rangle}|\theta_{t}]|\mathcal{H}^{\prime}_{t}]-\mathbb{E}[{\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{t}\rangle},\theta_{\star}\rangle}|\mathcal{F}^{\prime}_{t}]$
$\displaystyle=\Sigma_{t-1}.$ (44)

Hence, $\Sigma_{t}$ is a martingale with a bounded difference (by boundedness
of $\Theta,\mathcal{A}_{t}$). By Azuma–Hoeffding inequality [38], we have that
$|\Sigma_{T}|\leq c\sqrt{T\log 1/\delta}$ with probability at least
$1-\frac{1}{2\delta}$. For completeness, we state a special case of the Azuma-
Hoeffding inequality at the end of our proof. The summation
$\Sigma^{\prime}_{T}=\sum_{t=1}^{T}{\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{\star}\rangle},\theta_{\star}\rangle}-\mathbb{E}[{\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta_{\star}\rangle},\theta_{\star}\rangle}]$ can be bounded similarly.
Hence, by (A), we have that with probability at least $1-\delta$

$|R_{T}^{\mathcal{M}}(I)-R_{T}^{\Lambda}(L)|\leq c\sqrt{T\log 1/\delta}.$ (45)

We have shown that the regret of Algorithm 1 over the instance $I$ is
$O(\sqrt{T\log 1/\delta})$ away from $R_{T}^{\Lambda}(L)$ with probability at
least $1-\delta$. It remains to show that the rewards $r_{t}$ generated by the
described interaction with the instance $I$, are generated from $L$ by the
interaction of algorithm $\Lambda$.

######  Proposition 1.

The reward $r_{t}$ can be rewritten as

$r_{t}={\langle g(\theta_{t}),\theta_{\star}\rangle}+\eta^{\prime}_{t},$ (46)

where
$\mathbb{E}[\eta^{\prime}_{t}|\mathcal{F}^{\prime}_{t}]=0,\mathbb{E}[\exp(\lambda\eta^{\prime}_{t})|\mathcal{F}^{\prime}_{t}]\leq\exp(2\lambda^{2})\quad\forall\lambda\in\mathbb{R}$,
and where
$\mathcal{F}^{\prime}_{t}=\sigma\\{\theta_{1},r_{1},...,\theta_{t}\\}$ is the
filtration of historic information up to time $t$.

###### Proof.

We have that

$\displaystyle r_{t}$ $\displaystyle={\langle
a_{t},\theta_{\star}\rangle}+\eta_{t}={\langle\arg\max_{b\in\mathcal{A}_{t}}{\langle
b,\theta_{t}\rangle},\theta_{\star}\rangle}+\eta_{t}$ $\displaystyle={\langle
g(\theta_{t}),\theta_{\star}\rangle}+\left(\eta_{t}+{\langle\arg\max_{b\in\mathcal{A}_{t}}{\langle
b,\theta_{t}\rangle},\theta_{\star}\rangle}-{\langle
g(\theta_{t}),\theta_{\star}\rangle}\right).$ (47)

We let
$\eta^{\prime}_{t}=\eta_{t}+{\langle\arg\max_{b\in\mathcal{A}_{t}}{\langle
b,\theta_{t}\rangle},\theta_{\star}\rangle}-{\langle
g(\theta_{t}),\theta_{\star}\rangle}$. The proof that
$\mathbb{E}[\eta^{\prime}_{t}|\mathcal{F}_{t}]=0$ follows similarly to (A)

$\displaystyle\mathbb{E}[\eta_{t}^{\prime}|\mathcal{F}_{t}]$
$\displaystyle=\mathbb{E}[\eta_{t}|\mathcal{F}_{t}]+\mathbb{E}[{\langle\arg\max_{b\in\mathcal{A}_{t}}{\langle
b,\theta_{t}\rangle},\theta_{\star}\rangle}-{\langle
g(\theta_{t}),\theta_{\star}\rangle}|\mathcal{F}_{t}]$
$\displaystyle=\mathbb{E}[{\langle\arg\max_{b\in\mathcal{A}_{t}}{\langle
b,\theta_{t}\rangle},\theta_{\star}\rangle}-{\langle
g(\theta_{t}),\theta_{\star}\rangle}|\theta_{t}]=0.$ (48)

Lastly,
$\mathbb{E}[\exp(\lambda\eta^{\prime}_{t})|\mathcal{F}_{t}]\leq\exp(2\lambda^{2})\forall\lambda\in\mathbb{R}$
follows by boundedness of $\eta^{\prime}_{t}$ which follows by boundedness of
$\eta_{t},\Theta,\mathcal{A}_{t}$. ∎

This concludes the proof.

######  Lemma 1.

[Azuma’s Inequality [38]] Let $\Sigma_{0},\Sigma_{1},...$ be a martingale with
respect to filtration $\mathcal{F}_{0},\mathcal{F}_{1},...$ such that
$|\Sigma_{i}-\Sigma_{i-1}|\leq c$ almost surely. Then for all $\epsilon>0$, we
have that

$\mathbb{P}[|\Sigma_{n}-\Sigma_{0}|>\epsilon]\leq
2\exp(-\frac{\epsilon^{2}}{2nc^{2}}).$ (49)

∎

###  A.1 When $\sup_{a\in\mathcal{A}_{t}}{\langle a,\theta\rangle}$ is not
Unique

One solution is to choose $a_{t}$ as any action ${\langle
a_{t},\theta\rangle}\geq\sup_{a\in\mathcal{A}_{t}}{\langle
a,\theta\rangle}-\delta$ for some $\delta>0$. The error arising from
performing this step can be controlled by $\delta$, e.g., by setting
$\delta=\exp(-T)$. Our proofs will follow by choosing $a_{t}$ as described
above, using any deterministic or random choice function, as long as the
action $a_{t}$ is measurable.

##  Appendix B Proof of Theorem 2

######  Theorem (Restatement of Theorem 2).

Let $\Lambda_{\epsilon}$ be an algorithm for linear bandits with $\epsilon$
misspecification and $I$ be a contextual linear bandit instance with
stochastic contexts, unknown parameter $\theta_{\star}$ and rewards $r_{t}$
are generated as described in Algorithm 1. The following holds:
$\bullet$ Conditioned on
$\mathcal{H}_{t^{(m)}}=\sigma(\mathcal{A}_{1},a_{1},r_{1},...,\mathcal{A}_{t^{(m)}},a_{t^{(m)}},r_{t^{(m)}})$:
in epoch $m$, the rewards $r_{t}$ are generated, by pulling arm
$g^{(m)}(\theta_{t})$, from a misspecified linear bandit instance $L_{m}$ for
$t=t^{(m)}+1,...,t^{(m+1)}$, action set
$\mathcal{X}_{m}=\\{g^{(m)}(\theta)|\theta\in\Theta^{\prime}\\}$, unknown
parameter $\theta_{\star}$, mean rewards ${\langle
g(\theta),\theta_{\star}\rangle}$, and unknown misspecification
$\epsilon^{\prime}_{m}$.
$\bullet$ The misspecification $\epsilon^{\prime}_{m}$ is bounded by the known
quantity $\epsilon_{m}$ with probability at least $1-c\delta/M$.
$\bullet$ With probability at least $1-\delta$ we have that
$|R_{T}(I)-\sum_{m=1}^{M}R^{\Lambda_{\epsilon_{m}}}_{T_{m}}(L_{m})|\leq
c\sqrt{T\log(1/\delta)}$, where $R_{T}(I)$ is the regret of Algorithm 1 over
the instance $I$, $R^{\Lambda_{\epsilon_{m}}}_{T_{m}}(L_{m})$ is the regret of
algorithm $\Lambda_{\epsilon_{m}}$ over the bandit instance $L_{m}$ in phase
$m$, $T_{m}=t^{(m+1)}-t^{(m)}$, and $c$ is a universal constant.

###### Proof.

Let $L_{m}$ be a bandit instance with actions $\mathcal{X}_{m}={\langle
g^{(m)}(\theta)|\theta\in\Theta^{\prime}\rangle}$ indexed by the set
$\Theta^{\prime}$, mean rewards ${\langle
g(\theta),\theta_{\star}\rangle}\forall\theta\in\Theta^{\prime}$, and
$t\in\\{t^{(m)}+1,...,t^{(m+1)}\\}$. Let

$\mathcal{H}_{t^{(m)}}=\sigma\\{\mathcal{A}_{1},a_{1},r_{1},...,\mathcal{A}_{t^{(m)}},a_{t^{(m)}},r_{t^{(m)}}\\}$

be the filtration of all historic information before epoch $m$. Note that
$g^{(m)}$ is defined in line $7$ of Algorithm 1 and is the empirical estimate
of $g$ using history $\mathcal{H}_{t^{(m)}}$, hence, $g^{(m)}$ is
$\mathcal{H}_{t^{(m)}}$-predictable. Conditioned on $\mathcal{H}_{t^{(m)}}$,
we have that $L_{m}$ is a misspecified linear bandit instance with
misspecification,
$\epsilon_{m}^{\prime}=\sup_{\theta\in\Theta^{\prime}}{\langle
g(\theta)-g^{(m)}(\theta),\theta_{\star}\rangle}$. And the regret of the
algorithm $\Lambda_{\epsilon_{m}}$ over $L_{m}$ is the random quantity

$R^{\Lambda_{\epsilon_{m}}}_{T_{m}}(L_{m}):=\sum_{t=t^{(m)}+1}^{t^{(m+1)}}{\langle
g(\theta),\theta_{\star}\rangle}-{\langle
g(\theta_{t}),\theta_{\star}\rangle}.$

As we have shown in Proposition 1, conditioned on $\mathcal{H}_{t^{(m)}}$,
$r_{t}$ is generated from $L_{m}$ by pulling arm $\theta_{t}$. Define the
event $\mathcal{E}_{m}=\\{\epsilon^{\prime}_{m}>\epsilon_{m}\\}$ be the bad
event that the random quantity $\epsilon^{\prime}_{m}$ is greater than
$\epsilon_{m}$ defined in Algorithm 1. We will show in Proposition 2 that
$\sum_{m=1}^{M}\mathbb{P}[\mathcal{E}_{m}]\leq\delta$.

We next bound the regret of Algorithm 1 in terms of the random quantities
$\\{R^{\Lambda_{\epsilon_{m}}}_{T_{m}}(L_{m})\\}_{m=1}^{M}$. By choosing
$\delta$ sufficiently small, it it will be enough to bound
$R^{\Lambda_{\epsilon_{m}}}_{T_{m}}(L_{m})$ conditioned on
$\mathcal{H}_{t^{(m)}}$ and the good event
$\mathcal{G}_{m}=\\{\epsilon^{\prime}_{m}\leq\epsilon_{m}\\}$. Let us define
the random quantity
$R^{\Lambda_{\epsilon}}_{T}(L_{\epsilon})=\sum_{m=1}^{M}R^{\Lambda_{\epsilon_{m}}}_{T_{m}}(L_{m})$.
We show that $R^{\Lambda_{\epsilon}}_{T}(L_{\epsilon})$ is at most
$\tilde{O}(\sqrt{T})$ away from $R_{T}^{\mathcal{M}}$ with high probability.
By definition of $R^{\Lambda_{\epsilon_{m}}}_{T_{m}}(L_{m})$ we have that

$R^{\Lambda_{\epsilon}}_{T}(L_{\epsilon})=\sum_{t=1}^{T}\max_{\theta\in\Theta^{\prime}}{\langle
g(\theta),\theta_{\star}\rangle}-{\langle
g(\theta_{t}),\theta_{\star}\rangle}.$ (50)

As in the proof of Theorem 1, we assume for simplicity that for each
$\theta\in\Theta$, there is a unique $a_{t}\in\mathcal{A}_{t}$ that satisfies
${\langle a_{t},\theta\rangle}=\sup_{a\in\mathcal{A}_{t}}{\langle
a,\theta\rangle}$ almost surely. This can be relaxed in the same way as in
Theorem 1.

Recall that $L$ is the linear bandit instance in Theorem 1 with access to the
function $g$, and actions in $\mathcal{X}=\\{g(\theta)|\theta\in\Theta\\}$.
The regret $R^{\mathcal{M}}_{T}(I)$ of the contextual algorithm can be bounded
as

$\displaystyle R_{T}^{\mathcal{M}}(I)$
$\displaystyle\leq|R_{T}^{\mathcal{M}}(I)-R_{T}^{\Lambda}(L)|+|R_{T}^{\Lambda}(L)-R^{\Lambda_{\epsilon}}_{T}(L_{\epsilon})|,$
(51)

where $R_{T}^{\Lambda}(L)$ is defined as follows

$R_{T}^{\Lambda}(L)=\sum_{t=1}^{T}\max_{\theta\in\Theta}{\langle
g(\theta),\theta_{\star}\rangle}-{\langle
g(\theta_{t}),\theta_{\star}\rangle},$

and $\\{\theta_{t}\\}$ are the actions played by
$\\{\Lambda_{\epsilon_{m}}\\}$. The first term in (51) is bounded in Theorem
1. In the following, we focus on bounding
$|R_{T}^{\Lambda}(L)-R^{\Lambda_{\epsilon}}_{T}(L_{\epsilon})|$. To that end,
we first show that

$|{\langle
g(\theta_{\star}),\theta_{\star}\rangle}-\max_{\theta\in\Theta^{\prime}}{\langle
g(\theta),\theta_{\star}\rangle}|\leq 2/T.$ (52)

We recall from (41) that

${\langle
g(\theta^{\prime}),\theta^{\prime}\rangle}=\max_{\theta\in\Theta}{\langle
g(\theta),\theta^{\prime}\rangle},\quad\forall\;\theta^{\prime}\in\Theta.$
(53)

From $1/T$-net properties, we also have that there exists
$\phi\in\Theta^{\prime}$ such that $\|\theta_{\star}-\phi\|_{2}\leq 1/T$.
Hence,

$\displaystyle\max_{\theta\in\Theta^{\prime}}{\langle
g(\theta),\theta_{\star}\rangle}$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{\leq}}\max_{\theta\in\Theta}{\langle
g(\theta),\theta_{\star}\rangle}\stackrel{{\scriptstyle(ii)}}{{=}}{\langle
g(\theta_{\star}),\theta_{\star}\rangle}$
$\displaystyle\stackrel{{\scriptstyle(iii)}}{{\leq}}{\langle
g(\theta_{\star}),\phi\rangle}+1/T$
$\displaystyle\leq\max_{\theta\in\Theta}{\langle g(\theta),\phi\rangle}+1/T$
$\displaystyle\stackrel{{\scriptstyle(iv)}}{{=}}{\langle
g(\phi),\phi\rangle}+1/T\stackrel{{\scriptstyle(v)}}{{\leq}}{\langle
g(\phi),\theta_{\star}\rangle}+2/T$
$\displaystyle\stackrel{{\scriptstyle(vi)}}{{\leq}}\max_{\theta\in\Theta^{\prime}}{\langle
g(\theta),\theta_{\star}\rangle}+2/T,$ (54)

where $(i)$ follows from $\Theta^{\prime}\subseteq\Theta$, $(ii)$ follows from
(41), $(iii)$ follows from ${\langle
g(\theta_{\star}),\theta_{\star}-\phi\rangle}\leq\|g(\theta_{\star})\|_{2}\|\theta_{\star}-\phi\|_{2}\leq
1/T$, $(iv)$ follows from (41), $(v)$ follows as in $(iii)$, and $(vi)$
follows from $\phi\in\Theta^{\prime}$. Eq. (52) follows. Note that in this
part it is important to have $\Theta^{\prime}\subseteq\Theta$.

As a result $|R_{T}^{\Lambda}(L)-R^{\Lambda_{\epsilon}}_{T}(L_{\epsilon})|$
can be bounded as

$\displaystyle|R_{T}^{\Lambda}(L)-R^{\Lambda_{\epsilon}}_{T}(L_{\epsilon})|$
$\displaystyle=|\sum_{t=1}^{T}\max_{\theta\in\Theta^{\prime}}{\langle
g(\theta),\theta_{\star}\rangle}-\max_{\theta\in\Theta}{\langle
g(\theta),\theta_{\star}\rangle}|$
$\displaystyle\leq\sum_{t=1}^{T}|\max_{\theta\in\Theta^{\prime}}{\langle
g(\theta),\theta_{\star}\rangle}-\max_{\theta\in\Theta}{\langle
g(\theta),\theta_{\star}\rangle}|\stackrel{{\scriptstyle(i)}}{{\leq}}2,$ (55)

where $(i)$ follows uses (52) and (41).

Hence, by (51), Theorem 1, (B) and union bound, we have that with probability
at least $1-\delta$

$|R^{\mathcal{M}}_{T}(I)-R^{\Lambda_{\epsilon}}_{T}(L_{\epsilon})|\leq
c\sqrt{T\log 1/\delta}.$ (56)

Since
$R^{\Lambda_{\epsilon}}_{T}(L_{\epsilon})=\sum_{m=1}^{M}R^{\Lambda_{\epsilon_{m}}}_{T_{m}}(L_{m})$,
we have proved the second part of the theorem. It remains to show that in each
epoch $m$ the rewards $r_{t}$ are generated from the for linear bandit
instance $L_{m}$ and to bound the amount of misspecification. By Proposition
1, it suffices to show the following.

######  Proposition 2.

For each $m\in[M]$, we have that with probability at least $1-\delta/M$ it
holds that

$|{\langle g(\theta),\theta^{\prime}\rangle}-{\langle
g^{(m)}(\theta),\theta^{\prime}\rangle}|\leq
2\sqrt{\frac{\log(2M|\Theta^{\prime}|/\delta)}{t^{(m)}}}\forall\theta\in\Theta^{\prime},\theta^{\prime}\in\Theta.$
(57)

###### Proof.

Since for a fixed $\theta^{\prime}$ we have that
${\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta\rangle},\theta^{\prime}\rangle}$ is $1/4$-subgaussian with mean
${\langle g(\theta),\theta^{\prime}\rangle}$, we have that with probability at
least $1-\frac{\delta}{M|\Theta^{\prime}|^{2}}$ it holds that

$\displaystyle|{\langle g(\theta),\theta^{\prime}\rangle}-{\langle
g^{(m)}(\theta),\theta^{\prime}\rangle}|$ $\displaystyle=|{\langle
g(\theta),\theta^{\prime}\rangle}-\frac{1}{t^{(m+1)}}\sum_{t=1}^{t^{(m+1)}}{\langle\arg\max_{a\in\mathcal{A}_{t}}{\langle
a,\theta\rangle},\theta^{\prime}\rangle}|$ $\displaystyle\leq
2\sqrt{\frac{\log(2M|\Theta^{\prime}|/\delta)}{t^{(m)}}}.$ (58)

By the union bound, the following holds with probability at least $1-\delta/M$

$|{\langle g(\theta),\theta^{\prime}\rangle}-{\langle
g^{(m)}(\theta),\theta^{\prime}\rangle}|\leq
2\sqrt{\frac{\log(2M|\Theta^{\prime}|/\delta)}{t^{(m)}}}\forall\theta,\theta^{\prime}\in\Theta^{\prime}.$
(59)

Let us pick arbitrary $\theta\in\Theta^{\prime},\theta^{\prime}\in\Theta$. We
have that there is $\phi^{\prime}\in\Theta^{\prime}$ such that
$\|\theta^{\prime}-\phi^{\prime}\|_{2}\leq 1/T$. Hence, by Cauchy-Schwartz and
the triangle inequality, we have that the following holds with probability at
least $1-\delta/M$

$|{\langle g(\theta),\theta^{\prime}\rangle}-{\langle
g^{(m)}(\theta),\theta^{\prime}\rangle}|\leq|{\langle
g(\theta),\phi^{\prime}\rangle}-{\langle
g^{(m)}(\theta),\phi^{\prime}\rangle}|+\frac{2}{T}\leq
2\sqrt{\frac{\log(2M|\Theta^{\prime}|/\delta)}{t^{(m)}}}+\frac{2}{T}\forall\theta\in\Theta^{\prime},\theta^{\prime}\in\Theta.$
(60)

∎

This concludes the proof. ∎