Online Learning for Active Cache Synchronization
This addresses online caching scenarios like Web crawling, where it improves efficiency by optimizing when to update cached items, though it is incremental as it builds on existing MAB models.
The paper tackles the problem of active cache synchronization by introducing synchronization bandits, a variant of multi-armed bandits where arms generate costs continuously but are only observed when played, and presents MirrorSync, an algorithm with an adversarial regret of O(T^{2/3}).
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.