[论文] Hitting-Time Bounds for Asynchronous Q-Learning

论文概要

研究领域: ML 作者: Yang Peng 发布时间: 2026-10-09 arXiv: 2610.13901

中文摘要

我们研究了标准异步 Q-learning 在有限马尔可夫决策过程单条轨迹下末次迭代的收敛性质。轨迹遵循一个固定行为策略，其状态-动作链不可约且可能具有周期性。对于折扣因子 γ，记 H=(1-γ)^{-1}，μ_min 为最小平稳状态-动作概率，h_star 为反向状态-动作链的最大期望击中时间。我们证明：零初始化的 Q-learning 采用常数步长，以高概率在 Õ(H⁴/(μ_min ε²)+h_star) 次状态转移内达到不超过 ε 的 sup-范数误差（0<ε≤1）。统计项保留了标准 Q-learning 的有效视界四次方依赖，而初始化代价以 h_star 呈加性。对于非周期行为链，与混合时间的比较给出瞬态项 Õ(t_mix/μ_min)。一种经验性的状态-动作计数规则为后续训练运行选择常数步长，在无需事先知晓模型参数、目标精度或置信水平的情况下达到相同收敛速率。输出为最后一次训练迭代，两个阶段均计入样本数。证明使用两个确定性 Bellman 包络将统计误差与固定策略初始化误差分离，并将 TD 学习中的反向时间击中代价补偿方法适配到状态-动作传播上。

原文摘要

We study the last iterate of standard asynchronous Q-learning from a single trajectory of a finite Markov decision process. The trajectory follows a fixed behavior policy whose state-action chain is irreducible and may be periodic. For discount factor γ, write H=(1-γ)^{-1}, and let μ_min be the minimum stationary state-action probability and h_star the largest expected hitting time of the reverse state-action chain. We prove that zero-initialized Q-learning with a constant step size achieves sup-norm error at most ε with high probability using Õ(H^4/(μ_min ε^2)+h_star) transitions, for 0<ε≤1. The statistical term retains the quartic effective-horizon dependence of standard Q-learning, while initialization cost is additive in h_star. For aperiodic behavior chains, a comparison with mixing t...

#论文 #arXiv #ML #小凯