Near-Optimal Policies for Dynamic Multinomial Logit Assortment Selection Models
In this paper we consider the dynamic assortment selection problem under an uncapacitated multinomial-logit (MNL) model. By carefully analyzing a revenue potential function, we show that a trisection based algorithm achieves an item-independent regret bound of Op ? T log log T q, which matches information theoretical lower bounds up to iterated logarithmic terms. Our proof technique draws tools from the unimodal/convex bandit literature as well as adaptive confidence parameters in minimax multi-armed bandit problems.
Summary:  In the paper, the authors consider an online assortment problem, where each customer chooses his/her purchase from the offered assortment according to a multinomial logit choice model. The preference weights in the choice model are unknown to the seller, who aims to maximize the total revenue under the model uncertainty. The authors consider the unconstrained setting, which allows the seller to offer any subset of products as the assortment. This is different from most online assortment optimization literature, which consider the constrained setting where there is a cardinality constraint on the number of products in an assortment.  The authors first note the fact that, in the unconstrained setting, the optimal assortment lies in the sequence of revenue-ordered assortments. Using the established facts that the sequence of revenue-ordered assortments is nested and the sequence of mean revenue associated with the sequence of assortments, the authors transform the assortment optimization problem to a certain unimodal bandit problem. The authors accomplish a O(sqrt{T}log log T) regret bound, where T is the number of rounds, and the bound is independent of the number of products.   Major Comments:  While online assortment optimization is an important problem in the realm of e-commerce, I am not too convinced if the submission is sufficient for publication. Indeed, cardinality constraints are an important aspect in the e-commerce setting, since the seller can only display a limited number of products out of the set of all products, and the set is typically much larger than the display capacity. Therefore, with the absence of cardinality constraints, the submission shall be mainly weighted in terms of its theoretical contributions.  Given that the transformation to a unimodal optimization is a well-known result in the revenue optimization literature (for example, see the classical papers [TalluriVR04, RusmevichientongT12]), the main theoretical result shall be on addressing the unimodal bandit problem in the case of assortment optimization.  My major concern about the work is my difficulty in comparing the submission with existing works on unimodal bandits. While the submission claims (in Lines 96-97) that existing unimodal bandit literature requires structural assumptions such as convexity and inverse Lipschitz continuity, to my knowledge the design and analysis of Algorithm OSUB in [CP14] (see Sections 4.2, 4.3) seem not require any such sort of structural assumption. In fact, [CP14] seems to only require unimodality, same as the current paper. [CP14] provides a “gap-dependent” regret bound, while the current paper provides a “gap-independent” regret bound, where “gap” here refers to the difference between the optimal reward and a suitably defined second best reward. Understandably, we cannot directly compare a gap-independent regret bound with a gap-dependent one. Thus, we cannot conclude that the proposed algorithm in the submission achieves a better bound than Algorithm OSUB.  In relation to the previous comments, for assessment it will be beneficial for the authors to provide concrete examples (say in the supplementary material) on showing that structural assumptions such as convexity and inverse Lipchistz continuity (I believe that the literature are essentially [AFHKR13, YM11]) do not hold in the current problem setting.   (Post Rebuttal) I am convinced of the paper's technical novelty after the author's feedback. I feel that the improvement from log t to loglogt somehow overcome the models' limitation on the lack of capacity constraint.   Minor Comments: It shall be interesting to numerically compare the proposed algorithms with existing unimodal bandit algorithms [CP14, YM11] (in particular Algorithm OSUB in the former), and investigate if the proposed algorithms indeed suit better for the unconstrained assortment optimization problem empirically.  References [AFHKR13] A. Agarwal, D. P. Foster, D. Hsu, S. M. Kakade, and A. Rakhlin. Stochastic convex optimization with bandit feedback. SIAM Journal on Optimization, 23(1):213–240, 2013. [CP14] R. Combes and A. Proutiere. Unimodal bandits: Regret lower bounds and optimal algorithms. In ICML, 2014. [RT12] P. Rusmevichientong and H. Topaloglu. Robust assortment optimization in revenue management under the multinomial logit choice model. Operations Research, 60(4):865–882, 2012. [TVR04] Talluri, K., and G. J. van Ryzin. 2004. Revenue management under a general discrete choice model of consumer behavior. Management Science 50 (1): 15–33. [YM11] J. Y. Yu and S. Mannor. Unimodal bandits. In ICML, 2011.