# On-line algorithms for expert advice and task systems

Carl Burch

Thesis, May 20, 2000

Thesis proposal, February 16, 1999

### Abstract

This thesis explores two general on-line scenarios
historically deriving from two largely disjoint communities.
Though the problems are inherently similar,
the techniques and questions developed for these two problems are
very different;
an examination of them provides new insights and new directions,
each enriching the other.
From machine learning comes the problem
of *predicting from expert advice* - that is,
of choosing one of several experts for each query in a sequence
without doing much worse than the best expert overall.
And from competitive analysis comes *metrical task systems*,
where the algorithm is to decide in which state
to process each of several sequential tasks,
where each task specifies the processing cost in each state,
but changing states also has a cost according to a metric.

Besides connecting these problems,
the thesis presents a variety of results
lying in and around the area defined by them,
including interesting hybrid problems
(adding a switching cost between experts)
or generalizations
(a task system where the algorithm occupies several states).
This thesis answers a long-standing question in
competitive analysis by proving the first polylogarithmic
competitive ratio for task systems in general metric spaces.

### Committee

Avrim Blum (chair)

Allan Borodin

Bruce Maggs

Danny Sleator

On-line algorithms for expert advice and task systems /
Publications /
Carl Burch /
12 Feb 1999