# Optimistic Online Caching with Recommendations

Naram Mhaisen1, George Iosifidis1, Douglas Leith2 2School of Computer Science
and Statistics, Trinity College Dublin, Ireland  1ENS Group, Delft University
of Technology, The Netherlands.

# Optimistic Learning for Online Caching Policies

Naram Mhaisen1, George Iosifidis1, Douglas Leith2 2School of Computer Science
and Statistics, Trinity College Dublin, Ireland  1ENS Group, Delft University
of Technology, The Netherlands.

# Optimistic Learning for Online Caching

Naram Mhaisen1, George Iosifidis1, Douglas Leith2 2School of Computer Science
and Statistics, Trinity College Dublin, Ireland  1ENS Group, Delft University
of Technology, The Netherlands.

# Online Caching with Optimistic Learning

Naram Mhaisen1, George Iosifidis1, Douglas Leith2 2School of Computer Science
and Statistics, Trinity College Dublin, Ireland  1ENS Group, Delft University
of Technology, The Netherlands.

###### Abstract

The design of effective online caching policies is an increasingly important
problem for content distribution networks, online social networks and edge
computing services, among other areas. This paper proposes a new algorithmic
toolbox for tackling this problem through the lens of _optimistic_ online
learning. We build upon the Follow-the-Regularized-Leader (FTRL) framework
which is developed further here to include predictions for the file requests,
and we design online caching algorithms for bipartite networks with fixed-size
caches or elastic leased caches subject to time-average budget constraints.
The predictions are provided by a content recommendation system that
influences the users viewing activity, and hence can naturally reduce the
caching network’s uncertainty about future requests. We prove that the
proposed optimistic learning caching policies can achieve _sub-zero_
performance loss (regret) for perfect predictions, and maintain the best
achievable regret bound $O(\sqrt{T})$ even for arbitrary-bad predictions. The
performance of the proposed algorithms is evaluated with detailed trace-driven
numerical tests.

##  I Introduction

Motivation. The quest for efficient data caching policies spans more than 50
years and remains today one of the most important research areas for wireless
and wired communication systems [1]. Caching was first studied in computer
systems where the aim was to decide which files to store in fast-accessible
memory segments (_paging_) [2]. Its scope was later expanded due to the
explosion of Internet web traffic [3] and the advent of content distribution
networks (CDNs) [4], and was recently revisited as a technique to improve the
operation of wireless networks through edge caches [5] and on-device caching
[6]. A common challenge in these systems is to design an online policy that
decides which files to store at a cache, without knowing the future file
requests, so as to maximize the cache _hits_ or some other more general cache-
related performance metric.

There is a range of online caching policies that tackle this problem under
different assumptions about the request arrivals. Policies such as the LFU and
LRU are widely-deployed, yet their performance deteriorates when the file
popularity is non-stationary, i.e., the requests are drawn from a time-varying
probability distribution [7, 8, 9]. This motivated modeling non-stationary
request patterns [10, 11] and optimizing accordingly the caching decisions
[12, 13]. Another line of work relies on techniques such as reinforcement
learning to estimate the request probabilities and make caching decisions [14,
15]; but typically these solutions do not scale nor offer optimality bounds.
Caching was studied as an online learning problem in [16, 17] for a single-
cache system; and in its more general form in [18] that proposed an online
gradient descent (OGD) caching policy. Interesting follow-up works include
sub-modular policies [19], online mirror-descent policies [20], and the
characterization of their performance limits [21]. The advantage of these
online learning-based caching policies is that they are scalable, do not
require training data, and their performance bounds are _robust_ to any
possible request pattern.

An aspect that has not been studied, however, is whether predictions about
future requests can improve the performance of these learning-based caching
policies. This is important in modern caching systems where most often the
users receive content viewing recommendations from a recommendation system
(_rec-sys_). For instance, recommendations are a standard feature in streaming
platforms such as YouTube and Netflix [22]; but also in online social network
platforms such as Facebook and Twitter, which moderate the users’ viewing
feeds [23]. Not surprisingly, the interplay between recommendations and
caching has attracted substantial attention and recent works devised static
joint policies aiming, e.g., to increase the cache hit rate or reduce the
routing costs by recommending to users already-cached files [24, 25, 26].

Changing vantage point, one can observe that since recommendations bias the
users towards viewing certain content files, they can effectively serve as
predictions of the forthcoming requests. This prediction information, if
properly leveraged, can hugely improve the efficacy of caching policies,
transforming their design from an online learning to an online optimization
problem. Nevertheless, the caching policy needs to adapt to the accuracy of
recommendations and the users propensity to follow them – which is typically
unknown and potentially time-varying. Otherwise, the caching performance might
as well deteriorate by following these misleading request _hints_. The goal of
this work is to tackle exactly this challenging new problem and _propose
online learning-based caching policies which leverage predictions (of unknown
quality) to achieve robust performance bounds_.

Contributions. Our approach is based on the theory of Online Convex
Optimization (OCO) that was introduced in [27] and has since been applied in
different problems [28]. The basic premise of OCO is that a learner (here the
caching system) selects in each slot $t$ a decision vector $x_{t}$ from a
convex set $\mathcal{X}$, without knowing the $t$-slot convex performance
function $f_{t}(x)$, that change with time. The learner’s goal is to minimize
the growth rate of _regret_
$R_{T}\\!=\\!\sum_{t=1}^{T}f_{t}(x^{\star})\\!-\\!f_{t}(x_{t})$, where
$x^{\star}\\!=\\!\arg\max_{x\in\mathcal{X}}\sum_{t=1}^{T}f_{t}(x)$ is the
benchmark solution designed with hindsight. The online caching problem fits
squarely in this setup, where $f_{t}(x)$ depends on the users requests and is
unknown when the caching is decided. And previous works [18, 21, 20] have
proved that OCO-based policies achieve $R_{T}\\!=\\!O(\sqrt{T})$, thus
ensuring $\lim_{T\rightarrow\infty}R_{T}/T\\!=\\!0$.

Different from these studies, we extend the learning model to include
predictions that are available through the content recommendations. Improving
the regret of learning policies via predictions is a relatively new area in
machine learning research. For instance [29] used predictions
$\widetilde{c}_{t}$ for the function gradient $c_{t}\\!=\\!\nabla
f_{t}(x_{t})$ with guaranteed quality, i.e.,
$c_{t}^{\top}\widetilde{c}_{t}\\!\geq\\!a\|c_{t}\|^{2}$, to reduce $R_{T}$
from $O(\sqrt{T})$ to $O(\log T)$; and [30] enhanced this result by allowing
some predictions to fail the quality condition. A different line of works uses
regularizing functions which enable the learner to adapt to the predictions’
quality [31], [32]. This approach is more promising for the caching problem
where the recommendations might be inaccurate, or followed by the users for
only arbitrary time windows.

Our approach relies on the Follow-The-Regularized-Leader (FTRL) algorithm [33]
which we extend with predictions that offer _optimism_ by reducing the
uncertainty about the next-slot functions. We first design a policy (OFTRL)
for the bipartite caching model [5], which generalizes the standard single
cache case. Theorem 1 proves that $R_{T}$ is proportional to prediction errors
($\|c_{t}\\!-\widetilde{c}_{t}\|^{2},\forall t$) diminishing to zero for
perfect predictions; while still meeting the best achievable bound
$O(\sqrt{T})$ [18, 21] even if all predictions fail. We continue with the
_elastic_ caching problem [34], where the system resizes the caches at each
slot based, e.g., on volatile storage leasing costs [35, 36, 34]. The aim is
to maximize the performance subject to a long-term budget constraint. This
places the problem in the realm of constrained-OCO [37, 38, 39, 40]. Using a
new saddle point analysis with predictions, we devise Theorem 2 which reveals
how $R_{T}^{(e)}$ and the budget violation $V_{T}^{(e)}$ depend on the caches
and prediction errors, and how we can prioritize one metric over the other
while achieving sublinear growth rates for both.

The above algorithms make no assumption about the predictions accuracy, which
might be high or low, or even alternate between these extremes (e.g., as user
behavior changes) in any unpredictable and frequent fashion. However, in many
cases, a rec-sys exhibits _consistent_ performance, namely its recommendations
are of similar quality within a certain time window; either accurately due to
recently trained model, or poorly due to e.g., distributional shift, see [41]
and references therein. Our final contribution is a meta-learning caching
framework that utilizes such consistent behavior in order to achieve
_negative_ regret while maintaining sublinear regret when the consistency
fails, see Theorem 3.

In summary, the contributions of this work are the following:

$\bullet$ Introduces an online learning framework for bipartite and elastic
caching networks that leverages predictions to achieve a constant _zero_
regret for perfect recommendations and a sub-linear $O(\sqrt{T})$ regret for
arbitrary bad recommendations.

$\bullet$ Introduces a meta-learning framework that can achieve _negative_
regret by leveraging consistently-performing rec-sys.

$\bullet$ Evaluates the policies using various request models and real
datasets [42] and compares them with key benchmarks.

The work presents conceptual innovations, i.e., using recommendations as
predictions for caching, and using different online caching algorithms in a
meta-learning algorithm; as well as technical contributions such as the new
optimistic FTRL algorithm with budget constraints (Theorem 2). While we focus
on data caching, the proposed algorithms can be directly applied to caching of
services on edge systems.

##  II System model and Problem Statement

Figure 1: System Model. A network of $\mathcal{J}$ caches serves file requests
from a set $\mathcal{I}$ of user locations. Unserved requests are routed to
the Root Server. Caching decisions are aided via the recommendations provided
by the rec-sys.

###  II-A Model Preliminaries

Network. The caching network includes a set of edge caches ${\cal
J}\\!=\\!\\{1,2,\dots,J\\}$ and a root cache indexed with 0, Fig. 1. The file
requests emanate from a set of non-overlapping user locations ${\cal
I}=\\{1,2,\dots,I\\}$. The connectivity between $\mathcal{I}$ and
$\mathcal{J}$ is modeled with parameters
$\ell\\!=\\!\big{(}\ell_{ij}\in\\{0,1\\}:i\\!\in\\!\mathcal{I},j\\!\in\\!\mathcal{J}\big{)}$,
where $\ell_{ij}\\!=\\!1$ if cache $j$ can be reached from location $i$. The
root cache is within the range of all users in $\mathcal{I}$. This is a
general non-capacitated bipartite model [43] that encompasses as a special
case the celebrated femtocaching model [5], and can be used both for wired and
wireless networks.

Requests. The system operation is time slotted,
$t\\!\\!=\\!\\!1,2,\dots,\\!T$. Users submit requests for obtaining files from
a library $\mathcal{N}$ of $N$ files with unit size; we note that the analysis
can be readily extended to files with different sizes. Parameter
$q^{t}_{ni}\\!\in\\!\\{0,1\\}$ indicates the submission of a request for file
$n\\!\in\\!\mathcal{N}$ by a user at location $i\\!\in\\!\mathcal{I}$ in the
beginning of slot $t$. At each slot we assume there is one request; i.e., the
caching decisions are updated after every request, as in LFU and LRU policies,
[44, 45]. Hence, the request process comprises successive vectors
$q_{t}\\!=\\!(q_{ni}^{t}\\!\in\\!\\{0,1\\}:n\\!\in\\!\mathcal{N},i\\!\in\\!\mathcal{I})$
from the set:

$\mathcal{Q}=\bigg{\\{}q\in\\{0,1\\}^{N\cdot
I}~{}\Big{|}~{}\sum_{n\in\mathcal{N}}\sum_{i\in\mathcal{I}}q_{ni}=1\bigg{\\}}.$

We make no assumptions for the request pattern; it might follow a fixed or
time-varying distribution that is unknown to the system; and can be even
selected strategically by an _adversary_ aiming to degrade the caching
operation. If a policy performs satisfactory under this model, it is ensured
to achieve (at least) the same performance for other request models.

Recommendations. There is a recommender system (_rec-sys_) that suggests up to
$K_{i}$ files to each user $i\\!\in\\!\mathcal{I}$, see [22] for the case of
Netflix. User $i$ requests a recommended file with a certain probability that
captures the user’s propensity to follow one of the recommendations. Unlike
prior works that consider these probabilities fixed [46, 24], we model them as
unknown and possibly time-varying. A key point in our approach is that the
content recommendations, if properly leveraged, can serve as predictions for
the next-slot user requests which are otherwise unknown. We denote with
$\tilde{q}_{t}$ the prediction for the request $q_{t}$ that the system will
receive at the beginning of slot $t$, and we assume that $\tilde{q}_{t}$ is
available at the end of slot $t\\!-\\!1$, i.e., when the rec-sys provides its
recommendations.

Caching. Each cache $j\\!\in\\!\mathcal{J}$ stores up to $C_{j}\\!<\\!N$
files, while the root cache stores the entire library, i.e.,
$C_{0}\\!\geq\\!N$. We also define $C\\!=\\!\max_{j\in\mathcal{J}}C_{j}$.
Following the standard femtocaching model [5], we perform caching using the
_Maximum Distance Separable_ (MDS) codes, where files are split into a fixed
number of $F$ chunks, which include redundancy chunks. A user can decode the
file if it receives any $F$-sized subset of its chunks. For large values of
$F$, the MDS model allows us to use continuous caching variables.111Large
files are composed of thousands of chunks and hence the rounding operation
induces practically negligible errors [43] Hence, we define the variable
$y_{nj}^{t}\\!\in\\![0,1]$ which denotes the portion of $F$ chunks of file
$n\\!\in\\!\cal N$ stored at cache $j\\!\in\\!\cal J$, and we introduce the
$t$-slot caching vector
$y_{t}\\!=\\!(y_{nj}^{t}:n\\!\in\\!\mathcal{N},j\\!\in\\!\mathcal{J})$ that
belongs to set:

$\mathcal{Y}=\bigg{\\{}y\in[0,1]^{N\cdot
J}~{}\Big{|}~{}\sum_{n\in\mathcal{N}}y_{nj}\leq
C_{j},~{}j\in\mathcal{J}\bigg{\\}}.$

Routing. Since each user location $i\in\mathcal{I}$ may be connected to
multiple caches, we need to introduce routing variables. Let $z_{nij}^{t}$
denote the portion of request $q_{ni}^{t}$ served by cache $j$. In the MDS
caching model the requests can be simultaneously routed from multiple caches
and, naturally, we restrict222This practical constraint is called the
_inelastic_ model and compounds the problem, cf. [21] for a comparison with
the simpler elastic model. the amount of chunks not to exceed $F$. Hence, the
$t$-slot routing vector
$z_{t}=(z_{nij}^{t}\\!\in\\![0,1]:n\\!\in\\!\mathcal{N},i\\!\in\\!\mathcal{I},j\\!\in\\!\mathcal{J})$
is drawn from:

$\mathcal{Z}=\bigg{\\{}z\in[0,1]^{N\cdot J\cdot
I}~{}\Big{|}~{}\sum_{j\in\mathcal{J}}z_{nij}\leq
1,~{}n\in\mathcal{N},i\in\mathcal{I}\bigg{\\}}.$

Requests that are not (fully) served by the edge caches $\mathcal{J}$ are
served by the root server that provides the missing chunks. This decision
needs not to be explicitly modeled as it is directly determined by the routing
vector $z_{t}$.

###  II-B Problem Statement

Cache Utility & Predictions. We use parameters $w_{nij}\in[0,w]$ to model the
system utility when delivering a chunk of file $n\\!\in\\!\cal N$ to location
$i\\!\in\\!\cal I$ from cache $j\\!\in\\!\cal J$, instead of using the root
server. This utility model can be used to capture bandwidth or delay savings,
and other edge-caching gains in wired or wireless networks. The caching
benefits can in general differ for each cache and user location, and may vary
with time as it is explained in the sequel. Note that the cache-hit
maximization problem is a special case of this more general setting [1]. To
streamline presentation we introduce vector
$x_{t}\\!=\\!(y_{t},z_{t})\in\mathbf{R}^{m}$, with $m\\!=\\!NIJ\\!+\\!NJ$, and
define the system utility in slot $t$ as:

$f_{t}(x_{t})=\sum_{n\in\mathcal{N}}\sum_{i\in\mathcal{I}}\sum_{j\in\mathcal{J}}w_{nij}q^{t}_{ni}z_{nij}^{t}\
,$ (1)

and we denote its gradient $c_{t+1}\\!=\\!\nabla f_{t+1}(x_{t+1})$. As it will
become clear, our analysis holds also for non-linear concave functions
$f_{t}(x)$; this generalization is useful in case, e.g., we wish to enforce
fairness in the dispersion of caching gains across the user locations [36].

The main challenge in online caching is the following: at the end of each slot
$t$ where we need to decide the cache configuration, the utility function
$f_{t+1}$ is not available. Indeed, this function depends on the next-slot
request $q_{t+1}$ that is revealed only after $y_{t+1}$ is fixed333In our
case, since the routing is directly shaped by the caching, this restriction
affects also $z_{t+1}$., see [18, 21, 17]. Besides, this is also the timing of
the LRU/LFU policies [44, 45]. However, the recommendations provided to users
can be used to form a predicted request $\widetilde{q}_{t+1}$. For example,
the caching system can set $\widetilde{q}_{\hat{n}\hat{i}}^{t+1}\\!=\\!1$ and
$\widetilde{q}_{ni}^{t+1}\\!=\\!0,\forall(n,i)\neq(\hat{n},\hat{i})$, where
$(\hat{n},\hat{i})$ is the request with the highest predicted
probability444Note that our caching policy is orthogonal to the mechanism that
maps the recommendations to predictions.. Then, we can use
$\widetilde{q}_{t+1}$ to create a prediction for the next slot function
$\widetilde{f}_{t+1}$, or for its gradient $\widetilde{c}_{t+1}$, which
suffices to solve the caching problem, as we will see.

Benchmark. In such learning problems, it is important to understand the
learning objective that our learning algorithm aims to achieve. If we had
access to an oracle for the requests $\\{q_{t}\\}_{t=1}^{T}$ (and utility
parameters) we could devise the utility-maximizing static caching and routing
policy $x^{\star}=(y^{\star},z^{\star})$, by solving the following convex
optimization problem:

$\displaystyle\mathbb{P}_{1}:\quad\max_{x}\,\,\,\,\,\,$
$\displaystyle\sum_{t=1}^{T}f_{t}(x)$ (2) s.t. $\displaystyle\,\,z_{nij}\leq
y_{nj}\ell_{ij},\quad i\in\mathcal{I},j\in\mathcal{J},n\in\mathcal{N},$ (3)
$\displaystyle\,\,z\in\mathcal{Z},\,\,\,\,y\in\mathcal{Y},$ (4)

where constraints (3) ensure the routing decisions for each requested file use
only the edge caches that store enough chunks of that file. And let us define
the set of constraints
$\mathcal{X}=\mathcal{Y}\cap\mathcal{Z}\cap\\{\eqref{eq:opt1b}\\}$, which is
compact and convex.

This hypothetical solution $x^{\star}$ can be designed only with _hindsight_
and is the benchmark for evaluating our online learning policy $\pi$. To that
end, we use the metric of regret:

$\displaystyle
R_{T}(\pi)=\sup_{\\{f_{t}\\}_{t=1}^{T}}\left[\sum_{t=1}^{T}f_{t}\big{(}x^{\star}\big{)}-\sum_{t=1}^{T}f_{t}\big{(}x_{t}\big{)}\right],$
(5)

which quantifies the performance gap of $\pi$ from $x^{\star}$, for any
possible sequence of requests or, equivalently, functions $\\{f_{t}\\}_{t}$.
Our goal is to find a policy that achieves sublinear regret,
$R_{T}(\pi)\\!=\\!o(T)$, thus ensuring the average performance gap will
diminish as $T$ grows. This policy, similar to other online policies, decides
$x_{t+1}$ at the end of each slot $t$ using the previous utility functions
$\\{f_{\tau}\\}_{\tau=1}^{t}$ and the next-slot prediction $\tilde{f}_{t+1}$
which is made available through the rec-sys.

##  III Optimistic Bipartite Caching

Unlike recent caching solutions that rely on Online Gradient Descent (OGD)
[18] or on the Follow-the-Perturbed-Leader (FTPL) policy [21], our approach
draws from the _Follow-The-Regularized-Leader_ (FTRL) policy, cf. [47]. A key
element in our proposal is the _optimism_ emanating from the availability of
predictions, namely the content recommendations that are offered to users by
the rec-sys in each slot.

Let us begin by defining the proximal regularizers555A proximal regularizer is
one that induces a proximal mapping for the objective function; see [48, Ch.
6.1] for the formal definition.:

$\displaystyle r_{0}(x)=\bm{I}_{\mathcal{X}}(x),\quad
r_{t}(x)=\frac{\sigma_{t}}{2}\|x-x_{t}\|^{2},\,\,t\geq 1$ (6)

where $\|\cdot\|$ is the Euclidean norm, and $\bm{I}_{\mathcal{X}}(x)\\!=\\!0$
if $x\\!\in\\!\mathcal{X}$ and $\infty$ otherwise. We apply the following
regularizing parameters:

$\displaystyle\sigma_{t}=\sigma\left(\sqrt{h_{1:t}}-\sqrt{h_{1:t-1}}\right),\quad\text{with}\quad
h_{t}=\|c_{t}-\widetilde{c}_{t}\|^{2}$ (7)

where $\sigma\\!\geq\\!0$, $c_{t}\\!=\\!\nabla f_{t}(x_{t})$, and we used the
shorthand notation $h_{1:t}\\!=\\!\sum_{i=1}^{t}h_{i}$ for the aggregate
prediction errors during the first $t$ slots. The basic step of the algorithm
is the update:

$\displaystyle
x_{t+1}=\arg\min_{x\in\mathbf{R}^{m}}\Big{\\{}r_{0:t}(x)-(c_{1:t}+\widetilde{c}_{t+1})^{\top}x\Big{\\}},$
(8)

which calculates the decision vector based on past observations $c_{1:t}$, the
aggregate regularizer $r_{0:t}(x)$ and the prediction $\widetilde{c}_{t+1}$
(see Fig. 2). The update employs the negative gradients as it concerns a
maximization problem, cf. [47]. Henceforth, we refer to (8) as the
_optimistic_ FTRL (OFTRL) update.

Policy $\pi_{obc}$ is outlined in Algorithm 1. In each iteration, OBC solves a
convex optimization problem, (8), involving a projection on the feasible set
$\mathcal{X}$ (via $r_{0}(x)$). For the latter, one can rely on fast-
projection algorithms specialized for caching, e.g., see [18]; while it is
possible to obtain a closed-form solution for the OFTRL update for linear
functions.

Figure 2: A decision step for OBC. When a request $q_{t}$ arrives, the file is
routed based on the current cache configuration. The caches are updated using
the observed utility $f_{t}(x_{t})$ and the new prediction from the
recommender.

We quantify next the performance of Algorithm 1.

######  Theorem 1.

Algorithm OBC ensures the regret bound: $\displaystyle R_{T}\leq
2\sqrt{2(1\\!+JC)}\sqrt{\sum_{t=1}^{T}\|c_{t}-\widetilde{c}_{t}\|^{2}}$

###### Proof.

We start from [32, Theorem 1] which proved that a proximal OFTRL update with
regularizer $r_{0:t}(x)$ that is 1-strongly-convex w.r.t. some norm
$\|\cdot\|_{(t)}$ yields regret:

$\displaystyle R_{T}\leq
r_{1:T}(x^{\star})+\sum_{t=1}^{T}\|c_{t}-\widetilde{c}_{t}\|_{(t),\star}^{2},\,\,\,\,\forall
x^{\star}\in\cal X.$ (9)

Now, $r_{1:t}$ is 1-strongly-convex w.r.t. norm
$\|x\|_{(t)}=\sqrt{\sigma_{1:t}}\|x\|$ which has dual norm
$\|x\|_{(t),\star}=\|x\|/\sqrt{\sigma}_{1:t}$. Using the regularization
parameter (7), we get $\sigma_{1:t}=\sigma\sqrt{h_{1:t}}$, and replacing all
the above into (9) we get:

$\displaystyle R_{T}$
$\displaystyle\leq\frac{\sigma}{2}\sum_{t=1}^{T}\left(\sqrt{h_{1:t}}-\sqrt{h_{1:t-1}}\right)\|x^{\star}-x_{t}\|^{2}+\sum_{t=1}^{T}\frac{h_{t}}{\sigma\sqrt{h_{1:t}}}$
$\displaystyle\leq\frac{\sigma}{4}\sum_{t=1}^{T}\frac{h_{t}\|x^{\star}-x_{t}\|^{2}}{\sqrt{h_{1:t}}}+\sum_{t=1}^{T}\frac{h_{t}}{\sigma\sqrt{h_{1:t}}},$

where we used the concavity of square root
$\sqrt{a}\\!-\\!\sqrt{b}\\!\leq\\!(a\\!-\\!b)/2\sqrt{b}$ for the last step.
Then, we can set $\sigma\\!=\\!2/D_{\mathcal{X}}$ where $D_{\mathcal{X}}$ is
the Euclidean diameter of $\mathcal{X}$, namely $\forall x,x_{t}\\!\in\\!\cal
X$ holds:

$\displaystyle\|x-x_{t}\|^{2}=\sum_{n,j}(y_{nj}-y_{nj}^{t})^{2}+\sum_{n,i,j}(z_{nij}-z_{nij}^{t})^{2}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{n,j}|y_{nj}-y_{nj}^{t}|+\sum_{n,i,j}|z_{nij}-z_{nij}^{t}|\stackrel{{\scriptstyle(b)}}{{\leq}}2(JC+1)\triangleq
D_{\mathcal{X}}^{2}$

where $(a)$ holds as $y_{nj},z_{nij}\\!\in\\![0,1],\forall n,i,j$; $(b)$ holds
by the triangle inequality and definitions of
$\mathcal{Y},\mathcal{Z},\mathcal{Q}$; and $C\\!\triangleq\\!\max_{j}C_{j}$.
Finally, using [49, Lem. 3.5] to get
$\sum_{t}h_{t}/\sqrt{h_{1:t}}\\!\leq\\!2\sqrt{h_{1:t}}$ and expanding
$h_{1:t}$ we arrive at the result. ∎

1 Input: $\\{\ell_{ij}\\}_{(i,j)}$; $\\{C_{j}\\}_{j}$; $\mathcal{N}$;
$x_{1}\\!\in\\!\mathcal{X}$; $\sigma=2/D_{\mathcal{X}}$.

2Output: $x_{t}=(y_{t},z_{t})$, $\forall t$.

3for  _ $t=1,2,\ldots$ _ do

4 Route request $q_{t}$ according to configuration $x_{t}$

5 Observe system utility $f_{t}(x_{t})$

6 Observe the new prediction $\widetilde{c}_{t+1}$

7 Update the regularizer $r_{0:t}(x)$ using (6)-(7)

8 Calculate the new policy $x_{t+1}$ using (8)

end for

Algorithm 1 Optimistic Bipartite Caching ($\pi_{obc}$)

Discussion. Theorem (1) shows that the regret does not depend on the library
size $N$ and is also modulated by the quality of the content recommendations;
accurate predictions tighten the bound, and in the case of perfect prediction,
i.e., when users follow the recommendations, we get a negative regret
$R_{T}\\!\leq\\!0,\forall T$, which is much stronger than the sub-linear
growth rates in other works [18, 50]. On the other hand, for worst-case
prediction, it is $\|c_{t}-\widetilde{c}_{t}\|^{2}\leq 2w^{2}$, thus
$R_{T}\leq 4w\sqrt{2(JC+1)}\sqrt{T}=O(\sqrt{T})$; i.e., the regret is at most
a constant factor worse than the regret of those policies that do not
incorporate predictions666The factor is $2$ compared to the “any-time” version
of the bound that do not use predictions, and $2\sqrt{2}$ compared to those
that assume a known $T$., regardless of the predictions’ quality. Thus, OBC
offers an efficient and safe approach for incorporating predictions in cases
where we are uncertain about their accuracy, e.g., either due to the quality
of the rec-sys or the behaviour of users.

Another key point is that the _utility parameters might vary with time_ as
well. Indeed, replacing
$w_{t}=(w_{nij}^{t}\\!\leq\\!w,n\\!\\!\in\\!\\!\mathcal{N},i\\!\\!\in\\!\\!\mathcal{I},j\\!\\!\in\\!\\!\mathcal{J})$
in $f_{t}(x_{t})$ does not affect the analysis nor the bound. This is
important when the caching system employs a wireless network where the link
capacities vary, or when the caching utility changes. Similarly, for edge
computing and caching services, the utility of each computation or service
might vary substantially across users and time. Parameters $w_{t}$ can be even
unknown to the caching system when $x_{t}$ is decided, exactly as it is with
$q_{t}$, and they can be predicted either using the rec-sys or other side
information (e.g., channel measurements).

##  IV Optimistic Caching in Elastic Networks

We extend our analysis to _elastic_ caching networks where the caches can be
resized dynamically. Such architectures are important for two reasons.
Firstly, there is a growing number of small-size content providers that
implement their services by leasing storage on demand from infrastructure
providers [51]; and secondly, CDNs often resize their caches responding to the
time-varying user needs and operating expenditures [52].

We introduce the $t$-slot price vector
$s_{t}\\!=\\!(s_{j}^{t}\\!\leq\\!s,j\\!\in\\!\mathcal{J})$, where $s_{j}^{t}$
is the leasing price per unit of storage at cache $j$ in slot $t$, and $s$ its
maximum value. In the general case, these prices may change arbitrarily over
time, e.g., because the provider has a dynamic pricing scheme or the
electricity cost changes [35, 36]; hence the caching system has access only to
$s_{t}$ at each slot $t$. We denote with $B_{T}$ the budget the system intends
to spend during a period of $T$ slots for leasing cache capacity. The
objective is to maximize the caching gains while satisfying the constraint:

$\displaystyle\sum_{t=1}^{T}g_{t}(x_{t})=\sum_{t=1}^{T}\sum_{j\in\mathcal{J}}\sum_{n\in\mathcal{N}}s_{j}^{t}y_{nj}^{t}-B_{T}\leq
0.$ (10)

In particular, the new benchmark problem in this case is:

$\displaystyle\mathbb{P}_{2}:\quad\max_{x\in\mathcal{X}}\sum_{t=1}^{T}f_{t}(x)\,\,\,\,\,\,\text{s.t.}\,\,\,\,\,\,\eqref{eq:opt1b},\,\,\,\,\,\sum_{t=1}^{T}g_{t}(x)\leq
0,$ (11)

which differs from $\mathbb{P}_{1}$ due to the leasing constraint.

Indeed, in this case the regret is defined as:

$\displaystyle
R_{T}^{(e)}(\pi)=\sup_{\\{f_{t},g_{t}\\}_{t=1}^{T}}\left[\sum_{t=1}^{T}f_{t}\big{(}x^{\star}\big{)}-\sum_{t=1}^{T}f_{t}\big{(}x_{t}\big{)}\right],$
(12)

where
$x^{\star}\\!\in\\!\mathcal{X}_{e}\triangleq\\{x\in\mathcal{X}\mid\eqref{eq:opt1b},g_{t}(x)\leq
0,\forall t\\}$, i.e., $x^{\star}$ is a feasible point of $\mathbb{P}_{2}$
with the additional restriction to satisfy $g_{t}(x)\\!\leq\\!0$ in every
slot. In the definition of $\mathcal{X}$, $C$ now denotes the maximum leasable
space. Learning problems with time-varying constraints are notoriously hard to
tackle, see impossibility result in [53], and hence require such additional
restrictions on the selected benchmarks. We refer the reader to [37] for a
related discussion, and to [38, 39] for more competitive benchmarks. These
ideas are directly applicable to our OFTRL framework. For instance, the
analysis follows directly for the $K$-slot benchmark of [38] where
$\sum_{\tau=t}^{t+K}g_{t}(x^{\star})\\!\leq\\!0,\forall\tau$, instead of
$g_{t}(x^{\star})\\!\leq\\!0,\forall t$. Finally, apart from $R_{T}^{(e)}$, we
need also to ensure sublinear growth rate for the budget violation:

$V_{T}^{(e)}=\sum_{t=1}^{T}g_{t}(x_{t}).$

To tackle this new problem we follow a saddle point analysis, which is new in
the context of OFTRL.

We first define a Lagrangian-type function by relaxing the budget constraint
and introducing the dual variable $\lambda\geq 0$:

$\displaystyle\mathcal{L}_{t}(x,\lambda)\\!=\\!\frac{\sigma_{t}}{2}\|x\\!-x_{t}\|^{2}\\!-f_{t}(x_{t})\\!+\lambda
g_{t}(x_{t})\\!-\frac{\lambda^{2}}{a_{t}}.$ (13)

The last term is a non-proximal regularizer for the dual variable; and we use
$a_{t}\\!=\\!at^{-\beta}$, where parameter $\beta\\!\in\\![0,1)$ can be used
to prioritize either $R_{T}^{(e)}$ or $V_{T}^{(e)}$. The main ingredients of
policy $\pi_{oec}$ are the saddle-point iterations:

$\displaystyle\lambda_{t+1}=\arg\max_{\lambda\geq
0}\left\\{-\frac{\lambda^{2}}{a_{t+1}}+\lambda\sum_{i=1}^{t}g_{i}(x_{i})\right\\},$
(14)
$\displaystyle\\!\\!x_{t+1}\\!=\\!\arg\min_{x\in\mathbf{R}^{m}}\Big{\\{}\\!r_{0:t}(x)\\!+\\!\big{(}\sum_{i=1}^{t+1}\\!\lambda_{i}s_{i}-c_{1:t}\\!-\widetilde{c}_{t+1}\big{)}^{\top}\\!x\Big{\\}}$
(15)

and its implementation is outlined in Algorithm 2. Note that we use the same
regularizer for the primal variables $x_{t}$, while $\lambda_{t}$ modulates
the caching decisions by serving as a _shadow price_ for the average budget
expenditure.

1 Input: $\\{\ell_{ij}\\}_{(i,j)}$, $\\{C_{j}\\}_{j}$, $\mathcal{N}$,
$\lambda_{1}\\!=\\!0$, $x_{1}\\!\in\\!\mathcal{X}_{e}$,
$a_{t}\\!=\\!at^{-\beta}$

2Output: $x_{t}=(y_{t},z_{t})$, $\forall t$.

3for  _ $t=1,2,\ldots$ _ do

4 Route request $q_{t}$ according to configuration $x_{t}$

5 Observe system utility $f_{t}(x_{t})$ and cost $g_{t}(x_{t})$

6 Update the budget parameter $\lambda_{t+1}$ using (14)

7 Update the regularizer $r_{0:t}(x)$ using (6)-(7)

8 Observe prediction $\widetilde{c}_{t+1}$ and price $s_{t+1}$

9 Calculate the new policy $x_{t+1}$ using (15)

end for

Algorithm 2 Optimistic Elastic Caching ($\pi_{oec}$)

The performance of Algorithm OEC is characterized next.

######  Theorem 2.

Algorithm OEC ensures the bounds: $\displaystyle R_{T}^{(e)}\leq
D_{\mathcal{X}}\sqrt{\\!\sum_{t=1}^{T}\|c_{t}\\!-\widetilde{c}_{t}\|^{2}}\\!+\frac{a(sJC)^{2}}{2(1\\!-\\!\beta)}T^{1-\beta}$
$\displaystyle
V_{T}^{(e)}\leq\sqrt{\\!\frac{2D_{\mathcal{X}}T^{\beta}}{a}\sqrt{\\!\sum_{t=1}^{T}\|c_{t}\\!-\widetilde{c}_{t}\|^{2}}+\frac{T(sJC)^{2}}{1\\!-\beta}\\!-\\!\frac{2R_{T}^{(e)}T^{\beta}}{a}}$

###### Proof.

Observe that the update in (15) is similar to (8) but applied to the
Lagrangian in (13) instead of just the utility, and the known prices when
$x_{t+1}$ is decided represent perfect prediction for $g_{t}(x)$. Using
Theorem 1 with $c_{t}\\!-\\!\lambda_{t}s_{t}$ instead of $c_{t}$, and
$\widetilde{c}_{t}\\!-\\!\lambda_{t}s_{t}$ instead of $\widetilde{c}_{t}$, we
can write:

$\displaystyle\sum_{t=1}^{T}\\!\Big{(}f_{t}(x^{\star})-f_{t}(x_{t})+\lambda_{t}g_{t}(x_{t})-\lambda_{t}g_{t}(x^{\star})\Big{)}\\!\leq\\!D_{\mathcal{X}}\sqrt{h_{1:T}},$

and rearrange to obtain:

$\displaystyle R_{T}^{(e)}\leq
D_{\mathcal{X}}\sqrt{h_{1:T}}+\sum_{t=1}^{T}\lambda_{t}g_{t}(x^{\star})-\sum_{t=1}^{T}\lambda_{t}g_{t}(x_{t}).$
(16)

For the dual update (14), we can use the non-proximal-FTRL bound [47, Theorem
1] to write:

$\displaystyle\\!\\!\\!\\!-\\!\sum_{t=1}^{T}\lambda_{t}g_{t}(x_{t})\\!+\\!\lambda\sum_{t=1}^{T}g_{t}(x_{t})\\!\leq\\!\frac{\lambda^{2}}{a_{T}}\\!+\\!\frac{1}{2}\sum_{t=1}^{T}a_{t}g_{t}^{2}(x_{t}).$
(17)

Since $g_{t}(x^{\star})\\!\leq\\!0,\forall t$ and combining (16), (17) we get:

$\displaystyle\\!\\!R_{T}^{(e)}\\!\leq\\!D_{\mathcal{X}}\sqrt{h_{1:T}}\\!-\lambda\\!\sum_{t=1}^{T}g_{t}(x_{t})\\!+\\!\frac{\lambda^{2}}{a_{T}}\\!+\\!\frac{1}{2}\sum_{t=1}^{T}\\!a_{t}g_{t}^{2}(x_{t}).$
(18)

Setting $\lambda\\!=\\!0$, using the identity
$\sum_{t=1}^{T}at^{-\beta}\\!\leq\\!aT^{1-\beta}/(1\\!-\\!\beta)$ and the
bound $g_{t}(x_{t})\\!\leq\\!sJC$, we prove the $R_{T}^{(e)}$ bound. Using:

$\displaystyle\frac{a_{T}}{2}\left[\sum_{t=1}^{T}g_{t}(x_{t})\right]^{2}=\sup_{\lambda\geq
0}\left[\sum_{t=1}^{T}g_{t}(x_{t})\lambda-\frac{\lambda^{2}}{2a_{T}}\right],$

we can replace this term to (18) and write:

$\displaystyle\frac{a_{T}}{2}(V_{T}^{(e)})^{2}\leq
D_{\mathcal{X}}\sqrt{h_{1:T}}+\frac{a(sJC)^{2}}{2-2\beta}T^{1-\beta}-R_{T}^{(e)}.$

Rearranging and taking the square root yields $V_{T}^{(e)}$ bound. ∎

Discussion. The worst-case bounds in Theorem 2 arise when the predictions are
failing. In that case, we have
$\|c_{t}\\!-\\!\widetilde{c}_{t}\|^{2}\\!\leq\\!2w^{2}$ and use the bound
$-R_{T}^{(e)}\\!\\!\\!=\\!\\!\\!O(T)$ for the last term of $V_{T}^{(e)}$, to
obtain $R_{T}^{(e)}\\!\\!\\!=\\!\\!\\!O(T^{\kappa})$, with
$\kappa\\!=\\!\max\\{1/2,1\\!-\\!\beta\\}$ while
$V_{T}^{(e)}\\!=\\!O(T^{\phi})$, with $\phi\\!=\\!\frac{1+\beta}{2}$. Hence,
for $\beta\\!\\!=\\!\\!1/2$ we achieve the desired sublinear rates
$R_{T}^{(e)}\\!\\!\\!=\\!\\!O(\sqrt{T}),V_{T}^{(e)}\\!\\!\\!=\\!\\!O(T^{3/4})$.
However, when the rec-sys manages to predict accurately the user preferences,
the performance of $\pi_{oec}$ improves substantially as the first terms in
each bound are eliminated. Thus, for bounded $T$, we practically halve the
regret and violation bounds.

It is also interesting to observe the tension between $V_{T}^{(e)}$ and
$R_{T}^{(e)}$, which is evident from the $V_{T}^{(e)}$ bound and the condition
$-R_{T}^{(e)}\\!=\\!O(T)$. The latter refers to the upper bound of the
_negative_ regret, thus when it is consistently satisfied (i.e., for all $T$),
we obtain an even better result: $\pi_{oec}$ _outperforms_ the benchmark.
Another likely case is when $-R_{T}^{(e)}\\!=\\!O(\sqrt{T})$, i.e., the policy
does not outperform the benchmark at a rate larger than $\sqrt{T}$. Then,
Theorem 2 yields $R_{T}^{(e)}\\!=\\!O(T^{\kappa})$ with
$\kappa\\!=\\!\max\\{1/2,1-\beta\\}$ while $V_{T}^{(e)}\\!=\\!O(T^{\phi})$
with $\phi\\!=\\!\max\\{1/2,1/4+\beta/2\\}$. Hence, for $\beta\\!=\\!1/2$ the
rates are reduced to
$R_{T}^{(e)}\\!=\\!O(\sqrt{T}),V_{T}^{(e)}\\!=\\!O(\sqrt{T})$.

It is worth emphasizing that $\pi_{oec}$ can be readily extended to handle
additional budget constraints such as time-average routing costs or average
delays. We can also use a budget-replenishment process where in each slot $t$
the budget increases by an amount of $b_{t}$ units, e.g., based on
advertisement revenues in $t\\!-\\!1$, which might be even unknown in slot
$t$.

##  V Caching with non-volatile predictions

We now introduce a different approach on modeling recommendations as
predictions, which, in cases of consistent prediction performance, delivers
better regret. Namely, we model the problem of online caching using the
_experts model_ , see [54]. The first expert represents a robust learner
(referred to as _pessimistic_) and proposes an FTRL-based caching policy
without any predictions. The second expert represents an _optimistic_ learner
and implements a policy that always caches the file predicted to be requested.
To streamline the presentation, we present the results using a single cache
scenario (hence using only $y$ below), but it will become clear that this
method can be readily extended to caching networks.

Figure 3: A decision step for XC. Experts’ utilities are used to update the
weights $u$. The new caching decisions are then the combination of the
experts’ proposals. The optimistic decisions are updated based only on
predictions from rec-sys. The pessimistic decisions are updated based only on
past requests.

Formally, the pessimistic expert proposes caching actions
$\\{y^{(p)}_{t}\\}_{t}$ according to step (8), but with setting
$\widetilde{c}_{t}\\!\\!=\\!\\!0$ for the regulization parameter $\sigma_{t}$
in (7). Its regret w.r.t the optimal-in-hindsight caching configuration
$y^{\star}=\operatorname*{argmax}_{y\in\mathcal{Y}}c_{1:T}^{\top}y$ is denoted
with $R_{T}^{(p)}$. On the other hand, the optimistic expert proposes actions
$\\{y^{(o)}_{t}\\}_{t}$ according to the linear program:

$\displaystyle y^{(o)}_{t+1}=\operatorname*{argmax}_{y\in\mathcal{Y}}\ \
{\widetilde{c}_{t+1}}^{\top}\ y,$ (19)

and we denote its regret with $R_{T}^{(o)}$. The optimistic expert represents
a high-risk high-reward policy; $R_{T}^{(o)}$ is linear in the worst case
predictions and negative linear for perfect predictions. In contrast, the
pessimistic expert is more robust as it is not affected by bad predictions,
but guarantees only a sub-linear regret. We aim to have the best of both
worlds and design an algorithm that, in the best case, is able to obtain
negative regret, while being worse only by a constant factor than the
pessimistic expert in the general case.

Unlike $\pi_{obc}$ and $\pi_{ec}$, the predictions are not appended to the
FTRL step itself but rather treated independently through the optimistic
expert. The challenge is to meta-learn which of the two experts to rely upon.
To that end, we will be using Online Gradient Ascent (OGA) to learn how to
combine the experts’ proposed caching vectors $y^{(p)}_{t}$ and $y^{(o)}_{t}$.
The decisions of the meta-learner are then these combination weights
$u_{t}=(u^{(p)}_{t},u^{(o)}_{t})$, drawn from the 2-dimensional simplex set
$\Delta$, (see Fig. 3). The weights are learned through the OGA step:

$\displaystyle
u_{t+1}=\mathcal{P}_{\Delta}\big{\\{}u_{t}+\delta_{t}l_{t}\big{\\}},$ (20)

where $\mathcal{P}$ is the projection operator, $\delta_{t}$ is the OGA
learning rate and $l_{t}=(l_{t}^{(p)},l_{t}^{(o)})$ is the $t$-slot
performance vector for the experts, i.e.,
$l_{t}^{(p)}={c_{t}}^{\top}{y^{(p)}_{t}}$, and
$l_{t}^{(o)}={c_{t}}^{\top}{y^{(o)}_{t}}$. The caching decision is the convex
combination of experts’ proposals:

$\displaystyle y_{t+1}=u^{(p)}_{t+1}\ y^{(p)}_{t+1}+u^{(o)}_{t+1}\
y^{(o)}_{t+1}.$ (21)

Thus, $y_{t+1}$ is still a feasible caching policy. The steps are shown in
Algorithm 3, and the following theorem bounds the regret of the _caching
decisions_ $\\{y_{t}\\}_{t}$.

1 Input: $C$; $y_{1}\\!\in\\!\mathcal{Y}$; $\sigma=2/D_{\mathcal{Y}}$.

2Output: $y_{t}$, $\forall t$.

3for  _ $t=1,2,\ldots$ _ do

4 Serve request $q_{t}$ according to configuration $y_{t}$

5 Observe utilities $f_{t}(y_{t}^{(p)}),f_{t}(y_{t}^{(o)})$

6 Update $r_{0:t}(x)$ using (6)-(7) with $\widetilde{c}_{t+1}\\!=\\!0$

7 Calculate pessimistic expert’s proposal $y^{(p)}_{t+1}$ as in (8)

8 Observe the prediction $\widetilde{q}_{t+1}$, and calculate
$\widetilde{c}_{t+1}$

9 Calculate optimistic expert’s proposal $y^{(o)}_{t+1}$ using (19)

10 Calculate the new weights $u_{t+1}$ using (20)

11 Calculate the new policy $y_{t+1}$ using (21)

end for

Algorithm 3 Experts Caching ($\pi_{xc}$)

######  Theorem 3.

Algorithm XC ensures the bound $R^{(xc)}_{T}$=
$\displaystyle\\!\sum_{t=1}^{T}\\!{c_{t}}^{\top}\\!(y^{\star}\\!-\\!y_{t})\leq
2w\sqrt{2T}+\\!A,\ A\\!\in\\![-wT,2w\sqrt{2CT}]$

###### Proof.

First, we relate the regret of the combined caching decisions to that of the
expert selection,

$\displaystyle\\!R^{(xc)}_{T}\\!$
$\displaystyle=\\!\sum_{t=1}^{T}\\!{c_{t}}^{\top}{y^{\star}}\\!-\\!{c_{t}}^{\top}(u^{(p)}_{t}y^{(p)}_{t}\\!+\\!u^{(o)}_{t}y^{(o)}_{t})\\!=\\!\sum_{t=1}^{T}{c_{t}}\\!^{\top}\\!{y^{\star}}\\!-\\!{l_{t}}\\!^{\top}\\!{u_{t}}$
$\displaystyle=\sum_{t=1}^{T}{c_{t}}^{\top}{y^{\star}}-{l_{t}}^{\top}{u^{\star}}+{l_{t}}^{\top}{u^{\star}}-{l_{t}}^{\top}{u_{t}}$
$\displaystyle=R_{T}^{(u)}+\min\left\\{R_{T}^{(p)},R_{T}^{(o)}\right\\},$ (22)

where $R_{T}^{(u)}$ is the regret for the _expert selection weights $u$_:
$R_{T}^{(u)}=\sum_{t=1}^{T}{l_{t}}^{\top}{u^{\star}}-{l_{t}}^{\top}{u_{t}}$.
(22) holds because $u^{\star}\\!\\!=\\!\operatorname*{argmax}_{u}\
{l_{1:t}}\\!\\!^{\top}\\!{u}\\!={e^{k}}$, where $k\in\left\\{(p),(o)\right\\}$
and $e^{k}$ is standard basis vector. Thus, we have that

$\displaystyle l_{1:t}^{\top}\
u^{\star}=max\bigg{\\{}\sum_{t=1}^{T}c_{t}^{\top}y^{(p)}_{t},\sum_{t=1}^{T}c_{t}^{\top}y^{(o)}_{t}\bigg{\\}}.$
(23)

Now, we write the expressions for the terms in (22). $R_{T}^{(p)}$ can be
bounded in the same manner as Theorem $1$ with prediction vectors
$\widetilde{c}_{t}=0$, and substituting an upper bound $w$ for $\|c_{t}\|$:

$\displaystyle R_{T}^{(p)}$ $\displaystyle\leq
2w\mathcal{D}_{\mathcal{Y}}\sqrt{T}\leq 2w\sqrt{2CT}.$ (24)

$R_{T}^{(o)}$ is hard to calculate as it depends on both, prediction
$\\{\tilde{c}_{t}\\}_{t}$, and the relationship between $c_{1:t}$ and $c_{t}$.
However, we can easily deduce lower and upper bounds. Since $c_{t}$ and
$\tilde{c}_{t}$ represent the utility of one request to a file, each term of
the optimistic regret can be maximally $w$. Hence, we have that
$R_{T}^{(o)}\\!\in\\![-wT,wT]$, and:

$\displaystyle\min\left\\{R_{T}^{(p)},R_{T}^{(o)}\right\\}\in[-wT,2w\sqrt{2CT}].$
(25)

For $R_{T}^{(u)}$, we use the OGA bound [55, Thm. 4.14] tailored to the
simplex decision set. Using $\eta_{t}^{(u)}\\!=\\!\frac{1}{w\sqrt{t}}$, and
$\|l_{t}\|\\!\leq\\!w\sqrt{2}$:

$\displaystyle R_{T}^{(u)}$ $\displaystyle\leq 2w\sqrt{2T}$ (26)

Substituting (25) and (26) in (22) gives the bound. ∎

Discussion. The regret in Theorem 3 can now be _strictly_ negative for perfect
predictions, which is tighter than OBC. In general, however, the regret can be
an additive factor of $2w\sqrt{2T}$ (the first term) worse compared to
OBC777Note that the OBC bound in Theorem $1$ reduces to $2w\sqrt{2CT}$ under
the single-cache settings adopted in this section., i.e., still $O(\sqrt{T})$.
Overall, the bound is essentially the aggregate of two terms, the first,
$2w\sqrt{2T}$, is a worst-case bound for finding the best expert, i.e.,
$R_{T}^{(u)}$. In cases where the best expert is obvious, e.g., due to
consistent predictions which make $l_{t}$ similar, it would be a loose upper
bound and its actual value is negligible compared to the second term. The
second term is the regret of the best expert,
$\min\left\\{R_{T}^{(p)},R_{T}^{(o)}\right\\}$, and falls in a range that
depends on predictions’ quality at each step. Thus, if the optimistic expert
is better than the best-in-hindsight solution, this $\min$ term will be
negative.

##  VI Performance evaluation

Figure 4: Utility in the single cache model under different prediction quality
levels in (a) Zipf requests with $\zeta=1.2$, (b) YouTube request traces [42].

We evaluate $\pi_{obc}$, $\pi_{oec}$ and $\pi_{xc}$ under different request
patterns and predictions modes; and we benchmark them against $x^{\star}$ and
the OGD policy [18] that outperforms other state-of-the-art policies [44, 45].
We observe that when reasonable predictions are available, the proposed
policies have an advantage, and under noisy predictions, they still reduce the
regret at the same rate with OGD, as proven in the Theorems. First, we compare
$\pi_{obc}$ and $\pi_{xc}$ against OGD [18] in the single cache case. We then
study $\pi_{obc}$ for the bipartite model and $\pi_{oec}$ with the presence of
budget constraints. We consider two requests scenarios, stationary Zipf
requests (with parameter $\zeta\\!=\\!1.2$) and an actual trace from the
dataset in [42]. Predictions alternate between accurate and adversarial (i.e.,
requesting the recommended file vs. any other file, respectively), for $\tau$
time step in each mode. While low values of $\tau$ represent an unstable
performance, the high value of $\tau$ is meant to approximate the consistent
performance of practical rec-sys. We also experiment with random accuracies
where at each $t$, the prediction is accurate with probability $\rho$.

Single Cache Scenarios. We set $w\\!=\\!1$ to study the cache hit rate
scenario. Fig. 4.a shows the performance of $\pi_{obc}$ and $\pi_{xc}$ for a
library of $N\\!=\\!10^{4}$ files and cache size $C\\!=\\!100$. At each slot,
we plot the attained average utility, $\frac{1}{T}\sum_{t=1}^{T}f_{t}(x_{t})$,
for each policy and the best static cache configuration _until that slot_ ,
i.e., we find the best in hindsight888unlike [18] that calculates $x^{\star}$
for the largest $t$, we use $x_{t}^{\star}$ for each $t$. Thus, the gap
between any policy and BHS at $t$ is the policy’s average regret $R_{t}/t$.
for each $t$.

In the simulated requests case (Fig. 4.a), $\pi_{obc}$ achieves negative
regret through the experiment for $\tau\\!\\!=\\!\\!10^{3}$ and a regret that
is $57.1\%$ better than that of the OGD for $\tau\\!\\!=\\!\\!1$. Such an
advantage for the former is due to having more time steps with accurate
predictions. $\pi_{xc}$ also maintains negative regret that even outperforms
$\pi_{obc}$ when $\tau\\!=\\!10^{3}$. This is because the stable performance
of experts allows the policy to efficiently find the best expert and stick
with it within each time window. However, a value of $\tau\\!\\!=\\!\\!1$
induces frequent switching between the two experts in $\pi_{xc}$: the
performance of the optimistic expert alternate between $0$ and $1$, while that
of pessimistic expert is in the range ($0.6,0.7$). Hence, $\pi_{xc}$ is
inclined to place some weight on the opt. expert at one step, only to retract
and suffer a greater loss at the following one had it stayed with the full
weight on the pess. expert. Due to the additional regret caused by such
frequent switching, $\pi_{obc}$ performs better when $\tau=1$.

For the trace used in Fig. 4.b, $\pi_{obc}$ maintains the advantage over OGD
in both prediction modes. Regarding $\pi_{xc}$, the alternation of the
performance of the opt. expert (when $\\!\tau\\!\\!=\\!\\!1$) no longer
induces a switching between the experts since even when the opt. expert
performs poorly (gets $0$ reward), there is a high chance, especially
initially, that the pess. perform similarly999The poor performance of the
pess. expert here is due to more uniform, unpredictable, request vectors.
Hence, finding that the opt. expert is better is still easy (due to
differences in their utility). Thus, in this trace, $\pi_{xc}$ performs well
with both $\tau$ values.

Figure 5: Attained utility in the bipartite model under different prediction
quality levels in (a) Zipf requests with $\zeta=1.2$, (b) YouTube request
traces [42].

Bipartite Networks. We consider next a bipartite graph with $3$ caches and $4$
user locations, where the first two locations are connected with caches $1$
and $2$, and the rest are connected to caches $2$ and $3$. The utility vector
is $w_{n}\\!=\\!(1,2,100),\forall i,j$, thus an efficient policy places
popular files on cache $3$. This is the setup used in [18] that we adopt here
to make a fair comparison. For the stationary scenario, we consider a library
of $N\\!=\\!500$ files and $C\\!=\\!50$. For the traces scenario, files with
at least $10$ requests are considered, forming a library of $N\\!=\\!456$
files, and we keep $C\\!=\\!50$. In this experiment, we assume that at each
time step, the user follows the recommendation with probability $\rho$. The
location of each request is selected uniformly at random. Similar to the
single-cache case, we plot the average utility of the online policies and the
best static configuration _until each $t$_.

Scenario $1$ in Fig. 5.a shows the effect of good predictions as OBC maintains
utility within $5.32\%$ of BHS’s utility after $t\\!\\!=\\!\\!2.5k$. Even when
the recommendations are not followed, OBC preserves the sublinear regret,
achieving a gap of $27.4\%$ and $10.36\%$ for $t\\!\\!=\\!\\!1k$ and
$t\\!\\!=\\!\\!5k$, respectively. Akin patterns appear in the second scenario
(Fig. 5.b) but with lower utilities across all policies due to the more spread
requests. Recall that the area between a policy and BHS is the average regret.

Figure 6: Attained utility and constraints violations for OEC, OGD with (a):
Zipf requests with $\zeta=1.5$ and (b): YouTube request traces [42].

Next, we consider the case of budget constraint and evaluate $\pi_{oec}$ for
scenario 1, Fig. 6.a, and scenario 2, Fig. 6.b. The prices at each slot are
generated uniformly at random in the normalized range $[0,1]$, and the
available budget is generated randomly
$b_{t}\\!\\!=\\!\\!\mathcal{N}(0.5,0.05)\\!\\!\times\\!\\!10$ for scenario 1,
and $b_{t}\\!\\!=\\!\\!\mathcal{N}(0.5,0.05)\\!\\!\times\\!\\!30$ for scenario
2, i.e., enough for approx. $10$ and $30$ files, respectively. Such tight
budgets magnify the role of dual variables and allow us to test the constraint
satisfaction. The benchmark $x^{\star}$ is computed once for the _full time
horizon_ , and its utility is plotted for each $t$. In both scenarios, we note
that the constraint violation for all policies is approximately similar,
fluctuating during the first few slots and then stabilizing at zero. Hence, we
plot it for one case.

Concluding, we find that $\pi_{oec}$ can even outperform the benchmark since
it is allowed to violate the constraints at some time slots, provided that the
constraints are eventually satisfied, which occurs either due to strict
satisfaction or due to having an ample subsidy at some slots. Moreover, in the
first scenario (Fig.6.a), the good predictions enable OEC to outperform
$x^{\star}$ by $42.5\%$ after observing all requests ($T\\!\\!=\\!\\!5K$).
OGD, and OEC with noisy predictions attain utility units improvement of
$26.5\%$, $39.3\%$, respectively, over the BHS. In the second scenario
(Fig.6.b) , the good forecast enables a utility gain of $67.1\%$ compared to,
$-11.3\%$, and $49.7\%$ for OGD and OEC with noisy prediction, respectively.
We stress that the algorithms scale for very large libraries $\mathcal{N}$,
and the only bottleneck is finding $x^{\star}$ which involves the horizon $T$,
see also [18, 21]; this is not required in real systems.

##  VII Conclusions

The problem of online caching is timely with applications that extend beyond
content delivery to edge computing [1]. This work proposes a new suite of
caching policies that leverage predictions obtained from content-viewing
recommendations to achieve negative regret w.r.t to an ideal (unknown)
benchmark. As recommender systems permeate online content platforms, such
policies can play an essential role in optimizing the caching efficacy. We
identified and built upon this new connection. The framework is scalable and
robust to the quality of recommendations, improves previously known caching
regret bounds [18, 20, 21], and opens new directions. Among them, the design
of optimistic policies for uncoded caching is perhaps the most promising.

## References

  * [1] G. Paschos _et al._ , “The Role of Caching in Future Communication Systems and Networks,” _IEEE JSAC_ , vol. 36, no. 6, 2018.
  * [2] L. A. Belady, “A Study of Replacement Algorithms for Virtual Storage Computers,” in _IBM Systems Journal_ , vol. 5, no. 2, 1966.
  * [3] C. Aggarwal, et al., “Caching on the World Wide Web,” _IEEE Trans. on Knowledge and Data Eng._ , vol. 11, no. 1, pp. 94–107, 1999.
  * [4] J. Kangasharju, J. Roberts, and K. Ross, “Object replication strategies in content distribution networks,” _Computer Communications_ , vol. 25, no. 4, pp. 376–383, 2002.
  * [5] N. Golrezaei, et al., “FemtoCaching: Wireless Video Content Delivery through Distributed Caching Helpers,” Mar. 2012, pp. 1107–1115.
  * [6] ——, “Femtocaching and D2D collaboration: A New Architecture for Wireless Video Distribution,” _IEEE Communications Magazine_ , vol. 51, no. 4, April 2013.
  * [7] D. D. Sleator and R. E. Tarjan, “Amortized efficiency of list update and paging rules,” _Commun. ACM_ , pp. 202–208, 1985.
  * [8] P. R Jelenkovic, and X. Kang, “Characterizing the Miss Sequence of the LRU Cache,” _ACM SIGMETRICS Performance Evaluation Review_ , vol. 36, no. 2, pp. 119–121, 2008.
  * [9] D. Lee, et al., “On the Existence of a Spectrum of Policies that Subsumes the Least Recently Used (LRU) and Least-Frequently-Used (LFU) Policies,” _Proc. of ACM SIGMETRICS_ , 1999.
  * [10] S. Traverso _et al._ , “Temporal locality in today’s content caching: Why it matters and how to model it,” _ACM SIGCOMM_ , 2013.
  * [11] F. Olmos, B. Kauffmann, A. Simonian, and Y. Carlinet, “Catalog Dynamics: Impact of Content Publishing and Perishing on the Performance of a LRU Cache,” in _ITC_ , 2014.
  * [12] M. Leconte _et al._ , “Placing dynamic content in caches with small population,” in _IEEE INFOCOM_ , 2016.
  * [13] S.-E. Elayoubi and J. Roberts, “Performance and cost effectiveness of caching in mobile access networks,” in _ACM ICN_ , 2015.
  * [14] S. O. Somuyiwa et al., “A Reinforcement-Learning Approach to Proactive Caching in Wireless Networks,” _IEEE JSAC_ , vol. 36, no. 6, 2018.
  * [15] A. Sadeghi, F. Sheikholeslami, and G. B. Giannakis, “Optimal and Scalable Caching for 5G Using Reinforcement Learning of Space-Time Popularities,” _IEEE J. of S. Top. in Signal Proc._ , pp. 180–190, 2018.
  * [16] G. Sascha _et al._ , “Regret minimization for online buffering problems using the weighted majority algorithm.” in _COLT_ , 2010.
  * [17] T. Lykouris and S. Vassilvitskii, “Competitive caching with machine learning advice,” in _ICML_ , 2018.
  * [18] G. Paschos, A. Destounis, L. Vignieri, and G. Iosifidis, “Learning to Cache with No Regret,” in _Proc. of IEEE INFOCOM_ , 2019.
  * [19] Y. Li, T. Si Salem, G. Neglia, and S. Ioannidis, “Online caching networks with adversarial guarantees,” _Proc. ACM Meas. Anal. Comput. Syst._ , vol. 5, no. 3, dec 2021.
  * [20] T. Si Salem, G. Neglia, and S. Ioannidis, “No-Regret Caching via Online Mirror Descent,” in _Proc. of IEEE ICC_ , 2021.
  * [21] R. Bhattacharjee, S. Banerjee, and A. Sinh, “ Fundamental Limits of Online Network-Caching,” in _Proc. of ACM Sigmetrics_ , 2020.
  * [22] C. A. Gomez-Uribe, and N. Hunt, “The Netflix Recommender System: Algorithms, Business Value, and Innovation,” _ACM Trans. on Management Information Systems_ , vol. 6, no. 4, 2016.
  * [23] X. Amatriain, “Building Industrial-scale Real-world Recommender Systems,” _in Proc. of ACM RecSys_ , 2012.
  * [24] L. E. Chatzieleftheriou, et al., “Jointly Optimizing Content Caching and Recommendations in Small Cell Networks,” _IEEE Trans. on Mobile Computing_ , vol. 18, no. 1, pp. 125–138, 2019.
  * [25] Y. Fu, et al., “Revenue Maximization for Content-Oriented Wireless Caching Networks (CWCNs) With Repair and Recommendation Considerations,” _IEEE Trans. Wirel. Commun._ , vol. 20, no. 1, 2021.
  * [26] M. Sheng , W. Teng, X. Chu, J. Li , K. Guo, and Z. Qiu, “Cooperative Content Replacement and Recommendation in Small Cell Networks,” _IEEE Trans. Wirel. Commun._ , vol. 20, no. 3, pp. 2049–2063, 2021.
  * [27] M. Zinkevich, “Online convex programming and generalized infinitesimal gradient ascent,” in _ICML_ , 2003.
  * [28] E. Hazan, _Introduction to Online Convex Optimization_. Found. Trends Optim. , 2016, vol. 2, no. 3-4.
  * [29] O. Dekel, A. Flajolet, N. Haghtalab, and P. Jaillet, “Online Learning with a Hint,” in _Proc. of NIPS_ , 2017.
  * [30] A. Bhaskara, A. Cutkosky, R. Kumar, and M. Purohit, “Online learning with imperfect hints,” in _Proc. of ICML_ , 2020.
  * [31] S. Rakhlin and K. Sridharan, “Optimization, learning, and games with predictable sequences,” in _Proc. of NIPS_ , 2013.
  * [32] M. Mohri and S. Yang, “Accelerating Online Convex Optimization via Adaptive Prediction,” in _Proc. of AISTATS_ , 2016.
  * [33] S. Shalev-Shwartz, and Y. Singer, “A Primal-dual Perspective of Online Learning Algorithms,” _Machine Learning_ , vol. 69, no. 2-3, 2007.
  * [34] E. Nygren, R. K. Sitaraman, and J. Sun, “The akamai network: A platform for high-performance internet applications,” _SIGOPS Oper. Syst. Rev._ , vol. 44, no. 3, pp. 2–19, Aug. 2010. [Online]. Available: http://doi.acm.org/10.1145/1842733.1842736
  * [35] A. Sadeghi, F. Sheikholeslami, A. G. Marques, and G. B. Giannakis, “Reinforcement Learning for Adaptive Caching With Dynamic Storage Pricing,” _IEEE JSAC_ , vol. 37, no. 10, pp. 2267–2281, 2019.
  * [36] J. Kwak, G. Paschos, and G. Iosifidis, “Dynamic cache rental and content caching in elastic wireless cdns,” in _Proc. of WiOpt_ , 2018.
  * [37] T. Chen, Q. Ling, and G. B. Giannakis, “An online convex optimization approach to proactive network resource allocation,” _IEEE Trans. on Signal Processing_ , vol. 65, no. 24, 2017.
  * [38] N. Liakopoulos, A. Destounis, G. Paschos, T. Spyropoulos, and P. Mertikopoulos, “Cautious regret minimization: Online optimization with long-term budget constraints,” in _Proc. of ICML_ , 2019.
  * [39] V. Valls, G. Iosifidis, D. Leith, and L. Tassiulas, “Online convex optimization with perturbed constraints: Optimal rates against stronger benchmarks,” in _Proc. of AISTATS_ , 2020.
  * [40] Y. Xinlei et al., “Distributed Online Convex Optimization With Time-Varying Coupled Inequality Constraints,” _IEEE Trans. on Signal Processing_ , vol. 68, 2020.
  * [41] Y. Zhang et al., “How to retrain recommender system? a sequential meta-learning method,” in _Proc. 43rd International ACM SIGIR_. New York, NY, USA: Association for Computing Machinery, 2020, p. 1479–1488.
  * [42] M. Z. et al., “Watch Global, Cache Local: YouTube Network Traffic at a Campus Network: Measurements and Implications,” in _Multimedia Computing and Networking 2008_ , vol. 6818, 2008.
  * [43] G. Paschos, G. Iosifidis, and G. Caire, “Cache Optimization Models and Algorithms,” _FnT in Communications and Information Theory_ , vol. 16, no. 3-4, pp. 156–345, 2020.
  * [44] A. Giovanidis and A. Avranas, “Spatial multi-LRU: Distributed caching for wireless networks with coverage overlaps,” _arXiv:1612.04363_ , 2016.
  * [45] E. Leonardi, et al., “Implicit Coordination of Caches in Small Cell Networks under Unknown Popularity,” _IEEE JSAC_ , vol. 36, no. 6, 2018.
  * [46] D. Tsigkari, et al., “User-centric Optimization of Caching and Recommendations in Edge Cache Networks,” in _IEEE WoWMoM_ , 2020.
  * [47] H. B. McMahan, “A survey of algorithms and analysis for adaptive online learning,” _J. of Machine Learning Res._ , vol. 18, pp. 1–50, 2017.
  * [48] A. Beck, “First Order Methods in Optimization,” _MOS-SIAM Series on Optimization_ , 2017.
  * [49] P. Auer, N. Cesa-Bianchi, and C. Gentile,, “Adaptive and Self-confident On-line Learning Algorithms,” _Journal of Computer and System Sciences_ , vol. 64, no. 1, pp. 48–75, 2002.
  * [50] G. S. Paschos, A. Destounis, and G. Iosifidis, “Online convex optimization for caching networks,” _IEEE/ACM Transactions on Networking_ , vol. 28, no. 2, pp. 625–638, 2020.
  * [51] “Amazon Elastic CDN Service - ElastiCache.” [Online]. Available: https://aws.amazon.com/elasticache/
  * [52] Juniper Networks, “The Elastic CDN Solution,” Solution Brief, Dec. 2014. [Online]. Available: https://www.juniper.net/assets/kr/kr/local/pdf/solutionbriefs/3510532-en.pdf
  * [53] S. Mannor et al., “Online Learning with Sample Path Constraints,” _J. of Machine Learning Res._ , vol. 10, 2009.
  * [54] S. Shalev-Shwartz _et al._ , “Online learning and online convex optimization,” _FnT in Machine Learning_ , vol. 4, no. 2, pp. 107–194, 2011\.
  * [55] F. Orabona, “A modern introduction to online learning,” 2021. [Online]. Available: https://arxiv.org/abs/1912.13213