@inproceedings{bb57a091c7014fd3979ddbd2eb7d9c8a,
title = "Bandits with side observations: Bounded vs. logarithmic regret",
abstract = "We consider the classical stochastic multi-armed bandit but where, from time to time and roughly with frequency e, an extra observation is gathered by the agent for free. We prove that, no matter how small e is the agent can ensure a regret uniformly bounded in time. More precisely, we construct an algorithm with a regret smaller than Σi log(1/ϵ)/Δi, up to multiplicative constant and log log terms. We also prove a matching lower-bound, stating that no reasonable algorithm can outperform this quantity.",
author = "R{\'e}my Degenne and Evrard Garcelon and Vianney Perchet",
note = "Publisher Copyright: {\textcopyright} 2018 by Association For Uncertainty in Artificial Intelligence (AUAI) All rights reserved.; 34th Conference on Uncertainty in Artificial Intelligence, UAI 2018 ; Conference date: 06-08-2018 Through 10-08-2018",
year = "2018",
month = jan,
day = "1",
language = "English",
series = "34th Conference on Uncertainty in Artificial Intelligence 2018, UAI 2018",
publisher = "Association For Uncertainty in Artificial Intelligence (AUAI)",
pages = "467--476",
editor = "Amir Globerson and Amir Globerson and Ricardo Silva",
booktitle = "Uncertainty in Artificial Intelligence - Proceedings of the 34th Conference, UAI 2018",
}