Efficient Distributionally Robust Assortment Optimization in MNL Bandits

We investigate the distributionally robust assortment optimization (DRAO) problem under the contextual multinomial logit (MNL) choice model, where the decision-maker seeks to maximize revenue against worst-case distributional deviations. To address potential distribution shifts relative to the observed data environment, we study DRAO under ambiguity sets defined by three divergences: total variation (TV), Kullback–Leibler (KL), and chi-square ($\chi^2$). Incorporating robust concerns poses challenges for both algorithm design and theoretical analysis. By leveraging strong duality results from the distributionally robust optimization literature and integrating them into the assortment optimization procedures, we develop tailored polynomial-time algorithms under each divergence. We further provide a theoretical analysis and establish sample complexity bounds for all three robust formulations.

Online retailers and recommendation systems decide which products to show customers to maximize revenue. In practice, customer behavior often differs from what a model trained on historical data predicts: the underlying preferences may shift, or the model itself may be misspecified. We develop algorithms that choose product assortments that remain effective even when the customer's actual choice distribution lies within a plausible range around the learned model. We design efficient procedures under three standard ways of measuring distributional uncertainty, prove finite-sample guarantees on their performance, and validate them empirically. The result is a practical and theoretically grounded recipe for assortment decisions that hedge against realistic data drift.