# Adaptive Smooth Non-Stationary Bandits

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 64 references that are in the map.
- First posted on arXiv 11 Jul 2024.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free](https://mlsanity.com/paper/1902.00980/) (2019)
- [Rotting Bandits](https://mlsanity.com/paper/1702.07274/) (2017)
- [Nearly Optimal Adaptive Procedure with Change Detection for Piecewise-Stationary Bandit](https://mlsanity.com/paper/1802.03692/) (2018)
- [A Change-Detection based Framework for Piecewise-stationary Multi-Armed Bandit Problem](https://mlsanity.com/paper/1711.03539/) (2017)
- [Optimal Exploration-Exploitation in a Multi-Armed-Bandit Problem with Non-stationary Rewards](https://mlsanity.com/paper/1405.3316/) (2014)
- [Contextual Bandits with Continuous Actions: Smoothing, Zooming, and Adapting](https://mlsanity.com/paper/1902.01520/) (2019)
- [Unimodal Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.5096/) (2014)
- [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)
- [Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes](https://mlsanity.com/paper/1909.02553/) (2019)
- [Transfer Learning for Contextual Multi-armed Bandits](https://mlsanity.com/paper/2211.12612/) (2022)
- [Nonparametric Stochastic Contextual Bandits](https://mlsanity.com/paper/1801.01750/) (2018)
- [The K-Nearest Neighbour UCB algorithm for multi-armed bandits with covariates](https://mlsanity.com/paper/1803.00316/) (2018)
- [An Adaptive Algorithm for Learning with Unknown Distribution Drift](https://mlsanity.com/paper/2305.02252/) (2023)
- [On Abruptly-Changing and Slowly-Varying Multiarmed Bandit Problems](https://mlsanity.com/paper/1802.08380/) (2018)
- [Randomized Allocation with Nonparametric Estimation for Contextual Multi-Armed Bandits with Delayed Rewards](https://mlsanity.com/paper/1902.00819/) (2019)
- [Smoothness-Adaptive Contextual Bandits](https://mlsanity.com/paper/1910.09714/) (2019)
- [Smooth Non-Stationary Bandits](https://mlsanity.com/paper/2301.12366/) (2023)
- [Statistical Learning under Nonstationary Mixing Processes](https://mlsanity.com/paper/1512.08064/) (2015)
- [Self-Tuning Bandits over Unknown Covariate-Shifts](https://mlsanity.com/paper/2007.08584/) (2020)
- [Tracking Most Significant Shifts in Nonparametric Contextual Bandits](https://mlsanity.com/paper/2307.05341/) (2023)
- [Generalized non-stationary bandits](https://mlsanity.com/paper/2102.00725/) (2021)
- [Distribution-dependent and Time-uniform Bounds for Piecewise i.i.d Bandits](https://mlsanity.com/paper/1905.13159/) (2019)
- [Finite-time Analysis of Globally Nonstationary Multi-Armed Bandits](https://mlsanity.com/paper/2107.11419/) (2021)
- [On Slowly-varying Non-stationary Bandits](https://mlsanity.com/paper/2110.12916/) (2021)
- [Adversarial Rewards in Universal Learning for Contextual Bandits](https://mlsanity.com/paper/2302.07186/) (2023)

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

- [Contextual Bandits for Unbounded Context Distributions](https://mlsanity.com/paper/2408.09655/) (2024)
- [Non-Stationary Lipschitz Bandits](https://mlsanity.com/paper/2505.18871/) (2025)
- [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)

## Abstract (arXiv)

We study a K-armed non-stationary bandit model where rewards change smoothly, as captured by H"older class assumptions on rewards as functions of time. Such smooth changes are parametrized by a H"older exponent β and coefficient λ. While various sub-cases of this general model have been studied in isolation, we first establish the minimax dynamic regret rate generally for all K,β,λ. Next, we show this optimal dynamic regret can be attained adaptively, without knowledge of β,λ. To contrast, even with parameter knowledge, upper bounds were only previously known for limited regimes β≤ 1 and β=2 (Slivkins, 2014; Krishnamurthy and Gopalan, 2021; Manegueu et al., 2021; Jia et al.,2023). Thus, our work resolves open questions raised by these disparate threads of the literature. We also study the problem of attaining faster gap-dependent regret rates in non-stationary bandits. While such rates are long known to be impossible in general (Garivier and Moulines, 2011), we show that environments admitting a safe arm (Suk and Kpotufe, 2022) allow for much faster rates than the worst-case scaling with √T. While previous works in this direction focused on attaining the usual logarithmic regret bounds, as summed over stationary periods, our new gap-dependent rates reveal new optimistic regimes of non-stationarity where even the logarithmic bounds are pessimistic. We show our new gap-dependent rate is tight and that its achievability (i.e., as made possible by a safe arm) has a surprisingly simple and clean characterization within the smooth H"older class model.