Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1 — full-domain EXP2 regret lower bound (corrected: excludes dimension one)

Proved
OnlineCombOpt.Exp2Full.theorem_1_full_domain

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

Let n,d∈Nn,d\in\mathbb Nn,d∈N satisfy n≥dn\ge dn≥d and d≠1d\ne1d=1. There exist a finite nonempty action set A⊆{0,1}d\mathcal A\subseteq\{0,1\}^dA⊆{0,1}d and a natural number mmm such that every a∈Aa\in\mathcal Aa∈A has ∑i=1da(i)=m\sum_{i=1}^d a(i)=m∑i=1d​a(i)=m, and the following holds for every fixed real learning rate η≥0\eta\ge0η≥0.

Some deterministic oblivious loss sequence zt∈[0,1]dz_t\in[0,1]^dzt​∈[0,1]d forces the full-information EXP2 strategy, initialized uniformly on A\mathcal AA and updated by Figure 2, to satisfy

Rn(A,η,z)=∑t=1n∑a∈Apt(a)a⊤zt−min⁡a∈A∑t=1na⊤zt≥1100ddn.R_n(\mathcal A,\eta,z) =\sum_{t=1}^n\sum_{a\in\mathcal A}p_t(a)a^\top z_t -\min_{a\in\mathcal A}\sum_{t=1}^n a^\top z_t \ge\frac1{100}d\sqrt d\sqrt n.Rn​(A,η,z)=t=1∑n​a∈A∑​pt​(a)a⊤zt​−a∈Amin​t=1∑n​a⊤zt​≥1001​dd​n​.

The set A\mathcal AA and its common weight mmm are chosen before η\etaη; the loss sequence may depend on η,n,d\eta,n,dη,n,d. This witness implies the paper's lower bound on the supremum over admissible adversaries. The assertion retains every d≥2d\ge2d≥2, every n≥dn\ge dn≥d including odd horizons, and η=0\eta=0η=0. At d=0d=0d=0 the singleton empty vector gives regret and bound zero, including when n=0n=0n=0.

This result records the limitation of treating each combinatorial action as an independent expert, uniformly over the choice of a fixed learning rate.

Formalization Note The imported probability recursion is the actual full-information update, without exploration mixing. The finite sum is the exact expected loss against the chosen deterministic sequence. The comparator minimum is outside the expectation in the source; determinism makes it the displayed finite minimum.

Differences from the source:

  • correction: unrestricted dimension → d≠1d\ne1d=1; reason: at d=n=1d=n=1d=n=1, every nonempty constant-weight binary action set is either {0}\{0\}{0} or {1}\{1\}{1}, so every admissible loss process has regret zero while the claimed bound is 0.010.010.01.
  • generalization: supremum over admissible adversaries at least the threshold → a deterministic oblivious sequence attains the threshold; reason: a witness in this admissible subclass implies the source's supremum inequality, including attainment that the supremum alone does not assert.
  • encoding: coordinates and rounds numbered from one → vectors indexed by Fin d and rounds indexed from zero; reason: index ttt represents source round t+1t+1t+1, preserving the strictly earlier losses in each probability update.
  • encoding: expected cumulative loss minus minimum expected comparator loss → finite probability-weighted loss minus a nonempty finite minimum for the deterministic witness; reason: these are exactly the source expectations for deterministic losses, with no integrability default or empty minimum.
  • encoding: 0.01d3/2n0.01d^{3/2}\sqrt n0.01d3/2n​ → exact real (1/100)ddn(1/100)d\sqrt d\sqrt n(1/100)dd​n​; reason: natural dimensions are nonnegative, so the real expressions agree, with no natural division or floating-point approximation.
  • encoding: losses specified for the first nnn rounds → a sequence on all natural rounds with every coordinate in [0,1][0,1][0,1]; reason: every bounded finite sequence extends by zero beyond the horizon and regret uses only the first nnn terms.
Preamble
import Mathlib
import Definitions.Def_OnlineCombOpt_Exp2LB_Setting

open Finset

open OnlineCombOpt.Exp2LB
Formal statement
namespace OnlineCombOpt.Exp2Full

/-- Theorem 1, corrected only by excluding dimension one (Audibert, Bubeck and Lugosi,
arXiv:1204.4710v2, p. 6; setting p. 2 and Figure 2 p. 7).
For every `n ≥ d` and `d ≠ 1`, one nonempty constant-weight binary action set works for every
fixed learning rate `η ≥ 0`. A deterministic oblivious bounded loss sequence attains the exact
lower bound `0.01 d^(3/2) √n`, strengthening the source's adversary-supremum conclusion.
The source fails at `d = n = 1`: every admissible action set is a singleton and has regret zero,
whereas the asserted bound is `0.01`. No divisibility, parity or positive-rate restriction is
imposed here. Dimension zero, including horizon zero, remains in the statement.
Indices are zero-based, and all losses after the horizon may be extended by zero. -/
theorem theorem_1_full_domain (n d : ℕ) (hnd : d ≤ n) (hd : d ≠ 1) :
    ∃ (A : Finset (Fin d → ℝ)) (m : ℕ), IsBinaryActionSet A m ∧
      ∀ η : ℝ, 0 ≤ η → ∃ z : ℕ → Fin d → ℝ,
        (∀ t i, z t i ∈ Set.Icc (0 : ℝ) 1) ∧
        (1 : ℝ) / 100 * d * Real.sqrt d * Real.sqrt n ≤ exp2Regret A η z n := by sorry

end OnlineCombOpt.Exp2Full
Source
Audibert, Bubeck, Lugosi, Regret in Online Combinatorial Optimization, arXiv:1204.4710v2, p. 6, Theorem 1 (proof in App. A, pp. 14–16)

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