Optimistic No-regret Algorithms for Discrete Caching

Journal article (2023)

Authors

N. Mhaisen Networked Systems - EEMCS
Abhishek Sinha Tata Institute of Fundamental Research
Georgios Paschos Amazon.com Inc.
G. Iosifidis Networked Systems - EEMCS
Research Group
Networked Systems (EEMCS) (TU Delft)
Copyright: © 2023 N. Mhaisen, Abhishek Sinha, Georgios Paschos, G. Iosifidis
DOI
help_outline
https://doi.org/10.1145/3606376.3593561
Caching Optimistic learning Online algorithms Regret bounds
More Info
expand_more

Published Date

2023

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Software Technology

Research Group

Networked Systems

Abstract

We take a systematic look at the problem of storing whole files in a cache with limited capacity in the context of optimistic learning, where the caching policy has access to a prediction oracle. The successive file requests are assumed to be generated by an adversary, and no assumption is made on the accuracy of the oracle. We provide a universal lower bound for prediction-Assisted online caching and proceed to design a suite of policies with a range of performance-complexity trade-offs. All proposed policies offer sublinear regret bounds commensurate with the accuracy of the oracle. In this pursuit, we design, to the best of our knowledge, the first optimistic Follow-The-Perturbed leader policy, which generalizes beyond the caching problem. We also study the problem of caching files with different sizes and the bipartite network caching problem.