  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.
