On the Correctness and Sample Complexity of Inverse Reinforcement Learning
On the map: Offline RL and imitation learning from data → Inverse reinforcement learning
Abstract (arXiv)
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(n2 log (nk)) for recovering a reward function that generates a policy that satisfies Bellman's optimality condition with respect to the true transition probabilities.
Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Placed in Inverse reinforcement learning, one of 13 directions in Offline RL and imitation learning from data. Builds on 1 of its 14 references that are in the map. First posted on arXiv 2 Jun 2019.
Builds on
1 of 14 references.
References · 1
Built on by
Citing papers per year: 2019: 1; 2020: 0; 2021: 3; 2022: 0; 2023: 1; 2024: 3.
8 papers.
- 2023Towards Theoretical Understanding of Inverse Reinforcement Learningcited by 21
- 2021Efficient Performance Bounds for Primal-Dual Reinforcement Learning from Demonstrationscited by 9
- 2021Inverse Reinforcement Learning in a Continuous State Space with Formal Guaranteescited by 8
- 2021A Lower Bound for the Sample Complexity of Inverse Reinforcement Learningcited by 7
- 2024How does Inverse RL Scale to Large State Spaces? A Provably Efficient Approachcited by 5
- 2019On Value Discrepancy of Imitation Learningcited by 4
- 2024Towards Sample-Efficiency and Generalization of Transfer and Inverse Reinforcement Learning: A Comprehensive Literature Reviewcited by 3
- 2024Randomized algorithms and PAC bounds for inverse reinforcement learning in continuous spacescited by 0
- 2024Towards Sample-Efficiency and Generalization of Transfer and Inverse Reinforcement Learning: A Comprehensive Literature Review15 Nov 2024
- 2024How does Inverse RL Scale to Large State Spaces? A Provably Efficient Approach6 Jun 2024
- 2024Randomized algorithms and PAC bounds for inverse reinforcement learning in continuous spaces24 May 2024
- 2023Towards Theoretical Understanding of Inverse Reinforcement Learning25 Apr 2023
- 2021Efficient Performance Bounds for Primal-Dual Reinforcement Learning from Demonstrations28 Dec 2021
- 2021A Lower Bound for the Sample Complexity of Inverse Reinforcement Learning7 Mar 2021
- 2021Inverse Reinforcement Learning in a Continuous State Space with Formal Guarantees16 Feb 2021
- 2019On Value Discrepancy of Imitation Learning16 Nov 2019
Similar, not cited
Close in wording, no citation either way
- 2025Inverse Reinforcement Learning via Convex Optimization
- 2023A Novel Variational Lower Bound for Inverse Reinforcement Learning
- 2024Convergence of a model-free entropy-regularized inverse reinforcement learning algorithm
- 2018A Survey of Inverse Reinforcement Learning: Challenges, Methods and Progress
- 2023Inverse Reinforcement Learning with the Average Reward Criterion
- 2023Is Inverse Reinforcement Learning Harder than Standard Reinforcement Learning? A Theoretical Perspective
- 2021A Generalised Inverse Reinforcement Learning Framework
- 2020Regularized Inverse Reinforcement Learning