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 optimaldemonstrations 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 an equivalence to the set coverproblem, and use this equivalence to develop an efficient algorithm fordetermining the set of maximally-informative demonstrations. We apply ourproposed machine teaching algorithm to two novel applications: benchmarkingactive learning IRL algorithms and developing an IRL algorithm that, ratherthan assuming demonstrations are i.i.d., uses counterfactual reasoning overinformative demonstrations to learn more efficiently.