Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 3 — the truncated policy gradient ∇Jk(1/2)\nabla J_k(1/2)∇Jk​(1/2) is the average truncated QQQ-value difference

Proved
TPG.proposition_3_truncated_policy_gradient

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

Fix a truncation size kkk. For a reward time ttt, the hypothetical truncated policy follows the experimental policy π1/2\pi_{1/2}π1/2​ at the times u<max⁡(0,t−k)u<\max(0,t-k)u<max(0,t−k) and switches to πθ\pi_\thetaπθ​ at time max⁡(0,t−k)\max(0,t-k)max(0,t−k); Lθt,k\mathcal L_\theta^{t,k}Lθt,k​ denotes the law of YtY_tYt​ under it. The truncated policy value and the truncated QQQ-value are

Jk(θ)=1T∑t<TELθt,k[Yt],Q1/2t,k(z)=∑u=tmin⁡(t+k, T−1)E1/2[Yu∣Zt=z].J_k(\theta)=\frac1T\sum_{t<T}\mathbb E_{\mathcal L_\theta^{t,k}}[Y_t],\qquad Q_{1/2}^{t,k}(z)=\sum_{u=t}^{\min(t+k,\,T-1)}\mathbb E_{1/2}[Y_u\mid Z_t=z].Jk​(θ)=T1​t<T∑​ELθt,k​​[Yt​],Q1/2t,k​(z)=u=t∑min(t+k,T−1)​E1/2​[Yu​∣Zt​=z].

Proposition. For every T≥1T\ge1T≥1 and 0≤k≤T0\le k\le T0≤k≤T, the function JkJ_kJk​ is differentiable at θ=1/2\theta=1/2θ=1/2 and

∇Jk(1/2)=1T∑t=0T−1(Q1/2t,k(1)−Q1/2t,k(0)).\nabla J_k(1/2)=\frac1T\sum_{t=0}^{T-1}\bigl(Q_{1/2}^{t,k}(1)-Q_{1/2}^{t,k}(0)\bigr).∇Jk​(1/2)=T1​t=0∑T−1​(Q1/2t,k​(1)−Q1/2t,k​(0)).

The right-hand side is the expectation of the TPG estimator τ^k\widehat\tau_kτk​, so the estimator is unbiased for the truncated policy gradient.

Formalization Note In the formal definition the hypothetical policy keeps treatment probability θ\thetaθ after time ttt as well, which does not affect the law of YtY_tYt​.

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_3_truncated_policy_gradient {S : Type} [Fintype S] [MeasurableSpace S] [MeasurableSingletonClass S]
    (E : Env S) (T k : ℕ) (M : ℝ) (hT : 0 < T) (hk : k ≤ T) (hM : E.RewardBound M) :
    HasDerivAt (fun θ : ℝ => E.Jk T k θ)
      ((1 / (T : ℝ)) * ∑ t : Fin T, (E.Qk (1 / 2) T k t true - E.Qk (1 / 2) T k t false))
      (1 / 2) := 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. §5 (Estimation via the truncated policy gradient estimator), pp. 15–16, Proposition 3, eqs. (9)–(10); proof in Appendix G.3, p. 46.
Read-back

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

What is quantified. The statement holds for every choice of the following data.

  • A finite set SSS, carrying an arbitrary σ\sigmaσ-algebra in which every singleton is measurable (as SSS is finite, every subset of SSS is then measurable).

  • An "environment" EEE on SSS, meaning the following package:

    • for every natural number t∈Nt \in \mathbb{N}t∈N (all of them, not only those below the horizon) and every Boolean value z∈{true,false}z \in \lbrace \mathrm{true}, \mathrm{false} \rbracez∈{true,false}, a real S×SS \times SS×S matrix PtzP_t^{z}Ptz​ whose entries are all ≥0\ge 0≥0 and whose rows each sum to 111;
    • 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.

    Because ρ\rhoρ sums to 111, such an EEE can only exist when SSS is nonempty.

  • Natural numbers TTT and kkk, with the hypotheses 0<T0 \lt T0<T and k≤Tk \le Tk≤T. The value k=0k = 0k=0 is allowed.

  • A real number MMM (no sign condition), with the hypothesis that Rx,z([−M,M])=1R_{x,z}([-M, M]) = 1Rx,z​([−M,M])=1 for every x∈Sx \in Sx∈S and every Boolean zzz. The number MMM occurs nowhere else in the statement. If M<0M \lt 0M<0 the interval [−M,M][-M,M][−M,M] is empty and this hypothesis cannot be satisfied.

The sample space. Let Ω\OmegaΩ be the set of all sequences ω=(ω0,…,ωT−1)\omega = (\omega_0, \dots, \omega_{T-1})ω=(ω0​,…,ωT−1​) with each ωt∈S×{true,false}×R\omega_t \in S \times \lbrace \mathrm{true}, \mathrm{false} \rbrace \times \mathbb{R}ωt​∈S×{true,false}×R, with the product σ\sigmaσ-algebra (the given one on SSS, the discrete one on the Booleans, the Borel one on R\mathbb{R}R). Write Xt(ω)∈SX_t(\omega) \in SXt​(ω)∈S, Zt(ω)∈{true,false}Z_t(\omega) \in \lbrace \mathrm{true}, \mathrm{false} \rbraceZt​(ω)∈{true,false} and Yt(ω)∈RY_t(\omega) \in \mathbb{R}Yt​(ω)∈R for the three components of ωt\omega_tωt​. Times run over 0,1,…,T−10, 1, \dots, T-10,1,…,T−1.

The family of measures Λq\Lambda_qΛq​. Let q=(qu)q = (q_u)q=(qu​) be any sequence of real numbers indexed by u∈Nu \in \mathbb{N}u∈N (the entries need not lie in [0,1][0,1][0,1]). For x=(x0,…,xT−1)∈STx = (x_0,\dots,x_{T-1}) \in S^Tx=(x0​,…,xT−1​)∈ST and a Boolean sequence z=(z0,…,zT−1)z = (z_0,\dots,z_{T-1})z=(z0​,…,zT−1​) define the real number

wq(x,z)=ρ(x0)⋅∏s=0T−2Pszs(xs,xs+1)⋅∏u=0T−1bq(u,zu),bq(u,true)=qu,bq(u,false)=1−qu.w_q(x,z) = \rho(x_0) \cdot \prod_{s=0}^{T-2} P_s^{z_s}(x_s, x_{s+1}) \cdot \prod_{u=0}^{T-1} b_q(u, z_u), \qquad b_q(u,\mathrm{true}) = q_u, \quad b_q(u,\mathrm{false}) = 1 - q_u .wq​(x,z)=ρ(x0​)⋅s=0∏T−2​Pszs​​(xs​,xs+1​)⋅u=0∏T−1​bq​(u,zu​),bq​(u,true)=qu​,bq​(u,false)=1−qu​.

(The middle product is empty, equal to 111, when T=1T = 1T=1. The matrix PszsP_s^{z_s}Pszs​​ governs the passage from index sss to index s+1s+1s+1; matrices PszP_s^{z}Psz​ with s≥T−1s \ge T-1s≥T−1 are never used.) Then

Λq=∑(x,z)max⁡(wq(x,z),0)⋅⨂u=0T−1(δxu⊗δzu⊗Rxu,zu),\Lambda_q = \sum_{(x,z)} \max\bigl(w_q(x,z), 0\bigr) \cdot \bigotimes_{u=0}^{T-1} \bigl( \delta_{x_u} \otimes \delta_{z_u} \otimes R_{x_u, z_u} \bigr),Λq​=(x,z)∑​max(wq​(x,z),0)⋅u=0⨂T−1​(δxu​​⊗δzu​​⊗Rxu​,zu​​),

the sum running over all ∣S∣T⋅2T\lvert S \rvert^T \cdot 2^T∣S∣T⋅2T pairs (x,z)(x,z)(x,z), where δ\deltaδ denotes a point mass and the big tensor product is the product measure on Ω\OmegaΩ. Under the (x,z)(x,z)(x,z)-th summand, Xu=xuX_u = x_uXu​=xu​ and Zu=zuZ_u = z_uZu​=zu​ for all uuu almost surely, and Y0,…,YT−1Y_0,\dots,Y_{T-1}Y0​,…,YT−1​ are independent with YuY_uYu​ distributed according to Rxu,zuR_{x_u,z_u}Rxu​,zu​​.

Negative weights are replaced by 000. When all quq_uqu​ with u≤T−1u \le T-1u≤T−1 lie in [0,1][0,1][0,1], no weight is negative, Λq\Lambda_qΛq​ is a probability measure, and it is the joint law of the following process: X0X_0X0​ has distribution ρ\rhoρ; each ZuZ_uZu​ is true\mathrm{true}true with probability quq_uqu​, independently of X0,Z0,…,Xu−1,Zu−1,XuX_0, Z_0, \dots, X_{u-1}, Z_{u-1}, X_uX0​,Z0​,…,Xu−1​,Zu−1​,Xu​; given the past, Xu+1X_{u+1}Xu+1​ has distribution PuZu(Xu,⋅)P_u^{Z_u}(X_u, \cdot)PuZu​​(Xu​,⋅); and, given all the XuX_uXu​ and ZuZ_uZu​, the YuY_uYu​ are independent with YuY_uYu​ distributed according to RXu,ZuR_{X_u, Z_u}RXu​,Zu​​. When some quq_uqu​ lies outside [0,1][0,1][0,1], some weights are negative and are set to 000, and Λq\Lambda_qΛq​ is then a finite measure that is in general not of total mass 111.

The function being differentiated. For a real number θ\thetaθ (any real) and a time t∈{0,…,T−1}t \in \lbrace 0,\dots,T-1 \rbracet∈{0,…,T−1}, let q(t,θ)q^{(t,\theta)}q(t,θ) be the sequence

qu(t,θ)=12  if u+k<t,qu(t,θ)=θ  if u+k≥t,q_u^{(t,\theta)} = \frac{1}{2} \ \text{ if } u + k \lt t, \qquad q_u^{(t,\theta)} = \theta \ \text{ if } u + k \ge t ,qu(t,θ)​=21​  if u+k<t,qu(t,θ)​=θ  if u+k≥t,

and let νt,θ=Λq\nu_{t,\theta} = \Lambda_qνt,θ​=Λq​ for q=q(t,θ)q = q^{(t,\theta)}q=q(t,θ). So under νt,θ\nu_{t,\theta}νt,θ​ the parameter is the fixed number 1/21/21/2 at the times uuu that precede ttt by more than kkk steps, and is θ\thetaθ at all other times uuu (the times uuu with t−k≤u<tt - k \le u \lt tt−k≤u<t, of which there are at most kkk, the time ttt itself, and all times after ttt). Define, for every real θ\thetaθ,

Jk(θ)=1T∑t=0T−1∫ΩYt dνt,θ.J_k(\theta) = \frac{1}{T} \sum_{t=0}^{T-1} \int_\Omega Y_t \ \mathrm{d}\nu_{t,\theta} .Jk​(θ)=T1​t=0∑T−1​∫Ω​Yt​ dνt,θ​.

Each summand uses its own measure νt,θ\nu_{t,\theta}νt,θ​, which depends on ttt. This is a function R→R\mathbb{R} \to \mathbb{R}R→R defined for all real θ\thetaθ. Integrals are Lebesgue (Bochner) integrals, which by library convention are 000 if the integrand is not integrable; under the hypothesis on MMM each YtY_tYt​ satisfies ∣Yt∣≤M\lvert Y_t \rvert \le M∣Yt​∣≤M almost everywhere for each measure involved.

The claimed value of the derivative. Let μ1/2=Λq\mu_{1/2} = \Lambda_qμ1/2​=Λq​ for the constant sequence qu=1/2q_u = 1/2qu​=1/2 (this is also νt,1/2\nu_{t,1/2}νt,1/2​ for every ttt). For a measure μ\muμ on Ω\OmegaΩ and an event AAA, let μ(⋅∣A)\mu(\cdot \mid A)μ(⋅∣A) denote the measure B↦μ(A)−1μ(A∩B)B \mapsto \mu(A)^{-1} \mu(A \cap B)B↦μ(A)−1μ(A∩B) (by library convention this is the zero measure if μ(A)=0\mu(A) = 0μ(A)=0; here it is used only with μ=μ1/2\mu = \mu_{1/2}μ=μ1/2​ and A={Zu=z}A = \lbrace Z_u = z \rbraceA={Zu​=z}, an event of μ1/2\mu_{1/2}μ1/2​-measure 1/21/21/2). For each time u∈{0,…,T−1}u \in \lbrace 0, \dots, T-1 \rbraceu∈{0,…,T−1} and each Boolean zzz define the real number

Quk,z=∑t : u≤t≤u+k, t≤T−1∫ΩYt dμ1/2(⋅∣Zu=z),Q_u^{k,z} = \sum_{t \ : \ u \le t \le u+k, \ t \le T-1} \int_\Omega Y_t \ \mathrm{d}\mu_{1/2}(\cdot \mid Z_u = z),Quk,z​=t : u≤t≤u+k, t≤T−1∑​∫Ω​Yt​ dμ1/2​(⋅∣Zu​=z),

the sum over the times ttt in the window from uuu to u+ku+ku+k inclusive (cut off at the last time T−1T-1T−1) of the conditional expectation of YtY_tYt​ under μ1/2\mu_{1/2}μ1/2​ given the single event {Zu=z}\lbrace Z_u = z \rbrace{Zu​=z}. The conditioning is on the value of ZuZ_uZu​ only, not on XuX_uXu​ or on anything else, so Quk,zQ_u^{k,z}Quk,z​ is a number and not a function on SSS.

Conclusion. The function Jk:R→RJ_k : \mathbb{R} \to \mathbb{R}Jk​:R→R is differentiable at the point θ=1/2\theta = 1/2θ=1/2 (in the ordinary two-sided sense), and its derivative there is

Jk′(1/2)=1T∑u=0T−1(Quk,true−Quk,false).J_k'(1/2) = \frac{1}{T} \sum_{u=0}^{T-1} \bigl( Q_u^{k,\mathrm{true}} - Q_u^{k,\mathrm{false}} \bigr).Jk′​(1/2)=T1​u=0∑T−1​(Quk,true​−Quk,false​).

Precisely: Jk(θ′)=Jk(1/2)+(θ′−1/2)⋅D+o(θ′−1/2)J_k(\theta') = J_k(1/2) + (\theta' - 1/2) \cdot D + o(\theta' - 1/2)Jk​(θ′)=Jk​(1/2)+(θ′−1/2)⋅D+o(θ′−1/2) as θ′→1/2\theta' \to 1/2θ′→1/2 in R\mathbb{R}R, where DDD is the right-hand side above. The number 1/21/21/2 appears in three places: it is hard-wired into the measures νt,θ\nu_{t,\theta}νt,θ​ for the early times, it is the parameter of the measure μ1/2\mu_{1/2}μ1/2​ used for the Quk,zQ_u^{k,z}Quk,z​, and it is the point of differentiation. No other value is addressed.

Boundary cases of kkk that the statement includes. If k=0k = 0k=0, then qu(t,θ)q_u^{(t,\theta)}qu(t,θ)​ is 1/21/21/2 for u<tu \lt tu<t and θ\thetaθ for u≥tu \ge tu≥t, and each window consists of the single time t=ut = ut=u, so Qu0,z=∫Yu dμ1/2(⋅∣Zu=z)Q_u^{0,z} = \int Y_u \ \mathrm{d}\mu_{1/2}(\cdot \mid Z_u = z)Qu0,z​=∫Yu​ dμ1/2​(⋅∣Zu​=z). If k=T−1k = T-1k=T−1 or k=Tk = Tk=T (both permitted by k≤Tk \le Tk≤T), the condition u+k<tu + k \lt tu+k<t never holds for t≤T−1t \le T-1t≤T−1, so νt,θ\nu_{t,\theta}νt,θ​ is, for every ttt, the measure Λq\Lambda_qΛq​ with constant sequence qu=θq_u = \thetaqu​=θ, and each window consists of all times ttt with u≤t≤T−1u \le t \le T-1u≤t≤T−1.

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