Multiarmed Bandits with Strategic Feedback Skipping

This direction is merged into another direction: adversarial delay robustness. Its last version stays readable and citable here.

Version 1 of 112 papers19 conceptsfrozen 2026-10-04

In standard online learning, an agent makes a choice and receives immediate feedback. However, real-world applications like clinical trials or online advertising involve feedback delays that are often variable, unpredictable, or even infinite. Traditional algorithms struggle here because they must either slow down their learning rate to account for the worst-case delay or risk becoming unstable due to "stale" information.

A powerful solution emerging across recent research is the skipping mechanism: a strategy where the algorithm intentionally ignores feedback that arrives too late. By treating extreme outliers as lost data rather than incorporating them into the learning process, these algorithms maintain high performance and responsiveness.

The Cost of Waiting

When feedback is delayed, an agent must act multiple times before seeing the results of its previous choices. In adversarial settings, this delay creates a "drift" between the agent's current strategy and the information it has available. To maintain theoretical guarantees, classic algorithms like Exp3 must reduce their learning rate as the total delay increases.

The problem is that a single massive delay—or a few observations that never arrive—can force the learning rate to become so small that the agent stops learning effectively from the prompt feedback it does receive. Tobias Sommer Thune, Nicolò Cesa-Bianchi, and Yevgeny Seldin addressed this in Nonstochastic Multiarmed Bandits with Unrestricted Delays by introducing the "Skipper." Instead of letting a few outliers dictate the pace, the Skipper sets a temporal threshold; any feedback exceeding this limit is simply discarded.

Dynamic Thresholding for Robustness

The challenge lies in choosing the right threshold. If you skip too much, you lose valuable information; if you skip too little, the delays destabilize the learner. Modern approaches use dynamic thresholds that adapt to the observed delay distribution.

In Adapting to Delays and Data in Adversarial Multi-Armed Bandits, András György and Pooria Joulani developed algorithms that adjust strategies based on both the timing and the values of losses. This ensures that the cumulative regret remains bounded even when a subset of observations is significantly delayed.

This concept has been further refined into "Best-of-both-worlds" (BOBW) algorithms. These are designed to perform optimally in both stochastic (stable) and adversarial (changing) environments. Julian Zimmert, Saeed Masoudian, and Yevgeny Seldin demonstrate in A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delays that strategic skipping is essential for robustness. By ignoring feedback that exceeds a dynamic latency limit, the algorithm prevents a small number of indefinitely delayed observations from causing linear regret growth.

Beyond Single Agents

The utility of skipping extends to complex multi-agent systems. In decentralized Reinforcement Learning, agents often face asynchronous reward signals. Yuyang Zhang, Gen Li, and Na Li introduced the "usable visits" mechanism in Multi-Agent Reinforcement Learning with Reward Delays. By calculating a skipping threshold based on accumulated delay, agents can bypass missing data points and continue optimization, achieving convergence rates that match delay-free settings.

Why It Works: The Intuition

The core intuition behind skipping is a trade-off between bias and stability:

  1. Stability: Incorporating very old feedback introduces "noise" because the agent's strategy has changed significantly since that action was taken.
  2. Bias: Ignoring feedback introduces a small amount of bias (since we miss some data), but this bias is often negligible compared to the benefit of maintaining a faster, more aggressive learning rate.

By strategically filtering the feedback stream, these algorithms ensure that the "effective" delay remains small, allowing the agent to stay nimble in the face of uncertainty.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_multiarmed_bandits_with_strategic_feedba_456b246f,
  title = {Multiarmed Bandits with Strategic Feedback Skipping},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multiarmed-bandits-with-strategic-feedback-skipping/rdr_456b246fd4bc4f179b10e14859829e2a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_multiarmed_bandits_with_strategic_feedba_456b246f_v1,
  title = {Multiarmed Bandits with Strategic Feedback Skipping},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multiarmed-bandits-with-strategic-feedback-skipping/rdr_456b246fd4bc4f179b10e14859829e2a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}