  We study interactive imitation learning, where a learner interactively
queries a demonstrating expert for action annotations, aiming to learn a policy
that has performance competitive with the expert, using as few annotations as
possible. We focus on the general agnostic setting where the expert
demonstration policy may not be contained in the policy class used by the
learner. We propose a new oracle-efficient algorithm MFTPL-P (abbreviation for
Mixed Follow the Perturbed Leader with Poisson perturbations) with provable
finite-sample guarantees, under the assumption that the learner is given access
to samples from some ``explorative'' distribution over states. Our guarantees
hold for any policy class, which is considerably broader than prior state of
the art. We further propose Bootstrap-Dagger, a more practical variant that
does not require additional sample access. Empirically, MFTPL-P and
Bootstrap-Dagger notably surpass online and offline imitation learning
baselines in continuous control tasks.
