在部分观测条件下，高效且最优的无遗憾缓存策略

《IEEE Transactions on Networking》：Efficient and Optimal No-Regret Caching Under Partial Observation

针对 femtocaching 中缓存策略的通信限制问题，本文提出基于 Follow-the-Perturbed-Leader 的在线学习算法，在 Bernoulli 部分可观测模型下实现亚线性总请求数遗憾，并验证其在合成和真实请求数据上的有效性。

　　

摘要：

在线学习算法已被成功应用于设计缓存策略，使得总请求次数下的遗憾值（regret）呈亚线性增长，且无需对请求序列做出任何统计假设。大多数现有算法涉及计算成本较高的操作，并且需要了解所有过去的请求信息。然而，在实际场景中（如飞蜂窝缓存技术），这可能并不可行。在飞蜂窝缓存中，基站（BS）需要同时决定多个边缘缓存的内容，而要实现所有请求在基站的可见性，这些缓存与基站之间需要持续进行通信。为了考虑这一限制，我们研究了一个在更严格条件下的单一缓存问题，即所谓的伯努利部分可观测性（Bernoulli Partial Observability，简称BPO）模型。在该模型中，缓存策略仅以概率 p 观察到请求，这一概率反映了在飞蜂窝缓存示例中从边缘缓存转发到基站的请求比例。我们提出了一种基于经典在线学习算法“跟随扰动领导者”（Follow-the-Perturbed-Leader，简称FPL）的策略，在BPO模型下能够实现渐进最优的遗憾值界限，其表达式为 O(C/p?????√），其中 O(1 表示摊销时间复杂度，而 C 是缓存大小，T 是请求总数。此外，我们还证明了我们的策略可以扩展到双向缓存场景，尽管在这种情况下遗憾值仍呈亚线性增长，但代价是计算成本有所增加（具体为 α，其中 α=1?/）。实验评估将所提出的解决方案与经典缓存策略进行了比较，并通过合成数据和真实世界请求数据验证了该方法的有效性。