Theorem 1 — almost-sure boundedness under weighted linear growth
ProvedAsyncSA.Contraction.theorem1asynchronous-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 the map satisfies Assumption 6: for some positive weight vector , , and ,
Then, with probability one, there is a finite bound on every coordinate at every time . The bound may depend on the sample path.
This boundedness theorem is the intermediate result used in the proof of contraction-based convergence.
Formalization Note The paper uses adaptedness of implicitly, through measurability of its running maximum; it is explicit here. Conditional moments are generalized measurable-set statements. The uniform squared-step-size bound is chosen before the almost-sure quantifier.
Preamble
import Mathlib import Definitions.Def_AsyncSA_Contraction_Model
Formal statement
namespace AsyncSA.Contraction
open MeasureTheory Filter Topology
/-- Theorem 1, p. 189: sample-path boundedness under Assumption 6. -/
theorem theorem1 {n : ℕ} {Ω : Type*} [m₀ : MeasurableSpace Ω]
(P : Measure Ω) [IsProbabilityMeasure P]
(𝓕 : Filtration ℕ m₀) (alg : Algorithm n Ω)
(h1 : alg.Assumption1 P) (h2 : alg.Assumption2 P 𝓕)
(hx : alg.Adapted 𝓕) (h3 : alg.Assumption3 P)
(h6 : Assumption6 alg.F) :
∀ᵐ ω ∂P, ∃ M : ℝ, ∀ t j, |alg.x t ω j| ≤ M := by sorry
end AsyncSA.Contraction
Source
Tsitsiklis, Asynchronous Stochastic Approximation and Q-Learning, Machine Learning 16 (1994), p. 189, §2, Theorem 1; proof pp. 190–192, §4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.