Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2 — under Assumptions 1–4, bounded asynchronous stochastic approximation iterates converge to x* w.p.1

Proved
AsyncSA.Monotone.theorem2

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

asynchronous-iterationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1q-learningstochastic-approximation

Consider the asynchronous stochastic approximation algorithm on Rn\mathbb R^nRn,

xi(t+1)=xi(t)+αi(t)(Fi(xi(t))−xi(t)+wi(t)),xi(t)=(x1(τ1i(t)),…,xn(τni(t))),x_i(t+1)=x_i(t)+\alpha_i(t)\bigl(F_i(x^i(t))-x_i(t)+w_i(t)\bigr),\qquad x^i(t)=\bigl(x_1(\tau^i_1(t)),\dots,x_n(\tau^i_n(t))\bigr),xi​(t+1)=xi​(t)+αi​(t)(Fi​(xi(t))−xi​(t)+wi​(t)),xi(t)=(x1​(τ1i​(t)),…,xn​(τni​(t))),

with stepsizes αi(t)∈[0,1]\alpha_i(t)\in[0,1]αi​(t)∈[0,1], noise wi(t)w_i(t)wi​(t) and delays 0≤τji(t)≤t0\le\tau^i_j(t)\le t0≤τji​(t)≤t, all random variables on a probability space (Ω,F,P)(\Omega,\mathcal F,P)(Ω,F,P) with an increasing sequence of σ-fields {F(t)}\{\mathcal F(t)\}{F(t)}. Suppose

  1. Assumption 1: τji(t)→∞\tau^i_j(t)\to\inftyτji​(t)→∞ w.p.1 for all i,ji,ji,j;
  2. Assumption 2: x(0)x(0)x(0) is F(0)\mathcal F(0)F(0)-measurable, wi(t)w_i(t)wi​(t) is F(t+1)\mathcal F(t+1)F(t+1)-measurable, αi(t),τji(t)\alpha_i(t),\tau^i_j(t)αi​(t),τji​(t) are F(t)\mathcal F(t)F(t)-measurable, E[wi(t)∣F(t)]=0E[w_i(t)\mid\mathcal F(t)]=0E[wi​(t)∣F(t)]=0, and E[wi2(t)∣F(t)]≤A+Bmax⁡jmax⁡τ≤t∣xj(τ)∣2E[w_i^2(t)\mid\mathcal F(t)]\le A+B\max_j\max_{\tau\le t}|x_j(\tau)|^2E[wi2​(t)∣F(t)]≤A+Bmaxj​maxτ≤t​∣xj​(τ)∣2 for deterministic A,BA,BA,B;
  3. Assumption 3: ∑tαi(t)=∞\sum_t\alpha_i(t)=\infty∑t​αi​(t)=∞ w.p.1 and ∑tαi2(t)≤C\sum_t\alpha_i^2(t)\le C∑t​αi2​(t)≤C w.p.1 for a deterministic CCC;
  4. Assumption 4: FFF is monotone (componentwise), continuous, has the unique fixed point x∗x^*x∗, and F(x)−re≤F(x−re)≤F(x+re)≤F(x)+reF(x)-re\le F(x-re)\le F(x+re)\le F(x)+reF(x)−re≤F(x−re)≤F(x+re)≤F(x)+re for every xxx and every r>0r>0r>0 (eee the vector of ones).

Suppose moreover that x(t)x(t)x(t) is bounded with probability 1. Then

lim⁡t→∞x(t)=x∗with probability 1.\lim_{t\to\infty}x(t)=x^*\qquad\text{with probability 1.}t→∞lim​x(t)=x∗with probability 1.

The theorem covers, for instance, Q-learning for undiscounted (stochastic shortest path) problems, where the relevant Bellman operator is monotone but not a contraction; boundedness of the iterates must then be established separately.

Formalization Note The conditional expectations are generalized (set-integral) conditional expectations, not Mathlib's condExp; series conditions are stated through partial sums; the update holds in the paper's unified form for every ttt (no explicit update sets TiT^iTi). The paper treats x(t)x(t)x(t) as a random variable determined by the history F(t)\mathcal F(t)F(t) and uses this implicitly; the statement assumes it explicitly (Adapted). The bound in "x(t)x(t)x(t) is bounded with probability 1" may depend on the sample path. x∗x^*x∗ is the same vector as the fixed point in Assumption 4. Convergence is in Rn\mathbb R^nRn (product topology, equivalently the maximum norm). Components are indexed by Fin n (0-based).

Preamble
import Mathlib
import Definitions.Def_AsyncSA_Monotone_Model
Formal statement
namespace AsyncSA.Monotone

open MeasureTheory Filter Topology

theorem theorem2 {n : ℕ} {Ω : Type*} [m0 : MeasurableSpace Ω] (P : Measure Ω)
    [IsProbabilityMeasure P] (𝓕 : Filtration ℕ m0) (alg : Algorithm n Ω) (xstar : Fin n → ℝ)
    (h1 : alg.Assumption1 P) (h2 : alg.Assumption2 P 𝓕) (hx : alg.Adapted 𝓕)
    (h3 : alg.Assumption3 P) (h4 : Assumption4 alg.F xstar)
    (hbdd : ∀ᵐ ω ∂P, ∃ M : ℝ, ∀ t j, |alg.x t ω j| ≤ M) :
    ∀ᵐ ω ∂P, Tendsto (fun t => alg.x t ω) atTop (𝓝 xstar) := by sorry

end AsyncSA.Monotone
Source
Tsitsiklis, Asynchronous Stochastic Approximation and Q-Learning, Machine Learning 16 (1994), p. 189, Theorem 2
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me