The characteristic time of a Gaussian bandit is finite, with an explicit gap bound
ProvedBanditAlgorithm.gaussian_baiComplexity_le_and_ne_topbanditsbest-arm-identificationgaussian
For a unit-variance Gaussian bandit with a unique best arm, the characteristic time is finite, , and it is bounded explicitly in terms of the smallest gap: if satisfies for every , then
Finiteness is load-bearing rather than cosmetic. Theorem 33.6 asserts through the real number , but is defined in , and the coercion sends to ; without finiteness the statement would silently degrade to a false claim. The bound comes from evaluating the defining supremum at the uniform allocation .
Preamble
import Definitions.Def_TrackAndStop import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory InformationTheory NNReal ENNReal Filter
Formal statement
theorem BanditAlgorithm.gaussian_baiComplexity_le_and_ne_top {k : ℕ} [NeZero k]
{μvec : Fin k → ℝ} {istar : Fin k}
(hstar : ∀ j, j ≠ istar → μvec j < μvec istar) :
BanditAlgorithm.baiComplexity (BanditAlgorithm.gaussianBandit μvec)
(Set.range (BanditAlgorithm.gaussianBandit (k := k))) ≠ ⊤ ∧
∀ Δ : ℝ, 0 < Δ → (∀ j, j ≠ istar → Δ ≤ μvec istar - μvec j) →
BanditAlgorithm.baiComplexity (BanditAlgorithm.gaussianBandit μvec)
(Set.range (BanditAlgorithm.gaussianBandit (k := k)))
≤ ENNReal.ofReal (4 * (k : ℝ) / Δ ^ 2) := by
sorrySource
Lattimore & Szepesvari, Bandit Algorithms (CUP 2020), Eq. (33.4) and Section 33.2; Garivier & Kaufmann, COLT 2016, Section 3.