Theorem 3 — almost-sure convergence under a weighted maximum norm contraction
ProvedAsyncSA.Contraction.theorem3asynchronous-iterationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1q-learningstochastic-approximation
Consider the asynchronous stochastic approximation iteration of §2 under Assumptions 1, 2, and 3. Suppose Assumption 5 holds: there are a vector , a strictly positive weight vector , and such that
Then with probability one, including when different coordinates are updated at different times using outdated values.
This is the paper's contraction-based convergence theorem and the mission's goal.
Formalization Note The witnesses , , and are explicit binders, equivalent to their existence in Assumption 5. The paper implicitly treats as adapted to ; the statement includes adaptedness. No separate boundedness or Assumption 6 hypothesis is made.
Preamble
import Mathlib import Definitions.Def_AsyncSA_Contraction_Model
Formal statement
namespace AsyncSA.Contraction
open MeasureTheory Filter Topology
/-- Theorem 3, p. 189: almost-sure convergence to the contraction's fixed point. -/
theorem theorem3 {n : ℕ} {Ω : Type*} [m₀ : MeasurableSpace Ω]
(P : Measure Ω) [IsProbabilityMeasure P]
(𝓕 : Filtration ℕ m₀) (alg : Algorithm n Ω)
(xstar v : Fin n → ℝ) (β : ℝ)
(h1 : alg.Assumption1 P) (h2 : alg.Assumption2 P 𝓕)
(hx : alg.Adapted 𝓕) (h3 : alg.Assumption3 P)
(h5 : Assumption5 alg.F xstar v β) :
∀ᵐ ω ∂P, Tendsto (fun t => alg.x t ω) atTop (𝓝 xstar) := by sorry
end AsyncSA.Contraction
Source
Tsitsiklis, Asynchronous Stochastic Approximation and Q-Learning, Machine Learning 16 (1994), p. 189, §2, Theorem 3; proof pp. 195–196, §6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.