Dueling RL: Reinforcement Learning with Trajectory Preferences

Abstract

We consider the problem of preference based reinforcement learning (PbRL), where, unlike traditional reinforcement learning, an agent receives feedback only in terms of a 1 bit (0/1) preference over a trajectory pair instead of absolute rewards for them. The success of the traditional RL framework crucially relies on the underlying agent-reward model, which, however, depends on how accurately a system designer can express an appropriate reward function and often a non-trivial task. The main novelty of our framework is the ability to learn from preference-based trajectory feedback that eliminates the need to hand-craft numeric reward models. This paper sets up a formal framework for the PbRL problem with non-markovian rewards, where the trajectory preferences are encoded by a generalized linear model of dimension $d$. Assuming the transition model is known, we then propose an algorithm with almost optimal regret guarantee of $\tilde{\mathcal{O}}\left(SHd\log (T/\delta )\sqrt{T}\right)$. We further, extend the above algorithm to the case of unknown transition dynamics, and provide an algorithm with near optimal regret guarantee $\tilde{\mathcal{O}}((\sqrt{d}+H^2+|\mathcal{S}|)\sqrt{dT}+\sqrt{|\mathcal{S}||\mathcal{A}|TH})$. To the best of our knowledge, our work is one of the first to give tight regret guarantees for preference based RL problems with trajectory preferences.

arXiv commentAadirupa Saha and Aldo Pacchiano contributed equally

References in corpus (15)

• Optimizing Dialogue Management with Reinforcement Learning: Experiments with the NJFun System
• Maximum Entropy Deep Inverse Reinforcement Learning
• Apprenticeship Learning using Inverse Reinforcement Learning and Gradient Methods
• Provably Optimal Algorithms for Generalized Linear Contextual Bandits
• Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning
• Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning
• Time-uniform Chernoff bounds via nonnegative supermartingales
• Learning Trajectory Preferences for Manipulators via Iterative Improvement
• Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds
• Relative Upper Confidence Bound for the K-Armed Dueling Bandit Problem
• Provable Self-Play Algorithms for Competitive Reinforcement Learning
• Reducing Dueling Bandits to Cardinal Bandits
• Improved Optimistic Algorithms for Logistic Bandits
• Dueling Posterior Sampling for Preference-Based Reinforcement Learning
• On the Theory of Reinforcement Learning with Once-per-Episode Feedback