# Chained Information-Theoretic bounds and Tight Regret Rate for Linear Bandit
Problems

Amaury Gouverneur, Borja Rodríguez-Gálvez, Tobias J. Oechtering, and Mikael
Skoglund
KTH Royal Institute of Technology
{amauryg, borjarg, oech<EMAIL_ADDRESS>

###### Abstract

This paper studies the Bayesian regret of a variant of the Thompson-Sampling
algorithm for bandit problems. It builds upon the information-theoretic
framework of [1] and, more specifically, on the rate-distortion analysis from
[2], where they proved a bound with regret rate of $O(d\sqrt{T\log(T)})$ for
the $d$-dimensional linear bandit setting. We focus on bandit problems with a
metric action space and, using a chaining argument, we establish new bounds
that depend on the metric entropy of the action space for a variant of
Thompson-Sampling. Under suitable continuity assumption of the rewards, our
bound offers a tight rate of $O(d\sqrt{T})$ for $d$-dimensional linear bandit
problems. ††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.

##  1 Introduction

Bandit problems are a class of decision problems in which an agent interacts
sequentially with an unknown environment by choosing actions and earning
rewards in return. The goal of the agent is to maximize its expected
cumulative reward, which is the expected sum of rewards that it will earn
throughout its interaction with the environment. This necessitates a delicate
balance between the exploration of different actions to gather information for
potential future rewards, and the exploitation of known actions to receive
immediate gains. The theoretical study of the performance of an algorithm in a
bandit problem is done by analyzing the _expected regret_ , which is defined
as the difference between the cumulative reward of the algorithm and the
hypothetical cumulative reward that an oracle would obtain by choosing the
optimal action at each time step. An effective method for achieving small
regret is the Thomson Sampling (TS) algorithm [3], which, despite its
simplicity, has shown remarkable performance [4, 5, 6].

Studying the Thomspon Sampling regret, [1] introduced the concept of
information ratio, a statistic that captures the trade-off between the
information gained by the algorithm about the environment and the immediate
regret. They used this concept to provide a general upper bound for finite
action spaces $\mathcal{A}$ that depends on the entropy of the optimal action
$\textup{H}(A^{\star})$, the time horizon $T$ (the total number of times that
the agent interacts with the environment), and a problem-dependent upper bound
on the information-ratio $\Gamma$, namely $\sqrt{\Gamma\cdot
T\cdot\textup{H}(A^{\star})}$. For finite environment parameter spaces, under
a Lipschitz continuity assumption of the expected reward and using Lipschitz
maximal inequality argument, Dong and Van Roy [2] were able to control the
regret of the TS algorithm via a ”compressed statistic” $\Theta_{\varepsilon}$
of the environment paramers $\Theta$, with a bound of the form
$\varepsilon\cdot T+\sqrt{\Gamma\cdot
T\cdot\textup{H}(\Theta_{\varepsilon})}$. In particular, they derived a near
optimal regret rate of $O(d\sqrt{T\log T})$ for $d$-dimensional linear bandit
problems.

In this paper, building on the work of [2], we explored the use of the
chaining technique for bandit problems where the rewards exhibit some
subgaussian continuity property with respect to the action space. We
introduced the _Two Steps Thompson Sampling_ (2-TS), a variant of the original
algorithm where the history is updated every time steps. For this algorithm,
we derive a bound that captures the continuity property of the reward process
and depends on the metric entropy of the action space. Notably our bound does
not require finite environment or action space and holds for continuous action
spaces. For the class of linear bandit problems, we obtained a bound in
$O(d\sqrt{T})$ matching the best possible regret $\Omega(d\sqrt{T})$ from [7].

The rest of the paper is organized as follows. Section 2 presents the bandit
problem setup, gives a definition of the Bayesian expected regret, introduces
Two Steps Thompson Sampling algorithm and the specific notations. Section 3
explains the idea of the bounding technique, defines the required tools and
assumptions we will be using. Section 4 states and proves our main theorem.
Section 5 applies our theorem to the important case of linear bandit problems
and derives several specific bounds before giving an deriving a bound for
linear bandit problems with a ball structured action space. Finally, Section 6
discusses our results and possible extensions and future work.

##  2 Problem setup

We consider a sequential decision problem, where at each time step (or round)
$t\in\\{1,\ldots,T\\}$, an agent interacts with an environment by selecting an
action $A_{t}$ from a action set $\mathcal{A}$ and, based on that action,
receives a real valued reward $R_{t}\in\mathbb{R}$. The pair of the selected
action and the received reward is collected in a history $H^{t+1}=H^{t}\cup
H_{t+1}$, where $H_{t+1}=\\{A_{t},R_{t}\\}$, that will be accessible to the
agent in the next round. The procedure repeats until the last round $t=T$.

Following the Bayesian framework, we consider the environment to be
characterized by some parameters $\theta\in\mathcal{O}$, unknown to the agent,
that are sampled from a known prior distribution $\mathbb{P}_{\Theta}$. This
prior, together with the reward distribution $\mathbb{P}_{R|A,\Theta}$,fully
describes the bandit problem. As the reward distribution depends on the
selected action and the environment parameters, it may be written as
$R_{t}=R(A_{t},\Theta)$ for some possibly random function
$R:\mathcal{A}\times\mathcal{O}\to\mathbb{R}$.

The goal of the agent is to take a sequence of actions that maximizes the
total collected reward. More specifically, the agent seeks to learn a policy
$\varphi=\\{\varphi_{t}:\mathcal{H}^{t}\to\mathcal{A}\\}_{t=1}^{T}$ that, for
each time $t\in\\{1,\ldots,T\\}$, selects an action $A_{t}$ based on the
history $H^{t}$ such that it maximizes the _expected cumulative reward_
$R_{T}(\varphi)\coloneqq\mathbb{E}\left[\sum_{t=1}^{T}R(\varphi_{t}(H^{t}),\Theta)\right]$.

###  2.1 The Bayesian expected regret

The Bayesian expected regret quantifies the difference between the expected
cumulative reward achieved by the agent following a policy $\varphi$ and the
optimal expected cumulative reward that could be obtained by an _omniscient_
agent having access to the true reward function and selecting the action
yielding the highest expected reward.

######  Definition 1 (Optimal cumulative reward)

The _optimal cumulative reward_ of a bandit problem is defined as

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

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

We denote a policy that achieves the supremum of Definition 1 as
$\psi^{\star}$ and we refer to the action it selects as the _optimal action_
$A^{\star}\coloneqq\psi^{\star}(\Theta)$. We make the following technical
assumption on the action set to ensure that such a policy exists.

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

The set of actions $\mathcal{A}$ is compact.

The difference between the optimal cumulative reward and the expected
cumulative reward of a policy $\varphi$ is called the Bayesian expected regret
of $\varphi$, denoted $\textnormal{REG}_{T}(\varphi)$.

######  Definition 2 (Bayesian expected regret)

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

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

###  2.2 Thompson Sampling algorithm and the Two Steps variant

One of the most popular and most studied algorithm for solving bandit problems
is the _Thompson Sampling_ (TS) algorithm [4, 5, 6, 2]. TS works by sampling a
Bayesian estimate of the environment parameters from the posterior
distribution, and taking the optimal action for the sampled estimate.
Specifically, at each time step $t\in\\{1,\ldots,T\\}$, the agent draws a
Bayesian estimate $\hat{\Theta}_{t}$ based on the past collected history
$H^{t}$, takes the corresponding optimal action
$\hat{A_{t}}=\psi^{\star}(\hat{\Theta}_{t})$, receives a reward $R_{t}$, and
updates the history $H^{t+1}=\\{H^{t},\hat{A}_{t},R_{t}\\}$.

In this work, we consider a variation of TS, that we refer to as _Two Steps
Thompson Sampling_ (2-TS). The key difference between this algorithm and the
TS algorithm is that the history is updated every two time steps111We
implicitly assume that, for Two Steps Thompson Sampling, the total number of
steps $T$ is an even number.. Intuitively, the algorithm will behave the same,
but will wait to have collected two rewards before updating its history, thus
taking slightly less informed actions half of the time. This difference will
be important to implement the chaining technique later on. The pseudocode for
Two Steps Thompson Sampling is given in Algorithm 1.

Algorithm 1 Two Steps Thompson Sampling algorithm

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

2: for $t=1$ to T do

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

4: Take the corresponding optimal action
$\hat{A}_{t}=\psi^{\star}(\hat{\Theta}_{t})$.

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

6: if $t$ is even then

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

8: else

9: Keep the history $H^{t+1}=H^{t}$.

10: end if

11: end for

###  2.3 Notation specific to bandit problems

Since the $\sigma$-algebras of the history $H^{t}$ are often used in the
conditioning of the expectations and probabilities coming up in the analysis,
similarly to [1, 2, 8, 9], we define the operators
$\mathbb{E}_{t}[\cdot]\coloneqq\mathbb{E}[\cdot|H^{t}]$ and
$\mathbb{P}_{t}[\cdot]\coloneqq\mathbb{P}[\cdot|H^{t}]$, whose outcomes are
$\sigma(\mathcal{H}^{t})$-measurable random variables and
$\mathcal{H}=\mathcal{A}\times\mathbb{R}$.

Analogously, we define
$\textup{I}_{t}(A^{\star};R_{t})\coloneqq\mathbb{E}_{t}[\textup{D}_{\textnormal{KL}}(\mathbb{P}_{R_{t}|H^{t},A^{\star}}\lVert\mathbb{P}_{R_{t}|H^{t}})]$
as the _disintegrated_ conditional mutual information between the optimal
action $A^{\star}$ and the reward $R_{t}$, _given the history $H^{t}$_, see
[10, Definition 1.1], which is itself also a
$\sigma(\mathcal{H}^{t})$-measurable random variable.

When it is clear from the context that the random rewards depend on the
environment parameters $\Theta$, we will often use the notation $R(A_{t})$ as
a shorthand for $R(A_{t},\Theta)$ to simplify the expressions.

##  3 Chain-link Information Ratio and Chaining Technique

In bandit problems where the rewards of nearby actions exhibit some continuity
property, we aim to exploit this dependence using a chaining argument. More
specifically, our idea is to approach the _Two Step Thompson Sampling_
algorithm by a chain of increasingly accurate approximations, which we refer
to as _“approximate learning”_.

Inspired by [2], our construction relies on the existence of a sequence of
finer and finer quantizations $\\{A^{\star}_{k}\\}_{k=k_{0}}^{\infty}$ of the
optimal action $A^{\star}$ and a corresponding carefully crafted action
sampling function $f_{t}^{k}:\mathcal{A}\to\mathcal{A}$ for each round
$t\in\\{1,\ldots,T\\}$. This quantization and sampling functions are designed
to satisfy the following three requirements simultaneously:

  1. (i)

The quantizations $A^{\star}_{k}$ are less informative than $A^{\star}$, that
is, $\textup{H}(A^{\star}_{k})\leq\textup{H}(A^{\star})$ for all $k\geq
k_{0}$.

  2. (ii)

At each round $t\in\\{1,\ldots,T\\}$, the _Two Step Thompson Sampling_ regret
can be written as an infinite sum of the difference between the approximate
learning regrets:

$\displaystyle\mathbb{E}_{t}$
$\displaystyle\Big{[}R(A^{\star})-R(\hat{A}_{t})\Big{]}=$
$\displaystyle\sum_{k=k_{0}+1}^{\infty}\mathbb{E}_{t}\Big{[}\Big{(}R(f_{t}^{k}(A^{\star}_{k}))-R(f_{t}^{k}(\hat{A}_{t,k}))\Big{)}-\Big{(}R(f_{t}^{k-1}(A^{\star}_{k-1}))-R(f_{t}^{k-1}(\hat{A}_{t,k-1}))\Big{)}\Big{]}.$

  3. (iii)

For each time step $t\in\\{1,\ldots,T\\}$, and for every $k>k_{0}$, the regret
difference between the $k^{\textnormal{th}}$-consecutive _“approximate
learning”_ can be bounded using the information gained about the quantization
$A^{\star}_{k}$ while, at the same time, it reveals no more information about
the quantization $A^{\star}_{k}$ than Two Step Thompson Sampling.

###  3.1 Nets and quantizations

When designing the quantization $A^{\star}_{k}\in\mathcal{A}_{k}$ of the
optimal action, we face two conflicting goals: on the one hand, we want the
quantization to be little informative about $A^{\star}$ while, on the other
hand, we want to ensure that $\mathcal{A}_{k}$ converges quickly to a good
approximation of $\mathcal{A}$. This dual objective naturally leads to
considering $\varepsilon$-nets.

######  Definition 3 ($\varepsilon$-net and covering number)

A set $\mathcal{N}$ is called an _$\varepsilon$ -net_ for $(\mathcal{A},\rho)$
if, for every $a\in\mathcal{A}$, there is a $\pi(a)\in\mathcal{N}$ such that
$\rho(a,\pi(a))\leq\varepsilon$. The smallest cardinality of an
$\varepsilon$-net for $(\mathcal{A},\rho)$ is called the _covering number_ ,
that is

$\mathcal{N}(\mathcal{A},\rho,\varepsilon)\triangleq\inf\big{\\{}|\mathcal{N}|:\textnormal{
$\mathcal{N}$ is an $\varepsilon$-net of $(\mathcal{A},\rho)$}\big{\\}}.$

The covering number $\mathcal{N}(\mathcal{A},\rho,\varepsilon)$ can be
understood as a measure of the complexity of the action set $\mathcal{A}$ at
the resolution $\varepsilon$. Equipped with this new concept, a possible
$k^{\textnormal{th}}$-quantization $A^{\star}_{k}$ is the quantization of the
optimal action $A^{\star}$ at the scale $2^{-k}$.

######  Definition 4 ($k^{\textnormal{th}}$-quantization)

Let $\mathcal{A}_{k}$ be a $2^{-k}$-net for $(\mathcal{A},\rho)$ with an
associated mapping $\pi_{k}:\mathcal{A}\to\mathcal{A}_{k}$, such that the
mappings $\pi_{k}$ are restricted to those of the form
$\pi_{k}=\pi_{k}^{\prime}\circ\pi_{k+1}$, where
$\pi_{k}^{\prime}:\mathcal{A}_{k+1}\to\mathcal{A}_{k}$. We define
$A^{\star}_{k}=\pi_{k}(A^{\star})$ as the $k^{\textnormal{th}}$-quantization
of the optimal action $A^{\star}$ with respect to $(\mathcal{A},\rho)$.
Similarly, the quantization $\hat{A}_{t,k}=\pi_{k}(\hat{A}_{t})$ is the
$k^{\textnormal{th}}$-quantization of the sampled action $\hat{A}_{t}$.

Note that $A^{\star}_{k}$ is completely determined by $A^{\star}_{k+1}$ via
the mapping $\pi_{k}^{\prime}:\mathcal{A}_{k+1}\to\mathcal{A}_{k}$. In the
following, we set $k_{0}$ to be the largest integer such that
$2^{-k_{0}}\geq\textnormal{diam}(\mathcal{A})$.

###  3.2 Existence of the _“approximate learning”_

The sequence of quantizations $\\{A^{\star}_{k}\\}_{k=k_{0}}^{\infty}$ given
in Definition 4 satisfy Requirement (i) since there is a deterministic mapping
between $A^{\star}$ and $A^{\star}_{k}$ [11, Theorem 1.4 (f)]. We claim that
for each time step $t\in\\{1,\ldots,T\\}$, and for each $k>k_{0}$, there
exists a random function $f_{t}^{k}:\mathcal{A}_{k}\to\mathcal{A}_{k}$ that
satisfies Requirements (ii) and (iii).

###### Proposition 1

Let $\\{A^{\star}_{k}\\}_{k=k_{0}}^{\infty}$ be defined as in Definition 4.
For each time step $t\in\\{1,\ldots,T\\}$, there exists a sequence of random
functions $\\{f_{t}^{k}\\}_{k=k_{0}}^{\infty}$ that for each $k>k_{0}$,
satisfies the following:

  1. (i)

$\mathbb{E}_{t}\Big{[}R(f_{t}^{k_{0}}(A^{\star}_{k_{0}}))-R(f_{t}^{k_{0}}(\hat{A}_{t,k_{0}}))\Big{]}=0,$

  2. (ii)

$\lim_{k\to\infty}\mathbb{E}_{t}\Big{[}R(f_{t}^{k}(A^{\star}_{k}))-R(f_{t}^{k}(\hat{A}_{t,k}))\Big{]}=\mathbb{E}_{t}\Big{[}R(A^{\star})-R(\hat{A}_{t})\Big{]},$
and

  3. (iii)

$\textup{I}_{t}\big{(}A^{\star}_{k};R(f_{t}^{k}(\hat{A}_{t,k})),R(f_{t}^{k-1}(\hat{A}_{t,k-1}))\leq\textup{I}_{t}(A^{\star}_{k};R(\hat{A}_{t}),R(\hat{A}_{t}^{\prime})\big{)}$,
a.s.

where in (iii) the sampled actions $\hat{A}_{t}$ and $\hat{A}_{t}^{\prime}$
are identically distributed.

###### Proof 1

The proof follows closely the proof of [2, Proposition 2] and is given in
Appendix B.1.

###  3.3 Subgaussian process, smooth rewards and chain-link information ratio

The motivation for using a chaining technique is our aim to derive a regret
bound that could capture effectively the dependence between the rewards of
nearby actions. We conceptualize this dependence considering that the rewards
are subgaussian with respect to the actions.

######  Definition 5 (Subgaussian process)

A stochastic process $\\{R_{a}\\}_{a\in\mathcal{A}}$ on the metric space
$(\mathcal{A},\rho)$ is called _subgaussian_ if for all $a,b\in\mathcal{A}$
and all $\lambda>0$

$\log\mathbb{E}\bigg{[}e^{\lambda(R_{a}-R_{b})}\bigg{]}\leq\frac{\lambda^{2}\rho(a,b)^{2}}{2}.$

Technically, for a process $\\{R_{a}\\}_{a\in\ cA}$ to be subgaussian it is
also required that $\mathbb{E}[R_{a}]=0$ for all $a\in\mathcal{A}$, see, for
example [12, Definition 5.20]. However, we do not require this restriction
moving forward. One way to interpret the subgaussian process property is to
understand it as an ”in probability continuity” requirement. Actually,
Definition 5, up to constant terms, can be equivalently written as

$\displaystyle\mathbb{P}[|R_{a}-R_{b}|\geq t]\leq 2e^{-Ct^{2}\rho(a,b)^{2}}$

for all $t\geq 0$ and all all $a,b\in\mathcal{A}$, and for some $C>0$.

Lastly, to ensure that the difference of regret between consecutive
_approximate learning_ vanishes asymptotically, we can impose the following
mild technical assumption.

######  Definition 6 (Separable process)

A stochastic process $\\{R_{a}\\}_{a\in\mathcal{A}}$ is called _separable_ if
there is a countable set $\mathcal{A}^{\prime}\subseteq\mathcal{A}$ such that,
for all $a\in\mathcal{A}$

$R_{a}\in\lim_{\begin{subarray}{c}a^{\prime}\to a\\\
a^{\prime}\in\mathcal{A}^{\prime}\end{subarray}}R_{a^{\prime}}\ \textnormal{
a.s.}$

We refer to rewards satisfying both definition 5 and 6 as _smooth rewards_ on
the metric space $(\mathcal{A},\rho)$.

######  Definition 7 (Smooth rewards)

We say that the rewards are _smooth on the metric space $(\mathcal{A},\rho)$_,
if for all environment parameters $\theta\in\mathcal{O}$, the random rewards
$\\{R(a,\theta)\\}_{a\in\mathcal{A}}$ form a separable subgaussian process on
$(\mathcal{A},\rho)$.

To control the difference of regret between successive _approximate learning_
, it is useful to introduce the concept of _chain-link information ratio_. It
is a direct adaptation of our chaining technique to the _information ratio_
introduced by [1] and later used by [2].

######  Definition 8 (Chain-link information ratio)

For each time step $t\in\\{1,\ldots,T\\}$, and for each $k>k_{0}$, we define
the _chain-link information ratio_ as

$\Gamma_{t,k}\coloneqq\frac{\mathbb{E}_{t}\Big{[}\Big{(}R(f_{t}^{k}(A^{\star}_{k}))-R(f_{t}^{k}(\hat{A}_{t,k}))\Big{)}-\Big{(}R(f_{t}^{k-1}(A^{\star}_{k-1}))-R(f_{t}^{k-1}(\hat{A}_{t,k-1}))\Big{)}\Big{]}^{2}}{\textup{I}_{t}(f_{t}^{k}(A^{\star}_{k}),f_{t}^{k-1}(A^{\star}_{k-1});R(f_{t}^{k}(\hat{A}_{t,k})),R(f_{t}^{k-1}(\hat{A}_{t,k-1})))}$

where $A^{\star}_{k},A^{\star}_{k-1}$ and $\hat{A}_{t,k},\hat{A}_{t,k}$ are
the $k^{\textnormal{th}}$ and $(k-1)^{\textnormal{th}}$ quantizations of
$A^{\star}$ and $\hat{A}_{t}$ respectively and where the random functions
$f_{t}^{k}$ and $f_{t}^{k-1}$ satisfy the conditions of Proposition 1,

There is no particular interpretation of the chain-link information ratio. The
purpose of its introduction is to unify elegantly specific results via
problem-dependent upper bounds on $\Gamma_{t,k}$ similarly to what is done in
prior works for the information ratio [1, 2] and the lifted information ratio
[8, 9].

##  4 Main result

In this section, we leverage the previously introduced concepts to derive a
general chained bound on the Two Steps Thompson Sampling regret for bandit
problems with smooth rewards. We obtain a bound that depends on the complexity
of the action space. Remarkably, through the use of Lemma 1, our result hold
for continuous action spaces. We note that 1 could be applied to [2] as a
generalization of their [2, Lemma 1], thus extending their results to infinite
and continuous environment spaces.

######  Theorem 1 (Chained bound)

For bandit problems with smooth rewards on the metric space
$(\mathcal{A},\rho)$, the _2-TS_ expected cumulative regret after $T$ steps is
bounded as

$\displaystyle\textnormal{REG}^{\textnormal{2-TS}}_{T}\leq\sum_{k=k_{0}+1}^{\infty}\sqrt{2\cdot\bar{\Gamma}_{k}\cdot
T\cdot\textup{H}(A^{\star}_{k})},$

where $A^{\star}_{k}$ is the $k^{\textnormal{th}}$-quantization about the
optimal action $A^{\star}$ with respect to $(\mathcal{A},\rho)$ and where for
each $k>k_{0}$, and $\bar{\Gamma}_{k}$ is a upper bound on
$\mathbb{E}[\Gamma_{t,k}]$.

###### Proof 2

We show that

$\displaystyle\textnormal{REG}^{\textnormal{2-TS}}_{T}$
$\displaystyle=\sum_{t=1}^{T}\mathbb{E}[R(A^{\star})-R(\hat{A}_{t})]$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}2\sum_{1\leq t\leq
T,t\textnormal{ odd}}\mathbb{E}[R(A^{\star})-R(\hat{A}_{t})]$
$\displaystyle=2\sum_{1\leq t\leq T,t\textnormal{
odd}}\mathbb{E}\Big{[}\mathbb{E}_{t}[R(A^{\star})-R(\hat{A}_{t})]\Big{]}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}2\sum_{1\leq t\leq
T,t\textnormal{
odd}}\mathbb{E}\Big{[}\sum_{k=k_{0}+1}^{\infty}\mathbb{E}_{t}\Big{[}\Big{(}R(f_{t}^{k}(A^{\star}_{k}))-R(f_{t}^{k}(\hat{A}_{t,k}))\Big{)}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad-\Big{(}R(f_{t}^{k-1}(A^{\star}_{k-1}))-R(f_{t}^{k-1}(\hat{A}_{t,k-1}))\Big{)}\Big{]}\Big{]}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}2\sum_{1\leq t\leq
T,t\textnormal{
odd}}\sum_{k=k_{0}+1}^{\infty}\mathbb{E}\Big{[}\sqrt{\Gamma_{t,k}\cdot\textup{I}_{t}(A^{\star}_{k},A^{\star}_{k-1};R(f_{t}^{k}(\hat{A}_{t,k})),R(f_{t}^{k-1}(\hat{A}_{t,k-1})))}\Big{]}$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}2\sum_{1\leq t\leq
T,t\textnormal{
odd}}\sum_{k=k_{0}+1}^{\infty}\sqrt{\mathbb{E}[\Gamma_{t,k}]\cdot\textup{I}(A^{\star}_{k};R(\hat{A}_{t}),R(\hat{A}_{t+1})|H^{t})}$
$\displaystyle\stackrel{{\scriptstyle(e)}}{{\leq}}2\sum_{k=k_{0}+1}^{\infty}\sqrt{\frac{T}{2}\cdot\bar{\Gamma}_{k}\cdot\sum_{1\leq
t\leq T,t\textnormal{
odd}}\textup{I}(A^{\star}_{k};R(\hat{A}_{t}),R(\hat{A}_{t+1}))|H^{t})}$
$\displaystyle\stackrel{{\scriptstyle(f)}}{{\leq}}\sum_{k=k_{0}+1}^{\infty}\sqrt{2\cdot\bar{\Gamma}_{k}\cdot
T\cdot\sum_{1\leq t\leq T,t\textnormal{
odd}}\textup{I}(A^{\star}_{k};\hat{A}_{t},R(\hat{A}_{t}),\hat{A}_{t+1},R(\hat{A}_{t+1}))|H^{t})}$
$\displaystyle\stackrel{{\scriptstyle(g)}}{{=}}\sum_{k=k_{0}+1}^{\infty}\sqrt{2\cdot\bar{\Gamma}_{k}\cdot
T\cdot\textup{I}(A^{\star}_{k};H^{T})}$
$\displaystyle\stackrel{{\scriptstyle(h)}}{{\leq}}\sum_{k=k_{0}+1}^{\infty}\sqrt{2\cdot\bar{\Gamma}_{k}\cdot
T\cdot\textup{H}(A^{\star}_{k})}$

where (a) follows since the history of the of 2-TS is being updated every 2
time steps; (b) follows from the definition of the approximate learning; (c)
follows from the definition of $\Gamma_{t,k}$ and the data-processing
inequality; (d) follows from consecutively using the fact that
$A^{\star}_{k-1}$ is completely determined by $A^{\star}_{k}$, then using
Proposition 1 (iii), and finally applying Jensen’s inequality ; (e) follows
from the definition of $\bar{\Gamma}_{k}$ and the application of the Cauchy-
Schwartz inequality; (f) results from the ”more data, more information”
property [11, Proposition 2.3.5]; (g) follows from the chain rule for mutual
information; and (h) comes from [11, Proposition 2.4.4] and the fact that
$\mathcal{A}_{k}$ is a finite set.

In the next section, we present application of Theorem 1 to derive explicit
regret bounds for particular settings of bandit problems with structure and
show that our bound offers a tight regret rate for the linear bandit problem.

##  5 Applications to linear bandit problems

In _linear bandits_ problems, each action is parameterized by a feature vector
and the associated expected reward can be written as the inner product between
the feature vector and the environment parameter. Mathematically, a
$d$-dimensional linear bandit problem is a bandit problem with
$\mathcal{A},\mathcal{O}\subset\mathbb{R}^{d}$ and such that for all
$a\in\mathcal{A}$ and all $\theta\in\mathcal{O}$ we have

$\displaystyle\mathbb{E}[R(a,\theta)]=\langle a,\theta\rangle,$

where the expectation is taken over the randomness of the reward function.

Using a similar analysis as Russo and Van Roy [1], we can bound the chain-link
information ratio in linear bandits via the dimension of the action space. The
proof is given in Appendix B.2.

###### Proposition 2

For $d$-dimensional linear bandit problems with smooth rewards on the metric
space $(\mathcal{A},\rho)$, for each $t\in\\{1,\ldots,T\\}$, and each
$k>k_{0}$, we have that

$\displaystyle\Gamma_{t,k}\leq 2\cdot(6\cdot 2^{-k})^{2}\cdot d,$

where $\Gamma_{t,k}$ is the $k^{\textnormal{th}}$-chain-link information
ratio.

Combining Proposition 2 and Theorem 1 leads to the following bound on the
_2-TS_ regret for linear bandit problems with smooth rewards.

######  Theorem 2 (Smooth linear bandit)

For $d$-dimensional linear bandit problems with smooth rewards on the metric
space $(\mathcal{A},\rho)$, the _2-TS_ expected cumulative regret after $T$
steps is bounded by

$\displaystyle\textnormal{REG}^{\textnormal{2-TS}}_{T}$ $\displaystyle\leq
12\sum_{k=k_{0}+1}^{\infty}2^{-k}\sqrt{d\cdot
T\cdot\textup{H}(A^{\star}_{k})},$

where $A^{\star}_{k}$ is the $k^{\textnormal{th}}$ quantization of the optimal
action $A^{\star}$ with respect to the metric space $(\mathcal{A},\rho)$, as
defined in Definition 4.

From Theorem 2, we can derive a bound that depends on the _entropy integral_.
The proof follows the steps from [12, Corollary 5.25] and is given in Appendix
B.3.

######  Corollary 1 (Entropy integral)

For a linear bandit of dimension $d$, with smooth rewards on the metric space
$(\mathcal{A},\rho)$, the _2-TS_ expected cumulative regret after $T$ steps is
bounded as

$\displaystyle\textnormal{REG}^{\textnormal{2-TS}}_{T}$ $\displaystyle\leq
24\sqrt{d\cdot
T}\int_{0}^{\infty}\sqrt{\log(|\mathcal{N}(\mathcal{A},\rho,\varepsilon)|)}d\varepsilon,$

where $\mathcal{N}(\mathcal{A},\rho,\varepsilon)$ is the $\varepsilon$-net of
smallest cardinality for $(\mathcal{A},\rho)$.

For linear bandit problems where the possible actions lie in the unit ball,
with the help of a covering argument, we come to the following result. The
proof is given in Appendix B.4.

###### Proposition 3

For $d$-dimensional linear bandits with smooth rewards with respect to
$(\mathcal{A},||.||_{2})$ and a ball-structured action space
$\mathcal{A}\subseteq\overline{\mathbf{B}_{d}(0,1)}$, where
$\overline{\mathbf{B}_{d}(0,1)}$ is the $d$-dimensional closed Euclidean unit
ball, the _2-TS_ expected cumulative regret is bounded as

$\displaystyle\textnormal{REG}^{\textnormal{2-TS}}$ $\displaystyle\leq 7\cdot
d\sqrt{T}.$

The remarkable property of the above bound is that it is the first
information-theoretic bound on the regret of an algorithm for linear bandits
problem that only depends on the dimension $d$ and the square root of the
total number of steps $T$. It improves on the bound $O(d\sqrt{T\log(T)})$ from
Dong and Van Roy [2, Theorem 2] and matches the the minimax lower bound
$\Omega(d\sqrt{T})$ proven by Dani et al. [7, Theorem 3] thus suggesting that
Two Steps Thompson Sampling is optimal in this context.

##  6 Conclusion

In this paper, we studied bandit problems with rewards that exhibit some
continuity property with respect to the action space. We have introduced a
variation of the Thompson Sampling algorithm, which we named the Two Step
Thompson Sampling. The sole difference between this algorithm and the original
Thompson Sampling algorithm is that the history is updated every two time
steps. In Theorem 1, we have demonstrated using a chaining argument that the
Two Steps Thompson Sampling cumulative expected regret is bounded from above
by a measure of the complexity of the action space. For $d$-dimensional linear
bandit problems where the rewards form a subgaussian process with respect to
the action space, we obtain a tight regret rate $O(d\sqrt{T})$ that improves
upon the best information-theoretic bounds and matches with the minimax lower
bound $\Omega(d\sqrt{T})$ [7]. Our results raise the question whether it is
possible to obtain such bounds for the original Thompson Sampling algorithm
regret, either via adapting our proof techniques or by relating it to the Two
Steps Thompson Sampling regret. One could imagine analyzing separately the
regrets of the odd time steps than those of the even time steps and try to
apply techniques as in our paper. Future work also include extending our
results to generalized linear bandits and logistic bandit problems.

## References

  * Russo and Van Roy [2015] D. Russo and B. Van Roy, “An Information-Theoretic Analysis of Thompson Sampling,” Jun. 2015, number: arXiv:1403.5341 arXiv:1403.5341 [cs]. [Online]. Available: http://arxiv.org/abs/1403.5341
  * Dong and Van Roy [2020] S. Dong and B. Van Roy, “An Information-Theoretic Analysis for Thompson Sampling with Many Actions,” Jul. 2020, arXiv:1805.11845 [cs, math, stat]. [Online]. Available: http://arxiv.org/abs/1805.11845
  * Thompson [1933] 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.
  * Russo et al. [2018] D. J. Russo, B. Van Roy, A. Kazerouni, I. Osband, Z. Wen _et al._ , “A tutorial on thompson sampling,” _Foundations and Trends® in Machine Learning_ , vol. 11, no. 1, pp. 1–96, 2018.
  * Russo and Van Roy [2017] D. Russo and B. Van Roy, “Learning to Optimize via Information-Directed Sampling,” Jul. 2017, arXiv:1403.5556 [cs]. [Online]. Available: http://arxiv.org/abs/1403.5556
  * Chapelle and Li [2011] O. Chapelle and L. Li, “An empirical evaluation of Thompson sampling,” _Advances in neural information processing systems_ , vol. 24, 2011.
  * Dani et al. [2008] V. Dani, T. P. Hayes, and S. M. Kakade, “Stochastic Linear Optimization under Bandit Feedback,” _21st Annual Conference on Learning Theory_ , vol. 21st Annual Conference on Learning Theory, pp. 355–366, 2008.
  * Neu et al. [2022] G. Neu, I. Olkhovskaia, M. Papini, and L. Schwartz, “Lifting the Information Ratio: An Information-Theoretic Analysis of Thompson Sampling for Contextual Bandits,” _Advances in Neural Information Processing Systems_ , vol. 35, pp. 9486–9498, 2022.
  * Gouverneur et al. [2023] A. Gouverneur, B. Rodríguez-Gálvez, T. J. Oechtering, and M. Skoglund, “Thompson Sampling Regret Bounds for Contextual Bandits with sub-Gaussian rewards,” Apr. 2023, arXiv:2304.13593 [cs, stat]. [Online]. Available: http://arxiv.org/abs/2304.13593
  * Negrea et al. [2020] J. Negrea, M. Haghifam, G. K. Dziugaite, A. Khisti, and D. M. Roy, “Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates,” _arXiv:1911.02151 [cs, math, stat]_ , Jan. 2020, arXiv: 1911.02151. [Online]. Available: http://arxiv.org/abs/1911.02151
  * Yury Polyanskiy [2022] Y. W. Yury Polyanskiy, _Information Theory - From Coding to Learning_ , 1st ed. Cambridge University Press, Oct. 2022.
  * van Handel [2016] R. van Handel, _Probability in High Dimension_. Princeton University, Dec. 2016, vol. APC 550 Lecture Notes.
  * Gray [2013] R. M. Gray, _Entropy and Information Theory - First Edition, Corrected_. Information Systems Laboratory Electrical Engineering Department Stanford University: Springer-Verlag, 2013.

##  Appendix A Additional Lemmata

###### Lemma 1

Consider a space $\mathcal{A}$, two functions $f:\mathcal{A}\to\mathbb{R}_{+}$
and $g:\mathcal{A}\to\mathbb{R}_{+}$, and a probability distribution
$\mathbb{Q}$ on $\mathcal{A}$. Then, there exists a pair
$(a_{1},a_{2})\in\mathcal{A}^{2}$ and a $q\in[0,1]$ such that

$qf(a_{1})+(1-q)f(a_{2})\leq\int_{a\in\mathcal{A}}f(a)\mathrm{d}\mathbb{Q}(a)\quad\textnormal{and}\quad
qg(a_{1})+(1-q)g(a_{2})\leq\int_{a\in\mathcal{A}}g(a)\mathrm{d}\mathbb{Q}(a).$

###### Proof 3

The proof is inspired by to the one from Dong and Van Roy [2, Lemma 2].
Although, it contains key modifications that allow this version of the lemma
to work for general spaces $\mathcal{A}$ that are not necessarily finite.

Let $\bar{F}=\int_{a\in\mathcal{A}}f(a)\mathrm{d}\mathbb{Q}(a)$ and
$\bar{G}=\int_{a\in\mathcal{A}}g(a)\mathrm{d}\mathbb{Q}(a)$. Now, consider the
spaces $\mathcal{A}_{f}\coloneqq\\{a\in\mathcal{A}:f(a)\leq\bar{F}\\}$ and
$\mathcal{A}_{g}\coloneqq\\{a\in\mathcal{A}:g(a)\leq\bar{G}\\}$. If
$\mathcal{A}_{f}\cap\mathcal{A}_{g}\neq\emptyset$, then taking both $a_{1}$
and $a_{2}$ from $\mathcal{A}_{f}\cap\mathcal{A}_{g}$ trivially satisfies the
conditions for all $q\in[0,1]$. Therefore, let us assume that the sets are
disjoint for the rest of the proof.

Consider some $a_{1}\in\mathcal{A}_{f}=\mathcal{A}_{g}^{c}$ and some
$a_{2}\in\mathcal{A}_{g}=\mathcal{A}_{f}^{c}$. The required condition from the
lemma can be re-written as

$q\geq\frac{f(a_{2})-\bar{F}}{f(a_{2})-f(a_{1})}\quad\textnormal{ and }\quad
q\leq\frac{\bar{G}-g(a_{2})}{g(a_{1})-g(a_{2})},$

where the first inequality took into account that $f(a_{1})<f(a_{2})$ by the
definition of the sets $\mathcal{A}_{f}$ and
$\mathcal{A}_{g}=\mathcal{A}_{f}^{c}$. This inequality can, in turn, be
written as

$\frac{f(a_{2})-\bar{F}}{f(a_{2})-f(a_{1})}\leq\frac{\bar{G}-g(a_{2})}{g(a_{1})-g(a_{2})}$

which is equivalent to

$f(a_{2})g(a_{1})-\bar{F}\big{(}g(a_{1})-g(a_{2})\big{)}\leq\bar{G}\big{(}f(a_{2})-f(a_{1})\big{)}+f(a_{1})g(a_{2}).$

At this point, we have all the ingredients to proof the statement by
contradiction. Assume that there is no pair
$(a_{1},a_{2})\in\mathcal{A}_{f}\times\mathcal{A}_{g}$ such that the condition
holds, then it must be that

$f(a_{2})g(a_{1})-\bar{F}\big{(}g(a_{1})-g(a_{2})\big{)}>\bar{G}\big{(}f(a_{2})-f(a_{1})\big{)}+f(a_{1})g(a_{2})$

for every pair $(a_{1},a_{2})\in\mathcal{A}_{f}\times\mathcal{A}_{g}$.
Therefore, we can integrate over all such pairs and the inequality should
still hold, namely

$\displaystyle\int_{\mathcal{A}_{f}}\int_{\mathcal{A}_{g}}\bigg{[}$
$\displaystyle
f(a_{2})g(a_{1})-\bar{F}\big{(}g(a_{1})-g(a_{2})\big{)}\bigg{]}\mathrm{d}\mathbb{Q}(a_{1})\mathrm{d}\mathbb{Q}(a_{2})$
$\displaystyle>\int_{\mathcal{A}_{f}}\int_{\mathcal{A}_{g}}\bigg{[}\bar{G}\big{(}f(a_{2})-f(a_{1})\big{)}+f(a_{1})g(a_{2})\bigg{]}\mathrm{d}\mathbb{Q}(a_{1})\mathrm{d}\mathbb{Q}(a_{2}).$
(1)

To show that (1) cannot happen, we need to introduce some notation. Let
$F^{-}\coloneqq\int_{\mathcal{A}_{f}}f(a)\mathrm{d}\mathbb{Q}(a)$ and
$F^{+}\coloneqq\int_{\mathcal{A}_{g}}f(a)\mathrm{d}\mathbb{Q}(a)$ and note
that $F^{+}+F^{-}=\bar{F}$. Similarly,
$G^{-}\coloneqq\int_{\mathcal{A}_{g}}g(a)\mathrm{d}\mathbb{Q}(a)$ and
$F^{+}\coloneqq\int_{\mathcal{A}_{f}}g(a)\mathrm{d}\mathbb{Q}(a)$ and
$G^{+}+G^{-}=\bar{G}$. Using this notation, we can use Fubini’s theorem in (1)
and re-write it as

$F^{+}G^{+}-(F^{+}+F^{-})(G^{+}-G^{-})>(G^{+}+G^{-})(F^{+}-F^{-})+F^{-}G^{-},$

which can be simplified to

$F^{-}G^{-}>F^{+}G^{+}$

and which is impossible by the definition of $F^{-}$, $F^{+}$, $G^{+}$ and
$G^{-}$, completing the contradiction and therefore the proof.

######  Lemma 2 ([12, Lemma 5.13])

Let $\overline{\mathbf{B}_{d}(0,1)}$ denote the $d$-dimensional closed
Euclidean unit ball. We have
$|\mathcal{N}(\overline{\mathbf{B}_{d}(0,1)},||\cdot||_{2},\varepsilon)=1$ for
$\varepsilon\geq 1$ and

$\displaystyle\bigg{(}\frac{1}{\varepsilon}\bigg{)}^{d}\leq|\mathcal{N}(\overline{\mathbf{B}_{d}(0,1)},||\cdot||_{2},\varepsilon)|\leq\bigg{(}1+\frac{2}{\varepsilon}\bigg{)}^{d}$
$\displaystyle\textnormal{for }0<\varepsilon<1.$

##  Appendix B Proofs

###  B.1 Proof of Proposition 1

For each time step $t\in\\{1,\ldots,T\\}$, we will construct the sequence of
function $\\{f_{t}^{k}\\}_{k=k_{0}}^{\infty}$ by induction and instead of
constructing a sequence that satisfies directly (iii), we will design it such
that for each $k>k_{0}$, it satisfies simultaneously the two following
equations:

$\displaystyle\textup{I}_{t}\big{(}A^{\star}_{k};R(f_{t}^{k}(\hat{A}_{t,k})),R(f_{t}^{k-1}(\hat{A}_{t,k-1}))\Big{)}$
$\displaystyle\leq\textup{I}_{t}\big{(}A^{\star}_{k};R(\hat{A}_{t}),R(f_{t}^{k-1}(\hat{A}_{t,k-1}))\big{)}\textnormal{
and}$ (2)
$\displaystyle\textup{I}_{t}\big{(}A^{\star}_{k+1};R(\hat{A}_{t}),R(f_{t}^{k}(\hat{A}_{t,k}))\big{)}$
$\displaystyle\leq\textup{I}_{t}\big{(}A^{\star}_{k+1};R(\hat{A}_{t}),R(\hat{A}_{t}^{\prime})\big{)},$
(3)

thus ensuring that $f_{t}^{k}$ satisfies (iii).

First, we start by showing that there exists a function $f^{k_{0}}_{t}$ that
satisfies requirement (i) and equation (3). By definition of $k_{0}$, we have
that the cardinality of $\mathcal{A}_{k_{0}}$ is $1$, that is
$\mathcal{A}_{k_{0}}=\\{a_{0}\\}$ for some $a_{0}\in\mathcal{A}$ and, as
$A^{\star}_{k_{0}}\in\mathcal{A}_{k_{0}}$ and
$\hat{A}_{t,k_{0}}\in\mathcal{A}_{k_{0}}$, we have
$A^{\star}_{k_{0}}=\hat{A}_{t,k_{0}}=a_{0}$, thus satisfying requirement (i).
Setting the random function $f_{t}^{k_{0}}$ to have the same conditional
probability distribution as $\mathbb{P}_{A^{\star}|H^{t}}$ ensures equation
(3) is satisfied.

Now, we assume that for each $k\in\\{k_{0},\ldots,K-1\\}$, we have constructed
a function $f_{t}^{k}$ that satisfied (2) and (3). We then want to show that
we can construct a random function $f_{t}^{K}$ that also satisfies (2) and
(3).

First, for each $a_{K,i}\in\mathcal{A}_{K}$ with
$i\in\\{1,\ldots,|\mathcal{A}_{K}|\\}$, we define
$\mathcal{A}_{K,i}=\\{a\in\mathcal{A}:\pi_{K}(a)=a_{K,i}\\}$ as the set of
actions in $\mathcal{A}$ that are mapped to $a_{K,i}$ by the mapping $\pi_{K}$
associated to $\mathcal{A}_{K}$, that is formally. In this way, for each
$a_{K,i}\in\mathcal{A}_{K}$, we can write

$\displaystyle\textup{I}_{t}\big{(}A^{\star}_{K};R(\hat{A}_{t}),R(f_{t}^{K-1}(\hat{A}_{t,K}))|\hat{A}_{t}\in\mathcal{A}_{K,i}\big{)}$
$\displaystyle=\sum_{a\in\mathcal{A}_{K,i}}\mathbb{P}_{t}[\hat{A}_{t}=a|\hat{A}_{t}\in\mathcal{A}_{K,i}]\textup{I}_{t}\big{(}A^{\star}_{K};R(a),R(f_{t}^{K-1}(\hat{A}_{t,K}))|\hat{A}_{t}\in\mathcal{A}_{K,i}\big{)}$
$\displaystyle=\sum_{a\in\mathcal{A}_{K,i}}\mathbb{P}_{t}[\hat{A}_{t}=a|\hat{A}_{t}\in\mathcal{A}_{K,i}]\textup{I}_{t}\big{(}A^{\star}_{K};R(a),R(f_{t}^{K-1}(\hat{A}_{t,K}))\big{)}$

and

$\displaystyle\textup{I}_{t}\big{(}A^{\star}_{K+1};R(\hat{A}_{t}),R(\hat{A}_{t}^{\prime})|\hat{A}_{t}\in\mathcal{A}_{K,i}\big{)}$
$\displaystyle=\sum_{a\in\mathcal{A}_{K,i}}\mathbb{P}_{t}[\hat{A}_{t}=a|\hat{A}_{t}\in\mathcal{A}_{K,i}]\textup{I}_{t}\big{(}A^{\star}_{K+1};R(a),R(\hat{A}_{t}^{\prime})|\hat{A}_{t}\in\mathcal{A}_{K,i}\big{)}$
$\displaystyle=\sum_{a\in\mathcal{A}_{K,i}}\mathbb{P}_{t}[\hat{A}_{t}=a|\hat{A}_{t}\in\mathcal{A}_{K,i}]\textup{I}_{t}\big{(}A^{\star}_{K+1};R(a),R(\hat{A}_{t}^{\prime})\big{)},$

where we used the fact that $A^{\star}_{K}$ and $A^{\star}_{K+1}$ are
independent of $\hat{A}_{t}$ when conditioned on $H^{t}$.

Applying Lemma 1, for each step $t\in\\{1,\ldots,T\\}$ and each
$a_{K,i}\in\mathcal{A}_{K}$, there exist two actions
$a_{K,i}^{t,1},a_{K,i}^{t,2}\in\mathcal{A}_{K,i}$ and a value
$p_{K,i}^{t}\in[0,1]$, such that:

$\displaystyle\textup{I}_{t}\big{(}A^{\star}_{K};$ $\displaystyle
R(\hat{A}_{t}),R(f_{t}^{K-1}(\hat{A}_{t,K}))|\hat{A}_{t}\in\mathcal{A}_{K,i}\big{)}$
$\displaystyle\geq
p_{K,i}^{t}\textup{I}_{t}(A^{\star}_{K};R(a_{K,i}^{t,1}),R(f_{t}^{K-1}(\hat{A}_{t,K}))\big{)}+(1-p_{K,i}^{t})\textup{I}_{t}(A^{\star}_{K};R(a_{K,i}^{t,2}),R(f_{t}^{K-1}(\hat{A}_{t,K}))\big{)}$

and

$\displaystyle\textup{I}_{t}\big{(}A^{\star}_{K+1};$ $\displaystyle
R(\hat{A}_{t}),R(\hat{A}_{t}^{\prime})|\hat{A}_{t}\in\mathcal{A}_{K,i}\big{)}$
$\displaystyle\geq
p_{K,i}^{t}\textup{I}_{t}(A^{\star}_{K};R(a_{K,i}^{t,1}),R(\hat{A}_{t}^{\prime})\big{)}+(1-p_{K,i}^{t})\textup{I}_{t}(A^{\star}_{K};R(a_{K,i}^{t,2}),R(\hat{A}_{t}^{\prime})\big{)}.$

For $a\in\mathcal{A}_{K,i}$, we define the random function $f_{t}^{K}(a)$ such
that it outputs $a_{K,i}^{t,1}\in\mathcal{A}_{K,i}$ with probability
$p_{K,i}^{t}$ and $a_{K,i}^{t,2}\in\mathcal{A}_{K,i}$ with probability
$1-p_{K,i}^{t}$. We observe that for $a\in\mathcal{A}_{K,i}$,
$\pi_{K}(a)=\pi_{k}(f_{t}^{K}(a))=a_{K,i}$ as both $a$ and $f_{t}^{K}(a)$
belong to $\mathcal{A}_{K,i}$. Then, the distance $\rho(a,f_{t}^{k}(a))$ is
bounded by $2^{-K}$. We repeat this procedure for all
$a_{K,i}\in\mathcal{A}_{K}$ and their corresponding $\mathcal{A}_{K,i}$ to
define $f_{t}^{K}(a)$ for all $a\in\mathcal{A}$ and it holds by that, for all
$a\in\mathcal{A}$, $\rho(f_{t}^{K}(a),a)\leq 2^{-K}$.
We can verify that

$\displaystyle\textup{I}_{t}\big{(}A^{\star}_{K};R(f_{t}^{K}(\hat{A}_{t,K})),R(f_{t}^{K-1}(\hat{A}_{t,K-1}))\big{)}$
$\displaystyle=\sum_{a_{K,i}\in\mathcal{A}_{K}}\sum_{j=1,2}\mathbb{P}_{t}[f_{t}^{K}(\hat{A}_{t,K}))=a_{K,i}^{t,j}|\hat{A}_{t}\in\mathcal{A}_{K,i}]\cdot\mathbb{P}_{t}[\hat{A}_{t}\in\mathcal{A}_{K,i}]\cdot\textup{I}_{t}\big{(}A^{\star}_{K};R(a_{K,i}^{t,j}),R(f_{t}^{K-1}(\hat{A}_{t,K-1}))\big{)}$
$\displaystyle=\sum_{a_{K,i}\in\mathcal{A}_{K}}\mathbb{P}_{t}[\hat{A}_{t}\in\mathcal{A}_{K,i}](p_{K,i}^{t}\cdot\textup{I}_{t}\big{(}A^{\star}_{K};R(a_{K,i}^{t,1}),R(f_{t}^{K-1}(\hat{A}_{t,K-1}))\big{)}$
$\displaystyle\qquad+(1-p_{K,i}^{t})\cdot\textup{I}_{t}\big{(}A^{\star}_{K};R(a_{K,i}^{t,2}),R(f_{t}^{K-1}(\hat{A}_{t,K-1}))\big{)}$
$\displaystyle\leq\sum_{a_{K,i}\in\mathcal{A}_{K}}\mathbb{P}_{t}[\hat{A}_{t}\in\mathcal{A}_{K,i}]\textup{I}_{t}\big{(}A^{\star}_{K};R(\hat{A}_{t}),R(f_{t}^{K-1}(\hat{A}_{t,K-1}))|\hat{A}_{t}\in\mathcal{A}_{K,i}\big{)}$
$\displaystyle=\textup{I}_{t}\big{(}A^{\star}_{K};R(\hat{A}_{t}),R(f_{t}^{K-1}(\hat{A}_{t,K-1}))\big{)}$

and similarly that

$\displaystyle\textup{I}_{t}\big{(}A^{\star}_{K+1};R(f_{t}^{K}(\hat{A}_{t,K})),R(\hat{A}_{t}^{\prime})\big{)}$
$\displaystyle=\sum_{a_{K,i}\in\mathcal{A}_{K}}\sum_{j=1,2}\mathbb{P}_{t}[f_{t}^{K}(\hat{A}_{t,K}))=a_{K,i}^{t,j}|\hat{A}_{t}\in\mathcal{A}_{K,i}]\cdot\mathbb{P}_{t}[\hat{A}_{t}\in\mathcal{A}_{K,i}]\cdot\textup{I}_{t}\big{(}A^{\star}_{K+1};R(a_{K,i}^{t,j}),R(\hat{A}_{t}^{\prime})\big{)}$
$\displaystyle=\sum_{a_{K,i}\in\mathcal{A}_{K}}\mathbb{P}_{t}[\hat{A}_{t}\in\mathcal{A}_{K,i}](p_{K,i}^{t}\cdot\textup{I}_{t}\big{(}A^{\star}_{K+1}R(a_{K,i}^{t,1}),R(\hat{A}_{t}^{\prime})\big{)}+(1-p_{K,i}^{t})\cdot\textup{I}_{t}\big{(}A^{\star}_{K+1};R(a_{K,i}^{t,2}),R(\hat{A}_{t}^{\prime})\big{)}$
$\displaystyle\leq\sum_{a_{K,i}\in\mathcal{A}_{K}}\mathbb{P}_{t}[\hat{A}_{t}\in\mathcal{A}_{K,i}]\textup{I}_{t}\big{(}A^{\star}_{K+1};R(\hat{A}_{t}),R(\hat{A}_{t}^{\prime})|\hat{A}_{t}\in\mathcal{A}_{K,i}\big{)}$
$\displaystyle=\textup{I}_{t}\big{(}A^{\star}_{K+1};R(\hat{A}_{t}),R(\hat{A}_{t}^{\prime})\big{)}$

where the inequalities follow from the construction of $f_{t}^{K}$. Thus
$f_{t}^{K}$ satisfies requirement (iii). As the result holds already for
$k=k_{0}$, by induction, we extend this result for all $k\geq k_{0}$.

We note that by construction, for each step $t\in\\{1,\ldots,T\\}$ and for
each $k\geq k_{0}$, we have that

$\displaystyle\rho(f_{t}^{k}(A^{\star}_{k}),A^{\star})\leq\rho(f_{t}^{k}(A^{\star}_{k}),A^{\star}_{k})+\rho(A^{\star}_{k},A^{\star})\leq
2\cdot 2^{-k},$ (4)
$\displaystyle\rho(f_{t}^{k}(\hat{A}_{t,k}),\hat{A}_{t})\leq\rho(f_{t}^{k}(\hat{A}_{t,k}),\hat{A}_{t,k})+\rho(\hat{A}_{t,k},\hat{A}_{t})\leq
2\cdot 2^{-k},$ (5)

where we use the triangle inequality together with the definition of
$f_{t}^{k}$ and of $A^{\star}_{k}$ and $\hat{A}_{t,k}$.

Lastly, we have to verify that at each period $t\in\\{1,\ldots,T\\}$, the
regret of the “ _approximate learning_ ” asymptotically converges to the
regret of Two Steps Thompson Sampling regret for finer approximations.

Using the fact that by construction of $f_{t}^{k}$, we have for all
$a\in\mathcal{A}_{k}$ that $\pi_{k}(f_{t}^{k}(a))=a$ and that by definition
$A^{\star}_{k}=\pi_{k}(A^{\star})$, we can write:

$\displaystyle\mathbb{E}_{t}[R(f_{t}^{k}(A^{\star}_{k}))-R(A^{\star})]$
$\displaystyle=\mathbb{E}_{t}[R(f_{t}^{k}(A^{\star}_{k}))-R(A^{\star}_{k})]+\mathbb{E}_{t}[R(A^{\star}_{k})-R(A^{\star})]$
$\displaystyle=\mathbb{E}_{t}[R(f_{t}^{k}(A^{\star}_{k}))-R(\pi_{k}(f_{t}^{k}(A^{\star}_{k})))]+\mathbb{E}_{t}[R(\pi_{k}(A^{\star}))-R(A^{\star})]$
$\displaystyle\leq
2\cdot\mathbb{E}_{t}[\sup_{a\in\mathcal{A}}R(\pi_{k}(a))-R(a)].$

Since the process is separable, by using the same argument as in the proof of
[12, Theorem 5.24], we have that

$\displaystyle\lim_{k\to\infty}\mathbb{E}_{t}[\sup_{a\in\mathcal{A}}R(\pi_{k}(a))-R(a)]=0,$

and therefore

$\displaystyle\lim_{k\to\infty}\mathbb{E}_{t}[R(f_{t}^{k}(A^{\star}_{k}))]=\mathbb{E}_{t}[R(A^{\star})].$

A similar analysis can be applied to
$\mathbb{E}_{t}[R(f_{t}^{k}(\hat{A}_{t,k}))-R(\hat{A}_{t})]$ and leads to

$\displaystyle\lim_{k\to\infty}\mathbb{E}_{t}[R(f_{t}^{k}(A^{\star}_{k}))-R(f_{t}^{k}(\hat{A}_{t,k}))]=\mathbb{E}_{t}[R(A^{\star})-R(\hat{A}_{t})].$

###  B.2 Proof of Proposition 2

We start the proof by recalling the definition of $\Gamma_{t,k}$ as

$\Gamma_{t,k}=\frac{\mathbb{E}_{t}\Big{[}\Big{(}R(f_{t}^{k}(A^{\star}_{k}))-R(f_{t}^{k}(\hat{A}_{t,k}))\Big{)}-\Big{(}R(f_{t}^{k-1}(A^{\star}_{k-1}))-R(f_{t}^{k-1}(\hat{A}_{t,k-1}))\Big{)}\Big{]}^{2}}{\textup{I}_{t}(f_{t}^{k}(A^{\star}_{k}),f_{t}^{k-1}(A^{\star}_{k-1});R(f_{t}^{k}(\hat{A}_{t,k})),R(f_{t}^{k-1}(\hat{A}_{t,k-1})))}$

where $A^{\star}_{k}$ and $\hat{A}_{t,k}$ are the
$k^{\textnormal{th}}$-quantizations respectively of the optimal action
$A^{\star}$ and the sampled action $\hat{A}_{t}$. We recall from the proof of
Proposition 1 that the definition of $f_{t}^{k}(A)$ implies that for all
$a_{k,m}\in\mathcal{A}_{k}$ there exist a pair of actions
$a_{k,m}^{t,1},a_{k,m}^{t,2}\in\mathcal{A}_{k,m}$ such that

$\displaystyle\mathbb{P}_{t}[f_{t}^{k}(A)=a_{k,m}^{t,1}|A\in\mathcal{A}_{k,m}]=p^{t}_{k,m},\quad\mathbb{P}_{t}[f_{t}^{k}(A)=a_{k,m}^{t,2}|A\in\mathcal{A}_{k,m}]=1-p^{t}_{k,m}.$

For the sake of brevity, we define the notation

$\displaystyle\mathbb{Q}_{t}[a_{k-1,m},a_{k,l},i,i^{\prime}]\coloneqq$
$\displaystyle\mathbb{P}_{t}[f_{t}^{k-1}(A^{\star}_{k-1})=a_{k-1,m}^{t,i}|A^{\star}_{k-1}\in\mathcal{A}_{k,m}]$
$\displaystyle\cdot\mathbb{P}_{t}[f_{t}^{k}(A^{\star}_{k})=a_{k,l}^{t,i^{\prime}}|A^{\star}_{k}\in\mathcal{A}_{k,l}]$
$\displaystyle\cdot\mathbb{P}_{t}[A^{\star}_{k}\in\mathcal{A}_{k,l},A^{\star}_{k-1}\in\mathcal{A}_{k-1,m}]$

and use the notation
$\\{(a_{k-1,\delta_{n}},a_{k,\gamma_{n}},i_{\mu_{n}},i_{\nu_{n}}^{\prime})\\}_{n=1}^{N_{k}}$
to represent the sequence of all quadruplets
$\\{a_{k-1},a_{k},i,i^{\prime}\\}$ such that
$a_{k-1}\in\mathcal{A}_{k-1},a_{k}\in\mathcal{A}_{k},i\in\\{1,2\\},i^{\prime}\in\\{1,2\\}\textnormal{
and }\pi_{k-1}(a_{k})=a_{k-1}$, where $N_{k}$ is the number of such
quadruplets.

We will first focus on

$\mathbb{E}_{t}\left[\big{(}R(f_{t}^{k}(A^{\star}_{k}))-R(f_{t}^{k-1}(A^{\star}_{k-1}))\big{)}-\big{(}R(f_{t}^{k}(\hat{A}_{t,k}))-R(f_{t}^{k-1}(\hat{A}_{t,k-1}))\big{)}\right]$

and note that we can relate it to the trace of a random matrix. Indeed, using
the previously introduced notations, we can write this expectation as

$\displaystyle\sum_{n=1}^{N_{k}}\mathbb{Q}_{t}[a_{k-1,\delta_{n}},a_{k,\gamma_{n}},i_{\mu_{n}},i_{\nu_{n}}^{\prime}]$
$\displaystyle\cdot\big{(}\mathbb{E}_{t}[R(a^{t,i_{\mu_{n}}}_{k,\gamma_{n}})-R(a^{t,i_{\nu_{n}}^{\prime}}_{k-1,\delta_{n}})|f_{t}^{k}(A^{\star}_{k})=a^{t,i_{\mu_{n}}}_{k,\gamma_{n}},f_{t}^{k-1}(A^{\star}_{k-1})=a^{t,i_{\nu_{n}}^{\prime}}_{k-1,\delta_{n}}]-\mathbb{E}_{t}[R(a^{t,i_{\mu_{n}}}_{k,\gamma_{n}})-R(a^{t,i_{\nu_{n}}^{\prime}}_{k-1,\delta_{n}})]\big{)}.$

Therefore, for any round $t\in\\{1,\ldots,T\\}$, conditioned on the history
$\hat{H}^{t}$, we can define a random matrix
$M^{k,t}\in\mathbb{R}^{N_{k}\times N_{k}}$ by specifying the entry
$M^{k,t}_{p,q}$ to be equal to

$\displaystyle\sqrt{\mathbb{Q}_{t}[a_{k-1,\delta_{p}},a_{k,\gamma_{p}},i_{\mu_{p}},i_{\nu_{p}}^{\prime}]}\sqrt{\mathbb{Q}_{t}[a_{k-1,\delta_{q}},a_{k,\gamma_{q}},i_{\mu_{q}},i_{\nu_{q}}^{\prime}]}$
$\displaystyle\big{(}\mathbb{E}_{t}[R(a^{t,i_{\mu_{q}}}_{k,\gamma_{q}})-R(a^{t,i_{\nu_{q}}^{\prime}}_{k-1,\delta_{q}})|f_{t}^{k}(A^{\star}_{k})=a^{t,i_{\mu_{p}}}_{k,\gamma_{p}},f_{t}^{k-1}(A^{\star}_{k-1})=a^{t,i_{\nu_{p}}^{\prime}}_{k-1,\delta_{p}}]-\mathbb{E}_{t}[R(a^{t,i_{\mu_{q}}}_{k,\gamma_{q}})-R(a^{t,i_{\nu_{q}}^{\prime}}_{k-1,\delta_{q}})]\big{)}$

for all $p,q=1,\ldots,N_{k}$. In this way, the trace of the matrix $M^{k,t}$
is equal to the desired expectation, namely

$\mathrm{Tr}(M^{k,t})=\mathbb{E}_{t}\left[(R(f_{t}^{k}(A^{\star}_{k}))-R(f_{t}^{k-1}(A^{\star}_{k-1})))-(R(f_{t}^{k}(\hat{A}_{t,k}))-R(f_{t}^{k-1}(\hat{A}_{t,k-1})))\right].$

Here, we can note that
$R(f_{t}^{k}(A^{\star}_{k}))-R(f_{t}^{k-1}(A^{\star}_{k-1}))$ is $(6\cdot
2^{-k})^{2}$-sub-Gaussian. Indeed, by construction, of
$f_{t}^{k}(A^{\star}_{k})$ and $f_{t}^{k-1}(A^{\star}_{k-1})$, we had showed
in (4) that $\rho(f_{t}^{k}(A^{\star}_{k}),A^{\star})\leq 2\cdot 2^{-k}$ and
$\rho(f_{t}^{k-1}(A^{\star}_{k-1}),A^{\star})\leq 2\cdot 2^{-(k-1)}$. Then, by
using the triangle inequality, we have that

$\displaystyle\rho(f_{t}^{k}(A^{\star}_{k}),f_{t}^{k-1}(A^{\star}_{k-1}))\leq\rho(f_{t}^{k}(A^{\star}_{k}),A^{\star})+\rho(A^{\star},f_{t}^{k-1}(A^{\star}_{k-1}))\leq
2\cdot 2^{-k}+2\cdot 2^{-(k-1)}=6\cdot 2^{-k}.$

Similarly, we can show that
$R(f_{t}^{k}(\hat{A}_{t,k}))-R(f_{t}^{k-1}(\hat{A}_{t,k-1}))$ is also $(6\cdot
2^{-k})^{2}$-sub-Gaussian.

In the same fashion as in [1, Proposition 5], we relate the mutual information

$\textup{I}_{t}(f_{t}^{k}(A^{\star}_{k}),f_{t}^{k-1}(A^{\star}_{k-1});R(f_{t}^{k}(\hat{A}_{t,k})),R(f_{t}^{k-1}(\hat{A}_{t,k-1})))$

to the squared Frobenius norm of $M^{k,t}$ as:

$\displaystyle\textup{I}_{t}(f_{t}^{k}(A^{\star}_{k}),f_{t}^{k-1}(A^{\star}_{k-1});R(f_{t}^{k}(\hat{A}_{t,k})),R(f_{t}^{k-1}(\hat{A}_{t,k-1})))$
$\displaystyle\geq\textup{I}_{t}(f_{t}^{k}(A^{\star}_{k}),f_{t}^{k-1}(A^{\star}_{k-1});R(f_{t}^{k}(\hat{A}_{t,k}))-R(f_{t}^{k-1}(\hat{A}_{t,k-1})))$
$\displaystyle=\sum_{p=1}^{N^{k}}\sum_{q=1}^{N^{k}}\mathbb{Q}_{t}[a_{k-1,\delta_{p}},a_{k,\gamma_{p}},i_{\mu_{p}},i_{\nu_{p}}^{\prime}]\mathbb{Q}_{t}[a_{k-1,\delta_{q}},a_{k,\gamma_{q}},i_{\mu_{q}},i_{\nu_{q}}^{\prime}]$
$\displaystyle\cdot\textup{D}_{\textnormal{KL}}(\mathbb{P}_{R(a^{t,i_{\mu_{q}}}_{k,\gamma_{q}})-R(a^{t,i_{\nu_{q}}^{\prime}}_{k-1,\delta_{q}})|\hat{H}^{t},f_{t}^{k}(A^{\star}_{k})=a^{t,i_{\mu_{p}}}_{k,\gamma_{p}},f_{t}^{k-1}(A^{\star}_{k-1})=a^{t,i_{\nu_{p}}^{\prime}}_{k-1,\delta_{p}}}||\mathbb{P}_{R(a^{t,i_{\mu_{q}}}_{k,\gamma_{q}})-R(a^{t,i_{\nu_{q}}^{\prime}}_{k-1,\delta_{q}})|\hat{H}^{t}})$
$\displaystyle\geq\sum_{p=1}^{N^{k}}\sum_{q=1}^{N^{k}}\mathbb{Q}_{t}[a_{k-1,\delta_{p}},a_{k,\gamma_{p}},i_{\mu_{p}},i_{\nu_{p}}^{\prime}]\mathbb{Q}_{t}[a_{k-1,\delta_{q}},a_{k,\gamma_{q}},i_{\mu_{q}},i_{\nu_{q}}^{\prime}]\cdot\frac{1}{2\cdot(6\cdot
2^{-k})^{2}}$
$\displaystyle\cdot\big{(}\mathbb{E}_{t}[R(a^{t,i_{\mu_{q}}}_{k,\gamma_{q}})-R(a^{t,i_{\nu_{q}}^{\prime}}_{k-1,\delta_{q}})|f_{t}^{k}(A^{\star}_{k})=a^{t,i_{\mu_{p}}}_{k,\gamma_{p}},f_{t}^{k-1}(A^{\star}_{k-1})=a^{t,i_{\nu_{p}}^{\prime}}_{k-1,\delta_{p}}]-\mathbb{E}_{t}[R(a^{t,i_{\mu_{q}}}_{k,\gamma_{q}})-R(a^{t,i_{\nu_{q}}^{\prime}}_{k-1,\delta_{q}})]\big{)}^{2}$
$\displaystyle=\frac{1}{2(6\cdot 2^{-k})^{2}}||M^{k,t}||^{2}_{F}$

where the last inequality is obtained again using the Donsker–Varadhan
inequality [13, Theorem 5.2.1] as in [1, Lemma 3].

Combining the last two equations and using the inequality
$\textnormal{trace}(M)\leq\sqrt{\textnormal{rank}(M)}||M||_{F}$ [1, Fact 10],
it comes that

$\displaystyle\Gamma_{t,k}\leq 2(6\cdot
2^{-k})^{2}\frac{\textnormal{Trace}(M^{k,t})^{2}}{||M^{k,t}||_{F}^{2}}\leq
2(6\cdot 2^{-k})^{2}\cdot\textnormal{rank}(M^{k,t})\textnormal{ a.s.}.$

We conclude the proof by showing that the rank of the matrix $M^{k,t}$ is
upper bounded by $d$.

For the sake of brevity, we define $\Theta_{t}\coloneqq\mathbb{E}_{t}[\Theta]$
and for $n=1,\ldots,N_{k}$, we define
$\mathbb{Q}_{n,t}=\mathbb{Q}_{t}[a_{k-1,\delta_{n}},a_{k,\gamma_{n}},i_{\mu_{n}},i_{\nu_{n}}^{\prime}]$
and
$\Theta_{n,t}=\mathbb{E}_{t}[\Theta|f_{t}^{k}(A^{\star}_{k})=a^{t,i_{\mu_{n}}}_{k,\gamma_{n}},f_{t}^{k-1}(A^{\star}_{k-1})=a^{t,i_{\nu_{n}}^{\prime}}_{k-1,\delta_{n}}]$.

We then have

$\displaystyle\mathbb{E}_{t}\left[R(a^{t,i_{\mu_{q}}}_{k,\gamma_{q}})-R(a^{t,i_{\nu_{q}}^{\prime}}_{k-1,\delta_{q}})\right]=\mathbb{E}_{t}\left[\langle
a^{t,i_{\mu_{q}}}_{k,\gamma_{q}},\Theta\rangle-\langle
a^{t,i_{\nu_{q}}^{\prime}}_{k-1,\delta_{q}},\Theta\rangle\right]=\langle
a^{t,i_{\mu_{q}}}_{k,\gamma_{q}}-a^{t,i_{\nu_{q}}^{\prime}}_{k-1,\delta_{q}},\Theta_{t}\rangle$

and

$\displaystyle\mathbb{E}_{t}\left[R(a^{t,i_{\mu_{q}}}_{k,\gamma_{q}})-R(a^{t,i_{\nu_{q}}^{\prime}}_{k-1,\delta_{q}})|f_{t}^{k}(A^{\star}_{k})=a^{t,i_{\mu_{p}}}_{k,\gamma_{p}},f_{t}^{k-1}(A^{\star}_{k-1})=a^{t,i_{\nu_{p}}^{\prime}}_{k-1,\delta_{p}}\right]$
$\displaystyle=\mathbb{E}_{t}\left[\langle
a^{t,i_{\mu_{q}}}_{k,\gamma_{q}},\Theta\rangle-\langle
a^{t,i_{\nu_{q}}^{\prime}}_{k-1,\delta_{q}},\Theta\rangle|f_{t}^{k}(A^{\star}_{k})=a^{t,i_{\mu_{p}}}_{k,\gamma_{p}},f_{t}^{k-1}(A^{\star}_{k-1})=a^{t,i_{\nu_{p}}^{\prime}}_{k-1,\delta_{p}}\right]$
$\displaystyle=\langle
a^{t,i_{\mu_{q}}}_{k,\gamma_{q}}-a^{t,i_{\nu_{q}}^{\prime}}_{k-1,\delta_{q}},\Theta_{p,t}\rangle$

Since the inner product is linear, we can rewrite each entry $M^{k,t}_{p,q}$
of the matrix $M^{k,t}$ as

$\displaystyle\sqrt{\mathbb{Q}_{p,t}\mathbb{Q}_{q,t}}\langle
a^{t,i_{\mu_{q}}}_{k,\gamma_{q}}-a^{t,i_{\nu_{q}}^{\prime}}_{k-1,\delta_{q}},\Theta_{p,t}-\Theta_{t}\rangle.$

Equivalently, the matrix $M^{k,t}$ can be written as

$\displaystyle\begin{bmatrix}\sqrt{\mathbb{Q}_{1,t}}(\Theta_{1,t}-\Theta_{t})\\\
\vdots\\\
\sqrt{\mathbb{Q}_{N_{k},t}}(\Theta_{N_{k},t}-\Theta_{t})\end{bmatrix}\begin{bmatrix}\sqrt{\mathbb{Q}_{1,t}}\big{(}a^{t,i_{\mu_{1}}}_{k,\gamma_{1}}-a^{t,i_{\nu_{1}}^{\prime}}_{k-1,\delta_{1}}\big{)}&\cdots&\sqrt{\mathbb{Q}_{N_{k},t}}\big{(}a^{t,i_{\mu_{N_{k}}}}_{k,\gamma_{N_{k}}}-a^{t,i_{\nu_{N_{k}}}^{\prime}}_{k-1,\delta_{N_{k}}}\big{)}\end{bmatrix}.$

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

For completeness, we can write that the chain-link information ratio is upper
bounded by $\Gamma_{t,k}\leq 2\cdot\rho_{k}^{2}\cdot d$ where $\rho_{k}$ is an
upper bound on $\rho(f_{t}^{k}(A^{\star}_{k}),f_{t}^{k-1}(A^{\star}_{k-1}))$.
This remark will be of use in the proof of Proposition 3.

###  B.3 Proof of Corollary 1

Bounding the entropy of $A^{\star}_{k}$ by the cardinality of set
$\mathcal{A}_{k}$, we have that

$\displaystyle\sum_{k=k_{0}+1}^{\infty}2^{-k}\sqrt{\textup{H}(A^{\star}_{k})}\leq\sum_{k=k_{0}+1}^{\infty}2^{-k}\sqrt{\log(|\mathcal{N}(\mathcal{A},\rho,2^{-k})|)}.$

By definition of the $\varepsilon$-net,
$|\mathcal{N}(\mathcal{A},\rho,\varepsilon)|$ is decreasing in $\varepsilon$.
It then comes that

$\displaystyle\sum_{k=k_{0}+1}^{\infty}2^{-k}\sqrt{\log(|\mathcal{N}(\mathcal{A},\rho,2^{-k})|)}$
$\displaystyle=2\sum_{k=k_{0}+1}^{\infty}\int_{2^{-k}}^{2^{-k-1}}\sqrt{\log(|\mathcal{N}(\mathcal{A},\rho,2^{-k})|)}\,d\varepsilon$
$\displaystyle\leq
2\sum_{k=k_{0}+1}^{\infty}\int_{2^{-k}}^{2^{-k-1}}\sqrt{\log(|\mathcal{N}(\mathcal{A},\rho,\varepsilon)|)}\,d\varepsilon$
$\displaystyle=2\int_{0}^{\mathrm{diam}(\mathcal{A})}\sqrt{\log(|\mathcal{N}(\mathcal{A},\rho,\varepsilon)|)}\,d\varepsilon.$
$\displaystyle=2\int_{0}^{\infty}\sqrt{\log(|\mathcal{N}(\mathcal{A},\rho,\varepsilon)|)}\,d\varepsilon,$

where the last equality comes from the fact that
$\mathcal{N}(\mathcal{A},\rho,\varepsilon)$ is a singleton for every
$\varepsilon>\mathrm{diam}(\mathcal{A})$.

Using this fact together with Theorem 1 yields the desired result.

###  B.4 Proof of Proposition 3

In the end of proof of Proposition 2, we have showed that the chain-link
information ratio was in general bounded by $\Gamma_{t,k}\leq
2\cdot\rho_{k}^{2}\cdot d$ where $\rho_{k}$ is an upper bound on
$\rho(f_{t}^{k}(A^{\star}_{k}),f_{t}^{k-1}(A^{\star}_{k-1}))$ and proved that
by definition of the quantizations $A^{\star}_{k}$ and the sampling functions
$f_{t}^{k}$, it holds that

$\rho(f_{t}^{k}(A^{\star}_{k}),f_{t}^{k-1}(A^{\star}_{k-1}))\leq 2\cdot
2^{-k}+2\cdot 2^{-(k-1)}.$

We can reflect that the choice of using $2^{-k}$-nets to define our sequence
of quantizations $\\{A^{\star}_{k}\\}_{k=k_{0}+1}^{\infty}$ was arbitrary. In
general, we could have considered a $\alpha^{-k}$-net for some $\alpha>1$.
Adapting the bound on $\rho_{k}$ and to that reflection, leads to the
following bound:

$\rho(f_{t}^{k}(A^{\star}_{k}),f_{t}^{k-1}(A^{\star}_{k-1}))\leq
2\cdot\alpha^{-k}+2\cdot\alpha^{-(k-1)}.$

Combining this result with Theorem 1, we get that

$\displaystyle\textnormal{REG}^{\textnormal{2-TS}}_{T}$ $\displaystyle\leq
2\sum_{k=k_{0}+1}^{\infty}\sqrt{2\cdot\rho_{k}^{2}\cdot d\cdot
T\cdot\log(|\mathcal{N}(\mathcal{A},\rho,\alpha^{-k})|)},$

where we upper bounded the entropy of $A^{\star}_{k}$ by the logarithm of the
cardinality of the set $\mathcal{A}_{k}$.

Applying Lemma 2 to upper bound the cardinality of the smallest
$\alpha^{-k}$-net $\mathcal{N}(\mathcal{A},\rho,\alpha^{-k})$ and rearanging
the terms, we get the following bound:

$\displaystyle\textnormal{REG}^{\textnormal{2-TS}}_{T}$ $\displaystyle\leq
2\cdot
d\cdot\sqrt{T}\sum_{k=k_{0}+1}^{\infty}\sqrt{2\cdot\rho_{k}^{2}\cdot\log(2\cdot\alpha^{k}+1)}.$

Now, we note that for linear bandit problems, we can define the first
quantization set $\mathcal{A}_{k_{0}}$ to be the center of the ball, that is
$\mathcal{A}_{k_{0}}=\\{0_{d}\\}$ where $0_{d}$ is the $d$-dimensional zero
and chose $f_{t}^{k_{0}}(0_{d})=0_{d}$. It is easy to verify that this choice
satisfies Proposition 1 (i) as $A^{\star}_{k_{0}}=\hat{A}_{t,k_{0}}=0_{d}$ and
$f_{t}^{k_{0}}(A^{\star}_{k_{0}})=f_{t}^{k_{0}}(\hat{A}_{t,k_{0}})=0_{d}$, as
well as fulfills 3 as $R(f_{t}^{k_{0}}(\hat{A}_{t,k_{0}}))=R(0_{d})$ does not
depend on the $\Theta$ and therefore is independent of $A^{\star}$ and
$A^{\star}_{k_{0}+1}$.

Observing that in the unit ball, by definition the radius is $1$, we first
note that $\mathcal{A}_{k_{0}}$ is a $(\alpha^{0})$-net for $\mathcal{A}$,
implying $k_{0}=0$ and secondly that
$\rho(f_{t}^{k_{0}+1}(A^{\star}_{k_{0}+1}),f_{t}^{k_{0}}(A^{\star}_{k_{0}}))=\rho(f_{t}^{k_{0}+1}(A^{\star}_{k_{0}+1}),0_{d})\leq
1$ and therefore we can use $\rho_{k_{0}+1}=1$ which is a better upper bound
than $2\cdot\alpha^{-(k_{0}+1)}+2\cdot\alpha^{-k_{0}}=2\cdot(1+\alpha^{-1})$.

Applying those results, we obtain the following bound:

$\displaystyle\textnormal{REG}^{\textnormal{2-TS}}_{T}$ $\displaystyle\leq
d\sqrt{T}\cdot
2\cdot\bigg{(}\sqrt{2\cdot\log(2\alpha+1)}+\sum_{k=2}^{\infty}(2\cdot\alpha^{-k}+2\cdot\alpha^{-(k-1)})\sqrt{2\cdot\log(2\alpha^{k}+1)}\bigg{)}.$

For instance, choosing $\alpha=20$, we have that

$2\cdot\bigg{(}\sqrt{2\cdot\log(2\alpha+1)}+\sum_{k=2}^{\infty}(2\cdot\alpha^{-k}+2\cdot\alpha^{-(k-1)})\sqrt{2\cdot\log(2\alpha^{k}+1)}\bigg{)}\approx
6.27.$

Finally, rounding up this value leads to claimed result.