TPG and reward-corrected estimators, -values and truncated policy values — eqs. (3), (7), (9)–(11), Appendices D–E
DefinitionTPG_EstimatorsEstimators and population quantities of the source, built on the model of TPG_Model. Time is (the source's ), and is expectation under the Bernoulli randomization policy .
-
Score (
score): for . At this is the weight . -
TPG estimator (
tpgEst θ T k), eqs. (3) and (11):
The estimator of the main text is the case , and is the difference-in-means estimator.
- -values (
Env.Q,Env.Qk), eqs. (7) and (10):
- Truncated policy value (
Env.truncLaw,Env.Jk), eq. (9). For a reward time , the hypothetical truncated policy uses treatment probability at the times and from time on; is the law of under it, and
- Matrix form for a general experimental allocation (
Env.stateDist,Env.JkGen), Appendix D. With the distribution of under and ,
-
Constants (
Psi,Env.rDiffNorm): with , and . -
Reward-corrected estimator (
rcWeight,rcEst), Appendix E.1: with ,
These are the objects of Theorem 1 and Propositions 1–6.
Formalization Note Expectations given are integrals against the conditional measure , which is the zero measure when ; this happens only for . The truncated policy of item 4 keeps probability after time , which does not affect the law of . In item 5, is truncated subtraction of natural numbers, i.e. . Scores and weights divide by and and are used only for .
import Mathlib
import Definitions.Def_TPG_Model
open MeasureTheory ProbabilityTheory
open scoped BigOperators ENNReal
namespace TPG
variable {S : Type} [Fintype S]
/-- Bernoulli assignment score `s_θ(z) = z/θ - (1 - z)/(1 - θ)`.
At `θ = 1/2` it is the weight `1{z = 1}/(1/2) - 1{z = 0}/(1/2)`. -/
noncomputable def score (θ : ℝ) (z : Bool) : ℝ :=
if z then 1 / θ else -(1 / (1 - θ))
/-- Truncated policy gradient (TPG) estimator with truncation size `k` for data collected
under `π_θ`:
`(1/T) ∑_{u < T} s_θ(Z_u) ∑_{u ≤ t ≤ u + k, t < T} Y_t`.
The estimator `τ̂_k` of the main text is `tpgEst (1/2) T k`. -/
noncomputable def tpgEst (θ : ℝ) (T k : ℕ) (ω : Traj S T) : ℝ :=
(1 / (T : ℝ)) * ∑ u : Fin T, score θ (Z u ω) *
∑ t : Fin T, if (u : ℕ) ≤ (t : ℕ) ∧ (t : ℕ) ≤ (u : ℕ) + k then Y t ω else 0
/-- `Q`-value of action `z` at time `u` under `π_θ`:
`Q_θ^u(z) = ∑_{u ≤ t < T} E_θ[Y_t | Z_u = z]`. -/
noncomputable def Env.Q [MeasurableSpace S] (E : Env S) (θ : ℝ) (T : ℕ) (u : Fin T)
(z : Bool) : ℝ :=
∑ t : Fin T, if (u : ℕ) ≤ (t : ℕ) then
∫ ω, Y t ω ∂(ProbabilityTheory.cond (E.expLaw T θ) {ω | Z u ω = z}) else 0
/-- Truncated `Q`-value of action `z` at time `u` under `π_θ`:
`Q_θ^{u,k}(z) = ∑_{u ≤ t ≤ u + k, t < T} E_θ[Y_t | Z_u = z]`. -/
noncomputable def Env.Qk [MeasurableSpace S] (E : Env S) (θ : ℝ) (T k : ℕ) (u : Fin T)
(z : Bool) : ℝ :=
∑ t : Fin T, if (u : ℕ) ≤ (t : ℕ) ∧ (t : ℕ) ≤ (u : ℕ) + k then
∫ ω, Y t ω ∂(ProbabilityTheory.cond (E.expLaw T θ) {ω | Z u ω = z}) else 0
/-- Law of the trajectory under the hypothetical truncated policy for reward time `t`:
actions at times `u` with `u + k < t` are treatment with probability `1/2`, and actions at
all later times are treatment with probability `θ`. -/
noncomputable def Env.truncLaw [MeasurableSpace S] (E : Env S) (T k t : ℕ) (θ : ℝ) :
Measure (Traj S T) :=
E.trajLaw T (fun u => if u + k < t then 1 / 2 else θ)
/-- Truncated policy value function
`J_k(θ) = (1/T) ∑_t E_{L_θ^{t,k}}[Y_t]`. -/
noncomputable def Env.Jk [MeasurableSpace S] (E : Env S) (T k : ℕ) (θ : ℝ) : ℝ :=
(1 / (T : ℝ)) * ∑ t : Fin T, ∫ ω, Y t ω ∂(E.truncLaw T k (t : ℕ) θ)
/-- Row distribution `μ_q^t = ρᵀ P_q^{0 → t}` of the state at time `t` under `π_q`. -/
noncomputable def Env.stateDist [DecidableEq S] (E : Env S) (q : ℝ) (t : ℕ) : S → ℝ :=
Matrix.vecMul E.ρ (E.PProd q 0 t)
/-- Hypothetical truncated policy value under the experimental allocation `θ`:
`J_{k,θ}(q) = (1/T) ∑_{t < T} μ_θ^{a_t} P_q^{a_t → t} r_q` with `a_t = max(0, t - k)`. -/
noncomputable def Env.JkGen [DecidableEq S] (E : Env S) (T k : ℕ) (θ q : ℝ) : ℝ :=
(1 / (T : ℝ)) * ∑ t : Fin T,
dotProduct
(Matrix.vecMul (E.stateDist θ ((t : ℕ) - k)) (E.PProd q ((t : ℕ) - k) (t : ℕ)))
(E.rMix q)
/-- `Ψ_k(γ) = ∑_{j=0}^{k-2} (j + 1) γ^j`, with `Ψ_0 = Ψ_1 = 0`. -/
noncomputable def Psi (k : ℕ) (γ : ℝ) : ℝ :=
∑ j ∈ Finset.range k, if j + 2 ≤ k then ((j : ℝ) + 1) * γ ^ j else 0
/-- `‖r_1 - r_0‖_∞ = sup_x |r(x, 1) - r(x, 0)|`. -/
noncomputable def Env.rDiffNorm (E : Env S) : ℝ :=
⨆ x : S, |E.r true x - E.r false x|
/-- Additional importance weight of the reward-corrected estimator,
`w_θ(z) = (1 - θ) z / θ + θ (1 - z) / (1 - θ)`. -/
noncomputable def rcWeight (θ : ℝ) (z : Bool) : ℝ :=
if z then (1 - θ) / θ else θ / (1 - θ)
/-- Reward-corrected (RC) estimator
`(1/T) ∑_{u < T} s_θ(Z_u) [Y_u + ∑_{u < t ≤ u + k, t < T} w_θ(Z_t) Y_t]`. -/
noncomputable def rcEst (θ : ℝ) (T k : ℕ) (ω : Traj S T) : ℝ :=
(1 / (T : ℝ)) * ∑ u : Fin T, score θ (Z u ω) *
(Y u ω + ∑ t : Fin T,
if (u : ℕ) < (t : ℕ) ∧ (t : ℕ) ≤ (u : ℕ) + k then rcWeight θ (Z t ω) * Y t ω else 0)
end TPG
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Read-back: definition file TPG_Estimators (namespace TPG)
Twelve declarations, in file order. Each block below is self-contained and restates everything it uses.
score (TPG.score). Inputs: a real number and a Boolean . Output: the real number
There is no hypothesis on : it is an arbitrary real number, so , , and are all allowed. Division is the library's total division on , in which . Consequently (while ), and (while ). For the value is positive, and for the value is negative; the formulas are applied exactly as written. The definition involves no state space, no environment and no probability measure.
tpgEst (TPG.tpgEst). Inputs: a type (implicit; the file's ambient context declares to be a finite type, but this formula makes no use of finiteness and involves no -algebra on ); a real number (no hypothesis: any real); natural numbers and (either may be ); and a trajectory of length , meaning a function assigning to each index a triple with , a Boolean and . Output: the real number
where and (the function score of the same file), with the convention .
Literally, the inner sum ranges over all indices and keeps exactly when and (both inequalities non-strict), contributing otherwise. So the inner sum includes the term itself, has at most terms, and is cut off at the last index : indices do not exist and nothing replaces them. The addition is ordinary addition of natural numbers. This is a deterministic function of the single trajectory ; no probability measure or expectation appears, and the state components are not used.
Edge cases, as the formula literally evaluates:
- : the outer sum is empty and the prefactor is , so the value is .
- : the inner sum is the single term .
- : the inner sum is for every .
- : and , so indices with contribute .
- : and , so indices with contribute .
- : allowed; the formula is used as written.
Env.Q (TPG.Env.Q). Inputs: a finite type carrying a -algebra (the -algebra is an arbitrary parameter: it is not required to be discrete or to contain the singletons); an environment on ; a real number (no hypothesis: any real); a natural number ; an index (so the existence of forces ); and a Boolean . Output: a real number.
What an environment is. An environment on consists of: (a) for every natural number (all of , with no horizon) and every Boolean , a real matrix with rows and columns indexed by , all of whose entries are and each of whose rows sums to one, for every ; (b) a function with for every and (which forces to be nonempty); (c) for every and every Boolean , a Borel probability measure on , about which nothing else (support, moments) is assumed.
The trajectory space and the law used. Let and let be the set of all functions from to , with the product -algebra (the given one on , the discrete one on , the Borel one on ); write . Each pair with , gets the real weight
and is the measure on
Under each summand the coordinates are the fixed values and the are independent with distributed as . A negative weight is replaced by , with no renormalisation; since and the matrices are entrywise nonnegative, this happens only if , and then need not have total mass . For no clipping occurs and is a probability measure.
The definition. Put and let be the conditional measure . Then
Literally the sum ranges over all and the summand is the integral when (non-strict, so is included) and otherwise. The sum is not divided by and has no upper cut-off other than .
Conventions that decide the value in degenerate cases:
- If , the library's conditional measure is the zero measure, every integral against it is , and so . This occurs for instance when and , and when and . (For one has and .)
- Each integral is a Bochner integral, which by convention equals when is not integrable with respect to . No integrability or boundedness of the measures is assumed in this definition.
- For the definition still applies, to the clipped measure described above.
Env.Qk (TPG.Env.Qk). Inputs: a finite type carrying a -algebra (an arbitrary parameter: not required to be discrete or to contain the singletons); an environment on ; a real number (no hypothesis: any real); natural numbers and ( may be ); an index (so ); and a Boolean . Output: a real number.
What an environment is. An environment on consists of: (a) for every natural number (all of , with no horizon) and every Boolean , a real matrix with rows and columns indexed by , all of whose entries are and each of whose rows sums to one, for every ; (b) a function with for every and (which forces to be nonempty); (c) for every and every Boolean , a Borel probability measure on , about which nothing else is assumed.
The trajectory space and the law used. Let and let be the set of all functions from to , with the product -algebra (the given one on , the discrete one on , the Borel one on ); write . Each pair with , gets the real weight
and is the measure on
Under each summand the coordinates are the fixed values and the are independent with distributed as . A negative weight is replaced by , with no renormalisation; this happens only if , and then need not have total mass . For no clipping occurs and is a probability measure.
The definition. Put and let be the conditional measure . Then
Literally the sum ranges over all and the summand is the integral when and (both non-strict) and otherwise. So the window starts at (included), contains at most indices, and is cut off at the last index . The sum is not divided by . The conditioning is on the single coordinate and is the same for every in the window. This is the same expression as Env.Q of the same file except for the extra upper constraint ; for the two coincide, and for the sum is the single term .
Conventions that decide the value in degenerate cases:
- If , the library's conditional measure is the zero measure, every integral against it is , and the value is . This occurs for instance when and , and when and . (For one has and .)
- Each integral is a Bochner integral, which by convention equals when is not integrable with respect to . No integrability or boundedness of the measures is assumed in this definition.
- For the definition still applies, to the clipped measure described above.
Env.truncLaw (TPG.Env.truncLaw). Inputs: a finite type carrying a -algebra (an arbitrary parameter: not required to be discrete or to contain the singletons); an environment on ; three natural numbers , , (in this order; is an arbitrary natural number and is not required to be smaller than ); and a real number (no hypothesis: any real). Output: a measure on the trajectory space .
What an environment is. An environment on consists of: (a) for every natural number (all of , with no horizon) and every Boolean , a real matrix with rows and columns indexed by , all of whose entries are and each of whose rows sums to one, for every ; (b) a function with for every and (which forces to be nonempty); (c) for every and every Boolean , a Borel probability measure on , about which nothing else is assumed.
The trajectory space. Let and let be the set of all functions from to , with the product -algebra (the given one on , the discrete one on , the Borel one on ).
The definition. Define a sequence of real numbers by
Each pair with , gets the real weight
and the output is the measure
Under each summand the state and Boolean coordinates at index are the fixed values and the real coordinates are independent, the one at index distributed as .
Points the formula literally entails:
- The number is a constant written in the definition, not a parameter. It is used at exactly those indices with (strict), i.e. the indices more than steps before . Every other index uses , including and all indices after .
- If , no index satisfies , so for all and the measure is the one with constant sequence .
- Only enter the formula.
- A negative weight is replaced by , with no renormalisation; this can happen only if (the value never produces a negative factor), and then the total mass need not be . For the measure is a probability measure.
- The factor is present only when . For all products are empty, the weight is , is a single point, and the measure is the unit mass on it.
Env.Jk (TPG.Env.Jk). Inputs: a finite type carrying a -algebra (an arbitrary parameter: not required to be discrete or to contain the singletons); an environment on ; natural numbers and (either may be ); and a real number (no hypothesis: any real). Output: a real number.
What an environment is. An environment on consists of: (a) for every natural number (all of , with no horizon) and every Boolean , a real matrix with rows and columns indexed by , all of whose entries are and each of whose rows sums to one, for every ; (b) a function with for every and (which forces to be nonempty); (c) for every and every Boolean , a Borel probability measure on , about which nothing else is assumed.
The trajectory space. Let and let be the set of all functions from to , with the product -algebra (the given one on , the discrete one on , the Borel one on ); write for the real component of .
The definition. For each define the sequence if and if , the weights
for , , and the measure on
(this is Env.truncLaw of the same file, evaluated at ). Then
So the -th summand integrates the -th real coordinate against a measure that itself depends on : in , the indices with use the constant (written in the definition, not a parameter) and all other indices, including , use .
Points the formula literally entails:
- For every the sequence is constantly ; in particular if every is the measure with constant sequence .
- : the sum is empty and the prefactor is , so the value is .
- Each integral is a Bochner integral, equal to by convention when is not -integrable. No integrability or boundedness of the measures is assumed in this definition.
- A negative weight is replaced by with no renormalisation; this happens only if , and then need not have total mass .
Env.stateDist (TPG.Env.stateDist). Inputs: a finite type with decidable equality (a technical requirement, used to form identity matrices; no -algebra on is involved); an environment on ; a real number (no hypothesis: any real); and a natural number . Output: a function .
What an environment is. An environment on consists of: (a) for every natural number (all of , with no horizon) and every Boolean , a real matrix with rows and columns indexed by , all of whose entries are and each of whose rows sums to one, for every ; (b) a function with for every and (which forces to be nonempty); (c) for every and every Boolean , a Borel probability measure on (not used by this definition).
The definition. For each natural number let , a real matrix. The output is the row vector multiplied on the right by the ordered matrix product (factors in increasing order of index, from left to right):
For the product is empty and equals the identity matrix, so the output is itself. Since is unrestricted, for the matrices can have negative entries and the output need not be nonnegative; the formula is used as written. The same is used at every step.
Env.JkGen (TPG.Env.JkGen). Inputs: a finite type with decidable equality (a technical requirement, used to form identity matrices; no -algebra on is involved); an environment on ; natural numbers and (either may be ); and two real numbers and , in this order (no hypothesis on either: any reals). Output: a real number.
What an environment is. An environment on consists of: (a) for every natural number (all of , with no horizon) and every Boolean , a real matrix with rows and columns indexed by , all of whose entries are and each of whose rows sums to one, for every ; (b) a function with for every and (which forces to be nonempty); (c) for every and every Boolean , a Borel probability measure on , about which nothing else is assumed.
Ingredients. For a real number and a natural number let . For a Boolean and let (a Bochner integral, equal to by convention if has no finite first moment), and let . For let ; this is the truncated subtraction of natural numbers, so whenever .
The definition. For each , first form the row vector (this is Env.stateDist of the same file evaluated at and ), then the row vector
all matrix products being taken with indices increasing from left to right, an empty product being the identity matrix. Then
So in the -th summand the first steps (indices ) use the first real parameter , the last steps (indices ) use the second real parameter , and the mixture at the end also uses . This definition is built from matrices and the means only; no measure on a trajectory space appears in it.
Points the formula literally entails:
- For : , the -block is empty, and the -th summand does not depend on . In particular if the whole value does not depend on .
- For : , the -block is empty, all steps use , and only involves .
- : the sum is empty and the prefactor is , so the value is .
- and are unrestricted; for values outside the matrices can have negative entries and the formula is used as written.
Psi (TPG.Psi). Inputs: a natural number and a real number (no hypothesis: any real, in particular not required to lie in ). Output: the real number
The index ranges over the natural numbers , but the condition removes the last one, ; so the value equals
Thus , , . The power equals for every real , including . The definition involves no state space, environment or measure.
Env.rDiffNorm (TPG.Env.rDiffNorm). Inputs: a finite type (no -algebra on and no decidable equality are required) and an environment on . Output: a real number.
What an environment is. An environment on consists of: (a) for every natural number and every Boolean , a real matrix with rows and columns indexed by , all of whose entries are and each of whose rows sums to one (not used by this definition); (b) a function with for every and (not used by the formula, but its existence forces to be nonempty); (c) for every and every Boolean , a Borel probability measure on , about which nothing else is assumed.
The definition. For a Boolean and let . Then
The supremum is the library's real-valued supremum of a family, which by convention is for an empty index set or a family unbounded above; here is finite and nonempty, so it is the maximum over . Each is a Bochner integral, equal to by convention if has no finite first moment; no integrability or boundedness of is assumed in this definition.
rcWeight (TPG.rcWeight). Inputs: a real number and a Boolean . Output: the real number
There is no hypothesis on : any real number is allowed. Division is the library's total division on , in which . Consequently, at both values are ( and ), and at both values are ( and ). At both values are . For both values are negative. The definition involves no state space, environment or measure.
rcEst (TPG.rcEst). Inputs: a type (implicit; the file's ambient context declares to be a finite type, but this formula makes no use of finiteness and involves no -algebra on ); a real number (no hypothesis: any real); natural numbers and (either may be ); and a trajectory of length , meaning a function assigning to each index a triple with , a Boolean and . Output: the real number
where
(the functions score and rcWeight of the same file), with the convention .
Literally, the inner sum ranges over all indices and keeps exactly when (strict) and (non-strict), contributing otherwise. So the term at the index itself enters with coefficient (no factor ), the later indices each enter with the factor evaluated at that later index's own Boolean , and the whole bracket is multiplied by evaluated at . The window is cut off at the last index . This is a deterministic function of the single trajectory ; no probability measure or expectation appears, and the state components are not used.
Edge cases, as the formula literally evaluates:
- : the outer sum is empty and the prefactor is , so the value is .
- , or : the inner sum is empty and the bracket is .
- : , , and is identically , so the value is .
- : , , and is identically , so the value is .
- : is identically .
- : allowed; the formula is used as written.
Confirmed by the mission captain (proposal self-audit).