Finite Gaussian posterior-tail bound along realized arm ranks
ProvedBanditAlgorithm.gaussian_ts_exact_rank_tail_sums_boundConsider Gaussian Thompson sampling with unit-variance rewards, an optimal arm , and a suboptimal arm of gap . For each interaction history , let be the number of times arm has actually been pulled by horizon , and let be the posterior probability, after the first realized rewards of arm , that its sampled mean is at least . Then there is a universal constant such that, for every ,
The sums stop at the exact realized pull counts. Consequently every empirical mean appearing in them is formed from an actually observed initial reward segment; no value assigned to a nonexistent future pull enters the estimate. This is the Gaussian tail input needed by the exact-rank Thompson-sampling pull-count decomposition.
Formalization Note The expectations are encoded as lintegrals in , and the positive part of the reciprocal-tail term is represented by ENNReal.ofReal.
import Definitions.Def_ThompsonSampling import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory ENNReal
namespace BanditAlgorithm
/-- Gaussian posterior-tail estimate for the exact realized-rank sums in the
Thompson-sampling pull-count decomposition. -/
theorem gaussian_ts_exact_rank_tail_sums_bound :
∃ C : ℝ, 0 < C ∧
∀ (k : ℕ) [NeZero k] (μvec : Fin k → ℝ) (π : BanditPolicy k),
IsGaussianTSPolicy π →
∀ (i₀ : Fin k),
banditArmMean (gaussianBandit μvec) i₀ =
banditOptimalMean (gaussianBandit μvec) →
∀ (i : Fin k), 0 < banditGap (gaussianBandit μvec) i →
∀ n : ℕ, 2 ≤ n →
1 + (∫⁻ h, ∑ s ∈ Finset.range (armPullCount i₀ h),
ENNReal.ofReal
(1 / gaussianTSTailProb i₀ s
(banditArmMean (gaussianBandit μvec) i₀ -
banditGap (gaussianBandit μvec) i / 2) h - 1)
∂banditMeasure (gaussianBandit μvec) π n)
+ ∫⁻ h, ∑ s ∈ Finset.range (armPullCount i h),
(if 1 / (n : ℝ) <
gaussianTSTailProb i s
(banditArmMean (gaussianBandit μvec) i₀ -
banditGap (gaussianBandit μvec) i / 2) h
then (1 : ℝ≥0∞) else 0)
∂banditMeasure (gaussianBandit μvec) π n ≤
ENNReal.ofReal
(C * (1 + Real.log n /
banditGap (gaussianBandit μvec) i ^ 2)) := by
sorry
end BanditAlgorithm