Greedy Sampling Is Provably Efficient for RLHF

AI summary

Overview

Research area: Theoretical reinforcement learning from human feedback (RLHF), specifically KL-regularized contextual bandits with preference feedback.

Technical level: Advanced. The paper is a theory contribution built on regret analysis, Eluder dimension, maximum likelihood estimation, and Nash equilibrium in zero-sum games.

Scope: The paper proves that simply using empirical estimates ("greedy sampling") — without optimism or pessimism — achieves order-optimal regret and sample complexity for RLHF under both general preference and Bradley-Terry preference models, in both online and offline settings.

What This Paper Is About

RLHF trains language models using human comparisons rather than absolute scores, and its standard objective adds a Kullback-Leibler (KL) penalty that keeps the learned policy close to a reference policy. Prior theory for this setting mostly relied on reward-based Bradley-Terry models and on classic optimism or pessimism machinery (confidence bounds) to handle uncertainty. This paper asks whether that machinery is actually necessary, and shows that directly sampling from the optimal policy of the empirical estimate — greedy sampling — is provably efficient under both general and Bradley-Terry preference models, in both online and offline learning.

Key Contributions

1. First logarithmic regret for the general preference model. Under the general preference model in the online setting, the authors derive a regret upper bound of O(log(T)) with time horizon T, which they state is the first result of this order for the general preference model, improving on the previous O(√T) bound implied by Ye et al. (2024b).

2. First O(ε⁻¹) sample complexity for the general preference model in the offline setting. Using only a single-policy coverage condition, the offline algorithm attains O(ε⁻¹) sample complexity, improving over the previous O(ε⁻²) order from Ye et al. (2024b).

3. Provable efficiency of greedy sampling without confidence bounds. These guarantees come from algorithms that use empirical estimates as-is, rather than constructing optimistic or pessimistic estimates. The authors state this is the first time provable efficiency of greedy sampling is established for RLHF, regardless of the preference model, and that it avoids the computationally heavy construction of upper and lower confidence bounds.

4. Matching bounds for the Bradley-Terry model plus simulation corroboration. Under the BT model, greedy sampling again achieves O(log(T)) online regret and O(ε⁻¹) offline sample complexity, matching the upper bounds previously derived under optimism (Zhao et al., 2025a) and pessimism (Zhao et al., 2025b). Simulation results under both preference models show the simple greedy approach performs statistically comparably to prior methods with more sophisticated policy constructions.

Main Findings

• The optimal policy class is structurally constrained. Proposition 1 shows that both the BT optimal policy π*_BT and the general-preference Nash equilibrium policy π*_GP lie in the class Π_ℱ = {π_f : π_f(a|x) ∝ π_0(a|x) exp(η f(x,a)), f ∈ ℱ}, where ℱ contains functions mapping context-action pairs to [0,1].

• Bounded likelihood ratio is the key structural property. Lemma 1 proves that for any π_f in Π_ℱ, the ratio π_f(a|x)/π_0(a|x) lies in the interval [exp(−η), exp(η)] for all (x, a). The authors note this means candidate optimal policies are stochastic with the same support as the reference policy, and that this ratio is unbounded in canonical RL or bandits without KL-regularization.

• Online regret under the general preference model. Theorem 1: under the finite, realizable function class assumption (Assumption 1), with probability at least 1 − δ, Regret_GP(T) = O(exp(η) d_GP(𝒫, λ, T) log(N_𝒫 T / δ)), where d_GP is the Eluder dimension for the general preference model.

• Online regret under the Bradley-Terry model. Theorem 2: under Assumption 2, with probability at least 1 − δ, Regret_BT(T) = O(exp(η) d_BT(ℛ, λ, T) log(N_ℛ T / δ)), matching the order achieved by optimism in Zhao et al. (2025a).

• A stated cost of greedy sampling. Both online theorems incur an additional multiplicative factor of exp(η) in the bounds; the authors note the analysis focuses on scaling behavior with respect to T, and that refined analysis of other constants such as the dependency on η appears in the appendices.

• Offline sample complexity under the general preference model. Theorem 3: with probability at least 1 − δ and for m ≥ 8η(exp(2η) + 4η² exp(8η)) C(𝒟_0, (π_0, π_0)) log(N_𝒫/δ)/ε, the output policy of Algorithm 2 is ε-optimal.

• Offline sample complexity under the Bradley-Terry model. Theorem 4: with probability at least 1 − δ and for m ≥ 6η exp(2η + 1) C(𝒟_0, (π_0, π_0)) log(N_ℛ/δ)/ε, the output policy of Algorithm 2 is ε-optimal.

• Data coverage definition. Definition 5 defines a coverage coefficient C(𝒟, (π¹, π²)) = max over a¹, a², x of π¹(a¹|x)π²(a²|x) / (μ¹(a¹|x)μ²(a²|x)), where μ¹ and μ² are the empirical distributions of the first and second actions in the offline dataset; the offline bounds require only this single-policy coverage with (π_0, π_0).

• Comparison to canonical RL lower bounds. The paper situates its results against the traditional lower bounds of Ω(√T) regret and Ω(ε⁻²) sample complexity in canonical RL, while noting prior KL-regularized results achieved O(log(T)) regret and O(ε⁻¹) sample complexity only under direct reward observations or the BT model.

• Experiments use a small synthetic linear setup. Experiments focus on the online setting, in a linear setting with randomly sampled context vectors and 6 fixed actions; the general preference model uses dimension k × k × k and the BT model uses dimension k × k, with k set to 5. The paper reports comparisons of step regret and cumulative regret between greedy sampling and optimism (Figures 1 and 2) but the truncated content does not report numerical values for these comparisons.

Methodology in Plain English

The authors model RLHF as a KL-regularized contextual bandit: a policy takes a prompt (context) and produces a response (action), and the learner only sees binary preference labels between pairs of responses. For the general preference model, they take a game-theoretic view in which a max-player and a min-player compete in a zero-sum game, with a unique Nash equilibrium policy; for the BT model, a latent reward function induces the preference probabilities through a sigmoid of reward differences.

Both algorithms are deliberately simple. In the online algorithm, at each round the learner samples one action from its current learned policy and one from the fixed reference policy, observes the preference label, fits the preference model (or reward model under BT) by maximum likelihood estimation on all data seen so far, and then sets the next policy to the optimal policy (or Nash equilibrium policy) of that empirical estimate — no bonus term, no uncertainty-driven enhancer policy. The offline algorithm fits the same maximum likelihood estimate on a pre-collected dataset and outputs the corresponding optimal policy.

The analysis rests on two ingredients. The first is the bounded likelihood-ratio property of the optimal policy class from the KL-regularization. The second is a decomposition of the per-step regret that converts the problem into bounding squared differences between the empirical estimate and the true preference model, ultimately controlled by a confidence interval and aggregated using the Eluder dimension of the function class. For the offline case, a similar decomposition reduces the analysis to bounding the deviation of the maximum likelihood estimate from the true parameter under a coverage condition.

Why This Matters

Impact on research. The paper challenges a default assumption in the theory of RLHF: that optimism or pessimism is needed to handle uncertainty. By showing that greedy sampling is provably efficient and that this follows from the structure of the KL-regularized optimal policy class, it suggests a simpler template for designing and analyzing RLHF algorithms, one that removes the need for confidence-bound construction and the associated optimization problems.

Real-world applications.

• Post-training pipelines for large language models, where preference data is collected iteratively and where simpler update rules can reduce engineering and compute overhead.
• Alignment workflows that rely on human comparison data rather than absolute ratings, including the general preference formulations that do not assume a latent reward.
• Offline or batch learning from previously logged preference datasets, where sample efficiency directly determines labeling cost.
• Systems where solving a confidence-bound optimization at every round is impractical, making a maximum-likelihood-then-optimize loop attractive.

Industry relevance. The paper states that greedy policies need fewer computational resources than pessimism-based offline RLHF, which requires solving optimization problems at every step. Since RLHF is described as a key component of post-training for widely used LLMs, any reduction in per-round optimization cost is potentially relevant to teams training and aligning models at scale.

Future Directions

• Tightening the η dependence. The online bounds carry an extra multiplicative exp(η) factor relative to optimism-based results; the authors point to refined analyses of constants and dependency on η as an area covered in their appendices rather than resolved in the main results.
• Relaxing realizability and finiteness. The analysis assumes finite, realizable function classes; the authors note the finiteness assumption can be relaxed using standard covering-number arguments, leaving open how far the guarantees extend in practice.
• Extending beyond the KL-regularized contextual bandit. The single-turn bandit formulation is the setting studied here; multi-turn or sequential RLHF is not addressed in the provided content.
• Scaling the experimental evidence. The simulations use 6 fixed actions and dimension parameter k = 5 in a linear synthetic setting; whether the greedy approach retains statistically comparable performance in larger-scale or non-linear preference settings is not established by the reported experiments.

Target Audience

Researchers and graduate students working on the theory of reinforcement learning and RLHF, particularly those interested in regret bounds, sample complexity, and the role of KL-regularization in shaping the optimal policy class. It is also relevant to practitioners who want to understand why a simple maximum-likelihood-then-greedy procedure can be a principled default for preference-based post-training, though the paper's density of formal definitions and theorems makes it most accessible to readers with a background in bandit or RL theory.

Authors’ abstract

Reinforcement Learning from Human Feedback (RLHF) has emerged as a key technique for post-training large language models. Despite its empirical success, the theoretical understanding of RLHF is still limited, as learning the KL-regularized target with only preference feedback poses additional challenges compared with canonical RL. Existing works mostly study the reward-based Bradley-Terry (BT) preference model, and extend classical designs utilizing optimism or pessimism. This work, instead, considers the general preference model (whose practical relevance has been observed recently) and obtains performance guarantees with major, order-wise improvements over existing ones. Surprisingly, these results are derived from algorithms that directly use the empirical estimates (i.e., greedy sampling), as opposed to constructing optimistic or pessimistic estimates in previous works. This insight has a deep root in the unique structural property of the optimal policy class under the KL-regularized target, and we further specialize it to the BT model, highlighting the surprising sufficiency of greedy sampling in RLHF.