Existence of the limiting hindsight optimum
ProvedSoar.hindsight_tendstoStanding conventions. Throughout, (demand weight vectors) and (supply feature vectors) are measurable spaces, and are probability measures on them, and the match quality function is jointly measurable and bounded, for all . Expectations over i.i.d. demand units and independent i.i.d. supply units are integrals against the product measure on . The hindsight optimum value is
with the symmetric group, and the limiting hindsight optimum is .
Then the sequence of hindsight optimum values converges to the limiting hindsight optimum, and is dominated by it:
Equivalently, the hindsight regrets are nonnegative for and tend to .
Role. This is the statement of Section 2 that the limiting hindsight optimum exists, "guaranteed by the boundedness and monotonicity of ", together with the first inequality of the chain that Appendix A is devoted to. It is the input to Corollary 1 (vanishing regret of SOAR) and to the scaling corollaries.
Formalization Note Since is defined as , the content is that the supremum is the limit, which follows from Lemma A.1 and boundedness. The restriction in the second clause excludes the junk value .
import Mathlib import Definitions.Def_SoarModel open MeasureTheory Filter Topology
namespace Soar
theorem hindsight_tendsto {X Y : Type*} [MeasurableSpace X] [MeasurableSpace Y]
(P : Measure X) (Q : Measure Y) [IsProbabilityMeasure P] [IsProbabilityMeasure Q]
(φ : X → Y → ℝ) (hφ : Measurable (Function.uncurry φ)) (C : ℝ) (hC : SoarBounded φ C) :
Tendsto (fun n : ℕ => SoarHindsight P Q φ n) atTop (𝓝 (SoarLimit P Q φ)) ∧
∀ n : ℕ, 1 ≤ n → SoarHindsight P Q φ n ≤ SoarLimit P Q φ := by
sorry
end SoarRead-back
What the Lean code literally says, in plain math · claude-fable-5-1
Binders and hypotheses. Let and be arbitrary types with -algebras; let be a probability measure on and a probability measure on (hence nonempty and -finite). Let have measurable for the product -algebra. Let with for all , (so ).
Definitions unfolded. For let for , (a maximum over the finite set ; ); let on ; and let
(Bochner integral, value if not integrable; by the convention ). Let
a real supremum over the infinite family ( excluded), equal to by convention if that family is not bounded above.
Conclusion. Both of the following hold:
- the sequence (indexed from , so its first term is ) converges in to :
i.e. for every there is such that for all ; 2. for every natural number with ,
Nothing is asserted about in the second conjunct.