Research map / Reinforcement learning / MDPs and planning
How does Inverse RL Scale to Large State Spaces? A Provably Efficient Approach
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows the feasible reward set in Linear MDPs cannot be learned with sample complexity independent of state-space size, introduces reward compatibility and the CATY algorithm for IRL classification, and derives minimax-optimal tabular bounds plus an improved RFE lower bound.
Problem
Online inverse reinforcement learning (IRL) via the feasible reward set is sample-inefficient and impractical in large or continuous state spaces, even under Linear MDP structure.
Approach
Replaces the hard feasible-set criterion with a soft reward (non)compatibility measure (J*(r) minus expert's J(r)), turning IRL into a per-reward classification task; the CATY algorithm estimates this gap using RFE exploration plus expert-occupancy estimation, with complexity independent of state-space cardinality.
Key results
- Shows the feasible set requires Omega(S) expert samples even under Linear MDPs with a generative model and deterministic expert.
- CATY achieves tabular IRL classification sample complexity Otilde(H^3 SA/eps^2 (S + log 1/delta)) episodes, matched by an Omega lower bound up to log factors.
- Improves the RFE tabular lower bound by a factor H to Omega(H^3 SA/eps^2 (S + log 1/delta)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use rewards compatibility and classify rewards with CATY instead of estimating the full feasible set | Online IRL in Linear MDPs · Linear MDPs with large or continuous state spaces | sample complexity dependence on state-space cardinality | Helped |
| Estimate the feasible reward set without knowing the expert policy | Feasible-set learning in Linear IRL · Finite state space with deterministic expert | expert trajectories required: \Omega(S) | Hurt |
| Assume the expert policy is known and use an RFE routine to estimate the feasible set | Feasible-set learning in Linear MDPs · Linear MDPs | exploration episodes: \widetilde{\mathcal{O}}\Big(\frac{H^5d}{\epsilon^2}\Big(d+\log\frac{1}{\delta}\Big) \Big) | Helped |
| Apply CATY to tabular MDPs with any nonempty reward set | CATY · Tabular MDPs; |R|≥1 | exploration episodes: \widetilde{\mathcal{O}}\Big(\frac{H^3SA}{\epsilon^2}\Big(N+\log\frac{1}{\delta}\Big)\Big) | Helped |
| Use CATY when classifying the full reward class | CATY · Tabular MDPs; R=𝔯 | exploration episodes: \widetilde{\mathcal{O}}\Big(\frac{H^3SA}{\epsilon^2}\Big(N+\log\frac{1}{\delta}\Big)\Big) | Helped |
| Strengthen the tabular RFE lower-bound construction | Reward-Free Exploration · Tabular MDPs | exploration episodes lower bound: \Omega\bigg(\frac{H^3SA}{\epsilon^2}\Big( S+\log\frac{1}{\delta} \Big) \bigg) | Helped |
Surprising findings
- The feasible set is statistically inefficient in Linear MDPs with large state spaces, requiring sample complexity that scales with state-space cardinality even with a generative model and deterministic expert.
Limitations
- Relies on the Linear MDP assumption, which is strong for real-world settings.
- No lower bound for Linear MDPs is provided.
- Empirical validation is out of scope.
Experimental setup
Metrics: sample complexity
Baselines: feasible set learning (US-IRL) BPI-UCBVI RF-Express
Builds on: Linear MDP RFLin BPI-UCBVI RF-Express
Closest papers by meaning
- Is Inverse Reinforcement Learning Harder than Standard Reinforcement Learning? A Theoretical Perspective (ICML 2024 · similarity 0.92)
- Offline Inverse RL: New Solution Concepts and Provably Efficient Algorithms (ICML 2024 · similarity 0.92)
- Recent Advancements in Inverse Reinforcement Learning (AAAI 2024 · similarity 0.92)
- A Geometric Perspective on Reward Function Updates in Inverse Reinforcement Learning (NeurIPS 2026 · similarity 0.90)
- Randomized algorithms and PAC bounds for inverse reinforcement learning in continuous spaces (NeurIPS 2024 · similarity 0.90)
- Hybrid Inverse Reinforcement Learning (ICML 2024 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.