#

Analysis of Thompson Sampling for Partially Observable Contextual Multi-Armed
Bandits

Hongju Park and Mohamad Kazem Shirani Faradonbeh

###### Abstract

Contextual multi-armed bandits are classical models in reinforcement learning
for sequential decision-making associated with individual information. A
widely-used policy for bandits is Thompson Sampling, where samples from a
data-driven probabilistic belief about unknown parameters are used to select
the control actions. For this computationally fast algorithm, performance
analyses are available under full context-observations. However, little is
known for problems that contexts are not fully observed. We propose a Thompson
Sampling algorithm for partially observable contextual multi-armed bandits,
and establish theoretical performance guarantees. Technically, we show that
the regret of the presented policy scales logarithmically with time and the
number of arms, and linearly with the dimension. Further, we establish rates
of learning unknown parameters, and provide illustrative numerical analyses.

##  1 Introduction

Contextual Multi-Armed Bandits (CMAB) are canonical models in both theory and
applications of Reinforcement Learning (RL). In this setting, there is a set
of arms whose rewards depend on their multidimensional context vectors as well
as the underlying parameter that reflects the weights of each context
component. Thanks to their ability in modeling individual characteristics,
CMAB models are widely used in different areas of automation and decision-
making. For example, in personalized recommendation of news articles, CMAB
models can raise the click rate by $12.5\%$, compared to context-free bandit
algorithms [1]. In dynamic treatment of mice with skin tumours, adopting
biological factors as contexts, leads to a $50\%$ increase in life duration
[2]. CMAB can also provide a useful framework for sequential decision-making
in precision health by incorporating contexts such as location, calendar
busyness, and heart-rate [3].

The existing literature on bandit models for decision-making under uncertainty
goes back at least to the seminal work of Lai and Robbins [4] that introduces
Upper Confidence Bound (UCB) algorithm. Broadly speaking, UCB prescribes
acting based on optimism-based approximations of the unknown parameters, and
is efficient in both discrete and continuous spaces [5], [6]. Ensuing work
establish logarithmic regret bounds of UCB that hold uniformly over time [7].
The sequence of papers focusing on CMAB models and theoretical performance
guarantees of associated reinforcement learning policies continues with
showing that UCB algorithm appropriately addresses the exploitation-
exploration trade-off [8], followed by a finer analysis that improves
dependence on dimensions [5], and regret bounds for linear payoffs [9].

Another ubiquitous reinforcement learning policy that is usually faster than
UCB, yet performs equally efficient, is Thompson Sampling [10], [11]. The main
idea of Thompson Sampling is to select actions based on samples drawn from a
posterior distribution over unknown parameters [12]. The posterior is updated
by the observed rewards, and balances exploring for better options and more
accurate learning, versus exploiting the available information to maximize
earning. Theoretical analyses start by a regret bound for multi-armed bandits
[13], and continues to CMAB counterparts [14]. Moreover, Thompson Sampling has
favorable performances in continuous spaces [15] and large-scale problems
[16]. Other variants and more discussions can be found in a recent tutorial by
Russo et al. [17].

Further adaptive policies for CMAB models include greedy-type algorithms that
are efficient if the context distribution satisfies some diversity conditions
[18], [19]. Moreover, the existing literature consists of studies on non-
linear reward functions (of the contexts) under technical assumptions such as
Lipschitz continuity. That includes, near-optimal regret bounds obtained by
using partitioning techniques on the context and action space [20], and
utilizing non-parametric regression techniques for unknown non-linear reward
functions [21]. Finally, multi-agent settings and those with latent structure
of users’ reward functions are studied, as well as approaches aiming to
provide personalized recommendations for new users [22], [23], [24].

In many applications, context vectors are observed in a partial, transformed,
or noisy manner. For example, it includes situations that inquiring the entire
feature vector is too expensive, context variables correspond to physically
distant stations, data is provided by a network of sensors, or privacy
considerations restrict perfect context observations [25]. For restricted
contexts, reinforcement learning algorithms together with combinatorial search
algorithms demonstrate competitive empirical performance [26]. In presence of
known side-information about unobserved parts of the contexts, ridge
regression methods together with projections and UCB algorithms lead to
improved efficiency [27]. Another ubiquitous setting for studying control
policies under partial observations is state space model [28, 29, 30]. In this
setting, unobserved states are estimated based on output observations using
methods such as Kalman filter [31, 32, 33], and captures important
applications such as robot navigation [34, 35].

When the number of control actions is finite, CMAB models are widely used for
data-driven control. However, unlike the aforementioned frameworks with
partial observations, proper designs and comprehensive analyses of decision-
making algorithms in contextual bandits with imperfect observations are not
currently available. Accordingly, we study (a slightly modified) Thompson
Sampling reinforcement learning algorithm for CMAB models with partially
observable contexts. Note that because contexts are the main factors in
determining the optimal arm, additional learning procedures are needed to
estimate unobserved contexts, and so modifications in the algorithm are
inevitable.

Under minimal assumptions, we establish theoretical performance guarantees
showing that the regret (i.e., the cumulative decrease in rewards due to
uncertainty) scales as the logarithm of time, the logarithm of the number of
arms, and the dimension. We present an effective method for estimating
unobserved contexts based on transformed noisy outputs, and use them to form
the posterior belief about the unknown parameter, which determines the optimal
candidate arm at every time step. Furthermore, we specify the rates at which
Thompson Sampling learns the unknown parameter. To obtain the results, certain
technical tools from the theory of martingales are leveraged, and novel
methods are developed for precisely specifying the behavior of the posterior
distribution and its effect on the efficiency of the algorithm.

The remainder of this paper is organized as follows. In Section 2, we
formulate the problem and discuss preliminary results. In Section 3, we
present the reinforcement learning algorithm that utilizes Thompson Sampling
for partially observable CMAB models. Theoretical analysis of the algorithm is
provided in Section 4, followed by numerical illustrations in Section 5.
Finally, concluding remarks and future directions are discussed in Section 6.

The following notation will be used throughout this paper. For a matrix
$A\in\mathbb{C}^{p\times q}$, $A^{\top}$ denotes its transpose, and the trace
of $A$ is denoted by $\mathbf{tr}(A)$. For a vector $v\in\mathbb{C}^{d}$, we
use the Euclidean norm $||v||=(\sum_{i=1}^{d}|v_{i}|^{2})^{1/2}$, and for
matrices, we use the operator norm; $||A||=\sup_{||v||=1}||Av||$. Further,
$\overrightarrow{u}=u/||u||$ is the unit vector indicating the direction of
$u$, and $C(A)$ denotes the column space of the matrix $A$. Finally, the
sigma-field generated by random vectors $\\{X_{1},...,X_{n}\\}$ is denoted by
$\sigma(X_{1},\dots,X_{n})$.

##  2 Problem statement

We consider the following partially observed contextual multi-armed bandit
(POCMAB) problem. Suppose that a slot machine with $N$ arms is given, and each
arm $i\in\left\\{1,\cdots,N\right\\}$ has the unobserved $d$-dimensional
context $x_{i}(t)$, which is generated independently from
$N(0_{d},\Sigma_{x})$, where $\Sigma_{x}$ is the covariance matrix of
$x_{i}(t)$. These contexts determine the rewards: At each time step
$t=1,2,\dots$, the arm $a(t)$ is selected, which generates the reward
$r_{a(t)}(t)=x_{a(t)}(t)^{\top}\mu_{*}+\varepsilon_{r_{a(t)}}(t)$, where
$x_{a(t)}(t)$ is the context of the selected arm, $\mu_{*}$ is the unknown
true parameter, and $\varepsilon_{r_{a(t)}}(t)$ is the reward observation
noise with the distribution $N(0,\sigma^{2})$. The observations at time $t$
consist of the output vectors $\\{y_{i}(t)\\}_{1\leq i\leq N}$, generated
according to $y_{i}(t)=Ax_{i}(t)+\varepsilon_{y_{i}}(t)$, where
$\varepsilon_{y_{i}}(t)$ is the output observation noise that has the
distribution $N(0_{d},\Sigma_{y})$ and $\Sigma_{y}$ is the covariance matrix
of $y_{i}(t)$ given $x_{i}(t)$. Further, the matrix $A\in\mathbb{R}^{d\times
d}$ captures the relationship between the output and the context. For the ease
of presentation, we assume that $A$ is a known non-singular square matrix.

The goal is to design a reinforcement learning policy to select an arm at
every time step, such that the expected reward is maximized, based on the
information available at the time. That is, at time $t$, the goal is to find
the optimal arm $a^{*}(t)=\operatorname*{argmax}_{1\leq i\leq
N}\mathbb{E}[r_{i}(t)|y_{i}(t)]$. The data available at time $t$, based on
which we want to select $a^{*}(t)$, consists of the outputs
$\mathbf{y_{t}}=\\{y_{i}(\tau)\\}_{1\leq i\leq N,\leavevmode\nobreak\
1\leq\tau\leq t}$, the rewards of the arms selected so far
$\mathbf{r_{t-1}}=\\{r_{a(\tau)}(\tau)\\}_{1\leq\tau\leq t-1}$, and the
previously selected arms $\mathbf{a_{t-1}}=\\{a(\tau)\\}_{1\leq\tau\leq t-1}$.
Note that since the context vectors $x_{i}(t)$ are not observed, the optimal
arm $a^{*}(t)$ must be chosen according to a context estimate
$\widehat{x}_{i}(t)$, based on the observations $\\{y_{i}(t):i=1,\dots,N\\}$.
It is easy to see that it suffices to select

$\displaystyle a^{*}(t)=\underset{1\leq i\leq N}{\arg\max}\leavevmode\nobreak\
\widehat{x}_{i}(t)^{\top}\mu_{*},$ (1)

where $\widehat{x}_{i}(t)$ is the conditional expectation of $x_{i}(t)$ given
$y_{i}(t)$ (the output observation of the $i$th arm at time $t$).

Due to uncertainty about the true parameter $\mu_{*}$, a reinforcement
learning algorithm incurs a performance degradation compared to the optimal
policy that knows the true parameter $\mu_{*}$, and selects the optimal arms
$\\{a^{*}(t)\\}_{t\geq 1,}$ at every time step. Accordingly, the performance
of reinforcement learning algorithms is commonly assessed by the cumulative
decrease in rewards, which is called regret, and is defined as

$\displaystyle\mathrm{Regret}(T)$
$\displaystyle=\mathbb{E}\left[\sum_{t=1}^{T}r_{a^{*}(t)}(t)-r_{a(t)}(t)\right].$
(2)

Above $a(t)$ is the arm selected by the reinforcement learning policy under
study. In the sequel, we present the Thompson Sampling algorithm for POCMAB
models (Algorithm 1), and establish a regret bound for that based on $d,N,T$.

##  3 Reinforcement Learning Algorithm

Now, we explain a reinforcement learning algorithm that leverages Thompson
Sampling to learn to maximize the reward in the POCMAB problem above, based on
the output data at the time. At a high level, the main idea of the algorithm
is that we maximize the expected value of the reward $r_{i}(t)$ given the
output $y_{i}(t)$, because the contexts $\\{x_{i}(t)\\}_{1\leq i\leq N}$ are
not observed. To do so, using conditional expectation with respect to the
observations, the regret in (2) can be written as

$\displaystyle\mathrm{Regret}(T)=\mathbb{E}\left[\sum_{t=1}^{T}\mathbb{E}\left[\left.r_{a^{*}(t)}(t)-r_{a(t)}(t)\right|\\{y_{i}(t)\\}_{1\leq
i\leq N}\right]\right].\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ $ (3)

Note that depending on the problem understudy, technically different
definitions of regret are considered in the literature [36]. The objective of
the proposed reinforcement learning algorithm is to choose the arm $a(t)$ that
minimizes the conditional expected reward gap given the observations
$\\{y_{i}(t)\\}_{1\leq i\leq N,}$;

$\displaystyle\mathbb{E}\left[\left.\sum_{t=1}^{T}r_{a^{*}(t)}(t)-r_{a(t)}(t)\right|\\{y_{i}(t)\\}_{1\leq
i\leq N}\right],$ (4)

at each time $t$, and thereby aims to minimize the regret in (2).

Technically, to find $a(t)$ minimizing the conditional expected reward gap in
(4), we use the conditional distribution of the reward $r_{i}(t)$ given
$y_{i}(t)$, which is derived in Appendix. The conditional distribution of
$r_{i}(t)$ given $y_{i}(t)$ is

$\displaystyle N\left((Dy_{i}(t))^{\top}\mu_{*},\leavevmode\nobreak\
\mu_{*}^{\top}(A^{\top}\Sigma_{y}^{-1}A+\Sigma_{x}^{-1})^{-1}\mu_{*}+\sigma^{2}\right),$
(5)

where
$D=(A^{\top}\Sigma_{y}^{-1}A+\Sigma_{x}^{-1})^{-1}A^{\top}\Sigma_{y}^{-1}$ is
a matrix reflecting the average effect of $y_{i}(t)$ on $r_{i}(t)$. Next, let

$\displaystyle\widehat{x}_{i}(t)$ $\displaystyle=$
$\displaystyle(A^{\top}\Sigma_{y}^{-1}A+\Sigma_{x}^{-1})^{-1}A^{\top}\Sigma_{y}^{-1}y_{i}(t)=Dy_{i}(t).$
(6)

In fact, $\widehat{x}_{i}(t)$ is the conditional expectation
$\mathbb{E}[x_{i}(t)|y_{i}(t)]$. Putting (5) and (6) together, the conditional
expected reward gap in (4) can be written as

$\displaystyle\mathbb{E}\left[\left.r_{a^{*}(t)}(t)-r_{a(t)}(t)\right|\\{y_{i}(t)\\}_{1\leq
i\leq N}\right]$ $\displaystyle=$
$\displaystyle\mathbb{E}\left[\left.\mathbb{E}\left[r_{a^{*}(t)}(t)-r_{a(t)}(t)|x_{i}(t)\right]\right|\\{y_{i}(t)\\}_{1\leq
i\leq N}\right]$ (7) $\displaystyle=$
$\displaystyle\mathbb{E}\left[\left.(x_{a^{*}(t)}(t)-x_{a(t)}(t))^{\top}\mu_{*}\right|\\{y_{i}(t)\\}_{1\leq
i\leq N}\right]$ $\displaystyle=$
$\displaystyle(\widehat{x}_{a^{*}(t)}(t)-\widehat{x}_{a(t)}(t))^{\top}\mu_{*}.$

Thus, a policy is designed to choose the arm maximizing
$\widehat{x}_{i}(t)^{\top}\mu_{*}$. To ensure that the algorithm performs
enough exploration, we use the sample $\widetilde{\mu}(t)$ from the posterior
distribution

$\displaystyle N(\widehat{\mu}(t),B(t)^{-1}),$ (8)

where the posterior mean $\widehat{\mu}(t)$ and the inverse of the covariance
matrix $B(t)$ are as follows:

$\displaystyle B(t)$ $\displaystyle=$
$\displaystyle\Sigma^{-1}+\sum_{\tau=1}^{t-1}\widehat{x}_{a(\tau)}(\tau)\widehat{x}_{a(\tau)}(\tau)^{\top},$
(9) $\displaystyle\widehat{\mu}(t)$ $\displaystyle=$ $\displaystyle
B(t)^{-1}\sum_{\tau=1}^{t-1}\widehat{x}_{a(\tau)}(\tau)r_{a(\tau)}(\tau).$
(10)

Based on the estimates of the contexts and the sample $\widetilde{\mu}(t)$, we
select $a(t)$ such that

$\displaystyle a(t)=\underset{1\leq i\leq N}{\arg\max}\leavevmode\nobreak\
\widehat{x}_{i}(t)^{\top}\widetilde{\mu}(t).$ (11)

Then, we observe the reward $r_{a(t)}(t)$ of the arm $a(t)$, and update the
posterior according to

$\displaystyle B(t+1)$ $\displaystyle=$ $\displaystyle
B(t)+\widehat{x}_{a(t)}(t)\widehat{x}_{a(t)}(t)^{\top},$ (12)
$\displaystyle\widehat{\mu}(t+1)$ $\displaystyle=$ $\displaystyle
B(t+1)^{-1}(B(t)\widehat{\mu}(t)+\widehat{x}_{a(t)}(t)r_{a(t)}(t)).\>\>\>\>\leavevmode\nobreak\
\leavevmode\nobreak\ $ (13)

The initial values are $\widehat{\mu}(1)=0_{d}$ and $B(1)=\Sigma^{-1}$, where
$\Sigma$ is an arbitrary symmetric positive definite matrix.

1:Set $B(1)=\Sigma^{-1}$, $\widehat{\mu}(1)=\mathbf{0}_{d}$

2:for $t=1,2,\dots,$ do

3: for $i=1,\dots,N$ do

4: Estimate context by $\widehat{x}_{i}(t)$ in (6)

5: end for

6: Sample $\widetilde{\mu}(t)$ from $N(\widehat{\mu}(t),B(t)^{-1})$

7: Select arm $a(t)=\underset{1\leq i\leq N}{\arg\max}\leavevmode\nobreak\
\widehat{x}_{i}(t)^{\top}\widetilde{\mu}(t)$

8: Gain reward $r_{a(t)}(t)=x_{a(t)}(t)^{\top}\mu_{*}+\epsilon_{r_{a(t)}}(t)$

9: Update $B(t+1)$ and $\widehat{\mu}(t+1)$ by (12) and (13)

10:end for

Algorithm 1 : Thomson Sampling RL policy for POCMAB

The pseudo-code of Thompson sampling for POCMAB is provided in Algorithm 1. At
every time and for each arm, Algorithm 1 calculates the context estimate
$\widehat{x}_{i}(t)$ according to (6). Then, it chooses the arm $a(t)$ by
(11), based on $\widetilde{\mu}(t)$ generated from the posterior in (8), and
updates $\widehat{\mu}(t)$ and $B(t)$ according to (12) and (13). So,
Algorithm 1 selects the arm maximizing
$\widehat{x}_{i}(t)^{\top}\widetilde{\mu}(t)$ as a reliable estimate of the
unknown expected reward at time $t$.

##  4 Analysis of Algorithm 1

In this section, we provide theoretical performance guarantees for the
reinforcement learning policy in Algorithm 1, establishing that it efficiently
learns optimal decisions from the data of partial observations. In the first
result we show that Algorithm 1 learns the unknown parameter $\mu_{*}$, fast
and accurately. Then, in Theorem 2, we provide regret analysis, indicating
that the regret of Algorithm 1 scales logarithmically with both the number of
arms $N$, as well as the time of interaction with the environment $T$, and
scales linearly with the dimension $d$.

The following result shows that $\widehat{\mu}(t)$ is a consistent estimator
and its covariance matrix shrinks proportional to the inverse of the time of
interacting with the environment in Algorithm 1. Therefore, Theorem 1 provides
sample efficiency for the Thompson Sampling reinforcement learning policy for
POCMAB in Algorithm 1.

######  Theorem 1.

In Algorithm 1, let $\widehat{\mu}(t)$ be the parameter estimate at time $t$,
defined by (13). Then, we have
$\underset{t\rightarrow\infty}{\lim}\widehat{\mu}(t)=\mu_{*}$, as well as
$\mathrm{Cov}\left(\widehat{\mu}(t)\right)=O(t^{-1})$.

###### Proof.

First, for the prior $N(0_{d},\Sigma)$ of $\mu_{*}$, (9) and (10) imply that

$\displaystyle\mathbb{E}\left[\widehat{\mu}(t)\right]=\mathbb{E}\left[B(t)^{-1}\sum_{\tau=1}^{t-1}\widehat{x}_{a(\tau)}(\tau)\widehat{x}_{a(\tau)}(\tau)^{\top}\mu_{*}\right]=(I_{d}-\mathbb{E}[B(t)^{-1}]\Sigma^{-1})\mu_{*}.$
(14)

Further, let $\mathscr{F}_{t}=\sigma\left\\{\\{y_{i}(\tau)\\}_{1\leq i\leq
N,\leavevmode\nobreak\ 1\leq\tau\leq t},\\{a(\tau)\\}_{1\leq\tau\leq
t}\right\\}$ be the sigma-field generated by the sequence of all observations
and actions by time $t$. Given the sigma-field $\mathscr{F}_{t-1}$, we have

$\displaystyle\mathbb{E}\left[\widehat{\mu}(t)|\mathscr{F}_{t-1}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\left.B(t)^{-1}\sum_{\tau=1}^{t-1}\widehat{x}_{a(\tau)}(\tau)\widehat{x}_{a(\tau)}(\tau)^{\top}\mu_{*}\right|\mathscr{F}_{t-1}\right]=(I_{d}-B(t)^{-1}\Sigma^{-1})\mu_{*},$
(15)
$\displaystyle\mathrm{Cov}\left(\widehat{\mu}(t)|\mathscr{F}_{t-1}\right)$
$\displaystyle=$ $\displaystyle
B(t)^{-1}\left(\sum_{\tau=1}^{t}\mathrm{Var}\left(r_{a(\tau)}(\tau)|\mathscr{F}_{t-1}\right)\widehat{x}_{a(\tau)}(\tau)\widehat{x}_{a(\tau)}(\tau)^{\top}\right)B(t)^{-1}$
(16) $\displaystyle=$ $\displaystyle
B(t)^{-1}(B(t)-\Sigma^{-1})B(t)^{-1}\sigma^{2}_{ry},$

where
$\sigma^{2}_{ry}=\mathrm{Var}(r_{i}(t)|y_{i}(t))=\mu_{*}^{\top}(A^{\top}\Sigma_{y}^{-1}A+\Sigma_{x}^{-1})^{-1}\mu_{*}+\sigma^{2}$
is derived in Appendix. Using (14), (15) and (16), we obtain

$\displaystyle\mathrm{Cov}(\widehat{\mu}(t))$
$\displaystyle=\mathrm{Cov}(\mathbb{E}[\widehat{\mu}(t)|\mathscr{F}_{t-1}])+\mathbb{E}[\mathrm{Cov}(\widehat{\mu}(t)|\mathscr{F}_{t-1})]$
$\displaystyle=\mathbb{E}\left[B(t)^{-1}\Sigma^{-1}\mu_{*}\mu_{*}^{\top}\Sigma^{-1}B(t)^{-1}\right]-\mathbb{E}\left[B(t)^{-1}\right]\Sigma^{-1}\mu_{*}\mu_{*}^{\top}\Sigma^{-1}\mathbb{E}\left[B(t)^{-1}\right]$
$\displaystyle+\mathbb{E}\left[B(t)^{-1}\right]\sigma^{2}_{ry}-\mathbb{E}\left[B(t)^{-1}\Sigma^{-1}B(t)^{-1}\right]\sigma^{2}_{ry}.$
(17)

Next, we show that $\underset{t\rightarrow\infty}{\lim}t^{-1}B(t)$ is a
positive definite matrix. It implies that
$\mathrm{Cov}(\widehat{\mu}(t))=O(t^{-1})$, since the other terms in (17) are
$O(t^{-2})$, except $\mathbb{E}\left[B(t)^{-1}\right]\sigma^{2}_{ry}$. For
this purpose, let $S=(D\Sigma_{y}D^{\top})^{1/2}$, and define

$\displaystyle X_{t}$ $\displaystyle=$
$\displaystyle\sum_{\tau=1}^{t}\left(S^{-1}\widehat{x}_{a(\tau)}(\tau)\widehat{x}_{a(\tau)}(\tau)^{\top}S^{-1}-\mathbb{E}[S^{-1}\widehat{x}_{a(\tau)}(\tau)\widehat{x}_{a(\tau)}(\tau)^{\top}S^{-1}|\mathscr{F}_{\tau-1}]\right),$
$\displaystyle Y_{t}$ $\displaystyle=$
$\displaystyle\sum_{\tau=1}^{t}\tau^{-1}(X_{\tau}-X_{{\tau}-1}).$

Then, $X_{t}$ and $Y_{t}$ are matrix valued martingales adapted to the
filtration $\\{\mathscr{F}_{t}\\}_{t\geq 1}$. To see that, observe that the
following two equivalences

$\displaystyle\mathbb{E}\left[\left.S^{-1}\widehat{x}_{a(\tau)}(\tau)\widehat{x}_{a(\tau)}(\tau)^{\top}S^{-1}\right|\mathscr{F}_{t-1}\right]$
$\displaystyle=$ $\displaystyle
S^{-1}\widehat{x}_{a(\tau)}(\tau)\widehat{x}_{a(\tau)}(\tau)^{\top}S^{-1},$
(18)
$\displaystyle\mathbb{E}\left[\mathbb{E}\left[\left.\left.S^{-1}\widehat{x}_{a(\tau)}(\tau)\widehat{x}_{a(\tau)}(\tau)^{\top}S^{-1}\right|\mathscr{F}_{\tau-1}\right]\right|\mathscr{F}_{t-1}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\left.S^{-1}\widehat{x}_{a(\tau)}(\tau)\widehat{x}_{a(\tau)}(\tau)^{\top}S^{-1}\right|\mathscr{F}_{\tau-1}\right].$
(19)

lead to

$\displaystyle\mathbb{E}\left[X_{t}|\mathscr{F}_{t-1}\right]$ $\displaystyle=$
$\displaystyle\sum_{\tau=1}^{t}\left(\mathbb{E}\left[\left.S^{-1}\widehat{x}_{a(\tau)}(\tau)\widehat{x}_{a(\tau)}(\tau)^{\top}S^{-1}\right|\mathscr{F}_{t-1}\right]-\mathbb{E}\left[\mathbb{E}\left[\left.\left.S^{-1}\widehat{x}_{a(\tau)}(\tau)\widehat{x}_{a(\tau)}(\tau)^{\top}S^{-1}\right|\mathscr{F}_{\tau-1}\right]\right|\mathscr{F}_{t-1}\right]\right)$
(20) $\displaystyle=$
$\displaystyle\sum_{\tau=1}^{t}\left(\mathbb{E}[S^{-1}\widehat{x}_{a(\tau)}(\tau)\widehat{x}_{a(\tau)}(\tau)^{\top}S^{-1}|\mathscr{F}_{t-1}]-\mathbb{E}\left[\left.S^{-1}\widehat{x}_{a(\tau)}(\tau)\widehat{x}_{a(\tau)}(\tau)^{\top}S^{-1}\right|\mathscr{F}_{\tau-1}\right]\right)=X_{t-1},\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ $

for $\tau<t$ and

$\displaystyle\mathbb{E}\left[\left.S^{-1}\widehat{x}_{a(\tau)}(\tau)\widehat{x}_{a(\tau)}(\tau)^{\top}S^{-1}\right|\mathscr{F}_{t-1}\right]-\mathbb{E}\left[\mathbb{E}\left[\left.\left.S^{-1}\widehat{x}_{a(\tau)}(\tau)\widehat{x}_{a(\tau)}(\tau)^{\top}S^{-1}\right|\mathscr{F}_{\tau-1}\right]\right|\mathscr{F}_{t-1}\right]=0_{d\times
d},$

for $\tau=t$. Further, since
$\mathbb{E}[X_{\tau}|\mathscr{F}_{t-1}]=X_{\tau}$, for $\tau<t$, and we have
$\mathbb{E}[X_{t}|\mathscr{F}_{t-1}]-\mathbb{E}[X_{t-1}|\mathscr{F}_{t-1}]=0_{d\times
d}$, it holds that

$\displaystyle\mathbb{E}\left[Y_{t}|\mathscr{F}_{t-1}\right]=\sum_{\tau=1}^{t}\tau^{-1}\left(\mathbb{E}[X_{\tau}|\mathscr{F}_{t-1}]-\mathbb{E}[X_{{\tau}-1}|\mathscr{F}_{t-1}]\right)=\sum_{\tau=1}^{t-1}\tau^{-1}\left(X_{\tau}-X_{{\tau}-1}\right)=Y_{t-1}.$

Now, define the martingale difference sequence $Z_{t}=X_{t}-X_{t-1}$, and let
$X_{tij}$ be the $ij$th entry of $X_{t}$, to get

$\displaystyle\mathbb{E}\left[X_{tij}^{2}\right]=\mathbb{E}\left[\left(\sum_{\tau=1}^{t}Z_{\tau
ij}\right)^{2}\right]=\sum_{\tau=1}^{t}\mathbb{E}\left[Z_{\tau
ij}^{2}\right]+2\sum_{\tau_{1}<\tau_{2}}\mathbb{E}\left[Z_{\tau_{1}ij}Z_{\tau_{2}ij}\right]=\sum_{\tau=1}^{t}\mathbb{E}\left[Z_{\tau
ij}^{2}\right],$

using the fact that
$\mathbb{E}\left[Z_{\tau_{1}ij}Z_{\tau_{2}ij}\right]=\mathbb{E}\left[Z_{\tau_{1}ij}\mathbb{E}\left[\left.Z_{\tau_{2}ij}\right|\mathscr{F}_{\tau_{2}-1}\right]\right]=0$
for all $\tau_{1}<\tau_{2}$.

Using the above, we show that $Y_{t}$ is a square-integrable martingale. To
that end, since $\\{X_{t}-X_{t-1}:t\geq 1\\}$ is a martingale difference
sequence, we have

$\displaystyle\mathbb{E}\left[Y_{tij}^{2}\right]=\sum_{\tau=1}^{t}\tau^{-2}\left(\mathbb{E}\left[X_{\tau
ij}^{2}\right]-\mathbb{E}\left[X_{(\tau-1)ij}^{2}\right]\right)=\sum_{\tau=1}^{t}\tau^{-2}\mathbb{E}\left[Z_{\tau
ij}^{2}\right],$

where $X_{0}=0_{d\times d}$, and $Y_{tij}$ is the $ij$th entry of $Y_{t}$.
Since $\mathbb{E}\left[Z_{\tau
ij}^{2}\right]\leq\mathbb{E}\left[||S^{-1}\widehat{x}_{a(t)}(t)||^{4}\right]$,
for all $\tau$, $i$, and $j$, the expectation $\mathbb{E}[Y_{tij}^{2}]$ is
finite. So, by Martingale Convergence Theorem [37], the martingale $Y_{t}$
converges almost surely to a limit $Y$, such that $\mathbb{E}[|Y|]<\infty$. It
is straightforward to see that
$t^{-1}X_{t}=Y_{t}-t^{-1}\sum_{\tau=1}^{t}Y_{\tau}$. Thus, since
$\lim\limits_{t\rightarrow\infty}Y_{t}=Y$, the average of the sequence
converges to the same limit as well;
$\lim\limits_{t\rightarrow\infty}t^{-1}\sum_{\tau=1}^{t}Y_{\tau}=Y$. Thus,
$t^{-1}X_{t}$ converges to $0_{d\times d}$. To show that
$\lim_{t\rightarrow\infty}t^{-1}B(t)$ is a positive definite matrix, decompose
$X_{t}$ as follows:

$\displaystyle
X_{t}=S^{-1}(B(t)-\Sigma^{-1})S^{-1}-\sum_{\tau=1}^{t}\mathbb{E}[S^{-1}\widehat{x}_{a(\tau)}(\tau)\widehat{x}_{a(\tau)}(\tau)^{\top}S^{-1}|\mathscr{F}_{\tau-1}].$

Since $\lim_{t\rightarrow\infty}t^{-1}X_{t}=0_{d\times d}$, we have

$\displaystyle\lim_{t\rightarrow\infty}t^{-1}S^{-1}B(t)S^{-1}=\lim_{t\rightarrow\infty}t^{-1}\sum_{\tau=1}^{t}\mathbb{E}[S^{-1}\widehat{x}_{a(\tau)}(\tau)\widehat{x}_{a(\tau)}(\tau)^{\top}S^{-1}|\mathscr{F}_{\tau-1}].$
(21)

To proceed, we express the following result about the matrix
$M=\underset{t\rightarrow\infty}{\lim}\mathbb{E}[S^{-1}\widehat{x}_{a(t)}(t)\widehat{x}_{a(t)}(t)^{\top}S^{-1}|\mathscr{F}_{t-1}]$,
for which the proof is deferred to Appendix. Now, by (21), we have

$\displaystyle\underset{t\rightarrow\infty}{\lim}t^{-1}S^{-1}B(t)S^{-1}=M,$

which according to Lemma 1 is a positive definite matrix. Finally, the latter
result, together with (17), implies that

$\underset{t\rightarrow\infty}{\lim}t\mathrm{Cov}\left(\widehat{\mu}(t)\right)=\underset{t\rightarrow\infty}{\lim}t\mathbb{E}[B(t)^{-1}]\sigma^{2}_{ry}=SM^{-1}S\sigma^{2}_{ry},$

which is the desired result. $\blacksquare$

######  Lemma 1.

The matrix
$M=\underset{t\rightarrow\infty}{\lim}\mathbb{E}[S^{-1}\widehat{x}_{a(t)}(t)\widehat{x}_{a(t)}(t)^{\top}S^{-1}|\mathscr{F}_{t-1}]$
is deterministic and positive definite.

Theorem 1 establishes the square-root consistency of the parameter estimate
$\widehat{\mu}(t)$, indicating the Algorithm 1 effectively learns the unknown
true parameter $\mu_{*}$. Here, the inverse of
$\mathrm{Cov}(\widehat{\mu}(t))$ grows linearly with time $t$, only when the
smallest eigenvalue of $A^{\top}A$ is non-zero. If $A$ is singular, the
maximum eigenvalue of $\mathrm{Cov}(\widehat{\mu}(t))$ does not decrease as
$t$ becomes larger. This also affects the consistency of learning the unknown
parameter. A similar result holds for the samples $\widetilde{\mu}(t)$, as
elaborated in the following corollary, for which the details are provided in
Appendix.

######  Corollary 1.

For the samples $\\{\widetilde{\mu}(t)\\}_{t\geq 1}$ in Algorithm 1, we have

$\lim_{t\rightarrow\infty}\widetilde{\mu}(t)=\mu_{*},\>\>\>\>\>\>\>\mathrm{Cov}(\widetilde{\mu}(t))=O(t^{-1}).$

The following result provides a regret bound, and states that Algorithm 1 is
able to efficiently learn optimal arms in POCMAB.

######  Theorem 2.

For the regret of Algorithm 1, we have

$\mathrm{Regret}(T)=O\left(d\sqrt{\log N}\log T\right).$

Before proceeding towards the proof of Theorem 2, we discuss the intuition it
provides. Since the regret at time $t$ grows due to the difference between
$\mu_{*}$ and $\widetilde{\mu}(t)$, the growth rate of regret depends on the
shrinkage rate of $||\mu_{*}-\widetilde{\mu}(t)||^{2}$. According to Corollary
1, the shrinkage rate is $O(dt^{-1})$. Thus, aggregating the errors for the
time period $1\leq t\leq T$, the scaling with respect to $T$ becomes
logarithmic (see (33)), while the scaling with $d$ is linear. On the other
hand, the regret scales logarithmically _slow_ with the number of arms $N$,
because $N$ has two opposite effects. On the one hand, since $N$ is the total
number of options, the probability of choosing a sub-optimal arms increases as
$N$ grows. On the other hand, the difference between the reward of the optimal
arm and that of the chosen arm becomes smaller as $N$ grows. The consequences
of the two effects compensate each other, leading to the slow growth of the
regret with respect to $N$. As mentioned, the suggested regret bound works for
non-singular $A$. If $A$ is singular and $\mu_{*}\in
C\left(A^{\top}\right)^{\perp}$, the regret grows linearly with $T$.

###### Proof.

First, for the regret of Algorithm 1, it holds that
$\mathrm{Regret}(T)=\mathbb{E}\left[\sum_{t=1}^{T}(\widehat{x}_{a^{*}(t)}-\widehat{x}_{a(t)})^{\top}\mu_{*}\right]$,
according to (3) and (7). To proceed, we show that for an arbitrary
$\mu_{*}\in\mathbb{R}^{d}$, it holds that
$\mathbb{E}\left[\underset{\widehat{x}_{i}(t),1\leq i\leq
N}{\operatorname*{argmax}}\left\\{\widehat{x}_{i}(t)^{\top}\mu_{*}\right\\}\right]=c_{N}\overrightarrow{S\mu_{*}}$,
where the constant

$\displaystyle c_{N}=\mathbb{E}\left[\underset{1\leq i\leq
N}{\max}\\{V_{i}:V_{i}\sim N(0,1)\\}\right]$ (22)

captures the magnitude, and the unit vector $\overrightarrow{S\mu_{*}}$
indicates the direction of the expected value of the vector
$\widehat{x}_{i}(t)$ that achieves the maximum value inside the expectation.

To show the above result, define

$\displaystyle Z(\mu,N)=\underset{Z_{i},1\leq i\leq
N}{\operatorname*{argmax}}\left\\{Z_{i}^{\top}\mu\right\\},$ (23)

where $Z_{i}$ are independent standard $d$-dimensional normally distributed
random vectors. The vector $Z_{i}$ can be decomposed as
$Z_{i}=P_{\mu}Z_{i}+(I_{d}-P_{\mu})Z_{i}$, where $P_{\mu}$ is the projection
matrix onto $C(\mu)$, which is the $1$-dimensional subspace of the vectors
inline with $\mu$. Then, we have $Z(\mu,N)=\underset{\widehat{x}_{i}(t),1\leq
i\leq N}{\operatorname*{argmax}}\left\\{(P_{\mu}Z_{i}(t))^{\top}\mu\right\\}$,
because $P_{\mu}\mu=\mu$. This implies that only the first term,
$P_{\mu}Z_{i}$, affects the result of $\underset{Z_{i},1\leq i\leq
N}{\operatorname*{argmax}}\left\\{Z_{i}^{\top}\mu\right\\}$. This means that
$Z(\mu,N)$ has the same distribution as
$P_{\mu}Z(\mu,N)+(I_{d}-P_{\mu})Z_{i}$, which means

$\displaystyle Z(\mu,N)\overset{d}{=}P_{\mu}Z(\mu,N)+(I_{d}-P_{\mu})Z_{i},$
(24)

where $\overset{d}{=}$ is used to denote equality of the probability
distributions. Thus, since projection on a subspace is a linear operator, it
interchanges with expectation, and so we have

$\displaystyle\mathbb{E}[Z(\mu,N)]=\mathbb{E}\left[P_{\mu}Z(\mu,N)+(I_{d}-P_{\mu})Z_{i}\right]=P_{\mu}\mathbb{E}[Z(\mu,N)]\in
C(\mu).$ (25)

Next, we claim that $\mathbb{E}[Z(\mu,N)]=c_{N}\overrightarrow{\mu}$, where
$c_{N}$ is defined in (22), for which it is known that [38]:

$\displaystyle c_{N}=O\left(\sqrt{\log N}\right).$ (26)

Because $Z_{i}^{\top}\overrightarrow{\mu}$ has the standard normal
distribution $N(0,1)$, according to (22), we have
$\mathbb{E}\left[\underset{1\leq i\leq
N}{\max}\left\\{Z_{i}^{\top}\overrightarrow{\mu}\right\\}\right]=c_{N}$. Based
on the definition in (23), it holds that
$Z(\mu,N)^{\top}\overrightarrow{\mu}=\underset{1\leq i\leq
N}{\max}\left\\{Z_{i}^{\top}\overrightarrow{\mu}\right\\}$. Moreover, because
$\mathbb{E}[Z(\mu,N)]\in C(\mu)$ by (25), we have
$c_{N}=\mathbb{E}[Z(\mu,N)]^{\top}\overrightarrow{\mu}=||\mathbb{E}[Z(\mu,N)]||\leavevmode\nobreak\
||\overrightarrow{\mu}||=||\mathbb{E}[Z(\mu,N)]||$. Putting the above
together, we obtain

$\displaystyle\mathbb{E}[Z(\mu,N)]=c_{N}\overrightarrow{\mu}.$ (27)

Next, we apply the result in (27) to $\widehat{x}_{a^{*}(t)}(t)$ and
$\widehat{x}_{a(t)}(t)$. The definition of $Z(\mu,N)$ in (23) implies that
$S^{-1}\widehat{x}_{a^{*}(t)}(t)$ can be written as

$\underset{S^{-1}\widehat{x}_{i}(t),1\leq i\leq
N}{\operatorname*{argmax}}\left\\{(S^{-1}\widehat{x}_{i}(t))^{\top}S\mu_{*}\right\\}=Z(S\mu_{*},N).$

Similarly, it holds that

$\displaystyle
S^{-1}\widehat{x}_{a(t)}(t)=\underset{S^{-1}\widehat{x}_{i},1\leq i\leq
N}{\operatorname*{argmax}}\left\\{(S^{-1}\widehat{x}_{i}(t))^{\top}S\widetilde{\mu}(t)\right\\}=Z(S\widetilde{\mu}(t),N).$

Using (27), we can find the expected values as follows:

$\displaystyle\mathbb{E}[S^{-1}\widehat{x}_{a^{*}(t)}]$ $\displaystyle=$
$\displaystyle c_{N}\overrightarrow{S\mu_{*}},$ (28)
$\displaystyle\mathbb{E}[S^{-1}\widehat{x}_{a(t)}|\widetilde{\mu}(t)]$
$\displaystyle=$ $\displaystyle c_{N}\overrightarrow{S\widetilde{\mu}(t)}.$
(29)

Using the above equations, we have

$\displaystyle\mathbb{E}\left[\sum_{t=1}^{T}\left(S^{-1}\widehat{x}_{a^{*}(t)}(t)-S^{-1}\widehat{x}_{a(t)}(t)\right)^{\top}S\mu_{*}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\mathbb{E}\left[\left.\sum_{t=1}^{T}\left(S^{-1}\widehat{x}_{a^{*}(t)}(t)-S^{-1}\widehat{x}_{a(t)}(t)\right)^{\top}S\mu_{*}\right|\widetilde{\mu}(t)\right]\right]$
(30) $\displaystyle=$
$\displaystyle\mathbb{E}\left[\sum_{t=1}^{T}\left(c_{N}\overrightarrow{S\mu_{*}}-c_{N}\overrightarrow{S\widetilde{\mu}(t)}\right)^{\top}S\mu_{*}\right]$

for the expected gap.

Now, let $\theta_{t}$ denote the angle between $S\mu_{*}$ and
$S\widetilde{\mu}(t)$, defined as

$\displaystyle\theta_{t}=\cos^{-1}\frac{<S\mu_{*},S\widetilde{\mu}(t)>}{||S\mu_{*}||\leavevmode\nobreak\
||S\widetilde{\mu}(t)||}\leavevmode\nobreak\ \in[0,\pi].$ (31)

Since the vectors $\overrightarrow{S\mu_{*}}$ and
$\overrightarrow{S\widetilde{\mu}(t)}$ are of the same length, the angle
between $\overrightarrow{S\mu_{*}}-\overrightarrow{S\widetilde{\mu}(t)}$ and
$\overrightarrow{S\mu_{*}}$ is $(\pi-\theta_{t})/2$, which leads to
$\left|\left|\overrightarrow{S\mu_{*}}-\overrightarrow{S\widetilde{\mu}(t)}\right|\right|=2\sin(\theta_{t}/2)$.
Thus, we get

$\displaystyle\left(\overrightarrow{S\mu_{*}}-\overrightarrow{S\widetilde{\mu}(t)}\right)^{\top}S\mu_{*}$
$\displaystyle=||S\mu_{*}||\left|\left|\overrightarrow{S\mu_{*}}-\overrightarrow{S\widetilde{\mu}(t)}\right|\right|\cos\left(\frac{\pi-\theta_{t}}{2}\right)$
$\displaystyle=2||S\mu_{*}||\sin\left(\frac{\theta_{t}}{2}\right)\cos\left(\frac{\pi-\theta_{t}}{2}\right)$
$\displaystyle=2||S\mu_{*}||\sin^{2}\left(\frac{\theta_{t}}{2}\right)=2||S\mu_{*}||(1-\cos\theta_{t}).$

On the other hand, using (31), we obtain

$\displaystyle
1-\cos\theta_{t}=\frac{||S\mu_{*}-S\widetilde{\mu}(t)||^{2}-(||S\mu_{*}||-||S\widetilde{\mu}(t)||)^{2}}{2||S\mu_{*}||\leavevmode\nobreak\
||S\widetilde{\mu}(t)||}\leq\frac{||S\mu_{*}-S\widetilde{\mu}(t)||^{2}}{2||S\mu_{*}||\leavevmode\nobreak\
||S\widetilde{\mu}(t)||}.$

To proceed, define
$\eta(t)=S\widetilde{\mu}(t)-S\mu_{*}+S\mathbb{E}[B(t)^{-1}]\Sigma^{-1}\mu_{*}$,
and note that
$\mathbb{E}[\eta(t)\eta(t)^{T}]=S\mathrm{Cov}(\widetilde{\mu}(t))S$. So, it
holds that

$\displaystyle\mathbb{E}[1-\cos\theta_{t}]\leq\mathbb{E}\left[\frac{||\eta(t)-S\mathbb{E}[B(t)^{-1}]\Sigma^{-1}\mu_{*}||^{2}}{2||S\mu_{*}||\leavevmode\nobreak\
||S\widetilde{\mu}(t)||}\right]\leq\mathbb{E}\left[\frac{||\eta(t)||^{2}+||S\mathbb{E}[B(t)^{-1}]\Sigma^{-1}\mu_{*}||^{2}}{||S\mu_{*}||\leavevmode\nobreak\
||S\widetilde{\mu}(t)||}\right].$

By Corollary 1, we have

$\displaystyle\mathbb{E}[||\eta(t)||^{2}]=\mathbf{tr}\left(\mathbb{E}[\eta(t)\eta(t)^{T}]\right)=\mathbf{tr}(S\mathrm{Cov}(\widetilde{\mu}(t))S)=O(dt^{-1}).$
(32)

Accordingly, we get

$\displaystyle\mathbb{E}\left[\frac{||\eta(t)||^{2}+||S\mathbb{E}[B(t)^{-1}]\Sigma^{-1}\mu_{*}||^{2}}{||S\mu_{*}||\leavevmode\nobreak\
||S\widetilde{\mu}(t)||}\right]=O(dt^{-1}),$

because the expected value of the numerator is $O(t^{-1})$ by (32) and Theorem
1, while the denominator converges to $||S\mu_{*}||^{2}$ as
$t\rightarrow\infty$, by Corollary 1. Thus, we have

$\displaystyle\sum_{t=1}^{T}\mathbb{E}\left[\frac{||\eta(t)||^{2}+||S\mathbb{E}[B(t)^{-1}]\Sigma^{-1}\mu_{*}||^{2}}{||S\mu_{*}||\leavevmode\nobreak\
||S\widetilde{\mu}(t)||}\right]=O(d\log T).$ (33)

Putting the latter result together with (26), it yields to the desired result,
since $c_{N}$ depends only on $N$, and $||S\mu_{*}||$ is a constant:

$\displaystyle\mathrm{Regret}(T)=\sum_{t=1}^{T}c_{N}\mathbb{E}[2||S\mu_{*}||(1-\cos\theta_{t})]=O(d\sqrt{\log
N}\log T).$

$\blacksquare$

##  5 Numerical Illustrations

Figure 1: Plots of
$\mathbb{E}\left[||\widehat{\mu}(t)-\mu_{*}||/\sqrt{d}\right]$ over time for
different number of arms $N=5,10,20,50$, and different dimensions of the
contexts $d=10,30$.

Figure 2: Plots of the regret normalized by $d\log t\sqrt{\log N}$, over time
for different number of arms $N=5,10,20,50$, and the dimension of the context
$d=10,30$.

We consider cases with different numbers of arms, $N=5,\leavevmode\nobreak\
10,\leavevmode\nobreak\ 20,\leavevmode\nobreak\ 50,$ and different dimensions
of the contexts $d=10,\leavevmode\nobreak\ 30$, repeating 50 times for each
case, for every time step. We report two quantities,
$||\widehat{\mu}(t)-\mu_{*}||$ and $\mathrm{Regret}(t)$, over time, and take
averages of the quantities for 50 scenarios. The true parameter $\mu_{*}$ as
well as each row of $A$, are randomly generated. Further, we let
$\Sigma_{x}=I_{d}$, $\Sigma_{y}=I_{d}$, and $\sigma^{2}=1$.

Figure 1 depicts the average norm of the normalized errors over time. We
normalize the errors by $\sqrt{d}$, since
$\mathrm{Cov}(\widetilde{\mu}(t))=O(t^{-1})$, by Corollary 1, and so
$\mathbf{tr}(\mathrm{Cov}(\widetilde{\mu}(t)))=O(dt^{-1})$. The curves in
Figure 1 show that the errors decrease with the appropriate rates. Figure 2
illustrates the normalized regret over time. The regret is normalized by its
bound $d\log t\sqrt{\log N}$ in Theorem 1. In Figure 2, the curves show that
the normalized regret is constant over time, corroborating the regret bound in
Theorem 2.

##  6 Concluding remarks

We studied the design and analysis of a reinforcement learning policy for
partially observable contextual multi-armed bandits. First, we presented a
modified version of Thompson Sampling that leverages Bayesian methods for
balancing the exploration and the exploitation, and estimates the unobserved
contexts based on the sequence of output observations. Further, we show that
the parameter estimates converge fast to the truth, and that as time goes by,
the presented algorithm learns the unknown true parameter accurately. Finally,
we established theoretical performance guarantees showing that the regret of
the proposed algorithm scales linearly with dimension, and logarithmically
with time and the number of arms.

Extending the presented framework to similar reinforcement learning problems
is of interest, including partially observed (contextual) Markov decision
processes. Moreover, addressing the problem when the transformation matrix is
unknown, and incorporating an estimation procedure for that, is an interesting
direction for future work. Finally, settings with large-scale action spaces
and those with high-dimensional parameters constitute further topics for
future studies.

## References

  * [1] L. Li, W. Chu, J. Langford, and R. E. Schapire, “A contextual-bandit approach to personalized news article recommendation,” in _Proceedings of the 19th international conference on World wide web_ , 2010, pp. 661–670.
  * [2] A. Durand, C. Achilleos, D. Iacovides, K. Strati, G. D. Mitsis, and J. Pineau, “Contextual bandits for adapting treatment in a mouse model of de novo carcinogenesis,” in _Machine learning for healthcare conference_. PMLR, 2018, pp. 67–82.
  * [3] A. Tewari and S. A. Murphy, “From ads to interventions: Contextual bandits in mobile health,” in _Mobile Health_. Springer, 2017, pp. 495–517.
  * [4] T. L. Lai and H. Robbins, “Asymptotically efficient adaptive allocation rules,” _Advances in applied mathematics_ , vol. 6, no. 1, pp. 4–22, 1985\.
  * [5] Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári, “Improved algorithms for linear stochastic bandits,” _Advances in neural information processing systems_ , vol. 24, pp. 2312–2320, 2011.
  * [6] M. K. S. Faradonbeh, A. Tewari, and G. Michailidis, “Optimism-based adaptive regulation of linear-quadratic systems,” _IEEE Transactions on Automatic Control_ , vol. 66, no. 4, pp. 1802–1808, 2020.
  * [7] P. Auer, N. Cesa-Bianchi, and P. Fischer, “Finite-time analysis of the multiarmed bandit problem,” _Machine learning_ , vol. 47, no. 2, pp. 235–256, 2002.
  * [8] P. Auer, “Using confidence bounds for exploitation-exploration trade-offs,” _Journal of Machine Learning Research_ , vol. 3, no. Nov, pp. 397–422, 2002\.
  * [9] W. Chu, L. Li, L. Reyzin, and R. Schapire, “Contextual bandits with linear payoff functions,” in _Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics_. JMLR Workshop and Conference Proceedings, 2011, pp. 208–214.
  * [10] O. Chapelle and L. Li, “An empirical evaluation of thompson sampling,” _Advances in neural information processing systems_ , vol. 24, pp. 2249–2257, 2011.
  * [11] D. Russo and B. Van Roy, “Learning to optimize via posterior sampling,” _Mathematics of Operations Research_ , vol. 39, no. 4, pp. 1221–1243, 2014\.
  * [12] W. R. Thompson, “On the likelihood that one unknown probability exceeds another in view of the evidence of two samples,” _Biometrika_ , vol. 25, no. 3/4, pp. 285–294, 1933.
  * [13] S. Agrawal and N. Goyal, “Analysis of thompson sampling for the multi-armed bandit problem,” in _Conference on learning theory_. JMLR Workshop and Conference Proceedings, 2012, pp. 39–1.
  * [14] ——, “Thompson sampling for contextual bandits with linear payoffs,” in _International Conference on Machine Learning_. PMLR, 2013, pp. 127–135.
  * [15] M. K. S. Faradonbeh, A. Tewari, and G. Michailidis, “On adaptive linear–quadratic regulators,” _Automatica_ , vol. 117, p. 108982, 2020.
  * [16] T. Hu, E. B. Laber, Z. Li, N. J. Meyer, and K. Pacifici, “Note on thompson sampling for large decision problems,” _arXiv preprint arXiv:1905.04735_ , 2019.
  * [17] D. Russo, B. Van Roy, A. Kazerouni, I. Osband, and Z. Wen, “A tutorial on thompson sampling,” _arXiv preprint arXiv:1707.02038_ , 2017.
  * [18] M. Raghavan, A. Slivkins, J. W. Vaughan, and Z. S. Wu, “Greedy algorithm almost dominates in smoothed contextual bandits,” _arXiv preprint arXiv:2005.10624_ , 2020.
  * [19] H. Bastani, M. Bayati, and K. Khosravi, “Mostly exploration-free algorithms for contextual bandits,” _Management Science_ , vol. 67, no. 3, pp. 1329–1349, 2021.
  * [20] A. Slivkins, “Contextual bandits with similarity information,” in _Proceedings of the 24th annual Conference On Learning Theory_. JMLR Workshop and Conference Proceedings, 2011, pp. 679–702.
  * [21] Y. Hu, N. Kallus, and X. Mao, “Smooth contextual bandits: Bridging the parametric and non-differentiable regret regimes,” in _Conference on Learning Theory_. PMLR, 2020, pp. 2007–2010.
  * [22] O.-A. Maillard and S. Mannor, “Latent bandits.” in _International Conference on Machine Learning_. PMLR, 2014, pp. 136–144.
  * [23] L. Zhou and E. Brunskill, “Latent contextual bandits and their application to personalized recommendations for new users,” _arXiv preprint arXiv:1604.06743_ , 2016.
  * [24] J. Hong, B. Kveton, M. Zaheer, Y. Chow, A. Ahmed, and C. Boutilier, “Latent bandits revisited,” _arXiv preprint arXiv:2006.08714_ , 2020.
  * [25] A. Bensoussan, _Stochastic control of partially observable systems_. Cambridge University Press, 2004.
  * [26] D. Bouneffouf, I. Rish, G. A. Cecchi, and R. Féraud, “Context attentive bandits: Contextual bandit with restricted context,” _arXiv preprint arXiv:1705.03821_ , 2017.
  * [27] G. Tennenholtz, U. Shalit, S. Mannor, and Y. Efroni, “Bandits with partially observable confounded data,” in _Conference on Uncertainty in Artificial Intelligence. PMLR_ , 2021.
  * [28] R. Roesser, “A discrete state-space model for linear image processing,” _IEEE Transactions on Automatic Control_ , vol. 20, no. 1, pp. 1–10, 1975\.
  * [29] I. Nagrath, _Control systems engineering_. New Age International, 2006.
  * [30] J. Durbin and S. J. Koopman, _Time series analysis by state space methods_. Oxford university press, 2012\.
  * [31] R. E. Kalman, “A new approach to linear filtering and prediction problems,” 1960\.
  * [32] R. L. Stratonovich, “Optimum nonlinear systems which bring about a separation of a signal with constant parameters from noise,” _Radiofizika_ , vol. 2, no. 6, pp. 892–901, 1959.
  * [33] ——, “Application of the markov processes theory to optimal filtering,” _Radio Engineering and Electronic Physics_ , vol. 5, pp. 1–19, 1960.
  * [34] T. M. Howard, C. J. Green, A. Kelly, and D. Ferguson, “State space sampling of feasible motions for high-performance mobile robot navigation in complex environments,” _Journal of Field Robotics_ , vol. 25, no. 6-7, pp. 325–345, 2008.
  * [35] H. Surmann, C. Jestel, R. Marchel, F. Musberg, H. Elhadj, and M. Ardani, “Deep reinforcement learning for real autonomous mobile robot navigation in indoor environments,” _arXiv preprint arXiv:2005.13857_ , 2020.
  * [36] S. Bubeck and N. Cesa-Bianchi, “Regret analysis of stochastic and nonstochastic multi-armed bandit problems,” _arXiv preprint arXiv:1204.5721_ , 2012.
  * [37] J. L. Doob, _Stochastic processes_. New York Wiley, 1953, vol. 10.
  * [38] H. Cramér, _Mathematical Methods of Statistics (PMS-9), Volume 9_. Princeton university press, 2016.

## Appendix

### Derivation of the conditional distribution $\mathbb{P}(x_{i}(t)|y_{i}(t))$

Note that $y_{i}(t)=Ax_{i}(t)+\varepsilon_{yi}(t)$, where the distributions of
$\varepsilon_{y_{i}}(t)$ and $x_{i}(t)$ are $N(0_{d},\Sigma_{y})$ and
$N(0_{d},\Sigma_{x})$, respectively. The conditional distribution of
$x_{i}(t)$ given $y_{i}(t)$ can be calculated as follows.

$\displaystyle\mathbb{P}(x_{i}(t)|y_{i}(t))$
$\displaystyle\propto\mathbb{P}(y_{i}(t)|x_{i}(t))\mathbb{P}(x_{i}(t))$
$\displaystyle\propto\mathrm{exp}\left((y_{i}(t)-Ax_{i}(t))^{\top}\Sigma_{y}^{-1}(y_{i}(t)-Ax_{i}(t))\right)\mathrm{exp}\left(x_{i}(t)^{\top}\Sigma_{x}^{-1}x_{i}(t)\right)$
$\displaystyle\propto
N((A^{\top}\Sigma_{y}^{-1}A+\Sigma_{x}^{-1})^{-1}A^{\top}\Sigma_{y}^{-1}y_{i}(t),(A^{\top}\Sigma_{y}^{-1}A+\Sigma_{x}^{-1})^{-1})$
(34)

### Derivation of the conditional distribution $\mathbb{P}(r_{i}(t)|y_{i}(t))$

Let $\Sigma_{xy}=(A^{\top}\Sigma_{y}^{-1}A+\Sigma_{x}^{-1})^{-1}$ and recall
$\widehat{x}_{i}(t)=(A^{\top}\Sigma_{y}^{-1}A+\Sigma_{x}^{-1})^{-1}A^{\top}\Sigma_{y}^{-1}y_{i}(t)=Dy_{i}(t)$.

$\displaystyle\mathbb{P}(r_{i}(t)|\mu,y_{i}(t))$
$\displaystyle=\int_{\mathbb{R}^{d}}\mathbb{P}(r_{i}(t)|\mu,x_{i}(t))\mathbb{P}(x_{i}(t)|y_{i}(t))dx_{i}(t)$
$\displaystyle\propto\int_{\mathbb{R}^{d}}\mathrm{exp}\left(-\frac{(r_{i}(t)-x_{i}(t)^{\top}\mu)^{2}}{2\sigma^{2}}\right)\mathrm{exp}\left(-\frac{1}{2}(x_{i}(t)-\widehat{x}_{i}(t))^{\top}\Sigma_{xy}^{-1}(x_{i}(t)-\widehat{x}_{i}(t))\right)dx_{i}(t)$
$\displaystyle\propto\mathrm{exp}\left(-\frac{\left(r_{i}(t)-((A^{\top}\Sigma_{y}^{-1}A+\Sigma_{x}^{-1})^{-1}A^{\top}\Sigma_{y}^{-1}y_{i}(t))^{\top}\mu\right)^{2}}{2(\mu^{\top}\Sigma_{xy}\mu+\sigma^{2})}\right)$
$\displaystyle\propto
N\left(\widehat{x}_{i}(t)^{\top}\mu,\sigma^{2}_{ry}\right).$ (35)

### Derivation of the posterior
$\mathbb{P}(\mu|\mathbf{r}_{t-1},\mathbf{y}_{t-1})$

Let $\mathbb{P}(\mu)$, the pdf of $N(0,\sigma^{2}_{ry}\Sigma)$, be the prior
of $\mu_{*}$. We can decompose the posterior as follows.

$\displaystyle\mathbb{P}(\mu|\mathbf{r}_{t-1},\mathbf{y}_{t-1})$
$\displaystyle\propto\mathbb{P}(\mathbf{r}_{t-1},\mathbf{y}_{t-1}|\mu)\mathbb{P}(\mu)$
$\displaystyle\propto\mathbb{P}(\mathbf{r}_{t-1}|\mathbf{y}_{t-1},\mu)\mathbb{P}(\mu).$

Using the prior and the conditional distribution in (35), we have

$\displaystyle\mathbb{P}(\mu|\mathbf{r}_{t-1},\mathbf{y}_{t-1})$
$\displaystyle\propto\prod_{\tau=1}^{t-1}\mathrm{exp}\left(-\frac{(r_{a(\tau)}(\tau)-\widehat{x}_{a(\tau)}(\tau)^{\top}\mu)^{2}}{2\sigma^{2}_{ry}}\right)\mathrm{exp}\left(-\frac{1}{2\sigma^{2}_{ry}}\mu^{\top}\Sigma^{-1}\mu\right)$
$\displaystyle\propto\mathrm{exp}\left(-\frac{1}{2\sigma^{2}_{ry}}\left(\mu-\widehat{\mu}(t)\right)^{\top}B(t)\left(\mu-\widehat{\mu}(t)\right)\right),$
(36)

which is the kernel of the pdf of
$N(\widehat{\mu}(t),\sigma^{2}_{ry}B(t)^{-1})$, where
$\widehat{\mu}(t)=B(t)^{-1}\sum_{\tau=1}^{t-1}\widehat{x}_{a(t)}(t)r_{a(t)}(t)$
and

$B(t)=\sum_{\tau=1}^{t-1}\widehat{x}_{a(\tau)}(\tau)\widehat{x}_{a(\tau)}^{\top}(\tau)+\Sigma^{-1}.$

Thus, the posterior distribution is
$N(\widehat{\mu}(t),\sigma^{2}_{ry}B(t)^{-1})$. But, to allow for the
possibility that $\sigma^{2}_{ry}$ is unknown, we use a re-scaled posterior
distribution, $N(\widehat{\mu}(t),B(t)^{-1})$, which does not depend on
$\sigma^{2}_{ry}$.

### Derivation of the recursion formula to update the parameter.

Note that we can decompose the posterior as follows.

$\displaystyle\mathbb{P}(\mu|\mathbf{r}_{t},\mathbf{y}_{t})$
$\displaystyle\propto$
$\displaystyle\mathbb{P}(\mathbf{r}_{t},\mathbf{y}_{t},\mu)$
$\displaystyle\propto$
$\displaystyle\mathbb{P}(r_{a(t)}(t)|y_{a(t)}(t),\mu)\mathbb{P}(\mu|\mathbf{r}_{t-1},\mathbf{y}_{t-1}).$

Using the conditional distribution (35) and the posterior in (36), we get

$\displaystyle\mathbb{P}(\mu|\mathbf{r}_{t},\mathbf{y}_{t})$
$\displaystyle\propto\mathbb{P}(r_{a(t)}(t)|y_{a(t)}(t),\mu)\mathbb{P}(\mu|\mathbf{r}_{t-1},\mathbf{y}_{t-1})$
$\displaystyle\propto\mathrm{exp}\left(-\frac{(r_{a(t)}(t)-\widehat{x}_{a(t)}(t)^{\top}\mu)^{2}}{2\sigma^{2}_{ry}}\right)\mathrm{exp}\left(-\frac{1}{2\sigma^{2}_{ry}}\left(\mu-\widehat{\mu}(t)\right)^{\top}B(t)^{-1}\left(\mu-\widehat{\mu}(t)\right)\right)$
$\displaystyle\propto\mathrm{exp}\left(-\frac{1}{2\sigma^{2}_{ry}}\left(\mu-\widehat{\mu}(t+1)\right)^{\top}B(t+1)^{-1}\left(\mu-\widehat{\mu}(t+1)\right)\right),$

where
$\widehat{\mu}(t+1)=B(t+1)^{-1}\left(B(t)\widehat{\mu}(t)+\widehat{x}_{a(t)}(t)r_{a(t)}(t)\right)$
and $B(t+1)=B(t)+\widehat{x}_{a(t)}(t)\widehat{x}_{a(t)}(t)^{\top}$.

### Proof of Lemma 1

###### Proof.

Recall that we used the notation
$S=\mathrm{Var}(\widehat{x}_{i}(t))^{0.5}=(D\Sigma_{y}D^{\top})^{0.5}$ and
$Z(\mu,N)=\operatorname*{argmax}_{Z_{i},1\leq i\leq N}\\{Z_{i}^{\top}\mu\\}$.
Note that $S^{-1}\widehat{x}_{i}(t)$ has the distribution $N(0_{d},I_{d})$ and
$S^{-1}\widehat{x}_{a(t)}(t)=Z(S\widetilde{\mu}(t),N)$.
$S^{-1}\widehat{x}_{i}(t)$ can be decomposed as

$S^{-1}\widehat{x}_{i}(t)=P_{S\widetilde{\mu}(t)}S^{-1}\widehat{x}_{i}(t)+P_{S\widetilde{\mu}(t)^{\perp}}S^{-1}\widehat{x}_{i}(t),$

where $P_{S\widetilde{\mu}(t)^{\perp}}$ denotes the projection matrix onto a
subspace orthogonal to the column-space $C(S\widetilde{\mu}(t))$, which we
denote $C(S\widetilde{\mu}(t))^{\perp}$. As shown in (24), we have

$S^{-1}\widehat{x}_{a(t)}(t)\overset{d}{=}P_{S\widetilde{\mu}(t)}S^{-1}\widehat{x}_{a(t)}(t)+P_{S\widetilde{\mu}(t)^{\perp}}S^{-1}\widehat{x}_{i}(t),$

where $\overset{d}{=}$ expresses that the two quantities have an identical
distribution. Further, based on the fact that the function $Z(\mu,N)$ defined
in (23) is affected only by $\\{P_{\mu}Z_{i}\\}_{1\leq i\leq N}$, but not by
$\\{(I_{d}-P_{\mu})Z_{i}\\}_{1\leq i\leq N}$, we established that
$P_{S\widetilde{\mu}(t)}S^{-1}\widehat{x}_{a(t)}(t)$ and
$P_{S\widetilde{\mu}(t)^{\perp}}S^{-1}\widehat{x}_{i}(t)$ are statistically
independent. Now, consider the following decomposition.

$\displaystyle\mathbb{E}[S^{-1}\widehat{x}_{a(t)}(t)\widehat{x}_{a(t)}(t)^{\top}S^{-1}|\widetilde{\mu}(t)]$
$\displaystyle=P_{S\widetilde{\mu}(t)}E[S^{-1}\widehat{x}_{a(t)}(t)\widehat{x}_{a(t)}(t)^{\top}S^{-1}]P_{S\widetilde{\mu}(t)}+P_{S\widetilde{\mu}(t)^{\perp}}\mathbb{E}[S^{-1}\widehat{x}_{a(t)}(t)\widehat{x}_{a(t)}(t)^{\top}S^{-1}|\widetilde{\mu}(t)]P_{S\widetilde{\mu}(t)^{\perp}}$
$\displaystyle+P_{S\widetilde{\mu}(t)}\mathbb{E}[S^{-1}\widehat{x}_{a(t)}(t)\widehat{x}_{a(t)}(t)^{\top}S^{-1}|\widetilde{\mu}(t)]P_{S\widetilde{\mu}(t)^{\perp}}+P_{S\widetilde{\mu}(t)^{\perp}}\mathbb{E}[S^{-1}\widehat{x}_{a(t)}(t)\widehat{x}_{a(t)}(t)^{\top}S^{-1}|\widetilde{\mu}(t)]P_{S\widetilde{\mu}(t)}.$

By replacing $P_{S\widetilde{\mu}(t)}S^{-1}\widehat{x}_{a(t)}(t)$ with
$P_{S\widetilde{\mu}(t)^{\perp}}S^{-1}\widehat{x}_{i}(t)$ based on the
independence and the equivalence of the distribution, we get

$\displaystyle
P_{S\widetilde{\mu}(t)^{\perp}}\mathbb{E}[S^{-1}\widehat{x}_{a(t)}(t)\widehat{x}_{a(t)}(t)^{\top}S^{-1}|\widetilde{\mu}(t)]P_{S\widetilde{\mu}(t)^{\perp}}=P_{S\widetilde{\mu}(t)^{\perp}}\mathbb{E}[S^{-1}\widehat{x}_{i}(t)\widehat{x}_{i}(t)^{\top}S^{-1}|\widetilde{\mu}(t)]P_{S\widetilde{\mu}(t)^{\perp}}=P_{S\widetilde{\mu}(t)^{\perp}},$
(37)

and

$\displaystyle
P_{S\widetilde{\mu}(t)}\mathbb{E}[S^{-1}\widehat{x}_{a(t)}(t)\widehat{x}_{i}(t)^{\top}S^{-1}|\widetilde{\mu}(t)]P_{S\widetilde{\mu}(t)^{\perp}}+P_{S\widetilde{\mu}(t)^{\perp}}\mathbb{E}[S^{-1}\widehat{x}_{i}(t)\widehat{x}_{a(t)}(t)^{\top}S^{-1}|\widetilde{\mu}(t)]P_{S\widetilde{\mu}(t)}$
(38) $\displaystyle=$ $\displaystyle
P_{S\widetilde{\mu}(t)}\mathbb{E}[S^{-1}\widehat{x}_{a(t)}(t)|\widetilde{\mu}(t)]\mathbb{E}[\widehat{x}_{i}(t)^{\top}S^{-1}|\widetilde{\mu}(t)]P_{S\widetilde{\mu}(t)^{\perp}}+P_{S\widetilde{\mu}(t)^{\perp}}\mathbb{E}[S^{-1}\widehat{x}_{i}(t)|\widetilde{\mu}(t)]\mathbb{E}[\widehat{x}_{a(t)}(t)^{\top}S^{-1}|\widetilde{\mu}(t)]P_{S\widetilde{\mu}(t)}$
$\displaystyle=$ $\displaystyle 0,$

because $\mathbb{E}[\widehat{x}_{i}(t)|\widetilde{\mu}(t)]=0$. Thus, by
putting (37) and (38) together, we have

$\displaystyle\mathbb{E}[S^{-1}\widehat{x}_{a(t)}(t)\widehat{x}_{a(t)}(t)^{\top}S^{-1}|\widetilde{\mu}(t)]=P_{S\widetilde{\mu}(t)}\mathbb{E}[S^{-1}\widehat{x}_{a(t)}(t)\widehat{x}_{a(t)}(t)^{\top}S^{-1}|\widetilde{\mu}(t)]P_{S\widetilde{\mu}(t)}+P_{S\widetilde{\mu}(t)^{\perp}}.$

On the other hand,
$P_{S\widetilde{\mu}(t)}\mathbb{E}[S^{-1}\widehat{x}_{a(t)}(t)\widehat{x}_{a(t)}(t)^{\top}S^{-1}|\widetilde{\mu}(t)]P_{S\widetilde{\mu}(t)}$
can be written as

$\displaystyle
P_{S\widetilde{\mu}(t)}\mathbb{E}[S^{-1}\widehat{x}_{a(t)}(t)\widehat{x}_{a(t)}(t)^{\top}S^{-1}|\widetilde{\mu}(t)]P_{S\widetilde{\mu}(t)}$
$\displaystyle=$
$\displaystyle\frac{S\widetilde{\mu}(t)\widetilde{\mu}(t)^{\top}S}{\widetilde{\mu}(t)^{\top}S^{2}\widetilde{\mu}(t)}\mathbb{E}[S^{-1}\widehat{x}_{a(t)}(t)\widehat{x}_{a(t)}(t)^{\top}S^{-1}|\widetilde{\mu}(t)]\frac{S\widetilde{\mu}(t)\widetilde{\mu}(t)^{\top}S}{\widetilde{\mu}(t)^{\top}S^{2}\widetilde{\mu}(t)}$
(39) $\displaystyle=$
$\displaystyle\frac{S\widetilde{\mu}(t)}{\widetilde{\mu}(t)^{\top}S^{2}\widetilde{\mu}(t)}\mathbb{E}[(\widetilde{\mu}(t)^{\top}SS^{-1}\widehat{x}_{a(t)}(t))^{2}|\widetilde{\mu}(t)]\frac{\widetilde{\mu}(t)^{\top}S}{\widetilde{\mu}(t)^{\top}S^{2}\widetilde{\mu}(t)}$
$\displaystyle=$ $\displaystyle
P_{S\widetilde{\mu}(t)}\mathbb{E}\left[\left.\left(\left(S^{-1}\widehat{x}_{a(t)}(t)\right)^{\top}\overrightarrow{S\widetilde{\mu}(t)}\right)^{2}\right|\widetilde{\mu}(t)\right].$

Since $\widehat{x}_{i}(t)^{\top}S^{-1}\overrightarrow{S\widetilde{\mu}(t)}$
has a standard normal distribution, we have

$\displaystyle\mathbb{E}\left[\left.\left(\widehat{x}_{a(t)}^{\top}(t)S^{-1}\overrightarrow{S\widetilde{\mu}(t)}\right)^{2}\right|\widetilde{\mu}(t)\right]=\mathbb{E}\left[\left(\underset{1\leq
i\leq N}{max}(\\{V_{i}:V_{i}\sim N(0,1)\\}\right)^{2}\right].$ (40)

We define the quantity in (40) as $k_{N}$,

$\displaystyle k_{N}=\mathbb{E}\left[\left(\underset{1\leq i\leq
N}{max}(\\{V_{i}:V_{i}\sim N(0,1)\\}\right)^{2}\right],$ (41)

which is greater than 1 and grows as $N$ gets larger, because
$\mathbb{E}[V_{i}^{2}]=1<\mathbb{E}\left[\left(\underset{1\leq i\leq
N}{max}(\\{V_{i}:V_{i}\sim N(0,1)\\}\right)^{2}\right]$. Thus,
$\mathbb{E}[S^{-1}\widehat{x}_{a(t)}(t)\widehat{x}_{a(t)}(t)^{\top}S^{-1}|\widetilde{\mu}(t)]$
can be written as

$\displaystyle\mathbb{E}[S^{-1}\widehat{x}_{a(t)}(t)\widehat{x}_{a(t)}(t)^{\top}S^{-1}|\widetilde{\mu}(t)]=P_{S\widetilde{\mu}(t)}k_{N}+P_{S\widetilde{\mu}(t)^{\perp}}=P_{S\widetilde{\mu}(t)}(k_{N}-1)+I_{d}.$
(42)

Because the column-spaces of the matrices $P_{S\widetilde{\mu}(t)}$ and
$P_{S\widetilde{\mu}(t)^{\perp}}$ are orthogonal, the non-zero eigenvalues of
$P_{S\widetilde{\mu}(t)}\mathbb{E}[S^{-1}\widehat{x}_{a(t)}(t)\widehat{x}_{a(t)}(t)^{\top}S^{-1}|\widetilde{\mu}(t)]P_{S\widetilde{\mu}(t)}$
and $P_{S\widetilde{\mu}(t)^{\perp}}$ are the eigenvalues of
$\mathbb{E}[S^{-1}\widehat{x}_{a(t)}(t)\widehat{x}_{a(t)}(t)^{\top}S^{-1}|\widetilde{\mu}(t)]$.
That is, $(d-1)$ eigenvalues of
$\mathbb{E}[S^{-1}\widehat{x}_{a(t)}(t)\widehat{x}_{a(t)}(t)^{\top}S^{-1}|\widetilde{\mu}(t)]$
are $1$, and the other eigenvalue is $k_{N}$. This means that
$\mathbb{E}[S^{-1}\widehat{x}_{a(t)}(t)\widehat{x}_{a(t)}(t)^{\top}S^{-1}|\widetilde{\mu}(t)]$
is positive definite, since $k_{N}>1$.

Next, for the true parameter $\mu_{*}$, we claim
$\lim_{t\rightarrow\infty}\widetilde{\mu}(t)=\mu_{*}$. With (14), (17), and
the fact that $\widetilde{\mu}(t)$ is generated from the posterior
$N(\widehat{\mu}(t),B(t)^{-1})$, we have

$\displaystyle\mathbb{E}\left[\widetilde{\mu}(t)\right]$ $\displaystyle=$
$\displaystyle\mathbb{E}\left[\mathbb{E}[\widetilde{\mu}(t)|\mathscr{F}_{t-1}]\right]=\mathbb{E}\left[\widehat{\mu}(t)\right]=(I_{d}-\mathbb{E}[B(t)^{-1}]\Sigma^{-1})\mu_{*},$
(43) $\displaystyle\mathrm{Cov}(\widetilde{\mu}(t))$ $\displaystyle=$
$\displaystyle\mathrm{Cov}(\mathbb{E}[\widetilde{\mu}(t)|\mathscr{F}_{t-1}])+\mathbb{E}[\mathrm{Cov}(\widetilde{\mu}(t)|\mathscr{F}_{t-1})]$
(44) $\displaystyle=$
$\displaystyle\mathrm{Cov}(\widehat{\mu}(t))+\mathbb{E}[B(t)^{-1}]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[B(t)^{-1}\Sigma^{-1}\mu_{*}\mu_{*}^{\top}\Sigma^{-1}B(t)^{-1}\right]-\mathbb{E}\left[B(t)^{-1}\right]\Sigma^{-1}\mu_{*}\mu_{*}^{\top}\Sigma^{-1}\mathbb{E}\left[B(t)^{-1}\right]$
$\displaystyle+$
$\displaystyle\mathbb{E}\left[B(t)^{-1}\right]\sigma^{2}_{ry}-\mathbb{E}\left[B(t)^{-1}\Sigma^{-1}B(t)^{-1}\right]\sigma^{2}_{ry}+\mathbb{E}\left[B(t)^{-1}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[B(t)^{-1}\Sigma^{-1}\mu_{*}\mu_{*}^{\top}\Sigma^{-1}B(t)^{-1}\right]-\mathbb{E}\left[B(t)^{-1}\right]\Sigma^{-1}\mu_{*}\mu_{*}^{\top}\Sigma^{-1}\mathbb{E}\left[B(t)^{-1}\right]$
$\displaystyle+$
$\displaystyle\mathbb{E}\left[B(t)^{-1}\right](\sigma^{2}_{ry}+1)-\mathbb{E}\left[B(t)^{-1}\Sigma^{-1}B(t)^{-1}\right]\sigma^{2}_{ry}.$

Since $\lim_{t\rightarrow\infty}B(t)^{-1}=0_{d\times d}$ and thereby
$\lim_{t\rightarrow\infty}\mathrm{Cov}(\widetilde{\mu}(t))=0_{d\times d}$,
$\widetilde{\mu}(t)$ is a consistent estimator of $\mu_{*}$. That is,

$\displaystyle\lim_{t\rightarrow\infty}\widetilde{\mu}(t)=\mu_{*}.$ (45)

Thus, $\lim_{t\rightarrow\infty}P_{S\widetilde{\mu}(t)}=P_{S\mu_{*}}$. Using

$\mathbb{E}[S^{-1}\widehat{x}_{a(t)}(t)\widehat{x}_{a(t)}(t)^{\top}S^{-1}|\mathscr{F}_{t-1}]=\mathbb{E}[\mathbb{E}[S^{-1}\widehat{x}_{a(t)}(t)\widehat{x}_{a(t)}(t)^{\top}S^{-1}|\widetilde{\mu}(t)]|\mathscr{F}_{t-1}]$

and (42), we get

$\displaystyle\lim_{t\rightarrow\infty}\mathbb{E}[S^{-1}\widehat{x}_{a(t)}(t)\widehat{x}_{a(t)}(t)^{\top}S^{-1}|\mathscr{F}_{t-1}]=\lim_{t\rightarrow\infty}\mathbb{E}[P_{S\widetilde{\mu}(t)}(k_{N}-1)+I_{d}|\mathscr{F}_{t-1}]=P_{S\mu_{*}}(k_{N}-1)+I_{d}.$

Because the eigenvalues $P_{S\mu_{*}}(k_{N}-1)+I_{d}$ are $(d-1)$ $1$s and
$k_{N}$, which is greater than 1, $P_{S\mu_{*}}(k_{N}-1)+I_{d}$ is positive
definite. Therefore,
$\lim_{t\rightarrow\infty}\mathbb{E}[S^{-1}\widehat{x}_{a(t)}(t)\widehat{x}_{a(t)}(t)^{\top}S^{-1}|\mathscr{F}_{t-1}]$
is positive definite.

$\blacksquare$

### Proof of Corollary 1

###### Proof.

Recall $\mathrm{Cov}(\widetilde{\mu}(t))$ in (44)

$\displaystyle\mathrm{Cov}(\widetilde{\mu}(t))$ $\displaystyle=$
$\displaystyle\mathbb{E}\left[B(t)^{-1}\Sigma^{-1}\mu_{*}\mu_{*}^{\top}\Sigma^{-1}B(t)^{-1}\right]-\mathbb{E}\left[B(t)^{-1}\right]\Sigma^{-1}\mu_{*}\mu_{*}^{\top}\Sigma^{-1}\mathbb{E}\left[B(t)^{-1}\right]$
$\displaystyle+$
$\displaystyle\mathbb{E}\left[B(t)^{-1}\right](\sigma^{2}_{ry}+1)-\mathbb{E}\left[B(t)^{-1}\Sigma^{-1}B(t)^{-1}\right]\sigma^{2}_{ry}.$

Since $B(t)^{-1}=O(t^{-1})$ by Lemma 1 and the other terms are negligible
except $\mathbb{E}\left[B(t)^{-1}\right](\sigma^{2}_{ry}+1)$ in above terms,
we have $\mathrm{Cov}(\widetilde{\mu}(t))=O(t^{-1})$. In addition, we already
showed that $\lim_{t\rightarrow\infty}\widetilde{\mu}(t)=\mu_{*}$ in
(45).Therefore,

$\lim_{t\rightarrow\infty}\widetilde{\mu}(t)=\mu_{*},\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\mathrm{Cov}(\widetilde{\mu}(t))=O(t^{-1}).$

$\blacksquare$