# MNL-Bandit in non-stationary environments

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 42 references that are in the map.
- First posted on arXiv 4 Mar 2023.

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

- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [A* Sampling](https://mlsanity.com/paper/1411.0030/) (2014)
- [Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach](https://mlsanity.com/paper/2102.05406/) (2021)
- [Weighted Linear Bandits for Non-Stationary Environments](https://mlsanity.com/paper/1909.09146/) (2019)
- [Learning to Optimize under Non-Stationarity](https://mlsanity.com/paper/1810.03024/) (2018)
- [A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free](https://mlsanity.com/paper/1902.00980/) (2019)
- [Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient](https://mlsanity.com/paper/1605.04638/) (2016)
- [Efficient Contextual Bandits in Non-stationary Worlds](https://mlsanity.com/paper/1708.01799/) (2017)
- [Rotting Bandits](https://mlsanity.com/paper/1702.07274/) (2017)
- [A Simple Approach for Non-stationary Linear Bandits](https://mlsanity.com/paper/2103.05324/) (2021)
- [A Change-Detection based Framework for Piecewise-stationary Multi-Armed Bandit Problem](https://mlsanity.com/paper/1711.03539/) (2017)
- [An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits](https://mlsanity.com/paper/1605.08722/) (2016)
- [Thompson Sampling for the MNL-Bandit](https://mlsanity.com/paper/1706.00977/) (2017)
- [Tracking the Best Expert in Non-stationary Stochastic Environments](https://mlsanity.com/paper/1712.00578/) (2017)
- [A New Look at Dynamic Regret for Non-Stationary Stochastic Bandits](https://mlsanity.com/paper/2201.06532/) (2022)
- [Tracking Most Significant Arm Switches in Bandits](https://mlsanity.com/paper/2112.13838/) (2021)
- [Efficient Learning in Non-Stationary Linear Markov Decision Processes](https://mlsanity.com/paper/2010.12870/) (2020)
- [Algorithms for Non-Stationary Generalized Linear Bandits](https://mlsanity.com/paper/2003.10113/) (2020)
- [Combinatorial Semi-Bandit in the Non-Stationary Environment](https://mlsanity.com/paper/2002.03580/) (2020)
- [Model-Free Non-Stationary RL: Near-Optimal Regret and Applications in Multi-Agent RL and Inventory Control](https://mlsanity.com/paper/2010.03161/) (2020)
- [A Note on a Tight Lower Bound for MNL-Bandit Assortment Selection Models](https://mlsanity.com/paper/1709.06109/) (2017)

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

- [A Stability Principle for Learning under Non-Stationarity](https://mlsanity.com/paper/2310.18304/) (2023)

## Abstract (arXiv)

In this paper, we study the MNL-Bandit problem in a non-stationary environment and present an algorithm with a worst-case expected regret of tildeOleft( min left √NTL;,; N^frac13(Delta∞K)^frac13 T^frac23 + √NTrightright). Here N is the number of arms, L is the number of changes and Delta∞K is a variation measure of the unknown parameters. Furthermore, we show matching lower bounds on the expected regret (up to logarithmic factors), implying that our algorithm is optimal. Our approach builds upon the epoch-based algorithm for stationary MNL-Bandit in Agrawal et al. 2016. However, non-stationarity poses several challenges and we introduce new techniques and ideas to address these. In particular, we give a tight characterization for the bias introduced in the estimators due to non stationarity and derive new concentration bounds.