Timezone: »

 
Poster
Online Learning for Active Cache Synchronization
Andrey Kolobov · Sebastien Bubeck · Julian Zimmert

Tue Jul 14 07:00 AM -- 07:45 AM & Tue Jul 14 06:00 PM -- 06:45 PM (PDT) @
in Poster Session 1 »
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.
Keywords: Information Retrieval · Reinforcement Learning · Online Learning / Bandits · Other · Online Learning, Active Learning, and Bandits

Author Information

Andrey Kolobov (Microsoft Research)
Sebastien Bubeck (Microsoft Research)
Julian Zimmert (Google Research)

More from the Same Authors