Online Learning with Action Dependent Feedback Delays

This direction is merged into another direction: bandit feedback constraints. Its last version stays readable and citable here.

Version 1 of 16 papers16 conceptsfrozen 2026-10-04

In the standard multi-armed bandit framework, an agent pulls an arm and receives feedback—usually a reward or a loss—either immediately or after a fixed period. However, in many real-world scenarios, the time it takes to observe the outcome depends on the action itself. For instance, in clinical trials, a fast-acting drug provides data much sooner than a long-term treatment. In web advertising, a "click" happens seconds after an impression, while a "conversion" might take days.

Recent research has shifted toward modeling these action-dependent delays, revealing that the timing of information is just as critical as the value of the information itself.

The Information-Latency Trade-off

When delays depend on the action, the learner faces a novel dilemma: should I choose the arm with the lowest expected loss, or the arm that provides the fastest feedback?

Dirk van der Hoeven and Nicolò Cesa-Bianchi explored this in Nonstochastic Bandits and Experts with Arm-Dependent Delays. They demonstrated that in nonstochastic environments, there is a fundamental mathematical tension between minimizing immediate loss and minimizing feedback latency.

The intuition is that an action with a slightly higher immediate loss might actually be "cheaper" in the long run if its feedback arrives quickly. Faster feedback allows the algorithm to update its strategy more frequently, reducing the "stale" period where it might be playing suboptimal actions. By using a modified Follow the Regularized Leader (FTRL) approach, they showed that an algorithm can achieve first-order regret bounds by explicitly accounting for this trade-off, effectively treating information gain as a resource to be optimized alongside the primary objective.

When Delay is the Payoff

A particularly interesting case arises when the delay is not just action-dependent, but is actually tied to the magnitude of the payoff.

In Contextual Linear Bandits with Delay as Payoff, Mengxiao Zhang, Yingfei Wang, and Haipeng Luo investigate a setting where the feedback delay is proportional to the loss. This creates a "virtuous cycle": the most efficient actions (those with the lowest loss) provide the quickest feedback.

This asymmetry is a powerful tool for the learner. If the best actions are the fastest to report back, the learner can identify the optimal strategy much more rapidly than in settings where delays are uniform or, worse, where the best outcomes are the most delayed.

Overcoming the Failure of Confidence Ellipsoids

Standard contextual bandit algorithms like LinUCB rely on confidence ellipsoids to manage uncertainty. However, these methods often fail when delays are action-dependent because the "shape" of the uncertainty becomes biased by which actions have reported back and which are still pending.

To solve this, Zhang et al. utilize volumetric spanners—a geometric tool that ensures the learner chooses a diverse set of actions to span the feature space—combined with a phased arm elimination strategy. This approach allows the learner to maintain a robust estimate of the underlying reward function even when feedback arrives in a staggered, action-dependent fashion. Their work proves that with the right algorithmic structure, the regret overhead caused by these delays can be kept manageable, matching the performance of delay-free algorithms in many respects.

Why Action-Dependent Delay Matters

The shift from "delayed feedback" to "action-dependent delayed feedback" represents a move toward more realistic online learning. It acknowledges that the agent is not a passive recipient of information but an active participant who can choose how quickly they learn.

By prioritizing actions that provide rapid feedback, especially early in the learning process, these algorithms minimize the time spent in a state of ignorance. The core insight across this research is that latency is a cost, and a truly optimal agent must balance the quality of an action's reward with the speed of its revelation.

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_online_learning_with_action_dependent_fe_d9ba49b9,
  title = {Online Learning with Action Dependent Feedback Delays},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/online-learning-with-action-dependent-feedback-delays/rdr_d9ba49b9680e444195e6ff77da604ac9},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_online_learning_with_action_dependent_fe_d9ba49b9_v1,
  title = {Online Learning with Action Dependent Feedback Delays},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/online-learning-with-action-dependent-feedback-delays/rdr_d9ba49b9680e444195e6ff77da604ac9/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}