New and Improved Bounds for Markov Paging Chirag Pabbaraju, Ali Vakilian Abstract In the Markov paging model, one assumes that page requests are drawn from a Markov chain over the pages in memory, and the goal is to maintain a fast cache that suffers few page faults in expectation. While computing the optimal online algorithm ( OPT ) (\mathrm{OPT}) for this problem naively takes time exponential in the size of the cache, the best-known polynomial-time approximation algorithm is the dominating distribution algorithm due to Lund, Phillips and Reingold (FOCS 1994), who showed that the algorithm is 4 4 -competitive against OPT \mathrm{OPT} . We substantially improve their analysis and show that the dominating distribution algorithm is in fact 2 2 -competitive against OPT \mathrm{OPT} . We also show a lower bound of 1.5907 1.5907 -competitiveness for this algorithm—to the best of our knowledge, no such lower bound was previously known. 1 Introduction The online paging problem is a fundamental problem in the area of online algorithms. There are n pages in slow memory, and requests for these pages arrive in a sequential manner. We are allowed to maintain a fast cache of size k , which initially comprises of some k pages. At time step t , if the page that is requested, say p_{t} , exists in the cache, this corresponds to a cache hit: we suffer a zero cost, the cache stays as is, and we move on to the next request. Otherwise, we incur a cache miss/page fault, suffer a unit cost, and are forced to evict some page from the cache so as to bring p_{t} from the slow memory into the cache. A paging algorithm/policy is then specified by how it chooses the page to evict whenever it suffers a cache miss. An optimal offline algorithm for this problem is the algorithm that has entire knowledge of the page request sequence, and thereafter makes its eviction choices in a way that minimizes the total number of cache misses it incurs. The classical Farthest-in-Future algorithm ( Belady 1966 ) , which at any cache miss, evicts the page that is next requested latest in the remainder of the sequence, is known to be an optimal offline policy. In the spirit of competitive analysis as introduced by Sleator and Tarjan 1985 , one way to benchmark any online algorithm (i.e., one which does not have knowledge of the page request sequence) is to compute the ratio of the number of page faults that the algorithm suffers, to the number of page faults that the optimal offline algorithm suffers, on a worst-case sequence of page requests. It is known that any deterministic online algorithm has a worst-case ratio that is at least k , while any randomized online algorithm has a worst-case ratio of \Omega(\log k) . Taking a slightly more optimistic view, one can also consider benchmarking an algorithm against the best online algorithm, that does not know beforehand the realized sequence of page requests. Additionally, in the context of beyond worst-case analysis, one can impose assumptions on the sequence of page requests to more accurately model the behavioral characteristics of real-world page requests on computers. For example, page requests generally follow the locality of reference principle, either in time (the next time a particular page is requested is close to its previous time) or in space (the page that will be requested next is likely to be in a nearby memory location). The Markov Paging model, introduced by Karlin et al. 1992 , is one of the ways to model such locality of reference in the page requests. The model assumes that page requests are drawn from a (known) Markov chain over the entire set of n pages. Once such a distributional assumption over the page requests is imposed, one can ask how an online paging algorithm fares, in comparison to the optimal online algorithm that suffers the smallest number of page misses in expectation over the draw of a page sequence from the distribution. As it turns out, one can compute such an optimal online algorithm, but only in time exponential in the cache size k . Therefore, one seeks efficient polynomial-time algorithms that are approximately optimal. In 1994, Lund et al. 1994 proposed an extremely elegant randomized algorithm for the Markov Paging problem, known as the dominating distribution algorithm. The dominating distribution algorithm, whenever it suffers a cache miss, evicts a random page drawn from a special distribution, which has the property that a randomly drawn page is likely to be next requested latest among all the existing pages in the cache. This algorithm, which has since become a popular textbook algorithm due to its simplicity (e.g., see Chapter 5 in Borodin and El-Yaniv 2005 , or the lecture notes by Roughgarden 2010 ), runs in time polynomial in k ; furthermore, Lund et al. 1994 show that the algorithm suffers only 4 times more cache misses in expectation than the optimal online algorithm. Since then, this has remained state-of-the-art—we do not know any other polynomial-time algorithms that achieve a better performance guarantee. It has nevertheless been conjectured that the above guarantee for the dominating distribution algorithm is suboptimal (e.g., see Section 6.2 in Roughgarden 2010 ). Our main result in this work establishes an improved upper bound for the dominating distribution algorithm. Theorem 1 . The dominating distribution algorithm suffers at most 2 times more cache misses in expectation compared to the optimal online algorithm in the Markov Paging model. In fact, as mentioned in Lund et al. 1994 , our guarantee for the performance of the dominating distribution algorithm holds more generally for pairwise-predictive distributions. These are distributions for which one can compute any time, for any pair of pages p and q in the cache, the probability that p is next requested before q in the future (conditioned on the most recent request). While the dominating distribution algorithm is a randomized algorithm, Lund et al. 1994 also propose and study a simple deterministic algorithm for the Markov Paging model, known as the median algorithm. On any cache miss, the median algorithm evicts the page in cache that has the largest median time at which it is requested next. Lund et al. 1994 show that the median algorithm suffers at most 5 times more cache misses in expectation than the optimal online algorithm—to the best of our knowledge, this is the state of the art for deterministic algorithms. As an additional convenient consequence of our improved analysis, we are also able to improve the performance guarantee for the median algorithm. Theorem 2 . The median algorithm suffers at most 4 times more cache misses in expectation compared to the optimal online algorithm in the Markov Paging model. Given the improved performance guarantee in Theorem 1 , one can ask: is this the best bound that we can show for the dominating distribution algorithm? Or is there hope to show that it is the optimal online algorithm? A detail here is that the dominating distribution algorithm is defined as any algorithm satisfying a specific property (see ( 4 )); in particular, there can exist different dominating distribution algorithms. Our upper bound ( Theorem 1 ) holds uniformly for all dominating distribution algorithms. However, our next theorem shows a lower bound that at least one of these is significantly suboptimal. Theorem 3 . There exists a dominating distribution algorithm that suffers at least 1.5907 times more cache misses in expectation compared to the optimal online algorithm in the Markov Paging model. Theorem 3 shows that one cannot hope to show optimality uniformly for all dominating distribution algorithms. To the best of our knowledge, no such lower bounds for the dominating distribution algorithm have been previously shown. While we believe that the bound in Theorem 1 is the correct bound, it is an interesting open direction to close the gap between the upper and lower bound. Finally, we also consider a setting where the algorithm does not exactly know the Markov chain generating the page requests, but only has access to a dataset of past page requests. In this case, one can use standard estimators from the literature to approximate the transition matrix of the Markov chain from this dataset. But can an approximate estimate of the transition matrix translate to a tight competitive ratio for a paging algorithm, and if so, how large of a dataset does it require to achieve it? The robustness of the analysis 1 1 1 In fact, we borrow this robustness from the original analysis of Lund et al. 1994 . of Theorem 1 lets us derive a precise learning-theoretic result ( Theorem 6 in Section 7 ) showing that the dominating distribution algorithm, when trained on a dataset of size O(n^{2}/\varepsilon^{2}) , is no more than \frac{2}{1-2\varepsilon} times worse than the optimal online algorithm on a fresh sequence of page requests. This result is especially relevant in the context of data-driven and learning-augmented algorithms. For instance, by treating the learned Markov chain as a learned oracle and combining it with a worst-case approach, such as the Marker algorithm, similarly to the approach proposed in ( Mahdian et al. 2012 ; Lykouris and Vassilvitskii 2021 ) , the resulting algorithm achieves O(1) -consistency and O(\log k) -robustness guarantees for the online paging problem. Algorithm Reference Upper Bound Lower Bound Lund et al. 1994 4 - Dominating Distribution (Theorem 3.5) (Randomized) This Work 2 1.5907 ( Theorem 1 ) ( Theorem 3 ) Lund et al. 1994 5 1.511 2 2 2 Lund et al. 1994 only provide a proof for a lower bound of 1.4, but mention that they also obtained 1.511. Median (Theorem 2.4) (Theorem 5.4) (Deterministic) This Work 4 - ( Theorem 2 ) Table 1 : State of the art for Markov Paging (best-known bounds are in bold). Both the median and the dominating distribution algorithm are due to Lund et al. 1994 . 1.1 Other Related Work There is a rich literature by this point on studying the online paging problem under assumptions on the permissible page requests that are supposed to model real-world scenarios (see e.g., the excellent surveys by Irani 2005 and Dorrigiv and López-Ortiz 2005 ). In particular, several models are motivated by the aforementioned locality of reference principle. The access graph model, proposed originally by Borodin et al. 1991 , and developed further in the works of Irani et al. 1992 , Fiat and Karlin 1995 and Fiat and Mendel 1997 , assumes an underlying graph on the pages, which a request sequence is supposed to abide by. Namely, if a page p_{t} has been requested at time t , then only the neighbors of p_{t} in the graph may be requested at time t+1 . In this sense, the Markov Paging model can be thought of as a probabilistic variant of the access graph model. Torng 1998 models locality of reference based on the “working sets” concept, introduced by Denning 1968 , and also shows how a finite lookahead of the page sequence can be used to obtain improved guarantees. A related form of competitive analysis, proposed by Koutsoupias and Papadimitriou 2000 , assumes that there is a family of valid distributions, and page sequences are drawn from some distribution belonging to this family. The goal of an algorithm is then to be simultaneously competitive with the optimal algorithm for every distribution in the family. A particular family of interest suggested by Koutsoupias and Papadimitriou 2000 (which is incomparable to the Markov Paging model) is that of diffuse adversaries , which has since been developed further in follow-up works by Young 1998 ; Young 2000 and Becchetti 2004 . Finally, Angelopoulos and Schweitzer 2009 study paging under the bijective analysis framework, which compares the performance of two algorithms under bijections on page request sequences. 2 Background and Setup 2.1 Markov Paging The Markov Paging model assumes that the page requests are drawn from a time-homogeneous Markov chain, whose state space is the set of all pages. More precisely, the Markov Paging model is specified by an initial distribution on the n pages, and a transition matrix M\in[0,1]^{n\times n} , where M_{i,j} specifies the probability that page j is requested next, conditioned on the most recently requested page being i . The form of the initial distribution will not be too important for our purposes, but for concreteness, we can assume it to be the uniform distribution on the n pages. It is typically assumed that the transition matrix M is completely known to the paging algorithm/page eviction policy—however, the realized page sequence is not. Upon drawing T page requests from the Markov chain, the objective function that a page eviction policy \mathcal{A} seeks to minimize is: \displaystyle\operatorname{{\mathds{E}}}[\mathrm{Cost}(\mathcal{A},T)] \displaystyle=\operatorname{{\mathds{E}}}_{M,\mathcal{A}}\left[\sum_{t=1}^{T}\mathds{1}[\text{$\mathcal{A}$ suffers a cache miss at time $t$}]\right], (1) where the expectation is with respect to both the random page request sequence drawn from M , and the randomness in the policy \mathcal{A} . We denote by \mathrm{OPT} the policy that minimizes the objective in ( 1 ). For c\geq 1 , an eviction policy \mathcal{A} is said to c -competitive against \mathrm{OPT} if for every T , \operatorname{{\mathds{E}}}[\mathrm{Cost}(\mathcal{A},T)]\leq c\cdot\operatorname{{\mathds{E}}}[\mathrm{Cost}(\mathrm{OPT},T)] . It is worth emphasizing again that the competitive analysis above is with respect to the optimal online strategy, in that \mathrm{OPT} does not know beforehand the realized sequence of page requests. Contrast this to the best offline strategy, which also additionally knows the realized sequence of page requests. As mentioned previously, the Farthest-in-Future policy ( Belady 1966 ) , which at any cache miss, evicts the page that is next requested latest in the remainder of the sequence, is known to be an optimal offline policy. It is indeed possible to compute \mathrm{OPT} exactly—however, the best known ways do this are computationally very expensive, requiring an exponential amount of computation in k . Theorem 4 (Theorems 1, 2 in Karlin et al. 1992 ) . The optimal online policy that minimizes \lim_{T\to\infty}\frac{1}{T}\cdot\operatorname{{\mathds{E}}}[\mathrm{Cost}(\mathcal{A},T)] over all policies \mathcal{A} can be computed exactly by solving a linear program in n\binom{n}{k} variables. Furthermore, for any finite T , an optimal online policy that minimizes \operatorname{{\mathds{E}}}[\mathrm{Cost}(\mathcal{A},T)] can be computed in time T\cdot n^{\Omega(k)} . In the latter case above when T is finite, the optimal online policy can be computed, for example, via dynamic programming (using the “Bellman operator”), where one writes the recurrence for taking a single step of the optimal policy, and unrolls time backwards from T . However, the state space in the dynamic program comprises of all \{ cache state, requested page \} pairs—there are n^{\Omega(k)} many of these. Similarly, the linear program in the case where T\to\infty also comprises of a single variable for each such state. Unfortunately, we do not know of any better algorithms that are both optimal and run in polynomial time in k . Therefore, one seeks efficient polynomial time (in k ) algorithms that are approximately optimal, i.e., achieve c -competitiveness with \mathrm{OPT} for c as close to 1 as possible. Towards this, Karlin et al. 1992 showed that several intuitive eviction policies (e.g., on a cache miss, evict the page in cache that has the largest expected time to be requested next) are necessarily at least an \Omega(k) factor suboptimal compared to \mathrm{OPT} . They then showed a policy \mathcal{A} that is provably O(1) -competitive against \mathrm{OPT} ; however, the constant in the O(1) is somewhat large. Thereafter, Lund et al. 1999 3 3 3 We reference the journal version ( Lund et al. 1999 ) in lieu of the conference version ( Lund et al. 1994 ) hereafter. proposed a simple and elegant polynomial-time policy, referred to as the dominating distribution algorithm , and showed that it achieves 4 -competitiveness against \mathrm{OPT} . We describe this policy ahead. 2.2 Dominating Distribution Algorithm The dominating distribution algorithm, which was proposed by Lund et al. 1999 and is denoted \mathcal{A}_{\mathrm{dom}} hereon, operates as follows. At any page request, if \mathcal{A}_{\mathrm{dom}} suffers a cache miss, it computes a so-called dominating distribution \mu over the currently-existing pages in the cache. Thereafter, it draws a page p\sim\mu , and evicts p . First, we will specify the properties of this dominating distribution. Intuitively, we want \mu to be a distribution such that a typical page drawn from \mu will be highly likely to be next requested later than every other page in the cache. Formally, suppose that the most recently requested page (that caused a cache miss) is s . Fix any two pages p and q (not necessarily in the cache), and let \displaystyle\alpha(pt_{1} but t_{2}T . Thus, this charge is included in \mathcal{O} , canceling out the contribution due to the cache miss at t_{2} . This suggests that whenever a page is requested, we should clear not only the charges it gives but also any charges it bears , preventing unnecessary inclusion in \mathcal{O} . This approach ensures that a page discards its imposed charge immediately upon “paying it off” rather than with a delay. 4.3 No Accounting for Uncharged, Non-first-timer Pages Finally, observe that in the accounting of cache misses for \mathrm{OPT} , we only count those that occur due to requests to charged/savior pages (as counted by the \beta(t) ’s), and those that occur due to first-time requests to pages not initially in the cache (as counted by \mathcal{I} ). However, \mathrm{OPT} can also suffer cache misses due to a request to an uncharged page. Namely, if there is a request to a page q that was previously evicted by \mathrm{OPT} , but at the time that it is requested, q is bearing no charges at all, then the cache miss due to q is not being counted in the calculation. This is illustrated by the scenario below: Figure 4 : At t_{3} , q does not have any charges on it, but still causes a cache miss for \mathrm{OPT} . \mathcal{A} evicts p at time t_{1} and assigns a charge to q\neq p , implying that q is not in the cache of \mathrm{OPT} after the request at t_{1} (but was instead previously evicted by \mathrm{OPT} ). Next, at t_{2} , p is requested, and this clears the charge it had on q . Since p got requested before q , \beta(t_{1})=0 . Then, at t_{3} , q is requested— q has no charges on it at this point. Notice that this still causes a cache miss for \mathrm{OPT} at t_{3} . However, this cache miss is not accounted for in our calculation, either by \beta(t_{1}) , or by \mathcal{I} (since this is not the first time that q is being brought into the cache). 5 Tightening the Analysis to 2-competitiveness Having identified the loose ends in the analysis of Lund et al. 1999 above, we are able to tighten their analysis and prove the following lemma: Lemma 5.1 . Let \mathcal{A} be a paging algorithm. Suppose that whenever \mathcal{A} suffers a cache miss, the page p that it chooses to evict is chosen from a distribution such that the following property is satisfied: for every page q in the cache, the probability (over the choice of p and the random sequence ahead, conditioned on the most recently requested page) that q is next requested no later than the next request for p is at least 1/c . Then \mathcal{A} is c -competitive against \mathrm{OPT} . Proof. We make one small change (highlighted in green) to Item 1 in the charging scheme ( Figure 1 ) from the analysis of Lund et al. 1999 —whenever a new page is requested, any charges that this page might be giving are cleared, but also any charges that other pages might be having on the requested page are also cleared. This fixes the issue regarding uncleared charges discussed in Section 4.2 . Suppose that at time t , there is a request for page s . 1. (a) Set c(s)=\emptyset . (b) For any page p that has c(p)=s , set c(p)=\emptyset . 2. If \mathcal{A} evicts some page p , c(p) is selected as follows: (a) If p\notin\mathrm{OPT}^{+} , set c(p)=p . (b) If p\in\mathrm{OPT}^{+} , find a page q\in\mathcal{A}^{-}\setminus\mathrm{OPT}^{+} that has no charges from \mathrm{OPT}^{+}\setminus\mathcal{A}^{-} . Set c(p)=q . 3. If \mathrm{OPT} evicts some page p and c(p)\neq p , set c(p)=p . Figure 5 : Updated Charging Scheme Let \alpha(t) and \beta(t) be the same random variables as defined in ( 6 ), ( 3 ) in the proof of Lemma 3.1 . Further, let \mathcal{I} and \mathcal{O} be the same random variables as defined there as well. Note that even with the slightly-changed charging scheme, \mathcal{I} remains quantitatively the same; the random variable \mathcal{O} however changes—in particular, it potentially becomes a smaller number, because we are clearing charges more aggressively. The random variable \displaystyle\sum_{t\leq T}\beta(t)-\mathcal{O} nevertheless still counts the cache misses suffered by \mathrm{OPT} due to requests to savior pages, while potentially double-counting a few misses. However, to account for this double-counting, instead of dividing every miss by 2 (which was the issue discussed in Section 4.1 ), we explicitly keep track if some \beta(t) corresponds to a request to a doubly-charged page, and subtract it from our calculation. Formally, let \displaystyle\mathcal{D}=\sum_{t\leq T}\mathds{1}[\text{Page $\boldsymbol{p}$ requested at time $t$ has two charges on it}]. (9) Then, the quantity \displaystyle\sum_{t\leq T}\beta(t)-\mathcal{D}-\mathcal{O} counts the cache misses suffered by \mathrm{OPT} due to requests to savior pages more precisely, and without double-counting any miss. This crucially allows us to avoid an unnecessary factor of 2 . Lastly, in order for the analysis to go through, we have to also fix the final issue regarding requests to uncharged pages described in Section 4.3 . We simply do this by keeping track of an additional quantity that counts this, and add it to our calculation. Namely, let \displaystyle\mathcal{U}=\sum_{t\leq T}\mathds{1}[ Page \boldsymbol{p} requested at time t does not exist in \mathrm{OPT} ’s cache at this time because it was \displaystyle\text{previously evicted by $\mathrm{OPT}$, and $\boldsymbol{p}$ has no charges on it}]. (10) Then, combining all of the above, we have that \displaystyle\mathrm{Cost}(\mathrm{OPT},T) \displaystyle\geq\sum_{t\leq T}\beta(t)-\mathcal{D}-\mathcal{O}+\mathcal{U}. (11) Comparing this to the accounting in ( 8 ), it at least seems plausible that by not halving, we might be able to save a factor of 2. Namely, taking expectations, we obtain that \displaystyle\operatorname{{\mathds{E}}}[\mathrm{Cost}(\mathrm{OPT},T)] \displaystyle\geq\sum_{t\leq T}\operatorname{{\mathds{E}}}[\beta(t)]+\operatorname{{\mathds{E}}}[\mathcal{I}-\mathcal{D}-\mathcal{O}+\mathcal{U}] \displaystyle\geq\frac{1}{c}\sum_{t\leq T}\operatorname{{\mathds{E}}}[\alpha(t)]+\operatorname{{\mathds{E}}}[\mathcal{I}-\mathcal{D}-\mathcal{O}+\mathcal{U}] \displaystyle=\frac{1}{c}\operatorname{{\mathds{E}}}[\mathrm{Cost}(\mathcal{A},T)]+\operatorname{{\mathds{E}}}[\mathcal{I}-\mathcal{D}-\mathcal{O}+\mathcal{U}], where the first inequality follows from the same analysis that we did in the proof of Lemma 3.1 . It remains to argue that the quantity \operatorname{{\mathds{E}}}[\mathcal{I}-\mathcal{D}-\mathcal{O}+\mathcal{U}] is nonnegative. Note that the random variable \mathcal{I}-\mathcal{D}-\mathcal{O}+\mathcal{U} starts out being 0 before the very first request at time t=1 . We will argue that it always stays nonnegative thereafter via the following two claims. Claim 5.2 . If the page s requested at time t satisfies the following condition: s exists in \mathrm{OPT} ’s cache and s does not exist in \mathcal{A} ’s cache and s is not giving a charge and s is not bearing any charges, then the random variable \mathcal{I}-\mathcal{D}-\mathcal{O}+\mathcal{U} decreases by 1 from t to t+1 . Furthermore, if the page s requested at time t does not satisfy this condition, then \mathcal{I}-\mathcal{D}-\mathcal{O}+\mathcal{U} either increases or stays the same from t to t+1 . Proof. We first show that if the page s requested at time t satisfies the condition, then \mathcal{I}-\mathcal{D}-\mathcal{O}+\mathcal{U} decreases by 1. Since s is in \mathrm{OPT} ’s cache, the request to s does not change \mathcal{U} (see the definition in ( 10 )). Moreover, s being in \mathrm{OPT} ’s cache implies it was either in the initial cache or previously requested, so \mathcal{I} also remains unchanged. Similarly, because s is not doubly charged, \mathcal{D} remains unchanged. Thus, we only need to account for the change in \mathcal{O} . Because s is neither giving nor bearing any charges, both Item 1a and Item 1b cause no change in \mathcal{O} . Finally, because s does not exist in \mathcal{A} ’s cache and results in a cache miss, Item 2 creates a new charge, causing \mathcal{O} to increase by 1. In total, \mathcal{I}-\mathcal{D}-\mathcal{O}+\mathcal{U} decreases by 1. Next, we will show that if s does not satisfy the condition, then \mathcal{I}-\mathcal{D}-\mathcal{O}+\mathcal{U} either increases or stays the same. Towards this, consider each of the following cases: Case 1: s is a doubly-charged page. In this case, \mathcal{D} increases by 1. Note that one of the charges on s is by s itself, and the other charge is by some other page q . In particular, s is not giving a charge to a page other than itself. Thus, when s is requested, Item 1a and Item 1b ensure that the charge by s on itself as well as the charge on s by q are both dropped. 8 8 8 Note how Item 1b was necessary to ensure this. However, note also that s is not in the cache of \mathcal{A} (since it has a charge on itself, it was previously evicted by \mathcal{A} ), and hence this request has caused a cache miss in \mathcal{A} , resulting in the creation of a new charge in Item 2 . Item 3 can only reassign a charge, and thus, the net change in \mathcal{O} is -1 . Finally, \mathcal{I} and \mathcal{U} remain the same. Therefore, the overall change in \mathcal{I}-\mathcal{D}-\mathcal{O}+\mathcal{U} is 0. Case 2: s is a singly-charged page. This means that either s is not in the cache of \mathcal{A} and is charging itself, or s is in the cache of \mathcal{A} and is bearing a charge given by some other page p at the time of its eviction. In the former case, observe that none of \mathcal{I} , \mathcal{D} or \mathcal{U} are affected. The clearing of charges in Item 1 causes \mathcal{O} to decrease by 1, and the cache miss causes the creation of a new charge in Item 2 . In total, \mathcal{I}-\mathcal{D}-\mathcal{O}+\mathcal{U} stays unchanged. In the latter case, observe that the charge on s is cleared in Item 1b , causing \mathcal{O} to decrease by 1. Furthermore, because s is in the cache of \mathcal{A} , there is no creation of a new charge in Item 2 . Thus, \mathcal{I}-\mathcal{D}-\mathcal{O}+\mathcal{U} increases by 1. Case 3: s is not in \mathrm{OPT} ’s cache. If s is either singly or doubly-charged, we fall under Case 1 or 2. If s has no charges on it, then: Subcase 3a: s has never been requested before. In this case, \mathcal{I} increases by 1. Also, s cannot be giving or bearing any charges; thus Item 1a and Item 1b cause no change to \mathcal{O} . However, the request to s causes a cache miss in \mathcal{A} , resulting in an eviction, and the creation of a new charge. Thus, \mathcal{O} increases by 1. Additionally, \mathcal{D} and \mathcal{U} remain the same. Thus, the net change in \mathcal{I}-\mathcal{D}-\mathcal{O}+\mathcal{U} is 0. Subcase 3b: s has been requested before. This means that s was previously in \mathrm{OPT} ’s cache at some time but was since evicted. Also, s has no charges on it. Thus, \mathcal{U} increases by 1, while \mathcal{I} and \mathcal{D} remain unchanged. It remains to reason about \mathcal{O} . Because s has no charges on it, Item 1b causes no change in \mathcal{O} . Item 1a either decreases \mathcal{O} by 1 or causes no change to it. While the request to s can cause a cache miss to \mathcal{A} , this can only result in the creation of a single new charge, and \mathcal{O} can increase by at most 1 due to this. In total, \mathcal{I}-\mathcal{D}-\mathcal{O}+\mathcal{U} either increases or stays the same. Case 4: s is in \mathcal{A} ’s cache. This means that s is giving no charges. Then, either s is singly-charged or has no charges on it. It cannot be doubly-charged because it would have to be out of \mathcal{A} ’s cache for that. If it is singly-charged, we fall under Case 2. If it has no charges on it, we reason as follows: both Item 1 and Item 2 leave \mathcal{O} unaffected. Moreover, \mathcal{I} and \mathcal{D} remain unaffected. Finally, depending on whether s is or isn’t in \mathrm{OPT} ’s cache, \mathcal{U} either stays the same or increases. Hence, \mathcal{I}-\mathcal{D}-\mathcal{O}+\mathcal{U} either stays the same or increases. Case 5: s is giving a charge. If s has any charges on it, we fall under Case 1 or 2. So we assume that s has no charges on it. This means that s is not in \mathcal{A} ’s cache, but is still in \mathrm{OPT} ’s cache. Note then that \mathcal{I},\mathcal{D},\mathcal{U} remain unchanged. We reason about the change in \mathcal{O} as follows: Item 1a clears the charge that s is giving and decreases \mathcal{O} by 1, whereas Item 2 creates a new charge and increases \mathcal{O} by 1. In total, \mathcal{I}-\mathcal{D}-\mathcal{O}+\mathcal{U} remains unchanged. Thus, in any way that the requested page s might not satisfy the condition, \mathcal{I}-\mathcal{D}-\mathcal{O}+\mathcal{U} either increases or stays the same, concluding the proof. ∎ Claim 5.3 . If the page s requested at time t satisfies the condition: s exists in \mathrm{OPT} ’s cache and s does not exist in \mathcal{A} ’s cache and s is not giving a charge and s is not bearing any charges, then \mathcal{I}-\mathcal{D}-\mathcal{O}+\mathcal{U} is strictly positive just before this request. Proof. Consider any time t where the requested page s satisfies the condition. We can associate to the page s two past events occurring at times t_{1} and t_{2} (where t_{1}0 . In this case, the Markov chain is irreducible (meaning that there is a positive, and unique probability of eventually getting from any state to another). Thus, in this case, for every fixed p,q , the linear system ( 3 ) has a (unique) solution, meaning that matrix associated with it is invertible. The relevant quantity here will be the conditioning of the worst linear system that we might ever have to solve. Towards this, let L_{p,q} be the matrix associated with the linear system in ( 3 ) for pages p,q , and define: \displaystyle\gamma \displaystyle=\sup_{p\neq q}\|L_{p,q}^{-1}\|_{\infty}, (16) where for a square matrix A\in\mathds{R}^{n\times n} , \|A\|_{\infty}=\sup_{i}\sum_{j}|A_{i,j}| . Observe from ( 3 ) that 1\leq\|L_{p,q}\|_{\infty}\leq 2 for every p,q . We choose to adopt the following result of Hao et al. 2018 for our exposition: Theorem 6 (Theorem 4 in Hao et al. 2018 ) . Suppose we unroll a Markov chain to obtain m samples X_{1},\dots,X_{m} , where the initial distribution of X_{1} is arbitrary, but the transition matrix M\in[0,1]^{n\times n} of the Markov chain satisfies M_{i,j}\geq\delta>0 for every i,j . Then, there exists an estimator \hat{M}=\hat{M}(X_{1},\dots,X_{m}) that satisfies \displaystyle\operatorname{{\mathds{E}}}_{X_{1},\dots,X_{m}}\|M(i,:)-\hat{M}(i,:)\|_{2}^{2}\leq O\left(\frac{1}{m\delta}\right) for every i\in[n] , where M(i,:) (respectively \hat{M}(i,:) ) denotes the i^{\text{th}} row of M (respectively \hat{M} ). Using this theorem, we can obtain the following result: Theorem 7 . Suppose that the page requests are generated from an unknown Markov chain where every entry in the transition matrix M is at least \delta>0 . Let \gamma be as defined in ( 16 ). Given a training dataset of m=O\left(\frac{\gamma^{2}n^{2}}{\varepsilon^{2}\delta}\right) past page requests from M , there is an algorithm \mathcal{A} which is \frac{2}{1-2\varepsilon} -competitive against \mathrm{OPT} with probability at least 0.99 over the m samples. Proof. From the initial m page requests, \mathcal{A} constructs the estimator \hat{M} given by Theorem 6 . Applying Markov’s inequality to the in-expectation guarantee on \hat{M} , for every fixed i\in[n] , we have that with probability at least 1-0.01\cdot\frac{1}{n} , \displaystyle\|M(i,:)-\hat{M}(i,:)\|_{2}^{2}\leq O\left(\frac{n}{m\delta}\right). A union bound over the universe of n pages gives that with probability at least 0.99 , we have that \displaystyle\sup_{i\in[n]}\|M(i,:)-\hat{M}(i,:)\|_{2}^{2}\leq O\left(\frac{n}{m\delta}\right) The Cauchy-Schwarz inequality then implies that with probability at least 0.99 , \displaystyle\sup_{i\in[n]}\sum_{j=1}^{n}|M(i,j)-\hat{M}(i,j)|\leq O\left(\frac{n}{\sqrt{m\delta}}\right). Denoting \Delta=\hat{M}-M , we have effectively argued that \|\Delta\|_{\infty}\leq O\left(\frac{n}{\sqrt{m\delta}}\right) with probability at least 0.99 . The algorithm \mathcal{A} plays the dominating distribution algorithm as its eviction policy on a cache miss; however, it constructs the dominating distribution using the estimator \hat{M} . Namely, for every pair p,q , let \hat{L}_{p,q} be the matrix associated with the linear system in ( 3 ), where instead of the entries in M , we plug in entries from our estimator \hat{M} . Consider the solution \hat{x} of the perturbed linear system \hat{L}_{p,q}\cdot\hat{x}=b_{p,q} , where b_{p,q} is the right-hand side of ( 3 ). We care about bounding the difference between \hat{x} and x , where x is the solution to L_{p,q}\cdot x=b_{p,q} . Note that the right-hand side in both the perturbed and unperturbed systems (namely b_{p,q} ) is still the same. From a standard analysis of solutions to perturbed linear systems (e.g., see Theorem 1 in ( Falk 2016 ) ), we have that \displaystyle\|\hat{x}-x\|_{\infty} \displaystyle\leq\frac{\|L_{p,q}^{-1}\|_{\infty}\|\hat{L}_{p,q}-L_{p,q}\|_{\infty}\|x\|_{\infty}}{1-\|L_{p,q}^{-1}\|_{\infty}\|\hat{L}_{p,q}-L_{p,q}\|_{\infty}}. Now, observe that \|\hat{L}_{p,q}-L_{p,q}\|_{\infty}\leq\|\Delta\|_{\infty} , and also that \|x\|_{\infty}=1 . Plugging in our bound above on \Delta , we get \displaystyle\|\hat{x}-x\|_{\infty} \displaystyle\leq\frac{O(\gamma n/\sqrt{m\delta})}{1-O(\gamma n/\sqrt{m\delta})}. Setting m=C\cdot\frac{\gamma^{2}n^{2}}{\varepsilon^{2}\delta} for a constant C is sufficient to make the right-hand side above to be at most \varepsilon . 10 10 10 In fact, this is also sufficient to satisfy the technical condition of Theorem 1 in ( Falk 2016 ) that we used. But this means that all the \hat{\alpha}(p