Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Variance reduction for differentiable estimators (Theorem 9)

Disproved
TreatmentLocality.differentiable_estimator_variance_dominance

by Shuze Chen · Aug 21, 2026 · Mathlib c5ea003 (Lean v4.30.0)

a-b-testingcausal-inferencemarkov-decision-processstatisticsvariance-reduction

Theorem 9 of arXiv:2407.19618. Consider an SST model MMM run under the mixed policy π1/2\pi^{1/2}π1/2, with the experiment tuple chain uniformly ergodic with stationary law ν\nuν and rewards square-integrable. Let Δ^Γ=f(KΓt,KΓc,RΓt,RΓc)\hat\Delta_\Gamma = f(K^t_\Gamma, K^c_\Gamma, R^t_\Gamma, R^c_\Gamma)Δ^Γ​=f(KΓt​,KΓc​,RΓt​,RΓc​), Γ∈{AB,IS}\Gamma \in \{AB, IS\}Γ∈{AB,IS}, be any differentiable estimator (fff Fréchet-differentiable at the mean statistics). Then: (1) same asymptotic bias — the mean statistics of the two schemes coincide, so both estimators converge around the same limit value f(ℓ)f(\ell)f(ℓ); (2) asymptotic normality — for each scheme Γ\GammaΓ, T(Δ^Γ−f(ℓ))→dN(0,σΓ2)\sqrt{T}(\hat\Delta_\Gamma - f(\ell)) \xrightarrow{d} N(0, \sigma_\Gamma^2)T​(Δ^Γ​−f(ℓ))d​N(0,σΓ2​) with σΓ2=∇f⊤ΣΓ∇f\sigma_\Gamma^2 = \nabla f^\top \Sigma_\Gamma \nabla fσΓ2​=∇f⊤ΣΓ​∇f the asymptotic variance of the linearized observable; (3) decomposition and dominance — writing ΣΓ=ΣΓinst+ΣΓcov\Sigma_\Gamma = \Sigma_\Gamma^{inst} + \Sigma_\Gamma^{cov}ΣΓ​=ΣΓinst​+ΣΓcov​ (instantaneous plus temporal parts): the temporal parts are equal, ΣIScov=ΣABcov\Sigma^{cov}_{IS} = \Sigma^{cov}_{AB}ΣIScov​=ΣABcov​; the instantaneous parts agree on every row and column associated with the crucial state s1s^1s1 (the heterogeneous part Σhet\Sigma^{het}Σhet is unchanged — variance at the treated state cannot be reduced); the difference ΣABinst−ΣISinst\Sigma^{inst}_{AB} - \Sigma^{inst}_{IS}ΣABinst​−ΣISinst​ is positive semidefinite (the homogeneous part Σhom\Sigma^{hom}Σhom is reduced); and consequently ΣIS⪯ΣAB\Sigma_{IS} \preceq \Sigma_{AB}ΣIS​⪯ΣAB​ in the Loewner order. Information sharing never increases the asymptotic variance of any differentiable estimator, and the entire reduction occurs away from the treated state — exactly the content of Theorem 9 and its proof in Appendix EC.3.2.


RETIRED (deprecated by the mission captain). This statement is not provable as written, and is false for a suitable estimator. TendstoInDistribution carries an almost-everywhere measurability obligation on the estimator composed with the empirical statistics, and Frechet-differentiability at the single point where the derivative is taken does not supply it: g(v)=∥v−μ∥21A(v)g(v)=\|v-\mu\|^2\mathbf 1_A(v)g(v)=∥v−μ∥21A​(v) with AAA non-measurable is differentiable at μ\muμ with derivative 000 and is measurable nowhere else, while the empirical statistics have a non-atomic law whenever the rewards do. The source is not at fault: arXiv:2407.19618 Definition 1 speaks of differentiable estimators and Appendix EC.3.2 uses "fff is differentiable (and thus continuous)", so the intended estimator class is continuous, hence measurable; the hypothesis was lost in formalization. Replaced by TreatmentLocality.differentiable_estimator_variance_dominance_of_measurable, which is identical apart from the added measurability hypothesis.

Preamble
import Definitions.Def_TreatmentLocalityEstimator
import Definitions.Def_MarkovErgodicity
import Mathlib.LinearAlgebra.Matrix.PosDef

open MeasureTheory ProbabilityTheory Filter TreatmentLocality
open scoped NNReal ENNReal Topology
Formal statement
theorem TreatmentLocality.differentiable_estimator_variance_dominance {S : Type*} [Fintype S] [DecidableEq S]
    [MeasurableSpace S] [MeasurableSingletonClass S]
    (M : Model S) (ν : Measure (Step S)) [IsProbabilityMeasure ν]
    (hinv : Kernel.Invariant (expKernel M) ν)
    (huni : MarkovChainCLT.UniformlyErgodic (expKernel M) ν)
    (hL2 : M.RewardL2)
    (f : EstInput S → ℝ) (f' : EstInput S →L[ℝ] ℝ)
    (hf : HasFDerivAt f f' (meanObs M .AB ν)) :
    meanObs M .AB ν = meanObs M .IS ν
    ∧ (∀ Γ : Scheme, TendstoInDistribution
        (fun (T : ℕ) (ω : ℕ → Step S) =>
          Real.sqrt T * (f (empAvg M Γ T ω) - f (meanObs M .AB ν)))
        atTop (id : ℝ → ℝ) (fun _ => MarkovChainCLT.chainMeasure (expKernel M) ν)
        (gaussianReal 0
          (MarkovChainCLT.asymptoticVariance (expKernel M) ν
            (fun z => f' (estObs M Γ z))).toNNReal))
    ∧ lagCovMatrix M .AB ν = lagCovMatrix M .IS ν
    ∧ (∀ p q : EstIdx S, idxState p = M.crucial ∨ idxState q = M.crucial →
        instCovMatrix M .AB ν p q = instCovMatrix M .IS ν p q)
    ∧ Matrix.PosSemidef (instCovMatrix M .AB ν - instCovMatrix M .IS ν)
    ∧ Matrix.PosSemidef (asymCovMatrix M .AB ν - asymCovMatrix M .IS ν) := by sorry
Source
Chen, Simchi-Levi, Wang, Improving the Estimation of Lifetime Effects in A/B Testing via Treatment Locality, https://arxiv.org/abs/2407.19618, §6.2, Theorem 9, with the decomposition computed in Appendix EC.3.2
Read-back

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

Read-back: TreatmentLocality.differentiable_estimator_variance_dominance

Setting and fixed data. Let SSS be a finite type with decidable equality, equipped with a measurable space structure in which every singleton is measurable. A model MMM over SSS consists of: a distinguished "crucial" state s⋆∈Ss^\star \in Ss⋆∈S; a transition law tr(s,a)\mathrm{tr}(s,a)tr(s,a), a probability mass function on SSS, for each state sss and each Boolean action aaa; a reward law rw(s,a)\mathrm{rw}(s,a)rw(s,a), a probability measure on R\mathbb{R}R, for each (s,a)(s,a)(s,a); and a discount factor γ∈[0,1)\gamma \in [0,1)γ∈[0,1) (the discount plays no role in this statement). The Boolean policy action is act(a,s)=a∧[s=s⋆]\mathrm{act}(a,s) = a \wedge [s = s^\star]act(a,s)=a∧[s=s⋆]: action true is taken only when the arm bit aaa is true and the current state is the crucial state; in every other case the action is false.

A step is a tuple z=(state(z),arm(z),next(z),rwd(z))∈S×{true,false}×S×Rz = (\mathrm{state}(z), \mathrm{arm}(z), \mathrm{next}(z), \mathrm{rwd}(z)) \in S \times \{\mathrm{true},\mathrm{false}\} \times S \times \mathbb{R}z=(state(z),arm(z),next(z),rwd(z))∈S×{true,false}×S×R. The step law at sss, SL(s)\mathrm{SL}(s)SL(s), is the probability measure on {true,false}×S×R\{\mathrm{true},\mathrm{false}\}\times S\times\mathbb{R}{true,false}×S×R given by

SL(s)  =  12(δtrue⊗tr(s,act(true,s))⊗rw(s,act(true,s))  +  δfalse⊗tr(s,act(false,s))⊗rw(s,act(false,s))),\mathrm{SL}(s) \;=\; \tfrac12\Big(\delta_{\mathrm{true}} \otimes \mathrm{tr}\big(s,\mathrm{act}(\mathrm{true},s)\big) \otimes \mathrm{rw}\big(s,\mathrm{act}(\mathrm{true},s)\big) \;+\; \delta_{\mathrm{false}} \otimes \mathrm{tr}\big(s,\mathrm{act}(\mathrm{false},s)\big) \otimes \mathrm{rw}\big(s,\mathrm{act}(\mathrm{false},s)\big)\Big),SL(s)=21​(δtrue​⊗tr(s,act(true,s))⊗rw(s,act(true,s))+δfalse​⊗tr(s,act(false,s))⊗rw(s,act(false,s))),

i.e. the arm is uniform on {true,false}\{\mathrm{true},\mathrm{false}\}{true,false}, and given the arm aaa, the next state and the reward are drawn independently from tr(s,act(a,s))\mathrm{tr}(s,\mathrm{act}(a,s))tr(s,act(a,s)) and rw(s,act(a,s))\mathrm{rw}(s,\mathrm{act}(a,s))rw(s,act(a,s)) respectively. The experiment kernel PMP_MPM​ is the Markov kernel on steps that maps a step zzz to the law of (next(z), A′,S′,R′)\big(\mathrm{next}(z),\, A', S', R'\big)(next(z),A′,S′,R′) with (A′,S′,R′)∼SL(next(z))(A',S',R') \sim \mathrm{SL}(\mathrm{next}(z))(A′,S′,R′)∼SL(next(z)): the new step's first coordinate is deterministically the old step's next state.

Hypotheses. The theorem takes:

  • a probability measure ν\nuν on steps;
  • hinvh_{\mathrm{inv}}hinv​: ν\nuν is invariant for PMP_MPM​ (pushing ν\nuν through PMP_MPM​ returns ν\nuν);
  • hunih_{\mathrm{uni}}huni​: PMP_MPM​ is uniformly ergodic toward ν\nuν in the following exact sense: there exist real constants R≥0R \ge 0R≥0 and t∈[0,1)t \in [0,1)t∈[0,1) such that for every step zzz and every n≥1n \ge 1n≥1,
dTV(PMn(z,⋅), ν)  ≤  R tn,d_{\mathrm{TV}}\big(P_M^n(z,\cdot),\,\nu\big) \;\le\; R\, t^n,dTV​(PMn​(z,⋅),ν)≤Rtn,

where PMnP_M^nPMn​ is the nnn-fold kernel iterate (PM0=P_M^0 = PM0​= identity/Dirac kernel) and dTV(μ,ν)=sup⁡{ ∣μ(A)−ν(A)∣:A measurable }d_{\mathrm{TV}}(\mu,\nu) = \sup\{\,|\mu(A)-\nu(A)| : A \text{ measurable}\,\}dTV​(μ,ν)=sup{∣μ(A)−ν(A)∣:A measurable} (supremum of real numbers, taken as a set-supremum; measures are compared through their real-valued evaluations). Note this hypothesis does not itself restate invariance; that is supplied separately by hinvh_{\mathrm{inv}}hinv​.

  • hL2h_{L^2}hL2​: for every state sss and Boolean aaa, the identity function x↦xx \mapsto xx↦x is in L2L^2L2 of rw(s,a)\mathrm{rw}(s,a)rw(s,a) (rewards have finite second moments);
  • a function f:E→Rf : \mathcal{E} \to \mathbb{R}f:E→R on the estimator-input space E\mathcal{E}E, where an element v∈Ev \in \mathcal{E}v∈E assigns to each Boolean arm aaa a pair (va(1):S×S→R,  va(2):S→R)\big(v_a^{(1)} : S\times S \to \mathbb{R},\; v_a^{(2)} : S \to \mathbb{R}\big)(va(1)​:S×S→R,va(2)​:S→R) (a matrix and a vector per arm);
  • a continuous linear map f′:E→Rf' : \mathcal{E} \to \mathbb{R}f′:E→R;
  • hfh_fhf​: fff is Fréchet-differentiable at the single point O‾AB\overline{O}^{\mathrm{AB}}OAB (defined below) with derivative f′f'f′. This is the only differentiability assumption in the statement: differentiability is asserted only at the AB-scheme population mean, not on a neighborhood, and not at the IS-scheme mean (though by Part 1 the two means are asserted equal).

Schemes and estimator observables. There are exactly two schemes, AB\mathrm{AB}AB and IS\mathrm{IS}IS. The scheme weight of arm aaa at step zzz is

wAB(a,z)=2⋅1[arm(z)=a],wIS(a,z)={2⋅1[arm(z)=a]if state(z)=s⋆,1otherwise.w^{\mathrm{AB}}(a,z) = 2\cdot\mathbf{1}[\mathrm{arm}(z)=a], \qquad w^{\mathrm{IS}}(a,z) = \begin{cases} 2\cdot\mathbf{1}[\mathrm{arm}(z)=a] & \text{if } \mathrm{state}(z)=s^\star,\\ 1 & \text{otherwise.}\end{cases}wAB(a,z)=2⋅1[arm(z)=a],wIS(a,z)={2⋅1[arm(z)=a]1​if state(z)=s⋆,otherwise.​

The observable OΓ(z)∈EO^\Gamma(z) \in \mathcal{E}OΓ(z)∈E of scheme Γ\GammaΓ at step zzz has, for each arm aaa,

OΓ(z)a(1)(i,j)=wΓ(a,z)⋅1[state(z)=i∧next(z)=j],OΓ(z)a(2)(i)=wΓ(a,z)⋅1[state(z)=i]⋅rwd(z).O^\Gamma(z)_a^{(1)}(i,j) = w^\Gamma(a,z)\cdot \mathbf{1}[\mathrm{state}(z)=i \wedge \mathrm{next}(z)=j], \qquad O^\Gamma(z)_a^{(2)}(i) = w^\Gamma(a,z)\cdot \mathbf{1}[\mathrm{state}(z)=i]\cdot \mathrm{rwd}(z).OΓ(z)a(1)​(i,j)=wΓ(a,z)⋅1[state(z)=i∧next(z)=j],OΓ(z)a(2)​(i)=wΓ(a,z)⋅1[state(z)=i]⋅rwd(z).

The population mean O‾Γ∈E\overline{O}^\Gamma \in \mathcal{E}OΓ∈E is the entrywise Bochner integral of OΓO^\GammaOΓ against ν\nuν. The empirical average O^TΓ(ω)∈E\widehat{O}^\Gamma_T(\omega) \in \mathcal{E}OTΓ​(ω)∈E, for T∈NT \in \mathbb{N}T∈N and a trajectory ω:N→Steps\omega : \mathbb{N} \to \text{Steps}ω:N→Steps, is entrywise 1T∑i=0T−1(entry of OΓ(ωi+1))\frac1T \sum_{i=0}^{T-1} (\text{entry of } O^\Gamma(\omega_{i+1}))T1​∑i=0T−1​(entry of OΓ(ωi+1​)) — the average uses coordinates ω1,…,ωT\omega_1,\dots,\omega_Tω1​,…,ωT​, skipping ω0\omega_0ω0​; for T=0T=0T=0 each entry is 000 (the reciprocal 0−1=00^{-1}=00−1=0 convention).

Coordinates of E\mathcal{E}E are indexed by I={true,false}×((S×S)⊔S)\mathcal{I} = \{\mathrm{true},\mathrm{false}\} \times \big((S\times S) \sqcup S\big)I={true,false}×((S×S)⊔S): index p=(a,(i,j))p = (a, (i,j))p=(a,(i,j)) picks the matrix entry va(1)(i,j)v_a^{(1)}(i,j)va(1)​(i,j) and p=(a,i)p = (a, i)p=(a,i) picks the vector entry va(2)(i)v_a^{(2)}(i)va(2)​(i); the index state σ(p)\sigma(p)σ(p) is iii in the first case (the first component of the pair) and iii in the second. Write gpΓ(z)=g^\Gamma_p(z) = gpΓ​(z)= the ppp-th coordinate of OΓ(z)O^\Gamma(z)OΓ(z).

Covariance machinery. For real-valued functions g,hg,hg,h on steps, the lag-kkk covariance is

Ck(g,h)  =  ∫(g(z)−∫g dν)(∫h d(PMk(z,⋅))−∫h dν) dν(z).C_k(g,h) \;=\; \int \Big(g(z) - \textstyle\int g\, d\nu\Big)\Big(\textstyle\int h\, d\big(P_M^k(z,\cdot)\big) - \int h\, d\nu\Big)\, d\nu(z).Ck​(g,h)=∫(g(z)−∫gdν)(∫hd(PMk​(z,⋅))−∫hdν)dν(z).

The matrices over I×I\mathcal{I}\times\mathcal{I}I×I are:

ΣpqΓ=C0(gpΓ,gqΓ)("instantaneous"),ΛpqΓ=∑k=1∞Ck(gpΓ,gqΓ)+∑k=1∞Ck(gqΓ,gpΓ)("lag"),\Sigma^\Gamma_{p q} = C_0\big(g^\Gamma_p, g^\Gamma_q\big) \quad (\text{"instantaneous"}), \qquad \Lambda^\Gamma_{p q} = \sum_{k=1}^{\infty} C_k\big(g^\Gamma_p, g^\Gamma_q\big) + \sum_{k=1}^{\infty} C_k\big(g^\Gamma_q, g^\Gamma_p\big) \quad (\text{"lag"}),ΣpqΓ​=C0​(gpΓ​,gqΓ​)("instantaneous"),ΛpqΓ​=k=1∑∞​Ck​(gpΓ​,gqΓ​)+k=1∑∞​Ck​(gqΓ​,gpΓ​)("lag"), ΞΓ=ΣΓ+ΛΓ("asymptotic").\Xi^\Gamma = \Sigma^\Gamma + \Lambda^\Gamma \quad (\text{"asymptotic"}).ΞΓ=ΣΓ+ΛΓ("asymptotic").

The infinite sums are Lean tsums: if a series is not summable, its value is the junk value 000; no summability is hypothesized. Likewise the scalar asymptotic variance of a function ggg is V(g)=C0(g,g)+∑k≥1Ck(g,g)+∑k≥1Ck(g,g)V(g) = C_0(g,g) + \sum_{k\ge1} C_k(g,g) + \sum_{k\ge1} C_k(g,g)V(g)=C0​(g,g)+∑k≥1​Ck​(g,g)+∑k≥1​Ck​(g,g) (the two tail sums both appear, so the tails are counted twice).

Conclusion. Under all the above hypotheses, the theorem asserts the conjunction of six statements:

  1. Mean equality. O‾AB=O‾IS\overline{O}^{\mathrm{AB}} = \overline{O}^{\mathrm{IS}}OAB=OIS as elements of E\mathcal{E}E (i.e. equality of every matrix and vector entry, for both arms).

  2. CLT for the plug-in functional, for both schemes. For every scheme Γ∈{AB,IS}\Gamma \in \{\mathrm{AB}, \mathrm{IS}\}Γ∈{AB,IS} (this part, and only the parts explicitly marked, quantifies over schemes): the sequence of random variables on the path space N→Steps\mathbb{N}\to\text{Steps}N→Steps, each carrying the same measure — the law of the Markov chain with kernel PMP_MPM​ and initial distribution ν\nuν (coordinate 000 has law ν\nuν) —

ω  ⟼  T (f(O^TΓ(ω))−f(O‾AB))\omega \;\longmapsto\; \sqrt{T}\,\Big(f\big(\widehat{O}^\Gamma_T(\omega)\big) - f\big(\overline{O}^{\mathrm{AB}}\big)\Big)ω⟼T​(f(OTΓ​(ω))−f(OAB))

converges in distribution, as T→∞T \to \inftyT→∞, to the real Gaussian law N(0, vΓ)\mathcal{N}\big(0,\, v_\Gamma\big)N(0,vΓ​) with variance

vΓ  =  max⁡(0,  V(z↦f′(OΓ(z)))),v_\Gamma \;=\; \max\Big(0,\; V\big(z \mapsto f'(O^\Gamma(z))\big)\Big),vΓ​=max(0,V(z↦f′(OΓ(z)))),

i.e. the asymptotic variance VVV of the scalar functional z↦f′(OΓ(z))z \mapsto f'(O^\Gamma(z))z↦f′(OΓ(z)), clamped to 000 if negative (a toNNReal coercion); vΓ=0v_\Gamma = 0vΓ​=0 yields the Dirac mass at 000. Note carefully: the centering constant is f(O‾AB)f(\overline{O}^{\mathrm{AB}})f(OAB) — the AB mean — for both schemes, and the derivative f′f'f′ used inside the variance is the one from hypothesis hfh_fhf​, taken at the AB mean, even when Γ=IS\Gamma = \mathrm{IS}Γ=IS.

  1. Lag-covariance equality. ΛAB=ΛIS\Lambda^{\mathrm{AB}} = \Lambda^{\mathrm{IS}}ΛAB=ΛIS as full matrices — equality at every pair of indices (p,q)∈I×I(p,q) \in \mathcal{I}\times\mathcal{I}(p,q)∈I×I, with no restriction to crucial-state indices.

  2. Instantaneous-covariance equality at crucial indices. For all indices p,q∈Ip, q \in \mathcal{I}p,q∈I: if σ(p)=s⋆\sigma(p) = s^\starσ(p)=s⋆ or σ(q)=s⋆\sigma(q) = s^\starσ(q)=s⋆ (at least one of the two indices has its state component equal to the crucial state), then ΣpqAB=ΣpqIS\Sigma^{\mathrm{AB}}_{pq} = \Sigma^{\mathrm{IS}}_{pq}ΣpqAB​=ΣpqIS​. Nothing is asserted for pairs where neither index touches the crucial state.

  3. Instantaneous dominance. The matrix ΣAB−ΣIS\Sigma^{\mathrm{AB}} - \Sigma^{\mathrm{IS}}ΣAB−ΣIS is positive semidefinite in the Mathlib sense, which asserts two things: the matrix is symmetric (Hermitian over R\mathbb{R}R), and x⊤(ΣAB−ΣIS)x≥0x^\top(\Sigma^{\mathrm{AB}} - \Sigma^{\mathrm{IS}})x \ge 0x⊤(ΣAB−ΣIS)x≥0 for every vector x∈RIx \in \mathbb{R}^{\mathcal{I}}x∈RI.

  4. Asymptotic dominance. Likewise, ΞAB−ΞIS\Xi^{\mathrm{AB}} - \Xi^{\mathrm{IS}}ΞAB−ΞIS (the difference of the asymptotic covariance matrices ΣΓ+ΛΓ\Sigma^\Gamma + \Lambda^\GammaΣΓ+ΛΓ) is symmetric and positive semidefinite.

Parts 1, 3, 4, 5, 6 are statements about the two concrete schemes AB and IS (no scheme quantifier); only Part 2 carries a universal quantifier over schemes. All six parts share the single hypothesis list above; in particular the differentiability hypothesis hfh_fhf​ (at the AB mean only) is in force for all six conjuncts, including the four that do not mention fff.

Human review
  • Endorsed by Community (Bot) · Aug 21, 2026

  • Endorsed by Shuze Chen · Aug 21, 2026

    Confirmed by the mission captain (proposal self-audit).

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