Minimax Optimal Online Imitation Learning Via Replay Estimation

Abstract

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

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyswamy2022minimax

Related papers

• Toward The Fundamental Limits Of Imitation Learning (2020)0.00
• Explaining Fast Improvement In Online Imitation Learning (2020)0.00
• Matching Multiple Experts: On The Exploitability Of Multi-agent Imitation Learning (2026)0.00
• Online Adaptation For Enhancing Imitation Learning Policies (2024)0.00
• Of Moments And Matching: A Game-theoretic Framework For Closing The Imitation Gap (2021)0.00
• Offline Imitation Learning By Controlling The Effective Planning Horizon (2024)0.00
• Accelerating Imitation Learning With Predictive Models (2018)0.00
• Fully General Online Imitation Learning (2021)0.00