Modular Detection-Augmented Bandit Procedures for Piecewise-Stationary Multi-Armed Bandits
A modular framework for tackling multi-armed bandits whose arm-reward distributions stay fixed between abrupt change-points. It decouples the design into any stationary bandit algorithm plus any sequential change detector satisfying stated properties, so a single regret analysis yields order-optimal dynamic regret across many detector-plus-bandit combinations under sub-Gaussian rewards. Forced exploration guarantees that shifts even in rarely-pulled arms are detected, and improved lower bounds characterize the achievable dynamic regret.
Detection Augmented Bandit Procedures for Piecewise Stationary MABs: A Modular Approach
Studies the multi-armed bandit problem in piecewise-stationary environments, where each arm's reward distribution stays fixed between abrupt change-points at which some arms shift. It develops a modu…