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 interacting with the MDP for $N$ episodes. To our knowledge, this is the first algorithm with suboptimality having no dependence on the number of actions, under no additional assumptions. We then propose a novel algorithm based on minimum-distance functionals in the setting where the transition model is given and the expert is deterministic. The algorithm is suboptimal by $\lesssim \min \{H\sqrt{|\mathcal{S}|/N},|\mathcal{S}|H^{3/2}/N\}$, showing that knowledge of transition improves the minimax rate by at least a $\sqrt{H}$ factor.

arXiv comment45 pages, 3 figures

References in corpus (7)

• Deep Q-learning from Demonstrations
• Learning human behaviors from motion capture by adversarial imitation
• Reinforcement and Imitation Learning for Diverse Visuomotor Skills
• Deeply AggreVaTeD: Differentiable Imitation Learning for Sequential Prediction
• Imitation Learning as $f$-Divergence Minimization
• Learning Self-Correctable Policies and Value Functions from Demonstrations with Negative Sampling
• Provable Representation Learning for Imitation Learning via Bi-level Optimization

Cited by in corpus (5)

• Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coverage
• Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage
• CTRLStruct: Dialogue Structure Learning for Open-Domain Response Generation
• Provably Efficient Generative Adversarial Imitation Learning for Online and Offline Setting with Linear Function Approximation
• The Sample Complexity of Teaching-by-Reinforcement on Q-Learning