2020/04/01 by Archana Bura, Desik Rengarajan, Bura, Archana +7
Decision Sciences · Computer Science · #Advanced Bandit Algorithms Research #Optimization and Search Problems #Caching and Content Delivery
paper · pdf · doi:10.48550/arxiv.2004.00472
Crucial performance metrics of a caching algorithm include its ability to\nquickly and accurately learn a popularity distribution of requests. However, a\nmajority of work on analytical performance analysis focuses on hit probability\nafter an asymptotically large time has elapsed. We consider an online learning\nviewpoint, and characterize the "regret" in terms of the finite time difference\nbetween the hits achieved by a candidate caching algorithm with respect to a\ngenie-aided scheme that places the most popular items in the cache. We first\nconsider the Full Observation regime wherein all requests are seen by the\ncache. We show that the Least Frequently Used (LFU) algorithm is able to\nachieve order optimal regret, which is matched by an efficient counting\nalgorithm design that we call LFU-Lite. We then consider the Partial\nObservation regime wherein only requests for items currently cached are seen by\nthe cache, making it similar to an online learning problem related to the\nmulti-armed bandit problem. We show how approaching this "caching bandit" using\ntraditional approaches yields either high complexity or regret, but a simple\nalgorithm design that exploits the structure of the distribution can ensure\norder optimal regret. We conclude by illustrating our insights using numerical\nsimulations.\n