# Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement
Learning

Ahmadreza Moradipari &Mohammad Pedramfar∗ &Modjtaba Shokrian Zini∗ &Vaneet
Aggarwal Authors have equal contribution.Toyota Motor North America, InfoTech
Labs, Mountain View, CA, USA<EMAIL_ADDRESS>University, West Lafayette, IN, USA,
mpedramf<EMAIL_ADDRESS>University, West
Lafayette, IN, USA<EMAIL_ADDRESS>
###### Abstract

In this paper, we prove the first Bayesian regret bounds for Thompson Sampling
in reinforcement learning in a multitude of settings. We simplify the learning
problem using a discrete set of surrogate environments, and present a refined
analysis of the information ratio using posterior consistency. This leads to
an upper bound of order $\widetilde{O}(H\sqrt{d_{l_{1}}T})$ in the time
inhomogeneous reinforcement learning problem where $H$ is the episode length
and $d_{l_{1}}$ is the Kolmogorov $l_{1}-$dimension of the space of
environments. We then find concrete bounds of $d_{l_{1}}$ in a variety of
settings, such as tabular, linear and finite mixtures, and discuss how how our
results are either the first of their kind or improve the state-of-the-art.

00footnotetext:  This work was supported in part by the National Science
Foundation under grant CCF-2149588 and Cisco, Inc.

##  1 Introduction

Reinforcement Learning (RL) is a sequential decision-making problem in which
an agent interacts with an unknown environment typically modeled as a Markov
Decision Process (MDP) Sutton and Barto, (2018); Bertsekas and Tsitsiklis,
(1996). The goal of the agent is to maximize its expected cumulative reward.
This problem has a variety of applications, including robotics, game playing,
resource management, and medical treatments. The key challenge in RL is to
balance the so-called exploration-exploitation trade-off efficiently:
exploring unseen state-action pairs to gain more knowledge about the unknown
environment or exploiting the current knowledge to maximize the expected
cumulative reward. Two efficient approaches have been developed to control
this trade-off: optimism in the face of uncertainty (OFU) and Thompson
Sampling (TS) (or Posterior Sampling (PS)). OFU constructs a confidence set of
statistically plausible MDPs that includes the true MDP with high probability
and plays an optimistic policy according to the MDP with maximum gain from
this set Auer et al., (2008); Tossou et al., (2019). TS samples a
statistically plausible MDP from a posterior distribution and plays the
optimistic policy of the sampled MDP Osband et al., (2013); Osband and Van
Roy, (2017). In this work, we focus on the latter, and by combining an
information theoretical approach first introduced by Russo and Van Roy, (2016)
with analysis based on posterior consistency tools, we prove state-of-the-art
Bayesian regret bounds in a variety of settings.

In this paper, we start by defining the Bayesian RL problem, where transition
and reward functions are Bayesian and time inhomogeneous. The Bayesian RL
problem we consider is more comprehensive than in previous works, as we allow
for both Bayesian transition and Bayesian rewards, and do not make any
assumption on their individual prior. To simplify the learning problem, we
utilize the notion of surrogate environments, which is a discretization of the
environments space, and its learning task and TS regret is a proxy to that of
the main problem. The construction of the surrogate environments was first
introduced by Hao and Lattimore, (2022) with an incorrect proof, which is
fixed in our work by defining the surrogate environments through an
optimization. Of main importance is the size of this new environment space.
The Bayesian regret decomposes to the product of two terms, one being the
cumulative mutual information of the environment and history traversed by the
policy. By the well-known entropy estimation of the mutual information, this
significant factor in the regret is connected to the $l_{1}-$dimensions
($d_{l_{1}}$) of the transition and reward functions space, which can be more
succinctly interpreted as the $l_{1}-$dimension $d_{l_{1}}$ of the environment
space. The latter is in turn estimated by the size of the space of surrogate
environments.

The information ratio, representing a trade-off of exploration/exploitation,
is the other significant term in the decomposition of the TS Bayesian regret.
In an improvement to Hao and Lattimore, (2022), our novel analysis of this
ratio based on posterior consistency tools, shows that this trade-off is
bounded by $H^{3/2}$, where $H$ is the episode length. This bound is general
and independent of the dimension of transition/reward function space at each
step, which is is a key factor behind the advantage of our regret bound, such
as the $\sqrt{SA}$ advantage in the tabular case compared to Hao and
Lattimore, (2022), or the lack of any restriction on the prior (e.g.,
Dirichlet prior) compared to Osband and Van Roy, (2017). Following a further
refined approach, we finally estimate the TS Bayesian regret to be
$\widetilde{O}(\lambda\sqrt{d_{l_{1}}T})$ for large enough $T$ in the time
inhomogeneous setting. Here, a new term ‘value diameter’ $\lambda$, which is
the average difference of the optimal value functions at different states, is
used in bounding the information ratio, where instead of $H^{3/2}$, we have
the smaller term $\lambda H^{1/2}$. Bounding the information ratio with
$\lambda$ is a conceptual contribution of our work, which shows that the ratio
is bounded by a value-dependent term, which is in nature different from $H$
but always $\leq H+1$. Further, there exists another bound for $\lambda$; in
environments where states are reachable from one another in $D$ steps, we have
$\lambda\leq D+1$. In ‘well-connected’ MDPs, one could have $D\ll H$, implying
an improvement over the $H^{3/2}$ information ratio bound.

Our generic bound is abstract in terms of $d_{l_{1}}$, so we estimate it in
more explicit terms for useful applications. Hao and Lattimore, (2022) have
bounded $d_{l_{1}}$ in the tabular and linear case without formalizing this
notion, and while for tabular MDPs, $d_{l_{1}}$ was bounded by $SAH$, for
linear MDPs with feature space dimension $d_{f}$, we investigate their claim
of the bound $d_{f}H$. Detailed in Appendix F, we show a counterexample to
their analysis, and we manage to find a correct estimate in this setting. We
also introduce finite mixtures MDPs and are the first to prove a TS Bayesian
regret of order $\widetilde{O}(\lambda\sqrt{HmT})$, where $m$ is the number of
mixtures.

Lastly, we note that our regret bound of order
$\widetilde{O}(\lambda\sqrt{d_{l_{1}}T})$ is the first in the general
nonlinear time inhomogeneous Bayesian RL setting for TS, and generalizing
(Osband and Van Roy,, 2017, Conj. 1), we conjecture it to be optimal if
$\lambda$ can be replaced by $\widetilde{O}(\sqrt{H})$.

#### Related work.

Since the introduction of information ratio by Russo and Van Roy, (2014,
2016), a new line of research has emerged to provide tighter regret bounds for
TS. The general approach involves factoring the Bayesian regret into two
components: an information ratio that captures the trade-off between optimal
action selection and information gain, and a cumulative information gain term
that depends on the target environment and the history of previous
observations. Then, both components are bounded separately using information
theoretic tools.

In the bandit setting, this analysis has been used to bound Bayesian regret
for TS Dong and Van Roy, (2018); Bubeck and Sellke, (2020), as well as that of
a new algorithm called information-directed sampling (IDS) Russo and Van Roy,
(2014); Liu et al., (2018); Kirschner et al., (2021); Hao et al., (2021,
2022). This analysis has also been used in partial monitoring Lattimore and
Szepesvári, (2019); Lattimore and Gyorgy, (2021) and RL with a specific
Dirichlet prior and additional assumptions Lu and Van Roy, (2019); Lu, (2020).
More recently, Hao and Lattimore, (2022) studied the Bayesian regret of TS in
RL without any prior assumptions for tabular MDP. This is the closest work to
our paper and we discuss our generalization in detail in Section 5.

It is worth noting that there is another line of work that incorporates
confidence regions into TS to achieve Bayesian regret bounds that can match
the best possible frequentist regret bounds by UCB in both bandit settings
Russo and Van Roy, (2014) and RL Osband et al., (2013); Osband and Van Roy,
(2014); Osband et al., (2019). However, this technique results in a sub-
optimal Bayesian regret, as the best bound known for UCB itself is not
optimal. The Bayesian tabular MDP case has also been studied with the
additional Dirichlet prior assumption in Osband and Van Roy, (2017), where
they achieve a regret bound matching ours. In an independent approach, the
first non-linear Bayesian RL model was considered by Fan and Ming, (2021) with
a regret bound of $dH^{3/2}T^{1/2}$ where $d$ is a notion of dimension of
their model, but their results were limited to Gaussian process settings with
linear kernels. Finally, Chakraborty et al., (2022) considered general non-
linear Bayesian RL models and introduced an algorithm that obtains
$dH^{1+\alpha/2}T^{1-\alpha/2}$ where $\alpha$ is a tuning parameter and $d$
is the dimension of ${\mathcal{S}}\times\mathcal{A}\times{\mathcal{S}}$.

For the frequentist setting, various algorithms with provable regret
guarantees have been proposed for model-free tabular MDPs. These include UCBVI
Azar et al., (2017), optimistic Q-learning Jin et al., (2018), RLSVI Russo,
(2019); Zanette et al., (2020), and UCB-Advantage Zhang et al., (2020). These
algorithms were further generalized to linear or linear mixture MDPs, such as
LSVI-UCB Jin et al., (2020), OPPO Cai et al., (2020), and UCRL-VTR Ayoub et
al., (2020); Zhou et al., (2021). Slightly more related to our work, model-
based frequentist bounds have also been shown for a variant of posterior
sampling (PS) in the tabular setting Agrawal and Jia, (2017). For the specific
variant of optimistic PSRL, the optimal bound in the tabular setting with a
Dirichlet prior was shown in Tiapkin et al., (2022). To our knowledge, a
frequentist bound for PS is still an open problem for general RLs. Minimax
regret bounds have also been studied for variants of TS, as in Dann et al.,
(2021). Most recently, Agarwal et al., (2022) presented VO$Q$L, an algorithm
that achieves the optimal bound of $\widetilde{O}(d\sqrt{HT})$ in the general
model-free nonlinear setting, where $d$ represents the generalized Eluder
dimension of the value function space. Note that the notion of dimension used
in our regret bounds is different, and unrelated, to the Eluder dimension used
in model-free estimations. For frequentist model-based, the optimal bound was
achieved in the tabular setting by Azar et al., (2017). As another research
direction, Duan et al., (2021) utilized kernel-Hilbert spaces to estimate the
value of infinite horizon Markov reward process (MRP) for RL problem, and
Abedsoltan et al., (2023) pave the way for scalability challenges in kernel
models.

While our work’s emphasis is on theoretical guarantees for TS, we discuss here
the experiments using this algorithm. Previous works on PSRL Russo and Van
Roy, (2014); Liu et al., (2018); Kirschner et al., (2021); Hao et al., (2022);
Osband and Van Roy, (2017) come with extensive experiments on TS (and/or its
variants), and discussions on computational efficiency of PSRL. In particular,
experiments in Osband and Van Roy, (2017) support the assertion that “PSRL
dramatically outperforms existing algorithms based on OFU”. In addition, PSRL
with oracle access has been shown to be the most performant, esp. when
compared to recent OFU based UCBVI/UCBVI-B, or even variants of PSRL such as
Optimistic PSRL (Tiapkin et al.,, 2022, Fig. 1.3). However, an important
limitation in experiments is the need for oracle access to an optimal policy,
and that can not be always satisfied efficiently. Nevertheless, clever
engineering can make TS work even in large scale Deep RL. Indeed, for general
RL settings, the recent work Sasso et al., (2023) shows how to implement TS in
Deep RL on the Atari benchmark and concludes that “Posterior Sampling Deep RL
(PSDRL) significantly outperforms previous state-of-the-art randomized value
function approaches, its natural model-free counterparts, while being
competitive with a state-of-the-art (model-based) reinforcement learning
method in both sample efficiency and computational efficiency”. In summary,
experiments in the literature provide enough support for the empirical
performance of TS.

##  2 Preliminaries

###  2.1 Finite-horizon MDP

We follow the literature’s conventions in our notation and terminology to
avoid confusion when comparing results. The environment is a tuple
$\mathcal{E}=({\mathcal{S}},\mu_{\mathcal{S}},\mathcal{A},\mu_{\mathcal{A}},H,\\{P_{h}\\}_{h=1}^{H},\\{r_{h}\\}_{h=1}^{H})$,
where ${\mathcal{S}}$ is the topological measurable state space, $\mathcal{A}$
is the topological measurable action space, $\mu_{\mathcal{S}}$ and
$\mu_{\mathcal{A}}$ are base probability measures on ${\mathcal{S}}$ and
$\mathcal{A}$ respectively, $H$ is the episode length,
$P_{h}:{\mathcal{S}}\times\mathcal{A}\to\Delta_{{\mathcal{S}},\mu_{\mathcal{S}}}$
is the transition probability kernel, and
$r_{h}:{\mathcal{S}}\times\mathcal{A}\to\Delta_{[0,1],\operatorname{Lebesgue}}$
is the reward function, where we fix the convention
$r(s,a):=\mathbb{E}_{x}[r(x|s,a)]=\int_{0}^{1}xr(x|s,a)\operatorname{d}\\!x$
as we mostly deal with its mean value. Notice that $\Delta_{X,\mu}$ is the set
of probability distributions over $X$ that are absolutely continuous with
respect to $\mu$. We will use $\Delta_{X}$ when the base measure is clear from
the context. We assume ${\mathcal{S}}$, $\mathcal{A}$ are known and
deterministic while the transition probability kernel and reward are unknown
and random. Throughout the paper, the implicit dependence of $P_{h}$ and
$r_{h}$ on $\mathcal{E}$ should be clear from the context.

Let $\Theta_{h}^{P}$ be the topological function space of $P_{h}$ and
$\Theta^{P}=\Theta_{1}^{P}\times\cdots\times\Theta_{H}^{P}$ be the full
function space. The space $\Theta_{h}^{P}$ is assumed to be separable and
equipped with prior probability measure $\rho_{h}^{P}$ yielding the product
prior probability measure
$\rho^{P}=\rho_{1}^{P}\otimes\cdots\otimes\rho_{H}^{P}$ for $\Theta^{P}$. The
exact same definition with similar notations
$\Theta_{h}^{R},\rho_{h}^{R},\rho^{R},\Theta^{R}$ applies for the reward
function. Notice the explicit assumption of time inhomogeneity in these
definitions, with all ‘layers’ $h$ being independent. The two sets define the
set of all environments parametrized by
$\Theta=\Theta_{1}\times\cdots\times\Theta_{H}$ where
$\Theta_{h}=\Theta_{h}^{P}\times\Theta_{h}^{R}$. Note that the prior is
assumed to be known to the learner. This setting implies that an environment
$\mathcal{E}$ sampled according to the prior $\rho=\rho^{P}\otimes\rho^{R}$ is
essentially determined by its transition and reward functions pair
$\\{(P_{h},r_{h})\\}_{h=1}^{H}$. We simplify the notation to view $\Theta$ as
the set of all environments, i.e., saying $\mathcal{E}\in\Theta$ should be
viewed as $\\{(P_{h},r_{h})\\}_{h=1}^{H}\in\Theta$. The space of all possible
real-valued functions $\\{(P_{h},r_{h})\\}_{h=1}^{H}$ has a natural vector
space structure. Therefore it is meaningful to discuss the notion of the
convex combination of environments. We assume that $\Theta$ is a convex
subspace of the space of all possible environments. This assumption is not
restrictive, since we may replace any environment space with its convex hull.
Note that we do not assume that the support of the prior is convex.

######  Remark 1.

The case of joint prior may be of interest, but to our knowledge all prior
works also take $\rho^{P},\rho^{R}$ to be independent.

#### Agent, policy and history.

An agent starts at an initial state $s_{1}^{\ell}$, which is fixed for all
episodes $\ell$. It observes a state $s_{h}^{\ell}$ at layer $h$ episode
$\ell$, takes action $a_{h}^{\ell}$, and receives reward $r_{h}^{\ell}$. The
environment changes to the next random state $s_{h+1}^{\ell}$ with probability
$P_{h}(s_{h+1}^{\ell}|s_{h}^{\ell},a_{h}^{\ell})$. The agent stops acting at
$s_{H+1}$ and the environment is reset to its initial state.

We define $\mathcal{H}_{\ell,h}$ as the history
$(s_{1}^{\ell},a_{1}^{\ell},r_{1}^{\ell},\ldots,s_{h}^{\ell},a_{h}^{\ell},r_{h}^{\ell})$.
Denote by
$\mathcal{D}_{\ell}=(\mathcal{H}_{1,H},\ldots,\mathcal{H}_{\ell-1,H})$ the
history up to episode $\ell$, where $\mathcal{D}_{1}:=\emptyset$. Finally, let
$\Omega_{h}=\prod_{i=1}^{h}({\mathcal{S}}\times\mathcal{A}\times[0,1])\,$ be
the set of all possible histories up to layer $h$.

A policy $\pi$ is represented by stochastic maps $(\pi_{1},\ldots,\pi_{H})$
where each
$\pi_{h}:\Omega_{h-1}\times{\mathcal{S}}\to\Delta_{\mathcal{A},\mu_{\mathcal{A}}}$.
Let $\Pi_{S}$ denote the entire stationary policy class, stationary meaning a
dependence only on the current state and layer and let $\Pi\subseteq\Pi_{S}$.

#### Value and state occupancy functions.

Define the value function $V^{\mathcal{E}}_{h,\pi}$ as the value of the policy
$\pi$ interacting with $\mathcal{E}$ at layer $h$:

$\displaystyle
V^{\mathcal{E}}_{h,\pi}(s):=\mathbb{E}_{\pi}^{\mathcal{E}}\left[\sum_{h^{\prime}=h}^{H}r_{h^{\prime}}(s_{h^{\prime}},a_{h^{\prime}})\bigg{|}s_{h}=s\right]\,,$
(1)

where $\mathbb{E}_{\pi}^{\mathcal{E}}$ denotes the expectation over the
trajectory under policy, transition, and reward functions $\pi,P_{h},r_{h}$.
The value function at step $H+1$ is set to null,
$V_{H+1,\pi}^{\mathcal{E}}(\cdot):=0$. We assume there is a measurable
function $\pi^{*}_{\mathcal{E}}:\Theta\to\Pi$ such that
$V^{\mathcal{E}}_{h,\pi^{*}_{\mathcal{E}}}(s)=\max_{\pi\in\Pi}V_{h,\pi}^{\mathcal{E}}(s),\
\forall s\in{\mathcal{S}},h\in[H]$. The optimal policy $\pi^{*}$ is a function
of $\mathcal{E}$, making it a random variable in the Bayesian setting. Lastly,
let the _state-action occupancy probability measure_ be
$\mathbb{P}^{\mathcal{E}}_{\pi}(s_{h}=s,a_{h}=a)$, also known as the state
occupancy measure under policy $\pi$ and environment $\mathcal{E}$. It follows
from the definitions that this measure is absolutely continuous with respect
to
$\mu_{{\mathcal{S}}\times\mathcal{A}}:=\mu_{\mathcal{S}}\times\mu_{\mathcal{A}}$.
Let $d_{h,\pi}^{\mathcal{E}}(s,a)$ denote the Radon–Nikodym derivative so that
we have
$d_{h,\pi}^{\mathcal{E}}(s,a)\operatorname{d}\\!\mu_{{\mathcal{S}}\times\mathcal{A}}=\operatorname{d}\\!\mathbb{P}^{\mathcal{E}}_{\pi}(s_{h}=s,a_{h}=a)$.
We will assume throughout the paper that this density
$d_{h,\pi}^{\mathcal{E}}(s,a)$ is measurable and upper bounded for all
$\pi,\mathcal{E},s,a,h$. The upper bound is a reasonable assumption, and it
happens trivially in the tabular case ($d_{h,\pi}^{\mathcal{E}}(s,a)\leq SA$).
This also happens, e.g., when one assumes that the maps
$(\mathcal{E},s,a,s^{\prime},h)\mapsto P^{\mathcal{E}}_{h}(s^{\prime}|s,a)$
and $(\pi,s,a,h)\mapsto\pi_{h}(a|s)$ are continuous and $\Theta$,
${\mathcal{S}}$, $\mathcal{A}$ and the set of all optimal policies (as a
subset of $\Pi$) are compact.

###  2.2 Bayesian regret

We formulate the expected regret over $L$ episodes and $T=LH$ total steps in
an environment $\mathcal{E}$ as

$\displaystyle\mathfrak{R}_{L}(\mathcal{E},\pi)=\mathbb{E}\left[\sum_{\ell=1}^{L}\left(V_{1,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}}(s_{1}^{\ell})-V_{1,\pi^{\ell}}^{\mathcal{E}}(s_{1}^{\ell})\right)\right]\,,$
(2)

where the expectation is over the randomness of $\pi=\\{\pi^{\ell}\\}_{\ell}$.
The Bayesian regret is
$\mathfrak{BR}_{L}(\pi)=\mathbb{E}[\mathfrak{R}_{L}(\mathcal{E},\pi)]$. For
Thompson Sampling (TS), the algorithm selects the optimal policy of a given
sample $\mathcal{E}_{\ell}$ picked from the posterior
$\mathcal{E}_{\ell}\sim\mathbb{P}(\mathcal{E}\in\cdot|\mathcal{D}_{\ell})$:

$\displaystyle\pi_{\text{TS}}^{\ell}=\text{argmax}_{\pi\in\Pi}V_{1,\pi}^{\mathcal{E}_{\ell}}(s_{1}^{\ell})\,.$
(3)

Importantly, the law of TS aligns with the posterior, i.e.,
$\mathbb{P}(\mathcal{E}|\mathcal{D}_{\ell})=\mathbb{P}(\pi^{\ell}_{\text{TS}}=\pi^{*}_{\mathcal{E}}|\mathcal{D}_{\ell})$.

######  Remark 2.

Note that
$\mathbb{P}(\pi^{\ell}_{\text{TS}}=\pi^{*}_{\mathcal{E}}|\mathcal{D}_{\ell})$
is a probability for a specific measure on the space of optimal policies. To
ensure that
$\int_{\Pi^{*}}\mathbb{P}(\pi^{*}|\mathcal{D}_{\ell})\text{d}\rho_{\Pi^{*}}=1$,
we need an appropriate measure $\rho_{\Pi^{*}}$ on $\Pi^{*}$. Given the law of
TS, the natural choice for this measure is the push-forward of the prior
measure $\rho$ under the map $star:\Theta\to\Pi^{*}$, where
$star(\mathcal{E})=\pi^{*}_{\mathcal{E}}$.

###  2.3 Notations

For Bayesian RL, conditional expressions involving a given history
$\mathcal{D}_{\ell}$ are widely used. We adopt the notation in Hao and
Lattimore, (2022) to refer to such conditionals; let
$\mathbb{P}_{\ell}(\cdot):=\mathbb{P}(\cdot|\mathcal{D}_{\ell})$,
$\mathbb{E}_{\ell}[\cdot]:=\mathbb{E}[\cdot|\mathcal{D}_{\ell}]$. We can
rewrite the Bayesian regret as

$\displaystyle\mathfrak{BR}_{L}(\pi)=\sum_{\ell=1}^{L}\mathbb{E}\left[\mathbb{E}_{\ell}\left[V_{1,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}}(s_{1}^{\ell})-V_{1,\pi}^{\mathcal{E}}(s_{1}^{\ell})\right]\right]$
(4)

and define the conditional mutual information
$\mathbb{I}_{\ell}(X;Y):=D_{\mathrm{KL}}(\mathbb{P}((X,Y)\in\cdot|\mathcal{D}_{\ell})||\mathbb{P}(X\in\cdot|\mathcal{D}_{\ell})\otimes\mathbb{P}(Y\in\cdot|\mathcal{D}_{\ell}))$.
For a random variable $\chi$ and random policy $\pi$, the following will be
involved in the information ratio:

$\displaystyle\mathbb{I}_{\ell}^{\pi}(\chi;\mathcal{H}_{\ell,h}):=\mathbb{I}_{\ell}(\chi;\mathcal{H}_{\ell,h}|\pi)=\mathbb{E}_{\pi}[D_{\mathrm{KL}}(\mathbb{P}_{\ell}((\chi,\mathcal{H}_{\ell,h})\in\cdot|\pi)||\mathbb{P}_{\ell}(\chi\in\cdot|\pi)\otimes\mathbb{P}_{\ell}(\mathcal{H}_{\ell,h}\in\cdot|\pi))]\,,$
(5)

Note that
$\mathbb{E}[\mathbb{I}_{\ell}(X;Y)]=\mathbb{I}(X;Y|\mathcal{D}_{\ell})$. To
clarify, $\mathbb{P}_{\ell}(\mathcal{H}_{\ell,h}\in\cdot|\pi)$ is the
probability of $\mathcal{H}_{\ell,h}$ being generated under $\pi$ within some
environment. Given that the histories under consideration are generated by the
TS algorithm, they are always generated in the true environment $\mathcal{E}$
under an optimal policy $\pi^{*}_{\mathcal{E}^{\prime}}$. For
$\pi=\pi^{\ell}_{\text{TS}}$, this can be computed as
$\mathbb{P}_{\ell}(\mathcal{H}_{\ell,h}|\pi)=\int_{\mathcal{E}}P(\mathcal{H}_{\ell,h}|\pi,\mathcal{E})\operatorname{d}\\!\mathbb{P}_{\ell}(\mathcal{E})$,
where $P(\mathcal{H}_{\ell,h}|\pi,\mathcal{E})$ is an expression in terms of
transition and reward functions of $\mathcal{E}$ and $\pi$.

Finally, we define $\bar{\mathcal{E}}_{\ell}$ as the mean MDP where
$P_{h}^{\bar{\mathcal{E}}_{\ell}}(\cdot|s,a)=\mathbb{E}_{\ell}[P_{h}^{\mathcal{E}}(\cdot|s,a)]$
is the mean of posterior measure, and similarly for
$r_{h}^{\bar{\mathcal{E}}_{\ell}}(\cdot|s,a)=\mathbb{E}_{\ell}[r_{h}^{\mathcal{E}}(\cdot|s,a)]$.
We note that under the independence assumption across layers, the same is
given for the state-occupancy density
$d_{h,\pi}^{\bar{\mathcal{E}}_{\ell}}=\mathbb{E}_{\ell}[d_{h,\pi}^{\mathcal{E}}]$.

##  3 Bayesian RL problems

######  Definition 1.

A Bayesian RL in this paper refers to the time-inhomogeneous finite-horizon
MDP with independent priors on transition and reward functions, as described
in Section 2.1.

The Bayesian RL problem is the task of finding an algorithm $\pi$ with optimal
Bayesian regret as defined in Eq. 4. Below we list the variations of this
problem. A setting considered by most related works such as Osband and Van
Roy, (2017); Fan and Ming, (2021) is the following:

######  Definition 2.

The time (reward) homogeneous Bayesian RL refers to the Bayesian RL setting
where the prior $\rho^{P}$ ($\rho^{R}$) is over the space $\Theta^{P}$
($\Theta^{R}$) containing the single transition (reward) function $P$ ($r$)
defining $\mathcal{E}$, i.e., all layers have the same transition (reward)
functions.

######  Definition 3.

The tabular Bayesian RL is a Bayesian RL where ${\mathcal{S}},\mathcal{A}$ are
finite sets.

######  Definition 4 (Linear MDP Yang and Wang, (2019); Jin et al., (2020)).

Let
$\phi^{P}:{\mathcal{S}}\times\mathcal{A}\to\mathbb{R}^{d_{f}^{P}},\phi^{R}:{\mathcal{S}}\times\mathcal{A}\to\mathbb{R}^{d_{f}^{R}}$
be feature maps with bounded norm
$\|\phi^{P}(s,a)\|_{2},\|\phi^{R}(s,a)\|_{2}\leq 1$. The linear Bayesian RL is
a Bayesian RL where for any
$\mathcal{E}=\\{(P_{h}^{\mathcal{E}},r_{h}^{\mathcal{E}})\\}_{h=1}^{H}\in\Theta$,
there exists vector-valued maps
$\psi_{h}^{P,\mathcal{E}}(s),\psi_{h}^{R,\mathcal{E}}(s)$ with bounded
$l_{2}-$norm such that for any $(s,a)\in{\mathcal{S}}\times\mathcal{A}$,

$\displaystyle
P_{h}^{\mathcal{E}}(\cdot|s,a)=\langle\phi^{P}(s,a),\psi_{h}^{P,\mathcal{E}}(\cdot)\rangle\,,\
\
r_{h}^{\mathcal{E}}(\cdot|s,a)=\langle\phi^{R}(s,a),\psi_{h}^{R,\mathcal{E}}(\cdot)\rangle$
(6)

A restricted version of the finite mixtures called linear mixture was first
considered in Ayoub et al., (2020) in the frequentist setting. Here, we
consider the general setting.

######  Definition 5.

The finite mixtures Bayesian RL is a Bayesian RL where for any $h\in[H]$ there
exists fixed conditional distributions
$\\{Z_{h,i}^{P}:{\mathcal{S}}\times\mathcal{A}\to\Delta_{\mathcal{S}}\\}_{i=1}^{m_{h}^{P}}$
and
$\\{Z_{h,i}^{R}:{\mathcal{S}}\times\mathcal{A}\to\Delta_{[0,1]}\\}_{i=1}^{m_{h}^{R}}$,
such that for any environment $\mathcal{E}$ given by
$\\{(P_{h}^{\mathcal{E}},r_{h}^{\mathcal{E}})\\}_{h=1}^{H}$, there exists
parametrized probability distributions
$\bm{a}_{h}^{P,\mathcal{E}}:{\mathcal{S}}\times\mathcal{A}\to\Delta_{m_{h}^{P}},\bm{a}_{h}^{R,\mathcal{E}}:{\mathcal{S}}\times\mathcal{A}\to\Delta_{m_{h}^{R}}$
such that

$\displaystyle
P_{h}^{\mathcal{E}}(\cdot|s,a)=\sum_{i=1}^{m_{h}^{P}}a_{h,i}^{P,\mathcal{E}}(s,a)Z_{h,i}^{P}(\cdot|s,a),$
$\displaystyle\ \
r_{h}^{\mathcal{E}}(\cdot|s,a)=\sum_{i=1}^{m_{h}^{R}}a_{h,i}^{R,\mathcal{E}}(s,a)Z_{h,i}^{R}(\cdot|s,a)$
(7)

##  4 Surrogate learning

Next, we define the discretized surrogate learning problem, and bound the size
of the surrogate environments space, a significant term in the regret. To do
so, we need to first define the Kolmogorov dimension of a set of parametrized
distributions, esp. working out the case of $l_{1}-$distance. In the
definitions below, we implicitly assume any required minimal measurability
assumptions on the involved sets.

######  Definition 6.

Given a set $\mathcal{F}$ of $\mathcal{O}-$parametrized distributions
$P:\mathcal{O}\to\Delta({\mathcal{S}})$ over a set ${\mathcal{S}}$ where both
$\mathcal{O},{\mathcal{S}}$ are measurable. Let
$\mathcal{M}(\cdot,\cdot):\mathcal{F}\times\mathcal{F}\to\mathbb{R}^{\geq 0}$
be a distance, i.e., $\mathcal{M}(P,Q)\geq 0\xleftrightarrow{=}P=Q$. Then its
right $\varepsilon-$covering number is the size $K_{\mathcal{M}}(\varepsilon)$
of the smallest set
$\mathcal{C}_{\mathcal{M}}(\varepsilon)=\\{P_{1},\ldots,P_{K_{\mathcal{M}}(\varepsilon)}\\}\subset\mathcal{F}$
such that

$\displaystyle\forall P\in\mathcal{F},\ \exists
P_{j}\in\mathcal{C}_{\mathcal{M}}(\varepsilon):\
\mathcal{M}(P,P_{j})\leq\varepsilon\,.$ (8)

The potential asymmetry of $\mathcal{M}$ (e.g., KL-divergence) requires the
notion of left/right covering number. The right covering number will be the
default, so covering number will always refer to that.

######  Definition 7.

Let $d_{\mathcal{M}}(\varepsilon)=\log(K_{\mathcal{M}}(\varepsilon))$. Define
the Kolmogorov $\mathcal{M}-$dimension $d_{\mathcal{M}}$ of $\mathcal{F}$ as

$\displaystyle d_{\mathcal{M}}=\limsup_{\varepsilon\to
0}\frac{d_{\mathcal{M}}(\varepsilon)}{\log(\frac{1}{\varepsilon})}.$ (9)

For $l_{1}(P,Q):=\sup_{o\in\mathcal{O}}||P(\cdot|o)-Q(\cdot|o)||_{1}$,
applying Definition 6 to the sets $\Theta_{h}^{P},\Theta_{h}^{R}$ with
$\mathcal{O}={\mathcal{S}}\times\mathcal{A}$, and denote the respective
covering numbers by $L_{h}^{P}(\varepsilon),L_{h}^{R}(\varepsilon)$
corresponding to covering sets
$\mathcal{C}_{h}^{P}(\varepsilon),\mathcal{C}_{h}^{R}(\varepsilon)$. Similarly
applying Eq. 9 and denote the corresponding $l_{1}-$dimensions by
$d_{l_{1},h}^{P}(\varepsilon),d_{l_{1},h}^{R}(\varepsilon),d_{l_{1},h}^{P},d_{l_{1},h}^{R}$
and
$d_{l_{1}}^{P}:=\sum_{h}d_{l_{1},h}^{P},d_{l_{1}}^{R}:=\sum_{h}d_{l_{1},h}^{R}$.
The sums
$d_{l_{1},h}:=d_{l_{1},h}^{P}+d_{l_{1},h}^{R},d_{l_{1}}:=d_{l_{1}}^{P}+d_{l_{1}}^{R}$
can be interpreted as the $l_{1}-$dimension of $\Theta_{h}$ and $\Theta$,
i.e., the environment space.

######  Remark 3.

We can also apply this framework to the KL-divergence, by
$\mathcal{M}_{\mathrm{KL}}(P,Q):=\sup_{o\in\mathcal{O}}D_{\mathrm{KL}}(P(\cdot|o)||Q(\cdot||o))$.
This was implicitly used by Hao and Lattimore, (2022) to prove their regret
bound in the tabular case. Note that Pinsker’s lemma (Lemma 9) implies that
the KL-divergence is larger than the squared total variance, and the latter is
trivially larger than the $l_{1}$ distance. Therefore, $l_{1}-$dimension is
smaller than $d_{\mathcal{M}_{\mathrm{KL}}}$, allowing for tighter regret
bounds.

We now revisit the definition of $\varepsilon-$value partitions and show their
existence is guaranteed by finite $l_{1}-$covering numbers. These partitions
are the origins of surrogate environments.

######  Definition 8.

Given $\varepsilon>0$, an $\varepsilon-$value partition for a Bayesian RL
problem is a partition $\\{\Theta_{k}\\}_{k=1}^{K}$ over $\Theta$ such that
for any $k\in[K]$ and $\mathcal{E},\mathcal{E}^{\prime}\in\Theta_{k}$,

$\displaystyle
V_{1,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}}(s_{1}^{\ell})-V_{1,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}^{\prime}}(s_{1}^{\ell})\leq\varepsilon\,.$
(10)

A layered $\varepsilon-$value partition is one where the transition functions
are independent over layers after conditioning on $k$. Throughout this paper,
we will only consider layered $\varepsilon-$value partition. We define
$K_{\operatorname{surr}}(\varepsilon)$ as the minimum $K$ for which there
exists a layered $\varepsilon-$value partition.

Inspired by Eq. 9, we define the surrogate dimension as
$d_{\operatorname{surr}}=\limsup_{\varepsilon\to
0}\frac{K_{\operatorname{surr}}(\varepsilon)}{\log(1/\varepsilon)}$.

######  Lemma 1.

Given a Bayesian RL, we have
$K_{\operatorname{surr}}(\varepsilon)\leq\prod_{h}L_{h}^{P}(\varepsilon/(2H)^{2})\times
L_{h}^{R}(\varepsilon/(4H))$. This implies $d_{\operatorname{surr}}\leq
d_{l_{1}}$.

The above is proved in Appendix A. It is hard to find
$d_{\operatorname{surr}}$, but one can estimate $d_{l_{1}}$, and according to
the above, this acts as a proxy for $K_{\operatorname{surr}}$. This is useful
as the regret relates to $K_{\operatorname{surr}}$. But to show this, we need
to construct surrogate environments inside each partition, and show that
learning those is almost equivalent to the original problem. Let $\zeta$ be a
discrete random variable taking values in
$\\{1,\cdots,K_{\operatorname{surr}}(\varepsilon)\\}$ that indicates the
partition $\mathcal{E}$ lies in, such that $\zeta=k$ if and only if
$\mathcal{E}\in\Theta_{k}$.

######  Lemma 2.

For any $\varepsilon-$value partition and any $\ell\in[L]$, there are random
environments $\tilde{\mathcal{E}}^{*}_{\ell}\in\Theta$ with their laws only
depending on $\zeta,\mathcal{D}_{\ell}$, such that

$\displaystyle\mathbb{E}_{\ell}\left[V_{1,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}}(s_{1}^{\ell})-V_{1,\pi^{\ell}_{\text{TS}}}^{\mathcal{E}}(s_{1}^{\ell})\right]-\mathbb{E}_{\ell}\left[V_{1,\pi^{*}_{\mathcal{E}}}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s_{1}^{\ell})-V_{1,\pi^{\ell}_{\text{TS}}}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s_{1}^{\ell})\right]\leq\varepsilon\,.$
(11)

The expectation in both equations is over $\mathcal{E}$ and
$\pi_{\text{TS}}^{\ell}\in\\{\pi^{*}_{\mathcal{E}^{\prime}}\\}_{\mathcal{E}^{\prime}\in\Theta}$,
with both sampled independently $\sim\mathbb{P}_{\ell}(\cdot)$, and the $K$
different values of $\tilde{\mathcal{E}}^{*}_{\ell}$. The second expectation
over $(\tilde{\mathcal{E}}^{*}_{\ell},\mathcal{E})$ is over pairs that are in
the same partition, i.e., $\tilde{\mathcal{E}}^{*}_{\ell},\mathcal{E}$ are
independent only after conditioning on $\zeta$.

We note that the proof in (Hao and Lattimore,, 2022, App. B.1) contains the
use of a lemma that does not apply to construct the law of the environment
$\tilde{\mathcal{E}}^{*}_{\ell}$. More details is provided in Appendix B,
where we find $\tilde{\mathcal{E}}^{*}_{\ell}$ by minimizing an expected value
of $\pi^{\ell}_{\text{TS}}$.

##  5 Bayesian regret bounds for Thompson Sampling

###  5.1 General Bayesian regret bound

We start by introducing the notion of value diameter.

######  Definition 9.

Given the environment $\mathcal{E}$, its value diameter is defined as

$\lambda_{\mathcal{E}}:=\max_{1\leq h\leq
H}(\sup_{s}V_{h,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}}(s)-\inf_{s}V_{h,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}}(s))+\max_{1\leq
h\leq
H,s\in{\mathcal{S}},a\in\mathcal{A}}(r^{\operatorname{sup}}_{h}(s,a)-r^{\operatorname{inf}}_{h}(s,a)),$

where $r^{\operatorname{sup}}_{h}(s,a)$ (and
$r^{\operatorname{inf}}_{h}(s,a)$) is the supremum (and infimum) of the set of
rewards that are attainable under the distribution $r_{h}(s,a)$ with non-zero
probability. As a special case, if rewards are deterministic, then we have
$r^{\operatorname{sup}}_{h}(s,a)=r^{\operatorname{inf}}_{h}(s,a)$ for all
$s,a$. The (average) value diameter over $\Theta$ is denoted by
$\lambda:=\mathbb{E}_{\mathcal{E}\sim\rho}[\lambda_{\mathcal{E}}^{2}]^{1/2}$.

As the value function is between $0$ and $H$, we have
$\lambda_{\mathcal{E}}\leq H+1$ implying $\lambda\leq H+1$. Note that value
diameter is closely related to the notion of diameter commonly defined in
finite RL problems. Strictly speaking, for a time-homogeneous RL, it is
straightforward to see that the value diameter is bounded from above by one
plus the diameter Puterman, (2014). To our knowledge, the notion of diameter
has not been defined in the time-inhomogeneous setting.

We now discuss the assumptions surrounding our results. The main technical
assumption of this paper is the existence of consistent estimators, which as
we will see in Appendix J, is closely related to the notion of posterior
consistency:

######  Assumption 1.

There exists a strongly consistent estimator of the true environment given the
history.

Roughly speaking, we assume that with unlimited observations under TS, it is
possible to find the true environment. For this assumption to fail, we need to
have two environments that produce the same distribution over histories under
TS and are therefore indistinguishable from the point of view of TS. The
precise description of this assumption is detailed in Appendix J.

Another necessary technical assumption is that almost all optimal policies
visit almost all state action pairs in their respective environment.

######  Assumption 2.

For almost every environment $\mathcal{E}\in\Theta$ and almost every
$(s,a)\in{\mathcal{S}}\times\mathcal{A}$ and every $h\in[H]$, we have

$d_{h,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}}(s,a)\neq 0.$

Recall that, for any environment $\mathcal{E}\in\Theta$, the policy
$\pi^{*}_{\mathcal{E}}$ is the optimal policy of $\mathcal{E}$ within the
policy class $\Pi$. Therefore, one example of how the above assumption holds
is when $\Pi$ is the set of $\varepsilon$-greedy algorithms and transition
functions of environments assign non-zero probability to every state. Under
these assumptions, we discuss our main result and its corollaries.

######  Theorem 3.

Given a Bayesian RL problem, for all $\varepsilon>0$, we have

$\displaystyle\mathfrak{BR}_{L}(\pi_{\text{TS}})\leq
2\lambda\sqrt{\log(K_{\operatorname{surr}}(\varepsilon))T}+L\varepsilon+T_{0}$
(12)

where $T_{0}$ does not depend on $T$. This can be further upper bounded by

$\displaystyle\mathfrak{BR}_{L}(\pi_{\text{TS}})\leq\widetilde{O}(\lambda\sqrt{d_{l_{1}}T})\,.$
(13)

for large enough $T$. Given a homogeneous $l_{1}$ dimension
$d_{\operatorname{hom}}=d_{l_{1},h},\forall h$, this simplifies to

$\displaystyle\mathfrak{BR}_{L}(\pi_{\text{TS}})\leq\widetilde{O}(\lambda\sqrt{Hd_{\operatorname{hom}}T})\,.$
(14)

######  Remark 4.

For all regret bounds, we will replace $\lambda\leq H+1$ to compare our
result. For the case of homogeneous dimensions, we obtain
$\widetilde{O}(H^{3/2}\sqrt{d_{\operatorname{hom}}T})$. Crucially, our main
result shows a new conceptual understanding of the information ratio by
bounding it by two terms of different nature: $H$ and $\lambda$, where the
latter can be bounded by either the largest diameter of the environments or
$H$.

######  Remark 5.

Despite not impacting the asymptotics, the impact of $T_{0}$ can be large
depending on the structure of the RL problem, and could be dominant even for
large $T$s in practice.

######  Remark 6.

Considering time as a part of the state observation, one could apply this
regret analysis to particular time-homogeneous settings. However, this mapping
of time-inhomogeneous RLs to homogeneous ones is not surjective, hence the
result above does not readily extend to time-homogeneous settings.

While Fan and Ming, (2021) were the first to consider a nonlinear Bayesian RL
model, their bound is limited to the Gaussian process (with linear kernel)
setting, while ours in the nonlinear time inhomogeneous setting makes no
assumptions on the prior and is the first such bound. Our novel analysis allow
us to upper bound the information ratio by $\lambda\sqrt{H}$ instead of, for
example $H^{3/2}\sqrt{SA}$ (Hao and Lattimore, (2022)) in the tabular case,
improving the regret bound by a square root relevant to the dimension $d$ of
the problem.

The detailed proof is given in Appendix C. Following Hao and Lattimore,
(2022), the regret (4) is rewritten using Lemma 2 to reduce the problem into
its surrogate, and we use the well-known information-ratio trick by
multiplying and dividing by the mutual information. We follow that with a
Cauchy-Schwarz, summarized below

$\displaystyle\mathfrak{BR}_{L}(\pi_{\text{TS}})$
$\displaystyle\leq\mathbb{E}\left[\sum_{\ell=1}^{L}\frac{\mathbb{E}_{\ell}\left[V_{1,\pi^{*}_{\mathcal{E}}}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s_{1}^{\ell})-V_{1,\pi^{\ell}_{\text{TS}}}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s_{1}^{\ell})\right]}{\sqrt{\mathbb{I}_{\ell}^{\pi^{\ell}_{\text{TS}}}(\tilde{\mathcal{E}}_{\ell}^{*};\mathcal{H}_{\ell,H})}}\sqrt{\mathbb{I}_{\ell}^{\pi^{\ell}_{\text{TS}}}(\tilde{\mathcal{E}}_{\ell}^{*};\mathcal{H}_{\ell,H})}\right]+L\varepsilon$
(15)
$\displaystyle\leq\sqrt{\mathbb{E}\left[\sum_{\ell=1}^{L}\frac{\left(\mathbb{E}_{\ell}\left[V_{1,\pi^{*}_{\mathcal{E}}}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s_{1}^{\ell})-V_{1,\pi^{\ell}_{\text{TS}}}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s_{1}^{\ell})\right]\right)^{2}}{\mathbb{I}_{\ell}^{\pi^{\ell}_{\text{TS}}}(\tilde{\mathcal{E}}_{\ell}^{*};\mathcal{H}_{\ell,H})}\right]\mathbb{E}\left[\sum_{\ell=1}^{L}\mathbb{I}_{\ell}^{\pi^{\ell}_{\text{TS}}}(\tilde{\mathcal{E}}_{\ell}^{*};\mathcal{H}_{\ell,H})\right]}+L\varepsilon$
(16)

Note the cost $\varepsilon$ at each episode (Lemma 2) in the first inequality,
yielding the overall error $L\varepsilon$. Then, we can bound the mutual
information appearing in the regret term by
$\mathbb{E}\left[\sum_{\ell=1}^{L}\mathbb{I}_{\ell}^{\pi^{\ell}_{\text{TS}}}(\tilde{\mathcal{E}}_{\ell}^{*};\mathcal{H}_{\ell,H})\right]=I_{\ell}^{\pi^{\ell}_{\text{TS}}}(\tilde{\mathcal{E}}_{\ell}^{*};\mathcal{D}_{\ell})\leq
I_{\ell}^{\pi^{\ell}_{\text{TS}}}(\zeta;\mathcal{D}_{\ell})\leq
H(\zeta)\leq\log(K_{\operatorname{surr}}(\varepsilon))$, where we used the
mutual information chain rule, followed by data processing inequality to
substitute $\tilde{\mathcal{E}}_{\ell}^{*}\to\zeta$, and finally used the
trivial bound by the entropy. But the main novelty of our approach lies in our
control of the first term

$\displaystyle\Gamma_{\ell}(\pi_{\text{TS}}^{\ell}):=\frac{\left(\mathbb{E}_{\ell}\left[V_{1,\pi^{*}_{\mathcal{E}}}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s_{1}^{\ell})-V_{1,\pi^{\ell}_{\text{TS}}}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s_{1}^{\ell})\right]\right)^{2}}{\mathbb{I}_{\ell}^{\pi^{\ell}_{\text{TS}}}(\tilde{\mathcal{E}}_{\ell}^{*};\mathcal{H}_{\ell,H})}$
(17)

called the information ratio. In our analysis, we have the following bound on
its expectation.

$\mathbb{E}[\Gamma_{\ell}(\pi_{\text{TS}}^{\ell})\mid\mathcal{E}_{0}]\leq\mathbb{E}\left[\sum_{h}\int\frac{\mathbb{E}_{\ell}\left[(\lambda_{\mathcal{E}}d_{h,\pi^{*}}^{\bar{\mathcal{E}}_{\ell}}(s,a))^{2}\right]}{\mathbb{E}_{\ell}\left[d_{h,\pi^{*}}^{\bar{\mathcal{E}}_{\ell}}(s,a)\right]}\mu_{{\mathcal{S}}\times\mathcal{A}}\mid\mathcal{E}_{0}\right],$

where the average is taken over all histories $\mathcal{D}_{\ell}$ that are
generated from running TS on the true environment $\mathcal{E}_{0}$, and we
have introduced the smaller term $\lambda_{\mathcal{E}}$ instead of $H$ in Hao
and Lattimore, (2022). While Hao and Lattimore, (2022) essentially bound the
above only in the tabular setting with $SAH^{3}$, we manage to generally bound
the above with a more precise bound using Doob’s consistency theorem.
Assumption 1 allows us to use Doob’s consistency theorem to conclude that for
almost every environment $\mathcal{E}_{0}$, almost every infinite sequence of
histories $(\mathcal{D}_{\ell})_{\ell=1}^{\infty}$ sampled from
$\mathcal{E}_{0}$, and every integrable function $f$, the posterior mean
$\mathbb{E}_{\ell}[f(\mathcal{E})]=\mathbb{E}[f(\mathcal{E})\mid\mathcal{D}_{\ell}]$
converges to $f(\mathcal{E}_{0})$. In particular, we conclude that
$\mathbb{E}[\Gamma_{\ell}(\pi_{\text{TS}}^{\ell})\mid\mathcal{E}_{0}]$ tends
to $\lambda_{\mathcal{E}_{0}}^{2}H$ in the limit, allowing us to claim that
for large enough $\ell$, the expected information ratio
$\mathbb{E}[\Gamma_{\ell}(\pi_{\text{TS}}^{\ell})]$ is uniformly bounded by
$2\mathbb{E}[\lambda_{\mathcal{E}}^{2}]H=2\lambda^{2}H$. As there are $L$ many
such ratios, the two bounds together yield
$2\sqrt{\lambda^{2}HL}\cdot\sqrt{\log(K_{\operatorname{surr}}(\varepsilon))}+L\varepsilon$.
This bound is true for large enough $\ell$, giving the additional additive
term $T_{0}$ in the theorem. Since this term is additive, applying Lemma 1 to
bound $\log(K_{\operatorname{surr}}(\varepsilon))$, we have successfully shown
the asymptotic behavior of the regret, independent of the prior, is of order
$\widetilde{O}(H\sqrt{d_{l_{1}}T})$.

###  5.2 Applications

In each application below, the challenge is to bound $d_{l_{1}}$ using the
specifics of the model, and except for the case of tabular Bayesian RL, such
analysis has not been carried out rigorously. We formalize the corollaries and
show they are state-of-the-art compared to the literature.

#### Tabular RL.

The result below follows from Theorem 3; the main contribution comes from our
new information ratio bound, followed by the estimate
$\widetilde{O}((\frac{1}{\varepsilon})^{SAH})$ of
$K_{\operatorname{surr}}(\varepsilon)$ (Hao and Lattimore, (2022)).

######  Corollary 4.

Given a tabular Bayesian RL problem, for large enough $T$,

$\displaystyle\mathfrak{BR}_{L}(\pi_{\text{TS}})\leq\widetilde{O}(\lambda\sqrt{HSAT})\,,$
(18)

where the polylogarithmic terms are explicitly in terms of $H,S,A,L$.

We observe that our result matches Osband and Van Roy, (2017) when their
result in the time homogeneous setting (Definition 2) is extended to time
inhomogeneous. However, in that paper, the authors assume a Dirichlet based
prior which we do not.

#### Linear RL.

A previous state-of-the-art $\widetilde{O}(d_{f}H^{3/2}\sqrt{T})$ was claimed
by Hao and Lattimore, (2022) to hold for linear Bayesian RLs with
deterministic reward. We note:

  * •

As in the previous cases, their proof in bounding their information ratio
includes a factor of $d_{f}$, which ours avoids.

  * •

We show that the proof bounding $K_{\operatorname{surr}}(\varepsilon)$ in (Hao
and Lattimore,, 2022, App. B.4) is incorrect, starting with a wrong
application of Cauchy-Schwarz and a wrong mutual information in their
definition of information ratio. We provide counterexamples for the estimates
found therein to substantiate our claim (see Section F.1).

To state our own corollary in this case, we need to define a few notions. Let
$d_{l_{1}}^{f}=d_{l_{1}}^{P,f}+d_{l_{1}}^{R,f}$ be the sum of the
$l_{1}-$dimensions of the feature map space
$\\{\psi_{h}^{P,\mathcal{E}}\\}_{\mathcal{E}\in\Theta},\\{\psi_{h}^{R,\mathcal{E}}\\}_{\mathcal{E}\in\Theta}$
where the $l_{1}-$distance between feature maps is defined as
$l_{1}(\psi_{h}^{\mathcal{E}},\psi_{h}^{\mathcal{E}^{\prime}})=\int_{s}\|\psi_{h}^{\mathcal{E}}-\psi_{h}^{\mathcal{E}^{\prime}}\|_{1}\mu_{\mathcal{S}}$.
Our corollary also provides a concrete bound in the case of mixture linear
Bayesian RL where the feature maps are themselves a sum of finitely many fixed
feature maps. This means for all $\mathcal{E}\in\Theta$, we have

$\displaystyle\psi_{h}^{P,\mathcal{E}}=\sum_{i=1}^{m_{h}^{P}}a_{h,i}^{P,\mathcal{E}}\Psi_{h,i}^{P}(s),\
\
\psi_{h}^{R,\mathcal{E}}=\sum_{i=1}^{m_{h}^{R}}a_{h,i}^{R,\mathcal{E}}\Psi_{h,i}^{R}(s)$
(19)

where
$\\{\Psi_{h,i}^{P}(s)\\}_{i=1}^{m_{h}^{P}},\\{\Psi_{h,i}^{R}(s)\\}_{i=1}^{m_{h}^{R}}$
are finitely many fixed feature maps and
$\forall\mathcal{E},h:\sum_{i}|a_{h,i}^{P,\mathcal{E}}|^{2},\sum_{i}|a_{h,i}^{R,\mathcal{E}}|^{2}\leq
C_{a}$ for some constant $C_{a}>0$. Let
$M=M^{P}+M^{R}=\sum_{h}m_{h}^{P}+\sum_{h}m_{h}^{R}$.

######  Corollary 5.

For a linear Bayesian RL, for large enough $T$,

$\displaystyle\mathfrak{BR}_{L}(\pi_{\text{TS}})\leq\widetilde{O}(\lambda\sqrt{d_{l_{1}}^{f}T}).$
(20)

Given a linear Bayesian RL with finitely many states and total feature space
dimension $d_{f}=d_{f}^{P}+d_{f}^{R}$, we have $d_{l_{1}}\leq 2d_{f}HS$,
yielding for large enough $T$,

$\displaystyle\mathfrak{BR}_{L}(\pi_{\text{TS}})\leq\widetilde{O}(\lambda\sqrt{Hd_{f}ST}).$
(21)

Given a mixture linear Bayesian RL, for large enough $T$,

$\displaystyle\mathfrak{BR}_{L}(\pi_{\text{TS}})\leq\widetilde{O}(\lambda\sqrt{MT})\,,$
(22)

The proof is given in Appendix F. The fact that $d_{l_{1}}$ appears instead of
$d_{f}$ in the general bound is not counter-intuitive, as we should expect the
complexity of the feature map space
$\\{\psi_{h}^{P,\mathcal{E}}(s)\\}_{\mathcal{E}\in\Theta,h\in[H]},\\{\psi_{h}^{R,\mathcal{E}}(s)\\}_{\mathcal{E}\in\Theta,h\in[H]}$
to play a role in the regret, especially as this space can be very complex,
and model very different environments that can not be grouped in the same
$\varepsilon-$value partition.

Therefore, opposite to the claim made by Hao and Lattimore, (2022), this
complexity can not be captured by simply $d_{f}$ except maybe in degenerate
cases, such as when ${\mathcal{S}}$ is finite, which is our second statement.
More generally, if each feature map
$\psi_{h}^{P,\mathcal{E}}(s),\psi_{h}^{R,\mathcal{E}}(s)$ can be characterized
with a vector of uniformly bounded norm
$\bm{a}_{h}^{P,\mathcal{E}}\in\mathbb{R}^{m_{h}^{P}},\bm{a}_{h}^{R,\mathcal{E}}\in\mathbb{R}^{m_{h}^{R}}$,
then we can bound the regret in terms of $m_{h}^{P},m_{h}^{R}$’s, as is done
in Eq. 22 (the finite state case corresponds to
$m_{h}^{P}=d_{f}^{P}S,m_{h}^{R}=d_{f}^{R}S$).

#### Finite mixtures RL.

To state our finite mixtures model result, we need to set the following
notations. Let
$d_{l_{1}}^{m}=d_{l_{1}}^{m,P}+d_{l_{1}}^{m,R}=\sum_{h}d_{l_{1},h}^{m,P}+\sum_{h}d_{l_{1},h}^{m,R}$
correspond to the total $l_{1}-$dimension of the space of mixtures coefficient
maps
$\\{\bm{a}_{h}^{P,\mathcal{E}}(s,a)\\}_{\mathcal{E}\in\Theta},\\{\bm{a}_{h}^{R,\mathcal{E}}(s,a)\\}_{\mathcal{E}\in\Theta}$
with $l_{1}-$ distance defined as
$l_{1}(\bm{a}_{h}^{\mathcal{E}},\bm{a}_{h}^{\mathcal{E}^{\prime}})=\sup_{s,a}\|\bm{a}_{h}^{\mathcal{E}}(s,a)-\bm{a}_{h}^{\mathcal{E}^{\prime}}(s,a)\|_{1}$.
Define also the restricted finite mixtures model where
$\bm{a}_{h}^{P,\mathcal{E}},\bm{a}_{h}^{R,\mathcal{E}}$ are vectors in
$\mathbb{R}^{m_{h}^{P}},\mathbb{R}^{m_{h}^{R}}$ independent of $(s,a)$ and let
$M=M^{P}+M^{R}=\sum_{h}m_{h}^{P}+\sum_{h}m_{h}^{R}$.

######  Corollary 6.

Given a finite mixtures Bayesian RL problem, for large enough $T$,

$\displaystyle\mathfrak{BR}_{L}(\pi_{\text{TS}})\leq\widetilde{O}(\lambda\sqrt{d_{l_{1}}^{m}T})\,.$
(23)

Assuming the restricted finite mixtures model, for large enough $T$,

$\displaystyle\mathfrak{BR}_{L}(\pi_{\text{TS}})\leq\widetilde{O}\left(\lambda\sqrt{MT}\right)\,.$
(24)

which, given a uniform dimension $m=m_{h}^{P}=m_{h}^{R}$, yields
$\widetilde{O}(\lambda\sqrt{HmT})$.

We prove the above in Appendix G, deriving it from our generic bound, after
relating the $l_{1}-$dimension $d_{l_{1}}$ of the environment space to that of
the mixtures coefficients. To the best of our knowledge, this is the first
bound for finite mixtures Bayesian RL problems. We note that in a previous
work (Ayoub et al., (2020)), a restricted version of finite mixtures, like in
Eq. 24, was considered in the frequentist setting.

We finish this section by proposing the following conjecture, in line with
(Osband and Van Roy,, 2017, Conj. 1).

######  Conjecture 7.

For the Bayesian RL, the following is true and optimal for all $T$:

$\displaystyle\mathfrak{BR}_{L}(\pi_{\text{TS}})\leq
O\left(\inf_{\varepsilon>0}(\sqrt{H\log(K_{\operatorname{surr}}(\varepsilon))T}+L\varepsilon)\right)\,.$
(25)

where the constant factor is independent of the prior. This means there exists
a Bayesian RL problem such that
$\mathfrak{BR}_{L}(\pi_{\text{TS}})=\widetilde{\Omega}(\sqrt{Hd_{\operatorname{surr}}T})$.
All polylogarithmic terms are in terms of $H,d_{\operatorname{surr}},T$.

Note that the above coincides with the lower bound for the (model-based) time
inhomogeneous frequentist setting; see e.g., Jin et al., (2018) for the proven
lower bound for the tabular case. This is also $\sqrt{H}$ higher (this factor
being baked in $d_{\operatorname{surr}}$) than that of the time homogeneous
frequentist setting, which is expected, according to (Jin et al.,, 2018, App.
D). Note that in this conjecture, the $\lambda$ in our bound is replaced by
$\sqrt{H}$, and the conjecture is not for $T$ large enough, but for all $T$.
Supporting this conjecture requires experiments where TS can be exactly
implemented assuming access to an oracle which provides the optimal policy for
a query environment. Simulations have been performed for the similar (Osband
and Van Roy,, 2017, Conj. 1) in the time homogeneous case. Our conjecture is
similar but with the additional expected factor of $\sqrt{H}$ due to time
inhomogeneity, thus their simulation also supports the above.

##  6 Conclusions

In this paper, we have addressed the Bayesian Reinforcement Learning (RL)
problem in the context of time inhomogeneous transition and reward functions.
By considering both Bayesian transition and Bayesian rewards without prior
assumptions, we have extended the scope of previous works, making our
formulation more comprehensive. To simplify the learning problem, we have
introduced surrogate environments, which discretize the environment space. We
have established a connection between the size of this new environment space
and the $l_{1}$-dimensions of the transition and reward functions space,
providing insights into the $l_{1}$-dimension of the environment space denoted
by $d_{l_{1}}$. We have employed posterior consistency tools to analyze the
information ratio, which captures the trade-off between exploration and
exploitation. We conjecture that (at least a weakened version of) our
posterior consistency assumption should hold in general, which is left for
future work. Our analysis has resulted in a refined approach to estimate the
Bayesian regret in Thompson Sampling (TS), yielding a regret bound of
$\widetilde{O}(\lambda\sqrt{d_{l_{1}}T})$ for large enough time steps $T$. The
result is specialized to linear, tabular, and finite mixtures MDPs.

Limitations: While the paper provides asymptotic generic regret bound for TS
in a generalized setup which improve the state of the art results, finding
lower bounds, esp. one dependent on $\lambda$, are left open. In addition, the
issue of prior misspecificity is not discussed and left for future studies.

## References

  * Abedsoltan et al., (2023) Abedsoltan, A., Belkin, M., and Pandit, P. (2023).  Toward large kernel models.  arXiv preprint arXiv:2302.02605.
  * Agarwal et al., (2022) Agarwal, A., Jin, Y., and Zhang, T. (2022).  VOQL: Towards optimal regret in model-free rl with nonlinear function approximation.  arXiv preprint arXiv:2212.06069.
  * Agrawal and Jia, (2017) Agrawal, S. and Jia, R. (2017).  Optimistic posterior sampling for reinforcement learning: worst-case regret bounds.  Advances in Neural Information Processing Systems, 30.
  * Auer et al., (2008) Auer, P., Jaksch, T., and Ortner, R. (2008).  Near-optimal regret bounds for reinforcement learning.  Advances in neural information processing systems, 21.
  * Ayoub et al., (2020) Ayoub, A., Jia, Z., Szepesvari, C., Wang, M., and Yang, L. (2020).  Model-based reinforcement learning with value-targeted regression.  In International Conference on Machine Learning, pages 463–474. PMLR.
  * Azar et al., (2017) Azar, M. G., Osband, I., and Munos, R. (2017).  Minimax regret bounds for reinforcement learning.  In International Conference on Machine Learning, pages 263–272. PMLR.
  * Bertsekas and Tsitsiklis, (1996) Bertsekas, D. and Tsitsiklis, J. N. (1996).  Neuro-dynamic programming.  Athena Scientific.
  * Bubeck and Sellke, (2020) Bubeck, S. and Sellke, M. (2020).  First-order bayesian regret analysis of thompson sampling.  In Algorithmic Learning Theory, pages 196–233. PMLR.
  * Cai et al., (2020) Cai, Q., Yang, Z., Jin, C., and Wang, Z. (2020).  Provably efficient exploration in policy optimization.  In International Conference on Machine Learning, pages 1283–1294. PMLR.
  * Chakraborty et al., (2022) Chakraborty, S., Bedi, A., Koppel, A., Tokekar, P., Huang, F., and Manocha, D. (2022).  Posterior coreset construction with kernelized stein discrepancy for model-based reinforcement learning.  In NeurIPS 2022 Workshop on Score-Based Methods.
  * Dann et al., (2021) Dann, C., Mohri, M., Zhang, T., and Zimmert, J. (2021).  A provably efficient model-free posterior sampling method for episodic reinforcement learning.  Advances in Neural Information Processing Systems, 34:12040–12051.
  * Dong and Van Roy, (2018) Dong, S. and Van Roy, B. (2018).  An information-theoretic analysis for thompson sampling with many actions.  Advances in Neural Information Processing Systems, 31.
  * Duan et al., (2021) Duan, Y., Wang, M., and Wainwright, M. J. (2021).  Optimal policy evaluation using kernel-based temporal difference methods.  arXiv preprint arXiv:2109.12002.
  * Fan and Ming, (2021) Fan, Y. and Ming, Y. (2021).  Model-based reinforcement learning for continuous control with posterior sampling.  In International Conference on Machine Learning, pages 3078–3087. PMLR.
  * Ghosal and Van der Vaart, (2017) Ghosal, S. and Van der Vaart, A. (2017).  Fundamentals of nonparametric Bayesian inference, volume 44.  Cambridge University Press.
  * Hao and Lattimore, (2022) Hao, B. and Lattimore, T. (2022).  Regret bounds for information-directed reinforcement learning.  arXiv preprint arXiv:2206.04640.
  * Hao et al., (2021) Hao, B., Lattimore, T., and Deng, W. (2021).  Information directed sampling for sparse linear bandits.  Advances in Neural Information Processing Systems, 34:16738–16750.
  * Hao et al., (2022) Hao, B., Lattimore, T., and Qin, C. (2022).  Contextual information-directed sampling.  In International Conference on Machine Learning, pages 8446–8464. PMLR.
  * Jin et al., (2018) Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. (2018).  Is q-learning provably efficient?  Advances in neural information processing systems, 31.
  * Jin et al., (2020) Jin, C., Yang, Z., Wang, Z., and Jordan, M. I. (2020).  Provably efficient reinforcement learning with linear function approximation.  In Conference on Learning Theory, pages 2137–2143. PMLR.
  * Kirschner et al., (2021) Kirschner, J., Lattimore, T., Vernade, C., and Szepesvári, C. (2021).  Asymptotically optimal information-directed sampling.  In Conference on Learning Theory, pages 2777–2821. PMLR.
  * Lattimore and Gyorgy, (2021) Lattimore, T. and Gyorgy, A. (2021).  Mirror descent and the information ratio.  In Conference on Learning Theory, pages 2965–2992. PMLR.
  * Lattimore and Szepesvári, (2019) Lattimore, T. and Szepesvári, C. (2019).  An information-theoretic approach to minimax regret in partial monitoring.  In Conference on Learning Theory, pages 2111–2139. PMLR.
  * Liu et al., (2018) Liu, F., Buccapatnam, S., and Shroff, N. (2018).  Information directed sampling for stochastic bandits with graph feedback.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32.
  * Lu, (2020) Lu, X. (2020).  Information-directed sampling for reinforcement learning.  Stanford University.
  * Lu and Van Roy, (2019) Lu, X. and Van Roy, B. (2019).  Information-theoretic confidence bounds for reinforcement learning.  Advances in Neural Information Processing Systems, 32.
  * Osband et al., (2013) Osband, I., Russo, D., and Van Roy, B. (2013).  (more) efficient reinforcement learning via posterior sampling.  Advances in Neural Information Processing Systems, 26.
  * Osband and Van Roy, (2014) Osband, I. and Van Roy, B. (2014).  Model-based reinforcement learning and the eluder dimension.  Advances in Neural Information Processing Systems, 27.
  * Osband and Van Roy, (2017) Osband, I. and Van Roy, B. (2017).  Why is posterior sampling better than optimism for reinforcement learning?  In International conference on machine learning, pages 2701–2710. PMLR.
  * Osband et al., (2019) Osband, I., Van Roy, B., Russo, D. J., Wen, Z., et al. (2019).  Deep exploration via randomized value functions.  J. Mach. Learn. Res., 20(124):1–62.
  * Puterman, (2014) Puterman, M. L. (2014).  Markov decision processes: discrete stochastic dynamic programming.  John Wiley & Sons.
  * Russo, (2019) Russo, D. (2019).  Worst-case regret bounds for exploration via randomized value functions.  Advances in Neural Information Processing Systems, 32.
  * Russo and Van Roy, (2014) Russo, D. and Van Roy, B. (2014).  Learning to optimize via information-directed sampling.  Advances in Neural Information Processing Systems, 27.
  * Russo and Van Roy, (2016) Russo, D. and Van Roy, B. (2016).  An information-theoretic analysis of thompson sampling.  The Journal of Machine Learning Research, 17(1):2442–2471.
  * Sasso et al., (2023) Sasso, R., Conserva, M., and Rauber, P. (2023).  Posterior sampling for deep reinforcement learning.  arXiv preprint arXiv:2305.00477.
  * Sutton and Barto, (2018) Sutton, R. S. and Barto, A. G. (2018).  Reinforcement learning: An introduction.  MIT press.
  * Tiapkin et al., (2022) Tiapkin, D., Belomestny, D., Calandriello, D., Moulines, É., Munos, R., Naumov, A., Rowland, M., Valko, M., and Ménard, P. (2022).  Optimistic posterior sampling for reinforcement learning with few samples and tight guarantees.  Advances in Neural Information Processing Systems, 35:10737–10751.
  * Tossou et al., (2019) Tossou, A., Basu, D., and Dimitrakakis, C. (2019).  Near-optimal optimistic reinforcement learning using empirical bernstein inequalities.  arXiv preprint arXiv:1905.12425.
  * Yang and Wang, (2019) Yang, L. and Wang, M. (2019).  Sample-optimal parametric q-learning using linearly additive features.  In International Conference on Machine Learning, pages 6995–7004. PMLR.
  * Zanette et al., (2020) Zanette, A., Brandfonbrener, D., Brunskill, E., Pirotta, M., and Lazaric, A. (2020).  Frequentist regret bounds for randomized least-squares value iteration.  In International Conference on Artificial Intelligence and Statistics, pages 1954–1964. PMLR.
  * Zhang et al., (2020) Zhang, Z., Zhou, Y., and Ji, X. (2020).  Almost optimal model-free reinforcement learningvia reference-advantage decomposition.  Advances in Neural Information Processing Systems, 33:15198–15207.
  * Zhou et al., (2021) Zhou, D., Gu, Q., and Szepesvari, C. (2021).  Nearly minimax optimal reinforcement learning for linear mixture markov decision processes.  In Conference on Learning Theory, pages 4532–4576. PMLR.

##  Appendix A Proof of Lemma 1

To avoid conflict with the environment space notation
$\Theta=\Theta_{1}\times\cdots\times\Theta_{H}$, we adopt the notation
$\Theta_{k}^{\varepsilon}$ to refer to $\varepsilon-$value partitions.

#### Proof of covering number estimate.

Let
$\\{B_{h,i}^{P}(\varepsilon/(2H)^{2})\\}_{i=1}^{L_{h}^{P}(\varepsilon/(2H)^{2})},\\{B_{h,i}^{R}(\varepsilon/(4H))\\}_{i=1}^{L_{h}^{R}(\varepsilon/(4H))}$
be the $\varepsilon-$balls giving an $\varepsilon-$covering for
$\Theta_{h}^{P},\Theta_{h}^{R}$. Then define the $\varepsilon-$value partition
$\cup_{k=1}^{K}\Theta_{k}^{\varepsilon}=\Theta$ where
$K=\prod_{h}L_{h}^{P}(\varepsilon/(2H)^{2})\times L_{h}^{R}(\varepsilon/(4H))$
as follows. Each $k\in[K]$ can be enumerated as a $2H-$tuple
$(i_{1},j_{1},\ldots,i_{H},j_{H})$ where
$i_{h}\in[L_{h}^{P}(\varepsilon/(2H)^{2})],j_{h}\in[L_{h}^{R}(\varepsilon/(4H))]$.
Define $\Theta_{k}^{\varepsilon}=\\{\mathcal{E}|P_{h}^{\mathcal{E}}\in
B_{h,i_{h}}^{P}(\varepsilon/(2H)^{2}),r_{h}^{\mathcal{E}}\in
B_{h,j_{h}}^{R}(\varepsilon/(4H))\\}$. It is straightforward to check that
$\cup_{k}\Theta_{k}^{\varepsilon}=\Theta$. Any environment appearing
redundantly can be removed from all but one of the
$\Theta_{k}^{\varepsilon}$’s it lives in, so that we have a true partition of
$\Theta_{k}^{\varepsilon}$.

Next, we will need to use the following lemma.

Proving that our partition is an $\varepsilon-$value partition requires us to
show that for any
$\mathcal{E},\mathcal{E}^{\prime}\in\Theta_{k}^{\varepsilon}:V_{1,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}}(s_{1}^{\ell})-V_{1,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}^{\prime}}(s_{1}^{\ell})\leq\varepsilon$.
We have

$\displaystyle
V_{1,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}}(s_{1}^{\ell})-V_{1,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}^{\prime}}(s_{1}^{\ell})=$
$\displaystyle\sum_{h=1}^{H}\mathbb{E}_{\pi^{*}_{\mathcal{E}}}^{\mathcal{E}^{\prime}}\left[\mathbb{E}_{s^{\prime}\sim
P_{h}^{\mathcal{E}}(\cdot|s_{h},a_{h})}[V_{h+1,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}}(s^{\prime})]-\mathbb{E}_{s^{\prime}\sim
P_{h}^{\mathcal{E}^{\prime}}(\cdot|s_{h},a_{h})}[V_{h+1,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}}(s^{\prime})]\right]$
$\displaystyle\quad+\sum_{h=1}^{H}\mathbb{E}_{\pi^{*}_{\mathcal{E}}}^{\mathcal{E}^{\prime}}[r_{h}^{\mathcal{E}}(s_{h},a_{h})-r_{h}^{\mathcal{E}^{\prime}}(s_{h},a_{h})],$
(26)

Rewrite the first term and bound it as follows:

$\displaystyle\begin{split}\sum_{h=1}^{H}\mathbb{E}_{\pi^{*}_{\mathcal{E}}}^{\mathcal{E}^{\prime}}\left[\int_{\mathcal{S}}P_{h}^{\mathcal{E}}(s^{\prime}|s_{h}^{\ell},a_{h}^{\ell})V_{h+1,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}}(s^{\prime})-\int_{\mathcal{S}}P_{h}^{\mathcal{E}^{\prime}}(s^{\prime}|s_{h}^{\ell},a_{h}^{\ell})V_{h+1,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}}(s^{\prime})\right]\\\
\leq\sum_{h=1}^{H}\mathbb{E}_{\pi^{*}_{\mathcal{E}}}^{\mathcal{E}^{\prime}}\left[\left(\int_{\mathcal{S}}\Big{|}P_{h}^{\mathcal{E}}(s^{\prime}|s_{h}^{\ell},a_{h}^{\ell})-P_{h}^{\mathcal{E}^{\prime}}(s^{\prime}|s_{h}^{\ell},a_{h}^{\ell})\Big{|}V_{h+1,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}}(s^{\prime})\right)\right].\end{split}$
(27)

where integrals are with respect to the measure on ${\mathcal{S}}$. Then, we
can bound probability transitions terms by

$\displaystyle\begin{split}\sum_{h=1}^{H}&\mathbb{E}_{\pi^{*}_{\mathcal{E}}}^{\mathcal{E}^{\prime}}\left[\left(\int_{\mathcal{S}}\Big{|}P_{h}^{\mathcal{E}}(s^{\prime}|s_{h}^{\ell},a_{h}^{\ell})-P_{h}^{\mathcal{E}^{\prime}}(s^{\prime}|s_{h}^{\ell},a_{h}^{\ell})\Big{|}V_{h+1,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}}(s^{\prime})\right)\right]\\\
&\leq
H\sum_{h=1}^{H}\mathbb{E}_{\pi^{*}_{\mathcal{E}}}^{\mathcal{E}^{\prime}}\left[\int_{\mathcal{S}}\Big{|}P_{h}^{\mathcal{E}}(s^{\prime}|s_{h}^{\ell},a_{h}^{\ell})-P_{h}^{\mathcal{E}^{\prime}}(s^{\prime}|s_{h}^{\ell},a_{h}^{\ell})\Big{|}\right]\\\
&\leq
H\sum_{h=1}^{H}\sup_{s,a}\left(\int_{\mathcal{S}}\Big{|}P_{h}^{\mathcal{E}}(s^{\prime}|s,a)-P_{h}^{\mathcal{E}^{\prime}}(s^{\prime}|s,a)\Big{|}\right)\\\
&=H\sum_{h=1}^{H}l_{1}(P_{h}^{\mathcal{E}},P_{h}^{\mathcal{E}^{\prime}})\leq
H(2\frac{\varepsilon}{4H^{2}}\cdot H)\end{split}$ (28)

and similarly, reward terms by

$\displaystyle\begin{split}\sum_{h=1}^{H}E_{\pi^{*}_{\mathcal{E}}}^{\mathcal{E}^{\prime}}[r_{h}^{\mathcal{E}}(s_{h}^{\ell},a_{h}^{\ell})-r_{h}^{\mathcal{E}^{\prime}}(s_{h}^{\ell},a_{h}^{\ell})]&=\sum_{h=1}^{H}E_{\pi^{*}_{\mathcal{E}}}^{\mathcal{E}^{\prime}}\left[\int_{0}^{1}x\left(r_{h}^{\mathcal{E}}(x|s_{h}^{\ell},a_{h}^{\ell})-r_{h}^{\mathcal{E}^{\prime}}(x|s_{h}^{\ell},a_{h}^{\ell})\right)\operatorname{d}\\!x\right]\\\
&\leq\sum_{h=1}^{H}E_{\pi^{*}_{\mathcal{E}}}^{\mathcal{E}^{\prime}}\left[\int_{0}^{1}\Big{|}x\left(r_{h}^{\mathcal{E}}(x|s_{h}^{\ell},a_{h}^{\ell})-r_{h}^{\mathcal{E}^{\prime}}(x|s_{h}^{\ell},a_{h}^{\ell})\right)\Big{|}\operatorname{d}\\!x\right]\\\
&\leq\sum_{h=1}^{H}\sup_{s,a}\int_{0}^{1}\Big{|}x\left(r_{h}^{\mathcal{E}}(x|s,a)-r_{h}^{\mathcal{E}^{\prime}}(x|s,a)\right)\Big{|}\operatorname{d}\\!x\\\
&=\sum_{h=1}^{H}l_{1}(r_{h}^{\mathcal{E}},r_{h}^{\mathcal{E}^{\prime}})\leq
H(2\frac{\varepsilon}{4H})\end{split}$ (29)

See also Remark 7 for the reward term bound. In the first inequality, we used
that $V_{h+1,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}}(s^{\prime})$ is always
bounded by $H$, and in both cases we used the fact that the transition and
reward functions of $\mathcal{E},\mathcal{E}^{\prime}$ live inside the same
balls, with their $l_{1}$ distance being at most twice the radii
$\varepsilon/(2H)^{2}$ and $\varepsilon/(4H)$, respectively. Adding up the
above two estimates equals $\varepsilon$, as desired. This shows that our
$\Theta_{k}^{\varepsilon}$ partition is an $\varepsilon-$value partition,
hence $K_{\operatorname{surr}}(\varepsilon)\leq
K=\prod_{h}L_{h}^{P}(\varepsilon/(2H)^{2})\times L_{h}^{R}(\varepsilon/(4H))$.

######  Remark 7.

Notice that the $l_{1}-$distance of two reward functions is over their
probability distributions, and is larger than their expected norm difference,
i.e.,

$\displaystyle l_{1}(r,r^{\prime})$
$\displaystyle=\sup_{s,a\in{\mathcal{S}}\times\mathcal{A}}||r(\cdot|s,a)-r^{\prime}(\cdot|s,a)||_{1}=\sup_{s,a\in{\mathcal{S}}\times\mathcal{A}}\int_{0}^{1}|r(x|s,a)-r^{\prime}(x|s,a)|$
$\displaystyle\geq\sup_{s,a\in{\mathcal{S}}\times\mathcal{A}}\int_{0}^{1}x|r(x|s,a)-r^{\prime}(x|s,a)|=\sup_{s,a\in{\mathcal{S}}\times\mathcal{A}}\mathbb{E}[|r(s,a)-r^{\prime}(s,a)|].$
(30)

#### Proof of $d_{\operatorname{surr}}\leq d_{l_{1}}$.

By taking the log, dividing by $\log(1/\varepsilon)$, and taking the $\limsup$
of both sides of this inequality, we can infer the second statement of the
lemma:

$\displaystyle\begin{split}d_{\operatorname{surr}}&=\limsup_{\varepsilon\to
0}\frac{\log(K_{\operatorname{surr}}(\varepsilon))}{\log(1/\varepsilon)}\\\
&\leq\sum_{h=1}^{H}\limsup_{\varepsilon\to
0}\frac{\log(L_{h}^{P}(\varepsilon/(2H)^{2}))}{\log(\frac{1}{\varepsilon/(2H)^{2}})}\cdot\frac{1}{1+\log((2H)^{2})/\log(\varepsilon/(2H)^{2})}+\\\
&\quad\sum_{h=1}^{H}\limsup_{\varepsilon\to
0}\frac{\log(L_{h}^{R}(\varepsilon/(4H)))}{\log(\frac{1}{\varepsilon/(2H)^{2}})}\cdot\frac{1}{1+\log(4H)/\log(\varepsilon/(4H))}\\\
&=\sum_{h}d_{l_{1},h}^{P}+\sum_{h}d_{l_{1},h}^{R}=d_{l_{1}}.\end{split}$ (31)

######  Fact 1.

We separate the statement proved in Eqs. 28 and 29 as fact, useful for future
use: for all $\mathcal{E},\mathcal{E}^{\prime}\in\Theta$,

$\displaystyle
V_{1,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}}(s_{1}^{\ell})-V_{1,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}^{\prime}}(s_{1}^{\ell})\leq
H\sum_{h=1}^{H}l_{1}(P_{h}^{\mathcal{E}},P_{h}^{\mathcal{E}^{\prime}})+\sum_{h=1}^{H}l_{1}(r_{h}^{\mathcal{E}},r_{h}^{\mathcal{E}^{\prime}})\,.$
(32)

##  Appendix B Proof of Lemma 2

While we follow the proof of the same lemma in (Hao and Lattimore,, 2022, App.
B.1), we will need to correct some mistakes. Let us restate the equation of
the statement:

######  Lemma.

For any $\varepsilon-$value partition and any $\ell\in[L]$, there are random
environments $\tilde{\mathcal{E}}^{*}_{\ell}\in\Theta$ with their laws only
depending on $\zeta,\mathcal{D}_{\ell}$, such that

$\displaystyle\mathbb{E}_{\ell}\left[V_{1,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}}(s_{1}^{\ell})-V_{1,\pi^{\ell}_{\text{TS}}}^{\mathcal{E}}(s_{1}^{\ell})\right]-\mathbb{E}_{\ell}\left[V_{1,\pi^{*}_{\mathcal{E}}}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s_{1}^{\ell})-V_{1,\pi^{\ell}_{\text{TS}}}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s_{1}^{\ell})\right]\leq\varepsilon\,.$
(33)

###### Proof.

Assume a partition $\Theta_{k}^{\varepsilon}$ satisfying Definition 8 with
error $\varepsilon$ exists. Let $\mathcal{E}_{\ell}\sim
P(\cdot|\mathcal{D}_{\ell})$. We want to decompose
$\mathbb{E}_{\ell}\left[V_{1,\pi^{\ell}_{\text{TS}}}^{\mathcal{E}_{\ell}}(s_{1}^{\ell})\big{|}\mathcal{E}_{\ell}\in\Theta_{k}^{\varepsilon}\right]$,
where the expectation is over all
$\mathcal{E}_{\ell}\in\Theta_{k}^{\varepsilon}$ and all
$\pi^{\ell}_{\text{TS}}=\pi^{*}_{\mathcal{E}^{\prime}_{\ell}}$ , where
$\mathcal{E}^{\prime}_{\ell}\in\Theta$, with $\mathcal{E}^{\prime}_{\ell}$
independent of $\mathcal{E}_{\ell}$. We decompose this by writing the
expectation only over the former.

$\begin{split}\mathbb{E}_{\ell}\left[V_{1,\pi^{\ell}_{\text{TS}}}^{\mathcal{E}_{\ell}}(s_{1}^{\ell})\big{|}\mathcal{E}_{\ell}\in\Theta_{k}^{\varepsilon}\right]&=\int_{\mathcal{E}_{0}\in\Theta_{k}^{\varepsilon}}\mathbb{P}\left(\mathcal{E}_{\ell}=\mathcal{E}_{0}|\mathcal{E}_{\ell}\in\Theta_{k}^{\varepsilon}\right)\mathbb{E}_{\ell}\left[V_{1,\pi^{\ell}_{\text{TS}}}^{\mathcal{E}_{0}}(s_{1}^{\ell})\big{|}\mathcal{E}_{\ell}\in\Theta_{k}^{\varepsilon}\right]\operatorname{d}\\!\rho(\mathcal{E}_{0})\\\
&=\int_{\mathcal{E}_{0}\in\Theta_{k}^{\varepsilon}}\mathbb{P}\left(\mathcal{E}_{\ell}=\mathcal{E}_{0}|\mathcal{E}_{\ell}\in\Theta_{k}^{\varepsilon}\right)\mathbb{E}_{\ell}\left[V_{1,\pi^{\ell}_{\text{TS}}}^{\mathcal{E}_{0}}(s_{1}^{\ell})\right]\operatorname{d}\\!\rho(\mathcal{E}_{0})\,,\end{split}$
(34)

where the last equation is due to the independence between
$\mathcal{E}_{\ell}$ and $\mathcal{E}_{\ell}^{\prime}$.

We would like to find some $\tilde{\mathcal{E}}_{k,\ell}^{*}$ such that its
corresponding expected value is smaller than the integral above, i.e.

$\displaystyle\mathbb{E}_{\ell}\left[V_{1,\pi^{\ell}_{\text{TS}}}^{\tilde{\mathcal{E}}_{k,\ell}^{*}}(s_{1}^{\ell})\right]\leq\int_{\mathcal{E}_{0}\in\Theta_{k}^{\varepsilon}}\mathbb{P}\left(\mathcal{E}_{\ell}=\mathcal{E}_{0}|\mathcal{E}_{\ell}\in\Theta_{k}^{\varepsilon}\right)\mathbb{E}_{\ell}\left[V_{1,\pi^{\ell}_{\text{TS}}}^{\mathcal{E}_{0}}(s_{1}^{\ell})\right]\operatorname{d}\\!\rho(\mathcal{E}_{0})$
(35)

We set values of this random variable as
$\tilde{\mathcal{E}}^{*}_{k,\ell}=\mathbb{E}_{\ell}[\mathcal{E}|\mathcal{E}\in\Theta_{k}^{\varepsilon}],\forall
k\in[K_{\operatorname{surr}}(\varepsilon)]$. In other words, the posterior
mean over $\Theta_{k}^{\varepsilon}$. Now, we can define a new random
environment $\tilde{\mathcal{E}}_{\ell}^{*}$ which prior can be easily
computed as
$\mathbb{P}_{\ell}\left(\tilde{\mathcal{E}}_{\ell}^{*}=\tilde{\mathcal{E}}_{k,\ell}^{*}\right)=\mathbb{P}_{\ell}(\mathcal{E}\in\Theta_{k}^{\varepsilon})$
and $\zeta(\tilde{\mathcal{E}}^{*}_{k,\ell})=k$. Note the law of
$\tilde{\mathcal{E}}_{\ell}^{*}$ only depends on $\zeta\in[K]$ and
$\mathcal{D}_{\ell}$, and conditional on $\zeta$,
$\tilde{\mathcal{E}}_{\ell}^{*}$ is independent of $\mathcal{E}$, as desired.
While this definition of $\tilde{\mathcal{E}}^{*}_{\ell}$ may not be in
$\Theta$, that is fine as we do not use this condition in our proof (see also
Remark 8).

Notice that as a result, the overall posterior mean of
$\bar{\mathcal{E}}^{*}_{\ell}:=\mathbb{E}_{\ell}[\tilde{\mathcal{E}}^{*}_{\ell}]$
coincides with $\bar{\mathcal{E}}_{\ell}$. Also note that by this definition
of $\tilde{\mathcal{E}}^{*}_{k,\ell}$, and the independence over layers even
after conditioning on $\Theta^{\varepsilon}_{k}$, the mean
$\mathbb{E}_{\ell}[V_{1,\pi^{\ell}_{\text{TS}}}^{\tilde{\mathcal{E}}_{k,\ell}^{*}}(s_{1}^{\ell})]$
is in fact equal to the mean on the right hand side of Eq. 35, thus our
construction is sharp in that it satisfies this inequality with an equality.

Now, we are ready to make the connection with Eq. 11, showing that solving the
surrogate environment problem is ‘almost the same’ as solving the original
problem, up to some $\varepsilon$. Integrating over the different values of
$k$ with prior $\mathbb{P}_{\ell}(\mathcal{E}\in\Theta_{k}^{\varepsilon})$,

$\displaystyle\mathbb{E}_{\ell}\left[V_{1,\pi^{\ell}_{\text{TS}}}^{\tilde{\mathcal{E}}^{*}_{\ell}}(s_{1}^{\ell})\right]\leq\mathbb{E}_{\ell}\left[V_{1,\pi^{\ell}_{\text{TS}}}^{\mathcal{E}}(s_{1}^{\ell})\right]\implies\mathbb{E}_{\ell}\left[V_{1,\pi^{\ell}_{\text{TS}}}^{\tilde{\mathcal{E}}^{*}_{\ell}}(s_{1}^{\ell})\right]-\mathbb{E}_{\ell}\left[V_{1,\pi^{\ell}_{\text{TS}}}^{\mathcal{E}}(s_{1}^{\ell})\right]\leq
0$ (36)

Lastly, by the partition property,

$\displaystyle\mathbb{E}_{\ell}\left[V_{1,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}}(s_{1}^{\ell})-V_{1,\pi^{*}_{\mathcal{E}}}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s_{1}^{\ell})\right]\leq\varepsilon\,.$
(37)

where in the expectation above,
$\zeta(\tilde{\mathcal{E}}_{\ell}^{*})=\zeta(\mathcal{E})$, i.e.,
$\mathcal{E}$ and $\tilde{\mathcal{E}}^{*}_{\ell}$ are clearly independent
only after conditioning on $\zeta=k$, as also required in Eq. 11. Adding the
above two inequalities gives

$\displaystyle\mathbb{E}_{\ell}\left[V_{1,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}}(s_{1}^{\ell})-V_{1,\pi^{\ell}_{\text{TS}}}^{\mathcal{E}}(s_{1}^{\ell})\right]-\mathbb{E}_{\ell}\left[V_{1,\pi^{*}_{\mathcal{E}}}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s_{1}^{\ell})-V_{1,\pi^{\ell}_{\text{TS}}}^{\tilde{\mathcal{E}}^{*}_{\ell}}(s_{1}^{\ell})\right]\leq\varepsilon$
(38)

finishing the proof. Notice that Eq. 37 is the only place where the property
of $\varepsilon-$value partitioning is used. ∎

######  Remark 8.

We note that if $\tilde{\mathcal{E}}^{*}_{\ell}$ is any convex combination of
environments in $\Theta_{\zeta(\mathcal{E})}$, then by the $\varepsilon-$value
partition property
$\mathbb{E}_{\ell}[V_{1,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}}(s_{1}^{\ell})-V_{1,\pi^{*}_{\mathcal{E}}}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s_{1}^{\ell})]\leq\varepsilon$.
The distinct property that surrogate environments satisfy is

$\displaystyle\mathbb{E}_{\ell}[V_{1,\pi^{\ell}_{\text{TS}}}^{\tilde{\mathcal{E}}_{k,\ell}^{*}}(s_{1}^{\ell})]\leq\mathbb{E}_{\ell}[V_{1,\pi^{\ell}_{\text{TS}}}^{\mathcal{E}}(s_{1}^{\ell})|\mathcal{E}\in\Theta_{k}^{\varepsilon}],\
\forall k\in[K].$ (39)

and therefore, satisfy Eq. 33.

######  Remark 9.

For the purpose of fully addressing the issue present in Hao and Lattimore,
(2022) in proving the above lemma, we show an alternative construction which
does not assume a layered $\varepsilon-$value partition. One can always find a
decreasing sequence
$\mathbb{E}_{\ell}\left[V_{1,\pi^{\ell}_{\text{TS}}}^{\mathcal{E}^{1}}(s_{1}^{\ell})\right]\geq\mathbb{E}_{\ell}\left[V_{1,\pi^{\ell}_{\text{TS}}}^{\mathcal{E}^{2}}(s_{1}^{\ell})\right]\geq\ldots$
with limit
$\inf_{\mathcal{E}_{0}\in\Theta_{k}^{\varepsilon}}\mathbb{E}_{\ell}\left[V_{1,\pi^{\ell}_{\text{TS}}}^{\mathcal{E}_{0}}(s_{1}^{\ell})\right]$.
Then we claim there exists some $J$ such that the above inequality is true for
$\tilde{\mathcal{E}}_{k,\ell}^{*}=\mathcal{E}^{J}$. Otherwise, we have

$\displaystyle\mathbb{E}_{\ell}\left[V_{1,\pi^{\ell}_{\text{TS}}}^{\mathcal{E}^{i}}(s_{1}^{\ell})\right]>\int_{\mathcal{E}_{0}\in\Theta_{k}^{\varepsilon}}\mathbb{P}\left(\mathcal{E}_{\ell}=\mathcal{E}_{0}|\mathcal{E}_{\ell}\in\Theta_{k}^{\varepsilon}\right)\mathbb{E}_{\ell}\left[V_{1,\pi^{\ell}_{\text{TS}}}^{\mathcal{E}_{0}}(s_{1}^{\ell})\right]\operatorname{d}\\!\rho(\mathcal{E}_{0})$
(40)

for all $i$. Taking the limit $i\to\infty$, we get

$\displaystyle\inf_{\mathcal{E}_{0}\in\Theta_{k}^{\varepsilon}}\mathbb{E}_{\ell}\left[V_{1,\pi^{\ell}_{\text{TS}}}^{\mathcal{E}_{0}}(s_{1}^{\ell})\right]\geq\int_{\mathcal{E}_{0}\in\Theta_{k}^{\varepsilon}}\mathbb{P}\left(\mathcal{E}_{\ell}=\mathcal{E}_{0}|\mathcal{E}_{\ell}\in\Theta_{k}^{\varepsilon}\right)\mathbb{E}_{\ell}\left[V_{1,\pi^{\ell}_{\text{TS}}}^{\mathcal{E}_{0}}(s_{1}^{\ell})\right]\operatorname{d}\\!\rho(\mathcal{E}_{0})$
(41)

which can only be true if
$\mathbb{E}_{\ell}\left[V_{1,\pi^{\ell}_{\text{TS}}}^{\mathcal{E}_{0}}(s_{1}^{\ell})\right]=\inf_{\mathcal{E}_{0}\in\Theta_{k}^{\varepsilon}}\mathbb{E}_{\ell}\left[V_{1,\pi^{\ell}_{\text{TS}}}^{\mathcal{E}_{0}}(s_{1}^{\ell})\right]$
almost everywhere. Any $\mathcal{E}_{0}$ satisfying this equality would also
satisfy our requirement for $\tilde{\mathcal{E}}_{k,\ell}^{*}$. It is
important to note that $\tilde{\mathcal{E}}_{k,\ell}^{*}$ depends on both $k$
and $\mathcal{D}_{\ell}$, as mentioned in the lemma’s statement. The finishes
the construction of $\tilde{\mathcal{E}}_{\ell}^{*}$ and the rest follows
similar to the above proof.

######  Remark 10 (Incorrect proof by Hao and Lattimore, (2022) of the lemma).

Eq. 34 is different from what appears in (Hao and Lattimore,, 2022, App. B.1),
where we have corrected for the abuse of notation of $\mathcal{E}$ occurring
in e.g.
“$\mathbb{P}\left(\mathcal{E}_{\ell}=\mathcal{E}|\mathcal{E}_{\ell}\in\Theta_{k}^{\varepsilon}\right)\mathbb{E}_{\ell}\left[V_{1,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}}(s_{1}^{\ell})\right]$”.
We further note the use of summation over
$\mathcal{E}\in\Theta_{k}^{\varepsilon}$ in their equation, instead of an
integral which is required even in the tabular case. This is not easily fixed
by just replacing sum with integral, since the application of (Hao and
Lattimore,, 2022, Lemma D.1) used afterwards in their proof depends on having
a finite sum. We mention this lemma below:

(Lemma 1 in Dong and Van Roy, (2018)) Let $\\{a_{i}\\}_{i=1}^{N}$ and
$\\{b_{i}\\}_{i=1}^{N}$ be two sequences of real numbers, where $N<\infty$.
Let $\\{p_{i}\\}_{i=1}^{N}$ be such that $p_{i}\geq 0$ for all $i$ and
$\sum_{i=1}^{N}p_{i}=1$. Then there exists indices $j,k\in[N]$ and $r\in[0,1]$
such that

$ra_{j}+(1-r)a_{k}\leq\sum_{i=1}^{N}a_{i}p_{i},rb_{j}+(1-r)b_{k}\leq\sum_{i=1}^{L}b_{i}p_{i}\,.$

The application of this lemma is key to the proof as the authors cite it to
find the right surrogate environments that satisfy Eq. 39. However, even in
this application, it is not clear what exactly is the ‘second’ set of numbers
($b_{j}$ above), as is required for that Lemma to be a nontrivial result,
which makes its usage even more questionable.

##  Appendix C Proof of Theorem 3

We restate the theorem for ease of reference as it contains multiple
statements.

######  Theorem.

Given a Bayesian RL problem, we have

$\displaystyle\mathfrak{BR}_{L}(\pi_{\text{TS}})\leq\inf_{\varepsilon>0}\left(\lambda\sqrt{\log(K_{\operatorname{surr}}(\varepsilon))T}+L\varepsilon\right)+T_{0}$
(42)

where $T_{0}$ does not depend on $T$. This can be further upper bounded by

$\displaystyle\mathfrak{BR}_{L}(\pi_{\text{TS}})\leq\widetilde{O}(\lambda\sqrt{d_{l_{1}}T})\,.$
(43)

for large enough $T$. Given a homogeneous $l_{1}$ dimension
$d_{\operatorname{hom}}=d_{l_{1},h},\forall h$, this simplifies to

$\displaystyle\mathfrak{BR}_{L}(\pi_{\text{TS}})\leq\widetilde{O}(\lambda\sqrt{Hd_{\operatorname{hom}}T})\,.$
(44)

###### Proof.

The proof starts by employing the surrogate environment learning bound from
Appendix B:

$\displaystyle\mathbb{E}_{\ell}\left[V_{1,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}}(s_{1}^{\ell})-V_{1,\pi^{\ell}_{\text{TS}}}^{\mathcal{E}}(s_{1}^{\ell})\right]-\varepsilon\leq\mathbb{E}_{\ell}\left[V_{1,\pi^{*}_{\mathcal{E}}}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s_{1}^{\ell})-V_{1,\pi^{\ell}_{\text{TS}}}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s_{1}^{\ell})\right]\,.$
(45)

We have

$\displaystyle\begin{split}\mathfrak{BR}_{L}(\pi_{\text{TS}})&=\sum_{\ell=1}^{L}\mathbb{E}\left[\mathbb{E}_{\ell}\left[V_{1,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}}(s_{1}^{\ell})-V_{1,\pi^{\ell}_{\text{TS}}}^{\mathcal{E}}(s_{1}^{\ell})\right]\right]\\\
&=\sum_{\ell=1}^{L}\mathbb{E}\left[\mathbb{E}_{\ell}\left[V_{1,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}}(s_{1}^{\ell})-V_{1,\pi^{\ell}_{\text{TS}}}^{\mathcal{E}}(s_{1}^{\ell})\right]-\varepsilon\right]+L\varepsilon\\\
&=\sum_{\ell=1}^{L}\mathbb{E}\left[\mathbb{E}_{\ell}\left[V_{1,\pi^{*}_{\mathcal{E}}}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s_{1}^{\ell})-V_{1,\pi^{\ell}_{\text{TS}}}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s_{1}^{\ell})\right]\right]+L\varepsilon\end{split}$
(46)

Given that $\pi^{\ell}_{\text{TS}}$ is independent from
$\tilde{\mathcal{E}}^{*}_{\ell}$ and the independence of the latter’s prior
over different layers (due to the layered $\varepsilon-$value partition), we
observe that
$\mathbb{E}_{\ell}[V_{1,\pi^{\ell}_{\text{TS}}}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s_{1}^{\ell})]=\mathbb{E}_{\ell}[V_{1,\pi^{\ell}_{\text{TS}}}^{\bar{\mathcal{E}}_{\ell}^{*}}(s_{1}^{\ell})]$.
Again, since $\pi^{\ell}_{\text{TS}}$ is also independent from
$\bar{\mathcal{E}}^{*}_{\ell}$, and that $\pi^{\ell}_{\text{TS}}$ and
$\mathcal{E}$ have the same laws conditional on $\mathcal{D}_{\ell}$, we can
rewrite the latter as
$\mathbb{E}_{\ell}[V_{1,\pi^{*}_{\mathcal{E}}}^{\bar{\mathcal{E}}_{\ell}^{*}}(s_{1}^{\ell})]$.
This comes with the obvious note that $\bar{\mathcal{E}}_{\ell}^{*}$ and
$\mathcal{E}$ are independent, in contrast to $\tilde{\mathcal{E}}^{*}_{\ell}$
and $\mathcal{E}$ that are dependent through $\zeta$. This allows us to
rewrite

$\displaystyle\begin{split}\mathbb{E}_{\ell}\left[V_{1,\pi^{*}_{\mathcal{E}}}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s_{1}^{\ell})-V_{1,\pi^{\ell}_{\text{TS}}}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s_{1}^{\ell})\right]&=\mathbb{E}_{\ell}\left[V_{1,\pi^{*}_{\mathcal{E}}}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s_{1}^{\ell})-V_{1,\pi^{*}_{\mathcal{E}}}^{\bar{\mathcal{E}}_{\ell}^{*}}(s_{1}^{\ell})\right]\end{split}$
(47)

Due to our construction of $\bar{\mathcal{E}}^{*}_{\ell}$ in Appendix B, we
can substitute
$\bar{\mathcal{E}}^{*}_{\ell}=\bar{\mathcal{E}}_{\ell}=\mathbb{E}_{\ell}[\mathcal{E}]$.
Using Lemma 8, we can rewrite the above mean as

$\displaystyle\begin{split}=\sum_{h=1}^{H}\mathbb{E}_{\ell}&\left[\mathbb{E}_{\pi^{*}_{\mathcal{E}}}^{\bar{\mathcal{E}}_{\ell}}\left[\mathbb{E}_{(s^{\prime},r^{\prime})\sim(P_{h}^{\tilde{\mathcal{E}}_{\ell}^{*}}\otimes
r_{h}^{\tilde{\mathcal{E}}_{\ell}^{*}})(\cdot|s_{h},a_{h})}[r^{\prime}+V_{h+1,\pi^{*}_{\mathcal{E}}}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s^{\prime})]\right.\right.\\\
&\qquad\qquad\left.\left.-\mathbb{E}_{(s^{\prime},r^{\prime})\sim(P_{h}^{\bar{\mathcal{E}}_{\ell}}\otimes
r_{h}^{\bar{\mathcal{E}}_{\ell}})(\cdot|s_{h},a_{h})}[r^{\prime}+V_{h+1,\pi^{*}_{\mathcal{E}}}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s^{\prime})]\right]\right]\,.\end{split}$
(48)

Denoting

$\displaystyle\Delta_{h}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s_{h},a_{h})$
$\displaystyle:=\mathbb{E}_{(s^{\prime},r^{\prime})\sim(P_{h}^{\tilde{\mathcal{E}}_{\ell}^{*}}\otimes
r_{h}^{\tilde{\mathcal{E}}_{\ell}^{*}})(\cdot|s_{h},a_{h})}[r^{\prime}+V_{h+1,\pi^{*}_{\mathcal{E}}}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s^{\prime})]$
$\displaystyle\quad-\mathbb{E}_{(s^{\prime},r^{\prime})\sim(P_{h}^{\bar{\mathcal{E}}_{\ell}}\otimes
r_{h}^{\bar{\mathcal{E}}_{\ell}})(\cdot|s_{h},a_{h})}[r^{\prime}+V_{h+1,\pi^{*}_{\mathcal{E}}}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s^{\prime})],$
(49)

we have

$\displaystyle=\sum_{h=1}^{H}\mathbb{E}_{\ell}\left[\int_{s,a}d_{h,\pi^{*}_{\mathcal{E}}}^{\bar{\mathcal{E}}_{\ell}}(s,a)\Delta_{h}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s,a)\operatorname{d}\\!\mu_{{\mathcal{S}}\times\mathcal{A}}\right]\,.$
(50)

Let
$\mathcal{B}_{\ell}:=\\{(s,a,h)\mid\mathbb{E}_{\ell}\left[d_{h,\pi^{*}_{\mathcal{E}}}^{\bar{\mathcal{E}}_{\ell}}(s,a)\right]\neq
0\\}$ and let $\int_{(s,a,h)}:=\sum_{h}\int_{(s,a)}$ denote the integral over
the space $[H]\times{\mathcal{S}}\times\mathcal{A}$ where we use the product
of counting measure on $[H]$ and $\mu_{{\mathcal{S}}\times\mathcal{A}}$. We
apply Cauchy-Schwarz inequality using the similar technique in (Hao and
Lattimore,, 2022, App. A.2), which we modify to include the value diameter
(Definition 9). Since $\Delta_{h}^{\tilde{\mathcal{E}}^{*}_{\ell}}(s,a)\leq
2H$, we have

$\displaystyle\mathbb{E}_{\ell}\left[\int_{(s,a,h)}d_{h,\pi^{*}}^{\bar{\mathcal{E}}_{\ell}}(s,a)\Delta_{h}^{\tilde{\mathcal{E}}^{*}_{\ell}}(s,a)\right]$
$\displaystyle=\mathbb{E}_{\ell}\left[\int_{(s,a,h)\notin\mathcal{B}_{\ell}}d_{h,\pi^{*}}^{\bar{\mathcal{E}}_{\ell}}(s,a)\Delta_{h}^{\tilde{\mathcal{E}}^{*}_{\ell}}(s,a)\right]+\mathbb{E}_{\ell}\left[\int_{(s,a,h)\in\mathcal{B}_{\ell}}d_{h,\pi^{*}}^{\bar{\mathcal{E}}_{\ell}}(s,a)\Delta_{h}^{\tilde{\mathcal{E}}^{*}_{\ell}}(s,a)\right]$
$\displaystyle\leq
2H\mathbb{E}_{\ell}\left[\int_{(s,a,h)\notin\mathcal{B}_{\ell}}d_{h,\pi^{*}}^{\bar{\mathcal{E}}_{\ell}}(s,a)\right]+\mathbb{E}_{\ell}\left[\int_{(s,a,h)\in\mathcal{B}_{\ell}}d_{h,\pi^{*}}^{\bar{\mathcal{E}}_{\ell}}(s,a)\Delta_{h}^{\tilde{\mathcal{E}}^{*}_{\ell}}(s,a)\right]$
$\displaystyle=\mathbb{E}_{\ell}\left[\int_{(s,a,h)\in\mathcal{B}_{\ell}}d_{h,\pi^{*}}^{\bar{\mathcal{E}}_{\ell}}(s,a)\Delta_{h}^{\tilde{\mathcal{E}}^{*}_{\ell}}(s,a)\right]$
$\displaystyle=\mathbb{E}_{\ell}\left[\int_{(s,a,h)\in\mathcal{B}_{\ell}}\frac{\lambda_{\mathcal{E}}d_{h,\pi^{*}}^{\bar{\mathcal{E}}_{\ell}}(s,a)}{\mathbb{E}_{\ell}\left[d_{h,\pi^{*}}^{\bar{\mathcal{E}}_{\ell}}(s,a)\right]^{1/2}}\mathbb{E}_{\ell}\left[d_{h,\pi^{*}}^{\bar{\mathcal{E}}_{\ell}}(s,a)\right]^{1/2}\frac{\Delta_{h}^{\tilde{\mathcal{E}}^{*}_{\ell}}(s,a)}{\lambda_{\mathcal{E}}}\right]$
$\displaystyle\leq\left(\mathbb{E}_{\ell}\left[\int_{(s,a,h)\in\mathcal{B}_{\ell}}\frac{(\lambda_{\mathcal{E}}d_{h,\pi^{*}}^{\bar{\mathcal{E}}_{\ell}}(s,a))^{2}}{\mathbb{E}_{\ell}\left[d_{h,\pi^{*}}^{\bar{\mathcal{E}}_{\ell}}(s,a)\right]}\right]\right)^{1/2}$
$\displaystyle\qquad\qquad\qquad\qquad\left(\mathbb{E}_{\ell}\left[\int_{(s,a,h)\in\mathcal{B}_{\ell}}\mathbb{E}_{\ell}\left[d_{h,\pi^{*}}^{\bar{\mathcal{E}}_{\ell}}(s,a)\right](\frac{\Delta_{h}^{\tilde{\mathcal{E}}^{*}_{\ell}}(s,a)}{\lambda_{\mathcal{E}}})^{2}\right]\right)^{1/2}$
$\displaystyle\leq\left(\int_{(s,a,h)\in\mathcal{B}_{\ell}}\frac{\mathbb{E}_{\ell}\left[(\lambda_{\mathcal{E}}d_{h,\pi^{*}}^{\bar{\mathcal{E}}_{\ell}}(s,a))^{2}\right]}{\mathbb{E}_{\ell}\left[d_{h,\pi^{*}}^{\bar{\mathcal{E}}_{\ell}}(s,a)\right]}\right)^{1/2}\left(\mathbb{E}_{\ell}\left[\int_{(s,a,h)}\mathbb{E}_{\ell}\left[d_{h,\pi^{*}}^{\bar{\mathcal{E}}_{\ell}}(s,a)\right](\frac{\Delta_{h}^{\tilde{\mathcal{E}}^{*}_{\ell}}(s,a)}{\lambda_{\mathcal{E}}})^{2}\right]\right)^{1/2}$
$\displaystyle=\sqrt{{\mathcal{T}}^{\ell}\cdot\mathcal{I}^{\ell}},$

where we used ${\mathcal{T}}^{\ell}$ and $\mathcal{I}^{\ell}$ to denote the
first and the second term respectively.

Note that the total regret of each episode is at most $H$. Therefore, going
back to the Bayesian regret formulationa and using Cauchy-Schwarz, we get

$\displaystyle\mathfrak{BR}_{L}(\pi_{\text{TS}})$
$\displaystyle\leq\mathbb{E}\left[\sum_{\ell=L_{0}+1}^{L}\sqrt{{\mathcal{T}}^{\ell}\cdot\mathcal{I}^{\ell}}\right]+L_{0}H+L\varepsilon$
(51)
$\displaystyle\leq\mathbb{E}\left[(\sum_{\ell=L_{0}+1}^{L}{\mathcal{T}}^{\ell})^{1/2}\cdot(\sum_{\ell=L_{0}+1}^{L}\mathcal{I}^{\ell})^{1/2}\right]+L_{0}H+L\varepsilon$
(52)
$\displaystyle\leq\sqrt{\mathbb{E}\left[\sum_{\ell=L_{0}+1}^{L}{\mathcal{T}}^{\ell}\right]\cdot\mathbb{E}\left[\sum_{\ell=L_{0}+1}^{L}\mathcal{I}^{\ell}\right]}+L_{0}H+L\varepsilon$
(53) $\displaystyle\leq\sqrt{L\left(\sup_{L_{0}+1\leq\ell\leq
L}\mathbb{E}\left[{\mathcal{T}}^{\ell}\right]\right)\cdot\mathbb{E}\left[\sum_{\ell=1}^{L}\mathcal{I}^{\ell}\right]}+L_{0}H+L\varepsilon,$
(54)

for every $0\leq L_{0}<L$. We estimate each term separately in Appendix E and
Appendix D.

######  Remark 11.

While the spirit of the argument, in applying surrogate learning coupled with
information ratio and Cauchy Schwarz is similar to Hao and Lattimore, (2022),
the technical aspects are different for estimating
$\sum_{\ell}\mathcal{I}^{\ell}$, and more importantly, the entire analysis is
different for $\sum_{\ell}{\mathcal{T}}^{\ell}$, as can be observed in what
follows.

We gather the results to finish the proof. In Appendix D, we show that
$\mathbb{E}[\sum_{\ell}\mathcal{I}^{\ell}]\leq\frac{1}{2}\log(K_{\operatorname{surr}}(\varepsilon))$.

In Appendix E, we show that
$\limsup\mathbb{E}\left[{\mathcal{T}}^{\ell}\right]$ is bounded by
$\lambda^{2}H$. Thus $\sup_{L_{0}+1\leq\ell\leq
L}\mathbb{E}\left[{\mathcal{T}}^{\ell}\right]\leq 2\lambda^{2}H$ for large
enough $L_{0}>0$. Hence,

$\displaystyle\mathfrak{BR}_{L}(\pi_{\text{TS}})\leq\lambda\sqrt{\log(K_{\operatorname{surr}}(\varepsilon))T}+L\varepsilon+T_{0}$
(55)

for all $\varepsilon>0$, where $T_{0}=L_{0}H$. Taking the infimum over
$\varepsilon$ gives the desired regret bound. The next statement of the
theorem in Eq. 43 is an application of Lemma 1 followed by selecting
$\varepsilon=1/L$. Notice that due to nonzero $\varepsilon$ effects,
polylogarithmic terms in $H,L$ are picked up when comparing $d_{l_{1}}$ with
$d_{l_{1}}(\varepsilon)$. More precisely, according to Lemma 1, one compares
$\log(K_{\operatorname{surr}}(\varepsilon))$ with
$\sum_{h}\log(L_{h}^{P}(\varepsilon/(2H)^{2}))+\log(L_{h}^{R}(\varepsilon/(4H)))$.
From the definition of $d_{l_{1},h}^{P}$ we have
$\log(L_{h}^{P}(\varepsilon/(2H)^{2}))\sim
O(d_{l_{1},h}^{P}\log((2H)^{2}/\varepsilon))$, so this includes a logarithmic
factor of $H^{2}$, and choosing $\varepsilon=1/L$ means a logarithmic factor
of $H^{2}L$. A similar argument can be made for $L_{h}^{R}$.

Finally, the last statement of the theorem follows by definition:
$d_{l_{1}}L=(\sum_{h}d_{l_{1},h})L=d_{\operatorname{hom}}HL=d_{\operatorname{hom}}T$.
This finishes the proof of the main theorem. ∎

######  Remark 12.

Equations similar to Eq. 46 can be found in (Hao and Lattimore,, 2022, App.
B.2). However, a small correction must be made to their derivation. The
authors first apply Cauchy-Schwarz and then take the square of Eq. 45 to
replace the original regret with the surrogate regret. As seen later in the
proof, we do it in the opposite order, because in (45), the left side may be
negative, so we can not assume the square of that estimation to be also
correct. While outside the focus of this paper, we note that a side-effect of
this correction is another one to their definition of surrogate-IDS in (Hao
and Lattimore,, 2022, Eq. (4.3)), wherein minimization should be over the
square root of their information ratio.

##  Appendix D Bounding $\mathbb{E}[\sum_{\ell}\mathcal{I}^{\ell}]$

We start by proving
$\mathcal{I}^{\ell}\leq\frac{1}{2}\mathbb{I}^{\pi^{\ell}_{\text{TS}}}_{\ell}(\tilde{\mathcal{E}}^{*}_{\ell};\mathcal{H}_{\ell,H}),\forall\ell\in[L]$.
We recall that TS property implies
$\mathbb{E}_{\ell}[d_{h,\pi^{*}_{\mathcal{E}}}^{\bar{\mathcal{E}}_{\ell}}(s,a)]=\mathbb{E}_{\ell}[d_{h,\pi^{\ell}_{\text{TS}}}^{\bar{\mathcal{E}}_{\ell}}(s,a)]$.
So,

$\displaystyle\mathcal{I}^{\ell}$
$\displaystyle=\sum_{h=1}^{H}\mathbb{E}_{\ell}\left[\int_{s,a}\mathbb{E}_{\ell}[d_{h,\pi^{*}_{\mathcal{E}}}^{\bar{\mathcal{E}}_{\ell}}(s,a)]\frac{\Delta_{h}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s,a)^{2}}{\lambda_{\mathcal{E}}^{2}}\operatorname{d}\\!\mu_{{\mathcal{S}}\times\mathcal{A}}\right]$
(56)
$\displaystyle=\sum_{h=1}^{H}\mathbb{E}_{\ell}\left[\int_{s,a}\mathbb{E}_{\ell}[d_{h,\pi^{\ell}_{\text{TS}}}^{\bar{\mathcal{E}}_{\ell}}(s,a)]\frac{\Delta_{h}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s,a)^{2}}{\lambda_{\mathcal{E}}^{2}}\operatorname{d}\\!\mu_{{\mathcal{S}}\times\mathcal{A}}\right]\,.$
(57)

Next, we swap the two integrals, one represented by $\mathbb{E}_{\ell}$ and
the one over $s,a$,

$\displaystyle=\sum_{h=1}^{H}\int_{s,a}\mathbb{E}_{\ell}[d_{h,\pi^{\ell}_{\text{TS}}}^{\bar{\mathcal{E}}_{\ell}}(s,a)]\mathbb{E}_{\ell}\left[\frac{\Delta_{h}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s,a)^{2}}{\lambda_{\mathcal{E}}^{2}}\right]\operatorname{d}\\!\mu_{{\mathcal{S}}\times\mathcal{A}}$
(58)

Note that, given $\mathcal{D}_{\ell}$,
$\Delta_{h}^{\tilde{\mathcal{E}}^{*}_{\ell}}$ is independent of
$d_{h,\pi^{\ell}_{\text{TS}}}^{\bar{\mathcal{E}}_{\ell}}(s,a)$. Therefore,
using the identity $\mathbb{E}[XY]=\mathbb{E}[X]\mathbb{E}[Y]$ for two
independent random variables, and swapping back the two integrals,

$\displaystyle=\sum_{h=1}^{H}\mathbb{E}_{\ell}\left[\int_{s,a}d_{h,\pi^{\ell}_{\text{TS}}}^{\bar{\mathcal{E}}_{\ell}}(s,a)\frac{\Delta_{h}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s,a)^{2}}{\lambda_{\mathcal{E}}^{2}}\operatorname{d}\\!\mu_{{\mathcal{S}}\times\mathcal{A}}\right]=\sum_{h=1}^{H}\mathbb{E}_{\ell}\left[\mathbb{E}_{\pi^{\ell}_{\text{TS}}}^{\bar{\mathcal{E}}_{\ell}}\left[\frac{\Delta_{h}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s,a)^{2}}{\lambda_{\mathcal{E}}^{2}}\right]\right]$
(59)

Finally, notice that
$\frac{\Delta_{h}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s,a)^{2}}{\lambda_{\mathcal{E}}^{2}}$
can be estimated by Pinsker’s inequality (Lemma 9) as

$\displaystyle\begin{split}&\frac{\Delta_{h}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s,a)^{2}}{\lambda_{\mathcal{E}}^{2}}\\\
&\quad=\left(\mathbb{E}_{(s^{\prime},r^{\prime})\sim(P_{h}^{\tilde{\mathcal{E}}_{\ell}^{*}}\otimes
r_{h}^{\tilde{\mathcal{E}}_{\ell}^{*}})(\cdot|s_{h},a_{h})}\left[\frac{r^{\prime}+V_{h+1,\pi^{*}_{\mathcal{E}}}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s^{\prime})}{\lambda_{\mathcal{E}}}\right]\right.\\\
&\quad\qquad\left.-\mathbb{E}_{(s^{\prime},r^{\prime})\sim(P_{h}^{\bar{\mathcal{E}}_{\ell}}\otimes
r_{h}^{\bar{\mathcal{E}}_{\ell}})(\cdot|s_{h},a_{h})}\left[\frac{r^{\prime}+V_{h+1,\pi^{*}_{\mathcal{E}}}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s^{\prime})}{\lambda_{\mathcal{E}}}\right]\right)^{2}\\\
&\quad=\left(\mathbb{E}_{(s^{\prime},r^{\prime})\sim(P_{h}^{\tilde{\mathcal{E}}_{\ell}^{*}}\otimes
r_{h}^{\tilde{\mathcal{E}}_{\ell}^{*}})(\cdot|s_{h},a_{h})}\left[\frac{r^{\prime}+V_{h+1,\pi^{*}_{\mathcal{E}}}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s^{\prime})-r^{\operatorname{inf}}_{h}(s_{h},a_{h})-\inf_{s}V_{h+1,\pi^{*}_{\mathcal{E}}}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s)}{\lambda_{\mathcal{E}}}\right]\right.\\\
&\quad\qquad\left.-\mathbb{E}_{(s^{\prime},r^{\prime})\sim(P_{h}^{\bar{\mathcal{E}}_{\ell}}\otimes
r_{h}^{\bar{\mathcal{E}}_{\ell}})(\cdot|s_{h},a_{h})}\left[\frac{r^{\prime}+V_{h+1,\pi^{*}_{\mathcal{E}}}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s^{\prime})-r^{\operatorname{inf}}_{h}(s_{h},a_{h})-\inf_{s}V_{h+1,\pi^{*}_{\mathcal{E}}}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s)}{\lambda_{\mathcal{E}}}\right]\right)^{2}\\\
&\quad\leq\frac{1}{2}\textit{D}_{\text{KL}}\left((P_{h}^{\tilde{\mathcal{E}}_{\ell}^{*}}\otimes
r_{h}^{\tilde{\mathcal{E}}_{\ell}^{*}})(\cdot|s_{h},a_{h})||(P_{h}^{\bar{\mathcal{E}}_{\ell}}\otimes
r_{h}^{\bar{\mathcal{E}}_{\ell}})(\cdot|s_{h},a_{h})\right)\end{split}$

where we note the trick of adding and subtracting the constant term
$r^{\operatorname{inf}}_{h}(s_{h},a_{h})+\inf_{s}V_{h+1,\pi^{*}_{\mathcal{E}}}^{\tilde{\mathcal{E}}_{\ell}^{*}}(s)$
to the expected values in order to make the expression inside between zero and
$\lambda_{\mathcal{E}}$. This enables the application of Pinsker’s inequality
which requires the random variable $X$ in
$(\mathbb{E}_{P}[X]-\mathbb{E}_{Q}[X])^{2}\leq\frac{1}{2}\textit{D}_{\text{KL}}(P||Q)$
to be smaller than one. Therefore

$\displaystyle\mathcal{I}^{\ell}\leq\frac{1}{2}\sum_{h=1}^{H}\mathbb{E}_{\ell}\left[\mathbb{E}_{\pi^{\ell}_{\text{TS}}}^{\bar{\mathcal{E}}_{\ell}}\left[\textit{D}_{\text{KL}}\left((P_{h}^{\tilde{\mathcal{E}}_{\ell}^{*}}\otimes
r_{h}^{\tilde{\mathcal{E}}_{\ell}^{*}})(\cdot|s_{h},a_{h})||(P_{h}^{\bar{\mathcal{E}}_{\ell}}\otimes
r_{h}^{\bar{\mathcal{E}}_{\ell}})(\cdot|s_{h},a_{h})\right)\right]\right].$
(60)

Lastly, we use Lemma 10, wherein we show a fact similar to (Hao and
Lattimore,, 2022, App. C.1.) but for $\tilde{\mathcal{E}}^{*}_{\ell}$ instead
of $\mathcal{E}$, proving the above equals
$\frac{1}{2}\mathbb{I}_{\ell}^{\pi^{\ell}_{\text{TS}}}(\tilde{\mathcal{E}}^{*}_{\ell};\mathcal{H}_{\ell,H})$.

Next, observe that
$\mathbb{I}_{\ell}^{\pi^{\ell}_{\text{TS}}}(\tilde{\mathcal{E}}_{\ell}^{*};\mathcal{H}_{\ell,H})\leq\mathbb{I}_{\ell}^{\pi^{\ell}_{\text{TS}}}(\zeta;\mathcal{H}_{\ell,H})$.
Indeed, recall that the definition of $\mathbb{I}_{\ell}$ conditions on a
$\mathcal{D}_{\ell}$; and we know that conditional on a $\mathcal{D}_{\ell}$,
the surrogate environment $\tilde{\mathcal{E}}^{*}_{\ell}$ is only dependent
on $\zeta$ by construction, hence the data processing inequality applies and
we have

$\displaystyle\mathcal{I}^{\ell}\leq\frac{1}{2}\mathbb{I}_{\ell}^{\pi^{\ell}_{\text{TS}}}(\zeta;\mathcal{H}_{\ell,H}).$
(61)

Next, we use the mutual information chain rule, observing that

$\displaystyle\mathbb{E}\left[\mathbb{I}_{\ell}^{\pi^{\ell}_{\text{TS}}}(\zeta;\mathcal{H}_{\ell,H})\right]=\mathbb{I}(\zeta;\mathcal{H}_{\ell,H}|\mathcal{H}_{\ell-1,H},\ldots,\mathcal{H}_{1,H}),$
(62)

and therefore

$\displaystyle\mathbb{I}\left(\zeta;\mathcal{D}_{L+1}\right)=\mathbb{I}\left(\zeta;\left(\mathcal{H}_{1,H},\ldots,\mathcal{H}_{L,H}\right)\right)=\sum_{\ell=1}^{L}\mathbb{E}\left[\mathbb{I}_{\ell}^{\pi^{\ell}_{\text{TS}}}(\zeta;\mathcal{H}_{\ell,H})\right]\,.$
(63)

Applied to the above, and noting that
$\mathbb{I}\left(\zeta;\mathcal{D}_{L+1}\right)\leq
H(\zeta)\leq\log(K_{\operatorname{surr}}(\varepsilon))$, this finishes our
estimation of
$\mathbb{E}[\sum_{\ell}\mathcal{I}^{\ell}]\leq\frac{1}{2}\log(K_{\operatorname{surr}}(\varepsilon))$.

##  Appendix E Bounding $\mathbb{E}[{\mathcal{T}}^{\ell}]$

This is where we use analysis tools from posterior consistency. We focus on
bounding

$\displaystyle{\mathcal{T}}^{\ell}=\int_{(s,a,h)\in\mathcal{B}_{\ell}}\frac{\mathbb{E}_{\ell}\left[(\lambda_{\mathcal{E}}d_{h,\pi^{*}_{\mathcal{E}}}^{\bar{\mathcal{E}}_{\ell}}(s,a))^{2}\right]}{\mathbb{E}_{\ell}\left[d_{h,\pi^{*}_{\mathcal{E}}}^{\bar{\mathcal{E}}_{\ell}}(s,a)\right]}.$
(64)

Note that we have

$\displaystyle\mathbb{E}_{\ell}\left[d_{h,\pi^{*}_{\mathcal{E}}}^{\bar{\mathcal{E}}_{\ell}}(s,a)\right]=\mathbb{E}_{\ell}\left[d_{h,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}^{\prime}}(s,a)\right],$

where $\mathcal{E}^{\prime}$ is sampled from the posterior $\mathbb{P}_{\ell}$
independent of $\mathcal{E}$. Similarly

$\displaystyle\mathbb{E}_{\ell}\left[(\lambda_{\mathcal{E}}d_{h,\pi^{*}_{\mathcal{E}}}^{\bar{\mathcal{E}}_{\ell}}(s,a))^{2}\right]$
$\displaystyle=(\mathbb{E}_{\ell})_{\mathcal{E}\sim\mathbb{P}_{\ell}}\left[\lambda_{\mathcal{E}}^{2}\left((\mathbb{E}_{\ell})_{\mathcal{E}^{\prime}\sim\mathbb{P}_{\ell}}\left[d_{h,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}^{\prime}}(s,a)\right]\right)^{2}\right]$
$\displaystyle\leq(\mathbb{E}_{\ell})_{\mathcal{E}\sim\mathbb{P}_{\ell}}\left[\lambda_{\mathcal{E}}^{2}(\mathbb{E}_{\ell})_{\mathcal{E}^{\prime}\sim\mathbb{P}_{\ell}}\left[d_{h,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}^{\prime}}(s,a)^{2}\right]\right]$
$\displaystyle=\mathbb{E}_{\ell}\left[(\lambda_{\mathcal{E}}d_{h,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}^{\prime}}(s,a))^{2}\right].$

For any $\ell,s,a,h$ and $\mathcal{D}_{\ell}$, we define

$\displaystyle
g_{\ell}(s,a,h,\mathcal{D}_{\ell}):=\frac{\mathbb{E}_{\ell}\left[(\lambda_{\mathcal{E}}d_{h,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}^{\prime}}(s,a))^{2}\right]}{\mathbb{E}_{\ell}\left[d_{h,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}^{\prime}}(s,a)\right]},$
(65)

whenever $(s,a,h)\in\mathcal{B}_{\ell}$ and
$g_{\ell}(s,a,h,\mathcal{D}_{\ell}):=0$ otherwise. Clearly we have

$\displaystyle{\mathcal{T}}^{\ell}\leq\int_{(s,a,h)}g_{\ell}(s,a,h,\mathcal{D}_{\ell}).$
(66)

Moreover, given our assumption on state action occupation density, we have
$M_{d}:=\sup_{s,a,h,\pi,\mathcal{E}}d_{h,\pi}^{\mathcal{E}}(s,a)<\infty$,
which implies $g_{\ell}\leq M_{d}H^{2}<\infty$ and ${\mathcal{T}}^{\ell}\leq
M_{d}H^{3}<\infty$. Let $\mathcal{E}_{0}$ be the true environment. This means
$\mathbb{E}[\cdot|\mathcal{E}_{0}]=\mathbb{E}_{\mathcal{D}_{\ell}\sim\mathbb{P}(\cdot|\mathcal{E}_{0})}[\cdot]$.

According to Corollary 12, we have

$\displaystyle\lim_{\ell\to\infty}\mathbb{E}_{\ell}\left[d_{h,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}^{\prime}}(s,a)\right]$
$\displaystyle=d_{h,\pi^{*}_{\mathcal{E}_{0}}}^{\mathcal{E}_{0}}(s,a),$ (67)
$\displaystyle\lim_{\ell\to\infty}\mathbb{E}_{\ell}\left[(\lambda_{\mathcal{E}}d_{h,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}^{\prime}}(s,a))^{2}\right]$
$\displaystyle=(\lambda_{\mathcal{E}_{0}}d_{h,\pi^{*}_{\mathcal{E}_{0}}}^{\mathcal{E}_{0}}(s,a))^{2}.$
(68)

According to Assumption 2,
$d_{h,\pi^{*}_{\mathcal{E}_{0}}}^{\mathcal{E}_{0}}(s,a)\neq 0$ for almost
every $\mathcal{E}_{0},s,a$ and $h$. For any such values of
$(\mathcal{E}_{0},s,a,h)$ and almost every $\mathcal{D}_{\ell}$ sampled from
true environment $\mathcal{E}_{0}$, we conclude that

$\displaystyle\lim_{\ell\to\infty}g_{\ell}(s,a,h,\mathcal{D}_{\ell})=\lambda_{\mathcal{E}_{0}}^{2}d_{h,\pi^{*}_{\mathcal{E}_{0}}}^{\mathcal{E}_{0}}(s,a).$
(69)

Therefore, using dominated convergence theorem, for almost every
$\mathcal{E}_{0}$ we have

$\displaystyle\lim_{\ell\to\infty}\mathbb{E}[{\mathcal{T}}^{\ell}|\mathcal{E}_{0}]$
$\displaystyle\leq\lim_{\ell\to\infty}\mathbb{E}_{\mathcal{D}_{\ell}\sim\mathbb{P}(\cdot|\mathcal{E}_{0})}\left[\int_{(s,a,h)}g_{\ell}(s,a,h,\mathcal{D}_{\ell})\right]$
(70)
$\displaystyle=\lim_{\ell\to\infty}\int_{(s,a,h)}\mathbb{E}_{\mathcal{D}_{\ell}\sim\mathbb{P}(\cdot|\mathcal{E}_{0})}\left[g_{\ell}(s,a,h,\mathcal{D}_{\ell})\right]$
(71)
$\displaystyle=\int_{(s,a,h)}\mathbb{E}_{\mathcal{D}_{\ell}\sim\mathbb{P}(\cdot|\mathcal{E}_{0})}\left[\lim_{\ell\to\infty}g_{\ell}(s,a,h,\mathcal{D}_{\ell})\right]$
(72)
$\displaystyle=\int_{(s,a,h)}\mathbb{E}_{\mathcal{D}_{\ell}\sim\mathbb{P}(\cdot|\mathcal{E}_{0})}\left[\lambda_{\mathcal{E}_{0}}^{2}d_{h,\pi^{*}_{\mathcal{E}_{0}}}^{\mathcal{E}_{0}}(s,a)\right]$
(73)
$\displaystyle=\int_{(s,a,h)}\lambda_{\mathcal{E}_{0}}^{2}d_{h,\pi^{*}_{\mathcal{E}_{0}}}^{\mathcal{E}_{0}}(s,a)$
(74) $\displaystyle=\lambda_{\mathcal{E}_{0}}^{2}H.$ (75)

Therefore we may use dominated convergence theorem again to see that

$\displaystyle\lim_{\ell\to\infty}\mathbb{E}[{\mathcal{T}}^{\ell}]=\lim_{\ell\to\infty}\mathbb{E}[\mathbb{E}[{\mathcal{T}}^{\ell}|\mathcal{E}_{0}]]=\mathbb{E}[\lim_{\ell\to\infty}\mathbb{E}[{\mathcal{T}}^{\ell}|\mathcal{E}_{0}]]\leq\mathbb{E}[\lambda_{\mathcal{E}_{0}}^{2}H]=\mathbb{E}[\lambda_{\mathcal{E}}^{2}]H=\lambda^{2}H.$
(76)

Therefore, there exists $L_{0}>0$ such that
$\mathbb{E}[{\mathcal{T}}^{\ell}]\leq 2\lambda^{2}H$ for $\ell>L_{0}$.

##  Appendix F Proof of Corollary 5

We restate the corollary below. We prove it in a more general case where the
maps $\phi^{P},\phi^{R}$ are time inhomogeneous, i.e.
$\phi_{h}^{P},\phi_{h}^{R}$. In addition, the dimension of their target space
can also depend on $h$, i.e. we use $d_{f}^{P,h},d_{f}^{R,h}$, instead of just
$d_{f}^{P},d_{f}^{R}$. For the case where the dimensions are homogeneous, we
use $d_{f}^{\operatorname{hom}}$. This new notation impacts the statement as
follows:

######  Corollary.

For a linear Bayesian RL, for large enough $T$,

$\displaystyle\mathfrak{BR}_{L}(\pi_{\text{TS}})\leq\widetilde{O}(\lambda\sqrt{d_{l_{1}}^{f}T}).$
(77)

Given a linear Bayesian RL with finitely many states and homogeneous feature
space dimension $d_{f}^{\operatorname{hom}}$, we have $d_{l_{1}}^{f}\leq
2d_{f}^{\operatorname{hom}}HS$, yielding for large enough $T$,

$\displaystyle\mathfrak{BR}_{L}(\pi_{\text{TS}})\leq\widetilde{O}(\lambda\sqrt{Hd_{f}^{\operatorname{hom}}ST}).$
(78)

Given a mixture linear Bayesian RL, for large enough $T$,

$\displaystyle\mathfrak{BR}_{L}(\pi_{\text{TS}})\leq\widetilde{O}(\lambda\sqrt{MT})\,,$
(79)

The first statement follows from the generic bound, but we need to relate the
$l_{1}-$dimension of the environment space to that of the feature maps space,
where we recall the definitions
$d_{l_{1}}^{f}=d_{l_{1}}^{P,f}+d_{l_{1}}^{R,f}$ as the sum of the
$l_{1}-$dimensions of the feature map space
$\\{\psi_{h}^{P,\mathcal{E}}\\}_{\mathcal{E}\in\Theta},\\{\psi_{h}^{R,\mathcal{E}}\\}_{\mathcal{E}\in\Theta}$
where the $l_{1}-$distance between feature maps is defined as
$l_{1}(\psi_{h}^{\mathcal{E}},\psi_{h}^{\mathcal{E}^{\prime}})=\int_{s}\|\psi_{h}^{\mathcal{E}}-\psi_{h}^{\mathcal{E}^{\prime}}\|_{1}\mu_{\mathcal{S}}$.
We shall use 1:

$\displaystyle
V_{1,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}}(s_{1}^{\ell})-V_{1,\pi^{*}_{\mathcal{E}}}^{\mathcal{E}^{\prime}}(s_{1}^{\ell})\leq
H\sum_{h=1}^{H}l_{1}(P_{h}^{\mathcal{E}},P_{h}^{\mathcal{E}^{\prime}})+\sum_{h=1}^{H}l_{1}(r_{h}^{\mathcal{E}},r_{h}^{\mathcal{E}^{\prime}})\,.$
(80)

We estimate

$\displaystyle\begin{split}l_{1}(P_{h}^{\mathcal{E}},P_{h}^{\mathcal{E}^{\prime}})=\sup_{s,a}\int_{s^{\prime}}|P_{h}^{\mathcal{E}}(s^{\prime}|s,a)-P_{h}^{\mathcal{E}^{\prime}}(s^{\prime}|s,a)|=\sup_{s,a}\int_{s^{\prime}}|\phi_{h}^{P}(s,a)\cdot(\psi_{h}^{P,\mathcal{E}}(s^{\prime})-\psi_{h}^{P,\mathcal{E}}(s^{\prime}))|\leq\\\
\sup_{s,a}\int_{s^{\prime}}\sum_{i=1}^{d_{f,h}^{P}}|\phi_{h}^{P}(s,a)_{i}(\psi_{h}^{P,\mathcal{E}}(s^{\prime})-\psi_{h}^{P,\mathcal{E}}(s^{\prime}))_{i}|\end{split}$
(81)

Since $\|\phi_{h}^{P}(s,a)\|_{2}\leq 1\implies|\phi_{h}^{P}(s,a)_{i}|\leq
1,\forall i\in[d]$. Therefore

$\displaystyle
l_{1}(P_{h}^{\mathcal{E}},P_{h}^{\mathcal{E}^{\prime}})\leq\int_{s^{\prime}}\|(\psi_{h}^{P,\mathcal{E}}(s^{\prime})-\psi_{h}^{P,\mathcal{E}}(s^{\prime}))\|_{1}=l_{1}(\psi_{h}^{P,\mathcal{E}},\psi_{h}^{P,\mathcal{E}}).$
(82)

The similar bound can be achieved for
$l_{1}(r_{h}^{\mathcal{E}},r_{h}^{\mathcal{E}^{\prime}})$. As a result
$d_{l_{1}}\leq d_{l_{1}}^{f}$ and we get the first statement.

For Eq. 78, we note that if $S$ is a finite, then $\psi_{h}^{P,\mathcal{E}}$
can be viewed as a $d_{f}^{P,h}\times S$ matrix, or simply a vector with
dimension that size. Therefore, we can view our problem as asking for the
asymptotics of the $\varepsilon-$covering number in
$\mathbb{R}^{d_{f}^{P,h}S}$. As long as the collection
$\\{\psi_{h}^{P,\mathcal{E}}\\}_{\mathcal{E}}$ is within a finite ball, which
they are (Definition 4), the covering number is well-known to scale at most as
$O((\frac{\log(C_{\psi})}{\varepsilon})^{d_{f}^{P,h}S})$ where $C_{\psi}$ is
the radius of that ball. Applying the similar argument for the rewards, we
have $d_{l_{1}}\leq d_{l_{1}}^{f}\leq\sum(d_{f}^{P,h}+d_{f}^{R,h})S$, which
equals $2Hd_{f}^{\operatorname{hom}}S$ given a homogeneous feature space
dimension $d_{f}^{\operatorname{hom}}=d_{f}^{P,h}=d_{f}^{R,h}$, for all
$h\in[H]$.

The finite mixtures statement is a straightforward generalization of the
above, where every $\psi_{h}^{P,\mathcal{E}},\psi_{h}^{R,\mathcal{E}}$ is
characterized with a finite $m_{h}^{P},m_{h}^{R}$-dimensional vector instead
of specifically being $d_{f}^{P,h}S,d_{f}^{R,h}S$-dimensional. We note

$\displaystyle
l_{1}(\psi_{h}^{P,\mathcal{E}},\psi_{h}^{P,\mathcal{E}})=\int_{s^{\prime}}\|(\psi_{h}^{P,\mathcal{E}}(s^{\prime})-\psi_{h}^{P,\mathcal{E}}(s^{\prime}))\|_{1}\leq
C_{\Psi}\|\bm{a}_{h}^{P,\mathcal{E}}-\bm{a}_{h}^{P,\mathcal{E}^{\prime}}\|_{1}$
(83)

where $C_{\Psi}=\max_{1\leq i\leq m_{h}^{P}}\|\Psi_{h,i}^{P}\|_{1}$. So the
same argument above applies, where we consider the collection of finite
dimensional vectors $\\{\bm{a}_{h}^{P,\mathcal{E}}\\}_{\mathcal{E}}$ and the
$\varepsilon-$covering number, and similarly for
$\\{\bm{a}_{h}^{R,\mathcal{E}}\\}_{\mathcal{E}}$.

###  F.1 Incorrect proof for the Bayesian regret bound of linear Bayesian RL
with deterministic rewards

Here, we discuss the proof of Hao and Lattimore, (2022) for linear RLs, and
the mistakes in their argument. We start by citing the similar equations in
(Hao and Lattimore,, 2022, App. B.4) in bounding the value difference with the
feature maps difference:

> For any $\mathcal{E}_{1},\mathcal{E}_{2}\in\Theta_{k}$, […]
>
> $\displaystyle
> V_{1,\pi^{*}_{\mathcal{E}_{1}}}^{\mathcal{E}_{1}}(s_{1})-V_{1,\pi^{*}_{\mathcal{E}_{1}}}^{\mathcal{E}_{2}}(s_{1})$
> $\displaystyle\qquad=\sum_{h=1}^{H}\mathbb{E}_{\pi^{*}_{\mathcal{E}_{1}}}^{\mathcal{E}_{2}}\left[P_{h}^{\mathcal{E}_{1}}(\cdot|s_{h}^{\ell},a_{h}^{\ell})^{\top}V_{h+1,\pi^{*}_{\mathcal{E}_{1}}}^{\mathcal{E}_{1}}(\cdot)-P_{h}^{\mathcal{E}_{2}}(\cdot|s_{h}^{\ell},a_{h}^{\ell})^{\top}V_{h+1,\pi^{*}_{\mathcal{E}_{1}}}^{\mathcal{E}_{1}}(\cdot)\right]$
> $\displaystyle\qquad=\sum_{h=1}^{H}\mathbb{E}_{\pi^{*}_{\mathcal{E}_{1}}}^{\mathcal{E}_{2}}\left[\phi(s_{h}^{\ell},a_{h}^{\ell})^{\top}\sum_{s^{\prime}}V_{h+1,\pi^{*}_{\mathcal{E}_{1}}}^{\mathcal{E}_{1}}(s^{\prime})\psi_{h}^{\mathcal{E}_{1}}(s^{\prime})\right.$
> $\displaystyle\qquad\qquad\qquad\qquad\qquad\left.-\phi(s_{h}^{\ell},a_{h}^{\ell})^{\top}\sum_{s^{\prime}}V_{h+1,\pi^{*}_{\mathcal{E}_{1}}}^{\mathcal{E}_{1}}(s^{\prime})\psi_{h}^{\mathcal{E}_{2}}(s^{\prime})\right]\,,$
>
> […] Moreover, since the value function is always bounded by $H$, we have
>
> $\displaystyle V_{1,\pi^{*}_{\mathcal{E}_{1}}}^{\mathcal{E}_{1}}(s_{1})$
> $\displaystyle-V_{1,\pi^{*}_{\mathcal{E}_{1}}}^{\mathcal{E}_{2}}(s_{1})$
> $\displaystyle=H\sum_{h=1}^{H}\mathbb{E}_{\pi^{*}_{\mathcal{E}_{1}}}^{\mathcal{E}_{2}}\left[\phi(s_{h}^{\ell},a_{h}^{\ell})^{\top}\left(\sum_{s^{\prime}}\psi_{h}^{\mathcal{E}_{1}}(s^{\prime})-\sum_{s^{\prime}}\psi_{h}^{\mathcal{E}_{2}}(s^{\prime})\right)\right]$
> $\displaystyle\leq
> H\sum_{h=1}^{H}\mathbb{E}_{\pi^{*}_{\mathcal{E}_{1}}}^{\mathcal{E}_{2}}\left[\left\|\phi(s_{h}^{\ell},a_{h}^{\ell})\right\|_{2}\right]\left\|\sum_{s^{\prime}}\psi_{h}^{\mathcal{E}_{1}}(s^{\prime})-\sum_{s^{\prime}}\psi_{h}^{\mathcal{E}_{2}}(s^{\prime})\right\|_{2}$
> $\displaystyle\leq
> H\sum_{h=1}^{H}\left\|\sum_{s^{\prime}}\psi_{h}^{\mathcal{E}_{1}}(s^{\prime})-\sum_{s^{\prime}}\psi_{h}^{\mathcal{E}_{2}}(s^{\prime})\right\|_{2}\,.$
> (84)

Clearly, in the first equation, the equality must be replaced by $\leq$, and
more importantly, given that the value function
$V_{h+1,\pi^{*}_{\mathcal{E}_{1}}}^{\mathcal{E}_{1}}(\cdot)$ has argument
$\cdot=s^{\prime}$, the $l_{2}-$norm should be taken on the inside of the
integral
$\int_{s^{\prime}}\|\phi(s_{h}^{\ell},a_{h}^{\ell})^{\top}\left((\psi_{h}^{\mathcal{E}_{1}}(s^{\prime})-\psi_{h}^{\mathcal{E}_{2}}(s^{\prime})\right)\|_{2}$
(we note we also replaced the sum $\sum_{s^{\prime}}$ with integral, as linear
RLs could have infinitely many states). If our proposed correction were to be
followed then the next equations would change to ones similar to ours except
with an $l_{2}-$distance:

$\displaystyle\leq
H\sum_{h=1}^{H}\mathbb{E}_{\pi^{*}_{\mathcal{E}_{1}}}^{\mathcal{E}_{2}}\left[\left\|\phi(s_{h}^{\ell},a_{h}^{\ell})\right\|_{2}\right]\int_{s^{\prime}}\left\|\psi_{h}^{\mathcal{E}_{1}}(s^{\prime})-\psi_{h}^{\mathcal{E}_{2}}(s^{\prime})\right\|_{2}$
(85) $\displaystyle\leq
H\sum_{h=1}^{H}\int_{s^{\prime}}\left\|\psi_{h}^{\mathcal{E}_{1}}(s^{\prime})-\psi_{h}^{\mathcal{E}_{2}}(s^{\prime})\right\|_{2}$
(86)

Otherwise, let us assume that the authors were correct, then we have managed
to bound
$V_{1,\pi^{*}_{\mathcal{E}_{1}}}^{\mathcal{E}_{1}}(s_{1})-V_{1,\pi^{*}_{\mathcal{E}_{1}}}^{\mathcal{E}_{2}}(s_{1})\leq
H\sum_{h=1}^{H}\left\|\sum_{s^{\prime}}\psi_{h}^{\mathcal{E}_{1}}(s^{\prime})-\sum_{s^{\prime}}\psi_{h}^{\mathcal{E}_{2}}(s^{\prime})\right\|_{2}$.
We show that this is a bound by zero for an important subclass of linear RLs,
i.e. all tabular RLs.

It is a well-known fact that tabular RLs can be viewed as linear RLs. The
mapping works as follows. First let us enumerate the set
$\\{(s,a)\in{\mathcal{S}}\times\mathcal{A}\\}$ by $1,\ldots,SA$. Call this
assignment $N(s,a)\in[SA]$. Then define
$\phi(s,a)=e_{N(s,a)}\in\mathbb{R}^{SA}$, which is the Euclidean basis state
on axis $N(s,a)$. Let
$\psi_{h}^{\mathcal{E}}(s^{\prime})=(P_{h}^{\mathcal{E}}(s^{\prime}|s,a))_{s,a}$.
Then clearly all the conditions $\|\phi\|_{2}\leq
1,\|\sum_{s^{\prime}}\psi(s^{\prime})\|_{2}\leq C_{\psi}$ and most importantly
$P_{h}(\cdot|s,a)=\langle\phi(s,a),\psi_{h}^{\mathcal{E}}(s^{\prime})\rangle$,
are satisfied. However we note that for any $\mathcal{E},h$ we have
$\sum_{s^{\prime}}\psi_{h}^{\mathcal{E}}(s^{\prime})=(\sum_{s}^{\prime}P_{h}^{\mathcal{E}}(s^{\prime}|s,a))_{s,a}=(1)_{s,a}$
which is the all one vector in $\mathbb{R}^{SA}$. In that case,
$\sum_{s^{\prime}}\psi_{h}^{\mathcal{E}}(s^{\prime})-\sum_{s^{\prime}}\psi_{h}^{\mathcal{E}^{\prime}}(s^{\prime})$
in Eq. 84 is the zero vector, with zero norm.

Therefore, were the estimation in (Hao and Lattimore,, 2022, App. B.4)
correct, for all tabular Bayesian RLs with deterministic reward, the
difference of all value functions of the form
$V^{\mathcal{E}_{1}}_{1,\pi^{*}_{\mathcal{E}_{1}}}-V^{\mathcal{E}_{2}}_{1,\pi^{*}_{\mathcal{E}_{2}}}$
would be bounded above by zero, meaning we have estimated
$K_{\operatorname{surr}}(\varepsilon)=1$ for all $\varepsilon$, which since
$\log(1)=0$, implies a constant regret bound as well. This counterexample
further demonstrates the mistake above.

Overall, this makes the proof for (Hao and Lattimore,, 2022, Theorem 4.10)
incorrect and invalidates their claim of a regret bound
$\widetilde{O}(d_{f}^{\operatorname{hom}}H^{3/2}\sqrt{T})$.

######  Remark 13.

Another important gap in the proof of (Hao and Lattimore,, 2022, Theorem 4.10)
can be found in (Hao and Lattimore,, 2022, App. B.5), where the surrogate
regret is claimed to be bounded by a conditional mutual information by
$\pi^{*}$ instead of $\pi^{\ell}_{\text{TS}}$. This is explained in further
details in Section I.1.

##  Appendix G Proof of Corollary 6

We restate the corollary.

######  Corollary.

Given a finite mixtures Bayesian RL problem, for large enough $T$,

$\displaystyle\mathfrak{BR}_{L}(\pi_{\text{TS}})\leq\widetilde{O}(\lambda\sqrt{d_{l_{1}}^{m}T})\,.$
(87)

Assuming the restricted finite mixtures model, for large enough $T$,

$\displaystyle\mathfrak{BR}_{L}(\pi_{\text{TS}})\leq\widetilde{O}\left(\lambda\sqrt{MT}\right)\,.$
(88)

which, given a uniform dimension $m=m_{h}^{P}=m_{h}^{R}$, yields
$\widetilde{O}(\lambda\sqrt{HmT})$.

Given Theorem 3 and 1, we need to estimate the $d_{l_{1}}$ of $\Theta$ by that
of $\\{\bm{a}_{h}^{P,\mathcal{E}}(s,a)\\}_{\mathcal{E}\in\Theta}$ and
$\\{\bm{a}_{h}^{R,\mathcal{E}}(s,a)\\}_{\mathcal{E}\in\Theta}$. Indeed writing
the $l_{1}-$distance of two transition functions:

$\displaystyle\begin{split}&\sup_{s,a}\|P_{h}^{\mathcal{E}}(\cdot|s,a)-P_{h}^{\mathcal{E}^{\prime}}(\cdot|s,a)\|_{1}=\sup_{s,a}\|\sum_{i=1}^{m_{h}}({a}_{h,i}^{P,\mathcal{E}}(s,a)-a_{h,i}^{P,\mathcal{E}^{\prime}}(s,a))Z_{h,i}^{P}(\cdot|s,a)\|_{1}\leq\\\
&\sup_{s,a}\sum_{i=1}^{m_{h}}\|(a_{h,i}^{P,\mathcal{E}}(s,a)-a_{h,i}^{P,\mathcal{E}^{\prime}}(s,a))Z_{h,i}^{P}(\cdot|s,a)\|_{1}=\sup_{s,a}\sum_{i=1}^{m_{h}}|a_{h,i}^{P,\mathcal{E}}(s,a)-a_{h,i}^{P,\mathcal{E}^{\prime}}(s,a)|=\\\
&\sup_{s,a}\|\bm{a}_{h}^{P,\mathcal{E}}(s,a)-\bm{a}_{h}^{P,\mathcal{E}^{\prime}}(s,a)\|_{1}\end{split}$
(89)

where we used the triangle inequality and the fact that the density functions
are positive and their integral equals one.

For the second statement, we are faced with the problem of finding an
$l_{1}-$covering number for a collection of vectors on the $m_{h}-$dimensional
simplex. It is a standard fact that the covering of the latter is of order
$O\left((\frac{1}{\varepsilon})^{m_{h}}\right)$, implying Eq. 88.

##  Appendix H Useful Lemmas

######  Lemma 8.

For any two environments $\mathcal{E},\mathcal{E}^{\prime}$ with potentially
different transition and reward functions, and any policy $\pi$, we have

$\displaystyle V_{1,\pi}^{\mathcal{E}}(s_{1})$ $\displaystyle-
V_{1,\pi}^{\mathcal{E}^{\prime}}(s_{1})$
$\displaystyle=\sum_{h=1}^{H}\mathbb{E}_{\pi}^{\mathcal{E}^{\prime}}\left[\mathbb{E}_{s^{\prime}\sim
P_{h}^{\mathcal{E}}(\cdot|s_{h},a_{h})}[V_{h+1,\pi}^{\mathcal{E}}(s^{\prime})]-\mathbb{E}_{s^{\prime}\sim
P_{h}^{\mathcal{E}^{\prime}}(\cdot|s_{h},a_{h})}[V_{h+1,\pi}^{\mathcal{E}}(s^{\prime})]\right]$
$\displaystyle\quad+\sum_{h=1}^{H}\mathbb{E}_{\pi}^{\mathcal{E}^{\prime}}[r_{h}^{\mathcal{E}}(s_{h},a_{h})-r_{h}^{\mathcal{E}^{\prime}}(s_{h},a_{h})]$
$\displaystyle=\sum_{h=1}^{H}\mathbb{E}_{\pi}^{\mathcal{E}^{\prime}}\left[\mathbb{E}_{(s^{\prime},r^{\prime})\sim(P_{h}^{\mathcal{E}}\otimes
r_{h}^{\mathcal{E}})(\cdot|s_{h},a_{h})}[r^{\prime}+V_{h+1,\pi}^{\mathcal{E}}(s^{\prime})]\right.$
$\displaystyle\qquad\qquad\qquad\left.-\mathbb{E}_{(s^{\prime},r^{\prime})\sim(P_{h}^{\mathcal{E}^{\prime}}\otimes
r_{h}^{\mathcal{E}^{\prime}})(\cdot|s_{h},a_{h})}[r^{\prime}+V_{h+1,\pi}^{\mathcal{E}}(s^{\prime})]\right],$

where $V_{H+1,\pi^{*}}^{\mathcal{E}}(\cdot):=0$ and the expectation
$\mathbb{E}_{\pi}^{\mathcal{E}^{\prime}}$ is with respect to $s_{h},a_{h}$.

Note that when rewards are deterministic, we have

$\displaystyle
V_{1,\pi}^{\mathcal{E}}(s_{1})-V_{1,\pi}^{\mathcal{E}^{\prime}}(s_{1})$
$\displaystyle=\sum_{h=1}^{H}\mathbb{E}_{\pi}^{\mathcal{E}^{\prime}}\left[\mathbb{E}_{s^{\prime}\sim
P_{h}^{\mathcal{E}}(\cdot|s_{h},a_{h})}[V_{h+1,\pi}^{\mathcal{E}}(s^{\prime})]-\mathbb{E}_{s^{\prime}\sim
P_{h}^{\mathcal{E}^{\prime}}(\cdot|s_{h},a_{h})}[V_{h+1,\pi}^{\mathcal{E}}(s^{\prime})]\right],$

which is the statements of (Hao and Lattimore,, 2022, Lemma D.3).

###### Proof.

We have

$\displaystyle
V_{1,\pi}^{\mathcal{E}}(s_{1})-V_{1,\pi}^{\mathcal{E}^{\prime}}(s_{1})=(V_{1,\pi}^{\mathcal{E}}(s_{1})-V_{1,\pi}^{\mathcal{E}^{\prime}_{r^{\mathcal{E}}}}(s_{1}))+(V_{1,\pi}^{\mathcal{E}^{\prime}_{r^{\mathcal{E}}}}(s_{1})-V_{1,\pi}^{\mathcal{E}^{\prime}}(s_{1}))$
(90)

where $\mathcal{E}^{\prime}_{r^{\mathcal{E}}}$ is an environment with the
transition functions of $\mathcal{E}^{\prime}$ but reward functions of
$\mathcal{E}$. The first term above may be rewritten using (Hao and
Lattimore,, 2022, Lemma D.3). The second term may be rewritten using the
direct definition of value function as
$V_{1,\pi}^{\mathcal{G}}=\mathbb{E}_{\pi}^{\mathcal{G}}[\sum_{h=1}^{H}r^{\mathcal{G}}(s_{h},a_{h})]$,
which completes the proof. ∎

Pinsker’s lemma is at the center of relating the two concepts of regret and
mutual information. We cite the following variant of the Pinsker’s inequality
from Fact 9 in Russo and Van Roy, (2014).

######  Lemma 9.

For any distribution $P$ and $Q$ such that $P$ is absolutely continuous with
respect to $Q$, any random variable $X:\Omega\to\mathcal{X}$ and any
$g:\mathcal{X}\to\mathbb{R}$ such that $\sup g-\inf g\leq 1$, we have

$\displaystyle\mathbb{E}_{P}[g(x)]-\mathbb{E}_{Q}[g(x)]\leq\sqrt{\frac{1}{2}D_{\mathrm{KL}}(P||Q)}\,.$
(91)

##  Appendix I Mutual information of surrogate environment and history

Recall that by performing the information ratio trick, Cauchy-Schwarz and
Pinsker’s inequality, we obtained the following term in our bound of the
squared regret:

$\displaystyle\frac{1}{2}\sum_{h=1}^{H}\mathbb{E}_{\ell}\left[\mathbb{E}_{\pi^{\ell}_{\text{TS}}}^{\bar{\mathcal{E}}_{\ell}}\left[D_{\mathrm{KL}}\left((P_{h}^{\tilde{\mathcal{E}}^{*}_{\ell}}\otimes
r_{h}^{\tilde{\mathcal{E}}^{*}_{\ell}})(\cdot|s_{h-1}^{\ell},a_{h-1}^{\ell})||(P_{h}^{\bar{\mathcal{E}}_{\ell}}\otimes
r_{h}^{\bar{\mathcal{E}}_{\ell}})(\cdot|s_{h-1}^{\ell},a_{h-1}^{\ell})\right)\right]\right].$

Now we would like to show that the above is
$\frac{1}{2}\mathbb{I}^{\pi^{\ell}_{\text{TS}}}_{\ell}(\tilde{\mathcal{E}}^{*}_{\ell};\mathcal{H}_{\ell,H})$.
To be more careful in our arguments, we need to be reminded of what the random
variable $\mathcal{H}_{\ell,H}$ is. We must view it as
$\mathcal{H}_{\ell,H}=\mathcal{H}_{\ell,H}(\mathcal{E},\pi^{\ell}_{\text{TS}})$
or $\mathcal{H}_{\ell,H}(\mathcal{E},\pi^{*}_{\mathcal{E}_{\text{TS}}})$ where
$\mathcal{E},\mathcal{E}_{\text{TS}}$ are two independent samples of
$\mathbb{P}_{\ell}(\cdot)$, and $\mathcal{E}$ represents the same
$\mathcal{E}$ in the regret above in $\pi^{*}_{\mathcal{E}}$, i.e. the true
environment. Also note that $\mathcal{E},\tilde{\mathcal{E}}^{*}_{\ell}$ are
dependent, as we set $\tilde{\mathcal{E}}^{*}_{\ell},\mathcal{E}$ to have the
same $\zeta$ value.

######  Lemma 10.

With $\tilde{\mathcal{E}}^{*}_{\ell}$ defined according to the proof in
Appendix B, in a Bayesian RL, we have

$\displaystyle\mathbb{I}_{\ell}^{\pi^{\ell}_{\text{TS}}}(\tilde{\mathcal{E}}^{*}_{\ell};\mathcal{H}_{\ell,H})=\sum_{h=1}^{H}\mathbb{E}_{\ell}\left[\mathbb{E}_{\pi^{\ell}_{\text{TS}}}^{\bar{\mathcal{E}}_{\ell}}\left[D_{\mathrm{KL}}\left((P_{h}^{\tilde{\mathcal{E}}^{*}_{\ell}}\otimes
r_{h}^{\tilde{\mathcal{E}}^{*}_{\ell}})(\cdot|s_{h-1}^{\ell},a_{h-1}^{\ell})||(P_{h}^{\bar{\mathcal{E}}_{\ell}}\otimes
r_{h}^{\bar{\mathcal{E}}_{\ell}})(\cdot|s_{h-1}^{\ell},a_{h-1}^{\ell})\right)\right]\right]$

As a special case, when rewards are deterministic, we have

$\displaystyle\mathbb{I}_{\ell}^{\pi^{\ell}_{\text{TS}}}(\tilde{\mathcal{E}}^{*}_{\ell};\mathcal{H}_{\ell,H})=\sum_{h=1}^{H}\mathbb{E}_{\ell}\left[\mathbb{E}_{\pi^{\ell}_{\text{TS}}}^{\bar{\mathcal{E}}_{\ell}}\left[\textit{D}_{\text{KL}}(P_{h}^{\tilde{\mathcal{E}}_{\ell}^{*}}(\cdot|s_{h},a_{h})||P_{h}^{\bar{\mathcal{E}}_{\ell}}(\cdot|s_{h},a_{h})\right]\right].$

###### Proof.

Using the chain rule of mutual information,

$\begin{split}\mathbb{I}^{\pi^{\ell}_{\text{TS}}}_{\ell}(\tilde{\mathcal{E}}^{*}_{\ell};\mathcal{H}_{\ell,H})&=\sum_{h=1}^{H}\mathbb{I}_{\ell}^{\pi^{\ell}_{\text{TS}}}\left(\tilde{\mathcal{E}}^{*}_{\ell};(s_{h}^{\ell},a_{h}^{\ell},r_{h}^{\ell})\big{|}\mathcal{H}_{\ell,h-1}\right)\\\
&=\sum_{h=1}^{H}\mathbb{I}_{\ell}^{\pi^{\ell}_{\text{TS}}}\left(\tilde{\mathcal{E}}^{*}_{\ell};s_{h}^{\ell}\big{|}\mathcal{H}_{\ell,h-1}\right)+\sum_{h=1}^{H}\mathbb{I}_{\ell}^{\pi^{\ell}_{\text{TS}}}\left(\tilde{\mathcal{E}}^{*}_{\ell};a_{h}^{\ell}\big{|}s_{h}^{\ell},\mathcal{H}_{\ell,h-1}\right)\\\
&\quad+\sum_{h=1}^{H}\mathbb{I}_{\ell}^{\pi^{\ell}_{\text{TS}}}\left(\tilde{\mathcal{E}}^{*}_{\ell};r_{h}^{\ell}\big{|}s_{h}^{\ell},a_{h}^{\ell},\mathcal{H}_{\ell,h-1}\right)\,.\end{split}$
(92)

Let us note what is meant by
$\mathbb{I}^{\pi^{\ell}_{\text{TS}}}_{\ell}(\cdot)$ is
$\mathbb{I}_{\ell}(\cdot|\pi^{\ell}_{\text{TS}})$. In Hao and Lattimore,
(2022), the policy $\pi$ used is fixed/independent from the random variables
involved in the mutual information (given $\mathcal{D}_{\ell}$). Here, the
same holds as $\pi^{\ell}_{\text{TS}}$ and $\tilde{\mathcal{E}}^{*}_{\ell}$
are independent.

  * •

For the first term in Eq. (92), by using
$\mathbb{I}(X;Y)=\int\textit{D}_{\text{KL}}(P(Y|x)||P(Y))\operatorname{d}\\!\mathbb{P}(x)$,
and the definition of conditional mutual information, we have

$\small\begin{split}\mathbb{I}_{\ell}&\left(\tilde{\mathcal{E}}^{*}_{\ell};s_{h}^{\ell}\big{|}\mathcal{H}_{\ell,h-1},\pi^{\ell}_{\text{TS}}\right)\\\
&=\int\int
D_{\mathrm{KL}}\left(\mathbb{P}_{\ell}\left(s_{h}^{\ell}=\cdot|\mathcal{H}_{\ell,h-1},\pi^{*}_{\mathcal{E}_{\text{TS}}},\tilde{\mathcal{E}}^{*}_{\ell}\right)||\mathbb{P}_{\ell}\left(s_{h}^{\ell}=\cdot|\mathcal{H}_{\ell,h-1},\pi^{*}_{\mathcal{E}_{\text{TS}}}\right)\right)\\\
&\qquad\qquad\operatorname{d}\\!\mathbb{P}_{\ell}(\tilde{\mathcal{E}}^{*}_{\ell}|\mathcal{H}_{\ell,h-1},\pi^{*}_{\mathcal{E}_{\text{TS}}})\operatorname{d}\\!\mathbb{P}_{\ell}(\mathcal{H}_{\ell,h-1},\pi^{*}_{\mathcal{E}_{\text{TS}}})\\\
&=\int\int
D_{\mathrm{KL}}\left(P_{h}^{\tilde{\mathcal{E}}^{*}_{\ell}}\left(\cdot|s_{h-1}^{\ell},a_{h-1}^{\ell}\right)||\mathbb{P}_{\ell}\left(s_{h}^{\ell}=\cdot|\mathcal{H}_{\ell,h-1},\pi^{*}_{\mathcal{E}_{\text{TS}}}\right)\right)\\\
&\qquad\qquad\operatorname{d}\\!\mathbb{P}_{\ell}(\tilde{\mathcal{E}}^{*}_{\ell}|\mathcal{H}_{\ell,h-1},\pi^{*}_{\mathcal{E}_{\text{TS}}})\operatorname{d}\\!\mathbb{P}_{\ell}(\mathcal{H}_{\ell,h-1},\pi^{*}_{\mathcal{E}_{\text{TS}}})\,.\end{split}$
(93)

Where we substituted
$\mathbb{P}_{\ell}\left(s_{h}^{\ell}=\cdot|\mathcal{H}_{\ell,h-1},\pi^{*}_{\mathcal{E}_{\text{TS}}},\tilde{\mathcal{E}}^{*}_{\ell}\right)=P_{h}^{\tilde{\mathcal{E}}^{*}_{\ell}}\left(\cdot|s_{h-1}^{\ell},a_{h-1}^{\ell}\right)$.
Let us see why this is the case. Let us analyze the meaning of the conditional
on
$(\mathcal{H}_{\ell,h-1},\pi^{*}_{\mathcal{E}_{\text{TS}}},\tilde{\mathcal{E}}^{*}_{\ell})$.
Recall that
$\mathcal{H}_{\ell,h-1}=\mathcal{H}_{\ell,h-1}(\mathcal{E},\pi^{*}_{\mathcal{E}_{\text{TS}}})$.
Since $\tilde{\mathcal{E}}^{*}_{\ell}$ is given, the random variable
$\mathcal{E}$ can only go over the partition
$\Theta_{\zeta(\tilde{\mathcal{E}}^{*}_{\ell})}^{\varepsilon}$. Of course, we
can also drop all conditionals on previous state transitions, except for the
last one $s_{h-1}^{\ell}(\mathcal{E}),a_{h-1}^{\ell}(\mathcal{E})$. Note that
the policy $\pi^{*}_{\mathcal{E}_{\text{TS}}}$ is also irrelevant in this
conditional, since the next state only depends on probability transitions and
not on policy, hence why also we are not using the full notation
$s_{h-1}^{\ell}(\mathcal{E},\pi^{*}_{\mathcal{E}_{\text{TS}}}),a_{h-1}^{\ell}(\mathcal{E},\pi^{*}_{\mathcal{E}_{\text{TS}}})$.
This implies

$\displaystyle\mathbb{P}_{\ell}\left(s_{h}^{\ell}(\mathcal{E})=\cdot|\mathcal{H}_{\ell,h-1},\pi^{*}_{\mathcal{E}_{\text{TS}}},\tilde{\mathcal{E}}^{*}_{\ell}\right)$
$\displaystyle=\mathbb{P}_{\ell}\left(s_{h}^{\ell}(\mathcal{E})=\cdot|s_{h-1}^{\ell}(\mathcal{E}),a_{h-1}^{\ell}(\mathcal{E}),\tilde{\mathcal{E}}^{*}_{\ell}\right)$
(94)
$\displaystyle=\int_{\mathcal{E}}P_{h}^{\mathcal{E}}\left(s_{h}^{\ell}=\cdot|s_{h-1}^{\ell},a_{h-1}^{\ell}\right)\operatorname{d}\\!\mathbb{P}_{\ell}(\mathcal{E}|\zeta(\mathcal{E})$
(95) $\displaystyle=\zeta(\tilde{\mathcal{E}}^{*}_{\ell}))$ (96)
$\displaystyle=P_{h}^{\mathbb{E}_{\ell}[\mathcal{E}|\zeta(\mathcal{E})=\zeta(\tilde{\mathcal{E}}^{*}_{\ell})]}\left(s_{h}^{\ell}=\cdot|s_{h-1}^{\ell},a_{h-1}^{\ell}\right)$
(97)

However, recall that we defined $\tilde{\mathcal{E}}^{*}_{\ell}$ to be the
posterior mean of $\mathcal{E}$ over $\Theta_{k}^{\varepsilon}$, i.e.
$\mathbb{E}_{\ell}[\mathcal{E}|\zeta(\mathcal{E})=\zeta(\tilde{\mathcal{E}}^{*}_{\ell})]=\tilde{\mathcal{E}}^{*}_{\ell}$.
Hence, the average above yields
$P_{h}^{\tilde{\mathcal{E}}^{*}_{\ell}}\left(\cdot|s_{h-1}^{\ell},a_{h-1}^{\ell}\right)$,
as desired. Next, for the second term in the KL-divergence,

$\begin{split}\mathbb{P}_{\ell}\left(s_{h}^{\ell}(\mathcal{E})=\cdot|\mathcal{H}_{\ell,h-1},\pi^{*}_{\mathcal{E}_{\text{TS}}}\right)&=\int\mathbb{P}_{\ell}\left(s_{h}^{\ell}(\mathcal{E})=\cdot|\mathcal{H}_{\ell,h-1},\pi^{*}_{\mathcal{E}_{\text{TS}}},\mathcal{E}\right)\operatorname{d}\\!\mathbb{P}_{\ell}(\mathcal{E}|\mathcal{H}_{\ell,h-1},\pi^{*}_{\mathcal{E}_{\text{TS}}})\\\
&=\int
P_{h}^{\mathcal{E}}(s_{h}^{\ell}=\cdot|s_{h-1}^{\ell},a_{h-1}^{\ell})\operatorname{d}\\!\mathbb{P}_{\ell}(\mathcal{E}|\mathcal{H}_{\ell,h-1},\pi^{*}_{\mathcal{E}_{\text{TS}}})\\\
&=\int
P_{h}^{\mathcal{E}}(s_{h}^{\ell}=\cdot|s_{h-1}^{\ell},a_{h-1}^{\ell})\operatorname{d}\\!\mathbb{P}_{\ell}(\mathcal{E})\\\
&=P_{h}^{\bar{\mathcal{E}}_{\ell}}\left(s_{h}^{\ell}=\cdot|s_{h-1}^{\ell},a_{h-1}^{\ell}\right)\,.\end{split}$
(98)

In the above equations,
$\mathcal{H}_{\ell,h-1},\pi^{*}_{\mathcal{E}_{\text{TS}}}$ are given in the
conditional, and the true environment $\mathcal{E}$ is being integrated. The
second equality was explained in the previous case. Let us explain why
$\operatorname{d}\\!\mathbb{P}_{\ell}(\mathcal{E}|\mathcal{H}_{\ell,h-1},\pi^{*}_{\mathcal{E}_{\text{TS}}})=\operatorname{d}\\!\mathbb{P}_{\ell}(\mathcal{E})$