Meta-Learning for Fast Adaption in Caching Networks

With the proliferation of short form high quality video content, it has become increasing important to find light weight and efficient edge caching algorithms that can quickly adapt to changing trends. In this context we study an online caching problem where a set of users are connected to a set of caches. The users request files from these caches over a time horizon. These requests arrive sequentially, the sequence of requests are divided into tasks that have a certain degree of similarity. This similarity is leveraged so that we may learn the best policy for a new task using a very small number of sequential requests. We characterize the task averaged regret incurred in this setting, showing an improvement of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$D/D^{*}$ </tex-math></inline-formula> where D is the diameter of the set of cache configurations and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$D^{*}$ </tex-math></inline-formula> is a measure of task similarity. We provide the same theoretical guarantees under both a distributed and smoothed setting. Further, we validate our algorithm on trace based data as well as on synthetic data sets. In the trace based data sets we do not assume any inherent task structure or estimate of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$D^{*}$ </tex-math></inline-formula>. These simulations show not only fast adaptation to new incoming tasks but also improved performance in highly non-stationary request settings.