Sharp Analysis for KL-Regularized Contextual Bandits and RLHF
Authors: Heyang Zhao
Chenlu Ye
Quanquan Gu
Tong Zhang
Venue: NeurIPS 2025 poster ()
Keywords: Contextual bandits
regularization
Primary area: theory

Abstract: Reverse-Kullback-Leibler (KL) regularization has emerged to be a predominant technique to enhance policy optimization in reinforcement learning (RL) and reinforcement learning from human feedback (RLHF), which forces the learned policy to stay close to a reference policy. While the effectiveness of KL-regularization has been empirically demonstrated in various practical scenarios, current theoretical analyses of KL-regularized RLHF still yield the same $\mathcal{O}(1 / \epsilon^2)$ sample complexity as ones without KL-regularization. To understand the fundamental distinction between objectives with KL-regularization and ones without KL-regularization, we are the first to theoretically demonstrate the power of KL-regularization by providing a sharp analysis for KL-regularized contextual bandits and RLHF, revealing an $\mathcal{O}(1 / \epsilon)$ sample complexity when $\epsilon$ is sufficiently small. We also prove matching lower bounds for both settings. More specifically, we study how the coverage of the reference policy affects the sample complexity of KL-regularized online contextual bandits and RLHF. We show that with sufficient coverage from the reference policy, a simple two-stage mixed sampling algorithm can achieve an $\mathcal{O}(1 / \epsilon)$ sample complexity with only an additive dependence on the coverage coefficient, thus proving the benefits of online data even without explicit exploration. Our results provide a comprehensive understanding of the roles of KL-regularization and data coverage in online decision making, shedding light on the design of more efficient algorithms.

Sharp Analysis for KL-Regularized Contextual Bandits and RLHF
Heyang Zhao
Chenlu Ye
University of California, Los Angeles Los Angeles. CA 90095 hyzhao@cs. wataaaocssuccaa..om ucla.edu
University of Illimois Urbana-Chaman Champainn Urbana, IL 61801
chenluy3@illimoie iinisissiiiniiseuuuuu edu
Quanquan Gu University of California, Los Angeles CA 90095, USA qguêcs suluossuula..o edu edu
Tong Zhang
University of Illinois Urbana-Champaign Urbana, IL 61801
tongzhaang@tongzhangg-... org
Abstract
Kullback-Leibler (KL) regularization has emerged to be a predominant technique enhance policy optimization in reinforcement learning (RL) and rein- forcement learning from human feedback (RLHF). which forces the learned policy stay close reference policy. While the effectiveness of KL-regularization has been empirically demonstrated various practical scenarios, current theo- retical analyses of KL-regularized RLHF still yield the same (11/²²) sample complexity as ones without Kl-regullriizaton. To understand the fundamen- tal distinction between objectives with KI.-regularization and ones without KI- regularization, we are the first to theoretically demonstrate the power of KI- regularization by providing sharp analysis for KL-regularized contextual bandits and RLHF, revealing an (11/e) sample complexity when e is sufficiently small. We also prove matching lower bounds for both settings. More specifically, we study how the coverage of the reference policy affects the sample complexity of KL-regularized online contextual bandits and RLHF. We show that with sufficient coverage from the reference policy, a simple two-stage mixed sampling algorithm can achieve an (11ec) sample complexity with only an additive dependence on the coverage coefficient, thus proving the benefits of online data even without ex- plicit exploration. Our results provide a comprehensive understanding of the roles of KL-regularization and data coverage in online decision making, shedding light on the design more efficient algorithms.
1 Introduction
The KL-regularized contextual bandit problem (Langford and Zhang, 2007; Xiong et al., 2024a) has raised tremendous interest recently because of the significant development of the post-training stage in large language models (LLMs) and diffusion models from preference feedback (Christiano et al., 2017: Ziegler al., 2019 Ouyang et al., 2022: Bai al., 2022; Rafailov et al., 2024), which is called Reinforcement Learning from Human Feedback (RLHF). RLHF aims to optimize the policy by aligning it with human feedback, exhibiting impressive capabilities in applications such as Chatgpt (Achiam et al., 2023), Claude (Anthropic, 2023), Gemini (Team et al., 2023), and LLaMM-33 (Meta, 2024).
In RLHF, we treat the language model as policy that takes a prompt and produces a response conditioned on æ, optimizing the policy by aligning it with human feedback. There are mainly two
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

kinds of feedback: absolute rating and preference comparison. For absolute rating, the collection typically involves human annotators to provide rating scores like I to 5 (Wang et al., 2024a.b) for responses or hard 0-1 scores for math reasoning tasks since the reasoning tasks often have gold stan- dard answers (Cobbe et al., 2021; Hendrycks et al., 2021; Xiong et al., 2024b). Although discrete feedback is believed to be more intuitive for human users and easier to collect, it also poses more challenges for the RLHF algorithms to effectively leverage the feedback signals since the reward signals are not directly observed. In practice, the learning process typically involves (a) construct- ing reward model based on the maximum likelihood estimation (MLE) of Brudley-Terry (BT) (Bradley and Terry, 1952a) model from the preference feedback; (b) applying RL algorithms like PPO (Schulman et al., 2017b) to train the language model so that it maximizes the reward signals with KL regularization (Ouyang et al., 2022; Bai et al., 2022; Touvron et al., 2023).
Since the human feedback data only covers a tiny fraction of possible interactions, we optimize the model purely for the reward without constraints, it might learn behaviors that work well for the training feedback but fail catastrophically on slightly different inputs. For example, the policy may generate disproportionate bold words or emoji to please the learned reward (Zhang et al., 2024). Hence, the KL-regularization between the learned policy and a reference policy (the pre-trained model after supervised fine-tuning) plays a fundamental role in RLHF to avoid overfitting. There is a line of theoretical RLHF work that modeled the problem as a reverse-Ke KL regularized contextual bandit (Xiong et al., 2024a; Ye et al., 2024a: Zhong et al., 2024; Wu et al., 2024; Xie et al., 2024). However, they adopt the techniques from contextual bandits and neglect the power of reverse- KL- regularization, thus obtaining almost the same (1)/²²) sample complexity as learning objectives without Kl--regularization Therefore, the question of
whether there exists a fundamental distinction between bandit learning objectives with and without KL-regularization
is still largely under-explored.
Additionally, an emerging line of offline RLHF literature highlights the coverage of the reference policy To. The coverage of Ta refers to the ability of the model to generate diverse responses for a wide range of prompts. A model with good coverage can generalize well to unseen contexts and actions, which is essential for the learned reward function to also generalize well. In practice, this is evidenced by the fact that the simple best-of-n sampling based on xo is competitive with the well- tuned PPO algorithm for general open-ended conversation tasks (Dong et al., 2023), and the fact that the To can solve majority of the math problems with multiple responses (Shao et al., 2024; Nakano et al., 2021). While the coverage of To is recognized as a key factor in offline RLHF, its impact on the sample complexity of online RLHF is still largely unknown. Thus, it is natural to ask:
If online RLHF is theoretically more efficient than offline RLHF under strong coverage of mo?
In this paper, we answer the above questions by (1) providing a novel fine fine-grained decomposition for the suboptimiality of objective functions, which adapts to the strongly convex optimization land- scape of the reverse-KI. KL regularization and obtains a sharper sample complexity than the existing results, and (2) proposing an efficient 2-stage mixed sampling strategy for online RLHF with good coverage of no. which achieves sample complexity with only an additive dependence on the coverage coefficient. In contrast, the existing RLHF algorithms typically require a multiplicative dependence on the coverage coefficient.
1.1 Our Contributions
In this work, make first attempt to illustrate the statistical benefits of KL-regularization for contextual bandits and RLHE, Our main contributions are summarized as follows:
In Section 2, we study the contextual bandit problem with KL-regularization, which also serves as a mathematical formulation for RLHF with absolute-rating feedback. We provide lower bound for the KL.-regularized contextual bandit problem, which indicates that the sample complexity of the problem is ( log Nx (c)fe) when is sufficiently small, where NR(() is the covering number of the reward function class and y is the KL-regulaiization coefficient.
For simplicity, we omit here the dependencies on quantities other than

---

We povide novel analysis to upper bound the suboptimality gap of the KL-regularized objective in contextual bandits, and propose a simple two-stage mixed sampling strategy to achieve a sample complexity of O (1ax (2 m//e) log NR (e()/)) when the reward scale is a constant, where 1) is the coverage coefficient of the reference policy mo and is the confidence parameter. To the best of our knowledge, this is the first work to provide an (1/ec) sample complexity for KL--regllarized contextual bandits.
In Section 3, we extend our analysis to RLHE. We rigorously demonstrate that KL-regularization is essential for more efficient policy learning in RLHF with preference data. We further propose a two-stage mixed sampling strategy for online RLHF with good coverage of To: which achieves sample complexity of ((max(1)) D2, / log NR (</6)) when the reward scale is a constant.
In Appendix C, we consider the setting where the coverage condition is not satisfied. We show that an active querying subroutine can be used to improve the coverage of the collected data in the first stage, which can be combined with our two-stage mixed sampling strategy to achieve sample complexity of Odllog Nx (c/ / /c), where d is the eluder dimension (Russo and Van Roy, 2013) of the reward function class.
1.2 Previous Understanding of KL Regularization in RL
Our analysis of KL-regularized contextual bandits and RLHF also contributes to the theoretical understanding of the impact of KL-regularization in RL since contextual bandits can be viewed as simplified version of Markov decision processes (MDPs). In RI., -l-regularivation has been widely used to stabilize the learning process and prevent the policy from deviating too far from the reference policy. Here, we provide a brief overview of the existing understanding of KL-regularization in mecision-making problems. From the perspective of policy optimization, KL-regularizztion captures entropy regularization as special case 2, which is also an extensively used technique in RL literature (Sutton, 2018; Szepesvári, 2022). There is a large body of literature that has explored the benefits of entropy regularization or KL-regularization in RL (Schulman et al., 2015; Fox et al., 2016; Schulman al., 20;7a; Haarnoja et al., 2017, 2018; Ahmed al., 2019). Most related to our work, Ahmed et al. (2019) provided a comprehensive understanding of the role of entropy regularization in RL, showing that entropy regularization can improve the training efficiency and stability of the policy optimization process by changing the optimization landscape through experiments on continuous control tasks (Brockman, 2016). Theoretically, Neu et al. (2017) provided a unified view of entropy regularization approximate variants of Mirror Descent or Dual Averaging, and left the statistical justification for using entropy regularization in RL as an open question. Geist et al. (2019) provided a framework for analyzing the error propagation in regularized MDPs, which also focused on the proof of the convergence for the policy optimization methods with regularization and lacked a sharp sample complexity analysis.
2 KL--Regularieed Contextual Bandits
In this section, we formally define the KL-regularized contextual bandit problem and provide a lower bound for the sample complexity of the problem. We then propose novel two-stage mixed sampling strategy for online regularized bandits with good coverage of the reference policy no.
2.1 Problem Setup
In the contextual bandit setting, in each round the agent observes a context 2; X generated from a distribution do and chooses an action a; E A. The agent receives a stochastic reward r, E TR. depending on the context 24 and the action a; The goal to maximize the expected cumulative reward over T rounds.
The learner has access a family of reward functions R00, x a) parameterized by 0 E O, such that there exists 0, E θ satisfying E[r [1,,, 4]a] = R(O., Ir, a.). WLOG, we assume that the reward feedback r, at all rounds is non-negative real number bounded by B. We consider KL-regularized
We can regard the entropy regularization as a special case of KL-regularization by setting the reference policy the uniform distribution.
3

---

objective as follows:
TT (aaa)) (o(a
( =Bwdoo (l)x)) R(0,, n log
(2.1)
where no is a known fixed policy, and v > is a hyperparameter that controls the trade-off between maximizing rewards and staying close to the reference policy mo-
Remark 2.1. In RLHF with the absolute-rating feedback, we can directly measure the quality of the responses by querying absolute reward value. For instance, in the NVIDIA Helpsteer project (Wang et al., 2023b, 2024c), human labelers are required to provide absolute score in five attributes: helpfulness, correctness, coherence, complexity, and verbosity.
The absolute-rating feedback is directly modeled as the stochastic reward in the contextual bandit setting (Wang al., 2024a; Xiong et al., 2024b). Under the online RLHF setting, in each round t, the learner observes prompt (modeled as the contex() and chooses a response a, (modeled as the action). The learner then updates the model (policy) based on the absolute-rating feedback.
Remark 2.2. It is worth noting that entropy or Kullback-Leible (KL) regularization is also widely used in contextual bandits (Berthet and Perchet, 2017; Wu et al., 2016) and deep RL algorithms (Schulman et al., 2015; Fox et al., 2016; Schulman et al., 2017a; Haarnoja et al., 2017, 2018), where KL-divergence regularization is popular technique for preventing drastic updates to the policy. Al- gorithms such as Trust Region Policy Optimization (TRPO) (Schulman et al., 2015) explicitly incor- porate KL-regularrzztion to limit the policy updates during optimization, ensuring that the updated policy does not deviate too much from the current policy. This constraint promotes stable and reli- able learning, partieularly in high-dimensional state-action spaces. Additionally, KL-regularization is central to Proximal Policy Optimization (PPO) (Schulman et al., 2017a), where a penalty term involving KL-divergence ensures updates remain within "trust region".
Reward function class ability, we assume that the ground truth reward function R(O,, a) is in the function class R. Then, define the covering number of R follows.
We consider function class R = (R(0. : 11 Q) and for the realiz-
Definition 2.3 (e-cover and covering number). Given function class F, for each e 0, an e- cover of F. with respect to || llx. denoted by C(F,e), e), satisfies that for any ʃ E F, we can find I' C(F,e) such that ||ʃ -''l I e. The e-covering number, denoted Nexe), is the smallest cardinality of such C(F,e).
Planning oracle Given a reward model, we can learn the policy by optimizing the KL-regularized objective in (2.1). To simplify the analysis, we assume that there exists a planning oracle, which in empirical can be efficiently approximated by rejection sampling (Liu et al., 2023), Gibbs sampling (Xiong al., 2024a), and iterative preference learning with known reward (Dong et al., 2024).
Definition 2.4 (Policy Improvement Oracle). For reward function R(O,-.-) e R and a reference policy To, for any prompt æ ~ dg. we can compute:
(-(+)) argmax Ba-x(1)) [((0, a) n log T(alx) ((())E((A)
no(-|x)) exp (n :)) Ta(a)>)
Hence, the comparator policy is the solution to the oracle given the true reward function R(e T (+l-)) x no(-)-)-ese ex))))(xpp((.... ((... :)).. The goal is to minimize the oottmmattllyty of our learned policy π with respect to " Q(==)((===)))))) (()).
Coverage conditions It is crucial to assume that our data-collector policy Ru possesses good cov- erage, which can ensure that the learned reward function can generalize well to unseen contexts (prompts) and actions (responses), and thus can enable us to approximate the optimal policy.
Definition 2.5 (Data Coverage). Given reference policy no. D is the minimum positive real number satisfying V (I, a) E X' x A, T(alx)) > 0, we have for any pair of 0, 0f E e,
[R(O', Iz, a) R(0, x, a]}2
Eyg Aody ( [R(0', (R'(0'x'', af) R(B, x², aa))a $ D2

---

The coverage coefficient D measures how well the in-sample error induced by distribution dg x Tо can characterize the out-of-sample error. This concept is adapted from the F-design for online RL under general function approximation (Agarwal et al., 2024), and follows the coverage coefficient for offline RL (Di et al., 2023; Ye et al., 2024b), and the eluder dimension (Wang al., 2020; Ye al., 2023; Agarwal et al., 2023; Zhao et al., 2023a) for online RL. Take the linear model as an example, where the reward functiin is embedded into a d-dimensional vector space: R(0, æ a) = 0 60 a) ())(xxa)))) a) Then, the coverage condition turns into supa, ge (0"-0) - 2100 [0) S |, a) S D2, where the first inequality uses the Cauchy-Schward inequality. Hence, this quantity measures how much does the reference policy covers all directions of the feature space, and we can show that there exists To such that D = ((d through G-optimal design (Zhang, 2023; Lattimore and Szepesvári, 2020).
for 0 E Rd. Let the covariance matrix Σ
110'-0) "0'=0)"((raa)1 "(
2.2 Lower Bound
In this subsection, we provide lower bound for the KL-regularized contextual bandit problem.
Theorem 2.6. For any < E (0, 1/256), 7) > 4, and any algorithm A, there exists a KI.-regularized contextual bandit problem with reward function class RR and (c))(c)) data coverage coefficient (as defined Definition 2.5) such that A requires least 22 min yo (c). (og )) rounds to achieve a suboptimality gap of e.
Remark 2.7. The lower bound in Theorem 2.6 indicates that the sample complexity of the KL- regularized contextual bandit problem is (11 log (e)e))e) when e is sufficiently small. In our proof, the KL-regularization term shifts the local landscape of the objective function, which prevents us to directly apply the standard bandit analysis, and thus requires novel analysis to derive the new lower bound. This (2(1) log NR (c)/c) lower bound suggests that the KL-regularized contextual bandit problem potentially enjoy a lower sample complexity compared to the standard contextual bandit.
2.3 The Proposed Algorithm
We present our algorithm in Algorithm 1 for the KL-regularized contextual bandit problem, which serves theoretical model for online RLHF with absolute-rating feedback. The algorithm consists of two stages:
the first stage, we sample m contexts (prompts) and actions (answers) from the foundation model mo and observe the corresponding rewards (absolute ratings). These ratings can be regarded as noisy observations of the underlying reward function R(0., x. a). In line 6, we compute an estimate of the reward function Oo using least squares regression based on the collected data. which maximizes the following In line 7, we apply the planning oracle obtain the policy "0
KL-regularized estimated objective in Definition 2.4 with reward function R(0,,,) = R(0o, ::).
In the second stage, we utilize the trained policy Th to sample contexts (prompts) and actions (responses). With the intermediate policy T we can collect new data {(z,, a,, r=) which is more aligned with the data distribution induced by the optimal policy n. In line 13, the algorithm combines data from both stages {x,, a,, pr and {(=f, aq, ? to compute a refined least squares estimate 0 of the reward function, minimizing the sum of squared enrors across both datasets. By aggregating the two datasets together, there an overlap between the data to compute i and fg. so that the output policy n² is well covered by the intermediate policy Th
2.4 Theoretical Guarantees
Review of previous analysis The previous analysis (e.g., Xiong et al., 2024a) basically follows the techniques of bandits and neglects the significance short-hand notation R(O, I, π) = [a--r(ll>) R(0, x, a) and denote [=) when there is no confusion. We make the estimation on a dataset {(x,, r,, 2, do. 0g ~ To( (r:)) Th argmaxxen Ezwd, [R(0,ar, ar, T) 17 (T.(((T))))))) and has a small in-sample-
SL-rrgularization. For simplicity. We use
by KL(T|(=²)
5

---

to sample new responses Algorithm Two-stage Mixed-Policy Sampling (TMPS)
1: Input: 1), E, To. O
b Stage 1: Use policy To to achieve sufficient data coverage
2: for i= l.......
do
3: Sample context z ~ dg and action of ~ mo(-|>=?)
4: Observe reward r R(0,, x a eg, where ef is the random noise.
5: end for
6: Compute the least square estimate of the reward function based Do (frf, rf)))))))=
0o < argmin AE
[R(0, a.) - -r
7:
Apply the planning oracle compute n! (+1)) no(+))) exp(n
Stage 2: Use policy n² 88g
8:
9: for == do
10:
Sample context x, dg and action a, 00g (-|2rg)-
11: Observe reward r; R(O., 3i, 0i) + ti. where e; is the random noise.
12:
end for
13:
Compute the least square estimate of the reward function using ((r), dz, ri) together with Do:
Ø + argmin DEB
(R(0 x..aa a.) 19)2 + Σ [R(8,x;, - -r,)²
14:
Output (-)+)) no(-I-) (xp(F))))
error:
Exwd, BB (1 (R(0, R(,,,, I, a)) = O(L/n). The sub-optimality decomposed
Q(T*) - Q(T
= Egwdo
[R(0. 2, n, x²) R(0, x, x²)] Ex-dd [ x. TT - RR(O I, x3)]
+ Ez dg
[ x π²) 11 KL [[T)]] - Egodo [R x, TT)) - -KL( (T
< Egwdo [R(O,, (.,,T"")) R(,,, n,) + R(O,, x, TTy) - II,
where the inequality holds since 7 is the maximum.
Then, the suboptimality be further bounded by using the coverage condition (Definition 2.10)
and concentration inequalities:
-(m")-Q((+) ((x))) 22CGLE (- R(0,, R(( a)l]
<2CGL V (Ennoo (n) [R(6,, 2, a) R(0, a)) O(CaL/Vm Vn).
Hence, they need (( sample complexity to ensure O(e) sub-optimility.
Sharper results and analysis
Theorem 2.8. Suppose that Assumption 2.5 holds. For any d (0.1/5), > 0 and constant Cm,n > 0, if we set m = 0 n2 B²
and n = ( B2 log(NR(<s))/0)) and 6 = mmnn 2m1 )8* 1B, Da }. then with probability at least 1 - 55 the output policy of Algorithm T (cc) optimal.
Theorem 2.8 shows that the sample complexity of Algorithm 1 is O log NR(c/ when the reward scale is constant and is sufficiently small. The result indicates that the proposed two-stage mixed sampling strategy can achieve suboptimality gap with only an additive dependence on the coverage coefficient D
To illustrate the novel techniques to obtain the sharper bound, we highlight the erucial points in the sequel and defer the detailed proof to Appendix E.2.

---

Part I: Decomposition of the suboptimality gap The most challenging part is how to pro- ceed with the suboptimality gap based on the strong convexity of the objective with the KL- regularization. Given the closed-form solution of x =a(az) = no (1))))
a) a)) (x) and
(a(() = To (o(a)) exp(n) x. a)) Z where (z) = EnEA ma(aka) exp(7R(0,,z,0))
denotes the normalization constant, we can write the suboptimality
R(O., 2, a) log " (a(x)
Rx log (a(a 1 B. log To(a|z) exp(n [.)]]
[o(a Bg
"
1 Bag log To To(a exp(n)((.., x, a
17
x² <a(2))
17
0 x2(((z)
(J(x00 (();
where we define J (a;; 0) log Zz - T [R(O, x, a) IM,,,, a)}, and the last equation is deduced by taking the distribution of πt and g in the terms.
Thus, the suboptimality is expressed by the gap between i and 0, with respect to the function J. By taking the first-order Taylor expansion with respect to { (A(z, a) = R(0, 2, a) - R(0.. x. a) A}, we can prove the following lemma.
Lemma 2.9. For any estimator E O, and the policy To satisfying Definiton 2.4, we have
((*') Q(T))) Pa
Σ
E
aEA
a1.03EA
Σ
(T((l=)
(2.2)
GEA
R(A.. ..)) (r E (0.1)) 1)) the inequality uses the fact that second term on the right-hand side the equality (C 7 ())()))) O.
where f(.,-) = - (0. .) +
The proof of this lemma provided in Appendix E.2.
Part II: Utilizing the coverage condition In Algorithm 1, with the coverage condition (Defini- tion 2.5) and the concentration inequalities, if the sample size O17² D²), can prove that || ... -)l S n and [[((,...)) R(O.. .loo S . which implies the whole- policy coverage condition for all contexts: 1-)((1-)// (+))lx I e² Therefore, substituting it back
into (2.2) leads to
Q(T))) - Q(=z) Q(= S Bnla B [ 2, - R(0,,I, a)
Note that 0 in the RHS is computed using the data sampled from n By setting O(n/e), we obtain that oy is Oe)) optimal.
2.5 Result under Local-Coverage Condition
In this subsection, we consider another coverage conditions appearing in previous work as described in Definition 2.11.
Definition 2.10 (Global-Policy Coverage). Given a reference policy To. CGL is the minimum posi- tive real number satisfying that for any π X ((A)
Taaxx)
sup andd AEA To(a)z)
< CGL.
Definition 2.11 (Local KL-ball Coverage, Song et al. 2024). Given reference policy no. for positive constant PKL. < oc, and all policy satisfying that Exed, [KL(T, To)] S PKL. we define
T(ap))
sup a To (a/z)
CpRa.
7

---

Remark 2.12 (Relation between Local and Global Coverage Conditions), The local-coverage con- dition (Definition 2.11) more precise because compared to the global conditions targeting all possible policies, it only constrains the coverage to a KI.-balI. In Song et al. (2024), because of the specific form of the oracle (Definition 2.4), the considered policy class IT = (-(-))) x To(-I-) exp(n
R(O, :) E RJ. Thus, they only need to assume that the condition hold for p = Br indicating that Coga. I CGL. On the other hand, the data coverage condition (Definition 2.5) is measured on the level of reward functions instead of policies. In this sense, the data coverage condition and local-coverage condition do not encompass each other.
Corollary 2.13. Let OpEL be in Definition 2.11 where PKL 2nB.. For any å E (0, and e 0, if we set Cm ((Cpkt 17/'E B (e (E))/8)) (where constant Cm,n > 0. C c/(2(1 + (m.n))) then with probability at least 1 66 the output policy of Algorithm 3 my is
(e) optimal.
In comparison with the sample complexity @(1 + r//e) under data coverage Theorem 2.8, the order ((Cpkt/// r)/e) depends on a local coverage coefficient CpeL. but has multiplicative depen- dence on the coverage coefficient instead of additive dependence. Whether the additive dependence can be achieved under the local-coverage condition is left as future work. Moreover, compare this result with Theorem 4.2 in Song et al. (2024) and suppose that the in-sample-error ereward of Song al. (2024) is O(1/n), their sample complexity is ( pKa /c2,, which is looser than ours (CCpsi. (CCpp..)/ n/c) when o pk).../))
3 Reinforcement Learning from Preference Feedback
In this section, we consider the problem of aligning the language model with preference feedback.
3.1 Problem Setup
In each round, we can sample a pair of actions (responses) (11 dg and query a preference oracle to get the preference label y E {0, 1}, where = 1 means that the user prefers a1 over a2. Specifically, when receiving a prompt x E X. and two actions (responses) a aa E from some LLM policy (-|2x), a preference oracle will give feedback y defined as follows:
Definition 3.1 (Preference Oracle). A Preference Oracle is function P A A + {0, 1). Given a context x E X' and two actions a1, a2 E A. the oracle can be queried to obtain a preference signal y Bernoulli 41, a2)), where y 1 indicates that a1 is preferred to 02 in the context x, and = 0 indicates the opposite.
To learn the preference, we follow Ouyang et al. (2022); Zhu et al. (2023); Rafailov et al. (2024); Liu et al. (2023); Xiong et al. (2024a) and assume that the preference oracle is measured by the difference of ground-truth reward functions R(0,, x, a), which is named the Bradley-Terry (BT) model (Bradley and Terry, 1952b).
Definition 3.2 (Bradley-Terry Model). Given a context & E X and two actions a,, A, the probability of a being preferred to a2 is modeled as exp( exp(R(O.,,r,, a1)))
(1, 01, 02) = exp(R R( x. a1)) ))-))))))))))))))) + cxp( 20,,,
(R(O,, 2, x, (3.1)
where a (u) (1 e -)1 is the sigmoid function.
The RLHF training always follows the fine-tuning process, which yields reference policy To- When performing RLHF on specific tasks, to avoid overfitting, we impose KL-regularization to the learned reward model when optimizing the policy. Hence, our objective function is also (2.1).
To learn the reward function, we introduce the following assumption to ensure the existence of an MLE estimation oracle that can globally maximize the likelihood of the BT model over all possible reward functions.
Definition 3.3 (MLE estimation oracle). Given a set of context-action pairs ((ri, a,, , at m1 V=
generated from the BT model, can output the parameter such that
i arrgmax PEB
y: log ((H(e, 2,, of) R(0, v, )z + - wi log (H(0,, v., of) R(0, x., af)) 2(0)x .f.
8

---

Following the previous analysis for RLHF (Xiong et al., 2024a), we assume the existence of a policy improvement oracle (Definition 2.4) that can compute the optimal policy oz based on the reward
function 0.
Remark 3.4. We learn the reward function since can always control the reward (like clipping and normalization) to ensure that the reward function is always bounded by B. The bounded assumption does not apply for direct preference learning like DPO (Rafailov et al., 2024) since there is no intrinsic policy function class encompassing the soundness (Song et al., 2024), thus increasing the cases of overfitting
In RLHF setting, we cannot directly observe or estimate absolute reward values. Consequently, the most intuitive estimation approach is to focus relative rewards: for any context and actions a' a², our estimated difference f(s, a²) f(s, a²) should closely approximate the true reward difference r(s. -rss Therefore, extend the data coverage condition to the RLHF setting as follows.
Definition 3.5 (Data Coverage). Given reference policy no, D2 is the minimum positive real number satisfying A (x) E X' x A, x(a|z) > O, we have for any pair of 0, 0' E O, there exists 6: X [- B] such that
R(0', x. R(0, x. a) b(x)1
E g' Var (ala'mu((12")) RR(0' x², ad) - R(0, x', S
3.2 Theoretical Guarantees
Lower bound We provide a lower bound for the RLHF problem with preference feedback. The lower bound is derived by constructing hard instance where the reward function is difficult to estimate from the preference feedback.
Theorem 3.6. For any E (0, 1 1/256), v/ > 4. and any algorithm A, there exists a KL-regularized preference learning problem with (eNr(e)) coverage coefficient and reward function class R such that A requires at least O min(" log (c) log Nog,N((c) Nz)())) samples to achieve suboptimality gap of c.
e²
We present two-stage mixed-police sampling algorithm for RLHF, which can be seen as an exten- tion of Algorithm 1. Due to space limit, we defer it to Algorithm 3 in Appendix D.
Upper bound We provide the theoretical guarantees for Algorithm 3 in the following theorem. Theorem 3.7. Suppose that Assumption 2.5 holds. For any 8 E (0, 1/6) and > 0, if we set
m=0 D2 eB log (ogg(NR(.))) (c.)/6)) and n (n/ e log(NR (6))
where 6 = min (.) (ettm,,))e } then with probability at least 1 - 66 the output
policy of Algorithm nT is (e) optimal.
Remark 3.8 (Comparison with Hybrid Framework). We compare our two-stage mixed sampling method with hybrid RL. From the algorithmic perspective, a hybrid RL algorithm first Iearns from an offline dataset and then requires sufficient online iterations to ensure the performance (Xiong al., 2024a). For example, for finite action space with A actions, the number of online iterations should be (A)) In contrast, our method only requires two iterations of sampling from mixed policy and interacting with the environment. Moreover, the results of hybrid literature depend on both the coverage coefficient and the structure complexity of the function class (like the dimension for linear function class or eluder dimension (Russo and Van Roy, 2013)). Our result only needs the coverage condition of the reference policy. More importantly, we obtain sharper bound on the sample complexity and derive the additive dependence on the coverage coefficient.
Remark 3.9. Although the coefficient e appearing in sample size m, can be exponentially large, this term is caused by the mon-linearity of the link function for the preference model, and is common in RLHF literature (Zhu et al., 2023; Xiong et al., 2024a; Ye et al., 2024a; Song et al., 2024).
Theorem 3.7 shows that the sample complexity of Algorithm 3 is O(n/e e log (e()/)) when the reward scale is constant and is sufficiently small. The result indicates that the proposed two-stage mixed sampling strategy can achieve a suboptimality gap of with only an additive dependence on the coverage coefficient 2

---

Besides. the algorithm only requires sampling from the reference policy and the intermediate policy n/ "6' which is more aligned with the practical scenarios where the preference feedback is collected from the human users and it is expensive to collect the data while the language model is being updated. Our result implies that we may achieve a near-optimal sample complexity by simply leveraging an intermediate policy to collect more data, and the training process of the reward model and the policy (language model) can highly decoupled.
Upper bound for local coverage We also show the result under the local-coverage assumption (Definition 2) as follows.
Corollary 3.10. Let CoaL be Definition 2.11 where p = Bn For any E (0, 1/6) and e > 0, if we set n = Cm.afl (Kpp 9//e- BB (og((R((e))) (Nx())))))) (where constant Cm.. > 0, 6
2( 2(1+mmm then with probability at least 1 65 the output policy of Algorithm 3 n is ((e) 0
optimal.
4 Conclusions and Future Work
We have presented a comprehensive theoretical analysis of the role of reverse- regularization in decision-making models including contextual bandits and reinforcement learning from preference feedback, highlighting its significance in terms of sample complexity. Our results provide new in- sights into the power of regularization extending beyond its traditional role of mitigating errors from the current critic (or reward) model. Additionally, we examined the role of data coverage in both contextual bandits and RLHF. Our analysis shows that with sufficient coverage from the reference policy, a mixed sampling strategy can achieve a sample complexity that exhibits only an additive dependence on the coverage coefficient without the need for explicit exploration additional struc- tural assumptions. For future directions, it is interesting to study if the sharp bound exists for the KL-regularized Markov Decision Process (MDP) problem. Additionally, also worthwhile to explore how to achieve sample complexity bound with only additive dependence on the global and local coverage conditions in Definitions 2.10 and 2.
Acknowledgment
We thank the anonymous reviewers and area chair for their helpful comments. HZ and QG supported in part by the National Science Foundation DMS-2323113 and IIS-2403400. This work also partially supported by NSF grant No. 2416897 and ONR grant No. N000142512318. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.
References
ACHIAM, J., ADLER, S., AGARWAL, S., AHMAD, L., AKKAYA, I., ALEMAN, F. L., ALMEIDA, D., ALTENSCHMIDT, J., ALTMAN, S., ANADKAT, S. ET AL. (2023). Gpt-4 technical report. arXiv preprint arXiv:2303.08774.
AGARWAL, A., JIN, Y. and ZHANG, T. (2023). Vo ql: Towards optimal regret in model-free rl with nonlinear function approximation. In The Thirty Sixth Annual Conference on Learning Theory. PMLR.
AGARWAL, A., KAKADE, S. M., LEE, J. D. and MAHAJAN, G. (2020). Optimality and approx- imation with policy gradient methods in markov decision processes. In Conference on Learning Theory. PMLR.
AGARWAL, A., KAKADE, S. M., LEF, J. D. and MAHAJAN, G. (2021). On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research 22 1-76.
AGARWAL, A., QIAN, J., RAKHLIN, A. and ZHANG, T. (2024). The non-linear f-design and applications to interactive learning. In Forty-first International Conference Machine Learning.
10

---

AHMED, Z., LE ROUX. N., NOROUZI, M. and SCHUURMANS, D. (2019). Understanding the im- pact of entropy on policy optimization. In International conference on machine learning. PMLR.
ANTHROPIC, (2023). Introducing claude.
AZAR, M. G., GUo, Z. D., PIOT, B.. MUNOS, R., ROWLAND, M.. VALKO, M. and CALAN- DRIELLO, D. (2024). A general theoretical paradigm to understand learning from human prefer- ences. In International Conference on Artificial Intelligence and Statistics. PMLR.
BAI, Y., JONES, A., NDOUSSE, K., ASKELL, A., CHEN, A., DASSARMA, N., DRAIN, D., FORT. S., GANGULI, D., HENIGHAN, T. ET AL. (2022). Training a helpful and harmless assistant with reinforcement learning from human feedback. arXiv preprint arXiv:2204. 05862.
BERTHET, Q. and PERCHET, (2017). Fast rates for bandit optimization with upper-confidence frank-wolfe. Advances in Neural Information Processing Systems 30.
BRADLEY, R. A. and TERRY, M. E. (1952a). Rank analysis of incomplete block designs: I. the method paired comparisons. Biometrika 39 324.
BRADLEY, A. and TERRY, M. E. (1952b). Rank analysis of incomplete block designs: the method of paired comparisons. Biometrika 39 324-345.
BROCKMAN, G. (2016). Openai gym. arXiv preprint arXiv:
CALANDRIELLO, D., GUO, D., MUNOS, R., ROWLAND, M., TANG, Y., PIRES, B. A.,
RICHEMOND, H., LAN, C. L.. VALKO, M., LIC. ET AL. (2024). Human alignment of large language models through online preference optimisation. arXiv preprint arXiv:2403.08635
CHEN, Z., DENG, Y., YUAN, H., K. and GU, Q. (2024). Self-play fine-tuning converts weak language models to strong language models. arXiv preprint arXiv:2401.01335
CHRISTIANO, P. F., LEIKE, J., BROWN, T., MARTIC, M., LEGG. S. and AMODEI, D. (2017). Deep reinforcement learnin from human preferences. Advances in neural information processing systems 30.
COBBE, K., KOSARAJU, V., BAVARIAN, M., CHEN, M., JUN, H., KAISER, L., PLAPPERT, M., TWOREK, J., HILTON, J., NAKANO, ET AL. (2021). Training verifiers solve math word problems. arXiv preprini 10Xiv:2110.14111
DI, Q., ZHAO, H., HE, J. and GU, Q. (2023). Pessimistic nonlinear least-squares value iteration for offline reinforcement learning. arXiv preprint arXiv:2310.01388
DONG, H., XIONG, W., GOYAL, D., ZHANG, Y., CHOW, W., PAN, R., DIAO, S., ZHANG, J., SHUM, K. and ZHANG, T. (2023). Raft: Reward ranked finetuning for generative foundation model alignment. arXiv preprint wrxiv:2304.06767
DONG, H., XIONG, W. PANG, B.. WANG, H., ZHAO, H., ZHOU, Y., JIANG, N., SAHOO, D., XIONG, C. and ZHANG, T. (2024). Rlhf workflow: From reward modeling to online rlhf. arXiv preprint arXiv:2405.0788.
FOSTER, D. J., KAKADE, M., QIAN, J. and RAKHLIN, A. (2021). The statistical complexity of interactive decision making. arXiv preprini 11.
Fox, R., PAKMAN, A. and TISHBY, N. (2016). Taming the noise in reinforcement learning via soft updates. In 32nd Conference on Uncertainty in Artificial Intelligence 2016, UAI 2016. Association For Uncertainty in Artificial Intelligence (AUAI).
GEIST, M., SCHERRER, B. and PIETQUIN, O. (2019). A theory of regularized markov decision processes. In International Conference on Machine Learning. PMLR.
Gou, Z., SHAO, Z., GONG, Y., YELONG SHEN, YANG, Y., HUANG, M., DUAN, N. and CHEN, W. (2024). ToRA: A tool-integrated reasoning agent for mathematical problem solving. In The Twelfth International Conference on Learning Representations. URL https: http///pppeeviieeeeee wwt.rriiweeeeeeeeeeeeeeee wwwp//eettttnnnee aett//oormm/d--ppoti.ooooo.

---

GUI, L., GÁRBACEA, C. and VEITCH, V. (2024). Bonbon aligmment for large language models and the sweetness of best-of-n sampling, arXiv preprint wxXiv:2406.00832.
GULCEIREE C., PAINE, T. L., SRINIVASAN, S., KONYUSHKOOA, K., WEERTS, L., SHARRM,, A., SIDDHANT, A., AHERN, A., WANG, M., GU, C. ET AL. (2023). Reinforced self-training (rest) for language modeling. arXiv preprint arXiv:2308.08998
GUO, S., ZIANG, B., LIU, T., LIU, T., KHIALMAN, M., LLINARES, F., RAME, A., MESNARD, T., ZIIAO, Y., PIOT, B. ET AL. (2024). Direct language model alignment from online ai feedback. arXiv preprint arXiv:2402.04792.
HAARNOJA, T., TANG, H., ABBEEL, P. and LEVINE, S. (2017). Reinforcement learning with deep energy-based policies. In International conference on machine learning. PMLR.
HAARNOJA, T., ZHOU, A., ABBEEL,, and LEVINE, S. (2018). Soft actor-critic: Off-pooicc max- imum entropy deep reinforcement learning with stochastic actor. In International conference machine learning. PMLR.
HENDRYCKS, D., BURNS, C., KADAVATH, S., ARORA, A., BASART, S., TANG, E., SONG, D. and STEINHARDT, (2021). Measuring mathematical problem solving with the math dataset. arXiv preprint arXiv: 103.03874
LAN, G. (2023). Policy mirror descent for reinforcement learning: Linear convergence, pling complexity, and generalized problem classes. Mathematical programming 198 1059-1106.
LANGFORD, J. and ZHANG, T. (2007). The epoch- epoch-greedy algorithm for mnulti-armed bandits with side information. Advances in neural information processing systems 20.
LATTIMORE, T. and SZEPESVÁRI, C. (2020). Bandit algorithms. Cambridge University Press.
LIU, T., ZHAO, Y., JOSHI, R., KHALMAN, M., SALEH, M., LIU, J. and LIU, J. (2023). Sta- tistical rejection sampling improves preference optimization. arXiv preprint arX1v:230..06557
MEI, J., XIAO, C., SZEPESVARI, C. and SCHUURMANS, D. (2020). On the global convergence rates of softmax policy gradient methods. In International conference on machine learning- PMLR.
META, A. (2024). Introducing meta llama 3: The most capable openly available Ilm to date. Meta AI.
NAKANO, R., HILTON, J., BALAJI, S., WU, J., OUYANG, L., KIM, C., HESSE, C., JAIN, S., KOSARAJU, V. SAUNDERS, W. ET AL. (2021). Webgpt: Browser-assisted question-answering with human feedback. arXiv preprint arXiv:2112.09332.
NEU, G., JONSSON, A. and GÓMEZ, V. (2017). A unified view of entropy-regularized markov decision processes. arXiv preprint arXiv: FexXivv1775.00 170.007798.
OPENAI (2023). Gpt-4 technical report. ArXiv abs/2303.08774.
OUYANG, L., WU, J., JIANG, X., ALMEIDA, D., WAINWRIGHT, C., MISHKIN, P., ZHANG, C., AGARWAL, S., SLAMA, K., RAY, A. AL. (2022). Training language models to follow in- structions with human feedback. Advances in Neural Informaiinn Processing Systems 35 27730- 27744.
RAFAILOV, R., SHARMA, A., MITCHELL, E., MANNING, C. D., ERMON, S. and FINN, C, (2024). Direct preference optimization: Your language model is secretly reward model. Advances in Neural Information Processing Systems 36.
RUSSO, D. and VAN ROY, B. (2013). Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems 26.
SCHULMAN, J., CHEN, X. and ABBEEL, P. (2017a). Equivalence between policy gradients and soft g-eaarning arXiv preprint arXiv:1704.0666 1704.06440
12

---

SCHULMAN, J., LEVINE, S., ABBEEL, P., JORDAN, M. and MORITZ, P. (2015). Trust region policy optimization. In International Conference on Machine Learning. PMLR.
SCHULMAN, J., WOLSKI, F,, DIIARWWLL, P., RADFORD, A. and KLIMOV, O. (2017b). Proximal policy optimization algorithms. arXiv preprint arXhv:1707.06347
SHANI, L., EFRONI, Y. and MANNOR, S. (2020). Adaptive trust region policy optimization: Global convergence and faster rates for regularized mdps. In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34.
SHAO, Z., WANG, P., ZHU, Q., XU, R., SONG, J., ZHANG, M., LI, Y., WU, Y. and GUO, (2024). Deepseekmath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03300
SONG, Y., SWAMY, G., SINGH, A., BAGNELL, D. and SUN, W. (2024). The importance of online data: Understanding preference fine-tuning via coverage. In ICML 2024 Workshop: Aligning Reinforcement Learning Experimentalists and Theorists
SUTTON, R. S. (2018). Reinforcement learning: An introduction. A Bradford Book
SZEPESVÁRI, C. (2022). Algorithms for reinforcement learning. Springer nature.
TEAM, G., ANIL, R., BORGEAUD, S., WU, Y., ALAYRAC, J.-B., Yu, J., SORICUT, R., SCHALK-- WYK, J., DAI, M., HAUTII, A. ET AL. (2023). Gemini: a family of highly capable multimodal models. arXiv preprint arXiv:2312.11880
TONG, Y., ZHANG, X., WANG, R., WU, R. and HE, (2024). Dart-math: Difficulty rejection tuning for mathematical problem-solving, arXiv preprint arXiv:2407.13660
TOUVRON, H., MARTIN, L., STONE, K., ALBERT, P., ALMAHAIRI, A., BABAEI, Y., BASH- LYKOV, N., BATRA, S., BHARGAVA, P., BHOSALE, S. ET AL. (2023). Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288
WANG, H., LIN, Y., XIONG, W., YANG. DIAO, S., QIU, S., ZHAO, and ZHANG, (2024a). Arithmetic control of lims for diverse user preferences: Directional preference alignment with multi-objective rewards. arXiv preprint arXiv:2402.18557
WANG, H., XIONG, W., XIE, T., ZHAO, H. and ZHANG, T. (2024b). Interpretable preferences via multi-objective reward modeling and mixture-of-expert. arXiv preprint arXiv:2406.111 12845.
WANG, R., SALAKHUTDINOV, R. R. and YANG, L. (2020). Reinforcement learning with gen- eral value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems 6123-6135.
WANG, Y., LIU, Q. and JIN, C. (2023a). rlhf more difficult than standard rl? a theoretical perspective, Advances in Neural Information Processing Systems 36 76006-76032.
WANG, Z., DONG, Y., DELALLEAU, O., ZENG, J., SHEN, G., EGERT, D., ZHANG, J. J., SREED- HAR, M. N. and KUCHAIEV, O. (2024c). Helpsteer2: Open-source dataset for training top- performing reward models. arXiv preprint arXiv:2406.0861
WANG, Z., DONG, Y., ZENG, J., ADAMS, V., SREEDHAR, M. N., EGERT, D., DELALLEAU, O., SCOWCROFT, J. P., KANT, N., SWOPE, A. ET AL. (2023b). Helpsteer: Multi-attribute helpfulness dataset for steerlm. arXiv preprint arXiv:2311.09528
WU, Y., SHARIFF, R., LATTIMORE, T. and SZEPESVÁRI, C. (2016). Conservative bandits. In International Conference Machine Learning. PMLR.
WU, Y.. SUN, Z., YUAN, H., J1, K., YANG, Y. and Gu, Q. (2024), Self-play preference optimiza- tion for language model alignment. arXiv preprint arXiv:2405.0067.
XIE, T., FOSTER, J., KRISHNAMURTHY, A., ROSSET, C., AWADALLAH, A. and RAKHLIN, A. (2024). Exploratory preference optimization: Harnessing implicit q apprroxiiaiiio for sample- efficient rlhf. arXiv preprint arXiv:2405.21045
13

---

XIONG, W., DONG, H., YE, C., WANG. Z., ZHONG, H., JI, H.,, JIANG, N. and ZHANG, T. (2024a). Iterative preference learning from human feedback: Bridging theory and practice for rlhf under kl-constraint. In Forty-first International Conference Machine Learning.
XIONG, W., SHI, C., SHEN, J., ROSENBERG, A., QIN, Z., CALANDRIELLO, D., KHALMAN, M., JOSHI, R.,, PIOT, B., SALEH, M. ET AL. (2024b). Building math agents with multi-tura iterative preference learning. arXiv preprint arXivv2409.02.322
YE, C., XIONG, W., GU, Q. and ZHANG, T. (2023). Corruption- robustt algorithms with uncertainty weighting for nonlinear contextual bandits and markov decision processes. In International Con- ference on Machine Learning. PMLR.
YE, C., XIONG, W., ZHANG, Y., JIANG, N. and ZHANG, T. (2024a). A theoretical analysis of nash learning from human feedback under general kl-regularized preference. arXiv preprint arXiv:2402.07314.
YE, C., YANG, R., GU, Q. and ZHANG, T. (2024b). Corruption-robust offline reinforcement learn- ing with general function approximation. Advances in Neural Information Processing Systems 36.
YUE. Y., BRODER, J., KLEINBERG, R. and JOACHIMS, T. (2012). The k-armed dueling bandits problem. Journal of Computer and System Sciences 78
ZIIANG, T. (2023), Mathematical analysis of machine learning algorithms. Cambridge University Press.
ZHANG, X., XIONG, W., CHEN, L.., ZHOU, T., HUANG, H. and ZHANG, T. (2024). From lists to emojis: How format bias affects model alignment. arXiv preprint arXiv:2409.11704
ZHANG, Z., ZHOU, Y. and JI, X. (2020). Almost optimal model-free reinforcement learningvia reference-advantage decomposition. Advances in Neural Information Processing Systems 33 15198-15207.
ZHAO, H., HE, J. and GU, Q. (2023a). A nearly optimal and low-switching algorithm for rein- forcement learning with general function approximation. arXiv preprint wr.iv:2311.1522:::
ZHAO, Y., JOSHI, R., LIU, T., KHALMAN, M., SALEH, M. and LIU, P. J. (2023b). Slic-hf:
Sequence likelihood calibration with human feedback. arXiv preprini 2tti::2005.14225
ZHONG, H., FENG, G., XIONG, W., ZHAO, L.. HE, D., BIAN, J. and WANG, L. (2024). Dpo
meets ppo: Reinforced token optimization for rlhf. arXiv preprint arXiv:2404. 18922..
ZHU, B., JIAO, J. and JORDAN, M. I. (2023). Principled reinforcement learning with human feedback from pairwise or i- wise comparisons. arXiv preprint arXiv:2301.11270.
ZIEGLER, D. M., STIENNON, N., Wc, J., BROWN, T. B., RADFORD, A., AMODEL, D., CHRIS- TIANO, and IRVING, G. (2019). Fine-tuning language models from human preferences. arXiv preprint arXiv:1909.0852
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We clearly state the contributions of the paper in the abstract and introduc- tion. The main claims are that we provide theoretical analysis of the role of reverse-Ki KL regularization in decision-making models including contextual bandits and reinforcement learning from preference feedback, highlighting its significance in terms of sample com- plexity. We also show that with sufficient coverage from the reference policy, mixed sampling strategy can achieve sample complexity that exhibits only an additive depen- dence on the coverage coefficient without the need for explicit exploration or additional structural assumptions.
14

---

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

---

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

---

The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nip) cc/
onnolicy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips. cc/ httpc//ggiieeeeeeeeuuueeee CodeeSumieiiie sommisiii onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper is purely theoretical with only synthetic experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper is purely theoretical.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of emrrrs is not verified.
17

---

For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative enror rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper is purely theoretical.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental rums well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't ' make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: tttttps://eurre httpp/sccpcpcpccccccececcccceeee
Answer: [Yes]
Justification:
This theoretical research is fully in line with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. g.. there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: The purpose of this research is to advance the theory of reinforcement learn- ing. It may have downstream impacts, none of which is worth specific discussion.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
18

---

The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We believe that our theoretical analysis poses no such risk.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use the model, for example by re- quiring that users adhere to usage guidelines or restrictions to access the model or implementing safery filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
We do not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should provided.
assets are released, the license, copyright information, and terms of use the pack- age should be provided. For popular datasets, paperswi wwwwhcode...e.oooco com/ dataseta has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's ss creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
We do not release new assets.
19

---

Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, well details about compensation (if any)?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Question:
Answer: [NA]
Justification: All the proof techniques in this theoretical research are proposed by human.
Guidelines:
20

---

The answer NA means that the core method development in this research does not involve LLMs as any important. original, non-standard components.
Please refer to our LLM policy (https: : / http///eiincc///ee// /tt.:o/nfeereennee///////// for what should or should not be described.
21

---

A Additional Related Work
Analyses of Policy Optimization with Regularization While it is previously unknown whether regularization can improve the sample complexity of policy optimization without additional assump- tions, there are some works that provided a sharp convergence rate in the presence of regularization (Mei et al., 2020; Shani et al., 2020; Agarwal et al., 2020, 2021; Lan, 2023). However, these works either assumed the access of exact or unbiased policy gradient or required uniform value function ap- proximation error, which are not the standard case in general sample-based RI setting. For instance, Lan (2023) provided a sharp convergence rate for policy optimization with KI KI.-regularization as- suming the access to unbiased value function estimator (Condition 4. and the bounded infinity norm on the error (Conditions 4.2, 4.3). which is standard in the literature of optimization. However, RL algorithms usually make biased estimation balance exploration and exploitation. Instead of focusing on the influence of regularization on the optimization, our work aims to understand how the KL-regularization affects the exploration and exploitation trade-off' in the bandit and RLHF settings through a novel analysis on the optimal sample complexity.
RLHF Algorithms There are mainly three types of RLHF algorithms: offline, online and hyrbid. The most well- offline algorithms Slic (Zhao et al., 2023b), Direct Preference Optimiza- tion (DPO) (Rafailov et al., 2024), Identity-PO (IPO) (Azar et al., 2024) and (SPIN) (Chen et al., 2024). They aim to approximate the closed-form solution of the optimization problem on fixed offline dataset. For the online algorithms. the most representative one is Proximal Policy Optimiza- tion (PPO) (Schulman et al., 2017b). PPO has been used in the Chat-GPT (OpenAI, 2023), Gemini (Team et al., 2023), and Claude (Bai et al., 2022). However, the deep RL method PPO is known to be sample inefficient and unstable, making its success hard to reproduce for the open-source commu- nity. In response to this, there have been many efforts to propose alternative algorithms to the PPO algorithm. The Reward ranked fine-tuning (RAFT) (also known as rejection sampling finetuning) (Dong et al., 2023; Touvron et al., 2023; Gulcehre et al., 2023; Gui et al., 2024) is a stable frame- work requiring minimal hyper- parameter tuning, which iteratively learns from the best-of-n policy (Nakano et al., 2021). This framework proves to be particularly effective in the reasoning task such as (Gou et al., 2024; Tong et al., 2024). However, the RAFT-like algorithms only use the positive signal by imitating the best-of-n sampling. To further improve the efficiency, there is an emerging body of literature that proposes online direct preference optimization by extending DPO or IPO to an online iterative framework (Xiong et al., 2024a; Guo et al., 2024; Wu et al., 2024: Calandriello et al., 2024; Xiong et al., 2024b). Finally, for the third type, the common point of hybrid and online algorithms is that they both require further interaction with the preference oracle and on-policy data collection. The difference is that hybrid algorithms start with a pre-collected dataset (Xiong et al., 2024a; Song et al., 2024; Touvron et al., 2023), while the online algorithms learn from scratch.
RLHF Theory The theoretical study of RLHF can date back to the dueling bandits (Yue et al., 2012) and follow-up work on MDPs (Wang et al., 2023a; Zhu et al., 2023). However, these works deviate from the practice because they do not realize the significance of KL-regularization and still choose the greedy policy that simply maximizes the reward. After this line of work, Xiong et al. (2024a); Ye et al. (2024a); Song et al. (2024) highlight the KL-regularization theoretically and in- corporate the KL term into the learning objective. However, they circumvent the special advantages of KL-regularizztion and still follow the techniques in bandit analysis, thus obtaining loose bounds. In our paper, we establish a new lower bound and a sharper upper bound for the KL-regularized framework, thus validating the empirical advantage of KI Kl-reeglarizztton. There are also some works extending Kl.rregulri RLHF from bandit problems to the Markov decision process (MDP) prob- lems (Zhong et al., 2024; Xiong et al., 2024b). We expect that our techniques can also be extended to the MDP setting, which we leave for future work.
B Experimental Results
In this section, we conduct experiments with synthetic data to investigate the benefit of mixed -oolic sampling and the effect of Kl-regularization coefficient on the sample complexity of the problem. We plot the experimental results for RL from preference feedback in Figure 2 and the results for Kl.rregularized contextual bandits in Figure 1. All the trials are repeated for 10 times and plotted with the standard variation.
22

---

Stage Policy Sampling Sampling
SubOptt of Stage Mixed Policy Sampling wirt
0.011
2-5ay On-ho Syg
1720
3.002
1-25
0,030
10020
1-31
0.013
0.0MM
3,000
2200
1000
1000
10300
12000
14200
10000
2300
00.00
2000
10030
13600
14600
1902
2ample-20
Sample
201
(a) Benefit of mixec-policy sampling
(b) Results under different KI.-penalty
Figure 1: Suboptimality gap for KI.-regularized contextual bandits.
Sub:Opi of 2-Stage Kived-Policy Sempiing Offinne Sampling
SubOpt 2:Stage Mixed-Policy Sampling warl.
Ottine Samsing 2:rage On Palry Sampling
4-10.
0.0
4-2.5
0.8
0.4
0.3
0.4
02
2000
4020
5000
5100
12000
12000
14000
20000
2000
4000
6000
2000
10000
22005
14000
15000
Sumple
Sample
(a) Benefit of mixed-policy sampling
(b) Results under different KL-penalty
Figure 2: Suboptimality gap for reinforcement learning from preference feedback.
Algorithm Active Querying for Kl.-Regularized Bandits
1: Input: 1), e, θ.
2: for i, do
3: Sample context x ~ do.
4: if' there exists AA such that DR a; Do) 2 then
5:
Query the reward signal r for (xr, a) and update the dataset Do + Do U (2,0,),
6: end if
7:
end for
8:
Compute the least square estimate &g of the reward function based on Du-
We consider the case where context distribution do is projected Gaussian distribution over the unit sphere and A is a discrete set with |A| 5. We construct the reward functions as R(Ø, x, a) = (x, o(a)), parameterized by mapping ø from A to 10 and set the reference policy To to be the uniform random policy. To generate Φ., we sample Φ (a) independently for each a E A In Figure
according to another projected gaussian distribution over the sphere with radius equal to those of offline sampling using mo under the same sample sizes. The result indicates that the usage of mixed-policy sampling reduces the suboptimality gap by large margin. In Figure 2(b), it shown that the sample complexity is remarkably affected by the Kl-rregularization term, corroborating our sharp analysis for regularized RLHE.
2(a), we compare the suboptimality gaps of muxxed-policy sampling with
23

---

C Alternative Approach with Active Query
In this section, remove the converage assumption and show that if we could actively query the reward signal, we can still achieve the sharper sample complexity bound. The key idea is to actively query the context-action pairs that are most informative for the current reward model in stage 1, and then follow the same steps as in stage 2 of Algorithm 1.
In the following definition, we introduce the uncertainty measure DR (2., a; D) which characterizes the informativeness of the context-action pair (z, a) with respect to a dataset D.
Definition C.1 (Uncertainty Measure). For given dataset D = {zi, a; Jm we define the uncer- tainty measure DR(2; (2, a; D) as follows:
Ri (I, a) R2(r, a)
aR( = sup
RoER
>i= Ri (zi, R2 a:)l
Definition C.2 (Definition of eluder dimension, Russo and Van Roy 2013). The eluder dimension of function class G with domain Z is defined follows:
A point & E Z is e-dependent on 21, -2 2k E Z with respect to g, if for all 91.92 E such that Σ [9 (z) - I2 (2))) e. it holds that [ (z) 92(z)] e.
Further is said to be e-independent of 21, #2, 21; 22, Zk.
with respect to G. if is not dependent on
The eluder dimension of G. denoted by dG e). is the length of the longest sequence of elements in Z such that every element c'-independent its predecessors for some c' 2 c. Lemma C.3. Let (R) be the cluder dimension of the reward function class R as defined in Definition C.2. In Algorithm 2, if we m D(dimg(R)n/eed) then with probability least 1- 5, P Po {max Dx (I, Do) 2 u < e/n-
Proof. We denote the m sampled context by æ1,... Tm numbered in the order of operations, and denote by Do.: the dataset Do at the beginning of the i-th iteration. Also, we define μ4, Fawd, {max.e. DR(x, a; Do.)) 2 u].
Applying freedman's 's inequality (Lemma G.6), we have with probability at least 1 -
Σ M. 1 {mma (R a; Do.)) 2 w}] < aEA
Σ p. log (2m + 2)/6) + 2/108 log (2m + 2)
1=1
i=1
+ 2 2 (2m 2)/6)
Σ 14 + 1ogg( (2m 2)/5) + 2 (l/oog((mm + 22)5)
where the last inequality follows from Young's 's inequality.
Rearranging the terms, obtain:
2| + + 80ggg(02mmmmmmmm + 2)/6) + 4 /llog(22m 2)/8)
dimg 8og (2m 2)/8) + 4 log 2)/8)
where the last inequality holds due to the definition of cluder dimension.
Hence, by setting ((diigg we can ensure that >m M4 5,
Theorem C.4. Suppose we alternatively execute Algorithm 2 for stage Algorithm 1, and sup- pose that the reward signals lies in [0, 1]. If we set u
set m as in
Lemma C.3, and set n (11 log( (Ne((Nee)))))/))) then with probability least 65, the output policy Th is (c) optimal.

---

Proof. By Lemma C.3, we have with probability at least 1 - 8, P Pæwdo {maxae.4 Dx a: Do) 2 u} S e/n.
Let An == {a E X max.eA (R(x, a; Da) < u). Similar to the proof of Lemma E.4, by Lemma E.2 and the definition of u, have with probability at least - 45, for all x E No.
1) R( 2, a) - R(O,, v. a) - R(θ0 x, - R(O,, x, a)l 1
(C.1)
By Lemma 2.9, we have
Q(TT) - Q(x))) nBBando
Σ
R(0,2,
aEA
From (C.1), have for any Xo, A,
π T²(a| xx)
S e
π (a xr) 8
Therefore, proceed as in the proof of Theorem 2.8 to obtain
Q(+*) (m S me mpe'E Exwdo 1(x Xo)
(alz) -R(02,
80
+ 1 P do (max Dr. (2r, az Do) n).
aEA
Then we can complete the proof by Lemma E.3 and the union bound.
D KL-Regularized Algorithm for RLHF
In this section, present two-stage mixed-policy sampling algorithm for RLHF in Algorithm 3, which can he seen as an extention of Algorithm 1. There are two stages in the algorithm.
In the first stage, sample context-action pairs { at ai k from the BT model and call the preference oracle to get the preference labels. We then compute the MLE estimator of the reward function Og based on the preference feedback in line Afterwards, we apply the planning oracle to compute the optimal policy = based on the reward function 8g in line 7. Line 6 and line correspond to the practical implementation of RLHF (Ouyang et al., 2022; Bai et al., 2022; Touvron et al., 2023) given a dataset of preference feedback.
In the second stage, sample context-action pairs {(x,, at a² 9: 1i using the intermediate policy Th and call the preference oracle to get the preference labels. We then compute the MLE
estimator of the reward function Ô based the preference feedback from both stages. Finally, apply the planning oracle to compute the optimal policy x based on the reward function A.
E Proofs from Section
E.1 Proof of Theorem 2.6
Proof. Consider a simple case when | uniformly from X' at the beginning of each round. Let θ be the set consisting of mappings from X'
M and [A] = 2. suppose that the context x drawn
1/2 if 0(x), where E (0,
to A {0, 1}. For each O have R(0, 2,, a)
1/2
if + 0(x),
constant, and ((x:) is the optimal action under context when the model is 0.
For any (0, xr a) E θ x x A. we assume the reward feedback r Bernoulli x, a)) when the model is 0 and is chosen under context
((2(z)
if + Tu. if x Zo.
We pick pair of model 0,, O2 in O, such that 0, (xx) 1 (z(x)
25

---

Algorithm Two-stage Mixed-Police Sampling from Preference Feedback (TMPS-PF)
1: Input: 1/, E, To. O
b Use policy No to achieve sufficient data coverage
2: for i= i=
do 3: Sample context I2 ~ du and 2 actions a a² ~ (-))
4: Observe preference label ye {0, 1} from the preference oracle defined in Definition 3.1,
5: end for
6: Compute the MLE estimator of the reward function based on { 0i at M:)))
8. - argmax
V log (R(O, H., a!)) R(O, R., x))) + Mi) log (R(o, ot) - ((0,2,,07)
7:
Apply the planning oracle compute o. (-1-) & (-(-)-) exp (n(((o.:)))))
Use policy n. to sample new responses
8: for l..i=......
9:
Sample context 2; do and 2 actions a) af Observe preference label y; E {0, } from the preference oracle defined in Definition 3.1.
n/ (-1z;).
8p
10:
11: end for
12:
Compute the MLE estimator of the reward function using ((x,, at ae,aa,))))))) y:)) together with ((T,, d }1))
0 argmax
We log (N(O,,,, n(0,5;,a?)) (1 .i) log (R(0, a.) R1,0,;,.00 a!)
y log o [R(0, at) 21,,,,,.0 +(1 ys) log (Rg x,, a.) R(0, x1, a()))
Output (1)) x exp-))))
We denote by Pe. Eg the probability measure and expectation under the model Let Nxx) be the number of times the context æ is observed in the first I rounds for an r E X.
For two Bernoulli random variables X and Y with parameters 1/2 and 1/2 have
KL(X|Y) (1/2 c) log 1/2
1/2+c c
(1/2 log 1/2+c +
1/2
1 2c
2c log
< 16c²
1 2c
where the inequality follows from the fact that log(1 + x) S x for 2 and E 10,1/4).
Applying Pinsker's inequality (Lemma G.3), we have for all event measurable with respect to the filtration generated by the observations,
IP,, (A) - IPo,
(P, (A) S [N(oo] V V8eT/M,
where the first inequality follows from the chain rule of KI. divergence, and the fact that Es, [N(2))] = T/M.
Set to the event that Tour (zo) > 1/2. Then we have
Po, (Fou (0, (2ro 1/2) + Po, (Toal (02 (xo) (m0)) s 1/22 1
(Po, (A) (o, V8eTT/M.
If the model 0 is uniformly drawn from e, then have
Eg--Unif(e) () Po(TT.u(0 (0(z)) S 1122) 2 2
- 2M
for an arbitrary Tp-
Then consider the following suboptimality, where set to be the uniform random policy:
En""" R(O,, x a)
log no Ta (a(x
T. (a|x)
E.... R(O,, x. a)
1
log
Tour
To (a(ar)
26

---

mo(a|z>) exp(n)(BBB))) x. a))
1
To <o(a) exp(nR(0.. 2, a))
log
log
T.. (a/x)
17
nea
Tour (c/2))
E log Tour(a/2=) 7
' (a|z)
where the last equality follows from the fact that m. & mo(a)x) exp(n x, a)). Note that handle the difference in reward and the KL-divergence term together, which is distinct from the standard analysis of the lower bound for contextual bandits.
To bound the suboptimality gap, further have
Tout (a
Uni( ETTO
log π (a)
log naur (a
Unii(i)((
Σ JEA
E B (11z)
x (a|zz)
+ exp(-xp))))
+ exp(nc)
2 EggUUii((9) M
Σ
TPo (T( S $1/2).
log
+ 2
log
2
2
2
MEN
2 222TTMM -
-
(2
[2 log
+ exeepp-m0
+
log
1 + +xx((n))
(E.1)
2
2
2
where the first inequality follows from the fact that (-<=<()) if (om(0(x)) 1/2.
>
Here Tunit is the uniform distribution over A.
Note that
d du
1
1
1+ 1+e"
1 1 + exp(-u) 1 exp(u) I1_ 0,
log
log
2
u=0
d²
1
1
1+
exp(u)
log
2 log 2
2u
2
1 exp(u))2'
Thus, applying Taylor's expansion on the right-hand side of (E.1), we have
En. [log {a)r(a) 1 n³ (a|x) 2 (₂ 22e 1222 3 exp(nc)
1
which follows from the Taylor's expansion where -(x) - 1()) f'(0)= {2) where
[0, nc], and the fact that 2/2 (1+er)z 1 +40442 I 2 34ere-
When 1/64m, we can set e/m,. To achieve suboptimality gap of e, we need satisfy:
1
/ 2 1)p 1222
3 exp(nc) I ne
2 2
indicating that T
nM
= 22 nM
2048
When 1/64n, or equivalently, follows:
1/64e, we employ different lower bound for (E.1) as
1
log 1 exp(-1ic) 1
+ exp(1c)
2 + exp(11) + exp(-ncc
log
log
2
2
2
1
exp(1cc + exp(--pe
2
log
2
2
(7C log 2),
(E.2)
where the first inequality follows from Jensen's inequality. Substituting (E.2) into (E.1), we have
- Eg E... log x (apx) )
Toour (a(z))
1 4
G VeT/2M) (n/c log
1 11
Set c = 64c. Then we have T = 2(M/
Note that for the given e, NN(()) M, and since do is the uniform distribution over X, have D = O(M, which completes the proof.
27

---

E.2 Proof of Theorem 2.8
We start with the following lemma, which provides an on-policy generalization bound for the reward function. Due to the on-policy nature of the algorithm (i.e., the usage of intermediate x. ) we can leverage the covering number of the reward function class R derive the generalization error. Since we are using a fixed policy T to sample in the second stage, we can derive the generalization error of the reward function as follows:
"a
Lemma E.1 (Generalization error of reward function). For an arbitrary policy л,, a of context-
action pairs {(2, )=))== generated ii.d. from ग, and a distance threshold 0 < 6 S B, we have with probability at least for any pair of parameters 0, and 02.
E E=|R((,, x, a) R,00, a))²
2
32B² 3n
R(01, Fz, a,) R(02, az)
log(2Nx((c)/00) + 10c.B.
Proof. We first consider <e-net R2 of the reward function class R where R {R(0, : ))0 ) with size (c). For any R(O,"; E R. there exists 8 such that (R(0,;,) R(6 S Co-
By Lemma G.I, for each pair of 0f, 0g O (corresponding to 0,, 02), we have with probability at least 1 - 8,
(R(0f, a:) - R(09, Mi, a:)) E=|R(09, x, a) - R(05, v a))
2 Var, RR(0, v,a). a) R(0S, N. a)l log(2/5) +
2
B² log(2/5)
n
3n
2 R(0,, 2, a) R(05, x, a)l log(2/6) +
2 B² log(2/6)
n
3n
where the second inequality follows from the fact that R(0 x, a), R(0 x, a) S B.
Using union bound over all 0f, 0g Oc, we have with probability at least 6, for all 02, 0$ e Os,
E, 1(09, R(05, a) 1
[R(8, 2;) 21,
A R( x, a) R(OS, xz 1² log(2NR (E.)/0)
4B
log((.N
3n
from which we further obtain the following inequality by Lemma G.2
E. Ex|R((0,,x,00 a) R(00,,,,)) < 2
32B²
(R(09, xi a.) x000 0;))
3n
i=1
(E.3)
Then we can complete the proof by the definition of c-net.
Next, we provide the following lemma, which gives an upper bound on the cumulative square error of the learned reward function.
Lemma E.2 (Confidence bound for reward function). For an arbitrary policy æ, and a set of data
(Ji,, 0z; r3y )= generated i.i.d. from π, suppose that 0 is the least squares estimator of 0., i.e.,
0 arg mingge Σn (R(0, x,, az) - rt)?. Then for any threshold e. > O, with probability at least
1 - 6, it holds that
Σ (n( x,, x,) a:) - 2,,,,,,,
xi, a;)) < 16B 16 (og(2NN(e.))))) + 4e,n..
28

---

Proof. We have the following inequality for Σi= 21,0:) - Ri, a:))
[R(,, F₁, a;) - 2;,
(R,0,2;, - -ri)² Σ (R(0,, - r:)²
"
Σ
RR I4, a:) Ri,,,, a:) R(0,,
2 Σ (R(O, xi a.) R(O. zi, a.) R(0,, a;)))),
where the last inequality follows from Ex= (R(O,, k2,0;, a,) r.
the fact that (R(0, 2;, -ri)² S
We then consider an nnt R of the reward function class R where R {R(0. ))0 09] with
size (e(e2). For any :)) :) R, there exists 0 such that [R[0, x. a) R(0 xr a a>ls S 6c-
From Azuma- Azoma-Hoefiding inequality, with probability least 1 8, holds for all O that
R(O, F4, a.) 24, R(0., a.))
B (R(), (oo
Then we further have with probability at least 1 5, there exists ||R(09 R(0, 5.) s such that
R(O, Fy, 0.) - R(O I4, (4, -R,0,
< 2B
(R(0,2,,a.) (o0,, + 2
which implics that
E vi, ai) 2(,,,, 161B log(2Nr((e:)00) + 4
(E.4)
by Lemma G.2.
With the above lemmas, error of the reward function R(O,,,)) .))) under the sampled policy n²
ready to prove the following lemma that bounds the estimation
Lemma E.3. Let O be the least squares estimator of the reward function based the data {(x), a. m generated from no as defined in Algorithm 1. Then for any threshold 6, > O. with probability at least 28, we have
43B² n
B_ x,) R(O,, a))2
log(2Nx(<.)/8)) + 10c, + m/n)B.
Proof. By Lemma E.I, we have with probability at least - 8, the following upper bound holds for Bng y [[00, a) R(e,, x, a)
%0
Egy ( a) R(02, x, a)
80
29

---

2
32B²
RiO1, Ri, f1,0:) R(02, ag)l2+
log(2NR(<e)/00) + 10c.
(E.5)
3n
By Lemma E.2, with probability at least 1 -
x2, R(0, F. a;) < 16B log( 4c.(n m)
(E.6)
Then complete the proof using union bound and substituting (E.6) into (E.5).
Lemma E.4. If m 2 128 D² log(2N (tx)/ and there exists positive constant Cm.. such that m in Algorithm and Assumption 2.5 holds, then by taking < S mmin B, (8(1+
Cm,n) D D2)- }, with probability least 1 36, have
n/ R| a) R(O., x, a)l - 1, n|R(0,x,0) x,00 - R(O.. a)l S
for any pair (z, a) E X A such that <o(a/z) > 0.
Proof. By Lemma 1.1, with probability at least - 6, for all 0,, 02 E O we have
32B²
Emp R(0,, a) R(O,, x. a) Σ R(0,, a.) R(02, x 22)2
(og(2Nx()c)/0)
3m
By Lemma E.2, with probability at least we have
Σ 1R00,,1),af R(0,,
2f. 2, 16B 1og(2NN(e))00)) 4c.m.
Also, with probability at least 1 - 8, we have
m
Σ a0,00,.0,
x00,x%a0)1 1og(2 +cc(m + n)
Similar to the proof Lemma E.3, we have m 2 128n/ D2 log((2 n Cm, then with probability least 1 35,
Brol R[O0,, x, a) R(O, x, a)) 1/ R,,,, R(O, x, a) S D/
which implies that 1/) R(O x, a) R(0., x, a)l 1 and n/ x, a) R(O., x, a)l < for all (Ir a) E X' x A such that (a(a)z) > 0.
Lemma E.5 (Restatement of Lemma 2.9). For any estimator ē O. and the policy m. satisfying
Definiton 2.4, we have
Q(T")) ((=)) B/Enndo
Σ
(z,
Σ
AMaaEA
S Epgndo
A A3
DEA
where Axx,a) = R(Ō, v. a) - R(0.,20 x. a), ((::.) = 7 (1 7) ((0,. (r E 1)) the inequality uses the fact that second term on the right-hand side of the equality is (EnEA T)(al=))(z,
0.
Proof of Lemma 2.9. We have
1 T.. (a|x)
1
TH (a(x)
Eng ((0,,I,a) log
-Eng
RiO,, 21
log To (a|z)
7) no [x)
7
1
To(a[z) cxp(nn((.,,)))) a))
<o(a).)) exp R a))
-Eg
log
E 8
log
7
Tg. (alz)
m (a)xr
30

---

1 Eg log Zg, 17
(z)]
1
E Eo
log
[x)
E gg
Σ
( (R(0,, - R(O, x, 2.11)]
aEA
where the first equality follows from the definition of the KL-divergence, the second equality follows from Lemma G.5.
For an arbitrary reward function f x A Ret 4 (2, f(z, a) R(O,, a). Consider the following first derivative of J(f) log Z)(x) - n - (j(a))) A, a), where 27)()) EaEd To(a/x) exp(n f(x, a)) and Tr( x Ta(a))) exp(1) f(x,a)).
log (z) (z) 7 Σ
T7(a|x) ()(2,0)
0 (z)
aEA
(7(x) TO ro(a|z)) exp(1 f(z, 1) -}(4|2)
-1 -1 ()),)) To(a|z) exp(1 f(z, a))
1) + 1j As(o, a) [to(a|z) exp(n a))
(x)x)
(x)22
'1] A ( To(a'(x) exp(1) f(z,a')
Tu(a|z) exp(1 f(z
+
xx)
()(
d' (aE
- - (aa + + a)) +1
Σ
d'EA((a)
where the first equality is derived by taking the derivative of log Zz) and the second term with respect to Ay. Therefore, by the Mean Value Theorem, there exists an f(,-)) = RR(O, (1- 7) :) for some 7 E [0, 1J such that
1 EEnndo -17² Σ Tj(ak)) -7 7 (R(O,,, x, a) - RR(O,, x; a))² 77
Ex ((((O,,)))) J(B(O,, :.)]
aEd
1 Bandds
Σ Σ
(/(( [ 02) 2(0.,2, 02))
m1
"1
G1E.A
- Eny [R(0, 22, R(0,,
where the last inequality holds since
x, x,,,,, Σ Σ 7//0)1a)=//00)))))(0.... (K) 02) (2) x,,
arEda
= [aart(
R a)) R(O,, a)]] 2 0.
Now, we are ready prove the theorem.
Proof of Theorem 2.8. By Lemma 2.9, we have
Q(T") - Q < ny
Σ (( 1(0,x,)))) a))
By Lemma E.4, 2 1281/² D2 B (2 for any (x, X such that <o(a)>)> >
0, it holds that
n R(O, x. - R(0,, x. a) which means that for any (I, E X x
1 v| R(0,, x, a)l $ 1,
T T7(a|z)
$ E
(a .r)
Let 6c min (I+cm)))B 8(1+cmm 1Br B). By Lemma E.3, if m 2 128r D2 B² 1og(2Nx<<..) (8) and n 2 n/e. Ba Bº (o)((N(<c))/)))) and n m then with high probability
the output policy nh is O(e) optimal.
D
31

---

E.3 Proof of Corollary 2.13
Proof of Corollary 2.13. The proof follows the same lines as Theorem 3.7 by replacing the data coverage condition with the local-coverage condition. It still holds that
Q(=)) S n xxx [R I, a) R(O.,, a))
where (a/aa) & ()(ar)) exp(n f(r, a)) and f(+,) 7R(00- :.) R(0m) for some 1). Thus, We have (L(m)(a|x))1 2nB, which further implies that
( S Cor.." o ( B (N ( + B(1 mmin)c
by Lemma F.4. Then conclude by substituting the value of m into the suboptimality gap.
F Proofs from Section 3
F1 Proof of Theorem 3.6
Proof of Theorem 3.6. The proof follows similar construction the one for Theorem 2.6. Con- sider a simple case when X = M and [A] = 2. We suppose that the context æ is drawn uni- formly from X at the beginning of each round. Let θ be the set consisting of mappings from X
fe if a 0(x), where (0, 1/4) is
to A {0, 1}. For each 0 θ, we have R(0,2,a) (o
if + 0(z),
constant, and (xx) is the optimal action under context when the model
(2(xx) We pick pair of model f1, 0g in θ, such that (x)) [1 (2(2)
if + 20:
if Ty-
We denote by Po. Eg the probability measure and expectation under the model 0.
We have the following upper bound for two Bernoulli distribution y1 (ernoulli(((c)) and y2 Bernoull(((-cc) with (I) = 1/(1 exp(-x)):
(c) log a(-c) + aa--)) log (-c)
(cc)
(Cc) = ( o(-c) log
a(c)
a(-c)
1-e c l log
1 I lte - e -
< Ite lte
c. (c+ sc² [11 +e
where the first equality follows from the fact that (-c) log x S x - 1, and the second inequality holds since c < 1/4.
oc),, the first inequality holds since
Applying Pinsker's inequality (Lemma G.3), have for all event A measurable with respect the filtration generated by the observations,
Pe, (A) Po, (A)I (e CCTMMM
where the first inequality follows from the chain rule of KI. divergence, and the fact that Ea, [N(x)) = T/M.
Set A to be the event that (0 (ro) 1/2. Then we have
Pe, (Fout (0, (0)
(2o) - 1/2) + Fe, Tmot
s 1/2) 2 1- Po, (A) (A)) 21 VeT/M.
If the model 0 is uniformly drawn from θ, then have
1
Eg. (T (xn)) < 1/2) >
-V C4T/4M
2
32

---

for an arbitrary To-
Then consider the following suboptimality gap:
log To. (a/2:)
1
Tout a 2z)
B
R(Or, (I,
R(O., 2,
log
TO TT(aaa))
To(a|z) exp exp(p (7 It,
1
To (2)az)) exp (n 2. a))
log
E ma
log
1)
m0. (a)
11
Nout (1)
log
Tout (a/er)
7
π (a/zz
where the last equality follows from the fact that m², x mo(ala) exp(n)((0, 2. a)). To bound the suboptimality gap, we further have
log
Tout (al(( n (a
En-Uni)())) ErT.
Tout (a(z)
EmiuUi)(())
Σ
IE Ea T (1xx)
log
M
x²" (alz))
TEX
1
1 + exp( n)c)
1 + (7c)
Uni((i)
Σ
(To (0(z)) S 1/2)
log
+ log
M
2
xEX
1 exp(-ne)
1 exp(nc)
(TT/4MM)
log
log
(F.I)
Note that
1
1 e
log
log
0,
du
2
2
2
2
k=0
2 1 exp(-x)
1 exp(u)
m=0
d²
1
1
1te
+ 1
exp(u)
log
log
du
2
2
2
1 1+exx exp(u)]²'
Thus, applying Taylor's expansion on the right-hand side of (F.1), we have
Eam Bri. log
Tour (a/=z)))) xr" <a(xz)
2
(
VCT//M 72
exp(nc)
When 1//44,, we can set = 8///.1 To achieve suboptimality gap of e, need satisfy:
1
C2T/4M n²²2²
$ nJ.
2
3 exp(nc)
indicating that T
nM 512c
= Ω nM
When 1/64n, equivalently, 77 1/64e, we employ different lower bound for (E. as follows:
1 exp(-
1 exp(ne)
2 + exp(n))
+ +exp(-nc)
2 log
2 log
log
2
2
4
2 2 (log exp(ni) + exp(
1
2
2 (nc - log
(F2)
where the first inequality follows from Jensen't inequality. Substituting (F.2) into (F.1), we have
6 2 F.g Uni Eraa log
Tour (a(z)
1
VeT/AM) (nc log 2)
1 -.
n (a.x)
4
17
Set e = 64c. Then we have T =
33

---

F.2 Proof of Theorem 3.7
First, we provide the following lemma for the connection between the likelihood loss and the reward difference, which is a key step to upper bound the reward difference between 0 and 0z. Lemma F.1. For an arbitrary policy æ, and set of context-action pairs {22, a, af y1) y:)) gener- ated i.i.d. from the BT model and π,, we have with probability at least - 6, for any 8 S n1
[(0 Di; ai 25, vi) - C(0. az. vi)
2 1=1
1 g (RR(0, Iy az) R(0, Nr, at)] - [R(O,, Fy, az) R(O,, Nz, a!)l)²
s (10(1/8)
Proof. Applying Lemma G.4 to the sequence
{
(R(,,, 2, at) R(, af)) T2rioogg oR(O, z₁, a.) R(0, af)) 2 (1- (1-y;)-log (R,(O,; - R(0,, Ii, a
o[I{0, Tú, a.) - 1i0, xg a,)) 1) i=1
We have with probability at least 1 - 6, for all n,
[(0 at, v.) [(0. (2: aj, af.
< 1og((18) + ' log ( xz, at) R(O.. ot)) [R(0,, n,, x;) - R(O,x,,
1=1
+ (o(O0,, Ti, a²) I00 (P(()))) -(00) R(0,
< log((16) + Σ (R( R(0,, (1) (R(8,,2,, - R(0,2;, a!))
+ *V No((O,,,
Ii, at) - R(0,, xs, xi, -R(0 a()) -1)
= =log(1/8) Σ
2i, at) (o(R(O,
R(O,, F,, o())
Vo(((( Fi, at) R(0, xs a!))
1
Vo(R(00, a.) RR(0,, at)) (((((,2,,,))) R,,,, - 2
Σ
2
< <log(1/8)-
(o(H(0., In, at) 21, o(H(0, Ii, .²) - R(O, 2,, a a²)))²
==1
$log(1/8)
(I8(0, xi, a,) - R(O, x, a!) - [R(0., 2z, aZ) - R(O,, Tz a: )1)
where the second inequality holds due to log(1 + r) S r for r > -1, the equality follows from the fact that (r) + a-(-)) = 1 and the last incquality holds since d'(r) = o(r) (1 o(r)) 2 e -B for all E [- B, B).
To further control the error bound for the reward function with the help of Lemma F.1, we introduce the following lemma to show that the likelihood function class L can be well-covered by the c-net of the reward function class R.
Lemma F2 (Covering number of L). For any e, > 0, consider an en-tet R {M(( 10 E O*) for the reward function class R with size No (t.). Then for any E O, there exists 0e E O such
that for any s [n].
C(0)a,, ae of v))
2(0 a,, a. 28E
34

---

Proof. For any E R. we have d dlog(o())) dr
1 o(r) (r)) (1 (1-a(r)) a(r)) 1 o(r) E (0.
Thus, for any 0 E 0 x E X. a2, a² E A and E {0, 1), there exists 0 E e such that [((0) a v) [(0 a ... $ [R(0,2,at) R(0,z, d²)] [R(0" x, a²) R 2, a²)1l 2Ec.
With the above two lemmas, are now ready to provide the confidence bound for the MLE esti- mator of the reward function.
Lemma F.3. Consider a set of context-action pairs {(E a) oz 9:) )=) where labels (ui)= are generated independently from the BT model. Suppose that A is the MLE estimator as defined in Definition 3.3. We have with probability least 1-6,
Σ (IR(O, x. R(O, af)) [R(O., at) at))) O(e log( (xg(NN((e)/0)) + e nee).
Proof. By Lemmas F.1 and F.2, we have with probability at least 5, for any E O
[(0 al.a?. af. (0, a.,
log(NN((c)/O))
(IR xs, af) R00,z,, (00,x,,)))) at)] [R(O,, R(0., vs, at)1)² + O(nea).
Since O is the MLE estimator, we have Ei C(0)20,, at a² vi) [(0.|2,, aZ v:) 2 0, which further implies
n Σ
< log(NR(())/))
R(O,, x,. at)1) 2(0,,,,,3)) at)] [R, (
i=1
+ ((EE))
Then we have
2,00,,,,0 -R(O x,, af)] ((....,,,07) 2(, s O(e (e((N(cco)0)) + nnc)).
Finally, we provide the on-policy confidence bound for the squared reward difference between the MLE estimator 1 and the optimal reward function 0,,
Lemma F.4. Consider arbitrary policy n, and set of context-action pairs ((ri, at, aZ yo ) generated i..dd from the BT model and æ. Suppose that Ø the MLE estimator. have with probability at least 1 - 26, there exists mapping b X IR such that
En (R(0, x, a) R(0,,z, (((x))(()))))))))))())))) S O Le (o)() (e%ee))))))++))....))))))))))))
Proof. By Lemma F.3, we have with probability at least 1 - 5.
(IR(0,,,,af) R(O, xi, al) [R(0., of) - RRO,, 2;, a!)))² < Ole log(N (Eo)/ + t enee))
We consider an en-net R = {R(0, 10 @*} for the reward function class R with size Nr((e)- For any R(O,.,)) ") there exists R(0",-, ... such that
R(O,, x. a) R(0 x, a)) < O(ec)
35

---

for all x E X, E A. Applying Lemma G.I, with probability at least 8, have
([R(0) Vi, az) Ri00, ; Fi, a.)] - [R(O,, 3i, az) R(0,, a!)))
de Eed a² [R[(0 I, a.) R(O,,Izaa)) R(0 10, a²) + RiO, 2, a2))
aewn | (R(00, at) - R(O,, v,, a²) R0000 2, a²) + R(O., x, x2)) log((Nx(e))))) 4B aann
8 Bd log( (R({c)/0)
3
for all 0 E c By Lemma G.2 and the definition of @ we further have
Exndy Bot aawn (R(0, a²) R(0., a') -R(0 x. a²) )++ R(0-, xr x²))²²
I 0 - B² (Nx))N( + ([(O, x.. R m., a!)] [n[0,, ur, a.) R(,,, mi a.))) + Bea),
(F.3)
from which we can further derive that
Exwdy Ex 2a2 (R(0,x, 2(0,,,,a') 200,2,0²) 2(0.,,,
0 E (g((N((e./88) c.)
with probability at least 25 by Lemma F.3 and the union bound.
We can then complete the proof by setting
b(x) Eg (-) [R(O, x, a²) x[,)],
Lemma E5 (Coverage of n. and va by Tg If 2 D2 (og(NR((..)) = Cm.. m and
I (remm))""rpD in Algorithm 3 and Assumption 2.5 holds, then with probability at least 1 48, there exists bi X and b2 X R such that
1/ n/R(00, x. R(O., xr a) by (x)) S 1, n)R(0,x,0) R(O., a) b2(x))
for all x E X, a E A such that (a)arr) > 0.
Proof. By Lemma F.3 and the union bound, we have with probability at least 8, it holds that m
([R R, at) R00, H. 2 - 2, R(0,, a!)))²
(18(0, x, a2) 1100 x4, - at) R(0,,,,,,
OEe" (c.(N + e ( m)e.).
(F4)
Consider nett R [R((0 1) E @c) for the reward function class R with size Nr((e). For any :,,,,.)), there exists R(00,.. .)) such that
R(0, x, a) R(A x, a) s O(Ee)
for all x E X, E A. Applying Lemma G.1, with probability at least 8, have
m
Σ (IR(0)) Z. a7) R(0 F., 2,) - [R(00, Fi, at) R(0,, at))
36

---

-BBgwdd Ea ano (R(0 x, 22,2) -R(6,, -(,0",,,a)) x2))
4B Bu a2 (1,(00,,,,0)) R(0,, R(0 x, a²) ) 2(0,,,,,1)) log((NR(Ee)))
Bd log( (e)())))))))
3
for all 0 E e By Lemma G.2 and the definition of @c, we further have
Ez E a pa [ (R,)) R(O,, R(O x x,,,), R(O,, x, a²) a
B² (og((NR(ee)/)
[R(0, F., σ R(0, a:))
R(O., F., a))) - BEa).
(F.5)
Substituting (F.4) into (F.5), we have with probability at least - 20,
E Eg Bal (R(0. a²) R(O.. xx,. R(0,zza²) R(0., x,, a²)))
S 0 (e. + +e.. m
EO).
m
Therefore, there exists a mapping by : x'' R such that
E [R(0,x,,)) R(0,, by b2)))) 0 m
00- log (og() +eB n+ m
(c).
By Lemma F44, have with probability at least 26, there exists mapping x IR such that
Em [R(O,, x, - R(O., x. a) b1())) = =
log(NNe(ea)00) + eB mc.)
m
Hence, we can complete the proof by a union bound over the two events and Assumption 3.5. Now we are ready to prove Theorem 3.7.
Proof of Theorem 3.7. Let b be the mapping defined in Lemma F.4 for We have
1 T.. (a|z)
1
log 3 (a(x)
Eng
log 17 no To(a|z) x))
Enz
R(O,, x, a)
n
Ta(a)z)
1
log To(a|x) exp(1)((0,, a))
1 -EE
<o(al>) exp exp(1) (1)R(0.; x.a)) a))
-Eag
log
To. (a/z)
17
Ex
log 27, (x)] Ex log (x) - Exndo
Σ aEA
n (alx) (R(O,, R(O, x, aa)
7
1
For an arbitrary reward function f: X' x A R, let A f(x, a) - R(0., a). Consider "A (u(r)) A A(x, a), where (7(2)
the following first derivative of J(}) log (7) - 11 EnEd 7/
E.EA mo(a/z) exp(n f(x, a)) and T" (a|rr) x To(a exp(n f(z
Similar to the proof of Theorem 2.8, we still have
i
log Z7()) - Σ 77((/2) (2x
A xx a)
acd
((alr))xp(()) f(a, a)) -7 - 71 <7a([xx)
(x)
To(al=) exp(n f(z a))
TT(aaaz))) cxp(n f(x, (((nn-(x)a))1 2 (x)
- A(r,a)
17 + 17 ((x,))-
(x)
37

---

+ To(a'<>) exp(n fa,f((xx))))
.n A(x,a') To(a|z) exp(n f(x,a))
(z)
d'EA
/1/0///1000000 + e'EA((a)
Σ =((d)))7((())))4)..)))
Note that
J(B(O,,,)) log 20 2z(x)
mg(l)) [ (R(0, 11,0,,,,00)
aEd
=log
Σ To(a|z) (xp()( -())))))))))())))))))))))))))))) - Σ (a)(a))) (R(O, x. - R(0,,2,a) b(x))
aEA
aed
(R((,,,, b(x)).
Therefore, there exists [(, > (1-2)))((0,,.))) such that (7 (0,
Exwd (J((O,
- ((((O.,.
1 Rando -1j
Σ
x <a)()) 7 (R(0, R(0.,r,0) - b(x))²
17
aEA
+ Exndo
Σ
Σ [/(olb))7((000)((000... R(O., x. a1) b(x))
aLEAGEEA
(R(0,I, RR(0,, a2)
-17 -77- Bxy ( 1)) R(O., a) b(x))²
By Lemma F.2, if 2 32//² D2 ( for any (a, a) X x such that To(a|>) > O.
it holds that
R x, a) - R(0,, - (x)) 11,
n/ a) R(0., 2, a) - ba(x²) S 1,
which means that
f S
ed
π 80
Let 6, = min 201 211+c (1+em. Je "f }. By Lemma F.4, under the condition of the theorem,
with high probability the output policy m is Oc)) optimal.
F33 Proof of Corollary 3.10
In this subsection, we also discuss our result under the local-coverage condition (Definition 2.11).
Proof of Corollary 3.10. The proof follows the same lines Theorem 3.7 by replacing the data coverage condition with the local-coverage condition. It still holds that
( s.n E.ay [R x, a) R(0,, x, b(x)) 2
where -))([/z) x <o(a))) exp(n f(x, and f(..)) ((((o,, b(-) + (1-7) R() for some E (0, 1). Thus, We have (L(T)( mo) < Bn which further implics that
- Q(T))) 1n Cpxn. o B ( + B cmln -(a')-
by Lemma F.4. Then conclude by substituting the value of into the suboptimality gap.
38

---

Auxiliary Lemmas G
Lemma G.1 (Freedman's Inequality). Let M, v >> b fixed constants. Let {X;)== be stochastic process, (Gi)i be sequence of o-fields, and X; be Gi-measurable, while almost surely
E P 0, X S M, and Σ Gi
Then for any O, with probability least 5, it holds that
2 S 22 log(1/6) + M log(1/8).
3
Lemma G.2. Suppose a, b 0. If + b- z, then x² - 2b² 2a.
Proof. By solving the root of quadratic polynomial ((x) = x² b. we obtain max(21 22)
(b+ vD2 + 4a)/2. Hence, we have
+ provided that g(x) s 0. Then we further
have
1 ( b+ 12 + du) 2 - 2 (12 + + + +4) S 2b 2a. x² 2 S 1
(G.1)
Lemma G.3 (Pinsker's Inequality). If 11, P2 are two probability measures on common measur- able space F), then it holds that
P(, S KL(P) (P22),
where 8(:,) -) is the total variation distance and KL(-II-) is the Kullback-Leibler divergence. Lemma G.4 (Lemma A.4, Foster et al. 2021). For any sequence of real-valued random variables (X)) adapted filtration (Fi)esT, it holds that with probability at least - 6, for all T" < T,
T
Σ
X. x
Σ
log (og(Ex-llexi] log (1/6).
1=1
Lemma G.5 (Solution of KL-regularized Optimization (Proposition 7.16 of Zhang 2023)). For any fixed X and reward function R, have
max (a) A (L((((())
log E Eawao(-la) exp (n)(x,))).
where ZR(2) the normalization constant and the minimizer of the loss functional is
<>(a=>> Zx(x)
To(a|z) exp (1)((z,))
Lemma G.6 (Lemma 10, Zhang al. 2020). Let (M,)nz
martingale such that Mo = 0 and
M, Ma-al < e for some e > O and any n 2 1. Let Var, = E E[ [ Mt). Then for any positive integer and any e. p >
for n 2 where F&
have that
1
ee elog (1) - 2c ()) < (2ne² /ece"/ 2)
MA 2 2 Var, log
+ +
39


Reviews:
[{"review_id": "ROJmLul7W6", "reviewer": "Reviewer_5V1N", "summary": "The paper proves that for KL-regularized contextual bandits and RLHF, the correct sample complexity is of order $\\tilde{\\Theta}(1/\\epsilon)$, not $\\tilde{\\Theta}(1/\\epsilon^2)$ ignoring other factors. The lower bounds are proven via standard info-theoretic arguments, and the upper bounds are shown via proposing a two-stage approach. The first stage collects samples from the reference policy, and the second stage collects samples from the learned policy, where the learning happened from first stage's collected samples.", "questions": "1. In Rmk 3.9, the authors state that $e^B$ is probably unavoidable. Can the authors comment on whether the techniques from [1] can be adopted to remove such dependency?\n2. What parts of this paper can be easily extended to general preference learning scenarios?\n3. Related to weakness, can the authors comment on the (educated) conjectured \"correct\" dependency on the policy coverage?\n4. What is the intuition behind the fast rate of $1/\\epsilon$, in \"layman's terms\"? In learning theory, the intuition that I'm familiar with is regarding the curvature of the loss and mixability properties of the loss function. Do we have something similar here? If yes, then the authors should include such intuition in the main text.\n\n\n[1] https://arxiv.org/abs/2502.00666\n\n[2[ https://jmlr.org/papers/v16/vanerven15a.html", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n- Well-written\n\n**Weaknesses**\n- Lower bound w.r.t. policy coverage is lacking\n- References to the Appendix are lacking in the main text, e.g., Appendix D (experiments).\n- Moreover, discussions regarding the dependency of the coverage coefficient on $\\epsilon$ are lacking. Is it always negligible to claim that it is ignorable w.r.t. $1 / \\epsilon$? or can it be $\\frac{1}{\\epsilon} \\log\\frac{1}{\\epsilon}$, and so the current bound is tight up to logarithmic factors?", "was_revised": true, "final_justification": "During the rebuttals, some additional concerns for the lower bounds came up. But given the correctness of other parts as well as the significance of the new upper bound is appealing. Thus for the time-being (2025.08.03), I maintain my score of 4, but leaning towards acceptance, and willing to increase pending further discussions if possible. (2025.08.08) After the rebuttal, the authors have clarified all the concerns that I had, and thus I raise my score to 5.", "rebuttal": "Thank you for your positive feedback and insightful comments! We answer your questions point-by-point.\n\n**Q1.** Lower bound w.r.t. policy coverage is lacking.\n\n**A1.** While our lower bound mainly focuses on the dependency on $\\epsilon$, we can extend the hard case in Theorem 3.6 to show that additive dependency on coverage coefficient is necessary. \n\nWLOG, we assume that the coverage coefficient $C$ is an integer. In the new construction, we let the size of the action set $|\\cal{A}| = C$. We still define the same reward function as $R(\\theta, x, a)$ in the proof of Theorem 3.6, where the only difference is that $\\theta$ is now a mapping from $\\mathcal{X}$ to $\\cal{A}$. Similarly, we can show by Pinsker's inequality that $\\mathbb{E}\\_{Unif(\\theta)}\\mathbb{P}\\_\\theta(\\pi\\_{\\text{out}}(\\theta(x_0))\\le \\frac{1}{|\\mathcal{A}|}) \\ge \\frac{1}{2} - O(\\sqrt{c^2T/M})$.\n\nThen we have $$\n\\mathbb{E}\\_{\\theta \\sim \\text{Unif}(\\Theta)} \\mathbb{E}\\_{\\pi\\_{\\text{out}}}\n\\left[\n\\log \\frac{\\pi\\_{\\text{out}}(a \\mid x)}{\\pi^*(a \\mid x)}\n\\right]\n= \\mathbb{E}\\_{\\theta \\sim \\text{Unif}(\\Theta)}\n\\frac{1}{M} \\sum\\_{x \\in \\mathcal{X}} \\mathbb{E}\\_{a \\sim \\pi\\_{\\text{out}}(\\cdot \\mid x)}\n\\left[\n\\\\log \\frac{\\\\pi\\_{out}(a| x)}{\\\\pi\\^\\*(a|x)}\n\\right]\\\\ \\geq \\mathbb{E}\\_{\\theta \\sim \\text{Unif}(\\Theta)}\n\\frac{1}{M} \\sum\\_{x \\in \\mathcal{X}} \\mathbb{P}\\_{\\theta} \\left( \\pi_{\\text{out}}(\\theta(x)) \\leq \\frac{1}{|\\mathcal{A}|} \\right) \\cdot\n\\text{KL}(Unif(\\mathcal{A})\\|\\pi\\_\\theta\\^\\*)\n\\\\ \\geq \\left( \\frac{1}{2} - O(\\sqrt{c^2T/M}) \\right)\nO(\\eta^2c^2).$$\n\nWhen $\\epsilon$ is sufficiently small, we can set $c$ to $O(\\sqrt{\\epsilon / \\eta})$ and show that $T = \\Omega(\\eta M /\\epsilon) = \\Omega(\\eta \\log |\\mathcal{R}|/\\epsilon \\log C)$ where $C$ is the coverage coefficient, and $|\\mathcal{R}|$ is the size of the reward function class. Also note that we need at least $\\Omega(C \\log |\\mathcal{R}|/\\log C)$ rounds to explore all the actions. Hence the final lower bound is $\\Omega(\\max(\\eta \\log |\\mathcal{R}|/\\epsilon \\log C, C\\log |\\mathcal{R}|/\\log C)) = \\Omega(\\eta \\log |\\mathcal{R}|/\\epsilon \\log C+  C\\log |\\mathcal{R}|/\\log C)$, which nearly matches our upper bound.\n\n**Q2.** References to the Appendix are lacking in the main text, e.g., Appendix D (experiments).\n\n**A2.** Thank you for pointing this out. We will add necessary references in the revision.\n\n**Q3.** Moreover, discussions regarding the dependency of the coverage coefficient on $\\epsilon$ are lacking. s it always negligible to claim that it is ignorable w.r.t. $1/\\epsilon$\n or can it be $\\frac{1}{\\epsilon} \\log \\frac{1}{\\epsilon}$., and so the current bound is tight up to logarithmic factors?\n\n**A3.** In our setting, the coverage coefficient is not necessarily relevant to the value of $\\epsilon$. Note that in our upper bound, we only have an additive dependency on the coverage coefficient (the value of $m$ in Theorem 3.8 only depends on $D^2$, $\\eta$ and log-covering number of the reward function class). As explained in **A1**, we believe this dependency is not avoidable.\n \n**Q4.** In Rmk 3.9, the authors state that $e^B$ is probably unavoidable. Can the authors comment on whether the techniques from [1] can be adopted to remove such dependency?\n\n[1] Avoiding $\\mathbf{exp(R_{max})}$ scaling in RLHF through Preference-based Exploration.\n\n**A4.** Thank you for mentioning this recent work. We notice that Assumption 4.3 in [1] requires that the underlying reward function is a linear function, which is strictly stronger than the assumption made in this paper. (We only requires that the reward function class has a finite covering number.) Since our paper firstly consider the sharper bound with respect to $\\epsilon$, we believe that it would be a interesting future direction to consider remove $\\exp(R_{max})$ dependence in our bound when the reward function class is linear.\n\n**Q5.** What parts of this paper can be easily extended to general preference learning scenarios?\n\n**A5.** The main sharper analysis can be easily extended to the general preference setting, since the key technique is Lemma 2.9. This lemma implies that for any functions $R^*(x,a)$, $R(x,a)$, the KL-regularized function satisfies\n$$\nV(\\pi\\^\\*, R\\^\\*) - V(\\pi\\_R, R) \\le \\eta\\, \\mathbb{E}\\_{\\pi\\_{R'}}\\left( R(x,a) - R\\^\\*(x,a) \\right)^2,\n$$\nwhere \n$$\nV(\\pi, R) = \\mathbb{E}\\_{x \\sim d\\_0,\\, a \\sim \\pi}\\left[ R(x,a) - \\eta^{-1} \\mathrm{KL}(\\pi \\| \\pi\\_0) \\right].\n$$\nThis property follows from the strong convexity of the KL regularization, and thus also applies in the general preference setting, as the objective still includes a KL term.\n\nMoreover, according to [1], we can focus on the objective for the max player instead of analyzing the full Nash equilibrium. Therefore, it is promising that a similarly sharper bound can be obtained under general preference. Finally, if one considers uniform policy coverage (by extending Definition 2.5 to the general preference setting), this extension should be straightforward to accomplish.\n\n[1] Ye, C., et. al. Online iterative rein- forcement learning from human feedback with general preference model. NeurIPS.\n\n**Q6.** What is the intuition behind the fast rate of $1/\\epsilon$, in \"layman's terms\"? In learning theory, the intuition that I'm familiar with is regarding the curvature of the loss and mixability properties of the loss function. Do we have something similar here? If yes, then the authors should include such intuition in the main text.\n\n**A6.** Thank you for your valuable insight. Yes, there is indeed a similar intuition behind the fast \n$1/\\epsilon$ rate in this setting. Just as in learning theory where fast rates often arise from strong convexity or the mixability of the loss function, here the key driver is the curvature induced by the KL regularization. Specifically, the strong convexity of the KL divergence around the optimal policy ensures that the optimization landscape penalizes deviations more heavily, enabling tighter control over regret or value suboptimality. \n\nWe will revise the paper to emphasize this intuition more in the main text."}, {"review_id": "FJz78UQrrJ", "reviewer": "Reviewer_Gj2b", "summary": "This paper investigates the RLHF problem in the contextual bandit setting, with the goal of establishing tight sample complexity bounds. The authors analyze both the RL and RLHF settings, deriving matching upper and lower bounds for each. Notably, they demonstrate that incorporating a KL constraint into the problem yields a sample complexity that scales as $1/\\epsilon$, rather than $1/\\epsilon^2$ as in prior works.", "questions": "1. See weakness.\n2. Could you give a more detailed comparison between the things in Appendix B and [1]?\n\n\n\n[1] Zhao, H., Ye, C., Xiong, W., Gu, Q., & Zhang, T. (2025). Logarithmic Regret for Online KL-Regularized Reinforcement Learning. arXiv preprint arXiv:2502.07460.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\nThe work proposes a tight sample complexity for RL/RLHF with KL-regularization. The paper is well written and all the theorems seem correct.\n\n**Weaknesses**\n\n1. Definition 2.5 is too strong. Essentially, by collect N data from $\\pi_0$, we can immediately find $\\theta$ such that $\\mathbb{E}_{x, a\\sim \\pi_0}[(R(\\theta, x, a) - R(\\theta^\\star, x, a))^2] \\le c  \\frac{\\log |\\mathcal{R}|/\\delta }{N} $ with probability $1-\\delta$. By taking $N$ as some log order term, the right hand side can be bounded by constant. In this regard, Definition 2.5 actually claim that by collecting log number of data, we can find $\\theta$ such that $R(\\theta, x, a) - R(\\theta^\\star, x, a)$ can be well bounded for all $x, a$. This is impossible in practice.\n2. The results in the paper only holds when $\\eta$ is small, as a small $\\eta$ ensures that $\\pi(a|x)/\\pi^\\star(a|x)$ can be well bounded given $R(\\theta, x, a) - R(\\theta^\\star, x, a)$ is well bounded. This makes the proposed tight bound practically meaningless, considering that $\\eta$ is usually a very small value – for example, it is typically set to 1e-3 or 1e-4 in PPO or GRPO.\n3. The analysis under RL from preference feedback is actually trivial. Given that the reward is bounded by B, it is straightforward that using exp(B) times more preference feedback is equivalent to directly obtaining reward feedback.", "was_revised": true, "final_justification": "Most of my concerns are addressed. Specifically, the analysis for partial converge is valuable so I raise my score to 4.", "rebuttal": "Thank you for your constructive feedback!\n\n**Q1.** **Definition 2.5 is too strong.** Essentially, by collecting $N$ data from $\\pi_0$, we can immediately find $\\theta$ such that\n  $$\n  \\mathbb{E}_{x,a \\sim \\pi_0} \\left[ \\left(R(\\theta, x, a) - R(\\theta^*, x, a)\\right)^2 \\right] \\leq c \\cdot \\frac{\\log |\\mathcal{R}| / \\delta}{N}\n  $$\n  with probability $1 - \\delta$. By taking $N$ as some log-order term, the right-hand side can be bounded by a constant.\n\n  In this regard, Definition 2.5 actually claims that by collecting a logarithmic number of data, we can find $\\theta$ such that\n  $\n  R(\\theta, x, a) - R(\\theta^*, x, a)\n  $\n  can be well bounded for all $x, a$. This is impossible in practice.\n\n**A1.** This interpretation slightly misrepresents what Definition 2.5 claims. The definition does not imply that one can uniformly bound\n$R(\\theta, x, a) - R(\\theta^*, x, a)$\nfor all $x, a$ using only a logarithmic number of samples from $\\pi_0$. First, it is not proper to claim that $N$ is some log-order term. In practice, $\\log|\\mathcal{R}|$ is roughly in the same order as the number of parameters, which can still be quite large. Moreover, Definition 2.5 is quite standard in offline RL: the number of samples required to achieve small uniform error over all inputs typically scales with the complexity of the function class and the desired resolution. Although weaker assumptions are sometimes studied, Definition 2.5 is a common assumption for offline RL ([1, 2, 3]), especially for works aiming for tighter bounds. Also, $D^2$ in Definition 2.5 can be a large number when the action space is not well-covered, but our upper bound only has an additive dependence on $D^2$.\n\nWe can also obtain results under **partial coverage**. By using pessimism ($\\hat R(x,a) - R_*(x,a) \\le 0,\\forall x,a$) and denoting $\\Delta=\\hat R - R_*\\le 0$ and $\\pi_f(a|x)\\propto \\pi_0(a|x)\\exp(\\eta(\\gamma\\Delta(x,a) + R_*(x,a)))$, we can prove from (2.2) that by taking the derivative for $U(\\gamma)=\\sum_{a\\in \\mathcal{A}} \\pi_f^\\eta(a|x) (\\Delta(x,a))^2$ on $\\gamma$,\n\n$\n\\frac{\\partial U(\\gamma)}{\\partial \\gamma} = \\sum_{a\\in\\mathcal{A}} \\gamma\\cdot(\\Delta(x,a))^2\\pi\\_f\\^\\eta(a|x) \\cdot \\eta\\big(\\Delta(x,a) - \\mathbb{E}\\_{\\pi_f^\\eta} \\Delta(x,a)\\big) = \\gamma\\Big[\\mathbb{E}\\_{\\pi_f^\\eta} [\\Delta^3(x,a)] - \\mathbb{E}\\_{\\pi_f^\\eta} \\Delta(x,a)\\cdot \\mathbb{E}_{\\pi_f^\\eta} [\\Delta^2(x,a)]\\Big] \\le 0,$\n\nwhere the last inequality holds since $\\Delta(x,a)\\le0$. Therefore, we get\n\n$\n    Q(\\pi\\^\\*) - Q(\\hat\\pi_{pessi}) \\le \\eta\\mathbb{E}\\_{x\\sim d_0}U(\\gamma) \\le \\eta\\mathbb{E}\\_{x\\sim d_0}U(0) = \\eta\\mathbb{E}\\_{x\\sim d_0}\\sum_{a\\in \\mathcal{A}} \\pi\\_\\*(a|x) (\\Delta(x,a))^2 \\le \\eta C_{partial}\\mathbb{E}\\_{x\\sim d_0}\\mathbb{E}\\_{\\pi_0}(\\Delta(x,a))^2,\n$\n\nwhere $C_{partial}$ is the single-policy coverage. However, the partial coverage condition cannot enjoy the \\textbf{additive} dependence in the sample complexity. We will add and discuss this result in the revision.\n\n\n**Q2.** The results in the paper only hold when $\\eta$ is small. This makes the proposed tight bound practically meaningless, considering that $\\eta$ is usually a very small value — for example, it is typically set to $10^{-3}$ or $10^{-4}$ in PPO or GRPO.\n\n**A2.** It's not accurate to claim that $\\eta$ is usually as small as $10^{-3}$ or $10^{-4}$. A more realistic value is $\\eta \\in [0.01, 0.5]$, depending on the task and the algorithm.\n\n| Setting | Typical KL Coefficient ($\\beta$) |\n|--------|-----------------------------|\n| OpenAI's PPO for LLMs| 0.02 - 0.1 |\n| Hugging Face's TRL | 0.1 |\n| KL annealing setups | Start with 0.01, increase over time |\n| GRPO (Deepseek Math) | 0.04 |\n\nInstructGPT (OpenAI, 2022)\n\"Training language models to follow instructions with human feedback\" Appendix C.4\nhttps://arxiv.org/abs/2203.02155\n\nTRL (Hugging Face's trl library)\nPPO implementation with KL regularization\nhttps://github.com/huggingface/trl\n\nDeepSeekMath: Pushing the Limits of Mathematical\nReasoning in Open Language Models\nhttps://arxiv.org/pdf/2402.03300\n\nThe KL regularization coefficient in these reports is often denoted as $\\beta$ or $\\gamma$. You might have looked for the wrong notation.\n\n**Q3.** Could you give a more detailed comparison between the things in Appendix B and [1]?\n\n**A3.** [1] considers the online learning setting, where the learner interacts with the environment sequentially and must balance exploration and exploitation. To achieve a logarithmic regret bound, they design an optimism-based exploration strategy that leverages KL regularization to control exploration adaptively over time. Their algorithm explicitly addresses the challenges of limited feedback and non-stationary information acquisition.\n\nIn contrast, Appendix B of our work focuses on the active learning regime. Here, the learner is allowed to actively query reward labels without updating the model iteratively, and the goal is to minimize sample complexity while ensuring policy quality under KL regularization. The main difference lies in the type of interaction: online decision-making in [1] vs. selective querying in our setting.\n\n\n[1] Zhao, H., Ye, C., Xiong, W., Gu, Q., & Zhang, T. (2025). Logarithmic Regret for Online KL-Regularized Reinforcement Learning. arXiv preprint arXiv:2502.07460.\n\n[2] Ruosong Wang et al. What are the statistical limits of offline rl with linear function approxima-\ntion? In International Conference on Learning Representations (ICLR), 2021\n\n[3] Wei Xiong et al. Nearly minimax optimal offline reinforcement learning with linear function\napproximation: Single-agent mdp and markov game. In International Conference on Learning Rep-\nresentations (ICLR), 2023\n\n[4] Q Di et al. Pessimistic nonlinear least-squares value iteration for offline reinforcement learning. ICLR 2024."}, {"review_id": "8t2TYl5flZ", "reviewer": "Reviewer_Cnt4", "summary": "This paper provides sharper sample complexity bounds for KL-regularized contextual bandits and RLHF. The authors propose a two-stage mixed sampling algorithm: in the first stage, the reward model and policy are updated using samples from a reference policy; in the second stage, the resulting intermediate policy is used to collect additional samples to estimate the optimal policy. With this approach, the algorithm achieves an O(1/e) sample complexity for small e, improving upon the standard O(1/e^2) complexity.", "questions": "1. How does the coverage coefficient $D^2$ scale with the size of the state-action space? Could the authors provide any additional comparisons (either analytical or empirical) with existing online methods in the literature regarding sample complexity?\n2. Regarding Definition 3.5 (data coverage assumption for RLHF), the description is unclear. Could you provide additional explanation or intuition for the function $b(x)$? Is it dependent on $(\\theta, \\theta’)$?\n3. While higher KL regularization coefficients lead to sharper sample complexity bounds in suboptimality gap, it is unclear whether this can be called the \"power\" of regularization. Since increasing regularization changes the optimal policy (closer to the reference policy), isn't this just a trade-off?\n4. Minor issues:\n- Line 258: In $$\\pi: \\mathcal{X} \\to \\mathcal{A}$$, should the policy be deterministic or can it be stochastic?\n- Line 275: whether -> Whether\n- Definition 3.1 (Preference Oracle): Is the output of the mapping P {0, 1} or [0, 1]? It is unclear whether P is the sampled output or the probability.", "limitations": "The paper does not sufficiently discuss its limitations, which should be more explicitly addressed.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper provides a thorough theoretical analysis, including tight upper and lower bounds, and covers both global and local coverage assumptions.\n- The proposed two-stage mixed sampling algorithm is theoretically sound.\n- The algorithm is easily implementable, requiring only one additional policy update and online sampling step.\n\nWeakness:\n- The provided sample complexity is not adequately discussed or compared with prior work. For example, the number of samples required in the initial stage may explode in practice due to its dependence on the coverage coefficient, potentially limiting the algorithm’s applicability only to asymptotical analysis (with extremely small epsilon).\n- Empirical validation is limited, as the paper only compares the proposed method with an offline algorithm, where it is somewhat obvious that the online algorithm would perform better.\n- The potential limitations of the proposed algorithm are not thoroughly discussed.", "was_revised": true, "final_justification": "Based on the authors’ rebuttal and the strengths I mentioned in my initial review, I have decided to keep my score.", "rebuttal": ""}, {"review_id": "Z73WQC8A8t", "reviewer": "Reviewer_Rv2m", "summary": "The paper studied contextual bandits and RLHF problem with a KL-regularized objective function, and the novelty is mainly on the theoretical side of sharp analysis for sample complexity. The paper designed a two-stage mixed sampling algorithm to achieve a good upper bound, which is the lower bound for sample complexity for contextual bandits and the analysis can be extended to RLHF to get good results.", "questions": "1. The assumption of boundness for reward is widely used in related literature, but I didn't see the necessity of the non-negative assumption for reward. Could you clarify it further?\n2.  The authors discuss offline and online RLHF settings. But the writing is not clear, like which section or algorithm is for online and which part is for offline. For example, algorithm 1 seems like a hybrid setting. Could you discuss further?\n3. In line 216, $\\mathbb{E}_{x \\sim d_0} \\mathbb{E}_{a \\sim \\pi_o(\\cdot \\mid x)}\\left[\\left(R(\\widehat{\\theta}, x, a)-R\\left(\\theta_*, x, a\\right)\\right)^2\\right]=O(1 / n)$ is typically called generalization error. I didn't get why the authors called them in-sample error. Could you give further explanation?\n\nI really like the solid theoretical contribution of the paper. But I hope the authors have clearer writing to make the paper readable for more readers. Thus, depending on the rebuttal, I will consider changing my score.", "limitations": "1. The author mentioned the reverse KL regularization in the abstract. It will be better if the authors discuss forward KL v.s.  reverse KL regularization somewhere.\n2. I'd like to suggest that the authors give some proper citation for Definition 2.4.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\nThe paper provided a solid theoretical contribution, and they also provided experimental results to verify their findings.\n\nWeaknesses:\nThe writing and notation are confusing. For example, in line 217, what is $R(\\theta_*,x,\\pi^*)$? Please see the limitations part for more details.", "was_revised": true, "final_justification": "The paper provided solid theoretical contribution. But the writing part should be improved and some concept should be cleaner to make the paper more readable. Overall, I'd like to maintain my score.", "rebuttal": ""}]

Author rebuttal:

Meta-review: (a) Summary: This work provided sharper sample complexity bounds for KL-regularized contextual bandits and RLHF. The authors proposed a two-stage mixed sampling algorithm: in the first stage, the reward model and policy are updated using samples from a reference policy; in the second stage, the resulting intermediate policy is used to collect additional samples to estimate the optimal policy. With this approach, the algorithm achieves an $O(1/e)$ sample complexity for small e, improving upon the standard $O(1/e^2)$ complexity.

(b) Main reasons for decision/Cons: The work proposed a tight sample complexity for RL/RLHF with KL-regularization. The paper is generally well written.

(c) Change during rebuttal: The author(s) provided good response to allay the concerns from reviewers, especially the concerns about Definition 2.5 and Theorem 2.6 (lower bound). Some reviewers (e.g. Reviewer 5V1N) raised the rating during rebuttal. Such explanation should be included in the camera-to-ready version.

(d) Decision: I vote for accept with the average rating as 4.75.
- Most reviewers voted for 5 and are satisfied with the paper while only one reviewer (Reviewer Cnt4) feel that 'the paper does not sufficiently discuss its limitations, which should be more explicitly addressed.'
Decision: Accept (poster)