Theorem 4.1 — Bandit swap regret lower bound
ProvedCalibeatBandit.theorem_4_1algorithmic-game-theorybandit-algorithms
For some absolute constants and , for each integer and each measurable randomized bandit policy on actions, there is a deterministic oblivious sequence of reward vectors in for which the expected swap regret at horizon is at least . The learner’s next action is a measurable function of its private random seed and the rewards it observed on the previous rounds. This lower bound gives the hard instance used by the continuous pricing reduction.
Preamble
import Definitions.Def_CalibeatBandit_lower_bound_models import Definitions.Def_CalibeatBandit_swapRegret open CalibeatBandit MeasureTheory Set
Formal statement
theorem CalibeatBandit.theorem_4_1 :
∃ c : ℝ, 0 < c ∧ ∃ N₀ : ℕ, ∀ N : ℕ, N₀ ≤ N →
∀ {S : Type*} [MeasurableSpace S] (P : Measure S) [IsProbabilityMeasure P]
(pick : (t : ℕ) → S → FeedbackHistory t → Fin N),
(∀ t, Measurable (fun p : S × FeedbackHistory t => pick t p.1 p.2)) →
∃ y : ℕ → Fin N → ℝ, (∀ t i, y t i ∈ Icc 0 1) ∧
c * (N : ℝ) ^ 3 / (Real.log N) ^ 6 ≤
∫ s, swapRegret (N ^ 4) y (fun t => pick t s (feedbackHistory (fun i => pick i s) y t)) ∂P := by sorrySource
Hartline, Wang, Wu, Calibeating Bandit Advice, STOC 2027 submission 1457, Theorem 4.1 — Bandit swap regret lower bound