# Towards Theoretical Understanding of Inverse Reinforcement Learning

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

## Key facts

- Cited by 21 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 16 of its 44 references that are in the map.
- First posted on arXiv 25 Apr 2023.

## Placed in

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

## Builds on (most cited first, 16 of 16)

- [An Algorithmic Perspective on Imitation Learning](https://mlsanity.com/paper/1811.06711/) (2018)
- [A Survey of Inverse Reinforcement Learning: Challenges, Methods and Progress](https://mlsanity.com/paper/1806.06877/) (2018)
- [A Survey of Human-in-the-loop for Machine Learning](https://mlsanity.com/paper/2108.00941/) (2021)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning](https://mlsanity.com/paper/1510.08906/) (2015)
- [Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited](https://mlsanity.com/paper/2010.03531/) (2020)
- [Fast active learning for pure exploration in reinforcement learning](https://mlsanity.com/paper/2007.13442/) (2020)
- [Adaptive Reward-Free Exploration](https://mlsanity.com/paper/2006.06294/) (2020)
- [Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guarantees](https://mlsanity.com/paper/2210.01808/) (2022)
- [Planning in Markov Decision Processes with Gap-Dependent Sample Complexity](https://mlsanity.com/paper/2006.05879/) (2020)
- [Efficient Sampling-Based Maximum Entropy Inverse Reinforcement Learning with Application to Autonomous Driving](https://mlsanity.com/paper/2006.13704/) (2020)
- [Active Exploration for Inverse Reinforcement Learning](https://mlsanity.com/paper/2207.08645/) (2022)
- [Learning to Drive using Inverse Reinforcement Learning and Deep Q-Networks](https://mlsanity.com/paper/1612.03653/) (2016)
- [On the Correctness and Sample Complexity of Inverse Reinforcement Learning](https://mlsanity.com/paper/1906.00422/) (2019)
- [Inverse Reinforcement Learning in a Continuous State Space with Formal Guarantees](https://mlsanity.com/paper/2102.07937/) (2021)
- [A Lower Bound for the Sample Complexity of Inverse Reinforcement Learning](https://mlsanity.com/paper/2103.04446/) (2021)

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

- [PROGRESSOR: A Perceptually Guided Reward Estimator with Self-Supervised Online Refinement](https://mlsanity.com/paper/2411.17764/) (2024)
- [A Comprehensive Survey on Inverse Constrained Reinforcement Learning: Definitions, Progress and Challenges](https://mlsanity.com/paper/2409.07569/) (2024)
- [Offline Inverse RL: New Solution Concepts and Provably Efficient Algorithms](https://mlsanity.com/paper/2402.15392/) (2024)
- [Inverse Reinforcement Learning with the Average Reward Criterion](https://mlsanity.com/paper/2305.14608/) (2023)
- [How does Inverse RL Scale to Large State Spaces? A Provably Efficient Approach](https://mlsanity.com/paper/2406.03812/) (2024)
- [Is Inverse Reinforcement Learning Harder than Standard Reinforcement Learning? A Theoretical Perspective](https://mlsanity.com/paper/2312.00054/) (2023)
- [A Unified Linear Programming Framework for Offline Reward Learning from Human Demonstrations and Feedback](https://mlsanity.com/paper/2405.12421/) (2024)
- [On Feasible Rewards in Multi-Agent Inverse Reinforcement Learning](https://mlsanity.com/paper/2411.15046/) (2024)
- [Inverse Concave-Utility Reinforcement Learning is Inverse Game Theory](https://mlsanity.com/paper/2405.19024/) (2024)
- [Provably Efficient Exploration in Inverse Constrained Reinforcement Learning](https://mlsanity.com/paper/2409.15963/) (2024)
- [Apprenticeship learning with prior beliefs using inverse optimization](https://mlsanity.com/paper/2505.21639/) (2025)
- [PAC Apprenticeship Learning with Bayesian Active Inverse Reinforcement Learning](https://mlsanity.com/paper/2508.03693/) (2025)
- [Efficient Reward Identification In Max Entropy Reinforcement Learning with Sparsity and Rank Priors](https://mlsanity.com/paper/2508.07400/) (2025)
- [Generalizing Behavior via Inverse Reinforcement Learning with Closed-Form Reward Centroids](https://mlsanity.com/paper/2509.12010/) (2025)
- [Randomized algorithms and PAC bounds for inverse reinforcement learning in continuous spaces](https://mlsanity.com/paper/2405.15509/) (2024)
- [Robustness in the Face of Partial Identifiability in Reward Learning](https://mlsanity.com/paper/2501.06376/) (2025)
- [Statistical analysis of Inverse Entropy-regularized Reinforcement Learning](https://mlsanity.com/paper/2512.06956/) (2025)
- [Learning Incentive Structures for Cooperative Resilience in Multi-Agent Systems under Social Dilemmas](https://mlsanity.com/paper/2601.22292/) (2026)
- [Learning the Preferences of a Learning Agent](https://mlsanity.com/paper/2605.09217/) (2026)
- [Inverse Reinforcement Learning without an Optimal Demonstrator: A Feasible Reward Set Approach](https://mlsanity.com/paper/2605.30903/) (2026)
- [Path-dependent Discrete Amortized Inference](https://mlsanity.com/paper/2608.08644/) (2026)

## Abstract (arXiv)

Inverse reinforcement learning (IRL) denotes a powerful family of algorithms for recovering a reward function justifying the behavior demonstrated by an expert agent. A well-known limitation of IRL is the ambiguity in the choice of the reward function, due to the existence of multiple rewards that explain the observed behavior. This limitation has been recently circumvented by formulating IRL as the problem of estimating the feasible reward set, i.e., the region of the rewards compatible with the expert's behavior. In this paper, we make a step towards closing the theory gap of IRL in the case of finite-horizon problems with a generative model. We start by formally introducing the problem of estimating the feasible reward set, the corresponding PAC requirement, and discussing the properties of particular classes of rewards. Then, we provide the first minimax lower bound on the sample complexity for the problem of estimating the feasible reward set of order OmegaBigl( fracH3SAε2 bigl( log bigl(frac1δbigl) + S bigl)Bigl), being S and A the number of states and actions respectively, H the horizon, ε the desired accuracy, and δ the confidence. We analyze the sample complexity of a uniform sampling strategy (US-IRL), proving a matching upper bound up to logarithmic factors. Finally, we outline several open questions in IRL and propose future research directions.