Optimal Design for Multinomial Logit Model with Applications to Best Assortment Identification
Abstract
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 Õ((d log N)/Δ2), where d is the feature dimension, N is the number of arms, and Δ is the minimum revenue gap.
Related
- Uncertainty Quantification Methods for Optimal Excitation Design in Parameter Identification
- Optimal Catastrophe Bond Design and its Applications to Climate Change Risk
- Optimal sampling density design for homotopic off-the-grid deconvolution
- Optimal Average Distortion for Non-Expansive Embeddings of Euclidean Metrics into the Line: With applications to cut-matching games and vertex expansion
- Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback
BibTeX
@misc{lee2026optimal,
title = {{Optimal Design for Multinomial Logit Model with Applications to Best Assortment Identification}},
author = {Joongkyu Lee and Min-hwan Oh},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2605.25592},
eprint = {2605.25592},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.25592},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - Optimal Design for Multinomial Logit Model with Applications to Best Assortment Identification
AU - Joongkyu Lee
AU - Min-hwan Oh
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2605.25592
UR - https://arxiv.org/abs/2605.25592
AB - 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 Õ((d log N)/Δ^2), where d is the feature dimension, N is the number of arms, and Δ is the minimum revenue gap.
ER -