(A.14), p. 37 — the regret of Algorithm 1 is at most 𝔼 Σ_{ℓ≤L} (1 + V(S_ℓ))(R(S*, v) − R(S_ℓ, v))
ProvedMNLBandit.UCB.eq_A_14Consider 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. For a horizon , let be the number of epochs started within the first customers, the assortment of epoch , and . Then
The factor is the expected length of an epoch offering , so the regret, a sum over customers, is controlled by a sum over epochs; this is where the per-epoch bound of Lemma 4.3 enters.
Formalization Note. The paper prints (A.14) as an equality. Over a finite horizon the last epoch is cut at customer and contributes less than its expected full length, so only "" holds; the inequality is what the proof of Theorem 1 uses.
import Mathlib import Definitions.Def_ChoiceCDLP_MNL_mnlObjective import Definitions.Def_MNLBandit_UCB_Setting import Definitions.Def_MNLBandit_UCB_Algorithm1
namespace MNLBandit.UCB
open ChoiceCDLP.MNL
theorem eq_A_14 {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 : ℕ) :
regret v r 𝒮 hne (alg1 r sel) T ≤
∑ h : History N T, histProb v (alg1 r sel) h *
∑ ℓ ∈ Finset.range (epochsStarted h),
(1 + ∑ j ∈ nextSet r sel h ℓ, v j) *
(optRevenue v r 𝒮 hne - mnlObjective v r 1 (nextSet r sel h ℓ)) := by sorry
end MNLBandit.UCB
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.