Combinatorial Inference on the Optimal Assortment in Multinomial Logit Models

Shuting Shen; Xi Chen; Ethan X. Fang; Junwei Lu

stat.MLJan 28, 2023

Combinatorial Inference on the Optimal Assortment in Multinomial Logit Models

Authors: Shuting Shen, Xi Chen, Ethan X. Fang, Junwei Lu

Abstract

Assortment optimization has received active explorations in the past few decades due to its practical importance. Despite the extensive literature dealing with optimization algorithms and latent score estimation, uncertainty quantification for the optimal assortment still needs to be explored and is of great practical significance. Instead of estimating and recovering the complete optimal offer set, decision-makers may only be interested in testing whether a given property holds true for the optimal assortment, such as whether they should include several products of interest in the optimal set, or how many categories of products the optimal set should include. This paper proposes a novel inferential framework for testing such properties. We consider the widely adopted multinomial logit (MNL) model, where we assume that each customer will purchase an item within the offered products with a probability proportional to the underlying preference score associated with the product. We reduce inferring a general optimal assortment property to quantifying the uncertainty associated with the sign change point detection of the marginal revenue gaps. We show the asymptotic normality of the marginal revenue gap estimator, and construct a maximum statistic via the gap estimators to detect the sign change point. By approximating the distribution of the maximum statistic with multiplier bootstrap techniques, we propose a valid testing procedure. We also conduct numerical experiments to assess the performance of our method.

Explore similar work

May 25, 2026stat.ML

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{O}\big(\frac{d \log N}{Δ^2}\big)

, where

d

is the feature dimension,

N

is the number of arms, and

Δ

is the minimum revenue gap.

Joongkyu Lee, Min-hwan Oh

Generalized Linear Bandit Bayesian Experimental Design Optimal Design Semiparametric Framework Feedback Learning

Ask PDF

Jul 13, 2026stat.ML

Diversified Multinomial Logit Contextual Bandits

Existing contextual multinomial logit (MNL) bandits model relevance-driven choice but ignore the potential benefits of within-assortment diversity, while submodular/combinatorial bandits encode diversity in rewards but lack structured choice probabilities. We bridge this gap with the

\textit{diversified multinomial logit}

(DMNL) contextual bandit, which augments MNL choice probabilities with a generally submodular diversity function, thereby formalizing the relevance--diversity trade-off within a single model. Incorporating diversity renders exact MNL assortment optimization intractable. We propose a

\textit{white-box}

UCB-based algorithm,

\texttt{OFU-DMNL}

, that constructs assortments item-wise by maximizing optimistic marginal gains, avoids black-box optimization oracles. We show that

\texttt{OFU-DMNL}

achieves at least a

(1-\frac{1}{e+1})

\textit{approximate}

regret bound

\tilde{O}\left(d \sqrt{T/K}\right)

, where

d

is the context dimension,

K

the maximum assortment size, and

T

the horizon, and attains an improved approximation factor over standard submodular baselines. Experiments demonstrate consistent gains and, relative to exhaustive enumeration, comparable regret with substantially lower runtime. Overall, DMNL bandits provide a practical foundation for diversity-aware assortment optimization under uncertainty, and

\texttt{OFU-DMNL}

offers a statistically and computationally efficient solution.

Heesang Ann, Taehyun Hwang, Min-hwan Oh

Generalized Linear Bandit Bandits Semiparametric Framework

Ask PDF

Jul 10, 2026cs.LG

Estimation, Prediction, and Assortment Optimization for Markov Chain Choice Models with Panel Data

We propose a framework for the Markov chain (MC) choice model with panel data, including parameter estimation, personalized choice prediction, and personalized assortment optimization. In contrast to the traditional setting, which assumes that each transaction is independently drawn from a random utility model, our framework accounts for dependencies among transactions for the same customer in historical data, captured by partial-ordering preference information. To the best of our knowledge, our framework initiates the study of choice modeling with panel data under MC. As our primary result, we propose novel expectation-maximization (EM) algorithms for MC parameter estimation by incorporating partial-ordering-based customer preference information. On synthetic datasets and the sushi dataset, our EM algorithms outperform the traditional EM algorithm of Simsek and Topaloglu (Operations Research, 66, 2018) and multinomial-logit-based partial-order benchmarks adapted from Jagabathula and Vulcano (Management Science, 64, 2018). As our secondary contribution, we present hardness and computational results for conditional choice prediction and assortment optimization problems. These results complement our estimation framework and clarify the computational landscape of conditional choice and assortment optimization, which may be of independent interest.

Yalcin Akcay, Gerardo Berbeglia, Young-San Lin

Discrete Choice Models Semiparametric Framework Demand Forecasting Markov

Ask PDF