A Lower Bound for the 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 task of finding a reward function that generates a desired optimal policy for a given Markov Decision Process (MDP). This paper develops an information-theoretic lower bound for the sample complexity of the finite state, finite action IRL problem. A geometric construction of β-strict separable IRL problems using spherical codes is considered. Properties of the ensemble size as well as the Kullback-Leibler divergence between the generated trajectories are derived. The resulting ensemble is then used along with Fano's inequality to derive a sample complexity lower bound of O(n log n), where n is the number of states in the MDP.
Key facts. Cited by 7 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 2 of its 21 references that are in the map. First posted on arXiv 7 Mar 2021.
Builds on
2 of 21 references.
Closest ancestors · 1
Same direction, newest first
Other references · 1
Built on by
Citing papers per year: 2023: 2; 2024: 4; 2025: 1.
7 papers.
- 2023Towards Theoretical Understanding of Inverse Reinforcement Learningcited by 21
- 2024Offline Inverse RL: New Solution Concepts and Provably Efficient Algorithmscited by 9
- 2024How does Inverse RL Scale to Large State Spaces? A Provably Efficient Approachcited by 5
- 2024Towards Sample-Efficiency and Generalization of Transfer and Inverse Reinforcement Learning: A Comprehensive Literature Reviewcited by 3
- 2025PAC Apprenticeship Learning with Bayesian Active Inverse Reinforcement Learningcited by 1
- 2023Fundamental Tradeoffs in Learning with Prior Informationcited by 0
- 2024Randomized algorithms and PAC bounds for inverse reinforcement learning in continuous spacescited by 0
- 2025PAC Apprenticeship Learning with Bayesian Active Inverse Reinforcement Learning5 Aug 2025
- 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
- 2024Offline Inverse RL: New Solution Concepts and Provably Efficient Algorithms23 Feb 2024
- 2023Fundamental Tradeoffs in Learning with Prior Information26 Apr 2023
- 2023Towards Theoretical Understanding of Inverse Reinforcement Learning25 Apr 2023
Similar, not cited
Close in wording, no citation either way
- 2026Fast Rates for Inverse Reinforcement Learning
- 2023A Novel Variational Lower Bound for Inverse Reinforcement Learning
- 2025Inverse Reinforcement Learning via Convex Optimization
- 2023Inverse Reinforcement Learning With Constraint Recovery
- 2021A Generalised Inverse Reinforcement Learning Framework
- 2023Identifiability and Generalizability in Constrained Inverse Reinforcement Learning
- 2021Task-Guided Inverse Reinforcement Learning Under Partial Information
- 2021Identifiability in inverse reinforcement learning