  Imitation learning (IL) is a general learning paradigm for tackling
sequential decision-making problems. Interactive imitation learning, where
learners can interactively query for expert demonstrations, has been shown to
achieve provably superior sample efficiency guarantees compared with its
offline counterpart or reinforcement learning. In this work, we study
classification-based online imitation learning (abbrev. $\textbf{COIL}$) and
the fundamental feasibility to design oracle-efficient regret-minimization
algorithms in this setting, with a focus on the general nonrealizable case. We
make the following contributions: (1) we show that in the $\textbf{COIL}$
problem, any proper online learning algorithm cannot guarantee a sublinear
regret in general; (2) we propose $\textbf{Logger}$, an improper online
learning algorithmic framework, that reduces $\textbf{COIL}$ to online linear
optimization, by utilizing a new definition of mixed policy class; (3) we
design two oracle-efficient algorithms within the $\textbf{Logger}$ framework
that enjoy different sample and interaction round complexity tradeoffs, and
conduct finite-sample analyses to show their improvements over naive behavior
cloning; (4) we show that under the standard complexity-theoretic assumptions,
efficient dynamic regret minimization is infeasible in the $\textbf{Logger}$
framework. Our work puts classification-based online imitation learning, an
important IL setup, into a firmer foundation.
