Optimal Design for Multinomial Logit Model with Applications to Best Assortment Identification
Joongkyu Lee, Min-hwan Oh · 2026
Read Optimal Design for Multinomial Logit Model with Applications to Best Assortment Identification by Joongkyu Lee, Min-hwan Oh (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-25592.txt.
Introduction
Lee and Oh study optimal design for multinomial logit bandits, where an agent picks a subset of items and observes a choice. The combinatorial action space makes design and subset optimization intractable. One is a design oracle written as a zero-one mixed-integer linear program with solver-certified early stopping. The other is a polynomial-time lifted design built on a tractable surrogate. They prove near G-optimality guarantees with the Kiefer-Wolfowitz equivalence theorem, and their best-assortment method carries a sample complexity bound.
Catalog record
| CREATOR | Joongkyu Lee, Min-hwan Oh |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 139260 |
| LICENSE | http://creativecommons.org/licenses/by-sa/4.0/ |
| RIGHTS | CC BY SA |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.25592
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Optimal Design for Multinomial Logit Model with Applications to Best Assortment Identification Joongkyu Lee, Min-hwan Oh Abstract We study optimal experimental design for multinomial logit (MNL) bandits, where an agent repeatedly selects a subset of K K items from a ground set of size N 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 0 – 1 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 𝒪 ~ ( d log N Δ 2 ) \tilde{\mathcal{O}}\big(\frac{d\log N}{\Delta^{2}}\big) , where d d is the feature dimension, N N is the number of arms, and Δ \Delta is the minimum revenue gap. 1 Introduction We study optimal experimental design in multinomial logit (MNL) models ( 32 ) with linear utilities. The MNL model is a fundamental discrete choice model widely used in economics, marketing, and machine learning, where outcomes are generated from subset-dependent multinomial distributions parameterized by latent utilities. For instance, in online advertising, a user selects (e.g., clicks) one item from a subset of K ads presented on a page. Each ad can be represented by high-dimensional features, such as image or text embeddings produced by an off-the-shelf neural network. This structured feedback setting naturally arises in large-scale applications, where the total number of available items N can be very large. From an experimental design perspective, this setting poses significant challenges. Unlike linear or generalized linear models—where the design space consists of individual arms— the design space in MNL models is combinatorial : each experiment corresponds to selecting a subset of arms, and the number of feasible experiments grows on the order of N^{K} . Moreover, even for a fixed subset, the information induced by the MNL model is fundamentally different from that in linear or generalized linear models. In particular, the Fisher information is matrix-valued, depends nonlinearly on the underlying parameter, and is determined by the entire subset through MNL choice probabilities, rather than decomposing additively across individual arms. As a result, classical optimal design theory ( 25 ; 39 ) —which relies on additive, per-arm information contributions—does not directly apply. In this paper, we develop an optimal design framework for MNL models with combinatorial experiments that addresses the structural and computational challenges described above. Our approach builds on locally optimal design principles to handle the inherent nonlinearity of the MNL model, and leads to a Frank–Wolfe algorithm ( 16 ; 11 ) whose main computational challenge is a linear maximization oracle (LMO) over a combinatorial collection of feasible subsets. To address this bottleneck, we propose two complementary approaches: (i) an exact 0 – 1 mixed-integer linear program (MILP) reformulation of the LMO, allowing early stopping with guaranteed accuracy up to a user-specified tolerance, and (ii) a polynomial-time relaxation based on a Schur-complement lifting of the MNL Fisher information with a bounded approximation error. As an application of our efficient optimal design framework, we study best assortment identification in MNL bandits with linear utilities. In this fixed-confidence setting, an agent sequentially offers assortments (i.e., subsets of arms) and observes a single MNL choice outcome, with the goal of identifying the unique revenue-maximizing assortment S^{\star} with high probability while minimizing the total number of interactions. Leveraging a G -optimal design computed at a nominal parameter, we propose an algorithm, BSI-MNL , that combines an initial exploration phase (which ensures the nominal parameter is uniformly close to the true parameter), design-based sampling, and a principled stopping rule. We prove an instance-dependent sample complexity bound of \widetilde{\mathcal{O}}\!\left(d\log(N/\delta)\big(\Delta_{\min}^{-2}+(\kappa\Delta_{\min})^{-1}\big)\right) , which in the small-gap regime simplifies to the leading-order guarantee \widetilde{\mathcal{O}}\!\big(\frac{d\log N}{\Delta_{\min}^{2}}\big) . To the best of our knowledge, this yields the first sample complexity guarantee for best assortment identification in MNL bandits with linear utilities, while remaining computationally efficient via either MILP-based early stopping or the polynomial-time lifted relaxation. Our main contributions are summarized as follows: • Exact MILP reformulation: To address the primary computational bottleneck of the Frank–Wolfe (FW) algorithm—the linear maximization oracle (LMO) defined in ( 3 )—we show that the optimization problem admits an exact reformulation as a 0 – 1 mixed-integer linear program (Theorem 3.3 ). This reformulation allows the LMO to be solved using off-the-shelf MILP solvers, which either return an exact solution or terminate early with a user-specified, solver-certified optimality gap. Moreover, we show that the FW algorithm retains its \epsilon -optimality guarantee even with certified inexact LMO solutions, at the cost of a small additional number of FW iterations (Proposition 3.4 ). • Polynomial-time lifted surrogate: As an alternative approach, we propose a novel lifted surrogate based on a Schur-complement construction. This relaxation yields a ratio-of-sums objective that can be optimized exactly in polynomial time. The resulting design trades statistical efficiency for computational scalability, while incurring only a bounded and explicitly characterized approximation error (Theorem 3.5 ). • Best assortment identification in MNL bandits: Leveraging the optimal design, we propose BSI-MNL for best assortment identification in MNL bandits, and establish an instance-dependent sample complexity of \tilde{\mathcal{O}}\!\big(\frac{d\log N}{\Delta_{\min}^{2}}\big) , where d is the feature dimension, N is the number of arms, and \Delta_{\min} is the minimum revenue gap (Theorem 4.4 ). To the best of our knowledge, this is the first sample complexity guarantee for best assortment identification in MNL bandits with linear utilities and non-uniform revenue parameters. Moreover, the algorithm remains computationally efficient, either via MILP-based early stopping with certified gaps or via a fully polynomial-time lifted relaxation. 2 Related Work MNL model in Bandits. The MNL feedback model has been extensively studied in the bandit literature ( 5 ; 4 ; 37 ; 7 ; 35 ; 36 ; 38 ; 3 ; 28 ) . Compared to linear, generalized linear, and logistic bandits ( 1 ; 12 ; 2 ; 13 ; 30 ) , MNL bandits present additional challenges due to their combinatorial action space and non-uniform revenue parameters. Most prior work primarily focuses on regret minimization ( 7 ; 35 ; 36 ; 38 ; 28 ; 29 ) . Although a limited number of studies address best-arm or best-assortment identification ( 40 ; 41 ; 46 ; 24 ) , they are largely restricted to context-free MNL settings. Consequently, best assortment identification in MNL bandits with linear utilities remains underexplored. Pure Exploration in Linear Bandits. The pure exploration problem has been extensively investigated in linear bandits ( 42 ; 10 ; 31 ; 22 ; 14 ; 26 ; 47 ) . In this line of work, G-optimal design plays a central role in achieving near-optimal sample complexity. These approaches aim to identify