Distributed Bandits: Probabilistic Communication on d-regular Graphs

Udari Madhushani, Naomi Ehrich Leonard

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations


We study the decentralized multi-agent multi-armed bandit problem for agents that communicate with probability over a network defined by a d-regular graph. Every edge in the graph has probabilistic weight p to account for the (1 - p) probability of a communication link failure. At each time step, each agent chooses an arm and receives a numerical reward associated with the chosen arm. After each choice, each agent observes the last obtained reward of each of its neighbors with probability p. We propose a new Upper Confidence Bound (UCB) based algorithm and analyze how agent-based strategies contribute to minimizing group regret in this probabilistic communication setting. We provide theoretical guarantees that our algorithm outperforms state-of-the-art algorithms. We illustrate our results and validate the theoretical claims using numerical simulations.

Original languageEnglish (US)
Title of host publication2021 European Control Conference, ECC 2021
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9789463842365
StatePublished - 2021
Externally publishedYes
Event2021 European Control Conference, ECC 2021 - Delft, Netherlands
Duration: Jun 29 2021Jul 2 2021

Publication series

Name2021 European Control Conference, ECC 2021


Conference2021 European Control Conference, ECC 2021

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Artificial Intelligence
  • Decision Sciences (miscellaneous)
  • Control and Systems Engineering
  • Mechanical Engineering
  • Computational Mathematics


Dive into the research topics of 'Distributed Bandits: Probabilistic Communication on d-regular Graphs'. Together they form a unique fingerprint.

Cite this