On the Correctness and Sample Complexity of Inverse Reinforcement Learning
This work addresses the theoretical correctness and efficiency of IRL for finite-state Markov Decision Processes, providing a rigorous sample complexity bound, though it is incremental as it builds on existing IRL frameworks.
The paper tackles the problem of inverse reinforcement learning (IRL) by proposing an L1-regularized SVM formulation based on a geometric analysis, and shows a sample complexity of O(n^2 log(nk)) for recovering a reward function that generates a policy satisfying Bellman's optimality condition.
Inverse reinforcement learning (IRL) is the problem of finding a reward function that generates a given optimal policy for a given Markov Decision Process. This paper looks at an algorithmic-independent geometric analysis of the IRL problem with finite states and actions. A L1-regularized Support Vector Machine formulation of the IRL problem motivated by the geometric analysis is then proposed with the basic objective of the inverse reinforcement problem in mind: to find a reward function that generates a specified optimal policy. The paper further analyzes the proposed formulation of inverse reinforcement learning with $n$ states and $k$ actions, and shows a sample complexity of $O(n^2 \log (nk))$ for recovering a reward function that generates a policy that satisfies Bellman's optimality condition with respect to the true transition probabilities.