Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Markov structure of the trajectory law: paths, head and tail, restarted environment, state distribution under time-varying randomization

Definition
TPG_Markov

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

causal-inferencemarkov-chainnonstationaritypolicy-gradienttreatment-effect

Auxiliary objects for working with the trajectory law of TPG_Model. Time is t=0,…,T−1t=0,\dots,T-1t=0,…,T−1 (the source's t+1t+1t+1).

  1. Path embedding (embedPath x z y): the trajectory (xt,zt,yt)t<T(x_t,z_t,y_t)_{t<T}(xt​,zt​,yt​)t<T​ with state path xxx, action path zzz and rewards yyy.

  2. Head and tail (headTraj m n, tailTraj m n): for a trajectory of length m+nm+nm+n, its first mmm time steps, and its last nnn time steps re-indexed from 000.

  3. Reward law along a path (Env.rewardLaw x z): the product measure ⨂t<TR(⋅∣xt,zt)\bigotimes_{t<T}R(\cdot\mid x_t,z_t)⨂t<T​R(⋅∣xt​,zt​) on RT\mathbb R^TRT, i.e. the joint law of the rewards given the state and action paths.

  4. Restarted environment (Env.shift m a): the environment whose kernel at its time ttt is Pzm+tP^{m+t}_zPzm+t​, whose initial distribution is the point mass at the state aaa, and whose reward laws are unchanged. Its trajectory law is the law of the original process from time mmm on, started at Xm=aX_m=aXm​=a.

  5. State distribution under time-varying randomization (Env.stateVec q t): the row vector

μqt=ρ⊤Pq00Pq11⋯Pqt−1t−1,Pθs=θP1s+(1−θ)P0s,\mu_q^t=\rho^\top P^0_{q_0}P^1_{q_1}\cdots P^{t-1}_{q_{t-1}},\qquad P^s_{\theta}=\theta P^s_1+(1-\theta)P^s_0 ,μqt​=ρ⊤Pq0​0​Pq1​1​⋯Pqt−1​t−1​,Pθs​=θP1s​+(1−θ)P0s​,

which is the distribution of XtX_tXt​ when the action at time sss is treatment with probability qsq_sqs​.

These objects are used to state the mixture representation of the trajectory law, its Markov property, and the matrix formulas for expected rewards.

Formalization Note Env.shift and Env.stateVec need decidable equality on SSS (for the point mass and the identity matrix).

Definition code
import Mathlib
import Definitions.Def_TPG_Model

open MeasureTheory ProbabilityTheory
open scoped BigOperators ENNReal

namespace TPG

/-- The trajectory whose state path is `x`, whose action path is `z` and whose rewards are `y`. -/
def embedPath {S : Type} {T : ℕ} (x : Fin T → S) (z : Fin T → Bool) (y : Fin T → ℝ) :
    Traj S T :=
  fun t => (x t, z t, y t)

/-- The first `m` time steps of a trajectory of length `m + n`. -/
def headTraj {S : Type} (m n : ℕ) (ω : Traj S (m + n)) : Traj S m :=
  fun i => ω (Fin.castAdd n i)

/-- The last `n` time steps of a trajectory of length `m + n`, re-indexed from `0`. -/
def tailTraj {S : Type} (m n : ℕ) (ω : Traj S (m + n)) : Traj S n :=
  fun j => ω (Fin.natAdd m j)

section

variable {S : Type} [Fintype S]

/-- Joint law of the rewards along a fixed state path `x` and action path `z`:
independent coordinates with `Y_t ∼ R(· | x_t, z_t)`. -/
noncomputable def Env.rewardLaw (E : Env S) {T : ℕ} (x : Fin T → S) (z : Fin T → Bool) :
    Measure (Fin T → ℝ) :=
  Measure.pi (fun t => E.R (x t) (z t))

/-- The environment restarted at time `m` from the state `a`: the kernel used at its time `t`
is the original kernel of time `m + t`, the initial distribution is the point mass at `a`, and
the reward distributions are unchanged. -/
noncomputable def Env.shift [DecidableEq S] (E : Env S) (m : ℕ) (a : S) : Env S where
  P := fun t => E.P (m + t)
  P_nonneg := fun t => E.P_nonneg (m + t)
  P_row_sum := fun t => E.P_row_sum (m + t)
  ρ := fun x => if x = a then 1 else 0
  ρ_nonneg := fun x => by split_ifs <;> norm_num
  ρ_sum := by simp
  R := E.R
  R_prob := E.R_prob

/-- Row distribution of the state at time `t` when the action at time `s` is treatment with
probability `q s`: `ρᵀ P_{q_0}^0 P_{q_1}^1 ⋯ P_{q_{t-1}}^{t-1}`. -/
noncomputable def Env.stateVec [DecidableEq S] (E : Env S) (q : ℕ → ℝ) (t : ℕ) : S → ℝ :=
  Matrix.vecMul E.ρ ((List.range t).map (fun s => E.PMix (q s) s)).prod

end

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 formalizes §2.2, pp. 8–9 (Markov process, rewards), Appendix A.1, p. 27 (multi-step kernels), and the expectation E_{a_t,x} of the process started at X_{a_t}=x used in Appendix F.1, p. 40.

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