Source-linked AI summary
Online Learning under Delayed Feedback
Pooria Joulani, András György, Csaba Szepesvári
TL;DR
Delayed feedback creates a gap between online decisions and the observations needed to update them, affecting applications such as web advertising and distributed learning. The paper systematically analyzes this setting, gives black-box and UCB-based adaptations, and finds multiplicative regret increases in adversarial problems but additive increases in stochastic problems.
Problem
A comprehensive understanding of how delayed feedback affects online learning regret is missing, despite delayed feedback arising in web advertising and distributed learning.
Method
The paper studies partial monitoring, transforms non-delayed algorithms through black-box meta-algorithms, and adapts UCB for stochastic bandits with delayed feedback.
Results
Delay increases regret multiplicatively in adversarial problems and additively in stochastic problems.
Takeaways & Limitations
The delay cost depends on the problem setting, while general transformations extend non-delayed forecasters and modified UCB algorithms offer lower-complexity handling in bandits.
Takeaways & Limitations
Matching lower bounds establish these qualitative delay effects only for the full-information case, not for the general partial-monitoring setting.
Abstract
from arXiv · showhide
Online learning with delayed feedback has received increasing attention recently due to its several applications in distributed, web-based learning problems. In this paper we provide a systematic study of the topic, and analyze the effect of delay on the regret of online learning algorithms. Somewhat surprisingly, it turns out that delay increases the regret in a multiplicative way in adversarial problems, and in an additive way in stochastic problems. We give meta-algorithms that transform, in a black-box fashion, algorithms developed for the non-delayed case into ones that can handle the presence of delays in the feedback loop. Modifications of the well-known UCB algorithm are also developed for the bandit problem with delayed feedback, with the advantage over the meta-algorithms that they can be implemented with lower complexity.
1. Introduction
The paper systematically studies online learning when feedback is delayed, motivated by web advertising and distributed learning. It develops general transformations for delayed settings and finds multiplicative regret effects in adversarial problems versus additive effects in stochastic problems.
- Motivation: Delayed feedback matters in web advertising and parallel, distributed learning because information about prior predictions may arrive later.Examples include delayed ad-click information and delays caused by propagating information among distributed nodes.
- Contribution: The paper addresses the missing comprehensive understanding of delays by studying delayed online learning in the general partial monitoring setting.This setting covers previously considered online learning scenarios and extends, unifies, and often improves existing results.
- Contribution: The proposed meta-algorithms transform non-delayed online learning algorithms into algorithms that handle delayed feedback in a black-box fashion.The transformation is designed to handle delays efficiently without requiring a problem-specific redesign of the base algorithm.
- Main result: Delay inflates regret multiplicatively in adversarial problems but only additively in stochastic problems.This is presented as a surprising qualitative distinction between the two settings.
- Scope: The paper analyzes adversarial and stochastic problems, then develops a delayed-feedback modification of UCB for bandit problems.The paper structure places these analyses in Sections 3.1 and 3.2 and the UCB modification in Section 4.
2. The delayed feedback model
The delayed feedback model lets a forecaster act on side information while feedback is scheduled for later delivery with timestamps. It generalizes full-information, bandit, and partial-monitoring settings and motivates regret analyses based on outstanding or missing feedback.
- Model specification: The model uses prediction set A, outcomes B, side information X, reward function r, feedback function h, and horizon n.These parameters define the forecaster, environment, rewards, observations, and time horizon.
- Interaction: At each step, the environment selects side information and an outcome, after which the forecaster predicts and receives the corresponding reward.The reward depends on the side information, prediction, and outcome but is unknown to the forecaster at decision time.
- Delayed observations: Feedback h_t is scheduled for revelation after τ_t time instants, and all feedback due at time t arrives with its original timestamp.Multiple feedback values can arrive simultaneously, and delays can reorder the observations of earlier and later predictions.
- Objective: The forecaster maximizes cumulative reward and is evaluated by regret relative to the best static strategy in hindsight.Consistency is expressed as the average regret converging to zero.
- Special cases: The framework includes full-information, bandit, and partial-monitoring cases through different feedback functions and observation sets.Full information reveals the reward function, bandit feedback reveals the selected prediction's reward, and partial monitoring uses a general feedback function h.
- Relation to prior work: The paper generalizes prior delayed-feedback results to partial monitoring, with bounds also applying to more specialized settings.Related work covers adversarial and stochastic full-information, bandit, and Gaussian-process settings, while Table 1 summarizes the results.
3. Black-Box Algorithms for Delayed Feedback
The paper develops black-box reductions from non-delayed online-learning algorithms to delayed-feedback settings. BOLD handles adversarial and partial-monitoring problems, while QPM-D handles finite stochastic settings with additive delay penalties.
- Adversarial setting: BOLD runs multiple instances of a non-delayed base algorithm, selecting a free instance or creating one when all existing instances await feedback.Feedback is routed to the instance that made the corresponding prediction.
- Adversarial setting: Theorem 1 transfers the base algorithm’s expected regret bound to BOLD when delays are independent of the forecaster’s predictions.The analysis decomposes regret across instances that experience no delays internally, then uses concavity of the base bound.
- Adversarial setting: For constant delays, BOLD recovers the multiplicative regret bound of Weinberger and Ordentlich and generalizes it to partial monitoring.The paper does not establish tightness of this bound in partial monitoring, even when the base algorithm is minimax optimal.
- Adversarial setting: For i.i.d. delays with finite mean, the delay-dependent bound increases only by a log n factor, even when delays have unbounded support.The concentration argument bounds outstanding feedbacks using the delay expectation and a high-probability control on their maximum.
- Finite stochastic setting: In finite stochastic partial monitoring, QPM-D uses a base algorithm on queued, potentially permuted feedback and reward sequences rather than waiting for the exact feedback order.Under the stated independence assumptions, the reordered feedback sequence for each prediction remains i.i.d. with the same distribution.
- Finite stochastic setting: The stochastic delay penalty is additive: QPM-D’s expected regret is bounded by the non-delayed base regret plus a term depending on the delay scale.The stated bound uses O(τmax) for bounded delays, with unbounded i.i.d. delays handled through the outstanding-feedback bound.
4. UCB for the Multi-Armed Bandit Problem with Delayed Feedback
The paper extends UCB-type algorithms to stochastic multi-armed bandits with delayed feedback, preserving their theoretical guarantees up to an additive delay penalty. This white-box approach avoids the high memory requirements of black-box conversions.
- White-box UCB extensions: The proposed white-box extension modifies existing UCB-family algorithms for delayed stochastic bandits while retaining their theoretical guarantees.The approach exploits common characteristics of UCB-type algorithms and incurs an additive penalty depending on delays.
- UCB decision rule: UCB algorithms select the prediction with the largest optimistic upper confidence bound computed from observed reward samples.In the non-delayed setting, the sample count includes all previous trials; delayed variants use the number of rewards observed before the current time.
- Regret analysis: The delayed UCB analysis bounds the number of trials of a suboptimal prediction using concentration inequalities tailored to its confidence bound.This preserves the standard proof pattern while accounting for rewards that remain unobserved when decisions are made.
- Regret guarantee: The delayed algorithms achieve regret guarantees similar to their non-delayed counterparts, with only an additive penalty depending on the delays.The same concentration arguments can be reused for the delayed setting when confidence bounds use observed rewards.
5. Conclusion and future work
The conclusion reports that delay affects adversarial and stochastic online learning differently, while identifying the maximum number of missing rewards as the key performance quantity. Future analysis may benefit from connections to queueing systems and Markov chains, but matching lower bounds remain incomplete.
- Main conclusions: Delay increases regret multiplicatively in adversarial problems but only additively in stochastic problems.The authors describe these findings as qualitatively correct, but matching lower bounds are available only for the full information case.
- Key delay quantity: G∗_n, the maximum number of missing rewards, is the most important quantity determining the performance of the algorithms.This quantity captures the largest number of rewards unavailable while predictions are made.
- Connections: G∗_n equals the maximum number of servers in a multi-server queue with infinitely many servers and deterministic arrival times.The paper also relates it to the maximum deviation of a certain type of Markov chain.
- Future work: Results from queueing and Markov-chain theory could improve understanding of G∗_n and thereby improve delayed-feedback regret analysis.The authors note that they have not found immediately applicable results from these fields.
A. Proof of Lemma 4
The proof shows that independently delayed feedback remains i.i.d. after sorting by observation time and selecting feedback without dependence on future observations. This establishes the distributional property needed for Lemma 4.
- Reordering lemma: An independent random reordering of an i.i.d. sequence remains i.i.d. with the same distribution.The proof verifies equality of finite-dimensional joint probabilities under every fixed permutation and then averages over independent permutations.
- Delayed feedback ordering: Sorting feedback by possible observation time is an independent reordering because delays are independent of outcomes.The reordered sequence therefore has the same distribution as the original feedback sequence.
- Subsequence property: The feedback observed for one prediction forms a subsequence whose inclusion decisions cannot depend on future observations.Feedback from other predictions used in selecting the subsequence is assumed independent of the relevant reordered sequence.
- Conclusion of Lemma 4: By the subsequence lemma, the observed feedback sequence for a prediction is i.i.d. with the same distribution as its original feedback sequence.This completes the probabilistic step used in the i.i.d. partial-monitoring analysis.
B. UCB for the Multi-Armed Bandit Problem with Delayed Feedback
The delayed UCB analysis replaces trial counts with observed-reward counts in confidence bounds, then reuses the non-delayed concentration argument. The resulting regret matches the non-delayed analysis up to an additive delay-dependent penalty.
- Non-delayed analysis: Standard UCB analysis bounds a suboptimal prediction’s regret by upper bounding how often it is selected beyond a threshold.Whenever the suboptimal prediction is chosen, its confidence bound must exceed that of an optimal prediction.
- Concentration step: Concentration inequalities bound the expected excess-selection term in the standard UCB proof.These inequalities depend on the specific form of the confidence bounds.
- Delayed confidence bounds: In delayed feedback, confidence bounds use S_i(t−1), the number of rewards observed before time t, instead of T_i(t−1), the number of trials.The relation T_i(t−1) = G_i,t + S_i(t−1) separates trials with missing feedback from observed rewards.
- Regret consequence: The same concentration inequalities yield performance similar to the non-delayed setting, with an additive penalty depending on delays.This framework supports the delayed analysis of two UCB-type algorithms.
B.1. UCB1 under delayed feedback: Proof of Theorem 7
Theorem 7 bounds Delayed-UCB1 by adapting the original UCB1 analysis. Hoeffding’s inequality controls the probability terms, and combining the resulting bound with (2) completes the proof.
- The proof follows the original UCB1 analysis to bound the summation in (8) for each prediction i.
- Hoeffding’s inequality bounds each probability appearing in the summation.
- ζ(3) < 1.21 appears in the resulting bound before it is combined with (2) to prove Theorem 7.
B.2. KL-UCB under delayed feedback
The delayed KL-UCB analysis reuses the non-delayed KL-UCB proof with an adapted divergence lemma and a delay-dependent counting argument. The resulting algorithm retains the logarithmic structure of the non-delayed bound while adding a delay-related penalty.
- The Delayed-KL-UCB algorithm uses the KL-UCB upper confidence bound within the general delayed-feedback scheme.
- Theorem 10 states an expected-regret bound with leading term d(µi, µi∗)(1 + ǫ) and logarithmic term C1 log(log(n)).
- The adapted lemma bounds the positive KL-divergence term by log(n) + 3 log(log(n)) when the observation count is at least ℓ′.
- At most G∗i,n time instants can occur for each fixed observation count while prediction i is made and the count remains constant.
- The first summation retains the non-delayed logarithmic bound, while the second is controlled by Lemma 13 and delay independence from rewards.