Martingale-difference decomposition of the centered TPG sum with bounded, local increments
ProvedTPG.exists_mds_decompositionSetting. 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 .
Fix a truncation size and consider the experimental policy . Let and , so that . Assumption 1 holds for all times with one constant .
Lemma. There is a constant , depending only on the environment, , and , such that for every horizon there are functions of the trajectory with:
- locality: is measurable with respect to ;
- boundedness: everywhere;
- martingale differences: and almost surely for every ;
- decomposition: almost surely,
The are versions of the increments of the Doob martingale of . Their uniform bound comes from the geometric forgetting of Assumption 1, and their locality from the Markov property. A martingale central limit theorem applied to then gives the asymptotic normality of the estimator.
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 exists_mds_decomposition {S : Type} [Fintype S] [MeasurableSpace S] [MeasurableSingletonClass S]
(E : Env S) (k : ℕ) (γ M : ℝ) (hγ0 : 0 < γ) (hγ1 : γ < 1)
(hmix : ∀ T : ℕ, E.Mixing T γ) (hM : E.RewardBound M) :
∃ C : ℝ, 0 ≤ C ∧ ∀ T : ℕ, ∃ D : ℕ → Traj S T → ℝ,
(∀ j : ℕ, Measurable[sigmaWindow T (j - (k + 1)) j] (D j))
∧ (∀ (j : ℕ) (ω : Traj S T), |D j ω| ≤ C)
∧ (∫ ω, D 0 ω ∂(E.expLaw T (1 / 2)) = 0)
∧ (∀ j : ℕ, (E.expLaw T (1 / 2))[D (j + 1) | sigmaWindow T 0 j]
=ᵐ[E.expLaw T (1 / 2)] 0)
∧ (∀ᵐ ω ∂(E.expLaw T (1 / 2)),
∑ j ∈ Finset.range T, D j ω
= (∑ t : Fin T, Bt k t ω) - ∫ ω', ∑ t : Fin T, Bt k t ω' ∂(E.expLaw T (1 / 2))) := by sorry
end TPG