Proposition 13, main case: two or more arms
ProvedBanditAlgorithm.exists_policy_optimal_allocation_with_integrable_settling_time_of_two_leProposition 13, for two or more arms. There is a single sampling rule -- one policy, fixed before the environment and before the confidence level -- such that for every unit-variance Gaussian bandit with a strictly best arm there is an optimal allocation of Lattimore--Szepesv'ari Eq. (33.4), with all weights strictly positive, whose settling time
is almost surely finite and satisfies , at every accuracy .
The integrability, not merely the almost-sure finiteness, is the content: almost-sure convergence of the empirical allocation does not bound , since a rule may delay an arm to a round that is finite almost surely but has infinite mean.
For D-Tracking the quantitative input is the forced-exploration floor, which gives deterministically and hence Gaussian deviations at samples. Continuity of at -- available from uniqueness of the optimal allocation, with no modulus needed -- transfers this to the allocation through the tracking bound and a Cesàro average.
Two arms are needed for the statement to have content: the objective is an infimum over an empty index set when .
import Definitions.Def_TrackAndStop import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory InformationTheory NNReal ENNReal Filter
theorem BanditAlgorithm.exists_policy_optimal_allocation_with_integrable_settling_time_of_two_le
{k : ℕ} [NeZero k] (hk2 : 2 ≤ k) :
∃ pol : BanditAlgorithm.BanditPolicy k,
∀ (μvec : Fin k → ℝ) (istar : Fin k),
(∀ j, j ≠ istar → μvec j < μvec istar) →
∃ α : Fin k → NNReal,
(∀ i, 0 < α i) ∧
BanditAlgorithm.IsOptimalAllocation (BanditAlgorithm.gaussianBandit μvec)
(Set.range (BanditAlgorithm.gaussianBandit (k := k))) α ∧
∀ ξ : ℝ, 0 < ξ →
(∀ᵐ ω ∂(BanditAlgorithm.banditTrajMeasure
(BanditAlgorithm.gaussianBandit μvec) pol),
∃ N : ℕ, ∀ n : ℕ, N ≤ n →
(0 < n ∧
(∀ i, |BanditAlgorithm.trajAllocation i n ω - (α i : ℝ)| ≤ ξ) ∧
(∀ i, |BanditAlgorithm.trajEmpiricalMean i n ω - μvec i| ≤ ξ))) ∧
∫⁻ ω, ((sInf {N : ℕ | ∀ n, N ≤ n →
(0 < n ∧
(∀ i, |BanditAlgorithm.trajAllocation i n ω - (α i : ℝ)| ≤ ξ) ∧
(∀ i, |BanditAlgorithm.trajEmpiricalMean i n ω - μvec i| ≤ ξ))} : ℕ) : ℝ≥0∞)
∂(BanditAlgorithm.banditTrajMeasure
(BanditAlgorithm.gaussianBandit μvec) pol) ≠ ⊤ := by
sorry