Online Paging with a Vanishing Regret
This work provides a novel approach for online paging algorithms to achieve vanishing regret, which is significant for systems that rely on potentially inaccurate predictions over unbounded request sequences.
This paper addresses the online paging problem where an online algorithm uses multiple predictors, at least one of which makes a sublinear number of prediction errors. The authors designed a randomized online algorithm whose time-average regret, compared to the optimal offline algorithm, approaches zero over time. This result holds for both full information and bandit access models.
This paper considers a variant of the online paging problem, where the online algorithm has access to multiple predictors, each producing a sequence of predictions for the page arrival times. The predictors may have occasional prediction errors and it is assumed that at least one of them makes a sublinear number of prediction errors in total. Our main result states that this assumption suffices for the design of a randomized online algorithm whose time-average regret with respect to the optimal offline algorithm tends to zero as the time tends to infinity. This holds (with different regret bounds) for both the full information access model, where in each round, the online algorithm gets the predictions of all predictors, and the bandit access model, where in each round, the online algorithm queries a single predictor. While online algorithms that exploit inaccurate predictions have been a topic of growing interest in the last few years, to the best of our knowledge, this is the first paper that studies this topic in the context of multiple predictors for an online problem with unbounded request sequences. Moreover, to the best of our knowledge, this is also the first paper that aims for (and achieves) online algorithms with a vanishing regret for a classic online problem under reasonable assumptions.