Variance reduction for differentiable estimators (Theorem 9)
DisprovedTreatmentLocality.differentiable_estimator_variance_dominanceTheorem 9 of arXiv:2407.19618. Consider an SST model run under the mixed policy , with the experiment tuple chain uniformly ergodic with stationary law and rewards square-integrable. Let , , be any differentiable estimator ( 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 ; (2) asymptotic normality — for each scheme , with the asymptotic variance of the linearized observable; (3) decomposition and dominance — writing (instantaneous plus temporal parts): the temporal parts are equal, ; the instantaneous parts agree on every row and column associated with the crucial state (the heterogeneous part is unchanged — variance at the treated state cannot be reduced); the difference is positive semidefinite (the homogeneous part is reduced); and consequently 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: with non-measurable is differentiable at with derivative 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 " 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.
import Definitions.Def_TreatmentLocalityEstimator import Definitions.Def_MarkovErgodicity import Mathlib.LinearAlgebra.Matrix.PosDef open MeasureTheory ProbabilityTheory Filter TreatmentLocality open scoped NNReal ENNReal Topology
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 sorryRead-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 be a finite type with decidable equality, equipped with a measurable space structure in which every singleton is measurable. A model over consists of: a distinguished "crucial" state ; a transition law , a probability mass function on , for each state and each Boolean action ; a reward law , a probability measure on , for each ; and a discount factor (the discount plays no role in this statement). The Boolean policy action is : action true is taken only when the arm bit is true and the current state is the crucial state; in every other case the action is false.
A step is a tuple . The step law at , , is the probability measure on given by
i.e. the arm is uniform on , and given the arm , the next state and the reward are drawn independently from and respectively. The experiment kernel is the Markov kernel on steps that maps a step to the law of with : the new step's first coordinate is deterministically the old step's next state.
Hypotheses. The theorem takes:
- a probability measure on steps;
- : is invariant for (pushing through returns );
- : is uniformly ergodic toward in the following exact sense: there exist real constants and such that for every step and every ,
where is the -fold kernel iterate ( identity/Dirac kernel) and (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 .
- : for every state and Boolean , the identity function is in of (rewards have finite second moments);
- a function on the estimator-input space , where an element assigns to each Boolean arm a pair (a matrix and a vector per arm);
- a continuous linear map ;
- : is Fréchet-differentiable at the single point (defined below) with derivative . 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, and . The scheme weight of arm at step is
The observable of scheme at step has, for each arm ,
The population mean is the entrywise Bochner integral of against . The empirical average , for and a trajectory , is entrywise — the average uses coordinates , skipping ; for each entry is (the reciprocal convention).
Coordinates of are indexed by : index picks the matrix entry and picks the vector entry ; the index state is in the first case (the first component of the pair) and in the second. Write the -th coordinate of .
Covariance machinery. For real-valued functions on steps, the lag- covariance is
The matrices over are:
The infinite sums are Lean tsums: if a series is not summable, its value is the junk value ; no summability is hypothesized. Likewise the scalar asymptotic variance of a function is (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:
-
Mean equality. as elements of (i.e. equality of every matrix and vector entry, for both arms).
-
CLT for the plug-in functional, for both schemes. For every scheme (this part, and only the parts explicitly marked, quantifies over schemes): the sequence of random variables on the path space , each carrying the same measure — the law of the Markov chain with kernel and initial distribution (coordinate has law ) —
converges in distribution, as , to the real Gaussian law with variance
i.e. the asymptotic variance of the scalar functional , clamped to if negative (a toNNReal coercion); yields the Dirac mass at . Note carefully: the centering constant is — the AB mean — for both schemes, and the derivative used inside the variance is the one from hypothesis , taken at the AB mean, even when .
-
Lag-covariance equality. as full matrices — equality at every pair of indices , with no restriction to crucial-state indices.
-
Instantaneous-covariance equality at crucial indices. For all indices : if or (at least one of the two indices has its state component equal to the crucial state), then . Nothing is asserted for pairs where neither index touches the crucial state.
-
Instantaneous dominance. The matrix is positive semidefinite in the Mathlib sense, which asserts two things: the matrix is symmetric (Hermitian over ), and for every vector .
-
Asymptotic dominance. Likewise, (the difference of the asymptotic covariance matrices ) 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 (at the AB mean only) is in force for all six conjuncts, including the four that do not mention .
Confirmed by the mission captain (proposal self-audit).