在只能观察部分请求的情况下，实现高效低遗憾的缓存策略。
Efficient and Optimal No-Regret Caching under Partial Observation
- 基于随机扰动领袖算法，仅依赖部分历史请求做决策。
- 首次达到渐近最优遗憾界，且平均时间复杂度恒定。
- 适合基站等资源受限场景，对真实请求数据验证有效。
在线学习算法已被成功用于设计具有次线性遗憾的缓存策略，且无需对请求序列做统计假设。然而，大多数现有算法计算开销大，并需知晓所有历史请求，在蜂窝基站等实际场景中难以实现。为此，本文研究在仅能观测部分历史请求的更受限设置下的缓存问题，提出一种基于经典在线学习算法 Follow-the-Perturbed-Leader (FPL) 的随机缓存策略。该策略是首个在部分可观测请求设置下同时达到渐近最优遗憾界并保证渐近常数级均摊时间复杂度的方案。实验评估将该方法与经典缓存策略对比，基于合成及真实请求轨迹验证了其有效性。
原文摘要 · Abstract (English)
Online learning algorithms have been successfully used to design caching policies with sublinear regret in the total number of requests, with no statistical assumption about the request sequence. Most existing algorithms involve computationally expensive operations and require knowledge of all past requests. However, this may not be feasible in practical scenarios like caching at a cellular base station. Therefore, we study the caching problem in a more restrictive setting where only a fraction of past requests are observed, and we propose a randomized caching policy with sublinear regret based on the classic online learning algorithm Follow-the-Perturbed-Leader (FPL). Our caching policy is the first to attain the asymptotically optimal regret bound while ensuring asymptotically constant amortized time complexity in the partial observability setting of requests. The experimental evaluation compares the proposed solution against classic caching policies and validates the proposed approach under synthetic and real-world request traces.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。