Lemma 6.1, p. 20 — in a good epoch, if Tᵢ(ℓ) ≥ τ for every product offered, the offered assortment is optimal
ProvedMNLBandit.WellSeparated.lemma_6_1Consider the MNL-Bandit problem under Assumption 4.1 (, a feasible family of the form (2.3) closed under subsets), with revenues , and run Algorithm 1 with any tie-breaking rule along any history of customers. Let be the separation (6.1) and
Suppose the upper confidence bounds computed at the end of epoch are good, and the assortment chosen from them is offered within the horizon. If every product satisfies and , then
Once every product of the offered assortment has been sampled often enough, a good epoch offers an optimal assortment. Lemma 6.2 turns this into a bound on the number of good epochs that offer a sub-optimal assortment.
Formalization Note The page says "let be a good epoch and the assortment offered in epoch ". Algorithm 1 chooses an assortment from the bounds of the previous epoch, so the statement pairs the good bounds computed at the end of epoch with the set they select. Its proof (p. 46) uses Lemma 4.3 in the same way. "Offered in at least good epochs" is formalized by the lemma's own "i.e. ". The extra matters only when , that is when , where the good-epoch bound says nothing for unsampled products. The statement is pathwise: it holds along every history of the algorithm.
import Mathlib import Definitions.Def_ChoiceCDLP_MNL_mnlObjective import Definitions.Def_MNLBandit_WellSeparated_Setting
namespace MNLBandit.WellSeparated
open ChoiceCDLP.MNL
/-- Lemma 6.1, p. 20, for Algorithm 1 under Assumption 4.1 and `r_i ∈ [0, 1]`, along any history
`h` of `T` customers: if the UCBs computed at the end of epoch `ℓ` are good, the assortment
`S_{ℓ+1}` chosen from them is offered within the horizon, and every product `i ∈ S_{ℓ+1}` has
`T_i(ℓ) ≥ τ` (and `T_i(ℓ) ≥ 1`), then `S_{ℓ+1}` is optimal: `R(S_{ℓ+1}, v) = R(S*, v)`. -/
theorem lemma_6_1 (N : ℕ) (v r : Fin N → ℝ) (𝒮 : Finset (Finset (Fin N))) (h𝒮 : 𝒮.Nonempty)
(sel : (Finset (Fin N) → ℝ) → Finset (Fin N))
(hTU : MNLBandit.UCB.IsTU 𝒮) (hdown : MNLBandit.UCB.DownClosed 𝒮) (hv : ∀ i, 0 ≤ v i ∧ v i ≤ 1)
(hr : ∀ i, r i ∈ Set.Icc (0 : ℝ) 1) (hsel : MNLBandit.UCB.IsArgmaxSel 𝒮 sel)
(T : ℕ) (h : Fin T → Option (Fin N)) (ℓ : ℕ)
(hℓ : ℓ < epochsStarted r sel h) (hgood : IsGood v r sel h ℓ)
(hcount : ∀ i ∈ epochSet r sel h (ℓ + 1),
1 ≤ Tcount r sel h i ℓ ∧ tau N T (gap v r 𝒮 h𝒮) ≤ Tcount r sel h i ℓ) :
revenue v r (epochSet r sel h (ℓ + 1)) = MNLBandit.UCB.optRevenue v r 𝒮 h𝒮 := by sorry
end MNLBandit.WellSeparated
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.