DAL: A Practical Prior-Free Black-Box Framework for Piecewise Stationary Bandits

We introduce a practical, black-box framework termed Detection Augmented Learning (DAL) for the problem of piecewise stationary bandits without knowledge of the underlying non-stationarity. DAL accepts any stationary bandit algorithm with order-optimal regret as input and augments it with a change detector, enabling applicability to all common bandit variants. Extensive experimentation demonstrates that DAL consistently surpasses all state-of-the-art methods across diverse non-stationary scenarios, including synthetic benchmarks and real-world datasets, underscoring its versatility and scalability. We provide theoretical insights into DAL's strong empirical performance, complemented by thorough empirical validation.

Many machine learning systems make decisions by trying different options and learning which ones give the best results. For example, a system might learn which recommendation, advertisement, treatment, or hardware setting works best. But the real world changes: people's preferences shift, markets evolve, and conditions that were good yesterday may no longer be good today. Our work studies how to help these systems keep up with such changes. We introduce Detection Augmented Learning, or DAL, a method that adds a simple "change-checking" mechanism to existing learning algorithms. The algorithm mostly behaves as usual, but it occasionally collects information to see whether the environment has changed. When it finds convincing evidence of a change, it starts fresh so it can quickly learn what works in the new situation. We show that this idea works well across many different decision-making problems, including real-world datasets. We also prove that DAL can keep the strong mathematical guarantees of the algorithms it builds on. The main message is that learning systems do not always need to constantly adapt; sometimes, it is enough to reliably notice when the world has changed and restart learning at the right time.