Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 11.7: with probability at least μ10−μ20\mu^0_1 - \mu^0_2μ10​−μ20​, GREEDY never chooses arm 2

Proved
IntroBandits.greedy_never_explores

by naimengye · Sep 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

bayesian-greedyincentivized-explorationmartingale

Theorem 11.7. With probability at least μ10−μ20\mu^0_1 - \mu^0_2μ10​−μ20​, GREEDY never chooses arm 2.

Formally: for every prior PPP (a probability measure on mean vectors, supported on the finite set F⊆[0,1]2F \subseteq [0,1]^2F⊆[0,1]2, correlated or not), every reward family, every bandit policy π\piπ that is GREEDY (11.2) and every horizon TTT, under the joint law of (μ,HT)(\mu, H_T)(μ,HT​) of the run,

Pr⁡[ at=1 for every round t≤T ]≥μ10−μ20,\Pr[\,a_t = 1 \text{ for every round } t \le T\,] \ge \mu^0_1 - \mu^0_2 ,Pr[at​=1 for every round t≤T]≥μ10​−μ20​,

where μa0=E[μa]\mu^0_a = \mathbb{E}[\mu_a]μa0​=E[μa​] is the prior mean. The probability is written as ENNReal.ofReal(μ10−μ20)≤Pr⁡[⋅]\mathrm{ENNReal.ofReal}(\mu^0_1 - \mu^0_2) \le \Pr[\cdot]ENNReal.ofReal(μ10​−μ20​)≤Pr[⋅], so the statement is trivial when μ10<μ20\mu^0_1 < \mu^0_2μ10​<μ20​, as the book's is.

Preamble
import Definitions.Def_IntroBandits_Agents

open MeasureTheory ProbabilityTheory BanditAlgorithm
Formal statement
namespace IntroBandits

theorem greedy_never_explores (P : Measure (Fin 2 → ℝ)) [IsProbabilityMeasure P]
    (F : Finset (Fin 2 → ℝ)) (hF : P (↑F)ᶜ = 0)
    (hunit : ∀ μ ∈ F, ∀ a, μ a ∈ Set.Icc (0 : ℝ) 1) (fam : RewardFamily)
    {π : BanditPolicy 2} (hπ : IsGreedy P F fam π) (T : ℕ) :
    ENNReal.ofReal (priorMean P F 0 - priorMean P F 1) ≤
      jointMeasure P F fam π T (Set.univ ×ˢ {h | ∀ t, (h t).1 = 0}) := by sorry

end IntroBandits
Source
Slivkins, Introduction to Multi-Armed Bandits, arXiv:1904.07272 (FnT ML 12, 2019), §11.2 p. 148, Theorem 11.7, with its proof by optional stopping
Human review
  • Endorsed by Shuze Chen · Sep 25, 2026

    Confirmed by the moderator at approval.

  • Endorsed by naimengye · Sep 25, 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