Hitting-Time Bounds for Asynchronous Q-Learning

Hitting-Time Bounds for Asynchronous Q-Learning

arXiv:2610.13901v1 [stat.ML] 9 Oct 2026

Yang Peng Yau Mathematical Sciences Center, Tsinghua University yang-peng@mail.tsinghua.edu.cn

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 denote 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 e O + h ⋆ µmin ε2 transitions, for 0 < ε ≤ 1. The first term retains the quartic statistical horizon dependence of standard Q-learning. The second controls initialization error and is additive in h⋆ . For aperiodic behavior chains, a comparison with mixing time gives the corresponding bound with transient e mix /µmin ). An empirical state–action count rule selects a constant step for a subsequent O(t training run and attains the same rate without prior knowledge of unknown model parameters, target accuracy, or confidence level. Its output is the last training iterate, and its sample count includes both stages. The proof uses two deterministic Bellman envelopes to separate statistical error from fixed-policy initialization error, and adapts the reverse-time hitting-cost compensation used for 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.

1

Introduction

Q-learning estimates the optimal action-value function of a Markov decision process by updating one coordinate after each observed transition. In its standard asynchronous form, it uses a single trajectory generated by a behavior policy and stores only the current value table. Understanding the sample complexity of this recursion requires accounting for both statistical error and the time needed to visit the state–action pairs that must be learned. Under independent synchronous sampling, the sharp statistical dependence of standard Qlearning on the effective horizon H = (1 − γ)−1 is quartic (Li et al., 2024). For a single Markov trajectory, existing bounds also depend on the minimum stationary state–action probability µmin and the mixing time tmix of the behavior chain. In particular, Li et al. (2024, Theorem 4) gives the sufficient transition count ! 4 H Ht mix e O + . µmin ε2 µmin

1

The statistical term agrees with their algorithm-specific lower bound in its stated parameter range. The transient term leaves open whether the time needed to explore the behavior chain must be multiplied by the effective horizon. We prove that zero-initialized asynchronous Q-learning retains the quartic statistical term with an additive transient governed by hitting times. Specifically, for 0 < ε ≤ 1, a suitable constant step size gives last-iterate sup-norm accuracy ε with high probability using e O

H4 + h⋆ µmin ε2

!

(1)

transitions. Here h⋆ is the largest expected hitting time between two coordinates of the reverse behavior state–action chain. Our bounds hold for any initial state–action distribution and for finite irreducible behavior chains, including non-reversible and periodic chains. For aperiodic chains, the e mix /µmin ) gives the corresponding mixing-time bound with no extra factor of comparison h⋆ = O(t H in the transient. The hitting-time formulation can also be substantially smaller for some chains, as Example 3.2 illustrates. The proof separates stochastic fluctuations from initialization error. Two deterministic Bellman envelopes control the sampling error using concentration on the visit clock of each coordinate. The upper envelope is a perturbed optimal Bellman fixed point. The lower envelope compares Q-learning with evaluation under a fixed optimal policy and leaves a homogeneous propagation matrix as the initialization remainder. We represent its remaining mass by a reverse-time particle and compensate successive hitting costs with a physical-state potential. This gives the additive h⋆ term in (1). The envelopes and auxiliary evaluation process are used only in the proof; the algorithm remains standard Q-learning. An empirical state–action count rule attains the same rate without prior knowledge of unknown model parameters. For a prescribed budget, the first half of the trajectory supplies visit counts, which determine a constant step size for a zero-initialized run on the second half. The rule uses the known discount factor, the table size, the budget, and observed counts, but no target accuracy or confidence level. Theorem 3.3 gives a high-probability guarantee for the last training iterate, counting both stages. Corollary 3.4 gives the corresponding mean-square bound. Theorem 6.4 gives a matching lower bound, up to logarithmic factors, for the statistical and hitting-time terms on the parameter classes specified there. The statistical term extends the constant-step lower bound of Li et al. (2024) to steps selected from a pilot trajectory and then held fixed. It concerns mean-square error in the stated large-sample range. The exploration term follows from an unvisited-coordinate construction and holds for arbitrary predictable step sizes.

1.1

Related work

Classical convergence results for asynchronous Q-learning include Tsitsiklis (1994). Finite-time analyses of asynchronous stochastic approximation are developed by Qu and Wierman (2020). Li et al. (2022) obtain additive mixing-time bounds for standard and variance-reduced Q-learning. Their Section 3.4 also gives a step-size rule based on empirical occupancy and a guarantee for a stored schedule-boundary iterate. Our calibration result uses a pilot stage and a known budget to obtain (1) for the last iterate of a subsequent constant-step run. Li et al. (2024) establish the quartic statistical rate of standard Q-learning and its algorithmspecific lower bound. We retain this statistical dependence and sharpen the trajectory transient to an additive reverse hitting time. Variance reduction improves the statistical horizon dependence (Li et al., 2022); the results here concern the standard update.

2

Table 1: Single-trajectory transition bounds, up to logarithmic factors, for standard Q-learning and 0 < ε ≤ 1. The present upper bounds use zero initialization. All chain parameters in this table refer to the behavior state–action chain. Method or guarantee

Sufficient count or statistical lower bound

Constant step, Li et al. (2022)

H 5 /(µmin ε2 ) + Htmix /µmin

Constant step, Li et al. (2024)

H 4 /(µmin ε2 ) + Htmix /µmin

Constant step, this paper

H 4 /(µmin ε2 ) + h⋆

Empirically calibrated step, this paper

H 4 /(µmin ε2 ) + h⋆

Statistical lower bound, Li et al. (2024), and its pilot extension here

E∥QT − Q∗ ∥2∞ ≳ H 4 /(µmin T log3 T ), in the stated large-sample range

Monotone comparison arguments for Q-learning appear in Wainwright (2019). Lee (2026) separates positive and negative error components and compares the negative component with an optimal-policy linear system. We use this type of comparison with fixed, variance-sensitive Bellman envelopes and a homogeneous fixed-policy propagation remainder.

1.2

Relation to the analysis of TD learning

Peng (2026) studies importance-weighted asynchronous TD learning for fixed-policy evaluation and obtains the transition bound ! 3 ϱH e O + h⋆ , µmin ε2 where ϱ bounds the action importance ratios. In its state-value formulation, µmin and h⋆ refer to the behavior state chain. That work also covers importance-weighted action-value prediction. Here these parameters refer to the behavior state–action chain. Standard Q-learning uses no importance ratios: conditional on the current state–action pair, the observed transition has the required transition law, and the Bellman backup maximizes over the actions at the next state. Both analyses separate stochastic error from initialization and use a reverse-time particle with a hitting-time potential to obtain an additive transient. The stochastic arguments differ. Peng (2026) retains the exact affine stochastic convolution and controls it with an anchored local Poisson equation and a return-variance certificate. The maximization in Q-learning makes its update nonlinear. We instead use deterministic Bellman envelopes and visit-clock concentration to reduce the error to fixed-policy propagation. A variance certificate valid for every fixed policy controls the upper envelope, whose greedy policy need not be optimal for the original MDP. The remaining propagation selects a fixed target action at the next state, in place of the importance-weighted sampled next action in the TD action-value formulation. Section 5 adapts the hitting-cost compensation to this action projection. Thus the two papers share the initialization analysis principle, while using different estimates for stochastic error. The resulting statistical dependence is cubic in H for TD learning and quartic for standard Q-learning. The step-size and lower-bound results have different scopes as well. Peng (2026) gives constant and decreasing step sizes, together with an empirical-count rule that carries the estimate across epochs and has a time-uniform guarantee. Our empirical rule uses a prescribed budget and a new zero-initialized training run with a fixed step. The TD lower bounds are minimax bounds for policy evaluation on the specified parameter classes. The quartic statistical lower bound here is specific to the stated class of Q-learning procedures and to mean-square error.

3

Organization. Section 2 introduces the model and Q-learning update. Section 3 states the upper bounds and calibration rule. Sections 4 and 5 develop the Bellman envelope and initialization arguments. Section 6 gives the lower bounds, and Section 7 discusses further directions. The appendices collect occupancy concentration and the proofs that combine these ingredients into the stated upper bounds.

2

Problem Formulation

Let S be a finite state space, let A(s) be its nonempty finite action sets, and write X = {(s, a) : s ∈ S, a ∈ A(s)} and d = |X |. Given Xt = (St , At ) = x, the pair (Rt , St+1 ) has a fixed probability kernel Kx on [0, 1] × S, conditionally independent of the preceding history. Rewards and successor states may be dependent within a transition. Write P (v | x) for the state marginal and r(x) for the reward mean. The discount γ ∈ (0, 1) is known and H = (1 − γ)−1 . A fixed behavior policy b draws At from b(· | St ). Its state–action transition matrix is Kb ((s, a), (v, c)) = P (v | s, a)b(c | v). We assume Kb is irreducible on X , and denote its unique stationary distribution by µ. In particular b(a | s) > 0 for each admissible action. Let µmin = min µ(x), x∈X

Kb∗ (x, y) =

µ(y)Kb (y, x) , µ(x)

K∗

h⋆ = max Ex b inf{t ≥ 0 : Xt = y}. x,y

(2)

The initial physical state has any distribution. Upper bounds also allow an arbitrary initial state–action coordinate. No stationary initialization is assumed. For a stationary target policy π, write Kπ ((s, a), (v, c)) = P (v | s, a)π(c | v) and Tπ q = r + γKπ q. The optimal Bellman operator is (T q)(s, a) = r(s, a) + γ

X

P (v | s, a) max q(v, c).

v

c∈A(v)

Its unique fixed point is Q∗ , with 0 ≤ Q∗ ≤ H1. Fix a deterministic optimal policy π ∗ ; it exists because the MDP is finite. Sup norms of vectors and induced sup norms of matrices are both written ∥ · ∥∞ . The algorithm considered throughout is "

Qt+1 (x) = Qt (x) + ηt 1{Xt =x} Rt + γ

#

max

a∈A(St+1 )

Qt (St+1 , a) − Qt (x) ,

Q0 = 0.

(3)

For 0 ≤ ηt ≤ 1, the table stays in [0, H]d pathwise. The output is the last iterate; there is no averaging or variance reduction. The calibrated version starts (3) from zero after a preliminary observation period, on the continuation of the same trajectory. All logarithms are natural unless a base is displayed. Constants denoted by c, C are positive e suppresses logarithmic factors in the displayed statistical numerical constants. The notation O parameters, dimension, and confidence. Statements involving the statistical lower bound retain the explicit restrictions in Section 6.

4

3

Main Results

3.1

A constant step size

Theorem 3.1 (Constant-step last iterate). Under the model in Section 2, fix a deterministic T ≥ 1, 0 < ε ≤ 1, and 0 < δ < 1. Set LT = log

64dH(T + 1) , δεµmin

η=

ε2 . 4096H 3 LT

There is a numerical constant C such that, if !

T ≥C

H 4 LT + h⋆ LT , µmin ε2

(4)

then ordinary Q-learning (3) with ηt = η satisfies P(∥QT − Q∗ ∥∞ ≤ ε) ≥ 1 − δ. The step size in Theorem 3.1 uses the target accuracy, confidence level, and minimum stationary probability. Section 3.3 gives an empirical rule that does not use these quantities. The implicit appearance of T inside LT is logarithmic and gives the transition count (1). The proof is given in Appendix B. Proof overview. The proof has two inputs. The deterministic envelope argument in Section 4 controls the statistical term using concentration only on the visit clock of each coordinate. The propagation argument in Section 5 bounds initialization by reversing the behavior trajectory. Together they give ∥QT − Q∗ ∥∞ ≤ ε/2 + H∥ΦT,0 ∥∞ , where ΦT,0 is the homogeneous propagator under a fixed optimal policy.

3.2

Mixing-time consequence and periodic examples

For an aperiodic Kb , define tmix at total-variation threshold 1/4. Total-variation contraction gives an integer τ ≤ Ctmix log(2/µmin ) such that Kbτ (i, x) ≥ µ(x)/2 for all i, x. Indeed, iterate the usual contraction bound until the total-variation distance is at most µmin /2. Reversal then gives (Kb∗ )τ (x, i) = µ(i)Kbτ (i, x)/µ(x) ≥ µ(i)/2. At successive τ -spaced observation times, the conditional chance of hitting i is at least µ(i)/2. A geometric-tail bound therefore implies h⋆ ≤

2τ Ctmix 2 ≤ log . µmin µmin µmin

Consequently Theorem 3.1, and the calibrated theorem below, imply H4 tmix e O + 2 µmin ε µmin

!

.

The comparison uses the mixing time of the forward behavior chain.

5

(5)

Example 3.2 (Nearly alternating behavior). Take two physical states, two identical actions at each state, a uniform behavior policy, and physical transition matrix !

Pα =

α 1−α , 1−α α

0 ≤ α ≤ 1/4.

The state–action chain has µmin = 1/4. Its reverse equals itself. For a target coordinate, the expected hitting time from the other action at the target physical state is 4; from the opposite physical state it is 2 + (1 − α)−1 ≤ 10/3. Hence h⋆ = 4 throughout this family. For α > 0, the physical eigenvalue 2α − 1 gives tmix = Θ(1/α) as α ↓ 0. At α = 0 the chain is irreducible and periodic. Thus the hitting-time bound can remain bounded as the mixing-time bound diverges, and it still applies at the periodic limit.

3.3

Calibration without unknown problem parameters

The preceding guarantee uses a step size tuned to a target accuracy. We next give a fixed-budget rule that needs no transition probabilities, stationary probabilities, hitting times, target accuracy, or confidence level. The discount factor and the finite state–action space remain known inputs. The only extra operation is counting visits during an initial calibration segment. Fix an integer n ≥ 1, for a total budget of 2n transitions. Observe the first n transitions under the same behavior policy and set Nn (x) =

n−1 X

1{Xt =x} ,

Mn = max{1, min Nn (x)}, x

t=0

(6) 

2

ℓn = log 16dH(n + 8) ,

ηbn = min H

−1

AHℓn , Mn



.

(n)

Here A = 218 is fixed once and for all. At time n, initialize Q0 = 0 and perform exactly n ordinary (n) Q-learning updates on the next n transitions, using the constant step ηbn . Return Qn . The output is the last iterate of this Q-learning run. The calibration data determine its step size; the estimation phase uses each of its transitions once, in chronological order. Theorem 3.3 (Calibration without unknown problem parameters). Under the assumptions of the b 2n = Q(n) main upper-bound theorem, let Q n denote the output of (6). There are universal constants C0 , C1 > 0 such that the following holds. For every δ ∈ (0, 1) and ε ∈ (0, 1], put Ln = log

C0 dH(n + 8)2 . δµmin

If (

n ≥ C1

)

H 4 ℓn Ln + h⋆ Ln , µmin ε2

(7)

then, under every initial state–action distribution, b 2n − Q∗ ∥∞ ≤ ε ≥ 1 − δ. P ∥Q

e 4 /(µmin ε2 ) + h⋆ ). The quantities ε, δ, µmin , and h⋆ occur Thus its total transition complexity is O(H in the guarantee but not in the step rule.

6

The budget is fixed before observing the trajectory. Each budget specifies a pilot segment and a subsequent zero-initialized training run. The proof is given in Appendix C; it uses the occupancy estimate in Appendix A and the higher-power propagation bound in Section 5. Corollary 3.4 (Mean-square accuracy with the same calibrated step). For 0 < ε ≤ 1, the same algorithm satisfies b 2n − Q∗ ∥2 ≤ ε2 E∥Q ∞ whenever

(

n≥C

H 4 ℓn CdH 3 (n + 8)2 CdH 3 (n + 8)2 log + h log ⋆ µmin ε2 µmin ε2 µmin ε2

)

.

The proof is also given in Appendix C.

4

Deterministic Bellman Envelopes

This section separates the statistical error of Q-learning from homogeneous propagation under a fixed optimal policy. Unlike the affine stochastic-convolution analysis of Peng (2026), the argument uses two deterministic Bellman envelopes and concentration on the visit clock of each coordinate. Recall the notation of Section 2, and write V ∗ (s) = maxa Q∗ (s, a). Define the nonnegative function σ∗ by σ∗2 (x) = Var(Rt + γV ∗ (St+1 ) | Xt = x). (8) All vector inequalities below are componentwise. Lemma 4.1 (A variance certificate for every fixed policy). The function u = 2HQ∗ − (Q∗ )2 , where the square is componentwise, satisfies 0 ≤ u ≤ H 2 1,

σ∗2 + γ 2 Kπ u ≤ u

for every stationary policy π.

Consequently, (I − γKπ )−1 σ∗2 ≤ 2H 2 1,

(I − γKπ )−1 σ∗ ∞ ≤

√

2 H 3/2 .

(9)

(10)

Proof. The function f (z) = 2Hz − z 2 is increasing on [0, H]. Fix x = (s, a), write q = Q∗ (x), and set v ′ = V ∗ (St+1 ). Since Q∗ (s′ , a′ ) ≤ V ∗ (s′ ), (Kπ u)(x) ≤ E[2Hv ′ − (v ′ )2 | x]. Using q = E[Rt + γv ′ | x] gives u(x) − σ∗2 (x) − γ 2 (Kπ u)(x) ≥ E Rt (2H − Rt − 2γv ′ ) + 2γv ′ | x ≥ 0. 



Indeed, 2H − Rt − 2γv ′ ≥ 2H − 1 − 2γH = 1. This argument permits arbitrary dependence between Rt and St+1 conditional on x. Let Rπ = (I − γKπ )−1 , which is nonnegative. Then Rπ σ∗2 ≤ Rπ (I − γ 2 Kπ )u = u + γ(1 − γ)Rπ Kπ u ≤ (1 + γ)H 2 1 ≤ 2H 2 1. Every row sum of Rπ equals H. Applying Cauchy–Schwarz to each row yields (Rπ σ∗ )2 ≤ HRπ σ∗2 ≤ 2H 3 1.

7

Lemma 4.2 (Construction of two fixed envelopes). Fix 0 < ε ≤ 1, L ≥ 1, and 0<η≤

ε2 . 4096H 3 L

(11)

(12)

Define p

b(x) = 4 ηL σ∗ (x) + ε/2 + 8ηHL. There are unique vectors Q+ and q − satisfying Q+ = T Q+ + b,

q − = r + γKπ∗ q − − b.

(13)

They obey

ε ε Q∗ − 1 ≤ q − ≤ Q∗ ≤ Q+ ≤ Q∗ + 1. 2 2 Moreover, their fixed-target means satisfy m+ := T Q+ = Q+ − b ≥ 0,

(14)

m− := r + γKπ∗ q − = q − + b ≤ Q∗ ≤ H1.

(15)

Proof. Both maps in (13) are γ-contractions in the maximum norm. Monotonicity gives Q+ ≥ Q∗ , while Q∗ − q − = (I − γKπ∗ )−1 b ≥ 0. Let π + be a deterministic policy greedy with respect to Q+ . The Bellman optimality inequality for Q∗ implies Q+ − Q∗ ≤ γKπ+ (Q+ − Q∗ ) + b, Q+ − Q∗ ≤ (I − γKπ+ )−1 b. Lemma 4.1 therefore bounds either envelope error by 4 2ηL H 3/2 + 2Hε ηL + 8ηH 2 L. p

Under (11), this is at most

p

(16)

! √ 4 2+2 8 ε ε + < , 64 4096 2

where we used ε ≤ 1 and H ≥ 1. Finally, m+ ≥ 0 follows from Q+ ≥ Q∗ ≥ 0 and r ≥ 0; and m− ≤ r + γKπ∗ Q∗ = Q∗ follows from q − ≤ Q∗ . The lower envelope itself need not be nonnegative. We next state the comparison in a form that can be combined directly with a bound on homogeneous propagation. Along the observed trajectory, write Xt = (St , At ) and Zt = (St+1 , π ∗ (St+1 )). For the coordinate vector ex , put T Bt = I + ηeXt (γeT Zt − eXt ),

Φt,0 = Bt−1 · · · B0 ,

Φ0,0 = I.

(17)

Each Bt is a nonnegative substochastic matrix. For such matrices, ∥Φt,0 ∥∞ = ∥Φt,0 1∥∞ . Lemma 4.3 (Two-sided comparison for zero-initialized Q-learning). Let T ≥ 1, 0 < δ < 1, 0 < ε ≤ 1, and 4d(T + 1) L = log . (18) δ Suppose (11) holds. Run ordinary asynchronous Q-learning with the constant step size η and Q0 = 0: 



Qt+1 (Xt ) = (1 − η)Qt (Xt ) + η Rt + γ max Qt (St+1 , a) , a

8

leaving the other coordinates unchanged. Assume each coordinate is visited infinitely often almost surely, as holds for a finite, irreducible behavior chain. Then, with probability at least 1 − δ, simultaneously for all 0 ≤ t ≤ T , ε ε Q∗ − 1 − HΦt,0 1 ≤ Qt ≤ Q∗ + 1. 2 2 In particular, ∥QT − Q∗ ∥∞ ≤

(19)

ε + H∥ΦT,0 ∥∞ . 2

(20)

Proof. Construct Q+ and q − as in Lemma 4.2. For each coordinate x, let τj (x) be its jth visit time, starting with j = 1. Define the fixed targets Yj+ (x) = Rτj (x) + γ max Q+ (Sτj (x)+1 , a),

a − − Yj (x) = Rτj (x) + γq (Sτj (x)+1 , π ∗ (Sτj (x)+1 )).

Let Ft denote the history just before sampling the reward and next state at time t, including Xt . The conditional Markov assumption and the stopping-time property imply E[Yj± (x) | Fτj (x) ] = m± (x). The target revealed after one visit is measurable before the next visit, so these are martingale differences on the visit clock. By (14), their conditional standard deviations are at most σ∗ (x) + ε/2. This follows from the L2 triangle inequality for centered random variables, since each target differs pointwise from R + γV ∗ (S ′ ) by at most γε/2. Furthermore, −γε/2 ≤ Yj− (x) ≤ H.

0 ≤ Yj+ (x) ≤ H + γε/2,

Consequently, the absolute value of either centered target is at most 2H. For each deterministic k ∈ {1, . . . , T }, put Dk± (x) =

k X

η(1 − η)k−j Yj± (x) − m± (x) .

j=1

The weights are deterministic, their maximum is at most η, and their squared sum is η2

k X

(1 − η)2(k−j) ≤

j=1

η ≤ η. 2−η

The one-sided Bernstein–Freedman inequality, applied separately to Dk+ and −Dk− , therefore gives Dk− (x) ≥ −b(x)

Dk+ (x) ≤ b(x),

except on an event of probability at most 2e−L . For completeness, the corresponding Bernstein– Freedman threshold is p
4 2ηL σ∗ (x) + ε/2 + ηHL, 3 which is bounded by (12). A union bound over the d coordinates and the T deterministic values of k makes all these inequalities simultaneous with probability at least 1 − 2dT e−L ≥ 1 − δ. Denote this event by E. Controlling every deterministic k justifies substituting a random number of visits below; no concentration inequality with future-dependent weights is used. 9

We first prove Qt ≤ Q+ on E by induction on t. The claim holds at t = 0. If it holds before each of the first k updates of a coordinate x, the monotonicity of the sampled Bellman backup and expansion of that coordinate’s recursion give Qt (x) ≤

k X

η(1 − η)k−j Yj+ (x) = [1 − (1 − η)k ]m+ (x) + Dk+ (x) ≤ Q+ (x),

j=1

where the last step uses m+ (x) ≥ 0. Unvisited coordinates remain zero and also obey the inequality. Thus the upper comparison holds at every time up to T . For the lower comparison, run two auxiliary fixed-policy evaluation recursions on the same samples: qt+1 = Bt qt + ηRt eXt ,

q0 = 0,

wt+1 = Bt wt + ηRt eXt ,

w0 = H1.

Because the matrices Bt are nonnegative and a maximum is at least the value at π ∗ , induction gives qt ≤ Qt pathwise. Subtracting the two linear recursions gives the exact identity wt − qt = HΦt,0 1.

(21)

We claim that wt ≥ q − for every t ≤ T on E. It holds initially since q − ≤ Q∗ ≤ H1. If it has held before each of the first k updates of coordinate x, monotonicity and expansion give, with a = (1 − η)k , wt (x) ≥ aH + (1 − a)m− (x) + Dk− (x) ≥ aH + (1 − a)m− (x) − b(x) = q − (x) + a[H − m− (x)] ≥ q − (x). The last inequality uses m− (x) ≤ H, not nonnegativity of q − . Unvisited coordinates again satisfy the claim directly. Combining this induction with (21) yields Qt ≥ qt = wt − HΦt,0 1 ≥ q − − HΦt,0 1. Now (14) proves (19), and nonnegativity of Φt,0 proves (20). Conditioning on a calibration stage. The same argument applies conditionally on any initial history when the ensuing Q-learning run starts from zero and its step size is chosen using that history and then held fixed. In that application, the envelopes are fixed conditional on the history. The proof does not require stationarity of the starting distribution. Thus it can be combined with a separate count-calibration argument, without asserting a decreasing-step extension of the envelope lemma.

5

Forgetting the Initialization

The initialization argument follows the reverse-particle representation and hitting-cost compensation developed for TD learning by Peng (2026). We adapt these arguments to propagation that selects a fixed target action at the next state. This action projection is the form of propagation left by the Bellman-envelope comparison. 10

Use the notation and assumptions of Section 2, and fix a deterministic target policy π, which may differ from the behavior policy. The two transition kernels are Kb ((s, a), (v, c)) = P (v | s, a)b(c | v),

Kπ ((s, a), (v, c)) = P (v | s, a)1{c=π(v)} .

Put fπ (s, a) = (s, π(s)). For a trajectory Xt = (St , At ), the homogeneous propagation matrices with a constant step η are T Bt = I + ηeXt γeT fπ (Xt+1 ) − eXt ,

ΦT,0 = BT −1 · · · B0 .

Every Bt is nonnegative and substochastic when 0 < η ≤ 1.

5.1

Hitting times and a compensation identity

For the reverse behavior chain define τz+ = inf{n ≥ 1 : Xn = z},

τz = inf{n ≥ 0 : Xn = z}, h∗z (x) = E∗x τz ,

∗ + h∗,+ z (x) = Ex τz ,

h⋆ = max h∗z (x). x,z

Let db (s) = a µ(s, a) and P̄b (s, v) = a b(a | s)P (v | s, a). Irreducibility implies db (s) > 0, and stationarity gives µ(s, a) = db (s)b(a | s). A bar over a hitting time will refer to the physical-state chain P̄b , with zero-time conventions. Define a potential on physical states and its lift to X by P

P

a(s) =

X

db (u)h̄∗s (u),

a(s, c) = a(s).

u

The potential controls movement between physical states. The additional waiting time for a specified action is bounded by a state–action return time, giving the following compensation for the projected target kernel. Lemma 5.1 (Compensation for a fixed target policy). The potential satisfies 0 ≤ a ≤ h⋆ 1. For x = (s, a) and z = (v, c), 1 ∗ h∗,+ . (22) z (x) ≤ h̄v (s) + µ(z) Consequently, with ℓπ (x) =

∗,+ z Kπ (x, z)hz (x),

P

ℓπ ≤ (Kπ − I)a +

2 µmin

1.

(23)

Proof. The reverse transition formula is Kb∗ ((s, a), (u, c)) =

db (u)b(c | u)P (s | u, c) . db (s)

Its right side does not depend on the current action a. Summing over c shows that the physical-state projection evolves with P̄b∗ . In particular, its maximal mean hitting time is at most h⋆ , which also proves the bound on a. At physical state v, every reverse row is the same. Thus, from (v, a) with a = ̸ c, the mean time to hit z = (v, c) equals the positive return time from z, namely 1/µ(z) by Kac’s formula. The same bound applies when the starting pair is z, using the positive-time convention. Starting from a different physical state, first hit v and then apply the strong Markov property. This gives (22). 11

The classical hitting-time reversal identity (Beveridge and Lovász, 2010), applied to the physicalstate chain, gives h̄∗v (s) = h̄s (v) + a(v) − a(s). (24) A finite-dimensional derivation applies also to periodic chains. For P0 = P̄b and invariant column −1 exists. The hitting equations give h̄ (s) = vector d0 = db , the matrix Z = (I − P0 + 1dT v 0) (Zvv − Zsv )/d0 (v): this expression is zero at s = v and solves the hitting equation away from v. The reverse fundamental matrix is Z ∗ = diag(d0 )−1 Z T diag(d0 ). Hence a(v) = Zvv /d0 (v) − 1, and substituting these formulas proves (24). The physical-state return equation gives X

b(a′ | s)

a′

X

P (v | s, a′ )h̄s (v) =

v

1 − 1. db (s)

Every summand is nonnegative. Therefore, for each x = (s, a), X

P (v | s, a)h̄s (v) ≤

v

db (s)−1 − 1 1 ≤ . b(a | s) µ(x)

Combining this inequality, (22), and (24), and using that a depends only on the physical state, proves (23).

5.2

A reverse particle and its lifetime

Consider a reverse driver with kernel Kb∗ . Given an alive particle at i and driver at x, first draw y ∼ Kb∗ (x, ·). If y = ̸ i, leave the particle at i. If y = i, independently leave it at i with probability 1 − η, move it to fπ (x) with probability ηγ, and kill it with probability η(1 − γ). The next driver location is y. Let ζ ≥ 1 be its death time. The conditional particle masses follow pn+1 = pn + ηpn (y)(γefπ (x) − ey ). Consequently, conditional on a finite driver path, survival probability is the sum of these masses. For a stationary forward trajectory read backward, a particle initially at coordinate i therefore represents the ith row sum of ΦT,0 . Lemma 5.2 (Uniform expected lifetime). If 0 < ηH ≤ 1, then 

M := max Ei,x ζ ≤ 4 i,x

H + h⋆ . ηµmin 

(25)

−1 Proof. Write Fi (x) = Ei,x ζ, D(i) = Fi (i), and r⋆ = maxi,x h∗,+ i (x) ≤ h⋆ + µmin . First M is finite: in ⌈2r⋆ ⌉ steps the driver hits any fixed particle position with probability at least 1/2; at this first activation the particle dies with probability η/H. Iterating this uniform conditional probability bound over blocks gives a geometric tail. Let J be the driver state just before its first positive-time visit to i. First-activation decomposition yields ∗ Fi (x) = h∗,+ (26) i (x) + (1 − η)D(i) + ηγEx [Ffπ (J) (i)].

In particular, M ≤ r⋆ + (1 − η)Dmax + ηγM.

(27)

When the reverse driver starts at i, its last predecessor J before return to i has law Kb (i, ·). To see this, reverse every first-return excursion: the stationary factors in the reverse transition probabilities 12

telescope, so its probability equals that of the reversed forward excursion. Its last predecessor becomes the first forward successor. Almost-sure return then gives the claimed law. Since the mean return time is 1/µ(i), (26) on the diagonal gives D(i) =

X 1 +γ Kπ (i, z)Fz (i). ηµ(i) z

Apply (26) once more, now to Fz (i), and put λ = γ(1 − η). We obtain D≤

1 1 + γℓπ + λKπ D + ηγ 2 M 1. ηµmin

The resolvent (I − λKπ )−1 is nonnegative and has row sums 1/(1 − λ), even if Kπ is reducible. Insert (23) before taking a maximum. The identity (I − λKπ )−1 (Kπ − I) = λ−1 (1 − λ)(I − λKπ )−1 − I 

and 0 ≤ a ≤ amax 1 give Dmax ≤



1/η + 2γ ηγ 2 amax + M. + (1 − λ)µmin 1 − η 1 − λ

Substitute into (27). The coefficient of M after multiplying by 1 − λ is exactly (1 − ηγ)(1 − λ) − ηγ 2 (1 − η) = 1 − γ = H −1 . It follows that M ≤ H(1 − λ)(r⋆ + amax ) +

H(1 − η)(1/η + 2γ) . µmin

Now H(1 − λ) = 1 + ηγH ≤ 2, amax ≤ h⋆ , and (1 − η)(1/η + 2γ) ≤ 2/η. Thus M ≤ 4h⋆ + 2µ−1 min +

H 2H ≤ 4 h⋆ + . ηµmin ηµmin 



Proposition 5.3 (Constant-step forgetting). Suppose 0 < ηH ≤ 1 and define H B= 8 + h⋆ ηµmin  



.

For every initial distribution of the behavior chain and every 0 < ρ ≤ 1,

P ∥ΦT,0 ∥∞ > ρ ≤

d µmin ρ

2−⌊T /B⌋ .

(28)

Here and below the matrix norm is the induced sup norm. Proof. Markov’s inequality and Lemma 5.2 give supi,x Pi,x (ζ > B) ≤ 1/2. The strong Markov property at deterministic block boundaries then gives supi,x Pi,x (ζ > T ) ≤ 2−⌊T /B⌋ . Under stationary time reversal, each expected row sum of ΦT,0 is bounded by this quantity. Markov’s inequality and a union bound over the d rows give (28) without its factor µ−1 min . For an arbitrary initial law ν, the likelihood ratio of any finite forward path relative to its stationary law is ν(X0 )/µ(X0 ) ≤ µ−1 min . This proves the stated bound. 13

5.3

Higher-power forgetting

We adapt the power-comparison argument of Peng (2026) to the constant-step propagation studied here. The resulting bound permits step selection independent of the confidence level. The integer p is used only in the proof and does not enter the algorithm. Corollary 5.4 (Higher-power forgetting). Let p ≥ 1 be an integer and suppose pHη ≤ 1/2. Define  

Bp = 8

2H + h⋆ pηµmin



.

For any initial distribution and 0 < ρ ≤ 1, d

P ∥ΦT,0 ∥∞ > ρ ≤

µmin ρp

2−⌊T /Bp ⌋ .

(29)

The result also holds conditionally after any stopping-time pilot, if the constant η is chosen from the pilot history and then held fixed throughout the displayed propagation interval. Proof. Set Hp =

H +p−1 , p

γp =

H −1 , H +p−1

cp = 1 +

p−1 , H

ηp = 1 − (1 − η)(1 − η/H)p−1 .

For u, v ≥ 0, weighted Jensen’s inequality gives ((1 − η)u + ηγv)p ≤ (1 − η/H)p−1 ((1 − η)up + ηγv p ) ≤ (1 − ηp )up + ηp γp v p . The coefficients of up agree. The comparison of the other coefficients is equivalent to (1−η/H)p−1 (1+ (p − 1)η/H) ≤ 1, which follows from (1 − z)−(p−1) ≥ 1 + (p − 1)z for 0 ≤ z < 1. (p) Along the same trajectory, let ΦT,0 be the fixed-policy propagator with discount γp and step ηp . Coordinatewise induction using the preceding scalar inequality yields (p)

(p)

(ΦT,0 1)⊙p ≤ ΦT,0 1,

∥ΦT,0 ∥p∞ ≤ ∥ΦT,0 ∥∞ .

Moreover, 1 2 cp η ≤ ηp ≤ cp η.

The upper bound is the union bound for a product of numbers in [0, 1]. For the lower bound use (1 − η)(1 − η/H)p−1 ≤ e−cp η and 1 − e−z ≥ z/2 for 0 ≤ z ≤ 1; here cp η ≤ pη ≤ 1/(2H) < 1. Since Hp ≤ H and cp ≤ p, 2H Hp Hp ηp ≤ Hpη ≤ 12 , ≤ . ηp µmin pηµmin Apply Proposition 5.3 to Φ(p) with threshold ρp ; its block length is no larger than Bp . This proves (29). For the conditional statement, condition on the pilot history. The chosen step is then deterministic, and the strong Markov property starts the continuation from its observed behavior state. The bound is uniform over that state.

14

6

Lower Bounds and the Scope of Optimality

This section distinguishes two sources of difficulty. An unvisited coordinate cannot be learned by an algorithm that updates only the current coordinate. The additional statistical cost of ordinary Q-learning is captured by the constant-step lower bound of Li et al. (2024, Theorem 5). We also explain why that lower bound applies when a preliminary trajectory is used to select a step size, provided that Q-learning is subsequently initialized at zero and the selected step size is held fixed. Our matching statement concerns mean-square error and retains the parameter restrictions of the cited statistical lower bound. It does not assert a lower bound for arbitrary online step size rules. Write H = (1 − γ)−1 . For m > 0 and h > 0, let M(H, m, h) be the class of finite discounted MDPs, together with fixed stationary behavior policies, for which the state-action chain is irreducible, rewards belong to [0, 1], there are at most twelve admissible state-action pairs, and K∗

min µb (x) ≥ m,

max Ex b τz ≤ h.

x

x,z

Here τz = inf{t ≥ 0 : Xt = z}, and Kb∗ denotes the stationary time reversal of the behavior chain. State-dependent finite action sets are allowed.

6.1

An exploration lower bound for arbitrary step sizes

Proposition 6.1 (Unvisited-coordinate lower bound). Fix H > 1, 0 < m ≤ 1/4, and h ≥ 1/m. There is an MDP with two states and two actions, with µb,min = m and h⋆ = h, such that zeroinitialized Q-learning satisfies P(∥QT − Q∗ ∥∞ = H) ≥ exp(−8T /h)

(30)

for every integer T ≥ 0 and every predictable step size rule taking values in [0, 1]. The same assertion holds if the algorithm uses a preliminary observation period and then initializes Q-learning at zero. Consequently, E∥QT − Q∗ ∥2∞ ≥ H 2 exp(−8T /h). (31) Proof. Let the physical states be {0, 1}. Both actions have reward one and share the transition matrix ! 1 1−p p , p= ∈ (0, 1/2]. Pp = p 1−p h − 1/m + 2 The behavior policy chooses a designated rare action with probability q = 2m at both states and the other action with probability 1 − q. Thus µb (s, a) = b(a)/2 and µb,min = m. Moreover, Kb∗ ((s, a), (u, c)) = Pp (s, u)b(c) = Kb ((s, a), (u, c)). Fix a target coordinate (v, c) whose action has behavior probability r. Let g0 be its expected hitting time from the other physical state and let g1 be its expected hitting time from physical state v with the other action. First-step analysis gives g0 = 1 + (1 − p)g0 + p(1 − r)g1 ,

g1 = 1 + pg0 + (1 − p)(1 − r)g1 .

Solving yields g1 = 2/r and g0 = 1/p + 2/r − 2. Since p ≤ 1/2 and q ≤ 1/2, the maximal hitting time is attained when r = q, and 1 2 h⋆ = + − 2 = h. p q 15

Start the physical chain at state zero and draw the initial action from the behavior policy. All optimal action values equal H, whereas any coordinate that has not been updated retains value zero. The iterates stay in [0, H], so one unvisited coordinate forces the sup-norm error to equal H. If h ≥ 2/m, consider the event that the first T transitions never leave state zero. Its probability is (1 − p)T . The inequalities p ≤ 2/h and log(1 − p) ≥ −2p imply (1 − p)T ≥ exp(−4T /h). If 1/m ≤ h ≤ 2/m, instead consider the event that all of the first T actions are the nonrare action. Behavior randomization is independent across times conditional on the states, with the same probability at either state; this event has probability (1 − q)T . Since q ≤ 1/2 and m ≤ 2/h, (1 − q)T ≥ exp(−2qT ) = exp(−4mT ) ≥ exp(−8T /h). Neither argument uses the step sizes. If a pilot phase precedes a reset, use the same avoidance event over the entire T observations; the relevant coordinate also remains unvisited after the reset. In particular, achieving error smaller than H with failure probability at most δ requires T ≥ (h/8) log(1/δ) on this class. A mean-square error guarantee E∥QT − Q∗ ∥2∞ ≤ ε2 requires T ≥ (h/8) log(H 2 /ε2 ).

6.2

The statistical lower bound and calibration on a pilot trajectory

We first state precisely the external result that supplies the statistical obstruction. The form below uses sup-norm mean-square error, which is weaker than the maximum coordinate mean-square lower bound in the original theorem. Lemma 6.2 (Constant-step obstruction; Li et al., 2024). There are universal constants c, C > 0 such that the following holds. Fix an integer n ≥ 2 and suppose n ≥ 2,

γ ≥ 0.95,

0<m≤

c , log2 n

n≥

CH 7 log3 n . m

(32)

There is an MDP with four states and at most three actions per state, and a fixed behavior policy, with µb,min = m, for which zero-initialized Q-learning satisfies Es ∥Qn − Q∗ ∥2∞ ≥

cH 4 mn log3 n

(33)

for every constant η ∈ (0, 1) and every initial physical state s, with the first action drawn from the behavior policy. The same hard instance works for all η and s. Its reverse hitting time satisfies h⋆ ≤

2H H +1 ≤ . m m

(34)

Proof and source of the statistical bound. The statistical inequality is Li et al. (2024, Theorem 5); its stated error criterion is maxx E|Qn (x) − Q∗ (x)|2 , which implies (33). Its hypotheses include zero initialization and a constant step size, rather than a stationary initialization of the sample chain. To make the parameterization explicit, write a = 1 − γ and 

ν = (ν0 , ν1 , ν2 , ν3 ) =

16

2 2 1 , − 2m, , 2m . 5 5 5 

The hard instance has action sets A(0) = A(2) = A(3) = {1, 2} and A(1) = {1, 2, 3}, hence nine admissible coordinates. Its rewards and transition rows, in the state order (0, 1, 2, 3), are (s, u) r(s, u) (0, 1) 2/3 0 (0, 2) (1, 1), (1, 2) 1 0 (1, 3) (2, 1) 1 (2, 2) 0 (3, 1) 3/4 0 (3, 2)

P (· | s, u) (1, 0, 0, 0) (1 − 2a(1 − ν0 ), 2aν1 , 2aν2 , 2aν3 ) (3aν0 /2, 1 − 3aν0 /2, 0, 0) (0, 1 − 3a(ν2 + ν3 ), 3aν2 , 3aν3 ) (2aν0 , 0, 1 − 2aν0 , 0) (0, 2aν1 , 1 − 2a(ν1 + ν3 ), 2aν3 ) (0, 0, 0, 1) (2aν0 , 2aν1 , 2aν2 , 1 − 2a(1 − ν3 )).

Take the behavior policy uniform on each state’s action set. For sufficiently small m, direct calculation gives µb,min = ν3 /2 = m. This is the construction of Li et al. (2024, Appendix F.1) with cµ = 2m log2 n. We parameterize the rare-state mass directly so that the actual minimum state–action occupancy is exactly m; absolute normalization factors are absorbed into the universal constants of the quoted theorem. We record uniformity in the initial physical state because it is needed below. The physical behavior kernel of this instance is exactly P b = γI + (1 − γ)1ν ⊤ . For an arbitrary initial physical distribution λ its time-t distribution is exactly γ t λ + (1 − γ t )ν; see the calculation preceding equation (237). Thus all mixing bounds there are uniform in the initial state. The visit-count bounds in Appendix F.2.1 are likewise stated for arbitrary initial states. Appendix F.2.2 uses only the lower bound on the terminal marginal after mixing, and Appendix F.2.3 explicitly allows n/3 steps for mixing. None of these estimates restricts the initial state or changes the hard instance as a function of the initial state or the step size. This gives the uniform-start formulation above when the first action is drawn from the fixed behavior policy, as in the original sampling model. For completeness, the hitting-time bound does not have to be extracted from the cited proof. The physical kernel is reversible with invariant distribution ν. From a physical state different from v, its expected time to reach v is H/ν(v). In general, stationary reversal of a state-action behavior chain has the form ν(u)b(c | u)P (s | u, c) Kb∗ ((s, a), (u, c)) = , ν(s) which is independent of a. Consequently, from any coordinate at physical state v other than a specified target z = (v, c), the expected time to hit z equals the positive return time to z when started at z: their one-step transition distributions coincide. Kac’s formula makes this time 1/µb (z). Applying the strong Markov property at the first visit to physical state v therefore gives K∗

Ex b τz ≤

H 1 H +1 + ≤ . ν(v) µb (z) m

This proves (34). Proposition 6.3 (A step size selected from a pilot trajectory). Fix deterministic integers p ≥ 0 and n ≥ 2. Observe the behavior trajectory through physical state Sp , before drawing action Ap , and choose any Fp -measurable step size ηb ∈ (0, 1), initialize a fresh Q-table at zero, and perform n 17

ordinary Q-learning updates with the frozen step size ηb on the continuation of the same trajectory. Under (32), the hard instance in Lemma 6.2 satisfies b p+n − Q∗ ∥2 ≥ E∥Q ∞

cH 4 . mn log3 n

The choice of ηb can use all observed rewards and transitions, in addition to visit counts. Proof. Specifically, take Fp = σ(S0 , A0 , R0 , S1 , . . . , Ap−1 , Rp−1 , Sp ). Thus the calibration phase does not expose Ap or the outgoing training transition. Conditional on Fp , the training table is zero, the selected step size is a fixed number, and the training trajectory has the law of the same behavior chain started at the observed physical state, with a fresh behavior action. The Markov property and the inequality uniform over initial states and constant step sizes (33) therefore give h i cH 4 b p+n − Q∗ ∥2 | Fp ≥ E ∥Q almost surely. ∞ mn log3 n Taking expectations proves the assertion. The sup-norm risk is used here deliberately: the coordinate attaining a conditional maximum need not be the same for different pilot realizations. A maximum coordinate mean-square version follows with a further factor of at most twelve by summing the coordinate risks before taking expectations.

6.3

A joint class statement and its scope

Theorem 6.4 (Joint lower bound for pilot-calibrated constant step sizes). Consider any algorithm of Proposition 6.3 with n ≤ T = p + n ≤ 2n. Suppose (32) holds and h ≥ 2H/m. Then, for universal constants c, C > 0, (

sup M ∈M(H,m,h)

b T − Q⋆ ∥2 ≥ c EM ∥Q M ∞

)

H4 + H 2 exp(−8T /h) . mT log3 T

(35)

The supremum includes the initial driver distribution. The statement also applies to deterministic constant-step Q-learning by taking p = 0. Proof. The statistical instance of Lemma 6.2 belongs to the class by (34); apply Proposition 6.3. The exploration instance of Proposition 6.1 belongs to the same class and has reverse hitting time exactly h. The supremum is at least the maximum of the two lower bounds, hence at least half their sum. Finally n ≤ T ≤ 2n permits replacing n by T , with a change of universal constants. The two hard instances need not coincide. They lie in the same parameter class, which is sufficient for the supremum-risk assertion (35). The restriction h ≥ 2H/m ensures that the known statistical hard instance lies within the hitting-time budget. We do not claim the same statistical lower bound for every smaller feasible hitting-time budget. Theorem 6.4 identifies the H 4 /(mT ) statistical rate and an additive exploration cost, up to logarithmic factors, in its stated large-sample regime. The restriction n ≳ H 7 /m is material: the cited statistical theorem establishes a matching lower bound only in this large-sample range. Nor does a mean-square lower bound alone imply a constant-failure- probability statistical lower bound. High-probability upper bounds can be compared to (35) by taking a sufficiently small 18

b T − Q∗ ∥∞ ≤ rT (δ) failure probability: since both the table and Q∗ belong to [0, H], a bound ∥Q with probability at least 1 − δ implies b T − Q∗ ∥2 ≤ rT (δ)2 + H 2 δ. E∥Q ∞

Choosing, for example, δ = (T + H)−4 changes logarithmic factors only in the calibrated upper bound. The exploration lower bound itself is already a probability statement and applies to arbitrary predictable step sizes.

7

Discussion

Standard asynchronous Q-learning retains its quartic statistical horizon dependence with an additive reverse hitting-time cost. The argument combines fixed Bellman envelopes for the nonlinear update with initialization analysis under a fixed optimal policy. Its reverse-time compensation follows the approach used for TD learning by Peng (2026), adapted to propagation through the target action at the next state. The empirical step-size rule attains this rate using a prescribed budget, a preliminary count stage, and a zero-initialized training run with a constant step. Extending the result to one uninterrupted recursion with a decreasing step size would bring its algorithmic scope closer to the TD guarantees. The fixed-envelope argument would need to control the contribution of earlier, larger steps while preserving the additive hitting-time cost. Extending the comparison beyond zero initialization is another question. The lower bounds identify the statistical and exploration costs for the specified Q-learning procedures. The statistical result inherits the large-sample restriction of Li et al. (2024), and the joint bound requires a hitting-time budget that contains their hard instance. Obtaining a statistical lower bound for smaller hitting-time budgets, a broader class of online step-size rules, or a fixed-confidence criterion would clarify the scope of quartic horizon dependence further.

References A. Beveridge and L. Lovász. Exit frequency matrices for finite Markov chains. Combinatorics, Probability and Computing, 19(4):541–560, 2010. doi: 10.1017/S0963548310000118. D. Lee. Sign-separated asymmetric finite-time error analysis of Q-learning. arXiv preprint arXiv:2605.16103, 2026. URL https://arxiv.org/abs/2605.16103. Version 2. G. Li, Y. Wei, Y. Chi, Y. Gu, and Y. Chen. Sample complexity of asynchronous Q-learning: Sharper analysis and variance reduction. IEEE Transactions on Information Theory, 68(1):448–473, 2022. doi: 10.1109/TIT.2021.3120096. URL https://arxiv.org/abs/2006.03041. G. Li, C. Cai, Y. Chen, Y. Wei, and Y. Chi. Is Q-learning minimax optimal? A tight sample complexity analysis. Operations Research, 72(1):222–236, 2024. doi: 10.1287/opre.2023.2450. URL https: //arxiv.org/abs/2102.06548. Y. Peng. Near-minimax-optimal rates for asynchronous TD learning with Markovian data. arXiv preprint arXiv:2609.38880, 2026. URL https://arxiv.org/abs/2609.38880. G. Qu and A. Wierman. Finite-time analysis of asynchronous stochastic approximation and Q-learning. In Proceedings of the Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 3185–3205, 2020. URL https://proceedings.mlr.press/v125/qu20a.html. J. N. Tsitsiklis. Asynchronous stochastic approximation and Q-learning. Machine Learning, 16(3):185–202, 1994. doi: 10.1007/BF00993306. M. J. Wainwright. Stochastic approximation with cone-contractive operators: Sharp ℓ∞ -bounds for Q-learning. arXiv preprint arXiv:1905.06265, 2019. URL https://arxiv.org/abs/1905.06265.

19

A

Occupancy Concentration from Hitting Times

For the next lemma, hj (i) and h∗j (i) denote ordinary nonnegative hitting times of j from i in the forward and reverse behavior chains; in particular, both are zero when i = j. Lemma A.1 (Occupancy concentration from maximum hitting time). For every integer n ≥ 1 and every initial distribution, 

Nn (x) n . ∈ / [µ(x)/2, 2µ(x)] ≤ 4d exp − n 96(1 + h⋆ ) 

P ∃x :





(36)

Proof. The hitting-time reversal identity gives hi (j) = h∗j (i) + a(i) − a(j),

a(i) =

X

µ(z)h∗i (z),

0 ≤ a(i) ≤ h⋆ .

z

For clarity, this identity also holds for periodic chains: with Z = (I − Kb + 1µT )−1 , the usual ∗ = µ(j)Z /µ(i), and first-step equations give hj (i) = (Zjj − Zij )/µ(j); the reverse matrix is Zij ji substitution gives the displayed identity. Consequently, hi (j) ≤ 2h⋆ . Put F = 1 + 2h⋆ and fix a coordinate x. Let τ = inf{t ≥ 0 : Xt = x}, and let ξ1 , ξ2 , . . . be the successive positive return times after this first visit. The strong Markov property makes the ξi independent and identically distributed, with mean m = 1/µ(x) by Kac’s formula. Moreover, Eτ ≤ F,

m=1+

X

Kb (x, y)hx (y) ≤ F.

y

For every integer k ≥ 1, the hitting and return times satisfy Eτ k ≤ k!F k ,

Eξ1k ≤ k!mF k−1 .

(37)

Indeed, for any of these times Z, on {Z > s} its residual waiting time at each integer s ≥ 1 is a first hitting time with mean at most F ; at s = 0 it is the original waiting time. Apply induction P k−1 to get EZ k ≤ k!F k−1 EZ. All the moments are finite because finite to Z k ≤ k Z−1 s=0 (Z − s) irreducibility gives a uniform positive probability of a visit within a fixed finite block. For 0 ≤ λ < F −1 , the moment bounds and e−z ≤ 1 − z + z 2 /2 for z ≥ 0 imply Eeλτ ≤ (1 − λF )−1 , mλ log Eeλξ1 ≤ , 1 − λF log Ee−λξ1 ≤ −mλ + mF λ2 . Set λ = (4F )−1 and Wk = ki=1 ξi , with W0 = 0. For the lower occupancy tail, let k = ⌈n/(2m)⌉ − 1. The event Nn (x) < n/(2m) implies τ + Wk ≥ n, and km < n/2. Hence P

P{Nn (x) < n/(2m)} ≤ P{τ ≥ n/4} + P{Wk ≥ 3n/4}   4 3n km 7 ≤ e−n/(16F ) + exp − + ≤ e−n/(48F ) . 3 16F 3F 3 This calculation also applies when k = 0. If n ≥ 2m, put k = ⌊2n/m⌋. The event Nn (x) > 2n/m implies Wk < n, while km ≥ 3n/2. Thus 

P{Nn (x) > 2n/m} ≤ exp

n 3km − 4F 16F



≤ e−n/(32F ) .

Combining these bounds gives 4e−n/(48F ) . When n < 2m ≤ 2F , this last bound exceeds one and is still valid. A union bound and 48F ≤ 96(1 + h⋆ ) prove the lemma. 20

B

Proof of the Constant-Step Theorem

Proof of Theorem 3.1. Let ΦT,0 be the homogeneous propagator of evaluation under π ∗ along the behavior trajectory, defined in (17). Lemma 4.3, with failure probability δ/2, applies because LT ≥ log(8d(T + 1)/δ) and its step condition is monotone in the logarithm. On that event, ∥QT − Q∗ ∥∞ ≤ ε/2 + H∥ΦT,0 ∥∞ . Proposition 5.3, applied with ρ = ε/(2H), makes the second term at most ε/2 with failure probability at most δ/2, provided      H 4dH T ≥ 8 + h⋆ log2 . ηµmin δεµmin The step satisfies ηH ≤ 1, and (4) implies this last condition for a sufficiently large C. A union bound completes the proof.

C

Q-Learning with an Empirically Calibrated Step Size

Proof of Theorem 3.3. All constants below are universal. Increase C0 so that every logarithm appearing in the two-envelope bound with confidence δ/3 and length n is at most Ln . Write E for the event in which all empirical frequencies belong to the intervals in Lemma A.1. The sample condition, for sufficiently large C1 , implies n ≥ 96(1 + h⋆ ) log(12d/δ),

nµmin ≥ 1.

Therefore P(E c ) ≤ δ/3, and on E, 1 2 nµmin ≤ Mn ≤ 2nµmin .

The cap in (6) is inactive when C1 is sufficiently large. In particular, AHℓn 2AHℓn ≤ ηbn ≤ . 2µmin n µmin n

(38)

Condition now on the pilot history through Sn , before drawing An . The step ηbn and physical state Sn are fixed under this conditioning. Draw An freshly from the behavior policy; subsequent transitions have the original Markov reward law. All bounds used below hold uniformly over this starting state and therefore apply conditionally. The event E is measurable with respect to the conditioning history. Let Φ be the fixed-optimal-policy propagation matrix on the estimation segment, and put 

p=

Ln , ℓn 

r = (n + 8)−1 ,

q = δ/3.

Because Ln ≥ ℓn , we have Ln ≤ pℓn ≤ 2Ln . By (38), pH ηbn ≤

4AH 2 Ln . µmin n

Thus pH ηbn ≤ 1/2 when C1 is sufficiently large. Corollary 5.4 gives a block length satisfying  

bp = 8

2H + h⋆ pηbn µmin



21

≤

32n + 8h⋆ + 1 ALn

and the conditional failure bound P{∥Φ∥∞→∞ > r | Fn } ≤ Define

µmin

d



k = log2

d

µmin qrp

r−p 2−⌊n/bp ⌋ .



.

The inequalities log(d/(µmin q)) ≤ Ln and p log(n + 8) ≤ Ln show that k ≤ 4Ln . Consequently, bp k ≤

128 n + 32h⋆ Ln + 4Ln ≤ n, A

by the specified value of A and a sufficiently large C1 . We obtain 



P E ∩ {∥Φ∥∞→∞ > (n + 8)−1 } ≤ δ/3.

(39)

The integer p is only a proof parameter and is not used by the algorithm. The upper bracket in (38) and (7) also imply ηbn ≤

cε2 , H 3 Ln

ηbn H ≤ 1,

where c can be the numerical constant in the two-envelope lemma. Apply Lemma 4.3 conditionally to the zero-initialized estimation run, with confidence δ/3. On E, outside an additional event of unconditional probability at most δ/3, b 2n − Q∗ ∥∞ ≤ ε/2 + H∥Φ∥∞→∞ . ∥Q

Finally, (7) ensures H/(n + 8) ≤ ε/2. Combining the occupancy, envelope, and forgetting events proves the asserted probability bound. Proof of Corollary 3.4. Apply Theorem 3.3 with accuracy ε/2 and confidence δ = ε2 /(4H 2 ). Both the Q-learning iterates and Q∗ belong to [0, H]d , so the squared error is at most H 2 on the failure event. Its expectation is therefore at most ε2 /4+δH 2 ≤ ε2 . Neither this accuracy nor this confidence is an algorithm input.

22

Related documents

• Hitting-Time Bounds for Asynchronous Q-Learning#1298397
• $Q$ Can Play That Game: Online Fitted $Q$-Iteration for Continuous-Action Zero-Sum Markov Games with Convex-Concave Function Approximation#1199284
• Multiscale Reward Hedging from Correct Demonstrations#1077929
• Near-Optimal Sample Complexity for Recursive Entropic Risk Reinforcement Learning with a Generative Model#1216013
• Learning Multiple Timescales for Goal-Conditioned Reinforcement Learning#1155784