Abstract
Inverse reinforcement learning (IRL) infers a reward function fromdemonstrations, allowing for policy improvement and generalization. However,despite much recent interest in IRL, little work has been done to understand ofthe minimum set of demonstrations needed to teach a specific sequentialdecision-making task. We formalize the problem of finding maximally informativedemonstrations for IRL as a machine teaching problem where the goal is to findthe minimum number of demonstrations needed to specify the reward equivalenceclass of the demonstrator. We extend previous work on algorithmic teaching forsequential decision-making tasks by showing a reduction to the set coverproblem which enables an efficient approximation algorithm for determining theset of maximally-informative demonstrations. We apply our proposed machineteaching algorithm to two novel applications: providing a lower bound on thenumber of queries needed to learn a policy using active IRL and developing anovel IRL algorithm that can learn more efficiently from informativedemonstrations than a standard IRL approach.