Introduction
In standard Reinforcement Learning (RL), agents learn by maximizing a numeric reward signal. However, in real-world applications such as autonomous driving or healthcare, designing a perfect reward function is notoriously difficult. Poorly designed rewards often lead to "reward hacking," where an agent exploits loopholes to achieve high scores without performing the desired task.
Preference-based RL (PbRL) offers a compelling alternative: instead of relying on a numeric reward, a human overseer evaluates two trajectories and indicates a preference. While this human-in-the-loop approach is more intuitive, it presents significant theoretical challenges. Most existing theoretical proofs for PbRL are confined to "tabular" settings, where the number of states and actions is small and finite.
This paper bridges the gap between empirical success and theoretical understanding by introducing the first provably efficient algorithm for PbRL that accommodates general function approximation. By moving beyond simple tabular models to complex function spaces (such as neural networks or linear mixtures), the proposed framework achieves near-optimal regret bounds in large or infinite state spaces.
Methodology: Preference-based Optimistic Planning (PbOP)
The authors propose a novel algorithm, Preference-based Optimistic Planning (PbOP), grounded in the "Optimism in the Face of Uncertainty" principle. The core components of the algorithm include:
- Model Learning: The agent employs value-targeted regression (a form of least-squares estimation) to approximate both the transition dynamics of the environment and the underlying human preference function.
- Confidence Sets: Acknowledging the uncertainty in its estimates, the algorithm maintains "confidence sets." These sets encompass all statistically plausible models given the data collected thus far.
- Optimistic Planning: Rather than committing to a single "best" model, the agent identifies policies that could be optimal under any plausible model within its confidence set. It deliberately selects exploratory pairs of trajectories that maximize uncertainty, thereby forcing the agent to learn about unexplored facets of the environment.
- Extension to n-wise Comparisons (PbOP+): The authors also introduce PbOP+, an extension designed for settings where a human compares $n$ trajectories simultaneously—a scenario common in clinical trials or distributed robotics.
Key Insights and Theoretical Contributions
As a theoretical work, the paper focuses on rigorous mathematical proofs and Regret Analysis rather than empirical evaluations on datasets like MuJoCo or Atari. Regret measures the total reward the agent loses compared to an omniscient optimal policy over $K$ episodes.
Overcoming the Non-Markovian Hurdle
Standard RL relies heavily on the Markov property, assuming the future depends only on the current state. In PbRL, however, preferences are evaluated over entire trajectories, rendering the feedback non-Markovian. The authors successfully demonstrate that efficient learning is still achievable despite this structural difficulty.
Managing Complexity via the Eluder Dimension
To handle general function approximation, the authors utilize the Eluder dimension. This sophisticated metric measures the complexity of a function class by capturing the number of samples required to accurately estimate an unknown function, allowing the theory to scale to complex models.
The Reduction Trick
A pivotal theoretical contribution is a formal reduction demonstrating that PbRL is closely related to "RL with once-per-episode feedback." This connection enabled the authors to derive a rigorous lower bound, proving that PbOP's performance is nearly as good as theoretically possible.
Key Results
- Regret Bounds: The PbOP algorithm achieves a regret bound of $\tilde{O}(\text{poly}(dH)\sqrt{K})$. In practical terms, as the agent interacts more with the environment over $K$ episodes, its rate of mistakes drops significantly, adhering to the optimal $\sqrt{K}$ convergence rate.
- Near-Optimality in Linear Settings: When specialized to linear models, the authors prove that their upper bound matches the theoretical lower bound (up to logarithmic factors). This establishes that the algorithm is essentially optimal for linear settings.
- The Power of $n$-wise Comparisons: For the $n$-wise comparison setting, the analysis shows that comparing multiple trajectories simultaneously accelerates the learning rate for the preference model by a factor of $\sqrt{n}$.
Limitations and Future Work
While the paper establishes strong statistical efficiency, it acknowledges several limitations and avenues for future research:
- Computational Efficiency: The algorithm is statistically efficient but computationally demanding. Solving the optimistic planning problem over history-dependent policies requires significant computational resources.
- The $\sqrt{H}$ Gap: There remains a minor mathematical gap—a factor of the square root of the horizon $H$—between the upper and lower bounds. The authors suggest that the upper bound could be tightened using more advanced concentration inequalities, such as Bernstein bounds.
- Ranking vs. Comparison: The current $n$-wise setting assumes the human provides pairwise comparisons for all pairs within a set. Future work could explore "ranking" (ordering all $n$ trajectories), which would yield even more information per human interaction.
Summary updated