Competitive ratio vs regret minimization: achieving the best of both worlds
[edit]
Proceedings of the 30th International Conference on Algorithmic Learning Theory, PMLR 98:333368, 2019.
Abstract
We consider online algorithms under both the competitive ratio
criteria and the regret minimization one. Our main goal is to build
a unified methodology that would be able to guarantee both criteria
simultaneously.
For a general class of online algorithms, namely any Metrical Task
System (MTS), we show that one can simultaneously guarantee the best
known competitive ratio and a natural regret bound. For the paging
problem we further show an efficient online algorithm (polynomial in the number of pages) with this guarantee.
To this end, we extend an existing regret minimization algorithm
(specifically, Kapralov and Panigrahy 2011) to handle movement cost (the cost of
switching between states of the online system). We then show how to
use the extended regret minimization algorithm to combine multiple
online algorithms. Our end result is an online algorithm that can
combine a “base” online algorithm, having a guaranteed competitive
ratio, with a range of online algorithms that guarantee a small
regret over any interval of time. The combined algorithm guarantees
both that the competitive ratio matches that of the base algorithm
and a low regret over any time interval.
As a by product, we obtain an expert algorithm with close to optimal
regret bound on every time interval, even in the presence of
switching costs. This result is of independent interest.
Related Material


