Towards Theoretical Understanding of Inverse Reinforcement Learning
This work addresses a foundational theoretical limitation in IRL, which is crucial for AI and robotics applications, though it is incremental as it builds on existing formulations.
The paper tackles the theoretical gap in inverse reinforcement learning (IRL) for finite-horizon problems by focusing on estimating the feasible reward set, providing the first minimax lower bound on sample complexity of order Ω(H³SA/ε²(log(1/δ) + S)) and showing a matching upper bound up to logarithmic factors for a uniform sampling strategy.
Inverse reinforcement learning (IRL) denotes a powerful family of algorithms for recovering a reward function justifying the behavior demonstrated by an expert agent. A well-known limitation of IRL is the ambiguity in the choice of the reward function, due to the existence of multiple rewards that explain the observed behavior. This limitation has been recently circumvented by formulating IRL as the problem of estimating the feasible reward set, i.e., the region of the rewards compatible with the expert's behavior. In this paper, we make a step towards closing the theory gap of IRL in the case of finite-horizon problems with a generative model. We start by formally introducing the problem of estimating the feasible reward set, the corresponding PAC requirement, and discussing the properties of particular classes of rewards. Then, we provide the first minimax lower bound on the sample complexity for the problem of estimating the feasible reward set of order $Ω\Bigl( \frac{H^3SA}{ε^2} \bigl( \log \bigl(\frac{1}δ\bigl) + S \bigl)\Bigl)$, being $S$ and $A$ the number of states and actions respectively, $H$ the horizon, $ε$ the desired accuracy, and $δ$ the confidence. We analyze the sample complexity of a uniform sampling strategy (US-IRL), proving a matching upper bound up to logarithmic factors. Finally, we outline several open questions in IRL and propose future research directions.