Hitting-Time Bounds for Asynchronous Q-Learning: New Advances in Sample Complexity

A new theoretical study in reinforcement learning provides a refined sample complexity analysis for the last iterate of asynchronous Q-Learning. This work focuses on the practical setting of learning from a single trajectory and introduces the "hitting time" perspective to characterize initialization costs, offering a more practice-oriented theoretical framework for understanding the convergence behavior of asynchronous Q-Learning.

Background and Problem Setup

Classical convergence analyses of Q-Learning mostly rely on synchronous updates or assumptions of independent sampling for each state-action pair, but real online learning typically depends on a single trajectory generated by a fixed behavior policy. This paper operates precisely under this more realistic constraint.

The object of study is a finite Markov Decision Process (MDP) whose trajectory is generated by a fixed behavior policy, with an irreducible state-action chain that is allowed to be periodic. This is a key point — allowing periodicity means the analysis no longer relies on the traditional mixing time framework, and more general tools are needed to handle the temporal correlations in sampling.

The paper characterizes problem difficulty through several core quantities: the effective horizon $H=(1-\gamma)^{-1}$ corresponding to discount factor $\gamma$, the minimum stationary state-action probability $\mu_{\min}$, and the maximum expected hitting time $\mathfrak{h}_\star$ of the reverse state-action chain. These quantities correspond respectively to the difficulty introduced by discounting, the uniformity of sampling coverage, and the "reachability" structure of the chain.

Hitting Time is a fundamental concept in Markov chain theory, referring to the expected number of steps needed to reach a target state (or set of states) for the first time, starting from some initial state. In asynchronous Q-Learning, the frequency with which different state-action pairs are visited depends on the behavior policy and the chain structure — if a particular state-action pair is "hard to reach" on the chain, it receives almost no updates early in training, and its Q-value estimate remains near the initialization value for a long time. The $\mathfrak{h}_\star$ in the paper takes the maximum expected hitting time over all state-action pairs on the reverse-time chain (i.e., the chain with transition directions reversed). This quantity captures the initialization cost incurred by "the hardest-to-cover state-action pair," providing a finer characterization of the local reachability structure of the chain than mixing time alone.

Core Result: Sample Complexity Bound

The main theorem of the paper states that Q-Learning with zero initialization and a constant step size can, with high probability, drive the sup-norm error below $\varepsilon$ using $\widetilde{O}(H^4/(\mu_{\min}\varepsilon^2)+\mathfrak{h}_\star)$ state transitions (for $0<\varepsilon\le1$).

The structure of this bound warrants a closer look:

• The statistical term $\widetilde{O}(H^4/(\mu_{\min}\varepsilon^2))$ retains the quartic dependence on the effective horizon that is standard in Q-Learning analysis. This dependence has previously been shown to be unimprovable in the worst case, so the result matches existing statistical lower bounds.
• The initialization cost $\mathfrak{h}_\star$ appears in an additive form rather than multiplicatively. This means the extra cost due to hitting time is a one-time "warm-up" expense that does not grow as the accuracy requirement $\varepsilon$ tightens.

For the aperiodic behavior chain setting, the paper also provides a comparison with mixing time, yielding a transient term $\widetilde{O}(t_{\mathrm{mix}}/\mu_{\min})$, which connects the new framework to traditional mixing-time-based analyses.

Last Iterate convergence and Average Iterate convergence represent two distinct analytical paradigms in reinforcement learning theory. Average iterate outputs the mean of all historical Q-values, with statistical noise averaged away, making the analysis relatively tractable. However, practical algorithms almost always use the most recent Q-values directly — that is, the last iterate. Last iterate analysis is technically harder because it must control the fluctuation of a single estimate rather than the bias of a mean. Last iterate guarantees for Q-Learning have long lagged behind average iterate analyses and analogous results for methods like policy gradient. By providing tight bounds for the last iterate, this paper fills that gap, aligning theoretical conclusions with how the algorithm is actually deployed.

Step Size Selection Without Prior Knowledge

While the theoretical bound is elegant, a practical obstacle often arises: the optimal value of the constant step size typically depends on model parameters, the target accuracy, or the confidence level — all of which are unknown at training time.

The paper proposes a rule based on empirical state-action count for selecting the constant step size in subsequent training phases. This rule requires no prior knowledge of any model parameters, target accuracy, or confidence level, yet achieves the same convergence rate as the theoretically optimal step size. More importantly, the algorithm outputs the last training iterate rather than the historical average, and samples from both phases (step size selection + formal training) are counted toward the total sample budget — making the sample complexity accounting more honest.

Proof Techniques: Dual Bellman Envelopes and Reverse Hitting-Cost Compensation

From a methodological standpoint, the technical contributions of this paper are equally noteworthy. The core of the proof involves constructing two deterministic Bellman envelopes to decouple statistical error from initialization error under a fixed policy. This separation is the key reason why initialization cost can appear in additive form.

Another technical highlight is the adaptation of reverse-time hitting-cost compensation from TD learning analysis to the state-action propagation setting. This type of technique was originally developed to handle temporal correlations in temporal difference learning; the paper extends it to the update structure of Q-Learning.

The paper also proves an exploration lower bound that holds for any predictable step sizes. Combined with existing statistical lower bounds and their extensions to pilot-selected constant steps, these results collectively yield matching mean-square rates — accurate up to logarithmic factors — over the given class of large-sample parameters. In other words, the upper and lower bounds agree in order of magnitude, indicating that the analysis is essentially tight for this class of problems.

Bellman Envelope construction is motivated by writing the Q-Learning update as a Bellman operator iteration plus noise. A deterministic envelope refers to constructing two monotone deterministic sequences — one bounding from above and one from below — such that the actual random Q-value trajectory is always sandwiched between them. The key to decoupling statistical error from initialization error lies in recognizing that statistical error originates from the accumulation of sampling noise, whose magnitude is jointly determined by the step size and the number of samples; initialization error, on the other hand, arises from the distance between the starting point of Q-values (zero initialization) and the true Q-function, and its decay rate is governed by the Bellman contraction rate $\gamma$ and the time at which each state-action pair is first sufficiently visited. The dual envelope technique mathematically separates the evolution of these two components, causing hitting time to appear only in the term characterizing initialization decay — naturally yielding the additive structure.

Significance and Positioning

The value of this work lies in unifying three elements that are often treated separately into a single framework: single-trajectory sampling, periodic behavior chains, and practical step size adaptation. For researchers focused on the theory of sample efficiency in reinforcement learning, it provides a tight analytical paradigm under weaker assumptions. The introduction of hitting time as a measure of initialization cost also offers a new angle for understanding the question of "where does learning start."

It should be noted that this is primarily a theoretical study, and its conclusions rest on assumptions such as finite MDPs and fixed behavior policies, placing it at some distance from the function approximation setting of deep reinforcement learning. But as one piece of the puzzle in Q-Learning convergence theory, it further narrows the gap between statistical limits and algorithmic achievability.