Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Derivative of the expected reward along a partially varying randomization sequence

Proved
TPG.hasDerivAt_meanReward

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

causal-inferencemarkov-chainnonstationaritypolicy-gradienttreatment-effect

Let mt(q)=ρ⊤Pq00Pq11⋯Pqt−1t−1 rqtm_t(q)=\rho^\top P^0_{q_0}P^1_{q_1}\cdots P^{t-1}_{q_{t-1}}\,r_{q_t}mt​(q)=ρ⊤Pq0​0​Pq1​1​⋯Pqt−1​t−1​rqt​​ be the expected reward at time ttt under a sequence qqq of treatment probabilities, with Pθs=θP1s+(1−θ)P0sP^s_\theta=\theta P^s_1+(1-\theta)P^s_0Pθs​=θP1s​+(1−θ)P0s​ and rθ=θr1+(1−θ)r0r_\theta=\theta r_1+(1-\theta)r_0rθ​=θr1​+(1−θ)r0​ (time is 000-indexed).

Fix a set A⊆NA\subseteq\mathbb NA⊆N of times and a sequence ccc, and for a real number θ\thetaθ let qθq^\thetaqθ be the sequence equal to θ\thetaθ at the times in AAA and to csc_scs​ at the other times.

Lemma. The function θ↦mt(qθ)\theta\mapsto m_t(q^\theta)θ↦mt​(qθ) is differentiable at every θ0∈R\theta_0\in\mathbb Rθ0​∈R, with

ddθ mt(qθ)∣θ=θ0=∑u≤t, u∈A(mt(qθ0, u→1)−mt(qθ0, u→0)),\frac{d}{d\theta}\,m_t(q^\theta)\Big|_{\theta=\theta_0}=\sum_{u\le t,\ u\in A}\Bigl(m_t\bigl(q^{\theta_0,\,u\to1}\bigr)-m_t\bigl(q^{\theta_0,\,u\to0}\bigr)\Bigr),dθd​mt​(qθ)​θ=θ0​​=u≤t, u∈A∑​(mt​(qθ0​,u→1)−mt​(qθ0​,u→0)),

where qθ0, u→bq^{\theta_0,\,u\to b}qθ0​,u→b is qθ0q^{\theta_0}qθ0​ with the entry at time uuu replaced by bbb.

Since mtm_tmt​ is affine in each coordinate, its derivative along a diagonal direction is the sum of the one-coordinate differences. With A=NA=\mathbb NA=N this is the policy gradient of the value function; with A={u:u+k≥t}A=\{u:u+k\ge t\}A={u:u+k≥t} it is the truncated policy gradient.

Preamble
import Mathlib
import Definitions.Def_TPG_Model
import Definitions.Def_TPG_Estimators
import Definitions.Def_TPG_Markov
import Definitions.Def_TPG_Bridge

open MeasureTheory ProbabilityTheory
open scoped BigOperators ENNReal
Formal statement
namespace TPG
theorem hasDerivAt_meanReward {S : Type} [Fintype S] [DecidableEq S]
    (E : Env S) (t : ℕ) (A : ℕ → Prop) [DecidablePred A] (c : ℕ → ℝ) (θ₀ : ℝ) :
    HasDerivAt (fun θ : ℝ => E.meanReward (fun s => if A s then θ else c s) t)
      (∑ u ∈ Finset.range (t + 1),
        if A u then
          (E.meanReward (Function.update (fun s => if A s then θ₀ else c s) u 1) t
            - E.meanReward (Function.update (fun s => if A s then θ₀ else c s) u 0) t)
        else 0)
      θ₀ := 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. Auxiliary statement, not a numbered result of the paper: it is the product rule for d/dθ ρ^⊤ P_θ^{a→b} r_θ of Appendix A.3, p. 27, as used in Appendices G.1, G.3 and G.4, pp. 42–46.

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