Caching under adversarial requests has been studied since Sleator and Tarjan's seminal paper [1]} through the competitive ratio metric. An algorithm is said to be \(\alpha \) -competitive when its competitive ratio is bounded by \(\alpha \)  over all possible input sequences. The problem has been generalized by Manasse et al. [2]} under the name \(k\) -server problem, and further generalized by Borodin et al. under the name metrical task systems (MTS) [3]}. The literature on both the \(k\) -server and MTS problems is vast.
A recent trend is to apply continuous optimization techniques to solve these combinatorial problems. Bansal et al. [4]} study the \(k\) -server problem on a weighted star metric space. In the same spirit, Bubeck et al. [5]} use the framework of continuous online mirror descent to provide an \(o(k)\) -competitive algorithm for the \(k\) -server problem on hierarchically separated trees. In this paper, we focus on regret rather than competitive ratio as main performance metric.
Andrew et al. [6]} give a formal comparison between competitive ratio and regret and
prove that there is an intrinsic incompatibility between the two: no algorithm can have both sub-linear regret and a constant competitive ratio. At the same time, they propose an algorithm with sub-linear regret and slowly increasing competitive ratio.
