Efficient and Optimal No-Regret Caching Under Partial Observation

Online learning algorithms have been successfully used to design caching policies with sublinear regret in the total number of requests, with no statistical assumption about the request sequence. Most existing algorithms involve computationally expensive operations and require knowledge of all past requests. However, this may not be feasible in practical scenarios such as <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">femtocaching</i>, where a base station (BS) jointly decides the content of many edge caches and visibility of all requests at the BS requires constant communication between these caches and the BS. To capture this constraint, we study a single cache problem under a more restrictive setting, that we refer to as the Bernoulli Partial Observability (BPO) model, in which the caching policy only observes a request with probability <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$p$</tex-math> </inline-formula>, reflecting the fraction of requests forwarded from the edge caches to the BS in the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">femtocaching</i> example. We propose a policy, based on the classic online learning algorithm Follow-the-Perturbed-Leader (FPL), that achieves an asymptotically optimal regret bound of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathcal {O}(\sqrt {CT/p})$</tex-math> </inline-formula> under BPO in <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathcal {O}(1)$</tex-math> </inline-formula> amortized time complexity as <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$T$</tex-math> </inline-formula> goes to infinity, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$C$</tex-math> </inline-formula> is the cache size and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$T$</tex-math> </inline-formula> is the number of requests. Moreover, we show that our policy extends to bipartite caching albeit with a sublinear <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\alpha $</tex-math> </inline-formula>-regret for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\alpha =1-1/e$</tex-math> </inline-formula> and a higher computational cost. The experimental evaluation compares the proposed solution with classic caching policies and validates the proposed approach using both synthetic and real-world request traces.