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 synchronization bandits, a MAB variant where all arms generate costs at all times, but the agent observes an arm's instantaneous cost only when the arm is played. Synchronization MABs are inspired by online caching scenarios such as Web crawling, where an arm corresponds to a cached item and playing the arm means downloading its fresh copy from a server. We present MirrorSync, an online learning algorithm for synchronization bandits, establish an adversarial regret of $O(T^{2/3})$ for it, and show how to make it practical.
Introduction
In traditional multi-armed bandit (MAB) frameworks, an agent receives a reward or incurs a cost only when a specific action (pulling an arm) is taken. However, many real-world systems—most notably web crawlers and database caches—operate under a different paradigm. In these environments, the cost (staleness) of an item accumulates continuously over time, regardless of whether the agent interacts with it.
This paper formalizes this challenge as the Synchronization Bandit problem. In this setting, an agent manages $K$ items under a bandwidth constraint $B$. The goal is to minimize the total accumulated cost over time by deciding when to refresh each item. The primary difficulty lies in the partial observability: the agent only learns the current cost of an item at the moment it is refreshed or probed.
The Synchronization Bandit Model
Unlike standard MABs, where the environment is often assumed to be stationary or follows a specific distribution, the Synchronization Bandit model accounts for costs that are a function of the time elapsed since the last synchronization. Let $\tau$ be the time since the last refresh; the cost $c_k(\tau)$ is typically a non-decreasing function.
The agent's objective is to find an optimal vector of refresh rates $r$ that minimizes the long-term average cost while staying within the bandwidth budget $\sum r_k \leq B$. Because the underlying cost processes (e.g., how frequently a specific web page changes) are unknown and potentially adversarial, the agent must learn these rates online.
The MIRRORSYNC Algorithm
To address the synchronization challenge, the authors propose MIRRORSYNC, an algorithm rooted in Online Mirror Descent (OMD). The algorithm introduces several key innovations to handle the unique constraints of the synchronization setting.
Dual Play Modes: Sync and Probe
To estimate the cost gradients without knowing the cost functions, MIRRORSYNC utilizes two distinct interaction modes:
- Sync Mode: The agent refreshes the item, resetting its staleness timer to zero and observing the cost at that moment.
- Probe Mode: The agent observes the current cost to see how much it has grown since the last sync, but does not reset the timer. This allows for a more accurate estimation of the cost function's slope.
Log-Barrier Mirror Descent
A significant hurdle in this problem is that the gradient of the cost function often scales inversely with the refresh rate ($1/r_k$). In standard Stochastic Gradient Descent (SGD), this leads to exploding gradients as rates approach zero. MIRRORSYNC employs a log-barrier potential function within the Mirror Descent framework. This choice of geometry ensures that the algorithm remains stable even when dealing with very small refresh rates, effectively "warping" the search space to prevent divergence.
ASYNCMIRRORSYNC
Recognizing that theoretical models often assume synchronized "rounds" that do not exist in real-world systems, the authors developed ASYNCMIRRORSYNC. This variant allows for asynchronous updates and removes the requirement for "free" resets at the start of rounds, making the approach viable for production-scale web crawlers.
Theoretical and Empirical Results
The authors establish a theoretical regret bound of $O(T^{2/3})$ for MIRRORSYNC in adversarial settings. This indicates that the algorithm's performance converges toward the optimal fixed strategy as time progresses.
Empirical evaluations were conducted using two primary cost models:
- Polynomial Cost Processes: Where costs grow as $c_k(\tau) = a_k \tau^{p_k}$.
- Poisson Process-based Costs: A binary model where cost is 0 if no change has occurred and 1 if at least one change has occurred, mimicking web page updates.
In simulations, MIRRORSYNC and its asynchronous counterpart consistently outperformed standard Projected Stochastic Gradient Descent (PSGD), discovering optimal refresh policies significantly faster and maintaining lower total staleness.
Conclusion
The Synchronization Bandit framework provides a principled approach to a long-standing problem in data management. By shifting the focus from "payoff on play" to "cost on delay," and utilizing the stability of log-barrier Mirror Descent, MIRRORSYNC offers a robust solution for maintaining data freshness under resource constraints. Future work remains to bridge the gap between round-based regret and wall-clock-time regret, as well as scaling these gradient estimators to handle the billions of items managed by global-scale search engines.
Summary updated