@inproceedings{
kamoutsi2024randomized,
title={Randomized algorithms and {PAC} bounds for inverse reinforcement learning in continuous spaces},
author={Angeliki Kamoutsi and Peter Schmitt-F{\"o}rster and Tobias Sutter and Volkan Cevher and John Lygeros},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=VUgXAWOCQz}
}
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 $\varepsilon$-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.
Randomized algorithms and PAC bounds for inverse reinforcement learning in continuous spaces
Angeliki Kamoutsi Peter Schmitt-Förster Tobias Sutter Volkan Cevher John Lygeros