Adversarial Policy Optimization for Offline Preference-based Reinforcement Learning
Authors: Hyungkyu Kang
Min-hwan Oh
Venue: ICLR 2025 Poster (2025)
Keywords: Preference-based reinforcement learning
Reinforcement learning with human feedback
Offline reinforcement learning
Primary area: reinforcement learning

Abstract: In this paper, we study offline preference-based reinforcement learning (PbRL), where learning is based on pre-collected preference feedback over pairs of trajectories. While offline PbRL has demonstrated remarkable empirical success, existing theoretical approaches face challenges in ensuring conservatism under uncertainty, requiring computationally intractable confidence set constructions. We address this limitation by proposing Adversarial Preference-based Policy Optimization (APPO), a computationally efficient algorithm for offline PbRL that guarantees sample complexity bounds without relying on explicit confidence sets. By framing PbRL as a two-player game between a policy and a model, our approach enforces conservatism in a tractable manner. Using standard assumptions on function approximation and bounded trajectory concentrability, we derive a sample complexity bound. To our knowledge, APPO is the first offline PbRL algorithm to offer both statistical efficiency and practical applicability. Experimental results on continuous control tasks demonstrate that APPO effectively learns from complex datasets, showing comparable performance with existing state-of-the-art methods.

Published as a conference paper at ICLR 2025
ADVERSARIAL POLICY OPTIMIZATION FOR OFFLINE PREFERENCE-BASED REINFORCEMENT LEARNING
Hyungkyu Kang
Min-hwan Oh Seoul National University Seoul, South Korea minoh@snu. ac. kr
Seoul National University
Seoul, South Korea
hyungkyu0 10 190snu. ac. kr
ABSTRACT
In this paper, we study offline preference-basee reinforcement learning (PbRL), where learning is based on pre-collected preference feedback over pairs of trajec- tories. While offline PbRL has demonstrated remarkable empirical success, ex- isting theoretical approaches face challenges in ensuring conservatism under un- certainty, requiring computationally intractable confidence set constructions. We address this limitation by proposing Adversarial Preference-base based Policy Opti- mization (APPO), a computationally efficient algorithm for offline PbRL that guar- antees sample complexity bounds without relying explicit confidence sets. By framing PbRL as two-player game between a policy and model, our approach enforces conservatism in a tractable manner. Using standard assumptions on fune- tion approximation and bounded trajectory concentrability. we derive a sample complexity bound. To our knowledge, APPO is the first offline PbRL algorithm offer both statistical efficiency and practical applicability. Experimental results on continuous control tasks demonstrate that APPO effectively learns from complex datasets, showing comparable performance with existing Sate--f-thhe-a methods.
INTRODUCTION
While Reinforcement Learning (RL) has achieved remarkable success in real-world applica- tions (Mnih 2013) Silver al. 2017 Kalashnikov et al. 2018 Brohan et al. 2022). its performance heavily depends on the design of the reward function (Wirth et al. 2017). which can be challenging in practice. To address this issue, preference-
reinforcement learning (PbRL), also known as reinforcement learning with human feedback, has gained increasing attention as an alternative to manually designed rewards. PbRL, reward model is learned from preference feedback provided by human experts, who compare pairs of trajectories (Christiano et al., 2017). This approach enables the learning process to align better with human intentions. PbRL has demonstrated its effectiveness in various domains. including gaming (MacGlashan et al. 2017 Christiano al. 2017] Warnell
ct al. 2018), natural language processing (Ziegler et al., [2019] Stiennon et al. [2020] Nakano et al.
2021
Ouyang et al. 2022 Bai et al., 2022), and roboties (Brown et al. 2019 Shin et al. (023)).
However, collecting preference feedback can be costly, especially when real-time feedback from human experts is required. In such cases, learning from pre-collected data is preferred over on- line learning. This approach is referred to as offline PbRL, where the learning process relies solely on pre-collected trajectories and preference feedback. Empirical studies have shown the effective- ness of offline PbRL (Kim et al., 2023 An et al.) 2023 Shin et al. 2023) Hejna & Sadigh 2024), leveraging techniques from deep RL literature. On the theoretical side, prior works prove that tra- jectory concentrability with respect to the data-collecting distribution leads to sample complexity bound (Zhu et al. 2023) Zhan et al. 2024a| Pace et al.) (024). However, they rely on the explicit construction of confidence sets to achieve conservatism (pessimism). Dealing with such confidence sets in the general function approximation setting requires intractable optimizations: Zhan et al. (2024a) involve tri-level constrained optimization with respect to the confidence sets of rewards and transitions, Pace et al. (2024) use uncertainty penalty defined as the width of confidence sets, and the analysis of Zhu al. (2023) is restricted to linear models. Despite provable sample complexity bounds, existing offline PbRL algorithms become computationally intractable with general function approximation.

---

Published as a conference paper at ICLR 2025
In this work, we propose a computationally and statistically efficient offline PbRL algorithm, Ad- versarial Preference- based Policy Optimization (APPO). Our analysis based on general function approximation for both the model and value function classes. Moreover, standard assumptions function classes and bounded trajectory concentrability (Zhan et al. 2024a) are sufficient to estab- lish our sample complexity bound. Beyond its strong statistical guarantees, to implement using standard optimization techniques. The core idea behind our algorithm is the two-player game formulation of model-based PbRL, which has been used in other areas of RL (Ra- jeswaran et al. 2020; Rigter et al., 2022, Cheng et al., 2022 Shen et al. 2024, Bhardwaj et al., 2024j. By framing PbRL as a game between policy and a model, we ensure conservatism without explicitly constructing intractable confidence sets. Furthermore, our novel reparameterization tech- nique allows us to find near-optimal policy efficiently via adversarial training. To the best of our knowledge, APPO is the first offline PbRL algorithm with both statistical performance guarantees and a practical implementation. Our contributions can be summarized as follows:
algorithm is simple
We propose APPO, simple algorithm for offline PbRL with general function approxima- tion. Based on the two-player game formulation of PbRL in conjunction with our reparam- eterization technique for the reward model, our algorithm ensures provable conservatism without explicit construction of confidence sets. To our knowledge, our APPO the first computationally efficient offline PbRL algorithm providing a sample complexity bound.
We prove the sample complexity of our proposed algorithm under standard assumptions on the function classes and concentrability. 'he result is rooted in our novel sub-optimality decomposition, which shows that adversarial training leads to model conservatism.
We present practical implementation of APPO that can learn with large datasets using neural networks. Experiments on continuous control tasks demonstrate that APPO achieves performance comparable to existing state-of-the-an algorithms.
1.1 RELATED WORK
Provable Online PbRL. In the tabular setting, Novoseller et al. (2020) developed an algorithm grounded in posterior sampling and the dueling bandit framework (uue et al. 2012), demonstrat- ing an asymptotic rate for Bayesian regret. Xu et al. (2020) proposed an algorithm leveraging an exploration bonus for previously unseen states, which provides sample complexity bound. [Saha let al.] (2023) and /Zhan et al.] (2024b) focused on the linear preference model with a known linear feature map, each offering regret and sample complexity bounds. However, their algorithms require solving an optimization arg max nt' [E,==(((TT]
Er-xr [ for some positive definite ma- trix Σ, which is computationally intractable. To address this challenge in the linear model, Wu &
Sun 2024) devised randomized algorithm with a provable regret bound and further proposed
bbdel- posterior sampling algorithm under the bounded Eluder dimension (Russo Van Roy) 2013 assumption, ensuring bounded Bayesian regret. Recent works have also explored provably
efficient algorithms under the general function approximation setting (Chen et al.) [022] Wu Sun
2024 Chen al. 2023). Chen et al. (2022) introduced an exploration-bonus based algorithm that
provides bounded regret in both pairwise and n-wise comparison settings. Additionally, Chen et al. 2023) leveraged the conditional value-at-risk operator (Artzner 1997) to devise an algorithm with regret guarantee. [u et al. (2024) took a different approach, studying neural function approximation in the context of reward models. In another notable work, (Swamy al. (2024) reframed PbRL as zero-sum game between two policies, encompassing general reward models.
Provable Offline PbRL. While there has been growing amount of research on online PbRL,, the theoretical understanding of offline PbRL remains relatively limited. A primary challenge in offline PbRL, much like in offline standard RL, is ensuring sufficient conservatism the model. Zhu et al. (2023) addressed this challenge by proposing a pessimistic maximum like- lihood estimation (MLE) algorithm for the linear model with known transitions. Zhhan al.) (2024a) extended this idea to general function approximation, highlighting the importance of tra- jectory concentrability establishing a lower bound for sample complexity. Despite the prov- able sample complexity bound, their proposed algorithm, FREEHAND-transine ing arg max, arg min,er arg ( ((T)))
relies on solv- [x-=),x(((T]] where R. is the confi- dence set of rewards and P is the confidence set of transitions, which is intractable in prac- tice. Pace al. (2024) study different but related setting, where the agent elicits high-quality
2

---

Published as a conference paper at ICLR 2025
preference information from offline data. Their method achieves conservatism through explicit uncertainty penalties defined as (T( = sup, sup,, (r((T) - r2(r) (reward uncertainty) and ap(s,a) = sup Ps (1 - P2(- s,q)l (transition uncertainty), which makes it in- tractable with general function approximation. CChang et al. (022)) also explored slightly different scenario where the data collection policy is known and online interaction is allowed. They demon- strated that simple natural policy gradient combined with MLE reward is provably efficient. but their sample complexity bound is affected by an additional concentrability coefficient relative to KL-rregularize policies.
Adversarial Training in RL. Adversarial training is a widely used approach in RL literature Ra-
jeswaran et al., 2020; Pásztor et al., 2024), especially offline (standard) RL (Rigter et al., 2022
Cheng et al. 2022; Bhardwaj et al., 2024). The basic idea to leverage adversarial training to
implement conservative policy optimization. Recently, adversarial training has also been applied in
human preference alignment (Makar-Limanov Limanov et al. 2024]] Cheng et al.) 2024 Shen et al. 2024). The most closely related work to ours is Shhnn et al. (2024), which also formulated PbRL as two- player game. However, their focus is on online PbRL., and while they provide proof of convergence for the optimization objective, this does not necessarily translate into a sample complexity guarantee.
2 PRELIMINARIES
(r where Markov Decision Processes. We consider an episodic MDP AS (P
S and A are the state space and the action space, H is the length of each episode, P = {Pr h== is the collection of transition probability distributions, and r* = {rī ) is the collection of reward functions. Each episode starts at some initial state 81 without loss of generality and the episode ends after HI steps. For each step h [H], the agent observes the state Sh, and then takes action as. The environment generates reward r% ($). ax) (note that, in the preference-bas based learning setting, rewards at each step are unobservable to the agent) and next state sh+1 according to the transition probability PE (- 8h; an.)
The agent takes actions based on its policy æ {mA) (=(H) where ( 8) is a probability distri- bution over A. The state-value function and the action-value function of policy ı with respect to reward r = {rn) are the expected sum of rewards up to termination, starting from 8p, = s and (sh, an) = (s, a) respectively, following the policy x. Formally, they are defined as
H1
H
VE,r (s) = Ex
(sws,, and 8h = 8 Qh == E, J
Σ
Σ -
ru(S ax) 8h = 8, an = a
To simplify the notation, for 9 : S + R. use Py(s, a) to denote E. (1 For any policy т and reward r, the Bellman equation relates Q" to V as
(s, = rn (8, + P'V,+1, (+)r()) R (9 a)), 18) (8)= 0.
Given a policy π = (TE)), we define the state visitation distribution as di (s) == (sh = s) where P, the probability distribution of trajectories (s1, ................................ 8H, ax) when the agent uses policy x. We overload the notation to denote the state-action visitation distribution, di (s. a) := (*h = 8, a). addition, we denote the distribution of trajectories under π by dd (7).
Offline Preference-based Reinforcement Learning. We consider the offline PbRL. problem, where the agent cannot observe the true reward p* but only binary preference feedback over trajectory pairs. Specifically, we are given preference dataset 2 pref {(>=7.0 -T,,1 """) ) that consists of ii.d. trajectory pairs -", {s a% " Jh=1 (i 0, 1) sampled by some reference policy p. For monotonically increasing link function $ : R + [o, 1], we assume the preference feedback n E {0. 1} is generated by the following preference model:
P(u = 1 - Pr7 is preferred over 70) = (br ((((()))-
-r)(r)))
where we denote (T) - rz (sa, an) for given trajectory T (81, a1 ai...., tionally, we assume that ń = ([ ((r)), where R is a bound on trajectory returns, is
.....,55 SH az). Addi-
OOur result easily extends the general case with an initial distribution p(-). We can modify the MDP by setting fixed initial state 81 and Pi a), = p(-) for all E A.
3

---

Published as a conference paper at ICLR 2025
finite. When & is set to be the sigmoid function o(x) 1/(1 cxp(-x)), we obtain the widely used
model (Bradley & Terry, 1952) In addition to the preference dataset, we have an unlabeled trajectory dataset Pmj {(7"h,, Th J where the trajectory pairs are sam- pled i.i.d. by executing the reference policy μs. The agent's goal is to find an 6-optimal policy á with respect to the optimal policy π², which satisfies Vi,,-- (51) - (s,((()) e.
General Function Approximation. We consider general function approximation for rewards and transitions: the function class of rewards R and the function class of transitions P. We do not impose any specific structure them, R and P can contain expressive functions such as neural networks. Based on the function classes, we construct a reward model using maximum likelihood estimation f E arg min,eR" RR(T) where
(n(r) (r9,rt.))
E [y log -((()) + (1--)) log
v)
r(()))
Similarly, we learn transition model Ph arg migpp Lr (P; for all h E [M]] where
(P; = (sn.. (1) Dmy [log P(sn+1 Sh an.]
Additional Notations. We denote [n] = 21. n) for E N. For I, E Rd, (x. denotes the inner product and y. Given a function f: f:S S x A R and a policy n, we write f = (a (f a)]. For given dataset D, we use EE-D [f to denote Σ ExED f(x).
3
ALGORITHM
3.1 PBRL AS A TWO-PLAYER GAME
previous study on model-based PbRL by Zhan et al. (2024a) proves that the following optimization problem yields a near-optimal policy मt for an appropriately chosen constant Ç:
f arg max min (VT,, Vi,, (s1) where R fr E R" La(r) Lx(F) + +]-
(1)
rER
The minimization with respect to reward model E R ensures conservatism, which is essential for a provable guarantee. However, the constrained optimization is intractable with general function approximation. To address this challenge, we formulate the model- PbRL problem as a two- player Stackelberg game (Von Stackelberg 2010) between the policy and the reward:
# E arg max (VT,,- (s1) Vi (81))
subject to r E arg min (V1, (s, E(r;
TER
Here, f(r:)) is loss function that penalizes if it deviates from f. In the Stackelberg game formulation, the reward minimizes (*)(()) (s1, while the policy maximizes it. We can interpret this competition by viewing (31) V/ (s1) (s) as the relative performance of π compared to μ with respect to reward r. Intuitively, æ maximizes the cumulative reward r*, as in the standard RL setup. However, rd minimizes the cumulative reward when evaluated under This competition facilitates conservatism and makes π robust to model error.
Then, what loss function & leads provable bound? A naive choice might be Li((r) ( as it leads to the Lagrangian dual form of the optimization problem in ( while disregarding the Lagrangian multiplier. However, the loss (r; (R(r) LR(F) does not guarantee statistical efficiency, because the Stackelberg game in (2) does not include the Lagrangian multiplier for the likelihood constraint. Instead, we propose the trajectory -pair E loss:
E(r; = E,,,,'~ [|(r(>)) r(r')) ((())))(((77)) f(7 f(1
which leads provable guarantee (Theorem 4.1. Intuitively, this loss measures the deviation of from i by evaluating the difference in total reward (return) between the two trajectories. Given the unlabeled trajectory dataset D uaji. we approximate E(r; with its finite-sample version:
Epm, (r: B(r (r)De [[(r(r") r(r))) (f(79) +(+'))]]
In the following two sections, we discuss how to implement the optimization in in a sample- efficient manner.
4

---

Published as a conference paper at ICLR 2025
Algorithm 1 Adversarial Preference-based Policy Optimization with Rollout (APPO-rollou)
Input: Number of rollouts K1, K2. constant 7/, o Unif(A) for all [H]
2: Estimate E arg min, Cr((r)
3: for t = 1,,.., T do
4: Execute n² to collect K1 trajectories Pioloout
5: Optimize r' E arg min (ErwP) [r(r)] EynDin [r(T)] + Arp,,((:1
6: Compute Q' via PE(J,, f K2) in Algorithm
7: Update policy x (a) xx (a(a 8) (8, for all h E [H]
8: end for
9: Return π = EE=
Algorithm Adversarial Preference-basee based Policy Optimization (APPO)
1: Input: Constant y, Initial policy o = Unif((A) for all E [H]
2: Estimate À arg gR LR(r), Ph arg min (T h) for all h E [M]
3: for t = 1,....T do
4: f arg min JEFN
(Ei-) B (sn [f (Tp))))))))))))))()) fn an) + A (f: (f:
5: Update policy Tht
mft1(aa (a 8) aa(a| 8) exx(((/((s.a)) for h [H]
6: end for
7: Return 7 Et=1
3.2 ADVERSARIAL OPTIMIZATION FOR PBRL
In this section, present an algorithm, APPO-rollout, that serves as building block of our main algorithm. For APPO-rollout, we consider the setting where the transition P* known or where online interaction (without preference feedback) is possible. This is temporary assumption, main algorithm (Algorithm 2 works with an unknown transition.
Algorithm presents the pseudo-code of APPO-rollout, which is based on the Stackelberg game formulation of PbRL. that we discussed. Inspired by the adversarial training methods offline
RL under the standard setting (Cheng et al.] 2022 Rigter et al. 2022 Bhardwaj et al. 2024),
alternately optimize the policy and reward to solve the optimization problem in (2).
Reward Model Update for Provable Conservatism. The reward model update aims solve the following optimization problem approximately:
min "
EE
[r(r)]
E [r(r]] (E(r:))) arg min (VT, (s1) + XE(r;)), (3) 7mp4
FER"
which is the inner optimization in 2). The expectations [r-n(r(F)] and E(r; are approximated using offline data Dinj. Also, we collect trajectories by executing π², to compute the linteesample version of E (r(r)) Note that the trajectory rollout (Line 4) is possible since we assume known transition P* or access to online interaction.
Policy Update. After optimizing r", we estimate the action-valle funetion of n² with respect to p using a policy evaluation subroutine PE, whose pseudo-code is provided in Algorithm 3 This subroutine computes an approximate value function Q' using Monte Carlo estimation, providing an error bound relative to the true value function Q The theoretical analysis of PE is presented in Appendix B With the estimated value function Q', we then proceed to update the policy using trust region policy optimization (TRPO) (Schulman al. 2015) update.
3.3 APPO: REPARAMETERIZED ALGORITHM FOR UNKNOWN TRANSITION
In this section, consider the setting where the transition P* is unknown. In Algorithm I the information from the transition pa is utilized in Line 4, where we collect on-policy trajectories to approximate Ex-z+(((7) Moreover, the policy evaluation step in Algorithm involves trajectory
5

---

Published as a conference paper at ICLR 2025
rollouts. To bypass such on-poliey rollouts, make the following observation:
E E [r(T)] By [r(r)] VT. Vi, (81)
Σ (sn [Q o o/) - (h,
(4)
which is due to the performance difference lemma (Lemmal E. Since the expectation on the right taken with respect to d' the date-gener distribution of Dunj. we can approximate using Diaj- Furthermore, given the policy n², the Bellman equation implies a mapping between reward models and action-value functions. Specifically, for given reward model r = (rx ( k= we have the action-vall value function {QK Conversely, suppose that we have a function class F that contains every action-value function. For f = {.r 1==1 E _H we can construct the corresponding reward model satisfying the Bellman equation fh. Th P (fn+100 o0T Formally, define the induced reward models:
Definition (Induced reward model). Given f = [1a]mm E and a policy {TNJee) we define 1 the induced reward model r (* f where Thr = =sh (3 o Th+1) for
h E [H] (we set fH+1 = 0 by convention).
Therefore, given reward model r and action-value function f. we have that
Vh. - P (Qh+1.r Tnt1), fn. -,= + P% (fn+1 TT) for all h [M].
Importantly, the mapping does need to be bijective for theoretical analysis, long the Bellman equation holds. Using this mapping in conjunction with our observation in (4) we repa- rameterize the optimization problem as:
H
arg min JEFH
Σ 1=1
(en ann [Ifa (h)))s)) (n(s XE(fiP",
(5)
where 8(f;
- -(()
The offline dataset Drnj is sufficient approximate the optimization objective in with
E Da [(h o Th)(s)))) - fa an)] == E (en.on)) [(f, (sx, fa (sn,
ED, (f: P. = E ((oor))>P.. [[(r7) -r "7, (7')) (f(79) (('')||| = =(f;
where we use the estimated transition model P in place of p* Moreover, since we directly optimize the action-value function, a policy evaluation oracle is not required to update the policy. Therefore, this reparameterization allows us to solve the optimization problem in (2) without access to the true transition P* policy evaluation oracle. The complete pseudo-code is presented in Algorithm
Remark on Computational Complexity. The computational complexity APPO is primarily de- termined by the value function optimization (Line 4) and the policy update (Line 5). Although optimizing f is generally a non-convex problem, can be efficiently implemented using gradient- based methods when F is class of neural networks. For the policy update, it is known that Th +++((a s) x T (a () (xp((n//(( a)) is derived from the TRPO objective (Schulman et al, 2015
Neu et al. 2017):
T arg max mag' [1h o T(S)) - 17 -DD (=(- (w) [s))]]
which is widely used in deep RL. As result, the policy update is efficient within the deep learning framework. In practice, other policy optimization techniques (Schulman al. 2017: Fujimoto al. 2018 Haarnoja et al. 2018) can also be applied. Overall, APPO relies on solving two standard non- convex optimizations compute f and n², both of which are practical to implement with neural function approximation. This computational efficiency contrasts with that of existing offline PbRL algorithms, which require intractable optimization confidence sets, discussed in Section L.1

---

Published as a conference paper at ICLR 2025
4 THEORETICAL ANALYSIS
In this section, present theoretical analyses of our proposed algorithm, APPO. We note that APPO-rollout also guarantees a sample complexity bound, which is presented in Appendix C
We assume the reward class R and the transition class P are realizable and rewards bounded.
These are standard assumptions (Chen et al., 2023 Zhan et al. 2024a Pace et al. 2024).
Assumption (Reward realizability). We have ri for all h [H]. In addition, every E R satisfies S r(r) S for any trajectory T.
Assumption (Transition realizability). We have P7 E P for all E [H].
Additionally, we introduce the value function class and assume it bounded. Note that every Qh,- satisfies the condition ||/ S R due to Assumption T
Assumption (Value function class). For any h E [H], re E R" and policy n, we have Qh, E F. In addition, every f E F satisfies 0 S f(s, a) S for all (s,a) (x)x)xx A.A.
The following assumption defines the trajectory concentrability coefficient between the optimal pol- icy n' and the reference policy
Assumption 4 (Trajectory concentrability). There exists a finite constant CTR such that the behavior policy μ and the optimal policy x* satisfy sup, d'(
d' (r) CrR-
The bounded CTR ensures that the support of d' sufficiently covers the support of d= similar to the concentrability condition in Zhan et al. (2024a 2 As result, we expect Panj to contain high- quality trajectories. The lower bound in Zhan et al. (0244) shows that the trajectory concentrability is essential in offline PbRL. This implies that offline PbRL is strictly more challenging than offline standard RL, where step-wise concentrability is sufficient to achieve performance guarantee (Ue- hara & Sun 2022). We now present the sample complexity bound.
Theorem 4.1. Suppose Assumptions
2 3 4nldd With probability least 8, Algorithm
with x (CTTR), CIR, 7) =
log
achieves
V
V
R22 H
R
H 5
H
H
log A
50
CTR
log
RH
max log
log
RH
M
8
N
5
T
112 log LA]
H² log IA log((
R² log(H(||18)) }). and
Setting T θ
N
=
θ
max
M
θ Ciee 2 log( [ (8)
Algorithm 2 achieves e-optimal policy, i.e. VT VÝ, S.
Our analysis naturally extends to infinite function classes by applying the standard covering number argument, replacing the cardinalities [R], [P], and [F] with covering numbers. To our knowledge, FREEHAND-transttonn Zhan al. (2024a) is the only statistically effi- cient algorithm for offline PbRL in stochastic MDPs. Our sample complexity bound matches theirs C3 R2 n1² log(H (PI/))
Discussion Theorem 4.1
for labeled data (M). However,
SEREHHADD-transttin requires è
unlabeled
trajectories where Cp is the trajectory concentrability for transition This highlights a trade-off: While FREEHAND-rransine tractable. That is, problem. Therefore, our APPO is the first offline PbRL algorithm achieve both provable statistical efficiency and computational efficiency.
has tighter bounds for unlabeled data (N), it is computationally in- requires solving a nearly intractable nested optimization
"Our analysis remains valid under an alternative definition based the reward model error ratio, similar that used by /Zhan et al. (2024))
'Zhan al. (2224a consider reward functions defined over trajectories, thus their reward class G, is com- parable our R. They use bracketing numbers in their bound, but write here [P] for simplicity.

---

Published as a conference paper at ICLR 2025
Proof Sketch. We outline the proof of Theorem 4.1 where the detailed proof is deferred to Ap- pendix D The key observation is our novel sub-optimality decomposition:
VT.r- VIT
Vi - 1r-- + Vi
VI, 18--r VT. + Vi,,- +
ViT
Vi
1,p
1,r
())MLE error
(I)) Optiizatiio emor
(MT) : Policy update regret
where p' =r -p. and the initial state $1 is omitted here for readability. The term (I) is bounded by standard MLE guarantee (Lemmal E.2). while the policy update rule ensures that the sum of terms (III) over T steps bounded (Lemmal D.3) For (II), Assumption and À > CTR imply that
VT
Vi, = EET stompe [r'(79 -(7")( - (++)))))(--)---)) +((*)) (()))
S CTR ol mn [1((79) f()7)(()))))))))) - f(r")]] S XE(J"; P", P)-
Observe that APPO approximately solves the optimization problem in ( (Lemma D.I. and this optimization problem is equivalent arg min {V
1,pp, Lopt + AE(f:*)f)) Since
V
rp.. r' and r=¹ P P-, r", follows that V. Vi + XE(FI S VT.
V + -V XE(Q"" ;P* ;P*,))+ +c.
where represents approximation error. Thus, obtain (II) Combining the results with VT. Vř. = + (Vr.- Vi we complete the proof.
PRACTICAL IMPLEMENTATION OF APPO
While providing strong statistical guarantees, APPO allows practical implementation with neural networks, leveraging advanced training techniques from deep learning. In this section, we present a practical version of APPO tailored for deep PbRL. The pseudo-code is outlined in Algorithm 4 For practical implementation, we assume the standard discounted MDP setting in deep PbRL (Christiano) al. 2017), where trajectory segments of length L are given and preference labels are assigned to segment pairs.
Reward Learning. While theoretical analysis is based the maximum likelihood estimator, any reward learning strategy can be employed. This flexibility allows APPO to benefit from state-of- the-arts preference learning methods, such as data augmentation (Park al. 2022 and active query techniques (Shin et al. 2023; Hwang et al., 2024 Choi et al. 2024).
Training Value Functions. Given a parameterized policy Te and an aation-valur function Qg. the optimization objective in (5) can be adapted to the discounted setting as follows:
arg min EE (s.a)=d" [Q0 no (s) Qs a)] + AB(To.T))= [1(rg f) - (12 - (T
where r (T) = EL (Qo(s, 7(Q a o No) (8(41)) for the segment T (s1, a1.... SL, aL)- We employ the approximation (* (T) (st, 4:) = (Q Th (+1()) to avoid the need for tran- sition model. Additionally, to stabilize training, we apply the clipped double Q-learning trick (Fu- jimooo et al. 2018 Haarnoja et al. 2018 and maintain a separate value-function Vp. Given mini- batches of trajectory pairs Buny and transition tuples Bup each action-value function Q trained by minimizing Z3. = >Caad d= + Ege (where is moved to the first term, without loss generality), defined as follows:
Cady (Bup) B(ssa))BB. [Qar (8. no(s)) - Qsi a))
and E (Bua)) = ((77,71))88 (1 10 (T')) - (f(77) -((7)))((7'))]
(6)
Here, we use the notation r (7) = Ete (s1, - (V and we (s) denotes an action sampled from no(- s). Given target Q-networks 10 )eE11,2 we train Vi by minimizing
27
Le (Bup) Es-Bip
Vo(s)
min Q (SN41, To ( sE(1.2
8

---

Published as a conference paper at ICLR 2025
Datasct & # of feedback
Oracle
MR
PT
DPPO
IPL.
APPO (ours)
BPT-500
88.33
10.08
#7.57
22.87
3.93 #4.34
34.73
53.52
+-1.99
box-close-500
93.40 #3.10
29.12 #13.2
0.33
#1.16
10.20
+11.5
5.93
4.5.1
18.24 +-5.6
dial-turn-500
75.40 45.47
61.44
#6.08
68.67
1:2.4
26.67
#22.2
31.53
#:2.5
80,96
+-4.49
sweep-500
98.33 11.87
86.96
26.93
43.07
124.6
10.47
115.8
27.20
2:3.8
26.80
+5.32
BPT-wall-500
56.27 16.32
0.32
10.30
0.87 11.43
0.80 11.51
8.93 1:.844
64.32 121.0
sweep-into-500
78.80 18.80 77.96
28,40 =5.47
20.53 8..26
23.07 #7.02
32.20 17.35
24.08 15.91
drawer-open-500
100.00 +0000
98.00
#22322
88.73 #11.6
35,93 11.2
19.00 #13.6
87.68 +:1000
lever-pull-500
98.47 +1.77
79.28
#2.96
82.40
4:22.7
10.13 #12.2
31,20 +15.8
75.76+ +7.177
BPT-1000
88.33 1:4.76
8,48 55.80
18.27
1:066
3,20 13.04
36.67 1:1744
59.04 1:19.0
box-close-1000
93.40 +3.10
27.04
114.6
2.27 22.86
9.33 #9.60
6.73 #8.41
34.24 188.5
dial-tun-10000
75.40 #5.47
69.44 #4.70
68.80
+5.50
36.40 #21.9
43.93 113.4
81.44 +6.73
sweep-1000
98.33
87.52
#7.87
29.13
114.6
8.73 16.44
38.33 #24.9
17.36
BPT-wall-1000
56.27 1.632
0,48 10.47
2.13 2:996
0.27 10.85
14.07 111.5
62.96 1884
sweep-into-100
78,80 +7.96
26.00
#5.53
20.27
47.84
23.33
47.80
30,40
4:7.74
18.16 +1111
drawer-open- 1000
100.00
4.000
98.40
#2.82
95.40
#7.27
36.47
#7.30
28.53
118.4
98.56
4:268
reverppull-1000
98. 11.77
88.96
13.94
72.93
110.2
8.53
29.96
40.40
117.4
76.96 14.40
Average Rank
2.316
3.125
4.375
3.063
2.125
Success rates on Meta-World medium- dataset with 500 and 1000 preference feed- back samples, averaged over 5 random seeds. The results of baselines, Oracle, PT, DPPO, and IPL, are taken from Choi al. (2024), where Oracle refers to the policy trained using IQL with ground- truth rewards. The abbreviation BPT stands for button-press-toploon..
Table 1:
Intuitively, the term Ludyy ensures conservatism by regularizing Qs to have lower values near d and higher values near d, Additional insight can be gained by rearranging the integrand of Egp
Σ (st, f(3), a;) VV((541)))
This expression represents the sum the TD errors evaluated over the segment т. Thus, the loss Es minimizes the difference in trajectory TD errors between 70 and
Training Policy, We directly optimize the policy using the loss function in (8. The entropy regular-
ization term similar to that in SAC (Haamoja al. 2018). except that we use a randomly sampled Q₂t instead of the clipped value min [1,2] Qa The policy loss is given by:
Lo (Bup) = EanBur 1Qss (s, ()()) - aem
(>())] (s, i Unif{1,2]
(8)
EXPERIMENTS
Datasets and Evaluation. We evaluate our proposed algorithm on the Meta-Worke (Yu et al. 2020) medium repllay and medium-expers datasets from Choi et al. (2024). Our main experiments use the medium-repl. ay dataset, while the experiments with the medium-expe in Appendix F These datasets have favorable property: they are not learnable with incorrect re- wards (random or constant). This property is crucial for evaluating offline RL algorithms since their survival instinct can allow them to perform well even with completely incorrect reward signals (Li al. 2024). For more details on the dataset, see Choi al. (2024). Following the experiment pro- tocol of Choi et al.) (2024), the preference dataset consists of pairs of randomly sampled trajectory segments of length 25. The preference label is generated based on the ground truth reward, where (0, 1) label is assigned if the trajectory rewards differ by more than threshold of 12.5, and (0.5, 0.5) label assigned otherwise. We evaluate algorithm performance using the success rate for each task, which indicates whether the agent successfully completes the task.
dataset are presented
Algorithms. We consider four offline PbRL algorithms as baselines: Markovian Reward (MR),
Preference Transformer (PT) (Kim et al. 2023). Direct Preference-based Policy Optimization

---

Published as a conference paper at ICLR 2025
button-pret -pees-resssseeee toosss--pdow..lll,, 1000
dial-tum, 1000
lever-pull, 1000
100
100
100
Success Rate(%)
80
80
Success Rate/%)
80
60
Success
0.0
6.5
1.0
1.5
2.0
2.5
0.0
0.5
1.0
155
2.0
2.5
0.0
0.5
1.0
3.5
2.0
2.5
Training Step
165
Training
165
Training Step
165
1e-2
A= 3e-2
A = 1e-1
Figure 1: Effect of the conservatism regularizer
button-prees-tooaddow--alll
dial-turn
lever-pull
100
100
80
80
Success Rate
Success Rate
Success Rate
60
60
60
40
500
500 of foodback
of feodback
# of fondbark
APPO
MR
Oracle
Figure 2: Success rates of APPO and MR, with varying number of preference feedback samples.
(DPPO) (An et al. 2023) and Inverse Preference Learning (IPL.) (Hejna & Sadigh 2024). MR an
instance of IQL. Kostrikov al. 2022) trained with Markovian reward model, while PT assumes
a general sequential reward model implemented using a Transformer (Vaswani) 2017) architecture.
DPPO directly optimizes the policy without using reward model, while the other baseline methods
are based on IQL (Kosrrkoov et al. 2022). We evaluate the practical version of APPO in Algorithm using the same reward model as MR and setting À 0.03. Further details are in Appendix G
6.1 EVALUATION RESULTS
Table shows the performance of algorithms on the Meta-World control tasks. APPO outperforms shows comparable performance almost every dataset. Notably, APPO outperforms the policy trained with ground truth rewards in the dial-turn and observe that MR is a strong baseline, as reported in previous works (Hejna & Sadigh 2024 Choi et al. 2024). These results suggest that APPO performs comparably to state-of-the baselines, even with provable statistical guarantee.
press-topdow-wwaeee datasets. We also
Effect of Conservatism Regularizer. We investigate the effect of conservatism regularizer X, the coefficient to balance the adversarial loss Ladh and the trajectory-pair e loss Egg. In Figure APPO learns successfully with wide range X, but properly tuned improves performance and stabil- ity. We note that APPO has only one algorithmic hyperparameter X, whereas IQL algorithms (MR, PT, IPI.) require at least two (expectile parameter and temperature). DPPO, on the other hand, has two hyperparameters (conservatism regularizer and smoothness regularizer).
Effeet of Preference Dataset Size. PbRL, learning from small preference datasets is desired for cost-efficient learning. We evaluate the effect of preference dataset size on APPO's performance, varying the number of feedback samples from 100 to 2000. Figure 2 shows that APPO is robust to preference dataset size, displaying variance comparable MR, strong baseline, as shown in Table [ Note that APPO outperforms policy trained with ground truth rewards, using only 100 preference feedback samples.
10

---

Published as a conference paper at ICLR 2025
REPRODUCIBILITY
We describe the experimental details in Section and Section including training protocol and neural network architecture. Our code is available at https: / gi thub. cww.coo/ooooo cat/b.coo/hh-1100 1ah-labAAPPO git As explained in Section we use the Meta-Wan World medium-reples replay dataset from Choi et al. (0024) which is available their official repository along with download instructions.
ACKNOWLEDGEMENTS
This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. RS-2022-NR071 18331853 and RS-2023-00222663) and by Al-Bio Research Grant through Seoul National University.
REFERENCES
Gaon An, Junhycok Lee, Xingdong Zuo, Norio Kosaka, Kyung-Min Kim, and Hyun Oh Song. Direct sefference-based policy optimization without reward modeling. Advances in Neural Infor- mation Processing Systems, 36:70247-70266, 2023.
Philippe Artzner. Thinking coherently. Risk, 10:68-71, 1997.
Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al. Training a helpful and harmless assistant with reinforcement learning from human feedback. arXiv preprint arXiv:2204.0586,, 2022.
Mohak Bhardwaj. Tengyang Xie, Byron Boots, Nan Jiang, and Ching-An Cheng. Adversarial model for offline reinforcement learning. Advances in Neural Information Processing Systems, 36, 2024.
Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324 345, 1952.
Anthony Brohan, Noah Brown, Justice Carbajal, Yevgen Chebotar, Joseph Dabis, Chelsea Finn, Keerthana Gopalakrishnan, Karol Hausman, Alex Herzog, Jasmine Hsu, et al. Rt-1: Robotics transformer for real-world control at scale. arXiv preprint arXiv:2212.068// 2022.
Daniel Brown, Wonjoon Goo, Prabhat Nagarajan, and Scott Nickum. Extrapolating beyond sub- optimal demonstrations via inverse reinforcement learning from observations. In International conference on machine learning, pp. 783-792 PMLR, 2019.
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy opti- mization. In International Conference on Machine Learning, pp. 1283-1294. PMLR, 2020.
Jonathan D Chang, Wenhao Shan, Owen Oertell, Kianté Brantley, Dipendra Misra, Jason Lee, and Wen Sun. Dataset reset policy optimization for rlhf. arXiv preprint arXiv:2404.0884: 2024.
Xiaoyu Chen, Han Zhong, Zhuoran Yang. Zhaoran Wang, and Liwei Wang. Human-in numan-in-the-lowe in-the-loop: Provably efficient preference based reinforcement learning with general function approximation. In International Conference on Machine Learning, pp. 3773-3793. PMLR, 2022.
Yu Chen, Yihan Du, Pihe Hu, Siwei Wang, Desheng Wu, and Longbo Huang. Provably efficient iterated evar reinforcement learning with function approximation and human feedback. In The Twelfth International Conference on Learning Representations, 2023.
Ching-Ar An Cheng, Tengyang Xie, Nan Jiang, and Alekh Agarwal. Adversarially trained actor critic for offline reinforcement learning. In International Conference on Machine Learning, pp. 3852- 3878. PMLR, 2022.
Pengyu Cheng, Yifan Yang, Jian Li, Yong Dai, Tianhao Hu, Peixin Cao, Nan Du, and Xiaolong Li. Adversarial preference optimization: Enhancing your alignment via rm-llm game. In Findings of the Association for Computational Linguistics ACI. 2024, pp. 3705-3716, 2024.
11

---

Published as a conference paper at ICLR 2025
Heewoong Choi, Sangwon Jung, Hongjoon Ahn, and Taesup Moon. Listwise reward estimation for offline preference- based reinforcement learning. In Forty-first International Conference on Machine Learning. 2024.
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 sys- tems, 30, 2017.
Yihan Du, Anna Winnicki, Gal Dalal, Shie Mannor, and R. Srikant. Exploration-drivenn policy op- timization in RLHF: Theoretical insights on efficient data utilization. In Forty-first International Conference on Machine Learning, 2024.
Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor- critic methods. In International conference on machine learning, pp. 1587-1596. PMLR, 2018.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In International confer- ence on machine learming, pp. 1861-1870. PMLR, 2018.
Joey Hejna and Dorsa Sadigh. Inverse preference learning: Preference-based rl without a reward function. Advances in Neural Information Processing Systems, 36, 2024.
Joey Hejna, Rafael Rafailov, Harshit Sikchi, Chelsea Finn, Scott Niekum, W. Bradley Knox, and Dorsa Sadigh. Contrastive preference learning: Learning from human feedback without rein- forcement learning. In The Twelfth International Conference on Learning Representations, 2024.
Donald Joseph Hejna III and Dorsa Sadigh. Few-shot preference learning for human-in-the-loop rl. In Conference on Robot Learning, pp. 2014-2025, PMLR, 2023.
Minyoung Hwang, Gunmin Lee, Hogun Kee, Chan Woo Kim, Kyungjae Lee, and Songhwai Oh. Se- quential preference ranking for efficient reinforcement learning from human feedback. Advances in Neural Information Processing Systems, 36, 2024.
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
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the Nineteenth International Conference on Machine Learning, pp. 267-274, 2002.
Dmitry Kalashnikov, Alex Irpan, Peter Pastor, Julian Ibarz, Alexander Herzog, Eric Jang, Deirdre Quillen, Ethan Holly, Mrinal Kalakrishnan, Vincent Vanhoucke, et al. Scalable deep reinforce- ment learning for vision-based robotic manipulation. In Conference on robot learning, pp. 651- 673. PMLR, 2018
Yachen Kang, Diyuan Shi, Jinxin Liu, Li He, and Donglin Wang. Beyond reward: Offline preference-guided policy optimization. In International Conference on Machine Learning, pp. 15753-15768. PMLR, 2023.
Changyeon Kim, Jongjin Park, Jinwoo Shin, Honglak Lee, Pieter Abbeel, and Kimin Lec. Pref- erence transformer: Modeling human preferences using transformers for RL. In The Eleventh International Conference on Learning Representations, 2023.
Diederik P. Kingma and Jimmy Ba. Adam: method for stochastic optimization. In 3rd Interna- tional Conference on Learning Representations (ICLR), 2015. https://///a www./org/aaao abs// 1412. 6980 arXiv preprint 1eXiv:141226998
Ilya Kostrikov, Ashvin Nair, and Sergey Levine. Offline reinforcement learning with implicit q- learning. In International Conference Learning Representations, 2022.
Kimin Lee, Laura M Smith, and Pieter Abbeel. Pebble: Feedback-efficient interactive reinforcement learning via relabeling experience and unsupervised pre-training. In International Conference on Machine Learning, pp. 6152-6163. PMLR, 2021.
12

---

Published as a conference paper at ICLR 2025
Anqi Li, Dipendra Misra, Andrey Kolobov, and Ching-An Cheng. Survival instinct in offline rein- forcement learning. Advances in neural information processing systems, 36, 2024.
Xinran Liang, Katherine Shu, Kimin Lee, and Pieter Abbeel. Reward uncertainty for exploration in preference-basee reinforcement learning. In International Conference on Learning Representa- tions, 2022. URL
Runze Liu, Fengshuo Bai, Yali Du, and Yaodong Yang. Meta-reward-net: Implicitly differentiable reward learning for preference-based reinforcement learning. Advances in Neural Information Processing Systems, 35:22270- -222444 2022.
James MacGlashan, Mark K Ho, Robert Loftin, Bei Peng, Guan Wang, David L Roberts, Matthew E Taylor, and Michael Littman. Interactive learning from policy-dependent human feedback. In International conference machine learning, pp. 2285-2294 PMLR, 2017.
Jacob Makar-Limanov Arjun Prakash, Denizalp Goktas, Amy Greenwald, and Nora Ayanian. STA- RLHF: Stackelberg aligned reinforcement learning with human feedback. In Coordination and Cooperation for Multi-Agent Reinforcement Learning Methods Workshop, 2024.
Volodymyr Mnih. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013.
Reiichiro Nakano, Jacob Hilton, Suchir Balaji, Jeff Wu, Long Ouyang, Christina Kim, Christo- pher Hesse, Shantanu Jain, Vineet Kosaraju, William Saunders, et al. Webgpt: Browscr-assisted question-answering with human feedback. arXiv preprint 212002212
Gergely Neu, Anders Jonsson, and Vicenç Gómez. unified view of entropy--egullrized markov decision processes. arXiv preprint arXiv:7005.07798. 2017.
Ellen Novoseller, Yibing Wei, Yanan Sui, Yisong Yue, and Joel Burdick. Dueling posterior sam- pling for preference-basee reinforcement learning. In Conference Uncertainty in Artificial Intelligence, pp. 1029-1038, PMLR, 2020.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to fol- low instructions with human feedback. Advances in neural information processing systems, 35:
27730-27744, 2022.
Alizée Pace, Bernhard Schölkopf. Gunnar Ratsch, and Giorgia Ramponi. Preference elicitation for offline reinforcement learning. In /CML 2024 Workshop: Foundations of Reinforcement Learning and Control Connections and Perspectives, 2024. URL httpps://openereiierr wwwpeeeiiiiiiiieeeeeeee net/ forum?
Jd=YGaRv4UCRh
Jongjin Park, Younggyo Seo, Jinwoo Shin, Honglak Lee, Pieter Abbeel, and Kimin Lee. SURF: Semi-supervised reward learning with data augmentation for feedback-efficient preference based reinforcement learning. In International Conference on Learning Representations, 2022. URL
Barna Pásztor, Parnian Kassraie, and Andreas Krause. Bandits with preference feedback: A stackel- berg game perspective. In The eighth Annual Conference on Neural Information Process- ing Systems, 2024. URL https://openrevieet
http://orruiiiddwwseae-ee 12hXH
Aravind Rajeswaran, Igor Mordatch, and Vikash Kumar. A game theoretic framework for model based reinforcement learning. In International conference machine learning, pp. 7953-7963. PMLR, 2020.
Mare Rigter, Brumo Lacerda, and Nick Hawes. Rambo-rl: Robust adversarial model-based offline reinforcement learning. Advances in neural information processing systems, 35:16022-16097, 2022.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, 26, 2013.
13

---

Published as a conference paper at ICLR 2025
Aadirupa Saha, Aldo Pacchiano, and Jonathan Lee. Dueling rl: Reinforcement learning with trajec- tory preferences. In International Conference on Artificial Intelligence and Statistics, pp. 6263- 6289. PMLR. 2023.
John Schulman, Sergey Levine, Picter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pp. 1889-1897. PMLR, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06344 2017.
Han Shen, Zhuoran Yang, and Tianyi Chen. Principled penalty methods for bilevel reinforce- ment learning and RLHF, In Forty-first International Conference on Machine Learning, 2024. URL http:://pppeereeiieeet net/ for.mmid-
Daniel Shin, Anca Dragan, and Daniel S. Brown. Benchmarks and algorithms for offline preference- based reward learning. Transactions on Machine Learning Research, 2023. ISSN 2835-8856.
David Silver, Julian Schrittwieser, 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, 550(7676):354 339939. 2017.
Yuda Song, Yifei Zhou, Ayush Sekhari, Drew Bagnell, Akshay Krishnamurthy, and Wen Sun. Hy- brid RL: Using both offline and online data can make RL efficient. The Eleventh International Conference on Learning Representations, 2023.
Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano. Learning to summarize with human feedback. Advances in Neural Information Processing Systems, 33:3008-3021, 2020.
Gokul Swamy, Christoph Dann, Rahul Kidambi, Steven Wu, and Alekh Agarwal. A minimaximalist approach to reinforcement learning from human feedback. In Forty-first International Conference on Machine Learning. 2024.
Masatoshi Uehara and Wen Sun. Pessimistic model-based offline reinforcement learning under partial coverage. In International Conference Learning Representations, 2022.
A Vaswani. Attention is all you need. Advances in Neural Information Processing Systems, 2017.
Heinrich Von Stackelberg. Market structure and equilibrium. Springer Science & Business Media, 2010.
Garrett Warnell, Nicholas Waytowich, Vernon Lawhern, and Peter Stone. Deep tamer: Interac- tive agent shaping high- sigh-dimensional state spaces. Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
Christian Wirth, Riad Akrour, Gerhard Neumann, and Johannes Fürnkranz. A survey of preference- based reinforcement learning methods. Journal of Machine Learning Research, 18(136):1-46. 2017.
Runzhe Wu and Wen Sun. Making RL with preference-based feedback efficient via randomization. In The Twelfth International Conference on Learning Representations, 2024. URL https:// openreview
ppenreeiew..net/oorumff www.e/ooommdddeeellloo..
Yichong Xu, Ruosong Wang, Lin Yang, Aarti Singh, and Artur Dubrawski. Preference-based re- inforcement learning with finite-time guarantees. Advances in Neural Information Processing Systems, 33:18784-187799 18794, 2020.
Tianhe Yu, Deirdre Quillen, Zhanpeng He, Ryan Julian, Karol Hausman, Chelsea Finn, and Sergey Levine. Meta-worid: A benchmark and evaluation for multi-task and meta reinforcement learning. In Conference on robot learning, pp. 1094-1100. PMLR, 2020.
Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed dueling bandits 2012.
problem. Journal of Computer and System Sciences,
14

---

Published as a conference paper at ICLR 2025
Wenhao Zhan, Masatoshi Uchara, Nathan Kallus, Jason D. Lee, and Wen Sun. Provable offline preference-based reinforcement learning. In The Twelfth International Conference on Learning Representations, 2024a.
Wenhao Zhan, Masatoshi Uehara, Wen Sun, and Jason D. Lee. Provable reward-agnostic preference- based reinforcement learning. In The Twelfth International Conference on Learning Representa- tions, 2024b.
Banghua Zhu, Michael Jordan, and Jiantao Jiao. Principled reinforcement learning with human feed- back from pairwise or k-wise comparisons. In International Conference on Machine Learning, pp. 43037-43067. PMLR, 2023.
Daniel M Ziegler, Nisan Stiennon, Jeffrey Wu, Tom Brown, Alec Radford, Dario Amodei, Paul Christiano, and Geoffrey Irving. Fine-tuning language models from human preferences. arXiv preprint arXiv:1909.08522 2019.
15

---

Published as a conference paper at ICLR 2025
A ADDITIONAL RELATED WORK
Empirical PbRL. Incorporating preference feedback into reinforcement learning has been explored through various approaches. One standard method involves training reward model from prefer- ences, which is then used to train a standard RL algorithm (Christiano et al. 20177 Ibarz et al,, 2018 A variety of techniques have emerged in this area, including unsupervised pre-training (Lee et al.
2021), exploration driven by uncertainty (Liang et al. 2022), data augmentation (Park et al., and meta-learning (Hejna III Sadigh 2023). to list a few. Another prominent line re-
2022
search focuses on preference learning via active query methods (Shin et al. 2023 Hwang et al.
2024
Choi et al. 2024), which have shown strong empirical performance.
Beyond the conventional Markov reward model, some studies have proposed alternative reward structures. For example, Kim et al. (2023) employed transformer architectures for reward mod- eling, while Liu et al. (2022) and Hejna & Sadigh (2024) explored learning action-valus functions rather than directly modeling rewards. Several approaches bypass explicit reward models altogether, instead optimizing policies directly (An al. 2023 Kang al. 2023 Hejna et al. 2024).
B DETAILS ON THE POLICY EVALUATION SUBROUTINE
We present simple policy evaluation subroutine in Algorithm It requires online rollouts and access to the reference policy. The idea of policy evaluation via online rollouts adopted from Chang et al. (024), while the analysis follows standard methods.
Algorithm 3 PE: Monte Carlo Policy Evaluation
1: Input: Reference policy μs, Current policy xτ, Estimated reward i, Number of rollout K
2: for h E [H] do
3: Collect K i.i.d. trajectories {(s], at ...., s/ )==
4: where at p-((11 5/) for j h, af 2 (un x s4), and at 7T( 18)) for
5: Compute g¹: = P(s).. ) then set Dj. (s ah k
6: Least square value function estimation Of arg minjer K (xa.))D (f(s, a) - -9)
7:
end for
8:
Return (Q
We have the following guarantee.
Lemma B.1. With probability at least Algorithm guarantees that, for every (t. E [T]
[H].
- - (s,))) Ra log (H(()1)))
E Ba a- (1h +
=:rEE
K₂
where 0g is an absolute constant.
Proof. Since (0% |0h.rll. < for any policy x and r E R.H, Lemma E.4 with B = R and K = K₂
leads to
(oh(s,.) Qz (s. <
Ca log((F1/5)
E Eswdy an (xf)
K₂
over for any fixed (t, h) E [T] [H) The union bound over all (t, h) E [T) x H concludes the proof. L
16

---

Published as a conference paper at ICLR 2025
C THEORETICAL ANALYSIS OF APPO-ROLLOUT
In this section, provide theoretical analyses of APPO-rollout, naive algorithm for solving the optimization problem ( The ideas presented this section are relevant to the proof Theo- rem 4.1 and the results valuable for comparison with related works.
Before stating the theorem, we define step-wise concentrability, which is always bounded by CTR-
Definition 2 (Step-wise concentrability). Csr = max (UP(S,))ESxA (x.0))
(s,a)
Lemma C.1. It always holds that CST S CTR.
Proof. For a fixed pair (s, a), consider the set of trajectories a(s,a) == {r ($1, .1....,.... 8H, aH) 8/: = 8, 04 a). Then we have that
(s, f (T(..)) (F(r)dr.
for any fixed policy æ. Therefore, for every (8, a) E E x A, we have that
dh. (s, a) ST(S.) d= (T)dT (8,0) 0.) (T( (T))
(=) CTR.
S sup dT())
Taking the supremum on both sides concludes the proof.
Theorem C.2. Suppose Assumptions 7 and hold. With probability least Algorithm with
((CTR), >> CIR. 17 = V
2log LA| R-T
achieves
Vi," Vi
[R]
CIRRV VM
R
R
log |
OSt
TH Fl
0
V log
+
+RH
RH
log
8
VK
T
K₂
Setting
RR Jog
K1
R (og(11)/8)
M M= 0
(og(11118)))))
and
K₂ = R² Csy log(TH F8)8)
Algorithm uchieves e-oplimal policy, i.e. VI,"" VÍ,,- S e.
Discussion on Theorem C.2. We compare this bound with PbRL algorithms that assume a known transition model allow online rollouts. In comparison FREEHAND (Zhan et al.] (024a). APPO-rollout achieves a nearly identical rate for labeled data, but unlike FREEHAND. quires additional unlabeled trajectories. This represents trade-off between statistical efficiency and computational complexity, as FREEHAND relies on solving nearly intractable nested opti- mization problem. Another comparable algorithm DR-PO (Chang al.] 2024), which estab-
re-
lishes sample complexity of θ (Cr log( (6)66) for labeled data. Unlike APPO-rollout,
23
DR-PO assumes homogeneous rewards, which removes dependence on H from the bound. While additional factor, CSET supreD sup, d'(T)' where is a set of policies close to terms KL divergence. This addi- tional term arises because DR-PO does not explicitly ensure conservatism.
their bound tighter in CTR, it comes the cost of dependence
(T(
For simplicity, introduce some notation regarding optimization objectives in Algorithm 1 For r, F E R! we define
( = Ey [r(r)] - E.-Den [r(T)] + AE (r;
and its population version as
C. (r: P) Brane [r(T)] Erro (r(T)] AE(::))
17

---

Published as a conference paper at ICLR 2025
C.I OPTIMIZATION ERROR
In this section, we prove that the (finite-sample) optimization objective (r) is close to its population version, Log (r; The result ensures that rf is good approximation of the solution to the optimization program with infinite samples, i.c.
r 2 arg min S (T; VER
Lemma C.3. With probability at least - 8/2, all t E [T], we have
Lop (rp((r';f) (r';f) - Copr (r";;) + 2Epppro
where Eapproz is defined in Lemma C.4
Proof. We have the following decomposition:
(r) (f)
S (r"; m²) (r (r - Lo Cope (r); + E (rin(r::
- (r=;;)))
(
(lI)
(II)
Conditioned on the event defined by Lemma D.2 (I) and (III) are bounded by Copt. Moreover, the optimality of rf implies (II) O.
Lemma C.4. With probability at least 8/2, every [T] and R. it holds that
log(6/R1/5) 2K
2 2 6) R| Éapprox
(r) (rip(r;ff)) S RV
2R
Proof. Fix r R.H, and note that
- ((pu((:))
< BENDY [r(r)] - E. [r(T)] Errx)(((TT]] + 1BTrDe, [r(r]] - E Er [r(T]]
+ (1 [(r - () (r-') - E(r",r) - ymr - - (r-
Since ir(r) < and ()r-f)(r)) < for any trajectory т, each term can be bounded by Hoeffding inequality. Specifically, each of these three events occurs with probability at least 8/6:
log(6/8)
E ET marer [r(T)] EE Ey [r(7)] < R
R
2Ki
log(6/5)
(EWDDylI(T)) - (3>ma(((T)) =Brs)(((t)|{{)) RR
2.V
log(6/6)
[(r (
- (r ()r-)) B ((--)) - (7))) < 2R
2N
Taking union bound over these events and all E R" with probability at least 1 - 6/2, it holds that
log(6/Rl/0)
log(6)R
log (6|
(r: L. (r: s R
+ RV
+ -
2K1
2N
2N
log(6/R(/0)
2 2log(6|R /8)
R
+ 2R
2K1
N
for every R
18

---

Published as a conference paper at ICLR 2025
C.2 POLICY UPDATE
We present the guarantee regarding the policy update steps. The proofs in this section are based on the standard analysis of the natural policy gradient (also referred to trust region policy optimiza- tion) CCa et al. 2020; Chang et al., 2024).
Lemma C.5. With probability at least 8/4, it holds that
(s1) - (+)) < RHV
log |A| 2T
211EPE 2Cst
T
Proof of Lemma
C.5
The performance difference lemma (Lemma E.1 implies that
Σg (s1) (s1)
Raya
Σ TTi (sh: "), 1 8p)) T.(. sn)) 1=1
H
E B [1Qh(s,)) (, s) - - |s)]]
h=1
i
E Bowdg"
[((TT'>
(s, x, sh) mh(- |s)))
(
Bounding (I). Decompose the inner product inside the expectation:
(n -), M, s) ( s)}
(n (sh, 1), m (: 8) - +1 8)) + 1i ) "h 1-1
8) - 8)}
I (n (sn. ), mp(. | 8) m/ 8)) + 17 Qh (sh. :) )m 1 [ss) -m (-1
(1 1), m (s 11-mpp ( 8)) nlt { ()
m - $)]l
(9)
where we use Hölder's inequality with the fact that |1 |l I R. Now recall that the policy update step (Line in Algorithm | llads
++1 (.1( "h
(7) Th(- (-1 s) exp (nQ) (s.
where (s) = Eaes (a exp (ny), (s, a)). Using the relationship 17 (s, a) log (s) +
1+1 (a 8) - log logT/(( (a 8), it holds that log n
(nh) :), m
nh ++1 [))
(log (1())) log Th 1+1 (- 8) - log M 8), = 8) 1
241(1 (-1s))
(log tht ++ (- (=|s) log ( s), x 5) - Th x. (-1s))
(log T 1+1 (-1 [s) log ( x), (.1 s)) - DKL (Th (+1(1) (.1 8) s)]l s))
(.
+ log T/ (s)
(log ( 8)
Th. (s) (+( [s)) DDr (Th
++1 [)]l ( ss)
DKL (T/( s) ( s)) DKL (mf(-) [s]]| (-1s)) DKL (ah ++1 (- ||>|]| ())
< DKL. (TT( (: 8) ()) (s)) Drr (zi6 10)) (-1s)) - | (s) - (-1
19

---

Published as a conference paper at ICLR 2025
where the second equality holds since Z% (s) is constant given and the last inequality holds due to Pinsker's 's inequality. Combining this bound with (9). we obtain
-,, () - (1((115))
DKL (TM() () (s) -DE (TA(- s)]l= s)))
nR ( T (-16)]12 || 8) m x (- [0](?)
T
T
1 R2
(Del (+M())) 3)1 6)) DD (T +)]l= (.1 ((1))) + Σ
2
1=1
T+1 (-1)s)) R²
DEL ( () 8)) Dxn 1)
< log |A| + RTT
where the first inequality holds since Vo E R ar - x22/2 < a²/2, and the second inequality holds due to the fact that o Un) Finally, setting /
2log LA] Rx
(I) is bounded by
(I)
Σ (.
7'(- s))
log
|A|
nRT
Tlog AA|
<
RH
2
h=1
Bounding (I.).
We condition on the event defined by Lemma B.1 Then we have
E Bandy [[CQTT (s. )+
Beaaayaa [ (8, (8,
BlanamaR' [ (s, - 0 ((((sa))
d (s,a)
Eandy an an (s))) -h((sa)) )²]
<
2
sup hE(m (x,A)E8xA
max
(s,
< V 2C
where the first inequality holds due to Jensen's 's inequality, the second inequality uses importance sampling, and the last inequality uses Lemma B.1
20

---

Published as a conference paper at ICLR 2025
E Bondy [1CQE - Qh)(s, )) mhh
Eg Bandz Jaumt [ (s, (h(
Bondy awon (o - (2(),a)) )
dh (x)
an [ (0, Q a))
2 max sup
he(m]] #ES (s)
d= (8)
< 2 max sup
Bondg an (
(%((,,)) (1)
hE(m] #ES (s)
PE
Therefore, we obtain the bound
T
[100 - (s, m/(. [ss))]
(II)
t=1
h=
E Bandy"
() [s))
<
2CST.
We conclude the proof by combining the bounds on (I) and (II).
Now we prove Theorem based on the lemmas.
Proof of Theorem C.2 We condition on the event defined by Lemma E.2 (with 8' 8/4),
Lemma and Lemma which hold simultaneously with probability least 8. Consider the following sub-optimality decomposition at step l:
V
VIT, VIA VI
Vi,"*
Vi,. Vi.
Vi Va
V 1, Via. 1
(0) MLE estimation error
+ V.rp
Vi
T.p. + VI, + 1,pe Vu
1
1,ya
Optimization
VT
Va
(10)
(II) Policy update regret
where we omit the initial state sj for simplicity. Bounding (I).
Since we condition on the event defined by Lemma E.2 have
() ViJi - Vi.
E (-(
< V
21

---

Published as a conference paper at ICLR 2025
Bounding (II.. have that
We can relate the terms V Vitt-t
Vil 1,8-p E(rt; .). By Assumption 4
Vi Vi, 1,p-pt
E -
I T [
- ( + +r((++)]
-
-TTRE(";;A) v (E(");A)
where the last inequality holds since { is non-negative and X 2 CTR. Further, Lemma C.3 implies
AE(r";)) S VT. 1, 1,pe
1, + +XErr;;A) + ZEappror
Vl.
VI 1,r + (6/44 + 28 Capprox
1,rt
where the last inequality holds due Lemma E.2
( E, rlau - f(T')(()))) -
(7 +r
I Brp [|f(T)) - -(- - r* +r) (0/4).
Therefore, have
(I) S Xe, (6/4) + 2 approz
Bounding Sub-optimality. Putting the bounds on (I) and (II) into 10 we have
Vi
Ver
(6/4)) + (6/4) + 2eppproz + Viye 1,r
(11)
Since Algorithm Treturns the mixture policy # + E n², the sub-optimality is VT.
# Eiml
Vir..) Using the bound in and Lemma C.5 holds that
V
Vi,r-
1,r-
1
1,r. Viri
T 1=1
T
(TREs (er((6/4) + 2 2aapproz +
Vi- Vi
log A
(8/4, + (6/4) + 2Eapproz + RH
2/HEpE v OST
27
(Vios
[
CTRKVH H VM
R
R
log AA
CST log
TH
00
RH
RH V
VK
VN
Kg
22

---

Published as a conference paper at ICLR 2025
D DETAILED PROOF OF THEOREM 4.1
For simplicity, we introduce some notations regarding optimization objectives in Algorithm E F#l, we define
2 For
Eyp (f:
Σ E as [In (sn) frass, + N&D (f:P.F)
and its population version as
(s; B [/b o (((a))) Sn un)] + NE(;; P)
D.1 OPTIMIZATION ERROR
In this section, prove that the (fiiite-samlle) optimization objective Lope P, is close to its population version (Jp F). The result ensures that s is a good approximation for the solutions the optimization program with infinite samples, i.c.
ft x arg min Cpp (f)
JEFH
Remark. For this section, we assume that the maximum likelihood transition estimator P is com- puted using half of Dmj and the losses Lupe P) are computed from the other half. This in- creases the sample complexity only by a constant factor but helps avoid union bound over P in the proof of Lemma D.2
Lemma D.1. With probability at least 8/2, for all t [T], we have that
Cap (f) S (0=) ;f) +e appprox
where Capprox is defined in Lemma D.2
Proof. Consider this decomposition:
(f'((f:; (Q= :F)
(ft:) Ci (ft: (ft: L (Q :P,) ( (Q,,; C.pe (Q" (Q=²;A)
(II
Conditioned on the event defined by Lemma D.2 (I) and (III) are bounded by Capproz- Moreover, the optimality of for implies (II) 0.
Lemma D.2. With probability at least 8/2, for every E [T] and f FH, it holds that
H3T (oTlog(SH
(f: (f: S $8RV
2RHee(688) = Cupprox
Proof. Due the policy update Line 7 of Algorithm the following function class:
the policies { (a..eeeeet belongs to
exp (I (f
a(a s)
'f E F for all E
Eves exp Et= (n
It is clear that [T|| IF[T.
23

---

Published as a conference paper at ICLR 2025
Step 1. Fix h E f E F, and II. Since If r()s R. for all S, Hoeffding inequality
implies that
(8/5)
Ees EDy If [sh)] Esn-ay Ifo ((s))] S RV
2.N
with probability at least 6/8. Similarly, since (f(s _ R for all (s, a) E E x A, it holds that
log(8/8)
E (lsn.a))Deii [s an]] - E (an [f(sn, an)] - RV with probability at least 1 - 6/8. Thus, with probability at least 1 - 0/4, we have
2N
B(en [f (8n) f(sn, an)] Bo (f x(8)) - f(n,
( [f o o (sa)] - (on If T(T))))]]]
Elss DeD [[ an)] - dad (s))
log((8/1 (8/))
< RV
N
Consider union bound over all h E [H],f f F, and II. Since tं. for every (f, (T) [H], with probability at least 1 8/4, we have
E Dan [A o ( fr(sh,
Σ A=1
E Ron [fh TT fn(sh:
H
E (sn o [n an) Em [In mTt fa am)
logg SH F11111/00
(log(81(FF100)
< RH
S 2RH
N
N
for every f E.
Step
We have that
-
E(f:P",A)). (12)
Again, we use Hoeffding inequality to bound the first term. Fix f E F" and -= { " and consider the function " (Recall that "" ". (8,a) ff((s, P( (s+1)(s, for all
h E [H] and a) S A). Since 1(r,, - -F) s 2RH for any trajectory т, we have that
() (rp,-- - -))
E E ,
- (rp,,- (r)
2 2log(8/8)
2RH
N
with probability at least 1 1- 5/8. Applying union bound over all f E J and क E IT since स5 e TI for every ht [T] x [H], it holds that
(f: Pf: < 2RH $2RH 2H log(8) (|(00)
HT log Fl/6)
< 4RH
(13)
N
N
for every f E F, with probability least 1 5/8.
24

---

Published as a conference paper at ICLR 2025
On the other hand, the second term in 12 is bounded by
Pff: E(fiP" FA)
H
H Σ (P' - P) (5)
Σ P - P) o (5h al)
-
h=1
H
H
< ruy
(p* - (J) o oTh c
+ Rngingss
(P* - PP)- (h) (k)
h=1
h=1
(P -f <h)(sh
H
S 2RE
Σ
pt Sus
an) an) - -P(- sn anill]
|| PM( sh,
sh, an) P(. sn an))l.]
2R
B Be
where the first inequality holds since have ||a] |a|| S bj for all a, E R, and the third inequality holds due to Hölder's inequality with the fact that Il o wil S R. Furthermore, Lemma E.3 implies
-(): A) S 2R
Σ
E E an Joff PM sn, on) P(: sh
(olssann)ll an)l]]]
H
pay (pr(-1sh,a0 sh, ah) - P(- s/. an) [1]]
< 2R
E Js
h=
< 2RHeep(8/8
(14)
with probability at least 1 1-8/1 6/8. Taking union bound of the two event [3 and (4). with probability at least 1 - 6/4, it holds that
HT (Tlog(8)F1/0)
- E(F:P" 2RH
2RHer(5/8)
N
for every f F.
Finally, we conclude the proof by combining the bounds in Step 1 and Step 2. With probability at least 1 -5/2, for every E F, it hols that
C Pf: Si (f:))
H
B(sn.an) [In o mt. (sh) fn(sh, an)
Σ E Ein [In (h()) fn (sh, (s))))a))
E (f: (.P)) - E(J;P" ,))
1ogg(8HFF/) + +2RH
HT log (og((1)1)
4RH
+ 2RHcc(6/8))
N
(7Tlog(8H
&RR
(BRHep(8/8).
D.2 POLICY UPDATE
The analysis of the policy update step in Algorithm
2 follows the argument in Lemma C.5
25

---

Published as a conference paper at ICLR 2025
Lemma D.3. For any sequence of functions {f the policy update (Line 7) in Algorithu guarantees that
T
log |A|
Σ
(8)) - (VTr & RH
2T
where 1² = go Le. ()) (1( P* T Tht1)s, a) for all [H] and (8, a) S A.
Proof. Since we have the Bellman equation fg = + (fh Th41) for all h [H]. we can apply the performance difference lemma (Lemma
obtain
T H >E
(s1) - (
B
[sh(sn: (. (n)) - - [s,)))
Rearranging the inner product term, we see that
(n )) ( ( |s}
(nfi(sh, )), (: 1. (- 8)} + (), ( 8) ml( (.(1)))
$ (nfi(snn m. 8) ( 8)) + [ (sh, 11 || s) o [+])]]
(nfi(ssh m) () (- s))
nR ( s) - (. ||)s
(15)
where we use Hölder's inequality with the fact that 11 S R. Now recall that the policy update step in Algorithm] 3 leads to
++1 (. Th
(x) Th( 8) exp (nfh(s;)))
where (s) EnEd T/. (a 8) (s) exp (nfh (s) a)). Using the relationship ( a) = log 2 (s) + log m/ 2+1 (a log (a s), it holds that
(nfi(sh, 1). m.
Th x+1 s))
-llog (s) + log n
1+1 (- 8) log o/(( 8), (: 8) - x 1. 8))
(log n ++1 (-18) log ( 8), x 8) - - x. 8))
(log - (-)s) log ( s), (:1 s)) - DKI. (T/+1(( (.1 8) [ (s)
mf s)
+ log m/( [8)
(log T/(- 8)
T/( 8) ( [s)) DRL (at (zft1( (-1)((1s)l s) s))
DKL. ( s) [ (- s)) - DxL. (m/(-) [s)] (-1s)) Dxr. (5/ s)] s))
s DKL ( s) | s)) DEL (# [)]| s1 (- ss) | (s) . s)
where the second equality holds since Z (s) is constant given s, and the last inequality holds due to Pinsker's inequality. Combining this bound with (15), obtain
26

---

Published as a conference paper at ICLR 2025
1 - m/(- (1)))))
(Der (+ () 8)) Dxr. (TT(( |)|l= (.1 8)))
nR [ t/ (- || 8) - - (. [0]l
T
$ Σ
(Ke (- 8) (1))) - Dxx (Th(- s>)| ++1 (.1 [|)))) + Σ
2
t=1
t=1
DEL (17( (- 8)) DKL (w7(( T (. $)) + R2
1/2 RTT
S log |A|
where the first inequality holds since Vz E Rar - =22/2 a²/2, and the second inequality holds due to the fact that n = Un) Finally, setting 1) /
22og IAI RT
we have
T
H (sh. ). |ss) - ( snn)
1,pt
V.
B
1=1
E
Σ (J (, ), (n)) - T sn.)
H
log |A|
RReTT
Tlog |A
+
RH
1
2
2
Am
Finally, we prove Theorem 4.1
Proof of Theorem 4.1 For simplicity, we write rf = - i.e. (s, (s,
-
(s, a) for all (s, E S x and h E [H]. The condition rf E R not required; we only
rely on the boundedness || < R for all h. which Assumption 3 guaaanntess.
Condition on the events in Lemma F.2 (with 8' = 8/2) and Lemma D.I which hold simultaneously with probability at least Consider the following sub-optimality decomposition at step
VT
Va
VI,T" - VT,F7 VI
Vi
Vi - VT,"" + VI - V/
V TTr--p -
(I) MI..E Festimatton
+ Vi
T_pppp ppp Vir
V
+ Vit + Vi VR
Optimization error
+
V
V
(16)
(III Policy update regret
where we omit the initial state for simplicity.
27

---

Published as a conference paper at ICLR 2025
Bounding (I).
Using Lemma E.2 the MLE estimation error is bounded by:
()) VT. - Vi, -
B [r' ( -(())
- (+))
r (+))
S V (5/2)
Bounding (I..
We can relate the terms Vx Vi - 1, to the trajectory-pair & loss E(f, p=, ,))
VH
By Assumption
we have that
V 1f V4 1,
= Eeanar [f(TO) -(())-((T)))))) (()) +
S CIREEO,TIOO [|p(T9) ----())(---))))) (())))
CTRREOOT'' [1 [r)
=CREE(f: ,P S :
where the last incquality holds since E(f: P f) is non non-negative and À 2 CTR- Further, Lemma D.1 and Lemma E.1 implies
H
XE(f'
A) S
Σ
E (s Oh% (h() - Q (sh. and + >X(Q""; PP*,
"1
Σ aa (5h o (sh) - fh [n)] + 2Capprox
h=1
V
Vi + +E(Q""; ;P - (vT - Vt.,. ) + 2Eapproz.
On the other hand, note that
H
(T) =
(QT+4 Q (Sh, at) -P o (onn))
h=1
Q (s);an) an) p P'Vitt(shsaai
h=l
Σ h=1
(sp: an) = (T)
for any T = ($1,a1..... sH, 0H), i.e. px p. Q+ = rr. Thus, we have
XE(Q"";P) PMP A ((((((()-r((())))) ((())
x E (ronnry
[1( r ((()) s (6/2)
where the inequality follows from Lemma E.2 Combining the results, we obtain
(I) = (ViT - Vi..prr) (VirL- - ViJ.. + (vTTL- Vi,
S XE(Q""; ;P*,f) 2eapprox Xer (6/2) 2eapproz
28

---

Published as a conference paper at ICLR 2025
Bounding Sub-optimality. on (I) and (II) into (16.. we have
Finally, we bound the sub-optimality VT,-- VT..-. Putting the bounds
VT,-- VI
$ (5/2), + Xe, (8/2) + 2e approo + VT, Vi.
Since Algorithm returns the mixture policy म = + E{= T²,, the sub-optimality is VT, V1,
+ Σt=
V
Vi,""
Using the bounds we derived and Lemma D.3 holds that
1,p+
Viyn
T
T Σ
-1.-- ViTrm
2,r-
T
(TREx(6/2) + (c,(6 + Zeapproz +
2
V
1,7
T
[=1
log AA
(8/))))(/22) + (c/2 + 2capproz + RH
2T
R2H log( (R|/5)
H3T log( H F|
log H(18/))
log |A|
0
CTR
+ RV
RH
+ RH
M
N
N
R:2 log (R|/0)
max HT Hog H F1/8), log (
log [A]
0
CIR
+ RH
RH
M
N
T
E SUPPORTING LEMMAS
Lemma E.1 (Performance Difference Lemma (Kakade & Langford 2002)) Let P be any transition probability, and denote the corresponding value function by V. Let n. pi be any policies. For any reward r, we have that
(s1) V (s))
Σ E Bgn (0 ), 88)) |((1sn))
Proof. Recursively applying the Bellman equation, obtain
Vi, (81) Vi Ex(r(s1, Vg, E. [VV,
[x - (1) [x
(s, - (s, - V2. (2))
E= ). (( (1) #(- 81)) F. (22, (82))
Σ
Esanay [12h, (sh, T. 84) #(. sw)))]
h=1
Lemma E.2 (Lemma
Zhan et al. (2024a)). With probability least we huve
C 2 H log (R|/5") = 27))
Eo [[(((7)) -(77)) (r*(7))
-
M
29

---

Published as a conference paper at ICLR 2025
Lemma E.3 (Lemma 3 in Zhan et al. (2024a)).
With probability least 1 - for all h E [H],
holds that
(- 8h. an 11
C2 log H|P1/8') 26(
I (en.oon (ayd
Pa 8h: an.)
N
where 02 is an absolute constant.
Lemma E.4 (Lemma 15 in Song et al. 2023 ). Fix any B O, E (0. and assume we have a
class of real-valued functions H. X 1 B, B). Suppose have K i.i.d. samples { yk )1)) k= where 2& and yk h (zx)) + EN where h" E H and {e*)k_
independent random variables such that ElEk I&] = Additionally, suppose that max; 19 S and supzex [h((x)) S B.
(((())))-a)))))) Then, with probability at least 1 -- the least square estimator h E arg min Eke (h( - y satisfies:
Ezap (h(x) n((z))
C₂ log( (H1/0)
S
K
where Co an absolute constant.
Algorithm 4 APPO (Practical version)
Input: Batch size Learning rates Csg Ctg, ag. constants À
0, T E (0,
2: Train reward model f based on Preef
> Use any reward learning method
3: for step= 1, 1,2.... do
4: Sample mini-batch of transition tuples Bug and trajectory pairs Bunj from Drraj
5: Train Q functions of +- oe 0tp V L2. (Bups Bmn) for i E (1,2) (6)
6:
Update target Q function Ø' (1 T) + T for E {1,2]
7: Train V function vb &- vb a V (Bmp)) (Bmp) 7
8: Train actor < 0 + cup V Co (Bmp)
9: end for
30

---

Published as a conference paper at ICLR 2025
F ADDITIONAL EXPERIMENTS
F.1 EVALUATION ON THE META- WORLD MEDIUM-EXPERS DATASET
To further assess the generalization capability of APPO, we collected the Meta-World me-peere dataset following the data collection procedures outlined in prior works (Hejnal & Sadigh 2024 Choi et al. 2024j. Detailed information on the dataset is provided in Section G For comparison, use MR, the most effective baseline method identified in Table The results in Table 2 show that APPO consistently outperforms or matches MR.
# of feedback
500
1000
Dataset
dial-turn
sweep-into
dial-turn
sweep-into
MR APPO
15.80
14.3213.39
16.08
8.48+1.92 14.56-6.25
32.40+13.66
12.80
39.20
Table 2: Success rates Meta- World medium expert samples, averaged over 5 random seeds.
medpertexpert dataset with 500, 1000 preference feedback
F.2
EFFECT OF DATASET SIZE
dial-turn
sweep-into
100
100
80
80
Success Rate(%)
Success Rate(%)
60
60
0.5
1.0
2.0
3.0
0.5
15 Dataset Size (x1e5)
1.0
2.0
Dataset Size (xle5)
APPO
MR
Figure 3: Success rates of APPO and MR evaluated in Meta-Wan World medium podiumm-eet cannrlllyy datasets, with varying dataset sizes. The number of preference feedback samples is fixed at 1000.
To examine the impact of dataset size |Dwajl- we conducted experiments with varying sizes of the Meta- World medium-replay datasets. As shown in Figure 3] the performance of MR fluctuates with changes dataset size, whereas the performance of APPO exhibits more consistent and grad- ual response to dataset size variations.
F.3 LEARNING CURVES FROM EXPERIMENTS.
Figure and Figure show the learning curves of the experiments in Table | and Table Each algorithm is trained for 250,000 gradient steps, with evaluations conducted every 5,000 steps. The success rates from the final five evaluation points averaged and reported in Table I and Table 2
31

---

Published as a conference paper at ICLR 2025
Dataset
BPT
box-close
dial-turn
sweep
BPT-wall
sweep-into
drawer-open
lever-pull
Size (x10")
1.0
8.0
3.0
7.0
1.5
1.0
1.0
3.0
Table 3:
The sizes of Meta- World medi um- um-replay datasets BPT indicates button-press-topdoon.
(Choi al.
2024
The abbreviation
G EXPERIMENTAL DETAILS
G.1 DATASETS
The Meta- World medium-repla ay dataset from Choi et al. (2024) consists of replay buffers gener- ated by SAC (Haarnoja et 2018) agents with an approximate success rate of 50%. The dataset
sizes detailed in Table 3
The Meta- World medium eeepperr dataset was collected following the procedures described in prior works (Hejna & Sadigh 2024 Choi et al.] 2024). Each dataset contains trajectories from five sources: (1) an expert policy, (2) expert policies for randomized variants and goals of the task, (3) expert policies for different tasks, (4) random policy, and (5) e-greedy expert policy that takes greedy actions with a 50% probability. These trajectories are included in the dataset in propor- tions of 2: 4 respectively. Additionally, standard Gaussian noise added the actions of each policy. The dataset sizes match those of the medium-2e -repllayy dataset.
G.2 IMPLEMENTATION AND HYPERPARAMETERS.
For fair comparison with baseline methods, we train the reward model and MR following the offi- cial implementation of Choi al. (024). The reward model is implemented by an ensemble model of three fully connected neural networks with three hidden layers, each containing 128 neurons. For critics (Q and V) and policies,
fully connected neural networks with three hidden layers of 256 neurons each. Other hyperparameters are listed in Table 4 We find that using a lower learning rate for æ and softer target network updates improves the stability of APPO training. Experiments were conducted on an Intel Xeon Gold 6226R CPU and an Nvidia GeForce RTX 3090 GPU. Each training session consists 250.000 gradient steps, taking approximately 3-4 hours to complete. Our code is available at httph::t:///gt gtttp:://github com/ oh 1ab/ APPO. git
32

---

Published as a conference paper at ICLR 2025
Algorithm
Component
Value
Neural networks
3-layers, hidden dimension 128
Activation
ReLU for hidden activations, Tanh for final activation Adam (Kingma & Ba. 2015 with learning rate le-3
Optimizer
Reward model
Batch size
512
Epochs
300
Ensembles
3
Neural networks (Q, V, m)
3-layers, hidden dimension 256
Activaton
ReLU hidden activations
Q. V. optimizer
Adam with learning rate 3e-4
Batch size
256
MR
Target network soft update
0.005
(IQL advantage weight)
3.0
7 (IQL expectile parameter)
0.7
discount factor
0.99
Neural networks (Q, V, m)
3-layers, hidden dimension 256 LeakyReLU for hidden activations
Activaton
Q.V, optimizer
Adam with learning rate 3e-4
APPO
optimizer
Adam with learning rate 3e-5
Batch size
256 transitions and 16 trajectory pairs
Table Implementation details and hyperparameters. For the reward model and MR algorithm, Target network soft update
0.001
discount factor
0.99
follow the official implementation of Choi et al. (2024).
33

---

Published as a conference paper at ICLR 2025
preze topdown
SPICOO
500
500
Succea Taleri2
60-
28
Thaming Size
Tuaring 50PP
Tranein Skep
Teinnn Skap
1000
1000
1000
1000
Succea RutuT
28-
20-
Taal S0MP
Traiiingg
Taining Ship
lever-pull 500
500
900
500
60-
Saccaa fatrr2
2.5
06
25
Trakking Seap
Tall
Traiding
Thaliing Soup
1000
1000
2000
1000
2.
40
65
Wainnn
APRO tound
MR
DRPO
IPL
Figure 4: Learning Curves from the experiments in Table
34

---

Published as a conference paper at ICLR 2025
dial-turn 500
sweep-into
500
100
80
Success Rater%0
Success Rate!%)
60-
Training Step
1.6
Training
1000
102
80-
Success Rate!
Success Rate!S)
40
0.0
1.0
1.5
2.0
0.0
0.5
25
Training Stop
Trining Stop
APPO (ours)
MR
Figure Learning Curves from the experiments in Table 2
35


Reviews:
[{"review_id": "I6kkq79zZZ", "reviewer": "Reviewer_DhLA", "summary": "This paper introduces APPO, a novel algorithm for offline PbRL that utilizes a two-player game formulation to produce a robust policy less prone to model errors. By avoiding explicit confidence sets, APPO achieves computational and statistical efficiency. The paper derives a sample complexity bound for APPO under standard assumptions and presents experimental results demonstrating performance comparable to SOTA offline PbRL methods on continuous control tasks.", "questions": "1. The paper only evaluates APPO on a medium-replay dataset from Metaworld. It would be beneficial to evaluate APPO on a wider range of datasets to assess its generalizability and robustness.\n\n2. Previous work on offline PbRL, such as CPL [1], directly learns a policy without RL, as noted in the related work section. Using a supervised learning approach, CPL achieves comparable performance with SOTA baselines while significantly reducing computational complexity. How does APPO compare to CPL, and what are the advantages of using APPO over CPL?\n\n3. Could the authors discuss the limitations of APPO?\n\n[1] Joey Hejna, Rafael Rafailov, Harshit Sikchi, Chelsea Finn, Scott Niekum, W. Bradley Knox, and Dorsa Sadigh. Contrastive preference learning: Learning from human feedback without reinforcement learning. In The Twelfth International Conference on Learning Representations, 2024.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper is well-motivated and organized. The proposed approach is theoretically sound and solid. The authors derive sample complexity bounds without relying on explicit confidence sets, offering statistical efficiency and practical applicability. The approach is evaluated on continuous control tasks, with results showing that it performs on par with or surpasses SOTA baselines.", "weaknesses": "Please see Questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0eiM4KvZUx", "reviewer": "Reviewer_bKme", "summary": "This paper studies offline PbRL. The authors propose APPO, which frames PbRL as a two-player game between the policy and an adversarial reward model. This algorithm enforces pessimism without explicit confidence sets, making the method more computationally tractable than the existing literature. The paper further provides theoretical guarantees, demonstrating that APPO achieves strong sample complexity bounds under standard assumptions on function approximation and trajectory concentrability. Experimental results on continuous control tasks (in Meta-world) show that APPO achieves performance comparable to state-of-the-art methods.", "questions": "1. The authors claim that using Lagrangian multipliers to get rid of the confidence sets is not applicable here (Line 204-207). I am not quite convinced because such an approach is effective in standard RL and I hope the authors can elaborate more.\n\n\n2. For Algorithm 2, can we just replace the true environment in Algorithm 1 with the estimated environment $\\widehat{P}$ (adding some regularizers to quantify the uncertainty of $\\widehat{P}$ at the same time)? Then the resulted algorithm could be less complicated.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Algorithmic novelty: The Q function estimation part in Algorithm 2 is interesting and novel.\n\n2. Valid theoretical guarantee: The authors provide a rigorous sample complexity analysis under standard assumptions.\n\n3. Qualified empirical performance: The experiments show that the practical implementation of APPO is a competitive empirical algorithm. This part is lacked in many existing works.", "weaknesses": "1. Limited novelty: the essential idea is not very novel. In standard RL, there have been works to use two-player games to get rid of confidence sets (e.g., 'Adversarially Trained Actor Critic for Offline Reinforcement Learning' by Ching-An Cheng) and this work is very similar to this line of work. In addition, the authors should highlight new analysis techniques in the paper, if any.\n\n\n2. Complicated algorithm: although Algorithm 2 doesn't need confidence sets, the algorithm is still not computationally efficient due to Line 4. Typically, most of the existing works think a method computationally efficient if it can be solved with least squares oracles and MLE oracles. However, I think Line 4 in Algorithm 2 cannot be solved with these oracles.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RaRAWnBRCU", "reviewer": "Reviewer_FTyb", "summary": "This work explores the innovative realm of PbRL, addressing the challenges of ensuring conservatism under uncertainty. APPO is designed to ensure conservatism in PbRL without the need for explicit construction of intractable confidence sets. This is achieved by framing PbRL as a two-player game between a policy and a model, which allows for a tractable enforcement of conservatism. Experimental results show that APPO performs comparably to existing state-of-the-art algorithms in continuous control tasks．", "questions": "1.What is the impact of the conservatism regularizer coefficient (λ) on the performance of APPO? How can an appropriate λ value be selected?\n\n2.How does APPO compare to other IQL-based algorithms in terms of hyperparameter tuning advantages and disadvantages?\n\n3.What happens to the performance of APPO if these assumptions do not hold in certain environments?\n\n4.What are the scalability concerns of APPO in high-dimensional state or action spaces? Are there any issues related to computational complexity?\n\n5.In practical applications, how does APPO cope with sparse or non-representative preference data?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "APPO is designed to optimize the learning process in preference-based reinforcement learning (PbRL) by effectively utilizing preference feedback, which allows for faster convergence and improved sample efficiency compared to traditional methods. The proposed method can be integrated with any standard unconstrained reinforcement learning algorithm, making it versatile and applicable across various domains. Additionally, the paper provides theoretical bounds on the sample complexity of the proposed method.", "weaknesses": "The performance of APPO is sensitive to the choice of the conservatism regularizer coefficient (λ). While the algorithm can learn with a range of λ values, improper tuning can lead to suboptimal performance and stability issues, which may require additional effort in hyperparameter optimization. Moreover, the theoretical guarantees of APPO rely on standard assumptions regarding function approximation and bounded trajectory concentrability. If these assumptions do not hold in certain environments, the performance and reliability of the algorithm may be compromised.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wGgux3LBCG", "reviewer": "Reviewer_bzB5", "summary": "The authors propose a novel variant of the two-player formulation of PbRL, that allows the deviation of statistical bounds as well as a computational efficient implementation. The basic element of the proof is a novel sub-optimality decomposition. They also offer implementation details as well as an empirical comparison with other SoTA algorithms.", "questions": "Can you please point me to the description of the size of $D_{traj}$ used in the experiments?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Theoretically sound approaches to PbRL are an important tool for researchers, because they allow conclusions beyond the empirically tested scenarios. Together with the also available empirical evaluation, this work becomes a significant contribution. This is further strengthened by the fact, that the algorithm is competitive to the SoTA. This is not expected for an algorithm derived from an mostly theoretical work.\nThe primary contribution of the work is an original contribution, which is embedded in a established framework.\nQuality and Clarity are also good, with only minor limitations. Especially the formalization/introduction and the embedding into the available, related work are excellent. However, an overview table of related work, showing the available bounds, given assumptions & constraints would strength this further. This would enable the reader to directly pinpoint the variant considered by the authors, wrt. other works.", "weaknesses": "The most substantial weakness, are the repeated references to the appendix. The appendix should not be assumed to be available to every reader. In most cases, the explanations in the main paper are sufficient to follow the work without the appendix, but there are exceptions. E.g. the KL regularizer in alg 1&2 which is only requried for Alg.3, but this is not explained. In general, the authors should ensure that the paper is self contained. Stating a condensed version of what is written in the appendix (like for Theorem 4.1) is a good practice.\n\nFurthermore, there are some strong assumptions, that should be discussed, like the fixed-length requirement or the Markovian reward. Both assumptions are correctly stated, but it is not clear if they are a substantial requirement, or just in place for enabling the formal proof.\n\nAdditionally, the experiments should be extended by additional ablation studies. As example, the impact of smaller/larger D_traj sets would be interesting (independent of the number of preferences). Another improvement would be adding a rank or critical distance plot for table 1, as a direct comparison with the SoTA is inconclusive. However, given that experiments are not the primary scope of the paper, these are only a smaller concerns.\n\nOne small typo: The results of baselines Oracle, PT, DPPO, and IPL are taken from Choi et al. (2024) - \"Oracle\" should likely by \"MR\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)