# Making RL with Preference-based Feedback Efficient
via Randomization

Runzhe Wu111Email<EMAIL_ADDRESS>Wen Sun222Email<EMAIL_ADDRESS>
(Cornell University)

###### Abstract

Reinforcement Learning algorithms that learn from human feedback (RLHF) need
to be efficient in terms of _statistical complexity, computational complexity,
and query complexity_. In this work, we consider the RLHF setting where the
feedback is given in the format of preferences over pairs of trajectories. In
the linear MDP model, by using randomization in algorithm design, we present
an algorithm that is sample efficient (i.e., has near-optimal worst-case
regret bounds) and has polynomial running time (i.e., computational complexity
is polynomial with respect to relevant parameters). Our algorithm further
minimizes the query complexity through a novel randomized active learning
procedure. In particular, our algorithm demonstrates a near-optimal tradeoff
between the regret bound and the query complexity. To extend the results to
more general nonlinear function approximation, we design a model-based
randomized algorithm inspired by the idea of Thompson sampling. Our algorithm
minimizes Bayesian regret bound and query complexity, again achieving a near-
optimal tradeoff between these two quantities. Computation-wise, similar to
the prior Thompson sampling algorithms under the regular RL setting, the main
computation primitives of our algorithm are Bayesian supervised learning
oracles which have been heavily investigated on the empirical side when
applying Thompson sampling algorithms to RL benchmark problems.

##  1 Introduction

Reinforcement learning from human feedback (RLHF) has been widely used across
various domains, including robotics (Jain et al., 2013, 2015) and natural
language processing (Stiennon et al., 2020; Ouyang et al., 2022). Unlike
standard RL, RLHF requires the agent to learn from feedback in the format of
preferences between pairs of trajectories instead of per-step reward since
assigning a dense reward function for each state is challenging in many tasks.
For instance, in natural language generation, rating each generated token
individually is challenging. Hence, it is more realistic to ask humans to
compare two pieces of text and indicate their preference. Recent works have
shown that, by integrating preference-based feedback into the training
process, we can align models with human intention and enable high-quality
human-machine interaction.

Despite the existing empirical applications of RLHF, its theoretical
foundation remains far from satisfactory. Empirically, researchers first learn
reward models from preference-based feedback and then optimize the reward
models via policy gradient-based algorithms such as PPO (Schulman et al.,
2017). Questions such as whether or not the learned reward model is accurate,
whether PPO is sufficient for deep exploration, and how to strategically
collect more feedback on the fly are often ignored. Theoretically, prior works
study the regret bound for RL with preference-based feedback (Saha et al.,
2023; Chen et al., 2022). Despite achieving sublinear worst-case regret, these
algorithms are computationally intractable even for simplified models such as
tabular Markov Decision Processes (MDPs). This means that we cannot easily
leverage the algorithmic ideas in prior work to guide or improve how we
perform RLHF in practice.

In addition to maximizing reward, another important metric in RLHF is the
query complexity since human feedback is expensive to collect. To illustrate,
we note that InstructGPT’s training data comprises a mere 30K instances of
human feedback (Ouyang et al., 2022), which is significantly fewer than the
internet-scale dataset employed for training the GPT-3 base model. This
underscores the challenge of scaling up the size of human feedback datasets.
Ross et al. (2013); Laskey et al. (2016) also pointed out that extensively
querying for feedback puts too much burden on human experts. Empirically,
Lightman et al. (2023) observes that active learning reduces query complexity
and improves the learned reward model. In theory, query complexity is mostly
studied in the settings of active learning, online learning, and bandits
(Cesa-Bianchi et al., 2005; Dekel et al., 2012; Agarwal, 2013; Hanneke and
Yang, 2021; Zhu and Nowak, 2022; Sekhari et al., 2023a, b), but overlooked in
RL.

In this work, _we aim to design new RL algorithms that can learn from
preference-based feedback and can be efficient in statistical complexity
(i.e., regret), computational complexity, and query complexity_. In
particular, we strike a near-optimal balance between regret minimization and
query complexity minimization. To achieve this goal, our key idea is to use
_randomization_ in algorithm design. We summarize our new algorithmic ideas
and key contributions as follows.

  1. 1.

For MDPs with linear structure (i.e., linear MDP (Jin et al., 2020)), we
propose the first RL algorithm that achieves sublinear worst-case regret and
computational efficiency simultaneously with preference-based feedback. Even
when reduced to tabular MDPs, it is still the first to achieve a no-regret
guarantee and computational efficiency. Moreover, it has an active learning
procedure and attains a near-optimal tradeoff between the regret and the query
complexity. Our algorithm adds _random Gaussian noises_ to the learned state-
action-wise reward model and the least-squares value iteration (LSVI)
procedure. Using random noise instead of the UCB-style technique (Azar et al.,
2017) preserves the Markovian property in the reward model and allows one to
use dynamic programming to achieve computation efficiency.

  2. 2.

For function approximation beyond linear, we present a model-based Thompson-
sampling-style algorithm that forms posterior distributions over the
transitions and reward models. Assuming the transition and the reward model
class both have small _$\ell_{1}$ -norm eluder dimension_ – a structural
condition introduced in Liu et al. (2022a) that is more general than the
common $\ell_{2}$-norm eluder dimension (Russo and Van Roy, 2013), we show
that our algorithm again achieves a near-optimal tradeoff between the Bayesian
regret and the Bayesian query complexity. Computation-wise, similar to
previous Thompson sampling algorithms for regular RL (e.g., Osband et al.
(2013)), the primary computation primitives are Bayesian supervised learning
oracles for transition and reward learning.

  3. 3.

Our query conditions for both algorithms are based on variance-style
uncertainty quantification of the preference induced by the randomness of the
reward model. We query for preference feedback only when the uncertainty of
the preference on a pair of trajectories is large. Approximately computing the
uncertainty can be easily done using i.i.d. random reward models drawn from
the reward model distribution, which makes the active query procedure
computationally tractable.

Overall, while our main contribution is on the theoretical side, our
theoretical investigation provides several new practical insights. For
instance, for regret minimization, our algorithms propose to draw a pair of
trajectories with one from the latest policy and the other from an older
policy instead of drawing two trajectories from the same policy (e.g.,
Christiano et al. (2017)), avoiding the situation of drawing two similar
trajectories when the policy becomes more and more deterministic. Our theory
shows that drawing two trajectories from a combination of new and older
policies balances exploration and exploitation better. Another practical
insight is the variance-style uncertainty measure for designing the query
condition. Compared to more standard active learning procedure that relies on
constructing version space and confidence intervals (Dekel et al., 2012;
Puchkin and Zhivotovskiy, 2021; Zhu and Nowak, 2022; Sekhari et al., 2023a,
b), our new approach comes with strong theoretical guarantees and is more
computationally tractable. It is also amenable to existing implementations of
Thompson sampling RL algorithms (e.g., using bootstrapping to approximate the
posterior sampling (Osband et al., 2016a, 2023)).

##  2 Comparison to prior work

RL with preference-based feedback. Many recent works have obtained
statistically efficient algorithms but are computationally inefficient even
for tabular MDPs due to intractable policy search and version space
construction (Chen et al., 2022; Zhan et al., 2023a, b; Saha et al., 2023).
For example, Zhan et al. (2023b); Saha et al. (2023) use the idea from optimal
design and rely on the computation oracle:
$\mathop{\arg\max}_{\pi,\pi^{\prime}\in\Pi}\|\mathbb{E}_{s,a\sim\pi}\phi(s,a)-\mathbb{E}_{s,a\sim\pi^{\prime}}\phi(s,a)\|_{A}$
with some positive definite matrix $A$. Here $\|x\|^{2}_{A}:=x^{\top}Ax$, and
$\phi$ is some state-action feature.333These works typically assume
trajectory-wise feature $\phi(\tau)$ for a trajectory $\tau$. However, even
when specified to state-action-wise features, these algorithms are still
computationally intractable, even in tabular MDPs. It is unclear how to
implement this oracle since standard planning approaches based on dynamic
programming cannot be applied here. In addition, these methods also actively
maintain a policy space by eliminating potentially sub-optimal policies. The
policy class can be exponentially large even in tabular settings, so how to
maintain it computationally efficiently is unclear. We provide a more detailed
discussion on the challenges in achieving computational efficiency in RLHF in
Appendix A.

While the work mentioned above is intractable even for tabular MDPs, there are
some other works that could be computationally efficient but have weaker
statistical results. For instance, very recently, Wang et al. (2023) proposed
a reduction framework that can be computationally efficient (depending on the
base algorithm used in the reduction). However, their algorithms have PAC
bounds while we focus on regret minimization. Moreover, we achieve a near-
optimal balance between regret and query complexity. Novoseller et al. (2020)
proposed a posterior sampling algorithm for tabular MDP but their analysis is
asymptotic (i.e., they do not address exploration, exploitation, and query
complexity tradeoff). Xu et al. (2020) proposed efficient algorithms that do
reward-free exploration. However, it is limited to tabular MDPs and PAC
bounds.

In contrast to the above works, our algorithms aim to achieve efficiency in
statistical, computational, and query complexities simultaneously. Our
algorithms leverage _randomization_ to balance exploration, exploitation, and
feedback query. Randomization allows us to avoid non-standard computational
oracles and only use standard Dynamic Programming based oracles (e.g., value
iteration), which makes our algorithm computationally more tractable. Prior
works that simultaneously achieve efficiency in all three aspects are often
restricted in the bandit and imitation learning settings where the exploration
problem is much easier (Sekhari et al., 2023a).

RL via randomization. There are two lines of work that study RL via
randomization. The first injects random noise into the learning object to
encourage exploration. A typical example is the randomized least-squares value
iteration (RLSVI) (Osband et al., 2016b), which adds Gaussian noise into the
least-squares estimation and achieves near-optimal worst-case regret (Zanette
et al., 2020; Agrawal et al., 2021) for linear MDPs. The other line of work
falls into the Bayesian RL framework and uses Thompson sampling (TS) (Osband
et al., 2013; Osband and Van Roy, 2014b, a; Gopalan and Mannor, 2015; Agrawal
and Jia, 2017; Efroni et al., 2021). These algorithms achieve provable
Bayesian regret upper bound by maintaining posterior distributions over
models.

Active learning. Numerous studies have studied active learning across various
settings (Cesa-Bianchi et al., 2005; Dekel et al., 2012; Agarwal, 2013;
Hanneke and Yang, 2015, 2021; Zhu and Nowak, 2022; Sekhari et al., 2023b, a).
However, most of them focus on the bandits and online learning settings, and
their active learning procedures are usually computationally intractable due
to computing version spaces or upper and lower confidence bounds. In contrast,
we design a variance-style uncertainty quantification for our query condition,
which can be easily estimated by random samples of reward model. This makes
our active learning procedure more computationally tractable.

##  3 Preliminary

Notations. For two real numbers $a$ and $b$, we denote
$[a,b]\coloneqq\\{x:a\leq x\leq b\\}$. For an integer $N$, we denote
$[N]:=\\{1,2,\dots,N\\}$. For a set $\mathcal{S}$, we denote
$\Delta(\mathcal{S})$ as the set of distributions over $\mathcal{S}$. Let
$d_{{\rm{TV}}}(\cdot,\cdot)$ denote the total variation distance.

We consider a finite-horizon Markov decision process (MDP), which is a tuple
$M(\mathcal{S},\mathcal{A},r^{\star},P^{\star},H)$ where $\mathcal{S}$ is the
state space, $\mathcal{A}$ is the action space,
$P^{\star}:\mathcal{S}\times\mathcal{A}\rightarrow\Delta(\mathcal{S})$ is the
transition kernel, $r^{\star}:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$ is
the reward function, and $H$ is the length of the episode. The interaction
proceeds for $T$ rounds. At each round $t\in[T]$, we need to select two
policies $\pi_{t}^{0}$ and $\pi_{t}^{1}$ and execute them separately, which
generates two trajectories $\tau_{t}^{0}$ and $\tau_{t}^{1}$ where
$\tau_{t}^{i}=(s_{t,1}^{i},a_{t,1}^{i},\dots,s_{t,H}^{i},a_{t,H}^{i})$ for
$i\in\\{0,1\\}$. For the ease of notation, we assume a fixed initial state
$s_{1}$. Then, we need to decide whether to make a query for the preference
between $\tau_{t}^{0}$ and $\tau_{t}^{1}$. If making a query, we obtain a
preference feedback $o_{t}\in\\{0,1\\}$ that is sampled from the Bernoulli
distribution:

$\displaystyle\operatorname{Pr}(o_{t}=1\,|\,\tau_{t}^{1},\tau_{t}^{0},r^{\star})=\operatorname{Pr}(\tau_{t}^{1}\text{
is preferred to
}\tau_{t}^{0}\,|\,r^{\star})=\Phi\big{(}r^{\star}(\tau_{t}^{1})-r^{\star}(\tau_{t}^{0})\big{)}$

where
$r^{\star}(\tau_{t}^{i})=\sum_{h=1}^{H}r^{\star}(s_{t,h}^{i},a_{t,h}^{i})$ for
$i\in\\{0,1\\}$ is the trajectory reward, and
$\Phi:\mathbb{R}\rightarrow[0,1]$ is a monotonically increasing link function.
We note that, by symmetry, we have
$\Phi(r^{\star}(\tau_{t}^{0})-r^{\star}(\tau_{t}^{1}))+\Phi(r^{\star}(\tau_{t}^{1})-r^{\star}(\tau_{t}^{0}))=1$.
If not making a query, we receive no feedback.

This feedback model is weaker than the standard RL where the per-step reward
signal is revealed. We impose the following assumption on the link function
$\Phi$, which has appeared in many existing works of RLHF (Saha et al., 2023;
Zhu et al., 2023; Zhan et al., 2023a).

######  Assumption 3.1.

We assume $\Phi$ is differentiable and there exists constants
$\kappa,\overline{\kappa}>0$ such that
$\kappa^{-1}\leq\Phi^{\prime}(x)\leq\overline{\kappa}^{-1}$ for any
$x\in[-H,H]$.

The constants $\kappa$ and $\overline{\kappa}$ characterize the non-linearity
of $\Phi$ and determine the difficulty of estimating the reward from
preference feedback. It is noteworthy that, in the theoretical results of our
algorithms, the bounds depend polynomially on $\kappa$ but logarithmically on
$\overline{\kappa}$. Some typical examples of the link functions are provided
below.

######  Example 3.2 (Link functions).

It is common to have $\Phi(x)=1/(1+\exp(-x))$, which recovers the Bradley-
Terry-Luce (BTL) model (Bradley and Terry, 1952), and we have
$\kappa=2+\exp(-H)+\exp(H)$ and $\overline{\kappa}=4$. Additionally, if the
trajectory-wise reward is scaled within the interval of $[0,1]$, then the
difference in reward will be within the range of $[-1,1]$. In this case,
another common choice of the link function is $\Phi(x)=(x+1)/2$, which results
in $\kappa=\overline{\kappa}=2$.

The goal is to minimize the worst-case regret and the query complexity
simultaneously:

$\displaystyle{\rm{Regret}}_{T}\coloneqq\sum_{t=1}^{T}\Big{(}2V^{\star}(s_{1})-V^{\pi_{t}^{0}}(s_{1})-V^{\pi_{t}^{1}}(s_{1})\Big{)},\quad{\rm{Queries}}_{T}\coloneqq\sum_{t=1}^{T}Z_{t}.$

Here
$V^{\pi}(s_{1})\coloneqq\mathop{\mathbb{E}}_{\pi}[\sum_{h=1}^{H}r^{\star}(s_{h},a_{h})]$
denotes the state-value function of policy $\pi$, and we define
$V^{\star}(s_{1})\coloneqq V^{\pi^{\star}}(s_{1})$ where $\pi^{\star}$ is the
optimal policy that maximizes the state-value function. The variable
$Z_{t}\in\\{0,1\\}$ indicates whether a query is made at round $t$. Note that
the regret looks at the sum of the performance gaps between two pairs of
policies: $(\pi^{\star},\pi^{0}_{t})$ and $(\pi^{\star},\pi^{1}_{t})$. This is
standard in dueling bandits (Yue and Joachims, 2011; Yue et al., 2012; Dudík
et al., 2015; Wu et al., 2023b) and RL with preference-based feedback (Saha et
al., 2023; Chen et al., 2022).

Bayesian RL. We also consider Bayesian RL in this work when learning with
general function approximation. In the Bayesian setting, $P^{\star}$ and
$r^{\star}$ are sampled from some known prior distributions $\rho_{\rm{P}}$
and $\rho_{\rm{r}}$. The goal is to minimize the Bayesian regret and the
Bayesian query complexity:

$\displaystyle{\rm{BayesRegret}}_{T}\coloneqq\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}\Big{(}2V^{\star}(s_{1})-V^{\pi_{t}^{0}}(s_{1})-V^{\pi_{t}^{1}}(s_{1})\Big{)}\right],\,{\rm{BayesQueries}}_{T}\coloneqq\mathop{\mathbb{E}}\left[\sum_{t=1}^{T}Z_{t}\right].$

Here the expectation is taken with respect to the prior distribution over
$P^{\star}$ and $r^{\star}$. We will use Bayesian supervised learning oracles
to compute posteriors over the transition and reward model.

##  4 A model-free randomized algorithm for linear MDPs

In this section, we present a model-free algorithm for linear MDPs which is
defined as follows.

######  Assumption 4.1 (Linear MDP (Jin et al., 2020)).

We assume a known feature map
$\phi:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}^{d}$, an unknown
(signed) measure $\mu:\mathcal{S}\rightarrow\mathbb{R}^{d}$, and an unknown
vector $\theta^{\star}_{{\rm{r}}}$ such that for any
$(s,a)\in\mathcal{S}\times\mathcal{A}$, we have
$P^{\star}(s^{\prime}\,|\,s,a)=\phi^{\top}(s,a)\cdot\mu(s^{\prime})$ and
$r^{\star}(s,a)=\phi^{\top}(s,a)\cdot\theta^{\star}_{{\rm{r}}}$. We assume
$\|\phi(s,a)\|_{2}\leq 1$ for all $(s,a)\in\mathcal{S}\times\mathcal{A}$,
$\int_{\mathcal{S}}\|\mu(s)\|_{2}\mathop{}\mathrm{d}s\leq\sqrt{d}$, and
$\|\theta^{\star}_{{\rm{r}}}\|_{2}\leq B$ for some $B>0$. For a trajectory
$\tau=(s_{1},a_{1},\dots,s_{H},a_{H})$, we define
$\phi(\tau)=\sum_{h=1}^{H}\phi(s_{h},a_{h})$ and assume
$\|\phi(\tau)\|_{2}\leq 1$.

It is known that linear MDPs can capture tabular MDPs by setting
$d=|\mathcal{S}||\mathcal{A}|$ and $\phi(s,a)$ to be the one-hot encoding of
$(s,a)$. In this case, we have $\|\phi(\tau)\|_{2}\leq H$. However, we can
scale it down to get $\|\phi(\tau)\|_{2}\leq 1$ at the expense of scaling $B$
up by $H$. Define $\Theta_{B}=\\{\theta\in\mathbb{R}^{d}:\|\theta\|_{2}\leq
B\\}$, which contains $\theta^{\star}_{{\rm{r}}}$. Note that this symbol is
different from the asymptotic notations $\Theta(\cdot)$ and
$\widetilde{\Theta}(\cdot)$.

###  4.1 Algorithm

The algorithm, called PR-LSVI, is presented in Algorithm 1. At the beginning
of episode $k$, it first computes the maximum likelihood estimate
$\widehat{\theta}_{{\rm{r}},t}$ (Line 3). Computation-wise, while the
likelihood objective is not guaranteed to be concave due to the generality of
$\Phi$, efficient algorithms exist in certain common scenarios. For example,
if $\Phi(x)=1/(1+\exp(-x))$, it recovers the BTL model (Example 3.2). In this
case, the MLE objective is concave in $\theta$ and thus can be solved in
polynomial running time. Moreover, we emphasize that the reward is learned
under trajectory-wise features, which is different from the standard RL
setting where it is learned under state-action features.

Given the MLE $\widehat{\theta}_{{\rm{r}},t}$, it next samples
$\overline{\theta}_{{\rm{r}},t}$ from a Gaussian distribution centered at
$\widehat{\theta}_{{\rm{r}},t}$ (Line 4). Note that the covariance matrix
$\Sigma_{t-1}^{-1}$ uses trajectory-wise features (Line 16) which allows the
randomized Gaussian vector to capture trajectory-wise uncertainty of the
learned reward. The noise aims to encourage exploration. Then, it computes the
least-squares estimate of the state-action value function
$\widehat{\theta}_{{\rm{P}},t,h}$ for each $h\in[H]$ and samples
$\overline{\theta}_{{\rm{P}},t,h}$ from a Gaussian distribution centered at
$\widehat{\theta}_{{\rm{P}},t,h}$ (Lines 7-8). Similar to the reward model,
the noise is added to the state-value function to encourage exploration. We
then define the value function $\overline{Q}_{t,h}$ and $\overline{V}_{t,h}$
as

$\overline{Q}_{t,h}(s,a)\coloneqq{\phi(s,a)^{\top}\overline{\theta}_{{\rm{r}},t}}+\omega_{t,h}(s,a),\qquad\overline{V}_{t,h}(s)\coloneqq\max_{a}\overline{Q}_{t,h}(s,a)$
(1)

and the function $\omega:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ is
defined as

$\displaystyle\omega_{t,h}(s,a)={\begin{cases}\phi(s,a)^{\top}\overline{\theta}_{{\rm{P}},t,h}&\text{if
}\|\phi(s,a)\|_{\Sigma^{-1}_{t-1,h}}\leq\alpha_{\rm{L}}\\\
\rho(s,a)\Big{(}\phi(s,a)^{\top}\overline{\theta}_{{\rm{P}},t,h}\Big{)}+(1-\rho(s,a))(H-h)&\text{if
}\alpha_{\rm{L}}<\|\phi(s,a)\|_{\Sigma^{-1}_{t-1,h}}\leq\alpha_{\rm{U}}\\\
H-h&\text{if }\|\phi(s,a)\|_{\Sigma^{-1}_{t-1,h}}>\alpha_{\rm{U}}\end{cases}}$

where
$\rho(s,a)=(\alpha_{\rm{U}}-\|\phi(s,a)\|_{\Sigma^{-1}_{t-1,h}})/(\alpha_{\rm{U}}-\alpha_{\rm{L}})$
is introduced to interpolate between the two regimes to ensure continuity.
This truncation trick is from Zanette et al. (2020) and turns out to be
crucial. Without such truncation, the value functions $\overline{Q}_{t,h}$ and
$\overline{V}_{t,h}$ could be exponentially large on state-action pairs where
$\phi(s,a)^{\top}\Sigma_{t,h}\phi(s,a)$ is small. Moreover, the usual “value
clipping” trick (i.e., simply constraining the value function within the range
of $[0,H-h+1]$ by clipping) cannot work here since it introduces bias to the
random walk analysis, as also pointed out by Zanette et al. (2020).

Then, the algorithm computes the greedy policy $\pi_{t}^{0}$ with respect to
$\overline{Q}_{t,h}$. The comparator policy $\pi_{t}^{1}$ is simply set to be
the greedy policy from the previous episode, $\pi_{t-1}^{0}$ . In other words,
we are comparing the two most recent greedy policies. This is different from
previous work, which compares the current greedy policy with a fixed
comparator (Wang et al., 2023). Analytically, for our algorithm, the
cumulative regret incurred by $\pi_{t}^{1}$ for all $t\in[T]$ is equivalent to
that incurred by $\pi_{t}^{0}$ for all $t\in[T]$. Hence, it suffices to
compute the regret for one of them and multiply it by two to get the total
regret.

Given the trajectories $\tau_{t}^{0}$ and $\tau_{t}^{1}$ generated by
$\pi_{t}^{0}$ and $\pi_{t}^{1}$, we compute the expected absolute reward
difference between the trajectories under the same noisy distribution of the
reward parameter:

$\mathop{\mathbb{E}}_{\theta_{0},\theta_{1}\sim\mathcal{N}(\widehat{\theta}_{{\rm{r}},t},\sigma_{\rm{r}}^{2}\Sigma^{-1}_{t-1})}\Big{[}\big{|}(\phi(\tau_{t}^{0})-\phi(\tau_{t}^{1}))^{\top}(\theta_{0}-\theta_{1})\big{|}\Big{]}.$
(2)

This represents the uncertainty of the preference between the two
trajectories, and we make a query only when it is larger than a threshold
$\epsilon$ (Line 13). Intuitively, we only make a query on two trajectories
when we are uncertain about the preference (e.g., the expected disagreement
between two randomly sampled reward models is large). Computationally, we can
estimate this expectation by drawing polynomially many reward models from the
distribution
$\mathcal{N}(\widehat{\theta}_{{\rm{r}},t},\sigma_{\rm{r}}^{2}\Sigma^{-1}_{t-1})$
and computing the empirical average. The deviation of the empirical average to
the true mean can be easily bounded by standard concentration inequalities. We
simply use expectation here for analytical simplicity. If the query condition
is triggered, we make a query for feedback on $\tau_{t}^{0},\tau_{t}^{1}$, and
update the trajectory-wise feature covariance matrix accordingly.

Algorithm 1 Preference-based and Randomized Least-Squares Value Iteration (PR-
LSVI)

0: STD $\sigma_{\rm{r}},\sigma_{\rm{P}}$, threshold $\epsilon$, value cutoff
parameters $\alpha_{\rm{L}},\alpha_{\rm{U}}$, and regularization parameter
$\lambda$.

1: Let $\pi_{0}^{0}$ be an arbitrary policy, $\Sigma_{0}\leftarrow\lambda I$,
$\Sigma_{0,h}\leftarrow\lambda I\ (\forall h\in[H])$.

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

3:
$\widehat{\theta}_{{\rm{r}},t}\leftarrow\mathop{\arg\max}_{\theta\in\Theta_{B}}\sum_{s=1}^{t-1}Z_{s}\ln(o_{s}\Phi((\phi(\tau_{s}^{1})-\phi(\tau_{s}^{0}))^{\top}\theta)+(1-o_{s})\Phi((\phi(\tau_{s}^{0})-\phi(\tau_{s}^{1}))^{\top}\theta))$

4:
$\overline{\theta}_{{\rm{r}},t}\sim\mathcal{N}(\widehat{\theta}_{{\rm{r}},t},\sigma_{\rm{r}}^{2}\Sigma^{-1}_{t-1})$

5: $\widehat{\theta}_{{\rm{P}},t,H}\leftarrow 0$,
$\overline{\theta}_{{\rm{P}},t,H}\leftarrow 0$

6: for $h=H-1,\dots,1$ do

7:
$\widehat{\theta}_{{\rm{P}},t,h}\leftarrow\Sigma_{t-1,h}^{-1}(\sum_{i=1}^{t-1}\phi(s_{i,h}^{0},a_{i,h}^{0})\overline{V}_{t,h+1}(s_{i,h+1}^{0}))$

8:
$\overline{\theta}_{{\rm{P}},t,h}\sim\mathcal{N}(\widehat{\theta}_{{\rm{P}},t,h},\sigma_{\rm{P}}^{2}\Sigma_{t-1,h}^{-1})$

9: Define $\overline{Q}_{t,h}$ and $\overline{V}_{t,h}$ as in (1).

10: end for

11: Set
$\pi_{t}^{0}\leftarrow\\{\pi_{t,h}^{0}\>:\>\pi_{t,h}^{0}(s)=\mathop{\arg\max}_{a}\overline{Q}_{t,h}(s,a),\,\forall
s\in\mathcal{S},\,h\in[H]\\}$ and $\pi_{t}^{1}\leftarrow\pi_{t-1}^{0}$.

12: Sample $\tau_{t}^{0}\sim\pi_{t}^{0}$ and $\tau_{t}^{1}\sim\pi_{t}^{1}$.

13:
$Z_{t}\leftarrow\mathds{1}\\{\mathop{\mathbb{E}}_{\theta_{0},\theta_{1}\sim\mathcal{N}(\widehat{\theta}_{{\rm{r}},t},\sigma_{\rm{r}}^{2}\Sigma^{-1}_{t-1})}[|(\phi(\tau_{t}^{0})-\phi(\tau_{t}^{1}))^{\top}(\theta_{0}-\theta_{1})|]>\epsilon\\}$

14: if $Z_{t}=1$ then

15: Quey preference feedback $o_{t}$ on $\\{\tau_{t}^{0},\tau_{t}^{1}\\}$

16:
$\Sigma_{t}\leftarrow\Sigma_{t-1}+(\phi(\tau_{t}^{0})-\phi(\tau_{t}^{1}))(\phi(\tau_{t}^{0})-\phi(\tau_{t}^{1}))^{\top}$

17: else

18: $\Sigma_{t}\leftarrow\Sigma_{t-1}$

19: end if

20:
$\Sigma_{t,h}\leftarrow\Sigma_{t-1,h}+\phi(s_{t,h}^{0},a_{t,h}^{0})\phi^{\top}(s_{t,h}^{0},a_{t,h}^{0})$
$\;(\forall h\in[H])$.

21: end for

###  4.2 Analysis

The theoretical results of Algorithm 1 are stated in Theorem 4.2. The detailed
assignment of hyperparameters can be found in Table 1, and the proof is
provided in Appendix B.

######  Theorem 4.2.

Define $\gamma=\sqrt{\kappa+B^{2}}$, which characterizes the difficulty of
estimating the reward model. Set
$\sigma_{{\rm{r}}}=\widetilde{\Theta}(\gamma\sqrt{d})$,
$\sigma_{{\rm{P}}}=\widetilde{\Theta}(H^{3/2}d^{2}\gamma)$,
$\alpha_{\rm{U}}=(d^{5/2}H^{3/2}\gamma)^{-1}$,
$\alpha_{\rm{L}}=\alpha_{\rm{U}}/2$, and $\lambda=1$. Then, PR-LSVI (Algorithm
1) guarantees the following with probability at least $1-\delta$:

$\displaystyle{\rm{Regret}}_{T}=\widetilde{O}\left(\epsilon
Td^{1/2}+\sqrt{T}\cdot
d^{3}H^{5/2}\gamma+d^{17/2}H^{11/2}\gamma^{3}\right),\quad{\rm{Queries}}_{T}=\widetilde{O}\left(d^{4}\gamma^{4}/\epsilon^{2}\right).$

To further study the balance between the regret and the query complexity, we
let $\epsilon=T^{-\beta}$ for some $\beta\leq 1/2$. Then, the upper bounds in
Theorem 4.2 can be rewritten as

${\rm{Regret}}_{T}=\widetilde{O}(T^{1-\beta}),\quad{\rm{Queries}}_{T}=\widetilde{O}(T^{2\beta})$

where we only focus on the dependence on $T$ and omit any other factors for
simplicity. We see that there is a tradeoff in $T$ between the regret and the
query complexity — the smaller regret we want, the more queries we need to
make. For example, when $\beta=0$, the regret is $\widetilde{O}(T)$, and the
query complexity is $\widetilde{O}(1)$, meaning that we will incur linear
regret if we don’t make any query. If we increase $\beta$ to $1/2$, the regret
decreases to $\widetilde{O}(\sqrt{T})$ while the query complexity increases to
$\widetilde{O}(T)$, meaning that the regret bound is optimal in $T$ but we
make queries every episode.

We emphasize that this tradeoff in $T$ is optimal, as evidenced by a lower
bound result established by Sekhari et al. (2023a). Their lower bound was
originally proposed for contextual dueling bandits, which is a special case of
our setting. Their results are stated below.

######  Theorem 4.3.

(Sekhari et al., 2023a, Theorem 5) The following two claims hold: (1) For any
algorithm, there exists an instance that leads to
${\rm{Regret}}_{T}=\Omega(\sqrt{T})$; (2) For any algorithm achieving an
expected regret upper bound in the form of
$\mathop{\mathbb{E}}[{\rm{Regret}}_{T}]=O(T^{1-\beta})$ for some $\beta>0$,
there exists an instance that results in
$\mathop{\mathbb{E}}[{\rm{Queries}}_{T}]=\Omega(T^{2\beta})$.

It shows that our dependence on $T$ is tight. However, the dependence on other
parameters (e.g., $d$ and $H$) can be loose. We leave further investigation of
these factors as future work.

Although injecting random noise is inspired by RLSVI (Zanette et al., 2020),
we highlight 5 key differences between our analysis and theirs:

  1. 1.

Since the feedback is trajectory-wise, we need to design random noise that
preserves the state-action-wise format (so that it can be used in DP) but
captures the trajectory-wise uncertainty. We do this by maintaining
$\Sigma_{t}$, which uses trajectory-wise feature differences;

  2. 2.

Since the preference feedback is generated from some probabilistic model, we
learn the reward model via MLE and use MLE generalization bound (Geer, 2000)
to capture the uncertainty in the learned reward model. This allows us to use
a more general link function $\Phi$;

  3. 3.

We design a new regret decomposition technique to accommodate preference-based
feedback. Particularly, we decompose regret into a form that characterizes the
reward difference between $\pi_{t}^{0}$ and $\pi_{t}^{1}$:
${\rm{Regret}}_{T}\lesssim\sum_{t=1}^{T}(\overline{V}_{t}-\widetilde{V}_{t})-(V^{\pi_{t}^{0}}-V^{\pi_{t}^{1}})$
where $\overline{V}_{t}$ is an estimate of $V^{\pi^{0}_{t}}$, and
$\widetilde{V}_{t}\coloneqq\mathop{\mathbb{E}}_{\tau\sim\pi_{t}^{1}}[\sum_{h=1}^{H}\phi(s_{h},a_{h})^{\top}\overline{\theta}_{{\rm{r}},t}]$
is an estimate of $V^{\pi^{1}_{t}}$ under the real transition and the learned
reward model. This is different from standard RL (Zanette et al., 2020), and
is necessary since we cannot in general guarantee the learned reward model
will be accurate in a state-action-wise manner under the preference-based
feedback.

  4. 4.

Our algorithms have a new randomized active learning procedure for reducing
the number of queries, and our analysis achieves a near-optimal tradeoff
between regret and query complexity;

  5. 5.

Finally, in every round $t$, we propose to draw a pair of trajectories where
one is from the current greedy policy $\pi^{0}_{t}$ while the other is from
the greedy policy $\pi^{0}_{t-1}$ at the previous round $t-1$. This approach
makes sure that $\pi^{1}_{t}$ is conditionally independent of the random
Gaussian noises introduced at round $t$. This simple trick turns out to be the
key to proving optimism (with a constant probability), i.e.,
$\overline{V}_{t}-\widetilde{V}_{t}\geq V^{\star}-V^{\pi^{1}_{t}}$ (recall
$\widetilde{V}_{t}$ is an estimate of $V^{\pi^{1}_{t}}$ using the current
reward $\overline{\theta}_{{\rm{r}},t}$).

Running time. To assess the time complexity of Algorithm 1, assuming finite
number of actions444This is to ensure that $\arg\max_{a}Q(s,a)$ can be
computed efficiently., all steps can be computed in polynomial running time
(i.e., polynomial in $d,H,A$) except the MLE of the reward model (Line 3),
which depends on the link function $\Phi$. For the popular BTL model where
$\Phi(x)=1/(1+\exp(-x))$, the MLE objective is concave with respect to
$\theta$ and $\theta$ belongs to a convex set $\Theta_{B}$. In this case, we
can use any convex programming algorithms for the MLE procedure (e.g.,
projected gradient ascent).

##  5 A model-based Thompson sampling algorithm

In this section, we aim to extend to nonlinear function approximation. We do
so in a model-based framework with Thompson sampling (TS). The motivation is
that TS is often considered a computationally more tractable alternative to
UCB-style algorithms.

###  5.1 Algorithm

The algorithm, called PbTS, is presented in Algorithm 2. At the beginning of
episode $k$, it computes the reward model posterior $\rho_{{\rm{r}},t}$ and
the transition model posterior $\rho_{{\rm{P}},t}$ (Line 3). Then, it samples
$P_{t}$ and $r_{t}$ from the posteriors and computes the optimal policy
$\pi_{t}^{0}$ assuming the true reward function is $r_{t}$ and the true model
is $P_{t}$ (Line 5). Here we denote $V^{\pi}_{r,P}$ as the state-value
function of $\pi$ under reward function $r$ and model $P$. Note that this
oracle is a standard planning oracle. The comparator policy $\pi_{t}^{1}$ is
simply set to be the policy from the previous episode, $\pi_{t-1}^{0}$, as we
did in Algorithm 1. The two policies then generate respective trajectories
$\tau_{t}^{0}$ and $\tau_{t}^{1}$. To decide whether we should make a query,
we compute the uncertainty quantity under the posterior distribution of the
reward:
$\mathop{\mathbb{E}}_{r,r^{\prime}\sim\rho_{{\rm{r}},t}}[|r(\tau^{0}_{t})-r(\tau^{1}_{t})-(r^{\prime}(\tau^{0}_{t})-r^{\prime}(\tau^{1}_{t}))|],$
which is analogous to (2) in Algorithm 1. We make a query only when it is
larger than a threshold $\epsilon$. Similar to Algorithm 1, we can approximate
this expectation by sampling polynomial many pairs of $r$ and $r^{\prime}$ and
then compute the empirical average.

Algorithm 2 Preference-based Thompson Sampling (PbTS)

0: priors $\rho_{\rm{P}}$ and $\rho_{\rm{r}}$, threshold $\epsilon$.

1: Let $\pi_{0}^{0}$ be an arbitrary policy.

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

3: Compute posteriors:  $\displaystyle\rho_{{\rm{P}},t}(P)\propto\ $
$\displaystyle\rho_{\rm{P}}(P)\prod_{i=1}^{t-1}\prod_{h=1}^{H}P(s_{i,h+1}^{0}\,|\,s_{i,h}^{0},a_{i,h}^{0}),$
$\displaystyle\rho_{{\rm{r}},t}(r)\propto\ $
$\displaystyle\rho_{\rm{r}}(r)\prod_{i=1}^{t-1}\Big{(}o_{i}\Phi\big{(}r(\tau_{i}^{1})-r(\tau_{i}^{0})\big{)}+(1-o_{i})\Phi\big{(}r(\tau_{i}^{0})-r(\tau_{i}^{1})\big{)}\Big{)}^{Z_{i}}.$

4: Sample $P_{t}\sim\rho_{{\rm{P}},t}$ and $r_{t}\sim\rho_{{\rm{r}},t}$.

5: Compute
$\pi_{t}^{0}\leftarrow\mathop{\arg\max}_{\pi}V^{\pi}_{r_{t},P_{t}}(s_{1})$ and
$\pi_{t}^{1}\leftarrow\pi_{t-1}^{0}$.

6: Sample $\tau_{t}^{0}\sim\pi_{t}^{0}$ and $\tau_{t}^{1}\sim\pi_{t}^{1}$.

7:
$Z_{t}\leftarrow\mathds{1}\\{\mathop{\mathbb{E}}_{r,r^{\prime}\sim\rho_{{\rm{r}},t}}[|r(\tau^{0}_{t})-r(\tau^{1}_{t})-(r^{\prime}(\tau^{0}_{t})-r^{\prime}(\tau^{1}_{t}))|]>\epsilon\\}$

8: if $Z_{t}=1$ then

9: Query preference feedback $o_{t}$ on $\\{\tau_{t}^{0},\tau_{t}^{1}\\}$

10: end if

11: end for

###  5.2 Analysis

The theoretical results of Algorithm 2 should rely on the complexity of the
reward and the transition model. In our analysis, we employ two complexity
measures — eluder dimension and bracketing number. We start by introducing a
generic notion of $\ell_{p}$-eluder dimension (Russo and Van Roy, 2013).

######  Definition 5.1 ($\ell_{p}$-norm $\epsilon$-dependence).

Let $p>0$. Let $\mathcal{X}$ and $\mathcal{Y}$ be two sets and
$d(\cdot,\cdot)$ be a distance function on $\mathcal{Y}$. Let
$\mathcal{F}\subseteq\mathcal{X}\rightarrow\mathcal{Y}$ be a function class.
We say an element $x\in\mathcal{X}$ is $\ell_{p}$-norm $\epsilon$-dependent on
$\\{x_{1},x_{2},\dots,x_{n}\\}\subseteq\mathcal{X}$ with respect to
$\mathcal{F}$ and $d$ if any pair of functions $f,f^{\prime}\in\mathcal{F}$
satisfying $\sum_{i=1}^{n}d^{p}(f(x_{i}),f^{\prime}(x_{i}))\leq\epsilon^{p}$
also satisfies $d(f(x),f^{\prime}(x))\leq\epsilon$. Otherwise, we say $x$ is
$\ell_{p}$-norm $\epsilon$-independent of $\\{x_{1},x_{2},\dots,x_{n}\\}$.

######  Definition 5.2 ($\ell_{p}$-norm eluder dimension).

The $\ell_{p}$-norm $\epsilon$-eluder dimension of a function class
$\mathcal{F}\subseteq\mathcal{X}\rightarrow\mathcal{Y}$, denoted by
${\rm{dim}}_{p}(\mathcal{F},\epsilon,d)$, is the length of the longest
sequence of elements in $\mathcal{X}$ satisfying that there exists some
$\epsilon^{\prime}\geq\epsilon$ such that every element in the sequence is
$\ell_{p}$-norm $\epsilon^{\prime}$-independent of its predecessors.

One can verify that the eluder dimension is monotonically non-decreasing in
$p$, i.e.,
${\rm{dim}}_{p}(\mathcal{F},\epsilon,d)\leq{\rm{dim}}_{q}(\mathcal{F},\epsilon,d)$
for any $p\leq q$. In the analysis, we will focus on $\ell_{1}$-norm and
$\ell_{2}$-norm eluder dimension, which have been used in the literature of
nonlinear bandits and RL extensively (Wen and Van Roy, 2013; Osband and Van
Roy, 2014a; Jain et al., 2015; Wang et al., 2020; Ayoub et al., 2020; Foster
et al., 2021; Ishfaq et al., 2021; Chen et al., 2022; Liu et al., 2022a;
Sekhari et al., 2023a, b). Examples where the eluder dimension is small
include linear functions, generalized linear models, and functions in
Reproducing Kernel Hilbert Space (RKHS).

The other complexity measure we use is the bracketing number (Van de Geer,
2000).

######  Definition 5.3 (Bracketing number).

Consider a function class
$\mathcal{F}\subseteq\mathcal{X}\rightarrow\mathbb{R}$. Given two functions
$l,u:\mathcal{X}\rightarrow\mathbb{R}$, the bracket $[l,u]$ is defined as the
set of functions $f\in\mathcal{F}$ with $l(x)\leq f(x)\leq u(x)$ for all
$x\in\mathcal{X}$. It is called an $\omega$-bracket if $\|l-u\|\leq\omega$.
The bracketing number of $\mathcal{F}$ w.r.t. the metric $\|\cdot\|$, denoted
by $N_{[]}(\omega,\mathcal{F},\|\cdot\|)$, is the minimum number of
$\omega$-brackets needed to cover $\mathcal{F}$.

The logarithm of the bracketing number is small in many common scenarios,
which has been extensively examined by previous studies (e.g., Van de Geer
(2000)) for deriving MLE generalization bound (Agarwal et al., 2020; Uehara
and Sun, 2021; Liu et al., 2022b, 2023). For example, when $\mathcal{F}$ is
finite, the bracketing number is bounded by its size. When $\mathcal{F}$ is a
$d$-dimensional linear function class, the logarithm of the bracketing number
is upper bounded by $d$ up to logarithmic factors.

It is worth noting that while we will employ both measures to the model class
$\mathcal{P}$, we can not similarly apply them to the reward class
$\mathcal{R}$. Instead, we have to rely on the complexity of the following
function class, $\widetilde{\mathcal{R}}$, which comprises functions mapping
pairs of trajectories to reward differences:

$\displaystyle\widetilde{\mathcal{R}}\coloneqq\bigg{\\{}\widetilde{r}\>:\>\widetilde{r}(\tau^{0},\tau^{1})=$
$\displaystyle\sum_{h=1}^{H}r(s_{h}^{0},a_{h}^{0})-r(s_{h}^{1},a_{h}^{1}),\,\forall\tau^{i}=\\{s_{h}^{i},a_{h}^{i}\\}_{h},i\in\\{0,1\\},r\in\mathcal{R}\Bigg{\\}}.$
(3)

The reason that we have to use $\widetilde{\mathcal{R}}$ instead of
$\mathcal{R}$ is that we only receive preference feedback, and thus we can
only learn the reward function in terms of difference.

Now we are ready to state our main results. The proofs are provided in
Appendix C.

######  Theorem 5.4.

PbTS (Algorithm 2) guarantees that

$\displaystyle{\rm{BayesRegret}}_{T}=\widetilde{O}\bigg{(}$ $\displaystyle
T\epsilon+H^{2}\cdot{\rm{dim}}_{1}\Big{(}\mathcal{P},1/T\Big{)}\cdot\sqrt{T\cdot\iota_{\mathcal{P}}}+\kappa\cdot{\rm{dim}}_{1}\Big{(}\widetilde{\mathcal{R}},1/T\Big{)}\cdot\sqrt{T\cdot\iota_{\mathcal{R}}}\bigg{)},$
$\displaystyle{\rm{BayesQueries}}_{T}=\widetilde{O}\bigg{(}$
$\displaystyle\min\left\\{\frac{\kappa\sqrt{T\cdot\iota_{\mathcal{R}}}}{\epsilon}\cdot{\rm{dim}}_{1}\Big{(}\widetilde{\mathcal{R}},\epsilon/2\Big{)},\,\frac{\kappa^{2}\cdot\iota_{\mathcal{R}}}{\epsilon^{2}}\cdot{\rm{dim}}_{2}\Big{(}\widetilde{\mathcal{R}},\epsilon/2\Big{)}\right\\}\bigg{)}$

where we denote
$\iota_{\mathcal{P}}\coloneqq\log(N_{[]}((HT|\mathcal{S}|)^{-1},\mathcal{P},\|\cdot\|_{\infty}))$
and
$\iota_{\mathcal{R}}\coloneqq\log(N_{[]}(\overline{\kappa}(2T)^{-1},\widetilde{\mathcal{R}},\|\cdot\|_{\infty}))$.

Similar to the analysis of Algorithm 1, we study the balance between the
Bayesian regret and the query complexity by setting $\epsilon=T^{-\beta}$ for
some $\beta\leq 1/2$. Then, we can simplify the regret and query complexity as
${\rm{BayesRegret}}_{T}=\widetilde{O}(T^{1-\beta})$ and

${\rm{BayesQueries}}_{T}=\widetilde{O}\bigg{(}\min\bigg{\\{}\underbrace{T^{\beta+\frac{1}{2}}\cdot{\rm{dim}}_{1}\Big{(}\widetilde{\mathcal{R}},\epsilon/2\Big{)}}_{\rm(i)},\;\underbrace{T^{2\beta}\cdot{\rm{dim}}_{2}\Big{(}\widetilde{\mathcal{R}},\epsilon/2\Big{)}}_{\rm(ii)}\bigg{\\}}\bigg{)}$

where we have hidden all factors except $T$ and the eluder dimension for
brevity. We see that there is again a tradeoff in $T$ between the Bayesian
regret and the query complexity, similar to what we have observed in Theorem
4.2. The term (ii) demonstrates that the tradeoff in $T$ is again optimal as
evidenced by the lower bound result (Theorem 4.3). Moreover, term (i) further
improves the dependence on the eluder dimension (recalling that
$\ell_{1}$-norm eluder dimension is strictly smaller than the $\ell_{2}$-norm
version). However, the $T$-dependence becomes worse. It would be desired to
derive a query complexity upper bound that scale as
$\widetilde{O}(T^{2\beta}\cdot{\rm{dim}}_{1}(\widetilde{\mathcal{R}},\epsilon/2))$,
which attains the favorable dependence on both $T$ and the $\ell_{1}$-norm
eluder dimension. We leave this as future work.

We emphasize that the Bayesian regret analysis in Theorem 5.4 is not a trivial
extension of previous TS algorithms (Osband et al., 2013; Osband and Van Roy,
2014b, a; Gopalan and Mannor, 2015; Agrawal and Jia, 2017; Novoseller et al.,
2020). We highlight four main differences below.

  1. 1.

Preference-based regret decomposition. The feedback is preference-based, which
necessitates a new Bayesian regret decomposition:

$\displaystyle{\rm{BayesRegret}}_{T}=\underbrace{\sum_{t=0}^{T}\mathop{\mathbb{E}}\left[V^{\pi_{t}^{0}}_{r_{t},P_{t}}-V^{\pi_{t}^{0}}_{r_{t},P^{\star}}\right]}_{\mathtt{T}_{\rm{model}}}+\underbrace{\sum_{t=0}^{T}\mathop{\mathbb{E}}\left[\Big{(}V^{\pi_{t}^{0}}_{r_{t},P^{\star}}-V^{\pi_{t}^{1}}_{r_{t},P^{\star}}\Big{)}-\Big{(}V^{\pi_{t}^{0}}_{r^{\star},P^{\star}}-V^{\pi_{t}^{1}}_{r^{\star},P^{\star}}\Big{)}\right]}_{\mathtt{T}_{\rm{reward}}}.$

Recall that we denote $V^{\pi}_{r,P}$ as the state-value function of $\pi$
under reward function $r$ and model $P$. Here $\mathtt{T}_{\rm{model}}$ and
$\mathtt{T}_{\rm{reward}}$ are the regret incurred due to model and reward
misspecification, respectively. We highlight that $\mathtt{T}_{\rm{reward}}$
characterizes the misspecification in terms of the reward difference between
$\pi_{t}^{0}$ and $\pi_{t}^{1}$, which is different from the standard Bayesian
RL.

  2. 2.

MLE-based version space. Unlike prior works (Russo and Van Roy, 2014), we do
not rely on upper confidence bounds (UCB) or the idea of optimism. Instead, we
construct version spaces by the classic MLE generalization bound. Let us take
the reward learning as an example. Given the historical preference data
$\\{\tau_{i}^{0},\tau_{i}^{1},o_{i}\\}_{i=1}^{t-1}$, we construct the version
space at round $t$ as

$\displaystyle\mathcal{V}_{t}=$
$\displaystyle\left\\{r\in\mathcal{R}\>:\>\sum_{i=1}^{t-1}d_{{\rm{TV}}}^{2}\left(\operatorname{Pr}(\cdot\,|\,\tau_{i}^{1},\tau_{i}^{0},\widehat{r}_{t}),\,\operatorname{Pr}(\cdot\,|\,\tau_{i}^{1},\tau_{i}^{0},r)\right)\leq\beta\right\\}$

where
$\widehat{r}_{t}\coloneqq\mathop{\arg\max}_{r}\log\sum_{i=1}^{t-1}\operatorname{Pr}(o_{i}\,|\,\tau_{i}^{1},\tau_{i}^{0},r)$
is the MLE from the preference data and $\beta$ is a parameter tuned
appropriately to ensure $r^{\star}\in\mathcal{V}_{t}$ with probability at
least $1/T$. We then show for $r_{t}$ and $r^{\star}$, which are sampled from
the reward posterior distribution, the probability that either of them not
belonging to $\mathcal{V}_{t}$ is small, i.e.,
$\mathop{\mathbb{E}}[\mathds{1}\left\\{r_{t}\not\in\mathcal{V}_{t}\text{ or
}r^{\star}\not\in\mathcal{V}_{t}\right\\}]=O(1/T)$. Our analysis only uses
$\mathcal{V}_{t}$.

  3. 3.

$\ell_{1}$-norm eluder dimension dependence. Our analysis uses the tighter
$\ell_{1}$-norm eluder dimension (specifically, our regret bound exclusively
depends on $\ell_{1}$-eluder dimension), which is strictly better than the
$\ell_{2}$-norm eluder dimension used in prior work.

  4. 4.

Active learning procedure. We also equipped it with a randomized active
learning procedure for query complexity minimization, which has not been
presented in prior work.

Computation. The computational bottleneck of Algorithm 2 lies in the
computation of the posterior distribution (Line 3). Prior TS works have used
Bootstrapping to approximate posterior sampling (Osband et al., 2016a, 2023)
and achieved competitive performance in common RL benchmarks.

Non-Markovian reward. Algorithm 2 can be easily extended to the case where the
reward function is non-Markovian (i.e., reward model $r(\tau)$ is trajectory-
wise) without any change in the algorithm and the analysis. Here we present it
with Markovian reward for the consistency with Algorithm 1 and for the purpose
of using a standard planning oracle for computing an optimal policy given a
pair of reward and transition. While non-Markovian reward is more general, it
is unclear how to solve the planning problem efficiently for a non-Markovian
reward in tabular MDPs. This computation intractability in the planning phase
makes non-Markovian rewards not easily applicable in practice.

##  6 Conclusion

We use randomization to design new algorithms for RL with preference-based
feedback. Randomization allows us to minimize regret and query complexity
while at the same time maintaining computation efficiency. Concretely, for
linear models, our randomized algorithms achieve a near-optimal balance
between the worst-case reward regret and query complexity with a polynomial
computation complexity. For models beyond linear, using $\ell_{1}$-eluder
dimension as a structural complexity measure for function approximation, we
present a TS-inspired algorithm that balances Bayesian regret and Bayesian
query complexity nearly optimally.

## References

  * Abbasi-Yadkori et al. (2011) Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári.  Improved algorithms for linear stochastic bandits.  _Advances in neural information processing systems_ , 24, 2011.
  * Abeille and Lazaric (2017) Marc Abeille and Alessandro Lazaric.  Linear thompson sampling revisited.  In _Artificial Intelligence and Statistics_ , pages 176–184. PMLR, 2017.
  * Agarwal (2013) Alekh Agarwal.  Selective sampling algorithms for cost-sensitive multiclass prediction.  In _International Conference on Machine Learning_ , pages 1220–1228. PMLR, 2013.
  * Agarwal et al. (2020) Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun.  Flambe: Structural complexity and representation learning of low rank mdps.  _Advances in neural information processing systems_ , 33:20095–20107, 2020.
  * Agrawal et al. (2021) Priyank Agrawal, Jinglin Chen, and Nan Jiang.  Improved worst-case regret bounds for randomized least-squares value iteration.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pages 6566–6573, 2021.
  * Agrawal and Jia (2017) Shipra Agrawal and Randy Jia.  Optimistic posterior sampling for reinforcement learning: worst-case regret bounds.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Ayoub et al. (2020) Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang.  Model-based reinforcement learning with value-targeted regression.  In _International Conference on Machine Learning_ , pages 463–474. PMLR, 2020.
  * Azar et al. (2017) Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos.  Minimax regret bounds for reinforcement learning.  In _International Conference on Machine Learning_ , pages 263–272. PMLR, 2017.
  * Bradley and Terry (1952) Ralph Allan Bradley and Milton E Terry.  Rank analysis of incomplete block designs: I. the method of paired comparisons.  _Biometrika_ , 39(3/4):324–345, 1952.
  * Cesa-Bianchi et al. (2005) Nicolo Cesa-Bianchi, Gábor Lugosi, and Gilles Stoltz.  Minimizing regret with label efficient prediction.  _IEEE Transactions on Information Theory_ , 51(6):2152–2162, 2005.
  * Chatterji et al. (2021) Niladri Chatterji, Aldo Pacchiano, Peter Bartlett, and Michael Jordan.  On the theory of reinforcement learning with once-per-episode feedback.  _Advances in Neural Information Processing Systems_ , 34:3401–3412, 2021.
  * Chen et al. (2022) Xiaoyu Chen, Han Zhong, Zhuoran Yang, Zhaoran Wang, and Liwei Wang.  Human-in-the-loop: Provably efficient preference-based reinforcement learning with general function approximation.  In _International Conference on Machine Learning_ , pages 3773–3793. PMLR, 2022.
  * Christiano et al. (2017) Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei.  Deep reinforcement learning from human preferences.  _Advances in neural information processing systems_ , 30, 2017.
  * Dekel et al. (2012) Ofer Dekel, Claudio Gentile, and Karthik Sridharan.  Selective sampling and active learning from single and multiple experts.  _The Journal of Machine Learning Research_ , 13(1):2655–2697, 2012.
  * Dudík et al. (2015) Miroslav Dudík, Katja Hofmann, Robert E Schapire, Aleksandrs Slivkins, and Masrour Zoghi.  Contextual dueling bandits.  In _Conference on Learning Theory_ , pages 563–587. PMLR, 2015.
  * Efroni et al. (2021) Yonathan Efroni, Nadav Merlis, and Shie Mannor.  Reinforcement learning with trajectory feedback.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 35, pages 7288–7295, 2021.
  * Foster et al. (2021) Dylan Foster, Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu.  Instance-dependent complexity of contextual bandits and reinforcement learning: A disagreement-based perspective.  In _Conference on Learning Theory_ , pages 2059–2059. PMLR, 2021.
  * Geer (2000) Sara A Geer.  _Empirical Processes in M-estimation_ , volume 6.  Cambridge university press, 2000.
  * Gopalan and Mannor (2015) Aditya Gopalan and Shie Mannor.  Thompson sampling for learning parameterized markov decision processes.  In _Conference on Learning Theory_ , pages 861–898. PMLR, 2015.
  * Hanneke and Yang (2015) Steve Hanneke and Liu Yang.  Minimax analysis of active learning.  _J. Mach. Learn. Res._ , 16(1):3487–3602, 2015.
  * Hanneke and Yang (2021) Steve Hanneke and Liu Yang.  Toward a general theory of online selective sampling: Trading off mistakes and queries.  In _International Conference on Artificial Intelligence and Statistics_ , pages 3997–4005. PMLR, 2021.
  * Ishfaq et al. (2021) Haque Ishfaq, Qiwen Cui, Viet Nguyen, Alex Ayoub, Zhuoran Yang, Zhaoran Wang, Doina Precup, and Lin Yang.  Randomized exploration in reinforcement learning with general value function approximation.  In _International Conference on Machine Learning_ , pages 4607–4616. PMLR, 2021.
  * Jain et al. (2013) Ashesh Jain, Brian Wojcik, Thorsten Joachims, and Ashutosh Saxena.  Learning trajectory preferences for manipulators via iterative improvement.  _Advances in neural information processing systems_ , 26, 2013.
  * Jain et al. (2015) Ashesh Jain, Shikhar Sharma, Thorsten Joachims, and Ashutosh Saxena.  Learning preferences for manipulation tasks from online coactive feedback.  _The International Journal of Robotics Research_ , 34(10):1296–1313, 2015.
  * Jin et al. (2020) Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan.  Provably efficient reinforcement learning with linear function approximation.  In _Conference on Learning Theory_ , pages 2137–2143. PMLR, 2020.
  * Laskey et al. (2016) Michael Laskey, Sam Staszak, Wesley Yu-Shu Hsieh, Jeffrey Mahler, Florian T Pokorny, Anca D Dragan, and Ken Goldberg.  Shiv: Reducing supervisor burden in dagger using support vectors for efficient learning from demonstrations in high dimensional state spaces.  In _2016 IEEE International Conference on Robotics and Automation (ICRA)_ , pages 462–469. IEEE, 2016.
  * Lightman et al. (2023) Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe.  Let’s verify step by step.  _arXiv preprint arXiv:2305.20050_ , 2023.
  * Liu et al. (2022a) Qinghua Liu, Alan Chung, Csaba Szepesvári, and Chi Jin.  When is partially observable reinforcement learning not scary?  In _Conference on Learning Theory_ , pages 5175–5220. PMLR, 2022a.
  * Liu et al. (2022b) Qinghua Liu, Csaba Szepesvári, and Chi Jin.  Sample-efficient reinforcement learning of partially observable markov games.  _Advances in Neural Information Processing Systems_ , 35:18296–18308, 2022b.
  * Liu et al. (2023) Qinghua Liu, Praneeth Netrapalli, Csaba Szepesvari, and Chi Jin.  Optimistic mle: A generic model-based algorithm for partially observable sequential decision making.  In _Proceedings of the 55th Annual ACM Symposium on Theory of Computing_ , pages 363–376, 2023.
  * Novoseller et al. (2020) Ellen Novoseller, Yibing Wei, Yanan Sui, Yisong Yue, and Joel Burdick.  Dueling posterior sampling for preference-based reinforcement learning.  In _Conference on Uncertainty in Artificial Intelligence_ , pages 1029–1038. PMLR, 2020.
  * Osband and Van Roy (2014a) Ian Osband and Benjamin Van Roy.  Model-based reinforcement learning and the eluder dimension.  _Advances in Neural Information Processing Systems_ , 27, 2014a.
  * Osband and Van Roy (2014b) Ian Osband and Benjamin Van Roy.  Near-optimal reinforcement learning in factored mdps.  _Advances in Neural Information Processing Systems_ , 27, 2014b.
  * Osband et al. (2013) Ian Osband, Daniel Russo, and Benjamin Van Roy.  (more) efficient reinforcement learning via posterior sampling.  _Advances in Neural Information Processing Systems_ , 26, 2013.
  * Osband et al. (2016a) Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy.  Deep exploration via bootstrapped dqn.  _Advances in neural information processing systems_ , 29, 2016a.
  * Osband et al. (2016b) Ian Osband, Benjamin Van Roy, and Zheng Wen.  Generalization and exploration via randomized value functions.  In _International Conference on Machine Learning_ , pages 2377–2386. PMLR, 2016b.
  * Osband et al. (2023) Ian Osband, Zheng Wen, Seyed Mohammad Asghari, Vikranth Dwaracherla, Morteza Ibrahimi, Xiuyuan Lu, and Benjamin Van Roy.  Approximate thompson sampling via epistemic neural networks.  _arXiv preprint arXiv:2302.09205_ , 2023.
  * Ouyang et al. (2022) Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al.  Training language models to follow instructions with human feedback.  _Advances in Neural Information Processing Systems_ , 35:27730–27744, 2022.
  * Pollard (1990) David Pollard.  Empirical processes: theory and applications.  Ims, 1990.
  * Puchkin and Zhivotovskiy (2021) Nikita Puchkin and Nikita Zhivotovskiy.  Exponential savings in agnostic active learning through abstention.  In _Conference on Learning Theory_ , pages 3806–3832. PMLR, 2021.
  * Ross et al. (2013) Stéphane Ross, Narek Melik-Barkhudarov, Kumar Shaurya Shankar, Andreas Wendel, Debadeepta Dey, J Andrew Bagnell, and Martial Hebert.  Learning monocular reactive uav control in cluttered natural environments.  In _2013 IEEE international conference on robotics and automation_ , pages 1765–1772. IEEE, 2013.
  * Russo and Van Roy (2013) Daniel Russo and Benjamin Van Roy.  Eluder dimension and the sample complexity of optimistic exploration.  _Advances in Neural Information Processing Systems_ , 26, 2013.
  * Russo and Van Roy (2014) Daniel Russo and Benjamin Van Roy.  Learning to optimize via posterior sampling.  _Mathematics of Operations Research_ , 39(4):1221–1243, 2014.
  * Saha et al. (2023) Aadirupa Saha, Aldo Pacchiano, and Jonathan Lee.  Dueling rl: Reinforcement learning with trajectory preferences.  In _International Conference on Artificial Intelligence and Statistics_ , pages 6263–6289. PMLR, 2023.
  * Schulman et al. (2017) John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.  Proximal policy optimization algorithms.  _arXiv preprint arXiv:1707.06347_ , 2017.
  * Sekhari et al. (2023a) Ayush Sekhari, Karthik Sridharan, Wen Sun, and Runzhe Wu.  Contextual bandits and imitation learning via preference-based active queries.  _arXiv preprint arXiv:2307.12926_ , 2023a.
  * Sekhari et al. (2023b) Ayush Sekhari, Karthik Sridharan, Wen Sun, and Runzhe Wu.  Selective sampling and imitation learning via online regression.  _arXiv preprint arXiv:2307.04998_ , 2023b.
  * Stiennon et al. (2020) Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano.  Learning to summarize with human feedback.  _Advances in Neural Information Processing Systems_ , 33:3008–3021, 2020.
  * Uehara and Sun (2021) Masatoshi Uehara and Wen Sun.  Pessimistic model-based offline reinforcement learning under partial coverage.  In _International Conference on Learning Representations_ , 2021.
  * Van de Geer (2000) Sara Van de Geer.  _Empirical Processes in M-estimation_ , volume 6.  Cambridge university press, 2000.
  * Wang et al. (2020) Ruosong Wang, Russ R Salakhutdinov, and Lin Yang.  Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension.  _Advances in Neural Information Processing Systems_ , 33:6123–6135, 2020.
  * Wang et al. (2023) Yuanhao Wang, Qinghua Liu, and Chi Jin.  Is rlhf more difficult than standard rl?  _arXiv preprint arXiv:2306.14111_ , 2023.
  * Wen and Van Roy (2013) Zheng Wen and Benjamin Van Roy.  Efficient exploration and value function generalization in deterministic systems.  _Advances in Neural Information Processing Systems_ , 26, 2013.
  * Wu et al. (2023a) Runzhe Wu, Masatoshi Uehara, and Wen Sun.  Distributional offline policy evaluation with predictive error guarantees.  In _International Conference on Machine Learning_ , pages 37685–37712. PMLR, 2023a.
  * Wu et al. (2023b) Yue Wu, Tao Jin, Hao Lou, Farzad Farnoud, and Quanquan Gu.  Borda regret minimization for generalized linear dueling bandits.  _arXiv preprint arXiv:2303.08816_ , 2023b.
  * Xu et al. (2020) Yichong Xu, Ruosong Wang, Lin Yang, Aarti Singh, and Artur Dubrawski.  Preference-based reinforcement learning with finite-time guarantees.  _Advances in Neural Information Processing Systems_ , 33:18784–18794, 2020.
  * Yue and Joachims (2011) Yisong Yue and Thorsten Joachims.  Beat the mean bandit.  In _Proceedings of the 28th international conference on machine learning (ICML-11)_ , pages 241–248. Citeseer, 2011.
  * Yue et al. (2012) Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims.  The k-armed dueling bandits problem.  _Journal of Computer and System Sciences_ , 78(5):1538–1556, 2012.
  * Zanette et al. (2020) Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric.  Frequentist regret bounds for randomized least-squares value iteration.  In _International Conference on Artificial Intelligence and Statistics_ , pages 1954–1964. PMLR, 2020.
  * Zhan et al. (2023a) Wenhao Zhan, Masatoshi Uehara, Nathan Kallus, Jason D Lee, and Wen Sun.  Provable offline reinforcement learning with human feedback.  _arXiv preprint arXiv:2305.14816_ , 2023a.
  * Zhan et al. (2023b) Wenhao Zhan, Masatoshi Uehara, Wen Sun, and Jason D Lee.  How to query human feedback efficiently in rl?  _arXiv preprint arXiv:2305.18505_ , 2023b.
  * Zhu et al. (2023) Banghua Zhu, Jiantao Jiao, and Michael I Jordan.  Principled reinforcement learning with human feedback from pairwise or $k$-wise comparisons.  _arXiv preprint arXiv:2301.11270_ , 2023.
  * Zhu and Nowak (2022) Yinglun Zhu and Robert Nowak.  Efficient active learning with abstention.  _Advances in Neural Information Processing Systems_ , 35:35379–35391, 2022.

##  Appendix A Computational challenges in RL with preference-based feedback

For RL with preference-based feedback, there is currently no algorithm that
achieves sublinear worst-case regret and computational efficiency
simultaneously, even for tabular MDPs. In this section, we discuss the
challenges that hindered previous works from being computationally efficient.
Specifically, the reasons are twofold:

(1) Trajectory-wise information. The feedback is trajectory-wise, meaning that
we only receive information about cumulative rewards instead of per-step
rewards. In this case, there is no longer a ground truth per-step reward
signal. To see this, consider an MDP with two steps and a trajectory with a
cumulative reward of 1. Then, we cannot decide the respective per-step reward
for the two steps — it could be that the first step has reward 1 and the
second has reward 0, or both have reward 0.5. The preference-based feedback is
strictly harder than trajectory-wise reward feedback, and thus the same issue
persists. This invalidates all algorithms relying on per-step reward
information (e.g., UCBVI [Azar et al., 2017]) and necessitates leveraging
feedback signal at a trajectory level. However, trajectory-level approaches
typically entail maintaining a version space via trajectory constraints [Saha
et al., 2023, Chen et al., 2022, Zhan et al., 2023a], and the computational
complexity of searching within this version space is at least exponential in
the length of the episode. Some works circumvent this computational obstacle
by additional assumptions (e.g., explorability [Chatterji et al., 2021]),
which are restrictive and do not generally hold even in tabular MDPs.

(2) Preference-based information. The feedback relies on a pair of policies.
Standard algorithms based on a single policy become computationally
intractable when adapting to this setting since optimizing over a pair of
policies simultaneously is qualitatively different. For example, Zhan et al.
[2023b], Saha et al. [2023] use the idea from optimal design and need the
computation oracle:
$\mathop{\arg\max}_{\pi,\pi^{\prime}\in\Pi}\|\mathbb{E}_{s,a\sim\pi}\phi(s,a)-\mathbb{E}_{s,a\sim\pi^{\prime}}\phi(s,a)\|_{A}$
for some positive definite matrix $A$. Here $\|x\|^{2}_{A}:=x^{\top}Ax$, and
$\phi$ is some state-action wise feature.555These prior work typically assume
trajectory wise feature $\phi(\tau)$ for a state-action wise trajectory
$\tau$. However, even when specializing to state-action-wise features, these
algorithms are still not computationally tractable even in tabular MDPs. It is
unclear how to implement this oracle since standard planning approaches
relying on dynamic programming cannot be applied here. Additionally, these
methods also require actively maintaining a policy space $\Pi$ by eliminating
potentially sub-optimal policies. The policy class can be exponentially large
even in tabular settings, so it is unclear how to maintain a valid policy
space in a computationally tractable manner.

These challenges motivate us to devise a novel algorithm using a technique
distinct from previous approaches. Our solution centers around the concept of
randomization, which allows us to balance exploration and exploitation and
thus enable standard efficient computation oracles (e.g., DP-style planning
oracle like value iteration).

##  Appendix B Proof of Theorem 4.2

###  B.1 Notations

We define some symbols and their values in Table 1. We have categorized them
into four classes for the ease of reference.

Table 1: Symbols and their respective values. Symbol | Value
---|---
(1) Error components
$\xi_{{\rm{r}},t}$ | $\overline{\theta}_{{\rm{r}},t}-\widehat{\theta}_{{\rm{r}},t}$
$\xi_{{\rm{P}},t,h}$ | $\overline{\theta}_{{\rm{P}},t,h}-\widehat{\theta}_{{\rm{P}},t,h}$
$\lambda_{t,h}$ | $\lambda\Sigma^{-1}_{t-1,h}\int_{s^{\prime}}\mu^{\star}_{h}(s^{\prime})\overline{V}_{t,h+1}(s^{\prime})\mathop{}\mathrm{d}s^{\prime}$
$\eta_{{\rm{r}},t}$ | $\widehat{\theta}_{{\rm{r}},t}-\theta^{\star}_{{\rm{r}}}$
$\eta_{{\rm{P}},t,h}$ | $\Sigma^{-1}_{t-1,h}\left(\sum_{i=1}^{t-1}\phi(s_{i,h},a_{i,h})\left(\overline{V}_{t,h+1}(s_{i,h+1})-\mathop{\mathbb{E}}_{s_{i,h+1}}\left[\overline{V}_{t,h+1}(s_{i,h+1})\,\middle|\,s_{i,h},a_{i,h}\right]\right)\right)$
$\theta^{\star}_{{\rm{P}},t,h}$ | $\int_{s^{\prime}}\mu^{\star}_{h}(s^{\prime})\left[\overline{V}_{t,h+1}(s^{\prime})\right]\mathop{}\mathrm{d}s^{\prime}$
(2) Statistical upper bounds
$\epsilon_{{\rm{r}},\xi}$ | $\sigma_{{\rm{r}}}\sqrt{2d\log(2dT/\delta)}$
$\epsilon_{{\rm{r}},\eta}$ | $\sqrt{80\kappa d\log\Big{(}24BT^{2}/(\overline{\kappa}\delta)\Big{)}+168B^{2}d\log(6BT^{2}/\delta)+4\lambda B^{2}}$
$V_{\max}$ | $H(2+(\epsilon_{{\rm{r}},\xi}+\epsilon_{{\rm{r}},\eta})/\sqrt{\lambda})$
$\epsilon_{\lambda}$ | $V_{\max}\sqrt{\lambda d}$
$\epsilon_{{\rm{P}},\xi}$ | $\sigma_{{\rm{P}}}\sqrt{2d\log(2dHT/\delta)}$
$\iota_{\epsilon}$ | $\log\left(12HT^{2}(T+\lambda)V_{\max}\left(B+\frac{2V_{\max}\sqrt{dt}+\epsilon_{{\rm{P}},\xi}+\epsilon_{{\rm{r}},\xi}}{\sqrt{\lambda}}\right)\right)$
$\chi$ | (defined in Lemma B.3)
$\epsilon^{\prime}_{{\rm{P}},\eta}$ | $\frac{6}{\sqrt{\lambda}}+16dV_{\max}\sqrt{\iota_{\epsilon}-\log\big{(}(\alpha_{\rm{U}}-\alpha_{\rm{L}})\delta\lambda\big{)}}$
$\epsilon_{{\rm{P}},\eta}$ | $\chi\cdot\left(\frac{6}{\sqrt{\lambda}}+16dV_{\max}\sqrt{\iota_{\epsilon}-\log\big{(}\delta\lambda\big{)}}\right)$
(3) Value cutoff
$\bm{L}_{t,h}(s)$ | $\mathds{1}\\{\|\phi(s,\pi_{t,h}(s))\|_{\Sigma_{t-1,h}^{-1}}\leq\alpha_{\rm{L}}\\}$
$\bm{L}^{\complement}_{t,h}(s)$ | $\mathds{1}\\{\|\phi(s,\pi_{t,h}(s))\|_{\Sigma_{t-1,h}^{-1}}>\alpha_{\rm{L}}\\}$
$L_{\max}$ | $\frac{2dH}{\alpha_{L}^{2}}\cdot\log\left(\frac{\lambda+T}{\lambda}\right)$
(4) Hyperparameters
$\sigma_{{\rm{r}}}$ | $\epsilon_{{\rm{r}},\eta}$
$\sigma_{{\rm{P}}}$ | $(\epsilon_{{\rm{P}},\eta}+\epsilon_{\lambda})\sqrt{H}$
$\alpha_{\rm{U}}$ | $(\epsilon_{{\rm{P}},\xi}+\epsilon_{{\rm{P}},\eta}+\epsilon_{\lambda})^{-1}$
$\alpha_{\rm{L}}$ | $(\epsilon_{{\rm{P}},\xi}+\epsilon_{{\rm{P}},\eta}+\epsilon_{\lambda})^{-1}/2$
$\lambda$ | $1$

The concept of covering number is defined below, which will be used to bound
the statistical error of our algorithm.

######  Definition B.1 (Covering number).

Consider a function class
$\mathcal{F}\subseteq\mathcal{X}\rightarrow\mathbb{R}$. The $\omega$-cover of
a function $\widehat{f}\in\mathcal{F}$ is defined as the set of functions
$f\in\mathcal{F}$ for which $\|f-\widehat{f}\|\leq\omega$. The covering number
of $\mathcal{F}$ w.r.t. the metric $\|\cdot\|$ denoted by
$N(\omega,\mathcal{F},\|\cdot\|)$ is the minimum number of $\omega$-covers
needed to cover $\mathcal{F}$.

###  B.2 Supporting lemmas

######  Lemma B.2 (Covering number of Euclidean balls).

[Pollard, 1990] Let
$\Theta_{B}\coloneqq\\{\theta\in\mathbb{R}^{d}:\|\theta\|_{2}\leq B\\}$. Then
we have

$N(\omega,\Theta_{B},\|\cdot\|_{2})\leq(3B/\omega)^{d}.$

######  Lemma B.3.

There exists
$\chi=O(\log(\epsilon_{{\rm{P}},\xi}+\epsilon_{{\rm{P}},\eta}+\epsilon_{\lambda}))$
such that $\epsilon^{\prime}_{{\rm{P}},\eta}\leq\epsilon_{{\rm{P}},\eta}$
(recalling that $\chi$ is in the definition of $\epsilon_{{\rm{P}},\eta}$).

###### Proof of Lemma B.3.

By definition, we have

$\displaystyle\epsilon^{\prime}_{{\rm{P}},\eta}$
$\displaystyle=\frac{6}{\sqrt{\lambda}}+16dV_{\max}\sqrt{\iota_{\epsilon}-\log\big{(}(\alpha_{\rm{U}}-\alpha_{\rm{L}})\delta\lambda\big{)}}$
$\displaystyle=\frac{6}{\sqrt{\lambda}}+16dV_{\max}\sqrt{\iota_{\epsilon}-\log(\delta\lambda)-\log(\alpha_{\rm{U}}-\alpha_{\rm{L}})}$
$\displaystyle=\frac{6}{\sqrt{\lambda}}+16dV_{\max}\sqrt{\iota_{\epsilon}-\log(\delta\lambda)+\log
2(\epsilon_{{\rm{P}},\xi}+\epsilon_{{\rm{P}},\eta}+\epsilon_{\lambda})}$
$\displaystyle\leq\chi\left(\frac{6}{\sqrt{\lambda}}+16dV_{\max}\sqrt{\iota_{\epsilon}-\log(\delta\lambda)}\
\right)$ $\displaystyle=\epsilon_{{\rm{P}},\eta}.$

Here the third equality is by the definition of $\alpha_{\rm{L}}$ and
$\alpha_{\rm{U}}$. The inequality holds by setting
$\chi=O(\log(\epsilon_{{\rm{P}},\xi}+\epsilon_{{\rm{P}},\eta}+\epsilon_{\lambda}))$
to be large enough. ∎

######  Lemma B.4.

It holds that
$\eta_{{\rm{P}},t,h}+\lambda_{t,h}=\widehat{\theta}_{{\rm{P}},t,h}-\theta^{\star}_{{\rm{P}},t,h}$
for any $t\in[T]$ and $h\in[H]$.

###### Proof of Lemma B.4.

By definition, we have

$\displaystyle\eta_{{\rm{P}},t,h}+\lambda_{t,h}$
$\displaystyle=\Sigma^{-1}_{t-1,h}\left(\sum_{i=1}^{t-1}\phi(s_{i,h},a_{i,h})\left(\overline{V}_{t,h+1}(s_{i,h+1})-\mathop{\mathbb{E}}_{s_{h+1}}\left[\overline{V}_{t,h+1}(s_{i,h+1})\,\middle|\,s_{i,h},a_{i,h}\right]\right)\right)$
$\displaystyle\quad+\lambda\Sigma^{-1}_{t-1,h}\int_{s^{\prime}}\mu^{\star}_{h}(s^{\prime})\overline{V}_{t,h+1}(s^{\prime})\mathop{}\mathrm{d}s^{\prime}$
$\displaystyle=\widehat{\theta}_{{\rm{P}},t,h}-\Sigma^{-1}_{t-1,h}\left(\sum_{i=1}^{t-1}\phi(s_{i,h},a_{i,h})\phi(s_{i,h},a_{i,h})+\lambda
I\right)^{\top}\int_{s^{\prime}}\mu^{\star}_{h}(s^{\prime})\left[\overline{V}_{t,h+1}(s^{\prime})\right]\mathop{}\mathrm{d}s^{\prime}$
$\displaystyle=\widehat{\theta}_{{\rm{P}},t,h}-\int_{s^{\prime}}\mu^{\star}_{h}(s^{\prime})\left[\overline{V}_{t,h+1}(s^{\prime})\right]\mathop{}\mathrm{d}s^{\prime}$
$\displaystyle=\widehat{\theta}_{{\rm{P}},t,h}-\theta^{\star}_{{\rm{P}},t,h}.$

∎

The following lemma is adapted from Zanette et al. [2020, Lemma 1] to our
setting.

######  Lemma B.5 (One-step decomposition).

For any $t\in[T],h\in[H],s\in\mathcal{S},a\in\mathcal{A}$, and policy $\pi$,
we have

$\displaystyle\phi(s,a)^{\top}\left(\overline{\theta}_{{\rm{r}},t}+\overline{\theta}_{{\rm{P}},t,h}\right)-Q^{\pi}_{h}(s,a)$
$\displaystyle\qquad\qquad=\phi(s,a)^{\top}(\xi_{{\rm{r}},t}+\xi_{{\rm{P}},t,h}+\eta_{{\rm{r}},t}+\eta_{{\rm{P}},t,h}-\lambda_{t,h})+\mathop{\mathbb{E}}_{s^{\prime}}\left[\overline{V}_{t,h+1}(s^{\prime})-V^{\pi}_{h+1}(s^{\prime})\,\middle|\,s,a\right].$

###### Proof.

We have

$\displaystyle\phi(s,a)^{\top}\left(\overline{\theta}_{{\rm{r}},t}+\overline{\theta}_{{\rm{P}},t,h}\right)-Q^{\pi}_{h}(s,a)$
$\displaystyle=\phi(s,a)^{\top}\left(\overline{\theta}_{{\rm{r}},t}+\overline{\theta}_{{\rm{P}},t,h}\right)-\phi(s,a)^{\top}\theta^{\star}_{{\rm{r}}}-\mathop{\mathbb{E}}_{s^{\prime}}[V^{\pi}_{h+1}(s^{\prime})\,|\,s,a]$
$\displaystyle=\phi(s,a)^{\top}(\overline{\theta}_{{\rm{r}},t}-\widehat{\theta}_{{\rm{r}},t})+\phi(s,a)^{\top}(\overline{\theta}_{{\rm{P}},t,h}-\widehat{\theta}_{{\rm{P}},t,h})+\phi(s,a)^{\top}(\widehat{\theta}_{{\rm{r}},t}-\theta^{\star}_{{\rm{r}}})$
$\displaystyle\qquad+\phi(s,a)^{\top}\widehat{\theta}_{{\rm{P}},t,h}-\mathop{\mathbb{E}}_{s^{\prime}}[V^{\pi}_{h+1}(s^{\prime})\,|\,s,a].$

For the last but one term, we note that

$\displaystyle\phi(s,a)^{\top}\widehat{\theta}_{{\rm{P}},t,h}$
$\displaystyle=\phi(s,a)^{\top}\Sigma^{-1}_{t-1,h}\left(\sum_{i=1}^{t-1}\phi(s_{i,h},a_{i,h})\overline{V}_{t,h+1}(s_{i,h+1})\right)$
$\displaystyle=\phi(s,a)^{\top}\Sigma^{-1}_{t-1,h}\left(\sum_{i=1}^{t-1}\phi(s_{i,h},a_{i,h})\mathop{\mathbb{E}}_{s_{h+1}}\left[\overline{V}_{t,h+1}(s_{i,h+1})\,\middle|\,s_{i,h},a_{i,h}\right]\right)+\phi(s,a)^{\top}\eta_{{\rm{P}},t,h}$
$\displaystyle=\phi(s,a)^{\top}\Sigma^{-1}_{t-1,h}\left(\sum_{i=1}^{t-1}\phi(s_{i,h},a_{i,h})\phi(s_{i,h},a_{i,h})^{\top}\int_{s^{\prime}}\mu^{\star}_{h}(s^{\prime})\overline{V}_{t,h+1}(s^{\prime})\mathop{}\mathrm{d}s^{\prime}\right)+\phi(s,a)^{\top}\eta_{{\rm{P}},t,h}$
$\displaystyle=\phi(s,a)^{\top}\int_{s^{\prime}}\mu^{\star}_{h}(s^{\prime})\overline{V}_{t,h+1}(s^{\prime})\mathop{}\mathrm{d}s^{\prime}-\lambda\phi(s,a)^{\top}\Sigma^{-1}_{t-1,h}\int_{s^{\prime}}\mu^{\star}_{h}(s^{\prime})\overline{V}_{t,h+1}(s^{\prime})\mathop{}\mathrm{d}s^{\prime}+\phi(s,a)^{\top}\eta_{{\rm{P}},t,h}$
$\displaystyle=\mathop{\mathbb{E}}_{s^{\prime}}\left[\overline{V}_{t,h+1}(s^{\prime})\,\middle|\,s,a\right]-\phi(s,a)^{\top}\lambda_{t,h}+\phi(s,a)^{\top}\eta_{{\rm{P}},t,h}.$

Plugging this back, we get

$\displaystyle\phi(s,a)^{\top}\left(\overline{\theta}_{{\rm{r}},t}+\overline{\theta}_{{\rm{P}},t,h}\right)-Q^{\pi}_{h}(s,a)$
$\displaystyle=\phi(s,a)^{\top}(\overline{\theta}_{{\rm{r}},t}-\widehat{\theta}_{{\rm{r}},t})+\phi(s,a)^{\top}(\overline{\theta}_{{\rm{P}},t,h}-\widehat{\theta}_{{\rm{P}},t,h})+\phi(s,a)^{\top}(\widehat{\theta}_{{\rm{r}},t}-\theta^{\star}_{{\rm{r}}})$
$\displaystyle\quad+\mathop{\mathbb{E}}_{s^{\prime}}\left[\overline{V}_{t,h+1}(s^{\prime})-V^{\pi}_{h+1}(s^{\prime})\,\middle|\,s,a\right]-\phi(s,a)^{\top}\lambda_{t,h}+\phi(s,a)^{\top}\eta_{{\rm{P}},t,h}$
$\displaystyle=\phi(s,a)^{\top}(\xi_{{\rm{r}},t}+\xi_{{\rm{P}},t,h}+\eta_{{\rm{r}},t}+\eta_{{\rm{P}},t,h}-\lambda_{t,h})+\mathop{\mathbb{E}}_{s^{\prime}}\left[\overline{V}_{t,h+1}(s^{\prime})-V^{\pi}_{h+1}(s^{\prime})\,\middle|\,s,a\right].$

This completes the proof. ∎

######  Lemma B.6.

For any $t\in[T]$, if $Z_{t}=0$, then we have

$\displaystyle\|\phi(\tau_{t}^{0})-\phi(\tau_{t}^{1})\|_{\Sigma_{t-1}^{-1}}\leq\epsilon\sqrt{\pi}/(2\sigma_{{\rm{r}}}).$

###### Proof.

By the definition of $Z_{t}$, we have

$\displaystyle\epsilon\geq$
$\displaystyle\mathop{\mathbb{E}}_{\theta_{0},\theta_{1}\sim\mathcal{N}(\widehat{\theta}_{{\rm{r}},t},\sigma_{\rm{r}}^{2}\Sigma^{-1}_{t-1})}|(\phi(\tau_{t}^{0})-\phi(\tau_{t}^{1}))^{\top}(\theta_{0}-\theta_{1})|$
$\displaystyle=$ $\displaystyle\
\mathop{\mathbb{E}}_{u_{0},u_{1}\sim\mathcal{N}(0,I_{d})}|(\phi(\tau_{t}^{0})-\phi(\tau_{t}^{1}))^{\top}\sigma_{{\rm{r}}}\Sigma_{t-1}^{-1/2}(u_{0}-u_{1})|$
$\displaystyle=$ $\displaystyle\
\mathop{\mathbb{E}}_{u\sim\mathcal{N}(0,I_{d})}|(\phi(\tau_{t}^{0})-\phi(\tau_{t}^{1}))^{\top}\sqrt{2}\sigma_{{\rm{r}}}\Sigma_{t-1}^{-1/2}u|$
$\displaystyle=$ $\displaystyle\
\sigma_{{\rm{r}}}\sqrt{2}\mathop{\mathbb{E}}_{u\sim\mathcal{N}(0,I_{d})}\sqrt{u^{\top}\Sigma_{t-1}^{-1/2}(\phi(\tau_{t}^{0})-\phi(\tau_{t}^{1}))(\phi(\tau_{t}^{0})-\phi(\tau_{t}^{1}))^{\top}\Sigma_{t-1}^{-1/2}u}$
$\displaystyle=$ $\displaystyle\
\sigma_{{\rm{r}}}\sqrt{2}\mathop{\mathbb{E}}_{u\sim\mathcal{N}(0,I_{d})}\|u\|_{\Sigma_{t-1}^{-1/2}(\phi(\tau_{t}^{0})-\phi(\tau_{t}^{1}))(\phi(\tau_{t}^{0})-\phi(\tau_{t}^{1}))^{\top}\Sigma_{t-1}^{-1/2}}.$

We then apply Lemma D.9 and obtain

$\displaystyle\epsilon\geq\ $
$\displaystyle\sigma_{{\rm{r}}}\sqrt{2}\cdot\sqrt{\frac{2\mathop{\mathrm{tr}}\left(\Sigma_{t-1}^{-1/2}(\phi(\tau_{t}^{0})-\phi(\tau_{t}^{1}))(\phi(\tau_{t}^{0})-\phi(\tau_{t}^{1}))^{\top}\Sigma_{t-1}^{-1/2}\right)}{\pi}}$
$\displaystyle=\ $ $\displaystyle
2\sigma_{{\rm{r}}}\cdot\sqrt{\frac{(\phi(\tau_{t}^{0})-\phi(\tau_{t}^{1}))^{\top}\Sigma_{t-1}^{-1/2}\Sigma_{t-1}^{-1/2}(\phi(\tau_{t}^{0})-\phi(\tau_{t}^{1}))}{\pi}}$
$\displaystyle=\ $
$\displaystyle\frac{2\sigma_{{\rm{r}}}}{\sqrt{\pi}}\cdot\|\phi(\tau_{t}^{0})-\phi(\tau_{t}^{1})\|_{\Sigma_{t-1}^{-1}}.$

Hence, we complete the proof. ∎

###  B.3 Statistical upper bounds

######  Lemma B.7 (Gaussian noise).

Each of the following holds with probability at least $1-\delta$:

  1. 1.

$\|\xi_{{\rm{r}},t}\|_{\Sigma_{t-1}}\leq\epsilon_{{\rm{r}},\xi}$ for all
$t\in[T]$,

  2. 2.

$\|\xi_{{\rm{P}},t,h}\|_{\Sigma_{t-1,h}}\leq\epsilon_{{\rm{P}},\xi}$ for all
$t\in[T]$ and $h\in[H]$.

###### Proof of Lemma B.7.

It simply follows from Lemma D.3 and the union bound. ∎

######  Lemma B.8.

Fix $t\in[T]$. It holds with probability at least $1-\delta$ that

$\displaystyle\sum_{s=1}^{t-1}$
$\displaystyle\left|\big{(}\phi(\tau_{s}^{0})-\phi(\tau_{s}^{1})\big{)}^{\top}\left(\theta^{\star}_{{\rm{r}}}-\widehat{\theta}_{{\rm{r}},t}\right)\right|^{2}$
$\displaystyle\leq$ $\displaystyle
8\sum_{s=1}^{t-1}\mathop{\mathbb{E}}_{\tau_{s}^{0},\tau_{s}^{1}}\left|\big{(}\phi(\tau_{s}^{0})-\phi(\tau_{s}^{1})\big{)}^{\top}\left(\theta^{\star}_{{\rm{r}}}-\widehat{\theta}_{{\rm{r}},t}\right)\right|^{2}+168B^{2}d\log(3TB/\delta).$

Here the expectation is taken over the randomness of sampling $\tau_{s}^{0}$
and $\tau_{s}^{1}$ from $\pi_{s}^{0}$ and $\pi_{s}^{1}$, respectively.

###### Proof of Lemma B.8.

Let $\widetilde{\Theta_{B}}$ denote an $\omega$-covering of ${\Theta_{B}}$
with respect to $\|\cdot\|_{2}$ for some $\omega>0$. By Lemma B.2, we have
$|\widetilde{\Theta_{B}}|\leq(3B/\omega)^{d}$. Moreover, for any $s\in[t-1]$,
by Cauchy-Schwarz inequality, it holds that

$\displaystyle\left|\big{(}\phi(\tau_{s}^{0})-\phi(\tau_{s}^{1})\big{)}^{\top}\left(\theta^{\star}_{{\rm{r}}}-\widetilde{\theta}\right)\right|^{2}\leq\big{\|}\phi(\tau_{s}^{0})-\phi(\tau_{s}^{1})\big{\|}_{2}^{2}\cdot\big{\|}\theta^{\star}_{{\rm{r}}}-\widetilde{\theta}\big{\|}_{2}^{2}\leq
16B^{2}.$

Then, by Lemma D.4 and union bound over $\widetilde{\Theta_{B}}$, it holds
that

$\displaystyle\sum_{s=1}^{t-1}$
$\displaystyle\left|\big{(}\phi(\tau_{s}^{0})-\phi(\tau_{s}^{1})\big{)}^{\top}\left(\theta^{\star}_{{\rm{r}}}-\widetilde{\theta}\right)\right|^{2}$
$\displaystyle\leq$ $\displaystyle
2\sum_{s=1}^{t-1}\mathop{\mathbb{E}}_{\tau_{s}^{0},\tau_{s}^{1}}\left|\big{(}\phi(\tau_{s}^{0})-\phi(\tau_{s}^{1})\big{)}^{\top}\left(\theta^{\star}_{{\rm{r}}}-\widetilde{\theta}\right)\right|^{2}+64B^{2}d\log(3B/(\omega\delta))$
(4)

for all $\widetilde{\theta}\in\widetilde{\Theta_{B}}$ with probability at
least $1-\delta$. Now we consider an arbitrary $\theta\in{\Theta_{B}}$ and let
$\widetilde{\theta}\in\widetilde{\Theta_{B}}$ be the closest to $\theta$.
Then, by triangle inequality and Cauchy-Schwarz inequality, we have the
following two ineuqalities:

$\displaystyle\left|\big{(}\phi(\tau_{s}^{0})-\phi(\tau_{s}^{1})\big{)}^{\top}\left(\theta^{\star}_{{\rm{r}}}-\theta\right)\right|^{2}$
$\displaystyle\quad\leq
2\left|\big{(}\phi(\tau_{s}^{0})-\phi(\tau_{s}^{1})\big{)}^{\top}\left(\theta^{\star}_{{\rm{r}}}-\widetilde{\theta}\right)\right|^{2}+2\|\phi(\tau_{s}^{0})-\phi(\tau_{s}^{1})\|_{2}^{2}\|\theta-\widetilde{\theta}\|_{2}^{2}$
$\displaystyle\quad\leq
2\left|\big{(}\phi(\tau_{s}^{0})-\phi(\tau_{s}^{1})\big{)}^{\top}\left(\theta^{\star}_{{\rm{r}}}-\widetilde{\theta}\right)\right|^{2}+8\omega^{2},$
and
$\displaystyle\left|\big{(}\phi(\tau_{s}^{0})-\phi(\tau_{s}^{1})\big{)}^{\top}\left(\theta^{\star}_{{\rm{r}}}-\widetilde{\theta}\right)\right|^{2}$
$\displaystyle\quad\leq
2\left|\big{(}\phi(\tau_{s}^{0})-\phi(\tau_{s}^{1})\big{)}^{\top}\left(\theta^{\star}_{{\rm{r}}}-\theta\right)\right|^{2}+2\|\phi(\tau_{s}^{0})-\phi(\tau_{s}^{1})\|_{2}^{2}\|\theta-\widetilde{\theta}\|_{2}^{2}$
$\displaystyle\quad\leq
2\left|\big{(}\phi(\tau_{s}^{0})-\phi(\tau_{s}^{1})\big{)}^{\top}\left(\theta^{\star}_{{\rm{r}}}-\theta\right)\right|^{2}+8\omega^{2}$

Applying these inequalities and (4), we get

$\displaystyle\sum_{s=1}^{t-1}$
$\displaystyle\left|\big{(}\phi(\tau_{s}^{0})-\phi(\tau_{s}^{1})\big{)}^{\top}\left(\theta^{\star}_{{\rm{r}}}-\theta\right)\right|^{2}$
$\displaystyle\leq$ $\displaystyle
2\sum_{s=1}^{t-1}\left|\big{(}\phi(\tau_{s}^{0})-\phi(\tau_{s}^{1})\big{)}^{\top}\left(\theta^{\star}_{{\rm{r}}}-\widetilde{\theta}\right)\right|^{2}+8\omega^{2}t$
$\displaystyle\leq$ $\displaystyle
4\sum_{s=1}^{t-1}\mathop{\mathbb{E}}_{\tau_{s}^{0},\tau_{s}^{1}}\left|\big{(}\phi(\tau_{s}^{0})-\phi(\tau_{s}^{1})\big{)}^{\top}\left(\theta^{\star}_{{\rm{r}}}-\widetilde{\theta}\right)\right|^{2}+128B^{2}d\log(3B/(\omega\delta))+8\omega^{2}t$
$\displaystyle\leq$ $\displaystyle
8\sum_{s=1}^{t-1}\mathop{\mathbb{E}}_{\tau_{s}^{0},\tau_{s}^{1}}\left|\big{(}\phi(\tau_{s}^{0})-\phi(\tau_{s}^{1})\big{)}^{\top}\left(\theta^{\star}_{{\rm{r}}}-\theta\right)\right|^{2}+128B^{2}d\log(3B/(\omega\delta))+40\omega^{2}t$
$\displaystyle\leq$ $\displaystyle
8\sum_{s=1}^{t-1}\mathop{\mathbb{E}}_{\tau_{s}^{0},\tau_{s}^{1}}\left|\big{(}\phi(\tau_{s}^{0})-\phi(\tau_{s}^{1})\big{)}^{\top}\left(\theta^{\star}_{{\rm{r}}}-\theta\right)\right|^{2}+168B^{2}d\log(3TB/\delta)$

where the last step holds by setting $\omega=1/t$. ∎

######  Lemma B.9 (Reward estimation error).

It holds with probability at least $1-\delta$ that
$\|\eta_{{\rm{r}},t}\|_{\Sigma_{t-1}}\leq\epsilon_{{\rm{r}},\eta}$ for all
$t\in[T]$.

###### Proof of Lemma B.9.

Since $\widehat{\theta}_{{\rm{r}},t}$ is the MLE, by Lemma D.10, we have

$\displaystyle\sum_{s=1}^{t-1}\mathop{\mathbb{E}}_{\tau_{s}^{0},\tau_{s}^{1}}d_{{\rm{TV}}}^{2}\left(\operatorname{Pr}\left(\cdot\,\middle|\,\tau_{s}^{0},\tau_{s}^{1},\theta^{\star}_{{\rm{r}}}\right),\operatorname{Pr}\left(\cdot\,\middle|\,\tau_{s}^{0},\tau_{s}^{1},\widehat{\theta}_{{\rm{r}},t}\right)\right)\leq
10\log\Big{(}N_{[]}\big{(}(2T)^{-1},\overline{\mathcal{R}},\|\cdot\|_{\infty}\big{)}/\delta\Big{)}$
(5)

with probability at least $1-\delta$, where $\overline{\mathcal{R}}$ denotes
the set of probability distributions of preference feedback and
$\operatorname{Pr}(\cdot)$ denotes the preference feedback generating
probability. Now we upper bound the covering number of
$\overline{\mathcal{R}}$ by the covering number of $\Theta_{B}$. We notice the
following:

$\displaystyle\sup_{o,\tau^{0},\tau^{1}}\left|\operatorname{Pr}\left(o\,\middle|\,\tau^{0},\tau^{1},\theta^{\star}_{{\rm{r}}}\right)-\operatorname{Pr}\left(o\,\middle|\,\tau^{0},\tau^{1},\widehat{\theta}_{{\rm{r}},t}\right)\right|$
$\displaystyle=$
$\displaystyle\sup_{\tau^{0},\tau^{1}}\left|\Phi\Big{(}\big{(}\phi(\tau^{0})-\phi(\tau^{1})\big{)}^{\top}\theta^{\star}_{{\rm{r}}}\Big{)}-\Phi\Big{(}\big{(}\phi(\tau^{0})-\phi(\tau^{1})\big{)}^{\top}\widehat{\theta}_{{\rm{r}},t}\Big{)}\right|$
$\displaystyle\leq$
$\displaystyle\overline{\kappa}^{-1}\sup_{\tau^{0},\tau^{1}}\left|\big{(}\phi(\tau^{0})-\phi(\tau^{1})\big{)}^{\top}\big{(}\theta^{\star}_{{\rm{r}}}-\widehat{\theta}_{{\rm{r}},t}\big{)}\right|$
$\displaystyle\leq$
$\displaystyle\overline{\kappa}^{-1}\sup_{\tau^{0},\tau^{1}}\|\phi(\tau^{0})-\phi(\tau^{1})\|_{2}\|\theta^{\star}_{{\rm{r}}}-\widehat{\theta}_{{\rm{r}},t}\|_{2}$
$\displaystyle\leq$ $\displaystyle
2\overline{\kappa}^{-1}\|\theta^{\star}_{{\rm{r}}}-\widehat{\theta}_{{\rm{r}},t}\|_{2}$

where the equality holds since the feedback $o$ is binary, the first
inequality is Lemma D.1, and the last inequality is by the condition that
$\|\phi(\tau)\|_{2}\leq 1$ for any trajectory $\tau$. This means that an
$\omega$-covering of the space of parameter $\theta$ implies a
$2\omega\overline{\kappa}^{-1}$-covering of the space of the probability
distribution of the preference feedbacks. Hence, (5) can be further upper
bounded by

$\displaystyle\sum_{s=1}^{t-1}\mathop{\mathbb{E}}_{\tau_{s}^{0},\tau_{s}^{1}}d_{{\rm{TV}}}^{2}\left(\operatorname{Pr}\left(\cdot\,\middle|\,\tau_{s}^{0},\tau_{s}^{1},\theta^{\star}_{{\rm{r}}}\right),\operatorname{Pr}\left(\cdot\,\middle|\,\tau_{s}^{0},\tau_{s}^{1},\widehat{\theta}_{{\rm{r}},t}\right)\right)$
$\displaystyle\leq
10\log\Big{(}N_{[]}\big{(}(2T)^{-1},\overline{\mathcal{R}},\|\cdot\|_{\infty}\big{)}/\delta\Big{)}$
$\displaystyle\leq
10\log\Big{(}N\big{(}\overline{\kappa}/(4T),\Theta_{B},\|\cdot\|_{2}\big{)}/\delta\Big{)}$
$\displaystyle\leq 10d\log\Big{(}12BT/(\overline{\kappa}\delta)\Big{)}$ (6)

where the last inequality is Lemma B.2. For the left side, we note that

$\displaystyle\sum_{s=1}^{t-1}\mathop{\mathbb{E}}_{\tau_{s}^{0},\tau_{s}^{1}}d_{{\rm{TV}}}^{2}\left(\operatorname{Pr}\left(\cdot\,\middle|\,\tau_{s}^{0},\tau_{s}^{1},\theta^{\star}_{{\rm{r}}}\right),\operatorname{Pr}\left(\cdot\,\middle|\,\tau_{s}^{0},\tau_{s}^{1},\widehat{\theta}_{{\rm{r}},t}\right)\right)$
$\displaystyle=$
$\displaystyle\sum_{s=1}^{t-1}\mathop{\mathbb{E}}_{\tau_{s}^{0},\tau_{s}^{1}}\left|\Phi\left(\big{(}\phi(\tau_{s}^{0})-\phi(\tau_{s}^{1})\big{)}^{\top}\theta^{\star}_{{\rm{r}}}\right)-\Phi\left(\big{(}\phi(\tau_{s}^{0})-\phi(\tau_{s}^{1})\big{)}^{\top}\widehat{\theta}_{{\rm{r}},t}\right)\right|^{2}$
$\displaystyle\geq$
$\displaystyle\kappa^{-1}\sum_{s=1}^{t-1}\mathop{\mathbb{E}}_{\tau_{s}^{0},\tau_{s}^{1}}\left|\big{(}\phi(\tau_{s}^{0})-\phi(\tau_{s}^{1})\big{)}^{\top}\left(\theta^{\star}_{{\rm{r}}}-\widehat{\theta}_{{\rm{r}},t}\right)\right|^{2}$
$\displaystyle\geq$
$\displaystyle\frac{1}{8}\kappa^{-1}\sum_{s=1}^{t-1}\left|\big{(}\phi(\tau_{s}^{0})-\phi(\tau_{s}^{1})\big{)}^{\top}\left(\theta^{\star}_{{\rm{r}}}-\widehat{\theta}_{{\rm{r}},t}\right)\right|^{2}-21\kappa^{-1}B^{2}d\log(3TB/\delta)$
(7)

with probability at least $1-\delta$, where the first inequality is by Lemma
D.1 and the last inequality is by Lemma B.8. Furthermore, we have

$\displaystyle\sum_{s=1}^{t-1}\left|\big{(}\phi(\tau_{s}^{0})-\phi(\tau_{s}^{1})\big{)}^{\top}\left(\theta^{\star}_{{\rm{r}}}-\widehat{\theta}_{{\rm{r}},t}\right)\right|^{2}$
$\displaystyle=$
$\displaystyle\left(\theta^{\star}_{{\rm{r}}}-\widehat{\theta}_{{\rm{r}},t}\right)^{\top}\sum_{s=1}^{t-1}\big{(}\phi(\tau_{s}^{0})-\phi(\tau_{s}^{1})\big{)}\big{(}\phi(\tau_{s}^{0})-\phi(\tau_{s}^{1})\big{)}^{\top}\left(\theta^{\star}_{{\rm{r}}}-\widehat{\theta}_{{\rm{r}},t}\right)$
$\displaystyle=$
$\displaystyle\left(\theta^{\star}_{{\rm{r}}}-\widehat{\theta}_{{\rm{r}},t}\right)^{\top}\Sigma_{t-1}\left(\theta^{\star}_{{\rm{r}}}-\widehat{\theta}_{{\rm{r}},t}\right)-\left(\theta^{\star}_{{\rm{r}}}-\widehat{\theta}_{{\rm{r}},t}\right)^{\top}\lambda
I\left(\theta^{\star}_{{\rm{r}}}-\widehat{\theta}_{{\rm{r}},t}\right)\geq\|\eta_{{\rm{r}},t}\|_{\Sigma_{t-1}}^{2}-4\lambda
B^{2}$ (8)

Putting (6), (7), and (8) together, we get

$\displaystyle\|\eta_{{\rm{r}},t}\|_{\Sigma_{t-1}}^{2}\leq 80\kappa
d\log\Big{(}12BT/(\overline{\kappa}\delta)\Big{)}+168B^{2}d\log(3TB/\delta)+4\lambda
B^{2}$

with probability at least $1-2\delta$. Adjusting $\delta$ to $\delta/2$ and
taking the union bound over $t\in[T]$ yields the desired result. ∎

######  Lemma B.10 (One-step transition estimation error).

Assume the events defined in Lemma B.7 hold. Then, the following claim holds
for all $t\in[T]$ and $h\in[H]$ with probability at least $1-\delta$: if
$\max_{s}|\overline{V}_{t,h+1}(s)|\leq V_{\max}$, it holds that
$\|\eta_{{\rm{P}},t,h}\|_{\Sigma_{t-1,h}}\leq\epsilon_{{\rm{P}},\eta}.$

###### Proof of Lemma B.10.

By definition, we have

$\displaystyle\|\eta_{{\rm{P}},t,h}\|_{\Sigma_{t-1,h}}=\left\|\sum_{i=1}^{t-1}\phi(s_{i,h},a_{i,h})\left(\overline{V}_{t,h+1}(s_{i,h+1})-\mathop{\mathbb{E}}_{s_{i,h+1}}\left[\overline{V}_{t,h+1}(s_{i,h+1})\,\middle|\,s_{i,h},a_{i,h}\right]\right)\right\|_{\Sigma_{t-1,h}^{-1}}.$

Towards an upper bound of the above, we will conduct some covering arguments.
To that end, we first derive the upper bounds of norms of
$\overline{\theta}_{{\rm{r}},t}$ and $\overline{\theta}_{{\rm{P}},t,h}$.

##### Bounding the $\ell_{2}$-norms of $\overline{\theta}_{{\rm{r}},t}$ and
$\overline{\theta}_{{\rm{P}},t,h}$.

For $\overline{\theta}_{{\rm{r}},t}$, applying triangle inequality, we have
$\|\overline{\theta}_{{\rm{r}},t}\|_{2}\leq\|\xi_{{\rm{r}},t}\|_{2}+\|\widehat{\theta}_{{\rm{r}},t}\|_{2}\leq\|\xi_{{\rm{r}},t}\|_{2}+B$.
For $\|\xi_{{\rm{r}},t}\|_{2}$, we have

$\displaystyle\|\xi_{{\rm{r}},t}\|_{2}=\sqrt{\xi_{{\rm{r}},t}^{\top}\Sigma_{t-1}^{-1/2}\Sigma_{t-1}^{1/2}\xi_{{\rm{r}},t}}\leq\sqrt{\|\xi_{{\rm{r}},t}\|_{\Sigma_{t-1}}\|\xi_{{\rm{r}},t}\|_{\Sigma^{-1}_{t-1}}}\leq\sqrt{\epsilon_{{\rm{r}},\xi}\cdot\|\xi_{{\rm{r}},t}\|_{2}/\sqrt{\lambda}}$

where in the last step we applied Lemma B.7 and the fact that
$\|\xi_{{\rm{r}},t}\|_{\Sigma^{-1}_{t-1}}\leq\|\xi_{{\rm{r}},t}\|_{2}\|\Sigma_{t-1}^{-1/2}\|_{2}\leq\|\xi_{{\rm{r}},t}\|_{2}/\sqrt{\lambda}$.
This implies that
$\|\xi_{{\rm{r}},t}\|_{2}\leq\epsilon_{{\rm{r}},\xi}/\sqrt{\lambda}$, and
thus,
$\|\overline{\theta}_{{\rm{r}},t}\|_{2}\leq\epsilon_{{\rm{r}},\xi}/\sqrt{\lambda}+B$.

For $\overline{\theta}_{{\rm{P}},t,h}$, we have
$\|\overline{\theta}_{{\rm{P}},t,h}\|_{2}\leq\|\xi_{{\rm{P}},t,h}\|_{2}+\|\widehat{\theta}_{{\rm{P}},t,h}\|_{2}$.
For $\|\xi_{{\rm{P}},t,h}\|_{2}$, following a similar argument as above, we
have

$\displaystyle\|\xi_{{\rm{P}},t,h}\|_{2}\leq\sqrt{\|\xi_{{\rm{P}},t,h}\|_{\Sigma_{t-1,h}}\|\xi_{{\rm{P}},t,h}\|_{\Sigma_{t-1,h}^{-1}}}\leq\sqrt{\epsilon_{{\rm{P}},\xi}\cdot\|\xi_{{\rm{P}},t,h}\|_{2}/\sqrt{\lambda}},$

which implies that
$\|\xi_{{\rm{P}},t,h}\|_{2}\leq\epsilon_{{\rm{P}},\xi}/\sqrt{\lambda}$. For
$\|\widehat{\theta}_{{\rm{P}},t,h}\|_{2}$, we have

$\displaystyle\|\widehat{\theta}_{{\rm{P}},t,h}\|_{2}=$
$\displaystyle\left\|\Sigma_{t-1,h}^{-1/2}\Sigma_{t-1,h}^{-1/2}\left(\sum_{i=1}^{t-1}\phi(s_{i,h},a_{i,h})\overline{V}_{t,h+1}(s_{i,h+1})\right)\right\|_{2}$
$\displaystyle\leq$
$\displaystyle\|\Sigma_{t-1,h}^{-1/2}\|_{2}\cdot\left\|\sum_{i=1}^{t-1}\phi(s_{i,h},a_{i,h})\overline{V}_{t,h+1}(s_{i,h+1})\right\|_{\Sigma_{t-1,h}^{-1}}$
$\displaystyle\leq$
$\displaystyle\sqrt{\lambda^{-1}}\cdot\sqrt{t}\cdot\sqrt{\sum_{i=1}^{t-1}\left\|\phi(s_{i,h},a_{i,h})\overline{V}_{t,h+1}(s_{i,h+1})\right\|^{2}_{\Sigma_{t-1,h}^{-1}}}$
$\displaystyle\leq$ $\displaystyle\sqrt{\lambda^{-1}}\cdot\sqrt{t}\cdot
V_{\max}\cdot\sqrt{\sum_{i=1}^{t-1}\left\|\phi(s_{i,h},a_{i,h})\right\|^{2}_{\Sigma_{t-1,h}^{-1}}}$
$\displaystyle\leq$ $\displaystyle\frac{V_{\max}\sqrt{dt}}{\sqrt{\lambda}}$

where the second inequality is by the Jensen’s inequality, the third
inequality is by the condition that $\max_{s}|\overline{V}_{t,h}(s)|\leq
V_{\max}$, and the last inequality is by Lemma D.7. Putting these together, we
get
$\|\overline{\theta}_{{\rm{P}},t,h}\|_{2}\leq\epsilon_{{\rm{P}},\xi}/\sqrt{\lambda}+V_{\max}\sqrt{dt}/\sqrt{\lambda}$.

##### Covering construction.

With these bounds in hand, we can now proceed with a covering construction.
First define

$\displaystyle Q_{\theta_{{\rm{r}}},\theta_{{\rm{P}}},\Sigma}(s,a)$
$\displaystyle\quad\coloneqq\phi(s,a)^{\top}\theta_{{\rm{r}}}+\begin{cases}\phi(s,a)^{\top}\theta_{{\rm{P}}}&\text{if
}\|\phi(s,a)\|_{\Sigma}\leq\alpha_{\rm{L}}\\\
\rho(s,a)\Big{(}\phi(s,a)^{\top}\theta_{{\rm{P}}}\Big{)}+(1-\rho(s,a))(H-h)&\text{if
}\alpha_{\rm{L}}<\|\phi(s,a)\|_{\Sigma}\leq\alpha_{\rm{U}}\\\ H-h&\text{if
}\|\phi(s,a)\|_{\Sigma}>\alpha_{\rm{U}}\end{cases},$ $\displaystyle
V_{\theta_{{\rm{r}}},\theta_{{\rm{P}}},\Sigma}(s)\coloneqq\max_{a}Q_{\theta_{{\rm{r}}},\theta_{{\rm{P}}},\Sigma}(s,a).$
(9)

where
$\rho(s,a):=\frac{\alpha_{\rm{U}}-\|\phi(s,a)\|_{\Sigma}}{\alpha_{\rm{U}}-\alpha_{\rm{L}}}$.
This definition aims to mimic the behavior of Algorithm 1. Then, we define the
space of parameters as follows

$\displaystyle\mathcal{U}\coloneqq\Big{\\{}(\theta_{{\rm{r}}},\theta_{{\rm{P}}},\Sigma)\>:\>$
$\displaystyle\|\theta_{{\rm{r}}}\|_{2}\leq
B+\epsilon_{{\rm{r}},\xi}/\sqrt{\lambda},\,\|\theta_{{\rm{P}}}\|_{2}\leq(V_{\max}\sqrt{dt}+\epsilon_{{\rm{P}},\xi})/\sqrt{\lambda},$
$\displaystyle\|\Sigma\|_{\rm{F}}\leq\sqrt{d}/\lambda,\,\Sigma=\Sigma^{\top},\,\Sigma\succeq
0,\,{\|V_{\theta_{{\rm{r}}},\theta_{{\rm{P}}},\Sigma}\|_{\infty}\leq
V_{\max}}\Big{\\}}.$

Clearly, $\overline{\theta}_{{\rm{r}},t}$ and
$\overline{\theta}_{{\rm{P}},t,h}$ satisfy the constraints of
$\theta_{{\rm{r}}}$ and $\theta_{{\rm{P}}}$. Moreover,
$\|\Sigma_{t-1}^{-1}\|_{\rm{F}}\leq\sqrt{d}\|\Sigma_{t-1}^{-1}\|_{2}\leq\sqrt{d}/\lambda$,
and thus $\Sigma_{t-1}^{-1}$ satisfies the constraint of $\Sigma$. Hence, we
have
$(\overline{\theta}_{{\rm{r}},t},\overline{\theta}_{{\rm{P}},t,h},\Sigma_{t-1})\in\mathcal{U}$.

By Lemma B.2, the size of an $\omega$-covering of $\mathcal{U}$ by treating it
as a subset of $\mathbb{R}^{2d+d^{2}}$ can be bounded by

$\displaystyle
N(\omega,\mathcal{U},\|\cdot\|_{2})\leq\left(\frac{3\Big{(}(B+\epsilon_{{\rm{r}},\xi}/\sqrt{\lambda})+(V_{\max}\sqrt{dt}+\epsilon_{{\rm{P}},\xi})/\sqrt{\lambda}+{\sqrt{d}}/\lambda\Big{)}}{\omega}\right)^{2d+d^{2}}$

We denote the covering set by $\widetilde{\mathcal{U}}$. We will write
$N\coloneqq N(\omega,\mathcal{U},\|\cdot\|_{2})$ for simplicity when there is
no ambiguity. We note that it is possible that not all points in
$\widetilde{\mathcal{U}}$ belong to $\mathcal{U}$. However, we can project all
points to $\mathcal{U}$ so it becomes a $2\omega$-covering of $\mathcal{U}$.
We will omit this subtlety.

##### Covering argument.

For any $(\theta_{{\rm{r}}},\theta_{{\rm{P}}},\Sigma)\in\mathcal{U}$, we
define

$\displaystyle
x_{i,\theta_{{\rm{r}}},\theta_{{\rm{P}}},\Sigma}:=V_{\theta_{{\rm{r}}},\theta_{{\rm{P}}},\Sigma}(s_{i,h+1})-\mathop{\mathbb{E}}_{s^{\prime}}\left[V_{\theta_{{\rm{r}}},\theta_{{\rm{P}}},\Sigma}(s^{\prime})\,\middle|\,s_{i,h},a_{i,h}\right].$

By construction, we have
$|x_{i,\theta_{{\rm{r}}},\theta_{{\rm{P}}},\Sigma}|\leq 2V_{\max}$, so it is
$4V_{\max}$-subgaussian conditioning on $(s_{i,h},a_{i,h})$. Hence, for all
$(\theta_{{\rm{r}}},\theta_{{\rm{P}}},\Sigma)\in\widetilde{\mathcal{U}}$, we
have

$\displaystyle\left\|\sum_{i=1}^{t-1}\phi(s_{i,h},a_{i,h})x_{i,\theta_{{\rm{r}}},\theta_{{\rm{P}}},\Sigma}\right\|_{\Sigma_{t-1,h}^{-1}}\leq\sqrt{32V_{\max}^{2}\left(d\log\left(1+\frac{t}{\lambda}\right)+\log(N/\delta)\right)}$
(10)

with probability at least $1-\delta$ by Lemma D.5 and the union bound over
$\widetilde{\mathcal{U}}$. Now consider an arbitrary tuple
$(\theta_{{\rm{r}}},\theta_{{\rm{P}}},\Sigma)\in\mathcal{U}$ and the nearest
point
$(\tilde{\theta}_{{\rm{r}}},\tilde{\theta}_{{\rm{P}}},\widetilde{\Sigma})\in\widetilde{\mathcal{U}}$.
Then, we have

$\displaystyle\left\|\sum_{i=1}^{t-1}\phi(s_{i,h},a_{i,h})x_{i,\theta_{{\rm{r}}},\theta_{{\rm{P}}},\Sigma}\right\|_{\Sigma_{t-1,h}^{-1}}$
$\displaystyle\leq$
$\displaystyle\left\|\sum_{i=1}^{t-1}\phi(s_{i,h},a_{i,h})x_{i,\tilde{\theta}_{{\rm{r}}},\tilde{\theta}_{{\rm{P}}},\widetilde{\Sigma}}\right\|_{\Sigma_{t-1,h}^{-1}}+\left\|\sum_{i=1}^{t-1}\phi(s_{i,h},a_{i,h})(x_{i,\theta_{{\rm{r}}},\theta_{{\rm{P}}},\Sigma}-x_{i,\tilde{\theta}_{{\rm{r}}},\tilde{\theta}_{{\rm{P}}},\widetilde{\Sigma}})\right\|_{\Sigma_{t-1,h}^{-1}}$
$\displaystyle\leq$
$\displaystyle\left\|\sum_{i=1}^{t-1}\phi(s_{i,h},a_{i,h})x_{i,\tilde{\theta}_{{\rm{r}}},\tilde{\theta}_{{\rm{P}}},\widetilde{\Sigma}}\right\|_{\Sigma_{t-1,h}^{-1}}+\sum_{i=1}^{t-1}\left\|\phi(s_{i,h},a_{i,h})\right\|_{\Sigma_{t-1,h}^{-1}}\cdot\max_{i}|x_{i,\theta_{{\rm{r}}},\theta_{{\rm{P}}},\Sigma}-x_{i,\tilde{\theta}_{{\rm{r}}},\tilde{\theta}_{{\rm{P}}},\widetilde{\Sigma}}|$
$\displaystyle\leq$
$\displaystyle\left\|\sum_{i=1}^{t-1}\phi(s_{i,h},a_{i,h})x_{i,\tilde{\theta}_{{\rm{r}}},\tilde{\theta}_{{\rm{P}}},\widetilde{\Sigma}}\right\|_{\Sigma_{t-1,h}^{-1}}+\sqrt{\lambda^{-1}}\cdot
t\cdot\max_{i}|x_{i,\theta_{{\rm{r}}},\theta_{{\rm{P}}},\Sigma}-x_{i,\tilde{\theta}_{{\rm{r}}},\tilde{\theta}_{{\rm{P}}},\widetilde{\Sigma}}|$

where the last step is by the fact that
$\|\phi(s_{i,h},a_{i,h})\|_{\Sigma_{t-1,h}^{-1}}\leq\sqrt{\lambda^{-1}}$.
Observing the derived upper bound above, the first term is already bounded by
(10) since
$(\tilde{\theta}_{{\rm{r}}},\tilde{\theta}_{{\rm{P}}},\widetilde{\Sigma})\in\widetilde{\mathcal{U}}$.
To bound the second term, we note that, by the definiton of
$x_{i,\theta_{{\rm{r}}},\theta_{{\rm{P}}},\Sigma}$ and
$x_{i,\tilde{\theta}_{{\rm{r}}},\tilde{\theta}_{{\rm{P}}},\widetilde{\Sigma}}$,

$\displaystyle|x_{i,\theta_{{\rm{r}}},\theta_{{\rm{P}}},\Sigma}-x_{i,\tilde{\theta}_{{\rm{r}}},\tilde{\theta}_{{\rm{P}}},\widetilde{\Sigma}}|\leq$
$\displaystyle
2\max_{s}\left|V_{\theta_{{\rm{r}}},\theta_{{\rm{P}}},\Sigma}(s)-V_{\tilde{\theta}_{{\rm{r}}},\tilde{\theta}_{{\rm{P}}},\widetilde{\Sigma}}(s)\right|$
$\displaystyle=$ $\displaystyle
2\max_{s}\left|\max_{a}Q_{\theta_{{\rm{r}}},\theta_{{\rm{P}}},\Sigma}(s,a)-\max_{a}Q_{\tilde{\theta}_{{\rm{r}}},\tilde{\theta}_{{\rm{P}}},\widetilde{\Sigma}}(s,a)\right|$
$\displaystyle\leq$ $\displaystyle
2\max_{s,a}\left|Q_{\theta_{{\rm{r}}},\theta_{{\rm{P}}},\Sigma}(s,a)-Q_{\tilde{\theta}_{{\rm{r}}},\tilde{\theta}_{{\rm{P}}},\widetilde{\Sigma}}(s,a)\right|$

We assume $\omega\leq(\alpha_{\rm{U}}-\alpha_{\rm{L}})^{2}$ (and this will be
satisfied later when we specify the value of $\omega$). Recall that we have
three cases in the definition of
$Q_{\theta_{{\rm{r}}},\theta_{{\rm{P}}},\Sigma}(s,a)$ (see (9)), and we will
refer to them as Case L, Case M, and Case U. There are in total 6 possible
combinations of cases for the pair
$Q_{\theta_{{\rm{r}}},\theta_{{\rm{P}}},\Sigma}(s,a),Q_{\tilde{\theta}_{{\rm{r}}},\tilde{\theta}_{{\rm{P}}},\widetilde{\Sigma}}(s,a)$,
and we will discuss them one by one below. For the ease of notation, we denote
$Q(s,a)$ and $\widetilde{Q}(s,a)$ as shorthand for
$Q_{\theta_{{\rm{r}}},\theta_{{\rm{P}}},\Sigma}(s,a)$ and
$Q_{\tilde{\theta}_{{\rm{r}}},\tilde{\theta}_{{\rm{P}}},\widetilde{\Sigma}}(s,a)$.

##### (1) Case L + Case U.

This is impossible, because, in this case, we have
$|\|\phi\|_{\Sigma}-\|\phi\|_{\widetilde{\Sigma}}|>\alpha_{\rm{U}}-\alpha_{\rm{L}}$,
but we also have
$|\|\phi\|_{\Sigma}-\|\phi\|_{\widetilde{\Sigma}}|=|\sqrt{\phi^{\top}\Sigma\phi}-\sqrt{\phi^{\top}\widetilde{\Sigma}\phi}|\leq\sqrt{|\phi^{\top}(\Sigma-\widetilde{\Sigma})\phi|}\leq\sqrt{\|\phi\|_{2}\|\Sigma-\widetilde{\Sigma}\|_{\rm{F}}\|\phi\|_{2}}\leq\sqrt{\omega}<\alpha_{\rm{U}}-\alpha_{\rm{L}}$.

##### (2) Both are Case L.

Then we immediately have

$\displaystyle|Q(s,a)-\widetilde{Q}(s,a)|=$
$\displaystyle\left|\phi(s,a)^{\top}(\theta_{{\rm{r}}}+\theta_{{\rm{P}}}-\tilde{\theta}_{{\rm{r}}}-\tilde{\theta}_{{\rm{P}}})\right|\leq\|\phi(s,a)\|_{2}\Big{(}\|\theta_{{\rm{r}}}-\tilde{\theta}_{{\rm{r}}}\|_{2}+\|\theta_{{\rm{P}}}-\tilde{\theta}_{{\rm{P}}}\|_{2}\Big{)}\leq
2\omega.$

##### (3) Both are Case U.

Then we immediately have

$\displaystyle|Q(s,a)-\widetilde{Q}(s,a)|=$
$\displaystyle\left|\phi(s,a)^{\top}(\theta_{{\rm{r}}}-\tilde{\theta}_{{\rm{r}}})\right|\leq|\phi(s,a)\|_{2}\cdot\|\theta_{{\rm{r}}}-\tilde{\theta}_{{\rm{r}}}\|_{2}\leq\omega.$

##### (4) Case L + Case M.

Without loss of generality, we assume $Q(s,a)$ is in Case M and
$\widetilde{Q}(s,a)$ is in Case L. Then we have

$\displaystyle|Q(s,a)-\widetilde{Q}(s,a)|\leq$
$\displaystyle\rho(s,a)\left|\phi(s,a)^{\top}(\theta_{{\rm{r}}}+\theta_{{\rm{P}}}-\tilde{\theta}_{{\rm{r}}}-\tilde{\theta}_{{\rm{P}}})\right|$
$\displaystyle+(1-\rho(s,a))\left|\phi(s,a)^{\top}(\tilde{\theta}_{{\rm{r}}}+\tilde{\theta}_{{\rm{P}}})-(H-h)\right|$
$\displaystyle\leq$ $\displaystyle\rho(s,a)\cdot 2\omega+(1-\rho(s,a))\cdot
2V_{\max}$

Recall that
$\rho(s,a):=\frac{\alpha_{\rm{U}}-\|\phi(s,a)\|_{\Sigma}}{\alpha_{\rm{U}}-\alpha_{\rm{L}}}$,
so
$1-\rho(s,a):=\frac{\|\phi(s,a)\|_{\Sigma}-\alpha_{\rm{L}}}{\alpha_{\rm{U}}-\alpha_{\rm{L}}}$.
Futhermore,

$\displaystyle 1-\rho(s,a)$
$\displaystyle=\frac{\|\phi(s,a)\|_{\Sigma}-\alpha_{\rm{L}}}{\alpha_{\rm{U}}-\alpha_{\rm{L}}}=\frac{\|\phi(s,a)\|_{\Sigma}-\|\phi(s,a)\|_{\widetilde{\Sigma}}+\|\phi(s,a)\|_{\widetilde{\Sigma}}-\alpha_{\rm{L}}}{\alpha_{\rm{U}}-\alpha_{\rm{L}}}$
$\displaystyle\leq$
$\displaystyle\frac{\|\phi(s,a)\|_{\Sigma}-\|\phi(s,a)\|_{\widetilde{\Sigma}}}{\alpha_{\rm{U}}-\alpha_{\rm{L}}}=\frac{\sqrt{\phi^{\top}\Sigma\phi}-\sqrt{\phi^{\top}\widetilde{\Sigma}\phi}}{\alpha_{\rm{U}}-\alpha_{\rm{L}}}$
$\displaystyle\leq$
$\displaystyle\frac{\sqrt{|\phi^{\top}(\Sigma-\widetilde{\Sigma})\phi|}}{\alpha_{\rm{U}}-\alpha_{\rm{L}}}\leq\frac{\sqrt{\|\phi\|_{2}\|\Sigma-\widetilde{\Sigma}\|_{2}\|\phi\|_{2}}}{\alpha_{\rm{U}}-\alpha_{\rm{L}}}\leq\frac{\sqrt{\omega}}{\alpha_{\rm{U}}-\alpha_{\rm{L}}}$

where the first inequality is by the condition that $\widetilde{Q}$ is in Case
L. Inserting this back, we get $|Q(s,a)-\widetilde{Q}(s,a)|\leq
2\omega+\frac{2V_{\max}\sqrt{\omega}}{\alpha_{\rm{U}}-\alpha_{\rm{L}}}$.

##### (5) Case M + Case U.

Without loss of generality, we assume $Q(s,a)$ is in Case M and
$\widetilde{Q}(s,a)$ is in Case U. Then we have

$\displaystyle|Q(s,a)-\widetilde{Q}(s,a)|\leq$
$\displaystyle\rho(s,a)\left|\phi(s,a)^{\top}(\theta_{{\rm{r}}}+\theta_{{\rm{P}}}-(H-h))\right|+(1-\rho(s,a))\left|(H-h)-(H-h)\right|$
$\displaystyle=$
$\displaystyle\rho(s,a)\left|\phi(s,a)^{\top}(\theta_{{\rm{r}}}+\theta_{{\rm{P}}}-(H-h))\right|\leq\rho(s,a)\cdot
2V_{\max}\leq\frac{2V_{\max}\sqrt{\omega}}{\alpha_{\rm{U}}-\alpha_{\rm{L}}}$

where the last inequality is from

$\displaystyle\rho(s,a)$
$\displaystyle=\frac{\alpha_{\rm{U}}-\|\phi(s,a)\|_{\Sigma}}{\alpha_{\rm{U}}-\alpha_{\rm{L}}}=\frac{\alpha_{\rm{U}}-\|\phi(s,a)\|_{\Sigma}-\|\phi(s,a)\|_{\widetilde{\Sigma}}+\|\phi(s,a)\|_{\widetilde{\Sigma}}}{\alpha_{\rm{U}}-\alpha_{\rm{L}}}$
$\displaystyle\leq$
$\displaystyle\frac{\|\phi(s,a)\|_{\widetilde{\Sigma}}-\|\phi(s,a)\|_{\Sigma}}{\alpha_{\rm{U}}-\alpha_{\rm{L}}}=\frac{\sqrt{\phi^{\top}\widetilde{\Sigma}\phi}-\sqrt{\phi^{\top}\Sigma\phi}}{\alpha_{\rm{U}}-\alpha_{\rm{L}}}$
$\displaystyle\leq$
$\displaystyle\frac{\sqrt{|\phi^{\top}(\Sigma-\widetilde{\Sigma})\phi|}}{\alpha_{\rm{U}}-\alpha_{\rm{L}}}\leq\frac{\sqrt{\|\phi\|_{2}\|\Sigma-\widetilde{\Sigma}\|_{2}\|\phi\|_{2}}}{\alpha_{\rm{U}}-\alpha_{\rm{L}}}\leq\frac{\sqrt{\omega}}{\alpha_{\rm{U}}-\alpha_{\rm{L}}}.$

where the first inequality is by the condition that $\widetilde{Q}$ is in Case
U.

##### (6) Both are Case M.

Denote
$\rho(s,a)=\frac{\alpha_{\rm{U}}-\|\phi(s,a)\|_{\Sigma}}{\alpha_{\rm{U}}-\alpha_{\rm{L}}}$
and
$\widetilde{\rho}(s,a)=\frac{\alpha_{\rm{U}}-\|\phi(s,a)\|_{\widetilde{\Sigma}}}{\alpha_{\rm{U}}-\alpha_{\rm{L}}}$.
Then, we have

$\displaystyle|\rho(s,a)-\widetilde{\rho}(s,a)|=\frac{\Big{|}\|\phi(s,a)\|_{\widetilde{\Sigma}}-\|\phi(s,a)\|_{\Sigma}\Big{|}}{\alpha_{\rm{U}}-\alpha_{\rm{L}}}\leq\frac{\sqrt{\|\phi\|_{2}\|\widetilde{\Sigma}-\Sigma\|_{\rm{F}}\|\phi\|_{2}}}{\alpha_{\rm{U}}-\alpha_{\rm{L}}}\leq\frac{\sqrt{\omega}}{\alpha_{\rm{U}}-\alpha_{\rm{L}}},$

which also implies
$|(1-\rho(s,a))-(1-\widetilde{\rho}(s,a))|\leq\frac{\sqrt{\omega}}{\alpha_{\rm{U}}-\alpha_{\rm{L}}}$.
Hence, we have

$\displaystyle|Q(s,a)-\widetilde{Q}(s,a)|\leq$
$\displaystyle\left|\rho(s,a)\phi(s,a)^{\top}(\theta_{{\rm{r}}}+\theta_{{\rm{P}}})-\widetilde{\rho}(s,a)\phi(s,a)^{\top}(\tilde{\theta}_{{\rm{r}}}+\tilde{\theta}_{{\rm{P}}})\right|$
$\displaystyle+\left|(1-\rho(s,a))(H-h)-(1-\widetilde{\rho}(s,a))(H-h)\right|$
$\displaystyle\leq$
$\displaystyle\left|\rho(s,a)\phi(s,a)^{\top}(\theta_{{\rm{r}}}+\theta_{{\rm{P}}})-\rho(s,a)\phi(s,a)^{\top}(\tilde{\theta}_{{\rm{r}}}+\tilde{\theta}_{{\rm{P}}})\right|$
$\displaystyle+\left|\rho(s,a)\phi(s,a)^{\top}(\tilde{\theta}_{{\rm{r}}}+\tilde{\theta}_{{\rm{P}}})-\widetilde{\rho}(s,a)\phi(s,a)^{\top}(\tilde{\theta}_{{\rm{r}}}+\tilde{\theta}_{{\rm{P}}})\right|$
$\displaystyle+\left|(1-\rho(s,a))(H-h)-(1-\widetilde{\rho}(s,a))(H-h)\right|$
$\displaystyle\leq$ $\displaystyle
2\omega+\frac{V_{\max}\sqrt{\omega}}{\alpha_{\rm{U}}-\alpha_{\rm{L}}}+\frac{H\sqrt{\omega}}{\alpha_{\rm{U}}-\alpha_{\rm{L}}}$

##### Putting Everything Together.

Taking the maximum of the six cases, we conclude that

$\displaystyle|Q(s,a)-\widetilde{Q}(s,a)|\leq
2\omega+\frac{2V_{\max}\sqrt{\omega}}{\alpha_{\rm{U}}-\alpha_{\rm{L}}}$

We set
$\omega=\left(\frac{\alpha_{\rm{U}}-\alpha_{\rm{L}}}{2tV_{\max}}\right)^{2}$
and obtain

$\displaystyle|Q(s,a)-\widetilde{Q}(s,a)|\leq
2\left(\frac{\alpha_{\rm{U}}-\alpha_{\rm{L}}}{2tV_{\max}}\right)^{2}+\frac{1}{t}\leq\frac{3}{t}$

where we leverage the condition that $\alpha_{\rm{L}},\alpha_{\rm{U}}\leq 1$.
Thus, we have

$\displaystyle|x_{i,\theta_{{\rm{r}}},\theta_{{\rm{P}}},\Sigma}-x_{i,\tilde{\theta}_{{\rm{r}}},\tilde{\theta}_{{\rm{P}}},\widetilde{\Sigma}}|\leq
2\max_{s,a}\left|Q(s,a)-\widetilde{Q}(s,a)\right|\leq\frac{6}{t}.$

##### Final Bound.

The covering argument is now complete, and we can use it to derive an upper
bound for $\|\eta_{{\rm{P}},t,h}\|_{\Sigma_{t-1,h}}$. To that end, we note
that, for $\eta_{{\rm{P}},t,h}$, there must exists
$(\theta_{{\rm{r}}},\theta_{{\rm{P}}},\Sigma)\in\mathcal{U}$ and its closest
element
$(\widetilde{\theta_{{\rm{r}}}},\widetilde{\theta_{{\rm{P}}}},\widetilde{\Sigma})\in\widetilde{\mathcal{U}}$
such that

$\displaystyle\|\eta_{{\rm{P}},t,h}\|_{\Sigma_{t-1,h}}$
$\displaystyle=\left\|\sum_{i=1}^{t-1}\phi(s_{i,h},a_{i,h})\left(\overline{V}_{t,h+1}(s_{i,h+1})-\mathop{\mathbb{E}}_{s_{i,h+1}}[\overline{V}_{t,h+1}(s_{i,h+1})\,|\,s_{i,h},a_{i,h}]\right)\right\|_{\Sigma^{-1}_{t-1,h}}$
$\displaystyle=\left\|\sum_{i=1}^{t-1}\phi(s_{i,h},a_{i,h})x_{i,\theta_{{\rm{r}}},\theta_{{\rm{P}}},\Sigma}\right\|_{\Sigma_{t-1,h}^{-1}}$
$\displaystyle=\left\|\sum_{i=1}^{t-1}\phi(s_{i,h},a_{i,h})x_{i,\tilde{\theta}_{{\rm{r}}},\tilde{\theta}_{{\rm{P}}},\Sigma}\right\|_{\Sigma_{t-1,h}^{-1}}+\left\|\sum_{i=1}^{t-1}\phi(s_{i,h},a_{i,h})\big{(}x_{i,\theta_{{\rm{r}}},\theta_{{\rm{P}}},\Sigma}-x_{i,\tilde{\theta}_{{\rm{r}}},\tilde{\theta}_{{\rm{P}}},\Sigma}\big{)}\right\|_{\Sigma_{t-1,h}^{-1}}$

where the second term is bounded by

$\displaystyle\left\|\sum_{i=1}^{t-1}\phi(s_{i,h},a_{i,h})\big{(}x_{i,\theta_{{\rm{r}}},\theta_{{\rm{P}}},\Sigma}-x_{i,\tilde{\theta}_{{\rm{r}}},\tilde{\theta}_{{\rm{P}}},\Sigma}\big{)}\right\|_{\Sigma_{t-1,h}^{-1}}$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{t-1}\left\|\phi(s_{i,h},a_{i,h})\big{(}x_{i,\theta_{{\rm{r}}},\theta_{{\rm{P}}},\Sigma}-x_{i,\tilde{\theta}_{{\rm{r}}},\tilde{\theta}_{{\rm{P}}},\Sigma}\big{)}\right\|_{\Sigma_{t-1,h}^{-1}}$
$\displaystyle\leq$ $\displaystyle\sqrt{\lambda^{-1}}\cdot
t\cdot\max_{i}|x_{i,\theta_{{\rm{r}}},\theta_{{\rm{P}}},\Sigma}-x_{i,\tilde{\theta}_{{\rm{r}}},\tilde{\theta}_{{\rm{P}}},\Sigma}|$
$\displaystyle\leq$ $\displaystyle 6/\sqrt{\lambda},$

and, applying (10), the first term is bounded by

$\displaystyle\left\|\sum_{i=1}^{t-1}\phi(s_{i,h},a_{i,h})x_{i,\tilde{\theta}_{{\rm{r}}},\tilde{\theta}_{{\rm{P}}},\Sigma}\right\|_{\Sigma_{t-1,h}^{-1}}$
$\displaystyle\leq$
$\displaystyle\sqrt{32V_{\max}^{2}\left(d\log\left(1+\frac{t}{\lambda}\right)+\log(N/\delta)\right)}$
$\displaystyle\leq$
$\displaystyle\sqrt{32V_{\max}^{2}\left(d\log\left(1+\frac{t}{\lambda}\right)+(2d+d^{2})\log\left(\frac{3\Big{(}(B+\epsilon_{{\rm{r}},\xi}/\sqrt{\lambda})+(V_{\max}\sqrt{dt}+\epsilon_{{\rm{P}},\xi})/\sqrt{\lambda}+\sqrt{d}/\lambda\Big{)}}{\omega\delta}\right)\right)}$
$\displaystyle=$ $\displaystyle
V_{\max}\sqrt{32d\log\left(1+\frac{t}{\lambda}\right)+32(2d+d^{2})\log\left(\frac{12V_{\max}^{2}t^{2}\Big{(}(B+\epsilon_{{\rm{r}},\xi}/\sqrt{\lambda})+(V_{\max}\sqrt{dt}+\epsilon_{{\rm{P}},\xi})/\sqrt{\lambda}+\sqrt{d}/\lambda\Big{)}}{(\alpha_{\rm{U}}-\alpha_{\rm{L}})^{2}\delta}\right)}$

where the second inequality is by inserting the upper bound of the covering
number $N$, and the equality is by inserting the value of $\omega$. The last
line looks complicated and we can further simplify it and get

$\displaystyle\left\|\sum_{i=1}^{t-1}\phi(s_{i,h},a_{i,h})x_{i,\tilde{\theta}_{{\rm{r}}},\tilde{\theta}_{{\rm{P}}},\Sigma}\right\|_{\Sigma_{t-1,h}^{-1}}$
$\displaystyle\leq$ $\displaystyle
16dV_{\max}\sqrt{\log\left(\frac{12V_{\max}t(t+\lambda)\Big{(}(B+\epsilon_{{\rm{r}},\xi}/\sqrt{\lambda})+(V_{\max}\sqrt{dt}+\epsilon_{{\rm{P}},\xi})/\sqrt{\lambda}+\sqrt{d}/\lambda\Big{)}}{(\alpha_{\rm{U}}-\alpha_{\rm{L}})\delta\lambda}\right)}.$

Plugging these upper bounds back, we obtain

$\displaystyle\|\eta_{{\rm{P}},t,h}\|_{\Sigma_{t-1,h}}$
$\displaystyle\leq\frac{6}{\sqrt{\lambda}}+16dV_{\max}\sqrt{\log\left(\frac{12V_{\max}t(t+\lambda)\Big{(}(B+\epsilon_{{\rm{r}},\xi}/\sqrt{\lambda})+(V_{\max}\sqrt{dt}+\epsilon_{{\rm{P}},\xi})/\sqrt{\lambda}+\sqrt{d}/\lambda\Big{)}}{(\alpha_{\rm{U}}-\alpha_{\rm{L}})\delta\lambda}\right)}.$

Applying union bound over all $t\in[T]$ and $h\in[H]$, the upper bound exactly
becomes $\epsilon^{\prime}_{{\rm{P}},\eta}$. Further invoking Lemma B.3
finishes the proof. ∎

######  Lemma B.11 (Boundness of value functions and transition estimation
Error).

Assume the events define in Lemmas B.7 and B.9 hold. Then, the following holds
with probability at least $1-\delta$:

  1. 1.

$\max_{s,a}|\overline{Q}_{t,h}(s,a)|\leq V_{\max}$ for all $t\in[T]$ and
$h\in[H]$.

  2. 2.

$\|\eta_{{\rm{P}},t,h}\|_{\Sigma_{t-1,h}}\leq\epsilon_{{\rm{P}},\eta}$ for all
$t\in[T]$ and $h\in[H]$.

  3. 3.

$\|\lambda_{t,h}\|_{\Sigma_{t-1,h}}\leq\epsilon_{\lambda}$ for all $t\in[T]$
and $h\in[H]$.

The first statement implies $\max_{s}|\overline{V}_{t,h}(s)|\leq V_{\max}$ for
all $t\in[T]$ and $h\in[H]$.

###### Proof.

We prove the three statements together by induction.

For the first statement, we define
$V_{\max,h}\coloneqq(H-h+1)(1+(\epsilon_{{\rm{r}},\xi}+\epsilon_{{\rm{r}},\eta})/\sqrt{\lambda})$,
and we will actually show that
$\max_{s,a}|\overline{Q}_{t,h}(s,a)-Q^{\star}_{h}(s,a)|\leq V_{\max,h}$ in the
induction, which immediately leads to $\max_{s,a}|\overline{Q}_{t,h}(s,a)|\leq
V_{\max,h}+(H-h+1)\leq V_{\max}$.

##### Base.

For $h=H$, we can directly apply Lemma B.10 without the transition argument,
which leads to the desired upper bound of
$\|\eta_{{\rm{P}},t,H}\|_{\Sigma_{t-1,h}}$. Moreover, the upper bound of
$\|\lambda_{t,h}\|_{\Sigma_{t-1,h}}$ also trivially holds. For an upper bound
on the value function, we immediately have

$\displaystyle\big{|}\overline{Q}_{t,H}(s,a)-Q^{\star}_{H}(s,a)\big{|}=\big{|}\phi(s,a)^{\top}(\overline{\theta}_{{\rm{r}},t}-\theta^{\star}_{{\rm{r}}})\big{|}\leq\|\phi(s,a)\|_{\Sigma_{t-1}^{-1}}\|\overline{\theta}_{{\rm{r}},t}-\theta^{\star}_{{\rm{r}}}\|_{\Sigma_{t-1}}$

by Cauchy-Schwarz inequality. We note that
$\|\phi(s,a)\|_{\Sigma_{t-1}^{-1}}\leq\sqrt{\lambda^{-1}}$ and
$\|\overline{\theta}_{{\rm{r}},t}-\theta^{\star}_{{\rm{r}}}\|_{\Sigma_{t-1}}\leq\|\xi_{{\rm{r}},t}+\eta_{{\rm{r}},t}\|_{\Sigma_{t-1}}\leq\|\xi_{{\rm{r}},t}\|_{\Sigma_{t-1}}+\|\eta_{{\rm{r}},t}\|_{\Sigma_{t-1}}\leq\epsilon_{{\rm{r}},\xi}+\epsilon_{{\rm{r}},\eta}$.
Hence, we have

$\displaystyle\big{|}\overline{Q}_{t,H}(s,a)-Q^{\star}_{H}(s,a)\big{|}\leq(\epsilon_{{\rm{r}},\xi}+\epsilon_{{\rm{r}},\eta})/\sqrt{\lambda}\leq
V_{\max,H}.$

##### Inductive Steps.

Now consider $h<H$. By induction hypothesis, we have
$\max_{t,s}|\overline{V}_{t,h+1}(s)|\leq V_{\max}$. Thus, we can apply Lemma
B.10 and get
$\|\eta_{{\rm{P}},t,h}\|_{\Sigma_{t-1,h}}\leq\epsilon_{{\rm{P}},\eta}$. For
the upper bound of $\|\lambda_{t,h}\|_{\Sigma_{t-1,h}}$, by definition, we
have

$\displaystyle\|\lambda_{t,h}\|_{\Sigma_{t-1,h}}=$
$\displaystyle\left\|\lambda\int_{s^{\prime}}\mu^{\star}_{h}(s^{\prime})\overline{V}_{t,h+1}(s^{\prime})\mathop{}\mathrm{d}s^{\prime}\right\|_{\Sigma^{-1}_{t-1,h}}$
$\displaystyle\leq$
$\displaystyle\sqrt{\lambda}\left\|\int_{s^{\prime}}\mu^{\star}_{h}(s^{\prime})\overline{V}_{t,h+1}(s^{\prime})\mathop{}\mathrm{d}s^{\prime}\right\|_{2}$
$\displaystyle\leq$ $\displaystyle V_{\max}\sqrt{\lambda
d}=\epsilon_{\lambda}$

where the second inequality is by
$\|\Sigma^{-1/2}_{t-1,h}\|_{2}\leq\sqrt{\lambda}$, and the last inequality is
by 4.1.

For the upper bound on the value function, consider the following three cases.

##### Case 1: $\|\phi(s,a)\|_{\Sigma_{t-1,h}^{-1}}\leq\alpha_{\rm{L}}$.

We apply Lemma B.5 and get

$\displaystyle|\phi(s,a)^{\top}\left(\overline{\theta}_{{\rm{r}},t}+\overline{\theta}_{{\rm{P}},t,h}\right)-Q^{\star}_{h}(s,a)|$
$\displaystyle=$
$\displaystyle\left|\phi(s,a)^{\top}(\xi_{{\rm{r}},t}+\xi_{{\rm{P}},t,h}+\eta_{{\rm{r}},t}+\eta_{{\rm{P}},t,h}-\lambda_{t,h})+\mathop{\mathbb{E}}_{s^{\prime}}\left[\overline{V}_{t,h+1}(s^{\prime})-V^{\star}_{h+1}(s^{\prime})\,\middle|\,s,a\right]\right|$
$\displaystyle\leq$
$\displaystyle\left|\phi(s,a)^{\top}(\xi_{{\rm{r}},t}+\eta_{{\rm{r}},t})\right|+\left|\phi(s,a)^{\top}(\xi_{{\rm{P}},t,h}+\eta_{{\rm{P}},t,h}-\lambda_{t,h})\right|+\left|\mathop{\mathbb{E}}_{s^{\prime}}\left[\overline{V}_{t,h+1}(s^{\prime})-V^{\star}_{h+1}(s^{\prime})\,\middle|\,s,a\right]\right|$
$\displaystyle\leq$
$\displaystyle(\epsilon_{{\rm{r}},\xi}+\epsilon_{{\rm{r}},\eta})/\sqrt{\lambda}+\|\phi(s,a)\|_{\Sigma_{t-1,h}^{-1}}(\epsilon_{{\rm{P}},\xi}+\epsilon_{{\rm{P}},\eta}+\epsilon_{\lambda})+\Big{(}(H-h)(1+\big{(}\epsilon_{{\rm{r}},\xi}+\epsilon_{{\rm{r}},\eta})/\sqrt{\lambda}\big{)}\Big{)}$
$\displaystyle\leq$
$\displaystyle(\epsilon_{{\rm{r}},\xi}+\epsilon_{{\rm{r}},\eta})/\sqrt{\lambda}+1+\Big{(}(H-h)(1+\big{(}\epsilon_{{\rm{r}},\xi}+\epsilon_{{\rm{r}},\eta})/\sqrt{\lambda}\big{)}\Big{)}$
$\displaystyle=$
$\displaystyle(H-h+1)(1+\big{(}\epsilon_{{\rm{r}},\xi}+\epsilon_{{\rm{r}},\eta})/\sqrt{\lambda}\big{)}$
$\displaystyle=$ $\displaystyle V_{\max,h}$

where the second inequality is by Cauchy-Schwarz inequality, Lemmas B.7 and
B.9, and the induction hypothesis. The third inequality is by the condition
that $\|\phi(s,a)\|_{\Sigma_{t-1,h}^{-1}}\leq\alpha_{\rm{L}}$ and the
definition of $\alpha_{\rm{L}}$.

##### Case 2: $\|\phi(s,a)\|_{\Sigma_{t-1,h}^{-1}}>\alpha_{\rm{U}}$.

We have

$\displaystyle|\overline{Q}_{t,h}(s,a)-Q^{\star}_{h}(s,a)\Big{|}\leq$
$\displaystyle|\phi(s,a)^{\top}\overline{\theta}_{{\rm{r}},t}+H-h-Q^{\star}_{h}(s,a)|$
$\displaystyle=$
$\displaystyle|\phi(s,a)^{\top}(\xi_{{\rm{r}},t}+\eta_{{\rm{r}},t})+H-h+\phi(s,a)^{\top}\theta^{\star}_{{\rm{r}}}-Q^{\star}_{h}(s,a)|$
$\displaystyle\leq$
$\displaystyle(\epsilon_{{\rm{r}},\xi}+\epsilon_{{\rm{r}},\eta})/\sqrt{\lambda}+(H-h+1)$
$\displaystyle\leq$ $\displaystyle V_{\max,h}$

where we used the fact that
$0\leq\phi(s,a)^{\top}\theta^{\star}_{{\rm{r}}}\leq 1$ and $0\leq
Q^{\star}_{h}(s,a)\leq H-h+1$, which leads to
$-(H-h+1)\leq\phi(s,a)^{\top}\theta^{\star}_{{\rm{r}}}-Q^{\star}_{h}(s,a)\leq
1$.

##### Case 3:
$\alpha_{\rm{L}}<\|\phi(s,a)\|_{\Sigma_{t-1,h}^{-1}}\leq\alpha_{\rm{U}}$.

Denoting $\rho\coloneqq\rho(s,a)$ for simplicity, we have

$\displaystyle\Big{|}\overline{Q}_{t,h}(s,a)-Q^{\star}_{h}(s,a)\Big{|}$
$\displaystyle\leq$
$\displaystyle\rho\Big{|}\phi(s,a)^{\top}\left(\overline{\theta}_{{\rm{r}},t}+\overline{\theta}_{{\rm{P}},t,h}\right)-Q^{\star}_{h}(s,a)\Big{|}+(1-\rho)\Big{|}\phi(s,a)^{\top}\overline{\theta}_{{\rm{r}},t}+H-h-Q^{\star}_{h}(s,a)\Big{|}$
$\displaystyle\leq$
$\displaystyle\rho(H-h+1)\Big{(}1+(\epsilon_{{\rm{r}},\xi}+\epsilon_{{\rm{r}},\eta})/\sqrt{\lambda}\Big{)}+(1-\rho)\Big{|}\phi(s,a)^{\top}(\xi_{{\rm{r}},t}+\eta_{{\rm{r}},t})+H-h+\phi(s,a)^{\top}\theta^{\star}_{{\rm{r}}}-Q^{\star}_{h}(s,a)\Big{|}$
$\displaystyle\leq$
$\displaystyle\rho(H-h+1)\Big{(}1+(\epsilon_{{\rm{r}},\xi}+\epsilon_{{\rm{r}},\eta})/\sqrt{\lambda}\Big{)}+(1-\rho)\Big{(}(\epsilon_{{\rm{r}},\xi}+\epsilon_{{\rm{r}},\eta})/\sqrt{\lambda}+(H-h+1)\Big{)}$
$\displaystyle\leq$ $\displaystyle V_{\max,h}$

where we have used the similar arguments from Case 1 and 2.

Taking the maximum over the three cases, we conclude that

$\displaystyle|\overline{Q}_{t,h}(s,a)-Q^{\star}_{h}(s,a)|\leq V_{\max,h}$

which implies $\max_{s,a}|\overline{Q}_{t,h}(s,a)|\leq V_{\max}$. ∎

######  Lemma B.12 (High probability bounds – summary).

All of the following events hold simultaneously with probability at least
$1-\delta$:

  1. 1.

$\|\xi_{{\rm{r}},t}\|_{\Sigma_{t-1}}\leq\epsilon_{{\rm{r}},\xi}$ for all
$t\in[T]$

  2. 2.

$\|\xi_{{\rm{P}},t,h}\|_{\Sigma_{t-1,h}}\leq\epsilon_{{\rm{P}},\xi}$ for all
$t\in[T]$ and $h\in[H]$.

  3. 3.

$\|\eta_{{\rm{r}},t}\|_{\Sigma_{t-1}}\leq\epsilon_{{\rm{r}},\eta}$ for all
$t\in[T]$.

  4. 4.

$\|\eta_{{\rm{P}},t,h}\|_{\Sigma_{t-1,h}}\leq\epsilon_{{\rm{P}},\eta}$ for all
$t\in[T]$ and $h\in[H]$.

  5. 5.

$\|\lambda_{t,h}\|_{\Sigma_{t-1,h}}\leq\epsilon_{\lambda}$ for all $t\in[T]$
and $h\in[H]$.

  6. 6.

$|\overline{Q}_{t,h}(s,a)|\leq V_{\max}$ and $|\overline{V}_{t,h}(s)|\leq
V_{\max}$ for all $(s,a)\in\mathcal{S}\times\mathcal{A}$, $t\in[T]$, and
$h\in[H]$.

###### Proof of Lemma B.12.

The first and second statements are by Lemma B.7. The third is by Lemma B.9.
The last three are by Lemma B.11. Then we take a union bound over all of them.
∎

###  B.4 Bounding regret

We define

$\displaystyle\widetilde{V}_{t}=\mathop{\mathbb{E}}_{\tau\sim\pi_{t}^{1}}\left[\sum_{h=1}^{H}\phi(s_{h},a_{h})^{\top}\overline{\theta}_{{\rm{r}},t}\right].$

######  Lemma B.13.

Assume all events listed in Lemma B.12 hold. Fix $t\in[T]$. Then, we have
$(V^{\star}-\overline{V}_{t})+(\widetilde{V}-V^{\pi_{t}^{1}})\leq 0$ with
probability at least ${\rm{F}}^{2}(-1)$ where ${\rm{F}}$ denotes the CDF of a
standard normal distribution (i.e., $\mathcal{N}(0,1)$).

###### Proof.

Define the indicators

$\displaystyle\bm{L}^{\star}_{t,h}(s)\coloneqq$
$\displaystyle\mathds{1}\left\\{\|\phi(s,\pi^{\star}(s))\|_{\Sigma_{t-1,h}^{-1}}\leq\alpha_{\rm{L}}\right\\},$
$\displaystyle\bm{M}^{\star}_{t,h}(s)\coloneqq$
$\displaystyle\mathds{1}\left\\{\alpha_{\rm{L}}<\|\phi(s,\pi^{\star}(s))\|_{\Sigma_{t-1,h}^{-1}}\leq\alpha_{\rm{U}}\right\\},$
$\displaystyle\bm{U}^{\star}_{t,h}(s)\coloneqq$
$\displaystyle\mathds{1}\left\\{\|\phi(s,\pi^{\star}(s))\|_{\Sigma_{t-1,h}^{-1}}>\alpha_{\rm{U}}\right\\}.$

We note that they are independent of the random noises at episode $t$ and only
depends on the information up to episode $t-1$. Then, we can decompose
$V^{\star}-\overline{V}_{t}$:

$\displaystyle V^{\star}-\overline{V}_{t}=$
$\displaystyle\mathop{\mathbb{E}}_{s_{1}}\left[V^{\star}_{1}(s_{1})-\overline{V}_{t,1}(s_{1})\right]=\mathop{\mathbb{E}}_{s_{1}}\left[Q^{\star}_{1}(s_{1},\pi^{\star}(s_{1}))-\overline{Q}_{t,1}(s_{1},\pi_{t,1}^{0}(s_{1}))\right]$
$\displaystyle\leq$
$\displaystyle\mathop{\mathbb{E}}_{s_{1}}\left[Q^{\star}_{1}(s_{1},\pi^{\star}(s_{1}))-\overline{Q}_{t,1}(s_{1},\pi^{\star}(s_{1}))\right]$
$\displaystyle=$
$\displaystyle\mathop{\mathbb{E}}_{s_{1}}\left[\bm{L}^{\star}_{t,1}(s_{1})\left(Q^{\star}_{1}(s_{1},\pi^{\star}(s_{1}))-\overline{Q}_{t,1}(s_{1},\pi^{\star}(s_{1}))\right)\right]$
$\displaystyle+\mathop{\mathbb{E}}_{s_{1}}\left[\bm{M}^{\star}_{t,1}(s_{1})\left(Q^{\star}_{1}(s_{1},\pi^{\star}(s_{1}))-\overline{Q}_{t,1}(s_{1},\pi^{\star}(s_{1}))\right)\right]$
$\displaystyle+\mathop{\mathbb{E}}_{s_{1}}\left[\bm{U}^{\star}_{t,1}(s_{1})\left(Q^{\star}_{1}(s_{1},\pi^{\star}(s_{1}))-\overline{Q}_{t,1}(s_{1},\pi^{\star}(s_{1}))\right)\right]$
$\displaystyle=:$
$\displaystyle\mathtt{T}_{\rm{L}}+\mathtt{T}_{\rm{M}},+\mathtt{T}_{\rm{U}}.$

Now we establish upper bounds for each term. For $\mathtt{T}_{\rm{U}}$, we
have

$\displaystyle\mathop{\mathbb{E}}_{s_{1}}\left[\bm{U}^{\star}_{t,1}(s_{1})\left(Q^{\star}_{1}(s_{1},\pi^{\star}(s_{1}))-\overline{Q}_{t,1}(s_{1},\pi^{\star}(s_{1}))\right)\right]$
$\displaystyle=$
$\displaystyle\mathop{\mathbb{E}}_{s_{1}}\left[\bm{U}^{\star}_{t,1}(s_{1})\left(Q^{\star}_{1}(s_{1},\pi^{\star}(s_{1}))-\phi(s_{1},\pi^{\star}(s_{1}))^{\top}\overline{\theta}_{{\rm{r}},t}-(H-1)\right)\right]$
$\displaystyle=$
$\displaystyle\mathop{\mathbb{E}}_{s_{1}}\left[\bm{U}^{\star}_{t,1}(s_{1})\left(Q^{\star}_{1}(s_{1},\pi^{\star}(s_{1}))-\phi(s_{1},\pi^{\star}(s_{1}))^{\top}\theta^{\star}_{{\rm{r}}}-\phi(s_{1},\pi^{\star}(s_{1}))^{\top}(\eta_{{\rm{r}},t}+\xi_{{\rm{r}},t})-(H-1)\right)\right]$
$\displaystyle\leq$
$\displaystyle\mathop{\mathbb{E}}_{s_{1}}\left[\left(-\bm{U}^{\star}_{t,1}(s_{1})\phi(s_{1},\pi^{\star}(s_{1}))\right)^{\top}(\eta_{{\rm{r}},t}+\xi_{{\rm{r}},t})\right]$

where the inequality holds since

$\displaystyle
Q^{\star}_{1}(s_{1},\pi^{\star}(s_{1}))-\phi(s_{1},\pi^{\star}(s_{1}))^{\top}\theta^{\star}_{{\rm{r}}}-(H-1)$
$\displaystyle=$
$\displaystyle\phi(s_{1},\pi^{\star}(s_{1}))^{\top}\theta^{\star}_{{\rm{r}}}+\mathop{\mathbb{E}}_{s_{2}}[V^{\star}_{2}(s_{2})\,|\,s_{1},\pi^{\star}(s_{1})]-\phi(s_{1},\pi^{\star}(s_{1}))^{\top}\theta^{\star}_{{\rm{r}}}-(H-1)\leq
0.$

For $\mathtt{T}_{\rm{L}}$, we have

$\displaystyle\mathop{\mathbb{E}}_{s_{1}}\left[\bm{L}^{\star}_{t,1}(s_{1})\left(Q^{\star}_{1}(s_{1},\pi^{\star}(s_{1}))-\overline{Q}_{t,1}(s_{1},\pi^{\star}(s_{1}))\right)\right]$
$\displaystyle=$
$\displaystyle\mathop{\mathbb{E}}_{s_{1}}\left[\bm{L}^{\star}_{t,1}(s_{1})\left(Q^{\star}_{1}(s_{1},\pi^{\star}(s_{1}))-\phi(s_{1},\pi^{\star}(s_{1}))^{\top}(\overline{\theta}_{{\rm{r}},t}+\overline{\theta}_{{\rm{P}},t,h})\right)\right]$
$\displaystyle=$
$\displaystyle\mathop{\mathbb{E}}_{s_{1}}\left[\bm{L}^{\star}_{t,1}(s_{1})\left(-\phi(s_{1},\pi^{\star}(s_{1}))^{\top}(\xi_{{\rm{r}},t}+\xi_{{\rm{P}},t,1}+\eta_{{\rm{r}},t}+\eta_{{\rm{P}},t,1}-\lambda_{t,1})+\mathop{\mathbb{E}}_{s_{2}}\left[V^{\star}_{2}(s_{2})-\overline{V}_{t,2}(s^{\prime})\,\middle|\,s_{1},\pi^{\star}(s_{1})\right]\right)\right]$

where the last equality is by Lemma B.5.

For $\mathtt{T}_{\rm{M}}$, we have

$\displaystyle\mathop{\mathbb{E}}_{s_{1}}\left[\bm{M}^{\star}_{t,1}(s_{1})\left(Q^{\star}_{1}(s_{1},\pi^{\star}(s_{1}))-\overline{Q}_{t,1}(s_{1},\pi^{\star}(s_{1}))\right)\right]$
$\displaystyle=$
$\displaystyle\mathop{\mathbb{E}}_{s_{1}}\bigg{[}\bm{M}^{\star}_{t,1}(s_{1})\bigg{(}\rho(s_{1},\pi^{\star}(s_{1}))\Big{(}Q^{\star}_{1}(s_{1},\pi^{\star}(s_{1}))-\phi(s_{1},\pi^{\star}(s_{1}))^{\top}(\overline{\theta}_{{\rm{r}},t}+\overline{\theta}_{{\rm{P}},t,1})\Big{)}$
$\displaystyle\qquad\qquad\qquad\qquad+\big{(}1-\rho(s_{1},\pi^{\star}(s_{1}))\big{)}\Big{(}Q^{\star}_{1}(s_{1},\pi^{\star}(s_{1}))-\phi(s_{1},\pi^{\star}(s_{1}))^{\top}\overline{\theta}_{{\rm{r}},t}-(H-h)\Big{)}\bigg{)}\bigg{]}$
$\displaystyle\leq$
$\displaystyle\mathop{\mathbb{E}}_{s_{1}}\bigg{[}\bm{M}^{\star}_{t,1}(s_{1})\bigg{(}\rho(s_{1},\pi^{\star}(s_{1}))\bigg{(}-\phi(s_{1},\pi^{\star}(s_{1}))^{\top}(\xi_{{\rm{r}},t}+\xi_{{\rm{P}},t,1}+\eta_{{\rm{r}},t}+\eta_{{\rm{P}},t,1}-\lambda_{t,1})$
$\displaystyle+\mathop{\mathbb{E}}_{s_{2}}\left[V^{\star}_{2}(s_{2})-\overline{V}_{t,2}(s^{\prime})\,\middle|\,s_{1},\pi^{\star}(s_{1})\right]\bigg{)}+\big{(}1-\rho(s_{1},\pi^{\star}(s_{1}))\big{)}\left(-\phi(s_{1},\pi^{\star}(s_{1}))\right)^{\top}(\eta_{{\rm{r}},t}+\xi_{{\rm{r}},t})\bigg{)}\bigg{]}$

where the inequality is by similar arguments as in the case of
$\mathtt{T}_{\rm{U}}$ and $\mathtt{T}_{\rm{L}}$.

So putting $\mathtt{T}_{\rm{L}},\mathtt{T}_{\rm{M}},\mathtt{T}_{\rm{U}}$
together, we have

$\displaystyle V^{\star}-\overline{V}_{t}$ $\displaystyle\leq$
$\displaystyle\mathop{\mathbb{E}}_{s_{1}}\bigg{[}\underbrace{\Big{(}\bm{U}^{\star}_{t,1}(s_{1})+\bm{M}^{\star}_{t,1}(s_{1})(1-\rho(s_{1},\pi^{\star}(s_{1})))\Big{)}}_{=:\bm{UM}^{\star}_{t,1}(s_{1})}(-\phi(s_{1},\pi^{\star}(s_{1})))^{\top}(\eta_{{\rm{r}},t}+\xi_{{\rm{r}},t})$
$\displaystyle\quad+\underbrace{\Big{(}\bm{L}^{\star}_{t,1}(s_{1})+\bm{M}^{\star}_{t,1}(s_{1})\rho(s_{1},\pi^{\star}(s_{1}))\Big{)}}_{=:\bm{LM}^{\star}_{t,1}(s_{1})}\Big{(}-\phi(s_{1},\pi^{\star}(s_{1}))^{\top}(\xi_{{\rm{r}},t}+\xi_{{\rm{P}},t,1}+\eta_{{\rm{r}},t}+\eta_{{\rm{P}},t,1}-\lambda_{t,1})$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad+\mathop{\mathbb{E}}_{s_{2}}\left[V^{\star}_{2}(s_{2})-\overline{V}_{t,2}(s^{\prime})\,\middle|\,s_{1},\pi^{\star}(s_{1})\right]\Big{)}\bigg{]}$

Keeping expanding the last term, we arrive at

$\displaystyle V^{\star}-\overline{V}_{t}\leq$
$\displaystyle\mathop{\mathbb{E}}_{\tau\sim\pi^{\star}}\Bigg{[}\sum_{h=1}^{H}\left(\bm{UM}^{\star}_{t,h}(s_{h})\prod_{i=1}^{h-1}\bm{LM}^{\star}_{t,i}(s_{i})\right)\left(-\phi(s_{h},a_{h})^{\top}(\xi_{{\rm{r}},t}+\eta_{{\rm{r}},t})\right)$
$\displaystyle\qquad+\sum_{h=1}^{H}\left(\prod_{i=1}^{h}\bm{LM}^{\star}_{t,i}(s_{i})\right)\left(-\phi(s_{h},a_{h})^{\top}(\xi_{{\rm{r}},t}+\xi_{{\rm{P}},t,h}+\eta_{{\rm{r}},t}+\eta_{{\rm{P}},t,h}-\lambda_{t,h})\right)\Bigg{]}$
$\displaystyle=$
$\displaystyle\mathop{\mathbb{E}}_{\tau\sim\pi^{\star}}\Bigg{[}\sum_{h=1}^{H}\left(\bm{UM}^{\star}_{t,h}(s_{h})\prod_{i=1}^{h-1}\bm{LM}^{\star}_{t,i}(s_{i})+\prod_{i=1}^{h}\bm{LM}^{\star}_{t,i}(s_{i})\right)\left(-\phi(s_{h},a_{h})^{\top}(\xi_{{\rm{r}},t}+\eta_{{\rm{r}},t})\right)$
$\displaystyle\qquad+\sum_{h=1}^{H}\left(\prod_{i=1}^{h}\bm{LM}^{\star}_{t,i}(s_{i})\right)\left(-\phi(s_{h},a_{h})^{\top}(\xi_{{\rm{P}},t,h}+\eta_{{\rm{P}},t,h}-\lambda_{t,h})\right)\Bigg{]}$
$\displaystyle=:$
$\displaystyle(-\phi^{\star}_{\rm{r}})^{\top}(\xi_{{\rm{r}},t}+\eta_{{\rm{r}},t})+\sum_{h=1}^{H}(-\phi^{\star}_{{\rm{P}},h})^{\top}(\xi_{{\rm{P}},t,h}+\eta_{{\rm{P}},t,h}-\lambda_{t,h})$

where in the last step we defined $\phi^{\star}_{\rm{r}}$ and
$\phi^{\star}_{{\rm{P}},h}$ as

$\displaystyle\phi^{\star}_{\rm{r}}\coloneqq$
$\displaystyle\mathop{\mathbb{E}}_{\tau\sim\pi^{\star}}\left[\sum_{h=1}^{H}\left(\bm{UM}^{\star}_{t,h}(s_{h})\prod_{i=1}^{h-1}\bm{LM}^{\star}_{t,i}(s_{i})+\prod_{i=1}^{h}\bm{LM}^{\star}_{t,i}(s_{i})\right)\phi(s_{h},a_{h})\right],$
$\displaystyle\phi^{\star}_{{\rm{P}},h}\coloneqq$
$\displaystyle\mathop{\mathbb{E}}_{\tau\sim\pi^{\star}}\left[\left(\prod_{i=1}^{h}\bm{LM}^{\star}_{t,i}(s_{i})\right)\phi(s_{h},a_{h})\right].$

Now we also decompose $\widetilde{V}_{t}-V^{\pi_{t}^{1}}$ and get

$\displaystyle\widetilde{V}_{t}-V^{\pi_{t}^{1}}=$
$\displaystyle\mathop{\mathbb{E}}_{\tau\sim\pi_{t}^{1}}\left[\sum_{h=1}^{H}\phi(s_{h},a_{h})\right]^{\top}\left(\overline{\theta}_{{\rm{r}},t}-\theta^{\star}_{{\rm{r}}}\right)$
$\displaystyle=$
$\displaystyle\mathop{\mathbb{E}}_{\tau\sim\pi_{t}^{1}}\left[\sum_{h=1}^{H}\phi(s_{h},a_{h})\right]^{\top}\left(\xi_{{\rm{r}},t}+\eta_{{\rm{r}},t}\right)$
$\displaystyle=:$
$\displaystyle(\widetilde{\phi}_{t})^{\top}\left(\xi_{{\rm{r}},t}+\eta_{{\rm{r}},t}\right).$

Combining the decomposition together, we obtain

$\displaystyle(V^{\star}-\overline{V}_{t})+(\widetilde{V}-V^{\pi_{t}^{1}})$
$\displaystyle\leq$
$\displaystyle\left((-\phi^{\star}_{\rm{r}})^{\top}(\xi_{{\rm{r}},t}+\eta_{{\rm{r}},t})+\sum_{h=1}^{H}(-\phi^{\star}_{{\rm{P}},h})^{\top}(\xi_{{\rm{P}},t,h}+\eta_{{\rm{P}},t,h}-\lambda_{t,h})\right)+\widetilde{\phi}_{t}^{\top}(\xi_{{\rm{r}},t}+\eta_{{\rm{r}},t})$
$\displaystyle=$
$\displaystyle\left(\widetilde{\phi}_{t}-\phi^{\star}\right)^{\top}\left(\xi_{{\rm{r}},t}+\eta_{{\rm{r}},t}\right)+\sum_{h=1}^{H}(-\phi^{\star}_{{\rm{P}},h})^{\top}\left(\xi_{{\rm{P}},t,h}+\eta_{{\rm{P}},t,h}-\lambda_{t,h}\right)$
$\displaystyle\leq$
$\displaystyle\|\widetilde{\phi}_{t}-\phi^{\star}\|_{\Sigma^{-1}_{t-1}}\|\eta_{{\rm{r}},t}\|_{\Sigma_{t-1}}+(\widetilde{\phi}_{t}-\phi^{\star})^{\top}\xi_{{\rm{r}},t}$
$\displaystyle+\sum_{h=1}^{H}\|\phi^{\star}_{{\rm{P}},h}\|_{\Sigma^{-1}_{t-1,h}}\left(\|\eta_{{\rm{P}},t,h}\|_{\Sigma_{t-1,h}}+\|\lambda_{t,h}\|_{\Sigma_{t-1,h}}\right)-\sum_{h=1}^{H}{\phi^{\star}_{{\rm{P}},h}}^{\top}\xi_{{\rm{P}},t,h}$
$\displaystyle\leq$
$\displaystyle\|\widetilde{\phi}_{t}-\phi^{\star}\|_{\Sigma^{-1}_{t-1}}\epsilon_{{\rm{r}},\eta}-(\widetilde{\phi}_{t}-\phi^{\star})^{\top}\xi_{{\rm{r}},t}+\sqrt{\sum_{h=1}^{H}\|\phi^{\star}_{{\rm{P}},h}\|^{2}_{\Sigma^{-1}_{t-1,h}}}\cdot\sqrt{H(\epsilon_{{\rm{P}},\eta}+\epsilon_{\lambda})^{2}}-\sum_{h=1}^{H}{\phi^{\star}_{{\rm{P}},h}}^{\top}\xi_{{\rm{P}},t,h}$
$\displaystyle=$
$\displaystyle\underbrace{\|\widetilde{\phi}_{t}-\phi^{\star}\|_{\Sigma^{-1}_{t-1}}\epsilon_{{\rm{r}},\eta}-(\widetilde{\phi}_{t}-\phi^{\star})^{\top}\xi_{{\rm{r}},t}}_{(a)}$
$\displaystyle+\underbrace{\sqrt{\sum_{h=1}^{H}\min\left\\{1,\|\phi^{\star}_{{\rm{P}},h}\|^{2}_{\Sigma^{-1}_{t-1,h}}\right\\}}\cdot\sqrt{H(\epsilon_{{\rm{P}},\eta}+\epsilon_{\lambda})^{2}}-\sum_{h=1}^{H}{\phi^{\star}_{{\rm{P}},h}}^{\top}\xi_{{\rm{P}},t,h}}_{(b)}$

where the second inequality is by Cauchy-Schwarz inequality, the third
inequality is Lemma B.12 and Cauchy-Schwarz inequality again, and the last
step is by the fact that
$\|\phi^{\star}_{{\rm{P}},h}\|^{2}_{\Sigma^{-1}_{t-1,h}}\leq 1/\lambda\leq 1.$

##### For (a),

we note that
$(\widetilde{\phi}_{t}-\phi^{\star})^{\top}\xi_{{\rm{r}},t}\sim\mathcal{N}(0,\sigma_{{\rm{r}}}^{2}\|\widetilde{\phi}_{t}-\phi^{\star}\|^{2}_{\Sigma^{-1}_{t-1}})$.
So by setting $\sigma_{{\rm{r}}}\geq\epsilon_{{\rm{r}},\eta}$ , we have
$(a)\leq 0$ with probability at least ${\rm{F}}(-1)$.

##### For (b),

similarly, we note that
$\sum_{h=1}^{H}{\phi^{\star}_{{\rm{P}},h}}^{\top}\xi_{{\rm{P}},t,h}\sim\mathcal{N}(0,\sigma_{{\rm{P}}}^{2}\sum_{h=1}^{H}\|\phi^{\star}_{{\rm{P}},h}\|^{2}_{\Sigma_{t-1,h}^{-1}})$.
So by setting
$\sigma_{{\rm{P}}}\geq\sqrt{H(\epsilon_{{\rm{P}},\eta}+\epsilon_{\lambda})^{2}}$,
we have $(b)\leq 0$ with probability at least ${\rm{F}}(-1)$.