Regret Scaling and Stability under Delayed Feedback

159 concepts89 papers2 proposals

In standard online learning and sequential decision-making, we assume an idealized feedback loop: a learner selects an action, immediately observes the resulting loss or reward, and updates its strategy before making the next choice. In real-world systems—such as recommender systems, clinical trials, or distributed networks—this loop is broken by latency. Feedback arrives days, weeks, or an unpredictable number of steps after an action is taken.

To design algorithms that are robust to these latencies, we must understand exactly why delay degrades performance, how that degradation scales, and how we can modify optimization algorithms to maintain stability when learning from stale data.

The Information Gap and Outstanding Feedbacks

The fundamental challenge of learning under delayed feedback is the information gap it creates. At any given time step, the learner must make a decision without knowing the outcomes of its most recent actions.

As established by Pooria Joulani et al., the primary driver of performance degradation in delayed settings is the number of outstanding feedbacks—the information currently "in flight" through the system. This quantity measures the exact size of the learner's blind spot.

The nature of this information gap depends heavily on whether the delays are stochastic or driven by an adversary:

  • Stochastic Delays: When feedback latencies are independent and identically distributed, the number of outstanding feedbacks grows slowly (often logarithmically relative to the time horizon). In these benign environments, the penalty on cumulative regret is merely additive, acting as a constant shift in performance (Pooria Joulani et al., Zhongxuan Liu et al.).
  • Adversarial Delays: If an adversary can manipulate when feedback is revealed, they can strategically withhold information to force the learner into making poor choices repeatedly. In these worst-case environments, the delay penalty can scale multiplicatively with the problem's complexity, severely harming the system's efficiency.

The Core Failure Mode: Multi-Round Instability

Why do standard online optimization algorithms, such as Follow-the-Regularized-Leader (FTRL) or Online Mirror Descent (OMD), break down when feedback is delayed? The answer lies in their stability guarantees.

Standard algorithms are designed for step-to-step stability; they ensure that the policy does not change drastically between consecutive rounds. However, when feedback is delayed by $\tau$ steps, the learner updates its policy using a gradient or loss signal that is $\tau$ steps old. If the algorithm continues to update its strategy at every step using this stale data, it can overcorrect, leading to wild oscillations.

To remain effective under delay, an algorithm must exhibit multi-round stability—meaning its strategy must remain stable over a window of steps equal to the delay period, rather than just between consecutive rounds (Dirk van der Hoeven et al.). Without this multi-round buffering, the look-ahead predictions of optimistic algorithms are too weak to compensate for the feedback lag.

This instability triggers a severe phase transition in multi-agent settings and games. As observed by Yuma Fujimoto et al. and Georgios Piliouras et al., even a single step of feedback latency can cause standard no-regret mechanisms to lose their convergence guarantees entirely, causing agents to enter high-regret, unstable cycles instead of reaching a Nash equilibrium.

Restoring Stability via Adaptive Learning Rates and Skipping

To neutralize the destabilizing effects of latency, modern robust online learning relies on two primary mechanisms: information-dependent step sizes and outlier filtering.

Information-Dependent Learning Rates

Standard online learning algorithms decay their learning rate $\eta_t$ purely as a function of the time horizon $t$. Under delayed feedback, this is counterproductive: the algorithm slows down its learning based on elapsed time, even if it hasn't actually received enough data to justify that slowdown.

To fix this, the authors of recent robust frameworks decouple the learning rate from elapsed time, making it decay based on the amount of feedback actually received (Yuanyu Wan et al.). By tying the step size directly to the volume of integrated feedback, the algorithm automatically slows down when information is scarce and accelerates when a batch of delayed feedback arrives, matching the true information state of the learner.

The Skipper Mechanism

In adversarial or highly variable delay environments, a single extreme delay outlier can ruin the learning process. If an algorithm attempts to adjust its global learning rate to accommodate the worst-case maximum delay, it is forced to adopt an excessively small step size, stalling progress across all rounds.

To resolve this trade-off, Tobias Sommer Thune et al. proposed the Skipper mechanism. Instead of trying to learn from every piece of data, the algorithm sets a dynamic delay threshold and strategically ignores (skips) any feedback that arrives later than this threshold.

Timeline of Actions and Feedback
Round:    t=1      t=2      t=3      t=4      t=5      t=6
Action:   [A1]     [A2]     [A3]     [A4]     [A5]     [A6]
Feedback:           |        |        |                 |
                    v        |        v                 v
                 FB(A1)      |     FB(A2)            FB(A4)
                 (Delay=1)   |     (Delay=2)         (Delay=2)
                             v
                          FB(A3) -> SKIPPED by Skipper Mechanism!
                          (Delay=3, Exceeds Threshold)

By discarding these long-delayed outliers, the system avoids the performance collapse associated with worst-case latencies. This allows the algorithm to maintain a much more aggressive learning rate for the vast majority of standard-delay rounds, optimizing the balance between the number of skipped observations and cumulative latency.

When Latency Becomes Exponential: Switching Costs

While sublinear delay tolerance is achievable in standard bandit and convex optimization settings—often scaling with the square root of the cumulative delay (Bingcong Li et al.)—there is a hard theoretical boundary when actions carry physical or computational momentum.

In online optimization problems featuring switching costs (where changing your action from $x_t$ to $x_{t+1}$ incurs a penalty proportional to their distance), the interaction with feedback delay changes completely. As demonstrated by Guanya Shi et al., the competitive ratio of any online algorithm degrades exponentially with the length of the feedback delay.

The intuition behind this bottleneck is clear: if changing actions is expensive, and you cannot observe the utility of your choices for $\tau$ steps, you may blindly commit to a trajectory that incurs massive switching costs while moving in the completely wrong direction. This exponential penalty marks a fundamental boundary where algorithmic adjustments to the learning rate can no longer fully shield a learner from the physical costs of delayed information.

Key Foundational Work

Online Learning under Delayed Feedback. (2013) — contributed 3 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_adversarial_delay_robustness_5b339869,
  title = {adversarial delay robustness},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adversarial-delay-robustness/rdr_5b339869504c45288efd742c6c86e019},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_adversarial_delay_robustness_5b339869_v1,
  title = {adversarial delay robustness},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adversarial-delay-robustness/rdr_5b339869504c45288efd742c6c86e019/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake