An Improved On-line Algorithm for Learning Linear Evaluation Functions

摘要

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 introduction and 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.