Regret Bounds for Reinforcement Learning from Multi-Source Imperfect Preferences

Ming Shi [email protected], Yingbin Liang [email protected], Ness B. Shroff [email protected], Ananthram Swami [email protected] · 2026

Read Regret Bounds for Reinforcement Learning from Multi-Source Imperfect Preferences by Ming Shi [email protected], Yingbin Liang [email protected], Ness B. Shroff [email protected], Ananthram Swami [email protected] (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-20453.txt.

Introduction

Shi and co-authors develop regret theory for reinforcement learning from messy, multi-source preferences. Standard theory assumes labels flow from one true objective. Real feedback mixes annotators, experts, reward models, and heuristics. Each source can drift from the ideal in a persistent way. They measure this drift with a cumulative imperfection budget per source. Their algorithm gains from having more sources when imperfection is small. A matching lower bound shows some cost of imperfection is unavoidable. Naive trust in bad labels, they show, can prove costly.

Catalog record

CREATORMing Shi [email protected], Yingbin Liang [email protected], Ness B. Shroff [email protected], Ananthram Swami [email protected]
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE113970
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.20453

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Regret Bounds for Reinforcement Learning from Multi-Source Imperfect Preferences Ming Shi [email protected], Yingbin Liang [email protected], Ness B. Shroff [email protected], Ananthram Swami [email protected] Abstract 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 ω \omega over K K episodes. We propose a unified algorithm with regret O ~ ​ ( K / M + ω ) \tilde{O}(\sqrt{K/M}+\omega) , which exhibits a best-of-both-regimes behavior: it achieves M M -dependent statistical gains when imperfection is small (where M M is the number of sources), while remaining robust with unavoidable additive dependence on ω \omega when imperfection is large. We complement this with a lower bound Ω ~ ​ ( max ⁡ { K / M , ω } ) \tilde{\Omega}(\max\{\sqrt{K/M},\omega\}) , which captures the best possible improvement with respect to M M and the unavoidable dependence on ω \omega , and a counterexample showing that naïvely treating imperfect feedback as oracle-consistent can incur regret as large as Ω ~ ​ ( min ⁡ { ω ​ K , K } ) \tilde{\Omega}(\min\{\omega\sqrt{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. † † shortheadings: Regret Bounds for RL from Multi-Source Imperfect Preferences / Shi, Liang, Shroff, and Swami † † firstpage: 1 † † editor: My editor keywords RLHF, multi-source imperfect preferences, multi-source gains, robustness to imperfection, regret bounds 1 Introduction Reinforcement learning (RL) learns a policy through interaction to optimize long-term performance, typically formalized as maximizing expected cumulative return. In standard RL, learning is guided by a designer-specified reward function, e.g., 18 ; 36 ; 2 . In many modern applications, however, specifying a reward that faithfully encodes the intended objective is difficult or even infeasible, notably in large language models (LLMs) ( 1 ; 39 ; 3 ; 14 ) , robotics ( 11 ) , autonomous driving ( 35 ) , and generative modeling ( 23 ) . This motivates learning from feedback signals that are easier to elicit than an explicit reward. Reinforcement learning from human feedback (RLHF) uses human judgments, most commonly pairwise comparisons between two trajectories (or responses), as the training signal for alignment ( 19 ; 6 ) . A canonical pipeline collects preference labels, fits a reward/preference model, and then optimizes a policy using the learned model. Recent theory has begun to characterize sample efficiency and regret in preference-based RL and RLHF, under the assumption that feedback is generated consistently from a single ground-truth objective with a stationary noise model, e.g., 8 ; 9 ; 41 ; 48 ; 13 . In practice, RLHF feedback rarely comes from a single homogeneous oracle. Labels may be produced by multiple human annotators, domain experts, AI-based feedback models, heuristics, or automated evaluation tools ( 22 ; 38 ; 5 ; 10 ) . These sources can differ systematically due to subjectivity, expertise, instruction framing, calibration drift, and modeling artifacts, leading to preference probabilities that persistently deviate from the idealized objective one would use to define “ground-truth” performance. Empirical studies report substantial disagreement and bias across sources and highlight the need to reason about feedback imperfection ( 30 ; 32 ; 47 ; 7 ) . A parallel robustness literature addresses other failure modes in RLHF and preference optimization, such as sparse outlier corruptions in preference labels ( 5 ) , reward/preference model misspecification and variance reduction in policy optimization ( 46 ) , reward-robust objectives under reward-model uncertainty ( 44 ) , and distribution shift across prompts or tasks ( 26 ) . However, a regret-oriented theory that explicitly models multi-source preference imperfection , allows history-dependent deviations, and yields a best-of-both-regimes characterization in terms of (K,M,\omega) remains underdeveloped, where K is the number of episodes, M is the number of sources, and \omega quantifies the cumulative deviation from an ideal preference oracle. We consider episodic MDP with trajectory-level objectives. In each episode k , the learner executes \pi_{k} to generate a trajectory \tau_{k}\sim(P^{*},\pi_{k}) and compares it against an independent reference-policy rollout \tau_{k,0}\sim(P^{*},\pi_{0}) , where P^{*} is the unknown transition kernel. An ideal preference oracle prefers \tau_{k} over \tau_{k,0} with probability p_{k}^{*}=\sigma(R^{*}(\tau_{k})-R^{*}(\tau_{k,0})) , where R^{*} is an unknown trajectory-level reward functional and \sigma is a known link function. The learner observes M binary labels per episode from M sources, each inducing its own preference probability p_{k}^{m} . We quantify multi-source imperfection by a cumulative deviation budget \sum_{k=1}^{K}|p_{k}^{m}-p_{k}^{*}|\leq\omega for all m\in[M] , which permits heterogeneous deviations while ruling out unbounded adversarial drift. Since only comparisons are observed, our learning target is naturally the induced comparison function q_{R}(\tau,\tilde{\tau})=\sigma(R(\tau)-R(\tilde{\tau})) . The imperfection budget creates a fundamental tension between robustness and statistical efficiency. When \omega is large, naïvely treating labels as unbiased can accumulate systematic error and can lead to regret that scales linearly with K . When \omega is small, pooling M labels per episode should sharpen preference estimation, so the regret should improve with M . Reconciling these behaviors requires a single unified algorithm with guarantees that capture both limits. A central goal of this paper is to characterize the transition between the two regimes and develop a method whose regret bound smoothly interpolates between the low- and high-imperfection cases. Our main contributions are as follows. • A best-of-both-regimes algorithm and regret upper bound. We propose RL from Multi-Source Imperfect Preferences ( RL-MSIP ) and prove regret \tilde{O}\!\big(\sqrt{K/M}+\omega\big) , yielding a unified best-of-both-regimes guarantee: M -dependent statistical gains when imperfection is small, and robustness with unavoidable \omega dependence when imperfection is large. At a high level, our method learns a confidence set for the comparison function from multi-source imperfect preference, performs optimistic planning under model estimation error, and uses filtering to keep the learning analyzable. • A fundamental lower bound. We establish a worst-case regret lower bound \tilde{\Omega}\!\big(\max\{\sqrt{K/M},\,\omega\}\big) , showing that the optimal dependence on the number of sources M is at best \sqrt{K/M} , even when imperfection is negligible, and additive dependence on the cumulative imperfection budget \omega is information-theoretically necessary. • A counterexample for “ignoring imperfection.” We exhibit an instance where an unweighted baseline (that pools all labels and treats imperfect feedback as unbiased) incurs \tilde{\Omega}\!\big(\min\{\omega\sqrt{K},\,K\}\big) regret, showing that naïvely aggregating multi-source labels can amplify cumulative imperfection into a substantially worse rate (e.g., yielding an \omega\sqrt{K} term rather than the desired additive \omega dependence). • Technical analysis. Our method involves (i) imperfection-adaptive weighted comparison learning that controls the imperfection cross-term; (ii) value-targeted transition estimation to handle the hidden feedback-induced distribution shift; (iii) policy-level optimism tailored to preference-only objectives; and (iv) sub-importance sampling to control sensitivity so the weighted objectives admit a sharp regret analysis. Our

Read the complete text