Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximation

Xiaoyu Chen, Han Zhong, Zhuoran Yang, Zhaoran Wang, Liwei Wang

TL;DR

This paper introduces the first theoretically grounded algorithm for preference-based reinforcement learning (PbRL) that can handle complex, non-linear function approximations. It achieves near-optimal sample efficiency and extends PbRL to a new "n-wise comparison" setting, making it more applicable to real-world scenarios where human feedback is costly.

What Problem Does This Paper Address?

Traditional reinforcement learning (RL) relies on explicit reward functions, which are often difficult to define in real-world applications like robotics or healthcare. Preference-based RL (PbRL) offers a solution by learning from human preferences between pairs of trajectories, rather than numerical rewards. However, existing theoretical guarantees for PbRL are limited to simple "tabular" settings (small, discrete state and action spaces). This paper tackles the crucial challenge of extending PbRL to settings with "general function approximation," where the underlying dynamics and preferences can be complex and continuous, a much more realistic scenario. This gap has prevented theoretical understanding and efficient algorithms from being applied to many practical problems.

Methods

The core contribution is a novel algorithm called Preference-based Optimistic Planning (PbOP). It's a model-based approach that:

  • Estimates the environment's transition dynamics and the human's preference function using value-targeted regression, a technique that handles uncertainty well.
  • Calculates "confidence sets" for these estimated models, quantifying the uncertainty in their predictions.
  • Defines "exploration bonuses" based on the width of these confidence sets. These bonuses guide the agent to explore uncertain parts of the state-action space.
  • Solves an "optimistic planning problem" to determine exploratory policies that balance exploiting current knowledge with gathering more information.

The paper also introduces a new setting called RL with n-wise comparisons, where a human provides preferences among n trajectories simultaneously. This is more efficient when sampling trajectories is expensive.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Bridging the gap to general function approximation is critical: The paper demonstrates that theoretical PbRL can move beyond simple tabular cases, opening doors for practical applications with complex environments.
  • Optimism in the face of uncertainty is key: The PbOP algorithm's success hinges on carefully quantifying and leveraging uncertainty in model estimations through confidence sets and exploration bonuses.
  • "n-wise comparisons" offer a more practical feedback mechanism: This new formulation acknowledges that humans might naturally compare multiple options at once, leading to more sample-efficient learning when trajectory generation is costly.
  • A unified framework: The paper shows how a single algorithmic framework can be adapted to both standard PbRL and the novel n-wise comparison setting, highlighting the generality of their approach.

Key Results

  • Provably efficient algorithm for general PbRL: The proposed PbOP algorithm achieves a near-optimal regret bound of $\tilde{O}(\operatorname{poly}(d H) \sqrt{K})$, where $d$ is the model complexity, $H$ is the horizon, and $K$ is the number of episodes. This is the first such theoretical guarantee for PbRL with general function approximation.
  • Near-optimal performance in linear settings: When specialized to linear models, the algorithm's regret matches theoretical lower bounds, indicating its efficiency.
  • First sample-efficient algorithm for n-wise comparisons: The paper introduces an algorithm for the new n-wise comparison setting with near-optimal regret.
  • Connection to "once-per-episode feedback": The work establishes a link between PbRL and another RL setting that deals with delayed feedback, showing how their algorithm can be adapted.

Limitations and Future Work

  • Computational inefficiency: The paper acknowledges that the current algorithm can be computationally intensive due to the non-Markovian nature of the feedback. Future work aims to develop more computationally efficient algorithms.
  • Gap in regret bounds: There's a theoretical gap of $\sqrt{H}$ in some regret bounds, which the authors conjecture could be closed with more refined concentration analysis.
  • Extension to n-wise ranking: The current n-wise comparison setting handles pairwise preferences. Future research could explore scenarios where humans provide a full ranking of n trajectories, which is a more complex feedback mechanism.

Summary updated

Abstract

We study human-in-the-loop reinforcement learning (RL) with trajectory preferences, where instead of receiving a numeric reward at each step, the agent only receives preferences over trajectory pairs from a human overseer. The goal of the agent is to learn the optimal policy which is most preferred by the human overseer. Despite the empirical successes, the theoretical understanding of preference-based RL (PbRL) is only limited to the tabular case. In this paper, we propose the first optimistic model-based algorithm for PbRL with general function approximation, which estimates the model using value-targeted regression and calculates the exploratory policies by solving an optimistic planning problem. Our algorithm achieves the regret of $\tilde{O} (\operatorname{poly}(d H) \sqrt{K} )$, where $d$ is the complexity measure of the transition and preference model depending on the Eluder dimension and log-covering numbers, $H$ is the planning horizon, $K$ is the number of episodes, and $\tilde O(\cdot)$ omits logarithmic terms. Our lower bound indicates that our algorithm is near-optimal when specialized to the linear setting. Furthermore, we extend the PbRL problem by formulating a novel problem called RL with $n$-wise comparisons, and provide the first sample-efficient algorithm for this new setting. To the best of our knowledge, this is the first theoretical result for PbRL with (general) function approximation.
BibTeX
@inproceedings{chen2022human,
  author = {Xiaoyu Chen and Han Zhong and Zhuoran Yang and Zhaoran Wang and Liwei Wang},
  title = {{Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximation}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=JP1w2w-7JK},
}
Figure