Summability of quadratically weighted deviation failures
ProvedBanditAlgorithm.tsum_sq_mean_failure_ne_top_of_forced_explorationSuppose a sampling rule guarantees, almost surely, that every arm has been played at least times by round . Then for every accuracy
The forced-exploration floor makes every empirical mean rest on samples, so the time-uniform confidence bound gives a per-round failure probability decaying like , and a sub-exponential decay absorbs any polynomial weight.
The quadratic weight is what a delayed covering argument costs downstream: an allocation failure at round is covered by mean failures from round on, and exchanging the two sums turns a linear weight into a quadratic one. So a first moment for the allocation is a second moment for the means.
The count bound is assumed only almost surely, which is the strongest form any sampling rule delivers: a policy constrains only the trajectories in its support, while the canonical trajectory space contains every sequence of arm-reward pairs. The cost is a single intersection with a full-measure set inside the union bound.
import Definitions.Def_TrackAndStop import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory InformationTheory NNReal ENNReal Filter
theorem BanditAlgorithm.tsum_sq_mean_failure_ne_top_of_forced_exploration
{k : ℕ} [NeZero k] (μvec : Fin k → ℝ)
(pol : BanditAlgorithm.BanditPolicy k) {ξ : ℝ} (hξ : 0 < ξ)
(hcount : ∀ᵐ ω ∂(BanditAlgorithm.banditTrajMeasure
(BanditAlgorithm.gaussianBandit μvec) pol),
∀ (t : ℕ) (j : Fin k),
Real.sqrt (t : ℝ) - 2 * (k : ℝ) ≤ (BanditAlgorithm.trajPullCount j t ω : ℝ)) :
∑' m : ℕ, ((m : ℝ≥0∞) + 1) ^ 2 *
BanditAlgorithm.banditTrajMeasure (BanditAlgorithm.gaussianBandit μvec) pol
{ω : ℕ → Fin k × ℝ | ∀ i : Fin k,
|BanditAlgorithm.trajEmpiricalMean i m ω - μvec i| ≤ ξ}ᶜ ≠ ⊤ := by
sorry