提出一种自适应缓存策略，可在线应对恶意请求序列，实现次线性后悔。
On the Regret of Coded Caching with Adversarial Requests
- 基于扰动领袖追踪原则设计在线缓存策略
- 在任意请求序列下，后悔值为 O(√T)，优于线性增长
- 兼顾缓存更新次数限制，适合资源受限场景
我们将在在线学习框架下研究经典的编码缓存问题，其中请求按顺序到达，且在线策略可根据历史请求更新缓存内容。本文引入一种基于扰动领袖追踪（Follow-The-Perturbed-Leader）原则的缓存策略，并证明对于任意时间跨度 T 及任意请求序列，其相对于预先知晓请求序列的最优缓存策略，可实现次线性后悔值 Ω(√T)。这是首次在编码缓存设置中对对抗性后悔（adversarial regret）的研究。此外，我们还分析了切换成本问题：在无限制更新条件下，给出了算法期望缓存更新次数的上界；在仅允许在预设时间槽更新时，也提供了后悔值的上界。最后，通过真实数据集上的数值实验验证了理论结论的有效性。
原文摘要 · Abstract (English)
We study the well-known coded caching problem in an online learning framework, wherein requests arrive sequentially, and an online policy can update the cache contents based on the history of requests seen thus far. We introduce a caching policy based on the Follow-The-Perturbed-Leader principle and show that for any time horizon T and any request sequence, it achieves a sub-linear regret of \mathcal{O}(\sqrt(T) ) with respect to an oracle that knows the request sequence beforehand. Our study marks the first examination of adversarial regret in the coded caching setup. Furthermore, we also address the issue of switching cost by establishing an upper bound on the expected number of cache updates made by our algorithm under unrestricted switching and also provide an upper bound on the regret under restricted switching when cache updates can only happen in a pre-specified subset of timeslots. Finally, we validate our theoretical insights with numerical results using a real-world dataset
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。