# Non-Stationary Lipschitz Bandits

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

## 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 (most cited first, 29 of 29)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [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)
- [Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.4758/) (2014)
- [Bandit Convex Optimization in Non-stationary Environments](https://mlsanity.com/paper/1907.12340/) (2019)
- [Simple regret for infinitely many armed bandits](https://mlsanity.com/paper/1505.04627/) (2015)
- [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)
- [Bandits with many optimal arms](https://mlsanity.com/paper/2103.12452/) (2021)
- [An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledge](https://mlsanity.com/paper/2205.14775/) (2022)
- [Robust Lipschitz Bandits to Adversarial Corruptions](https://mlsanity.com/paper/2305.18543/) (2023)
- [Regret Bounds for Generalized Linear Bandits under Parameter Drift](https://mlsanity.com/paper/2103.05750/) (2021)
- [Smooth Non-Stationary Bandits](https://mlsanity.com/paper/2301.12366/) (2023)
- [On Adaptivity in Non-stationary Stochastic Optimization With Bandit Feedback](https://mlsanity.com/paper/2210.05584/) (2022)
- [Tracking Most Significant Shifts in Nonparametric Contextual Bandits](https://mlsanity.com/paper/2307.05341/) (2023)
- [ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Bandits](https://mlsanity.com/paper/2210.14322/) (2022)
- [Near-Optimal Algorithm for Non-Stationary Kernelized Bandits](https://mlsanity.com/paper/2410.16052/) (2024)
- [On Slowly-varying Non-stationary Bandits](https://mlsanity.com/paper/2110.12916/) (2021)
- [Adaptive Discretization against an Adversary: Lipschitz bandits, Dynamic Pricing, and Auction Tuning](https://mlsanity.com/paper/2006.12367/) (2020)
- [When Can We Track Significant Preference Shifts in Dueling Bandits?](https://mlsanity.com/paper/2302.06595/) (2023)
- [Is Prior-Free Black-Box Non-Stationary Reinforcement Learning Feasible?](https://mlsanity.com/paper/2410.13772/) (2024)
- [Lower Bounds for Time-Varying Kernelized Bandits](https://mlsanity.com/paper/2410.16692/) (2024)
- [Rotting Infinitely Many-armed Bandits](https://mlsanity.com/paper/2201.12975/) (2022)
- [Adaptive Smooth Non-Stationary Bandits](https://mlsanity.com/paper/2407.08654/) (2024)
- [Non-Stationary Dueling Bandits Under a Weighted Borda Criterion](https://mlsanity.com/paper/2403.12950/) (2024)
- [An Adaptive Approach for Infinitely Many-armed Bandits under Generalized Rotting Constraints](https://mlsanity.com/paper/2404.14202/) (2024)
- [Tracking Most Significant Shifts in Infinite-Armed Bandits](https://mlsanity.com/paper/2502.00108/) (2025)

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

- [Lipschitz Bandits with Stochastic Delayed Feedback](https://mlsanity.com/paper/2510.00309/) (2025)
- [Instance-dependent Stochastic Lipschitz bandit](https://mlsanity.com/paper/2605.29748/) (2026)
- [Lipschitz Bandits with Arbitrary Feedback Delays](https://mlsanity.com/paper/2608.15036/) (2026)

## 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.