In online Inverse Reinforcement Learning (IRL), the learner can collect samples about the dynamics of the environment to improve its estimate of the reward function. Since IRL suffers from identifiability issues, many theoretical works on online IRL focus on estimating the entire set of rewards that explain the demonstrations, named the feasible reward set. However, none of the algorithms available in the literature can scale to problems with large state spaces. In this paper, we focus on the online IRL problem in Linear Markov Decision Processes (MDPs). We show that the structure offered by Linear MDPs is not sufficient for efficiently estimating the feasible set when the state space is large. As a consequence, we introduce the novel framework of rewards compatibility, which generalizes the notion of feasible set, and we develop CATY-IRL, a sample efficient algorithm whose complexity is independent of the cardinality of the state space in Linear MDPs. When restricted to the tabular setting, we demonstrate that CATY-IRL is minimax optimal up to logarithmic factors. As a by-product, we show that Reward-Free Exploration (RFE) enjoys the same worst-case rate, improving over the state-of-the-art lower bound. Finally, we devise a unifying framework for IRL and RFE that may be of independent interest.

在线逆向强化学习中，为了改善对奖励函数的估计，学习器可以收集关于环境动态的样本。本文针对在线逆向强化学习问题在线性马尔可夫决策过程中的情况进行研究，介绍了奖励兼容性的新框架，并开发了一种样本高效的算法CATY-IRL，其复杂度与状态空间的基数无关。在表格式环境中，CATY-IRL表现为最优的最小最大率，并改进了最先进的下界。最后，我们提出了一个统一的逆向强化学习和无奖励探索框架，可能具有独立的研究价值。

如何扩展逆强化学习至大规模状态空间？一种经过验证的高效方法