[2603.20453] Reinforcement Learning from Multi-Source Imperfect Preferences: Best-of-Both-Regimes Regret

Computer Science > Machine Learning arXiv:2603.20453 (cs) [Submitted on 20 Mar 2026] Title:Reinforcement Learning from Multi-Source Imperfect Preferences: Best-of-Both-Regimes Regret Authors:Ming Shi, Yingbin Liang, Ness B. Shroff, Ananthram Swami View a PDF of the paper titled Reinforcement Learning from Multi-Source Imperfect Preferences: Best-of-Both-Regimes Regret, by Ming Shi and 3 other authors View PDF HTML (experimental) 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 \emph{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 \emph{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$ episodes. We propose a unified algorithm with regret $\tilde{O}(\sqrt{K/M}+\omega)$, 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 $\omega$ when imp...