Print Email Facebook Twitter Adaptive Caching with Follow The Perturbed Leader Replacement Policy Title Adaptive Caching with Follow The Perturbed Leader Replacement Policy Author Mäkelä, Mikkel (TU Delft Electrical Engineering, Mathematics and Computer Science) Contributor Iosifidis, G. (mentor) Si Salem, T. (graduation committee) Degree granting institution Delft University of Technology Programme Computer Science and Engineering Project CSE3000 Research Project Date 2022-06-24 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. To reference this document use: http://resolver.tudelft.nl/uuid:a0cf34e8-3598-4277-a800-0d486c186732 Part of collection Student theses Document type bachelor thesis Rights © 2022 Mikkel Mäkelä Files PDF mikke_makela_bachelor_thesis.pdf 859.82 KB Close viewer /islandora/object/uuid:a0cf34e8-3598-4277-a800-0d486c186732/datastream/OBJ/view