Optimal Design for Multinomial Logit Model with Applications to Best Assortment Identification

We study optimal experimental design for multinomial logit (MNL) bandits, where an agent repeatedly selects a subset of $K$ items from a ground set of size $N$ and observes single-choice feedback. Unlike linear or generalized linear bandits, MNL bandits have a combinatorial action space, which makes classical optimal design approaches and naive optimization over all subsets computationally intractable. We propose a computationally efficient optimal design framework for MNL models that achieves both statistical efficiency and scalability through two complementary approaches: (i) an exact or certified-approximate reformulation of the design oracle as a $0$-$1$ mixed-integer linear program (MILP) with solver-certified early stopping, and (ii) a fully polynomial-time lifted design that replaces the nonlinear objective with a tractable surrogate. Using the Kiefer-Wolfowitz equivalence theorem, we establish near G-optimality guarantees and characterize the induced statistical-computational trade-offs. As an application, we develop a best assortment identification algorithm for MNL bandits with linear utilities and non-uniform revenues, and prove an instance-dependent sample complexity of $\tilde{\mathcal{O}}\big(\frac{d \log N}{\Delta^2}\big)$, where $d$ is the feature dimension, $N$ is the number of arms, and $\Delta$ is the minimum revenue gap.

When an online store or advertising platform shows a small set of options, it often observes only one response: which item the user chose, or that they chose nothing. Learning from this feedback is hard because the system must decide which groups of items to show, and the number of possible groups grows explosively with the catalog size. We study how to plan such experiments under a common choice model, where each item has features and users tend to choose items whose features match their preferences. Our method chooses groups of items that are especially informative, rather than trying groups one by one. To make this practical, we provide two computation strategies: one uses standard optimization software and gives a certificate of accuracy, while the other is faster and suited to very large catalogs. We then use this design to identify the best revenue-generating assortment while collecting as few user interactions as possible. Our analysis shows that the required number of samples depends mainly on the number of item features and on how hard it is to distinguish the best assortment from close competitors. This can help recommendation, advertising, and retail systems learn better assortments more efficiently.