This paper explores algorithms to optimize networked caching, where requests for files can be handled by a local cache instead of a remote server. Caches work collaboratively to prevent redundant caching, and each new batch of file requests is used to update the entire network. Data is cached in an integral manner, meaning that only discrete files or chunks can be stored, not fractions of them. Bipartite networks are studied, though the proposed model supports arbitrary network topologies. The approach is based upon an Online Mirror Descent (OMD) policy, which has been shown to have sublinear regret in single cache scenarios.

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.