Efficient Preference-Based Reinforcement Learning: Randomized Exploration meets Experimental Design
Authors: Andreas Schlaginhaufen
Reda Ouhamma
Maryam Kamgarpour
Venue: NeurIPS 2025 poster ()
Keywords: RLHF
Preference learning
RL
Optimal design
Primary area: reinforcement_learning

Abstract: We study reinforcement learning from human feedback in general Markov decision processes, where agents learn from trajectory-level preference comparisons. A central challenge in this setting is to design algorithms that select informative preference queries to identify the underlying reward while ensuring theoretical guarantees. We propose a meta-algorithm based on randomized exploration, which avoids the computational challenges associated with optimistic approaches and remains tractable. We establish both regret and last-iterate guarantees under mild reinforcement learning oracle assumptions. To improve query complexity, we introduce and analyze an improved algorithm that collects batches of trajectory pairs and applies optimal experimental design to select informative comparison queries. The batch structure also enables parallelization of preference queries, which is relevant in practical deployment as feedback can be gathered concurrently. Empirical evaluation confirms that the proposed method is competitive with reward-based reinforcement learning while requiring a small number of preference queries.

Efficient Preference-Based Reinforcement Learning: Randomized Exploration Meets Experimental Design
Andreas Schlaginhaufen' SYCAMORE, EPFL
Reda Ouhamma SYCAMORE, EPFL
Maryam Kamgarpour SYCAMORE, EPFL
Abstract
We study reinforcement learning from human feedback general Markov decision processes, where agents learn from trajectory-level preference comparisons. A central challenge in this setting is to design algorithms that select informative preference queries identify the underlying reward while ensuring theoretical guarantees. We propose a meta-algorithm based on randomized exploration, which avoids the computational challenges associated with optimistic approaches and remains tractable. We establish both regret and last-iterate guarantees under mild reinforcement learning oracle assumptions. To improve query complexity, we introduce and analyze an improved algorithm that collects batches of trajectory pairs and applies optimal experimental design to select informative comparison queries. The batch structure also enables parallelization of preference queries, which relevant in practical deployment as feedback can be gathered concurrently. Empirical evaluation confirms that the proposed method is competitive with reward- based reinforcement learning while requiring a small number of preference queries.
Introduction
Reinforcement learning (RL) is a fundamental paradigm in machine learning, where agents learn to make sequential decisions by interacting with an environment to maximize cumulative rewards Barto 2021]. RL has enabled advances in domains such as game play [Silver et al.) 2017]. robotics Todorov al. 2012). autonomous driving [Lu et al.) 2023). However, the practicality of RL is hindered by the challenge of designing rewards: crafting a reward function that aligns with human objectives is often difficult, and misspecified reward function lead to suboptimal unsafe behavior (Amodei et al., 2016 Hadfield-Menell et al. 2017). This motivates the development of principled alternatives to manual reward design.
Rather than relying on manually specified reward functions, reinforcement learning from human feedback (RLHF) guides learning through preference feedback: at each step, human oracle compares trajectories and indicates which is preferable [Christiano et al.
2017). This preference signal is often
much easier provide than engincering reward function
Percira et al. 2019 Lee al. 2023
RLHF has proven to be effective robotics [Jain et al.
2013
and, more recently, fine-tuning of large
language models (Ziegler et al. 2019 Stiennon al. 2020
Rafailov al. 2023 This highlights
the practical relevance of RLHF compared to soward-based learning.
Despite its empirical success, the theoretical foundations of RLHF are still in development, Existing works first studied the simpler setting of dueling bandits. In this context, the learner selects pairs of actions and observes noisy preference feedback Yuue et al. 2012 Komiyama et al. (015). Clas- sical algorithms for regret minimization this setting include approaches based on zeroth-order
"Correspondence andreas. www.eeas..ccaaiaaaaeeeeea schlaginhaufeeeeppl...
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

optimization (Yue and Joachims 2009] or the principle of optimism [Ailnn et al. 2014]. A key challenge this setting is reducing the number of preference queries. For this purpose, several recent works propose query selection strategies for dueling bandits [Das et al. 2024 Liu et al. 2024 [Shhid ett al. 2024 Mukherjee et al., 2024], often hinging on optimal experimental design mechanisms [Pukelsheim] 2006]. However, such approaches are usually limited to finite-armed bandits, where the resulting optimization problems can be solved efficiently.
In the online RL setting, the theory of RLHF has received increasing attention, with several works establishing either regret or probably approximately correct (PAC) guarantees. PAC-RL methods aim to identify a near-optimal policy with high probability [Xu et al. 2020, Novoseller et al. 2020 approaches provide bounds on the cumulative reward during
Zhu et al. 2023], while regret-
learning Pacchiano et al. 2021 Chen et al. [022] [u and Sun 2023]. Similar to dueling bandits,
a central challenge in RLHF is to actively select informative trajectory comparisons to drive learning.
In RI, however, this active-learning problem presents additional difficulties: First, the learner cannot
freely choose arbitrary state-action pairs or trajectories, but must reach them through exploration [aagnmakerr et al. [022]. Second, many existing approaches with guarantees [Pacchiano et al. [022]]
Zhan et al. 2024 rely on maximizing an exploration bonus involving a norm of state distributions problem which is computationally intractable even in tabular settings (Efroni et al. 2021
To sidestep these challenges, another line of work focuses on RLHF with offline data. In this setting, learning proceeds over a fixed pre-collected dataset of trajectory preferences (Zhu et al.) [202]] Zhan
al. 2023). Although this offline paradigm avoids the need for online exploration and active query selection, it depends critically on having access to sufficiently diverse and informative preference
data priori (Rashidinejad et al., 2021 Xie et al. [021] Zanette et al., [202T] Zanette| (023) a
requirement that can be difficult to meet in practice. Hence, this merely shifts the exploration and
active learning challenges to the data collection phase.
Despite progress on statistical guarantees in RLHF, a central challenge remains open: designing tractable algorithms for active preference query selection that reduce the workload of human annotators. In existing approaches, a human must provide feedback at every round, which is impractical in real-world applications. Our goal in this work to develop RLHF algorithms that are computationally efficient, reduce the demand for human feedback, and actively select informative queries. Some recent work has made progress on computational tractability. For instance, Wu and Sun [2023] propose a randomized exploration algorithm with regret guarantees limited to linear dynamics, Dwaraahhher et al. (2024) show empirically that randomized exploration efficient for fine-tuning of language models. In parallel, Wang et al. [2023) introduce general reduction from RLHF to standard RL and establish PAC-style guarantees under RL oracle access. However, neither approach addresses the open challenges of reducing feedback requirements enabling active query selection.
Contributions In this work, we focus on reinforcement learning from human feedback (RLHF) and develop meta-algorithms that reduce the RL.FF problem to standard RL by leveraging existing RL algorithms as subroutines. Leveraging randomized exploration for tractable and efficient preference query selection, we provide both online algorithms with regret guarantees and preference-free algorithm with PAC-style guarantees under RL-oracle assumptions. Our contributions are as follows:
We propose two meta- algorithgss for RLHF using RL oracles: Algorithm D optimized for regret minimization, and Algorithm 2 which performs preference-free exploration and defers preference collection to single batch at the end. For these methods, we establish regret and PAC-style guarantees, respectively, holding in general MDPs.
We present a second meta-algorithm for regret minimization (Algorithm 3) with better scalability and query efficiency thanks to: Lazy updates, inspired by linear bandits [Abbasi] Yadkori et al. 2011], which enables parallelization of the preference oracle calls; Greedy optimal design, which selects informative preference queries and improves sample efficiency.
We provide empirical results showing that: Our algorithms are implementable, competitive with seward-based RL, and substantially outperform a baseline that relies solely on based exploration; Algorithm 3 achieves comparable performance to Algorithm while significantly reducing the query complexity?
Thh code is openly accessible at /tltttps:://ggieiie httpstttt....//aarrrrrcaaaaaattt
2

---

2 Preliminaries
Notation Let I4 and IR denote the sets of natural and real numbers, respectively. We write ||-I| for the Euclidean norm and (5-)) for the standard inner product in R. Moreover, for a positive definite matrix A E idddd we denote || := v (x, Ax) for the Mahalanobis norm. Furthermore, we denote the closed Euclidean ball of radius a > 0 by (a) C IR and for a compact subset X' R", we denote the set of all probability measures supported on X' by Ax. Finally, we use the standard notation (n) and (n) for asymptotic upper and lower bounds, as well as O(n) Onn polylog(n)) for suppressing polylogarithmic terms.
Setting We consider an infinite-horizon Markov decision process (MDP) M (8. A, with state and action spaces S S RR" and A C RR", respectively, initial state distribution 80 ~ Vo- transition law 1 P(-[sh (i.). and discount rate re- re-(s, (s. (0* 6(s a)), where ||0*]| s B and ø S x A - I is continuous feature mapping such that max || (0(s. s, a)]l I L. We denote the set of all trajectories as T := (S x A) and the distribution over T induced by stationary Markov policy π S A P For trajectory
(0, 1). We assume linear reward model
T = (so, dp, 81,-8 E 'T we denote the discounted sum features by o(7) == En=p 7 n ""hs, an) and the feature expectation of policy ı by Φ(xr) ETTP, (Ø(T). Furthermore, given reward parameter 0, we denote the value of a policy т by VJ := ETWP, 1 re an) (0, d(T)) and the optimal value by Vi =- max; V/¹
T Interaction protocol For each round I - ,, of RLHE, learner, the MDP, and preference oracle interact as follows. The learner selects two policies ग. and zí. and executes them to obtain two trajectories ~ PT, and T/ ~ Pa.-- Subsequently, the learner may query the preference oracle, which returns a binary label yr = 1 (Te T E 1). The label equals one if the trajectory тę is preferred over T/, denoted as T: T/. and zero otherwise. Each such interaction one RLHF round.
Preference model We consider a stochastic preference model characterized by a preference function P: T > [0, 1], assigning to each pair of trajectories 7, r' E TT the probability P(r r') of preferring T to r'. We make the following assumption about the preference model.
Assumption 2.1 (Bradley-Terry model). The preference function P satisfies for all T, E T
P(r 7') = (10", -
where (x) ee denotes the sigmoid function.
This preference model is a special case of the Plackett-Luce model Plackettt 1975 Luce et al. 1959
and is commonly used in the dueling bandit setting as well as the RLHF framework Yue et al. 2012
Christiano et al. 2017 Ouyang et al. 2022). It captures that the probability of preferring T over 7 is increasing the difference between their values (0", (()) ())(((())7)))))
Remark 2.2. In practice, we cannot compare trajectories of infinite length. Fortunately, many environments terminate in finite time, and otherwise one may truncate each trajectory at horizon
H = Olog, (s)), introducing at most an E error in value estimates (see e.g. [Schlaginhaufen and Kamgarpour 2024 For simplicity, however, omit this truncation step our presentation.
Regret To assess the learner's online performance, we consider the cumulative regret
R(T) Σ
T
(V=-
TiTH (Vz.
1
2V V
V
Cumulative regret has been widely adopted in the RL and RLHF literature [Abbasi- Yabaaii-Yddkori et al. 2011, Zanette et al., (2020) Wang et al.) 2023 Zhan et al. 2024). However, cumulative regret doesn'i 't provide us with a guarantee of the last iterate's suboptimality. As second metric, we therefore also consider the suboptimality of an output policy.
Our results extend directly the finite-horizon setting well.
3

---

Suboptimality The suboptimality of an output policy á is defined by SubOpt( = Vg- V
Suboptimality has previously been considered performance metric for offline RLHF [Zhu et al. 2023]. contextual bandits (Das et al. [024], and online RLHP [Wang et al. [023]. In the following.
propose meta-algorithm that features two variants: with theoretical guarantees cumulative regret, and another specifically ensuring a bound on last-iterate suboptimality.
Randomized Preference Optimization
3.1
Algorithm
Both algorithms share the same key ingredients: (i) estimating the reward parameter from preference feedback using maximum likelihood estimation, (ii) sampling reward parameters from a Gaussian distribution, reminiscent of linear Thompson sampling [Abeille and Lazaric 2017], and (iii) lever- aging an RL oracle to find an approximately optimal policy for the sampled reward parameter. In Algorithm ! apply these steps iteratively and, at each round, query the preference oracle by comparing a trajectory from the new policy to one from the previous policy to minimize regret. In contrast, Algorithm 2 performs preference-free exploration and defers all preference queries to single batch at the end.
Maximum likelihood estimation Considering preference model (T. standard approach for estimating the reward parameter 0* is via maximum likelihood estimation. Given a pair of trajectories
T kSh,k; (h.,k (h, >== and T ks Sh. x) ) we consider the design points 2g ((Tx) <(T()
Σ 7hhh (0(sn,k: k: kn,k) - 06s x)) and the preference labels y/ = 1(Th > =g)) In round t. the preference dataset is D2 {(2,, yk) 1i= and the corresponding (constrained) maximum likelihood
estimator (MLE) is given by 0. arg min |0]| LD, (0), where
LD. (0)
Σ
ly log (10, x)) + (1 y/) log or (-(,
(I,
is the negative log-likelihood of the Bradley-Terry model (1). The loss function (2) is the familiar logistic loss from logistic regression (Shalev-Shwartz and Ben-David 2014). In particular, it is convex problem that can be solved efficiently using standard methods such as LBFGS [Liu and Nocedal 1989]. Moreover, we have the following time-uniform confidence result.
Lemma 3.1. Let A 2 and define the design matrix at time given by V = =1 + Ei=l xaat. Then, with probability 1 for all t E N, the true reward parameter 0 is contained in the ellipsoid
Ed( = 0 0 0. 011. < Bc()) :0
( ())+ (ta²)++a)
Here, = (B)
1/6 (10,2)) denotes the Lipschitz constant of the inverse sig- moid function, and H,, = - -) the effective horizon of the MDP.
The above lemma hinges on a result for likelihood-ratio confidence sets by Lee et al. 2024 The proof and the precise constants are deferred to Appendix [
Remark 3.2. Compared to the standard analysis of stochastic linear bandits Abbasi- Yadkori et al. [2011] our parameter 3, includes an additional factor of /k. which arises naturally due to preference- based feedback. This result improves upon the bound provided by Zhu et al. [2023), which incurs a larger factor of instead of RR. While the v factor can theoretically be avoided by constructing confidence sets using the Hessian of the negative log- ligeliiil LD. [Lee et al. 2024 Das et al. 2024 it reappears in the regret bounds shown in (Das al. 2024). We adopt contidence sets based on V., as this facilitates preference- free exploration, and both V4 and its inverse can be efficiently updated via rank-one operations, unlike Ressian-based approaches.
Randomized exploration Many approaches to regret minimization and pure exploration in RLHF rely on maximizing an exploration bonus of the form [ς(())) <(T v- or
E
[Ø(()) (r")),, Although such methods yield provable guarantees for regret (Pac-
chiano et al. 2021 last-iterate suboptimality (Das et al. 2024), they are computationally intractable

---

To address this, we adopt randomized exploration scheme inspired by Thompson sampling algorithms for linear bandits. In line with and Lazaric [0177] we sample the reward parameter from an inflated version of the confidence set defined in Lemma 3.1 which produces a computationally efficient alternative to optimism optimism-based approaches. Furthermore, we also show that this randomized strategy extends to the pure exploration setting.
in RL settings (see Appendix E.2).
RL oracle With the objective of a meta-algorithm, we assume access to the following RL. oracle.
Assumption 3.3 (PAC-RL oracle). We assume access to an (e, 6)-PA oracle, ARL for the RL problem. That is, polynomial-ting algorithm that produces for every & > 8 E (0, 1), and & Rd
policy A (0, e, 6) such that with probability at least - 8 we have Vg V E.
This assumption of a PAC-RL oracle is satisfied several settings, including tabular and linear MDPs
[Dann al. 2019 Ménard et al. 202 [Al Marjani al.) 202 Wagenmaker et al. 2022
He et al.
2021]. Moreover, is relatively mild compared to stronger oracles considered in the RLH
literature
Ihan et al. 2024 such as reward-free algorithms [Wang et al. 22020] Kaufmann al. 2021 Ménard
ct al. 2021]. In practice, common choices for PAC A are policy optimization methods such as proximal
policy optimization (PPO) (Schulman et al., 2017] soft actor critic (Haarnoja et al. 2018]. J, which
have shown strong empirical performance in continuous control and large-scale applications such as
training large language models.
Algorithm statement Our algorithm randomized preference optimization (RPO) presented below comes in two variants: (i) RPO-Regret (Algorithm[] T which balances exploration and exploitation for regret minimization, and (ii) APO-Explors (Algorithm 2 which performs preference-free frree exploration and collects single batch of preferences at the end. In RPO RPO-Regret, we sample in each round reward parameter from confidence set (see Lemma 3.1 inflated by vd, compute the policy स. via RL oracle, and update the reward estimate by maximum likelihood using the newly collected preference. In contrast, APO-Explors ore samples reward parameters centered at zero, stores trajectory pairs during exploration, and collects a single batch of preferences at the end.
Algorithm 1: S-PO-Regret (online preference learning for regret minimization)
Input: T N, 8 (0, 1), >> 0
Initialize:
L/vT: ; 8' = 8/5: =1= AI; D1 0: 01 and choose To.
2 for t = 1,2, 1. T do
Ó, B(
// Reward sampling
Te A (0), e, 8' (T), T), -
// RL update
Tt Pr:: of ~ Psj
It = (TT)) - o((,)), V = V/2 x
De ( > T!), D++1 Di ((.).
// Preference feedback
0.1 E arg min 5B CD... (0)
// Reward estimation
end
Algorithm 2: RPO Exp-Eoe frreference-free exploration and batched reward estimation)
Input: N, 8 e (0, 1). A 0
Initialize: 1/vT:6 T: 8' = 8/5; V1 = A1; B = D = 0; and choose mi-
for ( 1,2...... do
// Reward sampling
4
Te ARL e0,,,,8'/17 E : = Tt-1
// RL update
~ Pr.; T! C.P.P. Pri
H, T(T,) o(T,), V = V + xT2T
B U ((T,, T(,
// Defer preference feedback
end
foreach (T, x) E B do
10
y = 1(T T'): D = DU ((
// Preference feedback
end
Output: Policy म = APAC (0, (,)
with i E arg min p (D)
// One MLE at end
5

---

3.2 Theoretical results
We analyze the regret Re-RP--eer and the suboptimality of the output policy RPDPP RPO-Explore
3.2.1 Regret analysis
We show that APO-Regres incurs sublinear regret with high probability.
Theorem 3.4. For any d (0, and T E: N, Algorithm 7 satisfies, with probability at least
R(TT) = O
RdPT log(d//00)))
The regret bound of Theorem 3.4 matches the best existing bounds for algorithms with randomized
exploration in reinforcement learning, see [Efroni et al. 2021 Ouhamma et al. [2023] In addition, due to learning from preferences, have an v factor (see Remark 3.2 which is in line with other recent work on RLHF [Wu and Sun 2023 Das et al. 2024
Comparison with prior work For Forepidoii tabular MDPs Pacchiano et al. [021] prove regret bound of (Tdv Similarly, Chen et al. 2022 considers episodic linear MDPs and derives regret bound of O(dvHT), avoiding dependence on by assuming a linear preference model. However, these approaches rely on type of optimism which is computationally intractable this setting (see Appendix E.2) Similar to us. Wu and Sun [2023 avoid this challenge by resorting to randomized exploration and proves (K' regret bound for linear MDPs. Compared to Wu and Sun [0233]. analysis improves the dependence dimensionality from d to d3/2 and avoids the need for truncation techniques on the value function. Furthermore, our settings differ in two key points: First, assume access to RL oracle without restricting the class of MDPs, whereas Wu
and Sun 2023) considers linear MDPs. Second, their approach is model-based, while Algorithm oracle-based and can accommodate both model-based and model-free implementations.
Proof idea The full proof of Theorem 3.4 is provided in Appendix A Analogous to the analysis of linear Thompson sampling [Abeille and Lazaric 2017]. the main idea to control the regret by showing that randomized exploration ensures constant probability of optimism. However, compared the linear bandit analysis, our setting comes with additional challenges: First, due to preference-based learning we require different regret decomposition accounting for the reference policy. Second, as we observe preference feedback on trajectories rather than policies, we need to apply Freedman's 's incquality (see Lemma D.9 to control the deviation between expected and observed features. Lastly, as we assume a PAC RL oracle - in place an exact maximization oracle- we need to carefully track the resulting approximation error.
3.2.2 Suboptimality gap
As RPO- Exploreecolleeeeeeeeeeee no preferences during exploration, it may incur linear regret as the policies TT. can highly suboptimal. However, Theorem 3.5 below shows that the final output policy is -opimaal.
Theorem 3.5. For any (0, and T Algorithm satisfies, with probability least 6.
(v
SubOpt (*) = (+)= kdB log
dT
In other words, we need (kdd /s²) iterations to output s-optimal policy with high probability.
Except for the extra vd dependency, which is inherent to approaches based on randomized explo- ration we match the last iterate guarantee proposed by Das et al. [2024) for a contextual linear bandit setting, but with an algorithm that (i) collects single batch of preferences and (ïi) remains tractable a full RL setting with trajectory-level feedback, given the PAC RL oracle tractable.
'Recently, Abeille al. 2025 showed that, certain cases, the factor vd can removed by an improved analysis. Their assumptions do not hold setting, whether vdl can be avoided remains open.

---

Comparison with prior work Algorithm is reminiscent of reward-free RL algorithms [Wang al. 2020], but in preference- setting. To our knowledge, Algorithm@ iss the first tractable algorithm to perform efficient preference-free free exploration with trajectory-level preferences, and the first across preference- or reward-based RI. to do so via randomized exploration. Few other works provide suboptimality guarantees in preference-basee based RI., but require preference-feedhace at every round. [Wang et al. [0023] propose meta-algorithm interfacing with a PAC-RL oracle that outputs an E-optimal policy after O(k² d /E") queries. A different approach by Zhan et al. [2024]
leverages optimal design to prove bound of ((1S)) I ( but their method relies on
an intractable maximization oracle. In comparison, Algorithm 2 achieves bound of (kd /s2)
improving the dependence on x over both prior results. The extra vd compared to /hhan et al. 2024
expected for randomized (rather than optimistic) exploration [Abeille and Lazarie 2017]. Finally, ly,
note that an online-to-batch conversion yields similar suboptimality bounds for Algorithm but would require preferences at every round [Ménard et al. 2021).
Proof idea The proof of Theorem 3.5 presented in Appendix builds on Das et al. 2024 s
suboptimality analysis for the contextual bandits setting. However, to sidestep the intractability of maximizing exploration bonus over policies, we leverage randomized exploration [Abeille and Lazaric 2017) to ensure a constant probability of optimism. This allows us to derive a bound on output policy's suboptimality that mirrors the regret bound, without needing additional assumptions.
3.3 Practical limitations
While Algorithm| D is tractable and efficient, presents certain limitations. Issuing preference queries at each round (line 7) is impractical, due to the need for continuous feedback, and requesting label for all trajectory pairs can be expensive and inefficient, as many comparisons may be uninformative. Moreover, the large regret of Algorithm 2 may be undesirable for certain applications. The next section introduces a refined regret-minimization algorithm that addresses these issues by decoupling trajectory collection from query selection and querying only the most informative comparisons.
4
A practical algorithm with efficient query selection
We present Algorithm
3 an improved method for preference collection and active query selection.
4.1
Algorithm
As discussed earlier, we design Algorithm 3 by using lazy updates to collect batch of tra- jectory pairs, then applying optimal design to select the informative queries from the batch.
Algorithm 3: LRPO-OD- (lazy randomized preference optimization with optimal design)
Input: T N, 5 E (0. 1), x
1, C 0 1/vT: 8' 8/5: V1 W1 A1; Di D = 00 tatop 1 1; 0,; n/.
Initialize:
2 for mrr==l 1, 2, . T do (1 + C¹) de (Veaop))) then Dopt, 1 = DeOp (D, Viatop We)
if det(
// Optimal design
D. = Dwrop
for (T, 7') E Dop do
D. D, U =() -
// Preferences
end
0, E arg min 1 (D.
// Reward estimation
10
Spop = D=
= n'' AgL (b,,e, 8
end
12
0, Ni kaup Brreon (8 lstop
// Reward sampling
ne AL e
// Update policy with RL
D DU ((T,, T/),, ②(Ti) ) o(T,) with T. P PR., T/ P,
If f tstop, then W441 V, INT, else: W411 W, + xT.e
16 end
7

---

Lazy updates We use an idea from Abbasi- Yadkori et al. [2011] to collect many trajectory pairs without querying the preference oracle. The modification compared to Algorithm | is collecting trajectories without updating the MLE Omo until the information gain, represented by det increases by multiplicative constant; see line 4 of Algorithm 3 We show that this procedure limits the number of batches to (Tog())). In other words, the average (over batches) size given batch is of order (TT / lT)(T)). A key advantage of this lazy update structure is that the preference queries (line 7) can be collected in parallel across all trajectory pairs within a batch. This significantly reduces the workload of the preference oracle, e.g. human annotator, by eliminating the need for round- by-round feedback, and the algorithm no longer pauses at each timestep to wait for preference labels.
To select informative preference queries from the collected trajectories above, we leverage tools from optimal experimental design. Specifically, we apply an approximate D-optimal design criterion to each collected batch of trajectory pairs; see Appendix E.1 for background on D-optimal design. Given the current matrix Vincop and the set candidate trajectory pairs D, we use greedy algorithm to solve the following maximization problem:
D-Optimal design
max log det (nx)
(Vescop +
Σ NzZT ZED
subject to
Σ The FED
1 -
ng E E.N.
Due to the submodularity of the log det function for greater than one, the greedy procedure of Algorithm 4 achieves an (1 1--e--eeppppp //p-xxpprxinnaiionn to the optimal solution; see [Nembauser et al.
1978 Krause et al. 2008 and Appendix E..
Another key feature of Algorithm 4 is its early stopping rule: the while loop terminates early det(V) exceeds the determinant of the naive design W; if this never happens we simply return W. When this early termination is satisfied, Algorithm requires fewer preferences than Algorithm]] [ Since the optimal design maximizes the information gain (as measured by det(V)), this termination condition is expected to be satisfied frequently in practice.
Algorithm 4: Greedy D-Optimal Design
Input: Dataset D. previous design matrix V, current design matrix W including D.
Initialize dataset Dogt =0 /
while de)( dee and [Doyl] < [D] do
(T, TT,'')= arg (r,")))) de + (é(T) <(T'))(((T) )(T'))
V + T. where Φ(T) - ((T'): Dopt Dopt U ((T,T'))
end
Output: (Dopt: V) det 2 de), else (D, W)
4.2
Theoretical result
We now provide our high probability regret bound for Algorithm
Theorem 4.1. Instantiating Algorithm 3 with C > 0 and X 2 1.2, I.2, it holds for any 5 E (0,
and T N, with probability at least - that
R(T) So (V(I+C) log(d
In addition, the number of times the condition of line 4 holds is at most log(1+0) log ( T(2LH Therefore, the size of the batches on average of order Ö(T (d)o())og()))
dA
Compared to Theorem 3.4 the above regret bound increases only by constant factors. Regarding the number of preference queries, Sekhari et al. [2023) shows that at least ?(T)) queries required to achieve O (VT)) regret in the worst case. However, optimal design may lead to significantly fewer queries in favorable instances, as demonstrated in our experiments, while preserving the worst-case guarantees.
Proof idea We briefly outline the main idea of the proof of Theorem 4.1 the full argument
deferred to Appendix C The central observation is that similarly as for the standard lazy update analysis [Abbasi- Yadkori et al. 2011), the regret only increases by constant factor (1 + C*) given that the optimal design subroutine ensures that det Vistop det W taop and [Dopel < [D).
8

---

Experiments
We first validate our theoretical results on regret minimization tabular gridworld environment, where RL oracle assumption provably holds, and then compare Algorithm [ and on more challenging continuous control tasks. The validation of Algorithm is deferred to Appendix
5.1 Tabular environment
consider a x 6 gridworld environment with deterministic transitions and 4 actions (up, down, left, right). The agent starts in the center and re- ceives reward 0.5 if reaches one of two boundary states. The reward features are one-hot features six boundary states including the goal states (see Figure 3 for an illustration the environ- ment). We compare RPO-Regret] (Algorithm [ against an RLHF baseline that explores purely through entropy regularization, using synthetic preferences generated from the ground truth re- ward parameter 0" We compute optimal policies using soft value iteration [Haarnoja et al., [2017]. and to reduce variance in the reward estimate, we sample 100 trajectories from and T.. in each RLHF round.
Intropy Exploration
3P0-Begret
80
Regret
20
200
RLII
Figure 1: (orange, Algorithm| T against a baseline with en- tropy exploration (blue). The solid lines indicate the median and the shaded areas the 0.2 and 0.8 quantiles, across 20 independent runs. The re- gret is computed with respect to the ground truth reward parameter 0"
We compare the regret
Regret
As shown Figure I RPO- Rego-Rerrt consid- erably lower regret with less variance across runs than the baseline. These results underscore that entropy exploration does not necessarily guarantee low regret in MDPs.
5.2 Continuous control
We validate our theoretical results on regret minimization (Theorems 3.4 and 4.1 on the Lsaac-Cartpole-wi environment from Nvidia Isaac Lab [Mittal al. 2023 In this task the goal to balance a pole on a cart by applying left or right forces, preventing the pole from falling. We compare RPO-Regret with its lazy variants (LRPO-Regret) without optimal design and L.-PO-OD-Regret with optimal design). To simulate human preferences, we generate synthetic preferences using the built-in task-specific reward function, which a linear combination of 5 reward
Number of proference quertes
40000
RPO-Rogret
LAPO-Bagret LAPO-DD-Bogret
30000
20000
2-
RPO Begret
10000
LRPO Begret
LRPO-00- APP0-00-Ragret.
10
15
20
0
10
15
20
RLHF stop
RL.FE step
(a)
(b)
Figure 2: Comparison of regret minimization algorithms in terms of (a) the cumulative regret (es- timated from samples against an RL policy trained with 0*) and (b) number of preference queries performed. In particular, we compare RPO-Regret (orange, Algorithm LRPO-Regret (nn-Reggrr]an[IRRPOO0 -0----D-Reeeeellee fer to Algorithm without and with optimal design subroutine. The solid lines indicate the median and the shaded areas the 0.2 and 0.8 quantiles, across 20 independent runs.
with lazy versions L LRPO-Regret annd [RPD CPPP0-DD-Rae -D-RegretRttpoeee
& green). Here,

---

terms (see Appendix F.. Furthermore, we adopt PPO (Schulman et al. 2017| as our RL oracle using 30 PPO steps per iteration of Algorithm andd] Again, we sample 100 trajectories from n. and T in each RLHF round.
Figure 2 shows that for all three algorithms the regret slope flattens after few RLHF rounds, demonstrating sublinear regret and performance competitive with RL using ground truth rewards. Although LRPO-OD-Rest Regret suffers slightly higher regret initially, it quickly reaches the same performance as RPO-Regret and LRPO-Regret, while reducing the number of preference queries considerably. This highlights that, despite theoretical worst-case lower bounds, the number of preference queries can be considerably reduced in practice by selecting informative queries with optimal design. Additional experimental results and further implementation and evaluation details are provided in Appendix F
6 Conclusion
We presented two simple meta-algorithms for reinforcement learning from human feedback (RLHF) that combine an RL oracle and randomized exploration, achieving complementary guarantees: regret bounds for Algorithm and PAC-style guarantees for Algorithm 2 Algorithm 2 to our knowledge, the first tractable method perform preference free exploration with trajectory-level preferences. Building on this framework, we introduced Algorithm 3] practical that combines lazy updates to enable parallelization with optimal design reduce query complexity, while maintaining regret guarantees. Empirically, our approach is competitive with reward- based RL while requiring significantly fewer preference queries. Overall, our contributions advance the state of RLHF by combining strong theoretical guarantees with practical algorithm design, improving efficiency and broadening applicability to real-world scenarios.
algorithm
Our work opens several directions for future research. First, we adopt the Bradley- model for preference generation, which may not fully capture the complexity of real-world human feedback. Extending the framework to richer preference models is an important direction. Second, our approach relies on an RL oracle at every RLHF step. which may computationally demanding. While using a reward- free algorithm as an RL oracle is theoretically efficient, practical RL implementations are typically based on policy optimization, which not a reward-fres -free algorithm, and often entails high sample complexity. Thus, it remains open whether we could require fewer RL oracle calls or whether reward-free oracles can successfully implemented. Finally, our experimental evaluation limited to tabular settings and simple robotic control tasks with synthetic feedback. Assessing performance on more complex tasks and with real human or LLM-generated feedback would offer a stronger test of the method's practical applicability.
Acknowledgments
Andreas Schlaginhaufen is funded by a PhD fellowship from the Swiss Data
Science Center.
References
Yasin Yadkor,, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Marc Abeille and Alessandro Lazaric. Linear Thompson Sampling Revisited. In Aarti Singh and Jerry Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statisties, volume 54 of Proceedings of Machine Learning Research, pages 176-184, PMLR, 20-22 Apr 2017. WRW.htttstt/.... htt.h:tt//pccceedinngg. mlr, ppwss/vv4 va5/////v//ae http/abellllllaaaeaaeeeaaaaaaale html
Mare Abeille, David Janz, and Ciara Pike-Burke. When and why randomised exploration works (in linear bandits). arXiv preprint arXiv:2502.08877, 2025.
Nir Ailon, Zohar Karnin, and Thorsten Joachims. Reducing dueling bandits to cardinal bandits. In International Conference on Machine Learning, pages 856-864, PMLR, 2014.
Aymen Al Marjani, Aurélien Garivier, and Alexandre Proutiere. Navigating to the best policy in markov decision processes. Advances Neural Information Processing Systems, 34:25852-25864, 2021.
10

---

Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané. Concrete problems in safety. arXiv preprint arXiv:1606.06563. 2016.
Peter Auer. Using confidence bounds for exploitation-explraaiin trade-offs. Journal of Machine Learning Research, 397-42.397-42 2002.
Andrew G Barto. Reinforcement learning: An introduction. by richard's sutton. SIAM Rev, 6(2):423, 2021.
Xiaoyu Chen, Han Zhong, Zhuoran Yang, Zhaoran Wang, and Liwei Wang. Human-int Nluman-in-the-llle in--tnn-ttoopppp Provably efficient preference-based reinforcement learning with general function approximation. In International Conference on Machine Learning, pages 3773-3793. PMLR, 2022.
Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane I Legg, and Dario Amodei. Deep reinforcement learning from human preferences. Advances neural information processing systems, 30, 2017.
Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: Towards accountable reinforcement learning. In International Conference on Machine Learning, pages 1507-1516. PMLR, 2019.
Nirjhar Das, Souradip Chakraborty, Aldo Pacchiano, and Sayak Ray Chowdhury. Active preference optimization for sample efficient rlhf. arXiv preprint arXiv:2402. 10500, 2024.
Vikranth Dwaracherla, Seyed Mohammad Asghari, Botao Hao, and Benjamin Van Roy. Efficient exploration for llms. In International Conference on Machine Learning, pages 12215-12227
PMLR, 2024.
Yonathan Efroni, Nadav Merlis, and Shie Mannor. Reinforcement learning with trajectory feedback. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 7288-7295, 2021.
David A Freedman. On tail probabilities for martingales. the Annals of Probability, pages 100-118 18, 1975.
Tuomas Haarnoja, Haoran Tang. Picter Abbeel, and Sergey Levine. Reinforcement learning with deep energy-basee policies. In International conference on machine learning, pages 1352-1361. PMLR, 2017.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International conference machine learning, pages 1861-1870. Pmlr, 2018.
Dylan Hadfield-Menell, Smitha Milli, Pieter Abbeel, Stuart Russell, and Anca Dragan. Inverse reward design. Advances in neural information processing systems, 30, 2017.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Uniform-pac bounds for reinforcement learning with linear function approximation. Advances in Neural Information Processing Systems, 34: 14188-1411 2021.
Ashesh Jain, Brian Wojeik, Thorsten Joachims, and Ashutosh Saxena. Learning trajectory preferences for manipulators via iterative improvement. Advances in neural information processing systems, 26, 2013.
Emilie Kaufmann, Pieme Ménard, Omar Darwiche Domingues, Anders Jonsson, Edouard Leurent, and Michal Valko. Adaptive reward-free exploration. In Algorithmic Learning Theory, pages 865-891, PMLR, 2021.
Jack Kiefer and Jacob Wolfowitz. The equivalence of two extremum problems. Canadian Journal of Mathematics, 12:363-366, 1960.
Junpei Komiyama, Junya Honda, Hisashi Kashima, and Hiroshi Nakagawa. Regret lower bound and optimal algorithm in dueling bandit problem. In Conference on learning theory, pages 1141-1154. PMLR. 2015.
11

---

Andreas Krause, Ajit Singh, and Carlos Guestrin. Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies. Journal of Machine Learning Research, 9(2), 2008
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Junghyun Lee, Se- Young Yun, and Kwang-Sung Jun. unified confidence sequence for generalized linear models, with applications to bandits. Advances in Neural Information Processing Systems, 37:124640-124685, 2024.
Kimin Lee, Hao Liu, Moonkyung Ryu, Olivia Watkins, Yuqing Du, Craig Boutilier, Pieter Abbeel, Mohammad Ghavamzadeh, and Shixiang Shane Gu. Aligning text-to-image models using human feedback. arXiv preprint arXiv:2302.121990 12192, 2023.
Dong C Liu and Jorge Nocedal. On the limited memory bfgs method for large scale optimization. Mathematical programming, 45(1):503-522 1989.
Pangpang Liu, Chengchun Shi, and Will Wei Sun. Dual active learning for reinforcement learning from human feedback. arXiv preprint arXiv:2410.02504, 2024.
Yiren Lu, Justin Fu, George Tucker, Xinlei Pan, Eli Bronstein, Rebecca Roelofs, Benjamin Sapp, Brandyn White, Aleksandra Faust, Shimon Whiteson, et al. Imitation is not enough: Robustifying imitation with reinforcement learning for challenging driving scenarios. In 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 7553-7560, IEEE, 2023.
R Duncan Luce et al. Individual choice behavior, volume 4. Wiley New York, 1959.
Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Emilie Kaufmann, Edouard Leurent, and Michal Valko. Fast active learning for pure exploration in reinforcement learning. In Interna- tional Conference on Machine Learning, pages 7599-7608. PMLR, 2021.
Mayank Mittal, Calvin Yu, Qinxi Yu, Jingzhou Liu, Nikita Rudin, David Hoeller, Jia Lin Yuan, Ritvik Singh, Yunrong Guo, Hammad Mazhar, Ajay Mandlekar, Buck Babich, Gavriel State, Marco Hutter, and Animesh Garg. Orbit: A unified simulation framework for interactive robot learning environments. IEEE Robotics and Automation Letters, 86)):740-37777, 2023, doi: 10.1 10.11999/AA
Subhojyoti Mukherjee, Anusha Lalitha, Kousha Kalantari, Aniket Deshmukh, Ge Liu, Yifei Ma. and Branislav Kveton. Optimal design for human feedback. arXiv preprint arXiv:2404. 13895, 2024.
Mojmir Mutny, Tadeusz Janik, and Andreas Krause. Active exploration via experiment design in markov chains. In International Conference on Artificial Intelligence and Statistics, pages 1349-7374 PMLR, 2023.
George I. Nemhauser, Laurence A Wolsey, and Marshall Fisher. An analysis of approximations for maximizing submodular set functions Mathematical programming, 14:265-295 294, 1978.
Ellen Novoseller, Yibing Wei, Yanan Sui, Yisong Yue, and Joel Burdick. Dueling posterior sampling for preference-based reinforcement learning. In Conference on Uncertainty in Artificial Intelligence, pages 1029-1038. PMLR, 2020.
Reda Ouhamma. Debabrota Basu, and Odalric Maillard. Bilinear exponential family of MDPs: frequentist regret bound with tractable exploration & planning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 9336-9344, 2023.
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 follow instructions with human feedback. Advances in newral information processing systems, 35:27730- 27744, 2022.
Aldo Pacchiano, Aadirupa Saha, and Jonathan Lee. Dueling rl: reinforcement learning with trajectory preferences. arXiv preprint arXiv:2111.04850, 2021.
12

---

Bruno L Pereira, Alberto Ueda, Gustavo Penha, Rodrygo LT Santos, and Nivio Ziviani. Online learning to rank for sequential music recommendation. In Proceedings of the 13th ACM Conference on Recommender Systems, pages 237-245, 2019.
Robin L Plackett. The analysis of permutations. Journal of the Royal Statistical Society Series C: Applied Statistics, 24(2):193225) 202, 1975.
Friedrich Pukelsheim. Optimal design of experiments. SIAM, 2006.
Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. Advances in Neural Information Processing Systems, 36:53728-53777 -3372, 2023.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline rein- forcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems, 34:1 1770221171666 2021.
Tyrrell Rockafellar. Convex analysis, volume 28, Princeton university press, 1997.
Antoine Scheid, Etienne Boursier, Alain Durmus, Michael Jordan, Pierre Ménard, Eric Moulines, and Michal Valko. Optimal design for reward modeling in rlhf. arXiv preprint 1100:52400..7055 2024.
Andreas Schlaginhaufen and Maryam Kamgarpour. Identifiability and generalizability in constrained inverse reinforcement learning. In International Conference on Machine Learning, pages 30224- 30251. PMLR, 2023.
Andreas Schlaginhaufen and Maryam Kamgarpour. Towards the transferability of rewards recovered via regularized inverse reinforcement learning. arXiv preprint arXiv:2406.0179) 2024.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy 2017.
optimization algorithms. arXiv preprint
Ayush Sekhari, Karthik Sridharan, Wen Sun, and Runzhe Wu. Contextual bandits and imitation learming with preference-bee bassd active queries. Advances in Neural Information Processing Systems, 36:1 16.11261-11295, 2023.
Shai Shalev-Shward and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
David Silver, Julian Schritwieser, 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) 2017.
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 procexsing systems, 33:3008-3021, 2020.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model- control. In 2012 IEEE/RSJ international conference on intelligent robots and systems, pages 5026-5033. IEEE, 2012.
Andrew J Wagenmaker, Max Simchowitz, and Kevin Jamieson. Beyond no regret: Instance pac reinforcement learning. Conference on Learning Theory, pages 358 418. PMLR, 2022.
Ruosong Wang, Simon S Du, Lin Yang, and Russ R Salakhutdinov. On reward ffree reinforcement learning with linear function approximation. Advances in neural information processing systems, 33:17816-17826 2020.
Yuanhao Wang, Qinghua Liu, and Chi Jin. Is rlhf more difficult than standard rl? a theoretical perspective. Advances Neural Information Processing Systems, 36:76006-76032, 2023.
Runzhe Wu and Wen Sun. Making with preference-based feedback efficient via randomization. arXiv preprint arXiv:2310.14555 2023.
13

---

Tengyang Xie, Nan Jiang, Huan Wang. Caiming Xiong, and Yu Bai. Policy finetuning: Bridg- ing sample-effiiint offline and online reinforcement learning. Advances neural information processing systems, 34:27395-27407, 2021.
Yichong Xu, Ruosong Wang, Lin Yang. Aarti Singh, and Artur Dubrawski. Preference-based reinforcement learning with finite-time guarantees. Advances in Neural Information Processing Systems, 11118884-18794, 2020.
Yisong Yue and Thorsten Joachims. Interactively optimizing information retrieval systems dueling bandits problem. In Proceedings of the 26th Annual International Conference on Machine Learning, pages 1201-1208, 2009.
Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed dueling bandits problem. Journal of Computer and System Sciences, 7865):133-1155, 2012.
Andrea Zanette. When is realizability sufficient for off-policy reinforcement learning? In Interna- tional Conference on Machine Learning, pages 40637-40666 PMLR, 2023.
Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric Frequentist regret bounds for randomized least-squares value iteration. In International Conference on Artificial Intelligence and Statistics, pages 1954-1964. PMLR, 2020.
Andrea Zanette, Martin Wainwright, and Emma Brunskill. Provable benefits of actor-critic methods for offline reinforcement learning. Advances neural information processing systems, 34:13626- 13640, 2021.
Wenhao Zhan, Masatoshi Uehara, Nathan Kallus, Jason D Lee, and Wen Sun. Provable offline reinforcement learning with human feedback. In ICML 2023 Workshop The Many Facets of Preference-Based Learning, 2023.
Wenhao Zhan, Masatoshi Uehara, Wen Sun, and Jason D Lee. Provable reward-agnostic preference- based reinforcement learning. International Conference on Learning Representations 2024, 2024.
Banghua Zhu, Michael Jordan, and Jiantao Jiao. Principled reinforcement learning with human feedback from pairwise k-wise comparisons. In International Conference Machine Learning, pages 43037-43067. PMLR, 2023.
Yinglun Zhu and Robert Nowak. Efficient active learning with abstention. Advances in Neural Information Processing Systems, 35:35379-35391, 2022.
Daniel M Ziegler, Nisan Stiennon, Jeffrey Wu, Tom B Brown, Alec Radford. Dario Amodei. Paul Christiano, and Geoffrey Irving. Fine-tuning language models from human preferences. arXiv preprint arXiv: 08593, 2019.
14

---

Appendix
Table of Contents
A Proof of Theorem 3.4
16
B Proof of Theorem 3.5
19
Proof Theorem
21
D Technical results
24
D.1 Confidence sequence
24
D.2
Optimism with constant probability
25
D.3
Elliptical potential bounds
26
D44
Miscellancous
28
Discussion background
28
Background optimal experimental design
28
E.2
On the intractability of optimistic approaches
29
F
Experiments
30
Gridworld environment
30
Cartpole environment
30
15

---

A Proof of Theorem 3.4
Theorem 3.4. For any (0,1) and N, Algorithm satisfies, with probability least 6,
R(T) 0 Rd Togglog////0))
Proof. The proof proceeds in four steps. We first define set of good events of concentration of parameters and sums of trajectory features, we show that they are satisfied with high probability. Second, we decompose the regret into two terms: pessimism term and estimation error term. We then show that the pessimism term is controlled by establishing a constant probability of optimism, and the estimation error term is controlled by the estimation error of the maximum likelihood estimator.
Throughout the proof, we work with the two filtrations Ft-1 o II-. and Fl-1 (Fr-1,0 0.). In particular, both O₂ and Vi are Ft-1 measurable. Therefore, O. follows Gaussian distribution given i.e i.e. 0, Fi-1 ~ N(,,, V while it fully determined by Fl-1.
Step I (good events): Recall that in Algorithm we set & = 1/v/T and 8 = 5/5. We define the following high probability events.
1. Let 8" = ellipsoid
8/ and c(8")== = /2d
/2dlog(10dT/8) Consider the inflated
STS 0 E RRd :100 10:1--001 110-b1111 6.112 =Ba(0')((8")
} -c()))))))))))))(( c(8"))
We define the events
E, = {0" E E,(8)))
E. } and E, E, Es
and let G1 == N E... This event implies that H" lies in the confidence set uniformly over times E [1, 7], and the sampled parameter is close to 0..
2. Let G2 denote the event that for
Cr 2 2
1 4T
12 log
4L3H4 1og(2){ )
16LH
2 8
2d
+
log
12)(
VX
it holds that
D E [lo(TT) - +( [r-1] s Cr.
and that
Σ [I(((T)) - -(F))ll, | < Cr.
3. Let A, = { [V2 VT S 8). where ग.. = ARC (0,,e,6' 8T)) and let G3 = n Ar. As shown below, with probability at least 1 - 8, all the above good events happen the same time.
Proposition A.I. Let G = ni= Ge. It holds that Pr [G] 2 8.
Proof. For the event G1, Lemma 3.1 and D.I imply that Pr
U Bg]
8 and Pr[Ef] 8' / for
any [1, T1. Hence, union bound yields Pr [c]] 28'. Furthermore, by Lemma D.4 2). we
have Pr [ s 8'. Moreover, by union bound and the definition of A we have Pr GD $ 8
Hence, we have [G] 2 1 - Pr G
2 1 - 45' 2 1 8.
16

---

Step 2 (regret decomposition): Recall that in algorithm | bound the cumulative regret follows
we choose T.. = T--1- Hence, we can upper
T
R(T)-
= 2
2V
3 0+
t=1
(Vg. Vi
V + V
t=1
Vg-
V
BLH
Let A.( == max, (0, - ((T(().. On the good event G, we can decompose the instantaneous regret as follows
== Via-- V
= Vz. V
V
vo(1)
(vT.
- -V%.)
(Vo
Via1
+
0.
Vo- Vod
| - Vil)
(VoT Viri
+ E +
0.
(0)) (0)
(0.
0+, Φ (tp)
(b(m()) te.
Here, r.S is a pessimism term that is negative by construction for optimistic algorithms, and r-MLE is related to the estimation error of the reward parameter.
Step 3 (bounding r:-5): This part of the analysis highlights the distinctiveness of randomized explo- ration. While optimistic algorithms ensure negativity of r through their intractable optimization procedures, randomized exploration controls it using probability arguments. Specifically, following the proof of Abeille and Lazaric (2017), we begin by bounding r, on the good event via a conditional expectation given the optimism event. The bound on r.S then follows by careful application of the anti-concentration property established in Lemma D.2
Conditioned on Es, we can lower bound
(,
2 min Ae(0) (ax((0,,0T)) o(T()) =: A..
BEET
for some 0, E ETS Moreover, O, = { (.,) 2 ( denotes the event of 0, being optimistic time I, we can upper bound (0") as follows
A,)) < E A.) Fr-1, o.
Putting this together, while keeping track of the events E, and Ar, we have
r! 1(
A,) < E
(A,())) 4.) 1(E, A.) IFr
( E
(10 ((T)) p(+i)) + max ((T) - ((((())
1(E, n Av)
(a)
x ((0, )(T()) - (l., ((T)) - (((iI)) ) 1(E, n AA) Fi-1, 0,
+E
(w0) < 23,,("))c(5"') [|((T)) - ( F E, O2 Pr Σ, F +
where (i) follows from e-optimality of ne, in (ii) we used that max, (L. ((T)) (iii) follows from the Cauchy-Schwan inequality. By the law of total probability, we have that
d(m+)) > and
E [[((m)) ( Fo-1, E., 0.] < [I(((T)) ((ti)ly;- Fr Es / Pr 0. E.
17

---

Next, 00 E & on Eg, we have
Pr Or Fr Es 2 Pr (.().) 2
max (, Fr-1 DEE
Since (,( is the sum a linear function and the function + maxx (0,)()) which convex and continuous by Proposition D.7 Then, applying Lemma D.2 with f(0) A,(0). i 0. Fi-1, and = &t, have
Pr [ F1 Edj 2 1/11/44/ (AVET) = p.
As result, we can upper bound the instantaneous regret as
(F A,) (3,("))((8") [1((T)))))))) - - |r-1
P
28( (ς((T)) (((t))lv.' Fr-1 |
tE,
p
where the second inequality follows from the convexity of norms. Applying Lemma 2)4 we have on the good event that
T
23)("")e(8")
T
[ o(tilly, 1 1 + Te
(3)
(3r(0')c( Cr + Te,
for the constant
Or = 12/
1+ (
(2dlogg
2d
42
12dL' log(2))
log
1+ Tog(2){
4L2112
)
16LH, log
2
dA
Step (bounding MLE); Conditioned event Eg we have
MLE
(0. 0r, ((Te))))))))))) - - x(x())
(0, Úr, ((1)) - ((T()) (0, 0", ((T))) ((T()) (,(8))( c()")) [[((TT) =
$ (((0))((+ c(" E [10(T.) - [F-1]
where the last inequality follows from the convexity of norms. From here, we can again apply the second result of Lemma D.4 We deduce that on the good event G, we have
T
+ MIE < (5 It
Σ
E
1521]
< +
C( CT.
18

---

In summary, we can conclude that with probability at least 1 - 5, the regret can be bounded as follows
R(T) S IT + MIBB +T= BLH,
237(0")((0))
+ (r + c(6")) Cr + 2Te BLH,
3,3 (6')((())))
Cr 2T + BLH,
P
3
V [log (7) + dlog max 4cBLH,1T-1)
+ 22ABB (101)g))
P
2 T 2dlog (1+ 4
12dL2 H2
4L2H3
+ 16LH,
10
(2g log 1+ 1og(2)1
log
dA
8
22T + -LHHH
=0 (Vadee log dl 3
B Proof of Theorem 3.5
Theorem 3.5. For any E 10 and T E N, Algorithm satisfies, with probability at least 5,
(V RRd3
dT
SubOpt (f)
= (R)=
log
In other words, need Okdd// /s²) iterations to output E-optimal policy with high probability.
Proof. Similar the proof of Theorem 4.1 we start by defining a set of good events.
Step 1 (good events): Recall that in Algorithm
ε 1/vT and 8' -0/5: round t,
conditional on Ft-1 = ( T4-1), 11), we sample ~ (O, V with V, A + Σi= x.aa (where IA = ((T)) - ((T()),, and is the MLE estimate at time T + 1 using all the data from round 1 to T. We now define the following high probability events.
1. Let 8 8'/T and c(0") V 22loo(22/00 = v (10dT/))))))) Consider the centered ellipsoid
E = 10 E Rd. 1101vv S c(6"))
We define the events
È = {100 0llvrn & 31+1(8)3. E, {ōr ETS
and let G1 := n== E. n E. This event implies that 0r lies in the confidence ellipsoid (T") and the sampled parameter lies in eTs for all L [1,
2. Let G2 denote the event that for
Cr Cr==2// 22/ (2dlog (1- 4T
dA +
12dLzH2
log
1 (0g(21
4L )) + 16LH
log
2
log(2)A
VX
8'
holds that
[|o(TT)) - ((+()), | CT.
19

---

3. Let A,
V 8.
s se). where n. =
=A Agge (0e,,, and let C3 N Ac.
4. Let G4 denote the event that V V/g I where क APAC (0, E, 6))
Analogously to Proposition A.1 it follows that Pr[G - 28' and Pr[G S 8' for k = 2, 4. Thus, by union bound, the good event G == N G, happens with probability at least 1 6. 6.
Step 2 (suboptimality bound): the following, we will denote x" E arg max, ((T)) for an arbitrary optimal policy corresponding to the ground truth reward parameter 0*, Under the above good event G, we can bound the suboptimality of á as follows
SubOpt(ft = (6" ((x((m)))))))))))()))))))))))( 0(#)) - (0- - 0 0,0((²) x(#); +e
ma - 0, (xx) <(*')) + = Br+1 (8') max [l((T)) ((T'))()) te. (4)
n,
Next, we continue with bounding the term max ((((m) ob (1))|===)) )|vs
Step (approximate G-optimal design): Due to the matrix inequalities Vr+1 2 Vr .... 2 V1, we have
I-llyz Illlyg S... s 11-l, I1-lyy-
Therefore, we can bound the right-hand-side of as follows
max [(((T) ((T ((T'))lVz)
max [(((T) (0 31
max ((((T) ((='0((1)) "1
K,
T
max ((((T) - (=i))l
where we used the triangle inequality in the last step. If it were tractable to compute ne arg max, 1Ø(x) - -(x)()))))))))) - we could invoke Lemma D.4 directly from here. Instead, we leverage randomized exploration to keep our algorithm tractable. In particular, we consider the function f() = max, (8, ((T) Φ(*()), the ellipsoid & = =fo: [ÍÍlv, < =1}. and the event O, (0.) 2 max (0)). By Proposition D.7 ft is convex and continuous. Applying Lemma D.2 with f = f.. = 0, F.-1, and E, it holds that Pr Fi-Il 2p: 1/(4/eT). Hence, we can proceed analogously to the proof of Theorem 3.4
max [0(x) - ((mi))l; 1 EE Ab)
max f(()) BEE.
(Er nA))
f(())) [E n.) 10,
(8,, ((TT)) - o(T))) (F)nAA) 10,, 10, +
S c(
O Oz, t || - o(+()l
(80) c(8")
E [[((TT) - -(ttill | te
p
c(0")
E [[0(TT)) -(())l |F +
Here, (i) follows because &, is centered ellipsoid, and (ii) from the total law of probability.
20

---

Using Lemma D.4 we conclude that with probability 1 - 5, we have that
SubOpt(f)) I s(1 + 23t+1 + (8')1("))(00")
T
[Io(T)) o(T))llV,> Fz-1
E2
p7
SCr
4eBLH
2 2d log (og((0dT//))
log
+ dlogg
max
2VTB
d
VVT
pf
4T
12dL2 log
4L2Hz
16LH.
10
2V1
2V
2d
1+
dA
1og(2)X
1+
Iog(2))
+
log
8
kd T
dT''
3
O
log
Remark B.1 (Connection to G-optimal design). Given subset X' C R G-optimal design selects
Ei...., 2T E X' to minimize max.ex || with V > J..." Under compactness and if (2) Rd, the Kiefer-Wolfowe Wolfowitz theorem Kiefer and Wolfowitz 1960) yields the lower bound x || 2 Vd/T, which is tight up rounding. In the proof above, show that Algorithm guarantees max [|Ø(z)) ((x') (()'))l (d (og(dd/6)///T] Thus, ignoring the noise in o (handled via Freedman) and, for simplicity, the regularization A, Algorithm achieves O
G-optimal design with probability least 1 1-66 8.
C Proof of Theorem 4.1
Theorem 4.1. Instantiating Algorithm with C >> and X 2 4H2,2, holds for any (0, 1) and T e N, with probability at least - that
S C1 (oa+oonoooo((( R(T) S
In addition, the number of times the condition of line 4 holds is at most [+ log 1 Therefore, the size of the batches is average of order ((T/(dlog(TT)
T(2LH,) dA
We start the proof by showing that the number of rounds where the design matrix is updated is small. Lemma C.1 (Number of design matrix updates). Using Algorithm with a parameter >> 0, holds that:
T 1 + v log (1 +
d log 1 T(2LH,)²
dA
That is, the number of updates of the matrix V, is at most logarithmic the number of interactions T.
Proof. Denote Nr = D [Ve+1 * Vi), and let lstop S the last time the matrix V, was updated. Then,
det(Vr) det(V (VeetV))))))) (1+ det(AI).
Here, we used that for two consecutive update rounds lstop 2 (stop we have that det Vi > + (1+C) det Viseop' Then, using the trace-determinant inequality det S (tr(A)/d)*, we have
d (1 (1+C) A dd) (dA+ T(2LH,)) (A+TT(LHH,)
d
and
d log 1 T(2LH,)
Ny S log (1 + CC)
d)
21

---

We now present the proof for the regret bound, which proceeds similarly to that of Theorem 3.4 up some modifications. The first change is in the regret decomposition, which needs to be adapted because we no longer compare to the past policy but rather to मे = _ katop (f): 8). The second change is using Lemma D.5 instead of Lemma D.4 to bound the sum of norms of trajectory features. Finally, the good events defined in the proof of Theorem 3.4 are slightly modified to account for the lazy design matrix and the new choice of comparator policy xtz.
Proof. Let us first define the function Extop N + N. which to a time t. assigns the last time (t) S t that the update condition (line Algorithm 3 was met.
We work with the same two filtrations as before Fi-1 o P2.,, U1...,,,,11,, Vt-1) and Fl_1 o(Fi-1,0)) 0z). And we recall that, given Fi-1, 0, in Algorithm is sampled from N (1)) Peno (1) V (etop(t))
Step (good events): Consider 8' 8/5, we redefine the high-probability events:
1. Let 8 = 8/T and c(8") = /2d log((2/8")) Consider the inflated ellipsoid
ETS (tspp((() (1) = {0 0 E RR -110- mm Venop(()
S (1)
We define the events E, = Eg n Fe, Ex (0 E Emno
E, = 0, E ETS
(t)
and let C1 = T E..
2. Let Cr Cr = 2/ 8(1+ 8) H
log 1
4T12 Ad
16LH
log(2/6), and define G2 as the vX
event under which it holds that
E
F SC,, [ - -6(T;)) ( vitop())
and
T
E
[Kp(TT) - -b(1))l 1- (1)p(1)
1 CT.
3. Let A, = {V:.
{
V/ VT S {) where क. = PAC (0,,,,8//T) and let G3 = - Ac.
We also define the intersection, G Ni=n G., of all good events.
We now compare each of these events to their counterparts in the proof of Theorem33.4 The event G1 is modified because we replace V; by Venap(t) and 0 by @tr. The event G1 still holds with probability at least 1 28' using the same concentration arguments as before. The event G2 is also modified to account for the lazy design matrix, and it holds with probability 8' thanks Lemma D.5 Finally, the event G3 remains unchanged.
We conclude that G happens with probability at least 1 - 8.
22

---

Step 2 (regret decomposition):: Since Algorithm 3 uses a different comparator policy my than Algo-
rithm I
we derive new regret decomposition. On the good event G. have
T
R(T)
= 2
2
V/-
1=1
T
((Vg- Vi=1) + (00 ((TT) -0(T()))
2
1=1
Σ
((V) ) + 100 0(TT) o(Tx)) + (0",)((m)) <(T()))
2
Σ (2(V)- ( + (#* (t))
(t): ((Te)) x(x+)) + (0tn ((T)) -
2 (VV- V + 00 0) Ve
[(((T)) - (((()))
+e
(stap(1) (1)
where the last line follows from the The second term in the decomposition above can be bounded on the good event G as:
inequality and because T|.
APAC (O (t) e, 8).
T
Σ 0 0 @locop(() (1) Vistope1
((x(T)) - d(T()]lv
$ BT
(1o(T)) - - Sxoop
(atop(()
$ BT
8(1 C) 12
where CT 2/
log
4T Ad
16LH, 1og(2/8).
VX
For the first term in the regret decomposition, similarly Appendix A we have that:
Tt Vi-
Viah = A. - (.) + (0. 0r, )(Te)( (((())
MLE
where we recall the gap function (,) max, (0, (x)) ((=1))
Step (bounding r:"): The proof for E. TS proceeds exactly like Appendix A up to Equation B)
this is because the probability of the optimism event O₂ and the events E, and E, is unaffected by the change to the algorithm. Then, we have that:
T
23(("))(("))
T Σ EB -1(()))- - -bti)l F + Te.
TS
We can then conclude, on the good event G, that
RTS (T) < (6)
Cr Te.
P
Step (bounding rt. MLE): This step is analogous to Appendix A We have:
T
MLE < (r(8)(1 + c(8"))
Σ (K((T)) ((T)))lm-
s B c(("))
Σ
B[([@(T+) - (b(())l v 1221)b
s S + c(8"))CT
23

---

where the second inequality follows from the convexity of the norm.
In summary, conclude that with probability least 1 ò, the regret can be bounded follows:
T
R(T) S 2
2 2 -V0 0"
[((TT)) - d(T/))lV; mmop
+
Matop(0
5.0
287 (8'(80)((8")
Br Cr Te.
Cr + +(
P
D Technical results
This section presents the technical results necessary for our theorems' proofs.
D.1 Confidence sequence
The first result a confidence sequence for the maximum likelihood estimation. It is an elliptical relaxation of the likelihood ratio confidence sequence provided in Theorem 3.1 of et al. (202)).
Lemma 3.1. Let X 2 and define the design matrix at time t given by V = AV + > IgZg Then, with probability 1 8. for all t N, the true reward parameter 0 contained in the ellipsoid
(6) = 0 0 0 011(2
- 3.(00)==00 :0(0))=0((1)
-0(x= (11110 ( ())+clogg ('z1))+a)
+ }
Here, K. == max (B), 1/6 (10,z)) denotes the Lipschitz constant of the inverse sig- moid function, and H, = (1-7)-1 the effective horizon of the MDP.
Proof. By first-order Taylor approximation with integral remainder, we have LD. (0*) LD. (0.) + (VLD, (0+), Ôe) +0" -0.) G,( (0) Ôc).
where CD. was defined in Equation (2) and
Ge( / (1 (1- r)
G((E. + +(0" - -ce) xb) )x dr
(1- - () + 7(0- - 6.), xx)) dr xz2
k=1
Rearranging terms gives
(1)
LD, - Lo,
(0.)
2
(0- 0,) TG, - -b,)
t-1
(0 - -0,7
K
ZAZI T
(0+ -0--6,)
k=1
=x 110
0. 11 - -
- ー > 10- 0.
where (i) follows from the first order optimality condition for 0, and (ii) from the lower bound in
(5) Rearranging again and applying Theorem 3.1 by Lee et al. [2024] for likelihood ratio confidence
sequences with the Lipschitz constant of LD, equal to T, = 21. 1), we get
10- - 0.1l" s log
1 -
4eBLH, 1) })
+ log max
+ +4B22
24

---

D.2 Optimism with constant probability
We first recall the following standard concentration and unti-concentration property of the Gaussian distribution.
Lemma D.1 (Appendix A of [Abeille and Lazaric 2017 Let 2 ~ NOO, I) be a d-dimensional Gaussian random vecior. Then, have:
1. Anti-concentration. For any u E (1), we have Pr Pu 2 2 AVer*
2. Concentration: Pr || (2dlog(2d/6) 2 21
The coneentrenntnnnnn property yields the following key result, which is required to prove a constant probability of optimism and subsequently control pessimism terms in the regret. While it has been proven by Abeille and Lazaric [2017] in their linear Thompson sampling analysis, we provide a concise proof based convex analysis for completeness.
Lemma D.2. Let f Rd - I be a continuous and convex function, and consider the ellipsoid 3 = {A E Rd ||0 Bollv I b] for positive definite matrix V and b > 0. If 0 ~ N(o, b
then Pr [(0) maxøes f(0) 1/ (AveT).
Proof. Note that by definition of 0 have Ō Oo bV-1/2,, where ă NNO, I). Hence, considering g(=) flo bV-1/22). have
p Pr [(0) 2 max [()] BE8
Pr [(()) 2 max =EB"(1)
0(2)
where we used that 0g + 1V--V/1//-- E & if and only if z E (1). Since is a continuous convex function, we can choose arg max g(2) such that |>| = By optimality of z holds that
0g(z) S (N)())
(6)
where (1)
denotes the normal cone to (1) at z. While this optimality condition for convex function maximization is somewhat standard (see e.g. [Rockafellar 1997 Theorem 32.4)), we can verify directly that by optimality of z we have
Rd :0 (h, 2), 42 (*()) ( :h
0g(z) = {h Rd g(()) - g()) 2 -2),-2),VV Vz]
S h E Rd g(() - g(3) 2 (h, - V2 B
E) V2 E Bdd (1(1) (B) C h Rd 02 (h,
Since is convex and finite on all of Rd, we have 0g(2) + Therefore, the inclusion (6) implies that
g(ž) 2 g(() + (Aε, - 2) = g( + (2, )) 1), for some À 2 0.
Therefore,
E2 2 implies that g(5) 2 (3), which yields the lower bound
p Pr (g(3) 2 g (( > Pr (r) 21.
In light of Lemma D.I this establishes 2 1/(4VET).
The above Lemma is helpful in the following way: Let H" E, θ No DV- and zō arg max (0, xr) for some bounded subset C Rdd (assuming the maximum exists). the support function of X, i.e. f()) maxxex (0, x). then we have with probability at least 1/ (4 that
max xx) f(0)) < max f(0) < f(ō) (0.zz) zg). 2Ex
Moreover, by part 2. of Lemma D.I. we still have that
0 On
< Ô (Vāb) with high probability.
This idea will be key to the proots of Theorems 3.4
3.5 and
25

---

D.3 Elliptical potential bounds
Another key component the convergence proofs are the following so-called elliptical potential lemmas that provide an upper bound on the sum of norms of sequentially observed vectors in the norm induced by their design matrix.
Lemma D.3 (Lemma 19.4 of Lattimore and Szepesvári 2020 Let (24)121 C RR and for all 1.
||,,1 S L, let V, = AI + >x k=1 R for some À > 0. Then,
TL dd
min 1111 }} 2d 1+
In the analysis of our algorithms, a central challenge is to control the norms of policy feature differences o0 (T)) ((T,). However, the learner only observes the trajectory-level differences It Φ( Tr) - o ). which are random variables with mean ((T,) Φ(x²). To overcome this, we build on Lemma D.3 and introduce new tools bound the sum of norms of policy feature differences.
Lemma D.4 (Ellliptiaal lemma). Lef {x+))21 Rdd be a sequence of random vectors adapted filtration {Fi) and let || S. L almost surely for all t 2 1. Let V₁ = X Σt=) z4z for some À > 0. Then, the following holds:
Deterministic bound. For all T N, almost surely.
I I 2d 1+
TT2
3dL.
log
I,2
dA
A llog
Alog
2) Hlihh-roobbbility bound. For all â E (0, 1), with probability at least 1 - -,
T M Elllaalyy | 2
(1+ TL2
3dl2
1 A log
2dlog
[+
log
1+
d)
A Algg
8L 1og(1/0)-
The first statement is small improvement over Lemma D.3 because involves || instead of
min(1, ||zz li. }} and maintains a similar upper bound. the second statement, { represent trajectory features and their expected values are policy features. Hence, the second statement of the lemma above allows control the elliptical potentials of the policy features while only observing trajectory features.
The proof of this result is based the observation in [Lattimore and Szepesvári 2020 Exercise 19.3]. Namely, the number of times the term || can be larger than
Proof. First statement:
one is at most
3d [og(2]
log(1 + X1oR(2)
Let's define the rounds Tr {1 S T, I| S 1), we have:
xell
Σ | + Σ |2eele.
tT
TETr
3d12 log(1
L A log(2))
min ||a 1
A log(2)
TT
where the first term of the last inequality follows by definition of Tr. The second term follows 3d Tog(2)
log(1 + Xlog(2)) as previously discussed, and because || < L2/X. Then, the proof is concluded by bounding the first sum on the right-hand side using Lemma D.3
because the number of times 1 < f < T not in Tr is at most
26

---

Second statement: The proof proceeds by using Lemma D.9 We have for any d E (0, 1) that with probability 6:
T
T
7L
B Blllaall Il,
1F--1 S
1 v. +
log (1g(1/6)
1=1
8L
- 2
10 Il, 1
log(1/6)
Vx
TL2
3dL2
L log(2
7L
$ 2/7
T
2d log
1+
log
1+
log (1)()
dx
1og(2)A
(og(()))))
VX
where the first inequality uses Lemma D.9 the second uses the Cauchy- Souchy-Schwarz inequality, and the last follows from the first result of the lemma.
We now present variant of the elliptical potential lemma above, adapted for the case where the design matrix is updated with lazy updates and optimal design; see Algorithm333 3 for more details.
Lemma D.5 (Lazy elliptical lemma). Let (24))21 C I2 be sequence of random vectors adapted to a filtration (Fi)e21. with ||2, & L almost surely. Fix 2 L² and C >
Define (V,, 12 as in Algorithm
Vi Wi AI, D1 0, 4stop
* For 1...., T:
-ffdetWW,) > (1 + det(V
* Let Vj = V + ExED,r. xx" T be such that det V 2 det We and (Dopll $ |D].
Set lssap t, D = 1
Observe xa and append D DUU (xe). Update
[V + mtrl W. + sett
ift= Estop: otherwise,
W4+
V4+1 Vz.
Then, the following holds:
1) Deterministic bound. For all T E N.
2(1 + C)
TL2 Ad
log 1
2) High-prooability bound. For fixed T E M and any 8 E (0, 1), with probability at least 8,
2(1 CT L
TL2
8L
EE[l Fe-i] s 2
log 1+
+ log(1/8).
Ad
Proof. First statement: First note that V, 2 AI for all hence ||01 S /2/>. For non-update
steps, t + tstop: have = Wt and dot(W,) < (1 + det(V). Hence, by Lemma D.8
Vo Rd. |, det (V,-
det(W; 1) || w. (1+
(7)
Using the inequality min 2) < 2 log(1 + 2) for = 2 O, we get
min || 1| < (1 + C) min ||,, 11y-1 < 2(1 + log (1 + [[sel((w]))
2(1 + C') log det (W441)
det (W.)
27

---

where the last equality follows from W4+1 We + mart and the matrix determinant lemma (see Abbbasi-Yan Yadkori et al. 2011 Lemma 11]..
For update steps, = hstpp we have by construction det (V,) 2 det(W,) and W4+1 = Vi + Fe0r.
Therefore, with the same reasoning as above,
min || S 2 log (1 ||=elly,-) log det (W++1) det (V))
det (W++1) det (W,)
2 2og
By summing over and telescoping, therefore get det (Wr+1) S 2(1 C)dlog (1 det (W1)
TL
Emin min (1, || S 2(1 + C)) log
Ad
Using that | s (12/A) min |1x |
concludes the proof of the first result.
Second statement: Analogously to Lemma D.4 the second statement follows from the first statement and Lemma D.9
Remark D.6. Note that we have not used the trick from [Lttimore and Szepesvári 2020 Exercise
19.3] in the proof above, as it doesn't trivially extend to our lazy setting.
D.4 Miscellaneous
Proposition D.7. The function f(0) = suPne(A.)) ((T)) is convex and continuous over Idd.
Proof. The function / is the support function of the set Z = (1b(T) n : S - AA]. To prove the convexity, note that for any 17 E (0, 1), we have
f(n0 + - -))" = sup (0, 2) + (1 1) sup (0', 2) - nf (0) + + (1-1)f(0))
sez
Furthermore, any convex function is continuous over the relative interior of its effective domain dom f {x : f(x) 3 (see e.g. [Rockafellar 1997 Theorem 10.1]). Since |s(0)) S |0]| LH this implies that f continuous over Rdd
Lemma D.8 (Lemma 12 of [Abbasi- Yadkori et al. 2011 Let A, B, and C be positive semi-definite matrices such that A B + C. Then, we have that:
xJ Ar
I dct(A)
sup x40
x Bx det(B)
This next lemma is one of the versions of Freedman's incquality [Freedman 1975].
Lemma D.9 (Lemma 2 of Zhu and Nowak 22022)) ) Let (Z))ST be real-valued sequence of random
variables adapted a filtration Fr. 1f0
S 2t
S
B almost surely, then with probability at least 1
T
T
24
E [ze
Fe-1l + 4B log (25-1)
2
1=1
and
E
[ze
Fr
< 2
Σ
+ 8B log (28-1).
1m1
E Discussion and background
E.1 Background on optimal experimental design
Continuous designs Given (possibly infinite) set of features X' Rd, D-optimal design is probability measure &* E Ax maximizing the log-determinant of the (normalized) information
matrix
V(E): / dg(x).
Ex arg max log det V(E), fε
28

---

The equivalence theorem [Kiefer and Wolfowitz 1960 further implies that any D-optimal design also minimizes the G-criterion
arg min max ||= with max | l d.
f
zEλ
REA
Consequently, X is contained the ellipsoid induced by V(E*):
where E(5") == { e R | - sd..
X _ E(5")
This characterization can be interpreted geometrically: E(E is the minimum-volume centered ellipsoid containing N;; see [Lattimore and Szepesváni 2020, Theorem 21.1]. Moreover, although X' may be infinite, D-optimal design can be chosen with finite support, in which case V(S*) >m waZ for some I; E X' and weights wi 2 0. w;
Discrete designs. When budget of samples is available, a (díscrete) D-optimal design may be posed as the allocation problem
max log det
Σ PEX
n2 xxx)
s.t.
nhe E
EN,,
Σ DEA
n1
n,
(n.hee
equivalently as selecting multiset S of size to maximize log deu Exggax)) This is challenging combinatorial optimization problem. However, if X 1 1, the set function
[x(5) = log det A
Σ x.
SCX,
#ES
a non-negative, monotone, and submodular function. Therefore, under cardinality constraint, |S| < n, the standard greedy algorithm achieves (1- s/p)--ppproiiiation guarantee [Nemhauser al. 1978). Hence, Algorithm provides principled way to select informative queries between two consecutive update steps tstop and Estop
E.2 On the intractability of optimistic approaches
Optimism for regret minimization Optimism in the face of uncertainty is a widely used principle for regret minimization in reinforcement learning. In the bandit setting, optimistic algorithms can be applied directly and yield minimax-optimal regret bounds [Auer] 2002]. For regret minimization in RLHF, optimistic algorithm would choose the policy n. maximize the upper confidence bound on the reward difference relative to a comparator policy n/C
74 arg max max V BEE.
arg max VT, 3r ((((T)))) - (+)ilv?
where & is confidence set for 6", This leads the following bound on the instantaneous regret:
VØ- vori
(V
Vir
max max V
V²d ( Vit Vili
V
V.T.
V
Viri
ile
0c
Ø,
| [) - ((T))))) (3,(6') [[((T,) d())) (<m)),))))m)))))))))))))
where 0, E &.. The cumulative regret can then be bounded using standard elliptical potential arguments (see Lemma D.4).
Optimism for preference-free exploration As is evident from the proof of Theorem 3.5 algorithms that solely maximize an exploration bonus of the form
[T²(T) <T)),,, or Erader (ạØ(T) - ~(T')),, ..p 1,
also effective for preference-free exploration.
29

---

Challenge of optimizing the exploration bonus The key problem of the above approaches is that for trajectory-level feedback preferences or reward they lead to optimization problems over policies that cannot be framed in terms of state-action rewards. |Efooi et al. [022] therefore conjecture that exactly solving these problems is intractable even in tabular settings. This stands in contrast to standard reinforcement learning with state-actin feedback, where optimistic algorithms, and
approaches based on optimal design [Wagenmaker et al. 2022 Mutny et al. 2023 involve (or can be reduced to) maximization of bonuses of the form
(s,,))=ue ( - 1,2,
which are linear in the occupancy measure fr and can be maximized via dynamic programming.
These computational challenges associated with exploration under trajectory-leve feedback motivate alternative approaches, such as randomized exploration, which can provide near-optimal theoretical guarantees while remaining computationally tractable.
Experiments
F1 Gridworld environment
As illustrated in Figure 3 below, the gridworld consists of 36 grid cells and the initial state lies in the center. The agent can choose the actions up. down, left, right, and will deterministically move in that direction or stay if it hits boundary. The reward features are one-hot features for the six boundary states in blue, and the ground truth reward is 0.5 for two of these states indicated in Figure 3 Moreover, rewards are discounted with y = 0.9. Our gridworld implementation builds on the code by (Scllaginhaufen and Kamgarpour 2023
0.5
start
Gridworld environment
Figure 3: Illustration of the gridworld environment.
F.2
Cartpole environment
Here, provide additional details for experiments Isaac Lab's Seaac-Carttole-vv environ- ment, as well as experimental results for the pure exploration version of our algorithm.
Isaac Lab's unmodified environment using the default PPO configuration. As reward features, we use the pre-defined reward terms. For cartpole these are: 1) Alive term: equal to for all non-terminal states; 2) Termination term: equal to for terminal states. A state terminal the cart goes out of bounds; 3) Goal tracking term: absolute value of pole angle measured from the upright position; 4) Cart velocity term: absolute value cart velocity; 5) Joint velocity term: absolute value of pole angular velocity. However, our implementation supports any Isaac Lab manager-based tasks.
Implementation details All experiments
We train over RLHF iterations, using steps of PPO at each iteration, and training repeated for 20 independent seeds. For the randomized exploration, we set 3, 0.001 + 0.1 max(1, log and
30

---

A= 1, and for lazy updates we set C = 0.5. At each RLHF iteration we compare 100 independently sampled trajectories. For the maximum likelihood estimation we perform 50 Adam steps (batch size 64, f2 penalty À 10-1). Experiments were executed on single machine equipped with an Intel 19- 14900KS CPU and an NVIDIA RTX 4090 GPU; completing 30 RLHF iterations required approximately 2 50
Preference-free exploration Our results the preference-free exploration algorithm RPO- OPO-Explore are shown in Figure and 5 below. In Figure 4 we see that all three versions of RPO-Explore achieve performance competitive to RL with the ground truth reward but RPO-OD -rxpooe needs the least preference queries. Moreover, in Figure 5 we that the per- formance during training is poor, í.e. the regret large, which is to be expected due to the pure exploration scheme.
122
RZU
LaPO
Flad gneeal tral pouand
1.0
E0C
1%
0.
25-
00
RL bencmaak
00 IVU LJ00
0 10 30
233
25
LAPO-00
BLHF stop
(a)
(b)
Figure 4: Comparison of RLHF algorithms in terms of (a) last iterate ground truth reward V (estimated from samples) and (b) number of preference queries performed. In particular, we compare APO-Explore (green, Algorithm|1 I with its lazy versions LRPO Explore and 1-P00-ODEExpl.oo (orange & blue). Here, LRPO Explore and LRPO-OD- Explore refer Algorithm without and with optimal design subroutine. The error bars indicate the 0.2 and 0.8 quantiles, across 20 independent The dashed blue line indicates the mean reward achieved by PPO with the ground truth parameter 6"
Grozal tack
Iedee R& benotmark
LAPO
LarC-CD
D0
20
BLET drop
Figure 5: Comparing the ground truth rewards V (estimated from samples) of RLHF algorithms
for reward-fiee free exploration during training, using the same color codes as in Figure 4
'Note that the RL baseline makes 24 x 4096 50 = =4'915 queries to the ground truth reward, whereas RPO most 150 binary preference queries.
31

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We provide our theoretical claims in Sections and 4 also provide empirical results Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We address the limitations of our work in Section 6
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
32

---

Justification:
We provide our assumptions in Section 2 and our proofs in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Our experimental environment will be publicly available, and experimental details can be found in Appendix F
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
33

---

Answer: [Yes]
Justification:
We provide the code used for our experiment with the supplementary files.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/
www.SSubbisiooooiiiooooooooo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The details are provided in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Our experiment section provides shaded areas for the standard deviation of the performance curves over 20 independent training runs. Additional details can be found therein.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
34

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: See appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http://aarrr....ccoopa/cccccccca
Answer: [Yes]
Justification:
We don't 't see any conflict with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
We do not foresee any negative societal impact for our algorithms.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
35

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not release models or datasets in this paper.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We citing and crediting the Isaac Lab creators for their RL environment.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
36

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Instructions for reproducing the experiments provided in the readme. Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our research is not involving any experiments with humans.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Our research is not involving any experiments with humans.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
37

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [No]
Justification: We only use LLMs to improve the writing quality.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy for what should or should not be described.
38


Reviews:
[{"review_id": "gvgR1Zl7Wh", "reviewer": "Reviewer_AbWE", "summary": "The paper addresses the problem of preference optimization in reinforcement learning, introducing a meta-algorithm where collecting preferences is an integral part of the learning process. The proposed method, Randomized Preference Optimization (RPO), involves sampling trajectories, collecting preferences over these trajectories, and then sampling reward parameters from a confidence set derived from the gathered preferences. The authors provide regret bounds for the meta-algorithm, assuming access to a PAC-RL algorithm capable of producing approximately optimal policies.\n\nTo reduce annotator burden and latency associated with labeling each trajectory, the paper proposes an extension: Lazy RPO with Optimal Design (LRPO-OD). This variant collects trajectories in batches and consults the oracle only when the information gain (measured by the determinant of the design matrix) increases by a constant factor. Within each batch, a greedy D-optimal design procedure is used to select the most informative trajectory comparisons to query. Theoretical analysis shows that LRPO-OD retains the original regret guarantees (up to constant factors) while significantly reducing the number of required preference queries---only $O(T / \\log T) $ in expectation over $ T $ rounds.\n\nEmpirical results on the Isaac-Cartpole environment demonstrate that both RPO and its lazy variants perform competitively with reward-based RL methods, with LRPO-OD achieving the highest returns while issuing the fewest preference queries.", "questions": "**Relation to existing RLHF work with reward randomization**:  \nSome related work on reward parameter randomization in the context of RLHF is discussed in the weaknesses section. It would be helpful to clarify how this work relates to or differs from prior approaches.\n\n**Experimental details**:  \nAdditional experimental concerns are raised in the weaknesses section.\n\n**Clarifications requested**:\n- What is the motivation for including the case with $\\alpha = 0$ in RPO?\n- From the regret bounds, it appears that both $\\alpha = 0$ and $\\alpha = 1$ result in the same cumulative regret---summing over the sub-optimality term in Theorem 3.5 yields a bound equivalent to Theorem 3.4. Could the authors clarify if there is any practical or theoretical distinction between the two settings?\n- In Algorithm 2, what role does $W_t$ play in tracking $V_t$? An explanation of how $W_t$ helps manage or estimate $V_t$ would be appreciated.", "limitations": "Yes, discussed.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n**Idea and Motivation**:  \nThe paper explores a compelling and timely idea, particularly relevant given the increasing focus on preference-based learning. One of the major bottlenecks in this field is the annotator burden and latency associated with collecting human preferences. The proposed approach directly addresses this challenge, making the contribution both relevant and potentially impactful.\n\n**Writing and Presentation**:  \nThe writing and structure of the paper are strong. Concepts are introduced in a logical sequence, and the overall exposition is clear and accessible---even for readers without a strong theoretical background.\n\n**Theory**:  \nWhile I do not have the theoretical background to verify the correctness or novelty of the formal results, the theorems are well-motivated and clearly explained. The theoretical development appears sound and well-integrated into the broader argument of the paper.\n\n## Weaknesses\n\n**Empirical Experiments**:  \n- The learning curves exhibit large overlapping confidence intervals. Although the intent seems to be showing that preference-based methods can match reward-based RL performance, conducting more trials would increase confidence in the empirical claims.\n- While the experiments support the effectiveness of RPO and LRPO-OD, they do not clearly isolate the benefit of reward parameter randomization. Including a baseline without randomization would help establish the specific advantage of RPO.\n- It is unclear what feature function was used in the experiments---i.e., was $\\phi(s, a)$ based on raw features or learned representations? Clarifying this would", "was_revised": true, "final_justification": "My concerns regarding different parameters and experiments have been well addressed by the authors. I recommend accept.", "rebuttal": ""}, {"review_id": "sl0bTIeDWs", "reviewer": "Reviewer_vHDX", "summary": "This paper proposes efficient RLHF algorithms for general MDPs when learning from preference feedback. First, it proposes a randomized exploration meta‐algorithm that achieves regret guarantees under RL‐oracle assumptions. Second, it proposes another algorithm which proposes a batch of queries at a time to enhance the query efficiency. Experiments show the effectiveness of their algorithms.", "questions": "In what situation will we set $\\alpha=0$ in algorithm 1? It looks like $\\alpha=1$ is strictly better.", "limitations": "The authors discussed the limitations in the paper.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I found the clarity of this paper to be great. It is easy to follow, and all algorithms and theoretical results are well explained. Careful comparisons to existing work are also provided, and thus I appreciate the time the authors spent on writing this.\n\nThe paper proposes two algorithms with theoretical guarantees. Although i didn't checked the proofs in detail, the results look sound. One weakness is that the paper could benefit from a clearer “highlight” of its main novelty. From my understanding, Algorithm 1 extends standard MLE-based RL algorithms to the RLHF setting – Im not trying to diminish this contribution; getting those ideas to work under RLHF is a cool contribution; but its main components (randomization, maintaining the \\$V\\$ matrix, and MLE) all appear in related work (such as those mentioned at the end of page 5), so its technical novelty is somewhat limited, that is, it seems hard to find something super insightful from Algorithm 1. Similarly, while Algorithm 2 is an algorithm of different style, it adapts the determinant‐trick from standard RL to RLHF. However, I acknowledge that such contribution is important and clearly nontrivial, thus I’m leaning toward acceptance.", "was_revised": true, "final_justification": "While many techniques used in this paper originate from prior work on standard RL, adapting them to the RLHF setting may be considered a contribution. That's why I am maintaining my inclination slightly toward acceptance.", "rebuttal": ""}, {"review_id": "mrPcQDROoS", "reviewer": "Reviewer_q874", "summary": "This paper addresses the challenge of designing computationally tractable and query-efficient algorithms for RLHF. The authors propose a meta-algorithm, Randomized Preference Optimization (RPO), which uses randomized exploration (inspired by Thompson sampling) to learn a linear reward model from trajectory preferences. The paper provides both regret and last-iterate (PAC-style) guarantees for RPO under the assumption of access to a PAC-RL oracle. To address practical issues like high query frequency and latency, the authors introduce an improved variant, LRPO-OD, which selects informative query batches, enabling parallelization. The efficacy of these methods is demonstrated theoretically and empirically on a simulated robotics task.", "questions": "1. What was the specific feature mapping used in the Cartpole experiments?\n\n2. What is the computational complexity of the greedy D-optimal design step, and how does it scale with the batch size?\n\n3. Can you discuss the relationship between your work and recent active exploration literature like Dwaracherla et al. (2024)?", "limitations": "The authors discuss several limitations, but the discussion would be stronger if it also acknowledged the challenges of generalizing the proposed sampling method beyond the linear reward model assumption.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper provides a clear framework for RLHF with strong theoretical guarantees (regret and PAC bounds)\n2. The LRPO-OD variant introduces practical variantions (lazy updates and D-optimal design) to enable parallelization, directly addressing a key bottleneck in real-world RLHF.\n\nWeaknesses:\n1. Empirical validation is limited to a single, simple simulated environment, making it difficult to assess real-world performance and scalability.\n2. The framework is confined to a linear reward model and does not address the challenge of generalizing its posterior sampling approach to non-linear settings. It is unclear if the cartpole problem uses neural networks. Clarification on this would be useful.\n 3. The paper doesn't cite recent, very relevant work on active exploration for preference learning (e.g., Dwaracherla et al., 2024: https://arxiv.org/pdf/2402.00396), miscontextualizing its contribution.", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "mlN2Ooy6kz", "reviewer": "Reviewer_Eram", "summary": "This paper studies preference-based reinforcement learning. They consider a MDP with linear reward function, while one can only query preference feed-back. They study two learning criterions: regret and sub-optimality, and propose a meta algorithm with theoretical guarantees. After that, they propose a more practical algorithm with lazy updates. Numerical experiments results are also provided.", "questions": "The optimal dependence on $d$ in regret should be $O(\\sqrt{d})$ (and $O(d)$ in the sample complexity guarantees), at least in linear MDP/bandits setting. Is there any hope to improve the results in this paper?", "limitations": "N.A.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "### Strengths\n\nThe preference-based learning setting is reasonable. The structure of this paper is clear and easy to follow. Numerical experiments are provided.\n\n### Weaknesses\n\n1. Although there are only a few previous work studying preference-based setting, I did not find much technical contribution in this paper. It seems to me most of the results are standard and non-surprising. \n\n2. Another part makes me confused is that how important is the efficiency in learning the transition function. \n\n    I think this paper studies the setting where both transition and reward functions are unknown. However, it seems to me the main theorems about regret and sub-optimality only considered the (sample) efficiency in learning reward function. \n\n    But if this is the case, it seems to me it is unnecessary to assume a PAC-RL oracle, and just assume the transition is known in advance or it has been estimated accurately enough, given that we do not care about the cost in this stage. Or as mentioned by authors in the conclusion, it is enough to just assume a reward-free algorithm as an RL oracle.", "was_revised": false, "final_justification": "", "rebuttal": ""}]

Author rebuttal:

Meta-review: This paper improves query efficiency in RL from preference data by integrating randomized exploration inspired by Thompson sampling with preference-based reward model learning. The work provides theoretical guarantees in regret and last-iterate bounds, and shows empirically that the proposed method is competitive with reward-based RL while requiring significantly fewer queries.

The reviewers initially raised several concerns such as wide confidence intervals, missing baselines and ablations, and novelty with respect to previous work from standard RL and bandits. The authors provided a comprehensive rebuttal (although late) that generally addressed these concerns, including increasing the number of trials to tighten confidence intervals, adding baselines, and testing the algorithm in additional environments. 

The reviewers were largely positive about the paper's clarity, theoretical soundness, and the significance of the problem it addresses. Overall, this paper makes a valuable contribution to an important problem.
Decision: Accept (poster)