How does Inverse RL Scale to Large State Spaces? A Provably Efficient Approach

📄 arXiv: 2406.03812v2 📥 PDF

作者: Filippo Lazzati, Mirco Mutti, Alberto Maria Metelli

分类: cs.LG

发布日期: 2024-06-06 (更新: 2024-10-08)

备注: Advances in Neural Information Processing Systems 38 (NeurIPS 2024)

💡 一句话要点

提出CATY-IRL算法，解决线性MDP中大规模状态空间下的逆强化学习问题

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 逆强化学习 线性MDP 奖励兼容性 在线学习 样本复杂度 无奖励探索 大规模状态空间

📋 核心要点

  1. 现有在线逆强化学习算法难以扩展到大规模状态空间的问题，限制了其应用。
  2. 论文提出奖励兼容性框架，并设计CATY-IRL算法，实现样本高效的逆强化学习。
  3. CATY-IRL算法在表格设置下达到极小极大最优，并改进了无奖励探索的下界。

📝 摘要（中文）

在在线逆强化学习(IRL)中，学习者可以通过收集环境动态的样本来改进对奖励函数的估计。由于IRL存在可辨识性问题，许多关于在线IRL的理论工作都集中在估计解释演示的整个奖励集合，即可行奖励集。然而，文献中没有算法可以扩展到具有大型状态空间的问题。本文关注线性马尔可夫决策过程(MDP)中的在线IRL问题。我们表明，当状态空间很大时，线性MDP提供的结构不足以有效地估计可行集。因此，我们引入了奖励兼容性的新框架，它推广了可行集的概念，并开发了CATY-IRL，这是一种样本高效的算法，其复杂度与线性MDP中状态空间的基数无关。当限制在表格设置中时，我们证明CATY-IRL在对数因子范围内是极小极大最优的。作为副产品，我们表明无奖励探索(RFE)享有相同的最坏情况速率，优于最先进的下界。最后，我们设计了一个统一的IRL和RFE框架，这可能具有独立的意义。

🔬 方法详解

问题定义：论文旨在解决在线逆强化学习中，当状态空间很大时，现有算法无法有效估计可行奖励集的问题。特别是在线性MDPs中，即使利用其结构，也难以高效地确定可行集。现有方法的痛点在于其复杂度与状态空间的大小相关，导致无法扩展到大规模问题。

核心思路：论文的核心思路是引入“奖励兼容性”的概念，它推广了可行奖励集。通过关注与专家策略“兼容”的奖励函数，而不是精确地估计整个可行集，从而降低了计算复杂度。CATY-IRL算法基于此框架，通过迭代地缩小兼容奖励函数的范围，最终找到一个能够解释专家行为的奖励函数。

技术框架：CATY-IRL算法的整体框架是一个在线学习过程。它主要包含以下几个阶段： 1. 样本收集：通过与环境交互，收集状态转移和奖励信息。 2. 奖励函数估计：基于收集到的样本，估计与专家策略兼容的奖励函数。 3. 策略优化：利用估计的奖励函数，优化策略。 4. 兼容性验证：验证当前估计的奖励函数是否与专家策略兼容，如果不兼容，则更新奖励函数的范围。 这个过程迭代进行，直到找到一个与专家策略兼容的奖励函数。

关键创新：论文最重要的技术创新在于提出了“奖励兼容性”的概念，并基于此设计了CATY-IRL算法。与现有方法相比，CATY-IRL的复杂度与状态空间的大小无关，从而能够扩展到大规模问题。此外，论文还提出了一个统一的IRL和RFE框架，为理解这两种学习范式之间的关系提供了新的视角。

关键设计：CATY-IRL算法的关键设计包括： 1. 奖励兼容性度量：定义了如何衡量一个奖励函数与专家策略的兼容性。 2. 奖励函数范围更新策略：设计了如何根据收集到的样本和兼容性验证结果，更新奖励函数范围的策略。 3. 样本复杂度分析：对算法的样本复杂度进行了理论分析，证明了其样本效率。

📊 实验亮点

论文证明了CATY-IRL算法在表格设置下是极小极大最优的，这意味着该算法在最坏情况下也能达到最优的性能。此外，论文还证明了无奖励探索(RFE)享有与CATY-IRL相同的最坏情况速率，优于现有的下界。这些结果表明CATY-IRL算法具有很强的理论保证和实际应用潜力。

🎯 应用场景

该研究成果可应用于机器人导航、自动驾驶、游戏AI等领域。例如，在机器人导航中，可以通过学习人类驾驶员的驾驶习惯，从而训练出更安全、更高效的自动驾驶系统。此外，该算法还可以用于设计更智能的游戏AI，使其能够模仿人类玩家的行为，从而提高游戏的趣味性和挑战性。

📄 摘要（原文）

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.