Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 5.3, p. 32 — A-armed bandit, M̄(π) = Ber(1/2): dec_γ(M^∞_{ε_γ}(M̄), M̄) ≥ 2⁻⁶·A/γ for γ ≥ A/3, ε_γ = A/(12γ)

Proved
StatComplexityDM.MAB.mab_localized_dec_lower_bound

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

decision-estimation-coefficientlower-boundmulti-armed-banditp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1

Consider the multi-armed bandit problem with A≥2A \ge 2A≥2 actions Π=[A]\Pi = [A]Π=[A] and rewards in [0,1][0,1][0,1], and the reference model M‾(π)=Ber(12)\overline{M}(\pi) = \mathrm{Ber}(\tfrac12)M(π)=Ber(21​) for every arm. For every γ≥A/3\gamma \ge A/3γ≥A/3, with εγ=A12γ\varepsilon_\gamma = \frac{A}{12\gamma}εγ​=12γA​,

decγ(Mεγ∞(M‾),M‾)≥2−6⋅Aγ,\mathsf{dec}_\gamma\bigl(\mathcal{M}^\infty_{\varepsilon_\gamma}(\overline{M}), \overline{M}\bigr) \ge 2^{-6} \cdot \frac{A}{\gamma},decγ​(Mεγ​∞​(M),M)≥2−6⋅γA​,

where decγ(M,M‾)=inf⁡p∈Δ(Π)sup⁡M∈MEπ∼p[fM(πM)−fM(π)−γDH2(M(π),M‾(π))]\mathsf{dec}_\gamma(\mathcal{M}, \overline{M}) = \inf_{p \in \Delta(\Pi)} \sup_{M \in \mathcal{M}} \mathbb{E}_{\pi \sim p}[f^M(\pi_M) - f^M(\pi) - \gamma D^2_{\mathrm{H}}(M(\pi), \overline{M}(\pi))]decγ​(M,M)=infp∈Δ(Π)​supM∈M​Eπ∼p​[fM(πM​)−fM(π)−γDH2​(M(π),M(π))] is the Decision-Estimation Coefficient and Mε∞(M‾)\mathcal{M}^\infty_{\varepsilon}(\overline{M})Mε∞​(M) is the L∞L_\inftyL∞​-localized class (12).

Combined with the paper's in-expectation lower bound (Theorem 3.2), this yields the Ω(AT)\Omega(\sqrt{AT})Ω(AT​) minimax regret lower bound for multi-armed bandits, matching the DEC upper bounds of Propositions 5.1 and 5.2 up to constants.

Formalization Note The model class is the Bernoulli bandits (reward distributions supported on {0,1}\{0,1\}{0,1}), a subclass of the paper's class of all distributions on [0,1][0,1][0,1]; since the localized class shrinks and the DEC decreases when passing to a subclass, this bound implies the paper's. The bound holds for every selector πM\pi_MπM​ of optimal arms. The constant 2−62^{-6}2−6 is the page's; its proof yields 1/481/481/48.

Preamble
import Mathlib
import Definitions.Def_FoundationsRL_GeneralDM_DEC
import Definitions.Def_StatComplexityDM_LowerBound_Core
import Definitions.Def_StatComplexityDM_MAB_Bernoulli
Formal statement
namespace StatComplexityDM.MAB

open FoundationsRL.GeneralDM

/-- Proposition 5.3 (arXiv:2112.13487v3, p. 32): for the multi-armed bandit with `A ≥ 2` arms,
rewards in `[0, 1]` and reference model `M̄(π) = Ber(1/2)`,
`dec_γ(M^∞_{ε_γ}(M̄), M̄) ≥ 2⁻⁶ · A/γ` for all `γ ≥ A/3`, where `ε_γ = A/(12γ)`.
The class is the Bernoulli bandits (a subclass of the paper's, which makes the bound stronger),
`dec_γ` is `decGf` (2) and `M^∞_ε(M̄)` is `linfLocalized` (12); the bound holds for every selector
`piStar` of maximizers of the mean reward. -/
theorem mab_localized_dec_lower_bound (A : ℕ) (hA : 2 ≤ A)
    (piStar : (Fin A → Bool → ℝ) → Fin A) (hpiStar : StatComplexityDM.LowerBound.IsArgmaxSel berRew piStar)
    (γ : ℝ) (hγ : (A : ℝ) / 3 ≤ γ) :
    (2 : ℝ) ^ (-6 : ℤ) * ((A : ℝ) / γ) ≤
      decGf (StatComplexityDM.LowerBound.linfLocalized (bernoulliBandits A) berRew piStar (fun _ => ber (1 / 2))
          ((A : ℝ) / (12 * γ)))
        berRew piStar γ (fun _ => ber (1 / 2)) := by sorry

end StatComplexityDM.MAB
Source
arXiv:2112.13487v3, Proposition 5.3, p. 32
Human review
  • Endorsed by Shuze Chen · Oct 9, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 9, 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