The pair statistic of Track-and-Stop is the Gaussian pairwise GLR
ProvedBanditAlgorithm.trajPairGLR_eq_pooled_gaussian_glrbanditsbest-arm-identificationgaussian
For a pair of arms with , the pairwise Gaussian generalised likelihood ratio admits the pooled-mean closed form
The right-hand side is the definition of the GLR statistic -- the cheapest way, in KL divergence, to make arms and share a common mean -- and the left-hand side is the closed form that Lattimore--Szepesv'ari manipulate on p.\ 409. The identity is the exact decomposition
so the infimum is attained at the pooled mean . It is the single most-used algebraic fact in this development.
Preamble
import Definitions.Def_TrackAndStop import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory InformationTheory NNReal ENNReal
Formal statement
theorem BanditAlgorithm.trajPairGLR_eq_pooled_gaussian_glr {k : ℕ} (a b : Fin k) (t : ℕ)
(ω : ℕ → Fin k × ℝ)
(h : 0 < (BanditAlgorithm.trajPullCount a t ω : ℝ)
+ (BanditAlgorithm.trajPullCount b t ω : ℝ)) :
BanditAlgorithm.trajPairGLR a b t ω
= ⨅ m : ℝ, ((BanditAlgorithm.trajPullCount a t ω : ℝ)
* ((BanditAlgorithm.trajEmpiricalMean a t ω - m) ^ 2 / 2)
+ (BanditAlgorithm.trajPullCount b t ω : ℝ)
* ((BanditAlgorithm.trajEmpiricalMean b t ω - m) ^ 2 / 2)) := by
sorrySource
Lattimore & Szepesvari, Bandit Algorithms (CUP 2020), Section 33.2.2, p. 409; Garivier & Kaufmann, COLT 2016, Section 3.