Means, gaps and optimal arms of a Gaussian bandit
ProvedBanditAlgorithm.gaussianBandit_mean_gap_dictionarybanditsgaussian
The dictionary between the Gaussian bandit and its parameter vector : the arm means of are , the suboptimality gaps are
and arm is suboptimal () exactly when some other arm has a strictly larger parameter.
Every statement about the Gaussian class is phrased through , while the general framework of Chapter 33 is phrased through the abstract means and gaps of a StochasticBandit. This lemma is the translation between the two, and is used at essentially every step of the Track-and-Stop analysis.
Preamble
import Definitions.Def_TrackAndStop import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory InformationTheory NNReal ENNReal
Formal statement
theorem BanditAlgorithm.gaussianBandit_mean_gap_dictionary {k : ℕ} [NeZero k]
(μvec : Fin k → ℝ) (i : Fin k) :
BanditAlgorithm.banditArmMean (BanditAlgorithm.gaussianBandit μvec) i = μvec i ∧
BanditAlgorithm.banditGap (BanditAlgorithm.gaussianBandit μvec) i
= (⨆ j, μvec j) - μvec i ∧
(0 < BanditAlgorithm.banditGap (BanditAlgorithm.gaussianBandit μvec) i
↔ ∃ j, μvec i < μvec j) ∧
(i ∈ BanditAlgorithm.banditOptimalArms (BanditAlgorithm.gaussianBandit μvec)
↔ ∀ j, μvec j ≤ μvec i) := by
sorrySource
Lattimore & Szepesvari, Bandit Algorithms (CUP 2020), Sections 4.4, 4.5 and 33.1.