论文标题
遗憾 - 最佳的在线缓存，用于对抗和随机到达
Regret-Optimal Online Caching for Adversarial and Stochastic Arrivals
论文作者
论文摘要
我们考虑了尺寸有限的在线缓存问题。在一个时间间隙的系统中，用户从每个插槽中的大目录请求一个文件。如果所请求的文件被缓存，则该策略将获得单位奖励，否则将获得零奖励。我们表明，随时随地缓存策略同时遗憾的是对抗和i.i.d.的扰动领导者（FTPL）的关注。随机到达。此外，在与切换缓存内容相关的成本相关的环境中，我们提出了FTPL的一种变体，该变体相对于对抗性和随机性到达的时间，相对于时间的时间，相对于随机到达的开关成本，与FTPL相比，其性能明显更高。我们还表明，这些结果可以推广到在可以更改缓存内容的频率上存在约束的设置。最后，我们验证在各种合成和现实世界痕迹上获得的结果。
We consider the online caching problem for a cache of limited size. In a time-slotted system, a user requests one file from a large catalog in each slot. If the requested file is cached, the policy receives a unit reward and zero rewards otherwise. We show that a Follow the Perturbed Leader (FTPL)-based anytime caching policy is simultaneously regret-optimal for both adversarial and i.i.d. stochastic arrivals. Further, in the setting where there is a cost associated with switching the cached contents, we propose a variant of FTPL that is order-optimal with respect to time for both adversarial and stochastic arrivals and has a significantly better performance compared to FTPL with respect to the switching cost for stochastic arrivals. We also show that these results can be generalized to the setting where there are constraints on the frequency with which cache contents can be changed. Finally, we validate the results obtained on various synthetic as well as real-world traces.
