Toward The Fundamental Limits Of Imitation Learning

Abstract

Imitation learning (IL) aims to mimic the behavior of an expert policy in a sequential decision-making problem given only demonstrations. In this paper, we focus on understanding the minimax statistical limits of IL in episodic Markov Decision Processes (MDPs). We first consider the setting where the learner is provided a dataset of \(N\) expert trajectories ahead of time, and cannot interact with the MDP. Here, we show that the policy which mimics the expert whenever possible is in expectation \(\lesssim \frac\{|\mathcal\{S\}| H^2 log (N)\}\{N\}\) suboptimal compared to the value of the expert, even when the expert follows an arbitrary stochastic policy. Here \(\mathcal\{S\}\) is the state space, and \(H\) is the length of the episode. Furthermore, we establish a suboptimality lower bound of \(\gtrsim |\mathcal\{S\}| H^2 / N\) which applies even if the expert is constrained to be deterministic, or if the learner is allowed to actively query the expert at visited states while interacti

Stats

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

Related papers

• The Pitfalls Of Imitation Learning When Actions Are Continuous (2025)0.00
• State-only Imitation With Transition Dynamics Mismatch (2020)0.00
• Minimax Optimal Online Imitation Learning Via Replay Estimation (2022)0.00
• Matching Multiple Experts: On The Exploitability Of Multi-agent Imitation Learning (2026)0.00
• Provably Efficient Adversarial Imitation Learning With Unknown Transitions (2023)0.00
• Sequence Model Imitation Learning With Unobserved Contexts (2022)0.00
• A Bayesian Solution To The Imitation Gap (2024)0.00
• Beyond-expert Performance With Limited Demonstrations: Efficient Imitation Learning With Double Exploration (2025)0.00