论文标题
在线寻求遗憾
Online Paging with a Vanishing Regret
论文作者
论文摘要
本文考虑了在线分页问题的变体，在线算法可以访问多个预测因子，每个预测指标都会为页面到达时间产生一系列预测。预测因子可能偶尔会出现预测错误，并且假定其中至少有一个会导致总共数量的预测错误。我们的主要结果指出，这种假设足以设计一种随机在线算法的设计，该算法在最佳的离线算法上，随着时间的流逝趋向于无限。对于完整的信息访问模型，这既有（具有不同的遗憾界限），在每个回合中，在线算法都可以预测所有预测变量，而Bandit访问模型则在每个回合中，在线算法在线算法查询一个单个预测指标。虽然利用不准确预测的在线算法在过去几年中一直引起人们越来越兴趣的话题，但据我们所知，这是第一篇论文在多个预测指标的背景下研究该主题的在线问题，这是一个没有绑定的请求序列。此外，据我们所知，这也是第一篇旨在（并实现）在线算法的论文，在合理假设下对经典在线问题的遗憾消失了。
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.
