# Towards Efficient Online Exploration for Reinforcement Learning with Human Feedback

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Reward modeling and RLHF, one of 10 directions in LLM alignment / RLHF / preference optimisation.
- Builds on 23 of its 30 references that are in the map.
- First posted on arXiv 26 Sep 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, 23 of 23)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [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)
- [Fine-Tuning Language Models from Human Preferences](https://mlsanity.com/paper/1909.08593/) (2019)
- [A General Theoretical Paradigm to Understand Learning from Human Preferences](https://mlsanity.com/paper/2310.12036/) (2023)
- [Self-Play Fine-Tuning Converts Weak Language Models to Strong Language Models](https://mlsanity.com/paper/2401.01335/) (2024)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [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)
- [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)
- [From r to Q^*: Your Language Model is Secretly a Q-Function](https://mlsanity.com/paper/2404.12358/) (2024)
- [Camels in a Changing Climate: Enhancing LM Adaptation with Tulu 2](https://mlsanity.com/paper/2311.10702/) (2023)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Direct Nash Optimization: Teaching Language Models to Self-Improve with General Preferences](https://mlsanity.com/paper/2404.03715/) (2024)
- [Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF](https://mlsanity.com/paper/2405.21046/) (2024)
- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [Value-Incentivized Preference Optimization: A Unified Approach to Online and Offline RLHF](https://mlsanity.com/paper/2405.19320/) (2024)
- [Self-Exploring Language Models: Active Preference Elicitation for Online Alignment](https://mlsanity.com/paper/2405.19332/) (2024)
- [PILAF: Optimal Human Preference Sampling for Reward Modeling](https://mlsanity.com/paper/2502.04270/) (2025)
- [Understanding the Performance Gap in Preference Learning: A Dichotomy of RLHF and DPO](https://mlsanity.com/paper/2505.19770/) (2025)

## Abstract (arXiv)

Reinforcement learning with human feedback (RLHF), which learns a reward model from human preference data and then optimizes a policy to favor preferred responses, has emerged as a central paradigm for aligning large language models (LLMs) with human preferences. In this paper, we investigate exploration principles for online RLHF, where one seeks to adaptively collect new preference data to refine both the reward model and the policy in a data-efficient manner. By examining existing optimism-based exploration algorithms, we identify a drawback in their sampling protocol: they tend to gather comparisons that fail to reduce the most informative uncertainties in reward differences, and we prove lower bounds showing that such methods can incur linear regret over exponentially long horizons. Motivated by this insight, we propose a new exploration scheme that directs preference queries toward reducing uncertainty in reward differences most relevant to policy improvement. Under a multi-armed bandit model of RLHF, we establish regret bounds of order T(β+1)/(β+2), where β>0 is a hyperparameter that balances reward maximization against mitigating distribution shift. To our knowledge, this is the first online RLHF algorithm with regret scaling polynomially in all model parameters.