Regret Bounds for Reinforcement Learning from Multi-Source Imperfect Preferences
On the map: LLM alignment / RLHF / preference optimisation → Reward modeling and RLHF
Abstract (arXiv)
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 tildeO(√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 tildeOmega(max√K/M,ω), which captures the best possible improvement with respect to M and the unavoidable dependence on ω, and a counterexample showing that na"ively treating imperfect feedback as oracle-consistent can incur regret as large as tildeOmega(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.
Key facts. Cited by 1 paper 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 36 of its 48 references that are in the map. First posted on arXiv 20 Mar 2026.
Builds on
36 of 48 references.
Closest ancestors · 17
Same direction, newest first
- 2025Robust Reinforcement Learning from Human Feedback for Large Language Models Fine-Tuning3 Apr
- 2025Distributionally Robust Reinforcement Learning with Human Feedback1 Mar
- 2024Reward-Robust RLHF in LLMs18 Sep
- 2024Robust Reinforcement Learning from Corrupted Human Feedback21 Jun
- 2024Optimizing Autonomous Driving for Safety: A Human-Centric Approach with LLM-Enhanced RLHF6 Jun
- 2024Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF31 May
- 2024RLHF from Heterogeneous Feedback via Personalization and Preference Aggregation30 Apr
- 2024Exploration-Driven Policy Optimization in RLHF: Theoretical Insights on Efficient Data Utilization15 Feb
- 2024Corruption Robust Offline Reinforcement Learning with Human Feedback9 Feb
- 2024A Minimaximalist Approach to Reinforcement Learning from Human Feedback8 Jan
- 2023A Survey of Reinforcement Learning from Human Feedback22 Dec
- 2023Nash Learning from Human Feedback1 Dec
5 more
- 2023RLAIF vs. RLHF: Scaling Reinforcement Learning from Human Feedback with AI Feedback1 Sep
- 2023Open Problems and Fundamental Limitations of Reinforcement Learning from Human Feedback27 Jul
- 2023Is RLHF More Difficult than Standard RL?25 Jun
- 2023Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons26 Jan
- 2017Deep reinforcement learning from human preferences12 Jun
Other references · 19
- 2023GPT-4 Technical Reportcited by 18,396
- 2023LLaMA: Open and Efficient Foundation Language Modelscited by 14,132
- 2023PaLM 2 Technical Reportcited by 1,162
- 2023Whose Opinions Do Language Models Reflect?cited by 773
- 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
- 2023Aligning Text-to-Image Models using Human Feedbackcited by 422
- 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
- 2023Large Language Model as Attributed Training Data Generator: A Tale of Diversity and Biascited by 232
- 2023Do LLMs exhibit human-like response biases? A case study in survey designcited by 180
- 2024Provably Robust DPO: Aligning Language Models with Noisy Feedbackcited by 135
- 2022Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximationcited by 81
- 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
7 more
- 2022Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processescited by 33
- 2021On the Theory of Reinforcement Learning with Once-per-Episode Feedbackcited by 32
- 2013Learning Trajectory Preferences for Manipulators via Iterative Improvementcited by 31
- 2020Online learning in MDPs with linear function approximation and bandit feedbackcited by 30
- 2023A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraintscited by 17
- 2022Investigations of Performance and Bias in Human-AI Teamwork in Hiringcited by 16
- 2024ROPO: Robust Preference Optimization for Large Language Modelscited by 16
Built on by
Citing papers per year: 2026: 1.
1 paper.
Similar, not cited
Close in wording, no citation either way
- 2026Learning Kernel-Based MDPs from Episodic Preferential Feedback
- 2026Reinforcement Learning from Human Feedback: A Statistical Perspective
- 2026Wasserstein Distributionally Robust Regret Optimization for Reinforcement Learning from Human Feedback
- 2025Towards Efficient Online Exploration for Reinforcement Learning with Human Feedback
- 2026A Regret Minimization Framework on Preference Learning in Large Language Models
- 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint
- 2022Models of human preference for learning reward functions
- 2025Policy-labeled Preference Learning: Is Preference Enough for RLHF?