Theorem 2 — explicit stochastic convex-bandit regret
ProvedLG2021.theorem_2There exists one universal constant such that for every integer dimension , horizon , and known compact convex set containing a closed Euclidean unit ball (with arbitrary center), there exists a measurable randomized bandit policy supported on satisfying
The probability space and policy are chosen before the unknown loss and observation kernel. The guarantee holds for every convex loss that is one-Lipschitz on . The compact body contains a unit ball, so its diameter is at least two. Lipschitz continuity ensures that the displayed infimum is attained; the formal statement uses the infimum for compatibility with the bounded-convex extension.
At every legal query, the adaptive observation kernel is conditionally centered at the loss and satisfies . Apart from this measurable conditional constraint, the noise may depend on the full prior legal query and observation history.
This formalizes the statistical regret guarantee of Theorem 2 of Tor Lattimore and András György, Improved Regret for Zeroth-Order Stochastic Convex Bandits, COLT 2021, PMLR 134. The full dimension and logarithmic dependence is explicit, with a single universal constant. Modifications to allow formalization include the centered Gaussian score , direct density comparisons in the separation argument, concentration for adaptive observation kernels, charges for both observations in each iteration, legal radial query guards, measurable ellipsoid choices from countable rational cut histories, an infimal-convolution Lipschitz extension, and sharp bookkeeping for the sample and simplex-volume stage bounds. The theorem asserts the statistical existence guarantee; computational efficiency, oracle complexity, and bit complexity are not asserted.
import Mathlib import Definitions.Def_LG2021_CanonicalBandit import Definitions.Def_LG2021_RegretRate open MeasureTheory BilateralProfitMHR BilateralProfitMHR.CorollaryTransport Set Metric
theorem LG2021.theorem_2 : ∃ 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 → LipschitzOnWith 1 L K →
(∀ 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