Is RLHF More Difficult than Standard RL? A Theoretical Perspective
Authors: Yuanhao Wang
Qinghua Liu
Chi Jin
Venue: NeurIPS 2023 poster (2023)
Keywords: reinforcement learning theory
reinforcement learning from human feedback
preference-based reinforcement learning

Abstract: Reinforcement learning from Human Feedback (RLHF) learns from preference signals, while standard Reinforcement Learning (RL) directly learns from reward signals. Preferences arguably contain less information than rewards, which makes preference-based RL seemingly more difficult. This paper theoretically proves that, for a wide range of preference models, we can solve preference-based RL directly using existing algorithms and techniques for reward-based RL, with small or no extra costs. Specifically, (1) for preferences that are drawn from reward-based probabilistic models, we reduce the problem to robust reward-based RL that can tolerate small errors in rewards; (2) for general arbitrary preferences where the objective is to find the von Neumann winner, we reduce the problem to multiagent reward-based RL which finds Nash equilibria for factored Markov games under a restricted set of policies. The latter case can be further reduce to adversarial MDP when preferences only depend on the final state. We instantiate all reward-based RL subroutines by concrete provable algorithms, and apply our theory to a large class of models including tabular MDPs and MDPs with generic function approximation. We further provide guarantees when K-wise comparisons are available.

Is RLHF More Difficult than Standard RL? A Theoretical Perspective
Yuanhao Wang, Qinghua Liu, Chi Jin Princeton University (yuanhao, qinghual, chi j eprinceton.
Abstract
Reinforcement learning from Human Feedback (RLHF) learns from preference signals, while standard Reinforcement Learning (RL) directly learns from reward signals. Preferences arguably contain less information than rewards, which makes preference-based RL seemingly more difficult. This paper theoretically proves that, for wide range of preference models, we can solve preference-based RI. directly using existing algorithms and techniques for reward-based RI., with small or no extra costs. Specifically, (I) for preferences that are drawn from reward-basse probabilistic models, we reduce the problem to robust reward- RL that can tolerate small errors in rewards; (2) for general arbitrary preferences where the objective is to find the von Neumann winner, we reduce the problem to multiagent reward-brid based RL which finds Nash equilibria for factored Markov games under restricted set of policies. The latter case can be further reduced to adversarial MDP when preferences only depend the final state. We instantiate all reward-based RL subroutines by concrete provable algorithms, and apply our theory to a large class of models including tabular MDPs and MDPs with generic function approximation. We further provide guarantees when K-wise comparisons are available.
Introduction
Reinforcement learning (RL) is control-theoretio problem in which agents take a sequence of actions, receive reward feedback from the environment, and aim find good policies that maximize the cumulative rewards. The reward labels can be objective measures of success (winning in a game of Go [Silver al., 2017]) or more often hand-designed measures of progress (gaining gold in DOTA2 [Berner et al., 2019]). The empirical success of RL in various domains [Mnih et al., 2013, Vinyals al., 2019, Todorov al., 2012] crucially relies on the availability and quality of reward signals. However, this also presents a limitation for applying standard reinforcement learning when designing good reward function difficult.
An important approach that addresses this challenge is reinforcement learning from Human feedback (RLHF), where RL agents learn from preference feedback provided by humans. Preference feedback is arguably more intuitive to human users, more aligned with human values and easier to solicit in applications such as recommendation systems and image generation [Pereira et al., 2019, Lee et al., 2023]. Empirically. RLHF is key ingredient empowering the successes in tasks ranging from robotics [Jain et al., 2013] to large language models [Ouyang et al., 2022].
A simple observation about preference feedback is that preferences can always be reconstructed from reward signals. In other words, preference feedback contains arguably less information than scalar rewards, which may render the RL.FF problem more challenging. A natural question to ask is:
Is preference-based RI more difficult than reward-based RI.?
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Existing research on preference-based RL [Chen et al., 2022, Pacchiano et al., 2021, Novoseller et al., 2020, Xu et al.. 2020, Zhu al., 2023] has established efficient guarantees for learning a near-optimal policy from preference feedback. These works typically develop specialized algorithms and analysis in white-box fashion, instead of building on existing techniques standard RI. This leaves open whether it is necessary to develop new theoretical foundation for preference- based RL in parallel to standard reward-based RL.
This work presents a comprehensive set of results on provably efficient RLHF under a wide range of preference models. We develop new simple reduction-baseed approaches that solve mrefreenc-basee RL by reducing it to existing frameworks in awarrd-ased RL, with little to no additional cost:
For utility-based preferences- drawn from a reward-based probabilistic model (see Section 2.1), we prove a reduction from preference-basel RI. reward-based RL with robustness guarantees via a new Preference-te toreettto-wdddd Interface (P2R, Algorithm 1). Our approach incurs no sample complexity overhead and the human query complexity does not scale with the sample complexity of the RL algorithm. We instantiate our framework for comparisons based on (1) immediate reward of the current state-action pair or (2) cumulative reward of the trajectory. and apply existing reward-baa -aaadd RL algorithms to directly find near-optimal policies for RLHF in large class of models including tabular MDPs, linear MDPs, and MDPs with low Bellman-Eluder dimension, etc. We further provide complexity guarantees when K-wise comparisons are available.
For general (arbitrary) preferences, consider the objective of the von Neumann winner [see, e.g. Dudík et al., 2015, Kreweras, 1965), a solution concept that always exists and extends the Condorcet winner. We reduce this problem to multiagent reward-based RL which finds Nash equilibria for special class of factored two-player Markov games under a restricted set of policies. When preferences only depend on the final state, we prove that such factored Markov games can be solved by both players running Adversarial Markov Decision Processes (AMDP) algorithms independently. For preferences that depend on entire trajectory, we develop an adapted version of optimistic Maximum Likelihood Estimation (OMLE) algorithm [Liu et al., 2022a]. which handles this factored Markov games under general function approximation.
Notably, our algorithmic solutions are either reductions to standard reward-based RL problems or adaptations of existing algorithms (OMLE). This suggests that technically, preference feedback is not difficult to address given the existing knowledge of RL with reward feedback. Nevertheless, our impossibility results for utility-based preference (Lemma 2, 3) and reduction for general preferences also highlight several important conceptual differences between RL.F and standard RL.
1.1 Related work
Dueling bandits (uue al., 2012, Bengs et al., 2021] can be seen special case of preference based RL with H = 1. Many assumptions later applied to preference based RL, such as an underlying utility model with a link function (Yue and Joachims, 2009], the Plackett-Luce model [Saha and Gopalan, 2019], and the Condorcet winner [Zoghi et al., 2014] can be traced back to literature on dueling bandits. A reduction from preference feedback to reward feedback for bandits is proposed by Ailon et al. [2014]. The concept of the von Neumann winner, which we employ for general preferences, has been considered in Dudík et al. [2015] for contextual dueling bandits.
Dueling bandits.
RL from human feedback. Using human preferences in RL has been studied for at least a decade [Jain et al., 2013, Busa-Fekete et al., 2014] and is later incorporated with Deep RL [Christiano et al., 2017]. It has found empirical success in robotics [Jain et al., 2013, Abramson et al., 2022, Ding et al.. 2023], game playing [lbarz et al., 2018] and fine-tuning large language models [Ziegler et al., 2019, Ouyang et al., 2022, Bai et al., 2022]. RL with other forms of human feedback, such as demonstrations and scalar ratings. has also been considered in previous research [Finn et al., 2016, Warnell et al., 2018, Arakawa et al., 2018] but falls beyond the scope of this paper.
Theory of Preference-based RL. For utility-based preferences, Novoseller al. [2020], Pacchiano et al. [2021] and Zhan et al. [2023b] consider tabular or linear MDPs, and assume that the per-
'Throughout this paper, by sample complexity we mean the number of interactions with the MDP, while the query complexity refers the total number of calls of human evaluators.

---

trajectory reward is linear in trajectory features. Xu et al. [2020] also considers the tabular setting. However, instead of assuming an explicit link function, several structural properties of the preference is assumed which guarantee Condorcet winner and ensure small regret of a black-box dueling bandit algorithm. Finally, recent work of Zhu al. [2023], Zhan et al. [2023a] consider utillty- preferences in the offline setting, assuming the algorithm is provided with pre-collected human preference (and transition) dataset with good coverage. Compared to the above works, this paper considers the online setting and derives results for utility-based preferences with general function approximation, which are significantly more general than those for tabular or linear MDPs.
For general preferences, Chen et al. [2022] also develops sample-efficient algorithms for finding the von Neumann winner 2, Their algorithm is computationally inefficient in general even when restricted to the tabular setting. Compared to this result, our AMDP-based reduction algorithm (Section 4.2) computationally efficient in the tabular or linear setting when the comparison only depends on the final states. For general trajectory-basee based comparison, our results apply to richer class of RL problems including POMDPs.
Finally, we remark that all prior results develop specialized algorithms and analysis for preference- based RL in white-box fashion. In contrast, we develop reduction-based algorithms which can directly utilize state-of-the-an results in reward-based RL for reference-baset RL. This reduction approach enables the significant generality of the results in this paper compared to prior works.
Preliminaries
We consider reinforcement learning in episodic MDPs, specified by tuple (H,, A. P). Here S is the state space, AA is the action space, and H is the length of each episode. IP is the transition probability function; for each h E [H] and s, a E S x A, [- a) specifies the distribution of the next state. A trujectory т (S x A)a is a sequence of interactions ($1, 01. , ag) with the MDP. A Markov policy
{T S Aatne(m specifies action distribution based on the
current state, while a general policy π { (S x A)h S AAhhe( can choose random action based on the whole history up to timestep h.
In RLHF, algorithm interacts with reward-less MDP environment and may query comparison oracle (human evaluators) for preference information. We consider two types of preferences: utility- based ones and general ones.
2.1 Utility-based preferences
For ubilety-based comparison, we assume there exists an underlying reward function r": (8xAA)
[o, 1]. Given a reward function, the value of a policy can be defined as E,, > r" (sh, ax)] )]
i.e. the expected cumulative reward obtained by executing the policy. An optimal policy is one that maximizes FT [Σ r" (s)) We say that m is e-optimal if TE | r"h,, ax)] Z max, E. |Σ r" (")(,,, ax)]
We also consider setting where the utility is only available for whole trajectory. In this case, we assume that there is an underlying trajectory reward function r" (S x A)" - [0, H), which assigns scalar utility to each trajectory. In this case the value of a policy can be defined similarly as (r-)(r(T))-
In preference based RI., the reward is assumed to be unobservable, but is respected by the comparison oracle which models human evaluators.
Definition (Comparison oracle). A comparison oracle takes in two trajectories Tı, T2 and returns
o Bex(((r (1)) (T=)))))
where a (-) is a link function, and r (-) is the underlying reward function.
Here Ber(p) denotes a Bernoulli distribution with mean p. The comparison outcome o = indicates Ti >- T2, and vice versa. We additionally require that the inputs 71, 72 to the comparison oracle are feasible in the sense that they should be actual trajectories generated by the algorithm and cannot be synthesized artificially. This is motivated by the potential difficulty of asking human evaluators to compare out-of distri--ditiiittionnn samples (e.g. random pixels).
While their paper makes Assumption 3.1 in Chen et al. [2022] that seemingly assumes a Condorcet winner, this assumption actually always holds as n² can be a general randomized policy, so their solution concept coincides with the von Neumann winner.
3

---

In this work, we also consider (s, a) preferences, where Pr[(s1, 01) (22.م2) ((((11, a1) r(82,02) For notational simplicity, we will use denote state-action pair (s, (which can be thought as incomplete trajectory) so that (s, a) preferences can be seen as special case of the comparison oracle (Definition 1). See more details Remark 1.
2.2 General preferences
For general preferences, we assume that for every trajectory pair T' the probability that a human evaluator prefers over s' is
(I) general preference may not be realizable by utility model, so we cannot define the optimal policy in the usual sense. Instead, we follow Dudik et al. [2015] and consider an alternative solution concept, the von Neumann winner (see Definition 5).
M[T, = Pr(r r].
2.3 Function approximation
We first introduce the concept of eluder dimension, which has been widely used in RL to measure the difficulty of function approximation.
Definition 2 (eluder dimension). For any function class F S (X - R), its Eluder dimension dimg(F (F.) defined as the length of the longest sequence {I1, 32,.... C X such that there exists é' 2 so that for all i E [ri], I; is é' é'-independent of its prefix sequence {I1,..., 1i-1h. in the such that
sense that there exists some fú,
E
((fi (x)))) se and 1(fi - (.)
Intuitively, eluder dimension measures the number of worst-case mistakes one has make order to identify an unknown function from the class F. It is often used as sufficient condition to prove sample efficiency guarantees for optimism-based algorithms.
As in many works on function approximation, we assume knowledge a class of reward functions R and realizability.
Assumption (Realizability). r" E R.
We further use R == cclc 0), 0 R} to denote the reward function class augmented with bias term. The inclusion of an additional bias due the assumption that preference feedback is based on reward differences, so we could only learn r* up to constant. We note that for the d-dimension linear reward class Rtinear, dimp,(Rnnaal (Rinear) < O(d), and that for general reward class 1/55// R. dim < O(Hding (R, 2/2) /c). The details can be found in Appendix B.
3 Utility-based RLHF
Given access to comparison oracles instead of scalar rewards, a natural idea convert preferences back to scalar reward signals, so that standard RL algorithms can be trained on top of them. In this section, we introduce an efficient reduction from RLHF to standard RL through preference-to- reward interface. On high level, the interface provides approximate reward labels for standard RL training, and only queries the comparison oracle when uncertainty is large. The reduction incurs small sample complexity overhead, and the number of queries to human evaluators does not scale with the sample complexity of the RL algorithm using it. Moreover, solicits feedback from the comparison oracle in a limited number of batches, simplifying the training schedule.
3.1 A prefereence-o--rewarre interface
The interaction protocol of an RL algorithm with the Preference-ue to-eneeett---wrrdd (P2R) Interface is shown in Fig. 1. P2R maintains confidence set of rewards B,.. When the RL algorithm wishes to learn reward label a trajectory 7. P2R checks whether B, approximately agrees on the reward of т. If so, it can return reward label with no queries to the comparison oracle; if not, it will query the comparison oracle on т and fixed trajectory Th and update the confidence of reward functions. The details of P2R are presented in Algorithm 1.

---

Algorithm Preference-to-Reeward (P2R) Interface
1: B, + R. + f}. Dhis +
2: Execute the random policy to collect TD
3: Upon query of trajectory
4: if (f, E Drist then
5: Return A
-r((m)) 6: if' "max,," ((()) (((m) < 2eg then
7: f+ -(T(()) (TT)) for an arbitrary E B,
8:
Duist t Dist U (f
9:
else
10:
Query comparison oracle m times on T and Tu: compute average comparison result
11:
i f argmin H, (z o), D DU (f,T), Dhist
Dist U (f,
12: Update B,
B, - f f TTE, B, :.::E ((r)ED r(7)) - =)) $ $
13: Return f
(s, a)
Reward-less MDP
s'
RL Algorithm
To
Preference-to-Rewarr Interface
Comparison
Oracle
Optional
Figure 1: Interaction protocol with the reward learning interface.
The performance of P2R depends on the RL algorithm running on top of it. In particular, we define sample complexity of standard reward- based RL. algorithm s as follows.
Definition 3. An RL algorithm s is g(c)-robust and has sample complexity C(e, 8) if can output an e-optimal policy using Cle, 8) samples with probability at least 1 - 8, even if the reward of each trajectory perturbed by E(T) with [|=(T) S g(c).
would like to note that the requirement being g(e)-robust typically not restrictive. In fact, any tabular RL algorithm with sample complexity would be -robust with the same sample complexity, while many algorithms with linear function approximation are O D(e/poly(d, H))- robust [Jin et al., 2020b. Zanette et al., 2020] (again with the same sample complexity). We can further show that one can effortlessly convert any standard RL algorithms with sample complexity into O (1oC)-robust one by using the procedure described in Lemma B.3.
Remark (Trajectory vs. (s, a) preferences). So far, we presented the comparison oracle (Defini- tion 1) and the P2R (Algorithm 1) using trajectory rewards. This would require the RL algorithm using P2R to one that learns from pnce-per-trajecton scalar reward. To be compatible with stan- dard RL algorithms,
formally set and Algorithm 1. This would not change the theoretical results regarding the P2R reduction.
"incomplete trajectory" (s, a) in both Definition 1
Theoretical analysis of P2R We assume that (-)) is known and satisfies the following regularity assumption.
Assumption 2. (0) = 3; for x E HH o' (x) > 0.
Assumption 2 is common in bandits literature [Li et al., 2017] and is satisfied by the popular Bradley- Terry model, where a is the logistic function. It is further motivated by Lemma 2 and Lemma when is unknown has no gradient lower bounds, the optimal policy can be impossible identify. Lemma a is unknown, even if there are only two possible candidates, the optimal policy indeterminate.
5

---

Lemma 3. If (-) is not lower bounded, for instance when (x) 2/1 (1 + sign(()), the optinal
policy is indeterminate.
P2R enjoys the following theoretical guarantee when we choose co g(c)/2, 3 1. dR dimp(R, to) and m O
dog In(d /8)
Theorem 4. Suppose that Assumption and 2 hold, and that of is an g(e))robust RL algorithm with sample complexity C(c, (), By running a with the interface in Algorithm 1, we can learn
&
an c-optimal policy using 5) samples and a=g(e)² probability 26.
queries to the comparison oracle with
The full proof of Theorem 4 is deferred to Appendix B.3. The key idea of the analysis is to the fact that r' E B, and the condition in Line to show that the returned reward labels are approximate accurate, and to use properties of eluder dimension bound the number samples for which the comparison oracle is called.
Theorem 4 shows that P2R is provably efficient reduction: any standard RL algorithm A combined with P2R induces a provably efficient algorithm that learns an approximately optimal policy from preference feedback. The number of required interactions with the MDP environment is identical to that of the standard RL algorithm, and the query complexity only scales with the complexity of learning the reward function.
Comparison with other approaches A more straightforward reduction would be extensively querying the comparison oracle for every sample generated by the RL algorithm. While this direct reduction would not suffer from increased sample complexity, encounters two other drawbacks: (1) the oracle complexity, or the total workload for human evaluators, increases proportionally with the sample complexity of the RI. algorithm, which can be prohibitive; (2) the RL training would need to pause and wait for human feedback at every iteration, creating substantial scheduling overhead.
Another method to construct reward feedback to learn a full reward function directly before running the RL algorithm, in Ouyang et al. [2022]. However, without pre-existing high-quality offline datasets, collecting the samples for reward learning would require solving an exploration problem at least hard RL itself [Jin et al., 2020a], resulting in significant sample complexity overhead. In P2R, the exploration problem is solved by the RL algorithm using it.
Compared to the two alternative approaches, our reduction achieves the best of both worlds by avoiding sample complexity overhead with a query complexity that does not scale with the sample complexity.
3.2 Instantiations of P2R
When combined with existing sample complexity results, Theorem 4 directly implies concrete sample and query complexity bounds for preference- based RL in many settings, with no statistical and small computational overhead.
a) preferences We first consider the comparison that is based on the immediate reward of the current state-action pair. Here we give tabular MDPs and MDPs with low Gallman-Ellude dimension [Jin et al., 2021] as two examples.
Example (Tabular MDPs). Our first example is tabular MDPs whose state and action spaces are finite and small. In this case dæ Ö(SS) [A]). The UCB VI-BF algorithm, proposed by Azar et al. [2017], is model-based tabular RI. algorithm which uses upper-confidence bound value iteration with Bernstein-Freedmee
bonuses. UCBVI-BF has sample complexity C (c, = O (H3SS|AAAe and is O(e/ H) robust due to Lemma B.4.
Proposition 5. Algorithm with UCBVI-BF learns an e-optimal policy of a tabular MDP from pref- erence feedback using Ō ((ASsiia) episodes of interaction with the environment and Ö H² si AP queries to the comparison oracle. The algorithm is computationally efficient.
Example 2 (Low Bellman-elude dimension). Bellman-eluder dimension [Jin et al., 2021] is complexity measure for function approximation RL with Q-value function class F. It can be

---

shown that a large class of RL problems, including tabular MDPs. linear MDPs, reactive POMDPs and low Bellman rank problems. all have small Bellman-cluder dimension. Furthermore, Jin et al. [2021] designed an algorithm, named GOLE, which (i) first constructs a confidence set for the optimal Q-functions by including all the candidates with small temporal difference loss, (ii) then optimistically picks Q-estimate from the confidence set and executes its greedy policy, and (iii) repeats (i) and (ii) using the newly collected data. Assuming that F satisfies realizability and completeness property,
GOLF is g(e) O Vdni -robust with sample complexity C(e, 6) = dag In [F] where
dBE is the Bellman-eluder dimension of the problem. By applying Theorem 4, we immediately have the following result.
Proposition 6. Algorithm with GOLF [Jin al., 2021] learns an e-optimal policy of RL problems with Bellman- Bellman-Eluder dimension dgg in Ö( ddae [F episodes of interaction with the environment
2
and Ö dBg & RH2 queries to the comparison oracle.
When the reward function is trajectory- based, we can instantiate P2R with the OMLE algorithm [Liu al., 2022a] to solve any model-based RLHF of low generalized eluder dimension. In brief, OMLE is an optimism-based algorithm that maintains model confidence set. This set comprises model candidates that demonstrate high log-likelihood on previously collected data. And in each iteration, the algorithm chooses a model estimate optimistically and executes its greedy policy to collect new data.
Firaectory-basee preferences
Example (Low generalized eluder dimension). Generalized eluder dimension [Liu et al., 2022a] is complexity measure for function approximation RI. with a transition function class P. In Appendix D.1, we show that a simple adaptation of OMLE g(() = O Vaz )-robust with sample Hdd
complexity 6) Ö [f' Hoggl In [P|
where dp denotes the generalized eluder dimension of P. |Ilexpl is parameter in the OMLE algorithm, and dre dimg(R, e). Plugging it back into Theorem 4, we obtain the following result.
Proposition Algorithm with OMLE learns an e-optimal policy of RL problems with low gen- eralized eluder dimension in ① H' Mazgp ? (P] Hdg Hádp[papp] episodes of interaction with the environment and Ö dx d
queries to the comparison oracle.
Liu et al. [2022a] prove that wide range of model-based reinforcement learning problems have low generalized eluder dimension dp and only require a mild [TTxpl to run the OMLE algorithm. Examples of such problems include tabular MDPs, factored MDPs, observable POMDPs, and decodable POMDPs. For a formal definition of generalized eluder dimension and more details on the aforementioned bound and examples, we refer interested readers to Appendix D.I or Liu et al. [2022a]. Finally, we remark that it is possible to apply the P2R framework in other settings with different complexity measures, such as DEC [Foster et al., 2021] or GEC [Zhong et al., 2022], by making some minor modifications to the corresponding algorithms to ensure robustness.
3.3 Extension to K-wise comparison
In this subsection, we briefly discuss how our results can be extended to K-wise comparison assuming the following Plackett-Luce (PL) model [Luce, 1959, Plackett, 1975] of K item preferences.
Definition 4 (Plackett- model). The oracle takes in K trajectories TI...., and outputs explo-((fe-1m)))
permutation ó [K] + [K] with probability P(Ø) = II Sx explpr(r.
Note that when K = 2, the above PL model reduces pair-wise trajectory-type comparison oracle (Definition 1) with (xx) = exp(πær (xp((rar)((xp((1z)) (exp(1zz) + 1) which satisties Assumption with (xprexx(nn)f) The PL model satisfies the following useful property, which is a corollary of its internal consistency [Hunter, 2004].
].] C [K], the following pair-wise comparisons are mutually independent: (()(1)) > o(j))).... ((b(i)) > Φ(js)) where
Property 8 (Hunter [2004, p396)). For any disjoint sets (11,11,... [ix:
a permutation sampled from Pi.(TI,.... .T......Tk... Moreover, 1 (Φ(im) < ((im)) ~ (er(a( r(T ))), where a (xx) exp(πx) (expp)) + 1).
7

---

This property enables "batch querying" the preferences on [K/2] pairs of (T1, T2) in parallel, which returns [ independent pairwise comparisons outcomes. This would enable us reduce the number of queries by factor of ((()) for small K in both Algorithm and 3.
Theorem 9 (P2R with K-wise comparison). Suppose ot is an g(bustobust RL algorithm with sample complexity C(e, and assume the same conditions and the same choice of parameters as in Theorem
4. By running sf with the interface in Algorithm I, we can learn an e-optimal policy using C(e, 6)
dx
samples and O g=)( min K.m})
queries to the K K-wise comparison oracle with probability 1 - 28.
Theorem is a direct consequence of Theorem 4: If K 2 2m, we can obtain m independent comparisons between two trajectories by single query to the K-wise comparison oracle and therefore reduce the overall query complexity in Theorem by a factor of m; otherwise, we can get independent comparisons by making O(m/ K) queries to the K-wis- comparison oracle, which reduces the overall query complexity by factor of K.
However, the above parallelization benefits of using K-wise comparison might be an artifact of the PL model: seems improbable that the same human evaluator would independently rank [K/2] copies of item A and item B. It remains an interesting problem to develop K K-wise comparison models more suitable to RLHE.
4 RLHF From General Preferences
The utility-based approach imposes strong assumptions on human preferences. Not only is the matrix M[r, r'] in (1) assumed be exactly realizable by (r(())r((r)) but also o is assumed be known and have gradient lower bound. Moreover, the utility-based approach assumes that transitivity: if Pr[m > T2. 2 0.5, Pr(me > Tal 2 0.5, then Pr(m > Tal 2 0.5. However, experiments have shown that human preferences can be intransitive [Tversky, 1969]. These limitations of the utility-based approach motivates us to consider general preferences.
A general preference may not be realizable by utility model, so we cannot define the optimal policy in the usual sense. Instead, we follow Dudík et al. [2015] and consider an alternative solution concept, the von Neumann winner.
Definition 5. n² the von Neumann winner policy if (T",, the constant-sun sum game: max, ming E w' M [T, 7').
x*) ) is a symmetric Nash equilibrium of
The duality gap of the game is defined as
DGap(T1, T2)= max,, E M[T, [T] min, Ee [[,
We say that π is an c-approximate von Neumann winner if the duality gap of (л, x) is at most e. The von Neumann winner has been studied under the name of maximal lotteries in the context of social choice theory [Kreweras, 1965, Fishburn, 1984]. The von Neumann winner is a natural generalization of the optimal policy concept for non-utility based preferences. It is known that
Intuitively, the von Neumann winner x is a randomized policy that "beats" any other policy a' in the sense that E M (7, [7] 2 1/2;
If the utility-based preference model holds and the transitions are deterministic, the von Neumann winner is the optimal policy;
The von Neumann winner is the only solution concept that satisfies population--onniitennyy and compossiton--coniitteng in social choice theory [Brandl et al., 2016).
Finding the von Neumann winner seems prima facie quite different from standard RL tasks. However, in this section we will show how finding the von Neumann winner can be reduced to finding the restricted Nash equilibrium in type of Markov games. For preferences based on the final state, we can further reduce the problem to RL in adversarial MDP.
4.1 A reduction to Markov games
Factorized and independent Markov games (FI-MG). Consider two-player zero-sum Markov games with state space S = s(1)) x S(2,, action space (1) and (2) for each player respectively,
8

---

transition kernel he and reward function r. We say the Markov game is factorized and independent if the transition kernel is factorized:
(2) (s 8/: 0n. = Ps 8%2 0h x Ph 5/ 0% (1) (()
(1)
(1)
where (5) (1) (2) S6+1 (5 ( (
( or (ah (2)) E A x A
The above definition implies that the Markov game can be partitioned into two MDPs, where the transition dynamics are controlled separately by each player, and are completely independent of each other. The only source of correlation between the two MDPs arises from the reward function, which is permitted to depend on the joint trajectory from both MDPs. Building on the above factorization
structure, define partial trajectory TEA == (s} aa ,..... (()) that consists of states of the i-th MDP factor and actions of the i-th player. Furthermore, we define a restricted policy class II; that contains all policies that map partial trajectory a distribution in A., i.e.
11, := TH )eeen) Th E ((S()) x A,)aa1 x s(i) 7 AA.) for E [2]. And the goal is to learn a restricted Nash equilibrium (u²,**) E 11, x II2 such that μr* E arg max Er (r(n) r]] and V' E arg min
7').
Finding von Neumann winner via learning restricted Nash. We claim that finding an approximate von Neumann winner can be reduced to learning an approximate restricted Nash equilibrium in FI-MG. The reduction is straightforward: we simply create a Markov game that consists of two independent copies of the original MDP and control the dynamics in the i-th copy by the i-th player's actions. Such construction is clearly factorized and independent. Moreover, the restricted policy class II, is equivalent to the universal policy class in the original MDP. We further define the reward function as r(T, T') = [T, r'] where M is the general preference function. By definition 5, we immediately obtain the following equivalence relation.
Proposition 10. If (p" ,V") is a restricted Nash equilibrium of the above FI-MG, then both μ² and 1/ are von Neumann winner in the original problem.
The problem we are faced with now is how to learn restricted Nash equilibria in FI-MG. In the following sections, we present two approaches that leverage existing RI. algorithms to solve this problem: (i) when the preference function depends solely on the final states of the two input trajectories, each player can independently execute adversarial MDP algorithm; (ii) for general preference functions, a straightforward adaptation of the OMLE algorithm is sufficient under certain eluder-type conditions.
4.2 Learning from mhal-state-based preferences via adversarial MDPs
In this section, we consider a special case where the preference depends solely on the final states of the two input trajectories, i.c., M T') = (SH sty). Given the previous equivalence relation between von Neumann winner and restricted Nash in FI-MG, one natural idea is to apply no-regret learning algorithms, as it is well-known that running two copies of no-regret online learning algorithms against each other can be used to compute Nash equilibria in zero-sum normal-form games. Since this paper focuses on sequential decision making, we need no-regret learning algorithms for adversarial MDPs, which we define below.
Adversarial MDPs. In the adversarial MDP problem, the algorithm interacts with series of MDPs with the same unknown transition but adversarially chosen rewards for each episode. Formally, there exists an unknown groundtruth transition function P = (1", h- At the beginning of the k-th episode, the algorithm chooses a policy x² and then the adversary picks reward function ,* {rr 1h-1- After that, the algorithm observes trajectory n = (sf, aft ,f...., ai vir) sampled from executing policy x in the MDP parameterized by P and ,² where Eiy, sy at] [a]==((as (sf. at) We define the regret of an adversarial MDP algorithm of to be the gap between the algorithm's expected payoff and the best payoff achievable by the best fixed Markov policy:
!f Regretx x (of) max, Ellaarkvv Σx=1 ES,T Eh=1
K
(5 an)] E E
K
E rf an)
Now we explain how to learn a von Neumann winner via running adversarial MDP algorithms. We simply create two copies of the original MDP and instantiate two adversarial MDP algorithms of and

---

S to control each of them separately. To execute of and 222 we need to provide reward feedback to (2(2) the final states df and .f2 observe in the k-th HH )) into of and 1 -- into 2a as their reward at step H H, respectively. And all other steps have zero reward feedback. The formal pseudocode provided in Algorithm 4 (Appendix E). The following theorem states that as long as the invoked adversarial
them in each k-th episode. Denote by sH (L) and 8H
episode. We will feed vy ~ Ber(M(ss k.(1) k.(2))
MDP algorithm has sublinear regret, the above scheme learns an approximate von Neumann winner in sample-efficient manner.
Theorem 11. Suppose Regretg x (s/) S BK1- with probability at least 1 - 6 for some e (0, 1). Then Algorithm 4 with K (4 outputs an e-approximate von Neumann winner with probability at least 1 26.
In order to demonstrate the applicability of Theorem 11, we offer two examples where sublinear regret can be achieved in adversarial MDPs via computationally efficient algorithms. The first one is adversarial tabular MDPs where the number of states and actions are finite, i.e., [S), S +oo.
Example (adversarial tabular MDPs). Jin et al. [2019] proposed
algorithm s with Regret x ( ( S O /|S Plugging it into Theorem 11 leads to K O (2(15||AA11 (|A))))//?)
sample complexity and query complexity for learning e-approximate von Neumann winner.
The second example is adversarial linear MDPs where the number of states and actions can be infinitely large while the transition and reward functions admit special linear structure. See Sherman et al. [2023] for the precise formulation of the adversarial linear MDP problem.
Example 5 (adversarial linear MDPs). Sherman et al. [2023] proposed an algorithm d with Regret x (af) I OddH² K for online learning in adversarial linear MDPs. Combining it with Theorem 11 leads to K = O H///c7) sample complexity and query complexity for learning e-approximate restricted Nash equilibria.
4.3 Learning from trajectory- preferences via OMLE -eEiLEEbuuilbruum
In this section, we consider the more general case where the preference [[r, r') is allowed to depend arbitrarily on the two input trajectories. Similar to the utility-based setting, we assume that the learner is provided with preference class M ((S x A)" (S x A)" " [0. 1]) and transition function class P a priori. which contains the groundtruth preference and transition we are interacting with. Previously, we have established the reduction from learning the Neumann winner learning restricted Nash in FI-MG. In addition, learning restricted Nash in FI-MG is in fact a special case of learning Nash equilibrium in partially observable Markov games (POMGs). As result, we can directly adapt the existing OMLE algorithm for learning Nash in POMGs [Liu et al., 2022b) to our setting, with only minor modifications required learn the von Neumann winner. We defer the algorithmic details for this approach (Algorithm 5) to Appendix F, and present only the theoretical guarantee here.
Theorem 12. Suppose Assumption holds. There exist absolute constant e and og such that for any (T, E N x (0, 1] we choose 8M ci ln(M[ and Bp cı In[I in Algorithm 5, then with probability at least - 6, the duality gap of the output policy of Algorithm 5 is at most
4E(dp, I, c23p, [eexp))
ddM3M
ea
where dm = dimma (M,, 1/T).
T
T
It has been proven that a wide range of RL problems admit a regret formulation of & Ö( d/ 3/ (T) with mild dr and [[es [Liu et al., 2022a]. These problems include, but are limited to, tabular MDPs, factored MDPs, linear kernel MDPs, observable POMDPs, and decodable POMDPs. For more details, please refer Appendix D.I or Liu et al. [2022a]. For problems that satisfy (d Texp (T), Theorem D.I implies a sample complexity of
δ dr In [P] dm In [M]
2
c2
The sample complexity for specific tractable problems can be derived by plugging their precise formulation of & (provided in Appendix D.1) into the above bound.
'Sherman et al. [2023] requires the adversarial reward function to be linear in the feature mapping of linear MDPs. In Appendix E, we show the reward signal we constructed in Algorithm 4 satisties such requirement.
10

---

Acknowledgement
This work was partial supported by National Science Foundation Grant NSF-IIS-2107304 and Office of Naval Research Grant N00014-22-1-2253.
References
Josh Abramson, Arun Ahuja, Federico Carnevale, Petko Georgiev, Alex Goldin, Alden Hung, Jessica Landon, Jirka Lhotka, Timothy Lillicrap, Alistair Muldal, et al. Improving multimodal interactive agents with reinforcement learning from human feedback. arXiv preprint arXiv:2211.11600 2022.
Nir Ailon, Zohar Karnin, and Thorsten Joachims. Reducing dueling bandits to cardinal bandits. In International Conference on Machine Learning, pages 856 864. PMLR, 2014.
Riku Arakawa, Sosuke Kobayashi, Yuya Unno, Yuta Tsuboi, and Shin-ichi Maeda. Dqn- tamer: Human-in-the-loop reinforcement learning with intractable feedback. arXiv preprint arXiv: 11111800..1114.... 2018.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for rein- forcement learning. In International Conference Machine Learning, pages 263-272. PMLR,
2017.
Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al. Training helpful and harmless assistant with reinforcement learning from human feedback. arXiv preprint arXiv:2204.0586. 2022.
Viktor Bengs, Róbert Busa-Fekete, Adil El Mesaoudi-Part Paul,, and Eyke Hüllermeier. Preference-based online learning with dueling bandits: A survey, The Journal of Machine Learning Research, 22(1): 278-385, 2021.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Dębiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al. Dota 2 with large scale deep reinforcement learning. arviv preprint arXiv:1912.06688 2019.
Florian Brandl, Felix Brandt, and Hans Georg Seedig. Consistent probabilistic social choice. Econo- metrica, 84(5):1839-1885 2016.
Róbert Busa-Fekete, Balázs Szörényi, Paul Weng, Weiwei Cheng, and Eyke Hüllermeier. Preference- based reinforcement learning: evolutionary direct policy search using preference-based racing algorithm. Machine learning, 97:327-351 2014.
Xiaoyu Chen, Han Zhong, Zhuoran Yang. Zhaoran Wang, and Liwei Wang. Human-in-the-lon Provably efficient preference-basee reinforcement learning with general function approximation. In International Conference on Machine Learning, pages 3773-3793. PMLR, 2022.
Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. Advances in neural information processing systems, 30, 2017.
Zihan Ding, Yuanpei Chen, Allen Z. Ren, Shixiang Shane Gu, Hao Dong, and Chi Jin. Learning universal human prior for dexterous manipulation from human preference. arXiv preprint N.Xiv:3304004600 2023.
Miroslav Dudík, Katja Hofmann, Robert Schapire, Aleksandrs Slivkins, and Masrour Zoghi. Contextual dueling bandits. In Conference on Learning Theory, pages 563-587. PMLR, 2015.
Chelsea Finn, Sergey Levine, and Pieter Abbeel. Guided cost learning: Deep inverse optimal control via policy optimization. In International conference on machine learning, pages 49-58. PMLR, 2016.
Peter C Fishburn. Probabilistic social choice based on simple voting comparisons. The Review of Economic Studies, (1(4):683-622 1984.

---

Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13487, 2021.
David R Hunter. Mm algorithms for generalized bradley-terry models. The annals of statistics, 32(1): 384-406, 2004.
Borja Ibarz, Jan Leike, Tobias Pohlen, Geoffrey Irving, Shane Legg, and Dario Amodei. Reward learning from human preferences and demonstrations in atari. Advances in neural information processing systems, 31, 2018.
Ashesh Jain, Brian Wojcik, Thorsten Joachims, and Ashutosh Saxena. Learning trajectory preferences for manipulators via iterative improvement. Advances in neural information processing systems, 26, 2013.
Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, and Tiancheng Yu. Learning adversarial mdps with bandit feedback and unknown transition. arXiv preprint arXiv:1912.01199 2019.
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In International Conference on Machine Learning, pages 4870-4879.
PMLR, 2020a.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143. PMLR, 2020b.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of problems, and sample-efficient algorithms. Advances in neural information processing systems, 34:13406-13418 2021.
Germain Kreweras. Aggregation of preference orderings. In Mathematics and Social Sciences I: Proceedings of the seminars of Menthon-Saiie -ain--aaaianddd France (1-27 July 1960) and of Gösing, Austria (3-27 July 1962), pages 73-79, 1965.
Kimin Lee, Hao Liu, Moonkyung Ryu, Olivia Watkins, Yuqing Du, Craig Boutilier, Pieter Abbeel, Mohammad Ghavamzadeh, and Shixiang Shane Gu. Aligning text-to-image models using human feedback. arXiv preprint 2321:2302..1192,, 2023.
Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contextual bandits. In International Conference on Machine Learning, pages 2071-2080. PMLR, 2017.
Qinghua Liu, Praneeth Netrapalli, Csaba Szepesvari, and Chi Jin. Optimistic mle-a generic model-based algorithm for partially observable sequential decision making. arXiv preprint arXiv:2209. 14997, 2022a.
Qinghua Liu, Csaba Szepesvári, and Chi Jin. Sample-efficient reinforcement learning of partially observable markov games. arXiv preprint 1:Xiv:2206.01315, 2022b.
Robert D Luce. Individual choice behavior: A theoretical analysis. John Willey and sons, 1959.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint 13X15:13/ 2013.
Ellen Novoseller, Yibing Wei, Yanan Sui, Yisong Yue, and Joel Burdick. Dueling posterior sampling for preference-based reinforcement learning. In Conference Uncertainty in Artificial Intelligence, pages 1029-1038. PMLR, 2020.
Long Ouyang. Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35: 27730 27744, 2022.
Aldo Pacchiano, Aadirupa Saha, and Jonathan Lee. Dueling rl: reinforcement learning with trajectory preferences. arXiv preprint 2rX1v:2111.04850, 2021.
12

---

Bruno L Pereira, Alberto Ueda, Gustavo Penha, Rodrygo LT Santos, and Nivio Ziviani. Online learning to rank for sequential music recommendation. In Proceedings of the 13th ACM Conference on Recommender Systems, pages 237-245, 2019.
Robin L Plackett. The analysis of permutations. Journal of the Royal Statistical Society Series C: Applied Statisties, 24(2): 19:-::9922222 1975.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, 26, 2013.
Aadirupa Saha and Aditya Gopalan. Pac battling bandits in the plackett- model. In Algorithmic Learning Theory, pages 700-737. PMLR, 2019.
Uri Sherman, Tomer Koren, and Yishay Mansour. Improved regret for efficient online reinforcement learning with linear function approximation. arXiv preprint arXiv:2.301. 130877 2023.
David Silver, Julian Schritwiessr. Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 350(7676)3354-4 355,33 2017.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model- -aaeed control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 5026-5033. IEEE, 2012. doi: 10.1 1..11099RRS.200 200.ER000...02...6660000 2.6386109.
Amos Tversky. Intransitivity of preferences. Psychological review, 76(1):31, 1969.
Oriol Vinyals, Igor Babuschkin, Wojeiech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung. David Choi, Richard Powell, Timo Ewalds, Petko Georgiev, al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782):350-333 -544000-5,,-- 2019.
Garrett Warnell, Nicholas Waytowich, Vernon Lawhern, and Peter Stone. Deep tamer: Interactive agent shaping in high- -igeeniienii state spaces. Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
Yichong Xu, Ruosong Wang, Lin Yang, Aarti Singh, and Artur Dubrawski. Preference- reinforcement learning with finite-time guarantees. Advances in Neural Information Processing Systems, 33:18784-1877 18794, 2020.
Yisong Yue and Thorsten Joachims. Interactively optimizing information retrieval systems dueling bandits problem. In Proceedings of the 26th Annual International Conference on Machine Learning, pages 1201-1208, 2009.
Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed dueling bandits problem. Journal of Computer and System Sciences, 1835)155 2012.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning. pages 10978-10989. PMLR, 2020.
Wenhao Zhan, Masatoshi Uehara, Nathan Kallus, Jason Lee, and Wen Sun. Provable offline reinforcement learning with human feedback. arXiv preprint arXiv:2305. 14816, 2023a.
Wenhao Zhan, Masatoshi Uehara, Wen Sun, and Jason D Lee. How to query human feedback efficiently rI? arXiv preprint arXiv:2305. 18505, 2023b.
Han Zhong, Wei Xiong, Sirui Zheng, Liwei Wang, Zhaoran Wang, Zhuoran Yang, and Tong Zhang. A posterior sampling framework for interactive decision making. arXiv preprint arXiv:2211.0096 2022.
Banghua Zhu, Jiantao Jiao, and Michael I Jordan. Principled reinforcement learning with human feedback from pairwise or k-wise comparisons. arXiv preprint arXiv:2301.11277 2023.
Daniel M Ziegler, Nisan Stiennon, Jeffrey Wu, Tom B Brown, Alec Radford, Dario Amodei, Paul Christiano, and Geoffrey Irving. Fine-tuning language models from human preferences. arXiv preprint ar 1909 08593, 2019.
13

---

Masrour Zoghi, Shimon Whiteson, Remi Munos, and Maarten Rijke. Relative upper confidence bound for the k-armed dueling bandit problem. In International conference on machine learning. pages 10-18. PMLR, 2014.
14

---

A Proofs of Impossibility Results
Proof of Lemma 2. Consider two link functions 01 (1) = 1+exp(-z) and
(2 aa + a2( az) || > 03):
where 01 1, 02 -0.444 0g 0.3 Consider an MDP with H and initial state so. Suppose that there are three terminal states 81, 82, 83, where we observe that the trajectory preferences only depend on the terminal state in the following way:
Pr[s1 52) 0.7, Pr[s > sal = 0.8, Pr(s: > 5y] 0.903.
This can be explained by both 01 with (1) {so 0, 81 : 0.847, 82 0, -1.386), and 02 with (2) { 0, s1 0.2, $2 S3 -
Suppose that state so has two actions and b, which leads to distributions {0.39 81, 0.61 83} and (1 : }2} respectively. Under y.(1) and r(2), the optimal action would be a and b respectively. Therefore without knowledge of the link function, it is impossible to identify the optimal policy even
with perfect knowledge of the transition and comparison probabilities.
Proof of Lemma 3. Similarly, consider an MDP with H = and initial state 8o. Suppose that there three terminal states $1, $2, 83, where observe that
Pr[si > s2 Pr(s2 sy] Pr(s $3] =1
Meanwhile the state has two actions and b, leading distributions {0.5 81, 0.5 83} and {1 82) respectively. In this case, both (1) {so 0, 81 0.5, 0, -1} and (2) (so 0, 1, 82 0,88 -0.5) fits the comparison results perfectly. However under (1) the optimal action is b while under (?)), the optimal action is a.
B Proofs for P2R
B.1 Properties of eluder dimension
We begin by proving two properties of the eluder dimension of R.
Lemma B.1. Consider Rlinear (0Tx), where X C Rd. ||0||2 S n. Then there exists absolute
constant C such that
dimg Riinear e) C(dd 1) 1+ 1+ 1
7 H
+1.
Proof. Note that
0 x c= [8 [xr 1].
Therefore Rineer can be seen as (d+ + 1)-dimensional linear function class with parameter norm ||;0, elll2 Sy H. The statement then direct corollary of Russo and Van Roy [2013, Proposition 6].
Lemma B.2. For a function class R with domain X and range [0, f)r < 1,
function dimg E) S ((H,eim(RRee2)))
Proof. Suppose that there exists sequence
(ri, Cs. Ri, Vi hee(m),
where r. R. G [-H,, o; X' and ys IR, such that for all i [m]
(r((2:) + vil N e, Σ
(l((a)) + 1, < e
jeN
15

---

By definition, dimg (R, c) is the largest m so that such a sequence exists. By the pigeon- hole principle, there exists a subset S [m] of size at least k TH/eal and [0. col such
that Vi E I, E [e, so]- Denote the subsequence indexed by / as {r C, 4/ D: = V/4 - č. Now consider the sequence (r/, 24, De NEjM- By definition Vi E [k]
Define
1r((24) Vel 2 co.
follows that
Σ Ir((z,) -0,1 7 - --rr((,)) (c)
+2 E (e-C) c/) (1)(2,) (1/ --))
+E(
(c d,)² jei
jei
jzi
jei
=²² + 2V + kc
1/3
We can choose Eg :
so that eo S </(4AK)).
Then we can guarantee
I6m
(x))))) Tsl 2 0.5c,
Σ (r((x,))
T. s 262.
j<i
By Jin et al. [2021, Proposition 43],
20a (0.5c)3
k: <
1
In other words,
m
S 9dimg (R, 0.5c),
[H/ccl
which gives
216H
dimg (R. c) S dimgg(R, (R,
B.2 Properties related to robustness
Lemma B.3 (Robustness perturbation). Any RL algorithm af with sample complexity C(e, can be converted to an algorithm sf that C(c,5) -robust with sample complexity C(e, 8/3).
Proof. Consider the following modification of s/: instead of using reward r directly, we project to +2H and -2H unbiasedly; that is, the algorithm receives the binarized rewards
b(r) 2H
2H
4H'
4H
By the definition of sample complexity, when using samples of b(r"), a outputs policy mo for y* that is c-optimal with probability by running s on b(r*) by "1, , -K. Now suppose that for Tk, the reward label is perturbed from b(r"(n (Tx)) to b(r()) with In] - r* (Tx)l s d' = (C(c, 8)) denote the output policy of a by n². can be shown that
8 in == C(e, 5) episodes. Denote the trajectories generated
In ( (b(r"(T))) =211 - 2H1 (((2) = 2H
) In 1+ -
Therefore the total density ratio
(( (n)), ... b(r (Tx) ((r b(r1), b(rk)) =
(Tk))== =
Ke' H
sup AE (2H,
K in 1+
$1.
It follows that the density ratio between and A is also bounded by Therefore the probability that f is not e-optimal is at most 36. Rescaling proves the lemma.
Lemma B.4. Any tabular RI. algorithm of with sample complexity Cle, 8) is e/(AH) robust with sample complexity C(e/2,8).
16

---

Proof. Suppose that of is rum on perturbed rewards, where rewards for trajectory is changed by E(T). By definition, using C(e/2. 6) samples and with probability
outputs an e/2-optimal policy & with respect to the perturbed reward function r + where ||e||>c S c/4H. Denote the value function of policy æ with respect to reward r by Var Further denote the optimal value function with respect to by x². It holds that for any policy
V - Vater S Se/4.
Therefore
v Var < 10 V
c/2 c/2
In other words से is indeed an c-optimal policy with respect the unperturbed rewards
B.3 Proof of Theorem 4
Lemma B.5. With m = + [I((1/8') nder2 ). for each such that the comparison oracle is queried, with
probability 8',
(F(T) (ro))
Proof. Suppose that the comparison oracle queried for т and the average outcome is ō. By Hoeffding bound, with probability 1 8', 8',
j - ofr r (T0)) S In(2/8))
Since f(r) lo(x) 5/.
(a(f(T)) - o. - - 0 In(2/8")
m
follows that
(a(f(r)) - -(r - (+0)) s $21 (n((8/8)
By Assumption
2 (In(2/8))
[f()) - ( (r)
Sc.
Lemma B.6. Set e @(dluid/o) and B 3 With probability 1 5, the number of samples which the comparison oracle is queried is most dimg (R,ng(R,eo (R,
Proof. Define (*( == r>)+))>>>>>>>>>) (TO) F(r) r(r) r(5o).
When the comparison oracle is queried, max,,r'B, ((r(T) r( (())))) -r()) > 26g which
means that either [F(r) F (r) 6n or (T( F" (r) > cn- Suppose that there are K trajectories which require querying comparison oracle. Suppose that the dataset composed of
D = ((),)),
Tk))
and Fi,..., FK R are the functions that satisfy (Fe(T)) - 7* (Tx)l ep-
We now verify that
(f1, T2, -2, FK, TK) is cluder sequence (with respect to function class R).
The confidence set condition implies
Σ (Fi(Tx) - Px)2 <
17

---

r.p With probability 1 1 6, 44 S K 2d. fx - - (Tx)] -
50 (by Lemma B.5). Then for any S h
4vd
(T) - (Ta))
-
(Fi(T)) - - +
(TT(TT) - fk + (((x)) - F (Tx)) (Fx - (Tx))
k
8 + 2 KB
+ K
S <
4
4vd
as long as K - 2d. In other words, with probability 1 - 8, (F1, Tı, F2, T2. ... .FKaad TRAnd) is an
eluder sequence, which by Definition 2 cannot have length more than == dimm(RRee co). It follows that K S (R, co).
Lemma B.7. With probability 1 - 6, r* E B, throughout the execution of Algoritium 1.
Proof. By Lemma B.5 and Lemma B.6, with probability 1 1- 6, at every step
Σ
(r* ( -A)² sd
v 6 B
4vd
4
(Ar))D
Lemma B.8. With probability for each T in Line of Algorithm 1, the returned reward satisfies
| (r- 260-
Proof. We already know that this is true for such that the comparison oracle is queried. However, it is not queried, then
max (r(r) r(ro) (T' (T(o) 2c0- Er"
Since r* Br (by Lemma B.7), this immediately implies (r"(T) r* (T()) S 2cc-
Proof of Theorem 4. Choose co := 9()) - and O dx 0z l
"aa""
By Lemma B.8 (rescaling 6), with probability 1 8, the reward returned by the reward interface is g(c)-close to F* := r* (To) throughout the execution of the algorithm. By the definition of 8, the policy returned by a/ is c-optimal for i* which
sample complexity, with probability implies that it is also e-optiall for r* The number of samples (episodes) is bounded by C(e, 6). Finally by Lemma B.6, the number of queries to the comparison oracle is at most
dimp((R,o)) m S
(2()2
C P-OMLE: Improved query complexity via white-box modification
While the P2R interface provides a clean and effortless recipe for modifying standard RL algorithms to work with preference feedback, it incurs a large query cost to the comparison oracle, e.g., cubic dependence on dz in Example We believe that this disadvantage is caused by the black-box nature of P2R, and that better query complexities can be achieved by modifying standard RL algorithms in a white-box manner and specialized analysis. In this section, we take OMLE [Liu et al., 2022a] as example and introduce standalone adaptation to trajectory preference feedback with improved query complexity. We expect other optimism- based algorithms (e.g.. UCBVI-BF and GOLF) can be modified in similar white-box manner achieve better query complexity.
The details of the Preference-bart based OMLE algorithm (P-OMLE) is provided in Algorithm 2. Com- pared to OMLE with reward feedback (Algorithm 3), the only difference is that now the reward confidence set is computed using preference feedback directly using log-likelihood. Denote by V the expected cumulative reward the leaner will receive she follows policy æ in model (p, r). In the t-th iteration, the algorithm follows the following steps:
18

---

Optimistic planning: Find the policy-modee model pair (I, r) that maximizes the value function V
T.p
Data collection: Construct exploration policy set eexp and collect trajectories by
running all policies in (x²)(
Confidence set update: Update the confidence using the updated log-likelihood:
Drwa)= = Σ
(no(r(t)-<(7'))))) L(p, Derans) ==
Σ
In In
(
Algorithm 2 Preference-based OMLE (P-OMLE)
1: B + R x P
2: execute an arbitrary policy collect trajectory 70
3: for prr== 1,=1,...
T' 1,..., do arg max=, (r.))e Vr - r[(7]]
4: compute "=',r".p")
5: execute n² to collect a trajectory
6: invoke comparison oracle on and 7 to get add (r, r" v) into Dend
7: for each π Ilexp (=') do
8: execute to collect trajectory т, add (TT, into Derans
9: update
B+
((r.p) E R : C(r, Dava)
max C(r', Drva) AR PER
and L(p, Derana)
max Llp', Derans) -3pp PEP
We have the follwoing guarantee for Algorithm 2.
Theorem C.1. Suppose Assumption, I, 2 and 3 hold. There exists an absolute constant C1 02 > 0 such that for any (T, 8) e N (0, 1] if we choose 3R ci [n((R/T88) and 3p c1 In([ in Algorithm 2, then with probability at least 1 - ò, we have that for all E [T].
T Σvv-v" 2, (ex O(Ha- VdRT3R
1=1
where dx dimg RR./vT).
For problems that satisfy & = Ō( /dp 3p [leppp"2 T), Theorem C. implies both the sample complexity and the query complexity for learning e-optimal policy is upper bounded by:
H 12 leepp 2n |P|
Hdd In |n|
+
a²c²
Compared to the result derived through the P2R interface (Example 3), the sample complexity here basically the same while the query complexity has improved dependence on dæ (from cubic to linear). Nonetheless, the query complexity here additionally depends on the complexity of learning the transition model, which is not the case in Example 3.
C.1 Proofs for P-OMLE
The proof of Theorem C.1 largely follows from that Theorem D.I. We first introduce several useful notations. Denote by Be B, the preference, transition confidence set in the f-th iteration, which satisfy B' = B% x B- Denote the groundtruth transition and preference by p* and M*. Denote the trajectories generated when running Algorithm by - r?.....,?"
Similar to Lemma D.3, we have that the confidence set satisfies the following properties.
Lemma C.2. There exists absolute constant O2 such that under the same condition as Theorem C.I, we have that with probability at least 1 8: for all E [T]
'The exploration policy set problem-dependen. dependent and be simply (x') ) for many settings.
19

---

pr" E B
E maxpEB; drv d .pp))) - E(dp,T, 028p 1x
Proof. For the first two statements, see the proof of Theorem 3.2 in Liu et al. [2022a]. For the third bullet point, see Liu et al. [2022a, Proposition B.2], which implies that
LHS S O(3r (n( - ((3).
Proof of Theorem C.I. By using the first relation Lemma C.2 and the definition (æ', :p)).
T
V
1=1
[Vippp .p
-r' -1'(7)+++(( +r"(70) - V/
[=1
[V pt (7 + +rr(( +r²) 1/ pr
T
T Σ
VTL
V pt - (7 + (+²) - va g.
1=1
We can control the first term by the second inequality in Lemma lem:omle-pref
T dTv (PP ppg') S 2HE(dd,TTcc2fp) (mxpl))
LIVE
V pp
2
For the second term, by Azuma- Hoeffding inequality and by combining the second inequality in Lemma C.2 with the regret guarantee for eluder dimension,
1V - (77)) + +r V. [..pp
- (1
<O(Ha + 3RR
D OMLE with Perturbed Reward
D.1 Algorithm details and theoretical guarantees
In this section, modify the optimistic MLE (OMLE) algorithm [Liu et al., 2022a] to deal with unknown reward functions. The adapted algorithm can then be used with Algorithm 1 as described in Example OMLE is model-based algorithm that requires model class P in addition to the reward class R. On a high level, OMLE maintains a joint confidence set B in R. x P. In the I-th iteration, the algorithm follows the following steps:
Optimistic planning: Find the policy-model pair (T, r,p) that maximizes the value function ya rp which is the expected cumulative reward the leaner will reseive if she follows policy æ in a model with transition p and reward
20

---

Data collection: Construct an exploration policy set Hexx $ and collect trajectories by rumning all policies in oxx (T²);
Confidence set update: Update the confidence set using the updated log-likelihood.
The main modification make is the confidence of r, since the original OMLE algorithm assumes
that r is known. The pseudocode of our adapted OMLE algorithm is provided in Algorithm 3.
Algorithm Optimistic MLE with <'Perturbed Reward Feedback
1: B <- R x P
2: Execute arbitrary policy to collect trajectory 70
3: for t ,,,..,,77 do
4: Compute (=',r"pp') = arg max,, (n Vi-p
5: Execute x' collect trajectory т, receive reward f, add(r, r) into Drud
6: for each (x') do
7: Execute æ to collect trajectory T, add (TT, 7) into Dirans
8: Update
B++1 + {(r,p) xxP:
max (r(T) - f/5c (res)
and L(p, Derana)
> max L(y/, Derans) (p)) VEP
In Line 8, the log-likelihood function is defined
[pp Derane) =
Σ (D,
In
where P (r) denotes the probability of observing trajectory in model with transition function under policy æ. Other algorithmic parameters T and 3p are chosen in the statement of Theorem D.1.
To obtain sample efficiency guarantees for OMLE, the following assumption is needed. Assumption 3 (Generalized eluder-type condition). There exists real number dp E and function such that: for any (T", E N x R+, transitions {p" heepy and policies { hee(T) we have
T
Vt E IT. Σ Σ
PF SA
Σ div p', PT) S Eldp, Hexp)).
T=1 x=lxpplep(FT)
Here ppg is the distribution of trajectories under model and policy H, while I Texpl =
max, [T) is the largest possible number of exploration policies.
Assumption 3 shares similar intuition with the pigeon-hole principle and the elliptical potential lemma, which play important roles the analysis of tabular MDP and linear bandits respectively. In particular, the function measures the worst-case growth rate of the cumulative error and is the central quantity characterizing the hardness the problem. Liu et al. [2022a] prove that a wide range of RI. problems satisfy Assumption with moderate dp, [Texpl and & = Ö ( A TTxp K), including tabular MDPss factored MDPs, observable POMDPs and decodable POMDPs (see Liu et al. [2022a] for more details).
Theorem D.I. Suppose Assumption I and 3 hold. There exists absolute constant C such that for any (T' 8) E N x (o, 1), if we choose 3p = [n([P]]leexp]T//0 in Algorithm 3, then with probability least 8. we have that for all [T].
T
V+* |= 22HEdd,,T.co.. [11xx
T "TVdR + mi) + Iww)) + O(HVTmO-
+
min w>O
where dR dimg (R,
'The exploration policy set problem dependent and be simply (x') ) for many settings.
21

---

Theorem D.1 implies sample complexity of For problems that satisfy & = Ō dp I eexp T).
In P HdR (dRRllexpl ō ( H12dpp Hexp
62
for learning an (cc)ooiiimal policy, if we have w = c and c' = c/vdR. The sample complexity for specific tractable problems can be found in Appendix D.2.
D.2 Examples satisfying generalized eluder-type condition
In this section, we present several canonical examples that satisfy the generalized eluder-type condition with { = O dp Hexp (T). More examples can be found in Liu et al. [2022a].
Example 6 (Finite-precision Factored MDPs). In factored MDPs, each state consists of factors denoted by (s[1), s(ml) E x The transition structure also factored as
( an)
II
I (sh+ [i] s% [pa,],
==1
where pa, S [m]] is the parent set of i. The reward function is similarly factored:
(8))) = Σ (+(o))
Define B = ::=>mm1 (xpp, Factored MDPs satisfy (with eepll and dp m2 m2 Boly
E(dp, T, A, [Txp)) S dp + Ao'poly
Moreover In |P] < mbAB, In |R| < mb)2), where b is the number of bits needed to specify each entry of P(s++1|s]ssl an) or Th (s) 6. Therefore Theorem D.I implies a sample complexity of
(mm²
(mmn |AASB
bm2 b
(oly(H) H
2
a²
To proceed, we define partially observable Markov decision process (POMDPs).
Definition In a POMDP, states are hidden from the learner and only observations emitted by states can be observed. Formally, at each step h [H... the learner observes oh OO(( sw)
where 84, is the current state and On(- 8h) A is the observation distribution conditioning
on the current state being Sh. Then the learner takes action an and the environment transitions to Sh+1 ~ PA(-1 Sky an).
Liu et al. [2022a] prove that the following subclasses of POMDPs satisfy Assumption 3 with moderate dp and Ie Example 7 (a-observable POMDPs). We say POMDP is a-observable if for every μ. 1. E As. min Eg (: s)] Eswne (. (-1 s)]ll1 a -
Intuitively, the above relation implies that different state distributions will induce different observation distributions, and the parameter a measures the amount information preserved after mapping states to observations. It is proved that a-observable POMDPs satisfy Condition with Iexp (T) = {m) and dp = (S, a, 1, H) [Liu et al., 2022a).
For simplicity of notations, let u(h) max(1, 1, m + 1).
Example 8 (m-step decodable POMDPs). We say POMDP is m-step decodable if there exists a set of decoder functions ( heeH such that for every h E [H]. 84 = dh ((o, a) u()):-11, on). In other words, the current state can be uniquely identified from the most recent m--stp observations and actions. It is proved that a-ooservable POMDPs satisfy Condition 3 with [Texpl n and dp poly A H)) where L max, rank(P,) denotes the rank of the transition matrices (IP he S SAXS [Liu et al., 2022a].
'We can deal with continuous model classes if we use the bracketing number instead of cardinatliy in Theorem D.I
22

---

D.3 Proof of Theorem D.1
We first define some useful notations. Denote by D rudd D Drrans the reward, transition dataset the end of the f-th iteration. We further denote
3 - fr R:
max (r,
- =c
Bp - {pE:: C(D, Dirans)
max L(p', Dirons) - -Bp]. PEP
By the definition of B have that B' BR Byp. Denote by (r","t) the trajectory-reward pair added into Drud in the (-th iteration of Algorithm 3.
By the definition of Bi and the fact that all reward feedback is most é' e'-corupted, directly have that the confidence set Big always contain the groundtruth reward function.
Lemma D.2. For all & [T], r* B
Moreover, according to Liu et al. [2022a], the transition confidence set Bip always satisfies the following properties.
Lemma D.3 (Liu et al. [2022a)). There exists absolute constant 02 such that under Assumption 3 and the same choice of 3p as in Theorem D.I, we have that with probability at least 8:
. p" E BBp,for all E [T].
ΣT max drv(1P) ,Pp"" S Siddp,Tcc2tt Ieepp))
The first relation states that the transition confidence set contains the groundtruth transition model with high probability. And the second one states that if we use arbitrary model E B% to predict the transition dynamics under policy n', then the cumulative prediction error over T iterations upper bounded by function &.
Proof of Theurem D. In the following proof, we will assume the two relations Lemma D.3 hold.
We have that
V
V
(VTT pippt - ppp'''
<2H Σ d pt p p + Σ
(T
p' - v)
22H Σ dTv(PTT pt: p + Σ + +
T. Mexp >E - (T))) - O(HH
22HE(dp,T,co2ng ( [) + OT d'c'' + dR) +
where the first inequality uses the definition (T', p²) and the relation (r* p²,p') E B the third one holds with probability at least 1 - 8 by Azuma-Hoeffding inequality, the fourth one uses the second relation in Lemma D.3, and the last one invokes the standard regret guarantee for eluder dimension (e.g., Russo and Van Roy [2013]) where dæe dimg /2).
E
Additional details and proofs for Section 4.2
E.1 Algorithm details
In Algorithm 4, describe how to learn approximate von Neumann winner via running two copies of an arbitrary adversarial MDP algorithm. Specifically, we maintain two algorithm instances
(1) and (2)) In the k-th iteration, we first sample two trajectories (s (11 a a1.H) and ($1.H @1.H)
(1) (1)
(2) (2)
23

---

without reward by executing "
(1) and x// the two output policies of of and (f(2,, respectively. augment (1) # $ into the comparison oracle and get binary feedback y. After that, we
Then we input (s
(5 (1) with zero reward at the first
2 steps and reward y at step //
which we feed into (f)) Similarly we create feedback for (²) by using ($1: (1:H-1) and reward - y. The final output policy =(1) is a uniform mixture of all the policies sf(1) has produced during K iterations.
Algorithm 4 Learning von Neumann Winner via Adversarial MDP Algorithms
Initialize two algorithm instances sf(1,, of(2) for 1 ,,... K do
(2) for adversarial MDPs with horizon length H
Receive Th (1) from af) and Th (2) from of
Sample (s
1H (1:H) Tk (1) and ($1-H d1. ~ k
(2)
Query comparison oracle y ~ (er(M H 5H
(1) (2)
Return feedback (s(", ai (1)
0, ................................ 2- a
(1) (1)
H 11-1-0H111 to mh
(1) (1)
and (51²) di O,..... - H
(2) (2)
(2) (2)
0,
1- -1-1:1 y) to 222, respectively
(2) (2)
--
Output average policy mixture (11) where (11) Unif (TT }KE(K)
(1)
Converting the output policy a Markov policy. Note that the output policy т is a general non-Markov policy. However, we can convert it to a Markov policy in samplc-efficiet manner for tabular MDPs through simple procedure: execute for N episodes, then compute the empirical policy?
tu (a(s) = as
(x)
where (s, a) and (s) denote the visitation counters at state-action pair (s, a) and state s at step respectively. The following lemma claims that the resulted Markov policy क is also an approximate restricted Nash equilibrium.
Lemma E.1. If an e-approximate von Neumann winner, then à a 2e-approxinate von Neumann winner with probability at least 5, provided that N 2 84
E.2 Proof of Theorem 11
Proof. Define U(T, T') = Een ~xx M (H s. The AMDP regret of (1)
gives
Σ
U T n
(1) (2)
max
Σ
U
T. T
(2)
-KK--c
x: Markoy
ΣU
- 3K1-c
maxx J:: general
TT T
where the second inequality uses the fact that there always exists a Markov best response because only the state distribution at the final step matters in the definition of U.
Similarly the regret of (2) gives
( (2)
me T ))))) max Σ
U (1) ) 3K2-s.
Summing the two inequalities gives
min U (#0),) x²) max U(n, (2)) - 2-3
In other words
DGap (1) x()) < K
Set (t(sss) Unif(AA) if (s 0, L.c. if state is never visited at step h.
24

---

By the symmetry of preference function, we further have
DGap(# )) max UnT, 11) min (71,, max U (T)) - 1
T.
max U m1) U(11, m1) x¹'
2DGap(# x(2) - 43/K3.
E.3 Details for adversarial linear MDPs.
To apply the regret guarantees from existing works on adversarial linear MDP [c.g., Sherman et al., 2023], we need to show the constructed reward signal in Algorithm 4 is linearly realizable. Since the reward signal is zero for the first H steps, we only need to consider step 1. Recall the definition of linear MDPs requires that there exist feature mappings á and s such that (s') 1s a) (Øn (s, a). (s')). By the bilinear structure of transition, the conditional expectation of reward at step H in the k-th iteration can be written as
Ely 8H-1: 8--11 - = M
(1)
(8 H H
(.
H H-11:
8H
Tk
(2)
18
11) H-11 H
D- Σ
WH-1(s)E[M(s
H
H
k
(2))
SES
Therefore, the reward function constructed for (f) is linear the feature mapping Φ. Similarly, we can show the reward function constructed for (2) is also linear.
E.4 Proof of Lemma E.1
Proof. Let e (6(AAHN/6) where e is a large absolute constant. By standard concentration, with probability at least 1-8,
8, we have that for all s, if p. (8), = s) 2 4/N, then Jn(ss 2 NN = s)/2.
With slight abuse of notation, we define (: 8h) Σ we have
1a -1 EaIA-1191 #n(: 01:h-1, 81:h). Therefore,
St.
iA NP* = s)
Σ pst (sh = (1 - #x 5))1 S
PPS(S = =6] V
N
St.
LSA
S
N
2H
Given a Markov policy и, and general policy æ2, we define
Ih
(sh: an)
sly [M s'4)
It follows that for any policy n.
H
(U( - U(F,
Σ
Es
(fta 188) Fx( sn), o. (sh, " })}
h=l
H
p (an = 5) [1 ()) - #x(- [5)l s 5e/2.
h=1
Therefore,
DGap(fi, A) = max U(x' +) 1 < 2 max U(+' -1 11 S 2c.
25

---

F
Additional details and proofs for Section 4.3
F.1
Algorithm details
To state the algorithm in a more compact way, we first introduce several notations. We denote the expected winning times of policy x against policy x' in RLHF instance with transition p and preference M by
V E M(T,T)) Pp. I' Pp
Furthermore, we denote the best-response value against policy as
VTl. min V
and the minimax value as
V.M max min VT.
Algorithm 5 Learning von Neumann winner via Optimistic MILE
1: B < x M
2: execute an arbitrary policy to collect trajectory 70
3: for = 1,..., do
4: compute optimistic von Neumann winner (7*,, M 77) arg maxx, (.. Vas
5: compute optimistic best-response (x' M .²) = arg min (..M) V mt
P.M
6: sample ş' ~ Ø' and z' ~ x²
7: invoke comparison oracle on (7' I') ) to get y², add (7' "'.I''' into prest
8: for each (Texp (#*) U [xxp((()) do
9: execute π to collect a trajectory T, add (T, T) into Derans
update
B++1 ((, P L(M, Pree))
max L(M', Ppret) -.M
M'EM
and L(p, D Derans)
> max L(y', Derana) {p}
p/EP
11: output out = Unif(( hemm)
We provide the pseudocode of learning von Neumann winner via optimistic MLE in Algorithm In each iteration E [T], the algorithm performs the following three key steps:
Optimistic planning: Compute the most optimistic von Neumann winner म" by picking the most optimistic model-preference candidate (M,p) in the current confidence set B². Then compute the most optimistic best-response to  denoted as x².
Sample two trajectories 7' and z' from 7' and x'. Then input them into the comparison oracle to get feedback y", which is added into the preference dataset D prref- And similar to the standard OMLE, also execute policies from the exploration policy set that is constructed by using म' and n², and add the collected data into the transition dataset Dtrans-
Data collection:
Confidence set update: Update the confidence set using the updated log-likelihood, which is the same as Algorithm 3 except that we replace the -bseet preference therein by general preference
C(M, Ppret)= =
Σ
In (yA((T,)'))) + (1- y)(1 M(T,T')))
DD)
26

---

F.2 Proof of Theorem 12
We first introduce several useful notations. Denote by Bi Bip the preference, transition confidence set in the f-th iteration, which satisfy B = B% x BM- Denote the groundtruth transition and preference by pz and M*. To prove Theorem 12, it suffices to bound
E ((V
V pT,
Similar to the proof of Theorem D.1, we first state several key properties of the MLE confidence set B¹, which are trivial extensions of the confidence set properties in Liu al. [2022a].
Lemma F.1 (Liu al. [2022a]). Under the same condition Theorem 12, have that with probability at least - 6: for all t E (T)
(+) E
En maxpEBE (dTV (PT _ + dTv (PP ) S c22p;
MBX Eie MM(F M (T =')² ((3m)
The first relation states that confidence set B contains the groundtruth caasition-preferenne model with high probability. The second one resembles the second relation in Lemma D.3. The third one states that any preference model M in confidence set B' can well predict the preference over the previously collected trajectory pairs.
By using the first relation in Lemma F.1 and the definition of n' and x', have
Σ Vr- V. .t pr MM,
(
# xx 21 21,
D.M
WT I77
(dTV pe 1.g.)) + drv ot 1155)) + drv (PT (pT .p.)))) + drv drv P
Σ (VT' PT MM
V=' .r'
(drv( (IpE' 1.7.' + dry (IP gf+ IPpp)) + drv (PT. 2 . + drv(p p ppi)
Σ M (T', -M
+ (VTIn(L/O).
By the second relation in Lemma F.1 and Definition 3, we have
Σ (div(PF..P.)) + drv drv(F (pa pe
po + drv (P (P,,,,, PT.)) + drv p (p5))) I 4E(ddp, T, cBp, [Txp
where c absolute constant.
Combining the third relation in Lemma F.1 with the regret bound of cluder dimension (c.g., Lemma in Russo and Van Roy [2013]), we have
Σ { (T' (r(rzz)) s SO(VdBBTT)
Putting all pieces together, we have
Σ (Vot.r-- VT' vpritt.) 4E(dp, T. cBp, [Tхp)) O( (dMMMTT
27


Reviews:
[{"review_id": "TjJxSfToW2", "reviewer": "Reviewer_Sju6", "summary": "The authors attempt to show the conditions under which RLHF is theoretically identical to standard RL where a reward function is specified as a part of the environment. The algorithm P2R Interface is given as way to learn from preference feedback such that all requirements are met for RLHF to be identical to standard RL. The reduction of RLHF to standard RL is discussed in the context of utility-baed preferences and general preferences that do not meet the requirements of a utility function.", "questions": "- In the utility-based preferences scenario the authors state that the trajectories given as input to the comparison oracle must generated by the policy. How does this work in the case of Ouyang et al. [2022]'s approach where the reward model is learned in advance and therefore are not generated by the policy?", "limitations": "- The paper is non-trivial for someone not an expert on the specific topic of the paper to follow. It would be great for the paper to be more easily understandable by those with a background in preference-based RL, so that they may incorporate the learnings into their work.", "rating": 5, "confidence": 1, "soundness": 2, "presentation": 1, "contribution": 1, "strengths": "- The paper includes an extensive related works section.", "weaknesses": "- The paper is difficult for me to follow and understand. It is very full of jargon for which no explanation is provided.\n- It is not well motivated why the \"reduction\" the authors propose to make is necessary and the benefits it carries.\n- A discussion section to wrap up what has been shown in the paper would be helpful.\n- Figure 1 is missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1.** The paper is difficult for me to follow and understand. It is very full of jargon for which no explanation is provided.\n\n**A1.** We kindly ask the reviewer to specify the sections of the paper they found ambiguous. We are eager to provide clarifications where needed.\n\n**Q2.**  It is not well motivated why the \"reduction\" the authors propose to make is necessary and the benefits it carries.\n\n**A2.** The term “reduction’’ in computer science refers to a scheme of transforming one problem into another problem. In our paper, the reduction is used to convert the RLHF problem to a standard reward-aware RL problem. The benefits of designing such a reduction (as opposed to a single RLHF algorithm) is that any standard RL algorithm can be combined with the reduction to derive a RLHF algorithm.\n\n**Q3.**  A discussion section to wrap up what has been shown in the paper would be helpful.\n\n**A3.** Thank you for the suggestion. We will add the following conclusion section in the revision:\nThis paper studies RLHF via efficient reductions. For utility based preferences, we introduce a Preference-to-Reward Interface which reduces preference based RL to standard reward-based RL. Our results are amenable to function approximation and incur no additional sample complexity. For general preferences without underlying rewards, we reduce finding the von Neumann winner to finding restricted Nash equilibrium in a class of Markov games. This can be more concretely solved by adversarial MDP algorithms if the preference depends solely on the final state, and by optimistic MLE for preferences that depend on the whole trajectory. Our results demonstrate that RLHF, from both utility-based and general preferences, can be readily solved under standard assumptions and by existing algorithmic techniques in RL theory literature. This suggests that RLHF is not much harder than standard RL in the complexity sense, and needs not to be more complicated in the algorithmic sense. Consequently, our findings partially answer our main query: RLHF may not be more difficult than standard RL.\n\n**Q4.**  Figure 1 is missing.\n\n**A4.** Please refer to Appendix A in the supplementary materials for Figure 1.\n\n**Q5.**  In the utility-based preferences scenario the authors state that the trajectories given as input to the comparison oracle must be generated by the policy. How does this work in the case of Ouyang et al. [2022]'s approach where the reward model is learned in advance and therefore are not generated by the policy?\n\n**A5.** Our algorithms (e.g., P2R Interface) only need to query the comparison oracle with trajectories generated by the policies. This means that all results in this paper still hold without any change even if we allow the comparison oracle to compare arbitrary trajectories, as is the case in Ouyang et al. [2022].  \n"}, {"review_id": "WkDqh9GYX5", "reviewer": "Reviewer_nikD", "summary": "The authors study the problem of learning in preference-based RL and investigate the question of whether preference based RL is any harder that reward based RL. They show that for preferences that are based on an underlying reward function, preference based RL is no harder than reward based RL for most of the theoretical RL settings including tabular MDPs, linear MDPs, MDPs with finite eluder dimension. They propose an efficient algorithm that can solve this problem by reducing it to the reward based RL and solving the reward version instead. Further, they demonstrate that this reduction does not incur any additional sample complexity, requiring humans to provide preference on only a small portion of trajectories collected by the algorithm.\n\nFor general preference function, they propose a framework of factored Multi-Agent MDP to find the “von Neumann winner” solution concept. They further provide algorithms based on Adversarial MDP and Optimistic MLE to solve the problem in the setting where preference are entirely based on last state and on complete trajectory respectively.", "questions": "1. In line 116-117 : Why is underlying reward function not state-action Markovian? The corresponding value notation is not correct.\n2. Can you compare two states as in line 139 or is it two (state,action) pair?\n3. Why the input trajectories needs to be feasible with respect to underlying environment? Where is this assumption used?", "limitations": "- The paper does not address the setting when users can only provide preference at state and not trajectory level. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- The paper is well written and except minor notation issues it is a good read.\n    \n- The authors provide algorithms to solve the preference based RL problem with a theoretical guarantee on sample and computation complexity in different RL settings including finite state, linear and bounded eluder dimension settings.\n    \n- The authors also study this problem in general preference feedback setting and propose the solution concept of “von Neumann winner”. They further propose algorithms when preference depend  on the final state or entirety of the two compared trajectories.", "weaknesses": "- The paper assumes that humans can provide preferential feedback at trajectory level which is not always easy.\n- The concept of Eluder dimension and following results are not very intuitive.\n- The paper lacks any experimental results but the theoretical contribution is strong enough.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank the reviewer for their positive evaluation and detailed feedback. We would address the reviewer’s questions as follows.\n\n**Q1.** “The paper assumes that humans can provide preferential feedback at trajectory level”\n\n**A1.** We would like to clarify that in the utility-based setting, our results could apply to the setting where human labellers provide feedback on a state-action pair, where the preference is assumed to be based on the immediate reward (see Line 133-136 and Remark 1). We present primarily the results for trajectory-based feedback setting since this is the setting considered in most prior work (see e.g. Pacchiano et al. 2021, Novoseller et al. 2020).\n\nFor the non-utility-based setting, we do have results (Section 4.2) on the case where the preference is based on the final-state of the trajectory. Without this assumption, it is highly unclear how one can reason about preferences of trajectory based on human feedback at a state-action pair level.\n\n**Q2.** “In line 116-117 : Why is the underlying reward function not state-action Markovian?”\n\n**A2.** Thank you for pointing out the notational inconsistency. Indeed, in Line 116-117, the reward function $r^\\star$ should be state-action based (that is $r^\\star = [H]\\times \\mathcal{S}\\times \\mathcal{A} \\to [0,1]$).\n\n**Q3.** “Can you compare two states as in line 139 or is it two (state,action) pair?”\n\n**A3.** Thank you for pointing out this typo. Line 139 should be modified as “... evaluator prefers $\\tau$ over $\\tau’$ is”.\n\n**Q4.** “Why does the input trajectories need to be feasible with respect to the underlying environment?”\n\n**A4.** The feasibility requirement is more of a restriction on algorithms (that our algorithms meet) than an assumption. The motivation of this condition is to rule out trivial but impractical strategies. For instance, one can learn the full reward function using *no* samples from the MDP by iteratively querying the trajectory with the highest uncertainty in the whole trajectory space. However, such synthesized trajectories could be random sequences of pixels or streams of incoherent speech, which human labelers cannot reliably evaluate. In other words, the feasibility requirement can be thought of as a weakening of Definition 1: instead of assuming the comparison oracle to be valid on the whole trajectory space, we can alternatively assume that it is only valid on trajectories that are feasible.\n\n\n---\n\nAldo Pacchiano, Aadirupa Saha, and Jonathan Lee. Dueling rl: reinforcement learning with trajectory preferences. 2021.\n\nEllen Novoseller, Yibing Wei, Yanan Sui, Yisong Yue, and Joel Burdick. Dueling Posterior Sampling for Preference-Based Reinforcement Learning. 2020.\n"}, {"review_id": "Mno6wdpgu7", "reviewer": "Reviewer_ZkeP", "summary": "Refined writing: The objective of this paper is to establish a theoretical foundation for reinforcement learning based on human feedback preferences. The authors conduct an analysis on two aspects: (1) utility-based preferences in tabular MDPs, linear MDPs, and MDPs with low Bellman-Ruler dimension, and (2) general preferences considering the assumption of the calculation of von Neumann winners can be reduced to finding NEs of games with independent transition dynamics.", "questions": "Please find the questions in the weakness section.", "limitations": "This paper didn't discuss limitations of their analyses in a separate section, but it clearly states their assumptions when introducing the theoretical findings.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "Refined writing: The current limitations in the theoretical understanding of reinforcement learning from human feedback have prompted the need for addressing crucial questions, particularly in light of the significant success achieved by RLHF in applications such as ChatGPT. This paper effectively tackles these important questions, contributing to a deeper understanding of the subject matter.", "weaknesses": "The research topic of this paper is indeed interesting, and the reviewer initially had high expectations. However, there is a significant discrepancy between the paper's title and the actual content presented in the theoretical analyses.\n\nThe first part of analyses primarily focus on the utility-based preferences, which is applicable to simple linear MDPs or MDPs with lower Bellman-Ruler dimensions. It is challenging to extend the conclusion that \"human query feedback does not scale with the sample complexity of the reinforcement learning algorithm\" to more powerful function approximators commonly used in complex learning settings. Additionally, it raises the question of whether human feedback is even necessary for learning in these simple MDPs. The reviewer thinks that high-cost factors like human feedback are typically introduced in sophisticated tasks such as large language models and autonomous driving.\n\nCertain sections of the paper, particularly the discussion on general preferences, are challenging to follow. There is a lack of exploration regarding how the theoretical analyses and computation of the von Neumann winner can be translated into an algorithm for relating preferences to rewards. This omission makes it difficult to assess the practicality and applicability of the proposed method, as it is based on the assumption of factorizable underlying Markov games. In realistic scenarios, independent transition dynamics are not commonly observed. This raises concerns about the completeness of this section in the paper.\n\nIf the results of the paper are limited to simple MDPs, the authors may consider changing the title to reflect this specificity.\n\nBased on the reviewer's assessment, the current state of the paper does not warrant immediate publication. The authors are encouraged to reorganize their work and submit a more comprehensive version to top machine learning venues in the future.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments, and we will address them below.\n\n**Q1.** The first part of analyses primarily focus on the utility-based preferences, which is applicable to simple linear MDPs or MDPs with lower Bellman-Ruler dimensions. It is challenging to extend the conclusion that \"human query feedback does not scale with the sample complexity of the reinforcement learning algorithm\" to more powerful function approximators commonly used in complex learning settings.\n\n**A1.** Theorem 4 shows that the query complexity of P2R Interface only scales with the complexity of learning the reward function and is independent of the complexity of the RL algorithm, regardless of the RL tasks and algorithms we are considering. As a result, even in a complex learning setting with powerful function approximators, the query complexity of P2R Interface is still independent of the RL algorithms. Nonetheless, P2R Interface may have larger query complexity in more complex tasks because the reward function could be harder to learn.\n\n**Q2.**  Additionally, it raises the question of whether human feedback is even necessary for learning in these simple MDPs.\n\n**A2.** This paper studies the setting of RLHF where human feedback is the only information available and rewards either are not observable (utility-based setting) or may not exist (non utility-based setting). Therefore, learning is impossible without using human feedback in the setting of RLHF.\n\n**Q3.**  There is a lack of exploration regarding how the theoretical analyses and computation of the von Neumann winner can be translated into an algorithm for relating preferences to rewards.\n\n**A3.**  Experiments have shown that human preferences can be intransitive [Tversky, 1969], which implies there is NO reward function that can represent human preference in certain tasks. As a result, we adopt a new solution concept—von Neumann winner, and provide two schemes to learn it: (1) reduce learning von Neumann winner to learning factorizable Markov games and then apply adversarial MDP algorithms; (2) a preference-based version of the OMLE algorithm. Finally, we remark that it is impossible to relate preferences to rewards because no reward function can represent intransitive preference.\n\n**Q4.**  This omission makes it difficult to assess the practicality and applicability of the proposed method, as it is based on the assumption of factorizable underlying Markov games. In realistic scenarios, independent transition dynamics are not commonly observed.\n\n**A4.** We neither assume factorizable Markov games nor assume independent transition dynamics. Instead, we reduce the problem of finding von Neumann winners to solving factorizable Markov games (Proposition 9). Moreover, the reduction holds for any RLHF problems without any assumption."}, {"review_id": "EPs5TH265D", "reviewer": "Reviewer_XC4t", "summary": "The authors consider the RLHF setting. First, in the case where there (a) exists a ground-truth utility function and (b) feedback is positive with higher probability when there is a larger difference in rewards, they derive an algorithm to iteratively winnow down a ball of reward functions. When such structure cannot be assumed, they derive a reduction to adversarial MDPS for solving for the von Neumann winner.", "questions": "1) Could you add in https://arxiv.org/pdf/2305.18505.pdf and https://arxiv.org/pdf/2305.14816.pdf to your related work section and discuss how your approach differs from theirs?\n\n2) Do you get any sort of agnostic guarantee for Alg. 1 in the non-realizable case?\n\n3) Are \"oracle complexity\" (line 169) and \"query complexity\" (footnote 2) the same thing? If so, could you pick a term and stick to it?\n\n4) Imagine if instead of receiving stochastic feedback, you received a deterministic (+/-) label from the oracle. While this is a simpler setting in some sense, I'm not sure if you'd still be able to compare things to a fixed initial trajectory. Do you have any thoughts on how you could modify Alg. 1 to handle this setting?\n\n5) Could you clarify how you could run Alg. 1 with k-wise comparison feedback? I found section 3.3 of the paper unfortunately vague.\n\n6) Footnote 3's reasoning is a bit artificial. Could you instead motivate the setting you consider by noting that for empirical RLHF, people usually treat it as a \"bandit\" problem and only give feedback at the ending?\n\n7) Could you run something like NPG instead as a no-regret algorithm for the adversarial MDPs your reduction requires solving? If so, that might be an illustrative point to add in given it's a bit closer to the PPO-style algorithms people use in practical RLHF. Also, given everything is fully observed, is there an algorithm that gets a tighter rate than OMLE? It sort of feels like you're using a heavier hammer than necessary.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "(+) The paper is clearly written and the algorithms are intuitive and reasonable.\n\n(+) I haven't seen someone consider the von Neumann winner before in the RLHF space.", "weaknesses": "(-) I think there's some weird formatting on the top of pg. 8 as the line numbers stop. Could you fix this? Also, I think you're missing a superscript $(i)$ in the definition of a partial trajectory. Also, please add some space between line 343 and the equation below.\n\n(-) There are no experiments whatsoever.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank the reviewer for their positive evaluation and detailed feedback. We would address the reviewer’s concerns as follows.\n\n**Q1. Formatting issues.**\n\n**A1.** Thank you for pointing out these issues. We will correct them in the final version since we cannot update the paper during the rebuttal process.\n\n**Q2. Additional related work.**\n\n**A2.** Thank you for bringing these two papers to our attention. We will revise the related work section accordingly in the final version.\n\n**Q3. “Do you get any sort of agnostic guarantee for Alg. 1 in the non-realizable case?”**\n\n**A3.** If the ground-truth reward function is not realizable but known to have a small approximation error, i.e. $\\Vert r^\\star - r\\Vert_\\infty<\\Delta$ for some $r\\in \\mathcal{R}$, we believe it is possible to obtain results on learning the optimal policy up to error $O(\\sqrt{d_r} \\Delta)$, where the approximation error is amplified by the square root of the eluder dimension similar to the case in bandits with misspecification (Lattimore et al., 2020).\n\n**Q4. On “oracle complexity” and “query complexity”.**\n\n**A4.** Yes, they are referring to the same concept. We will modify Line 169 to “query complexity”.\n\n**Q5. On deterministic labels.**\n\n**A5.** If labels are deterministic in the utility-based setting, we have established an impossibility result (Lemma 3) where it is impossible to identify the optimal policy. Intuitively, this is because when labels are deterministic, only ordinal information about the reward function is kept and the rest is lost. For instance, one can only learn that $\\tau_1$ is preferred over $\\tau_2$ and $\\tau_2$ over $\\tau_3$. However, without information on the actual reward differences, one cannot compare a policy that generates $\\tau_2$, and one that generates $\\tau_1$ with probability 0.5 and $\\tau_3$ with probability 0.5.\n\nOn the other hand, in the non utility-based setting, our results can handle deterministic or arbitrary link functions. However, the solution concept would be different from that of the utility-based setting.\n\n**Q6. Clarification on k-wise comparison.**\n\n**A6.** To adapt Algorithm 1 to k-wise comparison, we simply need to change Line 7 from\n\n> Query comparison oracle $m$ times on $\\tau$ and $\\tau_0$; compute average comparison result $\\bar{o}$\n\nto\n\n> For $i$ from 1 to $\\lceil 2m/k\\rceil$:\n> - Query comparison oracle on $(\\tau,\\tau_0,\\cdots,\\tau,\\tau_0)$, receive output $\\phi$\n> - Compute $o_i\\gets \\frac{2}{k}\\sum_{j=1}^{k/2} I[\\phi(2j-1)>\\phi(2j)]$\n> \n> Compute the average $\\bar{o}\\gets \\frac{1}{\\lceil 2m/k\\rceil} \\sum_{i=1}^{\\lceil 2m/k\\rceil} o_i$\n\nHere, instead of querying a two-way comparison oracle for $m$ times, we alternatively query a $k$-wise comparison oracle for $\\lceil 2m/k\\rceil$ times. By Proposition 5, the computed $\\bar{o}$ has the same statistical property as if using $k/2 \\cdot \\lceil 2m/k\\rceil$ independent samples from a two-way comparison oracle. \n\t\n\n**Q7. On NPG as an adversarial MDP solver.**\n\n**A7.** There are policy optimization style algorithms for adversarial MDPs in the tabular setting (see e.g. Algorithm 3 in Efroni et al. 2020), which could indeed be used as the solver required by the reduction in Section 4.2.\n\n**Q8. \"Also, given everything is fully observed, is there an algorithm that gets a tighter rate than OMLE? It sort of feels like you're using a heavier hammer than necessary.\"**\n\n**A8.** In certain cases like tabular MDPs and kernel linear MDPs, we believe it is possible to obtain sharper rates by replacing the MLE-based confidence sets with ones that are specially designed to exploit the problem structures. For example, we can use Bernstein inequality to construct tighter confidence intervals for each entry $P(s’ \\mid s,a)$ of the transition matrix in the tabular setting. Nonetheless, the current version uses OMLE-style algorithms because of its algorithmic simplicity and its generality. Specifically, we can use one single algorithm (OMLE) to provide polynomial sample-efficiency guarantees for many distinctive RLHF problems, e.g., tabular MDPs, factored MDPs, linear kernel MDPs etc. Moreover, it also directly generalizes to RLHF under partial observability, e.g., observable POMDPs and decodable POMDPs.\n\n---\n\nLattimore et al. Learning with Good Feature Representations in Bandits and in RL with a Generative Model. 2020.\n\nEfroni et al. Optimistic Policy Optimization with Bandit Feedback. 2020.\n\nLin Yang, Mengdi Wang. Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound. 2020.\n\n\n\n"}]

Author rebuttal:

Meta-review: The paper provides a theoretical study of reinforcement learning from preferences. The paper provides a reduction of preference based RL to other RL settings and shows that in many cases the additional cost incurred by those reductions are small. For preferences that can be explained by an underlying unknown reward function, then the authors provide a reduction to reward-based RL. For more general preferences, the paper provides a reduction to finding a Nash-equilibrium in 2-player factored Markov games.

There was consensus among the reviewers that the paper provides a solid contribution to literature. While the results are not particularly surprising, the analysis is sound and well executed. There were initial concerns that the results are only applicable to simple / small MDPs but the authors could clarify this point in their rebuttal and thus, these concerns may instead show an issue of presentation. In fact, clarity and presentation was assessed very differently across reviewers. While some sound the paper well written and clear, others found it hard to follow. The AC found the paper to be clear but believes that this divide between reviewers' assessment on the presentation is due to 2 things:

1. The paper requires a certain background and whether the paper is easy to follow heavily depends on whether a reader is already very familiar with specific concepts such as Bellman eluder dimension or von Neumann winner etc. It would be advisable for the authors to provide more background in order to make the paper accessible to a wider audience, perhaps with examples and further pointers to the literature.
2. The title (and introduction) are very broad, which may raise expectations on the paper that are then not met. Given that RLHF is currently very popular for fine-tuning complex neural network models, readers may indeed be disappointed to see a rather abstract treatment that is somewhat removed from neural network models. Of course, the reductions are agnostic to the function approximator used (and the authors give explicit examples of problems with small BE-dim) but it is also not clear that the results indeed provide direct implications for RLHF fine tuning of neural network models. To avoid this mismatch in expectations, the authors are advised to emphasize in the title and introduction the nature of the contributions. Perhaps highlight the theoretical focus by appending "-- A theoretical study" to the title?

Overall, no consensus could be reached in the reviewer discussion. Based on the ACs own reading of the paper, the AC agrees that the paper does provide valuable contributions to the theory of preference-based RL, and believes that the weaknesses stem from issues in the presentation that can be addressed with smaller modifications in a camera ready version. As a result, acceptance is recommended.
Decision: Accept (poster)