Rethinking the Hardness of PbRL: A Provable General Regret Bound

This paper studies \emph{preference-based reinforcement learning} (PbRL), where agents learn from comparative, trajectory-level feedback rather than numeric rewards. While PbRL has seen rapid empirical and theoretical progress, existing analyses are largely confined to restricted settings and fail to jointly capture the outcome-based and comparison-based nature of preference feedback. We prove that under a broad \emph{general function approximation} framework, PbRL admits a $\sqrt{T}$ regret guarantee. In particular, we introduce a simple and provably efficient algorithm, \emph{Recursive Trajectory-based Preference Q-Learning} (RTPQ), and establish its regret bound while explicitly accounting for the trajectory-level and comparative structure of preferences. Our analysis is characterized by a new complexity measure, the \emph{Dual Episodic Eluder Dimension} (DEED), which quantifies the intrinsic difficulty of PbRL. We show that for linear MDPs, the DEED scales as $\mathcal{O}(dH)$, yielding a regret bound of $\tilde{\mathcal{O}}(dH\sqrt{T}\max(H^{3/2},\,1/\kappa))$, where $\kappa$ is a problem-dependent constant. This bound is near-optimal up to horizon- and problem-dependent factors when compared to standard reward-based linear MDPs. In addition, our framework recovers the best-known regret bounds in the special cases of dueling bandits and standard outcome-based reinforcement learning. Overall, our results provide a general regret guarantee for PbRL with outcome-based preference feedback and broad function approximation.

Preference-based Reinforcement Learning (PbRL) has become a cornerstone for aligning modern AI, such as Large Language Models (LLMs), because it allows agents to learn from human comparisons (e.g., "Output A is better than Output B") rather than artificial numeric rewards. However, because agents must evaluate entire multi-step trajectories and compare them rather than receiving immediate feedback, PbRL is generally considered much harder to analyze and optimize than standard reward-based RL. We wanted to bridge this gap and understand the intrinsic limits of learning from preferences. To tackle this, we introduce a new complexity measure called the **Dual Episodic Eluder Dimension (DEED)**. DEED is designed to capture the two distinct difficulties of PbRL: managing long trajectories and interpreting comparative feedback. By using DEED, we prove that a new, simple algorithm—**Recursive Trajectory-based Preference Q-Learning (RTPQ)**—can achieve a stable $\sqrt{T}$ regret bound, which measures how quickly the agent minimizes its mistakes over time. **Our results imply** that learning from human preferences is not fundamentally more inefficient than learning from crisp, numeric rewards. By successfully unifying standard reinforcement learning and dueling bandits under one comprehensive framework, this work provides the first general, near-optimal guarantee for PbRL using broad function approximation—proving that preference-based AI alignment rests on solid theoretical ground.