Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4.2, p. 13 — R̃_{ℓ+1}(S_{ℓ+1}) ≥ R̃_{ℓ+1}(S*) ≥ R(S*, v) w.p. ≥ 1 − 6/ℓ

Proved
MNLBandit.UCB.lemma_4_2

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

assortment-optimizationmnl-banditp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1upper-confidence-bound

Consider the MNL-Bandit with NNN products, parameters 0≤vi≤v0=10\le v_i\le v_0=10≤vi​≤v0​=1, revenues ri∈[0,1]r_i\in[0,1]ri​∈[0,1], a feasible family S\mathcal SS given by totally unimodular constraints and closed under subsets, and Algorithm 1 with any argmax tie-breaking rule. Let S∗∈SS^*\in\mathcal SS∗∈S be an assortment with the highest expected revenue, R(S∗,v)=max⁡S∈SR(S,v)R(S^*,v)=\max_{S\in\mathcal S}R(S,v)R(S∗,v)=maxS∈S​R(S,v), all of whose products have vj>0v_j>0vj​>0. Let ℓ≥1\ell\ge1ℓ≥1. After epoch ℓ\ellℓ the algorithm computes v⋅,ℓUCBv^{\mathrm{UCB}}_{\cdot,\ell}v⋅,ℓUCB​, the optimistic revenue R~ℓ+1(S)=∑i∈Srivi,ℓUCB/(1+∑j∈Svj,ℓUCB)\tilde R_{\ell+1}(S)=\sum_{i\in S}r_iv^{\mathrm{UCB}}_{i,\ell}/(1+\sum_{j\in S}v^{\mathrm{UCB}}_{j,\ell})R~ℓ+1​(S)=∑i∈S​ri​vi,ℓUCB​/(1+∑j∈S​vj,ℓUCB​) and the next assortment Sℓ+1S_{\ell+1}Sℓ+1​. For every horizon TTT, with probabilities restricted to histories in which epoch ℓ\ellℓ is completed by customer TTT,

R~ℓ+1(Sℓ+1)≥R~ℓ+1(S∗)≥R(S∗,v)with probability at least 1−6ℓ.\tilde R_{\ell+1}(S_{\ell+1})\ge\tilde R_{\ell+1}(S^*)\ge R(S^*,v)\qquad\text{with probability at least }1-\frac{6}{\ell}.R~ℓ+1​(Sℓ+1​)≥R~ℓ+1​(S∗)≥R(S∗,v)with probability at least 1−ℓ6​.

In words, the optimistic estimate of the chosen assortment upper-bounds the optimal expected revenue with high probability.

Formalization Note.

  1. Index reading. The page writes R~ℓ(Sℓ)\tilde R_\ell(S_\ell)R~ℓ​(Sℓ​) with probability 1−6/ℓ1-6/\ell1−6/ℓ, while its proof ((A.9)–(A.10)) uses vi,ℓUCBv^{\mathrm{UCB}}_{i,\ell}vi,ℓUCB​, which by (3.7) and Algorithm 1 belongs to R~ℓ+1\tilde R_{\ell+1}R~ℓ+1​ and Sℓ+1S_{\ell+1}Sℓ+1​. The statement uses the estimate built at the end of epoch ℓ\ellℓ.
  2. Positivity on S∗S^*S∗. The page's "the assortment with highest expected revenue" is read as an optimal assortment containing no product with vj=0v_j=0vj​=0; such an optimum always exists (removing products with vj=0v_j=0vj​=0 keeps the revenue and, by closure under subsets, feasibility). For an optimum containing a product with vj=0v_j=0vj​=0, the middle inequality can fail with high probability (see Lemma A.3's note).
  3. Finite horizon TTT and the event "epoch ℓ\ellℓ completed", as in Lemma A.2.
Preamble
import Mathlib
import Definitions.Def_ChoiceCDLP_MNL_mnlObjective
import Definitions.Def_MNLBandit_UCB_Setting
import Definitions.Def_MNLBandit_UCB_Algorithm1
Formal statement
namespace MNLBandit.UCB

open ChoiceCDLP.MNL

theorem lemma_4_2 {N : ℕ} (v r : Fin N → ℝ)
    (𝒮 : Finset (Finset (Fin N))) (sel : (Finset (Fin N) → ℝ) → Finset (Fin N))
    (hTU : IsTU 𝒮) (hdc : DownClosed 𝒮) (hne : 𝒮.Nonempty) (hsel : IsArgmaxSel 𝒮 sel)
    (hv0 : ∀ i, 0 ≤ v i) (hv1 : ∀ i, v i ≤ 1) (hr : ∀ i, r i ∈ Set.Icc (0 : ℝ) 1)
    (Sstar : Finset (Fin N)) (hSstar : Sstar ∈ 𝒮)
    (hopt : mnlObjective v r 1 Sstar = optRevenue v r 𝒮 hne)
    (hpos : ∀ j ∈ Sstar, 0 < v j)
    (T ℓ : ℕ) (hℓ : 1 ≤ ℓ) :
    probT v (alg1 r sel) T (fun h =>
        ℓ ≤ epochsDone r sel h ∧
        ¬ (mnlObjective (fun j => vUCB r sel h j ℓ) r 1 (nextSet r sel h ℓ) ≥
              mnlObjective (fun j => vUCB r sel h j ℓ) r 1 Sstar ∧
            mnlObjective (fun j => vUCB r sel h j ℓ) r 1 Sstar ≥ mnlObjective v r 1 Sstar))
      ≤ 6 / ℓ := by sorry

end MNLBandit.UCB
Source
Agrawal, Avadhanula, Goyal, Zeevi, MNL-Bandit: A Dynamic Learning Approach to Assortment Selection, arXiv:1706.03880v2, p. 13, Lemma 4.2 (proof p. 36, (A.9)–(A.10))
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