提出新收缩原理，实现平均奖励Q学习的最优样本复杂度。
Achieving $\varepsilon^{-2}$ Dependence for Average-Reward Q-Learning with a New Contraction Principle
- 通过懒惰化动态构造依赖实例的半范数，使贝尔曼算子变为一步收缩。
- 在可达性假设下，同步与异步Q学习均达$ ilde{O}(\varepsilon^{-2})$样本复杂度。
- 无需未知参数或折扣近似，适合研究强化学习收敛性与高效算法设计者。
我们研究了平均奖励马尔可夫决策过程中的同步与异步Q学习的收敛速率。由于缺乏收缩性，这带来了根本性挑战。现有非渐近结果要么施加强假设以强制半范数收缩，要么依赖折扣或周期性马尔可夫决策过程作为逼近方式，前者需要未知参数，后者导致次优样本复杂度。本文在可达性假设下，为一种简单的同步与异步Q学习变体（采样自懒惰化动态）建立了最优$ ilde{O}(varepsilon^{-2})$样本复杂度保证（含对数因子）。核心分析在于构造一个依赖实例的半范数，并证明经懒惰变换后，贝尔曼算子在此半范数下为一步收缩。
原文摘要 · Abstract (English)
We present the convergence rates of synchronous and asynchronous Q-learning for average-reward Markov decision processes, where the absence of contraction poses a fundamental challenge. Existing non-asymptotic results overcome this challenge by either imposing strong assumptions to enforce seminorm contraction or relying on discounted or episodic Markov decision processes as successive approximations, which either require unknown parameters or result in suboptimal sample complexity. In this work, under a reachability assumption, we establish optimal $\widetilde{O}(\varepsilon^{-2})$ sample complexity guarantees (up to logarithmic factors) for a simple variant of synchronous and asynchronous Q-learning that samples from the lazified dynamics, where the system remains in the current state with some fixed probability. At the core of our analysis is the construction of an instance-dependent seminorm and showing that, after a lazy transformation of the Markov decision process, the Bellman operator becomes one-step contractive under this seminorm.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。