mlsanityData to 14 Oct 2026

Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without

arXiv 1904.12233 ↗First posted 28 Apr 2019cs.LG cs.MA stat.MLcited by 14

Not on the map. Why?

Abstract (arXiv)

We consider the non-stochastic version of the (cooperative) multi-player multi-armed bandit problem. The model assumes no communication at all between the players, and furthermore when two (or more) players select the same action this results in a maximal loss. We prove the first √T-type regret guarantee for this problem, under the feedback model where collisions are announced to the colliding players. Such a bound was not known even for the simpler stochastic version. We also prove the first sublinear guarantee for the feedback model where collision information is not available, namely T^1-frac12m where m is the number of players.

Key facts. Cited by 14 papers in the map (data through 14 Oct 2026). First posted on arXiv 28 Apr 2019.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 5; 2022: 6; 2023: 2; 2024: 0; 2025: 1.

14 papers.

Sort:

  1. 2021Federated Multi-Armed Banditscited by 59
  2. 2021Regret, stability & fairness in matching markets with bandit learnerscited by 20
  3. 2022A survey on multi-player banditscited by 19
  4. 2021Heterogeneous Multi-player Multi-armed Bandits: Closing the Gap and Generalizationcited by 18
  5. 2022Distributed Bandits with Heterogeneous Agentscited by 9
  6. 2021Multi-player Multi-armed Bandits with Collision-Dependent Reward Distributionscited by 8
  7. 2023On-Demand Communication for Asynchronous Multi-Agent Banditscited by 7
  8. 2021An Instance-Dependent Analysis for the Cooperative Multi-Player Multi-Armed Banditcited by 6
  9. 2022The Pareto Frontier of Instance-Dependent Guarantees in Multi-Player Multi-Armed Bandits with no Communicationcited by 2
  10. 2022Decentralized Stochastic Multi-Player Multi-Armed Walking Banditscited by 2
  11. 2022Multi-Player Bandits Robust to Adversarial Collisionscited by 1
  12. 2025Communication Bounds for the Distributed Experts Problemcited by 1
2 more
  1. 2022Collaborative Learning in General Graphs with Limited Memorization: Complexity, Learnability, and Reliabilitycited by 0
  2. 2023Near-Optimal Privacy-Preserving Learning for Max-Min Fair Multi-Agent Banditscited by 0