Regret-Optimal Learning for Minimizing Edge Caching Service Costs
Regret-Optimal Learning for Minimizing Edge Caching Service Costs
复制标题
DOI：
10.23919/wiopt56218.2022.9930560
复制
发表时间：
2022-09
期刊：
影响因子：
--
通讯作者：
Guocong Quan;A. Eryilmaz;N. Shroff
中科院分区：
文献类型：
--
作者：
Guocong Quan;A. Eryilmaz;N. Shroff
边缘缓存已被广泛实施，以有效地服务最终用户的数据请求。已经提出了许多边缘缓存策略来基于各种统计数据（包括数据流行度和丢失成本）自适应地更新缓存内容。然而，这些策略通常假设每个数据项的缺失成本是已知的，这在实际系统中并非如此。一种有前途的方法是使用在线学习来估计这些未知的失误成本。然而，现有技术不能直接应用，因为缓存问题具有传统学习设置中未涵盖的额外缓存容量和缓存更新约束。在这项工作中，我们通过开发一种新颖的边缘缓存策略来解决这些问题，该策略可以有效地学习不确定性错过成本，并且被证明是渐近最优的。我们首先得出可实现的遗憾的渐近下限。然后，我们设计了一种基于 Kullback-Leibler 置信下界（KL-LCB）的边缘缓存策略，该策略通过遵循“面对不确定性时保持乐观”的原则来自适应地学习随机缺失成本。通过采用一种新颖的分析来解释新的约束和环境的动态，我们证明了所提出的政策的遗憾与遗憾下限相匹配，从而显示出渐近最优性。此外，通过数值实验，我们证明了我们的策略相对于自然基准的性能改进。
Edge caching has been widely implemented to efficiently serve data requests from end users. Numerous edge caching policies have been proposed to adaptively update cache content based on various statistics including data popularities and miss costs. Nevertheless, these policies typically assume that the miss cost for each data item is known, which is not true in real systems. A promising approach would be to use online learning to estimate these unknown miss costs. However, existing techniques cannot be directly applied, because the caching problem has additional cache capacity and cache update constraints that are not covered in traditional learning settings. In this work, we resolve these issues by developing a novel edge caching policy that learns uncertainty miss costs efficiently, and is shown to be asymptotically optimal. We first derive an asymptotic lower bound on the achievable regret. We then design a Kullback-Leibler lower confidence bound (KL-LCB) based edge caching policy, which adaptively learns the random miss costs by following the “optimism in the face of uncertainty” principle. By employing a novel analysis that accounts for the new constraints and the dynamics of the setting, we prove that the regret of the proposed policy matches the regret lower bound, thus showing asymptotic optimality. Further, via numerical experiments we demonstrate the performance improvements of our policy over natural benchmarks.