commentblock draftblock

# On Sample-Efficient Offline Reinforcement Learning: Data Diversity,
Posterior Sampling, and Beyond

Thanh Nguyen-Tang & Raman Arora
Department of Computer Science
Johns Hopkins University, Baltimore, MD 21218

###### Abstract.

We seek to understand what facilitates sample-efficient learning from
historical datasets for sequential decision-making, a problem that is
popularly known as offline reinforcement learning (RL). Further, we are
interested in algorithms that enjoy sample efficiency while leveraging (value)
function approximation. In this paper, we address these fundamental questions
by (i) proposing a notion of data diversity that subsumes the previous notions
of coverage measures in offline RL and (ii) using this notion to unify three
distinct classes of offline RL algorithms based on version spaces (VS),
regularized optimization (RO), and posterior sampling (PS). We establish that
VS-based, RO-based, and PS-based algorithms, under standard assumptions,
achieve _comparable_ sample efficiency, which recovers the state-of-the-art
sub-optimality bounds for finite and linear model classes with the standard
assumptions. This result is surprising, given that the prior work suggested an
unfavorable sample complexity of the RO-based algorithm compared to the VS-
based algorithm, whereas posterior sampling is rarely considered in offline RL
due to its explorative nature. Notably, our proposed model-free PS-based
algorithm for offline RL is novel, with sub-optimality bounds that are
frequentist (i.e., worst-case) in nature.

##  1\. Introduction

Learning from previously collected experiences is a vital capability for
reinforcement learning (RL) agents, offering a broader scope of applications
compared to online RL. This is particularly significant in domains where
interacting with the environment poses risks or high costs. However,
effectively extracting valuable policies from historical datasets remains a
considerable challenge, especially in high-dimensional spaces where the
ability to generalize across various scenarios is crucial. In this paper, our
objective is to comprehensively examine the efficiency of offline RL in the
context of (value) function approximation. We aim to analyze this within the
broader framework of general data collection settings.

The problem of learning from historical datasets for sequential decision-
making, commonly known as _offline RL_ or _batch RL_ , originated in the early
2000s (Ernst et al., 2005; Antos et al., 2006; Lange et al., 2012) and has
recently regained significant attention (Levine et al., 2020; Uehara et al.,
2022a). In offline RL, where direct interaction with environments is not
possible, our goal is to learn an effective policy by leveraging pre-collected
datasets, typically obtained from different policies known as _behavior
policies_. The sample efficiency of an offline RL algorithm is measured by the
sub-optimality of the policies it executes compared to a “good” comparator
policy, which may or may not be an optimal policy. Due to the lack of
exploration inherent in offline RL, designing an algorithm with low sub-
optimality requires employing the fundamental principle of _pessimistic
extrapolation_. This means that the agent extrapolates from the offline data
while considering the worst-case scenarios that are consistent with that data.
Essentially, the _diversity_ present in the offline data determines the
agent’s ability to construct meaningful extrapolations. Hence, a suitable
notion of data diversity plays a crucial role in offline RL.

To address the issue of data diversity, several prior methods have made the
assumption that the offline data is _uniformly diverse_ – this implies that
the data should cover the entire trajectory space with some probability that
is bounded from below (Munos and Szepesvári, 2008; Chen and Jiang, 2019;
Nguyen-Tang et al., 2022b). This assumption is often too strong and not
feasible in many practical scenarios. In more recent approaches (Jin et al.,
2021b; Xie et al., 2021; Uehara and Sun, 2022; Chen and Jiang, 2022;
Rashidinejad et al., 2023), the stringent assumption of uniform diversity has
been relaxed to only require _partial_ diversity in the offline data. Various
measures have been proposed to capture this partial diversity, such as single-
policy concentrability coefficients (Liu et al., 2019; Rashidinejad et al.,
2021; Yin and Wang, 2021), relative condition numbers (Agarwal et al., 2021;
Uehara and Sun, 2022), and Bellman residual ratios (Xie et al., 2021). These
measures aim to quantify the extent to which the data captures diverse states
and behaviors. However, it should be noted that in some practical scenarios,
these measures may become excessive or may not hold at all.

In terms of algorithmic approaches, existing sample-efficient offline RL
algorithms explicitly construct pessimistic estimates of models or value
functions to effectively learn from datasets with partial diversity. This is
typically achieved through the construction of lower confidence bounds (LCBs)
(Jin et al., 2021b; Rashidinejad et al., 2021) or version spaces (VS) (Xie et
al., 2021; Zanette et al., 2021). LCB-based algorithms incorporate a bonus
term subtracted from the value estimates to enforce pessimism across all
state-action pairs and stages. However, it has been observed that LCB-based
algorithms tend to impose unnecessarily aggressive pessimism, leading to sub-
optimal bounds (Zanette et al., 2021). On the other hand, VS-based algorithms
search through the space of consistent hypotheses to identify the one with the
smallest value in the initial states. These algorithms have demonstrated
state-of-the-art bounds (Zanette et al., 2021; Xie et al., 2021).

In contrast to LCB-based and VS-based algorithms, regularized (minimax)
optimization (RO) and posterior sampling (PS) are more amenable to tractable
implementations but are relatively new in the offline RL literature. The RO-
based algorithm initially introduced by (Xie et al., 2021, Algorithm 1)
incorporates pessimism implicitly through a regularization term that promotes
pessimism in the initial state. This approach eliminates the need for an
intractable search over the version space. However, Xie et al. (2021)
demonstrate that the RO-based algorithm exhibits a significantly slower sub-
optimality rate than standard VS-based algorithms. Specifically, the RO-based
algorithm achieves a sub-optimality rate of $K^{-1/3}$, whereas VS-based
algorithms achieve a faster rate of $K^{-1/2}$, where $K$ represents the
number of episodes in the offline data.

Algorithms | Sub-optimality Bound | Data
---|---|---
VS in (Xie et al., 2021) | $Hb\sqrt{{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}C_{2}(\pi)}\cdot{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\ln(|{\mathcal{F}}|\cdot|\Pi^{all}|)}}\cdot{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}K^{-1/2}}$ | I
RO in (Xie et al., 2021) | $Hb\sqrt{{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}C_{2}(\pi)}}\cdot\sqrt[3]{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\ln(|{\mathcal{F}}|\cdot|\Pi^{soft}(T)|)}}\cdot{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}K^{-1/3}}+Hb/\sqrt{T}$ | I
MBPS in (Uehara and Sun, 2022) |  $Hb\sqrt{{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}C^{\text{Bayes}}}\cdot{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\ln|{\mathcal{M}}|}}\cdot{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}K^{-1/2}}$ (Bayesian) | I
VS in Algorithm 2 | $Hb\sqrt{{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}{\mathcal{C}}(\pi;1/\sqrt{K})}\cdot{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\ln(|{\mathcal{F}}|\cdot|\Pi^{soft}(T)|)}}\cdot{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}K^{-1/2}}+Hb/\sqrt{T}$ | A
RO in Algorithm 3 | $Hb\sqrt{{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}{\mathcal{C}}(\pi;1/\sqrt{K})}\cdot{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\ln(|{\mathcal{F}}|\cdot|\Pi^{soft}(T)|)}}\cdot{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}K^{-1/2}}+Hb/\sqrt{T}$ | A
MFPS in Algorithm 4 | $Hb\sqrt{{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}{\mathcal{C}}(\pi;1/\sqrt{K})}\cdot{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\ln(|{\mathcal{F}}|\cdot|\Pi^{soft}(T)|)}}\cdot{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}K^{-1/2}}+Hb/\sqrt{T}$ (frequentist) | A

Table 1. Comparison of our bounds with SOTA bounds for offline RL under
partial coverage and function approximation, where gray cells mark our
contributions. Algorithms: VS = version space, RO = regularized optimization,
MBPS = model-based posterior sampling, and MFPS = model-free posterior
sampling. Sub-optimality bound: $K$ = #number of episodes, $\pi$ = an
_arbitrary_ comparator policy, $H$ = horizon, $b$ = boundedness, $T$ = the
number of algorithmic updates,
$\ln|{\mathcal{F}}|,\ln|\Pi^{soft}(T)|,\ln|\Pi^{all}|,\ln|{\mathcal{M}}|$:
complexity measures of some value function class ${\mathcal{F}}$, “induced”
policy class $\Pi^{soft}(T)$, the class of all comparator policies
$\Pi^{all}$, and model class ${\mathcal{M}}$, where typically
$\Pi^{soft}(T)\subset\Pi^{all},\forall T$. Data: I = independent episodes, A =
adaptively collected data. Here ${\mathcal{C}}(\pi;1/\sqrt{K})$ and
$C_{2}(\pi)$ are some measures of extrapolation from the offline data to
target policy $\pi$.

On the other hand, posterior sampling (PS) (Thompson, 1933; Russo and Van Roy,
2014), a popular and successful method in online RL, is rarely explored in the
context of offline RL. PS involves sampling from a constructed posterior
distribution over the model or value function and acting accordingly. However,
PS is less commonly considered in offline RL due to its explorative nature,
which stems from the randomness of the posterior distribution. This randomness
is well-suited for addressing the exploration challenge in online RL tasks
(Zhang, 2022; Dann et al., 2021; Zhong et al., 2022; Agarwal and Zhang, 2022).
The only work that considers PS for offline RL is Uehara and Sun (2022), where
they maintain a posterior distribution over Markov decision process (MDP)
models. However, this model-based PS approach is limited to small-scale
problems where computing the optimal policy from an MDP model is
computationally feasible. In addition, this work only provides a weak form of
guarantees via Bayesian bounds.

In the context of (value) function approximation, achieving sample-efficient
offline RL relies on certain conditions that facilitate effective learning.
The identification of the minimum condition required for sample efficiency, as
well as the algorithms that can exploit such conditions, is an important
research question that we aim to address here. We advance our understanding by
making the following contributions: (I) We introduce a new notion of data
diversity that subsumes and expands almost all the prior distribution shift
measures in offline RL, and (II) We show that all VS-based, RO-based and PS-
based algorithms are in fact (surprisingly) competitive to each other, i.e.,
under standard assumptions, they achieve the same sub-optimality bounds (up to
constant and log factors). We summarize our key results in comparison with
related work in Table 1. Our results further expand the class of sample-
efficient offline RL problems (Figure 1) and provide more choices of offline
RL algorithms with competitive guarantees and tractable approximations for
practitioners to choose from.

For establishing (II), we need to construct concrete VS-based, RO-based and
PS-based algorithms. While the key components of the VS-based and RO-based
algorithms appear in the literature (Xie et al., 2021), we propose a novel, a
first-of-its-kind, model-free posterior sampling algorithm for offline RL. The
algorithm contains two new ingredients: a pessimistic prior that encourages
pessimistic value functions when being sampled from the posterior distribution
and integration of posterior sampling with the actor-critic framework that
incrementally updates the learned policy.

##### Overview of Techniques.

Our analysis method presents a “decoupling” argument tailored for the batch
setting, drawing inspiration from recent decoupling arguments in the online RL
setting (Foster et al., 2021; Jin et al., 2021a; Zhang, 2022; Dann et al.,
2021; Zhong et al., 2022; Agarwal and Zhang, 2022). The core idea behind our
decoupling argument is to establish a relationship between the Bellman error
under any comparator policy $\pi$ and the squared Bellman error under the
behavior policy. This relationship is mediated through our novel concept of
data diversity, denoted as ${\mathcal{C}}(\pi;{\epsilon}_{c})$, which is
defined in detail in 3. This allows to separate the sub-optimality of a
learned policy into two main sources of errors: the extrapolation error, which
captures the out-of-distribution (OOD) generalization from the behavior policy
to a target policy, and the in-distribution error, which focuses on
generalization within the same behavior distribution. The OOD error is
effectively managed by controlling the data diversity
${\mathcal{C}}(\pi;{\epsilon}_{c})$, while the in-distribution error is
carefully addressed by utilizing the algorithmic structures and the martingale
counterpart to Bernstein’s inequality (i.e., Freedman’s inequality).

In the process of bounding the in-distribution error of our proposed PS
algorithm that we built upon the technique of Dann et al. (2021), we correct a
non-rigorous argument of Dann et al. (2021) (which we discuss in detail in
Section D.3.1) and develop a new technical argument to handle the statistical
dependence induced by the data-dependent target policy in the actor-critic
framework. Our new argument carefully incorporates the uniform convergence
argument into the in-expectation bounds of PS. We give a detailed description
of this argument in Section D.3. As an immediate application, our technique
fixes a non-rigorous mistake involving how to handle the statistical
dependence induced by the min player in the self-play posterior sampling
algorithm of Xiong et al. (2022).

##  2\. Background and problem formulation

###  2.1. Episodic time-inhomogenous Markov decision process

Let ${\mathcal{S}}$ and ${\mathcal{A}}$ denote Lebesgue-measurable state and
action spaces (possibly infinite), respectively. Let
${\mathcal{P}}({\mathcal{S}})$ denote the space of all probability
distributions over ${\mathcal{S}}.$ We consider an episodic time-inhomogeneous
Markov decision process $M=({\mathcal{S}},{\mathcal{A}},P,r,H)$, where
$P=\\{P_{h}\\}_{h\in[H]}\in\\{{\mathcal{S}}\times{\mathcal{A}}\rightarrow{\mathcal{P}}({\mathcal{S}})\\}^{H}$
are the transition probabilities (where $[H]:=\\{1,\ldots,H\\}$),
$r=\\{r_{h}\\}_{h\in[H]}\in\\{{\mathcal{S}}\times{\mathcal{A}}\rightarrow{\mathbb{R}}\\}^{H}$
is the mean reward functions, and $H\in{\mathbb{N}}$ is the length of the
horizon for each episode.

For any policy
$\pi=\\{\pi_{h}\\}_{h\in[H]}\in\\{{\mathcal{S}}\rightarrow{\mathcal{P}}({\mathcal{A}})\\}^{H}$,
the action-value functions and the value functions under policy $\pi$ are
defined, respectively, as
$Q^{\pi}_{h,M}(s,a)={\mathbb{E}}_{\pi}[\sum_{i=h}^{H}r_{i}(s_{i},a_{i})\mid(s_{h},a_{h})=(s,a)]$,
and
$V^{\pi}_{h,M}(s)={\mathbb{E}}_{\pi}[\sum_{i=h}^{H}r_{i}(s_{i},a_{i})|s_{h}=s]$.
Here ${\mathbb{E}}_{\pi}[\cdot]$ denotes the expectation with respect to the
randomness of the trajectory $(s_{h},a_{h},\ldots,s_{H},a_{H})$, with
$a_{i}\sim\pi_{i}(\cdot|s_{i})$ and $s_{i+1}\sim P_{i}(\cdot|s_{i},a_{i})$ for
all $i$. For any policy $\pi$, we define the visitation density probability
functions
$d^{\pi}_{M}=\\{d^{\pi}_{h,M}\\}_{h\in[H]}\in\\{{\mathcal{S}}\times{\mathcal{A}}\rightarrow{\mathbb{R}}_{+}\\}^{H}$
as $d^{\pi}_{h}(s,a):=\frac{d\Pr((s_{h},a_{h})=(s,a)|\pi,M)}{d\rho(s,a)}$
where $\rho$ is the Lebesgue measure on ${\mathcal{S}}\times{\mathcal{A}}$ and
$\Pr((s_{h},a_{h})=(s,a)|\pi,M)$ is the probability of policy $\pi$ reaching
state-action pair $(s,a)$ at timestep $h$.

The Bellman operator ${\mathbb{T}}_{h}^{\pi}$ is defined as
$[{\mathbb{T}}_{h}^{\pi}Q](s,a):=r_{h}(s,a)+{\mathbb{E}}_{s^{\prime}\sim
P_{h}(\cdot|s,a),a^{\prime}\sim\pi_{h+1}(\cdot|s^{\prime})}\left[Q(s^{\prime},a^{\prime})\right]$,
for any $Q:{\mathcal{S}}\times{\mathcal{A}}\rightarrow{\mathbb{R}}$. Let
$\pi^{*}$ be an optimal policy, i.e., $Q^{\pi^{*}}_{h}(s,a)\geq
Q^{\pi}_{h}(s,a),\forall(s,a,h,\pi)\in{\mathcal{S}}\times{\mathcal{A}}\times[H]\times\Pi^{all}$,
where
$\Pi^{all}:=\\{{\mathcal{S}}\rightarrow{\mathcal{P}}({\mathcal{A}})\\}^{H}$ is
the set of all possible policies. For simplicity, we assume that the initial
state $s_{1}$ is deterministic across all episodes.111This assumption is
merely for the sake of clean presentation which does not affect any results.
We also assume that there is some $b>0$ such that for any trajectory
$(s_{1},a_{1},r_{1},\ldots,s_{H},a_{H},r_{H})$ generated under any policy,
$|r_{h}|\leq b,\forall h$ and $|\sum_{h=1}^{H}r_{h}|\leq b$ almost
surely.222Note that we allow the reward samples to be negative.

This boundedness assumption is standard and subsumes the boundedness
conditions in the previous works, e.g., Zanette et al. (2021) set $b=1$ and
Jin et al. (2021b) use $b=H$ (and further assume that $r_{h}\in[0,1],\forall
h$).333We can replace the condition $|r_{h}|\leq b,\forall h$ with $1$-sub-
Gaussian condition: $r_{h}\sim R_{h}(s_{h},a_{h})$ wherein
$R_{h}(s_{h},a_{h})$ is sub-Gaussian with mean $r_{h}(s_{h},a_{h})$ – which
replaces $b$ in our main theorems by $b+\ln(KH/\delta)$. Without loss of
generality, we assume that $b\geq 1$.

##### Additional notation.

For any $u:{\mathcal{S}}\times{\mathcal{A}}\rightarrow{\mathbb{R}}$ and any
$\pi:{\mathcal{S}}\rightarrow{\mathcal{P}}({\mathcal{A}})$, we overload the
notation $u(s,\pi):={\mathbb{E}}_{a\sim\pi(\cdot|s)}\left[u(s,a)\right]$. For
any $f:{\mathcal{S}}\times{\mathcal{A}}\rightarrow{\mathbb{R}}$, denote the
supremum norm
$\|f\|_{\infty}=\max_{(s,a)\in{\mathcal{S}}\times{\mathcal{A}}}|f(s,a)|$. We
write ${\mathbb{E}}[g]^{2}:=({\mathbb{E}}[g])^{2}$. For a probability measure
$\nu$ on some measurable space $(\Omega,{\mathcal{B}})$, we denote by
${\mathrm{supp}}(\nu)$ the support of $\nu$,
${\mathrm{supp}}(\nu):=\\{B\in{\mathcal{B}}:\nu(B)>0\\}$. We denote $x\lesssim
y$ to mean that $x={\mathcal{O}}(y)$.

###  2.2. Offline data generation

Denote the pre-collected dataset by
${\mathcal{D}}:=\\{(s^{t}_{h},a^{t}_{h},r^{t}_{h})\\}_{h\in[H]}^{t\in[K]}$,
where $s^{t}_{h+1}\sim P_{h}(\cdot|s^{t}_{h},a^{t}_{h})$ and
${\mathbb{E}}[r^{t}_{h}|s^{t}_{h},a^{t}_{h}]=r_{h}(s^{t}_{h},a^{t}_{h})$. We
consider the adaptively collected data setting where the offline data is
collected by _time-varying_ behavior policies $\\{\mu^{k}\\}_{k\in[K]}$,
concretely, defined as follows.

######  Definition 1 (Adaptively collected data444It is essentially the
“measurability” condition in Zanette et al. (2021) and “compliance” condition
in Jin et al. (2021b).).

$\mu^{k}$ is a function of
$\\{(s^{i}_{h},a^{i}_{h},r^{i}_{h})\\}_{h\in[H]}^{i\in[k-1]},~{}\forall
k\in[K]$.

For simplicity, we denote $\mu=\frac{1}{K}\sum_{k=1}^{K}\mu^{k}$,
$d^{\mu}=\frac{1}{K}\sum_{k=1}^{K}d^{\mu^{k}}$, and
${\mathbb{E}}_{\mu}[\cdot]=\frac{1}{K}\sum_{k=1}^{K}{\mathbb{E}}_{\mu^{k}}[\cdot]$.
The setting of adaptively collected data covers a common practice where the
offline data is collected by using some adaptive experimentation (Zhan et al.,
2023). When $\mu^{1}=\cdots=\mu^{K}$, it recovers the setting of independent
episodes in Duan et al. (2020).

##### Value sub-optimality.

The goodness of a learned policy $\hat{\pi}=\hat{\pi}({\mathcal{D}})$ against
a comparator policy $\pi$ for the underlying MDP $M$ is measured by the
(value) sub-optimality defined as

$\displaystyle\mathrm{SubOpt}_{\pi}^{M}(\hat{\pi}):=V_{1}^{\pi}(s_{1})-V_{1}^{\hat{\pi}}(s_{1}).$
(1)

Whenever the context is clear, we drop $M$ in $Q^{\pi}_{M}$, $V^{\pi}_{M}$,
$d^{\pi}_{M}$, and $\mathrm{SubOpt}_{\pi}^{M}(\hat{\pi})$.

###  2.3. Policy and function classes

Next, we define the policy space and the action-value function space over
which we optimize the value sub-optimality. We consider a (Cartesian product)
function class
${\mathcal{F}}={\mathcal{F}}_{1}\times\cdots\times{\mathcal{F}}_{H}\in\\{{\mathcal{S}}\times{\mathcal{A}}\rightarrow[-b,b]\\}^{H}$.

The function class ${\mathcal{F}}$ induces the following (Cartesian product)
policy class
$\Pi^{soft}(T)=\Pi_{1}^{soft}(T)\times\cdots\times\Pi_{H}^{soft}(T)$, where
$\Pi^{soft}_{h}(T):=\\{\pi_{h}(a|s)\propto\exp(\eta\sum_{i=1}^{t}g_{i}(s,a)):t\in[T],g_{i}\in{\mathcal{F}}_{h},\forall
i\in[t],\eta\in[0,1]\\}$ for any $T\in{\mathbb{N}}$.

The motivation for the induced policy class $\Pi^{soft}(T)$ is from the soft
policy iteration (SPI) update where we incrementally update the policy.

We now discuss a set of assumptions that we impose on the policy and function
classes.

######  Assumption 2.1 (Approximate realizability).

There exist $\\{\xi_{h}\\}_{h\in[H]}$ where $\xi_{h}\geq 0$ such that,

$\displaystyle\sup_{T\in{\mathbb{N}},\pi\in\Pi^{soft}(T),(s_{h},a_{h})\in{\mathrm{supp}}(d^{\mu}_{h})}\inf_{f\in{\mathcal{F}}}|f_{h}(s_{h},a_{h})-Q^{\pi}_{h}(s_{h},a_{h})|\leq\xi_{h},~{}~{}\forall
h\in[H].$

2.1 establishes that ${\mathcal{F}}$ can realize $Q^{\pi}$ for any
$\pi\in\Pi^{soft}(T)$ up to some error $\xi\in{\mathbb{R}}^{H}$ in the
supremum norm over the $\mu$-feasible state-action pairs. It strictly
generalizes the assumption in Zanette et al. (2021) which restricts
$\xi_{h}=0,~{}\forall h$ (i.e., assume realizability) and the assumption in
Xie et al. (2021) which constrains the approximation error under any feasible
state-action distribution.

The realizability in _value_ functions alone is known to be insufficient for
sample-efficient offline RL (Wang et al., 2021); thus, one needs to impose a
stronger assumption for polynomial sample complexity of model-free
methods.555A stronger form of realizability is sufficient for polynomial
sample complexity, e.g., realizability for a density ratio w.r.t. the behavior
state-action distribution in dual-primal methods (Zhan et al., 2022; Chen and
Jiang, 2022; Rashidinejad et al., 2023) or realizability for the underlying
MDP in model-based methods (Uehara and Sun, 2022). Instead, we pursue model-
free value-based methods. In this paper, we impose an assumption on the
closedness of the Bellman operator.

######  Assumption 2.2 (General Restricted Bellman Closedness).

There exists $\nu\in{\mathbb{R}}^{H}$ such that

$\displaystyle\sup_{T\in{\mathbb{N}},f_{h+1}\in{\mathcal{F}}_{h+1},\tilde{\pi}\in\Pi^{soft}(T)}\inf_{f^{\prime}_{h}\in{\mathcal{F}}_{h}}\|f^{\prime}_{h}-{\mathbb{T}}_{h}^{\tilde{\pi}}f_{h+1}\|_{\infty}\leq\nu_{h},~{}~{}\forall
h\in[H].$

2.2 ensures that the value function space ${\mathcal{F}}$ and the induced
policy class $\Pi^{soft}(T)$ for any $T\in{\mathbb{N}}$ are closed under the
Bellman operator up to some error $\nu\in{\mathbb{R}}^{H}$ in the supremum
norm. This assumption is a direct generalization of the Linear Restricted
Bellman Closedness in Zanette et al. (2020) from a linear function class to a
general function class. As remarked by Zanette et al. (2021), the Linear
Restricted Bellman Closedness is already strictly more general than the low-
rank MDPs (Yang and Wang, 2019; Jin et al., 2020).

###  2.4. Effective sizes of policy and function classes

When the function class and the policy class have finite elements, we use
their cardinality $|{\mathcal{F}}_{h}|$ and $|\Pi_{h}^{soft}(T)|$ to measure
their sizes (Jiang et al., 2017; Xie et al., 2021). When they have infinite
elements, we use log-covering numbers, defined as

$\displaystyle d_{{\mathcal{F}}}({\epsilon}):=\max_{h\in[H]}\ln
N({\epsilon};{\mathcal{F}}_{h},\|\cdot\|_{\infty}),\text{ and
}d_{\Pi}({\epsilon},T):=\max_{h\in[H]}\ln
N({\epsilon};\Pi^{soft}_{h}(T),\|\cdot\|_{1,\infty}),$

where
$\|\pi-\pi^{\prime}\|_{1,\infty}=\sup_{s\in{\mathcal{S}}}\int_{{\mathcal{A}}}|\pi(a|s)-\pi^{\prime}(a|s)|d\rho(a)$
for any
$\pi,\pi^{\prime}\in\\{{\mathcal{S}}\rightarrow{\mathcal{P}}({\mathcal{A}})\\}$
and $N({\epsilon};{\mathcal{X}},\|\cdot\|)$ denotes the covering number of a
pseudometric space $({\mathcal{X}},\|\cdot\|)$ with metric $\|\cdot\|$ (Zhang,
2023, e.g. Definition 4.1).

We also define a complexity measure that depends on a prior distribution
$p_{0}$ over ${\mathcal{F}}$ that we employ to favor certain regions of the
function space. Our notion, presented in 2, is simply a direct adaptation of a
similar notation of Dann et al. (2021) to the actor-critic setting.

######  Definition 2.

For any function $f^{\prime}\in{\mathcal{F}}_{h+1}$ and any policy
$\tilde{\pi}\in\Pi^{all}$, we define
${\mathcal{F}}^{\tilde{\pi}}_{h}({\epsilon};f^{\prime}):=\\{f\in{\mathcal{F}}_{h}:\|f-{\mathbb{T}}^{\tilde{\pi}}_{h}f^{\prime}\|_{\infty}\leq{\epsilon}\\}$,
for any ${\epsilon}\geq 0$, and subsequently define

$\displaystyle
d_{0}({\epsilon}):=\\!\\!\\!\\!\\!\\!\\!\\!\\!\sup_{T\in{\mathbb{N}},f\in{\mathcal{F}},\tilde{\pi}\in\Pi^{soft}(T)}\sum_{h=1}^{H}\ln\frac{1}{p_{0,h}({\mathcal{F}}_{h}^{\tilde{\pi}}({\epsilon};f_{h+1}))},d^{\prime}_{0}({\epsilon}):=\\!\\!\\!\\!\\!\\!\\!\\!\\!\sup_{T\in{\mathbb{N}},\tilde{\pi}\in\Pi^{soft}(T)}\sum_{h=1}^{H}\ln\frac{1}{p_{0,h}({\mathcal{F}}_{h}^{\tilde{\pi}}({\epsilon};Q_{h+1}^{\tilde{\pi}}))}.$

The quantity $d_{0}({\epsilon})$ and $d^{\prime}_{0}({\epsilon})$ measures the
concentration of the prior $p_{0}$ over all functions $f\in{\mathcal{F}}$ that
are ${\epsilon}$-close (element-wise) under ${\mathbb{T}}^{\tilde{\pi}}$ and
${\epsilon}$-close (element-wise) to $Q^{\tilde{\pi}}_{h}$, respectively. If a
stronger version of 2.1 is met, i.e.,
$Q^{\tilde{\pi}}_{h}\in{\mathcal{F}}_{h},\forall\tilde{\pi}\in\Pi^{all}_{h},h\in[H]$,
we have $d^{\prime}_{0}({\epsilon})\leq d_{0}({\epsilon}),\forall{\epsilon}$.
For the finite function class ${\mathcal{F}}$ and an uninformative prior
$p_{0,h}(f_{h})=1/|{\mathcal{F}}_{h}|$, under a stronger version of 2.2, i.e.,
$\nu_{h}=0,\forall h$, we have
$d_{0}({\epsilon})\leq\sum_{h=1}^{H}\ln|{\mathcal{F}}_{h}|=\ln|{\mathcal{F}}|.$
For a parametric model, where each $f_{h}=f_{h}^{\theta}$ is represented by a
$d$-dimensional parameter
$\theta\in\Omega_{h}^{\theta}\subset{\mathbb{R}}^{d}$, a prior over
$\Omega^{\theta}$ induces a prior over ${\mathcal{F}}$. If each
$\Omega^{\theta}_{h}$ is compact, we can generally assume the prior that
satisfies
$\sup_{\theta}\ln\frac{1}{p_{0,h}(\theta^{\prime}:\|\theta-\theta^{\prime}\|\leq{\epsilon})}\leq
d\ln(c_{0}/{\epsilon})$ for some constant $c_{0}$. If $f_{h}=f_{h}^{\theta}$
is Lipschitz in $\theta$, we can assume that
$\sup_{\theta}\ln\frac{1}{p_{0,h}(\theta^{\prime}:\|\theta-\theta^{\prime}\|\leq{\epsilon})}\leq
c_{1}d\ln(c_{2}/{\epsilon})$ for some constants $c_{1},c_{2}$. Overall, we can
assume that $d_{0}({\epsilon})\leq c_{1}Hd\ln(c_{2}/{\epsilon})$. A similar
discussion can be found in Dann et al. (2021).

##  3\. Algorithms

1:Offline data ${\mathcal{D}}$, function class ${\mathcal{F}}$, learning rate
$\eta>0$, and iteration number $T$

2:Uniform policy $\pi^{1}=\\{\pi^{1}_{h}\\}_{h\in[H]}$

3:for $t=1,\ldots,T$ do

4:
${\underline{Q}}^{t}={\framebox{\\!CriticCompute\\!}~{}}(\pi^{t},{\mathcal{D}},{\mathcal{F}},\ldots)$

5:
$\pi^{t+1}_{h}(a|s)\propto\pi^{t}_{h}(a|s)\exp(\eta{\underline{Q}}^{t}_{h}(s,a)),\forall(s,a,h)$

6:end for

7:A randomized policy $\hat{\pi}$ as a uniform distribution over
$\\{\pi^{t}\\}_{t\in[T]}$

Algorithm 1
GOPO$({\mathcal{D}},{\mathcal{F}},\eta,T,{\framebox{\\!CriticCompute\\!}~{}})$:
Generic Offline Policy Optimization Framework

Next, we present concrete instances of PS-based, RO-based, and VS-based
algorithms. The RO-based and VS-based algorithms presented here are slight
refinements of their original versions in Xie et al. (2021). The PS-based
algorithm is novel. All three algorithms resemble the actor-critic style
update, inspired by Zanette et al. (2021). We refer to this generic framework
as GOPO (Generic Offline Policy Optimization) presented in Algorithm 1. At
each round $t$, a critic estimates the value ${\underline{Q}}_{h}^{t}$ of the
actor (i.e., policy $\pi^{t}$) using the procedure CriticCompute on 4, and
the actor improves the policy using a multiplicative weights update (Arora et
al., 2012) (5). After $T$ iterations, GOPO returns a policy $\hat{\pi}$ that
is sampled uniformly from the set of the obtained policies
$\\{\pi^{t}\\}_{t\in[T]}$.

To incorporate the pessimism principle, a critic should generate pessimistic
estimates of the value of the actor $\pi^{t}$ in 4. This is where the three
approaches differ – each invokes a different method to compute the critic.
Here, we provide a detailed description of the critic module for each
approach. To aid the presentation, we introduce the total temporal difference
(TD) loss $\hat{L}_{\tilde{\pi}}$, defined as
$\hat{L}_{\tilde{\pi}}(f_{h},f_{h+1}):=\sum_{k=1}^{K}l_{\tilde{\pi}}(f_{h},f_{h+1};z^{k}_{h})$,
where $z_{h}:=$ $(s_{h},a_{h},r_{h},s_{h+1})$,
$z^{k}_{h}:=(s^{k}_{h},a^{k}_{h},r^{k}_{h},s^{k}_{h+1})$, and
$l_{\tilde{\pi}}(f_{h},f_{h+1};z_{h}):=(f_{h}(s_{h},a_{h})-r_{h}-f_{h+1}(s_{h+1},\tilde{\pi}))^{2}$.

##### Version space-based critic (VSC) (Algorithm 2).

Given the actor $\pi^{t}$, at each step $h\in[H]$, VSC directly maintains a
local regression constraint using the offline data:
$\hat{L}_{\pi^{t}}(f_{h},f_{h+1})\leq\inf_{g\in{\mathcal{F}}}\hat{L}_{\pi^{t}}(g_{h},f_{h+1})+\beta$,
where $\beta$ is a confidence parameter and $\hat{L}_{\pi^{t}}(\cdot,\cdot)$
is serving as a proxy to the squared Bellman residual at step $h$. By taking
the function that minimizes the initial value, VSC then finds the most
pessimistic value function ${\underline{Q}}^{t}$ from the version space
${\mathcal{F}}(\beta;\pi^{t})\subseteq{\mathcal{F}}$. In general, the
constrained optimization in 2 is computationally intractable. Note that a
minimax variant of GOPO+VSC first appeared in Xie et al. (2021), where they
directly perform an (intractable) search over the policy space, instead of
using the multiplicative weights algorithm (5) of Algorithm 1.

1:
${\mathcal{F}}(\beta;\pi^{t}):=\\{f\in{\mathcal{F}}:\hat{L}_{\pi^{t}}(f_{h},f_{h+1})\leq\inf_{g\in{\mathcal{F}}}\hat{L}_{\pi^{t}}(g_{h},f_{h+1})+\beta,\forall
h\in[H]\\}$

2:
${\underline{Q}}^{t}\in\operatorname*{arg\,min}_{f\in{\mathcal{F}}(\beta;\pi^{t})}f_{1}(s_{1},\pi^{t})$

3:${\underline{Q}}^{t}$

Algorithm 2 VSC(${\mathcal{D}},{\mathcal{F}},\pi^{t},\beta$): Version Space-
based Critic

##### Regularized optimization-based critic (ROC) (Algorithm 3).

Instead of solving the global constrained optimization in VSC, ROC solves
$\operatorname*{arg\,inf}_{f\in{\mathcal{F}}}\left\\{\lambda
f_{1}(s_{1},\pi^{t}_{1})+{\mathcal{L}}_{\pi^{t}}(f)\right\\}$, where $\lambda$
is a regularization parameter and ${\mathcal{L}}_{\pi^{t}}(f)$, defined in 1
of Algorithm 3. Note that in ROC, pessimism is implicitly encouraged through
the regularization term $\lambda f_{1}(s_{1},\pi^{t})$. We remark that, unlike
VSC, ROC admits tractable approximations that use adversarial training and
work competitively in practice (Cheng et al., 2022). Note that a discounted
variant of GOPO-ROC first appears in (Xie et al., 2021) in discounted MDPs.

1:
${\mathcal{L}}_{\pi^{t}}(f):=\sum_{h=1}^{H}\hat{L}_{\pi^{t}}(f_{h},f_{h+1})-\inf_{g\in{\mathcal{F}}}\sum_{h=1}^{H}\hat{L}_{\pi^{t}}(g_{h},f_{h+1})$

2:
${\underline{Q}}^{t}\leftarrow\operatorname*{arg\,inf}_{f\in{\mathcal{F}}}\left\\{\lambda
f_{1}(s_{1},\pi^{t})+{\mathcal{L}}_{\pi^{t}}(f)\right\\}$

3:${\underline{Q}}^{t}$

Algorithm 3 ROC(${\mathcal{D}},{\mathcal{F}},\pi^{t},\lambda$): Regularized
Optimization-based Critic

##### Posterior sampling-based critic (PSC) in Algorithm 4.

Instead of solving a regularized minimax optimization, PSC samples the value
function ${\underline{Q}}^{t}_{h}$ from the data posterior
$\hat{\pi}(f|{\mathcal{D}},\pi^{t})\propto\tilde{p}_{0}(f)\cdot
p({\mathcal{D}}|f,\pi^{t})$, where $\tilde{p}_{0}(f)$ is the prior over
${\mathcal{F}}$ and $p({\mathcal{D}}|f,\pi^{t})$ is the likelihood function of
the offline data ${\mathcal{D}}$. To formulate the likelihood function
$p({\mathcal{D}}|f,\pi^{t})$, we make use of the squared TD error
$\hat{L}_{\pi^{t}}(\cdot,\cdot)$ and normalization method in (Dann et al.,
2021) to construct an unbiased proxy of the squared Bellman errors. In
particular,
$p({\mathcal{D}}|f,\pi^{t})=\prod_{h\in[H]}\frac{\exp(-\gamma\hat{L}_{\pi^{t}}(f_{h},f_{h+1}))}{{\mathbb{E}}_{f^{\prime}_{h}\sim
p_{0,h}}\exp(-\gamma\hat{L}_{\pi^{t}}(f^{\prime}_{h},f_{h+1}))}$, where
$\gamma$ is a learning rate and $p_{0}$ is an (unregularized) prior over
${\mathcal{F}}$. A value function sampled from the posterior with this
likelihood function is encouraged to have small squared TD errors. The key
ingredient in our algorithmic design is the “pessimistic” prior
$\tilde{p}_{0}(f)=\exp(-\lambda f_{1}(s_{1},\pi_{1}))p_{0}(f)$ where we add a
new regularization term $\exp(-\lambda f_{1}(s_{1},\pi_{1}))$, with $\lambda$
being a regularization parameter – which is inspired by the optimistic prior
in the online setting (Zhang, 2022; Dann et al., 2021). This pessimistic prior
encourages the value function sampled from the posterior to have a small value
in the initial state, implicitly enforcing pessimism. We remark that PSC
requires a sampling oracle and expectation oracle (to compute the
normalization term in the posterior distribution), which could be amenable to
tractable approximations, including replacing expectation oracle with a
sampling oracle (Agarwal and Zhang, 2022) while the sampling oracle can be
implemented via first-order sampling methods (Welling and Teh, 2011) or
ensemble methods (Osband et al., 2016).

1:
${\underline{Q}}^{t}\sim\hat{p}(f|{\mathcal{D}},\pi^{t})\propto\exp\left(-\lambda
f_{1}(s_{1},\pi^{t})\right)p_{0}(f)\prod_{h\in[H]}\frac{\exp\left(-\gamma\hat{L}_{\pi^{t}}(f_{h},f_{h+1})\right)}{{\mathbb{E}}_{f^{\prime}_{h}\sim
p_{0,h}}\exp\left(-\gamma\hat{L}_{\pi^{t}}(f^{\prime}_{h},f_{h+1})\right)}$

2:${\underline{Q}}^{t}$

Algorithm 4 PSC$({\mathcal{D}},{\mathcal{F}},\pi^{t},\lambda,\gamma,p_{0})$:
Posterior Sampling-based Critic

##  4\. Main results

In this section, we shall present the upper bounds of the sub-optimality of
the policies executed by GOPO-VSC, GOPO-ROC, and GOPO-PSC. Our upper bounds
are expressed in terms of a new notion of data diversity.

###  4.1. Data diversity

We now introduce the key notion of data diversity for offline RL. Since the
offline learner does not have direct access to the trajectory of a comparator
policy $\pi\in\Pi^{all}$, they can only observe partial information about the
goodness of $\pi$ channeled through the “transferability” with the behavior
policy $\mu$. The transferability from $\mu$ to $\pi$ depends on how _diverse_
the offline data induced by $\mu$ can be in supporting the extrapolation to
$\pi$. Many prior works require uniform diversity where $\mu$ covers all
feasible scenarios of all comparator policies $\pi$. The data diversity can be
essentially captured by how well the Bellman error under the state-action
distribution induced by $\mu$ can predict the counterpart quantity under the
state-action distribution induced by $\pi$.

Our notion of data diversity, which is inspired by the notion of task
diversity in transfer learning literature (Tripuraneni et al., 2020; Watkins
et al., 2023), essentially encodes the ratio of some proxies of expected
Bellman errors induced by $\mu$ and $\pi$, and is defined as follows.

######  Definition 3.

For any comparator policy $\pi\in\Pi^{all}$, we measure the data diversity of
the behavior policy $\mu$ with respect to a target policy $\pi$ by

$\displaystyle{\mathcal{C}}(\pi;{\epsilon}):=\max_{h\in[H]}\chi_{({\mathcal{F}}_{h}-{\mathcal{F}}_{h})}({\epsilon};d^{\pi}_{h},d^{\mu}_{h}),\forall{\epsilon}\geq
0,$ (2)

where ${\mathcal{F}}_{h}-{\mathcal{F}}_{h}$ is the Minkowski difference
between the function class ${\mathcal{F}}_{h}$ and itself, i.e.,
${\mathcal{F}}_{h}-{\mathcal{F}}_{h}:=\\{f_{h}-f^{\prime}_{h}:f_{h},f^{\prime}_{h}\in{\mathcal{F}}\\}$,
and $\chi_{{\mathcal{Q}}}({\epsilon};q,p)$ is the discrepancy between
distributions $q$ and $p$ under the witness of function class ${\mathcal{Q}}$
defined as

$\displaystyle\chi_{{\mathcal{Q}}}({\epsilon};q,p)=\inf\left\\{C\geq
0:({\mathbb{E}}_{q}[g])^{2}\leq
C\cdot{\mathbb{E}}_{p}[g^{2}]+{\epsilon},\forall g\in{\mathcal{Q}}\right\\}$

with ${\mathcal{Q}}$ being a function class and $p$ and $q$ being two
distributions over the same domain.

Up to a small additive error ${\epsilon}$, a finite
${\mathcal{C}}(\pi;{\epsilon})$ ensures that a proxy of the Bellman error
under the $\pi$-induced state-action distribution is controlled by that under
the $\mu$-induced state-action distribution. Despite the abstraction in the
definition of this data diversity, it is _always_ upper bounded by the single-
policy concentrability coefficient (Liu et al., 2019; Rashidinejad et al.,
2021) and the relative condition number (Agarwal et al., 2021; Uehara et al.,
2022b; Uehara and Sun, 2022) that are both commonly used in many prior offline
RL works. We further discuss our data diversity measure in more detail in
Section 4.2.

###  4.2. Offline learning guarantees

We now utilize data diversity to give learning guarantees of the considered
algorithms for extrapolation to an arbitrary comparator policy
$\pi\in\Pi^{all}$. To aid the representation, in all of the following theorems
we are about to present, we shall set
$\eta=\sqrt{\frac{\ln{\mathrm{Vol}}({\mathcal{A}})}{4(e-2)b^{2}T}}$ in
Algorithm 1, where ${\mathrm{Vol}}({\mathcal{A}})$ is the volume of the action
set ${\mathcal{A}}$ (e.g., ${\mathrm{Vol}}({\mathcal{A}})=|{\mathcal{A}}|$ for
finite ${\mathcal{A}}$), and define, for simplicity, the misspecification
errors $\zeta_{msp}:=K\sum_{h=1}^{H}\left(\nu_{h}^{2}+b\nu_{h}\right)$,
$\tilde{\zeta}_{msp}:=\zeta_{msp}+bK\sum_{h=1}^{H}\xi_{h}$,
$\bar{\nu}:=\sum_{h=1}^{H}\nu_{h}$, the optimization error
$\zeta_{opt}:=Hb\sqrt{T^{-1}\ln{\mathrm{Vol}}({\mathcal{A}})}$, and the
complexity measures
$\tilde{d}_{opt}({\epsilon},T):=\max\\{d_{{\mathcal{F}}}({\epsilon}),d_{\Pi}({\epsilon},T)\\}$,
and
$\tilde{d}_{ps}({\epsilon},T):=\max\\{d_{{\mathcal{F}}}({\epsilon}),d_{\Pi}({\epsilon},T),\frac{d_{0}({\epsilon})}{\gamma
Hb^{2}},\frac{d^{\prime}_{0}({\epsilon})}{\gamma Hb^{2}}\\}$.

######  Theorem 1 (Guarantees for GOPO-VSC).

Let $\hat{\pi}^{vs}$ be the output of Algorithm 1 invoked with CriticCompute
being VSC(${\mathcal{D}},{\mathcal{F}},\pi^{t},\beta$) (Algorithm 2) with
$\beta={\mathcal{O}}(b^{2}K{\epsilon}+bK\max_{h\in[H]}\xi_{h}+Hb^{2}\max\\{\tilde{d}_{opt}({\epsilon},T),\ln(H/\delta)\\})$.
Fix any $\delta\in(0,1]$. Under 2.1-2.2, with probability at least $1-2\delta$
(over the randomness of the offline data), for any
${\epsilon},{\epsilon}_{c},\lambda>0$, and any $\pi\in\Pi^{all}$, we have

$\displaystyle{\mathbb{E}}\left[\mathrm{SubOpt}_{\pi}(\hat{\pi}^{vs})|{\mathcal{D}}\right]$
$\displaystyle\lesssim\frac{Hb^{2}\cdot\max\\{\tilde{d}_{opt}({\epsilon},T),\ln(H/\delta)\\}+b^{2}KH{\epsilon}+\tilde{\zeta}_{msp}}{\lambda}+\frac{\lambda
H\cdot{\mathcal{C}}(\pi;{\epsilon}_{c})}{2K}$
$\displaystyle+H{\epsilon}_{c}+\xi_{1}+\bar{\nu}+\zeta_{opt}.$

######  Theorem 2 (Guarantees for GOPO-ROC).

Let $\hat{\pi}^{ro}$ be the output of Algorithm 1 invoked with CriticCompute
being ROC(${\mathcal{D}},{\mathcal{F}},\pi^{t},\lambda$) (Algorithm 3). Fix
any $\delta\in(0,1]$. Under 2.1-2.2, with probability at least $1-2\delta$
(over the randomness of the offline data), for any
${\epsilon},{\epsilon}_{c},\lambda>0$, and any $\pi\in\Pi^{all}$, we have

$\displaystyle{\mathbb{E}}\left[\mathrm{SubOpt}_{\pi}(\hat{\pi}^{ro})|{\mathcal{D}}\right]$
$\displaystyle\lesssim\frac{Hb^{2}\cdot\max\\{\tilde{d}_{opt}({\epsilon},T),\ln\frac{H}{\delta}\\}+b^{2}KH{\epsilon}+\tilde{\zeta}_{msp}}{\lambda}+\frac{\lambda
H\cdot{\mathcal{C}}(\pi;{\epsilon}_{c})}{2K}$
$\displaystyle+H{\epsilon}_{c}+\xi_{1}+\bar{\nu}+\zeta_{opt}.$

######  Theorem 3 (Guarantees for GOPO-PSC).

Let $\hat{\pi}^{ps}$ be the output of Algorithm 1 invoked with CriticCompute
being PSC$({\mathcal{D}},{\mathcal{F}},\pi^{t},\lambda,\gamma,p_{0})$
(Algorithm 4). Under 2.2, for any $\gamma\in[0,\frac{1}{144(e-2)b^{2}}]$, and
${\epsilon},{\epsilon}_{c},\delta,\lambda>0$, and any $\pi\in\Pi^{all}$, we
have

$\displaystyle{\mathbb{E}}\left[\mathrm{SubOpt}_{\pi}(\hat{\pi}^{ps})\right]$
$\displaystyle\lesssim\frac{\gamma
Hb^{2}\cdot\max\\{\tilde{d}_{ps}({\epsilon},T),\ln\frac{\ln
Kb^{2}}{\delta}\\}+\gamma
b^{2}KH\cdot\max\\{{\epsilon},\delta\\}+\gamma\zeta_{msp}}{\lambda}$
$\displaystyle+\frac{\lambda
H\cdot{\mathcal{C}}(\pi;{\epsilon}_{c})}{K\gamma}+H{\epsilon}_{c}+{\epsilon}+\bar{\nu}+\zeta_{opt}.$

Our results provide a family of upper bounds on the sub-optimality of each of
$\\{\hat{\pi}^{vs},\hat{\pi}^{ro},\hat{\pi}^{ps}\\}$, indexed by our choices
of the comparator $\pi$ with the data diversity
${\mathcal{C}}(\pi;{\epsilon}_{c})$, additive (extrapolation) error
${\epsilon}_{c}$, the discretization level ${\epsilon}$ in log-covering
numbers, the “failure” probability $\delta$, and other algorithm-dependent
parameters ($\lambda$ for $\hat{\pi}^{ro}$ and ($\lambda$, $\gamma$) for
$\hat{\pi}^{ps}$). Note that the optimization error $\zeta_{opt}$ captures the
error rate of the actor and can be made arbitrarily small with large iteration
number $T$ whereas $\zeta_{msp}$, $\tilde{\zeta}_{msp}$, $\bar{\nu}$, and
$\xi_{1}$ are simply misspecification errors aggregated over all stages. Also,
note that our bound does not scale with the complexity of the comparator
policy class $\Pi^{all}$.

We next highlight the key characteristics of our main results in comparison
with existing work.

##### (I) Tight characterization of data diversity.

Our bounds in all the above theorems are expressed in terms of
${\mathcal{C}}(\pi;{\epsilon}_{c})$. Several remarks are in order. First,
${\mathcal{C}}(\pi;{\epsilon}_{c})$ is a _non-increasing_ function of
${\epsilon}_{c}$; thus ${\mathcal{C}}(\pi;{\epsilon}_{c})$ is always smaller
or at least equal to ${\mathcal{C}}(\pi;0)$. In fact, it is possible that
${\mathcal{C}}(\pi;0)=\infty$ yet ${\mathcal{C}}(\pi;{\epsilon}_{c})<\infty$
for some ${\epsilon}>0$. For instance, if there exists $g\in{\mathcal{Q}}$
such that $g(x)=0,\forall x\in{\mathrm{supp}}(p)$ and $\\{x:g(x)\neq 0\\}$ has
a positive measure under $q$, then $\chi_{{\mathcal{Q}}}(0;q,p)=\infty$ while
$\chi_{{\mathcal{Q}}}(\sup_{g\in{\mathcal{Q}}}{\mathbb{E}}_{q}[g]^{2};q,p)=0$.
Second, ${\mathcal{C}}(\pi;0)$ is always bounded from above by (often
substantially smaller than) the _single-policy concentrability coefficient_
between the $\pi$-induced and $\mu$-induced state-action distribution (Liu et
al., 2019; Rashidinejad et al., 2021), which been used extensively in recent
offline RL works (Yin and Wang, 2021; Nguyen-Tang et al., 2022a, 2023; Jin et
al., 2022; Zhan et al., 2022; Nguyen-Tang and Arora, 2023; Zhao et al., 2023).
This is essentially because $d^{\pi}$ can cover the region that is not covered
by $d^{\mu}$ but still the integration of functions in
${\mathcal{F}}_{h}-{\mathcal{F}}_{h}$ over two distributions are close to each
other. Third, ${\mathcal{C}}(\pi;0)$ is always upper bounded by the _relative
condition numbers_ used in (Agarwal et al., 2021; Uehara et al., 2022b; Uehara
and Sun, 2022). Our data diversity at ${\epsilon}=0$ is similar to the notion
of distribution mismatch in Duan et al. (2020); Ji et al. (2022), though our
notion is motivated by transfer learning and discovered naturally from our
decoupling argument. Our data diversity measure at ${\epsilon}=0$ is smaller
than the Bellman residual ratio measure used in Xie et al. (2021) (follows
using Jensen’s inequality). Finally, the concurrent work of Di et al. (2023)
proposed a notion of $D^{2}$-divergence to capture the data disparity of a
data point to the offline data. Our data diversity is in general less
restricted as we only need to ensure the diversity between two data
distributions (of the target policy and the behavior policy), not necessarily
between each of their individual data points.

In summary, ${\mathcal{C}}(\pi;{\epsilon}_{c})$, to the best of our knowledge,
provides the tightest characterization of distribution mismatch compared to
the prior data coverage notions. We sketch the relationships of the discussed
notions in Figure 1, where with our data diversity notion, we show that the
scenarios for the offline data in which offline RL is learnable are enlarged
compared to the picture depicted by the prior data coverage notions.

Figure 1. The relations of sample-efficient offline RL classes under different
data coverage measures. Given the same MDP and a target policy (e.g., an
optimal policy of the MDP), each data coverage measure induces a corresponding
set of behavior policies (represented by the rectangle labelled by the data
coverage measure) from which the target policy is offline-learnable.

##### (II) Competing with all comparator policies simultaneously.

Similar to some recent results in offline RL, our offline RL algorithms
compete with all comparator policies that are supported by offline data in
some sense. In particular, the choice of the comparator $\pi$ provides the
flexibility to _automatically_ compete with the best policy within a certain
diversity level of our choice. For instance, if we want to limit the level
${\mathcal{C}}(\pi;{\epsilon}_{c})\leq C$ for some arbitrary $C>0$, our bound
automatically competes with
$\pi=\operatorname*{arg\,max}_{\pi\in\Pi^{all}}\\{V_{1}^{\pi}(s):{\mathcal{C}}(\pi;{\epsilon}_{c})\leq
C\\}$. This is immensely meaningful since the offline data might not support
extrapolation to an optimal policy in practice.

##### (III) State-of-the-art bounds for _standard_ assumptions.

We compare our bounds with other recent guarantees of similar
assumptions.666Recent primal-dual methods achieve favorable guarantees for
offline RL. However, these guarantees are not directly comparable to the
guarantees of our value-based methods due to a different set of assumptions.
Nonetheless, we make a detailed discussion in Section 4.3. To ease comparison,
we assume for simplicity, that there is no misspecification, i.e.,
$\nu_{h}=\xi_{h}=0,\forall h\in[H]$, and $T\geq
K\ln{\mathrm{Vol}}({\mathcal{A}})$, and we minimize the bounds in Theorem 2
and Theorem 3 with respect to $\lambda$. The three theorems can then be
simplified into a unified result presented in 1.

######  Proposition 1 (A unified guarantee for VS, RO and PS).

Under 2.1-2.2 with no misspecification, i.e., $\nu_{h}=\xi_{h}=0,\forall
h\in[H]$,
$\forall\hat{\pi}\in\\{\hat{\pi}^{vs},\hat{\pi}^{ro},\hat{\pi}^{ps}\\}$,
${\mathbb{E}}[\mathrm{SubOpt}_{\pi}(\hat{\pi})]=\tilde{{\mathcal{O}}}(Hb\sqrt{\tilde{d}(1/K,T)\cdot{\mathcal{C}}(\pi;1/\sqrt{K})/K}+\xi_{opt})$,
where $\tilde{d}(1/K,T)=\tilde{d}_{opt}(1/K,T)$ if
$\hat{\pi}\in\\{\hat{\pi}^{vs},\hat{\pi}^{ro}\\}$ and
$\tilde{d}(1/K,T)=\tilde{d}_{ps}(1/K,T)$ if $\hat{\pi}=\hat{\pi}^{ps}$. In
addition,

  * •

If ${\mathcal{F}}_{h}$ and $\Pi^{soft}_{h}(T)$ have finite elements for all
$h\in[H]$, we have
$\tilde{d}(1/K,T)={\mathcal{O}}(\max_{h\in[H]}\max\\{\ln|{\mathcal{F}}_{h}|,\ln|\Pi_{h}^{soft}(T)|\\})$;

  * •

If
${\mathcal{F}}_{h}=\\{(s,a)\mapsto\langle\phi_{h}(s,a),w\rangle:\|w\|_{2}\leq
b\\}$ is a linear model, where
$\phi_{h}:{\mathcal{S}}\times{\mathcal{A}}\rightarrow{\mathbb{R}}^{d}$ is a
known feature map and w.l.o.g. $\max_{h}\|\phi_{h}\|_{\infty}\leq 1$, we have
$\tilde{d}(1/K,T)={\mathcal{O}}(d\log(1+KTb)),\forall T$.

1 essentially asserts that VS-based, RO-based, and PS-based algorithms obtain
comparable guarantees for offline RL in the realizable case. We now compare
our results to related work in various instantiating of function classes.

##### Compared with Xie et al. (2021) when the function class is finite.

In this case, the analysis of the VS-based algorithms and RO-based algorithms
of Xie et al. (2021) give the bounds that in our setting can be
translated777Xie et al. (2021) consider discounted MDP and a _restricted_
policy class for the comparator class. into:
$Hb\sqrt{\max_{h}\ln(|{\mathcal{F}}_{h}||\Pi_{h}^{all}|)\cdot C_{2}(\pi)/K}$
and
$Hb\sqrt{C_{2}(\pi)}\sqrt[3]{\max_{h}\ln(|{\mathcal{F}}_{h}||\Pi_{h}^{soft}(T)|)/K}+Hb/\sqrt{T}$,
respectively, where
$C_{2}(\pi):=\max_{h\in[H],\tilde{\pi}\in\Pi^{all},f\in{\mathcal{F}}}\frac{\|f_{h}-{\mathbb{T}}^{\tilde{\pi}}_{h}f_{h+1}\|^{2}_{2,\pi}}{\|f_{h}-{\mathbb{T}}^{\tilde{\pi}}_{h}f_{h+1}\|^{2}_{2,\mu}}$.
Instead, our bounds for both the VS-based and RO-based algorithms are
$Hb\sqrt{\max_{h}\ln(|{\mathcal{F}}_{h}||\Pi_{h}^{soft}(T)|)\cdot{\mathcal{C}}(\pi;1/\sqrt{K})/K}+Hb/\sqrt{T}$.
We improve upon the results of Xie et al. (2021) on several fronts. First, our
diversity measures ${\mathcal{C}}(\pi;1/K)$ is always smaller than their
measure $C_{2}(\pi)$, since
${\mathcal{C}}(\pi;1/\sqrt{K})\leq{\mathcal{C}}(\pi;0)\leq C_{2}(\pi)$.
Second, for the VS-based algorithm, $\Pi^{soft}(T)\subset\Pi^{all},\forall T$,
our bound is always tighter. In fact, $|\Pi^{all}|$ is arbitrarily large that
bounds depending on this quantity is vacuous. Third, for the RO-based
algorithm, the rates in terms of $K$ in the bound of Xie et al. (2021) are
slower than that in our bound. Specifically, if
$\Pi_{h}^{soft}(T)=\tilde{\mathcal{O}}_{T}(1)$, then these rates are
$K^{-1/3}$ vs $K^{-1/2}$ (with an optimal choice of $T=K$ for both bounds). If
we consider the worst case that
$\Pi_{h}^{soft}(T)=\mathcal{O}(T\log|{\mathcal{F}}_{h}|)$, then these rates
are $K^{-1/5}$ vs $K^{-1/4}$ (with an optimal choice of $T=K^{2/5}$ and
$T=\sqrt{K}$ in the respective bounds). Finally, our results hold under the
general adaptively collected data rather than their independent episode
setting. We summarize the bounds in the finite function class cases in Table
1, and give comparisons for the linear model cases in Table 2.

##### Compared with LCB-based algorithms.

When ${\mathcal{F}}_{h}$ is a $d$-dimensional linear model with feature maps
$\\{\phi_{h}\\}_{h\in[H]}$, our bounds reduce into $Hb\sqrt{d\cdot
K^{-1}\cdot{\mathcal{C}}(\pi;1/\sqrt{K})}$ (1), which matches the order of
(and potentially tighter than) the bound in Zanette et al. (2021), since
${\mathcal{C}}(\pi;1/\sqrt{K})$ is always smaller (or at least equal to) than
the relative condition number
$\max_{h}\sup_{x\in{\mathbb{R}}^{d}}\frac{x^{T}{\mathbb{E}}_{\pi}[\phi_{h}(s_{h},a_{h})\phi_{h}(s_{h},a_{h})^{T}]x}{x^{T}{\mathbb{E}}_{\mu}[\phi_{h}(s_{h},a_{h})\phi_{h}(s_{h},a_{h})^{T}]x}$.
Compared with the bound of LCB-based algorithms in Jin et al. (2021b), we
improve a factor $\sqrt{d}$ and holds under the more general 2.2 which
includes low-rank MDPs. In a more refined analysis (Xiong et al., 2023), the
LCB-based algorithm obtains the same dependence on $d$ for low-rank MDPs as
our guarantees. However, this improvement relies on a uniform coverage
assumption, i.e.,
$\min_{h\in[H]}\lambda_{\min}\left({\mathbb{E}}_{(s_{h},a_{h})\sim
d^{\mu}_{h}}\left[\phi_{h}(s_{h},a_{h})\phi_{h}(s_{h},a_{h})^{T}\right]\right)>0$,
which we do not require. Di et al. (2023) generalize the results of Xiong et
al. (2023) from linear MDPs to MDPs with general function approximation.
However, they still rely on a uniform coverage assumption. Finally note that,
for VS-based and RO-based algorithms, we provide high-probability bounds for a
smoothing version of $\hat{\pi}$ over the randomization of the algorithms, not
for $\hat{\pi}$ itself.

##### Compared with model-based PS

Uehara and Sun (2022) consider model-based PS for offline RL and derive the
_Bayesian_ sub-optimality bound of
$H^{2}\sqrt{C^{\text{Bayes}}\cdot\ln|{\mathcal{M}}|/K}$ where
$C^{\text{Bayes}}$ is the Bayesian version of a relative condition number and
${\mathcal{M}}$ is a finite model class. Two key distinctions are that our
method in Algorithm 4 is model-free, and our achieved bound is in the
frequentist (i.e., worst-case) nature, which is a stronger result than the
Bayesian bound of the same order.

###  4.3. Extended discussion

##### Comparison with primal-dual methods for offline RL

As opposed to the value-based methods we considered in our paper, an important
alternative approach to offline RL is the primal-dual methods (Zhan et al.,
2022; Chen and Jiang, 2022; Rashidinejad et al., 2023; Gabbianelli et al.,
2023; Ozdaglar et al., 2023). However, the guarantees of primal-dual methods
use a different set of assumptions than the value-based methods we consider
(the former assumes realizability for the ratio between the state-action
occupancy density of the target policy and the state-action occupancy density
of the behavior policy, except for Gabbianelli et al. (2023) where this
realizability assumption is implicitly encoded under a stronger assumption of
linear MDP). This makes the results presented in our paper and the results in
the primal-dual methods not directly comparable.

Since the work of Gabbianelli et al. (2023) considers linear MDPs, it is more
comparable (than the other primal-dual methods we mentioned) to the
instantiating of our results to the linear function class. Gabbianelli et al.
(2023) consider primal-dual methods for offline RL in both infinite-horizon
discounted MDP and average-reward MDP. Our analysis framework for the
regularized optimization method in the episodic MDP should work for the
infinite-horizon discounted MDP as well, where the regularized optimization
achieves the optimal sample complexity of $\mathcal{O}(\epsilon^{-2})$ while
the sample complexity in Gabbianelli et al. (2023) in this setting is
$\mathcal{O}(\epsilon^{-4})$. However, Gabbianelli et al. (2023) offers a
better computational complexity ($\mathcal{O}(K)$ vs $\mathcal{O}(K^{7/5})$)
and also works in the average-reward MDP setting which is beyond the episodic
MDP setting considered in our work; though our bounds hold for general
function approximation that is beyond the strong assumption of linear MDPs.

The concurrent work of Zhu et al. (2023) combined the actor-critic framework
with marginalized importance sampling (MIS) for an RO-based algorithm, which
also improves the sub-optimal rate of order $1/K^{1/3}$ by Xie et al. (2021);
Cheng et al. (2022) to the optimal rate of order $1/\sqrt{K}$. Instead, we
obtain the optimal rate of order $1/\sqrt{K}$ with a refined analysis for a
standard RO-based algorithm. That is, unlike Zhu et al. (2023), we do not use
MIS; consequently, we do not require the realizability assumption for the
ratio between the state-action occupancy density of the target policy and that
of the behavior policy.

##### Linear function classes

We consider the linear model cases, where there are known feature maps
$\phi_{h}:{\mathcal{X}}\times{\mathcal{A}}\rightarrow{\mathbb{R}}^{d}$ and
w.l.o.g. $\max_{h\in[H]}\|\phi(\cdot,\cdot)\|_{\infty}\leq 1$, such that
${\mathcal{F}}_{h}=\\{\phi_{h}(\cdot,\cdot)^{T}w:w\in{\mathbb{R}}^{d},\|w\|_{2}^{2}\leq
b\\}$. Recall that, in this case, e.g., it follows from (Zanette et al., 2021,
Lemma 6), that we have

$\displaystyle\log N({\epsilon};{\mathcal{F}}_{h},\|\cdot\|_{\infty})$
$\displaystyle\leq d\log(1+\frac{2}{{\epsilon}}),$ $\displaystyle\log
N({\epsilon};\Pi_{h}^{soft}(T),\|\cdot\|_{\infty})$ $\displaystyle\leq
d\log(1+\frac{16bT}{{\epsilon}}).$

Thus, our bounds from 1 can simplified as

$\displaystyle\tilde{{\mathcal{O}}}(Hb\sqrt{d\log(1+16bKT)\cdot{\mathcal{C}}(\pi;1/\sqrt{K})/K}+Hb\sqrt{T^{-1}\ln{\mathrm{Vol}}({\mathcal{A}})})$
$\displaystyle=\tilde{{\mathcal{O}}}\left(Hb\sqrt{\frac{\max\\{d{\mathcal{C}}(\pi;1/\sqrt{K}),\ln{\mathrm{Vol}}({\mathcal{A}})\\}}{K}}\right)$

where we choose $T=K$. To simplify the comparison, we assume that
$d{\mathcal{C}}(\pi;1/\sqrt{K})\geq\ln{\mathrm{Vol}}({\mathcal{A}})$. Let us
now compute various notions of data coverage in this linear model case. We
first need to define the following quantities (various forms of covariance
matrices).

$\displaystyle\Sigma_{h}$ $\displaystyle:=\lambda
I+\sum_{k=1}^{K}\phi_{h}(s^{k}_{h},a^{k}_{h})\phi_{h}(s^{k}_{h},a^{k}_{h})^{T},$
$\displaystyle\Lambda_{h}$ $\displaystyle:=\lambda
I+\sum_{k=1}^{K}\phi_{h}(s^{k}_{h},a^{k}_{h})\phi_{h}(s^{k}_{h},a^{k}_{h})^{T}/[{\mathbb{V}}_{h}V_{h+1}^{\pi}](s_{h}^{k},a_{h}^{k}),$
$\displaystyle\bar{\phi}_{h}^{\pi}$
$\displaystyle:={\mathbb{E}}_{\pi}[\phi_{h}(s_{h},a_{h})],$
$\displaystyle\bar{\Sigma}_{h}$
$\displaystyle:={\mathbb{E}}_{\mu}\left[\phi(s_{h},a_{h})\phi(s_{h},a_{h})^{T}\right].$

We define the following distribution mismatch quantities, which were used in
the literature.

$\displaystyle C_{pevi}(\pi)$
$\displaystyle:=\max_{h\in[H]}\left({\mathbb{E}}_{\pi}\left[\|\phi_{h}(s_{h},a_{h})\|_{\Sigma_{h}^{-1}}\right]\right)^{2},$
$\displaystyle C_{pevi-adv}(\pi)$
$\displaystyle:=\max_{h\in[H]}\left({\mathbb{E}}_{\pi}\left[\|\phi_{h}(s_{h},a_{h})\|_{\Lambda_{h}^{-1}}\right]\right)^{2},$
$\displaystyle C_{pacle}(\pi)$
$\displaystyle:=\max_{h\in[H]}\|\bar{\phi}_{h}^{\pi}\|^{2}_{\Sigma_{h}^{-1}},$
$\displaystyle C_{bcp}(\pi)$
$\displaystyle:=\max_{h\in[H]}\left({\mathbb{E}}_{\pi}\left[\|\phi_{h}(s_{h},a_{h})\|_{\bar{\Sigma}_{h}}\right]\right)^{2}.$

The sub-optimality bounds of various methods are summarized in Table 2. For
comparing our data diversity measure with different notions of distribution
mismatch, we have

$\displaystyle C_{pevi}(\pi)\geq
C_{pacle}(\pi)\approx{\mathcal{C}}(\pi;0)/K\leq C_{bcp}(\pi)/K.$

where the “$\approx$” denotes that the involved terms scale in the same order
and can be implied by Fredman’s matrix inequality (see (Duan et al., 2020,
Lemma B.5)) (under additional conditions). Note that
${\mathcal{C}}(\pi;1/\sqrt{K})\leq{\mathcal{C}}(\pi;0)$, thus our data
diversity is the tightest quantity among all that are considered.

Note that the data coverage measure in Xiong et al. (2023), roughly speaking,
can be bounded as follows:

$\displaystyle C_{pevi-adv}(\pi)\leq b^{2}C_{pevi}(\pi),$

where we use the inequality
$[{\mathbb{V}}_{h}V_{h+1}^{\pi}](s_{h}^{k},a_{h}^{k})\leq b^{2}$. Thus the
bound of Xiong et al. (2023) in general has a tighter dependence on $b$ (which
implicitly depends on $H$) than all the bounds of all other works considered
in Table 2, due to that Xiong et al. (2023) incorporated the variance
information into the estimation via the variance-weighted value iteration
algorithm. However, obtaining this improved bound in Xiong et al. (2023)
relies on a uniform coverage assumption which we do not require.

Algorithm | Sub-optimality bound
---|---
PEVI (Jin et al., 2021b) | $Hb\sqrt{C_{pevi}(\pi)}\cdot d$
PEVI-ADV+ (Xiong et al., 2023) | $H\sqrt{C_{pevi-avi}(\pi)\cdot d}$
PACLE (Zanette et al., 2021) | $Hb\sqrt{C_{pacle}(\pi)\cdot d}$
VC (Xie et al., 2021, Section 3) | $Hb\sqrt{C_{bcp}(\pi)\cdot d/K}$
RO (Xie et al., 2021, Section 4) | $Hb\sqrt{C_{bcp}(\pi)}\sqrt[3]{d/K}$
Ours (VS, RO, PS) | $Hb\sqrt{{\mathcal{C}}(\pi;1/\sqrt{K})\cdot d/K}$

Table 2. Sub-optimality bounds when the function class ${\mathcal{F}}_{h}$ is
linear in
$\phi_{h}:{\mathcal{S}}\times{\mathcal{A}}\rightarrow{\mathbb{R}}^{d}$.

##  5\. Conclusion

We contributed to the understanding of sample-efficient offline RL in the
context of (value) function approximation. We proposed a notion of data
diversity that generalizes the previous data coverage measures and importantly
expands the class of sample-efficient offline RL. We studied three different
algorithms: VS, RO, and PS, where the PS-based algorithm is our novel
proposal. We showed that VS, RO, and PS all have same-order guarantees under
standard assumptions.

## Acknowledgements

This research was supported, in part, by DARPA GARD award HR00112020004, NSF
CAREER award IIS-1943251, funding from the Institute for Assured Autonomy
(IAA) at JHU, and the Spring’22 workshop on “Learning and Games” at the Simons
Institute for the Theory of Computing.

## References

  * Agarwal and Zhang [2022] Alekh Agarwal and Tong Zhang.  Non-linear reinforcement learning in large action spaces: Structural conditions and sample-efficiency of posterior sampling.  In _Conference on Learning Theory_ , pages 2776–2814. PMLR, 2022.
  * Agarwal et al. [2021] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan.  On the theory of policy gradient methods: Optimality, approximation, and distribution shift.  _J. Mach. Learn. Res._ , 22(98):1–76, 2021.
  * Antos et al. [2006] András Antos, Csaba Szepesvári, and Rémi Munos.  Learning near-optimal policies with bellman-residual minimization based fitted policy iteration and a single sample path.  In Gábor Lugosi and Hans Ulrich Simon, editors, _Learning Theory, 19th Annual Conference on Learning Theory, COLT 2006, Pittsburgh, PA, USA, June 22-25, 2006, Proceedings_ , volume 4005 of _Lecture Notes in Computer Science_ , pages 574–588. Springer, 2006.
  * Arora et al. [2012] Sanjeev Arora, Elad Hazan, and Satyen Kale.  The multiplicative weights update method: a meta-algorithm and applications.  _Theory of Computing_ , 8(6):121–164, 2012.  doi: 10.4086/toc.2012.v008a006.
  * Bartlett et al. [2005] Peter L Bartlett, Olivier Bousquet, and Shahar Mendelson.  Local rademacher complexities.  _The Annals of Statistics_ , 33(4):1497–1537, 2005.
  * Chen and Jiang [2019] Jinglin Chen and Nan Jiang.  Information-theoretic considerations in batch reinforcement learning.  In _International Conference on Machine Learning_ , pages 1042–1051. PMLR, 2019.
  * Chen and Jiang [2022] Jinglin Chen and Nan Jiang.  Offline reinforcement learning under value and density-ratio realizability: the power of gaps.  In _Uncertainty in Artificial Intelligence_ , pages 378–388. PMLR, 2022.
  * Cheng et al. [2022] Ching-An Cheng, Tengyang Xie, Nan Jiang, and Alekh Agarwal.  Adversarially trained actor critic for offline reinforcement learning.  In _International Conference on Machine Learning_ , pages 3852–3878. PMLR, 2022.
  * Dann et al. [2021] Christoph Dann, Mehryar Mohri, Tong Zhang, and Julian Zimmert.  A provably efficient model-free posterior sampling method for episodic reinforcement learning.  In _Advances in Neural Information Processing Systems_ , 2021.
  * Di et al. [2023] Qiwei Di, Heyang Zhao, Jiafan He, and Quanquan Gu.  Pessimistic nonlinear least-squares value iteration for offline reinforcement learning.  _arXiv preprint arXiv:2310.01380_ , 2023.
  * Duan et al. [2020] Yaqi Duan, Zeyu Jia, and Mengdi Wang.  Minimax-optimal off-policy evaluation with linear function approximation.  In _International Conference on Machine Learning_ , pages 2701–2709. PMLR, 2020.
  * Ernst et al. [2005] Damien Ernst, Pierre Geurts, and Louis Wehenkel.  Tree-based batch mode reinforcement learning.  _Journal of Machine Learning Research_ , 6, 2005.
  * Foster et al. [2021] Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin.  The statistical complexity of interactive decision making.  _arXiv preprint arXiv:2112.13487_ , 2021.
  * Freedman [1975] David A. Freedman.  On tail probabilities for martingales.  _The Annals of Probability_ , 3(1):100–118, 1975.  ISSN 00911798.
  * Gabbianelli et al. [2023] Germano Gabbianelli, Gergely Neu, Nneka Okolo, and Matteo Papini.  Offline primal-dual reinforcement learning for linear mdps.  _arXiv preprint arXiv:2305.12944_ , 2023.
  * Ji et al. [2022] Xiang Ji, Minshuo Chen, Mengdi Wang, and Tuo Zhao.  Sample complexity of nonparametric off-policy evaluation on low-dimensional manifolds using deep networks.  _arXiv preprint arXiv:2206.02887_ , 2022.
  * Jiang et al. [2017] Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire.  Contextual decision processes with low bellman rank are pac-learnable.  In _International Conference on Machine Learning_ , pages 1704–1713. PMLR, 2017.
  * 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.
  * Jin et al. [2021a] Chi Jin, Qinghua Liu, and Sobhan Miryoosefi.  Bellman eluder dimension: New rich classes of RL problems, and sample-efficient algorithms.  In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, _Advances in Neural Information Processing Systems_ , 2021a.
  * Jin et al. [2021b] Ying Jin, Zhuoran Yang, and Zhaoran Wang.  Is pessimism provably efficient for offline rl?  In _International Conference on Machine Learning_ , pages 5084–5096. PMLR, 2021b.
  * Jin et al. [2022] Ying Jin, Zhimei Ren, Zhuoran Yang, and Zhaoran Wang.  Policy learning" without”overlap: Pessimism and generalized empirical bernstein’s inequality.  _arXiv preprint arXiv:2212.09900_ , 2022.
  * Lange et al. [2012] Sascha Lange, Thomas Gabel, and Martin Riedmiller.  Batch reinforcement learning.  In _Reinforcement learning_ , pages 45–73. Springer, 2012.
  * Levine et al. [2020] Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu.  Offline reinforcement learning: Tutorial, review, and perspectives on open problems.  _arXiv preprint arXiv:2005.01643_ , 2020.
  * Liu et al. [2019] Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill.  Off-policy policy gradient with stationary distribution correction.  In Amir Globerson and Ricardo Silva, editors, _Proceedings of the Thirty-Fifth Conference on Uncertainty in Artificial Intelligence, UAI 2019, Tel Aviv, Israel, July 22-25, 2019_ , volume 115 of _Proceedings of Machine Learning Research_ , pages 1180–1190. AUAI Press, 2019.
  * Massart [2000] Pascal Massart.  Some applications of concentration inequalities to statistics.  _Annales de la Faculté des Sciences de Toulouse_ , 9:245–303, 2000.
  * Munos and Szepesvári [2008] Rémi Munos and Csaba Szepesvári.  Finite-time bounds for fitted value iteration.  _J. Mach. Learn. Res._ , 9:815–857, 2008.
  * Nguyen-Tang and Arora [2023] Thanh Nguyen-Tang and Raman Arora.  VIPer: Provably efficient algorithm for offline RL with neural function approximation.  In _The Eleventh International Conference on Learning Representations_ , 2023.
  * Nguyen-Tang et al. [2022a] Thanh Nguyen-Tang, Sunil Gupta, A. Tuan Nguyen, and Svetha Venkatesh.  Offline neural contextual bandits: Pessimism, optimization and generalization.  In _International Conference on Learning Representations_ , 2022a.
  * Nguyen-Tang et al. [2022b] Thanh Nguyen-Tang, Sunil Gupta, Hung Tran-The, and Svetha Venkatesh.  On sample complexity of offline reinforcement learning with deep reLU networks in besov spaces.  _Transactions of Machine Learning Research_ , 2022b.
  * Nguyen-Tang et al. [2023] Thanh Nguyen-Tang, Ming Yin, Sunil Gupta, Svetha Venkatesh, and Raman Arora.  On instance-dependent bounds for offline reinforcement learning with linear function approximation.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 37, pages 9310–9318, 2023.
  * Osband et al. [2016] Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy.  Deep exploration via bootstrapped dqn.  _Advances in neural information processing systems_ , 29, 2016.
  * Ozdaglar et al. [2023] Asuman E Ozdaglar, Sarath Pattathil, Jiawei Zhang, and Kaiqing Zhang.  Revisiting the linear-programming framework for offline rl with general function approximation.  In _International Conference on Machine Learning_ , pages 26769–26791. PMLR, 2023.
  * Rashidinejad et al. [2021] Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell.  Bridging offline reinforcement learning and imitation learning: A tale of pessimism.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Rashidinejad et al. [2023] Paria Rashidinejad, Hanlin Zhu, Kunhe Yang, Stuart Russell, and Jiantao Jiao.  Optimal conservative offline RL with general function approximation via augmented lagrangian.  In _The Eleventh International Conference on Learning Representations_ , 2023.
  * 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.
  * Thompson [1933] William R. Thompson.  On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.  _Biometrika_ , 25:285–294, 1933.
  * Tripuraneni et al. [2020] Nilesh Tripuraneni, Michael Jordan, and Chi Jin.  On the theory of transfer learning: The importance of task diversity.  _Advances in neural information processing systems_ , 33:7852–7862, 2020.
  * Uehara and Sun [2022] Masatoshi Uehara and Wen Sun.  Pessimistic model-based offline reinforcement learning under partial coverage.  In _International Conference on Learning Representations_ , 2022.
  * Uehara et al. [2022a] Masatoshi Uehara, Chengchun Shi, and Nathan Kallus.  A review of off-policy evaluation in reinforcement learning.  _arXiv preprint arXiv:2212.06355_ , 2022a.
  * Uehara et al. [2022b] Masatoshi Uehara, Xuezhou Zhang, and Wen Sun.  Representation learning for online and offline RL in low-rank MDPs.  In _International Conference on Learning Representations_ , 2022b.
  * Wang et al. [2021] Ruosong Wang, Dean Foster, and Sham M. Kakade.  What are the statistical limits of offline RL with linear function approximation?  In _International Conference on Learning Representations_ , 2021.
  * Watkins et al. [2023] Austin Watkins, Enayat Ullah, Thanh Nguyen-Tang, and Raman Arora.  Optimistic rates for multi-task representation learning.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.
  * Welling and Teh [2011] Max Welling and Yee W Teh.  Bayesian learning via stochastic gradient langevin dynamics.  In _Proceedings of the 28th international conference on machine learning (ICML-11)_ , pages 681–688, 2011.
  * Xie et al. [2021] Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal.  Bellman-consistent pessimism for offline reinforcement learning.  _Advances in neural information processing systems_ , 34, 2021.
  * Xiong et al. [2022] Wei Xiong, Han Zhong, Chengshuai Shi, Cong Shen, and Tong Zhang.  A self-play posterior sampling algorithm for zero-sum markov games.  In _International Conference on Machine Learning_ , pages 24496–24523. PMLR, 2022.
  * Xiong et al. [2023] Wei Xiong, Han Zhong, Chengshuai Shi, Cong Shen, Liwei Wang, and Tong Zhang.  Nearly minimax optimal offline reinforcement learning with linear function approximation: Single-agent MDP and markov game.  In _The Eleventh International Conference on Learning Representations_ , 2023.
  * Yang and Wang [2019] Lin Yang and Mengdi Wang.  Sample-optimal parametric q-learning using linearly additive features.  In _International Conference on Machine Learning_ , pages 6995–7004. PMLR, 2019.
  * Yin and Wang [2021] Ming Yin and Yu-Xiang Wang.  Towards instance-optimal offline reinforcement learning with pessimism.  _Advances in neural information processing systems_ , 34, 2021.
  * Zanette et al. [2020] Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill.  Learning near optimal policies with low inherent bellman error.  In _International Conference on Machine Learning_ , pages 10978–10989. PMLR, 2020.
  * Zanette et al. [2021] Andrea Zanette, Martin J Wainwright, and Emma Brunskill.  Provable benefits of actor-critic methods for offline reinforcement learning.  _Advances in neural information processing systems_ , 34:13626–13640, 2021.
  * Zhan et al. [2023] Ruohan Zhan, Zhimei Ren, Susan Athey, and Zhengyuan Zhou.  Policy learning with adaptively collected data.  _Management Science_ , 2023.
  * Zhan et al. [2022] Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason Lee.  Offline reinforcement learning with realizability and single-policy concentrability.  In Po-Ling Loh and Maxim Raginsky, editors, _Proceedings of Thirty Fifth Conference on Learning Theory_ , volume 178 of _Proceedings of Machine Learning Research_ , pages 2730–2775. PMLR, 02–05 Jul 2022.
  * Zhang [2022] Tong Zhang.  Feel-good thompson sampling for contextual bandits and reinforcement learning.  _SIAM Journal on Mathematics of Data Science_ , 4(2):834–857, 2022.
  * Zhang [2023] Tong Zhang.  _Mathematical Analysis of Machine Learning Algorithms_.  Cambridge University Press, 2023.
  * Zhao et al. [2023] Yulai Zhao, Zhuoran Yang, Zhaoran Wang, and Jason D Lee.  Local optimization achieves global optimality in multi-agent reinforcement learning.  _arXiv preprint arXiv:2305.04819_ , 2023.
  * Zhong et al. [2022] Han Zhong, Wei Xiong, Sirui Zheng, Liwei Wang, Zhaoran Wang, Zhuoran Yang, and Tong Zhang.  A posterior sampling framework for interactive decision making.  _arXiv preprint arXiv:2211.01962_ , 2022.
  * Zhu et al. [2023] Hanlin Zhu, Paria Rashidinejad, and Jiantao Jiao.  Importance weighted actor-critic for optimal conservative offline reinforcement learning.  _arXiv preprint arXiv:2301.12714_ , 2023.

###### Contents

  1. 1 Introduction
  2. 2 Background and problem formulation
    1. 2.1 Episodic time-inhomogenous Markov decision process
    2. 2.2 Offline data generation
    3. 2.3 Policy and function classes
    4. 2.4 Effective sizes of policy and function classes
  3. 3 Algorithms
  4. 4 Main results
    1. 4.1 Data diversity
    2. 4.2 Offline learning guarantees
    3. 4.3 Extended discussion
  5. 5 Conclusion
  6. A Preparation
    1. A.1 Variance condition and Bernstein’s inequality
    2. A.2 Functional projections for misspecification
    3. A.3 Induced MDPs
    4. A.4 Error decomposition
    5. A.5 Decoupling lemma
    6. A.6 Regret of the multiplicative weights algorithm for the actors
  7. B Proof of
    1. B.1 Proof of
    2. B.2 Proof of Lemma B.1
    3. B.3 Proof of Lemma B.2
  8. C Proof of
  9. D Proof of
    1. D.1 Generalized form of posterior and
    2. D.2 Proof of
    3. D.3 Proof of
      1. D.3.1 Lower-bounding log-partition function.
      2. D.3.2 Upper-bounding log-partition function
      3. D.3.3 Proof of
  10. E Proof of 1
  11. F Support Lemmas

##  Appendix A Preparation

We now get into more involved parts where we present the proof process and the
technical results for obtaining Theorem 1, Theorem 2, and Theorem 3. In order
to prove our main results in Section 4, we shall need some old tools and
develop some new useful tools. For convenience, we start out with both old and
new notations of quantities summarized in Table 3 that we are going to use
frequently in our proofs.

Name | Notation | Expression
---|---|---
transition sample | $z^{k}_{h}$ | $(s^{k}_{h},a^{k}_{h},r^{k}_{h},a^{k}_{h+1})$
transition sample | $z_{h}$ | $(s_{h},a_{h},r_{h},s_{h+1})$
Bellman error | ${\mathcal{E}}_{h}^{\tilde{\pi}}(f_{h},f_{h+1})(s_{h},a_{h})$ | $({\mathbb{T}}_{h}^{\tilde{\pi}}f_{h+1}-f_{h})(s_{h},a_{h})$
TD loss function | $l_{\tilde{\pi}}(f_{h},f_{h+1};z_{h})$ | $(f_{h}(s_{h},a_{h})-r_{h}-f_{h+1}(s_{h+1},\tilde{\pi}))^{2}$
empirical squared Bellman error (SBE) | $\hat{L}_{\tilde{\pi}}(f_{h},f_{h+1})$ | $\sum_{k=1}^{K}l_{\tilde{\pi}}(f_{h},f_{h+1};z^{k}_{h})$
empirical bias-adjusted SBE | ${\mathcal{L}}_{{\tilde{\pi}}}(f)$ | $\sum_{h=1}^{H}\hat{L}_{{\tilde{\pi}}}(f_{h},f_{h+1})-\inf_{g\in{\mathcal{F}}}\sum_{h=1}^{H}\hat{L}_{{\tilde{\pi}}}(g_{h},f_{h+1})$
excess TD loss | $\Delta L_{\tilde{\pi}}(f_{h},f_{h+1};z_{h})$ | $l_{\tilde{\pi}}(f_{h},f_{h+1};z_{h})-l_{\tilde{\pi}}({\mathbb{T}}_{h}^{\tilde{\pi}}f_{h+1},f_{h+1};z_{h})$
– | ${\mathbb{E}}_{\mu}[\cdot]$ | $\frac{1}{K}\sum_{k=1}^{K}{\mathbb{E}}_{\mu^{k}}[\cdot]$
– | ${\mathbb{E}}_{k}[\cdot](:={\mathbb{E}}_{\mu^{k}}[\cdot])$ | ${\mathbb{E}}\left[\cdot\bigg{|}\\{z^{i}_{h}\\}_{h\in[H]}^{i\in[k-1]}\right]$

Table 3. A summary of notations and quantities of interest.

The quantity $l_{\tilde{\pi}}(f_{h},f_{h+1};z_{h})$ can be viewed as _a
temporal difference (TD) loss function_ defined on data point $z_{h}$
conditioned on each $f_{h+1}$ and $\tilde{\pi}$. The quantity
${\mathbb{T}}_{h}^{\tilde{\pi}}f_{h+1}$ can be viewed as _the Bellman
regression function_ , where, conditioned on each $f_{h+1}$ and $\tilde{\pi}$,
for any $(s_{h},a_{h})$, we have

$\displaystyle{\mathbb{T}}_{h}^{\tilde{\pi}}f_{h+1}(s_{h},a_{h})={\mathbb{E}}_{r_{h},s_{h+1}|s_{h},a_{h}}[r_{h}+f_{h+1}(s_{h+1},\tilde{\pi})]=\operatorname*{arg\,inf}_{g}{\mathbb{E}}_{r_{h},s_{h+1}|s_{h},a_{h}}l_{\tilde{\pi}}(g,f_{h+1};z_{h}).$

Thus, the quantity $\Delta L_{\tilde{\pi}}(f_{h},f_{h+1};z_{h})$ can be
referred to as the _excess TD loss_ , incurred by the predictor $f_{h}$,
relative to the TD regression function
${\mathbb{T}}_{h}^{\tilde{\pi}}f_{h+1}$, on data $z_{h}$ and conditioned on
$f_{h+1}$ and $\tilde{\pi}$.

###  A.1. Variance condition and Bernstein’s inequality

We also define the $\sigma$-algebra
${\mathcal{A}}^{k}_{h}:=\sigma({\mathcal{D}}_{k-1}\cup\\{(s^{k}_{h^{\prime}},a^{k}_{h^{\prime}},r^{k}_{h^{\prime}})\\}_{h^{\prime}\in[h-1]}\cup(s^{k}_{h},a^{k}_{h}))$
and denote
${\mathbb{E}}_{k,h}[\cdot]:={\mathbb{E}}[\cdot|{\mathcal{A}}^{k}_{h}]$. The
following lemma establishes the variance condition on the excess TD loss, a TD
analogous to the variance condition that is widely used in the empirical
process theory [Massart, 2000].

######  Lemma A.1.

For any ${\mathcal{A}}^{k}_{h}$-measurable policy $\pi$, we have

$\displaystyle{\mathbb{E}}_{k,h}[\Delta L_{\pi}(f_{h},f_{h+1};z^{k}_{h})]$
$\displaystyle={\mathcal{E}}^{\pi}_{h}(f_{h},f_{h+1})(s^{k}_{h},a^{k}_{h})^{2},$
$\displaystyle{\mathbb{E}}_{k,h}[\Delta L_{\pi}(f_{h},f_{h+1};z^{k}_{h})^{2}]$
$\displaystyle\leq
36b^{2}{\mathcal{E}}^{\pi}_{h}(f_{h},f_{h+1})(s^{k}_{h},a^{k}_{h})^{2}.$

###### Proof of Lemma A.1.

The result directly exploits the boundedness of the TD loss function and the
squared loss is Lipschitz. In concrete, it is a direct application of Lemma
F.1. ∎

The following lemma establishes the martingale extension of Bernstein’s
inequality, typically called Freedman’s inequality [Freedman, 1975]. In this
lemma, we prove a slightly modified version of the original Freedman’s
inequality for our own convenience. The proof for this lemma is elementary
which we also show here.

######  Lemma A.2 (Freedman’s inequality).

Let $X_{1},\ldots,X_{T}$ be _any_ sequence of real-valued random variables.
Denote ${\mathbb{E}}_{t}[\cdot]={\mathbb{E}}[\cdot|X_{1},\ldots,X_{t-1}]$.
Assume that $X_{t}\leq R$ for some $R>0$ and ${\mathbb{E}}_{t}[X_{t}]=0$ for
all $t$. Define the random variables

$\displaystyle S:=\sum_{t=1}^{T}X_{t},\hskip
10.0ptV:=\sum_{i=1}^{T}{\mathbb{E}}_{t}[X_{t}^{2}].$

Then for any $\delta>0$, with probability at least $1-\delta$, for any
$\lambda\in[0,1/R]$,

$\displaystyle S\leq(e-2)\lambda V+\frac{\ln(1/\delta)}{\lambda}.$

###### Proof of Lemma A.2.

Let us define the following sequence of random variables:
$Z_{0}=1,Z_{t}=Z_{t-1}\frac{e^{\lambda X_{t}}}{{\mathbb{E}}_{t}[e^{\lambda
X_{t}}]}$. We have

$\displaystyle{\mathbb{E}}_{t}[Z_{t}]$
$\displaystyle={\mathbb{E}}_{t}\left[Z_{t-1}\frac{e^{\lambda
X_{t}}}{{\mathbb{E}}_{t}[e^{\lambda
X_{t}}]}\right]=\frac{Z_{t-1}}{{\mathbb{E}}_{t}[e^{\lambda
X_{t}}]}{\mathbb{E}}_{t}[e^{\lambda X_{t}}]=Z_{t-1}.$

Thus, we have

$\displaystyle{\mathbb{E}}[Z_{T}]={\mathbb{E}}{\mathbb{E}}_{T}[Z_{T}]={\mathbb{E}}[Z_{T-1}]=\ldots={\mathbb{E}}[Z_{0}]=1.$

Note that

$\displaystyle Z_{T}=\frac{e^{\lambda
S}}{\prod_{t=1}^{T}{\mathbb{E}}_{t}[e^{\lambda X_{t}}]}=\frac{e^{\lambda
S}}{\sum_{t=1}^{T}e^{\ln{\mathbb{E}}_{t}[e^{\lambda
X_{t}}]}}=\exp\left(\lambda S-\sum_{t=1}^{T}\ln{\mathbb{E}}_{t}[e^{\lambda
X_{t}}]\right).$ (3)

Since $Z_{T}\geq 0$, it follows from Markov’s inequality that, for any
$\delta>0$, we have

$\displaystyle\Pr(Z_{T}\geq 1/\delta)\leq\delta{\mathbb{E}}[Z_{T}]=\delta.$
(4)

We now bound the logarithmic moment generating function
$\ln{\mathbb{E}}_{t}[e^{\lambda X_{t}}]$ using elementary inequalities: For
any $\lambda\in[0,1/R]$, we have

$\displaystyle\ln{\mathbb{E}}_{t}[e^{\lambda
X_{t}}]\leq{\mathbb{E}}_{t}[e^{\lambda
X_{t}}]-1\leq\lambda{\mathbb{E}}_{t}[X_{t}]+(e-2)\lambda^{2}{\mathbb{E}}_{t}[X_{t}^{2}],$
(5)

where the first inequality uses $\ln z\leq z-1,\forall z\geq 0$ and the second
inequality uses that $e^{z}\leq 1+z+(e-2)z^{2},\forall z\leq 1$ and that
$\lambda X_{t}\leq 1$.

Plugging Equation 5 into Equation 3, then all together into Equation 4
complete the proof.

∎

###  A.2. Functional projections for misspecification

Since 2.1 and 2.2 allow misspecification up to some errors $\xi$ and $\nu$,
while we are working on the function class ${\mathcal{F}}$, we rely on the
following projection operators, 4 and 5, to handle misspecification.

######  Definition 4 (Projection of action-value functions).

For any $\tilde{\pi}\in\Pi^{soft}(T)$ for some $T\in{\mathbb{N}}$, we define
the projection of the state-action value function $\tilde{\pi}$ onto
${\mathcal{F}}$ as

$\displaystyle{\mathrm{Proj}}_{{\mathcal{F}}}(Q^{\tilde{\pi}}):=\operatorname*{arg\,min}_{f\in{\mathcal{F}}}\left\\{|f_{h}(s_{h},a_{h})-Q_{h}^{\tilde{\pi}}(s_{h},a_{h})|,\forall
h\in[H],(s_{h},a_{h})\in{\mathrm{supp}}(d^{\mu}_{h})\right\\}.$

By 2.1, we have

$\displaystyle|{\mathrm{Proj}}_{{\mathcal{F}}}(Q^{\tilde{\pi}})(s_{h},a_{h})-Q_{h}^{\tilde{\pi}}(s_{h},a_{h})|\leq\xi_{h},~{}~{}\forall
h\in[H],(s_{h},a_{h})\in{\mathrm{supp}}(d^{\mu}_{h}).$

######  Definition 5 (Projection of Bellman operations).

For any $f\in{\mathcal{F}}$ and $\tilde{\pi}\in\Pi^{soft}(T)$ for some $T$, we
define the projection of the Bellman operation ${\mathbb{T}}^{\tilde{\pi}}f$
onto ${\mathcal{F}}$ as

$\displaystyle{\mathrm{Proj}}_{{\mathcal{F}}}({\mathbb{T}}^{\tilde{\pi}}f):=\operatorname*{arg\,min}_{f^{\prime}\in{\mathcal{F}}}\left\\{\|f^{\prime}_{h}-{\mathbb{T}}_{h}^{\tilde{\pi}}f_{h+1}\|_{\infty},\forall
h\in[H]\right\\}.$

By 2.2, we have

$\displaystyle\|{\mathrm{Proj}}_{{\mathcal{F}}}({\mathbb{T}}^{\tilde{\pi}}f)-{\mathbb{T}}_{h}^{\tilde{\pi}}f_{h+1}\|_{\infty}\leq\nu_{h},\forall
h\in[H].$

###  A.3. Induced MDPs

We now introduce the notion of _induced_ MDPs which is originally used in
[Zanette et al., 2021].

######  Definition 6 (Induced MDPs).

For any policy $\pi\in\Pi^{all}$ and any sequence of functions
$Q=\\{Q_{h}\\}_{h\in[H]}\in\\{{\mathcal{S}}\times{\mathcal{A}}\rightarrow{\mathbb{R}}\\}^{H}$,
the $(Q,\pi)$-induced MDPs, denoted by $M(Q,\pi)$ is the MDP that is identical
to the original MDP $M$ except only that the expected reward of $M(Q,\pi)$ is
given by $\\{r_{h}^{\pi,Q}\\}_{h\in[H]}$, where

$\displaystyle
r_{h}^{\pi,Q}(s,a):=r_{h}(s,a)-{\mathcal{E}}_{h}^{\pi}(f_{h},f_{h+1})(s,a).$

By definition of $M(\pi,Q)$, $Q$ is the fixed point of the Bellman equation
$Q_{h}={\mathbb{T}}^{\pi}_{h,M(\pi,Q)}Q_{h+1}$.

######  Lemma A.3.

For any $\pi\in\Pi^{all}$ and any sequence of functions
$Q=\\{Q_{h}\\}_{h\in[H]}\in\\{{\mathcal{S}}\times{\mathcal{A}}\rightarrow{\mathbb{R}}\\}^{H}$,
we have

$\displaystyle Q^{\pi}_{M(\pi,Q)}=Q,$

where $M(\pi,Q)$ is the induced MDP given in 6.

###  A.4. Error decomposition

The key starting point for the proofs of all of the three main theorems is the
following error decomposition that decomposes the sub-optimality into three
sources of errors: the Bellman error under the comparator policy $\pi$, the
gap values in the initial states, and the online-regret term due to the
induced MDPs. In online RL, the sub-optimality of a greedy policy against an
optimal policy can be decomposed into the sub-optimality in the Bellman errors
and the error in the initial states [Dann et al., 2021], using the standard
value-function error decomposition in [Jiang et al., 2017, Lemma 1]. However,
in our setting, we compete against an arbitrary policy $\pi$ (not necessarily
an optimal policy) and the learned policy $\pi^{t}$ is not greedy with respect
to the current action-value function ${\underline{Q}}^{t}$ – thus [Jiang et
al., 2017, Lemma 1] cannot apply here. Instead, we develop an error
decomposition – Lemma A.4 which generalizes what was implicit in Zanette et
al. [2021].

######  Lemma A.4 (Error decomposition).

For any action-value functions
$Q\in\\{{\mathcal{S}}\times{\mathcal{A}}\rightarrow{\mathbb{R}}\\}^{H}$ and
any policies $\pi,\tilde{\pi}\in\Pi^{all}$, we have

$\displaystyle\mathrm{SubOpt}^{M}_{\pi}(\tilde{\pi})=\sum_{h=1}^{H}{\mathbb{E}}_{\pi}[{\mathcal{E}}_{h}^{\tilde{\pi}}(Q_{h},Q_{h+1})(s_{h},a_{h})]+Q_{1}(s_{1},\tilde{\pi}_{1})-V_{1}^{\tilde{\pi}}(s_{1})+\mathrm{SubOpt}_{\pi}^{M(Q,\tilde{\pi})}(\tilde{\pi}).$

###### Proof of Lemma A.4.

We have

$\displaystyle\mathrm{SubOpt}^{M}_{\pi}(\tilde{\pi})=V_{1}^{\pi}(s_{1})-V_{1}^{\tilde{\pi}}(s_{1})$
$\displaystyle=\left(V_{1}^{\pi}(s_{1})-V_{1,M(Q,\tilde{\pi})}^{\pi}(s_{1})\right)+\left(V_{1,M(Q,\tilde{\pi})}^{\tilde{\pi}}(s_{1})-V_{1}^{\tilde{\pi}}(s_{1})\right)+\left(V_{1,M(Q,\tilde{\pi})}^{\pi}(s_{1})-V_{1,M(Q,\tilde{\pi})}^{\tilde{\pi}}(s_{1})\right)$
$\displaystyle=\sum_{h=1}^{H}{\mathbb{E}}_{\pi}[{\mathcal{E}}_{h}^{\tilde{\pi}}(Q_{h},Q_{h+1})(s_{h},a_{h})]+Q_{1}(s_{1},\tilde{\pi}_{1})-V_{1}^{\tilde{\pi}}(s_{1})+\mathrm{SubOpt}_{\pi}^{M(Q,\tilde{\pi})}(\tilde{\pi}),$

where in the last equality, for the first term, we use, by 6, that

$\displaystyle V_{1}^{\pi}(s_{1})-V_{1,M(Q,\tilde{\pi})}^{\pi}(s_{1})$
$\displaystyle=\sum_{h=1}^{H}{\mathbb{E}}_{\pi}\left[r_{h}(s_{h},a_{h})-r_{h}^{\tilde{\pi},Q}(s_{h},a_{h})\right]=\sum_{h=1}^{H}{\mathbb{E}}_{\pi}[{\mathcal{E}}_{h}^{\tilde{\pi}}(Q_{h},Q_{h+1})(s_{h},a_{h})],$

for the second term, we use, by Lemma A.3, that

$\displaystyle
V_{1,M(Q,\tilde{\pi})}^{\pi}(s_{1})=Q_{1,M(Q,\tilde{\pi})}^{\pi}(s_{1},\tilde{\pi}_{1})=Q_{1}(s_{1},\tilde{\pi}),$

and for the last term, we use the definition of value sub-optimality in
Equation 1. ∎

###  A.5. Decoupling lemma

One of the central tools for our proofs is the following decoupling lemma. The
decoupling lemma essentially decouples the Bellman residuals under the
$\pi$-induced state-action distribution into the squared Bellman residuals
under the $\mu$-induced state-action distribution and the new data diversity
measure in 3 and additive terms of low order.

######  Lemma A.5 (Decoupling argument).

Under 2.2, for any $f\in{\mathcal{F}}$, any $\tilde{\pi}\in\Pi^{soft}(T)$ for
some $T$, any $\pi\in\Pi^{all}$, any $\lambda>0$, and any ${\epsilon}\geq 0$,
we have

$\displaystyle\sum_{h=1}^{H}{\mathbb{E}}_{\pi}[{\mathcal{E}}^{\tilde{\pi}}_{h}(f_{h},f_{h+1})(s_{h},a_{h})]$
$\displaystyle\leq\frac{1}{2\lambda}\sum_{h=1}^{H}\left(\sum_{k=1}^{K}{\mathbb{E}}_{\mu^{k}}\left[{\mathcal{E}}_{h}^{\tilde{\pi}}(f_{h},f_{h+1})(s_{h},a_{h})^{2}\right]+K\nu_{h}^{2}+4bK\nu_{h}\right)$
$\displaystyle+\frac{\lambda
H\cdot{\mathcal{C}}(\pi;{\epsilon})}{2K}+H{\epsilon}+\sum_{h=1}^{H}\nu_{h},$

where ${\mathcal{C}}(\pi;{\epsilon})$ is defined in 3.

###### Proof of Lemma A.5.

We have

$\displaystyle\sum_{h=1}^{H}{\mathbb{E}}_{\pi}[{\mathcal{E}}_{h}^{\tilde{\pi}}(f_{h},f_{h+1})(s_{h},a_{h})]=\sum_{h=1}^{H}{\mathbb{E}}_{\pi}\left[({\mathbb{T}}_{h}^{\tilde{\pi}}f_{h+1}-f_{h})(s_{h},a_{h})\right]$
$\displaystyle\leq\sum_{h=1}^{H}{\mathbb{E}}_{\pi}\left[({\mathrm{Proj}}_{{\mathcal{F}}_{h}}({\mathbb{T}}_{h}^{\tilde{\pi}}f_{h+1})-f_{h})(s_{h},a_{h})\right]+\bar{\nu}$
$\displaystyle\leq\sum_{h=1}^{H}\sqrt{{\mathcal{C}}(\pi,{\epsilon}){\mathbb{E}}_{\mu}\left[({\mathrm{Proj}}_{{\mathcal{F}}_{h}}({\mathbb{T}}_{h}^{\tilde{\pi}}f_{h+1})-f_{h})(s_{h},a_{h})^{2}\right]}+H{\epsilon}+\bar{\nu}$
$\displaystyle\leq\sum_{h=1}^{H}\sqrt{{\mathcal{C}}(\pi,{\epsilon})\left({\mathbb{E}}_{\mu}[{\mathcal{E}}_{h}^{\tilde{\pi}}(f_{h},f_{h+1})(s_{h},a_{h})^{2}]+\nu_{h}^{2}+4b\nu_{h}\right)}+H{\epsilon}+\bar{\nu}$
$\displaystyle\leq\sqrt{H{\mathcal{C}}(\pi,{\epsilon})\sum_{h=1}^{H}\left({\mathbb{E}}_{\mu}[{\mathcal{E}}_{h}^{\tilde{\pi}}(f_{h},f_{h+1})(s_{h},a_{h})^{2}]+\nu_{h}^{2}+4b\nu_{h}\right)}+H{\epsilon}+\bar{\nu}$
$\displaystyle\leq\frac{K}{2\lambda}\sum_{h=1}^{H}\left({\mathbb{E}}_{\mu}[{\mathcal{E}}_{h}^{\tilde{\pi}}(f_{h},f_{h+1})(s_{h},a_{h})^{2}]+\nu_{h}^{2}+4b\nu_{h}\right)+\frac{\lambda
H{\mathcal{C}}(\pi,{\epsilon})}{2K}+H{\epsilon}+\bar{\nu},$

where the first inequality uses 2.2, the second inequality uses the definition
of $C_{\pi}({\epsilon})$, the third inequality uses 2.2 (again), the fourth
inequality uses Cauchy-Schwartz inequality, and the last inequality uses the
AM-GM inequality $\sqrt{xy}\leq\frac{K}{2\lambda}x+\frac{\lambda}{2K}y$. ∎

###  A.6. Regret of the multiplicative weights algorithm for the actors

Now we establish the regret bound for the online-regret term due to the
induced MDPs. The result in the following lemma is quite standard and can be
readily generalized from a similar result in Zanette et al. [2021]. We present
the proof here for completeness.

######  Lemma A.6.

Consider an arbitrary sequence of value functions $\\{Q^{t}\\}_{t\in[T]}$ such
that $\max_{h,t}\|Q^{t}_{h}\|_{\infty}\leq b$ and define the following
sequence of policies $\\{\pi^{t}\\}_{t\in[T+1]}$ where

$\displaystyle\pi^{1}(\cdot|s)$
$\displaystyle={\mathrm{Uniform}}({\mathcal{A}}),\forall s,$
$\displaystyle\pi^{t+1}_{h}(a|s)$
$\displaystyle\propto\pi^{t}_{h}(a|s)\exp\left(\eta
Q^{t}_{h}(s,a)\right),\forall(s,a,h,t).$

Suppose $\eta=\sqrt{\frac{\ln{\mathrm{Vol}}({\mathcal{A}})}{4(e-2)b^{2}T}}$
and $T\geq\frac{\ln{\mathrm{Vol}}({\mathcal{A}})}{(e-2)}$, where
${\mathrm{Vol}}({\mathcal{A}})$ denotes the volume of the action set
${\mathcal{A}}$. 888When $|{\mathcal{A}}|<\infty$,
${\mathrm{Vol}}({\mathcal{A}})=|{\mathcal{A}}|$. For an arbitrary policy
$\pi\in\Pi^{all}$, we have

$\displaystyle\sum_{t=1}^{T}\left(V^{\pi}_{1,M(\pi^{t},Q^{t})}(s_{1})-V_{1,M(\pi^{t},Q^{t})}^{\pi^{t}}(s_{1})\right)\leq
4Hb\sqrt{T\ln{\mathrm{Vol}}({\mathcal{A}})}.$

###### Proof of Lemma A.6.

The proof for this lemma is quite standard as shown in Zanette et al. [2021].
We rewrote the proof with a slight modification for completeness. For
simplicity, we write $M_{t}:=M(\pi^{t},Q^{t})$. We will see that the key
property that enables this lemma is that $Q^{t}_{h}=Q^{\pi^{t}}_{h,M_{t}}$
(Lemma A.3), which allows us to relate the value difference lemma to the log
policy ratio. Using the value difference lemma (Lemma F.2), we have

$\displaystyle
V^{\pi}_{1,M_{t}}(s_{1})-V_{1,M_{t}}^{\pi^{t}}(s_{1})=\sum_{h=1}^{H}{\mathbb{E}}_{\pi}A^{\pi^{t}}_{h,M_{t}}(s_{h},a_{h}),$

where ${\mathbb{E}}_{\pi}$ is the expectation over the random trajectory
$(s_{1},a_{1},\ldots,s_{H},a_{H})$ generated by $\pi$ (and the underlying MDP
$M_{t}$999Note that
$\Pr((s_{1},a_{1},\ldots,s_{H},a_{H})|\pi,M)=\Pr((s_{1},a_{1},\ldots,s_{H},a_{H})|\pi,M_{t})$
since $M_{t}$ and $M$ have identical transition kernels.). For any
$V:{\mathcal{S}}\rightarrow{\mathbb{R}}$, it follows from the definition of
$\\{\pi^{t}\\}$ update that we have

$\displaystyle\log\frac{\pi^{t+1}_{h}(a|s)}{\pi^{t}_{h}(a|s)}$
$\displaystyle=\eta
Q^{t}_{h}(s,a)-\log\left({\mathbb{E}}_{a\sim\pi_{h}^{t}(\cdot|s)}\left[\exp\left(\eta
Q^{t}_{h}(s,a)\right)\right]\right)$
$\displaystyle=\eta(Q^{t}_{h}(s,a)-V(s))-\log\left({\mathbb{E}}_{a\sim\pi_{h}^{t}(\cdot|s)}\left[\exp\left(\eta(Q^{t}_{h}(s,a)-V(s))\right)\right]\right).$

In the equation above, noting that $Q^{t}_{h}=Q^{\pi^{t}}_{h,M_{t}}$ (Lemma
A.3) and replacing $V(s)$ by $V^{\pi^{t}}_{h,M_{t}}$, we have

$\displaystyle\log\frac{\pi^{t+1}_{h}(a|s)}{\pi^{t}_{h}(a|s)}=\eta
A^{\pi^{t}}_{h,M_{t}}(s,a)-\log\left({\mathbb{E}}_{a\sim\pi_{h}^{t}(\cdot|s)}\left[\exp\left(\eta
A^{\pi^{t}}_{h,M_{t}}(s,a)\right)\right]\right),$ (6)

where we define the advantage function
$A^{\pi}_{M}=\\{A^{\pi}_{h,M}\\}_{h\in[H]}$ as

$\displaystyle
A^{\pi}_{h,M}(s,a):=Q^{\pi}_{h,M}(s,a)-V^{\pi}_{h,M}(s),\forall(s,a,h).$

Note that $|A^{\pi^{t}}_{h,M_{t}}(s,a)|\leq 2b$. By choosing
$\eta\in(0,1/(2b))$, we have

$\displaystyle\log\left({\mathbb{E}}_{a\sim\pi_{h}^{t}(\cdot|s)}\left[\exp\left(\eta
A^{\pi^{t}}_{h,M_{t}}(s,a)\right)\right]\right)$
$\displaystyle\leq\log\left({\mathbb{E}}_{a\sim\pi_{h}^{t}(\cdot|s)}\left[1+\eta
A^{\pi^{t}}_{h,M_{t}}(s,a)+(e-2)\eta^{2}A^{\pi^{t}}_{h,M_{t}}(s,a)^{2}\right]\right)$
$\displaystyle=\log\left({\mathbb{E}}_{a\sim\pi_{h}^{t}(\cdot|s)}\left[1+(e-2)\eta^{2}A^{\pi^{t}}_{h,M_{t}}(s,a)^{2}\right]\right)$
$\displaystyle\leq\log(1+(e-2)\eta^{2}4b^{2})$ $\displaystyle\leq
4(e-2)b^{2}\eta^{2}$ (7)

where the first inequality uses that $e^{x}\leq 1+x+(e-2)x^{2},\forall x\leq
1$ and $|\eta A^{\pi^{t}}_{h,M_{t}}(s,a)|\leq 1,\forall(s,a)$, the first
equality uses that
${\mathbb{E}}_{a\sim\pi_{h}^{t}(\cdot|s)}\left[A^{\pi^{t}}_{h,M_{t}}(s,a)\right]=0$,
the second inequality uses that $|A^{\pi^{t}}_{h,M_{t}}(s,a)|\leq 2b$, and the
last inequality uses that $\log(1+x)\leq x,\forall x\geq 0$. Combining
Equation 7 and Equation 6, we have

$\displaystyle
A^{\pi^{t}}_{h,M_{t}}(s,a)\leq\frac{1}{\eta}\log\frac{\pi^{t+1}_{h}(a|s)}{\pi^{t}_{h}(a|s)}+4(e-2)b^{2}\eta.$

Thus, for any $h\in[H]$, we have

$\displaystyle\sum_{t=1}^{T}{\mathbb{E}}_{\pi}A^{\pi^{t}}_{h,M_{t}}(s_{h},a_{h})$
$\displaystyle\leq\frac{1}{\eta}\sum_{t=1}^{T}\left({\mathbb{E}}_{\pi}\left[KL[\pi_{h}(\cdot|s_{h})\|\pi_{h}^{t}(\cdot|s_{h})]\right]-{\mathbb{E}}_{\pi}\left[KL[\pi_{h}(\cdot|s_{h})\|\pi_{h}^{t+1}(\cdot|s_{h})]\right]\right)+4(e-2)Tb^{2}\eta$
$\displaystyle=\frac{1}{\eta}\left({\mathbb{E}}_{\pi}\left[KL[\pi_{h}(\cdot|s_{h})\|\pi_{h}^{1}(\cdot|s_{h})]\right]-{\mathbb{E}}_{\pi}\left[KL[\pi_{h}(\cdot|s_{h})\|\pi_{h}^{T+1}(\cdot|s_{h})]\right]\right)+4(e-2)Tb^{2}\eta$
$\displaystyle\leq\frac{1}{\eta}{\mathbb{E}}_{\pi}\left[KL[\pi_{h}(\cdot|s_{h})\|\pi_{h}^{1}(\cdot|s_{h})]\right]+4(e-2)Tb^{2}\eta$
$\displaystyle\leq\frac{1}{\eta}\log({\mathrm{Vol}}({\mathcal{A}}))+4(e-2)Tb^{2}\eta,$

where the second inequality uses the non-negativity of KL divergence, and the
last inequality uses that
$KL[\pi_{h}(\cdot|s_{h})\|\pi_{h}^{1}(\cdot|s_{h})]=-H[\pi_{h}(\cdot|s_{h})]+\log({\mathrm{Vol}}({\mathcal{A}}))\leq\log({\mathrm{Vol}}({\mathcal{A}}))$
where $\pi^{1}$ is uniform over ${\mathcal{A}}$ and
${\mathrm{Vol}}({\mathcal{A}})$ denotes the volume over the compact set
${\mathcal{A}}$. Combining all pieces together, we have

$\displaystyle\sum_{t=1}^{T}{\mathbb{E}}_{\pi}A^{\pi^{t}}_{h,M_{t}}(s_{h},a_{h})\leq\frac{1}{\eta}H\log({\mathrm{Vol}}({\mathcal{A}}))+4(e-2)THb^{2}\eta.$

Minimizing the RHS of the above equation with respect to $\eta$ yields
$\eta=\sqrt{\frac{\log{\mathrm{Vol}}({\mathcal{A}})}{4(e-2)b^{2}T}}$ and

$\displaystyle\sum_{t=1}^{T}{\mathbb{E}}_{\pi}A^{\pi^{t}}_{h,M_{t}}(s_{h},a_{h})\leq
2H\sqrt{4(e-2)b^{2}T\log{\mathrm{Vol}}({\mathcal{A}})}\leq
4Hb\sqrt{T\log{\mathrm{Vol}}({\mathcal{A}})}.$

Finally, we need that

$\displaystyle\eta=\sqrt{\frac{\log{\mathrm{Vol}}({\mathcal{A}})}{4(e-2)b^{2}T}}\leq\frac{1}{2b},$

which implies $T\geq\frac{\ln{\mathrm{Vol}}({\mathcal{A}})}{(e-2)}$. ∎

We are now ready to establish the proofs of our three main theorems.

##  Appendix B Proof of Theorem 1

To construct our proof for Theorem 1, we first establish two following lemmas.
The first lemma, Lemma B.1 establishes that the in-distribution squared
Bellman residuals are bounded by the unbiased proxy of the squared Bellman
error ${\mathcal{L}}_{{\tilde{\pi}}}(f)$, up to some estimation and
approximation errors. The second lemma, Lemma B.2, asserts that the unbiased
proxy of the squared Bellman error at the projection of $Q^{{\tilde{\pi}}}$ is
close to zero, up to some estimation and approximation errors.

######  Lemma B.1.

For any $\delta>0,{\epsilon}>0$ and any $T\in{\mathbb{N}}$, under 2.2, with
probability at least $1-\delta$, it holds uniformly over all
$f\in{\mathcal{F}}$ and $\tilde{\pi}\in\Pi^{soft}(T)$ that

$\displaystyle\sum_{h=1}^{H}\sum_{k=1}^{K}{\mathbb{E}}_{k}\left[{\mathcal{E}}^{\tilde{\pi}}_{h}(f_{h},f_{h+1})(s_{h},a_{h})^{2}\right]$
$\displaystyle\leq
2{\mathcal{L}}_{{\tilde{\pi}}}(f)+40b(b+2)KH{\epsilon}+12bK\sum_{h=1}^{H}\nu_{h}$
$\displaystyle+144(e-2)b^{2}H\left[d_{{\mathcal{F}}}({\epsilon})+d_{\Pi}({\epsilon},T)+\ln(1/\delta)\right],$

where
${\mathcal{L}}_{{\tilde{\pi}}}(f):=\sum_{h=1}^{H}\hat{L}_{{\tilde{\pi}}}(f_{h},f_{h+1})-\inf_{g\in{\mathcal{F}}}\sum_{h=1}^{H}\hat{L}_{{\tilde{\pi}}}(g_{h},f_{h+1})$.

######  Lemma B.2.

Under 2.1, for any $T\in{\mathbb{N}}$, with probability at least $1-\delta$,
it holds uniformly for any ${\tilde{\pi}}\in\Pi^{soft}(T)$ that

$\displaystyle{\mathcal{L}}_{{\tilde{\pi}}}({\mathrm{Proj}}_{{\mathcal{F}}}(Q^{{\tilde{\pi}}}))$
$\displaystyle\leq
36(e-2)b^{2}H\left(2d_{{\mathcal{F}}}({\epsilon})+d_{\Pi}({\epsilon},T)+\ln\frac{H}{\delta}\right)+6b(3b+4){\epsilon}KH$
$\displaystyle+15bK\sum_{h=1}^{H}\xi_{h},$

where ${\mathrm{Proj}}_{{\mathcal{F}}}(Q^{{\tilde{\pi}}})$ is the projection
of $Q^{{\tilde{\pi}}}$ onto ${\mathcal{F}}$, formally defined in 4.

###  B.1. Proof of Theorem 1

With the two lemmas above, we are ready to prove Theorem 1. This proof is also
laying a foundational step for our proofs of Theorem 2 and Theorem 3 that we
shall present shortly. The proofs for the two lemmas above are presented
immediately after the proof of Theorem 1.

###### Proof of Theorem 1..

Using Lemma A.4, we have

$\displaystyle\mathrm{SubOpt}_{\pi}^{M}(\pi^{t})$
$\displaystyle=\sum_{h=1}^{H}{\mathbb{E}}_{\pi}[{\mathcal{E}}_{h}^{\pi^{t}}({\underline{Q}}^{t}_{h},{\underline{Q}}^{t}_{h+1})(s_{h},a_{h})]+\Delta_{1}{\underline{Q}}_{1}(s_{1},\pi_{1}^{t})+\mathrm{SubOpt}_{\pi}^{M_{t}}(\pi^{t})$

where we denote

$\displaystyle M_{t}$ $\displaystyle:=M({\underline{Q}}^{t},\pi^{t}),$
$\displaystyle\Delta_{1}{\underline{Q}}_{1}(s_{1},\pi^{t})$
$\displaystyle:={\underline{Q}}_{1}(s_{1},\pi^{t})-V_{1}^{\pi^{t}}(s_{1}).$

##### Bounding $\sum_{t=1}^{T}\mathrm{SubOpt}_{\pi}^{M_{t}}(\pi^{t})$.

Note that $\sum_{t=1}^{T}\mathrm{SubOpt}_{\pi}^{M_{t}}(\pi^{t})$ can be
controlled by standard tools from online learning (Lemma A.6); thus it remains
to control the first $H+1$ terms.

##### Bounding $\Delta_{1}{\underline{Q}}_{1}(s_{1},\pi_{1}^{t})$.

Due to Lemma B.2, the event that
${\mathrm{Proj}}_{{\mathcal{F}}}(Q^{\pi^{t}})\in{\mathcal{F}}(\beta;\pi^{t})$
holds occur at probability at least $1-\delta$. Furthermore, under this event,
we have

$\displaystyle\Delta_{1}{\underline{Q}}_{1}(s_{1},\pi_{1}^{t})$
$\displaystyle={\underline{Q}}_{1}(s_{1},\pi^{t})-V_{1}^{\pi^{t}}(s_{1})$
$\displaystyle\leq{\mathrm{Proj}}_{{\mathcal{F}}_{1}}(Q_{1}^{\pi^{t}})-V_{1}^{\pi^{t}}(s_{1})$
$\displaystyle\leq\xi_{1},$

where the first inequality exploits 2 of Algorithm 2, and the last inequality
uses 2.1.

##### Bounding
$\sum_{h=1}^{H}{\mathbb{E}}_{\pi}[{\mathcal{E}}_{h}^{\pi^{t}}({\underline{Q}}^{t}_{h},{\underline{Q}}^{t}_{h+1})(s_{h},a_{h})]$.

It follows from Lemma A.5 that

$\displaystyle\sum_{h=1}^{H}{\mathbb{E}}_{\pi}[{\mathcal{E}}_{h}^{\pi^{t}}({\underline{Q}}^{t}_{h},{\underline{Q}}^{t}_{h+1})(s_{h},a_{h})]$
$\displaystyle\leq\sqrt{H{\mathcal{C}}(\pi;{\epsilon})\sum_{h=1}^{H}\left({\mathbb{E}}_{\mu}[{\mathcal{E}}_{h}^{\tilde{\pi}}({\underline{Q}}_{h}^{t},{\underline{Q}}^{t}_{h+1})(s_{h},a_{h})^{2}]+\nu_{h}^{2}+4b\nu_{h}\right)}$
$\displaystyle+H{\epsilon}+\bar{\nu}.$

The term
$\sum_{h=1}^{H}{\mathbb{E}}_{\mu}[{\mathcal{E}}_{h}^{\tilde{\pi}}({\underline{Q}}_{h}^{t},{\underline{Q}}^{t}_{h+1})(s_{h},a_{h})^{2}]$
is bounded by Lemma B.1, with notice that
${\mathcal{L}}_{\pi^{t}}({\underline{Q}}^{t})\leq\beta$ (due to the definition
of ${\mathcal{F}}(\beta;\pi^{t})$ in Algorithm 2).

Combining the three steps above via the union bound completes our proof. ∎

We now prove the two support lemmas.

###  B.2. Proof of Lemma B.1

###### Proof of Lemma B.1.

Let us consider any fixed $f\in{\mathcal{F}}$ and any $\pi\in\Pi^{all}$. By
Lemma A.1, we have

$\displaystyle{\mathbb{E}}_{k,h}[\Delta L_{\pi}(f_{h},f_{h+1};z^{k}_{h})]$
$\displaystyle={\mathcal{E}}^{\pi}_{h}(f_{h},f_{h+1})(s^{k}_{h},a^{k}_{h})^{2},$
$\displaystyle{\mathbb{E}}_{k,h}[\Delta L_{\pi}(f_{h},f_{h+1};z^{k}_{h})^{2}]$
$\displaystyle\leq
36b^{2}{\mathcal{E}}^{\pi}_{h}(f_{h},f_{h+1})(s^{k}_{h},a^{k}_{h})^{2}.$

Combining with Lemma A.2, we have that with probability at least $1-\delta$,
for any $\iota\in[0,\frac{1}{13b^{2}}]$,

$\displaystyle\sum_{k=1}^{K}{\mathbb{E}}_{k}[{\mathcal{E}}_{h}^{\pi}(f_{h},f_{h+1})(s_{h},a_{h})^{2}]-\sum_{k=1}^{K}\Delta
L_{\pi}(f_{h},f_{h+1};z^{k}_{h})$ $\displaystyle\leq
36(e-2)b^{2}\iota\sum_{k=1}^{K}{\mathbb{E}}_{k}[{\mathcal{E}}_{h}^{\pi}(f_{h},f_{h+1})(s_{h},a_{h})^{2}]+(1/\iota)\log(1/\delta).$

By setting $\iota=\frac{1}{72(e-2)b^{2}}$, the above inequality becomes

$\displaystyle\sum_{k=1}^{K}{\mathbb{E}}_{k}[{\mathcal{E}}_{h}^{\pi}(f_{h},f_{h+1})(s_{h},a_{h})^{2}]\leq
2\sum_{k=1}^{K}\Delta
L_{\pi}(f_{h},f_{h+1};z^{k}_{h})+144(e-2)b^{2}\ln(1/\delta).$

For any ${\epsilon}>0$, and for any $f\in{\mathcal{F}},\pi\in\Pi^{soft}(T)$,
by definition of ${\epsilon}$-covering, there exist $f^{\prime}$ and
$\pi^{\prime}$ in the ${\epsilon}$-cover of ${\mathcal{F}}$ and
$\Pi^{soft}(T)$, i.e.,

$\displaystyle\|f_{h}-f^{\prime}_{h}\|_{\infty}\leq{\epsilon},\|\pi_{h}-\pi^{\prime}_{h}\|_{1,\infty}\leq{\epsilon}.$

By simple calculations, we have

$\displaystyle|{\mathcal{E}}_{h}^{\pi}(f_{h},f_{h+1})(s_{h},a_{h})^{2}-{\mathcal{E}}_{h}^{\pi^{\prime}}(f^{\prime}_{h},f^{\prime}_{h+1})(s_{h},a_{h})^{2}|$
$\displaystyle\leq 4b(b+2){\epsilon},$ $\displaystyle|\Delta
L_{\pi}(f_{h},f_{h+1};z^{k}_{h})-\Delta
L_{\pi^{\prime}}(f^{\prime}_{h},f^{\prime}_{h+1};z^{k}_{h})|$
$\displaystyle\leq 18b(b+2){\epsilon}.$

Thus, by the union bound, we have with probability at least $1-\delta$, it
holds uniformly over all $f\in{\mathcal{F}},\pi\in\Pi^{soft}(T)$ that

$\displaystyle\sum_{h=1}^{H}\sum_{k=1}^{K}{\mathbb{E}}_{k}[{\mathcal{E}}_{h}^{\pi}(f_{h},f_{h+1})(s_{h},a_{h})^{2}]\leq
2\sum_{h=1}^{H}\sum_{k=1}^{K}\Delta
L_{\pi}(f_{h},f_{h+1};z^{k}_{h})+40b(b+2)KH{\epsilon}$
$\displaystyle+144(e-2)b^{2}\sum_{h=1}^{H}\ln(N({\epsilon};{\mathcal{F}}_{h},\|\cdot\|_{\infty})N({\epsilon};\Pi^{soft}_{h}(T),\|\cdot\|_{1,\infty})/\delta).$

Finally, notice that

$\displaystyle|l_{\pi}({\mathbb{T}}_{h}^{\pi}f_{h+1},f_{h+1};z_{h})-l_{\pi}({\mathrm{Proj}}_{{\mathcal{F}}_{h}}({\mathbb{T}}_{h}^{\pi}f_{h+1}),f_{h+1};z_{h})|\leq
6b\nu_{h}.$

Thus, we have

$\displaystyle\sum_{h=1}^{H}\sum_{k=1}^{K}\Delta
L_{\pi}(f_{h},f_{h+1};z^{k}_{h})\leq{\mathcal{L}}_{\pi}(f)+6bK\sum_{h=1}^{H}\nu_{h}.$

We can then conclude our proof. ∎

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

In order to prove Lemma B.2, we shall first prove the following lemma, which
establishes the confidence radius of the empirical squared Bellman errors that
we used to establish the version space in Algorithm 2.

######  Lemma B.3.

Consider any $\delta>0,{\epsilon}>0,T\in{\mathbb{N}}$, let

$\displaystyle\beta_{{\epsilon}}$
$\displaystyle:=36(e-2)b^{2}\left(2d_{{\mathcal{F}}}({\epsilon})+d_{\Pi}({\epsilon},T)+\ln(H/\delta)\right)+6b(3b+4){\epsilon}K.$

With probability at least $1-\delta$, it holds uniformly over any
$\pi\in\Pi^{soft}(T)$, $f\in{\mathcal{F}}$, and $h\in[H]$ that

$\displaystyle\sum_{k=1}^{K}\left({\mathbb{T}}^{\pi}_{h}f_{h+1}(x^{k}_{h})-r^{k}_{h}-f_{h+1}(s^{k}_{h+1},\pi_{h+1})\right)^{2}\leq\inf_{g_{h}\in{\mathcal{F}}_{h}}\sum_{k=1}^{K}\left(g_{h}(x^{k}_{h})-r^{k}_{h}-f_{h+1}(s^{k}_{h+1},\pi_{h+1})\right)^{2}+\beta_{{\epsilon}}.$

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

Let us fix any $h\in[H]$. For any
$(f,g,\pi)\in{\mathcal{F}}\times{\mathcal{F}}\times\Pi^{soft}(T)$ and any
$k\in[K]$, define the following random variable

$\displaystyle
Z_{k,h}(f,g,\pi):=\left(g_{h}(x^{k}_{h})-r^{k}_{h}-f_{h+1}(s^{k}_{h+1},\pi_{h+1})\right)^{2}-\left({\mathbb{T}}^{\pi}_{h}f_{h+1}(x^{k}_{h})-r^{k}_{h}-f_{h+1}(s^{k}_{h+1},\pi_{h+1})\right)^{2}.$

Denote

$\displaystyle{\mathbb{E}}_{k,h}[\cdot]:={\mathbb{E}}\left[\cdot\bigg{|}\\{z^{i}_{h}\\}_{h\in[H]}^{i\in[k-1]},s_{1}^{k},a_{1}^{k},r_{1}^{k},\ldots,s^{k}_{h-1},a^{k}_{h-1},r^{k}_{h-1},s^{k}_{h},a^{k}_{h}\right].$

By Lemma A.1, we have

$\displaystyle{\mathbb{E}}_{k,h}\left[Z_{k,h}(f,g,\pi)\right]$
$\displaystyle={\mathcal{E}}_{h}^{\pi}(g_{h},f_{h+1})(s^{k}_{h},a^{k}_{h})^{2},$
$\displaystyle{\mathbb{E}}_{k,h}\left[Z^{2}_{k,h}(f,g,\pi)\right]$
$\displaystyle\leq
36b^{2}{\mathcal{E}}_{h}^{\pi}(g_{h},f_{h+1})(s^{k}_{h},a^{k}_{h})^{2}.$

Thus, combing with Lemma A.2, for any
$(f,g,\pi)\in{\mathcal{F}}\times{\mathcal{F}}\times\Pi^{soft}(T)$, with
probability at least $1-\delta$, for any $\iota\in[0,\frac{1}{13b^{2}}]$,

$\displaystyle\sum_{k=1}^{K}{\mathbb{E}}_{k,h}\left[Z_{k,h}(f,g,\pi)\right]-\sum_{k=1}^{K}Z_{k,h}(f,g,\pi)\leq
36(e-2)b^{2}\iota\sum_{k=1}^{K}{\mathcal{E}}_{h}^{\pi}(g_{h},f_{h+1})(s^{k}_{h},a^{k}_{h})^{2}+\frac{\ln(1/\delta)}{\iota}.$

By setting $\iota=1/(36(e-2)b^{2})$, the above inequality becomes

$\displaystyle-\sum_{k=1}^{K}Z_{k,h}(f,g,\pi)\leq 36(e-2)b^{2}\ln(1/\delta).$
(8)

For any ${\epsilon}>0$, let ${\mathcal{F}}^{{\epsilon}}$ and
$\Pi^{{\epsilon}}$ be ${\epsilon}$-covers of ${\mathcal{F}}$ and
$\Pi^{soft}(T)$, respectively, with respect to $\|\cdot\|_{\infty}$ and
$\|\cdot\|_{\infty,1}$, respectively, where
$\|u-v\|_{\infty}:=\sup_{(s,a)}|u(s,a)-v(s,a)|$ and
$\|\pi-\pi^{\prime}\|_{\infty,1}:=\sup_{s}\sum_{a\in{\mathcal{A}}}|\pi(a|s)-\pi^{\prime}(a|s)|$.
Using the union bound, it follows from Equation 8 that with probability at
least $1-\delta$, it holds uniformly over any $h\in[H]$ and any
$(f,g,\pi)\in{\mathcal{F}}^{{\epsilon}}\times{\mathcal{F}}^{{\epsilon}}\times\Pi^{{\epsilon}}$
that

$\displaystyle-\sum_{k=1}^{K}Z_{k,h}(f,g,\pi)\leq
18(e-2)b^{2}\left[\ln(H/\delta)+2d_{{\mathcal{F}}}({\epsilon})+d_{\Pi}({\epsilon},T)\right].$

For any $(f,g,\pi)\in{\mathcal{F}}\times{\mathcal{F}}\times\Pi^{soft}(T)$,
there exist
$(f_{{\epsilon}},g_{{\epsilon}},\pi_{{\epsilon}})\in{\mathcal{F}}^{{\epsilon}}\times{\mathcal{F}}^{{\epsilon}}\times\Pi^{{\epsilon}}$
such that

$\displaystyle\|f_{h}-(f_{{\epsilon}})_{h}\|_{\infty}\leq{\epsilon},\|g_{h}-(g_{{\epsilon}})_{h}\|_{\infty}\leq{\epsilon},\|\pi_{h}-(\pi_{{\epsilon}})_{h}\|_{\infty,1}\leq{\epsilon},\forall
h\in[H].$

It is easy to compute the discretization error that

$\displaystyle
Z_{k,h}(f,g,\pi)-Z_{k,h}(f_{{\epsilon}},g_{{\epsilon}},\pi_{{\epsilon}})\leq
18b(b+1){\epsilon}.$

Using the discretization argument and the union bound complete our proof. ∎

We are now ready to prove Lemma B.2.

###### Proof of Lemma B.2.

Consider the event that the inequality in Lemma B.3 holds. Under this event,
for any ${\tilde{\pi}}\in\Pi^{soft}(T)$, we have

$\displaystyle\sum_{k=1}^{K}l_{{\tilde{\pi}}}({\mathrm{Proj}}_{{\mathcal{F}}_{h}}(Q_{h}^{{\tilde{\pi}}}),{\mathrm{Proj}}_{{\mathcal{F}}_{h+1}}(Q_{h+1}^{{\tilde{\pi}}});z^{k}_{h})\leq\sum_{k=1}^{K}l_{{\tilde{\pi}}}(Q_{h}^{\pi^{t}},Q_{h+1}^{{\tilde{\pi}}};z^{k}_{h})+6bK\xi_{h}$
$\displaystyle=\sum_{k=1}^{K}l_{{\tilde{\pi}}}({\mathbb{T}}^{{\tilde{\pi}}}_{h}Q_{h+1}^{{\tilde{\pi}}},Q_{h+1}^{{\tilde{\pi}}};z^{k}_{h})+6bK\xi_{h}$
$\displaystyle\leq\sum_{k=1}^{K}l_{{\tilde{\pi}}}({\mathbb{T}}^{{\tilde{\pi}}}_{h}{\mathrm{Proj}}_{{\mathcal{F}}_{h+1}}(Q_{h+1}^{{\tilde{\pi}}}),{\mathrm{Proj}}_{{\mathcal{F}}_{h+1}}(Q_{h+1}^{{\tilde{\pi}}});z^{k}_{h})+12bK\xi_{h}$
$\displaystyle\leq\sum_{k=1}^{K}l_{{\tilde{\pi}}}(g_{h},{\mathrm{Proj}}_{{\mathcal{F}}_{h+1}}(Q^{{\tilde{\pi}}}_{h+1});z^{k}_{h})+\beta_{{\epsilon}}+12bK\xi_{h}~{}~{}~{}\text{(for
any $g_{h}\in{\mathcal{F}}_{h}$)}$
$\displaystyle\leq\sum_{k=1}^{K}l_{{\tilde{\pi}}}(g_{h},Q^{{\tilde{\pi}}}_{h+1};z^{k}_{h})+\beta_{{\epsilon}}+15bK\xi_{h},$

where we use 2.1 for the first, second, and last inequalities, the third
inequality uses Lemma B.3, and the equality uses
$Q_{h+1}^{{\tilde{\pi}}}={\mathbb{T}}^{{\tilde{\pi}}}_{h}Q_{h+1}^{{\tilde{\pi}}}$.
Rearranging the last inequality completes our proof. ∎

##  Appendix C Proof of Theorem 2

In this appendix, we present our complete argument to establish Theorem 2. In
order to prove Theorem 2, the key is to establish a connection from the
squared Bellman error under the data distribution $\mu$ to the regularized
objective in Algorithm 3. This key idea should become clear in the following
proof.

###### Proof of Theorem 2.

Similar to the proof of Theorem 1, our starting point is using Lemma A.4:

$\displaystyle\mathrm{SubOpt}_{\pi}^{M}(\pi^{t})$
$\displaystyle=\sum_{h=1}^{H}{\mathbb{E}}_{\pi}[{\mathcal{E}}_{h}^{\pi^{t}}({\underline{Q}}^{t}_{h},{\underline{Q}}^{t}_{h+1})(s_{h},a_{h})]+\Delta_{1}{\underline{Q}}_{1}(s_{1},\pi_{1}^{t})+\mathrm{SubOpt}_{\pi}^{M_{t}}(\pi^{t})$

and we bound $\sum_{t=1}^{T}\mathrm{SubOpt}_{\pi}^{M_{t}}(\pi^{t})$ using
Lemma A.6. We now bound the remaining terms.

For any $\gamma>0$, we have

$\displaystyle\sum_{h=1}^{H}{\mathbb{E}}_{\pi}[{\mathcal{E}}_{h}^{\pi^{t}}({\underline{Q}}^{t}_{h},{\underline{Q}}_{h+1}^{t})(s_{h},a_{h})]$
$\displaystyle\leq\frac{K}{2\lambda}\sum_{h=1}^{H}\left({\mathbb{E}}_{\mu}[{\mathcal{E}}_{h}^{\pi^{t}}({\underline{Q}}_{h}^{t},{\underline{Q}}^{t}_{h+1})(s_{h},a_{h})^{2}]+\nu_{h}^{2}+4b\nu_{h}\right)+\frac{\lambda
H{\mathcal{C}}({\pi},{\epsilon})}{2K}+H{\epsilon}+\bar{\nu}$
$\displaystyle\leq\frac{{\mathcal{L}}_{\pi^{t}}({\underline{Q}})+0.5\iota_{1}+0.5K\bar{\nu}^{2}+2bK\bar{\nu}}{\lambda}+\frac{\lambda
H{\mathcal{C}}({\pi},{\epsilon})}{2K}+H{\epsilon}+\bar{\nu},$

where the first inequality uses Lemma A.5 and the second inequality uses Lemma
B.1, and here
$\iota_{1}:=40b(b+2)KH{\epsilon}+12bK\sum_{h=1}^{H}\nu_{h}+144(e-2)b^{2}H\left[d_{{\mathcal{F}}}({\epsilon})+d_{\Pi}({\epsilon},T)+\ln(1/\delta)\right]$.
Thus, we have

$\displaystyle\sum_{h=1}^{H}{\mathbb{E}}_{\pi}[{\mathcal{E}}_{h}^{\pi^{t}}({\underline{Q}}^{t}_{h},{\underline{Q}}^{t}_{h+1})(s_{h},a_{h})]+\Delta_{1}{\underline{Q}}_{1}(s_{1},\pi_{1}^{t})$
$\displaystyle\leq\frac{{\mathcal{L}}_{\pi^{t}}({\underline{Q}})+\lambda\Delta_{1}{\underline{Q}}_{1}(s_{1},\pi_{1}^{t})+0.5\iota_{1}+0.5K\sum_{h=1}^{H}\nu_{h}^{2}+2bK\sum_{h=1}^{H}\nu_{h}}{\lambda}+\frac{\lambda
H{\mathcal{C}}({\pi},{\epsilon})}{2K}$
$\displaystyle+H{\epsilon}+\sum_{h=1}^{H}\nu_{h}$
$\displaystyle\leq\frac{{\mathcal{L}}_{\pi^{t}}({\mathrm{Proj}}_{{\mathcal{F}}}(Q^{\pi^{t}}))+\lambda\Delta_{1}{\mathrm{Proj}}_{{\mathcal{F}}_{1}}(Q^{\pi^{t}}_{1})(s_{1},\pi_{1}^{t})+0.5\iota_{1}+\sum_{h=1}^{H}\nu_{h}^{2}+2bK\sum_{h=1}^{H}\nu_{h}}{\lambda}$
$\displaystyle+\frac{\lambda
H{\mathcal{C}}({\pi},{\epsilon})}{2K}+H{\epsilon}+\sum_{h=1}^{H}\nu_{h}$
$\displaystyle\leq\frac{\iota_{2}+\lambda\xi_{1}+0.5\iota_{1}+\sum_{h=1}^{H}\nu_{h}^{2}+2bK\sum_{h=1}^{H}\nu_{h}}{\lambda}+\frac{\lambda
H{\mathcal{C}}({\pi},{\epsilon})}{2K}+H{\epsilon}+\sum_{h=1}^{H}\nu_{h},$

where the second inequality uses the fact that ${\underline{Q}}^{t}_{h}$ is a
minimizer over ${\mathcal{F}}\ni{\mathrm{Proj}}_{{\mathcal{F}}}(Q^{\pi^{t}})$
of ${\mathcal{L}}_{\pi^{t}}(f)+\lambda f_{1}(s_{1},\pi^{t}_{1})$ (which has
the same minimizer as
${\mathcal{L}}_{\pi^{t}}(f)+\lambda\Delta_{1}f_{1}(s_{1},\pi^{t}_{1})$), and
the last inequality uses Lemma B.2, and here we define
$\iota_{2}:=36(e-2)b^{2}H\left(2d_{{\mathcal{F}}}({\epsilon})+d_{\Pi}({\epsilon},T)+\ln\frac{H}{\delta}\right)+6b(3b+4){\epsilon}KH+15bK\sum_{h=1}^{H}\xi_{h}$.
∎

##  Appendix D Proof of Theorem 3

In this appendix, we give our complete proof for Theorem 3. In order to
develop our argument for proving Theorem 3, we shall start with a generalized
form of posterior sampling in Section D.1 and develop our key support result
in 2. We then use 2 and the similar machinery developed in Appendix C to
complete our argument for proving Theorem 3.

###  D.1. Generalized form of posterior and 2

We start with recalling the posterior distribution defined in 1 of Algorithm 4
as

$\displaystyle\hat{p}(f|{\mathcal{D}},\pi)\propto\exp\left(-\lambda
f_{1}(s_{1},\pi_{1})\right)p_{0}(f)\prod_{h\in[H]}\frac{\exp\left(-\gamma\hat{L}_{\pi}(f_{h},f_{h+1})\right)}{{\mathbb{E}}_{f^{\prime}_{h}\sim
p_{0,h}}\exp\left(-\gamma\hat{L}_{\pi}(f^{\prime}_{h},f_{h+1})\right)}.$ (9)

Similar to the proof strategy in Dann et al. [2021], we now consider a
slightly more general form of the posterior distribution with an extra
parameter $\alpha\in[0,1]$ and in an equivalent but more useful form. In
concrete, consider any $\alpha\in[0,1]$ and define the potential functions:

$\displaystyle\widehat{\Phi}_{h}(f,\pi;{\mathcal{D}})$ $\displaystyle:=-\ln
p_{0}(f_{h})+\alpha\gamma\sum_{k=1}^{K}\Delta
L_{\tilde{\pi}}(f_{h},f_{h+1};z^{k}_{h})$
$\displaystyle+\alpha\ln{\mathbb{E}}_{\tilde{f}_{h}\sim
p_{0}}\exp\left(-\gamma\sum_{k=1}^{K}\Delta
L_{\tilde{\pi}}(f_{h},f_{h+1};z^{k}_{h})\right),$
$\displaystyle\widehat{\Phi}(f,\pi;{\mathcal{D}})$
$\displaystyle:=\sum_{h=1}^{H}\widehat{\Phi}_{h}(f,\pi;{\mathcal{D}}),$
$\displaystyle\Delta_{1}f_{1}(s_{1},\pi)$
$\displaystyle:=f_{1}(s_{1},\pi)-V_{1}^{\pi}(s_{1}).$

where recall that $\Delta L_{\tilde{\pi}}(f_{h},f_{h+1};z^{k}_{h})$ is defined
in Table 3. Define the generalized posterior distribution

$\displaystyle\hat{p}(f|{\mathcal{D}},\pi)$
$\displaystyle\propto\exp\left(-\widehat{\Phi}(f,\pi;{\mathcal{D}})-\lambda\Delta
f_{1}(s_{1},\pi)\right),$ (10)

where it is equivalent to the posterior defined in Equation 9 when $\alpha=1$.
We shall use Equation 10 for the posterior for the rest of this section. We
shall also define the complexity measure of this generalized posterior – a
counterpart to that of the canonical posterior form in 2.

######  Definition 7.

Define

$\displaystyle\kappa_{h}(\alpha,{\epsilon},\tilde{\pi})$
$\displaystyle:=(1-\alpha)\ln{\mathbb{E}}_{f_{h+1}\sim
p_{0}}\left[p_{0,h}\left({\mathcal{F}}_{h}^{\tilde{\pi}}({\epsilon};f_{h+1})\right)^{-\alpha/(1-\alpha)}\right],$

where recall that
${\mathcal{F}}_{h}^{\tilde{\pi}}({\epsilon};f_{h+1})=\\{f^{\prime}\in{\mathcal{F}}_{h}:\sup_{s,a}|{\mathcal{E}}_{h}^{\tilde{\pi}}(f^{\prime},f_{h+1})(s,a)|\leq{\epsilon}\\}$
which is defined in 2. Define the complexity measure

$\displaystyle d_{0}({\epsilon},\alpha)$
$\displaystyle:=\sup_{T\in{\mathbb{N}},\tilde{\pi}\in\Pi^{soft}(T)}\sum_{h=1}^{H}\kappa_{h}(\alpha,{\epsilon},\tilde{\pi}).$
(11)

Note that we have

$\displaystyle\lim_{\alpha\rightarrow 1^{-}}d_{0}({\epsilon},\alpha)$
$\displaystyle=d_{0}({\epsilon}).$

We now state our key milestone result – 2 to support the argument for proving
Theorem 3. The proof of 2 is deferred to Section D.3.

##### Notation ${\mathbb{E}}_{\tilde{\pi}\sim P_{t}(\cdot|{\mathcal{D}})}$.

Note that in Algorithm 4, each policy $\pi^{t}$ for $t\in[T]$ is a random
variable that depends on both the offline data ${\mathcal{D}}$ and the
randomization of sampling from the posteriors. That is, when conditioned on
the offline data ${\mathcal{D}}$, each $\pi_{t}$ is still a random variable.
We denote $P_{t}(\cdot|{\mathcal{D}})$ as the posterior distribution of
$\pi^{t}$ conditioned on ${\mathcal{D}}$. Note that for any $\tilde{\pi}\sim
P_{t}(\cdot|{\mathcal{D}})$ and any $t\in[T]$, we have
$\tilde{\pi}\in\Pi^{soft}(T)$.

######  Proposition 2.

For any $\gamma\in[0,\frac{1}{144(e-2)b^{2}}]$, ${\epsilon}>0$, $\delta>0$,
$\alpha\in(0,1]$, $T\in{\mathbb{N}}$, and any $t\in[T]$ and $\lambda>0$, we
have,

$\displaystyle{\mathbb{E}}_{{\mathcal{D}}}{\mathbb{E}}_{\tilde{\pi}\sim
P_{t}(\cdot|{\mathcal{D}})}{\mathbb{E}}_{f\sim\hat{p}(\cdot|{\mathcal{D}},\tilde{\pi})}\left[0.125\alpha\gamma
K\sum_{h=1}^{H}{\mathbb{E}}_{\mu}[{\mathcal{E}}^{\tilde{\pi}}_{h}(f_{h},f_{h+1})(s_{h},a_{h})^{2}]+\lambda\Delta
f_{1}(s_{1},\tilde{\pi})\right]$
$\displaystyle\lesssim\lambda{\epsilon}+\alpha\gamma
Hb^{2}\cdot\max\\{d_{{\mathcal{F}}}({\epsilon}),d_{\Pi}({\epsilon},T),\ln\frac{\ln
Kb^{2}}{\delta}\\}+\alpha\gamma b^{2}KH\cdot\max\\{{\epsilon},\delta\\}+\gamma
HK\frac{{\epsilon}^{2}}{\alpha}$
$\displaystyle+\sum_{h=1}^{H}\sup_{\tilde{\pi}_{h}\in\Pi_{h}^{soft}(T)}\kappa_{h}(\alpha,{\epsilon},\tilde{\pi}_{h})+\sup_{\tilde{\pi}\in\Pi^{soft}(T)}\sum_{h=1}^{H}\ln\frac{1}{p_{0}({\mathcal{F}}_{h}({\epsilon};Q^{\tilde{\pi}_{h}}_{h}))}.$

We now have all main components needed to construct our argument for proving
Theorem 3.

###  D.2. Proof of Theorem 3

###### Proof of Theorem 3.

We start with the error decomposition argument.

##### Step 1: Error decomposition.

Similar to the first step of the proof of Theorem 2, using Lemma A.4, we have

$\displaystyle\mathrm{SubOpt}_{\pi}^{M}(\pi^{t})$
$\displaystyle=\sum_{h=1}^{H}{\mathbb{E}}_{\pi}[{\mathcal{E}}_{h}^{\pi^{t}}({\underline{Q}}^{t}_{h},{\underline{Q}}^{t}_{h+1})(s_{h},a_{h})]+\Delta_{1}{\underline{Q}}_{1}(s_{1},\pi_{1}^{t})+\mathrm{SubOpt}_{\pi}^{M_{t}}(\pi^{t})$

where we denote $M_{t}:=M({\underline{Q}}^{t},\pi^{t})$ and
$\Delta_{1}{\underline{Q}}_{1}(s_{1},\pi^{t}):={\underline{Q}}_{1}(s_{1},\pi^{t})-V_{1}^{\pi^{t}}(s_{1})$.
Since term $\sum_{t=1}^{T}\mathrm{SubOpt}_{\pi}^{M_{t}}(\pi^{t})$ can be
controlled Lemma A.6, it remains to control

$\displaystyle J$
$\displaystyle:={\mathbb{E}}_{{\mathcal{D}}}\left[\sum_{h=1}^{H}{\mathbb{E}}_{\pi}[{\mathcal{E}}_{h}^{\pi^{t}}({\underline{Q}}^{t}_{h},{\underline{Q}}^{t}_{h+1})(s_{h},a_{h})]+\Delta_{1}{\underline{Q}}_{1}(s_{1},\pi_{1}^{t})\right]$
$\displaystyle={\mathbb{E}}_{{\mathcal{D}}}{\mathbb{E}}_{\tilde{\pi}\sim
P_{t}(\cdot|{\mathcal{D}})}{\mathbb{E}}_{f\sim\hat{p}(\cdot|\tilde{\pi},{\mathcal{D}})}\left[\sum_{h=1}^{H}{\mathbb{E}}_{\pi}[{\mathcal{E}}_{h}^{\tilde{\pi}}(f_{h},f_{h+1})(s_{h},a_{h})]+\Delta_{1}f_{1}(s_{1},\tilde{\pi}_{1})\right].$

##### Step 2: Decoupling argument.

Using Lemma A.5, we have

$\displaystyle\sum_{h=1}^{H}{\mathbb{E}}_{\pi}[{\mathcal{E}}_{h}^{\tilde{\pi}}(f_{h},f_{h+1})(s_{h},a_{h})]+\Delta_{1}f_{1}(s_{1},\tilde{\pi}_{1})$
$\displaystyle\leq\frac{0.125K\gamma}{\lambda}\sum_{h=1}^{H}\left({\mathbb{E}}_{\mu}[{\mathcal{E}}^{\tilde{\pi}}_{h}(f_{h},f_{h+1})(s_{h},a_{h})^{2}]+\nu_{h}^{2}+4b\nu_{h}\right)+\frac{0.5\lambda
H{\mathcal{C}}(\pi,{\epsilon}_{c})}{K\gamma}+\Delta_{1}f_{1}(s_{1},\tilde{\pi}_{1})$
$\displaystyle+H{\epsilon}_{c}+\sum_{h=1}^{H}\nu_{h}$
$\displaystyle=\frac{0.125K\gamma\sum_{h=1}^{H}{\mathbb{E}}_{\mu}[{\mathcal{E}}^{\tilde{\pi}}_{h}(f_{h},f_{h+1})(s_{h},a_{h})^{2}]+\lambda\Delta_{1}f_{1}(s_{1},\tilde{\pi}_{1})+\iota_{1}}{\lambda}+\frac{0.5\lambda
H{\mathcal{C}}(\pi,{\epsilon}_{c})}{K\gamma}$
$\displaystyle+H{\epsilon}_{c}+\sum_{h=1}^{H}\nu_{h}$

where
$\iota_{1}:=0.125K\gamma\left(\sum_{h=1}^{H}\nu_{h}^{2}+4b\sum_{h=1}^{H}\nu_{h}\right)$.

Applying 2, taking the limit $\alpha\rightarrow 1^{-}$, and re-organizing the
terms complete our proof.

∎

It remains to prove 2, which is the focus of the remaining appendix.

###  D.3. Proof of 2

Our proof strategy for 2 builds upon Dann et al. [2021] where the central idea
in the proof is to upper and lower bound the log-partition function – which in
our case is as follows:

$\displaystyle
Z_{t}:={\mathbb{E}}_{{\mathcal{D}}}{\mathbb{E}}_{\tilde{\pi}\sim
P_{t}(\cdot|{\mathcal{D}})}{\mathbb{E}}_{f\sim\hat{p}(\cdot|{\mathcal{D}},\tilde{\pi})}\left[\widehat{\Phi}(f,\tilde{\pi};{\mathcal{D}})+\lambda\Delta
f_{1}(s_{1},\tilde{\pi})+\ln\hat{p}(f|{\mathcal{D}},\tilde{\pi})\right],$ (12)

for any $t\in[T]$ and any $T\in{\mathbb{N}}$. The key technical distinction is
that we need to handle the statistical dependence induced by
${\mathbb{E}}_{\tilde{\pi}\sim P_{t}(\cdot|{\mathcal{D}})}$ – which is absent
in Dann et al. [2021]. In concrete, when $\tilde{\pi}$ depends on
${\mathcal{D}}$, then

$\displaystyle{\mathbb{E}}\Delta
L_{h}^{\tilde{\pi}}(f_{h},f_{h+1})(s_{h}^{k},a^{k}_{h})\neq{\mathcal{E}}_{h}^{\tilde{\pi}}(f_{h},f_{h+1})(s^{k}_{h},a^{k}_{h})^{2},$

since $\tilde{\pi}$ depends on $(s_{h}^{k},a^{k}_{h})$. We develop an
machinery to handle such issue in posterior sampling by carefully controlling
the variance of the variable of interest (thus we can leverage the variance-
dependent concentration inequality in Lemma A.2) and integrating it into
posterior sampling using a uniform convergence argument. Roughly speaking,
several milestone results during the process of developing our proof argument,
we need to bound the form of

$\displaystyle{\mathbb{E}}_{{\mathcal{D}}}{\mathbb{E}}_{\tilde{\pi}\sim
P_{t}(\cdot|{\mathcal{D}})}{\mathbb{E}}_{f\sim\hat{p}(\cdot|{\mathcal{D}},\tilde{\pi})}\left[S(f,\tilde{\pi},{\mathcal{D}})\right]$

where $S(f,\tilde{\pi},{\mathcal{D}})$ is a function of
$f,\tilde{\pi},{\mathcal{D}}$. It is useful to view
$S(f,\tilde{\pi},{\mathcal{D}})$ as a stochastic process indexed by
$(f,\tilde{\pi})$. In our machinery, we shall first construct an upper bound
on the variance of the random process, namely

$\displaystyle
V(f,\tilde{\pi})\geq{\mathbb{E}}_{{\mathcal{D}}}[S(f,\tilde{\pi},{\mathcal{D}})^{2}].$

Using a discretization argument, the union bound and Lemma A.2, we have with
probability at least $1-\delta$, for any
$f\in{\mathcal{F}},\tilde{\pi}\in\Pi^{soft}(T)$, for any $t\in[0,\frac{1}{\sup
S(f,\tilde{\pi},{\mathcal{D}})}]$, we have

$\displaystyle S(f,\tilde{\pi},{\mathcal{D}})\leq
O_{K}(1)+{\mathbb{E}}_{{\mathcal{D}}}\left[S(f,\tilde{\pi},{\mathcal{D}})\right]+(e-2)t{\mathbb{E}}_{{\mathcal{D}}}[S(f,\tilde{\pi},{\mathcal{D}})^{2}]+\frac{\ln(N/\delta)}{t}$

where $O_{K}(1)$ is a discretization error that can be controlled, and $N$ is
a covering number of ${\mathcal{F}}\times\Pi^{soft}(T)$. Note that
$S(f,\tilde{\pi},{\mathcal{D}})$ often involves the squared loss which
satisfies the Bernstein condition (see Lemma F.1) – thus we can roughly bound
${\mathbb{E}}_{{\mathcal{D}}}[S(f,\tilde{\pi},{\mathcal{D}})^{2}]\leq\alpha|{\mathbb{E}}_{{\mathcal{D}}}\left[S(f,\tilde{\pi},{\mathcal{D}})\right]|$
for some constant $\alpha$. To integrate the high-probability bound into in-
expected bound, we use the argument:

$\displaystyle{\mathbb{E}}_{{\mathcal{D}}}{\mathbb{E}}_{\tilde{\pi}\sim
P_{t}(\cdot|{\mathcal{D}})}{\mathbb{E}}_{f\sim\hat{p}(\cdot|{\mathcal{D}},\tilde{\pi})}\left[S(f,\tilde{\pi},{\mathcal{D}})\right]\leq
O_{K}(1)+{\mathbb{E}}_{{\mathcal{D}}}{\mathbb{E}}_{\tilde{\pi}\sim
P_{t}(\cdot|{\mathcal{D}})}{\mathbb{E}}_{{\mathcal{D}}}\left[S(f,\tilde{\pi},{\mathcal{D}})\right]$
$\displaystyle+(e-2)t{\mathbb{E}}_{{\mathcal{D}}}{\mathbb{E}}_{\tilde{\pi}\sim
P_{t}(\cdot|{\mathcal{D}})}{\mathbb{E}}_{{\mathcal{D}}}[S(f,\tilde{\pi},{\mathcal{D}})^{2}]+\frac{\ln(N/\delta)}{t}+\delta\sup
S(f,\tilde{\pi},{\mathcal{D}}).$

####  D.3.1. Lower-bounding log-partition function.

In this appendix, we give a lower bound of the log-partition function defined
in Equation 12. The final lower bound is presented in 3. In order to establish
such a lower bound, we first present a series of support lemmas that will
culminate into 3.

The following lemma decomposes the log-partition function $Z$ into different
terms that we shall control separately.

######  Lemma D.1.

For any $t\in[T]$ and any $T\in{\mathbb{N}}$, we have

$\displaystyle
Z_{t}\geq\underbrace{{\mathbb{E}}_{{\mathcal{D}}}{\mathbb{E}}_{\tilde{\pi}\sim
P_{t}(\cdot|{\mathcal{D}})}{\mathbb{E}}_{f\sim\hat{p}(\cdot|{\mathcal{D}},\tilde{\pi})}\left[\lambda\Delta
f_{1}(s_{1},\tilde{\pi})+(1-0.5\alpha)\ln\frac{\hat{p}(f_{1}|{\mathcal{D}},\tilde{\pi})}{p_{0}(f_{1})}\right]}_{A_{t}}$
$\displaystyle+0.5\alpha\sum_{h=1}^{H}\underbrace{{\mathbb{E}}_{{\mathcal{D}}}{\mathbb{E}}_{\tilde{\pi}\sim
P_{t}(\cdot|{\mathcal{D}})}{\mathbb{E}}_{f\sim\hat{p}(\cdot|{\mathcal{D}},\tilde{\pi})}\left[2\gamma\sum_{k=1}^{K}\Delta
L_{\tilde{\pi}}(f_{h},f_{h+1};z^{k}_{h})+\ln\frac{\hat{p}(f_{h},f_{h+1}|{\mathcal{D}},\tilde{\pi})}{p_{0}(f_{h},f_{h+1})}\right]}_{B_{h,t}}+$
$\displaystyle\sum_{h=1}^{H}\underbrace{{\mathbb{E}}_{{\mathcal{D}}}{\mathbb{E}}_{\tilde{\pi}\sim
P_{t}(\cdot|{\mathcal{D}})}{\mathbb{E}}_{f\sim\hat{p}(\cdot|{\mathcal{D}},\tilde{\pi})}\left[\alpha\ln{\mathbb{E}}_{f^{\prime}_{h}\sim
p_{0}}\exp\left(-\gamma\sum_{k=1}^{K}\Delta
L_{\tilde{\pi}}(f^{\prime}_{h},f_{h+1};z^{k}_{h})\right)+(1-\alpha)\ln\frac{\hat{p}(f_{h+1}|{\mathcal{D}},\tilde{\pi})}{p_{0}(f_{h+1})}\right]}_{C_{h,t}}.$

###### Proof of Lemma D.1.

This is a simple adaptation of the decomposition in [Dann et al., 2021, Lemma
6]. ∎

We now control each term of the above decomposition of $Z$ separately – where
a majority of these steps are where our technical arguments depart from those
in Dann et al. [2021]. In particular, Lemma D.4, Lemma D.5, and Lemma D.7 are
our _new_ technical results.

##### Bounding $A_{t}$.

######  Lemma D.2.

We have

$\displaystyle
A_{t}\geq\lambda{\mathbb{E}}_{{\mathcal{D}}}{\mathbb{E}}_{\tilde{\pi}\sim
P_{t}(\cdot|{\mathcal{D}})}{\mathbb{E}}_{f\sim\hat{p}(\cdot|{\mathcal{D}},\tilde{\pi})}\Delta
f_{1}(s_{1},\tilde{\pi}).$

###### Proof of Lemma D.2.

It simply follows from that:

$\displaystyle{\mathbb{E}}_{{\mathcal{D}}}{\mathbb{E}}_{\tilde{\pi}\sim
P_{t}(\cdot|{\mathcal{D}})}{\mathbb{E}}_{f\sim\hat{p}(\cdot|{\mathcal{D}},\tilde{\pi})}\left[(1-0.5\alpha)\ln\frac{\hat{p}(f_{1}|{\mathcal{D}},\tilde{\pi})}{p_{0}(f_{1})}\right]=(1-0.5\alpha)D_{\mathrm{KL}}[\hat{p}(\cdot|{\mathcal{D}},{\tilde{\pi}})\|p_{0}]\geq
0.$

∎

##### Bounding $B_{h,t}$.

######  Lemma D.3.

For any $f,\tilde{\pi}$, $0\leq\gamma\leq\frac{1}{72(e-2)b^{2}}$, and
$h\in[H]$, we have

$\displaystyle\ln{\mathbb{E}}_{(s_{h+1},r_{h})\sim
P_{h}(\cdot|s_{h},a_{h})}\exp\left(-2\gamma\Delta
L_{\tilde{\pi}}(f_{h},f_{h+1};z_{h})\right)\leq-2\gamma(1-72(e-2)\gamma
b^{2}){\mathcal{E}}_{h}^{\tilde{\pi}}(f_{h},f_{h+1})(s_{h},a_{h})^{2}.$

###### Proof of Lemma D.3.

For simplicity, we write ${\mathbb{E}}={\mathbb{E}}_{(s_{h+1},r_{h})\sim
P_{h}(\cdot|s_{h},a_{h})}$. We have

$\displaystyle\ln{\mathbb{E}}\exp\left(-2\gamma\Delta
L_{{\tilde{\pi}}}(f_{h},f_{h+1};z_{h})\right)$
$\displaystyle\leq{\mathbb{E}}\exp\left(-2\gamma\Delta
L_{{\tilde{\pi}}}(f_{h},f_{h+1};z_{h})\right)-1$
$\displaystyle\leq-2\gamma{\mathbb{E}}\Delta
L_{{\tilde{\pi}}}(f_{h},f_{h+1};z_{h})+(e-2)4\gamma^{2}{\mathbb{E}}\Delta
L_{{\tilde{\pi}}}(f_{h},f_{h+1};z_{h})^{2}$
$\displaystyle\leq-2\gamma(1-(e-2)2\gamma
36b^{2}){\mathcal{E}}^{2}_{h}(f_{h},f_{h+1},\tilde{\pi})(s_{h},a_{h})$

where the first inequality uses $\ln x\leq x-1,\forall x\geq 0$, the second
inequality uses $e^{x}\leq 1+x+(e-2)x^{2},\forall|x|\leq 1$ and
$|2\gamma{\mathbb{E}}\Delta L_{{\tilde{\pi}}}(f_{h},f_{h+1};z_{h})|\leq
18\gamma b^{2}\leq 1$, the third inequality uses Lemma A.1 and
$\gamma\leq\frac{1}{72(e-2)b^{2}}$. ∎

######  Lemma D.4.

Define the random variable

$\displaystyle\xi_{h}^{\tilde{\pi}}(f_{h},f_{h+1};z_{h})$
$\displaystyle:=-2\gamma\Delta
L_{\tilde{\pi}}(f_{h},f_{h+1};z_{h})-\ln{\mathbb{E}}_{(s_{h+1},r_{h})\sim
P_{h}(\cdot|s_{h},a_{h})}\exp\left(-2\gamma\Delta
L_{\tilde{\pi}}(f_{h},f_{h+1};z_{h})\right).$

For any $\gamma\in[0,\frac{1}{144(e-2)b^{2}}]$, $t\in[0,\frac{1}{26\gamma
b^{2}}]$, ${\epsilon}>0$, $\delta>0$, $T\in{\mathbb{N}}$ with probability at
least $1-\delta$, it holds uniformly over all
$\tilde{\pi}\in\Pi^{soft}(T),f_{h}\in{\mathcal{F}}_{h},f_{h+1}\in{\mathcal{F}}_{h+1}$
that

$\displaystyle\sum_{k=1}^{K}\xi_{h}^{\tilde{\pi}}(f_{h},f_{h+1};z_{h}^{k})\leq
D+c\sum_{k=1}^{K}e_{k}^{2},$

where

$\displaystyle\begin{cases}D&:=120\gamma
b(b+2)K{\epsilon}+\frac{2d_{{\mathcal{F}}}({\epsilon})+d_{\Pi}({\epsilon},T)+\ln(1/\delta)}{t},\\\
c&:=320b^{2}\gamma^{2}(e-2)t,\\\
e_{k}&:={\mathcal{E}}_{h}^{\tilde{\pi}}(f_{h},f_{h+1})(s^{k}_{h},a^{k}_{h}).\end{cases}$
(13)

###### Proof of Lemma D.4.

For simplicity, denote

$\displaystyle\begin{cases}u_{k}&:=\ln{\mathbb{E}}_{(s_{h+1},r_{h})\sim
P_{h}(\cdot|s_{h},a_{h})}\exp\left(-2\gamma\Delta
L_{\tilde{\pi}}(f_{h},f_{h+1};z^{k}_{h})\right),\\\ v_{k}&:=-2\gamma\Delta
L_{\tilde{\pi}}(f_{h},f_{h+1};z^{k}_{h}),\\\ w_{k}&:=v_{k}-u_{k},\\\
e_{k}&:={\mathcal{E}}_{h}^{\tilde{\pi}}(f_{h},f_{h+1})(s^{k}_{h},a^{k}_{h}).\end{cases}$
(14)

We have

$\displaystyle u_{k}$ $\displaystyle\geq{\mathbb{E}}_{(s_{h+1},r_{h})\sim