Online Weighted Paging with Unknown Weights
Authors: Orin Levy
Noam Touitou
Aviv Rosenberg
Venue: NeurIPS 2024 poster (2024)
Keywords: Online Learning
Online Weighted Paging
Online Algorithms
Competitive Ratio
Regret
Theory
Primary area: online_learning
TL;DR: We study the Online Weighted Paging problem, where the weights are unknown. We provide algorithm and analyze it's performance in terms of competitive ratio and regret.

Abstract: Online paging is a fundamental problem in the field of online algorithms, in which one maintains a cache of $k$ slots as requests for fetching pages arrive online. 
In the weighted variant of this problem, each page has its own fetching cost; a substantial line of work on this problem culminated in an (optimal) $O(\log k)$-competitive randomized algorithm, due to Bansal, Buchbinder and Naor (FOCS'07).

Existing work for weighted paging assumes that page weights are known in advance, which is not always the case in practice.
For example, in multi-level caching architectures, the expected cost of fetching a memory block is a function of its probability of being in a mid-level cache rather than the main memory.
This complex property cannot be predicted in advance; over time, however, one may glean information about page weights through sampling their fetching cost multiple times.

We present the first algorithm for online weighted paging that does not know page weights in advance, but rather learns from weight samples.
In terms of techniques, this requires providing (integral) samples to a fractional solver, requiring a delicate interface between this solver and the randomized rounding scheme; we believe that our work can inspire online algorithms to other problems that involve cost sampling.

Online Weighted Paging with Unknown Weights
Orin Levy" Tel-Aviv University orinlevy@mail. tau. ac il
Noam Touitou
Amazon Science
noamtwx@gmail.cmm com
Aviv Rosenberg" Google Research avivros0070gmail.comm
Abstract
Online paging is fundamental problem in the field of online algorithms, in which one maintains cache of & slots as requests for fetching pages arrive online. In the weighted variant of this problem, each page has its own fetching cost; substantial line of work on this problem culminated in an (optimal) O k coompttiiive randomized algorithm, due to Bansal, Buchbinder and Naor (FOCS'07) 077).
Existing work for weighted paging assumes that page weights known in advance, which is not always the case in practice. For example, in multi-level caching architectures, the expected cost of fetching memory block is function of its probability of being in mid-level cache rather than the main memory. This complex property cannot be predicted in advance; over time, however, one may glean information about page weights through sampling their fetching cost multiple times. We present the first algorithm for online weighted paging that does not know page weights in advance, but rather learns from weight samples. In terms of techniques, this requires providing (integral) samples a fractional solver, requiring a delicate interface between this solver and the randomized rounding scheme: we believe that our work can inspire online algorithms other problems that involve cost sampling.
1 Introduction
Online weighted paging. In the online weighted paging problem, or OWP, one given a cache of k slots, and requests for pages arrive online. Upon each requested page, the algorithm must ensure that the page is in the cache, possibly evicting existing pages in the process. Each page p also has a weight w which represents the cost of fetching the page into the cache; the goal of the algorithm is to minimize the total cost of fetching pages. Assuming that the page weights are known, this problem admits an (log k) coompetiiiee randomized online algorithm, due Bansal, Buchbinder and Naor 20100 2012): This is optimal, as there exists an 22log k) --oompeiiiiveeess lower bound for randomized algorithms due to Fiat al. 1991 (that holds even for the unweighted case).
However, all previous work on paging assumes that the page weights are known in advance. This assumption is not always justified; for example, the following scenario, reminiscent of real-world architectures, naturally gives rise to unknown page weights. Consider a multi-core architecture, in which data be stored in one of the following: local "L,1" cache, unique each core; global "L.2" cache, shared between the cores; and the (large but slow) main memory. As a specific core requests memory blocks, managing its LI cache can seen an OWP instance. Suppose the costs
Research conducted while the author was an intern at Amazon Science. t Research conducted while author was Amazon Science.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

of fetching block from the main memory and from the L2 cache are I and e < 1, respectively. Then, when a core demands a memory block, the expected cost of fetching this block (i.e., its weight) is a convex combination of 1 and e, weighted by the probability that the block is in the 1.2 cache; this probability can be interpreted as the demand for this block by the various cores. When managing the L1 cache of a core, we would prefer to evict blocks with low expected fetching cost, as they are more likely to be available in the L2 cache. But, this expected cost is a complicated property of the computation run by the cores, and estimating it in advance is infeasible; however, when block is fetched in the above example, we observe a stochastic cost of either I or E. As we sample a given block multiple times, can gain insight into its weight.
Multi-armed bandit. The above example, in which we learn about various options through sampling, is reminiscent of the multi- armee bandit problem, or MAB. In the cost- cost-minimizztion version of this problem, one is given options (or arms), each with its own cost in [0. 1]. At each time step, the algorithm must choose an option and pay the corresponding cost; when choosing an option p. rather than learning its cost W the algorithm is only revealed a sample from some distribution whose expectation is wp- In this problem, the goal is to minimize the regret, which is the difference between the algorithm's 's total cost and the optimal cost (which is to always choose the cheapest option). Over T time steps, the best known regret bound for this problem is Ö(VnT), achieved through multiple techniques. (See, c.g., Slivkins et al. [2019). Lattimore and Szepesvári (2200) )
1.1 Our Results
We make the first consideration of OWP where page weights are not known in advance, and show that the optimal competitive ratio of Olog k) can still be obtained. Specifically, we present the problem of OWP-UW (Online Weighted Paging with Unknown Weights), that combines OWP with bandit-like feedback. In OWP-UW, every page p has an arbitrary distribution, whose expectation is its weight w = 1. Upon fetching a page, the algorithm observes a random, independent sample from the distribution of the page. We present the following theorem for OWP-UW.
Theorem 1.1. There exists a randomized algorithm ON for OWP-UW such that, for every input Q.
B[ON(Q)] s O k) (PT(() + +Ö(VTT)
where ON(Q) is the cost of ON on Q, QPT(Q) is the cost of the optimal solution to Q, and the expectation is taken over both the randomness in ON and the samples from the distributions of pages.
Note that the bound in Theorem combines competitive ratio of Ollog k) with regret (i.e., additive) term of Ô ViT). To motivate this type of bound, observe that OWP-UW does not admit sublinear regret without a competitive ratio. Consider the lower bound of 2 k) for the competitive ratio of paging: stated simply, one of k + pages of weight is requested at random. Over a sequence of T requests, the expected cost of any online algorithm is (2(T/k); meanwhile, the expected cost of the optimal solution is at most O (K log k)). (The optimal solution would be to wait for maximal phase of requests containing at most & pages, whose expected length is O(k k log k). then change state constant cost.) Without competitive ratio term, the difference between the online and offline solutions is ((T/k) /).. i.c.. linear regret. We note that this kind of bound appears in several previous works such as Basu et al. (2019), ,, Foussoul et al. [003)] As OWP-UW generalizes both standard OWP and MAB, both the competitive ratio and regret terms are asymptotically tight:
competitiveness lower bound of 2(log k) is known for randomized algorithms for online (weighted)
paging FFat et al. 1991]. and a regret lower bound of 2 ((VTT) is known for MAB [Ltttmore and
Szepesvári 2020
1.2 Our Techniques
Interface between fractional solution and rounding scheme. Randomized online algorithms are often built of the following components:
1. A deterministic, a-competitive online algorithm for a fractional relaxation of the problem.
2. An online randomized rounding scheme that encapsulates any online fractional algorithm. and has expected cost & times the fractional cost.
Combining these components yields a--competitive randomized online (integral) algorithm.

---

For our problem, it is easy to see where this common scheme fails. The fractional algorithm cannot be competitive without sampling pages; but, pages are sampled by the rounding scheme! Thus, the competitivenees of the fractional algorithm is not independent of the randomized rounding, which must provide samples. One could think of addressing this by feeding any samples obtained by the rounding procedure into the fractional algorithm. However, as the rounding is randomized, this would result in a non-deterministic fractional algorithm. As described later in the paper, this is problematic: the rounding scheme demands a globally accepted fractional solution against which probabilities of cache states are balanced.
Instead, we outline sampling interface between the fractional solver and the rounding scheme. Once the total fractional eviction of a page reaches an integer, the fractional algorithm will pop a sample of the page from a designated sampling queue, and process that sample. On the other side of the interface, the rounding scheme fills the sampling queue and ensures that when the fractional algorithm demands a sample, the queue will be non-empty with probability 1.
Optimistic fractional algorithm, pessimistic rounding scheme. When learning from samples, one must balance the exploration of unfamiliar options and the exploitation of familiar options that are known be good. A well-known paradigm for achieving this balance in multi-armed bandit problems is optimism under uncertainty. Using this paradigm to minimize total cost, one maintains a lower confidence bound (LCB) for the cost of an option. which holds with high probability, and tightens upon receiving samples; then, the option with the lowest LCB is chosen. As a result, one of the following two cases holds: either the option was good (high exploitation); or, the option was bad, which means that the LCB was not tight, and henceforth sampling greatly improves it (high exploration).
Our fractional algorithm for weighted paging employs this method. It optimistically assumes that the price of moving page is cheap, i.e., is equal to some lower confidence bound (LCB) for that page. It then uses multiplicative updates to allocate servers according to these LCB costs. The optimism under uncertainty paradigm then implies that the fractional algorithm learns the weights over time.
However, the rounding scheme behaves very differently. Unlike the fractional algorithm, the (ran- domized) rounding scheme is not allowed to samples to update the confidence bounds; otherwise, our fractional solution would behave non-deterministicall, Instead, the rounding scheme takes a pessimistic view: it uses an upper confidence bound (UCB) as the cost of a page, thus assuming that the page is expensive. Such pessimistic approaches are common in scenarios where obtaining additional samples is not possible (e.g., offline reinforcement learning (Levine al., 2020)). ) but rarely appear as a component of an online algorithm as we suggest in this paper.
1.3 Related Work
The online paging problem is fundamental problem in the field of online algorithms. In the unweighted setting, the optimal competitive ratio for a deterministic algorithm is k, due to Sleatoor
and Tarjan (1985.. J. Allowing randomization improves the best possible competitive ratio to O (log k
[Fit et al. 1991 As part of a line of work on weighted paging and its variants (e.g.. Young 1994
Manasse al. 1990), Albers (2003), Trani [2002). FFat and Mendel (2000), [Bansal et al. [2008] Irani
1997]), the best competitive ratios for weighted paging were settled, and were seen to match the
unweighted setting: k-competitiveness for deterministic algorithms, due to Chrobak et al. [991]]
and @(log k) -competitiveeess for randomized algorithms, due to Bansal et al. [0022).
Online (weighted) paging is special case of the kesereer problem, in which k servers exist in general metric space, and must be moved to address requests on various points in this space; the cache slots in (weighted) paging can be seen servers, moving in (weighted) uniform metric space. The @(k) bound on optimal competitiveness in the deterministic for paging also extends to general k-server [Manasse et al., 1990 Koutsoupias and Papadimitriou, 1995). However, allowing randomization, a recent breakthrough result by Bubeck et al. 2023 was lower bound of 22 k)- competitiveness for k-server, diverging from the O(log comppetttsss possible for paging.
Multi-Armed Bandit (MAB) is one of the most fundamental problems in online sequential decision making, often used to describe a trade-off between exploration and exploitation. was extensively studied in the past few decades, giving rise to several algorithmic approaches that guarantee optimal regret. The most popular methods include Optimism Under Uncertainty (e.g., the UCB algorithm
LLi and Robbins 1985 Auer et al. 2002a ), Action Elimination [Even- Dar et al. 2006). Thompson
3

---

Sampling Thompson 1933
Agrawal and Goyal 2012 and Exponential Weights (e.g., the EXP3 [uerr et al. 2002b For comprehensive review of the MAB literature, see Slivkinn et al.) [2019] Lattimore and Szepesvári 2020
algorithm
2 Preliminaries
In OWP-UW, an online fashion; we denote the set of requested pages by P. define := [P], and assume that > Each page p has corresponding weight 0 < w I; the weights not known to the algorithm. Moreover, every page p has a distribution Dp supported in (0, 1J. such that Bx-D, [x] = W'p
given memory cache of slots. A sequence of T page requests then arrives in
The online scenario proceeds in I' rounds In each round I E (1.2....,7):
A page P; E requested.
If the requested page is already in the cache, then it is immediately served.
Otherwise, we experience cache miss, and we must fetch py into the cache; if the cache is full, the algorithm must evict some page from the cache to make room for pr-
Upon evicting any page p from the cache, the algorithm receives independent sample from Dp.
The algorithm incurs cost when evicting pages from the cache: when evicting page p, the algorithm incurs a cost of wy Our goal is to minimize the algorithm's 's total cost of evicting pages, denoted by ON, and we measure our performance by comparison to the total cost the optimal algorithm, denoted by OPT. We say that our algorithm is a-competitive with R regret if E[ON] s OPT
3 Algorithmic Framework and Analysis Overview
We present an overview of the concepts and algorithmic components We would like to follow the paradigm of solving a fractional problem online, and then randomly rounding the resulting solution; however, discussed in the introduction, employing this paradigm for OWP-UW requires a well-defined interface between the fractional solver and the rounding procedure. Thus, present fractional version of OWP-UW that captures this interface.
to address OWP-UW.
Fractional OWP-UW. fractional OWP-UW, one allowed to move fractions servers, and request for page is satisfied if the total server fraction at that point sums to 1. More formally, for every page p E P we maintain an amount Yp [0. 1] which the fraction of p missing from the cache; call yp the fractional anti-server at p. (The term anti-server comes from the related k-server problem.) The feasibility constraints are:
1. any point the algorithm, it holds that Ppp yp in the cache is at most k.)
(L.e., the total number of pages
2. After a page is requested, it holds that y, = O. (I.e., there exists total server fraction of at p.)
Evicting server fraction from p (i.e., increasing yp by E) costs Wp-
Sampling. The fractional algorithm must receive samples pages over time in order to learn about their weights. An algorithm for fractional OWP-UW receives sample of page p whenever the total fraction of p evicted by the algorithm reaches an integer. In particular, the algorithm obtains the first sample of p (corresponding to 0 eviction) when p is first requested in the online input.
We make simplifying assumption that T is known in advanced. This can be easily removed using standard doubling (see, e.g.. Slivkins et al. (2019).
*Note that charging an OWP solution for evicting rather than fetching pages is standard: indeed, with the exception of most k pages, every fetched page is subsequently evicted, and thus the difference between eviction and fetching costs is at most k. Moreover, as we analyze additive regret, note that s VnI. implying that using fetching costs would not affect the bounds in this paper. Finally, note that we sample upon eviction rather than upon fetching, which is the "harder" model.

---

Algorithmic components. We present the fractional algorithm and randomized rounding scheme.
Fractional algorithm. In Section 4 we present an algorithm ONF for fractional OWP-UW. Fixing the random samples from the pages' weight distributions, the fractional algorithm ONF is deterministic. For every page p P. the fractional algorithm maintains an upper confidence bound UCBp and lower confidence bound LCBp- These confidence bounds depend on the samples provided for that page; we define the good event & be the event that at every time and for every page p P, it holds that LCB, s Wp s UCBp. We later show that & happens with high probability, and analyze the complementary event separately Thus, we henceforth focus on the good event.
The following lemma bounds the cost of ONF subject to the good event. In fact, it states stronger bound, that applies also when the cost of evicting page p is the upper confidence bound UCBp p 2 w p- Lemma 3.1. Fixing any input f. fractional OWP-UW, and assuming the good event, it holds that ONF(Q) S ONF(2) S Olog k) (PT(() + Õ(VnT)
where ONF is the cost of the algorithm on the input where the cost of evicting a page p is UCB, 2 Wp-
Randomized rounding. In Section we present the randomized algorithm ON for (integral) OWP-UW. maintains a probability distribution over integral cache states by holding an instance of ONF, to which it feeds the online input. For the online input to constitute a valid fractional input, the randomized algorithm ensures that samples are provided ONF when required. addition, the randomized algorithm makes use of ONF's exploration of page weights; specifically, it uses the UCBs calculated by ONF.
Lemma 3.2. Fixing any input Q for (integral) OWP-UW, assuming the good event &, it holds that B(ON(()) S 0(1) (NF( +
where ONF(Q) is the cost of the algorithm on such that the cost of evicting a page p is UCB, 2 W.p Figure D provides a step-by-step visualization of the interface between the fractional algorithm and the rounding scheme over the handling of page request.
4 Algorithm for Fractional OWP-UW
We now describe our algorithm for the fractional relaxation of OWP-UW, proving Lemma 3.1 Our fractional algorithm, presented in Algorithm [ beloow uses samples provided by the rounding scheme to learn the weights. A new sample for page p is provided and processed whenever the sum of fractional movements (in absolute value) mp hits a natural number. (At this point the number of samples np incremented.) The algorithm calculates non-increasing UCBs and non-decreasing LCBs that will be specified later in Section and guarantee with high probability, for every page p E P and time step E [1, LCB, S Wp S UCBp.
At each time step f, upon new page request pt. the algorithm updates its feasible fractional cache solution ppp)pep. The fractions are computed using optimistic estimates of the weights, i.e., the LCBs, in order to induce exploration and allow the true weights to be learned over time. After serving page Pt (that is, setting Yp, = 0), the algorithm continuously increases the anti-servers of all the other pages in the cache until feasibility is reached (that is, until Σper yp = n k). The fraction
Yp for some page p in the cache is increased proportionally to Yptn which our adaption of the LCE,'
algorithmic approach Bansal et al. [0010] to the unknown-weights scenario. Finally, to fulfil its end in the interface, the fractional algorithm passes its feasible fractional solution to the rounding scheme together with pessimistic estimates of the weights, i.e, the UCBs.
4.1 Analysis
In this analysis section, our goal to bound the amount ONF with respect the UCBs and LCBs calculated by the algorithm; i.c., to prove Lemma 4.1 Lemma C.I and Lemma C.2 from Appendix C
then make the choice of confidence bounds concrete, such that combining it with Lemma 4. vields the final bound for the fractional algorithm, i.e., Lemma 3.1
SSpecifically, we show that the complementary event E happens with probability at most #7 and that the algorithm's 's cost is most nT times the optimal cost when it happens.
5

---

OX2
OXB ONP
OMP
Stugles Dittstoatins
Stugle
Sample
Saugle
Distilationn
Disutbetiis P
This figure visualizes the running of the algorithm over request in the input. (a) shows the state prior to the arrival of the request. The integral algorithm maintains an instance of the fractional algorithm ONF, as well as distribution over integral cache states that upholds some properties w.r.t. ONF (specifically, the consistency property and subset property); note these properties are function both the anti-server state {Yp) per
and the upper-confidence bounds [CCBp] ( pep in ONF. The integral algorithm also maintains set of page samples, to be demanded by ONF a later time. In (b), page is requested (in red); thus, the fractional algorithu must fetch it into the cache, i.e. set its anti-server to 0. To maintain feasibility, the fractional algorithm will increase the anti-server at other pages in which some server fraction exists (in green). These changes anti-server are also fed into the integral algorithm, which modifies its distribution maintain consistency and the subset property w.r.t. ONF, (c), ONF reaches integral total eviction of a page p, and demands a sample from the integral algorithm. (We show that such sample always exists when demanded.) The bound UCBp p is updated in ONF, and is then fed to the integral algorithm to maintain the desired properties. After this sample, continuous increasing of anti-server continues until feasibility is reached in (d). Then, the integral algorithm ensures that a sample exists
requested page Pr. sampling page if needed. (As Pr now exists in μ with probability 1, sampling is done through evicting and re- re-fetching pr.)
Figure I: Visualization of the interface between the fractional and integral algorithms
Algorithm I: Fractional Online Weighted Caching with Unknown Weights
Set 17 - 1/k and yp + for every p P. for time 1 = 1,2, ..., T do
Page P2 c is requested.
contimually increase yp.mp
mp in proportion if mp reaches integer for some p (pr) then
Yn+l LCBp for every p P\ (pr) where yp until:
receive sample Wp for p. set Ap t Rp + call UPDATECONF
wp). recalculate confidence bounds for
if E EPPPP' p if this is the first request for then receive sample w for Pt- define mp 0, np call UPDATECONNBBUNDSS(P w.) calculate confulence bounds for Pr
k then break from the continuous increase loop.
12
13
Lemma 4.1. Fixing any inpus fractional OWP-UW, and assuming the good event, it holds that
"p
ONF(C) x Ollgg k) OPT( ΣΣ (CBB.. - LCBp..) +2log(1 1/n) Σ LCB..
PEP
PEP
where (a) ONF is the cost of the algorithm on the input such that the cost of evicting a page UCB, Wp. and (b) procedure UPDATECoNfBoUnDS (found in Appendix C immediately after processing the i'th sample of p, and (c) LCB, is the value after the last sample of page p was processed.
are the values of UCB, and LCB, calculated by the
Proof sketch. We prove the lemma using a potential analysis. In Bansal et al. (2010). potential function was introduced that encodes the discrepancy between the state of the optimal solution and the state of the algorithm. In our case, we require an additional term which can be viewed fractional exploration budget. This budget "recharged" upon receiving a sample; the cost of this recharging goes into regret term.

---

Pgn Pgil
80 Pg11
P2
Y
Y
Y
This figure visualizes single step in REBALANCESUBSETS Subfigure (a) shows the distribution of anti-cache states prior to this step; specifically, the axis is the probability measurc, and the y-axis is the number of pages of class and above in the anti-cache, i.e., == [S n Pzil. The red line is Y,, which through consistency, is the expectation m; the blue dotted lines are thus the allowed values for m, which are 1, LY:Jl. The total striped area in the figure is the imbalance measure, formally defined in Definition B.2 Subfigure (b) shows a single rebalancing step; we choose the imbalanced anti-cache S that maximizes Im Y/1: in our case, m > Y,. and thus match its measure with identical measure of anti-cache states that are below the upper blue line, ie., receive a page without increasing imbalance. Then, page of class is handed from to every matched state S note that every matched state might get a different page from S, but some such page in S S proven to exist. Finally, Subfigure (c) shows the state after the page transfer, note the decrease in imbalance that results. The REBALANCE SEBBLANCESSBSESS procedure performs such steps until there is imbalance; then, the procedure would advance class
Figure 2: Example of a rebalancing step
Randomized Rounding
This section describes randomized algorithm for (integral) OWP-UW, which uses Algorithm for fractional OWP-UW to maintain a probability distribution over valid integral cache states, while obtaining and providing page weight samples to Algorithm ! The method in which the randomized algorithm encapsulates and tracks the fractional solution is inspired by Bansal et al. [202]]. which maintains balanced property over weight classes of pages. However, as the weights are unknown in our case, the classes are instead defined using the probabilistic bounds maintained by the fractional solution (i.e., the UCBs). But, these bounds are dynamic, and change over the course of the algorithm; the imbalance caused by these discrete changes increases exponentially during rebalancing, and thus requires a more robust rebalancing procedure.
Following the notation in the previous sections, we identify each cache state with the set of pages not in the cache. Observing the state of the randomized algorithm at some point in time, let ((S) be the probability that 5 S P is the set of pages missing from the cache, also called the anti-cache. For the algorithm to be valid algorithm for OWP-UW, the cache can never contain more than k pages; this is formalized in the following property.
Definition 5.1 (valid distribution). A probability distribution is valid, if for any set S C P with (S)) it holds that [S]
k.
Instead of maintaining the distribution's validity, we will maintain a stronger property that implies validity. This property is the balanced property, involving the UCBs calculated by the fractional algorithm.
For every page p. we define the i'th UCB class be P, = {p : 6 S UCB, <
<6+1). (Note that UCB, E (0, 1J.) We also define P2j := Uizi pj. the set of all pages that their UCB is at least 6'.
Let [yp)pep be the fractional solution. The balanced property requires that, for every set S such that (S) 0 and every index j, the number of pages in S of class least j is the same as in the fractional solution, up to rounding. Formally, we define the balanced property as follows.
Definition 5.2 (balanced distribution). A probability distribution has the balanced subsets property with respect to y, if for any set with ((() > 0, the following holds for all j:
ΣΣ PEP:
Σ
yp
$ Σ [2) PEP:
Σ
Up e S S]
ΣΣ yp 12J P
7

---

Algorithm 2: Randomized rounding algorithm for OWP-UW
Initialization
Let ONF he instance of Algorithm that maintains fractional anti-server allocation {yp} pcP
Define μ
distribution over cache states, initially containing the empty cache state probability
For every p P. se NULL.
Event Function UPONREQUEST(P) called upon request for page p
pass the request for to ONF.
while ONF is handling the request for do // loop of Line 4 in Alg.
if ONF increases y by for some p' P then add to the anti-cache in e-measure of states without p'. call REBALANCESURSSETS.
if ONF decreases yp" by for some p' с P then remove p' from the anti-cache REBALANCESUBSETS.
e-measure of states with p'.
13
if ONF samples puge p' P then // sample due to Line of 6 Alg. provide xp' sample ONF, and xp' NULL. call REBALANCESUBSETS.
rebalance due change in UCBp'.
if s NULL then evict and re-fetch p obtain weight sample W and set sp W ONF requests sample of p then // sample due to Line II of Alg.
18
19
provide sp as sample to ONF, and set Sp NUII. call RERALANCESURRETS, // rebalance due to change in UCBp p-
20
Algorithm 3: Rebalancing procedure for randomized algorithm
Function REBALANCESUBSETT
lct /max be the maximum class that is not balanced.
let /mmn = [log(UCB )7, where UCBmin == minpsp UCBp. for every class j, let Pj := {p P[[oo(UCBB)]]))
for from /max down Jmin do lct Pzj = Up'zj Pj-
let Y, == Eper's Yp-
while 3S s.I. μ(() and IS P (1yll do // iteratively eliminate imbalanced
choose such S that maximizes im Vjj. where m := |s n P=
m 2 > then
Match the ({S) measure of with an identical measure of anti-cache states with at most
[yy]- pages from Pzj-
foreach anti-cache state S' matched with
((S) do
identify page p Pj. such that p S'
remove p from the anti-cache in the measure of S, and insert it into the anti-cache the measure of S'.
if s [Yy] - then
Match the ((S) measure of with identical measure of anti-cache states with least [Y, + pages from Pzj-
17
foreach aati-cache state matched with at measure Xg. $ (S)) do identify page p Pj such that S S.
remove from the anti-cache in the measure of S', and insert it into the anti-cache in the measure of S.

---

Choosing the minimum UCB class in Definition 5.2 and noting that Eperyp 2 through feasibility, immediately yields the following remark.
Remark 5.3. Every balanced probability distribution is also valid distribution.
To follow the fractional solution, we also demand that the distribution μ is consistent with the fractional solution, meaning, the marginal probability in that any page p is missing from the cache must be equal to yp-
Definition 5.4 (consistent distribution). A probability distribution μ on subsets S S P is consistent with respect to a fractional solution {yp) peP for every page it holds that EscrIpes (IS) ypp
In the following we describe the online maintenance of the distribution μt, that yields a distribution satisfying all of the above.
Algorithm overview. The randomized algorithm for OWP-UW is given in Algorithm 2 The algorithm encapsulates an instance of Algorithm T for fractional OWP-UW, called ONF. Upon new page request pr at round r, the algorithm forwards this requests to ONF. As ONF makes changes to its fractional solution, the algorithm modifies its probability distribution accordingly to remain consistent and balanced (and hence also valid).
Upon any (infinitesimally small) change to fractional variable, the algorithm first changes its distribution to maintain consistency: when the fractional algorithm ONF increases the variable yp of any page p' by an e-measure, the algorithm identifies an e-measure of cache states S s P in which there is no anti-server at p' and adds anti-server at p'. The case in which the fractional algorithm decreases variable is analogous.
However, this procedure may invalidate the balanced property. Specifically, for some class j. letting y be the total anti-server fraction of pages of at least class in ONF, there might now be states with [y, + I or [Y, - such pages in the anti-cache. Thus, the algorithm makes call to which restores the balanced property class-by-class, For every class j. the procedure repeatedly identifies violating state S where the number of pages of class 2 j in the anti-cache is not in {[x; 1. [r,]]: suppose it identifies such state with more than [Y,] such pages (the case of less than [r,] pages is analogous). The procedure seeks to move a page of class j from this state another state way that does not increase the "imbalance" in class j. Thus, the procedure identifies a matching measure of anti-cache states that contain at most YX - such pages, and moves page of class j from S to S" for every S' the matched measure; a visualization of the procedure is given in Figure 2 (The existence of this matching measure, as well as page to move, are shown the analysis.) In particular, note that the probability of every page being in the anti-cache remains the same, and thus REBALANCESSBSETT does not impact consistency.
REBALANCESSUBSETT
descending order.
Regarding samples, the algorithm can maintain sample Sp for every page p. A sample for p is obtained upon a request for after p is fetched with probability into the cache, if no such sample already exists (i.e., Sp NUI.I). Whenever ONF requests sample for page p, the randomized algorithm provides the sample Sp. and sets the variable xp to be NULL (we show that &p is never NULL when ONF samples p). A fine point is the sampling of new page in Line of Algorithm I this happens after Line 17 of Algorithm 2
Conclusions
In this paper, we presented the first algorithm for online weighted paging in which page weights not known in advance, but are instead sampled stochastically. In this model, we were able to recreate the best possible bounds for the classic online problem, with an added regret term typical to the multi-armed bandit setting. This unknown-costs relaxation makes sense because the problem has recurring costs; that is, the cost of evicting a page p can be incurred multiple times across the lifetime of the algorithm, and thus benefits from sampling.
We believe this paper can inspire future work on this problem. For example, revisiting the motivating case of managing a core-local I.1 cache, the popularity of page among the cores can vary over time; this would correspond to the problem of ntn-stationary bandits (see, e.g.,(ueer Auer et al. 2019b]aa, Chen et al. (2019), and it would be interesting to apply techniques from this domain to OWP-UW.

---

Finally, we hope that the techniques outlined in this paper could be extended to additional such problems. Specifically, we believe that the paradigm of using optimistic confidence bounds in lieu of actual costs could be used to adapt classical online algorithms to the unknown-costs setting. In addition, the interface between the fractional solver and rounding scheme could be used to mediate integral samples to an online fractional solver, which is common component in many online algorithms.
Acknowledgments
This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement No. 882396), by the Israel Science Foundation, the Yandex Initiative for Machine Learning at Tel Aviv University and grant from the Tel Aviv University Center for Al and Data Science (TAD).
10

---

References
S. Agrawal and N. Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Conference learning theory, pages 39-1. JMLR Workshop and Conference Proceedings, 2012.
S. Albers. Online algorithms: survey. Math. Program.. 97(1-2):3 26, 2003.
doi: 10.1007/
s10107-003-0433-0. URL httL:tttss//do.org////// 1htg//0.0000//00000 0000007-000043330 0436-0
P. Auer, N. Cesa-Bianchi Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47:235-2555 2002a.
P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-77 -7,887777778 2002b.
P. Auer, Y. Chen, P. Gajane, C. Lee, H. Luo, R. Ortner, and C. Wei. Achieving optimal dynamic regret for non-stationary bandits without prior information. In A. Beygelzimer and D. Hsu, editors, Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, volume 99 of Proceedings of Machine Learning Research, pages 159-163, PMLR, 2019a. URL http://proceedinn
mlr www.ppreessvs...e
/t////9//////// w999///er99bbbba auwaalerbbb... html
P. Auer, P. Gajane, and R. Ortner. Adaptively tracking the best bandit arm with an unknown number of distribution changes. In A. Beygelzimer and D. Hsu, editors, Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, volume 99 of Proceedings of Machine Learning Research, pages 138-155 PMLR, 2019b. (RLLitttt//proceeddiie mlr mir.press. v99 309/auerl1 auer19a. html
N. Bansal, N. Buchbinder, and J. Naor. Randomized competitive algorithms for generalized caching. In C. Dwork, editor, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 235- 244. ACM, 2008. doi: 10.1145
1374376.1374412. URL https: org/10 10. 1145/1374376 1374412
N. Bansal, N. Buchbinder, and J. S. Naor. simple analysis for randomized online weighted paging. Unpublished Manuscript, 2010.
N. Bansal, N. Buchbinder, and J. Naor. A primal-dual randomized algorithm for weighted paging. ACM, 1944)449 2012. doi: 10.114572339122.2339122 URL http/s/:s//doi. org/10 1145/233912 2339112 2339126
S. Basu, R. Sen, S. Sanghavi, and S. Shakkottai. Blocking bandits. Advances in Neural Information Processing Systems, 32, 2019.
S. Bubeck, C. Coester, and Y. Rabani. The randomized k-server conjecture is false! In B. Saha and R. A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 581-594. ACM, 2023. doi: 10.1 (0.1145/3564446338881
org/:/io.....///// 100 1111/115441444 3585132
Y. Chen, C. Lee, H. Luo, and C. Wei. A new algorithm for non-stationary contextual bandits: Efficient, optimal and parameter-free. In A. Beygelzimer and D. Hsu, editors, Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, volume 99 of Proceedings of Machine Learning Research, pages 696-726. PMLR, 2019. URL httt::tttoccceeeeeeeeee v99/chen 99. html
mlr .press//
M. Chrobak, H. Karloff, T. H. Payne, and S. Vishwanathan. New results on server problems. SIAM J. Discret. Math., 4(2):172-181, 1991. doi: 10.1137/0404017. URL https:////o org/ 10. 1137/0404011
E. Even-Dar, S. Mannor, Y. Mansour, and S. Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of machine learning research, 7(6), 2006.
A. Fiat and M. Mendel. Better algorithms for unfair metrical task systems and applications. In F. F. Yao and E. M. Luks, editors, Proceedings of the Thirly-Secone Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA, pages 725-734. ACM, 2000. doi: 10.1145/335305.335500 URL hattps://dof org wrw.oo...1111 00.11115333333 335408
11

---

A. Fiat, R. M. Karp, M. Luby, L. A. McGeoch, D. D. Sleator, and N. Young. Competitive paging algorithms. J. Algorithms, 12(4):685 699, 1991. doi: 10.00100199-6774499)9044111 URL https://doi.con org/10.g.11.. (000000660088--67774110001110110
A. Foussoul, V. Goyal, O. Papadigenopoulos, and A. Zeevi. Last switch dependent bandits with monotone payoff functions. In International Conference on Machine Learning, pages 10265-10284.
PMLR. 2023.
S. Irani. Page replacement with multi-size pages and applications to web eaching. In F. T. Leighton and P. W. Shor, editors, Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997, pages 701-710. ACM, 1997. doi: 10.1145/ 258533 258666. URL httphh/tp:///oi.... http::///ooi.o/////// 1 258533 258666
S. Irani. Randomized weighted caching with two page weights. Algorithmica, 32(4):624 640. 2002. doi: 10. 10.10077/004433-00-0000
URL http://////a..oor///./////000000
E. Koutsoupias and Papadimitriou. On the k-verer conjecture conjectuue /. ACM, (2()))91942)9919988888 1995. doi: 10.1145/2 18.2010. UBL.atpsee/ooo..0///00111////
L. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
S. Levine, A. Kumar, G. Tucker, and J. Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643, 2020.
M. S. Manasse, McGeoch, and Sleator. alonpetiiivee for server problems. Algorithmms, 1 (2)2 230, 1990. doi: 10. 901001600198-66774999990000000 URLphtts:: https://o// htg/10.1116//110
D. D. Sleator and R. E. Tarjan. Amortized efficiency list update and paging rules. Commun. ACM, 28(2):202-200 1985. doi: 10.1145/2786.779. URL https:////oo org. 10///11.11 1145/278162... 2793
A. Slivkins al. Introduction multi-armed bandits. Foundations and Trends@ in Machine Learning, 12(1-2):1-286, 2019.
W. R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-294 1933.
N. E. Young. The k-server dual and loose competitiveness for paging. Algorithmica, 11(6):525-54 1994. doi: 10. 189992. URL https::/doi..rgg/ 10t1//000000//F01189999
12

---

A Analysis of the Fractional Algorithm
In this analysis section, our goal is to bound the amount ONF with respect to the UCBs and LCBs
calculated by the algorithm; i.e., to prove Lemma 4.1 Lemma Lemma|C.I and Lemma C.2 from Appendix C then make the choice of confidence bounds concrete, such that combining it with Lemma 4.1 yields the final bound for the fractional algorithm. i.c., Lemma 3.1
Proof of Lemma 4.1 For the sake of this lemma, we assume without loss of generality that the optimal solution is lazy; that is, it only evicts a (single) page in order to fetch the currently-requested page. (It is easy to see that any solution can be converted into a lazy solution of lesser or equal cost.) In the following we present a potential amalysis to prove that ONF = log( + k) OPT + Ur, where Uy is regret term summed over T time steps that will be defined later. To that end, we show that the following equation holds for every round I,
ΔONE, + AQ, log(1 1/n) AOPT, AU,
where AX, is the change in X in time r and cb is potential function that we define next.
Let C² denote the set of pages in the offline (optimal) cache at time 1. The potential function
chose is an adaptation of the potential function used by Bansal et al. (2010), but modified to encode the uncertainty cost for not knowing the true weights. We define it as follows.
4 -2 Σ LCB, log
yp y 1+
(LUCB,-LCB,) (mp - -mp). PEP
PEC;
where UCBp, p. LCB, P are the confidence bounds in time step 1, up is the number of samples of page collected until that point, and mp is the total fractional movement of that page until that point. Note that "p mp [0. IJ. We now show that Equation holld in the three different cases in which the costs of the potential or the regret change. Before moving forward, we define the regret term, denoted U. follows,
2: Σ (UCBp.-- LLCBp.) + +2log(1 1/7) Σ LCBB Pep E=
peP
We note that each time the algorithm gets new sample, np is incremented and W/ increases.
Case 1 - the optimal algorithm moves. Note that a change in the cache of the optimal solution does not affect ONF or Ut and thus AONF All = 0. However, AOPT might be non-zero, as the optimal solution incurs a moving cost; addition, A&d might be non-zero, as the change in the optimal cache might affect the summands in the first term of the potential function.
Thus, proving Equation I for this case reduces to proving AØ, S 2 log(1 + AOPT. Assume the optimal solution moves; as we assume that the optimal solution is lazy, it must be that the requested page P, is not in C7 and that the optimal solution fetches into the cache, possibly evicting (single) page from its cache.
First, consider the case in which there exists an empty slot in the cache, and evictions take place when fetching Pr- In this case, AOPT O; moreover, as C, S C,,, it holds that A& s 0. Thus, Equation ① holds.
Otherwise, at time f, page Pt is fetched and another page p is evicted. Thus, 4OPT wp. For the potential change, p starts to contribute to Φ. In the worst case, yp = O and then Φ is increased by at most P log + 1/m) s 2wp log(1 + 1/n) = log( 1/n) AOPT, as desired.
Case 2 the fractional algorithm moves. In this case, only the potential and the cost of the fractional algorithm change, i.c., AOPT, = sl,, = O. Thus, Equation [I reduces to proving AONF, Ad, S 0 in this case.
There are two types of movement made by the algorithm: the immediate fetching of the requested page Pt, and the continuous eviction of other pages from the cache until feasibility is reached (i.e., there are k anti-servers). First, consider the fetching of p, into the cache; we charge for
13

---

evictions, this action does not incur cost (AONF = 0). In addition, through OPT's feasibility, it holds that P. E Cj. and thus changing yp, does not affect the potential function (AΦ 0); thus, Equation ① holds for this sub-case.
Next, consider the continuous eviction of pages. Suppose the fractional algorithm evicts dy page units, where dy is infinitesimally small. Let S = (p,) {p: yp < J.. Since the fractional algorithm increases yp proportionally to Yp*? for each E S {pt), it holds that, dyp = N LCB, LCBp
yp* dy, for
N = Epes)(p:) yptr Thus, AONF can be bounded as follows. LCB,"
AONF
Σ
UCBpdyp
peStiml
Σ pESMpr)
(LCB, p + (UCB, LCB,))dy,
Σ
(LCB, + (UCB,-UCBH, - LLCB,) 1 yp +1 dy
=
N LCB,
peSt(p))
Σ peSt(p))
1'' +nd
(UCB, LCBp)dyp
N
peSt(p:)
Σ PES\
1''
+n
IUCBp LCBBLBBP) LCBp)dyp
N
PEp
(a)
where the final equality stems from having dyp = for every p S {pr}. We now bound the term (a) using similar arguments to those presented in Bansal et al. 2010 We present them below for completeness.
(a) = E
1 + + n)dy s (1S) k)
N dy + ((S) - 1)m
dy s
2([S) - k)
dy.
N
N
peStIp))
where the first inequality implied since yp = for $ S. which yields that
Σ yp S Σ yp Σ yp Σ y p (IP) k) (IP) - (S)) |S] k.
PEST(p.)
PcS
pep
PdS
and the second inequality implied as (x 1)7 S k for any 2 k + 1 and using that |S| 2 k 1.
Next, we upper bound Ad, The rate of change in the potential with respect to yp
dΦ; = =-2 - LCBp dyp yp., +1
(UCB, LCBp))
The non-trivial part in the above calculation is that LCUC (mp (UCB, - LCB,). dyp This is true since up uncorrelated with the change in yp. however, mp is increasing with with respect to yp in l-linear ratio. Using the above get that
A0, Σ
d
dyp
dy
pEp
--2
LCBp
1 1yp +1 dy
Σ
(UCB, -LCB,) dyp
Yp + n LCBp
pesic
pep
Σ
dy
Σ (UCB, - I.CBp) dyp
= -
N
PESIC;
pep
-2 I dy
Σ (UCB, LCBp) dyp
Thus, 4ONF, Ad; 5 0, required.
14

---

Case 3 the LCBs are updated (a new sample is processed). Suppose the algorithm samples page p for the i'th time, and updates U.B,, LCBB, accordingly. Note that this sample does not incur any cost for the fractional algorithm or optimal solution, and thus AONF = AOPT = O. Thus, proving Equation I reduces proving AΦ AU for this case. Recalling the definition of U. it holds that
NU = (UCBp.. p.. LCB p.i) log (1 1/m) (LCB LCB p.I.p..
Denote by np. mp the variables of that name prior to sampling p: note that mp remains the same after sampling, while up is incremented to ni, np + 1. Moreover, note that sampling always occurs when mp = mp- Thus, the change in potential function is bounded as follows.
AΦ 2 log( 1//) & C,](L L. UCBp,t -CBBp
log(1 1/m) (LCBp,: ( LCBp,
UCBp,, LCBp,i
where the second inequality is due to the LCBs being monotone non-decreasing.
B Proofs from Section
B.1 Analysis and Proof of Lemma 3.2
Throughout this subsection, we assume the good event 8; that is, the UCBs and LCBs generated by ONF throughout the algorithm are valid upper and lower bounds for the weights pages.
In this subsection, we analyze Algorithm 2 and prove Lemma 3.2
We start by proving that the algorithm is able to provide a new sample whenever the fractional algorithm requires one. Proposition B.1. Algorithm provides page weight samples whenever demanded by ONF.
Proof. We must prove that whenever sample of page p is requested by ONF, holds that the variable sp in Algorithm is not NULL. Note that Algorithm| 2 samples Sp at the end of request for p. Now, note that:
The first sample of p is requested after the first request for is handled by ONF, and thus after p sampled.
Between two subsequent requests for samples of by ONF, the eviction fraction mp increased by But, this cannot happen without request for the interim; this request ensures that sp NULL, and thus the second request is satisfied.
Combining both cases, all sample requests by ONF are satisfied by Algorithm
Next, we focus on proving that the distribution maintained by the algorithm is consistent and balanced (and hence also valid). To prove this, we first formalize and prove the guarantee provided by the REBALANCESUBSETT procedure. To this end, we define amount quantifying the degree to which given distribution.
a class is imbalanced Definition B.2. Let μ be distribution over cache states, let {rr} per be the current fractional solution, and let be some class. We define the imbalance of class j μ to be
Σ (S)) max {|s P [ [r.] -
SCP
Definition B.2 quantifies the degree to which given class is not balanced given distribution; one can see that it the class is balanced, this amount would be O.
called, and let μ.. p³ be the distributions before and after the call REBALANCESUUSSETS, respectively; let Jmax. be the maximum non-balanced class in μ.
Lemma B.3. Suppose REBALANCESU
Suppose that (a) z is consistent, and (b) there exists O such that the imbalance of any class j $ Jmax in μ at most e. Then, holds that şí both consistent and balanced. Moreover, the total cost of REBALANCESUUSETT is most 12e 1eg-6hon 6
15

---

Proof. The rumning of REBALANCESSBSETSS consists of iterations of the For loop in Line 5 we number these iterations according to the class considered in the iteration (e.g., "Iteration i" considers class i). We make claim about the state of the anti-cache distribution after each iteration, and prove this claim inductively; applying this claim to the final iteration implies the lemma. Specifically, where Jmax as defined in the lemma statement, for every S Jmax consider the distribution immediately before Iteration i, denoted μt: We claim that (a) the μpj is consistent, (b) all classes greater than i are balanced in μ4i and (c) classes at most have imbalance at most 3/mls in μ4: Where Jmin is the minimum class, note that μ' = jmin II, and that this claim implies that j is consistent and balanced. (Note that the claim implies that class Jmin is balanced, which also implies that all classes smaller than Jmin are balanced.).
We prove this claim by descending induction on i. The base case, in which i = fmaxs is simply restatement of the assumptions made in the lemma, and thus holds. Now, assume that the claim holds for any class i I Juax; we now prove it for class i i- 1.
Consistency. First, as we" ve assumed that μi is consistent, note that Iteration does not change the marginal probability of a given page being in the anti-cache, as pages are only moved between identical anti-cache measures. Thus, the anti-cache distribution remains consistent at any step during Iteration i; in particular, M is consistent.
Existence of destination measure. Next, observe that every changes in Iteration consists of identifying& a measure of a violating anti-cache, and matching this measure to an identical measure of anti-cache states to which pages can be moved. To show that the procedure is legal, we claim that this measure always exists. Consider such a change that identifies violating anti-cache S, and let ğ be the distribution at that point. Assume that S is an "upwards" violation, i.e., [V;] where m : 1S 0 lerl: the case of a "downwards" violation is analogous. Note that consistency implies that -s 15' n Pzil Y,. Also note that was chosen to maximize |m Yil, i.e., the distance from the expectation. Thus, there exists a measure of at least A(S) of anti-caches S' such that [S' n Pzil < Y; (and thus |S' Pz1 < [Y1 1, as required).
Existence of page to move. After matching the aforementioned S to some S', we want to identify some page p Pi such that p S','', so can move it from the measure of S to the measure of S Indeed, from the choice of 5 and 5", it holds that |S Pzil 2 [v,]+ + 2 IS' n Pzil + 2. But, from the induction hypothesis for Iteration i, class i+ was balanced in μ4, and thus remains balanced every step during Iteration i (as this iteration never moves pages of classes i + and above). This implies that [S 121+1l [Y,m] IS' O O. 22111 1. We can thus conclude that there exists p P, (S((S)
as required.
Balanced property. Next, we prove that in 1i-1 after Iteration i, class i is balanced, and the imbalance of any class j < i is at most e 3 Consider any step in Iteration i, where a measure x of a violating state identified; then, a page is moved from measure x to another measure x. The induction hypothesis for Iteration implies that the imbalance of class i at μæ is at most 3/max Note that:
1. This step decreases the imbalance of class i by at least x, as it decreases the imbalance in the violating state, but does not increase imbalance in the matched measure.
2. This step can increase the imbalance of a class j < by most 2x, in the worst case in which moving the page increased imbalance in both measures of x.
As a result, we can conclude that for M;-1, at the end of iteration i, class i is balanced, while the imbalance of every class j < i increased by at most 2 e 3 -i, Combining this with the hypothesis for iteration i, the imbalance of every class j at fi-1 is most e 3 3imx-i e. 3 -(--1) as required.
This concludes the inductive proof of the claim.
Cost analysis. As mentioned before, every step in Iteration reduces imbalance at class by (at least) x, where x is the measure of the chosen violating anti-cache state. The cost of this step is the cost of evicting a single page in P: from a measure x; as we assume that the weight of page is at most its UCB, this cost is at most x 6'+1_ The inductive claim above states that the imbalance of class i the beginning of Iteration is at most e 3/m0-t thus, the total cost of Iteration is at most = (6mmx)) /2/ -1 Summing over iterations, the total cost of REBALANCES SUBEES /1mmst//2/mm
//m 6 e.
16

---

is at most:
Jinas
6lexet) /2 2 12E 6
Jain
We can now prove that the distribution is consistent and balanced.
Lemma B.4. The distribution maintained by Algorithm 2 both consistent and balanced.
Proof. First, we prove that the distribution is consistent. Indeed, note that consistency is ex- plicitly maintained in Lines 9 and 12 and that Lemma B.3 implies that the subsequent calls to REBALANCESUBSETS does not affect this consistency.
As the distribution is consistent at any point in time, Lemma B.3 also implics that it is balanced immediately after every all to REBALANCESUBSETTS such a call, the distribution is always balanced after every request.
the handling of every request ends with
At this point, we've shown that Algorithm 2 legal: it maintains valid distribution (through Lemma B.4 and Remark 5.3), and it provides samples to ONF when required (Proposition B. remains to bound the expected cost of
thus, is valid randomized algorithm for OWP-UW. Algorithm 2. thus proving Lemma 3.2, recall that this bound in terms of ONF, the cost of the fractional algorithm in terms of its UCBs rather than actual page weights.
Proof of Lemma 3.2 We consider the eviction costs incurred by Algorithm 2 and bound their costs individually.
First, consider the eviction cost due to maintaining consistency Line | (note that Line 12 only fetches pages, and incurs cost). An increase of in Y'p causes eviction of p' with probability: the expected cost of E Wp' can be charged to the eviction cost of -UCBp' incurred in ONF, and thus the overall cost due to this line is at most ONF.
Next, consider the cost due to eviction during sampling (Line 17 Observe page p E that is evicted in this way; the cost of this eviction is wp- For the first and second samples of p. we note that Wp 1; summing over p P, the overall cost of those evictions samples of p. note that for i > 2, the i'th sample of is taken when mp 2, charge this sample to the fractional eviction that increased mp from i 2- 1]. Thus, we can 2, which costs UCBp, p.
most 2n. For subsequent
Thus, the overall cost of this sampling is at most ONF 2n.
It remains to bound the cost of the REBALANCESSURSETS procedure. First, consider the cost of REBALANCESuBSETT due to sampling (Lines) 16 and 20). Consider the state prior such call; some page p has just been sampled, possibly decreasing UCBp p and decreasing the class of page p. which could break the balanced property. Specifically, i, be the old and new classes of p. where i' < i. Then, imbalance could be created only in classes j E (i' l.... ./). In such class j. both Y; could decrease, and [S i Pz/l could decrease for any anti-cache state S. However, as only changed class, one can note that the total imbalance in any such class j is at most 1. Thus, Lemma guarantees that the total cost of REBALANCESURREETS is most 12 6' 12 UCBp- p- Using the same argument as for the cost of sampling, the total cost of such calls at most. 12ONF + 24n.
page
Now, consider a call to REBALANCESUBSETS in Line 10 A page p' was evicted for fraction in ONF, and an e measure of p' was evicted in the distribution. Let j be the class of p': there could only be imbalance in classes at most j. For any such i S j. Y, increased by and |S n Peil increased by in most measure of states In addition, let Y Y := Y,- be the old and new values of Y;- Consider the imbalance in class i:
1. If [Y:] [ + 1, then the imbalance of class i can increase due states where Is Pz/l= |r-] becoming unbalanced. But, due to consistency, the fact that Y,- 2 [r--] implies that the measure of such pages is at most thus, the imbalance grows by at most
2. The adding of page p' to e-measure of pages add imbalance of at most
17

---

Overall, the imbalance in classes at most j prior to calling REBALANCESURSETS is at most 2c. Through Lemma B.3 the cost of REBALANCESUBSETS is thus most 24e 6', which is at most 24e UCBBp' But, the increase in ONF due to the fractional eviction is at least UCBp'; p'; thus, the overall cost of REBALANCESUBSETT called in Line is at most 24 ONF.
Finally, consider call to REBALANCESURRETS in Line 13 called upon decrease in Y'p of e for some page p'. Using an identical argument to the case of eviction, we can bound the cost of this call by 24 times the "fetching cost" of UCBp' Now, note that the fractional fetching of page exceeds the fractional eviction by at most I; thus, the total cost of such calls is at most 24ONF 24n.
Summing all costs, the total expected cost of the algorithm is at most 62ONF + 50n.
B.2 Proof of Theorem 1.1
We now combine the ingredients in this paper to prove the main competitiveness bound for Algo- rithm
Proof of Theorem 1.7 First, assume the good event & Combining Lemma 3.2 Lemma 3.1 and
Lemma C.2 it holds that
B[ON] s O k) OPT(() + Ö(V77)
Next, assume that & does not occur. Upper bound the cost of the algorithm by (n) per request, as in the worst case, the algorithm replaces the entire cache and samples each page in P once. Thus, an upper bound for the cost of the algorithm is (nT)). But, through Lemma C.I. the probability of & not occurring is at most nT' Thus, we can bound the expected cost of the algorithm as follows.
B[ON] & Pr[E] (o(log k) OPT(2) O(VnT) Pr(-81-0(11)
$ O k) (PT(() Ö(VNT).
C Choosing Confidence Bounds and Bounding Regret
In this section we define the UCBs and LCBs, prove that they hold with high probability and bound the regret term.
Let w' be the i-th sample of page For the initial confidence bounds, we sample each page once and set LCBp,1 . w/ UCBP,, Once we have 1 samples of page p. define the confidence bounds as follows. Let Wp.i E w/ be the average observed weight, and Ep./ log(4n²T*)
2r be the confidence radius. Then, we set LCBp.t max p. and UCB p. min(UCBp.iiI) p. Ep.i). The following procedure updates the confidence bounds online.
p. Wp. - Ep.i)
We show that the confidence bounds indeed bound the true weights with high probability (Lemma C.I and then bound the regret term (Lemma C.2).
Lemma C.1. Let up be the final number of samples collected for page p. With probability at least
1 n the following properties hold.
1. 0 LCBp.1 p. LCBB LCBB p.mp Wpp for every page p-
2. wp 1 =UCBp.np p. UCB UCBp.pp-1 .... UCB,, p. for every page
3. UCB p.j LLCBp, S 2Ep,i for every page p and i e [1,
Proof. By definition, the LCBs monotonically non-decreasing and the UCBs are monotonically non-increasing. Moreover,
UCBp.t LCB i UCC. + Ep.i) max LCB p.i-1. Wp.i Ep.i) p..-,,,.1,
I (wp,i p.i Ep.) - (wp,: Ep.i 2Ep.i.
18

---

Algorithm 4: Optimistic-Pessimssie Weights Estimation Procedure
Function UPDATECONFBOUNDSII pt update confidence bounds for p upon sample 1 this is the first sample of p (i.e, "p 1) then define Wp + Wp-
define LCBBp < 2n-7
W
define UCBp p c- 1. else
(np (np-1)upthp
update mean estimation Wp
log (gg(4'''))
define Ep V
2np
set LCBp c max LCB wi E
10
set UCBp min UCB p. Wp + Ep)
Thus, remains show that
2n-T w Wp and that w s Ep., for every page p and i E [1 with probability - nT For the first event, by Markov inequality and union bound over all the pages p E P. have
P pp 2n²T W Wp P[pp P. w/ 2n -wpl
2n
2nT
For the second event, by Hoeffding inequality and a union bound over all the pages P, all the time steps E [1, 7] and the possible number of samples for each page E [1, nT], we have
p[pp e Piie [1,7]. Iwp w wp.il > Ep.i] n212 2e 2ie = n2 1
1
2n273
2nT
The proof is now finished by taking union bound over these two events.
Define 4 = Epep E (UCBp. -CCB,, + 2logg(1 + 1/m) Epe LCBp, the regret term used in Lemma 4.1
Lemma C.2. Under the good event of Lemma C.1 it holds that
u s 8 log(nT) Ö(VTT).
Proof. The following holds under the good event.
Up
u = Σ
(CCB - LCBp.)) +2log(1 1//) Σ
LCBp
pep
pep
2 Σ
Ep.i +1ogg(1 1/7) Σ Wp
(Lemma C.1
pep t=l
pEp
= 2 Σ Rp
log 4n
2 log( 1 + 1/n) Σ wp
2i
PEP i=1
pep
2oo 773
2n log(1 1/n)
(w S 1)
PCP i=1
2 1og(4n273)
Σ Vnn + 2n log + 1/m)
E 1 Vi 2vD)
s 2 2nT 2 log(4n 2n log(1 + k),
where the last inequality holds by Cauchy-Sehiee Schwarz and our choice of 1) = 1/k. Lastly, the stated upper bound follows since k S n and n s VnT.
19

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We provide an algorithm for the problem of online weighted paging with unknown weights, and analyse it. See Section 1.1 for summary of our results, that will be proven throughout the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [NA]
Justification: This a theory paper that present an algorithm for the online weighted paging where the weight are unknown and prove the stated bounds. We do not believe there are additional limitations discuss.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
20

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All assumptions are stated in the statements of the theorem and related lemmas. A proof is provided for each theoretical claim.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: No additional information is required to obtain the results in this paper, which are theoretical. A full pseudocode for the algorithm appears in the paper and appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
21

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not contain experiments at all.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://mips.co
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
7 //nips. htcp//blcc/gudeeeeeeeeeeieeeeeee
ssiobbiiiisiooccccyy. for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
The paper does not contain experiments at all.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
There are no experiments in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
22

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
There are no experiments in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http://aaaaaaacccpppoaa/acccctta
Answer: [Yes]
Justification:
We reviewed the code of ethics and concluded the paper conforms to it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
This paper describes algorithm for the online weighted paging problem,
where the weights are unknown, and analyse it. The paper is theoretical. Thus, we do not predict any societal impact due to this work.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
23

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper is thcoretical. No data or models are associated with it.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper is theoretical. No existing assets are associated with it.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
24

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper is theoretical. No new assets are released it.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper is theoretical. It does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper is theoretical. It does involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
25

---

For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
26


Reviews:
[{"review_id": "s15GwXCtpF", "reviewer": "Reviewer_Yutu", "summary": "Author consider caching with stochastic weights. In particular,\nthe cost incurred by the algorithm at eviction of a page p\nis drawn independently from a fixed distribution D_p\nwhich is different for every page and is not known to the algorithm in advance.\nAuthors propose an algorithm with guarantees which combine both\ncompetitive ratio and regret. Authors claim that neither regret nor competitive\nratio are possible on their own.\nTheir algorithm is a modification of the classical algorithm\nby Bansal et al. for weighted paging, incorporating upper and lower confidence\nbounds on the average weight of the page.\nThe more challenging part seems to be randomized rounding, where they\nhave to deal with the changes of the upper confidence bounds and such\nelement was not present in the original paper of Bansal et al.", "questions": "* Please comment on the last two weaknesses mentioned above.", "limitations": "Authors do not discuss possible difficulties in implementing their algorithm\nin CPU caches although they use such use case as a main motivation.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* Problem seems interesting\n* Result is non-trivial from technical point of view", "weaknesses": "* I find the framing of their result in the context of hierarchical caching\nand CPU caches very unfortunate for several reasons:\n\n(1) hierarchical caching is already studied (see work of Bansal, Buchbinder, Naor SICOMP'12). Authors do not seem to be aware of this.\n\n(2) It is completely unclear why should there be an underlying distribution\nof the cost of loading each page in a hierarchical (or multi-level) cache:\nIt is enough that the algorithm operating on different levels of the cache\nare mis-aligned in some way to make weights of the pages\nadversarial instead of stochastic.\n\n(3) I cannot imagine implementing anything resembling their approach\nin CPU caches.\n\n* Provided justification of the optimality of the presented results\nis very informal. It is just a few lines.\nIn particular, authors argue about the necessity of the regret term using using\nlower bounds for bandits. However, their input is stochastic which\nallows much better regret bounds when the mean weights of the pages\ndiffer significantly. On the other hand, if the weights of the pages are\nsimilar, it is easy to achieve good competitive ratio.\n\n* Statements of their results are not completely clear: E.g., what is Q in\nTheorem 1.1? Theorem says it is an \"input\":\nIs it composed of the request sequence and the distribution of\npage weights, or does it contain also the realization of the page weights?\nWhat is OPT(Q) then? I do not see these things explained even in preliminaries.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful feedback, please see below our comments for the concerns raised.\n\n**Regarding (1):** _“Hierarchical caching is already studied”_. \nAssuming you refer to [1]: this paper studies generalized weighted paging, in which each page has both a weight and a size demand imposed on the cache. Their only reference to storage hierarchies refers to weights (not sizes); thus, we interpret the reviewer’s comment as claiming that our motivating example is captured by standard weighted paging with known weights. \nTo illustrate why this is not the case, note that in standard weighted paging, different pages have different weights, but each specific page has the same weight over time. In our motivating example, this is not the case: the same page can alternate between the main memory (fetching cost 1) and the L2 cache (fetching cost epsilon << 1). This motivates learning a page’s expected fetching cost over time, which is the crux of our model. \n\n\n**Regarding (2):**  _“...why should there be an underlying distribution of the cost of loading each page in a hierarchical cache”_. \nOur goal in this work is to remove the commonly used known-eviction-costs assumption in online weighted paging. Our motivating example refers to the aforementioned cache hierarchy, in which the L2 cache holds pages with probability proportional to their demand by the individual cores; we believe this is a reasonable assumption to make. We agree that the requested computation could in theory “game” the L2 cache; but, we don’t think encapsulating this (arguably somewhat pathological) case would make our motivating example more compelling.\n\n**Regarding (3):** \n(a) _“I cannot imagine implementing…”_. \n This paper, as previous works in this research field, is theoretical. Our algorithm is not claimed to be practically implementable, which also resembles previous works.\nThe only inefficient component in our algorithm is the rounding scheme, as it performs infinitesimal iterations, similar to the original rounding scheme proposed by Bansal, Buchbinder and Naor (FOCS’ 07).\n“Justification of the optimality … is very informal”. Our upper bound combines both the element of learning the page weight, which yields a regret term and the element of planning a close-to-optimal eviction strategy, which yields a competitive ratio term. We claimed that each term separately is optimal, and the combination of both is necessary. As you mentioned, our bounds provide a trade-off between the regret caused by the unknown costs and a competitive ratio w.r.t the optimal algorithm that knows the true expected eviction costs.   \n \n(b) _“What is $Q$ in Theorem 1.1?”_. \nThe overwhelming majority of work in randomized online algorithms deals with oblivious adversaries; this is also the case in this work. In particular, the input $Q$ consists of a sequence of $T$ requests for pages, where every page has an associated weight distribution; the oblivious adversary commits to this input. When the algorithm processes input $Q$, upon evicting a page, the algorithm obtains an independent sample from the weight distribution of that page.\n\nWe would be happy to elaborate on any issue during the discussion phase. If we’ve addressed your remarks to your satisfaction, we would be happy if you considered revising your merit score accordingly.\n\n[1] \"Randomized competitive algorithms for generalized caching\", Bansal, Buchbinder & Naor, 2012.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mgvuCMK1yO", "reviewer": "Reviewer_qj5j", "summary": "The paper studies a the online paging problem where the weights to retrieve a items are independent random variables with potentially different distributions. The paper introduces an algorithm whose expected performance differ from the optimal one by a multiplicative factor (logarithmic in the size of the cache) and an additive term (sublinear in the number of the requests).", "questions": "See questions above.", "limitations": "The computational complexity of the algorithm is not discussed. This is important, in particular if, as I think, the algorithm relies on solving some differential equations.", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "If correct, the paper makes a very interesting advance on an important theoretical topic. The authors position well the paper in the existing literature.", "weaknesses": "I found this paper the most difficult to evaluate. I feel NeurIPS may not be the most suited venue for such work, both for its theoretical focus (it seems more a STOC-paper) and the 9-page limit which forced the authors to compress much their reasoning. Probably for this reason, as well as some disorganization in the presentation, I was not able to figure out how the algorithm really works as well as to follow some more technical arguments. I provide some specific comments below\n\nDoubts\n- about algorithm 1, what is really behind \"continually increase\" at line 4, should we assume that that y_p and m_p are updated according to differential equations? This seems to be supported also by later statements like at line 276 \"upon any (infinitesimally small) change to a fractional variable\"\n- I was not able to understand the reasoning about why the problem may not exhibit sublinear regret without a competitive ratio (point b at page 2) \n- in section 1.2, the paper argues that the solution cannot be built in the standard way by combining a solution to the fractional problem and a rounding scheme. I was not able to follow the reasoning in lines 86-94. Even more, because the proposed solution combines a solution to the fractional problem and a rounding scheme\n- in footnote 2, \"note that k \\le \\sqrt{nT}\", I did not get if this follows from the previous reasoning or it is an implicit assumption that T is large enough.\n- algorithm 2, what does it mean line 9 \"add p' to the anti-cache in an \\epsilon-measure of states without p'\"? If find this kind of expressions too vague.\n- lines 254-255, there is probably an error, how can be UCB_p between 6^i and 6^{i+1} if, as observed in the same line UCB_p is between 0 and 1?\n\nMotivation\n- I find the motivation in terms of a cache inserted in the a hierarchy of caches quite weak. The content stored at caches of higher level would be determined by the caching decisions at lower levels. It would the not lead to the random weights considered in this paper.\n\nConfused presentation\n- the fact that costs may be considered to be paid upon eviction rather than upon fetching is mentioned in footnote 2 at page 4, but it is already implicitly used at page 2 when explaining why the problem cannot admit logarithmic competitive ratio without regret\n- the paper starts talking about moving fraction and servers at line 166 before referring to the parallel with the k-server problem\n- the (huge) caption of figure 1 refers to the \"consistency property\" and the \"subset property\". The first one is never really formally defined. The second one is only introduced two page later.\n- in the caption of figure 2, there is a reference to \"class i\" but this is only introduced at page 8. Also note that there are two classes i P_i and P_{\\ge i}\n\n\n\nMinor\n- the problem is sometimes referred to as OWP-UW, others as UW-OWP\n- line 95: \"the and rounding scheme\"\n- footnote 1: \"known in advanced\"\n- in the figures the lables of the different subfigures (e.g. a, b, c, d in figure 1 are missing)\n\nUpdate after rebuttal\n- the authors have addressed some of my technical questions and I have increased the score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their thorough assessment and comments. Here is our response to the points raised.\n\n**Suitability for NeurIPS**: we note that theory papers considering online caching/paging have appeared in ML conferences when combined with an ML-related theme. See for example [1,2,3,4,5], which are theory papers that augment caching/paging with ML predictions, and have appeared in ICML. In our case, multi-armed bandits are clearly appropriate for NeurIPS (in fact, they constitute a primary area). Thus, we believe that NeurIPS is the appropriate venue for this paper.\n\n**Computational tractability**: please see the general rebuttal. In short, the continuous presentation of the algorithm (also chosen for previous work) can easily be replaced with a computationally efficient discrete process. \n\n**Regret lower bound**: the described construction implies that for every randomized algorithm $ALG$ there exists an input such that $OPT = O(T/(k \\log k))$ and $E[ALG]=\\Omega(T/k)$. Thus, $E[ALG]-OPT$ (i.e., the regret) is at least $\\Omega(T/k)$; that is, the regret grows linearly in $T$.  We intend to formalize this further in the camera-ready version; see general rebuttal. \n\n**Fractional+rounding framework**: The point in Lines 86-94 was that in most algorithms involving fractional+rounding schemes, the integral problem immediately induces a fractional problem, such that the fractional solver is competitive w.r.t. this fractional problem, independently of any “downstream” rounding scheme. This is the case for Bansal, Buchbinder and Naor’s fractional solver for online paging with known weights. But, for unknown weights, no fractional solver can be competitive without learning about page weights – and this is done through sampling pages integrally, which cannot be done by a fractional solver. Thus, the interaction between the fractional solver and the rounding scheme is crucial even for the fractional solver itself to have any competitiveness guarantee. Indeed, one of the main contributions of this paper is devising an interface between the fractional solver and the rounding scheme that enables sampling page weights when needed. \nThank you for this input regarding writing clarity, we’ll improve this paragraph in the camera-ready version. \n\n**Additional notes**:\n1. _\" note that $k \\le \\sqrt{nT}$\"_: as noted in Line 146 in the preliminaries section, it holds that $k<n$ (otherwise the problem is trivial as all pages can be simultaneously held in the cache). Also, as $n$ is the number of requested pages and thus $n \\le T$, it also holds that $k<T$. The observation follows. \n2. _\"add $p'$ to the anti-cache in an \\epsilon-measure of states without $p'$\"_: In keeping with previous work on online weighted paging, our randomized algorithm is described as maintaining a distribution over cache states at any point in time; of course, in practice, only a single state is held by the algorithm and is updated as the distribution changes. For example, if the algorithm holds anti-cache state $S$ which has measure $x$ in the distribution, and the distribution is then updated such that $y<x$ measure of state $S$ receives page $p’$, then page $p’$ will be added to the anti-cache state with probability $y/x$ to maintain consistency. \nWhile this is consistent with previous work, we agree that this should be made more explicit; we will do so in the camera-ready version. \n3. Lines 254-255: there is no mistake here. The classes of values between $0$ and $1$ correspond to non-positive values of $i$. \n\nAs for the other remarks regarding writing, thanks for bringing those to our attention; we will modify the paper accordingly for the final version.\nWe hope the above has satisfied your concerns and questions, and that you positively consider increasing your assessment.\nWe, of course, will happily address any further questions you may have.\n\n\n\n\n[1] \"Paging with Succinct Predictions\", Antoniadis, Boyar, Eliáš, Favrholdt, Hoeksma, Larsen, Polak and Simon, ICML 2023\n\n[2] \"Parsimonious Learning-Augmented Caching\", Im, Kumar, Petety and Purohit, ICML 2022\n\n[3] \"Robust Learning-Augmented Caching: An Experimental Study\", Chłędowski, Polak, Szabucki and Żołna, ICML 2021\n\n[4] \"Online metric algorithms with untrusted predictions\", Antoniadis, Coester, Elias, Polak and Simon, ICML 2020\n\n[5] \"Competitive Caching with Machine Learned Advice\", Lykouris and Vassilvitskii, ICML 2018", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TdIeEYyPYv", "reviewer": "Reviewer_WtQQ", "summary": "The paper addresses the problem of online weighted paging with eviction costs drawn from unknown page-dependent distributions. As evictions occur, the authors demonstrate how to learn an effective eviction strategy online using previous cost samples, framing this as a multi-armed bandit problem. They first approach a fractional relaxation of the problem, then apply a rounding technique to derive a randomized algorithm for the original problem. The resulting algorithm incurs an expected cost of $O(\\log k) \\cdot \\text{OPT} + O(\\sqrt{nT})$, where $k$ is the cache size, $n$ is the number of pages, and $T$ is the number of time steps.", "questions": "Since the algorithm only chooses which of the $k$ pages in the cache to evict, would it be possible to improve the regret term in Theorem 1.1 and have instead a term of the form $O(\\sqrt{f(k,n) T})$, with $k \\leq f(k,n) < n$? If not, can you prove that the bound $O(\\sqrt{nT})$ is the best possible for any values of $n$ and $k$?", "limitations": "The assumptions of the theorems are clearly stated.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "* The paper is well-written and well-organized.\n* The setting is both well-motivated and theoretically interesting, as it combines techniques from competitive analysis and regret analysis.\n* The main result is strong and might inspire future work in the field of online algorithm design.", "weaknesses": "I do not see any major weaknesses in this paper, but there are a few minor ones:\n* Although the setting is different, the paper is closely related to the framework of learning-augmented algorithms. I suggest that the authors mention this connection in the related work section.\n* A very similar setting has been studied in \"On Preemption and Learning in Stochastic Scheduling\" (ICML 2023) for the non-clairvoyant scheduling problem, which also couples the analyses of the competitive ratio and regret. Maybe this should be cited as a related work.\n* While the main contribution is theoretical, it would be nice to conduct a few experiments to demonstrate how the proposed algorithms compare to other benchmark algorithms where the weights are known", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the encouraging review, as well as the thoughtful comments. Please see below our response regarding the weaknesses and questions mentioned.\n\n_“… the paper is closely related to the framework of learning-augmented algorithms. I suggest that the authors mention this connection in the related work section.”_ \\\nThanks for this remark, we’ll explore the connection between this problem and learning-augmented algorithms in the related work section. \n\n_“...it would be nice to conduct a few experiments…”_ \\\nWe’ll consider adding an experimental section towards demonstrating the applicability of the algorithm. We note that in bandit papers that focus on proving regret bounds, experimental sections are usually optional. (Unlike, e.g., learning-augmented online algorithms, where empirical evaluations are customary for ML conferences.)\n\n_“Since the algorithm only chooses which of the 𝑘 pages in the cache to evict, would it be possible to improve the regret term in Theorem 1.1 and have instead a term of the form $𝑂(\\sqrt{𝑓(𝑘,𝑛)𝑇})$, with $𝑘≤𝑓(𝑘,𝑛)<𝑛$? If not, can you prove that the bound $𝑂(\\sqrt{𝑛𝑇})$ is the best possible for any values of 𝑛 and 𝑘?”_ \\\nAs mentioned in the lower bounds described in “our results”, in the regime that allows a competitive ratio of $\\Theta(log k))$, there is a lower bound on regret of only  $\\Omega(\\sqrt{T})$. It could be the case that the $\\sqrt{n}$ term in our $O(\\sqrt{nT})$ regret bound could be improved upon; as this is the first work on this problem, we did not focus on obtaining tight bounds. However, we remark that $\\Theta(\\sqrt{nT})$ is the optimal regret bound for standard MAB, and we would thus be surprised if a significant gap were obtained for OWP-UW. \n\nWe thank you again for your positive assessment and hope the above has satisfied your concerns. We would be happy to address any further questions you may have.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gji8fflTQA", "reviewer": "Reviewer_MmEo", "summary": "This paper is the first to model and study to the online weighted paging problem with unknown weights. In this model, the weights $w_p$ of pages are initially unknown, and the eviction cost is drawn from an unknown distribution with an expectation equal to $w_p$. This study extends previous research on online weighted paging with unknown weights by integrating concepts from online learning.\n\nThe authors present an algorithm that achieves the performance bound as follows:\n$$\nE[ALG]\\ \\leq O(\\log k) OPT + \\tilde{O}(\\sqrt{nT}).\n$$\nRemark that $O(\\log k) is the competitive ratio in the known-weight setting. The proposed solution comprises two main components: a fractional algorithm and a rounding framework. The fractional algorithm is designed to approximate the optimal cost, while the rounding framework ensures consistency with the fractional solution through a rebalancing routine. The methodology for the fractional algorithm and the rounding and rebalancing framework are from [Bansal et al. 2010] and [Bansal et al. 2012]. Additionally, the weight estimation utilizes a classical Upper Confidence Bound (UCB) method from the multi-armed bandit problem in online learning. It is a non-trivial combination of the two techniques.", "questions": "In section 5, the author mentions that they need a more robust rebalancing procedure. What is the detailed difference between it and the previous approach? Can you give some more explanations?\n\nIt seems that the algorithm runs really slow because of the continuous rebalancing step. Can you remark on the running time of the algorithm?", "limitations": "The author does not address the limitations of the proposed algorithm. The efficiency of the algorithm is not considered. Given that the algorithm maintains an exponential number of subsets $S \\subset P$ and may adjust some $\\mu(S)$ each time an $\\epsilon$ fraction of $\\mu(S)$ changes, the running time may be quite large.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper presents their motivation for studying the new model clearly, using the example of multi-level cache structure as a compelling rationale. The proposed model is clean, providing a robust foundation that is likely to inspire future research.", "weaknesses": "The presentation in section 5 is not clear and may only be reader-friendly to those familiar with it [Bansal et al. 2012]. We may need a high-level idea and some introductions, like anti-cache, before presenting the pseudocode.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful comments and supportive review.\n\nWe take into account the comment regarding the presentation in Section 5. In the final version of the paper, we will edit this section to be more clear and emphasize high-level ideas.\n\nRegarding your question about our rebalancing procedure, this procedure is different from that of Bansal, Buchbinder and Naor [2012] in the following ways:\n1. Their procedure had to maintain the balanced property only upon changes to the distribution towards maintaining consistency (e.g., a certain probability mass gaining/losing a page). Our rebalancing procedure must also handle the case in which pages change class due to changes in their UCB (as page classes are not constant in our algorithm). \n2. A technical observation: note that the rebalancing procedure fixes the imbalance at every level, in descending order. (The imbalance is the striped area in Figure 2.) However, fixing the imbalance at level $i$ can increase the imbalance at levels $\\le i-1$. In BBN, after fixing an imbalance of $x$ at level $i$, the imbalance at levels $\\le i-1$ can be seen to be at most $x$. However, in our case, the imbalance at levels $\\le i-1$ can be at most $3x$; i.e., the imbalance grows exponentially. This tougher case of cascading imbalance occurs when fixing imbalance due to a page-changing UCB class.\n\nRegarding the mentioned limitation, the rounding scheme does maintain a distribution supported by many cache states (while, of course, holding in actuality a single cache state). To the best of our knowledge, this is true of any known rounding scheme for weighted caching, in particular for that of Bansal, Buchbinder, and Naor [2012]. The focus of this paper was introducing unknown weights to weighted paging, rather than improving the computational tractability of the rounding scheme for known weights; however, we agree with your observation and believe this is a promising direction for future study. \n\nWe thank you again for the thoughtful review. We would be happy to discuss any further notes/questions you have. If we’ve properly addressed your concerns, we would be happy if you considered updating your assessment accordingly.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SOjVqedqTe", "reviewer": "Reviewer_VdxB", "summary": "This paper considers a generalization of the classical online paging problem. In classical online paging, one needs to maintain a cache of k slots as requests for fetching pages arrive online. If the requested pages are in the cache, there is no charged cost; otherwise, w_p cost will be charged for page p. The goal is to maintain a cache of k slots such that the total fetching cost is minimized. This paper extends this classical setting to the case where the weight of all pages is not known prior to algorithms. Instead, the algorithm needs to sample a value from an unknown distribution, and such a value will be an estimated value of the actual weight. The goal is still to minimize the total fetching cost.\n\nThe main contribution of this work is an online algorithm that achieves alg$\\leq O(\\log k)$ opt + $O(\\sqrt{nT})$, where k is the size of the cache, n is the number of pages and T is the number requests. The main technique is fractional solution+rounding. To bridge these two phases, the authors design an interface, which aims to learn an estimation of weights for each page.", "questions": "Could you comment on how tight the regret bound O(\\sqrt{nT}) is? This seems to be a large number.", "limitations": "This is a theoretical paper, there is no potential negative societal impact.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The studied problem is well-motivated and it should be interested in the ML community. I expect that the studied problem will have a positive impact on practice.\n\n2. I like the interface idea to bridge the fractional solution and rounding. The main purpose of the interface is to learn the weights. Although all these ideas are not novel, it is interesting to see that a simple combination works well.\n\n3. The paper is well-structured. I appreciate that the authors give a very clear statement for the algorithmic framework in Section 3. This is very helpful for readers.", "weaknesses": "There is no lower bound in the paper. The regret bound might be far from tight, but this is expected in the first paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the thoughtful comments and encouraging review.\n\nRegarding lower bounds, see the remark in the general rebuttal. In essence, we’ve presented lower bounds for the problem in “Our Results”, which we intend to further formalize in the camera-ready version. \n\nRegarding the regret bound of $O(\\sqrt{nT})$, consider the following implications of the lower bounds (a) and (b) that appear in this paragraph (starting at Line 61 in the paper):\n1. Lower bound (b) implies that allowing a competitive ratio that is $o(\\log k)$, the regret of any algorithm is $\\Omega(T/k)$. In particular, for constant k, this implies $\\Omega(T)$ regret. Without loss of generality $n\\le T$, as pages that are never requested are never loaded into the cache; thus, the regret lower bound is $\\Omega(\\sqrt{nT})$ in this case. \n2. The term $\\Omega(\\sqrt{T})$ is necessary for any choice of (sublinear) competitive ratio. \n\n\nWe thank the reviewer again for the supportive review and will happily address any further questions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their thorough assessments and their thoughtful remarks. Here are some clarifications regarding themes that appear in more than one review.

**Running time:**

Reviewers Yutu and qj5j made remarks regarding the running time of the algorithm, and specifically the continuous updates in the fractional solver. The fractional solver is presented as continuously decreasing and increasing anti-server amounts, in keeping with previous work. But, this continuous process can be easily discretized into simple multiplicative updates, without affecting the correctness of the algorithm. This is a common trait of algorithms based on multiplicative updates; for an introduction to such discretization, see e.g. Chapter 4.2 of [1]. Similarly, the rounding scheme which maintains consistency and balance is presented as processing infinitesimal changes (in keeping with previous work), but can actually be applied only after the fractional solver has concluded; i.e., once per request.



**Lower bounds:**
  
Several reviewers had issues with the lower bounds complementing our main result. In particular, we showed that:
1. In the absence of a regret term, the competitive ratio of any algorithm is unfavorable (i.e., it has a polynomial dependence on $T$).
2. In the absence of a competitive ratio term, the regret of any algorithm is unfavorable (i.e., linear in $T$). 
We concluded that both a competitive ratio term and a regret term are necessary. As these lower bounds are rather simple, we chose to present them informally in “our results”; however, these lower bounds are concrete, and can easily be formalized as theorems. Given the reviewers’ feedback, we’ll formalize those lower bounds in the camera-ready version. 

[1] “The Design of Competitive Online Algorithms via a Primal-Dual Approach” by Niv Buchbinder and Seffi Naor.

Meta-review: This paper suggested a stochastic weight setting for online weighted paging. The access to the weight is modeled as a multi-armed bandit  (MAB) model.

The review is somewhat mixed. it is generally agreed that the motivation of considering stochastic weight makes sense. However, the main criticism is that the specific model of MAB is not well justified, and the mere motivating example in the paper may not be sufficient. Nonetheless, it seems MAB is a simple yet powerful model, and it makes sense to start with this as one of the early paper to initiate the study of the stochastic setting. 

The review somewhat agreed that the algorithm is technically nontrivial, and is an interesting combination of the online primal-dual/rounding framework with MAB. However, criticisms including practical efficiency of the algorithm and the clarity of the technical presentation (for example the vague lower bound argument) are also raised.

This is a borderline paper, but I suggest for an acceptance because of the conceptual value of initiating the stochastic setting of online weighted paging, as well as the technical strength of the paper.
Decision: Accept (poster)