Rethinking the Hardness of PbRL: A Provable General Regret Bound

This paper studies 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 general function approximation framework, PbRL admits a √ T regret guarantee. In particular, we introduce a simple and provably efficient algorithm, 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 Dual Episodic Eluder Dimension (DEED), which quantifies the intrinsic difficulty of PbRL. We show that for linear MDPs, the DEED scales as O(dH), yielding a regret bound of O(dH √ T maxH 3/2 , 1/κ), where κ is a problem-dependent constant. This bound is nearoptimal 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 outcomebased reinforcement learning. Overall, our results provide a general regret guarantee for PbRL with outcome-based preference feedback and broad function approximation.

Our objective is to find a policy π that maximizes the expected return from the initial state s 1 , i.e., J(π) := Q π 1 (s 1 , π 1 ),

where

We define J ⋆ = J(π ⋆ ), Q ⋆ = Q π ⋆ , where π ⋆ is the optimal policy.

Given a function Q ∈ H h=1 S h × A h → [0, H] , a policy π, and a transition kernel P ∈ H h=1 S h × A h → ∆(S h+1 ) , we define the backup operator P π as

We also define the greedy operator P ⋆ as P ⋆ Q = P π Q Q, where π Q is the greedy policy w.r.t. Q. In what follows, we may omit the subscript h when it is clear from the context.

Given a reward-based dataset defined as D t-1 = (s i h , a i h , r i h ) h=∈[H],i∈[t-1] , one of the classical losses used for value function estimation is the Bellman error:

where the second term is introduced to mitigate the doublesampling problem (Antos et al., 2008;Chen & Jiang, 2019;Zanette et al., 2020).

Under Bellman completeness, 2 we have