mlsanityData to 14 Oct 2026

How does Inverse RL Scale to Large State Spaces? A Provably Efficient Approach

arXiv 2406.03812 ↗First posted 6 Jun 2024cs.LGcited by 5

On the map: Offline RL and imitation learning from data → Inverse reinforcement learning

also in 1 more
Abstract (arXiv)

In online Inverse Reinforcement Learning (IRL), the learner can collect samples about the dynamics of the environment to improve its estimate of the reward function. Since IRL suffers from identifiability issues, many theoretical works on online IRL focus on estimating the entire set of rewards that explain the demonstrations, named the feasible reward set. However, none of the algorithms available in the literature can scale to problems with large state spaces. In this paper, we focus on the online IRL problem in Linear Markov Decision Processes (MDPs). We show that the structure offered by Linear MDPs is not sufficient for efficiently estimating the feasible set when the state space is large. As a consequence, we introduce the novel framework of rewards compatibility, which generalizes the notion of feasible set, and we develop CATY-IRL, a sample efficient algorithm whose complexity is independent of the cardinality of the state space in Linear MDPs. When restricted to the tabular setting, we demonstrate that CATY-IRL is minimax optimal up to logarithmic factors. As a by-product, we show that Reward-Free Exploration (RFE) enjoys the same worst-case rate, improving over the state-of-the-art lower bound. Finally, we devise a unifying framework for IRL and RFE that may be of independent interest.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Placed in Inverse reinforcement learning, one of 13 directions in Offline RL and imitation learning from data. Builds on 40 of its 67 references that are in the map. First posted on arXiv 6 Jun 2024.

Builds on

40 of 67 references.

Closest ancestors · 10

Same direction, newest first

  1. 2024Offline Inverse RL: New Solution Concepts and Provably Efficient Algorithms23 Feb
  2. 2023Is Inverse Reinforcement Learning Harder than Standard Reinforcement Learning? A Theoretical Perspective29 Nov
  3. 2023Towards Theoretical Understanding of Inverse Reinforcement Learning25 Apr
  4. 2022Misspecification in Inverse Reinforcement Learning6 Dec
  5. 2022Active Exploration for Inverse Reinforcement Learning18 Jul
  6. 2021Identifiability in inverse reinforcement learning7 Jun
  7. 2021A Lower Bound for the Sample Complexity of Inverse Reinforcement Learning7 Mar
  8. 2021Inverse Reinforcement Learning in a Continuous State Space with Formal Guarantees16 Feb
  9. 2019On the Correctness and Sample Complexity of Inverse Reinforcement Learning2 Jun
  10. 2018A Survey of Inverse Reinforcement Learning: Challenges, Methods and Progress18 Jun

Other references · 30

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
  2. 2016Generative Adversarial Imitation Learningcited by 1,597
  3. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  4. 2017Learning Robust Rewards with Adversarial Inverse Reinforcement Learningcited by 490
  5. 2016Guided Cost Learning: Deep Inverse Optimal Control via Policy Optimizationcited by 406
  6. 2016Cooperative Inverse Reinforcement Learningcited by 300
  7. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  8. 2017Inverse Reward Designcited by 249
  9. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  10. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  11. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
  12. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
18 more
  1. 2017Imitation from Observation: Learning to Imitate Behaviors from Raw Video via Context Translationcited by 167
  2. 2020Reward-rational (implicit) choice: A unifying formalism for reward learningcited by 120
  3. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 106
  4. 2020Toward the Fundamental Limits of Imitation Learningcited by 96
  5. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  6. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
  7. 2019Provably Efficient Imitation Learning from Observation Alonecited by 78
  8. 2020Adaptive Reward-Free Explorationcited by 77
  9. 2019On the Feasibility of Learning, Rather than Assuming, Human Biases for Reward Inferencecited by 49
  10. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  11. 2022Invariance in Policy Optimisation and Partial Identifiability in Reward Learningcited by 46
  12. 2022Settling the Reward Hypothesiscited by 33
  13. 2021Online Apprenticeship Learningcited by 29
  14. 2022Minimax Optimal Online Imitation Learning via Replay Estimationcited by 25
  15. 2016Towards Resolving Unidentifiability in Inverse Reinforcement Learningcited by 18
  16. 2023Provably Efficient Adversarial Imitation Learning with Unknown Transitionscited by 16
  17. 2024Imitation Learning in Discounted Linear MDPs without exploration assumptionscited by 15
  18. 2022Utility Theory for Sequential Decision Makingcited by 8

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 2; 2025: 2; 2026: 1.

5 papers.

  1. 2026Self-Distillation Enables Continual Learningcited by 247
  2. 2025Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learningcited by 12
  3. 2024On Feasible Rewards in Multi-Agent Inverse Reinforcement Learningcited by 4
  4. 2024Provably Efficient Exploration in Inverse Constrained Reinforcement Learningcited by 1
  5. 2025Robustness in the Face of Partial Identifiability in Reward Learningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Inverse Reinforcement Learning without an Optimal Demonstrator: A Feasible Reward Set Approach
  2. 2025Reward Compatibility: A Framework for Inverse RL
  3. 2020Efficient Exploration of Reward Functions in Inverse Reinforcement Learning via Bayesian Optimization
  4. 2022Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guarantees
  5. 2026Fast Rates for Inverse Reinforcement Learning
  6. 2025Inverse Reinforcement Learning via Convex Optimization
  7. 2026A Lecture Note on Offline RL and IRL, Part II: Foundations of Inverse Reinforcement Learning and Dynamic Discrete Choice Models
  8. 2022Structural Estimation of Markov Decision Processes in High-Dimensional State Space with Finite-Time Guarantees