# Online learning in bandits with predicted context

Yongyi Guo Department of Statistics, Harvard University, Cambridge, MA, 02138.
Email<EMAIL_ADDRESS>Susan Murphy Department of Statistics,
Harvard University, Cambridge, MA, 02138. Email<EMAIL_ADDRESS>
###### Abstract

We consider the contextual bandit problem where at each time, the agent only
has access to a noisy version of the context and the error variance (or an
estimator of this variance). This setting is motivated by a wide range of
applications where the true context for decision-making is unobserved, and
only a prediction of the context by a potentially complex machine learning
algorithm is available. When the context error is non-diminishing, classical
bandit algorithms fail to achieve sublinear regret. We propose the first
online algorithm in this setting with sublinear regret compared to the
appropriate benchmark. The key idea is to extend the measurement error model
in classical statistics to the online decision-making setting, which is
nontrivial due to the policy being dependent on the noisy context
observations.

##  1 Introduction

Contextual bandits (Auer, 2002; Langford and Zhang, 2007) represent a
classical sequential decision-making problem where an agent aims to maximize
cumulative reward based on context information. At each round $t$, the agent
observes a context and must choose one of $K$ available actions based on both
the current context and previous observations. Once the agent selects an
action, she observes the associated reward, which is then used to refine
future decision-making. The contextual bandit problem is a typical example of
reinforcement learning where balancing the exploration of new actions with the
exploitation of previously acquired information is necessary to achieve
optimal long-term rewards. It also has numerous real-world applications
including personalized recommendation systems (Li et al., 2010; Bouneffouf et
al., 2012), healthcare (Yom-Tov et al., 2017; Liao et al., 2020), and online
education (Liu et al., 2014; Shaikh et al., 2019).

Despite the extensive existing literature on contextual bandits, in many real-
world applications, the agent never observes the context _exactly_. One common
reason is that the true context for decision-making can only be detected or
learned approximately from observable auxiliary data. For instance, consider
the Sense2Stop mobile health study, in which the context is whether the
individual is currently physiologically stressed (Battalio et al., 2021). A
complex predictor of current stress was constructed/validated based on
multiple prior studies (Cohen et al., 1985; Sarker et al., 2016, 2017). This
predictor was then tuned to each user in Sense2Stop prior to their quit-smoke
attempt and then following the user’s attempt to quit smoking, at each minute,
the predictor input high-dimensional sensor data on the user and output a
continuous likelihood of stress for use by the decision-making algorithm.
Similarly, in online advertising, the context might be the measure of how
likely a user is to buy an item, which cannot be observed. The second reason
why the context is not observed exactly is because of measurement error. Noisy
measurement of variables is ubiquitous in practice, which introduces an
additional level of uncertainty that must be accounted for when making
decisions.

Motivated by the above, we consider the linear contextual bandit problem where
at each round, the agent only has access to a noisy observation of the true
context. Moreover, the agent has limited knowledge about the underlying
distribution of this noisy observation, as in many practical applications
(e.g. the above-mentioned ones). This is especially the case when this
‘observation’ is the output of a complex machine learning algorithm. We only
assume that the noisy observation is unbiased, its covariance is known or can
be estimated, and we put no other essential restrictions to its distribution.
This setting is intrinsically difficult for two main reasons: First, when
estimating the reward model, the agent needs to take into account the
misalignment between the noisy context observation and the reward which
depends on the true context. Second, even if the reward model is known, the
agent suffers from making bad decisions because of inaccurate context
information at each round.

Our contributions. We present the first online algorithm MEB (Measurement
Error Bandit) with sublinear regret in this setting, with a specific
discussion on the choice of appropriate benchmarks. MEB achieves
$\mathcal{O}(T^{2/3})$ regret compare to a standard benchmark and
$\mathcal{O}(T^{1/2})$ regret compare to a clipped benchmark with minimum
exploration probability which is common in many applications (Yang et al.,
2020a; Yao et al., 2021). MEB is based on a novel approach to model estimation
which is able to remove the systematic bias caused by the noisy context
observation. The estimator is inspired by the measurement error literature in
statistics (Carroll et al., 1995; Fuller, 2009): We extend this classical
method with additional tools in the online decision-making setting due to the
policy being dependent on the measurement error.

###  1.1 Related work

Our work complements several lines of literature in contextual bandits, as
listed below.

Latent contextual bandit. In the latent contextual bandit literature (Zhou and
Brunskill, 2016; Sen et al., 2017; Hong et al., 2020a, b; Xu et al., 2021;
Nelson et al., 2022; Galozy and Nowaczyk, 2023), the reward is typically
modeled as jointly depending on the latent state, the context, and the action.
Several works (Zhou and Brunskill, 2016; Hong et al., 2020a, b; Galozy and
Nowaczyk, 2023) assume no direct relations between the latent state and the
context while setting a parametric reward model. (Hong et al., 2020a) assumes
the latent state $s\in{\mathcal{S}}_{l}$ is unknown but constant over time and
provides an algorithm with regret
$\widetilde{\mathcal{O}}(\sqrt{T|{\mathcal{S}}_{l}|})$ when the reward model
is known. (Hong et al., 2020b; Galozy and Nowaczyk, 2023) assume that the
latent state evolves through a Markov chain
$\mathbb{P}_{\phi^{*}}(\cdot|\cdot)$ and propose algorithms with regret
$\mathcal{O}(T^{2/3}\sqrt{|{\mathcal{S}}_{l}|(1+pT)})$. Here
$p=1-\min_{s\in{\mathcal{S}}}\mathbb{P}_{\phi^{*}}(s|s)$. (Zhou and Brunskill,
2016) considers a sequence of contextual bandits, each with one of $N$ latent
states drawn from a distribution. (Xu et al., 2021) sets a specific context as
well as the latent feature for each action, and models the reward depending on
them through a generalized linear model. Different from the aforementioned
studies, we specify that the observed context is a noisy version of the latent
context (which aligns with many applications), and then leverage this
structure to design the online algorithm.

In another line of work, (Sen et al., 2017; Nelson et al., 2022) consider
contextual bandit with latent confounder instead of latent state in the sense
that the observed context influences the reward only through a latent
confounder variable, which ranges within a small discrete set. In (Sen et al.,
2017), the authors apply a matrix-factorization approach; While in (Nelson et
al., 2022), the authors assume additionally that the latent confounder evolves
through a Markov process, and the observed context depends on it through a
parametric model. Under some conditions, the problem can be transformed into a
linear contextual bandit. Our setting is distinct from these works in that the
latent context can span an infinite (or even continuous) space, which is not
of small cardinality.

Bandit with noisy context. In bandit with noisy context (Yun et al., 2017;
Kirschner and Krause, 2019; Yang et al., 2020b; Lin and Moothedath, 2022; Lin
et al., 2022), the agent has access to a noisy version of the true context
and/or some knowledge of the distribution of the noisy observation. (Yun et
al., 2017) considers the setting where for each time $t$ and action $a$, the
true context $z_{a,t}$ is i.i.d. normal. The agent only observes each entry of
$z_{a,t}+\epsilon_{a,t}$ with probability $p$, where the error
$\epsilon_{a,t}$ is multivariate normal with mean 0. The authors develop
algorithms with regret
$\widetilde{\mathcal{O}}(d\sqrt{T}+d^{2}\sqrt{T/p^{3}})$ compared to the
Bayesian oracle strategy. Other works such as (Kirschner and Krause, 2019;
Yang et al., 2020b; Lin et al., 2022) assume that the agent knows the full
distribution of the context each time, and observes no context. By assuming a
linear reward model, (Kirschner and Krause, 2019) transforms the problem into
a linear contextual bandit, and obtains $\widetilde{\mathcal{O}}(d\sqrt{T})$
regret compared to the policy maximizing the expected reward over the context
distribution. (Yang et al., 2020b; Lin et al., 2022) consider variants of the
problem such as multiple linear feedbacks, multiple agents, and additional
constraints. (Lin and Moothedath, 2022) considers another variant where $M$
collaborating agents know the full distribution of context each time and
observe the exact context after some delay. Compare to these works, we
consider a related but more challenging setting where besides an unbiased
noisy observation(prediction) for each context, the agent only knows the
second-moment information about the distribution. This does not transform into
a standard linear contextual bandit as (Kirschner and Krause, 2019).

Bandit with inaccurate/corrupted context. There are also a number of works
considering the setting where the context is simply inaccurate (without
randomness), or is corrupted and cannot be recovered. In (Yang and Ren, 2021a,
b), at each round, only an inaccurate context $\widehat{\mathbf{x}}_{t}$ is
available to the decision-maker, and the exact context $\mathbf{x}_{t}$ is
revealed after the action is taken. Under suitable conditions, (Yang and Ren,
2021a) proves that the regret of Thompson sampling is
$\widetilde{\mathcal{O}}(d\sqrt{T}+L_{f}\sqrt{d}\sum_{t\in[T]}\|\widehat{\mathbf{x}}_{t}-\mathbf{x}_{t}\|_{2})$,
where $L_{f}$ is the smoothness parameter of the reward. (Yang and Ren, 2021b)
considers the robustness objective of maximizing the worst-case reward or
minimizing the worst-case regret. In (Bouneffouf, 2020; Galozy et al., 2020),
the authors consider the setting where each context $\mathbf{x}_{t}$ is
completely corrupted with some probability and the corruption cannot be
recovered. In (Ding et al., 2022), the context is attacked by an adversarial
agent. Because these works focus more on adversarial settings for the context
observations, the application of their regret bounds to our setting results in
a linear regret. Given the applications we consider, we can exploit the
stochastic nature of the noisy context observations in our algorithm to
achieve improved performance.

###  1.2 Notations

Throughout this paper, we use $[n]$ to represent the set $\\{1,2,\ldots,n\\}$
for any positive integer $n$. For two real numbers $a,b\in\mathbb{R}$, let
$a\wedge b$ denote the minimum of $a$ and $b$. Given a positive integer $d$,
$\bm{I}_{d}$ denotes the $d$-by-$d$ identity matrix, and $\mathbf{1}_{d}$
denotes the $d$-dimensional vector with 1 in each entry. For a vector
$\bm{v}\in\mathbb{R}^{d}$, denote $\|\bm{v}\|_{2}$ as its $\ell_{2}$ norm. For
a matrix $\bm{M}\in\mathbb{R}^{m\times n}$, denote $\|\bm{M}\|_{2}$ as its
operator norm. The notation $\mathcal{O}(X)$ refers to a quantity that is
upper bounded by $X$ up to constant multiplicative factors, while
$\widetilde{\mathcal{O}}(X)$ refers to a quantity that is upper bounded by $X$
up to poly-log factors.

##  2 Measurement error adjustment to bandit with noisy context

###  2.1 Problem setting

We consider a linear contextual bandit with context space
$\mathcal{X}\subset\mathbb{R}^{d}$ and binary action space
$\mathcal{A}=\\{0,1\\}$111For simplicity, we consider the binary-action
setting, which is common in healthcare (Trella et al., 2022), economics (Athey
et al., 2017; Kitagawa and Tetenov, 2018) and many other applications.
However, all the results presented in this paper can be extended to the
setting with multiple actions. See Appendix D for details.. Let $T$ be the
time horizon. As discussed above, we consider the setting where at each time
$t\in[T]$, the agent only observes a noisy version of the context
$\widetilde{\mathbf{x}}_{t}$ instead of the true underlying context
$\mathbf{x}_{t}$. Thus at time $t$, the observation $o_{t}$ only contains
$(\widetilde{\mathbf{x}}_{t},a_{t},r_{t})$, where $a_{t}$ is the action and
$r_{t}$ is the corresponding reward. We further assume that
$\widetilde{\mathbf{x}}_{t}=\mathbf{x}_{t}+\bm{\epsilon}_{t}$, where the error
$\bm{\epsilon}_{t}$ is uniformly bounded and is independent of the history
$\mathcal{H}_{t-1}:=\\{o_{\tau}\\}_{\tau\leq t-1}$,
$\mathbb{E}\bm{\epsilon}_{t}=0$, $\operatorname{{\rm
Var}}\bm{\epsilon}_{t}=\bm{\Sigma}_{e,t}$. Initially we assume that
$(\bm{\Sigma}_{e,t})_{t\geq 1}$ is known. In Section 2.5, we consider the
setting where we have estimators of $(\bm{\Sigma}_{e,t})_{t\geq 1}$. We do not
make further restrictions on the distribution of $(\bm{\epsilon}_{t})_{t\geq
1}$. The reward
$r_{t}=\langle\bm{\theta}_{a_{t}}^{*},\mathbf{x}_{t}\rangle+\eta_{t}$, where
$\mathbb{E}[\eta_{t}|\mathcal{H}_{t-1},\bm{\epsilon}_{t},a_{t}]=0$ and
$(\bm{\theta}_{a}^{*})_{a\in\mathcal{A}}$ are the unknown parameters. It’s
worth noting that besides the policy, all the randomness here comes from the
reward noise $\eta_{t}$ and the measurement error $\bm{\epsilon}_{t}$. We
treat $(\mathbf{x}_{t})_{t\geq 1}$ as fixed throughout but unknown to the
algorithm (Unlike Yun et al. (2017), we don’t assume $\mathbf{x}_{t}$ are
i.i.d.). Our goal at each time $t$ is to design policy
$\pi_{t}(\cdot|\mathcal{H}_{t-1},\widetilde{\mathbf{x}}_{t})\in\Delta(\mathcal{A})$
given past history $\mathcal{H}_{t-1}$ and current observed noisy context
$\widetilde{\mathbf{x}}_{t}$, so that the agent can maximize the reward by
taking action
$a_{t}\sim\pi_{t}(\cdot|\mathcal{H}_{t-1},\widetilde{\mathbf{x}}_{t})$.

If $\bm{\Sigma}_{e,t}$ does not go to zero as $t$ grows, naive contextual
bandit algorithms are clearly sub-optimal, as they do not take the errors
$(\bm{\epsilon}_{t})_{t\geq 1}$ into account. It is thus necessary to design
an online algorithm that adjusts for these errors. To achieve this goal, we
must first redefine the regret by comparing to a suitable benchmark policy in
this setting.

###  2.2 Choice of the benchmark policy

We set the benchmark to perform ‘optimally’ with the knowledge of infinite
data. As the sequence $(\mathbf{x}_{t})_{t\geq 1}$ is never revealed, the
benchmark policy
$\pi_{t}^{\dagger}(\cdot|\widetilde{\mathbf{x}}_{t},\mathcal{H}_{t-1})$ can
only use observation of $\widetilde{\mathbf{x}}_{t}$, $\mathcal{H}_{t-1}$ and
knowledge of $(\bm{\theta}_{a}^{*})_{a\in\\{0,1\\}}$ to select actions at time
$t$.

As for reward maximization, notice that condition on the history
$\mathcal{H}_{t-1}$, maximizing expected reward with respect to policy $\pi$
is equivalent to minimizing the loss

$\displaystyle\ell_{t}(\pi;\mathbf{x}_{t},\mathcal{H}_{t-1})$
$\displaystyle=\mathbb{E}_{\widetilde{\mathbf{x}}_{t}=\mathbf{x}_{t}+\bm{\epsilon}_{t}}\mathbb{E}_{a_{t}\sim\pi(\cdot|\widetilde{\mathbf{x}}_{t},\mathcal{H}_{t-1})}|\langle\bm{\theta}_{0}^{*}-\bm{\theta}_{1}^{*},\mathbf{x}_{t}\rangle|\cdot
1_{\\{\langle\bm{\theta}_{a_{t}}^{*}-\bm{\theta}_{1-a_{t}}^{*},\mathbf{x}_{t}\rangle<0\\}}$
$\displaystyle=|\langle\bm{\theta}_{0}^{*}-\bm{\theta}_{1}^{*},\mathbf{x}_{t}\rangle|\cdot\mathbb{E}_{\widetilde{\mathbf{x}}_{t}=\mathbf{x}_{t}+\bm{\epsilon}_{t}}\left[1_{\left\\{f(\widetilde{\mathbf{x}}_{t})\cdot{\mathop{\mathrm{sign}}}(\langle\bm{\theta}_{0}^{*}-\bm{\theta}_{1}^{*},\mathbf{x}_{t}\rangle)<0\right\\}}\right].$
(2.1)

Here $f(\widetilde{\mathbf{x}}_{t})\in\\{\pm 1\\}$ is a (possibly random)
mapping of $\widetilde{\mathbf{x}}_{t}$, potentially depending on
$\mathcal{H}_{t-1}$, to predict the sign of
$\langle\bm{\theta}_{0}^{*}-\bm{\theta}_{1}^{*},\mathbf{x}_{t}\rangle$; $f=1$
and $-1$ correspond to the optimal action $a_{t}=0$ and 1 respectively. This
implies that there’s a one-to-one correspondence between the randomized
mapping $f$ and the policy $\pi$, and thus the loss minimization can be viewed
as minimizing $\ell_{t}(\pi(f);\mathbf{x}_{t})$ with respect to $f$.
Furthermore, upon close inspection, (2.1) can be viewed as a task of
estimating the sign of a linear transform of the unknown parameter
$\mathbf{x}_{t}$ given one single sample $\widetilde{\mathbf{x}}_{t}$ with
mean $\mathbf{x}_{t}$.

As in most parameter estimation problems, there is no function that minimizes
the loss for all parameter values. To illustrate in this context, fix some
$\mathbf{x}$ s.t.
$\langle\bm{\theta}_{0}^{*}-\bm{\theta}_{1}^{*},\mathbf{x}\rangle\neq 0$ and
consider the constant mapping
$f_{\mathbf{x}}(\widetilde{\mathbf{x}}_{t})\equiv\mathop{\mathrm{sign}}(\langle\bm{\theta}_{0}^{*}-\bm{\theta}_{1}^{*},\mathbf{x}\rangle)$.
It is easy to see that
$\ell_{t}(\pi(f_{\mathbf{x}});\mathbf{x}_{t},\mathcal{H}_{t-1})=0$ for all
$\mathbf{x}_{t}$ such that
$\mathop{\mathrm{sign}}(\langle\bm{\theta}_{0}^{*}-\bm{\theta}_{1}^{*},\mathbf{x}_{t}\rangle)=\mathop{\mathrm{sign}}(\langle\bm{\theta}_{0}^{*}-\bm{\theta}_{1}^{*},\mathbf{x}\rangle)$.
On the other hand,
$\ell_{t}(\pi(f_{\mathbf{x}});\mathbf{x}_{t},\mathcal{H}_{t-1})=|\langle\bm{\theta}_{0}^{*}-\bm{\theta}_{1}^{*},\mathbf{x}_{t}\rangle|$
for all $\mathbf{x}_{t}$ such that
$\mathop{\mathrm{sign}}(\langle\bm{\theta}_{0}^{*}-\bm{\theta}_{1}^{*},\mathbf{x}_{t}\rangle)=-\mathop{\mathrm{sign}}(\langle\bm{\theta}_{0}^{*}-\bm{\theta}_{1}^{*},\mathbf{x}\rangle)$.
Therefore, for any $\mathbf{x}_{t}$, there is always a mapping $f$ that
achieves zero loss at $\mathbf{x}_{t}$. But these mappings typically behave
badly at other values of $\mathbf{x}_{t}$: In fact, it’s impossible to find a
mapping that achieves 0 loss at _all_ $\mathbf{x}_{t}$.

Despite the above fact, the following lemma shows the advantage of the natural
mapping
$f(\widetilde{\mathbf{x}}_{t})=f_{t}^{\dagger}(\widetilde{\mathbf{x}}_{t}):=\mathop{\mathrm{sign}}(\langle\bm{\theta}_{0}^{*}-\bm{\theta}_{1}^{*},\widetilde{\mathbf{x}}_{t}\rangle)$.
The proof is in Appendix E.

######  Lemma 2.1.

Let $\mathcal{G}$ be the set of all mappings (including deterministic and
random ones) from $\mathbb{R}$ to $\mathbb{R}$. Then the followings hold:

(i) If $d=1$, then for any fixed distribution of $\bm{\epsilon}_{t}$ that is
continuous and symmetric around zero, for any $\mathbf{x}\in\mathbb{R}$,
$f_{t}^{\dagger}\in\mathop{\mathrm{argmin}}_{f\in\mathcal{G}}\\{\ell_{t}(\pi(f);\mathbf{x})+\ell_{t}(\pi(f);-\mathbf{x})\\}$.

(ii) For general $d$, given any fixed distribution of $\bm{\epsilon}_{t}$ that
is continuous and symmetric around zero, for any $\mathbf{x}$,
$f_{t}^{\dagger}\in\mathop{\mathrm{argmin}}_{f\in\mathcal{F}}\\{\ell_{t}(\pi(f);\mathbf{x})+\ell_{t}(\pi(f);-\mathbf{x})\\}$.
Here, $\mathcal{F}:=\\{f(\cdot):\exists g\in\mathcal{G}\text{ s.t.
}f(\widetilde{\mathbf{x}}_{t})=g(\langle\bm{\theta}_{0}^{*}-\bm{\theta}_{1}^{*},\widetilde{\mathbf{x}}_{t}\rangle)\\}$.

That is, in the one-dimensional case, $f(\widetilde{\mathbf{x}}_{t})$ always
minimizes the average loss between $\mathbf{x}_{t}=\mathbf{x}$ and
$\mathbf{x}_{t}=-\mathbf{x}$ for any $\mathbf{x}$ under mild regularity
conditions. In the general case, $f(\widetilde{\mathbf{x}}_{t})$ minimizes
this average loss for any $\mathbf{x}$ among all mappings of the form
$f(\widetilde{\mathbf{x}}_{t})=g(\langle\bm{\theta}_{0}^{*}-\bm{\theta}_{1}^{*},\widetilde{\mathbf{x}}_{t}\rangle)$.
Therefore, $f=f_{t}^{\dagger}$ is a reasonable choice for reward maximization.
Actually, it corresponds to the action
$a_{t}^{\dagger}:=\mathop{\mathrm{argmax}}_{a}\langle\bm{\theta}^{*}_{a},\widetilde{\mathbf{x}}_{t}\rangle$.
Thus we set the benchmark policy as

$\pi_{t}^{*}(a)=\begin{cases}1,\quad&\text{if
}a=a_{t}^{\dagger}=\mathop{\mathrm{argmax}}_{a}\langle\bm{\theta}^{*}_{a},\widetilde{\mathbf{x}}_{t}\rangle,\\\
0,\quad&\text{otherwise.}\end{cases}$ (2.2)

For any policy $\pi=\\{\pi_{t}\\}_{t}$, we define the cumulative regret as

$\text{Regret}(T;\pi^{*})=\sum\nolimits_{t\in[T]}[\mathbb{E}_{a\sim\pi_{t}^{*}}\langle\bm{\theta}^{*}_{a},\widetilde{\mathbf{x}}_{t}\rangle-\mathbb{E}_{a\sim\pi_{t}}\langle\bm{\theta}^{*}_{a},\widetilde{\mathbf{x}}_{t}\rangle].$
(2.3)

Further, in many applications, it’s desirable to design the policy under the
constraint that each action is sampled with a minimum probability $p_{0}$. One
reason for maintaining exploration is that we can update and re-optimize the
policy for future users to allow for potential non-stationarity (Yang et al.,
2020a). Additionally, keeping the exploration is also important for after-
study analysis (Yao et al., 2021), especially when the goal of the analysis is
not pre-specified prior to conducting data with the online algorithm.
Considering these factors, we also set a clipped benchmark policy

$\pi_{t}^{\dagger}(a)=\begin{cases}1-p_{0},\quad&\text{if
}a=a_{t}^{\dagger}=\mathop{\mathrm{argmax}}_{a}\langle\bm{\theta}^{*}_{a},\widetilde{\mathbf{x}}_{t}\rangle,\\\
p_{0},\quad&\text{otherwise,}\end{cases}$ (2.4)

and define $\text{Regret}(T;\pi^{\dagger})$ accordingly.

###  2.3 Estimation using weighted measurement error adjustment

In this section, we focus on learning the reward model parameters
$(\bm{\theta}_{a}^{*})_{a\in\mathcal{A}}$ with data $\mathcal{H}_{t}$ after a
policy
$(\pi_{\tau}(\cdot|\widetilde{\mathbf{x}}_{\tau},\mathcal{H}_{\tau-1}))_{\tau\in[t]}$
has been executed up to time $t\in[T]$. Learning a consistent model is
important in many bandit algorithms for achieving low regret (Abbasi-Yadkori
et al., 2011; Agrawal and Goyal, 2013). As we shall see in Section 2.4,
consistent estimation of $(\bm{\theta}_{a}^{*})_{a\in\mathcal{A}}$ also plays
an essential role in controlling the regret of our proposed algorithm.

A naive estimator. If $(\bm{\epsilon}_{\tau},\eta_{\tau})_{\tau\in[t]}$ are
i.i.d., there is only a single action $a=0$ and
$\bm{\Sigma}_{e,\tau}\equiv\bm{\Sigma}_{e}$, the classic linear measurement
error model provides a useful solution for estimating the model parameter
$\bm{\theta}_{0}^{*}$ given batch data
$(\widetilde{\mathbf{x}}_{\tau},r_{\tau})_{\tau\in[t]}$ (Fuller, 2009; Carroll
et al., 1995). In this single-action setting,
$\widehat{\bm{\theta}}_{0,me}^{(t)}:=\big{(}\frac{1}{t}\sum_{\tau\in[t]}\widetilde{\mathbf{x}}_{\tau}\widetilde{\mathbf{x}}_{\tau}^{\top}-\bm{\Sigma}_{e}\big{)}^{-1}\big{(}\frac{1}{t}\sum_{\tau\in[t]}\widetilde{\mathbf{x}}_{\tau}r_{\tau}\big{)}$
is a consistent estimator of $\bm{\theta}_{0}^{*}$. When there are multiple
actions, a naive generalization of the above estimator might be

$\widehat{\bm{\theta}}_{a,me}^{(t)}:=\bigg{(}\sum\nolimits_{{\tau}\in[t]}1_{\\{a_{\tau}=a\\}}(\widetilde{\mathbf{x}}_{\tau}\widetilde{\mathbf{x}}_{\tau}^{\top}-\bm{\Sigma}_{e})\bigg{)}^{-1}\bigg{(}\sum\nolimits_{{\tau}\in[t]}1_{\\{a_{\tau}=a\\}}\widetilde{\mathbf{x}}_{\tau}r_{\tau}\bigg{)}.$
(2.5)

Unfortunately, $\widehat{\bm{\theta}}_{a,me}^{(t)}$ is generally not
consistent in the multiple-action setting, even if the policy
$(\pi_{\tau})_{\tau\in[t]}$ is _stationary and not adaptive to history_. This
difference is essentially due to the interaction between the policy and the
measurement error: In the classical measurement error (single-action) setting,
$\mathbb{E}(\widetilde{\mathbf{x}}_{\tau}\widetilde{\mathbf{x}}_{\tau}^{\top})=\mathbf{x}_{\tau}\mathbf{x}_{\tau}^{\top}+\bm{\Sigma}_{e}$,
and
$\frac{1}{t}\sum_{\tau\in[t]}\widetilde{\mathbf{x}}_{\tau}\widetilde{\mathbf{x}}_{\tau}^{\top}-\bm{\Sigma}_{e}$
concentrates around its expectation
$\frac{1}{t}\sum_{{\tau}\in[t]}\mathbf{x}_{\tau}\mathbf{x}_{\tau}^{\top}$.
Likewise,
$\frac{1}{t}\sum_{{\tau}\in[t]}\widetilde{\mathbf{x}}_{\tau}r_{\tau}$
concentrates around
$(\frac{1}{t}\sum_{\tau\in[t]}\mathbf{x}_{\tau}\mathbf{x}_{\tau}^{\top})\bm{\theta}_{0}^{*}$.
Combining the above parts thus yields a consistent estimator of
$\bm{\theta}_{0}^{*}$. In our setting with multiple actions, however, the
agent picks the action $a_{\tau}$ _based on_ $\widetilde{\mathbf{x}}_{\tau}$,
so only certain values of $\widetilde{\mathbf{x}}_{\tau}$ lead to
$a_{\tau}=a$. Therefore, for those $\tau\in[t]$ when we pick $a_{\tau}=a$,
it’s more likely that $\widetilde{\mathbf{x}}_{\tau}$ falls in certain regions
depending on the policy, and we shouldn’t expect
$\mathbb{E}(\widetilde{\mathbf{x}}_{\tau}\widetilde{\mathbf{x}}_{\tau}^{\top})=\mathbf{x}_{\tau}\mathbf{x}_{\tau}^{\top}+\bm{\Sigma}_{e}$
anymore. In other words, the policy creates a complicated dependence between
$\widetilde{\mathbf{x}}_{\tau}\widetilde{\mathbf{x}}_{\tau}^{\top}$ and
$1_{\\{a_{\tau}=0\\}}$ for each $\tau$, which changes the limit of
$\sum_{{\tau}\in[t]}1_{\\{a_{\tau}=a\\}}(\widetilde{\mathbf{x}}_{\tau}\widetilde{\mathbf{x}}_{\tau}^{\top}-\bm{\Sigma}_{e})$
(and similarly
$\sum_{{\tau}\in[t]}1_{\\{a_{\tau}=a\\}}\widetilde{\mathbf{x}}_{\tau}r_{\tau}$).
This leads to the inconsistency of the naive estimator (See Appendix B for a
concrete example). In Section 3, we provide examples to show that (2.5) not
only deviates from the true parameters, but also leads to bad decision-making.

Our proposed estimator. Inspired by the above observations, for
$\pi_{\tau}(a|\widetilde{\mathbf{x}}_{\tau},\mathcal{H}_{\tau-1})$ positive,
we construct the following estimator for $\bm{\theta}^{*}_{a}$ given
$\mathcal{H}_{t}$, which corrects (2.5) using importance weights:

$\displaystyle\widehat{\bm{\theta}}_{a}^{(t)}:=\bigg{(}\widehat{\bm{\Sigma}}_{\widetilde{\mathbf{x}},a}^{(t)}-\frac{1}{t}\sum\nolimits_{\tau\in[t]}\pi^{nd}_{\tau}(a)\bm{\Sigma}_{e,\tau}\bigg{)}^{-1}\cdot\widehat{\bm{\Sigma}}_{\widetilde{\mathbf{x}},r,a}^{(t)},$
(2.6)

where

$\widehat{\bm{\Sigma}}_{\widetilde{\mathbf{x}},a}^{(t)}=\frac{1}{t}\sum_{\tau\in[t]}\frac{\pi_{\tau}^{nd}(a_{\tau})}{\pi_{\tau}(a_{\tau}|\widetilde{\mathbf{x}}_{\tau},\mathcal{H}_{\tau-1})}1_{\\{a_{\tau}=a\\}}\widetilde{\mathbf{x}}_{\tau}\widetilde{\mathbf{x}}_{\tau}^{\top},\quad\widehat{\bm{\Sigma}}_{\widetilde{\mathbf{x}},r,a}^{(t)}=\frac{1}{t}\sum_{\tau\in[t]}\frac{\pi_{\tau}^{nd}(a_{\tau})}{\pi_{\tau}(a_{\tau}|\widetilde{\mathbf{x}}_{\tau},\mathcal{H}_{\tau-1})}1_{\\{a_{\tau}=a\\}}\widetilde{\mathbf{x}}_{\tau}r_{\tau}.$

Here, $(\pi_{\tau}^{nd}(\cdot))_{\tau\in[t]}$ is a pre-specified policy (i.e.
not data-dependent) that can be chosen by the algorithm. We provide
theoretical guarantees for $\widehat{\bm{\theta}}_{a}^{(t)}$ under the
following assumptions:

######  Assumption 2.1 (Boundedness).

$\forall t\in[T]$, $\|\widetilde{\mathbf{x}}_{t}\|_{2}\leq 1$; There exists a
positive constant $R_{\theta}$ such that $\forall a\in\\{0,1\\}$,
$\|\bm{\theta}_{a}^{*}\|_{2}\leq R_{\theta}$; There exists a positive constant
$R$ such that $\forall t\in[T]$, $|r_{t}|\leq R$.

######  Assumption 2.2 (Minimum eigenvalue).

There exists a positive constant $\lambda_{0}$ such that $\forall
t\geq\sqrt{T}$, $a\in\\{0,1\\}$, $\frac{1}{t}\sum_{\tau\leq
t}\pi_{\tau}^{nd}(a)\mathbf{x}_{\tau}\mathbf{x}_{\tau}^{\top}\succeq\lambda_{0}\bm{I}_{d}$.

######  Remark 2.1.

Assumption 2.2 is mild. Even restricted to the choice of
$\pi_{\tau}^{nd}(a)\equiv 1/2$, under mild conditions, the assumption can be
satisfied with deterministic $(\mathbf{x}_{\tau})_{\tau\geq 1}$ or stochastic
$(\mathbf{x}_{\tau})_{\tau\geq 1}$ such as an i.i.d. sequence, a weakly
dependent stationary time series (e.g. multivariate ARMA process (Fan and Yao,
2017)), or a sequence with periodicity/seasonality with high probability (See
Appendix F for details).

The theorem below gives a high-probability upper bound on
$\|\widehat{\bm{\theta}}_{a}^{(t)}-\bm{\theta}_{a}^{*}\|_{2}$ (proof in
Appendix F).

######  Theorem 2.1.

For any $t\in[T]$, denote $q_{t}\\!:=\inf_{\tau\leq
t,a\in\\{0,1\\}}\pi_{\tau}(a|\widetilde{\mathbf{x}}_{\tau},\mathcal{H}_{\tau-1})$.
Then under Assumptions 2.1 and 2.2, there exist constants $C$ and $C_{1}$ such
that as long as
$q_{t}\geq\frac{C_{1}}{\lambda_{0}\wedge\lambda_{0}^{2}}\frac{d+\log t}{t}$,
with probability at least $1\\!-\\!\frac{8}{t^{2}}$,

$\|\widehat{\bm{\theta}}_{a}^{(t)}-\bm{\theta}_{a}^{*}\|_{2}\leq\frac{C(R+R_{\bm{\theta}})}{\lambda_{0}}\max\bigg{\\{}\frac{d\\!+\\!\log
t}{q_{t}t},\sqrt{\frac{d\\!+\\!\log t}{q_{t}t}}\bigg{\\}},\quad\forall
a\in\\{0,1\\}.$ (2.7)

######  Remark 2.2.

If $q_{t}t\gg d$, Theorem 2.1 indicates that
$\|\widehat{\bm{\theta}}_{a}^{(t)}-\bm{\theta}_{a}^{*}\|_{2}\lesssim\sqrt{\frac{d}{q_{t}t}}$
ignoring logarithmic terms. This result intuitively aligns with the typical
rate observed in statistical estimation, considering that the minimum
‘effective sample size’ for an action is $q_{t}t$. However, in general,
Theorem 2.1 allows $q_{t}$ to go to zero as fast as the rate $\frac{d+\log
t}{t}$.

Unlike the existing literature on off-policy learning in contextual bandits
(e.g. Wang et al. (2017); Zhan et al. (2021); Zhang et al. (2021); Bibaut et
al. (2021)), the role of the importance weights here is to correct the
dependence of a policy on the observed noisy context with error. The proof
idea can be generalized to a large class of off-policy method-of-moment
estimators, which might be of independent interest (See Appendix F).

###  2.4 MEB: Online bandit algorithm with measurement error adjustment

Algorithm 1 MEB (Measurement Error Bandit)

1: Input: $(\bm{\Sigma}_{e,t})_{t\in[T]}$: covariance sequence of
$(\bm{\epsilon}_{t})_{t\in[T]}$; $(p_{0}^{(t)})_{t\in[T]}$: minimum selection
probability at each time $t$; $T_{0}$: length of pure exploration

2: for time $t=1,2,\ldots,T$ do

3: if $t\leq T_{0}$ then

4: Sample
$a_{t}\sim\pi_{t}(\cdot|\widetilde{\mathbf{x}}_{t},\mathcal{H}_{t-1})$, where
$\pi_{t}(a|\widetilde{\mathbf{x}}_{t},\mathcal{H}_{t-1})=1/2$ for all
$a\in\\{0,1\\}$

5: else

6: Obtain updated estimators
$(\widehat{\bm{\theta}}_{a}^{(t-1)})_{a\in\\{0,1\\}}$ from (2.6)

7:
$\widetilde{a}_{t}\leftarrow\mathop{\mathrm{argmax}}_{a\in\\{0,1\\}}\langle\widehat{\bm{\theta}}_{a}^{(t-1)},\widetilde{\mathbf{x}}_{t}\rangle$

8: Sample
$a_{t}\sim\pi_{t}(\cdot|\widetilde{\mathbf{x}}_{t},\mathcal{H}_{t-1})$, where
$\pi_{t}(a|\widetilde{\mathbf{x}}_{t},\mathcal{H}_{t-1}):=\begin{cases}1-p_{0}^{(t)},\quad\text{if
}a=\widetilde{a}_{t}\\\ p_{0}^{(t)},\quad\text{otherwise}\end{cases}$

9: end if

10: end for

In this section, we propose MEB (Measurement Error Bandit), an online bandit
algorithm with measurement error adjustment based on the estimator (2.6). The
algorithm is presented in Algorithm 1 and is designed for the binary-action
setting, although it can be generalized to the case with multiple actions (see
Appendix D). At each time $t$, given the noisy context
$\widetilde{\mathbf{x}}_{t}$, the algorithm computes the best action
$\widetilde{a}_{t}$ according to
$(\widehat{\bm{\theta}}_{a}^{(t-1)})_{a\in\\{0,1\\}}$ calculated from (2.6).
Then, it simply samples $\widetilde{a}_{t}$ with probability $1-p_{0}^{(t)}$
and keeps an exploration probability of $p_{0}^{(t)}$ to sample the other
action. Here, $p_{0}^{(t)}\in(0,\frac{1}{2})$. In many common scenarios, we
can often set $p_{0}^{(t)}$ to be monotonically decreasing in $t$, in which
case $q_{t}\\!=\inf_{\tau\leq
t,a\in\\{0,1\\}}\pi_{\tau}(a|\widetilde{\mathbf{x}}_{\tau},\mathcal{H}_{\tau-1})=p_{0}^{(t)}$
for all $t\in[T]$.

Below, we focus on policies that always maintain an exploration probability of
at least $p_{0}$ where $p_{0}>0$. As discussed in Section 2.2, these policies
are used in many real-life applications in order to cope with potential future
non-stationarity and to perform efficient after-study analysis. In this
setting, it’s natural to choose $p_{0}^{(t)}\equiv p_{0}$ in Algorithm 1, and
we consider the regret compared to the clipped benchmark policy (2.4). In
Appendix C, we show that with other hyperparameter choices, MEB achieves a
regret upper bound of $\widetilde{\mathcal{O}}(T^{2/3})$ with respect to the
horizon $T$ compared to the non-clipped benchmark (2.2).

We first prove the following theorem, which states that the regret of MEB can
be directly controlled by the estimation error. In fact, this theorem holds
regardless of the form or quality of the estimation procedure (i.e. in line 6
of Algorithm 1). The proof is in Appendix G.

######  Theorem 2.2.

Given Assumption 2.1, the regret of Algorithm 1 satisfies

$\text{Regret}(T;\pi^{\dagger})\leq
2T_{0}R_{\theta}+2(1-2p_{0})\sum\nolimits_{t\in(T_{0},T]}\max\nolimits_{a\in\\{0,1\\}}\|\widehat{\bm{\theta}}_{a}^{(t-1)}-\bm{\theta}_{a}^{*}\|_{2}.$

The following corollary provides the regret guarantee of MEB by combining
Theorem 2.1 and 2.2 (Proof in Appendix G).

######  Corollary 2.1.

There exist constants $C,C^{\prime}$ such that by choosing $T_{0}=\lceil
2\sqrt{T}\rceil$, for any $T$ satisfying $T\geq
C^{\prime}\max\\{1,\frac{d^{2}+\log^{2}({T})}{p_{0}^{2}},\frac{d^{2}+\log^{2}({T})}{\lambda_{0}^{2}(1\wedge\lambda_{0}^{2})p_{0}^{2}}\\}$,
with probability at least $1\\!-\\!\frac{16}{\sqrt{T}}$, the regret of
Algorithm 1:

$\text{Regret}(T;\pi^{\dagger})\leq
C\cdot\left\\{R_{\theta}\sqrt{T}+\frac{(R\\!+\\!R_{\theta})(1\\!-\\!2p_{0})}{\lambda_{0}\sqrt{p_{0}}}\sqrt{T({d}\\!+\\!{\log
T})}\right\\}.$

Ignoring other factors, the regret upper bound is of order
$\mathcal{O}(\sqrt{T(d\\!+\\!\log T)})$ depending on the horizon $T$ and
dimension $d$.

In certain scenarios (e.g. when $d$ is large), it is desirable to save
computational resources by updating the estimates of
$(\bm{\theta}_{a}^{*})_{a\in\\{0,1\\}}$ less frequently in Algorithm 1.
Fortunately, low regret guarantees can still be achieved: Suppose at each time
$t$, the agent only updates the estimators according to (2.6) at selected time
points $t\in{\mathcal{S}}\subseteq[T]$ (in line 6); Otherwise, the agent
simply makes decisions based on the most recently updated estimators. In
Appendix G, we show that time points to perform the updates can be very
infrequent, such as $(n^{k})_{k\in\mathbb{N}^{+}}$ ($n\geq
2,n\in\mathbb{N}^{+}$), while still achieving the same rate of regret upper
bound as in Corollary 2.1.

###  2.5 Results given estimated error variance

In practice, the agent might not have perfect knowledge about
$\bm{\Sigma}_{e,t}$, the variance of the error $\bm{\epsilon}_{t}$. In this
section, we assume that at each time $t$, the agent has a (potentially
adaptive) estimator $\widehat{\bm{\Sigma}}_{e,t}$ that is close to
$\bm{\Sigma}_{e,t}$. Then, it is natural to replace $\bm{\Sigma}_{e,t}$ with
$\widehat{\bm{\Sigma}}_{e,t}$ in (2.6) to obtain the estimator for
$\bm{\theta}_{a}^{*}$ at time $t$:

$\widetilde{\bm{\theta}}_{a}^{(t)}:=\big{(}\widehat{\bm{\Sigma}}_{\widetilde{\mathbf{x}},a}^{(t)}-\frac{1}{t}\sum\nolimits_{\tau\in[t]}\pi^{nd}_{\tau}(a)\widehat{\bm{\Sigma}}_{e,\tau}\big{)}^{-1}\cdot\widehat{\bm{\Sigma}}_{\widetilde{\mathbf{x}},r,a}^{(t)}.$
(2.8)

The theorem below shows the consistency guarantees for
$\widetilde{\bm{\theta}}_{a}^{(t)}$ (Proof in Appendix H). An essential
quantity in the theorem is defined as
$\bm{\Delta}_{t}(a):=\frac{1}{t}\sum_{\tau\in[t]}\pi_{\tau}^{nd}(a)(\widehat{\bm{\Sigma}}_{e,\tau}-\bm{\Sigma}_{e,\tau})$
for $t\in[T]$, $a\in\\{0,1\\}$.

######  Theorem 2.3.

Recall that $q_{t}\\!:=\inf_{\tau\leq
t,a\in\\{0,1\\}}\pi_{\tau}(a|\widetilde{\mathbf{x}}_{\tau},\mathcal{H}_{\tau-1})$.
Then under Assumptions 2.1 and 2.2, there exist constants $C$ and
$C_{1}^{\prime}$ such that as long as
$q_{t}\geq\frac{C_{1}^{\prime}}{\min\\{\lambda_{0},\lambda_{0}^{2}\\}}\frac{d+\log
t}{t}$ and
$\max_{a\in\\{0,1\\}}\|\bm{\Delta}_{t}(a)\|_{2}\leq\frac{\lambda_{0}}{4}$,
with probability at least $1\\!-\\!\frac{8}{t^{2}}$,

$\|\widetilde{\bm{\theta}}_{a}^{(t)}-\bm{\theta}_{a}^{*}\|_{2}\leq\frac{C(R+R_{\bm{\theta}})}{\lambda_{0}}\max\bigg{\\{}\frac{d\\!+\\!\log
t}{q_{t}t},\sqrt{\frac{d\\!+\\!\log
t}{q_{t}t}}\bigg{\\}}+\frac{2R_{\theta}}{\lambda_{0}}\|\bm{\Delta}_{t}(a)\|_{2},\quad\forall
a\in\\{0,1\\}.$ (2.9)

By plugging in $\widetilde{\bm{\theta}}_{a}^{(t)}$ instead of
$\widehat{\bm{\theta}}_{a}^{(t)}$ as estimators in Algorithm 1 (line 6), we
have the following regret bound combining Theorems 2.2 and 2.3 (Proof in
Appendix H).

######  Corollary 2.2.

Suppose that
$\max_{t\in[\sqrt{T},T]}\max_{a\in\\{0,1\\}}\|\bm{\Delta}_{t}(a)\|_{2}\leq\frac{\lambda_{0}}{4}$.
Then there exist constants $C$, $C^{\prime\prime}$ such that by choosing
$T_{0}=\lceil 2\sqrt{T}\rceil$, for any $T$ satisfying $T\geq
C^{\prime\prime}\max\\{1,\frac{d^{2}+\log^{2}({T})}{p_{0}^{2}},\frac{d^{2}+\log^{2}({T})}{\lambda_{0}^{2}(1\wedge\lambda_{0}^{2})p_{0}^{2}}\\}$,
with probability at least $1-\frac{16}{\sqrt{T}}$, Algorithm 1 with
$\widetilde{\bm{\theta}}_{a}^{(t)}$ as plug-in estimators achieves:

$\displaystyle\text{Regret}(T;\pi^{\dagger})\leq$ $\displaystyle\thickspace
C\cdot\left\\{R_{\theta}\sqrt{T}+\frac{(R\\!+\\!R_{\theta})(1\\!-\\!2p_{0})}{\lambda_{0}\sqrt{p_{0}}}\sqrt{T({d}\\!+\\!{\log
T})}\right\\}$
$\displaystyle+\frac{4(1-2p_{0})R_{\theta}}{\lambda_{0}}\sum\nolimits_{t\in[2\sqrt{T}-1,T)\cap\mathbb{N}}\max\nolimits_{a\in\\{0,1\\}}\|\bm{\Delta}_{t}(a)\|_{2}.$
(2.10)

Theorem 2.3 and Corollary 2.2 show that both
$\widetilde{\bm{\theta}}_{a}^{(t)}$ and Algorithm 1 behave nicely if
$\bm{\Delta}_{t}(a)$, the weighted average of the estimation errors
$(\widehat{\bm{\Sigma}}_{e,\tau}-\bm{\Sigma}_{e,\tau})_{\tau\in[t]}$ is small
for $t\geq\sqrt{T}$. This is not a particularly high requirement: For example,
suppose the agent gathers more data over time so that
$\|\widehat{\bm{\Sigma}}_{e,t}-\bm{\Sigma}_{e,t}\|_{2}\lesssim\frac{1}{\sqrt{t}}$,
then it is easy to see that the last term in the regret bound (2.10)
$\lesssim\frac{(1-p_{0})R_{\theta}}{\lambda_{0}}\sqrt{T}$.

##  3 Simulation results

In this section, we set $d=5$, $T=20000$. In the reward model, let
$\bm{\theta}_{0}^{*}=(0,1,-1,1,-1)$, $\bm{\theta}_{1}^{*}=(1,0,0,0,0)$, and
$\eta_{t}$ drawn i.i.d. from $\mathcal{N}(0,1)$. Let
$(\mathbf{x}_{t})_{t\in[T]}$ be independently sampled from distribution
$\mathcal{N}(\bm{\mu}_{x},\bm{I}_{d})$, where $\bm{\mu}_{x}=\mathbf{1}_{d}$.
We further set
$\bm{\Sigma}_{e,t}\equiv\bm{\Sigma}_{e}:=\frac{1}{4}\bm{I}_{d}$, and consider
independent $(\bm{\epsilon}_{t})_{t\in[T]}$ with two distribution settings:
(i) Normal distribution; (ii) Multivariate $t(3)$ distribution with covariance
$\bm{\Sigma}_{e}$ (which is a typical heavy-tailed distribution). For each
setting, we independently generate bandit data for $n_{exp}=500$ times, and
compare among several candidate algorithms in terms of both estimation quality
and cumulative regret with a moderate exploration probability $p_{0}=0.1$ and
a small exploration probability $p_{0}=0.01$. The algorithms for comparison
include: Thompson sampling given normal priors (Russo et al., 2018) (with the
constraint of exploration probability at least $p_{0}$ at each time $t$), MEB
(Algorithm 1), and MEB-naive (MEB plugged in with the naive measurement error
estimator (2.5) instead of (2.6)).

Figure 1: Estimation error
($\|\widehat{\bm{\theta}}_{0}^{(t)}-\bm{\theta}_{0}^{*}\|_{2}$) and cumulative
regret of three algorithms with minimum exploration probability $p_{0}=0.1$
and $p_{0}=0.01$ under the settings of normal and heavy-tailed errors
$(\bm{\epsilon}_{t})_{t\geq 1}$. The results are calculated from $n_{exp}=500$
independent experiments. The red, blue, and green line corresponds to Thompson
sampling, MEB (Algorithm 1), and MEB-naive (MEB plugged in with the naive
measurement error estimator (2.5)) respectively. The solid lines indicate the
mean values, while the shaded bands represent the standard errors across the
independent experiments.

Figure 1 shows the estimation error
($\|\widehat{\bm{\theta}}_{0}^{(t)}-\bm{\theta}_{0}^{*}\|_{2}$)222Since the
results of $\|\widehat{\bm{\theta}}_{1}^{(t)}-\bm{\theta}_{1}^{*}\|_{2}$ is
similar to $\|\widehat{\bm{\theta}}_{0}^{(t)}-\bm{\theta}_{0}^{*}\|_{2}$, we
omit them here. In fact, estimating $\bm{\theta}_{0}^{*}$ is more challenging
in this setting since any algorithm with low regret should choose action 0
less often. For Thompson sampling, we take the posterior mean to be the
estimators for model parameters. as well as the cumulative regret of the
algorithms with two choices of $p_{0}$ under different settings of
$\bm{\epsilon}_{t}$ distributions. Across all scenarios, MEB is the only
algorithm that produces accurate model estimates and achieves sublinear
regret. Thompson sampling fails to make optimal decisions by disregarding the
presence of the noise $(\bm{\epsilon}_{t})_{t\geq 1}$ in the observed context.
Notably, for MEB-naive, we see that the inconsistent model estimators (2.5)
also lead to poor decision-making, as the regret of MEB-naive blows up in all
four settings. This is especially the case when the minimum exploration
probability $p_{0}$ is small. Moreover, the superior performance of MEB is
robust to the heavy-tailedness of $(\bm{\epsilon}_{t})_{t\geq 1}$, as
demonstrated by the right two columns in Figure 1. We further conduct
experiments with different levels of measurement errors and observe similar
findings (More details in Appendix A).

Despite the fact that the naive estimator (2.5) is inconsistent and can
perform even worse than the Thompson sampling estimator which completely
ignores the measurement errors, it’s interesting to notice that, when $p_{0}$
is small, in the earlier rounds of the online algorithm, the naive estimator
exhibits a smaller estimation error compared to the other two algorithms. This
phenomenon may arise because, in situations with limited data, the variance of
the estimator (2.6) with importance weights outweighs the bias in the naive
estimator. In practice, we can potentially mitigate this issue in two ways:
(i) To use variance reduction techniques (Robins et al., 2007) to enhance the
estimator (2.6); (ii) To fine-tune the sampling rate $(p_{0}^{(t)})_{t\geq 1}$
or switch between estimators during the algorithm for best performance. See
Appendix A for more explanations.

##  4 Discussion and conclusions

We propose a new algorithm, MEB, which is the first algorithm with sublinear
regret guarantees in contextual bandits where the context is observed with
noise, and we have limited knowledge of the noise distribution. This setting
is very common in practice, especially where only predictions for unobserved
context are available. MEB leverages the novel estimator (2.6), which extends
the conventional measurement error adjustment techniques by considering the
interplay between the policy and the measurement error.

Limitations and future directions. Several questions remain for future
investigation. First, is $\mathcal{O}(T^{2/3})$ the optimal rate of regret
compared to the standard benchmark policy (2.4), as in some other bandits with
semi-parametric reward model (e.g. Xu and Wang (2022))? Providing lower bounds
on the regret helps us understand the limit of improvement in the online
algorithm. Second, in our work, we assume that the agent has an unbiased
prediction of the true context. It is important to understand how biased
predictions affect the results, as in practice, machine learning algorithms
may well generate biased predictions. Last but not least, all analyses in this
paper are restricted to bandits, where future contexts are not affected by
previous actions. It’s interesting to see how we can extend our method to more
complicated decision-making settings (e.g. Markov decision processes).

##  5 Societal impact

This work represents the first steps toward using predictions of unobserved
context in an online reinforcement learning algorithm in digital intervention
in clinical trials. This work is intended to lead to the broader impact of
helping health scientists develop more effective digital interventions. The
biggest potential negative impact of this work would be a poor, careless
implementation in real life: For example, an implementation of this algorithm
(or a generalization of this algorithm) that is unstable and thus leads to
patient disengagement from care and a decrease in the patient’s confidence in
the ability of the health care system to help them.

## References

  * Abbasi-Yadkori et al. (2011) Abbasi-Yadkori, Y., Pál, D. and Szepesvári, C. (2011).  Improved algorithms for linear stochastic bandits.  Advances in neural information processing systems 24.
  * Agrawal and Goyal (2013) Agrawal, S. and Goyal, N. (2013).  Thompson sampling for contextual bandits with linear payoffs.  In International conference on machine learning. PMLR.
  * Athey et al. (2017) Athey, S., Wager, S. et al. (2017).  Efficient policy learning.  Tech. rep.
  * Auer (2002) Auer, P. (2002).  Using confidence bounds for exploitation-exploration trade-offs.  Journal of Machine Learning Research 3 397–422.
  * Banna et al. (2016) Banna, M., Merlevède, F. and Youssef, P. (2016).  Bernstein-type inequality for a class of dependent random matrices.  Random Matrices: Theory and Applications 5 1650006\.
  * Battalio et al. (2021) Battalio, S. L., Conroy, D. E., Dempsey, W., Liao, P., Menictas, M., Murphy, S., Nahum-Shani, I., Qian, T., Kumar, S. and Spring, B. (2021).  Sense2stop: a micro-randomized trial using wearable sensors to optimize a just-in-time-adaptive stress management intervention for smoking relapse prevention.  Contemporary Clinical Trials 109 106534\.
  * Bibaut et al. (2021) Bibaut, A., Dimakopoulou, M., Kallus, N., Chambaz, A. and van Der Laan, M. (2021).  Post-contextual-bandit inference.  Advances in neural information processing systems 34 28548–28559.
  * Bouneffouf (2020) Bouneffouf, D. (2020).  Online learning with corrupted context: Corrupted contextual bandits.  arXiv preprint arXiv:2006.15194 .
  * Bouneffouf et al. (2012) Bouneffouf, D., Bouzeghoub, A. and Gan

c

arski, A. L. (2012).  A contextual-bandit algorithm for mobile context-aware
recommender system.  In Neural Information Processing: 19th International
Conference, ICONIP 2012, Doha, Qatar, November 12-15, 2012, Proceedings, Part
III 19. Springer.

  * Carroll et al. (1995) Carroll, R. J., Ruppert, D. and Stefanski, L. A. (1995).  Measurement error in nonlinear models, vol. 105.  CRC press.
  * Cohen et al. (1985) Cohen, S., Mermelstein, R., Kamarck, T. and Hoberman, H. M. (1985).  Measuring the functional components of social support.  Social support: Theory, research and applications 73–94.
  * Ding et al. (2022) Ding, Q., Hsieh, C.-J. and Sharpnack, J. (2022).  Robust stochastic linear contextual bandits under adversarial attacks.  In International Conference on Artificial Intelligence and Statistics. PMLR.
  * Fan and Yao (2017) Fan, J. and Yao, Q. (2017).  The elements of financial econometrics.  Cambridge University Press.
  * Freedman (1975) Freedman, D. A. (1975).  On tail probabilities for martingales.  the Annals of Probability 100–118.
  * Fuller (2009) Fuller, W. A. (2009).  Measurement error models.  John Wiley & Sons.
  * Galozy and Nowaczyk (2023) Galozy, A. and Nowaczyk, S. (2023).  Information-gathering in latent bandits.  Knowledge-Based Systems 260 110099\.
  * Galozy et al. (2020) Galozy, A., Nowaczyk, S. and Ohlsson, M. (2020).  A new bandit setting balancing information from state evolution and corrupted context.  arXiv preprint arXiv:2011.07989 .
  * Hong et al. (2020a) Hong, J., Kveton, B., Zaheer, M., Chow, Y., Ahmed, A. and Boutilier, C. (2020a).  Latent bandits revisited.  Advances in Neural Information Processing Systems 33 13423–13433.
  * Hong et al. (2020b) Hong, J., Kveton, B., Zaheer, M., Chow, Y., Ahmed, A., Ghavamzadeh, M. and Boutilier, C. (2020b).  Non-stationary latent bandits.  arXiv preprint arXiv:2012.00386 .
  * Kirschner and Krause (2019) Kirschner, J. and Krause, A. (2019).  Stochastic bandits with context distributions.  Advances in Neural Information Processing Systems 32.
  * Kitagawa and Tetenov (2018) Kitagawa, T. and Tetenov, A. (2018).  Who should be treated? empirical welfare maximization methods for treatment choice.  Econometrica 86 591–616.
  * Langford and Zhang (2007) Langford, J. and Zhang, T. (2007).  The epoch-greedy algorithm for contextual multi-armed bandits.  Advances in neural information processing systems 20 96–1.
  * Li et al. (2010) Li, L., Chu, W., Langford, J. and Schapire, R. E. (2010).  A contextual-bandit approach to personalized news article recommendation.  In Proceedings of the 19th international conference on World wide web.
  * Liao et al. (2020) Liao, P., Greenewald, K., Klasnja, P. and Murphy, S. (2020).  Personalized heartsteps: A reinforcement learning algorithm for optimizing physical activity.  Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies 4 1–22.
  * Lin et al. (2022) Lin, J., Lee, X. Y., Jubery, T., Moothedath, S., Sarkar, S. and Ganapathysubramanian, B. (2022).  Stochastic conservative contextual linear bandits.  arXiv preprint arXiv:2203.15629 .
  * Lin and Moothedath (2022) Lin, J. and Moothedath, S. (2022).  Distributed stochastic bandit learning with context distributions.  arXiv preprint arXiv:2207.14391 .
  * Liu et al. (2014) Liu, Y.-E., Mandel, T., Brunskill, E. and Popovic, Z. (2014).  Trading off scientific knowledge and user learning with multi-armed bandits.  In EDM.
  * Nelson et al. (2022) Nelson, E., Bhattacharjya, D., Gao, T., Liu, M., Bouneffouf, D. and Poupart, P. (2022).  Linearizing contextual bandits with latent state dynamics.  In The 38th Conference on Uncertainty in Artificial Intelligence.
  * Robins et al. (2007) Robins, J., Sued, M., Lei-Gomez, Q. and Rotnitzky, A. (2007).  Comment: Performance of double-robust estimators when” inverse probability” weights are highly variable.  Statistical Science 22 544–559.
  * Russo et al. (2018) Russo, D. J., Van Roy, B., Kazerouni, A., Osband, I., Wen, Z. et al. (2018).  A tutorial on thompson sampling.  Foundations and Trends® in Machine Learning 11 1–96.
  * Sarker et al. (2017) Sarker, H., Hovsepian, K., Chatterjee, S., Nahum-Shani, I., Murphy, S. A., Spring, B., Ertin, E., Al’Absi, M., Nakajima, M. and Kumar, S. (2017).  From markers to interventions: The case of just-in-time stress intervention.  Springer.
  * Sarker et al. (2016) Sarker, H., Tyburski, M., Rahman, M. M., Hovsepian, K., Sharmin, M., Epstein, D. H., Preston, K. L., Furr-Holden, C. D., Milam, A., Nahum-Shani, I. et al. (2016).  Finding significant stress episodes in a discontinuous time series of rapidly varying mobile sensor data.  In Proceedings of the 2016 CHI conference on human factors in computing systems.
  * Sen et al. (2017) Sen, R., Shanmugam, K., Kocaoglu, M., Dimakis, A. and Shakkottai, S. (2017).  Contextual bandits with latent confounders: An nmf approach.  In Artificial Intelligence and Statistics. PMLR.
  * Shaikh et al. (2019) Shaikh, H., Modiri, A., Williams, J. J. and Rafferty, A. N. (2019).  Balancing student success and inferring personalized effects in dynamic experiments.  In EDM.
  * Trella et al. (2022) Trella, A. L., Zhang, K. W., Nahum-Shani, I., Shetty, V., Doshi-Velez, F. and Murphy, S. A. (2022).  Reward design for an online reinforcement learning algorithm supporting oral self-care.  arXiv preprint arXiv:2208.07406 .
  * Wang et al. (2017) Wang, Y.-X., Agarwal, A. and Dudık, M. (2017).  Optimal and adaptive off-policy evaluation in contextual bandits.  In International Conference on Machine Learning. PMLR.
  * Xu and Wang (2022) Xu, J. and Wang, Y.-X. (2022).  Towards agnostic feature-based dynamic pricing: Linear policies vs linear valuation with unknown noise.  In International Conference on Artificial Intelligence and Statistics. PMLR.
  * Xu et al. (2021) Xu, X., Xie, H. and Lui, J. C. (2021).  Generalized contextual bandits with latent features: Algorithms and applications.  IEEE Transactions on Neural Networks and Learning Systems .
  * Yang et al. (2020a) Yang, J., Eckles, D., Dhillon, P. and Aral, S. (2020a).  Targeting for long-term outcomes.  arXiv preprint arXiv:2010.15835 .
  * Yang and Ren (2021a) Yang, J. and Ren, S. (2021a).  Bandit learning with predicted context: Regret analysis and selective context query.  In IEEE INFOCOM 2021-IEEE Conference on Computer Communications. IEEE.
  * Yang and Ren (2021b) Yang, J. and Ren, S. (2021b).  Robust bandit learning with imperfect context.  In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35.
  * Yang et al. (2020b) Yang, L., Yang, J. and Ren, S. (2020b).  Multi-feedback bandit learning with probabilistic contexts.  In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence Main track.
  * Yao et al. (2021) Yao, J., Brunskill, E., Pan, W., Murphy, S. and Doshi-Velez, F. (2021).  Power constrained bandits.  In Machine Learning for Healthcare Conference. PMLR.
  * Yom-Tov et al. (2017) Yom-Tov, E., Feraru, G., Kozdoba, M., Mannor, S., Tennenholtz, M. and Hochberg, I. (2017).  Encouraging physical activity in patients with diabetes: intervention using a reinforcement learning system.  Journal of medical Internet research 19 e338.
  * Yun et al. (2017) Yun, S.-Y., Nam, J. H., Mo, S. and Shin, J. (2017).  Contextual multi-armed bandits under feature uncertainty.  arXiv preprint arXiv:1703.01347 .
  * Zhan et al. (2021) Zhan, R., Hadad, V., Hirshberg, D. A. and Athey, S. (2021).  Off-policy evaluation via adaptive weighting with data from contextual bandits.  In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining.
  * Zhang et al. (2021) Zhang, K., Janson, L. and Murphy, S. (2021).  Statistical inference with m-estimators on adaptively collected data.  Advances in neural information processing systems 34 7460–7471.
  * Zhou and Brunskill (2016) Zhou, L. and Brunskill, E. (2016).  Latent contextual bandits and their application to personalized recommendations for new users.  arXiv preprint arXiv:1604.06743 .

##  Appendix A Additional simulations

###  A.1 Improving early stage performance of MEB: an example

In Section 3, we mentioned that the performance of MEB in the early stage can
be improved by several potential methods. In this section, we show some
preliminary simulation results of one simple variant of MEB: Instead of always
making decisions with (2.6), in the first $T_{1}$ rounds after the pure
exploration, we use the estimator $\widehat{\bm{\theta}}_{a,me}^{(t)}$ from
(2.5) to make the decision. That is to say, for $t=T_{0}+1,\ldots,T_{1}$, we
modify line 7 of Algorithm 1 to

$\widetilde{a}_{t}\leftarrow\mathop{\mathrm{argmax}}_{a\in\\{0,1\\}}\langle\widehat{\bm{\theta}}_{a,me}^{(t)},\widetilde{\mathbf{x}}_{t}\rangle.$

It is easy to see that both the estimation and regret guarantees remain valid
as long as $T_{1}=\mathcal{O}(1)$. In fact, we can also replace (2.5) with any
estimator that achieves empirically good early-stage performance. Below, we
compare this newly proposed variant, MEB-naive-init, to the three algorithms
shown in Section 3 in terms of the early-stage empirical performance (up to
$t=10000$) under the same settings of Section 3.

Figure 2: Estimation error
($\|\widehat{\bm{\theta}}_{0}^{(t)}-\bm{\theta}_{0}^{*}\|_{2}$) and cumulative
regret of four algorithms with minimum exploration probability $p_{0}=0.1$ and
$p_{0}=0.01$ under the settings of normal and heavy-tailed errors
$(\bm{\epsilon}_{t})_{t\geq 1}$. The results are calculated from $n_{exp}=500$
independent experiments. The red, blue, green, and black line corresponds to
Thompson sampling, MEB (Algorithm 1), MEB-naive (Algorithm 1 plugged in with
the naive measurement error estimator (2.5)), and MEB-naive-init (Algorithm 1
plugged in with the naive measurement error estimator (2.5) up to time
$t=2000$, and (2.6) afterward) respectively. The solid lines indicate the mean
values, while the shaded bands represent the standard errors across the
independent experiments.

Figure 2 shows the estimation error (for $\bm{\theta}_{0}^{*}$) as well as the
cumulative regret of the four algorithms with two choices of $p_{0}$ under
different settings of $\bm{\epsilon}_{t}$ distributions. Here, in MEB-naive-
init, we use the naive estimator up to round 2000, and then continue to use
our proposed estimator (2.6) for decision-making. We can see that in all the
settings we consider here, MEB-naive-init not only decreases the estimation
error as desired, but also significantly improves the cumulative regret
performance compare to MEB due to making better decisions early in the
algorithm. This improvement is especially significant when the minimum
sampling probability, $p_{0}$, is small. After 2000 rounds, MEB-naive-init is
able to make decisions of the same quality as MEB. In practice, we can also
tune $T_{1}$, or explore other estimators when $t\leq T_{1}$ to further
improve the performance.

As mentioned in Section 3, MEB-naive-init is not the only way to boost the
early performance of MEB due to the enlarged variance caused by importance
weights. The alternative approaches (e.g. variance reduction techniques, fine-
tuning the sampling rate $(p_{0}^{(t)})_{t\geq 1}$) are left for further
investigation and are not explored in detail in this paper.

###  A.2 Results for different magnitudes of measurement error

Figure 3: Estimation error
($\|\widehat{\bm{\theta}}_{0}^{(t)}-\bm{\theta}_{0}^{*}\|_{2}$) and cumulative
regret of three algorithms with minimum exploration probability $p_{0}=0.1$
and $p_{0}=0.01$, when the error variance $\bm{\Sigma}_{e}=\bm{I}_{d}$ and
$\bm{\Sigma}_{e}=0.1\cdot\bm{I}_{d}$. The results are calculated from
$n_{exp}=500$ independent experiments. The red, green, and blue line
corresponds to Thompson sampling, MEB (Algorithm 1), and MEB-naive (MEB
plugged in with the naive estimator (2.5)) respectively. The solid lines
indicate the mean values, while the shaded bands represent the standard errors
across the independent experiments.

We provide additional simulation results under the same setting of Section 3
but with different magnitudes of the errors $\bm{\epsilon}_{t}$. Specifically,
Figure 3 shows the estimation error
($\|\widehat{\bm{\theta}}_{0}^{(t)}-\bm{\theta}_{0}^{*}\|_{2}$) as well as the
cumulative regret of Thompson sampling, MEB and MEB-naive with minimum
sampling probability $p_{0}=0.1$ and $p_{0}=0.01$ when
$\bm{\epsilon}_{t}\sim\mathcal{N}(\mathbf{0},\bm{\Sigma}_{e})$,
$\bm{\Sigma}_{e}=\bm{I}_{d}$ and $0.1\cdot\bm{I}_{d}$ (recall that in section
3, we did simulations for $\bm{\Sigma}_{e}=0.25\cdot\bm{I}_{d}$). In general,
larger $\bm{\Sigma}_{e}$ makes the problem more difficult.
$\bm{\Sigma}_{e}=\bm{I}_{d}$ and $p_{0}=0.01$ is actually a pretty extreme
case since the large variation of $\bm{\epsilon}_{t}$ and small sampling
probability will make the measurement error estimators numerically unstable
(Note that the true context
$\mathbf{x}_{t}\sim\mathcal{N}(\mathbf{1}_{d},\bm{I}_{d})$).

Despite the different levels of $\bm{\Sigma}_{e}$, we observe similar findings
as in Section 3: MEB is the only algorithm that leads to sublinear regret and
produces estimators that converge to the ground truth. Even in the extreme
case ($\bm{\Sigma}_{e}=\bm{I}_{d}$, $p_{0}=0.01$) where the estimator (2.6) is
unstable during the early stages of the algorithm, it has little impact on the
quality of the decisions, as the regret curve stops growing fast way before
the estimation error starts to stabilize. In addition, as previously
mentioned, we can also warm start MEB to boost its performance during the
early stages.

All the computational results are performed on a MacBook Pro (Apple M1 chip,
8GB Memory) and an iMac (Apple M1 chip, 8GB Memory).

##  Appendix B Example: inconsistency of the naive estimator (2.5)

######  Example B.1.

Let $d=1$, $\mathbf{x}_{\tau}\equiv 1$ for all ${\tau}$, and
$\bm{\epsilon}_{\tau}\sim\text{Unif}(-2,2)$ sampled independently. For the
reward model, let $\bm{\theta}_{0}^{*}=-1$, $\bm{\theta}_{1}^{*}=1$,
$\eta_{\tau}\sim\text{Unif}(-0.1,0.1)$ sampled independently. So in order to
maximize expected reward, we should choose action 1 if $\mathbf{x}_{\tau}$ is
positive and action 0 otherwise. Suppose the agent takes the following policy
that is stationary and non-adaptive to history:

$\pi_{\tau}(A)=\begin{cases}\frac{2}{3}1_{\\{A=1\\}}+\frac{1}{3}1_{\\{A=0\\}},\quad\text{if
}\widetilde{\mathbf{x}}_{\tau}>\rho\\\
\frac{1}{3}1_{\\{A=1\\}}+\frac{2}{3}1_{\\{A=0\\}},\quad\text{otherwise.}\end{cases}$

Here, $\rho$ is a pre-specified constant. Figure 4 (a) plots the mean and
standard deviation of $\widehat{\bm{\theta}}_{0,me}^{(t)}$ (as in (2.5)) given
100 independent experiments for each $t=1,\ldots,10000$, where
$\rho=-0.5,0,0.5$. Observe that as $t$ grows,
$\widehat{\bm{\theta}}_{0,me}^{(t)}$ converges to different limits for
different policies. In general, the limit is not equal to
$\bm{\theta}_{0}^{*}=-1$.

In contrast, Figure 4 (b) shows the mean and standard deviation of
$\widehat{\bm{\theta}}_{0}^{(t)}$ (as in (2.6)) given 100 independent
experiments under the same setting with the same three policies as in Figure 4
(a). Unlike the naive estimator (2.5), the proposed estimator (2.6) quickly
converges around the true value $-1$ for all three candidate policies.

Figure 4: Estimated value of $\bm{\theta}_{0}^{*}$ given the naive estimator
(2.5) in (a) and our proposed estimator (2.6) in (b) under different policies
under 100 independent experiments. The green, blue, and red line corresponds
to the policy with parameter $\rho=-0.5,0$, and $0.5$ respectively. The solid
lines indicate the mean values, while the shaded bands represent the standard
deviation across the independent experiments.

##  Appendix C Regret guarantees compare to the standard benchmark policy
(2.2)

In this section, we provide theoretical guarantees that by choosing other
hyperparameter values, MEB can achieve regret $\mathcal{O}(T^{2/3})$ compared
to the standard benchmark $\pi^{*}$.

######  Theorem C.1.

Under Assumptions 2.1 and 2.2, there exist constants $C$ and $C_{1}$ such that
by choosing $T_{0}=\lceil 2T^{\frac{2}{3}}\rceil$,
$p_{0}^{(t)}=t^{-\frac{1}{3}}$, for any $T$ satisfying $T\geq
C_{1}\max\\{1,(d+\log T)^{\frac{9}{4}},\big{(}\frac{d+\log
T}{\lambda_{0}\wedge\lambda_{0}^{2}}\big{)}^{\frac{9}{4}}\\}$, with
probability at least $1-\frac{16}{\sqrt{T}}$, the regret of Algorithm 1:

$\text{Regret}(T;\pi^{*})\leq
C\left\\{R_{\theta}T^{\frac{2}{3}}+\frac{R+R_{\theta}}{\lambda_{0}}T^{\frac{2}{3}}\sqrt{d+\log
T}\right\\}.$

###### Proof.

First, notice that $q_{t}=\min_{\tau\leq
t,a\in\\{0,1\\}}\pi_{\tau}(a|\widetilde{\mathbf{x}}_{t},\mathcal{H}_{\tau-1})=p_{0}^{(t)}$,
since $p_{0}^{(t)}$ is monotonically decreasing in $t$. Theorem 2.1 indicates
that, as long as

$p_{0}^{(t)}\geq\frac{C_{1}}{\lambda_{0}\wedge\lambda_{0}^{2}}\frac{d+\log
t}{t},$ (C.1)

with probability at least $1-\frac{8}{t^{2}}$, for any $a\in\\{0,1\\}$

$\|\widehat{\bm{\theta}}_{a}^{(t)}-\bm{\theta}_{a}^{*}\|_{2}\leq\frac{C(R+R_{\theta})}{\lambda_{0}}\max\left\\{\frac{d+\log
t}{t^{\frac{2}{3}}},\sqrt{\frac{d+\log t}{t^{\frac{2}{3}}}}\right\\}.$ (C.2)

At any time $t>T_{0}$, the instantaneous regret can be controlled by

$\displaystyle{\text{Regret}}_{t}^{*}$
$\displaystyle=\mathbb{E}_{a\sim\pi_{t}^{*}}\langle\bm{\theta}^{*}_{a},\widetilde{\mathbf{x}}_{t}\rangle-\mathbb{E}_{a\sim\pi_{t}}\langle\bm{\theta}^{*}_{a},\widetilde{\mathbf{x}}_{t}\rangle$
$\displaystyle=\langle\bm{\theta}^{*}_{a_{t}^{\dagger}},\widetilde{\mathbf{x}}_{t}\rangle-[(1-p_{0}^{(t)})\langle\bm{\theta}^{*}_{\widetilde{a}_{t}},\widetilde{\mathbf{x}}_{t}\rangle+p_{0}^{(t)}\langle\bm{\theta}^{*}_{1-\widetilde{a}_{t}},\widetilde{\mathbf{x}}_{t}\rangle]$
$\displaystyle=1_{\\{a_{t}^{\dagger}=\widetilde{a}_{t}\\}}p_{0}^{(t)}\langle\bm{\theta}^{*}_{a_{t}^{\dagger}}-\bm{\theta}^{*}_{1-a_{t}^{\dagger}},\widetilde{\mathbf{x}}_{t}\rangle+1_{\\{a_{t}^{\dagger}\neq\widetilde{a}_{t}\\}}(1-p_{0}^{t})\langle\bm{\theta}^{*}_{a_{t}^{\dagger}}-\bm{\theta}^{*}_{1-a_{t}^{\dagger}},\widetilde{\mathbf{x}}_{t}\rangle$
$\displaystyle\leq
2p_{0}^{(t)}R_{\theta}+1_{\\{a_{t}^{\dagger}\neq\widetilde{a}_{t}\\}}\langle\bm{\theta}^{*}_{a_{t}^{\dagger}}-\bm{\theta}^{*}_{1-a_{t}^{\dagger}},\widetilde{\mathbf{x}}_{t}\rangle.$
(C.3)

Here recall that
$a_{t}^{\dagger}:=\mathop{\mathrm{argmax}}_{a}\langle\bm{\theta}^{*}_{a},\widetilde{\mathbf{x}}_{t}\rangle$,
$\widetilde{a}_{t}:=\mathop{\mathrm{argmax}}_{a\in\\{0,1\\}}\langle\widehat{\bm{\theta}}_{a}^{(t-1)},\widetilde{\mathbf{x}}_{t}\rangle$.

Note that $a_{t}^{\dagger}\neq\widetilde{a}_{t}$ implies that

$\displaystyle\begin{cases}\langle\bm{\theta}_{a_{t}^{\dagger}}^{*},\widetilde{\mathbf{x}}_{t}\rangle\geq\langle\bm{\theta}_{1-a_{t}^{\dagger}}^{*},\widetilde{\mathbf{x}}_{t}\rangle\\\
\langle\widehat{\bm{\theta}}_{a_{t}^{\dagger}}^{(t-1)},\widetilde{\mathbf{x}}_{t}\rangle\leq\langle\widehat{\bm{\theta}}_{1-a_{t}^{\dagger}}^{(t-1)},\widetilde{\mathbf{x}}_{t}\rangle\end{cases}$

which leads to

$\displaystyle\langle\bm{\theta}_{a_{t}^{\dagger}}^{*},\widetilde{\mathbf{x}}_{t}\rangle$
$\displaystyle\geq\langle\bm{\theta}_{1-a_{t}^{\dagger}}^{*},\widetilde{\mathbf{x}}_{t}\rangle\geq\langle\widehat{\bm{\theta}}_{1-a_{t}^{\dagger}}^{(t-1)},\widetilde{\mathbf{x}}_{t}\rangle-\max_{a}\|\widehat{\bm{\theta}}_{a}^{(t-1)}-\bm{\theta}_{a}^{*}\|_{2}$
$\displaystyle\geq\langle\widehat{\bm{\theta}}_{a_{t}^{\dagger}}^{(t-1)},\widetilde{\mathbf{x}}_{t}\rangle-\max_{a}\|\widehat{\bm{\theta}}_{a}^{(t-1)}-\bm{\theta}_{a}^{*}\|_{2}\geq\langle\bm{\theta}_{a_{t}^{\dagger}}^{*},\widetilde{\mathbf{x}}_{t}\rangle-2\max_{a}\|\widehat{\bm{\theta}}_{a}^{(t-1)}-\bm{\theta}_{a}^{*}\|_{2},$

and further implies
$\left|\langle\bm{\theta}^{*}_{a_{t}^{\dagger}}-\bm{\theta}^{*}_{1-a_{t}^{\dagger}},\widetilde{\mathbf{x}}_{t}\rangle\right|\leq
2\max_{a}\|\widehat{\bm{\theta}}_{a}^{(t-1)}-\bm{\theta}_{a}^{*}\|_{2}$.

Plugging in the above to (C.3) leads to an upper bound of instantaneous regret

$\displaystyle\text{Regret}_{t}^{*}$ $\displaystyle\leq
2p_{0}^{(t)}R_{\theta}+2\max_{a}\|\widehat{\bm{\theta}}_{a}^{(t-1)}-\bm{\theta}_{a}^{*}\|_{2}$
$\displaystyle\leq\frac{2R_{\theta}}{t^{\frac{1}{3}}}+\frac{2C(R+R_{\theta})}{\lambda_{0}}\max\left\\{\frac{d+\log(t-1)}{(t-1)^{\frac{2}{3}}},\sqrt{\frac{d+\log(t-1)}{(t-1)^{\frac{2}{3}}}}\right\\}$
$\displaystyle\leq\frac{2R_{\theta}}{t^{\frac{1}{3}}}+\frac{2C(R+R_{\theta})}{\lambda_{0}}\max\left\\{\frac{d+\log
t}{(t/2)^{\frac{2}{3}}},\sqrt{\frac{d+\log t}{(t/2)^{\frac{2}{3}}}}\right\\}$
$\displaystyle\leq\frac{2R_{\theta}}{t^{\frac{1}{3}}}+\frac{4C(R+R_{\theta})}{\lambda_{0}}\max\left\\{\frac{d+\log
t}{t^{\frac{2}{3}}},\sqrt{\frac{d+\log t}{t^{\frac{2}{3}}}}\right\\}$

for $t>T_{0}$. If in addition, for all $t\geq T_{0}$,

$\frac{d+\log t}{t^{\frac{2}{3}}}\leq 1,$ (C.4)

then we further have

$\displaystyle\text{Regret}_{t}^{*}$
$\displaystyle\leq\frac{2R_{\theta}}{t^{\frac{1}{3}}}+\frac{4C(R+R_{\theta})}{\lambda_{0}}\sqrt{\frac{d+\log
t}{t^{\frac{2}{3}}}}$

for $t>T_{0}$. Meanwhile, notice that $\text{Regret}_{t}^{*}\leq 2R_{\theta}$
for any $t\leq T_{0}$. Thus, we deduce that the cumulative regret compared to
the standard benchmark:

$\displaystyle\text{Regret}(T;\pi^{*})$ $\displaystyle\leq T_{0}\cdot
2R_{\theta}+\sum_{t>2T^{\frac{2}{3}}}\left(2R_{\theta}t^{-\frac{1}{3}}+\frac{4C(R+R_{\theta})}{\lambda_{0}}t^{-\frac{1}{3}}\sqrt{d+\log
t}\right)$ $\displaystyle\leq
C_{2}\left\\{R_{\theta}T^{\frac{2}{3}}+\frac{R+R_{\theta}}{\lambda_{0}}T^{\frac{2}{3}}\sqrt{d+\log
T}\right\\}$ (C.5)

For a universal constant $C_{2}$. Finally, conditions (C.1) and (C.4) can be
guaranteed by $T\geq C_{3}\max\\{1,(d+\log
T)^{\frac{9}{4}},\big{(}\frac{d+\log
T}{\lambda_{0}\wedge\lambda_{0}^{2}}\big{)}^{\frac{9}{4}}\\}$ for some
universal constant $C_{3}$. ∎

##  Appendix D Generalization to $K\geq 2$ actions

In this section, we assume that $\mathcal{A}=\\{1,2,\ldots,K\\}$ instead of
$\\{0,1\\}$. The benchmarks (2.2) and (2.4) become

$\pi_{t}^{*}(a)=\begin{cases}1,\quad&\text{if
}a=a_{t}^{\dagger}=\mathop{\mathrm{argmax}}_{a}\langle\bm{\theta}_{a}^{*},\widetilde{\mathbf{x}}_{t}\rangle\\\
0,\quad&\text{otherwise, }\end{cases}$ (D.1)

and

$\pi_{t}^{\dagger}(a)=\begin{cases}1-(K-1)p_{0},\quad&\text{if
}a=a_{t}^{\dagger}=\mathop{\mathrm{argmax}}_{a}\langle\bm{\theta}_{a}^{*},\widetilde{\mathbf{x}}_{t}\rangle\\\
p_{0},\quad&\text{otherwise. }\end{cases}$ (D.2)

In the $K$-arm setting, we can still estimate $\bm{\theta}_{a}^{*}$ using
(2.6) for each $a\in\mathcal{A}$. Using the same proof ideas as Theorem 2.1,
we can get the following theoretical guarantees (proof omitted):

######  Theorem D.1 (Corresponds to Theorem 2.1).

For any $t\in[T]$, let
$q_{t}=\inf_{\tau\in[t],a\in\mathcal{A}}\pi_{\tau}(a|\widetilde{\mathbf{x}}_{\tau},\mathcal{H}_{\tau-1})$.
Then under Assumptions 2.1 and 2.2, there exist constants $C$ and $C_{1}$ such
that as long as
$q_{t}\geq\frac{C_{1}}{\lambda_{0}\wedge\lambda_{0}^{2}}\frac{d+\log t}{t}$,
with probability at least $1-\frac{4K}{t^{2}}$,

$\|\widehat{\bm{\theta}}_{a}^{(t)}-\bm{\theta}_{a}^{*}\|_{2}\leq\frac{C(R+R_{\theta})}{\lambda_{0}}\max\left\\{\frac{d+\log
t}{q_{t}t},\sqrt{\frac{d+\log t}{q_{t}t}}\right\\},\quad\forall
a\in\mathcal{A}.$

Algorithm 2 MEB with $K$ actions

1: Input: $(\bm{\Sigma}_{e,t})_{t\in[T]}$: covariance sequence of
$(\bm{\epsilon}_{t})_{t\in[T]}$; $(p_{0}^{(t)})_{t\in[T]}$: minimum selection
probability at each time $t$; $T_{0}$: length of pure exploration

2: for time $t=1,2,\ldots,T$ do

3: if $t\leq T_{0}$ then

4: Sample
$a_{t}\sim\pi_{t}(\cdot|\widetilde{\mathbf{x}}_{t},\mathcal{H}_{t-1})$, where
$\pi_{t}(a|\widetilde{\mathbf{x}}_{t},\mathcal{H}_{t-1})=1/K$ for all
$a\in\mathcal{A}$

5: else

6: Obtain updated estimators
$(\widehat{\bm{\theta}}_{a}^{(t-1)})_{a\in\mathcal{A}}$ from (2.6)

7:
$\widetilde{a}_{t}\leftarrow\mathop{\mathrm{argmax}}_{a\in\mathcal{A}}\langle\widehat{\bm{\theta}}_{a}^{(t-1)},\widetilde{\mathbf{x}}_{t}\rangle$

8: Sample
$a_{t}\sim\pi_{t}(\cdot|\widetilde{\mathbf{x}}_{t},\mathcal{H}_{t-1})$, where
$\pi_{t}(a|\widetilde{\mathbf{x}}_{t},\mathcal{H}_{t-1}):=\begin{cases}1-(K-1)p_{0}^{(t)},\quad\text{if
}a=\widetilde{a}_{t}\\\ p_{0}^{(t)},\quad\text{otherwise}\end{cases}$

9: end if

10: end for

MEB with $K$ actions is shown in Algorithm 2. When compared to the benchmark
(D.2), as in Theorem 2.2, we can still control its regret by the estimation
error of (2.6). See the Theorem below (The proof is only slightly different
from Theorem 2.2; We briefly list it in Appendix I.1).

######  Theorem D.2 (Corresponds to Theorem 2.2).

Given Assumption 2.1, the regret of Algorithm 2 satisfies

$\text{Regret}(T;\pi^{\dagger})\leq
2T_{0}R_{\theta}+2(1-Kp_{0})\sum_{t\in(T_{0},T]}\max_{a\in\mathcal{A}}\|\bm{\theta}_{a}^{(t-1)}-\bm{\theta}_{a}^{*}\|_{2}.$

Combining Theorems D.1 and D.2, we obtain the following corollary. Its proof
is the same as Corollary 2.1, and is thus omitted.

######  Corollary D.1 (Corresponds to Corollary 2.1).

There exist constants $C$, $C^{\prime}$ such that by choosing $T_{0}=\lceil
2\sqrt{T}\rceil$, for any $T$ satisfying $T\geq
C^{\prime}\max\\{1,\frac{d^{2}+\log^{2}(T)}{p_{0}^{2}},\frac{d^{2}+\log^{2}(T)}{\lambda_{0}^{2}(1\wedge\lambda_{0}^{2})p_{0}^{2}}\\}$,
with probability at least $1-\frac{8K}{\sqrt{T}}$, the regret of Algorithm 2:

$\text{Regret}(T;\pi^{\dagger})\leq
C\left\\{R_{\theta}\sqrt{T}+\frac{(R+R_{\theta})(1-Kp_{0})}{\lambda_{0}\sqrt{p_{0}}}\sqrt{T(d+\log
T)}\right\\}.$

Finally, compared to the benchmark (D.1), we have the following regret
guarantees (Proof in Appendix I.2).

######  Theorem D.3.

Under Assumptions 2.1 and 2.2, there exist constants $C$ and $C_{1}$ such that
by choosing $T_{0}=\lceil 2T^{\frac{2}{3}}\rceil$,
$p_{0}^{(t)}=t^{-\frac{1}{3}}$ in Algorithm 2, for any $T$ satisfying $T\geq
C_{1}\max\\{1,(d+\log T)^{\frac{9}{4}},\big{(}\frac{d+\log
T}{\lambda_{0}\wedge\lambda_{0}^{2}}\big{)}^{\frac{9}{4}}\\}$, with
probability at least $1-\frac{8K}{\sqrt{T}}$, the regret of Algorithm 2:

$\text{Regret}(T;\pi^{*})\leq
C\left\\{(K-1)R_{\theta}T^{\frac{2}{3}}+\frac{R+R_{\theta}}{\lambda_{0}}T^{\frac{2}{3}}\sqrt{d+\log
T}\right\\}.$

##  Appendix E Justification of the benchmark policy (Proof of Lemma 2.1)

We first prove (i). When
$\langle\bm{\theta}_{0}^{*}-\bm{\theta}_{1}^{*},\mathbf{x}\rangle=0$, the
result is obvious. If
$\langle\bm{\theta}_{0}^{*}-\bm{\theta}_{1}^{*},\mathbf{x}\rangle\neq 0$,
without loss of generality, we assume that
$\bm{\theta}_{0}^{*}-\bm{\theta}_{1}^{*}>0$. Then the result is a direct
consequence of the lemma below.

######  Lemma E.1.

Let $\epsilon$ be a random variable with mean 0 and a continuous symmetric
distribution around 0. For any $\mu\in\mathbb{R}$, $\mu\neq 0$, let $P_{\mu}$
and $P_{-\mu}$ denote the distribution of $\mu+\epsilon$ and $-\mu+\epsilon$
respectively. Then for any mapping $f:\mathbb{R}\rightarrow\mathbb{R}$,

$\mathbb{P}_{X\sim
P_{\mu}}(f(X)\neq\mathop{\mathrm{sign}}(\mu))+\mathbb{P}_{X\sim
P_{-\mu}}(f(X)\neq\mathop{\mathrm{sign}}(-\mu))\geq
1-\|P_{\mu}-P_{-\mu}\|_{TV},$ (E.1)

and the equality can be attained when $f(x)=\mathop{\mathrm{sign}}(x)$.

Lemma E.1 can be proved using only basic properties of the TV distance, so the
proof is omitted.

(ii) can be similarly proved by applying Lemma E.1 with $X$ corresponding to
$\langle\bm{\theta}_{0}^{*}-\bm{\theta}_{1}^{*},\widetilde{\mathbf{x}}_{t}\rangle$.

##  Appendix F Analysis of the proposed estimator (2.6)

###  F.1 Proof of Theorem 2.1

We fix some $t\in[T]$, and control
$\|\widehat{\bm{\theta}}_{a}^{(t)}-\bm{\theta}_{a}^{*}\|_{2}$ for
$a\in\\{0,1\\}$. Towards this goal, we combine analysis of the two random
terms $\widehat{\bm{\Sigma}}_{\widetilde{\mathbf{x}},a}^{(t)}$ and
$\widehat{\bm{\Sigma}}_{\widetilde{\mathbf{x}},r,a}^{(t)}$ in the lemma below.

######  Lemma F.1.

Under the same assumptions of Theorem 2.1, there exists an absolute constant
$C$ such that with probability at least $1-4/t^{2}$, both of the followings
hold:

$\displaystyle\bigg{\|}\widehat{\bm{\Sigma}}_{\widetilde{\mathbf{x}},a}^{(t)}-\frac{1}{t}\sum_{\tau\in[t]}\pi_{\tau}^{nd}(a)(\mathbf{x}_{\tau}\mathbf{x}_{\tau}^{\top}+\bm{\Sigma}_{e,\tau})\bigg{\|}_{2}\leq
C\max\left\\{\frac{d+\log t}{q_{t}t},\sqrt{\frac{d+\log t}{q_{t}t}}\right\\},$
(F.1)
$\displaystyle\bigg{\|}\widehat{\bm{\Sigma}}_{\widetilde{\mathbf{x}},r,a}^{(t)}-\bigg{(}\frac{1}{t}\sum_{\tau\in[t]}\pi_{\tau}^{nd}(a)\mathbf{x}_{\tau}\mathbf{x}_{\tau}^{\top}\bigg{)}\bm{\theta}^{*}_{a}\bigg{\|}_{2}\leq
CR\max\left\\{\frac{d+\log t}{q_{t}t},\sqrt{\frac{d+\log
t}{q_{t}t}}\right\\}.$ (F.2)

Proof of Lemma F.1 is in Section I.3.

Denote
$\bm{\Delta}_{1}=\widehat{\bm{\Sigma}}_{\widetilde{\mathbf{x}},a}^{(t)}-\frac{1}{t}\sum_{\tau\in[t]}\pi_{\tau}^{nd}(a)(\mathbf{x}_{\tau}\mathbf{x}_{\tau}^{\top}+\bm{\Sigma}_{e,\tau})$,
$\bm{\Delta}_{2}=\widehat{\bm{\Sigma}}_{\widetilde{\mathbf{x}},r,a}^{(t)}-\bigg{(}\frac{1}{t}\sum_{\tau\in[t]}\pi_{\tau}^{nd}(a)\mathbf{x}_{\tau}\mathbf{x}_{\tau}^{\top}\bigg{)}\bm{\theta}^{*}_{a}$.
Then

$\displaystyle\widehat{\bm{\theta}}_{a}^{(t)}$
$\displaystyle=\bigg{(}\widehat{\bm{\Sigma}}_{\widetilde{\mathbf{x}},a}^{(t)}-\frac{1}{t}\sum_{\tau\in[t]}\pi^{nd}_{\tau}(a)\bm{\Sigma}_{e,\tau}\bigg{)}^{-1}\cdot\widehat{\bm{\Sigma}}_{\widetilde{\mathbf{x}},r,a}^{(t)}$
$\displaystyle=\bigg{(}\frac{1}{t}\sum_{\tau\in[t]}\pi^{nd}_{\tau}(a)\mathbf{x}_{\tau}\mathbf{x}_{\tau}^{\top}+\bm{\Delta}_{1}\bigg{)}^{-1}\cdot\left[\bigg{(}\frac{1}{t}\sum_{\tau\in[t]}\pi_{\tau}^{nd}(a)\mathbf{x}_{\tau}\mathbf{x}_{\tau}^{\top}\bigg{)}\bm{\theta}^{*}_{a}+\bm{\Delta}_{2}\right]$
$\displaystyle=\bm{\theta}_{a}^{*}-\bm{J}_{1}+\bm{J}_{2},$

where

$\displaystyle\bm{J}_{1}:=\left[\frac{1}{t}\sum_{\tau\in[t]}\pi_{\tau}^{nd}(a)\mathbf{x}_{\tau}\mathbf{x}_{\tau}^{\top}+\bm{\Delta}_{1}\right]^{-1}\cdot\bm{\Delta}_{1}\bm{\theta}_{a}^{*},\quad\bm{J}_{2}:=\left[\frac{1}{t}\sum_{\tau\in[t]}\pi_{\tau}^{nd}(a)\mathbf{x}_{\tau}\mathbf{x}_{\tau}^{\top}+\bm{\Delta}_{1}\right]^{-1}\cdot\bm{\Delta}_{2}.$

It’s easy to verify that under the event where both (F.1) and (F.2) hold,
whenever

$C\max\left\\{\frac{d+\log t}{q_{t}t},\sqrt{\frac{d+\log
t}{q_{t}t}}\right\\}\leq\frac{\lambda_{0}}{2},$ (F.3)

we have

$\|\bm{J}_{1}\|_{2}\leq\frac{2CR_{\bm{\theta}}}{\lambda_{0}}\max\left\\{\frac{d+\log
t}{q_{t}t},\sqrt{\frac{d+\log t}{q_{t}t}}\right\\}$

and

$\|\bm{J}_{2}\|_{2}\leq\frac{2CR}{\lambda_{0}}\max\left\\{\frac{d+\log
t}{q_{t}t},\sqrt{\frac{d+\log t}{q_{t}t}}\right\\}.$

On the other hand, (F.3) can be ensured by
$t\geq\frac{C_{1}}{\min\\{\lambda_{0},\lambda_{0}^{2}\\}}\frac{d+\log
t}{q_{t}}$, where $C_{1}=\max\\{2C,4C^{2}\\}$. Given these guarantees, we have
with probability at least $1-4/t^{2}$,

$\|\widehat{\bm{\theta}}_{a}^{(t)}-\bm{\theta}_{a}^{*}\|_{2}\leq\|\bm{J}_{1}\|_{2}+\|\bm{J}_{2}\|_{2}\leq\frac{2C(R+R_{\bm{\theta}})}{\lambda_{0}}\max\left\\{\frac{d+\log
t}{q_{t}t},\sqrt{\frac{d+\log t}{q_{t}t}}\right\\}.$

Thus we conclude the proof.

###  F.2 Additional comments on Assumption 2.2

Following Remark 2.1, all the following examples of $\\{\mathbf{x}_{\tau}\\}$
allow the existence of $\lambda_{0}$ with $\pi_{\tau}^{nd}(a)\equiv 1/2$ given
any reasonably big $t$ with high probability:

  * •

$\\{\mathbf{x}_{\tau}\\}$ is an i.i.d. sequence satisfying
$\mathbb{E}\mathbf{x}_{\tau}\mathbf{x}_{\tau}^{\top}\succeq\lambda_{1}I_{d}$,
$\lambda_{1}>0$;

  * •

$\\{\mathbf{x}_{\tau}\\}$ is a weakly-dependent stationary time series (a
common example is the multivariate ARMA process under regularity conditions,
see e.g. Banna et al. (2016)). The stationary distribution $P$ satisfies
$\mathbb{E}_{\mathbf{x}\sim
P}\mathbf{x}\mathbf{x}^{\top}\succeq\lambda_{2}I_{d}$, $\lambda_{2}>0$;

  * •

$\\{\mathbf{x}_{\tau}\\}$ is a periodic time series such that there exists
$t_{0}\in\mathbb{N}^{+}$ which satisfies
$\frac{1}{t_{0}}\sum_{\tau\in(kt_{0}+1,(k+1)t_{0}]}\mathbf{x}_{\tau}\mathbf{x}_{\tau}^{\top}\succeq\lambda_{3}I_{d}$
a.s. $\forall k\in\mathbb{N}$.

###  F.3 Generalization to off-policy method-of-moment estimation

(2.6) can be generalized to a class of method-of-moment estimators for off-
policy learning. In this section, we delve into the general framework of off-
policy method-of-moment estimation. This framework proves valuable in
scenarios where a fully parametric model class for the reward is unavailable,
yet there is a desire to estimate certain model parameters using offline
batched bandit data.

For simplicity, we assume that $(X_{t},Y_{t}(a):a\in\mathcal{A})_{t\in[T]}$
are drawn i.i.d. from an unknown distribution $\mathcal{P}$. At each time
$t\in[T]$, the action $A_{t}$ is drawn from a policy
$\pi_{t}(\cdot|X_{t},\mathcal{H}_{t-1})$, and the agent observes only
$o_{t}=(X_{t},A_{t},Y_{t}(A_{t}))$ together with the action selection
probabilities $\pi_{t}$. Define the history up to time $t$ as
$\mathcal{H}_{t}=\\{o_{\tau}\\}_{\tau\leq t}$. For $a_{0}\in\mathcal{A}$,
we’re interested in estimating $\bm{\theta}_{a_{0}}^{*}$, a $d$-dimensional
parameter in $\mathcal{P}^{(a_{0})}$, which is the joint distribution of
$\\{X_{t},Y_{t}(a_{0})\\}$.

######  Remark F.1.

When the context is i.i.d., the problem of estimating
$\\{\bm{\theta}_{a}^{*}\\}_{a\in\mathcal{A}}$ in Section 2.3 is a special case
of this setup by taking $\widetilde{\mathbf{x}}_{t}$ as $X_{t}$ and $r_{t}$ as
$Y_{t}$.

The traditional method-of-moment estimator looks for functions
$f_{1},\ldots,f_{d}$ as well as a mapping
$\bm{\phi}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$, such that

$\bm{\theta}_{a_{0}}^{*}=\bm{\phi}\big{(}\mathbb{E}_{(X,Y)\sim\mathcal{P}^{(a_{0})}}f_{1}(X,Y),\ldots,\mathbb{E}_{(X,Y)\sim\mathcal{P}^{(a_{0})}}f_{d}(X,Y)\big{)}.$

Then, if given i.i.d. samples $(U_{t},V_{t})_{t\in[n]}$ from
$\mathcal{P}^{(a_{0})}$, the estimator takes the form

$\widehat{\bm{\theta}}_{a_{0}}=\bm{\phi}\bigg{(}\frac{1}{T}\sum_{t\in[T]}f_{1}(U_{t},V_{t}),\ldots,\frac{1}{T}\sum_{t\in[T]}f_{d}(U_{t},V_{t})\bigg{)}.$

In fact, the naive estimator (2.5) is of this form. It is clear that we cannot
use this estimator for offline batched data $\mathcal{H}_{T}$: There are no
i.i.d. samples from $\mathcal{P}^{(a_{0})}$ because of the policy
$\\{\pi_{t}\\}_{t\in[T]}$. Instead, we propose the following estimator:

$\widehat{\bm{\theta}}_{a_{0}}=\bm{\phi}\bigg{(}\frac{1}{T}\sum_{t\in[T]}W_{t}f_{1}(X_{t},Y_{t}),\ldots,\frac{1}{T}\sum_{t\in[T]}W_{t}f_{d}(X_{t},Y_{t})\bigg{)},$

where
$W_{t}=1_{\\{A_{t}=a_{0}\\}}\frac{\pi^{nd}(A_{t})}{\pi_{t}(A_{t}|X_{t},\mathcal{H}_{t-1})}$
for a data-independent probability distribution $\pi^{nd}$ on $\mathcal{A}$.
Similar to the proof of Theorem 2.1, it’s not difficult to see that
$\widehat{\bm{\theta}}_{a_{0}}$ is consistent under mild conditions. In fact,
(2.6) is a special case of this estimator when $\pi_{\tau}^{nd}$ does not
depend on $\tau$. A more detailed analysis is left for future work.

##  Appendix G Analysis of MEB

###  G.1 Proof of Theorem 2.2

At any time $t>T_{0}$, the instantaneous regret can be controlled by

$\displaystyle{\text{Regret}}_{t}$
$\displaystyle=\mathbb{E}_{a\sim\pi_{t}^{\dagger}}\langle\bm{\theta}^{*}_{a},\widetilde{\mathbf{x}}_{t}\rangle-\mathbb{E}_{a\sim\pi_{t}}\langle\bm{\theta}^{*}_{a},\widetilde{\mathbf{x}}_{t}\rangle$
$\displaystyle=[(1-p_{0})\langle\bm{\theta}^{*}_{a_{t}^{\dagger}},\widetilde{\mathbf{x}}_{t}\rangle+p_{0}\langle\bm{\theta}^{*}_{1-a_{t}^{\dagger}},\widetilde{\mathbf{x}}_{t}\rangle]-[(1-p_{0})\langle\bm{\theta}^{*}_{\widetilde{a}_{t}},\widetilde{\mathbf{x}}_{t}\rangle+p_{0}\langle\bm{\theta}^{*}_{1-\widetilde{a}_{t}},\widetilde{\mathbf{x}}_{t}\rangle]$
$\displaystyle\leq(1-2p_{0})1_{\\{a_{t}^{\dagger}\neq\widetilde{a}_{t}\\}}\left|\langle\bm{\theta}^{*}_{a_{t}^{\dagger}}-\bm{\theta}^{*}_{1-a_{t}^{\dagger}},\widetilde{\mathbf{x}}_{t}\rangle\right|.$
(G.1)

Here recall that
$a_{t}^{\dagger}:=\mathop{\mathrm{argmax}}_{a}\langle\bm{\theta}^{*}_{a},\widetilde{\mathbf{x}}_{t}\rangle$,
$\widetilde{a}_{t}:=\mathop{\mathrm{argmax}}_{a\in\\{0,1\\}}\langle\widehat{\bm{\theta}}_{a}^{(t-1)},\widetilde{\mathbf{x}}_{t}\rangle$.

Note that $a_{t}^{\dagger}\neq\widetilde{a}_{t}$ implies that

$\displaystyle\begin{cases}\langle\bm{\theta}_{a_{t}^{\dagger}}^{*},\widetilde{\mathbf{x}}_{t}\rangle\geq\langle\bm{\theta}_{1-a_{t}^{\dagger}}^{*},\widetilde{\mathbf{x}}_{t}\rangle\\\
\langle\widehat{\bm{\theta}}_{a_{t}^{\dagger}}^{(t-1)},\widetilde{\mathbf{x}}_{t}\rangle\leq\langle\widehat{\bm{\theta}}_{1-a_{t}^{\dagger}}^{(t-1)},\widetilde{\mathbf{x}}_{t}\rangle\end{cases}$

which leads to

$\displaystyle\langle\bm{\theta}_{a_{t}^{\dagger}}^{*},\widetilde{\mathbf{x}}_{t}\rangle$
$\displaystyle\geq\langle\bm{\theta}_{1-a_{t}^{\dagger}}^{*},\widetilde{\mathbf{x}}_{t}\rangle\geq\langle\widehat{\bm{\theta}}_{1-a_{t}^{\dagger}}^{(t-1)},\widetilde{\mathbf{x}}_{t}\rangle-\max_{a}\|\widehat{\bm{\theta}}_{a}^{(t-1)}-\bm{\theta}_{a}^{*}\|_{2}$
$\displaystyle\geq\langle\widehat{\bm{\theta}}_{a_{t}^{\dagger}}^{(t-1)},\widetilde{\mathbf{x}}_{t}\rangle-\max_{a}\|\widehat{\bm{\theta}}_{a}^{(t-1)}-\bm{\theta}_{a}^{*}\|_{2}\geq\langle\bm{\theta}_{a_{t}^{\dagger}}^{*},\widetilde{\mathbf{x}}_{t}\rangle-2\max_{a}\|\widehat{\bm{\theta}}_{a}^{(t-1)}-\bm{\theta}_{a}^{*}\|_{2},$

and further implies
$\left|\langle\bm{\theta}^{*}_{a_{t}^{\dagger}}-\bm{\theta}^{*}_{1-a_{t}^{\dagger}},\widetilde{\mathbf{x}}_{t}\rangle\right|\leq
2\max_{a}\|\widehat{\bm{\theta}}_{a}^{(t-1)}-\bm{\theta}_{a}^{*}\|_{2}$.

Plugging in the above to (G.1) leads to an upper bound of instantaneous regret

$\text{Regret}_{t}\leq
2(1-2p_{0})\max_{a}\|\widehat{\bm{\theta}}_{a}^{(t-1)}-\bm{\theta}_{a}^{*}\|_{2}$

for $t>T_{0}$. We conclude the proof by summing up all instantaneous regret,
and noticing that $\text{Regret}_{t}\leq 2R_{\theta}$ for any $t\leq T_{0}$.

###  G.2 Proof of Corollary 2.1

Under the assumptions of the Corollary, we first apply a union bound to
Theorem 2.1 to obtain that with probability at least $1-8/\sqrt{T}$, for all
$t\geq\max\\{\sqrt{T},\frac{C_{1}}{\min\\{\lambda_{0},\lambda_{0}^{2}\\}}\frac{d+\log
t}{p_{0}}\\}$, for all $a\in\\{0,1\\}$,

$\|\widehat{\bm{\theta}}_{a}^{(t)}-\bm{\theta}_{a}^{*}\|_{2}\leq\frac{C(R+R_{\bm{\theta}})}{\lambda_{0}}\max\left\\{\frac{d+\log
t}{p_{0}t},\sqrt{\frac{d+\log t}{p_{0}t}}\right\\}.$ (G.2)

Meanwhile, it’s easy to verify that as long as
$T\geq\max\\{10,\frac{C^{\prime}[d+\log(\sqrt{T})]^{2}}{\min\\{\lambda_{0}^{2},\lambda_{0}^{4}\\}p_{0}^{2}}\\}$
with $C^{\prime}=C_{1}^{2}$ as in Theorem 2.1, $\forall t\geq\sqrt{T}$,
$t\geq\frac{C_{1}}{\min\\{\lambda_{0},\lambda_{0}^{2}\\}}\frac{d+\log
t}{p_{0}}$. This implies that $\forall t>T_{0}$,
$t/2\geq\max\\{\sqrt{T},\frac{C_{1}}{\min\\{\lambda_{0},\lambda_{0}^{2}\\}}\frac{d+\log
t}{p_{0}}\\}$. Combining the results in Theorems 2.1 and 2.2, we obtain that
the regret of Algorithm 1

$\displaystyle\text{Regret}(T)$ $\displaystyle\leq
4R_{\theta}\lceil\sqrt{T}\rceil+2(1-2p_{0})\sum_{t>T_{0}}\frac{C(R+R_{\theta})}{\lambda_{0}}\max\left\\{\frac{d+\log(t-1)}{p_{0}(t-1)},\sqrt{\frac{d+\log(t-1)}{p_{0}(t-1)}}\right\\}$
$\displaystyle\leq
6R_{\theta}\sqrt{T}+\frac{2C(1-2p_{0})(R+R_{\theta})}{\lambda_{0}}\sum_{t>2\sqrt{T}}\max\left\\{\frac{d+\log(\frac{1}{2}t)}{p_{0}\cdot\frac{1}{2}t},\sqrt{\frac{d+\log(\frac{1}{2}t)}{p_{0}\cdot\frac{1}{2}t}}\right\\}$

Here we use the fact that the mapping $u\mapsto\frac{d+\log u}{u}$ is
monotonically decreasing on $[3,+\infty)$, and that $t-1\geq t/2\geq 3$ for
all $t>2\sqrt{T}$ due to the assumptions of Corollary 2.1. Moreover, one can
also verify that as long as
$T\geq\max\\{10,\frac{[d+\log(\sqrt{T})]^{2}}{p_{0}^{2}}\\}$, we have $\forall
t>2\sqrt{T}$, $\frac{d+\log(\frac{1}{2}t))}{p_{0}\cdot\frac{1}{2}t}\leq 1$.
Thus, we can further deduce that

$\displaystyle\text{Regret}(T)$ $\displaystyle\leq
6R_{\theta}\sqrt{T}+\frac{2C(1-2p_{0})(R+R_{\theta})}{\lambda_{0}}\sum_{t>2\sqrt{T}}\sqrt{\frac{d+\log(\frac{1}{2}t)}{p_{0}\cdot\frac{1}{2}t}}$
$\displaystyle\leq
6R_{\theta}\sqrt{T}+\frac{2\sqrt{2}C(1-2p_{0})(R+R_{\theta})}{\sqrt{p_{0}}\lambda_{0}}\left(\sqrt{d+\log\frac{1}{2}}\cdot\sum_{t>2\sqrt{T}}\sqrt{\frac{1}{t}}+\sum_{t>2\sqrt{T}}\sqrt{\frac{\log
t}{t}}\right).$ (G.3)

Meanwhile, we have

$\displaystyle\sum_{t>2\sqrt{T}}\sqrt{\frac{\log t}{t}}\leq 2\sum_{t=\lfloor
2\sqrt{T}\rfloor+1}^{T}\frac{1}{2}\frac{\log t+1}{\sqrt{t\log t}}\leq
2\int_{\lfloor
2\sqrt{T}\rfloor}^{T}\left(\frac{\mathrm{d}}{\mathrm{d}t}\sqrt{t\log
t}\right)\mathrm{d}t\leq 2\sqrt{T\log T}.$ (G.4)

Similarly one can obtain

$\sum_{t>2\sqrt{T}}\sqrt{\frac{1}{t}}\leq 2\sqrt{T}.$ (G.5)

Plug (G.4) and (G.5) into (G.3), we deduce that

$\displaystyle\text{Regret}(T)$ $\displaystyle\leq
6R_{\theta}\sqrt{T}+\frac{2\sqrt{2}C(1-2p_{0})(R+R_{\theta})}{\sqrt{p_{0}}\lambda_{0}}\left(\sqrt{d-\log
2}\cdot 2\sqrt{T}+2\sqrt{T\log T}\right)$ $\displaystyle\leq
6R_{\theta}\sqrt{T}+\frac{4\sqrt{2}C(1-2p_{0})(R+R_{\theta})}{\sqrt{p_{0}}\lambda_{0}}\sqrt{T}\left(\sqrt{d-\log
2}+\sqrt{\log T}\right),$

from which we conclude the proof.

###  G.3 MEB with infrequent model update

Algorithm 3 MEB with infrequent model update

1: Input: $\\{\bm{\Sigma}_{e,t}\\}_{t\in[T]}$: covariance sequence of
$\\{\bm{\epsilon}_{t}\\}_{t}$; $\\{p_{0}^{(t)}\\}_{t\in[T]}$: minimum
selection probability at each time $t$; ${\mathcal{S}}\subset[T]$: set of time
points to update model estimates

2: $\widehat{\bm{\theta}}_{a}\leftarrow 0$, $\forall a\in\\{0,1\\}$ $\%$
$\widehat{\bm{\theta}}_{a}$ stores the most recent updated estimate of
$\bm{\theta}_{a}^{*}$, only update if $t\in{\mathcal{S}}$

3: for time $t=1,2,\ldots,T$ do

4: if $\min_{s\in{\mathcal{S}}}s\geq t$ then

5: Sample
$a_{t}\sim\pi_{t}(\cdot|\widetilde{\mathbf{x}}_{t},\mathcal{H}_{t-1})$, where
$\pi_{t}(a|\widetilde{\mathbf{x}}_{t},\mathcal{H}_{t-1})=1/2$ for all
$a\in\\{0,1\\}$ $\%$ If the model has never been learned before, explore with
equal probability

6: continue

7: end if

8:
$\widetilde{a}_{t}\leftarrow\mathop{\mathrm{argmax}}_{a\in\\{0,1\\}}\langle\widehat{\bm{\theta}}_{a},\widetilde{\mathbf{x}}_{t}\rangle$

9: Sample
$a_{t}\sim\pi_{t}(\cdot|\widetilde{\mathbf{x}}_{t},\mathcal{H}_{t-1})$, where
$\pi_{t}(a|\widetilde{\mathbf{x}}_{t},\mathcal{H}_{t-1}):=\begin{cases}1-p_{0}^{(t)},\quad\text{if
}a=\widetilde{a}_{t}\\\ p_{0}^{(t)},\quad\text{otherwise}\end{cases}$

10: if $t\in{\mathcal{S}}$ then

11: $\widehat{\bm{\theta}}_{a}\leftarrow\widehat{\bm{\theta}}_{a}^{(t)}$ as in
(2.6)

12: end if

13: end for

As mentioned at the end of Section 2.4, in certain scenarios (e.g. when $d$ is
large), we can save computational resources by updating the estimates of
$(\bm{\theta}_{a}^{*})_{a\in\\{0,1\\}}$ less frequently. In Algorithm 3, we
propose a variant of Algorithm 1. At each time $t$, given the noisy context
$\widetilde{\mathbf{x}}_{t}$, the algorithm computes the best action
$\widetilde{a}_{t}$ according to the most recently updated estimators of
$(\bm{\theta}_{a}^{*})_{a\in\\{0,1\\}}$. Then, it samples $\widetilde{a}_{t}$
with probability $1-p_{0}^{(t)}$ and keeps an exploration probability of
$p_{0}^{(t)}$ to sample the other action. In the meantime, the agent only has
to update the estimate of $(\bm{\theta}_{a}^{*})_{a\in\\{0,1\\}}$ once in a
while to save computation power: The algorithm specifies a subset
${\mathcal{S}}\subset[T]$ and updates the estimators according to (2.6) only
when $t\in{\mathcal{S}}$.

Under mild conditions, Algorithm 3 achieves the same order of regret upper
bound as Algorithm 1, as seen from Theorem G.1 and Corollary G.1 below. They
are modified versions of Theorem 2.2 and Corollary 2.1.

######  Theorem G.1.

Let $s_{\min}:=\min_{s\in{\mathcal{S}}}s$ be the first time Algorithm 3
updates the model. Given Assumption 2.1, $\forall T_{0}\geq s_{\min}$, the
regret of Algorithm 3

$\text{Regret}(T;\pi^{\dagger})\leq
2T_{0}R_{\theta}+2(1-2p_{0})\sum\nolimits_{t\in(T_{0},T]}\max_{a\in\\{0,1\\}}\|\widehat{\bm{\theta}}_{a}^{(s_{t})}-\bm{\theta}_{a}^{*}\|_{2}.$

Here for any $t\in[T]$, $s_{t}:=\max\\{s\in{\mathcal{S}}:s<t\\}$.

######  Corollary G.1.

There exist constants $C,C^{\prime}$ such that as long as the set of model
update times ${\mathcal{S}}$ satisfies: (i) $s_{\min}\leq\sqrt{T}$; (ii)
$\forall t\in(\sqrt{T},T]$, $s_{t}=\max\\{s\in{\mathcal{S}}:s<t\\}\geq\alpha
t$ for some constant $\alpha\in(e^{-d},1)$, then for any $T$ s.t. $T\geq
C^{\prime}\max\\{1,\frac{d^{2}+\log^{2}({T})}{p_{0}^{2}},\frac{d^{2}+\log^{2}({T})}{\min\\{\lambda_{0}^{2},\lambda_{0}^{4}\\}p_{0}^{2}}\\}$,
with probability at least $1-\frac{16}{\sqrt{T}}$, the regret of Algorithm 3:
$\text{Regret}(T;\pi^{\dagger})\leq\frac{2R_{\theta}}{\alpha}\sqrt{T}+\frac{C(1-2p_{0})(R+R_{\theta})}{\lambda_{0}\sqrt{\alpha
p_{0}}}\sqrt{T({d}+{\log T})}$.

Condition (i) and (ii) essentially requires Algorithm 3 not to start learning
the model too late, and to keep updating the learned model at least at time
points with a ‘geometric’ growth rate. This covers a wide range of choices of
${\mathcal{S}}$ in practice. Two typical examples of ${\mathcal{S}}$ could be:
(1) ${\mathcal{S}}=\\{t\in[T]:t=kt_{0}\text{ for some }k\in\mathbb{N}^{+}\\}$
(the model is learned every $t_{0}$ time points routinely, where $t_{0}$ is a
constant integer); (2) If $1/\alpha\in\mathbb{N}^{+}$,
${\mathcal{S}}=\\{t\in[T]:t=(1/\alpha)^{k}\text{ for some
}k\in\mathbb{N}^{+}\\}$ (the model only needs to be learned $\mathcal{O}(\log
T)$ times to save computation).

The proof of Theorem G.1 is very similar to that of Theorem 2.2, and is thus
omitted. The proof of Corollary G.1 is only slightly different from Corollary
2.1. For completeness, we briefly list the proof in Appendix I.4.

##  Appendix H Analysis with estimated error variance

###  H.1 Proof of Theorem 2.3

Fix $t\in[T]$ such that the conditions of Theorem 2.3 hold. Fix
$a\in\\{0,1\\}$. As in Appendix F, define
$\bm{\Delta}_{1}:=\widehat{\bm{\Sigma}}_{\widetilde{\mathbf{x}},a}^{(t)}-\frac{1}{t}\sum_{\tau\in[t]}\pi_{\tau}^{nd}(a)(\mathbf{x}_{\tau}\mathbf{x}_{\tau}^{\top}+\bm{\Sigma}_{e,\tau})$,
$\bm{\Delta}_{2}:=\widehat{\bm{\Sigma}}_{\widetilde{\mathbf{x}},r,a}^{(t)}-\bigg{(}\frac{1}{t}\sum_{\tau\in[t]}\pi_{\tau}^{nd}(a)\mathbf{x}_{\tau}\mathbf{x}_{\tau}^{\top}\bigg{)}\bm{\theta}^{*}_{a}$.
We also let
$\bm{\Delta}_{3}:=-\bm{\Delta}_{t}(a)=-\frac{1}{t}\sum_{\tau\in[t]}\pi_{\tau}^{nd}(a)(\widehat{\bm{\Sigma}}_{e,\tau}-\bm{\Sigma}_{e,\tau})$.
Recall Lemma F.1: with probability at least $1-4/t^{2}$,

$\|\bm{\Delta}_{1}\|_{2}\leq C\max\left\\{\frac{d+\log
t}{q_{t}t},\sqrt{\frac{d+\log
t}{q_{t}t}}\right\\},\quad\|\bm{\Delta}_{2}\|_{2}\leq
CR\max\left\\{\frac{d+\log t}{q_{t}t},\sqrt{\frac{d+\log
t}{q_{t}t}}\right\\}.$

Meanwhile,

$\displaystyle\widetilde{\bm{\theta}}_{a}^{(t)}$
$\displaystyle=\bigg{(}\widehat{\bm{\Sigma}}_{\widetilde{\mathbf{x}},a}^{(t)}-\frac{1}{t}\sum_{\tau\in[t]}\pi^{nd}_{\tau}(a)\widehat{\bm{\Sigma}}_{e,\tau}\bigg{)}^{-1}\cdot\widehat{\bm{\Sigma}}_{\widetilde{\mathbf{x}},r,a}^{(t)}$
$\displaystyle=\bigg{(}\frac{1}{t}\sum_{\tau\in[t]}\pi^{nd}_{\tau}(a)\mathbf{x}_{\tau}\mathbf{x}_{\tau}^{\top}+\bm{\Delta}_{1}+\bm{\Delta}_{3}\bigg{)}^{-1}\cdot\left[\bigg{(}\frac{1}{t}\sum_{\tau\in[t]}\pi_{\tau}^{nd}(a)\mathbf{x}_{\tau}\mathbf{x}_{\tau}^{\top}\bigg{)}\bm{\theta}^{*}_{a}+\bm{\Delta}_{2}\right]$
$\displaystyle=\bm{\theta}_{a}^{*}-\bm{J}_{1}^{\prime}+\bm{J}_{2}^{\prime},$

where

$\displaystyle\bm{J}_{1}^{\prime}:=\bigg{[}\frac{1}{t}\sum_{\tau\in[t]}\pi_{\tau}^{nd}(a)\mathbf{x}_{\tau}\mathbf{x}_{\tau}^{\top}+\bm{\Delta}_{1}+\bm{\Delta}_{3}\bigg{]}^{-1}(\bm{\Delta}_{1}+\bm{\Delta}_{3})\bm{\theta}_{a}^{*},\thickspace\bm{J}_{2}^{\prime}:=\bigg{[}\frac{1}{t}\sum_{\tau\in[t]}\pi_{\tau}^{nd}(a)\mathbf{x}_{\tau}\mathbf{x}_{\tau}^{\top}+\bm{\Delta}_{1}+\bm{\Delta}_{3}\bigg{]}^{-1}\bm{\Delta}_{2}.$

Under the events where both (F.1) and (F.2) hold, whenever

$C\max\left\\{\frac{d+\log t}{q_{t}t},\sqrt{\frac{d+\log
t}{q_{t}t}}\right\\}\leq\frac{\lambda_{0}}{4}$ (H.1)

and $\|\bm{\Delta}_{3}\|_{2}\leq\frac{\lambda_{0}}{4}$, we have

$\|\bm{J}_{1}^{\prime}\|\leq\frac{2R_{\bm{\theta}}}{\lambda_{0}}\left(C\max\left\\{\frac{d+\log
t}{q_{t}t},\sqrt{\frac{d+\log
t}{q_{t}t}}\right\\}+\|\bm{\Delta}_{3}\|_{2}\right)$

and

$\|\bm{J}_{2}^{\prime}\|\leq\frac{2CR}{\lambda_{0}}\max\left\\{\frac{d+\log
t}{q_{t}t},\sqrt{\frac{d+\log t}{q_{t}t}}\right\\}.$

On the other hand, (H.1) can be ensured by
$t\geq\frac{C_{1}^{\prime}}{\min\\{\lambda_{0},\lambda_{0}^{2}\\}}\frac{d+\log
t}{q_{t}}$, where $C_{1}^{\prime}=\max\\{4C,16C^{2}\\}$. Given these
guarantees, we have with probability at least $1-4/t^{2}$,

$\|\widetilde{\bm{\theta}}_{a}^{(t)}-\bm{\theta}_{a}^{*}\|\leq\|\bm{J}_{1}^{\prime}\|_{2}+\|\bm{J}_{2}^{\prime}\|_{2}\leq\frac{2C(R+R_{\bm{\theta}})}{\lambda_{0}}\max\left\\{\frac{d+\log
t}{q_{t}t},\sqrt{\frac{d+\log
t}{q_{t}t}}\right\\}+\frac{2R_{\theta}}{\lambda_{0}}\|\bm{\Delta}_{t}(a)\|_{2}.$

Thus we conclude the proof.

###  H.2 Proof of Corollary 2.2

As in Appendix G.2, we first apply a union bound to Theorem 2.3 to obtain that
with probability at least $1-8/\sqrt{T}$, for all
$t\geq\max\\{\sqrt{T},\frac{C_{1}^{\prime}}{\min\\{\lambda_{0},\lambda_{0}^{2}\\}}\frac{d+\log
t}{p_{0}}\\}$, for all $a\in\\{0,1\\}$,

$\|\widetilde{\bm{\theta}}_{a}^{(t)}-\bm{\theta}_{a}^{*}\|_{2}\leq\frac{C(R+R_{\bm{\theta}})}{\lambda_{0}}\max\left\\{\frac{d+\log
t}{p_{0}t},\sqrt{\frac{d+\log
t}{p_{0}t}}\right\\}+\frac{2R_{\theta}}{\lambda_{0}}\|\bm{\Delta}_{t}(a)\|_{2}.$
(H.2)

Meanwhile, it’s easy to verify that as long as
$T\geq\max\\{10,\frac{C^{\prime\prime}[d+\log(\sqrt{T})]^{2}}{\min\\{\lambda_{0}^{2},\lambda_{0}^{4}\\}p_{0}^{2}}\\}$
with $C^{\prime\prime}=C_{1}^{\prime 2}$ as in Theorem 2.3, $\forall
t\geq\sqrt{T}$,
$t\geq\frac{C_{1}^{\prime}}{\min\\{\lambda_{0},\lambda_{0}^{2}\\}}\frac{d+\log
t}{p_{0}}$. This implies that $\forall t>T_{0}$,
$t/2\geq\max\\{\sqrt{T},\frac{C_{1}^{\prime}}{\min\\{\lambda_{0},\lambda_{0}^{2}\\}}\frac{d+\log
t}{p_{0}}\\}$. Combining the results in Theorems 2.2 and 2.3, we obtain that
the regret of Algorithm 1 with
$(\widetilde{\bm{\theta}}_{a}^{(t)})_{a\in\\{0,1\\},t\in[T]}$ as plugin
estimators:

$\displaystyle\text{Regret}(T)$ $\displaystyle\leq
4R_{\theta}\lceil\sqrt{T}\rceil+2(1-2p_{0})\sum_{t>T_{0}}\bigg{[}\frac{C(R+R_{\theta})}{\lambda_{0}}\max\bigg{\\{}\frac{d+\log(t-1)}{p_{0}(t-1)},\sqrt{\frac{d+\log(t-1)}{p_{0}(t-1)}}\bigg{\\}}$
$\displaystyle\quad+\frac{2R_{\theta}}{\lambda_{0}}\max_{a\in\\{0,1\\}}\|\bm{\Delta}_{t-1}(a)\|_{2}\bigg{]}.$

We use the same arguments as in Appendix G.2 to upper bound the first part of
the right-hand side:

$\displaystyle
4R_{\theta}\lceil\sqrt{T}\rceil+2(1-2p_{0})\sum_{t>T_{0}}\frac{C(R+R_{\theta})}{\lambda_{0}}\max\bigg{\\{}\frac{d+\log(t-1)}{p_{0}(t-1)},\sqrt{\frac{d+\log(t-1)}{p_{0}(t-1)}}\bigg{\\}}$
$\displaystyle\leq$ $\displaystyle
6R_{\theta}\sqrt{T}+\frac{4\sqrt{2}C(1-2p_{0})(R+R_{\theta})}{\sqrt{p_{0}}\lambda_{0}}\sqrt{T}\left(\sqrt{d-\log
2}+\sqrt{\log T}\right)$

given $T$ satisfies the conditions of the corollary. The proof is concluded by
plugging this into the regret upper bound above.

##  Appendix I Additional proofs

###  I.1 Proof of Theorem D.2

At any time $t>T_{0}$, the instantaneous regret can be controlled by

$\displaystyle{\text{Regret}}_{t}$
$\displaystyle=\mathbb{E}_{a\sim\pi_{t}^{\dagger}}\langle\bm{\theta}^{*}_{a},\widetilde{\mathbf{x}}_{t}\rangle-\mathbb{E}_{a\sim\pi_{t}}\langle\bm{\theta}^{*}_{a},\widetilde{\mathbf{x}}_{t}\rangle$
$\displaystyle\leq(1-Kp_{0})1_{\\{a_{t}^{\dagger}\neq\widetilde{a}_{t}\\}}\left|\langle\bm{\theta}^{*}_{a_{t}^{\dagger}}-\bm{\theta}^{*}_{\widetilde{a}_{t}},\widetilde{\mathbf{x}}_{t}\rangle\right|.$
(I.1)

Here recall that
$a_{t}^{\dagger}:=\mathop{\mathrm{argmax}}_{a}\langle\bm{\theta}^{*}_{a},\widetilde{\mathbf{x}}_{t}\rangle$,
$\widetilde{a}_{t}:=\mathop{\mathrm{argmax}}_{a\in\\{0,1\\}}\langle\widehat{\bm{\theta}}_{a}^{(t-1)},\widetilde{\mathbf{x}}_{t}\rangle$.

Note that $a_{t}^{\dagger}\neq\widetilde{a}_{t}$ implies that

$\displaystyle\begin{cases}\langle\bm{\theta}_{a_{t}^{\dagger}}^{*},\widetilde{\mathbf{x}}_{t}\rangle\geq\langle\bm{\theta}_{\widetilde{a}_{t}}^{*},\widetilde{\mathbf{x}}_{t}\rangle\\\
\langle\widehat{\bm{\theta}}_{a_{t}^{\dagger}}^{(t-1)},\widetilde{\mathbf{x}}_{t}\rangle\leq\langle\widehat{\bm{\theta}}_{\widetilde{a}_{t}}^{(t-1)},\widetilde{\mathbf{x}}_{t}\rangle\end{cases}$

which leads to

$\displaystyle\langle\bm{\theta}_{a_{t}^{\dagger}}^{*},\widetilde{\mathbf{x}}_{t}\rangle$
$\displaystyle\geq\langle\bm{\theta}_{\widetilde{a}_{t}}^{*},\widetilde{\mathbf{x}}_{t}\rangle\geq\langle\widehat{\bm{\theta}}_{\widetilde{a}_{t}}^{(t-1)},\widetilde{\mathbf{x}}_{t}\rangle-\max_{a}\|\widehat{\bm{\theta}}_{a}^{(t-1)}-\bm{\theta}_{a}^{*}\|_{2}$
$\displaystyle\geq\langle\widehat{\bm{\theta}}_{a_{t}^{\dagger}}^{(t-1)},\widetilde{\mathbf{x}}_{t}\rangle-\max_{a}\|\widehat{\bm{\theta}}_{a}^{(t-1)}-\bm{\theta}_{a}^{*}\|_{2}\geq\langle\bm{\theta}_{a_{t}^{\dagger}}^{*},\widetilde{\mathbf{x}}_{t}\rangle-2\max_{a}\|\widehat{\bm{\theta}}_{a}^{(t-1)}-\bm{\theta}_{a}^{*}\|_{2},$

and further implies
$\left|\langle\bm{\theta}^{*}_{a_{t}^{\dagger}}-\bm{\theta}^{*}_{\widetilde{a}_{t}},\widetilde{\mathbf{x}}_{t}\rangle\right|\leq
2\max_{a}\|\widehat{\bm{\theta}}_{a}^{(t-1)}-\bm{\theta}_{a}^{*}\|_{2}$.

Plugging in the above to (I.1) leads to an upper bound of instantaneous regret

$\text{Regret}_{t}\leq
2(1-Kp_{0})\max_{a}\|\widehat{\bm{\theta}}_{a}^{(t-1)}-\bm{\theta}_{a}^{*}\|_{2}$

for $t>T_{0}$. We conclude the proof by summing up all instantaneous regret,
and noticing that $\text{Regret}_{t}\leq 2R_{\theta}$ for any $t\leq T_{0}$.

###  I.2 Proof of Theorem D.3

As in the proof of Theorem C.1, we have $q_{t}=\min_{\tau\leq
t,a\in\\{0,1\\}}\pi_{\tau}(a|\widetilde{\mathbf{x}}_{t},\mathcal{H}_{\tau-1})=p_{0}^{(t)}$.
Theorem 2.1 indicates that, as long as

$p_{0}^{(t)}\geq\frac{C_{1}}{\lambda_{0}\wedge\lambda_{0}^{2}}\frac{d+\log
t}{t},$ (I.2)

with probability at least $1-\frac{4K}{t^{2}}$, for any $a\in\\{0,1\\}$

$\|\widehat{\bm{\theta}}_{a}^{(t)}-\bm{\theta}_{a}^{*}\|_{2}\leq\frac{C(R+R_{\theta})}{\lambda_{0}}\max\left\\{\frac{d+\log
t}{t^{\frac{2}{3}}},\sqrt{\frac{d+\log t}{t^{\frac{2}{3}}}}\right\\}.$ (I.3)

At any time $t>T_{0}$, the instantaneous regret can be controlled by

$\displaystyle{\text{Regret}}_{t}^{*}$
$\displaystyle=\mathbb{E}_{a\sim\pi_{t}^{*}}\langle\bm{\theta}^{*}_{a},\widetilde{\mathbf{x}}_{t}\rangle-\mathbb{E}_{a\sim\pi_{t}}\langle\bm{\theta}^{*}_{a},\widetilde{\mathbf{x}}_{t}\rangle$
$\displaystyle=\langle\bm{\theta}^{*}_{a_{t}^{\dagger}},\widetilde{\mathbf{x}}_{t}\rangle-\big{[}(1-(K-1)p_{0}^{(t)})\langle\bm{\theta}^{*}_{\widetilde{a}_{t}},\widetilde{\mathbf{x}}_{t}\rangle+\sum_{a\neq\widetilde{a}_{t}}p_{0}^{(t)}\langle\bm{\theta}^{*}_{a},\widetilde{\mathbf{x}}_{t}\rangle\big{]}$
$\displaystyle=p_{0}^{(t)}\sum_{a\neq
a_{t}^{\dagger}}\langle\bm{\theta}^{*}_{a_{t}^{\dagger}}-\bm{\theta}^{*}_{a},\widetilde{\mathbf{x}}_{t}\rangle+1_{\\{a_{t}^{\dagger}\neq\widetilde{a}_{t}\\}}(1-Kp_{0}^{(t)})\langle\bm{\theta}^{*}_{a_{t}^{\dagger}}-\bm{\theta}^{*}_{\widetilde{a}_{t}},\widetilde{\mathbf{x}}_{t}\rangle$
$\displaystyle\leq
2(K-1)p_{0}^{(t)}R_{\theta}+1_{\\{a_{t}^{\dagger}\neq\widetilde{a}_{t}\\}}\langle\bm{\theta}^{*}_{a_{t}^{\dagger}}-\bm{\theta}^{*}_{\widetilde{a}_{t}},\widetilde{\mathbf{x}}_{t}\rangle.$
(I.4)

Here recall that
$a_{t}^{\dagger}:=\mathop{\mathrm{argmax}}_{a}\langle\bm{\theta}^{*}_{a},\widetilde{\mathbf{x}}_{t}\rangle$,
$\widetilde{a}_{t}:=\mathop{\mathrm{argmax}}_{a\in\\{0,1\\}}\langle\widehat{\bm{\theta}}_{a}^{(t-1)},\widetilde{\mathbf{x}}_{t}\rangle$.

Note that $a_{t}^{\dagger}\neq\widetilde{a}_{t}$ implies that

$\displaystyle\begin{cases}\langle\bm{\theta}_{a_{t}^{\dagger}}^{*},\widetilde{\mathbf{x}}_{t}\rangle\geq\langle\bm{\theta}_{\widetilde{a}_{t}}^{*},\widetilde{\mathbf{x}}_{t}\rangle\\\
\langle\widehat{\bm{\theta}}_{a_{t}^{\dagger}}^{(t-1)},\widetilde{\mathbf{x}}_{t}\rangle\leq\langle\widehat{\bm{\theta}}_{\widetilde{a}_{t}}^{(t-1)},\widetilde{\mathbf{x}}_{t}\rangle\end{cases}$

which leads to

$\displaystyle\langle\bm{\theta}_{a_{t}^{\dagger}}^{*},\widetilde{\mathbf{x}}_{t}\rangle$
$\displaystyle\geq\langle\bm{\theta}_{\widetilde{a}_{t}}^{*},\widetilde{\mathbf{x}}_{t}\rangle\geq\langle\widehat{\bm{\theta}}_{\widetilde{a}_{t}}^{(t-1)},\widetilde{\mathbf{x}}_{t}\rangle-\max_{a}\|\widehat{\bm{\theta}}_{a}^{(t-1)}-\bm{\theta}_{a}^{*}\|_{2}$
$\displaystyle\geq\langle\widehat{\bm{\theta}}_{a_{t}^{\dagger}}^{(t-1)},\widetilde{\mathbf{x}}_{t}\rangle-\max_{a}\|\widehat{\bm{\theta}}_{a}^{(t-1)}-\bm{\theta}_{a}^{*}\|_{2}\geq\langle\bm{\theta}_{a_{t}^{\dagger}}^{*},\widetilde{\mathbf{x}}_{t}\rangle-2\max_{a}\|\widehat{\bm{\theta}}_{a}^{(t-1)}-\bm{\theta}_{a}^{*}\|_{2},$

and further implies
$\left|\langle\bm{\theta}^{*}_{a_{t}^{\dagger}}-\bm{\theta}^{*}_{\widetilde{a}_{t}},\widetilde{\mathbf{x}}_{t}\rangle\right|\leq
2\max_{a}\|\widehat{\bm{\theta}}_{a}^{(t-1)}-\bm{\theta}_{a}^{*}\|_{2}$.

Plugging in the above to (I.4) leads to an upper bound of instantaneous regret

$\displaystyle\text{Regret}_{t}^{*}$ $\displaystyle\leq
2(K-1)p_{0}^{(t)}R_{\theta}+2\max_{a}\|\widehat{\bm{\theta}}_{a}^{(t-1)}-\bm{\theta}_{a}^{*}\|_{2}$
$\displaystyle\leq\frac{2(K-1)R_{\theta}}{t^{\frac{1}{3}}}+\frac{2C(R+R_{\theta})}{\lambda_{0}}\max\left\\{\frac{d+\log(t-1)}{(t-1)^{\frac{2}{3}}},\sqrt{\frac{d+\log(t-1)}{(t-1)^{\frac{2}{3}}}}\right\\}$
$\displaystyle\leq\frac{2(K-1)R_{\theta}}{t^{\frac{1}{3}}}+\frac{2C(R+R_{\theta})}{\lambda_{0}}\max\left\\{\frac{d+\log
t}{(t/2)^{\frac{2}{3}}},\sqrt{\frac{d+\log t}{(t/2)^{\frac{2}{3}}}}\right\\}$
$\displaystyle\leq\frac{2(K-1)R_{\theta}}{t^{\frac{1}{3}}}+\frac{4C(R+R_{\theta})}{\lambda_{0}}\max\left\\{\frac{d+\log
t}{t^{\frac{2}{3}}},\sqrt{\frac{d+\log t}{t^{\frac{2}{3}}}}\right\\}$

for $t>T_{0}$. If in addition, for all $t\geq T_{0}$,

$\frac{d+\log t}{t^{\frac{2}{3}}}\leq 1,$ (I.5)

then we further have

$\displaystyle\text{Regret}_{t}^{*}$
$\displaystyle\leq\frac{2(K-1)R_{\theta}}{t^{\frac{1}{3}}}+\frac{4C(R+R_{\theta})}{\lambda_{0}}\sqrt{\frac{d+\log
t}{t^{\frac{2}{3}}}}$

for $t>T_{0}$. Meanwhile, notice that $\text{Regret}_{t}^{*}\leq 2R_{\theta}$
for any $t\leq T_{0}$. Thus, we deduce that the cumulative regret compared to
the standard benchmark:

$\displaystyle\text{Regret}(T;\pi^{*})$ $\displaystyle\leq T_{0}\cdot
2R_{\theta}+\sum_{t>2T^{\frac{2}{3}}}\left(2(K-1)R_{\theta}t^{-\frac{1}{3}}+\frac{4C(R+R_{\theta})}{\lambda_{0}}t^{-\frac{1}{3}}\sqrt{d+\log
t}\right)$ $\displaystyle\leq
C_{2}\left\\{(K-1)R_{\theta}T^{\frac{2}{3}}+\frac{R+R_{\theta}}{\lambda_{0}}T^{\frac{2}{3}}\sqrt{d+\log
T}\right\\}$ (I.6)

For a universal constant $C_{2}$. Finally, conditions (I.2) and (I.5) can be
guaranteed by $T\geq C_{3}\max\\{1,(d+\log
T)^{\frac{9}{4}},\big{(}\frac{d+\log
T}{\lambda_{0}\wedge\lambda_{0}^{2}}\big{)}^{\frac{9}{4}}\\}$ for some
universal constant $C_{3}$.

###  I.3 Proof of Lemma F.1

We first analyze $\widehat{\bm{\Sigma}}_{\widetilde{\mathbf{x}},a}^{(t)}$.
Notice that
$\widehat{\bm{\Sigma}}_{\widetilde{\mathbf{x}},a}^{(t)}=\frac{1}{t}\sum_{\tau\in[t]}\bm{V}_{\tau,a}$,
where
$\bm{V}_{\tau,a}=\frac{\pi_{\tau}^{nd}(A_{t})}{\pi_{\tau}(A_{t}|\widetilde{\mathbf{x}}_{t},\mathcal{H}_{t-1})}1_{\\{A_{t}=a\\}}\widetilde{\mathbf{x}}_{\tau}\widetilde{\mathbf{x}}_{\tau}^{\top}$.
For any fixed
$\bm{u}\in\mathbb{S}^{d-1}:=\\{\bm{u}^{\prime}\in\mathbb{R}^{d}:\|\bm{u}^{\prime}\|_{2}=1\\}$,
$(v_{\bm{u},\tau,a}:=\bm{u}^{\tau}[\bm{V}_{\tau,a}-\mathbb{E}[\bm{V}_{\tau,a}|\mathcal{H}_{\tau-1}]]\bm{u})_{\tau}$
is a martingale difference sequence. Moreover, it’s easy to verify that
$|v_{\bm{u},\tau,a}|\leq\frac{2}{q_{t}}$ and

$\displaystyle\operatorname{{\rm
Var}}(v_{\bm{u},\tau,a}|\mathcal{H}_{\tau-1})$
$\displaystyle\leq\mathbb{E}[(\bm{u}^{\top}\bm{V}_{\tau,a}\bm{u})^{2}|\mathcal{H}_{\tau-1}]=\mathbb{E}\left[\left(\frac{\pi_{\tau}^{nd}(A_{\tau})}{\pi_{\tau}(A_{\tau}|\widetilde{\mathbf{x}}_{\tau},\mathcal{H}_{\tau-1})}\right)^{2}1_{\\{A_{\tau}=a\\}}(\bm{u}^{\top}\widetilde{\mathbf{x}}\widetilde{\mathbf{x}}^{\top}\bm{u})^{2}\bigg{|}\mathcal{H}_{\tau-1}\right]$
$\displaystyle=\mathbb{E}_{\bm{\epsilon}_{\tau},A_{\tau}\sim\pi_{\tau}^{nd}(\cdot)}\left[\left(\frac{\pi_{\tau}^{nd}(A_{\tau})}{\pi_{\tau}(A_{\tau}|\widetilde{\mathbf{x}}_{\tau},\mathcal{H}_{\tau-1})}\right)1_{\\{A_{\tau}=a\\}}(\bm{u}^{\top}\widetilde{\mathbf{x}}\widetilde{\mathbf{x}}^{\top}\bm{u})^{2}\bigg{|}\mathcal{H}_{\tau-1}\right]\leq\frac{1}{q_{t}}.$

According to Freedman’s Inequality (Freedman, 1975), for any
$\gamma_{1},\gamma_{2}>0$,

$\mathbb{P}\left(\sum_{\tau\in[t]}v_{\bm{u},\tau,a}\geq\gamma_{1},\sum_{\tau\in[t]}\operatorname{{\rm
Var}}(v_{\bm{u},\tau,a}|\mathcal{H}_{\tau-1})\leq\gamma_{2}\right)\leq
e^{-\frac{\gamma_{1}^{2}}{2(\frac{2}{q_{t}}\gamma_{1}+\gamma_{2})}}.$

Set $\gamma_{2}=t/q_{t}$, and we obtain
$\mathbb{P}\left(\sum_{\tau\in[t]}v_{\bm{u},\tau,a}\geq\gamma_{1}\right)\leq
e^{-\frac{q_{t}\gamma_{1}^{2}}{2(2\gamma_{1}+t)}}$. Applying the same analysis
to $(-v_{\bm{u},\tau,a})_{\tau}$ and combining the results gives
$\mathbb{P}\left(|\sum_{\tau\in[t]}v_{\bm{u},\tau,a}|\geq\gamma_{1}\right)\leq
2e^{-\frac{q_{t}\gamma_{1}^{2}}{2(2\gamma_{1}+t)}}$.

Denote
$\bm{M}_{t}=\frac{1}{t}\sum_{\tau\in[t]}(\bm{V}_{\tau,a}-\mathbb{E}[\bm{V}_{\tau,a}|\mathcal{H}_{\tau-1}])$,
then the above means that $\forall\bm{u}\in\mathbb{S}^{d-1}$,

$\mathbb{P}\left(|\bm{u}^{\top}\bm{M}_{t}\bm{u}|\geq\frac{\gamma_{1}}{t}\right)\leq
2e^{-\frac{q_{t}\gamma_{1}^{2}}{2(2\gamma_{1}+t)}}.$ (I.7)

Let $\mathcal{N}$ be a $\frac{1}{4}$-net of $\mathbb{S}^{d-1}$,
$|\mathcal{N}|\leq 9^{d}$. $\forall\bm{u}\in\mathbb{S}^{d-1}$, find
$\bm{u}^{\prime}\in\mathcal{N}$ s.t.
$\|\bm{u}-\bm{u}^{\prime}\|_{2}\leq\frac{1}{4}$, and we have

$|\bm{u}^{\top}\bm{M}_{t}\bm{u}-\bm{u}^{\prime\top}\bm{M}_{t}\bm{u}^{\prime}|\leq|\bm{u}^{\top}\bm{M}_{t}(\bm{u}-\bm{u}^{\prime})|+|\bm{u}^{\prime\top}\bm{M}_{t}(\bm{u}-\bm{u}^{\prime})|\leq\frac{1}{2}\|\bm{M}_{t}\|_{2}.$

This implies that

$\|\bm{M}_{t}\|_{2}=\sup_{\bm{u}\in\mathbb{S}^{d-1}}|\bm{u}^{\top}\bm{M}_{t}\bm{u}|\leq\sup_{\bm{u}^{\prime}\in\mathcal{\mathcal{N}}}|\bm{u}^{\prime\top}\bm{M}_{t}\bm{u}^{\prime}|+\frac{1}{2}\|\bm{M}_{t}\|_{2},$

and thus
$\sup_{\bm{u}\in\mathcal{N}}|\bm{u}^{\top}\bm{M}_{t}\bm{u}|\geq\frac{1}{2}\|\bm{M}_{t}\|_{2}$.
Combining the above and (I.7), we obtain that for any $\gamma_{1}>0$,

$\displaystyle\mathbb{P}\left(\|\bm{M}_{t}\|_{2}\geq\frac{2\gamma_{1}}{t}\right)\leq\mathbb{P}\left(\sup_{\bm{u}\in\mathcal{N}}|\bm{u}^{\top}\bm{M}_{t}\bm{u}|\geq\frac{\gamma_{1}}{t}\right)\leq
9^{d}\cdot\mathbb{P}\left(|\bm{u}^{\top}\bm{M}_{t}\bm{u}|\geq\frac{\gamma_{1}}{t}\right)=2\cdot
9^{d}\cdot e^{-\frac{q_{t}\gamma_{1}^{2}}{2(2\gamma_{1}+t)}}.$

By choosing $\gamma_{1}=48\max\\{\frac{d+\log t}{q_{t}},\sqrt{\frac{d+\log
t}{q_{t}}}\\}$, and noticing that
$\bm{M}_{t}=\widehat{\bm{\Sigma}}_{\widetilde{\mathbf{x}},a}^{(t)}-\frac{1}{t}\sum_{\tau\in[t]}\mathbb{E}[\bm{V}_{\tau,a}|\mathcal{H}_{\tau-1}]$,
we have

$\mathbb{P}\left(\bigg{\|}\widehat{\bm{\Sigma}}_{\widetilde{\mathbf{x}},a}^{(t)}-\frac{1}{t}\sum_{\tau\in[t]}\mathbb{E}[\bm{V}_{\tau,a}|\mathcal{H}_{\tau-1}]\bigg{\|}_{2}\geq
96\max\left\\{\frac{d+\log t}{q_{t}t},\sqrt{\frac{d+\log
t}{q_{t}t}}\right\\}\right)\leq\frac{2}{t^{2}}.$ (I.8)

On the other hand, we have

$\displaystyle\mathbb{E}[\bm{V}_{\tau,a}|\mathcal{H}_{\tau-1}]$
$\displaystyle=\mathbb{E}_{\bm{\epsilon}_{\tau}}\left[\mathbb{E}_{A_{\tau}\sim\pi_{\tau}(\cdot|\widetilde{\mathbf{x}}_{\tau},\mathcal{H}_{\tau-1})}\bigg{[}\frac{\pi_{\tau}^{nd}(A_{\tau})}{\pi_{\tau}(A_{\tau}|\widetilde{\mathbf{x}}_{\tau},\mathcal{H}_{\tau-1})}1_{\\{A_{\tau}=a\\}}\widetilde{\mathbf{x}}_{\tau}\widetilde{\mathbf{x}}_{\tau}^{\top}\big{|}\bm{\epsilon}_{\tau},\mathcal{H}_{\tau-1}\bigg{]}\bigg{|}\mathcal{H}_{\tau-1}\right]$
$\displaystyle=\mathbb{E}_{\bm{\epsilon}_{\tau}}\left[\mathbb{E}_{A_{\tau}\sim\pi_{\tau}^{nd}(\cdot)}\big{[}1_{\\{A_{\tau}=a\\}}\widetilde{\mathbf{x}}_{\tau}\widetilde{\mathbf{x}}_{\tau}^{\top}\big{|}\bm{\epsilon}_{\tau},\mathcal{H}_{\tau-1}\big{]}\bigg{|}\mathcal{H}_{\tau-1}\right]$
$\displaystyle=\mathbb{E}_{\bm{\epsilon}_{\tau}}\left[\pi_{\tau}^{nd}(a)\cdot\widetilde{\mathbf{x}}_{\tau}\widetilde{\mathbf{x}}_{\tau}^{\top}\bigg{|}\mathcal{H}_{\tau-1}\right]$
$\displaystyle=\pi_{\tau}^{nd}(a)(\mathbf{x}_{\tau}\mathbf{x}_{\tau}^{\top}+\bm{\Sigma}_{e,\tau}).$
(I.9)

Here we’ve used the facts that (i) $\\{\pi_{\tau}^{nd}\\}_{\tau}$ is data-
independent; (ii) $\mathbb{E}[\bm{\epsilon}_{\tau}|\mathcal{H}_{\tau-1}]=0$,
$\operatorname{{\rm
Var}}[\bm{\epsilon}_{\tau}|\mathcal{H}_{\tau-1}]=\bm{\Sigma}_{e,\tau}$. Plug
(I.9) into (I.8), and we get

$\mathbb{P}\left(\bigg{\|}\widehat{\bm{\Sigma}}_{\widetilde{\mathbf{x}},a}^{(t)}-\frac{1}{t}\sum_{\tau\in[t]}\pi_{\tau}^{nd}(a)(\mathbf{x}_{\tau}\mathbf{x}_{\tau}^{\top}+\bm{\Sigma}_{e,\tau})\bigg{\|}_{2}\geq
96\max\left\\{\frac{d+\log t}{q_{t}t},\sqrt{\frac{d+\log
t}{q_{t}t}}\right\\}\right)\leq\frac{2}{t^{2}}.$ (I.10)

The analysis for $\widehat{\bm{\Sigma}}_{\widetilde{\mathbf{x}},r,a}^{(t)}$ is
similar. Write
$\widehat{\bm{\Sigma}}_{\widetilde{\mathbf{x}},r,a}^{(t)}=\frac{1}{t}\sum_{\tau\in[t]}\bm{Z}_{\tau,a}$,
$\bm{Z}_{\tau,a}:=\frac{\pi_{\tau}^{nd}(A_{t})}{\pi_{\tau}(A_{\tau}|\widetilde{\mathbf{x}}_{\tau},\mathcal{H}_{\tau-1})}1_{\\{A_{t}=a\\}}\widetilde{\mathbf{x}}_{t}r_{t}$.
Then for any $\bm{u}\in\mathcal{S}^{d-1}$, it’s easy to verify that
$|(\bm{Z}_{\tau,a}-\mathbb{E}[\bm{Z}_{\tau,a}|\mathcal{H}_{\tau-1}])^{\top}\bm{u}|\leq\frac{2R}{q_{t}}$,
and $\operatorname{{\rm
Var}}((\bm{Z}_{\tau,a}-\mathbb{E}[\bm{Z}_{\tau,a}|\mathcal{H}_{\tau-1}])^{\top}\bm{u})\leq\mathbb{E}[(\bm{Z}_{\tau,a}^{\top}\bm{u})^{2}|\mathcal{H}_{\tau-1}]\leq\frac{R^{2}}{q_{t}}$.
Applying Freedman’s Inequality leads to

$\mathbb{P}\left(|\bm{w}_{t}^{\top}\bm{u}|\geq\frac{\gamma_{1}}{t}\right)\leq
2e^{-\frac{q_{t}\gamma_{1}^{2}}{2(2R\gamma_{1}+R^{2}t)}},$ (I.11)

where
$\bm{w}_{t}:=\frac{1}{t}\sum_{\tau\in[t]}(\bm{Z}_{\tau,a}-\mathbb{E}[\bm{Z}_{\tau,a}|\mathcal{H}_{\tau-1}])$.

Recall that $\mathcal{N}$ is a $\frac{1}{4}$-net of $\mathbb{S}^{d-1}$,
$|\mathcal{N}|\leq 9^{d}$. $\forall\bm{u}\in\mathbb{S}^{d-1}$, find
$\bm{u}^{\prime}\in\mathbb{S}^{d-1}$ s.t. $\|\bm{u}-\bm{u}^{\prime}\|\leq
1/4$, then
$|\bm{w}_{t}^{\top}\bm{u}-\bm{w}_{t}^{\top}\bm{u}^{\prime}|\leq\frac{1}{4}\|\bm{w}_{t}\|_{2}$,
and thus

$\|\bm{w}_{t}\|_{2}=\sup_{\bm{u}\in\mathbb{S}^{d-1}}|\bm{w}_{t}^{\top}\bm{u}|\leq\sup_{\bm{u}^{\prime}\in\mathcal{N}}|\bm{w}_{t}^{\top}\bm{u}^{\prime}|+\frac{1}{4}\|\bm{w}_{t}\|_{2}$

which implies that
$\sup_{\bm{u}\in\mathcal{N}}|\bm{w}_{t}^{\top}\bm{u}|\geq\frac{3}{4}\|\bm{w}_{t}\|_{2}$.
Taking this and (I.11) into account, we derive that

$\mathbb{P}\left(\|\bm{w}_{t}\|_{2}\geq\frac{4}{3}\frac{\gamma_{1}}{t}\right)\leq\mathbb{P}\left(\sup_{\bm{u}\in\mathcal{N}}|\bm{w}_{t}^{\top}\bm{u}|\geq\frac{\gamma_{1}}{t}\right)\leq
9^{d}\cdot 2e^{-\frac{q_{t}\gamma_{1}^{2}}{2(2R\gamma_{1}+R^{2}t)}}$

By choosing $\gamma_{1}=48R\max\left\\{\frac{d+\log t}{t},\sqrt{\frac{d+\log
t}{t}}\right\\}$ and noticing that
$\bm{w}_{t}=\widehat{\bm{\Sigma}}_{\widetilde{\mathbf{x}},r,a}^{(t)}-\frac{1}{t}\sum_{\tau\in[t]}\mathbb{E}[\bm{Z}_{\tau,a}|\mathcal{H}_{\tau-1}]$,
we obtain that

$\mathbb{P}\left(\bigg{\|}\widehat{\bm{\Sigma}}_{\widetilde{\mathbf{x}},r,a}^{(t)}-\frac{1}{t}\sum_{\tau\in[t]}\mathbb{E}[\bm{Z}_{\tau,a}|\mathcal{H}_{\tau-1}]\bigg{\|}_{2}\geq
64R\max\left\\{\frac{d+\log t}{q_{t}t},\sqrt{\frac{d+\log
t}{q_{t}t}}\right\\}\right)\leq\frac{2}{t^{2}}.$ (I.12)

Finally, because

$\displaystyle\mathbb{E}[\bm{Z}_{\tau,a}|\mathcal{H}_{\tau-1}]$
$\displaystyle=\mathbb{E}_{\bm{\epsilon}_{\tau}}\left[\mathbb{E}_{A_{\tau}\sim\pi_{\tau}(\cdot|\widetilde{\mathbf{x}}_{\tau},\mathcal{H}_{\tau-1}),\eta_{\tau}}\left[\frac{\pi_{\tau}^{nd}(A_{\tau})}{\pi_{\tau}(A_{\tau}|\widetilde{\mathbf{x}}_{\tau},\mathcal{H}_{\tau-1})}1_{\\{A_{\tau}=a\\}}\widetilde{\mathbf{x}}_{\tau}r_{\tau}\big{|}\mathcal{H}_{\tau-1},\bm{\epsilon}_{\tau}\right]\bigg{|}\mathcal{H}_{\tau-1}\right]$
$\displaystyle=\mathbb{E}_{\bm{\epsilon}_{\tau}}\left[\mathbb{E}_{A_{\tau}\sim\pi_{\tau}^{nd}(\cdot),\eta_{\tau}}\left[1_{\\{A_{\tau}=a\\}}\widetilde{\mathbf{x}}_{\tau}r_{\tau}|\mathcal{H}_{\tau-1},\bm{\epsilon}_{\tau}\right]\bigg{|}\mathcal{H}_{\tau-1}\right]$
$\displaystyle=\mathbb{E}_{\bm{\epsilon}_{\tau}}\left[\mathbb{E}_{A_{\tau}\sim\pi_{\tau}^{nd}(\cdot),\eta_{\tau}}\left[1_{\\{A_{\tau}=a\\}}\widetilde{\mathbf{x}}_{\tau}(\mathbf{x}_{\tau}^{\top}\bm{\theta}^{*}_{a}+\eta_{\tau})|\mathcal{H}_{\tau-1},\bm{\epsilon}_{\tau}\right]\bigg{|}\mathcal{H}_{\tau-1}\right]$
$\displaystyle=\mathbb{E}_{\bm{\epsilon}_{\tau}}\left[\pi_{\tau}^{nd}(a)\mathbb{E}_{\eta_{\tau}}\left[\widetilde{\mathbf{x}}_{\tau}(\mathbf{x}_{\tau}^{\top}\bm{\theta}^{*}_{a}+\eta_{\tau})|\mathcal{H}_{\tau-1},\bm{\epsilon}_{\tau}\right]\bigg{|}\mathcal{H}_{\tau-1}\right]$
$\displaystyle=\pi_{\tau}^{nd}(a)\mathbb{E}_{\bm{\epsilon}_{\tau}}\left[\widetilde{\mathbf{x}}_{\tau}\mathbf{x}_{\tau}^{\top}\bm{\theta}^{*}_{a}\bigg{|}\mathcal{H}_{\tau-1}\right]=\pi_{\tau}^{nd}(a)(\mathbf{x}_{\tau}\mathbf{x}_{\tau}^{\top})\bm{\theta}^{*}_{a},$

Plug in (I.12), and we obtain

$\mathbb{P}\left(\bigg{\|}\widehat{\bm{\Sigma}}_{\widetilde{\mathbf{x}},r,a}^{(t)}-\bigg{[}\frac{1}{t}\sum_{\tau\in[t]}\pi_{\tau}^{nd}(a)\mathbf{x}_{\tau}\mathbf{x}_{\tau}^{\top}\bigg{]}\bm{\theta}^{*}_{a}\bigg{\|}_{2}\geq
64R\max\left\\{\frac{d+\log t}{q_{t}t},\sqrt{\frac{d+\log
t}{q_{t}t}}\right\\}\right)\leq\frac{2}{t^{2}}.$ (I.13)

Combining (I.13) and (I.10), we conclude the proof.

###  I.4 Proof of Corollary G.1

In Theorem G.1, choose $T_{0}=\sqrt{T}/\alpha$. Then $\forall t>T_{0}$,
$s_{t}\geq\alpha t>\sqrt{T}$. Moreover, it’s easy to verify that as long as
$T\geq\max\\{10,\frac{C^{\prime}[d+\log(\sqrt{T})]^{2}}{\min\\{\lambda_{0}^{2},\lambda_{0}^{4}\\}p_{0}^{2}}\\}$
with $C^{\prime}=C_{1}^{2}$ as in Theorem 2.1, $\forall t\geq\sqrt{T}$,
$t\geq\frac{C_{t}}{\min\\{\lambda_{0},\lambda_{0}^{2}\\}}\frac{d+\log
t}{p_{0}}$. This implies that $\forall t>T_{0}$,
$s_{t}\geq\max\\{\sqrt{T},\frac{C_{1}}{\min\\{\lambda_{0},\lambda_{0}^{2}\\}}\frac{d+\log
t}{p_{0}}\\}$. Combining the results in Theorem G.1 and Theorem 2.1, we obtain
that the regret of Algorithm 3

$\displaystyle\text{Regret}(T)$
$\displaystyle\leq\frac{2}{\alpha}R_{\theta}\sqrt{T}+2(1-2p_{0})\sum_{t>\sqrt{T}/\alpha}\frac{C(R+R_{\theta})}{\lambda_{0}}\max\left\\{\frac{d+\log
s_{t}}{p_{0}s_{t}},\sqrt{\frac{d+\log s_{t}}{p_{0}s_{t}}}\right\\}$
$\displaystyle\leq\frac{2}{\alpha}R_{\theta}\sqrt{T}+\frac{2C(1-2p_{0})(R+R_{\theta})}{\lambda_{0}}\sum_{t>\sqrt{T}/\alpha}\max\left\\{\frac{d+\log(\alpha
t)}{p_{0}\alpha t},\sqrt{\frac{d+\log(\alpha t)}{p_{0}\alpha t}}\right\\}$

Here we use the fact that the mapping $u\mapsto\frac{d+\log u}{u}$ is
monotonically decreasing on $[3,+\infty)$, and that $s_{t}\geq\alpha t>3$ for
all $t>\sqrt{T}/\alpha$ due to the assumptions in the corollary. Moreover, one
can also verify that as long as
$T\geq\max\\{10,\frac{[d+\log(\sqrt{T})]^{2}}{p_{0}^{2}}\\}$, we have $\forall
t>\sqrt{T}/\alpha$, $\frac{d+\log(\alpha t))}{p_{0}\alpha t}\leq 1$. Thus, we
can further deduce that

$\displaystyle\text{Regret}(T)$
$\displaystyle\leq\frac{2}{\alpha}R_{\theta}\sqrt{T}+\frac{2C(1-2p_{0})(R+R_{\theta})}{\lambda_{0}}\sum_{t>\sqrt{T}/\alpha}\sqrt{\frac{d+\log(\alpha
t)}{p_{0}\alpha t}}$
$\displaystyle\leq\frac{2}{\alpha}R_{\theta}\sqrt{T}+\frac{2C(1-2p_{0})(R+R_{\theta})}{\sqrt{p_{0}\alpha}\lambda_{0}}\left(\sqrt{d+\log\alpha}\cdot\sum_{t>\sqrt{T}/\alpha}\sqrt{\frac{1}{t}}+\sum_{t>\sqrt{T}/\alpha}\sqrt{\frac{\log
t}{t}}\right).$ (I.14)

Plug (G.4) and (G.5) into (I.14), we deduce that

$\displaystyle\text{Regret}(T)$
$\displaystyle\leq\frac{2}{\alpha}R_{\theta}\sqrt{T}+\frac{2C(1-2p_{0})(R+R_{\theta})}{\sqrt{p_{0}\alpha}\lambda_{0}}\left(\sqrt{d+\log\alpha}\cdot
2\sqrt{T}+2\sqrt{T\log T}\right)$
$\displaystyle\leq\frac{2}{\alpha}R_{\theta}\sqrt{T}+\frac{4C(1-2p_{0})(R+R_{\theta})}{\sqrt{p_{0}\alpha}\lambda_{0}}\sqrt{T}\left(\sqrt{d+\log\alpha}+\sqrt{\log
T}\right),$

from which we conclude the proof.