Hitting-Time Bounds for Asynchronous Q-Learning
Abstract
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⋆ 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 Õ(H4/(μminε2)+h⋆) transitions, for 0<ε≤1. The statistical term retains the quartic effective-horizon dependence of standard Q-learning, while initialization cost is additive in h⋆. For aperiodic behavior chains, a comparison with mixing time yields a transient term Õ(tmix/μ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.
Related
- L2-error bounds for covariation estimation under asynchronous mixed time-space sampling
- Asynchronous Parallel Computation of Lagrangian Bounds for Mixed-Integer Stochastic Programs by Frank-Wolfe Methods within Projective Hedging
- On the First Hitting Time Problems for Diffusion Processes: Local Time-Space Approach
- Hitting time for loose Hamilton cycles in the random hypergraph process
- A Decomposition of the Hitting Time Index Using the Kirchhoff Index and an Asymmetry Term
BibTeX
@misc{peng2026hittingtime,
title = {{Hitting-Time Bounds for Asynchronous Q-Learning}},
author = {Yang Peng},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.13901},
eprint = {2610.13901},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.13901},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Hitting-Time Bounds for Asynchronous Q-Learning
AU - Yang Peng
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.13901
UR - https://arxiv.org/abs/2610.13901
AB - 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_⋆ 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_⋆) transitions, for 0<ε≤1. The statistical term retains the quartic effective-horizon dependence of standard Q-learning, while initialization cost is additive in h_⋆. For aperiodic behavior chains, a comparison with mixing time yields a transient term Õ(t_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.
ER -