# Randomized algorithms and PAC bounds for inverse reinforcement learning in continuous spaces

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL for robot locomotion and manipulation, one of 15 directions in Deep reinforcement learning methods.
- Builds on 25 of its 75 references that are in the map.
- First posted on arXiv 24 May 2024.

## Placed in

- Deep reinforcement learning methods / [RL for robot locomotion and manipulation](https://mlsanity.com/deeprl/rl-for-robot-locomotion-and-manipulation/)

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

- [Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1606.03476/) (2016)
- [An Algorithmic Perspective on Imitation Learning](https://mlsanity.com/paper/1811.06711/) (2018)
- [Guided Cost Learning: Deep Inverse Optimal Control via Policy Optimization](https://mlsanity.com/paper/1603.00448/) (2016)
- [IQ-Learn: Inverse soft-Q Learning for Imitation](https://mlsanity.com/paper/2106.12142/) (2021)
- [Imitation Learning via Off-Policy Distribution Matching](https://mlsanity.com/paper/1912.05032/) (2019)
- [Imitation Learning as f-Divergence Minimization](https://mlsanity.com/paper/1905.12888/) (2019)
- [Reward (Mis)design for Autonomous Driving](https://mlsanity.com/paper/2104.13906/) (2021)
- [Reinforcement Learning in Economics and Finance](https://mlsanity.com/paper/2003.10014/) (2020)
- [Identifiability in inverse reinforcement learning](https://mlsanity.com/paper/2106.03498/) (2021)
- [Model-Free Imitation Learning with Policy Optimization](https://mlsanity.com/paper/1605.08478/) (2016)
- [Active Exploration for Inverse Reinforcement Learning](https://mlsanity.com/paper/2207.08645/) (2022)
- [Proximal Point Imitation Learning](https://mlsanity.com/paper/2209.10968/) (2022)
- [Adversarial Soft Advantage Fitting: Imitation Learning without Policy Optimization](https://mlsanity.com/paper/2006.13258/) (2020)
- [Towards Theoretical Understanding of Inverse Reinforcement Learning](https://mlsanity.com/paper/2304.12966/) (2023)
- [Identifiability and generalizability from multiple experts in Inverse Reinforcement Learning](https://mlsanity.com/paper/2209.10974/) (2022)
- [Performance Bounds for the Scenario Approach and an Extension to a Class of Non-convex Programs](https://mlsanity.com/paper/1307.0345/) (2013)
- [Offline Inverse RL: New Solution Concepts and Provably Efficient Algorithms](https://mlsanity.com/paper/2402.15392/) (2024)
- [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)
- [Maximum Hands-Off Control: A Paradigm of Control Effort Minimization](https://mlsanity.com/paper/1408.3025/) (2014)
- [From Infinite to Finite Programs: Explicit Error Bounds with Applications to Approximate Dynamic Programming](https://mlsanity.com/paper/1701.06379/) (2017)
- [On the Sample Size of Random Convex Programs with Structured Dependence on the Uncertainty (Extended Version)](https://mlsanity.com/paper/1502.00803/) (2015)
- [Linear conic optimization for inverse optimal control](https://mlsanity.com/paper/1412.2277/) (2014)
- [Characterization of maximum hands-off control](https://mlsanity.com/paper/1602.08834/) (2016)

## Abstract (arXiv)

This work studies discrete-time discounted Markov decision processes with continuous state and action spaces and addresses the inverse problem of inferring a cost function from observed optimal behavior. We first consider the case in which we have access to the entire expert policy and characterize the set of solutions to the inverse problem by using occupation measures, linear duality, and complementary slackness conditions. To avoid trivial solutions and ill-posedness, we introduce a natural linear normalization constraint. This results in an infinite-dimensional linear feasibility problem, prompting a thorough analysis of its properties. Next, we use linear function approximators and adopt a randomized approach, namely the scenario approach and related probabilistic feasibility guarantees, to derive epsilon-optimal solutions for the inverse problem. We further discuss the sample complexity for a desired approximation accuracy. Finally, we deal with the more realistic case where we only have access to a finite set of expert demonstrations and a generative model and provide bounds on the error made when working with samples.