Search papers, labs, and topics across Lattice.
This paper tackles the challenge of optimal experimental design for multinomial logit (MNL) bandits, which suffer from a combinatorial action space that renders traditional methods computationally infeasible. They introduce a computationally efficient framework based on reformulating the design oracle as a 0-1 mixed-integer linear program (MILP) and a fully polynomial-time lifted design. The authors leverage the Kiefer-Wolfowitz equivalence theorem to provide near G-optimality guarantees and apply their framework to best assortment identification, achieving an improved sample complexity bound.
MNL bandit optimization, previously plagued by computational bottlenecks, now has a scalable solution with provable optimality guarantees.
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.
