Lemma 4.3, p. 14 — (1 + V(S_{ℓ+1}))(R̃_{ℓ+1}(S_{ℓ+1}) − R(S_{ℓ+1}, v)) ≤ Σᵢ[C₁√(vᵢ log(√Nℓ+1)/Tᵢ(ℓ)) + C₂ log(√Nℓ+1)/Tᵢ(ℓ)] w.p. ≥ 1 − 13/ℓ
ProvedMNLBandit.UCB.lemma_4_3mnl-banditp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1regretupper-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 , , and . Let be the assortment computed at the end of epoch and the optimistic revenue built from . For every horizon , with probabilities restricted to histories in which epoch is completed by customer and every product of has ,
with probability at least . This per-epoch rate is summed over epochs in the proof of Theorem 1.
Formalization Note.
- Sum over . The page's right-hand side has a free index ; its proof ((A.11)–(A.12), p. 36) gives the sum over , which is stated.
- Index reading. As in Lemma 4.2, the page's with , and is read as the estimate built at the end of epoch .
- Constants. "There exist constants and " is instantiated with the values of Lemma 4.1's proof.
- Guard. The right side divides by , so the event requires for every .
- Finite horizon 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_3 {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 ≤ ℓ) :
probT v (alg1 r sel) T (fun h =>
ℓ ≤ epochsDone r sel h ∧
(∀ i ∈ nextSet r sel h ℓ, 1 ≤ Tcount r sel h i ℓ) ∧
¬ ((1 + ∑ j ∈ nextSet r sel h ℓ, v j) *
(mnlObjective (fun j => vUCB r sel h j ℓ) r 1 (nextSet r sel h ℓ)
- mnlObjective v r 1 (nextSet r sel h ℓ)) ≤
∑ i ∈ nextSet r sel h ℓ,
((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 ℓ)))
≤ 13 / ℓ := by sorry
end MNLBandit.UCB
Source
Agrawal, Avadhanula, Goyal, Zeevi, MNL-Bandit: A Dynamic Learning Approach to Assortment Selection, arXiv:1706.03880v2, p. 14, Lemma 4.3 (proof p. 36, (A.11)–(A.12))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.