PaperlayerView exact revision on arXiv

Source-linked AI summary

Hitting-Time Bounds for Asynchronous Q-Learning

Yang Peng

arXiv:2610.13901v1stat.MLcs.LG

TL;DR

Asynchronous Q-learning from a single trajectory must account for statistical error and the time required to visit state–action pairs. The paper analyzes standard Q-learning with deterministic Bellman envelopes and reverse hitting-time compensation, obtaining an additive transient alongside the quartic statistical term. It also gives a count-based calibration rule and lower bounds within stated parameter classes.

  • Problem

    For single-trajectory asynchronous Q-learning, sample complexity must account for both statistical error and the time needed to visit state–action pairs.

    Source: §1 · pp. 1–2

  • Method

    The proof uses deterministic Bellman envelopes to separate sampling error from fixed-policy initialization error, while a pilot count rule selects a constant step size for a zero-initialized run.

    Source: §1 · p. 2

  • Results

    The bound retains the quartic statistical term with an additive reverse hitting-time transient, and matching mean-square lower bounds hold up to logarithmic factors on stated parameter classes.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The hitting-time formulation covers irreducible non-reversible and periodic behavior chains and can be substantially smaller for some chains.

    Source: §1 · p. 2

    The lower-bound results retain the statistical result’s large-sample restriction, and the joint bound requires a hitting-time budget containing the hard instance.

    Source: §7 · p. 19

Abstract

from arXiv · show

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 $\gamma$, write $H=(1-\gamma)^{-1}$, and let $\mu_{\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/(\mu_{\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}}/\mu_{\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.

1 Introduction

The introduction frames asynchronous Q-learning as balancing statistical error against the time needed to visit state–action pairs. It presents an additive reverse hitting-time transient, a pilot-based calibration rule, and lower bounds with stated scope restrictions.

1.1 Related work

  • Prior single-trajectory analyses depend on minimum stationary state–action probability and mixing time, while variance reduction improves the statistical horizon dependence (Li et al., 2022).The present results concern the standard update.Source: §1 · p. 1, §1.1 · p. 2

1 Introduction

  • The result retains Q-learning’s quartic statistical term and adds a transient governed by reverse-chain hitting times, with no extra H factor in the aperiodic mixing-time comparison.The bounds cover finite irreducible behavior chains, including non-reversible and periodic chains, and allow arbitrary initial state–action distributions.Source: §1 · p. 2
  • The empirical count rule uses a pilot segment to choose a constant step size for a zero-initialized training run without prior model parameters, target accuracy, or confidence level.Its high-probability guarantee concerns the last training iterate and counts both stages.Source: §1 · p. 2
  • The lower bounds match the statistical and hitting-time terms up to logarithmic factors on specified parameter classes, while the exploration term applies to arbitrary predictable step sizes.The statistical term extends to pilot-selected steps held fixed and concerns mean-square error in the stated large-sample range.Source: §1 · p. 2

1.2 Relation to the analysis of TD learning

  • The analysis shares TD learning’s reverse-time hitting-cost compensation for initialization error but uses Bellman envelopes and visit-clock concentration for Q-learning’s nonlinear stochastic error.The propagation step targets a fixed action at the next state rather than an importance-weighted sampled action.Source: §1.2 · p. 3
  • The empirical calibration differs from the cited TD rule by using a prescribed budget and a new zero-initialized fixed-step run, with a last-iterate guarantee.The Q-learning statistical lower bound is specific to the stated procedure class and mean-square error.Source: §1.2 · p. 3

2 Problem Formulation

The formulation uses a finite discounted MDP and a fixed behavior policy to generate a single state–action trajectory. It studies the last iterate of standard asynchronous Q-learning under an irreducible behavior chain, without averaging or variance reduction.

2 Problem Formulation

  • The finite state–action set has size d, and each observed transition supplies a reward and successor state from a fixed kernel that may couple the two.The discount factor γ is known and H = (1 − γ)^−1.Source: §2 · p. 4
  • A fixed behavior policy induces an irreducible state–action chain with stationary distribution µ; the initial coordinate need not be stationary.The initial physical state may have any distribution, and upper bounds allow an arbitrary initial state–action coordinate.Source: §2 · p. 4
  • The algorithm outputs the last iterate, with no averaging or variance reduction; the calibrated run starts from zero after preliminary observations on the same trajectory.For step sizes between zero and one, the table remains pathwise in [0, H]^d.Source: §2 · p. 4

3 Main Results

The results give total transition complexity eO(H^4/(µminε^2) + h⋆) for the calibrated run and show that reverse-chain hitting time can remain bounded even when mixing time diverges. They also separate statistical error from initialization error and provide a count-based step-size rule.

3.1 A constant step size

  • The proof separates statistical error from initialization error, bounding the latter through a homogeneous propagator under a fixed optimal policy.The statistical term uses concentration on each coordinate’s visit clock; the initialization argument reverses the behavior trajectory.Source: §3.1 · p. 5

3.2 Mixing-time consequence and periodic examples

  • In the nearly alternating example, h⋆ = 4 throughout, while tmix = Θ(1/α) as α ↓ 0; at α = 0 the irreducible chain is periodic.Thus the hitting-time bound remains bounded as the mixing-time bound diverges, including at the periodic limit.Source: §3.2 · p. 6

3.3 Calibration without unknown problem parameters

  • The calibration rule counts visits during an initial segment, then uses the selected constant step size for a zero-initialized Q-learning run on the next segment.For a total budget of 2n transitions, the procedure uses n transitions for calibration and n for training, returning the training run’s last iterate.Source: §3.3 · p. 6
  • The calibrated method has total transition complexity eO(H^4/(µminε^2) + h⋆), while ε, δ, µmin, and h⋆ do not enter its step rule.The rule uses an initial calibration segment before a zero-initialized training run.Source: §3.3 · p. 6

4 Deterministic Bellman Envelopes

The section separates stochastic error from initialization propagation using two deterministic Bellman envelopes. Visit-clock concentration controls the stochastic component, while a fixed-policy recursion isolates the propagation remainder.

4 Deterministic Bellman Envelopes

  • Two deterministic Bellman envelopes separate stochastic fluctuations from homogeneous initialization propagation in the zero-initialized Q-learning comparison.The lower-envelope comparison reduces to fixed-policy propagation.Source: §4 · pp. 7, 10
  • The upper envelope uses a variance certificate valid for every fixed policy, while the lower comparison uses evaluation under the fixed optimal policy.The lower envelope need not be nonnegative.Source: §4 · pp. 7, 8, 10
  • Coordinate-wise target noise forms martingale differences on each coordinate’s visit clock, with Bernstein–Freedman bounds made simultaneous over coordinates and times.The targets are measurable before the next visit, and simultaneous bounds permit substitution of a random visit count.Source: §4 · p. 9
  • The envelope comparison also holds conditionally after calibration when training starts from zero and holds the history-selected step size fixed.The argument does not require a stationary starting distribution.Source: §4 · p. 10

5 Forgetting the Initialization

The initialization analysis adapts reverse-particle and hitting-cost compensation ideas to propagation through a fixed target action. A physical-state potential accounts for movement between states and the additional wait for a specified action.

5 Forgetting the Initialization

  • The initialization argument adapts reverse-particle and hitting-cost compensation for TD learning to propagation that selects a fixed target action at the next state.This action projection is the propagation left by the Bellman-envelope comparison.Source: §5 · p. 10

5.1 Hitting times and a compensation identity

  • A physical-state potential bounded by h⋆ compensates movement between states and the additional waiting time to reach a specified state–action pair.The compensation applies to the projected target kernel.Source: §5.1 · p. 11

5.2 A reverse particle and its lifetime

  • A reverse particle’s survival probability represents propagator row sums along a stationary reversed path, so lifetime tails control forgetting uniformly over starting distributions.The constant-step forgetting result assumes 0 < ηH ≤ 1.Source: §5.2 · pp. 12–13

5.3 Higher-power forgetting

  • Higher-power comparison yields a step-selection bound that does not depend on the confidence level; the proof-only integer p is not part of the algorithm.The result also applies conditionally after a stopping-time pilot when the chosen step is held fixed.Source: §5.3 · p. 14

6 Lower Bounds and the Scope of Optimality

The lower bounds distinguish the cost of leaving coordinates unvisited from the statistical obstruction for constant-step Q-learning. Their joint matching statement is restricted to specified parameter classes and a large-sample regime.

6 Lower Bounds and the Scope of Optimality

  • The statistical matching lower bound is a mean-square result in the cited large-sample range, not a lower bound for arbitrary online step-size rules.The discussion preserves the restrictions of the underlying statistical lower bound.Source: §6 · p. 15, §6.3 · p. 18

6.1 An exploration lower bound for arbitrary step sizes

  • T ≥ (h/8) log(1/δ) is necessary to achieve error below H with failure probability at most δ on the exploration hard class.The exploration lower bound holds for every predictable step-size rule, including after a preliminary observation period and reset.Source: §6.1 · pp. 15–16

6.2 The statistical lower bound and calibration on a pilot trajectory

  • The statistical obstruction for constant-step Q-learning extends to a pilot-selected step when the subsequent run resets to zero and holds that step fixed.The pilot may use observed rewards and transitions as well as visit counts.Source: §6.2 · pp. 17–18

6.3 A joint class statement and its scope

  • Theorem 6.4 matches the statistical and hitting-time lower-bound terms up to logarithmic factors in its stated large-sample parameter class.The joint claim requires a hitting-time budget that contains the statistical hard instance; the two hard instances need not coincide.Source: §6.3 · p. 18

7 Discussion

The discussion states that asynchronous Q-learning retains quartic statistical horizon dependence with an additive reverse hitting-time cost. It identifies the scope of the empirical step-size rule and lower bounds as open directions.

7 Discussion

  • Standard asynchronous Q-learning retains quartic statistical horizon dependence with an additive reverse hitting-time cost.The argument uses fixed Bellman envelopes and adapts reverse-time hitting-cost compensation to state–action propagation.Source: §7 · p. 19
  • The empirical rule requires a prescribed budget, a preliminary count stage, and a fresh zero-initialized training run with a fixed step.Extending it to one uninterrupted decreasing-step recursion and beyond zero initialization remains open.Source: §7 · p. 19
  • The lower-bound scope leaves open smaller hitting-time budgets, broader online step-size rules, and fixed-confidence criteria.The statistical lower bound inherits a large-sample restriction.Source: §7 · p. 19

A Occupancy Concentration from Hitting Times

The occupancy argument converts reverse-chain hitting-time control into bounds on how often each state–action coordinate is visited, including for periodic chains.

A Occupancy Concentration from Hitting Times

  • The reverse-chain hitting-time identity also holds for periodic chains and implies that forward hitting times are at most 2h⋆.The identity follows from first-step equations and the relation between the forward and reverse behavior-chain matrices.Source: A Occupancy Concentration from Hitting… · p. 20
  • After the first visit to a coordinate, its positive return times are independent and identically distributed with mean 1/µ(x).This follows from the strong Markov property and Kac’s formula.Source: A Occupancy Concentration from Hitting… · p. 20
  • Hitting and return times have moment bounds derived from residual waiting times, enabling exponential occupancy-tail control.The proof bounds moments using a uniform residual hitting-time mean and then applies an exponential-moment argument.Source: A Occupancy Concentration from Hitting… · p. 20
  • Combining the bounds gives 4e−n/(48F); for n < 2m ≤ 2F this bound exceeds one but remains valid, and a union bound with 48F ≤ 96(1 + h⋆) proves the occupancy lemma.Source: A Occupancy Concentration from Hitting… · p. 20

B Proof of the Constant-Step Theorem

The constant-step theorem proof controls the fixed-policy initialization remainder and stochastic fluctuations separately, then combines their probability bounds.

B Proof of the Constant-Step Theorem

  • The proof applies a concentration result to the homogeneous propagator for evaluation under the fixed optimal policy, with failure probability δ/2.The stated logarithmic condition and monotone step condition permit the concentration lemma to be applied.Source: B Proof of the Constant-Step Theorem · p. 21
  • The initialization-related term is bounded by ε/2 with failure probability at most δ/2 after setting ρ = ε/(2H).This uses Proposition 5.3 under its stated condition.Source: B Proof of the Constant-Step Theorem · p. 21
  • The step-size condition ηH ≤ 1 holds for a sufficiently large constant, and a union bound completes the proof.The proof verifies the remaining condition from equation (4).Source: B Proof of the Constant-Step Theorem · p. 21

C Q-Learning with an Empirically Calibrated Step Size

The section analyzes a pilot-count rule for choosing a constant step size and establishes guarantees for the last iterate using both stages of the run.

C Q-Learning with an Empirically Calibrated Step Size

  • Conditioned on the pilot history before the next action is drawn, the step size and physical state are fixed, and the following transitions retain the behavior-policy reward law.The bounds hold uniformly over the starting state, so the proof applies conditionally.Source: C Q-Learning with an Empirically… · p. 21
  • The integer p used in the proof is not an input to the algorithm.Source: C Q-Learning with an Empirically… · p. 22
  • The proof of the empirical-step theorem combines occupancy, envelope, and forgetting events to obtain its asserted probability bound.The sample condition ensures the occupancy event, and the proof applies the envelope and forgetting bounds to the estimation run.Source: C Q-Learning with an Empirically… · pp. 21–22
  • The resulting procedure has mean-square error at most ε², although neither its accuracy nor its confidence level is an algorithm input.The proof applies the high-probability theorem at accuracy ε/2 and confidence δ = ε²/(4H²), using the [0,H]^d range to bound squared error on failure.Source: C Q-Learning with an Empirically… · p. 22
Loading 2610.13901v1…