  We study Imitation Learning (IL) from Observations alone (ILFO) in
large-scale MDPs. While most IL algorithms rely on an expert to directly
provide actions to the learner, in this setting the expert only supplies
sequences of observations. We design a new model-free algorithm for ILFO,
Forward Adversarial Imitation Learning (FAIL), which learns a sequence of
time-dependent policies by minimizing an Integral Probability Metric between
the observation distributions of the expert policy and the learner. FAIL is the
first provably efficient algorithm in ILFO setting, which learns a near-optimal
policy with a number of samples that is polynomial in all relevant parameters
but independent of the number of unique observations. The resulting theory
extends the domain of provably sample efficient learning algorithms beyond
existing results, which typically only consider tabular reinforcement learning
settings or settings that require access to a near-optimal reset distribution.
We also investigate the extension of FAIL in a model-based setting. Finally we
demonstrate the efficacy of FAIL on multiple OpenAI Gym control tasks.
