Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learning

📄 arXiv: 2502.13900v2 📥 PDF

作者: Antoine Moulin, Gergely Neu, Luca Viano

分类: cs.LG

发布日期: 2025-02-19 (更新: 2025-06-18)

💡 一句话要点

提出高效算法解决无限期强化学习与模仿学习问题

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

关键词: 强化学习 模仿学习 马尔可夫决策过程 乐观探索 动态规划 算法效率 对抗性奖励

📋 核心要点

  1. 核心问题：现有的强化学习算法在无限期折扣线性MDP中效率低下，难以实现最优的后悔保证。
  2. 方法要点：论文提出结合加性探索奖励与人工转移的乐观探索技术，提升算法的效率与效果。
  3. 实验或效果：所提算法在对抗性奖励序列中表现优异，达到了最先进的模仿学习结果。

📝 摘要（中文）

本文研究了在无限期折扣线性马尔可夫决策过程中的强化学习问题，提出了一种首个计算上高效的算法，能够在该环境中实现最优的后悔保证。我们结合了两种经典的乐观探索技术：对奖励函数的加性探索奖励和向最大回报的吸收状态的人工转移。结合正则化的近似动态规划方案，所提出的算法在样本转移总数为T的情况下，后悔值为$ ilde{ ext{O}} ( ext{sqrt}(d^3 (1 - ext{γ})^{- 7 / 2} T))$。该结果在对抗性奖励序列下依然成立，使得我们的方法能够应用于线性MDP中的模仿学习问题，并取得了最先进的结果。

🔬 方法详解

问题定义：本文旨在解决在无限期折扣线性马尔可夫决策过程中的强化学习问题。现有方法在处理此类问题时，往往面临效率低下和后悔保证不足的挑战。

核心思路：论文的核心思路是结合两种经典的乐观探索技术：对奖励函数的加性探索奖励和向最大回报的吸收状态的人工转移。这种设计旨在通过增强探索来提高学习效率。

技术框架：整体架构包括两个主要模块：首先是加性探索奖励的计算，其次是通过人工转移构建的吸收状态。结合正则化的近似动态规划方案，形成完整的学习流程。

关键创新：最重要的技术创新点在于首次将这两种乐观探索技术有效结合，形成了一个计算上高效的算法，能够在无限期折扣线性MDP中实现最优的后悔保证。

关键设计：算法中关键的参数设置包括折扣因子γ和特征维度d，损失函数设计为结合探索奖励与实际奖励的加权和，以确保在学习过程中平衡探索与利用。算法的复杂度分析显示其在样本转移数量T的依赖性。

🖼️ 关键图片

img_0

📊 实验亮点

实验结果表明，所提算法在对抗性奖励序列下的后悔值达到了$ ilde{ ext{O}} ( ext{sqrt}(d^3 (1 - ext{γ})^{- 7 / 2} T))$，在模仿学习任务中超越了现有的最先进方法，展示了显著的性能提升。

🎯 应用场景

该研究的潜在应用领域包括机器人控制、自动驾驶、游戏智能体等需要长期决策的场景。通过实现高效的强化学习与模仿学习，能够显著提升智能体在复杂环境中的表现，具有重要的实际价值和未来影响。

📄 摘要（原文）

We study the problem of reinforcement learning in infinite-horizon discounted linear Markov decision processes (MDPs), and propose the first computationally efficient algorithm achieving rate-optimal regret guarantees in this setting. Our main idea is to combine two classic techniques for optimistic exploration: additive exploration bonuses applied to the reward function, and artificial transitions made to an absorbing state with maximal return. We show that, combined with a regularized approximate dynamic-programming scheme, the resulting algorithm achieves a regret of order $\tilde{\mathcal{O}} (\sqrt{d^3 (1 - γ)^{- 7 / 2} T})$, where $T$ is the total number of sample transitions, $γ\in (0,1)$ is the discount factor, and $d$ is the feature dimensionality. The results continue to hold against adversarial reward sequences, enabling application of our method to the problem of imitation learning in linear MDPs, where we achieve state-of-the-art results.