No-Regret Caching with Noisy Request Estimates
This work addresses caching in high-load or memory-constrained scenarios where exact request data is unavailable, representing an incremental improvement over existing methods.
The paper tackles the problem of caching with noisy request estimates, proposing the NFPL algorithm which achieves sublinear regret under specific conditions on the estimator, as validated experimentally against classic policies on synthetic and real traces.
Online learning algorithms have been successfully used to design caching policies with regret guarantees. Existing algorithms assume that the cache knows the exact request sequence, but this may not be feasible in high load and/or memory-constrained scenarios, where the cache may have access only to sampled requests or to approximate requests' counters. In this paper, we propose the Noisy-Follow-the-Perturbed-Leader (NFPL) algorithm, a variant of the classic Follow-the-Perturbed-Leader (FPL) when request estimates are noisy, and we show that the proposed solution has sublinear regret under specific conditions on the requests estimator. The experimental evaluation compares the proposed solution against classic caching policies and validates the proposed approach under both synthetic and real request traces.