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.