An optimal allocation exists and has full support
ProvedBanditAlgorithm.exists_isOptimalAllocation_gaussianbanditsbest-arm-identificationgaussianoptimization
Every unit-variance Gaussian bandit with a unique best arm admits an optimal allocation with full support: there exists with for all attaining the supremum in
This is the object Track-and-Stop tracks -- line 8 of Algorithm 21 plugs the empirical means into and drives the empirical allocation towards the result -- so both the existence and the strict positivity matter: full support is what lets the plug-in estimate be consistent. Existence is compactness of the simplex against upper semicontinuity of the objective; full support holds because the objective vanishes whenever some coordinate does, so no boundary point can be optimal.
Preamble
import Definitions.Def_TrackAndStop import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory InformationTheory NNReal ENNReal Filter
Formal statement
theorem BanditAlgorithm.exists_isOptimalAllocation_gaussian {k : ℕ} [NeZero k]
{μvec : Fin k → ℝ} {istar : Fin k}
(hstar : ∀ j, j ≠ istar → μvec j < μvec istar) :
∃ α : Fin k → NNReal, (∀ i, 0 < α i) ∧
BanditAlgorithm.IsOptimalAllocation (BanditAlgorithm.gaussianBandit μvec)
(Set.range (BanditAlgorithm.gaussianBandit (k := k))) α := by
sorrySource
Garivier & Kaufmann, Optimal Best Arm Identification with Fixed Confidence, COLT 2016, Section 3 (existence and uniqueness of the optimal weights); Lattimore & Szepesvari, Bandit Algorithms (CUP 2020), Eq. (33.4) and Algorithm 21.