Staying up to Date with Online Content Changes Using
Reinforcement Learning for Scheduling

Andrey Kolobov 1 Yuval Peres 2 Cheng Lu 3 Eric Horvitz 4

Abstract
From traditional Web search to virtual assistants
and Web accelerators, services that rely on online information need to keep track of continuing
content changes. Many of these services need to
explicitly request content updates from remotesources (e.g., web pages), which gives rise to aformidable challenge. A search engine, for example, may track billions of sources, with content
change timing or even frequency being initiallyunknown for most. How should it schedule requests for updates under constraints of network
bandwidth? We introduce a novel optimization
objective for this setting that has several desirable
properties, and efficient algorithms for it with optimality guarantees even in the face of mixed content change observability and initially unknown
model parameters. An evaluation on a set of 20M
web pages crawled daily for 14 weeks shows thescalability and other properties of our approach.

1. Introduction
As the Web becomes more and more dynamic, services that
rely on web data face the increasingly challenging problemof keeping up with online content changes. Whether it bea continuous-query system (Pandey et al., 2003), a virtualassistant like Cortana or Google Now, or an Internet searchengine, such a service tracks many remote sources of information – web pages or data streams (Pandey et al., 2004).
Users expect these services, which we call trackers, to be
surface the latest information that appears at the sources.
This is easy to do when the remote sources push content
updates to the tracker. Unfortunately, the push model is impractical for maintaining databases as large as major searchengines’ indexes (Baeza-Yates & Ribeiro-Neto, 1999) andconversation agents’ knowledge graphs (Hixon et al., 2015).
Instead, for all sources they track, these services must continually decide when to re-request (crawl) their data in order1
akolobov@microsoft.com, Microsoft Research, Redmond,
WA, USA 2 At Microsoft Research at the time of work on thispublication 3 Cheng.Lu@microsoft.com, Microsoft Bing, Bellevue, WA, USA 4 horvitz@microsoft.com, Microsoft Research,
Redmond, WA, USA. Correspondence to: Andrey Kolobov<akolobov@microsoft.com>.

pick up the changes. A policy that makes these decisions
well solves freshness crawl scheduling problem.
Freshness crawl scheduling has several challenging aspects.
For most sources, the tracker finds out whether they havechanged only when it crawls them. To guess when thechanges happen, and hence should be downloaded, thetracker needs a predictive model whose parameters are initially unknown. Thus, the tracker needs to learn these models and optimize a freshness-related objective when scheduling crawls. For some web pages, however, sitemap pollingand other means can provide trustworthy near-instantaneous
signals that the page has changed in a meaningful way,though not what the change is exactly. But even with theseremote change observations and known change model parameters, freshness crawl scheduling remains highly nontrivial because the tracker cannot react to every individual
predicted or actual change. The tracker’s infrastructure imposes a bandwidth constraint on the average daily numberof crawls, usually limiting it to a fraction of the change event
volume. Last but not least, Google and Bing track many
billions of pages (van den Bosch et al., 2015) with vastlydifferent importance and change frequency characteristics.
The sheer size of this constrained learning and optimization problem makes low-polynomial algorithms strongly
preferable, despite the availability of big-data platforms.
This paper presents a holistic approach to freshness crawlscheduling that handles all of the above aspects in a computationally efficient manner with optimality guarantees
using a type of reinforcement learning (Sutton & Barto,
1998). Different aspects of crawl scheduling have beenstudied extensively before, as described in detail in the Related Work section. Crawl schedule optimization alone,under various objectives and assuming known model parameters, has been the focus of many papers since Coffman
et al. (1998). However, even without remote change sensing
and under the known-model assumption, efficient optimization has so far been possible only for freshness objectives
that induce policies with practically undesirable behaviors
such as crawl-starving many of the sources forever (Azaret al., 2018). Learning change-predictive models has received much attention as well (e.g., (Cho & Garcia-Molina,
2003b)) but purely as a preprocessing step, without regard to
the learning versus schedule optimization tradeoff. No priorwork has studied joint optimization of all facets of freshness
crawl scheduling that we consider here. Specifically, ourStaying up to Date with Online Content Changes Using Reinforcement Learning for Schedulingcontributions are as follows:• We propose a natural freshness optimization objective
based on harmonic numbers, and show how its mathematical properties enable efficient optimal scheduling.
• We derive efficient optimization procedures forthis bandwidth-constrained objective under complete,
mixed, and lacking remote change observability.
• We present a reinforcement learning algorithm that
integrates these approaches with model estimation of
Cho & Garcia-Molina (2003b) and converges to the optimal policy, lifting the known-parameter assumption.
• We introduce an approximate crawl scheduling algorithm that requires learning far fewer parameters, andderive a condition under which its solution is optimal.

2. Problem formalization
In settings we consider, a service we call tracker monitors
a set W of information sources. A source w ∈ W can bea web page, an RSS feed, a data stream, a file, etc, whose
content changes from time to time. To pick up changes
from a source, the tracker needs to crawl it, i.e., download
its content. At any time when source w has changes thatthe tracker hasn’t picked up, the tracker is stale w.r.t. w;
otherwise, it is fresh w.r.t. w. We assume crawl operations
to be near-instantaneous, and the set W of sources to be
fixed. Growing W to improve information completeness(Pandey et al., 2004) is also an important but largely distinct
problem; we do not consider it here.

tracker receives incomplete change observations about them.
However, for other sources, which we denote as W o , thetracker may receive near-instant notification whenever theychange, i.e., get complete remote change observations. E.g.,
for web pages these signals may be available from browser
telemetry or sitemaps. Thus the tracker’s set of sources canbe represented as W = W o ∪ W − and W o ∩ W − = 0.
Bandwidth constraints. Even if the tracker receives complete change observations, it generally cannot afford to doa crawl upon each of them. The tracker’s network infrastructure and considerations of respect to other Internet users
limit its crawl rate – the average number of requests per day– and the total change rate of tracked sources may be muchhigher. We call this limit bandwidth constraint R.
Optimizing freshness. We assume that the tracker operates
in continuous time and starts fresh w.r.t. all tracked sources.
A solution to the freshness crawl scheduling problem is apolicy π – a rule that at every instant t chooses (potentiallystochastically) a source to crawl or decides that none shouldbe crawled. Executing π produces a crawl sequence oftime-source pairs CrSeq = (t1 , w1 ), (t2 , w2 ), . . ., where
we omit the time points for which π does not choose asource to crawl. For a specific source w, we denote thissequence as CrSeqw = (t1 , w), (t2 , w), . . . Similarly, the(Poisson) change process at the sources generates a change
sequence ChSeq = (t01 , w10 ), (t02 , w20 ), . . ., where each t0i is
a change time of source wi0 , and its restriction to source w
is ChSeqw . We denote the joint process governing changes~
at all sources as P (∆).

3. Minimizing harmonic staleness penalty

Discrete page changes. We define a content change at asource to be an alteration at least minimally important to thetracker. In practice, trackers compute a digest of a source’s
content using data extractors, shingles (Broder et al., 1997),
or similarity hashes (Charikar, 2002), and consider content
changed when its digest changes. We assume changes to beinstantaneous and associate change time tc with each.

We view maximizing freshness as minimizing costs the
tracker incurs for the lack thereof, and associate the following policy cost J π with every scheduling policy π, thetime-averaged expected staleness penalty:
" Z
#
1 T X
π
J = limµw C(Nw (t))dt
E
T →∞ CrSeq∼π,
T 0Models of change process and importance. We model
each source w ∈ W ’s changes as a Poisson process withchange rate ∆w . We also associate an importance score µw
with each source, and denote these parameters jointly as µ~.
Importance score µw can be thought of as characterizing
the time-homogeneous Poisson rate at which the page isserved in response to the query stream, although in general
it can be any positive weight measuring the significance ofa page (Azar et al., 2018). While scores µw are defined,
and hence known, by the tracker itself, change rates ∆w
generally need to be learned.

(1)

Change observability. For most sources, the tracker canfind out whether the source has changed only by crawlingit. In this case, even crawling doesn’t tell the tracker how
many times the source has changed since the last crawl. We
denote the set of these sources as W = W − and say that thew∈W~
ChSeq∼P (∆)

Here, T is a planning horizon, Nw (t) is the number ofuncrawled changes source w has accumulated by time t,
and C : Z+ → R+ is a penalty function, to be chosen
later, that assigns a cost to every possible number of uncrawled changes. Note that Nw (t) implicitly depends onthe most recent time w was crawled as well as on change sequence ChSeq, so the expectation is taken both over possible change sequences and possible crawl sequences CrSeq
generatable by π. Minimizing staleness means finding
π ∗ = argmin J π ,

(2)

π∈Π

subject to bandwidth constraints, where Π is a suitably chosen policy class.
Choosing C(n) that is efficient to optimize and induces

Staying up to Date with Online Content Changes Using Reinforcement Learning for Scheduling”well-behaving” policies is of utmost importance. Cho &Garcia-Molina (2003a) and Azar et al. (2018) have considered Equation 1 with C(n) = 1n>0 , i.e., imposing a penalty
if a source had any changes independently of their number,with Π = {CrSeqw ∼ P oisson(ρw ) for all w ∈ W |~ρw },i.e., policies that crawl each source according to a Poissonprocess with a source-specific rate ρw . Under a bandwidth
constraint only, they find the optimal policy in this classvery efficiently, in O(|W | log(|W |)) time, but this solution
assigns ρw = 0 for many sources (Azar et al., 2018; Cho& Garcia-Molina, 2003a). In practice, this may not be acceptable, as it leaves the tracker stale w.r.t. these sources
forever and therefore raises a question: why does the tracker
monitor these sources at all?
In this paper, we propose and analyze the following penalty:
C(n) = H(n) =

n
X
1
i=1

n

if n > 0, and 0 if n = 0(3)

H(n) for n > 0 is known as the n-th harmonic number andhas several desirable properties as staleness penalty:
It is strictly monotonically increasing. Thus, it penalizes the
tracker for every change that happened at a source since theprevious crawl, not just the first one as in (Cho & GarciaMolina, 2003a).
It is discrete-concave, providing diminishing penalties. This
reflects the intuition that while all undownloaded changes
at a source matter, the first one matters most, as it marks thetransition from freshness to staleness.
”Good” policies w.r.t. this objective don’t starve any source:
Proposition 1. Under C(n) = H(n), any policy thatcrawls each source at a fixed Poisson rate ρw and assigns
ρw > 0 to each w with µw , ∆w > 0 is strictly preferable toany such policy that assigns ρw = 0 to any such source.
Proof. See the supplement. This is a direct consequence of
Proposition 2: any policy π with ρw = 0 has J π = ∞. C(n) = H(n) allows for efficiently finding optimal policies under practical policy classes. Indeed, C(n) = H(n)isn’t the only penalty function satisfying the above properties. For instance, C(n) = nd for 0 < d < 1 andC(n) = logd (1 + n) for d > 1 behave similarly. However,
optimizing these alternatives turns out much less efficient.

4. Optimization under known change process
We now derive procedures for optimizing Equation 1 with
C(n) = H(n) (Equation 3) under the bandwidth constraint
for sources with incomplete and complete change observations, assuming that we know the change process parameters~ exactly. In Section 5 we will lift the known-parameters∆~ > 0, because sources that are
assumption. We assume µ~, ∆unimportant or never change don’t need to be crawled.

4.1. Case of incomplete change observations
When the tracker’s only way to find out about changes at asource is crawling it, we consider the class of randomized
memoryless policies that sample crawl times for each source
according to a Poisson process with parameter ρw :Π− = {CrSeqw ∼ P oisson(ρw ) ∀w ∈ W − |~ρ ≥ 0} (4)This policy class reflects the intuition that, since each sourcechanges according to a Poisson process, i.e., roughly periodically, it should also be crawled roughly periodically. In
fact, as Azar et al. (2018) show, any π ∈ Π− can be derandomized into a deterministic policy that is approximately
periodic for each w. Since every π ∈ Π− is fully determined by the corresponding vector ρ~, we
P can easily express
a bandwidth constraint on π ∈ Π− as w∈W − ρw = R.
To optimize over Π− , we first express the cost function from
Equation 1 in terms of Π− ’s policy parameters ρ~ ≥ 0:
Proposition 2. For π ∈ Π− , J π from Eq. 1 is equivalent toXρw
Jπ = −µw ln(5)∆w + ρ w−
w∈W

Proof. See the Supplement. Note that J π = ∞ if ρ = 0 for
any w ∈ W − . The proof proceeds via a series of algebraic
manipulations and relies on properties of Poisson processes,
particularly their memorylessness.
Thus, finding π ∗ ∈ Π− can be formalized as follows:
Problem 1. [Finding π ∗ ∈ Π− ]I NPUT: bandwidth R > 0; positive importance and change~ > 0.
rate vectors µ~, ∆O UTPUT: Crawl rates ρ~ = (ρw )w∈W − maximizing


X
ρw
π
J = −J π =µw ln∆w + ρ ww∈W −subject toXρw = R, ρw ≥ 0 for all w ∈ W − .

(6)

w∈W −

The next result readily identifies the optimal solution to thisproblem:~ > 0, policy π ∗ ∈ Π− parameterProposition 3. For µ~, ∆ized by ρ~∗ > 0 that satisfies√(−∆w + ∆2w + 4µwλ∆w
ρw =, for all w ∈ W −2(7)Pw∈W − ρw = R
is unique, minimizes the harmonic penalty J π in Equation
3, and is therefore optimal in Π− .
Proof. See the Supplement. The main insight is that for~ > 0 the Lagrange multiplier method, which gives
any µ
~, ∆

Staying up to Date with Online Content Changes Using Reinforcement Learning for Schedulingrise to Equation system 7, identifies the only maximizer ofπ
J = −J π (Equation 6) in the region ρ~ > 0, which must
therefore correspond to π ∗ ∈ Π− . Crucially, that solution
always has λ > 0.

Equation system 7 is non-linear, but the r.h.s. of equations
involving λ monotonically decreases in λ > 0, so, e.g.,bisection search (Burden & Faires, 1985) on λ > 0 can findρ~∗ as in Algorithm 1.
Algorithm 1: L AMBDAC RAWL -I NCOML O BS: finding the optimal crawl scheduling policy π ∗ ∈ Π−under incomplete change observations (Problem 1)
Input: R ≥ 0 – bandwidth;~ > 0 – importance and change rates;µ~ > 0, ∆ > 0 – desired precision on λ1 ; Output: ρ~ – vector of crawl rates for each source.
2
3

lower bound λ ←[upper bound λ ←[|W − |2 minw∈W − {∆w } minw∈W − {µw }|W − | maxw∈W − {∆w }R+R2|W − |2 maxw∈W − {∆w } maxw∈W − {µw }|W − | minw∈W − {∆w }R+R2

λ ←[ BisectionSearch(lower bound λ, upper bound λ, )
5 // see, e.g., Burden & Faires (1985)

if p~ > 0 and J π = ∞ if pw = 0 for any w ∈ W o .
Proof. See the Supplement. The key insight is that underany π ∈ Πo , the number of w’s uncrawled changes at time
t is geometrically distributed with parameter pw .
Under any π ∈ Πo , the crawl rate ρw of any source w is
related to its change rate ∆w : every time w changes we
get an observation and crawl w with probability pw . Thus,ρw = pw ∆w . However, since pw is a probability,
P we musthave 0 ≤ pw ≤ 1. Also, bandwidth R >w∈W o ∆w
isn’t sensible, because with complete change observations
the tracker doesn’t benefit from more crawls than there arechanges. Thus, we frame finding π ∗ ∈ Πo as follows:
Problem 2. [Finding π ∗ ∈ Πo ]I NPUT: bandwidth R s.t. 0 < R ≤~ > 0.
and change rate vectors µ~, ∆foreach w ∈ W − do ρw ←[7 Return ρ~q
4µw ∆w−∆w + ∆2w+
λ2w∈W o ; importance

O UTPUT: Crawl probabilities p~ = (pw )w∈W o maximizingXπ
J = −J π =µw ln (pw )
(9)

4

6

P

w∈W o

subject toX

pw ∆w = R, 0 ≤ pw ≤ 1 for all w ∈ W ow∈W o

Proposition
4.
L AMBDAC RAWL -I NCOML O BS
(Algorithm 1) finds an arbitrarily close approximation to Problem 1’s optimal solution in time
upper bound λ−lower bound λO(log2 ()|W − |).


Solving Problem 2 requires non-linear optimization underinequality constraints, which, in general, could take time
exponential in the constraint number. Our main result inthis subsection is that one can find the optimal solution to
Problem 2 in polynomial time in the number of constraints.

Proof. See the Supplement. The key step is showing thatthe solution λ is in [lower bound λ, upper bound λ].
We begin by inspecting solutions to the relaxation of Problem 2 that ignores the inequality constraints:
Proposition 6. The optimal solution p̂~∗ to the relaxation of
Problem 2 that ignores inequality constraints is unique andassigns

4.2. Case of complete change observations
When the tracker receives an observation every time a sourcechanges, the policy class Π− in Equation 4 is clearly suboptimal, because it completely ignores change signals when
deciding when to crawl a source. At the same time, crawling
every source on every change signal
Pis unviable, because
the total change rate of all sources w∈W ∆w can easily
exceed bandwidth R. These extremes suggest a policy classwhose members trigger crawls for only a fraction of theobservations, dictated by a source-specific probability pw :Πo ={for all w ∈ W o , whenever change observation ow
arrives, crawl w with probability pw |0 ≤ p~ ≤ 1}
As with Π− , to find π ∗ ∈ Πo we first express J π from Equation 1 in terms of Πo ’s policy parameters p~ = (pw )w∈W o :Proposition 5. For π ∈ Πo , J π from Eq. 1 is equivalent toX
Jπ = −µw ln (pw )
(8)
w∈W o

p̂∗w =∆w

RµP w

w0 ∈W o µw

for all w ∈ W o

(10)

0

Proof. See the Supplement. The proof applies the methodof Lagrange multipliers to this relaxation.
Equation 10 indicates that the relaxation’s solution never has
pw ≤ 0, but it may indeed violate the constraints pw ≤ 1.
The main difficulty of inequality-constrained optimization
is exactly in determining the subset of inequality constraints
that are active under the optimal solution, i.e., in our case,finding all sources w for which the optimal p~∗ has p∗w = 1.
Our algorithm L AMBDAC RAWL -C OMPL O BS (Algorithm2) finds them iteratively. In each iteration (lines 4-14), we
consider only the sources that haven’t yet been proved toactivate their pw ≤ 1 constraint under p~∗ (lines 3,12). For
them, we solve a relaxation of Problem 2 that ignores theseStaying up to Date with Online Content Changes Using Reinforcement Learning for Schedulingconstraints, using Proposition 6 (lines 5-6), and check if
this solution p̂~∗ happens to violate any constraints (line 9).
Our key insight is that any source w that activates or violates its constraint under Proposition 6’s solution, i.e., hasp̂∗w ≥ 1, must necessarily have p∗w = 1. As we prove in
the Supplement, this follows from the strict concavity ofπ
J and the convexity of the optimization region given by
the constraints. Whenever we can prove source w to activate its constraint in this way, we set p∗w = 1, adjust theoverall bandwidth constraint for the remaining sources to
Rrem = R −p∗w ∆w = R −∆w , and remove w from further
consideration (lines 10-12). Eventually, our problem gets
reduced to a (possibly empty) set of sources for which Proposition 6’s solution doesn’t violate any constraints under theremaining bandwidth (lines 15-16). Since Proposition 6’ssolution is optimal in this case, the overall algorithm is
optimal as well.
Algorithm 2: L AMBDAC RAWL -C OMPL O BS: finding
the optimal crawl scheduling policy π ∗ ∈ Πo undercomplete change observations (Problem 2)

4.3. Crawl scheduling under mixed observability
In practice, trackers have to simultaneously handle sources
W − for which complete change observations are available
and sources W o for which they aren’t at the same time,
under a common bandwidth constraint R. How should we
optimize scheduling mixed-observability scenarios?
Consider the policy class that combines Π− and Πo :

−

ρ},
{CrSeqw ∼ P oisson(ρw ) for all w ∈ W |~o
Π = {for all w ∈ W , whenever change observationo arrives, crawl w with probability p |~
w
w p}
(11)
For π ∈ Π , Propositions 2 and 5 imply that J π from
Equation 1 is equivalent to


X
X
ρw
π
µw ln (pw )
J =−
µw ln
−
∆w + ρ w
w∈W o
w∈W −
(12)
Optimization over π ∈ Π can be stated as follows:
Problem 3. [Finding π ∗ ∈ Π ]1

I NPUT: bandwidth R > 0; importance and change rate
~ > 0.
vectors µ~, ∆7

O UTPUT: Crawl rates ρ~ = (ρw )w∈W − and crawl probabilities p~ = (pw )w∈W o maximizing
 X

X
ρw
π
π
J = −J =+µw lnµw ln (pw )∆w + ρ w
w∈W o
w∈W −
(13)
subject toXXρw +pw ∆w = R,

L AMBDAC RAWL -C OMPL O BS:~ – importance and change rate vectors
Input: µ~, ∆P
2
R s.t. 0 ≤ R ≤ w∈W ∆w – bandwidth;
Output: p~∗ – vector specifying optimal per-page crawl
probabilities upon receiving a change observation.
o
3 Wrem ←[ W// remaining sources to considero
4 while Wrem 6= ∅ doo5foreach w ∈ Wremdoo6p̂∗w ←[ ∆w P 0Rµwo µ 0 for all w ∈ Wremw ∈Wremw

13

V iolationDetected ←[ F alseoforeach w ∈ Wremdo∗
if p̂w ≥ 1 thenp∗w ←[ 1R ←[ R − ∆w // reduce remaining bandwidthooWrem←[ Wrem\ {w} // ignore w onwards
V iolationDetected = T rue

14

if V iolationDetected == F alse then break

8
9
10
11
12

16

o
foreach w ∈ Wremdop∗w ←[ p̂∗w

17

Return p~∗ = (p∗w )w∈W o

15

Proposition 7. L AMBDAC RAWL -C OMPL O BS returns the
optimal solution to Problem 2 and runs in time O(|W o |2 ).

Proof. See the Supplement. The proof formalizes the aboveπ
intuitions and critically relies on the concavity of J . 
In practice, the running time bound of O(|W o |2 ) is veryloose. Each iteration usually discovers several active constraints, and many sources don’t activate their constraint
under p~∗ , so the computation time is close to linear in |W o |.

w∈W −

w∈W o

ρw > 0 for all w ∈ W − , 0 < pw ≤ 1 for all w ∈ W o
The optimization objective (Equation 13) is strictly concave as a sum of concave functions over the region described by the constraints, and therefore has a unique maximizer. To find it efficiently, we observe that solving Problem 3 amounts to deciding how to split the global bandwidth constraint R into an allotment Ro for sources withcomplete change observations and R− = R − Ro for the
rest. For any candidate split, L AMBDAC RAWL -C OMPL O BS
and L AMBDAC RAWL -I NCOML O BS give us the rewardmaximizing policy parameters p~∗ (Ro ) and ρ~∗ (R− ), respectively, and Equation 13 then tells us the overall value∗
J (Ro , R− ) of that split. We
Palso know that for the opti∗
mal split, Ro ∈ [0, min{R, w∈Wo ∆w }], as described in
Problem 2 and discussion immediately before it. Thus, we
can find Problem 3’s maximizer to any desired precision using a method such as Golden-section search (Kiefer, 1953)
on Ro . L AMBDAC RAWL (Algorithm 3) implements this∗∗idea, where S PLIT-E VAL -J (line 7) evaluates J (Ro , R− )and OptMaxSearch denotes an optimal search method.
Proposition 8. L AMBDAC RAWL (Algorithm 3) finds anStaying up to Date with Online Content Changes Using Reinforcement Learning for Scheduling

arbtirarily close approximation to Problem 3’s optimal solution using O(log( R )) calls to L AMBDAC RAWL I NCOML O BS and L AMBDAC RAWL -C OMPL O BS.
Proof. This follows directly from the optimality of
L AMBDAC RAWL -I NCOML O BS and L AMBDAC RAWL C OMPL O BS (Propositions 3 and 7), as well as of
OptMaxSearch such as Golden section, which makes
O(log( R )) iterations.

Algorithm 3: L AMBDAC RAWL: finding optimal
mixed-observability policy π ∗ ∈ Π (Problem 3)
Input: R > 0 – bandwidth;~ > 0 – importance and change rates;µ~ > 0, ∆no-obs ,  > 0 – desired precisions
Output: ρ~∗ , p~∗ – crawl rates and probabilities for sources
without and with complete change observations.
o
1 Rmin ←[ 0Po
2 Rmax ←[ min{R,w∈Wo ∆w }
∗
∗
∗
o
o
3 ρ
~ ,p
~ ←[ OptMaxSearch(Split-Eval-J , Rmin
, Rmax, )
4 // E.g., Golden section search (Kiefer, 1953)
5 Return ρ~∗ , p~∗
6∗

S PLIT-E VAL -J :Input: Ro – bandwidth for sources with complete change~ no-obs
observations, R, µ
~ , ∆,∗
Output: J (Equation 13) for the given split
8 ρ~ ←[ L AMBDAC RAWL -I NCOML O BS(R −~ W − , no-obs )Ro , µ~W−, ∆o~ Wo)
9 p~ ←[ L AMBDAC RAWL -C~Wo, ∆
 OMPL OBS(RP, µPρw
10 Return+ w∈W o µw ln (pw )w∈W − µw ln ∆w +ρw
7

5. Reinforcement learning for scheduling
Although staleness minimization is efficient under the
known-model assumption, in reality change rates are usually unavailable and vary with time, requiring constant relearning. As it turns out, their estimation can be done with
only minor changes to L AMBDAC RAWL that turn it into a
type of model-based reinforcement learning (RL) algorithm.
Suppose for a given source w the tracker has observed a sequence of binary change indicator variables z1 , z2 , . . . , zU ,where t0 , . . . , tU are times when the observations arrived,
and, for 1 ≤ j ≤ U , zj = 1 iff the source changed compared to time tj−1 at least once. Consider two cases:
Incomplete change observations for w. Crawling thesource is the only way for the tracker to find out about any
changes: after each crawl at times t1 , . . . , tU , the tracker
checks for changes compared to w’s previous crawl andrecords ztj = 1 or ztj = 0 accordingly. There may be morethan one change since the previous crawl, but the tracker
cannot determine this. Denoting atj = tj − tj−1 , j ≥ 1,
ˆ that solves
Cho & Garcia-Molina (2003b) show that ∆X
j:ztj =1 e

atj
atj ∆

−1

−

X

atj = 0,(14)

j:ztj =0

is a maximum-likelihood estimator of ∆ for the given source.
The l.h.s. of the equation is monotonically decreasing in ∆,ˆ can be efficiently found numerically. This estimatorso ∆is consistent under mild conditions (Cho & Garcia-Molina,
2003b), e.g., if the sequence {atj }∞j=1 doesn’t converge to0, i.e., if the observations are spaced apart.
Complete change observations for w. In this case, forall j, ztj = 1; a change observation arrives only when
there is a change and indicates exactly one change. This is astandard setting for estimating Poisson process intensity, andˆ is simply the time-averaged
a consistent MLE estimator ∆number of observed changes (Taylor & Karlin, 1998):
U +1
∆=
,
(15)
tU
L AMBDA L EARNA ND C RAWL, a model-based RL version of
L AMBDAC RAWL that uses these estimators to learn model
parameters simultaneously with scheduling is presented in
Algorithm 4. It operates in epochs of length Tepoch timeunits each (lines 3-13). At the start of each epoch n, it~ˆcalls L AMBDAC RAWL (Algorithm 3) on the available ∆n−1∗∗change rate estimates to produce a policy (~ρn , p~n ) optimal
with respect to them (line 4). Executing this policy during
the current epoch, for the time period of Tepoch , and recording the observations extends the observation history (lines 78). (Note though that for sources w ∈ W o , the observations
don’t depend on the policy.) It then re-estimates change
rates using a suffix of the augmented observation history(lines 10-13). Under mild assumptions, L AMBDA L EAR NA ND C RAWL converges to the optimal policy:
Proposition 9. L AMBDA L EARNA ND C RAWL (Algorithm 4) converges in probability to the opti~ i.e.,
mal policy under the true change rates ∆,∗ ∗~ islimNepochs →∞ (~ρNepochs , p~Nepochs ) = (~ρ , p~ ), if ∆stationary and S(n), the length of the history’s training
suffix, satisfies S(Nepoch ) = length(obs hist).
Proof. See the Supplement. It follows from the consistency
and positivity of the change rate estimates, as well as L AMB DAC RAWL’s optimalityUsing L AMBDA L EARNA ND C RAWL in practice requires
attention to several aspects:~ Source change rates may vary with time,
Stationarity of ∆.
~ should typiso the length of history suffix for estimating ∆cally be shorter than the entire available history.
~ˆSingularities of ∆estimators. Given a limited observation
ˆ = ∞ ifhistory, the MLE in Equation 14 can produce ∆all crawls detected a change (the r.h.s. is 0). Similarly,ˆ w = 0 if no observations about
Equation 15 can produce ∆Staying up to Date with Online Content Changes Using Reinforcement Learning for Scheduling

Algorithm 4: L AMBDA L EARNA ND C RAWL: finding
optimal crawl scheduling policy π ∗ ∈ Π (Problem 3)
under initially unknown change model
Input: R > 0 – bandwidth;~ˆµ~ > 0, ∆0 > 0 – importance and initial change rate
guessesno-obs ,  > 0 – desired precisions
Tepoch > 0 – duration of an epoch
Nepochs > 0 – number of epochs
S(n) – for each epoch n, observation history~ in that epoch
suffix length for learning ∆// obs hist[S(n)] is S(n)-length observation history suffix
obs hist ←[ ()3 foreach 1 ≤ n ≤ Nepochs do~ˆno-obs4ρ~∗n , p~∗n ←[ L AMBDAC RAWL(R, µ
~, ∆
, )
n−1 , ~// Znew holds observations for all sources from start to
5
6// end of epoch n. Execute policy (~ρ∗n , p~∗n ) to get it∗~ new ←[ ExecuteAndObserve(~
7Z
ρn , p~∗n , Tepoch )~ new )
8
Append(obs hist, Z~
9// Learn new ∆ estimates using Eqs. 14 and 15
10
foreach w ∈ W − doaj
0.5
ˆ nw ←[ Solve( P11∆+ e0.5∆
−
aj ∆
−1
−1
j:zjw =1 ePaj − 0.5 = 0, obs hist[S(n)])
12

j:zjw =012
13

foreach w ∈ W o do
ˆ nw ←[ Solve( US(n) +0.5 , obs hist[S(n)])∆S(n)+0.5

w arrived during a given period. To avoid them without
affecting estimation consistency, we use smoothing to add
imaginary observation intervals of length 0.5 to Equation 14
and imaginary 0.5 observation to Equation 15 (lines 11,13).
The sheer number of parameters L AMBDA L EARNA ND C RAWL needs to learn raises a question: can we employ anapproximation with fewer parameters to learn? The following result suggests one such approximation:
Proposition 10. Suppose the tracker’s set of sources W − isµwsuch that for some constant c > 0, ∆= c for all w ∈ W − .
w
Then minimizing harmonic penalty under incomplete change−
observations (Problem 1) has ρ∗w = P µ0 w R− µ 0 .
w ∈Ww

Proof. See the Supplement. The proof proceeds by plugging in ∆w = 1c µw into Equation system 7.
In essence, the proposition states that if the importanceto-change-rate ratio is constant across all sources, theneach source’s crawl rate is independent of its change rate,and even the ratio constant itself. This greatly simplifies crawl scheduling, because for sources w ∈ W − ,we don’t need to learn any change rates, provided thatthe constant-ratio assumption holds at least approximately.
Moreover, if L AMBDAC RAWL -I NCOML O BS (Algorithm 1)

is replaced by assigning ρ∗w , w ∈ W − as in Proposition 10,
an O(|W − |) operation, which improves the computational
efficiency of L AMBDAC RAWL and L AMBDA L EARNA ND C RAWL in its own right. Our evaluation (Section 7) explores
the quality of this approximation empirically.

6. Related work
Most literature related to our work comes from research on
polling-based cache/database maintenance and web crawling. The term ”Web caching,” in spite of its seeming relevance, refers to HTTP caches, a different cache type found inbrowsers, proxy servers, and content distribution networks(CDNs). They refresh their content when prompted by aclient request or when a source pushes fresh content (as in
the case of CDNs). In contrast, this paper focuses on settings
where neither of these is feasible. A major example of suchtrackers are search engines and knowledge graphs. Olston& Najork (2010) provides an extensive survey of crawling
research; we review its most relevant aspects below.
Maintaining fresh cache via polling. This problem has
been studied under a variety of settings and assumptions.
Besides monitoring online information sources, mathematically similar settings have been researched in the context ofscheduling maintenance service to machines (Anily et al.,
1998; Bar-Noy et al., 1998). In the context of a search engine
index, the closest works are Cho & Garcia-Molina (2003a),
Wolf et al. (2002), Pandey & Olston (2005), and Azar et al.
(2018). Like Cho & Garcia-Molina (2003a) and Azar et al.
(2018), we use the method of Lagrange multipliers as part of
optimization , and adopt the Poisson change model of Cho &Garcia-Molina (2003a) and many works since. Our contributions differ from prior art in several ways: (1) optimization
objectives and properties of resulting policies (see the next
subsection); (2) crawl scheduling for sources with completechange observations, both separately from and jointly withthe commonly studied setting of sources whose changes aredetectable only at crawl time; (3) learning model parameters
in a principled way during crawling.
Optimization objectives. Staleness penalty minimization
we proposed can be viewed as a generalization of the binary freshness objective studied by Cho & Garcia-Molina(2003a) and Azar et al. (2018) whereby the cache incurs afixed penalty if and only if the source has changed in any
way at least once since it was last crawled. As Azar et al.
(2018) show, the optimal policy for this objective has thepractically undesirable property of starving many sources,leaving the tracker’s copies to diverge from the original. In
contrast, our objective guarantees that this doesn’t happen.
Other related technical objectives include minimizing age(Cho & Garcia-Molina, 2000), a.k.a. obsolescence (Gal
& Eckstein, 2001). On the other hand, Pandey & Olston(2005) focus on a cache ”quality” measure that depends onuser behavior, and Wolf et al. (2002) study another usercentric objective, embarrassment minimization, whereby
pages likely to be most clicked get crawled more frequently.

Staying up to Date with Online Content Changes Using Reinforcement Learning for Scheduling

LCA

0.5
0

1,000

LC

LCA

IC

UC

CC

BC

∞

500
0

0

10

400
Policy cost J π

1,500

LC
1

Policy cost J π

Running time (s)

·10

4

300
200
LLC
LLCA
IC

100

LC (known params)
LCA (known params)

0

20

0

Number of sources (URLs), ×1, 000, 000

2

4

6

Number of epochs

Figure 1. Solution time of L AMBDAC RAWL Figure 2. Average policy cost per page of Figure 3. Convergence of L AMBDA L EAR and L AMBDAC RAWL A PPROX as a function L AMBDAC RAWL (LC) and other algorithms NA ND C RAWL (LLC) and L AMBDA L EAR of source set size |W |. Both scale linearly on the 20M-URL dataset. Lower bars in- NA ND C RAWL A PPROX (LLCA) for a subin |W | in practice, but L AMBDAC RAWL A P - dicate better policies. The optimal L AMB - sample of the dataset with |W | = 100000. 1
DAC RAWL incurs 31% lower cost than the
PROX shows significant time savings. See
epoch = 14 days. Dashed lines indicate their
Figures 2 and 3 for policy cost comparisons. next-best prior algorithm ImportanceCrawl asymptotic policy cost (under known change(IC). BinaryCrawl (Azar et al., 2018) has rates). ImportanceCrawl (IC) is shown for
J π = ∞ due to crawl-starving many URLs. comparison as the best-of-the-rest approach.

User-centric measures are desirable in principle, but involve
many hard-to-verify assumptions about the user population
and become ambiguous for trackers, such as caches, supporting several distinct services, e.g., a knowledge graph, image
search, and document search at the same time. Coupled withcomputational tractability, this makes technical objectives
like freshness preferable in many practical systems.
Acquiring model parameters. Like ours, many previous
works rely on page importance and change models. Importance can be defined and quickly determined from information readily available to search engines, e.g., page
relevance to queries (Wolf et al., 2002), query-independent
popularity such as PageRank (Page et al., 1998), and otherfactors (Pandey & Olston, 2005)). Learning page change
rates is more delicate. Change rate estimators we use are dueto (Cho & Garcia-Molina, 2003b); our contribution in thisregard is integrating model estimation with crawl schedulingwhile providing theoretical guarantees, as well as identifying conditions when estimation can be side-stepped using anapproximation. While many prior works adopt the homogeneous Poisson change process, its non-homogeneous variant(Gal & Eckstein, 2001) as well as a quasi-deterministicchange model (Wolf et al., 2002) have also been considered.
As an alternative to estimating source change models individually, Cho & Ntoulas (2002) propose inferring them indirectly using page similarities. Predictions of page change
kind and significance, as in (Radinsky & Bennett, 2013),
are also helpful for a crawl scheduler in prioritizing crawls.

7. Empirical evaluation
In the experiments, we explore L AMBDAC RAWL’s (labelled
LC in the figures) scalability and solution quality relative
to L AMBDAC RAWL A PPROX (LCA), a L AMBDAC RAWL
version that uses the approximation from Proposition 10
instead of L AMBDAC RAWL -I NCOML O BS for w ∈ W − ,ImportanceCrawl (IC) and ChangeRateCrawl (CC) (Cho& Garcia-Molina, 2003a), BinaryCrawl (BC) (Azar et al.,2018), and UniformCrawl (UC) — please see the Supplement, Section 10 for the description of these algorithms
from prior literature. We also assess the convergence speedof L AMBDA L EARNA ND C RAWL.

For the dataset, we crawled 20, 151, 962 URLs daily over 14
weeks to estimate their crawl rates reliably using Equations
14 and 15. These URLs are data sources for the knowledge
graph of a major virtual assistant. Approximately 13%of them had complete change observations from reliable
sitemaps. We set their importance scores µw to values
defined by the production crawler based on PageRank andpopularity. The bandwidth constraint was set to 20% of thenumber of pages in the corresponding experiment.
The experiments used a Python implementation of all algorithms from this paper, All algorithms were implemented
in Python (the code will be open-sourced) and run on a
Windows 10 laptop with 16GB RAM and an Intel quad-core
2.11GHz i7-8650U CPU.
The results are shown in Figures 1, 2, and 3, with additional
details in Supplement, Section 10. Note that, as described
there and per Proposition 10, ImportanceCrawl is a special
case of L AMBDAC RAWL and L AMBDAC RAWL A PPROX
without the L AMBDAC RAWL -C OMPL O BS component andµwµw
assuming uniform ∆. Thus, as the ∆distribution acrossw
w
most of the dataset happens to be nearly uniform (Figure 4
in Supplement, Section 10), our theory explains why ImportanceCrawl does relatively well on this data.

8. Conclusion
We have introduced a new objective and a suite of highly
efficient algorithms for it to address the freshness crawlscheduling problem faced by many services from search engines to databases. In particular, we have presented L AMB DA L EARNA ND C RAWL, which integrates model parameter
learning with scheduling optimization. To give convergence
speed guarantees for this kind of approaches in the future,
we intend to look at multi-armed bandit (MAB) models
similar to Immorlica & Kleinberg (2018). Their current
fundamental distinction from our setting is the reward mechanism: a MAB yields a reward only when an arm is pulled,
not continuously as in freshness optimization. Nonetheless,we believe that a new bandit model will provide practicallyand theoretically important insights into freshness crawlscheduling.

Staying up to Date with Online Content Changes Using Reinforcement Learning for Scheduling

References
Anily, S., Glass, C., and Hassin, R. The scheduling ofmaintenance service. Discrete Applied Mathematics, pp.
27–42, 1998.
Azar, Y., Horvitz, E., Lubetzky, E., Peres, Y., and Shahaf, D.
Tractable near-optimal policies for crawling. Proceedingsof the National Academy of Sciences (PNAS), 2018.
Baeza-Yates, R. A. and Ribeiro-Neto, B. Modern Information Retrieval. Addison-Wesley Longman Publishing Co.,
Inc., Boston, MA, USA, 1999.

Kolobov, A., Lubetzky, E., Peres, Y., and Horvitz, E. Optimal freshness crawl under politeness constraints. In
SIGIR, 2019.
Olston, C. and Najork, M. Web crawling. Foundations andTrends in Information Retrieval, 3(1):175–246, 2010.
Page, L., Brin, S., Motwani, R., and Winograd, T. The
pagerank citation ranking: Bringing order to the web.
Technical report, MA, USA, 1998.
Pandey, S. and Olston, C. User-centric web crawling. In
WWW, 2005.

Bar-Noy, A., Bhatia, R., Naor, J., and Schieber, B. Minimizing service and operation costs of periodic scheduling. In
SODA, pp. 11–20, 1998.

Pandey, S., Ramamritham, K., and Chakrabarti, S. Monitoring the dynamic web to respond to continuous queries.
2003.

Broder, A., Glassman, S., Manasse, M., and Zweig, G.
Syntactic clustering of the web. In WWW, pp. 1157–1166,
1997.

Pandey, S., Dhamdhere, K., and Olston, C. WIC: A
general-purpose algorithm for monitoring web information sources. 2004.

Burden, R. L. and Faires, J. D. Numerical Analysis. PWS
Publishers, 3rd edition, 1985.

Radinsky, K. and Bennett, P. Predicting content change on
the web. In WSDM, 2013.

Charikar, M. Similarity estimation techniques from rounding algorithms. In STOC, pp. 380–388, 2002.

Sutton, R. and Barto, A. G. Introduction to Reinforcement
Learning. MIT Press, 1st edition, 1998.

Cho, J. and Garcia-Molina, H. Synchronizing a databaseto improve freshness. In ACM SIGMOD International
Conference on Management of Data, 2000.

Taylor, H. and Karlin, S. An Introduction To Stochastic
Modeling. Academic Press, 3rd edition, 1998.

Cho, J. and Garcia-Molina, H. Effective page refresh policies for web crawlers. ACM Transactions on Database
Systems, 28(4):390–426, 2003a.
Cho, J. and Garcia-Molina, H. Estimating frequency ofchange. ACM Transactions on Internet Technology, 3(3):256–290, 2003b.
Cho, J. and Ntoulas, A. Effective change detection using
sampling. In VLDB, 2002.
Coffman, E. G., Liu, Z., and Weber, R. R. Optimal robot
scheduling for web search engines. Journal of Scheduling,
1(1), 1998.
Gal, A. and Eckstein, J. Managing periodically updated data
in relational databases. Journal of ACM, 48:1141–1183,
2001.
Hixon, B., Clark, P., and Hajishirzi, H. Learning knowledge
graphs for question answering through conversational
dialog. 2015.
Immorlica, N. and Kleinberg, R. Recharging bandits. In
FOCS, 2018.
Kiefer, J. Sequential minimax search for a maximum. Proceedings of the American Mathematical Society, 4(3):502–506, 1953.

van den Bosch, A., Bogers, T., and de Kunder, M. A longitudinal analysis of search engine index size. 2015.
Wolf, J. L., Squillante, M. S., Yu, P. S., Sethuraman, J., andOzsen, L. Optimal crawling strategies for web searchengines. In WWW, 2002.

Staying up to Date with Online Content Changes Using Reinforcement Learning for Scheduling

SUPPLEMENT

9. Proofs
P ROOF OF P ROPOSITION 1. This is a direct consequence of Proposition 2, which implies that any policy π with ρw = 0
for any source w with µw , ∆w > 0 has J π = ∞, whereas any π with rhow > 0 for every µw , ∆w > 0 has J π = ∞ .

P ROOF OF P ROPOSITION 2.
First we rearrange Equation 1 as follows, dropping the distributions under the expectation and using W instead of W −throughout the proof to make the notation less cumbersome:"J π = lim

T →∞E

CrSeq∼π,~
ChSeq∼P (∆)

1= lim
T →∞ T

Z T
0

!
X

#

µw C(Nw (t)) dt

w∈W

!

Z T
0

1
T

X

µw E [C(Nw (t))] dtw∈WThen we use the definition of expectation, chain rule of probabilities, and variable tprev to denote the time when source w
was last crawled before time t (although tprev is specific to each source w, for clarity of notation we make this implicit):

1
J = limT →∞ T

Z T

1
= lim
T →∞ T

Z T

1
= lim
T →∞ T

Z T

π

!
X

0

µw E[C(Nw (t))] dt

w∈W

X

0

0

µw

∞ 
X

w∈W

m=0

X

∞ 
X

w∈W

µw

!
C(m) · P[Nw (t) = m]
dt
Z t
C(m)

P[Nw (t) = m | t − tprev = T 0 ] P[t − tprev = T 0 ]dT 0

!
dt

0

m=0

Now using the fact that our policy is a set of Poisson processes with parameters ρw and page changes are governed byanother set of Poisson processes with parameters ∆w , we can plug in appropriate expressions for the probabilities:

1
J = limT →∞ T

Z T

1

Z T

π

= lim

T →∞ T

0

0

∞
X

!
!!

0
(T 0 ∆w )m e−T ∆w−ρw T 0
0
µw
C(m)
ρe
dT
dt
m!
0
m=0
w∈W
!
Z t
∞ 
X
X
0
C(m)ρw ∆m
wµw
dt
T 0m e−(ρw +∆w )T dT 0
m!
0
m=0
X

Z t

w∈W

We do a variable substitution u = (ρw + ∆w )T 0 , so T 0 = ∆wu+ρw and dT 0 = ∆wdu
+ρw :

Staying up to Date with Online Content Changes Using Reinforcement Learning for Scheduling1
J π = lim
T →∞ T

Z T

1

Z T

= lim

0

T →∞ T

0

Z 
∞ 
X
C(m)ρw ∆m t

m
!
u
du
w
µw
e−u
dt
m!
∆
+
ρ
∆w + ρ w
w
w
0
m=0
w∈W


m Z t
!
∞ 
X
X
C(m)
ρw
∆w
m −u
µw
u e dudtm!
∆ w + ρw
∆w + ρ w
0
m=0
X

w∈W

Rt
Consider F (m, t) = 0 um e−u du. By definition of gamma functions, F (m, t) = Γ(m+1)−Γ(m+1, t) = m!−Γ(m+1, t).
Recalling that C(m) = H(m) for m > 0 and C(0) = 0 (Equation 3), we get


∞ 
X
H(m)


m
!
ρw
∆w
µw
(m! − Γ(m + 1, t))dtm!
∆w + ρw∆w + ρ w
0
m=1
w∈W

Z T "Xm  X

m
# !
∞ 
∞ 
1 X
ρw
∆w
∆w
H(m)
= lim
µw
H(m)
−
Γ(m + 1, t) dt
T →∞ T∆w + ρ w∆w + ρ wm!
∆w + ρ w
0
m=1
m=1

1
J = limT →∞ T
π

Z T

X

w∈W

m 

R T P∞ ∆w
dt,
Now consider for each w ∈ W functions G(T ) =H(m)m=1∆w +ρw0
R T P∞  H(m)  ∆w m
Γ(m + 1, t) dt, and limT →∞ T1 (G(T ) − R(T )) so thatm=1
m!
∆w +ρw
0
π

J =

X 
w∈W


µw

ρw
∆w + ρ w



1(G(T ) − R(T ))lim
T →∞ T

R(t)

=


(16)

Thus, if limT →∞ T1 (G(T ) − R(T )) exists, is finite, and we can compute it, we can compute J π as well. Focusing on G(T )P∞ln( ρw ))and recalling that m=1 H(m)xm = − ln(1−x)
for |x| < 1, we see that G(T ) = − ∆ρww+ρw T , so limT →∞ G(T
=
1−x
T
−

w
ln( ∆wρ+ρ
)w
ρw∆w +ρw∆w +ρw

exists. Focusing on R(T ), we see that since m! < Γ(m + 1, t) for any t > 0 and since R(T ) is an integral)of a non-negative function, we have 0 ≤ R(T ) ≤ G(T ) < ∞, so limT →∞ R(Texists as well. Therefore, we can write
T
G(T
)
R(T
)
1
limT →∞ T (G(T ) − R(T )) = limT →∞ T − limT →∞ T .
)R(T )We already know limT →∞ G(TT . To evaluate limT →∞ T , we upper-bound R(T ). Again using the fact that it is an
integral of a non-negative function, we have

Z T X
∞ 


m

H(m)
∆w
R(T ) =
Γ(m + 1, t) dt
m!
∆ w + ρw
0 m=1

m

Z ∞X
∞ 
H(m)
∆w
<
Γ(m + 1, t) dt
m!
∆w + ρ w
0
m=1
m Z ∞

∞ 
X
H(m)
∆w
=
Γ(m + 1, t)dtm!
∆w + ρ w
0
m=1




∞
m
X H(m)∆w=
Γ(m + 2)m!
∆w + ρ w
m=1


m 
∞
X
∆w
=
(m + 1)H(m)∆w + ρ w
m=1
We have used the fact thatR∞0Γ(m + 1, t)dt = Γ(m + 2) = (m + 1)!. The seriesP∞

m=1 (m + 1)H(m)xmconverges forStaying up to Date with Online Content Changes Using Reinforcement Learning for Scheduling)≤ limT →∞ TL = 0 and limT →∞ T1 (G(T )−R(T )) = −|x| < 1 to some limit L > 0, so we have limT →∞ R(TT
Plugging this back into Equation 9, we get

Jπ = −

X


µw ln

w∈W

ρw
∆w + ρ ww
ln( ∆wρ+ρ
)w
ρw∆w +ρw.



P ROOF OF P ROPOSITION 3. The high-level idea is to apply the method of Lagrange multipliers to Problem 1’s
relaxation without inequality constraints ρ~ ≥ 0 and show that (a) only one local maximum of this relaxation is within theregion given by ρ
~ ≥ 0 – the one satisfying Equation system 7 – and (b) solutions that touch the boundary of this region, i.e.,
have ρw = 0 for any w ∈ W − , are suboptimal. In fact, part (b) follows immediately from Proposition 1, so we only need tosolve the relaxation and show part (a).


P
π
ρw
To apply the method of Lagrange multipliers to the relaxation, we set f (~ρ) = J =andw∈W − µw ln ∆w +ρw
Pg(~ρ) = w∈W − ρw − R. We need to solve(∇f (~ρ) = λ∇g(~ρ)g(~ρ) = 0.
∂g
∂f
µw ∆w
∆w
w
For any w ∈ W − , we have ∂ρ= 1 and ∂ρ= µw ∆wρ+ρ
(∆w +ρw )2 = ∆w ρw +ρ2w , so the above system of equations turns
w
w
w
into

(

µw ∆w
∆w ρw +ρ2w = λ,Pw∈W − ρw = R

for all w ∈ W −and therefore(

λρ2w + λ∆w ρw − µw ∆w = 0, for all w ∈ W −Pw∈W − ρw = R

Solving each quadratic equation separately, we get
(

ρw =
P

−∆w ±

√

∆2w + 4µwλ∆w,
2

for all w ∈ W −w∈W − ρw = R

This gives all potential solutions to the relaxation of Problem 1. Now consider~ ≥ 0 omitted so√ the inequality constraints ρ−∆ −∆2 + 4µw ∆w

w
w
λfar. Observe that any real solution to the above system that has ρw =for any w ∈ W − implies ρw < 02for µw , ∆w > 0, which violates these constraints. Therefore, any solution to Problem 1 itself must satisfy

(

√

ρw =
P

−∆w +

∆2w + 4µwλ∆w,
2

for all w ∈ W −w∈W − ρw = R

and have λ ≥ 0 (otherwise ρ~ < 0, again violating the inequality constraints). Although
Pthe first group of equations are
non-linear, note that each ρwP(λ) is strictly monotone decreasing in λ for λ ≥ 0, so w∈W − ρw is strictly monotone
decreasing too implying that w∈W − ρw (λ) = R has a unique solution in λ, and therefore there is a unique ρ~ satisfying
the above system of equations. Thus, this ρ~ is the solution to Problem 1 and therefore corresponds to π ∗ ∈ Π− .
Staying up to Date with Online Content Changes Using Reinforcement Learning for Scheduling

P ROOF OF P ROPOSITION 4
We start by combining Equation system 7,√(−∆w + ∆2w + 4µwλ∆w, for all w ∈ W −ρw =2Pw∈W − ρw = R,

(17)

into one equation:
X −∆w +q

∆2w + 4µwλ∆w
2

w∈W −

=R

Bisection search is guaranteed to converge to some solution λ of this equation as long as we initialize the search withlower bound λ, upper bound λ s.t. λ ∈ [lower bound λ, upper bound λ]. However, all λ− ≤ 0 that solve Equation
system 7 correspond to solutions that have ρ~ < 0. At the same time, from the proof of Proposition 3 we know that
there is exactly one λ+ > 0 that solves Equation system 7, and it corresponds to the (unique) the optimal solutionρ~∗ of Problem 1. We want bisection search to find only this λ+ > 0, so we want lower bound λ, upper bound λ s.t.
λ+ ∈ [lower bound λ, upper bound λ] and lower bound λ, upper bound λ > 0.
To find these bounds, we observe that the l.h.s. of the above equation is monotonically decreasing in λ for λ > 0, so if wefind any λl > 0 that guaranteesr∆2w +4µw ∆w
2R≥ ∆w +
for all w ∈ W − ,λl|W |then we have
X −∆w +w∈W −q

∆2w + 4µwλl∆w
2≥R

and hence λl ≤ λ+ . To find such λl , we perform a series of algebraic manipulations:r

4µw ∆w
2R≥ ∆w +
for all w ∈ W − , λl > 0
λl
|W |

2
4µw ∆w
2R
2⇐⇒∆w +≥ ∆w +
for all w ∈ W − , λl > 0λl|W − |2
4µw ∆w
4∆w R
R
⇐⇒
≥
+
4
for all w ∈ W − , λl > 0λl|W − ||W − ||W − |2 µw ∆w⇐⇒λl ≤
for all w ∈ W − , λl > 0|W − |∆w R + R2
|W − |2 minw∈W − {µw } minw∈W − {∆w }⇐=λl ≤, λl > 0|W − | maxw∈W − {∆w }R + R2
∆2w +Since the r.h.s. of this inequality is always positive, we set lower bound λ =|W − |2 minw∈W − {µw } minw∈W − {∆w }.
|W − | maxw∈W − {∆w }R+R2

AnStaying up to Date with Online Content Changes Using Reinforcement Learning for Scheduling

analogous chain of reasoning shows that we can choose upper bound λ =|W − |2 maxw∈W − {∆w } maxw∈W − {µw }.
|W − | minw∈W − {∆w }R+R2

To establishPa bound on the running time, we observe that each iteration of L AMBDAC RAWL -I NCOML O BS involves
evaluating w∈W − ρw , which takes O(|W − |) time, so by the properties of bisection search the total running time isupper bound λ−lower bound λO(log2 ()|W − |).

P ROOF OF P ROPOSITION 5 Let Chw (t) denote the total number of changes that have happened at source w intime interval [0, t]. As in the proof of Proposition 2, we start with rearranging the cost function in Equation 1, dropping the
distributions under the expectation and using W instead of W o throughout the proof to make the notation less cumbersome.
Using the definition of expectation and chain rule of probabilities to get:"π

J = lim

T →∞E

CrSeq∼π,~
ChSeq∼P (∆)

1= lim
T →∞ T

Z T

1
= lim
T →∞ T

Z T

1
= lim
T →∞ T

Z T

0

Z T
0

!
X

#

µw C(Nw (t)) dt

w∈W

!
X

µw E [C(Nw (t))] dt

w∈W

0

0

1
T

X

µw

∞ 
X

!
C(m) · P[Nw (t) = m]
dt

w∈W

m=0

X

∞ X
∞ 
X

µw

w∈W

!
C(m) · P[Nw (t) = m|Chw (t) = c]P[Chw (t) = c]dt

c=0 m=0−∆w t

c(∆w t)
Since changes at every source w are governed by a Poisson process with rate ∆w , P[Chw (t) = c] = e. Now,
c!
oconsider P[Nw (t) = m|Chw (t) = c]. Recall that whenever source w ∈ W changes, we find out about the change
immediately; with probability pw the policy π ∈ Πo then crawls source w straight away, and with probability (1 − pw ) it
waits to make this decision until we find out about w’s next change. Therefore, the only way we can have Nw (t) = m is if
our policy crawled source w m + 1 changes ago and has not chosen to crawl w after any of the m changes that happened
since, or it hasn’t chosen to crawl w since ”the beginning of time”. Thus, Nw (t) is geometrically distributed, assuming thatat least m + 1 changes actually happened at source w in the time interval [0, 1]. Thus, we havem
pw (1 − pw ) , if c ≥ m + 1
P[Nw (t) = m|Chw (t) = c] = (1 − pw )m ,if c = m0otherwise
Recalling that C(m) = H(m) for m > 0 and C(0) = 0 (Equation 3) and putting everything together, we have1
J π = lim
T →∞ T

Z T

1
= lim
T →∞ T

Z T

1
= lim
T →∞ T

Z T

0

0

0

X

µw

∞ X
∞ 
X

!
C(m) · P[Nw (t) = m|Chw (t) = c]P[Chw (t) = c]dtw∈Wc=0 m=0X∞  −∆w t
Xe(∆w t)c

µw

c!

w∈W

c=1

X


∞  −∆w t
Xe(∆w t)c

w∈W

µw

c=1

c!

pw

c−1
X

m

H(m)(1 − pw ) + H(c)(1 − pw )

c

!
dt

m=1

pw

∞
X
m=1

m

H(m)(1 − pw ) − pw

∞
X
m=c

m

H(m)(1 − pw ) + H(c)(1 − pw )

c

!
dt

Staying up to Date with Online Content Changes Using Reinforcement Learning for Scheduling

Now consider
Z T
G(T ) =0Z T
R(T ) =0Z T
F (T ) =0X∞  −∆w t
Xe(∆w t)c

µw

c!

w∈W

c=0

X


∞  −∆w t
Xe(∆w t)c

µw

c!

X


∞  −∆w t
Xe(∆w t)c
c!

c=0

Since

!

C(m)(1 − pw )

dt

pw

∞
X

m

!

C(m)(1 − pw )

dt

m=c

c=0

µw

pw

m

m=0

w∈W

w∈W

∞
X

C(c)(1 − pw )

c

!
dt

1
(G(T ) − R(T ) + F (T )),T →∞ TJ π = lim)R(T )F (T )
if we show that each of limT →∞ G(Texists and manage to compute them, then we
T , limT →∞ T , and limT →∞ Tπwill know J . The rest of the proof focuses on computing these limits.
P∞
P∞
Consider G(T ). Note that pw m=0 C(m)(1 − pw )m = pw m=1 H(m)(1 − pw )m doesn’t depend on c. We canP∞P∞
use the identity m=1 H(m)xm = − ln(1−x)
for |x| < 1 to get pw m=0 C(m)(1 − pw )m = − ln(pw ), so G(T ) =
1−x






RT P
P∞
P∞
e−∆w t (∆w t)ce−∆w t (∆w t)c
− 0
µ
ln(p
)
dt.
To
simplifyG(T)
further,note
thatis just
w
w
w∈W
c=0
c=0
c!
c!

the probability of any number of changes occurring in time interval [0, t] under a Poisson process, and therefore equals 1.
RT PPThus, G(T ) = − 0w∈W µw ln(pw ) dt = −Tw∈W µw ln(pw ), so
X
G(T )
=−
µw ln(pw ).
T →∞
T
lim

w∈W

P∞
P∞
Consider R(T ). Observe that C(m) = H(m) < m for m > 1, so pw m=c C(m)(1−pw )m < pw m=c m(1−pw )m =c
(1−pw ) (cpw −pw +1)
1. Because (1 − pw )c decreases in c much faster than c(cpw −p
for any fixed 0 < pw ≤ 1, for any
pw
w +1)
c
P
∞
(1−pw ) (cpw −pw +1)
1∗m
w ∈ W there is a cw s.t. pw m=c C(m)(1 − pw ) << c for any c > c∗w . Let c∗ = maxw∈W c∗w .
pw
We can then upper-bound R(T ) as follows:

Z T
R(T ) =
0

X

µw


∞  −∆w t
Xe(∆w t)c
c!

c=0

w∈W

pw

∞
X

C(m)(1 − pw )m!
dt = R1 (T ) + R2 (T ),

m=c

where
Z T
R1 (T ) =0Z T
R2 (T ) =
0

X

µw

∗
cX
−1  −∆w t

e(∆w t)c
c!



w∈W

c=0

X


∞  −∆w t
Xe(∆w t)c

w∈W

µw

c=c∗

c!

pw

∞
X

m

!

C(m)(1 − pw )

dt

m=c

pw

∞
X

m

C(m)(1 − pw )

!
dt

m=c

P∞
P∞
Considering R1 (T ), recalling that C(m) = H(m) for m > 0, we have pw m=c C(m)(1 − pw )m ≤ pw m=1 C(m)(1 −R−∆tcw (∆ t)Tw
wT )pw )m = − ln(pw ), as shown previously. Also, for any c we have 0 e
dt = Γ(c+1)−Γ(c+1,∆. Therefore,
c!
∆w c!

Staying up to Date with Online Content Changes Using Reinforcement Learning for Scheduling

Z T

X

R1 (T ) =
0

<−

w∈W

X

µw

∗
cX
−1  −∆w t(∆w t)cc!

e

c=0µw ln(pw )

∞
X


pw

m

!

C(m)(1 − pw )

dt

m=c

∗
cX
−1

w∈W

Γ(c + 1) − Γ(c + 1, ∆w T )
∆w c!
c=0

wT )
= 0, R1 (T ) is therefore upper-bounded by a finite sum of terms that all go to 0 when divided
Since limT →∞ Γ(c+1,∆
T
by T as T → ∞. Since R1 (T ) ≥ 0 also holds, we have limT →∞ R1T(T ) = 0.

Considering R2 (T ), we use our definition of c∗ to write

Z T

X

R2 (T ) =
0

Z T
<
0

Z T
≤

c!

c=c∗

X

 
∞  −∆w t
X1e(∆w t)c

µw

c=c∗

X


∞  −∆w t
Xe(∆w t)c

µw

Z T
0

w∈W

X

µw

w∈W

C(m)(1 − pw )

m

!
dt

m=c

c!

w∈W

w∈W

=

pw

∞
X

w∈W

c

!

Z T
dt =
0

X
w∈W

µw

!
∞  −∆w t
Xe(∆w t)cc=c∗(c + 1)!

dt!

(c + 1)!
!
X
1 − e−∆w t
µw
dt
∆w t

0

=

µw


∞  −∆w t
Xe(∆w t)cdt

c=0

ln(∆w T ) + Γ(0, ∆w T ) + γ
,
∆w

wT )
where γ is the Euler-Mascheroni constant. Since limT →∞ Γ(0,∆= 0, R2 (T ) is therefore upper-bounded by a finite sumTof terms that all go to 0 when divided by T as T → ∞. Since R2 (T ) ≥ 0 also holds, we have limT →∞ R2T(T ) = 0. Thus,
we haveR(T )R1 (T ) + R2 (T )R1 (T )
R2 (T )
= lim
= lim
+ lim
=0
T →∞
T →∞
T →∞
T →∞
T
T
T
T
lim

)
Consider F (T ). Observe that for a suitably chosen constant s > 0, sR(T ) > F (T ). Therefore, since limT →∞ R(T= 0,T)limT →∞ F (T
=
0
too.
T

We have thus shown that
X
G(T ) − R(t) + F (T )
G(T )
R(T )
F (T )
= lim
− lim
+ lim
=−
µw ln(pw )
T →∞
T →∞
T →∞
T →∞
T
T
T
T

J π = limw∈W

P ROOF OF P ROPOSITION 6. Since under any p~ ≥ 0 crawl rates ρ~ are related to crawl probabilities via ρw = pw ∆w ,to apply the method of Lagrange multipliers to the relaxation of Problem 2 that takes into account only the bandwidthPPπconstraint we set f (~p) = J = w∈W o µw ln(pw ) and g(~ρ) = w∈W o pw ∆w − R. We need to solveStaying up to Date with Online Content Changes Using Reinforcement Learning for Scheduling(∇f (~p) = λ∇g(~p)g(~p) = 0.
∂f∂g= ∆w and ∂p= µpww , so the above system of equations turns into
For any w ∈ W o , we have ∂p
w
w

(

µw

= λ∆w ,w∈W o pw ∆w = R

pw
P

for all w ∈ W o

and therefore(
pw = ∆w PRµw o µw for all w ∈ W o
λ=

w∈W

P

w∈W o µw

R

This is the only solution yielded by the method of Lagrange multipliers, so it is the unique maximizer of the relaxation.

P ROOF OF P ROPOSITION 7.
To establish L AMBDAC RAWL -C OMPL O BS’s correctness, we first prove the following lemma, which establishes that any
source w that violates its pw ≤ 1 constraint in any iteration of L AMBDAC RAWL -C OMPL O BS must have p∗w = 1:
Lemma 1. Let p~∗ be the maximizer of Problem 2, and let p~0∗ be the maximizer of the relaxation Problem 2 with the same
inputs but with inequality constraints ignored. Then any source w that has p~0∗ has p0∗
w > 1, violating its inequality constraint,
necessarily has p∗w = 1.
P
Proof. For convenience,
we rewrite Problem 2 as an equivalent problem of maximizing J mod = w∈W o µw ln(ρw ) underP
the constraints w∈W o ρw = R and ρw ≤ ∆w for every w ∈ W o . Consider its relaxation with ρw ≤ ∆w for every0∗w ∈ W o ignored. By the equivalent of Proposition 6 for this reformulation,ρ~0∗ is unique and must have p0∗
w = ρw /∆wPfor each source w. The Lagrangian of L(~
ρ, λ0 ) := J mod (~ρ) − λ0 ( w∈W o ρw − R) must have ∇L(~
ρ0∗ , λ0∗
)
=
0
for
the
0
0∗
optimal solution (~ρ0∗ , λ0∗)(which,again,
encodestheoptimalpfortherelaxationoftheoriginal
formulationofProblem
2
w
0
∂
∂
0∗
0∗
o
0∗ = λ0∗ , for any sources u, w ∈ W . Since
via p0∗
=
ρ
/∆
).
From
this
we
see
that
J

=
J

w
mod
ρ
mod
ρ
w
w
0
∂ρu
∂ρw
u
w
µw
∂
,
this
implies
J
=
mod
∂ρw
ρw
µu
µw
= 0∗ for all u, w ∈ W o .
(18)
0∗
ρu
ρw
Consider the slack-variable formulation of Problem 2 with slack variables {qw }w∈W o . Inequality constraints in thisformulation turn into ρw = ∆w − qw for qw ≥ 0. In this formulation, we now haveXL(~ρ, λ0 , λ1 , . . . , λ|W o | ) := L(~ρ, λ0 ) −λw (ρw − ∆w ) .
w∈W o

where, by the Karush-Kuhn-Tucker conditions, λw ≥ 0 for all w. By complementary slackness, λ∗w = 0 for everyw ∈ W o such that qw > 0, i.e., for every w that does not activate its inequality constraint, under the optimal solution(~ρ∗ , λ∗0 , λ∗w , . . . , λ∗|W o | ). This implies that ∂ρ∂u J mod ρ∗u −λ∗u = λ∗0 = ∂ρ∂w J mod ρ∗w −λ∗w , for any sources u, w ∈ W o , i.e.,µuµw− λ∗u = λ∗0 = 0∗ − λ∗w
ρ0∗
ρw
u

for all u, w ∈ W o .

(19)

∗
0∗
Now, suppose for contradiction that there is a source u ∈ W o that has p0∗
u > 1 but pu < 1, implying that ρu > ∆u but∗0∗∗∗ρu < ∆u . This, in turn, implies thatand (b) λu = 0, since u doesn’t activate its inequality constraint under ρ~∗P(a) ρu > ρuP(and hence under p~∗ ). Then, since v∈W o ρ∗v = v∈W o ρ0∗
=
R,
there
must
also
exist
some
other
source
w
=
6
u
such
that
v
∗
∗
∗
∗
ρ0∗
w < ρw . For this source, λw ≥ 0, so λw ≥ λu .

Staying up to Date with Online Content Changes Using Reinforcement Learning for Scheduling

Recall that J mod is strictly concave, and its partial derivatives µρvv are monotone decreasing in every non-negative ρv .
∗
0∗
∗
∗
∗
Together with ρ0∗
u > ρu , ρw < ρw , λw ≥ λu , and Equation 19, this implies
µu
µw
µw
µu
< ∗ ≤ ∗ < 0∗
ρ0∗
ρ
ρ
ρw
u
u
w
But this contradicts Equation 18, completing the proof of the lemma.

The optimality of L AMBDAC RAWL -C OMPL O BS now follows by induction. Its every iteration except the last one identifies atleast one constraint that is active under p~∗ , by the above lemma, and thereby assigns an optimal p∗w to some sources, leaving
optimal crawl probabilities for others to be found in subsequent iterations. The solution for the sources remaining in the
final iteration, which does not violate any inequality constraints, is optimal by Proposition 6. Therefore, L AMBDAC RAWL C OMPL O BS arrives at the optimal solution, and that solution is unique because Problem 2’s maximization objective isconcave as a sum of concave functions, and the optimization region is convex.
We note that the proof so far is similar to the proof of Lemma 3.3 from (Kolobov et al., 2019) for a different concave function
F under constraints of the form x1 + . . . + xk ≤ ck , where x1 , . . . , xk is a subset of F ’s variables and ck is a constraint.
Since in each iteration L AMBDAC RAWL -C OMPL O BS removes at least one source from further consideration, it makes
at most |W o | iterations. In each iteration it applies Proposition 6, which takes O(|W o |) time, yielding the overall timecomplexity of O(|W o |2 ).
P ROOF OF P ROPOSITION 8. See the paper.

~ˆP ROOF OF P ROPOSITION 9. L AMBDA L EARNA ND C RAWL starts with strictly positive finite estimates ∆0 ofchange rates. Since L AMBDAC RAWL, which L AMBDA L EARNA ND C RAWL uses for determining crawl rates for the
next epoch, is optimal to any desired precision (Proposition 8), it follows from Proposition 1 that it returns positive~ˆ~∗ , p̂~∗ > 0, and 0 < µ~ , R < ∞ guarantees that these crawl rates are also finite. In subsequent iterations, ∆ρ̂n are estimated
1 1
using Equations 14 and 15 with smoothing terms (lines 11 and 13 of Algorithm 4), and the smoothing terms ensure that~ˆ
the change rate estimates are finite and bounded away from 0: 0 < δmin ≤ ∆n < ∞, where δmin is implied by the
aforementioned estimators and specific smoothing term values. This, along with finite positive µ~ and R, ensures that~∗ , p̂~∗ < δmax . Hence, by induction, no source is ever starved, and no source is crawled infinitely frequently.
0 < ρ̂
n+1 n+1
This ensures, together with consistency of estimators from Equations 14 and 15, that if at least the last iteration Nepoch uses
the entire observation history, i.e. S(Nepoch ) = length(obs hist), then change rate estimates converge to the true change~ˆ~ as long as ∆~ doesn’t change with time. Optimality of L AMBDAC RAWL
rates in probability: plim∆
= ∆,N
Nepochs →∞epochs~∗~∗~∗ ~∗then implies probabilistic convergence of (ρ̂Nepochs , p̂Nepochs ) to (ρ̂ , p̂ ) as well.

P ROOF OF P ROPOSITION 10. According to Equation system 7, the parameter vector ρ~ of the optimal π ∗ ∈ Π− thatminimizes the expected harmonic penalty in the absence of remote change observations (Problem 1) satisfies
(

√

ρw =
P

−∆w +

∆2w + 4µwλ∆w,
2

for all w ∈ W −w∈W − ρw = Rµw
If ∆= c for all w ∈ W − , c > 0, then we can express ∆w = c0 µw where c0 = 1/c and plug it into the above equations tow
getStaying up to Date with Online Content Changes Using Reinforcement Learning for Scheduling

ρw =

−∆w +

q

∆2w + 4µwλ∆w

q2
4c0 µ2−c µw + (c0 µw )2 + λ w
0

=

0

=

−c µw + µw

2qc02 λ+4c0
λ

2q

02
0
−c + c λ+4cλ
 for all w ∈ W −= µw 
20Plugging this into the remaining equation from the above system,


X

−c0 +

q

c02 λ+4c0
λ

(20)

P

w∈W − ρw = R, we get = R =⇒
2q02
0
−c0 + c λ+4c
R
λ
=P
=⇒
2
w∈W − µw
22R
c02 λ + 4c0
= P
+ c0
=⇒
λ
w∈W − µw

2
2R
0
λ P
+c
− c02 λ = 4c0 =⇒w∈W − µw
µw 

w∈W −

4c0

λ= 

2R
P

w∈W

+ c0
− µw

Plugging this and ∆w = c0 µw back into Equations 20, we get for all w ∈ W −

2

− c02

Staying up to Date with Online Content Changes Using Reinforcement Learning for Scheduling

v 


u
u 

u c02 4c0
+4c0 !2
u  P 2R


+c0
−c02

 0 u
µ
− w
w∈W
u

 −c + t
0
4c


!2


2R
P
+c0
−c02
µ


w
w∈W −

ρw = µw 


2














v 
 
u
u 
 
u 4c0 c02
+1 !2 u  P 2R

+c0
−c02
 0 u

µw
−
w∈W
 −c + u

4c0
t


!2


2R
0
02
P
+c
−c
µ


w∈W − w

= µw 

2














v
2 
2

u
2R
u P 2R µ +c0P+c0 −c02µ− w
 −c0 + uw∈W − w
2
t w∈W 


2R
0
02


P
+c
−c
µw
−


w∈W


= µw 

2









= µw −c0 + P

Rw∈W − µw

=P

+ c0



µw R

w∈W − µw



10. Details of the Experiments and Additional Plots
In the experiments we used the following algorithms for comparison:
ImportanceCrawl (IC) is the name we give to the heuristic proposed by Cho & Garcia-Molina (2003a) that sets
ρw = Pµw R

w0 ∈W µw,
0i.e., crawls sources at a rate proportional to their importance. This heuristic doesn’t differentiate between pages with andwithout remote change observations. Note that our Proposition 10 implies that ImportanceCrawl is actually a special casewof L AMBDAC RAWL— without the L AMBDAC RAWL -C OMPL O BS component and assuming that mu∆w is the same forall sources in W . Thus, our theory identifies conditions under which ImportanceCrawl, previously considered merely aheuristic, is optimal.
ChangeRateCrawl (CC) is the name we give to another heuristic proposed by Cho & Garcia-Molina (2003a) that sets

Staying up to Date with Online Content Changes Using Reinforcement Learning for Scheduling

∆w R
,
0
w0 ∈W ∆w

ρw = P

thereby crawling sources at a rate proportional to their change rate. Cho & Garcia-Molina (2003a) pointed outthat ChangeRateCrawl can be very suboptimal if the set W includes sources that change frequently. This causes
ChangeRateCrawl to over-commit crawl bandwidth to sources whose changes are near-impossible to keep up with, at theexpense of almost ignoring the rest. Our experimental results agree with this observation — ChangeRateCrawl turned out tobe the second weakest-performing baseline.
BinaryCrawl (BC) is the algorithm proposed by Azar et al. (2018) that produces crawl rates that minimizes binary stalenessor, as this objective is equivalently stated in Azar et al. (2018), maximizes binary freshness
lim E

T →∞

"

1
T

Z T

n
X

0

i=1

µi · 1F RESH(i,t)

!

#
dt

.
It is related to our objective, but has a major difference — according to it, the marginal penalty for the 2nd, 3rd, etc change
at a source is 0.
This difference is crucial in practice, because minimizing binary staleness generally yields ρ~∗ with ρ∗w = 0 for many sourceseven if they ∆w > 0. This effectively tells the tracker to ignore changes to these sources — an unacceptable strategy in realapplications. Indeed, harmonic penalty (Equation 1) assigns J π = ∞ to such strategies, causing BinaryCrawl to be theweakest-performing baseline in our experiment, in spite of its formal optimality guarantee w.r.t. binary staleness.
UniformCrawl (UC) is a heuristic that assigns an equal crawl rate to all sources:ρw = R/|W |.
In spite of its simplicity, in our experiments it outperforms ChangeRateCrawl, as predicted by Cho & Garcia-Molina(2003a), and BinaryCrawl (Azar et al., 2018).
Dataset details. Proposition 10 suggests that the performance gap between L AMBDAC RAWL, L AMBDAC RAWL A PPROX,µw
and ImportanceCrawl depends on the distribution of the ratios ∆across the set of sources W : if they are all equal, thew
policy cost of L AMBDAC RAWL and L AMBDAC RAWL A PPROX should be the same, with ImportanceCrawl’s being similar(dependent on the fraction of sources with complete remote observations, which ImportanceCrawl ignores). As Figure 4
shows, these ratios are indeed similar across much of our dataset.

µw
Figure 4. Ranking of 20,151,303 URLs in our dataset by their ∆ratio. This ratio distribution is nearly constant across most of thew
dataset, except the URLs at the head of the ranking.

Details of the reinforcement learning experiment (Figure 3). The goal of the last experiment was assessing the convergence properties of L AMBDA L EARNA ND C RAWL and L AMBDA L EARNA ND C RAWL A PPROX. We sampled 100,000 URLs
from the aforementioned 20M-URL dataset uniformly at random. Using the dataset, we simulated runs of L AMBDA L EAR NA ND C RAWL and its Proposition 10-based approximation L AMBDA L EARNA ND C RAWL A PPROX . We set the length of 1

Staying up to Date with Online Content Changes Using Reinforcement Learning for Schedulingepoch (Algorithm 4) to 14 days, and simulated a 98-day crawling and learning process as follows. We generated 98 days’
worth of page changes using the ground-truth change rates (unknown to L AMBDA L EARNA ND C RAWL and L AMBDA L EAR NA ND C RAWL A PPROX at the beginning). As in the real dataset, for 13% of the URLs we (simulated) instantaneous change
notifications to our algorithms. Then we ran L AMBDA L EARNA ND C RAWL and L AMBDA L EARNA ND C RAWL A PPROX on
this simulated data, which at each epoch n reestimated page change rates using data from executing their policies in theprevios epochs, recomputed the policy, and executed it during the n-th epoch. For the 1st epoch, both algorithms ran the”warm-start” policy produced by ImportanceCrawl, which doesn’t need change rate estimates. At the start of each epoch aswell as the end of the last, 6th epoch, we evaluated the algorithms’ newly computed policies using the ground truth change
rates from the dataset Equation 13. We repeated the above procedure 20 times and plotted the results in Figure 3. Along with
L AMBDA L EARNA ND C RAWL’s and L AMBDA L EARNA ND C RAWL A PPROX’s performance we plotted the (hypothetical)
policy quality of L AMBDAC RAWL and L AMBDAC RAWL A PPROX assuming the ground-truth change rates were known
to them — this is the asymptotic performance level of the learning algorithms. Figure 3 also shows the performance ofImportanceCrawl for comparison: the RL algorithms start with its performance due to using it as a warm start, but improvetheirs thanks to learning to nearly asymptotic level after just 2 epochs.