mlsanityData to 14 Oct 2026

Non-Stationary Lipschitz Bandits

arXiv 2505.18871 ↗First posted 24 May 2025stat.ML cs.LGcited by 3

Not on the map. Why?

Abstract (arXiv)

We study the problem of non-stationary Lipschitz bandits, where the number of actions is infinite and the reward function, satisfying a Lipschitz assumption, can change arbitrarily over time. We design an algorithm that adaptively tracks the recently introduced notion of significant shifts, defined by large deviations of the cumulative reward function. To detect such reward changes, our algorithm leverages a hierarchical discretization of the action space. Without requiring any prior knowledge of the non-stationarity, our algorithm achieves a minimax-optimal dynamic regret bound of mathcalwidetildeO(tildeL1/3T2/3), where tildeL is the number of significant shifts and T the horizon. This result provides the first optimal guarantee in this setting.

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 29 of its 48 references that are in the map. First posted on arXiv 24 May 2025.

Builds on

29 of 48 references.

References · 29

  1. 2019Introduction to Multi-Armed Banditscited by 481
  2. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  3. 2019Weighted Linear Bandits for Non-Stationary Environmentscited by 86
  4. 2018Learning to Optimize under Non-Stationaritycited by 85
  5. 2019A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-freecited by 71
  6. 2014Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithmscited by 60
  7. 2019Bandit Convex Optimization in Non-stationary Environmentscited by 41
  8. 2015Simple regret for infinitely many armed banditscited by 39
  9. 2022A New Look at Dynamic Regret for Non-Stationary Stochastic Banditscited by 28
  10. 2021Tracking Most Significant Arm Switches in Banditscited by 27
  11. 2021Bandits with many optimal armscited by 17
  12. 2022An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledgecited by 17
17 more
  1. 2023Robust Lipschitz Bandits to Adversarial Corruptionscited by 15
  2. 2021Regret Bounds for Generalized Linear Bandits under Parameter Driftcited by 13
  3. 2023Smooth Non-Stationary Banditscited by 13
  4. 2022On Adaptivity in Non-stationary Stochastic Optimization With Bandit Feedbackcited by 11
  5. 2023Tracking Most Significant Shifts in Nonparametric Contextual Banditscited by 10
  6. 2022ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Banditscited by 8
  7. 2024Near-Optimal Algorithm for Non-Stationary Kernelized Banditscited by 8
  8. 2021On Slowly-varying Non-stationary Banditscited by 7
  9. 2020Adaptive Discretization against an Adversary: Lipschitz bandits, Dynamic Pricing, and Auction Tuningcited by 6
  10. 2023When Can We Track Significant Preference Shifts in Dueling Bandits?cited by 5
  11. 2024Is Prior-Free Black-Box Non-Stationary Reinforcement Learning Feasible?cited by 5
  12. 2024Lower Bounds for Time-Varying Kernelized Banditscited by 5
  13. 2022Rotting Infinitely Many-armed Banditscited by 4
  14. 2024Adaptive Smooth Non-Stationary Banditscited by 4
  15. 2024Non-Stationary Dueling Bandits Under a Weighted Borda Criterioncited by 2
  16. 2024An Adaptive Approach for Infinitely Many-armed Bandits under Generalized Rotting Constraintscited by 2
  17. 2025Tracking Most Significant Shifts in Infinite-Armed Banditscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 2.

3 papers.

  1. 2025Lipschitz Bandits with Stochastic Delayed Feedbackcited by 1
  2. 2026Instance-dependent Stochastic Lipschitz banditcited by 0
  3. 2026Lipschitz Bandits with Arbitrary Feedback Delayscited by 0