# Smooth Non-Stationary Bandits

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 45 references that are in the map.
- First posted on arXiv 29 Jan 2023.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Dynamic Regret of Convex and Smooth Functions](https://mlsanity.com/paper/2007.03479/) (2020)
- [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)
- [Efficient Contextual Bandits in Non-stationary Worlds](https://mlsanity.com/paper/1708.01799/) (2017)
- [A Sliding-Window Algorithm for Markov Decision Processes with Arbitrarily Changing Rewards and Transitions](https://mlsanity.com/paper/1805.10066/) (2018)
- [Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes](https://mlsanity.com/paper/1909.02553/) (2019)
- [Smoothness-Adaptive Contextual Bandits](https://mlsanity.com/paper/1910.09714/) (2019)
- [Regime Switching Bandits](https://mlsanity.com/paper/2001.09390/) (2020)
- [Generalized non-stationary bandits](https://mlsanity.com/paper/2102.00725/) (2021)
- [Multi-armed Bandit Requiring Monotone Arm Sequences](https://mlsanity.com/paper/2106.03790/) (2021)
- [Algorithmic Challenges in Ensuring Fairness at the Time of Decision](https://mlsanity.com/paper/2103.09287/) (2021)

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

- [A Stability Principle for Learning under Non-Stationarity](https://mlsanity.com/paper/2310.18304/) (2023)
- [A Definition of Non-Stationary Bandits](https://mlsanity.com/paper/2302.12202/) (2023)
- [Reinforcement Learning in the Real World: A Survey of Statistical Challenges and Future Directions](https://mlsanity.com/paper/2601.15353/) (2026)
- [Low-Rank MDPs with Continuous Action Spaces](https://mlsanity.com/paper/2311.03564/) (2023)
- [Adaptive Smooth Non-Stationary Bandits](https://mlsanity.com/paper/2407.08654/) (2024)
- [Non-Stationary Lipschitz Bandits](https://mlsanity.com/paper/2505.18871/) (2025)
- [Non-Stationary Dueling Bandits Under a Weighted Borda Criterion](https://mlsanity.com/paper/2403.12950/) (2024)
- [Tracking Most Significant Shifts in Infinite-Armed Bandits](https://mlsanity.com/paper/2502.00108/) (2025)
- [Constrained Feedback Learning for Non-Stationary Multi-Armed Bandits](https://mlsanity.com/paper/2509.15073/) (2025)
- [Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting](https://mlsanity.com/paper/2409.05980/) (2024)
- [Natural Policy Gradient for Average Reward Non-Stationary RL](https://mlsanity.com/paper/2504.16415/) (2025)
- [Quick-Draw Bandits: Quickly Optimizing in Nonstationary Environments with Extremely Many Arms](https://mlsanity.com/paper/2505.24692/) (2025)
- [Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent](https://mlsanity.com/paper/2605.25590/) (2026)

## Abstract (arXiv)

In many applications of online decision making, the environment is non-stationary and it is therefore crucial to use bandit algorithms that handle changes. Most existing approaches are designed to protect against non-smooth changes, constrained only by total variation or Lipschitzness over time. However, in practice, environments often change em smoothly, so such algorithms may incur higher-than-necessary regret. We study a non-stationary bandits problem where each arm's mean reward sequence can be embedded into a β-H"older function, i.e., a function that is (β-1)-times Lipschitz-continuously differentiable. The non-stationarity becomes more smooth as β increases. When β=1, this corresponds to the non-smooth regime, where citebesbes2014stochastic established a minimax regret of tilde Theta(T2/3). We show the first separation between the smooth (i.e., β≥ 2) and non-smooth (i.e., β=1) regimes by presenting a policy with tilde O(k4/5 T3/5) regret on any k-armed, 2-H"older instance. We complement this result by showing that the minimax regret on the β-H"older family of instances is Omega(T(β+1)/(2β+1)) for any integer β≥ 1. This matches our upper bound for β=2 up to logarithmic factors. Furthermore, we validated the effectiveness of our policy through a comprehensive numerical study using real-world click-through rate data.