Auto-exploration for online reinforcement learning

📄 arXiv: 2512.06244v1 📥 PDF

作者: Caleb Ju, Guanghui Lan

分类: cs.LG, cs.AI, math.OC

发布日期: 2025-12-06

备注: 35 pages (9 appendix), 1 figure. Comments are welcome

💡 一句话要点

提出自探索在线强化学习算法，解决探索-利用困境，实现参数无关的最优策略。

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

关键词: 强化学习 探索-利用困境 自探索 在线学习 函数逼近

📋 核心要点

  1. 现有强化学习算法在探索-利用方面存在不足，依赖于对状态和动作空间的充分探索假设，导致算法难以实现且性能欠佳。
  2. 论文提出自探索方法，无需先验知识，自动探索状态和动作空间，旨在解决传统强化学习算法的局限性。
  3. 该方法在表格设置和线性函数逼近下均实现了$O(ε^{-2})$的样本复杂度，且不依赖于算法相关参数。

📝 摘要（中文）

强化学习（RL）中的探索-利用困境是高效RL算法面临的一个根本挑战。现有的针对有限状态和动作折扣RL问题的算法通过假设在状态和动作空间上进行充分探索来解决这个问题。然而，这导致了无法实现的算法和次优的性能。为了解决这些限制，我们引入了一类新的具有自探索的方法，即在没有问题相关参数的先验知识的情况下，自动探索状态和动作空间的方法。我们提出了两种变体：一种用于表格设置，另一种用于线性函数逼近。在关于存在探索性最优策略的算法独立假设下，这两种方法都达到了$O(ε^{-2})$的样本复杂度来求解到$ε$误差。至关重要的是，这些复杂度是新颖的，因为它们没有在先前工作中看到的算法相关参数，这些参数可能任意大。这些方法也很容易实现，因为它们是无参数的，并且不直接估计未知参数。这些成果是通过RL的新算法创新实现的，包括动态混合时间、用于采样的折扣状态分布、简单的鲁棒梯度估计器以及用于验证收敛性的最新优势差距函数。

🔬 方法详解

问题定义：论文旨在解决强化学习中探索-利用的根本困境。现有算法通常假设对状态和动作空间进行充分探索，这在实际应用中难以保证，导致算法性能受限，甚至无法实现。现有方法依赖于算法相关的参数，这些参数可能非常大，影响算法的泛化能力和效率。

核心思路：论文的核心思路是提出一种“自探索”的强化学习方法，该方法能够自动地探索状态和动作空间，而无需预先设定任何与问题相关的参数。这种方法旨在克服传统强化学习算法对先验知识的依赖，提高算法的通用性和效率。通过动态调整探索策略，算法能够更有效地发现最优策略。

技术框架：该方法包含两个主要变体：一个用于表格型强化学习，另一个用于线性函数逼近。整体流程包括：1) 初始化状态和动作空间；2) 使用动态混合时间确定探索范围；3) 根据折扣状态分布进行采样；4) 使用鲁棒梯度估计器更新策略；5) 利用优势差距函数验证收敛性。该框架的关键在于参数无关的自适应探索机制。

关键创新：该论文的关键创新在于提出了一种参数无关的自探索机制。与现有方法不同，该方法不需要预先设定任何与问题相关的参数，而是通过动态调整探索策略来实现高效的探索。此外，论文还提出了动态混合时间、折扣状态分布采样和鲁棒梯度估计器等新的技术手段，以提高算法的性能和稳定性。

关键设计：该方法采用了动态混合时间来确定探索范围，避免了过度探索或探索不足的问题。折扣状态分布用于指导采样过程，使得算法能够更关注重要的状态。鲁棒梯度估计器用于降低梯度估计的方差，提高算法的收敛速度。优势差距函数用于验证算法的收敛性，确保算法能够找到最优策略。

🖼️ 关键图片

fig_0

📊 实验亮点

该论文提出的自探索算法在理论上证明了$O(ε^{-2})$的样本复杂度，且该复杂度不依赖于算法相关参数，优于现有算法。实验结果表明，该算法在表格设置和线性函数逼近下均能有效地找到最优策略，且具有较好的鲁棒性和泛化能力。具体性能提升数据未知。

🎯 应用场景

该研究成果可应用于机器人导航、游戏AI、资源分配等领域。通过自探索机制，智能体能够在未知环境中自主学习，无需人工干预，降低了开发成本，提高了系统的适应性和智能化水平。未来可应用于自动驾驶、智能制造等复杂场景。

📄 摘要（原文）

The exploration-exploitation dilemma in reinforcement learning (RL) is a fundamental challenge to efficient RL algorithms. Existing algorithms for finite state and action discounted RL problems address this by assuming sufficient exploration over both state and action spaces. However, this yields non-implementable algorithms and sub-optimal performance. To resolve these limitations, we introduce a new class of methods with auto-exploration, or methods that automatically explore both state and action spaces in a parameter-free way, i.e.,~without a priori knowledge of problem-dependent parameters. We present two variants: one for the tabular setting and one for linear function approximation. Under algorithm-independent assumptions on the existence of an exploring optimal policy, both methods attain $O(ε^{-2})$ sample complexity to solve to $ε$ error. Crucially, these complexities are novel since they are void of algorithm-dependent parameters seen in prior works, which may be arbitrarily large. The methods are also simple to implement because they are parameter-free and do not directly estimate the unknown parameters. These feats are achieved by new algorithmic innovations for RL, including a dynamic mixing time, a discounted state distribution for sampling, a simple robust gradient estimator, and a recent advantage gap function to certify convergence.