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

• URL: http://arxiv.org/abs/2605.25592v1
• Date: Mon, 25 May 2026 08:41:56 GMT
• Title: Optimal Design for Multinomial Logit Model with Applications to Best Assortment Identification
• Abstract summary: We study optimal experimental design for multinomial logit (MNL) bandits.<n>Unlike linear or generalized linear bandits, MNL bandits have a nonlinear action space.<n>We develop a best identification algorithm for MNL bandits.
• Score: 39.805192541498634
• License: http://creativecommons.org/licenses/by-sa/4.0/
• 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 $\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.

Related papers

• Diversified Multinomial Logit Contextual Bandits [34.403840521131606]
  Existing contextual multinomial logit (MNL) bandits model relevance-driven choice but ignore the potential benefits of within-assortment diversity.<n>We bridge this gap with the $textitdiversified multinomial logit$ (DMNL) contextual bandit.<n>We show that $textttOFU-DMNL$ achieves at least a $(frac1e+1)$-$textitapproximate$ regret bound $tildeOleft(d sqrtT/K
  arXiv  Detail & Related papers  (2026-07-13T15:21:30Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Tensor Network Generator-Enhanced Optimization for Traveling Salesman Problem [12.04919729571293]
  We present an application of the tensor network generator-enhanced optimization (TN-GEO) framework to the traveling salesman problem (TSP)<n>Our approach employs a tensor network Born machine based on automatically differentiable matrix product states (MPS) as the generative model.<n>$k$-site variants, which put more focus on local correlations, show better results compared to the full-MPS case.
  arXiv  Detail & Related papers  (2026-02-12T21:18:19Z)
• Tractable Multinomial Logit Contextual Bandits with Non-Linear Utilities [34.403840521131606]
  We study the multinomial logit (MNL) contextual bandit problem for sequential assortment selection.<n>Our proposed method is the first computationally tractable algorithm for MNL contextual bandits with non-linear utilities.
  arXiv  Detail & Related papers  (2026-01-11T13:43:42Z)
• Scalable Neural Incentive Design with Parameterized Mean-Field Approximation [28.20524168049273]
  We show that when dynamics and rewards are Lipschitz, the finite-$N$ ID objective is approximated by the PMFG at rate $mathscrO(frac1sqrtN)$.<n>We further introduce our Adjoint Mean-Field Incentive Design (AMID) algorithm, which uses explicit differentiation of iterated equilibrium operators to compute gradients efficiently.
  arXiv  Detail & Related papers  (2025-10-24T13:18:54Z)
• Best-of-$\infty$ -- Asymptotic Performance of Test-Time Compute [10.167365483866663]
  We study best-of-$N$ for large language models (LLMs) where the selection is based on majority voting.<n>We propose an adaptive generation scheme that selects $N$ based on answer agreement.<n>We extend the framework to weighted ensembles of multiple LLMs, showing that such mixtures can outperform any individual model.
  arXiv  Detail & Related papers  (2025-09-25T12:41:05Z)
• Achieving PAC Guarantees in Mechanism Design through Multi-Armed Bandits [8.013444110633223]
  We analytically derive a class of optimal solutions to a linear program (LP) for automated mechanism design.<n>These solutions can be expressed using a set of essential variables whose cardinality is exponentially smaller than the total number of variables in the original formulation.<n>We address this by translating the evaluation of this term into a multi-armed bandit (MAB) problem.
  arXiv  Detail & Related papers  (2024-11-30T03:59:36Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  Single-Index Models are high-dimensional regression problems with planted structure. We show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $Omega(dkstar/2)$ samples.
  arXiv  Detail & Related papers  (2024-03-08T18:50:19Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  We propose a novelgreedy bandit (SGB) algorithm for multi-armed bandit problems when no extra information other than the joint reward of the selected set of $n$ arms at each time $tin [T]$ is observed. SGB adopts an optimized-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms.
  arXiv  Detail & Related papers  (2023-12-13T11:08:25Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model. The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
  arXiv  Detail & Related papers  (2022-08-11T04:12:50Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  We show that model-based MARL achieves a sample complexity of $tilde O(|S||B|(gamma)-3epsilon-2)$ for finding the Nash equilibrium (NE) value up to some $epsilon$ error. We also show that such a sample bound is minimax-optimal (up to logarithmic factors) if the algorithm is reward-agnostic, where the algorithm queries state transition samples without reward knowledge.
  arXiv  Detail & Related papers  (2020-07-15T03:25:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.