arXiv:2512.00553cs.LGcs.AI2025-12被引 1

提出可复现强化学习新框架,让算法多次运行结果落在小列表中。

List Replicable Reinforcement Learning

  • 设计基于字典序选择的规划策略,控制输出策略数量
  • 理论证明列表复杂度为多项式级别,避免指数增长
  • 适合关注算法稳定性的研究者和工业落地应用

可复现性是强化学习中的根本挑战,因算法对训练条件敏感且表现不稳定。本文在可能近似正确(PAC)RL框架下研究“列表可复现性”,要求算法在不同运行中返回一个近优策略,该策略必须属于一个小的策略列表,且高概率成立。列表大小定义为“列表复杂度”。我们提出弱与强两种形式的可复现性:弱形式仅保证最终策略在小列表中,强形式进一步要求整个执行策略序列也受控。现有算法常导致指数级列表复杂度。本文主要贡献是一个可证明高效的表格型强化学习算法,确保列表复杂度在状态数、动作数和时域长度上为多项式。我们还扩展方法实现强可复现性,以高概率将可能的策略执行轨迹数控制在多项式范围内。关键创新包括:(i) 基于随机容差阈值内近优动作的字典序选择规划策略;(ii) 在随机环境中测试状态可达性的同时保持可复现性。理论分析揭示了实际算法不稳定的根源,并实证表明所提策略可融入现有框架显著提升稳定性。

原文摘要 · Abstract (English)

Replicability is a fundamental challenge in reinforcement learning (RL), as RL algorithms are empirically observed to be unstable and sensitive to variations in training conditions. To formally address this issue, we study \emph{list replicability} in the Probably Approximately Correct (PAC) RL framework, where an algorithm must return a near-optimal policy that lies in a \emph{small list} of policies across different runs, with high probability. The size of this list defines the \emph{list complexity}. We introduce both weak and strong forms of list replicability: the weak form ensures that the final learned policy belongs to a small list, while the strong form further requires that the entire sequence of executed policies remains constrained. These objectives are challenging, as existing RL algorithms exhibit exponential list complexity due to their instability. Our main theoretical contribution is a provably efficient tabular RL algorithm that guarantees list replicability by ensuring the list complexity remains polynomial in the number of states, actions, and the horizon length. We further extend our techniques to achieve strong list replicability, bounding the number of possible policy execution traces polynomially with high probability. Our theoretical result is made possible by key innovations including (i) a novel planning strategy that selects actions based on lexicographic order among near-optimal choices within a randomly chosen tolerance threshold, and (ii) a mechanism for testing state reachability in stochastic environments while preserving replicability. Finally, we demonstrate that our theoretical investigation sheds light on resolving the \emph{instability} issue of RL algorithms used in practice. In particular, we show that empirically, our new planning strategy can be incorporated into practical RL frameworks to enhance their stability.

强化学习可复现性稳定性

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