On-line evaluation and prediction using linear functions

Abstract

We propose a model for situations where an algorithm needs to make a sequence of choices to minimize an evaluation function, but where the evaluation function must be learned on-line as it is being used. We describe algorithms for learning linear evaluation functions in this model, and prove performance bounds for them that hold in the worst case. Each bound is on the expectation, with respect to an algorithm`s randomization, of the sum of differences between the costs of the choices the algorithm makes and the best choices available. The bounds are in terms of the extent to which a linear model is appropriate, the number of alternatives to choose from, and the number of choices that need to be made. Ideas from the above analysis yield new absolute loss bounds for learning linear functions in the standard on-line prediction model. These bounds are on difference between the sum of absolute prediction errors made by the learning algorithm, and the best sum of absolute prediction errors that can be obtained by fixing a linear function in the given class. Known results imply that our bounds on this difference cannot be improved by more than a constant factor.