John normalization of explicit stochastic convex-bandit regret
ProvedLG2021.john_normalized_banditFor each ambient dimension , there is a constant such that every nonempty compact convex set admits, for each horizon , a measurable randomized bandit policy supported on with expected regret at most for every continuous convex loss and every admissible adaptive observation kernel. The probability space and policy precede the unknown loss and observation kernel. The noise is conditionally centered and satisfies the exponential-square moment bound at every legal query.
This is the John-normalized consequence of the explicit universal dimension and diameter bound in Theorem 1 of Lattimore and György (COLT 2021). The proof uses the affine hull of , applies the proved Löwner–Fritz John theorem in that dimension, specializes the explicit rate using the diameter bound of the normalized body, and transports the resulting policy and adaptive kernels through the affine coordinate map. Singleton bodies have zero regret. The theorem does not assert a computational complexity bound.
import Mathlib import Definitions.Def_LG2021_CanonicalBandit open MeasureTheory BilateralProfitMHR BilateralProfitMHR.CorollaryTransport Set
theorem LG2021.john_normalized_bandit :
∀ d : ℕ, ∃ C : ℝ, 0 ≤ C ∧ ∀ n : ℕ, 2 ≤ n →
∀ K : Set (EuclideanSpace ℝ (Fin d)), K.Nonempty → IsCompact K → Convex ℝ K →
∃ (Ω : Type) (_ : MeasurableSpace Ω) (P : Measure Ω), IsProbabilityMeasure P ∧
∃ A : QueryAlg (EuclideanSpace ℝ (Fin d)) Ω, A.IsOn K ∧
∀ L : EuclideanSpace ℝ (Fin d) → ℝ,
ContinuousOn L K → 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 * Real.sqrt n * Real.log n ^ 2) := by sorry