§2 — nonstationary Markovian treatment model: Assumption 1 (mixing), kernel deviation , trajectory law, value function , GATE
DefinitionTPG_ModelThis definition file fixes the dynamic model of treatment of the source (§2.2–2.3) and the objects built from it.
Convention. Time is indexed by ; the source writes , so time here is the source's time .
-
Total variation. For real vectors on a finite set , (
tvDist). A probability vector is a nonnegative vector summing to one (IsProbVec). -
Environment (
Env S). A finite state space with, for every time and action (falseis control,trueis treatment), a transition matrix with nonnegative entries and rows summing to one, so that ; a distribution of the initial state ; and for every state and action a probability distribution on of the reward. -
Bounded rewards (
Env.RewardBound M): for all . The mean rewards are (Env.r) and (Env.rMix). -
Kernels under : (
Env.PMix), and the multi-step kernel , equal to the identity when (Env.PProd). -
Assumption 1, mixing time (
Env.Mixing T γ): for every , every action and every pair of probability vectors on ,
The condition is a separate hypothesis of each theorem.
-
Kernel deviation (
Env.delta T): . -
Trajectories. A trajectory of horizon is (
Traj S T, with coordinate mapsX,Z,Y). For a sequence of treatment probabilities,Env.pathWeightis the probability of a state path and an action path ,
and Env.trajLaw T q is the law of the trajectory when , the actions are independent with , the state follows , and, given the states and actions, the rewards are independent with . Env.expLaw T θ is the case : the law under the Bernoulli randomization policy .
- Value function and estimand (
Env.J,Env.gate):
is the global average treatment effect (GATE).
Every statement of the mission is expressed through these objects.
Formalization Note Kernels are stored for all ; a statement with horizon involves only for , which are the source's . The trajectory law is constructed as a finite mixture, over the pairs of a state path and an action path, of products of point masses and reward laws. For negative path weights are replaced by and the result is not a probability law; no statement uses such except through values of away from the point of interest. For the averages and equal .
import Mathlib
open MeasureTheory ProbabilityTheory
open scoped BigOperators ENNReal
namespace TPG
/-- Total variation distance between two real vectors on a finite set,
with the convention `‖f - g‖_TV = (1/2) ‖f - g‖₁`. -/
noncomputable def tvDist {S : Type} [Fintype S] (f g : S → ℝ) : ℝ :=
(1 / 2) * ∑ x, |f x - g x|
/-- `f` is a probability distribution on the finite set `S`. -/
def IsProbVec {S : Type} [Fintype S] (f : S → ℝ) : Prop :=
(∀ x, 0 ≤ f x) ∧ ∑ x, f x = 1
/-- A nonstationary Markovian environment with finite state space `S` and binary action
(`true` = treatment, `false` = control). Time is indexed by `t = 0, 1, 2, …`
(the source's time `t + 1`).
* `P t z` is the transition matrix used between times `t` and `t + 1` under action `z`;
* `ρ` is the distribution of the initial state;
* `R x z` is the distribution of the real-valued reward when action `z` is taken in state `x`. -/
structure Env (S : Type) [Fintype S] where
P : ℕ → Bool → Matrix S S ℝ
P_nonneg : ∀ (t : ℕ) (z : Bool) (x x' : S), 0 ≤ P t z x x'
P_row_sum : ∀ (t : ℕ) (z : Bool) (x : S), ∑ x', P t z x x' = 1
ρ : S → ℝ
ρ_nonneg : ∀ x : S, 0 ≤ ρ x
ρ_sum : ∑ x, ρ x = 1
R : S → Bool → Measure ℝ
R_prob : ∀ (x : S) (z : Bool), IsProbabilityMeasure (R x z)
instance {S : Type} [Fintype S] (E : Env S) (x : S) (z : Bool) :
IsProbabilityMeasure (E.R x z) := E.R_prob x z
section Kernels
variable {S : Type} [Fintype S]
/-- Rewards are almost surely bounded by `M`: `R([-M, M] | x, z) = 1` for all `x, z`. -/
def Env.RewardBound (E : Env S) (M : ℝ) : Prop :=
∀ (x : S) (z : Bool), E.R x z (Set.Icc (-M) M) = 1
/-- Expected reward `r(x, z) = ∫ y R(dy | x, z)`. -/
noncomputable def Env.r (E : Env S) (z : Bool) (x : S) : ℝ :=
∫ y, y ∂(E.R x z)
/-- Expected reward `r_θ(x) = θ r(x, 1) + (1 - θ) r(x, 0)` under the policy `π_θ`. -/
noncomputable def Env.rMix (E : Env S) (θ : ℝ) (x : S) : ℝ :=
θ * E.r true x + (1 - θ) * E.r false x
/-- Transition matrix `P_θ^t = θ P_1^t + (1 - θ) P_0^t` under the policy `π_θ`. -/
noncomputable def Env.PMix (E : Env S) (θ : ℝ) (t : ℕ) : Matrix S S ℝ :=
θ • E.P t true + (1 - θ) • E.P t false
/-- Multi-step kernel `P_θ^{a → b} = P_θ^a P_θ^{a+1} ⋯ P_θ^{b-1}`
(the identity matrix when `b ≤ a`). -/
noncomputable def Env.PProd [DecidableEq S] (E : Env S) (θ : ℝ) (a b : ℕ) : Matrix S S ℝ :=
((List.Ico a b).map (fun u => E.PMix θ u)).prod
/-- Assumption 1 (mixing time) over the horizon `T` with contraction constant `γ`:
for every time `t < T`, every action `z` and every pair of probability distributions
`f, f'` on `S`, `‖f' P_z^t - f P_z^t‖_TV ≤ γ ‖f' - f‖_TV`. -/
def Env.Mixing (E : Env S) (T : ℕ) (γ : ℝ) : Prop :=
∀ t : ℕ, t < T → ∀ (z : Bool) (f f' : S → ℝ), IsProbVec f → IsProbVec f' →
tvDist (Matrix.vecMul f' (E.P t z)) (Matrix.vecMul f (E.P t z)) ≤ γ * tvDist f' f
/-- Kernel deviation
`δ = sup_{t < T} sup_x ‖P_1^t(x, ·) - P_0^t(x, ·)‖_TV` over the horizon `T`. -/
noncomputable def Env.delta (E : Env S) (T : ℕ) : ℝ :=
⨆ t : Fin T, ⨆ x : S, tvDist (E.P (t : ℕ) true x) (E.P (t : ℕ) false x)
end Kernels
section Trajectory
variable {S : Type} [Fintype S]
/-- A trajectory `(X_t, Z_t, Y_t)_{t < T}` of states, actions and rewards. -/
abbrev Traj (S : Type) (T : ℕ) : Type := Fin T → S × Bool × ℝ
/-- State at time `t`. -/
def X {T : ℕ} (t : Fin T) (ω : Traj S T) : S := (ω t).1
/-- Action (treatment indicator) at time `t`. -/
def Z {T : ℕ} (t : Fin T) (ω : Traj S T) : Bool := (ω t).2.1
/-- Reward at time `t`. -/
def Y {T : ℕ} (t : Fin T) (ω : Traj S T) : ℝ := (ω t).2.2
/-- Probability of the state path `x` and action path `z` over the horizon `T` when the
initial state has distribution `ρ`, the action at time `t` is treatment with probability
`q t` independently of everything else, and the state moves from time `s` to time `s + 1`
according to `P s (z s)`:
`ρ(x_0) · ∏_{s + 1 < T} P_{z_s}^s(x_s, x_{s+1}) · ∏_{t < T} (q_t if z_t else 1 - q_t)`. -/
noncomputable def Env.pathWeight (E : Env S) (T : ℕ) (q : ℕ → ℝ)
(x : Fin T → S) (z : Fin T → Bool) : ℝ :=
(∏ t : Fin T, if (t : ℕ) = 0 then E.ρ (x t) else 1)
* (∏ s : Fin T, ∏ t : Fin T,
if (s : ℕ) + 1 = (t : ℕ) then E.P (s : ℕ) (z s) (x s) (x t) else 1)
* (∏ t : Fin T, if z t then q (t : ℕ) else 1 - q (t : ℕ))
/-- Law of the trajectory `(X_t, Z_t, Y_t)_{t < T}` when the action at time `t` is treatment
with probability `q t`: a mixture over state/action paths, weighted by `pathWeight`, of the
laws under which the path is fixed and the rewards are independent with
`Y_t ∼ R(· | x_t, z_t)`. -/
noncomputable def Env.trajLaw [MeasurableSpace S] (E : Env S) (T : ℕ) (q : ℕ → ℝ) :
Measure (Traj S T) :=
∑ p : (Fin T → S) × (Fin T → Bool),
ENNReal.ofReal (E.pathWeight T q p.1 p.2) •
Measure.pi (fun t : Fin T =>
(Measure.dirac (p.1 t)).prod ((Measure.dirac (p.2 t)).prod (E.R (p.1 t) (p.2 t))))
/-- Law of the trajectory under the Bernoulli randomization policy `π_θ`
(every action is treatment with probability `θ`). -/
noncomputable def Env.expLaw [MeasurableSpace S] (E : Env S) (T : ℕ) (θ : ℝ) :
Measure (Traj S T) :=
E.trajLaw T (fun _ => θ)
/-- Value function `J(θ) = (1/T) ∑_t E_{π_θ}[Y_t]`. -/
noncomputable def Env.J [MeasurableSpace S] (E : Env S) (T : ℕ) (θ : ℝ) : ℝ :=
(1 / (T : ℝ)) * ∑ t : Fin T, ∫ ω, Y t ω ∂(E.expLaw T θ)
/-- Global average treatment effect
`τ = (1/T) ∑_t (E_{π_1}[Y_t] - E_{π_0}[Y_t])`. -/
noncomputable def Env.gate [MeasurableSpace S] (E : Env S) (T : ℕ) : ℝ :=
(1 / (T : ℝ)) * ∑ t : Fin T,
((∫ ω, Y t ω ∂(E.expLaw T 1)) - ∫ ω, Y t ω ∂(E.expLaw T 0))
end Trajectory
end TPG
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Read-back of the definition file TPG_Model
All declarations live in the namespace TPG. Throughout, "Boolean" means an element of the two-point set , , and denotes the set of natural numbers below (empty when ). Declarations are listed in file order.
tvDist (definition, a real number). Let be a finite type and let be two arbitrary real-valued functions on (they are not required to be nonnegative or to sum to ). The real number is defined by
If is empty the sum is empty and the value is .
IsProbVec (definition, a proposition). Let be a finite type and . The proposition is the conjunction of two conditions: for every , and . If is empty the sum is , so no function satisfies the proposition.
Env (structure). Let be a finite type. An element of is a bundle of the following eight fields (three pieces of data, each followed by the conditions imposed on it).
P: for every natural number (all natural numbers, with no upper limit) and every Boolean , a real matrix with rows and columns indexed by ; its entry in row , column is written .P_nonneg: for every , every Boolean and all : .P_row_sum: for every , every Boolean and every : (every row sums to ).ρ: a function .ρ_nonneg: for every : .ρ_sum: .R: for every and every Boolean , a measure on (with its Borel -algebra). This family is indexed by and only; it has no dependence on a time index.R_prob: for every and every Boolean , is a probability measure, i.e. .
Nothing else is required: in particular no boundedness, moment or support condition is imposed on the measures . If is empty, the condition ρ_sum reads , so has no elements; hence the existence of any forces to be nonempty.
(unnamed instance). Let be a finite type, , and a Boolean. The declaration records that the measure of is a probability measure, the justification being the field R_prob of applied to and . It adds no new mathematical content; it makes this fact available automatically wherever a probability measure is expected.
Env.RewardBound (definition, a proposition). Let be a finite type, with reward measures on (one probability measure for each and Boolean ), and let be an arbitrary real number (its sign is not constrained). The proposition says: for every and every Boolean ,
where is the closed interval. If this interval is empty, its measure is , and the proposition is false (recall that is necessarily nonempty once exists).
Env.r (definition, a real number). Let be a finite type, with reward measures , let be a Boolean and (the arguments are taken in this order: first , then ). The real number is
the integral of the identity function against the probability measure . No integrability hypothesis is part of the definition; the integral is the Bochner integral, which by convention has the value when the identity function is not integrable with respect to (that is, when ).
Env.rMix (definition, a real number). Let be a finite type, , an arbitrary real number (not required to lie in ), and . With as in Env.r (value if the identity is not -integrable), the definition is
Env.PMix (definition, a real matrix). Let be a finite type, with matrices , let be an arbitrary real number (not required to lie in ) and . The matrix is the entrywise combination
For one of the two coefficients is negative, so entries of can be negative.
Env.PProd (definition, a real matrix). Let be a finite type with decidable equality (used to form the identity matrix), , arbitrary, and . Writing as in Env.PMix, the definition is the ordered matrix product over the indices , taken in increasing order from left to right:
The number of factors is computed with truncated subtraction of natural numbers: if there are no factors and the value is the identity matrix on ; if the value is the single matrix .
Env.Mixing (definition, a proposition). Let be a finite type, with matrices , , and an arbitrary real number (not required to be nonnegative or less than ). For a function and a matrix write for the row-vector-times-matrix product, . The proposition says: for every natural number with , every Boolean , and all functions such that both and have nonnegative entries summing to ,
The inequality is non-strict. Only the matrices with time index are constrained (both Boolean values, each separately); if the proposition holds vacuously for every .
Env.delta (definition, a real number). Let be a finite type, with matrices , and . The definition is
i.e. for each time and each row index , half the -distance between row of and row of , then the supremum over and over . The suprema are suprema of real numbers with the convention that the supremum over an empty index set is ; consequently . For both index sets are finite and nonempty, so the suprema are maxima.
Traj (abbreviation, a type). Let be any type (no finiteness is required here) and . Then is the set of all functions
i.e. sequences of length of triples (element of , Boolean, real number). For this set has exactly one element (the empty sequence).
X (definition, an element of ). Let be any type (the definition does not use finiteness of ), , and , i.e. is a length- sequence of triples in . Then is the first component of the triple . (When there is no admissible .)
Z (definition, a Boolean). Let be any type (finiteness not used), , and , a length- sequence of triples in . Then is the second (Boolean) component of the triple .
Y (definition, a real number). Let be any type (finiteness not used), , and , a length- sequence of triples in . Then is the third (real) component of the triple .
Env.pathWeight (definition, a real number). Let be a finite type, with matrices and initial vector , let , let be an arbitrary sequence of real numbers (the values are not required to lie in ), let and . The real number is the product of three factors,
where
Evaluating the products, for this is
Literal consequences: the factor for the step from time to time uses the matrix with time index and the Boolean of the earlier time ; the matrices with do not occur, and the last Boolean occurs only in the third factor; only are used. For there is no transition factor and . For all three products are empty and (for the unique empty and ). If some lies outside , then can be negative.
Env.trajLaw (definition, a measure on ). Let be a finite type that is in addition equipped with a -algebra, supplied as an arbitrary extra structure (nothing requires it to be the -algebra of all subsets). Let with matrices , initial vector and reward probability measures on ; let and let be an arbitrary real sequence. The space carries the product -algebra (the given -algebra on , all subsets of the Booleans, the Borel sets of ). The measure is the following finite sum, taken over all pairs with and :
where:
- is the path weight of
Env.pathWeight(equal to when ); - the scalar in front of each term is the weight converted to an extended nonnegative real by replacing every negative value with ; so pairs with negative weight contribute nothing, rather than a negative amount;
- is the unit point mass at on , the unit point mass at on the Booleans, and their product with on ; the outer is the product measure over the time coordinates.
Thus each term is a measure under which the state and Boolean coordinates are deterministically and and the real coordinates are independent with (the reward measure depends on the state and Boolean at the same time , and not on itself). When for all , every weight is nonnegative, no clipping occurs, the weights sum to , and is the joint law of the following process: ; at each time , is with probability and with probability , drawn independently of everything before it (its distribution depends on only, not on the states); is drawn from row of ; and is drawn from . When some with lies outside , some weights may be negative and are replaced by , and is then in general not a probability measure. For the space is a single point, there is exactly one pair , its weight is , and is the unit mass on that point.
Env.expLaw (definition, a measure on ). Let be a finite type equipped with an arbitrary -algebra, , and an arbitrary real number (not required to lie in ). The measure is the measure of Env.trajLaw for the constant sequence for all :
the sum being over all and , with
(and when ). Here denotes a unit point mass, are the reward probability measures of , and each summand makes the state and Boolean coordinates equal to and and the real coordinates independent with . For this is the law of the process in which , each is independently with probability , is drawn from row of , and . For only sequences that are constantly have nonzero weight, and for only those constantly . For negative weights are replaced by and is in general not a probability measure.
Env.J (definition, a real number). Let be a finite type equipped with an arbitrary -algebra, , and arbitrary. Let be the measure of Env.expLaw on length- trajectories (for : , each independently with probability , drawn from row of , ; for other , the same formula with negative path weights replaced by ), and let be the real component of at time . The definition is
Conventions that apply literally: for the factor is , which equals , and the sum is empty, so . Each integral is a Bochner integral with no integrability hypothesis; it has the value whenever is not integrable with respect to (no bound or moment condition on the reward measures is assumed in this definition). For the integrals are taken against a measure that need not have total mass .
Env.gate (definition, a real number). Let be a finite type equipped with an arbitrary -algebra, and . Let and be the measures of Env.expLaw for and on length- trajectories. Explicitly, is the law of the process with , for all , drawn from row of and ; and is the same with in place of throughout. With the real component of the trajectory at time , the definition is
For the value is (since and the sum is empty). Each integral is a Bochner integral with value when is not integrable under the respective measure; no integrability is assumed. Distributing the finite sum, this number equals with as in Env.J.
Confirmed by the mission captain (proposal self-audit).