The hindsight benchmark is bounded
ProvedSoar.hindsight_abs_leStanding 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 every hindsight optimum value and the limiting hindsight optimum are bounded by the same constant:
Role. The paper assumes bounded precisely so that and are finite and the regret is well defined; this is the statement "with bounded quality function , are trivially bounded, then by monotone convergence is also bounded" of Appendix A.
Formalization Note The bound for holds because is the junk value and (a probability measure on forces nonempty, so some exists). The bound on needs no monotonicity: a supremum of a sequence bounded in absolute value by is bounded by .
import Mathlib import Definitions.Def_SoarModel open MeasureTheory
namespace Soar
theorem hindsight_abs_le {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) :
(∀ n : ℕ, |SoarHindsight P Q φ n| ≤ C) ∧ |SoarLimit P Q φ| ≤ C := 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, each equipped with a -algebra. Let be a measure on and a measure on , and assume both are probability measures (, ). Because a probability measure cannot live on an empty type, this forces and ; it also makes and finite, hence -finite, which is the only property the definitions below require of them. Let be a function such that is measurable from the product -algebra on to the Borel -algebra on . Let be a real number and assume the bound
Since and are nonempty this hypothesis can only hold when , so the degenerate case is excluded by the hypotheses themselves.
Definitions unfolded. For , , , define the hindsight sum
This is a real supremum over the finite nonempty set , hence an honest maximum (no junk value can arise); for the sum is empty and . Let
be the product measure on ( independent copies of times independent copies of ); for each factor is the Dirac mass at the unique empty tuple, so is a unit point mass. Under the hypotheses is a probability measure. The normalized hindsight value at horizon is
with the Bochner-integral convention (value if the integrand is not integrable) and the division convention ; in particular regardless of . Finally the limit value is
a real supremum over the infinite family (the term is not included); if that family were not bounded above, would be by convention.
Conclusion. Both of the following hold simultaneously:
- for every natural number , including (where the claim reads ),
- the limit value satisfies