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

Andrey Kolobov, Yuval Peres, Cheng Lu, Eric HorvitzNeurIPS 2019 · OpenReview

Introduction

From traditional web search engines to virtual assistants, services that rely on online information must continually track remote content changes. This requires explicitly requesting content updates from remote sources (e.g., web pages) through a process known as "freshness crawl scheduling."

This paper introduces a novel reinforcement learning framework designed to optimize exactly when a search engine should re-download a web page to keep its index up to date. By replacing traditional binary freshness metrics with a "harmonic penalty" objective, the authors developed algorithms that prevent content starvation and significantly outperform existing state-of-the-art methods on a massive real-world dataset of 18.5 million URLs.

The Challenge: Observability and Starvation

Search engines act as "trackers" that need to mirror the constantly changing state of the web. However, trackers operate under strict "bandwidth constraints"—they cannot crawl every page every second without overwhelming servers or incurring massive infrastructure costs.

This scheduling challenge is complicated by two main factors:

  1. Observability: For most pages, trackers only know a change has occurred after they crawl them (incomplete observations). For a small subset, trackers might receive a "ping" via a sitemap or telemetry indicating a change (complete observations).
  2. The Starvation Trap: Older models often relied on a binary metric where a page is either "fresh" (0 penalty) or "stale" (1 penalty). Mathematically, optimizing for this often leads to "starvation." The algorithm determines it is never "optimal" to spend bandwidth crawling slow-changing pages, leaving them to rot in the index indefinitely.

Methodology: Harmonic Penalty and LambdaCrawl

To overcome the starvation trap, the authors propose a new optimization objective based on Harmonic Numbers ($H(n) = \sum_{i=1}^n 1/i$).

Unlike binary metrics, the harmonic penalty is strictly increasing and discrete-concave. Every single change at a source adds to the penalty, but the first missed change hurts the most. This mathematical property ensures that the penalty for ignoring a changing source eventually grows to infinity, forcing the algorithm to crawl it and preventing starvation.

Based on this objective, the authors derive the LambdaCrawl family of algorithms:

  • LAMBDACRAWL-INCOMLOBS: Designed for sources where changes are hidden.
  • LAMBDACRAWL-COMPLOBS: Designed for sources that provide explicit change signals.
  • LAMBDACRAWL: A unified version that optimally splits a single bandwidth budget between these two types of sources.
Algorithm for optimal per-page crawl probabilities

Because change rates ($\Delta$) are rarely known upfront, the system integrates a model-based Reinforcement Learning (RL) approach called LAMBDALEARNANDCRAWL. It uses Maximum Likelihood Estimation (MLE) to learn how fast a page changes while simultaneously using those estimates to schedule the next crawl.

Dataset and Experimental Setup

The study is backed by an impressive real-world dataset collected from Microsoft Bing, comprising 18.5 million URLs. Over a 14-week duration, pages were crawled daily to establish a "ground truth" of when changes actually occurred.

The dataset featured mixed observability: while most URLs provided only incomplete observations, about 4% included "complete" change signals (like sitemaps), allowing the authors to rigorously test their mixed-observability model.

Key Insights and Results

  • The Power of Complete Observations: One of the most striking insights is the disproportionate impact of complete observation data. Even though only 4% of the URLs provided change signals, specifically optimizing for those signals yielded a 2x reduction in staleness for those pages. Furthermore, it allowed the tracker to reallocate saved bandwidth to harder-to-track pages.
  • Superiority over Prior Art: The unified LAMBDACRAWL (LC) policy proved highly robust. It outperformed the previous state-of-the-art (BinaryLambdaCrawl) by 35% in terms of harmonic staleness, while remaining near-optimal even when evaluated against older binary freshness metrics.
  • Fast Convergence: In the RL experiments where change rates were initially unknown, the LAMBDALEARNANDCRAWL algorithm converged to the optimal policy within just a few simulated "days" (epochs) of crawling.
  • Parameter-Free Scheduling: The authors identified a theoretical "sweet spot": if the ratio of a page's importance to its change rate is roughly constant across a set of pages, the system does not actually need to learn the change rates to schedule them optimally, significantly reducing computational overhead.

Limitations and Future Work

While highly effective, the model assumes that web pages change according to a Poisson process with a steady rate ($\Delta$). In reality, web changes can be "bursty" (e.g., a news site during a major event), which might require non-homogeneous Poisson models in the future.

Additionally, while the algorithms are efficient, scaling even low-polynomial algorithms to billions of pages remains a challenge, necessitating further work on big-data platform integration. Finally, the authors suggest framing this challenge as a "restless multi-armed bandit" (MAB) problem to open up new theoretical avenues for proving convergence in even more complex environments.

Summary updated

Abstract

From traditional Web search engines to virtual assistants and Web accelerators, services that rely on online information need to continually keep track of remote content changes by explicitly requesting content updates from remote sources (e.g., web pages). We propose a novel optimization objective for this setting that has several practically desirable properties, and efficient algorithms for it with optimality guarantees even in the face of mixed content change observability and initially unknown change model parameters. Experiments on 18.5M URLs crawled daily for 14 weeks show significant advantages of this approach over prior art.
BibTeX
@inproceedings{kolobov2019staying,
  author = {Andrey Kolobov and Yuval Peres and Cheng Lu and Eric Horvitz},
  title = {{Staying up to Date with Online Content Changes Using Reinforcement Learning for Scheduling}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=ZYQIHNtYbK},
}
Figure