Randomized algorithms and PAC bounds for inverse reinforcement learning in continuous spaces
This work addresses the challenge of inferring cost functions from expert behavior in continuous domains, offering theoretical guarantees for practical applications, though it is incremental in extending existing methods to continuous settings.
The paper tackles the inverse reinforcement learning problem in continuous spaces by characterizing solution sets and using randomized algorithms to derive epsilon-optimal solutions, providing sample complexity bounds for approximation accuracy.
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.