强化学习增强的缓存:实验研究
采用盲算法和最优竞争算法相结合的混合算法在在线缓存中表现优于所有现有方法,而且结构更简单。此外,我们证明了对于这个问题,将 BlindOracle 与 LRU 相结合实际上是确定性算法中的最优解。
May, 2020
利用机器学习模型从过去和现在的数据中获得的预测,近期算法设计的先进方法已经显示出提高性能的潜力,并在预测失败时提供最坏情况保证,本文研究在线问题,着重于将学习问题与算法挑战相互整合,并设计了专为所需算法任务而量身定制的在线学习算法,通过细致设计的明确学习算法提出了优化总体性能的新算法,并证明了我们方法的潜力通过改进以前研究中建立的性能界限。
Mar, 2024
本篇论文提出了一种框架,通过将已有的在线算法与机器学习算法结合,可以在具有较低误差的情况下证明实现竞争比的提高。并将此框架应用于传统缓存问题中,通过修改 Marker 算法,利用机器学习算法的预测结果,实现较低的竞争比,即使是使用简单的预测也可以在真实环境中取得好的性能。
Feb, 2018
该论文研究了基于机器学习建议的在线缓存模型,提出了一种新的算法来解决缓存问题,该算法适用于低误差情况下的预测,具有低的竞争比率;通过改进算法和提供下限,有望进一步提高算法性能。
Oct, 2019
本文提出了一种缓存感知的强化学习方法(CARL),通过实时计算和缓存的联合优化来改善用户参与度,并通过实验表明 CARL 在考虑结果缓存时能显著提高用户参与度。CARL 已在快手应用完全推出,并服务于超过一亿用户。
Apr, 2024
本文提出了一种基于位置定制的缓存方案,使用线性模型估计未来内容命中率,并以此为基础提出了求解最优缓存策略的不依赖于训练的在线算法,实现了自适应缓存决策并达到了与最优策略相当的命中率。
Sep, 2018
介绍了一种算法设计范例 —— 基于学习预测器的算法,将在线学习技术应用于预测器学习、调整鲁棒性 - 一致性折中并绑定样本复杂度,在构建优美的预测器的同时,在二分图匹配、滑雪租赁、页面迁移和作业调度等多场景中优化了多个现有结果,且提供了第一批基于学习理论的担保。
Feb, 2022
设计在线算法,利用机器学习预测,以超越最坏情况范例,解决各种实际相关在线问题(如调度、缓存、聚类、滑雪租赁等)。通过研究设计具备多个专家的在线算法,以超越静态最佳专家的贪心基准。在新的动态基准中提出了具有 O(log K)性能保证的竞争算法,其中 K 是专家数量,适用于 0-1 在线优化问题。此外,我们的多专家方法提供了一种在线组合多个在线算法的新视角,这是在线算法研究社区长期的核心主题。
Dec, 2023
本文介绍了在学习增强的在线算法中使用回归技术来预测未来输入参数的方法,并在广义滑雪租赁、装箱问题、最小完成时间调度等一般在线搜索方案的背景下探讨了这种方法。通过在设计回归问题的损失函数中结合在线优化基准,我们显示了这种回归问题样本复杂度的近似上下界,并将我们的结果扩展到了不可知设置。
May, 2022