Regret Bounds for Reinforcement Learning from Multi-Source Imperfect Preferences
Authors: Ming Shi, Yingbin Liang, Ness B. Shroff, Ananthram Swami
Organizations: Department of Electrical Engineering, University at Buffalo, Buffalo, NY 14260, USA · Department of Electrical and Computer Engineering, The Ohio State University, Columbus, OH 43210, USA · Department of Electrical and Computer Engineering and Computer Science and Engineering, The Ohio State University, Columbus, OH 43210, USA · DEVCOM Army Research Laboratory, Adelphi, MD 20783, USA
Reinforcement learning from human feedback (RLHF) replaces hard-to-specify rewards with pairwise trajectory preferences, yet regret-oriented theory often assumes that preference labels are generated consistently from a single ground-truth objective. In practical RLHF systems, however, feedback is typically multi-source (annotators, experts, reward models, heuristics) and can exhibit systematic, persistent mismatches due to subjectivity, expertise variation, and annotation/modeling artifacts. We study episodic RL from multi-source imperfect preferences through a cumulative imperfection budget: for each source, the total deviation of its preference probabilities from an ideal oracle is at most ω over K episodes. We propose a unified algorithm with regret O~(K/M+ω), which exhibits a best-of-both-regimes behavior: it achieves M-dependent statistical gains when imperfection is small (where M is the number of sources), while remaining robust with unavoidable additive dependence on ω when imperfection is large. We complement this with a lower bound Ω~(max{K/M,ω}), which captures the best possible improvement with respect to M and the unavoidable dependence on ω, and a counterexample showing that naïvely treating imperfect feedback as oracle-consistent can incur regret as large as Ω~(min{ωK,K}). Technically, our approach involves imperfection-adaptive weighted comparison learning, value-targeted transition estimation to control hidden feedback-induced distribution shift, and sub-importance sampling to keep the weighted objectives analyzable, yielding regret guarantees that quantify when multi-source feedback provably improves RLHF and how cumulative imperfection fundamentally limits it.
Preference-based reinforcement learning learns policies from comparisons or rankings of behaviors instead of requiring hand-designed numerical rewards.
Human feedback often arrives as preferences rather than calibrated numeric rewards, motivating reinforcement learning from preferential feedback, also referred to as reinforcement learning from human feedback (RLHF). We present a rigorous theoretical study of preference-only learning in episodic kernel MDPs. In each episode, the learner deploys two policies from a common start state and receives a single binary label indicating which trajectory is preferred, modeled by a Bradley--Terry--Luce link on the difference of cumulative (unobserved) rewards. Under kernel-based assumptions on the reward and transition functions (one of the most general models amenable to theoretical analysis) we develop preference-based value estimation and confidence sets tailored to end-of-episode comparisons. We prove high-probability regret bounds that scale sublinearly in the number of episodes, implying that the value of the learned policy converges to that of the optimal policy.
Reinforcement learning with verifiable rewards (RLVR) has enabled progress on reasoning-intensive tasks by relying on task-specific verifiers that provide automated correctness signals. However, many realistic language tasks are difficult to equip with reliable verifiers, motivating a growing reliance on reinforcement learning from human feedback (RLHF). In this setting, we argue that a closer examination of how human feedback should be interpreted is essential. We introduce Regret-based Preference Optimization (RePO), which reframes RLHF through regret minimization rather than reward maximization. Human preferences are often shaped by prospective anticipation of outcomes and counterfactual comparisons to alternative behaviors, rather than by immediate, outcome-independent utility. RePO captures this structure by modeling preferences as behavior-conditioned assessments of relative suboptimality. Experiments on mathematical reasoning benchmarks and human preference datasets demonstrate consistent performance gains, indicating that RePO is an effective and human-aligned approach for training large language models.
Suhwan Kim, Taehyun Cho, Geon-Hyeong Kim +4
Seoul National University, Seoul, South Korea · LG AI Research, Seoul, South Korea · UNIST, Ulsan, South Korea +1
Reinforcement learning from human feedback (RLHF) has emerged as a central framework for aligning large language models (LLMs) with human preferences. Despite its practical success, RLHF raises fundamental statistical questions because it relies on noisy, subjective, and often heterogeneous feedback to learn reward models and optimize policies. This survey provides a statistical perspective on RLHF, focusing primarily on the LLM alignment setting. We introduce the main components of RLHF, including supervised fine-tuning, reward modeling, and policy optimization, and relate them to familiar statistical ideas such as Bradley-Terry-Luce (BTL) model, latent utility estimation, active learning, experimental design, and uncertainty quantification. We review methods for learning reward functions from pairwise preference data and for optimizing policies through both two-stage RLHF pipelines and emerging one-stage approaches such as direct preference optimization. We further discuss recent extensions including reinforcement learning from AI feedback, inference-time algorithms, and reinforcement learning from verifiable rewards, as well as benchmark datasets, evaluation protocols, and open-source frameworks that support RLHF research. We conclude by highlighting open challenges in RLHF. An accompanying GitHub demo https://github.com/Pangpang-Liu/RLHF_demo illustrates key components of the RLHF pipeline.
Pangpang Liu, Chengchun Shi, Will Wei Sun
Department of Biostatistics, Yale University. · Department of Statistics, London School of Economics and Political Science. · Mitch Daniels School of Business, Purdue University.