Smooth Non-Stationary Bandits

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.