# Simple Opinion Dynamics for No-Regret Learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 52 references that are in the map.
- First posted on arXiv 14 Jun 2023.

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

- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication](https://mlsanity.com/paper/1902.00340/) (2019)
- [Stochastic Gradient Push for Distributed Deep Learning](https://mlsanity.com/paper/1811.10792/) (2018)
- [Decentralized Deep Learning with Arbitrary Communication Compression](https://mlsanity.com/paper/1907.09356/) (2019)
- [Delay and Cooperation in Nonstochastic Bandits](https://mlsanity.com/paper/1602.04741/) (2016)
- [Distributed Cooperative Decision-Making in Multiarmed Bandits: Frequentist and Bayesian Algorithms](https://mlsanity.com/paper/1606.00911/) (2016)
- [Social Learning in Multi Agent Multi Armed Bandits](https://mlsanity.com/paper/1910.02100/) (2019)
- [SIC-MMAB: Synchronisation Involves Communication in Multiplayer Multi-Armed Bandits](https://mlsanity.com/paper/1809.08151/) (2018)
- [Collaborative Learning of Stochastic Bandits over a Social Network](https://mlsanity.com/paper/1602.08886/) (2016)
- [Individual Regret in Cooperative Nonstochastic Multi-Armed Bandits](https://mlsanity.com/paper/1907.03346/) (2019)
- [Coordination without communication: optimal regret in two players multi-armed bandits](https://mlsanity.com/paper/2002.07596/) (2020)
- [A Distributed Learning Dynamics in Social Groups](https://mlsanity.com/paper/1705.03414/) (2017)
- [Collaboratively Learning the Best Option on Graphs, Using Bounded Local Memory](https://mlsanity.com/paper/1811.03968/) (2018)
- [Tight Bounds for Rumor Spreading with Vertex Expansion](https://mlsanity.com/paper/1302.6243/) (2013)
- [Plurality Consensus in the Gossip Model](https://mlsanity.com/paper/1407.2565/) (2014)
- [Human collective intelligence as distributed Bayesian inference](https://mlsanity.com/paper/1608.01987/) (2016)
- [Eigenvector Computation and Community Detection in Asynchronous Gossip Models](https://mlsanity.com/paper/1804.08548/) (2018)
- [The Evolutionary Price of Anarchy: Locally Bounded Agents in a Dynamic Virus Game](https://mlsanity.com/paper/1906.00110/) (2019)

## Abstract (arXiv)

We study a cooperative multi-agent bandit setting in the distributed GOSSIP model: in every round, each of n agents chooses an action from a common set, observes the action's corresponding reward, and subsequently exchanges information with a single randomly chosen neighbor, which may inform its choice in the next round. We introduce and analyze families of memoryless and time-independent protocols for this setting, inspired by opinion dynamics that are well-studied for other algorithmic tasks in the GOSSIP model. For stationary reward settings, we prove for the first time that these simple protocols exhibit best-of-both-worlds behavior, simultaneously obtaining constant cumulative regret scaling like R(T)/T = widetilde O(1/T), and also reaching consensus on the highest-mean action within widetilde O(√n) rounds. We obtain these results by showing a new connection between the global evolution of these decentralized protocols and a class of zero-sum multiplicative weights update processes. Using this connection, we establish a general framework for analyzing the population-level regret and other properties of our protocols. Finally, we show our protocols are also surprisingly robust to adversarial rewards, and in this regime we obtain sublinear regret scaling like R(T)/T = widetilde O(1/√T) as long as the number of rounds does not grow too fast as a function of n.