A Tighter Bound for Reward Learning in Reinforcement Learning from Human Feedback
Authors: Guoxi Chen
Xing Chen
Bo An
Ya Zhang
Venue: Accepted by TMLR ()

Abstract: As a key component of reinforcement learning from human feedback (RLHF), reward learning directly influences the final learned policy.
Unfortunately, existing theoretical estimation error bounds in reward learning rely on the complexity of the reward function class, unattainable optimal parameters, or non-zero constants independent of sample size, leading to uncomputable bounds that are meaningless for reward function classes with unknown complexity.
To address this issue, 
this paper presents an analysis of parameter estimation for reward learning in RLHF under general function approximation, without imposing restrictions on the complexity of the reward function class.
A tighter bound is provided without non-zero terms independent of the sample size.
The optimal parameters are eliminated by applying linear approximation around the learned parameters. 
Additionally, the relationship between the preference dataset and the learned parameters is further examined to demonstrate how to efficiently collect data based on the current learned parameters.
Inspired by the theoretical results,
a novel offline RLHF algorithm with parameter constraints is proposed, restricting parameters to the valid space defined by the dataset. 
Furthermore, an online RLHF algorithm is proposed to iteratively optimize parameter learning and improve data collection efficiency.
This work provides a tighter bound than previous studies and offers theoretical guidance for online data collection under general function approximation.

Published in Transactions on Machine Learning Research (03/2025)
A Tighter Bound for Reward Learning in Reinforcement Learning from Human Feedback
Guoxi Chen
chen leen_ggooi@seeeeuu.co
School of Automation Southeast Universily
Xing Chen
zingchen1990jun edu.com
School of Artificial Intelligence Jilin University
Bo An
boan edu.sg
College of Computing and Data Science Nanyang Technological University
Ya Zhang
machang@seu.ddu.cr
School of Automation Southeast University
Reviewed OpenReview:
https: openreview. net/ forum? 3dF2yhooFF1333dddeeeeerrrr
Abstract
As key component of reinforcement learning from human feedback (RLHF), reward learn- ing directly influences the final learned policy. Unfortunately, existing theoretical estima- tion error bounds in reward learning rely on the complexity of the reward function class, unattainable optimal parameters, or non-zero constants independent of sample size, lead- ing to uncomputable bounds that are meaningless for reward function classes with unknown complexity. address this issue, this paper presents an analysis of parameter estimation for reward learning in RLHF under general function approximation, without imposing restric- tions the complexity of the reward function class. A tighter bound is provided without non-zero terms independent of the sample size. The optimal parameters are eliminated by applying linear approximation around the learned parameters. Additionally, the relationship between the preference dataset and the learned parameters is further examined to demon- strate how to efficiently collect data based on the current Icarned parameters. Inspired by the theoretical results, a novel offline RLHF algorithm with parameter constraints pro- posed, restricting parameters to the valid space defined by the dataset. Furthermore, an online RLHF algorithm proposed to iteratively optimize parameter learning and improve data collection efficiency. This work provides tighter bound than previous studies and offers theoretical guidance for online data collection under general function approximation.
1 Introduction
Reinforcement learning from human feodback (RLHF) has shown great empirical success in various ficlds, including large language models (Liu et al.] 2023
Ouyang et al.) 2022 recommender systems {Xue et al. 2023a b), robot training (Kupesik et al.) 2018 Bıyιk et al. 2022), and autonomous driving (Wu et al, 2024 Sun al.) (0024). The standard RLHF framework typically consists of lcarning a reward function from a preference dataset and subsequently applying deep reinforcement learning to optimize a policy based
the learned reward (Dong et al. 2024 Ti et al.
2024 Wang al. 2023 Nika al. 2024 As key

---

Published in Transactions on Machine Learning Research (03/2025)
capability, the reward function plays an essential role in the success of RLHF (Kausik et al. 2024 Zhou et al, 2024). Since the reward function is typically parameterized by neural network and its learning involves adjusting the network's parameters, parameter estimation error becomes critically important in measuring the performance of reward learning.
Parameter estimation errors in reward learning are inevitable (Gao et al. 2023 Pan et al. 2024 Coste
ett al. 2023). In practice, is necessary to establish an error bound determine how the estimation error scales with sample size. This error bound also provides valuable insights for optimizing data collection strategies. Furthermore, in an ideal setting, it is intuitively expected that the error bound provides guidance for identifying an infinite datasct, such that the estimation error converges to zero. However, existing error bounds fail to fulfill this expectation.
Several studies Zhan et al. 2023b Zhu et al. 2023 Xiong et al. 2024 Du et al. 2024 Ge et al. 2024 have explored sample complexity, showing that the error bound converges to zero as the dataset size approaches infinity when the reward function is restrieted to the class of linear functions. Zhhu et al. (2023) extended the linear analysis to the nonlinear case. In their results, even with infinite number of samples and all conditions satisfied, the learning error does not necessarily converge to zero. A few studies (Zhan et al, 2023a; Ji et al. 2024) focused on providing convergence guarantees for general function approximations. Their error bounds rely on the complexity constraints of the reward function class, unattainable optimal parameters, the supremum operator and the expectation operator. These factors make it difficult to compute error bounds and use them to support the design of online data collection strategies.
Inspired by the weight fine-tuning process in large language models (LLM), we compress the parameter solution space to achieve a tighter bound for parameter estimation in reward learning under general function approximation. We also establish the theoretical relationship between the dataset properties, the optimal parameters, and the learned parameters. The main contributions of this paper are summarized as follows.
(I) We propose an estimation error bound in the form Ō C(data,0 /d where C(data, 0*) is a vn constant dependent on the dataset and the optimal parameters 0* (see Theorem D and Table [ for details). This bound is tighter than that of Zhu et al. (2023), and provides a thcoretical foundation for parameter optimization and online data collection to ensure the estimation error converges to 0 as the sample size + oo.
(2) To avoid dependence on unavailable optimal parameters, we perform Taylor expansion around the learned parameters, replacing the dependence on the optimal parameters with the learned pa- rameters. We further derive an estimation error bound in the form Ö v 1 where C(data, 0) is a constant dependent on the dataset and the learned parameters 0 (see Theorem for details).
(3) Inspired by the theoretical results, we propose a parameter-constrainee offline RLHF algorithm that is designed to ensure parameter lcarning occurs within the region effectively covered by the offline dataset. Furthermore, we develop a novel online RLHF algorithm. Utilizing iterative pro- cesses, we design bi-level optimization framework to optimize parameter learning and improve data collection efficiency.
The proposed theoretical results can be applied to more general reward learning problems and offer theoretical guidance for online data collection.
2
Related Work
This section begins by discussing learning from pairwise comparisons and then explores reward learning in both linear and general function classes.
Learning from pairwise comparison. Learning from pairwise comparisons has been widely studied the literature. Rajkumar & Agarwal (2014) explored the statistical convergence properties of some rank aggregation algorithms within a natural statistical framework. Shah et al. (2016) proposed the sharp upper
2

---

Published in Transactions on Machine Learning Research (03/2025)
The proposed bound
Existing bound Zhu et al. 2023
Linear case (i.e., b2 0)
d+2 doogg ++2221000 2og
C.
d4log( AB
<(1
x+2
n
n"
212 doox
2
Nonlinear case (i.c., b2 +
a9 40
24g
002
a1
d+ (og(1/))) azn
a + bbbbyB) Ba +
Table 1: Comparison of the proposed bounds with previous studies.
and lower bounds on the optimal error in estimating the Bradley-Tery-Luec (BTL) models. Recently, several studies have started exploring this issue within the framework of RLHF. Unlike earlier research, which aimed to minimize the probability of disagreement in random pairwise comparisons, studies in RLHF focus on identifying the optimal strategy from preference dataset. Both [Skalse et al. (2023) and Li et al. (2024) highlighted the ambiguity in reward function learning within the context of pairwise performance comparisons, emphasizing the critical need for convergence conditions for reward learning.
Learning within the lincar function class. Existing rescarch on reward function learning has achieved good results in the linear function class. Xiong et al. (2024) studied the reverse-KL regularized contextual bandit for RLHF, and proposed efficient algorithms with finite-sample theoretical guarantees. iZhan et al.. (2023b) proposed strategy collect preference samples and provided an error bound for the parameter estimation. Zhu et al. (2023) analyzed the convergence conditions of the maximum likelihood estimator (MLE) and its corresponding error bound for the linear reward function class. This paper extends the results of Zhu et al. (2023) and provides a tighter bound for general function approximations.
Learning within the general function class. The research most similar to our objective is that of Zhan et al. 2023a).. Under the pessimistic learning assumption, they provided a bound on the error when the dataset has good coverage. However, this bound requires limiting the complexity of the reward function class. Subsequent studies also limited the complexity of the reward function class when analyzing the sample complexity of general function learning, such Chang et al. (2024), Liu et al. (2024), Huang et al.) 2024h, and Ji et al. (2024). Overall, these studies establish the finite sample suboptimality gap of the form ( coverage /NR/N) /N), where NR is the complexity of the reward model class R, N is the sample size, and C2 coverage is the concentrability coefficient to characterize the coverage of the preference dataset. However, the complexity constraints on the reward function classes restrict the types of reward functions that can be represented, resulting in the ground truth reward function falling outside of this class. Furthermore, Cooverage involves the supremum operator, the expectation operator, and the unattainable optimal parameters, which makes the bound difficult to compute and ineffective guiding the online data collection process (see Section 5.3 for details).
In this paper, we study the general function approximation learning problem from the perspective of pa- rameter estimation. We propose tighter bound than Zhu et al. (202)) Based on theoretical results, we naturally propose an oflline RLHF algorithm to learn the parameters in the space well covered by the dataset. Furthermore, we propose an online RLHF iteration for parameter optimization and data collection.
3 Preliminaries
We begin by introducing the notation used in the paper. The Markov decision process is int roduced in Subsection 3. and the data collection model of human preferences is detailed in Subsection 3.2
Notations: R and R" denote the set of real numbers and the n-dimensional Euclidean space, respectively. [[] describes the mathematical expectation. A(X') denotes the set of all probability distributions over the space X. || ll2 the 2-norm of vector or the spectral norm when applied to matrix. ||a|| = Vr is the semi-norm of x, when Σ is a positive-semidefnite matrix. X 2 Y (especially, X > Y) means X-Y is positive semi-definite (especially, positive definite). Ta is the d-dimensional identity matrix. Amin(.) is the
3

---

Published in Transactions on Machine Learning Research (03/2025)
smallest eigenvalue of a matrix. P(4) represents the probability that event A will occur. tr(+) is the trace of matrix.
3.1 Markov Decision Processes
In this paper, we consider a finite-horizon MDP described by a tuple M H. P, R2, where S is a stale space; A is an action space, is the horizon length, Pa. : S x A A(S) is the state transition at each step h p the initial state distribution, and R. the reward space. Following Zhan al. (2023a) we consider the reward function R: T R to include the entire trajectory, which is more general than the single-step reward, where T == (S A) is the set of all possible trajectories. The reward defined the state-action pair can also be viewed as a special case of H 1.
At each step h, the agent executes action a from state and transits to the next state s with probability (s a) E Ph- At step H, the agent completes the entire trajectory T E T and receives a trajectory- based reward r(T) E R.
A policy : + (AA determines the probability distribution over actions, conditioned on the current state. After determining the reward function r, the value function V, S + R for policy æ defined as the expected reward, given by starting at state and following policy SE S, (s) == [r)r),) where the expectation is taken over the state transition and policy-inducod action distribution. The Q-function O S + I for a policy æ is defined analogously, i.e, Q, (8, a) == (x)(((s)) (r())]. Given a reward function r, the goal is to find a strategy π that maximizes the objective (T),, where
Mathematically, for any
J. = Ee (r(()r
The optimal policy x' is defined as the policy that maximizes re, i.e., n² = arg max, (T).
In the RLHF setting, aim to learn the ground truth reward function r- from human preference data, and obtain its estimate A. The corresponding optimization algorithm then finds the optimal policy tt = arg max, JT),,, which, however, may be suboptimal with respect to the ground truth objective function (T). We define the gap as
G( R) J,- (T²" Jy. (f).
(2)
We will show in Theorem 3 that the gap G(T* 4) influenced by the learning error of the reward. Subsection 3.2 we will detail the data collection and learning model for the reward.
3.2 Human Feedback Model
We focus the problem that both the trajectories and preference labels come from a pre-collected dataset D = [Λी. Tá. pi where n is the sample size. For every sample i, oí and T are two different trajectories, and Pi [0, 1] represents human preference. The samples are assumed to be ii.d. Assume that a human provides preference labels by comparing trajectories based on an unobscrvable reward function r". Considering randomness, the label pt treated as a random variable that satisfies
ex (r)
Elp.]
(3)
(rf) (T))
It is a more general model. When P4 is Bernoulli variable with probability simplifies to the widely used Menully-Terry-Luee (BTL) model (Bradley Terry
Gr (135 equation (3)
1952 Christiano et al,
2017 Zhu et al. 2023 Zhan et al. (223a)). Equation also allows experts to provide continuous preference labels when the dillerence between trajectories is subble. As analyzed in Subsection 3.1 the crucial factor of is the error of reward function learning. Following Zhu et al. (202)), we study this problem from the perspective of parameter estimation. Throughout the paper, we make the following assumption the parameterization of the reward.
Assumption 1. The ground Iruth reward r* can be parameterized by 0* E Rdd
4

---

Published in Transactions on Machine Learning Research (03/2025)
This assumption is common Zhu al. 2023 Zhan et al. 2023b,, and always use parameterized neural networks to learn reward functions, which essentially defaults to this assumption. In the subsequent analysis, we use Tg. to replace r* and rg for f, to highlight our objective of learning the parameters 0" There have been many studics discussing the relationship between the reward learning error bound and the sample size. Zhu et al. 2023) and Zhan et al. (2023b) studied the case where the reward function is linear, and they proposed the error bound from the perspective of parameter convergence. As for nonlinear reward functions, Zhan al. (2023b) proposed a loose bound parameter convergence, which does not tend 0 the sample size increases. From another perspective, some studies have focused on the identification capabilities and the complexity of the reward function class. Under pessimistic learning conditions, Zhan et al. (2023a) provide an error bound for learning nonlinear reward functions. However, this bound imposes limitations on the cardinality and expressive capacity of the reward function class. These same limitations are also noted in Chang et al. (024)) and Liu et al. 2024).
In this paper, we analyze the estimation error of nonlinear learning from the perspective of parameter estimation, tightening the bound discussed in Zhan el. al. (2023b). We show that, even without pessimistic learning conditions, the convergence of parameter learning can still be guaranteed if the preference data provides rich information in the gradient sense (scc Theorem | for details). We will provide an example to show that this condition is intuitive. Without this condition being satisfied, no performance guarantees can be obtained even if the reward function follows a linear structure.
4 Problem Formulation
This section defines the problem statement. The standard RLHF typically involves a two-stage procedure Song et al. (2024): first, learning a reward function from a preference dataset using MLE; second, employing the learned reward function with standard reinforcement learning algorithms (such as PPO) to derive the optimal policy with respect to the learned reward function, summarized in Algorithm
Algorithm Standard RLHF
Input:
offline dataset D.
1. MLE: compute rg by solving 11 and 12
2. Standard RL: find á = arg max (T)
To approximate the ground truth reward r", according to Assumption ! we define a parameterized function class R = [ro]0 / E {), such as neural networks or other parametric models, to approximate the true ground truth reward. The parameter space is defined as
+ = (0
|0||| B).
(4)
where B is positive constant to measure the bound of the parameter space. Similar to Ahmadian et al. h2024h, the reward learning stage aims to find paramcters 0 E e that minimize the negative fog-likelhhood L(0,70 D):
n
( ps log ( + (7)()))
1
L(B,D)
Pe log
+ +(1 pt)
Pt) log
(5)
12
7
1 1+e-t
1 1 eb
where (T m5) = re(7T) To
R.
For convenience, dency on D, except for Subsection 6.2
shorthand n/ : (Ti, T²), and all functions in subsequent sections will omit depen-
Then, we make the following assumptions about the reward function class R. The Assumptions 2 coistrain
the variation in the reward function, ensuring that bounded parameter changes lead to bounded changes in reward values. Similar assumptions have also been mentioned in rescarch on noulinear function problems by Zhu al. 2023). It is also common in the study of nonlinear functions (Malanowski al. 2020 An al. 2023).
5

---

Published in Transactions on Machine Learning Research (03/2025)
Assumption 2. The reward function re R is continuous with respect to 0 O Assumption 3. For any 0 E θ E T, the following inequolities hold:
[ra(T) - bo:
(6)
|| |[rr(T)]l2 S bb,
(7)
l S b2,
where bo. b1, and b2 are some positive constants to restrict the rg E RR from the value, gradient, and Hessian with respect to 0, respectively-
Assumption 4. The second-order derivative of the reward function is bounded, and its gradient with respect to theta is also bounded, i.e., for any T E T, 1 1 i,j S
rro(T)
$ c1:
(9)
0,0,
(T((T)
1l2 S 02:
(10)
0,0;
where 0g is the i-th parameter of 0. C₁ and 02 derivative of re that satísfies the Lipschitz continuity condition.
positive constants to restrict the second-order
In the following probably approximately correct (PAC) analysis, further assume that the parameter class is realizable.
Assumption 5. (Realizability): 0" E e.
Assumption 5 flimits the analysis to the PAC learnability framework, where non-PAC learnable problems can only yield approximately optimal solutions within the solution space. This assumption is common in related
research (hhu et al. 2023 Zhan et al. 2023b
Wang et al. 2023 Liu et al. 2024).
Under the Assumptions
the MLE estimator attempts to solve the following optimization problem Zhu
al.
2023
Zhan et al. 2023b
arg min I(O), s.t. ||0| E A.
(11)
(12)
Now, we clearly define the main focus. Define 1 as the last trained parameter obtained from problem
11:-0 12
and the estimation error is A = 0 0-0 In existing research, under similar assumptions, Zhu et al.
(202)) establishes a bound for A the form o C' /d+log + C")b), where C' and C" are non-zero conslants dependent on the datasct. The estimation error bound is expected to tend to 0 as n increases if suitable samples are collected. However, the theoretical result falls short of this expectation if the reward function is non-linear (i.e., by * 0). Some studies Zhan et al. (2023a) analyze the problem from the perspective of function expressiveness. However, these approaches inevitably require constraining the complexity of the reward function class, and the resulting bounds often involve unataanabbe optimal function (see Section 6 for detailed comparison). In this paper, focus providing tighter bounds for A than Zhu et al. 2202)), and we further decouple A from its dependence on 0", making it both computable and practical for guiding data collection.
/n
5 Tighter Bounds for RLHF with General Function Approximation
In this section, we provide the main theoretical results, including lighter bounds for reward learning and tighter bounds for the suboptimal performance gap. In subsection 5.1 we tighten the bound on a key Hessian matrix to propose a tighter bound than that Zhu et al. (2023) (Theorem []. Similar their result, this bound is related to the dataset properties and the optimal parameters 6*. To further eliminate dependence the inaccessible optimal parameters, perform Taylor expansion around the learned parameters,

---

Published in Transactions on Machine Learning Research (03/2025)
replacing dependence the optimal parameters with that the learned ones. This error bound depends solely on the dataset properties and the learned parameters. In subsection 5.2 we establish the relationship between the gap G( ;) between the suboptimal strategy á and the optimal strategy x² and the reward learning error A. This relationship is summarized in Theorems g and which correspond to the results of Theorems ] and 2 respectively. In subsection 5.3 we theoretically compare the estimated error bounds with those from existing research. We further explain why these bounds are tighter. Additionally, we provide explanations for the key parameter a involved in the error bounds with an illustrative example.
5.1 The Tighter Bounds for Reward Learning
For convenience, define Ç - ming,s
Since ná is bounded, Ç must satisfy < Ç < 1. A tighter bound
1++0%
for reward learning from the point of view of 6" is summarized in Theorem
Theorem 1. Under the Assumption we have
if O, for any X 2 0, with probability - 8, (1) When e = 0,
80 01
(A S
(13)
(2) When a 00 En", after n > n", we have
a1 - Va
4 ag * 02
| S
(14)
2az
if B 01 V 4aagagg
where 02 (8(bbb + bieid + 202d), a1 5 BCA + dog 8 1log(2d2) (2d2/6)
) 1,00
402 /4
/d22/dlog $ ++2log
B
and is the mininamm eigenvalue of En (0*), with En((") = E V
(Vrg-)
Overall, the bounds depend on the paramcters of the reward function class, i.c., b,, b2, Ci2 C22 d, the quality of the dataset, i.c., Q, and the number of samples, i.e., n, while 02 characterizes the part of the reward function class that captures nonlinearity. Comparing 13) and (14), both are derived from (15). Specifically, for the linear case where d2 0, (15p can be further simplified to (13). This relationship is analogous to quadratic equation with sccond-order coefficient. More clearly, the linear case bound can be written 1422/dlo 7 2
<(I
We sketch the proof of Theorem
The core goal of the proof is to construct the following quadratic inequality 155 that is only related to || [=)))-)
A 2 ED a Eo( 00 S S.
(15)
To achieve this goal, we use the PAC assumption (Assumption 5 to obtain the following inequality.
| (V
2 1(0 + A) - 1(0") TvI(0").
(16)
To express the right-hand side of equation 16) solely in terms of | A we make use of a property
satisfied by 0', which lies between 0* and 0, rather than applying it to all 0 as in Zhu et al. 2023) Then, at 0", Taylor expansion with a Lagrange remainder term is performed, and
| (Vtp://0)"4xll(10000000000000aam
8log (2d2 18) |
<| Ep(e-) - (8cbibb + bleld + 202d) day
(17)
n
can be further obtained. An important step this process is tightening the bound on the following Hessian matrix E y where yi zero-mean random variable. We toy example in Appendix A.4

---

Published in Transactions on Machine Learning Research (03/2025)
to illustrate that it may tend to 0 as increases, rather than being merely bounded by constant. This is the key motivation to tighten the existing bound. Due to the correlation between O' and yi, transform Van into a finite increment related to 0" - 0' according to Assumption 4 and variable independent of yi- This allows us to control the upper bound of the Hessian matrix at the element lovel, tightening the original upper bound 2b2 provided by Zhu et al. (2023) Furthermore, on the left-hand side of Equation is transformed into lower bound that depends on vū, a probabilistic sense.
177,
Since || ((=0)))(( only involves 0", this step can follow a similar process to Zhu et al.) (2023).
Ultimately, this leads to quadratic inequality in the form of Equation [15 The proot is detailed in
Appendix C.1
Parameters 02, 01, ao, and are only related to the 0* and dataset D, so they are considered constants. Ep((") depends on the dataset and the ground truth parameter 0". Thus, Theorem shows that when the dataset satisfies some conditions, the estimation error tends to 0 as approaches infinity. It is tighter bound than Zhu et al. (2023). However, this thcorem passive, as Σn(6") is fixed, making Theorem | inapplicable to parameter learning and data collection. To overcome this limitation, we expand around 0 to associate the learned parameters with the propertics of the datasct. computable bound of the reward learning from the standpoint of 0 is shown in Theorem 2
Theorem 2. Under the Assumplion we have
if Q > O, for any 2 0, with probabilily 1- 8, (1) When et = 0,
60 ā1
A AlEED())AA1
S
(18)
22) When ci 0, 3n", after n", we have
| â1
09
4 do
02
(19)
202
if B <
41 y Vaj 4a
where â₂ = 3 (8(bzb, + bic1d+ + 202d) 2 0, 00,0==
- + de1 V 8log(2d2 /8)
) a.
482 v
dbftA
361
8d (
3
and à is the minimum eigenvalue of (d)),, with ED(() = n E (vn) A+a
n
The sketch of the proof is similar to Theorem 1 except that the Taylor expansion is performed around 0'. related to both and 0*, which invalidates the proof strategy employed in Theorem [ We solve this problem by bounding [|V[(0*)| by controlling the bounds and growth rate of its elements. Note that each element of vi(0") is a zero-mean random variable scaled by constant. Therefore, the corresponding bound can be derived using the union bound. Then, we use the compatibility of norms to unify the resulting quadratic inequality. The proof is detailed in Appendix C.2 Parameters 02, âi, âg B. and â offer a concise representation, highlighting the relationship between these parameters and Å. Theorem eesaalishess the relationship between the learned parameters 0 and the bound A on estimation error. This theorem suggests that it is possible to learn parameters within finite space to ensure bounded estimation error. Moreover, it indicates that by continuously collecting data online, the coverage of the dalaset can be optimized.
This causes (=((0))
5.2 The Tighter Bounds for the Suboptimal Performance Gap
In this subsection, we address the second stage of standard reinforcement learning, which involves using reinforcement learning algorithms (such as TD3 and PPO) to optimize the policy based the learned reward function. We summarize the performance gap between the policy induced by the learned reward function and the optimal policy in Theorem and
Theorem 3. Under Assumption 2 5 the gap in performance between the policy induced by the learned reward function ra and the ground truth optimal policy can be expressed as
G(T", #) 2b, (1x
(20)
8

---

Published in Transactions on Machine Learning Research (03/2025)
Recall that A = θ - is the reward learning error of the parameters. The main idea of the proof involves converting the performance gap into the learning error of the reward function and obtaining the further result according to the Lipschitz continuity condition (Assumption 2). The detailed proof is provided in Appendix C.3 The bound of Theorem is related to Theorem from the perspective of l". Similarly, the result corresponding to Theorem is summarized as Theorem
Theorem 4. Under Assumplion 5 the gap in performance between the policy induced by the learned reward function rg and the ground truth optimal policy can be expressed as
"( 2b 2133)
(21)
The proof sketch is similar that of Theorem The detailed proof is provided in Appendix C.4 In the next section, will analyze in detail what these boundarics signify and compare them with existing results.
Theorems and reveal the relationship between reward function learning and the final suboptimal policy error, suggesting that the focus of theoretical analysis can be placed on reward function learning, Theorem 3 links the performance gap to the parameter estimation gap. Equation (20) implies that, with the same 1 probability, the performance gap and the parameter estimation gap share the same upper bound, differing only by a constant. Thcorem 4 has the same meaning as Theorem 3 except that it linked to the paramcter estimation error used in Theorem 2
5.3 Insight into the Tighter Bounds
In Theorem I since a the minimum eigenvalue of the positive definite matrix Ed(0"), @ 2 0 always holds.
When Q > 0, we compare the proposed bounds with existing studies. Table shows that we achieved a tighter bound. In Zhu et al. 2023). for the lincar case (i.c., b2 0), when À + 0, they achieve
+ log (1/8)
| AE S SC
2 + XB2.
(22)
where is universal constant. The right side of the 22 does not tend 0 as n - 0o, if condition by implies 61 0. As oc, ag vanishes at rate of O(1/vn), while 5(1 - is
X 0. The
constant. Thus, de + 0, if a > 0. Comparing 13 and 22 since the estimation error bound is a strictly et
monotonically decreasing function of n, there exists value N such that for N,
Al
a1
d 2 d log 3 + 2og gi
(Our bound)
<(1
X+a
d log (1g() 2 n
SC.
+ XB2 (Existing bound).
holds. The third inequality holds strictly when X > 0. For nonlinear case (i.c., by # 0), we have achieved a tighter error bound. They proposed the following bound
23
+ log(1/8) azn
by + b,bbB B², 02
| (A Say a1
+ X
(23)
where an and 02 are some universal constants. If by + 0, as n increases, the right side of equation
23
will not converge to 0, but lo a constant a a (A+
ba + BbbbBBBB even = 0. However, our result al 0g

---

Published in Transactions on Machine Learning Research (03/2025)
Theorem 1 is tight. As the sample size approaches infinity, the right side of equation 14 tends to 0, since (Ao 0. Thus, comparing (14g and 223 there exists value N when >> N',
a1 Vaz - 4 ao * 02
| |AlEDD(*)+\a S
202
d42y 12
a1
V a9 - 4
02
(Our bound)
20²
+ log(1/0)
by + bybbB B (Existing bound)
< 01
+
02
holds. The third inequality will strictly hold, if b2 + O. Their bound under nonlinear conditions fails to answer whether parameter estimation errors would asymptotically approach zero with an infinite dataset, even under ideal conditions. In comparison, we propose a tighter bound that successfully fulfills this expectation.
The error bound proposed in Zhan et (2023a) involves the complexity of the reward function class, and the concentrability coefficient C Cooverage which reflects the quality of the data and is expressed
Mo: (1) = max {o, 0u,upp E Erjoet an Ir (m)))))
where Ho and Pl are two distributions data sources. Compared to them, we do not require comprehensive coverage assump- tions for the data collection policy, nor do we impose restrictions on the complexity of the reward function class. Although Ceoverage also describes the data quality, it involves the supremum operator, the expectation operator and the unattainable optimal parameters. These factors make Cooverage difficult to compute and ineffective in guiding online data collection. Under ideal conditions, the proposed bound is computable and offers a tcal approach for identifying an infinite dataset to achieve est imation errors approaching zero.
Cooverage (R, x" No:
In the error bound proposed in Theorem [ the most crucial parameter a, which is the minimum eigenvalue of (Br) If a 0, then, the given bound is empty.
The case where a requires separate treatment. In this scenario, a 0 allows A to become arbitrarily large in certain subspace, which causes ||||)=,,0->> to remain bounded while ||A grows without bound. Consequently, any discussion of error bounds becomes meaningless, including (22) It is reasonable and consistent with observations in existing studies. We begin by discussing the importance of a from the perspective of the estimation algorithm. Zhu et al. (2023) explored the estimation problem within the lamily of linear structure reward functions, where r"(r) = " and Vng. = ((T)) - d(r2). They used a pessimistic learning strategy make learning more robust. However, we use an intuitive example in Appendix 3 to illustrate that even under the linear structure assumption, the pessimistic learning strategy may not be able to obtain any effective performance guarantee.
Theorem is related to 0" When the characteristics of the offline dataset satisfy the corresponding condi- tions, the estimation error is bounded and tends to 0 as sample size tends to infinity. When the offline dataset is imperfect, although Theorem D provides a tighter bound than existing studies, since 6* is inacces- sible, it fails to theoretically offer practical and efficient online data collection strategy.
To address the problem of imperfections in offline datasets, we propose Theorem 2 This theorem clarifies the relationship between the learned parameters and the error bounds, providing critical insights into both the scope of parameter learning and the objectives of online data. collection. In the next section, we will propose two RLHF algorithms induced by Theorem
6 Application of the Tighter Estimation Error Bound
The previous analysis gives tighter bounds for general functions under the standard RLHF, Inspired by the theoretical results, we add constraints to the standard RLHF framework highlight the importance of a. To further optimize a, we propose a novel online RLHF approach that iteratively collects data and retrains parameters, supported by Theorem
10

---

Published in Transactions on Machine Learning Research (03/2025)
6.1 Offline Iterative RLHF
Online data collection provide much better coverage than the offline dataset. While the study (Xiong et al. 2024b confirms this result, its scope is restricted to linear function classes. Theorem 2 links the learned parameters, sample properties, and estimation error bounds. This observation motivates us to employ constrained optimization on the parameters to ensure that the learned parameters remain within the confidence region the pre-collected dataset.
We modify the optimization problem
12 as follows.
arg min L(0): 0
(24)
s.l.
Σ
2 Otaaggt ld:
(25)
n
i=1
0 E
(26)
where Otarget is predefined constant.
This implies that in solving the optimization problem, we limit the scope of acceptable solutions to represent the confidence region of the offline data. This constraint is directly derived from the error bounds. Appendix(A.] we provide a toy example to demonstrate how this constraint effectively restricts the parameter solutions to fcasible space. The offiine RLHF algorithm under paramcter constraints is summarized in Algorithm
2
Algorithm 2 Offline RLHF
Input:
offline dataset D.
1. MLE: compute ræ by solving 24
26
2. Standard RI: find arg max Jrg
It may be difficult for the oflline datasel to satisfy the constraints. Given this limitation, propose a novel online RLHF that iteratively performs data collection and parameter optimization.
6.2 Online Iterative RLHF
We aim for the collected data to cover the feature space represented by 8", as shown in Theorem 1 However, we actually only have the learned parameters é. Inspired by Theorem 2 we propose a bi-level optimization approach for the original constrained optimization problem 254 Overall, we use the parameters obtained from the (t-1)-th iteration calculate the characteristics that the data collected in the t-th iteration should satisfy. For the 1-th iteration, with 0 fixed, we aim to collect data to increase the confidence of 0% i.e.,
mm finding (7 72 Jj=1 that satisfy
arg [r) 1rdd
Amiin (E4(0) 11'((1))
(27)
where is the sample size per iteration,
(0)) m
1
Va. -a
is generated by new data, and (0t) = + Σm vn (vr)))
(²'))) is generated before the t- 1-th
additional data collection.
Then, retrain gc+1 according
28
30
to find better solution that satisfies the constraints.
11

---

Published in Transactions on Machine Learning Research (03/2025)
arg min 0
L(0, D)),
(28)
DD (0) 2 Otarget Id s.t.
(29)
f E θ
(30)
where D' is the datasot used for training at the 1-th itcration. summarized in Algorithm 3
The corresponding online RLHF is
Remark 1. The proposed online algorithm's 's bottlenecks stem from bi-level optimization and minimum eigen- value calculation. Il provides guidance for dala collection and does nol necessorily require mullippee ileralions. In the simple ezperiment 6.3 show the results obtained from single iteration, which already demon- strate superior performance compared to random sampling. For computing the minimum eigenvalue, if we select m trajectories from condidate set of size M, the number of possible choices is (m), which makes exhaustive evaluation compulationally prohibilive. rithm that selects each step the trojectory that yields the largest increase in the minimum eigenvalue. For high-dimenstonal problems, computing the minimum eigenvalue itself challenging, and iterative methods lypically adopled to oblain opprozimale solutions, such as the LOBPCG algorillem.
reasonable upprozimation to adopt a greedy algo-
Remark 2. The parameter Ozarget in 29 is determined by both the dataset and the learned parameters. During dala collection, the value of corresponding to the current dalaset. under the current porameter 0 can be compuled, and Oktarget is then empiricully set as Ottarget al0') for the (1 + 1)-th ileralion.
Algorithm 3 Online Iterative RLHF
Input: offline datasct D, itcration count T, sample size m per itcration.
1. D D.
2. compute Tha by solving 24
26
3. for itcration t t= 1 T
do
collect data {T 12 1--1 according to (2
D D U (T m
1==1-
compute rg++1 by solving 28-030
5: end for
6. Standard RL: find â arg max Jryr (TT)
6.3 Experiment
This section evaluates the proposed algorithm on a small-scale reinforcement learning task and uses HalfCheetah-v4 from MuJoCo as the evaluation environment. The environment's default reward function is denoted as r". A preference datasct then constructed by sampling preferences according r*. The reward function maps the current stale, next state, and action to proxy reward value, comprising total of 84 learnable parameters due to the omission of the bias term in the output layer.
of state pairs and assigning
We constructed 10, 000 preference samples based on the r". Then, for reward learning, 100 samples were initially selected to train the model raı, whose performance evaluated using accuracy, Pearson, and Spear- man correlation coefficients. After the initial training, we further collected 50 trajectories through random sampling and Algorithm to obtain the proxy reward models riaa and Alg3 respectively. A comparative analysis of these models provided in Table
02
12

---

Published in Transactions on Machine Learning Research (03/2025)
Table 2: Evaluation metrics on the overall preference dataset.
Proxy reward model
Accuracy
Pearson coefficient Spearman coefficient
rg=
73.39%
0.5666
0.6616
rga
77.43%
0.6789
0.7348
Alg3
96.43%
0.9906
0.9929
Aa
We adopt TD3 the downstream reinforcement learning algorithm. Fig. shows the performance of four different reward functions (r", rgi, Tga and T'= Alg3 in downstream DRL tasks, where the y-axis represents the true and unnormalized reward. It be seen that the proposed online collection algorithm improves data collection efficiency and achieves performance on downstream tasks that is closer to training with ground-trute reward compared to random sampling.
Comparison Downstream RL on HalfCheetah-vd
The Beward
vairing with rewards
with Proxy Reward sampling
Experiment Algonthmm
-2000
3.0
0.2
0.6
1.
Total Timesteps
1ed
Figure 1: Comparison of Downstream RL Tasks on HalfChoctah-v4
7 Conclusion
We have provided a theoretical convergence analysis of RLHF under general function approximation. The main results involve two insights: (i) when the preference datasct satisfics some conditions, the parameter estimation error converges to without any constraints on the complexity of the reward function class (Theorem I and (ii) collecting data that enriches the gradient information of the reward function is beneficial to parameter learning (Algorithm 3).
Although we have made progress in understanding the convergence of RLHF, several issues remain unre- solved.
1). Although it is not difficult to find the gradient of the reward function, finding the minimum eigenvalue a matrix computationally complex, and how to find an effective approximation remains an open issue.
2). This paper studies the PAC problem. If the optimal parameters are not in the solution space, whether meaningful error bound can still be guaranteed remains open issue.
13

---

Published in Transactions on Machine Learning Research (03/2025)
Acknowledgments
This research supported by National Natural Science Foundation (NNSF) of China under Grant 62373100 and 62233003, National Science and Technology Major Project under Grant 2212D0112702 and SEU Innovation Capability Enhancement Plan for Doctoral Students under Grant CXJH SEU 24131. This rescarch is supported by the Ministry of Education, Singapore, under its MOE AcRF Tier 2 Award MOE- T2EP20223-0003. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not reflect the views of the Ministry of Education, Singapore.
References
Arash Ahmadian, Chris Cremer, Matthias Gallé, Marzieh Fadaee, Julia Kreutzer, Ahmet Üstün, and Sara Hooker. Back to basics: Revisiting reinforce style optimization for learning from human feedback in llms. arXiv preprinl Xio: 14740, 2024.
Xuming An, Li Shen, Han Hu, and Yong Luo. Federated learning with manifold regularization and normalized update reaggregation. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Newral Information Processing Systems, volume 36, pp. 55097-55109. Cur- ran Associates, Inc., 2023. URL
newr.seerrrpp... hotpr///cc/ppprrrr.e//////////// acf25Seee002211622220cc222222222 Srrpre/eeeeeeeappae-ooorrreeeeee Confeeeneee
Erdem Bıyık, Dylan P Losey, Malayandi Palan, Nicholas C Landolfi, Gleb Shevchuk, and Dorsa Sadigh. Learning reward functions from diverse sources of human feedback: Optimally integrating demonstrations and preferences. Int. J. Rob. Res., 41(1):45-67, 2022.
Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: 1. the method of paired comparisons. Biomelrika, 39(3/4):324 345, 1952.
Jonathan D Chang, Wenhao Shan, Owen Ocrtell, Kianté Brantloy, Dipendra Misra, Jason D Lee, and Wen Sun. Dataset reset policy optimization for RLHF. arXiv preprinl (54::4444088495 2024.
Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legy, and Dario Amodei. Deep reinforce- ment learning from human preferences. In Advances in neural information processing systems, volume 30, 2017.
Thomas Coste, Usman Anwar, Robert Kirk, and David Krueger. Reward model ensembles help mitigate overoptimization. arXiv preprint arXiv:2310.0277 027443, 2023.
Hanze Dong, Wei Xiong, Bo Pang, Haoxiang Wang, Han Zhao, Yingbo Zhou, Nan Jiang, Doyen Sahoo, Caiming Xiong, and Tong Zhang. RLHF workflow: From reward modeling online RLHF, Trans. Mach. Learn. Res., 2024, 2024.
Yihan Du, Anna Winnicki, Gal Dalal, Shie Mannor, and R Srikant. Exploration-driven policy optimization in RLHF: Theoretical insights on efficient data utilization. arXiv preprint arXiv:2402.10344, 2024.
Leo Gao, John Schulman, and Jacob Hilton. Scaling laws for reward model overoptimization. In International Conference on Machine Learning (ICML), pp. 10835-10866. PMLR, 2023.
Luise Ge, Brendan Juba, and Yevgeniy Vorobeychik. Learning linear utility functions from pairwise com-
parison queries. Xrxio preprint Xii::2205.02612 2024.
Roger Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
Daniel Hsu, Sham M Kakade, and Tong Zhang. A tail incquality for quadratic forms of subgaussian random vectors. Electron. Commun. Probab., 17:1, 2012.
Audrey Huang, Wenhao Zhan, Tengyang Xic, Jason D Leo, Wen Sun, Akshay Krishnamurthy, and Dylan J Foster. Correcting the mythos of kl-regularization: Direct alignment without overparameterization via chi-squared preference optimization. Xiv preprint (77.1:2407.133990 2024.
14

---

Published in Transactions on Machine Learning Research (03/2025)
Xiang Ji, Sanjeev Kulkarni, Mengdi Wang, and Tengyang Xie. Self-play with adversarial critic: Provable and scalable offline alignment for language models. arxiv preprint or arXin:2406.04277, 042.06 2024.
Chinmaya Kausik, Mirco Mutti, Aldo Pacchiano, and Ambuj Tewari. A theoretical framework for partially observed reward-states in RLHF. In International Conference on Machine Learning (ICML), 2024.
Andras Kupesik, David Hsu, and Wee Sun Lee. Learning dynamic robot-to-human object handover from human feedback. Robotics Research: Volume 1, pp. 161 176, 2018.
Ziniu Li, Tian Xu, and Yang Yu. When is RL better than DPO in RLHF? a representation and optimization perspective. In International Conference on Learning Representations (ICLR), 2024.
Hao Liu, Carmclo Sferrazza, and Pieter Abbecl. Languages are rewards: Hindsight finctuning using human leedback. arxiv preprint 0iv:222302.00 0i:22302.0666,, 1, 2023.
Zhihan Liu, Miao Lu, Shenao Zhang, Boyi Liu, Hongyi Guo, Yingxiang Yang, Jose Blanchet, and Zhaoran Wang. Provably mitigating overoptimization in RLHF: Your sft loss is implicitly an adversarial regularizer. arXiv preprint Xrxi::2405. 16436, 2024.
Kazimierz Malanowski, Christof Büskens, and Helmut Maurer. Convergence of approximations nonlinear optimal control problems. In Mathematical programming with data perturbations, pp. 253 284-284. CRC Press, 2020.
Andi Nika, Debmalya Mandal, Parameswaran Kamalaruban, Georgios Tzannetos, Goran Radanović, and Adish Singla. Reward model learning vs. direct policy optimization: A comparative analysis of learning from human preferences. arXiv preprint arXiv:2403.00 01857, 2024.
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. In Advances in neural information processing systems, volume 35, pp. 27730-277711 -77444, 2022.
Jane Pan, He He, Samuel R Bowman, and Shi Feng. Spontancous reward hacking in iterative self-refinement. arxiv preprint Xrx0:244070445/, 2024.
Arun Rajkumar and Shivani Agarwal. A statistical convergence perspective of algorithms for rank aggrega- tion from pairwise data. In International conference on machine learning (ICML), pp. 118 126.. PMLR, 2014.
Nihar B Shah, Sivaraman Balakrishnan, Joseph Bradley, Abhay Parekh, Kannan Ramch, Martin Wain- wright,, et al. Estimation from pairwise comparisons: Sharp minimax bounds with topology dependence. J. Mach. Learn. Res., 17(58):1 47, 2016.
Joar Max Viktor Skalse, Matthew Farrugia-Roberts, Stuart Russell, Alessandro Abate, and Adam Gleave. Invariance in policy oplimisation and partial identifiability in reward learning. In International Conference on Machine Learning (ICML), pp. 32033 32058. PMLR, 2023.
Yuda Song, Gokul Swamy, Aarti Singh, J Andrew Bagnell, and Wen Sun. Understanding preference fine- tuning through the lens of coverage. arXiv preprint ar arxiv:246..00 01462, 2024.
Yuan Sun, Navid Salami Pargoo, Peter Jin, and Jorge Ortiz. Optimizing autonomous driving for safety: A human-centric approach with ann-nnneeedd RLHF In Companion of the 2024 on ACM International Joint Conference on Pervasive and Ubiquilous Compuling, pp. 76 80, 2024.
Yuanhao Wang, Qinghua Liu, and Chi Jin. Is RLHF more difficult than standard RL? a theoret- ical perspective. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (ods.): Advances in Neural Information Processing Systems, volume 36, pp. 76006-76032. Curran Associates, Inc., 2023. URL ctt553775555334440tcceeeeeeeeeee http://owoaaaooooo.ooo.aappppprr
15

---

Published in Transactions on Machine Learning Research (03/2025)
Jingda Wu, Zhiyu Huang, Wenhui Huang, and Chen Lv. Prioritized experience-basee reinforcement learning with human guidance for autonomous driving. TEEE Trans. Neural Netw. Learn. Syst., (1551))858888)) 2024. doi: 10.1109/TNNLA 2022..1772....
Wei Xiong. Hanze Dong, Chenlu Ye, Ziqi Wang, Han Zhong, Heng Ji, Nan Jiang, and Tong Zhang. Iterative preference learning from human feedback: Bridging theory and practice for RLHF under kl-constraint. International Conference on Machine Learning (ICML), 2024.
Wanqi Xue, Qingpeng Cai, Zhenghai Xue, Shuo Sun, Shuchang Liu, Dong Zheng, Peng Jiang, Kun Gai, and Bo An. Prefrec: Recommender systems with humman preferences for reinforcing long-term user engagement. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '23, New York, NY, USA, 2023a. Association for Computing Machinery. ISBN 9798400701030.
pp.
Wanqi Xue, Qingpeng Cai, Zhenghai Xue, Shuo Sun, Shuchang Liu, Dong Zheng, Peng Jiang, Kun Gai, and Bo An. Prefrec: recommender systems with human preferences for reinforcing long-term user engagement. In Proceedings of the 29th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp.
2874-2884, 2023b.
Wenhao Zhan, Masatoshi Uchara, Nathan Kallus, Jason D Lee, and Wen Sun. Provable offline preference- based reinforeement learning. arXiv preprint arxi2:2005. 14816, 2023a.
Wenhao Zhan, Masatoshi Uchara, Wen Sun, and Jason D Lec. How to query human feedback efficiently in rI? In International Conference on Machine Learning (ICML), 2023b.
Jiayi Zhou, Jiaming Ji, Juntao Dai, and Yaodong Yang. Sequence to sequence reward modeling: Improving RLHF by language foedback. arXiv preprint arXiv:2409.0011 001622 2024.
Banghua Zhu, Michael Jordan, and Jiantao Jiao. Principled reinforcement learning with human feedback from pairwise or k-wise comparisons. In International Conference on Machine Learning (ICML), pp. 43037 43067. PMLR, 2023.
A Toy example
A.1 Toy Example
This example is used to verify the proposed offline RLHF.
Example 1. Consider simple monlinear reward function learning problem with only 4 trajectories, denoted
0
0
[
[1]
1 1
T1
12
and Ta
Let the ground Irulh reward parameterized by 0" 1.1 and the nonlineur function defored as
("(r) To 00[1] 12 T[1] 7 (0 -[1]+ + (8'1)))))))
where [1] and 0 [2] represent the first and second elements of 0*, respectively, and r[1] and [ denole the first and second elements of T, respectively. Then,
[00 2 T [ + 1 + (10
Vro(T) 0 [ T + + (2)
Although constrained optimization problems are unlikely to yield solutions that make the objective function smaller than unconstruined oplimization problems, when there are mulliple solutions, construints con elim- inate unreliable solutions suggested by the data. Fig. [ shows this point. Assuming uniform sampling, the MLE solution may be inaccurate when the sample size small. In this case, the solution that minimizes the loss function ( becomes invalid, resulting in erroneous estimations. Fortunately, the constroint helps miligate the impact of this error.
16

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm II
Estimation Error under 2-nom
2.5
0.5
400
700
1000
of Samples
Figure 2: Comparison of estimation errors versus # of samples.
A.2 Toy Example
This example toy verification of the proposed online RLHFF. Consider simple nonlinear reward function
learning problem with only 4 trajectories, denoted as 0
0
[ and T4 | Let the
0
1
ground truth reward be paramcterized by 0" 1
1.1 and the nonlincar function is defined as r²(r)
((r)Tor + [1] [-[2] * r[1] 7[2), where [']1] and 0 [2] represent the first and second elements of 0",
respectively, and r[1] and r[2] denote the first and second clements of T, respectively. Then, Vro(T)
[0-2] * * + +T[1]
[111 * * + +r(2] We evaluate the effectiveness Algorithm by comparing the estimation error
of standard RLHF, which uses uniform sampling, with that of Algorithm across varying sample sizes. when the number of samples is small (less than 100). We set T 2 in 3 and each sample size is lested 10 times. When deploying Algorithm 3 the first N/2 samples are obtained through uniform sampling. Then, the parameters are obtained by solving the constrained optimization problems (28 (30 and further data collection based on the learned parameters and (27
We mainly focus the
Algorithm
The comparative experimental result is presented in Fig. g
Starplic
Figure 3: Comparison of estimation errors versus # of samples.
17

---

Published in Transactions on Machine Learning Research (03/2025)
Compared to uniform sampling, Algorithm B achieves better estimation results when the sample size is small. This is due to the fact that the latter N/2 samples provide the necessary information for more accurate parameter estimation with respect to the learned parameters. These experimental results suggest that the proposed tighter bound offers a more effective strategy for online data collection.
A.3 Toy Example
This example aims to present the curve of || Ei Pi* (pi* l4e% -(1 - p.) o²b 140%
) 82nillz as a function of
Vi, illustrating how we can compress the existing bounds. Example 2. We use the same configuration the Example 1 and eliminated randomness by averaging the
results from 100 experiments. The relationship between 1/2 Σ
1+c" (1 - p:)
1+e"0 V2nill and
V shown in Fig. is shown in Fig. 4 From Fig.
realized that although v² v2n l/gll is related to O
x10
12
10
Values
6
4
10
15
20
25
30
35
40
45
Vn
Figure 4: The relationship between a key term the bound and Vn.
and therefore to ps * 14 (1-p:)
Σ. Pt * 1+e
-
14 r2rrgl2 may still approach
1
zero. In fact, Fig. A shows that it approaches O at rale of approzimately Vn. This intuition encourages us to compress the eristing bounds and derive the tighter theoretical results.
A.4 Toy Example
Example 3. In this ezample, we will show that even pessimistic learning strategy canmot achieve any meaningful results =.
I i
0
0
Consider trajectories encoded by d(Ti)
(b(())))
((TT))
0
and db(Ta)
0
The pre-
1
collected dataset contains zhd comparison results of TI and and comparison results of and
If the
[0.5
0
0
reward function class follows linear structure, i.e., (*(T)) = TO then, Σp(I))
0
0.5
0
has
0
0
0
18

---

Published in Transactions on Machine Learning Research (03/2025)
01
the minimewn eigenvalue
The parumeters be learned are wrillen as
0
Divide the dalasel into
03
lao parts {ri 72, (:) and {Tz) P(. then the loss
be reorganized,
3
L(0)
pj log
+ (1 pi) log
1 e 0i
1 e
Σ p4 loy
+11 p/) log
+ 8-
+ 802
④
It easy to verify that for MLE solution 0=
02
poramelers
62
with any 0 is also a MLE solution.
02
Nole that the Pessimislic MLE of Zhuu et al. 22023) try to find the optimal strategy as follows.
arg
arg min Jra (T)] (EE(0.))
(31)
Let the ground truth reward be l" 0..1 0.1,, 1], the optimal strategy should generates T4 with probability
However, the optimal solution from 31
produces Ta with probability O, since
0
02
E ((,
B
07
02
This suggests that the optimal policy learned based on pessimistic optimization objective 31 can still exhibit an arbitrarily large performance gap compared to the true optimal policy when a
B
Auxiliary Lemmas
Lemma 1. (Objective decomposition). Let J(x) be the objective function defined in [ and for any reward
function f, the gap, as expressed 2 between the induced optimal policy क arg max, J+(x) and the optimal performance can be reformulated follows.
G( f) = E Braxt (T*(T) f(T)] + Esn - rT)
(32)
Proof. This proof mainly refers to Lemma A.1 of Song et al. (0224). Note that f arg max, Jz(T), thus
J+(+) 2 J+(
Then, we have
G( "( = Jr ( (+)
EgNpBRyN (r" (T)] E Eg, Ey (T))
BanpBras (r"(T) (T)] EgnpE. E + (r"(r) + E Ba ErspErxs(((()) Err [f(r]
[f(T]
< Byap Ir* (r)] EgNDE
E [[()] + E Br [f(T]] Br (T)
EaupEr (T) - -f(7)] + B.nnelB (f(T) r7)
(33)
This completes the proof.
19

---

Published in Transactions on Machine Learning Research (03/2025)
Lemma 2. (Hsu et al. 2012 Let M R=*" be matrix. Suppose that y [y,,..., yyl is random vector such that,
E
aa'y S
cllallā/2
(34)
holds for all a E R". For all t > 0, the following probability inequality holds.
P y > tr(M) + 2 to (M²) 2/IM|ld se
(35)
Lemma 3. For a matrix Rdxd, assuming its elements are bounded by |ayوl S b, then, the spectral norm of A bounded as follows:
|| - db.
(36)
Proof. According the properties of matrix norms, the spectral norm of matrix A is bounded above by its Frobenius norm |
A|l2 S |||E..
(37)
The Frobenius norm is defined as the square root of the sum of the absolute squares of its elements:
d d
|||
laay
2
(38)
1=1
Given the condition that each element is bounded by lasyl S b, we can derive the following inequality:
d
aisl
M 82 d²b²
(39)
1-
j=1
Taking the square root of both sides yields the upper bound for the Frobenius norm:
|| S Va db.
(40)
Consequently, applying the relationship between the spectral norm and the Frobenius norm, we obtain:
||4||2 S ||||| S db
(41)
This completes the proof.
C Proof of the Theorem
C.1 Proof of the Theorem i
Theorem (Restatement). Under the Assumption 2
5
if a 0, for any X 2 with probability 1 8, (1)
When 0, we have
S 00
(42)
01
(2) When Ci 0, 3n", after n > n², we have
01
ai
ag 02
|| (AIEED10)4)L
<
(43)
202
20

---

Published in Transactions on Machine Learning Research (03/2025)
if B a1+ -4 where dazy 402/ +0
(8(bbb2 + b211 + 202d)
8 (2dg
-- (CA das
d + 2 dlog + 2og
40
8 == Vxta
and a is the minimum eigenvalue of En(0*), with Ep((") = -E vng. (Vng- )
Proof. First, we get the expression of vi(0) E Fd as follows
the * Vnh
c * Vil
vI(0)
Pj
(1 - pb)
+ e n
+ e%
%
e
Di *
(1 - p2)
Vrie
+ T
+ e
1
en
Pi
-11 - p2)
(44)
1 1
1 + e/
The next step is to compute the Hessian matrix, v2((0) E Rdxd,
v21(0)
1
(p:
1
(1 pi)
v2
n
1 1 1+e% c%
+ c
-e%
(emb)²
(pi
(1 p:)
+ pı)
Und (vn))))
n
(1 cn
+ e
(1 + o
= (0) + (2)
(45)
where
1 n1
e
(0)
Σ
Pi
(1 - -pp).
V21l6.
(46)
n 1=1
1 2
+ c
and
1 n
em
(2(
Σ 71
Vila (vbb))
(47)
(1 + ebb
Then, we need to bound these two items respectively.
For convenience, noting that in the subsequent analysis we use the variable oá = rT( convert the constraints on the reward function in Assumption into constraints on n For any 0 e O 7I, E T, the following inequalities are hold according to the triangle inequality of norms (Horn & Johnson.
ro(T)), we first
21

---

Published in Transactions on Machine Learning Research (03/2025)
2012
No 11, T2) = - (rc) 2
(48)
[T,, 72)1l [|(r((T)) Vre(T2)le s + 261
(49)
( = (|T)) v2ro(12) = 1 s 2b
(50)
8ono(TI, T2)
pro(TT) @ro(Tz)
- 2c1
(51)
0.03
0,0g
0,0;
0n 17 [1. T2)
Pro(TT) rro (T2)
V|
1| 11
|| < 202
(52)
0:00
0,8;
0,00
Next, we will discuss the boundaries of (0) and ge(0), respectively.
(1). For gi (0), we discuss the bound of 9i (0') the range of 0' = to [0. 1]. Recall that 0-0 0- Intuitively, we leverage the continuity of re R with respect I e explore the property that 0' satisfies, where 8' lies between l and 0.
Then,
91()')
1
Σ
Ps
1
(1 P&)
71 i=1
1 +
e'
1 1 etio e
Next, aim to bound matrix 91 (0') Raxd using Lemma 3 and therefore perform element-wing wise analysis of 91 (0') first.
In order to reduce the pressure of symbolic expression, define the elements of the matrix V d') ik!
where i S n, and 1 S j. s d. The apostrophe indicates that this element is associated with 6', From (52 get 22n S a'j 20
Then, the clements of the matrix 91 (0') can be expressed as
9jke
(53)
1=1
where fic = (p. -p
Pa á jk:
(1 pp))
Decompose L/x into two parts as shown in (54) gn - Tzh
1+e"0
Ite"
and g3k- The first term associated with H' 0", while the other involves 0" and is expected to be 0.
6/x (ISN 95x) + gjke
(54)
where 93 - Ei= god Ske and
2/
g"
Di
(1 pi)
ar
jk.
(55)
1 1+ ei
1 + vo
Next, we need to find bounds for (0/x - 97x) and By respectively.
We will begin by finding the bound for Gik- After fixing the samples of and Tá. 9") is a random variable, with its randomness arising from p,. Define auxiliary random variable
1
31 Pi
(1 P.)
(56)
1 1 %-
1 1 %
22

---

Published in Transactions on Machine Learning Research (03/2025)
Then, take the expectation both sides of equation 56/. we have
E
E
Pr
E
Ps)
(57)
1 1 en
1 + el
Note that the randomness the right side of the equation (57) comes from Ps: and constants. We can further obtain
and
are
14
1te 6
1
c
ysl
E(pp]
(1 Elp,)) (1-E)p,])
0.
(58)
1 + c-
1 c% 6%
Similarly, since a" jbs is independent of Pt.
Eignj jkl = =Elyiia" jR =0
(59)
Since lyal <= 1, g j& is also bounded random variable, with -2c1 S g¹) jk 201- Thus, according to Hoeffding's inequality, we have
2,a
P( 2 t)
P
jk
E
jkl
t) 2e
i- (dcz)²
(60)
1=1
i=1
Simplify 60 and get
P( 21) $ 2e nc.
(61)
Rewriting 61 gives
-n. P( St) 2 2e Scg
(62)
Now, let.
-nt 8 2e Sc,
(63)
which leads
8 8log(2/8)
t == c
(64)
Thus, logel can be bounded with the probability of 8
18 (log(2/8)
93 S cav
(65)
n
for some special j, k.
Then, consider the bound of another part, S'p gik- The idea behind proving its boundedness is use the Lipschitz continuity condition to transform into bound related to the estimation error 0" 0'
1
e
1
en
Pi
(1 pi)
jk
Pt * 1 %b 1
(1 p.))
a jks
1+ No
1
%
+ e
1=1
i=1
(66)
23

---

Published in Transactions on Machine Learning Research (03/2025)
Consider an auxiliary function
1
en
p
fzx(0) = Ps
-(1 - pi)
(67)
1+ e%
+ en
8,0k
(()).
Note that
(f((O)
en
00
Pi
(1+ e (1+
Vno(Ti,75) (1 pi)
(1 + en
(noo(i, 72).
(68)
according to 50
we have
|V S 0.5b,,
(69)
since 11terral I 0.25 and
(1teryal S 0.25 always holds for any x.
Thus,
(f)x +
(70)
Furthermore, we have
(0)1e < ((f((()))() + (If(()) - S bic1 + 202,
(71)
since | and | S
always holds for any 0.
We further know that (0) is continuous with respect to 0, since fi(0) and f2(0) is contimuous according to the assumptions. According to the mean value theorem, we have
5i(0") - ((0)=)(0)=v((0)))
holds for some 8. Thus,
15'(0') - 1 (v/ - 0')
[v/'(a)aa 10)00 - 00112 S (bres + 202))l0' 0/
holds for any 1 isis n, and J. k s Combined with the above analysis, we have
1
(Bx(0') s
1944 g5al
n7
fix(0*) (3)(
i=1
< (bic1 + 202)) 00
According
and 65
8 1ogg(/8)
1 S (bic) + 20 -0 a
(72)
n
holds with the probability of 1 8, for special j, k. Using union bound, with probability 1- 8, we have
Slog(2d? /8)
I9/Nl (bic1 + 202) 0 + ay
(73)
n
for any j, k.
24

---

Published in Transactions on Machine Learning Research (03/2025)
According to 73 and Lemma We get the following results about the spectral norm of matrix 91 (0"). for any 0' 0r + * E [0, I], with the probability of - 6, we have
8 llog(2d /0)
91 01(0)= 2 (d(bic) 202)]l0' 00 + dei
la-
(74)
(2). Next, the bounds of 92 (0) is discussed. We continue to discuss the property of the parameter between and 0"
Define d,(0", 0¹) = Vng ui--vin Vig-- since the first derivative function also continuous. According to Assumption
and 51 we have ||d, (")1l"00")1= s 2b2]16 1-
For 92 (0'), further derive:
(2
Vig (vr)))
Vng. + (,(00,''))(vvi) + ())
vnhh (vni-) )T + d, 8 (v))b-)) JT d (00
(75)
Next, combine g1 (0') and 92(6") discuss the property that 0' satisfy. Define X(0*)
[vnl,, ........ vnh- E Raxd is the parameter matrix of the n samples, then Ep((") = (x0)
Note that Voll z 2b1, according to 45 we have
v²1(0') - (0') + 92()
[x(00) + S Σ d, (')(n))))))) T Vnl (T) + g1
> (x0)) 8Cb2b 1|0 - 00 + (6')
(76)
Combined with the previous derivation, can summarize the following property about 0'. For any 0' 0* +ooA, [0, 1], the following event holds with the probability of 1 6.
8 8log (2d2 (8)
A AT>"((0')>> <IAII A 10'0 Ab + 202) 0- 11,
AT
(77)
Using Taylor expansion with Lagrangian remainder, know that 30' 0 -e(0- [0, 11, 100 + +A) 1(0*) VI(0-)TA AT Since (77) holds for all 0', we have
8 Blog (2d /0)
1(0" A) 1(0") vI(0-)TZ / (0-)
+ bbc 2c2d) dep
|
Note that 8* is optimal for L(0), according to the realizability Assumption 5
we have
1(0' + A) - -Tv((T AV(((")) o.
(78)
25

---

Published in Transactions on Machine Learning Research (03/2025)
Using the Cauchy-Sch inequality (Shah et al. 2016 for
78 and combining
77
obtain
| ZDl00 |
2 - v((0)
z 1100 + -) - 1(00) A TV((0))
z <|| | Eo(e-) (8(C(1 + bic1d+ 202d)
log(22l2/
do
A
(79)
n
The following goal is transform 79 into inequality still holds. Thus, need to bound Recall
inequality equation about ||a|| while ensuring that the further.
12
e
Σ
vI(0))
Ps
(1 Pi)
+ e-
c
Since both vi(0") and Ef()") are related to 0", following Zhu et al. (s)00)))
2023 we can use Lemma to bound
Recall 566
%%
V1 Ps 1 + e/--
(1 - -P:)
and
X(0))= = [Vnge Vig-.... ..., vr/g1
Define Y E R", with this notation, Rewrite
vi(0") --x)== -0O0TTT
n
and
=V (TX(0))))))))) -
VYTMY,
where M = + 2 and ||, we need to analyze some properties of M. First, perform singular value decomposition on X(O"):
is n-dimensional square matrix. To determine the tr(M),
X(0)) U.VT,
(80)
where Σ E Baxd U e gxx= and V E gdxd, U and V are two orthogonal matrices. The diagonal of Σ contains singular values o;.
Calculate (E) + ATa) first.
(ED(0") + Aa) -LVETUTUEVT + A
= =n(VE"EVT+ +ndla)
(Since U is an orthogonal matrix.)
=n(V(A+ T)
26

---

Published in Transactions on Machine Learning Research (03/2025)
where = ΣTΣ Rdxd is diagonal matrix with diagonal elements of.
Then,
n² M X(0))2(())+M)))
n
-UEAA+NAaa nXla) - (Since U and V orthogonal matrices.)
7
Since A is diagonal matrix, (A n is also d-dimensional diagonal matrix with diagonal elements Furthermore, Σ(A + nATa) is also d-dimensional diagonal matrix with diagonal elements
nAto? of
of
We summarize the properties of M as follows Thus, M has only d non-zero cigenvalues m(mi-o?))
mdto?
Tr(M) <
(Since and the trace of a matrix is equal to the sum its eigenvalues.)
(81)
d
Tr (M <
(82)
n
|| S n
(Since A 0.)
(83)
Since Ely. = 0 and -1 S y: S 1, according to Hoeffding Lemma,
E[c*"] S e
holds for any k. Since ys are independent random variables,
II
E [e = [eZi kivi
holds for any Ki, K2, Kin which shows that random vector satisfies According to Lemma 2 combined with 81
83
we have
P
MY
-2
S Se-
n
Then, laking 6 = e- i..,, I. = log to with probability
8, we have
d 2+ d dlog j/ + 2 log 1
VYTMY <
(84)
n
Using union bound, with probability at least
8, according to
79
we have
d 2 d log + 2 logg 2
| |
CII (0=) A (T(bii + bieid + 202d)]
8 (2d2 (5)
-dei
||
=CIIA - -88bb,b2 + bicid + 2e2d)
8 8log(2dP// |
- - + de1
2 -CIA - (*(b + bicid 202d)
2log(222/8))
- -C((C do
27

---

Published in Transactions on Machine Learning Research (03/2025)
The third inequality is due to the consistency of the norm, ie.,
|ul1 - 2ll
(85)
holds, for any o E R2, since g2 is the smallest eigenvalue of Ep(0r) + Ala.
The above inequalities are organized into
-22 E (0 + 2o00 00 S 0,
(86)
where
02 3 (8(b1b2 + bleid 202d) 2 0
a1 = Ç - (²((A + dop 8log(22P)8) ) and
n
d 2 2 doo 3 + 2lggo AM
80
Next, need to solve the incquality second-order derivatives are O. Consequently, have 82 c2 = 0, and a2 0. Therefore,
86 If c 0, by definition, this implies that ro is linear, and all its
|Al Q1
(87)
If C1 > 0, since of - * ag is monotonically increasing function of n, and limn-+co of ag * a2
<(1 (²>) 0, there exists n", such that when n², at 4 op 02 have
01 a ag 02
AA| -
202
or A 01 + a
* dg * 02
(88)
202
a1 attva 4400002
Since <
we can conclude that
4ag /b7++
a1 V [i
4 ag a2
|A|ED
S
(89)
202
This completes the proof.
C.2 Proof of the Theorem 2
Thcorem 2 (Restatement). Under the Assumption 2
if à 0, for any À 2 0, with probability 1 - 6, (1)
When by = 0, we have
âp ā1
A AlEDD())AL
(90)
(2) When by 0, 3n", after n n², we have
à
07
do
à
| A
(91)
28
28

---

Published in Transactions on Machine Learning Research (03/2025)
if B â1 - where (02/103+>
02 3 (8(b1)2 + bicid+ + 202d) 2 0,
â1 3 (CA + dep
8 blog(2d3/)
8d ldgog2d//0)
00 BbbV
3 Va+a
and & is the minimum eigenvalue of ED (0), with Σp(0) = " Ei vng(vrn)"
Proof. Note that vl(0) E IRd, then
% Vil
e Vr/a
v((0)
pj *
(1 - pi)
+ E = %
2
e
ps *
(11 - ps)
41j0
1 ni
1 + nh
e
pj *
(1 - pi)
Vnb
(92)
1 1+ e/
1 + nb
The next step to compute the Hessian matrix, v²((0) E Rdxd,
1
1
e%
v71(0)
(p:
(1 pi)
+ e/ v2mg
1 1 et
-e%/
(enb)²
Σ (pa
(1 p2)
+ (1 ps))
vnl (v16))
n
(1 (1+ 6%
1 + c%
(1 + em,z
(0) + 92(
(93)
where
2%
(1) = Σ
- (1 Pi)
(94)
1 1 t
1 + Th
==1
and
(2)
1
Σ i=1
(1+ e1+ vob(vnb)T)
en
(95)
n
Then, we need to bound these two items respectively.
For convenience, noting that in the subsequent analysis we use the variable vá = rT( convert the constraints on the reward function in Assumption into constraints on n For any 0 e O 7I, E T, the following inequalities are hold according to the triangle inequality of norms (Horn & Johnson.
ro(T)), we first
29

---

Published in Transactions on Machine Learning Research (03/2025)
2012
No T1, 72) = - (o0 2
(96)
[T, 72)1l [|(r((T)) Vre(T2)le s | 261
(97)
( 72)1l = (|T)) v2ro(12))l2 = 1 s 2b
(98)
iono(TI.2) T2)
pro(TT) @ro(Tz)
- 2c1
(99)
0.03
0,0g
0,0;
0n 17 [1. T2)
(ro(TI) rro (T2)
V|
1| 11
||2 < 202
(100)
0:00
0,8;
0,00
Next, we will discuss the boundaries of (0) and ge(0), respectively.
(1). For gi (0), we discuss the bound of 9i (0') the range of 0' = 0" +o [0. 1]. Recall that 0- Intuitively, we leverage the continuity of re R with respect I e explore the property that 0' satisfies, where 8' lies between 0 and 0.
Then,
(1
Σ n1
1
Ps
1
(1 P&)
e
1 +
e'
1 1 etio e
Next, aim to bound matrix 91 (0") Raxd using Lemma 3 and therefore perform dlement-wise analysis of 91 (0') first.
In order to reduce the pressure of symbolic expression, define the elements of the matrix V a" it: where S n, and 1 j k s d. The apostrophe indicates that this element is associated with 0'. From (100 get 22n S a'j 20
Then, the clements of the matrix 91 (0') can be expressed as
9jke
(101)
1=1
where ffke = -p-+
2/6 d jk: Decompose S/y into two parts as shown (102;: g - 9zh
pı)
1t0"0.
140"0
and g3k- The first term associated with H' 0", while the other involves 0" and is expected to be 0.
6/x (d'x g5x) + gjke
(102)
where 93 - Ei= gdd Ske and
2/
g"
Di
(1 pi)
ar
jk.
(103)
1 1+ ei
1 + vo
Next, we need to find bounds for (0/N - 97x) and Byh respectively.
We will begin by finding the bound for Gik- After fixing the samples of and Tá. 9") is a random variable, with its randomness arising from p,. Define auxiliary random variable
1
31 Pi
(1 pt)
(104)
1 1 %-
1 + %
30

---

Published in Transactions on Machine Learning Research (03/2025)
Then, take the expectation both sides of equation 104 have
c
E y
E
Pr
pi)
(105)
1 cn
1 + cn
2% and
Note that the randomness on the right side of the equation (105) comes from Pe, and constants. We can further obtain
are
14c"0-
14c"0-
1
UA]
E[ps]
+ 6% - (1 - Elpi)) (1-Elp)))
C = 0.
(106)
Similarly, since a*} jr is independent of Pt:
Eig jkl = Ely,la" jk =
(107)
Since lyel <= 1, 9 jk also bounded random variable, with -201 S g S 201-
Thus, according
Hoeffding's inequality, we have
2,2
F(Igjul 2t) = PO
jk
E
9 jkl
ž t) $ 2e
2i ( (9r1)²
(108)
1=1 11
i=1
Simplify 108 and get
P( 2 $ 2c sc.
(109)
Rewriting 109 gives
P(1gjel St) 2 1 2e 3oy
(110)
Now, let
8 = 2e Sc1
(111)
which leads
8 8lo((2/0)
t == C1
(112)
Thus, 103el can be bounded with the probability of
8 8log(2/8)
99 S es
(113)
n
for some special j, k.
Then, consider the bound of another part, 0/p gyk. The idea behind proving its boundedness is use the Lipschitz continuity condition to transform it into bound related to the estimation error H" 0'
9j*
1
Pi
(1 Pi)
e
i
Pj
(1 pc)
e
a
jks
1 Po.
da
n
1
+ c/.
31

---

Published in Transactions on Machine Learning Research (03/2025)
Consider an auxiliary function
1
en
p
fzx(0) = Ps
-(1 - pi)
(114)
1+ e%
+ en
8,0k
(()).
Note that
(f((O)
en
00
Pi
(1+ e (1+
Vno(Ti,75) (1 pi)
(1 + en
(no(Ti,
(115)
according to
98
we have
|V S 0.5b,,
(116)
since 11terral 1 0.25 and
(1teryal S 0.25 always holds for any x.
Thus,
(f)x +
(117)
Furthermore, we have
(0)1e < ((f((0)))()) + [If(())v53(0)) = S bic + 202,
(118)
since | and | S
always holds for any 0.
We further know that (0) is continuous with respect to 0, since fi(0) and f2(0) is contimuous according to the assumptions. According to the mean value theorem, we have
5i(0") - ((0)=)(0)=v(())))
holds for some 8. Thus,
15'(0') - (0(0 1v/ - 0') (V/ - 00112 S (bres + 202))l0' 0/
holds for any 1 isis n, and J. k s Combined with the above analysis, we have
1
(Bx(0') s
1944 g5al
n7
fix(0*) (3)(
i=1
< (bic1 + 202)) 00
According
102 and 113
8 1og((/8)
1 S (bic) + 20 -0 a
(119)
n
holds with the probability of 1 8, for special j, k. Using union bound, with probability 1- 8, we have
|s5sl| < (bic) + 20 8 + e1 8 logg(2d2/5)
(120)
for any j, k.
32

---

Published in Transactions on Machine Learning Research (03/2025)
We get the following results about the spectral norm of matrix 91 (0'). For any 0' 0r + A E [0, I], with the probability of 1 - 8, we have
According to 120 and Lemma 3
8 Blog(2d /5)
91 (0) = (d(bic) + 202))l 00 + de V
la-
(121)
(2). Next, the bounds of 92 (0) discussed. We continue to discuss the property of the parameter 0' been and 8 The key difference from the proof of Theorem | is that this time we expands around 6'. Define d0, 0*) = Vnh Vng. since the first derivative function is also continuous according to Assumption and 51,, we have (0, 0')ll z 2b2 Ó11- Then, 92(0") can further oblain as follows.
(0 2
vnda (
71
" n
(vng + d:(0,, +
Vn)((Vn)) + (') + vn)d
(122)
In the following, combine (8') and g2(0") to discuss the property that 8' can satisfy. Define X(θ)
(nn). vng.... Vnğl" Rxxd is the parameter matrix of the samples, then Σp x()) For now,
Note that Vngl S 2b1, we have
v²(((")= 91 (00) 92((")
[x(0)_ x0) + S Σ d,(00')) + S Σ
2 [x(0)= x - 8(b2hn 110 - 0112 g00)
(123)
Combined with the previous derivation, can summarize the following property about 0', For any 0' 8* +o o E 1), with the probability of 1 - 5, the following event is established.
8 Blog( (2d2 2012/8)
AT (T>21(0')2 C A7(8Cb2bi10'' -11,) Alc(bic + 202)110' 00112- - A
(124)
Using Taylor expansion with Lagrangian remainder, know that 30' 0" - [0, 1(0" +A) 1(0") vI(0-)TA A Since 124 holds for all 0', we have
log (2d2 /8) lodd
1(0" + A) - 1(00) vI(0")T 2 (0) - - b,c,d A12 dei
A
n
Note that H* is optimal for L(6), according to the realizability Assumption 5.
we have
1(0 + A) - 1(00) A + S 0.
(125)
Using the Cauchy-Sehwarz inequality for 125 and combining 124 obtain
|||2||v((0*))) 112 2 -
2 1(0" + A) - 1(0 A Tv((0*)
8 8log (2d2 /0)
1 E AT(BCb + b 2c2d)|1A1124 -do1
||
(126)
33

---

Published in Transactions on Machine Learning Research (03/2025)
The following goal is to transform (266 into inequality equation about ||||| while ensuring that the inequality still holds. Thus, need bound ||] further. Since vI(0") related to 0 but Ep(
is related to Ó, Lemma 2 does not apply. Portunately, we can obtain an acceptable result by controlling the bounds of the elements of vi(0") and applying the union bound.
Recall
c%
vI(0")
Ps
(1 pi)
Vnh-
1 cni-- cn
+ c
and Vng- Rd is bounded vector after fixing oं and TÿJ-
With slight abuse of notation, let the elements of Vni-- be a1 و S d, Sis n).
According to
104
oblain the elements a1(1 j S d) of vi(0") as follows.
aj
yaa
(127)
Since the randomness of ys comes from ps and is independent of aj, based on 106 we have
Ely,a5] = E[ysJaj = O.
(128)
Since V ll2 S 201, and af is the element of nē- |ay1 S 261 always holds.
Combining |ys| < 1, waa a bounded random variable with -2h S y:a s 21.
Thus, according to Hoeffding's inequality, have
2,2
F(la,l t) P(
1 n
Σ
yia
E n
yaal
2 t) s 2c
(ab,)
(129)
Simplify 129
and get
2e -a12
P(|aş] 2 f) <
8h,
(130)
Rewriting 130 gives
P(Jay) St) 2 2e 8b1
(131)
Now, let
-ne?
8 = 2e 96,
(132)
which leads to
(208(2/8)
t t= b1
(133)
n
Thus, |ayl can be bounded with the probability of 1
la,1 S 8log(2/0)
(134)
n
for some special j. Using union bound, with least probability 1 5, we have
log(2d/0)
lay1 < by V
(135)
34

---

à0 Published in Transactions on Machine Learning Research (03/2025)
for any j. Therefore, we arrive at the final conclusion that
|v](0))|2 s bi Vi 8d Bdlog/2d/0)
(136)
holds with probability of at least 1- Next, we the compatibility of norms unify the norm forms both sides of the incquality 126 According to the compatibility of norms, we have
||ll2 S A {0)0)l
holds for any Rd, since 3 and å is the minimum eigenvalue of E)(() and is the smallest eigenvalue of (0) Ala- Using union bound, with probability at least 1 8, we have
Va+a
B
8d (2g(//2
8 8log(2d) (2///8)))))))
3b1
Al (0))++A1 2 CI1A - (8cb102 + breid + 202d)|| dei
|| |
n
= =cIL -CIAAEED(0)N)) (8C1) + bieid 202d) 202d) ||1
8log(2d /8)
- -CA + de1
)11|
CII
3 (8Cbi bicid + AI
(CA + doi
880g((2(1/))
|| 21 (0
The above incqualities are organized into
02 A || LNt
+ +11l|Al Eo(0)+>a - âo S0
(137)
where
à2 3d (8(b1b2 + bicid + 202d) 2 0,
â1 = < - 3'1 + des 8 8log(2(2/8)
) and
Sel log (2d/o)
āo 301V
Next, we need to solve the inequality 137 If e 0, by definition, this implies that re is linear, and all its second-order derivatives are 0. Consequently, have b2 c2 and a2 0. Therefore,
A
If c1 0, since of - 4 åo dg is monotonically increasing function of and lim of 4 âo ag
C(1 3² >) > 0, there exists n², such that when n> n², ai 4 åo d2 > 0 we have
0 V 0 4 dn az
| 1
2I
à + v
o
4 dg à2
or 1D
(138)
2ā
35

---

Published in Transactions on Machine Learning Research (03/2025)
Since B < (L--V conclude that
142 103+1
0g
02
A Ex (0)+ (0)
S
2
This completes the proof.
C.3 Proof of the Theorem
Theorem (Restatement). Under Assumption 2 the gap in performance between the policy induced by the learned rewand function rg and the ground truth optimal policy con be expressed as
G( 2b A|AA
Proof. According to Lemma under Assumplion 2 5
for the MLE solution rg. we have
G( ft) EgpplErwar [ra- (T) - ro(T)) Es
(To(T) Eeuple re- (7)].
Then, combined with Assumption and we can further obtain
G( = ES-DEErTn (ra- (r) - rT((T]] + Es-pErralrat re- (T)
$ |b2l|A1 A|l
$ 311 Eo(0
The last incquality holds due to the compatibility of the norms, i.e, ||0|2 S / (0-)) holds, for any
Rd.
This completes the proof.
C.4 Proof of the Theorem 4
Theorem (Restatement). Under Assumption 5 the gap in performance between the policy induced by the learned reward function ra and the ground truth optimal policy can be expressed as
G( G(T", 2b, Al
Proof. According to Lemma under Assumption for the MLE solution vag, we have
Gi f) = BerpEy [ra- (T) [T(TT] Be (Fo(T) - re- (T)]-
Then, combined with Assumption and we can further obtain
G( +) = SEsplErww [re- (ra-(r) (r)-r((7)) + E re- (T)
< 2b, A|l2
< 2b, 3| A1
The last inequality holds due to the compatibility of the norms, i.c., ||l|| s -3111lE holds, for any Rd This completes the proof.
36


Reviews:
[{"review_id": "Gu1V2Z4Ool", "reviewer": "Reviewer_S8EA", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper makes a strong theoretical contribution to RLHF by deriving a tighter parameter estimation error bound under general function approximation settings. It avoids dependence on unattainable optimal parameters and addresses previous limitations of uncomputable or vacuous bounds that rely on the complexity of the reward function class. Additionally, the authors propose offline and online RLHF algorithms inspired by their theoretical findings, with promising empirical illustrations in a toy example.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The authors claim to provide a tighter error bound for reward learning in RLHF under general function approximation, without relying on reward function class complexity or unattainable optimal parameters. These claims are supported by two main theorems (Theorems 1-4), with clearly stated assumptions (Assumptions 2–5) and well-structured proof sketches in the main text, along with full proofs in the appendix.", "audience_yn": "Yes", "audience_explanation": "The paper introduces theoretical advances with practical implications in RLHF, aligning well with TMLR’s mission. It is likely to be of interest to a significant portion of the readership engaged in RLHF.", "requested_changes": "1. The reference formatting appears to be not correct, particularly with respect to missing parentheses in citations. The authors should ensure correct usage of `\\citet` and `\\citep` throughout the manuscript.\n\n2. Although the paper is primarily theoretical, the current experimental evaluation is limited to toy problems with low-dimensional trajectory spaces. To improve practical relevance and broaden the paper’s appeal, it would be beneficial to include experiments on standard RLHF benchmarks, such as Gridworlds or CartPole with trajectory preferences, as well as simple reward modeling tasks in robotic feedback simulations (e.g., MuJoCo) or even LLMs.\n\n3. The tightness of the theoretical bounds and the empirical success of the proposed algorithms critically depend on the parameter $\\alpha$ (the minimum eigenvalue of a data-dependent matrix). The paper would be strengthened by an empirical analysis of how $\\alpha$ varies across datasets, along with a sensitivity study of performance with respect to $\\alpha_{\\text{target}}$ in the constrained optimization (Eq. 25). Additionally, approximate methods for estimating $\\alpha$ in high-dimensional settings should be discussed.\n\n4. Computing the minimum eigenvalue and solving the bi-level optimization in Algorithm 3 may be computationally expensive in high-dimensional regimes. The authors should discuss potential scaling strategies or approximations to improve efficiency.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "67DCGuor5w", "reviewer": "Reviewer_wocM", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This submission studies reward learning in RLHF from a parameter estimation perspective under general (nonlinear) function approximation. A key difference from prior work is that the proposed bounds avoid dependence on reward-class complexity measures and reduce reliance on inaccessible optimal parameters.\n\nThe main contributions are: (1) a tighter finite-sample estimation-error bound for reward parameter learning, along with a computable variant; (2) a connection between reward estimation error and downstream policy performance gap; and (3) algorithmic implications, including an offline RLHF approach with constraints and an online iterative RLHF procedure motivated by improving the informativeness of collected comparisons. Overall, the bound provides practical insight into how improving data “informativeness” can improve generalization.\n\nA main weakness is the limited empirical validation: the numerical experiments are small-scale, and the paper would benefit from more extensive ablations and evaluations to support the practical claims.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The core claims are supported by a coherent set of theoretical results (Theorems 1–4) with clearly stated conditions and explicit bounds. In particular, the main bound is formulated in a way that removes explicit dependence on the unknown optimal parameter $\\theta^*$, and the recommended procedures (offline constraints and online iterative data collection) follow plausibly from the theory.\n\nThat said, while the theoretical development is convincing under the paper’s assumptions, the practical and algorithmic implications would be more compelling with stronger empirical evidence and clearer implementation details for realistic settings (e.g., how the key quantities are estimated efficiently in high-dimensional models). Overall, the theory is well-supported, but the practicality claims would benefit from additional demonstrations.", "audience_yn": "Yes", "audience_explanation": "Reward learning is central to RLHF, and this paper contributes to an active research direction on understanding when and why reward learning converges under nonlinear function approximation, as well as how dataset properties affect estimation and generalization. The analysis offers an informative viewpoint that may be useful both for theory-driven readers and for practitioners thinking about data collection and training stability.", "requested_changes": "The paper’s practical takeaway is the proposed algorithmic framework. I would expect at least one additional experiment beyond the small toy example (e.g., using a standard benchmark or a realistic preference-learning setup) to demonstrate scalability and practical benefit. In particular, it would strengthen the paper to report: (1) reward estimation error, (2) downstream policy performance, and (3) runtime/compute overhead, ideally with ablation studies that isolate the effect of the proposed data-collection or constraint mechanisms.", "broader_impact_concerns": "I do not see major ethical issues of this paper, since it is primarily theoretical and methodological.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "8X5FB6mRWE", "reviewer": "Reviewer_WLtK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The main contributions of the paper are the derivations of tighter bounds for reward learning in RLHF that are not dependent on constants such that the bounds approach zero as the dataset approaches infinite size. Another key difference from previous bounds is the proposed bounds are not restricted to the linear reward function class. The authors suggest $\\underline{\\alpha}$ which is the minimum eigenvalue of the empirical fisher information matrix $\\Sigma_{D}$ is the most crucial parameter. They propose a constrained offline reward learning algorithm with a constraint on the empirical fisher matrix to keep the parameters in the confidence region of the dataset and extend it to online reward learning. A toy experiment was used to demonstrate improved reward learning accuracy of the online RLHF algorithm compared to uniform data sampling.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The main claim of the paper is a set of tighter bounds for RLHF. Compare to previously developed bounds, e.g., by Zhu et al, 2023 and Zhan et al, 2023a, the bounds are indeed tighter and approach zero as dataset increases. And these prior work are properly discussed and no significant prior work is missing as far as I can tell. \n\nThe toy experiment also clearly demonstrate the advantage of the proposed algorithm where targeted sampling improves accuracy over uniform sampling with small dataset size.", "audience_yn": "Yes", "audience_explanation": "Understanding the theoretical behavior of RLHF and more efficient data sampling method is of wide interest.", "requested_changes": "* I think the paper can do a much better job explaining the various quantities and constants to help readers understand the meaning of the proposed bounds more intuitively, in addition to just agreeing with the statements in the paper. Section 5.3 attempts to do this job and I think organizationally it's in an adequate spot in the paper. What I would like to see is the an explanation of most constants, e.g., $a_0, a_1, a_2, n^*$ if not all right after theorem 1. \n* Another useful information intuitively is a comparison of (13) and (14), i.e., the bounds for $c_1=0$ (linear) and $c_1 > 0$ (non-linear). What are the main causes for the difference?", "broader_impact_concerns": "NA", "additional_comments": "* I am wondering whether the bound for the linear case is guaranteed to be non-negative, since according to the equation between (22) and (23), you have a term $1/(1 - \\beta^2\\lambda)$.\n* How are the proposed algorithms different from active preference learning where you sample data in the uncertain region and thereby increase confidence, e.g., [1]? \n\n[1] [Bıyık, E., Talati, A., & Sadigh, D. (2022, March). Aprel: A library for active preference-based reward learning algorithms. In 2022 17th ACM/IEEE International Conference on Human-Robot Interaction (HRI) (pp. 613-617). IEEE.](https://arxiv.org/abs/2108.07259)", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)