Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 1 — the policy gradient ∇J(1/2)\nabla J(1/2)∇J(1/2) is the average QQQ-value difference

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

The value function is J(θ)=1T∑t<TEθ[Yt]J(\theta)=\frac1T\sum_{t<T}\mathbb E_\theta[Y_t]J(θ)=T1​∑t<T​Eθ​[Yt​], and the QQQ-value of action zzz at time ttt under the experimental policy π1/2\pi_{1/2}π1/2​ is the expected cumulative reward from time ttt to the end of the horizon given that action,

Q1/2t(z)=∑u=tT−1E1/2[Yu∣Zt=z].Q_{1/2}^{t}(z)=\sum_{u=t}^{T-1}\mathbb E_{1/2}[Y_u\mid Z_t=z].Q1/2t​(z)=u=t∑T−1​E1/2​[Yu​∣Zt​=z].

Proposition. For every T≥1T\ge1T≥1, the function JJJ is differentiable at θ=1/2\theta=1/2θ=1/2 and

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

This identifies the derivative of the policy value at the balanced design with a quantity that the untruncated estimator τ^T\widehat\tau_TτT​ estimates without bias, and is the basis of the policy-gradient interpretation of the TPG estimator.

Formalization Note The QQQ-values do not depend on the state; they are expectations under the conditional law given the event {Zt=z}\{Z_t=z\}{Zt​=z}, which has probability 1/21/21/2.

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_1_policy_gradient {S : Type} [Fintype S] [MeasurableSpace S] [MeasurableSingletonClass S]
    (E : Env S) (T : ℕ) (M : ℝ) (hT : 0 < T) (hM : E.RewardBound M) :
    HasDerivAt (fun θ : ℝ => E.J T θ)
      ((1 / (T : ℝ)) * ∑ t : Fin T, (E.Q (1 / 2) T t true - E.Q (1 / 2) T 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. §4, pp. 13–14, Proposition 1, eqs. (6)–(7); proof in Appendix G.1, pp. 42–43.
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.

  • A natural number TTT, with the hypothesis 0<T0 \lt T0<T.

  • 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 t=0,1,…,T−1t = 0, 1, \dots, T-1t=0,1,…,T−1.

The measure μθ\mu_\thetaμθ​. Fix a real number θ\thetaθ (any real number, not only one in [0,1][0,1][0,1]). For a sequence 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

wθ(x,z)=ρ(x0)⋅∏s=0T−2Pszs(xs,xs+1)⋅∏t=0T−1bθ(zt),bθ(true)=θ,bθ(false)=1−θ.w_\theta(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} b_\theta(z_t), \qquad b_\theta(\mathrm{true}) = \theta, \quad b_\theta(\mathrm{false}) = 1-\theta .wθ​(x,z)=ρ(x0​)⋅s=0∏T−2​Pszs​​(xs​,xs+1​)⋅t=0∏T−1​bθ​(zt​),bθ​(true)=θ,bθ​(false)=1−θ.

(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

μθ=∑(x,z)max⁡(wθ(x,z),0)⋅⨂t=0T−1(δxt⊗δzt⊗Rxt,zt),\mu_\theta = \sum_{(x,z)} \max\bigl(w_\theta(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),μθ​=(x,z)∑​max(wθ​(x,z),0)⋅t=0⨂T−1​(δxt​​⊗δzt​​⊗Rxt​,zt​​),

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, Xt=xtX_t = x_tXt​=xt​ and Zt=ztZ_t = z_tZt​=zt​ for all ttt almost surely, and Y0,…,YT−1Y_0,\dots,Y_{T-1}Y0​,…,YT−1​ are independent with YtY_tYt​ distributed according to Rxt,ztR_{x_t,z_t}Rxt​,zt​​.

Negative weights are replaced by 000. When 0≤θ≤10 \le \theta \le 10≤θ≤1 no weight is negative, μθ\mu_\thetaμθ​ is a probability measure, and it is the joint law of the following process: X0X_0X0​ has distribution ρ\rhoρ; each ZtZ_tZt​ is true\mathrm{true}true with probability θ\thetaθ, independently of X0,Z0,…,Xt−1,Zt−1,XtX_0, Z_0, \dots, X_{t-1}, Z_{t-1}, X_tX0​,Z0​,…,Xt−1​,Zt−1​,Xt​; given the past, Xt+1X_{t+1}Xt+1​ has distribution PtZt(Xt,⋅)P_t^{Z_t}(X_t, \cdot)PtZt​​(Xt​,⋅); and, given all the XtX_tXt​ and ZtZ_tZt​, the YtY_tYt​ are independent with YtY_tYt​ distributed according to RXt,ZtR_{X_t, Z_t}RXt​,Zt​​. When θ\thetaθ lies outside [0,1][0,1][0,1] some weights wθ(x,z)w_\theta(x,z)wθ​(x,z) are negative and are set to 000, so μθ\mu_\thetaμθ​ is then a finite measure that is in general not of total mass 111.

The function being differentiated. For every real θ\thetaθ,

J(θ)=1T∑t=0T−1∫ΩYt dμθ.J(\theta) = \frac{1}{T} \sum_{t=0}^{T-1} \int_\Omega Y_t \ \mathrm{d}\mu_\theta .J(θ)=T1​t=0∑T−1​∫Ω​Yt​ dμθ​.

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. 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

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

that is, the sum over all times ttt with u≤t≤T−1u \le t \le T-1u≤t≤T−1 (the term t=ut = ut=u included) 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 QuzQ_u^{z}Quz​ is a number and not a function on SSS.

Conclusion. The function J:R→RJ : \mathbb{R} \to \mathbb{R}J: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

J′(1/2)=1T∑u=0T−1(Qutrue−Qufalse).J'(1/2) = \frac{1}{T} \sum_{u=0}^{T-1} \bigl( Q_u^{\mathrm{true}} - Q_u^{\mathrm{false}} \bigr).J′(1/2)=T1​u=0∑T−1​(Qutrue​−Qufalse​).

Precisely: J(θ′)=J(1/2)+(θ′−1/2)⋅D+o(θ′−1/2)J(\theta') = J(1/2) + (\theta' - 1/2) \cdot D + o(\theta' - 1/2)J(θ′)=J(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 point of differentiation is the fixed number 1/21/21/2 and the quantities QuzQ_u^{z}Quz​ are computed under μ1/2\mu_{1/2}μ1/2​; no other value of the parameter is addressed.

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