stat.MLJan 31, 2025

The Revenue Cost of Inference in Online Assortment Optimization

Authors: Jierui Zuo, Hanzhang Qin

Organizations: Department of Management Science and Engineering, Tsinghua University, Beijing, China. · Department of Industrial Systems Engineering and Management, National University of Singapore, Singapore.

Abstract

A seller running an assortment experiment must earn revenue while collecting data to compare future offers. For a regular finite-dimensional parametric choice model and a finite assortment family, we characterize the oracle frontier between expected revenue loss and the largest local first-order variance constant across prespecified revenue comparisons. The oracle benchmark remains finite at zero cost exactly when revenue-maximizing assortments provide information in every target-gradient direction. When costly offers can supply the missing information, we derive the exact leading coefficient of the inverse-budget variance law and the limiting optimal spending shares. A pilot-based procedure reserves reference offers to preserve information and tightens the estimated budget constraint to account for uncertainty. We give conditions for the implemented design's variance criterion to converge to the stabilized oracle value at a fixed budget and reference share. Simulations with synthetic instances and Expedia-calibrated markets show that allocating offers across the full assortment family can improve the precision of revenue comparisons under a common opportunity-cost budget. Additional experiments assess pilot spending, budget protection, and sensitivity to choice-model misspecification.

Figures & tables

Explore similar work

Jan 28, 2023

Combinatorial Inference on the Optimal Assortment in Multinomial Logit Models

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.
Apr 20, 2026

Optimal Exploration of New Products under Assortment Decisions

We study online learning for new products on a platform that makes capacity-constrained assortment decisions on which products to offer. For a newly listed product, its quality is initially unknown, and quality information propagates through social learning: when a customer purchases a new product and leaves a review, its quality is revealed to both the platform and future customers. Since reviews require purchases, the platform must feature new products in the assortment ("explore") to generate reviews to learn about new products. Such exploration is costly because customer demand for new products is lower than for incumbent products. We characterize the optimal assortments for exploration to minimize regret, addressing two questions. (1) Should the platform offer a new product alone or alongside incumbent products? The former maximizes the purchase probability of the new product but yields lower short-term revenue. Despite the lower purchase probability, we show it is always optimal to pair the new product with the top incumbent products. (2) With multiple new products, should the platform explore them simultaneously or one at a time? We show that the optimal number of new products to explore simultaneously has a simple threshold structure: it increases with the "potential" of the new products and, surprisingly, does not depend on their individual purchase probabilities. We also show that two canonical bandit algorithms, UCB and Thompson Sampling, both fail in this setting for opposite reasons: UCB over-explores while Thompson Sampling under-explores. Our results provide structural insights on how platforms should learn about new products through assortment decisions.
May 25, 2026

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 KK items from a ground set of size NN 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 00-11 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 O~(dlog⁡NΔ2)\tilde{O}\big(\frac{d \log N}{Δ^2}\big), where dd is the feature dimension, NN is the number of arms, and ΔΔ is the minimum revenue gap.