# Cooperative Online Learning: Keeping your Neighbors Updated

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jan 2019.

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

- [A survey on multi-player bandits](https://mlsanity.com/paper/2211.16275/) (2022)
- [Distributed Bandits with Heterogeneous Agents](https://mlsanity.com/paper/2201.09353/) (2022)
- [Doubly Adversarial Federated Bandits](https://mlsanity.com/paper/2301.09223/) (2023)
- [On-Demand Communication for Asynchronous Multi-Agent Bandits](https://mlsanity.com/paper/2302.07446/) (2023)
- [Distributed Online Learning for Joint Regret with Communication Constraints](https://mlsanity.com/paper/2102.07521/) (2021)
- [Cooperative Stochastic Multi-agent Multi-armed Bandits Robust to Adversarial Corruptions](https://mlsanity.com/paper/2106.04207/) (2021)
- [Cooperative Online Learning with Feedback Graphs](https://mlsanity.com/paper/2106.04982/) (2021)
- [On Regret-optimal Cooperative Nonstochastic Multi-armed Bandits](https://mlsanity.com/paper/2211.17154/) (2022)
- [Distributed Online Optimization with Stochastic Agent Availability](https://mlsanity.com/paper/2411.16477/) (2024)
- [Multiplayer Information Asymmetric Bandits in Metric Spaces](https://mlsanity.com/paper/2503.08004/) (2025)
- [Multiplayer Information Asymmetric Contextual Bandits](https://mlsanity.com/paper/2503.08961/) (2025)
- [Online Learning with Uncertain Feedback Graphs](https://mlsanity.com/paper/2106.08441/) (2021)
- [Asymptotic Optimality for Decentralised Bandits](https://mlsanity.com/paper/2109.09427/) (2021)
- [Online-to-PAC generalization bounds under graph-mixing dependencies](https://mlsanity.com/paper/2410.08977/) (2024)
- [A Survey on Distributed Online Optimization and Game](https://mlsanity.com/paper/2205.00473/) (2022)
- [Multitask Online Learning: Listen to the Neighborhood Buzz](https://mlsanity.com/paper/2310.17385/) (2023)
- [PAC-Learning Uniform Ergodic Communicative Networks](https://mlsanity.com/paper/2111.10708/) (2021)
- [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)
- [Flooding with Absorption: An Efficient Protocol for Heterogeneous Bandits over Complex Networks](https://mlsanity.com/paper/2303.05445/) (2023)
- [Distributed No-Regret Learning for Multi-Stage Systems with End-to-End Bandit Feedback](https://mlsanity.com/paper/2404.04509/) (2024)
- [Decentralized Parameter-Free Online Learning with Compressed Gossip](https://mlsanity.com/paper/2605.27831/) (2026)

## Abstract (arXiv)

We study an asynchronous online learning setting with a network of agents. At each time step, some of the agents are activated, requested to make a prediction, and pay the corresponding loss. The loss function is then revealed to these agents and also to their neighbors in the network. Our results characterize how much knowing the network structure affects the regret as a function of the model of agent activations. When activations are stochastic, the optimal regret (up to constant factors) is shown to be of order √α T, where T is the horizon and α is the independence number of the network. We prove that the upper bound is achieved even when agents have no information about the network structure. When activations are adversarial the situation changes dramatically: if agents ignore the network structure, a Omega(T) lower bound on the regret can be proven, showing that learning is impossible. However, when agents can choose to ignore some of their neighbors based on the knowledge of the network structure, we prove a O(√overlinechi T) sublinear regret bound, where overlinechi ≥ α is the clique-covering number of the network.