Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Normalized stochastic convex-bandit model

Definition
LG2021_CanonicalBandit

by sim2000dg · Nov 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

banditconvex-optimizationprobability

These predicates specify the normalized stochastic convex-bandit observation model and its canonical geometric problem.

For a known set KKK and loss LLL, the normalized noise condition requires every legal finite-history observation law at x∈Kx\in Kx∈K to be a probability measure, to have mean L(x)L(x)L(x), and to satisfy

E[exp⁡((Y−L(x))2)]≤2.\mathbb E[\exp((Y-L(x))^2)]\le2.E[exp((Y−L(x))2)]≤2.

The mean and exponential moment are integrable. The observation law may depend measurably on all previous queries and observations.

The canonical problem in dimension ddd and with constant CCC requires, for every n≥2n\ge2n≥2 and every known compact convex body B1⊆K⊆BdnB_1\subseteq K\subseteq B_{dn}B1​⊆K⊆Bdn​, a legal measurable query policy and probability seed chosen before the loss and noise law. For every globally convex, nonnegative, 111-Lipschitz loss with values in [0,1][0,1][0,1] on KKK and every admissible observation kernel, the expected cumulative regret is at most Cnlog⁡2nC\sqrt n\log^2nCn​log2n.

These are definitions, not asserted guarantees. The normalized body condition is the source-shaped intermediate problem produced by John normalization and the horizon-dependent erosion; the existence theorem is proved separately.

Definition code
import Definitions.Def_BilateralProfitMHR_ConvexBandit

/-! The normalized stochastic convex-bandit problem. The known body and horizon
precede the algorithm; the unknown loss and every admissible adaptive observation
kernel follow it. This is a predicate, whose existence theorem is proved separately. -/

namespace BilateralProfitMHR.CorollaryTransport
open MeasureTheory
def UnitNoiseCond {X : Type} (K : Set X) (L : X → ℝ) (ν : ObsKernel X) : Prop :=
  ∀ (τ : ℕ) (xs : Fin τ → X) (ys : Fin τ → ℝ) (x : X),
    (∀ i, xs i ∈ K) → x ∈ K →
      IsProbabilityMeasure (ν τ xs ys x) ∧
      Integrable (fun z : ℝ => z) (ν τ xs ys x) ∧
      (∫ z, z ∂(ν τ xs ys x)) = L x ∧
      Integrable (fun z : ℝ => Real.exp ((z - L x) ^ 2)) (ν τ xs ys x) ∧
      (∫ z, Real.exp ((z - L x) ^ 2) ∂(ν τ xs ys x)) ≤ 2

end BilateralProfitMHR.CorollaryTransport

namespace LG2021
open MeasureTheory BilateralProfitMHR BilateralProfitMHR.CorollaryTransport Set Metric
def CanonicalLipschitzBandit (d : ℕ) (C : ℝ) : Prop :=
  ∀ n : ℕ, 2 ≤ n → ∀ K : Set (EuclideanSpace ℝ (Fin d)),
    IsCompact K → Convex ℝ K → closedBall 0 1 ⊆ K →
    K ⊆ closedBall 0 ((d : ℝ) * n) →
    ∃ (Ω : Type) (_ : MeasurableSpace Ω) (P : Measure Ω), IsProbabilityMeasure P ∧
      ∃ A : QueryAlg (EuclideanSpace ℝ (Fin d)) Ω, A.IsOn K ∧
        ∀ L : EuclideanSpace ℝ (Fin d) → ℝ,
          ConvexOn ℝ univ L → LipschitzWith 1 L → (∀ x, 0 ≤ L x) →
          (∀ 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)

end LG2021
Source
Tor Lattimore and András György, Improved Regret for Zeroth-Order Stochastic Convex Bandits, Proceedings of the 34th Conference on Learning Theory (COLT 2021), Proceedings of Machine Learning Research 134:2938–2964, 2021, observation model on printed p. 4 and non-Lipschitz reduction in Appendix F, printed p. 27. The explicit quantifier and measurable-kernel interfaces are formal adapters.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me