Adaptive Smooth Non-Stationary Bandits

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.