Lemma 5 — the sequences U^k and L^k converge to x*
ProvedAsyncSA.Monotone.lemma5fixed-pointmonotone-operatorp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let satisfy Assumption 4 with unique fixed point (monotone, continuous, unique fixed point, and for all and all ). Fix and let be defined by , and
Then
Together with the bracketing for large , this is what turns the envelope argument of §5 into convergence of to .
Formalization Note Convergence is in (Fin n → ℝ with its product topology, equivalently the maximum norm). The statement holds for every , as in Lemma 4.
Preamble
import Mathlib import Definitions.Def_AsyncSA_Monotone_Model
Formal statement
namespace AsyncSA.Monotone
open Filter Topology
theorem lemma5 {n : ℕ} (F : (Fin n → ℝ) → Fin n → ℝ) (xstar : Fin n → ℝ) (r : ℝ)
(h4 : Assumption4 F xstar) (hr : 0 < r) :
Tendsto (Useq F xstar r) atTop (𝓝 xstar) ∧ Tendsto (Lseq F xstar r) atTop (𝓝 xstar) := by sorry
end AsyncSA.Monotone
Source
Tsitsiklis, Asynchronous Stochastic Approximation and Q-Learning, Machine Learning 16 (1994), p. 193, §5, Lemma 5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.