An Improved On-Line Algorithm for Learning Linear Evaluation Functions

Abstract

We improve and extend results on a learning model where an algorithm has to make a sequence of choices based on an evaluation function [Lon97]. This evaluation function has to be learned on-line from partial information and is assumed to be linear. The main innovation of this paper is the introductionand analysis of a new kind of on-line algorithm which is "adaptively conservative". This algorithm changes its current hypothesis only if the hypothesis is substantially wrong. The analysis of this algorithm establishes performance bounds which depend more directly on the quality of the best off-line approximation of the evaluation function. This improves and unifies previous results. 1 Introduction We consider the learning model proposed in [Lon97] and call it the uniform evaluation model. We will also consider a slight extension of this model which we call individual evaluation model. In both models learning proceeds in trials t = 1; : : : ; m. In each trial t the learning algorithm f...