AIIC AI Intelligence Centre

SOURCE-LINKED INTELLIGENCE

Hitting-Time Bounds for Asynchronous Q-Learning

arXiv · AI, language, vision and robotics · article · Oct 9, 2026 · UTC

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 $\mathfrak 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 $\varepsilon$ with high probability using $\widetilde{O

Read original source ↗ Open in workspace

recordType
paper
region
Global

Evidence & attribution

First collected: 2026-10-13T16:12:24.076Z. This is not the publication date.