Online Learning for Active Cache Synchronization

Andrey Kolobov, Sébastien Bubeck, Julian Zimmert

Abstract Existing multi-armed bandit (MAB) models make two implicit assumptions: an arm generates a payoff only when it is played, and the agent observes every payoff that is generated. This paper introduces a novel framework to address environments where these assumptions fail, specifically focusing on active cache synchronization.

The Challenge of Active Caching

Traditional Multi-Armed Bandit (MAB) models operate on two fundamental assumptions: an arm only generates a payoff (or cost) when played, and the agent observes every generated payoff. However, in real-world active cache synchronization—such as a search engine crawler keeping its web index fresh—these assumptions break down.

A webpage changes at its source regardless of whether a crawler visits it. The "cost" (staleness) of a cached page grows continuously over time, but the crawler only observes how stale a page was at the exact moment it downloads a fresh copy. The core challenge is proactive scheduling: allocating a limited bandwidth budget (downloads per second) across $K$ different items to minimize total staleness, without knowing the underlying change rates and relying only on sparse "bandit feedback" during refreshes.

The Synchronization Bandit Framework

To tackle this, the authors formalize the problem as a Synchronization MAB. In this framework, the agent can interact with an arm in two distinct ways:

  • Sync Mode: Refresh the item, observe its current cost, and reset its staleness to zero.
  • Probe Mode: Observe the item's current cost without resetting it, used purely for gathering information.

The most critical insight of this framework is the concept of the "hidden" cost. In synchronization tasks, the agent is penalized for what it does not see. The cost is a function of elapsed time, not just the actions taken.

MIRRORSYNC: Navigating Problem Geometry

The paper's primary contribution is MIRRORSYNC, an algorithm that operates in rounds and uses Online Mirror Descent (OMD) to update the refresh rates ($r_k$) for each arm.

MIRRORSYNC introduces several key innovations:

  1. Unbiased Gradient Estimation via Probing: Because the agent does not see the full cost function, MIRRORSYNC sacrifices a small fraction of its bandwidth budget to "probe" items at random times. These probes allow the agent to construct an unbiased estimate of the cost gradient without needing a closed-form expression for the cost function.
  2. Log-Barrier Potential: Standard Stochastic Gradient Descent (SGD) struggles in this environment because gradients can explode as refresh rates approach zero (scaling with $1/r_k$). By utilizing OMD with a "log-barrier" potential function, MIRRORSYNC naturally adapts to the problem's geometry, replacing a polynomial dependence on the minimum refresh rate with a much more manageable logarithmic one.
  3. ASYNCMIRRORSYNC: Recognizing that real-world systems are rarely perfectly synchronized at the start of every round, the authors also provide a practical, asynchronous variant of the algorithm.

Experimental Setup and Key Results

The researchers evaluated MIRRORSYNC using synthetic problem instances, employing both polynomial cost functions and Poisson process models to ensure the algorithm's performance is independent of specific penalty functions.

The results demonstrate strong theoretical and empirical performance:

  • Theoretical Robustness: The paper establishes an adversarial regret bound of $O(T^{2/3})$. This guarantees that even if the change rates of the pages shift adversarially over time, the algorithm's performance remains competitive with the best fixed strategy.
  • Superior Convergence: In empirical tests, MIRRORSYNC converged significantly faster than baseline versions using projected SGD, validating the choice of Mirror Descent.
  • Practical Applicability: In simulations, the asynchronous version (ASYNCMIRRORSYNC) performed nearly identically to the idealized version, proving that the theoretical insights translate effectively to practical implementations without "free resets."

Limitations and Future Work

While MIRRORSYNC offers a robust solution for active caching, the authors note a few limitations. First, the current regret bound is calculated in terms of rounds rather than wall-clock time. In massive, slow-moving systems (like crawling billions of pages), a single round could be impractically long. Second, the model assumes cost monotonicity—that items only get staler over time. While true for caching, this may not apply to other synchronization tasks where costs fluctuate. Finally, while synthetic tests proved successful, testing the algorithm on actual web-crawl logs is a necessary next step to evaluate its resilience against the extreme non-stationarity of the real internet.

Summary updated

Abstract

Existing multi-armed bandit (MAB) models make two implicit assumptions: an arm generates a payoff only when it is played, and the agent observes every payoff that is generated. This paper introduce...
BibTeX
@inproceedings{kolobov2020online,
  author = {Andrey Kolobov and Sébastien Bubeck and Julian Zimmert},
  title = {{Online Learning for Active Cache Synchronization}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=qytGR4mf46},
}
Figure