# Online learning with noisy side observations

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 16 references that are in the map.
- First posted on arXiv 15 Apr 2026.

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

- [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 Gaussian Payoffs and Side Observations](https://mlsanity.com/paper/1510.08108/) (2015)
- [Prediction by Random-Walk Perturbation](https://mlsanity.com/paper/1302.5797/) (2013)

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

- [Revealing graph bandits for maximizing local influence](https://mlsanity.com/paper/2605.00489/) (2026)
- [Online learning with ErdHos-R'enyi side-observation graphs](https://mlsanity.com/paper/2604.25271/) (2026)
- [Spectral bandits](https://mlsanity.com/paper/2604.25272/) (2026)
- [Bandits on graphs and structures](https://mlsanity.com/paper/2605.03493/) (2026)

## Abstract (arXiv)

We propose a new partial-observability model for online learning problems where the learner, besides its own loss, also observes some noisy feedback about the other actions, depending on the underlying structure of the problem. We represent this structure by a weighted directed graph, where the edge weights are related to the quality of the feedback shared by the connected nodes. Our main contribution is an efficient algorithm that guarantees a regret of widetildeO(√α^* T) after T rounds, where α^* is a novel graph property that we call the effective independence number. Our algorithm is completely parameter-free and does not require knowledge (or even estimation) of α^*. For the special case of binary edge weights, our setting reduces to the partial-observability models of Mannor and Shamir (2011) and Alon et al. (2013) and our algorithm recovers the near-optimal regret bounds.