Online Weighted Paging with Unknown Weights

Authors: orin  levy
noam  touitou
aviv  rosenberg
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-09 12:57:07

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.

Main paper: 
 introduction: 
 Online weighted paging. In the online weighted paging problem, or OWP, one is given a cache of 𝑘 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 𝑝 also has a weight 𝑤 𝑝 , 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 𝑘)-competitive randomized online algorithm, due to Bansal, Buchbinder, and Naor [2010, 2012] ; This is optimal, as there exists an Ω(log 𝑘)-competitiveness lower bound for randomized algorithms due to Fiat et 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 can be stored in one of the following: a local "L1" cache, unique to each core; a global "L2" cache, shared between the cores; and the (large but slow) main memory. As a specific core requests memory blocks, managing its L1 cache can be seen as an OWP instance. Suppose the costs of fetching a block from the main memory and from the L2 cache are 1 and 𝜖 ≪ 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 𝜖, weighted by the probability that the block is in the L2 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 a block is fetched in the above example, we observe a stochastic cost of either 1 or 𝜖. As we sample a given block multiple times, we 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-armed bandit problem, or MAB. In the cost-minimization 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 𝑝, rather than learning its cost 𝑤 𝑝 , the algorithm is only revealed a sample from some distribution whose expectation is 𝑤 𝑝 . In this problem, the goal is to minimize the regret, which is the difference between the algorithm's total cost and the optimal cost (which is to always choose the cheapest option). Over 𝑇 time steps, the best known regret bound for this problem is Õ ( √ 𝑛𝑇), achieved through multiple techniques. (See, e.g., Slivkins et al. [2019] , Lattimore and Szepesvári [2020] ).We make the first consideration of OWP where page weights are not known in advance, and show that the optimal competitive ratio of 𝑂 (log 𝑘) 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 𝑝 has an arbitrary distribution, whose expectation is its weight 0 < 𝑤 𝑝 ≤ 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 𝑄, E[ON(𝑄)] ≤ 𝑂 (log 𝑘) • OPT(𝑄) + Õ ( √ 𝑛𝑇), where ON(𝑄) is the cost of ON on 𝑄, OPT(𝑄) is the cost of the optimal solution to 𝑄, 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 1.1 combines a competitive ratio of 𝑂 (log 𝑘) with a regret (i.e., additive) term of Õ ( √ 𝑛𝑇). To motivate this type of bound, we observe that OWP-UW does not admit sublinear regret without a competitive ratio. Consider the lower bound of Ω(log 𝑘) for the competitive ratio of paging; stated simply, one of 𝑘 + 1 pages of weight 1 is requested at random. Over a sequence of 𝑇 requests, the expected cost of any online algorithm is Ω(𝑇/𝑘); meanwhile, the expected cost of the optimal solution is at most 𝑂 (𝑇/(𝑘 log 𝑘)). (The optimal solution would be to wait for a maximal phase of requests containing at most 𝑘 pages, whose expected length is Θ(𝑘 log 𝑘), then change state at constant cost.) Without a competitive ratio term, the difference between the online and offline solutions is Ω(𝑇/𝑘), i.e., linear regret. We note that this kind of bound appears in several previous works such as Basu et al. [2019] , Foussoul et al. [2023] . As OWP-UW generalizes both standard OWP and MAB, both the competitive ratio and regret terms are asymptotically tight: a competitiveness lower bound of Ω(log 𝑘) is known for randomized algorithms for online (weighted) paging [Fiat et al., 1991] , and a regret lower bound of Ω( √ 𝑛𝑇) is known for MAB [Lattimore and Szepesvári, 2020] .Interface between fractional solution and rounding scheme. Randomized online algorithms are often built of the following components:1. A deterministic, 𝛼-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 an 𝛼𝛽-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 competitiveness 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 a 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 to 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 a 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 (randomized) rounding scheme is not allowed to use samples to update the confidence bounds; otherwise, our fractional solution would behave non-deterministically. 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 et al., 2020] ), but rarely appear as a component of an online algorithm as we suggest in this paper.The online paging problem is a fundamental problem in the field of online algorithms. In the unweighted setting, the optimal competitive ratio for a deterministic algorithm is 𝑘, due to Sleator and Tarjan [1985] . Allowing randomization improves the best possible competitive ratio to Θ(log 𝑘) [Fiat et al., 1991] . As part of a line of work on weighted paging and its variants (e.g., Young [1994] , Manasse et al. [1990] , Albers [2003] , Irani [2002] , Fiat 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: 𝑘-competitiveness for deterministic algorithms, due to Chrobak et al. [1991] ; and Θ(log 𝑘)-competitiveness for randomized algorithms, due to Bansal et al. [2012] .Online (weighted) paging is a special case of the 𝑘-server problem, in which 𝑘 servers exist in a 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 as servers, moving in a (weighted) uniform metric space. The Θ(𝑘) bound on optimal competitiveness in the deterministic for paging also extends to general 𝑘-server [Manasse et al., 1990, Koutsoupias and Papadimitriou, 1995] . However, allowing randomization, a recent breakthrough result by Bubeck et al. [2023] was a lower bound of Ω(log 2 𝑘)competitiveness for 𝑘-server, diverging from the 𝑂 (log 𝑘)-competitiveness 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. It 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 [Lai and Robbins, 1985, Auer et al., 2002a] ), Action Elimination [Even-Dar et al., 2006] , ThompsonSampling [Thompson, 1933, Agrawal and Goyal, 2012] and Exponential Weights (e.g., the EXP3 algorithm [Auer et al., 2002b] ). For a comprehensive review of the MAB literature, see Slivkins et al. [2019] , Lattimore and Szepesvári [2020] .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 a 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 in 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 as long as it is clear that these goals are not attained by the paper. 
preliminaries: 
 In OWP-UW, we are given a memory cache of 𝑘 slots. A sequence of 𝑇 page requests then arrives in an online fashion; we denote the set of requested pages by 𝑃, define 𝑛 := |𝑃|, and assume that 𝑛 > 𝑘.Each page 𝑝 has a corresponding weight 0 < 𝑤 𝑝 ≤ 1; the weights are not known to the algorithm. Moreover, every page 𝑝 has a distribution D 𝑝 supported in (0, 1], such that E 𝑥∼D 𝑝 [𝑥] = 𝑤 𝑝 .The online scenario proceeds in 𝑇 rounds. 3 In each round 𝑡 ∈ {1, 2, . . . , 𝑇 }:• A page 𝑝 𝑡 ∈ 𝑃 is requested.• If the requested page is already in the cache, then it is immediately served.• Otherwise, we experience a cache miss, and we must fetch 𝑝 𝑡 into the cache; if the cache is full, the algorithm must evict some page from the cache to make room for 𝑝 𝑡 .• Upon evicting any page 𝑝 from the cache, the algorithm receives an independent sample from D 𝑝 .The algorithm incurs cost when evicting pages from the cache: when evicting a page 𝑝, the algorithm incurs a cost of 𝑤 𝑝4 . Our goal is to minimize the algorithm's total cost of evicting pages, denoted by ON, and we measure our performance by comparison to the total cost of the optimal algorithm, denoted by OPT. We say that our algorithm is𝛼-competitive with R regret if E[ON] ≤ 𝛼 • OPT + R.1. At any point in the algorithm, it holds that 𝑝∈ 𝑃 𝑦 𝑝 ≥ 𝑛 -𝑘. (I.e., the total number of pages in the cache is at most 𝑘.)2. After a page 𝑝 is requested, it holds that 𝑦 𝑝 = 0. (I.e., there exists a total server fraction of 1 at 𝑝.)Evicting an 𝜖 server fraction from 𝑝 (i.e., increasing 𝑦 𝑝 by 𝜖) costs 𝜖 • 𝑤 𝑝 .Sampling. The fractional algorithm must receive samples of pages over time in order to learn about their weights. An algorithm for fractional OWP-UW receives a sample of a page 𝑝 whenever the total fraction of 𝑝 evicted by the algorithm reaches an integer. In particular, the algorithm obtains the first sample of 𝑝 (corresponding to 0 eviction) when 𝑝 is first requested in the online input.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 𝑝 ∈ 𝑃, the fractional algorithm maintains an upper confidence bound UCB 𝑝 and a lower confidence bound LCB 𝑝 . These confidence bounds depend on the samples provided for that page; we define the good event E to be the event that at every time and for every page 𝑝 ∈ 𝑃, it holds that LCB 𝑝 ≤ 𝑤 𝑝 ≤ UCB 𝑝 . We later show that E happens with high probability, and analyze the complementary event separately5 . 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 a stronger bound, that applies also when the cost of evicting page 𝑝 is the upper confidence bound UCB 𝑝 ≥ 𝑤 𝑝 . Lemma 3.1. Fixing any input 𝑄 for fractional OWP-UW, and assuming the good event, it holds thatONF(𝑄) ≤ ONF(𝑄) ≤ 𝑂 (log 𝑘) • OPT(𝑄) + Õ ( √ 𝑛𝑇)where ONF is the cost of the algorithm on the input where the cost of evicting a page 𝑝 is UCB 𝑝 ≥ 𝑤 𝑝 .Randomized rounding. In Section 5 we present the randomized algorithm ON for (integral) OWP-UW. It 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 to ONF when required. In 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 𝑄 for (integral) OWP-UW, assuming the good event E, it holds thatE[ON(𝑄)] ≤ 𝑂 (1) • ONF(𝑄) + 𝑛where ONF(𝑄) is the cost of the algorithm on 𝑄 such that the cost of evicting a page 𝑝 is UCB 𝑝 ≥ 𝑤 𝑝 .Figure 1 provides a step-by-step visualization of the interface between the fractional algorithm and the rounding scheme over the handling of a page request.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [NA] Justification: This is 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 to discuss.Guidelines:• The answer NA means that the paper has no 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 a 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 on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
ucb: 
 P ∃𝑝 ∈ 𝑃. 1 2𝑛 2 𝑇 • 𝑤 1 𝑝 > 𝑤 𝑝 = P[∃𝑝 ∈ 𝑃. 𝑤 1 𝑝 > 2𝑛 2 𝑇 • 𝑤 𝑝 ] ≤ 𝑛 • 1 2𝑛 2 𝑇 = 1 2𝑛𝑇.For the second event, by Hoeffding inequality and a union bound over all the pages 𝑝 ∈ 𝑃, all the time steps 𝑡 ∈ [1, 𝑇] and all the possible number of samples for each page 𝑖 ∈ [1, 𝑛𝑇], we have Proof. The following holds under the good event.P ∃𝑝 ∈ 𝑃, 𝑖 ∈ [1, 𝑇]. |𝑤 𝑝 -w 𝑝,𝑖 | > 𝜖 𝑝,𝑖 ≤ 𝑛 2 𝑇 2 • 2𝑒 -2𝑖 𝜖 2 𝑝,𝑖 = 𝑛 2 𝑇 2 • 1 2𝑛 3 𝑇 3 = 1 2𝑛𝑇U = ∑︁ 𝑝∈ 𝑃 𝑛 𝑝 ∑︁ 𝑖=1 UCB 𝑝,𝑖 -LCB 𝑝,𝑖 + 2 log(1 + 1/𝜂) ∑︁ 𝑝∈ 𝑃 LCB 𝑝 ≤ 2 ∑︁ 𝑝∈ 𝑃 𝑛 𝑝 ∑︁ 𝑖=1 𝜖 𝑝,𝑖 + 2 log(1 + 1/𝜂) ∑︁ 𝑝∈ 𝑃 𝑤 𝑝 (Lemma C.1) = 2 ∑︁ 𝑝∈ 𝑃 𝑛 𝑝 ∑︁ 𝑖=1 √︂ log(4𝑛 3 𝑇 3 ) 2𝑖 + 2 log(1 + 1/𝜂) ∑︁ 𝑝∈ 𝑃 𝑤 𝑝 ≤ √︃ 2 log(4𝑛 3 𝑇 3 ) ∑︁ 𝑝∈ 𝑃 𝑛 𝑝 ∑︁ 𝑖=1 1 √ 𝑖 + 2𝑛 log(1 + 1/𝜂) (𝑤 𝑝 ≤ 1) ≤ 2 √︃ 2 log(4𝑛 3 𝑇 3 ) ∑︁ 𝑝∈ 𝑃 √ 𝑛 𝑝 + 2𝑛 log(1 + 1/𝜂) ( 𝑡 𝑖=1 1 √ 𝑖 ≤ 2 √ 𝑡) ≤ 2 √︃ 2𝑛𝑇 log(4𝑛 3 𝑇 3 ) + 2𝑛 log(1 + 𝑘),where the last inequality holds by Cauchy-Schwarz and our choice of 𝜂 = 1/𝑘. Lastly, the stated upper bound follows since 𝑘 ≤ 𝑛 and 𝑛 ≤ √ 𝑛𝑇. □NeurIPS Paper Checklist• The method for calculating the error bars should be explained (closed form formula, call to 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. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 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 out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
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 1 below, uses samples provided by the rounding scheme to learn the weights. A new sample for page 𝑝 is provided and processed whenever the sum of fractional movements (in absolute value) 𝑚 𝑝 hits a natural number. (At this point the number of samples 𝑛 𝑝 is incremented.) The algorithm calculates non-increasing UCBs and non-decreasing LCBs that will be specified later in Section C and guarantee with high probability, for every page 𝑝 ∈ 𝑃 and time step 𝑡 ∈ [1, 𝑇], LCB 𝑝 ≤ 𝑤 𝑝 ≤ UCB 𝑝 . At each time step 𝑡, upon a new page request 𝑝 𝑡 , the algorithm updates its feasible fractional cache solution {𝑦 𝑝 } 𝑝∈ 𝑃 . 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 𝑝 𝑡 (that is, setting 𝑦 𝑝 𝑡 = 0), the algorithm continuously increases the anti-servers of all the other pages in the cache until feasibility is reached (that is, until 𝑝∈ 𝑃 𝑦 𝑝 = 𝑛 -𝑘). The fraction 𝑦 𝑝 for some page 𝑝 in the cache is increased proportionally to𝑦 𝑝 +𝜂LCB 𝑝 , which is our adaption of the algorithmic approach of Bansal et al. [2010] 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.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 C.1 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.e., Lemma 3.1.This figure visualizes the running of the algorithm over a 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 a distribution over integral cache states that upholds some properties w.r.t. ONF (specifically, the consistency property and the subset property); note that these properties are a function of both the anti-server state 𝑦 𝑝 𝑝∈ 𝑃 and the upper-confidence bounds UCB 𝑝 𝑝∈ 𝑃 in ONF. The integral algorithm also maintains a set of page samples, to be demanded by ONF at a later time. In (b), a page is requested (in red); thus, the fractional algorithm 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 in anti-server are also fed into the integral algorithm, which modifies its distribution to maintain consistency and the subset property w.r.t. ONF. In (c), ONF reaches integral total eviction of a page 𝑝, and demands a sample from the integral algorithm. (We show that such a sample always exists when demanded.) The bound UCB 𝑝 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 for the requested page 𝑝 𝑡 , sampling the page if needed. (As 𝑝 𝑡 now exists in 𝜇 with probability 1, sampling is done through evicting and re-fetching 𝑝 𝑡 .) if this is the first request for 𝑝 𝑡 then receive sample 𝑤 𝑝 𝑡 for 𝑝 𝑡 .define 𝑚 𝑝 ← 0, 𝑛 𝑝 ← 1.call UPDATECONFBOUNDS(𝑝 𝑡 , 𝑤 𝑝 𝑡 ). // calculate confidence bounds for 𝑝 𝑡 Lemma 4.1. Fixing any input 𝑄 for fractional OWP-UW, and assuming the good event, it holds thatONF(𝑄) ≤ 𝑂 (log 𝑘) • OPT(𝑄) + ∑︁ 𝑝∈ 𝑃 𝑛 𝑝 ∑︁ 𝑖=1 UCB 𝑝,𝑖 -LCB 𝑝,𝑖 + 2 log(1 + 1/𝜂) ∑︁ 𝑝∈ 𝑃 LCB 𝑝 .where (a) ONF is the cost of the algorithm on the input such that the cost of evicting a page 𝑝 is UCB 𝑝 ≥ 𝑤 𝑝 , and (b) UCB 𝑝,𝑖 , LCB 𝑝,𝑖 are the values of UCB 𝑝 and LCB 𝑝 calculated by the procedure UPDATECONFBOUNDS (found in Appendix C) immediately after processing the 𝑖'th sample of 𝑝, and (c) LCB 𝑝 is the value after the last sample of page 𝑝 was processed.Proof sketch. We prove the lemma using a potential analysis. In Bansal et al. [2010] , a 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 as a fractional exploration budget. This budget is "recharged" upon receiving a sample; the cost of this recharging goes into a regret term. □This figure visualizes a single step in REBALANCESUBSETS. Subfigure (a) shows the distribution of anti-cache states prior to this step; specifically, the 𝑥 axis is the probability measure, and the 𝑦-axis is the number of pages of class 𝑖 and above in the anti-cache, i.e., 𝑚 := |𝑆 ∩ 𝑃 ≥𝑖 |. The red line is 𝑌 𝑖 , which through consistency, is the expectation of 𝑚; the blue dotted lines are thus the allowed values for 𝑚, which are |⌈𝑌 𝑖 ⌉, ⌊𝑌 𝑖 ⌋|. 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 𝑆 that maximizes |𝑚 -𝑌 𝑖 |; in our case, 𝑚 > 𝑌 𝑖 , and thus we match its measure with an identical measure of anti-cache states that are below the upper blue line, i.e., can receive a page without increasing imbalance. Then, a page of class 𝑖 is handed from 𝑆 to every matched state 𝑆 ′ ; note that every matched state might get a different page from 𝑆, but some such page in 𝑆 \ 𝑆 ′ is proven to exist. Finally, Subfigure (c) shows the state after the page transfer; note the decrease in imbalance that results. The REBALANCESUBSETS procedure performs such steps until there is no imbalance; then, the procedure would advance to class 𝑖 -1.  
randomized rounding: 
 This section describes a randomized algorithm for (integral) OWP-UW, which uses Algorithm 1 for fractional OWP-UW to maintain a probability distribution over valid integral cache states, while obtaining and providing page weight samples to Algorithm 1. The method in which the randomized algorithm encapsulates and tracks the fractional solution is inspired by Bansal et al. [2012] , which maintains a 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 𝜇(𝑆) be the probability that 𝑆 ⊆ 𝑃 is the set of pages missing from the cache, also called the anti-cache. For the algorithm to be a valid algorithm for OWP-UW, the cache can never contain more than 𝑘 pages; this is formalized in the following property. Definition 5.1 (valid distribution). A probability distribution 𝜇 is valid, if for any set 𝑆 ⊆ 𝑃 with 𝜇(𝑆) > 0 it holds that |𝑆| ≥ 𝑛 -𝑘.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 𝑝, we define the 𝑖'th UCB class to be 𝑃 𝑖 := 𝑝 ∈ 𝑃 : 6 𝑖 ≤ UCB 𝑝 < 6 𝑖+1 . (Note that UCB 𝑝 ∈ (0, 1].) We also define 𝑃 ≥ 𝑗 := 𝑖 ≥ 𝑗 𝑃 𝑗 , the set of all pages that their UCB is at least 6 𝑗 .Let {𝑦 𝑝 } 𝑝∈ 𝑃 be the fractional solution. The balanced property requires that, for every set 𝑆 such that 𝜇(𝑆) > 0 and every index 𝑗, the number of pages in 𝑆 of class at least 𝑗 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 𝑦, if for any set 𝑆 ⊆ 𝑃 with 𝜇(𝑆) > 0, the following holds for all 𝑗:∑︁ 𝑖 ≥ 𝑗 ∑︁ 𝑝∈ 𝑃 𝑖 𝑦 𝑝 ≤ ∑︁ 𝑖 ≥ 𝑗 ∑︁ 𝑝∈ 𝑃 𝑖 I[ 𝑝 ∈ 𝑆] ≤ ∑︁ 𝑖 ≥ 𝑗 ∑︁ 𝑝∈ 𝑃 𝑖 𝑦 𝑝 .Algorithm 2: Randomized rounding algorithm for OWP-UWLet ONF be an instance of Algorithm 1, that maintains a fractional anti-server allocation 𝑦 𝑝 𝑝∈ 𝑃 .Define 𝜇 to be a distribution over cache states, initially containing the empty cache state with probability 1.For every 𝑝 ∈ 𝑃, let 𝑠 𝑝 ← NULL. remove 𝑝 from the anti-cache in the 𝑥 measure of 𝑆 ′ , and insert it into the anti-cache in the 𝑥 measure of 𝑆.Choosing the minimum UCB class in Definition 5.2, and noting that 𝑝∈ 𝑃 𝑦 𝑝 ≥ 𝑛 -𝑘 through feasibility, immediately yields the following remark.Remark 5.3. Every balanced probability distribution is also a 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 𝑝 is missing from the cache must be equal to 𝑦 𝑝 .Definition 5.4 (consistent distribution). A probability distribution 𝜇 on subsets 𝑆 ⊆ 𝑃 is consistent with respect to a fractional solution 𝑦 𝑝 𝑝∈ 𝑃 if for every page 𝑝 it holds that 𝑆 ⊆ 𝑃 | 𝑝∈𝑆 𝜇(𝑆) = 𝑦 𝑝 .In the following we describe the online maintenance of the distribution 𝜇, 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 1 for fractional OWP-UW, called ONF. Upon a new page request 𝑝 𝑡 at round 𝑡, 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 a fractional variable, the algorithm first changes its distribution to maintain consistency: when the fractional algorithm ONF increases the variable 𝑦 𝑝 ′ of any page 𝑝 ′ by an 𝜖-measure, the algorithm identifies an 𝜖-measure of cache states 𝑆 ⊆ 𝑃 in which there is no anti-server at 𝑝 ′ and adds anti-server at 𝑝 ′ . The case in which the fractional algorithm decreases a variable is analogous.However, this procedure may invalidate the balanced property. Specifically, for some class 𝑗, letting 𝑌 𝑗 be the total anti-server fraction of pages of at least class 𝑗 in ONF, there might now be states with 𝑌 𝑗 + 1 or 𝑌 𝑗 -1 such pages in the anti-cache. Thus, the algorithm makes a call to REBALANCESUBSETS, which restores the balanced property class-by-class, in a descending order.For every class 𝑗, the procedure repeatedly identifies a violating state 𝑆 where the number of pages of class ≥ 𝑗 in the anti-cache is not in 𝑌 𝑗 , 𝑌 𝑗 ; suppose it identifies such a state with more than 𝑌 𝑗 such pages (the case of less than 𝑌 𝑗 pages is analogous). The procedure seeks to move a page of class 𝑗 from this state to another state in a way that does not increase the "imbalance" in class 𝑗. Thus, the procedure identifies a matching measure of anti-cache states that contain at most 𝑌 𝑗 -1 such pages, and moves a page of class 𝑗 from 𝑆 to 𝑆 ′ , for every 𝑆 ′ in the matched measure; a visualization of the procedure is given in Figure 2 . (The existence of this matching measure, as well as a page to move, are shown in the analysis.) In particular, note that the probability of every page being in the anti-cache remains the same, and thus REBALANCESUBSETS does not impact consistency.Regarding samples, the algorithm can maintain a sample 𝑠 𝑝 for every page 𝑝. A sample for 𝑝 is obtained upon a request for 𝑝 after 𝑝 is fetched with probability 1 into the cache, if no such sample already exists (i.e., 𝑠 𝑝 = NULL). Whenever ONF requests a sample for a page 𝑝, the randomized algorithm provides the sample 𝑠 𝑝 , and sets the variable 𝑠 𝑝 to be NULL (we show that 𝑠 𝑝 is never NULL when ONF samples 𝑝). A fine point is the sampling of a new page in Line 11 of Algorithm 1; 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 are 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 𝑝 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 L1 cache, the popularity of a page among the cores can vary over time; this would correspond to the problem of non-stationary bandits (see, e.g., Auer et al. [2019b,a] , 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 a common component in many online algorithms. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?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 NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 an 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 is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 a 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 as 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 or 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe 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)? Answer: [NA] Justification: This paper is theoretical. No data or models are associated with it.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 a best faith effort. 12. Licenses for existing assets Question: 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? Answer: [NA] Justification: This paper is theoretical. No existing assets are associated with it.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a 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 the 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 a dataset.• For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.  
 
 Appendix: 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 C.1 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.e., 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 analysis to prove that ONF ≤ 2 log(1 + 𝑘) • OPT + U 𝑇 , where U 𝑇 is a regret term summed over 𝑇 time steps that will be defined later. To that end, we show that the following equation holds for every round 𝑡,EQUATIONwhere Δ𝑋 𝑡 is the change in 𝑋 in time 𝑡 and Φ is a potential function that we define next.Let 𝐶 * 𝑡 denote the set of pages in the offline (optimal) cache at time 𝑡. The potential function we 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.Φ 𝑡 = -2 ∑︁ 𝑝∉𝐶 * 𝑡 LCB 𝑝 • log 𝑦 𝑝 + 𝜂 1 + 𝜂 + ∑︁ 𝑝∈ 𝑃 UCB 𝑝 -LCB 𝑝 • 𝑛 𝑝 -𝑚 𝑝 ,where UCB 𝑝 , LCB 𝑝 are the confidence bounds in time step 𝑡, 𝑛 𝑝 is the number of samples of page 𝑝 collected until that point, and 𝑚 𝑝 is the total fractional movement of that page until that point. Note that 𝑛 𝑝 -𝑚 𝑝 ∈ [0, 1]. We now show that Equation 1 holds 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, as follows,U := ∑︁ 𝑝∈ 𝑃 𝑛 𝑝 ∑︁ 𝑖=1 (UCB 𝑝,𝑖 -LCB 𝑝,𝑖 ) + 2 log(1 + 1/𝜂) ∑︁ 𝑝∈ 𝑃 LCB 𝑝 .We note that each time the algorithm gets a new sample, 𝑛 𝑝 is incremented and U increases.Case 1 -the optimal algorithm moves. Note that a change in the cache of the optimal solution does not affect ONF or U, and thus ΔONF = ΔU = 0. However, ΔOPT might be non-zero, as the optimal solution incurs a moving cost; in addition, ΔΦ 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 (1) for this case reduces to proving ΔΦ 𝑡 ≤ 2 log(1 + 1/𝜂)ΔOPT. Assume the optimal solution moves; as we assume that the optimal solution is lazy, it must be that the requested page 𝑝 𝑡 is not in 𝐶 * 𝑡 -1 , and that the optimal solution fetches it into the cache, possibly evicting a (single) page from its cache.First, consider the case in which there exists an empty slot in the cache, and no evictions take place when fetching 𝑝 𝑡 . In this case, ΔOPT = 0; moreover, as 𝐶 * 𝑡 -1 ⊆ 𝐶 * 𝑡 , it holds that ΔΦ ≤ 0. Thus, Equation (1) holds.Otherwise, at time 𝑡, page 𝑝 𝑡 is fetched and another page 𝑝 is evicted. Thus, ΔOPT = 𝑤 𝑝 . For the potential change, 𝑝 starts to contribute to Φ. In the worst case, 𝑦 𝑝 = 0 and then Φ is increased by at most 2LCB 𝑝 log(1 + 1/𝜂) ≤ 2𝑤 𝑝 log(1 + 1/𝜂) = 2 log(1 + 1/𝜂)ΔOPT, as desired.Case 2 -the fractional algorithm moves. In this case, only the potential and the cost of the fractional algorithm change, i.e., ΔOPT 𝑡 = ΔU 𝑡 = 0. Thus, Equation (1) reduces to proving ΔONF 𝑡 + ΔΦ 𝑡 ≤ 0 in this case.There are two types of movement made by the algorithm: the immediate fetching of the requested page 𝑝 𝑡 , and the continuous eviction of other pages from the cache until feasibility is reached (i.e., there are 𝑛 -𝑘 anti-servers). First, consider the fetching of 𝑝 𝑡 into the cache; as we charge for evictions, this action does not incur cost (ΔONF = 0). In addition, through OPT's feasibility, it holds that 𝑝 𝑡 ∈ 𝐶 * 𝑡 , and thus changing 𝑦 𝑝 𝑡 does not affect the potential function (ΔΦ = 0); thus, Equation (1) holds for this sub-case.Next, consider the continuous eviction of pages. Suppose the fractional algorithm evicts 𝑑 𝑦 page units, where 𝑑 𝑦 is infinitesimally small. Let 𝑆 = {𝑝 𝑡 } ∪ 𝑝 : 𝑦 𝑝 < 1 . Since the fractional algorithm increases 𝑦 𝑝 proportionally to𝑦 𝑝 +𝜂 LCB 𝑝 for each 𝑝 ∈ 𝑆 \ {𝑝 𝑡 }, it holds that, 𝑑𝑦 𝑝 = 1 𝑁 • 𝑦 𝑝 +𝜂 LCB 𝑝 𝑑𝑦, for 𝑁 := 𝑝∈𝑆\{ 𝑝 𝑡 } 𝑦 𝑝 +𝜂LCB 𝑝 . Thus, ΔONF can be bounded as follows.𝑝∈𝑆\{ 𝑝 𝑡 } UCB 𝑝 𝑑𝑦 𝑝 = ∑︁ 𝑝∈𝑆\{ 𝑝 𝑡 } LCB 𝑝 + UCB 𝑝 -LCB 𝑝 𝑑𝑦 𝑝 = ∑︁ 𝑝∈𝑆\{ 𝑝 𝑡 } LCB 𝑝 + UCB 𝑝 -LCB 𝑝 1 𝑁 𝑦 𝑝 + 𝜂 LCB 𝑝 𝑑𝑦 = ∑︁ 𝑝∈𝑆\{ 𝑝 𝑡 } 1 𝑁 𝑦 𝑝 + 𝜂 𝑑𝑦 + ∑︁ 𝑝∈𝑆\{ 𝑝 𝑡 } UCB 𝑝 -LCB 𝑝 𝑑𝑦 𝑝 = ∑︁ 𝑝∈𝑆\{ 𝑝 𝑡 } 1 𝑁 𝑦 𝑝 + 𝜂 𝑑𝑦 (𝑎) + ∑︁ 𝑝∈ 𝑃 UCB 𝑝 -LCB 𝑝 𝑑𝑦 𝑝 (𝑏).where the final equality stems from having 𝑑𝑦 𝑝 = 0 for every 𝑝 ∉ 𝑆 \ {𝑝 𝑡 }. We now bound the term (𝑎) using similar arguments to those presented in Bansal et al. [2010] . We present them below for completeness.(𝑎) = ∑︁ 𝑝∈𝑆\{ 𝑝 𝑡 } 1 𝑁 𝑦 𝑝 + 𝜂 𝑑𝑦 ≤ (|𝑆| -𝑘) 𝑁 𝑑𝑦 + (|𝑆| -1)𝜂 𝑁 𝑑𝑦 ≤ 2(|𝑆| -𝑘) 𝑁 𝑑𝑦,where the first inequality implied since 𝑦 𝑝 = 1 for 𝑝 ∉ 𝑆, which yields that∑︁ 𝑝∈𝑆\{ 𝑝 𝑡 } 𝑦 𝑝 ≤ ∑︁ 𝑝∈𝑆 𝑦 𝑝 = ∑︁ 𝑝∈ 𝑃 𝑦 𝑝 - ∑︁ 𝑝∉𝑆 𝑦 𝑝 ≤ (|𝑃| -𝑘) -(|𝑃| -|𝑆|) = |𝑆| -𝑘,and the second inequality implied as (𝑥 -1)𝜂 ≤ 𝑥 -𝑘 for any 𝑥 ≥ 𝑘 + 1 and using that |𝑆| ≥ 𝑘 + 1.Next, we upper bound ΔΦ 𝑡 . The rate of change in the potential with respect to 𝑦 𝑝 is𝑑Φ 𝑡 𝑑𝑦 𝑝 = -2 LCB 𝑝 𝑦 𝑝,𝑡 + 𝜂 -UCB 𝑝 -LCB 𝑝 .The non-trivial part in the above calculation is that 𝑑 (UCB𝑝-LCB𝑝)•(𝑛𝑝-𝑚𝑝)𝑑𝑦 𝑝 = -UCB 𝑝 -LCB 𝑝 . This is true since 𝑛 𝑝 is uncorrelated with the change in 𝑦 𝑝 , however, 𝑚 𝑝 is increasing with with respect to 𝑦 𝑝 in 1-linear ratio. Using the above we get thatΔΦ 𝑡 = ∑︁ 𝑝∈ 𝑃 𝑑Φ 𝑡 𝑑𝑦 𝑝 𝑑𝑦 𝑝 = -2 ∑︁ 𝑝∈𝑆\𝐶 * 𝑡 LCB 𝑝 𝑦 𝑝 + 𝜂 1 𝑁 𝑦 𝑝 + 𝜂 LCB 𝑝 𝑑𝑦 - ∑︁ 𝑝∈ 𝑃 UCB 𝑝 -LCB 𝑝 • 𝑑𝑦 𝑝 = -2 ∑︁ 𝑝∈𝑆\𝐶 * 𝑡 𝑑𝑦 𝑁 - ∑︁ 𝑝∈ 𝑃 UCB 𝑝 -LCB 𝑝 • 𝑑𝑦 𝑝 ≤ -2 |𝑆| -𝑘 𝑁 𝑑𝑦 - ∑︁ 𝑝∈ 𝑃 UCB 𝑝 -LCB 𝑝 • 𝑑𝑦 𝑝 .Thus, ΔONF 𝑡 + ΔΦ 𝑡 ≤ 0, as required.Case 3 -the LCBs are updated (a new sample is processed). Suppose the algorithm samples a page 𝑝 for the 𝑖'th time, and updates UCB 𝑝 , LCB 𝑝 accordingly. Note that this sample does not incur any cost for the fractional algorithm or optimal solution, and thus ΔONF = ΔOPT = 0. Thus, proving Equation (1) reduces to proving ΔΦ ≤ ΔU for this case. Recalling the definition of U, it holds that ΔU = (UCB 𝑝,𝑖 -LCB 𝑝,𝑖 ) + 2 log (1 + 1/𝜂) (LCB 𝑝,𝑖 -LCB 𝑝,𝑖-1 ).Denote by 𝑛 𝑝 , 𝑚 𝑝 the variables of that name prior to sampling 𝑝; note that 𝑚 𝑝 remains the same after sampling, while 𝑛 𝑝 is incremented to 𝑛 ′ 𝑝 := 𝑛 𝑝 + 1. Moreover, note that sampling always occurs when 𝑚 𝑝 = 𝑛 𝑝 . Thus, the change in potential function is bounded as follows.ΔΦ = 2 log(1 + 1/𝜂)I[ 𝑝 ∉ 𝐶 * 𝑖 ] LCB 𝑝,𝑖 -LCB 𝑝,𝑖-1 + UCB 𝑝,𝑖 -LCB 𝑝,𝑖 ≤ 2 log(1 + 1/𝜂) LCB 𝑝,𝑖 -LCB 𝑝,𝑖-1 + UCB 𝑝,𝑖 -LCB 𝑝,𝑖where the second inequality is due to the LCBs being monotone non-decreasing. □ B Proofs from Section 5B.1 Analysis and Proof of Lemma 3.2In this subsection, we analyze Algorithm 2 and prove Lemma 3.2. Throughout this subsection, we assume the good event E; that is, the UCBs and LCBs generated by ONF throughout the algorithm are valid upper and lower bounds for the weights of pages.We start by proving that the algorithm is able to provide a new sample whenever the fractional algorithm requires one. Proposition B.1. Algorithm 2 provides page weight samples whenever demanded by ONF.Proof. We must prove that whenever a sample of page 𝑝 is requested by ONF, it holds that the variable 𝑠 𝑝 in Algorithm 2 is not NULL. Note that Algorithm 2 samples 𝑠 𝑝 at the end of a request for 𝑝. Now, note that:• The first sample of 𝑝 is requested after the first request for 𝑝 is handled by ONF, and thus after 𝑝 is sampled.• Between two subsequent requests for samples of 𝑝 by ONF, the eviction fraction 𝑚 𝑝 increased by 1. But, this cannot happen without a request for 𝑝 in the interim; this request ensures that 𝑠 𝑝 ≠ NULL, and thus the second request is satisfied.Combining both cases, all sample requests by ONF are satisfied by Algorithm 2. □ 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 REBALANCESUBSETS procedure. To this end, we define an amount quantifying the degree to which a class is imbalanced in a given distribution. Definition B.2. Let 𝜇 be a distribution over cache states, let 𝑦 𝑝 𝑝∈ 𝑃 be the current fractional solution, and let 𝑗 be some class. We define the imbalance of class 𝑗 in 𝜇 to be ∑︁𝑆 ⊆ 𝑃 𝜇(𝑆) • max 𝑆 ∩ 𝑃 ≥ 𝑗 -𝑌 𝑗 , 𝑌 𝑗 -𝑆 ∩ 𝑃 ≥ 𝑗 ;Definition B.2 quantifies the degree to which a given class is not balanced in a given distribution; one can see that if the class is balanced, this amount would be 0. Lemma B.3. Suppose REBALANCESUBSETS is called, and let 𝜇, 𝜇 ′ be the distributions before and after the call to REBALANCESUBSETS, respectively; let 𝑗 max be the maximum non-balanced class in 𝜇.Suppose that (a) 𝜇 is consistent, and (b) there exists 𝜖 > 0 such that the imbalance of any class 𝑗 ≤ 𝑗 max in 𝜇 is at most 𝜖. Then, it holds that 𝜇 ′ is both consistent and balanced. Moreover, the total cost of REBALANCESUBSETS is at most 12𝜖 • 6 𝑗 max .Proof. The running of REBALANCESUBSETS 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 𝑖" considers class 𝑖). We make a 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 𝑗 max as defined in the lemma statement, for every 𝑖 ≤ 𝑗 max consider the distribution immediately before Iteration 𝑖, denoted 𝜇 𝑖 . We claim that (a) the 𝜇 𝑖 is consistent, (b) all classes greater than 𝑖 are balanced in 𝜇 𝑖 , and (c) classes at most 𝑖 have imbalance at most 𝜖 • 3 𝑗 max -𝑖 in 𝜇 𝑖 . Where 𝑗 min is the minimum class, note that 𝜇 ′ = 𝜇 𝑗 min -1 , and that this claim implies that 𝜇 ′ is consistent and balanced.(Note that the claim implies that class 𝑗 min is balanced, which also implies that all classes smaller than 𝑗 min are balanced.).We prove this claim by descending induction on 𝑖. The base case, in which 𝑖 = 𝑗 max , is simply a restatement of the assumptions made in the lemma, and thus holds. Now, assume that the claim holds for any class 𝑖 ≤ 𝑗 max ; we now prove it for class 𝑖 -1.Consistency. First, as we've assumed that 𝜇 𝑖 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 𝑖; in particular, 𝜇 𝑖-1 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 𝑆, and let μ be the distribution at that point. Assume that 𝑆 is an "upwards" violation, i.e., 𝑚 ≥ ⌈𝑌 𝑖 ⌉ + 1, where 𝑚 := |𝑆 ∩ 𝑃 ≥𝑖 |; the case of a "downwards" violation is analogous. Note that consistency implies that E 𝑆 ′ ∼ μ |𝑆 ′ ∩ 𝑃 ≥𝑖 | = 𝑌 𝑖 . Also note that 𝑆 was chosen to maximize |𝑚 -𝑌 𝑖 |, i.e., the distance from the expectation. Thus, there exists a measure of at least μ(𝑆) of anti-caches𝑆 ′ such that |𝑆 ′ ∩ 𝑃 ≥𝑖 | < 𝑌 𝑖 (and thus |𝑆 ′ ∩ 𝑃 ≥𝑖 | ≤ ⌈𝑌 𝑖 ⌉ -1, as required).Existence of page to move. After matching the aforementioned 𝑆 to some 𝑆 ′ , we want to identify some page 𝑝 ∈ 𝑃 𝑖 such that 𝑝 ∈ 𝑆\𝑆 ′ , so we can move it from the measure of 𝑆 to the measure of 𝑆 ′ . Indeed, from the choice of 𝑆 and 𝑆 ′ , it holds that |𝑆 ∩ 𝑃 ≥𝑖 | ≥ ⌈𝑌 𝑖 ⌉ + 1 ≥ |𝑆 ′ ∩ 𝑃 ≥𝑖 | + 2. But, from the induction hypothesis for Iteration 𝑖, class 𝑖 + 1 was balanced in 𝜇 𝑖 , and thus remains balanced at every step during Iteration 𝑖 (as this iteration never moves pages of classes 𝑖 + 1 and above). This implies that |𝑆 ∩ 𝑃 ≥𝑖+1 | ≤ ⌈𝑌 𝑖+1 ⌉ ≤ |𝑆 ′ ∩ 𝑃 ≥𝑖+1 | + 1. We can thus conclude that there exists 𝑝 ∈ 𝑃 𝑖 ∩ (𝑆 \ 𝑆 ′ ) as required.Balanced property. Next, we prove that in 𝜇 𝑖-1 after Iteration 𝑖, class 𝑖 is balanced, and the imbalance of any class 𝑗 < 𝑖 is at most 𝜖 • 3 𝑗 max -(𝑖-1) . Consider any step in Iteration 𝑖, where a measure 𝑥 of a violating state is identified; then, a page is moved from a measure 𝑥 to another measure 𝑥. The induction hypothesis for Iteration 𝑖 implies that the imbalance of class 𝑖 at 𝜇 𝑖 is at most 𝜖 • 3 𝑗 max -𝑖 . Note that:1. This step decreases the imbalance of class 𝑖 by at least 𝑥, 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 𝑗 < 𝑖 by at most 2𝑥, in the worst case in which moving the page increased imbalance in both measures of 𝑥.As a result, we can conclude that for 𝜇 𝑖-1 , at the end of iteration 𝑖, class 𝑖 is balanced, while the imbalance of every class 𝑗 < 𝑖 increased by at most 2 • 𝜖 • 3 𝑗 max -𝑖 . Combining this with the hypothesis for iteration 𝑖, the imbalance of every class 𝑗 at 𝜇 𝑖-1 is at most 𝜖• 3 • 3 𝑗 max -𝑖 = 𝜖 • 3 𝑗 max -(𝑖-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) 𝑥, where 𝑥 is the measure of the chosen violating anti-cache state. The cost of this step is the cost of evicting a single page in 𝑃 𝑖 from a measure 𝑥; as we assume that the weight of a page is at most its UCB, this cost is at most 𝑥 • 6 𝑖+1 . The inductive claim above states that the imbalance of class 𝑖 at the beginning of Iteration 𝑖 is at most 𝜖 • 3 𝑗 max -𝑖 ; thus, the total cost of Iteration 𝑖 is at most 𝜖 • 3 𝑗 max -𝑖 • 6 𝑖+1 = 𝜖 • 6 𝑗 max +1 /2 𝑗 max -𝑖 . Summing over iterations, the total cost of REBALANCESUBSETS Overall, the imbalance in classes at most 𝑗 prior to calling REBALANCESUBSETS is at most 2𝜖. Through Lemma B.3, the cost of REBALANCESUBSETS is thus at most 24𝜖 • 6 𝑗 , which is at most 24𝜖 • UCB 𝑝 ′ . But, the increase in ONF due to the fractional eviction is at least 𝜖 • UCB 𝑝 ′ ; thus, the overall cost of REBALANCESUBSETS called in Line 10 is at most 24 • ONF.Finally, consider a call to REBALANCESUBSETS in Line 13, called upon a decrease in 𝑦 𝑝 ′ of 𝜖 for some page 𝑝 ′ . Using an identical argument to the case of eviction, we can bound the cost of this call by 24 times the "fetching cost" of 𝜖 • UCB 𝑝 ′ . Now, note that the fractional fetching of a page exceeds the fractional eviction by at most 1; thus, the total cost of such calls is at most 24ONF + 24𝑛.Summing all costs, the total expected cost of the algorithm is at most 62ONF + 50𝑛. □We now combine the ingredients in this paper to prove the main competitiveness bound for Algorithm 2.Proof of Theorem 1.1. First, assume the good event E. Combining Lemma 3.2, Lemma 3.1 and Lemma C.2, it holds thatE[ON] ≤ 𝑂 (log 𝑘) • OPT(𝑄) + Õ ( √ 𝑛𝑇)Next, assume that E does not occur. Upper bound the cost of the algorithm by 𝑂 (𝑛) per request, as in the worst case, the algorithm replaces the entire cache and samples each page in 𝑃 once. Thus, an upper bound for the cost of the algorithm is 𝑂 (𝑛𝑇). But, through Lemma C.1, the probability of E not occurring is at most 1 𝑛𝑇 . Thus, we can bound the expected cost of the algorithm as follows.E[ON] ≤ Pr[E] • 𝑂 (log 𝑘) • OPT(𝑄) + Õ ( √ 𝑛𝑇) + Pr[¬E] • 𝑂 (𝑛𝑇) ≤ 𝑂 (log 𝑘) • OPT(𝑄) + Õ ( √ 𝑛𝑇). □In this section we define the UCBs and LCBs, prove that they hold with high probability and bound the regret term.Let 𝑤 𝑖 𝑝 be the 𝑖-th sample of page 𝑝. For the initial confidence bounds, we sample each page once and set LCB 𝑝,1 = 1 2𝑛 2 𝑇 • 𝑤 1 𝑝 , UCB 𝑝,1 = 1. Once we have 𝑖 > 1 samples of page 𝑝, we define the confidence bounds as follows. Let w 𝑝,𝑖 := 1 𝑖 𝑖 𝑗=1 𝑤 𝑗 𝑝 be the average observed weight, and𝜖 𝑝,𝑖 = √︃ log(4𝑛 3 𝑇 3 ) 2𝑖be the confidence radius. Then, we set LCB 𝑝,𝑖 = max{LCB 𝑝,𝑖-1 , w 𝑝,𝑖 -𝜖 𝑝,𝑖 } and UCB 𝑝,𝑖 = min{UCB 𝑝,𝑖-1 , w 𝑝,𝑖 + 𝜖 𝑝,𝑖 }. The following procedure updates the confidence bounds online.We show that the confidence bounds indeed bound the true weights with high probability (Lemma C.1), and then bound the regret term (Lemma C.2). Lemma C.1. Let 𝑛 𝑝 be the final number of samples collected for page 𝑝. With probability at least 1 -1 𝑛𝑇 , the following properties hold. 1. 0 < LCB 𝑝,1 ≤ LCB 𝑝,2 ≤ . . . ≤ LCB 𝑝,𝑛 𝑝 ≤ 𝑤 𝑝 for every page 𝑝.2. 𝑤 𝑝 ≤ UCB 𝑝,𝑛 𝑝 ≤ UCB 𝑝,𝑛 𝑝 -1 ≤ . . . ≤ UCB 𝑝,1 = 1 for every page 𝑝. 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, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 it into the paper).We make a simplifying assumption that 𝑇 is known in advanced. This can be easily removed using a 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 at most 𝑘 pages, every fetched page is subsequently evicted, and thus the difference between eviction and fetching costs is at most 𝑘. Moreover, as we analyze additive regret, note that 𝑘 ≤ √ 𝑛𝑇, 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.Specifically, we show that the complementary event E happens with probability at most 1 𝑛𝑇 , and that the algorithm's cost is at most 𝑛𝑇 times the optimal cost when it happens. 


Decision: 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.

Reviews: review: paper_summary: paper_summary: Author consider caching with stochastic weights. In particular,
the cost incurred by the algorithm at eviction of a page p
is drawn independently from a fixed distribution D_p
which is different for every page and is not known to the algorithm in advance.
Authors propose an algorithm with guarantees which combine both
competitive ratio and regret. Authors claim that neither regret nor competitive
ratio are possible on their own.
Their algorithm is a modification of the classical algorithm
by Bansal et al. for weighted paging, incorporating upper and lower confidence
bounds on the average weight of the page.
The more challenging part seems to be randomized rounding, where they
have to deal with the changes of the upper confidence bounds and such
element was not present in the original paper of Bansal et al.
strength_weakness: strength_weakness: * I find the framing of their result in the context of hierarchical caching
and CPU caches very unfortunate for several reasons:

(1) hierarchical caching is already studied (see work of Bansal, Buchbinder, Naor SICOMP'12). Authors do not seem to be aware of this.

(2) It is completely unclear why should there be an underlying distribution
of the cost of loading each page in a hierarchical (or multi-level) cache:
It is enough that the algorithm operating on different levels of the cache
are mis-aligned in some way to make weights of the pages
adversarial instead of stochastic.

(3) I cannot imagine implementing anything resembling their approach
in CPU caches.

* Provided justification of the optimality of the presented results
is very informal. It is just a few lines.
In particular, authors argue about the necessity of the regret term using using
lower bounds for bandits. However, their input is stochastic which
allows much better regret bounds when the mean weights of the pages
differ significantly. On the other hand, if the weights of the pages are
similar, it is easy to achieve good competitive ratio.

* Statements of their results are not completely clear: E.g., what is Q in
Theorem 1.1? Theorem says it is an "input":
Is it composed of the request sequence and the distribution of
page weights, or does it contain also the realization of the page weights?
What is OPT(Q) then? I do not see these things explained even in preliminaries.
questions: questions: * Please comment on the last two weaknesses mentioned above.
limitations: limitations: Authors do not discuss possible difficulties in implementing their algorithm
in CPU caches although they use such use case as a main motivation.
paper_summary: paper_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).
strength_weakness: strength_weakness: 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

Doubts
- 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"
- 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) 
- 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
- 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.
- 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.
- 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?

Motivation
- 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.

Confused presentation
- 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
- the paper starts talking about moving fraction and servers at line 166 before referring to the parallel with the k-server problem
- 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.
- 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}



Minor
- the problem is sometimes referred to as OWP-UW, others as UW-OWP
- line 95: "the and rounding scheme"
- footnote 1: "known in advanced"
- in the figures the lables of the different subfigures (e.g. a, b, c, d in figure 1 are missing)

Update after rebuttal
- the authors have addressed some of my technical questions and I have increased the score.
questions: questions: See questions above.
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: I do not see any major weaknesses in this paper, but there are a few minor ones:
* 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.
* 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.
* 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
questions: 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: limitations: The assumptions of the theorems are clearly stated.
paper_summary: paper_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.

The authors present an algorithm that achieves the performance bound as follows:
$$
E[ALG]\ \leq O(\log k) OPT + \tilde{O}(\sqrt{nT}).
$$
Remark 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.
strength_weakness: strength_weakness: 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.
questions: 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?

It seems that the algorithm runs really slow because of the continuous rebalancing step. Can you remark on the running time of the algorithm?
limitations: 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.
paper_summary: paper_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.

The 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.
strength_weakness: strength_weakness: There is no lower bound in the paper. The regret bound might be far from tight, but this is expected in the first paper.
questions: questions: Could you comment on how tight the regret bound O(\sqrt{nT}) is? This seems to be a large number.
limitations: limitations: This is a theoretical paper, there is no potential negative societal impact.

Comments: title: Please comment on the rebuttal
comment: I'd like to thank the authors for addressing my concerns. The rebuttal addresses my concerns and I will keep my score.
We appreciate your feedback and would like to thank you for your consideration of our comments.

Regarding motivation, as stated in our response to Reviewer Yutu, there are multiple motivations for studying OWP-UW, as in essence the deterministic-weights assumption in previous papers is often unjustified. One specific example is stated in our comment to Reviewer Yutu (handling stochastic weights, e.g., when retrieving data from the internet). In the final version of the paper, we'll be sure to expand our motivation segment; e.g.,  through including this additional motivating case. 

Regarding writing, we thank you again for your feedback. We'll ensure that our final version has a clear presentation that addresses your concerns.
I thank the authors for their explanations. I was convinced by the technical answers. I still maintain that the motivation is quite weak (and I went through the discussion with the reviewer Yutu), the main text is packing too much information, and the presentation is quite disorganized. I am (slightly) increasing the original score.
Dear reviewer qj5j, MmEo and VdxB,

Can you please read and comment on the rebuttal from the authors? Please also try to take other reviews and responses into consideration.

Regards,
Area Chair
Our algorithm indeed handles even adversarial inputs, and does not rely on stochasticity in the request sequence. Of course, our algorithm can handle stochastic input sequences as well. 

Zooming out, it appears that your remaining concern is with the CPU cache motivating example. The goal of this example was merely demonstrating how sampled weighted instances can arise from seemingly unweighted instances. The motivation for studying OWP-UW is wider; in fact, we gave one such motivation in our previous comment regarding [1]. (We'll integrate this additional motivating case into the camera ready paper.) 

If indeed the only remaining concern is with the motivating paragraph, we hope that you'll consider revising your score accordingly. If there are any additional concerns, we'll be happy to address them.
> Suppose that the L2 cache fetches any page requested by a core, and evicts uniformly at random. Then, if a page is requested twice as often by the cores than another page, the probability of that page appearing in the cache at a given point in time is roughly twice as large.

this cannot be true unless you have some very strong assumptions about the request sequence. But the request sequence is adversarial in your setting, right?
Thank you for your comment,

Regarding motivation:
1. Suppose that the L2 cache fetches any page requested by a core, and evicts uniformly at random. Then, if a page is requested twice as often by the cores than another page, the probability of that page appearing in the cache at a given point in time is roughly twice as large. 
2. Perhaps more importantly than the specifics of the CPU cache example, we note that the motivation for our work is not different from that of any paper in the significant line of work on weighted caching. In fact, the assumption made in these previous papers that the page weights are known is often unjustified. For example, as you've mentioned [1], they use as motivation hierarchical caching for web pages:
*"This version of the problem is called weighted caching and it models scenarios in which the cost of fetching a page is not the same due to different locations of the pages (e.g., main memory, disk, Internet)"*. The cost of fetching a page from the internet cannot be assumed to be constant, and can be modeled much more realistically as drawn from some unknown distribution. This assumption made in all prior weighted paging papers ([1] included) is the one that our paper addresses.

Regarding the lower bounds: \
You have perhaps misunderstood the claim reflected in our lower bounds. We did *not* merely claim that either a competitive ratio or a regret term are needed. We claimed that (a) In the absence of a competitive ratio, a terrible regret term is needed (much worse than our regret bound), and (b) in the absence of a regret term, a terrible competitive ratio is needed (much worse than our competitive ratio). The conclusion to draw is that **both** a competitive ratio term and a regret term are needed. We will ensure that this point is emphasized well in the paper. 


*"Your problem is partially adversarial and partially stochastic which is not a particularly common setting"*: \
In fact, the majority of works in the field of multiarmed bandits use this setting. For example, in arguably the most well-known variant of MAB, each arm has a value distribution chosen adversarially, while the samples from this distribution are obtained stochastically. We nevertheless value the writing feedback and will ensure that our paper makes this clear.
* reference [1] shows how to model the hierarchical cache where the cost of a page load depends on what layer of the cache contains the page as a generalized caching problem.

* what algorithm do you expect to be maintaining the L2 cache? Which algorithm satisfies the property that a given page is in the cache with some probability dependent only on the page itself? I do not find expecting such property reasonable at all. Does your algorithm satisfy this property?

* Yes, there are many theoretical papers on caching but it is definitely not common motivating a complicated and resource demanding algorithm by CPU caches.

to sum up, I am still not happy about the framing of your result.

Now about the tightness of your result. You provide a bound which combines a competitive ratio with a regret term depending on T.  You claim that sometimes you may need the regret term and sometimes competitive ratio. But your bound contains both at the same time, which  is pretty weak in the context of the competitive analysis as well regret analysis. Do you have a lower bound showing that you need both terms at the time? I have explained my doubts about the existence of such bound in my review.

thank you for explaining the statement of your theorem. your problem is partially adversarial and partially stochastic which is not a particularly common setting. I believe that this deserves a proper explanation in the paper.
I thank the authors for their response, and I strongly encourage them to add the necessary discussion on the relation with learning-augmented algorithms, and in particular the works where the unknown variables are learned during the algorithm execution.

I would have liked to see experiments mostly because I am curious to observe if the asymptotic behavior, when T is very large, aligns with that of prior algorithms that have knowledge of the weights, in terms of the multiplicative constant in $O(\log k)$. However, I agree that this is not a major weakness of the paper, but a suggestion instead, as the theoretical contribution is sufficiently interesting.