The MNL-Bandit Problem

One fundamental problem in revenue management that arises in many settings including retail and display-based advertising is assortment planning. Here, the focus is on understanding how consumers select from a large number of substitutable items and identifying the optimal offer set to maximize revenues. Typically, for tractability, we assume a model that captures consumer preferences and focus on computing the optimal offer set. A significant challenge here is the lack of knowledge on consumer preferences. In this thesis, we consider the multinomial logit choice model, the most popular model for this application domain and develop tractable robust algorithms for assortment planning under uncertainty. We also quantify the fundamental performance limits from both computational and information theoretic perspectives for such problems. The existing methods for the dynamic problem follow ``estimate, then optimize'' paradigm, which require knowledge of certain parameters that are not readily available, thereby limiting their applicability in practice. We address this gap between theory and practice by developing new theoretical tools which will aid in designing algorithms that judiciously combine exploration and exploitation to maximize revenues. We first present an algorithm based on the principle of ``optimism under uncertainty'' that is simultaneously robust and adaptive to instance complexity. We then leverage this theory to develop a Thompson Sampling (TS) based framework with theoretical guarantees for the dynamic problem. This is primarily motivated by the growing popularity of TS approaches in practice due to their attractive empirical properties. We also indicate how to generalize the TS framework to design scalable dynamic learning algorithms for high-dimensional data and discuss empirical gains of such approaches from preliminary implementations on Flipkart, a large e-commerce firm in India.