On-line Learning with Delayed Label Feedback Author: Chris Mesterharm Source: Algorithmic Learning Theory, 16th International Conference, ALT 2005, Singapore, October 2005, Proceedings, (Sanjay Jain, Hans Ulrich Simon and Etsuji Tomita, Eds.), Lecture Notes in Artificial Intelligence 3734, pp. 399 - 413, Springer 2005. Abstract. We generalize on-line learning to handle delays in receiving labels for instances. After receiving an instance x, the algorithm may need to make predictions on several new instances before the label for x is returned by the environment. We give two simple techniques for converting a traditional on-line algorithm into an algorithm for solving a delayed on-line problem. One technique is for instances generated by an adversary; the other is for instances generated by a distribution. We show how these techniques effect the original on-line mistake bounds by giving upper-bounds and restricted lower-bounds on the number of mistakes. ©Copyright 2005, Springer