# No-Regret Caching with Noisy Request Estimates

Younes Ben Mazziane, Francescomaria Faticanti, Giovanni Neglia, Sara Alouf

► To cite this version:

Younes Ben Mazziane, Francescomaria Faticanti, Giovanni Neglia, Sara Alouf. No-Regret Caching with Noisy Request Estimates. IEEE VCC 2023 - IEEE Virtual Conference on Communications, Nov 2023, New York (ONLINE), United States. pp.341-346, 10.1109/VCC60689.2023.10474978 . hal-04318435v2

HAL Id: hal-04318435

https://hal.science/hal-04318435v2

Submitted on 24 Dec 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
No-Regret Caching with Noisy Request Estimates

Younes Ben Mazziane, Francescomaria Faticanti, Giovanni Neglia, Sara Alouf

Inria, Université Côte d'Azur

Sophia Antipolis, France

firstname.lastname@inria.fr

*Abstract*—Online learning algorithms have been successfully used to design caching policies with regret guarantees. Existing algorithms assume that the cache knows the exact request sequence, but this may not be feasible in high load and/or memory-constrained scenarios, where the cache may have access only to sampled requests or to approximate requests' counters. In this paper, we propose the Noisy-Follow-the-Perturbed-Leader (NFPL) algorithm, a variant of the classic Follow-the-Perturbed-Leader (FPL) when request estimates are noisy, and we show that the proposed solution has sublinear regret under specific conditions on the requests estimator. The experimental evaluation compares the proposed solution against classic caching policies and validates the proposed approach under both synthetic and real request traces.

*Index Terms*—Caching, Online learning, Follow-the-Perturbed-Leader.

# I. INTRODUCTION

Caching techniques are extensively employed in computer systems, serving various purposes such as accelerating CPU performance [1] and enhancing user experiences in content delivery networks (CDNs) [2]. The primary objective of a caching system is to carefully choose files for storage in the cache to maximize the proportion of file requests that can be fulfilled locally. This approach effectively minimizes the dependence on remote server retrievals, which can be costly in terms of delay and network traffic. The presence of caching systems facilitates more efficient data delivery in network traffic and leads to enhanced overall system performance, especially with the widespread adoption of traffic-intensive applications such as virtual and augmented reality [3], or edge video analytics [4].

Caching policies have been thoroughly investigated under numerous assumptions concerning the statistical regularity of file request processes [5], [6]. However, real-world request sequences tend to deviate from these theoretical models, especially when aggregated over small geographic areas [7]. This deviation has inspired the exploration of online learning algorithms, beginning with the work of Paschos et al. [8], which applied the Online Convex Optimization (OCO) framework [9] to caching. These algorithms exhibit robustness to varying request process patterns, as they operate under the assumption that requests may be generated by an adversary.

In this context, the main metric of interest is the *regret*, which is the difference between the cost—e.g., the number of cache misses—incurred by a given online caching algorithm and the cost of the optimal static cache allocation with hindsight, i.e., with knowledge of the future requests over a fixed

time horizon. In this framework, the primary objective is to design no-regret algorithms, i.e., online policies whose regret grows sublinearly with the length of the time horizon [8].

Several online caching policies have been proposed in the literature, drawing on well-known online algorithms such as Online Gradient Descent (OGD) [8], Follow-the-Regularized-Leader (FRL) [10] or Follow-the-Perturbed-Leader (FPL) [11]. The latter is especially promising, as cache updates can be performed without the need for computationally intensive projection operations over the set of feasible cache states.

Caching policies, including no-regret ones, make admission and eviction decisions based on information from the request sequence. This can include factors such as the number of past requests for each file or a list of the most recently requested files. However, when dealing with a vast file catalog and/or a high request rate, a cache might have to depend on noisy information. For instance, limited availability of high-speed memory can necessitate the use of approximate counters based on hash functions [12], [13]. Alternatively, request sampling might be employed to decrease the frequency of counter updates [14].

Surprisingly, much of the existing literature on no-regret caching policies overlooks these practical constraints. Typically, these studies operate under the assumption that caches have exact knowledge of the request sequences or of its summaries. A notable exception is the work presented in [15]. However, it exclusively examines the scenario in which the cache is only aware of requests for files it already contains.

In this paper, we bridge this gap by adapting the FPL algorithm—renowned for its computational efficiency and no-regret properties—to manage noisy request estimates. Our main contributions are the following:

* We modify the FPL algorithm to handle noisy request estimates and prove that, under specific conditions on the estimator, the algorithm maintains sublinear regret. We refer to this extended version as Noisy-Follow-the-Perturbed-Leader (NFPL).

* We propose two variants of the NFPL algorithm for the caching problem, namely, NFPL-Fix and NFPL-Var, where the requests estimator uses sampling. We prove that NFPL-Fix and NFPL-Var have sublinear regret.

* We prove a new regret bound for the classic FPL caching policy that is independent of the catalog size.

* We show through experimental analysis the advantage of the NFPL algorithm over classical caching policies.
We also evaluate the impact of the sampling rate on the performance of NFPL-Fix and NFPL-Var.

The paper is organized as follows. We describe the system assumptions and give background details in Section II. The extension of FPL to deal with noisy requests and its analysis are described in Section III. Experimental results are presented in Section IV. Finally, Section V concludes the paper.

## II. SYSTEM DESCRIPTION AND BACKGROUND

### A. Caching Problem: Model and Notation

We consider a single-cache system in which file requests for a catalog $\mathcal{I}$ with $N$ files can either be served locally by a cache with finite capacity $C$ or, in the case of a file miss, by a remote server.

**Cache state.** The local cache has a capacity $C \in \{1, \dots, N\}$ and stores files in their entirety. The cache state at time $t$ is represented by the vector $\mathbf{x}_t = [x_{t,i}]_{i \in \mathcal{N}}$, which indicates the files missing in the cache; that is, $x_{t,i} = 1$ if and only if file $i$ is not stored in the cache at time $t$. A feasible cache allocation is then represented by a vector in the set:

$$ \mathcal{X} = \left\{ \mathbf{x} \in \{0, 1\}^N \middle| \sum_{i=1}^{N} x_i = N - C \right\}. \quad (1) $$

**Cache updates.** Although caching policies are often assumed to update their state after each request, in high request rate regimes or when cache updates are computationally or communicationally expensive, the cache may update its state after receiving a batch of $B$ requests [16]. We study caching policies in this more general setting and consider a time-slotted operation. At each time slot $t = 1, \dots, T$, $B$ requests are collected from the users and the cache state is updated. The request process is represented as a sequence of vectors $\mathbf{r}_t = (r_{t,i} \in \mathbb{N} : i \in \mathcal{I}) \forall t$, where $r_{t,i}$ is the number of requests received for file $i$ in the $t$-th batch. Then, each vector belongs to the set:

$$ \mathcal{B} = \left\{ \mathbf{r} \in \mathbb{N}^N \middle| \sum_{i=1}^{N} r_i = B \right\}. \quad (2) $$

**Cost.** At each time slot $t$, the cache pays a cost equal to the number of misses, i.e., to the number of requests for files not in the cache. The cost can be computed as follows:

$$ \langle \mathbf{r}_t, \mathbf{x}_t \rangle = \sum_{i=1}^{N} r_{t,i} x_{t,i}, \quad (3) $$

where $\langle \mathbf{r}, \mathbf{x} \rangle \triangleq \sum_{i=1}^{N} r_i x_i$ denotes the scalar product of the two vectors $\mathbf{r}$ and $\mathbf{x}$.

For the sake of conciseness, we introduce the following notation. For any vector $\mathbf{r}$, we denote by $M(\mathbf{r})$ an arbitrary element of $\arg\min_{\mathbf{x} \in \mathcal{X}} \langle \mathbf{r}, \mathbf{x} \rangle$. Furthermore, given a sequence of vectors $(\mathbf{r}_1, \dots, \mathbf{r}_t)$, we represent their aggregate sum as $\mathbf{r}_{1:t} \triangleq \sum_{s=1}^{t} \mathbf{r}_s$.

<table><caption>TABLE I: Table of notation</caption><tr><td>N</td><td>catalog size</td></tr><tr><td>C</td><td>cache capacity</td></tr><tr><td>B</td><td>number of requests in each batch</td></tr><tr><td>X</td><td>decision set</td></tr><tr><td>B</td><td>set of request vectors</td></tr><tr><td>T</td><td>time horizon</td></tr><tr><td>r<sub>t</sub></td><td>request vector at time step t</td></tr><tr><td>x<sub>t</sub></td><td>decision vector at time step t</td></tr><tr><td>⟨r<sub>t</sub>, x<sub>t</sub>⟩</td><td>cost at time step t</td></tr><tr><td>r<sub>1:t</sub></td><td>sum of r<sub>s</sub> for all values of s from 1 to t</td></tr><tr><td>M(r)</td><td>value of x in X that minimizes ⟨r, x⟩</td></tr><tr><td>R<sub>T</sub>(A)</td><td>regret algorithm A</td></tr><tr><td>γ<sub>t</sub></td><td>noise vector</td></tr><tr><td>r̂<sub>t</sub></td><td>noisy request estimates</td></tr><tr><td>B̂</td><td>r̂<sub>t</sub> state space</td></tr></table>

### B. Caching and Online Learning

Caching can be framed as an online learning problem [17], where an agent (the caching system) chooses an action $\mathbf{x}_t$ from the set $\mathcal{X}$ at each time slot $t$ before an adversary reveals a request vector $\mathbf{r}_t$ from the set $\mathcal{B}$.

The cache state is determined by an online algorithm $\mathcal{A}$ that, at each time slot $t$, computes the cache state $\mathbf{x}_{t+1}$ for the next time slot given the current state $\mathbf{x}_t$ and the sequence of requests up to time $t$, that is $\{\mathbf{r}_s\}_{s=1}^t$.

The main performance metric used to evaluate an online deterministic algorithm $\mathcal{A}$ choosing action $\mathbf{x}_t$ at each time step $t$ is the regret defined as:

$$ \mathcal{R}_T(\mathcal{A}) = \sup_{\{\mathbf{r}_1, \dots, \mathbf{r}_T\}} \left\{ \sum_{t=1}^{T} \langle \mathbf{r}_t, \mathbf{x}_t \rangle - \mathrm{OPT}_T \right\}, \quad (4) $$

where $\mathrm{OPT}_T = \langle \mathbf{r}_{1:T}, M(\mathbf{r}_{1:T}) \rangle$ is the cost incurred under the request sequence $\{\mathbf{r}_1, \dots, \mathbf{r}_T\}$ by the optimal static allocation $\mathbf{x}^* = M(\mathbf{r}_{1:T})$. When the algorithm $\mathcal{A}$ is randomized, one can define the expected regret:

$$ \mathcal{R}_T(\mathcal{A}) = \sup_{\{\mathbf{r}_1, \dots, \mathbf{r}_T\}} \left\{ \mathbb{E} \left[ \sum_{t=1}^{T} \langle \mathbf{r}_t, \mathbf{x}_t \rangle \right] - \mathrm{OPT}_T \right\}, \quad (5) $$

where the expectation is taken over any random choice of the algorithm $\mathcal{A}$. The expected regret quantifies then the performance gap over a time horizon $T$ between the algorithm $\mathcal{A}$ and the best static cache allocation with hindsight.

Given the supremum taken over all request sequences in both (4) and (5), it is evident that the regret metrics refrain from making any assumptions regarding the characteristics of the request sequence, such as any inherent statistical regularity. The request sequence may be thought to have been generated by an adversary seeking to degrade the performance of the caching system. In this setting, one aims for an algorithm with sublinear regret, $\mathcal{R}_T(\mathcal{A}) = o(T)$. These algorithms are commonly known as no-regret algorithms since their time-average cost approaches the optimal static policy's cost as $T$ grows.

Various algorithms, such as Online Gradient Descent (OGD) and Follow-the-Regularized-Leader (FTRL), can attain $O(\sqrt{T})$-regret for caching problems [8], [10]. However, their
**Algorithm 1:** Noisy-Follow-the-Perturbed-Leader with Uniform Noise (NFPL)

**Input:** Set of decisions $\mathcal{X}$; $T$; $\eta$

**Output:** Sequence of decisions: $\{\mathbf{x}_t\}_{t=1}^T$

1. costs $\leftarrow 0$,

2. for round $t = 1, 2, ..., T$ do

3. $\gamma_t \sim \text{Unif}([0, \eta]^N, \mathbb{I}_{N \times N})$

4. $\mathbf{x}_t \leftarrow M(\text{costs} + \gamma_t)$

5. Pay $\langle \mathbf{r}_t, \mathbf{x}_t \rangle$

6. Observe $\hat{\mathbf{r}}_t$

7. costs $\leftarrow$ costs + $\hat{\mathbf{r}}_t$

8. end

cache update procedures require a computationally expensive projection of a tentative solution back onto the feasible set $\mathcal{X}$ (e.g., its cost is $O(N^2)$ for OGD [16]).

In the next section, we present a lightweight caching algorithm with $O(\sqrt{T})$-regret.

### C. Follow-the-Perturbed-Leader (FPL)

Within the domain of online learning, the Follow-the-Perturbed-Leader (FPL) algorithm is a notable projection-free methodology known to achieve sublinear regret. This algorithm was initially introduced by Vempala et al. [18], and later studied within the caching framework by Bhattacharjee et al. [19].

The FPL algorithm serves as a refined version of the traditional Follow-the-Leader (FTL) algorithm [20]. The latter greedily selects the state that would have minimized the past cumulative cost, i.e., $\mathbf{x}_{t+1}(\text{FTL}) = M(\mathbf{r}_{1:t})$.

While the FTL algorithm proves optimal when cost functions are sampled from a stationary distribution, it, unfortunately, yields linear regret in adversarial settings [21].

The FPL algorithm improves the performance of FTL by incorporating a noise vector $\gamma_t$ at each time step $t$. This vector's components are independent and identically distributed (i.i.d.) random variables, pulled from a distinct distribution (such as the uniform and exponential distributions in [18], and the Gaussian distribution in [19]). The update process unfolds similarly to FTL:

$$ \mathbf{x}_t(\text{FPL}) = M(\mathbf{r}_{1:t-1} + \gamma_t). \quad (6) $$

As shown in [19], FPL provides optimal regret guarantees for the discrete caching problem. Moreover, the cache update, as specified in equation (6), involves storing the files that correspond to the largest elements of the vector $\mathbf{r}_{1:t-1} + \gamma_t$. FPL cache update necessitates then a sorting operation. Notably, its computational complexity of $O(N \log N)$ is less taxing than the projection step required by either the FRL or OGD algorithms, as highlighted in [19].

## III. EXTENDING FPL

The traditional FPL algorithm needs to track the request count for each file in the catalog. As we discussed in the

introduction, in scenarios with a large catalog and/or high request rate, the cache may only have access to noisy estimates. For this reason, we introduce the Noisy-Follow-the-Perturbed-Leader (NFPL), a lightweight variant of FPL that employs noisy request estimates instead of exact request counts. In Section III-A, we present the NFPL algorithm in detail along with its regret analysis. Subsequently, in Section III-B, we study NFPL when noisy request estimates stem from sampling the request process as in [14].

### A. Noisy-Follow-the-Perturbed-Leader (NFPL)

The NFPL algorithm is described in Algorithm 1. NFPL follows in the footsteps of FPL with uniform noise but observes the estimated requests $\hat{\mathbf{r}}_t$ instead of the real requests $\mathbf{r}_t$. In particular, at each time slot $t$, the algorithm generates $\gamma_t$ from a multivariate uniform distribution with uncorrelated components, constrained within the range $[0, \eta]^N$, and it updates the decision vector $\mathbf{x}_t$ with the minimizer of $\langle \mathbf{x}, \hat{\mathbf{r}}_{1:t-1} + \gamma_t \rangle$ over $\mathbf{x} \in \mathcal{X}$. The cost paid at time slot $t$ is equal to $\langle \mathbf{r}_t, x_t \rangle$. The total cost of the NFPL algorithm is

$$ \text{NFPL}_T = \sum_{t=1}^{T} \langle \mathbf{r}_t, M(\hat{\mathbf{r}}_{1:t-1} + \gamma_t) \rangle. \quad (7) $$

We remark that Algorithm 1 is not just confined to the caching scenario discussed in Section II. Indeed, it is also applicable to any situation where the agent incurs costs represented by the equation $\langle \mathbf{r}_t, \mathbf{x}_t \rangle$.

**Assumption 1:** We assume that $\hat{\mathbf{r}}_t$ is an unbiased estimator of $\mathbf{r}_t$, which implies that the expected value of $\hat{\mathbf{r}}_t$ equals $\mathbf{r}_t$, i.e., $\mathbb{E}[\hat{\mathbf{r}}_t] = \mathbf{r}_t$.

**Assumption 2:** Let $\hat{\mathcal{B}}$ be the state space of $\hat{\mathbf{r}}_t$. We assume the existence of the following constants:

$$ \hat{A} = \sup_{\hat{\mathbf{r}} \in \hat{\mathcal{B}}} \|\hat{\mathbf{r}}\|_1, \quad \hat{R} = \sup_{\mathbf{x} \in \mathcal{X}, \mathbf{r} \in \hat{\mathcal{B}}} \langle \mathbf{r}, \mathbf{x} \rangle, \quad (8) $$

$$ D = \sup_{\mathbf{x}, \mathbf{y} \in \mathcal{X}} \|\mathbf{x} - \mathbf{y}\|_1. \quad (9) $$

**Theorem 1 (Regret bound NFPL):** Under Assumptions 1 and 2, the NFPL algorithm with $\eta = \sqrt{\hat{R} \cdot \hat{A} \cdot T/D}$ enjoys sublinear regret:

$$ \mathcal{R}_T(\text{NFPL}) \le 2\sqrt{\hat{R} \cdot \hat{A} \cdot D \cdot T}. \quad (10) $$

*Proof:* It is convenient to define the following two auxiliary quantities

$$ \text{NFPL}_T = \sum_{t=1}^{T} \langle \hat{\mathbf{r}}_t, M(\hat{\mathbf{r}}_{1:t-1} + \gamma_t) \rangle, \quad (11) $$

$$ \text{OPT}_T = \langle \hat{\mathbf{r}}_{1:T}, M(\hat{\mathbf{r}}_{1:T}) \rangle. \quad (12) $$

We compute the expectation—over $\{\hat{\mathbf{r}}_t, \gamma_t\}_{t=1}^T$—of the difference between the total cost of NFPL and OPT$_T = \langle \mathbf{r}_{1:T}, M(\mathbf{r}_{1:T}) \rangle$ as follows

$$ \begin{aligned} & \mathbb{E}[\text{NFPL}_T - \text{OPT}_T] \\ &= \mathbb{E}[\text{NFPL}_T - \text{NF}\hat{\text{PL}}_T] + \mathbb{E}[\text{NF}\hat{\text{PL}}_T - \text{OPT}_T] \\ &\quad + \mathbb{E}[\text{OPT}_T - \text{OPT}_T]. \end{aligned} \quad (13) $$
We have:

$$ \mathbb{E}[\mathrm{NFPL}_T - \mathrm{NFPL}_T] = 0, \quad (14) $$

$$ \mathbb{E}[\mathrm{OPT}_T - \mathrm{OPT}_T] \le 0, \quad (15) $$

$$ \mathbb{E}[\mathrm{NFPL}_T - \mathrm{OPT}_T] \le 2\sqrt{\hat{R} \cdot \hat{A} \cdot D \cdot T}. \quad (16) $$

The random vectors $\hat{r}_t$ and $M(\hat{r}_{1:t-1} + \gamma_t)$ are independent, hence $\mathbb{E}[(\hat{r}_t, M(\hat{r}_{1:t-1} + \gamma_t))] = \langle \hat{r}_t, \mathbb{E}[M(\hat{r}_{1:t-1} + \gamma_t)] \rangle$ and by linearity of the expectation we deduce (14). We have that $\mathrm{OPT}_T \le \langle \hat{r}_{1:T}, M(\mathbf{r}_{1:T}) \rangle$, we get then (15).

The quantity $\mathrm{NFPL}_T - \mathrm{OPT}_T$ can be seen as the difference between the cost of an FPL algorithm with uniform noise, that observes costs $\{\hat{r}_t\}_{1}^T$, minus the cost incurred by the optimal static allocation $\mathbf{x}^* = M(\hat{r}_{1:T})$. Therefore, applying [18, Theorem 1.1 a)] with $\epsilon = 1/\eta$ such that $\eta = \sqrt{\hat{R} \cdot \hat{A} \cdot D/T}$, we get

$$ \mathbb{E}_{\{\gamma_t\}_1^T} [\mathrm{NFPL}_T - \mathrm{OPT}_T] \le 2\sqrt{\hat{R} \cdot \hat{A} \cdot D \cdot T} $$

for any $\{\hat{r}_t\}_{1}^T$, and by taking the expectation over the randomness of $\{\hat{r}_t\}_{1}^T$ in both sides of the last inequality, we find (16). Plugging (14), (15) and (16) in (13), we deduce that $\mathbb{E}[\mathrm{NFPL}_T - \mathrm{OPT}_T] \le 2\sqrt{\hat{R} \cdot \hat{A} \cdot D \cdot T}$ for every $\{\mathbf{r}_t\}_{1}^T$, concluding the proof.

**Remark 1:** NFPL regret bound in Theorem 1 can be written as $\alpha \cdot \beta$ where $\alpha = \hat{R} \cdot \hat{A}/(R \cdot A)$, $\beta = 2\sqrt{R \cdot A \cdot D \cdot T}$, $R = \sup_{\mathbf{x} \in \mathcal{X}, \mathbf{x} \in \bar{\mathcal{B}}} \langle \mathbf{r}, \mathbf{x} \rangle$ and $A = \sup_{\mathbf{r} \in \bar{\mathcal{B}}} \|\mathbf{r}\|_1$. Observe that $\beta$ is FPL's classical regret bound when the algorithm knows the exact costs [18, Theorem 1.1 a)]. It is easy to verify that $\alpha$ is greater than or equal to 1 and can then be interpreted as the performance loss the algorithm incurs due to the noisy costs.

## B. NFPL for Caching

We apply NFPL to the caching problem (section II-A), deriving $\hat{r}_t$ from sampled requests. Two methods are explored: NFPL-Fix, sampling a fixed number of requests within each batch, and NFPL-Var, independently sampling each request within the batch with a fixed probability.

**NFPL-Fix.** The caching system samples $b \ge 1$ requests uniformly at random from a batch of $B$ requests at each time slot. Let $\hat{\mathbf{d}}_t$ be the number of requests for each file in the sampled batch at time step $t$. NFPL-Fix is Algorithm 1 with noisy request estimates $\hat{r}_t$ given by

$$ \hat{r}_t = \frac{B}{b} \cdot \hat{\mathbf{d}}_t. \quad (17) $$

**Corollary 1 (Regret bound NFPL-Fix):** NFPL-Fix with $\eta = B\sqrt{2T}/2C$ has sublinear regret:

$$ \mathcal{R}_T(\mathrm{NFPL-Fix}) \le 2\sqrt{2} \cdot B\sqrt{C \cdot T}. \quad (18) $$

*Proof:* Observe that with (17), we have that $\mathbb{E}[\hat{r}_t] = \mathbf{r}_t$. Since $\|\hat{\mathbf{d}}_t\|_1 = b$, then $\hat{A} = B$ and $\hat{R} \le B$. We have that $D \le 2C$, hence by applying Theorem 1 in this setting, the regret bound readily follows concluding the proof.

**NFPL-Var.** The caching system samples each request within the batch of requests with a probability $f > 0$ at each time slot. Let $\hat{s}_t$ be the number of requests for each file in the sampled batch at time step $t$. NFPL-Var is Algorithm 1 with noisy request estimates $\hat{r}_t$ expressed as

$$ \hat{r}_t = \frac{1}{f} \cdot \hat{s}_t. \quad (19) $$

**Corollary 2 (Regret bound NFPL-Var):** NFPL-Var with $\eta = B\sqrt{2T}/(2f \cdot C)$ has sublinear regret:

$$ \mathcal{R}_T(\mathrm{NFPL-Var}) \le 2\sqrt{2} \cdot \frac{B}{f} \cdot \sqrt{C \cdot T}. \quad (20) $$

*Proof:* Observe that with (19), we have that $\mathbb{E}[\hat{r}_t] = \mathbf{r}_t$. Moreover, we observe that the maximum of $\|\hat{r}_t\|_1$ is attained when the sub-batch includes all the requests from the batch, i.e., $\|\hat{s}_t\|_1 = B$. It follows that $\hat{A} = B/f$ and $\hat{R} \le B/f$. We have that $D \le 2C$, hence by applying Theorem 1 in this setting, the regret bound readily follows concluding the proof.

For $b = B$ and $f = 1$, request counts are exact, i.e., $\hat{r}_t = \mathbf{r}_t$, and both NFPL-Fix and NFPL-Var coincide with the classic FPL. Using Corollary 1 or Corollary 2 we deduce the following corollary.

**Corollary 3 (Regret bound FPL caching):** FPL with $\eta = B\sqrt{2T}/2C$ has sublinear regret:

$$ \mathcal{R}_T(\mathrm{FPL}) \le 2\sqrt{2} \cdot B\sqrt{C \cdot T}. \quad (21) $$

The authors of [19] proved regret guarantees for FPL applied to caching under perfect knowledge of the requests when $B = 1$. We report the result here for completeness.

**Theorem 2:** [19, Thm. 3] FPL applied to the caching problem with $B = 1$, learning rate $\eta = \frac{1}{4\pi(\ln N)^{1/4}}\sqrt{\frac{T}{C}}$, and noise vectors $\{\gamma_t\}_{1}^T$, where $\gamma_t/\eta$ is drawn from a standard multivariate normal distribution, has sublinear regret. More specifically

$$ \mathcal{R}_T(\mathrm{FPL}) \le 1.51 \cdot (\ln N)^{1/4} \cdot \sqrt{C \cdot T}. \quad (22) $$

The comparison of Corollary 3 and Theorem 2 shows that our analysis is also of interest when requests are exactly known. First, our bound (21) is also valid when the requests are batched, which is of practical interest since updating the cache at each request might be computationally impractical. Second, our bound does not depend on the catalog size, as (22) does, and in particular it will not diverge as $N$ goes to infinity.

## IV. NUMERICAL EVALUATION

We conducted simulations of NFPL-Fix and NFPL-Var and other existing policies, using both synthetic and real-world traces. Details about the traces are presented in Section IV-A, while Section IV-B discusses the caching baselines. We evaluate the effectiveness of our proposed algorithms, NFPL-Fix and NFPL-Var, from two perspectives. First, in Section IV-C, we compare the NFPL family of algorithms to traditional caching algorithms. Second, we compare NFPL-Fix and NFPL-Var and show the effect of sampling on their performance in Section IV-D.
<figure><img src="image_2.png" /><figcaption>Fig. 1: Average miss ratio, C = 100.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Fig. 2: Average miss ratio vs. sampling probability.</figcaption></figure>

## A. Traces

**Zipf trace.** We generate a total of $5 \times 10^6$ requests from a catalog of $N = 10^4$ files following an i.i.d. Zipf distribution with exponent $\alpha = 1$. The Zipf distribution is a popular model for the request process in caching [22].

**Akamai trace.** The request trace, sourced from Akamai CDN as documented in [23], encompasses several days of file requests, amounting to a total of $2 \times 10^7$ requests for a catalog comprising $N = 10^3$ files.

**Round-robin trace.** We generate a total of $10^6$ file requests from a catalog comprising $N = 10^4$ files in a round-robin fashion. The round-robin trace is commonly considered as an adversarial trace [19].

## B. Caching policies

We compare our methods (NFPL-Fix and NFPL-Var) with the optimal static cache allocation with hindsight (OPT), FPL with perfect knowledge of the requests (equivalent to NFPL-Var with $f = 1$), as well as two classic caching policies: Least-Frequently-Used (LFU) and Least-Recently-Used (LRU). Upon a miss, LFU and LRU evict from the cache the least popular file and the least recently requested file, respectively. FPL and NFPL policies are configured with $T$ equal to the number of batches in the corresponding trace.

All the aforementioned caching policies are evaluated with the average miss ratio computed as follows

$$ \frac{1}{Bt} \sum_{\tau=1}^{t} \langle \mathbf{r}_{\tau}, \mathbf{x}_{\tau} \rangle. \qquad (23) $$

For NFPL-Fix and NFPL-Var, the average miss ratio is averaged over $M = 50$ runs, considering different noisy request estimates $\{\hat{r}_t\}_{1}^T$ and noise vectors $\{\gamma_t\}_{1}^T$. To account for the variability across the runs, we report the first and ninth deciles of the average miss ratio. In all experiments, the batch size $B$ is set to 200.

## C. NFPL vs. classical policies

We simulate NFPL-Var, with sampling probability $f = 0.5$, FPL, LRU, LFU, and OPT over all the presented traces. In Figure 1, we show the average miss ratio at each time step $t$.

In the Zipf trace, files popularity does not change over time and LFU rapidly discerns the most popular files and subsequently converges to OPT. However, due to the noise $\gamma_t$, FPL requires a longer duration to accurately determine the files to be stored. NFPL, on the other hand, grapples with two sources of noise: the inherent noise $\gamma_t$ and the additional noise due to sampling. As a result, NFPL takes even longer to adjust. Nevertheless, both FPL and NFPL outperform LRU, whose missing ratio fails to converge to OPT.

In the Akamai trace, it is plausible to anticipate fluctuations in popularity over time, and requests' temporal correlations.
Such patterns can be advantageous for LRU. In fact, LRU now performs almost on par with LFU. Notably, both FPL and NFPL appear to be converging to the performance of OPT.

Under the round-robin trace, optimality can be achieved with any static allocation of *C* distinct files. However, both LRU and LFU demonstrate equally disappointing performances. This is because at any time LRU stores the *C* most recently requested files, while LFU retains the *C* most frequently requested ones, but the next request is not for any of these cached files.

In contrast, both NFPL-Var and FPL showcase performances that are close to optimal. This reaffirms the resilience and adaptability of online learning policies across request processes as different as the three traces we considered. Intriguingly, NFPL-Var, which is inherently “noisier,” outperforms FPL to some extent. This phenomenon can be explained: the noisier $\hat{r}_{1:t} + \gamma_t$, the more the cache tends to store a random set of files disregarding past requests. Such strategy is precisely up for the round-robin trace.

### D. NFPL-Fix vs. NFPL-Var

We compare the performance of NFPL-Fix, NFPL-Var, and OPT on all the considered traces for two cache sizes: $C \in \{10, 200\}$ for the Zipf trace and $C \in \{10, 100\}$ for the Akamai and round-robin traces. Figure 2 illustrates the average miss ratio for all the aforementioned caching policies when varying sampling probabilities, i.e., *f* for NFPL-Var and $b/B$ for NFPL-Fix.

Across the various traces we analyzed, the performance difference between NFPL-Fix and NFPL-Var is consistently minimal for all the sampling rates. This indicates that the selection of the sampling method may exert only a marginal impact on the performance of NFPL.

The influence of the sampling rate varies across the traces, aligning with the patterns previously noted in Figure 1. For the Zipf and Akamai traces, the performance of both NFPL-Fix and NFPL-Var tends towards that of OPT with increasing sampling rates. This is attributable to the relatively stationary nature of these traces, where the count of past requests serves as a good predictor for future requests; thus, more precise estimates bolster performance. In contrast, the round-robin trace benefits from noisier estimates, as it is preferable to overlook past requests in this scenario. As a result, the performance of NFPL-Fix and NFPL-Var deteriorates with a rising sampling rate.

## V. CONCLUSION

In this paper, we introduce the Noisy-Follow-the-Perturbed-Leader (NFPL) algorithm, a variant of the Follow-the-Perturbed-Leader (FPL) algorithm that incorporates noisy cost estimates, and provide conditions on the cost estimates estimator for which NFPL achieves sublinear regret. In the context of the caching problem, we propose two NFPL algorithms, NFPL-Fix and NFPL-Var, based on sampling, that achieve sublinear regret. By conducting experiments on both synthetic and real world traces, we show the impact of request sampling

on the performance of NFPL. In future work, we plan to investigate the regret of NFPL when the request estimator is based on approximate counting data structures such as the Count-Min Sketch [13].

## VI. ACKNOWLEDGMENTS

This research was supported in part by the French Government through the “Plan de Relance” and “Programme d’investissements d’avenir.

## REFERENCES

[1] J. Tse and A. J. Smith, “CPU cache prefetching: Timing evaluation of hardware implementations,” *IEEE Transactions on Computers*, vol. 47, no. 5, pp. 509–526, 1998.

[2] T. Bektas, O. Oguz, and I. Ouveysi, “Designing cost-effective content distribution networks,” *Computers & Operations Research*, vol. 34, no. 8, pp. 2436–2449, 2007.

[3] D. Chatzopoulos et al., “Mobile augmented reality survey: From where we are to where we go,” *IEEE Access*, vol. 5, pp. 6917–6950, 2017.

[4] G. Ananthanarayanan et al., “Real-time video analytics: The killer app for edge computing,” *Computer*, vol. 50, no. 10, pp. 58–67, 2017.

[5] R. Fagin, “Asymptotic miss ratios over independent references,” *Journal of Computer and System Sciences*, vol. 14, no. 2, pp. 222–250, 1977.

[6] S. Traverso et al., “Temporal locality in today’s content caching: Why it matters and how to model it,” *ACM SIGCOMM Computer Communication Review*, vol. 43, no. 5, pp. 5–12, 2013.

[7] M. Leconte et al., “Placing dynamic content in caches with small population,” in *IEEE INFOCOM 2016*, pp. 1–9, 2016.

[8] G. S. Paschos et al., “Learning to cache with no regrets,” in *IEEE INFOCOM 2019*, pp. 235–243, 2019.

[9] M. Zinkevich, “Online convex programming and generalized infinitesimal gradient ascent,” in *ICML 2003*, pp. 928–936, 2003.

[10] N. Mhaisen, G. Iosifidis, and D. Leith, “Online caching with optimistic learning,” in *2022 IFIP Networking Conference (IFIP Networking)*, pp. 1–9, 2022.

[11] N. Mhaisen et al., “Optimistic no-regret algorithms for discrete caching,” *Proceedings of the ACM on Measurement and Analysis of Computing Systems*, vol. 6, no. 3, pp. 1–28, 2022.

[12] G. Einziger, R. Friedman, and B. Manes, “Tinylfu: A highly efficient cache admission policy,” *ACM Transactions on Storage (ToS)*, vol. 13, no. 4, pp. 1–31, 2017.

[13] Y. Ben Mazziane, S. Alouf, and G. Neglia, “Analyzing count min sketch with conservative updates,” *Computer Networks*, vol. 217, p. 109315, 2022.

[14] S. Li et al., “Full-stack architecting to achieve a billion-requests-per-second throughput on a single key-value store server platform,” *ACM Transactions on Computer Systems (TOCS)*, vol. 34, no. 2, pp. 1–30, 2016.

[15] Q. Liu and Y. Zhang, “Learning to caching under the partial-feedback regime,” in *2022 18th International Conference on Network and Service Management (CNSM)*, pp. 154–162, 2022.

[16] T. Si Salem, G. Neglia, and S. Ioannidis, “No-regret caching via online mirror descent,” *ACM Transactions on Modeling and Performance Evaluation of Computing Systems*, vol. 8, no. 4, pp. 1–32, 2023.

[17] E. Hazan, “Introduction to online convex optimization,” *Foundations and Trends® in Optimization*, vol. 2, no. 3-4, pp. 157–325, 2016.

[18] A. Kalai and S. Vempala, “Efficient algorithms for online decision problems,” *Journal of Computer and System Sciences*, vol. 71, no. 3, pp. 291–307, 2005.

[19] R. Bhattacharjee, S. Banerjee, and A. Sinha, “Fundamental limits on the regret of online network-caching,” *Proceedings of the ACM on Measurement and Analysis of Computing Systems*, vol. 4, no. 2, pp. 1–31, 2020.

[20] N. Littlestone and M. K. Warmuth, “The weighted majority algorithm,” *Information and computation*, vol. 108, no. 2, pp. 212–261, 1994.

[21] S. De Rooij et al., “Follow the leader if you can, hedge if you must,” *The Journal of Machine Learning Research*, vol. 15, no. 1, pp. 1281–1316, 2014.

[22] L. Breslau et al., “Web caching and zipf-like distributions: Evidence and implications,” in *IEEE INFOCOM’99. Conference on Computer Communications.*, vol. 1, pp. 126–134, IEEE, 1999.
[23] G. Neglia et al., "Access-time-aware cache algorithms," *ACM Transactions on Modeling and Performance Evaluation of Computing Systems (TOMPECS)*, vol. 2, no. 4, pp. 1-29, 2017.