Provable Offline Preference-Based Reinforcement Learning
Authors: Wenhao Zhan
Masatoshi Uehara
Nathan Kallus
Jason D. Lee
Wen Sun
Venue: ICLR 2024 spotlight (2024)
Keywords: reinforcement learning theory
offline reinforcement learning
Primary area: reinforcement learning
TL;DR: PAC offline reinforcement learning from preference feedback over trajectories using general function approximation.

Abstract: In this paper, we investigate the problem of offline Preference-based Reinforcement Learning (PbRL) 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.

Published as a conference paper at ICLR 2024
PROVABLE OFFLINE PREfERENCE-BASED REINFORCE- MENT LEARNING
Wenhao Zhan
Masatoshi Uehara Genentech
Princeton University
wenhao zhan@pri @wt.eprrnintooo.oommm edu
uehara www.masstsss.....m.. @egechhiggeee..c
Nathan Kallus Cornell University
Jason D. Lee
Wen Sun
Princeton University
Cornell University
kallus@cornell.ccu
jusonlee@princetton edu
ws ws455@cornell.c
ABSTRACT
In this paper, we investigate the problem of offline Preference-base Reinforcement Learning (PbRL) with human feedback where feedback 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 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 polynomial number of samples, as long as the target policy covered by the offline data. This guarantee is the first of its kind with general function approximation. To measure the coverage the target policy, we introduce a new single-polic 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-we rewards are directly observed. We further extend and analyze our algorithm when the feedback is given over action pairs.
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. (017). To address this challenge. preference-based RL (PbRL) with human feedback has emerged
promising alternative (Christiano et al., 2017). In PbRL, the agent does not receive 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. PbRL has gained considerable attention across multiple application domains, including games (MacGlashan et al., 2017 Christiano al. 2017 Warnell et al.) 2018). large language models (Ziegler et al.) [2019] Stiennon al.) 22200] Wu et al., [222 I
Nakano ct al. 2022 Ouyang et al.) [0022; Glaese et al. 2022 Bai et al. [022 Ramamurthy et al. 2022
Liu et al.] 2023), and robot learning (Brown et al. 2019 Shin al. (003)).
In this work, we focus on the problem of offline PbRL, 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 PbRL, an offline setting is particularly relevant due 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
"The first two authors contributed equally.
This work done Comell University.

---

Published as a conference paper at ICLR 2024
feasible in practice (Chen and Jiang 2019a), 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. 202 Li et al.
2022a 2022a In the context of PhRI., it is also crucial to develop
Shi et al. 2022; Yin and Wang [ et al. 2021
Uehara and Sun| 2021 Zhan et al.
algorithms that work under the partial coverage condition.
Despite its significance, there are very few algorithms specifically designed for offline PbRL with strong statistical guarantees. In this work, we provide such algorithms and guarantees when prefer- ences 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. (022)) use metrics defined over the entire trajectories. Our main contributions can be summarized as follows:
We propose 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 offiin 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 PbRL. As the concentrability coefficient differs from that in the standard RL setting where state-action- wiise rewards are directly observed, we establish lower bounds that highlight the necessity of our partial coverage condition. To the best of our knowledge, this is the first theoretical separation result between standard offline RL and offline PbRL.
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-wisse 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 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 bound on the advantage function, which can be much smaller than a bound on per-trajectory rewards as shown in Ross et al. (201T): Agarwal et al. (2019).
2 RELATED WORK
Preference-based Reinforcement Learning. The closest work to ours is Zhu et al. (2023), which also studies offline PbRL, 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 recover theirs. So, our guarantees are more general; see Remark 2 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 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 al. (2017) provide survey of PbRL. PbRL has received considerable attention in theoretical RL ( Yue et al.) 20112) 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, /hhu et (2023) 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 unable to learn the optimal policy in such scenarios (Rashidinejad et al.) (0216). To tackle this problem. numerous algorithms
have been proposed with theoretical guarantees (Liu et al. 2020 Kumar al. 2020 Jin al. 2021
2

---

Published as a conference paper at ICLR 2024
Rashidinejad et al., 2021b Uehara and Sun 202 Li et al. 2022b Shi et al. 2022: Jin al. 2020
Xie et al. 2021 Zhan et al.
2022a). J The most relevant work is Uchara and Sun (021). D. which focuses on offline model-based RL with general function approximation. However, their methods cannot be directly applied to PbRI. since per-step rewards are not observable in our setting. Furthermone, even in the standard RL setring, the construction of confidence intervals differs between our approach and theirs. Another related paper is Cheng et al. (2022), which considers the general offline pessimistic RL framework in the standard setting and also subtracts a reference term in their algorithm, similar to ours. However, our motivations for such reference terms are quite different from theirs. Additional detailed comparisons are given in Section 4.1 and Remark 3
PRELIMINARIES
We first introduce our offline PbRL setting with general function approximation.
Markov decision processes. We consider an episodic inmmmmnoooeeessus Markov Decision Process (MDP) denoted by M,, which consists of a state space S, action space A. an initial state distribution P E As. and a horizon H E N+ At each step h E [ - I]. we use P% : S A + As to denote the ground truth transitions. The ground truth reward function for the entire trajectory is denoted by r* : T [0, /. where T = (S x AA) represents the set of all possible trajectories. Note that r" is trajectory- -wise reward, which is more general than Sate-action-we wise rewards commonly considered
in standard RL, which is the special case where for some (== we have r (T) =Ei r7, (sh, oh) for a trajectory T ($1, 01, 8H: A.)).
policy x == { characterized by Th (S x AAA-1 x S AA. specifying the probability of selecting actions for the agent at each step h E [H] based on the entire history. We denote the set of all such history-dependent policies as This Given policy n, we define its expected reward with respect to a general reward function r and initial and transition distributions P = [P as J(T; P) == By PP) (r].). Here, (a, P) represents the expectation over the trajectory distribution when executing the policy ι under the transition P starting from Po- We use E,<xl:] [.] or |-] to denote the special case when
the ground truth distribution P = (Pr H h==
The optimal policy, denoted TT, is the policy that maximizes the expected reward with respect to the true reward r* and system dynamics Pt, ie.,, x P',....
:= arg max J(T;; r", P*). As the true reward function r² is dependent on the entire trajectory, the optimal policy x² is generally history-dependent. Thus, designing offline PbRL algorithms that can learn history-dependent policies is crucial.
For any policy n, we can define its state-action visitation measure as follows: 8, On a). Yh [H), where IPt.P' (.) denotes the distribution of the trajectory when executing policy π in P* We will also use (T) to denote pa.P' (r) for the whole trajectory т.
di, (s, a) PT (sh
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 (T((s = Ex IEt rf [s, = s/,vh vh E [H] (s, = E, En r? (52, (s) = 8, ag = a). vh E [H] It is well-known that when the reward is state-action-wise, the optimal policy n is both Markovian and deterministic (Bertsekas 2017). Furthermore, we have Vi"" (s) sup, V7((s) and QT, (s,a) = sup, QT, (s, a) for all h [ For brevity, we will use V* and Q* to represent the optimal state-value function and Q function, respectively. The advantage function of the optimal policy, denoted by A", is defined to be A (s, a) Q7, (s, a) V (s) for all h E [H]. s E S, E A.
Offline Preference- based Reinforcement Learning. We focus on the problem of offline PbRL in this work. Specifically, in the trajectory-based pairwise comparison setting, we are provided with an offline dataset D = (7 y..1, o00) _'' 1 where n.0 {s),00 0 n..0 Th=1 and nr1 = {s) a% 1 # are i.i.d. sampled from the distributions μo and μr, respectively. and Td E {0,, 1) indicates preference for n.l over n.2 We assume satisfies the following preference model:
/==1
Assumption 1 (Preference-bee based model). Given a pair of trajectories (r", o 10 satisfies
P(o = T), P(T is preferred over To To, To, (() (To))
where T IR + [0, 1] is monotonically increasing link function.
3

---

Published as a conference paper at ICLR 2024
A commonly used link function is the sigmoid function (xx) 1/(1 xx) leading to the Pradley-Terry-Lueee (BTL) model (Christiano et al. (017).
The objective of offline PbRL is learn high-quality policy म E Hhis f.e., with ( r* PP)) J( PP) S E where Ttar is a target policy we want to compete with (potentially π )T).
General function approximation. In paper, estimate the reward r* with general function approximation. We introduce a function class Gr, such as linear functions or neural networks, to approximate the true reward. For each G, and trajectory pair (79, , denote the induced preference model with respect to r as P =²), defined as
7 (r((T))-(((
(1)
We use bracketing numbers to measure the complexity of (Pp Gr}.
Definition 1 (c-bracketing number of preferences). We say (g) ,g¹) where g¹ g² TXTTTTT R and trajectory-pair (T +1), The e-bracketing number of Gv, denoted by Ng. (E), is the minimal number 2.
an c-bracket if g 70,
,0,-") S s²d)) 1 -0,=")
- 1 (r,7)) e all
of e-brackets (g n. g" n= needed so that for any r E 9, there is a bracket E [N] containing it,
meaning of (1700 0...0 T P-(--7 (-(1) (- (1) for all trajectory-paiis (7 7T
The e-bracket number is widely used in statisties (van de Geer 2000) to study MLE and related M-estimates. Particularly, our setting the bracket number of reward classes will be of the same order as the covering number, another common complexity measure in statistics (Wainwright 2019). for P, (-(-7",, r') has only two dimensions. One example for which we can bound the e-bracket number is linear rewards under the BTL model (Pacchiano et al., 2021: Zhu et al. 2023).
11012 S B} for some featurization Φ :T:TT + R² and > O, and the link function is ( = o-). Then for any e S 1, Nog,N, (t) S Od BR
Proposition 1. Suppose |)(())l22 < R VT T, Gr S (T (o(T), 0)
The proof is deferred to Appendix A To handle unknown transitions, we similarly use function classes {Gp, W approximate the transition probabilities {P% (P)) Similarly, we use Nor, (e)
to denote the c-bracket number of Gr,, The formal definition is deferred to Appendix E
TRAJECTORY-BASED PAIRWISE-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 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 |
consists of the following two steps.
Confidence set construction via MLE (Lines 3). We construct confidence set for the ground truth reward from the implicit preference feedback. We achieve this by selecting reward models that nearly maximize the log- ligllikli of observed data up slackness parameter Ç. We will show that the result, R(D), approximates the following confidence set:
RD(D) = {r G, B .1 me [I((T)) r r(7))) - ( -r
for certain ç. Here the distance between and r* is measured using the total variation distance (i.e., l norm) of r(m) - r(ro) and (T) - (To) over the offline data.
Distributionally robust policy optimization (Line After constructing the confidence set, we search for the policy that maximizes the policy value under the least favorable reward model, the R(D) minimizing the policy value J [IT; r, P*) minus Er~nnet [r]]], where pree is an arbitrary known reference trajectory distribution. It is generally recommended to set Pref to Ml. as we will explain later, possibly sample-average approximation thereof based on {T!.) ..... NN.). By selecting the least favorable reward model instead of the MLE solution f. we penalize policies that are well-covered by the offline data. The need for reference policy arises because the approximated
4

---

Published as a conference paper at ICLR 2024
Algorithm 1 FREEHAND: oFfline ReinforcemEnnt lEarning with HumAN feeDback
1: Input: offline datset D. slackness parameter Ç, reference distribution pref, true transition P
2: MLE: compute F argmaa En=1 log (o 0" |,,11 ,,.0)
3: Confidence set construction: construct
R(D) - (r E G. E log (o = o" 1 ; xnit) En log P=(o= -,:1,
4: Distributionally robust planning: return
म
argmax miD (J(TiT,P*) (((r))(((((T))
confidence set measures the uncertainty for reward difference between two trajectories (r(1))-((()) but it cannot measure the uncertainty of the reward of a single trajectory.
In the following, we compare our algorithm to existing works. Zhu et al. (2023) consider a pessimistic offline RL algorithm for PbRL specialized to the linear reward class setting, while our FREEHAND can handle general function approximation. Specifically, they construct the confidence set using the Ceattue--oovariance--ooo
b--ball around the MLE 8, where f(r) (Ø(T), 0).. In contrast. confidence set is obtained directly from the log-likelihood objective and is generic. [ehaaa and Sun (202T) proposes model-based pessimistic offline RI algorithm when 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 reference policy. This similarity is superficial, however, as the motivations are different. We subtract the value because we can only measure the difference between rewards of any two trajectories, while their motivation is to obtain certain robustness result (their proposition 3).
Remark (Computational Efficiency). Line 4 in FREEHAND is computationally hard in general. Nevertheless, by leveraging Lagrangian formulation, we can use Lagrangian multiplier to convert the constraint r E (D) into a regularization term of the objective function and have a feasible version of our algorithm in praclice. See more details in Appendix B
4.2 ANALYSIS
To analyze the sample complexity of FREEHAND, we first quantify the discrepancy between the offline data 'D and the distribution induced by the target policy Tear-
Definition (concentrability coefficient for preference- feedback). The concentrability coeffi-
cient w.r.f. reward class Gr. larget policy Ttar, and a reference policy pret is defined
E T Prrt [r' (77) - r (T -(7)) + +
(r, Tears Mrot) = max 0, sup
rEgr / EEoompot (1*) - (7') - r(7)) +r(+")
Note, when we choose Mrer = u1, by Jensen's 's inequality, the value of C, (Gr, Tears /1) ) can always be upper bounded by the per-trajectory concentration coefficient: C,,,, taar #h S VCr for any Gr. where Ctr == max,eT (o(F))
(r) Moreover, while (r,, Ttars P1) becomes VCr in the worst case (e.g., when G. is the set of all functions mapping from T to R), it can generally be much smaller. For example, when using linear models, is a relative condition number, as explained in Appendix [D.T] Finally, when Peef aae, our coefficient becomes 0. This implics that C, Ttar, 11) could be small when tear and Hyet are close. While the concept of concentrability coefficient has been used in offline RL with explicit reward feedback (Chen and Jiang 2019b] Song al. 2022). this property is unique when the feedback is in the form of preferences.
In our following PAC analysis, we further assume the reward class G, is realizable and bounded. Assumption (Realizability). We have r* G,. Assumption 3 (Boundedness). We have 0 S r(r) S Tmax for all r Gr and E T. Theorem For any 8 E 10, ( = CML.F. (o (1/N)/8) where CMLR.. > universal constant, then under Assumption 72 and 3 with probability 1 - 6, we have
cC?(Or, Tears Mrat ) (Ng,))1
J(Tar: r", P²) J ".t""",')) <
(2)
N
5

---

Published as a conference paper at ICLR 2024
where O is universal constant and (infxe( Piaas,,maa ('xx))
Theorem indicates that FREEHAND can learn an e-optimal policy compared to Ttar with a sample complexity of
= Ci(9ns ( Ttar; Pref )R (1/N)/8)
Next we provide a detailed explanation of this sample complexity. Firstly, C,(9r, Ttars Pref) rep- resents the extent to which the dataset 'D covers the target policy Tur- In our theorem, to obtain a non-vacuous PAC guarantee, we only require the dataset 'D to cover the target policy Ttar (i.e., (Gr, Ttar, Mref) 00). The distributionally robust optimization step plays crucial role in obtain- ing this guarantee under partial coverage. In particular, invoking the abovementioned third property of (9r, Ttars (rrf)), when setting Ttar Pref- (2) is reduced to
[[ret P') S
(():r",P")
(3)
This encourages us to choose prer Pui (or (P)) as it will allow us to ensure our performance is at least larger than the performance associated with the offline data.
Secondly, log (1/N)) measures the complexity of the function class G,.. For example, when using linear models, it takes (dd) We refer the reader to van de Geer (2000) for bracketing number computations for more general classes. Thirdly, & represents the non- non-linearity of the link function 4, which determines the difficulty of estimating the reward from human preferences. This dependence on k is present in the existing literature of PbRL, both in online settings (Pacchiano et al. 2021 Chen
al. 2022) and offline settings (Zhu et al.
2023).
Remark 2 (Comparison to Zhu et al. (2023)). By specializing our result to the linear model,
we recover the result in Zhu et al. (2023). Specifically, the bracketing number is calculated in
Proposition 7 and (r, Ttar; Pref) is reduced to relative condition number. The details are
deferred Appendix D.I
4.3 DISCUSSION OF THE CONCENTRABILITY COFFFICIENT
In the worst-case scenario (i.e., Gr is the set of all functions mapping from T to IR, the value of Cr,, Tiar; (1) is reduced to to the per-trajectory concentrability coefficient Ctr. The per- trajectory concentrability coefficient is generally larger than the per-step concentrability coefficient
Ca commonly used in the general offline RL literature (Xie et al. 2021 Uchara and Sun 2021 Zhan
ct al. 2022a). Specifically, Cst is defined
Cat max th (s,a)/ s,a,h
where (s, a) represents the marginal distribution at step h. In this section, we show the depen- dence on the per-trajectory concentrability coefficient is necessary for our offline PbRL context. This intuitively because PbRL setting involves reward functions defined over trajectories, reflecting the fact that human feedback also trajectory- based.
In the next proposition, first show that the per-trajectory concentrability coefficient Cer can be exponentially larger than the per-step concentrability coefficient Cst-
Proposition 2. For any S 1, > 2, H > C 2 there exists an MDP M with horizon H, policy Taar and a data distribution μo such that |S] = S, |A| A and Cat = while Cur =H Proposition
2 indicates that Cu can be significantly larger than Cst. natural question arises to whether we can obtain suboptimality guarantees using C.t- Unfortunately, the following lower bounds reveal that per-step concentrability not sufficient to guarantee efficient learning in trajectory- based PbRL setting, even when the reward function is defined over state action pairs:
Theorem 2. Set Trar = x² Then, for any C and H 2 2, there exists dataset distribution μn such that we have
ED[J(TTrr" P*) - PP) R min {c ( 1.-1.13.
inf *
sup (C.
where रे is any mesurable function of the data D (and knows the information of p1). (a(CC) is the set of all MDPs with per-step reward, offfine distribution (M, Po) such that Cat S C. Note Ep is taken with respect the randomness in

---

Published as a conference paper at ICLR 2024
Algorithm 2 FREEHAND
Input: offline dataset D, slackness parameter ç, Sp. reference distribution Pref
MLE for reward: compute f = argmax Σ log (0 d" T -n.0)
MLE for transition: compute P/. = argmax Pr, Σn=1 Σi= log (1 n-4
n.d
n.d)
Sh
Confidence set construction: for 0 - h - H - 1, construct
1000 ,m.1) 2 En= log Pr(o n,0 "1,1) - =c. R(D)= = r Er En log (o ,
N
log Pn (s (5h+115h aa anitt SPn }
(D) Ph E gp.
ΣΣ
n.d 4111 ax log
n=1 ==0
n=1 x=0
Distributionally robust planning: return
ā argmax min.eR(() J (: (TV (P. E Er ir(r)).
Theorem indicates that learning in our setting intrinsically hard due to trajectory-based feedback, even if we restrict the reward function class. In addition, we can show that scaling with Cr is necessary in our setting:
Theorem 3. Set Tear =", Then for any C > 1 and H 2 1, there exists dataset distribution μai
such that we have
C (C-1./ N
inf # (M..))
sup
Ea[J(n':'", PT) J(a;"* pP)) 2 min
where fे is any mesurable function of the data DD (and knows the information of p1). Oir is the set of all MDP, offtine distribution (M, pu) such that C₁ S C. Note Ep is taken with respect to the randomness in D.
Note that when μi is known, we can set jhoef μn in Algorithm Dand then (g,, Ttars P1) S V which implies the sample complexity in Theorem [ [indeed nearly matches this lower bound with respect to Ctr and N when N is sufficiently large.
In summary, Theorem and Theorem imply that the scaling with the per-trajectory concentrability sairwise-compriisn setting, and it cannot be relaxed to
coefficient is essential in the crajectory-based the per-step concentrability without additional assumptions, such the reward structure. To the best of our knowledge, this is the first theoretical result indicating that trajectory-wiss feedback is intrinsically harder learn than step-wise feedback offline PbRL.
PRAJECTORY--ASER COMPARISON WITH UNKNOWN TRANSITION
We extend the setting presented in Section 4 to the scenario where the transition function p* is unknown. The algorithm is described in Algorithm Compared to Algorithm I we simply added
similar step handle unknown transitions. Hereafter, we use the convention Po (- s, a) Po(.).
Our sample complexity will depend on the following additional concentration coefficient:
Definition 3 (Concentrability coefficient for the transition). The concentrability coefficient w.n.t transition classes (Gp,) } and a target policy Ttar is defined as
B(s.a)ad P1 (: s, - P. (s
Cp(19p,), Ttar) == max sup ho Pi, / /ELs.)) (P s. P a)
Note this is always upper-bounded by the Density-ratio-ben concentrability coefficient, Cr((Er,) ), Tear) S sup(s.a.)ESSxxx HI) 1o.
dtear (e.a)
We also assume the transition classes (Gp, Jizo are realizable: Assumption (Realizability). Suppose that we have Př E C9,, for all h where 0 S < H In addition, any choice Pt. E GP, ( < H are valid transition distributions.
Then with the above assumptions, we have the following theorem to characterize the sample com- plexity when the transition is unknown:
7

---

Published as a conference paper at ICLR 2024
Algorithm 3 FREEHAND-action
1: Input: offline datset D.
n.0 sh. an ,a aahi)) vh [H] 2: MLE: compute A. argmaX,,E9A, Ex=1 log PAa (o 0j
3: Greedy policy: return Fn (5) argmax as
Theorem 4. For any ō E (0, 1], let Ç CMLE log(NG, (L/ = cp log HN (1/N)/6) where CMLE, cp > O are universal constants, then under Assumption and we have
[ ;r' P*) J( PT)
cC (Gr, Tears Mrof RR² log( (1,N)/11)/ + Hr max
cppl19p, Tear log (og
N
N
where and the same as Theorem 7 and Np maxognsH-1
Compared Theorem I 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 per- formance comparable any target policy Ttar covered by the offline data, i.e., C, Tears Hsett) <
0o, Cp(19r, I Ttar)) < <c.
Remark (Comparison to Uehara and Sun (021) ). Like us. Uehara and Sun 2021| proposed a model-based RL algorithm that works under partial coverage, but in the standard RL setring and with known state-action-wise reward function, See the detailed comparison in Appendix D.3
6 ACTION-BASEE 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" is state-action- - H
(T) > k= (s an) for (81, " ,H an). And, consider preference model based on Q"
Setting. We have datasets D = HD with Dj, = ((sh) 2,0 n.1
a :0h .oh)]== for each h E [H]. where each sample is drawn i..dd from the distribution 8y ~ phi dh
n.U ~pona(- (- (8)) n.1 #1,((-)
*)) and of f0, 1} indicates preference for a,'" over dn in the state sh. We assume it satisfies the following preference model:
Assumption 5 (Action-based comparison model). Given a pair of actions ah ah and state sn. E 1) satisfies
1 P(on = 1 sh, ah. a = (QT a (T(,,,))))
Here, the aforementioned distribution can be equivalently expressed as P( = s a% a. n. (AA, (s% ") - (s a.."))). where A denotes the optimal advantage function. Consequently, we introduce general function classes GA,, estimate the optimal advantage function Aj. In addition, for each A, E 9A and (s, , a²) E S x A x A, we use PA, (. 8, a², aat) to represent the human preference model with respect to Ar. defined PAR (o
s, a at) = (AA - d")).
We again use the e-bracket number of such advantage fuuccion classes to quantify their complexity, denoted as NGA. The full formal definition is provided in Appendix E
Algorithm. Our algorithm comprises two steps. In the first step (Line the optimal advantage function using MLE In the second step (Linne 3). we determine the policy by selecting the action with the highest advantage value based on the learned advantage function.
objective is to estimate
Analysis. Now we show that FREEHAND-act on can learn a opar-optimal policy as long as offline data covers the optimal policy. Our analysis depends on the assumption on the margin of Q*:
Assumption 6 (Soft margin). There exists ag R+, 3 E (0, oo] such that for all a E A, E
[M]. > O, we have pa _P' (0- < |Q] (Sh, T" (sn)) - (s,, a)) < a) S (
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
8

---

Published as a conference paper at ICLR 2024
2022; Uehara et al. 2023).
Note, when the optimal Q function satisfies gap (as in Simchowitz and Wu et al. 2022). the soft margin assumption holds with co.
Jamieson 2019
Next, we introduce the concentrability coefficient for the action-based comparison setting, which is defined as follows.
Definition 4 (concentrability coefficient for action-based comparison).
E Fea,a" -'--Uuii(())))) 11 a!)]
Cact ==
sup
AE EGA, E www..aaawaaaalil...aamm..a...
where 1(A 8, a", ,,,)) = |A (s, dd) - Ax, An a²) + (, a and Unif(: 8) is the
uniform policy over A.
We observe that
d% (x)
sup (a 1
(A
sup he ne(M,, EA (1 Based on this bound, we can consider simple sufficient conditions for Cact to be finite. Firstly, regarding the first term, it is sufficient for the dataset distribution μn cover the states visited by the optimal policy x², denoted as d% Regarding the second term, we require Mo,s to cover Th Additionally, the third term can be upper bounded when P1.1 can cover the whole action space. This is mild because Vs S: (s) 0 is not controllable to the learner, but V(s,a) S x M1,t is controllable to the learner in the data-collectton process. To summarize, Cart < oo primarily requires partial coverage over the state space with respect to the optimal policy, which is preferable in practical applications where S can be very large.
Cact sup
NE(M)) MAn
he (E( EA (a.
Additionally, introduce several assumptions the function classes similar to those in Section Assumption 7. For all h E [H) we have A₁, E 9AA-
Assumption 8. For all h E [H] and A₁ E GAn we have (A, s Umax for all (s, a) ES A.
With the aforementioned assumptions, we can establish the sample complexity.
Theorem 5. Under Assumplion 567 and g
huve with probubility at least 1 - 8 that
DFF
20
Cnee log( HNG (1/N)/1)))))))))) zीz
J(m";r" pP) - -J P') cH
N
where Ng. ma NGA,, and KA
inf Pmans Amanz) (T)))
Theorem suggests that FREEHAND act ion can learn a near-optimal policy as long as Caet takes finite value under soft margin. Specifically, when hard margin is imposed (i.e., B oo), FREEHAND-action
learn c-optimal policy with sample complexity of N (1/c). which faster than typical rate ( As mentioned earlier, the quantity Caet 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 designed to overcome the limitations of existing approaches. In Theorem [] our upper- bound is influenced by the parameter When using common sigmoid link function, this parameter scales with ((exp(r (mxx))) As result, in dense reward settings where Tmax scales with 17, this scaling factor may lead observations have been made in previous works (Zhu et al., [203)] Pacchiano et al. 2021] Chen et al.
explicit dependence of (expp( ( H)). Similar
2022). However, even if Tmax scales with H, it is known that the -nom of the advantage function. denoted as bmax. can take much smaller values (Ross et al. 2011 Agarwal et al. 2019) Hence, we can avoid the explicit dependence on (cexp(H)).
-norm
7 CONCLUSIONS
We propose the first algorithm for trajectory-wise PbRL with general function approximation and under partial coverage. We establish lower bounds that explain the differences between our PbRL model and standard RL with direct reward feedback. Moreover, extend algorithm to unknown transitions and to preference feedback over actions, all while maintaining strong guarantees under partial coverage.

---

Published as a conference paper at ICLR 2024
REFERENCES
Abdelkareem, Y., Shehata, S., and Karray, F. (2022). Advances in preference-basee reinforcement learning: review. 2022 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pages 2527-2532. IEEE.
Agarwal, A., Jiang, N., Kakade, S. M., and Sun, W. (2019). Reinforcement learning: Theory and algorithms. Technical report.
Audibert, J.-Y. and Tsybakov, A. B. (2007). Fast learning rates for plug-in classifiers. The Annals of statistics, 35(2):008-633.
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.00 058622.
Bertsekas, D. (2017). Dynamic programming and optimal control (4th edition). Athena Scientific.
Brown, D., Goo, W., Nagarajan, P., and Niekum, S. (2019). Extrapolating beyond suboptimal demonstrations via inverse reinforcement learning from observations. In International conference machine learning, pages 783-792. PMLR.
Chen, and Jiang, N. (2019a). Information-thheretii considerations batch reinforcement learning. In International Conference on Machine Learning, pages 1042-1051. PMLR.
Chen, and Jiang, N. (2019b). ceemmation-thooretit considerations in batch reinforcement learning. In Proceedings of the 36th International Conference on Machine Learning, volume 97, pages 1042-1051.
Chen, X., Zhong, H., Yang, Z.., Wang, Z., and Wang. L. (2022). Human-in-the-llop. Provably efficient preference-basee reinforcement learning with general function approximation. In International Conference on Machine Learning, pages 3773-3793, PMLR.
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, P. F., Leike, J., Brown, T., Martic, M., Legg, S., and Amodei, D. (2017). Deep rein- forcement learning from human preferences. Advances in neural information processing systems, 30.
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 dialogue agents via targeted human judgements. arXiv preprint 2rXiv:2209.1433
Hu, Y., Kallus, N., and Mao, X. (2022). Fast rates for contextual linear optimization. Management Science, 68(6):4236-422
Hu, Y., Kallus, N., and Uehara, M. (2021). Fast rates for the regret of offline reinforcement learning. In Conference Learning Theory. PMLR.
Jin, Y.. Yang, Z., and Wang. Z. (2020). Is pessimism provably efficient for offline rI? arXiv preprint arXiv:2012. 1508.
Jin, Y., Yang. Z., and Wang, Z. (2021). pessimism provably efficient for offline rI? International Conference on Machine Learning, pages 5084-5096. PMLR.
Kidambi, R., Rajeswaran, A., Netrapalli, P., and Joachims, T. (2020). Morel: Model-based offline reinforcement learning. In Advances in Newral Information Processing Systems, volume 33, pages 21810-21823. Curran Associates, Inc.
Kumar, A., Zhou, A., Tucker, G., and Levine, S. (2020). Conservative q-learning for offline reinforcement learning. In Conference Neural Information Processing Systems (NeurIPS).
10

---

Published as a conference paper at ICLR 2024
Li, G., Ma, C., and Srebro, N. (2022a). Pessimism for offline linear contextual bandits using Ip confidence sets. arXiv preprint arXiv:2205.10671.
Li, G., Shi, L., Chen, Y., Chi, Y., and Wei, Y. (2022b). Seuling the sample complexity of model-based offline reinforcement learning. arXiv preprint arXiv:2204.05777
Liu, H., Sterrazza, C., and Abbeel, P. (2023). Languages are rewards: Hindsight finetuning using human feedback. arXiv preprint arXiv:2302.0267.
Liu, Q. Chung, A., Szepesvári, C., and Jin, C. (2022). When is partially observable reinforcement learning not scary? arXiv preprint vrXiv:2204008967,
Liu, Y., Swaminathan, A., Agarwal, A., and Brunskill, E. (2020). Provably good batch reinforcement learning without great exploration. arXiv preprint arXiv:2007.08202.
Luedtke, A. and Chambaz, A. (2020). Performance guarantees for policy learning. Annales de l'IHP Probabilites statistiques, volume 56, page 2162. NIH Public Access.
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-dependel human feedback. In International Conference on Machine Learning, pages 2285 2294. PMLR.
Nakano, R., Hilton, J., Balaji, S., Wu, J.. Ouyang, L., Kim, C., Hesse, C., Jain, S., Kosaraju, V., Saunders. W., al. (2021). Webgpt: Browser-assisted question-answering with human feedback. arXiv preprint arXiv:2112.0933:
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, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., al. (2022). Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35:27730-27744,
Pacchiano, A., Saha, A., and Lee, J. (2021). Dueling rl: reinforcement learning with trajectory preferences. arXiv preprint arXiv:2111.04850.
Perchet, V. and Rigollet, P. (2013). The multi-armed bandit problem with covariates. The Annals of Statistics, (122)693--721
Ramachandran, D. and Amir, E. (2007). Bayesian inverse reinforcement learning. Urbana, 51:61801.
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?: Bench- marks, baselines, and building blocks for natural language policy optimization. arXiv preprint arXiv:2210.01241.
Rashidinejad, P., Zhu, B., Ma, C., Jiao, J., and Russell, S. (2021a). Bridging offline reinforcement learning and imitation learning: tale of pessimism. arXiv preprint 2rXiv:2103.1202.
Rashidinejad, P., Zhu, B., Ma, C., Jiao, J., and Russell, S. (2021b). Bridging offline reinforcement learning and imitation learning: A tale of pessimism. Advances Neural Information Processing Systems, 34:11702-11716
Rigter, M., Lacerda, B., and Hawes, N. (2022). Rambo-rl: Robust adversarial model-based offline reinforcement learning. arXiv preprint arXiv:2204. 1258/.
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, 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.
11

---

Published as a conference paper at ICLR 2024
Shin, D., Dragan, A. D., and Brown, D. S. (2023). Benchmarks and algorithms for offline preference- based reward learning. arXiv preprint arX1v:2301.01392.
Simchowitz, M. and Jamieson, K. G. (2019). Non-asymptotic gap-dependent regret bounds for tabular mdps. Advances in Neural Information Processing Systems, 32.
Song. Y., Zhou, Y., Sekhari, A., Bagnell, A., Krishnamurthy, A., and Sun, W. (2022). Hybrid rl: Using both offline and online data can make rl efficient. arXiv preprini arXiv:2210.0067/8
Stiennon, N., Ouyang, I.., 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.
Uehara, M. Kallus, N., Lee, J. D., and Sun, W. (2023). Refined value-based offline rl under realizability and partial coverage. arXiv preprint arXiv2302..2339.
Uehara, M. and Sun, W. (2021). Pessimistic model-based offline rl: Pac bounds and posterior sampling under partial coverage. In arXiv preprint 1rX:v:2107.06226.
van de Geer, S. (2000). Empirical Processes in M-estimation, volume 6. Cambridge university press.
Wainwright, M. (2019). Hligh-Dimensional Statistics: Non-Asymptotic Viewpoint, volume 48 of Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press.
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, C., Akrour, R., Neumann, G., Fürnkranz,
al. (2017). A survey of preference-based reinforcement learning methods. Journal of Machine Learning Research, 18(13)):
Wu, J., Braverman, V., and Yang, L. (2022). Gap-dependent unsupervised exploration for rein- forcement learning. In International Conference on Artificial Intelligence and Statistics, pages 4131- PMLR.
Wu, J., Ouyang, L., Ziegler, D. M., Stiemnon, N., Lowe, R., Leike, J., and Christiano, P. (2021). Recursively summarizing books with human feedback. arXiv preprint arXiv:2109.10862
Xie, T., Cheng, C.-A., Jiang, N., Mineiro, P., and Agarwal, A. (2021). Bellman-consistent pessimism for offline reinforcement learning. arXiv preprint arXiv:21066 06926.
Xu, Y., Wang, R., Yang, L., Singh, A., and Dubrawski, A. (2020). Preference-based reinforce- ment learning with finite-time guarantees. Advances in Neural Information Processing Systems, 33:18784-1878
Yin, M. and Wang. Y.-.. (2021). Towards instance-optimal offline reinforcement learning with pessimism. Advances in neural information processing systems, 34:4065-4078.
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, Y., Broder, J., Kleinberg, R., and Joachims, T. (2012). The k-armed dueling bandits problem. Journal of Computer and System Sciences, 1835):153
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.
Zhan, W., Uehara, M., Sun, W., and Lee, J. D. (2022b). Pac reinforcement learning for predictive state representations. arXiv preprint arXiv:2207.05738.
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.11220.
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: /00.:/99990899
12

---

Published as a conference paper at ICLR 2024
A PROOF OF PROPOSITION 1
Let F denote the function class {fr : fr((T), ) = = E g Let Iz(c) denote the e-bracket number with respect -norm, i.e., the minimum integer M such that there exist M functions } such that for each fr E F, we have sup,",r" (f-((T) f"(""" s e for some E [M]. Then we know there exists of function F with FF (c/4/4) such that for each
fr F, there exists J E F satisfying
sup -
Now we construct bracket (07. 0 defined as follows:
of(o= = + 07 =1
xt) -e/4,
0f 1|7 -1) -(7] +1) - -1)--1
=1 -(7 -()),/)) + c/4.
Then clearly we have (2((17), ,-) I ,.
(F(117",*) and (10((17",
Chat.Ng (((-1",7>)1] S e. This implies that (g. (e) s I=(e/4).
Now we only need to bound (c/44)). Consider and A' with 100 81122 S c and let (r)) denote the reward (Ø, 0) (0,0")) 8')) Then we know for all T,
((()) - r'()) Rej.
Fix the trajectory pair (7,,72) 7²). Without loss of generality, we assume exp(r(>")) + exp(r(r*)) s exp(r'(7") + exp(r'(r)) Then we have
exp(r(7")) + exp(((r")) S exp(r'(7") + exx((r exp(Ree) exp((((")) (epp(())(ee(((t))++cc+)
On the other hand, we have
[ fr((7, -') exp(r(+-)) exp((' +xp((r(+))) exp((r((-)) (exp(r(>")) + exp(r(r))))
- (xxp("(="))=xpp(r(("" (xp((((7))
(x((((( exp(((())))
Therefore, if ((ex((r((>))
>
then we have
(exp((()))) exp(('(())) (xx(r(t"))(ep((((()))
- - exp(r' exp((r(7)) + exp(r(>))))
Sexp(R(r (xp(((()))((((())) (xxp(((7)) +xp((((r))) - exp(- RG) exp(r(7))) exp(r(70)) exp(r(7!)))
=(exp(Re:) -xppl)))-xpppppp ( exp()(())) exp(r(7")) (ex((()))(((((""))=>+))))))) exx((((")))
exp(-Rei))
Otherwise, we have
(exp(r(=))) (exp(r((x)) + exp(r'(+t)) - exp()'(>))) exp(((+7)) + exp(r(r+))) S Eex((Re) (xm())xxppr))) (exp(r(>))) + exp(r(+*))) -xxp(((r))))(( exp(r(>")) + exp(r(r')))
(eep((Re) exp(r(r))) exp(r(7")) + exp(r(+))))
Therefore we have
((((7,77)) (+((79,7))
13

---

Published as a conference paper at ICLR 2024
exp(((+*)) (exp(Rei) exxp(-Re)) exp(r(>')) exp((=))))exp((((7)) (exp(((7))((xp(((=)))) ((a(((")))+<xp(((() +exp(((7))) exp(2R()) -
exp(r'(79)) exp(r"(71)) exp(r(79) +exp(r(7)))
This implies that for any S 1,
21n d BR B²))
log Iy (c/4) log L
c)
0
R
where (-) (-) the covering number of d-dimensional ball centered at the origin with radius B with respect to 82-norm and the last step is from Wainwright (201)). This concludes our proof.
B FEASIBLE IMPLEMENTATION OF FREEHAND
In this section we show how to implement the robust optimization step (Line 4) of FREEHAND in practice. Our idea is inspired by standard offline RI. (Rigter et al., 2022) where the authors rely on Lagrangian formulation to make the theoretical algorithm CPPO (Uehara and Sun, (021) practical enough to achieve good performance on the D4RL datasets. We believe the empirical insights provided in (Rigter et al. 2022) can be applied here as well.
First for Lagrangian relaxation, original inner minimization problem Line 4 of FREEHAND is
min J(m;r, P*) -Erpper rE)(D)
Note that the only constraint is E R(D). Then by introducing a Lagrangian multiplier 3, we convert such constrained minimization problem into unconstrained regularized minimization problem:
min (T; P*) - Er-yea [r(T]]
Σ
log (o = ,"1
7um
Consequently, Line 4 in FREEHAND can be converted the following unconstrained regularized max-min problem:
N max min [(T,T) (TT,,, Er [r(r)] - log P. o'1 nn.l).
n=1
Since now we are facing an unregularized problem, the most common way to solve L(TT, r) in practice gradient ascent-descent. Suppose and are parametrized by 0 and À (usaully neural networks). Then gradient ascent-descent requires us to compute an unbiased stochastic gradient with respect to 0 and respectively. Fortunately, this can be easy to achieve in practice. On the one hand, for the gradient of 0, we only need to compute (T r, P*) ). This task has been thoroughly discussed in the literature of policy gradient and one example REINFORCE, which samples a trajectory by executing Ty in p" and then the estimated graidient can be expressed as
H
V (onlsn))
A=1
where (sh, 0%) is the h-step of T.
On the other hand, for the gradient of X, we only need to sample independent trajecotories 7' by executing in pa and 7 from phef and an index i [N]. Then the unbiased estimated gradient can be directly written as
Vx Vxrx(7") vV, log (r o'17th0,7f111
Therefore, with the above estimated gradients, we can then run graident ascent-desee descent happily to solve max min, L( r) in practice.
14

---

Published as a conference paper at ICLR 2024
Furthermore, to compute Erw [r]]] in Line in practice, sample No trajectories {r');- )==1 from Pref and then use No r(r') as surrogate of Exreueer [r(r). From Azuma-Hoeffding inequality, this will only incur error scaling with N. Therefore long as we choose No ÓLLe²), this error can be neglected while line 4 becomes more computationally efficient.
C PROOF OF THEOREM
The proof of Theorem T consists of two steps, deriving the guarantee of MLE and analyzing the performance of pessimistic offline RL.
Step 1: MLE guarantee. We first need show that the confidence set R(D) contains the true reward r* with high probability. This can be proved via the following lemma which characterizes the guarantee of MLE:
Lemma (Performance of MLE). Fix any 5 E (0, 1]. Then with probability at least 1 - 8/2 we have that for all reward function Gr.
Pr(o"Iomio ,nill) Pr. (0 (7a,0 pm
log
I CMLLE (og.)
where OMLE > 0 is universal constant.
We defer the proof to Appendix C.I 1 8/2. Under the event E,, we have
Denote the event in Lemma 1by & then we know P(E1) 2
N
Σ
log P.- (00 m.)) 2 n=1
Σ
log (7 (10,1,",,,,,1)))) (m,1) - CMI. - log, (1/N)/0)),
which implies that r* E R(D) since we know Gr from Assumption
Nevertheless, the confidence set R(D) is constructed via loglikelihood and we indeed prefer a bound on the total variation (TV) distance between P, and P,, where r E RRD)) facilitate our subsequent analysis. We can obtain such a bound shown in the following lemma from the literature (Liu et al. (ropposioo 14] 14an et al. [0226) 9]):
Lemma 2, With probability at least 5/2, we have for all reward function r E G, that
||
+|)
<
CTV N
Σ
N
log
Pr (o- ((00|//00,70))) (ri))) + (10N(N..1//N)88))
Pr 7 ,n.1]
where crv is a universal constant.
Denote the event in Lemma 2 by Eg and then we know P(E,) > 1 - 8/2. Then from Lemma and Lemma 2 we know that under event E, n E2, have for all R(D):
Pr- (-17, - ,
+)] ,
e clog(No, (1gg))
By0 A mpp
(4)
N
where e is a universal constant.
Then under Assumption 3. we apply the mean value theorem between (T()) - (To) and r(71) r(To) to and ensure for all r R(D) that
cn. Logg, (og
Epo -
-
(5)
N
where K = infee(-rmax.Pma) (w) measures the non-linearity of the link function 4.
15

---

Published as a conference paper at ICLR 2024
Step 2: Pessimistic offline RL. Let rif denote argmin,ER(D)) J(;rr, PT) Brauptoo [r(r)] Then
can bound the suboptimality of स as follows:
J ]mtaiir" r", P*) J[R; PT)
(J (Teari r" P*)
E romer | (r))) (J(F:r", P*) B Byramoor (r"()))
(J (Teari r", PP*) E Ereeera (r" (T(())) (J pint P.) E Eyouror tre frime (T)]))
(J(trr", P*) Bynmerr lr" (r)) (J(H; R Po) Brreet (n (T))
( (Teari P*) - Brapher (r" (T))) - (JTrri ronn P*) - Ermemer (
(rinf Temm (T)])
Re o' meee ((r (T") (r²))) - (rinf (79) - inf (T'
(9rs Tear, prof) V Bro [Ir (17) - (+(()) rinf (r0)
pint mear
(+1)
</ C3igrn Tears prof NR? (o,,N,,
N
where the second step is due to = argmax R(D) [ P*) - Erypaa [r(T)], the third step is due to rine argmin, J( P*) Bromes [r(r],, the fifth step comes from the definition of C, (9r; Ttar Pret) (Definition 2 and the last step leverages (5). This concludes our proof.
C.I PROOF OF LEMMA I
The proof largely follows Zhan et al. (2022b). Suppose F is 1/N-bracket of Gr with [F] Ng.. (1/N) and we denote the set of all right brackets in F by F, i.e. F = {f [
3,, such that [f" FJ. Then fix any / E F, we have:
E exp
Σ log
P... (oxh (0 }
f(o f(00 "101111))""11))
N
E
exp log
f(o0 7 Pr. (or (om1pni0 ppnli Tm,1)
N
N
N
II
E
E n=1
Σ
(7m.)) s (1
Se,
(o rm,1)
N
where the first step is due to each sample in D is i.i.d., the third step uses Tower property and the fourth step is from the fact that J minimum 1/N N-bracket.
Then by Markov's inequality we have for any d E (0, 1).
flo"Itm.0 :miil)
PP
Σ
log
log(1/6)
Pr. (o" pm.l)
N
_ ) Pr. (o /
exp
Σ log
[oo[-loo((/]]] S ed.
By union bound, we have for all f EEF
f(o ,m.1) P log (o.(oa/T7a (ran pn.T)
LoL. 3 5/2
where CMLE is universal constant.
Therefore from the definition of 1/N- 1/N-bracket net, we know for all r E Gr, there exists f E F such that ( r!) S f(-17",T), for any trajectories (7", r²). This implies that for all r E 9r.
Pr(o"ITnn rr:1)) Pr. (o pnu prnl,,nnn rn.1)
P
Σ log
CMLE CMLE log(,, I 8/2,
This concludes our proof.
16

---

Published as a conference paper at ICLR 2024
D COMPARISON WITH RELATED WORKS
D.1 COMPARISON WITH ZHU ET AL. (023)
Zhu et al. (2023) considers the linear reward setting under BTL model and they can achieve the following sample complexity:
N N-07 - expl (xp(exxpp4BB))) (xp(4B)))dlo((10))
e2
where R and B the norm bounds the feature vectors & and parameter 8 (defined in Proposi- tion The concentrability coefficient Ciin is defined as
Oin
torpte (o)(T)) (0 (
and Ed the empirical covariance matrix of the dataset N Σn E ( <(r":1))T
Note that all the analysis and proofs in this paper still hold when define the concentrability coefficient as
(G,,, Tear Mret) = max {
E "ewnerrr
(" r(r9) + r(r')] E (Tm.0) r (T".1) r(r".0) + r(rm
0, sup rEgr
Then when specializing the result in Theorem to the linear reward setting under BTL model with this version of concentrability coefficient, the sample complexity is
N N= NOŌ (C,( Ttar, prot))² exp(2r )d looog(R//)))
2
We know that BR 2 maax- In addition, note that in this case, we have Cin 2 and for any r E G,.
B Aepee (r' (7 r" (7t) r(7") + r(r')]
(E (0(7)) x(>))))))))))))))))))) 0)
< E EE (0(70) - o(T (T')]ll>,' 1 -1 -011sp
N ( - (- r(rn.0) + r((,,.))22
= [ upaa (0(7)) ) "(T
N
n=1
where we suppose r (T) (d((), )+) and r(7) ( 0). Therefore we have
C₂ Ttars Pret) I Cli-
This implies that Theorem
I can recover the sample complexity for linear reward setting under BTL model Zhu et al. (023) with only some additional log factors.
D.2 COMPARISON AGAINST PRACTICAL WORKS
Our algorithm is different from the practical algorithms presented in Wirth al. (2017). Although they also use MLE to estimate the reward model, they typically run RL algorithms with respect to the learned MLE rewards without any pessimism. The lower bound in Zhu al. (2023 Theorem 3.9) has shown that this kind of algorithm can fail in the worst cases. In contrast, we use pessimism to circumvent such failure. More specifically, we construct confidence set of the reward model and then evaluate each policy with the most pessimistic reward model inside the confidence set. This the key difference between our algorithm and existing commonly used algorithms in Wirth et al.) (2017). and this modification is crucial to overcome their limit.
D.3 COMPARISON WITH UEHARA AND SUN 2021
Like us, Uchara and Sun 202T proposed a model-based RL algorithm that works under partial coverage, but in the standard RL. setting and with known state-action-wirs -iiee reward function. In
17

---

Published as a conference paper at ICLR 2024
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 the total variation distance, use the Kullback-Leibler (KL) distance. This may be preferable as computing the KI. distance is generally easier than the total variation distance as it arises directly from the MLE objective, practically done in RRigter al. (2022).
E OMITTED DETAILS
In this section we supplement the definition of bracket number for the transition class and advantage function class.
Definition 5 (c-bracket number of transition probability classes). Suppose f¹,5² is a function e-bracket if
with (-|s,,, a), (=(),, a) E R SI for all (s, a) E x A. Then we say (f*,
a)]lı S e all (s,a). The e-bracket number of (+ls,, a) S (-(ss, a) and (-fs - (-
transition probability class Gp, where h E [H - 1] is the minimum integer N satisfying that there exist N e-brackets (fm.1, f
ff.),, Jn= such that for any function Ps. Gp, there is a bracket (f%.1, f%.2) (1l,a where E [N] containing it, ie., (1,, a) S Pr( a) S (-18 for all (8,a).
Definition 6 (e-bracket number of initial state distribution classes). Suppose S 12 E RISi, Then say f2) is e-bracket if f S 1 and || f S The e-bracket number of initial state distribution class Gr, is the minimum integer N satisfying that there exist N e-brackets (fm.1 fn.2) n=1 such that for any Po Gp, there is bracket (fr.1, ft.)) where E [N] containing it, i... fill < Po S fr.
Definition 7 (e-bracket number of advantage function classes), Suppose g',g g2
a function with
g-( a., a²), ".gg (-1s,, a. a E IR22 for all a a²) E S x A A. Then we say (g',g²) ) is e-bracket if g² (1s. a I g"(+|s, a², a²) and l1 (-)s a², a²) - g² a a ][ S e for all (s, a,, a²)) E S Ax A. The e-bracket number of a reward class GA where h E [H] is the minimum integer N satisfying that there exist e-brackets (g" "g" .) )
such for any function A E GA g
there is bracket (g':) .g??) where i [N] containing it, i.e., (-|s, a., a.) S PA, (-1s, a .a))
2-1,,1,, an for all (8, aa,a,, ,,a) E A A.
We use Ngr, (c) and Nga, (c) denote the e-bracket number of Gp, and G Similarly, when the transition probability the advantage function possesses low-dimension embedding, we can also bound the e-bracket number efficiently.
F PROOFS OF LOWER BOUNDS
F.1 PROOF OF PROPOSITION 2
Given any S, A, H, consider MDP with horizon H, state space S = {st, 82 ...,.,,,, ...,5) and action space A = {a .... ..,, In the following discussion we consider the case C 2 and 1 < C < respectively.
Case 1: C 2. Consider the case where the state is fixed throughout an episode. We suppose and P7
the initial state distribution PT is (ss))
215-1 for all 2 i I S. Let
(tar, 18) = 1 for all h E [H] and s E S. Then we can set the dataset distribution μ40 as
the state s and all actions in T are a² except d = a², if the state is s' and all actions in r are a except an a² if the state is not s and all actions in are at. otherwise,
20
(T)
2
20
2(5-1)
0,
where aj is the action step h in Then know
1 2(S 1)
(o,a(s,a))=
vh [ {s'},
1
(o, ,a')= 2' (o,'-1(s,a')
2 20 (o,a = 20
=
18

---

Published as a conference paper at ICLR 2024
It is obvious we have Cst I C' in this setting. On the other hand, since the trajectory whose state is and all actions are is covered by Ttar but not by Ho, we have Ctr = cc.
Case 2: 1 C < Consider the case where the state is fixed throughout an episode. We suppose the initial state distribution of Po is ( - (s = 2-C and Po (s') 2(5-2) 2] for all
3 ssis S. Note that here we require 2 3. When 5 2, we can let Po
and Po(s²) 2 C' and the following analysis will still hold. Therefore here we assume S 2 3 without
loss of generality. Let Tear, (a*1s) = for all h E [H] and s E S. Then we can set the dataset distribution μl
if the state of is s and all actions in are a except a#-1 a² if the state of is 8 and actions r are at except us = a², if the state of is s² and the actions are all a if the state of is not s or 8 and the actions are all a! otherwise.
g
Mu(T) =
20
2(S-2)
0,
Then we know
1
(0, a²)
vh [H) S\ ,
2(S - 2)'
2 - C
(s, aa)
thE [H)
2C'
2C -
MO,r(s',al
Wh E ||| 2]
2C
Ho.H-1(s* a²) = (s ( = C
2C'
It is obvious have Cat C' in this setting, On the other hand, since the trajectory whose state is s and all actions are al covered by Ttar but not by Has we have Ctr = cc. This concludes our proof.
F.2 PROOF OF THEOREM
We consider the case C 2 and C' respectively.
Case 1:C2 2. Consider the case where there is only one state s and two actions at a² Set the dataset distribution 1i0 = W4) where
all actions in r are a! except aæ-1 = a², if all actions in r are al except = a², otherwise,
c (o(T)= = 1 C+
0,
where an is the action at step h т. In the following discussion we will use T! to denote the trajectory where all actions are a except ax-1 a² and 72 to denote the trajectory where all actions are a except an- a². Then we know
(s,
Yh. E [H - -2].
1
1
Mo.8-1(s,a')111 =1
10.
C
C
Ho. o
po.n(s, = C
We consider two different reward function pd and 2
r)t))at)= = () = = = )=) =
wh E H - 2).
( = r =1, T
= 0,
(s, at) = (s, =1,
() = r
19

---

Published as a conference paper at ICLR 2024
Then we have two MDPs, M1 and M2 whose reward functions are r and 7² respectively. can be easily verified that (Mi, Ho) E @nt(C), (M2, mo) E (C))
Further, let M) denote the suboptimality of policy xr in M, then we have for policies ",
M1T; + L(T; M2) 2 2.
Now can apply Le Cam's method, which leads to the following inequality
[o[[(T,M]] exp(-NVKL no @ pn @ Prollpo @ p1 @ Pra)).
inf sup Ma)
It can be observed that KL Mo & mi 8 P. since r (+ = (7 -
(772) 1. Therefore we have
1 ED] 2 2
inf Ma)
sup
Case 2: 1 < <. Consider the case where there are two one states 8 8² and two actions a² a² We suppose the initial state distribution of Pt is fixed as (s*) C 1 and Pj (s²) In addition, the state will stay the same throughout the whole episode. Then we can set the dataset distribution Ho Mu where
C.
if the state of r s and all actions in T are al except a = a². if the state of r is s and all actions in are a' except a², if the state of is s and the actions are all a!, otherwise.
(D(T)=
In the following discussion will use 7 to denote the trajectory where state is s and all actions are a² except d = a²: 7 to denote the trajectory where state is s² and all actions are at except a = a²: 7 to denote the trajectory where state is s² and all actions are at, Then we know
C
(s aa) C
wh E (H),
(0 ,a") = 20 -2
Yh E H - 2]
C
H0. (2t) = Ho.H 1 (5) = C-1
C
(s, = HOHH (s) ( = C
C
We consider two different reward function pd and 2
nl(s' a') = r/(s' a²) = (s
r a²) 00
Vh E H 2],
1 ( a²) = 2 a²²) 11
1 ( d²)
( ( 0,
(
Th a')==,
0,
r)(6?,a') =r)( ( -=)==)(((())))))) =0 vh | 1]
(s( (52 1,
= 0.
Then have two MDPs, Mi and M2 whose reward functions are r and x² respectively. It can be easily verified that (Mi, mo) E (C,()), (M2, E (C.
In addition, we have for all policies ,,
I(m;M1) + M2); 2 2(C 1).
20

---

Published as a conference paper at ICLR 2024
Therefore by Le Cam's method, we have
[D([[,,M (C-1) exp (-N N KL (n 8m Pr ( P P:a))
inf sup Ma)
where the KL divergence is 0 since r(r) for all (rt,,2) and ( Therefore, we have
EDIL(T, 2 C-1 2
inf Mz(
sup
In conclusion, we have for any C> 1 and H 2 2,
Ep[J(T':r" PT) , min {
1,1
inf sup # (MuI)
F.3 PROOF OF THEOREM
The proof is inspired by the hard instances in Rashidinejad et al. (2021b). We consider the case C 2 and < < respectively.
Case 1: C 222 2, Consider the case where there is only one state s and two actions a! a',a² aa Set the dataset distribution Ho μ4 where
1 T.
-1 1 po( =
po(T")=
po(
where r" is the trajecotry where the actions are all a and r is the trajecotry where the actions are all a².
We consider two different reward function pd1 and 2
+
F, all the actions in 7 are at, otherwise.
(T)
1
2
T, if all the actions in 7 are at,
2
(T)
otherwise.
2:
Here 0 x is quantity will specify later. Then we have two MDPs, Mi and M2 whose reward functions are pd and 22 respectively. It can be easily verified that (M1, (C)(C') (M2, mo) E (C)(
Further, let MM) denote the suboptimality of policy æ in M, then we have for all policies n [(x;M)) + (T;MM)) x.
Now can apply Le Cam's method, which leads to the following inequality
ED [(T 2 exp - (NN-KL ( @ PP.lll0mm@P.))
inf sup # Mc)
Now we only need to bound KL (10 31 s P,, 11 8/1 &,s) which can be computed follows:
KL
no @
Pr.lIuo @ & Pr2))
-2
Σ
(1(7") (T) (Bern( (ern)
2 2exp(1/2)x²
Then by letting min
have
2' 2exp(112)x
exp(-1)
exp( 11)
C
inf
sup Mc(
ET(L(T,M))
min
*
4
22'
2exp(1 11/2)
21

---

Published as a conference paper at ICLR 2024
states s s² and two actions a' a² We suppose the initial state distribution of Po is fixed as (s') = C - and Po (s²) = C. In addition, the state will stay the same throughout the whole episode. Then we can set the dataset distribution 14 where
Case 2: 1 <C <C<2 2. Consider the case where there
10-11
if the state of s and the actions are all a all a², the state of T 8 and the actions are all a², if the state of r is s and the actions contain a².
21
2
Po(T)
C
0,
Let 7* be the trajectory where the state 8 and the actions are a!. We further consider two different reward function r' and r²:
+ x, if the state is s and all the actions in T are al,
(7)
otherwise.
2
2 I, if the state is s and all the actions in are a!,
(T)
otherwise.
Here 0 < < is a quantity we will specify later. Then we have two MDPs, Mi and M2 whose reward functions are rl and r² respectively. It can be easily verified that (M) (c., (M2, Mo) E (C).
In addition, we have for all policies x,
((T;M) + M(T; (C - 1)x.
Therefore by Le Cam's method, have
inf sup Ep( 2 (C - 1)x exp - Ma)
N. KL (No 19 0 pr & & P
where the KL divergence can be computed as follows:
KL Hg & fr @ Prrlluo @ p1 @ P,a
=2 Σ
po(T") KL [[er
2(C 1) (xp()
C
Then by letting x min
2 2mxp(1 1/) we have
C
Ep Ep[L(T, > (C- (C-1)exp(-1) exp(-1)
C -
(C'-) 1)
inf sup Ma)
4
4 min
2
|
2cxp(1/2)N
In conclusion, have for any C > and HI 1,
BolJ(T''r',P")) - J(Rr"", P')] ]] 2 min {c c-
inf sup (M.)))
N
G PROOF OF THEOREM
The proof still consists of two steps, deriving the guarantee of MLE and analyzing the performance of pessimistic offline RI.
Step 1: MLE guarantee. Note that Lemmal D and Lemma 2 still applies here. Let E₁ and Eg denote the event in Lemma] and Lemma (eamaarresppe respectivel. Following almost the same arguments, we have the following guarantee for the estimation of the system dynamics:
22

---

Published as a conference paper at ICLR 2024
Lemma 3. Under Assumption
with probability least 1 - 8/2, the the following event holds true:
(1)P% Pn(D), Po E Pin(
4h E [H - 11,
- - a) [1] + +eeenee)~ppL ||
(2) (2)
clog HNNGP (1/N)/0)
vh H 11, Pa E Pn(D),
N
[|I66()-P7(00)) PT (0)
+ +Eorna.. [|1666)- PT (8) (1)
(3) (3)Es<Ho..
clog(HINGp, (1/N)/0)
VPb E Po(D).
N
The proof is omitted here. Let &g denote the event in Lemma
Step 2: Pessimistic offline RL. We first introduce the following lemma which suggests that under
event &g, we can evaluate the expected cumulative reward of maar with respect to any reward function E Gy via the system dynamics Pa E PD()):
Lemma 4. Suppose Asusmption 3 is true, Then under Eg, we have for all reward finction r E Gr and P (())) where Pp. (D) that
[Ttarir, P*) [Ttari S Hrmux V cC Ttar) ( log (o/HH1/
N
where Np maxoSASH-I(NGG.
The proof is deferred to Appendix G.I
Let (rinf, Pinf)) denote argmin,ER(D)) PEP... Pa(D) J(:r, P) E Eyyeprr [r(r)]- Then der the event Eg, we can bound the suboptimality of π. as follows:
[Taari r* P³) J(a:r", " ,P)
=[I(Terrs r PT) ErTeper (r* (r))) (J(Frr*,, PO) (r
Tear? P*) - Bromuet inf (T))) ((TTarrar)"" P*) Erwnted (T)]) - (J(Teari int
+ (J piul Tims"
P²)) Ey Exnppea pial Tear (T)]) - (Jataai Fias piul) Eyoupsen mene (r)))
+ (Jataar lul
news piul ) Erwmeer Hear (T))) - (J(f;; r plaat) ) Erwmerr (r)e((
(f)))
(J ri inf piint) - Er Bramuer In inf (r)1) - r PT) - Er [r (T)]) inf Tene P¹) Eroeprer Irint (T)))
(Ttari"" PP) - Era (r)]) - (J(Teari
(J iuf Feni P*) E Brwweet mua (T)]) (J
iul Thus
piul Erapeee Meas (T)))
(R; inf phint) B, Brrane (rdnn(())) (r))) - (J(Rrr* P*) - Byy (r (T))))
J (Tta P*) - Ey (r' (r)]) (T(Taari PP)
Broueed Io (r)))
(Jataar rinf P*) Ey Eynppra ānf (T)]) (JTtaai
brine riuf pfuf Pine Eyaepraa
Tear (T)))
CC Stary Pret xR log(NG (1/N)/8)
HTmmx cCP(19r }. Tear) log (HNN(//N))/)) N
N
where the third and fourth step are due to the definition of म. (rint PPi")) and (1) in Lemma last step comes from Lemma and the proof of Theorem This concludes proof.
The
23

---

Published as a conference paper at ICLR 2024
G.1 PROOF OF LEMMA 4
Let ph be the system dynamics (P:) (P:) for all S h H - Then we have
H-1
J(tarii P*) [ P)
Σ
(Jaaaii Ph) [ ;r; ph- + (J Po) J [ P)).
h=1
For any h E [H 1], we have
[Teari r, pht (Trari vi ph-1)
-B (n.ar))(Trrr.PP
Ph ( (n ( [r(T)]si, "" ,0411
Shil
Σ Ph an ( [r(T)] a1, 01. shti]
#1+1
= =B( ( P*)
Σ (sn+1199 an) - Ph Pr(snt1 sp. an a ( (1) ..
9h+1
Smmax (on, Pt)
|1 an) Pa an)lli]
(Ta())))) log HNom, (1/N)/5)
STmax|
N
where (x a1, sh+1 the distribution of the trajectory t when executing policy
Ttar under the transition probability {Pr H-1 { while fixing the history to be 81, 41,-.. ... 8/+1- Here
the first step utilizes the Tower property, the third and fourth step uses Cuachy-Schward inequality and the last step comes from Lemma
For J (Reari r, PO) [Teari T, P), similarly we have
J (Tarii r, Pd) - J (Ttari P) S mmax (C log(HNop, (1/N)/5)
N
Therefore we conclude that
cC (Tar)) log( HNN((1NN//)))
[Ttari P*) (TTari Hrmax
N
H PROOF OF THEOREM 5
We first derive the guarantee of MLE for estimating A'. Similar to Lemma and Lemma 2 we have the following lemma in the action-bait based comparison setting:
Lemma 5. Under Assumption 7 with probability at least 1 - 8, the following event holds true:
E (Noo atpa Pa, (-1s, a. ,at) ) - PAy, (1s,, a aat,at)) 13) < clog(HNNg, (L/N)/8)
4I E [H].
N
The proof is omitted here. Let E, denote the event in Lemma 5 Then under Assumption apply mean value theorem and obtain that under E4, we have for all [H] that
8
we can
Egnpes a (-1o)) (xpaa(() (1)(ssa)) Ah(s,at) - An(s, An(s,at))
CK2
log log HNg,, (1/N)/8) Vh E {-).
(6)
N
Recall that K infael
M.TacC-rmaeieee Vmar Umase]
On the other hand, note that we have the following performance lemma:
24

---

Published as a conference paper at ICLR 2024
Lemma 6. For any deterministic Markovian policies π and x', we have
H
,,;r"", - J(T';r",
Σ
E swud
The proof is deferred Appendix H.1
The rest of the proof largely follows Uchara et al.
2023). Under the event E,, we can bound the
suboptimality of क follows:
H ((T # # 1sQM(, (7)
P*) J(TTr" PT) S Tmax Σ
Beand B
Srmax
Bandg"
Σ aEA
1 (An(), (( ( (
< (((6)
h=1
where the first step comes from Lemma and the second step due to the definition of ã. Then for any a > O, we have
B Bendy
Σ
(A(A(ss))) (((e,
aEA
<B <B Bodd
Σ 1
> (7(,,)) (1(+, a)]
aEA
(0)) - (x) -
+ An(s, ( 20() 20)
+ E Badd
aEA
By Assumption 6 we have
Σ 1 (( (M(s,)) Q1(+ a1] s $1Al(a/00)).
E E
For the second term, we have
E
gNdd
Σ
()(s,a) I -((66)
-() - (n(s - + 2a)]
aEA
1 E
Σ azl (AA( AN(s,a) (n + An(s,a) 2 2
Egnda
2
aEd
Σ aEA
A7 (s)) - a)(s,a) - (x(), + An(o,a)))
C.A log( HNGA, (1/N)/0) a²N where the last step comes from the definition of Cact and 6
c
Therefore by picking appropriate a, we have with probability at least 1 that
2 3
$=3
7#2
Cx log( HNG (1/N)/8)
J(rtir", - J(frr", cH|
N
H.1 PROOF OF LEMMA 6
For any policies and n', we have that
J( r", P*) - J(mr"", P*)
=Ea (i))) + V (82)
- E (v))
25

---

Published as a conference paper at ICLR 2024
E
1/2 (82)
(11 - (((s1.1)))
1/2¹ (82)
V/2 (82)
+ Er (QT 01) - (s1)]
E
1/2 (82)
V/2 (s2)
+ Eg ((QT(s))))) ) (((()) - (1111))
H
E (1Q7 )) TA (+s))]]
h=1
This concludes our proof.
26


Reviews:
[{"review_id": "nWfAu8A0Ye", "reviewer": "Reviewer_AQNJ", "summary": "This paper analyzes preference-based reinforcement learning in offline setting. Specifically, they propose three algorithms for Offline PbRL. One estimates the reward function using MLE, constructs confidence sets around the MLE and optimizes the policy against the worst reward model under the assumptions that the transition probabilities are known. The second algorithm is similar to the first except that it operates under the assumptions that the transition probabilities are unknown. The algorithm estimates the transition probabilities using MLE and constructs uncertainty sets around the MLE of the transition probabilities. It then optimizes the policy against the worst reward model and the transition probabilities in their respective uncertainty sets. The third algorithm considers the case where preferences are established over actions instead of trajectories. It estimates the advantage function and computes a greedy policy based on the advantage function.\nWhile the paper does not empirically evaluate these algorithms, they theoretically analyze the sample complexity and performance error of the algorithms and show that as long as the offline data covers the target policy,  it can compete with the target policy.\nThey also show that even if the reward is trajectory wise, you can still efficiently learn the policy if the transition dynamics are estimated per step.\nFinally, the paper establishes a partial coverage guarantees for the third algorithm and show that the sample complexity scales with a bound on the advantage function.", "questions": "No questions.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The paper is clearly written.\nThe paper provides several strong and novel theoretically results on preference-based RL in offline setting. Some of these results also generalize the results of Zhu et al for linear function approximators to general function approximators.", "weaknesses": "Although the main contribution is theoretical, it would be nice to see an empirical case study or two  where the given algorithm works as expected.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WAhTMPqgH4", "reviewer": "Reviewer_Ekit", "summary": "The paper aims to investigate preferance based offline reinforcement learning. They consider a setting where the dataset consists of trajectory pairs with a preference. They assume a preference model over the trajectories and come up with an algorithm which has two parts, the first to obtain a confidence set of reward functions using maximum likelihood estimation and the second part is to obtain the policy over this confidence set. Their algorithm provides a guarantee that allows to learn the target policy with a polynomial number of samples.", "questions": "(1) In Section 4.1, it is mentioned the distance between r and r* is computed as total variation distance or l1 norm. Arent r and r* scalars? \n\n(2) Does C_tr (per trajectory concentration coefficient) not depend on \\mu_1? If so, why?\n\n(3) How does C_r(G_r, \\pi_tar, \\u_1) reduce to sqrt(Ctr)?\n\n(4) It looks like pi, mu and d are used interchangeably. I recommend correcting this.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "(1) The problem of reinforcement learning with human feedback, specifically offline preference learning is highly relevant. \n\n(2) Their algorithm provides a guarantee of being able to learn the target policy using polynomial number of samples.\n\n(3) They extend their algorithm to settings with unknown transition kernel and state-action preferences.\n\n(4) They introduce a new single-policy concentrability coefficient to measure the coverage of the target policy on the dataset.", "weaknesses": "(1) There are no implementation details about the algorithms. These algorithms are theoretically sound but there is no intuition for the reader on how to implement them or construct a practical algorithm. \n\n(2) There are no experiments either. So there is no way to check how this method empirically scales. \n\n(3) Several terms in the paper are not well explained. For example, $\\epsilon$-bracketing: what do you mean by g(.|tau1, tau2)? Is g a probability measure, or a preference?\n\n(4) Proposition 1: For epsilon being arbitrarily small, and the bounds B and R being arbitrarily large, log N_G_r can be arbitrarily large making the sample bounds weak.\n\n(5) The sample bounds i.e. sample complexity N = O(..log (..1/N)). How can N be on both sides, something seems missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "00wY1hV612", "reviewer": "Reviewer_1qtd", "summary": "### Contributions\n* This paper proposed the first algorithm for offline trajectory-wise PbRL with general function approximation and under partial coverage.\n    * The reward function can be defined over the whole trajectory, or for each state action pair.\n    * Extending to the case where transition kernel is also learned, and the case where data is composed of action comparisons, rather than trajectory comparisons.\n* Setting: finite horizon MDP with trajectory-wise reward.\n* Preference model: known link function.\n* Goal: ϵ-δ PAC offline RL: use offline dataset {(traj 1, traj 2, preference signal)} to learn the optimal policy, with unknown reward (extended to also unknown transition kernels).\n* Key innovation: function approximation\n    * Use a given realizable function class Gr to learn the reward function r.\n    * Measure the complexity as the ϵ-bracketing number of the set of preferences induced by Gr.\n* If transition kernels is known:\n    * Algorithm\n        * (1) MLE the reward, r\\hat, using the data; (2) construct a confidence set around r\\hat; (3) distributionally robust planning to jointly max total reward and stay close to some reference trajectory, under the worst-case reward in the confidence set.\n    * Analysis\n        * This paper developed concentrability coefficient for preference-based feedback (Sec.4.2) and discuss the relation bw per-trajectory concentrability coefficient vs per-step concentrability coefficient (Sec.4.3). This result indicates that trajectory-wise feedback is intrinsically harder than step-wise feedback in offline PbRL.\n        * The resulting PAC bound (under Eq.2) depends on this coefficient and also the ϵ-bracketing number of the function class.\n* If transition kernels is unknown:\n    * Algorithm: also do MLE and confidence set for transition kernel.\n    * Analysis: concentrability coefficient.\n* If action-based comparison:\n    * Assuming that the preference feedback is based on the Q value at the state with two actions.\n    * Algorithm: MLE the advantage function and output the greedy policy.\n    * Analysis: concentrability coefficient.", "questions": "* It seems to me that the link function in Eq.1 is known? Would it work if the link function is unknown?\n* For unknown transition kernels, would the result extend to the case where the transition kernels' data are sampled separately from the preference data?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The algorithm and analysis are sound.\n* Considering multiple cases, e.g., unknown transition, action-based comparison, and fitting them within similar algorithmic framework.\n* Nice comparison with previous work in Sec.4.1, Remark 2, 4.", "weaknesses": "* This paper is fully focusing on theory. It would be nice to also have some empirical results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YXXAGqGmij", "reviewer": "Reviewer_2Fsc", "summary": "The authors propose a PbRL algorithm via computing a return utility function, based on MLE. They then construct a confidence set, based on that estimate to solve a planning problem for deriving an approximate, optimal policy. In contrast to most PbRL work, they do not assume the existence of state-action utility. \nThis algorithm forms the base for analyzing the algorithms sample complexity, using a novel trajectory-based concentration coefficient. This analysis is also applied to a setting with learned transition dynamics and action preferences.", "questions": "Please explain \"cannot be relaxed to the per-step concentrability without additional assumptions, such as on the reward structure\" (see above)", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Most work in PbRL focuses on empirical evaluations, therefore additional work considering the theoretical background is important. This work is especially relevant, as it is not restricted to a specific class of function approximation and considers return-based utility. Reward-based utility is usually easier to handle, but can induce abnormalities in the preference setting, therefore the return-generalization is also highly interesting. Adapting the concentrability coefficient to this setting is interesting as it allows to separate (offline) optimization of the policy from the issues of exploration/exploitation.", "weaknesses": "The most substantial weakness of the paper is, that the related work focuses on other, theoretical work, but not practical. E.g. the idea of return-based utility approximation is not novel (e.g. Preference-Based Policy Learning, Akrour, 2011 - see Wirth 2017 for more examples). This is relevant because of two reasons. First, it allows the reader to determine which algorithms fit under the proposed framework and second, it clarifies the differences between the proposed algorithm and other works. Considering the algorithm is mentioned as one of the main contributions, but likelihood-based estimation of the return utility is already known, the novelty of the algorithm is a bit limited.\n\nBesides that, there are several possibilities to improve the presentation:\n- Reward is defined wrt. trajectories, but this is commonly denoted return in the PbRL literature\n- Some relevant information is left to the appendix - mostly the feasible implementation and the comparison to Zu 2023. Especially some details concerning the feasible implementation are relevant for practioners.\n- Remark 3 is not explained\n\nFurthermore, to the reviewer, one of the statements is not obvious:\n- cannot be relaxed to the per-step concentrability without additional assumptions, such as on the reward structure - Why does it follow from the Theorems, that state-action rewards are not enabling this?\n\nAs small remarks:\n- Missing reference: \"..per-step concentrability coefficient Cst commonly used in the general offline RL literature\"\n- Missing reference: \"..It is well-known that when the reward is state-action-wise, the optimal policy π is both Markovian and deterministic.\"\n- Definition 1 is a bit hard to understand, because g is never define.\n- The slack parameter in Sec. 4.1 has the wrong symbol\n- Typo in Alg 2: \"Distributionally robust plnanning\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)