Lemma 4.2, p. 13 — R̃_{ℓ+1}(S_{ℓ+1}) ≥ R̃_{ℓ+1}(S*) ≥ R(S*, v) w.p. ≥ 1 − 6/ℓ
ProvedMNLBandit.UCB.lemma_4_2assortment-optimizationmnl-banditp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1upper-confidence-bound
Consider the MNL-Bandit with products, parameters , revenues , a feasible family given by totally unimodular constraints and closed under subsets, and Algorithm 1 with any argmax tie-breaking rule. Let be an assortment with the highest expected revenue, , all of whose products have . Let . After epoch the algorithm computes , the optimistic revenue and the next assortment . For every horizon , with probabilities restricted to histories in which epoch is completed by customer ,
In words, the optimistic estimate of the chosen assortment upper-bounds the optimal expected revenue with high probability.
Formalization Note.
- Index reading. The page writes with probability , while its proof ((A.9)–(A.10)) uses , which by (3.7) and Algorithm 1 belongs to and . The statement uses the estimate built at the end of epoch .
- Positivity on . The page's "the assortment with highest expected revenue" is read as an optimal assortment containing no product with ; such an optimum always exists (removing products with keeps the revenue and, by closure under subsets, feasibility). For an optimum containing a product with , the middle inequality can fail with high probability (see Lemma A.3's note).
- Finite horizon and the event "epoch 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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.