Distributed Bandits: Probabilistic Communication on d-regular Graphs

Udari Madhushani, Naomi Ehrich Leonard

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

Abstract

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.
Pages830-835
Number of pages6
ISBN (Electronic)9789463842365
DOIs
StatePublished - 2021
Event2021 European Control Conference, ECC 2021 - Delft, Netherlands
Duration: Jun 29 2021Jul 2 2021

Publication series

Name2021 European Control Conference, ECC 2021

Conference

Conference2021 European Control Conference, ECC 2021
Country/TerritoryNetherlands
CityDelft
Period6/29/217/2/21

All Science Journal Classification (ASJC) codes

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

Fingerprint

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

Cite this