Theorem 2 — under Assumptions 1–4, bounded asynchronous stochastic approximation iterates converge to x* w.p.1
ProvedAsyncSA.Monotone.theorem2Consider the asynchronous stochastic approximation algorithm on ,
with stepsizes , noise and delays , all random variables on a probability space with an increasing sequence of σ-fields . Suppose
- Assumption 1: w.p.1 for all ;
- Assumption 2: is -measurable, is -measurable, are -measurable, , and for deterministic ;
- Assumption 3: w.p.1 and w.p.1 for a deterministic ;
- Assumption 4: is monotone (componentwise), continuous, has the unique fixed point , and for every and every ( the vector of ones).
Suppose moreover that is bounded with probability 1. Then
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 (no explicit update sets ). The paper treats as a random variable determined by the history and uses this implicitly; the statement assumes it explicitly (Adapted). The bound in " is bounded with probability 1" may depend on the sample path. is the same vector as the fixed point in Assumption 4. Convergence is in (product topology, equivalently the maximum norm). Components are indexed by Fin n (0-based).
import Mathlib import Definitions.Def_AsyncSA_Monotone_Model
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.