A Note on a Tight Lower Bound for MNL-Bandit Assortment Selection Models

Xi Chen; Yining Wang

A Note on a Tight Lower Bound for MNL-Bandit Assortment Selection Models

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1709.06109 v3 pith:FDNAQRL2 submitted 2017-09-18 stat.ML cs.LG

Xi Chen , Yining Wang This is my paper

classification stat.MLcs.LG

keywords assortmentlowerregretboundboundsexistingnotetight

verification ladder T0 review T1 audit T2 compute T3 formal

0 comments

abstract

In this short note we consider a dynamic assortment planning problem under the capacitated multinomial logit (MNL) bandit model. We prove a tight lower bound on the accumulated regret that matches existing regret upper bounds for all parameters (time horizon $T$, number of items $N$ and maximum assortment capacity $K$) up to logarithmic factors. Our results close an $O(\sqrt{K})$ gap between upper and lower regret bounds from existing works.

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Diversified Multinomial Logit Contextual Bandits
stat.ML 2026-07 accept novelty 7.0 of 10

OFU-DMNL achieves a (1-1/(e+1))-approximate regret bound Õ(d √(T/K)) for contextual assortment selection under a diversity-augmented MNL choice model via item-wise optimistic construction.

Pith tools