Variance of a sum of bounded functionals of short time windows is under Assumption 1
ProvedTPG.variance_sum_window_leSetting. is a finite state space, actions are , time is (the source's time ). The environment has transition matrices , initial distribution and reward laws on with . is the law of the trajectory under the Bernoulli policy , and .
Assumption 1 holds on the horizon with a constant : for all , all and all probability vectors .
Lemma. Let , let be an integer and a real number, and for let be a real function of the trajectory that is measurable with respect to and satisfies . Then
Functionals of time windows separated by steps have covariance at most by the strong mixing of the process and the covariance inequality, and summing over pairs gives a bound linear in the horizon. The lemma is the law-of-large-numbers input of the central limit theorem and of the variance-estimator consistency.
Formalization Note is a truncated subtraction of natural numbers.
import Mathlib import Definitions.Def_TPG_Model import Definitions.Def_TPG_Estimators import Definitions.Def_TPG_Inference open MeasureTheory ProbabilityTheory open scoped BigOperators ENNReal
namespace TPG
theorem variance_sum_window_le {S : Type} [Fintype S] [MeasurableSpace S] [MeasurableSingletonClass S]
(E : Env S) (T w : ℕ) (θ γ M K : ℝ)
(hθ0 : 0 < θ) (hθ1 : θ < 1) (hγ0 : 0 < γ) (hγ1 : γ < 1)
(hmix : E.Mixing T γ) (hM : E.RewardBound M)
(U : ℕ → Traj S T → ℝ)
(hU : ∀ j : ℕ, Measurable[sigmaWindow T (j - w) j] (U j))
(hK : ∀ (j : ℕ) (ω : Traj S T), |U j ω| ≤ K) :
variance (fun ω : Traj S T => ∑ j ∈ Finset.range T, U j ω) (E.expLaw T θ)
≤ (T : ℝ) * K ^ 2 * (2 * (w : ℝ) + 3 + 8 / (1 - γ)) := by sorry
end TPG