Minimax Optimal Online Imitation Learning via Replay Estimation
Online imitation learning is the problem of how best to mimic expert
demonstrations, given access to the environment or an accurate simulator. Prior
work has shown that in the infinite sample regime, exact moment matching
achieves value equivalence to the expert policy. However, in the finite sample
regime, even if one has no optimization error, empirical variance can lead to a
performance gap that scales with $H^2 / N$ for behavioral cloning and $H /
\sqrt{N}$ for online moment matching, where $H$ is the horizon and $N$ is the
size of the expert dataset. We introduce the technique of replay estimation to
reduce this empirical variance: by repeatedly executing cached expert actions
in a stochastic simulator, we compute a smoother expert visitation distribution
estimate to match. In the presence of general function approximation, we prove
a meta theorem reducing the performance gap of our approach to the parameter
estimation error for offline classification (i.e. learning the expert policy).
In the tabular setting or with linear function approximation, our meta theorem
shows that the performance gap incurred by our approach achieves the optimal
$\widetilde{O} \left( \min({H^{3/2}} / {N}, {H} / {\sqrt{N}} \right)$
dependency, under significantly weaker assumptions compared to prior work. We
implement multiple instantiations of our approach on several continuous control
tasks and find that we are able to significantly improve policy performance
across a variety of dataset sizes.