Generalized non-stationary bandits

Abstract

In this paper, we study a non-stationary stochastic bandit problem, which generalizes the switching bandit problem. On top of the switching bandit problem (\textbf{Case a}), we are interested in three concrete examples: (\textbf{b}) the means of the arms are local polynomials, (\textbf{c}) the means of the arms are locally smooth, and (\textbf{d}) the gaps of the arms have a bounded number of inflexion points and where the highest arm mean cannot vary too much in a short range. These three settings are very different, but have in common the following: (i) the number of similarly-sized level sets of the logarithm of the gaps can be controlled, and (ii) the highest mean has a limited number of abrupt changes, and otherwise has limited variations. We propose a single algorithm in this general setting, that in particular solves in an efficient and unified way the four problems (a)-(d) mentioned.

References in corpus (6)

• On Upper-Confidence Bound Policies for Non-Stationary Bandit Problems
• What Doubling Tricks Can and Can't Do for Multi-Armed Bandits
• Nearly Optimal Adaptive Procedure with Change Detection for Piecewise-Stationary Bandit
• Unimodal Bandits: Regret Lower Bounds and Optimal Algorithms
• Rotting Bandits
• A single algorithm for both restless and rested rotting bandits