Contextual Bandits and Imitation Learning via Preference-Based Active
  Queries
Ayush Sekhari Karthik Sridharan Wen Sun Runzhe Wu
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 two-fold: 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\{\sqrt{T}, d/\Delta\})$, where $T$
represents the number of interactions, $d$ represents the eluder dimension of
the function class, and $\Delta$ represents the minimum preference of the
optimal action over any suboptimal action under all contexts. Our algorithm
does not require the knowledge of $\Delta$, 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(\min\{T, d^2/\Delta^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. Interestingly, our
algorithm for imitation learning can even learn to outperform the underlying
expert, when it is suboptimal, highlighting a practical benefit of
preference-based feedback in imitation learning.