# Online learning with ErdHos-R'enyi side-observation graphs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 20 references that are in the map.
- First posted on arXiv 28 Apr 2026.

## Builds on (most cited first, 6 of 6)

- [Online Learning with Feedback Graphs: Beyond Bandits](https://mlsanity.com/paper/1502.07617/) (2015)
- [From Bandits to Experts: A Tale of Domination and Independence](https://mlsanity.com/paper/1307.4564/) (2013)
- [Online Learning with Feedback Graphs Without the Graphs](https://mlsanity.com/paper/1605.07018/) (2016)
- [An efficient algorithm for learning with semi-bandit feedback](https://mlsanity.com/paper/1305.2732/) (2013)
- [Efficient learning by implicit exploration in bandit problems with side observations](https://mlsanity.com/paper/2604.24555/) (2026)
- [Online learning with noisy side observations](https://mlsanity.com/paper/2604.13740/) (2026)

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

- [Bandits on graphs and structures](https://mlsanity.com/paper/2605.03493/) (2026)

## Abstract (arXiv)

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(√(T /r) log N ) whenever r≥(log T)/(2N), while our second algorithm achieves a regret of O(√(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.