Prudent-Banker: No Extra Fees for Baseline Safety in Adversarial Bandits With and Without Delays

We study adversarial multi-armed bandits with and without delayed feedback under a **safety-aware** goal: achieving minimax-optimal worst-case regret while keeping nearly **constant** regret relative to a designated "safe" baseline policy. Existing approaches can balance this trade-off with immediate feedback for smooth comparators, but arbitrary delays can mistime transitions between **conservatism** and **exploration**, endangering the safety guarantee. To bridge this gap, we propose PRUDENT-BANKER, a novel algorithm that combines a delay-adapted variant of Online Mirror Descent with a modified phased-aggression mechanism. Its key technical contribution is a delay-calibrated restart threshold that rigorously accounts for the worst-case distortion induced by unobserved feedback and reliably detects comparator suboptimality. We also establish new lower bounds for safety-constrained adversarial delayed bandits, showing that the regret guarantees of PRUDENT-BANKER are unimprovable, up to logarithmic factors, under the baseline-safety requirement. To the best of our knowledge, PRUDENT-BANKER is the first algorithm to achieve the optimal safety–robustness trade-off: pseudo-regret $\tilde{O}(\sqrt{T}+\sqrt{D})$ together with $\tilde{O}(1)$ regret against the safe comparator, both with and without delays. Experiments across diverse delay distributions show that, unlike standard delay-robust baselines, PRUDENT-BANKER effectively balances safety and learning.