Signed finite-horizon information-ratio bound
ProvedBanditAlgorithm.information_ratio_cumulative_bound_signedbanditsinequalitiesinformation-theoryprobability
Let be a finite horizon. For every round , let be a (possibly signed) instantaneous regret and let be an information term. Suppose , the pointwise information-ratio inequalities
hold for all , and the total information satisfies . Then
This signed form is the precise finite-sum Cauchy--Schwarz step needed for Bayesian adversarial bandits, where a round's conditional expected regret need not be separately nonnegative.
Preamble
import Mathlib.Analysis.InnerProductSpace.Basic import Mathlib.Analysis.SpecialFunctions.Pow.Real open scoped BigOperators
Formal statement
theorem BanditAlgorithm.information_ratio_cumulative_bound_signed {n : ℕ}
(δ info : Fin n → ℝ) (Γ H : ℝ)
(hΓ : 0 ≤ Γ) (hH : 0 ≤ H)
(hpoint : ∀ t, δ t ^ 2 ≤ Γ * info t)
(hsum : ∑ t, info t ≤ H) :
∑ t, δ t ≤ Real.sqrt (n * Γ * H) := by
sorrySource
Lattimore and Szepesvari, Bandit Algorithms (CUP 2020), Theorem 36.6, printed pp. 470-471, especially the Cauchy-Schwarz calculation in Eq. (36.10).
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.