# Collaborative Learning in General Graphs with Limited Memorization: Complexity, Learnability, and Reliability

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 53 references that are in the map.
- First posted on arXiv 29 Jan 2022.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Stochastic bandits robust to adversarial corruptions](https://mlsanity.com/paper/1803.09353/) (2018)
- [Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares](https://mlsanity.com/paper/1410.2596/) (2014)
- [Better Algorithms for Stochastic Bandits with Adversarial Corruptions](https://mlsanity.com/paper/1902.08647/) (2019)
- [Social Learning in Multi Agent Multi Armed Bandits](https://mlsanity.com/paper/1910.02100/) (2019)
- [Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1904.03293/) (2019)
- [Collaborative Learning of Stochastic Bandits over a Social Network](https://mlsanity.com/paper/1602.08886/) (2016)
- [On Regret-Optimal Learning in Decentralized Multi-player Multi-armed Bandits](https://mlsanity.com/paper/1505.00553/) (2015)
- [Robust Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2007.03812/) (2020)
- [Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without](https://mlsanity.com/paper/1904.12233/) (2019)
- [On Sequential Elimination Algorithms for Best-Arm Identification in Multi-Armed Bandits](https://mlsanity.com/paper/1609.02606/) (2016)
- [A Distributed Learning Dynamics in Social Groups](https://mlsanity.com/paper/1705.03414/) (2017)
- [Distributed Random Walks](https://mlsanity.com/paper/1302.4544/) (2013)
- [Collaboratively Learning the Best Option on Graphs, Using Bounded Local Memory](https://mlsanity.com/paper/1811.03968/) (2018)
- [Efficient Randomized Distributed Coloring in CONGEST](https://mlsanity.com/paper/2012.14169/) (2020)
- [Fast Distributed Algorithms for Testing Graph Properties](https://mlsanity.com/paper/1602.03718/) (2016)
- [Faster Deterministic All Pairs Shortest Paths in Congest Model](https://mlsanity.com/paper/2005.09588/) (2020)

## Abstract (arXiv)

We consider a K-armed bandit problem in general graphs where agents are arbitrarily connected and each of them has limited memorizing capabilities and communication bandwidth. The goal is to let each of the agents eventually learn the best arm. It is assumed in these studies that the communication graph should be complete or well-structured, whereas such an assumption is not always valid in practice. Furthermore, limited memorization and communication bandwidth also restrict the collaborations of the agents, since the agents memorize and communicate very few experiences. Additionally, an agent may be corrupted to share falsified experiences to its peers, while the resource limit in terms of memorization and communication may considerably restrict the reliability of the learning process. To address the above issues, we propose a three-staged collaborative learning algorithm. In each step, the agents share their latest experiences with each other through light-weight random walks in a general communication graph, and then make decisions on which arms to pull according to the recommendations received from their peers. The agents finally update their adoptions (i.e., preferences to the arms) based on the reward obtained by pulling the arms. Our theoretical analysis shows that, when there are a sufficient number of agents participating in the collaborative learning process, all the agents eventually learn the best arm with high probability, even with limited memorizing capabilities and light-weight communications. We also reveal in our theoretical analysis the upper bound on the number of corrupted agents our algorithm can tolerate. The efficacy of our proposed three-staged collaborative learning algorithm is finally verified by extensive experiments on both synthetic and real datasets.