# Multinomial Logit Bandit with Low Switching Cost

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jul 2020.

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

- [Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning](https://mlsanity.com/paper/2210.08238/) (2022)
- [Semantic Caching for Low-Cost LLM Serving: From Offline Learning to Online Adaptation](https://mlsanity.com/paper/2508.07675/) (2025)
- [UCB-based Algorithms for Multinomial Logistic Regression Bandits](https://mlsanity.com/paper/2103.11489/) (2021)
- [Towards Scalable and Robust Structured Bandits: A Meta-Learning Framework](https://mlsanity.com/paper/2202.13227/) (2022)
- [Online Convex Optimization with Continuous Switching Constraint](https://mlsanity.com/paper/2103.11370/) (2021)
- [Contextual Multinomial Logit Bandits with General Value Functions](https://mlsanity.com/paper/2402.08126/) (2024)
- [Enjoying Non-linearity in Multinomial Logistic Bandits: A Minimax-Optimal Algorithm](https://mlsanity.com/paper/2507.05306/) (2025)
- [Batched Thompson Sampling for Multi-Armed Bandits](https://mlsanity.com/paper/2108.06812/) (2021)
- [Encrypted Linear Contextual Bandit](https://mlsanity.com/paper/2103.09927/) (2021)
- [Oracle-Efficient Combinatorial Semi-Bandits](https://mlsanity.com/paper/2510.21431/) (2025)

## Abstract (arXiv)

We study multinomial logit bandit with limited adaptivity, where the algorithms change their exploration actions as infrequently as possible when achieving almost optimal minimax regret. We propose two measures of adaptivity: the assortment switching cost and the more fine-grained item switching cost. We present an anytime algorithm (AT-DUCB) with O(N log T) assortment switches, almost matching the lower bound Omega(fracN log T log log T). In the fixed-horizon setting, our algorithm FH-DUCB incurs O(N log log T) assortment switches, matching the asymptotic lower bound. We also present the ESUCB algorithm with item switching cost O(N log2 T).