Time-Varying Stochastic Multi-Armed Bandit Problems

Abstract—In this paper, we consider a time-varying stochastic multi-armed bandit (MAB) problem where the unknown reward distribution of each arm can change arbitrarily over time. We obtain a lower bound on the regret order and demonstrate that an online learning algorithm achieves this lower bound. We further consider a piece-wise stationary model of the arm reward distri-butions and establish the regret performance of an online learning algorithm in terms of the number of change points experienced by the reward distributions over the time horizon. I