Finite-sum form of the TPG bias bound, valid for every contraction constant
ProvedTPG.tpg_bias_finite_sumSetting. 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 a constant (not assumed smaller than one): for every time , every action and every pair of probability vectors on , , where . The kernel deviation is .
The global average treatment effect is .
Fix and let , , computed under . Write and (so ), and for a reward time let be the start of its truncation window and its length.
Lemma. For every and ,
The three terms are the contribution of the history before the window, the second-order remainder inside the window, and the first-order term caused by unbalanced randomization. For the bound implies Proposition 5; for , which every environment satisfies, it gives the bound of Proposition 2 at , .
Formalization Note is a truncated subtraction of natural numbers.
import Mathlib import Definitions.Def_TPG_Model import Definitions.Def_TPG_Estimators open MeasureTheory ProbabilityTheory open scoped BigOperators ENNReal
namespace TPG
theorem tpg_bias_finite_sum {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 ≤ γ)
(hmix : E.Mixing T γ) (hM : E.RewardBound M) :
|(∫ ω, tpgEst θ T k ω ∂(E.expLaw T θ)) - E.gate T|
≤ (1 / (T : ℝ)) * ∑ t : Fin T,
(2 * E.delta T * M * γ ^ (min (t : ℕ) k) * (∑ j ∈ Finset.range ((t : ℕ) - k), γ ^ j)
+ 4 * (θ ^ 2 + (1 - θ) ^ 2) * (E.delta T) ^ 2 * M * Psi (min (t : ℕ) k) γ
+ 2 * |1 - 2 * θ| * E.delta T * (∑ j ∈ Finset.range (min (t : ℕ) k), γ ^ j)
* E.rDiffNorm) := by sorry
end TPG