Making RL with Preference-based Feedback Efficient via Randomization
This work addresses efficiency challenges in RLHF for researchers and practitioners by providing sample-efficient, computationally tractable methods with reduced human feedback queries, though it is incremental as it builds on existing RL and Thompson sampling frameworks.
The authors tackled the problem of making reinforcement learning from human preferences (RLHF) efficient by introducing randomized algorithms that achieve near-optimal tradeoffs between regret bounds and query complexity in linear MDPs and extend to nonlinear function approximation with Bayesian regret minimization.
Reinforcement Learning algorithms that learn from human feedback (RLHF) need to be efficient in terms of statistical complexity, computational complexity, and query complexity. In this work, we consider the RLHF setting where the feedback is given in the format of preferences over pairs of trajectories. In the linear MDP model, using randomization in algorithm design, we present an algorithm that is sample efficient (i.e., has near-optimal worst-case regret bounds) and has polynomial running time (i.e., computational complexity is polynomial with respect to relevant parameters). Our algorithm further minimizes the query complexity through a novel randomized active learning procedure. In particular, our algorithm demonstrates a near-optimal tradeoff between the regret bound and the query complexity. To extend the results to more general nonlinear function approximation, we design a model-based randomized algorithm inspired by the idea of Thompson sampling. Our algorithm minimizes Bayesian regret bound and query complexity, again achieving a near-optimal tradeoff between these two quantities. Computation-wise, similar to the prior Thompson sampling algorithms under the regular RL setting, the main computation primitives of our algorithm are Bayesian supervised learning oracles which have been heavily investigated on the empirical side when applying Thompson sampling algorithms to RL benchmark problems.