Research map / Bandits and online learning / Online convex optimization and games

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

NeurIPS 2026 · Bandits and online learning › Online convex optimization and games · approach: Best-of-both-worlds bandit algorithms · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes Prudent-Banker, a delay-robust OMD-based phased-aggression algorithm for adversarial bandits that achieves minimax-optimal regret with O~(1) regret against an exploratory safe baseline, both with and without delays.

Problem

Adversarial multi-armed bandits with arbitrary delayed feedback need minimax-optimal worst-case regret while keeping near-constant regret relative to a designated safe baseline policy; delays can mistime switches between conservatism and exploration.

Approach

Combines a delay-adapted OMD (Banker-OMD) with phased aggression, using a delay-calibrated restart threshold (slack scaling with sqrt(D)/delta) to avoid false suboptimality certificates from unobserved feedback, plus a doubling-stage hard restart for unknown total delay.

Key results

• Theorem gives pseudo-regret O~(sqrt(T)+sqrt(D)) with O(1+log D) comparator regret under the exploratory baseline assumption.
• Non-delayed corollary: regret O~(sqrt(delta^-1 T log A)) with O(1) safe-comparator regret, claimed to match the Omega(sqrt(T/delta)) lower bound up to logs.
• Experiments (synthetic, A=100, T=50000) show Prudent-Banker's gap to safe comparator stays bounded and repeatedly negative under geometric and Pareto delays.

Surprising findings

• Conservative-UCB appears slightly closer to the hindsight best arm only because its default arm is the best arm in the diagnostic setting, an advantage the authors say is not online.

Limitations

• Delay-side regret carries an extra sqrt(A) penalty relative to the unconstrained benchmark, inherited from Banker-OMD.
• Requires a full-support (exploratory) safe baseline with minimum mass delta; deterministic comparators are excluded.
• Experiments are limited to a single synthetic environment with an oracle comparator concentrated on the hindsight best arm.

Experimental setup

Datasets: synthetic non-stationary bandit environment (T=50000, A=100, 500 blocks)

Benchmarks: synthetic non-stationary bandit environment

Metrics: pseudo-regret comparator regret cumulative loss gap mixing coefficient alpha_t

Baselines: Conservative-UCB Safe-EXP3-IX

Builds on: Banker-OMD phased aggression (Muller et al.) Exp3 EXP3-IX

Closest papers by meaning

• Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback (NeurIPS 2025 · similarity 0.91)
• Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · similarity 0.91)
• Taming Heavy-Tailed Losses in Adversarial Bandits and the Best-of-Both-Worlds Setting (NeurIPS 2024 · similarity 0.89)
• Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints (NeurIPS 2024 · similarity 0.89)
• Near-Optimal Stochastic Linear Bandits with Delay (NeurIPS 2026 · similarity 0.89)
• Stochastic Bandits Robust to Adversarial Attacks (ICLR 2025 · similarity 0.88)