Timezone: »

 
Poster
Stochastic bandits with arm-dependent delays
Anne Gael Manegueu · Claire Vernade · Alexandra Carpentier · Michal Valko

Wed Jul 15 10:00 AM -- 10:45 AM & Wed Jul 15 11:00 PM -- 11:45 PM (PDT) @ None #None
in Poster Session 24 »

Significant work has been recently dedicated to the stochastic delayed bandit setting because of its relevance in applications. The applicability of existing algorithms is however restricted by the fact that strong assumptions are often made on the delay distributions, such as full observability, restrictive shape constraints, or uniformity over arms. In this work, we weaken them significantly and only assume that there is a bound on the tail of the delay. In particular, we cover the important case where the delay distributions vary across arms, and the case where the delays are heavy-tailed. Addressing these difficulties, we propose a simple but efficient UCB-based algorithm called the PATIENTBANDITS. We provide both problem-dependent and problem-independent bounds on the regret as well as performance lower bounds.

Keywords: Active Learning · Online Learning / Bandits · Online Learning, Active Learning, and Bandits

Author Information

Anne Gael Manegueu (Otto-von-Guerricke University)
Claire Vernade (Deepmind)
Alexandra Carpentier (Otto-von-Guericke University)
Michal Valko (DeepMind)

More from the Same Authors