Adaptive Caching with Follow The Perturbed Leader Replacement Policy

Abstract

Caching is a widely relevant problem in the world of ever-growing online traffic. In recent years, on-line learning methods have inspired algorithms that outperform more traditional, widely used policies such as LRU and LFU. Furthermore, some of these newly proposed policies have proven upper regret bounds, offering guarantees on arbitrary request se-quences. In this paper, we inspect one such policy named Follow the Perturbed Leader (FTPL), which we found to perform reasonably well among dif-ferent traces but showcases poor ability to adapt to changing file popularities. We propose a modifi-cation to the algorithm which addresses this issue, and although it comes with no performance guar-antees, we leverage the expert problem to maintain such a guarantee. More precisely, we utilize dif-ferent configurations of FTPL, including the one with a tight upper bound, as experts in an Incre-mentally Adaptive Weighted Majority (IAWM) al-gorithm. Our findings include simulation results on the MovieLens trace, as well as multiple syn-thetic traces, some with adversarial properties. We record these in a setting where a single user is con-nected to a single cache, which is then connected to a server, but also in a bipartite network where mul-tiple clients execute traces against multiple caches.