PaperlayerView exact revision on arXiv

Source-linked AI summary

Finite-Time Analysis of Asynchronous Stochastic Approximation and $Q$-Learning

Guannan Qu, Adam Wierman

arXiv:2002.00260v1math.OCcs.LG

TL;DR

Finite-time analyses for nonlinear contractive SA had focused on synchronous updates, leaving asynchronous single-trajectory behavior an open question. This paper analyzes weighted-infinity-norm contractive asynchronous SA and applies the result to Q-learning, where its bound matches the sharpest known synchronous scaling and improves prior asynchronous bounds.

  • Problem

    Earlier finite-time results for nonlinear infinity-norm contractive SA considered synchronous updates, leaving the convergence rate for asynchronous SA and Q-learning on a single trajectory open.

    Source: §1 · p. 2

  • Method

    The paper proves a finite-time convergence bound for asynchronous nonlinear SA with a weighted infinity-norm contraction using a recursive error decomposition.

    Source: §1 · p. 2

  • Results

    The asynchronous Q-learning bound matches the sharpest known synchronous scaling and improves the known asynchronous bound’s state-action-space dependence from at least cubic to square.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The recursive decomposition gives a more transparent account of how stochastic noise affects approximation error and leads to a sharper bound.

    Source: §1 · p. 2

    The analysis assumes every coordinate has positive conditional probability of being visited over a bounded lag, ensuring sufficiently frequent visits.

    Source: §2 · p. 5

Abstract

from arXiv · show

We consider a general asynchronous Stochastic Approximation (SA) scheme featuring a weighted infinity-norm contractive operator, and prove a bound on its finite-time convergence rate on a single trajectory. Additionally, we specialize the result to asynchronous $Q$-learning. The resulting bound matches the sharpest available bound for synchronous $Q$-learning, and improves over previous known bounds for asynchronous $Q$-learning.

1. Introduction

The paper addresses finite-time convergence for asynchronous stochastic approximation and Q-learning on a single trajectory, where earlier finite-time results for nonlinear contractive SA considered synchronous updates. It proves a bound for weighted-infinity-norm contractive SA and reports improved asynchronous Q-learning bounds alongside a distinct recursive proof approach.

1. Introduction

  • The paper asks for the finite-time convergence rate of asynchronous SA and Q-learning on a single trajectory, a setting not covered by earlier synchronous analyses of nonlinear contractive SA.The cited synchronous results concern SA with infinity-norm contractive or cone-contractive operators.Source: §1 · p. 2
  • The paper proves a finite-time convergence rate for asynchronous nonlinear SA schemes with a weighted infinity-norm contraction.The weighted norm is presented as covering discounted and undiscounted Q-learning settings.Source: §1 · p. 2
  • A rescaled linear step size can avoid the exponential blow-up in 1/(1−γ) reported in related Q-learning analyses.The authors describe this as consistent with related findings in other settings.Source: §1 · pp. 2–3
  • A recursive error decomposition replaces epoch-by-epoch control and makes the stochastic noise’s impact on approximation error more transparent.The authors state that this approach leads to a sharper bound and partly draws on drift analysis from ODE-based SA.Source: §1 · p. 2
  • The asynchronous Q-learning bound matches the sharpest known synchronous scaling and improves state-action-space dependence from at least cubic to square over previous asynchronous bounds.The comparison concerns finite-time bounds for classical Q-learning.Source: §1 · p. 3
  • Infinity-norm finite-time error bounds target accurate estimates of every Q-function entry and typically assume sufficient exploration, unlike regret bounds.The paper distinguishes these bounds from regret results, which address exploration and transient performance.Source: §1 · p. 3

2. Finite-Time Analysis of Stochastic Approximation

The section establishes finite-time convergence analysis for asynchronous stochastic approximation with a weighted infinity-norm contractive operator. Its guarantee relies on bounded noise and sufficient coordinate exploration.

2. Finite-Time Analysis of Stochastic Approximation

  • The analysis gives a finite-time convergence result for asynchronous stochastic approximation with a weighted infinity-norm contractive operator.The operator has a unique fixed point under the stated contraction assumption.Source: §2 · pp. 3–5
  • At each iteration, the scheme updates one selected coordinate using the operator value, the current estimate, and stochastic noise.The coordinate-selection process is adapted to a filtration, and the scheme captures asynchronous Q-learning.Source: §2 · pp. 3–4
  • The analysis assumes contraction, bounded martingale-difference noise, and sufficient exploration that gives every coordinate positive visitation probability.The exploration condition requires this probability over a window of length τ, conditional on the prior history.Source: §2 · pp. 4–5
  • The step-size constant h must scale with 1/(1−γ) and, asynchronously, with 1/σ.Here σ reflects the lower bound on coordinate visitation probability.Source: §2 · pp. 5–6

3. Application to Q-learning

The paper applies its asynchronous stochastic-approximation analysis to Q-learning in a discounted infinite-horizon MDP. The resulting bound matches the best-known synchronous dependence on 1/ε while improving the prior asynchronous dependence on the discount factor and state-action space size.

3. Application to Q-learning

  • The analysis treats finite-state, finite-action, discounted infinite-horizon MDPs and learns Q-values from a trajectory generated under a behavioral policy.The general stochastic-approximation result also applies to the undiscounted case, though this section focuses on the discounted setting.Source: §3 · p. 6
  • The application assumes bounded rewards and an ergodic state-action Markov chain with positive minimum stationary probability and finite mixing time.These conditions provide sufficient exploration for applying the asynchronous stochastic-approximation result.Source: §3 · p. 7
  • The Bellman operator is a γ-contraction, and the Q-learning updates satisfy the noise and boundedness conditions needed to apply the general result.The paper bounds the iterates by ¯r/(1−γ) and the update noise by 2¯r.Source: §3 · p. 7

T + ¯rtMIX

  • The asynchronous Q-learning bound matches the best-known synchronous dependence on 1/ε and improves prior asynchronous dependence on 1/(1−γ) and state-action space size.The prior asynchronous bound scales as (|S||A|)^5, while the paper describes its own square dependence on state-action space size as not optimal.Source: T + ¯rtMIX · p. 8

4. Convergence Proof

The proof controls finite-time error by decomposing the recursive update, bounding stochastic-noise contributions, and combining these bounds with induction. A shifted martingale-difference property and sufficient coordinate visitation support the noise bound.

4. Convergence Proof

  • The proof proceeds by recursively decomposing the error, bounding the noise contribution, then combining those bounds to prove Theorem 4.The decomposition makes the stochastic-noise contribution explicit.Source: §4 · pp. 8, 9, 12
  • The noise sequence is a shifted martingale difference: its conditional mean is zero given F_{t−τ}, rather than the standard F_t conditioning.The proof uses this property to apply a variant of the Azuma–Hoeffding bound.Source: §4 · pp. 9–10
  • With probability 1−δ, Lemma 12 bounds the accumulated noise term appearing in the recursive error decomposition.The term is a weighted sum of noise vectors, with coordinate i given by the corresponding entries of the matrix products and noise sequence.Source: §4 · pp. 9–10
  • Because the error sum includes random products not measurable under the needed conditioning, the proof removes that randomness using d_{ℓ,i} ≥ σ before applying concentration.Lemma 14 bounds the original quantity by a supremum with the random product removed; Lemma 13 then supplies the concentration bound.Source: §4 · p. 11
  • The proof applies union bounds over time and coordinates, then uses the error decomposition and an induction argument to control the error through the finite horizon.The final step combines the noise bound with Lemma 11 and conditions on the resulting high-probability event.Source: §4 · pp. 11–12

A.1. Proof of Proposition 2

The proof constructs a unit weighted-norm vector from a coordinate attaining the largest normalized entry, completing the proposition’s argument.

A.1. Proof of Proposition 2

  • The proof selects an index maximizing |a_{i*j}|/v_i, with ties broken arbitrarily.This index identifies the coordinate used to construct the vector.Source: §A.1 · p. 15
  • It defines x_j = v_j sign(a_{i*j}), using sign(z)=1 for z ≥ 0 and −1 otherwise.The construction aligns each coordinate with the selected row’s entries.Source: §A.1 · p. 15
  • The constructed vector satisfies ∥x∥_v = 1, which completes the proof.Source: §A.1 · p. 15

A.2. Proof of Proposition 3

The proof verifies the coordinate-visitation condition by lower-bounding each conditional selection probability using the stationary minimum mass and a total-variation bound.

A.2. Proof of Proposition 3

  • For each coordinate i, the conditional probability d_i is at least μ_i minus the total-variation distance between d and μ.Here d is the distribution of i_t conditioned on F_{t−τ}.Source: §A.2 · p. 15
  • The total-variation bound yields d_i ≥ μ_min − TV(d, μ) ≥ 1/2 μ_min for every i.Source: §A.2 · p. 15
  • This lower bound verifies Assumption 3.Source: §A.2 · p. 15

A.3. Proof of Proposition 5

The proof derives a linear growth bound for the operator from its contraction property, then uses induction to bound the iterates in the weighted norm.

A.3. Proof of Proposition 5

  • The contraction property gives ∥F(x)∥_v ≤ γ∥x∥_v + (1 + γ)∥x*∥_v.The proof identifies the additive constant as C = (1 + γ)∥x*∥_v for Assumption 1(b).Source: §A.3 · pp. 15–16
  • The proof establishes the iterate bound ∥x(t)∥_v ≤ x̄ by induction, starting from the all-zero initialization.Source: §A.3 · p. 16
  • The induction step uses the almost-sure noise bound |w(t)| ≤ w̄ from Assumption 2.The displayed step also invokes the relation involving γx̄, C, and w̄.Source: §A.3 · p. 16

A.4. Proof of Proposition 6

The proof proceeds by induction for part (a), then completes part (b) using the displayed intermediate expression.

A.4. Proof of Proposition 6

  • Part (a) starts from the all-zero initialization at t = 0 and uses induction to establish the statement at t + 1.The induction step bounds ∥Q(t + 1)∥∞ by the maximum of ∥Q(t)∥∞ and |Q_st,at(t + 1)|.Source: §A.4 · p. 16
  • For part (b), the proof proceeds from an intermediate expression involving |Q_st+1,a(t)| and |F_st,at(Q(t))|.The excerpt states that this completes the proof of part (b).Source: §A.4 · pp. 16–17

B.1. Proof of Lemma 8 (Error Decomposition)

These appendix subsections establish error and step-size bounds and prove auxiliary lemmas using concentration and sequence comparisons.

B.1. Proof of Lemma 8 (Error Decomposition)

  • The proof uses that F is a γ-contraction in ∥·∥v with fixed point x∗, then combines this with (15).This appears in the proof of the error decomposition lemma.Source: §B.1 · p. 17

B.2. Proof of Lemma 9 (Bounds on ∥ǫ(t)∥v and ∥φ(t)∥v)

  • The bounds proof uses ∥F(x(t − τ))∥v ≤ γ∥x(t − τ)∥v + C ≤ x̄ + C and bounds the indicator-minus-frequency term by 1.For part (b), it bounds the corresponding difference term by 2∥x(t) − x(t − τ)∥v.Source: §B.2 · p. 18

B.3. Proof of Lemma 10 (Step Sizes)

  • The step-size proof applies log(1 − x) ≤ −x and uses t0 ≥ 4h in a subsequent inequality.It also bounds αℓ by h over the stated range and uses σh − 1 > 1.Source: §B.3 · pp. 18–19

B.4. Proof of Lemma 13 (Azuma Hoeffding)

  • The Azuma-Hoeffding proof defines processes indexed by ℓ and applies a union bound over ℓ = 0, …, τ − 1 to obtain a probability-at-least-1 − δ bound.The final inequality uses Cauchy-Schwarz.Source: §B.4 · p. 19

B.5. Proof of Lemma 14

  • The Lemma 14 proof constructs a comparison sequence and inductively shows that pk and p̃k have the same sign and |pk| ≤ |p̃k| for k ≥ k0 + 1.It then invokes the upper bound on ∥ǫ(k0)∥v from Lemma 9(a).Source: §B.5 · pp. 19–20

B.6. Proof of Lemma 15

  • The Lemma 15 proof fixes i and uses dk,i ≥ σ almost surely while establishing its statement by induction.The excerpt also invokes ω ≤ 1 and a condition on h.Source: §B.6 · pp. 20–21
Loading 2002.00260v1…