Provable Representation Learning for Imitation with Contrastive Fourier Features

Ofir Nachum, Mengjiao Yang

Summary

This paper introduces a novel approach to utilizing large, "unlabeled" offline datasets to learn robust state representations for imitation learning (IL). By employing a contrastive learning objective based on Fourier features, the authors provide theoretical guarantees that their method remains effective even when the expert's behavior is highly complex. In practice, this approach significantly outperforms standard behavioral cloning across 60 Atari games.

The Challenge: Sample Efficiency and State Aliasing

Imitation learning is the process of teaching an agent to act by observing an expert. The most common approach, Behavioral Cloning (BC), treats this as a supervised learning problem, mapping states directly to the expert's actions. However, BC suffers from a major bottleneck: it requires a massive number of expert demonstrations, scaling poorly as environment complexity increases.

While expert data is rare and expensive, "offline" data—random logs of an agent exploring an environment—is often plentiful. The primary challenge is leveraging this lower-quality offline data to learn a representation (a simplified map of the world) that makes the expert's policy easier to learn.

Illustration of state aliasing in MDPs.

The specific danger in representation learning is aliasing. If a representation simplifies the world too aggressively, it might map two distinct states—where the expert would take completely different actions—to the identical "latent" state. This confuses the downstream learner, forcing it to average out the conflicting actions and ultimately fail the task.

Methodology: Contrastive Fourier Features

To circumvent the aliasing problem, the authors propose a representation learning objective that is provably robust.

  1. Dynamics over Latents: Instead of merely compressing the state space or forcing the latent space to mimic the environment (as in bisimulation), the representation ($\phi$) is trained to predict the actual environment's rewards and transition dynamics. Anchoring the representation to real-world physics prevents harmful aliasing.
  2. Contrastive Learning: This predictive objective is implemented using a contrastive loss. The model learns to distinguish a true next-state $s'$ from a random "noise" state, given the current state and action.
  3. Random Fourier Features (RFF): To make the mathematics tractable for linear policies, the authors utilize Random Fourier Features. This technique approximates complex, non-linear kernels using linear transformations. By projecting the state into this Fourier space, non-linear environment dynamics can be treated as linear, enabling the derivation of strong performance bounds.
  4. Theoretical Guarantees: The authors prove that as long as the representation captures the environment's dynamics accurately, the performance gap between the learner and the expert is strictly bounded—even if the expert's policy is highly non-linear.

Experimental Results

The researchers evaluated their approach on synthetic tabular domains (Tree Environments) designed with low-rank transitions to verify the theory, as well as on 60 Atari 2600 games using the DQN Replay Dataset (representing 50 million transitions of unlabeled offline data per game).

Performance comparison showing high sample efficiency of Fourier features over Vanilla BC.
  • Sample Efficiency: In the controlled tree environments, the learned representations allowed the agent to reach near-expert performance with a fraction of the demonstrations required by vanilla BC.
  • Atari Dominance: The Contrastive Fourier Features method achieved a normalized improvement of over 40% compared to vanilla BC on more than half of the 60 Atari games tested.
  • Beating Bisimulation: The proposed method significantly outperformed popular latent space models like DeepMDP and Deep Bisimulation for Control (DBC). While those methods often struggled or performed worse than basic BC, the contrastive approach consistently leveraged offline data to improve sample efficiency.

Limitations and Future Directions

While powerful, the method has a few limitations. The theoretical bounds rely on the "Pearson $\chi^2$ divergence" between the offline data and the expert's data. If the offline data suffers from severe distribution shift (e.g., the offline agent only explores a useless corner of the map), the learned representation won't aid the expert's specific path.

Additionally, the current work focuses on single-step transitions. Extending this framework to multi-step "temporal" contrastive learning could yield even richer representations. Finally, while the method can function without rewards, it performs optimally when reward information is present in the offline dataset, which is not always guaranteed in pure imitation settings.

Summary updated

Abstract

In imitation learning, it is common to learn a behavior policy to match an unknown target policy via max-likelihood training on a collected set of target demonstrations. In this work, we consider using offline experience datasets -- potentially far from the target distribution -- to learn low-dimensional state representations that provably accelerate the sample-efficiency of downstream imitation learning. A central challenge in this setting is that the unknown target policy itself may not exhibit low-dimensional behavior, and so there is a potential for the representation learning objective to alias states in which the target policy acts differently. Circumventing this challenge, we derive a representation learning objective that provides an upper bound on the performance difference between the target policy and a low-dimensional policy trained with max-likelihood, and this bound is tight regardless of whether the target policy itself exhibits low-dimensional structure. Moving to the practicality of our method, we show that our objective can be implemented as contrastive learning, in which the transition dynamics are approximated by either an implicit energy-based model or, in some special cases, an implicit linear model with representations given by random Fourier features. Experiments on both tabular environments and high-dimensional Atari games provide quantitative evidence for the practical benefits of our proposed objective.
BibTeX
@inproceedings{nachum2021provable,
  author = {Ofir Nachum and Mengjiao Yang},
  title = {{Provable Representation Learning for Imitation with Contrastive Fourier Features}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=50fccglxEDo},
}
Figure