Inverse reinforcement learning (IRL) denotes a powerful family of algorithms
for recovering a reward function justifying the behavior demonstrated by an
expert agent. A well-known limitation of IRL is the ambiguity in the choice of
the reward function, due to the existence of multiple rewards that explain the
observed behavior. This limitation has been recently circumvented by
formulating IRL as the problem of estimating the feasible reward set, i.e., the
region of the rewards compatible with the expert's behavior. In this paper, we
make a step towards closing the theory gap of IRL in the case of finite-horizon
problems with a generative model. We start by formally introducing the problem
of estimating the feasible reward set, the corresponding PAC requirement, and
discussing the properties of particular classes of rewards. Then, we provide
the first minimax lower bound on the sample complexity for the problem of
estimating the feasible reward set of order ${\Omega}\Bigl(
\frac{H^3SA}{\epsilon^2} \bigl( \log \bigl(\frac{1}{\delta}\bigl) + S
\bigl)\Bigl)$, being $S$ and $A$ the number of states and actions respectively,
$H$ the horizon, $\epsilon$ the desired accuracy, and $\delta$ the confidence.
We analyze the sample complexity of a uniform sampling strategy (US-IRL),
proving a matching upper bound up to logarithmic factors. Finally, we outline
several open questions in IRL and propose future research directions.

本文中，我们介绍了使用生成模型的有限时间问题中逆强化学习（IRL）的可行奖赏估计问题，提出了关于可行奖赏集合的最小最大下界，并分析了平均复杂度。