Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 6.1, p. 20 — in a good epoch, if Tᵢ(ℓ) ≥ τ for every product offered, the offered assortment is optimal

Proved
MNLBandit.WellSeparated.lemma_6_1

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

assortment-optimizationinstance-dependent-regretmnl-banditp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Consider the MNL-Bandit problem under Assumption 4.1 (0≤vi≤v0=10\le v_i\le v_0=10≤vi​≤v0​=1, a feasible family S\mathcal SS of the form (2.3) closed under subsets), with revenues ri∈[0,1]r_i\in[0,1]ri​∈[0,1], and run Algorithm 1 with any tie-breaking rule along any history of TTT customers. Let Δ(v)\Delta(\mathbf v)Δ(v) be the separation (6.1) and

τ=4NClog⁡NTΔ2(v),C=max⁡{C12,C2}.\tau=\frac{4NC\log NT}{\Delta^2(\mathbf v)},\qquad C=\max\{C_1^2,C_2\}.τ=Δ2(v)4NClogNT​,C=max{C12​,C2​}.

Suppose the upper confidence bounds computed at the end of epoch ℓ\ellℓ are good, and the assortment Sℓ+1S_{\ell+1}Sℓ+1​ chosen from them is offered within the horizon. If every product i∈Sℓ+1i\in S_{\ell+1}i∈Sℓ+1​ satisfies Ti(ℓ)≥τT_i(\ell)\ge\tauTi​(ℓ)≥τ and Ti(ℓ)≥1T_i(\ell)\ge1Ti​(ℓ)≥1, then

R(Sℓ+1,v)=R(S∗,v).R(S_{\ell+1},\mathbf v)=R(S^*,\mathbf v).R(Sℓ+1​,v)=R(S∗,v).

Once every product of the offered assortment has been sampled often enough, a good epoch offers an optimal assortment. Lemma 6.2 turns this into a bound on the number of good epochs that offer a sub-optimal assortment.

Formalization Note The page says "let ℓ\ellℓ be a good epoch and SℓS_\ellSℓ​ the assortment offered in epoch ℓ\ellℓ". Algorithm 1 chooses an assortment from the bounds of the previous epoch, so the statement pairs the good bounds computed at the end of epoch ℓ\ellℓ with the set Sℓ+1S_{\ell+1}Sℓ+1​ they select. Its proof (p. 46) uses Lemma 4.3 in the same way. "Offered in at least τ\tauτ good epochs" is formalized by the lemma's own "i.e. Ti(ℓ)≥τT_i(\ell)\ge\tauTi​(ℓ)≥τ". The extra Ti(ℓ)≥1T_i(\ell)\ge1Ti​(ℓ)≥1 matters only when τ≤0\tau\le0τ≤0, that is when NT≤1NT\le1NT≤1, where the good-epoch bound says nothing for unsampled products. The statement is pathwise: it holds along every history of the algorithm.

Preamble
import Mathlib
import Definitions.Def_ChoiceCDLP_MNL_mnlObjective
import Definitions.Def_MNLBandit_WellSeparated_Setting
Formal statement
namespace MNLBandit.WellSeparated

open ChoiceCDLP.MNL

/-- Lemma 6.1, p. 20, for Algorithm 1 under Assumption 4.1 and `r_i ∈ [0, 1]`, along any history
`h` of `T` customers: if the UCBs computed at the end of epoch `ℓ` are good, the assortment
`S_{ℓ+1}` chosen from them is offered within the horizon, and every product `i ∈ S_{ℓ+1}` has
`T_i(ℓ) ≥ τ` (and `T_i(ℓ) ≥ 1`), then `S_{ℓ+1}` is optimal: `R(S_{ℓ+1}, v) = R(S*, v)`. -/
theorem lemma_6_1 (N : ℕ) (v r : Fin N → ℝ) (𝒮 : Finset (Finset (Fin N))) (h𝒮 : 𝒮.Nonempty)
    (sel : (Finset (Fin N) → ℝ) → Finset (Fin N))
    (hTU : MNLBandit.UCB.IsTU 𝒮) (hdown : MNLBandit.UCB.DownClosed 𝒮) (hv : ∀ i, 0 ≤ v i ∧ v i ≤ 1)
    (hr : ∀ i, r i ∈ Set.Icc (0 : ℝ) 1) (hsel : MNLBandit.UCB.IsArgmaxSel 𝒮 sel)
    (T : ℕ) (h : Fin T → Option (Fin N)) (ℓ : ℕ)
    (hℓ : ℓ < epochsStarted r sel h) (hgood : IsGood v r sel h ℓ)
    (hcount : ∀ i ∈ epochSet r sel h (ℓ + 1),
      1 ≤ Tcount r sel h i ℓ ∧ tau N T (gap v r 𝒮 h𝒮) ≤ Tcount r sel h i ℓ) :
    revenue v r (epochSet r sel h (ℓ + 1)) = MNLBandit.UCB.optRevenue v r 𝒮 h𝒮 := by sorry

end MNLBandit.WellSeparated
Source
Agrawal, Avadhanula, Goyal, Zeevi, MNL-Bandit: A Dynamic Learning Approach to Assortment Selection, arXiv:1706.03880v2, p. 20, Lemma 6.1 (with (6.1), p. 19, and (6.2), p. 20; proof p. 46)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

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