Learning in Position-Aware Multinomial Logit Bandits: From Multiplicative to General Position Effects

Xi Chen; Shibo Dai; Jiameng Lyu; Yuan Zhou

cs.LGMay 17, 2026

Learning in Position-Aware Multinomial Logit Bandits: From Multiplicative to General Position Effects

Authors: Xi Chen, Shibo Dai, Jiameng Lyu, Yuan Zhou

Organizations: Leonard N. Stern School of Business, New York University, New York, NY 10012, USA · Qiuzhen College, Tsinghua University, Beijing 100084, China · Department of Management Science, School of Management, Fudan University, Shanghai, 200433, China · May Yau Mathematical Sciences Center & Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China

Abstract

We study the dynamic joint assortment selection and positioning problem, where the attraction of each product depends on both its intrinsic appeal and its display position under a Multinomial Logit (MNL) choice framework. Our study ranges from the multiplicative position effects model, in which each product's attraction is scaled by a position-specific factor, to a general position effects model assigning independent attraction parameters to every product--position pair to capture heterogeneous synergies. For both models, we design round-based learning algorithms that update decisions after every single feedback, and establish the first regret-optimal characterization. Besides, our round-based algorithms provide the prompt operations needed by modern platforms. For the multiplicative model, we develop a cross-position pairwise maximum likelihood estimator with a clipping mechanism, and prove that our algorithm P2MLE-UCB attains a regret of $\tilde{O}(\sqrt{NT})$ , matching the lower bound and closing the $\sqrt{K}$ gap left by prior epoch-based analyses. For the general model, we establish a minimax lower bound and propose GP2-UCB with a matching upper bound. Moreover, we design an efficient subroutine for the per-round joint assortment and positioning optimization based on Dinkelbach's method and maximum-weight bipartite matching. Numerical experiments on synthetic data and the Expedia dataset show that our algorithms consistently outperform state-of-the-art benchmarks.

Explore similar work

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

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

Jun 9, 2026cs.LG

Data-Driven Dynamic Assortment in Online Platforms: Learning about Two Sides

We study a dynamic assortment problem on a two-sided service platform with incomplete information and heterogeneous customers in a discrete-time setting. In each period, a customer arrives seeking service, and the platform chooses an assortment of sellers to display. The customer then proposes a transaction to at most one seller in the assortment according to a multinomial logit choice model. After a fixed number of periods, sellers review the proposals they have received and each chooses at most one customer according to another multinomial logit choice model, after which the cycle repeats. A key challenge is that the platform does not know the choice-model parameters of either customers or sellers in advance. To our knowledge, this is the first study of a dynamic assortment problem in which both sides' choice parameters are unknown. We develop a data-driven algorithm that learns these parameters while optimizing the platform's objective over time. We evaluate performance using regret, which measures revenue loss relative to a clairvoyant benchmark that knows all parameters and customer arrivals in advance. We show that the algorithm's worst-case regret grows polylogarithmically over time, and we derive a matching lower bound, establishing its rate optimality.

Rahul Roy, Nur Sunar, Jayashankar M. Swaminathan

Linear Regret Semiparametric Framework Optimality

Ask PDF