# Cooperative Online Learning with Feedback Graphs

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

## Key facts

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

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

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Online Learning with Feedback Graphs: Beyond Bandits](https://mlsanity.com/paper/1502.07617/) (2015)
- [Delay and Cooperation in Nonstochastic Bandits](https://mlsanity.com/paper/1602.04741/) (2016)
- [Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback](https://mlsanity.com/paper/1409.8428/) (2014)
- [Bandit Learning in Decentralized Matching Markets](https://mlsanity.com/paper/2012.07348/) (2020)
- [The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits](https://mlsanity.com/paper/2001.05452/) (2020)
- [Cooperative Multi-Agent Bandits with Heavy Tails](https://mlsanity.com/paper/2008.06244/) (2020)
- [Collaborative Learning of Stochastic Bandits over a Social Network](https://mlsanity.com/paper/1602.08886/) (2016)
- [Adapting to Delays and Data in Adversarial Multi-Armed Bandits](https://mlsanity.com/paper/2010.06022/) (2020)
- [Cooperative Online Learning: Keeping your Neighbors Updated](https://mlsanity.com/paper/1901.08082/) (2019)
- [Multi-Agent Online Optimization with Delays: Asynchronicity, Adaptivity, and Optimism](https://mlsanity.com/paper/2012.11579/) (2020)
- [Kernel Methods for Cooperative Multi-Agent Contextual Bandits](https://mlsanity.com/paper/2008.06220/) (2020)
- [Individual Regret in Cooperative Nonstochastic Multi-Armed Bandits](https://mlsanity.com/paper/1907.03346/) (2019)
- [A Generalized Online Mirror Descent with Applications to Classification and Regression](https://mlsanity.com/paper/1304.2994/) (2013)
- [Bayesian Algorithms for Decentralized Stochastic Bandits](https://mlsanity.com/paper/2010.10569/) (2020)
- [An Efficient Algorithm for Cooperative Semi-Bandits](https://mlsanity.com/paper/2010.01818/) (2020)

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

- [Topological Structure Learning Should Be A Research Priority for LLM-Based Multi-Agent Systems](https://mlsanity.com/paper/2505.22467/) (2025)
- [An Application of Online Learning to Spacecraft Memory Dump Optimization](https://mlsanity.com/paper/2202.06617/) (2022)
- [Decentralized Online Bandit Optimization on Directed Graphs with Regret Bounds](https://mlsanity.com/paper/2301.11802/) (2023)
- [Decentralized Parameter-Free Online Learning with Compressed Gossip](https://mlsanity.com/paper/2605.27831/) (2026)

## Abstract (arXiv)

We study the interplay between communication and feedback in a cooperative online learning setting, where a network of communicating agents learn a common sequential decision-making task through a feedback graph. We bound the network regret in terms of the independence number of the strong product between the communication network and the feedback graph. Our analysis recovers as special cases many previously known bounds for cooperative online learning with expert or bandit feedback. We also prove an instance-based lower bound, demonstrating that our positive results are not improvable except in pathological cases. Experiments on synthetic data confirm our theoretical findings.