A New Algorithm for Nonstationary Contextual Bandits: Efficient, Optimal and Parameterfree
[edit]
Proceedings of the ThirtySecond Conference on Learning Theory, PMLR 99:696726, 2019.
Abstract
We propose the first contextual bandit algorithm that is parameterfree, efficient, and optimal in terms of dynamic regret. Specifically, our algorithm achieves $\mathcal{O}(\min\{\sqrt{KST}, K^{\frac{1}{3}}\Delta ^{\frac{1}{3}}T^{\frac{2}{3}}\})$ dynamic regret for a contextual bandit problem with $T$ rounds, $K$ actions, $S$ switches and $\Delta$ total variation in data distributions. Importantly, our algorithm is adaptive and does not need to know $S$ or $\Delta$ ahead of time, and can be implemented efficiently assuming access to an ERM oracle. Our results strictly improve the $\mathcal{O} (\min \{S^{\frac{1}{4}}T^{\frac{3}{4}}, \Delta^{\frac{1}{5}}T^{\frac{4}{5}}\})$ bound of (Luo et al., 2018), and greatly generalize and improve the $\mathcal{O}(\sqrt{ST})$ result of (Auer et al., 2018) that holds only for the twoarmed bandit problem without contextual information. The key novelty of our algorithm is to introduce {\it replay phases}, in which the algorithm acts according to its previous decisions for a certain amount of time in order to detect nonstationarity while maintaining a good balance between exploration and exploitation.
Related Material


