Proposition 6 — bias and variance bounds for the reward-corrected (RC) estimator
ProvedTPG.proposition_6_rc_boundsSetting. is a finite state space and the action is control or treatment. Time is , which is the source's time . Under action at time the state moves according to a transition matrix , i.e. ; the matrices may depend on arbitrarily. The initial state has distribution , and the reward has distribution on , with for all and conditional independence from everything else given . Under the policy every action is treatment with probability , independently of everything else; , and refer to the law of the trajectory under .
Assumption 1 (mixing time) with constant : for every time , every action and every pair of probability vectors on , , where . The kernel deviation is .
The global average treatment effect is .
Fix . With the score and the additional importance weight , the reward-corrected estimator with truncation size , computed from a trajectory generated under , is
Write , and (so ).
Proposition. Under Assumption 1, for every , and integer :
When , the first term of the bias bound can be omitted.
Compared with Proposition 5, the reward correction removes the first-order term in that appears away from balanced randomization, at the cost of a larger variance bound. At the two estimators coincide.
Formalization Note The remark on is the third conjunct of the formal statement, under the hypothesis .
import Mathlib import Definitions.Def_TPG_Model import Definitions.Def_TPG_Estimators open MeasureTheory ProbabilityTheory open scoped BigOperators ENNReal
namespace TPG
theorem proposition_6_rc_bounds {S : Type} [Fintype S] [MeasurableSpace S] [MeasurableSingletonClass S]
(E : Env S) (T k : ℕ) (θ γ M : ℝ)
(hT : 0 < T) (hk : k ≤ T) (hθ0 : 0 < θ) (hθ1 : θ < 1) (hγ0 : 0 < γ) (hγ1 : γ < 1)
(hmix : E.Mixing T γ) (hM : E.RewardBound M) :
|(∫ ω, rcEst θ T k ω ∂(E.expLaw T θ)) - E.gate T|
≤ 2 * E.delta T * M * γ ^ k / (1 - γ)
+ 4 * (θ ^ 2 + (1 - θ) ^ 2) * (E.delta T) ^ 2 * M * Psi k γ
∧ variance (rcEst θ T k) (E.expLaw T θ)
≤ M ^ 2 / ((T : ℝ) * (θ * (1 - θ)))
* (1 + (k : ℝ) * (1 + (1 - 2 * θ) ^ 2 / (θ * (1 - θ))))
* (2 * (k : ℝ) + 3 + 4 * γ / (1 - γ))
∧ (T ≤ k + 1 →
|(∫ ω, rcEst θ T k ω ∂(E.expLaw T θ)) - E.gate T|
≤ 4 * (θ ^ 2 + (1 - θ) ^ 2) * (E.delta T) ^ 2 * M * Psi k γ) := by sorry
end TPGRead-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting (data and typeclass assumptions). Let be a finite set carrying a -algebra in which every singleton is measurable (as is finite, this forces the -algebra to be the full power set). Let be an environment on , which consists of exactly the following data:
- for every time index and every Boolean (here = true, = false), a real matrix whose entries are all and whose rows each sum to one: for every ;
- a function with for all and ;
- for every and every Boolean , a Borel probability measure on .
Such an can exist only if is non-empty, because sums to .
Let and be natural numbers and let be real numbers. The statement is asserted for all such , , , , , , satisfying the six hypotheses below.
Hypotheses.
- .
- .
- and .
- and .
- (Contraction of every one-step matrix, with constant .) For every natural number , every Boolean , and every pair of functions that are probability vectors (all values , values summing to ),
Here is the row-vector–matrix product , and for any two functions the symbol means . The condition is imposed separately on and on , for only.
- (Bounded support.) For every and every Boolean , .
No sign condition on is stated separately. If the interval is empty and hypothesis 6 cannot hold; if hypothesis 6 says that every is the unit point mass at .
The probability measures used. Times are indexed from . The sample space is
with the product -algebra (power set on and on the Booleans, Borel sets on ). For and write , and for the three components of the -th coordinate of .
For a real number and sequences , , define the weight
(in the code the first factor is a product over all of factors equal to when and to otherwise, and the second is a product over all pairs of factors equal to when and to otherwise). Define the measure on
where is the unit point mass at and is the product measure. (The code defines this for an arbitrary real sequence in place of the constant ; this statement only uses the constant sequences , and . For every weight is already , so the truncation changes nothing, and the weights sum to .) In words, under : has distribution ; each equals with probability and with probability , independently of everything earlier; given the past, is drawn from row of the matrix ; and, given the whole sequence , the are independent with . Under only the sequence has non-zero weight, and under only . The matrices , and all with , do not occur in .
Write for the integral with respect to (the Bochner integral, which by convention is for a non-integrable integrand), and
computed as an integral with values in and then converted to a real number with the convention . (Under hypothesis 6 every lies in almost surely under , , , so neither convention is triggered for the quantities below.)
Quantities appearing in the statement.
- The reference quantity (named
gatein the code):
- The statistic (named
rcEst), a function of :
with
The inner sum runs over (strictly later than , cut off at the last time , empty when or ). The term carries no factor ; each later is multiplied by , evaluated at the Boolean of the same time .
- The kernel discrepancy (named
delta):
Both suprema are over finite non-empty sets, so this is a maximum; it includes . (The supremum used is the real-valued one, which would return over an empty index set.)
- The polynomial-geometric sum (named
Psi):
which equals when or .
Conclusion. Under hypotheses 1–6, all three of the following hold.
(i) Bound on the difference between the -expectation of the statistic and :
(ii) Bound on the variance of the statistic under :
Both bracketed factors multiply the fraction (neither is in the denominator).
(iii) If moreover , then
that is, the right-hand side of (i) without its first term .
Edge cases covered by the quantifiers.
- Together with hypothesis 2, the extra condition in (iii) means or . For every the cut-off equals for all , so and are the same function, while the right-hand sides of (i)–(iii) are evaluated at the respective value of .
- is allowed. Then the bracket in the statistic is the single term , and : (i) reads ; (ii) reads ; and (iii) applies only when .
- Since for , the right-hand side of (iii) is whenever ; the condition of (iii) is then met exactly for , and in those cases (iii) asserts .
- is allowed. Then contains no matrix entry at all, while hypothesis 5 and still refer to ; the condition of (iii) holds for both admissible values .
- In general hypothesis 5 and involve the matrices at , which do not enter any of the measures .
Confirmed by the mission captain (proposal self-audit).