Contextual Bandits and Imitation Learning with Preference-Based Active Queries

We consider the problem of contextual bandits and imitation learning, where the learner lacks direct knowledge of the executed action's reward. Instead, the learner can actively query an expert at each round to compare two actions and receive noisy preference feedback. The learner's objective is twofold: to minimize the regret associated with the executed actions, while simultaneously, minimizing the number of comparison queries made to the expert. In this paper, we assume that the learner has access to a function class that can represent the expert's preference model under appropriate link functions, and provide an algorithm that leverages an online regression oracle with respect to this function class for choosing its actions and deciding when to query. For the contextual bandit setting, our algorithm achieves a regret bound that combines the best of both worlds, scaling as O(min √ T , d/∆), where T represents the number of interactions, d represents the eluder dimension of the function class, and ∆ represents the minimum preference of the optimal action over any suboptimal action under all contexts. Our algorithm does not require the knowledge of ∆, and the obtained regret bound is comparable to what can be achieved in the standard contextual bandits setting where the learner observes reward signals at each round. Additionally, our algorithm makes only O(minT, d 2 /∆ 2 ) queries to the expert. We then extend our algorithm to the imitation learning setting, where the learning agent engages with an unknown environment in episodes of length H each, and provide similar guarantees for regret and query complexity. The regret bound for our imitation learning algorithm, which relies on preferencebased feedback, matches the prior results in interactive imitation learning (Ross and Bagnell, 2014) that require access to the expert's actions as well as reward signals. Furthermore, we show that our algorithm enjoys improved query complexity bounds. Interestingly, in some cases, our algorithm for imitation learning via preference-feedback can even learn to outperform the underlying expert thus highlighting a practical benefit of considering preference-based feedback in imitation learning.