PaperlayerView exact revision on arXiv

Source-linked AI summary

Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction

Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, Yuxin Chen

arXiv:2006.03041v3cs.LGeess.SPmath.OCmath.STstat.MLstat.TH

TL;DR

Asynchronous Q-learning must estimate the optimal Q-function from a single Markovian trajectory, and the tightness of its sample-complexity analysis has remained uncertain. This paper develops a refined analysis using trajectory features and studies a variance-reduced variant. It reports an improvement over the prior bound and improved effective-horizon scaling for the variant, while leaving the exact horizon dependence unresolved.

  • Problem

    How many samples asynchronous Q-learning needs to estimate the optimal Q-function from a single Markovian trajectory remains unclear, with a reported gap between asynchronous and synchronous bounds.

    Source: §1 · p. 3

  • Method

    The paper develops a refined finite-sample analysis of classical asynchronous Q-learning using mixing time and minimum state-action occupancy, and analyzes a variance-reduced variant.

    Source: §1.1 · p. 3, §10 · p. 27

  • Results

    The classical asynchronous Q-learning bound improves on the state-of-the-art result by at least |S||A|, while the variance-reduced variant improves effective-horizon scaling.

    Source: §10 · p. 27

  • Takeaways & Limitations

    The analysis sharpens understanding of asynchronous Q-learning sample efficiency through the trajectory's intrinsic features.

    Source: §10 · p. 27

    The exact effective-horizon scaling for asynchronous Q-learning remains open for future work.

    Source: §10 · p. 28

Abstract

from arXiv · show

Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP), based on a single trajectory of Markovian samples induced by a behavior policy. Focusing on a $\gamma$-discounted MDP with state space $\mathcal{S}$ and action space $\mathcal{A}$, we demonstrate that the $\ell_{\infty}$-based sample complexity of classical asynchronous Q-learning --- namely, the number of samples needed to yield an entrywise $\varepsilon$-accurate estimate of the Q-function --- is at most on the order of $\frac{1}{\mu_{\min}(1-\gamma)^5\varepsilon^2}+ \frac{t_{mix}}{\mu_{\min}(1-\gamma)}$ up to some logarithmic factor, provided that a proper constant learning rate is adopted. Here, $t_{mix}$ and $\mu_{\min}$ denote respectively the mixing time and the minimum state-action occupancy probability of the sample trajectory. The first term of this bound matches the sample complexity in the synchronous case with independent samples drawn from the stationary distribution of the trajectory. The second term reflects the cost taken for the empirical distribution of the Markovian trajectory to reach a steady state, which is incurred at the very beginning and becomes amortized as the algorithm runs. Encouragingly, the above bound improves upon the state-of-the-art result \cite{qu2020finite} by a factor of at least $|\mathcal{S}||\mathcal{A}|$ for all scenarios, and by a factor of at least $t_{mix}|\mathcal{S}||\mathcal{A}|$ for any sufficiently small accuracy level $\varepsilon$. Further, we demonstrate that the scaling on the effective horizon $\frac{1}{1-\gamma}$ can be improved by means of variance reduction.

1 Introduction

The introduction frames asynchronous Q-learning as learning from a single Markovian trajectory, where non-i.i.d. sampling makes sample-complexity analysis harder. It motivates sharper bounds and introduces a variance-reduced variant to improve effective-horizon scaling.

1 Introduction

  • The paper studies how many samples asynchronous Q-learning needs to estimate the optimal Q-function from a single behavior-policy trajectory.Unlike the synchronous setting, only one state-action pair is updated per sample, and the resulting sampling process is Markovian.Source: §1 · pp. 2–3
  • The introduction identifies a gap of at least |S||A| between state-of-the-art asynchronous and synchronous sample-complexity bounds.This motivates examining whether a bottleneck intrinsic to asynchronous sampling limits performance.Source: §1 · p. 3

1.1 Main contributions

  • The analysis uses the trajectory's mixing time and minimum state-action occupancy probability to characterize its sample efficiency.The mixing time describes how quickly the trajectory moves beyond its initial state; minimum occupancy captures the least-visited state-action pair's frequency.Source: §1.1 · p. 3
  • The paper analyzes a variance-reduced asynchronous Q-learning variant to improve scaling with the effective horizon 1/(1−γ).The introduction also connects the results to ℓ∞ sample-complexity guarantees for TD learning on Markovian samples when the action space is a singleton.Source: §1.1 · p. 4
  • The introduction places the work alongside prior cover-time-based bounds and notes that its analysis framework supports comparisons involving cover time.The paper's roadmap covers models and assumptions, algorithmic guarantees, related work, theorem analyses, and conclusions; notation and preliminary Markov-chain facts are also introduced.Source: §1.1 · p. 4, §1.2 · pp. 4–5

1.2 Paper organization, notation, and basic concept

  • Section 1.2 introduces notation, including entrywise vector operations and conventions for inequalities and universal constants.It also introduces uniform ergodicity for Markov chains.Source: §1.2 · p. 5

2 Models and background

The paper studies a discounted, infinite-horizon MDP and seeks its optimal Q-function from a trajectory generated by a stationary behavior policy. It formalizes asynchronous updates and characterizes the behavior chain through its stationary distribution, occupancy, and mixing properties.

2 Models and background

  • The setting is a discounted infinite-horizon MDP with finite state and action spaces and rewards in [0,1].The paper focuses on the tabular setting, including cases with large state or action spaces and long effective horizons.Source: §2 · p. 5
  • A stationary behavior policy induces a time-homogeneous Markov chain over state-action pairs, assumed uniformly ergodic.The trajectory supplies the samples, while the behavior policy may differ from the optimal policy being sought.Source: §2 · p. 6
  • The analysis characterizes the behavior chain using its stationary state-action distribution, minimum occupancy, mixing time, and cover time.Minimum occupancy reflects how often the least-visited pair occurs; mixing time measures decorrelation from the initial state, and cover time concerns visiting every pair.Source: §2 · p. 6
  • The objective is to approximate the optimal Q-function in the ℓ∞ sense, updating a state-action pair only when the behavior-policy trajectory reaches it.This is the paper's asynchronous Q-learning setting.Source: §2 · p. 6

3 Asynchronous Q-learning on a single Markovian trajectory

The section presents asynchronous Q-learning on a single trajectory and establishes finite-sample guarantees, then extends the analysis to TD learning and adaptive learning rates.

3.1 Algorithm

  • Each asynchronous Q-learning step updates only the sampled state-action entry using the empirical Bellman operator, leaving all other entries unchanged.The algorithm initializes Q_0 to zero unless otherwise noted.Source: §3.1 · p. 7

3.2 Theoretical guarantees for asynchronous Q-learning

  • The sample-complexity bound is linear in 1/µ_min; with near-uniform occupancy it scales linearly in |S||A| and improves on Qu and Wierman (2020) by at least |S||A|.Its accuracy-dependent scaling is 1/((1−γ)^5 ε^2), matching the synchronous setting; the additive mixing-time cost is nearly accuracy-independent and amortized as the algorithm runs.Source: §3.2 · p. 8
  • A fixed learning rate yields linear ℓ∞ error decay to a rate-determined floor, but the Theorem 1 prescription requires ε, δ, and T in advance.A carefully designed diminishing schedule can achieve the same guarantees without requiring those parameters a priori.Source: §3.2 · p. 8
  • The cover-time analysis gives an alternative guarantee, but does not strictly dominate the mixing-time analysis in every instance; it is tighter in worst-case scenarios.For uniformly ergodic chains, t_cover = eO(t_mix/µ_min); some cases also satisfy t_mix/µ_min = eO(t_cover).Source: §3.2 · p. 9

3.3 A special case: TD learning

  • With a singleton action set, the Q-learning analysis yields non-asymptotic ℓ∞ guarantees for TD learning on Markovian samples.The stated guarantee assumes an appropriate constant learning rate; prior cited ℓ∞ TD analysis focused on synchronous i.i.d. samples.Source: §3.3 · p. 10

3.4 Adaptive and implementable learning rates

  • The proposed visit-count-based learning-rate schedule is data-driven and avoids prior knowledge of t_mix, µ_min, or the target accuracy ε.The analysis extends to this schedule and retains the performance guarantee advertised for Theorem 1.Source: §3.4 · pp. 10–11
  • The ordinary visit-count linear learning rate can yield sample complexity exponential in the effective horizon, unlike a properly rescaled linear rate.The cited discussion notes this risk for η_t = 1/K_t(s_t,a_t).Source: §3.4 · p. 11

4 Extension: asynchronous variance-reduced Q-learning

The section introduces epoch-based variance reduction for asynchronous Q-learning and establishes guarantees that improve its dependence on the effective horizon. Its first complexity term matches the synchronous result in a stated accuracy range, while extensions cover adaptive learning rates and TD learning.

4 Extension: asynchronous variance-reduced Q-learning

  • Variance reduction improves the effective-horizon scaling, with a stated (1−γ)^-3 scaling matching the synchronous minimax lower bound.The passage identifies the lower bound with Azar et al. (2013).Source: §4 · p. 11, §4.2 · p. 13

4.1 Algorithm

  • The update replaces the stochastic Bellman term with a difference of empirical operators plus a batch estimate, aiming to reduce variability when Q is close to the current estimate.The batch estimate is computed once per epoch to limit the sampling burden.Source: §4.1 · p. 12
  • Each epoch estimates T(Q) from N consecutive transitions, then uses that estimate in iterative updates centered at the reference Q-function.The reference is periodically updated across epochs to better approximate Q* and reduce bias.Source: §4.1 · p. 12

4.2 Theoretical guarantees for variance-reduced Q-learning

  • The variance-reduced complexity’s first term matches the synchronous independent-sample result, apart from a mixing-time term, for the stated small-accuracy range.The synchronous match is stated for ε ∈ (0, min{1, 1/((1−γ)√t_mix)}].Source: §4.2 · p. 13
  • The analysis also yields asynchronous variance-reduced TD guarantees and allows adaptive learning rates without prior knowledge of t_mix and μ_min.The paper says these extensions do not compromise sample complexity.Source: §4.2 · p. 13

5 Related works

The related-work discussion places the paper among finite-sample analyses of Q-learning and other model-free algorithms. It contrasts asynchronous guarantees with synchronous results, momentum-based methods, and model-based approaches.

Finite-sample ℓ∞ guarantees for Q-learning

  • Prior synchronous Q-learning bounds use rescaled linear or constant learning rates, while this work gives the first classical asynchronous analysis with linear scaling in 1/μ_min or t_cover.The passage points to Table 1 for detailed comparisons.Source: §5 · p. 14
  • Speedy Q-learning uses a momentum term and twice the storage of classical Q-learning, but its proof relies on update-specific details that do not readily improve asynchronous horizon dependence.The cited speedy Q-learning result is attributed to Azar et al. (2011).Source: §5 · p. 14

Finite-sample guarantees for model-free algorithms

  • Recent Markovian analyses cover TD learning, Q-learning, and SARSA, but typically study weighted ℓ2 error rather than ℓ∞ risk.Khamaru et al. (2020) studied ℓ∞ bounds for variance-reduced TD learning without accounting for Markovian noise.Source: §5 · p. 15

Finite-sample guarantees for model-based algorithms

  • Model-based empirical-MDP planning has synchronous minimax-optimal sample complexity for finding both an ε-optimal Q-function and policy, whereas the model-free optimality claim covers a smaller accuracy range.The passage notes that existing model-based analyses might generalize to Markovian data.Source: §5 · p. 15

6 Analysis of asynchronous Q-learning

This section analyzes asynchronous Q-learning with a constant learning rate by deriving blockwise error decay and then using recursive bounds to establish sample-complexity guarantees. The proof combines concentration for Markovian samples with stability and frame-based recursion.

6.1 Error decay in the presence of constant learning rates

  • With a constant learning rate, the ℓ∞ estimation error decays linearly in blocks to an error floor scaling with √η.Theorem 5 holds with the probability and parameter conditions stated in the theorem.Source: §6.1 · p. 16

6.2 Proof of Theorem 5

  • The proof combines an epoch-based view, Markov-chain concentration, and recursive relations to connect asynchronous dynamics with the synchronous counterpart.The authors say these ingredients collectively yield a bound improving on Qu and Wierman (2020).Source: §6.1 · p. 16

6.2.1 Key decomposition and a recursive formula

  • The key decomposition separates the error into terms controlled using transition-level statistical independence, Bernstein concentration, and empirical-distribution concentration.The stated bounds are assembled into a recursive formula for the error.Source: §6.2.1 · pp. 16–17

6.2.2 Recursive analysis

  • A crude induction bound establishes update stability, while a refined frame-based recursion bounds the error through auxiliary sequences.The refined analysis divides iterations into frames of t_frame iterations.Source: §6.2.2 · pp. 17–19

6.3 Proof of Theorem 1

  • The proof of Theorem 1 selects the learning rate to bound both terms in the error estimate, yielding an ℓ∞ error at most 3ε before rescaling ε.The displayed proof conditions the first-term bound on η < 1/μ_frame.Source: §6.3 · p. 19

7 Cover-time-based analysis of asynchronous Q-learning

The cover-time analysis replaces mixing-frame quantities with cover-time quantities in the convergence argument. Its key input is that, with high probability, every state-action pair is visited in each cover-time frame.

7 Cover-time-based analysis of asynchronous Q-learning

  • With high probability, every state-action pair is visited at least once in each time frame of length t_cover,all.The claim applies to frames within the stated time range.Source: §7 · p. 20
  • The cover-time argument requires T > t_cover,all and 0 < η < 1 for its stated high-probability bound.The guarantee is uniform over the specified iterations and initial error vectors.Source: §7 · p. 20
  • Replacing t_frame and μ_min with t_cover,all and 1/t_cover,all yields a cover-time-based analogue of the recursive convergence guarantee.The analysis reuses the recursive argument after applying the cover-time concentration result.Source: §7 · p. 20

8 Analysis under adaptive learning rates (proof of Theorem 3)

The proof analyzes adaptive learning rates over piecewise-constant time intervals. It uses a crude error bound at interval starts and then refines the analysis to establish the theorem.

Refined analysis

  • The refined proof invokes a concentration result to obtain a high-probability bound in its analysis of the change points.It then applies Theorem 1 from the interval-start estimate under a sample-size condition.Source: §8 · pp. 21–22

Useful preliminary facts about η_t

  • Within each time segment, the auxiliary estimate remains fixed, so the analysis can focus on the estimates at change points.The segments are defined by the change points t_k.Source: §8 · p. 21

A crude bound

  • The proof bounds the estimation error at the start of each interval using a crude bound on ∥Q_t−Q⋆∥∞.For t > 1/(1−γ), the bound is ∥Q_t−Q⋆∥∞ ≤ 3t.Source: §8 · p. 22

9 Analysis of asynchronous variance-reduced Q-learning

The variance-reduced asynchronous Q-learning analysis proceeds epoch by epoch, separating large- and small-error regimes. It establishes an ℓ∞ error of at most 3ε after the required number of epochs.

9.1 Per-epoch analysis

  • Each epoch starts with estimate Q0 = Q and subsequent variance-reduced Q-learning updates; initial-estimate quality determines its two phases, while the empirical transition-kernel matrix uses N new sample transitions.Source: §9.1 · p. 23

9.1.1 Phase 1: when ∥Q −Q⋆∥∞> 1/√1 −γ

  • The analysis presents an error decomposition and, following similar steps, obtains a recursive relation; it also sets a constant learning rate, η_t ≡ η, through a minimum-based choice.Source: §9.1.1 · pp. 23–24

9.1.2 Phase 2: when ∥Q −Q⋆∥∞≤1/√1 −γ

  • When the initial error is at most 1/√(1−γ), Phase 2 combines concentration bounds with a perturbed Bellman equation for its analysis.The auxiliary fixed point is a proof device and is not constructed by the algorithm, which lacks access to P.Source: §9.1.2 · p. 25

9.2 How many epochs are needed?

  • The epoch count first brings the error into the Phase 2 range; subsequent epochs yield the stated ε-accuracy guarantee.For targets above the phase boundary, the algorithm terminates in Phase 1.Source: §9.2 · p. 27
  • In Phase 2, the analysis establishes an ℓ∞ estimation error at most 3ε after the required number of epochs.The passage does not specify the epoch count in the supplied text.Source: §9.2 · p. 27

10 Discussion

The discussion reports sharper finite-sample analysis for classical asynchronous Q-learning and improved effective-horizon scaling with variance reduction. It identifies exact horizon scaling in the asynchronous setting as future work.

10 Discussion

  • The classical asynchronous bound scales as 1/(1−γ)^5, compared with the synchronous Q-learning scaling 1/(1−γ)^4 reported by Li et al. (2021a,b).The paper describes its asynchronous scaling as inferior and leaves its exact scaling for future work.Source: §10 · pp. 27–28
  • The discussion leaves open whether the analysis framework extends to model-free algorithms with more sophisticated exploration and general Markov-chain-based optimization.The paper notes a connection between asynchronous Q-learning and coordinate descent with Markov-chain-selected coordinates.Source: §10 · p. 28

A.1 Concentration of empirical distributions of Markov chains

  • The appendix frames empirical-distribution concentration for uniformly ergodic Markov chains as a result in which mixing time plays a role.It introduces the mixing time for a time-homogeneous, uniformly ergodic chain.Source: §A.1 · p. 28, A Preliminaries on Markov chains · p. 28

A.2 Connection between the mixing time and the cover time

The paper relates cover time to mixing time and minimum occupancy for uniformly ergodic chains, while noting that the relationship is not a general matching converse. A constructed example makes the upper bound nearly unimprovable up to logarithmic factors.

A.2 Connection between the mixing time and the cover time

  • The upper bound is nearly unimprovable up to logarithmic factors in general, but a matching converse is not available for arbitrary chains.The paper gives special examples where the bound is provably tight.Source: §A.2 · p. 30
  • The example makes states in one half harder to reach and makes all states lazy, linking low occupancy and slow mixing to increased cover time.The construction is designed so that cover time is proportional to both minimum occupancy’s reciprocal and mixing time.Source: §A.2 · p. 30

B Proofs of technical lemmas

The proofs use state-action visit times to establish concentration for transition samples, then apply visit-count bounds and induction to control the stated lemmas.

B.1 Proof of Lemma 1

  • At each state-action pair, transitions observed at successive visit times are independent with distribution P_s,a, enabling Hoeffding bounds that hold simultaneously across pairs and visit counts.The proof defines t_k(s, a) as the time of the k-th visit and applies a union bound over state-action pairs and K ≤ T.Source: §B.1 · pp. 32–33

B.2 Proof of Lemma 2 and Lemma 6

  • Lemma 2 and Lemma 6 use visit-count bounds to control the stated quantities uniformly over state-action pairs and time.For Lemma 6, the proof substitutes t/t_cover,all for tμ_min after t exceeds t_cover,all.Source: §B.2 · pp. 33–34

B.3 Proof of Lemma 3

  • Lemma 3 is proved by induction, using a threshold condition involving tμ_min and (1−γ)ε to establish the claim at each iteration.The proof combines the induction hypotheses with the stated inequalities and the definition of v_t.Source: §B.3 · p. 34

B.4 Proof of Lemma 4

The proofs bound error across timeframes by induction and use trajectory visits to control transition estimates and state-action coverage.

B.4 Proof of Lemma 4

  • Lemma 4 is established by induction over timeframes, bounding the error within each timeframe using visit counts and a non-increasing sequence of bounds.The proof uses per-interval state-action visit counts and combines the resulting bounds to establish inequality (55).Source: §B.4 · pp. 35–36

B.5 Proof of Lemma 7

  • The empirical transition rows average observed transitions at each state-action pair’s visit times, which are independent; Hoeffding bounds control the estimate across pairs.For N ≥ t_frame, the proof also invokes a lower bound on visits to each state-action pair.Source: §B.5 · p. 37

B.6 Proof of Lemma 5

  • The Lemma 5 proof bounds the probability that any state-action pair remains unvisited through t_cover,all using the Markov property and a union bound.It recursively bounds the probability of the relevant events before applying the union bound.Source: §B.6 · pp. 37–38
Loading 2006.03041v3…