🤖 machine learning

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

This paper introduces Prudent-Banker, a novel algorithm for adversarial multi-armed bandits with and without delayed feedback that achieves minimax-optimal worst-case regret while maintaining nearly constant regret against a safe baseline policy through a delay-calibrated restart mechanism and matching lower bounds.

Original authors: Ting Hu, Luanda Cai, Emmanouil-Vasileios Vlatakis-Gkaragkounis

Published 2026-05-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ting Hu, Luanda Cai, Emmanouil-Vasileios Vlatakis-Gkaragkounis

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the captain of a ship navigating through a foggy, stormy sea. You have two goals:

Survival: You must never crash into a hidden reef (a "safe" baseline policy you trust).
Speed: You want to reach the treasure island as fast as possible by exploring new routes, even if they look risky.

The problem? The fog is thick, and your radar is broken. When you steer the ship, you don't know if you hit a rock until hours later. This is the world of "delayed feedback."

This paper introduces a new captain named Prudent-Banker who solves this dilemma. Here is how it works, using simple analogies.

The Problem: The "Hidden Debt" Trap

In the past, if you wanted to be safe, you had to stick to the known safe route. If you wanted to be fast, you had to explore. But with delayed feedback, a dangerous trap exists:

Imagine you steer toward a risky shortcut. You don't know it's a dead end yet because the radar is slow. So, you keep steering toward it, thinking it's fine. By the time the radar finally screams "CRASH!", you have already sailed 100 miles into a swamp. You have accumulated a "hidden debt" of bad decisions that you didn't know about.

Old algorithms would either:

Be too scared: Stay on the safe route forever and miss the treasure.
Be too reckless: Keep exploring until the hidden debt becomes so huge that the ship sinks.

The Solution: Prudent-Banker

The authors created Prudent-Banker, a smart algorithm that acts like a cautious but ambitious captain. It uses two main tools to manage the fog:

1. The "Banker" (Managing the Ledger)

Think of the algorithm as a bank. Every time you make a decision, you borrow "learning credit" from the future.

Because feedback is delayed, the bank knows it can't spend all its credit right now. It holds back some "credits" (updates) until the feedback actually arrives.
This ensures that even if the ship is sailing blind for a while, the captain isn't making wild guesses based on old, stale maps. It keeps the "worst-case" speed (regret) optimal, even with the fog.

2. The "Phased Aggression" (The Safety Switch)

This is the clever part. The captain doesn't just flip a switch from "Safe" to "Risky." Instead, they use a staged approach:

Phase 1 (The Guard): You sail mostly on the safe route, but you take tiny, tiny steps off the path to peek around.
The "Restart" Check: The captain constantly asks, "Is the safe route actually the best one?"
- The Twist: Because of the fog (delays), the captain might think the safe route is bad when it's actually fine, or vice versa. The data is incomplete.
- The Fix: Prudent-Banker adds a "Safety Buffer" to its check. It says, "I won't switch to full speed until I am extra sure the safe route is bad, accounting for the fact that I might be missing some radar data."
The Switch: Only when the evidence is overwhelming (and the buffer is satisfied) does the captain switch to "Full Aggression" (exploring the risky shortcut). If the radar later shows a mistake, the captain immediately hits the "Hard Restart" button, goes back to the safe route, and wipes the slate clean.

Why This is Special

The paper proves that Prudent-Banker achieves the "Best of Both Worlds":

It's Safe: It never loses much more than the safe baseline, even with delays. It pays almost zero extra cost for being safe.
It's Fast: It learns as fast as theoretically possible, even with the fog.

The authors also proved a "Lower Bound," which is like saying, "You can't build a better ship than this." They showed that no other method can be both safer and faster than Prudent-Banker in this specific scenario.

The Experiment

The authors tested this in a computer simulation (a "video game" of sorts) with 100 different paths and 50,000 turns. They tested three types of fog:

Short delays: A few seconds of lag.
Geometric delays: Occasional long lags.
Pareto delays: Rare, but massive lags (like a radar blackout for a long time).

The Result:

Old Safe Algorithms: Stayed too conservative and missed opportunities.
Old Fast Algorithms: Got confused by the delays, thought they were doing well when they were actually crashing, and accumulated huge losses.
Prudent-Banker: It danced perfectly. It stayed close to the safe route when the fog was thick, but as soon as the "Safety Buffer" cleared, it sped up. When the fog got too thick again, it slowed down and restarted.

The Bottom Line

Prudent-Banker is a new way to make decisions when you don't know the results immediately. It teaches us that you can be bold and fast without being reckless, as long as you have a smart "banker" to manage your credit and a "buffer" to account for the time it takes to see the consequences of your actions. It is the first method to prove you can have your cake (safety) and eat it too (speed), even when the world is slow to tell you what happened.

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

1. Problem Formulation

The paper addresses the Safe Online Learning in Delays (SOLID) problem within the framework of adversarial multi-armed bandits (MAB) with delayed feedback. The setting involves a learner interacting with an oblivious adversary over a horizon $T$ . At each round $t$ , the learner selects a distribution over arms, incurs a loss, and receives feedback only after a delay $d_t$ . The total delay is denoted by $D = \sum d_t$ .

The core challenge is to satisfy two simultaneous, often conflicting objectives:

Global Robustness (Minimax Optimality): Achieve a worst-case pseudo-regret of $\tilde{O}(\sqrt{T} + \sqrt{D})$ against the best fixed arm in hindsight, even under arbitrary adversarial loss sequences and delays.
Risk-Averse Behavior at No Extra Cost: Maintain a comparator regret of $\tilde{O}(1)$ relative to a designated safe baseline policy $x_c$ . This ensures the learner does not suffer significant additional loss compared to a trusted, vetted strategy (e.g., a standard medical treatment or conservative investment rule) while exploring.

The paper highlights that existing approaches for immediate feedback (e.g., Müller et al. [49]) fail in the delayed setting. Delays create a "hidden debt" where unobserved losses distort the learner's perception of the baseline's performance. Standard safety mechanisms, which rely on comparing observed gaps to a threshold, may trigger premature transitions from conservatism to aggression, violating the safety guarantee.

2. Methodology: The PRUDENT-BANKER Algorithm

The authors propose PRUDENT-BANKER, a novel algorithm that integrates a delay-adapted Online Mirror Descent (OMD) variant with a modified phased-aggression mechanism. The algorithm operates on three hierarchical levels of adaptation:

A. Delay-Stage Adaptation (Unknown Total Delay)

Since the total delay $D$ is unknown, the algorithm employs a doubling trick to estimate the delay scale. It operates in "stages" $s$ . If the accumulated delay within a stage exceeds the current estimate $\hat{D}_s$ , the algorithm triggers a Hard Restart:

The delay estimate is doubled ( $\hat{D}_{s+1} \approx 2\hat{D}_s$ ).
The internal state is reset to adapt to the new delay scale.
This ensures the algorithm adapts to the unknown delay landscape without prior knowledge.

B. The Core Learner: Banker-OMD

The base learner utilizes Banker-OMD (Huang et al. [31]), which handles feedback latency by maintaining a virtual account of "step-size credits."

Instead of updating immediately, the algorithm allocates learning rates based on the availability of feedback.
It constructs importance-weighted estimators only when feedback arrives.
This mechanism restores the telescoping cancellation property of OMD, ensuring the base learner achieves $\tilde{O}(\sqrt{T} + \sqrt{D})$ regret regardless of the feedback arrival order.

C. Phased Aggression with Delay-Calibrated Restarts

The safety mechanism is controlled by an aggression parameter $\alpha_k \in [0, 1]$ , which mixes the base learner $\hat{x}_t$ with the safe baseline $x_c$ :
$x_t = \alpha_k \hat{x}_t + (1 - \alpha_k) x_c$
The algorithm starts with low aggression (high weight on $x_c$ ) and increases $\alpha_k$ geometrically ( $2^{k-1}$ ) as it gathers evidence that the baseline is suboptimal.

The Key Innovation: Delay-Calibrated Restart Threshold
In the absence of delays, a restart is triggered if the empirical gap between the baseline and the learner exceeds a threshold $R$ . In the delayed setting, the authors introduce a slack term $\xi$ to account for "ghost losses" (unobserved feedback):
$\text{Threshold } B(\hat{D}_s) = 2\hat{R}(\hat{D}_s) + \xi(\hat{D}_s)$
where $\xi(\hat{D}_s) \approx O(\sqrt{\hat{D}_s/\delta})$ .

Soft Restart: If the observed gap exceeds $B(\hat{D}_s)$ , the algorithm enters a new phase, increases $\alpha_k$ , and resets the base learner.
Safety Guarantee: The slack term $\xi$ acts as a buffer against the distortion caused by missing feedback. It prevents the algorithm from falsely concluding the baseline is suboptimal due to unobserved losses, thereby preserving the $\tilde{O}(1)$ comparator regret.

3. Key Contributions

First Algorithm for SOLID with Delays: PRUDENT-BANKER is the first algorithm to achieve the optimal safety–robustness trade-off in adversarial bandits with arbitrary delays. It simultaneously guarantees:
- Worst-case regret: $\tilde{O}(\sqrt{T} + \sqrt{D})$ .
- Comparator regret: $\tilde{O}(1)$ (specifically $O(\log D)$ ).
Delay-Calibrated Restart Mechanism: The paper identifies that standard safety tests fail under delays due to "hidden debt." The authors derive a rigorous delay-calibrated restart threshold that accounts for the worst-case distortion induced by unobserved feedback. This allows for safe switching from conservatism to exploration without violating safety guarantees.
Optimality via Lower Bounds: The authors establish new lower bounds for safety-constrained adversarial delayed bandits. They prove that the $\tilde{O}(\sqrt{\delta^{-1}T} + \sqrt{\delta^{-1}D})$ regret rate achieved by PRUDENT-BANKER is unimprovable (up to logarithmic factors) under the baseline-safety requirement. This confirms that the $\delta^{-1/2}$ overhead is the intrinsic price of safety in the presence of delays.
Resolution of the "Best-of-Both-Worlds" in Delays: The work extends the "Best-of-Both-Worlds" (BOBW) concept—simultaneous guarantees against a specific comparator and in the worst case—to the delayed feedback setting, resolving a gap left by previous immediate-feedback frameworks.

4. Results and Experiments

Theoretical Results

Theorem 4.1: PRUDENT-BANKER achieves $R_T \le \tilde{O}(\sqrt{C_1 C_2}(\sqrt{T} + \sqrt{D}))$ and $R_T(x_c) \le O(1 + \log D)$ .
Theorem 4.2 (Lower Bound): Any algorithm satisfying a constant comparator regret must incur a worst-case regret of at least $\Omega(\sqrt{\delta^{-1}T} + \sqrt{\delta^{-1}D})$ . This proves the optimality of PRUDENT-BANKER's dependence on $T$ and $D$ .

Experimental Findings

Experiments were conducted on a non-stationary synthetic environment ( $T=50,000$ , $A=100$ ) under three delay regimes: no delay, geometric delays, and heavy-tailed Pareto delays.

Safety: PRUDENT-BANKER maintained a bounded (and often negative) gap relative to the safe comparator across all delay regimes, validating the $\tilde{O}(1)$ guarantee. In contrast, baselines like SAFE-EXP3-IX and CONSERVATIVE-UCB failed to certify comparator-level safety under delays.
Adaptivity: The mixing coefficient $\alpha_t$ in PRUDENT-BANKER dynamically adjusted. Under delays, the algorithm repeatedly performed conservative restarts when the realized delay budget exceeded estimates, only re-entering aggressive phases after the delay-calibrated threshold was met.
Competitiveness: PRUDENT-BANKER outperformed SAFE-EXP3-IX in worst-case regret (pseudo-loss) while maintaining safety, demonstrating that it effectively balances exploration and safety without the "wasteful" exploration of standard adversarial learners.

5. Significance and Claims

The paper claims to provide the first affirmative resolution of the SOLID problem in the adversarial delayed-feedback setting. Its significance lies in:

Bridging the Gap: It connects the theoretical robustness of minimax-optimal delayed bandit algorithms with the practical necessity of safety constraints in high-stakes domains (e.g., clinical decision-making, robotics).
Rigorous Safety: It demonstrates that safety can be maintained without a linear penalty in regret, even when feedback is delayed, by rigorously accounting for information deficits.
Optimality: By proving matching upper and lower bounds, the paper establishes that the trade-off between safety and robustness under delays is fundamentally optimal, setting a new benchmark for safe online learning in asynchronous environments.

The authors conclude that PRUDENT-BANKER effectively balances safety and learning, avoiding the "mistimed transitions" that endanger safety guarantees in existing delay-robust baselines.