A regret lower bound for assortment optimization under the capacitated MNL model with arbitrary revenue parameters. Issue 4 (October 2022)

• Record Type: Journal Article
• Authors: Peeters, Yannik; den Boer, Arnoud V.
• Is Part Of: Probability in the engineering and informational sciences. Volume 36:Issue 4(2022)
• Page Start: 1266
• Page End: 1274
• Publication Date: 2022-10
• Subjects: Assortment optimization -- Incomplete information -- Multinomial logit model -- Regret lower bound; Probabilities -- Periodicals; Engineering -- Statistical methods -- Periodicals; Information science -- Statistical methods -- Periodicals; 519.202462
• DOI: 10.1017/S0269964821000395
• Languages: English
• ISSNs: 0269-9648

Abstract

Abstract: In this note, we consider dynamic assortment optimization with incomplete information under the capacitated multinomial logit choice model. Recently, it has been shown that the regret (the cumulative expected revenue loss caused by offering suboptimal assortments) that any decision policy endures is bounded from below by a constant times $\sqrt {NT}$, where $N$ denotes the number of products and $T$ denotes the time horizon. This result is shown under the assumption that the product revenues are constant, and thus leaves the question open whether a lower regret rate can be achieved for nonconstant revenue parameters. In this note, we show that this is not the case: we show that, for any vector of product revenues there is a positive constant such that the regret of any policy is bounded from below by this constant times $\sqrt {N T}$ . Our result implies that policies that achieve ${{\mathcal {O}}}(\sqrt {NT})$ regret are asymptotically optimal for all product revenue parameters.