Proposition 5, variance part —
ProvedTPG.tpg_variance_boundSetting. 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 .
Fix and let , , computed from a trajectory generated under ; write .
Statement. Under Assumption 1, for every and ,
This is the variance half of Proposition 5; at it is the explicit form of the variance bound of Theorem 1.
import Mathlib import Definitions.Def_TPG_Model import Definitions.Def_TPG_Estimators open MeasureTheory ProbabilityTheory open scoped BigOperators ENNReal
namespace TPG
theorem tpg_variance_bound {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) :
variance (tpgEst θ T k) (E.expLaw T θ)
≤ M ^ 2 * ((k : ℝ) + 1) / ((T : ℝ) * (θ * (1 - θ)))
* (2 * (k : ℝ) + 3 + 4 * γ / (1 - γ)) := by sorry
end TPG