Theorem 1 — explicit regret for bounded convex bandit losses
ProvedLG2021.theorem_1There exists a universal constant such that, for every integer dimension , horizon , and known compact convex set containing a closed Euclidean unit ball with any center, there is a measurable randomized policy with all queries in and
The probability seed and policy are chosen before the unknown loss and observation kernel. The guarantee holds for every convex loss , without a boundary continuity assumption. The formal comparator is the infimum of the loss on ; it equals the source's minimum comparator whenever a minimum is attained.
The measurable observation kernel may depend on every previous legal query and observation. At each legal current query , its observation has conditional mean and satisfies , with the indicated moments integrable.
This is the statistical regret guarantee of Theorem 1 in Lattimore and György, Improved Regret for Zeroth-Order Stochastic Convex Bandits, COLT 2021, PMLR 134. Its proof imports the formalized original dimension-dependent Theorem 2 and follows Appendix F: erode the known body at depth , scale the eroded body by , and pull queries and adaptive observations back by the inverse scaling. The scaled loss is one-Lipschitz. The diameter grows by at most , and the cumulative comparator penalty is at most one. The proof makes this reduction explicit for the infimum comparator and for a unit ball with arbitrary center. These adaptations preserve the displayed dimension, horizon, and logarithmic rate with one universal constant. Computational efficiency, oracle complexity, and bit complexity are not asserted. The formalization adaptations in the imported Theorem 2 are documented on that theorem.
import Mathlib import Definitions.Def_LG2021_CanonicalBandit import Definitions.Def_LG2021_RegretRate open MeasureTheory BilateralProfitMHR BilateralProfitMHR.CorollaryTransport Set Metric LG2021
theorem LG2021.theorem_1 : ∃ C : ℝ, 0 ≤ C ∧
∀ d : ℕ, 0 < d → ∀ n : ℕ, 2 ≤ n →
∀ K : Set (EuclideanSpace ℝ (Fin d)), IsCompact K → Convex ℝ K →
(∃ a, closedBall a 1 ⊆ K) →
∃ (Ω : Type) (_ : MeasurableSpace Ω) (P : Measure Ω), IsProbabilityMeasure P ∧
∃ A : QueryAlg (EuclideanSpace ℝ (Fin d)) Ω, A.IsOn K ∧
∀ L : EuclideanSpace ℝ (Fin d) → ℝ,
ConvexOn ℝ K L → (∀ x ∈ K, L x ∈ Icc 0 1) →
∀ ν : ObsKernel (EuclideanSpace ℝ (Fin d)), ν.IsMeasurable →
UnitNoiseCond K L ν →
expectedCumLoss A P ν
(fun x => ENNReal.ofReal (L x - sInf (L '' K))) n ≤
ENNReal.ofReal (C * sharpRate d (Metric.diam K) n) := by sorry