Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3, p. 20 — on well-separated instances Algorithm 1 has regret at most B₁N² log T/Δ(v) + B₂

Proved
MNLBandit.WellSeparated.theorem_3

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

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

Consider the MNL-Bandit problem with NNN products, revenues ri∈[0,1]r_i\in[0,1]ri​∈[0,1], and Assumption 4.1: the attraction parameters satisfy 0≤vi≤v0=10\le v_i\le v_0=10≤vi​≤v0​=1, and the feasible family S\mathcal SS has the totally unimodular form (2.3) and is closed under taking subsets. Let Δ(v)\Delta(\mathbf v)Δ(v) be the separation (6.1) between the expected revenues of the optimal and the second-best assortment.

There are absolute constants B1B_1B1​ and B2B_2B2​ such that for every such instance, every tie-breaking rule in the argmax of Algorithm 1, and every horizon TTT, the regret of Algorithm 1 satisfies

Regπ(T,v)≤B1 N2log⁡TΔ(v)+B2.\mathrm{Reg}_\pi(T,\mathbf v)\le B_1\,\frac{N^2\log T}{\Delta(\mathbf v)}+B_2.Regπ​(T,v)≤B1​Δ(v)N2logT​+B2​.

The worst-case bound of Theorem 1 grows like T\sqrt{T}T​. When the optimal assortment is separated from the others, the same algorithm, which does not know Δ(v)\Delta(\mathbf v)Δ(v), has regret logarithmic in TTT.

Formalization Note The constants B1,B2B_1,B_2B1​,B2​ are chosen before the number of products, the parameters, the revenues, the feasible family, the tie-breaking rule and the horizon. log⁡T\log TlogT is stated as printed; the proof's final display (C.12) has log⁡NT\log NTlogNT, from which the printed form follows. When every feasible assortment is optimal, Δ(v)\Delta(\mathbf v)Δ(v) is a minimum over the empty set. Lean then uses the value 111; the regret is 000 in that case. The constraint v0=1v_0=1v0​=1 is the paper's normalization (p. 5).

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

open ChoiceCDLP.MNL

/-- Theorem 3, p. 20 (arXiv:1706.03880v2): under Assumption 4.1 and `r_i ∈ [0, 1]`, the regret of
Algorithm 1 is at most `B₁ N² log T / Δ(v) + B₂` for absolute constants `B₁, B₂`, for every
tie-breaking rule of the argmax and every horizon `T`. -/
theorem theorem_3 :
    ∃ B₁ B₂ : ℝ, ∀ (N : ℕ) (v r : Fin N → ℝ) (𝒮 : Finset (Finset (Fin N))) (h𝒮 : 𝒮.Nonempty)
      (sel : (Finset (Fin N) → ℝ) → Finset (Fin N)) (T : ℕ),
      MNLBandit.UCB.IsTU 𝒮 → MNLBandit.UCB.DownClosed 𝒮 → (∀ i, 0 ≤ v i ∧ v i ≤ 1) → (∀ i, r i ∈ Set.Icc (0 : ℝ) 1) →
      MNLBandit.UCB.IsArgmaxSel 𝒮 sel →
      MNLBandit.UCB.regret v r 𝒮 h𝒮 (alg1 r sel) T ≤
        B₁ * ((N : ℝ) ^ 2 * Real.log T / gap v r 𝒮 h𝒮) + B₂ := by sorry

end MNLBandit.WellSeparated
Source
Agrawal, Avadhanula, Goyal, Zeevi, MNL-Bandit: A Dynamic Learning Approach to Assortment Selection, arXiv:1706.03880v2, p. 20, Theorem 3 (Δ(v) from (6.1), p. 19; proof App. C, pp. 46–50)
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