Learning to Cache and Caching to Learn: Regret Analysis of Caching Algorithms

Crucial performance metrics of a caching algorithm include its ability to quickly and accurately learn a popularity distribution of requests. However, a majority of work on analytical performance analysis focuses on hit probability after an asymptotically large time has elapsed. We consider an onlin...

Full description

Saved in:
Bibliographic Details
Published in:IEEE/ACM transactions on networking 2022-02, Vol.30 (1), p.18-31
Main Authors: Bura, Archana, Rengarajan, Desik, Kalathil, Dileep, Shakkottai, Srinivas, Chamberland, Jean-Francois
Format: Article
Language:English
Subjects:
Algorithms
Caching
Caching algorithms
Distance learning
IEEE transactions
Libraries
Machine learning
Measurement
multi armed bandits
Multi-armed bandit problems
online learning
Performance analysis
Performance measurement
Routing
Servers
Time-frequency analysis
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Crucial performance metrics of a caching algorithm include its ability to quickly and accurately learn a popularity distribution of requests. However, a majority of work on analytical performance analysis focuses on hit probability after an asymptotically large time has elapsed. We consider an online learning viewpoint, and characterize the "regret" in terms of the finite time difference between the hits achieved by a candidate caching algorithm with respect to a genie-aided scheme that places the most popular items in the cache. We first consider the Full Observation regime wherein all requests are seen by the cache. We show that the Least Frequently Used (LFU) algorithm is able to achieve order optimal regret, which is matched by an efficient counting algorithm design that we call LFU-Lite. We then consider the Partial Observation regime wherein only requests for items currently cached are seen by the cache, making it similar to an online learning problem related to the multi-armed bandit problem. We show how approaching this "caching bandit" using traditional approaches yields either high complexity or regret, but a simple algorithm design that exploits the structure of the distribution can ensure order optimal regret. We conclude by illustrating our insights using numerical simulations.
ISSN:1063-6692
1558-2566
DOI:10.1109/TNET.2021.3105880