On-line learning and the metrical task system problem

The problem of combining expert advice, studied extensively in the Computat ional Learning Theory literature, and the Metrical Task System (MTS) proble m, studied extensively in the area of On-line Algorithms, contain a number of interesting similarities. In this paper we explore the relationship betw een these problems and show how algorithms designed for each can be used to achieve good bounds and new approaches for solving the other. Specific con tributions of this paper include: An analysis of how two recent algorithms for the MTS problem can be applied to the problem of tracking the best expert in the "decision-theoretic" set ting, providing good bounds and an approach of a much different flavor from the well-known multiplicative-update algorithms. An analysis showing how the standard randomized Weighted Majority (or Hedge ) algorithm can be used for the problem of "combining on-line algorithms on -line", giving much stronger guarantees than the results of Azar, Y., Brode r, A., & Manasse, M. (1993). Proc ACM-SIAM Symposium on Discrete Algorithms (pp. 432-440) when the algorithms being combined occupy a state space of b ounded diameter. A generalization of the above, showing how (a simplified version of) Herbst er and Warmuth's weight-sharing algorithm can be applied to give a "finely competitive" bound for the uniform-space Metrical Task System problem. We a lso give a new, simpler algorithm for tracking experts, which unfortunately does not carry over to the MTS problem. Finally, we present an experimental comparison of how these algorithms perf orm on a process migration problem, a problem that combines aspects of both the experts-tracking and MTS formalisms.