mlsanityData to 7 Oct 2026

MNL-Bandit in non-stationary environments

arXiv 2303.02504 ↗First posted 4 Mar 2023cs.LG cs.AI stat.MLcited by 1

Not on the map. Why?

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.

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

Builds on

21 of 42 references.

References · 21

  1. 2013Non-stationary Stochastic Optimizationcited by 173
  2. 2014A* Samplingcited by 150
  3. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  4. 2018Learning to Optimize under Non-Stationaritycited by 85
  5. 2019Weighted Linear Bandits for Non-Stationary Environmentscited by 84
  6. 2019A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-freecited by 71
  7. 2016Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradientcited by 65
  8. 2017Efficient Contextual Bandits in Non-stationary Worldscited by 62
  9. 2017Rotting Banditscited by 57
  10. 2021A Simple Approach for Non-stationary Linear Banditscited by 54
  11. 2017A Change-Detection based Framework for Piecewise-stationary Multi-Armed Bandit Problemcited by 48
  12. 2016An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial banditscited by 47
9 more
  1. 2017Thompson Sampling for the MNL-Banditcited by 35
  2. 2017Tracking the Best Expert in Non-stationary Stochastic Environmentscited by 35
  3. 2022A New Look at Dynamic Regret for Non-Stationary Stochastic Banditscited by 28
  4. 2021Tracking Most Significant Arm Switches in Banditscited by 27
  5. 2020Efficient Learning in Non-Stationary Linear Markov Decision Processescited by 26
  6. 2020Algorithms for Non-Stationary Generalized Linear Banditscited by 23
  7. 2020Combinatorial Semi-Bandit in the Non-Stationary Environmentcited by 17
  8. 2020Model-Free Non-Stationary RL: Near-Optimal Regret and Applications in Multi-Agent RL and Inventory Controlcited by 15
  9. 2017A Note on a Tight Lower Bound for MNL-Bandit Assortment Selection Modelscited by 7

Built on by

Cited by year

Citing papers per year: 2023: 1.

1 paper.

  1. 2023A Stability Principle for Learning under Non-Stationaritycited by 9