Algorithm adapts to unknown switches in adversarial bandit problems
Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary
Machine Learning
Summary
This work addresses how to choose the best options over time when the best choice can change occasionally, but the number of changes is unknown. Previous approaches required knowing how many times the best option changes or only worked under certain conditions. The authors developed a single algorithm that automatically adapts to any number of changes without prior knowledge, performing nearly as well as if that number were known. Their method cleverly uses a combination of strategies and gradually adjusts based on observed improvements.
What this means in practice
- •For online advertising platforms: Optimize ad selection strategies when user preferences shift unpredictably without knowing how often those shifts occur.
- •For network schedulers: Adapt resource allocation dynamically to fluctuating traffic patterns when the timing and frequency of changes are unknown.
Authors
Mengxiao Zhang
Abstract
We study switching regret in adversarial multi-armed bandits, where the learner competes with an arm sequence that changes at most $S$ times. When $S$ is known, an optimal expected regret of $\widetilde{\mathcal{O}}(\sqrt{(S+1)KT})$ is obtainable [Auer et al., 2002]. However, when $S$ is unknown, Marinov and Zimmert [2021] show that this guarantee is impossible under an adaptive adversary. In this paper, we show that a single algorithm achieves $\widetilde{\mathcal{O}}(\sqrt{(S+1)KT})$ expected regret for every $S$ against an oblivious adversary, resolving an open problem of Auer et al. [2019b]. Our algorithm combines a fixed-share learner initialized with a small learning rate and dyadic-interval subroutines that search for local improvements using randomized learning rates and implicit exploration. Importantly, a non-uniform prior favors following the main learner, keeping the cost of maintaining many subroutines small. When the subroutines accumulate sufficient improvement over the main learner, its learning rate doubles, allowing adaptation to the unknown number of comparator switches $S$.