Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3 — central limit theorem for the TPG estimator

Proved
TPG.lemma_3_clt

by Wenqian Xing · Oct 12, 2026 · Mathlib 0df444a (Lean v4.33.1)

causal-inferencemarkov-chainnonstationaritypolicy-gradienttreatment-effect

Setting. SSS is a finite state space and the action Zt∈{0,1}Z_t\in\{0,1\}Zt​∈{0,1} is control or treatment. Time is t=0,1,…,T−1t=0,1,\dots,T-1t=0,1,…,T−1, which is the source's time t+1t+1t+1. Under action zzz at time ttt the state moves according to a transition matrix PztP_z^tPzt​, i.e. P(Xt+1=x′∣Xt=x,Zt=z)=Pzt(x,x′)\mathbb P(X_{t+1}=x'\mid X_t=x,Z_t=z)=P_z^t(x,x')P(Xt+1​=x′∣Xt​=x,Zt​=z)=Pzt​(x,x′); the matrices may depend on ttt arbitrarily. The initial state X0X_0X0​ has distribution ρ\rhoρ, and the reward YtY_tYt​ has distribution R(⋅∣Xt,Zt)R(\cdot\mid X_t,Z_t)R(⋅∣Xt​,Zt​) on R\mathbb RR, with R([−M,M]∣x,z)=1R([-M,M]\mid x,z)=1R([−M,M]∣x,z)=1 for all x,zx,zx,z and conditional independence from everything else given (Xt,Zt)(X_t,Z_t)(Xt​,Zt​). Under the policy πθ\pi_\thetaπθ​ every action is treatment with probability θ\thetaθ, independently of everything else; Eθ\mathbb E_\thetaEθ​, Pθ\mathbb P_\thetaPθ​ and Var⁡θ\operatorname{Var}_\thetaVarθ​ refer to the law of the trajectory (Xt,Zt,Yt)t<T(X_t,Z_t,Y_t)_{t<T}(Xt​,Zt​,Yt​)t<T​ under πθ\pi_\thetaπθ​.

Asymptotic setting. The truncation size k≥0k\ge0k≥0 is fixed and the horizon T→∞T\to\inftyT→∞; for each TTT the trajectory (Xt,Zt,Yt)t<T(X_t,Z_t,Y_t)_{t<T}(Xt​,Zt​,Yt​)t<T​ is generated under the experimental policy π1/2\pi_{1/2}π1/2​. Assumption 1 holds for all times with one constant γ∈(0,1)\gamma\in(0,1)γ∈(0,1). Write wtIPW=2(2Zt−1)w_t^{\mathrm{IPW}}=2(2Z_t-1)wtIPW​=2(2Zt​−1) and

Bt=∑i=max⁡(0,t−k)twiIPW Yt,μt=E[Bt],Bˉ=1T∑t<TBt=τ^k.B_t=\sum_{i=\max(0,t-k)}^{t}w_i^{\mathrm{IPW}}\,Y_t,\qquad \mu_t=\mathbb E[B_t],\qquad \bar B=\frac1T\sum_{t<T}B_t=\widehat\tau_k .Bt​=i=max(0,t−k)∑t​wiIPW​Yt​,μt​=E[Bt​],Bˉ=T1​t<T∑​Bt​=τk​.

Assumption 2 (asymptotic variance): 1TVar⁡(∑t<TBt)→σk2\frac1T\operatorname{Var}\bigl(\sum_{t<T}B_t\bigr)\to\sigma_k^2T1​Var(∑t<T​Bt​)→σk2​ as T→∞T\to\inftyT→∞, with 0<σk2<∞0<\sigma_k^2<\infty0<σk2​<∞.

Lemma. Under Assumptions 1 and 2, as T→∞T\to\inftyT→∞,

T (τ^k−E[τ^k]) ⇒ N(0,σk2),\sqrt T\,\bigl(\widehat\tau_k-\mathbb E[\widehat\tau_k]\bigr)\ \Rightarrow\ \mathcal N\bigl(0,\sigma_k^2\bigr),T​(τk​−E[τk​]) ⇒ N(0,σk2​),

where τ^k=1T∑u=0T−1(1{Zu=1}1/2−1{Zu=0}1/2)∑t=umin⁡(u+k, T−1)Yt\widehat\tau_k=\frac1T\sum_{u=0}^{T-1}\bigl(\frac{\mathbf 1\{Z_u=1\}}{1/2}-\frac{\mathbf 1\{Z_u=0\}}{1/2}\bigr)\sum_{t=u}^{\min(u+k,\,T-1)}Y_tτk​=T1​∑u=0T−1​(1/21{Zu​=1}​−1/21{Zu​=0}​)∑t=umin(u+k,T−1)​Yt​ is the TPG estimator.

This is the asymptotic normality part of Theorem 2; it does not need the mean-stability condition.

Formalization Note Convergence in distribution is stated as convergence of E[f(⋅)]\mathbb E[f(\cdot)]E[f(⋅)] for every bounded continuous fff, with the expectation taken under the horizon-TTT law for each TTT. The limit σk2\sigma_k^2σk2​ is a parameter vvv constrained by Assumption 2.

Preamble
import Mathlib
import Definitions.Def_TPG_Model
import Definitions.Def_TPG_Estimators
import Definitions.Def_TPG_Inference

open MeasureTheory ProbabilityTheory
open scoped BigOperators ENNReal
Formal statement
namespace TPG
theorem lemma_3_clt {S : Type} [Fintype S] [MeasurableSpace S] [MeasurableSingletonClass S]
    (E : Env S) (k : ℕ) (γ M v : ℝ)
    (hγ0 : 0 < γ) (hγ1 : γ < 1) (hmix : ∀ T : ℕ, E.Mixing T γ) (hM : E.RewardBound M)
    (hvar : E.AsymptoticVariance k v) :
    E.TendstoNormal
      (fun (T : ℕ) (ω : Traj S T) =>
        Real.sqrt (T : ℝ) *
          (tpgEst (1 / 2) T k ω - ∫ ω', tpgEst (1 / 2) T k ω' ∂(E.expLaw T (1 / 2))))
      v := by sorry
end TPG
Source
Johari, Peng, Xing, Estimation of Treatment Effects Under Nonstationarity via the Truncated Policy Gradient Estimator, revised manuscript of October 2026 (revision of arXiv:2506.05308v3, https://arxiv.org/abs/2506.05308); numbering follows the revised manuscript. Appendix F.2, p. 41, Lemma 3; proof in Appendix H.1, pp. 51–53 (uses Definition 1 and Lemma 6, p. 51).
Read-back

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

Data quantified over. The statement is asserted for every choice of the following.

  • A set SSS with finitely many elements, carrying a σ\sigmaσ-algebra in which every one-point set is measurable (as SSS is finite, every subset of SSS is then measurable). Non-emptiness of SSS is not listed as an assumption, but the datum ρ\rhoρ below cannot exist on an empty set.
  • An environment EEE on SSS, i.e. a package consisting of:
    • for every time t∈N={0,1,2,… }t \in \mathbb{N} = \lbrace 0,1,2,\dots \rbracet∈N={0,1,2,…} and every z∈{true,false}z \in \lbrace \text{true}, \text{false} \rbracez∈{true,false}, a real S×SS \times SS×S matrix PtzP_t^{z}Ptz​ all of whose entries are ≥0\ge 0≥0 and each of whose rows sums to 111;
    • a function ρ:S→R\rho : S \to \mathbb{R}ρ:S→R with ρ(x)≥0\rho(x) \ge 0ρ(x)≥0 for every xxx and ∑x∈Sρ(x)=1\sum_{x \in S} \rho(x) = 1∑x∈S​ρ(x)=1;
    • for every x∈Sx \in Sx∈S and z∈{true,false}z \in \lbrace \text{true}, \text{false} \rbracez∈{true,false}, a Borel probability measure Rx,zR_{x,z}Rx,z​ on R\mathbb{R}R (the package itself imposes no moment or support condition on it).
  • A natural number kkk (any value, 000 included; one fixed number, not varying with TTT).
  • Real numbers γ\gammaγ, MMM, vvv.

Sample space and probability measure, one for each TTT. For each T∈NT \in \mathbb{N}T∈N let

ΩT=(S×{true,false}×R)T,\Omega_T = \bigl(S \times \lbrace \text{true}, \text{false} \rbrace \times \mathbb{R}\bigr)^{T},ΩT​=(S×{true,false}×R)T,

the set of sequences ω=(Xt,Zt,Yt)t=0T−1\omega = (X_t, Z_t, Y_t)_{t = 0}^{T-1}ω=(Xt​,Zt​,Yt​)t=0T−1​, with the product σ\sigmaσ-algebra (the given σ\sigmaσ-algebra on SSS, all subsets of {true,false}\lbrace \text{true}, \text{false} \rbrace{true,false}, Borel sets of R\mathbb{R}R). Write Xt(ω)∈SX_t(\omega) \in SXt​(ω)∈S, Zt(ω)∈{true,false}Z_t(\omega) \in \lbrace \text{true}, \text{false} \rbraceZt​(ω)∈{true,false}, Yt(ω)∈RY_t(\omega) \in \mathbb{R}Yt​(ω)∈R for the coordinates at time ttt.

For x=(x0,…,xT−1)∈STx = (x_0, \dots, x_{T-1}) \in S^Tx=(x0​,…,xT−1​)∈ST and z=(z0,…,zT−1)∈{true,false}Tz = (z_0, \dots, z_{T-1}) \in \lbrace \text{true}, \text{false} \rbrace^Tz=(z0​,…,zT−1​)∈{true,false}T define the weight

wT(x,z)=ρ(x0)⋅∏s=0T−2Pszs(xs,xs+1)⋅∏t=0T−112.w_T(x, z) = \rho(x_0) \cdot \prod_{s=0}^{T-2} P_s^{z_s}(x_s, x_{s+1}) \cdot \prod_{t=0}^{T-1} \tfrac12 .wT​(x,z)=ρ(x0​)⋅s=0∏T−2​Pszs​​(xs​,xs+1​)⋅t=0∏T−1​21​.

(The transition from time sss to time s+1s+1s+1 uses the matrix indexed by the departure time sss and by the value zsz_szs​. The last product comes from a general recipe "factor qtq_tqt​ if ztz_tzt​ is true, 1−qt1 - q_t1−qt​ if false", used here with qt=12q_t = \tfrac12qt​=21​ for all ttt. Empty products are 111: for T=0T = 0T=0 the weight is 111, and the factor ρ(x0)\rho(x_0)ρ(x0​) is present only when T≥1T \ge 1T≥1.) The measure on ΩT\Omega_TΩT​ is the finite mixture of product measures

PT=∑(x,z)∈ST×{true,false}Tmax⁡(wT(x,z),0)⋅⨂t=0T−1(δxt⊗δzt⊗Rxt,zt).\mathbb{P}_T = \sum_{(x,z) \in S^T \times \lbrace \text{true}, \text{false} \rbrace^T} \max\bigl(w_T(x,z), 0\bigr) \cdot \bigotimes_{t=0}^{T-1} \bigl( \delta_{x_t} \otimes \delta_{z_t} \otimes R_{x_t, z_t} \bigr).PT​=(x,z)∈ST×{true,false}T∑​max(wT​(x,z),0)⋅t=0⨂T−1​(δxt​​⊗δzt​​⊗Rxt​,zt​​).

The clipping max⁡(⋅,0)\max(\cdot, 0)max(⋅,0) is in the definition; here every weight is already ≥0\ge 0≥0 and the weights sum to 111, so PT\mathbb{P}_TPT​ is a probability measure. In words: X0X_0X0​ has law ρ\rhoρ; each ZtZ_tZt​ is a fair coin flip independent of everything generated before it and of XtX_tXt​; Xt+1X_{t+1}Xt+1​ is drawn from row XtX_tXt​ of PtZtP_t^{Z_t}PtZt​​; and, given all the XXX's and ZZZ's, the YtY_tYt​ are independent with Yt∼RXt,ZtY_t \sim R_{X_t, Z_t}Yt​∼RXt​,Zt​​. For T=0T = 0T=0, Ω0\Omega_0Ω0​ is a single point and P0\mathbb{P}_0P0​ is the unit mass on it. Write ET[⋅]\mathbb{E}_T[\cdot]ET​[⋅] for integration against PT\mathbb{P}_TPT​.

Statistics on ΩT\Omega_TΩT​. Throughout, 1/T1/T1/T is read as 000 when T=0T = 0T=0 (so every statistic below is 000 at T=0T = 0T=0), all integrals are Bochner integrals (value 000 if the integrand is not integrable), and Var⁡μ(F)\operatorname{Var}_\mu(F)Varμ​(F) means ∫∣F−∫Fdμ∣2dμ\int \lvert F - \int F d\mu \rvert^2 d\mu∫∣F−∫Fdμ∣2dμ computed in [0,∞][0, \infty][0,∞] and then converted to a real number with ∞\infty∞ sent to 000.

Two sign weights occur. The first is s(z)=1/θs(z) = 1/\thetas(z)=1/θ if zzz is true and −1/(1−θ)-1/(1-\theta)−1/(1−θ) if zzz is false, evaluated at θ=12\theta = \tfrac12θ=21​: so s(true)=2s(\text{true}) = 2s(true)=2, s(false)=−2s(\text{false}) = -2s(false)=−2. The second is a(z)=2⋅(2⋅1[z=true]−1)a(z) = 2 \cdot (2 \cdot \mathbf{1}[z = \text{true}] - 1)a(z)=2⋅(2⋅1[z=true]−1): so a(true)=2a(\text{true}) = 2a(true)=2, a(false)=−2a(\text{false}) = -2a(false)=−2.

The statistic in the conclusion is built from

GT(ω)=1T∑u=0T−1s(Zu)∑t=umin⁡(u+k,T−1)Yt,WT(ω)=T⋅(GT(ω)−ET[GT]),G_T(\omega) = \frac{1}{T} \sum_{u=0}^{T-1} s(Z_u) \sum_{t = u}^{\min(u+k, T-1)} Y_t , \qquad W_T(\omega) = \sqrt{T} \cdot \bigl( G_T(\omega) - \mathbb{E}_T[G_T] \bigr),GT​(ω)=T1​u=0∑T−1​s(Zu​)t=u∑min(u+k,T−1)​Yt​,WT​(ω)=T​⋅(GT​(ω)−ET​[GT​]),

where the inner sum runs over the times t∈{0,…,T−1}t \in \lbrace 0, \dots, T-1 \rbracet∈{0,…,T−1} with u≤t≤u+ku \le t \le u + ku≤t≤u+k (so it is cut off at the horizon T−1T-1T−1), and the centring constant is the PT\mathbb{P}_TPT​-expectation of GTG_TGT​ itself.

The variance hypothesis is built from, for t∈{0,…,T−1}t \in \lbrace 0, \dots, T-1 \rbracet∈{0,…,T−1},

BT,t(ω)=∑i=max⁡(t−k,0)ta(Zi)⋅Yt,VT=1TVar⁡PT(∑t=0T−1BT,t),B_{T,t}(\omega) = \sum_{i = \max(t-k, 0)}^{t} a(Z_i) \cdot Y_t , \qquad V_T = \frac1T \operatorname{Var}_{\mathbb{P}_T}\Bigl( \sum_{t=0}^{T-1} B_{T,t} \Bigr),BT,t​(ω)=i=max(t−k,0)∑t​a(Zi​)⋅Yt​,VT​=T1​VarPT​​(t=0∑T−1​BT,t​),

where the sum defining BT,tB_{T,t}BT,t​ is over the indices i∈{0,…,T−1}i \in \lbrace 0, \dots, T-1 \rbracei∈{0,…,T−1} with i≤t≤i+ki \le t \le i + ki≤t≤i+k.

Hypotheses. All of the following are assumed.

  1. 0<γ0 \lt \gamma0<γ.
  2. γ<1\gamma \lt 1γ<1.
  3. (Contraction of every transition matrix.) For every T∈NT \in \mathbb{N}T∈N and every t<Tt \lt Tt<T (equivalently, for every t∈Nt \in \mathbb{N}t∈N; the instance T=0T = 0T=0 is empty), every z∈{true,false}z \in \lbrace \text{true}, \text{false} \rbracez∈{true,false}, and every pair of functions f,f′:S→Rf, f' : S \to \mathbb{R}f,f′:S→R that are each nonnegative with entries summing to 111:
12∑x′∈S∣(f′Ptz)(x′)−(fPtz)(x′)∣≤γ⋅12∑x∈S∣f′(x)−f(x)∣,where (fP)(x′)=∑x∈Sf(x)P(x,x′).\frac12 \sum_{x' \in S} \bigl\lvert (f' P_t^z)(x') - (f P_t^z)(x') \bigr\rvert \le \gamma \cdot \frac12 \sum_{x \in S} \lvert f'(x) - f(x) \rvert, \qquad \text{where } (f P)(x') = \sum_{x \in S} f(x) P(x, x').21​x′∈S∑​​(f′Ptz​)(x′)−(fPtz​)(x′)​≤γ⋅21​x∈S∑​∣f′(x)−f(x)∣,where (fP)(x′)=x∈S∑​f(x)P(x,x′).
  1. (Bounded rewards.) For every x∈Sx \in Sx∈S and every zzz: Rx,z([−M,M])=1R_{x,z}([-M, M]) = 1Rx,z​([−M,M])=1. Here MMM is an arbitrary real number; if M<0M \lt 0M<0 the interval is empty and this hypothesis cannot hold.
  2. (Limit variance.) v>0v \gt 0v>0, and VT→vV_T \to vVT​→v as T→∞T \to \inftyT→∞.

Conclusion. For every bounded continuous function f:R→Rf : \mathbb{R} \to \mathbb{R}f:R→R,

lim⁡T→∞∫ΩTf(WT(ω))dPT(ω)=∫Rf(y)dN(0,max⁡(v,0))(y),\lim_{T \to \infty} \int_{\Omega_T} f\bigl( W_T(\omega) \bigr) d\mathbb{P}_T(\omega) = \int_{\mathbb{R}} f(y) d\mathcal{N}\bigl(0, \max(v, 0)\bigr)(y),T→∞lim​∫ΩT​​f(WT​(ω))dPT​(ω)=∫R​f(y)dN(0,max(v,0))(y),

where N(0,σ2)\mathcal{N}(0, \sigma^2)N(0,σ2) is the Gaussian measure on R\mathbb{R}R with mean 000 and variance σ2\sigma^2σ2, defined to be the point mass at 000 when σ2=0\sigma^2 = 0σ2=0. Under hypothesis 5, max⁡(v,0)=v\max(v, 0) = vmax(v,0)=v.

Literal behaviours to note.

  • The limit is along T∈NT \in \mathbb{N}T∈N, T→∞T \to \inftyT→∞, and both the sample space ΩT\Omega_TΩT​ and the measure PT\mathbb{P}_TPT​ change with TTT: the conclusion is convergence of the laws of WTW_TWT​ under PT\mathbb{P}_TPT​, tested against bounded continuous functions, each law living on its own space.
  • The numbers γ\gammaγ and MMM occur only in hypotheses 1 to 4, not in the conclusion. The number vvv in the conclusion is the same vvv as in hypothesis 5.
  • The two sign weights sss and aaa take the same values, so exchanging the order of the finite double sum gives ∑tBT,t=T⋅GT\sum_t B_{T,t} = T \cdot G_T∑t​BT,t​=T⋅GT​ pointwise on ΩT\Omega_TΩT​; consequently, for T≥1T \ge 1T≥1 and when the integrals involved are finite, VTV_TVT​ equals the variance of WTW_TWT​ under PT\mathbb{P}_TPT​. (This identity follows from the definitions; it is not written in the statement.)
  • Boundary effects are as written: for u>T−1−ku \gt T - 1 - ku>T−1−k the inner sum in GTG_TGT​ has fewer than k+1k + 1k+1 terms, and for t<kt \lt kt<k the sum defining BT,tB_{T,t}BT,t​ has t+1t + 1t+1 rather than k+1k + 1k+1 terms.
  • The transition matrices PtzP_t^zPtz​ with t≥T−1t \ge T - 1t≥T−1 do not enter PT\mathbb{P}_TPT​.
Human review
  • Endorsed by tianyipeng · Oct 12, 2026

  • Endorsed by Wenqian Xing · Oct 12, 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