Online learning with Erdős-Rényi side-observation graphs

Abstract

We consider adversarial multi-armed bandit problems where the learner is allowed to observe losses of a number of arms beside the arm that it actually chose. We study the case where all non-chosen arms reveal their loss with a fixed but unknown probability $r$, independently of each other and the action of the learner. We propose two algorithms that work for different ranges of $r$. We show that after $T$ rounds in a bandit problem with $N$ arms, the expected regret of our first algorithm is $O(\sqrt{(T/r)\log N})$ whenever $r\ge (\log T)/(2N)$, while our second algorithm achieves a regret of $O(\sqrt{(T/r)\log (N+T)})$ for smaller values of $r$. We also give a quick estimation procedure that decides the range of~$r$. All our bounds are within logarithmic factors of the best achievable performance of any algorithm that is even allowed to know~$r$.

Published at International Conference on Machine Learning (ICML) 2015. 11 pages

References in corpus (3)

• Efficient learning by implicit exploration in bandit problems with side observations
• Online learning with noisy side observations
• Revealing graph bandits for maximizing local influence