  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.
