Provably Efficient Imitation Learning from Observation Alone

1. Introduction

• ILFO demonstrations contain only observations, with no expert actions or rewards and no reset access, so action-supervised IL methods cannot be applied directly.Inverse-model approaches can suffer covariate shift, while handcrafted trajectory costs may require task knowledge and differ from the unknown true cost.Source: §1 · p. 1
• Large-scale MDPs require guarantees near the expert under the unknown true cost, sample complexity independent of observation-space cardinality, and polynomially many efficient oracle calls.The paper motivates function approximation because tabular methods scale with the number of observations.Source: §1 · pp. 1–2
• FAIL decomposes ILFO into H independent two-player min-max games and learns time-dependent policies by matching learner and expert observation distributions with an IPM.Its sample complexity depends on policy- and discriminator-class complexity, not explicitly on the observation-space cardinality.Source: §1 · p. 2
• The paper studies FAIL in Lipschitz-continuous MDPs, interactive ILFO, and state abstraction, and reports efficacy on multiple continuous-control tasks.The extensions and experiments are identified as distinct settings and evaluations.Source: §1 · p. 2

2. Preliminaries

• The setup uses a finite-horizon process with time-dependent observation spaces, a discrete action set, transition model, and bounded terminal observation cost.The observation spaces are discrete but extremely large, making sample complexity polynomial in their cardinality unsuitable.Source: §2 · p. 2
• The learning goal is to choose a policy from the time-dependent policy classes to minimize expected cost.The policy class at each step maps observations to distributions over actions.Source: §2 · p. 2
• An IPM measures distance between distributions using a symmetric class of real-valued functions; the function class determines the particular distance.The supplied examples include total variation, Wasserstein distance, and maximum mean discrepancy.Source: §2 · p. 3

2.1. Assumptions

• The analysis assumes access to cost-sensitive and linear-programming oracles for optimization over policy and function classes.The passages describe solutions for linear objectives over bounded-norm RKHS functions and bounded-Lipschitz functions.Source: §2.1 · p. 3
• Realizability requires the expert policy and associated functions to lie in the specified classes, which are symmetric and finite for the analysis.The classes may be extremely large, with bounds scaling logarithmically in their size.Source: §2.1 · p. 3

3.1. Learning One Step Policy via a Min-Max Game

• The one-step game uses importance-weighted empirical IPM estimation and no-regret updates, with the policy player using Follow-the-Regularized Leader.The discriminator’s best response uses an LP oracle, while the policy update uses a regularized CS oracle.Source: §3.1 · p. 4
• Conditioned on earlier policies, Algorithm 1 approximately minimizes the next-step IPM relative to the best achievable policy in that step.The stated guarantee is up to an epsilon error, and the analysis uses a min-max theorem and uniform convergence.Source: §3.1 · p. 4

3.2. Forward Adversarial Imitation Learning

• FAIL learns each time-dependent policy by minimizing an IPM between the next-step learner and expert observation distributions, then chains H such problems forward.At each step, previously learned policies are fixed; the one-step game can be solved using no-regret online learning.Source: §3 · p. 3, §3.2 · p. 4

3.3. Analysis of Algorithm 2

• The paper measures discriminator capacity with inherent Bellman error, which can decrease as the function class grows.The unrestricted bounded-function class corresponds to total variation, but the paper warns that it prevents efficient learning.Source: §3.3 · p. 5
• An unrestricted bounded-function discriminator makes efficient learning impossible, while finite-capacity classes can regularize the matching problem.The paper notes that restricting the class may introduce inherent Bellman error.Source: §3.3 · p. 5
• With M = O(log(|X|)) samples in the constructed realizable setting, expert and learner datasets become disjoint with probability tending to one as |X| grows.The corresponding empirical total-variation distances become constants, so distinguishing the policies requires sample size scaling polynomially with |X|.Source: §3.3 · p. 5
• Theorem 3.3 analyzes FAIL’s sample complexity under Assumption 2.1 and bounds performance error using an average over learned and expert state distributions.The cited passages do not provide the complete theorem bound.Source: §3.3 · p. 5

4. The Gap Between ILFO and RL

• ILFO can solve the constructed MDP family with O(H) expert-observation trajectories, while RL requires exponentially many trajectories to find a near-optimal policy.For the same family, the RL lower bound holds for deterministic dynamics, horizon H, 2H − 1 states, and two actions.Source: §4 · p. 6

5.1. Lipschitz Continuous MDPs

• Lipschitz function classes permit empirical IPM evaluation by linear programming, with generalization governed by covering dimension.The class has bounded Lipschitz constant and bounded value; its Rademacher complexity scales as O(N^-1/cov(X)).Source: §5.1 · p. 6
• In Lipschitz continuous MDPs, FAIL achieves J(π) − J(π⋆) ≤ O(H^2ϵ) with probability at least 1 − δ, and its bound removes inherent Bellman error.The sample complexity depends on covering dimension, which may be much smaller than the real dimension; it still has an exponential dependency on covering dimension.Source: §5.1 · pp. 6–7

5.2. Interactive Imitation Learning from Observations

• Interactive FAIL avoids inherent Bellman error by querying an expert for one-step transitions, but assumes stronger expert access than the non-interactive setting.The learner asks the expert to act for one step from an observation and observes the resulting next observation.Source: §5.2 · p. 7

5.3. State Abstraction

• Under a bisimulation state abstraction, FAIL uses bounded piecewise-constant functions and obtains zero inherent Bellman error.The abstraction makes the optimal value constant within each abstract state; the empirical IPM can be computed by linear programming.Source: §5.3 · p. 7

• An inverse model P(a|x_h, x_h+1) depends on the action-generation policy, so learning expert actions from observation pairs requires expert actions unless dynamics are deterministic and bijective.The passage notes that without expert actions, relying on such an inverse model provides no general performance guarantees.Source: §6 · p. 7

Experimental setup

• The experiments cover Swimmer, Reacher, and FetchReach, with each action dimension discretized into five values and modeled independently.The baseline removes actions from GAIL's discriminator; FAIL uses an RBF-kernel MMD IPM and the reported results average ten random trials.Source: §7 · pp. 7–8

Results

• On dense tasks, GAIL outperforms FAIL on Swimmer in some configurations, while FAIL outperforms GAIL on dense Reacher across configurations.Figure 1 compares the methods on dense Reacher and Hopper under varying demonstrations or training samples.Source: §7 · p. 8, Figure 1 · p. 8
• FAIL significantly outperforms GAIL on Reacher Sparse and FetchReach.Figure 2 compares expert, FAIL, and GAIL without actions while varying expert demonstrations under fixed training samples.Source: §7 · p. 8, Figure 2 · p. 8

Limitations

• FAIL shows less improvement over GAIL on longer-horizon tasks, which the authors attribute to learning a sequence of time-dependent policies requiring more samples as the horizon grows.They contrast this with GAIL's single stationary policy, which they describe as less sensitive to horizon increases.Source: §7 · p. 8

8. Model-based FAIL

• The model-based setting assumes the model class contains the true model and each discriminator class contains the corresponding optimal value function.These are the stated realizability assumptions.Source: §8 · p. 9
• The procedure expands discriminator classes using a potential Bellman operator, then runs FAIL with the constructed policy and discriminator classes.The construction is designed to make the expanded classes realizable.Source: §8 · p. 9
• The first construction step needs no real-world samples; real-world samples are required only in the second step, which calls FAIL.Figure 3 presents these as two procedures.Source: §8 · p. 9
• With probability at least 1 − δ, model-based FAIL learns an ϵ-near-optimal policy using samples and expert samples polynomial in H, K, 1/ϵ, log(|P|), log(F), and log(1/δ).The guarantee assumes P ∈ P and V⋆_h ∈ F_h for every h.Source: §8 · p. 9
• Realizability suffices for polynomial sample complexity statistically, but naive Figure 3 computation costs Θ(FH), and model-free sufficiency remains unresolved.The authors identify polynomial sample and computation conditions for ILFO as future work.Source: §8 · p. 9

9. Conclusion and Future Work

• FAIL decomposes sequential learning into independent two-player min-max games solved using general no-regret online learning.The conclusion describes this as the algorithmic approach for ILFO.Source: §9 · p. 9
• The paper presents the first exponential sample-complexity gap between ILFO and RL and identifies discriminator regularization and reducing inherent Bellman Error as key observations.The conclusion says the discriminator class should be explicitly regularized to achieve sample efficiency.Source: §9 · p. 9
• Experimentally, FAIL works as well as GAIL on dense-reward problems and significantly outperforms GAIL on sparse-reward MDPs.The conclusion characterizes sparse-reward MDPs as common in practice.Source: §9 · p. 9
• The analysis provides the paper’s first strong theoretical guarantee for solving ILFO, while the conclusion claims FAIL achieves sample and computational efficiency.Source: §9 · p. 9

A. Proof of Theorem 3.1

• Theorem 3.1’s proof uses the algorithm’s best-response and FTRL structure, together with concentration bounds, to establish its guarantee.The proof applies Bernstein’s inequality and a union bound over policy and discriminator classes.Source: A. Proof of Theorem 3.1 · pp. 12, 14

B. Proof of Theorem 3.2

• In the constructed H = 2 MDP, the expert and two alternative policies generate disjoint state supports, so distinguishing them from samples requires Ω(poly(|X|)) samples.The construction uses two actions and splits the state space into two equal parts with disjoint transition supports.Source: B. Proof of Theorem 3.2 · p. 15
• Comparing empirical distributions with bounded discriminators yields constant total-variation distances among the expert and alternatives unless the sample size scales as Ω(poly(|X|)).The proof notes that the three datasets do not overlap asymptotically at smaller sample sizes.Source: B. Proof of Theorem 3.2 · p. 15

C. Proof of Theorem 3.3

• The proof of Theorem 3.3 uses the Performance Difference Lemma to connect distribution discrepancies across time steps to policy performance.The proof states that Algorithm 1 selects each time-dependent policy with probability at least 1 −δ, but the supplied passage omits the associated bound.Source: C. Proof of Theorem 3.3 · pp. 16–17

D. Proof of Proposition 4.1

• The binary-tree construction reduces best-arm identification to RL, so finding a near-optimal policy without further MDP information inherits the bandit lower bound.The tree has deterministic transitions, zero-cost internal nodes, and leaf costs encoding the arms; an IL algorithm can instead recover the expert’s action sequence using at most 2(H −1) trajectories.Source: D. Proof of Proposition 4.1 · p. 18

E. Reduction to LP

• The LP oracle constructs an L-Lipschitz function matching the LP optimum on the sampled points, establishing the claimed reduction to a finite LP.The LP has 2N variables and O(N^2) constraints.Source: E. Reduction to LP · pp. 18–19

F. Proof of Corollary 5.1

• For infinite Lipschitz function classes, the proof constructs an (α + 2Lϵ)-cover and extends Theorem 3.3 using concentration and a union bound.The cover combines a metric-space ϵ-cover with an α-cover of function values on those covering points.Source: F. Proof of Corollary 5.1 · p. 20

G. FAIL in Interactive Setting

• Interactive FAIL queries the expert at learner-visited states and uses at most HK log(H|Π||F|/δ)/ϵ^2 trajectories overall.At each time step it compares next-observation distributions after learner and expert actions, conditioned on the learner’s current-state distribution.Source: G. FAIL in Interactive Setting · pp. 20–21

H. Relaxation of Assumption 2.1

• Under Assumption H.1, Corollary H.2 states that for ϵ ∈ (0, 1), δ ∈ (0, 1), T = Θ(K/ϵ²), and n = Θ(K log(|Π||F|H/δ)/ϵ²), non-interactive FAIL outputs a policy with probability at least 1 − δ.Source: H. Relaxation of Assumption 2.1 · p. 22
• IFAIL achieves J(π) − J(π⋆) ≤ O(Hϵ + HϵF + HϵΠ) using at most Õ((HK/ϵ²) log(|Π||F|/δ)) trajectories under both settings.Source: H. Relaxation of Assumption 2.1 · p. 22

H.1. Proof of Corollary H.2

• The Corollary H.2 proof uses the Performance Difference Lemma in both settings and reuses steps from the proofs of Theorems 3.3 and 5.2.Source: §H.1 · pp. 22–23

I. Missing Details on ILFO with State Abstraction

• The discriminator class’s Rademacher complexity is bounded in terms of the abstraction size |S| and sample count N.The passage describes the bound as being of order O(|S|/N).Source: §I · p. 23
• State abstraction yields piecewise-constant discriminators with zero inherent Bellman error and bounded statistical complexity.The discriminator functions are constant over the partitions induced by φ.Source: §I · p. 23
• The Bellman operator maps each bounded piecewise-constant discriminator back into the same function class.For f in Fh+1, Γhf is piecewise constant over the abstraction partitions and remains bounded by 1.Source: §I · p. 24

J. Additional Experiments

• Uniform action sampling with importance weighting bounds estimator variance by K; in practice, any reference policy can generate actions.The importance weights are adjusted to the action probabilities used for sampling.Source: J. Additional Experiments · p. 25
• If every action has a lower-bounded selection probability, the estimator variance is bounded, and the formulation extends to continuous action spaces.For on-policy samples, the policy gradient can be estimated using REINFORCE.Source: J. Additional Experiments · p. 25
• The min-max optimization alternates between an LP-oracle discriminator maximization and a policy-gradient descent update.The passage describes integrating this optimization into the forward training framework.Source: J. Additional Experiments · p. 25
• Algorithm 5 incrementally updates earlier policies using their on-policy samples while training the current policy.This reuses samples that Algorithm 2 discards.Source: J. Additional Experiments · p. 25
• At 0.25 million training samples, FAIL* can be more sample efficient, especially in small-data settings.Figure 4 compares expert, FAIL*, FAIL, and GAIL without actions across three control tasks; results average 10 random seeds.Source: J. Additional Experiments · p. 26, Figure 4 · p. 26