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. 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.
翻译:本文考虑了在线定位问题的变体, 在线算法可以访问多个预测器, 每一个都生成了页面到达时间的预测序列。 预测器可能会偶尔出现预测错误, 并且假设其中至少有一个会产生一个子线性预测错误。 我们的主要结果表明, 这个假设足以设计随机化的在线算法, 其时间平均对最佳离线算法的遗憾往往为零, 因为时间倾向于无限。 这( 具有不同的遗憾界限 ), 既包括完整的信息访问模型, 在每个回合中, 在线算法都能得到所有预测器的预测, 也包括带宽访问模型, 在每回合中, 在线算法询问一个单一预测器。 尽管利用不准确预测的在线算法在过去几年中引起了越来越多的兴趣, 据我们所知, 这是第一个在多个预测器中研究这个话题的论文。 此外, 根据我们所知, 这还是第一个旨在( 并实现) 在线算法, 在合理的假设下, 以迷惑为典型的在线算法的( ) 实现( ) 。