Forced exploration plus a settling allocation gives a settling time
ProvedBanditAlgorithm.settling_of_allocation_half_and_forced_explorationLet a sampling rule satisfy, almost surely, the forced-exploration bound for every round and arm. Suppose that at accuracy the empirical allocation settles to almost surely and its failure series is summable,
Then the joint settling time of the allocation and the empirical means,
is almost surely finite and satisfies .
This is Proposition 13 reduced to its allocation half: the empirical-mean half is supplied here, because forced exploration alone makes every mean rest on samples and the time-uniform confidence bound then gives a summable failure series. The settling time of an intersection is at most the sum of the two, so integrability is inherited.
The count bound is assumed only almost surely, which is the strongest form any sampling rule delivers: a policy constrains only the trajectories in its support, while the canonical trajectory space contains every sequence of arm-reward pairs.
import Definitions.Def_TrackAndStop import Definitions.Def_GaussianBandit open MeasureTheory ProbabilityTheory InformationTheory NNReal ENNReal Filter
theorem BanditAlgorithm.settling_of_allocation_half_and_forced_exploration
{k : ℕ} [NeZero k] (μvec : Fin k → ℝ)
(pol : BanditAlgorithm.BanditPolicy k) (α : Fin k → ℝ) {ξ : ℝ} (hξ : 0 < ξ)
(hcount : ∀ᵐ ω ∂(BanditAlgorithm.banditTrajMeasure
(BanditAlgorithm.gaussianBandit μvec) pol),
∀ (t : ℕ) (j : Fin k),
Real.sqrt (t : ℝ) - 2 * (k : ℝ) ≤ (BanditAlgorithm.trajPullCount j t ω : ℝ))
(hAsettle : ∀ᵐ ω ∂(BanditAlgorithm.banditTrajMeasure
(BanditAlgorithm.gaussianBandit μvec) pol),
∃ N : ℕ, ∀ n : ℕ, N ≤ n →
(0 < n ∧ ∀ i, |BanditAlgorithm.trajAllocation i n ω - α i| ≤ ξ))
(hAsum : ∑' m : ℕ, ((m : ℝ≥0∞) + 1) *
BanditAlgorithm.banditTrajMeasure (BanditAlgorithm.gaussianBandit μvec) pol
{ω : ℕ → Fin k × ℝ |
0 < m ∧ ∀ i, |BanditAlgorithm.trajAllocation i m ω - α i| ≤ ξ}ᶜ ≠ ⊤) :
(∀ᵐ ω ∂(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