Greedy Sampling Is Provably Efficient for RLHF

• URL: http://arxiv.org/abs/2510.24700v1
• Date: Tue, 28 Oct 2025 17:52:08 GMT
• Title: Greedy Sampling Is Provably Efficient for RLHF
• Authors: Di Wu, Chengshuai Shi, Jing Yang, Cong Shen,
• Abstract summary: This work considers the general preference model and obtains performance guarantees with major, order-wise improvements over existing ones.<n>Surprisingly, these results are derived from algorithms that directly use the empirical estimates.<n>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.
• Score: 19.590316589389577
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• ExPO: Unlocking Hard Reasoning with Self-Explanation-Guided Reinforcement Learning [12.83211408922535]
  Reinforcement learning-style post-training improves reasoning by optimizing model outputs based on reward or preference signals.<n> GRPO-style approaches implement this by using self-generated samples labeled by an outcome-based verifier.<n>We propose $textbfSelf-Explanation Policy Optimization (ExPO)$-a simple and modular framework that generates such samples by conditioning on the ground-truth answer.
  arXiv  Detail & Related papers  (2025-07-03T17:44:55Z)
• Generalist Reward Models: Found Inside Large Language Models [50.7432354447554]
  We show that a powerful reward model is already latently present within any Large Language Models (LLMs) trained via standard next-token prediction.<n>We prove that this endogenous reward is not a reward function learned through offline inverse reinforcement learning.<n>We also prove that subsequent reinforcement learning using this endogenous reward leads to a policy with a provably superior error bound compared to the base model.
  arXiv  Detail & Related papers  (2025-06-29T13:45:54Z)
• Reward Model Overoptimisation in Iterated RLHF [10.041379049591969]
  Reinforcement learning from human feedback (RLHF) is a widely used method for aligning large language models with human preferences.<n> RLHF often suffers from reward model overoptimisation, in which models overfit to the reward function.<n>We present the first comprehensive study of overoptimisation in iterated RLHF.
  arXiv  Detail & Related papers  (2025-05-23T17:36:13Z)
• Self-Boost via Optimal Retraining: An Analysis via Approximate Message Passing [58.52119063742121]
  Retraining a model using its own predictions together with the original, potentially noisy labels is a well-known strategy for improving the model performance.<n>This paper addresses the question of how to optimally combine the model's predictions and the provided labels.<n>Our main contribution is the derivation of the Bayes optimal aggregator function to combine the current model's predictions and the given labels.
  arXiv  Detail & Related papers  (2025-05-21T07:16:44Z)
• A Minimalist Approach to LLM Reasoning: from Rejection Sampling to Reinforce [68.99924691391048]
  We revisit GRPO from a reinforce-like algorithm perspective and analyze its core components.<n>We find that a simple rejection sampling baseline, RAFT, yields competitive performance than GRPO and PPO.<n>Motivated by this insight, we propose Reinforce-Rej, a minimal extension of policy gradient that filters both entirely incorrect and entirely correct samples.
  arXiv  Detail & Related papers  (2025-04-15T16:15:02Z)
• Robust Reinforcement Learning from Human Feedback for Large Language Models Fine-Tuning [11.31665596884142]
  Reinforcement learning from human feedback (RLHF) has emerged as a key technique for aligning the output of large language models with human preferences.<n>Most existing RLHF algorithms use the Bradley-Terry model, which relies on assumptions about human preferences that may not reflect the complexity and variability of real-world judgments.<n>We propose a robust algorithm to enhance the performance of existing approaches under such reward model misspecifications.
  arXiv  Detail & Related papers  (2025-04-03T16:16:35Z)
• Iterative Nash Policy Optimization: Aligning LLMs with General Preferences via No-Regret Learning [55.65738319966385]
  We propose a novel online algorithm, iterative Nash policy optimization (INPO)<n>Unlike previous methods, INPO bypasses the need for estimating the expected win rate for individual responses.<n>With an LLaMA-3-8B-based SFT model, INPO achieves a 42.6% length-controlled win rate on AlpacaEval 2.0 and a 37.8% win rate on Arena-Hard.
  arXiv  Detail & Related papers  (2024-06-30T08:00:34Z)
• Regularizing Hidden States Enables Learning Generalizable Reward Model for LLMs [25.011675414622392]
  This study introduces a novel approach to enhance the reward model's generalization ability against distribution shifts. We retain the base model's language model head and incorporate a suite of text-generation losses to preserve the hidden states' text-generation capabilities. Our experimental results demonstrate that the introduced regularization technique markedly improves the accuracy of learned reward models.
  arXiv  Detail & Related papers  (2024-06-14T17:49:59Z)
• Scaling Laws for Reward Model Overoptimization in Direct Alignment Algorithms [50.808123629394245]
  Direct Alignment Algorithms (DDAs) like Direct Preference Optimization have emerged as alternatives to the classical RLHF pipeline. This work formulates and formalizes the reward over-optimization or hacking problem for DAAs and explores its consequences across objectives, training regimes, and model scales.
  arXiv  Detail & Related papers  (2024-06-05T03:41:37Z)
• Towards Understanding the Influence of Reward Margin on Preference Model Performance [8.891183078634786]
  This study introduces a novel method to estimate the preference differences without the need for detailed, exhaustive labels from human annotators. Our experimental results provide empirical evidence that incorporating margin values into the training process significantly improves the effectiveness of reward models.
  arXiv  Detail & Related papers  (2024-04-07T12:10:04Z)
• Online Iterative Reinforcement Learning from Human Feedback with General Preference Model [20.81421550138371]
  We investigate Reinforcement Learning from Human Feedback (RLHF) in the context of a general preference oracle. We consider a standard mathematical formulation, the reverse-KL regularized minimax game between two LLMs for RLHF under general preference oracle. We show that this framework is strictly more general than the reward-based one, and propose sample-efficient algorithms for both the offline learning from a pre-collected preference dataset and online learning.
  arXiv  Detail & Related papers  (2024-02-11T21:44:21Z)
• Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint [56.74058752955209]
  This paper studies the alignment process of generative models with Reinforcement Learning from Human Feedback (RLHF) We first identify the primary challenges of existing popular methods like offline PPO and offline DPO as lacking in strategical exploration of the environment. We propose efficient algorithms with finite-sample theoretical guarantees.
  arXiv  Detail & Related papers  (2023-12-18T18:58:42Z)
• Provable Reward-Agnostic Preference-Based Reinforcement Learning [61.39541986848391]
  Preference-based Reinforcement Learning (PbRL) is a paradigm in which an RL agent learns to optimize a task using pair-wise preference-based feedback over trajectories. We propose a theoretical reward-agnostic PbRL framework where exploratory trajectories that enable accurate learning of hidden reward functions are acquired.
  arXiv  Detail & Related papers  (2023-05-29T15:00:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.