  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.
