# Restless Bandit Problem with Rewards Generated by a Linear Gaussian
Dynamical System

Jonathan Gornet and Bruno Sinopoli

###### Abstract

Decision-making under uncertainty is a fundamental problem encountered
frequently and can be formulated as a stochastic multi-armed bandit problem.
In the problem, the learner interacts with an environment by choosing an
action at each round, where a round is an instance of an interaction. In
response, the environment reveals a reward, which is sampled from a stochastic
process, to the learner. The goal of the learner is to maximize cumulative
reward. In this work, we assume that the rewards are the inner product of an
action vector and a state vector generated by a linear Gaussian dynamical
system. To predict the reward for each action, we propose a method that takes
a linear combination of previously observed rewards for predicting each
action’s next reward. We show that, regardless of the sequence of previous
actions chosen, the reward sampled for any previously chosen action can be
used for predicting another action’s future reward, i.e. the reward sampled
for action 1 at round $t-1$ can be used for predicting the reward for action
$2$ at round $t$. This is accomplished by designing a modified Kalman filter
with a matrix representation that can be learned for reward prediction.
Numerical evaluations are carried out on a set of linear Gaussian dynamical
systems and are compared with 2 other well-known stochastic multi-armed bandit
algorithms.

##  1 Introduction

The Stochastic Multi-Armed Bandit (SMAB) problem provides a rigorous framework
for studying decision-making under uncertainty. The problem consists of the
interaction between a learner and an environment for a set number of rounds.
For each round, the learner chooses an action and in response the environment
reveals a reward, which is sampled from a stochastic process, to the learner.
The goal of the learner is to maximize cumulative reward. In the non-
stationary case of the SMAB, the distributions of the reward for each action
can change each round. A key result in the area is [1] where it assumes that
the cumulative changes in the reward distributions are bounded by a known
constant.

A more specific variation of the non-stationary SMAB are environments where
the rewards are generated by $s$-step autoregressive models, i.e. an action’s
sampled reward $X_{t}$ is a linear combination of rewards
$X_{t-s},\dots,X_{t-1}$ where $s$ is the autoregressive model order. Two key
results that have tackled this SMAB environment are [2, 3, 4]. [2] studied the
performance of a number of algorithms for rewards generated by Brownian
motion. In [3], the authors consider when the rewards for each action is
generated by a known 1-step autoregressive process. In [4], they address SMAB
environments modeled as an unknown 1-step autoregressive or a known $s$-step
autoregressive. A key application of autoregressive models is presented in
[5], where the work tunes the hyperparameters, such as the gradient descent’s
learning rate, during the training process of a reinforcement learning based
on neural networks. Finally, another perspective to $s$-step autoregressive
models is [6] where the reward $X_{t}$ and a context $\theta_{t}$ are
generated by a Linear Gaussian Dynamical System (LGDS), where a context is a
partial observation of the LGDS’s state variables. The authors prove that a
linear combination of previously observed contexts
$\theta_{t-s},\dots,\theta_{t-1}$ can be used to predict the reward $X_{t}$, a
perspective similar to the environments considered in [3] and [4].

Our work proposes a discrete-time restless bandit with continuous state-space
by assuming the state and rewards are generated by a LGDS. This paper extends
the results in [6] where now the context is no longer observed. The
contributions of our paper are as follows.

Our Contributions:

  * •

We introduce a SMAB environment where the rewards are generated by a LGDS in
Section 2.

  * •

We prove that we can predict the reward for each action by using a linear
combination of observed rewards. For example, for an environment with 3
actions, if a learner chose action $A_{t-2}=2$ at round $t-2$ and $A_{t-1}=1$
at round $t-1$, the learner can take a linear combination of the sampled
rewards $X_{t-2}$ and $X_{t-1}$ to predict the reward for action $a=3$ at
round $t$. The coefficients for the linear combination are from the identified
modified Kalman filter matrix representation. We provide a proof of the error
bound of the reward prediction for the identified modified Kalman filter. The
idea is inspired by [7] for identifying the Kalman filter, where now we assume
that the measurements of the LGDS, a linear combination of the system’s state
variables, can change each round. (See Section 3)

  * •

Using the proved error bound of the reward prediction, we propose the
algorithm Uncertainty-Based System Search (UBSS). The algorithm chooses the
action that maximizes the sum of the reward prediction and its error. (See
Section 4)

  * •

For numerical results in Section 5, we apply UBSS to a parameterized LGDS to
illustrate its numerical performance. Here, we compare UBSS to Upper
Confidence Bound (UCB) algorithm [8] and Sliding Window UCB (SW-UCB) [9]
algorithm, two well-known SMAB algorithms, and for which LGDS UBSS performs
best.

Related Work

One example of the non-stationary SMAB is the restless bandit where the reward
for each action is the function of a state that is generated by a Markov chain
[10]. Whenever the learner chooses an action, the learner observes a Markov
chain’s state and a reward. This paper focuses on the case when the transition
matrix of the Markov chain is unknown. Previous results in the discrete state-
space Markov chain that use an approach similar to UCB are [11, 12, 13, 14,
15]. [16] uses Thompson sampling, i.e. sampling parameters based on a priori
distribution of Markov chain, for action selection. We avoid comparisons with
these previous results since the states of the Markov chain are discrete,
whereas the results presented in this paper focus on when the states are
continuous. This allows us to tackle a different set of application, such as
hyperparameter optimization for reinforcement learning based on neural
networks, e.g. [5].

##  2 Problem Formulation

The learner will interact with an environment modeled as a LGDS. We will
consider the following LGDS:

$\begin{cases}z_{t+1}&=\Gamma
z_{t}+\xi_{t},~{}~{}z_{0}\sim\mathcal{N}\left(\hat{z}_{0},P_{0}\right)\\\
X_{t}&=\left\langle c_{A_{t}},z_{t}\right\rangle+\eta_{t}\end{cases},$ (1)

where the reward $X_{t}\in\mathbb{R}$ is the inner product of an action vector
$c_{A_{t}}\in\mathcal{A}$ and the state $z_{t}\in\mathbb{R}^{d}$. The process
noise $\xi_{t}\in\mathbb{R}^{d}$ and measurement noise $\eta_{t}\in\mathbb{R}$
are independent normally distributed random variables, i.e.
$\xi_{t}\sim\mathcal{N}(0,Q)$ and $\eta_{t}\sim\mathcal{N}(0,\sigma^{2})$. The
action vector $c_{A_{t}}\in\mathcal{A}=\\{c_{a}\in\mathbb{R}^{d\times
1}\mid\left\|c_{a}\right\|_{2}\leq B_{c},a\in[k]\\}$ where $B_{c}$ is known
and $a\in[k]\triangleq\\{1,2,\dots,k\\}$ is the indexed action. Using similar
notation as [17], actions that are realized at round $t$ are denoted as
$c_{A_{t}}\in\mathcal{A}$ and unrealized actions are denoted as
$c_{a}\in\mathcal{A}$. We make the following assumptions on system (1).

######  Assumption 1.

The state matrix $\Gamma$ is marginally stable, i.e.
$\rho\left(\Gamma\right)\leq 1$.

######  Assumption 2.

The vectors and matrices in system (1) are unknown along with $Q$, $\sigma$,
and $d$. However, number of actions $k$ is known.

######  Assumption 3.

The matrix pair $\left(\Gamma,Q^{1/2}\right)$ is controllable. The pair
$\left(\Gamma,c_{a}^{\top}\right)$ is detectable for every vector
$c_{a}\in\mathcal{A}$.

The goal of the learner is to maximize the cumulative reward over a horizon
$n>0$, i.e. $\sum_{t=1}^{n}X_{t}$. The horizon length $n>0$ may be unknown. To
provide analysis on the performance of any proposed algorithm for maximizing
cumulative reward in (1), regret is analyzed which is defined to be

$R_{n}\triangleq\sum_{t=1}^{n}\mathbb{E}\left[X_{t}^{*}-X_{t}\right],$ (2)

where $X_{t}^{*}$ is the highest possible reward that can be sampled at round
$t$. In the next section, we discuss a reward predictor for the LGDS (1).

##  3 Predicting the Reward of the LGDS

This section reviews the optimal $1$-step predictor of the rewards, in the
mean-squared error sense, generated by LGDS (1): the Kalman filter. According
to Assumption 2, the matrices of the LGDS (1) are unknown, implying that the
Kalman filter needs to be identified. However, to the best of our knowledge,
no current results exist for direct identification of the Kalman filter when
the LGDS’s (1) action vector $c_{A_{t}}\in\mathcal{A}$ can change each round.
Therefore, we propose a modified Kalman filter to identify. Imposing the
assumptions posed in the previous section, we prove that prediction error of
the modified Kalman filter is lower than or equal to the variance of the
reward $X_{t}$, making it possible to extract a signal to predict the reward
for each action. The added benefit of the modified Kalman filter is that it is
tractable to identify.

The Kalman filter uses the previous observations $X_{1},\dots,X_{t}$ to
compute an estimate of the state $z_{t}$ as
$\hat{z}_{t}\triangleq\mathbb{E}\left[z_{t}\mid\mathcal{F}_{t-1}\right]$ where
$\mathcal{F}_{t-1}$ is the sigma algebra generated by the rewards
$X_{1},\dots,X_{t-1}$,

$\begin{cases}\hat{z}_{t+1}&=\Gamma\hat{z}_{t}+\Gamma
K_{t}\left(X_{t}-\left\langle
c_{A_{t}},\hat{z}_{t}\right\rangle\right),~{}~{}P_{t+1}=g\left(P_{t},c_{A_{t}}\right)\\\
K_{t}&=P_{t}c_{A_{t}}\left(c_{A_{t}}^{\top}P_{t}c_{A_{t}}+\sigma\right)^{-1}\\\
\hat{X}_{t}&=\left\langle c_{A_{t}},\hat{z}_{t}\right\rangle\end{cases},$ (3)

and $g\left(P,c\right)$ is defined to be the following Riccati equation [18]

$g\left(P,c\right)\triangleq\Gamma P\Gamma^{\top}+Q-\Gamma
Pc\left(c^{\top}Pc+\sigma\right)^{-1}c^{\top}P\Gamma^{\top}.$ (4)

We impose the following assumption for the LGDS’s (1) initial state
$z_{0}\sim\mathcal{N}(\hat{z}_{0},P_{0})$ and the Kalman filter’s (3) initial
error covariance matrix $P_{0}$:

######  Assumption 4.

The initial state $z_{0}\in\mathbb{R}^{d}$ of the LGDS (1) is sampled from a
normal distribution with a mean $\hat{z}_{0}\in\mathbb{R}^{d}$ that is a
solution of $\hat{z}_{0}=\Gamma\hat{z}_{0}$ and covariance matrix
$P_{0}\in\mathbb{R}^{d\times d}$. We assume that $P_{0}=P_{\overline{a}}$,
where $P_{\overline{a}}$ is the steady-state error covariance matrix,
$P_{\overline{a}}=g\left(P_{\overline{a}},c_{\overline{a}}\right)$,
$c_{\overline{a}}\in\mathcal{A}$. This assumption implies that the LGDS (1) is
in a steady-state distribution.

######  Remark 1.

Assumption 4 states that LGDS (1) is in steady-state and the Kalman filter’s
(3) error covariance matrix is bounded. This is a reasonable assumption as the
Kalman filter covariance matrix $P_{t}$ converges exponentially to the steady
state covariance matrix $P_{\overline{a}}$ as $t$ increases if action
$c_{\overline{a}}\in\mathcal{A}$ is consistently chosen. In addition, a
similar assumption has been made in [19], [20], and [7]. Finally, it will be
proven in Lemma 1 that there exists an action $c_{\overline{a}}\in\mathcal{A}$
such that $P_{\overline{a}}\succeq P_{t}$ if $P_{\overline{a}}=P_{0}$.

As mentioned earlier, the parameters of LGDS (1) are unknown due to Assumption
2. Therefore, we propose to learn the Kalman filter (3) for reward prediction.
However, since the Kalman filter matrices $P_{t}$ and $K_{t}$ change
constantly, it is intractable to identify the Kalman filter. Therefore, we
prove that there exists a modified Kalman filter that has a bounded reward
prediction error regardless of the choices $c_{A_{t}}\in\mathcal{A}$ that is
tractable to identify. For proving Theorem 1, we first provide Lemma 1 for the
bound on the Kalman filter error covariance matrix $P_{t}$.

######  Lemma 1.

Let $P_{a}$, $a\in[k]$ be the steady state solution of the Kalman filter for
each action $c_{a}\in\mathcal{A}$, $P_{a}=g\left(P_{a},c_{a}\right)$, where
$g\left(P_{a},c_{a}\right)$ is defined in (4). Define $P_{\overline{a}}\succeq
0$ to be the steady-state error covariance matrix of the Kalman filter (3)
associated with action $c_{\overline{a}}\in\mathcal{A}$ such that
$P_{\overline{a}}\succeq P_{a}$ for every action $a\in[k]$. By imposing
Assumptions 1, 3, and 4, the LGDS (1), then $P_{\overline{a}}\succeq P_{t}$
for any $t=1,2,\dots,n$.

Below is Theorem 1 which proves the existence of a modified Kalman filter with
a bounded prediction error. Proof for Theorem 1 can be found in Appendix B.

######  Theorem 1.

We define the following modified Kalman filter

$\begin{cases}\hat{z}_{t+1}^{\prime}&=\Gamma\hat{z}_{t}^{\prime}+\Gamma
L_{A_{t}}\left(X_{t}-\left\langle
c_{A_{t}},\hat{z}_{t}^{\prime}\right\rangle\right)\\\ X_{t}&=\left\langle
c_{A_{t}},\hat{z}_{t}^{\prime}\right\rangle+\gamma_{A_{t}}\end{cases},~{}~{}L_{A_{t}}\triangleq
P_{\overline{a}}c_{A_{t}}\left(c_{A_{t}}^{\top}P_{\overline{a}}c_{A_{t}}+\sigma\right)^{-1},$
(5)

where $\gamma_{A_{t}}\triangleq X_{t}-\left\langle
c_{A_{t}},\hat{z}_{t}^{\prime}\right\rangle\sim\mathcal{N}\left(0,c_{A_{t}}^{\top}P_{t}^{\prime}c_{A_{t}}+\sigma\right)$
and
$P_{t}^{\prime}\triangleq\mathbb{E}\left[\left(z_{t}-\hat{z}_{t}^{\prime}\right)\left(z_{t}-\hat{z}_{t}^{\prime}\right)^{\top}\mid\mathcal{F}_{t-1}\right]$.
It is proven for the modified Kalman filter (5) that 1) the matrix
$\Gamma-\Gamma L_{A_{t}}c_{A_{t}}^{\top}$ is stable and 2) the variance of the
residual $\mbox{Var}\left(\gamma_{A_{t}}\right)$ is bounded.

The key takeaway for Theorem 1 is that there exists a modified Kalman filter
(5) that is easier to identify in comparison to the Kalman filter (3) at the
expense of a higher prediction error $\mbox{Var}\left(\gamma_{a}\right)\geq
c_{a}^{\top}P_{t}c_{a}+\sigma^{2}$. This is because the modified Kalman filter
has only a finite number of gain matrices $L_{A_{t}}$ and a static covariance
matrix $P_{\overline{a}}$. In addition, the variance of the prediction error
$\mbox{Var}\left(\gamma_{a}\right)$ has an upper-bound.

###  3.1 Learning the Modified Kalman filter

Using Theorem 1 and inspired by the results presented in [7], we will learn
the modified Kalman filter since the matrices and vectors in the LGDS (1) and
its modified Kalman filter (5) are unknown. Let parameter $s>0$ denote how far
in the past the learner will look. We define the tuple
$\mathbf{c}\triangleq\begin{pmatrix}c_{A_{t-s}}&\dots&c_{A_{t-1}}\end{pmatrix}$
as the sequence of actions chosen by the learner from rounds $t-s$ to $t-1$.
The reward $X_{t}=\left\langle c_{a},z_{t}\right\rangle+\eta_{t}$ for action
$a\in[k]$ can be expressed as a linear combination of rewards
$X_{t-s},\dots,X_{t-1}$ generated by the tuple $\mathbf{c}$ using the matrices
defined in the modified Kalman filter (5):

$X_{t}=c_{a}^{\top}\left(\Gamma-\Gamma
L_{A_{t-1}}\right)\cdots\left(\Gamma-\Gamma L_{A_{t-s+1}}\right)\Gamma
L_{A_{t-s}}X_{t-s}+\dots{\\\ }+c_{a}^{\top}\Gamma
L_{A_{t-1}}X_{t-1}+c_{a}^{\top}\left(\Gamma-\Gamma
L_{A_{t-1}}c_{A_{t-1}}^{\top}\right)\cdots\left(\Gamma-\Gamma
L_{A_{t-s}}c_{A_{t-s}}^{\top}\right)\hat{z}_{t-s}^{\prime}+\gamma_{a},$ (6)

Therefore, let there be defined the vectors $G_{c_{a}|\mathbf{c}}$,
$c_{a}\in\mathcal{A}$, and $\Xi\left(\mathbf{c}\right)$ to express the reward
$X_{t}=\left\langle c_{a},z_{t}\right\rangle+\eta_{t}$:

$\Rightarrow
X_{t}=G_{c_{a}\mid\mathbf{c}}^{\top}\Xi_{t}\left(\mathbf{c}\right)+\beta_{a}+\gamma_{a},$
(7) $\displaystyle G_{c_{a}\mid\mathbf{c}}$
$\displaystyle\triangleq\begin{bmatrix}c_{a}^{\top}\left(\Gamma-\Gamma
L_{A_{t-1}}\right)\cdots\left(\Gamma-\Gamma L_{A_{t-s+1}}\right)\Gamma
L_{A_{t-s}}&\dots&c_{a}^{\top}\Gamma
L_{A_{t-1}}\end{bmatrix}\in\mathbb{R}^{s\times 1}$
$\displaystyle\Xi_{t}\left(\mathbf{c}\right)$
$\displaystyle\triangleq\begin{bmatrix}X_{t-s}&\dots&X_{t-1}\end{bmatrix}^{\top}\in\mathbb{R}^{s\times
1}$ $\displaystyle\beta_{a}$ $\displaystyle\triangleq
c_{a}^{\top}\left(\Gamma-\Gamma
L_{A_{t-1}}c_{A_{t-1}}^{\top}\right)\cdots\left(\Gamma-\Gamma
L_{A_{t-s}}c_{A_{t-s}}^{\top}\right)\hat{z}_{t-s}^{\prime}\in\mathbb{R}.$

Based on equation (7), we can express the reward $X_{t}=\left\langle
c_{a},z_{t}\right\rangle+\eta_{t}$ for each action $c_{a}\in\mathcal{A}$ using
$G_{c_{a}|\mathbf{c}}$, $c_{a}\in\mathcal{A}$, and
$\Xi\left(\mathbf{c}\right)$ with the following linear model:

$\begin{pmatrix}\left\langle c_{1},z_{t}\right\rangle+\eta_{t}\\\ \left\langle
c_{2},z_{t}\right\rangle+\eta_{t}\\\ \vdots\\\ \left\langle
c_{k},z_{t}\right\rangle+\eta_{t}\\\
\end{pmatrix}=\begin{pmatrix}G_{c_{1}\mid\mathbf{c}}^{\top}\\\
G_{c_{2}\mid\mathbf{c}}^{\top}\\\ \vdots\\\
G_{c_{k}\mid\mathbf{c}}^{\top}\end{pmatrix}\Xi_{t}\left(\mathbf{c}\right)+\begin{pmatrix}\beta_{1}\\\
\beta_{2}\\\ \vdots\\\ \beta_{k}\end{pmatrix}+\begin{pmatrix}\gamma_{1}\\\
\gamma_{2}\\\ \vdots\\\ \gamma_{k}\end{pmatrix}.$ (8)

The linear model (8) proves that we only need to identify $k^{s+1}$ vectors
$G_{c_{a}\mid\mathbf{c}}$. Therefore, we can 1) identify
$G_{c_{a}\mid\mathbf{c}}$ for each action $c_{a}\in\mathcal{A}$ and 2) predict
the reward $X_{t}$ using inner product of the identified
$G_{c_{a}\mid\mathbf{c}}$ and sequence of rewards $X_{t-s},\dots,X_{t-1}$.

######  Remark 2.

In the linear model (8), there is a parameter $s>0$ which is the number of
previous rewards $X_{t-s},\dots,X_{t-1}$ used for predicting the reward
$X_{t}$. Parameter $s>0$ impacts the magnitude of the term $\beta_{a}$ (which
decreases exponentially as $s$ increases) and the number of linear models
$G_{c_{a}\mid\mathbf{c}}$ to identify (which increases exponentially as $s$
increases).

The following are assumed about $G_{c_{a}\mid\mathbf{c}}$, $\gamma_{a}$, and
$c_{a}\in\mathcal{A}$:

######  Assumption 5.

There exists a known upper bound $B_{G}$ such that
$\|G_{c_{a}\mid\mathbf{c}}\|_{2}\leq B_{G}$ for all $a\in[k]$ which is a
common assumption to use in SMAB problems [21].

######  Assumption 6.

There exists a known constant $B_{R}>0$ such that for any round $t>0$, we
have:

$\displaystyle\sqrt{\mbox{tr}\left(Z_{t}\right)}\leq
B_{R},~{}Z_{t}\triangleq\mathbb{E}\left[z_{t}z_{t}^{\top}\right],~{}\mbox{Var}\left(\gamma_{a}\right)\leq
c_{a}^{\top}P_{\overline{a}}c_{a}+\sigma_{\eta}\leq B_{R}^{2}\mbox{ for
}c_{a}\in\mathcal{A},$

where $Z_{t}$ (which has the iteration $Z_{t+1}=\Gamma Z_{t}\Gamma^{\top}+Q$)
is the covariance of the LGDS’s (1) state $z_{t}$. Results in the area of non-
stationary SMAB have made similar assumptions (see [4]).

To learn $G_{c_{a}\mid\mathbf{c}}$, assume that at time points
$\mathcal{T}_{c_{a}\mid\mathbf{c}}=\left\\{t_{1},\dots,t_{N_{a}}\right\\}$
($N_{a}$ is the number of times action $c_{a}\in\mathcal{A}$ is chosen) the
following tuple sequence
$\begin{pmatrix}c_{A_{t_{i}-s}},\dots,c_{A_{t_{i}-1}}\end{pmatrix}=\mathbf{c}\in\mathcal{A}^{s}\mbox{
for }t_{i}\in\left\\{t_{1},\dots,t_{N_{a}}\right\\}$ and action
$c_{A_{t}}=c_{a}\in\mathcal{A}$ are chosen. We have the following linear model

$\mathbf{X}_{\mathcal{T}_{c_{a}\mid\mathbf{c}}}=G_{c_{a}\mid\mathbf{c}}^{\top}\mathbf{Z}_{\mathcal{T}_{c_{a}\mid\mathbf{c}}}+\mathbf{B}_{\mathcal{T}_{c_{a}\mid\mathbf{c}}}+\mathbf{E}_{\mathcal{T}_{c_{a}\mid\mathbf{c}}},$
(9) $\displaystyle\mathbf{X}_{\mathcal{T}_{c_{a}\mid\mathbf{c}}}$
$\displaystyle\triangleq\begin{bmatrix}X_{t_{1}}&\dots&X_{t_{N_{a}}}\end{bmatrix}\in\mathbb{R}^{1\times
N_{a}},$ $\displaystyle\mathbf{Z}_{\mathcal{T}_{c_{a}\mid\mathbf{c}}}$
$\displaystyle\triangleq\begin{bmatrix}\Xi_{t_{1}}\left(\mathbf{c}\right)&\dots&\Xi_{t_{N_{a}}}\left(\mathbf{c}\right)\end{bmatrix}\in\mathbb{R}^{s\times
N_{a}},$ $\displaystyle\mathbf{B}_{\mathcal{T}_{c_{a}\mid\mathbf{c}}}$
$\displaystyle\triangleq\begin{bmatrix}\beta_{A_{t_{1}}}&\dots&\beta_{A_{t_{N_{a}}}}\end{bmatrix}\in\mathbb{R}^{1\times
N_{a}},$ $\displaystyle\mathbf{E}_{\mathcal{T}_{c_{a}\mid\mathbf{c}}}$
$\displaystyle\triangleq\begin{bmatrix}\gamma_{A_{t_{1}}}&\dots&\gamma_{A_{t_{N_{a}}}}\end{bmatrix}\in\mathbb{R}^{1\times
N_{a}}.$

The least squares estimate of $G_{c_{a}\mid\mathbf{c}}$ in (9) is

$\displaystyle\hat{G}_{c_{a}\mid\mathbf{c}}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)$
$\displaystyle=\mathbf{X}_{\mathcal{T}_{c_{a}\mid\mathbf{c}}}\mathbf{Z}_{\mathcal{T}_{c_{a}\mid\mathbf{c}}}^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}$
(10) $\displaystyle V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)$
$\displaystyle\triangleq\lambda
I_{s}+\mathbf{Z}_{\mathcal{T}_{c_{a}\mid\mathbf{c}}}\mathbf{Z}_{\mathcal{T}_{c_{a}\mid\mathbf{c}}}^{\top}=\lambda
I_{s}+\sum_{i=1}^{N_{a}}\Xi_{t_{i}}\left(\mathbf{c}\right)\Xi_{t_{i}}\left(\mathbf{c}\right)^{\top},$
(11)

where $\lambda>0$ is a regularization term. Since there are $k^{s}$ codes
$\mathbf{c}\in\mathcal{A}^{s}$, then there are $k^{s+1}$ vectors
$G_{c_{a}\mid\mathbf{c}}$ to learn.

##  4 Uncertainty-Based System Search Restless Bandit Problem

The section above provided a predictor, the modified Kalman filter, for the
rewards generated by the LGDS (1). It also provided a methodology for
identifying the predictor. Now that the reward can be predicted using an
identified modified Kalman filter, we discuss how to use the predictor in
Algorithm 1, Uncertainty-Based System Search (UBSS). The general scheme for
UBSS is to 1) identify the predictor $G_{c_{a}\mid\mathbf{c}}$ for each action
$c_{a}\in\mathcal{A}$ and 2) select actions that balances what the learner
predicts will return the highest reward versus which actions the learner is
the most uncertain due to the error of the predictor
$\hat{G}_{c_{a}\mid\mathbf{c}}$. Therefore, for each round $t$ in UBSS, the
learner will choose actions based on the following optimization problem

$\underset{a\in[k]}{\arg\max}~{}\hat{G}_{c_{a}\mid\mathbf{c}}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{\top}\Xi_{t}\left(\mathbf{c}\right)+\left(e_{c_{a}\mid\mathbf{c}}\left(\delta_{e}\right)+b_{c_{a}\mid\mathbf{c}}\left(\delta_{b}\right)\right)\sqrt{\Xi_{t}\left(\mathbf{c}\right)^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}\Xi_{t}\left(\mathbf{c}\right)},$
(12)

where with a probability of at least $(1-\delta_{e})(1-\delta_{b})$, the
following inequality is satisfied (see Theorem 9 in Appendix C.2):

$\hat{G}_{c_{a}\mid\mathbf{c}}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{\top}\Xi_{t}\left(\mathbf{c}\right)-G_{c_{a}\mid\mathbf{c}}^{\top}\Xi_{t}\left(\mathbf{c}\right)\leq\left(e_{c_{a}\mid\mathbf{c}}\left(\delta_{e}\right)+b_{c_{a}\mid\mathbf{c}}\left(\delta_{b}\right)\right)\sqrt{\Xi_{t}\left(\mathbf{c}\right)^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}\Xi_{t}\left(\mathbf{c}\right)}.$
(13)

The terms $e_{c_{a}\mid\mathbf{c}}\left(\delta_{e}\right)$ and
$b_{c_{a}\mid\mathbf{c}}\left(\delta_{b}\right)$ are defined as

$\displaystyle e_{c_{a}\mid\mathbf{c}}\left(\delta_{e}\right)$
$\displaystyle\triangleq\sqrt{2B_{R}^{2}\log\left(\frac{1}{\delta_{e}}\frac{\det(V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right))^{1/2}}{\det(\lambda
I)^{1/2}}\right)}$ (14) $\displaystyle
b_{c_{a}\mid\mathbf{c}}\left(\delta_{b}\right)$
$\displaystyle\triangleq\sqrt{N_{a}}\frac{B_{c}B_{R}}{\delta_{b}}\sqrt{\mbox{tr}\left(I-\lambda
V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}\right)}+\lambda\sqrt{\mbox{tr}\left(V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}\right)}B_{G}.$
(15)

Reward prediction uncertainty (13) of action $c_{a}\in\mathcal{A}$ is impacted
directly $V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)$ which is a sum
of $N_{a}$ (number of times action $c_{a}\in\mathcal{A}$ is chosen) positive
semi-definite matrices. Therefore, choosing an action frequently (large
$N_{a}$) will lower the reward prediction uncertainty. The rationale behind
optimization problem (12) is to balance choosing the action with the highest
reward versus the action with the most uncertainty. We summarize below which
term is defined to be in (12) within Algorithm 1 which consists of an
Exploitation term (which action the learner expects to return the highest
reward) and an Exploration term (how much should the learner explore an
action).

  * •

Exploitation term:
$\hat{G}_{c_{a}\mid\mathbf{c}}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{\top}\Xi_{t}\left(\mathbf{c}\right)$

  * •

Exploration term:
$\left(e_{c_{a}\mid\mathbf{c}}\left(\delta_{e}\right)+b_{c_{a}\mid\mathbf{c}}\left(\delta_{b}\right)\right)\sqrt{\Xi_{t}\left(\mathbf{c}\right)^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}\Xi_{t}\left(\mathbf{c}\right)}$

Parameters $\left(\delta_{e},\delta_{b}\right)$ are failure rates of the bound
in (13) where $\left(\delta_{e},\delta_{b}\right)$ values closer to 0 computes
a larger bound (13). Parameter $s$ is the number of previously observed
rewards $X_{t-\tau}$ ($\tau=1,\dots,s$) used for predicting the next reward.
The number of models to learn increases exponentially as $s$ increases.
Finally, $\lambda$ is a regularization parameter to ensure that (11) is
invertible.

Input:  $\delta_{e},\delta_{b}\in(0,1)$, $\lambda>0$, $s\in\mathbb{N}$,
$B_{c},B_{R},B_{G}\in\mathbb{R}^{+}$

// Initialization

for  _$\mathbf{c}\in\left\\{\begin{pmatrix}c_{a_{1}}
&c_{a_{2}}&\dots&c_{a_{s}}\end{pmatrix}\in\mathcal{A}^{s}\right\\}$_ do

for  _$a\in[k]$_ do

$\mathcal{T}_{c_{a}\mid\mathbf{c}}\leftarrow\\{\\},~{}~{}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)\leftarrow\lambda
I_{s},~{}~{}\hat{G}_{c_{a}\mid\mathbf{c}}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)\leftarrow\mathbf{0}_{s\times
1}$

$\left(e_{c_{a}\mid\mathbf{c}}\left(\delta_{e}\right),b_{c_{a}\mid\mathbf{c}}\left(\delta_{b}\right)\right)\leftarrow
1/\epsilon$ where $\epsilon$ small

end for

end for

// Learner interaction with LGDS

for  _$t=1,2,\dots,n$_ do

if  _ $t\geq s$ _ then

// Action selection

$A_{t}\leftarrow\underset{a\in\\{1,2,\dots,k\\}}{\arg\max}\hat{G}_{c_{a}\mid\mathbf{c}}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{\top}\Xi_{t}\left(\mathbf{c}\right)+\left(e_{c_{a}\mid\mathbf{c}}\left(\delta_{e}\right)+b_{c_{a}\mid\mathbf{c}}\left(\delta_{b}\right)\right)\sqrt{\Xi_{t}\left(\mathbf{c}\right)^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}\Xi_{t}\left(\mathbf{c}\right)}$

Sample $X_{t}$ from (1)

$\mathbf{c}\leftarrow\begin{pmatrix}c_{A_{t-s}}&\dots&c_{A_{t-1}}\end{pmatrix}$

$\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}\leftarrow\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}\cup\\{t\\}$

// Update estimates

$V_{A_{t}}\left(\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}\right)\leftarrow
V_{A_{t}}\left(\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}\right)+\Xi_{t}\left(\mathbf{c}\right)\Xi_{t}\left(\mathbf{c}\right)^{\top}$

$\hat{G}_{c_{A_{t}}\mid\mathbf{c}}\left(\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}\right)\leftarrow\hat{G}_{c_{A_{t}}\mid\mathbf{c}}\left(\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}\right)^{\top}+X_{t}\Xi_{t}\left(\mathbf{c}\right)^{\top}V_{A_{t}}\left(\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}\right)^{-1}$

// Update bounds

Set $e_{c_{A_{t}}\mid\mathbf{c}}\left(\delta\right)$ and
$b_{c_{A_{t}}\mid\mathbf{c}}\left(\delta\right)$ based on (14) and (15),
respectively.

else

$A_{t}\leftarrow\mbox{Sample uniformly }a\sim[k]$

Sample $X_{t}$ from (1)

end if

end for

Algorithm 1 Uncertainty-Based System Search (UBSS)

###  4.1 Regret Performance

Algorithm 1, UBSS, has the following upper bound on regret (2). Proof is in
Appendix C.3.

######  Theorem 2.

Using Algorithm 1 and setting $\delta_{e}=\delta_{b}=\delta\in(0,1)$, regret
(2) satisfies the following inequality with a probability of at least
$(1-\delta)^{5}$:

$R_{n}\leq\sum_{t=1}^{s}\max_{c_{a}\in\mathcal{A}}\mathbb{E}\left[\left\langle
c_{a^{*}}-c_{a},z_{t}\right\rangle\right]+\sum_{a=1}^{k}2(n-s)B_{c}^{2}B_{R}^{2}\left(1-\left(1-\delta\right)^{4}\left(1-\exp\left(\frac{-4B\left(\delta\mid\mathbf{c}\right)^{2}}{2\Delta
G_{c_{a}\mid\mathbf{c}}^{\top}\Sigma_{\Xi_{t}\left(\mathbf{c}\right)}\Delta
G_{c_{a}\mid\mathbf{c}}}\right)\right)\right),$ (16)

where $\Delta G_{c_{a}\mid\mathbf{c}}\triangleq
G_{c_{a^{*}}\mid\mathbf{c}}-G_{c_{a}\mid\mathbf{c}}$,
$\Sigma_{\Xi_{t}\left(\mathbf{c}\right)}\triangleq\mathbb{E}\left[\Xi_{t}\left(\mathbf{c}\right)\Xi_{t}\left(\mathbf{c}\right)^{\top}\right]$,
and $B\left(\delta\mid\mathbf{c}\right)$ is

$B\left(\delta\mid\mathbf{c}\right)\triangleq\sqrt{2B_{R}^{2}\log\left(\frac{1}{\delta}\frac{\left(s\lambda+(n-s)\frac{\mathbb{E}\left[\left\|\Xi_{t}\left(\mathbf{c}\right)\right\|_{2}\right]}{\delta}\right)^{s/2}}{\lambda^{s/2}}\right)}\sqrt{\frac{s}{\lambda}}\frac{\mathbb{E}\left[\left\|\Xi_{t}\left(\mathbf{c}\right)\right\|_{2}\right]}{\delta}\\\
+\sqrt{n-s}\frac{B_{c}B_{R}}{\delta}\sqrt{s}\sqrt{\frac{s}{\lambda}}\frac{\mathbb{E}\left[\left\|\Xi_{t}\left(\mathbf{c}\right)\right\|_{2}\right]}{\delta}+\lambda
B_{G}\sqrt{\frac{s}{\lambda}}\frac{\mathbb{E}\left[\left\|\Xi_{t}\left(\mathbf{c}\right)\right\|_{2}\right]}{\delta}.$
(17)

Theorem 2 proves that regret increases at worst linearly, i.e.
$\mathcal{O}\left(n\right)$. If the covariance for two different actions is
large, e.g. large $\Delta G_{c_{a}\mid\mathbf{c}}$ and
$\Sigma_{\Xi_{t}\left(\mathbf{c}\right)}$ terms, then the bound will decrease.
The bound decreases exponentially as uncertainty (13) decreases.

##  5 Numerical Results

For numerical results, we generated rewards $X_{t}\in\mathbb{R}$ for each
action $\\{c_{1},c_{2}\\}$ from the following LGDS:

$\begin{cases}z_{t+1}&=\begin{pmatrix}0.9R\left(\theta\right)&I_{2}\\\
\mathbf{0}_{2\times 2}&0.9R\left(\theta\right)\end{pmatrix}z_{t}+\xi_{t}\\\
X_{t}&=\left\langle
c_{A_{t}},z_{t}\right\rangle+\eta_{t}\end{cases},~{}\begin{cases}R\left(\theta\right)&\triangleq\begin{pmatrix}\cos\theta&\sin\theta\\\
-\sin\theta&\cos\theta\end{pmatrix}\\\
c_{1}&\triangleq\begin{pmatrix}10&0&0&0\end{pmatrix}\\\
c_{2}&\triangleq\begin{pmatrix}0&10&0&0\end{pmatrix}\end{cases},$ (18)

where the process noise $\xi_{t}\sim\mathcal{N}\left(0,I_{4}\right)$ and the
measurement noise $\eta_{t}\sim\mathcal{N}\left(0,1\right)$ are sampled from
standard normal distributions. The LGDS (18) is proposed to study how the
magnitude of the error covariance matrix $P_{\overline{a}}$ impacts
performance of UBSS, where $P_{\overline{a}}$ is directly impacted by the
parameter $\theta\in[0,2\pi]$. Prior to the learner’s interaction with the
LGDS (18), $10^{4}$ time steps are computed of the LGDS (18) to set the system
to a steady state. After, the $10^{4}$ time steps, the length of the
interaction between the environment and the learner is $n=10^{4}$ rounds.
Regret (2) is used to provide a metric of performance. Parameter $s$ in
Algorithm 1, UBSS, is set to $1$ in the top left plot. For comparison, we
consider UCB [8], SW-UCB [9], and a learner that selects a random action each
round (this learner is denoted as Random). We use UCB as a comparison since
the eigenvalues of the LGDS (18) state matrix $\Gamma\in\mathbb{R}^{4\times
4}$ is Schur, implying that the reward distributions have a bounded covariance
with a mean of zero. SW-UCB is also used as a comparison since the reward is
still generated by a dynamical system. Finally, Random is used as baseline for
worst performance.

Figure 1: Comparison algorithm’s regret normalized with respect to UBSS’s
regret. A positive percent implies that UBSS has a lower regret than the
compared algorithm.

In the top left plot of Figure 1, the percentage of UBSS’s regret (2) is lower
than UCB (red), Sliding UCB (green) and Random (blue) regret is shown for each
$\theta\in[0,2\pi]$. The middle plot of Figure 1 is the minimum eigenvalue of
the Observability Gramian $\mathcal{O}$ [22] for both actions
$c_{a}\in\\{c_{1},c_{2}\\}$, which is the solution of the Lyapunov equation
$\mathcal{O}=\Gamma^{\top}\mathcal{O}\Gamma+c_{a}c_{a}^{\top}$. The bottom
plot of Figure 1 is the real part of the eigenvalue of the state matrix
$\Gamma$. In the white regions, all the comparison algorithms outperform UBSS.
Based on the plot in the middle, it appears that the low Observability Gramian
minimum eigenvalue and a positive real part of the state matrix’s eigenvalue
is the cause. For the blue regions, no algorithm outperforms Random, implying
that the rewards are too noisy to estimate/predict for the compared
algorithms. Finally, the gray regions is approximately where UBSS performs the
best, providing approximately a 10% improvement for each of the algorithms
mid-region. Based on the bottom 2 plots, this increase in performance is from
the high observability and an eigenvalue with a negative real part for the
state matrix. High observability lowers the magnitude of the error covariance
matrix $P_{\overline{a}}$, which leads to a lower regret bound of UBSS. In
addition, an eigenvalue with a negative real part for the state matrix leads
to rapid switching of the optimal action, making it difficult for UCB to
adapt. For the plot on the far right, this is the relative performance of UBSS
for each parameter $s=1,2,3$ when the LGDS system (18) parameter set to
approximately $5\pi/8$ (approximately where we see the largest improvement in
performance of UBSS in the top left plot). Therefore, it appears that as $s$
increases to $s=2,3$, regret performance of UBSS decreases. Since the number
of parameters to identify increases exponentially as $s$ increases (leading to
longer exploration times), regret performance of UBSS decreases as $s$
increases.

##  6 Conclusion

We have presented an algorithm for addressing a variation of the restless
bandit with a continuous state-space. The rewards generated by this restless
bandit variation is a LGDS. Based on the formulation, we propose to learn a
representation of the modified Kalman filter to predict the rewards for each
action. We have shown that regardless of the sequence of actions chosen, the
learned representation of the modified Kalman filter converges. It is then
proven what strategy should be used given the bound on regret, leading to an
uncertainty-based strategy.

In this work, we have not considered how the sequence of actions impact
prediction error, how to choose window size (how far the learner looks into
the past), and best obtainable performance of SMAB with LGDS environments.
First, the perturbation added for exploration only considers error of the
model and not the sequence of actions impact on the error of the prediction.
In other words, the chosen sequence of actions are myopic. Therefore, future
work will focus on the action sequence impact on the reward prediction. Next,
an important parameter in UBSS is the window size. In UBSS, this is a
parameter to set prior to the interaction with the environment. However,
questions we care to ask is how to automate the process of choosing window
size. Finally, UBSS has linear regret performance. Therefore, future work will
be to derive the best obtainable performance of any algorithm applied to a
SMAB with rewards generated by this paper’s proposed LGDS. We will then
analyze if UBSS regret performance is close or far to the best obtainable
performance.

## References

  * [1] O. Besbes, Y. Gur, and A. Zeevi, “Stochastic multi-armed-bandit problem with non-stationary rewards,” _Advances in neural information processing systems_ , vol. 27, pp. 199–207, 2014.
  * [2] A. Slivkins and E. Upfal, “Adapting to a changing environment: the brownian restless bandits.” in _COLT_ , 2008, pp. 343–354.
  * [3] I. Bogunovic, J. Scarlett, and V. Cevher, “Time-varying gaussian process bandit optimization,” in _Proceedings of the 19th International Conference on Artificial Intelligence and Statistics_ , ser. Proceedings of Machine Learning Research, A. Gretton and C. C. Robert, Eds., vol. 51. Cadiz, Spain: PMLR, 09–11 May 2016, pp. 314–323. [Online]. Available: https://proceedings.mlr.press/v51/bogunovic16.html
  * [4] Q. Chen, N. Golrezaei, and D. Bouneffouf, “Non-stationary bandits with auto-regressive temporal dependency,” in _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.
  * [5] J. Parker-Holder, V. Nguyen, and S. J. Roberts, “Provably efficient online hyperparameter optimization with population-based bandits,” _Advances in neural information processing systems_ , vol. 33, pp. 17 200–17 211, 2020\.
  * [6] J. Gornet, M. Hosseinzadeh, and B. Sinopoli, “Stochastic multi-armed bandits with non-stationary rewards generated by a linear dynamical system,” in _2022 IEEE 61st Conference on Decision and Control (CDC)_. IEEE, 2022, pp. 1460–1465.
  * [7] A. Tsiamis and G. J. Pappas, “Finite sample analysis of stochastic system identification,” in _2019 IEEE 58th Conference on Decision and Control (CDC)_. IEEE, 2019, pp. 3648–3654.
  * [8] R. Agrawal, “Sample mean based index policies by o (log n) regret for the multi-armed bandit problem,” _Advances in Applied Probability_ , vol. 27, no. 4, pp. 1054–1078, 1995.
  * [9] A. Garivier and E. Moulines, “On upper-confidence bound policies for non-stationary bandit problems,” _arXiv preprint arXiv:0805.3415_ , 2008\.
  * [10] P. Whittle, “Restless bandits: Activity allocation in a changing world,” _Journal of applied probability_ , vol. 25, no. A, pp. 287–298, 1988.
  * [11] C. Tekin and M. Liu, “Online learning of rested and restless bandits,” _IEEE Transactions on Information Theory_ , vol. 58, no. 8, pp. 5588–5611, 2012.
  * [12] R. Ortner, D. Ryabko, P. Auer, and R. Munos, “Regret bounds for restless markov bandits,” in _International conference on algorithmic learning theory_. Springer, 2012, pp. 214–228.
  * [13] S. Wang, L. Huang, and J. Lui, “Restless-ucb, an efficient and low-complexity algorithm for online restless bandits,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 11 878–11 889, 2020.
  * [14] W. Dai, Y. Gai, B. Krishnamachari, and Q. Zhao, “The non-bayesian restless multi-armed bandit: A case of near-logarithmic regret,” in _2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2011, pp. 2940–2943.
  * [15] H. Liu, K. Liu, and Q. Zhao, “Logarithmic weak regret of non-bayesian restless multi-armed bandit,” in _2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2011, pp. 1968–1971.
  * [16] Y. H. Jung and A. Tewari, “Regret bounds for thompson sampling in episodic restless bandit problems,” _Advances in Neural Information Processing Systems_ , vol. 32, 2019.
  * [17] Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári, “Improved algorithms for linear stochastic bandits,” in _Advances in Neural Information Processing Systems_ , J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger, Eds., vol. 24. Curran Associates, Inc., 2011.
  * [18] A. Gelb _et al._ , _Applied optimal estimation_. MIT press, 1974.
  * [19] M. Deistler, K. Peternell, and W. Scherrer, “Consistency and relative efficiency of subspace methods,” _Automatica_ , vol. 31, no. 12, pp. 1865–1875, 1995.
  * [20] T. Knudsen, “Consistency analysis of subspace identification methods based on a linear regression approach,” _Automatica_ , vol. 37, no. 1, pp. 81–89, 2001.
  * [21] T. Lattimore and C. Szepesvári, _Bandit algorithms_. Cambridge University Press, 2020.
  * [22] J. P. Hespanha, _Linear systems theory_. Princeton university press, 2018.
  * [23] B. Sinopoli, L. Schenato, M. Franceschetti, K. Poolla, M. Jordan, and S. Sastry, “Kalman filtering with intermittent observations,” _IEEE Transactions on Automatic Control_ , vol. 49, no. 9, pp. 1453–1464, 2004.
  * [24] S. Boucheron, G. Lugosi, and P. Massart, _Concentration inequalities: A nonasymptotic theory of independence_. Oxford university press, 2013.
  * [25] J. M. Wooldridge, _Econometric analysis of cross section and panel data_. MIT press, 2010.

##  Appendix A Proof of Lemma 1

###### Proof.

Let $P_{\overline{a}}$ be the steady-state solution of the Kalman filter (3)
such that

$P_{\overline{a}}\succeq P_{a}\mbox{ for all }c_{a}\in\mathcal{A}\mbox{ where
}P_{a}\mbox{ solves }P_{a}=g\left(P_{a},c_{a}\right).$

Based on [23], if $P_{\overline{a}}\succeq P$ for any arbitrary $P\succeq 0$,
then based on definition of $g\left(\cdot,\cdot\right)$ in (3):

$g\left(P_{\overline{a}},c_{a}\right)\succeq g\left(P,c_{a}\right),$

for any $c_{a}\in\mathcal{A}$ that is detectable with the LGDS (1). Assuming
that $P_{\overline{a}}\succeq P$, we satisfy the following inequalities
according to [23]:

$\displaystyle
P_{\overline{a}}\overset{(*)}{\succeq}g\left(P_{\overline{a}},c_{A_{t}}\right)$
$\displaystyle=\left(\Gamma-\Gamma
L_{A_{t}}c_{A_{t}}^{\top}\right)P_{\overline{a}}\left(\Gamma-\Gamma
L_{A_{t}}c_{A_{t}}^{\top}\right)^{\top}+Q+\sigma^{2}\Gamma
L_{A_{t}}L_{A_{t}}^{\top}\Gamma^{\top}$
$\displaystyle\succeq\left(\Gamma-\Gamma
L_{A_{t}}c_{A_{t}}^{\top}\right)P\left(\Gamma-\Gamma
L_{A_{t}}c_{A_{t}}^{\top}\right)^{\top}+Q+\sigma^{2}\Gamma
L_{A_{t}}L_{A_{t}}^{\top}\Gamma^{\top}.$

For $(*)$, assume for proof of contradiction that
$g\left(P_{\overline{a}},c_{A_{t}}\right)\succeq P_{\overline{a}}$. Based on
[23], then
$g\left(g\left(P_{\overline{a}},c_{A_{t}}\right),c_{A_{t}}\right)\succeq
g\left(P_{\overline{a}},c_{A_{t}}\right)$, where the iteration will either
diverge to infinity or $P_{A_{t}}$. However, we assumed that
$P_{\overline{a}}\succeq P_{A_{t}}$ and the steady-state solution
$P_{A_{t}}=g\left(P_{A_{t}},c_{A_{t}}\right)$ exists from Assumption 3. Since
there is a contradiction, $(*)$ is true. Therefore, based on above, let there
be the modified Kalman filter (5) and the error covariance matrix
$P_{t}^{\prime}\triangleq\mathbb{E}\left[\left(z_{t}-\hat{z}_{t}^{\prime}\right)\left(z_{t}-\hat{z}_{t}^{\prime}\right)^{\top}\mid\mathcal{F}_{t-1}\right]$.
The iteration of $P_{t}^{\prime}$ is

$P_{t+1}^{\prime}=\left(\Gamma-\Gamma
L_{A_{t}}c_{A_{t}}^{\top}\right)P_{t}^{\prime}\left(\Gamma-\Gamma
L_{A_{t}}c_{A_{t}}^{\top}\right)^{\top}+Q+\sigma^{2}\Gamma
L_{A_{t}}L_{A_{t}}^{\top}\Gamma^{\top},$ (19)

where it is clear from arguments above that $P_{\overline{a}}\succeq
P_{t}^{\prime}$ and $P_{\overline{a}}\succeq P_{t+1}^{\prime}$. ∎

##  Appendix B Proof of Theorem 1

###### Proof.

The following is true based on Lemma 1 and Assumption 3:

  * •

The matrix pair $\left(\Gamma,Q^{1/2}\right)$ is controllable.

  * •

The matrix $\sigma^{2}\Gamma L_{A_{t}}L_{A_{t}}^{\top}\Gamma^{\top}\succeq 0$.

  * •

The iteration (19) is bounded by $P_{\overline{a}}$ and is monotonic.

Therefore, the matrix $\Gamma-\Gamma L_{A_{t}}c_{A_{t}}^{\top}$ is stable. In
addition, there exists an action $c_{A_{t}}\in\mathcal{A}$ such that the error
$\gamma_{A_{t}}\sim\mathcal{N}\left(0,c_{A_{t}}^{\top}P_{t}^{\prime}c_{A_{t}}+\sigma\right)$
has the following upper-bound

$c_{A_{t}}^{\top}P_{t}^{\prime}c_{A_{t}}+\sigma\leq
c_{A_{t}}^{\top}P_{\overline{a}}c_{A_{t}}+\sigma.$

∎

##  Appendix C Rationale behind OSS

To develop an algorithm for LGDS restless bandits (1), we propose the
following methodology. First, we will propose that actions should be chosen
based on the following optimization problem

$\underset{a\in[k]}{\arg\max}~{}\hat{G}_{c_{a}\mid\mathbf{c}}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{\top}\Xi_{t}\left(\mathbf{c}\right)+u_{a},$
(20)

where
$\hat{G}_{c_{a}\mid\mathbf{c}}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{\top}\Xi_{t}\left(\mathbf{c}\right)$
is an Exploitation term (which action the learner predicts to have the highest
reward) and an arbitrary term $u_{a}$ that is an Exploration term (how much
should the learner continue exploring this action). We first prove the regret
bound as a function of $u_{a}$. We then design $u_{a}$ such that the regret
bound is minimized.

In Subsection C.1, the model error bound of
$\hat{G}_{c_{a}\mid\mathbf{c}}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)$
is proven in Theorem 3. To prove Theorem 3, we provide Lemma 2. In Subsection
C.2, prediction error
$\hat{G}_{c_{a}\mid\mathbf{c}}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{\top}\Xi_{t}\left(\mathbf{c}\right)$
is proven. Theorem 4 proves the bound of the following difference:

$\hat{G}_{c_{a}\mid\mathbf{c}}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{\top}\Xi_{t}\left(\mathbf{c}\right)-G_{c_{a}\mid\mathbf{c}}^{\top}\Xi_{t}\left(\mathbf{c}\right).$
(21)

Lemma 3 is then provided to prove the rate of convergence for prediction error
that is derived in Theorem 4. Finally, Subsection C.3 provides proofs of
Algorithm 1 regret bound. We first prove a regret bound if actions are chosen
based on optimization problem (20). Based on the derived bound, we propose
what value $u_{a}$ should be set to in (20).

###  C.1 Model Error

The following lemma is provided which will be used for proving Theorem 3.

######  Lemma 2.

Let
$\hat{G}_{c_{a}\mid\mathbf{c}}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)$
and $G_{c_{a}\mid\mathbf{c}}$ be as in (10) and (8), respectively. Then, the
matrix of the bias terms $\mathbf{B}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}$
satisfies the following inequality with a probability of at least
$1-\delta_{b}$ (the failure probability value $\delta_{b}$ is assumed to be in
the open interval $(0,1)$):

$\left\|\mathbf{Z}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}\mathbf{B}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}^{\top}\right\|_{V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}}\leq\sqrt{N_{a}}\frac{B_{c}B_{R}}{\delta_{b}}\sqrt{\mbox{tr}\left(I-\lambda
V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}\right)}.$ (22)

###### Proof.

According to (9),
$\left\|\mathbf{Z}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}\mathbf{B}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}^{\top}\right\|_{V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}}$
can be expressed as

$\left\|\mathbf{Z}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}\mathbf{B}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}^{\top}\right\|_{V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}}=\left\|\sum_{t\in\mathcal{T}_{c_{a}\mid\mathbf{c}}}\Xi_{t}\left(\mathbf{c}\right)\beta_{A_{t}}\right\|_{V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}}.$
(23)

Based on the triangle and Cauchy-Schwarz inequalities, (23) has the following
bound

$\displaystyle\left\|\mathbf{Z}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}\mathbf{B}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}^{\top}\right\|_{V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}}$
$\displaystyle=\left\|\Xi_{t_{1}}\left(\mathbf{c}\right)^{\top}\beta_{a;t_{1}}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1/2}+\dots+\Xi_{t_{N_{a}}}\left(\mathbf{c}\right)^{\top}\beta_{a;t_{N_{a}}}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1/2}\right\|_{2}$
$\displaystyle\overset{(*)}{\leq}\left\|\Xi_{t_{1}}\left(\mathbf{c}\right)^{\top}\beta_{a;t_{1}}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1/2}\right\|_{2}+\dots$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+\left\|\Xi_{t_{N_{a}}}\left(\mathbf{c}\right)^{\top}\beta_{a;t_{N_{a}}}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1/2}\right\|_{2}$
$\displaystyle\overset{(**)}{\leq}\left|\beta_{a;t_{1}}\right|\left\|\Xi_{t_{1}}\left(\mathbf{c}\right)^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1/2}\right\|_{2}+\dots$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+\left|\beta_{a;t_{N_{a}}}\right|\left\|\Xi_{t_{N_{a}}}\left(\mathbf{c}\right)^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1/2}\right\|_{2},$
$\Rightarrow\left\|\mathbf{Z}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}\mathbf{B}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}^{\top}\right\|_{V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}}\leq\sum_{i=1}^{N_{a}}\left|\beta_{a;t_{i}}\right|\left\|\Xi_{t_{i}}\left(\mathbf{c}\right)^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1/2}\right\|_{2},$
(24)

where $(*)$ uses the triangle inequality and $(**)$ uses the Cauchy-Schwarz
inequality. The term $\left|\beta_{A_{t}}\right|$,
$t\in\mathcal{T}_{c_{a}\mid\mathbf{c}}$ has the following bound using Cauchy-
Schwarz inequality

$\displaystyle\left|\beta_{A_{t}}\right|$ $\displaystyle=\left|\left\langle
c_{a},\left(\Gamma-\Gamma
L_{a_{t-1}}c_{a_{t-1}}^{\top}\right)\cdots\left(\Gamma-\Gamma
L_{a_{t-s}}c_{a_{t-s}}^{\top}\right)\hat{z}_{t-s}\right\rangle\right|$
$\displaystyle\leq\left\|c_{a}\right\|_{2}\left\|\left(\Gamma-\Gamma
L_{a_{t-1}}c_{a_{t-1}}^{\top}\right)\cdots\left(\Gamma-\Gamma
L_{a_{t-s}}c_{a_{t-s}}^{\top}\right)\hat{z}_{t-s}\right\|_{2}.$ (25)

We can upper-bound the right side of (25) with
$\left\|\hat{z}_{t}\right\|_{2}$. First, define
$\hat{Z}_{t}\triangleq\mathbb{E}\left[\hat{z}_{t}\hat{z}_{t}^{\top}\mid\mathcal{F}_{t-1}\right]$
to get the following two iteration

$\displaystyle\hat{Z}_{t-s+1}^{[1]}$ $\displaystyle=\left(\Gamma-\Gamma
L_{a_{t-s}}c_{a_{t-s}}^{\top}\right)\hat{Z}_{t-s}^{[1]}\left(\Gamma-\Gamma
L_{a_{t-s}}c_{a_{t-s}}^{\top}\right)^{\top}+\mathbb{E}\left[X_{t-s}^{2}\right]\Gamma
L_{a_{t-s}}L_{a_{t-s}}^{\top}\Gamma^{\top}$
$\displaystyle\hat{Z}_{t-s+1}^{[2]}$ $\displaystyle=\left(\Gamma-\Gamma
L_{a_{t-s}}c_{a_{t-s}}^{\top}\right)\hat{Z}_{t-s}^{[2]}\left(\Gamma-\Gamma
L_{a_{t-s}}c_{a_{t-s}}^{\top}\right)^{\top}$

where $\sqrt{\mbox{tr}\left(\hat{Z}_{t}^{[1]}\right)}$ and
$\sqrt{\mbox{tr}\left(\hat{Z}_{t}^{[2]}\right)}$ are equal to

$\displaystyle\sqrt{\mbox{tr}\left(\hat{Z}_{t}^{[1]}\right)}$
$\displaystyle=\left\|\hat{z}_{t}\right\|_{2}$ (26)
$\displaystyle\sqrt{\mbox{tr}\left(\hat{Z}_{t}^{[2]}\right)}$
$\displaystyle=\left\|\left(\Gamma-\Gamma
L_{a_{t-1}}c_{a_{t-1}}^{\top}\right)\cdots\left(\Gamma-\Gamma
L_{a_{t-s}}c_{a_{t-s}}^{\top}\right)\hat{z}_{t-s}\right\|_{2}.$ (27)

We know that $\Gamma-\Gamma L_{a_{t}}c_{a_{t}}^{\top}$ is stable for any
$c_{A_{t}}\in\mathcal{A}$ based on Theorem 1. Therefore, based on (26) and
(27),
$\sqrt{\mbox{tr}\left(\hat{Z}_{t}^{[1]}\right)}\succeq\sqrt{\mbox{tr}\left(\hat{Z}_{t}^{[2]}\right)}$
implying that

$\left\|\left(\Gamma-\Gamma
L_{a_{t-1}}c_{a_{t-1}}^{\top}\right)\cdots\left(\Gamma-\Gamma
L_{a_{t-s}}c_{a_{t-s}}^{\top}\right)\hat{z}_{t-s}\right\|_{2}\leq\sqrt{\mbox{tr}\left(\hat{Z}_{t}\right)}=\left\|\hat{z}_{t}\right\|_{2},$

To bound $\left\|\hat{z}_{t}\right\|_{2}$, assumption 6 states that
$\sqrt{\mbox{tr}\left(\mathbb{E}\left[z_{t}z_{t}^{\top}\right]\right)}\leq
B_{R}$. Since $z_{t}=\hat{z}_{t}+e_{t}$ and by the orthogonality principle

$\mbox{tr}\left(\mathbb{E}\left[\hat{z}_{t}e_{t}^{\top}+e_{t}\hat{z}_{t}^{\top}\right]\right)=0,$

then using $Z_{t}$ in (22),

$\displaystyle Z_{t}=\mathbb{E}\left[z_{t}z_{t}^{\top}\right]$
$\displaystyle=\mathbb{E}\left[\left(\hat{z}_{t}+e_{t}\right)\left(\hat{z}_{t}+e_{t}\right)^{\top}\mid\mathcal{F}_{t-1}\right]$
$\displaystyle=\mathbb{E}\left[\hat{z}_{t}\hat{z}_{t}^{\top}+\hat{z}_{t}e_{t}^{\top}+e_{t}\hat{z}_{t}^{\top}+e_{t}e_{t}^{\top}\mid\mathcal{F}_{t-1}\right]$
$\displaystyle=\mathbb{E}\left[\hat{z}_{t}\hat{z}_{t}^{\top}\mid\mathcal{F}_{t-1}\right]+\mathbb{E}\left[\hat{z}_{t}e_{t}^{\top}+e_{t}\hat{z}_{t}^{\top}\mid\mathcal{F}_{t-1}\right]+\mathbb{E}\left[e_{t}e_{t}^{\top}\mid\mathcal{F}_{t-1}\right]$
$\displaystyle=\mathbb{E}\left[\hat{z}_{t}\hat{z}_{t}^{\top}\mid\mathcal{F}_{t-1}\right]+\mathbb{E}\left[e_{t}e_{t}^{\top}\mid\mathcal{F}_{t-1}\right]$
$\displaystyle=\hat{Z}_{t}+P_{t},$

where
$\hat{Z}_{t}\triangleq\mathbb{E}\left[z_{t}z_{t}^{\top}\mid\mathcal{F}_{t-1}\right]$
and
$P_{t}\triangleq\mathbb{E}\left[e_{t}e_{t}^{\top}\mid\mathcal{F}_{t-1}\right]$.
Since $\hat{Z}_{t}\succeq 0$ and $P_{t}\succeq 0$, then

$\displaystyle\sqrt{\mbox{tr}\left(Z_{t}\right)}=\sqrt{\mbox{tr}\left(\hat{Z}_{t}+P_{t}\right)}\geq\sqrt{\mbox{tr}\left(\hat{Z}_{t}\right)}$
$\displaystyle\Rightarrow\sqrt{\mbox{tr}\left(\hat{Z}_{t}\right)}\leq B_{R}.$

Therefore, using the Markov inequality [24], with a probability of at least
$1-\delta_{b}$,

$\left|\beta_{A_{t}}\right|\leq\left\|c_{a}\right\|_{2}\frac{\sqrt{\mbox{tr}\left(\mathbb{E}\left[z_{t}z_{t}^{\top}\right]\right)}}{\delta_{b}}\leq\left\|c_{a}\right\|_{2}\frac{B_{R}}{\delta_{b}}\leq\frac{B_{c}B_{R}}{\delta_{b}}.$
(28)

Using inequality (28), inequality (24) can be rewritten as

$\displaystyle\left\|\mathbf{Z}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}\mathbf{B}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}^{\top}\right\|_{V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}}$
$\displaystyle\leq\sum_{i=1}^{N_{a}}\frac{B_{c}B_{R}}{\delta_{b}}\left\|\Xi_{t_{i}}\left(\mathbf{c}\right)^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1/2}\right\|_{2}$
$\displaystyle=\sum_{i=1}^{N_{a}}\frac{B_{c}B_{R}}{\delta_{b}}\sqrt{\mbox{tr}\left(V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}\Xi_{t_{i}}\left(\mathbf{c}\right)\Xi_{t_{i}}\left(\mathbf{c}\right)^{\top}\right)}$
$\displaystyle\leq\sum_{i=1}^{N_{a}}\frac{B_{c}B_{R}}{\delta_{b}}\sqrt{\mbox{tr}\left(V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}\Xi_{t_{i}}\left(\mathbf{c}\right)\Xi_{t_{i}}\left(\mathbf{c}\right)^{\top}\right)\cdot
1}$
$\displaystyle\overset{(*)}{\leq}\frac{B_{c}B_{R}}{\delta_{b}}\sqrt{\sum_{i=1}^{N_{a}}1}\sqrt{\sum_{i=1}^{N_{a}}\mbox{tr}\left(V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}\Xi_{t_{i}}\left(\mathbf{c}\right)\Xi_{t_{i}}\left(\mathbf{c}\right)^{\top}\right)}$
$\displaystyle=\sqrt{N_{a}}\frac{B_{c}B_{R}}{\delta_{b}}\sqrt{\mbox{tr}\left(V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}\sum_{i=1}^{N_{a}}\Xi_{t_{i}}\left(\mathbf{c}\right)\Xi_{t_{i}}\left(\mathbf{c}\right)^{\top}\right)}$
$\displaystyle=\sqrt{N_{a}}\frac{B_{c}B_{R}}{\delta_{b}}\sqrt{\mbox{tr}\left(V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}\left(V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)-\lambda
I\right)\right)},$
$\Rightarrow\left\|\mathbf{Z}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}\mathbf{B}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}^{\top}\right\|_{V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}}\leq\sqrt{N_{a}}\frac{B_{c}B_{R}}{\delta_{b}}\sqrt{\mbox{tr}\left(I-\lambda
V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}\right)},$

where $(*)$ uses the Cauchy-Schwarz inequality. Since
$V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)\succeq\lambda I$ based on
(11), then the difference $I-\lambda
V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)\succeq 0$. Therefore, no
further effort is needed to show that inequality (22) is satisfied with a
probability of at least $1-\delta_{b}$.

∎

Using Lemma 2, Theorem 3 can be proven.

######  Theorem 3.

Let $\hat{G}_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)$ be identified
based on (10) where the reward
$\mathbf{X}_{\mathcal{T}_{c_{a}\mid\mathbf{c}}}$ has expression (9). Then, the
following inequality is satisfied with a probability of at least
$\left(1-\delta_{e}\right)\left(1-\delta_{b}\right)$, where
$\delta_{e},\delta_{b}\in(0,1)$ are designed parameters for tolerated failure
probabilities:

$\left\|\hat{G}_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)-G_{c_{a}\mid\mathbf{c}}\right\|_{V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)}\leq
e_{c_{a}\mid\mathbf{c}}\left(\delta_{e}\right)+b_{c_{a}\mid\mathbf{c}}\left(\delta_{b}\right),$
(29)

where $e_{c_{a}\mid\mathbf{c}}\left(\delta_{e}\right)$ and
$b_{c_{a}\mid\mathbf{c}}\left(\delta_{b}\right)$ are defined in (14) and (15),
respectively.

###### Proof.

Let $\mathbf{X}_{\mathcal{T}_{c_{a}\mid\mathbf{c}}}$ be expressed using (9).
The norm
$\left\|\hat{G}_{c_{a}\mid\mathbf{c}}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)-G_{c_{a}\mid\mathbf{c}}\right\|_{2}$
can be expressed the following way

$\hat{G}_{c_{a}\mid\mathbf{c}}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)-G_{c_{a}\mid\mathbf{c}}=-\lambda
G_{c_{a}\mid\mathbf{c}}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}+\left(\mathbf{B}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}+\mathbf{E}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}\right)\mathbf{Z}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1},$

which implies that:

$\displaystyle\left(\hat{G}_{c_{a}\mid\mathbf{c}}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{\top}-G_{c_{a}\mid\mathbf{c}}^{\top}\right)V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)$
$\displaystyle=-\lambda
G_{c_{a}\mid\mathbf{c}}^{\top}+\left(\mathbf{B}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}+\mathbf{E}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}\right)\mathbf{Z}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}^{\top},$
$\displaystyle\left(\hat{G}_{c_{a}\mid\mathbf{c}}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)-G_{c_{a}\mid\mathbf{c}}\right)^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)$
$\displaystyle=\left(-\lambda
G_{c_{a}\mid\mathbf{c}}+\mathbf{Z}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}\left(\mathbf{B}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}+\mathbf{E}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}\right)^{\top}\right)^{\top},$

and consequently:

$\left\|\hat{G}_{c_{a}\mid\mathbf{c}}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)-G_{c_{a}\mid\mathbf{c}}\right\|_{V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)}=\left\|-\lambda
G_{c_{a}\mid\mathbf{c}}+\mathbf{Z}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}\left(\mathbf{B}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}+\mathbf{E}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}\right)^{\top}\right\|_{V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}}.$

Using the triangle inequality, it follows from (C.1) that:

$\left\|\hat{G}_{c_{a}\mid\mathbf{c}}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)-G_{c_{a}\mid\mathbf{c}}\right\|_{V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)}\leq\left\|\lambda
G_{c_{a}\mid\mathbf{c}}\right\|_{V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}}+\left\|\mathbf{Z}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}\mathbf{B}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}^{\top}\right\|_{V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}}\\\
+\left\|\mathbf{Z}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}\mathbf{E}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}^{\top}\right\|_{V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}}.$
(30)

As it is shown in Lemma 2, inequality (22) is satisfied with a probability of
at least $1-\delta$. For the term $\varepsilon_{a;\tau}$, since
$\varepsilon_{a;\tau}$ is conditionally $B_{R}$-sub-Gaussian on
$\mathcal{F}_{t-1}$ and $\Xi_{t}$ is $\mathcal{F}_{t-1}$ measurable, then the
conditions described in [17], Theorem 1, are satisfied. Therefore, the
following inequality is satisfied with a probability of at least
$1-\delta_{e}$:

$\left\|\mathbf{Z}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}\mathbf{E}_{\mathcal{T}_{c_{A_{t}}\mid\mathbf{c}}}^{\top}\right\|_{V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}}\leq\sqrt{2B_{R}^{2}\log\left(\frac{1}{\delta_{e}}\frac{\det(V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right))^{1/2}}{\det(\lambda
I)^{1/2}}\right)}.$

Finally, using Assumption 5, the term $\lambda G_{c_{a}\mid\mathbf{c}}$ can be
bounded using the Cauchy-Schwarz inequality

$\displaystyle\left\|\lambda
G_{c_{a}\mid\mathbf{c}}\right\|_{V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}}$
$\displaystyle\leq\left|\lambda\right|\sqrt{\mbox{tr}\left(V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}\right)}\left\|G_{c_{a}\mid\mathbf{c}}\right\|_{2}$
$\displaystyle\leq\left|\lambda\right|\sqrt{\mbox{tr}\left(V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}\right)}B_{G}$

Therefore, the bound (29) is obtained. ∎

Theorem 3 states that with a probability of at least
$\left(1-\delta_{b}\right)\left(1-\delta_{e}\right)$, the weighted-norm in
(29) is upper-bounded by two terms, (14) and (15). Note that the terms
$(\delta_{e},\delta_{b})$ are within the interval $(0,1)$, where the closer
$(\delta_{e},\delta_{b})$ are to $0$, the larger the terms (14) and (15) are.
The opposite occurs if $(\delta_{e},\delta_{b})$ are closer to $1$.

###  C.2 Prediction Error

Using Theorem 3, we can prove a bound on the prediction error (21).

######  Theorem 4.

With a probability of at least
$\left(1-\delta_{e}\right)\left(1-\delta_{b}\right)$, the following inequality
is satisfied

$\hat{G}_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{\top}\Xi\left(\mathbf{c}\right)-G_{c_{a}\mid\mathbf{c}}^{\top}\Xi\left(\mathbf{c}\right)\leq\sigma\left(\delta_{e},\delta_{b},c_{a}\mid\mathbf{c}\right),$
(31)

where $\sigma\left(\delta_{e},\delta_{b},c_{a}\mid\mathbf{c}\right)$ is
defined to be

$\sigma\left(\delta_{e},\delta_{b},c_{a}\mid\mathbf{c}\right)\triangleq\left(e_{c_{a}\mid\mathbf{c}}\left(\delta_{e}\right)+b_{c_{a}\mid\mathbf{c}}\left(\delta_{b}\right)\right)\sqrt{\Xi_{t}\left(\mathbf{c}\right)^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}\Xi_{t}\left(\mathbf{c}\right)}.$
(32)

###### Proof.

Let there be the following optimization problem

$\begin{array}[]{cc}\underset{a\in[k]}{\arg\max}&\tilde{G}_{c_{a}\mid\mathbf{c}}^{\top}\Xi\left(\mathbf{c}\right)\\\
\mbox{s.t.}&\left\|\hat{G}_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)-\tilde{G}_{c_{a}\mid\mathbf{c}}\right\|_{V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)}^{2}\leq\left(e_{c_{a}\mid\mathbf{c}}\left(\delta_{e}\right)+b_{c_{a}\mid\mathbf{c}}\left(\delta_{b}\right)\right)^{2}\end{array}.$
(33)

To solve (33), we have the following Lagrangian

$L\left(\tilde{G}_{c_{a}\mid\mathbf{c}},\alpha\right)=\tilde{G}_{c_{a}\mid\mathbf{c}}^{\top}\Xi\left(\mathbf{c}\right)-\frac{\alpha}{2}\left(\left\|\hat{G}_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)-\tilde{G}_{c_{a}\mid\mathbf{c}}\right\|_{V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)}^{2}-\left(e_{c_{a}\mid\mathbf{c}}\left(\delta_{e}\right)+b_{c_{a}\mid\mathbf{c}}\left(\delta_{b}\right)\right)^{2}\right),$

$L\left(\tilde{G}_{c_{a}\mid\mathbf{c}},\alpha\right)=\tilde{G}_{c_{a}\mid\mathbf{c}}^{\top}\Xi\left(\mathbf{c}\right)\\\
-\frac{\alpha}{2}\left(\left(\hat{G}_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)-\tilde{G}_{c_{a}\mid\mathbf{c}}\right)^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)\left(\hat{G}_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)-\tilde{G}_{c_{a}\mid\mathbf{c}}\right)-\left(e_{c_{a}\mid\mathbf{c}}\left(\delta_{e}\right)+b_{c_{a}\mid\mathbf{c}}\left(\delta_{b}\right)\right)^{2}\right),$
(34)

$L\left(\tilde{G}_{c_{a}\mid\mathbf{c}},\alpha\right)=\tilde{G}_{c_{a}\mid\mathbf{c}}^{\top}\Xi\left(\mathbf{c}\right)-\frac{\alpha}{2}\hat{G}_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)\hat{G}_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)\\\
+\alpha\hat{G}_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)\tilde{G}_{c_{a}\mid\mathbf{c}}-\frac{\alpha}{2}\tilde{G}_{c_{a}\mid\mathbf{c}}^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)\tilde{G}_{c_{a}\mid\mathbf{c}}+\frac{\alpha}{2}\left(e_{c_{a}\mid\mathbf{c}}\left(\delta_{e}\right)+b_{c_{a}\mid\mathbf{c}}\left(\delta_{b}\right)\right)^{2}.$
(35)

Therefore, the partial derivatives of the Lagrangian are

$\displaystyle\frac{\partial
L\left(\tilde{G}_{c_{a}\mid\mathbf{c}},\alpha\right)}{\partial\tilde{G}_{c_{a}\mid\mathbf{c}}}$
$\displaystyle=\Xi\left(\mathbf{c}\right)^{\top}-\alpha\tilde{G}_{c_{a}\mid\mathbf{c}}^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)+\alpha\hat{G}_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)$
$\displaystyle\frac{\partial
L\left(\tilde{G}_{c_{a}\mid\mathbf{c}},\alpha\right)}{\partial\alpha}$
$\displaystyle=-\frac{1}{2}\left(\left\|\hat{G}_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)-\tilde{G}_{c_{a}\mid\mathbf{c}}\right\|_{V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)}^{2}+\left(e_{c_{a}\mid\mathbf{c}}\left(\delta_{e}\right)+b_{c_{a}\mid\mathbf{c}}\left(\delta_{b}\right)\right)^{2}\right).$

Setting $\partial
L\left(\tilde{G}_{c_{a}\mid\mathbf{c}},\alpha\right)/\partial\tilde{G}_{c_{a}\mid\mathbf{c}}=0$
and solving $\tilde{G}_{c_{a}\mid\mathbf{c}}$ provides

$\displaystyle\Xi\left(\mathbf{c}\right)^{\top}-\alpha\tilde{G}_{c_{a}\mid\mathbf{c}}^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)+\alpha\hat{G}_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)$
$\displaystyle=0$
$\displaystyle\Xi\left(\mathbf{c}\right)^{\top}+\alpha\hat{G}_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)$
$\displaystyle=\alpha\tilde{G}_{c_{a}\mid\mathbf{c}}^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right),$
$\Rightarrow\tilde{G}_{c_{a}\mid\mathbf{c}}^{\top}=\Xi\left(\mathbf{c}\right)^{\top}\frac{V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}}{\alpha}+\hat{G}_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{\top}.$
(36)

Plugging in $\tilde{G}_{c_{a}\mid\mathbf{c}}$ in (35) provides

$\displaystyle\frac{1}{2}\left(\left\|\hat{G}_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)-\left(\hat{G}_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)-\frac{V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}}{\alpha}\Xi\left(\mathbf{c}\right)\right)\right\|_{V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)}^{2}-\left(e_{c_{a}\mid\mathbf{c}}\left(\delta_{e}\right)+b_{c_{a}\mid\mathbf{c}}\left(\delta_{b}\right)\right)^{2}\right)$
$\displaystyle=0$
$\displaystyle\frac{1}{2}\left(\left\|\frac{V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}}{\alpha}\Xi\left(\mathbf{c}\right)\right\|_{V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)}^{2}-\left(e_{c_{a}\mid\mathbf{c}}\left(\delta_{e}\right)+b_{c_{a}\mid\mathbf{c}}\left(\delta_{b}\right)\right)^{2}\right)$
$\displaystyle=0$
$\displaystyle\frac{1}{2}\left(\frac{\Xi\left(\mathbf{c}\right)^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}\Xi\left(\mathbf{c}\right)}{\alpha^{2}}-\left(e_{c_{a}\mid\mathbf{c}}\left(\delta_{e}\right)+b_{c_{a}\mid\mathbf{c}}\left(\delta_{b}\right)\right)^{2}\right)$
$\displaystyle=0$
$\displaystyle\frac{1}{2}\left(\frac{\Xi\left(\mathbf{c}\right)^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}\Xi\left(\mathbf{c}\right)}{\alpha^{2}}-\left(e_{c_{a}\mid\mathbf{c}}\left(\delta_{e}\right)+b_{c_{a}\mid\mathbf{c}}\left(\delta_{b}\right)\right)^{2}\right)$
$\displaystyle=0,$
$\displaystyle\frac{\Xi\left(\mathbf{c}\right)^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}\Xi\left(\mathbf{c}\right)}{\alpha^{2}}$
$\displaystyle=\left(e_{c_{a}\mid\mathbf{c}}\left(\delta_{e}\right)+b_{c_{a}\mid\mathbf{c}}\left(\delta_{b}\right)\right)^{2}$
$\displaystyle\frac{\Xi\left(\mathbf{c}\right)^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}\Xi\left(\mathbf{c}\right)}{\left(e_{c_{a}\mid\mathbf{c}}\left(\delta_{e}\right)+b_{c_{a}\mid\mathbf{c}}\left(\delta_{b}\right)\right)^{2}}$
$\displaystyle=\alpha^{2},$
$\Rightarrow\alpha=\sqrt{\frac{\Xi\left(\mathbf{c}\right)^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}\Xi\left(\mathbf{c}\right)}{\left(e_{c_{a}\mid\mathbf{c}}\left(\delta_{e}\right)+b_{c_{a}\mid\mathbf{c}}\left(\delta_{b}\right)\right)^{2}}}.$
(37)

Finally, plugging in (37) and (36) into
$\tilde{G}_{c_{a}\mid\mathbf{c}}^{\top}\Xi\left(\mathbf{c}\right)$ provides

$\tilde{G}_{c_{a}\mid\mathbf{c}}^{\top}\Xi\left(\mathbf{c}\right)=\hat{G}_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{\top}\Xi\left(\mathbf{c}\right)+\Xi\left(\mathbf{c}\right)^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}\Xi\left(\mathbf{c}\right)\sqrt{\frac{\left(e_{c_{a}\mid\mathbf{c}}\left(\delta_{e}\right)+b_{c_{a}\mid\mathbf{c}}\left(\delta_{b}\right)\right)^{2}}{\Xi\left(\mathbf{c}\right)^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}\Xi\left(\mathbf{c}\right)}}.$

The solution therefore for (33) is

$\hat{G}_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{\top}\Xi\left(\mathbf{c}\right)+\left(e_{c_{a}\mid\mathbf{c}}\left(\delta_{e}\right)+b_{c_{a}\mid\mathbf{c}}\left(\delta_{b}\right)\right)\sqrt{\Xi\left(\mathbf{c}\right)^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}\Xi\left(\mathbf{c}\right)}.$
(38)

If we define $\sigma\left(\delta_{e},\delta_{b},c_{a}\mid\mathbf{c}\right)$ to
be (32), then the inequality (31) is satisfied with a probability of at least
$\left(1-\delta_{e}\right)\left(1-\delta_{b}\right)$. ∎

The following lemma is provided for proving the bound of (32).

######  Lemma 3.

The upper bound of
$\sigma\left(\delta_{e},\delta_{b},c_{a}\mid\mathbf{c}\right)$ is satisfied
with a probability of at least $1-\delta$ where the bound is

$\sigma\left(\delta_{e},\delta_{b},c_{a}\mid\mathbf{c}\right)\leq
B\left(\delta\mid\mathbf{c}\right),$ (39)

where $B\left(\delta\mid\mathbf{c}\right)$ is defined to be (17).

###### Proof.

The upper bound of
$\sigma\left(\delta_{e},\delta_{b},c_{a}\mid\mathbf{c}\right)$ is as follows:
given that the following inequality is satisfied with a probability of least
$1-\delta$:

$\left\|\Xi_{t}\left(\mathbf{c}\right)\right\|_{2}\leq\frac{\mathbb{E}\left[\left\|\Xi_{t}\left(\mathbf{c}\right)\right\|_{2}\right]}{\delta},$
(40)

then according to Lemma 11 in [17],
$e_{c_{a}\mid\mathbf{c}}\left(\delta_{e}\right)$ is upper bounded as (with a
probability of at least $1-\delta$)

$\displaystyle e_{c_{a}\mid\mathbf{c}}\left(\delta_{e}\right)$
$\displaystyle\leq\sqrt{2B_{R}^{2}\log\left(\frac{1}{\delta_{e}}\frac{\left(\mbox{tr}\left(\lambda
I_{s}\right)+\left|\mathcal{T}_{c_{a}\mid\mathbf{c}}\right|\frac{\mathbb{E}\left[\left\|\Xi_{t}\left(\mathbf{c}\right)\right\|_{2}\right]}{\delta}\right)^{s/2}}{\sqrt{\det\left(\lambda
I_{s}\right)}}\right)}$
$\displaystyle\leq\sqrt{2B_{R}^{2}\log\left(\frac{1}{\delta_{e}}\frac{\left(s\lambda+(n-s)\frac{\mathbb{E}\left[\left\|\Xi_{t}\left(\mathbf{c}\right)\right\|_{2}\right]}{\delta}\right)^{s/2}}{\lambda^{s/2}}\right)}.$

The term $b_{c_{a}\mid\mathbf{c}}\left(\delta_{b}\right)$ is based on bound
(22). To bound $\sqrt{\mbox{tr}\left(I_{s}-\lambda
V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}\right)}$ in (22),
note that since
$V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)\succeq\lambda I$, then

$\sqrt{\mbox{tr}\left(I_{s}-\lambda
V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}\right)}\leq\sqrt{\mbox{tr}\left(I_{s}\right)}=\sqrt{s}.$

Therefore, we have the upper bound of
$b_{c_{a}\mid\mathbf{c}}\left(\delta_{b}\right)$:

$b_{c_{a}\mid\mathbf{c}}\left(\delta_{b}\right)\leq\sqrt{n-s}\frac{B_{c}B_{R}}{\delta_{b}}\sqrt{s}.$

Finally, the term
$\sqrt{\Xi_{t}\left(\mathbf{c}\right)^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}\Xi_{t}\left(\mathbf{c}\right)}$
has the following bound with a probability of at least $1-\delta$

$\displaystyle\sqrt{\Xi_{t}\left(\mathbf{c}\right)^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}\Xi_{t}\left(\mathbf{c}\right)}$
$\displaystyle\leq\sqrt{\mbox{tr}\left(V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}\right)}\left\|\Xi_{t}\left(\mathbf{c}\right)\right\|_{2}$
$\displaystyle\leq\sqrt{\mbox{tr}\left(\frac{I_{s}}{\lambda}\right)}\left\|\Xi_{t}\left(\mathbf{c}\right)\right\|_{2},$
$\Rightarrow\sqrt{\Xi_{t}\left(\mathbf{c}\right)^{\top}V_{a}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{-1}\Xi_{t}\left(\mathbf{c}\right)}\leq\sqrt{\frac{s}{\lambda}}\frac{\mathbb{E}\left[\left\|\Xi_{t}\left(\mathbf{c}\right)\right\|_{2}\right]}{\delta}.$
(41)

where the final inequality (41) uses (40). Therefore, the bound for
$\sigma\left(\delta_{e},\delta_{b},c_{a}\mid\mathbf{c}\right)$ is (39), which
satisfied with a probability of at least $1-\delta$. ∎

###  C.3 Regret Performance

The following theorem provides a bound for regret.

######  Theorem 5.

Let $\delta_{e}=\delta_{b}=\delta\in(0,1)$. Regret satisfies the following
inequality with a probability of at least $\left(1-\delta\right)^{4}$

$R_{n}\leq\sum_{a=1}^{k}2nB_{c}^{2}B_{R}^{2}\left(1-\left(1-\delta\right)^{4}\left(1-\exp\left(\frac{-\phi_{a,a_{t}^{*}}^{2}}{2\Delta
G_{c_{a}\mid\mathbf{c}}^{\top}\Sigma_{\Xi_{t}\left(\mathbf{c}\right)}\Delta
G_{c_{a}\mid\mathbf{c}}}\right)\right)\right),$ (42)

where $a_{t}^{*}\in[k]$ is the index of the optimal action
$c_{a_{t}^{*}}\in\mathcal{A}$ at round $t$. Terms $\Delta
G_{c_{a}\mid\mathbf{c}}$, $\phi_{a,a_{t}^{*}}^{2}$, and
$\Sigma_{\Xi_{t}\left(\mathbf{c}\right)}$ are defined to be

$\displaystyle\Delta G_{c_{a}\mid\mathbf{c}}$ $\displaystyle\triangleq
G_{c_{a^{*}}\mid\mathbf{c}}-G_{c_{a}\mid\mathbf{c}}$ (43)
$\displaystyle\phi_{a,a^{*}}^{2}$ $\displaystyle\triangleq
u_{a^{*}}-u_{a}+\sigma\left(\delta,\delta,c_{a^{*}}\mid\mathbf{c}\right)+\sigma\left(\delta,\delta,c_{a}\mid\mathbf{c}\right)$
(44) $\displaystyle\Sigma_{\Xi_{t}\left(\mathbf{c}\right)}$
$\displaystyle\triangleq\mathbb{E}\left[\Xi_{t}\left(\mathbf{c}\right)\Xi_{t}\left(\mathbf{c}\right)^{\top}\right],$
(45)

and $\sigma\left(\delta,\delta,c_{a}\mid\mathbf{c}\right)$ is defined to be
(32).

###### Proof.

Define $c_{a^{*}}\in\mathcal{A}$ as the optimal action, i.e. choosing action
$c_{a^{*}}\in\mathcal{A}$ samples a reward $X_{t}^{*}$ from (1) such that for
any action $c_{a}\in\mathcal{A}$ with a sampled reward $X_{t}$, the reward
$X_{t}^{*}\geq X_{t}$. The probability of choosing the optimal action
$c_{a^{*}}\in\mathcal{A}$ is based on the following event

$\hat{G}_{c_{a^{*}}\mid\mathbf{c}}\left(\mathcal{T}_{c_{a^{*}}\mid\mathbf{c}}\right)^{\top}\Xi\left(\mathbf{c}\right)+u_{a^{*}}\geq\hat{G}_{c_{a}\mid\mathbf{c}}\left(\mathcal{T}_{c_{a}\mid\mathbf{c}}\right)^{\top}\Xi\left(\mathbf{c}\right)+u_{a}.$

With a probability of at least $\left(1-\delta\right)^{4}$, the following
inequality is satisfied

$G_{c_{a^{*}}\mid\mathbf{c}}^{\top}\Xi\left(\mathbf{c}\right)+u_{a^{*}}+\sigma\left(\delta,\delta,c_{a^{*}}\mid\mathbf{c}\right)\geq
G_{c_{a}\mid\mathbf{c}}^{\top}\Xi\left(\mathbf{c}\right)+u_{a}-\sigma\left(\delta,\delta,c_{a}\mid\mathbf{c}\right).$

Rearranging provides the following

$\left(G_{c_{a^{*}}\mid\mathbf{c}}-G_{c_{a}\mid\mathbf{c}}\right)^{\top}\Xi\left(\mathbf{c}\right)\geq
u_{a}-\sigma\left(\delta,\delta,c_{a}\mid\mathbf{c}\right)-u_{a^{*}}-\sigma\left(\delta,\delta,c_{a^{*}}\mid\mathbf{c}\right).$

Define the left side of the inequality as (43) and the right side of
inequality (C.3) as (44). Since $\Delta
G_{c_{a}\mid\mathbf{c}}^{\top}\left(\Xi\left(\mathbf{c}\right)-\mathbb{E}\left[\Xi\left(\mathbf{c}\right)\right]\right)$
is sub-Gaussian, then using the Cramer-Chernoff bound (based on a Corollary
5.5 in [21]) provides

$\mathbb{P}\left(\Delta
G_{c_{a}\mid\mathbf{c}}^{\top}\Xi\left(\mathbf{c}\right)\geq\Delta
G_{c_{a}\mid\mathbf{c}}^{\top}\mathbb{E}\left[\Xi\left(\mathbf{c}\right)\right]-\phi_{a,a^{*}}\right)\geq
1-\exp\left(\frac{-\phi_{a,a^{*}}^{2}}{2\Delta
G_{c_{a}\mid\mathbf{c}}^{\top}\Sigma_{\Xi_{t}\left(\mathbf{c}\right)}\Delta
G_{c_{a}\mid\mathbf{c}}}\right)$ (46)

the optimal action is chosen. The probability of choosing the sub-optimal
action is the probability of not choosing the optimal action. This implies
that with a probability of at most

$p_{a}\triangleq
1-\left(1-\delta\right)^{4}\left(1-\exp\left(\frac{-\phi_{a,a^{*}}^{2}}{2\Delta
G_{c_{a}\mid\mathbf{c}}^{\top}\Sigma_{\Xi_{t}\left(\mathbf{c}\right)}\Delta
G_{c_{a}\mid\mathbf{c}}}\right)\right),$

the sub-optimal action is chosen. Using the law of iterated expectations [25],
the upper bound for instantaneous regret
$\mathbb{E}\left[X_{t}^{*}-X_{t}\right]$ is

$\mathbb{E}\left[X_{t}^{*}-X_{t}\right]=\sum_{a=1}^{k}\mathbb{E}\left[\left\langle\Delta
c_{a},z_{t}\right\rangle\mid
a\right]\mathbb{P}\left[a\right]\leq\sum_{a=1}^{k}\mathbb{E}\left[\left\langle\Delta
c_{a},z_{t}\right\rangle\mid a\right]p_{a},$
$\Rightarrow\mathbb{E}\left[X_{t}^{*}-X_{t}\right]\leq\sum_{a=1}^{k}2B_{c}^{2}B_{R}^{2}\left(1-\left(1-\delta\right)^{4}\left(1-\exp\left(\frac{-\phi_{a,a^{*}}^{2}}{2\Delta
G_{c_{a}\mid\mathbf{c}}^{\top}\Sigma_{\Xi_{t}\left(\mathbf{c}\right)}\Delta
G_{c_{a}\mid\mathbf{c}}}\right)\right)\right).$

Therefore, regret is upper-bounded by inequality (42). ∎

The regret bound is a function of prediction errors
$\sigma\left(\delta,\delta,c_{a}\mid\mathbf{c}\right)$ and
$\sigma\left(\delta,\delta,c_{a^{*}}\mid\mathbf{c}\right)$. To control the
impact of prediction error
$\sigma\left(\delta,\delta,c_{a}\mid\mathbf{c}\right)$, we set $u_{a}$ and
$u_{a^{*}}$ to be $u_{a}=\sigma\left(\delta,\delta,c_{a}\mid\mathbf{c}\right)$
and $u_{a^{*}}=\sigma\left(\delta,\delta,c_{a^{*}}\mid\mathbf{c}\right)$. By
setting $u_{a}=\sigma\left(\delta,\delta,c_{a}\mid\mathbf{c}\right)$ for all
$c_{a}\in\mathcal{A}$, setting $\delta_{e}=\delta_{b}=\delta\in(0,1)$, and
using Lemma 4 and Theorem 5, Theorem 2 can be easily proven.