Lemma A.2, pp. 33–34 — concentration of the epoch averages v̄ᵢ,ℓ of Algorithm 1 (6/(Nℓ), 4/(Nℓ), 3/(Nℓ))
ProvedMNLBandit.UCB.lemma_A_2concentration-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 (2.3) and closed under subsets, and Algorithm 1 run with any argmax tie-breaking rule. For an epoch index and a product , write and for the number of the first epochs that offered and the average of their purchase counts of , and . Then, for every horizon , with probabilities over the first customers and restricted to histories in which epoch is completed and ,
These bounds are the probabilistic core of the upper confidence bounds (3.4): they give Lemma 4.1 directly.
Formalization Note.
- The paper prints as the second term of the first bound; its proof (Corollary D.1 and (D.22)) and every use ((A.4)–(A.5)) have , which is stated here.
- is undefined when ; the events require .
- The paper's statement is for the infinite-horizon process ("for every epoch "). Here it is stated for every finite horizon , on the event that epoch has been completed by customer ; uniformity in is the infinite-horizon statement.
- The standing assumptions of §4 (TU and down-closed , ) are carried as hypotheses.
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_A_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)
(T ℓ : ℕ) (hℓ : 1 ≤ ℓ) (i : Fin N) :
probT v (alg1 r sel) T (fun h =>
ℓ ≤ epochsDone r sel h ∧ 1 ≤ Tcount r sel h i ℓ ∧
|vbar r sel h i ℓ - v i| >
Real.sqrt (48 * vbar r sel h i ℓ * Real.log (Real.sqrt N * ℓ + 1)
/ Tcount r sel h i ℓ)
+ 48 * Real.log (Real.sqrt N * ℓ + 1) / Tcount r sel h i ℓ)
≤ 6 / (N * ℓ) ∧
probT v (alg1 r sel) T (fun h =>
ℓ ≤ epochsDone r sel h ∧ 1 ≤ Tcount r sel h i ℓ ∧
|vbar r sel h i ℓ - v i| >
Real.sqrt (24 * v i * Real.log (Real.sqrt N * ℓ + 1) / Tcount r sel h i ℓ)
+ 48 * Real.log (Real.sqrt N * ℓ + 1) / Tcount r sel h i ℓ)
≤ 4 / (N * ℓ) ∧
probT v (alg1 r sel) T (fun h =>
ℓ ≤ epochsDone r sel h ∧ 1 ≤ Tcount r sel h i ℓ ∧
vbar r sel h i ℓ >
3 * v i / 2 + 48 * Real.log (Real.sqrt N * ℓ + 1) / Tcount r sel h i ℓ)
≤ 3 / (N * ℓ) := by sorry
end MNLBandit.UCB
Source
Agrawal, Avadhanula, Goyal, Zeevi, MNL-Bandit: A Dynamic Learning Approach to Assortment Selection, arXiv:1706.03880v2, pp. 33–34, Lemma A.2 (proof p. 56)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.