Hitting-Time Bounds for Asynchronous Q-Learning (arXiv 2610.13901)

Forum topic · 小凯 · 2026-10-14

Summary

This paper by Yang Peng (arXiv:2610.13901, October 2026) analyzes the last-iterate convergence of standard asynchronous Q-learning run on a single trajectory of a finite Markov decision process. The trajectory follows a fixed behavior policy whose state-action chain is irreducible and possibly periodic. With discount factor gamma, effective horizon H=(1-gamma)^{-1}, minimum stationary state-action probability mu_min, and h_star denoting the largest expected hitting time of the reverse state-action chain, the author proves that zero-initialized Q-learning with a constant step size achieves sup-norm error at most epsilon (0 < epsilon <= 1) with high probability within O-tilde(H^4/(mu_min epsilon^2) + h_star) transitions. The statistical term preserves the standard quartic effective-horizon dependence, while the initialization cost is additive in h_star; for aperiodic behavior chains this transient term becomes O-tilde(t_mix/mu_min) via comparison with mixing time. The paper also proposes an empirical state-action counting rule for choosing constant step sizes in subsequent runs, achieving the same convergence rate without prior knowledge of model parameters, target accuracy, or confidence levels. The proof separates statistical error from fixed-policy initialization error using deterministic Bellman envelopes and adapts reverse-time hitting-cost compensation from TD learning to state-action propagation.

Paper Overview

Field: Machine Learning
Author: Yang Peng
Posted: 2026-10-09
arXiv: 2610.13901

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_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.

Key Results

The statistical term retains the quartic effective-horizon (H^4) dependence of standard Q-learning.
The initialization cost is additive in h_star, the largest expected hitting time of the reverse state-action chain.
For aperiodic behavior chains, comparison with the mixing time yields a transient term of Õ(t_mix/μ_min).
An empirical state-action counting rule selects constant step sizes for subsequent training runs, achieving the same convergence rate without prior knowledge of model parameters, target accuracy, or confidence levels. The output is the final training iterate, with sample counts charged across both phases.

Proof Techniques

The analysis uses two deterministic Bellman envelopes to separate statistical error from fixed-policy initialization error, and adapts the reverse-time hitting-cost compensation method from TD learning to state-action propagation.

---

*Auto-collected on 2026-10-14.*