Lemma 6.2, p. 20 — Algorithm 1 offers sub-optimal assortments in at most Nτ good epochs
ProvedMNLBandit.WellSeparated.lemma_6_2Consider 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 as in (6.2), and let be the number of epochs started within the horizon. Then
In words: Algorithm 1 cannot offer sub-optimal assortments in more than good epochs.
Together with the fact that bad epochs are rare, this bounds the number of epochs in which the algorithm loses revenue. This is the step that gives the logarithmic dependence on in Theorem 3.
Formalization Note As in Lemma 6.1, a good epoch is paired with the assortment selected by its upper confidence bounds. Epoch (the first assortment, chosen from ) is included in the count. The bound is pathwise: it holds along every history.
import Mathlib import Definitions.Def_ChoiceCDLP_MNL_mnlObjective import Definitions.Def_MNLBandit_WellSeparated_Setting
namespace MNLBandit.WellSeparated
open ChoiceCDLP.MNL
open Classical in
/-- Lemma 6.2, p. 20, for Algorithm 1 under Assumption 4.1 and `r_i ∈ [0, 1]`, along any history
`h` of `T` customers: among the epochs started within the horizon, at most `Nτ` are good epochs
offering a sub-optimal assortment (epoch `ℓ + 1` counted when the UCBs computed at the end of
epoch `ℓ` are good and `R(S_{ℓ+1}, v) < R(S*, v)`). -/
theorem lemma_6_2 (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)) :
(((Finset.range (epochsStarted r sel h)).filter (fun ℓ =>
IsGood v r sel h ℓ ∧
revenue v r (epochSet r sel h (ℓ + 1)) < MNLBandit.UCB.optRevenue v r 𝒮 h𝒮)).card : ℝ)
≤ N * tau N T (gap v r 𝒮 h𝒮) := by sorry
end MNLBandit.WellSeparated
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.