arXiv:2505.03710stat.MLcs.AI2025-05ICML被引 4

提出新算法实现最优采样效率,解决长期未解难题。

Actor-Critics Can Achieve Optimal Sample Efficiency

  • 结合乐观探索与离线数据,设计高效更新机制
  • 理论证明采样复杂度达 $O(1/ε^2)$ 轨迹,优于现有方法
  • 适合关注采样效率的强化学习研究者与应用开发者

Actor-critic 算法在强化学习中广泛应用,但以往工作未能在需策略性探索的通用函数近似下,以 $O(1/ε^2)$ 轨迹数学习 $ε$-最优策略。本文提出新型算法,实现 $O(dH^5 \log|\mathcal{A}|/ε^2 + dH^4 \log|\mathcal{F}|/ε^2)$ 轨迹的样本复杂度,并伴随 $\ ext{\sqrt{T}}$ 逆悔差。其中 $d$ 为贝尔曼可辨识维度,$H$ 为有限时域马尔可夫决策过程的时域,$\mathcal{F}$ 为评价函数类,$\mathcal{A}$ 为动作空间。算法融合乐观性、离线估计与稀疏策略重置。扩展至混合强化学习,利用离线数据初始化可提升采样效率。进一步给出无需乐观性的可证明高效算法,仅需 $N_{\text{off}} \geq c_{\text{off}}^* dH^4/ε^2$ 的离线样本即可,解决了文献中的另一开放问题。数值实验验证理论结果。

原文摘要 · Abstract (English)

Actor-critic algorithms have become a cornerstone in reinforcement learning (RL), leveraging the strengths of both policy-based and value-based methods. Despite recent progress in understanding their statistical efficiency, no existing work has successfully learned an $ε$-optimal policy with a sample complexity of $O(1/ε^2)$ trajectories with general function approximation when strategic exploration is necessary. We address this open problem by introducing a novel actor-critic algorithm that attains a sample-complexity of $O(dH^5 \log|\mathcal{A}|/ε^2 + d H^4 \log|\mathcal{F}|/ ε^2)$ trajectories, and accompanying $\sqrt{T}$ regret when the Bellman eluder dimension $d$ does not increase with $T$ at more than a $\log T$ rate. Here, $\mathcal{F}$ is the critic function class, $\mathcal{A}$ is the action space, and $H$ is the horizon in the finite horizon MDP setting. Our algorithm integrates optimism, off-policy critic estimation targeting the optimal Q-function, and rare-switching policy resets. We extend this to the setting of Hybrid RL, showing that initializing the critic with offline data yields sample efficiency gains compared to purely offline or online RL. Further, utilizing access to offline data, we provide a \textit{non-optimistic} provably efficient actor-critic algorithm that only additionally requires $N_{\text{off}} \geq c_{\text{off}}^*dH^4/ε^2$ in exchange for omitting optimism, where $c_{\text{off}}^*$ is the single-policy concentrability coefficient and $N_{\text{off}}$ is the number of offline samples. This addresses another open problem in the literature. We further provide numerical experiments to support our theoretical findings.

强化学习采样效率算法优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。