On Slowly-varying Non-stationary Bandits

Understand

We consider minimisation of dynamic regret in non-stationary bandits with a slowly varying property.

• Namely, we assume that arms' rewards are stochastic and independent over time, but that the absolute difference between the expected rewards of any arm at any two consecutive time-steps is at most a drift limit $\delta > 0$.
• For this setting that has not received enough attention in the past, we give a new algorithm which extends naturally the well-known Successive Elimination algorithm to the non-stationary bandit setting.
• We establish the first instance-dependent regret upper bound for slowly varying non-stationary bandits.