No-Regret Mixing of LRU and LFU with Optimal Switching Cost ∗
∗
Younes Ben Mazziane
Xinying Zou
Université d’Avignon
Linköping University
arXiv:2609.07566v1 [cs.LG] 7 Sep 2026
ABSTRACT
requests [6, 9, 11, 17, 14]. Despite their strong empirical performance, these algorithms are not known to guarantee performance comparable to the better of LRU and LFU on arbitrary request sequences. Worst-case guarantees for caching algorithms were first studied in the paging problem, where each miss triggers an eviction and hits leave the cache content unchanged. The standard metric is the competitive ratio, defined as the worst-case ratio between the miss count of the online policy and that of Belady’s offline optimal algorithm. For cache capacity C, no deterministic online algorithm can achieve a competitive ratio smaller than C, and several policies, including LRU and FIFO, attain this bound [3]. Thus, the competitive ratio can fail to distinguish algorithms with different practical behavior. More recently, several caching policies based on online convex optimization [8] have been proposed [12, 2]. These policies are evaluated through regret, defined as the worst-case gap between the miss count of the algorithm and that of the optimal offline static caching policy, i.e., the cache storing the top-C most requested items. Sublinear regret then guarantees that, asymptotically, the miss ratio of the policy approaches that of this optimal static cache. However, this benchmark can be weak, as it is frequency-based and therefore close in spirit to LFU. The limitation is particularly clear for workloads with strong temporal locality. For example, consider a cache of size C = 2 and a trace composed of n phases, where phase i consists of 2r requests of the form (ai , bi )r , with ai and bi being fresh items. Since every item appears exactly r times, storing any two distinct items is optimal among static caches and incurs 2(n − 1)r misses. In contrast, LRU incurs 2n misses, which is much smaller than the optimal static offline benchmark when r is large. This shows that no-regret guarantees with respect to the optimal static cache do not necessarily imply good performance on recency-friendly workloads. In this paper, we consider as performance metric, the worst-case gap, over all request sequences of length T , between the number of misses incurred by an algorithm A and the smaller miss count incurred by LRU or LFU. We refer to this metric throughout the paper simply as regret, and we denote it as RA T . The objective is then to design efficient caching policies with sublinear regret, i.e., RA T = o(T ). Such policies are then guaranteed to adapt to both frequency and recency driven workloads. A natural way to achieve sublinear regret is to formulate caching as an experts problem [4], with LRU and LFU as experts. The policies LeCaR [17] and Cacheus [14] follow this principle: upon a miss, they probabilistically choose whether to evict according to LRU or LFU. Their selection probabilities are inspired by Hedge [4]; they maintain scores for the two eviction rules and sample from the corresponding softmax distribution. The scores are updated through a history of past evictions. When an
Caching systems often rely on simple eviction policies such as Least Recently Used (LRU) and Least Frequently Used (LFU), which perform well in complementary request regimes. Recent policies such as LeCar and Cacheus combine LRU and LFU using ideas from the experts problem in online learning. Specifically, upon a miss, they randomize between the two eviction rules using probabilities derived from scores updated by tracking the history of past evictions. While these policies exhibit strong empirical performance, it remains unclear whether they are guaranteed, on every request sequence, to perform asymptotically as well as the better of LRU and LFU, i.e., whether they achieve sublinear regret with respect to this benchmark. We first show that LeCar suffers linear regret against an oblivious adversary, even with unbounded history. We then propose H-MC, a Hedge-based mixture of virtual LRU and LFU caches that preserves Hedge’s selection probabilities, and hence its regret guarantees, while minimizing the switching cost among all joint selection rules with these marginals.
Keywords Caching, Expert’s problem, Lazy online learning
1.
INTRODUCTION
Caching is widely used across computer systems, from improving CPU performance to enhancing user experience in content delivery networks. Its main goal is to decide which files should be stored locally so as to reduce the fraction of requests that cannot be served directly from the cache. Least Recently Used (LRU) and Least Frequently Used (LFU) are very popular caching policies. Upon a miss (a request for an item not stored in the cache), LRU evicts the least recently requested item from the cache, whereas LFU evicts the least frequently requested one. LRU and LFU are known to perform well in complementary regimes. For instance, LFU is asymptotically optimal when requests are drawn from a stationary distribution. In contrast, LRU is often more effective in nonstationary environments, where requests exhibit temporal locality [16], such as when items are requested in bursts and may not be requested again afterward. Motivated by this complementarity, many subsequent caching policies have been proposed to adaptively combine recency-based and frequency-based decisions depending on the observed ∗Both authors contributed equally to this work.
Copyright is held by author/owner(s).
1
We consider a server storing a set I of N files and a single cache memory, that can store up to C < N files from I. A sequence of requests for items in I of length T , denoted f = (fs )s∈[T ] , arrives at the cache. If ft is available in the cache at step t, the request is a hit, and the cache serves the request. Otherwise, it is a miss, and the cache forwards the request to the server. A caching policy A decides the content of the cache at time t, denoted StA , based on past requests f1 , . . . , ft−1 . Algorithm A samples StA from a probability distribution over the space {S ⊂ I : |S| = C}. Let the total miss count of a caching policy A until time T be
evicted item is requested again, the rule responsible for its eviction is penalized. However, it remains unclear if such policies inherit Hedge’s sublinear regret guarantees. We thus aim to address the following questions: 1. Do existing online-learning inspired caching policies, such as LeCaR, have sublinear regret guarantees? 2. If not, what are efficient alternative ways to combine LRU and LFU to achieve such guarantees?
Contributions
MTA ≜
This paper makes two main contributions. First, we prove that LeCaR approach to combining LRU and LFU exhibits linear regret against an oblivious adversary, i.e., RLeCaR = T Ω(T ), even when the history size is unbounded. Second, we propose H-MC, a Hedge-based mixture of virtual LRU and LFU caches that preserves the Hedge selection probabilities, and hence its regret guarantees, while minimizing the switching cost among all couplings with these marginals.
1{ft ∈ / StA }.
(1)
t=1
One of the most popular caching policies are the Least Recently Used (LRU) caching policy that evicts the leastrecently used item upon a miss and the Least Frequently Used (LFU) that evicts the least popular item among stored ones upon a miss. In this paper we aim to devise policies that perform as well as the best of LRU and LFU for any request sequence. Namely, policies with sublinear regret where the regret is defined as the gap between the miss count of an algorithm and that of the minimum of LRU and LFU. We denote this metric as RA T and it is formally defined as, h i A RA − min MTLFU , MTLRU , (2) T ≜ sup E MT
LeCaR has linear regret. This result is first established in Theorem 3.1 for cache capacity equal to 2, and is then extended to arbitrary cache capacities in Theorem 3.2. Establishing this negative result is not immediate. Standard adversarial traces, such as round-robin traces, are ineffective because LRU and LFU often recommend the same eviction. Moreover, on stationary or clearly recency friendly traces, eviction feedback tends to reveal the better rule, allowing LeCaR to adapt. Beyond the choice of trace, the analysis is complicated by LeCaR’s time-varying selection probabilities: each randomized eviction can lead to a different future cache state, making the algorithm’s evolution difficult to track. To handle this difficulty, we construct a periodic request sequence for which LRU and LFU incur the same number of misses in each period, but recommend storing different files. Using a negative-drift argument for the Markov chain governing the ratio of their selection probabilities, we show that LeCaR repeatedly switches between the two rules, resulting in linear regret.
f
LeCar. LeCaR [17] was proposed as a caching policy that uses online learning techniques to adaptively balance between LRU and LFU updates. The high level idea is that, upon a miss, LeCaR randomize between LRU and LFU eviction rules using probabilities derived from scores updated by tracking the history of past evictions. Algorithm 2, in the appendix, describes the caching policy. At each step t, the algorithm maintains a cache content St ⊆ I, a recency list Rt ordering the cached items from least to most recently used, and LFU hash map Nt for cached items, both of size C. In addition, for each expert e ∈ E = {LRU, LFU}, the algorithm maintains a weight wte and a history Hte of size at most k. The history Hte is a Hashmap/dictionary that maps previously evicted items by LeCaR, on recommendation by expert e, to their eviction times. For example, Hte = {(f, s)} means that file f was evicted by LeCaR on a recommendation by expert e at step s. We also write Hte [f ] = s and we use similar notation for Nt . At time t, the requested item is ft . If ft ∈ St−1 , the request is a hit. The cache content, experts weights, and histories remain unchanged. The recency list is updated by moving ft to the most-recently-used position, and the LFU counter of ft is incremented. If ft ∈ / St−1 , the request is a miss and an eviction decision is required. Before choosing the eviction, each expert e receives the decayed loss
Caching with experts. Rather than using LRU and LFU as experts that recommend which item to evict, as in LeCaR, we use them as experts that recommend complete cache content. This yields a standard experts problem: at time t, Hedge (for example) outputs a probability qt of following the cache content of LRU, and probability 1 − qt of following LFU. Sampling the expert independently at each time step, however, can incur a large upload cost, since the selected expert may switch frequently. We therefore couple consecutive expert selections so as to preserve the marginals qt while minimizing the probability of switching. This is achieved by a maximal coupling between the decisions at times t and t + 1, and is optimal among all policies with the same marginal probabilities (see Theorem 4.1). We call the resulting coupling MC. Combining √ MC with Hedge√gives the policy H-MC, which has O( T ) regret and O( T ) worst-case switching cost, as shown in Corollary 4.1.
e
e ℓet = 1{ft ∈ Ht−1 }d t−Ht−1 [ft ] ,
(3)
where d ∈ (0, 1) is parameter of the algorithm. This penalizes expert e if ft is in the history of expert e, Hte . The e expert weights are then updated as, wte = wt−1 exp(−ηℓet ), and normalized into probabilities pet ∝ wte . An expert Et is sampled according to pt = (pet )e∈E and its eviction recommendation is followed. The LRU expert recommends the least recently used item, vtLRU = first(Rt−1 ), whereas the LFU expert recommends an item with minimum counter, vtLFU ∈ arg mini∈St−1 Nt−1 [i], with ties broken according to the LRU order. The cache is then
Outline. The rest of the paper is organized as follows. Section 2 formally defines the problem and describes LeCaR, Section 3 proves that LeCaR suffers linear regret, Section 4 introduces the proposed caching policy H-MC, and Section 5 concludes the paper.
2.
T X
PROBLEM FORMULATION 2
updated so that the recommended item for eviction vtEt is removed from the cache and the requested item is added instead. The recency list removes the evicted item vtEt and inserts ft in the most-recently-used position. Similarly, the counts Hashmap Nt removes vtEt ’s entry and adds ft with count 1. Finally, the requested item is removed from both histories, since it is now cached, and the item evicted by the selected expert is inserted into the corresponding history with timestamp t. If this history exceeds size k, its oldest entry is discarded.
3.
where Et designates the expert selected by LeCaR at step t. These three events describe all possible evolutions of S LeCaR inside phase i, as shown in (7). a,a,b
i {a, bi−1 } −−−−→ {a, bi } bi a → {a, bi }, {bi , ci } −→ {bi , ci } − ci bi a −→ {bi , ci } − → {a, bi }, {a, ci } −→ b a i {a, bi } − → {a, bi }, {a, ci } −→
LECAR HAS LINEAR REGRET
ρi (j) ≜
(4)
{a, b0 } −−−−→ {a, b1 } −→ {a, c1 } −−→ {a, b1 }.
Pr A1i | ρi =
ρi , (1 + ρi )(µ1 + ρi ) µ1 Pr A3i | ρi = . (1 + ρi )(µ1 + ρi )
(5)
c
b ,a
(11)
Note that, even when the history sizes are unbounded, the histories at the end of each phase contain only items that will never be requested again. Therefore, these items do not incur any future penalties, regardless of which history contains which item. We denote the expected number of misses per phase i conditioned on ρi as m(i|ρ): " 6 # X LeCaR m(i|ρ) = E 1 fτi (j) ∈ / Sτi (j) | ρi = ρ (12)
Miss count of LRU. The same reasoning applies to LRU. In phase 1, a,a,b
ρi , 1 + ρi
Pr A2i | ρi =
and LFU incurs three misses. Hence, at the end of the phase, it again stores a and one phase item, namely b1 . The same argument applies inductively to every phase. Therefore, MTLFU = 2 + (T − 3)/2.
1 1 1 {a, b0 } −−−−→ {a, b1 } −→ {b1 , c1 } −− → {a, b1 },
(8)
Therefore,
where bi and ci are requests for 2 distinct items that only appear at phase i. Without loss of generality, we assume that T − 3 is a multiple of 6. Miss count of LFU. Initially, LFU incurs two misses and stores {a, b0 }. In phase 1, b1 ,a
wLRU (τi (j)) . wLFU (τi (j))
Let µ1 = exp(−ηd), and µ2 = exp(−ηd2 ). Conditioned on ρi = ρ, the ratio ρi (j) changes only at the steps where one of the experts is penalized. Along the three path events A1i , A2i , A3i , its evolution is a → µ2 ρ, on A1i , ρ − a,a,bi ,ci ,bi ρ a → ρ, on A2i , (10) ρ −−−−−−−→ µ1 − a ρ − ρ 3 , on A . → i µ1 µ1
Proof. The request sequence starts with (b0 , a, a). After that, the request occurs in periodic way, each with 6 requests. In each phase i, the request sequence is
c1
on A3i .
We also write ρi ≜ ρi (1) for the value of this ratio at the beginning of phase i. Conditioned on ρi (j) = ρ, the probability that LeCaR selects LRU at an eviction time is ρ Pr Eτi (j) = LRU | ρi (j) = ρ = . (9) 1+ρ
Theorem 3.1. LeCaR has linear regret, i.e., RLeCaR = T Ω(T ) when the cache capacity C = 2 and for any histories length k ≥ 1.
a,a,b1
(7)
on A2i ,
Although the quantity S LeCaR exhibits a periodic pattern per phase, the probabilities of the three paths in each phase, depend on the evolution of the expert weights. We therefore track the relative weight of LRU with respect to LFU. For i ≥ 1 and j ∈ [6], define
LeCaR was empirically shown to remain competitive with both LRU and LFU on traces that alternate between recency-friendly and frequency-friendly phases [17]. Theorem 3.1 shows that this is not guaranteed when the separation between the two regimes is less clear. In particular, it constructs a trace on which LRU and LFU have comparable performance, at every time, while maintaining different cache contents. In this case, LeCaR keeps switching between the two eviction rules, causing it to perform worse than both LRU and LFU.
(a, a, bi , ci , bi , a),
on A1i ,
(6)
j=1
and LRU also incurs three misses. Thus, at the end of each phase, it stores a and the corresponding phase item. By induction, MTLRU = 2 + (T − 3)/2.
From (7), LeCaR incurs three misses on A1i and A3i , and four misses on A2i . Hence, m(i|ρ) = 3 +
Miss count of LeCaR. Define τi (j) as the time index of request number j ∈ [6] in phase i, i.e., τi (j) = 3+6(i−1)+ j. Assume that the phase starts from S LeCaR = {a, bi−1 }. The first two requests to a are hits, while the request to the fresh item bi evicts bi−1 , so the cache becomes {a, bi }. The only nontrivial branching occurs after the request to ci , and possibly after the following request to bi , depending on which expert is selected for eviction. In all possible branches, however, the phase ends again with S LeCaR = {a, bi }. We denote the three possible paths during phase i by
ρ 1 1 + ρ µ1 + ρ
(13)
The excess miss probability with respect to LRU and LFU ρ 1 in one phase is thus 1+ρ . This quantity is small only µ1 +ρ when ρ is close to 0 or very large, which corresponds to LeCaR selecting essentially only one of the two experts. Hence, to prove linear regret, it is enough to show that the weight ratio does not escape to either extreme. More precisely, suppose that there exist constants 0 < ρ− < ρ+ < ∞ and κ > 0, such that for every phase i, Pr (ρi ∈ [ρ− , ρ+ ]) ≥ κ.
A1i ≜ {Eτi (4) = LRU},
(14)
Then for any phase i,
A2i ≜ {(Eτi (4) , Eτi (5) ) = (LFU, LRU)},
E [m(i|ρ)] ≥ 3 + κ
A3i ≜ {(Eτi (4) , Eτi (5) ) = (LFU, LFU)}, 3
min ρ∈[ρ− ,ρ+ ]
1 ρ 1 + ρ µ1 + ρ
.
(15)
4.
The minimum is strictly positive because [ρ− , ρ+ ] is a compact subset of (0, ∞). Therefore, LeCaR incurs a constant excess number of misses per phase compared with LRU and LFU, which implies RLeCaR = Ω(T ). Next we T prove (14). Proof of (14). Combining (10) and (11) yields that ρi is Markov process with the following transition probabilities, ρi , µ ρ , w.p. 2 i 1 + ρi 1 ρi w.p. , (16) ρi+1 = ρi , 1 + ρ ρ + µ1 i i ρi µ1 1 µ , . w.p. 1 1 + ρi ρi + µ1
With this choice of experts, decision set, and loss function, the regret of the resulting online decision problem coincides with the regret defined in (2). Applying the Hedge algorithm in this setting yields ( LRU LFU StLRU , w.p. ψ Mt−1 − Mt−1 , Hedge (24) St = StLFU , otherwise,
Let γi ≜ ln(ρi ) and consider the following conditional expected drift, denoted as ∆(ρ), and defined as, ∆(ρ) ≜ E [γi+1 − γi |γi = ln(ρ)] .
(17)
Define β1 = ln(µ1 ) and β2 = ln(µ2 ). Direct computations yields, 1 µ1 ρ · β2 − · · β1 1+ρ 1 + ρ µ1 + ρ β2 β1 = · ρ2 + µ1 ρ − µ1 · . (1 + ρ)(µ1 + ρ) β2
∆(ρ) =
1 . Equivalently, qtHedge = ψ (∆t ), where ψ(x) ≜ 1+exp(ηx) LRU LFU LRU LFU where ∆t = Mt−1 − Mt−1 , and Mt−1 and Mt−1 denote the miss count of √ LRU and LFU over the first t − 1 requests. Taking η = O(1/ T ) yields√asymptotically optimal sublinear regret: RHedge = O( T ). Appendix C provides T more details about the Hedge algorithm in general. Despite its optimal regret guarantee, using Hedge to mix LRU and LFU may incur a large upload cost. WhenA ever Et+1 ̸= EtA , the algorithm may need to replace its current cache state with that of the newly selected policy. In the worst case, the two virtual caches are disjoint, requiring the upload of as many as C files. By contrast, A when Et+1 = EtA , the cache performs a standard LRU or LFU update, which requires at most one upload. Thus, switches capture the main source of excess update cost, motivating our focus on the expert-switching cost.
(18) (19)
Note that β1 = −ηd and β2 = −ηd2 with d ∈ (0, 1), and thus β2 < 0 and β1 /β2 = 1/d > 1. Thus, the r roots of the −µ1 ±
β
1 µ2 1 +4µ1 β
quadratic function ρ2 + µ1 ρ − µ1 ββ12 are 2 And there exists δ > 0, and 0 < r1 < r2 such that,
2
CACHING WITH EXPERTS
To obtain a caching policy with sublinear regret guarantees, in the sense of (2), we cast the problem as an experts problem. The set of experts is E = {LRU, LFU}. At each time step t, each expert recommends the cache state that would be maintained by its corresponding virtual cache, namely StLRU and StLFU . The loss of expert e ∈ E at time t is defined as ℓet = 1{ft ∈ / Ste }. At each step t, the algorithm A selects an expert EtA . We denote its probability of selecting LRU as qtA ≜ Pr StA = StLRU . The expected loss of A at time t is therefore linear in its decision, ℓt (A) = qtA ℓLRU + 1 − qtA ℓLFU (23) t t .
.
∀ρ ∈ (0, r1 ), ∆(ρ) > δ, and ∀ρ ∈ (r2 , +∞), ∆(ρ) < −δ. (20) Given that γi has bounded increments, i.e., γi+1 − γi ∈ {β2 , 0, −β1 }, [13, Thm. 1] implies that there exists a constant L > 0 such that,
UTA (f ) ≜
T −1 X
A Pr Et+1 ̸= EtA ,
(25)
t=1
sup E [|γi |] ≤ L.
(21)
which counts the expected number of expensive transitions between the two virtual caches. Thus, besides the marginal probabilities qtA ≜ Pr EtA = LRU , an algorithm is also characterized by the joint distribution of (EtA )t∈[T ] . A natural implementation is to sample EtA independently at each time step according to qtA . However, this A can lead to linear switching cost. For instance, if qt ≃ A 1/2, then Pr Et+1 ̸= EtA ≃ 12 , and hence UTA (f ) = Θ(T ). Instead, given a sequence of marginal probabilities (qt )t∈[T ] , for instance produced by Hedge, we couple consecutive expert choices so as to preserve the marginals while minimizing the probability of switching. This is achieved by a maximal coupling of two Bernoulli random variables [15, Chapter 1.4]. Specifically, the maximal-coupling sampler, denoted by MC, satisfies min{1 − qt , 1 − qt+1 } MC Pr Et+1 = LFU | EtMC = LFU = , 1 − qt min{qt , qt+1 } MC Pr Et+1 = LRU | EtMC = LRU = , (26) qt
i≥1
This permits to use Markov inequality to prove that that there exists κ > 0 such that γi is bounded in a finite segment with a probability at least κ. This is equivalent to proving (14) and finishes the proof. Theorem 3.2. The statement of Theorem 3.1 also holds for any cache size C ≥ 2. Proof. The proof follows the same argument as in the case C = 2, by adding C − 2 persistent items that remain permanently in the cache without affecting the dynamics of the two remaining cache slots. Let G = (g1 , . . . , gC−2 ) be a sequence of C − 2 distinct items. We modify the request sequence in the proof of Thm. 3.1 so that the initial requests are G, G, b0 , a, a, ensuring that S LeCaR = {a, b0 , G} at the beginning. Then in each phase i, the request sequence is, (a, a, G, bi , G, ci , G, bi , G, a).
(22)
Theorem 4.1 shows that this construction preserves the marginals, and minimizes the switching cost.
The cache-state evolution on the two non persistent slots has the same structure as in the proof of Theorem 3.1. The only change is that the elapsed times between an eviction and the corresponding future request are larger because of the intervening requests to G. This (C) (C) only replaces µ1 and µ2 by constants µ1 , µ2 ∈ (0, 1), and the same drift argument applies.
Theorem 4.1. For any request sequence f of length T and any sequence of probabilities (qt )t∈[T ] , min
A: ∀t, qtA =qt
4
UTA (f ) =
T −1 X t=1
|qt+1 − qt |.
(27)
Pr EtMC = LRU = qtHedge . It follows that H-MC inherits the√sublinear regret guarantees of Hedge, i.e., RH-MC = T O( T ). The same theorem also computes the corresponding switching cost. Moreover,
Algorithm 1 H-MC: Hedge with maximal-coupling Require: Request sequence f = (f1 , . . . , fT ), cache size C, learning rate η > 0 1: (∆0 , q1 ) ← (0, 0.5) 2: Sample E1 ∼ Bernoulli(q1 ), where E1 = LRU w.p. q1 3: for t = 1 to T do 4: St ← StEt 5: δt ← 1{ft ∈ / StLRU } − 1{ft ∈ / StLFU } 6: ∆t ← ∆t−1 + δt 7: qt+1 ← ψ (∆t ) 8: if (δt = 1, Et = LRU) then q 9: Et+1 ← LFU w.p. 1 − t+1 qt 10: else if (δt = −1, Et = LFU) then qt+1 −qt 11: Et+1 ← LRU w.p. 1−qt 12: else 13: Et+1 ← Et 14: end if 15: end for
Hedge |qt+1 − qtHedge | = |ψ(∆t ) − ψ(∆t−1 )| η η ≤ |∆t − ∆t−1 | ≤ . (30) 4 4 We used above the fact that the derivative of ψ is equal to η exp(ηx)/(1+exp(ηx))2 , which is smaller than η/4. This √ proves that the switching cost is O( T ) for any f .
More generally, there is extensive literature on minimizing the switching cost in the experts problem, including Shrinking Dartboard, a lazy variant of Hedge [7], and lazy variants of Follow the Perturbed Leader [10, 5]. We instead exploit the fact that there are two experts, enabling us to construct a maximal coupling between consecutive selections and minimize the switching cost. To further reduce the switching cost, one may also use simple schemes such as batching decisions, i.e., resampling the expert only once every B requests, combined with sampling the request sequence with some probability p. Although such schemes preserve sublinear p regret, they worsen the regret bound by a factor O( B/p) [1]. Appendix C evaluates the upload cost and the miss count of H-MC when augmented with these modifications. Finally, although H-MC minimizes the switching cost, it may still be undesirable to incur a large upload cost in a single step when the selected expert changes. To mitigate this issue, observe that any algorithm A satisfying i ∈ StLRU ∩ StLFU , 1, q Hedge , i ∈ StLRU \ StLFU , t (31) Pr i ∈ StA = Hedge 1 − qt , i ∈ StLFU \ StLRU , 0, otherwise,
Moreover, this minimum is achieved by the maximal coupling sampler MC in (26). The proof uses the following claim. Claim 4.1. Let X and Y be Bernoulli random variables with success probabilities x and y. Among all joint distributions with these marginals, the minimum possible mismatch probability, Pr (X ̸= Y ), is |x − y|. Moreover, this value is achieved by the maximal coupling, for which Pr (X = 1, Y = 1) = min{x, y}, Pr (X = 0, Y = 0) = min{1 − x, 1 − y}.
(28)
The proof of the claim is Appendix B. Proof of Thm. 4.1. Using Claim 4.1 for two Bernoulli random variables, Et and Et+1 , with success probabilities MC qt and qt+1 , we deduce that (EtMC , Et+1 ) is a maximal cou MC = pling of these two distributions, i.e., Pr EtMC ̸= Et+1 |qt+1 − qt |. Thus MC minimizes the switching cost.
has the same expected loss as Hedge in (24). This observation allows for more flexible implementations. For example, instead of selecting one entire virtual cache, one can construct a randomized cache by coupling the files in StLRU \StLFU with those in StLFU \StLRU and storing exactly one file from each pair, with probabilities qtHedge and 1 − qtHedge , respectively. Such an implementation keeps the same expected regret guarantee as Hedge, while avoiding the need to upload an entire virtual cache in one shot.
Combining Hedge with MC yields a caching algorithm that we call H-MC. This policy is a lazy implementation of Hedge. Instead of resampling an expert independently from the new Hedge distribution at every step, H-MC couples the choices as in (26). Algorithm 1 describes an implementation of H-MC. More precisely, after observing request ft , the algorithm computes δt = 1{ft ∈ / StLRU } − 1{ft ∈ / StLFU },
5.
CONCLUSION
We showed that the LeCaR-style approach to combining LRU and LFU has linear regret with respect to the better of the two policies. We then proposed a Hedge-based algorithm for a suitable experts formulation, achieving sublinear regret while minimizing the switching cost through a maximal coupling of consecutive selections. In future work, we would like to investigate whether the maximalcoupling idea can be extended to design efficient lazy noregret algorithms for the general experts problem. We would also like to design caching policies with sublinear regret guarantees under a more practical upload cost metric, rather than using switching cost as a proxy.
(29)
and sets qt+1 as the probability of sampling an expert in Hedge, i.e., qt+1 = ψ(∆t ), with ∆t = MtLRU − MtLFU . If δt = 0, both experts incur the same loss, and therefore qt+1 = qt . In this case the maximal coupling keeps the same expert with probability one. If δt = 1, then LRU misses while LFU hits, so the Hedge probability of LRU decreases, i.e., qt+1 < qt . Hence, only when the current expert is LRU may a switch be needed; the algorithm sets q MC Et+1 = LFU w.p. 1 − t+1 . Similarly, if δt = −1, then qt LRU hits while LFU misses, so qt+1 > qt . In this case, only when the current expert is LFU may a switch be needed. q −qt MC The algorithm then sets Et+1 = LRU w.p. t+1 . 1−qt Corollary 4.1 shows that H-MC has sublinear regret and √ a worst-case switching cost of O( T ). √ √ Corollary 4.1.√If η = O(1/ T ), then RH-MC = O( T ) T H-MC and UT (f ) = O( T ), for any requests f .
6.
ACKNOWLEDGMENTS
The authors thank the anonymous reviewers of IFIP Performance for their insightful comments, which helped improve the paper. YB also thanks Isidoor Pinillo Esquivel for a helpful discussion during a visit to Inria, and Giovanni Neglia and Sara Alouf for hosting the visit. Xinying Zou is supported by ELLIIT and the KAW foundation.
Proof. Using Thm. 4.1, MC is maximal coupling and thus it preserves the marginal probabilities, i.e., 5
APPENDIX A.
LECAR
Algorithm 2 LeCaR-style update with LRU and LFU experts Input: Request sequence f = (f1 , . . . , fT ), cache size c, initial cache content S0 , initial recency list R0 , learning rate η > 0, discount factor d ∈ (0, 1], history size k Output: Cache states S1 , . . . , ST . 1: E ← {LRU, LFU} 2: N0 ← {(i, 0) : i ∈ S0 }, ▷ Initial LFU counters 3: (w0e , H0e ) ← (1, ∅) ∀e ∈ E ▷ Initial expert weight and history 4: for t = 1 to T do ▷ Increment only the requested item’s LFU counter 5: if ft ∈ St−1 then e e 6: (St , wte , Hte ) ← (St−1 , wt−1 , Ht−1 ) 7: Rt ← MRU(Rt−1 , ft ) ▷ Move ft to most recent position 8: Nt [i] ← Nt−1 [i] + 1 (i = ft ), ∀i ∈ Nt−1 9: else e e 10: ℓet ← 1 (ft ∈ Ht−1 ) dt−Ht−1 [ft ] , for all e e e e 11: wt ← wt−1 exp(−ηℓt ), ∀e ▷ Penalize the expert whose history contains ft we 12: pet ← P t e′ , ∀e e′ ∈E wt
13: Sample Et ∼ pt ▷ Choose eviction expert 14: vtLRU ← first(Rt−1 ) ▷ LRU recommendation ▷ LFU recommendation 15: vtLFU ← arg mini∈St−1 (Nt−1 (i)) (ties broken by LRU) 16: St ← St−1 \ {vtEt } ∪ {ft } ▷ Evict vtEt and insert ft ▷ Update recency list 17: Rt ← MRU(Rt−1 \ {vtEt }, ft ) 18: Nt ← Nt−1 ∪ {(ft , 1)} \ {vtEt , Nt−1 [vtEt ]}. e 19: Hte ← ▷ Remove requested item from the history t−1 \ {ft }, ∀e H Et Et ▷ Insert evicted item with timestamp t 20: Ht vt = t 21: Evict from HtEt the item with the oldest timestamp when |HtEt | ≥ k 22: end if 23: end for
B.
PROOFS
Proof of Claim 4.1. Let p and q denote the distributions of X and Y on {0, 1}, i.e., p(1) = x, p(0) = 1 − x, q(1) = y, and q(0) = 1 − y. Define r(i) ≜ min{p(i), q(i)}, ∀i ∈ {0, 1} and α ≜ r(0) + r(1). [15, Thm. 4.1] implies that 1 − α = |x − y| is the minimum possible mismatch probability. We now use the maximal coupling construction from [15, Chap. 1, Sec.4]. Let I be a Bernoulli random variable with parameter α. If I = 1, X = Y = V , where V in a random variable on {0, 1} with distribution r(i) , ∀i ∈ {0, 1}. α Otherwise, X = WX and Y = WY such that the distributions of WX and WY are given by, Pr (V = i) =
Pr (WX = i) =
(32)
p(i) − r(i) q(i) − r(i) , Pr (WY = i) = . 1−α 1−α
(33)
[15, Thm. 4.2] shows that this construction minimizes the mismatch probability, i.e., Pr (X ̸= Y ) = |x − y|. Note that WX and WY have disjoint supports, since for each i ∈ {0, 1}, at most one of p(i) − r(i) and q(i) − r(i) is positive. Hence, conditioned on I = 0, we have X ̸= Y . Therefore, Pr (X = Y = 1) = Pr (I = 1, V = 1) =
αr(i) = min(x, y). α
(34)
Similar arguments hold for X = Y = 0, which finishes the proof.
C.
HEDGE
In the standard experts problem, each expert e ∈ E incurs a loss ℓet ∈ [0, 1] at time t. Let Mte = cumulative loss. The Hedge algorithm selects expert e at time t with probability pet = P and therefore incurs expected loss ℓt (Hedge) = RTHedge ≜
P
T X t=1
Pt
e s=1 ℓs denote its
e exp(−ηMt−1 ) , e′ exp(−ηM t−1 ) e′ ∈E
e e e∈E pt ℓt . For any loss sequence, its regret satisfies
ℓt (Hedge) − min MTe ≤ e∈E
log |E| ηT + . η 8
p p Thus, choosing η = 8 log |E|/T gives RTHedge = O( T log |E|), which is minimax optimal up to constant factors [4, Thm. 2.2 and Sec. 3.7]. 6
D.
REFERENCES
[1] Younes Ben Mazziane, Francescomaria Faticanti, Sara Alouf, and Giovanni Neglia. Efficient and Optimal No-Regret Caching Under Partial Observation. IEEE Transactions on Networking, 34:2020–2030, 2026. doi:10.1109/TON.2025.3636929. [2] Rajarshi Bhattacharjee, Subhankar Banerjee, and Abhishek Sinha. Fundamental Limits on the Regret of Online Network-Caching. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 4(2):1–31, June 2020. doi:10.1145/3392143. [3] Joan Boyar, Lene M. Favrholdt, and Kim S. Larsen. The relative worst-order ratio applied to paging. Journal of Computer and System Sciences, 73(5):818–843, August 2007. doi:10.1016/j.jcss.2007.03.001. [4] Nicolo Cesa-Bianchi and Gabor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006. [5] Luc Devroye, Gábor Lugosi, and Gergely Neu. Prediction by random-walk perturbation. In Proceedings of the 26th Annual Conference on Learning Theory, volume 30, pages 460–473, Princeton, NJ, USA, June 2013. PMLR. URL: https://proceedings.mlr.press/v30/Devroye13.html. [6] Donghee Lee, Jongmoo Choi, Jong-Hun Kim, S.H. Noh, Sang Lyul Min, Yookun Cho, and Chong Sang Kim. LRFU: a spectrum of policies that subsumes the least recently used and least frequently used policies. IEEE Transactions on Computers, 50(12):1352–1361, December 2001. doi:10.1109/TC.2001.970573. [7] Sascha Geulen, Berthold Vöcking, and Melanie Winkler. Regret Minimization for Online Buffering Problems Using the Weighted Majority Algorithm. In COLT 2010 - The 23rd Conference on Learning Theory, pages 132–143. Omnipress, 2010. [8] Elad Hazan. Introduction to online convex optimization. Foundations and Trends® in Optimization, 2(3-4):157–325, 2016. [9] Song Jiang and Xiaodong Zhang. LIRS: an efficient low inter-reference recency set replacement policy to improve buffer cache performance. ACM SIGMETRICS Performance Evaluation Review, 30(1):31–42, June 2002. doi:10.1145/511399.511340. [10] Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):291–307, October 2005. doi:10.1016/j.jcss.2004.10.016. [11] Nimrod Megiddo and Dharmendra S. Modha. ARC: A Self-Tuning, Low Overhead Replacement Cache. In 2nd USENIX Conference on File and Storage Technologies (FAST 03). USENIX Association, March 2003. URL: https://www.usenix.org/conference/fast-03/arc-self-tuning-low-overhead-replacement-cache. [12] Georgios S. Paschos, Apostolos Destounis, Luigi Vigneri, and George Iosifidis. Learning to Cache With No Regrets. pages 235–243. IEEE, April 2019. doi:10.1109/INFOCOM.2019.8737446. [13] Robin Pemantle and Jeffrey S. Rosenthal. Moment conditions for a sequence with negative drift to be uniformly bounded in Lr. Stochastic Processes and their Applications, 82(1):143–155, July 1999. doi:10.1016/S0304-4149(99)00012-5. [14] Liana V. Rodriguez, Farzana Yusuf, Steven Lyons, Eysler Paz, Raju Rangaswami, Jason Liu, Ming Zhao, and Giri Narasimhan. Learning Cache Replacement with CACHEUS. In 19th USENIX Conference on File and Storage Technologies (FAST 21), pages 341–354. USENIX Association, February 2021. URL: https://www.usenix.org/conference/fast21/presentation/rodriguez. [15] Hermann Thorisson. Coupling, stationarity, and regeneration. Probability and its Applications, 2000. [16] Stefano Traverso, Mohamed Ahmed, Michele Garetto, Paolo Giaccone, Emilio Leonardi, and Saverio Niccolini. Temporal locality in today’s content caching: why it matters and how to model it. ACM SIGCOMM Computer Communication Review, 43(5):5–12, November 2013. doi:10.1145/2541468.2541470. [17] Giuseppe Vietri, Liana V. Rodriguez, Wendy A. Martinez, Steven Lyons, Jason Liu, Raju Rangaswami, Ming Zhao, and Giri Narasimhan. Driving Cache Replacement with ML-based LeCaR. In 10th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage 18), July 2018.
7