On-line learning and the metrical task system problem

Abstract

We relate two problems that have been explored in two distinct communities. The first is the problem of combining expert advice, studied extensively in the computational learning theory literature, and in particular the problem of tracking the best expert in the clean ``decision-theoretic'' setting. The second is the Metrical Task System (MTS) problem, studied extensively in the On-line Algorithms literature, and in particular, variations on the setting of the uniform metric space. We show that these problems contain several interesting similarities and demonstrate how algorithms designed for each can be used to achieve good bounds and new approaches for solving the other.

Specific contributions of this paper include:

• An analysis showing how two recent algorithms for the MTS problem can be applied to the setting of tracking the best expert, providing good bounds with an approach of a much different flavor than the well-known multiplicative weighted-expert algorithms.
• A version of Herbster and Warmuth's weight-sharing algorithm for tracking the best expert that works in the decision-theoretic setting, and an application of this to the Metrical Task System problem.
• A new simpler algorithm for tracking experts, which does not carry over to the MTS problem.

Finally, we present an experimental comparison of how these algorithms perform on a process migration problem.