Theorem 2, p. 14 — under a K-cardinality constraint every policy has regret at least C√(NT/K) on a randomized instance
ProvedMNLBandit.LowerBound.theorem_2Setting. An MNL-Bandit instance with products consists of a no-purchase weight , attraction parameters with , and revenues . Offering an assortment yields one customer choice drawn from the MNL model for , and the expected revenue . A policy may be randomized; it respects the -cardinality constraint if it only offers assortments with . Its regret over periods is
where is an assortment of at most products with maximum expected revenue.
Theorem. There is an absolute constant such that for every number of products , every with and every horizon there is a randomized instance, a probability distribution with finite support over instances satisfying and . The values of and are common to every point in the support, as in the paper's constructions. Every policy respecting the -cardinality constraint has
The randomized instance is chosen before the policy and may depend on , and only. Together with the upper bound of Theorem 1 it shows that the epoch-based UCB policy is optimal up to logarithmic factors when is fixed.
Formalization Note The randomized instance is a finite list of instances with weights summing to ; the paper's instances (Definitions 5.2 and E.1) are uniform over finitely many values, so a finite support is faithful, and the regret is averaged over the instance as in Lemma 5.1. All support points share the same known revenues and no-purchase weight , as those constructions do. Without this clause, one common policy would be tested on instances distinguished by revenues known to the seller, weakening the lower bound. Policies are behavioural: at every history of offered sets and choices they draw the next assortment from a probability vector, which by Kuhn's theorem covers the paper's admissible policies (2.4). The page says "for any and "; the claim is false for (offering the single product whenever is optimal for every ) and for (only can be offered), so and are added; is the cardinality constraint's range. is part of the claim.
import Mathlib import Definitions.Def_MNLBandit_LowerBound_Setting
namespace MNLBandit.LowerBound
theorem theorem_2 :
∃ C : ℝ, 0 < C ∧ ∀ (n K T : ℕ), 2 ≤ n → 1 ≤ K → K ≤ n → n ≤ T →
∃ (m : ℕ) (w : Fin m → ℝ) (inst : Fin m → Instance n),
(∀ j, 0 ≤ w j) ∧ ∑ j, w j = 1 ∧ (∀ j, (inst j).Valid) ∧
(∀ j k, (inst j).v₀ = (inst k).v₀ ∧ (inst j).r = (inst k).r) ∧
∀ π : BPolicy n, IsCardinalityK K π →
C * Real.sqrt ((n : ℝ) * T / K) ≤ ∑ j, w j * regret (inst j) K π T := by sorry
end MNLBandit.LowerBound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.