# Provable Offline Reinforcement Learning
with Human Feedback

Wenhao Zhan 111The first two authors contributed equally. Masatoshi Uehara
11footnotemark: 1 Nathan Kallus
Jason D. Lee Wen Sun Princeton University. Email:
<EMAIL_ADDRESS>University. Email<EMAIL_ADDRESS>University. Email<EMAIL_ADDRESS>University. Email:
<EMAIL_ADDRESS>University. Email<EMAIL_ADDRESS>
###### Abstract

In this paper, we investigate the problem of offline reinforcement learning
with human feedback where feedback is available in the form of preference
between trajectory pairs rather than explicit rewards. Our proposed algorithm
consists of two main steps: (1) estimate the implicit reward using Maximum
Likelihood Estimation (MLE) with general function approximation from offline
data and (2) solve a distributionally robust planning problem over a
confidence set around the MLE. We consider the general reward setting where
the reward can be defined over the whole trajectory and provide a novel
guarantee that allows us to learn any target policy with a polynomial number
of samples, as long as the target policy is covered by the offline data. This
guarantee is the first of its kind with general function approximation. To
measure the coverage of the target policy, we introduce a new single-policy
concentrability coefficient, which can be upper bounded by the per-trajectory
concentrability coefficient. We also establish lower bounds that highlight the
necessity of such concentrability and the difference from standard RL, where
state-action-wise rewards are directly observed. We further extend and analyze
our algorithm when the feedback is given over action pairs.

##  1 Introduction

In standard reinforcement learning (RL) setting, the agent learns to maximize
an observed numerical reward signal. However, finding appropriate numerical
rewards can often be challenging in practice, and getting rewards right
significantly impacts the effectiveness of RL algorithms (Wirth et al.,,
2017). To address this challenge, preference-based RL with human feedback
(RLHF) has emerged as a promising alternative (Christiano et al.,, 2017). In
RLHF, the agent does not receive a numerical reward signal, but rather
feedback from a human expert in the form of _preferences_ for a state-action
trajectory in given pairs of trajectories. RLHF has gained considerable
attention across multiple application domains, including games (MacGlashan et
al.,, 2017; Christiano et al.,, 2017; Warnell et al.,, 2018), large language
models (Ziegler et al.,, 2019; Stiennon et al.,, 2020; Wu et al.,, 2021;
Nakano et al.,, 2021; Ouyang et al.,, 2022; Glaese et al.,, 2022; Bai et al.,,
2022; Ramamurthy et al.,, 2022; Liu et al.,, 2023), and robot learning (Brown
et al.,, 2019; Shin et al.,, 2023).

In this work, we focus on the problem of offline RLHF, where the learning
process relies exclusively on pre-collected offline data without active
interaction with the environment. Offline RL has gained significant attention
in various applications where conducting real-time online experiments may be
costly. In the context of RLHF, an offline setting is particularly relevant
due to the high cost and latency associated with obtaining human feedback. One
of the key challenges in offline RL is the limited coverage of available
offline data. Since coverage of the entire state-action space is rarely
feasible in practice (Chen and Jiang,, 2019), recent empirical and theoretical
approaches to offline RL leverage pessimism so as to rely only on the coverage
of one comparator policy (possibly the optimal one), _i.e._ , the so-called
partial coverage condition (Yu et al.,, 2020; Kidambi et al.,, 2020;
Rashidinejad et al., 2021a, ; Li et al., 2022a, ; Shi et al.,, 2022; Yin and
Wang,, 2021; Xie et al.,, 2021; Uehara and Sun,, 2021; Zhan et al., 2022a, ).
In the context of RLHF, it is also crucial to develop algorithms that work
under the partial coverage condition.

Despite its significance, there are very few algorithms specifically designed
for offline RLHF with strong statistical guarantees. In this work, we provide
such algorithms and guarantees when preferences depend on unknown reward
functions over trajectories. Notably, we consider general reward functions
that can be defined over the whole trajectory rather than just state-action
pairs. This is consistent with many practical settings in natural language
processing. For instance, all benchmarks presented in RL4LM (Ramamurthy et
al.,, 2022) use metrics defined over the entire trajectories. Our main
contributions can be summarized as follows:

  * •

We propose a simple algorithm with general function approximation that
consists of two main steps: (1) estimate the implicit reward using Maximum
Likelihood Estimation (MLE) with general function approximation from offline
data and (2) solve a distributionally robust planning problem over a
confidence set around the MLE.

  * •

We prove that our algorithm can effectively compete with a target policy as
long as the offline data cover the target policy. Our analysis leverages a
newly defined concentrability coefficient which is tailored to RLHF. As the
concentrability coefficient differs from that in the standard RL setting where
state-action-wise rewards are directly observed, we establish lower bounds
that highlight the necessity of our partial coverage condition.

  * •

We extend the algorithm to the setting where the transition kernel is unknown,
where we not only construct confidence sets for the reward function but also
for the system dynamics. Notably, even though the reward can be trajectory-
wise, we only need to estimate the per-step transition dynamics to ensure
efficient learning.

  * •

We further extend our results to the action-based comparison model, where
preferences are defined over individual actions instead of entire trajectories
based on the advantage function of the optimal policy (Ramachandran and Amir,,
2007; Zhu et al.,, 2023). In comparison to the case of the trajectory-wise
comparison model, we can establish a partial coverage guarantee using a
concentrability coefficient on pairs of state-action pairs rather than
trajectories. In this scenario, our sample complexity only scales with a bound
on the advantage function, which can be much smaller than a bound on per-
trajectory rewards, a common assumption that is widely used in the imitation
learning literature (Ross et al.,, 2011; Sun et al.,, 2017; Agarwal et al.,,
2019).

##  2 Related Work

Reinforcement learning from human feedback. The closest work to ours is Zhu et
al., (2023), which also studies offline RLHF, but their algorithm and analysis
are restricted to linear models. Our algorithm and analysis extend to general
function approximation. Indeed, general classes such as neural networks are
commonly employed in practice (Christiano et al.,, 2017; Abdelkareem et al.,,
2022). In the special case of linear rewards and preferences over
trajectories, while our algorithms differ, our guarantees generalize theirs.
see Section 4 for more discussion. Moreover, they only consider the setting
where the transition kernel is known, while our work can also handle unknown
transitions. Finally, in the case of action-based preferences, Zhu et al.,
(2023) cannot provide guarantees with partial coverage, even under their
restriction to linear models. We demonstrate how to achieve meaningful
guarantees under partial coverage and a soft margin (Assumption 6).

Wirth et al., (2017) provide a survey of Preference-based RL (PbRL). PbRL has
received considerable attention in theoretical RL (Yue et al.,, 2012;
Novoseller et al.,, 2020; Xu et al.,, 2020; Pacchiano et al.,, 2021; Chen et
al.,, 2022) but the focus is largely on online PbRL. To the best of our
knowledge, Zhu et al., (2023) is the only previous work to provide theoretical
guarantees for offline PbRL.

#### Offline RL.

In offline RL, one of the most critical challenges is addressing the issue of
insufficient coverage in the offline data. It is well-known that naive methods
are unable to learn the optimal policy in such scenarios (Rashidinejad et al.,
2021b, ). To tackle this problem, numerous algorithms have been proposed with
theoretical guarantees (Liu et al.,, 2020; Kumar et al.,, 2020; Jin et al.,,
2021; Rashidinejad et al., 2021b, ; Uehara and Sun,, 2021; Li et al., 2022b, ;
Shi et al.,, 2022; Jin et al.,, 2020; Xie et al.,, 2021; Zhan et al., 2022a,
). The most relevant work is Uehara and Sun, (2021), which focuses on offline
model-based RL with general function approximation. However, their methods
cannot be directly applied to RLHF since per-step rewards are not observable
in our setting. Furthermore, even in the standard RL setting, the construction
of confidence intervals differs between our approach and theirs. Another
related paper is Cheng et al., (2022), which also considers pessimistic model-
based offline RL. Cheng et al., (2022) differs from Uehara and Sun, (2021) by
incorporating a term related to a reference policy into the objective function
to ensure that the learned policy can at least outperform the reference
policy. We also introduce a reference policy in our algorithms, however, our
motivations for such reference policies is more than just being able to
compete against the reference policy. Additional detailed comparisons are
given in Section 4.1 and Remark 1.

##  3 Preliminaries

We first introduce our offline RLHF setting with general function
approximation.

#### Markov decision processes.

We consider an episodic time-inhomogeneous Markov Decision Process (MDP)
denoted by $\mathcal{M}$, which consists of a state space ${\mathcal{S}}$, an
action space $\mathcal{A}$, an initial state distribution
$P_{0}^{\star}\in\Delta_{{\mathcal{S}}}$, and a horizon $H\in\mathbb{N}^{+}$.
At each step $h\in[H-1]$, we use
$P^{\star}_{h}:{\mathcal{S}}\times\mathcal{A}\to\Delta_{{\mathcal{S}}}$ to
denote the ground truth transitions. The ground truth reward function for the
entire trajectory is denoted by
$r^{\star}:{\mathcal{T}}\to[0,r_{\mathrm{max}}]$, where
${\mathcal{T}}=({\mathcal{S}}\times\mathcal{A})^{H}$ represents the set of all
possible trajectories. Note that $r^{\star}$ is a trajectory-wise reward,
which is more general than state-action-wise rewards commonly considered in
standard RL, which is the special case where for some
$\\{r^{\star}_{h}\\}_{h=1}^{H}$ we have
$r^{\star}(\tau)=\sum_{h=1}^{H}r^{\star}_{h}(s_{h},a_{h})$ for a trajectory
$\tau=(s_{1},a_{1},\cdots,s_{H},a_{H})$.

A history-dependent policy $\pi:=\\{\pi_{h}\\}_{h=1}^{H}$ is characterized by
$\pi_{h}:({\mathcal{S}}\times\mathcal{A})^{h-1}\times{\mathcal{S}}\to\Delta_{\mathcal{A}}$,
specifying the probability of selecting actions for the agent at each step
$h\in[H]$ based on the entire history. We denote the set of all such history-
dependent policies as $\Pi_{\mathrm{his}}$. Given a policy $\pi$, we define
its expected reward with respect to a general reward function $r$ and initial
and transition distributions $P=\\{P_{h}\\}_{h=0}^{H-1}$ as
$J(\pi;r,P):=\mathbb{E}_{\tau\sim(\pi,P)}[r(\tau)]$. Here,
$\mathbb{E}_{\tau\sim(\pi,P)}[\cdot]$ represents the expectation over the
trajectory distribution when executing the policy $\pi$ under the transition
$P$ starting from $P_{0}$. We use $\mathbb{E}_{\tau\sim\pi}[\cdot]$ or
$\mathbb{E}_{\pi}[\cdot]$ to denote the special case when $P$ is the ground
truth distribution $P^{\star}:=\\{P^{\star}_{h}\\}_{h=0}^{H-1}$.

The optimal policy, denoted $\pi^{\star}$, is the policy that maximizes the
expected reward with respect to the true reward $r^{\star}$ and system
dynamics $P^{\star}$, _i.e._ ,
$\pi^{\star}:=\arg\max_{\pi\in\Pi_{\mathrm{his}}}J(\pi;r^{\star},P^{\star})$.
As the true reward function $r^{\star}$ is dependent on the entire trajectory,
the optimal policy $\pi^{\star}$ is generally history-dependent. Thus,
designing offline RLHF algorithms that can learn history-dependent policies is
crucial.

For any policy $\pi$, we can define its state-action visitation measure as
follows: $d^{\pi}_{h}(s,a)=\mathbb{P}^{\pi,P^{\star}}(s_{h}=s,a_{h}=a),\forall
h\in[H],$ where $\mathbb{P}^{\pi,P^{\star}}(\cdot)$ denotes the distribution
of the trajectory when executing policy $\pi$ in $P^{\star}$. We will also use
$d^{\pi}(\tau)$ to denote $\mathbb{P}^{\pi,P^{\star}}(\tau)$ for the whole
trajectory $\tau$.

A policy is Markovian if at each step it depends solely on the current state.
When the reward is state-action-wise and the policy is Markovian, we can
define the associated V- and Q-functions as
$V^{\pi}_{h}(s)=\mathbb{E}_{\pi}[\sum_{t=h}^{H}r^{\star}_{t}(s_{t},a_{t})|s_{h}=s],\forall
h\in[H],Q^{\pi}_{h}(s,a)=\mathbb{E}_{\pi}[\sum_{t=h}^{H}r^{\star}_{t}(s_{t},a_{t})|s_{h}=s,a_{h}=a],\,\forall
h\in[H].$ It is well-known that when the reward is state-action-wise, the
optimal policy $\pi^{\star}$ is both Markovian and deterministic. Furthermore,
we have $V^{\pi^{\star}}_{h}(s)=\sup_{\pi}V^{\pi}_{h}(s)$ and
$Q^{\pi^{\star}}_{h}(s,a)=\sup_{\pi}Q^{\pi}_{h}(s,a)$ for all $h\in[H]$. For
brevity, we will use $V^{\star}$ and $Q^{\star}$ to represent the optimal
state-value function and Q-function, respectively. The advantage function of
the optimal policy, denoted by $A^{\star}$, is defined to be
$A^{\star}_{h}(s,a)=Q^{\star}_{h}(s,a)-V^{\star}_{h}(s)$ for all
$h\in[H],s\in{\mathcal{S}},A\in\mathcal{A}$.

#### Offline reinforcement learning with human feedback.

We focus on the problem of offline RLHF in this work. Specifically, in the
trajectory-based pairwise comparison setting, we are provided with an offline
dataset $\mathcal{D}=\\{\tau^{n,0},\tau^{n,1},o^{n}\\}_{n=1}^{N}$, where
$\tau^{n,0}=\\{s^{n,0}_{h},a^{n,0}_{h}\\}_{h=1}^{H}$ and
$\tau^{n,1}=\\{s^{n,1}_{h},a^{n,1}_{h}\\}_{h=1}^{H}$ are i.i.d. sampled from
the distributions $\mu_{0}$ and $\mu_{1}$, respectively, and
$o^{n}\in\\{0,1\\}$ indicates preference for $\tau^{n,1}$ over $\tau^{n,2}$.
We assume it satisfies the following preference model:

######  Assumption 1 (Preference-based model).

Given a pair of trajectories $(\tau^{0},\tau^{1})$, $o\in\\{0,1\\}$ satisfies

$\displaystyle P(o=1\mid\tau_{0},\tau_{1})=P(\text{$\tau_{1}$ is preferred
over
$\tau_{0}$}\mid\tau_{0},\tau_{1})=\Phi(r^{\star}(\tau_{1})-r^{\star}(\tau_{0})).$

where $\Phi:\mathbb{R}\to[0,1]$ is a monotonically increasing link function.

A commonly used link function is the sigmoid function
$\sigma(x)=1/\\{1+\exp(-x)\\}$, leading to the Bradley-Terry-Luce (BTL) model
(Christiano et al.,, 2017).

The objective of offline RLHF is to learn a high-quality policy
$\widehat{\pi}\in\Pi_{\mathrm{his}}$, _i.e._ , with
$J(\pi_{\mathrm{tar}};r^{\star},P^{\star})-J(\widehat{\pi};r^{\star},P^{\star})\leq\epsilon$
where $\pi_{\mathrm{tar}}$ is a target policy we want to compete with
(potentially $\pi^{\star}$).

#### General function approximation.

In our paper, we estimate the reward $r^{\star}$ with general function
approximation. We introduce a function class $\mathcal{G}_{r}$, such as linear
functions or neural networks, to approximate the true reward. For each
$r\in\mathcal{G}_{r}$ and trajectory pair $(\tau^{0},\tau^{1})$, we denote the
induced preference model with respect to $r$ as $P_{r}(o|\tau^{0},\tau^{1})$,
defined as

$\displaystyle
P_{r}(o=1\mid\tau^{0},\tau^{1}):=\Phi(r(\tau^{1})-r(\tau^{0})).$ (1)

We use bracketing numbers to measure the complexity of
$\\{P_{r}:r\in\mathcal{G}_{r}\\}$.

######  Definition 1 ($\epsilon$-bracketing number of preferences).

We say $(g^{1},g^{2})$ is an $\epsilon$-bracket if
$g^{1}(\cdot\mid\tau^{0},\tau^{1})\leq g^{2}(\cdot\mid\tau^{0},\tau^{1})$ and
$\|g^{1}(\cdot\mid\tau^{0},\tau^{1})-g^{2}(\cdot\mid\tau^{0},\tau^{1})\|_{1}\leq\epsilon$
for all trajectory-pairs $(\tau^{0},\tau^{1})$. The $\epsilon$-bracketing
number of $\mathcal{G}_{r}$, denoted by
$\mathcal{N}_{\mathcal{G}_{r}}(\epsilon)$, is the minimal number of
$\epsilon$-brackets $(g^{n,1},g^{n,2})_{n=1}^{N}$ needed so that for any
$r\in\mathcal{G}_{r}$ there is a bracket $i\in[N]$ containing it, meaning
$g^{i,1}(\cdot|\tau^{0},\tau^{1})\leq P_{r}(\cdot|\tau^{0},\tau^{1})\leq
g^{i,2}(\cdot|\tau^{0},\tau^{1})$ for all trajectory-pairs
$(\tau^{0},\tau^{1})$.

The $\epsilon$-bracket number is widely used in statistics (van de Geer,,
2000) to study MLE and related M-estimates. One example for which we can bound
the $\epsilon$-bracket number is linear rewards under the BTL model (Pacchiano
et al.,, 2021; Zhu et al.,, 2023).

######  Proposition 1.

Suppose $\|\phi(\tau)\|_{2}\leq R$ $\forall\tau\in{\mathcal{T}}$,
$\mathcal{G}_{r}\subseteq\\{\tau\mapsto\langle\phi(\tau),\theta\rangle:\|\theta\|_{2}\leq
B\\}$ for some featurization $\phi:{\mathcal{T}}\to\mathbb{R}^{d}$ and $B>0$,
and the link function is $\Phi(\cdot)=\sigma(\cdot)$. Then for any
$\epsilon\leq 1$,
$\log\mathcal{N}_{\mathcal{G}_{r}}(\epsilon)\leq\mathcal{O}(d\log\frac{BR}{\epsilon}).$

The proof is deferred to Appendix A. To handle unknown transitions and action-
based comparison, we use function classes
$\\{\mathcal{G}_{P_{h}}\\}_{h=0}^{H-1}$ to approximate the transition
probabilities $\\{P^{\star}_{h}\\}_{0=1}^{H-1}$ and
$\\{\mathcal{G}_{A_{h}}\\}_{h=1}^{H}$ for advantage function approximation.
Similarly, we can define their bracket number as follows. Note that
$P_{A_{h}}(\cdot\mid s,a^{0},a^{1})$ is defined as $P_{A_{h}}(o=1\mid
s,a^{0},a^{1}):=\Phi(A_{h}(s,a^{1})-A_{h}(s,a^{0}))$ and $P_{A_{h}}(o=0\mid
s,a^{0},a^{1}):=1-\Phi(A_{h}(s,a^{1})-A_{h}(s,a^{0}))$.

######  Definition 2 ($\epsilon$-bracket number of transition probability
classes).

Suppose $f^{1},f^{2}$ is a function with
$f^{1}(\cdot|s,a),f^{2}(\cdot|s,a)\in\mathbb{R}^{|{\mathcal{S}}|}$ for all
$(s,a)\in{\mathcal{S}}\times\mathcal{A}$. Then we say $(f^{1},f^{2})$ is a
$\epsilon$-bracket if $f^{1}(\cdot|s,a)\leq f^{2}(\cdot|s,a)$ and
$\|f^{1}(\cdot|s,a)-f^{2}(\cdot|s,a)\|_{1}\leq\epsilon$ for all $(s,a)$. The
$\epsilon$-bracket number of a transition probability class
$\mathcal{G}_{P_{h}}$ where $h\in[H-1]$ is the minimum integer $N$ satisfying
that there exist $N$ $\epsilon$-brackets $(f^{n,1},f^{n,2})_{n=1}^{N}$ such
that for any function $P_{h}\in\mathcal{G}_{P_{h}}$ there is a bracket
$(f^{i,1},f^{i,2})$ where $i\in[N]$ containing it, i.e.,
$f^{i,1}(\cdot|s,a)\leq P_{h}(\cdot|s,a)\leq f^{i,2}(\cdot|s,a)$ for all
$(s,a)$.

######  Definition 3 ($\epsilon$-bracket number of initial state distribution
classes).

Suppose $f^{1},f^{2}\in\mathbb{R}^{|{\mathcal{S}}|}$. Then we say
$(f^{1},f^{2})$ is a $\epsilon$-bracket if $f^{1}\leq f^{2}$ and
$\|f^{1}-f^{2}\|_{1}\leq\epsilon$. The $\epsilon$-bracket number of a initial
state distribution class $\mathcal{G}_{P_{0}}$ is the minimum integer $N$
satisfying that there exist $N$ $\epsilon$-brackets
$(f^{n,1},f^{n,2})_{n=1}^{N}$ such that for any $P_{0}\in\mathcal{G}_{P_{0}}$
there is a bracket $(f^{i,1},f^{i,2})$ where $i\in[N]$ containing it, i.e.,
$f^{i,1}\leq P_{0}\leq f^{i,2}$.

######  Definition 4 ($\epsilon$-bracket number of advantage function
classes).

Suppose $g^{1},g^{2}$ is a function with
$g^{1}(\cdot|s,a^{0},a^{1}),g^{2}(\cdot|s,a^{0},a^{1})\in\mathbb{R}^{2}$ for
all $(s,a^{0},a^{1})\in{\mathcal{S}}\times\mathcal{A}\times\mathcal{A}$. Then
we say $(g^{1},g^{2})$ is a $\epsilon$-bracket if
$g^{1}(\cdot|s,a^{0},a^{1})\leq g^{2}(\cdot|s,a^{0},a^{1})$ and
$\|g^{1}(\cdot|s,a^{0},a^{1})-g^{2}(\cdot|s,a^{0},a^{1})\|_{1}\leq\epsilon$
for all $(s,a^{0},a^{1})\in{\mathcal{S}}\times\mathcal{A}\times\mathcal{A}$.
The $\epsilon$-bracket number of the class $\mathcal{G}_{A_{h}}$ where
$h\in[H]$ is the minimum integer $N$ satisfying that there exist $N$
$\epsilon$-brackets $(g^{n,1},g^{n,2})_{n=1}^{N}$ such that for any function
$A_{h}\in\mathcal{G}_{A_{h}}$ there is a bracket $(g^{i,1},g^{i,2})$ where
$i\in[N]$ containing it, i.e., $g^{i,1}(\cdot|s,a^{0},a^{1})\leq
P_{A_{h}}(\cdot|s,a^{0},a^{1})\leq g^{i,2}(\cdot|s,a^{0},a^{1})$ for all
$(s,a^{0},a^{1})\in{\mathcal{S}}\times\mathcal{A}\times\mathcal{A}$.

We use $\mathcal{N}_{\mathcal{G}_{P_{h}}}(\epsilon)$ and
$\mathcal{N}_{\mathcal{G}_{A_{h}}}(\epsilon)$ to denote the $\epsilon$-bracket
number of $\mathcal{G}_{P_{h}}$ and $\mathcal{G}_{A_{h}}$. When the transition
probability or the advantage function possesses a low-dimension embedding, we
can also bound the $\epsilon$-bracket number efficiently.

##  4 Trajectory-Based Comparison with Known Transition

In this section, we present our algorithm and analyze the sample complexity
for the trajectory-based pairwise-comparison setting when the ground truth
transition $P^{\star}$ is known. In Sections 5 and 6, we will further explore
the unknown transition setting and the action-based comparison setting.

###  4.1 Algorithm

Our proposed algorithm, FREEHAND described in Algorithm 1, consists of the
following two steps.

  * •

Confidence set construction via MLE (Lines 2–3). We construct a confidence set
for the ground truth reward from the implicit preference feedback. We achieve
this by selecting reward models that nearly maximize the log-likelihood of
observed data up to a slackness parameter $\zeta$. We will show that the
result, $\mathcal{R}(\mathcal{D})$, approximates the following confidence set:

$\displaystyle\mathcal{R}^{\prime}(\mathcal{D}):=\\{r\in\mathcal{G}_{r}:\mathbb{E}_{\tau_{0}\sim\mu_{0},\tau_{1}\sim\mu_{1}}[|\\{r(\tau_{1})-r(\tau_{0})\\}-\\{r^{*}(\tau_{1})-r^{*}(\tau_{0})\\}|^{2}]\leq\xi\\}$

for a certain $\xi$. Here the distance between $r$ and $r^{\star}$ is measured
using the squared error of $r(\tau_{1})-r(\tau_{0})$ and
$r^{*}(\tau_{1})-r^{*}(\tau_{0})$ over the offline data.

  * •

Distributionally robust policy optimization (Line 4). After constructing the
confidence set, we search for the policy that maximizes the policy value under
the least favorable reward model, the $r\in\mathcal{R}(\mathcal{D})$
minimizing the policy value $J(\pi;r,P^{*})$ minus
$\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r(\tau)]$, where $\mu_{\mathrm{ref}}$
is an arbitrary known reference trajectory distribution. It is generally
recommended to set $\mu_{\mathrm{ref}}$ to $\mu_{1}$, as we will explain
later, possibly a sample-average approximation thereof based on
$\\{\tau^{1,1},\dots,\tau^{N,1}\\}$. By selecting the least favorable reward
model instead of the MLE solution $\widehat{r}$, we penalize policies that are
not well-covered by the offline data. The need for a reference policy arises
because the approximated confidence set measures the uncertainty for reward
difference between two trajectories ($r(\tau_{1})-r(\tau_{0})$), but it cannot
measure the uncertainty of the reward of a single trajectory $r(\tau)$.

In the following, we compare our algorithm to existing works. Zhu et al.,
(2023) consider a pessimistic offline RL algorithm for RLHF specialized to the
linear reward class setting, while our FREEHAND can handle general function
approximation. Specifically, they construct the confidence set using the
feature-covariance-rotated $\ell_{2}$-ball around the MLE $\hat{\theta}$,
where $\widehat{r}(\tau)=\langle\phi(\tau),\hat{\theta}\rangle$. In contrast,
our confidence set is obtained directly from the log-likelihood objective and
is generic. Uehara and Sun, (2021) proposes a model-based pessimistic offline
RL algorithm when we have access to rewards. The confidence set construction
correspondingly differs significantly. Cheng et al., (2022) considers a
general offline pessimistic RL framework. In their policy optimization step,
they also subtract the value of a reference policy. While our approach also
guarantees that the learned policy can be as good as the reference, another
key motivation for us to use the reference policy is that in RLHF, we can only
measure the difference between rewards of any two trajectories.

Algorithm 1 FREEHAND: oFfline ReinforcemEnt lEarning with HumAN feeDback

1:Input: offline datset $\mathcal{D}$, slackness parameter $\zeta$, reference
distribution $\mu_{\mathrm{ref}}$, true transition $P^{\star}$

2:MLE: compute
$\widehat{r}=\mathop{\mathrm{argmax}}_{r\in\mathcal{G}_{r}}\sum_{n=1}^{N}\log
P_{r}(o=o^{n}\mid\tau^{n,1},\tau^{n,0})$

3:Confidence set construction: construct
$\textstyle\mathcal{R}(\mathcal{D})=\big{\\{}r\in\mathcal{G}_{r}:\sum_{n=1}^{N}\log
P_{r}(o=o^{n}\mid\tau^{n,0},\tau^{n,1})\geq\sum_{n=1}^{N}\log
P_{\widehat{r}}(o=o^{n}\mid\tau^{n,0},\tau^{n,1})-\zeta\big{\\}}$

4:Distributionally robust planning: return
$\textstyle\widehat{\pi}=\mathop{\mathrm{argmax}}_{\pi\in\Pi_{\mathrm{his}}}\min_{r\in\mathcal{R}(\mathcal{D})}\left(J(\pi;r,P^{\star})-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r(\tau)]\right)$

###  4.2 Analysis

To analyze the sample complexity of FREEHAND, we first quantify the
discrepancy between the offline data $\mathcal{D}$ and the distribution
induced by the target policy $\pi_{\mathrm{tar}}$.

######  Definition 5 (concentrability coefficient for preference-based
feedback).

The concentrability coefficient w.r.t. a reward class $\mathcal{G}_{r}$, a
target policy $\pi_{\mathrm{tar}}$, and a reference policy
$\mu_{\mathrm{ref}}$ is defined as

$\displaystyle
C_{r}(\mathcal{G}_{r},\pi_{\mathrm{tar}},\mu_{\mathrm{ref}}):=\max\Biggl{\\{}0,~{}\sup_{r\in\mathcal{G}_{r}}\frac{\mathbb{E}_{\tau^{0}\sim\pi_{\mathrm{tar}},\tau^{1}\sim\mu_{\mathrm{ref}}}[r^{\star}(\tau^{0})-r^{\star}(\tau^{1})-r(\tau^{0})+r(\tau^{1})]}{\sqrt{\mathbb{E}_{\tau^{0}\sim\mu_{0},\tau^{1}\sim\mu_{1}}\big{[}|r^{\star}(\tau^{0})-r^{\star}(\tau^{1})-r(\tau^{0})+r(\tau^{1})|^{2}\big{]}}}\Biggr{\\}}.$

Note, when we choose $\mu_{\mathrm{ref}}=\mu_{1}$, by Jensen’s inequality, the
value of $C_{r}(\mathcal{G}_{r},\pi_{\mathrm{tar}},\mu_{1})$ can always be
upper bounded by the per-trajectory concentration coefficient:
$C_{r}(\mathcal{G}_{r},\pi_{\mathrm{tar}},\mu_{1})\leq\sqrt{C_{\mathrm{tr}}}$
for any $\mathcal{G}_{r}$, where $\textstyle
C_{\mathrm{tr}}:=\max_{\tau\in{\mathcal{T}}}\frac{d^{\pi_{\mathrm{tar}}}(\tau)}{\mu_{0}(\tau)}.$
Moreover, while $C_{r}(\mathcal{G}_{r},\pi_{\mathrm{tar}},\mu_{1})$ becomes
$\sqrt{C_{\mathrm{tr}}}$ in the worst case (_e.g._ , when $\mathcal{G}_{r}$ is
the set of all functions mapping from ${\mathcal{T}}$ to $\mathbb{R}$), it can
generally be much smaller. For example, when using linear models, it is a
relative condition number, as explained later. Finally, when
$\mu_{\mathrm{ref}}=d^{\pi_{\mathrm{tar}}}$, our coefficient becomes $0$. This
implies that $C_{r}(\mathcal{G}_{r},\pi_{\mathrm{tar}},\mu_{1})$ could be
small when $\pi_{\mathrm{tar}}$ and $\mu_{\mathrm{ref}}$ are close. While
similar definition of concentrability coefficient has been used in regular RL
(Song et al.,, 2022), this new definition is unique for RLHF.

In our following PAC analysis, we further assume the reward class
$\mathcal{G}_{r}$ is realizable and bounded.

######  Assumption 2 (Realizability).

We have $r^{\star}\in\mathcal{G}_{r}$.

######  Assumption 3 (Boundedness).

We have $0\leq r(\tau)\leq r_{\mathrm{max}}$ for all $r\in\mathcal{G}_{r}$ and
$\tau\in{\mathcal{T}}$.

Then we have the following theorem stating the suboptimality of
$\widehat{\pi}$ aganist $\pi_{\mathrm{tar}}$ with respect to the true reward
$r^{\star}$ and system dynamics $P^{\star}$:

######  Theorem 1.

For any $\delta\in(0,1]$, let
$\zeta=c_{\mathrm{MLE}}\log(\mathcal{N}_{\mathcal{G}_{r}}(1/N)/\delta)$ where
$c_{\mathrm{MLE}}>0$ is a universal constant, then under Assumption 1,2 and 3,
with probability $1-\delta$, we have

$\displaystyle
J(\pi_{\mathrm{tar}};r^{\star},P^{\star})-J(\widehat{\pi};r^{\star},P^{\star})\leq\sqrt{\frac{cC^{2}_{r}(\mathcal{G}_{r},\pi_{\mathrm{tar}},\mu_{\mathrm{ref}})\kappa^{2}\log(\mathcal{N}_{\mathcal{G}_{r}}(1/N)/\delta)}{N}},$
(2)

where $c>0$ is a universal constant and
$\kappa=(\inf_{x\in[-r_{\mathrm{max}},r_{\mathrm{max}}]}\Phi^{\prime}(x))^{-1}$.

Theorem 1 indicates that FREEHAND can learn an $\epsilon$-optimal policy
compared to $\pi_{\mathrm{tar}}$ with a sample complexity of

$N=\widetilde{\mathcal{O}}\bigg{(}\frac{C^{2}_{r}(\mathcal{G}_{r},\pi_{\mathrm{tar}},\mu_{\mathrm{ref}})\kappa^{2}\log(\mathcal{N}_{\mathcal{G}_{r}}(1/N)/\delta)}{\epsilon^{2}}\bigg{)}.$

Next we provide a detailed explanation of this sample complexity. Firstly,
$C_{r}(\mathcal{G}_{r},\pi_{\mathrm{tar}},\mu_{\mathrm{ref}})$ represents the
extent to which the dataset $\mathcal{D}$ covers the target policy
$\pi_{\mathrm{tar}}$. In our theorem, to obtain a non-vacuous PAC guarantee,
we only require the dataset $\mathcal{D}$ to cover the target policy
$\pi_{\mathrm{tar}}$ (i.e.,
$C_{r}(\mathcal{G}_{r},\pi_{\mathrm{tar}},\mu_{\mathrm{ref}})<\infty$). The
distributionally robust optimization step plays a crucial role in obtaining
this guarantee under partial coverage. In particular, invoking the fact that
$C_{r}(\mathcal{G}_{r},\pi_{\mathrm{tar}},\mu_{\mathrm{ref}})=0$ when setting
$\pi_{\mathrm{tar}}=\mu_{\mathrm{ref}}$, (2) is reduced to

$\displaystyle J(\mu_{\mathrm{ref}};r^{\star},P^{\star})\leq
J(\widehat{\pi};r^{\star},P^{\star})$ (3)

This shows that a reasonable default choice for the reference is to choose
$\mu_{\mathrm{ref}}=\mu_{1}$ (or $\mu_{0})$ as it will allow us to ensure our
performance is at least no smaller than the performance associated with the
offline data, thus achieving a robustness guarantee here.

Secondly, $\log(\mathcal{N}_{\mathcal{G}_{r}}(1/N))$ measures the complexity
of the function class $\mathcal{G}_{r}$. For example, when using linear
models, it takes $\tilde{O}(d)$. We refer the reader to van de Geer, (2000)
for bracketing number computations for more general classes. Thirdly, $\kappa$
represents the non-linearity of the link function $\Phi$, which determines the
difficulty of estimating the reward from human preferences. This dependence on
$\kappa$ is present in the existing literature of RLHF, both in online
settings (Pacchiano et al.,, 2021; Chen et al.,, 2022) and offline settings
(Zhu et al.,, 2023).

#### Comparison to Zhu et al., (2023).

Now we show that our result strictly generalizes the results from Zhu et al.,
(2023) when using linear function approximation for rewards. Zhu et al.,
(2023) considers the linear reward setting under BTL model and they can
achieve the following sample complexity:

$\displaystyle
N=\mathcal{O}\bigg{(}\frac{C^{2}_{\mathrm{lin}}\exp(4BR)d\log(1/\delta)}{\epsilon^{2}}\bigg{)},$

where $R$ and $B$ are the norm bounds on the feature vectors $\phi$ and
parameter $\theta$ (defined in Proposition 1).The concentrability coefficient
$C_{\mathrm{lin}}$ is defined as

$\displaystyle
C_{\mathrm{lin}}:=\|\mathbb{E}_{\tau^{0}\sim\pi_{\mathrm{tar}},\tau^{1}\sim\mu_{\mathrm{ref}}}[\phi(\tau^{0})-\phi(\tau^{1})]\|_{\Sigma_{\mathcal{D}}^{-1}},$

and $\Sigma_{\mathcal{D}}$ is the empirical covariance matrix of the dataset
$\frac{1}{N}\sum_{n=1}^{N}(\phi(\tau^{n,0})-\phi(\tau^{n,1}))(\phi(\tau^{n,0})-\phi(\tau^{n,1}))^{\top}$.

Note that all the analysis and proofs in this paper still hold when we define
the concentrability coefficient as

$\displaystyle
C^{\prime}_{r}(\mathcal{G}_{r},\pi_{\mathrm{tar}},\mu_{\mathrm{ref}}):=\max\bigg{\\{}0,\sup_{r\in\mathcal{G}_{r}}\frac{\mathbb{E}_{\tau^{0}\sim\pi_{\mathrm{tar}},\tau^{1}\sim\mu_{\mathrm{ref}}}[r^{\star}(\tau^{0})-r^{\star}(\tau^{1})-r(\tau^{0})+r(\tau^{1})]}{\sqrt{\frac{1}{N}\sum_{n=1}^{N}|r^{\star}(\tau^{n,0})-r^{\star}(\tau^{n,1})-r(\tau^{n,0})+r(\tau^{n,1})|^{2}}}\bigg{\\}}.$

Then when specializing the result in Theorem 1 to the linear reward setting
under BTL model with this version of concentrability coefficient, the sample
complexity is

$\displaystyle
N=\widetilde{\mathcal{O}}\bigg{(}\frac{(C^{\prime}_{r}(\mathcal{G}_{r},\pi_{\mathrm{tar}},\mu_{\mathrm{ref}}))^{2}\exp(2r_{\mathrm{max}})d\log(BR/\delta)}{\epsilon^{2}}\bigg{)}.$

We know that $BR\geq r_{\mathrm{max}}$. In addition, note that in this case,
we have $C_{\mathrm{lin}}\geq 0$ and for any $r\in\mathcal{G}_{r}$,

$\displaystyle\big{|}\mathbb{E}_{\tau^{0}\sim\pi_{\mathrm{tar}},\tau^{1}\sim\mu_{\mathrm{ref}}}[r^{\star}(\tau^{0})-r^{\star}(\tau^{1})-r(\tau^{0})+r(\tau^{1})]\big{|}$
$\displaystyle\qquad=\big{|}\langle\mathbb{E}_{\tau^{0}\sim\pi_{\mathrm{tar}},\tau^{1}\sim\mu_{\mathrm{ref}}}[\phi(\tau^{0})-\phi(\tau^{1})],\theta^{\star}-\theta\rangle\big{|}$
$\displaystyle\qquad\leq\|\mathbb{E}_{\tau^{0}\sim\pi_{\mathrm{tar}},\tau^{1}\sim\mu_{\mathrm{ref}}}[\phi(\tau^{0})-\phi(\tau^{1})]\|_{\Sigma_{\mathcal{D}}^{-1}}\cdot\|\theta^{\star}-\theta\|_{\Sigma_{\mathcal{D}}}$
$\displaystyle\qquad=\|\mathbb{E}_{\tau^{0}\sim\pi_{\mathrm{tar}},\tau^{1}\sim\mu_{\mathrm{ref}}}[\phi(\tau^{0})-\phi(\tau^{1})]\|_{\Sigma_{\mathcal{D}}^{-1}}\cdot\sqrt{\frac{1}{N}\sum_{n=1}^{N}|r^{\star}(\tau^{n,0})-r^{\star}(\tau^{n,1})-r(\tau^{n,0})+r(\tau^{n,1})|^{2}},$

where we suppose $r^{\star}(\tau)=\langle\phi(\tau),\theta^{\star}\rangle$,
$r(\tau)=\langle\phi(\tau),\theta\rangle$ and $\|x\|_{A}:=\sqrt{x^{\top}Ax}$.
Therefore we have

$\displaystyle
C^{\prime}_{r}(\mathcal{G}_{r},\pi_{\mathrm{tar}},\mu_{\mathrm{ref}})\leq
C_{\mathrm{lin}}.$

This implies that Theorem 1 can recover the sample complexity for linear
reward setting under BTL model in Zhu et al., (2023) with only some additional
log factors. As a matter of fact, our analysis has certain superiority even in
the linear case because the sample complexity can be $0$ when $\pi_{tar}$ and
$\mu_{ref}$ are close.

#### Proof sketch.

The proof of Theorem 1 consists of two steps, deriving the guarantee of MLE
and analyzing the performance of pessimistic offline RL. In the first step, we
leverage the MLE guarantee with general function approximation and apply mean
value theorem to bound the estimation error of the reward. This is different
from the literature (Pacchiano et al.,, 2021; Zhu et al.,, 2023) where the
analysis is specifically tailored to linear function approximation and cannot
extend to general function directly. The second step relies on our newly-
defined cocnentrability coefficient to deal with the distribution shift in the
trajectory-based comparison setting. The complete proof is deferred to
Appendix B.

###  4.3 Discussion of the Concentrability Coefficient

In the worst-case scenario (_i.e._ , $\mathcal{G}_{r}$ is the set of all
functions mapping from ${\mathcal{T}}$ to $\mathbb{R}$), the value of
$C_{r}(\mathcal{G}_{r},\pi_{\mathrm{tar}},\mu_{1})$ is reduced to to the per-
trajectory concentrability coefficient $C_{\mathrm{tr}}$. The per-trajectory
concentrability coefficient is generally larger than the per-step
concentrability coefficient $C_{\mathrm{st}}$ commonly used in the general
offline RL literature. Specifically, $C_{\mathrm{st}}$ is defined as

$C_{\mathrm{st}}:=\max_{s,a,h}d^{\pi_{\mathrm{tar}}}_{h}(s,a)/\mu_{0,h}(s,a),$

where $\mu_{0,h}(s,a)$ represents the marginal distribution at step $h$. In
this section, we show the dependence on the per-trajectory concentrability
coefficient is necessary for our offline RLHF context. This is intuitively
because our RLHF setting involves reward functions defined over trajectories,
reflecting the fact that human feedback is also trajectory-based.

In the next proposition, we first show that the per-trajectory concentrability
coefficient $C_{\mathrm{tr}}$ can be exponentially larger than the per-step
concentrability coefficient $C_{\mathrm{st}}$.

######  Proposition 2.

For any $S\geq 1,A\geq 2,H\geq 1,C\geq 1$, there exists an MDP $\mathcal{M}$
with horizon $H$, a policy $\pi_{\mathrm{tar}}$ and a data distribution
$\mu_{0}$ such that $|{\mathcal{S}}|=S,|\mathcal{A}|=A$ and
$C_{\mathrm{st}}=C$ while $C_{\mathrm{tr}}=C^{H}$.

Proposition 2 indicates that $C_{\mathrm{tr}}$ can be significantly larger
than $C_{\mathrm{st}}$. Then a natural question arises as to whether we can
obtain suboptimality guarantees using $C_{\mathrm{st}}$ as one would have in
regular offline RL. Unfortunately, the following lower bounds reveal that the
suboptimality can scale with $C_{\mathrm{st}}^{H-1}$ in the worst case:

######  Theorem 2.

Set $\pi_{\mathrm{tar}}=\pi^{\star}$. Then, for any $C>1$ and $H\geq 1$, there
exists a dataset distribution $\mu_{1}$ such that we have

$\displaystyle\inf_{\widehat{\pi}}\sup_{(\mathcal{M},\mu_{0})\in\Theta_{\mathrm{st}}(C)}\mathbb{E}_{\mathcal{D}}[J(\pi^{\star};r^{\star},P^{\star})-J(\widehat{\pi};r^{\star},P^{\star})]\gtrsim\min\bigg{\\{}C-1,\sqrt{\frac{(\max\\{C,2\\})^{H-1}(C-1)}{N}}\bigg{\\}},$

where $\widehat{\pi}$ is any mesurable function of the data $\mathcal{D}$ (and
knows the information of $\mu_{1}$). $\Theta_{\mathrm{st}}(C)$ is the set of
all MDP, offline distribution $(\mathcal{M},\mu_{0})$ such that
$C_{\mathrm{st}}\leq C$. Note $\mathbb{E}_{\mathcal{D}}$ is taken with respect
to the randomness in $\mathcal{D}$.

In addition, with similar hard instances constrcuted in Theorem 2, we can show
that scaling with $C_{\mathrm{tr}}$ is necessary in our setting:

######  Theorem 3.

Set $\pi_{\mathrm{tar}}=\pi^{\star}$. Then for any $C>1$ and $H\geq 1$, there
exists a dataset distribution $\mu_{1}$ such that we have

$\displaystyle\inf_{\widehat{\pi}}\sup_{(\mathcal{M},\mu_{0})\in\Theta_{\mathrm{tr}}(C)}\mathbb{E}_{\mathcal{D}}[J(\pi^{\star};r^{\star},P^{\star})-J(\widehat{\pi};r^{\star},P^{\star})]\gtrsim\min\bigg{\\{}C-1,\sqrt{\frac{C-1}{N}}\bigg{\\}},$

where $\widehat{\pi}$ is any mesurable function of the data $\mathcal{D}$ (and
knows the information of $\mu_{1}$). $\Theta_{\mathrm{tr}}$ is the set of all
MDP, offline distribution $(\mathcal{M},\mu_{0})$ such that
$C_{\mathrm{tr}}\leq C$. Note $\mathbb{E}_{\mathcal{D}}$ is taken with respect
to the randomness in $\mathcal{D}$.

Note that when $\mu_{1}$ is known, we can set $\mu_{\mathrm{ref}}=\mu_{1}$ in
Algorithm 1 and then
$C_{r}(\mathcal{G}_{r},\pi_{\mathrm{tar}},\mu_{1})\leq\sqrt{C_{\mathrm{tr}}}$,
which implies the sample complexity in Theorem 1 indeed nearly matches this
lower bound with respect to $C_{\mathrm{tr}}$ and $N$ when $N$ is sufficiently
large.

In summary, Theorem 2 and Theorem 3 imply that the scaling with the per-
trajectory concentrability coefficient is essential in the trajectory-based
pairwise-comparison setting, and it cannot be relaxed to the per-step
concentrability without additional assumptions, such as on the reward
structure.

##  5 Trajectory-Based Comparison with Unknown Transition

We extend the setting presented in Section 4 to the scenario where the
transition function $P^{\star}$ is unknown. The algorithm is described in
Algorithm 2. Compared to Algorithm 1, we simply added a similar step to handle
unknown transitions. Hereafter, we use the convention $P_{0}(\cdot\mid
s,a):=P_{0}(\cdot)$.

Algorithm 2 FREEHAND-transition

Input: offline dataset $\mathcal{D}$, slackness parameter
$\zeta,\zeta_{P_{h}}$, reference distribution $\mu_{\mathrm{ref}}$

MLE for reward: compute
$\textstyle\widehat{r}=\mathop{\mathrm{argmax}}_{r\in\mathcal{G}_{r}}\sum_{n=1}^{N}\log
P_{r}(o=o^{n}|\tau^{n,1},\tau^{n,0})$

MLE for transition: compute
$\widehat{P}_{h}=\mathop{\mathrm{argmax}}_{P_{h}\in\mathcal{G}_{P_{h}}}\sum_{n=1}^{N}\sum_{i=0}^{1}\log
P_{h}(s^{n,i}_{h+1}|s^{n,i}_{h},a^{n,i}_{h})$

Confidence set construction: for $0\leq h\leq H-1$, construct
$\textstyle\mathcal{R}(\mathcal{D})=\bigg{\\{}r\in\mathcal{G}_{r}:\sum_{n=1}^{N}\log
P_{r}(o=o^{n}|\tau^{n,0},\tau^{n,1})\geq\sum_{n=1}^{N}\log
P_{\widehat{r}}(o=o^{n}|\tau^{n,0},\tau^{n,1})-\zeta\bigg{\\}}.$
$\mathcal{P}_{h}(\mathcal{D})=\bigg{\\{}P_{h}\in\mathcal{G}_{P_{h}}:\sum_{n=1}^{N}\sum_{i=0}^{1}\log
P_{h}(s^{n,i}_{h+1}|s^{n,i}_{h},a^{n,i}_{h})\geq\sum_{n=1}^{N}\sum_{i=0}^{1}\log\widehat{P}_{h}(s^{n,i}_{h+1}|s^{n,i}_{h},a^{n,i}_{h})-\zeta_{P_{h}}\bigg{\\}},$

Distributionally robust plnanning: return
$\textstyle\widehat{\pi}=\mathop{\mathrm{argmax}}_{\pi\in\Pi_{\mathrm{his}}}\min_{r\in\mathcal{R}(\mathcal{D}),P_{h}\in\mathcal{P}_{h}(\mathcal{D})}J\Big{(}\pi;r,\\{P_{h}\\}_{h=0}^{H-1})\Big{)}-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r(\tau)].$

Our sample complexity will depend on the following additional concentration
coefficient:

######  Definition 6 (Concentrability coefficient for the transition).

The concentrability coefficient w.r.t. transition classes
$\\{\mathcal{G}_{P_{h}}\\}$ and a target policy $\pi_{\mathrm{tar}}$ is
defined as

$\displaystyle
C_{P}(\\{\mathcal{G}_{P_{h}}\\},\pi_{\mathrm{tar}}):=\max_{h:0\leq h\leq
H-1}\sup_{P_{h}\in\mathcal{G}_{P_{h}}}\frac{\mathbb{E}_{(s,a)\sim
d^{\pi_{\mathrm{tar}}}_{h}}[\|P_{h}(\cdot\mid s,a)-P^{\star}_{h}(\cdot\mid
s,a)\|_{1}]}{\sqrt{\mathbb{E}_{(s,a)\sim(\mu_{0,h}/2+\mu_{1,h}/2)}[\|P_{h}(\cdot\mid
s,a)-P^{\star}_{h}(\cdot\mid s,a)\|^{2}_{1}]}}.$

Note this is always upper-bounded by the density-ratio-based concentrability
coefficient,
$C_{P}(\\{\mathcal{G}_{P_{h}}\\},\pi_{\mathrm{tar}})\leq\sup_{(s,a,h)\in{\mathcal{S}}\times\mathcal{A}\times[H]}\frac{d^{\pi_{\mathrm{tar}}}_{h}(s,a)}{\mu_{0,h}(s,a)/2+\mu_{1,h}(s,a)/2}.$

We also assume the transition classes $\\{\mathcal{G}_{P_{h}}\\}_{h=0}^{H-1}$
are realizable:

######  Assumption 4 (Realizability).

Suppose that we have $P^{\star}_{h}\in\mathcal{G}_{P_{h}}$ for all $h$ where
$0\leq h\leq H-1$. In addition, any choice $P_{h}\in\mathcal{G}_{P_{h}}$ for
$0\leq h\leq H-1$ are valid transition distributions.

Then with the above assumptions, we have the following theorem to characterize
the sample complexity when the transition is unknown:

######  Theorem 4.

For any $\delta\in(0,1]$, let
$\zeta=c_{\mathrm{MLE}}\log(\mathcal{N}_{\mathcal{G}_{r}}(1/N)/\delta)$,$\zeta_{P_{h}}=c_{P}\log(H\mathcal{N}_{\mathcal{G}_{P_{h}}}(1/N)/\delta)$
where $c_{\mathrm{MLE}},c_{P}>0$ are universal constants, then under
Assumption 1,2,3 and 4, we have

$\displaystyle
J(\pi_{\mathrm{tar}};r^{\star},P^{\star})-J(\widehat{\pi};r^{\star},P^{\star})$
$\displaystyle\leq\sqrt{\frac{cC^{2}_{r}(\mathcal{G}_{r},\pi_{\mathrm{tar}},\mu_{\mathrm{ref}})\kappa^{2}\log(\mathcal{N}_{\mathcal{G}_{r}}(1/N)/\delta)}{N}}+Hr_{\mathrm{max}}\sqrt{\frac{cC^{2}_{P}(\\{\mathcal{G}_{P_{h}}\\},\pi_{\mathrm{tar}})\log(H\mathcal{N}_{P}(1/N)/\delta)}{N}},$

where $c>0$ and $\kappa$ are the same as Theorem 1 and
$\mathcal{N}_{P}:=\max_{0\leq h\leq H-1}\mathcal{N}_{\mathcal{G}_{P_{h}}}$.

Compared to Theorem 1, we introduce an additional term in our guarantee to
account for the unknown transitions. Once again, our result demonstrates that
the learned policy can achieve performance comparable to any target policy
$\pi_{\mathrm{tar}}$ covered by the offline data, i.e.,
$C_{r}(\mathcal{G}_{r},\pi_{\mathrm{tar}},\mu_{\mathrm{ref}})<\infty,C_{P}(\\{\mathcal{G}_{P_{h}}\\},\pi_{\mathrm{tar}})<\infty$.

######  Remark 1 (Comparison to Uehara and Sun, (2021) ).

Like us, Uehara and Sun, (2021) proposed a model-based RL algorithm that works
under partial coverage, but in the standard RL setting and with a known state-
action-wise reward function. In addition to the difference in settings, which
is the primary difference, our approach moreover differs from their approach
because while they construct confidence intervals by defining a confidence
ball around the MLE solution based on the total variation distance, we use the
Kullback-Leibler (KL) distance. This may be preferable as computing the KL
distance is generally easier than the total variation distance as it arises
directly from the MLE objective, as practically done in Rigter et al., (2022).

##  6 Action-Based Comparison

Next, we turn our attention to the action-based comparison setting
(Ramachandran and Amir,, 2007; Zhu et al.,, 2023), where human evaluators
provide preferences between pairs of actions instead of pairs of trajectories.
In this section, we assume that the reward function $r^{\star}$ is state-
action-wise: $r^{\star}(\tau)=\sum_{h=1}^{H}r^{\star}_{h}(s_{h},a_{h})$ for
$\tau=(s_{1},a_{1},\cdots,s_{H},a_{H})$. And, we consider a preference model
based on $Q^{\star}$.

#### Setting.

We have datasets $\mathcal{D}=\\{\mathcal{D}_{h}\\}_{h=1}^{H}$ with
$\mathcal{D}_{h}=\\{(s_{h}^{n},a_{h}^{n,0},a_{h}^{n,1},o_{h}^{n})\\}_{n=1}^{N}$
for each $h\in[H]$, where each sample is drawn i.i.d. from the distribution
$s_{h}^{n}\sim\mu_{h},a_{h}^{n,0}\sim\mu_{0,h}(\cdot\mid
s_{h}^{n}),a_{h}^{n,1}\sim\mu_{1,h}(\cdot\mid s_{h}^{n})$ and
$o^{n}_{h}\in\\{0,1\\}$ indicates preference for $a_{h}^{1,n}$ over
$a_{h}^{0,n}$ in the state $s_{h}^{n}$. We assume it satisfies the following
preference model:

######  Assumption 5 (Action-based comparison model).

Given a pair of actions $a^{0}_{h},a^{1}_{h}$ and state $s_{h}$,
$o\in\\{0,1\\}$ satisfies

$\displaystyle P(o_{h}=1\mid
s_{h},a_{h}^{0},a_{h}^{1})=\Phi(Q^{\star}_{h}(s_{h},a_{h}^{1})-Q^{\star}_{h}(s_{h},a_{h}^{0})).$

where $o_{h}=1$ means $a^{1}_{h}$ is preferred over $a^{0}_{h}$.

Here, the aforementioned distribution can be equivalently expressed as
$P(o_{h}^{n}=1\mid
s_{h}^{n},a_{h}^{n,0},a_{h}^{n,1})=\Phi(A^{\star}_{h}(s_{h}^{n},a_{h}^{n,1})-A^{\star}_{h}(s_{h}^{n},a_{h}^{n,0}))$,
where $A^{\star}$ denotes the optimal advantage function. Consequently, we
introduce general function classes $\mathcal{G}_{A_{h}}$ to estimate the
optimal advantage function $A^{\star}_{h}$. In addition, for each
$A_{h}\in\mathcal{G}_{A_{h}}$ and
$(s,a^{0},a^{1})\in{\mathcal{S}}\times\mathcal{A}\times\mathcal{A}$, recall
that we use $P_{A_{h}}(\cdot\mid s,a^{0},a^{1})$ to represent the human
preference model with respect to $A_{h}$, defined as $P_{A_{h}}(o=1\mid
s,a^{0},a^{1}):=\Phi(A_{h}(s,a^{1})-A_{h}(s,a^{0}))$. We again use the
$\epsilon$-bracket number of such advantage function classes to quantify their
complexity, denoted as $\mathcal{N}_{\mathcal{G}_{A_{h}}}$.

###  6.1 Algorithm

Our algorithm comprises two steps. In the first step (Line 2), our objective
is to estimate the optimal advantage function using MLE. In the second step
(Line 3), we determine the policy by selecting the action with the highest
advantage value based on the learned advantage function. Note that our
algorithm does not rely on pessimism here. In the next section, we show that
under a soft-margin condition, our algorithm can still compete against
$\pi^{\star}$ even without leveraging any pessimism.

Algorithm 3 FREEHAND-action

1:Input: offline datset $\mathcal{D}$.

2:MLE: compute
$\textstyle\widehat{A}_{h}=\mathop{\mathrm{argmax}}_{A_{h}\in\mathcal{G}_{A_{h}}}\sum_{n=1}^{N}\log
P_{A_{h}}(o=o_{h}^{n}\mid s_{h}^{n},a_{h}^{n,0},a_{h}^{n,1})$ $\forall
h\in[H]$

3:Greedy policy: return
$\widehat{\pi}_{h}(s)=\mathop{\mathrm{argmax}}_{a\in\mathcal{A}}\widehat{A}_{h}(s,a),\quad\forall
h\in[H]$.

###  6.2 Analysis

Now we show that FREEHAND-action is able to learn a near-optimal policy as
long as offline data covers the optimal policy. Our analysis depends on the
following assumption on the margin of $Q^{\star}$:

######  Assumption 6 (Soft margin).

There exists $\alpha_{0}\in\mathbb{R}^{+}$, $\beta\in(0,\infty]$ such that for
all $a\in\mathcal{A},h\in[H],\alpha>0$, we have
$\mathbb{P}^{\pi^{\star},P^{\star}}(0<|Q^{\star}_{h}(s_{h},\pi^{\star}(s_{h}))-Q^{\star}_{h}(s_{h},a)|<\alpha)\leq(\alpha/\alpha_{0})^{\beta}.$

The soft margin is widely used in the literature on classification, decision
making, and RL (Audibert and Tsybakov,, 2007; Perchet and Rigollet,, 2013;
Luedtke and Chambaz,, 2020; Hu et al.,, 2021, 2022; Uehara et al.,, 2023).
Note, when the optimal Q function satisfies a gap (as in Simchowitz and
Jamieson,, 2019; Wu et al.,, 2022), the soft margin assumption holds with
$\beta=\infty$.

Next, we introduce the concentrability coefficient for the action-based
comparison setting, which is defined as follows.

######  Definition 7 (concentrability coefficient for action-based
comparison).

$\displaystyle
C_{\mathrm{act}}:=\sup_{h\in[H],A_{h}\in\mathcal{G}_{A_{h}}}\frac{\mathbb{E}_{(s,a^{0})\sim
d^{\pi^{\star}}_{h},a^{1}\sim\mathrm{Unif}(\cdot\mid
s)}[l(A_{h},s,a^{0},a^{1})]}{\mathbb{E}_{s\sim\mu_{h},a^{0}\sim\mu_{0,h}(\cdot\mid
s),a^{1}\sim\mu_{1,h}(\cdot\mid s)}[l(A_{h},s,a^{0},a^{1})]},$

where
$l(A_{h},s,a^{0},a^{1}):=|A^{\star}_{h}(s,a^{0})-A^{\star}_{h}(s,a^{1})-A_{h}(s,a^{0})+A_{h}(s,a^{1})|^{2}$
and $\mathrm{Unif}(\cdot\mid s)$ is the uniform policy over $\mathcal{A}$.

We observe that

$\displaystyle
C_{\mathrm{act}}\leq\bigg{(}\sup_{h\in[H],s\in{\mathcal{S}}}\frac{d^{\pi^{\star}}_{h}(s)}{\mu_{h}(s)}\bigg{)}\cdot\bigg{(}\sup_{h\in[H],s\in{\mathcal{S}},a^{0}\in\mathcal{A}}\frac{\pi^{\star}_{h}(a^{0}\mid
s)}{\mu_{0,h}(a^{0}\mid
s)}\bigg{)}\cdot\bigg{(}\frac{1}{|\mathcal{A}|}\sup_{h\in[H],s\in{\mathcal{S}},a^{1}\in\mathcal{A}}\frac{1}{\mu_{1,h}(a^{1}\mid
s)}\bigg{)}.$

Based on this bound, we can consider simple sufficient conditions for
$C_{\mathrm{act}}$ to be finite. Firstly, regarding the first term, it is
sufficient for the dataset distribution $\mu_{h}$ to cover the states visited
by the optimal policy $\pi^{\star}$, denoted as $d^{\pi^{\star}}_{h}$.
Regarding the second term, we require $\mu_{0,h}$ to cover $\pi^{\star}_{h}$.
Additionally, the third term can be upper bounded when $\mu_{1,h}$ can cover
the whole action space. This is mild because $\forall
s\in{\mathcal{S}};\mu_{h}(s)>0$ is not controllable to the learner; but
$\forall(s,a)\in{\mathcal{S}}\times\mathcal{A};\mu_{1,h}(a\mid s)>0$ is
controllable to the learner in the data-collection process. To summarize,
$C_{\mathrm{act}}<\infty$ primarily requires partial coverage over the state
space with respect to the optimal policy, which is preferable in practical
applications where ${\mathcal{S}}$ can be very large.

Additionally, we introduce several assumptions on the function classes similar
to those in Section 4.

######  Assumption 7.

For all $h\in[H]$, we have $A^{\star}_{h}\in\mathcal{G}_{A_{h}}$.

######  Assumption 8.

For all $h\in[H]$ and $A_{h}\in\mathcal{G}_{A_{h}}$, we have $|A_{h}(s,a)|\leq
b_{\max}$ for all $(s,a)\in{\mathcal{S}}\times\mathcal{A}$.

With the aforementioned assumptions, we can establish the sample complexity of
FREEHAND-action.

######  Theorem 5.

Under Assumption 5,6,7 and 8, we have with probability at least $1-\delta$
that

$\displaystyle
J(\pi^{\star};r^{\star},P^{\star})-J(\widehat{\pi};r^{\star},P^{\star})\leq
cH|\mathcal{A}|\bigg{(}\frac{2}{\beta}\bigg{)}^{\frac{\beta-2}{\beta+2}}\bigg{(}\frac{1}{\alpha_{0}}\bigg{)}^{\frac{2\beta}{\beta+2}}\bigg{(}\frac{\kappa^{2}_{A}C_{\mathrm{act}}\log(H\mathcal{N}_{\mathcal{G}_{A}}(1/N)/\delta)}{N}\bigg{)}^{\frac{\beta}{\beta+2}},$

where
$\mathcal{N}_{\mathcal{G}_{A}}:=\max_{h\in[H]}\mathcal{N}_{\mathcal{G}_{A_{h}}}$
and $\kappa_{A}=\frac{1}{\inf_{x\in[-b_{\max},b_{\max}]}\Phi^{\prime}(x)}$.

Theorem 5 suggests that FREEHAND-action can learn a near-optimal policy as
long as $C_{\mathrm{act}}$ takes a finite value under a soft margin.
Specifically, when a hard margin is imposed (i.e., $\beta=\infty$), FREEHAND-
action can learn an $\epsilon$-optimal policy with a sample complexity of
$N=\widetilde{\mathcal{O}}(1/\epsilon)$, which is faster than a typical rate
$\widetilde{\mathcal{O}}(1/\epsilon^{2})$. As mentioned earlier, the quantity
$C_{\mathrm{act}}$ represents the extent to which the distribution induced by
the optimal policy is covered by the offline data. Therefore, there is no need
for a potentially stringent condition that requires the offline data to cover
the entire state space like Zhu et al., (2023).

Furthermore, our guarantee is designed to overcome the limitations of existing
approaches. In Theorem 1, our upper-bound is influenced by the parameter
$\kappa$. When using a common sigmoid link function, this parameter scales
with $\Theta(\exp(r_{\max}))$. As a result, in dense reward settings where
$r_{\max}$ scales with $H$, this scaling factor may lead to an explicit
dependence of $\Theta(\exp(H))$. Similar observations have been made in
previous works (Zhu et al.,, 2023; Pacchiano et al.,, 2021; Chen et al.,,
2022). However, even if $r_{\max}$ scales with $H$, it is possible that the
$\ell_{\infty}$-norm of the advantage function, denoted as $b_{\max}$, can
take much smaller values which is a standard assumption used in Imitation
learning to argue that interaction mitigates covariate shift (Ross et al.,,
2011; Sun et al.,, 2017)222Without such an assumption, interactive imitation
learning algorithms not necessarily can outperform the classic Behavior
cloning algorithm (Agarwal et al.,, 2019).. Hence, we can avoid the explicit
dependence on $\Theta(\exp(H))$.

##  7 Conclusions

We propose the first algorithm for offline RLHF with preferences over
trajectories using general function approximation. Our algorithms leverage the
classic maximum likelihood estimation, and work under the setting where
offline data only provides partial coverage over some high quality policies,
and transitions are unknown. We establish lower bounds that explain the
differences between our RLHF model which uses trajectory-wise reward and
standard RL which uses state-action wise rewards. Moreover, we extend our
algorithm to the setting where preference is over actions.

## References

  * Abdelkareem et al., (2022) Abdelkareem, Y., Shehata, S., and Karray, F. (2022).  Advances in preference-based reinforcement learning: A review.  In 2022 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pages 2527–2532. IEEE.
  * Agarwal et al., (2019) Agarwal, A., Jiang, N., Kakade, S. M., and Sun, W. (2019).  Reinforcement learning: Theory and algorithms.  Technical report.
  * Audibert and Tsybakov, (2007) Audibert, J.-Y. and Tsybakov, A. B. (2007).  Fast learning rates for plug-in classifiers.  The Annals of statistics, 35(2):608–633.
  * Bai et al., (2022) Bai, Y., Jones, A., Ndousse, K., Askell, A., Chen, A., DasSarma, N., Drain, D., Fort, S., Ganguli, D., Henighan, T., et al. (2022).  Training a helpful and harmless assistant with reinforcement learning from human feedback.  arXiv preprint arXiv:2204.05862.
  * Brown et al., (2019) Brown, D., Goo, W., Nagarajan, P., and Niekum, S. (2019).  Extrapolating beyond suboptimal demonstrations via inverse reinforcement learning from observations.  In International conference on machine learning, pages 783–792. PMLR.
  * Chen and Jiang, (2019) Chen, J. and Jiang, N. (2019).  Information-theoretic considerations in batch reinforcement learning.  In International Conference on Machine Learning, pages 1042–1051. PMLR.
  * Chen et al., (2022) Chen, X., Zhong, H., Yang, Z., Wang, Z., and Wang, L. (2022).  Human-in-the-loop: Provably efficient preference-based reinforcement learning with general function approximation.  In International Conference on Machine Learning, pages 3773–3793. PMLR.
  * Cheng et al., (2022) Cheng, C.-A., Xie, T., Jiang, N., and Agarwal, A. (2022).  Adversarially trained actor critic for offline reinforcement learning.  In International Conference on Machine Learning, pages 3852–3878. PMLR.
  * Christiano et al., (2017) Christiano, P. F., Leike, J., Brown, T., Martic, M., Legg, S., and Amodei, D. (2017).  Deep reinforcement learning from human preferences.  Advances in neural information processing systems, 30.
  * Glaese et al., (2022) Glaese, A., McAleese, N., Trębacz, M., Aslanides, J., Firoiu, V., Ewalds, T., Rauh, M., Weidinger, L., Chadwick, M., Thacker, P., et al. (2022).  Improving alignment of dialogue agents via targeted human judgements.  arXiv preprint arXiv:2209.14375.
  * Hu et al., (2022) Hu, Y., Kallus, N., and Mao, X. (2022).  Fast rates for contextual linear optimization.  Management Science, 68(6):4236–4245.
  * Hu et al., (2021) Hu, Y., Kallus, N., and Uehara, M. (2021).  Fast rates for the regret of offline reinforcement learning.  In Conference on Learning Theory. PMLR.
  * Jin et al., (2020) Jin, Y., Yang, Z., and Wang, Z. (2020).  Is pessimism provably efficient for offline rl?  arXiv preprint arXiv:2012.15085.
  * Jin et al., (2021) Jin, Y., Yang, Z., and Wang, Z. (2021).  Is pessimism provably efficient for offline rl?  In International Conference on Machine Learning, pages 5084–5096. PMLR.
  * Kidambi et al., (2020) Kidambi, R., Rajeswaran, A., Netrapalli, P., and Joachims, T. (2020).  Morel: Model-based offline reinforcement learning.  In Advances in Neural Information Processing Systems, volume 33, pages 21810–21823. Curran Associates, Inc.
  * Kumar et al., (2020) Kumar, A., Zhou, A., Tucker, G., and Levine, S. (2020).  Conservative q-learning for offline reinforcement learning.  In Conference on Neural Information Processing Systems (NeurIPS).
  * (17) Li, G., Ma, C., and Srebro, N. (2022a).  Pessimism for offline linear contextual bandits using lp confidence sets.  arXiv preprint arXiv:2205.10671.
  * (18) Li, G., Shi, L., Chen, Y., Chi, Y., and Wei, Y. (2022b).  Settling the sample complexity of model-based offline reinforcement learning.  arXiv preprint arXiv:2204.05275.
  * Liu et al., (2023) Liu, H., Sferrazza, C., and Abbeel, P. (2023).  Languages are rewards: Hindsight finetuning using human feedback.  arXiv preprint arXiv:2302.02676.
  * Liu et al., (2022) Liu, Q., Chung, A., Szepesvári, C., and Jin, C. (2022).  When is partially observable reinforcement learning not scary?  arXiv preprint arXiv:2204.08967.
  * Liu et al., (2020) Liu, Y., Swaminathan, A., Agarwal, A., and Brunskill, E. (2020).  Provably good batch reinforcement learning without great exploration.  arXiv preprint arXiv:2007.08202.
  * Luedtke and Chambaz, (2020) Luedtke, A. and Chambaz, A. (2020).  Performance guarantees for policy learning.  In Annales de l’IHP Probabilites et statistiques, volume 56, page 2162. NIH Public Access.
  * MacGlashan et al., (2017) MacGlashan, J., Ho, M. K., Loftin, R., Peng, B., Wang, G., Roberts, D. L., Taylor, M. E., and Littman, M. L. (2017).  Interactive learning from policy-dependent human feedback.  In International Conference on Machine Learning, pages 2285–2294. PMLR.
  * Nakano et al., (2021) Nakano, R., Hilton, J., Balaji, S., Wu, J., Ouyang, L., Kim, C., Hesse, C., Jain, S., Kosaraju, V., Saunders, W., et al. (2021).  Webgpt: Browser-assisted question-answering with human feedback.  arXiv preprint arXiv:2112.09332.
  * Novoseller et al., (2020) Novoseller, E., Wei, Y., Sui, Y., Yue, Y., and Burdick, J. (2020).  Dueling posterior sampling for preference-based reinforcement learning.  In Conference on Uncertainty in Artificial Intelligence, pages 1029–1038. PMLR.
  * Ouyang et al., (2022) Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., et al. (2022).  Training language models to follow instructions with human feedback.  Advances in Neural Information Processing Systems, 35:27730–27744.
  * Pacchiano et al., (2021) Pacchiano, A., Saha, A., and Lee, J. (2021).  Dueling rl: reinforcement learning with trajectory preferences.  arXiv preprint arXiv:2111.04850.
  * Perchet and Rigollet, (2013) Perchet, V. and Rigollet, P. (2013).  The multi-armed bandit problem with covariates.  The Annals of Statistics, 41(2):693–721.
  * Ramachandran and Amir, (2007) Ramachandran, D. and Amir, E. (2007).  Bayesian inverse reinforcement learning.  Urbana, 51:61801.
  * Ramamurthy et al., (2022) Ramamurthy, R., Ammanabrolu, P., Brantley, K., Hessel, J., Sifa, R., Bauckhage, C., Hajishirzi, H., and Choi, Y. (2022).  Is reinforcement learning (not) for natural language processing?: Benchmarks, baselines, and building blocks for natural language policy optimization.  arXiv preprint arXiv:2210.01241.
  * (31) Rashidinejad, P., Zhu, B., Ma, C., Jiao, J., and Russell, S. (2021a).  Bridging offline reinforcement learning and imitation learning: A tale of pessimism.  arXiv preprint arXiv:2103.12021.
  * (32) Rashidinejad, P., Zhu, B., Ma, C., Jiao, J., and Russell, S. (2021b).  Bridging offline reinforcement learning and imitation learning: A tale of pessimism.  Advances in Neural Information Processing Systems, 34:11702–11716.
  * Rigter et al., (2022) Rigter, M., Lacerda, B., and Hawes, N. (2022).  Rambo-rl: Robust adversarial model-based offline reinforcement learning.  arXiv preprint arXiv:2204.12581.
  * Ross et al., (2011) Ross, S., Gordon, G., and Bagnell, D. (2011).  A reduction of imitation learning and structured prediction to no-regret online learning.  In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pages 627–635.
  * Shi et al., (2022) Shi, L., Li, G., Wei, Y., Chen, Y., and Chi, Y. (2022).  Pessimistic q-learning for offline reinforcement learning: Towards optimal sample complexity.  arXiv preprint arXiv:2202.13890.
  * Shin et al., (2023) Shin, D., Dragan, A. D., and Brown, D. S. (2023).  Benchmarks and algorithms for offline preference-based reward learning.  arXiv preprint arXiv:2301.01392.
  * Simchowitz and Jamieson, (2019) Simchowitz, M. and Jamieson, K. G. (2019).  Non-asymptotic gap-dependent regret bounds for tabular mdps.  Advances in Neural Information Processing Systems, 32.
  * Song et al., (2022) Song, Y., Zhou, Y., Sekhari, A., Bagnell, J. A., Krishnamurthy, A., and Sun, W. (2022).  Hybrid rl: Using both offline and online data can make rl efficient.  arXiv preprint arXiv:2210.06718.
  * Stiennon et al., (2020) Stiennon, N., Ouyang, L., Wu, J., Ziegler, D., Lowe, R., Voss, C., Radford, A., Amodei, D., and Christiano, P. F. (2020).  Learning to summarize with human feedback.  Advances in Neural Information Processing Systems, 33:3008–3021.
  * Sun et al., (2017) Sun, W., Venkatraman, A., Gordon, G. J., Boots, B., and Bagnell, J. A. (2017).  Deeply aggrevated: Differentiable imitation learning for sequential prediction.  In International conference on machine learning, pages 3309–3318. PMLR.
  * Uehara et al., (2023) Uehara, M., Kallus, N., Lee, J. D., and Sun, W. (2023).  Refined value-based offline rl under realizability and partial coverage.  arXiv preprint arXiv:2302.02392.
  * Uehara and Sun, (2021) Uehara, M. and Sun, W. (2021).  Pessimistic model-based offline rl: Pac bounds and posterior sampling under partial coverage.  In arXiv preprint arXiv:2107.06226.
  * van de Geer, (2000) van de Geer, S. (2000).  Empirical Processes in M-estimation, volume 6.  Cambridge university press.
  * Wainwright, (2019) Wainwright, M. (2019).  High-Dimensional Statistics: A Non-Asymptotic Viewpoint, volume 48 of Cambridge Series in Statistical and Probabilistic Mathematics.  Cambridge University Press.
  * Warnell et al., (2018) Warnell, G., Waytowich, N., Lawhern, V., and Stone, P. (2018).  Deep tamer: Interactive agent shaping in high-dimensional state spaces.  In Proceedings of the AAAI conference on artificial intelligence, volume 32.
  * Wirth et al., (2017) Wirth, C., Akrour, R., Neumann, G., Fürnkranz, J., et al. (2017).  A survey of preference-based reinforcement learning methods.  Journal of Machine Learning Research, 18(136):1–46.
  * Wu et al., (2022) Wu, J., Braverman, V., and Yang, L. (2022).  Gap-dependent unsupervised exploration for reinforcement learning.  In International Conference on Artificial Intelligence and Statistics, pages 4109–4131. PMLR.
  * Wu et al., (2021) Wu, J., Ouyang, L., Ziegler, D. M., Stiennon, N., Lowe, R., Leike, J., and Christiano, P. (2021).  Recursively summarizing books with human feedback.  arXiv preprint arXiv:2109.10862.
  * Xie et al., (2021) Xie, T., Cheng, C.-A., Jiang, N., Mineiro, P., and Agarwal, A. (2021).  Bellman-consistent pessimism for offline reinforcement learning.  arXiv preprint arXiv:2106.06926.
  * Xu et al., (2020) Xu, Y., Wang, R., Yang, L., Singh, A., and Dubrawski, A. (2020).  Preference-based reinforcement learning with finite-time guarantees.  Advances in Neural Information Processing Systems, 33:18784–18794.
  * Yin and Wang, (2021) Yin, M. and Wang, Y.-X. (2021).  Towards instance-optimal offline reinforcement learning with pessimism.  Advances in neural information processing systems, 34:4065–4078.
  * Yu et al., (2020) Yu, T., Thomas, G., Yu, L., Ermon, S., Zou, J. Y., Levine, S., Finn, C., and Ma, T. (2020).  Mopo: Model-based offline policy optimization.  In Advances in Neural Information Processing Systems, volume 33, pages 14129–14142.
  * Yue et al., (2012) Yue, Y., Broder, J., Kleinberg, R., and Joachims, T. (2012).  The k-armed dueling bandits problem.  Journal of Computer and System Sciences, 78(5):1538–1556.
  * (54) Zhan, W., Huang, B., Huang, A., Jiang, N., and Lee, J. (2022a).  Offline reinforcement learning with realizability and single-policy concentrability.  In Conference on Learning Theory, pages 2730–2775. PMLR.
  * (55) Zhan, W., Uehara, M., Sun, W., and Lee, J. D. (2022b).  Pac reinforcement learning for predictive state representations.  arXiv preprint arXiv:2207.05738.
  * Zhu et al., (2023) Zhu, B., Jiao, J., and Jordan, M. I. (2023).  Principled reinforcement learning with human feedback from pairwise or $k$-wise comparisons.  arXiv preprint arXiv:2301.11270.
  * Ziegler et al., (2019) Ziegler, D. M., Stiennon, N., Wu, J., Brown, T. B., Radford, A., Amodei, D., Christiano, P., and Irving, G. (2019).  Fine-tuning language models from human preferences.  arXiv preprint arXiv:1909.08593.

##  Appendix A Proof of Proposition 1

Let $\mathcal{F}$ denote the function class
$\\{f_{r}:f_{r}(\tau^{0},\tau^{1})=P_{r}(o=1|\tau^{0},\tau^{1}),r\in\mathcal{G}_{r}\\}$.
Let $\mathcal{I}_{\mathcal{F}}(\epsilon)$ denote the $\epsilon$-bracket number
with respect to $\ell_{\infty}$-norm, i.e., the minimum integer $M$ such that
there exist $M$ functions $\\{f^{i}\\}_{i=1}^{M}$ such that for each
$f_{r}\in\mathcal{F}$, we have
$\sup_{\tau^{0},\tau^{1}}|f_{r}(\tau^{0},\tau^{1})-f^{i}(\tau^{0},\tau^{1})|\leq\epsilon$
for some $i\in[M]$. Then we know there exists a set of function
$\overline{\mathcal{F}}$ with
$|\overline{\mathcal{F}}|=\mathcal{I}_{\mathcal{F}}(\epsilon/4)$ such that for
each $f_{r}\in\mathcal{F}$, there exists
$\overline{f}\in\overline{\mathcal{F}}$ satisfying

$\displaystyle\sup_{\tau^{0},\tau^{1}}|f_{r}(\tau^{0},\tau^{1})-\overline{f}(\tau^{0},\tau^{1})|\leq\epsilon/4.$

Now we construct a bracket $(g^{1}_{\overline{f}},g^{2}_{\overline{f}})$
defined as follows:

$\displaystyle
g^{1}_{\overline{f}}(o=1|\tau^{0},\tau^{1})=\overline{f}(\tau^{0},\tau^{1})-\epsilon/4,g^{1}_{\overline{f}}(o=0|\tau^{0},\tau^{1})=1-\overline{f}(\tau^{0},\tau^{1})-\epsilon/4,$
$\displaystyle
g^{2}_{\overline{f}}(o=1|\tau^{0},\tau^{1})=\overline{f}(\tau^{0},\tau^{1})+\epsilon/4,g^{2}_{\overline{f}}(o=0|\tau^{0},\tau^{1})=1-\overline{f}(\tau^{0},\tau^{1})+\epsilon/4.$

Then clearly we have $g^{1}_{\overline{f}}(\cdot|\tau^{0},\tau^{1})\leq
P_{r}(\cdot|\tau^{0},\tau^{1})\leq
g^{2}_{\overline{f}}(\cdot|\tau^{0},\tau^{1})$ and
$\|g^{1}_{\overline{f}}(\cdot|\tau^{0},\tau^{1})-g^{2}_{\overline{f}}(\cdot|\tau^{0},\tau^{1})\|_{1}\leq\epsilon$.
This implies that
$\mathcal{N}_{\mathcal{G}_{r}}(\epsilon)\leq\mathcal{I}_{\mathcal{F}}(\epsilon/4)$.

Now we only need to bound $\mathcal{I}_{\mathcal{F}}(\epsilon/4)$. Consider
$\theta$ and $\theta^{\prime}$ with
$\|\theta-\theta^{\prime}\|_{2}\leq\epsilon_{1}$ and let $r$ ($r^{\prime}$)
denote the reward $\langle\phi,\theta\rangle$
($\langle\phi,\theta^{\prime}\rangle$). Then we know for all $\tau$,

$\displaystyle|r(\tau)-r^{\prime}(\tau)|\leq R\epsilon_{1}.$

Fix the trajectory pair $(\tau^{0},\tau^{1})$. Without loss of generality, we
assume
$\exp(r(\tau^{0}))+\exp(r(\tau^{1}))\leq\exp(r^{\prime}(\tau^{0}))+\exp(r^{\prime}(\tau^{1}))$.
Then we have

$\displaystyle\exp(r(\tau^{0}))+\exp(r(\tau^{1}))\leq\exp(r^{\prime}(\tau^{0}))+\exp(r^{\prime}(\tau^{1}))\leq\exp(R\epsilon_{1})\Big{(}\exp(r(\tau^{0}))+\exp(r(\tau^{1}))\Big{)}.$

On the other hand, we have

$\displaystyle|f_{r}(\tau^{0},\tau^{1})-f_{r^{\prime}}(\tau^{0},\tau^{1})|$
$\displaystyle\qquad=\frac{\Big{|}\exp(r(\tau^{1}))\Big{(}\exp(r^{\prime}(\tau^{0}))+\exp(r^{\prime}(\tau^{1}))\Big{)}-\exp(r^{\prime}(\tau^{1}))\Big{(}\exp(r(\tau^{0}))+\exp(r(\tau^{1}))\Big{)}\Big{|}}{\Big{(}\exp(r^{\prime}(\tau^{0}))+\exp(r^{\prime}(\tau^{1}))\Big{)}\Big{(}\exp(r(\tau^{0}))+\exp(r(\tau^{1}))\Big{)}}.$

Therefore, if
$\exp(r(\tau^{1}))\Big{(}\exp(r^{\prime}(\tau^{0}))+\exp(r^{\prime}(\tau^{1}))\Big{)}-\exp(r^{\prime}(\tau^{1}))\Big{(}\exp(r(\tau^{0}))+\exp(r(\tau^{1}))\Big{)}\geq
0$, then we have

$\displaystyle\Big{|}\exp(r(\tau^{1}))\Big{(}\exp(r^{\prime}(\tau^{0}))+\exp(r^{\prime}(\tau^{1}))\Big{)}-\exp(r^{\prime}(\tau^{1}))\Big{(}\exp(r(\tau^{0}))+\exp(r(\tau^{1}))\Big{)}\Big{|}$
$\displaystyle\leq$
$\displaystyle\exp(R\epsilon_{1})\exp(r(\tau^{1}))\Big{(}\exp(r(\tau^{0}))+\exp(r(\tau^{1}))\Big{)}-\exp(-R\epsilon_{1})\exp(r(\tau^{1}))\Big{(}\exp(r(\tau^{0}))+\exp(r(\tau^{1}))\Big{)}$
$\displaystyle=$
$\displaystyle(\exp(R\epsilon_{1})-\exp(-R\epsilon_{1}))\exp(r(\tau^{1}))\Big{(}\exp(r(\tau^{0}))+\exp(r(\tau^{1}))\Big{)}.$

Otherwise, we have

$\displaystyle\Big{|}\exp(r(\tau^{1}))\Big{(}\exp(r^{\prime}(\tau^{0}))+\exp(r^{\prime}(\tau^{1}))\Big{)}-\exp(r^{\prime}(\tau^{1}))\Big{(}\exp(r(\tau^{0}))+\exp(r(\tau^{1}))\Big{)}\Big{|}$
$\displaystyle\leq$
$\displaystyle\exp(R\epsilon_{1})\exp(r(\tau^{1}))\Big{(}\exp(r(\tau^{0}))+\exp(r(\tau^{1}))\Big{)}-\exp(r(\tau^{1}))\Big{(}\exp(r(\tau^{0}))+\exp(r(\tau^{1}))\Big{)}$
$\displaystyle=$
$\displaystyle(\exp(R\epsilon_{1})-1)\exp(r(\tau^{1}))\Big{(}\exp(r(\tau^{0}))+\exp(r(\tau^{1}))\Big{)}.$

Therefore we have

$\displaystyle|f_{r}(\tau^{0},\tau^{1})-f_{r^{\prime}}(\tau^{0},\tau^{1})|$
$\displaystyle\qquad\leq\frac{(\exp(R\epsilon_{1})-\exp(-R\epsilon_{1}))\exp(r(\tau^{1}))\Big{(}\exp(r(\tau^{0}))+\exp(r(\tau^{1}))\Big{)}}{\Big{(}\exp(r^{\prime}(\tau^{0}))+\exp(r^{\prime}(\tau^{1}))\Big{)}\Big{(}\exp(r(\tau^{0}))+\exp(r(\tau^{1}))\Big{)}}\leq\exp(2R\epsilon_{1})-1.$

This implies that for any $\epsilon\leq 1$,

$\displaystyle\log\mathcal{I}_{\mathcal{F}}(\epsilon/4)\leq\log\mathcal{I}_{d,B}\Big{(}\frac{2\ln
2}{R}\epsilon\Big{)}\leq\mathcal{O}\Big{(}d\log\frac{BR}{\epsilon}\Big{)},$

where $\mathcal{I}_{d,B}(\cdot)$ is the covering number of a $d$-dimensional
ball centered at the origin with radius $B$ with respect to $\ell_{2}$-norm
and the last step is from Wainwright, (2019). This concludes our proof.

##  Appendix B Proof of Theorem 1

The proof of Theorem 1 consists of two steps, deriving the guarantee of MLE
and analyzing the performance of pessimistic offline RL.

#### Step 1: MLE guarantee.

We first need to show that the confidence set $\mathcal{R}(\mathcal{D})$
contains the true reward $r^{\star}$ with high probability. This can be proved
via the following lemma which characterizes the guarantee of MLE:

######  Lemma 1 (Performance of MLE).

Fix any $\delta\in(0,1]$. Then with probability at least $1-\delta/2$ we have
that for all reward function $r\in\mathcal{G}_{r}$,

$\displaystyle\sum_{n=1}^{N}\log\bigg{(}\frac{P_{r}(o^{n}|\tau^{n,0},\tau^{n,1})}{P_{r^{\star}}(o^{n}|\tau^{n,0},\tau^{n,1})}\bigg{)}\leq
c_{\mathrm{MLE}}\log(\mathcal{N}_{\mathcal{G}_{r}}(1/N)/\delta),$

where $c_{\mathrm{MLE}}>0$ is a universal constant.

We defer the proof to Appendix B.1. Denote the event in Lemma 1 by
$\mathcal{E}_{1}$, then we know $\mathbb{P}(\mathcal{E}_{1})\geq 1-\delta/2$.
Under the event $\mathcal{E}_{1}$, we have

$\displaystyle\sum_{n=1}^{N}\log
P_{r^{\star}}(o^{n}|\tau^{n,0},\tau^{n,1})\geq\sum_{n=1}^{N}\log
P_{\widehat{r}}(o^{n}|\tau^{n,0},\tau^{n,1})-c_{\mathrm{MLE}}\log(\mathcal{N}_{\mathcal{G}_{r}}(1/N)/\delta),$

which implies that $r^{\star}\in\mathcal{R}(\mathcal{D})$ since we know
$r^{\star}\in\mathcal{G}_{r}$ from Assumption 2.

Nevertheless, the confidence set $\mathcal{R}(\mathcal{D})$ is constructed via
loglikelihood and we indeed prefer a bound on the total variation (TV)
distance between $P_{r}$ and $P_{r^{\star}}$ where
$r\in\mathcal{R}(\mathcal{D})$ to facilitate our subsequent analysis. We can
obtain such a bound as shown in the following lemma from the literature (Liu
et al., (2022)[Proposition 14],Zhan et al., 2022b [Lemma 9]):

######  Lemma 2.

With probability at least $1-\delta/2$, we have for all reward function
$r\in\mathcal{G}_{r}$ that

$\displaystyle\mathbb{E}_{\tau^{0}\sim\mu_{0},\tau^{1}\sim\mu_{1}}\bigg{[}\Big{\|}P_{r}(\cdot|\tau^{0},\tau^{1})-P_{r^{\star}}(\cdot|\tau^{0},\tau^{1})\Big{\|}_{1}^{2}\bigg{]}\leq\frac{c_{\mathrm{TV}}}{N}\bigg{(}\sum_{n=1}^{N}\log\bigg{(}\frac{P_{r^{\star}}(o^{n}|\tau^{n,0},\tau^{n,1})}{P_{r}(o^{n}|\tau^{n,0},\tau^{n,1})}\bigg{)}+\log(\mathcal{N}_{\mathcal{G}_{r}}(1/N)/\delta)\bigg{)},$

where $c_{\mathrm{TV}}>0$ is a universal constant.

Denote the event in Lemma 2 by $\mathcal{E}_{2}$ and then we know
$\mathbb{P}(\mathcal{E}_{2})\geq 1-\delta/2$. Then from Lemma 1 and Lemma 2 we
know that under event $\mathcal{E}_{1}\cap\mathcal{E}_{2}$, we have for all
$r\in\mathcal{R}(\mathcal{D})$:

$\displaystyle\mathbb{E}_{\tau^{0}\sim\mu_{0},\tau^{1}\sim\mu_{1}}\bigg{[}\Big{\|}P_{r}(\cdot|\tau^{0},\tau^{1})-P_{r^{\star}}(\cdot|\tau^{0},\tau^{1})\Big{\|}_{1}^{2}\bigg{]}\leq\frac{c\log(\mathcal{N}_{\mathcal{G}_{r}}(1/N)/\delta)}{N},$
(4)

where $c>0$ is a universal constant.

Then under Assumption 3, we can apply the mean value theorem between
$r^{\star}(\tau_{1})-r^{\star}(\tau_{0})$ and $r(\tau_{1})-r(\tau_{0})$ to (4)
and ensure for all $r\in\mathcal{R}(\mathcal{D})$ that

$\displaystyle\mathbb{E}_{\tau^{0}\sim\mu_{0},\tau^{1}\sim\mu_{1}}[|(r^{\star}(\tau_{1})-r^{\star}(\tau_{0}))-(r(\tau_{1})-r(\tau_{0}))|^{2}]\leq\frac{c\kappa^{2}\log(\mathcal{N}_{\mathcal{G}_{r}}(1/N)/\delta)}{N},$
(5)

where
$\kappa:=\frac{1}{\inf_{x\in[-r_{\mathrm{max}},r_{\mathrm{max}}]}\Phi^{\prime}(x)}$
measures the non-linearity of the link function $\Phi$.

#### Step 2: Pessimistic offline RL.

Let $r^{\mathrm{inf}}_{\pi}$ denote
$\mathop{\mathrm{argmin}}_{r\in\mathcal{R}(\mathcal{D})}J(\pi;r,P^{\star})-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r(\tau)]$.
Then we can bound the suboptimality of $\widehat{\pi}$ as follows:

$\displaystyle
J(\pi_{\mathrm{tar}};r^{\star},P^{\star})-J(\widehat{\pi};r^{\star},P^{\star})$
$\displaystyle=$
$\displaystyle\big{(}J(\pi_{\mathrm{tar}};r^{\star},P^{\star})-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r^{\star}(\tau)]\big{)}-\big{(}J(\widehat{\pi};r^{\star},P^{\star})-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r^{\star}(\tau)]\big{)}$
$\displaystyle\leq$
$\displaystyle\Big{(}\big{(}J(\pi_{\mathrm{tar}};r^{\star},P^{\star})-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r^{\star}(\tau)]\big{)}-\big{(}J(\pi_{\mathrm{tar}};r^{\mathrm{inf}}_{\pi_{\mathrm{tar}}},P^{\star})-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r^{\mathrm{inf}}_{\pi_{\mathrm{tar}}}(\tau)]\big{)}\Big{)}$
$\displaystyle-\Big{(}\big{(}J(\widehat{\pi};r^{\star},P^{\star})-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r^{\star}(\tau)]\big{)}-\big{(}J(\widehat{\pi};r^{\mathrm{inf}}_{\widehat{\pi}},P^{\star})-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r^{\mathrm{inf}}_{\widehat{\pi}}(\tau)]\big{)}\Big{)}$
$\displaystyle\leq$
$\displaystyle\big{(}J(\pi_{\mathrm{tar}};r^{\star},P^{\star})-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r^{\star}(\tau)]\big{)}-\big{(}J(\pi_{\mathrm{tar}};r^{\mathrm{inf}}_{\pi_{\mathrm{tar}}},P^{\star})-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r^{\mathrm{inf}}_{\pi_{\mathrm{tar}}}(\tau)]\big{)}$
$\displaystyle=$
$\displaystyle\mathbb{E}_{\tau^{0}\sim\pi_{\mathrm{tar}},\tau^{1}\sim\mu_{\mathrm{ref}}}[(r^{\star}(\tau^{0})-r^{\star}(\tau^{1}))-(r^{\mathrm{inf}}_{\pi_{\mathrm{tar}}}(\tau^{0})-r^{\mathrm{inf}}_{\pi_{\mathrm{tar}}}(\tau^{1}))]$
$\displaystyle\leq$ $\displaystyle
C_{r}(\mathcal{G}_{r},\pi_{\mathrm{tar}},\mu_{\mathrm{ref}})\sqrt{\mathbb{E}_{\tau_{0}\sim\mu_{0},\tau_{1}\sim\mu_{1}}[|r^{\star}(\tau^{0})-r^{\star}(\tau^{1})-r^{\mathrm{inf}}_{\pi_{\mathrm{tar}}}(\tau^{0})+r^{\mathrm{inf}}_{\pi_{\mathrm{tar}}}(\tau^{1})|^{2}]}$
$\displaystyle\leq$
$\displaystyle\sqrt{\frac{cC^{2}_{r}(\mathcal{G}_{r},\pi_{\mathrm{tar}},\mu_{\mathrm{ref}})\kappa^{2}\log(\mathcal{N}_{\mathcal{G}_{r}}(1/N)/\delta)}{N}},$

where the second step is due to
$\widehat{\pi}=\mathop{\mathrm{argmax}}_{\pi\in\Pi_{\mathrm{his}}}\min_{r\in\mathcal{R}(\mathcal{D})}J(\pi;r,P^{\star})-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r(\tau)]$,
the third step is due to
$r^{\mathrm{inf}}_{\widehat{\pi}}=\mathop{\mathrm{argmin}}_{r\in\mathcal{R}(\mathcal{D})}J(\widehat{\pi};r,P^{\star})-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r(\tau)]$,
the fifth step comes from the definition of
$C_{r}(\mathcal{G}_{r},\pi_{\mathrm{tar}},\mu_{\mathrm{ref}})$ (Definition 5)
and the last step leverages (5). This concludes our proof.

###  B.1 Proof of Lemma 1

The proof largely follows Zhan et al., 2022b . Suppose
$\overline{\mathcal{F}}$ is a $1/N$-bracket of $\mathcal{G}_{r}$ with
$|\overline{\mathcal{F}}|=\mathcal{N}_{\mathcal{G}_{r}}(1/N)$ and we denote
the set of all right brackets in $\overline{\mathcal{F}}$ by
$\widetilde{\mathcal{F}}$, i.e., $\widetilde{\mathcal{F}}:=\\{f:\exists
f^{\prime},\text{ such that }[f^{\prime},f]\in\overline{\mathcal{F}}\\}$. Then
fix any $f\in\widetilde{\mathcal{F}}$, we have:

$\displaystyle\mathbb{E}\bigg{[}\exp\bigg{(}\sum_{n=1}^{N}\log\bigg{(}\frac{f(o^{n}|\tau^{n,0},\tau^{n,1})}{P_{r^{\star}}(o^{n}|\tau^{n,0},\tau^{n,1})}\bigg{)}\bigg{)}\bigg{]}=\prod_{n=1}^{N}\mathbb{E}\bigg{[}\exp\bigg{(}\log\bigg{(}\frac{f(o^{n}|\tau^{n,0},\tau^{n,1})}{P_{r^{\star}}(o^{n}|\tau^{n,0},\tau^{n,1})}\bigg{)}\bigg{)}\bigg{]}$
$\displaystyle\qquad=\prod_{n=1}^{N}\mathbb{E}\bigg{[}\frac{f(o^{n}|\tau^{n,0},\tau^{n,1})}{P_{r^{\star}}(o^{n}|\tau^{n,0},\tau^{n,1})}\bigg{]}=\prod_{n=1}^{N}\mathbb{E}\bigg{[}\sum_{o}f(o|\tau^{n,0},\tau^{n,1})\bigg{]}\leq\bigg{(}1+\frac{1}{N}\bigg{)}^{N}\leq
e,$

where the first step is due to each sample in $\mathcal{D}$ is i.i.d., the
third step uses Tower property and the fourth step is from the fact that
$\overline{\mathcal{F}}$ is a minimum $1/N$-bracket.

Then by Markov’s inequality we have for any $\delta\in(0,1]$,

$\displaystyle\mathbb{P}\bigg{(}\sum_{n=1}^{N}\log\bigg{(}\frac{f(o^{n}|\tau^{n,0},\tau^{n,1})}{P_{r^{\star}}(o^{n}|\tau^{n,0},\tau^{n,1})}\bigg{)}>\log(1/\delta)\bigg{)}$
$\displaystyle\qquad\leq\mathbb{E}\bigg{[}\exp\bigg{(}\sum_{n=1}^{N}\log\bigg{(}\frac{f(o^{n}|\tau^{n,0},\tau^{n,1})}{P_{r^{\star}}(o^{n}|\tau^{n,0},\tau^{n,1})}\bigg{)}\bigg{)}\bigg{]}\cdot\exp[-\log(1/\delta)]\leq
e\delta.$

By union bound, we have for all $f\in\widetilde{\mathcal{F}}$,

$\displaystyle\mathbb{P}\bigg{(}\sum_{n=1}^{N}\log\bigg{(}\frac{f(o^{n}|\tau^{n,0},\tau^{n,1})}{P_{r^{\star}}(o^{n}|\tau^{n,0},\tau^{n,1})}\bigg{)}>c_{\mathrm{MLE}}\log(\mathcal{N}_{\mathcal{G}_{r}}(1/N)/\delta)\bigg{)}\leq\delta/2,$

where $c_{\mathrm{MLE}}>0$ is a universal constant.

Therefore from the definition of $1/N$-bracket net, we know for all
$r\in\mathcal{G}_{r}$, there exists $f\in\widetilde{\mathcal{F}}$ such that
$P_{r}(\cdot|\tau^{0},\tau^{1})\leq f(\cdot|\tau^{0},\tau^{1})$ for any
trajectories $(\tau^{0},\tau^{1})$. This implies that for all
$r\in\mathcal{G}_{r}$,

$\displaystyle\mathbb{P}\bigg{(}\sum_{n=1}^{N}\log\bigg{(}\frac{P_{r}(o^{n}|\tau^{n,0},\tau^{n,1})}{P_{r^{\star}}(o^{n}|\tau^{n,0},\tau^{n,1})}\bigg{)}>c_{\mathrm{MLE}}\log(\mathcal{N}_{\mathcal{G}_{r}}(1/N)/\delta)\bigg{)}\leq\delta/2,$

This concludes our proof.

##  Appendix C Proofs of Lower Bounds

###  C.1 Proof of Proposition 2

Given any $S,A,H$, consider a Markov Chain with horizon $H$, state space
${\mathcal{S}}$ and transition $P_{\mathrm{MC}}$ where $|{\mathcal{S}}|=S$ and
$P_{\mathrm{MC},h}:{\mathcal{S}}\times{\mathcal{S}}\mapsto[0,1]$ specifies the
transition probability for each step $h$. Then we can construct a MDP which
has the same state space ${\mathcal{S}}$ and horizon $H$. In addition, the
action space $\mathcal{A}$ satisfies $|\mathcal{A}|=A$ and the transition
$P^{\star}$ is independent from the action, i.e.,
$P^{\star}_{h}(s^{\prime}|s,a)=P_{\mathrm{MC},h}(s^{\prime}|s)$ for all
$a\in\mathcal{A}$.

We consider the case where $\pi_{\mathrm{tar}}$ is a Markovian policy. Then we
can define $\pi_{b,h}(\cdot|s)$ for every $h\in[H],s\in{\mathcal{S}}$ as
follows:

$\displaystyle\pi_{b,h}(a|s)=\begin{cases}\pi_{\mathrm{tar},h}(a|s)/C,&\text{
if }a=a^{1},\\\
\pi_{\mathrm{tar},h}(a|s)+(1-1/C)\pi_{\mathrm{tar},h}(a^{1}|s),&\text{ if
}a=a^{2},\\\ \pi_{\mathrm{tar},h}(a|s),&\text{ otherwise,}\end{cases}$

and we select $\mu_{0}=d^{\\{\pi_{b,h}\\}_{h=1}^{H}}$.

Then since $d^{\pi}_{h}(s)$ is fixed for any policy $\pi$, we know

$\displaystyle
C_{\mathrm{st}}=\sup_{s,a,h}\frac{\pi_{\mathrm{tar},h}(a|s)}{\pi_{b,h}(a|s)}=C.$

On the other hand, we have

$\displaystyle
C_{\mathrm{tr}}=\sup_{a_{1:H},s_{1:H}}\prod_{h\in[H]}\frac{\pi_{\mathrm{tar},h}(a_{h}|s_{h})}{\pi_{b,h}(a_{h}|s_{h})}=\sup_{s_{1:H}}\prod_{h\in[H]}\frac{\pi_{\mathrm{tar},h}(a^{1}|s_{h})}{\pi_{b,h}(a^{1}|s_{h})}=C^{H}.$

This concludes our proof.

###  C.2 Proof of Theorem 2

The proof is inspired by the hard instances in Rashidinejad et al., 2021b . We
consider the case $C\geq 2$ and $1<C<2$ respectively.

#### Case 1: $C\geq 2$.

Consider the case where there is only one state $s$ and two actions
$a^{1},a^{2}$. Set the dataset distribution $\mu_{0}=\mu_{1}$ where

$\displaystyle\mu_{0,h}(s,a^{1})=\frac{1}{C},\qquad\mu_{0,h}(s,a^{2})=1-\frac{1}{C},\qquad\forall
h\in[H],$

and $\mu_{0}(\tau)=\prod_{h=1}^{H}\mu_{0,h}(s_{h},a_{h})$ for all trajectory
$\tau=(s_{1},a_{1},\cdots,s_{H},a_{H})$.

We consider two different reward function $r^{1}$ and $r^{2}$:

$\displaystyle r^{1}(\tau)=\begin{cases}\frac{1}{2}+x,&\text{ if all the
actions in $\tau$ are $a^{1}$,}\\\ \frac{1}{2},&\text{ otherwise.}\end{cases}$
$\displaystyle r^{2}(\tau)=\begin{cases}\frac{1}{2}-x,&\text{ if all the
actions in $\tau$ are $a^{1}$,}\\\ \frac{1}{2},&\text{ otherwise.}\end{cases}$

Here $0<x<\frac{1}{2}$ is a quantity we will specify later and we denote the
special trajectory where all the actions are $a^{1}$ by $\tau^{\star}$. Then
we have two MDPs, $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$ whose reward
functions are $r^{1}$ and $r^{2}$ respectively. It can be easily verified that
$(\mathcal{M}_{1},\mu_{0})\in\Theta_{\mathrm{st}}(C),(\mathcal{M}_{2},\mu_{0})\in\Theta_{\mathrm{st}}(C)$.

Further, let $L(\pi;\mathcal{M})$ denote the suboptimality of policy $\pi$ in
$\mathcal{M}$, then we have for all policies $\pi$,

$\displaystyle L(\pi;\mathcal{M}_{1})+L(\pi;\mathcal{M}_{2})\geq x.$

Now we can apple Fano’s inequality, which leads to the following inequality

$\displaystyle\inf_{\widehat{\pi}}\sup_{\mathcal{M}\in\\{\mathcal{M}_{1},\mathcal{M}_{2}\\}}\mathbb{E}_{\mathcal{D}}[L(\pi,\mathcal{M})]\geq\frac{x}{2}\bigg{(}2-N\cdot\bm{\mathrm{KL}}\Big{(}\mu_{0}\otimes\mu_{1}\otimes
P_{r^{1}}\|\mu_{0}\otimes\mu_{1}\otimes P_{r^{2}}\Big{)}\bigg{)}.$

Now we only need to bound $\bm{\mathrm{KL}}\Big{(}\mu_{0}\otimes\mu_{1}\otimes
P_{r^{1}}\|\mu_{0}\otimes\mu_{1}\otimes P_{r^{2}}\Big{)}$, which can be
computed as follows:

$\displaystyle\bm{\mathrm{KL}}\Big{(}\mu_{0}\otimes\mu_{1}\otimes
P_{r^{1}}\|\mu_{0}\otimes\mu_{1}\otimes P_{r^{2}}\Big{)}$ $\displaystyle=$
$\displaystyle
2\sum_{\tau^{0}=\tau^{\star},\tau^{1}\neq\tau^{\star}}\mu_{0}(\tau^{0})\mu_{1}(\tau^{1})\bm{\mathrm{KL}}\big{(}\mathrm{Bern}(\sigma(x))\|\mathrm{Bern}(\sigma(-x))\big{)}$
$\displaystyle\leq$ $\displaystyle\frac{2\exp(1/2)x^{2}}{C^{H}}.$

Then by letting
$x=\min\bigg{\\{}\frac{1}{2},\sqrt{\frac{C^{H}}{2\exp(1/2)N}}\bigg{\\}}$, we
have

$\displaystyle\inf_{\widehat{\pi}}\sup_{\mathcal{M}\in\\{\mathcal{M}_{1},\mathcal{M}_{2}\\}}\mathbb{E}_{\mathcal{D}}[L(\pi,\mathcal{M})]\geq\frac{x}{2}=\min\bigg{\\{}\frac{1}{4},\sqrt{\frac{C^{H}}{8\exp(1/2)N}}\bigg{\\}}.$

#### Case 2: $1<C<2$.

Consider the case where there are two one states $s^{1},s^{2}$ and two actions
$a^{1},a^{2}$. We suppose the initial state distribution of $P_{0}^{\star}$ is
fixed as $P_{0}^{\star}(s^{1})=C-1$ and $P_{0}^{\star}(s^{2})=2-C$. In
addition, the state will stay the same throughout the whole episode. Then we
can set the dataset distribution $\mu_{0}=\mu_{1}$ where

$\displaystyle\mu_{0}(\tau)=\begin{cases}\frac{2(C-1)}{C}\cdot\frac{1}{2^{H}},&\text{
if the state of $\tau$ is $s^{1}$,}\\\ \frac{2-C}{C},&\text{ if the state of
$\tau$ is $s^{2}$ and the actions are all $a^{1}$,}\\\ 0,&\text{ if the state
of $\tau$ is $s^{2}$ and the actions contain $a^{2}$.}\end{cases}$

Then we know

$\displaystyle\mu_{0,h}(s^{1},a^{1})=\mu_{0,h}(s^{1},a^{2})=\frac{C-1}{C},$
$\displaystyle\mu_{0,h}(s^{2},a^{1})=\frac{2-C}{C},\mu_{0,h}(s^{2},a^{2})=0,\qquad\forall
h\in[H].$

We consider two different reward function $r^{1}$ and $r^{2}$:

$\displaystyle r^{1}(\tau)=\begin{cases}\frac{1}{2}+x,&\text{ if the state is
$s^{1}$ and all the actions in $\tau$ are $a^{1}$,}\\\ \frac{1}{2},&\text{
otherwise.}\end{cases}$ $\displaystyle
r^{2}(\tau)=\begin{cases}\frac{1}{2}-x,&\text{ if the state is $s^{1}$ and all
the actions in $\tau$ are $a^{1}$,}\\\ \frac{1}{2},&\text{
otherwise.}\end{cases}$

Here $0<x<\frac{1}{2}$ is a quantity we will specify later and we denote the
special trajectory where the state is $s^{1}$ and all the actions are $a^{1}$
by $\tau^{\star}$. Then we have two MDPs, $\mathcal{M}_{1}$ and
$\mathcal{M}_{2}$ whose reward functions are $r^{1}$ and $r^{2}$ respectively.
It can be easily verified that
$(\mathcal{M}_{1},\mu_{0})\in\Theta_{\mathrm{st}}(C),(\mathcal{M}_{2},\mu_{0})\in\Theta_{\mathrm{st}}(C)$.

In addition, we have for all policies $\pi$,

$\displaystyle L(\pi;\mathcal{M}_{1})+L(\pi;\mathcal{M}_{2})\geq(C-1)x.$

Therefore by Fano’s inequality, we have

$\displaystyle\inf_{\widehat{\pi}}\sup_{\mathcal{M}\in\\{\mathcal{M}_{1},\mathcal{M}_{2}\\}}\mathbb{E}_{\mathcal{D}}[L(\pi,\mathcal{M})]\geq\frac{(C-1)x}{2}\bigg{(}2-N\cdot\bm{\mathrm{KL}}\Big{(}\mu_{0}\otimes\mu_{1}\otimes
P_{r^{1}}\|\mu_{0}\otimes\mu_{1}\otimes P_{r^{2}}\Big{)}\bigg{)},$

where the KL divergence can be computed as follows:

$\displaystyle\bm{\mathrm{KL}}\Big{(}\mu_{0}\otimes\mu_{1}\otimes
P_{r^{1}}\|\mu_{0}\otimes\mu_{1}\otimes P_{r^{2}}\Big{)}$ $\displaystyle=$
$\displaystyle
2\sum_{\tau^{0}=\tau^{\star},\tau^{1}\neq\tau^{\star}}\mu_{0}(\tau^{0})\mu_{1}(\tau^{1})\bm{\mathrm{KL}}\big{(}\mathrm{Bern}(\sigma(x))\|\mathrm{Bern}(\sigma(-x))\big{)}$
$\displaystyle\leq$ $\displaystyle\frac{4(C-1)\exp(1/2)x^{2}}{2^{H}C}.$

Then by letting
$x=\min\bigg{\\{}\frac{1}{2},\sqrt{\frac{2^{H}C}{4\exp(1/2)(C-1)N}}\bigg{\\}}$,
we have

$\displaystyle\inf_{\widehat{\pi}}\sup_{\mathcal{M}\in\\{\mathcal{M}_{1},\mathcal{M}_{2}\\}}\mathbb{E}_{\mathcal{D}}[L(\pi,\mathcal{M})]\geq\frac{(C-1)x}{2}=\min\bigg{\\{}\frac{C-1}{4},\sqrt{\frac{2^{H}C(C-1)}{16\exp(1/2)N}}\bigg{\\}}.$

In conclusion, we have for any $C>1$ and $H\geq 1$,

$\displaystyle\inf_{\widehat{\pi}}\sup_{(\mathcal{M},\mu_{0})\in\Theta_{\mathrm{st}}(C)}\mathbb{E}_{\mathcal{D}}[J(\pi^{\star};r^{\star},P^{\star})-J(\widehat{\pi};r^{\star},P^{\star})]\gtrsim\min\bigg{\\{}C-1,\sqrt{\frac{(\max\\{C,2\\})^{H-1}(C-1)}{N}}\bigg{\\}}.$

###  C.3 Proof of Theorem 3

The proof is quite similar to the proof of Theorem 2. We consider the case
$C\geq 2$ and $1<C<2$ respectively.

#### Case 1: $C\geq 2$.

Consider the case where there is only one state $s$ and two actions
$a^{1},a^{2}$. Set the dataset distribution $\mu_{0}=\mu_{1}$ where

$\displaystyle\mu_{0}(\tau^{\star})=\frac{1}{C},\qquad\mu_{0}(\tau^{\dagger})=1-\frac{1}{C},$

where $\tau^{\star}$ is the trajecotry where the actions are all $a^{1}$ and
$\tau^{\dagger}$ is the trajecotry where the actions are all $a^{2}$.

We consider two different reward function $r^{1}$ and $r^{2}$:

$\displaystyle r^{1}(\tau)=\begin{cases}\frac{1}{2}+x,&\text{ if all the
actions in $\tau$ are $a^{1}$,}\\\ \frac{1}{2},&\text{ otherwise.}\end{cases}$
$\displaystyle r^{2}(\tau)=\begin{cases}\frac{1}{2}-x,&\text{ if all the
actions in $\tau$ are $a^{1}$,}\\\ \frac{1}{2},&\text{ otherwise.}\end{cases}$

Here $0<x<\frac{1}{2}$ is a quantity we will specify later. Then we have two
MDPs, $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$ whose reward functions are
$r^{1}$ and $r^{2}$ respectively. It can be easily verified that
$(\mathcal{M}_{1},\mu_{0})\in\Theta_{\mathrm{tr}}(C),(\mathcal{M}_{2},\mu_{0})\in\Theta_{\mathrm{tr}}(C)$.

Further, let $L(\pi;\mathcal{M})$ denote the suboptimality of policy $\pi$ in
$\mathcal{M}$, then we have for all policies $\pi$,

$\displaystyle L(\pi;\mathcal{M}_{1})+L(\pi;\mathcal{M}_{2})\geq x.$

Now we can apple Fano’s inequality, which leads to the following inequality

$\displaystyle\inf_{\widehat{\pi}}\sup_{\mathcal{M}\in\\{\mathcal{M}_{1},\mathcal{M}_{2}\\}}\mathbb{E}_{\mathcal{D}}[L(\pi,\mathcal{M})]\geq\frac{x}{2}\bigg{(}2-N\cdot\bm{\mathrm{KL}}\Big{(}\mu_{0}\otimes\mu_{1}\otimes
P_{r^{1}}\|\mu_{0}\otimes\mu_{1}\otimes P_{r^{2}}\Big{)}\bigg{)}.$

Now we only need to bound $\bm{\mathrm{KL}}\Big{(}\mu_{0}\otimes\mu_{1}\otimes
P_{r^{1}}\|\mu_{0}\otimes\mu_{1}\otimes P_{r^{2}}\Big{)}$, which can be
computed as follows:

$\displaystyle\bm{\mathrm{KL}}\Big{(}\mu_{0}\otimes\mu_{1}\otimes
P_{r^{1}}\|\mu_{0}\otimes\mu_{1}\otimes P_{r^{2}}\Big{)}$ $\displaystyle=$
$\displaystyle
2\sum_{\tau^{0}=\tau^{\star},\tau^{1}=\tau^{\dagger}}\mu_{0}(\tau^{0})\mu_{1}(\tau^{1})\bm{\mathrm{KL}}\big{(}\mathrm{Bern}(\sigma(x))\|\mathrm{Bern}(\sigma(-x))\big{)}$
$\displaystyle\leq$ $\displaystyle\frac{2\exp(1/2)x^{2}}{C}.$

Then by letting
$x=\min\bigg{\\{}\frac{1}{2},\sqrt{\frac{C}{2\exp(1/2)N}}\bigg{\\}}$, we have

$\displaystyle\inf_{\widehat{\pi}}\sup_{\mathcal{M}\in\\{\mathcal{M}_{1},\mathcal{M}_{2}\\}}\mathbb{E}_{\mathcal{D}}[L(\pi,\mathcal{M})]\geq\frac{x}{2}=\min\bigg{\\{}\frac{1}{4},\sqrt{\frac{C}{8\exp(1/2)N}}\bigg{\\}}.$

#### Case 2: $1<C<2$.

Consider the case where there are two one states $s^{1},s^{2}$ and two actions
$a^{1},a^{2}$. We suppose the initial state distribution of $P_{0}^{\star}$ is
fixed as $P_{0}^{\star}(s^{1})=C-1$ and $P_{0}^{\star}(s^{2})=2-C$. In
addition, the state will stay the same throughout the whole episode. Then we
can set the dataset distribution $\mu_{0}=\mu_{1}$ where

$\displaystyle\mu_{0}(\tau)=\begin{cases}\frac{2(C-1)}{C}\cdot\frac{1}{2},&\text{
if the state of $\tau$ is $s^{1}$ and the actions are all $a^{1}$ or all
$a^{2}$,}\\\ \frac{2-C}{C},&\text{ if the state of $\tau$ is $s^{2}$ and the
actions are all $a^{1}$,}\\\ 0,&\text{ if the state of $\tau$ is $s^{2}$ and
the actions contain $a^{2}$.}\end{cases}$

Let $\tau^{\star}$ be the trajectory where the state is $s^{1}$ and the
actions are all $a^{1}$.

We further consider two different reward function $r^{1}$ and $r^{2}$:

$\displaystyle r^{1}(\tau)=\begin{cases}\frac{1}{2}+x,&\text{ if the state is
$s^{1}$ and all the actions in $\tau$ are $a^{1}$,}\\\ \frac{1}{2},&\text{
otherwise.}\end{cases}$ $\displaystyle
r^{2}(\tau)=\begin{cases}\frac{1}{2}-x,&\text{ if the state is $s^{1}$ and all
the actions in $\tau$ are $a^{1}$,}\\\ \frac{1}{2},&\text{
otherwise.}\end{cases}$

Here $0<x<\frac{1}{2}$ is a quantity we will specify later. Then we have two
MDPs, $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$ whose reward functions are
$r^{1}$ and $r^{2}$ respectively. It can be easily verified that
$(\mathcal{M}_{1},\mu_{0})\in\Theta_{\mathrm{tr}}(C),(\mathcal{M}_{2},\mu_{0})\in\Theta_{\mathrm{tr}}(C)$.

In addition, we have for all policies $\pi$,

$\displaystyle L(\pi;\mathcal{M}_{1})+L(\pi;\mathcal{M}_{2})\geq(C-1)x.$

Therefore by Fano’s inequality, we have

$\displaystyle\inf_{\widehat{\pi}}\sup_{\mathcal{M}\in\\{\mathcal{M}_{1},\mathcal{M}_{2}\\}}\mathbb{E}_{\mathcal{D}}[L(\pi,\mathcal{M})]\geq\frac{(C-1)x}{2}\bigg{(}2-N\cdot\bm{\mathrm{KL}}\Big{(}\mu_{0}\otimes\mu_{1}\otimes
P_{r^{1}}\|\mu_{0}\otimes\mu_{1}\otimes P_{r^{2}}\Big{)}\bigg{)},$

where the KL divergence can be computed as follows:

$\displaystyle\bm{\mathrm{KL}}\Big{(}\mu_{0}\otimes\mu_{1}\otimes
P_{r^{1}}\|\mu_{0}\otimes\mu_{1}\otimes P_{r^{2}}\Big{)}$ $\displaystyle=$
$\displaystyle
2\sum_{\tau^{0}=\tau^{\star},\tau^{1}\neq\tau^{\star}}\mu_{0}(\tau^{0})\mu_{1}(\tau^{1})\bm{\mathrm{KL}}\big{(}\mathrm{Bern}(\sigma(x))\|\mathrm{Bern}(\sigma(-x))\big{)}$
$\displaystyle\leq$ $\displaystyle\frac{2(C-1)\exp(1/2)x^{2}}{C}.$

Then by letting
$x=\min\bigg{\\{}\frac{1}{2},\sqrt{\frac{C}{2\exp(1/2)(C-1)N}}\bigg{\\}}$, we
have

$\displaystyle\inf_{\widehat{\pi}}\sup_{\mathcal{M}\in\\{\mathcal{M}_{1},\mathcal{M}_{2}\\}}\mathbb{E}_{\mathcal{D}}[L(\pi,\mathcal{M})]\geq\frac{(C-1)x}{2}=\min\bigg{\\{}\frac{C-1}{4},\sqrt{\frac{(C-1)}{8\exp(1/2)N}}\bigg{\\}}.$

In conclusion, we have for any $C>1$ and $H\geq 1$,

$\displaystyle\inf_{\widehat{\pi}}\sup_{(\mathcal{M},\mu_{0})\in\Theta_{\mathrm{st}}(C)}\mathbb{E}_{\mathcal{D}}[J(\pi^{\star};r^{\star},P^{\star})-J(\widehat{\pi};r^{\star},P^{\star})]\gtrsim\min\bigg{\\{}C-1,\sqrt{\frac{C-1}{N}}\bigg{\\}}.$

##  Appendix D Proof of Theorem 4

The proof still consists of two steps, deriving the guarantee of MLE and
analyzing the performance of pessimistic offline RL.

#### Step 1: MLE guarantee.

Note that Lemma 1 and Lemma 2 still applies here. Let $\mathcal{E}_{1}$ and
$\mathcal{E}_{2}$ denote the event in Lemma 1 and Lemma 2 respectively.
Following almost the same arguments, we have the following guarantee for the
estimation of the system dynamics:

######  Lemma 3.

Under Assumption 4, with probability at least $1-\delta/2$, the following
event holds true:

$\displaystyle(1)P^{\star}_{h}\in\mathcal{P}_{h}(\mathcal{D}),P_{0}^{\star}\in\mathcal{P}_{\mathrm{ini}}(\mathcal{D}),\qquad\forall
h\in[H-1],$
$\displaystyle(2)\mathbb{E}_{(s_{h},a_{h})\sim\mu_{0,h}}\bigg{[}\Big{\|}P_{h}(\cdot|s,a)-P^{\star}_{h}(\cdot|s,a)\Big{\|}_{1}^{2}\bigg{]}+\mathbb{E}_{(s_{h},a_{h})\sim\mu_{1,h}}\bigg{[}\Big{\|}P_{h}(\cdot|s,a)-P^{\star}_{h}(\cdot|s,a)\Big{\|}_{1}^{2}\bigg{]}$
$\displaystyle\qquad\leq\frac{c\log(H\mathcal{N}_{\mathcal{G}_{P_{h}}}(1/N)/\delta)}{N},\qquad\forall
h\in[H-1],P_{h}\in\mathcal{P}_{h}(\mathcal{D}),$
$\displaystyle(3)\mathbb{E}_{s\sim\mu_{0,1}}\bigg{[}\Big{\|}P_{0}(s)-P_{0}^{\star}(s)\Big{\|}_{1}^{2}\bigg{]}+\mathbb{E}_{s\sim\mu_{1,1}}\bigg{[}\Big{\|}P_{0}(s)-P_{0}^{\star}(s)\Big{\|}_{1}^{2}\bigg{]}$
$\displaystyle\qquad\leq\frac{c\log(H\mathcal{N}_{\mathcal{G}_{P_{0}}}(1/N)/\delta)}{N},\qquad\forall
P_{0}\in\mathcal{P}_{0}(\mathcal{D}).$

The proof is omitted here. Let $\mathcal{E}_{3}$ denote the event in Lemma 3.

#### Step 2: Pessimistic offline RL.

We first introduce the following lemma which suggests that under event
$\mathcal{E}_{3}$, we can evaluate the expected cumulative reward of
$\pi_{\mathrm{tar}}$ with respect to any reward function $r\in\mathcal{G}_{r}$
via the system dynamics $P_{h}\in\mathcal{P}_{h}(\mathcal{D})$:

######  Lemma 4.

Suppose Asusmption 3 is true. Then under $\mathcal{E}_{3}$, we have for all
reward function $r\in\mathcal{G}_{r}$ and $P=(\\{P_{h}\\}_{h=0}^{H-1})$ where
$P_{h}\in\mathcal{P}_{h}(\mathcal{D})$ that

$\displaystyle J(\pi_{\mathrm{tar}};r,P^{\star})-J(\pi_{\mathrm{tar}};r,P)\leq
Hr_{\mathrm{max}}\sqrt{\frac{cC^{2}_{P}(\\{\mathcal{G}_{P_{h}}\\},\pi_{\mathrm{tar}})\log(H\mathcal{N}_{P}(1/N)/\delta)}{N}},$

where $\mathcal{N}_{P}=\max_{0\leq h\leq
H-1}\\{\mathcal{N}_{\mathcal{G}_{P_{h}}}\\}$.

The proof is deferred to Appendix D.1.

Let $(r^{\mathrm{inf}}_{\pi},P^{\mathrm{inf}}_{\pi})$ denote
$\mathop{\mathrm{argmin}}_{r\in\mathcal{R}(\mathcal{D}),P\in\mathcal{P}_{\mathrm{ini}}(\mathcal{D})\times\prod_{h=1}^{H-1}\mathcal{P}_{h}(\mathcal{D})}J(\pi;r,P)-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r(\tau)]$.
Then under the event $\mathcal{E}_{3}$, we can bound the suboptimality of
$\widehat{\pi}$ as follows:

$\displaystyle
J(\pi_{\mathrm{tar}};r^{\star},P^{\star})-J(\widehat{\pi};r^{\star},P^{\star})$
$\displaystyle=$
$\displaystyle\big{(}J(\pi_{\mathrm{tar}};r^{\star},P^{\star})-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r^{\star}(\tau)]\big{)}-\big{(}J(\widehat{\pi};r^{\star},P^{\star})-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r^{\star}(\tau)]\big{)}$
$\displaystyle=$
$\displaystyle\Big{(}\big{(}J(\pi_{\mathrm{tar}};r^{\star},P^{\star})-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r^{\star}(\tau)]\big{)}-\big{(}J(\pi_{\mathrm{tar}};r^{\mathrm{inf}}_{\pi_{\mathrm{tar}}},P^{\star})-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r^{\mathrm{inf}}_{\pi_{\mathrm{tar}}}(\tau)]\big{)}\Big{)}$
$\displaystyle+\Big{(}\big{(}J(\pi_{\mathrm{tar}};r^{\mathrm{inf}}_{\pi_{\mathrm{tar}}},P^{\star})-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r^{\mathrm{inf}}_{\pi_{\mathrm{tar}}}(\tau)]\big{)}-\big{(}J(\pi_{\mathrm{tar}};r^{\mathrm{inf}}_{\pi_{\mathrm{tar}}},P^{\mathrm{inf}}_{\pi_{\mathrm{tar}}})-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r^{\mathrm{inf}}_{\pi_{\mathrm{tar}}}(\tau)]\big{)}\Big{)}$
$\displaystyle+\Big{(}\big{(}J(\pi_{\mathrm{tar}};r^{\mathrm{inf}}_{\pi_{\mathrm{tar}}},P^{\mathrm{inf}}_{\pi_{\mathrm{tar}}})-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r^{\mathrm{inf}}_{\pi_{\mathrm{tar}}}(\tau)]\big{)}-\big{(}J(\widehat{\pi};r^{\mathrm{inf}}_{\widehat{\pi}},P^{\mathrm{inf}}_{\widehat{\pi}})-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r^{\mathrm{inf}}_{\widehat{\pi}}(\tau)]\big{)}\Big{)}$
$\displaystyle+\Big{(}\big{(}J(\widehat{\pi};r^{\mathrm{inf}}_{\widehat{\pi}},P^{\mathrm{inf}}_{\widehat{\pi}})-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r^{\mathrm{inf}}_{\widehat{\pi}}(\tau)]\big{)}-\big{(}J(\widehat{\pi};r^{\star},P^{\star})-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r^{\star}(\tau)]\big{)}\Big{)}$
$\displaystyle\leq$
$\displaystyle\Big{(}\big{(}J(\pi_{\mathrm{tar}};r^{\star},P^{\star})-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r^{\star}(\tau)]\big{)}-\big{(}J(\pi_{\mathrm{tar}};r^{\mathrm{inf}}_{\pi_{\mathrm{tar}}},P^{\star})-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r^{\mathrm{inf}}_{\pi_{\mathrm{tar}}}(\tau)]\big{)}\Big{)}$
$\displaystyle+\Big{(}\big{(}J(\pi_{\mathrm{tar}};r^{\mathrm{inf}}_{\pi_{\mathrm{tar}}},P^{\star})-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r^{\mathrm{inf}}_{\pi_{\mathrm{tar}}}(\tau)]\big{)}-\big{(}J(\pi_{\mathrm{tar}};r^{\mathrm{inf}}_{\pi_{\mathrm{tar}}},P^{\mathrm{inf}}_{\pi_{\mathrm{tar}}})-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r^{\mathrm{inf}}_{\pi_{\mathrm{tar}}}(\tau)]\big{)}\Big{)}$
$\displaystyle+\Big{(}\big{(}J(\widehat{\pi};r^{\mathrm{inf}}_{\widehat{\pi}},P^{\mathrm{inf}}_{\widehat{\pi}})-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r^{\mathrm{inf}}_{\widehat{\pi}}(\tau)]\big{)}-\big{(}J(\widehat{\pi};r^{\star},P^{\star})-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r^{\star}(\tau)]\big{)}\Big{)}$
$\displaystyle\leq$
$\displaystyle\Big{(}\big{(}J(\pi_{\mathrm{tar}};r^{\star},P^{\star})-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r^{\star}(\tau)]\big{)}-\big{(}J(\pi_{\mathrm{tar}};r^{\mathrm{inf}}_{\pi_{\mathrm{tar}}},P^{\star})-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r^{\mathrm{inf}}_{\pi_{\mathrm{tar}}}(\tau)]\big{)}\Big{)}$
$\displaystyle+\Big{(}\big{(}J(\pi_{\mathrm{tar}};r^{\mathrm{inf}}_{\pi_{\mathrm{tar}}},P^{\star})-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r^{\mathrm{inf}}_{\pi_{\mathrm{tar}}}(\tau)]\big{)}-\big{(}J(\pi_{\mathrm{tar}};r^{\mathrm{inf}}_{\pi_{\mathrm{tar}}},P^{\mathrm{inf}}_{\pi_{\mathrm{tar}}})-\mathbb{E}_{\tau\sim\mu_{\mathrm{ref}}}[r^{\mathrm{inf}}_{\pi_{\mathrm{tar}}}(\tau)]\big{)}\Big{)}$
$\displaystyle\leq$
$\displaystyle\sqrt{\frac{cC^{2}_{r}(\mathcal{G}_{r},\pi_{\mathrm{tar}},\mu_{\mathrm{ref}})\kappa^{2}\log(\mathcal{N}_{\mathcal{G}_{r}}(1/N)/\delta)}{N}}+Hr_{\mathrm{max}}\sqrt{\frac{cC^{2}_{P}(\\{\mathcal{G}_{P_{h}}\\},\pi_{\mathrm{tar}})\log(H\mathcal{N}_{P}(1/N)/\delta)}{N}},$

where the third and fourth step are due to the definition of
$\widehat{\pi},(r^{\mathrm{inf}}_{\widehat{\pi}},P^{\mathrm{inf}}_{\widehat{\pi}})$
and (1) in Lemma 3. The last step comes from Lemma 4 and the proof of Theorem
1. This concludes our proof.

###  D.1 Proof of Lemma 4

Let $P^{h}$ be the system dynamics
$(P_{0}^{\star},\\{P^{\star}_{t}\\}_{t=1}^{h},\\{P_{t}\\}_{t=h+1}^{H-1})$ for
all $0\leq h\leq H-1$. Then we have

$\displaystyle
J(\pi_{\mathrm{tar}};r,P^{\star})-J(\pi_{\mathrm{tar}};r,P)=\sum_{h=1}^{H-1}(J(\pi_{\mathrm{tar}};r,P^{h})-J(\pi_{\mathrm{tar}};r,P^{h-1}))+(J(\pi_{\mathrm{tar}};r,P^{0})-J(\pi_{\mathrm{tar}};r,P)).$

For any $h\in[H-1]$, we have

$\displaystyle J(\pi_{\mathrm{tar}};r,P^{h})-J(\pi_{\mathrm{tar}};r,P^{h-1})$
$\displaystyle=$
$\displaystyle\mathbb{E}_{(s_{1},a_{1},\cdots,s_{h},a_{h})\sim(\pi_{\mathrm{tar}},P^{\star})}\Big{[}\sum_{s_{h+1}}P^{\star}_{h}(s_{h+1}|s_{h},a_{h})\mathbb{E}_{(\pi_{\mathrm{tar}},P)}\big{[}r(\tau)|s_{1},a_{1},\cdots,s_{h+1}\big{]}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad-\sum_{s_{h+1}}P_{h}(s_{h+1}|s_{h},a_{h})\mathbb{E}_{(\pi_{\mathrm{tar}},P)}\big{[}r(\tau)|s_{1},a_{1},\cdots,s_{h+1}\big{]}\Big{]}$
$\displaystyle=$
$\displaystyle\mathbb{E}_{(s_{1},a_{1},\cdots,s_{h},a_{h})\sim(\pi_{\mathrm{tar}},P^{\star})}\Big{[}\sum_{s_{h+1}}(P^{\star}_{h}(s_{h+1}|s_{h},a_{h})-P_{h}(s_{h+1}|s_{h},a_{h}))\mathbb{E}_{(\pi_{\mathrm{tar}},P)}\big{[}r(\tau)|s_{1},a_{1},\cdots,s_{h+1}\big{]}\Big{]}$
$\displaystyle\leq$ $\displaystyle
r_{\mathrm{max}}\mathbb{E}_{(s_{h},a_{h})\sim(\pi_{\mathrm{tar}},P^{\star})}\Big{[}\big{\|}P^{\star}_{h}(\cdot|s_{h},a_{h})-P_{h}(\cdot|s_{h},a_{h})\big{\|}_{1}\Big{]}$
$\displaystyle\leq$ $\displaystyle
r_{\mathrm{max}}\sqrt{\frac{cC^{2}_{P}(\pi_{\mathrm{tar}})\log(H\mathcal{N}_{\mathcal{G}_{P_{h}}}(1/N)/\delta)}{N}},$

where
$\mathbb{E}_{(\pi_{\mathrm{tar}},P)}\big{[}\cdot|s_{1},a_{1},\cdots,s_{h+1}\big{]}$
is the distribution of the trajectory $\tau$ when executing policy
$\pi_{\mathrm{tar}}$ under the transition probability
$\\{P_{t}\\}_{t=h+1}^{H-1}$ while fixing the history to be
$s_{1},a_{1},\cdots,s_{h+1}$. Here the first step utilizes the Tower property,
the third and fourth step uses Cuachy-Schwartz inequality and the last step
comes from Lemma 3.

For $J(\pi_{\mathrm{tar}};r,P^{0})-J(\pi_{\mathrm{tar}};r,P)$, similarly we
have

$\displaystyle J(\pi_{\mathrm{tar}};r,P^{0})-J(\pi_{\mathrm{tar}};r,P)\leq
r_{\mathrm{max}}\sqrt{\frac{cC^{2}_{P}(\pi_{\mathrm{tar}})\log(H\mathcal{N}_{\mathcal{G}_{P_{0}}}(1/N)/\delta)}{N}}.$

Therefore we conclude that

$\displaystyle J(\pi_{\mathrm{tar}};r,P^{\star})-J(\pi_{\mathrm{tar}};r,P)\leq
Hr_{\mathrm{max}}\sqrt{\frac{cC^{2}_{P}(\pi_{\mathrm{tar}})\log(H\mathcal{N}_{P}(1/N)/\delta)}{N}}.$

##  Appendix E Proof of Theorem 5

We first derive the guarantee of MLE for estimating $A^{\star}$. Similar to
Lemma 1 and Lemma 2, we have the following lemma in the action-based
comparison setting:

######  Lemma 5.

Under Assumption 7, with probability at least $1-\delta$, the following event
holds true:

$\displaystyle\mathbb{E}_{s\sim\mu_{h},a^{0}\sim\mu_{0,h}(\cdot|s),a^{1}\sim\mu_{1,h}(\cdot|s)}\bigg{[}\Big{\|}P_{\widehat{A}_{h}}(\cdot|s,a^{0},a^{1})-P_{A^{\star}_{h}}(\cdot|s,a^{0},a^{1})\Big{\|}_{1}^{2}\bigg{]}\leq\frac{c\log(H\mathcal{N}_{\mathcal{G}_{A_{h}}}(1/N)/\delta)}{N},\forall
h\in[H].$

The proof is omitted here. Let $\mathcal{E}_{4}$ denote the event in Lemma 5.
Then under Assumption 8, we can apply the mean value theorem and obtain that
under $\mathcal{E}_{4}$, we have for all $h\in[H]$ that

$\displaystyle\mathbb{E}_{s\sim\mu_{h},a^{0}\sim\mu_{0,h}(\cdot|s),a^{1}\sim\mu_{1,h}(\cdot|s)}\bigg{[}|A^{\star}_{h}(s,a^{0})-A^{\star}_{h}(s,a^{1})-\widehat{A}_{h}(s,a^{0})+\widehat{A}_{h}(s,a^{1})|^{2}\bigg{]}$
$\displaystyle\qquad\leq\frac{c\kappa^{2}\log(H\mathcal{N}_{\mathcal{G}_{A_{h}}}(1/N)/\delta)}{N},\forall
h\in[H].$ (6)

Recall that
$\kappa=\frac{1}{\inf_{x\in[-r_{\mathrm{max}},r_{\mathrm{max}}]}\Phi^{\prime}(x)}$.

On the other hand, note that we have the following performance lemma:

######  Lemma 6.

For any deterministic Markovian policies $\pi$ and $\pi^{\prime}$, we have

$\displaystyle
J(\pi;r^{\star},P^{\star})-J(\pi^{\prime};r^{\star},P^{\star})=\sum_{h=1}^{H}\mathbb{E}_{s\sim
d^{\pi^{\prime}}_{h}}\Big{[}Q^{\pi}_{h}(s,\pi(s))-Q^{\pi}_{h}(s,\pi^{\prime}(s))\Big{]}$

The proof is deferred to Appendix E.1.

The rest of the proof largely follows Uehara et al., (2023). Under the event
$\mathcal{E}_{4}$, we can bound the suboptimality of $\widehat{\pi}$ as
follows:

$\displaystyle
J(\pi^{\star};r^{\star},P^{\star})-J(\widehat{\pi};r^{\star},P^{\star})\leq
r_{\mathrm{max}}\sum_{h=1}^{H}\mathbb{E}_{s\sim
d^{\pi^{\star}}_{h}}\Big{[}\mathbbm{1}(\pi^{\star}_{h}(s)\neq\widehat{\pi}_{h}(s))\cdot\mathbbm{1}(Q^{\star}_{h}(s,\widehat{\pi}_{h}(s))<Q^{\star}_{h}(s,\pi^{\star}_{h}(s)))\Big{]}$
$\displaystyle\leq$ $\displaystyle
r_{\mathrm{max}}\sum_{h=1}^{H}\mathbb{E}_{s\sim
d^{\pi^{\star}}_{h}}\bigg{[}\sum_{a\in\mathcal{A}}\mathbbm{1}\Big{(}\widehat{A}_{h}(s,a)\geq\widehat{A}_{h}(s,\pi^{\star}_{h}(s))\Big{)}\cdot\mathbbm{1}\Big{(}Q^{\star}_{h}(s,a)<Q^{\star}_{h}(s,\pi^{\star}_{h}(s))\Big{)}\bigg{]},$

where the first step comes from Lemma 6 and the second step is due to the
definition of $\widehat{\pi}$. Then for any $\alpha>0$, we have

$\displaystyle\mathbb{E}_{s\sim
d^{\pi^{\star}}_{h}}\bigg{[}\sum_{a\in\mathcal{A}}\mathbbm{1}\Big{(}\widehat{A}_{h}(s,a)\geq\widehat{A}_{h}(s,\pi^{\star}_{h}(s))\Big{)}\cdot\mathbbm{1}\Big{(}Q^{\star}_{h}(s,a)<Q^{\star}_{h}(s,\pi^{\star}_{h}(s))\Big{)}\bigg{]}$
$\displaystyle\leq$ $\displaystyle\mathbb{E}_{s\sim
d^{\pi^{\star}}_{h}}\bigg{[}\sum_{a\in\mathcal{A}}\mathbbm{1}\Big{(}Q^{\star}_{h}(s,\pi^{\star}_{h}(s))>Q^{\star}_{h}(s,a)\geq
Q^{\star}_{h}(s,\pi^{\star}_{h}(s))-\alpha\Big{)}\bigg{]}$
$\displaystyle+\mathbb{E}_{s\sim
d^{\pi^{\star}}_{h}}\bigg{[}\sum_{a\in\mathcal{A}}\mathbbm{1}\Big{(}Q^{\star}_{h}(s,\pi^{\star}_{h}(s))-Q^{\star}_{h}(s,a)-\widehat{A}_{h}(s,\pi^{\star}_{h}(s))+\widehat{A}_{h}(s,a)\geq\alpha\Big{)}\bigg{]}.$

By Assumption 6, we have

$\displaystyle\mathbb{E}_{s\sim
d^{\pi^{\star}}_{h}}\bigg{[}\sum_{a\in\mathcal{A}}\mathbbm{1}\Big{(}Q^{\star}_{h}(s,\pi^{\star}_{h}(s))>Q^{\star}_{h}(s,a)\geq
Q^{\star}_{h}(s,\pi^{\star}_{h}(s))-\alpha\Big{)}\bigg{]}\leq|\mathcal{A}|(\alpha/\alpha_{0})^{\beta}.$

For the second term, we have

$\displaystyle\mathbb{E}_{s\sim
d^{\pi^{\star}}_{h}}\bigg{[}\sum_{a\in\mathcal{A}}\mathbbm{1}\Big{(}Q^{\star}_{h}(s,\pi^{\star}_{h}(s))-Q^{\star}_{h}(s,a)-\widehat{A}_{h}(s,\pi^{\star}_{h}(s))+\widehat{A}_{h}(s,a)\geq\alpha\Big{)}\bigg{]}$
$\displaystyle=$ $\displaystyle\frac{1}{\alpha^{2}}\mathbb{E}_{s\sim
d^{\pi^{\star}}_{h}}\bigg{[}\sum_{a\in\mathcal{A}}\alpha^{2}\mathbbm{1}\Big{(}A^{\star}_{h}(s,\pi^{\star}_{h}(s))-A^{\star}_{h}(s,a)-\widehat{A}_{h}(s,\pi^{\star}_{h}(s))+\widehat{A}_{h}(s,a)\geq\alpha\Big{)}\bigg{]}$
$\displaystyle\leq$ $\displaystyle\frac{1}{\alpha^{2}}\mathbb{E}_{s\sim
d^{\pi^{\star}}_{h}}\bigg{[}\sum_{a\in\mathcal{A}}\Big{|}A^{\star}_{h}(s,\pi^{\star}_{h}(s))-A^{\star}_{h}(s,a)-\widehat{A}_{h}(s,\pi^{\star}_{h}(s))+\widehat{A}_{h}(s,a)\Big{|}^{2}\bigg{]}$
$\displaystyle\leq$
$\displaystyle\frac{c|\mathcal{A}|C_{\mathrm{act}}\kappa^{2}\log(H\mathcal{N}_{\mathcal{G}_{A_{h}}}(1/N)/\delta)}{\alpha^{2}N},$

where the last step comes from the definition of $C_{\mathrm{act}}$ and (6).

Therefore by picking appropriate $\alpha$, we have with probability at least
$1-\delta$ that

$\displaystyle
J(\pi^{\star};r^{\star},P^{\star})-J(\widehat{\pi};r^{\star},P^{\star})\leq
cH|\mathcal{A}|\bigg{(}\frac{2}{\beta}\bigg{)}^{\frac{\beta-2}{\beta+2}}\bigg{(}\frac{1}{\alpha_{0}}\bigg{)}^{\frac{2\beta}{\beta+2}}\bigg{(}\frac{\kappa^{2}C_{\mathrm{act}}\log(H\mathcal{N}_{\mathcal{G}_{A}}(1/N)/\delta)}{N}\bigg{)}^{\frac{\beta}{\beta+2}}.$

###  E.1 Proof of Lemma 6

For any two policies $\pi$ and $\pi^{\prime}$, we have that

$\displaystyle J(\pi^{\prime};r^{\star},P^{\star})-J(\pi;r^{\star},P^{\star})$
$\displaystyle=$
$\displaystyle\mathbb{E}_{\pi^{\prime}}\left[r^{\star}_{1}(s_{1},a_{1})+V^{\pi^{\prime}}_{2}(s_{2})\right]-\mathbb{E}_{\pi^{\prime}}\left[V^{\pi}_{1}(s_{1})\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{\pi^{\prime}}\left[V^{\pi^{\prime}}_{2}(s_{2})-(V^{\pi}_{1}(s_{1})-r^{\star}_{1}(s_{1},a_{1}))\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{\pi^{\prime}}\left[V^{\pi^{\prime}}_{2}(s_{2})-V^{\pi}_{2}(s_{2})\right]+\mathbb{E}_{\pi^{\prime}}\left[Q^{\pi}_{1}(s_{1},a_{1})-V^{r,\pi}_{1}(s_{1})\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{\pi^{\prime}}\left[V^{\pi^{\prime}}_{2}(s_{2})-V^{\pi}_{2}(s_{2})\right]+\mathbb{E}_{\pi^{\prime}}\left[\left\langle
Q^{\pi}_{1}(s_{1},\cdot),\pi^{\prime}_{1}(\cdot|s_{1})-\pi_{1}(\cdot|s_{1})\right\rangle\right]$
$\displaystyle=$
$\displaystyle\cdots=\sum_{h=1}^{H}\mathbb{E}_{\pi^{\prime}}\left[\langle
Q^{\pi}_{h}(s_{h},\cdot),\pi^{\prime}_{h}(\cdot|s)-\pi_{h}(\cdot|s)\rangle\right].$

This concludes our proof.