Theorem 3, p. 20 — on well-separated instances Algorithm 1 has regret at most B₁N² log T/Δ(v) + B₂
ProvedMNLBandit.WellSeparated.theorem_3Consider the MNL-Bandit problem with products, revenues , and Assumption 4.1: the attraction parameters satisfy , and the feasible family has the totally unimodular form (2.3) and is closed under taking subsets. Let be the separation (6.1) between the expected revenues of the optimal and the second-best assortment.
There are absolute constants and such that for every such instance, every tie-breaking rule in the argmax of Algorithm 1, and every horizon , the regret of Algorithm 1 satisfies
The worst-case bound of Theorem 1 grows like . When the optimal assortment is separated from the others, the same algorithm, which does not know , has regret logarithmic in .
Formalization Note The constants are chosen before the number of products, the parameters, the revenues, the feasible family, the tie-breaking rule and the horizon. is stated as printed; the proof's final display (C.12) has , from which the printed form follows. When every feasible assortment is optimal, is a minimum over the empty set. Lean then uses the value ; the regret is in that case. The constraint is the paper's normalization (p. 5).
import Mathlib import Definitions.Def_ChoiceCDLP_MNL_mnlObjective import Definitions.Def_MNLBandit_WellSeparated_Setting
namespace MNLBandit.WellSeparated
open ChoiceCDLP.MNL
/-- Theorem 3, p. 20 (arXiv:1706.03880v2): under Assumption 4.1 and `r_i ∈ [0, 1]`, the regret of
Algorithm 1 is at most `B₁ N² log T / Δ(v) + B₂` for absolute constants `B₁, B₂`, for every
tie-breaking rule of the argmax and every horizon `T`. -/
theorem theorem_3 :
∃ B₁ B₂ : ℝ, ∀ (N : ℕ) (v r : Fin N → ℝ) (𝒮 : Finset (Finset (Fin N))) (h𝒮 : 𝒮.Nonempty)
(sel : (Finset (Fin N) → ℝ) → Finset (Fin N)) (T : ℕ),
MNLBandit.UCB.IsTU 𝒮 → MNLBandit.UCB.DownClosed 𝒮 → (∀ i, 0 ≤ v i ∧ v i ≤ 1) → (∀ i, r i ∈ Set.Icc (0 : ℝ) 1) →
MNLBandit.UCB.IsArgmaxSel 𝒮 sel →
MNLBandit.UCB.regret v r 𝒮 h𝒮 (alg1 r sel) T ≤
B₁ * ((N : ℝ) ^ 2 * Real.log T / gap v r 𝒮 h𝒮) + B₂ := by sorry
end MNLBandit.WellSeparated
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.