From gap-dependent pull bounds to minimax regret
ProvedBanditAlgorithm.finite_gap_pull_bound_to_minimaxbanditsinequalitiesminimaxregret
Let and . For each arm , let its gap satisfy , and let be an expected pull count with . Suppose that every positive-gap arm satisfies the logarithmic instance-dependent estimate
Then the corresponding regret obeys the distribution-free bound
This is the standard small-gap/large-gap conversion: split at , control small gaps using the total pull count, and control large gaps using the instance-dependent estimate.
Preamble
import Mathlib.Analysis.SpecialFunctions.Log.Basic import Mathlib.Analysis.SpecialFunctions.Pow.Real import Mathlib.Analysis.Complex.ExponentialBounds import Mathlib.Algebra.Order.BigOperators.Group.Finset open scoped BigOperators
Formal statement
theorem BanditAlgorithm.finite_gap_pull_bound_to_minimax {k n : ℕ} [NeZero k]
(hn : 2 ≤ n) (Δ T : Fin k → ℝ) (C : ℝ)
(hΔ : ∀ i, Δ i ∈ Set.Icc (0 : ℝ) 1)
(hT : ∀ i, 0 ≤ T i) (hsum : ∑ i, T i = n)
(hC : 0 ≤ C)
(hpull : ∀ i, 0 < Δ i →
T i ≤ C * (1 + Real.log n / Δ i ^ 2)) :
∑ i, Δ i * T i ≤
(1 + 3 * C) * Real.sqrt (k * n * Real.log n) := by
sorrySource
Lattimore and Szepesvari, Bandit Algorithms (CUP 2020), Theorem 36.3, printed p.465, distribution-free conclusion; standard small-gap/large-gap conversion used throughout Chapters 7-9.