Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 6 — bias and variance bounds for the reward-corrected (RC) estimator

Proved
TPG.proposition_6_rc_bounds

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πθ​.

Assumption 1 (mixing time) with constant γ∈(0,1)\gamma\in(0,1)γ∈(0,1): for every time t<Tt<Tt<T, every action zzz and every pair of probability vectors f,f′f,f'f,f′ on SSS, ∥f′Pzt−fPzt∥TV≤γ ∥f′−f∥TV\|f'P_z^t-fP_z^t\|_{\mathrm{TV}}\le\gamma\,\|f'-f\|_{\mathrm{TV}}∥f′Pzt​−fPzt​∥TV​≤γ∥f′−f∥TV​, where ∥f−f′∥TV=12∥f−f′∥1\|f-f'\|_{\mathrm{TV}}=\tfrac12\|f-f'\|_1∥f−f′∥TV​=21​∥f−f′∥1​. The kernel deviation is δ=sup⁡t<Tsup⁡x∈S∥P1t(x,⋅)−P0t(x,⋅)∥TV\delta=\sup_{t<T}\sup_{x\in S}\|P_1^t(x,\cdot)-P_0^t(x,\cdot)\|_{\mathrm{TV}}δ=supt<T​supx∈S​∥P1t​(x,⋅)−P0t​(x,⋅)∥TV​.

The global average treatment effect is τ=1T∑t<T(E1[Yt]−E0[Yt])\tau=\frac1T\sum_{t<T}\bigl(\mathbb E_1[Y_t]-\mathbb E_0[Y_t]\bigr)τ=T1​∑t<T​(E1​[Yt​]−E0​[Yt​]).

Fix θ∈(0,1)\theta\in(0,1)θ∈(0,1). With the score sθ(z)=zθ−1−z1−θs_\theta(z)=\dfrac z\theta-\dfrac{1-z}{1-\theta}sθ​(z)=θz​−1−θ1−z​ and the additional importance weight wθ(z)=(1−θ)zθ+θ(1−z)1−θw_\theta(z)=\dfrac{(1-\theta)z}{\theta}+\dfrac{\theta(1-z)}{1-\theta}wθ​(z)=θ(1−θ)z​+1−θθ(1−z)​, the reward-corrected estimator with truncation size kkk, computed from a trajectory generated under πθ\pi_\thetaπθ​, is

τ^θ,kRC=1T∑u=0T−1sθ(Zu)[Yu+∑t=u+1min⁡(u+k, T−1)wθ(Zt) Yt].\widehat\tau^{\mathrm{RC}}_{\theta,k}=\frac1T\sum_{u=0}^{T-1}s_\theta(Z_u)\Bigl[Y_u+\sum_{t=u+1}^{\min(u+k,\,T-1)}w_\theta(Z_t)\,Y_t\Bigr].τθ,kRC​=T1​u=0∑T−1​sθ​(Zu​)[Yu​+t=u+1∑min(u+k,T−1)​wθ​(Zt​)Yt​].

Write pθ=θ(1−θ)p_\theta=\theta(1-\theta)pθ​=θ(1−θ), cθ=1+(1−2θ)2pθc_\theta=1+\dfrac{(1-2\theta)^2}{p_\theta}cθ​=1+pθ​(1−2θ)2​ and Ψk(γ)=∑j=0k−2(j+1)γj\Psi_k(\gamma)=\sum_{j=0}^{k-2}(j+1)\gamma^jΨk​(γ)=∑j=0k−2​(j+1)γj (so Ψ0=Ψ1=0\Psi_0=\Psi_1=0Ψ0​=Ψ1​=0).

Proposition. Under Assumption 1, for every T≥1T\ge1T≥1, θ∈(0,1)\theta\in(0,1)θ∈(0,1) and integer 0≤k≤T0\le k\le T0≤k≤T:

∣Eθ[τ^θ,kRC]−τ∣≤2δMγk1−γ+4[θ2+(1−θ)2]δ2M Ψk(γ),\Bigl|\mathbb E_\theta\bigl[\widehat\tau^{\mathrm{RC}}_{\theta,k}\bigr]-\tau\Bigr|\le\frac{2\delta M\gamma^k}{1-\gamma}+4\bigl[\theta^2+(1-\theta)^2\bigr]\delta^2M\,\Psi_k(\gamma),​Eθ​[τθ,kRC​]−τ​≤1−γ2δMγk​+4[θ2+(1−θ)2]δ2MΨk​(γ), Var⁡θ(τ^θ,kRC)≤M2T pθ (1+k cθ)(2k+3+4γ1−γ).\operatorname{Var}_\theta\bigl(\widehat\tau^{\mathrm{RC}}_{\theta,k}\bigr)\le\frac{M^2}{T\,p_\theta}\,(1+k\,c_\theta)\Bigl(2k+3+\frac{4\gamma}{1-\gamma}\Bigr).Varθ​(τθ,kRC​)≤Tpθ​M2​(1+kcθ​)(2k+3+1−γ4γ​).

When k≥T−1k\ge T-1k≥T−1, the first term of the bias bound can be omitted.

Compared with Proposition 5, the reward correction removes the first-order term in δ\deltaδ that appears away from balanced randomization, at the cost of a larger variance bound. At θ=1/2\theta=1/2θ=1/2 the two estimators coincide.

Formalization Note The remark on k≥T−1k\ge T-1k≥T−1 is the third conjunct of the formal statement, under the hypothesis T≤k+1T\le k+1T≤k+1.

Preamble
import Mathlib
import Definitions.Def_TPG_Model
import Definitions.Def_TPG_Estimators

open MeasureTheory ProbabilityTheory
open scoped BigOperators ENNReal
Formal statement
namespace TPG
theorem proposition_6_rc_bounds {S : Type} [Fintype S] [MeasurableSpace S] [MeasurableSingletonClass S]
    (E : Env S) (T k : ℕ) (θ γ M : ℝ)
    (hT : 0 < T) (hk : k ≤ T) (hθ0 : 0 < θ) (hθ1 : θ < 1) (hγ0 : 0 < γ) (hγ1 : γ < 1)
    (hmix : E.Mixing T γ) (hM : E.RewardBound M) :
    |(∫ ω, rcEst θ T k ω ∂(E.expLaw T θ)) - E.gate T|
        ≤ 2 * E.delta T * M * γ ^ k / (1 - γ)
          + 4 * (θ ^ 2 + (1 - θ) ^ 2) * (E.delta T) ^ 2 * M * Psi k γ
      ∧ variance (rcEst θ T k) (E.expLaw T θ)
        ≤ M ^ 2 / ((T : ℝ) * (θ * (1 - θ)))
            * (1 + (k : ℝ) * (1 + (1 - 2 * θ) ^ 2 / (θ * (1 - θ))))
            * (2 * (k : ℝ) + 3 + 4 * γ / (1 - γ))
      ∧ (T ≤ k + 1 →
          |(∫ ω, rcEst θ T k ω ∂(E.expLaw T θ)) - E.gate T|
            ≤ 4 * (θ ^ 2 + (1 - θ) ^ 2) * (E.delta T) ^ 2 * M * Psi k γ) := 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 E.1, p. 33 (RC estimator) and Appendix E.3, p. 36, Proposition 6, eqs. (22)–(23); proof in Appendix G.6, pp. 48–51.
Read-back

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

Setting (data and typeclass assumptions). Let SSS be a finite set carrying a σ\sigmaσ-algebra in which every singleton is measurable (as SSS is finite, this forces the σ\sigmaσ-algebra to be the full power set). Let E=(P,ρ,R)E=(P,\rho,R)E=(P,ρ,R) be an environment on SSS, which consists of exactly the following data:

  • for every time index t∈N={0,1,2,… }t\in\mathbb{N}=\{0,1,2,\dots\}t∈N={0,1,2,…} and every Boolean z∈{1,0}z\in\{1,0\}z∈{1,0} (here 111 = true, 000 = false), a real S×SS\times SS×S matrix Pt(z)P_t^{(z)}Pt(z)​ whose entries are all ≥0\ge 0≥0 and whose rows each sum to one: ∑x′∈SPt(z)(x,x′)=1\sum_{x'\in S}P_t^{(z)}(x,x')=1∑x′∈S​Pt(z)​(x,x′)=1 for every x∈Sx\in Sx∈S;
  • a function ρ:S→R\rho:S\to\mathbb{R}ρ:S→R with ρ(x)≥0\rho(x)\ge 0ρ(x)≥0 for all 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 every Boolean zzz, a Borel probability measure Rx,zR_{x,z}Rx,z​ on R\mathbb{R}R.

Such an EEE can exist only if SSS is non-empty, because ρ\rhoρ sums to 111.

Let TTT and kkk be natural numbers and let θ,γ,M\theta,\gamma,Mθ,γ,M be real numbers. The statement is asserted for all such SSS, EEE, TTT, kkk, θ\thetaθ, γ\gammaγ, MMM satisfying the six hypotheses below.

Hypotheses.

  1. 0<T0<T0<T.
  2. k≤Tk\le Tk≤T.
  3. 0<θ0<\theta0<θ and θ<1\theta<1θ<1.
  4. 0<γ0<\gamma0<γ and γ<1\gamma<1γ<1.
  5. (Contraction of every one-step matrix, with constant γ\gammaγ.) For every natural number t<Tt<Tt<T, every Boolean zzz, and every pair of functions f,f′:S→Rf,f':S\to\mathbb{R}f,f′:S→R that are probability vectors (all values ≥0\ge 0≥0, values summing to 111),
TV(f′Pt(z), fPt(z))  ≤  γ⋅TV(f′,f).\mathrm{TV}\big(f'P_t^{(z)},\,fP_t^{(z)}\big)\;\le\;\gamma\cdot\mathrm{TV}(f',f).TV(f′Pt(z)​,fPt(z)​)≤γ⋅TV(f′,f).

Here fPfPfP is the row-vector–matrix product (fP)(x′)=∑x∈Sf(x) P(x,x′)(fP)(x')=\sum_{x\in S}f(x)\,P(x,x')(fP)(x′)=∑x∈S​f(x)P(x,x′), and for any two functions g,h:S→Rg,h:S\to\mathbb{R}g,h:S→R the symbol TV\mathrm{TV}TV means TV(g,h)=12∑x∈S∣g(x)−h(x)∣\mathrm{TV}(g,h)=\tfrac12\sum_{x\in S}\lvert g(x)-h(x)\rvertTV(g,h)=21​∑x∈S​∣g(x)−h(x)∣. The condition is imposed separately on Pt(1)P_t^{(1)}Pt(1)​ and on Pt(0)P_t^{(0)}Pt(0)​, for t=0,1,…,T−1t=0,1,\dots,T-1t=0,1,…,T−1 only.

  1. (Bounded support.) For every x∈Sx\in Sx∈S and every Boolean zzz, Rx,z([−M,M])=1R_{x,z}\big([-M,M]\big)=1Rx,z​([−M,M])=1.

No sign condition on MMM is stated separately. If M<0M<0M<0 the interval [−M,M][-M,M][−M,M] is empty and hypothesis 6 cannot hold; if M=0M=0M=0 hypothesis 6 says that every Rx,zR_{x,z}Rx,z​ is the unit point mass at 000.

The probability measures used. Times are indexed from 000. The sample space is

ΩT=(S×{1,0}×R){0,1,…,T−1},\Omega_T=\big(S\times\{1,0\}\times\mathbb{R}\big)^{\{0,1,\dots,T-1\}},ΩT​=(S×{1,0}×R){0,1,…,T−1},

with the product σ\sigmaσ-algebra (power set on SSS and on the Booleans, Borel sets on R\mathbb{R}R). For t∈{0,…,T−1}t\in\{0,\dots,T-1\}t∈{0,…,T−1} and ω∈ΩT\omega\in\Omega_Tω∈ΩT​ write Xt(ω)∈SX_t(\omega)\in SXt​(ω)∈S, Zt(ω)∈{1,0}Z_t(\omega)\in\{1,0\}Zt​(ω)∈{1,0} and Yt(ω)∈RY_t(\omega)\in\mathbb{R}Yt​(ω)∈R for the three components of the ttt-th coordinate of ω\omegaω.

For a real number ccc and sequences x=(x0,…,xT−1)∈STx=(x_0,\dots,x_{T-1})\in S^Tx=(x0​,…,xT−1​)∈ST, z=(z0,…,zT−1)∈{1,0}Tz=(z_0,\dots,z_{T-1})\in\{1,0\}^Tz=(z0​,…,zT−1​)∈{1,0}T, define the weight

wc(x,z)  =  ρ(x0)  ⋅  ∏s=0T−2Ps(zs)(xs,xs+1)  ⋅  ∏t=0T−1{c,zt=1,1−c,zt=0,w_c(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}\begin{cases}c,& z_t=1,\\ 1-c,& z_t=0,\end{cases}wc​(x,z)=ρ(x0​)⋅s=0∏T−2​Ps(zs​)​(xs​,xs+1​)⋅t=0∏T−1​{c,1−c,​zt​=1,zt​=0,​

(in the code the first factor is a product over all ttt of factors equal to ρ(xt)\rho(x_t)ρ(xt​) when t=0t=0t=0 and to 111 otherwise, and the second is a product over all pairs (s,t)(s,t)(s,t) of factors equal to Ps(zs)(xs,xt)P_s^{(z_s)}(x_s,x_t)Ps(zs​)​(xs​,xt​) when t=s+1t=s+1t=s+1 and to 111 otherwise). Define the measure on ΩT\Omega_TΩT​

Pc  =  ∑(x,z)∈ST×{1,0}Tmax⁡{wc(x,z),0}  ⋅  ⨂t=0T−1(εxt⊗εzt⊗Rxt,zt),\mathbb{P}_c\;=\;\sum_{(x,z)\in S^T\times\{1,0\}^T}\max\{w_c(x,z),0\}\;\cdot\;\bigotimes_{t=0}^{T-1}\Big(\varepsilon_{x_t}\otimes\varepsilon_{z_t}\otimes R_{x_t,z_t}\Big),Pc​=(x,z)∈ST×{1,0}T∑​max{wc​(x,z),0}⋅t=0⨂T−1​(εxt​​⊗εzt​​⊗Rxt​,zt​​),

where εa\varepsilon_aεa​ is the unit point mass at aaa and ⨂\bigotimes⨂ is the product measure. (The code defines this for an arbitrary real sequence (qt)t∈N(q_t)_{t\in\mathbb{N}}(qt​)t∈N​ in place of the constant ccc; this statement only uses the constant sequences c=θc=\thetac=θ, c=1c=1c=1 and c=0c=0c=0. For c∈[0,1]c\in[0,1]c∈[0,1] every weight is already ≥0\ge 0≥0, so the truncation max⁡{⋅,0}\max\{\cdot,0\}max{⋅,0} changes nothing, and the weights sum to 111.) In words, under Pc\mathbb{P}_cPc​: X0X_0X0​ has distribution ρ\rhoρ; each ZtZ_tZt​ equals 111 with probability ccc and 000 with probability 1−c1-c1−c, independently of everything earlier; given the past, Xt+1X_{t+1}Xt+1​ is drawn from row XtX_tXt​ of the matrix Pt(Zt)P_t^{(Z_t)}Pt(Zt​)​; and, given the whole sequence (Xt,Zt)t(X_t,Z_t)_t(Xt​,Zt​)t​, the YtY_tYt​ are independent with Yt∼RXt,ZtY_t\sim R_{X_t,Z_t}Yt​∼RXt​,Zt​​. Under P1\mathbb{P}_1P1​ only the sequence z≡1z\equiv 1z≡1 has non-zero weight, and under P0\mathbb{P}_0P0​ only z≡0z\equiv 0z≡0. The matrices PT−1(z)P_{T-1}^{(z)}PT−1(z)​, and all Pt(z)P_t^{(z)}Pt(z)​ with t≥Tt\ge Tt≥T, do not occur in wcw_cwc​.

Write Ec[ ⋅ ]\mathbb{E}_c[\,\cdot\,]Ec​[⋅] for the integral with respect to Pc\mathbb{P}_cPc​ (the Bochner integral, which by convention is 000 for a non-integrable integrand), and

Varc(F)  =  ∫ΩT(F−Ec[F])2 dPc,\mathrm{Var}_c(F)\;=\;\int_{\Omega_T}\big(F-\mathbb{E}_c[F]\big)^2\,d\mathbb{P}_c,Varc​(F)=∫ΩT​​(F−Ec​[F])2dPc​,

computed as an integral with values in [0,∞][0,\infty][0,∞] and then converted to a real number with the convention ∞↦0\infty\mapsto 0∞↦0. (Under hypothesis 6 every YtY_tYt​ lies in [−M,M][-M,M][−M,M] almost surely under Pθ\mathbb{P}_\thetaPθ​, P1\mathbb{P}_1P1​, P0\mathbb{P}_0P0​, so neither convention is triggered for the quantities below.)

Quantities appearing in the statement.

  • The reference quantity (named gate in the code):
GT  =  1T∑t=0T−1(E1[Yt]−E0[Yt]).G_T\;=\;\frac1T\sum_{t=0}^{T-1}\Big(\mathbb{E}_1[Y_t]-\mathbb{E}_0[Y_t]\Big).GT​=T1​t=0∑T−1​(E1​[Yt​]−E0​[Yt​]).
  • The statistic (named rcEst), a function of ω∈ΩT\omega\in\Omega_Tω∈ΩT​:
Hθ,T,krc(ω)  =  1T∑u=0T−1sθ(Zu(ω))(Yu(ω)  +∑t∈{0,…,T−1}u<t≤u+kλθ(Zt(ω)) Yt(ω)),H^{\mathrm{rc}}_{\theta,T,k}(\omega)\;=\;\frac1T\sum_{u=0}^{T-1}s_\theta\big(Z_u(\omega)\big)\Bigg(Y_u(\omega)\;+\sum_{\substack{t\in\{0,\dots,T-1\}\\ u<t\le u+k}}\lambda_\theta\big(Z_t(\omega)\big)\,Y_t(\omega)\Bigg),Hθ,T,krc​(ω)=T1​u=0∑T−1​sθ​(Zu​(ω))(Yu​(ω)+t∈{0,…,T−1}u<t≤u+k​∑​λθ​(Zt​(ω))Yt​(ω)),

with

sθ(1)=1θ,sθ(0)=−11−θ,λθ(1)=1−θθ,λθ(0)=θ1−θ.s_\theta(1)=\frac1\theta,\quad s_\theta(0)=-\frac{1}{1-\theta},\qquad \lambda_\theta(1)=\frac{1-\theta}{\theta},\quad \lambda_\theta(0)=\frac{\theta}{1-\theta}.sθ​(1)=θ1​,sθ​(0)=−1−θ1​,λθ​(1)=θ1−θ​,λθ​(0)=1−θθ​.

The inner sum runs over t=u+1,…,min⁡(u+k, T−1)t=u+1,\dots,\min(u+k,\,T-1)t=u+1,…,min(u+k,T−1) (strictly later than uuu, cut off at the last time T−1T-1T−1, empty when k=0k=0k=0 or u=T−1u=T-1u=T−1). The term YuY_uYu​ carries no factor λθ\lambda_\thetaλθ​; each later YtY_tYt​ is multiplied by λθ(Zt)\lambda_\theta(Z_t)λθ​(Zt​), evaluated at the Boolean of the same time ttt.

  • The kernel discrepancy (named delta):
δT  =  sup⁡t∈{0,…,T−1}  sup⁡x∈S  12∑x′∈S∣Pt(1)(x,x′)−Pt(0)(x,x′)∣.\delta_T\;=\;\sup_{t\in\{0,\dots,T-1\}}\;\sup_{x\in S}\;\frac12\sum_{x'\in S}\Big\lvert P_t^{(1)}(x,x')-P_t^{(0)}(x,x')\Big\rvert .δT​=t∈{0,…,T−1}sup​x∈Ssup​21​x′∈S∑​​Pt(1)​(x,x′)−Pt(0)​(x,x′)​.

Both suprema are over finite non-empty sets, so this is a maximum; it includes t=T−1t=T-1t=T−1. (The supremum used is the real-valued one, which would return 000 over an empty index set.)

  • The polynomial-geometric sum (named Psi):
Ψk(γ)  =  ∑j=0k−11[ j+2≤k ] (j+1) γj  =  ∑j=0k−2(j+1) γj,\Psi_k(\gamma)\;=\;\sum_{j=0}^{k-1}\mathbf{1}[\,j+2\le k\,]\,(j+1)\,\gamma^{j}\;=\;\sum_{j=0}^{k-2}(j+1)\,\gamma^{j},Ψk​(γ)=j=0∑k−1​1[j+2≤k](j+1)γj=j=0∑k−2​(j+1)γj,

which equals 000 when k=0k=0k=0 or k=1k=1k=1.

Conclusion. Under hypotheses 1–6, all three of the following hold.

(i) Bound on the difference between the Pθ\mathbb{P}_\thetaPθ​-expectation of the statistic and GTG_TGT​:

∣ Eθ[Hθ,T,krc]−GT ∣  ≤  2 δT M γk1−γ  +  4(θ2+(1−θ)2) δT 2 M Ψk(γ).\Big\lvert\,\mathbb{E}_\theta\big[H^{\mathrm{rc}}_{\theta,T,k}\big]-G_T\,\Big\rvert\;\le\;\frac{2\,\delta_T\,M\,\gamma^{k}}{1-\gamma}\;+\;4\big(\theta^2+(1-\theta)^2\big)\,\delta_T^{\,2}\,M\,\Psi_k(\gamma).​Eθ​[Hθ,T,krc​]−GT​​≤1−γ2δT​Mγk​+4(θ2+(1−θ)2)δT2​MΨk​(γ).

(ii) Bound on the variance of the statistic under Pθ\mathbb{P}_\thetaPθ​:

Varθ(Hθ,T,krc)  ≤  M2T θ (1−θ)⋅(1+k(1+(1−2θ)2θ (1−θ)))⋅(2k+3+4γ1−γ).\mathrm{Var}_\theta\big(H^{\mathrm{rc}}_{\theta,T,k}\big)\;\le\;\frac{M^2}{T\,\theta\,(1-\theta)}\cdot\Bigg(1+k\bigg(1+\frac{(1-2\theta)^2}{\theta\,(1-\theta)}\bigg)\Bigg)\cdot\Big(2k+3+\frac{4\gamma}{1-\gamma}\Big).Varθ​(Hθ,T,krc​)≤Tθ(1−θ)M2​⋅(1+k(1+θ(1−θ)(1−2θ)2​))⋅(2k+3+1−γ4γ​).

Both bracketed factors multiply the fraction M2Tθ(1−θ)\tfrac{M^2}{T\theta(1-\theta)}Tθ(1−θ)M2​ (neither is in the denominator).

(iii) If moreover T≤k+1T\le k+1T≤k+1, then

∣ Eθ[Hθ,T,krc]−GT ∣  ≤  4(θ2+(1−θ)2) δT 2 M Ψk(γ),\Big\lvert\,\mathbb{E}_\theta\big[H^{\mathrm{rc}}_{\theta,T,k}\big]-G_T\,\Big\rvert\;\le\;4\big(\theta^2+(1-\theta)^2\big)\,\delta_T^{\,2}\,M\,\Psi_k(\gamma),​Eθ​[Hθ,T,krc​]−GT​​≤4(θ2+(1−θ)2)δT2​MΨk​(γ),

that is, the right-hand side of (i) without its first term 2δTMγk1−γ\tfrac{2\delta_T M\gamma^k}{1-\gamma}1−γ2δT​Mγk​.

Edge cases covered by the quantifiers.

  • Together with hypothesis 2, the extra condition T≤k+1T\le k+1T≤k+1 in (iii) means k=T−1k=T-1k=T−1 or k=Tk=Tk=T. For every k≥T−1k\ge T-1k≥T−1 the cut-off min⁡(u+k,T−1)\min(u+k,T-1)min(u+k,T−1) equals T−1T-1T−1 for all uuu, so Hθ,T,TrcH^{\mathrm{rc}}_{\theta,T,T}Hθ,T,Trc​ and Hθ,T,T−1rcH^{\mathrm{rc}}_{\theta,T,T-1}Hθ,T,T−1rc​ are the same function, while the right-hand sides of (i)–(iii) are evaluated at the respective value of kkk.
  • k=0k=0k=0 is allowed. Then the bracket in the statistic is the single term YuY_uYu​, γ0=1\gamma^0=1γ0=1 and Ψ0(γ)=0\Psi_0(\gamma)=0Ψ0​(γ)=0: (i) reads ∣Eθ[Hθ,T,0rc]−GT∣≤2δTM/(1−γ)\lvert\mathbb{E}_\theta[H^{\mathrm{rc}}_{\theta,T,0}]-G_T\rvert\le 2\delta_T M/(1-\gamma)∣Eθ​[Hθ,T,0rc​]−GT​∣≤2δT​M/(1−γ); (ii) reads Varθ(Hθ,T,0rc)≤M2Tθ(1−θ)(3+4γ1−γ)\mathrm{Var}_\theta(H^{\mathrm{rc}}_{\theta,T,0})\le \frac{M^2}{T\theta(1-\theta)}\big(3+\frac{4\gamma}{1-\gamma}\big)Varθ​(Hθ,T,0rc​)≤Tθ(1−θ)M2​(3+1−γ4γ​); and (iii) applies only when T=1T=1T=1.
  • Since Ψk(γ)=0\Psi_k(\gamma)=0Ψk​(γ)=0 for k≤1k\le 1k≤1, the right-hand side of (iii) is 000 whenever k≤1k\le 1k≤1; the condition of (iii) is then met exactly for (T,k)∈{(1,0),(1,1),(2,1)}(T,k)\in\{(1,0),(1,1),(2,1)\}(T,k)∈{(1,0),(1,1),(2,1)}, and in those cases (iii) asserts Eθ[Hθ,T,krc]=GT\mathbb{E}_\theta[H^{\mathrm{rc}}_{\theta,T,k}]=G_TEθ​[Hθ,T,krc​]=GT​.
  • T=1T=1T=1 is allowed. Then wcw_cwc​ contains no matrix entry at all, while hypothesis 5 and δT\delta_TδT​ still refer to P0(1),P0(0)P_0^{(1)},P_0^{(0)}P0(1)​,P0(0)​; the condition of (iii) holds for both admissible values k∈{0,1}k\in\{0,1\}k∈{0,1}.
  • In general hypothesis 5 and δT\delta_TδT​ involve the matrices at t=T−1t=T-1t=T−1, which do not enter any of the measures Pc\mathbb{P}_cPc​.
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