Lemma 5.1, p. 15 — every online algorithm has expected regret at least ϵT/6 on I_MAB
ProvedMNLBandit.LowerBound.lemma_5_1Let arms, a horizon , , and
with . On the randomized Bernoulli instance (Definition 5.1: a hidden arm , uniform on , has mean and every other arm mean ), every online algorithm , deterministic or randomized, that plays arm at time satisfies
where the expectation is over the hidden arm and over the rewards of the pulled arms (and the algorithm's own randomization).
This MAB lower bound is what the reduction of §5.2 transfers to the MNL-Bandit problem under a cardinality constraint.
Formalization Note The page assumes only . That is not enough: for close to the biased arm is identified after few pulls and the bound fails; the proof sets " to be a small enough constant" (p. 19). The added hypothesis (which implies ) and restore it. is added because has in a denominator. The printed proof's line "Let " contradicts Definition 5.1; the lemma is stated with Definition 5.1's , which satisfies the proof's requirement . The printed is kept although the printed proof (via Lemma E.2) needs .
import Mathlib import Definitions.Def_MNLBandit_LowerBound_BernoulliMAB
namespace MNLBandit.LowerBound
theorem lemma_5_1 (N : ℕ) (hN : 2 ≤ N) (α : ℝ) (hα : 0 < α) (T : ℕ) (hT : 1 ≤ T)
(hαϵ : 2 * α + epsMAB N α T ≤ 1) (A : MABAlg N) (hA : IsMABAlg A) :
epsMAB N α T * T / 6 ≤ regretIMAB A α (epsMAB N α T) T := by sorry
end MNLBandit.LowerBound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.