Suboptimal-arm large posterior tails along realized ranks
ProvedBanditAlgorithm.gaussian_ts_suboptimal_exact_rank_large_tail_sum_boundbanditsgaussianprobabilitythompson-sampling
Consider an arbitrary adaptive policy on a unit-variance Gaussian bandit. Fix an optimal arm and a suboptimal arm with gap . After the first realized rewards of arm , let be the posterior Gaussian probability of exceeding the midpoint between the two arm means. There is a universal constant such that, for every ,
This finite estimate is the suboptimal-arm Gaussian posterior-tail input in the pull-count analysis. Exact realized ranks ensure that every empirical mean in the sum is computed from observations that actually occurred.
Formalization Note The expectation is represented by a lintegral with values in the extended nonnegative reals.
Preamble
import Definitions.Def_ThompsonSampling import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory ENNReal
Formal statement
namespace BanditAlgorithm
/-- The suboptimal-arm posterior large-tail estimate from Exercise 36.6(b),
truncated at the realized pull count. -/
theorem gaussian_ts_suboptimal_exact_rank_large_tail_sum_bound :
∃ C : ℝ, 0 < C ∧
∀ (k : ℕ) [NeZero k] (μvec : Fin k → ℝ) (π : BanditPolicy k),
∀ (i₀ : Fin k),
banditArmMean (gaussianBandit μvec) i₀ =
banditOptimalMean (gaussianBandit μvec) →
∀ (i : Fin k), 0 < banditGap (gaussianBandit μvec) i →
∀ n : ℕ, 2 ≤ 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 BanditAlgorithmSource
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), Exercise 36.6(b), printed p. 475 / PDF p. 484; Theorem 36.2 and Eq. (36.3), printed pp. 463–465 / PDF pp. 472–474. This is the finite-horizon exact-rank envelope underlying the displayed asymptotic estimate.