  Inverse Reinforcement Learning (IRL) -- the problem of learning reward
functions from demonstrations of an \emph{expert policy} -- plays a critical
role in developing intelligent systems, such as those that understand and
imitate human behavior. While widely used in applications, theoretical
understandings of IRL admit unique challenges and remain less developed
compared with standard RL theory. For example, it remains open how to do IRL
efficiently in standard \emph{offline} settings with pre-collected data, where
states are obtained from a \emph{behavior policy} (which could be the expert
policy itself), and actions are sampled from the expert policy.
  This paper provides the first line of results for efficient IRL in vanilla
offline and online settings using polynomial samples and runtime. We first
design a new IRL algorithm for the offline setting, Reward Learning with
Pessimism (RLP), and show that it achieves polynomial sample complexity in
terms of the size of the MDP, a concentrability coefficient between the
behavior policy and the expert policy, and the desired accuracy. Building on
RLP, we further design an algorithm Reward Learning with Exploration (RLE),
which operates in a natural online setting where the learner can both actively
explore the environment and query the expert policy, and obtain a stronger
notion of IRL guarantee from polynomial samples. We establish sample complexity
lower bounds for both settings showing that RLP and RLE are nearly optimal.
Finally, as an application, we show that the learned reward functions can
\emph{transfer} to another target MDP with suitable guarantees when the target
MDP satisfies certain similarity assumptions with the original (source) MDP.

Machine Learning;Artificial Intelligence;Machine Learning