Sample complexity from an integrable witness time
ProvedBanditAlgorithm.sample_complexity_from_witness_boundsbanditssequential-analysis
Suppose that for every there is a random time with , not depending on , such that for every ,
Then at every confidence level, and for every ,
This is the bookkeeping that turns the finite- bounds of Garivier & Kaufmann's Theorem 14 into the limit statement of Lattimore--Szepesv'ari's Theorem 33.6, and it explains where the of Theorem 14 has to sit. Once is fixed, is a constant and is divided away by ; the multiplicative constant is not. So the bound must be sharp in its multiplicative constant and may be arbitrarily lossy in the additive one --- which is precisely the trade the crossing estimate makes.
Stated for an abstract family of -valued times, so it applies to any stopping rule with a bound of this shape.
Preamble
import Definitions.Def_TrackAndStop import Definitions.Def_GaussianBandit import Mathlib.MeasureTheory.Measure.Prod open MeasureTheory ProbabilityTheory Real NNReal ENNReal Filter Topology
Formal statement
theorem BanditAlgorithm.sample_complexity_from_witness_bounds {k : ℕ} [NeZero k]
{P : MeasureTheory.Measure (ℕ → Fin k × ℝ)} [MeasureTheory.IsProbabilityMeasure P]
{τ : ℝ → (ℕ → Fin k × ℝ) → ℕ∞} {c : ℝ} (hc : 0 ≤ c)
(H : ∀ ε : ℝ, 0 < ε → ∃ W : (ℕ → Fin k × ℝ) → ℕ,
(∫⁻ ω, (W ω : ℝ≥0∞) ∂P ≠ ⊤) ∧
∀ δ ∈ Set.Ioo (0 : ℝ) 1, ∀ᵐ ω ∂P,
τ δ ω ≤ ((W ω : ℕ∞) + ((⌈(1 + ε) * c * Real.log (1 / δ)⌉₊ : ℕ) : ℕ∞))) :
(∀ δ ∈ Set.Ioo (0 : ℝ) 1, ∫⁻ ω, (τ δ ω : ℝ≥0∞) ∂P ≠ ⊤) ∧
∀ ε : ℝ, 0 < ε → ∀ᶠ δ in nhdsWithin (0 : ℝ) (Set.Ioi 0),
(∫⁻ ω, (τ δ ω : ℝ≥0∞) ∂P).toReal / Real.log (1 / δ) ≤ c + ε := by
sorrySource
The passage from Garivier & Kaufmann, COLT 2016, Theorem 14 to the limit form of Lattimore & Szepesvari, Bandit Algorithms (CUP 2020), Theorem 33.6, p. 410.