Provably Breaking the Quadratic Error Compounding Barrier in Imitation
  Learning, Optimally
  We study the statistical limits of Imitation Learning (IL) in episodic Markov
Decision Processes (MDPs) with a state space $\mathcal{S}$. We focus on the
known-transition setting where the learner is provided a dataset of $N$
length-$H$ trajectories from a deterministic expert policy and knows the MDP
transition. We establish an upper bound $O(|\mathcal{S}|H^{3/2}/N)$ for the
suboptimality using the Mimic-MD algorithm in Rajaraman et al (2020) which we
prove to be computationally efficient. In contrast, we show the minimax
suboptimality grows as $\Omega( H^{3/2}/N)$ when $|\mathcal{S}|\geq 3$ while
the unknown-transition setting suffers from a larger sharp rate
$\Theta(|\mathcal{S}|H^2/N)$ (Rajaraman et al (2020)). The lower bound is
established by proving a two-way reduction between IL and the value estimation
problem of the unknown expert policy under any given reward function, as well
as building connections with linear functional estimation with subsampled
observations. We further show that under the additional assumption that the
expert is optimal for the true reward function, there exists an efficient
algorithm, which we term as Mimic-Mixture, that provably achieves suboptimality
$O(1/N)$ for arbitrary 3-state MDPs with rewards only at the terminal layer. In
contrast, no algorithm can achieve suboptimality $O(\sqrt{H}/N)$ with high
probability if the expert is not constrained to be optimal. Our work formally
establishes the benefit of the expert optimal assumption in the known
transition setting, while Rajaraman et al (2020) showed it does not help when
transitions are unknown.
