Hitting-Time Bounds for Asynchronous Q-Learning
Asynchronous Q-learning reaches epsilon error with a quartic horizon term plus an additive hitting-time cost.
The paper analyzes the last iterate of standard asynchronous Q-learning from a single trajectory of a finite Markov decision process. Zero-initialized constant-step-size Q-learning reaches sup-norm error epsilon with high probability after roughly H to the fourth over mu_min epsilon squared plus the reverse-chain hitting time transitions. An empirical state-action count rule selects the step size without prior knowledge of model parameters, target accuracy, or confidence. Combined with lower bounds, the result matches mean-square rates up to logarithmic factors.
- Last-iterate asynchronous Q-learning is analyzed on one finite-MDP trajectory.
- High-probability error needs order H^4 over mu_min epsilon squared plus hitting time.
- A count-based rule picks a constant step size without knowing model parameters.
- Matching mean-square rates hold up to logarithmic factors.
Full article232 words · extracted from arxiv.org · click to collapse
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}(H^4/(μ_{\min}\varepsilon^2)+\mathfrak h_\star)$ transitions, for $0<\varepsilon\le1$. The statistical term retains the quartic effective-horizon dependence of standard Q-learning, while initialization cost is additive in $\mathfrak h_\star$. For aperiodic behavior chains, a comparison with mixing time yields a transient term $\widetilde{O}(t_{\mathrm{mix}}/μ_{\min})$. An empirical state--action count rule selects a constant step size for a subsequent training run and attains the same rate without prior knowledge of model parameters, target accuracy, or confidence level. The output is the last training iterate, with both stages included in the sample count. The proof uses two deterministic Bellman envelopes to separate statistical error from fixed-policy initialization error and adapts reverse-time hitting-cost compensation from TD learning to state--action propagation. An exploration lower bound holds for arbitrary predictable step sizes. Together with the existing statistical lower bound and its extension to pilot-selected constant steps, it yields matching mean-square rates up to logarithmic factors on the stated large-sample parameter classes.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2610.13901