Provable Reward-Agnostic Preference-Based Reinforcement Learning
Authors: Wenhao Zhan
Masatoshi Uehara
Wen Sun
Jason D. Lee
Venue: ICLR 2024 spotlight (2024)
Keywords: reinforcement learning theory
reward-agnostic learning
Primary area: reinforcement learning
TL;DR: PAC reward-agnostic reinforcement learning from preference feedback over trajectories with function approximation.

Abstract: Preference-based Reinforcement Learning (PbRL) is a paradigm in which an RL agent learns to optimize a task using pair-wise preference-based feedback over trajectories, rather than explicit reward signals. While PbRL has demonstrated practical success in fine-tuning language models, existing theoretical work focuses on regret minimization and fails to capture most of the practical frameworks. In this study, we fill in such a gap between theoretical PbRL and practical algorithms by proposing a theoretical reward-agnostic PbRL framework where exploratory trajectories that enable accurate learning of hidden reward functions are acquired before collecting any human feedback. Theoretical analysis demonstrates that our algorithm requires less human feedback for learning the optimal policy under preference-based models with linear parameterization and unknown transitions, compared to the existing theoretical literature. Specifically, our framework can incorporate linear and low-rank MDPs with efficient sample complexity. Additionally, we investigate reward-agnostic RL with action-based comparison feedback and introduce an efficient querying algorithm tailored to this scenario.

Published as a conference paper at ICLR 2024
PROVABLE REWARD-AGNOSTH PREFERENCE-BASED REINFORCEMENT LEARNING
Wenhao Zhan
Masatoshi Uehara"
Princeton University
Genentech
wenhao - zhan@princeton
uehara www.aaaaattttseessese.....
Wen Sun
Jason D. Lee
Cornell University wa4455@cornel..duu
Princeton University
jasonlee@princetooncco
ABSTRACT
ceference-basele Reinforcement Learning (PbRL) is paradigm in which RL agent learns to optimize a task using pair-wise preference- based feedback over trajectories, rather than explicit reward signals. While PbRL has demonstrated practical success in fine-tuning language models, existing theoretical work focuses regret minimization and fails capture most of the practical frameworks. In this study, we fill in such a gap between theoretical PbRL and practical algorithms by proposing a theoretical reward-agnostic PbRL framework where exploratory trajectories that enable accurate learning of hidden reward functions are acquired before collecting any human feedback. Theoretical analysis demonstrates that our algorithm requires less human feedback for learning the optimal policy under preference-basee basse models with linear parameterization and unknown transitions, compared to the existing theoretical literature. Specifically, our framework incorporate linear and low-rank MDPs with efficient sample complexity. Addition- ally, investigate reward-agnosie RL with action- based comparison feedback and introduce an efficient querying algorithm tailored to this scenario.
INTRODUCTION
Reinforcement learning algorithms train agents to optimize rewards interests. However, setting an appropriate numerical reward can be challenging in practical applications (e.g., design a reward function for a robot arm to learn to play table tennis), and optimizing hand-crafted reward functions can lead to undesirable behavior when the reward function does not align with human intention. To overcome this challenge, there has been a recent surge of interest in Preference reeference-based Reinforcement Learning (PbRL) with human feedback. In PbRL, the agent does not receive numerical reward signal, but rather receives feedback from a human expert in the form of preferences, indicating which state-action trajectory is preferred in a given pair of trajectories. PbRL has gained considerable attention in various domains, including NI.P (Ziegler et al., 2019; Stiennon et al., 2020; Wu et al., 2021; Nakano et al., 2021: Ouyang al., 2022: Glaese al., 2022: Ramamurthy al., 2022; Liu et al., 2023), robot learning (Christiano et al., 2017; Brown et al., 2019; Shin et al., 2023), and recommender systems (Xue al., 2022).
Despite the promising applications of PbRL in various areas, there are only few provably efficient algorithms (also known as PAC RL) for this purpose (Pacchiano al., 2021; Chen et al., 2022b). These algorithms focus on regret minimization and iterate through the following processes: collecting new trajectories from the environment, obtaining human feedback on the trajectories, and learning hidden reward functions approach can be slow and expensive in practice as it requires humans in every iteration of dynamic model selection process, which is not easy it may sound. For example, interactive decision- making algorithms that put human in the loop of model learning process such as DAgger (Ross weal-world robotics applications, as has
well as the dynamic model from the human feedback. However, this
et al., 2011) can become impractical when applied to been observed in prior works (Ross et al., 2013; Laskey et al., 2016). In contrast, in practical PbRL
"This work done Comell University.

---

Published as a conference paper at ICLR 2024
applications like InstructGPT (Ouyang al., 2022) and PEBBLE (Lee al., 2021), the majority of preference data are collected by crowdsourcing prompts from the entire world and the supervised or heuristic policies, therefore most of the human labeling process does not depend the training steps afterward. Another line of work (Zhu et al., 2023) focuses on purely offline RI. algorithms to learn a near-optimal policy from offline trajectories with good coverage (e.g., offline data that covers some high-quality policies' traces). Nevertheless, it is unclear how to obtain such high-quality offline data a priori (Chen and Jiang, 2019).
To fill in such gap between theoretical work and practical applications in PbRL, we propose a new theoretical method that lies in between purely online and purely offline methods for PbRL, resembling the framework of InstructGPT and PEBBLE. Our algorithm first collects state-action trajectories from the environment without human feedback. In this step, we design a novel sampling procedure to acquire exploratory trajectories that facilitate the subsequent learning of reward functions which is fully wwarrd-agnosti.. the second step, we collect preference feedback on the collected trajectories from human experts. In the third step, we aim to learn the underlying hidden reward functions using the collected trajectories in the first step and preference feedback in the second step. In the fourth step, we learn the optimal poliey by solving the offline RL problem under the learned reward function. Our approach can be understood as performing experimental design for PbRL, which allows us to separate the data-collection process from the process of querying human feedback, eliminating the need for constantly keeping human in the training loop. For instance, we only need to keep human experts in step 2 above, while we can freely perform hyperparameter tuning model selection for the rest steps without requiring human experts sitting next to the computers. This process can significantly reduce the burden from human experts.
Our contributions can be summarized as follows:
We propose an efficient experimental design algorithm for PbRL. Our algorithm specifically designed for linear reward parametrization, which is commonly used in models such as the Bradley- Terry-Luce model, and can handle unknown transitions. This flexibility allows us to handle non-tabular transition models like low-rank MDPs (Agarwal et al., 2020a) and linear MDPs (Jin et al., 2019). To the best of the our knowledge, existing works with statistical guarantees cannot incorporate these models efficiently. Notably, our experimental design algorithm does not depend on any information of the reward and is reward-agnostic, Therefore, the collected trajectories can indeed be reused for learning many reward functions at the same time.
Our key idea is to decouple the interaction with the environment and the collection of human feedback. This decoupling not only simplifies the process of obtaining human feedback in practice but also results in a significant reduction in the sample complexity associated with human feedback compared to existing works (Pacchiano et al., 2021; Chen et al., 2022b). This improvement is particularly valuable as collecting human feedback is often a resource-intensive process.
To circumvent the scaling with the maximum per-trajectory reward in the trajectory-based compari- son setting, we further investigate preference-based RL with action-based comparison and propose a provably efficient algorithm for this setting. We show that in this case the sample complexity only scales with the bound of the advantage functions of the optimal policy, which can be much smaller than the maximum per-trajectory reward (Ross et al., 2011; Agarwal et al., 2019).
1.1 RELATED WORKS
We refer the readers to Wirth al. (2017) for an overview of Preference-based RL (PbRL). PbRL has been well-explored in bandit setting under the notion of dueling bandits (Yue et al., 2012; Zoghi et al., 2014; Dudík al., 2015), where the goal is to find the optimal arm in the bandit given human preference over action pairs For MDPs, in addition to Pacchiano et al. (2021); Chen et al. (2022b), which we compare in the introduction, Novoseller et al. (2020); Xu et al. (2020) have also developed algorithms with sample complexity guarantees. Novoseller et al. (2020) proposes a double posterior sampling algorithm with an asymptotic regret sublinear in the horizon H. Xu et al. (2020) proposes a PAC RL algorithm but relies on potentially strong assumptions such Strong Stochastic Transitivity. Note both of Novoseller et al. (2020); Xu et al. (2020) are limited to the tabular setting.
Our algorithm shares similar concept with reward-free RL which focuses exploration in the state-action space without using explicit rewards. Reward-fres free RL has been studied in many MDPs such tabular MDPs (Jin et al., 2020a), linear MDPs (Wang et al., 2020), low-rank MDPs (Agarwal
2

---

Published as a conference paper at ICLR 2024
al., 2020a) and several other models (Chen et al., 2022a; Zanette et al., 2020; Qiu et al., 2021). The goal of reward- free RL is to gather exploratory state-action data to address the challenge of unknown transitions before observing rewards. In contrast, our approach aims to design single exploration distribution from which we can draw trajectory pairs to solicit human feedback for learning reward functions. Our setting can be considered experimental design for PhRL..
2 PRELIMINARIES
We introduce formulation of Markov decision processes (MDPs) and PbRL.
2.1 MDPs WITH LINEAR REWARD PARAMETRIZATION
We consider finite-horizon MDP M = (S, A, P",,.",.. .r: H), where S is the state space. A is the action space, P {PP) h==1 is the ground-truth transition dynamics, r = (ri is the ground- truth reward function, and is the horizon. Specifically, for each h E [H] ( (1,... H)), P% S A + (SS) and r S x A- [0, 1] represent the transition and reward function at step h. respectively. Moreover, we use Pi(-) to denote the initial state distribution. Here, both r" P are unknown the learner. In this work, we assume that the cumulative reward of any trajectory
r (8h, (=)== does not exceed max i.e., Σx=1 I' (* (n) S maax-
Policies and value functions. A policy π { where Th : S (AA) for each h [H] characterizes the action selection probability for every state at each step. In this paper, we assume the policy belongs
policy class II, which can be infinite. Given reward function and policy T, the associated value function and Q function at time step are defined as follows: (s)
E,, EE Fh (Sh, Isn $) (s, a) E-. 1En = Th (s. an)[s, = 8, 0n =]. Here, En [-] represents the expectation of the distribution of the trajectory induced by a policy and the transition pa We use Vr. denote the expected cumulative rewards of policy x with respect to reward function r under Pa, i.e., Vr= = Eg VTT (s), and use V to denote the maximal expected cumulative rewards with respect to reward function under P i.e., VTT. == maxxxe1 V funetion
In partieular, let x* denote the best policy in II with respect r", i.e., arg =a V*", , In contrast, we denote the globally optimal policy by Fg arg max V"' where Ma is the set of all Markovian policies. Note that when II o I x" might not be optimal compared to Tg.
Linear reward parametrization. To learn the unknown reward function, it is necessary to make structural assumptions about the reward. We consider a setting where the true reward function possesses linear structure:
Assumption 1 (Linear Reward Parametrization). We assume MDP has a linear reward parametriza- tion with respect to (w.rt.) known feature vectors @n (s, a) Rd. Specifically, for each h E [H], there
exists an unknown vector 0% E TR& such that ( a) (5( a) 6% for all (s, a) E S x A. For technical purposes, we suppose for all s E S, A. E [H), we have (1)((s,)) a)ll S R. |10 S B.
Note when d
[ and setting (n,s,, a) as one-hot encoding vectors, we can encompass the tabular setting. Linear reward parametrization is commonly used in the literature of preference- based RL with statistical guarantees (Pacchiano et al., 2021; Zhu al., 2023). See Appendix A for more details.
Notation. We use (T) = El (sh an) to denote the ground-truth cumula- tive rewards of trajectory T. In particular, (T)
(Ø(T), where O(T) := 10t .... TT We
[dr (81, a1) T ,... (nn(sn, an) "JT 00
((x)) to denote
Bx>((rp=))l(()) [o)]) for simplicity. We also use @(B) to denote the set (0 E Rd : ||0] < B)
and @(B, H) to denote the set {0 Rdd 0 0 .... On] 0n e @(B), Vh [#]] n (0
Rdd :d((T) 8*) Tmaxx V.J. We the notation f Ogg) when there exists universal constant C> 0 such that f S Cy and Ögg) = Ogglog l)
2.2 PREFERENCE-
C-AEEE BASED REINFORCEMENT LEARNING In this paper, we consider a framework for PbRL that mainly consists of the following four steps:
Step 1: Collect a dataset of trajectory pairs Dreward = (7".0, -",1) ) n. where n' = {s 4, s Mi for n E [N] and E (0,
N 1 in reward-agnostic fashion,
Step 2: Obtain preference feedback from human experts for each pair of trajectories in D Dreward- Namely, if trajectory n.1 is preferred over 70. then assign nr 1, otherwise assign 0² = 0.
3

---

Published as a conference paper at ICLR 2024
Algorithm REGIME: Experimental Design for Querying Human Preference
1: Input: Regularization parameter X, model estimation accuracy e', parameters 8.
2: Initialize Σ1 Tl
3: Estimate model P t- P(ll, ,8/4) (Possibly, requires the interaction with the enviroment.)
4: for = ,,. do
5: Compute (,=.00=''0) & arg max," [²(=)) - -(()))<=-
6: Update - = En + (0(T") - - -
7: end for
8: for n= =1=1, 1,..., , N do
9: Collect a pair of trajectories 7 n.. from the enviroment by =n. n" respectively.
10: Add it to Dreward.
11: end for.
12: Obtain the preference labels [o"] for Dreward from human experts.
Run MLE <- arg maxge@(B.F)) L(0, Dreward, {o") )nm)) where L(0, Drwward {o") )nm)) is defined in (1).
14:
Return म arg (
Step 3: Estimate the ground truth reward using the dataset Dreward and preference labels {o")
Step 4: Run RL algorithms (either online or offline) using the learned rewards and obtain a policy क that maximizes the cumulative learned rewards.
The above framework has been applied in practical applications, such as PEBBLE (Lee et al., 2021). However, these algorithms lack provable sample efficiency guarantees. In particular, it remains unclear in the literature how to collect the trajectories in Step 1 to enable accurate estimation of the ground truth reward. In our work, we strive to develop a concrete algorithm that adheres to the above framework while ensuring theoretical sample efficiency. We also emphasize that step is aeward-agnostic, and the collected dataset can be re-used for learning many different rewards as long they are línear in the feature Φ.
Preference model. In this work, we assume the preference label follows the (BTI.) model (Bradley and Terry, 1952) in Step i.e., we have the following assumption: Assumption 2. Suppose for any pair of trajectory (7",7) ),), we have
P(o P(r' > 79) = o(rr ( exp(r" (7)) (exp(
exp(r (r-))
where is the human preference over (7", 72) and (.) is the sigmoid function.
Our analysis will leverage the quantity x sup a Mmps. |1/o'(a) 2xex 2r max) to measure the difficulty of estimating the true reward from the BTL preference model.
3 ALGORITHM: REGIME
We propose algorithm specifically designed for the PbRL setting when the transitions are unknown. In order to handle unknown transitions, we use the following mild oracle:
Definition 1 (Reward-free RL oracle). A reward-free learning oracle P(II, e, 8) can return an estimated model P such that with probability least 1 - 8, we have for all policy π II and h [ 8 E S,a E A. (P) Pí (-)11 e ME (l|ssss) ( < where || || denotes total variation distance (i.e., E {i-norm).
This oracle necessitates accurate model learning through interactions with the environment. The required guarantee is relatively mild since we do not require a point-wise error guarantee, but rather an expectation-based guarantee under the ground truth transition. This oracle holds true not only in tabular MDPs (Jin et al., 2020a), but also in low-rank MDPs (Agarwal et al., 2020a: 2022), where the only assumption is the low-rank property of the transition dynamics, and features could be unknown to the learner. Low-rank MDPs find wide application in practical scenarios, including blocked MDPs (Du al., 2019; Zhang al., 2020a;b; Sodhani al., 2021; 2022).
4

---

Published as a conference paper at ICLR 2024
3.1 ALGORITHM
The algorithm is described in Algorithm 1. Given a learned model P. we use @(x²) = B8 y P) [<)(T] estimate ((x)= == (==((_,))))(T)) The algorithm mainly consists of four steps as follows.
Step I: Collection of state-action trajectories by interacting with the environment (Line 4-11). To learn the ground truth reward function, we collect exploratory state-action trajectories that cover the space spanned by o(-) before collecting any human feedback. To achieve this, at each iteration, we identify a set of explorative policy pairs that are not covered by existing data. We measure the extent which the trajectory generated by (No, π1) can be covered by computing the norm of ((mo) ((TT) ) on the metric induced by the inverse covariance matrix En at time step n. After iterating this procedure N times and obtaining sets of policies {(x",0, a m")))) m== we sample N exploratory trajectory pairs by executing the policy pairs (T 7))) for n E [M]. Notably, this trajectory-collection process is reward-agnostic and thus the collected samples can be used to learn multiple rewards in multi-task RL.
Step 2:
Collection of preference feedback by interacting with human experts (Line 12). If trajectory 7".1 is preferred over T".0, then assign o" = 1. otherwise assign o" 0.
Step 3: Reward learning via MLE (Line 13). We adopt the widely-used maximum likelihood
estimation (MLE) approach to learn the reward function, which has also been employed in other works Ouyang et al. (2022); Christiano et al. (2017); Brown et al. (2019); Shin et al. (2023); Zhu et al. (2023). Specifically, we learn the reward model by maximizing the log- ligelikeldhood L(0, Dreward, {o") I==1):
Eninlog log (0" -o( ((7.)) ((F"-)))) + 11-100 -²)) (10, ((T=)))) - ((*))))). (I)
Step 4: RL with respect to learned rewards (Line 14). We obtain the near-optimal policy that maximizes the cumulative learned rewards.
Our algorithm differs significantly from the algorithms proposed in Pacchiano et al. (2021); Chen et al. (2022b). In their algorithms, they repeat the following steps: (a) collect new trajectories from the environment using policies based on the current learned reward and transition models, (b) collect human feedback for the obtained trajectories, (c) update the reward and transition models. A potential issue with this approach that every time human feedback is collected, agents need to interact with the environment, causing a wait time for humans. In contrast, our algorithm first collects exploratory trajectories without collecting any human feedback Step Then, we query human feedback and learn the reward model in Step 2-3, As a result, we decouple the step of collecting exploratory data from that of collecting human feedback. Hence, in our algorithm, we can efficiently query human feedback in parallel, mirroring common practice done in InstructGPT. Moreover, algorithm's design leads to lower sample complexity for both trajectory pairs and human feedback than Pacchiano al. (2021); Chen al. (2022b). See Appendix A for our technical novelty.
Remark 1. Our collection method in Step 1 shares a similar idea to active learning. See Appendix A.
Remark 2. The majority of computational cost lies in line 5 in Algorithm To implement the algorithm, grudient ascent can be applied here to solve the optimizution problem. See Appendix A.
Remark 3. In Step 4 (Line 14), it is not necessary to use the same P as in Line 3. Instead, any sample-efficiett RI. algorithm can be employed w.r.t the learned reward such as Lee et al. (2021).
3.2 ANALYSIS
Now we provide the sample complexity of Algorithm 1 as shown in the following theorem.
Theorem 1. Let
x2 4HRE N 5 B M ( 1og(1/0)),
6'5
6
2
/ 6BR H dogg
Then under Assumption and 2, with probability least 5, we have Vr" > -
Note the sample complexity in Theorem does not depend the complexity of II and thus we can learn arbitrary policy classes. When II 1M we have πI" = Tg and thus we can compete against the global optimal policy.
5

---

Published as a conference paper at ICLR 2024
Since the sample complexity of human feedback, denoted by Nham is equal to N, Theorem 1 shows that the sample complexity of human feedback required to learn an c-optimal policy scales with Ó(1/²)) and is polynomial in the norm bounds B, R. the horizon H, and the dimension of the feature space d. Notably, the sample complexity of human feedback Nuun only depends the structural complexity of the reward function, regardless of the underlying transition model. This is because while our theorem requires that the learned transition model accurate enough (e' (BRH²) ) we do not need human feedback to learn the transition model for this purpose. This property of our algorithm is particularly desirable when collecting human feedback is much more expensive than collecting trajectories from the environment. Existing works with sample-efficient guarantees, such as Pacchiano et al. (2021); Chen et al. (2022b), do not have this property. Our algorithm's favorable property can be attributed to the careful design of the algorithm, where the step of collecting trajectories and learning transitions is -agnosti and thus separated from the step of collecting human feedback and learning rewards. Furthermore, note that our results algorithm indeed works beyond low-rank MDPs, as long as there exists a suitable reward-free model-learning oracle. See Appendix A for more details.
As the most relevant work, we compare our results with Pacchiano et al. (2021), which considers online learning in PbRL with unknown tabular transition models and linear reward parameterization. Let Nea and Num denote the number of required trajectory pairs and human feedback, respectively. Then, to obtain c-optimal policy, the algorithm in Pacchiano al. (2021, Theorem 2) requires:
|S |S dd
Nera
Nhum Ō
log
Here omit the dependence on B, R. H to facilitates the comparison. In contrast, in the setting considered in Pacchiano et al. (2021), by leveraging the reward-free learning oracle from Jin et al. (2020a), our algorithm achieves the following sample complexity:
Nira |S| - R2d
log Num =ō ) -0(50
162d 2 log
1
22
where the number of required trajectory-pairs comes from Jin et al. (2020a)[Lemma 3.6]. We observe that our algorithm achieves a better sample complexity for human feedbacks than the previous work while retaining the total trajectory complexity. In particular, our algorithm has the advantage that Nuum depends only on the feature dimension d and not on [S] or [A]. This improvement is significant since obtaining human feedback is often costly. Lastly, we note that a similar comparison can be made to the work of Chen et al. (2022b), which considers reward and transition models with bounded Eluder dimension.
4 REGIME IN LINEAR MDPs
So far, we have considered PbRL given reward- free RL oracle satisfying Definition 1. Existing works have shown the existence of such a model-based reward-free RL oracle in low-rank MDPs (Agarwal al., 2020a; 2022). However, these results have not been extended linear MDPs (Jin et al., 2020b) where model-free techiniques are necessary. Linear MDPs are relevant to our setting because linear reward parametrization naturally holds in linear MDPs. Unfortunately. direct reduction from linear MDPs to low-rank MDPs may introduce a dependence on the cardinality of S without assuming strong inductive bias in the function class. In this section, propose model-free algorithm that can overcome this dependence by making slight modifications to Algorithm 1. We begin by providing the definition of linear MDPs.
Assumption 3 (Linear MDPs (Jin al., 2020b)). We suppose MDP is linear with respect some known feature vectors Φ (s, E (R E [H) E S, E A). More specifically, for each h E [H], there exist d unknown signed measures Pi (((()) ,... ((d))) over S and an unknown vector 0g IRd such that (- a) = (n a) (+,(-) and (s, a) = (n(ssa) 0% for all (s, e For technical purposes, we suppose the norm bound || (s))22) S vdl any E S.
E A.
In addition, we use NIT(e) denote the covering number of II, which is defined as follows:
Definition 2 (e-covering number). The e-covering number of the policy class II, denoted by Nin(e). is the minimumn integer n such that there exists a subset II' C II with [II' = n and for any π E II there exists nt II' such that max (T((s)) T (+18) S

---

Published as a conference paper at ICLR 2024
Algorithm 2 REGIME-1in
Input: Regularization parameter X. feature estimation sample complexity K.
Call Algorithm 4 with generating K trajectories by interacting with the environment.
Call Algorithm 5 with reward function (r/ ) to estimate (δ(T))n, for all т E fT E [ e [d] using K trajectories. Let ((④)) = (T) (T)] is (o(T))). for 1,... ,N do
where the j-th entry of on (*)
Compute (T xn.1) < arg mag en [0(=7)) 2( )ll_)
Update Em = S. (ō(m²) -( (()T)) o(r²)))
end for for -........ do Collect a pair of trajectories T".0, n from the environment by x" , respectively.
Add (rm:0, )".1) to D reward
end for
Obtain the preference labels Jo from human experts.
Run MLE + arg minse ((B,H) (0, Droward, {o(*) (o()))_).)) jmm=)).
Return arg EI (f) where VT(F) obtained by calling Algorithm with reward function F {fn 1 for all ı where (s, = (s.
4.1 ALGORITHM
The reward-free RL oracle that satisfies Definition 1 for learning accurate transitions may be exces- sively strong for linear MDPs. Upon closer examination of Algorithm 1, it becomes apparent that the learned transition model solely used for estimating ((x). Therefore, our approach focuses on achieving precise estimation of d(T).
Our main algorithm is described in Algorithm 2 with subroutines for estimating H(T). The overall structure of the primary algorithm resembles that of Algorithm 1. The key distinction lies in the part to accurately estimate 5(T) within the subroutines, without relying on the abstract reward-free free RL oracle (Definition 1). In the following, we provide brief explanation of these subroutines. The detailed descriptions of these subroutines deferred to Algorithm 4 and 5 in Appendix B.
Collecting exploratory data to learn transitions. Being inspired by the approach in Jin et al. (2020b); Wang et al. (2020), we construct an exploratory dataset by running LSVI-UCB (Jin et al., 2020b) with rewards equivalent to the bonus. Specifically, in the k-th iteration, recursively apply the least square value iteration with a bonus term {b) (s,, a) )) which is introduced to induce exploration. This process yields an exploratory policy z² based on exploratory rewards (r h== where r = HH. H. We then collect a trajectory by executing policy x² By repeating this procedure for K iterations, we accumulate Appendix B (Algorithm 4). It is important to note that this step involves generating K trajectories through interactions with the environment.
exploratory dataset. The detailed algorithm is provided in
Estimating ((T) using the exploratory data. Let (#(*)) denote the j-th entry of ()(T)) E, (o) dn)]. Then to estimate ((x), we only need to estimate ()(T))n.s for all h E [M],] E [d]
Note that for all π II, we have ((T) = [E, (11, I,, Er, [ (sn, an) []] Here, the key observation is that (ó(z))n. exactly the expected cumulative rewards with respect to the following reward function r/, (s, a) ow((s, a) Oby'' for all h E [H]] (up to an R factor) where 0/.3 Cj for h' = h and B/. = 0. otherwise (h' a h). Here e, is the one-hot encoding vector whose j-th entry is Therefore, with the collected dataset, we can run the least square policy evaluation to estimate (d(T))).,) The detail is in Algorithm 5 in Appendix B.
4.2 ANALYSIS
Now we present the sample complexity of Algorithm 2. The formal statement and proof are deferred to Appendix B and E.
Theorem 2 (Informal). By choosing parameters in an appropriate way and setting
7

---

Published as a conference paper at ICLR 2024
( Lo K 6
2 (o N 2 0( An 2n2 loe(1/6) ) 72BR' va vanku=> k
under Assumption 1,2, and 3, with probability at least 1-8, we have V VV' Furthermore,
by selecting a policy class II properly, we have V f 2 V , 2e by replacing log log(NN((e)/0))
Hdlog
12WR
where W (B+(H+))vd) log LA]
The first statement says Algorithm can learn an e-optimal policy with the number of trajectory- and human feedbacks follows:
N K + N N 6 log log +
.Nium - Ö 2
Since the sample complexity depends on the covering number of II, we need carefully choose the policy class. When we choose II to be the log- log-linear policy class:
exp(Ch on (s.
= - [= (a]ss) En'e exp(G) (s, CA E B(,, S, E {
E
although n² F Tg. we can show that the value of x² is close to the value of mg up to e by setting sufficiently large W. This immediately leads to the second statement in Theorem 2. Consequently, to learn an e-global-optimal policy, it concluded that the number of required trajectory pairs and human feedbacks for Algorithm 2 does not depend on |S] at all.
Finally, we compare our work to Chen et al. (2022b), as is the only existing work that addresses provable PbRL with non-tabular transition models. Their algorithm exhibits sample complexities that depend on the Eluder dimension associated with the transition models. However, linear MDPs, remains uncertain whether we can get upper-bound on the Eluder dimension without introducing dependence on (S]. Consequently, our Algorithm 2 the first provable PbRL algorithm capable of achieving polynomial sample complexity that is independent of [S] in linear MDPs.
REGIME WITH OCTION-BASED COMPARISON
The drawback of the current results is that the sample complexity is dependent K, which can exhibit exponential growth in maax under the BTL model. This is due to the fact that suppssS 11/o' /zz) =
(exxp(rmax)) )). Such dependence on Tmax is undesirable, especially when rewards are dense and Tmax scales linearly with H. Similar limitations are present in existing works, such as Pacchiano et al. (2021); Chen et al. (2022b). To address this challenge, we consider the action- based comparison model (Zhu et al., 2023) in this section. Here, we assume that humans compare two actions based on their optimal Q-values. Given tuple (s, a", a² h)), the human provides feedback following Po = 1|s, o, a h) P(a do|s, h) = (AA,ss a"t) - Aî a d²)).
(2)
where Aj, is the advantage function of the optimal policy. Similar to trajectory- based comparisons with linear reward parametrization, we assume linearly parameterized advantage functions:
Assumption 4 (Linear Advantage Parametrization). An MDP has linear advantage functions with respect to some known fnawnfeature vectors on (s,ss) E (d E [H] E S,a a E A) ffr each E [H], there exists unknown vector Et E Ra such that A (s, a) de (s. a) ER for all (s,a) S A.
We assume for all E S,a E A, h. E [H), we have |10% (s. a) < R, |IE S B.
Generally, the value of (s, a)] tends to be much smaller than H since large value of [A] a)l implies that it may be difficult to recover from a previous incorrect action even under the best policy n (Ross et al., 2011; Agarwal et al., 2019). Therefore, by defining Badv sup(,.a) |4 a)), expect that Badv will be much smaller than H, even in scenarios with dense rewards.
In the following discussion, we will use 7(B,h) h) to denote the convex set (S E RRd |K| S B, (d), (s, a), C) < Badv, Vs E S, a E A). We consider the setting where IT = Mar and assume the transition model is known for brevity. In the case of unknown transition models, we can employ the
same approach as described in Section 3 with reward free RL oracles.
We present our algorithm for action-based comparison models in Algorithm 3. In Line 19 we denote
N
L(E, D Div,, 1o" I)) == Σ log (oh.". -01S (n hm ahm..1) - -0s ,..n,)))))
n=l
8

---

Published as a conference paper at ICLR 2024
Algorithm 3 REGIME-action
1: Input: Regularization parameter X.
2: for h 1, H
3: Initialize Σ,, AI.
4: for nur== =,==,.... .N. do
5: Compute: (n 1 mh)...)) arg of en 1 (sn -9) (n 2
6: where dh (8, Rt Bawna (11))))()))))))))
7: Update:
Σn,+t1 =
(sh. v xh.n.o) (n xhk.n.))1) (B ey motha oon (6) (8h, nh,,,0) 0% x x.,n,,))))
8: end for
9: end for
10: for h = 1,.... H do
for
1,...... N do
Sample ~h."" time step h by executing policy Th.n. { (mhnnig
2h Sample actions h.n.0 h.m.0 (-Ishh.)) ah.n.1
hnn! (-1akim)) nh
13:
14:
Add (s*.", ah,,,0, am...)) to Diay-
(These steps involve the interaction with environment) 16: end for
end for
18: Obtain the preference labels {o In=1 for D
ady from human experts. Run MLE Én arg mingez(B,R) LLE, Dh (o j==)).
20: Compute: for all S,Sa E A, h [M]:
21: (n a) + (s,s,a) a) Eh. (s) + arg max.ed (n(
22: Return 7े (f)
+(1 (1-0"~m) (1EE: (n (n - 608 "asmn,ale a(mm))))))
where DA
adv = fshhie amim a...N..
In=l.
5.1 ANALYSIS
Theorem 3. Let
A 2 4R2,
N2 T BR log(1/8)/e3
where Kadv sup B [x)) in REGIME-action Then under Assumption 4, with proba- bility at least 1- have Vr" -rr
Theorem demonstrates that for the action-based comparison model, the number of required human feedbacks scales with Kadv instead of к. This implies that when a is a commonly used sigmoid function, the sample complexity is exponential in Badv rather than Tmax. Crucially, Badv always less than equal to Tmaxx: and as mentioned earlier, Badv can be of H)) even in dense reward settings where Fmax (HH). Consequently, we achieve superior sample complexity compared to the crajectoyy-based comparison setting.
SUMMARY
We consider the problem of how to query human feedback efficiently PbRL, i.e., the experimental design problem in PbRL. In particular, we design reward-agnostic trajectory collection algorithm for human feedback querying when the transition dynamics is unknown. Our algorithm provably requires less human feedback to learn the true reward and optimal policy than existing literature. Our results also go beyond the tabular cases and cover common MDPs models including linear MDPs and low-rank MDPs. Further, we consider the action-based comparison setting and propose corresponding algorithms to circumvent the exponential scaling with r Tmax of trajectory-basse comparison setting.

---

Published as a conference paper at ICLR 2024
REFERENCES
Agarwal, A., Jiang, N., Kakade, S. M., and Sun, W. (2019). Reinforcement learning: Theory and algorithms. Technical report.
Agarwal, A., Kakade, S., Krishnamurthy, A., and Sun, W. (2020a). Flambe: Structural complexity and representation learning of low rank mdps. arXiv preprint 200.:::0006.08114.
Agarwal, A., Kakade, S. M., Lee, D., and Mahajan, G. (2020b). Optimality and approximation with policy gradient methods in Markov decision processes. In Conference on Learning Theory, pages 64-66. PMLR.
Agarwal, A., Song, Y., Sun, W., Wang, K., Wang, M., and Zhang, X. (2022). Provable benefits of representational transfer in reinforcement learning. arXiv preprini arXiv:2205.14577.
Bradley, R. A. and Terry, M. E. (1952). Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324-345.
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.
Cen, S., Cheng, C.,, Chen, Y., Wei, Y., and Chi, Y. (2022). Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research, 70(4):2563-257)
Chen, J. and Jiang, N. (2019). Information-theoreti considerations in batch reinforcement learning. In International Conference on Machine Learning, pages 1042-1051. PMLR.
Chen, J., Modi, A., Krishnamurthy, A., Jiang, N., and Agarwal, A. (2022a). On the statistical
efficiency of reward-free exploration in non-linear rl. arXiv preprint arXiv:2206.10770.
Chen, X., Zhong, H., Yang. Z., Wang, Z., and Wang, L. (2022b). Human-in-the-loop: Provably efficient preference-based reinforcement learning with general function approximation. In Interna- tional Conference on Machine Learning, pages 3773-3793. 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.
Du, S. S., Luo, Y., Wang, R., and Zhang, H. (2019). Provably efficient Q-learning with function approximation via distribution shift error checking oracle. In Advances Neural Information Processing Systems, pages 8058-8068, PMLR.
Dudík, M., Hofmann, K., Schapire, R. E., Slivkins, A., and Zoghi, M. (2015). Contextual dueling bandits. In Conference on Learning Theory, pages 563-587. PMLR.
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 (tf.::2209113773.
Jin, C., Krishnamurthy, A., Simchowitz, M., and Yu, T. (2020a). Reward-free exploration for reinforcement learning. In International Conference on Machine Learning, pages 4879.
PMLR.
Jin, C., Yang, 7.,, Wang, 7.,, and Jordan, M. I. (2019). Provably efficient reinforcement learning with linear function approximation. arXiv preprint arXiv:1907.05388.
Jin, C., Yang, Z., Wang, Z., and Jordan, M. I. (2020b). Provably efficient reinforcement learning with linear function approximation. Conference on Learning Theory, pages 2137-2143. PMLR.
Laskey, M., Staszak, S., Hsieh, W. Y.-S., Mahler, J., Pokorny, F. T., Dragan, A. D., and Goldberg. K. (2016). Shiv: Reducing supervisor burden in dagger using support vectors for efficient learning from demonstrations in high dimensional state spaces. In 2016 IEEE International Conference on Robotics and Automation (ICRA), pages 462-469.
10

---

Published as a conference paper at ICLR 2024
Lee, K., Smith, L., and Abbeel, P. (2021). Pebble:
Feedback-efficient interactive reinforcement learning via relabeling experience and unsupervised pre-training. arXiv preprins arXiv:2106.0509)
Liu, H., Sferrazza, C., and Abbeel, P. (2023). Languages are rewards: Hindsight finetuning using human feedback. arXiv preprint arXiv:2302.02676.
Nachum, O., Norouzi, M., Xu, K., and Schuurmans, D. (2017). Bridging the gap between value and policy based reinforcement learning. In Advances in Neural Information Processing Systems, pages 2775-2785.
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 ar arXiv:21
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., Parker-Holder J., Tang, Y., Choromanski, K., Choromanska, A., and Jordan, M. (2020). Learning to score behaviors for guided policy optimization. In International Conference on Machine Learning, pages 7455-7454, PMLR.
Pacchiano, A., Saha, A., and Lee, J. (2021). Ducling rl: reinforcement learning with trajectory preferences. arXiv preprint wrXiv:2111.04850
Parker-Holder, J., Pacchiano, A., Choromanski, K. M., and Roberts, S. J. (2020). Effective diversity in population based reinforcement learning. Advances in Neural Information Processing Systems, 10118000-8062..
Qiu, S., Ye, J., Wang, Z.,, and Yang. Z. (2021). On reward-free rl with kernel and neural function approximations: Single-agent mdp and markov game. In International Conference on Machine Learning, pages
PMLR.
Ramamurthy, R., Ammanabrolu, P., Brantley, K., Hessel, J., Sifa, R., Bauckhage, C., Hajishirzi, H., and Choi, Y. (2022). reinforcement learning (not) for natural language processing?: Bench- marks, baselines, and building blocks for natural language policy optimization, arXiv preprint a.0.v:2210.01241.
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 artificial intelligence and statistics, pages 627-635.
Ross, S. Beiik--Brrkhudrov, N., Shankar, K. S., Wendel, A., Dey, D., Bagnell, J. A., and Hebert, M. (2013). Learning monocular reactive uav control in cluttered natural environments. In 2013 IEEE international conference on robotics and automation, pages 1765-1772. JEEE.
Shin, D., Dragan, A. D., and Brown, D. S. (2023). Benchmarks and algorithms for offline preference- based reward learning. arXiv preprint arXiv:2301.01392
Sodhani, S., Meier, F., Pineau, J., and Zhang, A. (2022). Block contextual mdps for continual learning. In Learning for Dynamics and Control Conference, pages 608-623. PMLR.
Sodhani, S., Zhang, A., and Pineau, J. (2021). Multi-task reinforcement learning with context-basedd representations. International Conference on Machine Learning, pages 9767-9779. PMLR.
Stiennon, N., Ouyang, L., Wu, J., Ziegler, D., Lowe, R., Voss, C., Radford, A., Amodei, D., and Christiano, F. (2020). Learning to summarize with human feedback. Advances in Neural Information Processing Systems, 33:3008-3021.

---

Published as a conference paper at ICLR 2024
Wang, R., Du, S. S., Yang, L., and Salakhutdinov, R. R. (2020). On reward- free reinforcement learning with linear function approximation. Advances in neural information processing systems, 33:17816-17826.
Wirth, C., Akrour, R., Neumann, G., Fürnkranz, al. (2017). A survey of preference-based reinforcement learning methods. Journal of Machine Learning Research, 18(136):1-46.
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.
Xu, Y., Parker-Holder, J., Pacchiano, A., Ball, P., Rybkin, O., Roberts, S., Rocktäschel, T., and Grefenstette, E. (2022). Learning general world models in handful of reward-free deployments. Advances in Neural Information Processing Systems, 35:26820-2666 268338.
Xu, Y., Wang, R., Yang, L., Singh, A., and Dubrawski, A. (2020). Preference-basee reinforce- ment learning with finite-time guarantees. Advances in Neural Information Processing Systems, 33:18784-18794.
Xue, W., Cai, Q. Xue, Z., Sun, S., Liu, S., Zheng, D., Jiang, P., and An, B. (2022). Prefrec: Preference-based recommender systems for reinforcing long-term user engagement. arXiv preprint arXiv:2212.02779.
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-155
Zanette, A., Lazaric, A., Kochenderfer, M. J., and Brunskill, E. (2020). Provably efficient reward- agnostic navigation with linear value iteration. Advances Neural Information Processing Systems, 13:11756-111 11766.
Zhang, A., Lyle, C., Sodhani, S., Filos, A., Kwiatkowska, M., Pineau, J., Gal, Y., and Precup, D. (2020a). Invariant causal prediction for block mdps. In International Conference on Machine Learning, pages 11214-11224 PMLR.
Zhang, A., McAllister, R., Calandra, R., Gal, Y., and Levine, S. (2020b). Learning invariant represen- tations for reinforcement learning without reconstruction. arXiv preprint arXiv:2006. 10742.
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, 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.
Zoghi, M., Whiteson, S. A., De Rijke, M., and Munos, R. (2014). Relative confidence sampling for efficient on-line ranker evaluation. In Proceedings of the 7th ACM international conference Web search and data mining, pages 73-82.
12

---

Published as a conference paper at ICLR 2024
A DISCUSSION
Validity of Linear Parametrization. this work we consider linear reward parametrization, or more generally, linear trajectory embeddings. Such assumptions are commonly used in the theoretical works of PbRL (Pacchiano et al., 2021; Zhu et al., 2023) and relevant examples can be borrowed from the practical works (Pacchiano al., 2020; Parker-Holder et al., 2020) like the behavior guided class of algorithms for policy optimization. We admit that our analysis cannot cover all kinds of reward parametrization, but we think it is reasonable starting point consider linear function approximation for theoretical analysis.
Applicability REGIME. Our results are not restricted linear MDPs and low-rank MDPs. Our main result (Theorem 1) only requires suitable reward-free oracle for dynamics learning and in practice there exist some oracles ready for use, even when the MDPs are very complicated (Xu et al., 2022). This implies that by plugging in these general reward-free oracles, we are able to deal with general MDPs as well.
Relationship to Active Learning. The trajectory collection process in Step of REGIME utilizes a similar idea to active learning. In active learning, people choose a trajectory pair to query human feedback which can maximize the information gain in each iteration. Similarly, in our algorithm, the estimated covariance matrix En, can be regarded the current information in n-th iteration. Then we choose a pair of policies (T="0 m².1) which can maximize the information gain approximately (line 5, it is approximate because
using approximate dynamics P for evaluation).
Implementation of Algorithm 1. The majority of computational cost of Algorithm I lies in line To implement the algorithm, gradient ascent can be applied here to solve the optimization problem. More specifically, assume that T" and x² are parameterized by nd and v² (for example, they might be parametrized by a neural network). Then the gradient of the objective f(v", v²) := (IØ(=)) - ((r")!ss._ with respect to 10 (gradient of v can be similarly computed) can be computed
0f(1.v') 06(T9) Oro = OuD
E-11 (6(=7)-0(())
Here )(T7) and O(T') can be estimated efficiently by simulating T. and n. in P. For show in Section 4 that each coordinate of 2(T²) is indeed value function with respect to certain reward function under P. Therefore we can apply the techniques in policy gradient literature such as REINFORCE estimate 0ā(a") efficiently.
05(1
Bu we
Oe"
Technical Novelty. The novelty of our algorithm mainly lies in the reward-agnostic trajectory collection procedure (line 4-11 in Algorithm 1). For the other steps in the framework, we follow the common practice in empirical works and thus they are the same as the practical work. Our reward- agnostic trajectory collection procedure takes inspiration from the existing works in reward-free exploration RI. and online PbRL.. However, it is not a simple combination of the existing algorithms. More specifically, our analysis has the following challenges that are not solved in the literature:
First, almost all the reward-free -fredd-free exploration literature is focused on learning the transition dynamics of the MDPs. Our problem is completely different because our main task is to learn the reward function from human preferences. Consequently,
iterative collection procedure (line 4-11 Algorithm 1) also differs from the reward-free exploration literature. For example, Wang al. (2020) is the closest work to ours and studies the reward-free exploration in linear MDPs. They utilize a variant of UCB-LSVI, which is quite different from our collection procedure. Correspondingly, we can not directly use the existing analysis either and need come up with new proofs.
Second, our framework is also different from the existing online PbRL (Pacchiano et al., 2021; Chen et al., 2022b). In their algorithms, the reward-leaminn process and exploration phase not decoupled and the analysis heavily relies on the utilization of optimism. In contrast, our algorithm does not use optimism and thus their analysis techniques also do not apply here.
13

---

Published as a conference paper at ICLR 2024
Algorithm 4 REGIME--xpploration
Input: The number of total episodes K, bonus parameter Bex and regularization parameter Aex. for 1,
Initialize: Qu++(( 4 0, V (1) (+ 0. for = H, ........ do
Compute the covariance matrix: A t Eiz1 (n(5), at (11)) T²) + Aeet.
Compute the bonus and reward:
(+ + min { [ex foxl (+, (-.-)))))))))) ((a))),, h h+ 1 and r - -b, b///H H.
Compute Q function:
on(()) + r,(,,,))) (Ta)) 1
( + Coi Clipjo.H-n-y((uf
where w = i= on (5)
a/)) VE V ($/+1).
Compute value function and policy:
()(() max ()(ss)), +) arg max a) aEA
aEA
end for Collect trajectory 7 (sh, a 1 by running x² ( and add 7 into Dex- end for
Sample K states from the initial states (si")) Ji=1 and add them Din. Return Dex. Din-
Third, our analysis of REGIME-1in differs from the one in the literature on linear MDPs. This is because while the style of our algorithm is akin multi-policy evaluation in linear MDPs, the current literature of linear MDPs mainly focuses on Q-learning-style algorithms for policy optimization (Jin et al., 2019; Wang et al., 2020).
More specifically, in REGIME- Mini, we want to evaluate the policies in a policy class under certain reward function. This brings Wang et al. (2020): our learning difficulty will scale with the size the policy class. This forces find and analyze appropriate policy class that is able approximate the optimal policy while retaining a relatively small size. In addition, a key component of our analysis is the new concentration inequality in Lemma 13, which also differs from the existing concentration lemma in Jin et al. (2019); Wang et al. (2020) and may be of independent interest.
challenge that does not occur in Jin et al. (2019);
B OMIT DETAILS IN SECTION
In this section we present the details of Algorithm 4 and Algorithm 5. means min(max((s IJ, In particular, when estimating (é(T)),.j. the reward function h.j TH (8, a) = dw a) T 0h for all Ií' E [M] (up to an factor) where
Here Clip (1)
[ 1 ej. if h'=h, 0,
otherwise.
Here ey is the one-hot vector whose j-th entry 1. For simplicity, we denote Pr x Suhi, win by Vhiia, Qh.ia whi. and let the estimation (b(T))),, be ())))))))
Then we have the following formal theorem characterizing the sample complexity of Algorithm Theorem 4. Let
dex App = R²2
Box Ry Mow.RRooooddo (og//oKKK///j,.,pp = 1og
11 11 1d log(Ni(())/0)) N
B2 d log log(1/0) (10))
X > 4H K
N2 0(
2
2
14

---

Published as a conference paper at ICLR 2024
Algorithm 5 REGIME-planning
Input: Dataset Dex = {(sh ah sh 1 1==,h=1 Din = {s]
S J bonus parameter Spl and regularization parameter Apt. policy n, reward function (rn)m=1- for h' = H, H,..,, do
Compute the covariance matrix: Anr t -E on (s 1oh,,ah di Jon a T + ApIl. Compute the bonus: bn (:..) & min {Suillo (:: (.))))(( 2(H - h + 11}. end for
Initialize: Q7: (..-) 0, pi. (+1(+) 0. for h' = H, ..... do
Compute Q function:
(5)) CH Chip--
(bxr))))
where w - on (sh. ate) Vist ($/ Compute value function: Vi (.) f- Barny Q1/ (:,a). end for
Compute (=(r)= + R EE P1T"7(111 m)
Return (T)r..
where è' H /a" KH-1 C3 > 0 is universal constant and + exp(2rmax) exp(- exp(-2mmax). Then under Assumption 1 and 3, with probability at least 1 1 6, we have
v -
The proof is deferred to Appendix E.
B.1 LOG-LINEAR POLICY CLASSS
The sample complexity Theorem 2 depends on the covering number of the policy class Therefore we want to find policy class for linear MDPs that is rich enough (i.e., contains near-global-optimal policies) while retains small covering number the same time. Indeed, the log-linear policy class (Agarwal et al., 2020b) satisfies this requirement, which is defined as follows:
exp(SI a)) 11 = { (a(ss) EvEE exp(S) (n Sn [Bdd, W), S, [H]
Here (d, W) is the d-dimensional ball centered at the origin with radius W. The following proposition characterizes the covering number of such log-linear policy class: Proposition Let be the log-linear policy class. Then under Assumption for any S 1, we have Nn(e)) < Hdlog 12WR
Meanwhile, quantify the bias of such log- policy class follows:
Proposition 2. Let W (B+(H++))v)) log [A]
then under Assumption and 3, have
max V S, RENT
where 7g is the global optimal policy.
Combining Theorem 4, Proposition and Proposition 2, we know that the returned policy 7 by Algorithm 2 with log-linear policy classes can indeed compete against the global optimal policy with the following sample complexities:
Nus = K + N= Ō (dd Nuum = =0 122d
15

---

Published as a conference paper at ICLR 2024
C PROOF OF THEOREM 1 WITH KNOWN TRANSITIONS
In this section, we consider the proof of Theorem 1 when transitions are known, i.e., d' = 0 and P P In this case we have (()) d(T). We will deal with the unknown transition in Appendix D.1.
First, note that from the definition of म, we have
v
VR=""
where x² is the optimal policy with respect to the ground-truth reward r², ie., n arg max V n Therefore expand the suboptimality as follows:
V vra (vr"*+ VP + (VR=" - V(* (V -v
(V vF= + (V -V
E 0 0 - -Err 0)]
(Ø(TT) -(()) 0r - 8)
S {1(((T)) - (()) (()))l== 110" - 01
(3)
Φ( (((((=)))))))) - ()T for all n E [N + 1]. Here the third step is due to the definition of value function and the last step comes from Cauchy-Schward inequality. Next we will bound [|((TT) dff)lls and ||0- 0l|xw11 respectively.
where Σn == Ex
First for [|Ø(=*) ((F))ly)) notice that 1N+1 2 En for all [N + I]. which implies
N
N Σ
((5)11 [1Ø(=") -
|
(())ll, S
[k((=00) - "(("">))>>?>>
n=1
n=1
Σ
| o(T 1 2
where the second step comes from the definition n. and nn,1 and the last step due to Cauchy- Schwartz inequality. To bound the right hand side of (4), we utilize the following Elliptical Potential Lemma:
Lemma (Elliptical Potential Lemma), For any R and d 2 1, consider a sequence of vectors {x" pdy In=1 where ||>"| S Rg for all n E [N]. Let En = AI + Σi= x" (x") T, then we have
1+ N
Σ
| E E=
2d
The proof is deferred to Appendix C.I. Since we have X 2 4HR², by Lemma we know
Σ |d(m)00) (( S /2HdN log(1 +N(HH))
Combining the above inequality with (4), we have
2Hdlog(1 + N/(Hd))
[(((*)) -
1 (()))l,,,,, s
(5)
N
For ||0- 100-00' - first note that 0 is the MIE estimator. Let E,, denote the empirical cumulative
covariance matrix AI + (o=((((+")) - "(>**)))
-((t)))))))())))))))))) T, then from the literature (Zhu
al., 2023), know that MLE has the following guarantee:
16

---

Published as a conference paper at ICLR 2024
Lemma 2 (MLE guarantee). For any O and ò (0.1), with probability least 1 6, we have |00 0 Sx S CMLE V (Rd(Hd log(1/6)) + XH
(6)
where & = 2 exp (ax +
and CMLE is a universal constant.
The proof deferred to Appendix C.2. With Lemma 2, to ||0" -rr-0laa Ex- we only need to show Σx+1 is close to ΣN+1- This can be achieved by the following concentration result from the literature: Lemma (Pacchiano et al. (2021) 7). For any À > 0 and E (0, 1), with probability at least 1 - 8, we have
10" 01 2 - 0 2++1 + C H dR2 B log(N/6),
where CCON > 0 is universal constant.
Therefore, combining (7) and (6), by union bound with probability least have that
| 01 S C1 .BBR m.BRrAAH"dlog(//) (ogd)og(N/))
(8)
where C1 a universal constant.
Thus substituting (5) and (8) into (3), have V=(r*) V(r", #) with probability at least 1 as long as
An B B H log dog (og(1
N 2 8
2
C.1 PROOF OF LEMMA
Note that when À 2 R2, we have |,"|s, S for all n [N], which implics that for all n E [N],
we have
| S log 1 ||0 ||>")|,..)
On the other hand, let n denote |,=" 1,, then we know for any E [N - 1]
log det En+1
det(En, + x (x") = log dct( 1--22"""""""""" -=-" log (E.)) log det (1 (E,, 1/2"/ 12-
= log dee((E,) + log det [ (Σ ") T(E, (/211/2
= log (ede(((..)) + log
||x" ||>"|
where the fourth step due to the property of determinants. Therefore we have
N
log
+ ||= E.
|
log det E log det E1 = loggdet EN+1/ det 1,)
1=1
log det I+
Σ n=1
xd
(T7)7).
Now let [di)d denote the eigenvalues of ΣA x0 (T"""" then we know
log dot I+
1
log x" (an)T)
[[(+
< dlog
7
M
d
(1 + X1/11) s dlog
1
NR
dx
$ dlog (1+ N )
where the third step comes from Ed A; Tr DN' x²
(x")T
Mn' ||=0 ||
N
N R3 and
the last step due to the fact that À > R². This concludes proof.
17

---

Published as a conference paper at ICLR 2024
C.2 PROOF OF LEMMA 2
First note that we have the following lemma from literature:
Lemma (Zhu et al., 2023)[Lemma 3.1)). For any X with probability at least 6, we have
10 - 0 10011 01I1DAATSS
50(
R² R2d d + log(1/6)) NHB²
N
where D = -( -
d(
Therefore X x and from the above lemma we can obtain
110 00 10 E 50(v
R + log(1/8))
AH
N
which is equivalent to
|10 0 EE 50(
=0(V2(HH++oog(1/))) AHB
This concludes our proof.
D PROOFS IN SECTION 3
D.I PROOF OF THEBREM 1
Note that from the proof of Theorem with known transition dynamics, we have:
Vr*,+ VT < (Ø(TT) ((=),0" 0) (V - VF:)).
Then we have
V V (0(TT) "(TT",, 0) (7( ('+), -
( (()) 0 -0) + (V vF.a).
(10)
Now we only need to bound the three terms in the RHS of (10). For the first and second term, we need to utilize the following lemma:
Let d,, (s, a) and (s,(s,a) a) denote the visitation measure of policy x under P and P. Then with probability at least 1 8/4, we have for all h E [H] and π II.
Lemma 5.
|| d 11 < he'.
(1I)
Let E denote the event when (11) holds. Then under event ε,, we further have the following lemma:
Lemma 6. Under event E,, for all policy क E II and vector v [01, "..."" where 4n E IRd and
[|,]]| < 2B for all h [H) we have,
Ō(F), (((()))(()))))
BRI?..
Substitute Lemma into (10), we have
VT" yr ( 0(7).0" - θ) 2BRH + -
Then by Cauchy-Schwartz inequality, we have under event E
Vr'r - Vr F [k(x=) "())), 110 - - + 2BRH22 + (VF*' - -VRā). (12)
Following the same analysis in the proof of Theorem with known transition, know
2Hdlog(1 + N/(Hd))
(ल((m)) - - S
(13)
N
18

---

Published as a conference paper at ICLR 2024
Now only need to bound ||0- - 0 xx Similar to the proof of Theorem with known tran- sition, we use En and En, denote AI + Σx= (0(=²0) - ((("")) (( and
Al + - - "(T)))) - ((F respectively. Then under event E₁, we have the following connection between EN+1 and EN+1:
Lemma 7. Under event E,, we have
100 - ---0ls Ullw S V21100 11000--001x++++222BBB +2V2NBRIP
Combining Lemma 7 with Lemma 2 and Lemma 3, we have under event &1 n E
110- - -lls 11
<2110- AllsK+1 2V2NBRH'
$ C2 &BRV / (N// + 2V2N
(14)
where Pr(E2) 2 1- - 8/2 and C2 > 0 is universal constant.
Now we only need to bound (V v which can be achieved with Lemma 6:
V -V = (6((() ) 0) (6(7), 0)
(0(=)) "(="), 0) (Ø(mT) ())) + ()(=) - ()), < <2RRH
(15)
where the last step comes from Lemma and the definition of म.
Combining (12), (13) (14) and (15), we have Vr V * S e with probability at least
â as
long
An B2 R² H d log (1/0))
é' 6BRH
N > 0
22
D.2 PROOF OF LEMMA 5
First notice that d7 (8) = di. (s) and (s. = (a)))s)))) which implies that for all
[H]
d
Σ (5 2h (s,a)|= = Σ ())(s) - (s) (((ls))
5,a
Σ (s)(s) 2T((s)) Σ T(als) Σ (s)(s) d.
Therefore we only need to prove Σ, (2 2 (8) S he for all h E [H. We use induction
to prove this. First for the base case, we have E. |d] (s) (i)) E. (+ (1() s é according to the guarantee of the reward-free learnign oracle P.
Now assume that Σ, |d%. - -r. (s)) S he''' for all H E [M] where h E |H 1]. Then we have
Σ (s) (+)) = Σl Σ (()mm(o'ss)))) 11
(x'ss) -1)))d(()))mm ( (P
Σ dh (a'))()))))))))) (1') Pho
- ((())s'.a)))
5,81
Σ (7') dT((5') E ss') Σ Pr (o))
+ ER Pr ,a') - - P2('''
< (h + 1)c',
where the second step comes from the triangle inequality and the last step is dueto the induction hypothesis and the guarantee of P. Therefore, we have E, | - ( N (h + 1)e'. Then by induction, we know Σ. [d] T. (+)] & he for all h E [H]. which concludes our proof.
19

---

Published as a conference paper at ICLR 2024
D.3 PROOF OF LEMMA 6
Note that from the definition of ((π)) we have
H
(0(T), u) PP)
Ty (sh, an)uh
Σ
Σ
dy (Sh; on (8ts on)
h=
Similarly, we have
"
(0(T),
= Σ Σ
(n) (sn, an)
h=1 Sa
Therefore,
(Ó(T)) - 2(T), u>) S Σ Σ
an), (sh an)l 10% (sn,
h=1 Ph
H
$
2BR
(sh, an) - (sh, an)l
h= An
2BR
Σ hd s BRIHé
where the first step is due to the triangle inequality and the third step comes from Lemma 5, This concludes our proof.
D.4 PROOF OF LEMMA 7
We use AO to denote 0" Ô in this proof. From Lemma 6, we know that for any policy m
(((T)) (()). A00- s BRH?d.
By the triangle inequality, this implies that for any policy x0, T!,
Kō(T²) ~( A0) ((((=) - + 2BRH
Therefore we have for any policy T ,,,,,
( 3( 20) A0)) ((((TT)) ((''), 8(BRI(()
(16)
Note that from the definition of Σ4+1 and ΣN+1, we have
A E =AAT (AT+ + Σ (7(7 - ()( - A0
=112012 +
(0)) m00) 11 A012
N
< 22(1114012 +
Σ
((0(=)).)) - (17)1)),, ,0)p)) + SN(BRH?2)
2 A0 2 + 2))
where the third step comes from (16). This implies that
|| | Alllsyy S A2ll + +222
which concludes our proof.
20

---

Published as a conference paper at ICLR 2024
E PROOFS IN SECTION 4 AND APPENDIX B
E. PROOF OF THEOREM
First note that Algorithm 4 provides us with the following guarantee:
Lemma 8. We have with probability at least 1 8/6 that
Pa P (V (si)] S Ciin / log(An(e)dKHRRO))
where bn is defined in Algorithm and Cin > 0 is a universal constant. Here (81) =
ma V (s1).
Lemma 8 is adapted from Wang et al. (2020)LLemma 3.2] and we highlight the difference of the proof Appendix E.2. Then we consider e'-covering for I1, denoted by C(II, Following the similar analysis in Wang et al. (2020)LLemma 3.3], we have the following lemma:
Lemma 9. With probability - 6/6, for all N/ E [H), policy æ E ECTTT and linear reward function
with Th E [-1,1], 1], have
Q 2N
W (c)) (l)))) Pi WW + 2bw
The proof of Lemma 9 deferred to Appendix E.3. Denote the event in Lemma 8 and Lemma by Ea and &, respectively. Then under event E n &s, we have for all policy C(II, e') and all linear reward function r with гh E 1-],
< P (81) Vi 2E,, P (V (61)
d3 HR log(dKHRNn(())/))
< 2HH AH HH (s ) < 20
S co.
(17)
K
where 6p "2 Here the first step comes from the left part of Lemma and the second step is due to the right part of Lemma 9.
Note that the proof Lemma 13, we calculate the covering number of the function class { (Vr is linear and гh []} for any fixed in (24). Then by Azuma-Hoo Hoeffding's 's inequality and (24), we have with probability at least 1 - 8/6 that for all policy π CIII, e') and all linear reward function with ra E 1, that
< Czll log(Nn(e)) K
Ex PE (s1)
S ED.
(18)
K
==1
where C3 0 is universal constant.
Combining (17) and (18), we have with probability at least - 5/2 that for all policy и E C(II, c')
and all linear reward function r with Ta [-
(r) - Vn I 26g-
(19)
This implies that we can estimate the value function for all C(II, c') and linear reward function with rh E 1-1, up to estimation error 2cg.
Now we consider any policy π E II. Suppose that T' C(II, e') satisfies that
max
[| (-1ss)) <..
(20)
eES
Then we can bound (i*(T) - vー (r) and V Vi for all linear reward function with Th [-1, respectively.
For |VT== Vr.a", |, note that we have the following performance difference lemma:
Lemma 10. For any policy π, n' and reward function
have
H
Σ
Ex p (2 (sh, :) T/((sss) Th (-()s)
h=1
21

---

Published as a conference paper at ICLR 2024
The proof is deferred to Appendix E.4. Therefore from Lemma 10 have
[V
V
Σ
Ex
[100
11 " (sw >), mn)(-))) The (11)))
h'=1
P p- [|
The (-s))l)) S Hé'
(21)
On the other hand, we have the following lemma to bound (VT()) (r)): Lemma 11. Suppose (20) holds and (r), Va (r) are calculated as Algorithm Then for all linear reward function with 0 S r(T) S Tmax, we have
(TT()) V. (r) Goover = He
(dK)
(22)
vdK-
The proof is deferred to Appendix E.5.
Combining (19),211) and (22), we have for all policy a E II and linear reward function r with 0 r(T) S
Tmmxs
(V* - V' S 2ep + Hé' + Ecover
(23)
In particular, since (d(T)),.) = RVr we have for all policy E Il and h E [H] [d].
((o(T))n.s - (m(T))nol s 2Rei - HRe' + Recover
This implies that for all policy æ E IT and any v defined in Lemma 6, we have
[(((()) (0())), w) 2BH + HRe' Recover).
The rest of the proof is the same as Theorem 1 and thus is omitted here. The only difference is that we need to show is a near-optimal policy with respect P. This can be proved as follows:
Fi+ FR (V+*- - (M)
(v 1 V (+()))))))))))))))))))))))))(() + (v (F) V.
< 4eo + 2H + 22coverr
where the last step comes from (23) and the definition of
E.2 PROOF OF LEMMA
Here outline the difference of the proof from Wang et al. (2020)[Lemma 3.2). First, we also have the following concentration guarantee:
Lemma 12. Fix a policy æ. Then with probability least 6, we have for all h [H] and k E [K].
Σ 0%
v (1+21)h422)
PM of) - s'eS
I O(HHHR/oo((KKR//8)
A
The proof is almost the same as Lemma 13 and thus is omitted here. Then following the same arguments in Wang et al. (2020), we have the following inequality under Lemma 12:
aT Tw
Σ Pi (5)) s Bex (ss, SESS
Note that V/ (s) E 10, h] for all S, which implies that
< Σ ( V/ (5) + a) s H +1.
E'ES
22

---

Published as a conference paper at ICLR 2024
Note that Clip is contraction operator, which implies that
s -41 Φ1(s. + +r(((, - (
Ph (s') + =
N'E
s (wh)) )n(s,a) Σ
1 S (eanlon((
s'ES
On the other hand,
Clip (onooo-)
(n(), (((s,))) -
-H-
NEES
This implies that
()) -(6.0) +()00))))))))) S a))
Clipoo.-n+u (n( + (x))))
Σ EEES
The rest of the proof is the same as Wang et al. (2020) and thus omitted.
E.3 PROOF OF LEMMA
In the following discussion will use of denote dh (1), af)) First need the following concentration lemma which is similar to Jin et al. (2020b)[Lemaa B.3];
Lemma 13. Fix a policy x. Then with probability at least - 8, we have for all h E [H] and linear reward functions with Th 1-1,1].
Σ 0% (ViT)(h+))) Σ af s'ES
S O(HHR\/og((KHR/O) A
The proof deferred to Appendix E.6. Then by union bound, we know with probability 8/6, we have for all policy E(Il,,'), E [H] and linear reward functions with ra E [-1,1) that
Σ
Pr. h41
(sh+1))
EPA(s Ph (s,s|ss,,,,,, of (AT(())
9h
e'ES
Let Eg denote the event thar the above inequality holds. Then under & following the same analysis in (Wang et al., 2020) 3.1], we have for all policy æ E C(III, (s, E A. [H] and linear reward functions with rh [-1,1] that
Tw (s (n a) wh
& (s)l
E'ES
Form the contraction property of Clip and the fact that Eves Ph P1 an(s,a)) [- - h 1), h + 1]. we know
CHip--(-A (() (n(ss)) (((()) (((),))) - (1(611,,)) rn S (s)
s'ES
Therefore, under Eg have
2 (m(ssa)
EE(6s1s, (s,
Now we only need to prove under Es, for all policy т C(II, c)) (8, S x A, [H] and linear reward function r with T4 E [[-1,]], we have 27. & "7:"(s,a a). We use induction to prove this. The claim holds obviously for h H Then we suppose for some h [H), we have
23

---

Published as a conference paper at ICLR 2024
Q (s.a) a) I Qha 1 a) for all policy C(I,, (s. E E x A and linear reward function
with rh E 1.] Then we have:
K41 (s)
E Ea (+1) [9ht
- V h+1 (s) = Eowna (11 (8, a)]
This implies that
C(Pp--0H--+))8----(000 (h (()a:: (2)(00)) + (n( 2 Σ
(1( +n((s,)=== = 0%- (s. a).
s'ES
On the other hand we have
( (s. a) < H - h 1.
Therefore we have By induction we can prove the lemma.
2 (s, a) s Q (s,
E.4
PROOF OF LEMMA 10
For any policies n' and æ,, it follows from the definition of Vn and Ven that
V
V
- p-
(1(,, a1) + V (52)
E p- (si)
=Eg' p-
1, (82) (V1'* (81)
[1))
Viri' (82)
+ Er [Q] (81, (s1)
-E p-
V2 V
(82) Vi2 (s2)
+ E [1 (Q
(s1, ), x1(+ss) (+(s)))
E p- 12 (sn. 7/(s),)))))))) ma (+18))
This concludes our proof.
E.5 PROOF OF LEMMA
For any h E [H), suppose max.es 17 (s) - -ir (s)l S C441, then for any E S, A, have
1h7T (s,a) -Q (s, a)) < [ww - whh ())(
K
< SW41
(sn (ss,s)(AAnA)) (Anr) (nr
T=1
K Σ
S6441
(1))
Σ (skr
(h S Sw4iVdK.
Here the final step is comes from the auxiliary Lemma 14 and the fact that Ap 2 R²1 and thus Σ (so a)ll(a.)) < Σ 1 1 K.
Therefore we have
Vin (s) V.. (s) (5)) HC' + VdKew41-
CN' == max
SES
Note that cH+1 0, therefore we have
He
Vdk - (dK) 1
This concludes proof.
24

---

Published as a conference paper at ICLR 2024
E.6 PROOF OF LEMMA 13
The proof is almost the same as Jin et al. (202o B.3] except that the function class of V different. Therefore we only need to bound the covering number My(e)) of Vy"" where the distance is defined as dist(VV V") = sup, (s() - V'()).- Note that V belongs to the following function class:
V Vu,n(s) Ba
Clip--(H- (Hi (n)(s,))
+C . s.
where the parameters (w, A) satisty ||w|| S 2/1 /dK/Aph, |||||
8 Pp
Note that for any Ver,Ar Vwr.Az V. we have
dist(Van..dr AuzzAs) S sup 8.0
(Cin--uu-AA)jjannnnn(j o a)) + (()pp)aa-
(C ON (s, a)) + (0lp:)/cCCcooouur444p/46/cc011aa
S sup s.e
(s) [0pp::/h.....aiicoooooooioohhihh ow
+ sup
< R sup
(wi wz2 T δ
R sup 1
T A2)0
|
S
< R[[w w2ll VIA A2l(F).
where the first and third step utilize the contraction property of Clip. Let Cw be the e/(2R) of {w E Rd ||w||| S 2rmax / ((K/Ap) w.r.. f2-norm and CA be the (c/2R)-cover of (A E Rdxd,
||A||| s Ap Xp } w.r.t. the Frobenius norm, then from the literature Jin et al. (2020b)[Lemma D.5], we have
(e < log (Cvll + log Cal S d log (1 8 ne (Apiee)) + dl do log [ + /2 R2 (Annee) (24)
The rest of the proof follows Jin et al. (2020b)[Lemma B.3] directly so omit here.
E.7 PROOF PROPOSITION
First consider ( and ç' which satisfies:
115a Sk 62, wh (H].
Then we know for any h E [H], s E S,
ST (h a) (n < R.
(25)
Now fix any h E [H] and S. To simplify writing, use s(a) and (a) to denote GI (s, a) and (C)) (n,s, a) respectively. Without loss of generality, assume E. exp(x(a)) s Ea exp(x' (a)).
Then from (25) we have
Σ Exxp(r(a)) < Σ exp(x'(aa) s exp(e:R) Σ exp(x(a)).
Note that we have
exp(x(a))
exp(x'(a))
(-(s)))) TH. (-1s)l1 = Σ
En exp(x((l)) E. (xp(x((aa)))
25

---

Published as a conference paper at ICLR 2024
Ee exp(x(a))) exp(a'dd)) exp(<'(a)) E. exp(x(d))
E. exp(x(a())) En exp(x'(a'))
For any a E A. if exp(((((a) En exp(x'(a))) - exp(x' Ev exp(x(a))) 2 0, then exp(('(a')) - exp((= (a)) Σ exp(<(a)))
exp(((()) Σ
<exple, R) exp(x(a)) Σ
exp(<(a')) expl-c2 R) exp(x(a)) Σ exp(x(a'))
- exp(-e,,) exp((((())) Σ exp(x<aa))
Otherwise, we have
exp(x(a)) Σ exp(x'(d')) - exp(x'(a)) Σ exp(<(aa))
sexp(c=R) Σ exp(<x(a') exp(s((a) Σ exp(x(a)))
-(exp(e, exp(x(a)) Σ exp(x(a)))
Therefore we have
(-1s) T (+1=)l (exp(e2/l) - exp(-ex1() E. exp(x(a)) Ee exp(s(a') Ea exp(x(aa)) Ea exp(2'(a'))
S exp(2e_ R) -1 1.
This implies that for any e S 1,
In2
12WR Hd
Nu(()) < (Nn(a.w)
2R
where the first step uses exp(x) - 1 S x/ when
when x
S In 2. This concludes our proof.
E.8 PROOF OF PROPOSITION
First we consider the following entropy-regularizzed RL problem where we try to maximize the following objective for some
0:
H
max Va T) = E Pk
Σ
(ih, log TA (an(aa)))))
From the literature (Nachum et al., 2017; Cen et al., 2022), we know that we can define corresponding optimal regularized value function and Q function as follows:
(n,( a) (s, + P [V
(a max Eog Qa, (s, an) - a log T. (an (an|s)] Th
where V V²,H41(s) for s S. Note that we have Vi (s) = H(1 + a (Al) for all s e and h E [H]. The global optimal regularized policy is therefore
2x,(Qianss
T (als) - Ear (s,
In particular, in linear MDPs, we have
(),(8,0)) = (n( 00 { 1 (s) (s)ds
SES
26

---

Published as a conference paper at ICLR 2024
Therefore, (s, an( T where
||w2 S B + H(1 + a log [A)vv.
This implies that x, belongs to the log- lineainear policy class II with W = Hog On the other hand, let Tg denote the global unregularized optimal policy, then
(*("", mg) max V(r", x) S (r" (T)) - V(r"; ma)) nlll
= (V"(r" ng) - (r", (Va :gg Vā (r",,,))) mz)) + (Va . - -V" 2 (r",,=, - (r" m.) S a H log AAl
Therefore we only need to let a Hlog to ensure V(r",Tgg) max+en V(r", Se.
F PROOF OF THEOREM 3
First from performance difference lemma (Lemma 10), we have
F
V
E an.
d (sh, R) Qi (sh, " T]
4=1
H
E rdf (ip - - An #)] + E Ban [An (Sn, - (sn, xT))
h=1
+ E a -dj
[An TT) (hh:
E Ben mdj (h((,, An(on, 7)] + E Bendef (An(sn x²) (h T")
h=1
H
Σ
E Ben mdf [A) 7) - An #) + Anh: xT) Ahss [")]
h=1
H
E s/ vdf (00 (8h, 7).5% - En) (0n(sh, x²" x)) -call
h=1
H
E Branet d (sn 7) (n x x²),Eh - EnnIl
H
|I ( (on(s, - Sn (sn, n " "]اا |1sh Eullbrn.nii
(26)
1=1
Next we will bound [|B,,-ay jon(sn, 7) 2n TT" )] ""]x, and 115" - Ell respectively. First
for (B John (sh, 77 cha. (sn, }]l] ">lb==.... notice that Σn,N41 2 En. all E [N + +1], which implies
N [ a [on 7) On π T")]
|| sn maf (sh 7) (s क
N
| ap (o ThghnThnnn Tnm.0) -nn. n Ain. 1
E www. xh.n0) @n(sn, T/.m,1)]11B
- k.
2d + N/d)
(27)
N
27

---

Published as a conference paper at ICLR 2024
where the third step comes from the definition of wh.n. and Th.n. and the last step comes from Elliptical Potential Lemma (Lemma 1) and the fact that 2 4R².
For I on(s (shn, a (ddm, (s ahmn.0) Φn (s a)
En let
Enm denote AI + (on (sh.,, "aati,aaaaa almn.,)
Then similar to Lemma 3, we
have with probability at least 6/2.
k&% E 2
Enll E N41
+ 2Ccond B2 log((/)))
(28)
On the other hand, similar to Lemma 2. MLE guarantees that with probability at least 1 8/2,
E&+ - EillEn.N S 20ML.. V Madv (d + log(1/6)) + XB2,
(29)
where Kaddv 2 + (2xp(Baavv exp(-2BBav)-
Therefore combining (28) and (29), we have with probability at least 6,
I
Enlls S (Kady BR / Adlog(N/o))
(30)
Thus combining (26). (27) and (30) via union bound, we have (*())- Ø) at least 1 - as long
with probability
AR adv
R2 log log log(1/0))
N
2
G AUXILIARY LEMMAS
Lemma (Jin al. (2020b)[Lemma D.IJ). Let AI ΣK doot where Φs E Rd and then we have E 0, \ S d.
28


Reviews:
[{"review_id": "xCIE8KTgm8", "reviewer": "Reviewer_s63Y", "summary": "This paper studies online reward-agnostic Preference-based Reinforcement Learning (PbRL) with linear reward functions, which aims at learning a near-optimal policy with human preferences as feedback. This setting is different from current literature of online PbRL in that the humans are able to get rid of online preferences labeling in the exploration on-the-fly, instead they label the exploratory trajectories after they are complete collected. The paper provides sample efficient algorithms with different reward-agnostic setup: when a model-based reward-free exploration oracle is given, or when the underlying model is linear MDP or low-rank MDP. The theoretical algorithms are complemented with polynomial sample complexity in terms of the MDP parameters and $\\epsilon$. Moreover, the sample complexity can be reduce to $O(\\exp(B_{\\mathrm{adv}}))$ where $B_{\\mathrm{adv}}$ is the $l_\\infty$ norm of the optimal advantage function when action-wise preference in terms of the optimal Q function is provided instead of trajectory-wise preference.", "questions": "The previous work Pacchiano et al. studied the online PbRL with a linear reward function. It seems that the sample complexity of this in the reward-free exploratory stage is better than that of the previous work, which is not reward-free setting. What causes this gap between current work and previous work?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "PbRL and RLHF are highly related to important practical problems such as tuning large models, and they are also proved to be one of the key designs in the success of LLMs. Therefore, the importance of studying the theoretical information provided by human preference data is significant.", "weaknesses": "1. Since the motivation of this work derives from prominent practical problems, the results seem to be limited to guide the use of PbRL of RLHF in real-world problems. Although the results show a reduction of the number of human preference data compared to previous work by collecting a exploratory dataset in advance, it is doubtful whether the algorithmic designs are computational efficient to be implemented to improve the RLHF. Some experiment results (even on toy examples) are appreciated to show the effectiveness of decoupling the human labeling process and online exploration stage. The significance of the results cannot be fully verified without the proof of practical usage of these algorithmic designs, because the proposed algorithms may be computational inefficient, thus explaining the theoretical advantage of such algorithms rarely helps to explain the advantage of current PbRL used in practice.\n\n2. The setting looks like a combination of reward-free exploration and online PbRL, which are both standard in reinforcement learning and extensively studied. Therefore, it is hard to evaluate the technical contributions as a theoretical work. The subroutine to collect exploratory data with linear reward functions (using whether reward-free exploration oracle or linear reward-free exploration subroutine) used for human preferences, the MLE estimation of the underlying reward model, and the planning of the optimal policy seem to be slight modification of standard algorithms in the literature, as long as the proving tools. I recommend to explicitly explain the technical contributions in the paper.", "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": "3dKxm7zEFJ", "reviewer": "Reviewer_m5cB", "summary": "This paper studies Preference-based RL (PbRL) for tabular, linear, and low-rank MDPs. The authors focus on designing PAC algorithms and prove sample complexity guarantees for all proposed algorithms. In particular, the proposed algorithms separate the trajectory selection stage and human feedback stage, which could be very useful in applications since all the human feedback can be queried in a single batch. Finally, the authors also extend their algorithms to action-based comparisons.", "questions": "- At the end of Section 3, you compare to Pacchiano et al. (2021). I suppose that the stated sample complexities are for $(\\varepsilon, \\delta)$-PAC and the dependence on $\\delta$ omitted? I'm also slightly confused because the referenced Theorem 2 in Pacchiano et al. (2021) only provides a regret upper bound. Where did you find the PAC bound?  \n- How computationally expensive is step 1 (e.g., line 5 in Algorithm 1, line 7 in Algorithm 2, line 5 in Algorithm 3)? \n- How do you think will your algorithms perform in practice? Do you anticipate any obstacles when deploying your algorithms (computational or otherwise)? \n- Intuitively, one would think that adaptive trajectory selection which queries human feedback after every selection would be advantageous compared to first selecting all trajectories without observing intermediate human feedback. In other words, you would expect *adaptive* experimental design to perform better than *offline* experimental design (even when it comes to PAC learning). Your results however suggest that \"offline\" trajectory selection does not hurt performance. Can you provide any reasons or intuition for this? \n- Hereto related, do you think that your approach of seperating trajectory selection and human feedback stages is applicable/useful for regret minimization as well? (Beyond trivially reducing your $(\\varepsilon, \\delta)$-PAC guarantees to regret bounds via some explore-then-commit strategy).", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The studied problem of PAC PbRL is interesting and hasn't been studied much before.  \n- As far as I can tell, the contributions of this paper are novel and significant in that (a) the algorithms attain better sample complexity and (b) are arguably more practical by seperating the trajectory collection and human feedback stages.  \n- A main strength of the porposed algorithms is that all the sampling of exploratory trajcetories is done first and only then human comparisons queried.", "weaknesses": "- I think that the presentation can be improved. I know that space limitations are tight, however, removing margins around equations and sections will make the paper much harder to read. A table which compares this paper's results with related work would also help the reader to place this work into the existing literature. This would be particularly helpful since much of the related work does not study PAC algorithms, but only regret minimization, and it is difficult to figure out the current state-of-the-art and open questions in this area from just reading the paper.", "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": "Kvr0nsBkji", "reviewer": "Reviewer_dgpw", "summary": "The authors introduce an algorithm for PbRL, that collects trajectories and preference feedback only in an initial phase and not iteratively. Assuming a linear reward function and an epsilon-exact transition function estimator, they show a novel sample-complexity analysis. This approach is also extended to a linear MDP setting, where it is possible to forgo the requirement of an transition function estimator and directly approximate a policies feature space. They also show a complexity analysis that is independent of $r_{max}$.", "questions": "-", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors consider a relevant problem, which relates to a commonly used variant of PbRL (non-interactive). The given assumptions are reasonable under for many real world scenarios. Linear rewards can usually be achieved with suitable projections and epsilon-exact transition function approximators are also available in several domains. Therefore, the complexity analysis is potentially applicable to a wide range of problems, rendering the work significant. The work is also original, as the authors deviate from the common, reward-based scheme.\nClarity could be slightly improved, as explained in the following.", "weaknesses": "The most substantial weakness of the contribution, is its substantial dependence on the appendix. It is acceptable to move specific details, like a formal proof, to the supplementary, but the main paper should be able to stand on its own. This mostly concerns Theorem 1, which is not sufficiently explained in the main paper. At least the basic idea/concept should be added. Furthermore, Algorithm 4/5 are direct references to the supplementary material.\n\nOn a side note, the relation to $\\hat{P}$ and the related approximation error is not obvious from the used notation, because the dependence is missing from line 5 (and14) of Algorithm 1.", "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": "plbTpy7ZJy", "reviewer": "Reviewer_XEZ8", "summary": "This paper deals with Preference-based RL (PbRL), a framework in which the learning agent collects a pair of trajectories and asks an external evaluator which one is better. Differently from previous works, this paper proposes to decouple the exploration of the environment, which is done through a reward-free oracle, and the active learning of the reward, by querying the external evaluators on previously collected trajectory pairs. Specifically, the paper provides (i) new algorithms implementing this framework for PbRL in both tabular and linear MDPs, which are called REGIME and REGIME-lin respectively, (ii) the analysis of the sample complexity of the latter algorithms, (iii) an alternative feedback model in which the external evaluator provides preferences over action pairs, together with a corresponding algorithm variation that is called REGIME-action.", "questions": "1) While it is widely known that Markovian policies are sufficient to maximize a reward function, it comes as a surprise history-dependent policies are not considered although the feedback is based on full trajectories. I guess this might be a consequence of the linear reward assumption. Can the authors develop on why Markovian policies are sufficient to actively generate trajectories for the feedback collection step?\n\n2) In the Preliminaries section, the paper claims that \"it is necessary to make structural assumptions about the reward\". Do the authors mean that the problem is not learnable without the linear reward assumption, or that *some* structural assumption is needed? Providing a lower bound would be clarifying of course.\n \n3) Related to the previous question, one may wonder whether assuming an underlying reward function is really necessary for PbRL. Can the problem be cast as a direct maximization of the human feedback instead?\n\n4) The action-based preference feedback looks somehow related to inverse RL, where the learner can query an expert on the optimal action for a given state rather than a preference between a pair of actions. Can the authors relate their findings with previous inverse RL literature? Do they think their problem is easier/harder than inverse RL?\n\n5) Can the authors discuss the novelty of their sample complexity analysis w.r.t. prior work? Is there any novel technique they would like to highlight?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- (Originality) To the best of my knowledge, this is the first paper providing sample complexity results for PbRL with an algorithm specifically designed for the PAC setting instead of regret minimization;\n- (Significance) As the authors argue in the paper, their framework where exploration and feedback collection are decoupled can suit better some important applications;\n- (Quality) Although I did not checked the derivations in details, the reported results and the considered assumptions look reasonable;\n- (Clarity) The paper is well presented and clear, even if some comparison with previous works seem overstretched.", "weaknesses": "- (Worst-case complexity) All of the reported results on trajectory-preference feedback come with the huge caveat that the rate may be exponential in the worst-case, as $r_{\\text{max}}$ can be as large as $H$;\n- (Lower bound) The paper does not provide a lower bound on the sample complexity, which makes unclear whether the reported factors are actually unavoidable (especially in $\\kappa$ as the necessity of $|\\mathcal{S}|^2 |\\mathcal{A}|$ cannot be overcome due to the reward-free oracle).\n\nGENERAL COMMENT\n\nThis looks like an interesting paper addressing a relevant problem, which is gaining additional traction given the recent success of RL from human feedback. I found the claim of improved results w.r.t. prior works (e.g., Pacchiano et al., 2021) to be a little overstated: Previous works target regret minimization instead of sample complexity, which arguably makes the comparison spurious. Whereas it is important to show that REGIME improves their sample complexity rate, it is unclear whether the regret can also be bounded, which would result in a worse fit for online settings. Having said that, both the online settings and the online exploration/offline feedback collection look reasonable to me, hence the results in this paper are valuable. For this reason, I am currently providing a slightly positive evaluation, but I am open to increase my score after a deeper inspection of the analysis possibly revealing interesting techniques, and a convincing authors' response on the questions below.", "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)