Selective Sampling and Imitation Learning via Online Regression
Ayush Sekhari Karthik Sridharan Wen Sun Runzhe Wu
We consider the problem of Imitation Learning (IL) by actively querying noisy
expert for feedback. While imitation learning has been empirically successful,
much of prior work assumes access to noiseless expert feedback which is not
practical in many applications. In fact, when one only has access to noisy
expert feedback, algorithms that rely on purely offline data (non-interactive
IL) can be shown to need a prohibitively large number of samples to be
successful. In contrast, in this work, we provide an interactive algorithm for
IL that uses selective sampling to actively query the noisy expert for
feedback. Our contributions are twofold: First, we provide a new selective
sampling algorithm that works with general function classes and multiple
actions, and obtains the best-known bounds for the regret and the number of
queries. Next, we extend this analysis to the problem of IL with noisy expert
feedback and provide a new IL algorithm that makes limited queries.
  Our algorithm for selective sampling leverages function approximation, and
relies on an online regression oracle w.r.t.~the given model class to predict
actions, and to decide whether to query the expert for its label. On the
theoretical side, the regret bound of our algorithm is upper bounded by the
regret of the online regression oracle, while the query complexity additionally
depends on the eluder dimension of the model class. We complement this with a
lower bound that demonstrates that our results are tight. We extend our
selective sampling algorithm for IL with general function approximation and
provide bounds on both the regret and the number of queries made to the noisy
expert. A key novelty here is that our regret and query complexity bounds only
depend on the number of times the optimal policy (and not the noisy expert, or
the learner) go to states that have a small margin.