This paper deals with bandit online learning problems involving feedback of unknown delay that can emerge in multi-armed bandit (MAB) and bandit convex optimization (BCO) settings. MAB and BCO require only values of the objective function involved that become available through feedback, and are used to estimate the gradient appearing in the corresponding iterative algorithms. Since the challenging case of feedback with delays prevents one from constructing the sought gradient estimates, existing MAB and BCO algorithms become intractable. For such challenging setups, delayed exploration, exploitation, and exponential (DEXP3) iterations, along with delayed bandit gradient descent (DBGD) iterations are developed for MAB and BCO, respectively. Leveraging a unified analysis framework, it is established that the regret of DEXP3 and DBGD are @math and @math , respectively, where @math is the maximum delay and @math denotes the delay accumulated over @math slots. Numerical tests using both synthetic and real data validate the performance of DEXP3 and DBGD.
This class deals with delayed but fully revealed loss information, namely fully known gradient or loss function. It is proved that an @math regret for a @math -slot time horizon with overall delay @math can be achieved. Particularly, algorithms dealing with a fixed delay have been studied in @cite_16 . To reduce the storage and computation burden of @cite_16 , an online gradient descent type algorithm for fixed @math -slot delay was developed in @cite_8 , where the lower bound @math was also provided. Adversarial delay has been tackled recently in @cite_13 @cite_0 @cite_7 . However, the algorithms as well as the corresponding analyses in @cite_13 @cite_0 @cite_7 are not applicable to bandit online learning setting when the delays are unknown.
@cite_7 @cite_8 @cite_0 @cite_16 @cite_13
2186411897 2949198759 2963727676 2101734711 2563280975
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 O(√D) in the delayed setting, where D is the sum of delays of each round's feedback. This bound collapses to an optimal O(√T) 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. Online learning algorithms have impressive convergence properties when it comes to risk minimization and convex games on very large problems. However, they are inherently sequential in their design which prevents them from taking advantage of modern multi-core architectures. In this paper we prove that online learning with delayed updates converges well, thereby facilitating parallel online learning. Prediction of individual sequences is investigated for cases in which the decision maker observes a delayed version of the sequence, or is forced to issue his her predictions a number of steps in advance, with incomplete information. For finite action and observation spaces, it is shown that the prediction strategy that minimizes the worst case regret with respect to the Bayes envelope is obtained through subsampling of the sequence of observations. The result extends to the case of logarithmic loss. For finite-state (FS) reference prediction strategies, the delayed FS predictability (DFSP) is defined and related to its nondelayed counterpart. As in the nondelayed case, an efficient on-line decision algorithm, based on the incremental parsing rule, is shown to perform in the long run essentially as well as the best FS strategy determined in hindsight, with full knowledge of the given sequence of observations. An application to adaptive prefetching in computer memory architectures is discussed. We present a unified, black-box-style method for developing and analyzing online convex optimization (OCO) algorithms for full-information online learning in delayed-feedback environments. Our new, simplified analysis enables us to substantially improve upon previous work and to solve a number of open problems from the literature. Specifically, we develop and analyze asynchronous AdaGrad-style algorithms from the Follow-the-Regularized-Leader (FTRL) and Mirror-Descent family that, unlike previous works, can handle projections and adapt both to the gradients and the delays, without relying on either strong convexity or smoothness of the objective function, or data sparsity. Our unified framework builds on a natural reduction from delayed-feedback to standard (non-delayed) online learning. This reduction, together with recent unification results for OCO algorithms, allows us to analyze the regret of generic FTRL and Mirror-Descent algorithms in the delayed-feedback setting in a unified manner using standard proof techniques. In addition, the reduction is exact and can be used to obtain both upper and lower bounds on the regret in the delayed-feedback setting.