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

arXiv: https://arxiv.org/abs/2605.23351 · HTML: https://mlsanity.com/paper/2605.23351/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 65 references that are in the map.
- First posted on arXiv 22 May 2026.

## Builds on (most cited first, 7 of 7)

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [What Doubling Tricks Can and Can't Do for Multi-Armed Bandits](https://mlsanity.com/paper/1803.06971/) (2018)
- [Delay-Aware Multi-Agent Reinforcement Learning for Cooperative and Competitive Environments](https://mlsanity.com/paper/2005.05441/) (2020)
- [On the Limitations and Possibilities of Nash Regret Minimization in Zero-Sum Matrix Games under Noisy Feedback](https://mlsanity.com/paper/2306.13233/) (2023)
- [Optimism and Delays in Episodic Reinforcement Learning](https://mlsanity.com/paper/2111.07615/) (2021)
- [Best of Both Worlds: Regret Minimization versus Minimax Play](https://mlsanity.com/paper/2502.11673/) (2025)

## Abstract (arXiv)

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 widetildeO(√T+√D) together with widetildeO(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.