arXiv:2506.20904cs.LGcs.IT2025-06NeurIPS被引 2

首次给出平均奖励强化学习的单策略样本复杂度下界,突破以往理论限制。

Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL

  • 基于目标策略的偏差跨度与新提出击中半径,构建单策略分析框架
  • 在弱连通马尔可夫决策过程上实现最优样本效率,无需先验参数
  • 提出带分位数截断的悲观折扣值迭代算法,提升学习稳定性

本文研究平均奖励马尔可夫决策过程中的离线强化学习,该问题因分布偏移和非均匀覆盖带来更大挑战,且理论研究相对不足。现有工作虽在单策略数据覆盖假设下提供性能保证,但依赖对所有策略统一的复杂度度量(如一致混合时间)。本文首次建立仅依赖目标策略的精确保证,引入偏差跨度与新颖的策略击中半径,实现平均奖励离线强化学习的首个完整单策略样本复杂度界。同时,首次处理一般弱连通MDP,摆脱以往严格的结构假设。为此提出基于悲观折扣值迭代并结合新分位数截断技术的算法,支持更紧致的经验跨度惩罚函数,且无需任何先验参数。通过硬例证明,在此条件下学习需超越目标策略平稳分布的覆盖要求,揭示单策略复杂度度量的独特性。还建立了近乎匹配主结果的下界。

原文摘要 · Abstract (English)

We study offline reinforcement learning in average-reward MDPs, which presents increased challenges from the perspectives of distribution shift and non-uniform coverage, and has been relatively underexamined from a theoretical perspective. While previous work obtains performance guarantees under single-policy data coverage assumptions, such guarantees utilize additional complexity measures which are uniform over all policies, such as the uniform mixing time. We develop sharp guarantees depending only on the target policy, specifically the bias span and a novel policy hitting radius, yielding the first fully single-policy sample complexity bound for average-reward offline RL. We are also the first to handle general weakly communicating MDPs, contrasting restrictive structural assumptions made in prior work. To achieve this, we introduce an algorithm based on pessimistic discounted value iteration enhanced by a novel quantile clipping technique, which enables the use of a sharper empirical-span-based penalty function. Our algorithm also does not require any prior parameter knowledge for its implementation. Remarkably, we show via hard examples that learning under our conditions requires coverage assumptions beyond the stationary distribution of the target policy, distinguishing single-policy complexity measures from previously examined cases. We also develop lower bounds nearly matching our main result.

强化学习离线学习样本复杂度马尔可夫决策

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