# Thompson Sampling Regret Bounds for Contextual Bandits with sub-Gaussian
rewards ††thanks: This work was partially supported by (i) the Wallenberg AI,
Autonomous Systems and Software Program (WASP) funded by the Knut and Alice
Wallenberg Foundation and (ii) the Swedish Research Council under contract
2019-03606.

Amaury Gouverneur, Borja Rodríguez-Gálvez, Tobias J. Oechtering, and Mikael
Skoglund  Division of Information Science and Engineering (ISE)  KTH Royal
Institute of Technology<EMAIL_ADDRESS>
###### Abstract

In this work, we study the performance of the Thompson Sampling algorithm for
Contextual Bandit problems based on the framework introduced by [1] and their
concept of lifted information ratio. First, we prove a comprehensive bound on
the Thompson Sampling expected cumulative regret that depends on the mutual
information of the environment parameters and the history. Then, we introduce
new bounds on the lifted information ratio that hold for sub-Gaussian rewards,
thus generalizing the results from [1] which analysis requires binary rewards.
Finally, we provide explicit regret bounds for the special cases of
unstructured bounded contextual bandits, structured bounded contextual bandits
with Laplace likelihood, structured Bernoulli bandits, and bounded linear
contextual bandits.

##  I Introduction

Contextual bandits encompasses sequential decision-making problems where at
each round an agent must choose an action that results in a reward. This
action is chosen based on a context of the environment and a history of past
contexts, rewards, and actions [2].111This setting is also known as bandit
problems with covariates [3, 4], associative reinforcement learning [5, 6, 7],
or associative bandit problems [8]. Contextual bandits have become an
important subset of sequential decision-making problems due to their multiple
applications in healthcare, finance, recommender systems, or
telecommunications (see [9] for a survey on different applications).

There is an interest to study the theoretical limitations of algorithms for
contextual bandits. This is often done considering their _regret_ , which is
the difference in the collected rewards that an algorithm obtains compared to
an oracle algorithm that chooses the optimal action at every round [10, 11,
12, 13, 14, 15, 16, 1].

A particularly successful approach is the _Thomson Sampling (TS) algorithm_
[17], and was originally introduced for multi armed bandits, which are
sequential decision-making problems without context. Despite its simplicity,
this algorithm has been shown to work remarkably well for contextual bandits
[18, 19]. This algorithm has been studied for multi armed bandits [20, 21, 22]
and in the more general context of Markov decision processes [23]. A crucial
quantity for the analysis of TS in the multi armed bandit setting is the
_information ratio_ [20], which trades off achieving low regret and gaining
information about the optimal action.

In [1], the authors extend this concept to the _lifted information ratio_ to
fit the more challenging setting of contextual bandits, where the optimal
action changes at every round based on the context. However, their main
results are limited to contextual bandits with binary rewards. Albeit this is
a common setting, as often rewards represent either a success or a failure
[19], it fails to capture more nuanced scenarios, like dynamic pricing where
rewards represent revenue [24].

In this paper, we extend the results from [1] to contextual bandits with sub-
Gaussian rewards. These rewards include the common setup where the rewards are
bounded, but are not necessarily binary [10, 11, 12, 13, 14, 15, 16], or
setups where the expected reward is linear but is corrupted by a sub-Gaussian
noise [24].

More precisely, our contributions in this paper are:

  * •

A comprehensive bound on the TS regret that depends on the mutual information
between the environment parameters and the history collected by the agent
(Theorem 1). Compared to [1, Theorem 1], this bound highlights that, given an
average lifted information ratio, the regret of TS does not depend on all the
uncertainty of the problem, but only on the uncertainty that can be explained
by the data collected from the TS algorithm.

  * •

An alternative proof of [1, Theorem 2] showing that, if the log-likelihood of
the rewards satisfies certain regularity conditions, the TS regret is bounded
by a measure of the complexity of the parameters’ space in cases where this is
not countable. The presented proof (Theorem 2) highlights that the rewards
need not to be binary.

  * •

Showing the lifted information ratio is bounded by the number of actions
$|\mathcal{A}|$ in unstructured settings (Lemma 1) and by the dimension $d$
when the expected rewards are linear (Lemma 2). These bounds extend [1,
Lemmata 1 and 2] from the case where the rewards are binary to the more
general setting where they are sub-Gaussian.

  * •

Explicit regret bounds for particular settings as an application of the above
results (Section IV). Namely, bounds for (i) bounded unstructured contextual
bandits that show that TS has a regret with the desired [11, 25] rate of
$O(\sqrt{|\mathcal{A}|T\log|\mathcal{O}|})$, (ii) bounded structured
contextual bandits including those with Laplace likelihoods and Bernoulli
bandits, and (iii) bounded linear bandits that show that the TS regret is
competitive with LinUCB’s [12].

##  II Preliminaries

###  II-A General Notation

Random variables $X$ are written in capital letters, their realizations $x$ in
lowercase letters, their outcome space in calligraphic letters $\mathcal{X}$,
and its distribution is written as $\mathbb{P}_{X}$. The density of a random
variable $X$ with respect to a measure $\mu$ is written as
$f_{X}\coloneqq\frac{d\mathbb{P}_{X}}{d\mu}$. When two (or more) random
variables $X,Y$ are considered, the conditional distribution of $Y$ given $X$
is written as $\mathbb{P}_{Y|X}$ and the notation is abused to write their
joint distribution as $\mathbb{P}_{X}\mathbb{P}_{Y|X}$.

###  II-B Problem Setting: Contextual Bandits

A _contextual bandit_ is a sequential decision problem where, at each time
step, or round $t\in[T]$, an agent interacts with an environment by observing
a context $X_{t}\in\mathcal{X}$ and by selecting an action
$A_{t}\in\mathcal{A}$ accordingly. Based on the context and the action taken,
the environment produces a random reward $R_{t}\in\mathbb{R}$. The data is
collected in a history $H^{t+1}=H^{t}\cup H_{t+1}$, where
$H_{t+1}=\\{A_{t},X_{t},R_{t}\\}$. The procedure repeats until the end of the
time horizon, or last round $t=T$.

In the Bayesian setting, the environment is characterized by a parameter
$\Theta\in\mathcal{O}$ and a contextual bandit problem $\Phi$ is completely
defined by a prior environment parameter $\mathbb{P}_{\Theta}$, a context
distribution $\mathbb{P}_{X}$, and a fixed reward kernel
$\kappa_{\textnormal{reward}}:\mathcal{B}(\mathbb{R})\times(\mathcal{X},\mathcal{A},\mathcal{O})\to[0,1]$
such that
$\mathbb{P}_{R_{t}|X_{t},A_{t},\Theta}=\kappa_{\textnormal{reward}}\big{(}\cdot,(X_{t},A_{t},\Theta)\big{)}$.
Thus, the reward may be written as $R_{t}=R(X_{t},A_{t},\Theta)$ for some
(possibly random) function $R$.

The task in a Bayesian contextual bandit is to learn a policy
$\varphi=\\{\varphi_{t}:\mathcal{X}\times\mathcal{H}^{t}\to\mathcal{A}\\}_{t=1}^{T}$
taking an action $A_{t}$ based on the context $X_{t}$ and on the past
collected data $H^{t}$ that maximizes the _expected cumulative reward_
$R_{\Phi}(\varphi)\coloneqq\mathbb{E}\big{[}\sum_{t=1}^{T}R(X_{t},\varphi_{t}(X_{t},H^{t}),\Theta)\big{]}$.

####  II-B1 The Bayesian expected regret

The Bayesian expected regret of a contextual bandit problem measures the
difference between the performance of a given policy and the optimal one,
which is the policy that knows the true reward function and selects the
actions yielding the highest expected reward. For a given contextual bandit
problem, we define the performance of the optimal policy as the _optimal
cumulative reward_.

###### Definition 1

The _optimal cumulative reward_ of a contextual bandit problem $\Phi$ is
defined as

$R^{\star}_{\Phi}\coloneqq\sup_{\psi}\mathbb{E}\bigg{[}\sum_{t=1}^{T}R(X_{t},\psi(X_{t},\Theta),\Theta)\bigg{]},$

where the supremum is taken over the decision rules
$\psi:\mathcal{X}\times\mathcal{O}\to\mathcal{A}$ such that the expectation
above is defined.

A policy that achieves the supremum of Definition 1 is denoted as
$\psi^{\star}$ and the actions it generates are
$A^{\star}_{t}\coloneqq\psi^{\star}(X_{t},\Theta)$.

######  Assumption 1 (Compact action set)

The set of actions $\mathcal{A}$ is compact. Therefore, an optimal policy
$\psi^{\star}$ always exists.

The difference between the expected cumulative reward of a policy $\varphi$
and the optimal cumulative reward is the _Bayesian expected regret_.

###### Definition 2

The _Bayesian expected regret_ of a policy $\varphi$ in a contextual bandit
problem $\Phi$ is defined as

$\textnormal{REG}_{\Phi}(\varphi)\coloneqq
R^{\star}_{\Phi}-R_{\Phi}(\varphi).$

####  II-B2 The Thompson sampling algorithm

Thomson Sampling (TS) is an elegant algorithm to solve decision problems when
the environment $\Theta$ is unknown. It works by randomly selecting actions
according to their posterior probability of being optimal. More specifically,
at each round $t\in[T]$, the agent samples a Bayes estimate $\hat{\Theta}_{t}$
of the environment parameters $\Theta$ based on the past collected data
$H^{t}$ and selects the action given the optimal policy $\psi^{\star}$ for the
estimated parameters and the observed context $X_{t}$, that is
$\hat{A}_{t}=\psi^{\star}(X_{t},\hat{\Theta}_{t})$. The history collected by
the TS algorithm up to round $t$ is denoted $\hat{H}^{t}$. The pseudocode for
this procedure is given in Algorithm 1. Therefore, the Bayesian cumulative
reward $R^{\textnormal{TS}}_{\Phi}$ of the TS algorithm is

$R^{\textnormal{TS}}_{\Phi}\coloneqq\mathbb{E}\bigg{[}\sum_{t=1}^{T}R(X_{t},\psi^{\star}(X_{t},\hat{\Theta}_{t}),\Theta)\bigg{]},$

where $\hat{\Theta}_{t}$ has the property that
$\mathbb{P}_{\hat{\Theta}|\hat{H}^{t}}=\mathbb{P}_{\Theta|\hat{H}^{t}}$ a.s..
The Bayesian expected regret of the TS is denoted
$\textnormal{REG}^{\textnormal{TS}}_{\Phi}$ and is usually referred to as the
_TS cumulative regret_.

####  II-B3 Notation specific to contextual bandits

To aid the exposition, and since the $\sigma$-algebras of the history
$\hat{H}^{t}$ and the context $X_{t}$ are often in the conditioning of the
expectations and probabilities used in the analysis, similarly to [21, 1], we
define the operators
$\mathbb{E}_{t}[\cdot]\coloneqq\mathbb{E}[\cdot|\hat{H}^{t},X_{t}]$ and
$\mathbb{P}_{t}[\cdot]\coloneqq\mathbb{P}[\cdot|\hat{H}^{t},X_{t}]$, whose
outcomes are $\sigma(\mathcal{H}^{t}\times\mathcal{X})$-measurable random
variables and $\mathcal{H}=\mathcal{A}\times\mathcal{X}\times\mathbb{R}$.
Similarly, we define
$\textup{I}_{t}(\Theta;R_{t}|\hat{A}_{t})\coloneqq\mathbb{E}_{t}[\textup{D}_{\textnormal{KL}}(\mathbb{P}_{R_{t}|\hat{H}^{t},X_{t},\hat{A}_{t},\Theta}\lVert\mathbb{P}_{R_{t}|\hat{H}^{t},X_{t},\hat{A}_{t}})]$
as the _disintegrated_ conditional mutual information between the parameter
$\Theta$ and the reward $R_{t}$ given the action $\hat{A}_{t}$, _given the
history $\hat{H}^{t}$ and the context $X_{t}$_, see [26, Definition 1.1],
which is itself as well a
$\sigma(\mathcal{H}^{t}\times\mathcal{X})$-measurable random variable.

Algorithm 1 Thompson Sampling algorithm

1: Input: environment parameters prior $\mathbb{P}_{\Theta}$.

2: for $t=1$ to T do

3: Observe the context $X_{t}\sim\mathbb{P}_{X}$.

4: Sample a parameter estimation
$\smash{\hat{\Theta}_{t}\sim\mathbb{P}_{\Theta|\hat{H}^{t}}}$.

5: Take the action $\hat{A}_{t}=\psi^{\star}(X_{t},\hat{\Theta}_{t})$.

6: Collect the reward $R_{t}=R(X_{t},\hat{A}_{t},\Theta)$.

7: Update the history
$\hat{H}^{t+1}=\\{\hat{H}^{t},\hat{A}_{t},X_{t},R_{t}\\}$.

8: end for

##  III Main results

In this section, we present our main results to bound the TS cumulative regret
for contextual bandits. In Section III-A, we first (Theorem 1) prove a
comprehensive bound on the TS cumulative regret that, rather than depending on
the entropy of the environment’s parameters as [1, Theorem 1], it depends on
their mutual information with the history. This highlights that, given an
average lifted information ratio, the TS cumulative regret does not depend on
the uncertainty of the parameters, but on the uncertainty of the parameters
explained by the history. Then (Theorem 2), we slightly relax the assumptions
of [1, Theorem 2] and digest this result with an alternative proof, which
formalizes that the TS cumulative regret is bounded by the complexity of the
environment’s space. In Section III-B, we provide bounds on the lifted
information ratio. First (Lemma 1), without assuming any structure in the
rewards, we show a bound that scales linearly with the number of actions. We
then (Lemma 2) consider the special case of linear contextual bandits and show
that in that case we can obtain a bound that scales with the dimension of the
problem. These results, in turn, generalize [1, Lemmata 1 and 2], which are
only valid for binary losses.

###  III-A Bounding the TS cumulative regret

In the contextual bandits setting, the concept of _lifted information ratio_
was introduced in [1] as the random variable

$\Gamma_{t}\coloneqq\frac{\mathbb{E}_{t}[R^{\star}_{t}-R_{t}]^{2}}{\textup{I}_{t}(\Theta;R_{t}|\hat{A}_{t})},$

where $R_{t}$ is the reward collected by the TS algorithm and $R^{\star}_{t}$
is the one collected playing optimally, i.e.
$R(X_{t},\psi^{\star}_{t}(X_{t},\Theta),\Theta)$. This concept was inspired by
the _information ratio_ from [21] in the non-contextual multi armed bandit
problem setting and it is closely related to the _decoupling coefficient_ from
[16].

In the proof of [1, Theorem 1], it is shown that

$\textnormal{REG}_{\Phi}^{\textnormal{TS}}\leq\sqrt{\bigg{(}\sum_{t=1}^{T}\mathbb{E}[\Gamma_{t}]\bigg{)}\bigg{(}\sum_{t=1}^{T}\textup{I}(\Theta;R_{t}|\hat{H}^{t},X_{t},\hat{A}_{t})\bigg{)}}.$
(1)

This is employed to show a result bounding the TS cumulative regret for
problems with a countable environment space $\Theta$. However, this
intermediate step can also be leveraged to obtain a more general, and perhaps
more revealing bound on the TS cumulative regret.

###### Theorem 1

Assume that the average of the lifted information ratios is bounded
$\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}[\Gamma_{t}]\leq\Gamma$ for some
$\Gamma>0$. Then, the TS cumulative regret is bounded as

$\displaystyle\textnormal{REG}^{\textnormal{TS}}_{\Phi}$
$\displaystyle\leq\sqrt{\Gamma T\textup{I}(\Theta;\hat{H}^{T+1})}$
$\displaystyle=\sqrt{\Gamma
T\mathbb{E}[\textup{D}_{\textnormal{KL}}(\mathbb{P}_{\Theta|\hat{H}^{T+1}}\lVert\mathbb{P}_{\Theta})]}.$

###### Proof:

The proof follows by an initial application of the chain rule of the mutual
information. Namely,

$\displaystyle\smash{\textup{I}(\Theta;\hat{H}^{T+1})=\sum\nolimits_{t=1}^{T}\textup{I}(\Theta;\hat{H}_{t+1}|\hat{H}^{t}).}$

Applying the chain rule once more to each term shows that

$\displaystyle\textup{I}(\Theta;\hat{H}_{t+1}|\hat{H}^{t})=\textup{I}(\Theta;X_{t},\hat{A}_{t}|\hat{H}^{t})+\textup{I}(\Theta;R_{t}|\hat{H}^{t},X_{t},\hat{A}_{t}).$

Finally, the non-negativity of the mutual information completes the proof as
$\textup{I}(\Theta;\hat{H}_{t+1}|\hat{H}^{t})\geq\textup{I}(\Theta;R_{t}|\hat{H}^{t},X_{t},\hat{A}_{t})$.
∎

Theorem 1 has [1, Theorem 1] as a corollary by noting that for countable
parameters’ spaces $\textup{I}(\Theta;\hat{H}^{T+1})\leq\textup{H}(\Theta)$
and that if $\Gamma_{t}\leq\Gamma$ a.s. for all $t\in[T]$, then
$\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}[\Gamma_{t}]\leq\Gamma$. This seemingly
innocuous generalization gives us insights on the TS cumulative regret via the
following two factors:

  * •

The bound on the average of lifted information ratios $\Gamma$. This measures
the maximum information gain on the environment parameters on average through
the rounds. This is different to the requirement that
$\mathbb{E}[\Gamma_{t}]\leq\Gamma^{\prime}$ from [1], which penalizes equally
rounds with large or little information gain. This may be relevant in
scenarios where the lifted information ratio can vary drastically among
rounds.

  * •

The mutual information between the parameters $\Theta$ and the history
$\hat{H}^{t}$. Contrary to the entropy $\textup{H}(\Theta)$ featured in the
bound [1, Theorem 1], which is a measure of the uncertainty of the parameters,
the mutual information $\textup{I}(\Theta;\hat{H}^{t})$ measures the
uncertainty of the parameters that is explained by the history of TS since

$\textup{I}(\Theta;\hat{H}^{t})=\underbrace{\textup{H}(\Theta)}_{\textnormal{Uncertainty
of
$\Theta$}}-\underbrace{\textup{H}(\Theta|\hat{H}^{t}).}_{\begin{subarray}{c}\textnormal{Uncertainty
of $\Theta$}\\\ \textnormal{not explained by $\hat{H}^{t}$}\end{subarray}}$

Moreover, the mutual information is the relative entropy between the TS
posterior on the parameters and the true parameters’ prior, i.e.
$\mathbb{E}[\textup{D}_{\textnormal{KL}}(\mathbb{P}_{\Theta|\hat{H}^{T+1}}\lVert\mathbb{P}_{\Theta})]$,
which measures how well is the TS posterior aligned with the true parameters’
distribution in the last round. As for the TS algorithm we can sample from the
posterior $\mathbb{P}_{\Theta|\hat{H}^{T+1}}$, there are situations where the
posterior is known analytically and thus this relative entropy can be
numerically estimated at each round [20, Section 6].

In [1], for binary rewards, i.e.
$R:\mathcal{X}\times\mathcal{A}\times\mathcal{O}\to\\{0,1\\}$, it is shown
that regularity on the reward’s log-likelihood is sufficient to guarantee a
bound on the TS cumulative regret _à la Lipschitz maximal inequality_ [27,
Lemma 5.7]. More precisely, if the parameters’ space $\mathcal{O}$ is a metric
space $(\mathcal{O},\rho)$, they impose that the log-likelihood is Lipschitz
continuous for all actions and all contexts. However, requiring the log-
likelihood random variable to be a Lipschitz process is sufficient, as we will
show shortly.

######  Assumption 2 (Lipschitz log-likelihood)

There is a random variable $C>0$ that can depend only on $R_{t},X_{t}$, and
$\hat{A}_{t}$ such that $|\log
f_{R_{t}|X_{t},\hat{A}_{t},\Theta=\theta}(R_{t})-\log
f_{R_{t}|X_{t},\hat{A}_{t},\Theta=\theta^{\prime}}(R_{t})|\leq
C\rho(\theta,\theta^{\prime})$ a.s. for all
$\theta,\theta^{\prime}\in\mathcal{O}$.

With this regularity condition, the TS cumulative regret can be bounded from
above by the “complexity" of the parameter’s space $\mathcal{O}$, measured by
the $\epsilon$-covering number of the space.

###### Definition 3

A set $\mathcal{N}$ is an $\epsilon$-net for $(\mathcal{O},\rho)$ if for every
$\theta\in\mathcal{O}$, there exists a _projection map_
$\pi(\theta)\in\mathcal{N}$ such that $\rho(\theta,\pi(\theta))\leq\epsilon$.
The smallest cardinality of an $\epsilon$-net for $(\mathcal{O},\rho)$ is
called _the $\epsilon$-covering number_

$|\mathcal{N}(\mathcal{O},\rho,\epsilon)|\coloneqq\inf\\{|\mathcal{N}|:\mathcal{N}\textnormal{
is an }\epsilon\textnormal{-net for }(\mathcal{O},\rho)\\}.$

In [1], they prove their result manipulating the densities and employing the
_Bayesian telescoping_ technique to write the so called “Bayesian marginal
distribution" as the product of “posterior predictive distributions" [28].
Observing their proof, it seems that their result did not require the rewards
to be binary to hold. Below, using the properties of mutual information and
standard arguments to bound Lipschitz processes [27, Section 5.2] we provide
an alternative proof for this result where the weaker regularity condition and
the unnecessary requirement of binary rewards is apparent.

###### Theorem 2

Assume that the parameters’ space is a metric space $(\mathcal{O},\rho)$ and
let $|\mathcal{N}(\mathcal{O},\rho,\varepsilon)|$ be the $\epsilon$-covering
number of this space for any $\varepsilon>0$. Assume as well that the log-
likelihood is a Lipschitz process according to 2 and that the average of the
lifted information ratios is bounded
$\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}[\Gamma_{t}]\leq\Gamma$ for some
$\Gamma>0$. Then, the TS cumulative regret is bounded as

$\textnormal{REG}_{\Phi}^{\textnormal{TS}}\leq\sqrt{\Gamma
T\min_{\varepsilon>0}\big{\\{}\varepsilon\mathbb{E}[C]T+\log|\mathcal{N}(\mathcal{O},\rho,\varepsilon)|\big{\\}}}.$

###### Proof:

The proof follows considering (1) again. The mutual information terms can be
written as

$\displaystyle\textup{I}(\Theta;R_{t}|\hat{H}^{t},X_{t},\hat{A}_{t})=\mathbb{E}\bigg{[}\log\frac{f_{R_{t}|\hat{H}^{t},X_{t},\hat{A}_{t},\Theta}(R_{t})}{f_{R_{t}|\hat{H}^{t},X_{t},\hat{A}_{t}}(R_{t})}\bigg{]}.$
(2)

Consider now an $\varepsilon$-net of $\mathcal{O}$ with minimal cardinality
$|\mathcal{N}(\mathcal{O},\rho,\epsilon)|$, where $\pi$ is its projecting map.
Then, the mutual information in (2) can equivalently be written as

$\displaystyle\mathbb{E}\bigg{[}\int_{\mathcal{O}}f_{\Theta|R_{t},\hat{H}^{t},X_{t},\hat{A}_{t}}(\theta)$
$\displaystyle\bigg{(}\log\frac{f_{R_{t}|X_{t},\hat{A}_{t},\Theta=\theta}(R_{t})}{f_{R_{t}|X_{t},\hat{A}_{t},\Theta=\pi(\theta)}(R_{t})}$
$\displaystyle+\log\frac{f_{R_{t}|\hat{H}^{t},X_{t},\hat{A}_{t},\Theta=\pi(\theta)}(R_{t})}{f_{R_{t}|\hat{H}^{t},X_{t},\hat{A}_{t}}(R_{t})}\bigg{)}d\theta\bigg{]},$

since
$f_{R_{t}|\hat{H}^{t},X_{t},\hat{A}_{t},\Theta}=f_{R_{t}|X_{t},\hat{A}_{t},\Theta}$
a.s. by the conditional Markov chain $R_{t}-\hat{A}_{t}-\hat{H}\ |\
\Theta,X_{t}$. The regularity condition in 2 ensures that the first term is
bounded by $\varepsilon\mathbb{E}[C]$. Then, defining the random variable
$\Theta_{\pi}\coloneqq\pi(\Theta)$, we note that the second term is equal to
$\textup{I}(\Theta_{\pi};R_{t}|\hat{H}^{t},X_{t},\hat{A}_{t})$.

Summing the $T$ terms from the regularity condition results in
$\varepsilon\mathbb{E}[C]T$ and, similarly to the proof of Theorem 1, summing
the $T$ mutual information
$\textup{I}(\Theta_{\pi};R_{t}|\hat{H}^{t},X_{t},\hat{A}_{t})$ terms results
in the upper bound

$\smash{\sum\nolimits_{t=1}^{T}\textup{I}(\Theta_{\pi};R_{t}|\hat{H}^{t},X_{t},\hat{A}_{t})\leq\textup{I}(\Theta_{\pi};\hat{H}^{T+1})\leq\textup{H}(\Theta_{\pi}).}$

Finally, bounding the entropy by the cardinalitiy of the net
$\textup{H}(\Theta_{\pi})\leq\log|\mathcal{N}(\mathcal{O},\rho,\varepsilon)|$
completes the proof.

∎

###  III-B Bounding the lifted information ratio

The next lemma provides a bound on the lifted information ratio that holds for
settings with a finite number of actions and sub-Gaussian rewards. This result
generalizes [1, Lemma 1] as their proof technique requires the rewards to be
binary. Under this specific case, we recover their result with a smaller
constant as binary random variables are $1/4$-sub-Gaussian.222Random variables
in $[0,L]$ are $\frac{L^{2}}{4}$-sub-Gaussian[29, Theorem 1].

###### Lemma 1

Assume the number of actions $|\mathcal{A}|$ is finite. If for all $t\in[T]$,
$h^{t}\in\mathcal{H}^{t}$, and $x\in\mathcal{X}$, the random rewards $R_{t}$
are $\sigma^{2}$-sub-Gaussian under
$\mathbb{P}_{R_{t}|\hat{H}^{t}=h^{t},X_{t}=x}$, then $\Gamma_{t}\leq
2\sigma^{2}|\mathcal{A}|$.

###### Proof:

The proof adapts [20, Proof of Proposition 3] to contextual bandits. The
adaptation considers sub-Gaussian rewards using the Donsker–Varadhan
inequality [30, Theorem 5.2.1] as suggested in [20, Appedix D]. This
adaptation completely differs from the one in [1], which is based on convex
analysis of the relative entropy of distributions with binary supports. The
full proof is in Appendix A. ∎

Next, we consider cases of linear expected rewards. This setting is an
extension of the stochastic linear bandit problem studied in [21, Section 6.5]
to contextual bandit problems. The following lemma provides a bound on the
lifted information ratio for problems in this setting with sub-Gaussian
rewards, thus generalizing [1, Lemma 2] which only considers binary random
rewards. It useful in cases where the dimension is smaller than the number of
actions $d<|\mathcal{A}|$.

###### Lemma 2

Assume the number of actions $|\mathcal{A}|$ is finite, the expectation of the
rewards is $\mathbb{E}[R(x,a,\theta)]=\langle\theta,m(x,a)\rangle$ for some
feature map $m:\mathcal{X}\times\mathcal{A}\to\mathbb{R}^{d}$, and that
$\mathcal{O}\subseteq\mathbb{R}^{d}$. If for all $t\in[T]$,
$h^{t}\in\mathcal{H}^{t}$, and $x\in\mathcal{X}$, the random rewards $R_{t}$
are $\sigma^{2}$-sub-Gaussian under
$\mathbb{P}_{R_{t}|\hat{H}^{t}=h^{t},X_{t}=x}$, then $\Gamma_{t}\leq
2\sigma^{2}d$.

###### Proof:

The proof adapts [20, Proof of Proposition 5] to contextual bandits similarly
to [1, Proof of Lemma 2]. The key difference with the latter is that instead
of binary rewards [1], this considers sub-Gaussian ones using again the
Donsker–Varadhan inequality [30, Theorem 5.2.1] similarly to the proof of
Lemma 1. The full proof is in Appendix A. ∎

##  IV Applications

###  IV-A Unstructured bounded contextual bandits

The problem of contextual bandits with bounded rewards
$R:\mathcal{X}\times\mathcal{A}\times\mathcal{O}\to[0,1]$ and a finite number
of actions $|\mathcal{A}|$ and of parameters $|\mathcal{O}|$ is well studied.
In [11] and [25], respectively, the authors showed that the algorithms Policy
Elimination and Exp4.P have a regret upper bound in
$O\big{(}\sqrt{|\mathcal{A}|T\log(T|\mathcal{O}|/\delta)}\big{)}$ and in
$O\big{(}\sqrt{|\mathcal{A}|T\log(|\mathcal{O}|/\delta)}\big{)}$ with
probability at least $1-\delta$. Then, it was shown that there exist some
contextual bandit algorithm with a regret upper bound in
$O(\sqrt{|\mathcal{A}|T\log|\mathcal{O}|})$ [14] and that, for all algorithms,
there is a parameters’ space $\mathcal{O}^{\prime}$ with cardinality smaller
than $|\mathcal{O}|$ such that the regret lower bounded is in
$\Omega(\sqrt{|\mathcal{A}|T\log|\mathcal{O}|/\log|\mathcal{A}|})$ [13]. This
sparked the interest to study how the TS or related algorithms’ regret
compared to these bounds. In [16, Section 5.1], it was shown that the Feel-
Good TS regret has a rate in $O(\sqrt{|\mathcal{A}|T\log|\mathcal{O}|})$ and
recently, in [1, Theorem 3], it was shown that if the reward is binary, the TS
also has a rate in $O(\sqrt{|\mathcal{A}|T\log|\mathcal{O}|})$. Here, as a
corollary of Theorem 1 and Lemma 1, we close the gap on the regret of the TS
algorithm showing that it is in $O(\sqrt{|\mathcal{A}|T\log|\mathcal{O}|})$
for sub-Gaussian rewards, and thus for bounded ones.

###### Corollary 1

Assume that the rewards are bounded in $[0,L]$. Then, for any contextual
bandit problem $\Phi$, the TS cumulative regret after $T$ rounds is bounded as

$\displaystyle\textnormal{REG}^{\textnormal{TS}}_{\Phi}\leq\sqrt{\frac{L^{2}|\mathcal{A}|T\textup{H}(\Theta)}{2}}.$

Note that the above result also holds for $\sigma^{2}$-sub-Gaussian rewards by
replacing $L^{2}/2$ by $2\sigma^{2}$.

###  IV-B Structured bounded contextual bandits

####  IV-B1 Bandits with Laplace likelihoods

We introduce the setting of contextual bandits with Laplace likelihoods. In
this setting, we model the rewards’ random variable with a Laplace
distribution. More precisely, this setting considers rewards with a likelihood
proportional to $\exp\Big{(}-\frac{|r-f_{\theta}(x,a)|}{\beta}\Big{)}$ for
some $\beta>0$. In addition, this setting assumes that the random variable
$f_{\theta}(X,A)$ is a Lipschitz process with respect to $\theta$ with random
variable $C\coloneqq C(X,A)$. This ensures 2 with random variable
$\frac{C}{\beta}$ as by the triangle inequality

$|r-f_{\theta}(x,a)|-|r-f_{\theta^{\prime}}(x,a)|\leq|f_{\theta}(x,a)-f_{\theta^{\prime}}(x,a)|.$

Theorem 2 and Lemma 1 yield the following corollary, where we further use the
bound on the $\varepsilon$-covering number
$|\mathcal{N}(\mathcal{O},\rho,\epsilon)|\leq\big{(}\frac{3S}{\varepsilon}\big{)}^{d}$
[27, Lemma 5.13] and we let $\varepsilon=\frac{d\beta}{\mathbb{E}[C]T}$.

###### Corollary 2

Assume that $\mathcal{O}\subset\mathbb{R}^{d}$ with
$\textnormal{diam}(\mathcal{O})\leq S$. Consider a contextual bandit problem
$\Phi$ with Laplace likelihood and rewards bounded in $[0,L]$. Then, the TS
cumulative regret after $T$ rounds is bounded as

$\displaystyle\textnormal{REG}^{\textnormal{TS}}_{\Phi}\leq\sqrt{\frac{L^{2}|\mathcal{A}|Td}{2}\bigg{(}1+\log\bigg{(}\frac{3S\mathbb{E}[C]T}{d\beta}\bigg{)}\bigg{)}}.$

In particular, for linear functions
$f_{\theta}(x,a)=\langle\theta,m(x,a)\rangle$ with a bounded feature map, i.e.
$\lVert m(x,a)\rVert\leq B$ for all $x\in\mathcal{X}$ and all
$a\in\mathcal{A}$, then $C\leq B$ a.s..

####  IV-B2 Bernoulli bandits with structure

A common setting is that of Bernoulli contextual bandits, where the random
rewards $R_{t}$ are binary and Bernoulli distributed [18, 19]. This is an
attractive setting as binary rewards are usually modeled to measure success in
e-commerce. In this setting, usually $R_{t}\sim\textnormal{Ber}\big{(}g\circ
f_{\Theta}(X_{t},\hat{A}_{t})\big{)}$, where $g$ is a _binomial link function_
and $f$ is a linear function $f_{\theta}(x,a)=\langle\theta,m(x,a)\rangle$ for
some feature map $m$. When the link function is the logistic function
$g(z)=\sigma(z)\coloneqq(1+e^{-z})^{-1}$, $f$ is $C$-Lipschitz (e.g., when it
is a linear function with a bounded feature map), and the parameters’ space is
bounded $\lVert\theta\rVert\leq S$ for all $\theta\in\mathcal{O}$, [1] showed
that the TS cumulative regret rate is in
$O\big{(}\sqrt{|\mathcal{A}|Td\log(SCT)}\big{)}$. This result is founded in
their Theorem 2 and Lemma 1, and the fact that $\log\sigma$ is a $1$-Lipschitz
function. We note that this is also true for other link functions such as the
generalized logistic function
$\sigma_{\alpha}(z)\coloneqq(1+e^{-z})^{-\alpha}$, whose $\log$ is
$\alpha$-Lipschitz for all $\alpha>0$, or the algebraic logistic function
$\sigma_{\textnormal{alg}}(z)\coloneqq\frac{1}{2}(1+\frac{z}{\sqrt{1+z^{2}}})$,
whose $\log$ is $2$-Lipschitz. Moreover, we also note that with an appropriate
choice of $\varepsilon$ as in Corollary 2, these results improve their rate to
$O\big{(}\sqrt{|\mathcal{A}|Td\log(SCT/d)}\big{)}$.

###  IV-C Bounded linear contextual bandits

In this section, we focus on the setting of contextual bandits with linear
expected rewards. This setting has been introduced by [10] and further studied
in [12]. In this setting, the rewards are bounded in $[0,1]$ and their
expectation is linear $\mathbb{E}[R(x,a,\theta)]=\langle\theta,m(x,a)\rangle$
with a bounded feature map $m:\mathcal{X}\times\mathcal{A}\to[0,1]$ and
parameters’ space $\textnormal{diam}(\mathcal{O})=1$.

In this setting, [12] showed that LinUCB has a regret bound in
$O\big{(}\sqrt{dT\log^{3}(|\mathcal{A}|T\log(T)/\delta)}\Big{)}$ with
probability no smaller than $1-\delta$. The following corollary shows that if
one is able to work with a discretized version $\mathcal{O}_{\varepsilon}$ of
$\mathcal{O}$ with precision $\varepsilon$, i.e. $\mathcal{O}_{\varepsilon}$
is an $\varepsilon$-net of $\mathcal{O}$, then TS has a regret bound in
$O\Big{(}\sqrt{d^{2}T\log\big{(}\frac{3}{\varepsilon}}\big{)}\Big{)}$, which
also follows from the bound on the $\varepsilon$-covering number
$|\mathcal{N}(\mathcal{O},\lVert\cdot\rVert,\varepsilon)|\leq\big{(}\frac{3}{\varepsilon}\big{)}^{d}$
[27, Lemma 5.13]. This bound is especially effective when the dimension $d$ is
small or the number of actions $|\mathcal{A}|$ is large. More precisely, it is
tighter than [12]’s bound when
$d\log(1/\varepsilon)<\log^{3}(|\mathcal{A}|T\log T)$.

###### Corollary 3

Assume that $\mathcal{O}=\\{\theta_{1},\ldots,\theta_{|\mathcal{O}|}\\}$ where
$\theta\in\mathbb{R}^{d}$. Consider a contextual bandit problem $\Phi$ with a
finite number of actions $|\mathcal{A}|$, rewards bounded in $[0,L]$ and such
that the expectation of the rewards is
$\mathbb{E}[R(x,a,\theta)]=\langle\theta,m(x,a)\rangle$ for some feature map
$m:\mathcal{X}\times\mathcal{A}\to\mathbb{R}^{d}$. Then the TS cumulative
regret after $T$ rounds is bounded as

$\displaystyle\textnormal{REG}^{\textnormal{TS}}_{\Phi}\leq\sqrt{\frac{L^{2}dT\log(|\mathcal{O}|)}{2}}$

###### Proof:

It follows from Theorem 1 and Lemma 2. ∎

##  V Conclusion

In this paper, we showed in Theorem 1 that the TS cumulative regret for
contextual bandit problems is bounded from above by the mutual information
between the environment parameters and the history. Compared to [1, Theorem
1], this highlights that, given an average lifted information ratio, the
regret of TS does not depend on all the uncertainty of the environment
parameters, but only on the uncertainty that can be explained by the history
collected by the algorithm. In Theorem 2, we provided an alternative proof to
[1, Theorem 2] showing that the TS regret is bounded by the "complexity" of
the parameters’ space, where we highlighted that this result holds without the
requirement of the rewards being binary.

In Lemmata 1 and 2, we provided bounds on the lifted information ratio that
hold for contextual bandit problems with sub-Gaussian rewards. This includes
the standard setting where the rewards are bounded [10, 11, 12, 13, 14, 15,
16], and setups where the expected reward is linear but is corrupted by a sub-
Gaussian noise [24], thus extending the results from [1] that worked only with
binary rewards. When no structure of the problem is assumed, the lifted
information ratio bound scales with the number of actions $|\mathcal{A}|$
(Lemma 1), and for problems with linear expected rewards, the bound scales
with the dimension $d$ of the parameters’ space $\mathcal{O}$ (Lemma 2).

Finally, we applied our results to some particular settings such as: bounded
unstructured contextual bandits, for which TS has a regret with rate of
$O(\sqrt{|\mathcal{A}|T\log|\mathcal{O}|})$; bounded structured contextual
bandits including those with Laplace likelihoods and Bernoulli bandits; and
lastly, bounded linear bandits underlining that TS has a regret bound
competing with LinUCB [12].

## References

  * [1] G. Neu, J. Olkhovskaya, M. Papini, and L. Schwartz, “Lifting the information ratio: An information-theoretic analysis of thompson sampling for contextual bandits,” _arXiv preprint arXiv:2205.13924_ , 2022.
  * [2] J. Langford and T. Zhang, “The epoch-greedy algorithm for multi-armed bandits with side information,” _Advances in neural information processing systems_ , vol. 20, 2007.
  * [3] J. Sarkar, “One-armed bandit problems with covariates,” _The Annals of Statistics_ , pp. 1978–2002, 1991.
  * [4] M. Woodroofe, “A one-armed bandit problem with a concomitant variable,” _Journal of the American Statistical Association_ , vol. 74, no. 368, pp. 799–806, 1979.
  * [5] A. G. Barto and P. Anandan, “Pattern-recognizing stochastic learning automata,” _IEEE Transactions on Systems, Man, and Cybernetics_ , no. 3, pp. 360–375, 1985.
  * [6] V. Gullapalli, _Associative reinforcement learning of real-valued functions_. Citeseer, 1990.
  * [7] L. P. Kaelbling, “Associative reinforcement learning: A generate and test algorithm,” _Machine Learning_ , vol. 15, pp. 299–319, 1994.
  * [8] A. L. Strehl, C. Mesterharm, M. L. Littman, and H. Hirsh, “Experience-efficient learning in associative bandit problems,” in _Proceedings of the 23rd international conference on Machine learning_ , 2006, pp. 889–896.
  * [9] D. Bouneffouf, I. Rish, and C. Aggarwal, “Survey on applications of multi-armed and contextual bandits,” in _2020 IEEE Congress on Evolutionary Computation (CEC)_. IEEE, 2020, pp. 1–8.
  * [10] N. Abe, A. W. Biermann, and P. M. Long, “Reinforcement learning with immediate rewards and linear hypotheses,” _Algorithmica_ , vol. 37, pp. 263–293, 2003\.
  * [11] M. Dudik, D. Hsu, S. Kale, N. Karampatziakis, J. Langford, L. Reyzin, and T. Zhang, “Efficient optimal learning for contextual bandits,” _arXiv preprint arXiv:1106.2369_ , 2011.
  * [12] 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.
  * [13] A. Agarwal, M. Dudík, S. Kale, J. Langford, and R. Schapire, “Contextual bandit learning with predictable rewards,” in _Artificial Intelligence and Statistics_. PMLR, 2012, pp. 19–26.
  * [14] D. Foster and A. Rakhlin, “Beyond ucb: Optimal and efficient contextual bandits with regression oracles,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 3199–3210.
  * [15] D. J. Foster and A. Krishnamurthy, “Efficient first-order contextual bandits: Prediction, allocation, and triangular discrimination,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 18 907–18 919, 2021.
  * [16] T. Zhang, “Feel-good thompson sampling for contextual bandits and reinforcement learning,” _SIAM Journal on Mathematics of Data Science_ , vol. 4, no. 2, pp. 834–857, 2022.
  * [17] 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.
  * [18] S. L. Scott, “A modern bayesian look at the multi-armed bandit,” _Applied Stochastic Models in Business and Industry_ , vol. 26, no. 6, pp. 639–658, 2010.
  * [19] O. Chapelle and L. Li, “An empirical evaluation of Thompson sampling,” _Advances in neural information processing systems_ , vol. 24, 2011.
  * [20] D. Russo and B. Van Roy, “Learning to optimize via information-directed sampling,” _Advances in Neural Information Processing Systems_ , vol. 27, 2014.
  * [21] ——, “An information-theoretic analysis of Thompson sampling,” _The Journal of Machine Learning Research_ , vol. 17, no. 1, pp. 2442–2471, 2016.
  * [22] S. Dong and B. Van Roy, “An information-theoretic analysis for thompson sampling with many actions,” _Advances in Neural Information Processing Systems_ , vol. 31, 2018.
  * [23] A. Gouverneur, B. Rodríguez-Gálvez, T. J. Oechtering, and M. Skoglund, “An information-theoretic analysis of bayesian reinforcement learning,” in _2022 58th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_. IEEE, 2022, pp. 1–7.
  * [24] J. W. Mueller, V. Syrgkanis, and M. Taddy, “Low-rank bandit methods for high-dimensional dynamic pricing,” _Advances in Neural Information Processing Systems_ , vol. 32, 2019.
  * [25] A. Beygelzimer, J. Langford, L. Li, L. Reyzin, and R. Schapire, “Contextual bandit algorithms with supervised learning guarantees,” in _Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics_. JMLR Workshop and Conference Proceedings, 2011, pp. 19–26.
  * [26] J. Negrea, M. Haghifam, G. K. Dziugaite, A. Khisti, and D. M. Roy, “Information-theoretic generalization bounds for sgld via data-dependent estimates,” _Advances in Neural Information Processing Systems_ , vol. 32, 2019.
  * [27] R. van Handel, “Probability in high dimension,” PRINCETON UNIV NJ, Tech. Rep., 2014.
  * [28] P. Grünwald, “The safe bayesian: learning the learning rate via the mixability gap,” in _Algorithmic Learning Theory: 23rd International Conference, ALT 2012, Lyon, France, October 29-31, 2012. Proceedings 23_. Springer, 2012, pp. 169–183.
  * [29] W. Hoeffding, “Probability inequalities for sums of bounded random variables,” in _The collected works of Wassily Hoeffding_. Springer, 1994, pp. 409–426.
  * [30] R. M. Gray, _Entropy and information theory_. Springer Science & Business Media, 2011.

##  Appendix A Proofs of lemmata

See 1

###### Proof:

The proof follows the same methodology as [21, Proof of Proposition 3], taking
care of the presence of contexts in the analysis. For the sake of brevity, we
introduce the following notation $R^{\prime}_{t}(a)\coloneqq
R(X_{t},a,\Theta)$ and recall the previously defined notations
$A^{\star}_{t}\coloneqq\psi^{\star}(X_{t},\Theta)$ and
$\hat{A}_{t}\coloneqq\psi^{\star}(X_{t},\hat{\Theta}_{t})$. Then at each round
$t\in[T]$, one can write the expected regret conditioned on
$\hat{H}^{t},X_{t}$ as

$\displaystyle\mathbb{E}_{t}[R^{\star}_{t}-R_{t}]=\sum_{a\in\mathcal{A}}$
$\displaystyle\mathbb{P}_{t}[A^{\star}_{t}=a]\mathbb{E}_{t}[R^{\prime}_{t}(a)|A^{\star}_{t}=a]$
$\displaystyle-\sum_{a\in\mathcal{A}}\mathbb{P}_{t}[\hat{A}_{t}=a]\mathbb{E}_{t}[R^{\prime}_{t}(a)|\hat{A}_{t}=a]\
\textnormal{a.s.}.$

By definition of the TS algorithm
$\mathbb{P}_{t}[A^{\star}_{t}=a]=\mathbb{P}_{t}[\hat{A}_{t}=a]$ a.s..
Observing as well that conditioned on $\hat{H}^{t}$ and $X_{t}$, the reward
$R^{\prime}_{t}(a)$ is independent of the TS action $\hat{A}_{t}$, the
conditional expected regret can be a.s. rewritten as

$\displaystyle\sum_{a\in\mathcal{A}}\mathbb{P}_{t}[A^{\star}_{t}=a]\big{(}\mathbb{E}_{t}[R^{\prime}_{t}(a)|A^{\star}_{t}=a]-\mathbb{E}_{t}[R^{\prime}_{t}(a)]\big{)}.$
(3)

As the rewards are $\sigma^{2}$-sub-Gaussian, the difference of expectations
in this last rewriting can be upper bounded using the Donsker-Varadhan
inequality [30, Theorem 5.2.1] as in [20, Lemma 3]. It then comes that (3) can
be a.s. upper bounded by

$\displaystyle\sum_{a\in\mathcal{A}}\underbrace{\mathbb{P}_{t}[A^{\star}_{t}=a]\sqrt{2\sigma^{2}D_{\textnormal{KL}}(\mathbb{P}_{R^{\prime}_{t}(a)|\hat{H}^{t},X_{t},A^{\star}_{t}=a}\>\|\>\mathbb{P}_{R^{\prime}_{t}(a)|\hat{H}^{t},X_{t}})}}_{\coloneqq
v_{a}}.$ (4)

Using the Cauchy-Schwartz inequality, i.e.

$\sum_{a\in\mathcal{A}}u_{a}v_{a}\leq\sqrt{\sum_{a\in\mathcal{A}}u_{a}^{2}\sum_{a\in\mathcal{A}}v_{a}^{2}},$

with $u_{a}=1$ for all $a\in\mathcal{A}$ and $v_{a}$ defined as above it
follows that (4) is a.s. upper bounded by

$\displaystyle\sqrt{2\sigma^{2}|\mathcal{A}|\sum_{a\in\mathcal{A}}\mathbb{P}_{t}[A^{\star}_{t}=a]^{2}}$
$\displaystyle\qquad\qquad\cdot\sqrt{D_{\textnormal{KL}}(\mathbb{P}_{R^{\prime}_{t}(a)|\hat{H}^{t},X_{t},A^{\star}_{t}=a}\>\|\>\mathbb{P}_{R^{\prime}_{t}(a)|\hat{H}^{t},X_{t}})}.$

Adding the non-negative extra terms
$2\sigma^{2}|\mathcal{A}|\sum_{a\in\mathcal{A}}\mathbb{P}_{t}[A^{\star}_{t}=a]\sum_{b\in\mathcal{A}\setminus
a}\mathbb{P}_{t}[A^{\star}=b]D_{\textnormal{KL}}(\mathbb{P}_{R^{\prime}_{t}(b)|\hat{H}^{t},X_{t},A^{\star}_{t}=a}\>\|\>\mathbb{P}_{R^{\prime}_{t}(b)|\hat{H}^{t},X_{t}})$
in the square root gives

$\displaystyle\mathbb{E}_{t}[R^{\star}_{t}-R_{t}]\leq\sqrt{2\sigma^{2}|\mathcal{A}|\textup{I}_{t}(A^{\star}_{t};R_{t}|\hat{A}_{t})}\textnormal{
a.s.},$

using that
$\textup{I}_{t}(A^{\star}_{t};R_{t}|\hat{A}_{t})=\sum_{a,b\in\mathcal{A}}\mathbb{P}_{t}[A^{\star}_{t}=a]\mathbb{P}_{t}[A^{\star}_{t}=b]D_{\textnormal{KL}}(\mathbb{P}_{R^{\prime}_{t}(b)|\hat{H}^{t},X_{t},A^{\star}_{t}=a}\>\|\>\mathbb{P}_{R^{\prime}_{t}(b)|\hat{H}^{t},X_{t}})$
a.s.. Then, as the Markov chain $A^{\star}_{t}-\Theta-R_{t}\ |\
\hat{H}^{t},X_{t},\hat{A}_{t}$ holds, by the data processing inequality
$\textup{I}_{t}(A^{\star}_{t};R_{t}|\hat{A}_{t})\leq\textup{I}_{t}(\Theta;R_{t}|\hat{A}_{t})$
a.s.. Squaring and reordering the terms yields the desired result. ∎

See 2

###### Proof:

This proof follows the techniques from [21, Proof of Proposition 5] taking
care of the presence of contexts similarly to [1, Proof of Lemma 2]. The
difference with the latter is that instead of using Pinsker’s inequality after
noting that the expected value of a Bernoulli random variable is its
probability of success, restriting the analysis to binary rewards, it uses the
Donsker–Varadhan inequality [30, Theorem 5.2.1] as in the proof of Lemma 1 to
allow sub-Gaussian rewards in the analysis.

Let $\mathcal{A}=\\{a_{1},\ldots,a_{|\mathcal{A}|}\\}$ without loss of
generality and for any round $t\in[T]$, conditioned on the history
$\hat{H}^{t}$ and the context $X_{t}$, we define a random matrix
$M\in\mathbb{R}^{|\mathcal{A}|\times|\mathcal{A}|}$ by specifying the entry
$M_{i,j}$ to be equal to

$\displaystyle\sqrt{\mathbb{P}_{t}[A_{t}^{\star}=a_{i}]\mathbb{P}_{t}[A_{t}^{\star}=a_{j}]}\big{(}\mathbb{E}_{t}[R^{\prime}_{t}(a_{j})|A^{\star}_{t}=a_{i}]-\mathbb{E}_{t}[R^{\prime}_{t}(a_{j})]\big{)}$

for all $i,j\in\big{[}|\mathcal{A}|\big{]}$. Then, the expected regret of the
TS algorithm is equal to the trace of the matrix $M$. Indeed,

$\displaystyle\mathbb{E}_{t}[$ $\displaystyle R^{\star}_{t}-R_{t}]$
$\displaystyle=\sum_{a\in\mathcal{A}}\mathbb{P}_{t}[A^{\star}_{t}=a]\big{(}\mathbb{E}_{t}[R^{\prime}_{t}(a)|A^{\star}_{t}=a]-\mathbb{E}_{t}[R^{\prime}_{t}(a)]\big{)}\textnormal{
a.s.}$ $\displaystyle=\textnormal{Trace}(M)\textnormal{ a.s.}.$

In the same fashion as in [21, Proposition 5], we relate
$\textup{I}_{t}(\Theta;R_{t}|\hat{A}_{t})$ to the squared Frobenius norm of
$M$ as:

$\displaystyle\textup{I}_{t}(\Theta;$ $\displaystyle R_{t}|\hat{A}_{t})$
$\displaystyle\geq\textup{I}_{t}(A^{\star}_{t};R_{t}|\hat{A}_{t})\textnormal{
a.s.}$
$\displaystyle=\sum_{a_{i},a_{j}\in\mathcal{A}}\mathbb{P}_{t}[A^{\star}_{t}=a_{i}]\mathbb{P}_{t}[A^{\star}_{t}=a_{j}]$
$\displaystyle\quad\quad\cdot
D_{\textnormal{KL}}(\mathbb{P}_{R^{\prime}_{t}(a_{j})|\hat{H}^{t},X_{t},A^{\star}_{t}=a_{i}}\>\|\>\mathbb{P}_{R^{\prime}_{t}(a_{j})|\hat{H}^{t},X_{t}})\textnormal{
a.s.}$
$\displaystyle\geq\sum_{a_{i},a_{j}\in\mathcal{A}}\mathbb{P}_{t}(A^{\star}_{t}=a_{i})\mathbb{P}_{t}(A^{\star}_{t}=a_{j})$
$\displaystyle\quad\quad\cdot\frac{1}{2\sigma^{2}}\big{(}\mathbb{E}_{t}[R^{\prime}_{t}(a_{j})|A^{\star}_{t}=a_{i}]-\mathbb{E}_{t}[R^{\prime}_{t}(a_{j})]\big{)}^{2}\textnormal{
a.s.}$ $\displaystyle=\frac{1}{2\sigma^{2}}||M||_{F}^{2}\textnormal{ a.s.},$

where the last inequality is obtained again using the Donsker-Varadhan
inequality [30, Theorem 5.2.1] as in [20, Lemma 3]. Combining the last two
equations and using the inequality
$\textnormal{trace}(M)\leq\sqrt{\textnormal{rank}(M)}||M||_{F}$ [21, Fact 10],
it comes that

$\displaystyle\Gamma_{t}=\frac{\mathbb{E}_{t}[R^{\star}_{t}-R_{t}]^{2}}{\textup{I}_{t}(\Theta;R_{t}|\hat{A}_{t})}\leq
2\sigma^{2}\frac{\textnormal{Trace}(M)^{2}}{||M||_{F}^{2}}\leq
2\sigma^{2}\textnormal{Rank}(M)\textnormal{ a.s.}.$

The proof concludes showing the rank of the matrix $M$ is upper bounded by
$d$. For the sake brevity, we define
$\Theta_{t}\coloneqq\mathbb{E}_{t}[\Theta]$ and
$\Theta_{t,i}\coloneqq\mathbb{E}_{t}[\Theta|A^{\star}_{t}=a_{i}]$ for all
$i\in\big{[}|\mathcal{A}|\big{]}$. We then have
$\mathbb{E}_{t}[\langle\Theta,m(X_{t},a_{j})\rangle]=\langle\Theta_{t},m(X_{t},a_{j})\rangle$
a.s. and
$\mathbb{E}_{t}[\langle\Theta,m(X_{t},a_{j})\rangle|A^{\star}_{t}=a_{i}]=\langle\Theta_{t,i},m(X_{t},a_{j})\rangle$
a.s.. Since the inner product is linear, we can rewrite each entry $M_{i,j}$
of the matrix $M$ as

$\displaystyle\sqrt{\mathbb{P}_{t}(A_{t}^{\star}=a_{i})\mathbb{P}_{t}(A_{t}^{\star}=a_{j})}\langle\Theta_{t,i}-\Theta_{t},m(X_{t},a_{j})\rangle.$

Equivalently, the matrix $M$ can be written as

$\displaystyle\begin{bmatrix}\sqrt{\mathbb{P}_{t}[A_{t}^{\star}=a_{1}]}(\Theta_{t,1}-\Theta_{t})\\\
\vdots\\\
\sqrt{\mathbb{P}_{t}[A_{t}^{\star}=a_{|\mathcal{A}|}]}(\Theta_{t,|\mathcal{A}|}-\Theta_{t})\end{bmatrix}\begin{bmatrix}\sqrt{\mathbb{P}_{t}[A_{t}^{\star}=a_{1}]}m(X_{t},a_{1})\\\
\vdots\\\
\sqrt{\mathbb{P}_{t}[A_{t}^{\star}=a_{|\mathcal{A}|}]}m(X_{t},a_{|\mathcal{A}|})\end{bmatrix}^{\intercal}.$

This rewriting highlights that $M$ can be written as the product of a
$|\mathcal{A}|$ by $d$ matrix and a $d$ by $|\mathcal{A}|$ matrix and
therefore has a rank lower or equal than $\min(d,|\mathcal{A}|)$. ∎