# Bandits with Side Observations: Bounded vs. Logarithmic Regret

arXiv: https://arxiv.org/abs/1807.03558 · HTML: https://mlsanity.com/paper/1807.03558/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jul 2018.

## Built on by (most cited first, 4 of 4)

- [Leveraging Demonstrations to Improve Online Learning: Quality Matters](https://mlsanity.com/paper/2302.03319/) (2023)
- [Improved Policy Optimization for Online Imitation Learning](https://mlsanity.com/paper/2208.00088/) (2022)
- [Allocating Divisible Resources on Arms with Unknown and Random Rewards](https://mlsanity.com/paper/2306.16578/) (2023)
- [Leveraging Similarities in Multi-Armed Bandits](https://mlsanity.com/paper/2606.23414/) (2026)

## Abstract (arXiv)

We consider the classical stochastic multi-armed bandit but where, from time to time and roughly with frequency ε, an extra observation is gathered by the agent for free. We prove that, no matter how small ε is the agent can ensure a regret uniformly bounded in time. More precisely, we construct an algorithm with a regret smaller than sumi fraclog(1/ε)Deltai, up to multiplicative constant and loglog terms. We also prove a matching lower-bound, stating that no reasonable algorithm can outperform this quantity.