Abstract

 We study the performance of standard online learning algorithms when the feedback is delayed by an adversary. We show that online-gradient-descent  [1] and follow-the-perturbed-leader [2] achieve regret in the delayed setting, where D is the sum  of delays of each round’s feedback. This bound collapses to an optimal bound in the usual setting of no delays (where D = T ). Our main contribution is to show that standard algorithms for online learning already have simple regret bounds in the most general setting of delayed feedback, making adjustments to the analysis and not to the algorithms themselves. Our results help affirm and clarify the success of recent algorithms in optimization and machine learning that operate in a delayed feedback model.