# MNL-Bandit with Knapsacks: a near-optimal algorithm

arXiv: https://arxiv.org/abs/2106.01135 · HTML: https://mlsanity.com/paper/2106.01135/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 52 references that are in the map.
- First posted on arXiv 2 Jun 2021.

## Builds on (most cited first, 11 of 11)

- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Adversarial Bandits with Knapsacks](https://mlsanity.com/paper/1811.11881/) (2018)
- [Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2002.10421/) (2020)
- [MNL-Bandit: A Dynamic Learning Approach to Assortment Selection](https://mlsanity.com/paper/1706.03880/) (2017)
- [Thompson Sampling for the MNL-Bandit](https://mlsanity.com/paper/1706.00977/) (2017)
- [Thompson Sampling for Budgeted Multi-armed Bandits](https://mlsanity.com/paper/1505.00146/) (2015)
- [Combinatorial Semi-Bandits with Knapsacks](https://mlsanity.com/paper/1705.08110/) (2017)
- [Inventory Balancing with Online Learning](https://mlsanity.com/paper/1810.05640/) (2018)
- [Assortment Optimization under Unknown MultiNomial Logit Choice Models](https://mlsanity.com/paper/1704.00108/) (2017)
- [Multi-stage and Multi-customer Assortment Optimization with Inventory Constraints](https://mlsanity.com/paper/1908.09808/) (2019)
- [Online Resource Allocation with Customer Choice](https://mlsanity.com/paper/1511.01837/) (2015)

## Built on by (most cited first, 2 of 2)

- [Learning an Optimal Assortment Policy under Observational Data](https://mlsanity.com/paper/2502.06777/) (2025)
- [MNL-Bandits under Inventory and Limited Switches Constraints](https://mlsanity.com/paper/2204.10787/) (2022)

## Abstract (arXiv)

We consider a dynamic assortment selection problem where a seller has a fixed inventory of N substitutable products and faces an unknown demand that arrives sequentially over T periods. In each period, the seller needs to decide on the assortment of products (satisfying certain constraints) to offer to the customers. The customer's response follows an unknown multinomial logit model (MNL) with parameter boldsymbolv. If customer selects product i ∈ [N], the seller receives revenue ri. The goal of the seller is to maximize the total expected revenue from the T customers given the fixed initial inventory of N products. We present MNLwK-UCB, a UCB-based algorithm and characterize its regret under different regimes of inventory size. We show that when the inventory size grows quasi-linearly in time, MNLwK-UCB achieves a tildeO(N + √NT) regret bound. We also show that for a smaller inventory (with growth ~ Tα, α < 1), MNLwK-UCB achieves a tildeO(N(1 + T^frac1 - α2) + √NT). In particular, over a long time horizon T, the rate tildeO(√NT) is always achieved regardless of the constraints and the size of the inventory.