Lemma 2 — uniform smallness of late noise tails
ProvedAsyncSA.Contraction.lemma2martingalep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-approximation
Under the scalar filtration, step-size, and conditional-noise conditions of Lemma 1, define the zero-start tail by and for . Almost surely, for every , there is a time such that
The uniformity in both the starting and ending times lets later arguments restart the noise recursion after delayed information has become sufficiently recent.
Formalization Note On p. 192 the paper states this for the rescaled noise . The preceding page establishes that the rescaled process satisfies Lemma 1's conditions; this statement records the same conclusion for any scalar process satisfying those conditions. The tail is zero before its start time as well.
Preamble
import Mathlib import Definitions.Def_AsyncSA_Contraction_Model
Formal statement
namespace AsyncSA.Contraction
open MeasureTheory Filter Topology
/-- Lemma 2, p. 192, for any scalar noise process satisfying Lemma 1's conditions. -/
theorem lemma2 {Ω : Type*} [m₀ : MeasurableSpace Ω]
(P : Measure Ω) [IsProbabilityMeasure P]
(𝓕 : Filtration ℕ m₀) (α w B : ℕ → Ω → ℝ) (C : ℝ)
(hαmeas : ∀ t, Measurable[𝓕 t] (α t))
(hwmeas : ∀ t, Measurable[𝓕 (t + 1)] (w t))
(hBmeas : ∀ t, Measurable[𝓕 t] (B t))
(hmean : ∀ t, CondMeanZero m₀ (𝓕 t) P (w t))
(hsq : ∀ t, CondSqLe m₀ (𝓕 t) P (w t) (B t))
(hαmem : ∀ᵐ ω ∂P, ∀ t, α t ω ∈ Set.Icc (0 : ℝ) 1)
(hdiv : ∀ᵐ ω ∂P,
Tendsto (fun T => ∑ t ∈ Finset.range T, α t ω) atTop atTop)
(hsum : ∀ᵐ ω ∂P,
∀ T, ∑ t ∈ Finset.range T, α t ω ^ 2 ≤ C)
(hBbound : ∀ᵐ ω ∂P, ∃ K : ℝ, ∀ t, |B t ω| ≤ K) :
∀ᵐ ω ∂P, ∀ δ : ℝ, 0 < δ →
∃ T : ℕ, ∀ t₀ t : ℕ, T ≤ t₀ → t₀ ≤ t →
|tailW (fun s => α s ω) (fun s => w s ω) t₀ t| ≤ δ := by sorry
end AsyncSA.Contraction
Source
Tsitsiklis, Asynchronous Stochastic Approximation and Q-Learning, Machine Learning 16 (1994), pp. 191–192, §4, rescaled noise and Lemma 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.