Adaptive Regret for Bandits Made Possible: Two Queries Suffice
Zhou Lu Qiuyi Zhang Xinyi Chen Fred Zhang David Woodruff Elad Hazan
Fast changing states or volatile environments pose a significant challenge to
online optimization, which needs to perform rapid adaptation under limited
observation. In this paper, we give query and regret optimal bandit algorithms
under the strict notion of strongly adaptive regret, which measures the maximum
regret over any contiguous interval $I$. Due to its worst-case nature, there is
an almost-linear $\Omega(|I|^{1-\epsilon})$ regret lower bound, when only one
query per round is allowed [Daniely el al, ICML 2015]. Surprisingly, with just
two queries per round, we give Strongly Adaptive Bandit Learner (StABL) that
achieves $\tilde{O}(\sqrt{n|I|})$ adaptive regret for multi-armed bandits with
$n$ arms. The bound is tight and cannot be improved in general. Our algorithm
leverages a multiplicative update scheme of varying stepsizes and a carefully
chosen observation distribution to control the variance. Furthermore, we extend
our results and provide optimal algorithms in the bandit convex optimization
setting. Finally, we empirically demonstrate the superior performance of our
algorithms under volatile environments and for downstream tasks, such as
algorithm selection for hyperparameter optimization.