# Avoiding mathbfexp(Rmax) scaling in RLHF through Preference-based Exploration

arXiv: https://arxiv.org/abs/2502.00666 · HTML: https://mlsanity.com/paper/2502.00666/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Placed in Reward modeling and RLHF, one of 10 directions in LLM alignment / RLHF / preference optimisation.
- Builds on 54 of its 63 references that are in the map.
- First posted on arXiv 2 Feb 2025.

## Placed in

- LLM alignment / RLHF / preference optimisation / [Reward modeling and RLHF](https://mlsanity.com/alignment/reward-modeling-and-rlhf/)

## Builds on (most cited first, 30 of 54)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [Think you have Solved Question Answering? Try ARC, the AI2 Reasoning Challenge](https://mlsanity.com/paper/1803.05457/) (2018)
- [HellaSwag: Can a Machine Really Finish Your Sentence?](https://mlsanity.com/paper/1905.07830/) (2019)
- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (2017)
- [TruthfulQA: Measuring How Models Mimic Human Falsehoods](https://mlsanity.com/paper/2109.07958/) (2021)
- [GPQA: A Graduate-Level Google-Proof Q&A Benchmark](https://mlsanity.com/paper/2311.12022/) (2023)
- [Fine-Tuning Language Models from Human Preferences](https://mlsanity.com/paper/1909.08593/) (2019)
- [A General Language Assistant as a Laboratory for Alignment](https://mlsanity.com/paper/2112.00861/) (2021)
- [SimPO: Simple Preference Optimization with a Reference-Free Reward](https://mlsanity.com/paper/2405.14734/) (2024)
- [A General Theoretical Paradigm to Understand Learning from Human Preferences](https://mlsanity.com/paper/2310.12036/) (2023)
- [Adversarial NLI: A New Benchmark for Natural Language Understanding](https://mlsanity.com/paper/1910.14599/) (2019)
- [AlpacaFarm: A Simulation Framework for Methods that Learn from Human Feedback](https://mlsanity.com/paper/2305.14387/) (2023)
- [AGIEval: A Human-Centric Benchmark for Evaluating Foundation Models](https://mlsanity.com/paper/2304.06364/) (2023)
- [Zephyr: Direct Distillation of LM Alignment](https://mlsanity.com/paper/2310.16944/) (2023)
- [SLiC-HF: Sequence Likelihood Calibration with Human Feedback](https://mlsanity.com/paper/2305.10425/) (2023)
- [Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint](https://mlsanity.com/paper/2312.11456/) (2023)
- [A Long Way to Go: Investigating Length Correlations in RLHF](https://mlsanity.com/paper/2310.03716/) (2023)
- [RLHF Workflow: From Reward Modeling to Online RLHF](https://mlsanity.com/paper/2405.07863/) (2024)
- [Direct Language Model Alignment from Online AI Feedback](https://mlsanity.com/paper/2402.04792/) (2024)
- [Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons](https://mlsanity.com/paper/2301.11270/) (2023)
- [Self-Play Preference Optimization for Language Model Alignment](https://mlsanity.com/paper/2405.00675/) (2024)
- [Implementation Matters in Deep Policy Gradients: A Case Study on PPO and TRPO](https://mlsanity.com/paper/2005.12729/) (2020)
- [Mitigating the Alignment Tax of RLHF](https://mlsanity.com/paper/2309.06256/) (2023)
- [Direct Nash Optimization: Teaching Language Models to Self-Improve with General Preferences](https://mlsanity.com/paper/2404.03715/) (2024)

## Built on by (most cited first, 8 of 8)

- [Accelerating RL for LLM Reasoning with Optimal Advantage Regression](https://mlsanity.com/paper/2505.20686/) (2025)
- [Extragradient Preference Optimization (EGPO): Beyond Last-Iterate Convergence for Nash Learning from Human Feedback](https://mlsanity.com/paper/2503.08942/) (2025)
- [Understanding the Performance Gap in Preference Learning: A Dichotomy of RLHF and DPO](https://mlsanity.com/paper/2505.19770/) (2025)
- [Count Counts: Motivating Exploration in LLM Reasoning with Count-based Intrinsic Rewards](https://mlsanity.com/paper/2510.16614/) (2025)
- [General Exploratory Bonus for Optimistic Exploration in RLHF](https://mlsanity.com/paper/2510.03269/) (2025)
- [Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Options](https://mlsanity.com/paper/2510.18713/) (2025)
- [Stratified Consistency Distillation for Natural Language Formalization](https://mlsanity.com/paper/2608.30258/) (2026)
- [Data-dependent Exploration for Online Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2605.04477/) (2026)

## Abstract (arXiv)

Reinforcement Learning from Human Feedback (RLHF) has emerged as a pivotal technique for large language model (LLM) alignment. This paper studies the setting of online RLHF and focus on improving sample efficiency. All existing algorithms in online RLHF, whether doing passive exploration or active exploration, suffer from a sample complexity that scales exponentially with the scale of the reward function. This fundamental limitation hinders their effectiveness in scenarios with heavily skewed preferences, e.g. questions with a unique correct solution. To address this, we introduce Self-Exploring Preference-Incentive Online Preference Optimization (SE-POPO), an online RLHF algorithm that for the first time achieves a sample complexity that scales polynomially with the reward scale, answering an open problem raised by Xie et al. (2024).. Theoretically, we demonstrate that the sample complexity of SE-POPO dominates that of existing exploration algorithms. Empirically, our systematic evaluation confirms that SE-POPO is more sample-efficient than both exploratory and non-exploratory baselines, in two primary application scenarios of RLHF as well as on public benchmarks, marking a significant step forward in RLHF algorithm design. The code is available at https://github.com/MYC000801/SE-POPO.