Proposition 6, variance part —
ProvedTPG.rc_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 with and , computed under ; write and .
Statement. Under Assumption 1, for every and ,
This is the variance half of Proposition 6.
import Mathlib import Definitions.Def_TPG_Model import Definitions.Def_TPG_Estimators open MeasureTheory ProbabilityTheory open scoped BigOperators ENNReal
namespace TPG
theorem rc_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 (rcEst θ T k) (E.expLaw T θ)
≤ M ^ 2 / ((T : ℝ) * (θ * (1 - θ)))
* (1 + (k : ℝ) * (1 + (1 - 2 * θ) ^ 2 / (θ * (1 - θ))))
* (2 * (k : ℝ) + 3 + 4 * γ / (1 - γ)) := by sorry
end TPG