Detection Augmented Learning In Non-Stationary Bandit Environments
Abstract
We study the problem of non-stationary bandits without knowledge of the environmental changes. We propose Detection Augmented Learning (DAL) a black-box paradigm that comprises three modular components: a bandit algorithm, a change detector, and a forced exploration schedule. This modular design enables its applicability across a broad spectrum of bandit problems, from classical to highly structured settings. First, we provide theoretical insights into DAL's strong empirical performance: a single regret bound shows that DAL transfers the regret of its stationary input to the piecewise stationary setting, attaining or improving the best known bounds in every setting considered. We further identify conditions under which DAL performs well in drifting environments. Then, we showcase DAL's practical performance and versatility through extensive experimentation in which DAL consistently surpasses all state-of-the-art methods, both prior-free and prior-based, across diverse non-stationary scenarios in nine bandit settings. Finally, we investigate the effectiveness of the forced exploration and show that a bandit-driven strategy improves performance and shortens detection delay.
Related
- Domains of Attraction for Quasi-Stationary Distributions of Branching Processes in Random Environments
- Decentralized Bandit Learning of Markov Perfect Equilibria
- Scaling Bayesian Bandit Encoding with Shared Learning
- PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting
- Bandit Learning in General Open Multi-agent Systems
BibTeX
@misc{gerogiannis2026detection,
title = {{Detection Augmented Learning In Non-Stationary Bandit Environments}},
author = {Argyrios Gerogiannis and Yu-Han Huang and Subhonmesh Bose and Venugopal V. Veeravalli},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.25782},
eprint = {2610.25782},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.25782},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Detection Augmented Learning In Non-Stationary Bandit Environments
AU - Argyrios Gerogiannis
AU - Yu-Han Huang
AU - Subhonmesh Bose
AU - Venugopal V. Veeravalli
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.25782
UR - https://arxiv.org/abs/2610.25782
AB - We study the problem of non-stationary bandits without knowledge of the environmental changes. We propose Detection Augmented Learning (DAL) a black-box paradigm that comprises three modular components: a bandit algorithm, a change detector, and a forced exploration schedule. This modular design enables its applicability across a broad spectrum of bandit problems, from classical to highly structured settings. First, we provide theoretical insights into DAL's strong empirical performance: a single regret bound shows that DAL transfers the regret of its stationary input to the piecewise stationary setting, attaining or improving the best known bounds in every setting considered. We further identify conditions under which DAL performs well in drifting environments. Then, we showcase DAL's practical performance and versatility through extensive experimentation in which DAL consistently surpasses all state-of-the-art methods, both prior-free and prior-based, across diverse non-stationary scenarios in nine bandit settings. Finally, we investigate the effectiveness of the forced exploration and show that a bandit-driven strategy improves performance and shortens detection delay.
ER -