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

arXiv: https://arxiv.org/abs/2406.03812 · HTML: https://mlsanity.com/paper/2406.03812/

## 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.

## Placed in

- Offline RL and imitation learning from data / [Inverse reinforcement learning](https://mlsanity.com/offlinerl/inverse-reinforcement-learning/)

## Builds on (most cited first, 30 of 40)

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1606.03476/) (2016)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Learning Robust Rewards with Adversarial Inverse Reinforcement Learning](https://mlsanity.com/paper/1710.11248/) (2017)
- [Guided Cost Learning: Deep Inverse Optimal Control via Policy Optimization](https://mlsanity.com/paper/1603.00448/) (2016)
- [Cooperative Inverse Reinforcement Learning](https://mlsanity.com/paper/1606.03137/) (2016)
- [A Survey of Inverse Reinforcement Learning: Challenges, Methods and Progress](https://mlsanity.com/paper/1806.06877/) (2018)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Inverse Reward Design](https://mlsanity.com/paper/1711.02827/) (2017)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [Imitation from Observation: Learning to Imitate Behaviors from Raw Video via Context Translation](https://mlsanity.com/paper/1707.03374/) (2017)
- [Reward-rational (implicit) choice: A unifying formalism for reward learning](https://mlsanity.com/paper/2002.04833/) (2020)
- [Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited](https://mlsanity.com/paper/2010.03531/) (2020)
- [Toward the Fundamental Limits of Imitation Learning](https://mlsanity.com/paper/2009.05990/) (2020)
- [Fast active learning for pure exploration in reinforcement learning](https://mlsanity.com/paper/2007.13442/) (2020)
- [On Reward-Free Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2006.11274/) (2020)
- [Provably Efficient Imitation Learning from Observation Alone](https://mlsanity.com/paper/1905.10948/) (2019)
- [Adaptive Reward-Free Exploration](https://mlsanity.com/paper/2006.06294/) (2020)
- [Identifiability in inverse reinforcement learning](https://mlsanity.com/paper/2106.03498/) (2021)
- [On the Feasibility of Learning, Rather than Assuming, Human Biases for Reward Inference](https://mlsanity.com/paper/1906.09624/) (2019)
- [Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes](https://mlsanity.com/paper/2201.11206/) (2022)
- [Invariance in Policy Optimisation and Partial Identifiability in Reward Learning](https://mlsanity.com/paper/2203.07475/) (2022)
- [Settling the Reward Hypothesis](https://mlsanity.com/paper/2212.10420/) (2022)
- [Online Apprenticeship Learning](https://mlsanity.com/paper/2102.06924/) (2021)
- [Active Exploration for Inverse Reinforcement Learning](https://mlsanity.com/paper/2207.08645/) (2022)
- [Misspecification in Inverse Reinforcement Learning](https://mlsanity.com/paper/2212.03201/) (2022)
- [Minimax Optimal Online Imitation Learning via Replay Estimation](https://mlsanity.com/paper/2205.15397/) (2022)

## Built on by (most cited first, 5 of 5)

- [Self-Distillation Enables Continual Learning](https://mlsanity.com/paper/2601.19897/) (2026)
- [Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learning](https://mlsanity.com/paper/2502.13900/) (2025)
- [On Feasible Rewards in Multi-Agent Inverse Reinforcement Learning](https://mlsanity.com/paper/2411.15046/) (2024)
- [Provably Efficient Exploration in Inverse Constrained Reinforcement Learning](https://mlsanity.com/paper/2409.15963/) (2024)
- [Robustness in the Face of Partial Identifiability in Reward Learning](https://mlsanity.com/paper/2501.06376/) (2025)

## 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.