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 $\epsilon$, an extra observation is gathered by the agent for free. We prove that, no matter how small $\epsilon$ is the agent can ensure a regret uniformly bounded in time. More precisely, we construct an algorithm with a regret smaller than ${\sum }_i\frac{\log (1/\epsilon )}{{\Delta }_i}$, up to multiplicative constant and loglog terms. We also prove a matching lower-bound, stating that no reasonable algorithm can outperform this quantity.

arXiv commentConference on Uncertainty in Artificial Intelligence (UAI) 2018, 21 pages

References in corpus (5)

• Bounds on the Lambert function and their application to the outage analysis of user cooperation
• Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms
• From Bandits to Experts: On the Value of Side-Observations
• Online Learning with Feedback Graphs: Beyond Bandits
• Regret Analysis of the Anytime Optimally Confident UCB Algorithm

Cited by in corpus (3)

• Thompson Sampling for Combinatorial Network Optimization in Unknown Environments
• Crush Optimism with Pessimism: Structured Bandits Beyond Asymptotic Optimality
• Diversity-Preserving K-Armed Bandits, Revisited