Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Existence of the limiting hindsight optimum

Proved
Soar.hindsight_tendsto

by Shuze Chen · Sep 22, 2026 · Mathlib 0df444a (Lean v4.33.1)

benchmarkdynamicmatchinghindsightoptimumlimit

Standing conventions. Throughout, X\mathcal XX (demand weight vectors) and Y\mathcal YY (supply feature vectors) are measurable spaces, PPP and QQQ are probability measures on them, and the match quality function φ:X×Y→R\varphi : \mathcal X \times \mathcal Y \to \mathbb Rφ:X×Y→R is jointly measurable and bounded, ∣φ(x,y)∣≤C|\varphi(x,y)| \le C∣φ(x,y)∣≤C for all x,yx, yx,y. Expectations over nnn i.i.d. demand units and nnn independent i.i.d. supply units are integrals against the product measure P⊗n⊗Q⊗nP^{\otimes n} \otimes Q^{\otimes n}P⊗n⊗Q⊗n on Xn×Yn\mathcal X^n \times \mathcal Y^nXn×Yn. The hindsight optimum value is

UnH=1n E[sup⁡σ∈Sn∑t=1nφ(Xt,Yσ(t))],U^H_n = \frac{1}{n}\,\mathbb E\Bigl[\sup_{\sigma \in S_n} \sum_{t=1}^{n} \varphi\bigl(X_t, Y_{\sigma(t)}\bigr)\Bigr],UnH​=n1​E[σ∈Sn​sup​t=1∑n​φ(Xt​,Yσ(t)​)],

with SnS_nSn​ the symmetric group, and the limiting hindsight optimum is U∞=sup⁡n≥1UnHU_\infty = \sup_{n \ge 1} U^H_nU∞​=supn≥1​UnH​.

Then the sequence of hindsight optimum values converges to the limiting hindsight optimum, and is dominated by it:

lim⁡n→∞UnH=U∞,andUnH≤U∞for every n≥1.\lim_{n \to \infty} U^H_n = U_\infty, \qquad\text{and}\qquad U^H_n \le U_\infty \quad \text{for every } n \ge 1 .n→∞lim​UnH​=U∞​,andUnH​≤U∞​for every n≥1.

Equivalently, the hindsight regrets Regn(H-OPT)=U∞−UnH\mathrm{Reg}_n(\mathrm{H\text{-}OPT}) = U_\infty - U^H_nRegn​(H-OPT)=U∞​−UnH​ are nonnegative for n≥1n \ge 1n≥1 and tend to 000.

Role. This is the statement of Section 2 that the limiting hindsight optimum exists, "guaranteed by the boundedness and monotonicity of UnHU^H_nUnH​", together with the first inequality of the chain U∞≥UnH≥Un(π)U_\infty \ge U^H_n \ge U_n(\pi)U∞​≥UnH​≥Un​(π) 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 U∞U_\inftyU∞​ is defined as sup⁡n≥1UnH\sup_{n \ge 1} U^H_nsupn≥1​UnH​, the content is that the supremum is the limit, which follows from Lemma A.1 and boundedness. The restriction n≥1n \ge 1n≥1 in the second clause excludes the junk value U0H=0U^H_0 = 0U0H​=0.

Preamble
import Mathlib
import Definitions.Def_SoarModel

open MeasureTheory Filter Topology
Formal statement
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 Soar
Source
Y. Chen, Y. Kanoria, A. Kumar, W. Zhang, Feature-Based Dynamic Matching, SSRN working paper 4451799 (version of 27 May 2025; extended abstract in Proc. 24th ACM Conference on Economics and Computation, EC'23), https://ssrn.com/abstract=4451799, Section 2 and Appendix A (existence of U∞U_\inftyU∞​ and U∞≥UnHU_\infty \ge U^H_nU∞​≥UnH​)
Read-back

What the Lean code literally says, in plain math · claude-fable-5-1

Binders and hypotheses. Let XXX and YYY be arbitrary types with σ\sigmaσ-algebras; let PPP be a probability measure on XXX and QQQ a probability measure on YYY (hence X,YX,YX,Y nonempty and P,QP,QP,Q σ\sigmaσ-finite). Let φ:X×Y→R\varphi : X\times Y\to\mathbb Rφ:X×Y→R have (x,y)↦φ(x,y)(x,y)\mapsto\varphi(x,y)(x,y)↦φ(x,y) measurable for the product σ\sigmaσ-algebra. Let C∈RC\in\mathbb RC∈R with ∣φ(x,y)∣≤C|\varphi(x,y)|\le C∣φ(x,y)∣≤C for all x∈Xx\in Xx∈X, y∈Yy\in Yy∈Y (so C≥0C\ge0C≥0).

Definitions unfolded. For m∈Nm\in\mathbb Nm∈N let Sm(x,y):=sup⁡σ∈Sm∑t=0m−1φ(xt,yσ(t))S_m(x,y):=\sup_{\sigma\in\mathcal S_m}\sum_{t=0}^{m-1}\varphi(x_t,y_{\sigma(t)})Sm​(x,y):=supσ∈Sm​​∑t=0m−1​φ(xt​,yσ(t)​) for x∈Xmx\in X^mx∈Xm, y∈Ymy\in Y^my∈Ym (a maximum over the finite set Sm\mathcal S_mSm​; S0≡0S_0\equiv0S0​≡0); let Πm:=P⊗m⊗Q⊗m\Pi_m:=P^{\otimes m}\otimes Q^{\otimes m}Πm​:=P⊗m⊗Q⊗m on Xm×YmX^m\times Y^mXm×Ym; and let

Hm  :=  1m∫Xm×YmSm(x,y) Πm(dx,dy)H_m\;:=\;\frac1m\int_{X^m\times Y^m} S_m(x,y)\ \Pi_m(dx,dy)Hm​:=m1​∫Xm×Ym​Sm​(x,y) Πm​(dx,dy)

(Bochner integral, value 000 if not integrable; H0=0H_0=0H0​=0 by the convention a/0=0a/0=0a/0=0). Let

L  :=  sup⁡m∈NHm+1  =  sup⁡m≥1Hm,L\;:=\;\sup_{m\in\mathbb N}H_{m+1}\;=\;\sup_{m\ge1}H_m ,L:=m∈Nsup​Hm+1​=m≥1sup​Hm​,

a real supremum over the infinite family H1,H2,…H_1,H_2,\dotsH1​,H2​,… (H0H_0H0​ excluded), equal to 000 by convention if that family is not bounded above.

Conclusion. Both of the following hold:

  1. the sequence (Hn)n∈N(H_n)_{n\in\mathbb N}(Hn​)n∈N​ (indexed from n=0n=0n=0, so its first term is H0=0H_0=0H0​=0) converges in R\mathbb RR to LLL:
lim⁡n→∞Hn  =  L,\lim_{n\to\infty}H_n\;=\;L,n→∞lim​Hn​=L,

i.e. for every ε>0\varepsilon>0ε>0 there is NNN such that ∣Hn−L∣<ε|H_n-L|<\varepsilon∣Hn​−L∣<ε for all n≥Nn\ge Nn≥N; 2. for every natural number nnn with 1≤n1\le n1≤n,

Hn  ≤  L.H_n\;\le\;L .Hn​≤L.

Nothing is asserted about H0H_0H0​ in the second conjunct.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me