Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.7 — OSMD with a 0-potential: Rˉn≤q2mdn/(q−1)\bar R_n\le q\sqrt{2mdn/(q-1)}Rˉn​≤q2mdn/(q−1)​ for semi-bandits

Proved
RegretBandits.Linear.osmd_zero_potential

by mikedeng1 · Oct 4, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatorial-banditsmirror-descentp2o-batch-pfp1bp2o-gran-per-chapterp2o-plan-bookp2o-v1regretsemi-bandits

Consider online combinatorial optimization with semi-bandit feedback. The arm set is a nonempty C⊆{0,1}d\mathcal C\subseteq\{0,1\}^dC⊆{0,1}d with ∥v∥1=m\|v\|_1=m∥v∥1​=m for all v∈Cv\in\mathcal Cv∈C, the convex hull K=Conv(C)\mathcal K=\mathrm{Conv}(\mathcal C)K=Conv(C) meets (0,+∞)d(0,+\infty)^d(0,+∞)d, and the losses ℓt∈[0,1]d\ell_t\in[0,1]^dℓt​∈[0,1]d are fixed in advance. OSMD on K\mathcal KK plays random arms vt∈Cv_t\in\mathcal Cvt​∈C with E[vt∣xt]=xt\mathbb E[v_t\mid x_t]=x_tE[vt​∣xt​]=xt​.

  1. Let ψ\psiψ be a 000-potential and run OSMD with FψF_\psiFψ​ and non-negative, unbiased loss estimates ℓ~t\tilde\ell_tℓ~t​ (E[ℓ~t∣xt]=ℓt\mathbb E[\tilde\ell_t\mid x_t]=\ell_tE[ℓ~t​∣xt​]=ℓt​). Then for every η>0\eta>0η>0 and every x∈Kx\in\mathcal Kx∈K
E∑t=1nℓt⊤vt−∑t=1nℓt⊤x ≤ sup⁡x∈KFψ(x)−Fψ(x1)η+η2∑t=1n∑i=1dE[ℓ~t(i)2(ψ−1)′(xt(i))].\mathbb E\sum_{t=1}^n\ell_t^\top v_t-\sum_{t=1}^n\ell_t^\top x\ \le\ \frac{\sup_{x\in\mathcal K}F_\psi(x)-F_\psi(x_1)}{\eta}+\frac\eta2\sum_{t=1}^n\sum_{i=1}^d\mathbb E\left[\frac{\tilde\ell_t(i)^2}{(\psi^{-1})'(x_t(i))}\right].Et=1∑n​ℓt⊤​vt​−t=1∑n​ℓt⊤​x ≤ ηsupx∈K​Fψ​(x)−Fψ​(x1​)​+2η​t=1∑n​i=1∑d​E[(ψ−1)′(xt​(i))ℓ~t​(i)2​].
  1. Let q>1q>1q>1, ψ(x)=(−x)−q\psi(x)=(-x)^{-q}ψ(x)=(−x)−q, the estimate (5.5), and
η=2q−1⋅m1−2/qn d1−2/q.\eta=\sqrt{\frac{2}{q-1}\cdot\frac{m^{1-2/q}}{n\,d^{1-2/q}}}.η=q−12​⋅nd1−2/qm1−2/q​​.

Then

E∑t=1nℓt⊤vt−∑t=1nℓt⊤x ≤ q2q−1 mdn.\mathbb E\sum_{t=1}^n\ell_t^\top v_t-\sum_{t=1}^n\ell_t^\top x\ \le\ q\sqrt{\frac{2}{q-1}\,mdn}.Et=1∑n​ℓt⊤​vt​−t=1∑n​ℓt⊤​x ≤ qq−12​mdn​.
  1. With q=2q=2q=2, i.e. η=2/n\eta=\sqrt{2/n}η=2/n​, this is 22mdn2\sqrt{2mdn}22mdn​.

The maximum of the left-hand side over x∈Kx\in\mathcal Kx∈K is the pseudo-regret Rˉn\bar R_nRˉn​. The bound improves Theorem 5.6 by the factor ln⁡(d/m)\sqrt{\ln(d/m)}ln(d/m)​. For m=1m=1m=1 it is the log-free O(dn)O(\sqrt{dn})O(dn​) bound for the adversarial multi-armed bandit.

Formalization Note Corrected misprint: the book prints η=2q−1m1−2/qd1−2/q\eta=\sqrt{\frac2{q-1}\frac{m^{1-2/q}}{d^{1-2/q}}}η=q−12​d1−2/qm1−2/q​​, without the factor 1/n1/n1/n. The proof bounds sup⁡Fψ−Fψ(x1)\sup F_\psi-F_\psi(x_1)supFψ​−Fψ​(x1​) by qq−1m(q−1)/qd1/q\frac q{q-1}m^{(q-1)/q}d^{1/q}q−1q​m(q−1)/qd1/q and the second term by q m1/qd1−1/qq\,m^{1/q}d^{1-1/q}qm1/qd1−1/q per round (p. 81). The stated bound q2mdn/(q−1)q\sqrt{2mdn/(q-1)}q2mdn/(q−1)​ is attained by the η\etaη above, which includes nnn. q>1q>1q>1 is needed for ψ\psiψ to be a 000-potential. Non-negativity of the estimates is in the book's statement. Unbiasedness is the standing assumption of Section 5.4 behind (5.6). K∩(0,+∞)d≠∅\mathcal K\cap(0,+\infty)^d\ne\emptysetK∩(0,+∞)d=∅ is the OMD requirement K∩D≠∅K\cap D\ne\emptysetK∩D=∅. x1x_1x1​ is the same on every sample path. Iterates and arms are measurable; in part 1 the estimates and the right-hand side expectations are assumed integrable. E[⋅∣xt]\mathbb E[\cdot\mid x_t]E[⋅∣xt​] is conditioning on σ(xt)\sigma(x_t)σ(xt​).

Preamble
import Mathlib
import Definitions.Def_RegretBandits_Linear_ConvexBasics
import Definitions.Def_RegretBandits_Linear_OMD
import Definitions.Def_RegretBandits_Linear_Potential
import Definitions.Def_RegretBandits_Linear_SemiBandit

open MeasureTheory
Formal statement
namespace RegretBandits.Linear

/-- Theorem 5.7 (OSMD with a 0-potential; Bubeck, Cesa-Bianchi, arXiv:1204.5721v2, p. 80).
Semi-bandit setting of p. 77: arms `C ⊆ {0,1}^d` with `‖v‖₁ = m`, `K = Conv(C)`, oblivious losses
`ℓ_t ∈ [0,1]^d`, played arms `v_t ∈ C` with `E[v_t | x_t] = x_t`.
1. For every `0`-potential `ψ`, OSMD on `K` with `F_ψ` and non-negative estimates `ℓ̃_t` with
   `E[ℓ̃_t | x_t] = ℓ_t` satisfies, for every `x ∈ K`,
   `E ∑ ℓ_tᵀv_t - ∑ ℓ_tᵀx ≤ (sup_K F_ψ - F_ψ(x_1))/η + (η/2) ∑_t ∑_i E[ℓ̃_t(i)² / (ψ⁻¹)'(x_t(i))]`.
2. For `q > 1`, `ψ(x) = (-x)^{-q}`, the estimate (5.5) and
   `η = √((2/(q-1)) m^{1-2/q} / (n d^{1-2/q}))` (corrected: the book prints no `n`),
   `E ∑ ℓ_tᵀv_t - ∑ ℓ_tᵀx ≤ q √((2/(q-1)) m d n)`.
3. With `q = 2` (`η = √(2/n)`): `E ∑ ℓ_tᵀv_t - ∑ ℓ_tᵀx ≤ 2 √(2mdn)`. -/
theorem osmd_zero_potential {d m : ℕ} {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
    [IsProbabilityMeasure P] {C : Set (Fin d → ℝ)} (hC : IsCombinatorialSet C m)
    (hKD : (convexHull ℝ C ∩ posOrthant d).Nonempty)
    (ℓ : ℕ → Fin d → ℝ) (hℓ : ∀ t i, ℓ t i ∈ Set.Icc (0 : ℝ) 1) (n : ℕ) :
    (∀ (ψ : ℝ → ℝ) (a : EReal), IsPotential 0 a ψ →
      ∀ (η : ℝ), 0 < η → ∀ (x v ℓt w : ℕ → Ω → Fin d → ℝ) (x₁ : Fin d → ℝ),
      (∀ ω, IsOMDRun (potentialFn ψ a 0) (posOrthant d) (convexHull ℝ C) η
        (fun t => ℓt t ω) (fun t => x t ω) (fun t => w t ω)) →
      (∀ ω, x 1 ω = x₁) →
      (∀ t, 1 ≤ t → Measurable (x t)) → (∀ t, 1 ≤ t → Measurable (v t)) →
      (∀ t, 1 ≤ t → ∀ ω, v t ω ∈ C) →
      (∀ t, 1 ≤ t → condExpGiven P (x t) (v t) =ᵐ[P] x t) →
      (∀ t, 1 ≤ t → ∀ ω i, 0 ≤ ℓt t ω i) →
      (∀ t, 1 ≤ t → ∀ i, Integrable (fun ω => ℓt t ω i) P) →
      (∀ t, 1 ≤ t → condExpGiven P (x t) (ℓt t) =ᵐ[P] fun _ => ℓ t) →
      (∀ t, 1 ≤ t → ∀ i,
        Integrable (fun ω => ℓt t ω i ^ 2 / deriv (potInv ψ a) (x t ω i)) P) →
      ∀ y ∈ convexHull ℝ C,
        ∫ ω, ∑ t ∈ Finset.Icc 1 n, ℓ t ⬝ᵥ v t ω ∂P - ∑ t ∈ Finset.Icc 1 n, ℓ t ⬝ᵥ y ≤
          (sSup (potentialFn ψ a 0 '' convexHull ℝ C) - potentialFn ψ a 0 x₁) / η +
            η / 2 * ∑ t ∈ Finset.Icc 1 n, ∑ i,
              ∫ ω, ℓt t ω i ^ 2 / deriv (potInv ψ a) (x t ω i) ∂P) ∧
    (∀ (q : ℝ), 1 < q → ∀ (x v w : ℕ → Ω → Fin d → ℝ),
      (∀ ω, IsOMDRun (potentialFn (powPotential q) 0 0) (posOrthant d) (convexHull ℝ C)
        (Real.sqrt (2 / (q - 1) * (m : ℝ) ^ (1 - 2 / q) / (n * (d : ℝ) ^ (1 - 2 / q))))
        (fun t => semiBanditEstimate (ℓ t) (v t ω) (x t ω)) (fun t => x t ω)
        (fun t => w t ω)) →
      (∀ t, 1 ≤ t → Measurable (x t)) → (∀ t, 1 ≤ t → Measurable (v t)) →
      (∀ t, 1 ≤ t → ∀ ω, v t ω ∈ C) →
      (∀ t, 1 ≤ t → condExpGiven P (x t) (v t) =ᵐ[P] x t) →
      ∀ y ∈ convexHull ℝ C,
        ∫ ω, ∑ t ∈ Finset.Icc 1 n, ℓ t ⬝ᵥ v t ω ∂P - ∑ t ∈ Finset.Icc 1 n, ℓ t ⬝ᵥ y ≤
          q * Real.sqrt (2 / (q - 1) * m * d * n)) ∧
    (∀ (x v w : ℕ → Ω → Fin d → ℝ),
      (∀ ω, IsOMDRun (potentialFn (powPotential 2) 0 0) (posOrthant d) (convexHull ℝ C)
        (Real.sqrt (2 / n))
        (fun t => semiBanditEstimate (ℓ t) (v t ω) (x t ω)) (fun t => x t ω)
        (fun t => w t ω)) →
      (∀ t, 1 ≤ t → Measurable (x t)) → (∀ t, 1 ≤ t → Measurable (v t)) →
      (∀ t, 1 ≤ t → ∀ ω, v t ω ∈ C) →
      (∀ t, 1 ≤ t → condExpGiven P (x t) (v t) =ᵐ[P] x t) →
      ∀ y ∈ convexHull ℝ C,
        ∫ ω, ∑ t ∈ Finset.Icc 1 n, ℓ t ⬝ᵥ v t ω ∂P - ∑ t ∈ Finset.Icc 1 n, ℓ t ⬝ᵥ y ≤
          2 * Real.sqrt (2 * m * d * n)) := by sorry

end RegretBandits.Linear
Source
Bubeck, Cesa-Bianchi, Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems, arXiv:1204.5721v2, p. 80, Theorem 5.7 (setting on p. 77, Eq. (5.5); proof on p. 81)
Human review
  • Endorsed by Shuze Chen · Oct 4, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 4, 2026

    Confirmed by the mission captain (proposal self-audit).

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