# Minimax Optimal Online Imitation Learning via Replay Estimation

arXiv: https://arxiv.org/abs/2205.15397 · HTML: https://mlsanity.com/paper/2205.15397/

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- Placed in Imitation learning methods, one of 13 directions in Offline RL and imitation learning from data.
- Builds on 14 of its 36 references that are in the map.
- First posted on arXiv 30 May 2022.

## Placed in

- Offline RL and imitation learning from data / [Imitation learning methods](https://mlsanity.com/offlinerl/imitation-learning-methods/)

## Builds on (most cited first, 14 of 14)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Improved Training of Wasserstein GANs](https://mlsanity.com/paper/1704.00028/) (2017)
- [Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1606.03476/) (2016)
- [Exploration by Random Network Distillation](https://mlsanity.com/paper/1810.12894/) (2018)
- [MOReL : Model-Based Offline Reinforcement Learning](https://mlsanity.com/paper/2005.05951/) (2020)
- [Self-Supervised Exploration via Disagreement](https://mlsanity.com/paper/1906.04161/) (2019)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Toward the Fundamental Limits of Imitation Learning](https://mlsanity.com/paper/2009.05990/) (2020)
- [Of Moments and Matching: A Game-Theoretic Framework for Closing the Imitation Gap](https://mlsanity.com/paper/2103.03236/) (2021)
- [Optimal Learners for Multiclass Problems](https://mlsanity.com/paper/1405.2420/) (2014)
- [Random Expert Distillation: Imitation Learning via Expert Policy Support Estimation](https://mlsanity.com/paper/1905.06750/) (2019)
- [Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally](https://mlsanity.com/paper/2102.12948/) (2021)

## Built on by (most cited first, 25 of 25)

- [Zero-Shot Whole-Body Humanoid Control via Behavioral Foundation Models](https://mlsanity.com/paper/2504.11054/) (2025)
- [Inverse Reinforcement Learning without Reinforcement Learning](https://mlsanity.com/paper/2303.14623/) (2023)
- [Hybrid Inverse Reinforcement Learning](https://mlsanity.com/paper/2402.08848/) (2024)
- [A Smooth Sea Never Made a Skilled SAILOR: Robust Imitation via Learning to Search](https://mlsanity.com/paper/2506.05294/) (2025)
- [Provably Efficient Adversarial Imitation Learning with Unknown Transitions](https://mlsanity.com/paper/2306.06563/) (2023)
- [Learning Shared Safety Constraints from Multi-task Demonstrations](https://mlsanity.com/paper/2309.00711/) (2023)
- [Imitation Learning in Discounted Linear MDPs without exploration assumptions](https://mlsanity.com/paper/2405.02181/) (2024)
- [PivotRL: High Accuracy Agentic Post-Training at Low Compute Cost](https://mlsanity.com/paper/2603.21383/) (2026)
- [Multi-Agent Imitation Learning: Value is Easy, Regret is Hard](https://mlsanity.com/paper/2406.04219/) (2024)
- [Conformalized Interactive Imitation Learning: Handling Expert Shift and Intermittent Feedback](https://mlsanity.com/paper/2410.08852/) (2024)
- [Non-Adversarial Inverse Reinforcement Learning via Successor Feature Matching](https://mlsanity.com/paper/2411.07007/) (2024)
- [EvIL: Evolution Strategies for Generalisable Imitation Learning](https://mlsanity.com/paper/2406.11905/) (2024)
- [Provably and Practically Efficient Adversarial Imitation Learning with General Function Approximation](https://mlsanity.com/paper/2411.00610/) (2024)
- [How does Inverse RL Scale to Large State Spaces? A Provably Efficient Approach](https://mlsanity.com/paper/2406.03812/) (2024)
- [IL-SOAR : Imitation Learning with Soft Optimistic Actor cRitic](https://mlsanity.com/paper/2502.19859/) (2025)
- [Efficient Imitation under Misspecification](https://mlsanity.com/paper/2503.13162/) (2025)
- [Inverse Q-Learning Done Right: Offline Imitation Learning in Qπ-Realizable MDPs](https://mlsanity.com/paper/2505.19946/) (2025)
- [Learning Equilibria from Data: Provably Efficient Multi-Agent Imitation Learning](https://mlsanity.com/paper/2505.17610/) (2025)
- [C-GAIL: Stabilizing Generative Adversarial Imitation Learning with Control Theory](https://mlsanity.com/paper/2402.16349/) (2024)
- [When Does Online Imitation Learning Help in LLM Post-Training? The Role of (Non-)Realizability Beyond Horizon](https://mlsanity.com/paper/2606.30445/) (2026)
- [Interactive and Hybrid Imitation Learning: Provably Beating Behavior Cloning](https://mlsanity.com/paper/2412.07057/) (2024)
- [Agnostic Interactive Imitation Learning: New Theory and Practical Algorithms](https://mlsanity.com/paper/2312.16860/) (2023)
- [Adversarial Imitation Learning with General Function Approximation: Theoretical Analysis and Practical Algorithms](https://mlsanity.com/paper/2605.01778/) (2026)
- [The Virtues of Pessimism in Inverse Reinforcement Learning](https://mlsanity.com/paper/2402.02616/) (2024)
- [Dynamic Action Interpolation: A Universal Approach for Accelerating Reinforcement Learning with Expert Guidance](https://mlsanity.com/paper/2504.18766/) (2025)

## Abstract (arXiv)

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 H2 / N for behavioral cloning and H / √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 widetildeO left( min(H3/2 / N, H / √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.