Lemma 4.1, p. 13 — v^UCB_{i,ℓ} ≥ vᵢ w.p. ≥ 1 − 6/(Nℓ), and its convergence rate w.p. ≥ 1 − 7/(Nℓ)
ProvedMNLBandit.UCB.lemma_4_1concentration-inequalitymnl-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 , let be a product, and write . For every horizon , with probabilities restricted to histories in which epoch is completed by customer :
- the upper confidence bound is optimistic,
- with and , on the event ,
Optimism (part 1) drives Lemma 4.2 and the convergence rate (part 2) drives Lemma 4.3.
Formalization Note.
- The lemma says "there exist constants and "; the values and are those its proof establishes (p. 35, last display before Lemma A.3), a disclosed instantiation of the existential.
- Part 2 needs (the right side divides by it). Part 1 needs no such guard: while the algorithm keeps .
- Finite horizon and the event "epoch completed" as in Lemma A.2; uniformity in is the paper's statement.
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_1 {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)
(T ℓ : ℕ) (hℓ : 1 ≤ ℓ) (i : Fin N) :
probT v (alg1 r sel) T (fun h =>
ℓ ≤ epochsDone r sel h ∧ vUCB r sel h i ℓ < v i) ≤ 6 / (N * ℓ) ∧
probT v (alg1 r sel) T (fun h =>
ℓ ≤ epochsDone r sel h ∧ 1 ≤ Tcount r sel h i ℓ ∧
vUCB r sel h i ℓ - v i >
(Real.sqrt 72 + Real.sqrt 24)
* Real.sqrt (v i * Real.log (Real.sqrt N * ℓ + 1) / Tcount r sel h i ℓ)
+ 144 * Real.log (Real.sqrt N * ℓ + 1) / Tcount r sel h i ℓ)
≤ 7 / (N * ℓ) := 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.1 (proof pp. 34–35)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.