Reproduce “Prudent-Banker: No Extra Fees for Baseline Safety in Adversarial Bandits With and Without Delays” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Ting Hu, Luanda Cai, Emmanouil-Vasileios Vlatakis-Gkaragkounis
The PRUDENT-BANKER algorithm tackles adversarial multi-armed bandits with arbitrary feedback delays, providing worst-case regret bounds of O(sqrt(T) + sqrt(D)) against the optimal arm while simultaneously ensuring O(1) regret relative to a pre-defined safe baseline. This dual objective is met through a novel delay-calibrated phase transition mechanism that accounts for unobserved feedback.
Key insights
- It is possible to simultaneously achieve minimax-optimal worst-case regret and nearly constant regret against an exploratory safe baseline even under arbitrary feedback delays, providing the first affirmative resolution to the SOLID problem.
- The inherent information deficit from delayed feedback can be managed by augmenting restart conditions with a delay-dependent slack term, enabling accurate certification of baseline suboptimality.
- The component of adversarial regret proportional to sqrt(delta^{-1}D) is a fundamental "price of safety" in delayed bandit settings, as confirmed by theoretical lower bounds.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.