Most bandit algorithms assume a stable environment, but real-world recommendation and pricing problems drift. In a new arXiv paper, Gerogiannis et al. propose Detection Augmented Learning (DAL), a black-box wrapper that adds two components—a change detector and a forced exploration schedule—to any existing bandit algorithm. Because the components are modular, DAL can be applied to classical and highly structured bandit problems alike.
The paper's main theoretical result is a single regret bound that transfers the stationary regret of the input algorithm to piecewise-stationary environments. In every setting considered, this bound attains or improves the best known bounds. The authors also identify conditions under which DAL remains effective in drifting, non-piecewise environments.
Experiments across nine bandit settings show DAL consistently outperforming state-of-the-art methods, including both prior-free and prior-based approaches. The authors further find that making the forced exploration schedule bandit-driven—rather than fixed—improves performance and shortens detection delay.