Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint

1 Introduction

• The paper models RLHF as a reverse-KL-regularized contextual bandit, whose stochastic policy balances reward with diversity, fidelity, and proximity to the initial model.This formulation is intended to reflect practical alignment more accurately than deterministic reward maximization, which can cause overfitting and reward hacking.Source: §1 · p. 4
• Existing RLHF methods require near-uniform preference coverage over an exponentially large prompt-response space, making convergence to the optimal policy impractical.The broader RLHF pipeline also faces data-selection difficulty, reward misspecification, training instability, distribution shift, and performance degeneration under strong optimization pressure.Source: §1 · pp. 3–4
• The framework provides complementary finite-sample analyses for offline, online, and hybrid RLHF, with offline pessimism yielding sample-efficient learning and online exploration enabling continual policy improvement.Pessimism is implementable through PPO and DPO, while online and hybrid methods strategically interact with humans.Source: §1 · p. 4
• A 34.79% AlpacaEval2 win-rate from Zephyr-SFT-7B surpasses DPO, RSO, and many larger LLMs in real-world alignment experiments.The proposed algorithms are implemented with offline PPO, offline DPO, and InfoNCA as planning components.Source: §1 · p. 4

1.1 Related Work

• RLHF commonly follows supervised fine-tuning, reward modeling, and reward optimization, while PPO is difficult and resource-intensive and DPO offers a stable offline alternative.Related methods include reward-ranked or rejection-sampling fine-tuning and direct preference optimization, but comprehensive theoretical analysis remains open.Source: §1.1 · p. 5
• Compared with prior RLHF theory, this work introduces a KL-constrained formulation and hybrid setting that connect theoretical guarantees to practical algorithmic designs.The paper positions iterative DPO as a corollary of the framework while retaining external human or model reward signals and the initial policy as reference.Source: §1.1 · p. 6

2.1 Formulation of RLHF

• RLHF models prompts as states and generated responses as actions, with preferences governed by a Bradley–Terry model and an LLM represented as a policy.The ground-truth reward r∗ maps prompt-response pairs to [0,1], and preference probabilities use the sigmoid of reward differences.Source: §2.1 · p. 6
• The target policy maximizes expected ground-truth reward while remaining close to the pretrained policy through a KL penalty η > 0.The pretrained policy π0 is obtained before RLHF alignment, and prompts are sampled from d0; the formulation is widely used in practice and analyzed theoretically here.Source: §2.1 · p. 7
• The reward model assumes a linear parameterization rθ(x, a) = ⟨θ, ϕ(x, a)⟩ with bounded features and parameters, while allowing extension to general low-rank function classes.The stated bounds are ∥ϕ(x, a)∥≤1 and ∥θ∥≤B.Source: §2.1 · p. 7

2.2 The Insufficiency of Classic Frameworks

• Classic RLHF uses maximum-likelihood reward modeling followed by PPO-based policy optimization, with an information-theoretic oracle yielding a Gibbs policy.The reward model is fit from preference tuples using the Bradley–Terry likelihood, and the learned reward is optimized with a KL-regularized objective.Source: §2.2 · pp. 7–8
• Finite preference data causes reward over-optimization because learned rewards may fail on out-of-distribution responses, while DPO requires effectively infinite coverage of the prompt-response space to converge to π∗.The proxy reward aligns with the gold reward early in-distribution but diverges as distribution shift grows; the DPO limitation is stated for DPO as a representative direct-preference method.Source: §2.2 · p. 8, Figure 2 · p. 9

2.3 Preliminary

• The preliminary analysis decomposes policy suboptimality into reward-estimation errors under comparator and learned policies plus the policy-improvement error.In the KL-constrained setting, policies cannot be greedy or deterministic, so the additional improvement error must be estimated for oracle-induced policies.Source: §2.3 · pp. 8–9
• Covariance and elliptical-potential techniques quantify uncertainty in reward-feature differences, enabling exploration and bounding out-of-sample error from in-sample preference-data error.The analysis relies on low-rank structure so the elliptical potential cannot remain large too often, reducing generalization to online supervised error estimation and minimization.Source: §2.3 · p. 10

3.1 Setup

• The offline analysis addresses limited coverage because finite behavior-policy data may not cover the prompt space, making the learned reward and induced policy statistically dependent.Pessimism uses a conservative reward that is a high-probability lower bound on the true reward.Source: §3.1 · p. 11

3.2 Algorithms

• The offline GSHF framework implements pessimism either through an uncertainty-penalized reward estimator or a pessimistic target that also incorporates the KL divergence.Algorithm 1 outputs a Gibbs distribution with the modified reward; Option II is especially amenable to empirical oracle approximation.Source: §3.2 · p. 11

3.3 Main Results: Pessimism is Provably Efficient

• Pessimistic Offline GSHF achieves finite-sample guarantees under comparator-policy coverage, with uncertainty bonuses defined by either expected feature uncertainty or point-wise feature uncertainty.Option I uses Γe(π, ν, Doff) = ∥Ex∼d0[ϕ(x, π) −ν]∥Σ−1, while Option II uses Γ(x, a, ν, Doff) = ∥ϕ(x, a) −ν∥Σ−1.Source: §3.3 · p. 12
• Option I yields a sharper uncertainty bound and robustly improves over a reference policy regardless of dataset coverage, whereas Option II is easier to approximate using methods such as PPO.Setting ν = Ex∼d0[ϕ(x, πref)] supports the robust improvement property, and the reference vector can precondition the suboptimality bound.Source: §3.3 · p. 12

4.1 Setup: Batch Hybrid Learning

• The batch hybrid framework starts from Doff when available, repeatedly collects m preference-labeled response pairs, and incorporates the resulting batches into iterative learning.The framework models T batches of fixed size m and supports starting from an empty dataset when no offline data exists.Source: §4.1 · p. 13

4.2 Algorithms

• Online Iterative GSHF assigns exploitation to a main agent and exploration to an enhancer, allowing the latter to seek informative policies without incurring its own suboptimality penalty.When Doff has good coverage, the enhancer can avoid active exploration; otherwise it maximizes uncertainty relative to the main agent while maintaining moderate KL divergence.Source: §4.2 · pp. 13–14

4.3 Main Results: RLHF Benefits from Online Exploration

• Theorem 3 establishes a finite-sample guarantee for Algorithm 2 with Option II: under Assumption 1, after T = min{n ∈N+ : n ≥d log(n)} iterations, it holds with probability at least 1 −3δ.With explicit exploration, no offline dataset with good coverage is needed.Source: §4.3 · p. 16
• The two options trade algorithmic simplicity against data requirements: Option I is simpler but needs high-quality Doff, whereas Option II avoids that requirement but needs difficult uncertainty estimation.For neural networks, uncertainty estimators lack a closed form, so practical implementations may use heuristic estimators.Source: §4.3 · pp. 15–16

5 Implementations of GSHF

• GSHF implementations combine existing oracle-approximation algorithms, with PPO offering a standard deep-RL route and DPO providing a stable, easy-to-implement preference-learning alternative.DPO’s optimal policy matches the RLHF objective under the MLE reward, and the framework generalizes this result to incorporate pessimism.Source: §5 · pp. 16–17

5.1 Direct Preference Learning with Pessimism

• Direct preference learning with pessimism implements Algorithm 1 by adding an adaptive uncertainty-difference margin to each preference pair’s loss.Uncertainty can be estimated heuristically with an ensemble of five reward models; subtracting their variance reduces reward overoptimization for PPO and best-of-n sampling.Source: §5.1 · p. 17

5.2 Enhancer Explores with Variants of Main Agent Policy

• Enhancer exploration seeks policies that maximize their difference from the main agent while maintaining moderate KL divergence, using model variants or rejection sampling as heuristics.Model variants may use checkpoints from different training steps and sampling temperatures, while best-of-n sampling selects the highest-reward response among n independent samples.Source: §5.2 · pp. 17–18

5.3 Offline Learning with Pseudo-Labeling

• Offline RLHF methods use learned-reward pseudo-labels without new human feedback, with PPO and RAFT outperforming SFT and RSO outperforming DPO.RSO can suffer when rejection rates are extremely low: with r_x = 1 and η = 0.1, the acceptance rate is approximately 0.00004, potentially making it inferior to DPO.Source: §5.3 · pp. 18–19
• Multi-step RSO progressively approximates the target distribution, raising each rejection-sampling acceptance rate above exp(-1) > 0.367 and exponentially increasing acceptance with the number of steps.Choosing N = [r_x/η] + 1 steps yields an O(1) acceptance probability at each step, addressing RSO’s low sampling efficiency.Source: §5.3 · p. 19

6.1 Experiments Setup

• The experiments use Open-LLaMA-3B-V2 on Anthropic HH-RLHF, evaluate gold reward and KL divergence, and compare SFT, Offline DPO, RSO, Hybrid-GSHF-DPO, and Multi-step RSO.The setup includes 103K training prompts, 5K in-domain test prompts, 5K UltraFeedback OOD prompts, and η = 0.1.Source: §6.1 · pp. 19–20

6.2.1 Online Exploration Improves Model Performance

• Hybrid-GSHF-DPO surpasses DPO and RSO in gold reward and GPT-4 evaluations, while all RLHF methods outperform SFT and GSHF methods show smaller in-domain-to-OOD reward gaps.The comparison uses Table 2, Figure 3, and reward-KL trade-offs evaluated on in-domain and UltraFeedback prompts.Source: Table 2 · p. 21, §6.2.1 · pp. 21–22, Figure 3 · p. 22
• Each Hybrid-GSHF-DPO iteration strictly improves the reward-KL frontier, showing that online data is more efficient than additional offline data for iterative DPO.The comparison is made against offline DPO, which uses more offline data than the first iteration.Source: Figure 4 · p. 22, §6.2.1 · p. 22

6.2.2 RLHF Benefits from Pseudo Labelling and Iterative Learning

• Multi-step RSO strictly dominates RSO in reward-KL trade-offs, and its third iteration achieves the highest ground-truth reward, confirming benefits from pseudo-labelling and iterative learning.RSO also outperforms DPO despite DPO being selected using the ground-truth UltraRM-13B reward model.Source: Table 2 · p. 21, §6.2.2 · pp. 22–23

6.2.3 Robustness to Sampling Temperature and Length Bias

• GSHF improvements remain stable across sampling temperatures, with Multi-step RSO and Hybrid-GSHF-DPO consistently surpassing DPO and RSO; temperature 0.7 gives the highest gold reward for all models.Hybrid-GSHF-DPO gains more advantage over Multi-step RSO at lower temperatures, consistent with benefits from online exploration.Source: Figure 5 · p. 23, §6.2.3 · p. 23
• Hybrid-GSHF-DPO output length rises from 161 to 243 to 263 across three iterations, but its final length does not significantly exceed DPO or RSO.The authors caution that longer outputs may contribute to reward gains and recommend early stopping, replay, and thorough validation against reward hacking.Source: §6.2.3 · pp. 23–24

6.3 Scaling-up Experiments

• 34.79% length-control win rate is achieved by the strengthened Online-GSHF-DPO model, while the three-iteration model reaches 24.17% and surpasses offline DPO and RAFT by a large margin.The three-iteration model's raw win rate is 30.49%, suggesting bias toward longer responses from UltraRM-13B.Source: §6.3 · p. 24, Figure 6 · p. 25

7 Conclusion

• The framework models RLHF with a stochastic optimal policy and statistically efficient offline, online, and hybrid algorithms that address preference learning and KL-constraint challenges (Bai et al., 2022; Rafailov et al., 2023).It incorporates pessimism and optimism within the reverse-KL-regularized contextual bandit formulation.Source: §7 · p. 25
• The proposed practical implementations outperform strong baselines including DPO and RSO in real-world alignment experiments with large language models.The theoretical findings motivate implementations of the information-theoretical algorithms developed in Section 5.Source: §7 · p. 25

A Notation Table, Backgrounds, and Organization of Appendix

• The appendix improves readability with a notation table and an introduction to rejection sampling.Table 4 collects the paper’s notation, while the appendix introduces rejection sampling for completeness.Source: A Notation Table, Backgrounds, and… · p. 32, Table 4 · p. 32

A.1 Rejection Sampling

• Rejection sampling differs from best-of-n policy: it samples from a target distribution using a proposal distribution when the density ratio is bounded.Best-of-n selects the highest-reward sample among n draws, whereas rejection sampling accepts proposal samples probabilistically to represent the target distribution.Source: §A.1 · p. 32
• Rejection sampling becomes inefficient when density ratios are large, especially in high dimensions, and works best when the proposal closely approximates the target.The acceptance-rate problem reflects the curse of dimensionality and worsens as the bound M increases.Source: §A.1 · p. 32

A.2 Organization of the Appendix

• The appendix organizes proofs and supplementary material across pure online, offline, hybrid, DPO convergence, technical lemmas, and additional experimental details.The main batch-learning focus is supplemented by sequential-setting results with m = 1, while Appendices B–H cover the listed topics.Source: §A.2 · p. 33

B Proof of Online Learning

• The online framework addresses the KL-constraint contextual bandit setting omitted from the main paper.Source: B Proof of Online Learning · p. 33

B.1 Batch Online Learning

• Batch online learning targets an ϵ-optimal policy with sample complexity polynomial in 1/ϵ, feature dimension d, and other problem parameters.For m > 1, the method uses a sparser model update and collects response pairs from model variants with different temperatures to improve output diversity.Source: §B.1 · p. 33

B.2 Sequential Online Setting

• Sequential online learning with m = 1 outputs policy pairs whose cumulative and average suboptimality regrets are intended to be sublinear.The enhancer selects its policy by maximizing an uncertainty estimator based on data collected in previous batches.Source: §B.2 · p. 35
• Theorem 4 establishes high-probability regret guarantees for Algorithm 2 with Option II in the sequential online setting.The theorem uses regularization scaling with d, log(T/δ), γ, and B, and the stated guarantee holds with probability at least 1 −2δ.Source: §B.2 · p. 36
• The sequential regret proof combines decomposition, concentration of the covariance matrix, Cauchy-Schwarz, Jensen, and the elliptical potential lemma.Source: §B.2 · pp. 36–37

B.3 Construction of the Confidence Set

• The confidence-set construction proves that the optimal policy π∗ belongs to Πt at every iteration with high probability.The proof bounds two terms using concentration and policy-comparison lemmas, with an additional log T factor from the union bound over iterations.Source: §B.3 · p. 38

C.1 Proof of Theorem 1

• Theorem 1 is proved by combining maximum-likelihood reward estimation with either direct policy construction or point-wise pessimism, followed by Oracle 1 and concentration inequalities.The proof uses Equation (20), Lemma 1, Lemma 2, Lemma 8, and Cauchy-Schwarz steps to control the policy-value difference.Source: §C.1 · pp. 38–39

C.2 Proof of the Direct Preference Learning with Pessimism

• Direct preference learning with pessimism is analyzed by optimizing a KL-regularized target whose uncertainty bonus becomes an adaptive margin in the induced DPO objective.The proof establishes the correspondence between the reward-side objective and the closed-form policy, with the implicit reward shifted by the uncertainty penalty Γ(x, a).Source: §C.2 · p. 40

D.1 More Discussions on α(mT, Doff)

• Proposition 2 shows that α(mT, Doff) is controlled under single-policy coverage, a condition weaker than uniform coverage of the entire feature space.The analysis uses the covariance structure of the offline preference data and bounds its eigenvalues to derive the dependence on online and offline sample sizes.Source: §D.1 · pp. 40–41
• When offline and online datasets are comparable in size, the discussion states that α(mT, Doff) approximates 1/2, illustrated by LLaMA2-scale datasets with about 1.5 × 10^6 offline and 1.4 × 10^6 online samples.The condition requires the offline dataset size to be comparable to the total number of online samples, which the passage describes as realistic for LLMs.Source: §D.1 · p. 40
• Across the offline and hybrid analyses, covariance matrices provide the common mechanism for translating coverage assumptions and sequential data accumulation into finite-sample control.The hybrid proof explicitly defines covariance matrices and combines the resulting bounds after separately controlling P1 and P2.Source: §D.1 · p. 41, §D.2 · pp. 41–42

D.2 Sequential Hybrid Setting

• Theorem 5 establishes the sequential hybrid-setting guarantee for Algorithm 2 with Option II and m = 1 under Assumptions 1 and 2, with probability at least 1 − 2δ.The theorem specifies λ = d log(T/δ)/(γ^2B^2) and a β scaling stated as O in the supplied passage.Source: §D.2 · p. 41
• The sequential hybrid proof decomposes the error into covariance-controlled terms P1 and P2, then bounds them using Assumption 2 and Lemmas 9 and 10.The argument also uses Lemmas 1, 2, and 8, Cauchy-Schwarz, and the monotonicity relation Σt ⪰ Σoff.Source: §D.2 · p. 42

Proof of Theorem 2

• Theorem 2 is proved by controlling the exploration error and separately handling suboptimality because the reference policy is directly available for data collection.The proof follows the batch online-learning argument for exploration error and avoids optimism for relating reference-policy uncertainty to data.Source: §D.3 · p. 43
• Under Assumption 2, bounding the remaining terms with Cauchy–Schwarz and Lemma 8, then selecting parameters appropriately, completes the proof.The argument uses T ≥d log(T) and an absolute constant C in the final estimation.Source: §D.3 · p. 43

Implication

• When noff ≈mT, Proposition 2 gives α(mT, Doff) ≈1 and a corresponding final sample-complexity guarantee for finding an ϵ-optimal policy.This regime is identified with the LLaMA2 project (Touvron et al., 2023).Source: §D.3 · p. 43
• The convergence rate is jointly determined by offline-data coverage and reward-function complexity, but the guarantee may be conservative because online data can improve coverage during training.In particular, online data may increase the coverage coefficient Ccov along the way.Source: §D.3 · p. 43

• DPO’s loss yields the maximum-likelihood preference model pθ = p∗ and enforces πθ(a1|x)/πθ(a2|x) = π∗(a1|x)/π∗(a2|x) on support(πoff).This analysis uses the population-loss setting with sufficiently many offline samples.Source: E Discussion on the Coverage Condition… · p. 44
• For outputs generated by π∗ but not πoff, the loss is unaffected, so πθ may assign arbitrary probabilities there while still minimizing the population loss.The minimizing policy combines π∗ on covered outputs with an arbitrary distribution on uncovered outputs, subject to normalization.Source: E Discussion on the Coverage Condition… · p. 44
• Convergence to π∗ for every action with π∗(a|x) > 0 therefore requires no uncovered outputs, or sufficient constraints on the uncovered support.The dataset imposes constraints through Lemma 5 only where the behavior policy provides coverage.Source: E Discussion on the Coverage Condition… · pp. 44–45
• A predetermined offline dataset may lack adequate coverage for preference learning at state-of-the-art model scale, while finite data further aggravates distribution shift.Source: E Discussion on the Coverage Condition… · p. 45

F Technical Lemma Proofs

• The proof of Lemma 2 rewrites the oracle-induced policy and reward parameterization to relate policy optimization error under the estimated reward to the lemma’s target expression.The argument uses the normalization constant associated with the reward reparameterization and substitutes the resulting equality into the lemma.Source: F Technical Lemma Proofs · p. 45
• The proof of Lemma 5 reformulates its loss as a KL divergence plus a constant, yielding a unique optimum and a ratio-based sufficient condition for optimality.The stated condition is πθ(a1|x)/πθ(a2|x) = π∗(a1|x)/π∗(a2|x).Source: F Technical Lemma Proofs · p. 45

G Technical Lemmas

• Lemma 6 states Jensen’s inequality for convex functions under finite weighted sums and probability measures, with norms included through convexity from the triangle inequality.Its proof is cited to Proposition A.9 of Zhang (2023).Source: G Technical Lemmas · pp. 45–46
• Lemma 8 provides an in-sample maximum-likelihood estimation error guarantee under bounded features and parameter norm, with probability at least 1 − δ.The lemma assumes ∥ϕ(x, a)∥≤1 and ∥θ∥≤B for all context-action pairs and defines γ = 1/(2 + exp(−B) + exp(B)).Source: G Technical Lemmas · p. 46
• Lemma 9 gives an elliptical potential bound for bounded vector sequences accumulated in a positive-definite covariance matrix.It assumes ∥xi∥2 ≤ L and defines the sequence through updates of the form Λt = Λ0 + Σi.Source: G Technical Lemmas · p. 46
• Lemma 10 establishes concentration of an inverse covariance under bounded features when the regularization scale satisfies λ = Ω(d log(n/δ)).The guarantee holds with probability at least 1 − δ for the conditional feature distributions and their expected covariance matrix.Source: G Technical Lemmas · p. 46
• Lemma 11 identifies the minimizer of a KL-regularized loss as a Gibbs distribution proportional to the reference policy times an exponentiated loss-dependent term.The result is attributed to Proposition 7.16 and Theorem 15.3 of Zhang (2023).Source: G Technical Lemmas · p. 46

Implementation

• Experiments run on 8×A40 (48G) GPUs with 600G RAM and half-precision bf16 training, using open-source TRL and LMFlow implementations.The code is planned for public release on GitHub in the camera-ready version.Source: H More Experiment Details · p. 47

Hyperparameters

• Hyperparameters are compactly reported in Tables 8 and 9, with further details provided in the subsequent subsections.Source: H More Experiment Details · p. 47

Rejection-rate illustration

• Figure 7 illustrates rejection rates for η_i = Nη/i under a Gaussian-mixture π_0, with r = [1, 0]⊤a and η = 1 for π_r.The model follows the setting of Figure 1, and preference is mathematically captured by a reward linearly dependent on a.Source: Figure 7 · p. 47, H More Experiment Details · p. 47

H.1 Implementation Details

• Rejection sampling generates K responses per prompt, extracts n preference pairs through 2n sampling rounds, randomizes them, and labels positives by comparative rewards, following Liu et al. (2023a).The rejection coefficient corresponds to the target distribution’s η parameter, and the implementation follows Algorithm 1’s Python code.Source: §H.1 · p. 47
• Multi-step approximation divides the path into three steps with η ∈{0.1, 0.3, 0.5} and uses 25K prompts per step.RSO uses a rejection coefficient selected from {0.5, 1, 2, 3}, larger than the DPO KL coefficient, consistent with Liu et al. (2023a).Source: §H.1 · p. 47
• Hybrid GSHF uses a gold reward trained on UltraFeedback, Anthropic HH-RLHF, and other datasets with LLaMA2-13B, while accumulating past and present samples across iterations.The 75K Anthropic HH-RLHF prompts support three iterations: initial DPO training, then online labels from model samples, with each iteration restarting from the initial model.Source: §H.1 · p. 47
• GPT-4 evaluation uses GPT-4-turbo on 100 prompts, with DPO-aligned models as the baseline and final winners counted as win+tie×0.5.Detailed results appear in Table 3, while test hyperparameters are provided in Table 8.Source: §H.1 · p. 48
• The evaluation judge prompt instructs GPT-4 to compare two assistants impartially, assess helpfulness and related qualities, and return [[A]], [[B]], or [[C]].It explicitly guards against position, response-length, and assistant-name biases.Source: §H.1 · p. 48
• Absolute reward values in Table 2 use the initial model’s test reward as the baseline by convention (Gao et al., 2023; Dong et al., 2023).This baseline convention is stated for presenting absolute values rather than for defining the GPT-4 comparison.Source: §H.1 · p. 48

H.2 Examples

• Sample outputs from different RLHF algorithms are provided for in-distribution HH-RLHF prompts in Tables 5 and 6 and an out-of-distribution Ultra-Chat prompt in Table 7.Tables 8 and 9 additionally report fine-tuning and auxiliary-training hyperparameters.Source: §H.2 · p. 48, Table 5 · p. 49, Table 6 · p. 50