# Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF

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

## Key facts

- Cited by 106 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 55 of its 73 references that are in the map.
- First posted on arXiv 31 May 2024.

## 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 55)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [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)
- [Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2204.05862/) (2022)
- [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)
- [Chatbot Arena: An Open Platform for Evaluating LLMs by Human Preference](https://mlsanity.com/paper/2403.04132/) (2024)
- [Length-Controlled AlpacaEval: A Simple Way to Debias Automatic Evaluators](https://mlsanity.com/paper/2404.04475/) (2024)
- [Adversarial NLI: A New Benchmark for Natural Language Understanding](https://mlsanity.com/paper/1910.14599/) (2019)
- [AGIEval: A Human-Centric Benchmark for Evaluating Foundation Models](https://mlsanity.com/paper/2304.06364/) (2023)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [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)
- [Iterative Reasoning Preference Optimization](https://mlsanity.com/paper/2404.19733/) (2024)
- [From r to Q^*: Your Language Model is Secretly a Q-Function](https://mlsanity.com/paper/2404.12358/) (2024)
- [Nash Learning from Human Feedback](https://mlsanity.com/paper/2312.00886/) (2023)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [A unified view of entropy-regularized Markov decision processes](https://mlsanity.com/paper/1705.07798/) (2017)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [Direct Nash Optimization: Teaching Language Models to Self-Improve with General Preferences](https://mlsanity.com/paper/2404.03715/) (2024)
- [Orca-Math: Unlocking the potential of SLMs in Grade School Math](https://mlsanity.com/paper/2402.14830/) (2024)
- [A Minimaximalist Approach to Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2401.04056/) (2024)
- [Understanding the performance gap between online and offline alignment algorithms](https://mlsanity.com/paper/2405.08448/) (2024)

## Built on by (most cited first, 30 of 106)

- [Interpretable Preferences via Multi-Objective Reward Modeling and Mixture-of-Experts](https://mlsanity.com/paper/2406.12845/) (2024)
- [Self-Improvement in Language Models: The Sharpening Mechanism](https://mlsanity.com/paper/2412.01951/) (2024)
- [Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignment](https://mlsanity.com/paper/2503.21878/) (2025)
- [Outcome-based Exploration for LLM Reasoning](https://mlsanity.com/paper/2509.06941/) (2025)
- [Process Reward Model with Q-Value Rankings](https://mlsanity.com/paper/2410.11287/) (2024)
- [Correcting the Mythos of KL-Regularization: Direct Alignment without Overoptimization via Chi-Squared Preference Optimization](https://mlsanity.com/paper/2407.13399/) (2024)
- [Self-rewarding correction for mathematical reasoning](https://mlsanity.com/paper/2502.19613/) (2025)
- [Unintentional Unalignment: Likelihood Displacement in Direct Preference Optimization](https://mlsanity.com/paper/2410.08847/) (2024)
- [Building Math Agents with Multi-Turn Iterative Preference Learning](https://mlsanity.com/paper/2409.02392/) (2024)
- [From Lists to Emojis: How Format Bias Affects Model Alignment](https://mlsanity.com/paper/2409.11704/) (2024)
- [Iterative Nash Policy Optimization: Aligning LLMs with General Preferences via No-Regret Learning](https://mlsanity.com/paper/2407.00617/) (2024)
- [Sharp Analysis for KL-Regularized Contextual Bandits and RLHF](https://mlsanity.com/paper/2411.04625/) (2024)
- [Improving Sampling Efficiency in RLVR through Adaptive Rollout and Response Reuse](https://mlsanity.com/paper/2509.25808/) (2025)
- [The Crucial Role of Samplers in Online Direct Preference Optimization](https://mlsanity.com/paper/2409.19605/) (2024)
- [A Comprehensive Survey of Direct Preference Optimization: Datasets, Theories, Variants, and Applications](https://mlsanity.com/paper/2410.15595/) (2024)
- [Reinforce LLM Reasoning through Multi-Agent Reflection](https://mlsanity.com/paper/2506.08379/) (2025)
- [Online Preference Alignment for Language Models via Count-based Exploration](https://mlsanity.com/paper/2501.12735/) (2025)
- [On the Position Bias of On-Policy Distillation](https://mlsanity.com/paper/2606.22600/) (2026)
- [Improving LLM General Preference Alignment via Optimistic Online Mirror Descent](https://mlsanity.com/paper/2502.16852/) (2025)
- [Accelerating RL for LLM Reasoning with Optimal Advantage Regression](https://mlsanity.com/paper/2505.20686/) (2025)
- [Co-rewarding: Stable Self-supervised RL for Eliciting Reasoning in Large Language Models](https://mlsanity.com/paper/2508.00410/) (2025)
- [Logarithmic Regret for Online KL-Regularized Reinforcement Learning](https://mlsanity.com/paper/2502.07460/) (2025)
- [PILAF: Optimal Human Preference Sampling for Reward Modeling](https://mlsanity.com/paper/2502.04270/) (2025)
- [KnowRL: Exploring Knowledgeable Reinforcement Learning for Factuality](https://mlsanity.com/paper/2506.19807/) (2025)
- [Do We Need to Verify Step by Step? Rethinking Process Supervision from a Theoretical Perspective](https://mlsanity.com/paper/2502.10581/) (2025)
- [Sample-Efficient Alignment for LLMs](https://mlsanity.com/paper/2411.01493/) (2024)
- [Extragradient Preference Optimization (EGPO): Beyond Last-Iterate Convergence for Nash Learning from Human Feedback](https://mlsanity.com/paper/2503.08942/) (2025)
- [Representation-Based Exploration for Language Models: From Test-Time to Post-Training](https://mlsanity.com/paper/2510.11686/) (2025)
- [Qsharp: Provably Optimal Distributional RL for LLM Post-Training](https://mlsanity.com/paper/2502.20548/) (2025)
- [Right Now, Wrong Then: Non-Stationary Direct Preference Optimization under Preference Drift](https://mlsanity.com/paper/2407.18676/) (2024)

## Abstract (arXiv)

Reinforcement learning from human feedback (RLHF) has emerged as a central tool for language model alignment. We consider online exploration in RLHF, which exploits interactive access to human or AI feedback by deliberately encouraging the model to produce diverse, maximally informative responses. By allowing RLHF to confidently stray from the pre-trained model, online exploration offers the possibility of novel, potentially super-human capabilities, but its full potential as a paradigm for language model training has yet to be realized, owing to computational and statistical bottlenecks in directly adapting existing reinforcement learning techniques. We propose a new algorithm for online exploration in RLHF, Exploratory Preference Optimization (XPO), which is simple and practical -- a one-line change to (online) Direct Preference Optimization (DPO; Rafailov et al., 2023) -- yet enjoys the strongest known provable guarantees and promising empirical performance. XPO augments the DPO objective with a novel and principled exploration bonus, empowering the algorithm to explore outside the support of the initial model and human feedback data. In theory, we show that XPO is provably sample-efficient and converges to a near-optimal language model policy under natural exploration conditions, irrespective of whether the initial model has good coverage. Our analysis, which builds on the observation that DPO implicitly performs a form of Qstar-approximation (or, Bellman error minimization), combines previously disparate techniques from language modeling and theoretical reinforcement learning in a serendipitous fashion through the perspective of KL-regularized Markov decision processes. Empirically, we find that XPO is more sample-efficient than non-exploratory DPO variants in a preliminary evaluation.