Closed form for the characteristic time of a Gaussian bandit
ProvedBanditAlgorithm.gaussian_bai_characteristic_time_formulabanditsbest-arm-identificationgaussianinformation-theory
The characteristic time of a unit-variance Gaussian bandit with a unique best arm has a closed form: for any allocation with full support,
This is the computation behind Equation (33.4) for the Gaussian class, and it is what makes effective rather than merely defined. An alternative environment must promote some arm above ; the cheapest way to do so moves only the two coordinates and , to their pooled mean, at cost . Note the same pooled-mean expression as in the empirical GLR statistic -- with the true means and the allocation in place of the empirical means and the pull counts. That correspondence is the whole idea of Track-and-Stop.
Preamble
import Definitions.Def_TrackAndStop import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory InformationTheory NNReal ENNReal
Formal statement
theorem BanditAlgorithm.gaussian_bai_characteristic_time_formula {k : ℕ} [NeZero k]
{μvec : Fin k → ℝ} {istar : Fin k}
(hstar : ∀ j, j ≠ istar → μvec j < μvec istar) {α : Fin k → NNReal}
(hα : ∀ i, 0 < α i) :
(⨅ ν' ∈ BanditAlgorithm.baiAlternatives
(Set.range (BanditAlgorithm.gaussianBandit (k := k)))
(BanditAlgorithm.gaussianBandit μvec),
∑ i, (α i : ENNReal) * InformationTheory.klDiv
((BanditAlgorithm.gaussianBandit μvec).P i) (ν'.P i))
= ⨅ j ∈ {j : Fin k | j ≠ istar},
ENNReal.ofReal ((α istar : ℝ) * (α j : ℝ) / ((α istar : ℝ) + (α j : ℝ))
* (μvec istar - μvec j) ^ 2 / 2) := by
sorrySource
Garivier & Kaufmann, Optimal Best Arm Identification with Fixed Confidence, COLT 2016, Section 3 and Eq. (3); Lattimore & Szepesvari, Bandit Algorithms (CUP 2020), Eq. (33.4) specialised to the class E^k_N(1).